Landau–Ramanujan theorem: the density of sums of two squares is $\\Theta(x/\\sqrt{\\log x})$

Statement

Let $S(x)$ denote the number of positive integers $n\le x$ that can be written as a sum of two integer squares, $n=a^2+b^2$ with $a,b\in\mathbb Z_{\ge0}$.

Landau–Ramanujan theorem (Landau, 1908; independently Ramanujan, 1913). $$S(x) \sim K\,\frac{x}{\sqrt{\log x}} \qquad (x\to\infty),$$ where $K$ is the Landau–Ramanujan constant, $$K = \frac{1}{\sqrt2}\prod_{\substack{p\text{ prime}\\ p\equiv3\,(\mathrm{mod}\,4)}}\Big(1-\frac1{p^2}\Big)^{-1/2} \;=\; \frac{\pi}{4}\prod_{\substack{p\text{ prime}\\ p\equiv1\,(\mathrm{mod}\,4)}}\Big(1-\frac1{p^2}\Big)^{1/2} \;\approx\; 0.76422365358922066299\ldots$$ (en.wikipedia.org/wiki/Landau–Ramanujan_constant; mathworld.wolfram.com/Landau-RamanujanConstant.html; OEIS A064533).

Equivalently: $\lim_{x\to\infty} S(x)\sqrt{\log x}/x = K$. Refined versions give a full asymptotic expansion in inverse powers of $\log x$: $$S(x) = \frac{Kx}{\sqrt{\log x}}\Big[1+\frac{c_1}{\log x}+\frac{c_2}{(\log x)^2}+\cdots\Big]$$ with explicitly computable constants $c_j$ (mathworld.wolfram.com/Landau-RamanujanConstant.html). Ramanujan's own 1913 form (in his first letter to Hardy) was the integral version $S(x)\sim K\int_2^x dt/\sqrt{\log t}$, with claimed error $O(x/\log x)$.

Underlying arithmetic characterization (Fermat/Euler, prerequisite fact, not itself the theorem). A positive integer $n$ is a sum of two squares iff every prime $p\equiv3\pmod4$ divides $n$ to an even power. (Primes $p\equiv1\pmod4$, and $p=2$, are unrestricted.) This is what makes $S(x)$ countable via a multiplicative/Euler-product machine in the first place.

Facts

