66 votes
Accepted

What is the simplest proof that the density of primes goes to zero?

I'm summarising the discussion in GH from MO's answer as a separate answer for clarity. The fact that the primes have (natural) density zero can be deduced from a (seemingly) more general statement: ...
Terry Tao's user avatar
  • 108k
52 votes
Accepted

Ideas in the elementary proof of the prime number theorem (Selberg / Erdős)

The complex-analytic proof of the prime number theorem can help inform the elementary one. The von Mangoldt function $\Lambda$ is related to the Riemann zeta function $\zeta$ by the formula $$ \sum_n ...
Terry Tao's user avatar
  • 108k
46 votes

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

The PNT is indeed equivalent to $\lim_{x\to\infty} \frac{\psi(x) -x}{x}=0$ which Von Mangoldt's formula and some trivial estimates reduce to proving $$ \lim_{x\to\infty} \sum_{ \zeta(\rho)=0} \frac{x^{...
Will Sawin's user avatar
  • 135k
44 votes
Accepted

What is the simplest proof that the density of coprime pairs does not go to zero?

I would say that the standard proof is elementary enough, but here is an argument that avoids the Möbius function and the Riemann zeta function. Let $A_d$ be the set of pairs $(a,b)$ where $a,b\le x$ ...
Ofir Gorodetsky's user avatar
37 votes

What is the limit of $a (n + 1) / a (n)$?

The value is close to $e$ but not. It's actually the positive real root of $p(t) := t^3 - 2t^2 + t - 8$. This is solvable via ACSV (see book by Pemantle and Wilson 2013). To summarize, the ...
robin pemantle's user avatar
36 votes

Alternative proofs sought after for a certain identity

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ ...
Fedor Petrov's user avatar
34 votes

Which theorems have Pythagoras' Theorem as a special case?

The Law of cosines is the first that comes to my mind: $$c^{2}=a^{2}+b^{2}-2ab\cos \gamma$$ (source: Wikipedia) If $\gamma$ is a right angle, its cosine is 0 and all that remains is Pythagoras' ...
33 votes

Chebyshev polynomials of the first kind and primality testing

Wow. This deserves a separate answer. As I mentioned in a comment, motivated by the question, in a previous comment, by Igor Rivin whether an efficient primality test can be made if the statement in ...
მამუკა ჯიბლაძე's user avatar
32 votes
Accepted

Unrigorous British mathematics prior to G.H. Hardy

Rigor and Clarity: Foundations of Mathematics in France and England, 1800-1840 explains in some detail how British mathematicians in the early 19th century viewed the role of rigor in the formulation ...
Carlo Beenakker's user avatar
30 votes

What is the simplest proof that the density of primes goes to zero?

Here is a very much self-contained version of the argument discussed in the posts by GH from MO and Terry Tao. The claim immediately follows from $H_k:=1+1/2+\ldots+1/k\to \infty$ and the following ...
Fedor Petrov's user avatar
29 votes
Accepted

Diophantine equation $3^a+1=3^b+5^c$

I can't resist this: The young Chris Skinner showed that if $a$, $b$, $c$, $d$ are fixed positive integers, and $p$ and $q$ are positive coprime integers then the equation $$ ap^x + bq^y = c+ dp^z q^...
Lucia's user avatar
  • 43.3k
29 votes

Which theorems have Pythagoras' Theorem as a special case?

Parseval identities in the theory of Fourier series and integrals.
29 votes
Accepted

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

To complement Will Sawin's answer, in the specific context of the prime number theorem, there are historically well-established notions of "elementary" and "non-elementary" proofs, ...
Kostya_I's user avatar
  • 8,642
28 votes
Accepted

What is the value of this double sum in closed form?

Consider the integral $$I=\int_0^1\int_0^1\frac{zdzdt}{(1-zt)(1-z(1-t))}=\sum_{k,j\geqslant 0} \int_0^1\int_0^1 z^{k+j+1}t^k(1-t)^jdzdt=\\ \sum_{k,j\geqslant 0} \frac1{k+j+2}\cdot \frac{k!j!}{(k+j+1)!}...
Fedor Petrov's user avatar
28 votes
Accepted

A Putnam problem with a twist

$\newcommand{\QQ}{\mathbb{Q}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]} \...
darij grinberg's user avatar
27 votes
Accepted

An infinite series that converges to $\frac{\sqrt{3}\pi}{24}$

Here is an elementary proof. We rewrite the series as $$\frac{1}{4}\int_0^1\frac{1-x^4}{1-x^6}\,dx=\frac{1}{8}\int_0^1\frac{dx}{1-x+x^2}+\frac{1}{8}\int_0^1\frac{dx}{1+x+x^2}.$$ It is straightforward ...
GH from MO's user avatar
  • 98.2k
