Combinatorial Games and Error-Correcting Codes

Abstract

Combinatorial game theory and coding theory appear to be completely separate fields at first glance. However, they share a profound connection through structures known as lexicographic codes, or lexicodes. First introduced by Conway and Sloane in 1986, lexicodes are generated by greedily selecting words from the space 𝔽ⁿ_B, and the conditions we impose on the selection algorithm and the structures of these codes form the bridge between error-correcting codes and lexicodes. We explore this bridge in detail, beginning with the foundations of the Sprague-Grundy theory of combinatorial games and nim-addition, as well as providing some intuition as to how a game's winning strategy can be represented as a binary code, referred to as a losing code. We then generalize the concept of a losing code to base B, and then prove the relation between lexicodes and games, and discover the structures hidden in lexicodes. In particular, we demonstrate how lexicodes constructed over bases that are Fermat powers of 2 naturally form linear codes, and introduce the notion of nim-multiplication as the scalar multiplication that the code is closed under. Then, we look at how certain combinatorial games' losing codes are error-correcting codes, including the classical Hamming codes and the extended binary Golay code. We then incorporate recent research by Yuki Irie to show that this greedy construction is not limited to bases that are powers of two; by applying a basis modification, we provide a proof that the algorithm successfully generates the extended ternary Golay code in base 3. Finally, we analyze constant weight lexicodes, establishing their connection to game theory and demonstrating how these restricted codes can generate highly symmetric combinatorial designs, specifically the S(5, 8, 24) and S(5, 6, 12) Steiner systems. Ultimately, this paper synthesizes classical results with modern developments to highlight the enduring utility of game theory in understanding optimal error-correcting codes.

Domains and classifications

Version history

Expositio keeps public paper versions together so readers can see the current PDF while still understanding how the record has changed.