%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-9/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{thrm}{Theorem}[section]

\title{Progressions of Squares}
\author{
\renewcommand{\thefootnote}{\arabic{footnote}}
Tom C. Brown\footnotemark[1], Allen R. Freedman\footnotemark[2], and Peter Jau-Shyong Shiue\footnotemark[2]}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, A.R. Freedman, and P.~J.-S. Shiue, \emph{Progressions of squares},
  Australas. J. Combin. \textbf{27} (2004), 187--192.}\bigskip\end{center}

\footnotetext[1]{\parbox{\textwidth}{Department of Mathematics, ¶¡ÏãÔ°AV,
Burnaby, BC, Canada V6G 1G4\\\texttt{tbrown@sfu.ca}, \texttt{allen@mathways.com}}\\~\\}
\footnotetext[2]{\parbox{\textwidth}{Department of Mathematical Sciences, University of Nevada, Las Vegas, Nevada USA 89154-4020\\\texttt{shiue@nevada.edu}}}



\begin{abstract}Some generalizations of arithmetic progressions are:
quasi-progressions, combinatorial progressions, semi-progressions, and
descending waves. (The definitions are given below.) We study the occurrence
of these progressions in the set of squares of integers.
\end{abstract}

%\bigskip %this is a hack to force the references to their own page

\section{Introduction}

It is well known that there is no four-term arithmetic progression (AP)
consisting of squares. We have not found a really lucid demonstration of
this fact (first proved by Fermat), but one can work through the proof in
Chapter 4 of \cite{mordell1969}. However, three-term arithmetic progressions occur
in abundance among the squares: take any Pythagorean triple, $a^2 + b^2 =
c^2$; then $(b-a)^2,c^2,(b+a)^2$ is clearly a 3-term AP with common difference
$2ab$. It's also easy to show that every 3-term AP of squares has this form.

In \cite{brown+erdos+freedman1990} and \cite{ding+freedman1996} several
generalizations of arithmetic progressions have been introduced and their
properties investigated. For instance, since $(n+1)^2/n^2\to1$, Corollary 4,
page 94 of \cite{brown+erdos+freedman1990} shows that the set of squares
contains arbitrarily long \emph{descending waves}. A descending wave is a
set $\{a_1,a_2,\ldots,a_n\}$ such that $a_{j+1}-a_j\geq a_{j+1}-a_{j+1}$,
$1\leq j\leq n - 2$.

Thus the problems concerning the existence of long progressions in the set of
squares is completely solved for APs and descending waves.

For other types of progressions studied in the above mentioned papers
(quasi-progressions (QP), combinatorial progressions (CP) and semi-progressions
(SP)) very little is known about the existence or non-existence of long
progressions of these types among the squares.

In this note we relate what we have found regarding APs, QPs, CPs and SPs
occurring in the set of squares. We give the definitions as we go along, and we
use some notation consistent with \cite{brown+erdos+freedman1990} and
\cite{ding+freedman1996}.

\section{Arithmetic Progressions and Combinatorial Progressions}

In Theorem \ref{shuckburgh} below, an $n$-CP$\left(\frac{n-1}{2}\right)$ is a
set $\{b_1,b_2,\ldots,b_n\}$ such that $|\{b_2-b_1,b_3-b_2,\ldots,b_n-b_{n-1}\}|
\leq (n-1)/2$.

Consider the sequence $\{a_n\} = \{1,5,7,13,17,25,\ldots\}$ where $a_n$ is
defined by
\[ a_n = \left\{ \begin{array}{cr}
\frac{(n+1)^2-2}2, &\text{ if $n$ is odd} \\
\frac{(n+1)^2+1}2, &\text{ if $n$ is even}
\end{array}\right. \]
A simple calculation shows that, if $n$ is odd, then $(a_n)^2$, $(a_{n+1})^2$,
$(a_{n+2})^2$ is a 3-term AP of squares with common difference = $(n+1)(n+2)
(n+3)$. Using this we get the following result concerning combinatorial
progressions.

\begin{thrm} For each odd $n\geq1$ there exists an $n$-CP$\left(\frac{n-1}{2}\right)$
among the squares.\label{shuckburgh}\end{thrm}
\begin{proof} Using the first $n$ terms of the sequence $\{a_n\} = \{1,5,7,13,17,
25,\ldots\}$ defined above, the sequence of $n-1$ differences of $a_1^2,a_2^2,a_3^2,
\ldots,a_n^2$ is $24,24,120,120,336,336,\ldots,N,N$ where $N = (n-1)(n)(n + 1)$. Here,
the number of distinct differences is, clearly, $(n-1)/2$.\end{proof}
% NOTE the ldots above was a capital K in Tom's paper -- assuming typo

Hence, the set of squares contains arbitrarily long progressions, $P$, with the
property
\[ \frac{\textnormal{cardinality of the difference set of $P$}}{\textnormal{length
of $P$}} < \frac12 \]

We do not know whether or not the value 1/2 in this statement can be improved.
Also, this result can be compared with that of Theorem \ref{antarctic} below.

Another proof of Theorem \ref{shuckburgh} can be obtained from the sequence $\{g_n\}$
formed as follows: We start with $g_1=1$, $g_2=a^2$, $g_3=b^2$, where $1,a^2,b^2$ is
a 3-term AP. (The smallest such 3-term AP is 1,25,49. The most general 3-term AP of
this form is $1,a^2,b^2$, where $b/a$ is any even convergent of the simple continued
fraction of $\sqrt2$ --- see below.) Then we define $g_i = b^{i-1}$ if $i$ is odd and
$g_i = a^2b^{i-2}$ if $i$ is even. The sequence $\{g_n\}$ has similar properties to
those of $\{a_n\}$.

In passing we note two interesting facts regarding APs in the squares.

The first is that the even terms of the sequence $\{a_n\}$ above are exactly the
hypotenuses of all the Pythagorean triples of the form $A^2+B^2=(B+1)^2$.

(\emph{Proof.} This equation holds if and only if $B+1 = (A^2+1)/2$. Thus $A$ must
be odd ($=2k+1$) and so $B+1=a_{2k}$.)

The second fact is this: $1,a^2,b^2$ (where $a>0$, $b>0$) is a 3-term AP if and only
if $b/a$ is an even convergent of the simple continued fraction of $\sqrt2$.

(\emph{Proof.} If $1,a^2,b^2$ is a 3-term AP, then $1+b^2=2a^2$, which gives $2-b^2/a^2
= 1/a^2$ or $(\sqrt2 - b/a)(\sqrt2 + b/a) = 1/a^2$. Thus
\[ 0 < \sqrt2 - \frac{b}a = \frac1{(\sqrt2 + b/a)a^2} < \frac1{2a^2} \]
which yields the result. (See \cite{niven+zuckerman+montgomery1991}.) One can
also prove this starting with the equation $b - 2a^2 = -1$. For the converse,
one easily shows by induction on $n$ that if $p_{2n}/q_{2n}$ is the $(2n)$th
convergent of the simple continued fraction of $\sqrt2$, then $1,q_{2n}^2,
p_{2n}^2$ is a 3-term AP.)

\section{Quasi-Progressions}

We now turn our attention to quasi-progressions of squares. While no 4-AP of
squares exists, we can nevertheless construct infinitely many 4-term
\emph{quasi-progressions} of squares each with \emph{diameter 1}. That is,
sequences $a^2 < b^2 < c^2 < d^2$ where the difference set $\{b^2 - a^2, c^2
- b^2, d^2 - c^2\} = \{D,D+1\}$ for some $D$. Such a sequence is called a
4-QP(1).

\begin{thrm}There are infinitely many 4-QP(1)'s among the squares.\end{thrm}
\begin{proof} Let $(a,b,c)$ be any Pythagorean triple. Recall that $(b-a)^2,
c^2,(b+a)^2$ is a 3-term AP. We note that $(b+a)^2+2ab$ is not a square lest
we get the 4-AP of squares $(b-a)^2,c^2,(b+a)^2,(b+a)^2+2ab$. Let $(x,y)$ be
any one of the infinitely many solutions to the Pellian equation
\[ x^2 - \left[(b + a)^2 + 2ab\right]y^2 = 1 \]
Then $(b-a)^2,y^2,c^2y^2,(b+a)^2y^2,x^2$ is a 4-QP(1) since the first two
differences are $2aby^2$ and the last difference is
\begin{align*}
x^2 - (b+a)^2y^2
&= \left[(b + a)^2 + 2ab\right]y^2 + 1 - (b+a)^2y^2 \\
&= 2aby^2 + 1
\end{align*}
\end{proof}

Similar 4-QP(1)'s, where the third difference is one less than the first two
differences, may be found in the same way from solutions to the equation $x^2
- \left[(b + a)^2 + 2ab\right]y^2 = -1$ when they exist. Furthermore, the
$x^2$ may be made the first term of the 4-progression when $(x,y)$ is a
solution to $x^2 - \left[(b - a)^2 - 2ab\right]y^2 = \pm1$ (provided $(b-a)^2
>2ab$).

The simplest example: take the Pythagorean triple $(3,4,5)$. Then $(b+a)^2+2ab
= 73$ and a solution to $x^2-73y^2 = -1$ is $x = 1068$, $y = 125$. The 4-QP(1)
produced is $125^2, (5\cdot125)^2,(7\cdot125)^2,1068^2$ with difference
sequence $24\cdot125^2,24\cdot125^2,24\cdot125^2-1$.

Examples with very large numbers are also easy to produce provided you can solve
the Pellian equation. In fact, most 4-QP(1)'s in the squares consist of very
large numbers.

We do not know whether or not there exists any 5-QP(1) among the squares. In
fact, we have no found a 5-QP(5) among the squares. Here is a 5-term progression
of squares with small difference set diameter: $1^2,41^2,58^2,71^2,82^2$. The
differences are 1680, 1683, 1677, 1683 so the progression is a 5-QP(6). Another
5-QP(6) is: $10^2,25^2,34^2,41^2,47^2$. Although these examples are curious,
they are not very significant in the present context since it happens that any
progression of five consecutive squares is a 5-QP(6).

We offer the following conjecture: for each $K\geq0$, there is an $N$ such
that any $n$-progression of squares, with $n\geq N$, is not an $n$-QP($K$).
(For $K=0$, we have $N=4$, but this is all we know.)

\section{Semi-progressions}

For a given function $g$, an $n$-SP($g$) is a set $\{b_1,b_2,\ldots,b_n\}$ such
that the diameter of the set $\{b_2-b_1,b_3-b_2,\ldots,b_n-b_{n-1}\}$ is less
than or equal to $g(n)$. If a set $X$ contains $n$-SP($g$)'s for arbitrarily
large $n$, we say that $X$ has \emph{property} SP($g$).

We remark that, if $g(k)$ is bounded above by a polynomial, property SP($g$)
is stronger than the property of containing arbitrarily long descending waves.
(See \cite{ding+freedman1996}.)

As was remarked in \cite{ding+freedman1996}, the set of squares has property
SP($2n$). (Just consider the progression consisting of the first $n$ squares.
The diameter of the difference sequence is $\left(n^2 - (n-1)^2\right)-\left(2^2 - 1^2\right)
=2n-4 < 2n$.)

Our purpose here is to improve this result by replacing $2n$ with $(3/2)n$.

\begin{thrm} The set of squares has property SP($(3/2)n$). \label{antarctic}\end{thrm}
\begin{proof} We wish to prove that there are arbitrarily long progressions of
squares $a_1^2<a_2^2<a_3^2<\cdots<a_n^2$ such that the diameter of the difference
% This cdots was a capital L... I'm sure this is a typo, or maybe a glitch in the PDF
set, $D = \max\{a_{i+1}^2 - a_i^2\} - \min\{a_{i+1}^2 - a_i^2\}$, does not exceed
$(3/2)n$. In other words $(D/n) \leq (3/2)$.

We will refer to a positive integer $a$ as the \emph{base} of the square $a^2$.
Let $K$ be a positive integer and let $A = 2^K$. We construct the following
progression, $B$, squares: The progression $B$ will be the union of the $K+1$
blocks of squares $B_0,B_1,\ldots,B_K$ where
\begin{align*}
B_0 &= \left\{ (2A)^2 \right\} \\
B_1 &= \left\{ \left(2A + \frac{A}2\right)^2, \left(2A + 2\frac{A}2\right)^2,
\left(2A + 3\frac{A}2\right)^2, \left(2A + 4\frac{A}2\right)^2 \right\} \\
&\vdots \\
B_i &= \left\{ \left(2^iA+\frac{A}{2^i}\right)^2, \left(2^iA+2\frac{A}{2^i}\right)^2,
\left(2^iA+3\frac{A}{2^i}\right)^2, \ldots,
\left(2^iA+4^i\frac{A}{2^i}\right)^2 \right\} \\
&\vdots \\
B_K &= \left\{ \left(2^KA + 1\right)^2, \left(2^KA + 2\right)^2,
\left(2^KA + 3\right)^2, \ldots, \left(2^KA + 4^K\right)^2 \right\}
\end{align*}
% all the dots above were fucked up in Tom's PDF
We observe that $|B_i| = 4^i$ for $0\leq i\leq K$. Hence the progression $B$ has
length
\[ n = 1 + 4 + 4^2 + \cdots + 4^K = \frac13\left(4^{K+1} - 1 \right). \]
% ditto here
Also note that the base of the last term of $B_i$ is $2^{i+1}A$. Since the bases
of the squares, starting from the last term of a given block and continuing
through all the terms of the next block, increase by a constant amount ($=A/2^i$
in block $B_i$), the difference sequence of the squares is increasing for these
terms. In order to calculate the diameter of the difference set, we need only
check the $K$ largest differences (which occur between the last two terms of the
blocks) and the $K$ smallest differences (which occur between the last term of
a block and the first term of the succeeding block). Finding the largest and
smallest among these differences will produce our $D$. The largest difference
in block $B_i$ is
%\[ \left( 2^{i+1}A + \frac{A}{2^{i+1}}\right)^2 - \left(2^{i+1}A\right)^2 =
% \frac{A}{2^{i+1}}\left(2^{i+2}A + \frac{A}{2^{i+1}}\right) =
% 2A^2 + \frac{A^2}{4^{i+1}}, \]
\[ \left(2^{i+1}A\right)^2 - \left(2^{i+1}A - \frac{A}{2^i}\right)^2 = \frac{A}{2^i}\left(2^{i+2}A - \frac{A}{2^i}\right) = 4A^2 - \frac{A^2}{4^i}, \]
and the maximum of these occurs when $i = K$ and is equal to $4A^2 - 1 = H$. The
difference from the last term of $B_{i+1}$ is
\[ \left( 2^{i+1}A + \frac{A}{2^{i+1}}\right)^2 - \left(2^{i+1}A\right)^2 =
\frac{A}{2^{i+1}}\left(2^{i+2}A + \frac{A}{2^{i+1}}\right) =
2A^2 + \frac{A^2}{4^{i+1}}, \]
and the minimum of these occurs at $i+1 = K$ with value $2A^2 + 1 = L$. Hence
\[ D = H - L = 2A^2 - 2 = 2^{2K+1} - 2 \]
and, finally, our last calculation completes the proof:
\[ \frac{D}{n} = \frac{2^{2K+1}-2}{\frac13(4^{K+1}-1)}
= \frac{3\left(1 - \frac1{2^{2K}}\right)}{2\left(1-\frac1{2^{2K+2}}\right)} < \frac32 \]

We do not know whether or not this theorem is best possible. Perhaps the set
of squares possesses property SP$((1 + \epsilon)n)$ for every $\epsilon>0$,
or even property SP$(n)$.
\end{proof}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}