PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 63 (77), 1998, 21–25

ATKIN’S THEOREM ON PSEUDO-SQUARES

R. Balasubramanian and D.S. Ramana

Communicated by Aleksandar Ivić

Abstract. We give an elementary proof of a theorem of A.O.L. Atkin on psuedo-squares. As pointed out by Atkin, from this theorem it immediately follows that there exists an infinite sequence of positive integers, whose j th term s(j) satisfies s(j) = j^{2} + O(log(j)), such that the set of integers representable as a sum of two distinct terms of this sequence is of positive asymptotic density.

1. Introduction. In [1] Atkin proves the existence of an infinite sequence of positive integers, whose j th term s(j) satisfies s(j) = j^{2} + O(log(j)), such that the set of integers representable as a sum of two distinct terms of this sequence is of positive asymptotic density. See also [2, Ch. 3, Sec. 2, p. 113]. Atkin deduces this result as an immediate consequence of the following theorem.

Let N and M be positive integers such that M satisfies a/ log(N) ≤ M ≤ b/ log(N) for some positive real numbers a and b. This assumption will hold throughout.

Let L(N, M) denote the set of mappings from the set {1, 2,…, N} into the set of integers in the closed interval [−M, M]. For any λ in L(N, M), let ℑ(N, λ) denote the set {(N +1)^{2}+λ(1),…, (N +k)^{2}+λ(k),…, (2N)^{2}+λ(N)}. Let R(N, λ) denote the number of integers representable as a sum of two distinct elements of ℑ(N, λ).

Theorem. For sufficiently large N there exists λ in L(N, M) such that R(N, λ) ≫ N^{2}.

Using a combinatorial argument, Atkin reduces the proof of this theorem to the estimation of a certain integral. This estimation is then done in [1] by the Hardy–Littlewood method.

The purpose of this note is to point out that arranging the combinatorial content of [1] differently yields a simple and elementary proof of the above theorem.

AMS Subject Classification (1991): Primary 11B13

2. Proof of the theorem. For any integer k and any λ in L(N, M) let r(k, λ) denote the number of ordered pairs (s, t) of distinct elements of the set ℑ(N, λ) such that s + t is k. Clearly one has

∑_{k∈Z} r(k, λ) = N^{2} − N  (1)

R(N, λ) is the number of integers k for which r(k, λ) ≠ 0. Therefore, if the sum ∑ r^{2}(k, λ) taken over all integers k, is denoted by T (N, λ), the Cauchy– Schwarz inequality gives

R(N, λ) ≥ (N^{2} − N)^{2}/T (N, λ)  (2)

Inequality (2) reduces the proof of the theorem to that of Lemma 1.

Lemma 1. For sufficiently large N there exists λ in L(N, M) such that T (N, λ) ≪ N^{2}.

Lemma 1 is an immediate corollary to the following lemma.

Lemma 2. For sufficiently large N the arithmetic mean A(N, M) of T (N, λ) over all λ in L(N, M) satisfies A(N, M) ≪ N^{2}.

Proof: For any integer k let P (N, k) be the number of ordered quadruples q = (q_{1}, q_{2}, q_{3}, q_{4}) of distinct elements of the set {1, 2,…, N} satisfying (3), below. We rewrite (3) as (4).

(N + q_{1})^{2} + (N + q_{2})^{2} − (N + q_{3})^{2} − (N + q_{4})^{2} = k  (3)
(q_{1} − q_{3})(2N + q_{1} + q_{3}) = (q_{4} − q_{2})(2N + q_{2} + q_{4}) + k  (4)

Note that P (N, k) = P (N, −k) for all integers k.

Assume k ≥ 0. Denote the right-hand side of (4) by h + k. We have the following relations.

\sqrt{|h + k|} ≤ 2N + q_{1} + q_{3} ≤ 4N, 2N + q_{1} + q_{3} divides h + k  (5)
\sqrt{|h|} ≤ 2N + q_{2} + q_{4} ≤ 4N, 2N + q_{2} + q_{4} divides h  (6)
−3N^{2} ≤ h ≤ 3N^{2}  (7)

Motivated by (5), (6) and (7) we define, for any integer h, τ_{1}(h) to be the number of positive integers s satisfying \sqrt{|h|} ≤ s ≤ 4N, s divides h. It is immediate that

P (N, k) ≤ ∑_{−3N^{2}≤h≤3N^{2}} τ_{1}(h)τ_{1}(h + |k|) for all integers k  (8)

In Section 2, assuming N is sufficiently large, we will prove the following inequality.

