Skip to main content
added 94 characters in body
Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

Yes, $A(n)$ has zero natural density. It suffices to prove this for $n$ which is a power of $10$. and it is possible to make this more precise. To see this, first let $n=10^k$ and note that for $X$ chosen uniformly among integers in $[0,n-1]$, the sum $S(X)$ of base 10 digits is the sum of $k$ i.i.d. random variables uniformly distributed among integers in $[0,9]$. By the Local Central Limit Theorem for i.i.d. lattice variables (see, e.g. [1], [2] for a precise formulation) the law of $S(X)$ is very well approximated by a normal density of standard deviation of order $\sqrt{k}$ centered at $4.5k$. Now use the elementary fact that for any $f(k) \to \infty$ and any $B>1$, the asymptotic frequency of primes in $[k, k+f(k)]$ is at most $\prod_{p \le B} (1-1/p) $. This product over primes tends to 0 as $B \to \infty$, proving the asymptotic density of $A(n)$ is zero.

Remark: Together with the PNT [3] one gets the prediction $$A(n)/n=\frac{1+o(1)}{\log \log(n)} \,,(*) $$ but the PNT does not imply this, one needs to use more precise information on the number of primes in short intervals, a topic of much research, see e.g. [4], [5] and the references therein. In particular, the sieve estimate of Montgomery-Vaughn, cited (See Cor 3.4 in [5],[4]) yields $$A(n)/n\le \frac{2+o(1)}{\log \log(n)} \,.$$$$A(n)/n\le \frac{4+o(1)}{\log \log(n)} \,.$$

[1] https://encyclopediaofmath.org/wiki/Local_limit_theorems

[2] V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian)

[3] https://en.wikipedia.org/wiki/Prime_number_theorem

[4] https://en.wikipedia.org/wiki/Maier%27s_theoremMontgomery, Hugh L., and Robert C. Vaughan. Multiplicative number theory I: Classical theory. Vol. 97. Cambridge university press, 2007.

[5] How many primes can there be in a short interval?

Yes, $A(n)$ has zero natural density. It suffices to prove this for $n$ which is a power of $10$. and it is possible to make this more precise. To see this, first let $n=10^k$ and note that for $X$ chosen uniformly among integers in $[0,n-1]$, the sum $S(X)$ of base 10 digits is the sum of $k$ i.i.d. random variables uniformly distributed among integers in $[0,9]$. By the Local Central Limit Theorem for i.i.d. lattice variables (see, e.g. [1], [2] for a precise formulation) the law of $S(X)$ is very well approximated by a normal density of standard deviation of order $\sqrt{k}$ centered at $4.5k$. Now use the elementary fact that for any $f(k) \to \infty$ and any $B>1$, the asymptotic frequency of primes in $[k, k+f(k)]$ is at most $\prod_{p \le B} (1-1/p) $. This product over primes tends to 0 as $B \to \infty$, proving the asymptotic density of $A(n)$ is zero.

Remark: Together with the PNT [3] one gets the prediction $$A(n)/n=\frac{1+o(1)}{\log \log(n)} \,,(*) $$ but the PNT does not imply this, one needs to use more precise information on the number of primes in short intervals, a topic of much research, see e.g. [4], [5] and the references therein. In particular, the sieve estimate of Montgomery-Vaughn, cited in [5], yields $$A(n)/n\le \frac{2+o(1)}{\log \log(n)} \,.$$

[1] https://encyclopediaofmath.org/wiki/Local_limit_theorems

[2] V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian)

[3] https://en.wikipedia.org/wiki/Prime_number_theorem

[4] https://en.wikipedia.org/wiki/Maier%27s_theorem

[5] How many primes can there be in a short interval?

Yes, $A(n)$ has zero natural density. It suffices to prove this for $n$ which is a power of $10$. and it is possible to make this more precise. To see this, first let $n=10^k$ and note that for $X$ chosen uniformly among integers in $[0,n-1]$, the sum $S(X)$ of base 10 digits is the sum of $k$ i.i.d. random variables uniformly distributed among integers in $[0,9]$. By the Local Central Limit Theorem for i.i.d. lattice variables (see, e.g. [1], [2] for a precise formulation) the law of $S(X)$ is very well approximated by a normal density of standard deviation of order $\sqrt{k}$ centered at $4.5k$. Now use the elementary fact that for any $f(k) \to \infty$ and any $B>1$, the asymptotic frequency of primes in $[k, k+f(k)]$ is at most $\prod_{p \le B} (1-1/p) $. This product over primes tends to 0 as $B \to \infty$, proving the asymptotic density of $A(n)$ is zero.

Remark: Together with the PNT [3] one gets the prediction $$A(n)/n=\frac{1+o(1)}{\log \log(n)} \,,(*) $$ but the PNT does not imply this, one needs to use more precise information on the number of primes in short intervals, a topic of much research, see e.g. [4], [5] and the references therein. In particular, the sieve estimate of Montgomery-Vaughn (See Cor 3.4 in [4]) yields $$A(n)/n\le \frac{4+o(1)}{\log \log(n)} \,.$$

[1] https://encyclopediaofmath.org/wiki/Local_limit_theorems

[2] V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian)

[3] https://en.wikipedia.org/wiki/Prime_number_theorem

[4] Montgomery, Hugh L., and Robert C. Vaughan. Multiplicative number theory I: Classical theory. Vol. 97. Cambridge university press, 2007.

[5] How many primes can there be in a short interval?

Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

Yes, $A(n)$ has zero natural density. It suffices to prove this for $n$ which is a power of $10$. and it is possible to make this more precise. To see this, first let $n=10^k$ and note that for $X$ chosen uniformly among integers in $[0,n-1]$, the sum $S(X)$ of base 10 digits is the sum of $k$ i.i.d. random variables uniformly distributed among integers in $[0,9]$. By the Local Central Limit Theorem for i.i.d. lattice variables (see, e.g. [1], [2] for a precise formulation) the law of $S(X)$ is very well approximated by a normal density of standard deviation of order $\sqrt{k}$ centered at $4.5k$. Now use the elementary fact that for any $f(k) \to \infty$ and any $B>1$, the asymptotic frequency of primes in $[k, k+f(k)]$ is at most $\prod_{p \le B} (1-1/p) $. This product over primes tends to 0 as $B \to \infty$, proving the asymptotic density of $A(n)$ is zero.

Remark: Together with the PNT [3] one gets the prediction $$A(n)/n=\frac{1+o(1)}{\log \log(n)} \,,(*) $$ but the PNT does not imply this, one needs to use more precise information on the number of primes in short intervals, a topic of much research, see e.g. [4], [5] and the references therein. In particular, the sieve estimate of Montgomery-Vaughn, cited in [5], yields $$A(n)/n\le \frac{2+o(1)}{\log \log(n)} \,.$$

[1] https://encyclopediaofmath.org/wiki/Local_limit_theorems

[2] V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian)

[3] https://en.wikipedia.org/wiki/Prime_number_theorem

[4] https://en.wikipedia.org/wiki/Maier%27s_theorem

[5] How many primes can there be in a short interval?