Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

4
votes
1answer
167 views

Landau's theorem using nth roots

This question was asked earlier at MSE . Let $\omega$(n) denote the number of distinct primes dividing $n$. The Mobius function is defined as $\mu(n) = (-1)^{\omega(n)}$ if $n$ is squarefree and $\...
5
votes
0answers
189 views

Explicit bounds for the Mertens function

It is a consequence of some forms of the prime number theorem that with $\mu$ the Möbius function, for all $A > 0$, there exists $c_A$ such that for all sufficiently large $x$, $$\frac{1}{x}\sum_{n\...
6
votes
2answers
269 views

A simultaneous generalization of the Grunwald-Wang and Dirichlet Theorems on primes

By Grunwald-Wang Theorem, if for some odd number $n$ the equation $x^n=a$ has no solutions in $\mathbb Z$, then the equation $x^n=a\mod p$ has no solutions for some prime number $p$. I am interested ...
47
votes
5answers
2k 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 ...
6
votes
2answers
284 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} \...
13
votes
3answers
2k 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
votes
0answers
129 views

Cancellation in this exponential sum?

I would like to know whether it is possible to obtain cancellation in the sum $$\sum_{p \leq X} e^{{2\pi iX}/{p}}$$ where $X$ is a real number that goes to $\infty$, and $p$ denotes a prime number.
5
votes
1answer
419 views

What is the natural density of hyper prime numbers?

What do we mean by hyper prime numbers? Well, roughly speaking they are natural numbers which are prime with respect to hyperoperators in arithmetic such as exponentiation, tetration, pentation, et ...
1
vote
2answers
606 views

Prime counting. Meissel, Lehmer: is there a general formula?

I am looking for a general forumla to count prime numbers on which the Meissel and Lehmer formula are based: $$\pi(x)=\phi(x,a)+a-1-\sum\limits_{k=2}^{\lfloor log_{p_{(a+1)}}(x) \rfloor}{P_k(x,a)}$$ ...
3
votes
0answers
643 views

Euclides' sieve

This is probably a well-known problem. Given a set or multiset of natural numbers let us construct its "Euclides" closure: on each step we take all possible products $P_i$ of the elements in the set, ...
8
votes
1answer
671 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$ ...
10
votes
1answer
655 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 ...
1
vote
0answers
141 views

Is it also infinite prime's power in Dirichlet's arithmetic progressions? [closed]

we know if $(a, b)=1$,then in sequence $a,\ a+d,\ a+2d,\ a+3d,\ \dots ,\ $ we can get infinite primes.But i'm wondering if we exchange the prime $p_i$ for $p_i^{k}$, where $k\geq 1$,is it also true? ...
1
vote
2answers
255 views

Estimates for Sum of Prime Factors and Number of Prime Factors

