Questions tagged [prime-number-theorem]

The Prime Number Theorem is a theorem that describes the distribution of the primes. It says that the number of primes less than or equal to a real number $x$ is asymptotic to $\frac{x}{\ln x}$.

Filter by
Sorted by
Tagged with
50 votes
5 answers
3k views

Motivated account of the prime number theorem and related topics

Though my own research interests (described below) are pretty far from analytic number theory, I have always wanted to understand the prime number theorem and related topics. In particular, I often ...
Sarah's user avatar
  • 482
46 votes
4 answers
8k views

Why could Mertens not prove the prime number theorem?

We know that $$ \sum_{n \le x}\frac{1}{n\ln n} = \ln\ln x + c_1 + O(1/x) $$ where $c_1$ is a constant. Again Mertens' theorem says that the primes $p$ satisfy $$ \sum_{p \le x}\frac{1}{p} = \ln\ln ...
Nilotpal Kanti Sinha's user avatar
36 votes
2 answers
6k views

Why do primes dislike dividing the sum of all the preceding primes?

I was investigating primes with the property that the sum of the first $n$ primes is divisible by $p_n$. It turns out that these primes are extremely extremely rare. For primes less than $10^9$, I ...
Nilotpal Kanti Sinha's user avatar
31 votes
3 answers
7k views

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

I'm reading the elementary proof of prime number theorem (Selberg / Erdős, around 1949). One key step is to prove that, with $\vartheta(x) = \sum_{p\leq x} \log p$, $$(1) \qquad\qquad \vartheta(x) \...
Basj's user avatar
  • 577
30 votes
3 answers
3k views

Heuristic argument for the prime number theorem?

Here is a bad heuristic argument for the prime number theorem. Let $n$ be a positive integer and assume that PNT holds up to $n$. Then $n$ itself is prime if and only if for each prime $p<n$ the ...
gowers's user avatar
  • 28.7k
29 votes
2 answers
3k views

Is there a Kolmogorov complexity proof of the prime number theorem?

Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. ...
Turbo's user avatar
  • 13.7k
21 votes
4 answers
3k views

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

There is an easy proof of the PNT, just in a few lines, in the book by Julian Havil, "Gamma", pages 201-202. Specifically, Von Mangoldt's formula, which is very easy to derive: $$ \psi(x) = ...
Peter S.'s user avatar
  • 221
21 votes
3 answers
6k views

Why is the Chebyshev function relevant to the Prime Number Theorem

Why is the Chebyshev function $\theta(x) = \sum_{p\le x}\log p$ useful in the proof of the prime number theorem. Does anyone have a conceptual argument to motivate why looking at $\sum_{p\le x} \log ...
user16557's user avatar
  • 1,513
20 votes
2 answers
4k views

information-theoretic derivation of the prime number theorem

Motivation: While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number ...
Aidan Rocke's user avatar
  • 3,827
20 votes
4 answers
2k views

Can anything deep be said uniformly about conjectures like Goldbach's?

This is a soft question sparked by my curiosity about the intrinsic depth of Goldbach-like conjectures as perceived by current experts in number theory. The incompleteness theorem implies that, if our ...
user21820's user avatar
  • 2,734
17 votes
5 answers
3k views

Teaching prime number theorem in a complex analysis class for physicists

This is a question about pedagogy. I want to sketch the proof of the prime number theorem or any other application of complex analysis to number theory in a single lecture, in a complex analysis ...
guest17's user avatar
  • 253
15 votes
5 answers
9k views

Upper bounds for the sum of primes up to $n$

Let $s(n)$ denote the sum of primes less than or equal to n. Clearly, $s(n)$ is bounded from above by the sum of the first $n/2$ odd integers $+1$. $s(n)$ is also bounded by the sum of the first $n$ ...
Jernej's user avatar
  • 3,433
15 votes
3 answers
1k views

Elementary lower bounds for the number of primes in arithmetic progressions

Some version of the Prime Number Theorem provides the asymptotic behavior of the number of primes in arithmetic progression $qn+a$ with $(q,a)=1$, $n \ge 1$. I was wondering there are Chebyshev-type ...
Keivan Karai's user avatar
  • 6,064
14 votes
1 answer
1k views

A naive question about the prime number theorem

Let $\psi(x)=\sum_{n\leq x} \Lambda(n)$, where $\Lambda(n)$ is the von Mangoldt function. Then as Chebyshev showed, the following equality holds $$\sum_{n\leq x} \psi(x/n)=x\log(x)-x+O(\log(x)).$$ My ...
Zamanyan's user avatar
  • 165
