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;
        }
Improve this question
$\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$
    – Noam D. Elkies
    Commented 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$
    – Noam D. Elkies
    Commented 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$
    – Pain Fither
    Commented 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.
    Commented Mar 1, 2017 at 20:47

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .