# Binary codes with length and distance a power of 2

Let $A_2(n,d)$ denote the maximum number of words in a binary code (not necessarily linear) with length $n$ and distance $d$. The value of this function is not known in general, though there are tables for small values of $n$ and $d$, e.g. http://www.win.tue.nl/~aeb/codes/binary-1.html.

Suppose $n = 2^k$ and $d = 2^j$ (with $j < k$) are both powers of $2$. Is there a known formula for $A_2(2^k,2^j)$? It seems like a strong enough assumption that a closed formula should exist.

I am also interested if there are other exact results that apply when $n$ and $d$ can be large.

• Some glossary: binary code here is: subset of $K_n=(\mathbf{Z}/2\mathbf{Z})^n$. Distance is $\ell^1$-distance, aka Hamming distance. $A_2(n,d)$ is the maximum among all cardinals of subsets of $K_n$ in which points are pairwise at distance $\ge d$. – YCor Mar 21 '17 at 1:13

I doubt that a general formula is known, even in this special case. But the largest and smallest $2+2$ cases are easy: for all $n$, whether of the form $2^k$ or not, we have:
• $A_2(n,1) = 2^n$ (trivial);
• $A_2(n,2) = 2^{n-1}$ (partiy code);
• $A_2(n,n) = 2$ (repetition code), and most interestingly:
• if $n$ is even then $A_2(n,n/2) \leq 2n$, with equality at least when $n = 2^k$ (extended Hamming code).
• [Likewise $A_2(n-1, n/2) \leq n$, with the same equality condition.]
When $n=2^k$, these are all examples of Reed-Muller codes, and there's one of minimal distance $2^j$ for each $j$; but in general they're far from optimal.