Erdos – Katz Theorem

The Erdшаs – Katz theorem is a statement in number theory that relates the distribution of the number of different prime divisors of large numbers to the formulas of the limit laws of probability theory . This result of number theory , obtained by Pal Erdös and Mark Katz in 1940, states that if $\omega (n)$ ${\ displaystyle \ omega (n)}$ $\ omega (n)$ - the number of different prime divisors of the number $n$ ${\ displaystyle n}$ $n$ , then the limit distribution of the quantity

{\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}

{\ displaystyle {\ frac {\ omega (n) - \ log \ log n} {\ sqrt {\ log \ log n}}}}

{\ displaystyle {\ frac {\ omega (n) - \ log \ log n} {\ sqrt {\ log \ log n}}}}

is the standard normal distribution . This is a deep generalization of the Hardy – Ramanujan theorem , which states that the “mean” value $\omega (n)$ ${\ displaystyle \ omega (n)}$ $\ omega (n)$ equally $\log \log n$ ${\ displaystyle \ log \ log n}$ ${\ displaystyle \ log \ log n}$ , and the "average deviation" is not more than ${\sqrt {\log \log n}}$ ${\ displaystyle {\ sqrt {\ log \ log n}}}$ ${\ displaystyle {\ sqrt {\ log \ log n}}}$ .

Content

Theorem

More formally, the theorem states that for any fixed $a<b$ ${\ displaystyle a <b}$ done:

\lim _{x\rightarrow \infty }{\frac {1}{x}}\left|\left\{n\leq x:a\leq {\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}\leq b\right\}\right|=\Phi (a,b)

{\ displaystyle \ lim _ {x \ rightarrow \ infty} {\ frac {1} {x}} \ left | \ left \ {n \ leq x: a \ leq {\ frac {\ omega (n) - \ log \ log n} {\ sqrt {\ log \ log n}}} \ leq b \ right \} \ right | = \ Phi (a, b)}

,

Where

\Phi (a,b)={\frac {1}{\sqrt {2\pi }}}\int _{a}^{b}e^{-t^{2}/2}\,dt.

{\ displaystyle \ Phi (a, b) = {\ frac {1} {\ sqrt {2 \ pi}}} \ int _ {a} ^ {b} e ^ {- t ^ {2} / 2} \ , dt.}

.

Original Proof

In the original proof ^{[1], the} statement about the normality of the distribution in the first lemma of the theorem is based on the fact that the function $\omega (n)$ ${\ displaystyle \ omega (n)}$ is additive and can be represented as the sum of indicators of divisibility by primes. Further, without introducing the concept of random variable, the authors argue that the indicator terms are independent ^[2] . Then, without going into details, the authors refer to the source ^[3] , where the normality of the distribution is proved for sums of weakly dependent random variables ^[4] . At the end of the proof, the authors apologize for the superficiality of the “statistical” ^[5] lemma.

In 1958, Alfred Renyi and Pal Turan provided more accurate evidence.

Features

The theorem is about the distribution of deterministic quantities, and not about the probability distribution of a random variable . But if on a sufficiently large segment of natural numbers randomly choose a number $n$ ${\ displaystyle n}$ , then the number of different prime divisors of this number will have an approximately normal distribution with a mathematical expectation and dispersion equal to the average value $\log \log n$ ${\ displaystyle \ log \ log n}$ on the segment. Since this function, called the repeated logarithm, grows slowly, such averaging will not lead to a big error even on very long segments. The form of the distribution connects the Erdшаos – Katz theorem with the central limit theorem .

Repeat Logarithm Growth Rate

The repeat logarithm is an extremely slowly growing function. In particular, numbers up to a billion contain, on average, three primes in the decomposition into primes.

For example, 1,000,000,003 = 23 × 307 × 141 623 .

n	Number of characters in n	The average number of primes in the expansion	average deviation
1000	four	2	1.4
1,000,000,000	ten	3	1.7
1,000,000,000,000,000,000,000,000,000	25	four	2
10 ⁶⁵	66	five	2.2
10 ⁹⁵⁶⁶	9567	ten	3.2
10 ^{210 704 568}	210 704 569	20	4,5
10 ^{10 ²²}	10 ²² +1	50	7.1
10 ^{10 ⁴⁴}	10 ⁴⁴ +1	100	ten
10 ^{10 ⁴³⁴}	10 ⁴³⁴ +1	1000	31.6

If you fill a ball the size of the Earth with sand, you will need about 10 ³³ grains of sand. To fill the visible part of the universe, 10 ⁹³ grains of sand would be required. 10 ¹⁸⁵ quantum strings can also fit there.

Numbers of this size - with 186 characters - on average consist of only 6 primes in the expansion.

Notes

↑ Paul Erdős , Mark Kac. The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions // American Journal of Mathematics. - 1940. - T. 62 , No. 1/4 . - S. 738-742 . (MR2, 42c; Zentralblatt 24, 102
↑ If the number $n$ ${\ displaystyle n}$ divided by $m$ ${\ displaystyle m}$ , then it is not divided into simple $p>{\frac {n}{m}}$ ${\ displaystyle p> {\ frac {n} {m}}}$ . This means that if several indicators have taken the value 1, then the remaining indicators are equal to 0. The indicators are weakly interdependent and, in addition, have different distributions.
↑ Cf. for instance the first chapter of S. Bernstein's paper, "Sur I'extension du theoreme limite du calcul des probabilites aux sommes de quantites dependantes", Mathematische Annalen, vol. 97, pp. 1-59.
↑ The interdependence of the terms is apparently assumed, but not specified.
↑ Authors quotes.

Links

Weisstein, Eric W. Erdős – Kac Theorem on the Wolfram MathWorld website.
Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)

[1] Paul Erdős , Mark Kac. The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions // American Journal of Mathematics. - 1940. - T. 62 , No. 1/4 . - S. 738-742 . (MR2, 42c; Zentralblatt 24, 102

[2] If the number $n$ ${\ displaystyle n}$ divided by $m$ ${\ displaystyle m}$ , then it is not divided into simple $p>{\frac {n}{m}}$ ${\ displaystyle p> {\ frac {n} {m}}}$ . This means that if several indicators have taken the value 1, then the remaining indicators are equal to 0. The indicators are weakly interdependent and, in addition, have different distributions.

[3] Cf. for instance the first chapter of S. Bernstein's paper, "Sur I'extension du theoreme limite du calcul des probabilites aux sommes de quantites dependantes", Mathematische Annalen, vol. 97, pp. 1-59.

[4] The interdependence of the terms is apparently assumed, but not specified.

[5] Authors quotes.