Erdős Problem #408

Erdős Problem 408: an additive formula for totient height

Statement and outcome

We reconstruct the exact additive structure of the height, prove two-sided logarithmic bounds, and exhibit different limiting ratios on two sparse subsequences. These do not settle the distribution or normal-order questions. Source: https://www.erdosproblems.com/408. The additive structure is classical Shapiro theory; a primary modern treatment is Bal--Bhatnagar, Theorem 1, https://arxiv.org/abs/1903.09619. No novelty is claimed.

Constructing the additive function without circularity

For $n>2$, $\varphi(n)$ is even, since reduced residue classes pair as $u,n-u$. Induction on $n$, using $\varphi(n)<n$ for $n>1$ and checking $n=2$ separately, now gives \[ f(n)=\begin{cases} h(n),&n\text{ even},\\ h(n)+1,&n>1\text{ odd}. \end{cases} \tag{2} \] Thus the prime-factor formula for the height is fully proved, rather than assuming additivity of $\varphi$ or of its iterates. In particular for $a,b>1$, \[ f(ab)=\begin{cases} f(a)+f(b),&a,b\text{ both even},\\ f(a)+f(b)-1,&\text{otherwise}. \end{cases} \tag{3} \] The exclusion of $1$ in $3$ is necessary with the convention $f(1)=0$.

Bounds and exactly computed extremal families

For an even integer $m$, $\varphi(m)\le m/2$. After the first step from any $n>2$, all subsequent iterates greater than one are even. Hence before reaching one, $\varphi_j(n)\le(n-1)/2^{j-1}$ for $j\ge1$. Taking $j=\lceil\log_2 n\rceil$ forces the iterate below $2$, unless it already reached $1$. Thus \[ f(n)\le\lceil\log_2 n\rceil. \tag{5} \] The rounding and the initial parity step matter: $\varphi(m)\le m/2$ is false for odd primes.

As $w(3)=h(2)=1$, the exact formulas include \[ f(2^r)=r,\qquad f(3^r)=r+1,\qquad f(2\cdot3^r)=r+1. \] Therefore the ratios tend respectively to $1/\log2$ and $1/\log3$ on the first and third families. There is no ordinary limit over all integers. These families have density zero, so they do not contradict a constant normal order or a limiting distribution.

A modest prime-factor observation and the remaining gap

The older local draft's valid elementary upper bound is retained, now joined by the full additive reconstruction and its consequences. Understanding the weighted prime-factor sum $h(n)$ for a density-one set of integers, and controlling large prime factors along typical totient chains, remain unresolved in this attempt. No conjectural distribution theorem is used as an unconditional result. Completion rate estimate: 45%.

1) FORMAL RESTATEMENT

Let $\varphi$ be Euler's totient function. Define iterates \[ \varphi_1(n)=\varphi(n),\qquad \varphi_{k}(n)=\varphi(\varphi_{k-1}(n))\ (k\ge 2). \]

Define \[ f(n):=\min\{k\ge 0:\ \varphi_k(n)=1\}, \] with the convention $\varphi_0(n)=n$ (so $f(1)=0$).

Questions. (A) Does $f(n)/\log n$ have a distribution function? (B) Is $f(n)/\log n$ almost always constant? (C) For $k=\log\log n$, what can be said about the largest prime factor of $\varphi_k(n)$?

2) QUICK LITERATURE/CONTEXT CHECK

I only restate what is recorded in the problem statement.

The statement records: - Pillai proved $\log_3 n < f(n) < \log_2 n$ for all large $n$. - Shapiro proved $f(n)$ is essentially multiplicative. - Erdős--Granville--Pomerance--Spiro proved (conditional on Elliott--Halberstam type input) the answers to (A) and (B) are yes.

3) ATTACK PLAN

Proof-track (partial): - Prove an elementary upper bound on $f(n)$ using $\varphi(n)\le n/2$ for $n>2$. - Compute small values for sanity.

Disproof-track: - Try to find irregular behaviour of $f(n)/\log n$ in small ranges (purely computational evidence).

Chosen path: prove explicit elementary bounds and compute $f(n)$ for $n\le 50$.

4) WORK

PHASE 1 — FAST REALITY CHECK (computed)

