I also haven't found any improvements to the 46/4 code. But here are a couple of curiosities. First, I went the opposite direction with regard to symmetry. Since the optimal codes have sizes that grow exponentially with n, my speculation was that eventually they will outgrow the cyclic group. So I looked at low order transitive subgroups of S_n, whose orders must be multiples of n. For n=10 there is a subgroup of order 60 isomorphic to the icosahedral group (the 10 rats correspond to the axes of 3-fold symmetry). But the best I got for that group was 75/7. So n=10 may still be too small. For fun I looked at n=13 and found a remarkable 53/2 code. One of the code words is the zero codeword and the others are orbits under the dihedral group (order 26) of the codewords {0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1} {0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1} So this counts as an example of a slightly larger transitive subgroup. It turns out both codewords above are constant autocorrelation sequences. This code is the current record holder for the "rate": (1/13) log_2(53/2) = 0.363686 Michael's 46/4 code has rate 0.352356. The best upper bound I have for the rate is 1/2. (Note: my units for rate is the bit-per-rat, or BPR, rather than the NPR.) The 52/2 code you get by taking away the zero codeword might be the basis of a card trick where the magician amazingly determines the identities of two cards. I'm stuck on how the or/union operation gets implemented in an interesting way. Finally, for large optimal codes we expect the frequencies of the 2^n possible outcomes of their pairwise unions to be as uniform as possible (so as to maximize the entropy). But that means the frequency of 1's in the first (or any) position should be about 1-1/sqrt(2) = .293 in order for the pairwise-or distribution in that position to have equal probability of 0 and 1. This suggests the heuristic of tuning the weight of codewords near .293n in searches. -Veit On Dec 15, 2012, at 11:17 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
In case anyone else is still interested in rats and wine bottles:
Last weekend I C++ified my search for "capped union codes" with symmetry. Top-line result: I haven't found anything that beats the 46/4 code that I posted here on 11/23 (and gets down to discarding 88 of the 1000 bottles of wine). I did find a unique-union code of size 22, beating Thomas's 21, but this only brings a 96-bottle solution down to 92 bottles.
If we restrict our attention, as Thomas proposed, to codes that have full 10-fold cyclic symmetry, then with a cap of k=2/3/4/5/6/7/8/9 the maximal size of a capped union code is 21/31/46/56/66/76/86/96. Hooray for exhaustive search. (As before, a cap of k means that for any word w that is a pairwise union of two (not necessarily distinct) words in the code, there are at most k codewords that can participate in such a pairwise union to form w.) For rats and bottles, the 46/4 codes are far better than anything else.
We could loosen our symmetry requirement, though, and allow just 5-fold symmetry instead. (Just to be clear, that means that if e.g. the word 111100000 is in our code, then so are the four other words you get by rotating it 2 bits at a time: 0011110000, 0000111100, 0000001111, 1100000011).
Unfortunately, this makes the search space quite a bit larger. With 10-fold symmetry and a cap of 2/3/4, the number of locally maximal codes is 120 / 779 / 12489. If we only demand 5-fold symmetry, the corresponding sizes are 20215, ~1.7 million, ~220 million. These size estimates come from a clever observation I learned from Knuth at some point: the number of leaves in a tree is the average value of the "product of number of children" statistic for a random path down through the tree, where "random" means "start at the root and from each node pick uniformly at random from its children until you reach a leaf."
I ran the exhaustive search for 5-fold cap=2 and didn't break the code size record of 21 already attained by 10-fold symmetric codes. For cap=3, though, with 5-fold symmetry you can inch up to a code of size 32, instead of 31! One of many such codes: the six words {0000000101, 0000001111, 0000100011, 0001010011, 0001100110, 0010001001} plus the symmetry-required four rotations of each, along with two singletons {0000000000} and {1010101010}.
For cap=4 the search is still running, but it's nearly done and has not exceeded the 46/4 record. It has produced fully 494 codes of that size, though. I've tried higher caps and the search has become much too long to wait for it to finish, but for the bits of the space I have explored, not much to report: I haven't beaten the 10-fold rotation record in any case other than cap=3.
Finally, we can go wholer hog and ask about just 2-fold rotational symmetry! For cap=2 the search space is around 36 billion and for cap=4 it seems to be size 10^18, so, um, not going to explore the whole thing. (That would be 80K years if we could explore 1 code per microsecond!) However, I have found some 22/2 codes this way! For example: {1, 32, 6, 192, 24, 768, 75, 354, 108, 387, 149, 676, 178, 581, 269, 424, 308, 649, 337, 554, 531, 624}. I've written codewords as decimal integers in [0,1023] this time, to save space; I'm sure you can all translate to binary yourselves. These 22/2 codes aren't particularly rare; I've seen hundreds of them.
There! Aren't you glad you asked?
--Michael _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun