56

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:
Theorem Let $1 < n_1 < n_2 < \dots$ be a sequence of natural numbers that are pairwise coprime. Then this sequence has zero (natural) density.
Proof ...

answered Jan 17 '21 at 17:34

Terry Tao

89.2k2424 gold badges344344 silver badges422422 bronze badges

49

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 \frac{\Lambda(n)}{n^s} = -\frac{\zeta'(s)}{\zeta(s)},$$
at least in the region $\mathrm{Re}(s) > 1$. The right-hand side has a pole of residue 1 at the ...

37

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 bivariate generating function is $1/Q := 1 / (1-xy-xy^2-2x^2y)$. The intersection of this in the positive quadrant with $xQ_x = yQ_y$ is a point $(x_0,y_0)$, where $\...

35

$\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$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\...

answered Dec 18 '20 at 20:05

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

33

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 the question is true, I asked a separate question about whether one could efficiently compute $T_n(x)$ modulo $x^r-1,n$. That question got a brilliant answer by ...

answered Nov 21 '17 at 18:47

მამუკა ჯიბლაძე

15.9k33 gold badges6767 silver badges153153 bronze badges

29

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^w
$$
has a bounded number of solutions in $(x,y,z,w)$ and that a bound on these could be computed (and the equation solved in practice). This solves (in ...

27

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)!},$$
that is your sum (denote $n=k+j$). For evaluating the integral, we first integrate by $t$, get $-2\log(1-z)/(2-z)$. Now denote $1-z=x$ and integrate $2\log ...

answered Jun 3 '18 at 17:40

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

27

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 to show that
\begin{align*}
\int_0^1\frac{dx}{1-x+x^2}&=\frac{2\pi}{3\sqrt{3}},\\
\int_0^1\frac{dx}{1+x+x^2}&=\frac{\pi}{3\sqrt{3}},
\end{align*}
so we ...

26

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 latitude moving at a constant speed $c$. At some point this circle/wave will meet the point $q$ (let's say that $q$ lies within the continent of Antarctica, so the ...

26

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
Lemma. For a positive integer $k$, and any positive integer $N$, we have $\pi(N)\leqslant N/H_k+k+\text{lcm}(1,\ldots,k)$.
Proof. Choose the maximal integer $M\...

answered Jan 17 '21 at 19:01

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

24

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^2(\pi k/N)}.$$
Your sum is $S_{10,1}-S_{10,3}$.

22

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_{1\le i<j\le n} x_ix_j$$
so we can find that $V_{n}(P)=(n-1)a^2-2nb$. Similarly we have
$$V_{n-1}(P')=(n-2)\frac{(n-1)^2a^2}{n^2}-2(n-1)\frac{(n-2)b}{n}$$
$$=...

answered Aug 29 '18 at 0:52

Gjergji Zaimi

81.3k44 gold badges212212 silver badges380380 bronze badges

22

$\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]}
\newcommand{\suml}{\sum\limits}
\newcommand{\sumS}{\suml_{S \in P}}
\newcommand{\prodl}{\prod\limits}
\newcommand{\prodS}{\prodl_{S \in P}}
\newcommand{\subs}{\subseteq}...

21

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 hold, then use the well ordering principle to select the smallest number $s$ which can be factored in two distinct ways into products of primes, $s = p_1p_2 \dots ...

19

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. See this.

19

Complementing Terry's nice response, let me try to explain from a more elementary point of view why Selberg's formula (1) is natural, and why it is true.
It is natural to formulate the PNT in terms of the von Mangoldt function $\Lambda(n)$, because it is supported on the prime powers, where it is given by the simple analytic formula $\Lambda(p^r)=\log p$. ...

19

Ancients did not know line integrals, but they understood that the length of the curve
is the limit of the lengths of inscribed broken lines. To prove the inequality for broken lines (piecewise-great-circles), it is enough to prove that a side of a small
spherical triangle is less than the sum of two other sides. This can be done using spherical trigonometry,...

answered Jan 14 '19 at 13:50

Alexandre Eremenko

74.3k88 gold badges211211 silver badges354354 bronze badges

19

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 by Erdős (1938), see Theorem 19 and its proof in Hardy-Wright: An introduction to the theory of numbers.