Given a positive integer $n$, I've workout out a formula which involves the expression "sum of distinct primes dividing n" minus "number of distinct prime factors of n." Are there any known ...
7
votes
2answers
833 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(...
2
votes
0answers
93 views

Bombieri-Vinogradov up to smaller moduli?

Bombieri-Vinogradov theorem (taken from Wikipedia) states: Let $x$ and $Q$ be any two positive real numbers with $x^{1/2}\log^{-A}x\leq Q\leq x^{1/2}.$ Then $$\sum_{q\leq Q}\max_{y<x}\max_{1\le a\...
3
votes
1answer
112 views

Double max of a particular sum in Montgomery-Vaughan

In the Montgomery-Vaughan's paper ''The exceptional set in Goldbach's problem'', they estimate the following sum: $$\displaystyle \max_{0<y\leq x}\max_{0<h\leq x} \left(h+\frac{x}{P}\right)^{-1}...
3
votes
1answer
196 views

PNT analog for primes inside a structured set

Let $\Bbb T$ be the set of all square free integers with ordering derived from $\Bbb N$. Essentially $PNT$ says if you pick $\log N$ integers less than $N$ you can expect one of them to be prime. ...
4
votes
0answers
151 views

Does $\pi(x) \geq \mathrm{Li}(x)$ imply that $\vartheta(x) \geq x$

As the question in the title asks, does $\pi(x) \geq \mathrm{Li}(x)$ imply that $\vartheta(x) \geq x$? Here $\pi(x) = \#\{p \leq x\}$, $\vartheta(x) = \sum_{p \leq x} \log p$ and $\mathrm{Li}(x) = \...
3
votes
0answers
180 views

Prime powers between $x$ and $x+x^\theta$

By the result of Baker, Harman, Pintz (http://www.cs.umd.edu/~gasarch/BLOGPAPERS/BakerHarmanPintz.pdf), for any sufficiently large $x$ the interval $[x-x^{21/40},x]$ contains a prime number. This ...
1
vote
1answer
246 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 ...
1
vote
0answers
152 views

R.H. equivalent statement condition

Is the inequality $\prod \limits_{p \leq \sqrt{x}} (1+\frac{1}{p^2-1}) \prod \limits_{p \leq x} (1+\frac{1}{p}) \leq e^\gamma \ln(\theta(\sqrt{x})+\theta(x))$ where $\theta(x)$ is the Chebyshev's ...
1
vote
1answer
324 views

nth prime better approximation

let $n$ be some integer then from Wikipedia i got that : $p_n \approx n(\ln n + \ln \ln n -1 + \frac{\ln \ln n-2}{\ln n}+\frac{6\ln \ln n-(\ln \ln n)^2-11}{\ln^2 n} $. what is a better approximation ...
3
votes
2answers
361 views

Odd Chebyshev, part 1

QUESTION Find all triples of odd natural numbers $\ a < b\ $ and $\ c\ $ such that $\ a+b = c-1\ $ and $$ \frac {c!!}{a!!\cdot b!!}\ =\ \frac {P(c)}{P(b)} $$ where $\ P(x) \ $ is the product of ...
23
votes
3answers
4k 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) \...
0
votes
1answer
259 views

Numbers related to the Riemann hypothesis

Are there numbers $k > 1$ and $c > 1$ such that: 1 ) $\theta(c) \geq c \left( 1-\frac{1}{5 \ln^2(c)} \right) $ 2 ) $\frac{c}{1+\frac{1}{\ln^4(c)}} \leq p(\pi(c))$ where $p(n)$ is the $n$-th ...
0
votes
1answer
250 views

prime counting function pi bounds [closed]

is it true that for some integer $n_0$, that all integer numbers n such that $n \geq n_0$ the following holds true for the prime counting function : $\frac{x}{\ln x} (1+\frac{1}{\ln x}+\frac{2}{\ln^2 ...
8
votes
2answers
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^{\...
0
votes
2answers
275 views

On a coprime generalization of Cramer's conjecture

Given a large enough integer $n\in\Bbb N$ and a real $r\in\big(0,\frac12\big]$ and $n_1\in\Bbb N_{> n}$ is the smallest integer such that $n_1=AB$ for two coprime integers $A$ bigger than but close ...
3
votes
2answers
210 views

Is there a tighter bound than $\alpha=4$ in $ \prod_{i=1}^n p_i < \alpha^{p_n} $?

With $p_i$ being the $i$-th prime, I'm wondering whether there is a tighter bound than $\alpha = 4$ in the relation $$ \prod_{i=1}^n p_i < \alpha^{p_n} $$ $\alpha = 4$, which is tight enough to be ...
2
votes
1answer
96 views

converge inequality for squares of primes

Does this inequality always hold : $$\frac{1}{6} \pi ^2 \prod _{i=1}^x \frac{\left(p_i\right){}^2-1}{\left(p_i\right){}^2}\leq \frac{1}{p_x}+1 $$ such that $p_i$ is the $i$-th prime number
0
votes
1answer
253 views

Mertens' 3rd theorem, upper bound

Is it true that $$\prod_{p\le x}\frac p{p-1}\le e^\gamma\ln x\left(1-\frac{0{.}011}{\ln x}+\frac{0.2}{(\ln x)^2}\right)$$ for all $x>25\,000$, where the product is over prime $p$?
1
vote
0answers
74 views

Smallest interval for which the number of primes in each is non-increasing [closed]

Consider the intervals $[0, x)$, $[x, 2x)$, $[2x, 3x)$, ... in $\mathbb{Z}$. Let's call this sequence of intervals $I_1$, $I_2$, $I_3$, ... Let the function $p(I)$ return the number of primes in an ...
2
votes
0answers
95 views

Wiener-Ikehara Theorem and Signal Processing

I am trying to understand the Wiener-Ikehara Tauberian theorem which can be a step to understanding the prime number theorem. Let $$ \hat{a}(s) = \int_0^\infty e^{-us}\, da(u) $$ with $a(u)$ some ...
7
votes
0answers
290 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 ...
7
votes
1answer
252 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 ...
2
votes
1answer
339 views

How to count fixed-sized subsets of pairwise co-prime numbers less than a prime, satisfying an additional ‎constraint‎?

In part of my research, I need to count (or find a polynomial bound for) the number of ‎possible ‎ways to select $n$ distinct integers less than the prime $p$, say $r_1, r_2, …, r_n$, which ‎are ...
1
vote
0answers
73 views

A prime number simplex

Let $\ n\in\mathbf N:= \{1\ 2\ \ldots\}\ $ be a natural number. Let $\ K\ $ be a non-empty finite set of primes. Let $\ \kappa:=|K|.\ $ Consider a $\kappa$-dimensional simplex $\ S_K\subseteq \mathbf ...
7
votes
1answer
209 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. ...
1
vote
1answer
605 views

What is the best currently proven bounds on prime gaps?

I did some digging around on the internet but I found tons of different equations on both lower and upper bounds for the largest possible prime gap g(n). I was wondering what are currently the best ...
3
votes
0answers
274 views

Effective prime number theorem

The prime number theorem implies that for every $ϵ>0$, there is $n_\epsilon$ such that for all $n≥n_\epsilon$ the number of primes in $[n,cn]$ is at least $\frac{(c−1−\epsilon)n}{\log n}$ and at ...
1
vote
0answers
58 views

Distribution of primes and near-primes among $\prod p_k \pm 1$

For $n\in \Bbb{Z}^+$ define the statement "$n$ is $k$-social" to mean that $$ \prod_{i=1}^n p_i +1 \mbox{ has exactly } k \mbox{ prime factors} $$ where $p_i$ is the $i$-th prime. So for example $5$ ...
1
vote
0answers
161 views

Density of ratios of an arbitrary increasing sequence of prime numbers

It is well known that the set $\left\{ \frac{p}{q} : p,q \textrm{ prime numbers }\right\}$ is dense in the positive real numbers $\mathbb{R}_{>0}$. Not having a background in number theory, I ask ...
3
votes
0answers
152 views

Does data suggest $| \pi_2 (n) - 2\Pi \int_2^n \frac{dx}{\ln(x)^2} | < \ln(n+2)^2 \sqrt (n+2) $?

Let $\Pi$ be the twin prime constant and $\pi_2(n)$ the twin prime counting function. Define $$ t(n) = \left| \pi_2(n) - 2 \Pi \int_2^n \frac{dx}{\ln(x)^2} \right| $$ Is it consistent with current ...
8
votes
1answer
335 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 ...
9
votes
3answers
768 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 ...
6
votes
2answers
821 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} \ \ ?$$
5
votes
3answers
701 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 ...
0
votes
2answers
164 views

Min number of primes up to n

According to the prime number theorem there are about $n/\ln(n)$ primes less than $n$. This value is a limit but it could fluctuate. My question is, is there a known bound on this fluctuation? i.e. ...
7
votes
3answers
502 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 ...