\input{defines.tex}
\documentstyle{article}

\title{Quadratic Forms, Pythagorean Triples, and the Equation
  ${\displaystyle \sum} x^{k} = \left({\displaystyle \sum} x\right)^{2}$}
\author{Cordelia Aitkin \and Thomas Colthurst \and Kathryn Kollett 
	\and Steven Levandosky \and Andrew Perry \and Eugene Stern }

\begin{document}
\maketitle

\section{Introduction and Definitions}
Whether learning or teaching induction, you've probably noticed that
the formula for the sum of the first $n$ cubes is the square of the formula
for the sum of the first $n$ integers.  In other words,
the elements of the set $\{1,2,\ldots ,n\}$ satisfy
the relation
\begin{equation}
x_1^3+x_2^3+\cdots +x_n^3=(x_1+x_2+\cdots +x_n)^2.
\label{eq:scube}
\end{equation}
Other solutions of this equation include the following:
\begin{itemize}
\item The multiset $ \{ \overbrace{n,n,\ldots ,n}^{n {\rm \: times}} \} $,
where $n$ is any positive integer.
\item Let $m$ be a positive integer, let $c_1, \ldots ,c_n$ be its
divisors, and let $d(x)$ be the number of divisors of $x$.  Then the multiset
\[ \{d(c_1),d(c_2),\ldots ,d(c_n) \} \]
is a solution of the equation.  For example, if $m=6$, its divisors are
1,2,3, and 6, so we obtain $\{1,2,2,4\}$, which satisfies the identity.
\end{itemize}

In this note we find all integer solutions to equation (\ref{eq:scube})
as well as to a generalized equation, in which cubes are replaced by arbitrary
odd $k$-th powers.  We then discuss how to generate positive integer 
solutions.  While our method is neither the fastest nor the most
efficient, it does bring out an illuminating connection with Pythagorean
triples.

This work was done at the 1991 SMALL undergraduate math research program
at Williams College under the guidance of Jerry Bope.  We are grateful 
to Professor Bope for finding this problem for us, as well as for his
help and encouragement.  We are also grateful to Frank Morgan for several
helpful suggestions.  This research was supported by the NSF SURF program,
NECUSE, the Ford Foundation, and Williams College.

\section{Integer Solutions to 
$x_1^3+x_2^3+\cdots +x_n^3=(x_1+x_2+\cdots +x^n)2$}
Equation (\ref{eq:scube}) has a surprisingly large number of solutions; there
are over 8000 solutions with twelve elements, for instance.
How would one go about finding them?  A natural way is to organize them
by sum, where the {\em sum} of the solution
$\{x_1,x_2,\ldots ,x_n\}$ 
is given by $s = x_1+x_2+\cdots +x_n.$
Note that since $x_i^3 \equiv x_i $ (mod 3) implies $s \equiv s^2 $ 
(mod 3), we must have $s \equiv$ 0 or 1 (mod 3).

Now given the solution $\{1,2,3,4,5,5,-5\}$, we may
remove a $5$ and a $-5$ and be left with the solution $\{1,2,3,4,5\}$.
A solution will be said to be
in {\em reduced form} if it is impossible to simplify
it by canceling $j$'s with $-j$'s in this way and if it contains no zeros.
From now on we will only consider reduced form solutions, which we classify
without 
regard to the number of terms; i.e., we do not consider $n$ to be fixed.

Given an arbitrary reduced
solution over the integers, let $t_j$ denote the number of
times the positive integer $j$ appears in it.  If
a positive integer $j$ does not appear but $-j$
appears $r$ times, then let $t_j = -r$.  For example, the solution
$\{-1,-1,2,2,3,4,4\}$ gives $t_1=-2$, $t_2=2$, $t_3=1$, $t_4=2$.  We see that
reduced form 
integer solutions to our equation correspond to integer solutions of
\begin{equation}
t_1+8t_2+\cdots +h^3t_h=(t_1+2t_2+\cdots +ht_h)^2,
\label{eq:count}
\end{equation}
and that 
\begin{equation}
s = t_1 + 2t_2 + \cdots + ht_h.
\label{eq:sum}
\end{equation}

At this point one may obtain equations for $t_1$ and $t_2$ in terms of
$s$ and $t_3,\ldots ,t_n$ by substituting $s$ into equation (\ref{eq:count}) 
and then subtracting multiples of (\ref{eq:sum}) 
from (\ref{eq:count}).  The approach we use will yield essentially the
same results, but is hopefully more instructive.

\begin{theorem}
There exist integer
solutions to (\ref{eq:count}) with sum $s$ iff $s \equiv  0$ or $1$
{\rm (mod 3)}; the space of integer solutions with sum $s$ is
\[ \vec{u} \oplus L, \]
where
\begin{equation}
\vec{u}= \left( \frac{4s-s^2}{3}, \frac{s^2-s}{6},0,0,\ldots \right).
\label{eq:sumvec}
\end{equation}
and $L$ is a free {\bf Z}-module with basis vectors
\begin{equation}
{\vec{v}}_j = \left( \frac{j^3-4j}{3}, \frac{j-j^3}{6},0,\ldots ,0,
\underbrace{1}_{j {\rm -th \: place}},0, \ldots \right)
\end{equation}
for $j \geq 3$.
\end{theorem}
\bigskip
\pf Introducing another variable, $t_{0}$ in (3), we obtain the homogeneous
quadratic
\begin{equation}
t_{0}(t_1+8t_2+\cdots +h^3t_h)=(t_1+2t_2+\cdots +ht_h)^2.
\end{equation}
The matrix representation of the corresponding quadratic form is
\[ Q= \left( \begin{array}{rrrcrc}
0&-\frac{1}{2} & -4 &-\frac{27}{2} &\ldots &-\frac{h^3}{2} \\
-\frac{1}{2}&1&2&3&\ldots &h \\
-4&2&4&6&\ldots &2h \\
-\frac{27}{2}&3&6&9&\ldots &3h \\
\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\
-\frac{h^3}{2}&h&2h&3h&  \ldots &h^2 \\
\end{array} \right) .  \]
An orthonormal basis for $Q$
is formed by the columns of
\[ C = \left( \begin{array}{rrrrrrc}
0&2&2&0&0&\ldots &0 \\
1&\frac{4}{3}  &1&5&16&\ldots &\frac{h^3-4h}{3} \\
0&-\frac{1}{6} &0&-4&-10&\ldots &\frac{h-h^3}{6} \\
0&0&0&1&0&\ldots &0 \\
0&0&0&0&1&\ldots &0 \\
\vdots & \vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\
0&0&0&0&0&\ldots &1 \\
\end{array} \right) . \]
$Q$ is nondegenerate on the subspace spanned by the first three columns
of $C$, and the other columns form a basis for the nullspace of $Q$.

The diagonal matrix with respect to the orthonormal basis is just
\[ D=  \left( \begin{array}{rrrrrr}
1&0&0&0&\ldots &0 \\
0&1&0&0&\ldots &0 \\
0&0&-1&0&\ldots &0 \\
0&0&0&0&\ldots &0 \\
\vdots & \vdots & \vdots & \vdots &\ddots &\vdots \\
0&0&0&0&\ldots &0
\end{array} \right) . \]
This gives us the equation
$$ x_1^2+x_2^2-x_3^2=0 $$.
Its solutions, the Pythagorean triples, have a well-known
parametrization.  A routine calculation (changing bases and setting $t_{0}
=1$) shows that solutions to the original equation may be uniquely written
as $\vec{u}  + \vec{v}$, where $\vec{u}$ is given by (3) and $\vec{v}$
is in the ${\bf Z}$-span of the ${\vec{v}}_j$, which we are calling $L$.
Since the sum of a solution
is not affected by adding on the ${\vec{v}}_j$, to find all the solutions
with a prescribed sum $s$, we simply 
fix the vector $\vec{u}$.
(In essence, we have found
a pairing between Pythagorean triples and sums;
the space of solutions corresponding to a given sum is obtained by
translating the space $L$ by the corresponding
``Pythagorean vector'' ${\vec{u}}$.)

Finally, since 
${\vec{v}}_j$ always has integer entries, there exist integer solutions
with sum $s$ precisely when $(4s-s^2)/3$ and $(s^2-s)/6$
are integers, which occurs {\em iff} $s \equiv $ 0 or 1 (mod 3).

\section{Generalizing to Arbitrary Odd Powers}

The preceeding method can be easily extended to the  
equation

\begin{equation}
 x_{1}^{k} + x_{2}^{k} + \cdots + x_{n}^{k} 
 = ( x_{1} + x_{2} + \cdots + x_{n} )^{2} 
 \label{eq:skube}
\end{equation}
where $k$ is odd.
The multiset $$\{  \overbrace{ m, m, \ldots m }^{ m^{k-2} {\rm \: times} }
\},$$ for instance, satisfies this equation.

\bthm
There exist integer solutions to (\ref{eq:skube}) for odd $ k>2 $ with sum $s$ 
iff $ s \equiv 0 $ or $1$ (mod $p$)
for all odd primes $p$ for which $ p-1 \mid k-1 $.
The solution space  
of reduced form integer solutions with sum $s$ is $ \vec{u} \oplus L $, where

\begin{equation}
\vec{u} = \left( \frac{ 2^{k-1}s - s^{2} }{ 2^{k-1} -1 },
				 \frac{ s^{2} - s }{ 2^{k} - 2 },
			0, 0, \ldots \right) 
\end{equation}		
and L is a free {\bf Z}-module with basis vectors

\begin{equation}
 \vec{v}_{j} = \left( \frac{ j^{k} - 2^{k-1}j }{ 2^{k-1} - 1 },
				      \frac{ j - j^{k} }{ 2^{k} - 2 },
				      0, \ldots, 0, 
                                       \underbrace{1}_{j {\rm -th \: place}},
                                      0, \ldots
			   \right)
\end{equation}
for $ j \geq 3 $.

\ethm

\pf Equation (\ref{eq:skube}) can be transformed into a quadratic form as
before, and again gives a rank 3 matrix which yields, after a change of basis,
the Pythagorean equation.  Changing bases back again, the solution space
is as stated in the theorem.

Therefore, the only question that remains is for what sums integer
solutions exist.
A given sum will fail to have integer solutions only if
all of the numerators of $\vec{x} \oplus L $ are not
divisible by $ 2^{k-1} - 1 $.
This is equivalent to having a sum $s$ for
which $ s^{2} - s \not\equiv 0 $ (mod $p^{\alpha}$)
and $ j^{k} - j \equiv 0 $ (mod $p^{\alpha}$) for all $ j \geq 3 $ where
$ p^{\alpha} \mid 2^{k-1} - 1 $.
This cannot occur if $\alpha > 1 $ since $ p^{k} - p \not\equiv 0 $ (mod
$p^{\alpha}$) for such $p^{\alpha}$.  However, $ j^{k} - j \equiv 0 $
(mod $p$) for all $j$ {\em iff} $ p-1 \mid k-1 $
and for such $p$, $ p \mid 2^{k-1} -1 $.
Thus, for such $p$, $ s^{2} - s \equiv 0 $ (mod $p$), i.e.,
	$s \equiv 0 $ or 1 (mod $p$).

\nl

When k is even, we can no longer cancel $j$'s and $-j$'s to obtain a
reduced form solution.  Instead, we must look for solutions to 
\begin{equation}
h^k t_{-h} + \cdots + t_{-1} + t_{1} + \cdots +
h^k t_{h} = ( -h t_{-h} - \cdots - t_{-1} + t_{1} +
\cdots + h t_{h} )^{2}
\label{eq:skeven}
\end{equation}
in which every $t_{j}$ is positive.

\bthm
For even $ k > 2 $, integer solutions to (\ref{eq:skube}) correspond to
elements of $ \vec{u}' \oplus L' $ in which all entries are positive, where

\begin{equation}
\vec{u}' = \left( \ldots, 0, 0,
				 \frac{ 2^{k-1}s - s^{2} }{ 2^{k-1} -1 },
				 \frac{ s^{2} - s }{ 2^{k} - 2 },
				 0, 0, \ldots \right)
\end{equation}

and $L'$ is a free {\bf Z}-module with basis vectors

\begin{equation} 
\vec{v}_{j} = \left( \ldots, 0, 0,
					 \frac{ j^{k} - 2^{k-1}j }{ 2^{k-1} - 1 },
                     \frac{ j - j^{k} }{ 2^{k} - 2 }, 0, \ldots, 0,
					 \underbrace{1}_{j {\rm -th \: place}},
					 0, 0, \ldots \right)
\end{equation}

for all $ j \not= 1 $ or $2$.

\ethm

Note that for even $k$, there are no restrictions on possible sums
(since there are no odd primes $p$ for which $ p-1 \mid k-1 $),
but there are only
a finite number of solutions for any sum.

\section{Bounds on Positive Solutions}
We now turn to the question of positive integer solutions to our equation.
In this section we consider the relationships between the sum $s$, the
number of elements $n$, and the highest element $h$ in a solution to
(\ref{eq:skube})
over the positive integers.

\blm
In any positive integer solution to (\ref{eq:skube}),
the following inequalities hold:

(a) $ s^{k-2} \leq n^{k-1} $,

(b) $ h^{k} \leq s^{2} $, 

(c) $ h^{k-1} \geq s $,

(d) $ h \leq n^{\frac{ 2(k-1) }{ k(k-2) }} $, and 

