레프네 약방

3 Distinct proofs on lower bound of Euler's totient function

2018. 6. 27. 20:30수학 이론/정수론

Definition.

$$\phi(n)$$ : Number of natural numbers in $$1..n$$, which are relatively prime to $$n$$.

$$\sigma(n)$$ : Sum of divisors of $$n$$, including $$1$$ and $$n$$ itself.

claim.

$$n > 1 \Rightarrow \phi(n) > \frac{n}{4\log n}$$

This section is intentionally left blank.

Special thanks: H. Cho, W. Song.

Solution 1. (Official)

$$n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}$$.

$$\phi(n) = n \prod_{i = 1}^{k} \left( 1 - \frac{1}{p_{i}} \right) = n \left( 1 - \frac{1}{p_{1}} \right) \cdots \left( 1 - \frac{1}{p_{k}} \right)$$

$$= n \frac{\color{red}{ \prod_{i = 1}^{k} \left( 1 - \frac{1}{p_{i}^2} \right)}}{\color{blue}{ \prod_{i = 1}^{k} \left( 1 + \frac{1}{p_{i}} \right)}} > n\frac{\color{red}{ \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k^2} \right) }}{\color{blue}{ \prod_{i = 1}^{k} \left( 1 + \frac{1}{p_{i}} \right) }}$$

By expanding blue term, we acquire the sum of reciprocal of distinct integers. ( $$\because \forall p_{i}$$ are distinct )

Hence, the blue term is less than $$\color{blue}{1 + \frac{1}{2} + \cdots \frac{1}{n}}$$, which is definitely smaller than $$\color{blue}{1 + \log n < 2\log n}$$.  $$( \because \prod p_{i} \le n )$$

The red term can be reduced by the following telescoping step.

$$\color{red}{ \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k^2} \right) = \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k} \right)\left( 1 + \frac{1}{k} \right) = \frac{1}{2} }$$

Therefore,

$$\phi(n) > n\frac{\color{red}{ \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k^2} \right) }}{\color{blue}{ \prod_{i = 1}^{k} \left( 1 + \frac{1}{p_{i}} \right) }} > n\frac{\color{red}{1/2}}{\color{blue}{2\log n}} = \frac{n}{4\log n} \blacksquare$$

Solution 2. (TAMREF. Yun.)

$$n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}$$.

Lemma. $$\sigma(n) < n ( 1 + \log n )$$.

pf) $$\sigma(n) = \sum_{d | n} d = \sum_{d | n} \frac{n}{d} = n \sum_{d |n } \frac{1}{d} \le n \sum_{d \le n} \frac{1}{d} \le n (1 + \log n). \blacksquare$$

$$\frac{\phi (n) \sigma(n)}{n} = \prod_{i = 1}^{k} \left( 1 - \frac{1}{p_i} \right) \cdot \frac{p_{i}^{e_{i}+1}-1}{p_{i}-1} = \prod_{i = 1}^{k} \frac{p_{i}^{e_{i} + 1} - 1}{p_{i}} = \prod_{i = 1}^{k} \left( p_{i}^{e_{i}} - \frac{1}{p_{i}} \right)$$

$$= \prod_{i = 1}^{k} \color{red}{p_{i}^{e_{i}}} \left(1 - \frac{1}{p_{i}^{e_{i}+1}}\right)= \color{red}{n} \prod_{i=1}^{k} \left( 1 - \color{blue}{\frac{1}{p_{i}^{e_{i}+1}}} \right) \ge n \prod_{i=1}^{k} \left( 1 - \color{blue}{\frac{1}{p_{i}^{2}}} \right)$$

Since $$(1-x_{1})(1-x_{2})\cdots (1-x_{n}) > 1-x_{1}-x_{2}-\cdots x_{n}$$ for $$x_{i} < 1$$,

$$\frac{\phi (n) \sigma (n)}{n} \ge n \prod_{i=1}^{k} \left( 1 - \frac{1}{p_{i}^{2}} \right) > n \left( 1 - \sum_{i=1}^{k} \frac{1}{p_{i}^2} \right) > n \left( 1 - \sum_{p} \frac{1}{p^2} \right)$$

From the following inequality (we can tighten the bound up to $$0.4522$$ by googling) and the Lemma,

$$\sum_{p} \frac{1}{p^2} < \sum_{k \text{ : odd}} \frac{1}{k^2} + \frac{1}{2^2} - \frac{1}{1^2} = \frac{3}{4}\zeta (2) - \frac{3}{4} = \frac{\pi^2}{8} - \frac{3}{4} \sim 0.4837$$

$$\phi(n) > \frac{n^2 \cdot (1-0.4837)}{\sigma(n)} > \frac{0.5162n}{(1+\log n)} > \frac{0.2581n}{\log n} > \frac{n}{4\log n}. \blacksquare$$

Solution 3. (Hatalova, Salat)

$$n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k} \quad (p_1 < p_2 < \cdots p_k)$$.

claim) $$4\log n > \frac{n}{\phi(n)} = \prod_{i=1}^{k} \frac{p_{i}}{p_{i}-1}$$

pf.

$$4\log n \ge 4(\log p_1 + \log p_2 + \cdots \log p_k) \ge 4k\log 2 \ge 2\log 2 (k + 1) = (2\log 2) \frac{2}{1} \cdot \frac{3}{2} \cdots \frac{k+1}{k}$$

Since $$p_k \ge k+1$$ and $$f(x) = \frac{x}{x-1}$$ is decreasing on $$x > 1$$, the inequality $$\frac{i+1}{i} \ge \frac{p_{i}}{p_{i}-1}$$ holds.

$$\therefore 4\log n \ge 2\log 2 \prod_{i=1}^{k} \frac{i+1}{i} \ge 2\log 2 \prod_{i=1}^{k} \frac{p_{i}}{p_{i}-1} = 2\log 2 \frac{n}{\phi(n)} \gtrsim \frac{1.39n}{\phi(n)}$$

$$\therefore \phi(n) \ge \frac{1.39n}{4\log n} > 0.346\frac{n}{\log n} > \frac{n}{4\log n} \blacksquare$$

'수학 이론 > 정수론' 카테고리의 다른 글

 Apostol 해석적 정수론 CH3. 28~31  (0) 2018.12.07 2018.12.07 2018.06.27 2018.02.17 2017.10.14 2017.08.15