A(M, N) ≤ 2(N^{2} − N) + \frac{1}{2M + 1} ∑_{0≤|k|≤4M} P (N, k)  (9)

To finish the proof of Lemma 2 we will use the following estimates whose proofs will be given in Section 3. These estimates have perhaps already appeared in the literature in another context. For the lack of suitable references we include their proofs.

∑_{−3N^{2}≤h≤3N^{2}} τ_{1}^{2}(h) ≪ N^{2} log(N)  (10)
∑_{1≤k≤4N} ∑_{−3N^{2}≤h≤3N^{2}} τ_{1}(h)τ_{1}(h + k) ≪ N^{2}M  (11)

Combining (8)–(11) we obtain (12) below, for sufficiently large N.

A(N, M) ≪ N^{2}(1 + \frac{log(N)}{M}) ≪ N^{2}  (12)

This completes the proof of Lemma 2.

3. An inequality for A(N, M). Lemma 3. For sufficiently large N inequality (9) holds.

Proof. Let ℘(N) denote the set of all ordered quadruples q = (q_{1}, q_{2}, q_{3}, q_{4}) of elements of the set {1, 2,…, N} satisfying q_{1} ≠ q_{2}, q_{3} ≠ q_{4}. We will use the letter q to denote a general element of ℘(N). We will denote L(N, M) by L and it’s cardinality by |L|.

From the definition of T (N, λ) given in Section 1 it follows that T (N, λ) is the number of q satisfying (13) below for a given λ. We rewrite (13) as (14).

(N +q_{1})^{2}+λ(q_{1})+(N +q_{2})^{2}+λ(q_{2}) = (N +q_{3})^{2}+λ(q_{3})+(N +q_{4})^{2}+λ(q_{4}) (13)
(N +q_{1})^{2}+(N +q_{2})^{2}−(N +q_{3})^{2}−(N +q_{4})^{2} = λ(q_{4})+λ(q_{3})−λ(q_{1})−λ(q_{2}) (14)
(N + q_{1})^{2} + (N + q_{2})^{2} − (N + q_{3})^{2} − (N + q_{4})^{2} = k(q)  (15)

For any q, we denote the left hand side of (14) by k(q) and denote by m(q) the number of λ in L for which (14) is satisfied by the given q. It then follows that

∑_{λ∈L} T (N, λ) = ∑_{q∈℘(N)} m(q)  (16)

Remark 1. If |k(q)| > 4M then m(q) = 0.

Since λ takes values in [−M, M] it follows that the right hand side of (14) lies in [−4M, 4M]. Hence the remark.

Remark 2. If |k(q)| ≤ 4M and k(q) ≠ 0 then q_{1}, q_{2}, q_{3}, q_{4} are all distinct. Suppose q_{1} = q_{3}. If q_{2} ≠ q_{4}, then the left hand side of (15) is of the order N

while the right hand side if of the order M. Since M is o(N) this gives a contradiction for sufficiently large N. Hence q_{2} = q_{4} and therefore k(q) = 0 contradicting k(q) ≠ 0. Thus q_{1} ≠ q_{3}. In a similar manner we dispose off all possibilities of equality between q_{1}, q_{2}, q_{3}, q_{4} till we arrive at the remark. Note that q_{1} = q_{2} or q_{3} = q_{4} are impossible by definition of ℘(N).

Let ℘_{1}(N) consist of all those q with either q_{1} = q_{3} and q_{2} = q_{4} or q_{1} = q_{4} and q_{2} = q_{3}. The cardinality of ℘_{1}(N) is clearly 2(N^{2} − N). Further k(q) = 0 for q in ℘_{1}(N). Also one has

Remark 3. If k(q) = 0 then either q_{1}, q_{2}, q_{3}, q_{4} are distinct or q is in ℘_{1}(N). Combining the above remarks we have (17), below,where ∑^{1} denotes that

the summation is only over those q with q_{1}, q_{2}, q_{3}, q_{4} distinct.

∑_{q∈℘(N)} m(q) = ∑_{q∈℘_{1}(N)} m(q) + ∑_{0≤|k|≤4M}^{1}m(q)  (17)

Remark 4. If q is in ℘_{1}(N) then m(q) is |L|.

Remark 5. If the q_{1}, q_{2}, q_{3}, q_{4} are distinct then m(q) is at most |L|/2M + 1. When q_{1}, q_{2}, q_{3}, q_{4} are distinct then m(q) is at most the number of mappings

