Logic Problems: Improve Deductive Skills with Basic Totient Function

[Nono713]

For those of you more into logical thinking, here are a few related problems I made up. They are not difficult by any means and are mostly meant to improve deductive skills, logic and proofwriting. Please be comfortable with the basic properties of the totient function as we'll use it as a framework for this problem set.

Consider the mapping $\mathbb{F}_n : \mathbb{N} \to 2^\mathbb{N}$ defined as:

$$a \in \mathbb{F}_n ~ \Leftrightarrow ~ \varphi{(a)} = n ~ ~ ~ ~ \left ( \text{for all} ~ a > 1 \right )$$

Where $\varphi(a)$ is the Euler totient of $a$, and $n \in \mathbb{N}$. In other words, $\mathbb{F}_n$ is the "inverse totient" of $n$. As an example:

$$\mathbb{F}_{10} = \{ 11, 22 \} ~ ~ \text{and} ~ ~ \mathbb{F}_{32} = \{ 51, 64, 68, 80, 96, 102, 120 \}$$

Consider the tree graph produced by iterating this mapping on its outputs recursively, starting at $n = 1$. See here (limited to 50, green squares are odd primes, yellow squares may or may not have children on the full tree).

Problems, in rough order of difficulty - solutions will be posted on Tuesday 2PM UTC+12 (NZST):

1. Show that $\mathbb{F}_n$ is empty when $n > 1$ is an odd integer. Show that the converse is true.

2. Prove that $\mathbb{F}_n$ always has an even number of elements when $n + 1$ is prime.

3. Show that $a \in \mathbb{F}_{n_1}$ and $a \in \mathbb{F}_{n_2}$ implies $n_1 = n_2$ (the converse is trivially true).

4. Prove that if $n = 2^m$, then $\mathbb{F}_n = m + 2$, with the exception of $m = 0$ where $\mathbb{F}_n = 1$.

5. Show that the tree has the heap property (i.e integers always get larger as you go down the tree).

6. Prove that any integer in the tree appears only once.

7. Show that this tree is infinite, that is, it has infinitely many elements.

8. Decide whether or not this tree contains all positive integers, and prove so.

9. We place an upper bound $m$ on elements of $\mathbb{F}_n$ (like the example tree did with $m = 50$). Give the tightest bound you can obtain for the maximum number of levels the resulting tree will have.

10. On what level of the tree is the integer $a$, on average? The root is at level zero.

11. How many elements will the tree have at level $l$, on average?

* For the three last problems, make reasonable assumptions on the distribution of elements in the tree.

Hints (click to show if you are out of ideas):

Spoiler

Are you sure? You can't forget hints.

Spoiler

1. Think of the multiplicative properties of $\varphi$, and the fundamental theorem of arithmetic.

2. Try and divide $\mathbb{F}_{37 - 1}$ into pairs, and find a pattern.

3. Remember $\mathbb{F}_n$ is not a function, but $\varphi$ is. What does this entail?

4. If $\varphi{(a)} = 2^m$, what form can $a$ possibly have? Check $a = 2^r (2^p + 1)$ with $2^p + 1$ prime.

5. Go back to the definition of $\varphi$.

6. What do (3) and (5) tell you?

7. Traverse the tree backwards by iterating $\varphi$ instead.

8. Using the same iteration approach as in (7), show the sequence will converge to 1 for any integer.

9. Use the method hinted at for (7). Study the rate at which the iterated value decreases.

10. Use your results for (9) to consider the average case.

11. This is a trick question, you can't just assume the tree is finite. First, apply the same reasoning as in (9) by rigorously bounding the size of the tree, then take the limit at infinity.

 

[Nono713]

Please ignore problem 2 - I had a mistake in my original proof and it does not hold (e.g. n = 660).

 

[Nono713]

The following solutions are somewhat generic and are mostly along the lines of "see, this is true, and you can show it this way", and are not particularly rigorous. A good exercise in proofwriting would be to rewrite them properly by defining and then proving important lemmas and theorems (especially since all ten problems are related).

1. Consider any integer $a$, with prime factorization:

$$a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$

The totient function's multiplicative properties apply here, we have:

$$\varphi{(a)} = \varphi{( p_1^{\alpha_1} )} \varphi{( p_2^{\alpha_2} )} \cdots \varphi{( p_k^{\alpha_k} )}$$

Recall that $\varphi{(p^\alpha)} = p^{\alpha - 1} (p - 1)$, so:

$$\varphi{(a)} = p_1^{\alpha_1 - 1} (p_1 - 1) p_2^{\alpha_2 - 1} (p_2 - 1) \cdots p_k^{\alpha_k - 1} (p_k - 1)$$

Assume $a > 2$, then at least one prime must be odd, thus one of $(p_1 - 1), (p_2 - 1) \cdots (p_k - 1)$ must be even. It follows that $\varphi{(a)}$ is even. Finally, for $a \leqslant 2$, we easily compute $\varphi{(a)} = 1$, and this is the only exception.

