Mixed binary/ternary codes

A.E. Brouwer, H.O. Hämäläinen, P.R.J. Östergård & N.J.A. Sloane,
Bounds on Mixed Binary/Ternary Codes,
IEEE Trans. Inf. Th. 44 (1998) 140-161

N(m,n,d) is defined as the maximum number of vectors of length m+n with m binary and n ternary coordinates and mutual distance at least d. If n=0 or m=0, this is about binary or ternary codes, and discussed elsewhere. The case m > 0, n > 0 is the truly mixed case discussed here. The cases d ≤ 2 or d ≥ m+n−1 are easy and have been settled completely. Here we copy the tables from the reference above and add some modern improvements.

Football pool

The covering problem is interesting if one wants to be sure to get a prize. The packing problem, if one does not want to waste money by covering the same possibility twice. The function N(m,n,d) answers the packing problem (with d = 2e+1).

Since our football pools have 13 matches, that explains the restriction to m+n ≤ 13 in the tables in [BHÖS]. However, the spanish Quiniela has 14+1 matches, so there is interest in extending these tables to m+n ≤ 14.

Errors

This wrong construction was used to show that N(13,2,6) ≥ 134, N(12,2,6) ≥ 68, N(12,1,5) ≥ 68, N(11,2,6) ≥ 38, N(11,1,5) ≥ 38, so that these five values are now in doubt. We can use N(12,1,5) ≥ N(13,0,5) = 64, N(11,1,5) ≥ N(12,0,5) = 32, N(10,3,6) ≥ N(11,2,6) ≥ N(12,1,6) = 32 instead. These smaller lower bounds are given in blue.

Improvements

Additions

d = 3

m\n	0	1	2	3	4	5	6	7
0	1	1	1	3	9	18	38	99-111
1	1	1	2	6	12	33	71-76	198-222
2	1	2	4	9	22	52-66	134-152	396-444
3	2	3	6	18	42-44	99-126	264-304	711-888
4	2	6	12	28-33	72-88	186-243	486-608	1422-1749
5	4	8	22	54-65	144-167	348-457	948-1216	2592-3259
6	8	16	38-44	108-123	288-322	648-863	1896-2332	5184-6362
7	16	26-30	72-85	192-230	576-609	1296-1612	3792-4443	10368-12171
8	20	50-60	144-160	384-417	1152	2560-3110	6912-8331
9	40	96-109	288-293	768-806	1728-2131	4608-5924
10	72	192-213	512-556	1152-1536	3280-4147
11	144	384	848-1049	2304-2910
12	256	768	1536-2011
13	512	1120-1365
14	1024

m\n	8	9	10	11	12	13	14
0	246-333	729-937	2187-2808	6561-7029	19683	59049	118098-153527
1	486-666	1458-1874	4374-4920	13122-14058	39366	78732-106288
2	972-1284	2916-3514	8748-9840	26244-26790	59049-75920
3	1944-2464	5832-6846	17496-18589	40095-52488
4	3888-4767	11664-12887	34992-36337
5	7776-9128	23328-25194
6	15552-17485

The bound N(10,0,3) ≤ 72 (and hence N(11,0,3) ≤ 144) was obtained in

P.R.J. Östergård, T. Baicheva & E. Kolev,
Optimal binary one-error-correcting codes of length 10 have 72 codewords,
IEEE Trans. Inform. Theory 45 (1999) 1229-1231.

The bounds N(0,6,3) ≤ 38 (and hence N(a,6,3) ≤ 38.2^a) and N(0,7,3) ≤ 111 (and hence N(a,7+b,3) ≤ 111.2^a.3^b) were obtained in

P.R.J. Östergård,
Classification of binary/ternary one-error-correcting codes,
Discrete Math. 223 (2000) 253-262.

The bound N(0,10,3) ≤ 2808 is due to

W. Lang, J. Quistorff & E. Schneider,
New Results on Integer Programming for Codes,
Congr. Numer. 188 (2007) 97-107.

The bound N(3,5,3) ≥ 99 follows by explicit construction due to Pedro fdez, 2011-04-28.

The bound N(0,8,3) ≥ 246 follows by explicit construction due to ehl555, 2011-07-17.

