n\w | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
15 | 399 | |||||||||||
16 | 322 | 616 | ||||||||||
17 | ||||||||||||
18 | 544 | 2042 | ||||||||||
19 | ||||||||||||
20 | 10048 | |||||||||||
21 | 1113 | 6161 | 10767 | 17177 | 20654 | |||||||
22 | 8338 | 16527 | 25902 | 37127 | 40624 | |||||||
23 | 11696 | 23467 | 41413 | 58659 | 76233 | |||||||
24 | 59904 | 98852 | 118422 | 151484 | ||||||||
25 | 7787 | 21220 | 47265 | 89742 | 142373 | 198387 | 231530 | |||||
26 | 27050 | 66352 | 129708 | 222775 | 320584 | 401937 | 431724 | |||||
27 | 35874 | 88604 | 188561 | 334859 | 518014 | 686164 | 791461 | |||||
28 | 44915 | 122685 | 263008 | 508952 | 819041 | 1167909 | 1420920 | 1535756 | ||||
29 | 4423 | 17710 | 57943 | 157734 | 365699 | 728330 | 1266026 | 1895939 | 2499311 | 2870880 | ||
30 | 4901 | 21931 | 73853 | 214545 | 514015 | 1085000 | 1977548 | 3143989 | 4325235 | 5313399 | 5697080 | |
n/w | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
[aeb & T. Etzion, Nov-Dec 2009]
The standard reference for bounds on binary constant weight codes of length at most 28 is
A. E. Brouwer, James B. Shearer, N. J. A. Sloane & Warren D. Smith,NJAS has a somewhat updated online version. A more recent version by aeb.
A new table of constant weight codes,
IEEE Trans. Inf. Th. 36 (1990) 1334-1380.
Tuvi Etzion & Sara Bitan,and
On the chromatic number, colorings, and codes of the Johnson graph,
Discr. Applied Math. 70 (1996) 163-175,
Kari J. Nurmela, Markku K. Kaikkonen & Patric R. J. Östergård,and by
New constant weight codes from linear permutation groups,
IEEE Trans. Inf. Th. 43 (1997) 1623-1630,
Tuvi Etzion & Patric R. J. Östergård,The above supersedes all bounds from this last reference, and all except the bound A(24,4,7) ≥ 15656 from the Etzion-Bitan paper.
Greedy and heuristic algorithms for codes and colorings,
IEEE Trans. Inf. Th. 44 (1998) 382-388.
Tables for larger word length were given in
D.H. Smith, L.A. Hughes and S. Perkins,with improvements in
A New Table of Constant Weight Codes of Length Greater than 28,
Electronic J. Combin. 13 (2006) #A2.
R. Montemanni and D.H. Smith,and an updated on-line version can be found here, or here.
Heuristic Algorithms for Constructing Binary Constant Weight Codes,
IEEE Transactions on Information Theory 55 (2009) 4651–4656.
Using partition methods one can improve the bounds given there for d=4. A small table with lower bounds for A(n,4,5):
29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
4423 | 5148s | 6138g | 6582 | 7656s | 8976.s | 10472.s | 10948 | 12473 | 13471 | 15010 | 17119 |
41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |
19258 | 20671 | 22728 | 25564 | 28413s | 31878.s | 35673.s | 36809 | 40560 | 42920 | 46612 | 51420 |
53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
56251 | 59293 | 63973 | 69931 | 75550 | 79330 | 85728 | 93206 | 100527 | 105472 | 112457 | 121902 |
The existence of the Steiner systems S(5,6,36) and S(5,6,48) implies A(36,4,6) = 62832, A(35,4,5) = 10472, A(35,4,6) = 52360, A(34,4,5) = 8976, A(33,4,5) ≥ 7656. A(48,4,6) = 285384, A(47,4,5) = 35673, A(47,4,6) = 249711, A(46,4,5) = 31878, A(45,4,5) ≥ 28413.
The bound A(31,4,5) ≥ 6138 is found by taking a union of ASL(1,31)-orbits.
n | w | # | norm | part sizes | link |
---|---|---|---|---|---|
10 | 4 | 9 | 5574 | 30 30 30 28 26 23 22 20 1 | d |
10 | 5 | 9 | 7854 | 36 36 34 32 32 29 25 24 4 | n |
10 | 5 | 9 | 7344 | 36 36 36 24 24 24 24 24 24 | o |
10 | 5 | 9 | 7734 | 36 33 33 33 31 31 31 12 12 | p |
11 | 4 | 10 | 10948 | 35 35 35 35 35 34 31 31 31 28 | ac |
11 | 4 | 10 | 10946 | 35 35 35 35 34 33 32 32 32 27 | y |
11 | 4 | 11 | 10910 | 35 35 35 35 35 34 34 34 28 23 2 | c |
11 | 4 | 11 | 10894 | 35 35 35 35 34 33 33 33 29 27 1 | z |
11 | 4 | 11 | 10884 | 35 35 35 35 35 34 34 34 29 21 3 | d |
11 | 4 | 13 | 10782 | 35 35 35 34 34 34 34 34 34 12 3 3 3 | t |
11 | 4 | 11 | 10764 | 35 35 35 35 35 35 35 32 27 20 6 | m |
11 | 4 | 12 | 10746 | 35 35 35 35 35 35 35 32 29 16 7 1 | x |
11 | 5 | 9 | 25968 | 66 66 60 55 55 55 54 39 12 | e |
See the subdirectories part10.4, part10.5, part11.4, part11.5, part12.4, part12.5, part12.6, part13.4, part13.5, part13.6, part14.4, part14.5, part14.6, part14.7 for machine-readable descriptions of the partitions. (Improvements are welcome. Mail aeb@cwi.nl .)
Lexicographically best constant starts known:
n\w | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|
6 | 44 | ||||||
7 | 72 | ||||||
8 | 87 | 142 | |||||
9 | 127 | 185 | |||||
10 | 139 | 305 | 363 | ||||
11 | 179 | 357 | 662 | ||||
12 | 2011 | 516 | 804 | 1322 | |||
13 | 2611 | 655 | 1234 | 1663 | |||
14 | 2813 | 914 | 1694 | 2782 | 3252 | ||
15 | 3513 | 1058 | 2372 | 3991 | 5851 | ||
16 | 3715 | 1408 | 3221 | 6151 | 8361 | 11701 |
The entries here give the size of the largest constant weight code known with given n, w, and for each such code the maximal known number of pairwise disjoint such codes. This is the most greedy start known for a (n,w) partition. Of course there need not be a completion of a greedy start to a good partition.
n | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | |
b | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 5 | 7 | 7 | 8 | 9 | 10 | 13 | 14 | 16 | 20 | 25 | 31 | 31 | 31-32 | 33-34 | 35 | 37 | 37-43 | |
N | 1 | 2 | 2 | 2 | 1 | 3 | 4 | 1 | 3 | 1 | 1 | 3 | 2 | 2 | 10 | 2 | 2 | 1 | 1 | 1 | 1 | 7 | ? | ? | ? | 2 | ? |
In particular, A(36,10,6) = 37.
One needs 6, 6+5=11, 11+4=15, 15+3=18, 18+2=20, 20+1=21, 21+0=21 points to have 1,2,3,4,5,6,7 lines, respectively. This gives A(n,10,6) for n ≤ 21. The unique system of 7 lines on 21 points has group Sym(7) of order 5040.
The two systems of 8 lines on 23 points have groups of orders 48, 144. The nicer system is the dual of the partial linear space with 8 points and 23 lines obtained by taking two disjoint triples and the 21 pairs not in a triple and not disjoint from both.
The two systems of 9 lines on 24 points have groups of orders 12, 72. The nicer system is the dual of the linear space with 9 points and 24 lines obtained by taking six triples forming a 3x3 grid, and the 18 remaining edges.
The ten systems of 10 lines on 25 points have groups of orders 2, 3, 3, 4, 4, 6, 10, 12, 24, 120. The nicest system is the dual of the linear space with 10 points and 25 lines obtained by taking ten triples, three on each point, and the 15 remaining edges. If the 10 points are given as pairs ab from a 5-set, then the 10 triples are the triples abc from that 5-set, with the natural incidence. The group is Sym(5).
The two systems of 13 lines on 26 points are the duals of the two Steiner triple systems STS(13) (so have 3 lines on each point). They have groups of orders 6 and 39.
The two systems of 14 lines on 27 points have groups of orders 6, 12. Both systems are the dual of a partial linear space obtained by deleting the 2-line from the linear space with 14 points and 28 lines (1 2-line, 24 3-lines, 3 4-lines; where 4-lines and 2-line partition the point set). Cf. A.E. Brouwer, The linear spaces on 15 points, Ars Combinatoria 12 (1981) 3-35.
The unique system of 16 lines on 28 points is obtained by puncturing PG(2,5) thrice (in a noncollinear triple).
The unique system of 20 lines on 29 points is obtained by puncturing PG(2,5) twice.
The unique system of 25 lines on 30 points is the punctured PG(2,5).
The unique system of 31 lines on 31 points is the projective plane PG(2,5) of order 5.
There is no system of 32 lines on 32 points, since that would be a GD[6,1,2;32] and Schellenberg (1975) proved that none exists. (See also BCN, p. 24.)
There is no system of 33 lines on 33 points (as one sees by exhaustive search). In particular, there is no GD[6,1,3;33].
There are precisely two systems of 37 lines on 36 points. Both have a cyclic group of order 30, acting 30+6 on the points, and 30+6+1 on the blocks. (That no larger system exists follows by exhaustive search.)