We conclude that $\varphi{(a)} = n$ has no solutions in $a$ when $n > 1$ is odd. Thus $\mathbb{F}_n$ is empty.

As for the converse, it can be easily shown. Assume $\mathbb{F}_n$ is not empty, and let $n$ be odd. But writing down any element of $\mathbb{F}_n$ as shown above shows that $n$ is, in fact, even. Therefore, $\mathbb{F}_n$ must be empty.

3. This one is easy enough.

$$a \in \mathbb{F}_{n_1} ~ ~ \implies ~ ~ \varphi{(a)} = n_1$$
$$a \in \mathbb{F}_{n_2} ~ ~ \implies ~ ~ \varphi{(a)} = n_2$$
$$\therefore n_1 = n_2$$

4. Let $n = 2^m$. We are solving $\varphi{(a)} = 2^m$. Consider $a = 2^r (2^{p_1} + 1) (2^{p_2} + 1) \cdots (2^{p_k} + 1)$ with $2^{p_i} + 1$ prime. No other form of $a$ can have a power of two totient (the proof is quite easy and left as an exercise to the reader).

$$\varphi{(2^r)} \varphi{ (2^{p_1} + 1)} \varphi{ (2^{p_2} + 1) } \cdots \varphi{ (2^{p_k} + 1)} = 2^{r - 1} 2^{p_1} 2^{p_2} \cdots 2^{p_k} = 2^{r + p_1 + p_2 + \cdots + p_k - 1}$$

We require $r + p_1 + p_2 + \cdots + p_k = m + 1$. We note primes of the form $2^p + 1$ are rare, in fact there are only five known to date (Fermat primes) and we have the following possible values: $p_i = \{ 1, 2, 4, 8, 16 \}$.

How many possible arrangements do we have that add up to $m + 1$? Since $r$ can be anything, we could just find all arrangements of those five values which sum up to at most $m + 1$, and complete by selecting $r$ as needed.

However, It turns out that because $p_i$ are successive powers of two, a nice property of binary numbers apply, and we're better off just varying $r$ from $0$ to $m + 1$ and adding up the number of possible arrangements of $p_i$. And in fact, for any $r$, there is only one such arrangement, since all distinct binary numbers are unique.

So the number of possible arrangements is:

$$\sum_{0}^{m + 1} 1 = m + 2$$

And our proof is complete... almost. We're limited to $m < 31$, since $p_i$ is finite, so the theorem does not quite hold for all $n = 2^m$. However, this draws an interesting parallel between Fermat primes and our problem here - if every number of the form $2^{2^p} + 1$ was prime, the theorem would always hold. In addition, if the number of Fermat primes were finite, it would immediately imply that:

$$\lim_{m \to \infty} |\mathbb{F}_{2^m}| = k!$$

Where $k$ is the number of Fermat primes known, which is an interesting upper bound, perhaps worth studying.

5. This is rather trivially shown, by noting that $\varphi{(n)} < n$ for all $n > 1$ (by definition).

6. Pick an arbitrary integer $a_1$ in the tree, and assume it appears twice at different locations.

Now compute $a_2 = \varphi{(a_1)}$. This, by definition, moves us one level up the tree, in both locations, so the parent of the two locations of $a_1$ must be the same.

Now compute $a_3 = \varphi{(a_2)}$, which means the grandparent of $a$ must also be the same, for both locations of $a_1$.

Repeat until we're reached the root of the tree. So we've apparently got two identical branches of the tree, all the way from the root to the two locations of $a_1$. But recall problem (3), and it should be clear that those two locations must in fact be the same. Therefore, any integer in the tree can only appear once.

7. Let $n = 2^1$. Then $\varphi{(2^1)} = 1$, so $2^1$ is in the tree.

Now let $n = 2^2$, then $\varphi{(2^2)} = 2^1$, which is in the tree, so $2^2$ is in the tree.

Repeat ad infinitum.

$\therefore$ the tree contains all powers of two, and is therefore infinite.

This is kind of a lazy man's proof, but the next problem is more general so I'm avoiding repetition.

8. Take an arbitrary positive integer $n$. Consider the sequence:

$$a_0 = n ~ ~ ~ \text{and} ~ ~ ~ a_{n + 1} = \varphi{(a_n)}$$

From our proof to problem (5), it's easy to see that this sequence is strictly decreasing:

$$\lim_{i \to \infty} a_i = \varphi{(1)} = 1$$

Which proves that $n$ is in the tree. Therefore all positive integers $n$ are in the tree, only once, due to problem (6).

