Turning the Golay problem sideways

I’ve written a couple posts about the Golay problem recently, first here then here. The problem is to find all values of N and n such that

S(N, n) = \sum_{k=0}^n \binom{N}{k}

is a power of 2, say 2p. Most solutions apparently fall into three categories:

  • n = 0 or n = N,
  • N is odd and n = (N-1)/2, or
  • n = 1 and N is one less than a power of two.

The only two other solutions as far as I know are the two that Golay found, namely N = 23 with n = 3 and N = 90 with n = 2. Those are the only solutions for N < 30,000.

Solutions for fixed p

Phil Connor wrote me with a good suggestion: for fixed n, S(N, n) is an nth degree polynomial in N, and we can search for when that polynomial equals 2p.

Instead of looping over N and seeing whether any S(N, n) is a power of 2 comes out, we could fix p and see whether there’s a corresponding value of N.

Now

S(N, n) = (1/n!)Nn + … + 1

and so we are looking for positive integer solutions to

Nn + … + n! = n! 2p.

Using the rational root theorem

By the rational root theorem, a necessary condition for

Nn + … – n!(2p -1)= 0

to have a rational root is that N must divide the constant term

-n!(2p -1).

That means that for fixed n and fixed p there are only a finite number of Ns that could possibly be solutions, namely the divisors of

n!(2p -1).

Say we wanted to find all solutions with p = 32 and n = 3. Then we only need to check 96 values of N because 3!(232 -1) has 96 divisors as the following Python code shows.

    >>> from sympy import divisors
    >>> len(divisors(6*(2**32-1)))
    96

We could evaluate S(N, 3) for each of the divisors of 6(232 -1) and see if any of them equal 232. And since S(N, n) is an increasing function of N, we could speed things up by being a little clever in our search. For example, if S(d, 3) > 232 for a particular divisor d, there’s no need to keep trying larger divisors. More generally, we could do a binary search.

Not only could this approach be more efficient, I suspect it casts the problem in a form that would make it easier to prove theorems about.

Using the quadratic equation

The rational root theorem isn’t the only theorem we could apply to the polynomial formulation of the Golay problem. For example, if n = 2 we can use the quadratic equation and look at the discriminant to show that a necessary condition for there to be an integer solution is that

2p+3 – 7

must be a positive integer. When p = 12 we get

215 – 7 = 1812,

and this corresponds to Golay’s solution N = 90. There cannot be any solutions for larger values of p if p is odd because then 2p+3 is a perfect square and there cannot be another perfect square so close. I don’t know whether there can be larger even values of p with

2p+3 – 7

being a perfect square. If someone could show there are no such solutions, this would prove Golay found the only solution with n = 2. Maybe something similar would work for larger values of n.

Rumors of a proof

The conjecture I’ve been writing about is listed as Theorem 9.3 in Martin Erickson’s book Introduction to Combinatorics, Erickson does not give a proof but refers to Vera Pless’ book Introduction to the Theory of Error-correcting Codes, Wiley, 1989. However, people on MathOverflow who have seen Pless’ book say there’s no proof there.

Terry Tao says he doubts there is a proof:

To be honest, I doubt that this “theorem” is within the reach of existing technology. … My guess is that Erickson misread the discussion in Pless’s book.

Part of the confusion is that exceptional solutions to the problem discussed here are necessary (but not sufficient) for the existence of perfect Golay codes. It is widely reported that there is only one perfect binary Golay code, one based on S(23, 3) = 211. Some have taken that to mean that there are no more exceptional solutions, but this doesn’t follow. Maybe there are more exceptional solutions, but they don’t lead to the existence of more perfect binary Golay codes.

I haven’t seen a proof that Golay’s 23-bit code is the only perfect binary Golay code, though I’ve seen this theorem quoted repeatedly. It would be good to track down the proof of this theorem (if there is one!) and see whether it proves what I’m calling the Golay conjecture as an intermediate step. (Update: it does not. Seems Terry Tao was right to suspect there is no proof.)

2 thoughts on “Turning the Golay problem sideways

  1. This is related to the fact that the variant of the Collatz conjecture using 181n+1 is false:
    27 * 181 + 1 = 4888
    4888 / 8 = 611
    611 * 181 + 1 = 110592
    110592 / 4096 = 27
    Because 2^15 is slightly larger than 181^2. I haven’t found any other examples of this

  2. That the only nontrivial perfect codes are the Hamming and Golay codes is Theorem 33 (due to Tietäväinen and Van Lint) in Chapter 6 of MacWilliams and Sloane’s book, “The Theory of Error-Correcting Codes” (North-Holland, 1977). That your condition on the sum of the binomial coefficients is necessary for a perfect binary code is their Lemma 34 (which they call “the sphere packing condition”). But as you can verify yourself if you obtain a copy of the book, the proof of Theorem 33 does not show that there are no other solutions to the sphere packing condition. They have a remark that a computer search has turned up only one other solution (the one with n = 90), but they do not claim that there can be no other solutions.

Leave a Reply

Your email address will not be published.