11
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Are you sure $2^{\log\log n}=\log n$? $\endgroup$
    – joro
    Commented Dec 18, 2016 at 16:00
  • $\begingroup$ @joro base $2$ unnatural logarithm. $\endgroup$
    – user94040
    Commented Dec 18, 2016 at 18:38

2 Answers 2

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ 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? $\endgroup$
    – user94040
    Commented Dec 18, 2016 at 10:09
  • $\begingroup$ @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$. $\endgroup$
    – Will Sawin
    Commented Dec 18, 2016 at 10:16
  • $\begingroup$ "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? $\endgroup$
    – user94040
    Commented Dec 18, 2016 at 10:19
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – Will Sawin
    Commented Dec 18, 2016 at 21:08
  • 1
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Commented Dec 19, 2016 at 5:10
10
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @Jan-Christoph Schlage-Puchta when you say $\pi(x)$ is not asymptote to $\frac x{log x}$ does Beurling give more primes or less primes? $\endgroup$
    – user94040
    Commented Dec 18, 2016 at 18:44
  • 1
    $\begingroup$ @AJ: If $N(x)\sim Ax$, you always have $\liminf\frac{\pi(x)\log x}{x}\leq 1\leq\limsup\frac{\pi(x)\log x}{x}$. So $\pi(x)\not\sim\frac{x}{\log x}$ means that the two limits do not coincide. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Dec 19, 2016 at 10:39
  • 1
    $\begingroup$ @AJ see this classic MO question for a little intuition on this. mathoverflow.net/questions/95743/… $\endgroup$
    – Will Sawin
    Commented Dec 19, 2016 at 19:07
  • $\begingroup$ a reference for the needed Tauberian theorem on Dirichlet series with positive coefs $\endgroup$
    – reuns
    Commented Dec 30, 2016 at 12:41

You must log in to answer this question.