Re: [math-fun] poisoned wine bottles
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
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.
Here's a symmetry update. Among the codes found by wax-&-wane for 48-50/4 only three groups have shown up: 1) The trivial group, G1. 2) The group of order 2, G2, generated by (1 3) (2 4) (5 7) (6 8) (9) (10) 3) The quaternion group of order 8, G8, generated by (1 2 3 4) (5 6 7 8) (9) (10) (1 6 3 8) (5 4 7 2) (9) (10) All three 50/4 codes found so far have symmetry G8. The four 49/4 codes I looked at (determining their symmetry is more work than generating them) all have symmetry G2. And three out of the four 48/4 codes I looked at all had no symmetry (G1); the fourth had symmetry G2. All of my codes are maximal, in the sense that additional codewords can't be added. This local optimality may account for some of the symmetry. On the other hand, Michael's Z2xZ2 group might be excessive, since there are 48/4 and 49/4 codes with symmetry groups that are proper subgroups of his group. Michael: could your program complete an exhaustive search for group G8? If it finds something larger than 50/4, maybe it will have an even larger symmetry group. -Veit On Jan 3, 2013, at 11:01 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
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
Michael: could your program complete an exhaustive search for group G8? If it finds something larger than 50/4, maybe it will have an even larger symmetry group.
Great suggestion! Looks like the 50s are as good as that symmetry group gets. I just ran the exhaustive search for cap=4 codes invariant under your representation of the Quaternion units. There are 1,960,139 locally maximal codes, of which 144 are 50/4, and that's the largest that exists. (That 144 isn't reduced by symmetry at all, so probably there are fewer than that up to isomorphism; maybe I'll try to reduce this set to canonical forms later. Hmm, I'll need to figure out the normalizer of that quaternion representation...) For reference, that search took around 2 hours of compute time. --Michael -- Forewarned is worth an octopus in the bush.
Wow -- that was fast! wax & wane has found several more 50/4's, all with the same (quaternion unit) symmetry group. I'll try a deeper search to see if something else turns up. -Veit On Jan 6, 2013, at 3:13 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Great suggestion! Looks like the 50s are as good as that symmetry group gets.
I just ran the exhaustive search for cap=4 codes invariant under your representation of the Quaternion units. There are 1,960,139 locally maximal codes, of which 144 are 50/4, and that's the largest that exists. (That 144 isn't reduced by symmetry at all, so probably there are fewer than that up to isomorphism; maybe I'll try to reduce this set to canonical forms later. Hmm, I'll need to figure out the normalizer of that quaternion representation...)
For reference, that search took around 2 hours of compute time.
--Michael
participants (2)
-
Michael Kleber -
Veit Elser