53
$\begingroup$

Define the function $$S(N, n) = \sum_{k=0}^n \binom{N}{k}.$$

For what values of $N$ and $n$ does this function equal a power of 2?

There are three classes of solutions:

  • $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.

There are only two solutions $(N, n)$ outside of these three classes as far as I know: (23, 3) and (90, 2). These were discovered by Marcel Golay in 1949. There are no more solutions with $N < 30{,}000$.

I've written more about this problem here.

By the way, I looked in Concrete Mathematics hoping to find a nice closed form for $S(N, n)$ but the book specifically says there isn't a closed form for this sum. There is a sum in terms of the hypergeometric function $_2F_1$ but there's no nice closed form.

$\endgroup$
7
  • $\begingroup$ For each fixed $n>1$, the number of solutions $N$ is finite as the corresponding equation reduces to a finite number of (hyper)elliptic ones. $\endgroup$ Jan 1 at 19:37
  • $\begingroup$ It looks like you implicitly assume $n\leq N$ as any $N<n$ gives a trivial solution as well. $\endgroup$ Jan 1 at 21:41
  • 2
    $\begingroup$ OEIS sequence A175542 is relevant although it does not provide any additional examples. $\endgroup$ Jan 1 at 21:58
  • 3
    $\begingroup$ The case $n=2$ reduces to finding integral points on 3 elliptic curves: $N^2 + N + 2 = 2^a M^3$ indexed by $a\in\{0,1,2\}$, with additional restriction that $M$ is a power of 2. The solutions here can be easily computed with existing software (eg., Sage) and happen to be $N\in\{0,1,2,5,90\}$. $\endgroup$ Jan 2 at 1:02
  • 1
    $\begingroup$ Irreducibility over the integers is generic behavior for polynomials, see e.g., mathoverflow.net/questions/60101/… . The height of these polynomials grows exponentially in $n$, and the probability of reducibility is inversely proportional to height, so this irreducibility observation is not extremely surprising. $\endgroup$
    – Terry Tao
    Jan 5 at 18:31

4 Answers 4

23
$\begingroup$

The case $n=2$ was settled by Nagell in 1948 and suspected (?) by Ramanujan in 1913, but in an equivalent form.

As John points out in his growing blog post, the $n = 2$ case is a quadratic equation which, via the quadratic formula, requires that $2^n - 7 = x^2$ for some integer $x$.

Motivated by who-knows-what, Ramanujan posted the following in 1913 (J. Indian Math.).

Question 464. $2^n - 7$ is a perfect square for the values $3, 4, 5, 7, 15$ of $n$. Find other values.

A posted "solution" just verified the values of $n$ he gave and did not address whether there are other solutions. The same problem was proposed by Ljunggren in a Norwegian journal in 1943; in 1948 Nagell proved that there are no other solutions, using a quadratic field with $\sqrt{-7}$ and focusing on values of $x$ rather than $n$.

Skolem, Chowla, and Lewis (referencing Ramanujan but not aware of Nagell's solution) solved the problem using $p$-adic techniques in 1959, prompting Nagell to republish his easier 1948 proof in English.

Meanwhile, in another part of the forest, error-correcting codes arose. With that motivation, Shapiro and Slotnick essentially reconstructed Nagell's approach in 1959. Their subsequent results make use of other error-correcting code structures; techniques in coding veer away from the binomial sum question. As van Lint explained in a 1975 survey,

Although as far as perfect codes are concerned the problem has been settled, the purely number-theoretic problem of finding all solutions of (5.2) remains open.

where (5.2) is the more general $\sum_{i=0}^e \binom{n}{i} (q-1)^i = q^k$ where $q$ is a power of a prime.

Bringing Nagell into the error-correcting code literature occurred by 1964 (Cohen). The OEIS entries A215797, A060728, and A038198 address the problem from different viewpoints.


There's one reference to another solution that I have not been able to track down. In a 1998 textbook on error correcting codes, John Baylis writes (p109)

...so $2+n+n^2$ must be a power of 2. It was shown in 1930 that $n = 1, 2, 5$ and 90 are the only positive integers for which this is true.

Any idea what 1930 result he has in mind?


References:

Baylis, Error-Correcting Codes, Chapman & Hall, 1998.

Berndt, Choi, Kang, The problems submitted by Ramanujan to the Journal of the Indian Mathematical Society, Contemporary Mathematics 236, 1999.

Cohen, A note on double perfect error-correcting codes on $q$ symbols, Information and Control 7, 1964.

Nagell, The diophantine equation $x^2 + 7 = 2^n$, Arkiv Math. 4, 1961 (English version of his 1948 article published in Norwegian).

Shapiro, Slotnick, On the mathematical theory of error correcting codes, IBM Journal, January 1959 (available through IEEE).

Skolem, Chowla, Lewis, The diophantine equation $2^{n+2} - 7 = x^2$ and related problems, Proc. AMS 10, 1959.

van Lint, A survey of perfect codes, Rocky Mountain J. Math. 5, 1975.

$\endgroup$
2
  • $\begingroup$ It's a nice historical perspective. And it's amazing to see how problems that took quite an effort some decades ago are now solved routinely with computers thanks to development of computational methods and software. $\endgroup$ Jan 3 at 15:33
  • 1
    $\begingroup$ For a 2-adic approach to the Ramanujan-Nagell equation see users.renyi.hu/~gharcos/ramanujan_nagell.pdf $\endgroup$
    – GH from MO
    Jan 5 at 10:51
24
$\begingroup$

I doubt this problem has an easy solution. It is clear how it was approached for small fixed $N$. Below I show how it can be addressed for the case of fixed odd $n>1$.

When $n>1$ is odd, $S(N,n)$ as a polynomial in $N$ is divisible by $N+1$. Let $n!\cdot S(N,n) = (N+1)\cdot g_n(N)$, where $g_n(N)$ is a polynomial with integer coefficients. Hence, any solution $N$ has the form $d\cdot 2^k-1$, where $d$ runs over the divisors of $\operatorname{OddPart}(n!)$. Then $g_n(d\cdot 2^k-1)$ as a co-factor must be of the form $\frac{\operatorname{OddPart}(n!)}{d}2^\ell$, which gives an equation that can be solved for $k$ and $\ell$ (additionally we need $k+\ell\geq \nu_2(n!)$, which can be checked later).


Example for $n=3$. We have $$6\cdot S(N,3) = (N+1)\cdot g_3(N),$$ where $g_3(N)=N^2 - N + 6$. Hence, $N=2^k - 1$ or $3\cdot 2^k-1$.

If $N=2^k - 1$, then $$g_3(2^k - 1) = 2^{2k} - 3\cdot 2^k + 8,$$ where we first iterate over $k\le \nu_2(8)=3$, each of which happens to be deliver $g_3(2^k - 1)$ in the required form $3\cdot 2^\ell$, namely $(k,\ell)\in\{ (0,1), (1,1), (2,2), (3,4)\}$. Then consider the case $k>3$ implying $g_3(2^k - 1) = 3\cdot 2^3$ and giving no solutions.

If $N=3\cdot 2^k - 1$, then $$g_3(3\cdot 2^k - 1) = 9\cdot 2^{2k} - 9\cdot 2^k + 8,$$ where we again first iterate over $k\le \nu_2(8)=3$, getting solutions $(k,\ell)\in\{ (0,3), (3,9)\}$. Then for $k>3$, we have $g_3(3\cdot 2^k - 1) = 2^3$, getting only extraneous $k=0$.

In summary for $n=3$, the solutions are $N\in\{0,1,2,3,7,23\}$.


I've computed all solutions for odd $n$ in the interval $[5,49]$, and verified that there are no non-trivial ones.

ADDED. As for even $n$, I explained in the comments that the case $n=2$ is solved via finding integral points on elliptic curves. Similarly, the case $n=4$ can be reduced to finding integral points on two quartic curves, for which Magma is able to compute the solutions and confirm that there are no non-trivial ones. So, the smallest unsolved $n$ is $n=6$.

$\endgroup$
17
$\begingroup$

This is a follow-up to John's answer.

Here is the questionable "theorem" from the 2nd (2013) edition of Erickson's book (thanks @spin for the pointer), which in the 1st (1996) edition was numbered as Theorem 9.3. Apparently, the statement about "only two feasible sets of parameters for perfect codes" is correct, but "theorem" as stated lacks a proof (and thus may be incorrect) and was not an argument for non-existence of other perfect codes. Reference [22] is Pless' book. Page 157 from Martin Erickson's "Introduction to Combinatorics" book (2013)


And here are two pages (pages 23-24) with a relevant discussion from the 3rd (1998) edition of Pless' book. It does mention Tietäväinen and van Lint results on page 24, but they do not imply the "theorem" from Erickson's book. Reference [29] is

A. Tietäväinen, "On the nonexistence of perfect codes over finite fields", SIAM J. Appl. Math. 24 (1973), 88-96.

Page 23 from Vera Pless "Introduction to the Theory of Error-correcting Codes" book (1998) Page 24 from Vera Pless "Introduction to the Theory of Error-correcting Codes" book (1998)


$\endgroup$
13
$\begingroup$

Theorem 9.3 in Martin Erickson's book Introduction to Combinatorics says that the two solutions (23, 3) and (90, 2) are the only ones. Thanks to Steve Kass (@stevekass on Twitter) for providing this reference.

Erickson does not give a proof, but implies that Vera Pless gives a proof in her book Introduction to the Theory of Error-correcting Codes, Wiley, 1989.

Update: Apparently the book by Vera Pless does not give a proof.

$\endgroup$
15
  • 5
    $\begingroup$ I cannot find a proof in Pless' book. There is one page (page 23) discussion, which essentially says that such and such parameters give such and such codes, but it does not claim that other parameters do not exist. $\endgroup$ Jan 2 at 4:05
  • 2
    $\begingroup$ Me neither. But I find the following reference: "Tietäväinen, Aimo On the nonexistence of perfect codes over finite fields. SIAM J. Appl. Math. 24 (1973), 88-96." doi.org/10.1137/0124010 $\endgroup$
    – spin
    Jan 2 at 4:07
  • 12
    $\begingroup$ If I got it correctly, the issue with the codes perspective is that the equation in question is only necessary but not sufficient for codes to exist. So, non-existence of certain codes does not necessarily mean that our equation does not have other non-trivial solutions. $\endgroup$ Jan 2 at 4:34
  • 4
    $\begingroup$ @JohnD.Cook: In fact, Pless says that the two perfect codes correspond to solutions $(5,2)$ and $(23,3)$, while the solution $(90,2)$ does not correspond to any perfect code. It does not seem to follow from anywhere that there are no other solutions like $(90,2)$. $\endgroup$ Jan 2 at 14:35
  • 17
    $\begingroup$ To be honest, I doubt that this "theorem" is within the reach of existing technology; when $N, n$ are both large (say $n \sim N^\theta$ for some $0 < \theta < 1$) the binomial sum has no exploitable structure, and we have no tools with which to rule out that this sum might occasionally collide with a power of 2 by pure chance (though standard heuristics, based on the fact that a typical number $k$ has probability $\sim 1/(k \log 2)$ of being a power of 2, suggests this happens at most finitely often for say $3 \leq n < N/2$). My guess is that Erickson misread the discussion in Pless's book. $\endgroup$
    – Terry Tao
    Jan 2 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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