Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a_0,...,a_{2^{24}-1}\in \{0,1\}^{24}$ be a sequence such that $a_k$ is the binary representation of $k$. i.e. $$a_0=(0,...,0,0,0,0)$$ $$a_1=(0,...,0,0,0,1)$$ $$a_2=(0,...,0,0,1,0)$$ $$a_3=(0,...,0,0,1,1)$$ $$.$$ $$.$$

Let $b_0,...,b_{2^{12}-1}$ be a subsequence of $a_0,...,a_{2^{24}-1}$ such that $$b_0=a_0$$ and for $n\geq 1$, $$b_n=a_k$$ where $k$ is the least number such that $a_k$ differs in at least 8 components from each of $b_0,...,b_{n-1}$.

why is the sequence $b_k$ well-defined?

Let $L$ be the set of all $b_k$ that have exactly 8 nonzero componenets. Let

$$X=\{1,2,...,24\}$$

Clearly each $b\in L$ is in one-one correspondence with an 8-element subset $S_b\subseteq X$. Let $$\mathcal{B}=\{S_b|b\in L\}$$

I'm trying to show that $(X,\mathcal{B})$ is an $S(5,8,24)$ steiner system.

  1. $|X|=24$.
  2. $(\forall B\in\mathcal{B})(|B|=8)$.
  3. $(\forall A\in X^{\{5\}})(\exists! B\in\mathcal{B})(A\subseteq B)$.

in 3 why does $B$ exist? (it's easy to show that it's unique if it exists).

Let $$M_{24}=Aut(X,\mathcal{B})$$ why does $M_{24}$ act 5-transitively on $X$?

share|improve this question
1  
$b_n$ is well-defined, because at each step $k$ is well defined. We need to show that there is at least 1 integer that is not excluded. Each $a_i$ excludes at most $2^7$ possible values of $k$. There are at most $2^{12}-1 \times 2^7 < 2^{24}$ values that are excluded (worst case is when the sets are disjoint), such a $k$ always exist. –  Calvin Lin Feb 5 '13 at 0:27
    
Related question: math.stackexchange.com/questions/293216/… –  Gerry Myerson Feb 5 '13 at 0:57
1  
@CalvinLin I don't understand your argument. Why does each $a_i$ exclude at most $2^7$ values? The bound $(2^{12} - 1) \cdot 2^7$ is suspicious because it seems to suggest that the we will reach the last codeword $b_{4095}$ with room to spare, whereas, in fact, $b_{4095}$ is the all-ones codeword. –  Ted Feb 5 '13 at 4:51
add comment

1 Answer

up vote 1 down vote accepted

I'll answer all your questions except the 5-transitivity of $M_{24}$. That would require constructing symmetries of $(X, \mathcal{B})$, which is very hard to do using this construction (there are no "obvious" symmetries in this construction to get us started).

Let $V$ be the set of subsets of $X$, and let $C$ be the subset of $V$ corresponding to the $b$'s. Then $V$ is a 24-dimensional vector space over $\mathbb{F}_2$ (the sum of two subsets, $A+B$, is the set of elements of $X$ that lie in exactly one of $A$ or $B$).

Claim 1: $C$ is a subspace of $V$.

This claim is the most difficult part of the proof, and we'll come back to it at the end.

Note that $|V| = 2^{24}$ and $|C| = 2^{12}$, so that the quotient group $V/C$ also contains $2^{12}$ elements.

Claim 2: $C$ does not contain any nonempty subsets of $X$ of size less than 8.

Proof: By construction, the empty set lies in $C$ (it corresponds $b_0 = 0$) and any other element of $C$ differs from the empty set in at least 8 positions.

Claim 3: Suppose $S$ and $T$ are subsets of $X$ having size $\le 4$. If $S+T \in C$, then $|S|=|T|=4$, and $S$ and $T$ are disjoint.

(Proof: This follows easily from Claim 2.)

Choose $x \in X$. Let $\mathcal{R}$ be the set of all subsets of $X$ of size $\le 3$ together with the set of all subsets of $X$ of size 4 containing $x$. (Note that $\mathcal{R}$ depends on $x$, but we will suppress the dependence on $x$ in the notation.)

