Rank Amplification for Shifted Equal Values of Euler's Totient Function
Eric Li
math.NT
Jun 22, 2026 · v2
TL;DR
All results are formalised in Lean 4 with Mathlib, with no admitted proofs or custom axioms. The formalisation was developed with AI coding assistants and released on GitHub.
Abstract
Let $S_h^\varphi(x)$ denote the number of integers $n\le x$ for which $\varphi(n)=\varphi(n+h)$. For the unit shift, we prove $S_1^\varphi(x)\ll x\exp{-(1/2-o(1))\sqrt{\log x,\log_2 x}}$. More generally, put $A=\log_3 x+\log_4 x-\log 2$, $G=\sqrt{\log x,A}$, and $V=\log x/G$. For every fixed integer $J\ge 1$, uniformly for $1\le h\le \exp{G/\sqrt{J}}$, we obtain $S_h^\varphi(x)=D_{h,>Y_J}^\varphi(x)+O_J(x\exp{-\sqrt{J},G+o_J(V)})$, where $Y_J=\exp{\sqrt{J},G}$. Here $D_{h,>Y_J}^\varphi(x)$ is the above-cutoff part of the classical Graham–Holt–Pomerance same-support family; it is empty for odd $h$. A moving choice $J\asymp \log_2 x/\log_3 x$ gives the unit-shift estimate and an analogous decomposition for a uniform range of shifts. The proof combines the smooth-totient theorem of Banks–Friedlander–Pomerance–Shparlinski with labelled supplier systems, a shifted divisor convolution, and an injective encoding of large supplier products into weighted friable tuples. The results of this paper have been formally verified in Lean.
Problem
The goal is to bound the count S_h(x) of integers n ≤ x with φ(n)=φ(n+h). The aim is to improve known upper bounds for the unit shift and for a uniform range of shifts.
Approach
The proof extracts the largest prime of the common totient and uses a nonsmooth transfer theorem with divisor-weighted smooth sums. It then performs 'rank amplification' using J common large-prime occurrences. It combines the Banks–Friedlander–Pomerance–Shparlinski smooth-totient theorem with labelled supplier systems, shifted divisor convolutions, and an injective encoding into weighted friable tuples. All results are formalised in Lean 4 with Mathlib.
Results
For the unit shift, S_1(x) ≪ x exp{-(1/2-o(1))√(log x log_2 x)}. For fixed J, S_h(x) equals a Graham–Holt–Pomerance same-support term plus O_J(x exp{-√J G + o(V)}), uniformly for h ≤ exp{G/√J}. The Lean development is complete, with no sorries.