# How many sequences of rational squares are there, all of whose differences are also rational squares?

After commenting on a question of Joseph O'Rourke's, I thought it interesting that a number theory result (artihmetic progressions of rational squares cannot be arbitrarily long) had applications to geometry (don't look at mostly regular cones of regular hypercubes for totally rational polytopes). (I hope I got the above right and that it is indeed an application; I proceed on that basis.) Of course I am also impressed by the fact that there is no known geometric proof of the fact that finite geometries satisfy both or neither of the configurations of Pappus and of Desargues. So of course, a natural question would be to consider applications of number theory to geometry; I'm not going to do that here. Instead, I will ask for assistance with Joseph's program by asking a question about rational squares.

The first question that occurred to me was " (1) Is there a sequence of integer squares whose differences are also integral squares?" For sake of interest I require all squares to be nonzero, though later they may be rational and not just integral.

Before posting this question, I saw the answer was yes, and that indeed there were at least countably many such sequences, although I don't know if there are infinitely many tails. So I nominate question first':

(1') How many infinite sequences of integer squares are there, all of whose first differences are also integer squares?

There is the potential to be uncountably many such, especially if there are (is?) an uncountable infinity of tails. But wait! There's more!

(2) Fix an integer $k$ with $k > 1$. How many infinite sequences of integer squares are there, all of whose first through $k$th differences are also integer squares?

Recall that for a sequence $a_i$, the first difference is the sequence $b_i = a_{i+1} - a_i$, and the $(k+1)$st difference is the first difference of the $k$th difference. I suspect that for $k$ large enough, the answer will be zero. However, those are just warm ups for this question:

(3) How many sequences of rational squares are there such that for every positive integer $k$ all $k$th differences are also rational squares?

Motivation: I think it is a cool set of questions. Also I think that if Joseph is going to get a family of rational polytopes of arbitrarily high dimension, he will find such sequences useful (I am thinking volume of a pyramid being base times height times some rational number in combination with a multidimensional Pythagorean-type expression), and that such a family will imply the existence of such sequences, but I do not see the converse as the polytopes have to satisfy additional relations. As usual, reference requests and related problems are welcome.

-
It occurs to me that projections of rational polytopes may give point sets all of whose distances are rational (or maybe not). So Joseph might be asking a question that is harder than this one and is open (and not just in the sense of Gerry Myerson's response to Joseph's question). (Also, Euler bricks may be related.) Gerhard "Ask Me About System Design" Paseman, 2011.08.03 –  Gerhard Paseman Aug 3 '11 at 21:22
Hi, Gerhard. I will need to read this more carefully later. It is worth mentioning that there are no infinite sets of points in the plane at integral (pairwise) distances from each other. This goes back to about 1950, a fairly long article, then in preparing a review Kaplansky discussed the matter with Erdos and they came up with a short elementary proof then and there, using hyperbolas. In order to get large finite sets, essentially take one point off a line, such that the perpendicular dropped to the line is the short leg of a large number of Pythagorean right triangles. –  Will Jagy Aug 3 '11 at 21:58
Yes. I believe there are also large numbers arranged on a circle. However, sometimes projections will carry rational length edges to irrational length edges, so maybe projections is not that big a worry. Gerhard "Ask Me About System Design" Paseman, 2011.08.03 –  Gerhard Paseman Aug 3 '11 at 22:28
Firing @Will, of course there are infinite sets of points in the plane at integral pairwise distances from each other - you forgot to rule out having all the points lie on a line. –  Gerry Myerson Aug 3 '11 at 23:57
Gerhard, do you have even one (non-constant) sequence of squares whose first and second differences are all squares? –  Gerry Myerson Aug 4 '11 at 0:18

I was in the process of writing up a "proof" (modulo a conjecture on primes) almost identical to Gjergji Zaimi's when his answer arrived. Thank goodness I didn't have to finish, because examining the slight difference in our approaches made me realize how to get around the conjecture.

To simplify things, let $a_0,\ a_1,\ a_2, \ldots$ be a sequence of odd numbers whose squares have square difference, such as

$$5,\ 13,\ 85,\ 157,\ 12325,\ldots$$ or $$5,\ 13,\ 85,\ 3613,\ 6526885,\ldots$$

Note that the sequence starting at 5 splits into two sequences at 85.

Now factor $12325 = 5b$ with $b=2465$ and continue the first sequence as

$$5,\ 13,\ 85,\ 157,\ 5b,\ 13b,\ 85b,\ 157b, \ 12325b,\ldots$$

or

$$5,\ 13,\ 85,\ 157,\ 5b,\ 13b,\ 85b,\ 3613b,\ 6526885b,\ldots$$

Likewise factor $6526885 = 5B$ with $B= 1305377$ and continue the second sequences as

$$5,\ 13,\ 85,\ 3613,\ 5B,\ 13B,\ 85B,\ 157B,\ 12325B,\ldots$$ or

$$5,\ 13,\ 85,\ 3613,\ 5B,\ 13B,\ 85B,\ 3613B,\ 6526885B,\ldots$$

The point is, starting from any multiple of 5, we reach (in two steps) a multiple of a number (it happens to be 85), from which there are two branches, each of which reaches another multiple of 5. So there's guaranteed to be an infinite binary tree, and hence there are uncountably many sequences of square integers whose first differences are square.

I'm sorry if this is somewhat clumsily explained. Maybe someone can clean it up.

-
Ah! +1, that's very clever! –  Gjergji Zaimi Aug 4 '11 at 4:07
I guess the hard problem then is what happens if one restricts the sequences not to have elements divisible by a specific set of primes, will the answer still be uncountable? –  Gjergji Zaimi Aug 4 '11 at 4:10

I suppose there are infinitely many infinite sequences of integer squares, all of whose first differences are also integer squares. Here is an attempt at constructive proof.

Suppose you have the sequence up to $a_n$ and wish to extend it. Write $a_n$ as a difference of squares (it is a square): $a_n = a^2 = (\frac{\frac{a_n}{d}+d}{2})^2 - (\frac{\frac{a_n}{d}-d}{2})^2, d \mid a_n$. Setting $a_{n+1}=(\frac{\frac{a_n}{d}+d}{2})^2$ and $a_{n+1}-a_n=(\frac{\frac{a_n}{d}-d}{2})^2$ will extend the sequence as long as it is an integer. To force it being an integer, one can insist that $a_n = 16 u^2$ with $u$ odd and take $d=4, \frac{a_n}{d}=4 u^2$ (avoiding factorization) leading to $\frac{\frac{a_n}{d}+d}{2} \equiv 0 \mod 4$ and the square again of the form $16u^2$ with $u$ odd (this follows from examining $(\frac{4+4(2x+1)^2}{2})^2 \mod 32$). So start from $a_1=16 u^2$ and extend the sequence.

After simplification, $a_{n+1}=(\frac{4+\frac{a_n}{4}}{2})^2$ and $a_1=16 u^2$, $u > 1$ odd.

Starting with $a_1= 16 \cdot 5^2$ I get:

400, 2704, 115600, 208860304, 681603644851600, 7259117635546998039104028304, 823356075729834991394377343895101538985808607052531600, 10592425428769277708701964508444107521120841773208159861878488881058295592932634035770367240431209291868304

EDIT: About rational squares whose all k-th differences are square.

Set $a=\frac{p}{q}, p^2-q^2=u^2$

Let $a_n=a^{2n}$. All kth differences are of the form $(a^2-1)^k a^{2s}$ and $(a^2-1)$ is a square by the choice of $p,q$.

EDIT2 A possible approach to get square first and second differences of rational squares is to use the above construction and try to insert a term at the beginning (to get rid of the geometric progression). Solving symbolically leads to rational points on an elliptic curve and if it is of positive rank this will give infinitely many new solutions. For $a=\frac{5}{4}$ the first term of $(\frac{1595}{1924})^2$ was found. This might be a counter example to Gjergji Zaimi's conjecture about similar triangles (in the comments).

-
It might be better to say $k$th differences are of the form $(a^2 -1)^k a^{2s}$. I do like the construction though. This gives countably many such sequences; is there a way to tweak the exponents to get uncountably many? Gerhard "Ask Me About System Design" Paseman, 2011.08.04 –  Gerhard Paseman Aug 5 '11 at 6:55
Thank you Gerhard! Will address your comment. As a side effect the second construction appears to give arbitrary long finite integer sequences whose all k-th differences are squares. –  joro Aug 5 '11 at 8:49

Here is an attempt at a cleaner exposition for problem (1');  although I take full credit/blame for the exposition, it is based on ideas posted by Barry Cipra, Gjergji Zaimi, and joro.

Let me define S, also known as the square sequence graph.  The vertices will be all positive integers which are squares of integers greater than 2, and edges will be directed: $(a,b)$ will be an edge from $a$ to $b$ iff the quantity $b-a$ is the square of a positive integer.  Paths through S will thus be monotonically increasing.

S has many vertices with out degree at least 2.  Indeed, if $d$ is not the square of a prime the square of either an odd composite number or of a number with at least three not necessarily distinct prime divisors (thanks to Gerry Myerson for an earlier counterexample), it has at least two factorizations of the form $mn$ where $m-n$ is even and positive, and each such factorization leads to an arrow from $d$ to $((m+n)/2)^2$.  Further, considerations mod 4 show that odd squares can only have arrows to other odd squares in S.

Each infinite sequence in the question (1') corresponds to a path through S.  Barry Cipra suggested how to find uncountably many such paths.  Let $d$ be any vertex in S which is 9 mod 10, and $d > 10$. There is an arrow from $d$ to $c = ((d + 1)/2)^2$.  This is a number which is an odd nontrivial multiple of 5 as well as being a square, and has two or more arrows leading from it.  One of the arrows from $c$ leads to a still larger square $((c+1)/2)^2$ which is 9 mod 10.  Another leads to a different square (corresponding to a factorization where $m = c/5$ and $n = 5$) which leads to another square which is 5 mod 10.

Any path which starts out with a large square mod 5 has a choice of passing through an infinite number of other squares mod 5, where after each such square, the path may go to a square which is 9 mod 10 before going to a square which is 5 mod 10.  Since this subset of paths is determined by which subset of these countably infinite set of choices to make, Barry has shown us a subset which has a bijection (thanks, Gjergji) with a set of infinite binary sequences.  In the set theory that I like doing this, this means there are at least continuum many such sequences.

I invite others to play with S and find out properties of infinite sequences of squares with square first differences.

The related graph R using rational squares holds promise also.  It may be possible to use S to show that for $k=2$, the answer to question (2) is 0, which is my intuition.  It should be clear that all (with at most one exception) of the kth differences of an integral square sequence must be even for them to be all integral squares.

$d=36$ is not the square of a prime, but it has only one factorization $36=mn$ with $m-n$ even and positive. –  Gerry Myerson Aug 5 '11 at 5:36