Intuition for Euler’s product formula and the $\ln\ln$ runtime

December 24, 2022
Útulek Series, 4 | CF1761D Chapter, 4

Last time, I investigated the $\ln\ln$ runtime of the Sieve of Eratosthenes, and left off with an introduction of Euler’s Product Formula (EPF). I have since come to realize that the domain for which EPF holds is nuanced and may greatly complicate the proof. Thus, instead of providing anything rigorous, I will instead quickly give intuition to EPF.

Recall the Prime Factorization Theorem (PFT), also known as the Fundamental Theorem of Arithmetic:

Theorem 0.1 (Prime Factorization Theorem): Every positive integer can be written as a product of prime numbers, and this product is unique up to the order of the factors.

We have, then, that every positive integer $n$ may be uniquely represented in the following form:

$$n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\ldots$$

for all primes $p_i$ and non-negative exponents $\alpha_i$. Recognizing the RHS of Euler’s product formula as a geometric series, we have

$$\begin{aligned} \zeta(s)&=\prod^\infty (1-1/p_i^s)^{-1}\\ 1^{-s}+2^{-s}+3^{-s}+\ldots&=\prod^\infty (1+p_i^{s}+p_i^{2s}+\ldots)^{-1}. \end{aligned}$$

As intuition, should $s=1$, every positive integer occurs on the LHS exactly once. Similarly, by PFT, the positive integers must form a bijection with the RHS terms. For positive real $s$ in general, any $s$-power $n$ can be represented with each $\alpha_i$ an integer multiple of $s$. Hence, Euler’s product formula should still hold.

Theorem 0.2 (Euler’s Product Formula): For positive real $s$,

$$\zeta(s):=\sum^\infty\frac{1}{i^s}=\prod^\infty (1-1/p_i^s)^{-1}.$$

As the harmonic series (the limit of which is $\zeta(1)$) is $\Theta(\ln N)$, and the RHS of Euler’s Product Formula is remarkably close to the prime harmonic series $P_i$, which we suspect to be $\Theta(\ln\ln N)$, we are inspired to take $\ln$ of both sides:

$$\begin{aligned} \Theta(\ln\ln N)&=\ln(\sum^\infty\frac{1}{i})=\prod^\infty (1-1/p_i)^{-1}\\ &=-\sum^\infty \ln(1-1/p_i). \end{aligned}\tag{0.3}$$

The RHS is actually remarkably similar to the prime harmonic series. Should we take the Taylor series about $x=1$ of $\ln(x)=(x-1)-\frac{(x-1)^2}{2}+\frac{(x-1)^3}{3}-\ldots$, we have

$$\begin{aligned} \Theta(\ln\ln N)&=-\sum^\infty \ln(1-1/p_i)\\ &=\sum^\infty (1/p_i+1/(2p_i^2)+1/(3p_i^3)+\ldots)\\ &=\sum^\infty \frac{1}{p_i}+\frac{1}{2}\sum^\infty \frac{1}{p_i^2}+\frac{1}{3}\sum^\infty \frac{1}{p_i^3}+\ldots\\ &=P_\infty+\text{something}. \end{aligned}$$

There is a lot of abuse of notation going on here. First, taking $\ln$ of a divergent series $\zeta(1)$ in $(0.3)$ is no good, and similarly as $P_\infty$ goes to $\infty$, we do not want to use it explicitly in showing the growth rate of $P_i$. Still, should the $\text{something}$ be convergent, the $\ln\ln$ result is intuitively within grasp.

Unfortunately, I’m a little short on time today, so I’ll leave the Taylor series for next time.