The bound N(5,5,3) ≥ 348 follows by explicit construction due to Pucho, 2011-03-03.

The bound N(11,2,3) ≥ 848 follows by explicit construction due to Código, 2011-04-10.

The bound N(13,1,3) ≥ 1120 follows by explicit construction due to Código, 2011-04-07.

The bound N(4,7,3) ≥ 1422 follows by explicit construction due to PacoHH, 2010-12-08. It implies N(3,7,3) ≥ 711.

The bounds N(8,5,3) ≥ 2560 and N(10,4,3) ≥ 3280 follow by explicit construction due to Código, 2011-04-04.

The bounds N(11,3,3) ≥ 2304, N(9,5,3) ≥ 4608, N(8,6,3) ≥ 6624, N(7,7,3) ≥ 9720, N(6,8,3) ≥ 14256 were announced by PacoHH, 2010-11-30. On this page one finds a zip file with codes confirming these.

The bounds N(8,6,3) ≥ 6912, N(7,7,3) ≥ 10368, N(6,8,3) ≥ 15552, N(5,9,3) ≥ 23328, N(4,10,3) ≥ 34992, N(3,11,3) ≥ 40095 were announced by Código. All follow from the last two. No explicit construction was given.

d = 4

m\n	0	1	2	3	4	5	6	7
0	1	1	1	1	3	6	18	33
1	1	1	1	2	4	12	33	66
2	1	1	2	3	8	22	51-66	114-132
3	1	2	3	6	15	36-44	92-124	216-264
4	2	2	6	11	28-30	62-86	158-242	408-528
5	2	4	8	20	48-60	114-167	288-454	756-1056
6	4	8	16	34-40	96-120	216-319	576-863	1512-2112
7	8	16	26-30	64-80	192-230	408-612	1152-1612	2994-4224
8	16	20	50-60	128-160	384-417	768-1120	2304-3224
9	20	40	96-109	256-293	540-782	1536-2199
10	40	72-76	192-213	410-556	1024-1533
11	72	144-152	384	768-1060
12	144	256	768
13	256	512
14	512

m\n	8	9	10	11	12	13	14
0	99	243-297	729-891	1458-2561	4374-6839	8559-19270	24786-54774
1	162-198	486-594	972-1749	2916-4920	8019-13678	16767-38540
2	324-396	729-1188	1944-3498	5589-9777	16038-27356
3	510-792	1296-2376	3726-6791	10692-19554
4	1020-1584	2484-4752	7128-13122
5	1845-3168	4752-9313
6	3634-6336

We have N(11,0,4) = N(10,0,3) and N(12,0,4) = N(11,0,3).

The bound N(0,7,4) ≤ 33 (with usual consequences for N(a,7+b,4)) is due to

P.R.J. Östergård,
On binary/ternary error-correcting codes with minimum distance 4,
in: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (M. Fossorier, H. Imai, S. Lin, and A. Poli, Eds.), LNCS 1719, Springer, Berlin 1999, pp. 472-481.

The bounds N(0,12,4) ≤ 6839 and N(0,13,4) ≤ 19270 are due to

Dion Gijswijt, Alexander Schrijver & Hajime Tanaka,
New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming,
JCT (A) 113 (2006) 1719-1731.

The bound N(8,2,4) ≥ 50 follows by explicit construction due to PacoHH, 2010-12-10.

The bound N(3,5,4) ≥ 36 follows by explicit construction due to PacoHH, 2010-11-28.

The bound N(4,5,4) ≥ 62 follows by explicit construction due to PacoHH, 2010-12-02.

The bound N(5,5,4) ≥ 114 follows by explicit construction due to Pedro fdez, 2011-03-01.

The bound N(7,5,4) ≥ 408 follows by explicit construction due to Joan, 2011-02-27.

The bound N(3,6,4) ≥ 92 follows by explicit construction due to PacoHH, 2010-12-16.

The bound N(4,6,4) ≥ 158 follows by explicit construction due to Código, 2011-04-02.

The bound N(5,6,4) ≥ 216 follows by explicit construction due to PacoHH, 2011-03-16.

The bound N(2,7,4) ≥ 114 follows by explicit construction due to PacoHH, 2011-03-16.

