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
4
votes
1
answer
1k
views
Difficulty with "A new elementary proof of the Prime Number Theorem" by Richter
I'm studying Richter's "A new elementary proof of the Prime Number Theorem" paper, and I'm finding some problems understanding some parts of it. For example, I don't see how to get, in Lemma ...
CommunityBot
- 1
4
votes
1
answer
255
views
First occurrence of formula for $\sum_{n\leq x} \mu(n) \log n$ in terms of $\psi(y)-\lfloor y\rfloor$?
The identity contained in the last two displayed equations in the following passage (from page 110 in Ayoub's An Introduction to the Analytic Theory of Numbers, 1963) gives us right away a simple ...
- 63.9k
4
votes
0
answers
150
views
Identities to go from $\sum_{n\leq x} \mu(n) \log \frac{x}{n}$ to $M(x) = \sum_{n\leq x} \mu(n)$?
Let $\mu$ be the Möbius function. Say we have a bound on $\check{M}(x) = \sum_{n\leq x} \mu(n) \log \frac{x}{n}$ of the form $|\check{M}(x)|\leq \epsilon x$ for all $x\geq x_0$.
It is then easy to ...
- 63.9k
3
votes
0
answers
191
views
What smoothing to use for PNT-like results?
Consider a Dirichlet series $\sum_n a_n n^{-s}$ with desirable analytic properties (e.g., analytic extension to $\Re s>0$); one example would be $a_n=\mu(n)$. Say we want to estimate $\sum_{n\leq x}...
- 20.2k
-3
votes
1
answer
201
views
Formula for gaps between primes [closed]
The twin prime conjecture refers to:
$$
\liminf_{n\to \infty}\; p_{n+1} - p_{n} = 2.
$$
By reasoning I arrive at the following simple formula for gaps between primes:
\begin{align}
p_{...
- 26.9k
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 ...
- 14.6k
1
vote
0
answers
156
views
Nontrivial nonrandom properties of prime numbers
What are some nontrivial nonrandom properties of prime numbers. Consider the simple model where each number is prime with probability 1/log(n) by Montgomery and extensions of it. Once you add some ...
- 356
0
votes
0
answers
122
views
Explicit upper bounds on the number of primes up to the square of the $n^\text{th}$ prime number $p_n$
I'm looking for explicit upper bounds on the number of primes up to the square $m=p_n^2$ of the $n^\text{th}$ prime number.
Such estimates can rely on the knowledge of the exact number of primes up to ...
- 727
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=...
CommunityBot
- 1
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 ...
- 188k
1
vote
0
answers
68
views
Primality testing by reversible computation using the prime number theorem
Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are ...
- 283
0
votes
0
answers
78
views
Using Ehrhart polynomials to count primes?
As indicated below, one could use the Ehrhart polynomials of the simplex in number theory.
Here are the questions without context first:
Questions:
The sum $$\sum_{k=0}^t (-1)^k ( \operatorname{...
- 3,032
5
votes
1
answer
736
views
Smallest prime factor of numbers
The literature refers to smooth integers as \begin{equation}\Psi(x,y):=\#\{n\le x:P_1(n)\le y\},\end{equation} where $P_1(n)$ is the largest prime factor of $n$. There are lots of results studying $\...
- 105k
0
votes
0
answers
90
views
Generalizations for the PNT to a subset of Dedekind domains?
The classical prime number theorem states that the prime counting function
$$\pi(X) := \# \{ p \leq X \ | \ \text{$p$ prime} \}$$
is asymptotically equal to $X/\log(X)$.
It is also known (and much ...
- 131
2
votes
2
answers
424
views
"Squeezing" the primes?
The logical idea here is to map a curve that encodes the primes into the region $(0,1)^2$ and analyze the distribution there more easily and achieve tight bounds.
To assess the distribution of primes, ...
- 1,126
3
votes
1
answer
540
views
Prime number theorem via the explicit formula
Can the prime number theorem be obtained from the explicit formula,
$\psi(x)=x-\sum_{\zeta(\rho)=0}\frac{x^\rho}{\rho}+O(1)$?
Here, $\psi(x)=\sum_{k=1}^\infty\sum_{p^k<x}\log p$
- 11.1k
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 ...
- 8,374
2
votes
1
answer
152
views
Estimating the minimum number of distinct least prime factors found in range of $c$ consecutive integers
When I look at the count of distinct least prime factors for a range of consecutive integers, I am seeing the same minimum number appear again and again. I am wondering if this number represents the ...
- 1,049
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) = ...
- 50.6k
2
votes
1
answer
1k
views
Given an even integer N, what is the minimum set of primes such that any even number x <= N can be expressed as the sum of two primes from the set?
Given an even integer N, what is the minimum set of primes such that any even number $x \leq N$ can be expressed as the sum of two primes in the set?
Goldbach's conjecture said Every even integer ...
- 1,944
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 -...
- 14.6k
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) < ...
- 56.9k
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 ...
CommunityBot
- 1
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 ...
- 50.6k
1
vote
1
answer
122
views
Best possible unconditional partial sum estimate of $\sum_{p\leq x}\frac{\ln(p)}{({p})^{n/2}}$:
Consider the following partial sum:
$$S(x,n)=\sum_{p\leq x}\frac{\ln(p)}{({p})^{n/2}}$$
Here p runs through primes and $n$ is constant
What is the best possible unconditional( using best known version ...
- 5,089
4
votes
1
answer
601
views
Reference for a proof of Euclid's Theorem for the infinitude of primes
I would be curious to have a reference for the following proof
of Euclid's Theorem on the infinitude of primes:
Using Legendre's formula (also called de Polignac's formula) for
$p$-adic valuations of ...
- 118k
4
votes
1
answer
251
views
Density of semiprimes in arithmetic progression
Let $n,a,b$ be integers such that $n$ and $a$ are coprime, and $n$ and $b$ are also coprime. According to the Prime number theorem for arithmetic progressions, the primes which are $a\mod n$ have the ...
- 4,713
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 ...
- 4,713
2
votes
1
answer
283
views
Explicit bounds on number of primes of given size
How many prime numbers of $b$ bits are there?
Beyond the prime number theorem, one can give explicit bounds on the number of primes below some integer $n$, or in a given interval. For instance, Rosser ...
- 105k
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 $\...
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 ...
2
votes
0
answers
215
views
An approach to the prime number theorem with Rademacher variables and a recursive formula for the prime pi function?
Consider the bipartite graphs defined here:
Why is this bipartite graph a partial cube, if it is?
We do random walks on them with equal propability and since the graphs are finite and connected the ...
- 3,032
0
votes
0
answers
136
views
Bounded sums involving primes
I'm trying to generalize the Theorem 2.7.1 in [1] where they prove:
$$\sum_{p \leq x} f(p) = \int_{2}^{x} \frac{f(t)}{\log{t}} dt + \epsilon(x)f(x) - \int_{2}^{x} \epsilon(t) f^{'}(t) dt $$
where $\...
- 63.9k
0
votes
2
answers
302
views
How can I convert Meissel's/Lehmer's formula for prime counting to get sum of primes
Legendre's formula can be very easily be generalised as mentioned here (visible after login) which is like this
${\pi}(v,p)={\pi}(v,p-1)-1.[{\pi}(v/p,p-1)-{\pi}(p-1,p-1)]$
${ \big\downarrow}$
$S(v,p)=...
0
votes
0
answers
91
views
How to use prime number theorem In such cases?
Let,
$$A(x)=\sum_{p\leq x}f(p)$$
Where $p$ is a prime number.
Under the Prime Number theorem we have that,
$$\pi(x)=Li(x)+O\left(\frac{x}{e^{a\sqrt{\ln(x)}}}\right) $$
as $x$ approach infinity.
Now,
$$...
- 111
0
votes
1
answer
195
views
Geometric prime distribution
Let integers $\ a>1\ $ and $\ b\in\mathbb Z\ $ be relatively prime (hence $\ b\ne 0).\ $ The Dirichlet's prime distribution theorems apply to the arithmetic sequence
$$ (_aG_b(x) : x\in\mathbb Z) $$...
- 4,776
0
votes
0
answers
144
views
better estimates than the prime number Theorem in Euclidean domains
For a unique factorization domain we know that we have some the analogues of fundamental theorem of arithmetic, and can build elements by using 'building blocks'. For me the easiest examples are ...
- 865
2
votes
1
answer
300
views
Averages of Möbius function in arithmetic progressions
It is mentioned in multiple occasions here that the bound
$$
\mathop{\sum_{n=1}^{N}}_{n\equiv a\mod l} \mu(n) = o(N)
$$
is equivalent to the prime number theorem in arithmetic progressions. But I am ...
- 50.6k
1
vote
1
answer
317
views
An explicit value for a bound proof
I saw a proof that $|p_n - li^{-1}(n)| \leq n e^{-c \sqrt{\ln(n)}} $,
without saying anything about $c$ !
My questions is, what the explicit value of $c$ ??
It just says for some number $c$ without ...
- 105k
2
votes
1
answer
138
views
Is $\lim_{s \rightarrow 1} E(f(X_s)) = \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{k=1}^N f(k)$?
Let $s>1$ be a real number. We look at the zeta probability function / Zipf probability function defined as:
$$P(X = n) = \frac{1}{n^s \zeta(s)}$$
Suppose $f: \mathbb{N} \rightarrow \mathbb{R}$ is ...
- 128k
0
votes
0
answers
97
views
Primes in residue classes [duplicate]
For which sets of residue classes are there easy elementary proofs that there are infinitely many primes in them, which don’t require the machinery of proofs of Dirichlet’s theorem?
Example: it’s ...
- 827
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 ...
- 114k
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 ...
- 3,699
1
vote
1
answer
310
views
Asymptotic lower bound for the number of square free with at least two prime factors
In one of Soundararajan's papers, he claims without proof that it is a standard exercise to show that the number $N(X)$ of positive square-free integers $d \equiv 1 \; \bmod \; 8$ less than $X$, with ...
- 14.6k
3
votes
0
answers
1k
views
On new (purely analytic) perspective towards theory of prime numbers
[I'm going to ask this question very carefully as a question similar to this received a critical response on this platform.
I myself am very skeptical about this but I want to know, from the experts' ...
- 375
3
votes
3
answers
380
views
Oscillations of $\theta(x)-x$, for the Chebyshev $\theta$ function
Is anything known about the relative "periodicity" of the oscillations of $\theta(x)-x$, that is, how frequent, in general terms, are the sign changes? Here, $\theta(x)$ is the Chebyshev $\theta$. ...
- 8,842
2
votes
1
answer
460
views
How essential is the vanishing of the Dirichlet $L$-functions to Dirichlet's theorem on primes in arithmetic progressions?
I seem to recall that the prime number theorem (PNT) is equivalent to the fact that the Riemann zeta function $\zeta(s)$ is non-zero on all of $\text{Re}(s) = 1$ (see https://math.stackexchange.com/...
- 50.6k
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
4
votes
1
answer
246
views
Short proof of the error bound in PNT assuming a zero-free strip?
I am looking for a short proof of the fact that $\zeta(z)\neq 0$ for $\Re z>a$ implies the prime number theorem with an error bound $O(x^{a+\varepsilon})$ for any $\varepsilon>0$, which would be ...
- 5,089
6
votes
2
answers
390
views
A lower-bound for the square-mean of Fourier coefficients of cusp forms at primes argument
There is a basis question which puzzles me for a while. The question is the following:
Let $X\ge 2,$ and $\lambda(n)$ be the $n$-th Fourier coefficient of a $GL(2)$ newform of prime level $N>1$, ...
- 563