Claim 4: The set $\mathcal{R}$ is a complete set of coset representatives for $C$ in $V$. In other words, for every subset $S$ of $X$, there is a unique $T \in \mathcal{R}$ such that $S+T \in C$.

Proof: By Claim 3, no two elements of $\mathcal{R}$ lie in the same coset of $C$ in $V$. But the number of elements of $\mathcal{R}$ is $$\binom{24}{0} + \binom{24}{1} + \binom{24}{2} + \binom{24}{3} + \binom{23}{3}$$ which, miraculously, equals $2^{12}$, the number of cosets of $C$ in $V$. Therefore, every coset contains a unique element of $\mathcal{R}$.

Claim 5: The set of elements of size 8 in $C$ form a $(5,8,24)$ Steiner system.

Let $S$ be a subset of $X$ of size 5. Choose $x \in S$, and construct $\mathcal{R}$ as above. By claim 4, there exists a unique $T \in \mathcal{R}$ such that $S+T \in C$. This $T$ must have size 3, because size 0,1, or 2 would clearly be too small (by claim 2), and size 4 does not work because such a set must contain $x$, which is also in $S$, so again the sum would have size $\le 7$. Also, $S$ and $T$ are disjoint, or else $S+T$ would again be too small. Therefore $S+T$ is a set of size 8 in $C$ containing $S$. The uniqueness of $T$ implies that this 8-element set in $C$ is unique.

Reference for all of the above.

Okay, now back to claim 1. This will only be a sketch. For details, look up the theory of impartial combinatorial games.

We consider the following two-player game. The starting position is an integer $n$, with $0 \le n \le 2^{24}-1$. Players alternate turns. A legal move is to replace an integer $n$ with a smaller nonnegative integer $m$ such that $m$ and $n$ differ by no more than 7 bits. The player that moves to 0 wins. (Reference: This is the game "Turning Turtles" in Winning Ways for your Mathematical Plays, by Berlekamp, Conway, and Guy, Volume 3 (2nd ed.), Chapter 14. In the 1st edition, it's in Volume 2.)

I claim that the values $b_i$ which make up $C$ are precisely the starting integers for which the second player can win. Proof: by induction. If the starting position is 0, then the second player has won by definition. If the starting position $n$ is in between 2 consecutive $b_i$ and $b_{i+1}$, then $n$ and $b_i$ differ by at most 7 bits, for if they differed by 8 or more, this would contradict the construction of $b_{i+1}$. Therefore, it is legal for the first player to move from $n$ to $b_i$, and now the first player becomes the second player in the new game $b_i$ which (by the inductive hypothesis) is a second player win. Therefore the first player wins $n$. Finally, if $n = b_i$, then the first player cannot move to any smaller $b_j$ because they all differ by 8 or more bits by construction. Therefore any move by the first player leads to a position between 2 consecutive $b$'s, which the first player (who was the second player in the original game) can win by the inductive hypothesis.

In the language of impartial combinatorial games, the numbers $b_i$ are precisely the $P$-positions of this game.

Now the theory of impartial combinatorial games tells us that there exist integers $x_0, x_1, \ldots, x_{23}$ such that if $n = c_i 2^i$ is the binary expansion of $n$, then the nim sum $\oplus c_i x_i = 0$ iff $n$ is a second player win. The nim sum is exactly the same operation as the symmetric difference of subsets in our original space $V$. So the elements of $C$ are precisely those for which $\oplus c_i x_i = 0$, and this latter description of $C$ is clearly linear. Therefore, Claim 1 holds.

share|improve this answer
    
thanks. There may be a simpler way to prove $b_k$ is well-defined. Or maybe I can omit the uppr bound $2^{12}-1$ . –  user59671 Feb 5 '13 at 13:42
1  
@CutieKrait I think the best way is to say: calculate $b_0, b_1, b_2, \ldots$ until no more values are possible (i.e. there are no more values < $2^{24}$ that differ by 8 or more bits from previous values). Then you can calculate the dimension of $C$ using game theory: it is the number of $x_0, x_1, \ldots, x_{23}$ which are not powers of 2. In this case, this number is 12. –  Ted Feb 5 '13 at 17:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.