Skip to main content
added 4 characters in body
Source Link
Terry Tao
  • 114.2k
  • 33
  • 462
  • 539

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/2W \leq N \leq X/W$ is an integer. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these "probabilities" to be "independent", then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w < p \leq \log^2 X$, or $WN \pm pq$ for some primes $w < p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be independent"independent", then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the probability"probability" of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which is well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form (maybe after numerically optimizing the $w$ parameter$w, X$ parameters to maximize the predicted probability of success for a given budget of search time, and maybe also shifting to $[WN, WN+2\log^2 X]$ instead which has marginally fewer candidates) may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/2W \leq N \leq X/W$ is an integer. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these "probabilities" to be "independent", then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w < p \leq \log^2 X$, or $WN \pm pq$ for some primes $w < p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be independent, then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the probability of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which is well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form (maybe after optimizing the $w$ parameter, and maybe also shifting to $[WN, WN+2\log^2 X]$ instead which has marginally fewer candidates) may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/2W \leq N \leq X/W$ is an integer. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these "probabilities" to be "independent", then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w < p \leq \log^2 X$, or $WN \pm pq$ for some primes $w < p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be "independent", then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the "probability" of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which is well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form (maybe after numerically optimizing the $w, X$ parameters to maximize the predicted probability of success for a given budget of search time, and maybe also shifting to $[WN, WN+2\log^2 X]$ instead which has marginally fewer candidates) may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.

added 132 characters in body
Source Link
Terry Tao
  • 114.2k
  • 33
  • 462
  • 539

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/W \leq X \leq 2X/W$$X/2W \leq N \leq X/W$ is an integer. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these probabilities"probabilities" to be independent"independent", then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w \leq p \leq \log^2 X$$w < p \leq \log^2 X$, or $WN \pm pq$ for some primes $w \leq p,q$$w < p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be independent, then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the probability of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which is well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form (maybe after optimizing the $w$ parameter, and maybe also shifting to $[WN, WN+2\log^2 X]$ instead which has marginally fewer candidates) may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/W \leq X \leq 2X/W$. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these probabilities to be independent, then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w \leq p \leq \log^2 X$, or $WN \pm pq$ for some primes $w \leq p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be independent, then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the probability of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/2W \leq N \leq X/W$ is an integer. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these "probabilities" to be "independent", then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w < p \leq \log^2 X$, or $WN \pm pq$ for some primes $w < p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be independent, then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the probability of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which is well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form (maybe after optimizing the $w$ parameter, and maybe also shifting to $[WN, WN+2\log^2 X]$ instead which has marginally fewer candidates) may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.

Source Link
Terry Tao
  • 114.2k
  • 33
  • 462
  • 539

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/W \leq X \leq 2X/W$. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these probabilities to be independent, then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w \leq p \leq \log^2 X$, or $WN \pm pq$ for some primes $w \leq p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be independent, then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the probability of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.