Update on the Golay problem

I played around with what I’m calling the Golay problem over Christmas and wrote a blog post about it. I rewrote the post as I learned more about the problem due to experimentation and helpful feedback via comments and Twitter.

In short, the Golay problem is to classify the values of N and n such that

is a power of 2. It’s called the Golay problem because Marcel Golay discovered the solutions (23, 3) and (90, 2) in 1949. He used the former as the basis for the error correcting code that bears his name.

S(N, n) is a power of 2 if

• 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 other solutions, as far as I know, are the two that Golay discovered.

I wrote a Python program to explore the problem, not intending to use it for large values of N. Then I became interested in searching further and it was clear that Python wouldn’t cut it. My son in law Aaron Smith offered to port the program to C using the GMP library, and the new code ran much faster.

The C code was about 40x faster for small values of N, and its speed advantage increases for larger values of N. I’ve currently verified that there are no more solutions up to N = 30,000.