- The set of sums of two squares has natural density zero, but at the slowest possible non-trivial rate. $S(x)/x\to0$, yet $S(x)/x^{1-\epsilon}\to\infty$ for every $\epsilon>0$ — the decay is only by a factor $1/\sqrt{\log x}$, not a power of $x$. This "just barely density zero" behavior is the signature output whenever this theorem is invoked. - Contrast with 3 and 4 squares (why "two" is special). By Lagrange's four-square theorem every $n$ is a sum of four squares ($S_4(x)=x$, density 1); by the three-square theorem almost every $n$ is a sum of three squares (density 1, exceptions are exactly $n=4^a(8b+7)$). Only for two squares does a genuine sub-polynomial-but-superpolylog density gap appear — this is the unique "interesting" case in the $k$-squares family and the reason it needs its own named theorem/constant. - Multiplicative skeleton (Brahmagupta–Fibonacci identity). If $m=a^2+b^2$ and $n=c^2+d^2$ then $mn=(ac-bd)^2+(ad+bc)^2$ — the set of sums of two squares is closed under multiplication, mirroring the fact that a Gaussian integer $a+bi$ of norm $n$ exists iff $n$'s prime factorization avoids odd powers of inert primes ($p\equiv3\bmod4$). This multiplicativity is what makes the counting function amenable to an Euler-product/Dirichlet-series treatment (see Technique). - Dirichlet series encoding. The representation-count function $r_2(n)=\#\{(a,b)\in\mathbb Z^2: a^2+b^2=n\}$ has generating Dirichlet series $\sum_{n\ge1} r_2(n)n^{-s} = 4\zeta(s)L(s,\chi_{-4})$, where $\chi_{-4}$ is the non-principal character mod 4 (equivalently $L(s,\chi_{-4})=\beta(s)$, the Dirichlet beta function). This equals $4\zeta(s)\beta(s)$, the Epstein zeta function of the quadratic form $x^2+y^2$ over $\mathbb Z[i]$ (grokipedia.com, cross-checked against the standard theta-series/Mellin-transform identity for the Gaussian lattice). - **Connection to $\sqrt{\log x}$: the exponent $1/2$ traces to $\zeta(s)L(s,\chi_{-4})$ having, near $s=1$, a factor of $L(s,\chi_{-4})$ (regular, non-vanishing) times $\zeta(s)$ (simple pole) — but the *sum-of-two-squares indicator* series (as opposed to the representation-count series $r_2(n)$) is built instead from an Euler product that behaves like $\zeta(s)^{1/2}$ near $s=1$ (each inert prime $p\equiv3\bmod4$ contributes a factor $(1-p^{-2s})^{-1/2}$ rather than $(1-p^{-s})^{-1}$, since only *even* powers of $p$ are allowed). A pole of order $1/2$ (a branch-point / half-order singularity, not a genuine pole) at $s=1$ is exactly what produces a $1/\sqrt{\log x}$ correction to the $x$-scale main term under Tauberian/Perron inversion, in contrast to an ordinary simple pole (order 1) which would give a density-$c$ result with no logarithmic correction at all. - Generalizes to other binary quadratic forms of class number 1. For the Eisenstein-integer form $x^2+xy+y^2$ (Loeschian numbers), the analogous count is $\sim c\,x/\sqrt{\log x}$ with $c = \frac{3^{-1/4}}{4}\prod_{p\equiv2(3)}(1-p^{-2})^{-1/2}\approx0.60684$ — same $\sqrt{\log x}$ shape, different constant, same proof architecture (grokipedia.com, cross-referencing class-number-1 discriminants). This signals the theorem is really about "integers representable by a fixed positive-definite binary quadratic form with an inert-prime obstruction," of which $x^2+y^2$ is the flagship case. - Two structurally different proofs exist beyond Landau's original complex-analytic one: (i) H. Iwaniec (1974) gave a sieve-theoretic proof avoiding complex analysis entirely (upper/lower bound sieve, no contour integration); (ii) A. Selberg gave a short proof of the analogous asymptotic restricted to *squarefree* sums of two squares. Both are cited by Grokipedia's synthesis but their exact bibliographic details were not independently verified here — treat as leads, not confirmed citations. - Used live in this wiki's own Erdős-problem pages as a density input, not as the object of study itself — always invoked as a known black-box fact to bound/explain some *other* combinatorial quantity: - Erdős #89 — distinct distances in the plane (Erdős distinct distances problem): the conjectured-tight lower bound $\Omega(n/\sqrt{\log n})$ for distinct distances in an $n$-point set is witnessed by a $\sqrt n\times\sqrt n$ integer grid, and the grid's optimality is *exactly* the Landau–Ramanujan theorem: every squared Euclidean distance in the grid is (up to scaling) a sum of two squares, and only $\Theta(x/\sqrt{\log x})$ integers up to $x$ have that form, so the grid cannot realize more than $\Theta(n/\sqrt{\log n})$ distinct squared distances (wiki/problems/89.md, citing Sheffer survey arXiv:1406.1949 §1–2). - erdos/773 (Sidon subset of $\{1,4,9,\ldots,N^2\}$): Alon–Erdős (1985) derive the upper bound $|A|\ll N/(\log N)^{1/4}$ for such a Sidon set directly from Landau's density result — a Sidon condition among squares forces the *sums* $a^2+b^2$ ($a,b\in A$) to be mostly distinct, and since there are only $O(N^2/\sqrt{\log N})$ available sums-of-two-squares values below $\sim N^2$ (this theorem, with $x=N^2$, giving the extra $\sqrt{\log N}$-type saving that becomes a $(\log N)^{1/4}$ after taking square roots in the parameter conversion), a large Sidon set of size $\gg N/(\log N)^{1/4}$ would produce more distinct pairwise sums than there is room for. (Direct quote: "since (as shown by Landau) the density of the sums of two squares decays like $(\log N)^{-1/2}$" — erdosproblems.com/773.) - erdos/222 (gaps between consecutive sums of two squares $n_1<n_2<\cdots$): the whole problem — bounding $n_{k+1}-n_k$ — is a second-order, pointwise question about the *same* sequence this theorem controls on average. Erdős (1951) proved $n_{k+1}-n_k\gg\log n_k/\sqrt{\log\log n_k}$ infinitely often (improved by Richards 1982 to $\limsup(n_{k+1}-n_k)/\log n_k\ge1/4$, then to $\ge0.868\ldots$ by Dietmann–Elsholtz–Kalmynin–Konyagin–Maynard 2022); the upper bound $n_{k+1}-n_k\ll n_k^{1/4}$ is due to Bambah–Chowla (1947). This is the still-open problem (erdosproblems.com/222, fetched 2026-07-02) that asks for the fine-scale/gap structure the Landau–Ramanujan asymptotic only controls in the mean — an open direct descendant worth flagging for anyone treating this theorem as "solved and done": the *average-spacing* consequence $x/S(x)\sim\sqrt{\log x}/K$ is fully understood, but the *worst-case-gap* question is not.