from an N − 1 element subset of {1, 2,…, N} into the set of integers in the closed interval [−M, M]. This in our notation is |L|/2M + 1. Hence Remark 5.

Combining the Remarks (4)–(6) with (17) and recalling the definition of P (N, k) from Section 1, we obtain the inequality (9).

4. Upper bounds for the τ_{1} sums. Here we prove (10) and (11). First a lemma.

Lemma 4. We have for all integers k ≥ 0 the following inequality

∑_{−3N^{2}≤h≤3N^{2}} τ_{1}(h)τ_{1}(h + k) ≤ 4 ∑_{\begin{matrix}1≤s≤4N \\ 1≤t≤4N \end{matrix}}^{k} gcd(s, t)  (18)

Above ∑^{k} indicates that the summation is only over those (s, t) with gcd(s, t) dividing k. Note that when k is 0, ∑^{k} is the same as ∑.

Proof. Recalling the definition of τ_{1} and interchanging the summations involved we obtain (19), below, where ∑^{1} indicates that the summation is only over those h in [−3N^{2}, 3N^{2}] satisfying the conditions h ≡ 0 (mod s) and h + k ≡ 0 (mod t). Clearly, the conditions h ≡ 0 (mod s) and h + k ≡ 0 (mod t) imply that gcd(s, t) divides k. Hence the appearance of ∑^{k} in (19).

∑_{−3N^{2}≤h≤3N^{2}} τ_{1}(h)τ_{1}(h + k) ≤ ∑_{\begin{matrix}1≤s≤4N \\ 1≤t≤4N \end{matrix}}^{k} ∑_{\begin{matrix}1≤\sqrt{|h|}≤s \\ 1≤\sqrt{|h+k|}≤t \end{matrix}}^{1} 1  (19)

Assume that s ≥ t. The Chinese Remainder Theorem gives an integer p such that for any h satisfying the conditions h ≡ 0 (mod s) and h + k ≡ 0 (mod t), h satisfies h ≡ p (mod lcm(s, t)). If, in addition, 1 ≤ \sqrt{|h|} ≤ s then there are at most 2s^{2}/ lcm(s, t) + 1 such h. With this we obtain the inequalities (20), below. When s > t we argue with h + k in place of h and t in place of s to obtain the same inequalities. Combining (19) and (20), Lemma 4 follows.

∑_{\begin{matrix}1≤\sqrt{|h|}≤s \\ 1≤\sqrt{|h+k|}≤t \end{matrix}}^{1}1 ≤ (\frac{2s^{2}}{lcm(s, t)} + 1) = (\frac{2s}{t} gcd(s, t) + 1) ≤ 4 gcd(s, t)  (20)

To obtain (10) and (11) we note the following inequalities.

∑_{\begin{matrix}1≤s≤4N \\ 1≤t≤4N \end{matrix}} gcd(s, t) = ∑_{1≤l≤4N} l ∑_{\begin{matrix}1≤s≤4N \\ 1≤t≤4N \end{matrix}}^{l}1 ≤ ∑_{1≤l≤4N} l(\frac{4N}{l} )^{2} ≪ N^{2} log(N)  (21)

where ∑^{l} denotes that the summation is only over those (s, t) for which gcd(s, t) is l.

∑_{1≤k≤4M} ∑_{\begin{matrix}1≤s≤4N \\ 1≤t≤4N \end{matrix}}^{k}gcd(s, t) = ∑_{1≤m≤4N}m ∑_{\begin{matrix}1≤s,t≤4N \\ 1≤k≤4M \end{matrix}}^{m} 1 ≤ ∑_{1≤m≤4N}m(\frac{4M}{m} )(\frac{4N}{m} )^{2}≪N^{2}M

(22)

where ∑^{m} indicates that the summation is only over those (k, s, t) such that gcd(s, t) is m and m divides k.

Combining (21) and (22) with Lemma 4 we obtain (10) and (11).

5. Acknowledgements. The basic idea that Lemma 2 implies Lemma 1 is in [1]. We thank Dr. Mohan Nair, Prof. A.O.L. Atkin and Mr. Jishnu Biswas.

References

1. A.O.L. Atkin, On Psuedo-squares, Proc. London Math. Soc. (A)(3) 14 (1965), 22–27.

2. H. Halberstam and K.F. Roth, Sequences, Vol. 1, Oxford University Press, 1966.

The Institute of Mathematical Sciences (Received 19 01 1998) C.I.T. Campus, Taramani Chennai 600113 India

   balu@imsc.ernet.in
   suri@imsc.ernet.in