On a Conjecture of Farhi

Soufiane Mezroui, Abdelmalek Azizi, and M’hammed Ziane Laboratoire ACSA Département de Mathématiques et Informatique Université Mohammed Premier Oujda 60000 Morocco

                   mezroui.soufiane@yahoo.fr
                   abdelmalekazizi@yahoo.fr
                      ziane12001@yahoo.fr

Abstract Recently, Farhi showed that every natural number N ≢ 2 (mod 24) can be written as the sum of three numbers of the form ⌊\frac{n^{2}}{3} ⌋ (n ∈ ℕ). He conjectured that this result remains true even if N ≡ 2 (mod 24). In this note, we prove this statement.

1 Introduction

Throughout this note, we let ℕ and ℤ, respectively, denote the set of the non-negative integers and the set of the integers. We let ⌊·⌋ and ⟨·⟩ denote the integer-part and the fractional-part functions. Let X be a set. We denote the cardinality of X by #X. We also recall that (\frac{·}{·}) is the Jacobi symbol.

Recently, Farhi [1] showed that every natural number N ≢ 2 (mod 24) can be written as the sum of three numbers of the form ⌊\frac{n^{2}}{3} ⌋ (n ∈ ℕ). He conjectured that this result remains true even if N ≡ 2 (mod 24). We recall his conjecture. Conjecture 1. Every natural number can be written as the sum of three numbers of the form ⌊\frac{n^{2}}{3} ⌋ (n ∈ ℕ).

In fact, he proposed a more general conjecture.

Conjecture 2. Let k ≥ 2 be an integer. There then exists a positive integer a(k) that satisfies the following property: every natural number can be written as the sum of k + 1 numbers of the form ⌊\frac{n^{k}}{a(k)}⌋ (n ∈ ℕ).

In this note, we prove Conjecture 1.

2 Proof of Conjecture 1

We recall Legendre’s theorem [3, pp. 331–339], which is a necessary tool for our proof:

Theorem 3. Every natural number not of the form 4^{h}(8k + 7)(h, k ∈ ℕ) can be represented as the sum of three squares of natural numbers.

We note that since 4^{h}(8k + 7) is congruent to 0, 4 or 7 modulo 8, every natural number not congruent to 0, 4 or 7 modulo 8 can be represented as the sum of three squares of natural numbers. We will use this result later.

Let r_{3}(n) be the number of representations of the positive integer n as the sum of three squares of integers. The following theorem provides an interesting formula for r_{3}(n), which can be proven using the theory of modular functions.

Theorem 4 (see [2]). For any positive integer n, we have

r_{3}(n) = \frac{16}{π}\sqrt{n}χ_{2}(n)K(−4n) ∏_{p^{2}|n} (1 + \frac{1}{p} + ⋯ + \frac{1}{p^{b−1}} + \frac{1}{p^{b}} (1 − (\frac{−p^{−2b}n}{p}) \frac{1}{p})^{−1}) ,

where b = b(p) is the largest integer such that p^{2b} | n,

K(−4n) = ∑_{m=1}^{∞} (\frac{−4n}{m}) \frac{1}{m},

and if 4^{a} is the highest power of 4 dividing n, then

χ_{2}(n) = \begin{cases}0, & if 4^{−a}n ≡ 7 (mod 8); \\ \frac{1}{2^{a}} , & if 4^{−a}n ≡ 3 (mod 8); \\ \frac{3}{2^{a+1}} , & if 4^{−a}n ≡ 1, 2, 5, 6 (mod 8). \end{cases}

□

We will require the following technical lemma.

Lemma 5. For any positive integer n ≡ 1 (mod 8), we have

r_{3}(9n) > \frac{3}{2} r_{3}(n).

Proof. We have

\begin{matrix}r_{3}(9n) = & \frac{16}{π}\sqrt{9n}χ_{2}(9n)K(−36n)× \\ ∏_{p^{2}|9n} (1 + \frac{1}{p} + ⋯ + \frac{1}{p^{b′−1}} & +\frac{1}{p^{b′}} (1 − (\frac{−9 p^{−2b′}n}{p}) \frac{1}{p})^{−1}) , \end{matrix}

where b′ = b′(p) denotes the largest integer for which p^{2b′} | 9n. Since n ≡ 1 (mod 8), it follows that 4^{0} = 1 is the highest power of 4 dividing n. This result implies that χ_{2}(n) = \frac{3}{2}. Similarly, we have 9n ≡ 1 (mod 8). Thus, 4^{0} = 1 is the highest power of 4 dividing 9n, which gives χ_{2}(9n) = χ_{2}(n) = \frac{3}{2}. Conversely, it follows from [2, p. 84] that

