Erdős Problem #415
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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
Let \(\phi(n)\) be Euler's totient: the number of integers from \(1\) through \(n\) that are coprime to \(n\). Erdős Problem 415 studies the order in which consecutive values \(\phi(m+1),\ldots,\phi(m+k)\) can appear. For a strict interpretation, all values in the block must be different, and its order is one of the \(k!\) permutations of \(1,\ldots,k\). Define \(F_{\mathrm{str}}(x)\) to be the largest \(k\) for which every such permutation occurs in at least one block ending at or before \(x\).
The maintained problem page asks three related questions. Is \(F(x)\) asymptotic to a constant times \(\log\log\log x\)? Is the decreasing pattern the first one to disappear? Is the pattern suggested by \(\phi(1),\ldots,\phi(k)\) the most likely? There is an essential ambiguity: “ordering pattern” might mean strict inequalities, or a weak order in which equal values are allowed. The first interpretation is a permutation question. The third cannot be purely a permutation question, since \(\phi(1)=\phi(2)=1\) and \(\phi(3)=\phi(4)=2\).
The source record therefore contains two problems joined together: a strict-order threshold and an equality-sensitive weak-order problem. They should not be silently treated as the same statement.
A small example
Here is an exact finite check using only integer arithmetic. Compute \(\phi(t)\) from its definition \(\phi(t)=\#\{a:1\leq a\leq t,\ \gcd(a,t)=1\}\), enumerate every starting point \(m\) with \(m+3\leq x\), discard blocks with ties, and record the rank pattern. The first cutoff found for which all six strict patterns of length three occur is \(x=315\):
| pattern of ranks | \(m\) | \((\phi(m+1),\phi(m+2),\phi(m+3))\) |
|---|---|---|
| \((1,2,3)\) | 104 | \((48,52,106)\) |
| \((1,3,2)\) | 5 | \((2,6,4)\) |
| \((2,1,3)\) | 4 | \((4,2,6)\) |
| \((2,3,1)\) | 15 | \((8,16,6)\) |
| \((3,1,2)\) | 12 | \((12,6,8)\) |
| \((3,2,1)\) | 312 | \((312,156,144)\) |
For example, \(\phi(313)=312\), \(\phi(314)=156\), and \(\phi(315)=144\), so the last row is genuinely decreasing. This is a reproducible certificate for a finite, length-three assertion; it does not prove an asymptotic formula, prove that the next missing pattern is decreasing at every cutoff, or say anything about weak orders with ties.
What is known
The relevant primary source is Pollack, Pomerance, and Treviño, “Sets of monotonicity for Euler’s totient function,” Ramanujan Journal 30 (2013), 379–398. Their Theorem 1.5, on page 3 of the author PDF, states that the largest consecutive block in \([1,x]\) on which \(\phi\) is nonincreasing has size \(\frac{\log_3 x}{\log_6 x}+(\alpha-\gamma+o(1))\frac{\log_3 x}{(\log_6 x)^2}\), and the same holds for nondecreasing blocks. Here \(\log_j\) denotes the j-fold iterated natural logarithm, \(\gamma\) is Euler's constant, and \(\alpha\) is defined by \(\exp(\alpha)=\prod_p(1-1/p)^{-1/p}\).
The paper's remark after the proof, on page 12, says its lower-bound construction also works for strictly decreasing and strictly increasing blocks. Thus, for the strict interpretation, the longest increasing and decreasing blocks have this same asymptotic scale. Since every universal collection of strict permutations must include both monotone permutations, \(F_{\mathrm{str}}(x)\) is at most that quantity. In particular it cannot be asymptotic to a positive constant times \(\log_3 x\); the extra divisor \(\log_6 x\) matters.
That primary theorem does not establish that every strict permutation occurs up to the same threshold. A linked 2026 circulation sketch claims such a result by reindexing the paper's construction, and claims that every fixed strict permutation occurs infinitely often. This is an external, unreviewed report rather than a GCL-certified theorem; its status is recorded as a claim requiring source and semantic review. It also deliberately leaves the equality-allowing variant separate. The maintained page reports these facts and was last edited 28 May 2026, but a maintained webpage is not a substitute for checking the proof.
GCL's current state
At the frozen catalogue revision teorth/erdosproblems@536408716724a2402bdfa7c1d764bf83d64a8c89, the entry for number: '415' has Git blob 4e60263a80af6207aca494d2e1388e44fa372889, informal status open, status date 2025-08-31, formal-solution status unformalized, and statement-formalized metadata no. It has number-theory tags and no prize metadata. Those fields are catalogue evidence, not a replacement for the mathematical statement.
The Programme triage record classifies 415 as STATEMENT_CAPTURE_REQUIRED: no protected FormalConjectures statement is present. I found no exact pinned 415 Lean file or protected blob to read, so there is no Lean theorem, sorry body, replay result, or semantic comparison to report. The live page's newer discussion is therefore source drift from the frozen packet, not a formal admission. V2 ledger state, when applicable, decides accepted coverage; this article makes no acceptance or certification claim.
What remains
A bounded successor task is to audit the strict-order circulation sketch against the primary paper. Input should be the exact linked PDF (all nine pages), the frozen catalogue entry, and Pollack–Pomerance–Treviño pages 3 and 11–12. The target is one normalized statement for \(F_{\mathrm{str}}\), \(D_{\mathrm{str}}\), and \(I_{\mathrm{str}}\), followed by a page-and-equation map showing whether each claimed upper and lower bound is actually inherited from the primary proof. Acceptance is a complete map with every new permutation-symmetry step either proved from the cited estimates or explicitly marked an unresolved lemma. Falsification is a counterexample to a claimed inequality, a missing uniformity hypothesis, or a strict/weak-order mismatch. Stop after the nine-page source audit and one finite certificate; do not launch a Lean build or a broad literature search. The equality-allowing problem should remain a separate successor task because it reaches the adjacent open question of infinitely many \(n\) with \(\phi(n)=\phi(n+1)\).
Sources and claim boundaries
- Original assignment: MATH-PROGRAMME issue #1685. The original SOURCE RESULT/1 citation is authenticated original RESULT/1.
- Frozen catalogue: commit 536408716724a2402bdfa7c1d764bf83d64a8c89, the
415entry, blob4e60263a80af6207aca494d2e1388e44fa372889. - Maintained Erdős Problems #415, including its 28 May 2026 edit and stated strict/non-strict ambiguity.
- Primary paper: Pollack–Pomerance–Treviño PDF, SHA-256
146a124e660273b701fc83b75322972401cde731e0e1bba9e584a8e1d267bc38; DOI 10.1007/s11139-012-9386-6. - External report, not independently certified: linked 2026 sketch, SHA-256
4f243c673861f7712ea5e19cb48b6cdbaff78f186aaa7bd7fdab2c6a62d38694.
The primary paper supports the monotone-block bound and its strict lower-bound remark. The finite table is an independently rerun exact calculation. The sketch's all-permutations claim, any formalization, and any GCL mathematical certification remain outside this article's claims.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1685 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- 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.