Wow, super result! The spontaneous symmetry is fascinating, maybe there is something to that after all. Would it be easy for you to modify your wax-and-wane code to enforce a symmetry constraint? Even a simple one, like adding and subtracting cyclic-rotation-by-5 pairs of points? Would be interesting to see how the codes that that produces differ from those produced by the unconstrained search. (Hmm, I suppose during the wane step you'd need to figure out how to balance the removal of a single-point symmetry class like {1000010000} versus a two-point class {1000000000, 0000010000}.) --Michael On Thu, Jan 3, 2013 at 2:54 PM, Veit Elser <ve10@cornell.edu> wrote:
After three hours wax-&-wane found the following 50/4 code:
{225, 593, 92, 198, 394, 46, 553, 291, 816, 674, 538, 320, 780, 114, \ 53, 147, 75, 660, 897, 281, 141, 104, 278, 69, 208, 712, 420, 612, \ 578, 64, 160, 24, 6, 513, 400, 261, 48, 136, 516, 3, 640, 36, 296, 9, \ 770, 18, 528, 130, 33, 12}
I used d=6 for a slightly deeper, less greedy search.
This code has the symmetry of the 8-element quaternion group:
i = (2) (4) (1 6 9 3) (5 8 7 10) j = (2) (4) (1 7 9 5) (3 10 6 8) k = (2) (4) (1 10 9 8) (3 5 6 7)
(These are the permutations on the codewords as bit strings.)
I am now intrigued to see what other symmetries might turn up -- recall that wax-&-wane makes no symmetry restrictions whatsoever.
So now we can evenly divide up the 1000 bottles into 50 sets of 20 from which at most 80 must be rejected.
-Veit
On Jan 2, 2013, at 9:19 PM, Veit Elser <ve10@cornell.edu> wrote:
Thanks for pointing out the rounding issue; it's gratifying to know I helped in a small way to salvage another bottle of wine!
I spent a couple of hours turning my Mma program into C code, in case anyone wants to play with it. It generates 49/4 codes at a rate of about 1 per minute. Here's a brief description of the algorithm:
There are two operations, wax and wane, in each cycle. As the names suggest, the code grows in size during wax and shrinks during wane.
Wax is the simpler of the two: unused codewords are added as long as the "cap" on the code (4 in the case of 49/4) is not exceeded. This introduces randomness, because the algorithm tries the unused codewords in a random (not lexicographic) order.
During wane, codewords are deleted that have an overabundant representation in the unions that are at their capped values. The rationale is that growth of the code is more likely when fewer unions are capped, and if the rule is to always delete the same number d of codewords, one should preferentially delete those that "un-cap" the greatest number of capped unions. So the algorithm assigns a cost to each codeword equal to the number of capped unions it contributes to and then deletes the d codewords having the highest cost.
Starting from the empty code the algorithm performs many wax and wane cycles and outputs the code whenever an increased size is found. During wax there is no limit to the growth of the code, while the size always shrinks by d during wane. I get good results for the 49/4 code when d=5.
-Veit
On Jan 2, 2013, at 7:46 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Oh hey, my Z2xZ2 symmetry search just turned up a 49/4 also:
5,160,640,20,6,192,384,12,10,320,33,528,34,65,272,520,40,257,80,514,51,609,816,537,60,897,240,519,66,264,77,418,712,278,90,834,360,267,102,195,408,780,132,145,548,169,293,596,658
(Note the presence of 132 = 0010000100, a symmetry orbit of size 1, allowing the code to be of odd size.)
Still eager to see Veit's approach, though; I remain afraid that this symmetry thing is ultimately a distraction.
--Michael
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.