Sums of two squares: positive lower density? [duplicate]

Question

This question was (indirectly) raised in this post.

A set $A\subseteq \mathbb{N}$ has positive lower density if $$\text{lim inf}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n} > 0.$$

Does the set $\{x^2+y^2: x,y \in \mathbb{N}\}$ have positive lower density?

Answer 1

As pointed out in the comments above, the answer is already contained in the other post linked in the OP. However, the result can be proven independently of Landau's work.

To see how, denote by $w_k(X)$, for every integer $k \ge 1$ and $X \subseteq \mathbf N$, the number of residues $r \in [\![0, k-1 ]\!]$ such that $X \cap (k \cdot \mathbf N + r) \ne \emptyset$ (see the note below), and let $\mathsf{d}_\ast$ and $\mathsf{d}^\ast$ be the functions $\mathcal P(\mathbf N) \to [0,\infty[$ taking a subset of $\mathbf N$ to its lower and upper asymptotic density, respectively.

Of course, $\mathsf{d}_\ast(X) \le \mathsf{d}^\ast(X)$ for all $X$, and it is not difficult to prove that $$\mathsf{d}^\ast(X) \le \liminf_{k \to \infty} \frac{w_k(X)}{k};$$ thus, letting $(q_k)_{k \ge 1}$ be the natural enumeration of the primes $\equiv 3 \bmod 4$, we find that $$\mathsf{d}^\ast(X) \le \liminf_{k \to \infty} \prod_{i=1}^k \frac{w_{q_i^2}(X)}{q_i^2},$$ where we have used that $w_{mn}(X) \le w_m(X) w_n(X)$ for all coprime $m,n \in \mathbf N^+$.

It follows that $\mathsf{d}_\ast(Q_2) = \mathsf{d}^\ast(Q_2) = 0$, since for each prime $q \equiv 3 \bmod 4$ we have $w_{q^2} \le q^2 - q + 1$ (just consider that $q \mid x^2 + y^2 $ for some $x,y \in \mathbf Z$ iff $\gcd(x,y)$ is divided by $q$, because $-1$ is not a quadratic residue $\bmod q$), and on the other hand, $$\lim_{k \to \infty} \prod_{i = 1}^k \left(1 - \frac{q_k-1}{q_k^2}\right) = 0.$$ Here, $Q_2 := \{x^2 + y^2: x, y \in \mathbf N\}$.

Note. A better definition of $w_k(X)$ is in terms of those residues $r \in [\![0, k-1 ]\!]$ for which the upper asymptotic density of $X \cap (k \cdot \mathbf N + r)$ is positive, but this wouldn't make any difference here.

Edit (Jun 16, 2015). For those who may be interested, I'd like to add a complement to my previous answer, as the above ideas can be used to prove a sensibly more general result.

To start with, let $\mathbf H$ be either $\mathbf Z$, $\mathbf N$, or $\mathbf N^+$ (*), and let an upper quasi-density (on $\mathbf H$) be a function $\mu^\ast: \mathcal P(\mathbf H) \to \mathbf R$ such that, for all $X,Y \subseteq \mathbf H$ and $h,k \in \mathbf N^+$, the following hold:

1. $\mu^\ast(\mathbf H) = 1$;
2. $\mu^\ast(X \cup Y) \le \mu^\ast(X) + \mu^\ast(Y)$;
3. $\mu^\ast(k \cdot X + h) = \frac{1}{k} \mu^\ast(X)$;
4. $\mu^\ast(X) \le 1$.

If, in addition, $\mu^\ast$ is monotonic, viz. $\mu^\ast(X) \le \mu^\ast(Y)$ whenever $X \subseteq Y \subseteq \mathbf H$, then we call $\mu^\ast$ an upper density (on $\mathbf H$), in which case condition 4 is implied by the others.

It can be shown that the upper asymptotic (or natural), upper Banach (or uniform), and upper logarithmic density, as well as Buck's measure density [1] and the analytic upper density [2, Part III, Section 1.3] are upper densities according to the definition above.

Upper quasi-densities are interesting widgets, I believe, insofar as they introduce a certain amount of unification into the study of densities (or "densitology", to put it in the words of Georges Grekos). The OP serves a benchmark in this sense, as we have the following:

Theorem. Fix $a,b,c \in \mathbf H$, set $X := \{ax^2 + bxy + cy^2: x, y, z \in \mathbf H\}$ and $D := b^2 - ac$, and let $\mu^\ast$ be an upper quasi-density on $\mathbf H$. Then $\mu^\ast(X) = 0$ if $D$ is not a perfect square or $D = 0$, while $\mu^\ast(X) > 0$ if (i) $D$ is a nonzero perfect square and $ac = 0$, or (ii) $D$ is a nonzero perfect square, $ac \ne 0$, and $\mathbf H = \mathbf Z$.

The proof of this relies, at least in part, on a natural extension of the criterion I used above to answer the question in the OP (those interested may see [2, Theorem 4] for details), and shows that if $X$ is the set of all integers of the form $x^2 + y^2$ with $x,y \in \mathbf H$ then $\mu^\ast(X) = 0$, uniformly with respect to $\mu^\ast$, whenever $\mu^\ast$ is an upper quasi-density, which I don't think has any chance to be proved by an argument that relies on Landau's estimate (or any other sort of analytic estimate in the spirit of Landau's).

For the record, the missing cases in the theorem (namely, $\mathbf H = \mathbf N$ or $\mathbf N^+$, $D$ a nonzero perfect square, and $ac \ne 0$) are more tricky, in that the result is no longer uniform with respect to the actual choice of $\mu^\ast$, which is part of the reason why I mentioned that the choice of $\mathbf H$ leads to different scenarios.

Notes.

(*) Different choices of $\mathbf H$ give rise to different scenarios, and I don't know whether the case $\mathbf H = \mathbf N^+$ can be reduced to the case $\mathbf H = \mathbf N$ (which would be nice, if true).

Bibliography.

[1] R. C. Buck, The Measure Theoretic Approach to Density, Amer. J. Math. 68 (1946), No. 4, 560-580.

[2] P. Leonetti and S.T., On the notions of upper and lower density, preprint (arXiv:1506.04664)

[3] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge Stud. Adv. Math. 46, Cambridge Univ. Press, 1995.