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. Some of them were again improved later.

Improvements

A large number of improved upper bounds was given in

Bart Litjens,
Semidefinite bounds for mixed binary/ternary codes,
Discr. Math. 341 (2018) 1740-1748. arXiv:1606.06930

No reference is given for upper bounds that are a consequence of N(m+1,n,d) ≤ 2N(m,n,d) or N(m,n+1,d) ≤ 3N(m,n,d).

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-74	198-222
2	1	2	4	9	22	52-54	134-148	396-444
3	2	3	6	18	42	100-108	266-296	711-888
4	2	6	12	28	72	186-216	504-592	1422-1749
5	4	8	22	54	144	348-432	1008-1184	2592-3259
6	8	16	38	108	288	672-855	1896-2332	5184-6362
7	16	26	72	192-216	576	1296-1612	3792-4443	10368-12171
8	20	50	144	384-414	1152	2560-3087	6912-8331
9	40	96-100	288	768-796	1728-2130	4608-5924
10	72	192-200	512-552	1152-1492	3280-4081
11	144	384	864-1049	2304-2890
12	256	768	1536-2011
13	512	1120-1360
14	1024

m\n	8	9	10	11	12	13	14
0	252-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-4764	11664-12887	34992-36337
5	7776-9128	23328-25194
6	15552-17485

The bound N(10,0,3) ≤ 72 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(7,1,3) ≤ 26, N(8,1,3) ≤ 50, N(6,2,3) ≤ 38, N(7,2,3) ≤ 72, N(4,3,3) ≤ 28, N(5,3,3) ≤ 54, N(3,4,3) ≤ 42, N(4,4,3) ≤ 72, N(2,5,3) ≤ 54, N(1,6,3) ≤ 74, N(0,6,3) ≤ 38, N(0,7,3) ≤ 111 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) ≥ 252 follows by explicit construction due to ehl555, 2012-04-25.

The bound N(3,6,3) ≥ 266 follows by explicit construction due to PacoHH, 2013-01-03.

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(5,6,3) ≥ 1008 follows by explicit construction due to Pucho, 2012-04-23.

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.

The bounds N(3,5,3) ≥ 100 and N(11,2,3) ≥ 864, were found by anonymous, and given on this forum page (with explicit codes given in D3.zip).

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	114-132
3	1	2	3	6	15	36	92-96	216-264
4	2	2	6	11	28	62-64	158-192	408-528
5	2	4	8	20	50	114-128	288-384	762-1056
6	4	8	16	34	96	216-256	576-768	1512-2112
7	8	16	26	64-68	192	408-512	1152-1536	3024-4224
8	16	20	50	128-136	384	768-1024	2304-3027
9	20	40	96-100	256-272	548-768	1536-2048
10	40	72	192-200	420-544	1050-1480
11	72	144	384	784-1032
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-13531	16767-37714
2	324-396	729-1188	1944-3371	5589-9450	16038-27356
3	528-792	1296-2376	3726-6581	10692-18039
4	1056-1584	2484-4590	7128-13122
5	1896-3168	4752-9180
6	3660-6336

We have N(8,2,4) ≤ N(8,1,3) and N(10,1,4) ≤ N(11,0,4) ≤ N(10,0,3) and N(3,6,4) ≤ (3/2)N(4,5,4).

The bounds N(6,3,4) ≤ 34, N(5,4,4) = 50, N(6,4,4) ≤ 96, N(3,5,4) = 36, N(4,5,4) ≤ 64, N(2,6,4) ≤ 51, N(3,6,4) ≤ 100, N(0,7,4) ≤ 33 are 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(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 bounds N(3,8,4) ≥ 528, N(4,8,4) ≥ 1056 follow by explicit construction due to spaik and Código, 2011-04-25.

The bound N(5,8,4) ≥ 1896 follows by explicit construction due to spaik, 2012-04-25.

The bound N(6,8,4) ≥ 3660 follows by explicit construction due to PacoHH, 2013-01-02.

The bound N(5,7,4) ≥ 762 follows by explicit construction due to Pucho, 2012-04-25.

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

The bound N(7,7,4) ≥ 3024 follows by explicit construction due to Pucho, 2012-04-25.

The bound N(10,3,4) ≥ 420 follows by explicit construction due to PacoHH, 2012-12-21.

The bound N(11,3,4) ≥ 784 follows by explicit construction due to Pucho, 2012-05-21.

The bound N(9,4,4) ≥ 548 follows by explicit construction due to PFPGU, 2012-05-21.

The bound N(10,4,4) ≥ 1050 follows by explicit construction due to PacoHH, 2012-11-08.

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-563
7	2	4	9	20-24	44-56	99-144	255-407	648-1047
8	4	7	16	34-44	84-112	180-288	453-755
9	6	12	26-31	64-85	136-216	318-534
10	12	24	48-61	128-158	234-390
11	24	38-43	96-115	192-292
12	32	64-83	192-213
13	64	128-156
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-1138	1458-2927	4374-7598
2	108	324	729-849	972-2105	2916-5512
3	216	486-601	729-1519	1944-3964
4	324-420	729-1099	1458-2801
5	486-791	1458-2000
6	972-1437

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 bounds N(11,1,5) ≥ 38 and N(7,6,5) ≥ 240 follow 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. The bound N(5,9,5) ≥ 1458 was announced by Pucho. Constructions are given here.

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-22	44-48	99-142	216-375
8	2	4	7	16	32-39	66-96	168-273
9	4	6	12	26-30	56-75	112-192
10	6	12	24	44-56	88-144
11	12	24	38-43	88-107
12	24	32	64-83
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-1073	1458-2657
2	36	108	324	729-803	972-1935
3	72	216	486-574	729-1414
4	144	324-425	729-1036
5	216-276	486-744
6	324-527

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(8,6,6) ≥ 168 follows by explicit construction due to spaik, 2012-04-18.

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

N(11,2,6) ≥ 38 restores a lower bound that was earlier given using an erroneous argument, this time using an explicit construction by anonymous, given on this forum page (in D6.zip).

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-591
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	28-48	57-112	108-288
4	1	1	1	2	2	3	6	14	24-36	48-96	84-224
5	1	1	2	2	3	6	12	21-28	36-72	69-174
6	1	2	2	3	4	9	18-23	33-53	61-130
7	2	2	2	4	8	16	24-41	58-99
8	2	2	4	6	16	22-31	44-74
9	2	3	4	12	18-23	36-53
10	2	4	8	16-18	28-41
11	4	6	12	24-31
12	4	12	20-24
13	8	16-19
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 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) ≥ 28 follows by explicit construction due to spaik, 2012-04-08.

The bound N(3,10,7) ≥ 57 follows by explicit construction due to spaik, 2012-05-09.

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) ≥ 84 follows by explicit construction due to spaik, 2012-04-17.

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 bound N(6,8,7) ≥ 61 follows by explicit construction due to spaik, 2012-04-02.

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) ≥ 44 follows by explicit construction due to spaik, 2012-12-19.

The bound N(9,5,7) ≥ 36 follows by explicit construction due to PacoHH, 2012-12-16.

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-67	81-179
2	1	1	1	1	1	1	2	3	4	7	18	36-48	75-134
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	28-44
7	1	2	2	2	4	6	12	23-32
8	2	2	2	3	6	12	20-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) ≥ 28 follows by explicit construction due to spaik, 2012-04-10.

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.

N(8,6,8) ≥ 20 follows by explicit construction given by Pucho, 2012-04-22.

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-50
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	20-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) ≥ 20 follows by explicit construction due to spaik, 2012-04-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