Probabilistic number theory

Probabilistic number theory studies arithmetic functions and integer sets through probability distributions, concentration, and limit theorems.

For a real strongly additive arithmetic function with uniformly bounded values on primes, put $A(x)={\sum }_{p\le x}f(p)/p$ and $B(x{)}^2={\sum }_{p\le x}f(p{)}^2/p$. If $B(x)\to \infty$, then $(f(n)-A(N))/B(N)$ under uniform sampling from $[N]$ converges to the standard normal distribution. For the prime omega function, the mean and variance scales are $\log \log N$.

If a strongly additive arithmetic function $g$ is supported on primes up to $y$, its $j$th uniform central moment differs from the independent Bernoulli random variables model with probabilities $1/p$ by $O(j{y}^j({\sum }_{p\le y}|g(p)|{)}^j/N)$. Expansion of divisibility indicator functions reduces the comparison to $\lfloor N/d\rfloor /N=1/d+O(1/N)$.

The Cramér model selects integers $n\ge 3$ independently with probability $1/\log n$, and conventionally sets $U_1=0$, $U_2=1$. It is a random model for the distribution of primes, not an assertion of independence for actual prime numbers.

If $P_n$ are the increasing selected integers in the Cramér model, then almost surely ${\mathrm{limsup}}_n(P_{n+1}-P_n)/(\log P_n{)}^2\le 1$. A zero block of length $(1+ϵ)(\log k{)}^2$ after $k$ has summable probability, so the Borel-Cantelli first lemma excludes these blocks eventually.

The multiplication table problem asks how many distinct integers occur as $ab$ with $1\le a,b\le N$. Counting the $N^2$ pairs greatly overcounts the distinct products.

Concentration of the prime omega function near $\log \log N$, together with $\omega (ab)=\omega (a)+\omega (b)-\omega (\gcd (a,b))$ and the bounded mean of $\omega (\gcd (a,b))$, gives $M(N)\ll N^2/\log \log N$. This elementary argument uses only distinct prime factors.

For an additive arithmetic function $f$, $N^{-1}{\sum }_{n\le N}|f(n)-A_f(N){|}^2\ll B_f(N{)}^2$, where $A_f$ is the mean of an additive arithmetic function and $B_f(N{)}^2={\sum }_{p^k\le N}|f(p^k){|}^2/p^k$. The implied constant is absolute.