The bound N(4,7,4) ≥ 408 follows by explicit construction due to Código, 2011-04-02.

The bound N(5,8,4) ≥ 1845 follows by explicit construction due to Pucho, 2011-03-02.

The bounds N(3,8,4) ≥ 510, N(4,8,4) ≥ 1020 follow by explicit construction due to PacoHH, 2011-03-03.

The bound N(5,7,4) ≥ 756 follows by explicit construction due to Pucho, 2011-03-01.

The bound N(6,7,4) ≥ 1512 follows by explicit construction due to Pucho, 2011-03-02.

The bound N(7,7,4) ≥ 2994 follows by explicit construction due to Pucho, 2011-03-02.

The bound N(10,3,4) ≥ 410 follows by explicit construction due to PacoHH, 2011-03-02.

The bound N(0,13,4) ≥ 8559 follows by explicit construction due to Código, 2011-03-26.

The bound N(1,13,4) ≥ 16767 follows by explicit construction due to Código, 2011-03-27.

The bound N(0,14,4) ≥ 24786 follows by explicit construction due to Código, 2011-03-19.

All unexplained lower bounds can be found in the file provided by PacoHH, 2011-03-03.

d = 5

m\n	0	1	2	3	4	5	6	7
0	1	1	1	1	1	3	4	10
1	1	1	1	1	2	3	8	18
2	1	1	1	2	3	6	15	36
3	1	1	2	3	6	12	24-27	72
4	1	2	2	4	9	18	48-54	144
5	2	2	4	6	14	33-36	96-108	216-288
6	2	3	6	12	28	66-72	144-216	378-576
7	2	4	9	20-24	44-56	99-144	255?-432	648-1089
8	4	7	16	34-48	84-112	180-288	453-806
9	6	12	26-32	64-91	136-224	318-576
10	12	24	48-64	128-170	234-427
11	24	32-48	96-121	192-316
12	32	64-86	192-236
13	64	128-170
14	128

m\n	8	9	10	11	12	13	14
0	27	81	243	729	729-1557	2187-4078	6561-10624
1	54	162	486	729-1145	1458-2984	4374-7630
2	108	324	729-867	972-2157	2916-5636
3	216	486-633	729-1567	1944-4122
4	324-432	729-1153	1458-2921
5	486-850	1458-2098
6	972-1481

N(0,12,5) ≤ 1557 and N(0,13,5) ≤ 4078 is due to Gijswijt et al., see above.

The bound N(6,4,5) ≥ 28 follows by explicit construction due to Joan, 2010-11-21.

The bound N(8,3,5) ≥ 34 follows by explicit construction due to Pucho, 2011-03-19.

The bound N(8,4,5) ≥ 84 follows by explicit construction due to Código, 2011-03-19.

The bound N(8,5,5) ≥ 180 follows by explicit construction due to PacoHH, 2011-06-07.

The bound N(7,6,5) ≥ 240 follows by explicit construction due to PacoHH, 2011-02-18 or earlier. This link also reveals that PacoHH is Francisco Hernández Hernández.

The bound N(6,7,5) ≥ 378 follows by explicit construction due to spaik, 2011-06-02.

The bound N(8,6,5) ≥ 453 follows by explicit construction due to PacoHH, 2011-06-05.

The bound N(7,6,5) ≥ 255 was announced by Código.

d = 6

m\n	0	1	2	3	4	5	6	7
0	1	1	1	1	1	1	3	3
1	1	1	1	1	1	2	3	6
2	1	1	1	1	2	3	6	12
3	1	1	1	2	3	4	12	24
4	1	1	2	2	4	8	18	48
5	1	2	2	3	6	12	33-36	96
6	2	2	3	6	12	24	66-72	144-192
7	2	2	4	8	18-24	44-48	99-144	216-384
8	2	4	7	16	32-43	66-96	144-288
9	4	6	12	26-32	56-77	108?-192
10	6	12	24	44-61	88-153
11	12	24	32-48	88-112
12	24	32	64-87
13	32	64
14	64

