11

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^{\log\log n}=\log n$ seems to make both facts related.

How related are these two facts in number theory?

Let me put it in this way.

Suppose we somehow naturally choose a subset of natural numbers where Erdos-Kac law applies but with average factors as $f(\log\log n)$ for some $f(x)=o(x)$ then how many primes of magnitude $n$ can we expect in this subset? Say for instance $f(\log\log n)=(\log\log n)^\alpha$ or $f(\log\log n)=(\log\log\log n)^{1/\alpha}$ where $0<\alpha\ll1$ holds?

I think such sets should typically have $\frac{n}{2^{f(\log\log n)}}\gg\frac{n}{\log n}$ primes.

Martin Sleziak
  • 4,608

2 Answers2

18

Yes. The number of prime factors of a number is distributed roughly like a Poisson process of expectation $\log \log n$, so the probability of exactly one prime factor is roughly $e^{- \log \log n} = 1/\log n$.

Remember that natural numbers of size roughly $n$ correspond, in the number field / function field dictionary, to polynomials of degree roughly $\log n$, whose prime factorizations are controlled by the permutation of Frobenius acting on the roots, a random permutation of $\log n$ letters, where primes correspond to cycles. You can check that the distribution of the number of cycles of a random permutation is close to a Poisson process because, e.g., writing permutations in standard cycle form, the chance of stopping a cycle after a given number of letters is determined only by number of previous letters and not the previous cycles, so the number of cycles is a sum of many independent random variables.

However this will not rigorously establish facts about numbers.

For your second question, I think you will find it very hard to find a natural set of numbers where the average number of prime factors changes, without doing something very drastic to the distribution. In general, one finds that the distribution of the number of prime factors is very insensitive to almost all conditions you can place on a number (e.g. congruence conditions), other than conditions stated directly in terms of the prime factorization.

Of course for a condition stated in terms of the prime factorization, there is no reason to expect that the number of prime factors and the probability of being prime should move in tandem.

Will Sawin
  • 135,926
  • Could you please be little bit more technical with your post with some references for indepth read? So you do not expect my $\frac{n}{2^{f(\log\log n)}}$ hypothesis to hold? Under what conditions could the hypothesis hold? –  Dec 18 '16 at 10:09
  • @AJ. I will give some technical details, but there is no hope for a technical answer to your last question without a precise definition of "naturally choose a subset of numbers". I expect that, if you choose a very lax definition (allowing e.g. a class of smooth numbers) then it will not hold, and if you choose a more stringent definition, there will be no examples where $f(\log \log n)$ is very far from $\log \log n$. – Will Sawin Dec 18 '16 at 10:16
  • "ON THE DISTRIBUTION OF 2-SELMER RANKS WITHIN QUADRATIC TWIST FAMILIES OF ELLIPTIC CURVES WITH PARTIAL RATIONAL TWO-TORSION" by ZEV KLAGSBRUN shows in appendix square free integers have $\omega(\log\log\log n)$ mean and Erdos-Kac distribution. This was the motivation for the query. I was really really really curious if PNT then fails or weakens for these sets? –  Dec 18 '16 at 10:19
  • @AJ. I don't think that's what the paper says. If you want to set $g(p)=1$ for all $p$, don't you fail the conditon $B(x) = \sqrt{\sum_{p \leq x} \frac{g(p)^2}{p}}= \omega (\log \log \log x)$? – Will Sawin Dec 18 '16 at 10:32
  • @Aj. I can certainly tell you what the prime number theorem is for squarefree numbers! Because all primes are squarefree, a density $1/\log n$ of all numbers of size about $n$ are prime, and a density $6/\pi^2$ of all numbers are squarefree, a density $\pi^2/6 \log n$ of all squarefree numbers are prime. – Will Sawin Dec 18 '16 at 10:33
  • I am wrong on the paper. You are right. (seeing your $\pi^2/6$ comment yes that makes sense). –  Dec 18 '16 at 10:34
  • Removed my comment your intuition may be right on Erdos-Kac for subsets. –  Dec 18 '16 at 10:44
  • "the distribution of the number of prime factors is very insensitive to almost all conditions you can place on a number (e.g. congruence conditions), other than conditions stated directly in terms of the prime factorization" could you provide more details and references? –  Dec 18 '16 at 20:59
  • 1
    @AJ. Well, any congruence condition, or any condition like squarefreeness that can be sieved, is basically independent of the number of prime factors. To prove this, one observes that the average number of prime factors of elements of a set $S$ of size at most $x$ is the sum over $p \leq x$ of the fraction of elements of $S$ divisible by $p$. As long as that number is close to $1/p$, the average will be close to $\log \log x$. For a congruence condition all but finitely many of the fractions will be the same, and for squarefree they are only slightly altered - to $p/(p^2-1)$. – Will Sawin Dec 18 '16 at 21:08
  • "One observes that the average number of prime factors of elements of a set S of size at most x is the sum over p≤x of the fraction of elements of S divisible by p." Is this easy to see? (some kind of local global relation is happening or is it just counting argument of total number offactors of all integers in the set?). –  Dec 18 '16 at 21:30
  • 1
    @AJ. Yes it's just a counting argument and exchanging the order of summation. The number of prime factors of the number $n\leq x$ is the sum over $p\leq x$ of $1$ if $p$ divides $n$ and $0$ otherwise. Sum over $n$ in $S$, divide by $|S|$, then exchange the order of summation. – Will Sawin Dec 19 '16 at 05:10
  • 'Of course for a condition stated in terms of the prime factorization, there is no reason to expect that the number of prime factors and the probability of being prime should move in tandem.' so you are saying number of primes need not be $$\frac{n}{2^{f(\log\log n)}}\gg\frac n{\log n}$$ hard to believe....... is there a rigorous reason? – Turbo Apr 23 '17 at 10:17
  • @Turbo Well, for instance we could take the condition that a number has exactly two prime factors, which would have the average number of prime factors $2$ but the density of primes is zero. – Will Sawin Apr 23 '17 at 14:17
