%%
%% LaTeX file starts here
%%

%% INTEGERS declarations
\documentclass[12pt]{article}
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 

%% Commands for making a box
\def\makeblanksquare#1#2{
\dimen0=#1pt\advance\dimen0 by -#2pt
      \vrule height#1pt width#2pt depth0pt\kern-#2pt
      \vrule height#1pt width#1pt depth-\dimen0 \kern-#1pt
      \vrule height#2pt width#1pt depth0pt \kern-#2pt
      \vrule height#1pt width#2pt depth0pt
}
%\def\boxx{\makeblanksquare6{.4}}

\def\boxx{\hfill $\Box$}
\usepackage{latexsym,amssymb}

%% Command for putting () around equation numbers
\newcommand{\reff}[1]{(\ref{#1})}

%% INTEGERS title page info
\begin{document} 
\vspace*{-60pt}
\centerline{\smalltt INTEGERS:
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4
(2004), \#A09}
\vskip 50pt

\begin{center}
{\bf A COMBINATORIAL PROOF OF A RESULT FROM NUMBER THEORY}
\vskip 20pt
{\bf Shaun Cooper}\\
{\smallit Institute of Information and Mathematical Sciences,
Massey University -- Albany, Private Bag 102904, North Shore Mail Centre,
Auckland, New Zealand}\\
{\tt s.cooper@massey.ac.nz}\\
\vskip 10pt
{\bf Michael Hirschhorn}\\
{\smallit School of Mathematics, UNSW, Sydney 2052, Australia}\\
{\tt m.hirschhorn@unsw.edu.au}\\
\end{center}
\vskip 30pt
\centerline{\smallit Received: 11/11/03, Accepted: 6/8/04, Published:
6/10/04 }
\vskip 30pt 

\centerline{\bf Abstract}

\noindent
%Put your abstract here. Please limit it to half of a page of text.
Let $r_k(n)$ denote the number of representations of $n$ as a sum
of $k$ squares and $t_k(n)$ the number of representations of $n$ as
a sum of $k$ triangular numbers. We give an elementary, combinatorial
proof of the relations
$$r_k(8n+k)=c_kt_k(n),\;\;\;1\leq k \leq 7,$$
where
$c_1=2$, $c_2=4$, $c_3=8$, $c_4=24$, $c_5=112$, $c_6=544$ and $c_7=2368$.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL
NUMBER THEORY \smalltt 4 (2004), \#A09\hfill}

\thispagestyle{empty}
\baselineskip=15pt 
\vskip 20pt 

\section*{\normalsize 1. Introduction}

Let $r_k(n)$ denote the number of solutions in integers of the equation
$$x_1^2+x_2^2+\cdots+x_k^2=n,$$
and let $t_k(n)$ denote the number of solutions in non-negative integers
of the equation
$$\frac{x_1(x_1+1)}{2} + \frac{x_2(x_2+1)}{2} + \cdots +
\frac{x_k(x_k+1)}{2} = n.$$
For example,
\begin{eqnarray*}
9 & = & (\pm3)^2+0^2+0^2 = 0^2+(\pm3)^2+0^2 = 0^2+0^2+(\pm3)^2 \\
  & = & (\pm2)^2+(\pm2)^2+(\pm1)^2 = (\pm2)^2+(\pm1)^2+(\pm2)^2 =
(\pm1)^2+(\pm2)^2+(\pm2)^2,
\end{eqnarray*}

\footnoterule \vskip -5pt
\noindent
{\footnotesize {\bf Key words:} sum of squares, sum of triangular
numbers, combinatorial proof,
bijective proof.\\
2000 Mathematics Subject Classification: Primary--11E25; Secondary--05A15}


\noindent
and so $r_3(9)=30$. On the other hand, $r_3(7)=0$.
Also, $t_3(10)=9$, because the solutions of
$\displaystyle{\frac{x_1(x_1+1)}{2} + \frac{x_2(x_2+1)}{2} +
\frac{x_3(x_3+1)}{2} = 10}$
in non-negative integers are $(x_1,x_2,x_3) = (4,0,0)$ (three possible
permutations), and
$(3,2,1)$ (six possible permutations), giving a total of nine solutions.

Geometrically, $r_k(n)$ counts the number of points with integer coordinates
on the $k$-dimensional sphere $x_1^2+x_2^2+\cdots+x_k^2=n.$
Similarly, $2^kt_k(n)$ counts the number of points with integer coordinates
on the 
$k$-dimensional sphere
$(x_1+\frac{1}{2})^2+(x_2+\frac{1}{2})^2+\cdots+(x_k+\frac{1}{2})^2=2n+\frac
{k}{4}.$

A great deal is known about $r_k(n)$ and $t_k(n)$. For example, generating
functions
which yield explicit formulas
for $r_k(n)$ and $t_k(n)$ for $k=2, 4, 6$ and 8 in terms of the divisors of
$n$,
were given by Jacobi \cite[pp. 159--170]{jacobi}. On the other hand,
explicit formulas for odd
values of $k$ are much more complicated. For both even and odd values of
$k\geq 9$, explicit
formulas become even more complicated. For more information, see
\cite{primitive}, \cite[Chs. 6--9]{dickson}, \cite[Ch. 20]{hardy_wright} and
\cite{milne}.

In \cite{bateman}, a remarkable connection between
$t_k(n)$ and $r_k(8n+k)$ for $1 \leq k \leq 7$
was observed. These relations were independently rediscovered in
\cite{b-c-h}.

\noindent
{\bf Theorem \cite[Lemma 2.7]{bateman}, \cite{b-c-h}.}
\\
For any non-negative integer $n$,
$$r_k(8n+k)=2^k\left(1+\frac{k(k-1)(k-2)(k-3)}{48}\right)t_k(n),\;\;\;1\leq
k \leq 7.$$
\boxx

Thus for $1\leq k \leq 7$, in
order to study the sequence $\left\{ t_k(n) \right\}_{n\geq 0}$,
it suffices to study the subsequence $\left\{ r_k(8n+k) \right\}_{n\geq 0}$
of $\left\{ r_k(n) \right\}_{n\geq 0}$.

The proof in \cite{bateman} relies on Jacobi's explicit formula for
$r_4(n)$ in terms of divisors of $n$. The proof in \cite{b-c-h} uses
generating
functions, and depends on properties of theta functions. The purpose of this
article is to give an elementary, combinatorial proof of this theorem.
\vskip 30pt
\section*{\normalsize 2. Proofs}
{\bf Lemma.}
Let
\begin{eqnarray*}
A_n & = & \left\{(i,j,k,l) \in \mathbb{Z}^4:  i+j+k+l\equiv 0 \pmod
2,\right. \\
    &   & \;\;\;\;\;\left.(2i+1)^2+(2j+1)^2+(2k+1)^2+(2l+1)^2 =
8n+4\right\}, \\
B_n & = & \left\{(i,j,k,l) \in \mathbb{Z}^4: i+j+k+l\equiv 1 \pmod 2,\right.
\\
    &   & \;\;\;\;\;\left.(2i+1)^2+(2j+1)^2+(2k+1)^2+(2l+1)^2 =
8n+4\right\}, \\
C_n & = & \left\{(i,j,k,l) \in \mathbb{Z}^4:
(2i)^2+(2j)^2+(2k)^2+(2l)^2 = 8n+4\right\}.
\end{eqnarray*}
Then the sets $A_n$, $B_n$ and $C_n$ are equinumerous.
Note that for the set $C_n$, the condition
$i+j+k+l\equiv 1 \pmod 2$ also holds.

\noindent
{\it Proof.}
Define $f:A_n\rightarrow B_n$ by
$$
f(i,j,k,l) = (i,j,k,-l-1).
$$
Then $f$ is readily seen to be a bijection, and so $A_n$ and $B_n$ are
equinumerous.
Similarly, define $g:B_n\rightarrow C_n$ by
$$
g(i,j,k,l) = \frac{1}{2}(i+j+k-l+1,i+j-k+l+1,i-j+k+l+1,-i+j+k+l+1).
$$
Then it may be easily verified that
$$
g^{-1}(i,j,k,l) = \frac{1}{2}(i+j+k-l-1,i+j-k+l-1,i-j+k+l-1,-i+j+k+l-1),
$$
and $g$ is a bijection. Thus $B_n$ and $C_n$ are equinumerous.
\boxx

\noindent
{\bf Corollary.}
The number of representations of $8n+4$ as a sum of four odd squares equals
twice
the number of representations of $8n+4$ as a sum of four even squares.

\noindent
{\it Proof of the Theorem.}
We will show that each representation of $n$ as a sum of $k$ triangular
numbers gives rise to $2^k\left(1+\frac{k(k-1)(k-2)(k-3)}{48}\right)$
representations of $8n+k$ as a sum of $k$ squares, and that every
representation of $8n+k$ as a sum of $k$ squares arises once and only
once in this way.

Suppose
\begin{equation}
n=\frac{x_1(x_1+1)}{2} + \cdots + \frac{x_k(x_k+1)}{2}
\label{k-triangles}
\end{equation}
is a representation of $n$ as a sum of $k$ triangular numbers.
Then multiplying by 8 and completing the square gives
\begin{equation}
8n+k=(\pm(2x_1+1))^2+\cdots+(\pm(2x_k+1))^2.
\label{odd-squares}
\end{equation}
This gives rise to $2^k$ representations of $8n+k$ as a sum of $k$ odd
squares, because there are $2^k$ possibilities for the signs. Conversely,
each of the $2^k$ representations in \reff{odd-squares} arises only from the
corresponding representation \reff{k-triangles}.

If $1\leq k \leq 3$, then the only way $8n+k$ may be expressed as a sum
of $k$ squares is if all the squares are odd, and so we have
$r_k(8n+k)=2^kt_k(n)$ in this case.

If $4\leq k\leq 7$ and $8n+k$ is a sum of $k$ squares, then parity
considerations 
show that either all $k$ squares are odd, or $k-4$ are odd and $4$ are even.
In the first case, equation \reff{odd-squares} gives $2^k$ representations
of $8n+k$ as a sum of $k$ odd squares for each instance of
\reff{k-triangles},
and this accounts for all representations of $8n+k$ as a sum of $k$ odd
squares.
In the latter case, there are 
$\displaystyle{{k \choose 4}}$
 orderings of
$x_1, \cdots, x_k$ by parity, in which four of the squares are even and the
others odd.
Consider the equation
\begin{equation}
x_1^2+\cdots+x_k^2=8n+k
\label{eq}
\end{equation}
where $x_1,\;x_2,\;x_3$ and $x_4$ are
even and the other $x_i$s are odd. The number of
such representations is half the number of representations of $8n+k$ as a
sum
of $k$ odd squares.
To see this, rewrite \reff{eq}
in the form
$$x_1^2+\cdots + x_4^2 = 8n+k-\sum_{j=5}^k x_j^2,$$
and apply the corollary.
It follows that the number of representations of $8n+k$
as a sum of $k$ squares, 4 of which are even, arising from the single
representation \reff{k-triangles} is $\displaystyle{\frac{1}{2} {k \choose
4} 2^k }$.

Combining the two cases we complete the proof of the Theorem.
\boxx

\noindent
{\bf Remark.}
It is clear from this proof of the Theorem that extra complications will
arise
if $k\geq 8$. In fact, using modular forms it was shown in
\cite{bateman-new}
that for each value of $k\geq 8$,
$r_k(8n+k)/t_k(n)$ is not a constant function of $n$. Therefore the Theorem
does
not hold if $k\geq 8$.


\small
\parskip=5pt

\begin{thebibliography}{99}

\bibitem{bateman}
P. T. Bateman and M. I. Knopp,
{\it Some new old-fashioned modular identities,}
The Ramanujan Journal, {\bf 2} (1998), 247--269.

\bibitem{bateman-new}
P. T. Bateman, B. A. Datskovsky and M. I. Knopp,
{\it Sums of squares and the preservation of modularity under congruence
restrictions,}
Symbolic computation, number theory, special functions, physics and
combinatorics
(Gainesville, FL, 1999), 59--71, Dev. Math., {\bf 4} Kluwer Acad. Publ.,
Dordrecht, 2001. 

\bibitem{b-c-h}
P. Barrucand, S. Cooper and M. Hirschhorn,
{\it Relations between squares and triangles,}
Discrete Math., {\bf 248} (2002), 245--247.

\bibitem{primitive}
S. Cooper and M. Hirschhorn,
{\it On the number of primitive representations of integers as sums of
squares,}
The Ramanujan Journal, {\it to appear}.

\bibitem{dickson}
L. E. Dickson,
{\it History of the theory of numbers,}
Vol. 2, Chelsea, New York, 1952.

\bibitem{hardy_wright}
G. H. Hardy and E. M. Wright,
{\it An Introduction to the Theory of Numbers,}
Fifth edition, Oxford, reprinted 1989.

\bibitem{jacobi}
C. G. J. Jacobi,
{\it Fundamenta Nova Theoriae Functionum Ellipticarum,} 1829.
Reprinted in {\em C. G. J. Jacobi's Gesammelte Werke,} B. 1,  49--239,
(ed. K. Weierstrass), 1881; Second edition published by Chelsea, New York,
1969.

\bibitem{milne}
S. C. Milne,
{\it Infinite families of exact sums of squares formulas, Jacobi elliptic
functions,
continued fractions, and Schur functions,}
The Ramanujan Journal, {\bf 6} No. 1 (2002), 7--149.


\end{thebibliography}



\end{document}