presented by Wikipedia):
- For each 15-bit string a denote a1...a15 it's bits.
- Choose A such that all the bits except a1, a2, a4 and a8 can be chosen freely and bits a1,a2,a4,a8 are bound to the following equations:
a1=a3+a5+a7+a9+a11+a13+a15
a2=a3+a6+a7+a10+a11+a14+a15
a4=a5+a6+a7+a12+a13+a14+a15
a8=a9+a10+a11+a12+a13+a14+a15
Visual matrix representation:
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15
a1 X X X X X X X
a2 X X X X X X X
a4 X X X X X X X
a8 X X X X X X X
- Approaches of type II are what Carbon1nTheRough had in mind. Choose a minimum number of seeds (11010001000000 in his case, which is actual easy to remember 1 if position is a power of 2 and 0 otherwise) and choose addition between elements in A and multiplication between one element in A and any other element as generating mechanisms i.e. generating a cyclic code as an ideal in a certain ring. As I said, choosing rotation/cyclic shift as a generating mechanism is not enough since rotation/cyclic shift is only multiplication by a particular element - polynomial p(X)=X or 0100..00. So you basically need at least an additive group (e.g. additive group generated by 4 strings with only one bit as 1, on positions 1,2,4 and 8) as seeds and then allow for full-multiplication (modulo 2) to grow/generate the set A. Rotation/cyclic shift is not sufficient.
I think the different viewpoints come from different interpretations for the n=3 case. n=3=2^2-1 so 2 balls are in the Hamming partition. There are also 2-partitions of the same space which do not follow construction by Hamming distance one of which is given as example.
The following are different 2-partitions with a "center (set of elements graviting the center)" notation for Hamming :
- Linear/Hamming: 000 (100, 010, 001) and 111 (011, 101, 110).
- Cyclic partition: (110, 101, 011, 000) and mirror (001, 010, 110, 111).
All Hamming codes are notorios to being closed under addition (as any linear code) and although not all Hamming code presentations are cyclic themselves, they are equivalent to a Hamming code presentation that is a cyclic code.
In my opinion, the cyclic view is much harder to grasp for n>3. Although such a cyclic partition does exist (as Hamming codes are equivalent to a cyclic code), it's not that simple as choosing a minimal seed and reconstructing the rest with rotation/mirroring/addition as it looks like for n=3.
For n=7, one can indeed construct such a (cyclic) set easily (roughly following Carbon1nTheRough ideas) using mirroring and rotation. For n=15 and above, I don't see an easy construction (for n=15, a partition has 2048 elements so less than log(2048) would sound as a nice seed set).
I personally like a star/planets analogy view on Hamming partitions which I will use in the following. Assume a finite universe of size 2^n in which all points are either stars or planets. All centers in the Hamming partition are stars and all points not in A are planets which revolve around exactly one star.
Recall some of the previous notes on how centers in A relate to one another:
1) (Local sparsity) Two centers are at a distance of at least 2 from one another: The 2 centers cannot be at distance 1 from one another i.e. one "graviting" around another one since the radius-1 balls around each other would collide. Moreover, since the balls don't touch, two centers cannot be at distance 2 from one another. In that case, the balls would share at least a string (two strings in fact) that can be found in the middle of the two-step flipping transition which gets us from one center to another (definition of distance 2).
2) (Global density) Two centers cannot be too much apart either or more precisely, for each center there must be at least one center at distance 3 from it (for n>=2). Just imagine center A - a string B gravitating around A (at distance 1) and a string C obtained by flipping another bit from B (not the one that differentiates between A and B). Distance between A and C is 2 so C is not a center. However, C must gravitate around a center since this a partition after all.
3) The Hamming distance is also a metric on the n-bit space - the triangle inequality d(A,C) <= d(A,B) + d(B,C) holds for the Hamming distance. It's easy to see that equality is reached if and only if the set of positions in which A and B are different is disjoint from the set of positions in which B and C are different.
So, starting from s=null-string which has 0 1-bits (call it our Sun), we find all strings with 1 1-bit graviting around this center (call them planets) and the all 2 1-bit strings (planets in another solar system) graviting around other centers (stars). Since these neighbor stars cannot have one 1-bit, then reaching them from one of the 2 1-bit planets means flipping one of the other bits from them - a bit which is 0 for planets. Hence these neighboring stars have 3 1-bits = are at distance 3 from our sun (seed).
However not all 3-bit strings can be stars since for example 11100..0 and 01110..0 are at distance 2 from one another.
Choosing a set of stars from these 3-bit strings is certainly not unique, since rotation/shifting for example can lead to alternative partitions. There are nC3 combinations of 3 1-bit strings.
First, let's see how many we need. For n=7, m=3 so we need 2^(7-3)=16 stars in A.
Taking s=0000000 and non-s=1111111 in A, 14 pairs remain. nC3=7C3=7*6*5/2*3=35 points at distance 3 from s. Similarly, only 35 points have 4 1-bits and thus lie at distance 3 from non-s and therefore distance n-3=4 from s. It is then clear that the only stars other than s and non-s must lie at either distance 3 or 4 from s, otherwise they would be too close from s or non-s. The symmetry involved in the Hamming hypercube shows that there are as many stars at distance 3 from s as stars at distance 4 from non-s so 14/2=7=n stars are in each category. Moreover, choosing 7 stars at distance 3 from s (which lie at least at distance 3 from each other) forces us to consider their mirrors as the other set of stars.
Note that if you get lucky and choose a stars whose rotations are all at distance at least 3 from one another, your job is finished since there are 7 rotations possible. Since these are stars with 3 1-bit, achieving a distance of at least 3 means that when rotating, no more than 1 pair of these 3 1-bits can overlap (2 pairs of 1-bits overlapping determine a Hamming distance of 2 - remaining 1-bits can be flipped to go from one star to another - as seen in the following counter example: 1110000 and 01110000).
A beautiful (easier to prove) seed for the 3-bit stars is the one involved in all strategies in the other posts - one in which the 1-bits are on positions that are powers of 2. For n=3 this means 1101000.
So, for n=3 a simple set A can be found by taking s=0000000, p=1101000, all the strings that can be obtained from p by shifting (1+1+6=8 so far) and all their mirror strings (totaling 16 so far).
For n=15 the problem is not that simple. Consider Carbon1nTheRough's partial solution. He chooses s=000000000000000, p=110100010000000 and their mirrors and cyclic shifts (because he does not consider a predetermined fixed position i.e. a leader). Problem is that d(s,p)=4 and no shifting modifies the number of 1's (1-bits) in a string. So there is no star at distance 3 from s which contradicts the Global density property of Hamming partitions. Therefore it is at best incomplete/partial in achieving a Hamming code/Hamming partition, no matter how you look at it.
For n=15, I do not see such an easy-to-explain construction using mirroring/shifting and maybe addition (n=15=2^4-1, m=4, 2^(n-m)=2^11=2048 stars needed). From an algebraic point of view, a binary linear cyclic code can be generated by the polynomial g(x)=1+x+x^4.
Completely classifying/constructing 1-error correcting codes of length n is not so simple as it may seem. If one defines two codes to be equivalent if one can turn one code into the other by permuting the coordinates and adding a constant vector, then characterization of equivalence clases is non-trivial for n>=15. For example there are 5983 non-equivalent perfect codes of length 15 (while there is a unique perfect code for n=3, n=7). Several recent results can be found here and here . n=31 is still an open challenge I think.
Thanks, araver, I was confused by the solution comments made by
Carbon1nTheRough, bushindo, and Kornrade. They obviously understood
something which I missed somewhere along the line. I very much appreciate
your excellent explanation. I now understand the other's comments on
solution. I also wish to thank Kornrade for this beautiful problem.
But without your lengthy explanation, araver, I would be spending at
least several more hours pondering this (possibly without success).