9. Recall the tree will contain all integers less than and including $m$ (this doesn't immediately follow from (8) but the proof can be trivially adapted). Consider the sequence:

$$0 < a_0 \leqslant m ~ ~ ~ \text{and} ~ ~ ~ a_{n + 1} = \varphi{(a_n)}$$

We already know this sequence is strictly decreasing, for any $a_0$, from (5). But at what rate? The maximum value for $\varphi{(a_n)}$ occurs when $a_n$ is prime, clearly, so at the very least the sequence will decrease by 1. However, we can (and must) do better - if $a_n$ is prime, then $a_{n + 1} = a_n - 1$ and will clearly no longer be prime, except for the unique case $a_n = 3$. Consider the case of $a_n$ semiprime, with $p \approx q \approx \sqrt{a_n}$:

$$a_n = pq ~ ~ \implies ~ ~ \varphi{(a_n)} = (p - 1)(q - 1) = a_n - (p + q - 1) \approx a_n - 2 \sqrt{a_n}$$

What about $a_n$ when it has three prime factors, with $p \approx q \approx r \approx \sqrt[3]{a_n}$?

$$a_n = pqr ~ ~ \implies ~ ~ \varphi{(a_n)} = (p - 1)(q - 1)(r - 1) \approx a_n - 3 \left (\sqrt[3]{a_n}^2 - \sqrt[3]{a_n} \right )$$

Clearly, as you add more and more factors, the rate at which the sequence decreases will increase. The limiting case is (of course) the case $a_n = 2^m$, where the sequence is quite simply halved, and this is a minimum.

The probability that a randomly selected $p$ less than or equal to $m$ is prime, is asymptotically $\frac{1}{\ln{(m)}}$.

So if we select a random $a_0$, it is either prime, in which case the sequence decreases by 1, or it is composite, in which case the sequence decreases by at least $2 \sqrt{a_0}$. We'll assume $m$ is large enough such that the fraction of primes less than $m$ is insignificant - an analysis using the logarithmic distribution primes may be done, but is more difficult:

Thus we can calculate an asymptotic upper bound on the time it takes for the sequence to converge to 1, which gives us the maximum number of levels for a tree truncated at $m$ elements:

$$a_n - a_{n + 1} = 2 \sqrt{a_n} ~ ~ \implies ~ ~ a_{n + 1} = a_n - 2 \sqrt{a_n}$$

After how many iterations will the sequence reach 1? Sum up the differences:

$$\Delta = 2 \sqrt{m} + 2 \sqrt{m - 2 \sqrt{m} } + \cdots$$

Which yields the following:

$$\left ( \frac{4 \Delta - 2 \sqrt{m}}{2} \right )^2 = m - 4 \Delta$$

And we obtain:

$$\Delta = \sqrt{m} - 1$$

Thus, a tree truncated at $m$ will have an asymptotic maximal height (number of levels) of:

$$\lfloor \sqrt{m} \rfloor$$

This is a rather poor bound for small $m$, since most small integers are prime (though it works quite well on our $m = 50$ example tree, since its height is 7 and $\sqrt{50} \approx 7.07$). An analysis taking this into account would probably use the Prime Number Theorem.

Of course, the minimal height is much easier to derive, under the same assumptions. Since the sequence decreases by at most one half by iteration, the minimal height is trivially:

$$\log_2{(m)}$$

There is a better bound using the fact that if $p$ is prime, then $p - 1$ cannot be, but it is left to the reader.

10. We can just reuse our work in problem (9), and with some modifications we show that an integer $a$ has a maximal level (in the tree) of:

$$\lfloor \sqrt{a} + 1 \rfloor$$

The $+1$ is there because we start counting at zero (the previous problem was concerned with the number of levels).

And hence the average level will be:

$$\left \lfloor \sqrt{\frac{a}{2}} + 1 \right \rfloor = \left \lfloor \frac{\sqrt{a}}{4} + 1 \right \rfloor$$

To prove this, consider an integer $a' = \frac{a}{2}$ and see why you can't just take half the maximal level (the sequence is nonlinear).

11. Assume the tree is truncated to elements less than or equal to $m$. Then, we know there are $m$ integers in the tree. Amusingly, this problem isn't too difficult because any tree grows exponentially by definition, so we know the answer is at least proportional to $2^l$. Since our maximal number of levels is:

$$\lfloor \sqrt{m} - 1 \rfloor$$

Then we have:

$$c_l \propto 2^l ~ ~ \implies ~ ~ c_l = \alpha 2^l$$

Where $c_l$ is the minimal number of elements at level $l$. And the constant factor can be found by simply making sure everything adds up to $m$:

$$\alpha = m \left ( \sum_{l = 0}^{\lfloor \sqrt{m} - 1 \rfloor} 2^l \right )^{-1}$$

And the average number of elements can then be found by (note the square root):

$$c_l = \frac{1}{\sqrt{2}} \alpha 2^l$$

Interestingly, this also gives a heuristic argument on $| \mathbb{F}_n |$ as $n \to \infty$, in that the number of solutions to $\varphi{(a)} = n$ tends to grow exponentially with $n$, at least on average.