m\n	8	9	10	11	12	13	14
0	9	27	81	243	729	729-1449	2187-3660
1	18	54	162	486	729-1145	1458-2868
2	36	108	324	729-867	972-2093
3	72	216	486-614	729-1512
4	144	324-425	729-1133
5	216-288	486-829
6	324-576

N(0,13,6) ≤ 1449 is due to Gijswijt et al., see above.

N(10,3,6) ≥ 44 follows by explicit construction due to Pucho, 2011-03-15.

N(6,5,6) ≥ 24 follows by explicit construction due to Pucho, 2011-03-15.

N(9,4,6) ≥ 56 follows by explicit construction due to Joan, 2011-03-15.

N(10,4,6) ≥ 88 follows by explicit construction due to PacoHH, 2011-03-15.

N(11,3,6) ≥ 88 follows by explicit construction due to Pedro fdez, 2011-05-05.

N(2,12,6) ≥ 972 follows by explicit construction due to PacoHH, 2011-07-04.

d = 7

m\n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	1	1	1	1	1	1	1	3	3	6	14	36	60-108	162-324	243-805
1	1	1	1	1	1	1	2	3	6	12	24-28	48-72	108-216	243-623
2	1	1	1	1	1	2	3	4	9	18-24	36-56	75-144	162-432
3	1	1	1	1	2	3	4	7	16-18	27-48	54-112	108-288
4	1	1	1	2	2	3	6	14	24-36	48-96	81-224
5	1	1	2	2	3	6	12	21-28	36-72	69-180
6	1	2	2	3	4	9	18-24	33-56	60-135
7	2	2	2	4	8	16	24-45	58-102
8	2	2	4	6	16	22-32	40-79
9	2	3	4	12	18-26	32-62
10	2	4	8	16-18	28-47
11	4	6	12	24-35
12	4	12	20-24
13	8	16-20
14	16

N(0,10,7) ≤ 14 is due to

