I recently watched the video for the talk The Biggest Known Prime Number (slides located here) by Keith Conrad, which is on Mersenne primes $M_n = 2^n-1$. It is well-known that such numbers can be prime only if $n$ is prime, but that this condition is not sufficient for primality of $M_n$. The smallest counterexample is $M_{11} = 2^{11} -1 = 23\cdot 87$. Conrad's talk includes the remark:
That $2^{11}−1$ has factor 23 is related to an important construction in coding theory called the perfect binary Golay code(a special subset of 23-dimensional space over integers mod 2)
My questions are:
What is the relation precisely?
Are there further relations between divisors of "Mersenne composites" and coding-theoretic constructions?
The connection is much simpler than I was imagining. It is well-known that the binary Golay code is perfect. A code $\mathcal{C}\subseteq \mathbb{F}_2^n$ is called perfect if Hamming balls of radius $(d-1)/2$ centered at each codeword $c\in\mathcal{C}$ partition $\mathbb{F}_2^n$.
Note that the size of a Hamming ball of radius $r$ within $\mathbb{F}_2^n$ is $1 + \binom{n}{1}+\dots+\binom{n}{r}$. For this to partition the whole space, this quantity must be equal to exactly $|\mathbb{F}_2^n|/|\mathcal{C}| = 2^{n-k}$, where $k$ is the rank of the code. So we get the condition:
$$1 + \binom{n}{1}+\dots + \binom{n}{r} = 2^{n-k}\iff \binom{n}{1}+\dots + \binom{n}{r} = 2^{n-k}-1$$
As $n$ obviously divides $\sum_{i = 1}^r\binom{n}{i}$, a necessary condition for this equality (and therefore for $\mathcal{C}$ to be perfect) is for $n$ to divide $2^{n-k}-1$, hence $2^{11}-1$ being composite (and in particular being divisible by 23) is necessary for there to exist a rank 12 perfect code within $\mathbb{F}_2^{23}$.
There may be a deeper connection still, as perfect codes are much rarer than the above condition might imply. I'll probably leave this question open a few more days in case someone knows a deeper connection.