14
$\begingroup$

Also posted on the Math Stackexchange: 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$.


User Pazzaz at MSE said that he checked all cases up to $n=10^{10}$ and none of them were powers of $2$.

$\endgroup$
  • $\begingroup$ Have you seen this? $\endgroup$ – J. M. is not a mathematician Nov 18 at 9:53
  • 4
    $\begingroup$ When $m$ is large, for $2^m$ to equal $f(n)$ it must be that $n=\lfloor \sqrt[4]{24\cdot2^m}+1.5\rfloor$. A quick check on mathematica with $m\leq 10000$ found no solution; this means for every $n$ smaller than about $10^{250}$ (and bigger than 10) that $f(n)$ is NOT a power of $2$. $\endgroup$ – Joel Moreira Nov 18 at 16:32
  • $\begingroup$ See example 5 of this paper $\endgroup$ – Ivan Meir Nov 18 at 17:17
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If I understand correctly, this Magma function isn't guaranteed to produce all solutions. Does Magma tell you when it is not sure that it has found all solutions? $\endgroup$ – Timothy Chow Nov 19 at 4:11
  • 1
    $\begingroup$ @TimothyChow: If it terminates, it guarantees producing all solutions (its description says "returns all integral points"). So, it fails when it does not produce an answer in a reasonable amount of time. For the current problem, we are lucky that it does terminate. $\endgroup$ – Max Alekseyev Nov 19 at 4:18
  • $\begingroup$ Thank you for the answer (and for drawing my attention to the Magma Software too) $\endgroup$ – Maximilian Janisch Nov 19 at 15:31
  • $\begingroup$ @MaxAlekseyev : Okay. I remain somewhat skeptical because the documentation for IntegralPoints says that the function calls MordellWeilGroup, for which no guaranteed algorithm is known, and which sometimes returns unproven results along with a warning that the result is unproven. I suppose IntegralPoints could artificially enter an infinite loop when MordellWeilRank returns a warning, but I would be surprised if it does so. Perhaps IntegralPoints returns a warning whenever MordellWeilRank returns a warning, but since the documentation doesn't say this explicitly, I'm a little wary. $\endgroup$ – Timothy Chow Nov 19 at 19:49
  • 1
    $\begingroup$ In the magma source for the function MWFreeBasis there is the following warning > if rlow ne rhigh or #gens lt rlow then > printf "WARNING"* > "\nIntegralPoints could not determine the Mordell-Weil group."* > "\nAfter applying all available tools,\n %o <= rank <= %o."* > "\nThe known subgroup has rank %o, with generators: \n %o."* > "\nOnly integral points contained in this subgroup will be found.\n\n", > rlow, rhigh, #gens, gens; > end if; this is called by IntegralQuarticPoints so I believe if there was a problem you would see this. $\endgroup$ – Alex J Best Nov 23 at 20:29
8
$\begingroup$

In this paper by Schinzel and Tijdeman it is proven that if a polynomial $P(x)$ with rational coefficients has at least 2 distinct zeros then the equation $$y^m=P(x),\;\;\;\; x,y\in\mathbb{Z}, \;\;\;\;\;|y|\geq2$$ implies that $m<c(P)$ where $c(P)$ is an effectively computable constant.

They deduce a corollary (3) which says that if polynomial $P(x)$ with rational coefficients has at least 3 simple zeros then the equation $y^m=P(x)$ has only finitely many solutions with $m\geq2$ and $|y|\geq2$ and these solutions can be found effectively.

Since $f(x)=\frac{1}{24} \left(n^4-6 n^3+23 n^2-18 n+24\right)$ has all roots simple and $f(n)=2^r$ implies $r\geq2$ for $n>2$ we can apply the theorem to show that $f(n)=2^m$ has only finitely many solutions and they can be found effectively.

So this at least reduces the problem to a finite search.

$\endgroup$
7
$\begingroup$

I can prove that there are only finitely many solutions as a consequence of Theorem 2 in The $p$-adic generalization of the Thue-Siegel-Roth theorem (Ridout, Mathematika 2010). Specializing this theorem slightly, it states

Let $F(x,y)$ be a homogenous irreducible polynomial with integral coefficients of degree $n \geq 3$. Let $p$ be a prime and let $G_p(x,y)$ be the greatest power of $p$ dividing $F(x,y)$. Let $\kappa > 2$. Then there are only finitely many solutions to $$\frac{|F(x,y)|}{G_p(x,y)} < \max(|x|,|y|)^{n-\kappa}$$ with $GCD(x,y)=1$.

Putting $y=1$, we deduce

Let $f(x)$ be an irreducible polynomial with integral coefficients of degree $n \geq 3$. Let $p$ be a prime and let $g(x)$ be the greatest power of $p$ dividing $f(x)$. Let $\kappa > 2$. Then there are only finitely many solutions to $$\frac{|f(x)|}{g_p(x)} < |x|^{n-\kappa}.$$

It is quite probable that the version with $y=1$ is much easier, but I didn't find a source in the literature for the easier version.

Now, let $$\binom{x}{0} + \binom{x}{1} + \binom{x}{2} + \binom{x}{3} + \binom{x}{4} = \frac{f(x)}{24}.$$ The polynomial $f(x)$ is $x^4-2 x^3+11 x^2+14 x+24$, which is easily checked to be irreducible. So there are only finitely many solutions to $$\frac{|f(x)|}{g_2(x)} < \max(|x|)^{1.9}.$$ But, if $f(x)$ is a power of $2$, then $\tfrac{|f(x)|}{g_2(x)} = 3$. So this can only happen finitely often.

$\endgroup$
  • $\begingroup$ This is quite interesting. $\endgroup$ – EGME Nov 18 at 23:03

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.