Sorry if this is trivial: it is well-known that the number of sums of two squares less than $X$ is asymptotic to $CX/\log(X)^{1/2}$ for some $C$. Is this a general phenomenon ? More precisely, if $A$ and $B$ are subsets of the natural numbers whose counting functions $|A(X)|$ and $|B(X)|$ are $O(X^{1/2})$, it it true that $|(A+B)(X)|$ is $o(X)$ (or perhaps always $O(X/\log(X)^{1/2})$ ?


This is false in general. If you take $A$ and $B$ to be sets consisting of numbers with only 1's in their even (respectively odd) positions up to $2^{2n}$, then $|A|=|B|=2^n$ but $|A+B|=2^{2n}$.


Here are four approaches to find counter examples, three of them even work in the special case $A=B$.

Together all this means that cases like sums of two squares (or more generally quadratic forms in the integers create an algebraic reason that those integers that can be written in this form have a representation number (say $r_2(n)/4$ for sums of two squares) which is much larger than for random sets.

One could ask vice versa, which conditions on $A$ with counting function $\gg \sqrt{X}$ allow that $(A+A)(X)=o(X)$? Examples would be $A$: contains large subsets which come from linear or quadratic polynomials. What other examples?

Now the four types of counter examples:

A) The elements lie close to squares: Atkin proved that it is possible to use elements $s_j=j^2+O(\log j)$ such that the sumset of these pseudo squares has positive density. (See references 1) and 2).)

B) Another approach is from (infinite) Sidon sets, which have by definition the property that all sums $a_i+a_j$ are distinct, or more generally $B_2(g)$ sequences, with the number of representations as $a_i+a_j$ bounded by $g$. (Then $A(X)=O(\sqrt{X})$ follows.)

Erdos constructed (see for example Krückeberg or Cilleruelo and Trujillo below): an infinite Sidon set $A$ with counting function $A(X)$ and $\lim \sup_{x \rightarrow \infty} \frac{A(X)}{\sqrt{X}}\geq \frac{1}{2}$. By the Sidon property the sumset $A+A$ must have positive density at least infinitely often, which contradicts $A(X)=o(X)$. (To do this with $\lim \inf$ is much harder and unknown, see 5) below.)

(Krückeberg improved the constant of Erdos, Cilleruelo and Trujillo generalized it to $B_2(g)$ sequences.

C) A third related approach are "thin bases". A set $A\subset\mathbb{N}_0$ is said to be a basis of order 2 if every positive integer can be written as a sum of 2 (not necessarily distinct) elements of $A$, and is called "thin" if $A(X)=O(\sqrt{X})$. Stöhr, Raikov and many others proved the existence of such bases. Moreover, they actually have so called UR-bases, where $A=B \cup C$, every element can be written in a unique way as $b+c, b \in B, c\in C$.

(The Stöhr-Raikov constructions are digit based, and thus related to Gjergji Zaimi's solution. Nathanson (and others) have also non-digit based constructions.)

D) It follows by work of Sarnak, https://mathscinet.ams.org/mathscinet-getitem?mr=1472786 and Eskin, Margulis and Mozes https://mathscinet.ams.org/mathscinet-getitem?mr=2153398

that many quadratic forms with irrational coefficients and integer variables generate a positive density of the integers, in particular this works with $\lfloor x^2+\alpha y^2\rfloor$, if $\alpha$ is not extremely well approximable. (Here algebraic irrationals such as $\alpha=2$ are admissable.) Choose $A$ as the set of squares and $B=\{\lfloor \alpha y^2\rfloor ; y \in \mathbb{N} \}$.

See also this MO post: Distribution of $a^2+\alpha b^2$


1) A.O.L. Atkin, On Pseudo-squares, Proc. LMS 14 (1965), 22-27

2) Atkin's theorem on pseudo-squares, R. Balasubramanian and D.S. Ramana PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.) Vol. 63 (77), pp. 21-25 (1998)


3) Krückeberg. B2-Folgen und verwandte Zahlenfolgen, Journal für die reine und angewandte Mathematik (1961) Volume: 206, page 53-60 https://eudml.org/doc/150472

4) Javier Cilleruelo, Carlos Trujillo. Infinite $B_2[g]$ sequences Israel Journal of Mathematics, December 2001, Volume 126, Issue 1, pp 263–267. https://doi.org/10.1007/BF02784156

5) Gowers's webblog (2012): https://gowers.wordpress.com/2012/07/13/what-are-dense-sidon-subsets-of-12-n-like/

6) A. Stöhr

Eine Basis h-ter Ordnung für die Menge aller natürlichen Zahlen, Mathematische Zeitschrift (1937) Volume: 42, page 739-743


7) D. Raikov Über Basen der natürlichen Zahlenreihe Mat. Sb. N.S., 2 (44) (1937), pp. 595-597. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=5584&option_lang=eng

8) M.B. NathansonNathanson, Thin bases in additive number theory Discrete Math. 312 (2012), no. 12-13, 2069–2075.


9) Eskin, Margulis, Mozes, Quadratic forms of signature (2,2) and eigenvalue spacings on rectangular 2-tori. Ann. of Math. (2) 161 (2005), no. 2, 679–725.

  • $\begingroup$ Thanks to both for those detailed answers. $\endgroup$ Sep 1 '19 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.