K(−36n) = K(−4 × 3^{2} × n) = (1 − (\frac{−4n}{3}) \frac{1}{3}) K(−4n).

Since n ≡ 1 (mod 8), it follows from Legendre’s theorem that n can be represented as the sum of three squares of natural numbers. Thus, r_{3}(n) ≠ 0. Dividing through by r_{3}(n) then yields an identity equivalent to

\frac{r_{3}(9n)}{r_{3}(n)} = \frac{3}{(1 − (\frac{−4n}{3}) \frac{1}{3})^{−1}} × \begin{matrix}∏ & p_{2}|9n & (1 + \frac{1}{p} + ⋯ + \frac{1}{p^{b′ −1}} + \frac{1}{p^{b′}} (1 − (^{\frac{−9 p^{−2b′} n}{p}}) \frac{1}{p})^{−1}) \\ ∏ & p_{2}|n & (1 + \frac{1}{p} + ⋯ + \frac{1}{p^{b−1}} + \frac{1}{p^{b}} (1 − (\frac{−p^{−2b}n}{p}) \frac{1}{p})^{−1}) \end{matrix}·

Let p ≠ 3 with p^{2} | n. Thus, b′ = b′(p) is the largest integer for which p^{2b′} | n. Therefore, one obtains b′ = b′(p) = b(p) = b. Furthermore, we have

(\frac{−9 p^{−2b′}n}{p}) = (\frac{3^{2}}{p} ) (\frac{−p^{−2b′}n}{p}) = (\frac{−p^{−2b′}n}{p}) = (\frac{−p^{−2b}n}{p}) ·

For every p ≠ 3 with p^{2} | n, we then have 1 + \frac{1}{p} + ⋯ + \frac{1}{p^{b′ −1}} + \frac{1}{p^{b′}} (1 − (^{\frac{−9 p^{−2b′} n}{p}}) \frac{1}{p})^{−1} =

1 + \frac{1}{p} + ⋯ + \frac{1}{p^{b−1}} + \frac{1}{p^{b}} (1 − (\frac{−p^{−2b}n}{p}) \frac{1}{p})^{−1} . Thus, two cases are evident: if 3^{2} | n, then

\frac{r_{3}(9n)}{r_{3}(n)} = \frac{3}{(1 − (\frac{−4n}{3}) \frac{1}{3})^{−1}} × \frac{1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b′ −1}} + \frac{1}{3^{b′}} (1 − (^{\frac{−9×3^{−2b′} n}{3}}) \frac{1}{3})^{−1}}{1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b−1}} + \frac{1}{3^{b}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1}} ,

Otherwise, 3^{2} does not divide n, so

\frac{r_{3}(9n)}{r_{3}(n)} = \frac{3}{(1 − (\frac{−4n}{3}) \frac{1}{3})^{−1}} × (1 + ⋯ + \frac{1}{3^{b′−1}} + \frac{1}{3^{b′}} (1 − (\frac{−9 × 3^{−2b′}n}{3}) \frac{1}{3})^{−1}).

We now show that in all cases, r_{3}(9n) > \frac{3}{2} r_{3}(n).

• If 3^{2} does not divide n, b′ = b′(3) = 1 is implied to be the largest integer for which 3^{2b′} | 9n. One obtains

\frac{r_{3}(9n)}{r_{3}(n)} = \frac{3}{(1 − (\frac{−4n}{3}) \frac{1}{3})^{−1}} × (1 + \frac{1}{3} (1 − (\frac{−n}{3}) \frac{1}{3})^{−1}) .

We have (1 − (\frac{−4n}{3}) \frac{1}{3}) = 1, \frac{2}{3} or \frac{4}{3} and so _{\frac{3}{(1−(\frac{−4n}{3})\frac{1}{3})^{−1}}} > \frac{3}{2}, which gives the result r_{3}(9n) > \frac{3}{2} r_{3}(n).

• If 3^{2} | n, then b (respectively b′) is the largest integer for which 3^{2b} | n (respectively 3^{2b′} | 9n). Hence,

\begin{aligned}\frac{r_{3}(9n)}{r_{3}(n)} & = \frac{3}{(1 − (\frac{−4n}{3}) \frac{1}{3})^{−1}} × \frac{1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b}} + \frac{1}{3^{b+1}} (1 − (\frac{−9×3^{−2(b+1)}n}{3}) \frac{1}{3})^{−1}}{1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b−1}} + \frac{1}{3^{b}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1}} \\ & = \frac{3}{(1 − (\frac{−4n}{3}) \frac{1}{3})^{−1}} × \frac{1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b}} + \frac{1}{3^{b+1}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1}}{1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b−1}} + \frac{1}{3^{b}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1}} · \end{aligned}