13 votes
2 answers
2k views

Asymptotics of the n-th prime using the gamma function

In the paper http://rgmia.org/papers/v8n2/eepnt.pdf, the author proves that proves an explicit inequality on prime numbers using the gamma function and as a corollary, he showed that. $$ p_n = n \...
Nilotpal Kanti Sinha's user avatar
13 votes
1 answer
2k views

Why shouldn't this prove the Prime Number Theorem?

Denote by $\mu$ the Mobius function. It is known that for every integer $k>1$, the number $\sum_{n=1}^{\infty} \frac{\mu(n)}{n^k}$ can be interpreted as the probability that a randomly chosen ...
Q_p's user avatar
  • 824
12 votes
4 answers
2k views

Proving Mertens' theorem using the prime number theorem

Mertens' Theorem states that $$\sum_{p \leq x}\frac{1}{p} = \log \log x + M + O(1/\log x).$$ This is weaker than the prime number theorem; in fact according to the Wikipedia page, the prime number ...
Daniel Loughran's user avatar
12 votes
1 answer
836 views

Newman's proof of the prime number theorem

I am teaching a graduate course in Complex Analysis and I am covering Newman's proof of the prime number theorem. I have been using the simplified version in the papers of Zagier and Korevaar. However,...
Gio67's user avatar
  • 401
11 votes
2 answers
1k views

Does the Prime Number Theorem have anything to do with Erdos-Kac law or vice versa?

