Problem 49

Let $A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}$ be such that $\phi(a_1)<\cdots<\phi(a_t)$ . The primes are such an example. Are they the largest possible? Can one show that $\lvert A\rvert<(1+o(1))\pi(N)$ or even $\lvert A\rvert=o(N)$ ?

Second statement

Let $A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}$ be such that $\phi(a_1)<\cdots<\phi(a_t)$ . The primes are such an example. Can one show that $\lvert A\rvert<(1+o(1))\pi(N)$ or even $\lvert A\rvert=o(N)$ ?

Source: erdosproblems.com/49

Number theory
Primes

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN), the site's label, which describes the corrected Statement: the site credits Tao [Ta24d], and Tao's theorem, an accepted full claim, answers both of its clauses, giving $\lvert A\rvert<(1+o(1))\pi(N)$ and hence $\lvert A\rvert=o(N)$ . The strict $o(N)$ clause is older and elementary: a strict example has distinct totient values, so its size is at most the number of totient values up to $N$ , which Erdős (1935) bounded by $N/(\log N)^{1+o(1)}$ ; Pollack, Pomerance and Treviño (2013) extended $o(x)$ to the weak maximum. The community database lists the formal status Lean, last updated 2026-08-24; that status tracks Boris Alexeev's lean-proofs file, which states the strict $o(N)$ clause and Tao's weak bound with its rate, not exact extremality. Erdős's exact conjecture, recorded under Formulation, is open.

Notes

The site's wording asks three things: whether the primes are the largest strict totient sequence in $\{1,\ldots,N\}$ , whether $\lvert A\rvert<(1+o(1))\pi(N)$ , and whether $\lvert A\rvert=o(N)$ . Erdős printed the first as an expectation, not as the question: item 9 of Part I of [Er95] (typescript p. 6, display (7)) says "Probably $t=\pi(n)$ " and then asks whether one can prove $t<(1+o(1))\pi(n)$ or at least $t=o(n)$ , adding that the last will probably be easy. The site reads the problem as the quantitative question: its label is PROVED (LEAN), and its commentary says "Solved by Tao [Ta24d]", citing the bound $\lvert A\rvert\le(1+O((\log\log x)^5/\log x))\pi(x)$ , which is the asymptotic clause; the site's forum thread had no comments when searched. The change removes the sentence "Are they the largest possible?" and inserts nothing; the two remaining clauses are the site's words (the site's "or even" presents $o(N)$ as the stronger clause where Erdős's "or at least" presents it as the weaker; the words are kept as the site prints them). The answer under the site's reading is yes: Tao's Theorem 1.1 proves the bound for the weak maximum $M_\le(N)$ , and $\pi(N)\le M_<(N)\le M_\le(N)$ gives $M_<(N)\sim\pi(N)$ and $M_<(N)=o(N)$ (the strict transfer, on the library page). The $o(N)$ clause is older and elementary: a strict sequence has distinct totient values, so its size is at most the number of totient values up to $N$ , which Erdős (1935) bounded by $N/(\log N)^{1+o(1)}$ ; Pollack, Pomerance and Treviño [PoPoTr13], Theorem 1.2, gave $o(x)$ for the weak maximum in 2013. The answer under the exact reading is unknown for the strict maximum: no source located asserts or refutes $M_<(N)=\pi(N)$ for $N\ge2$ , and at $N=1$ the exact statement fails trivially ( $\{1\}$ has one element and $\pi(1)=0$ ; this corpus's check). For the weak variant of [Er95c] the exact reading is false: [PoPoTr13]'s numerics and OEIS A365339 give $M_\le(x)\ge\pi(x)+64$ for every $x\ge31957$ . The exact question is recorded in Formulation as Erdős's conjecture, with no claim page. Results about the site's wording, credited and never counted: the site's '(LEAN)' rests on Boris Alexeev's plby/lean-proofs file Erdos49.lean (commit 1e0ec64f07933c62401e0053041e5bece2cbe325, 2026-09-04), whose erdos_49 states $M_<(N)=o(N)$ and whose erdos_49_quantitative states the weak bound with Tao's rate, neither built here. The page's standing judges the corrected Statement.

Er95: P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas 2 (1995), 165–186, Part I item 9, typescript p. 6, display (7) (card): the strict formulation with "Probably $t=\pi(n)$ ", the two quantitative clauses offered as fallbacks, and "This latest conjecture will probably be easy" for $t=o(n)$ .
Er95c: P. Erdős, Some problems in number theory, Octogon Mathematical Magazine (1995), 3–5; source reference as recorded by the site, not held.
PoPoTr13: P. Pollack, C. Pomerance, E. Treviño, Sets of monotonicity for Euler's totient function, Ramanujan J. 30(3) (2013), 379–398, DOI 10.1007/s11139-012-9386-6; the library card records the author manuscript, the Ramanujan Journal manuscript version (not held).
Ta24d: T. Tao, Monotone Nondecreasing Sequences of the Euler Totient Function, La Matematica 3(2) (2024), 793–820, DOI 10.1007/s44007-024-00115-z. The canonical source is the published 28-page version; the card also records arXiv v4.

Problem 49

Second statement

Status

Notes

Proof claims

Discussion