Computed values of $f(n)$ for $1\le n\le 50$ (where $f(n)$ counts the number of totient-iterations to reach $1$) start as \[ ( f(1),\dots,f(10))=(0,1,2,2,3,2,3,3,3,3), \] and the maximum in $n\le 50$ is $6$ (attained at $n=41,47$ in this range).

Lemma 1 (elementary upper bound $f(n)\le \lceil\log_2 n\rceil$). For every integer $n\ge 2$, \[ f(n)\le \lceil\log_2 n\rceil. \]

Proof. We treat $n=2$ separately: $\varphi(2)=1$, so $f(2)=1=\lceil\log_2 2\rceil$.

Now assume $n\ge 3$. Set $x_0=n$ and $x_j:=\varphi_j(n)$ for $j\ge 1$. Then $x_1=\varphi(n)\le n-1$. Also, $x_1$ is even: indeed, for $n>2$ the reduced residue classes modulo $n$ come in pairs $\{a,n-a\}$, so their count $\varphi(n)$ is even.

Claim. For every even integer $m\ge 2$ one has $\varphi(m)\le m/2$.

Proof of the claim. If $m$ is even, then any integer coprime to $m$ must be odd. There are exactly $m/2$ odd integers in $\{1,2,\dots,m\}$, so $\varphi(m)\le m/2$. $\square$

We now bound the iterates. Since $x_1$ is even, either $x_1=2$ (in which case $x_2=\varphi(2)=1$) or $x_1\ge 4$. In all cases, as long as $x_j\ge 2$ we have $x_j$ even and hence by the claim \[ x_{j+1}=\varphi(x_j)\le \frac{x_j}{2}. \] By induction this yields, for every $k\ge 1$, \[ x_k\le \frac{n-1}{2^{k-1}}. \] Now take $k:=\lceil\log_2 n\rceil$. Then $2^{k-1}\ge n/2$, so \[ x_k\le \frac{n-1}{2^{k-1}} < \frac{n}{2^{k-1}}\le 2. \] Since $x_k$ is a positive integer, this forces $x_k=1$. Therefore $f(n)\le k=\lceil\log_2 n\rceil$. $\square$

Remark. The above proof is deliberately elementary and yields a correct $O(\log n)$ bound, though it does not reproduce the sharper constant bounds recorded in the statement.

Lemma 2 (exact value on powers of $2$). For every integer $m\ge 1$, \[ f(2^m)=m. \]

Proof. For $m\ge 1$, $\varphi(2^m)=2^{m-1}$. Iterating gives \[ \varphi_1(2^m)=2^{m-1},\ \varphi_2(2^m)=2^{m-2},\ \dots,\ \varphi_{m-1}(2^m)=2,\ \varphi_m(2^m)=1. \] Thus the smallest $k$ with $\varphi_k(2^m)=1$ is $k=m$, i.e. $f(2^m)=m$. $\square$

5) VERIFICATION

- The formula $f(2^m)=m$ matches computed values: $f(2)=1$, $f(4)=2$, $f(8)=3$, $f(16)=4$, $f(32)=5$. - The upper bound from Lemma 1 is consistent with computed values for $n\le 50$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here. - Exact formula $f(2^m)=m$ (Lemma 2). - Elementary logarithmic upper bound $f(n)\ll \log n$ (Lemma 1). - Computed values of $f(n)$ for $n\le 50$.

(ii) Exact first gap. Establish unconditionally the existence of a limiting distribution for $f(n)/\log n$ or determine whether it is almost surely constant (both of which are only recorded conditionally in the statement).

(iii) Top 3 next moves (concrete targets). 1. Prove sharper deterministic upper and lower bounds for $f(n)$ in terms of the prime factorisation of $n$ (e.g. via multiplicativity of $\varphi$ and typical sizes of $\varphi(n)$). 2. Run large-scale computations of $f(n)$ for $n$ up to, say, $10^7$ to estimate the empirical distribution of $f(n)/\log n$. 3. Investigate the behaviour of the largest prime factor of $\varphi_k(n)$ for slowly growing $k$ via explicit bounds on prime factors of totients.

(iv) What a minimal counterexample would likely look like. If $f(n)/\log n$ failed to have a distribution function, one would expect a positive-density subset of integers where $f(n)$ is systematically atypical (either unusually large for integers with many small prime factors, or unusually small for integers with special structure), causing persistent oscillations in the empirical distribution.