2
$\begingroup$

I have recently looked through perfect error correcting codes and found the Hamming(7,3) and Golay(23,7). Using a computer program I have found a new 2 bit perfect error correcting code: Code(90, 2). Proof: 1+90+89*90/2=2^12

This code has 5 bits and can theoretically correct any 2 bit errors in an 85 bit message - total: 90 bits.

I have ran the following computer program and I think it confirms that there are no other perfect error correcting codes that can correct up to 10'000 bits of error and have a total length less than 1'000'000.

Can some math prove/disprove the existence of such codes? Are there any other bigger than 3 bit perfect error correcting codes? Does the monster group or any other groups relate to such codes?

        int maxn = 1000000;
        int maxe = 10000;
        long[] sum = new long[maxe];
        sum[0] = 1;
        HashSet<int> codes = new HashSet<int>();
        string s1 = "";
        for (int n = 1; n < maxn; n++)
        {
            long[] news = new long[maxe];
            news[0] = 1;
            for (int j = 1; j < Math.Min(n, maxe); j++)
            {
                long v = news[j] = news[j - 1] + sum[j] - (j >= 2 ? sum[j - 2] : 0);
                if ((v & (v - 1)) == 0)
                {
                    if (n > j * 2 + 1 && !codes.Contains(j))
                    {
                        codes.Add(j);
                        s1 += "Code(" + n.ToString() + "," + (2 * j + 1).ToString() + ")\r\n";
                    }
                }
            }
            if (n < maxe)
            {
                news[n] = news[n - 1] + 1;
            }
            sum = news;
        }
$\endgroup$
4
  • 10
    $\begingroup$ That's a necessary but not a sufficient condition for the existence of a perfect code. By a special case of the Tietäväinen-van Lint theorem, there's no perfect code with those parameters. The Diophantine equation $1 + n + {n \choose 2} = 2^e$ is equivalent to Ramanujan's question about $y^2 + 7 = 2^x$, settled by Nagell's theorem that $(x,y) = (15, \pm 181)$ is the last pair of integer solutions. $\endgroup$ Feb 27, 2017 at 3:17
  • 6
    $\begingroup$ Checking my notes I see that this is already part of Lloyd's theorem, preceding TvL. math.harvard.edu/~elkies/M256.13/lloyd.pdf $\endgroup$ Feb 27, 2017 at 3:20
  • $\begingroup$ Comment: In practice there will be differing network packet sizes, apis, and consistency issues which would be a problem for a single perfect algorithm. Under some contrived mathematical definition then you could of course have a perfect algorithm. $\endgroup$ Feb 27, 2017 at 3:38
  • $\begingroup$ Thank you @Noam D. Elkies. I believe the document you pointed to answers the question as there are no other perfect error correcting codes. This question can be marked as answered. $\endgroup$
    – RobertB.
    Mar 1, 2017 at 20:47

1 Answer 1

1
$\begingroup$

This question was answered by @Noam D. Elkies in the above comments with an excellent link to an article describing the problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.