The prime number theorem says on average we can find $\frac n{\log n}$ primes of magnitude $n$. Erdos-Kac law state a typical number of magnitude $n$ has $\log\log n$ primes. Somehow the fact $e^{\...
user avatar
11 votes
2 answers
1k views

Mertens-like theorem

Mertens' first theorem states that $$ \sum_{p \leq n} \frac{\log p}{p} = \log n + O(1). $$ I read in this paper that the following variant is "classical": $$ \sum_{p \leq n} \frac{\log p}{p -...
Charles Bouillaguet's user avatar
11 votes
1 answer
685 views

Squarefree numbers $n$ such that $432n+1$ is also squarefree

This is a second attempt (see Primes $p$ such that $432 p +1$ is prime) Is the set of squarefree numbers $n$ such that $n(432 n+1)$ is also squarefree known to be infinite? Fact: the number of such ...
user21's user avatar
  • 123
10 votes
3 answers
1k views

Quantitative and elementary proofs of the Prime Number Theorem

I would like to know two things: one, whether the best quantative bounds in the Prime Number Theorem are still basically those given by the Vinogradov-Korobov zero-free region? and two, whether there ...
user36212's user avatar
  • 1,687
10 votes
1 answer
800 views

An extremal problem related either to an uncertainty principle on the circle, or else to the prime number theorem

Consider for $X = 1,2, \ldots$ the set $\mathcal{S}_X$ of trigonometric polynomials $f(t) := \sum_{|k| \leq X} c_k e^{2\pi i kt}$ on the circle $\mathbb{T} := \mathbb{R}/\mathbb{Z}$ of degree $\leq X$ ...
Vesselin Dimitrov's user avatar
10 votes
1 answer
1k views

The supremum value of $\int f(t) \log{\frac{1}{|t|}} \, dt$ for normalized Fourier pairs non-negative outside of $[-1,1]$

Observe that for any Schwartz function $f \in \mathcal{S}(\mathbb{R})$ having $$ f(0) = \widehat{f}(0) = 1 $$ and $$ f, \widehat{f} \geq 0 \quad \textrm{outside of} \quad [-1,1], $$ the following ...
Vesselin Dimitrov's user avatar
10 votes
1 answer
325 views

Vinogradov-Korobov prime number theorem for number fields

Without assuming the Riemann hypothesis, the traditional error bound of the prime-counting function $\pi(x)$ is $O(x\exp(-c(\log(x))^{1/2}))$. As shown by the Wikipedia page for the Landau prime ...
George Bentley's user avatar
10 votes
0 answers
409 views

Are prime numbers among sums of prime numbers distributed as $\frac n{2\ln(n)}$?

Let $(s_n)_{n\in\mathbb N}$ be defined as follows: For $n\in\mathbb N$, $s_n:=2+3+5+\cdots+p_n$ is the sum of the first $n$ prime numbers (e.g.: $s_1=2$, $s_2=5$, $s_3=10$, $s_4=17$, $\ldots$). Let $\...
Tobias Schnieders's user avatar
10 votes
0 answers
730 views

Implications of divergence of $1/\zeta(s) $ at 1/2

$1/\zeta(s)=\sum_{n>0}\frac{\mu(n)}{n^s}$ where $\mu$ is the Moebius function. This series is known to converge for $s\ge 1$ and diverge for $s\le 1/2$. Its convergence is unknown if $1/2< s&...
Koushik's user avatar
  • 2,076
10 votes
0 answers
505 views

Montgomery's conjecture and lower bound on certain Fourier transform.

Recently I have come across the following question, while meditating about Matt Young's answer to this question of mine, explaining the heuristic (or at least, one possible heuristic) behind ...
Joël's user avatar
  • 25.7k
9 votes
3 answers
569 views

Deriving an asymptotic for $\pi(x)$ directly from $\log \zeta(s)$?

Denote by $\pi(x)$ the number of primes $p\leq x$. We generally give approximations for $\pi(x)$ by first approximating $\psi(x) = \sum_{n\leq x} \Lambda(n)$. Part of the reason is presumably that, if ...
H A Helfgott's user avatar
  • 19.3k
8 votes
4 answers
2k views

Asymptotic bounds on $\pi^{-1}(x)$ (inverse prime counting function)

What are the current best asymptotic bounds on $\pi^{-1}(x)$, where $\pi(x)$ denotes the prime counting function (number of primes at most $x$)? In other words, I am curious about the state of the ...
pre-kidney's user avatar
  • 1,289
8 votes
3 answers
1k views

Asymptotics for primality of sum of three consecutive primes

We consider the sequence $R_n=p_n+p_{n+1}+p_{n+2}$, where $\{p_i\}$ is the prime number sequence, with $p_0=2$, $p_1=3$, $p_2=5$, etc.. The first few values of $R_n$ are: 10, 15, 23, 31, 41, 49, 59, ...
Raj 's user avatar
  • 93
8 votes
1 answer
642 views

Strange and non-strange prime numbers, are there infinitely many of them?

Definition. A prime number $p$ is called strange if there exists $k>1$ such that each prime divisior of $p^k-1$ divides $p-1$. Example 3. The prime number $p=3$ is strange as $3^2-1=8$ has the same ...
Taras Banakh's user avatar
  • 40.8k
8 votes
1 answer
805 views

Are there highly composite prime gaps?

Definition: Highly composite prime gap The three composite numbers between the consecutive primes $643$ and $647$ each have at least three distinct prime factors. This is the first occurrence of prime ...
Nilotpal Kanti Sinha's user avatar
8 votes
1 answer
235 views

Main term in the number of sign changes of $\psi(x) - x$

Define $N_\Delta(T)$ to be the number of sign changes of $\psi(x) - x$ in the interval $[1, T]$. Landau's Theorem says $N_\Delta(T)$ is $\Omega(\log T)$ [1]. But perhaps that estimate is too crude. ...
ZapMathigan's user avatar
8 votes
1 answer
419 views

Primes in arithmetic progression with a moduli equal to a power of 2

I am currently looking for a result stronger than Siegel-Walfisz theorem, which gives an upper bound on the error term $|\pi(x,a,b)-\frac{\pi(x)}{\phi(a)}|$ for particular $a$. The Siegel Walfisz is ...
Serge Boissot's user avatar
8 votes
1 answer
325 views

Lexicographic distribution of irreducible polynomials

Let $A = {\mathbb F}_2[X]$, though the following can be adapted to $p \neq 2$ too. Order the elements of $A$ lexicographically. Equivalently, take a polynomial such as $P = X^4 + X + 1$, write its ...
Marty's user avatar
  • 13.1k
7 votes
3 answers
1k views

a question for the prime counting function

A famous inequality that has been proved by J.B. Rosser and L. Schoenfeld says that $\frac{n}{\ln n-1/2}$ < $\pi(n)$<$\frac{n}{\ln n-3/2} , n\ge 67$. Using this inequality we can prove ...
Konstantinos Gaitanas's user avatar
7 votes
3 answers
584 views

How many primes have the form $(2^p+1)/3$?

Assuming that $p$ is an odd prime. How many primes have the form $(2^p+1)/3$? Is the number finite? Mathematica calculation shows that there are 23 such primes when $p$ ranges over the first 500 ...
Huangjun Zhu's user avatar
7 votes
1 answer
1k views

A curious prime counting approximation or just data overfitting?

I am not sure, if this is a research problem. If not I will move this question to ME: Let $\Omega(n) = \sum_{p|n} v_p(n)$, which we might view as a random variable. Let $E_n = \frac{1}{n} \sum_{k=1}^n\...
user avatar
7 votes
2 answers
2k views

Asymptotics of the least common multiple of the first natural numbers

What is $$ \limsup_{n \to \infty} \frac{\log(\mathrm{lcm}(1,2, \dots, n))}{n} \ \ ?$$
Pablo's user avatar
  • 11.2k
7 votes
1 answer
3k views

Error term of the Prime Number Theorem and the Riemann Hypothesis

I have read that the Riemann Hypothesis is equivalent to $\pi(x)=\text{Li}(x)+O(\sqrt{x}\log x)$ Is there an analogous statement saying the Riemann Hypothesis is equivalent to $\pi(x)=\frac{x}{\log ...
user16557's user avatar
  • 1,513
7 votes
2 answers
1k views

Legendre's Constant

In a couple of web pages, I see that Legendre's constant is defined to be $\lim_{n \to \infty} (\pi(n) - (n/\log(n)))$ (for example, here and here). Actually the first uses $\lim_{n \to \infty} (\log(...
user304582's user avatar
7 votes
2 answers
447 views

Asymptotics of $\operatorname{lcm} ((2-1), (3-1), (5-1), (7-1), (11-1), \dotsc, p_n-1 )$

$\DeclareMathOperator\lcm{lcm}$Let $p_k$ be the $k$th prime number. Set $$L(n) = \lcm(p_1-1, p_2-1, \dotsc, p_n-1). $$ What can we say about the growth of $L(n)$? Trivially, one has that $L(n) < ...
JoshuaZ's user avatar
  • 6,090
7 votes
2 answers
608 views

How to use the Prime Number Theorem in order to prove Selberg's Formula?

I`m reading Melvin B. Nathanson's "Elementary Methods in Number Theory" and I can't think of a way of deducing Selberg's formula (9.3) from the prime number theorem. This is one of the tasks ...
Juu's user avatar
  • 129
7 votes
2 answers
418 views

Divisor sums over values of binary forms of primes

Let $\tau$ be the divisor function, that is $$ \tau(n)=\sharp\{d \in \mathbb{N}, d|n\}. $$ I was wondering if anyone has ever proved an asymptotic estimate for the sum $$S(x):=\sum_{p,q\leq x}\tau(p^...
Dr. Pi's user avatar
  • 2,939
7 votes
0 answers
455 views

On a paper of Alain Connes entitled 'Around Wilson's Theorem '

A relatively recent paper Alain Connes - Around Wilson's theorem introduced the function $$ S(n,x ) = \sum_{i=1}^n \sin^2\Bigl(\frac{(i-1)! x}{i}\Bigr). $$ In the same paper, he proved that the ...
user avatar
7 votes
0 answers
375 views

A variant of the equidistribution of primes in an imaginary quadratic number ring

It is known that the arguments of prime elements of $\mathbb{Z}[i]$ are equidistributed in $(0,2π)$ (by Theorem 5.36 of Iwaniec and Kowalski, or one of Kubilius' papers cited below). This theorem ...
BDS's user avatar
  • 123
6 votes
4 answers
2k views

Probability that randomly chosen integers from a restricted set of natural numbers are coprime

We know that the probability $P(k)$ of $k$ randomly chosen integers $(k \ge 2)$ from the set of natural number are coprime is $$ P(k) = \frac{1}{\zeta(k)}. $$ I am looking at a special case of ...
Nilotpal Kanti Sinha's user avatar
6 votes
3 answers
2k views

Logarithmic integral, $π(x)$ and $x/(\ln x)$

The function $\text{Li}$ (logarithmic integral) is defined for $x>0$ by $$ \text{Li}(x)=\int_2^{x}\frac{dt}{\ln t}. $$ The prime number theorem, proven by Hadamard and de la Vallée-Poussin in 1896 ...
Bazin's user avatar
  • 15.1k
6 votes
2 answers
385 views

asymptotic for li(x)-Ri(x)

Is it true that $$\operatorname{li}(x)-\operatorname{Ri}(x) \sim \frac{1}{2}\operatorname{li}(x^{1/2}) \ (x \to \infty),$$ where $$\operatorname{Ri}(x) = \sum_{n = 1}^\infty \frac{\mu(n)}{n} \...
Jesse Elliott's user avatar