Happy 2012.25 ! While I can't offer you any more bottles of wine, here is a 49/4 = 12.25 code that beats Michael's 48/4: 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 No symmetry was used in its construction, only a very simple heuristic. I'm calling the algorithm wax & wane. Details next year! -Veit On Dec 25, 2012, at 2:57 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Merry Christmas! My present to you: four more bottles of wine. Last night my program turned up a 10-bit cap=4 union code with 48 codewords. The 1000 bottles of wine can therefore be assorted into 48 bins with at most 21 bottles in each bin, and we will need to throw away at most 84 bottles.
The search through codes with 5-fold rotation symmetry did indeed finish as expected with lots of 46/4 codes but nothing better, and the search space for codes with 2-fold rotation symmetry is too large. In between (in size, not in the subgroup lattice) there's the space of codes with Z2 x Z2 symmetry: fixed under rotation by five positions and under reversing the whole string. That is, if the code contains word [abcde fghij], then it also contains [fghij abcde], [jihgf edcba], and [edcba jihgf]. (As usual, some of these might coincide, so the class might have only 1 or 2 distinct words instead of 4.)
That search has turned up both a 47/4 code and a 48/4 code. The 48/4 consists of ten 4-word symmetry classes and four 2-word classes: 4-word: 0000000101, 0000000110, 0000001001, 0000100010, 0000101000, 0000111001, 0001011100, 0001100110, 0010110010, 0100101010 2-word: 0010001110, 0010010001, 0010010101, 0000100001
The fact that a code having this 4-fold symmetry, which singles out one pair of bits (c and h above), beats the best codes with the much more uniform 5-fold rotational symmetry, gives me the impression that symmetry is useful more because it cuts down the search space than because large codes are likely to be highly symmetric.
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun