Connections between Mersenne Primes and Codes 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?
 A: 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.
A: Well, there is a direct connection between composite $M_n$'s and coding theory.
Such a composite Mersenne number exists iff there is a (non-degenerate) binary irreducible cyclic code of dimension n and length a non-trivial divisor of $M_n.$ Of course, not all irreducible cyclic codes are as exciting as the $[23,11],$ the dual of the perfect binary Golay!