(e) $ (n - 1)^{k-1} \geq \frac{(s-h)^{k}}{s^{2} - h^{k}} $.
\elm
\pf

	(a) $ \sum x^{k} $ is minimized for a given length and sum when all the
	 terms are the same.  This gives $ x = s/n $, so
	 $\sum (s/n)^{k} \leq s^{2} $,  and this implies 
         $s^{k-2} \leq n^{k-1} $.

        (b) $ h^{k} \leq \sum x^{k} $ gives $ h^{k} \leq s^{2} $. 

	(c) $ h^{k} = s^{2} - \sum x^{k} $ is minimized when $x$ is as high
            as possible, i.e., when $ x = h $.  This gives $nh^{k} = s^{2}$
 	    and $ nh = s $, so $ h^{k-1} \geq s $.
 
	(d) Follows from (a) and (b).

	(e) For a given $s$ and $h$, $ \sum x^{k} $ is minimized when
	all the other $n-1$ terms are the same.  This gives $ x = 
        \frac{s-h}{n-1}$, so
	$(n - 1)^{k-1} \geq \frac{(s-h)^{k}}{s^{2} - h^{k}} $.

\nl
When $k = 3$, we may further our analysis.

\bthm
In any positive integer solution to $ \sum x^{3} = ( \sum x )^{2} $ with
$ n > 1 $,
\begin{equation}
h \leq {2\over 3} + {{5 - 8 n + 4 {n^2}}\over{3 w}} + {{w}\over{3}}
\label{eq:high}
\end{equation}
where
\[
w = \sqrt[3]{ 11 - 28 n + 22 {n^2} - 8 {n^3} + 2 {n^4}
	    		- 2 {{\left( -1 - 2 n + {n^2} \right) }^{{3\over 2}}}
	    		+ 2 n {{\left( -1 - 2 n + {n^2} \right) }^{{3\over 2}}}
            }			
\]
\ethm
\pf By the above lemma, $ (n - 1)^{2} \geq \frac{(s-h)^{3}}{s^{2} - h^{3}} $.
	The right hand side is minimized when
	$ s^{2} - 2 h s = k h^{3} $ or
	$ s = h ( \sqrt{ 3 h +1 } - 1) $.
	Plugging this in and eliminating the roots by squaring yields a
	fourth degree polynomial in $h$, of which (\ref{eq:high}) is 
	the only nontrivial real solution.

\nl
The asymptotic behavior of this bound is dominated by the third term,
so $ h \leq \frac{\sqrt[3]{4}}{3} n^{4/3} $ as $ n \rightarrow \infty $.
It is also the least bound for all cases of which we are aware ($n \leq
12$), and it is exact for an infinite number of cases, as can be seen by
the multiset solution \{ $ \overbrace{ \frac{4}{3}(r^{3}-r), \ldots,
\frac{4}{3}(r^{3}-r) }^{ 2r^{3}-3r {\rm \: times } }, \frac{4}{3}(r^{4}-r^{2})
$ \}.

\section{Generating Positive Integer Solutions}

To find positive integer solutions to our original cubic equation, we
just need to find positive integer solutions to (\ref{eq:count}), which
by Theorem 1 are elements of $ \vec{u} \oplus L $ with all positive
entries.  This is the same as having integer solutions to the inequalities

\begin{equation}
4s-s^2 + \sum_{ j \geq 3 } t_{j} ( j^{3}-4j ) \geq 0
\end{equation}
and
\begin{equation}
s^2 - s + \sum_{ j \geq 3 } t_{j} ( j - j^{3} ) \geq 0
\end{equation}

By Lemma 1, $ h \leq s^{2/3} $, so we may generate all positive
solutions by trying all combinations of
$t_{j}$ with $ 3 < j < s^{2/3} $ that satisfy the above inequalities.

As an example, let us find all the solutions with sum $13$.  We have
\[\vec{u}=(-39,26,0,0,\ldots )\]
and 
\[{\vec{v}}_3=(5,-4,1,0,0,\ldots ),\]
\[{\vec{v}}_4=(16,-10,0,1,0,0,\ldots ),\]
\[{\vec{v}}_5=(35,-20,0,0,1,0,\ldots ),\]
\[{\vec{v}}_6=(64,-35,0,0,0,1,0,\ldots ),\]
\[\vdots \]
We see that the only integer solution is 
\[(1,2,1,0,1,0,0,\ldots )=\vec{u} + {\vec{v}}_3 + {\vec{v}}_5 \]
corresponding to the set $\{1,2,2,3,5\}$.

The number of positive solutions grows rapidly as a function of sum.  While
there is only 1 positive
solution with sum 13 and only 2 with sum 15, there are 200
positive solutions with sum 49, 248 with sum 51, 261 with sum 52, and 344
with sum 54.  

\end{document}