Archive for the ‘Diophantine’ Category

Sequences 1, Tribonacci numbers

In this 3-part series of posts, we’ll discuss well-known sequences with the recurrence,

aP_{n-3} + bP_{n-2} + cP_{n-1} = P_n

where {a, b, ccan only be zero or unity.  Aside from the Fibonacci and Lucas numbers which is a = 0, there is the Narayana sequence with b = 0, the Padovan and Perrin with c = 0, and the tribonacci has a = b = c = 1.  All four cases may then share similar properties and one of which, interestingly enough, is that their limiting ratios, a root of the following equations,

\begin{aligned}    x^2 &=x+1\\    y^3 &= y^2+1\\    z^3 &= z+1\\    t^3 &= t^2+t+1\end{aligned}

can also be used to express \zeta(3),  or Apery’s constant.

I. Fibonacci and Lucas numbers

Given the two roots of,

x^2=x+1

with x_1 > x_2, the larger root being the golden ratio, we get the Lucas numbers L(n) and Fibonacci numbers F(n),

\begin{aligned}    L_n &= x_1^n+x_2^n = 2,1,3,4,7,11,18,29,\dots\\[2mm]    F_n &= \frac{x_1^n-x_2^n}{\sqrt{5}} = 0,1,1,2,\,3,\,5,\,8,\,13,\dots\end{aligned}

(The starting index is n = 0.)  Expanding powers of the golden ratio, then for n > 0,

\begin{aligned} & {x_1}^n = \Big(\frac{1+\sqrt{5}}{2}\Big)^n = \frac{L_n+F_n\sqrt{5}}{2}\end{aligned}

We’ll see this can be generalized to powers of the tribonacci constant.

II. Tribonacci numbers

These are a generalization of the Fibonacci numbers, being,

t_n = t_{n-1}+t_{n-2}+t_{n-3}

Pin-Yen Lin has a nice paper involving these numbers.  First, define the following three sequences with this recurrence, but with different initial values,

\begin{aligned}S_n &=0,0,1,1,2,4,7,13,24,\dots\\U_n &=0,3,2,5,10,17,32,49,\dots\\V_n &=3,1,3,7,11,21,39,71,\dots \end{aligned}

(The starting index as usual is n = 0.)  The first and the third are recognized by the OEIS, with the first being the tribonacci numbers.  The limiting ratio for all three is the tribonacci constant, T, the real root of,

x^3=x^2+x+1

or,

T = \frac{1}{3}+\frac{1}{3}(19+3\sqrt{33})^{1/3}+\frac{1}{3}(19-3\sqrt{33})^{1/3}

I’ve already written about the tribonacci constant before.  But I want to include how Lin found that powers of x can be expressed in terms of those three sequences. Define,

a =\sqrt[3]{19+3\sqrt{33}}

b =\sqrt[3]{19-3\sqrt{33}}

then, similar to the golden ratio,

T^n = \frac{1}{9}(a^2+b^2)\,S_n+\frac{1}{9}(a+b)\,U_n+\frac{1}{3}\,V_n

Hence, starting with = 1,

T = \frac{0}{9}(a^2+b^2)+\frac{3}{9}(a+b)+\frac{1}{3}

T^2 = \frac{1}{9}(a^2+b^2)+\frac{2}{9}(a+b)+\frac{3}{3}

T^3 = \frac{1}{9}(a^2+b^2)+\frac{5}{9}(a+b)+\frac{7}{3}

and so on.  Interesting, isn’t it, that powers of the tribonacci constant can be expressed in this manner.

Addendum:

There is a primality test regarding Lucas numbers: if n is a prime then L_n-1 is divisible by n.  For example L_5 = 11, minus 1, is divisible by 5.  However there are Lucas pseudoprimes, composite numbers that pass this test, with the smallest being n = 705.

The third tribonacci sequence can be formed analogously to the Lucas numbers.  Given the three roots x_1, x_2, x_3 of,

x^3=x^2+x+1

then, starting with n = 0,

V_n = x_1^n+x_2^n+x_3^n = 3,1,3,7,11,21,39,71,\dots

I notice that likewise, if n is prime, then V_n-1 is divisible by n.  But there are also tribonacci-like pseudoprimes.  The smallest is n = 182.  Steven Stadnicki was nice enough to compute the first 36.  It turns out they are relatively rarer, as there are only 21 less than 10^8, while there are  852 Lucas pseudoprimes in the same range.

Odd powers of Fibonacci numbers

The Fibonacci numbers F_n,

F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots

obey the following recurrence relations,

\begin{aligned}&F_n-F_{n-1}-F_{n-2} = 0\\[1.5mm]&F_n^2-2F_{n-1}^2-2F_{n-2}^2+F_{n-3}^2 = 0\\[1.5mm]&F_n^3-3F_{n-1}^3-6F_{n-2}^3+3F_{n-3}^3+F_{n-4}^3 = 0\\[1.5mm]&F_n^4-5F_{n-1}^4-15F_{n-2}^4+15F_{n-3}^4+5F_{n-4}^4-F_{n-5}^4 = 0\\[1.5mm]&F_n^5-8F_{n-1}^5-40F_{n-2}^5+60F_{n-3}^5+40F_{n-4}^5-8F_{n-5}^5-F_{n-6}^5 = 0\end{aligned}

and so on.  As a number triangle, the coefficients are,

\begin{aligned}    &1;\; \bold{1, -1,-1}=0\\    &2;\; 1, -2, -2, \;1=0\\    &3;\; \bold{1, -3, -6, \;3, \;1}=0\\    &4;\; 1, -5, -15, 15, \;5, \;-1=0\\    &5;\; \bold{1, -8, -40, 60, 40, -8, -1}=0    \end{aligned}

See Ron Knott’s article on the fibonomials, so-called since the above is reminiscent of the binomial triangle.  However, I found another set of recurrence relations can be given as,

\begin{aligned}    &F_{n-1}^2-F_{n+1}^2 = -F_{2n}\\[1.5mm]    &F_{n-1}^3-F_{n}^3-F_{n+1}^3 = -F_{3n}\\[1.5mm]    &F_{n-2}^4+3F_{n-1}^4-3F_{n+1}^4-F_{n+2}^4 = -6F_{4n}\\[1.5mm]    &F_{n-2}^5-3F_{n-1}^5-6F_{n}^5+3F_{n+1}^5+F_{n+2}^5 = 6F_{5n}\\[1.5mm]    &F_{n-3}^6+4F_{n-2}^6-20F_{n-1}^6+20F_{n+1}^6-4F_{n+2}^6-F_{n+3}^6 = -120F_{6n}\\[1.5mm]    &F_{n-3}^7-8F_{n-2}^7-40F_{n-1}^7+60F_{n}^7+40F_{n+1}^7-8F_{n+2}^7-F_{n+3}^7 = -240F_{7n}\\[1.5mm]\end{aligned}

etc.  As a number triangle,

\begin{aligned}    &2;\; 1, -1 =-1\\    &3;\; \bold{1, -1,-1}=-1\\    &4;\; 1, \;\;\;3, -3, \;-1=-6\\    &5;\; \bold{1, -3, -6, \;3, \;\;1}\;=\;6\\    &6;\; 1, \;\;\;4, -20, 20, -4, -1=-120\\    &7;\; \bold{1, -8, -40, 60, 40, -8, -1}=-240    \end{aligned}

Compare the two triangles.  Notice how, for odd powers, the same coefficients appear, though moved up by one odd power.  I have no explanation for the phenomenon, other than the fact that I’ve seen several instances already of a “recycled” polynomial appearing in many contexts.

The equation ap^3+bq^3+cr^3+ds^3 = 0

Theorem 2:  “Likewise, given one non-trivial solution to the cubic,

a_1y_1^3+a_2y_2^3+a_3y_3^3+\dots+a_ny_n^3 = 0

then an infinite more can be found.”

Proof:  As before, we will start with a particular example and derive the rest by induction. The following is identically true,

ax_1^3+bx_2^3+cx_3^3+dx_4^3 = (ay_1^3+by_2^3+cy_3^3+dy_4^3)\,(ay_1^3-by_2^3)^3

where,

\begin{aligned} x_1 &=y_1(ay_1^3+2by_2^3)\\ x_2 &= -y_2(2ay_1^3+by_2^3)\\ x_3 &= y_3(ay_1^3-by_2^3)\\ x_4 &= y_4(ay_1^3-by_2^3) \end{aligned}

Thus, if one has initial {y_1, y_2, y_3, y_4} such that the RHS is zero, this leads to a second, the {x_1, x_2, x_3, x_4}. By iteration, these can be used to generate a third, and so on.  The reason why {x_3, x_4}  have a common factor will be clear in a moment.

This is by A. Desboves, but it is not hard to generalize it to n cubes. The basis is the identity,

\text{(1)}\;\; a(ax^4+2bxy^3)^3 + b(-2ax^3y-by^4)^3 = (ax^3+by^3)(ax^3-by^3)^3

If the first factor of the RHS, ax^3+by^3, can be expressed as a sum of n cubes,

ax^3+by^3 = c_1z_1^3+c_2z_2^3+\dots +c_nz_n^3

it is a simple matter of distributing the second factor of the RHS among the n cubes so that (1) assumes the form,

au_1^3+bu_2^3 = c_1v_1^3+c_2v_2^3+\dots +c_nv_n^3

which explains the common factor of {x_3, x_4} in the 4-cube identity.  Hence from {x, y, z_i}, we get new solutions {u_i, v_i} leading to further solutions, ad infinitum.

There doesn’t seem to be any example of a diagonal quartic surface,

a_1y_1^4+a_2y_2^4+a_3y_3^4+\dots+a_ny_n^4 = 0

which has been proven to have only one non-trivial and primitive integer solution.  Based upon the quadratic and cubic cases, it is tempting to speculate that if it has one, then there may be in fact an infinity.

The equation ap^2+bq^2+cr^2+ds^2 = 0

In the previous post, it was discussed that an initial non-trivial integer solution to the diagonal quartic surface,

ax_1^4+bx_2^4+cx_3^4+dx_4^4 = 0

apparently does not help in determining if the equation has an infinite number of primitive integer solutions.  However, it is different for its quadratic and cubic counterparts.

Theorem 1:  “In general, given one non-trivial solution to the quadratic,

a_1y_1^2+a_2y_2^2+\dots+a_ny_n^2 = 0

then an infinite more can be found.”

Theorem 2:  “Likewise, given one non-trivial solution to the cubic,

a_1y_1^3+a_2y_2^3+\dots+a_ny_n^3 = 0

then an infinite more can be found.”

Proof of Theorem 1  (Theorem 2 will be discussed in the next post):

We’ll start with n = 3,4 and prove the rest by induction. There is the identity,

ax_1^2+bx_2^2+cx_3^2 = (ay_1^2+by_2^2+cy_3^2)\,(az_1^2+bz_2^2+cz_3^2)^2

where,

(x_1, x_2, x_3) = (uy_1-vz_1, uy_2-vz_2, uy_3-vz_3)

and,

(u,v) = (az_1^2+bz_2^2+cz_3^2,\, 2(ay_1z_1+by_2z_2+cy_3z_3)\,)

Thus, if one has an initial solution (y_1, y_2, y_3), then the RHS of the identity becomes zero, and one gets a parametrization in the (x_1, x_2, x_3) for three free variables (z_1, z_2, z_3). An example is given in this page, form 2b.  For n = 4, it is just a generalization,

ax_1^2+bx_2^2+cx_3^2+dx_4^2 = (ay_1^2+by_2^2+cy_3^2+dy_4^2)(az_1^2+bz_2^2+cz_3^2+dz_4^2)^2

where,

(x_1, x_2, x_3, x_4) = (uy_1-vz_1, uy_2-vz_2, uy_3-vz_3, uy_4-vz_4)

and,

(u,v) = (az_1^2+bz_2^2+cz_3^2+dz_4^2,\, 2(ay_1z_1+by_2z_2+cy_3z_3+dy_4z_4)\,)

The pattern is easily seen for n = 5,6, ad infinitum.  If only it was that easy for the quartic case.

A Fermat’s Last Theorem near-miss

By Fermat’s Last Theorem, the quartic equation,

x^4+y^4 = z^4

has no non-trivial rational solutions.  In fact, the same can be said for the less strict,

x^4+y^4 = z^2

So how do we explain the near-equalities,

24576^4+48767^4 \approx (49535.000000000006\dots)^4

419904^4 + 1257767^4 \approx (126155.000000000000001\dots)^4

A search for others with z < 8,000,000 will not yield better approximations.  Noam Elkies showed that an identity is behind it, namely,

(192v^8-24v^4-1)^4+ (192v^7)^4= (192v^8+24v^4-1)^4+12(2v)^4

Since the second term on the RHS is small compared to the others, this gives an excellent near-miss to Fermat’s Last Theorem.  Inspired by Elkies’ quartic identity, Seiji Tomita found similar ones as,

(48v^8-12v^4-1)^4 + 2(48v^7)^4 = (48v^8+12v^4-1)^4 + 6(2v)^4

(12v^8-6v^4-1)^4 + 4(12v^7)^4 = (12v^8+6v^4-1)^4 + 3(2v)^4

It can be shown all three belong to the same family.  For arbitrary m let,

b = \frac{8}{m},\;\; d = \frac{3m}{2}

then,

(3m^2 v^8-3m v^4-1)^4+b(3m^2 v^7)^4=(3m^2v^8+3mv^4-1)^4+d(2v)^4

Note that,

bd = 12

In general, these are diagonal quartic surfaces of form,

ax^4+by^4 = cz^4+dt^4

The case {a, b, c, d} = {1, 2, 1, 4}, or the Swinnerton-Dyer quartic surface, was discussed in the previous post and, in the link above, Elsenhans gives first-known but large solutions to other positive {a, b, c, d}.  From Elkies’ and Tomita’s results, it is tempting to speculate that if,

x^4+2y^4 = z^4+4t^4

has a non-trivial solution, then does

x^4+y^4 = z^4+8t^4

have one as well?  Unfortunately, this particular form does not seem to be in Elsenhans’ list.  (For positive {a, b, c, d}, the only other case I know of that has an infinite number of solutions is a = b = c = d = 1.)

The Swinnerton-Dyer quartic surface

Does the Diophantine equation,

\text{(1)}\,\,\, a^4+2b^4=c^4+4d^4

first suggested by Swinnerton-Dyer, only have a finite number of primitive solutions? Note that, by Sophie Germain’s identity, the RHS factors as,

c^4+4d^4 = \big((c+d)^2+d^2\big)\big((c-d)^2+d^2\big) = (c^2+2cd+d^2)(c^2-2cd+d^2)

Before discussing (1), we can compare it to other quartic Diophantine equations.  Any primitive integral solution to,

\text{(2)}\,\,\, a^4+b^4+c^4+d^4 = e^4

must obey the congruential constraint that there is an addend such that either {d^2+e^2,\, d^2-e^2} is divisible by 5^4.  The smallest was found by Norrie in 1911 as,

(a,b,c,d,e) = (30, 120, 315, 272, 352)

and indeed,

\begin{aligned}d+e &= 272+353 = 5^4\\ -d+e &= -272+353 = 3^4 \end{aligned}

On the other hand, for,

\text{(3)}\,\,\, a^4+b^4+c^4 = d^4

Morgan Ward proved the added constraint that either {c+d, -c+d} is divisible by 2^{10}. The smallest was found by Roger Frye in 1988,

(a,b,c,d) = (95800, 414560, 217519, 422481)

and we can see that,

c+d = 217519+422481 = 2^{10}\, 5^4

Going back to the Swinnerton-Dyer equation, the only solution less than a hundred million (10^7) is,

(a,b,c,d) = (1484801, 1203120, 1169407, 1157520)

found by A. Elsenhans and J. Jahnel in 2004.  On a hunch, I decided to test the values and found that,

a+c = 1484801+1169407 = 2^{15}\,3^4

I don’t know if this is a general congruence valid to all primitive solutions of (1), and an email to the authors revealed neither did they.  In fact, to quote their paper, “... it is unknown whether this equation admits finitely or infinitely many primitive solutions. If their number were actually finite then this would settle a famous open problem in the arithmetic of K3 surfaces…

So many questions, so little time.