On a Conjecture on the Representation of Positive Integers as the Sum of Three Terms

of the Sequence ⌊\frac{n^{2}}{a}⌋

Sebastian Tim Holdum Niels Bohr Institute

University of Copenhagen

Denmark

sebastian.holdum@nbi.dk

Frederik Ravn Klausen and Peter Michael Reichstein Rasmussen Department of Mathematics University of Copenhagen

Denmark

 tlk870@alumni.ku.dk
 nmq584@alumni.ku.dk

Abstract

We prove some cases of a conjecture by Farhi on the representation of every positive integer as the sum of three terms of the sequence ⌊\frac{n^{2}}{a} ⌋. This is done by generalizing a method used by Farhi in his original paper.

1 Introduction

In the following we let ℕ denote the set of non-negative integers, ⌊·⌋ denote the greatest integer function, and ⟨·⟩ denote the fractional part function.

A classical result by Legendre [3] states that every natural number not of the form 4^{s}(8t + 7), s, t ∈ ℕ can be written as the sum of three squares.

In relation to this, Farhi recently conjectured the following:

Conjecture 1 (Farhi [2]). Let a ≥ 3 be an integer. Then every natural number can be represented as the sum of three terms of the sequence (⌊\frac{n^{2}}{a} ⌋)_{n∈ℕ}.

The conjecture was confirmed by Farhi [1] and Mezroui, Azizi, and Ziane [4] for a ∈ {3, 4, 8}.

In this paper we generalize the method used by Farhi for a = 4, and partially for a = 3, to prove that the conjecture holds for a ∈ {4, 7, 8, 9, 20, 24, 40, 104, 120}. The method uses Legendre’s three-square theorem and properties of quadratic residues.

We also note that the set of integers a such that Conjecture 1 holds is closed under multiplication by a square.

2 Method and results

We start by introducing the following sets:

Definition 2. For any nonzero a ∈ ℕ we define

Q_{a} = {0 < φ < a | ∃x ∈ ℤ: φ ≡ x^{2} (mod a)}.

Therefore, Q_{a} is the set of quadratic residues modulo a.

Definition 3. For any nonzero a ∈ ℕ we define

A_{a} = {φ ∈ ℕ | ∃x, y, z ∈ Q_{a} ∪ {0}: φ = x + y + z}.

Thus, A_{a} is the set of integers that can be written as the sum of three elements of Q_{a} ∪ {0}.

Definition 4. For any nonzero a ∈ ℕ we define

R_{a} = {φ ∈ A_{a} | ∀ψ ∈ A_{a}: φ ≡ ψ (mod a) ⇒ φ = ψ}.

So, R_{a} is the set of integers that can be written as the sum of three elements of Q_{a} ∪ {0}, and such that no other integer in the same residue class modulo a has this property.

Now we are ready to formulate the main result.

Theorem 5. Let a ∈ ℕ be nonzero and assume that for every k ∈ ℕ there exists an r ∈ R_{a} such that ak + r ≠ 4^{s}(8t + 7) for any s, t ∈ ℕ. Then every N ∈ ℕ can be written as the sum of three terms of the sequence (⌊\frac{n^{2}}{a} ⌋)_{n∈ℕ}.

Proof. Let N ∈ ℕ be fixed. By assumption we can choose r ∈ R_{a} such that aN + r ≠ 4^{s}(8t + 7) for any s, t ∈ ℕ. By Legendre’s theorem it follows that aN + r can be written of the form

aN + r = A^{2} + B^{2} + C^{2}  (1)

for some A, B, C ∈ ℕ. Now we have

r ≡ A^{2} + B^{2} + C^{2} (mod a),

so

r = (A^{2} mod a) + (B^{2} mod a) + (C^{2} mod a),  (2)

since r ∈ R_{a}. Dividing by a and separating the integer and fractional parts of the right hand side in (1), we get

N + \frac{r}{a} = ⌊\frac{A^{2}}{a} ⌋ + ⌊\frac{B^{2}}{a} ⌋ + ⌊\frac{C^{2}}{a} ⌋ + ⟨\frac{A^{2}}{a} ⟩ + ⟨\frac{B^{2}}{a} ⟩ + ⟨\frac{C^{2}}{a} ⟩ ,

and from (2) we have

\frac{r}{a} = ⟨\frac{A^{2}}{a} ⟩ + ⟨\frac{B^{2}}{a} ⟩ + ⟨\frac{C^{2}}{a} ⟩ ,

so

N = ⌊\frac{A^{2}}{a} ⌋ + ⌊\frac{B^{2}}{a} ⌋ + ⌊\frac{C^{2}}{a} ⌋ .

