Perfect codes over non-prime power alphabets: an approach based on Diophantine equations

Perfect error correcting codes allow for an optimal transmission of information while guaranteeing error correction. For this reason, proving their existence has been a classical problem in both pure mathematics and information theory. Indeed, the classification of the parameters of e-error correcting perfect codes over q-ary alphabets was a very active topic of research in the late 20th century. Consequently, all parameters of perfect e-error correcting codes were found if e 3, and it was conjectured that no perfect 2-error correcting codes exist over any q-ary alphabet, where q > 3. In the 1970s, this was proved for q a prime power, for q = 2ʳ3ˢ and for only 7 other values of q. Almost 50 years later, it is surprising to note that there have been no new results in this regard and the classification of 2-error correcting codes over non-prime power alphabets remains an open problem. In this paper, we use techniques from the resolution of generalised Ramanujan--Nagell equation and from modern computational number theory to show that perfect 2-error correcting codes do not exist for 172 new values of q which are not prime powers, substantially increasing the values of q which are now classified. In addition, we prove that, for any fixed value of q, there can be at most finitely many perfect 2-error correcting codes over an alphabet of size q.