Bossy Lobster

A blog by Danny Hermes; musing on tech, mathematics, etc.

Edit on GitHub

Moser's Circle Problem and Polynomial Root Asymptotes

3b1b Moser's Circle Problem

Below, we'll show two facts which help understand the positive integer solutions to the following diophantine equation:

1+(n2)+(n4)=2m.1 + \binom{n}{2} + \binom{n}{4} = 2^m.

We'll show that there is a lone positive root and as mm \longrightarrow \infty the root approaches:

242m4+32+O(1242m4).\sqrt[4]{24 \cdot 2^m} + \frac{3}{2} + \mathcal{O}\left(\frac{1}{\sqrt[4]{24 \cdot 2^m}}\right).

Additionally, if this root is an integer (i.e. the relevant solutions to a diophantine equation), then for m4m \geq 4 it must be exactly equal to:

n=242m4+32.n = \left\lfloor \sqrt[4]{24 \cdot 2^m} + \frac{3}{2} \right\rfloor.



I started down this path after watching a video from 3Blue1Brown1 where he discusses Moser's circle problem. In particular, he demonstrates the formula

Fn=1+(n2)+(n4)F_n = 1 + \binom{n}{2} + \binom{n}{4}

for the number of distinct regions a circle is divided into when connecting all pairs of nn points around the circle in general position.

The video is about showing the perils of assuming a pattern repeats indefinitely:

F1=1,F2=2,F3=4,F4=8,F5=16,F6=3132.F_1 = 1, F_2 = 2, F_3 = 4, F_4 = 8, F_5 = 16, F_6 = 31 \neq 32.

but also shows one more value equal to a power of two: F10=256F_{10} = 256.

Open Question

At the end of the video he poses a challenge question that piqued my interest and that's what we'll be talking about here2: Will there ever be another power of 2?

3b1b Challenge Question

There is a fairly clean solution to this on Math StackExchange, but it uses extremely non-elementary methods (I am not a number theorist). It does use a simple observation to transform the exponential part of the equation into a low degree polynomial so that existing tools for solving diophantine equations can be used. In particular, it uses the observation that 2m2^m is either equal to k2k^2 or 2k22k^2 depending on the parity of mm.

I tried (and failed) to make progress on this challenge question by investigating properties of a solution nn as mm varies. (As opposed to what I view the more common approach of investigating factors of FnF_n as nn varies.) However along the way I discovered some interesting facts about the roots as mm \longrightarrow \infty.


We'll reframe Fn=2mF_n = 2^m via a change of variables to get an explicit Laurent series to more easily understand the behavior of the positive root. Note that we can say the positive root: there is exactly one. To see why, consider

f(n;m)=24(Fn2m)=n46n3+23n218n24(2m1).\begin{aligned} f(n; m) &= 24 \left(F_n - 2^m\right) \\ &= n^4 - 6n^3 + 23n^2 - 18n - 24 \left(2^m - 1\right). \end{aligned}

This function is concave up since monic and

f(n;m)=12n236n+46=3(2n3)2+19.f''(n; m) = 12 n^2 - 36 n + 46 = 3\left(2n - 3\right)^2 + 19.

For m1m \geq 1 we have f(0;m)=f(1;m)=24(2m1)<0f(0; m) = f(1; m) = -24\left(2^m - 1\right) < 0 which guarantees a root greater than 1 and a root less than 0.

We'd like to understand the asymptotic root behavior, but as mm \longrightarrow \infty both the "input" 2m2^m goes to infinity and the "output" nn goes to infinity since the largest term of the polynomial will dominate:

n4+O(n3)=242mn242m4.n^4 + \mathcal{O}\left(n^3\right) = 24 \cdot 2^m \Longrightarrow n \approx \sqrt[4]{24 \cdot 2^m}.

We'd like a Taylor series at infinity that converges to infinity. However, no such expansion exists, so we instead use a quantity that goes to infinity as some input XX goes to zero:

n46n3+23n218n+24=242m=1X4.n^4 - 6n^3 + 23n^2 - 18n + 24 = 24 \cdot 2^m = \frac{1}{X^4}.

This satisfies 1X4\frac{1}{X^4} \longrightarrow \infty as X0+X \longrightarrow 0^+ but since n1X44=1Xn \sim \sqrt[4]{\frac{1}{X^4}} = \frac{1}{X} it doesn't solve the nn \longrightarrow \infty problem. For that, we use the substitution s=nXs = n X and now can start to pursue a Taylor series for our root via

(s/X)46(s/X)3+23(s/X)218(s/X)+24=1X4\left(s / X\right)^4 - 6\left(s / X\right)^3 + 23\left(s / X\right)^2 - 18\left(s / X\right) + 24 = \frac{1}{X^4}

which is equivalent to finding roots of the parameterized polynomial

g(s;X)=s46Xs3+23X2s218X3s+(24X41).g(s; X) = s^4 - 6X s^3 + 23 X^2 s^2 - 18 X^3 s + \left(24X^4 - 1\right).

This polynomial allows us to define the positive root α(X)\alpha(X) as an implicit function via

0g(α(X);X).0 \equiv g\left(\alpha(X); X\right).

We'll start from the Taylor series

α(X)=a0+a1X+a22X2+O(X3)\alpha(X) = a_0 + a_1 X + \frac{a_2}{2} X^2 + \mathcal{O}\left(X^3\right)

and transform to the Laurent series for n=s/Xn = s / X

a0X+a1+a22X+O(X2).\frac{a_0}{X} + a_1 + \frac{a_2}{2} X + \mathcal{O}\left(X^2\right).

Finding Coefficients

