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.