\documentclass[12pt,reqno]{article}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
An Elementary Proof that any Natural \\ \vskip .05in
Number can be Written as the Sum of Three \\ \vskip .11in
Terms of the Sequence $\lfloor\frac{n^2}{3}\rfloor$
}
\vskip 1cm
\large
Bakir Farhi\\
Department of Mathematics\\
University of B\'ejaia\\
B\'ejaia\\
Algeria\\
\href{mailto:bakir.farhi@gmail.com}{\tt bakir.farhi@gmail.com} \\
\end{center}
\vskip .2 in
\def\modd#1 #2{#1\ ({\rm mod}\ #2)}
\begin{abstract}
We give an elementary proof that any
natural number can be written as the sum of three terms of the sequence
${(\lfloor\frac{n^2}{3}\rfloor)}_{n \in \N}$. This is a recent
conjecture of the author that was very recently confirmed by
Mezroui et al.; they used a result due to Bateman and derived from
the theory of modular forms. We also state some conjectures related to
the subject.
\end{abstract}
\section{Introduction}
Throughout this paper, we let $\N$ and $\N^*$ denote, respectively, the set of the non-negative integers and the set of the positive integers. We also let $\lfloor x \rfloor$ and $\langle x \rangle$ denote, respectively, the integer part and the fractional part of a real
number $x$.
The representation of natural numbers as the sum of a fixed number of
squares is one of the oldest and most fascinating problems of number theory.
Let us just cite the most important classical results which are due to
Euler, Lagrange, Legendre and Gauss. Euler proved that a natural number
is the sum of two squares if and only if in its decomposition as a
product of primes, the powers of the primes having the form $(4 k + 3)$
($k \in \N$) are all even. Lagrange \cite{lag} proved that any natural
number is the sum of four squares of integers. Legendre and then Gauss
proved the powerful result stating that any natural number not of the
form $4^h (8 k + 7)$ ($h , k \in \N$) can be written as the sum of
three squares (see for example \cite{leg}).
By using Legendre's theorem cited above, the author \cite{far} obtained some results concerning the representation of the natural numbers as the sum of three terms of the sequence ${(\lfloor\frac{n^2}{a}\rfloor)}_{n \in \N}$ (where $a \in \N^*$ is a parameter). In particular, we proved that any natural number $N \not\equiv \modd{2} {24}$ can be written as the sum of three terms of the sequence ${(\lfloor\frac{n^2}{3}\rfloor)}_{n \in \N}$ and we conjectured that this result remains true even if $N \equiv \modd{2} {24}$. This conjecture was very recently confirmed by Mezroui et al.\ \cite{mez}. So we have the following:
\begin{theorem}[see \cite{far, mez}]\label{t1}
Every natural number can be written as the sum of three numbers of the form $\lfloor\frac{n^2}{3}\rfloor$ ($n \in \N$).
\end{theorem}
However, the proof of Mezroui et al.\ \cite{mez} is not elementary
because it depends on a result of Bateman \cite{bat} which is related
to the theory of modular forms. The aim of this note is to give an
elementary proof of Theorem \ref{t1}. The advantage of our proof is
twofold: on the one hand, it is elementary, and on the other hand, it
gives us a method of finding explicitly the representation in question;
that is, the representation of a given natural number as
$\lfloor\frac{a^2}{3}\rfloor + \lfloor\frac{b^2}{3}\rfloor +
\lfloor\frac{c^2}{3}\rfloor$ ($a , b , c \in \N$).
\section{An elementary proof of Theorem \ref{t1}}
The fundamental idea of our proof of Theorem \ref{t1} consists of using the identity:
\begin{equation}\label{eq-fund}
(2 x + 2 y + z)^2 + (2 x - y - 2 z)^2 + (x - 2 y + 2 z)^2 ~=~ 9\left(x^2 + y^2 + z^2\right)
\end{equation}
($\forall x , y , z \in \Z$). Once known, the verification of this identity is immediate.
We now give the details of our proof. We begin with two lemmas:
\begin{lemma}\label{l1}
Let $a , b , c \in \Z$. If one at least of the three integers $a$, $b$ and $c$ is not a multiple of $3$, then also one at least of the three integers $a + b - c$, $a + c - b$ and $b + c - a$ is not a multiple of $3$.
\end{lemma}
\begin{proof}
The system of congruences
$$
\left\{
\begin{array}{rcl}
a + b - c & \equiv & \modd{0} {3} \\
a + c - b & \equiv & \modd{0} {3} \\
b + c - a & \equiv & \modd{0} {3}
\end{array}
\right.
$$
has determinant
$$
\begin{vmatrix}
1 & 1 & -1 \\
1 & -1 & 1 \\
-1 & 1 & 1
\end{vmatrix} = -4 \not\equiv \modd{0} {3} .
$$
Since this determinant is invertible modulo $3$, we have
$$
\left\{
\begin{array}{rcl}
a + b - c & \equiv & \modd{0} {3} \\
a + c - b & \equiv & \modd{0} {3} \\
b + c - a & \equiv & \modd{0} {3}
\end{array}
\right. \Longleftrightarrow \left\{
\begin{array}{rcl}
a & \equiv & \modd{0} {3} \\
b & \equiv & \modd{0} {3} \\
c & \equiv & \modd{0} {3}
\end{array}
\right. ,
$$
which concludes this proof.
\end{proof}
\begin{lemma}[The fundamental lemma]\label{l2}
For any natural number $k$, there exist natural numbers $a$, $b$, $c$, which are not all multiples of $3$, such that
$$
a^2 + b^2 + c^2 ~=~ 8 k + 1 .
$$
\end{lemma}
\begin{proof}
We argue by induction on $k$.
For $k = 0$, it suffices to take $(a , b , c) = (1 , 0 , 0)$.
Now let $k$ be a positive integer.
Suppose that the property of the lemma is true for all natural number $k' < k$ and let us show that it holds for $k$. We distinguish the following two cases:
\medskip
\noindent {\bf Case 1:} $k \not\equiv \modd{1} {9}$:
By Legendre's theorem, there exist $a , b , c \in \N$ such that
$$
a^2 + b^2 + c^2 = 8 k + 1 .
$$
If $a$, $b$, $c$ are all multiples of $3$, we have $a^2 + b^2 + c^2 \equiv \modd{0} {9}$; that is $8 k + 1 \equiv \modd{0} {9}$. This gives $k \equiv \modd{1} {9}$, which contradicts the assumption of this first case. So $a$, $b$, $c$ cannot all be multiples of $3$, as required.
\medskip
\noindent {\bf Case 2:} $k \equiv \modd{1} {9}$:
In this case, there exists $k' \in \N$ such that $k = 9 k' + 1$. So we have
$$
8 k + 1 = 9 (8 k' + 1) .
$$
Since $k' = \frac{k - 1}{9} < k$, then by the induction hypothesis there exist $a' , b' , c' \in \N$, which are not all multiples of $3$, such that
$$
a'^2 + b'^2 + c'^2 = 8 k' + 1 .
$$
Next, by Lemma \ref{l1}, one at least of the integers $a' + b' - c'$, $a' + c' - b'$, $b' + c' - a'$ is not a multiple of $3$. By permuting $a'$, $b'$, $c'$ if necessary, we can suppose that
\begin{equation}\label{eq1}
a' + b' - c' \not\equiv \modd{0} {3}
\end{equation}
Now, let
\begin{eqnarray*}
a & := & |2 a' + 2 b' + c'| \\
b & := & |2 a' - b' - 2 c'| \\
c & := & |a' - 2 b' + 2 c'| .
\end{eqnarray*}
By \eqref{eq-fund}, we have
$$
a^2 + b^2 + c^2 = 9 (a'^2 + b'^2 + c'^2) .
$$
Hence
$$
a^2 + b^2 + c^2 = 9 (8 k' + 1) = 8 k + 1 .
$$
To conclude, it remains to show that the natural numbers $a$, $b$, $c$ are not all multiples of $3$. We have
$$
\left\{
\begin{array}{rcl}
a & \equiv & \modd{0} {3} \\
b & \equiv & \modd{0} {3} \\
c & \equiv & \modd{0} {3}
\end{array}
\right. ~\Longleftrightarrow~
\left\{
\begin{array}{rcl}
2 a' + 2 b' + c' & \equiv & \modd{0} {3} \\
2 a' - b' - 2 c' & \equiv & \modd{0} {3} \\
a' - 2 b' + 2 c' & \equiv & \modd{0} {3}
\end{array}
\right. ~\Longleftrightarrow~ a' + b' - c' \equiv \modd{0} {3} .
$$
But since $a' + b' - c' \not\equiv \modd{0} {3}$ (according to \eqref{eq1}), we conclude that effectively $a$, $b$, $c$ are not all multiples of $3$. The proof is complete.
\end{proof}
Using Lemma \ref{l2}, we are now able to prove Theorem \ref{t1} by the method we have introduced in \cite{far}.
\begin{proof}[Proof of Theorem \ref{t1}]
Let $N$ be a fixed natural number. We shall prove that $N$ can be represented as the sum of three terms of the sequence ${(\lfloor\frac{n^2}{3}\rfloor)}_{n \in \N}$. To do this, we distinguish the following two cases:
\noindent {\bf Case 1:} if $N \not\equiv \modd{2} {8}$.
In this case, we can find $r \in \{1 , 2\}$ such that $3 N + r \not\equiv \modd{0 , 4 , 7} {8}$, so $(3 N + r)$ is not of the form $4^h (8 k + 7)$ $(h , k \in \mathbb{N})$. It follows by Legendre's theorem that $(3 N + r)$ can be written as
\begin{equation*}
3 N + r = a^2 + b^2 + c^2 ~~~~~~~~~~ \text{(with $a , b , c \in \mathbb{N}$).}
\end{equation*}
By dividing by $3$ and by separating the integer and the fractional parts, we get
\begin{equation}\label{eq2}
N + \frac{r}{3} = \left\lfloor\frac{a^2}{3}\right\rfloor + \left\lfloor\frac{b^2}{3}\right\rfloor + \left\lfloor\frac{c^2}{3}\right\rfloor + \left(\left\langle\frac{a^2}{3}\right\rangle + \left\langle\frac{b^2}{3}\right\rangle + \left\langle\frac{c^2}{3}\right\rangle\right)
\end{equation}
Now, since the quadratic residues modulo $3$ are $0$ and $1$ then $\langle\frac{a^2}{3}\rangle + \langle\frac{b^2}{3}\rangle + \langle\frac{c^2}{3}\rangle \in \{0 , \frac{1}{3} , \frac{2}{3} , 1\}$. But on the other hand, we have (according to \eqref{eq2}) $\langle\frac{a^2}{3}\rangle + \langle\frac{b^2}{3}\rangle + \langle\frac{c^2}{3}\rangle \equiv \modd{\frac{r}{3}} {1}$. Hence $\langle\frac{a^2}{3}\rangle + \langle\frac{b^2}{3}\rangle + \langle\frac{c^2}{3}\rangle = \frac{r}{3}$ and by replacing this in \eqref{eq2}, we get (after simplifying)
$$
N = \left\lfloor\frac{a^2}{3}\right\rfloor + \left\lfloor\frac{b^2}{3}\right\rfloor + \left\lfloor\frac{c^2}{3}\right\rfloor ,
$$
as required.
\medskip
\noindent {\bf Case 2:} if $N \equiv \modd{2} {8}$.
In this case, we have $3 N + 3 \equiv \modd{1} {8}$. It follows by Lemma \ref{l2} that there exist $a , b , c \in \N$, which are not all multiples of $3$, such that
\begin{equation}\label{eq3}
3 N + 3 = a^2 + b^2 + c^2
\end{equation}
By dividing by $3$ and by separating the integer and the fractional parts, we get
\begin{equation}\label{eq4}
N + 1 = \left\lfloor\frac{a^2}{3}\right\rfloor + \left\lfloor\frac{b^2}{3}\right\rfloor + \left\lfloor\frac{c^2}{3}\right\rfloor + \left(\left\langle\frac{a^2}{3}\right\rangle + \left\langle\frac{b^2}{3}\right\rangle + \left\langle\frac{c^2}{3}\right\rangle\right)
\end{equation}
Now, since $a$, $b$, $c$ are not all multiples of $3$ and $a^2 + b^2 + c^2 \equiv \modd{0} {3}$ (according to \eqref{eq3}), then we have inevitably
$$
a^2 \equiv b^2 \equiv c^2 \equiv \modd{1} {3} .
$$
This implies that $\langle\frac{a^2}{3}\rangle = \langle\frac{b^2}{3}\rangle = \langle\frac{c^2}{3}\rangle = \frac{1}{3}$. By replacing this in \eqref{eq4}, we finally obtain (after simplifying)
$$
N = \left\lfloor\frac{a^2}{3}\right\rfloor + \left\lfloor\frac{b^2}{3}\right\rfloor + \left\lfloor\frac{c^2}{3}\right\rfloor ,
$$
which is the required representation of $N$. The proof is complete.
\end{proof}
\section{Some related conjectures}
Up to now, we just know (according to \cite{far}, \cite{mez} and the present paper) that for $a \in \{3 , 4 , 8\}$, any natural number can be represented as the sum of three terms of the sequence ${(\lfloor\frac{n^2}{a}\rfloor)}_{n \in \N}$. However, a simple PARI/GP program leads us to believe that this property holds for any integer $a \geq 3$. We make the following:
\begin{conjecture}\label{conj1}
Let $a \geq 3$ be an integer. Then every natural number can be represented as a sum of three terms of the sequence ${(\lfloor\frac{n^2}{a}\rfloor)}_{n \in \N}$.
\end{conjecture}
Next, the author \cite{far} conjectured the following:
\begin{conjecture}[see \cite{far}]\label{conj2}
For any integer $k \geq 2$, there exists a positive integer $a(k)$ satisfying the following property:
\noindent Every natural number can be represented as the sum of $(k + 1)$ terms of the sequence ${(\lfloor\frac{n^k}{a(k)}\rfloor)}_{n \in \N}$.
\end{conjecture}
For the moment, the only value of $k$ for which Conjecture \ref{conj2} is known to be true is $k = 2$ and we can take $a(2) = 8$, $4$ or $3$.
Now suppose Conjecture \ref{conj2} true. We are interested in the smallest possible value of $a(k)$ ($k \geq 2$) in that conjecture. We make the following
\begin{conjecture}\label{conj3}
Suppose that Conjecture \ref{conj2} is true and let $\alpha(k)$ denote ($k \geq 2$ an integer) the smallest possible value of $a(k)$ in Conjecture \ref{conj2}. Then we have
$$
k! ~<~ \alpha(k) ~<~ k^k .
$$
\end{conjecture}
By taking $k = 2$ in Conjecture \ref{conj3}, we obtain $\alpha(2) = 3$,
which is true (according to \cite{far,mez} and the present paper).
For $k = 3$, a PARI/GP program leads us to believe that $\alpha(3) = 17$, which satisfies the double inequality of Conjecture \ref{conj3}.
Further,
we believe that
in Conjecture \ref{conj2} we can take
$a(k) = k^k$ (for any $k \geq 2$). So we make the following conjecture:
\begin{conjecture}\label{conj4}
Let $k \geq 2$ be an integer. Then every natural number can be represented as the sum of $(k + 1)$ terms of the sequence ${(\lfloor(\frac{n}{k})^k\rfloor)}_{n \in \N}$.
\end{conjecture}
Up to now, Conjecture \ref{conj4} has been confirmed only for $k = 2$ (see \cite{far}).
We end this note by making a final conjecture which is stronger than Conjecture \ref{conj2} and generalizes at the same time Conjecture \ref{conj1}.
\begin{conjecture}\label{conj5}
For any integer $k \geq 2$, there exists a positive integer $b(k)$ such that for any integer $b \geq b(k)$, we have the following property:
\noindent Every natural number can be represented as the sum of $(k + 1)$ terms of the sequence ${(\lfloor\frac{n^k}{b}\rfloor)}_{n \in \N}$.
\end{conjecture}
If we believe the truths of Conjectures \ref{conj1} and \ref{conj5} and we let $\beta(k)$
denote the smallest possible value of $b(k)$ in Conjecture \ref{conj5},
then we have $\beta(2) = 3 = \alpha(2)$. Note that for other values of
$k$ ($k \geq 3$), we just have (obviously) $\beta(k) \geq \alpha(k)$.
\section{Acknowledgements}
I would like to thank the referee for his/her comments and suggestions which certainly
improved the readability of this paper.
\begin{thebibliography}{9}
\bibitem{bat}
P. T. Bateman, On the representations of a number as the sum of three squares, {\it Trans. Amer. Math. Soc}. {\bf 71} (1951), 70--101.
\bibitem{far}
B. Farhi, On the representation of the natural numbers as the sum of three terms of the sequence $\lfloor\frac{n^2}{a}\rfloor$, {\it J. Integer Seq}. {\bf 16} (2013),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Farhi/farhi7.html}{Article
13.6.4}.
\bibitem{lag}
J. L. Lagrange, D\'emonstration d'un th\'eor\`eme d'arithm\'etique, {\it Nouveaux M\'emoires de l'Acad. Royale des Sci. et Belles-Lettres de Berlin} {\bf 3} (1770), 189--201.
\bibitem{leg}
A. M. Legendre, {\it Th\'eorie des Nombres}, 3rd ed., vol.\ 2, 1830.
\bibitem{mez}
S. Mezroui, A. Azizi, and M. Ziane, On a conjecture of Farhi, {\it J. Integer Seq}. {\bf 17} (2014),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezroui/soufiane4.html}{Article
14.1.8}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B13.
\noindent \emph{Keywords:}
Sum of squares, Legendre's theorem, additive bases.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received November 6 2013;
revised versions received May 14 2014; May 29 2014; June 25 2014.
Published in {\it Journal of Integer Sequences}, July 11 2014.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}