Is the excess $M(x)-\pi(x)$ of the longest $\varphi$-nondecreasing sequence over the primes bounded?

Let $M(x)$ denote the largest cardinality of a subset of $\{n\le x\}$ on which Euler's totient function $\varphi$ is nondecreasing. The primes form such a subset, so $M(x)\ge\pi(x)$, and Tao (2024) proved $M(x)=(1+O(\log_2^5 x/\log x))\pi(x)$, resolving Erdős's 1995 question whether $M(x)\sim\pi(x)$. The sharpened bounded-excess conjecture of Pollack–Pomerance–Treviño (2013) — $M(x)\le\pi(x)+O(1)$, with numerics suggesting $M(x)=\pi(x)+64$ for all $x\ge31957$ — remains open. The source paper identifies two structural obstructions: an unconditional proof of bounded excess would imply Legendre's conjecture for all sufficiently large primes, and improving the error term beyond $O(1/\log x)$ would require quantitative Dickson–Hardy–Littlewood prime-tuples control. The problem asks for an unconditional proof or disproof of $M(x)\le\pi(x)+O(1)$ (with the exact constant as the sharpened target); source-recognized intermediate targets include reducing the exponent $5$ in the error term and establishing conditional or short-interval analogues under quantitative prime-distribution hypotheses.

Background

Let $\varphi(n)$ denote Euler's totient function, which counts the integers between $1$ and $n$ that are coprime to $n$, and let $\pi(x)$ denote the number of primes $p\le x$. For a finite set $A$ of natural numbers, write $M(A)$ for the largest cardinality of a subset of $A$ on which $\varphi$ is nondecreasing (weakly increasing), and let $M(x)$ denote this quantity for the initial segment $[x]=\{n\in\mathbb{N}:n\le x\}$. For instance $M(6)=5$, since $\varphi$ is nondecreasing on $\{1,2,3,4,5\}$ or $\{1,2,3,4,6\}$ but not on all of $\{1,\dots,6\}$ (the sequence of values is recorded as OEIS A365339). Because $\varphi(p)=p-1$ increases with the primes, the primes themselves form such a subset, so $M(x)\ge\pi(x)$.