19

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}^{+\infty}\frac{\mathrm{sgn}_2(n)}{n}=\prod_p\left(1-\frac{\mathrm{sgn}_2(p)}{p}\right)^{-1}=
$$
$$
=\left(1-\frac12\right)^{-1}\left(1-\frac13\right)^{-1}\prod_{...

answered Jun 15 '21 at 7:31

Alexander Kalmynin

4,87911 gold badge1313 silver badges3333 bronze badges

18

I don't know how "classical" you find these values, but here's perhaps something.
Define $E=\sum_{m,n\in\mathbb{Z}}q^{m^2+n^2}$, which is known to be a weight 1 level 4 modular form. In fact $E$ is an eigenform for the Hecke operators, and if we write $E=\sum_{r\geq0}a_rq^r$ then $L(E,s)=\sum_{r\geq1}a_r/r^s$ equals $4\zeta(s)L(\chi,s)$ with $\chi$ the ...

answered Jan 31 '17 at 22:02

Kevin Buzzard

38.6k1313 gold badges150150 silver badges233233 bronze badges

18

\begin{align*}
\sum_{k=1}^{n} \frac{2^k-1}{k}
&=\sum_{k=1}^{n} \frac{1}{k}\left(\sum_{j=1}^{k} \binom{k}{j}\right) \\
&=\sum_{j=1}^{n} \sum_{k=j}^{n} \binom{k}{j}\frac{1}{k} \\
&=\sum_{j=1}^{n} \frac{1}{j}\left(\sum_{k=j}^{n} \binom{k-1}{j-1}\right) \\
&=\sum_{j=1}^{n} \frac{1}{j} \binom{n}{j}.
\end{align*}

17

I mention this as an answer since it is too long for comments. I do not know what the adelic proof assumes. Suppose that all but finitely many primes of $K$ split completely in $L$. Suppose $d$ is the degree of $L$ over $K$. Then the zeta function of $L$ is the $d$-th power of the zeta function of $K$, up to finitely many factors. But the Zeta functions of $...

17

$$\sum_{k=1}^n\binom nk\frac1k=\sum_{k=1}^n\binom nk\int_0^1 dt\,t^{k-1}=
\int_0^1 dt\,\sum_{k=1}^n\binom nk t^{k-1}=\int_0^1 dt\,\frac{(1+t)^n-1}t.$$
$$\sum_{k=1}^n\frac{2^k-1}k=\sum_{k=1}^n\int_0^1 dt\,(1+t)^{k-1}=
\int_0^1 dt\,\sum_{k=1}^n (1+t)^{k-1}=\int_0^1 dt\,\frac{(1+t)^n-1}t.$$

answered Dec 18 '20 at 16:54

Iosif Pinelis

69.4k66 gold badges6666 silver badges125125 bronze badges

17

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)$ directly. Expanding its inverse as a geometric series gives
$$\prod_{ p \; {\rm prime}} (1-1/p)^{-1}=\prod_{ p \; {\rm prime}}(1+1/p+1/p^2 + \ldots)=\sum_{n \...

16

From your post it seems you are permitted to use the following:
$a\in\mathbb{R}$ is a root of $p(x)$ (i.e. $p(a) = 0$) iff $p(x) = (x-a)q(x)$ for some polynomial $q(x)$.
$a\in\mathbb{R}$ is a local extremum of $p(x)$ iff (thanks to Ilya Bogdanov; consider e.g. $p(x) = x^3$) only if $p(x)-p(a) = (x-a)^2q(x)$ for some polynomial $q(x)$.
A proof using these ...

16

It's clearest to write the identities in terms of Bernoulli numbers $B_n$ using
\begin{equation}
\zeta (2 n) = \frac{(-1)^{n - 1} (2 \pi)^{2 n}}{2 (2 n)!} B_{2 n} .
\end{equation}
Remembering that $B_1 = \frac{1}{6}$ and that $B_n$ vanishes for all other odd $n$, the desired identity is
\begin{equation}
\sum_{k = 0}^{2 n} \binom{2 n}{k} 2^k (2^k - 1) B_k = 0 ...

16

This is just the following identity:
$$a^3+b^3+c^3-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ca).$$ Since $$F_n+(-F_{n-1})+(-F_{n-2})=0,$$ your formula follows.

16

Such things are quick in complex numbers. Let $O=0$ be the origin, $ABC$ be the unit circle. The centroid of $ABC$ is $G=(A+B+C)/3$, the Euler circle is the image of the circle $ABC$ under homothety $f\colon X\to (3G-X)/2$ centered in $G$ with coefficient $-1/2$, thus $N=f(O)=(A+B+C)/2$. Next, $A'=2N-A=B+C$. The circle through $O,A,B+C$ has equation $g_A(z):=...

answered Apr 24 '21 at 6:03

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

16

Denoting $H_0=0$, we have $$\sum_{n=1}^\infty \frac{H_n}{n(n+1)2^n}=\sum_{n=1}^\infty \left(\frac1n-\frac1{n+1}\right)\frac{H_n}{2^n}=\sum_{n=1}^\infty \frac{1}n\left(\frac{H_n}{2^n}-\frac{H_{n-1}}{2^{n-1}}\right)\\=\sum_{n=1}^\infty\frac1{n^22^n}-\sum_{n=1}^\infty\frac{H_n}{(n+1)2^{n+1}}.$$
It is well known that $\sum_{n=1}^\infty\frac1{n^22^n}=\frac{\pi^2}{...

answered Aug 24 '21 at 6:16

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

15

Darij already gave a great elementary detailed exposition. I wanted to remark that all such kinds of results (including the postscript) are special cases of a classical result that (at least in the generality of semilattices) goes back to Lindström in Determinants on semilattices. For this question we are in the special case of the Boolean lattice.

answered Dec 7 '18 at 11:03

Gjergji Zaimi

81.3k44 gold badges212212 silver badges380380 bronze badges

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

#### Related Tags

elementary-proofs × 183nt.number-theory × 81

prime-numbers × 36

mg.metric-geometry × 28

euclidean-geometry × 25

co.combinatorics × 23

reference-request × 18

sequences-and-series × 17

real-analysis × 16

analytic-number-theory × 16

plane-geometry × 15

triangles × 13

counterexamples × 12

diophantine-equations × 11

polygons × 10

ca.classical-analysis-and-odes × 9

inequalities × 8

polynomials × 7

soft-question × 7

cv.complex-variables × 5

combinatorial-identities × 5

pr.probability × 4

linear-algebra × 4

ho.history-overview × 4

ag.algebraic-geometry × 3