# How is this equation (involving a recurrence and $\phi(N)$) derived?

As in another question, let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise} \end{cases}$$

where $$\phi(N)$$ is Euler's totient function.

Tasse kindly reasoned that we can write

$$T(N) = T(\phi(N))+\log(\phi(N))^3 = T(\phi(\phi(N)))+\log(\phi(\phi(N)))^3 + \log(\phi(N))^3$$

I can't at all see why this is true. How is this equation derived? I do understand his proof that $$\phi(\phi(N)) < N/2$$.

## 1 Answer

Here's the relevant part of the proof, quoting verbatim:

First, show that $$\phi(\phi(n)) < n/2$$. This can be done as such:

Let $$n = \prod_{i=1}^rp_i^{k_i}$$ be the prime factorisation of $$n$$ ($$p_i$$ prime, $$k_i>0$$)

• Suppose $$n$$ is even. Then $$\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$$ Thus $$\phi(\phi(n)) < n/2$$.
• Suppose $$n$$ is odd and $$n > 1$$. Then $$\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$$ is even and smaller than $$n$$. By the previous result $$\phi(\phi(n)) < n/2$$.

So we get the desired result.

This lemma is slightly mis-stated, because when $$n=2$$, $$\phi(\phi(n)) = n/2$$. But it doesn't invalidate the main result. We will state the lemma as:

Lemma For all $$n \ge 2$$, $$\phi(\phi(n)) \le \frac{n}{2}$$.

Tasse's proof sketch is a proof by induction in disguise, but this may not have been obvious to you. I'm going to simplify the proof sketch a little bit and lay it out more like a proper proof by induction.

Proof By induction on $$n$$.

Base case: If $$n=2$$, see above.

Inductive step: Suppose that for all $$2 \le m < n$$, $$\phi(\phi(m)) \le \frac{m}{2}$$. We want to prove that $$\phi(\phi(n)) \le \frac{n}{2}$$.

Case 1: Suppose $$n$$ is even, that is, $$n = 2q$$ for some $$q$$. In this case, the multiplicative property of the totient function says that $$\phi(2q) = \phi(2) \phi(q) = \phi(q)$$.

That is, $$\phi(n) = \phi(\frac{n}{2})$$. However, another useful property of the totient function is that for all $$m \ge 2$$, $$\phi(m) \le m-1$$. Therefore $$\phi(\phi(n)) \le \frac{n}{2} - 1$$.

This proves what we wanted for this case, but we have also incidentally proven another useful thing: If $$n$$ is even, then $$\phi(n) \le \frac{n}{2}$$. This will be important in the next step.

Case 2: Suppose $$n$$ is odd. That is, $$n = p^k q$$ for some odd prime $$p$$, and some positive integer $$k$$, and some $$q$$ which doesn't have $$p$$ as a divisor. Then:

$$\phi(n) = \phi(p^k) \phi(q) = \left(p^k - p^{k-1}\right) \phi(q)$$.

Now there are two things you need to notice about the right-hand side.

First off, it's less than $$n$$. Why? Because clearly $$p^k - p^{k-1} < p^k$$, and it's a standard property of the totient function that $$\phi(q) \le q$$. (Note that this is also true if $$q = 1$$.)

Secondly, it's even. Why? Because if $$p$$ is odd, $$p^k - p^{k-1}$$ is even.

So by that incidental result we discovered in case 1:

$$\phi(\phi(n)) = \phi(\left(p^k - p^{k-1}\right) \phi(q)) \le \frac{\left(p^k - p^{k-1}\right) \phi(q)}{2} < \frac{n}{2}$$.

QED

• It looks like you've clarified quite a bit the result that $\phi(\phi(N)) \le N/2$, and I will dutifully review it, but the question is actually about the equation $$T(N) = T(\phi(N))+\log(\phi(N))^3 = T(\phi(\phi(N)))+\log(\phi(\phi(N)))^3 + \log(\phi(N))^3,$$ which is what I don't have any idea why it's true. If you could explain it with the level of clarity you seem to explain the lemma, that'd be really great. Thanks! – R. Chopin Oct 1 '19 at 13:15
• Oh, sorry, I clarified the wrong part! I'll take a look tomorrow. – Pseudonym Oct 1 '19 at 13:36
• Pseudonym, $\phi(2q) = \phi(2)\phi(q)$ provided $\gcd(2,q) = 1$, but all we have in your case 1 is that $2q$ is even; we don't know $q$ is odd, so you cannot use the multiplicative property of $\phi$. What do you say? – R. Chopin Oct 2 '19 at 14:07