Since we can find the sets R_{a} by computation, we can now apply the main theorem to get the following corollary.

Corollary 6. Conjecture 1 is satisfied for a ∈ {4, 7, 8, 9, 20, 24, 40, 104, 120}.

Proof. Consider the following table:

\begin{matrix}a & R_{a} \\ 4 & \{0, 1, 2, 3\} \\ 7 & \{4, 6\} \\ 8 & \{2, 3, 5, 6\} \\ 9 & \{1, 4, 7, 8\} \\ 20 & \{11, 15, 18, 19\} \\ 24 & \{11, 14, 19, 21, 22\} \\ 40 & \{27, 38\} \\ 104 & \{99\} \\ 120 & \{107\} \end{matrix}

Calculating modulo 8 it can be checked fairly easily that for each a ∈ {4, 7, 8, 9, 20, 24, 40, 104, 120} and every k ∈ ℕ there exists an r ∈ R_{a} such that ak + r is not of the form 4^{s}(8t + 7), s, t ∈ ℕ, and thus every natural number can be written as the sum of three terms of the sequence (⌊\frac{n^{2}}{a} ⌋)_{n∈ℕ}.

To demonstrate this, we show the case a = 7. All the other cases are done in exactly the same way.

For k ≡ 1, 2, 3, 6 or 7 (mod 8) we have 7k + 4 ≡ 3, 2, 1, 6 and 5 (mod 8), respectively, and for k ≡ 0, 4 or 5 (mod 8) we have 7k + 6 ≡ 6, 2 and 1 (mod 8), respectively. Since 4^{s}(8t + 7) ≡ 0, 4 or 7 (mod 8), s, t ∈ ℕ, we conclude that for every k ∈ ℕ we can write 7k + r, for r ∈ R_{7} = {4, 6}, such that it is not of the form 4^{s}(8t + 7), s, t ∈ ℕ. The case now follows from Theorem 5.

Further, one should note that the set of integers satisfying Conjecture 1 is closed under multiplication by a square.

Observation 7. Let M be the set of integers satisfying Conjecture 1. If a ∈ M, then ak^{2} ∈ M for any integer k > 0.

Proof. This follows easily since for any n we can find A, B, C ∈ ℕ such that

n = ⌊\frac{A^{2}}{a} ⌋ + ⌊\frac{B^{2}}{a} ⌋ + ⌊\frac{C^{2}}{a} ⌋

= ⌊\frac{(Ak)^{2}}{ak^{2}} ⌋ + ⌊\frac{(Bk)^{2}}{ak^{2}} ⌋ + ⌊\frac{(Ck)^{2}}{ak^{2}} ⌋ .

Knowing this, we see that since Conjecture 1 is satisfied for a = 3, 9, 4, and 8, it must also hold for a = 3^{k} for any positive integer k and for a = 2^{k}, k > 1.

Finally, using Observation 7, Corollary 6, and the fact [4] that Conjecture 1 holds for a = 3, we get that the conjecture holds for the following values up to 120.

a ∈ {3, 4, 7, 8, 9, 12, 16, 20, 24, 27, 28, 32, 36, 40, 48,
63, 64, 72, 75, 80, 81, 96, 100, 104, 108, 112, 120}.

Unfortunately, it seems that the method deployed in Theorem 5 is not extendable to other cases, since its success relies on R_{a}, and in general R_{a} does not contain the necessary elements for the condition in the theorem to be satisfied.

3 Acknowledgment

The authors would like to thank Jan Agentoft Nielsen for his suggestions that helped to improve the manuscript.

References

[1] B. Farhi, On the representation of the natural numbers as the sum of three terms of the sequence ⌊\frac{n^{2}}{a} ⌋, J. Integer Seq., 16 (2013), Article 13.6.4.

[2] B. Farhi, An elementary proof that any natural number can be written as the sum of three terms of the sequence ⌊\frac{n^{2}}{3} ⌋, J. Integer Seq., 17 (2014), Article 14.7.6.

[3] A. M. Legendre, Théorie des Nombres, 3rd ed., Vol. 2, 1830.

[4] S. Mezroui, A. Azizi, and M. Ziane, On a conjecture of Farhi, J. Integer Seq., 17 (2014), Article 14.1.8.

2010 Mathematics Subject Classification: Primary 11B13. Keywords: additive base, Legendre’s theorem.

Received September 29 2014; revised version received March 5 2015; May 19 2015. Published in Journal of Integer Sequences, May 31 2015.

Return to Journal of Integer Sequences home page.