Tag Info

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


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 $$\zeta (2 n) = \frac{(-1)^{n - 1} (2 \pi)^{2 n}}{2 (2 n)!} B_{2 n} .$$ Remembering that B_1 = \frac{1}{6} and that B_n vanishes for all other odd n, the desired identity is \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