d=3 d=4 d=5 d=6 d=7 d=8 d=9 d=10

Mixed binary/ternary codes

In
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
(quoted as [BHÖS]) bounds on the size of mixed binary/ternary codes were given.

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

This problem gets attention from football pool enthusiasts. Suppose some games will be played, and for n games the result (win/equal/loss) is open, while for m games there are only two possible outcomes one wishes to consider, and all remaining games have an outcome that is presumed known.
The covering problem now asks: How many football pool forms do I have to fill in order to be sure that at least one of them has not more than e wrong predictions? See Kéri for tables on covering codes.
The packing problem asks: How many football pool forms can I fill so that for no possible outcome there are two forms, both with at most e wrong predictions?

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

Pedro Pablo Rivas Soriano pointed out two flaws in [BHÖS]. One a typo: the last codeword of code C3 in Lemma 5.5 should be "01002" instead of "02010". The other an error: the construction that was supposed to produce a partition of S(5,6,12) into six 22-word codes with minimum distance 6 is wrong. That means that some lower bounds will have to be revised.

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

Various upper bounds were improved by linear or semidefinite programming or backtrack search. Various lower bounds were improved by explicit constructions, all but one of which were found in this discussion (by Código, Joan, PacoHH, Pucho, jnacho, Pedro fdez, spaik, and others) on a spanish forum about football pools. In the tables below, improvements are given in red.

A large number of improved upper bounds was given in

Bart Litjens,
Semidefinite bounds for mixed binary/ternary codes,
arXiv:1606.06930v1
These upper bounds are not quoted separately, but are given in the tables in purple.

Additions

Values for m+n = 14 were added. Almost all lower bounds are from the abovementioned spanish forum.

d = 3

The table here gives bounds for N(m,n,d) where d=3, with m indexing the rows and n indexing the columns. Values given without explanation are from the above-cited [BHÖS]. Changes are explained below.

m\n 0 1 2 3 4 5 6 7
0 1113918 38 99-111
1 11261233 71-76 198-222
2 12492252-65 134-152 396-444
3 2361842-44 99-125 266-304 711-888
4 261228-3072-88186-238 504-608 1422-1749
5 482254-60144-165 348-457 1008-1216 2592-3259
6 81638-44108-118288-317 672-8551896-2332 5184-6362
7 1626-3072-83192-225576-604 1296-16123792-4443 10368-12171
8 2050-59144-154384-4141152 2560-3087 6912-8331
94096-108288-292 768-796 1728-2130 4608-5924
1072192-212 512-5521152-1492 3280-4081
11144384 848-1049 2304-2890
12256768 1536-2011
13512 1120-1360
141024

m\n 8 9 10 11 12 13 14
0 252-333 729-9372187-28086561-7029 1968359049 118098-153527
1 486-666 1458-18744374-492013122-1405839366 78732-106288
2 972-12842916-35148748-984026244-26790 59049-75920
3 1944-24645832-684617496-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 (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.2a) and N(0,7,3) ≤ 111 (and hence N(a,7+b,3) ≤ 111.2a.3b) 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(5,6,3) ≥ 1008 follows by explicit construction due to Pucho, 2012-04-23.

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

Bounds for N(m,n,d) where d=4.

m\n 0 1 2 3 4 5 6 7
0 11113618 33
1 1112412 3366
2 1123822 51-61114-132
3 123615 36-43 92-117 216-264
4 2261128-30 62-83 158-228 408-528
5 24820 50-59 114-160288-436 762-1056
6 481634-4096-114 216-308576-825 1512-2112
7 81626-3064-80192-220 408-5851152-1576 3024-4224
8 162050-59 128-153 384-407768-1103 2304-3027
9 204096-108256-288 548-771 1536-2105
10 4072-76192-212 420-548 1050-1480
11 72144-152384 784-1032
12 144256 768
13 256512
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-17492916-4920 8019-13531 16767-37714
2 324-396 729-1188 1944-33715589-9450 16038-27356
3 528-792 1296-23763726-6581 10692-18039
4 1056-1584 2484-4590 7128-13122
5 1896-3168 4752-9180
6 3660-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,4,4) ≥ 50 follows by explicit construction due to PFPGU, 2012-05-08.

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

Bounds for N(m,n,d) where d=5.

m\n 0 1 2 3 4 5 6 7
0 1111134 10
1 1111238 18
2 11123615 36
3 112361224-27 72
4 122491848-54 144
5 22461433-36 96-108216-288
6 2361228 66-72144-216 378-563
7 24920-2444-5699-144 255-407 648-1047
8 471634-4484-112 180-288 453-755
9 61226-3164-85 136-216 318-534
10 122448-61128-158 234-390
11 2438-4396-115 192-292
12 3264-83 192-213
13 64128-156
14 128

m\n 8 9 10 11 12 13 14
0 2781243729 729-1557 2187-4078 6561-10624
1 54162486729-1138 1458-2927 4374-7598
2 108324729-849972-2105 2916-5512
3 216486-601729-1519 1944-3964
4 324-420729-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

Bounds for N(m,n,d) where d=6.

m\n 0 1 2 3 4 5 6 7
0 1111113 3
1 1111123 6
2 1111236 12
3 11123412 24
4 11224818 48
5 122361233-36 96
6 2236122466-72 144-192
7 224818-2244-48 99-142 216-375
8 2471632-3966-96 168-273
9 461226-30 56-75 112-192
10 6122444-56 88-144
11 122432-43 88-107
12 243264-83
13 3264
14 64

m\n 8 9 10 11 12 13 14
0 92781243729 729-1449 2187-3660
1 1854162486729-1073 1458-2657
2 36108324729-803 972-1935
3 72216486-574 729-1414
4 144324-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.

d = 7

Bounds for N(m,n,d) where d=7.

m\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1111111 33614 36 60-108 162-324 243-805
1 1111112 361224-28 48-72 108-216 243-591
2 1111123 4918-2436-56 75-144 162-432
3 1111234 716-1828-4857-112 108-288
4 1112236 1424-3648-96 84-224
5 11223612 21-2836-72 69-174
6 122349 18-23 33-53 61-130
7 222481624-41 58-99
8 22461622-31 44-74
9 2341218-23 36-53
10 24816-18 28-41
11 4612 24-31
12 412 20-24
13 816-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 (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 <0319>) 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

Bounds for N(m,n,d) where d=8.

m\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1111111 13361236 54-95 108-237
1 1111111 23492439-67 81-179
2 1111112 3471836-48 75-134
3 1111123 361324-3654-96
4 1111223 61224-2642-72
5 1112234 818-2430-52
6 1122347 14-1628-44
7 12224612 23-32
8 2223612 20-24
9 22349 18
10 2246 16
11 24612
12 4412
13 48
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

Bounds for N(m,n,d) where d=9.

m\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1111111 11334927 36-62
1 1111111 1234618 30-50
2 1111111 233612 27-36
3 1111112 33610 20-24
4 1111122 348 18-20
5 1111223 46 14-16
6 1112234 612
7 1122236 10
8 1222348
9 222346
10 22246
11 2246
12 234
13 24
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

Bounds for N(m,n,d) where d=10.

m\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1111111 1113346 13
1 1111111 11233610-12
2 1111111 123369
3 1111111 23347
4 1111112 2346
5 1111122 346
6 1111223 36
7 1112223 4
8 1122234
9 122234
10 22224
11 2223
12 223
13 22
14 2