Erdős asked in 1995 (recorded as problem #49 in the online Erdős problems database) whether $M(x)$ is in fact asymptotic to $\pi(x)$. Pollack, Pomerance, and Treviño (2013) initiated the quantitative study of these sets of monotonicity: they proved $M(x)\le(1-c+o(1))W(x)$ for an absolute constant $c>0$, where $W(x)$ counts the distinct values taken by $\varphi$ on $[x]$, which combined with known estimates for $W(x)$ yields an upper bound exceeding $\pi(x)$ by a factor $\exp((C+o(1))(\log_3 x)^2)$ (here $\log_3 x=\log\log\log x$), leaving a wide gap around the primes; they also showed every such subset has size $o(x)$. Based on extensive numerics they posed the much sharper question

$M(x)\le\pi(x)+O(1),$

conjecturing the precise formula $M(x)=\pi(x)+64$ for all $x\ge31957$ (verified for $x=10^m$, $m\le7$).

Tao (2024) closed the asymptotic gap by proving

$M(x)=\left(1+O\left(\frac{\log_2^5 x}{\log x}\right)\right)\pi(x)\quad(x\ge10),$

where $\log_2 x=\log\log x$. The proof is elementary apart from the prime number theorem with classical error term, and rests on the sharp inequality $\sum_{d:\varphi(d)/d=q}1/d\le1$ for positive rational $q$ (Proposition 1.4 of the source), which attains equality only at $q=1$ and $q=1/2$; the equality case $q=1/2$ (attained when $d$ ranges over the powers of $2$) is the technical bottleneck of the method, since it produces an almost viable counterexample to the bounded-excess conjecture built from numbers of the form $2^k p$ with $p$ prime. The same paper obtains the analogous asymptotic for the sum-of-divisors function $\sigma(n)=\sum_{d\mid n}d$.

The bounded-excess question itself is explicitly left open in the source, which records two structural obstructions. First, Legendre-type prime gaps: Legendre's conjecture asserts that for every $n\ge2$ there is a prime between $(n-1)^2$ and $n^2$; it is open even for all sufficiently large $n$ and even under the Riemann hypothesis (the conjecture that all nontrivial zeros of the Riemann zeta function have real part $1/2$). Proposition 4.1 of the source shows that if Legendre's conjecture fails for infinitely many primes $p$, then the squares $p^2$ can be inserted into the sequence of primes without breaking $\varphi$-monotonicity, forcing $M(x)-\pi(x)\to\infty$; stated contrapositively, a proof of $M(x)\le\pi(x)+O(1)$ would imply Legendre's conjecture for all sufficiently large primes. Second, prime-tuple correlations: the Dickson–Hardy–Littlewood prime-tuples conjecture predicts, for coprime integers $a,b$ with $a>0$, that the number of primes $p\le x$ with $ap+b$ also prime is $(\mathfrak{S}_{a,b}+o(1))x/\log^2 x$ for an explicit positive singular series $\mathfrak{S}_{a,b}$; it implies the twin prime conjecture and is far beyond current sieve methods. Proposition 4.5 of the source shows that a severe breakdown of such correlations (specifically, if for all $k$ with $2^k\le2\log x$ there are only $O(x/(\log^2 x\log_2^3 x))$ primes $p\le x$ with $\lceil p/2^k\rceil$ also prime) would force $M(x)-\pi(x)\gg x/\log^2 x$; consequently, improving the error term in the main theorem to better than $O(1/\log x)$ — a fortiori proving boundedness — would require substantial quantitative progress on prime tuples. Within this landscape, the unresolved target is the exact size of the excess $M(x)-\pi(x)$.

Problem Statement

Prove or disprove, unconditionally, that the excess of the maximal $\varphi$-nondecreasing subset of $[x]=\{n\in\mathbb{N}:n\le x\}$ over the primes is bounded:

$M(x)-\pi(x)=O(1)\quad(x\to\infty),$

that is, $M(x)\le\pi(x)+O(1)$; and, in the strongest form, decide the numerical conjecture of Pollack–Pomerance–Treviño that $M(x)=\pi(x)+64$ for all $x\ge31957$. The optimal constant in $M(x)-\pi(x)=O(1)$ need not be identified, and a disproof requires an infinite construction rather than a single finite example. Explicitly recognized intermediate targets toward the same objective, recorded in the source's discussion of open problems: (i) unconditionally reducing the exponent $5$ in the error term $M(x)=(1+O(\log_2^5 x/\log x))\pi(x)$; (ii) proving conditional bounds such as $M(x)=\pi(x)+O(x^\theta)$ for some $0<\theta<1$, or the short-interval analogue $M([x+x^\theta]\setminus[x])\le(1+o(1))(\pi(x+x^\theta)-\pi(x))$, under precisely stated hypotheses such as Cramér's conjecture on prime gaps ($p_{n+1}-p_n\ll\log^2 p_n$) or a quantitative form of the Dickson–Hardy–Littlewood prime-tuples conjecture; and (iii) controlling the exceptional multiplicative configurations arising from the equality case $q=1/2$ of the inequality $\sum_{d:\varphi(d)/d=q}1/d\le1$. These intermediate results constitute partial progress on the common objective — quantifying the excess of $M(x)$ over $\pi(x)$ — and do not by themselves close the stated question.

References

1. Terence Tao, Monotone Nondecreasing Sequences of the Euler Totient Function, La Matematica 3 (2024), no. 2, 793–820, DOI 10.1007/s44007-024-00115-z, https://doi.org/10.1007/s44007-024-00115-z (preprint arXiv:2309.02325, https://arxiv.org/abs/2309.02325)
2. Paul Pollack, Carl Pomerance, Enrique Treviño, Sets of monotonicity for Euler's totient function, The Ramanujan Journal 30 (2013), no. 3, 379–398, DOI 10.1007/s11139-012-9386-6, https://doi.org/10.1007/s11139-012-9386-6 (origin of the bounded-excess conjecture)
3. Stijn Cambie, On Erdős problem #648, arXiv:2503.22691 [math.NT] (2025), https://arxiv.org/abs/2503.22691 (longest sequences with decreasing largest prime factor)
4. Noah Lebowitz-Lockard, Joseph Vandehey, Arithmetic functions that remain constant on runs of consecutive integers, Journal of Integer Sequences 26 (2023), Article 23.8.4, https://cs.uwaterloo.ca/journals/JIS/VOL26/Lebowitz/lebo10.html (constant-run analogues)
5. Noah Lebowitz-Lockard, J.C. Saunders, Runs of integers with constant values of the Carmichael function, arXiv:2402.06832 [math.NT] (2024), https://arxiv.org/abs/2402.06832 (constant runs of the Carmichael function)
6. OEIS Foundation (ed.), The On-Line Encyclopedia of Integer Sequences, sequence A365339: length of the longest subsequence of 1,...,n on which the Euler totient function is nondecreasing, https://oeis.org/A365339 (numerical status of $M(x)$ and of the $\pi(x)+64$ conjecture)
7. T. F. Bloom (ed.), Erdős Problems, Problem #49, https://www.erdosproblems.com/49 (page edited 19 April 2026, accessed 2026-09-06; status of Erdős's asymptotic question about $M(x)$)