27 votes

Unrigorous British mathematics prior to G.H. Hardy

The excellent answers by Carlo Beenakker and Padraig Ó Catháin have inspired me to do some reading, and I have come to the understanding that the contrast between English and Continental mathematics ...
Timothy Chow's user avatar
  • 78.1k
26 votes

Geodesics on the sphere

Imagine that the sphere is the surface of the earth, and that an earthquake happens at the south pole, point $p$. A seismic wave goes out from the point $p$, so that the wave front is a circle of ...
Ian Agol's user avatar
  • 66.8k
26 votes

Unrigorous British mathematics prior to G.H. Hardy

These examples relate to algebra rather than analysis, but might in any case be useful. The papers of JJ Sylvester are full of deep insight and entertaining prose, but are also full of unsupported ...
Padraig Ó Catháin's user avatar
24 votes
Accepted

A conjectural infinite series for $\frac{\pi^2}{5\sqrt{5}}$

More generally, if $1\le k\le N-1$ is an integer, where $N$ is a positive interger, $$S_{N,k} := \sum_{n=0}^\infty\biggl( \frac{1}{(N n+N-k)^2} + \frac{1}{(N n+k)^2} \biggr) = \frac{\pi^2}{N^2\sin^...
Brendan McKay's user avatar
22 votes
Accepted

Roots and relation between polynomials and their derivatives

Suppose that we have $$P(x)=x^n-ax^{n-1}+bx^{n-2}+\cdots$$ where we can take $P$ to be monic since it doesn't affect $V_n(P)$. From Vieta's formula we have $$a=\sum_{i=1}^n x_i \quad , \quad b=\sum_{...
Gjergji Zaimi's user avatar
22 votes
Accepted

The constant $e$ represented by an infinite series

Your sum actually equals $\frac{\pi\sqrt{3}}{2}$, so it's more like $\pi$ all over again, not $e$. To see this, note first that by definition $\mathrm{sgn}_2$ is multiplicative, hence $$ A=\sum_{n=1}^{...
Alexander Kalmynin's user avatar
22 votes

Which theorems have Pythagoras' Theorem as a special case?

The parallelogram law says that if $\mathcal{V}$ is an inner product space and $\mathbf{v},\mathbf{w} \in \mathcal{V}$, then $$ 2\|\mathbf{v}\|^2 + 2\|\mathbf{w}\|^2 = \|\mathbf{v} + \mathbf{w}\|^2 + \...
21 votes
Accepted

Nonstandard proofs of the fundamental theorem of arithmetic

To summarize the comments, this is also known as Zermelo's proof. A version can be found on wikipedia. I will give the proof here to avoid link rot. The proof is by contradiction. If FTA did not ...
21 votes

Which theorems have Pythagoras' Theorem as a special case?

The Pythagorean theorem is a limit of the general formula for spherical or hyperbolic space: $\cos(a\sqrt{\kappa})\cos(b\sqrt{\kappa})=\cos(c\sqrt{\kappa})$, where $\kappa$ is the curvature.
21 votes

Simpler proofs using the axiom of choice

In Division by Three, Peter G. Doyle and John Horton Conway show, without invoking the Axiom of Choice, that for any sets $A$ and $B$, if there is a bijection between $3 \times A$ and $3 \times B$, ...
20 votes

What is the simplest proof that the density of primes goes to zero?

Using the Chinese Remainder Theorem, one can reduce the statement to $\prod_p(1-1/p)=0$, which in turn is equivalent to $\sum_p 1/p=\infty$. For the last statement a short (but clever) proof was given ...
GH from MO's user avatar
  • 98.2k
20 votes

What is the simplest proof that the density of primes goes to zero?

The proof by GH from MO is, of course, correct. As noted in the comment of Fedor Petrov, there is no need to pass to the series $\sum_p 1/p$ and it is easier to analyze the product $\prod_p (1-1/p)$ ...
Yuval Peres's user avatar
20 votes

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

The fundamental problem with using formulas of the kind you described for $\psi(x)$ is that the series $\sum_\rho x^\rho/\rho$ is hard to estimate on its own. The crux of the problem here is that ...
KConrad's user avatar
  • 49.6k
19 votes
Accepted

roots of higher derivatives of exponential

The (physicists') Hermite polynomials are $$ H_n(x) = (-1)^n e^{x^2} D^n e^{-x^2}$$ And their roots are real. For that you don't need to know they are Hermite polynomials: just Rolle's theorem. ...
Robert Israel's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible