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

is a power of 2, say 2^p. 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 2^p.

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!)Nⁿ + ... + 1

and so we are looking for positive integer solutions to

Nⁿ + ... + n! = n! 2^p.

Using the rational root theorem

By the rational root theorem, a necessary condition for

Nⁿ + ... - n!(2^p -1)= 0

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

-n!(2^p -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!(2^p -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!(2³² -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(2³² -1) and see if any of them equal 2³². 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) > 2³² 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

2^p+3 - 7

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

2¹⁵ - 7 = 181²,

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 2^p+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

2^p+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) = 2¹¹. 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.

The post Turning the Golay problem sideways first appeared on John D. Cook.