Posts Tagged ‘diophantine’

Sequences 2, Padovan and Perrin numbers

III. Padovan sequence

Just like the golden ratio and tribonacci constant, powers of the plastic constant P can also be expressed in terms of sequences associated with it. P is a root of the equation,

P^3=P+1

or,

P = \frac{1}{3}\left(\frac{27+3\sqrt{69}}{2}\right)^{1/3}+\frac{1}{3}\left(\frac{27-3\sqrt{69}}{2}\right)^{1/3}

Define,

\begin{aligned}    a & = \left(\tfrac{27+3\sqrt{69}}{2}\right)^{1/3}\\b&=\left(\tfrac{27-3\sqrt{69}}{2}\right)^{1/3}\end{aligned}

then powers of P  are,

P^{n} = \frac{1}{9}(a^2+b^2)U_{n+1}+\frac{1}{3}(a+b)U_{n+2}+\frac{1}{3}V_n

where U and V are the Padovan and Perrin sequences, respectively,

\begin{aligned} U_n &= 1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16\dots\\    V_n &=3,0,2,3,2,5,5,7,10,12,17,22,29,\dots\end{aligned}

which start with index n = 0.  Hence,

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

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

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

and so on.  These sequences obey,

W_n = W_{n-2} + W_{n-3}

and their limiting ratio, of course, is P.  While the Fibonacci sequence has a nice representation as a square spiral, the Padovan is a spiral of equilateral triangles,

The Perrin sequence also has a notable feature regarding primality testing.  Let x_1, x_2, x_3 be the roots of,

P^3=P+1

then, starting with n = 0,

V_n=x_1^n+x_2^n+x_3^n = 3,0,2,3,2,5,5,7,10,12,17,22,29,\dots

Indexed in this manner, if n is prime, then n divides V_n.  For example V_{11} = 22.  However, there are Perrin pseudoprimes, composite numbers that pass this test, with the smallest being n = 521^2.

Lastly, like all the four limiting ratios of this family of recurrences, the plastic constant P  can be expressed in terms of the Dedekind eta function as,

\begin{aligned} P &=\frac{e^{\pi i/24}\,\eta(\tau) }{\sqrt{2}\,\eta(2\tau)}\end{aligned}

where,

\tau=\frac{1+\sqrt{-23}}{2}

Even powers of Fibonacci numbers

In a previous post, it was pointed out that powers of Fibonacci numbers also obey recurrence relations.  For example, it is the case that,

F_n^2-2F_{n+1}^2-2F_{n+2}^2+F_{n+3}^2 = 0

In general, for even kth powers, it takes k+2 consecutive Fibonacci numbers to sum up to zero.  However, using Mathematica’s LatticeReduce function which has an integer relations algorithm, I found that if reduced to k+1 terms, then it can still sum up to a constant, though it is now non-zero.  Thus,

\begin{aligned}    &F_n^2-3F_{n+1}^2+F_{n+2}^2 = (-1)^{n+1}\,2\\[1.5mm]    &F_n^4-4F_{n+1}^4-19F_{n+2}^4-4F_{n+3}^4+F_{n+4}^4 = 6\\[1.5mm]    &F_n^6-14F_{n+1}^6-90F_{n+2}^6+350F_{n+3}^6-90F_{n+4}^6-14F_{n+5}^6+F_{n+6}^6 = (-1)^n\, 80\\[1.5mm]    &F_n^8-33F_{n+1}^8-747F_{n+2}^8+3894F_{n+3}^8+16270F_{n+4}^8+3894F_{n+5}^8-747F_{n+6}^8\\&\;\;-33F_{n+7}^8+F_{n+8}^8 = 2520\end{aligned}

and so on, with k = 10 summing to (-1)^{n+1}\,226800.  Notice the formulas are palindromic, the same read forwards or backwards.

I was curious if this sequence of constants,

C(2p) = 2, 6, 80, 2520, 226800, \dots

had a generating function. Unfortunately, OEIS didn’t recognize it, so that question is unanswered for now.

Update, May 26, 2012:  Jim Cullen found a recurrence relation which is equivalent to the formula,

\begin{aligned}C(2p)&=\prod_{n=1}^p \frac{2(2n-1)(F(n))^2}{n}=\frac{(2p)!}{p!^2}\prod_{n=1}^p (F(n))^2\\&=2,6,80, 2520, 226800,53222400,\dots\end{aligned}

hence the next constant is(12) = 53222400.  The product of the first p Fibonacci numbers (n) is called a fibonorial.

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.

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.