New types of inequalities.

Prove/disprove the following inequalities.

If $M$ and $k$ are natural numbers, then

$1) \sum_{n=1}^{M} \phi(n) \geq \frac{1}{\sum_{n=1}^{M} \phi (n)}$

$2)\sum_{n=1}^{M} \phi(n) \geq \sum_{n=1}^{M} \phi(\phi(n))$

Notation: $\phi(\cdot)$ denotes Euler's totient function.

Stay updated with my new inequality notes !!!

#NumberTheory

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

since the sum on the LHS is ≥1, it is ≥ its reciprocal.
Lemma: $\phi(n^k)≥\phi(n)^k$

proof: $\phi(n^k)=n^{k-1}\phi(n)≥\phi^k(n)\to n^{k-1}≥\phi^{k-1}(n)\to n≥\phi(n)$ which we know is true. the result follows

3. $n≥\phi(n)$ let $n=\phi(x)$ the $\phi(x)≥\phi(\phi(x))$ and the result follows.

Aareyan Manzoor - 5 years, 3 months ago

right, exactly. The only non-trivial one is $\phi(n^k)=n^{k-1}\phi(n)$

Otto Bretscher - 5 years, 3 months ago

Darn I worked so hard to type the whole solution.

Thank god I started from the bottom, otherwise I would've worked harder, only to receive nothing :P

Mehul Arora - 5 years, 3 months ago

I thought about them during my morning shower, and they all appear to be true. Want any proofs? They are all one liners...

Otto Bretscher - 5 years, 3 months ago

Morning shower is the best place to think abt maths , ;) , Actually I thought abt them and their proofs , in my morning shower

A Former Brilliant Member - 5 years, 3 months ago

Q3. We will prove that $\phi (n) > \phi (\phi (n))$

$\phi (n) = n \times (1- \dfrac {1}{a_1}) \times (1- \dfrac {1}{a_2}) \times \cdots \times \dfrac {1}{a_k}$ where $n = a_1 ^{p_1} a_2 ^{p_2}\cdots a_k ^{p_k}$ where $a_1,a_2...., a_k$ are prime numbers, and $p_1,p_2..., p_k$ are positive integers.

Now, $\phi (\phi (n)) = \phi (n \times (1- \dfrac {1}{a_1}) \times (1- \dfrac {1}{a_2}) \times \cdots \times \dfrac {1}{a_k}))$

We observe that $\phi (n) < n$ , because it is multiplied by fractions less than 1.

Thus , we show that $\phi (\phi (n)) \leq \phi (n)$ , thus the inequality holds true.

Mehul Arora - 5 years, 3 months ago

Small correction : $\phi(n)\leq n$ since you have equality for $n=1$

Otto Bretscher - 5 years, 3 months ago

Oops yeah, thanks :D

Mehul Arora - 5 years, 3 months ago

Nicely done Mehul !

A Former Brilliant Member - 5 years, 3 months ago

Thanks Chinmay! :D

I was about to write the other proofs as well, but Aareyan beat me ;)

Mehul Arora - 5 years, 3 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$