Technique

How the theorem is proved (the transferable engine — Euler product with a half-order singularity, inverted via Perron/Tauberian machinery):

1. Reduce counting to a multiplicative/Euler-product object. Because "$n$ is a sum of two squares" is characterized purely by parity conditions on prime exponents (Fermat/Euler two-square theorem), the indicator function of $S$ is multiplicative up to the even/odd-exponent constraint at primes $\equiv3\bmod4$. This lets you write a Dirichlet series $F(s)=\sum_{n\in S} n^{-s}$ as an Euler product: unrestricted factors $(1-p^{-s})^{-1}$ at $p=2$ and $p\equiv1\bmod4$, but *even-exponents-only* factors $(1-p^{-2s})^{-1}\cdot(\text{normalization})$ — equivalently $\sim(1-p^{-s})^{-1/2}$ in the relevant regime — at $p\equiv3\bmod4$. 2. Identify the order of the singularity at $s=1$. Compare $F(s)$ to $\zeta(s)$: because half of all primes (by Dirichlet's theorem on primes in arithmetic progressions, split evenly between $\equiv1$ and $\equiv3\bmod4$) contribute a "half-strength" Euler factor, $F(s)$ behaves like $\zeta(s)^{1/2}\times(\text{holomorphic, non-vanishing factor})$ near $s=1$ — a branch-point singularity of order $1/2$, not a simple pole (order 1). This is the crux fact: it is the exponent $1/2$ here, not any deeper arithmetic, that produces the $1/\sqrt{\log x}$ (rather than a constant-density $O(x)$) asymptotic. 3. Invert via Perron's formula / contour integration around the singularity. $S(x)=\sum_{n\le x, n\in S}1$ is recovered from $F(s)$ by a Perron-type contour integral $\frac{1}{2\pi i}\int F(s)x^s\,ds/s$. Because the integrand's dominant singularity at $s=1$ is a *branch point of order $1/2$* rather than a pole, the standard "residue at the pole gives the main term" step is replaced by a finer local analysis (Landau's original method: careful complex-analytic estimate of the contour integral near the branch point using Gamma-function asymptotics; modern treatments use a Selberg–Delange-type theorem for Dirichlet series with a $\zeta(s)^{\alpha}$-type singularity of general real order $\alpha$, here $\alpha=1/2$) — this produces the extra $1/\Gamma(1/2)\cdot x/\sqrt{\log x}$-type main term directly, with the Landau–Ramanujan constant $K$ emerging as the value of the non-singular Euler factor at $s=1$, normalized by the Gamma-function constant from the singularity analysis. 4. WHEN this technique applies — the general pattern. Any time you need the count of integers $\le x$ satisfying a *local (prime-by-prime), multiplicatively-defined constraint that excludes a positive-density set of primes from appearing to odd powers* (or more generally restricts a positive proportion of Euler factors to a fractional power $\alpha\in(0,1)$ of the "generic" factor), the resulting counting function has asymptotic order $x/(\log x)^{1-\alpha}$ — here $\alpha=1/2$ giving $x/\sqrt{\log x}$. This is the reusable machine (the "Landau–Selberg–Delange method" in its modern form) for any density-zero-but-slowly-decaying set defined by congruence obstructions at a positive-density subset of primes: sums of two squares ($\alpha=1/2$), values of other class-number-1 binary quadratic forms ($\alpha=1/2$, different constant), numbers with all prime factors from a fixed set of Dirichlet-density $\delta$ (giving exponent $1-\delta$), etc. 5. What this technique does NOT do. It is a *pointwise-in-aggregate/counting-function* tool — it tells you how many elements of $S$ lie below $x$, and by inversion the *average* gap $\bar g(x)\sim\sqrt{\log x}/K$ between consecutive elements. It gives no information about the worst-case (extremal) gap between consecutive elements of $S$ — that is a genuinely different, harder, still partly-open question (see erdos/222 above) requiring separate combinatorial/sieve arguments (Erdős's original gap lower bound used an explicit construction of a long stretch of non-representable integers via CRT-style congruence blocking at several primes $\equiv3\bmod4$ simultaneously, not the Dirichlet-series machine). Do not cite this theorem as settling anything about *gaps*, *runs*, or *pointwise* structure of $S$ — only about the *counting function* $S(x)$ itself and quantities (like the distinct-distances bound in Erdős #89 — distinct distances in the plane) that reduce cleanly to it. 6. Alternative, elementary-flavored proof routes (useful when the full complex-analytic/Selberg–Delange machinery is overkill or when a more robust/sieve-friendly argument is wanted): Iwaniec's 1974 sieve-theoretic proof (upper- and lower-bound sieve estimates, no contour integration) and Selberg's short proof for the squarefree-sum-of-two-squares sub-case — both give the same $x/\sqrt{\log x}$ order by fundamentally combinatorial rather than analytic means (leads only, not independently verified here — see provenance).

Related

- Erdős #89 — distinct distances in the plane — Erdős distinct distances problem: this theorem is the exact mechanism explaining why the integer-lattice construction achieves (and cannot beat) $\Theta(n/\sqrt{\log n})$ distinct distances, pinning the $\sqrt{\log n}$ exponent in the still-open conjecture. - erdos/773 — Sidon subset of $\{1,4,9,\ldots,N^2\}$: this theorem (applied at scale $x=N^2$) is the direct source of the current-best upper bound $|A|\ll N/(\log N)^{1/4}$ via Alon–Erdős (1985); the lower bound side is unrelated (random/explicit Sidon constructions). - erdos/222 — gaps between consecutive sums of two squares: the still-open *worst-case* companion question to this theorem's *average-case* asymptotic; illustrates the sharp technique boundary (Technique item 5) between what the Dirichlet-series/counting-function method proves and what it says nothing about. - Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve — Iwaniec's alternative 1974 proof route for this theorem is a sieve-theoretic argument; general sieve machinery is the natural alternative toolkit whenever the Selberg–Delange/Perron-contour approach is unavailable or too heavy. - Erdős–Fuchs theorem: average representation count can't be too close to linear — a structurally adjacent "additive representation function" impossibility theorem proved by a related but distinct generating-function + Parseval/contour technique; both this theorem and Erdős–Fuchs sit in the broader family of results extracting asymptotic counting information from the analytic behavior of a representation-counting Dirichlet/power series near its dominant singularity. - Additive representation function $r_{B,h}(n)$ — the parent family of results about $r_2(n)$ and related representation-counting functions; this theorem is the "how many $n\le x$ have $r_2(n)\ge1$" (existence/density) member of that family, as opposed to $r_2(n)$'s own pointwise or average-order behavior. - E. Landau, "Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate," *Archiv der Mathematik und Physik* 13 (1908) — the original proof (not independently read here; German, on archive.org per secondary-source references). - S. Ramanujan, first letter to G. H. Hardy, 16 January 1913 — independent rediscovery, integral form $S(x)\sim K\int_2^x dt/\sqrt{\log t}$.