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

\title{On the Diophantine Equation
	   ${\displaystyle \sum} x^{k} = \left({\displaystyle \sum} x\right)^{m}$}
\author{Cordelia Aitkin \and Thomas Colthurst \and Kathryn Kollett 
	\and Steven Levandosky \and Andrew Perry \and Eugene Stern }

\begin{document}
\maketitle

\section{Introduction}
It is well known that 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}
This equation can be generalized to 
\begin{equation}
x_1^k+x_2^k+\cdots +x_n^k=(x_1+x_2+\cdots +x_n)^m;
\label{eq:skube}
\end{equation}
the multiset $ \{ \overbrace{ n^{\frac{k-m}{m-1}}, n^{\frac{k-m}{m-1}},
							  \ldots , n^{\frac{k-m}{m-1}}
							}^{n {\rm \: times}} \} $
is a solution, for example.
In this paper, we find all integer solutions of Equation
(\ref{eq:skube}) by reformulating
the problem with new unknowns, in such a way that the solutions can be
easily parameterized by their sum.  We also show for what sums integer
solutions exist, and give bounds on the sum, size, and highest element
of positive integer solutions.

We would like to thank Jerry Bope, our advisor, for framing this problem and
for his help and encouragement.  We acknowledge the work done on this problem
by the 1990 SMALL combinatorics group at Williams College.
We would also like to thank Frank Morgan
for his comments on this paper.  This research was funded by the NSF SURF
program, NECUSE, the Ford Foundation, and Williams College.

\section{Finding Integer Solutions for Odd $k$}
We begin with some definitions.  If $\{x_1,x_2,\ldots ,x_n\}$ is a 
solution, then its {\em sum} is given by $s = x_1+x_2+\cdots +x_n.$

If $k$ is odd, observe that given the solution $\{1,2,3,4,5,5,-5\}$, we may
simply 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.

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$.
We see that reduced form 
integer solutions to our equation correspond to integer solutions of
\begin{equation}
t_1 + 2^k t_2 + \cdots + h^k t_h=(t_1+2t_2+\cdots +ht_h)^m,
\label{eq:count}
\end{equation}
and that
\begin{equation}
s = t_1 + 2t_2 + \cdots + ht_h.
\label{eq:sum}
\end{equation}

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

\begin{equation}
\vec{u} = \left( \frac{ 2^{k-1}s - s^{m} }{ 2^{k-1} -1 },
				 \frac{ s^{m} - 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
Subtracting Equation (\ref{eq:sum}) from Equation (\ref{eq:count}) gives
\begin{equation}
t_2 = \frac{ s^m - s }{ 2^k - 2 } +
	  \sum_{j \geq 3 } t_j \frac{ j - j^k }{ 2^k-2 }
\label{eq:t2}
\end{equation}
Plugging this back into Equation (\ref{eq:count}) and solving for $t_1$
gives
\begin{equation}
t_1 = \frac{ 2^{k-1} s - s^m }{ 2^{k-1} - 1 }
	  + \sum_{j \geq 3 } t_j \frac{ j^{k} - 2^{k-1}j }{ 2^{k-1} - 1 }
\end{equation}

Therefore, the only question that remains is for what sums solutions exist.
A given sum will fail to have integer solutions only if
all of the numerators of $\vec{u} \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, since ${\bf Z}/p{\bf Z}$ has a 
primitive root, $ 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$, we must have $ s^{m} - s \equiv 0 $ (mod $p$) for
there to be integer solutions.

\nl
Note that the equivalence $ s^{m} \equiv s $ (mod $p$) has
$1+\gcd(m-1,p-1)$ solutions.  There are thus no restrictions on sums,
for instance, when $k=2m-1$ and $m$ is an odd prime.

\section{Finding Integer Solutions for Even $k$}

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} )^{m}
\label{eq:skeven}
\end{equation}
in which every $t_{j}$ is positive.

\bthm
For even $ k > 2 $, integer reduced form solutions $\vec{t}$
to (\ref{eq:skube}) satisfy 

\begin{eqnarray*}
t_1  = & {\large \frac{ 2^{k-1}s - s^{m} }{ 2^{k-1} -1 } } & + 
        \sum_{ j \not=1 {\rm \: or \:} 2 }
				  t_j \frac{ j^{k} - 2^{k-1}j }{ 2^{k-1} - 1 } \\
t_2  = & {\large \frac{ s^{m} - s }{ 2^{k} - 2 } } & + 
	    \sum_{ j \not=1 {\rm \: or \:} 2 } t_j \frac{ j - j^{k} }{ 2^{k} - 2 }
\end{eqnarray*}

and $ t_j \geq 0 $.
\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-m} \leq n^{k-1} $,

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

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

(d) $ (n - 1)^{k-1} \geq \frac{(s-h)^{k}}{s^{m} - 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^{m} $,  and this implies 
         $s^{k-m} \leq n^{k-1} $.

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

	(d) 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^{m} - h^{k}} $.

\nl
When $k = 3$ and $m = 2$, 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 = 3 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})
\}.
\]
These bounds and Theorems 1 and 2 can be used to quickly generate
positive integer solutions.
\end{document}