We have (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3}) = 1, \frac{2}{3} or \frac{4}{3}. One obtains the following in all cases:

\frac{1}{3^{b}} + \frac{1}{3^{b+1}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1} ≥ \frac{1}{3^{b}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1} .

This result implies 1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b}} + \frac{1}{3^{b+1}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1} ≥ 1 + \frac{1}{3} + ⋯ + \frac{1}{3^{b−1}} +

\frac{1}{3^{b}} (1 − (\frac{−3^{−2b}n}{3}) \frac{1}{3})^{−1} . Conversely, _{\frac{3}{(1−(\frac{−4n}{3})\frac{1}{3})^{−1}}} > \frac{3}{2}. Thus, we obtain the desired result, r_{3}(9n) > \frac{3}{2} r_{3}(n).

Theorem 6. Every natural number N ≡ 2 (mod 24) can be written as the sum of three numbers of the form ⌊\frac{n^{2}}{3} ⌋ (n ∈ ℕ).

Proof. We may write N = 2 + 24k with k ∈ ℕ. Thus, 3N + 3 = 9(1 + 8k). We now define two sets S_{1} and S_{2} as follows:

S_{1} = {(a, b, c) ∈ ℤ^{3} : a^{2} + b^{2} + c^{2} = 1 + 8k},
S_{2} = {(a, b, c) ∈ ℤ^{3} : a^{2} + b^{2} + c^{2} = 9(1 + 8k)}.

By the definition of r_{3}, we have #S_{2} = r_{3}(9(1 + 8k)) and #S_{1} = r_{3}(1 + 8k). Since 1 + 8k ≡ 1 (mod 8), we apply Lemma 5 to obtain r_{3}(9(1 + 8k)) > \frac{3}{2} r_{3}(1 + 8k) ≥ r_{3}(1 + 8k). One obtains r_{3}(9(1 + 8k)) > r_{3}(1 + 8k), which is equivalent to #S_{2} > #S_{1}. We note that this last result is the key to the proof. Let us define the map

\begin{aligned}f : & S_{1} & ⟶ & S_{2} \\ & (a, b, c) & ⟼ & (3a, 3b, 3c). \end{aligned}

We see easily that f is well defined and injective. Since #S_{2} > #S_{1}, we can find (a, b, c) ∈ S_{2} such that (a, b, c) ∉ f(S_{1}). Furthermore, we have a^{2} + b^{2} + c^{2} = 9(1 + 8k) ≡ 0 (mod 3), then either a^{2} ≡ b^{2} ≡ c^{2} ≡ 1 (mod 3) or a^{2} ≡ b^{2} ≡ c^{2} ≡ 0 (mod 3). The last case cannot hold because one of the elements, a, b and c, is not divisible by 3 ((a, b, c) ∉ f(S_{1})). Thus, a^{2} ≡ b^{2} ≡ c^{2} ≡ 1 (mod 3) and we have

N + 1 = 3(1 + 8k)

= \frac{a^{2}}{3} + \frac{b^{2}}{3} + \frac{c^{2}}{3}

= ⌊\frac{a^{2}}{3} ⌋ + ⌊\frac{b^{2}}{3} ⌋ + ⌊\frac{c^{2}}{3} ⌋ + ⟨\frac{a^{2}}{3} ⟩ + ⟨\frac{b^{2}}{3} ⟩ + ⟨\frac{c^{2}}{3} ⟩.

Since a^{2} ≡ b^{2} ≡ c^{2} ≡ 1 (mod 3), then ⟨\frac{a^{2}}{3} ⟩ + ⟨\frac{b^{2}}{3} ⟩ + ⟨\frac{c^{2}}{3} ⟩ = \frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1, which gives

N = ⌊\frac{a^{2}}{3} ⌋ + ⌊\frac{b^{2}}{3} ⌋ + ⌊\frac{c^{2}}{3} ⌋. We replace (a, b, c) ∈ ℤ^{3} by (|a|, |b|, |c|) ∈ ℕ^{3} to obtain the

desired solution. The conjecture is proven.

3 Acknowledgments

The authors would like to thank the editor and the anonymous reader for their invaluable comments.

This work was supported by Académie Hassan 2 under the project “Mathématiques et Applications: cryptographie” and URAC6-CNRST.

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] P. T. Bateman, On the representation of a number as the sum of three squares, Trans. Amer. Math. Soc. 71 (1951), 70–101.

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

2010 Mathematics Subject Classification: Primary 11B13. Keywords: additive base, Legendre’s theorem, representation of an integer as the sum of three squares.

Received July 25 2013; revised versions received July 31 2013; November 22 2013; December 30 2013. Published in Journal of Integer Sequences, December 30 2013. Revision, January 3 2014.

Return to Journal of Integer Sequences home page.