A binary code of length 21 with minimum distance 10

How many binary words of length 21 can be chosen so that any two differ in at least 10 positions? The best code known has 42 words, found in 1989. Semidefinite programming shows that no code has more than 47. Closing this gap means either constructing a code with 43 words or proving that 42 is optimal.

Problem

Let $A(n,d)$ be the largest size of a binary code $C \subseteq \{0,1\}^n$ in which any two distinct codewords are at Hamming distance at least $d$. Currently

$$42 \le A(21,10) \le 47 .$$

Construct an explicit code $C \subseteq \{0,1\}^{21}$ with minimum distance at least 10 and $|C| \ge 43$, or prove that $A(21,10) = 42$. Adding or deleting a parity bit shows $A(21,10) = A(20,9)$, so one may equally look for a four-error-correcting code of length 20 with 43 words.

Background

The numbers $A(n,d)$ are the basic extremal quantities of coding theory. Brouwer maintains a table of the best known bounds for unrestricted, not necessarily linear, binary codes [4]. Lower bounds come from explicit constructions. Upper bounds come from linear programming and, more recently, semidefinite programming: Schrijver (2005) obtained new code bounds from the Terwilliger algebra [3], and Gijswijt, Mittelmann and Schrijver (2012) extended the method to quadruples of codewords [2]. Small open cases such as $A(21,10)$ test both kinds of method.

What is known

• Lower bound $A(21,10) \ge 42$: Kaikkonen (1989) constructed a four-error-correcting code of length 20 with 42 words [1]. Brouwer's table lists this as the best known lower bound, and HorizonMath uses 42 as its baseline [4].
• Upper bound $A(21,10) \le 47$: Gijswijt, Mittelmann and Schrijver (2012), by semidefinite programming with quadruple distances [2]. This improved the bound of 48 from van Pul's 1982 thesis, as recorded in [4].
• HorizonMath places the problem in its top difficulty tier ("possibly unsolvable"), allowing for the possibility that 42 is optimal.

What would count as progress

• A list of 43 or more distinct words of length 21 with all pairwise Hamming distances at least 10. HorizonMath's validator checks every pair, by XOR and popcount, in a fraction of a second. Any such code beats the baseline of 42.
• A proof that $A(21,10) \le 46$ or lower, for example by a stronger semidefinite or exhaustive computer-assisted argument with a checkable certificate. A proof that $A(21,10) = 42$ would settle the question.

References

1. M. K. Kaikkonen, "A new four-error-correcting code of length 20", IEEE Trans. Inf. Theory 35 (1989), 1344. doi:10.1109/18.45298
2. D. C. Gijswijt, H. D. Mittelmann and A. Schrijver, "Semidefinite code bounds based on quadruple distances", IEEE Trans. Inf. Theory 58 (2012), 2697–2705. doi:10.1109/TIT.2012.2184845
3. A. Schrijver, "New code upper bounds from the Terwilliger algebra and semidefinite programming", IEEE Trans. Inf. Theory 51 (2005), 2859–2866. doi:10.1109/TIT.2005.851748
4. A. E. Brouwer, "Small binary codes: Table of general binary codes", online table, accessed 2026-10-20. aeb.win.tue.nl/codes/binary-1.html

Source

Imported from HorizonMath A21_10_binary_code, curated by Erik Y. Wang, Sumeet R. Motwani et al. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.