K.S. Kapralov,
The nonexistence of ternary (10,15,7) codes,
Proc. 7th international workshop on algebraic and combinatorial coding theory (ACCT'2000), Bansko, Bulgaria, 18-24 June, 2000, pp. 189-192.

N(0,11,7) ≤ 36 (and hence N(0,12,7) ≤ 108, N(0,13,7) ≤ 324) is due to

M.J. Letourneau & S.K. Houghten,
Optimal Ternary (11,7) and (14,10) Codes,
Journal of Combinat. Math. and Combinat. Computing 51 (2004) 159-164.

The bound N(0,12,7) ≥ 60 follows by explicit construction due to spaik, 2011-06-22.

The bound N(0,13,7) ≥ 162 follows by explicit construction (18 cosets of <1011100011122,0100011122111>) due to spaik, 2011-06-11.

The bound N(1,11,7) ≥ 48 follows by explicit construction (16 cosets of <0³1⁹>) due to Código, 2011-03-13.

The bounds N(1,12,7) ≥ 108 and N(2,12,7) ≥ 162 and N(3,11,7) ≥ 108 follow from N(0,13,7) ≥ 162.

The bound N(1,13,7) ≥ 243 follows by explicit construction due to PacoHH, 2011-06-12.

The bound N(2,11,7) ≥ 75 follows from N(2,12,8) ≥ 75.

The bound N(3,9,7) ≥ 27 follows by explicit construction due to Pucho, 2011-03-14.

The bound N(3,10,7) ≥ 54 follows by explicit construction due to Código, 2011-04-02.

The bounds N(4,8,7) ≥ 24, N(5,8,7) ≥ 36 follow by explicit construction due to Pucho, 2011-03-13.

The bound N(4,9,7) ≥ 48 follows by explicit construction due to Código, 2011-04-02.

The bound N(4,10,7) ≥ 81 follows by explicit construction due to spaik, 2011-06-11.

The bound N(5,7,7) ≥ 21 follows by explicit construction due to PacoHH, 2010-12-05.

The bound N(5,9,7) ≥ 69 follows by explicit construction due to spaik, 2011-06-11.

The bound N(6,6,7) ≥ 18 follows by explicit construction due to PacoHH, 2010-12-17.

The bound N(6,7,7) ≥ 33 follows by explicit construction due to spaik, 2011-07-18.

The bounds N(7,7,7) ≥ 58 and N(6,8,7) ≥ 60 follow by explicit construction due to spaik, 2011-07-17.

The bound N(8,5,7) ≥ 22 follows by explicit construction due to PacoHH, 2012-03-26.

The bound N(8,6,7) ≥ 40 follows by explicit construction due to PacoHH, 2011-05-16.

The bound N(9,5,7) ≥ 32 follows by explicit construction due to Pucho, 2011-03-13.

The bound N(10,4,7) ≥ 28 follows by explicit construction due to Pucho, 2011-03-13.

d = 8

m\n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	1	1	1	1	1	1	1	1	3	3	6	12	36	54-95	108-237
1	1	1	1	1	1	1	1	2	3	4	9	24	39-72	81-179
2	1	1	1	1	1	1	2	3	4	7	18	36-48	75-139
3	1	1	1	1	1	2	3	3	6	13	24-36	54-96
4	1	1	1	1	2	2	3	6	12	24-26	42-72
5	1	1	1	2	2	3	4	8	18-24	30-52
6	1	1	2	2	3	4	7	14-16	24-46
7	1	2	2	2	4	6	12	23-32
8	2	2	2	3	6	12	18-24
9	2	2	3	4	9	18
10	2	2	4	6	16
11	2	4	6	12
12	4	4	12
13	4	8
14	8

N(0,13,8) ≤ 95 is due to Gijswijt et al., see above.

N(0,13,8) ≥ 54 follows by explicit construction due to PacoHH, 2011-03-14.

N(1,12,8) ≥ 39 follows by explicit construction due to Código, 2011-04-04.

N(4,10,8) ≥ 42 follows by explicit construction due to Joan, 2011-07-23.

N(3,11,8) ≥ 45 follows by explicit construction due to PacoHH, 2011-04-26.

N(2,12,8) ≥ 75 follows by explicit construction due to spaik, 2011-06-26.

N(1,13,8) ≥ 81 follows by explicit construction due to spaik, 2011-06-27.

N(0,14,8) ≥ 108 follows by explicit construction due to Joan, 2011-07-24.

N(7,7,8) ≥ 23 follows by explicit construction due to spaik, 2011-07-23.

N(6,8,8) ≥ 24 follows by explicit construction due to Joan, 2011-03-18.

N(4,9,8) ≥ 24 follows by explicit construction given by Pedro fdez, 2011-04-12.

N(5,9,8) ≥ 30 follows by explicit construction given by PacoHH, 2011-03-18.

d = 9

m\n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	1	1	1	1	1	1	1	1	1	3	3	4	9	27	36-62
1	1	1	1	1	1	1	1	1	2	3	4	6	18	30-54
2	1	1	1	1	1	1	1	2	3	3	6	12	27-36
3	1	1	1	1	1	1	2	3	3	6	10	19-24
4	1	1	1	1	1	2	2	3	4	8	18-20
5	1	1	1	1	2	2	3	4	6	14-16
6	1	1	1	2	2	3	4	6	12
7	1	1	2	2	2	3	6	10
8	1	2	2	2	3	4	8
9	2	2	2	3	4	6
10	2	2	2	4	6
11	2	2	4	6
12	2	3	4
13	2	4
14	4

N(0,14,9) ≥ 36 follows by explicit construction due to spaik, 2011-04-09.

N(1,13,9) ≥ 30 follows by explicit construction due to spaik, 2011-06-05.

N(3,11,9) ≥ 19 follows by explicit construction due to spaik, 2011-06-30.

d = 10

m\n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	1	1	1	1	1	1	1	1	1	1	3	3	4	6	13
1	1	1	1	1	1	1	1	1	1	2	3	3	6	10-12
2	1	1	1	1	1	1	1	1	2	3	3	6	9
3	1	1	1	1	1	1	1	2	3	3	4	7
4	1	1	1	1	1	1	2	2	3	4	6
5	1	1	1	1	1	2	2	3	4	6
6	1	1	1	1	2	2	3	3	6
7	1	1	1	2	2	2	3	4
8	1	1	2	2	2	3	4
9	1	2	2	2	3	4
10	2	2	2	2	4
11	2	2	2	3
12	2	2	3
13	2	2
14	2