Skip to content

Erdős Problem #49

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, primes.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

List the elements of a set \(A\) in increasing order,

\[ a_1<a_2<\cdots<a_t, \]

and suppose that their Euler totient values also strictly increase,

\[ \phi(a_1)<\phi(a_2)<\cdots<\phi(a_t). \]

Erdős Problem #49 asks whether this forces \(A\subseteq[1,N]\) to contain asymptotically no more elements than the primes up to \(N\). The answer is yes, established by Terence Tao.

A small example

If \(p\) is prime, then \(\phi(p)=p-1\). Thus as the primes increase, their totient values increase. For \(N\ge5\), the set \(\{2,3,5\}\) has totient values \(\{1,2,4\}\), an immediate example. The primes provide a lower construction of size \(\pi(N)\).

What is known

Tao, Monotone Nondecreasing Sequences of the Euler Totient Function, La Matematica 3 (2024), 793–820, proved a stronger result: even if the totient values are merely nondecreasing, the largest possible sequence has cardinality

\[ M(N)=\left(1+O\left(\frac{(\log\log N)^5}{\log N}\right)\right)\pi(N) \]

for sufficiently large \(N\). A strictly increasing totient sequence is automatically nondecreasing. Therefore Tao's theorem applies to Erdős's narrower problem, and the prime example matches its main term.

The related nondecreasing-variant question and analogous sums-of-divisors results should retain their own theorem boundaries.

GCL's current state

Source audit #1318 checks the strict-versus-nonstrict implication and published 2024 source. No admitted frozen GCL formal-provider statement for this numbered problem was identified, and the full analytic argument was not independently formalized by GCL.

What remains

The asymptotic comparison is solved in the literature. Future work can formalize the strict-to-nondecreasing reduction and numerical checks or independently replay Tao's source proof without asserting a new bound.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1318 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction