When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?

Question

Also asked on MathOverflow: When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?

Introduction

Recently, a friend told me about the following interesting fact:

Place $n$ points on a circle and draw a line between every pair of points. Suppose that no three lines intersect at one point. Then the number of regions which are separated by the lines is equal to the sum of the first five numbers in the $n-1$st row of Pascal's triangle!

See this image image (from Wikipedia). Here, $n$ is the number of points, $c$ is the number of lines and $r_G$ is the number of regions:

Here is a great video by 3Blue1Brown on this subject: Circle Division Solution. The series is A000127 in the OEIS.

Preliminary results

The following is known (see again Wikipedia for instance):

For $n$ points, the number of resulting regions is $$1+\binom n2+\binom n4 = \sum_{i=0}^4 \binom{n-1}i=\text{sum of first } 5 \text{ numbers in $n$th row of Pascal's triang.}=\frac{1}{24}n(n^3-6n^2+23n-18)+1.$$

In particular, for $n\in\{1,2,3,4,5,10\}$, the number of areas is a power of $2$.

My question

Is it true that, for any other $n$, the number of areas is not a power of two?

Some attempts

First off, we can simply check that for $n\in\{6,7,8,9\}$, the number of areas is not a power of two. So the question is equivalent to: Is it true that, for any $n\geq 11$, the number of areas is not a power of $2$?

The following Proposition is easy to prove:

Proposition. For $n> 5$, we have that $f(n)< 2^{n-1}$, where $f(n)$ denotes the number of regions.

Proof. For $n>5$ we have $$f(n)=\sum_{i=0}^{n-1} \binom{n-1}i-\sum_{i=5}^{n-1}\binom{n-1}i = 2^{n-1}-\sum_{i=5}^{n-1}\binom{n-1}i<2^{n-1}.\square$$

---

However, this only proves that $f(n)\neq 2^{n-1}$ for any $n>6$. There could still be some $m\in\mathbb N$ with $m<n$ such that $f(n)=2^m$.

Answer 1

This is a copy of my answer at MO.

Denoting $k:=2^{\lfloor m/2\rfloor}$, we get two cases to consider: $k^2 = f(n)$ and $2k^2 = f(n)$, or making the coefficients integer: $$(12k)^2 = 144f(n)\qquad\text{and}\qquad (12k)^2 = 72f(n).$$

These equations have finite number of integer solutions by Siegel's theorem.

Numerically these equations can be solved in Magma with IntegralQuarticPoints() function.

---

For the first equation, Magma gives the following integral points $(n,12k)$ (up to a sign of $k$):

[ [ 36, 2928 ], [ 5, 48 ], [ 3, -24 ], [ 1, 12 ], [ -12, 456 ], [ 10, -192 ], [ -2, -36 ], [ -237, 139344 ], [ 0, -12 ] ]

which correspond to the following solutions in $n$ and $m$: $$(n,m)\in \{ (5, 4), (3, 2), (1, 0), (10, 8) \}.$$

Similarly, for the second equation we get that the only solutions are $(n,m) \in \{ (2,1), (4,3) \}$.

Hence, there are no other solutions besides those mentioned by OP.

Answer 2

A partial result: let $$ f(n)=\frac{1}{24}n(n^3-6n^2+23n-18)+1 $$

Then for $n=6,7,8,9\mod 8$ we have $f(n)=\text{odd}$, and so it cannot be a power of $2$. The proof is trivial: say e.g., $n=8m+6$; then \begin{align} f(n)&=\frac{512 m^4}{3}+384 m^3+\frac{1048 m^2}{3}+158 m+31\\ &=1062 \binom{m}{1}+5392 \binom{m}{2}+8448 \binom{m}{3}+4096 \binom{m}{4}+31 \end{align} which is manifestly odd. The other three cases are identical.

So it only remains to consider the cases $n=2,3,4,5\mod 8$. For all of these, $f(n)$ is even, and so it may be a power of $2$. I have no proof that this cannot happen. One could try and break these cases into mod 16, but this leads nowhere as far as I an see (it is easy to check that $f(n)=2\times\mathrm{odd}$ for $n=2,11,12,13\mod 16$, but the cases $n=10,3,4,5\mod16$ are again divisible by $4$, and so we are back to square one).

Answer 3

A heuristic for why we shouldn't expect further solutions: $f$ is increasing for $n\geq0$. Therefore, the number of integers $f$ between $f(n)$ and $f(n+1)$ (inclusive, exclusive) is $$f(n+1)-f(n)=\frac{1}{6}n\left(n^2-3n+8\right).$$ We might therefore estimate the "probability" of a number $k$ being taken by $f$ as the reciprocal of this quantity, $$\frac{6}{k\left(k^2-3k+8\right)}.$$ Numerical analysis by @Pazzaz shows that no further power of two is taken for $n\leq1.4\times10^{10}$. This means, again since $f$ is incrasing, that no power of two less than $$\frac{1}{24}\left(1.4\times10^{10}\right)\left(\left(1.4\times10^{10}\right)^3-6\left(1.4\times10^{10}\right)^2+23\left(1.4\times10^{10}\right)-18\right)+1\approx2^{130.23387},$$ other than those already found, is taken by $f$. So, we should expect $$\sum_{k=131}^\infty\frac{6}{2^k\left(2^{2k}-3\cdot2^k+8\right)}\approx3.39903\times10^{-118}$$ powers of two left to find. In other words, virtually none.

This is not a proof, but it should be reason to convince yourself that the list is complete, unless some astronomical numerical coincidence holds, or unless some hidden relationship exists.

Answer 4

Accepting by inspection that $f(n)$ is odd for $n=1,6,7,0$ mod $8$, then$$f(n)\ne 2^m$$for half of all $n$.

Further, $3$ divides $f(n)$ for $n=7,8$ mod $9$. And since half of these $f(n)$ are even, we can rule out $\frac{1}{9}$ of even $f(n)$.

Thus we can say$$f(n)\ne 2^m$$for $$\frac{1}{2}+\frac{1}{9}=\frac{11}{18}$$of $f(n)$.

Again by inspection, the only odd prime factors $<101$ of $f(n)$ are$$3,11,19,23,31,37,47,61,67,83,89,97$$Now $11$ divides $f(n)$ for every eleventh $n$ beginning with $n=8$, although some of these $f(n)$ have already been excluded as even multiples of $3$.

Every odd prime factor $p>3$ of $f(n)$ appears for some $f(n)<p$ and recurs in this predictable way for every $pth$ subsequent $f(n)$. Hence we can identify countless sequences of $f(n)$ for which $f(n)\ne 2^m$.

But the question still remains, May some even $f(n)>2^8=2^m$?

I have tried a more general approach and searched in Pascal's triangle for $f(n)=2^m$ when $k$, the number of terms being summed in each row of the triangle, is other than $5$.

Since each row begins with $1$, clearly for $k=1$,$$f(n)=1=2^0$$for all $n$.

For $k=2$, since the second term in each row is $n-1$, then $f(n)=n$ is a power of $2$ whenever $n$ itself is, i.e. infinitely many times.

For $k=3$, we find that$$f(n)=1,2,4,7,11,16,22,29,37...=\frac{n^2-n+2}{2}$$It is clear that for all $k$, $f(n)$ is a power of $2$ for $n\le k$, since an entire row of the triangle is then being summed. It is also clear that $f(n)$ is a power of $2$ when $n=2k$, since there are then an even number of terms in symmetry in the row; since $f(k)=2^{k-1}$, then the sum of the first $k$ terms of the $2kth$ row is$$\frac{1}{2}2^{2k-1}=2^{2k-2}$$Thus, as in the posted case of $k=5$, here too $f(n)=2^{k-1}$ and $2^{2k-2}$ when $n=k$ and $2k$, respectively. For $n\le 90$, no other $f(n)$ is a power of $2$ when $k=3$. I was tempted to conjecture that, setting aside the obvious cases where $k$ exceeds the number of terms in a row of the triangle, $f(n)$ can be a power of $2$ IFF $n=k$ or $n=2k$, i.e. when we sum either the entire row with $k$ terms or half the row with $2k$ terms, and that any ratio $\frac{k}{n}$ other than $\frac{1}{1}$ or $\frac{1}{2}$, yields a sum with at least one odd prime factor. But for $n=91$, $$f(n)=4096=2^{12}=1+90+4005$$the sum of the first three terms of the $91st$ row. Thus the ratio $\frac{k}{n}$ is here $\frac{3}{91}$, contrary to conjecture.

Again, when $k=4$,$$f(n)=1,2,4,8,15,26,42,64,93,...=\frac{n^3-3n^2+8n}{6}$$As expected, $f(n)=2^3$ and $2^6$ for $n=4$ and $8$, respectively. But further$$f(24)=2048=2^{11}=1+23+253+1771$$the sum of the first four terms of row $24$. Thus in this case$$\frac{k}{n}=\frac{1}{6}$$again contrary to conjecture. This power of $2$ appeared for a value of $n$ relatively small, but nonetheless greater than $n=2k$.

Thus $f(n)$ is a power of $2$ for at least one $n>2k$ for every $k<5$.

But for $k=5$, as OP and others have found, $f(n)\ne2^m$ for any $n>2k=10$.

For $k=6$,$$f(n)=1,2,4,8,16,32,63,120,219...=\frac{n^5-10n^4+55n^3-110n^2+184n}{120}$$I don't find $f(n)=2^m$ for $n>2k=12$. Does this rule apply to partial sums of terms in rows of Pascal's triangle for all $k>4$? If so, can it be proven?