On Nov 28, 2012, at 8:55 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
k 2 3 4 5 6 M(7,k) 10 14* 20* 24* 29* M(7,k)/k 5 4.67* 5* 4.8* 4.83*
The numbers marked * are lower bounds. As you can see, the results up to n=7 are inconclusive: only ties for k>2 have been found. The best hope looks like n=7, k=4.
Hey, my trivial Mathematica program can do that: for n=7, there is a 21-element cyclic capped union code with k=4, consisting of the circular shifts of {0000001, 0001011, 0001101}. No reason to think that forcing cyclic symmetry is optimal, but in this case it's good enough.
So now we have at least one case where the more-general capped union code out-performs the unique union code.
--Michael
Thanks for settling that question. I raised the upper bound for n=7, k=3 from 14 to 15, giving yet another tie. Your 21-element code achieves another milestone of sorts. The "rate" of these rat-codes is log_2( N(n,k)/k ) / n bits, where N(n,k) is the number of codewords. This reaches 1/3 already for the n=3 code, and in fact Grossman's product construction has this as the asymptotic rate. Your n=7 code gives the first improvement: 0.34176. The best rate so far is given by your 46 element n=10, k=4 code: 0.3523. Have you noticed that the transposes of your cyclic codes are always equal weight and equidistant? Your latest has 7 words of length 21, all of weight 7 and equal distance 10 to all the other words. This led me to try out "random" codes with this property and check them for the union property. While this works for n=8, k=2 (and other small cases), it fails for n=10, k=2 (a small fraction of the unions are generated from more than k words). Somehow your cyclic codes are capturing something else that's important. -Veit