Edit. After a computer search found an example for $n=8$, I've rephrased my original question as a conjecture.

This question is motivated by the existence of perfect $1$-error correcting binary codes, such as the Hamming codes. Let $d$ be the Hamming distance on $\mathbb{F}_2^n$.

Conjecture. Say that a partition $\mathbb{F}_2^n$ into subsets $S_1,\ldots, S_n$ is one-flip covering if for all $i \in \{1,\ldots, n\}$ and $u \in \mathbb{F}_2^n$ there exists a unique $v \in S_i$ such that $u_i = v_i$ and $d(u,v) \le 1$. There exist a one-flip covering partition of $\mathbb{F}_2^n$ if and only if $n$ is a power of $2$.

Taking the elements $v$ of $S_i$ with $v_i = 0$ and deleting the $i$th position from each gives a covering code of radius $1$ and length $n-1$. Hence $|S_i|/2 \ge 2^{n-1}/n$ for each $i$. Since $|S_i| \le 2^n/n$, equality holds. This proves the `only if' part of the conjecture.

Such partitions exist when $n=1$, $2$, $4$ and $8$. For example, the unique partition for $n=2$ has parts $\{00, 11\}$ and $\{01,10\}$. If $C = \{0000, 0111, 1000, 1111 \}$ then one of the $40$ possible choices for $n=4$ is

$$\bigl\{ C, C^{(1,2)}+0001, C^{(1,3)}+0100, C^{(1,4)}+0010 \bigr\} $$

where the superscripts indicate the position permutation to apply to each element of $C$. Let $D \subseteq \mathbb{F}_2^8$ be the set of $32$ codewords obtained from a Hamming code of length $7$ by prepending either $0$ or $1$ to each codeword. A computer search found a one-flip covering partition of $\mathbb{F}_2^8$ in which each part is equivalent to $D$ by permuting positions and flipping a bit. (I can supply details and code to verify this on request.)

Further motivation. Using such a partition, one can perform this trick. Person A puts $n$ coins in a row, and indicates one of them to Person B. Person B may then flip any other coin. Person C then enters the room and, looking only at the coins, picks up Person A's chosen coin.

If Person B may also flip the chosen coin, there are simpler ways to work the trick. Suppose that $n = 2^r$. Encode a head in position $i \in \{1,\ldots, n\}$ by the binary representation of $i$, thought of as an element of $\mathbb{F}_2^r$. (So position $n$ is encoded as $(0,\ldots,0) \in \mathbb{F}_2^r$.) Then person B can always flip a coin so that the sum in $\mathbb{F}_2^r$ of the positions of heads is the position of the chosen coin.

  • $\begingroup$ I don't understand what the u_i or v_i are in your question. $\endgroup$ – Josh Jul 1 '16 at 14:58
  • $\begingroup$ $u_i$ is the $i$th position of $u \in \mathbb{F}_2^n$, and similarly for $v_i$. $\endgroup$ – Mark Wildon Jul 1 '16 at 15:45
  • $\begingroup$ If $n=2$ in your example, how come $C$ has length 4? Confused. $\endgroup$ – kodlu Jul 10 '16 at 20:38
  • $\begingroup$ There are two examples. In the first $n=2$, and the only partition has parts $\{00,11\}$ and $\{01,10\}$. In the second $n=4$ and the partition has four parts, each equivalent (by position permutations and flipping bits) to the code $C$. $\endgroup$ – Mark Wildon Jul 10 '16 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.