# Background

I've just learned a bit about linear codes. Hamming codes 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 totwocorrupted 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.