10

The right context of your question is probably the area of Beurling primes. An arithmetic semigroup is a semigroup $(G,\cdot)$ together with a norm $\|\cdot\|:G\rightarrow[1,\infty)$, such that $\|gh\|=\|g\|\|h\|$ and for all $x$ we have that $N(x) = \#\{g\in G: \|g\|\leq x\}$ is finite. Define $\pi(x)$ as the number of indecompsable elements of $G$ with norm $\leq x$. Beurling proved that $N(x)=cx+\mathcal{O}(\frac{x}{x^{3/2+\delta}})$ implies the prime number theorem in the form $\pi(x)\sim\frac{x}{\log x}$, and the condition is best possible in the sense that for every $\delta>0$ there are groups satisfying $N(x)=cx+\mathcal{O}(\frac{x}{x^{3/2-\delta}})$ and $\pi(x)\not\sim\frac{x}{\log x}$.

The theory of Beurling primes has two motivations: On one hand it has applications to algebra and logic, see the books "Abstract analytic number theory" by Knopfmacher and "Number theoretic densities and logical limit laws" by Burris. On the other hand it serves as a context in which "equivalence" of statements about primes can be made precise.

In this context your question becomes: Is the set of arithmetic semigroups satisfying the prime number theorem equal to the set of semigroups satisfying Erdos-Kac? Erdos-Kac is essentially equivalent to $\sum_{p\leq x}\frac{1}{p}\sim\log\log x$, which is obviously implied by the prime number theorem, but Pollack ( http://pollack.uga.edu/beurling.pdf Wayback Machine ) showed that $\sum_{p\leq x}\frac{1}{p}\sim\log\log x$ is equivalent to the statement $\zeta_G(s)\sim\frac{A}{s-1}$, where $\zeta_G(s)=\sum_{g\in G}\|g\|^{-s}$. In particular all semigroups with $N(x)\sim Ax$ satisfy Erdos-Kac, while the counterexamples found by Beurling show that Erdos-Kac is strictly weaker then the prime number theory.

Martin Sleziak
  • 4,608
Jan-Christoph Schlage-Puchta
  • 9,097