Background
==========


I've just learned a bit about linear codes. [Hamming codes](http://en.wikipedia.org/wiki/Hamming_code) have the property that up to one bit in a block can be corrupted, and we still communicate the message correctly. This is done by making all the non-zero vectors in $\newcommand\ZZ{\mathbb Z}(\ZZ/2)^k$ columns in a $k\times (2^k-1)$ matrix $H$. Valid transmissions are vectors $t$ of length $2^k-1$ so that $Ht=0$. If you receive an invalid transmission $\tilde t$, then look for the column of $H$ which is equal to $H\tilde t$, flip the corresponding bit of $\tilde t$, and you have the unique valid transmission which differs from $\tilde t$ in one bit.


Note: the number of data bits that are transmitted is the dimension of the kernel of $H$, $2^k-1-k$. That is, for each block of $2^k-1$ bits sent, $k$ of them are used for purposes of correcting errors, so they can't be used for transmitting information.




---



> 
> **General question:** is there a similarly elegant scheme for correcting up to **two** corrupted bits in a block?
> 
> 
> 


Here's what I've done so far. I'd like to find an $m\times n$ matrix $H$ over $\ZZ/2$ and declare that valid transmissions are vectors $t$ of length $n$ so that $Ht=0$. Moreover, I'd like to have the property that any non-zero vector of length $m$ (think of this as $H\tilde t$ for some invalid transmission $\tilde t$) is *uniquely* expressible as either one of the columns of $H$, or the sum of two of the columns of $H$. Uniqueness is important because that's what tells me which bit (or which two bits) of $\tilde t$ needs to be corrected.


This is clearly only possible if $n + \binom{n}{2} = \binom{n+1}{2} = 2^m -1$, so I set out looking for triangle numbers that are one less than a power of two. $1$ and $3$ have $n=m$ (so $\dim\ker H=0$, so no data can be sent), so the first one of interest is $15 = \binom{5+1}{2} = 2^4-1$. Here we can take
$$H = \pmatrix{1&0&0&0&1\\ 0&1&0&0&1\\ 0&0&1&0&1\\ 0&0&0&1&1},$$
which works, but is extremely boring, since the corresponding code sends $5-4=1$ actual bits of data for every $5$ bits transmitted by simply sending each bit five times in a row and decoding by majority vote in each block of five.


The *only*† other case is $4095 = \binom{90+1}{2} = 2^{12}-1$, which is much more interesting. If such an $H$ exists, we get a scheme for transmitting $90-12=78$ bits of data in blocks of size $90$, which is resistant to corruption of any two bits in a block. My specific question is whether such an $H$ does in fact exist. In case it's catchier, we can interpret the columns of $H$ as $12$-bit integers to get the following question:



> 
> **Specific question:** Does there exist a set $S\subseteq \{1,2,3\dots, 4095\}$ of size $90$ so that $S\cup (S\text{ xor }S) = \{1,2,3\dots, 4095\}$?
> 
> 
> 


†Bonus question: why is this the only other case? I've checked that $2^m-1$ isn't a triangle number for $12<m\le 6000$, but I don't see a reason there couldn't be any more.



Is there a code which corrects corruption of any two bits in a block?
Here is the Tompkins proof, from page 86 of From Error-Correcting Codes Through Sphere Packings to Simple Groups, Volume 21 By Thomas M. Thompson
<http://books.google.com/books?isbn=0883850370>


Assume such a code exists, w/o loss of generality it contains 0.
Each 90-tuple with exactly three 1s must be in a Hamming sphere of radius 2
centered on a codeword which has exactly five 1s, three of which are in the
same coordinates as those of the 90-tuple. Consider in particular the set
of eighty-eight 90-tuples with 1's in the first two coordinates and one 1
elsewhere. Each member of this set must be within two units of a unique
codeword. Each such codeword has 1s in the first two positions and three 1s
elsewhere. Two such codewords cannot have 1s in the same coordinate positions
other than the first two, otherwise some 90-tuple in the above set would be
within two units of two codewords. This means the eighty-eight coordinate
positions other than the first two must be divided into equinumerous
disjoint sets of three. Since three does not divide eighty-eight,
this is impossible.