To find the first few terms of this expansion, we'll utilize SymPy. First, we'll set up our variables, our parameterized polynomial g(s;X)g(s; X) and the first three terms of the Taylor series α(X)\alpha(X) (utilizing the very useful sympy.Order type in SymPy):

In [1]: import sympy; sympy.__version__
Out[1]: '1.12'

In [2]: a0, a1, a2, s, X = sympy.symbols("a0, a1, a2, s, X")

In [3]: g = s**4 - 6 * X * s**3 + 23 * X**2 * s**2 - 18 * X**3 * s + (24 * X**4 - 1)

In [4]: alpha = a0 + a1 * X + a2 / 2 * X**2 + sympy.Order(X**3)

Substituting alpha and expanding, we have a series with quadratic terms in XX and as expected a tail of the form O(X3)\mathcal{O}\left(X^3\right):

In [5]: g.subs({s: alpha}).expand()
Out[5]: -1 + a0**4 - 6*X*a0**3 + 4*X*a0**3*a1 + 23*X**2*a0**2 - 18*X**2*a0**2*a1 + 6*X**2*a0**2*a1**2 + 2*X**2*a0**3*a2 + O(X**3)

In [6]: T2 = sympy.Poly(g.subs({s: alpha}).expand().removeO(), X)

In [7]: T2
Out[7]: Poly((2*a0**3*a2 + 6*a0**2*a1**2 - 18*a0**2*a1 + 23*a0**2)*X**2 + (4*a0**3*a1 - 6*a0**3)*X + a0**4 - 1, X, domain='ZZ[a0,a1,a2]')

Setting the coefficients of the first three terms to zero, we'll have our expansion:

In [8]: T2.coeff_monomial(1)
Out[8]: a0**4 - 1

In [9]: T2.coeff_monomial(X).factor()
Out[9]: 2*a0**3*(2*a1 - 3)

In [10]: T2.coeff_monomial(X**2).factor()
Out[10]: a0**2*(2*a0*a2 + 6*a1**2 - 18*a1 + 23)

Since we want the positive root, we choose α(0)=a0=1\alpha(0) = a_0 = 1. Independent of this value we also see a1=32a_1 = \frac{3}{2} (since all four possible values of a0a_0 are nonzero). Finally solving for the last term:

In [11]: T2.coeff_monomial(X**2).subs({a0: 1, a1: sympy.Rational(3, 2)}).factor()
Out[11]: (4*a2 + 19)/2

Putting it all together:

α(X)=1+32X198X2+O(X3).\alpha(X) = 1 + \frac{3}{2} X - \frac{19}{8} X^2 + \mathcal{O}\left(X^3\right).

Root as Floor

We'll show below that 1+12X<α(X)<1+32X1 + \frac{1}{2} X < \alpha(X) < 1 + \frac{3}{2} X for small enough XX3. Once established, this means

1X+12<n=α(X)X<1X+32\frac{1}{X} + \frac{1}{2} < n = \frac{\alpha(X)}{X} < \frac{1}{X} + \frac{3}{2}

and since this interval has a width of 11 we have n=1X+32n = \left\lfloor \frac{1}{X} + \frac{3}{2} \right\rfloor. The connection to mm comes in via:

1X4=242m1X=242m4.\frac{1}{X^4} = 24 \cdot 2^m \Longleftrightarrow \frac{1}{X} = \sqrt[4]{24 \cdot 2^m}.

We can establish the upper bound via:

g(1+32X;X)=53716X4+24X3+192X2.g\left(1 + \frac{3}{2} X; X\right) = \frac{537}{16} X^4 + 24 X^3 + \frac{19}{2} X^2.

This quantity is always positive for XX in our domain, which means it is to the right of α(X)\alpha(X) due to the concavity of gg.

3b1b Challenge Question

For the lower bound:

g(1+12X;X)=32116X4+X3+312X24X.g\left(1 + \frac{1}{2} X; X\right) = \frac{321}{16} X^4 + X^3 + \frac{31}{2} X^2 - 4X.

This quantity is negative for X<0.2371X < 0.2371 which first happens when m=4m = 4 and remains negative thereafter:

3b1b Challenge Question

Tighter Bounds

In an attempt to show that there could be no more solutions to the original diophantine equation, I tightened the bounds on α(X)\alpha(X) and explored the behavior. In fact, for m20m \geq 20 we have

242m4+1.46<n<242m4+32\sqrt[4]{24 \cdot 2^m} + 1.46 < n < \sqrt[4]{24 \cdot 2^m} + \frac{3}{2}

which is a very small window of width 0.040.04. I was hoping to show that for large enough mm this window contains no integers,= but unfortunately it appears that the window contains an integer about 4% of the time. Plotting the number of such windows C1.46(m)C_{1.46}(m) against a line with slope 0.040.04:

3b1b Challenge Question

Future Work

Though I didn't get the result I was hoping for, I did have a lot of fun exploring the behavior of roots as mm \longrightarrow \infty. I do think there is more progress to be made in this direction. For example, in order for our expected root to actually be a root, we must have

24(2m1)0mod242m4+32.24 \left(2^m - 1\right) \equiv 0 \bmod{\left\lfloor \sqrt[4]{24 \cdot 2^m} + \frac{3}{2} \right\rfloor}.

but it appears that m=36m = 36 is the last time this is satisfied.

  1. Grant Sanderson, aka 3Blue1Brown is awesome and I highly recommend all of his videos.
  2. I know the last time I wrote about math on this blog it was the same situation, i.e. an offhand comment on a popular YouTube video.
  3. Note that the negative quadratic term in the Taylor series for the root indicates the upper bound.