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}$.
160 questions
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 ...
- 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 ...
- 5,460
36
votes
2
answers
7k
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 ...
- 5,460
32
votes
3
answers
8k
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) \...
- 587
30
votes
3
answers
4k
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 ...
- 29k
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$. ...
- 13.9k
21
votes
4
answers
4k
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) = ...
- 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 ...
- 1,533
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 ...
- 3,871
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 ...
- 2,912
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 ...
- 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$ ...
- 3,463
15
votes
3
answers
2k
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 ...
- 6,214
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 ...
- 165
13
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 ...
- 21.1k
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 \...
- 5,460
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 ...
- 1,019
12
votes
1
answer
894
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,...
- 411
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^{\...
user94040
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 -...
11
votes
1
answer
700
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 ...
- 123
11
votes
3
answers
1k
views
What is the intuition behind applying the Mellin Transform to prime distribution?
I am an undergraduate student writing an expository thesis on the complex-analytic proof of the Prime Number Theorem.
I understand that applying the Mellin Transform to the partial sum of the van ...
- 113
11
votes
4
answers
707
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 ...
- 20.2k
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 ...
- 1,687
10
votes
1
answer
808
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$ ...
- 13.8k
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 ...
- 13.8k
10
votes
1
answer
398
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 ...
- 211
10
votes
0
answers
416
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 $\...
10
votes
0
answers
739
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&...
- 2,106
10
votes
0
answers
512
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 ...
- 26k
9
votes
1
answer
699
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 ...
- 41.8k
8
votes
2
answers
3k
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} \ \ ?$$
- 11.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 ...
- 1,329
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, ...
- 93
8
votes
1
answer
834
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 ...
- 5,460
8
votes
1
answer
243
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. ...
- 83
8
votes
1
answer
436
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 ...
8
votes
1
answer
329
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 ...
- 13.3k
8
votes
1
answer
245
views
Asymptotic density of sums of consecutive primes
Call a positive integer respectable if it is a sum of consecutive prime numbers. For example, every prime numbers is respectable. So are $3+5=8$, $2+3+5=10$, $5+7=12$, $3+5+7=15$, $2+3+5+7=17$, $7+11=...
- 15.4k
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 ...
- 3,866
7
votes
3
answers
607
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 ...
- 533
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\...
user6671
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 ...
- 1,533
7
votes
2
answers
2k
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(...
- 595
7
votes
2
answers
475
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) < ...
- 6,969
7
votes
2
answers
636
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 ...
- 129
7
votes
2
answers
426
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^...
- 3,062
7
votes
0
answers
461
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 ...
user145059
7
votes
0
answers
399
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 ...
- 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 ...
- 5,460