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


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=\...


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


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


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\...


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}$$ $$=...


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,...


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_{...


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


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.$$


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):=...


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}{...


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.


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