Problem 415

For any $n$ let $F(n)$ be the largest $k$ such that any of the $k!$ possible ordering patterns appears in some sequence of $\phi(m+1),\ldots,\phi(m+k)$ with $m+k\leq n$ . Is it true that

F(n)=(c+o(1))\log\log\log n

for some constant $c$ ? Is the first pattern which fails to appear always

\phi(m+1)>\phi(m+2)>\cdots >\phi(m+k)?

Is it true that the 'natural' ordering which mimics what happens to $\phi(1),\ldots,\phi(k)$ is the most likely to appear?

Source: erdosproblems.com/415

Number theory

Wiki page

Status

ClaimedDisproved

A full solution has been claimed but not yet accepted. The statement is false.

The site labels the problem OPEN (page last edited 28 May 2026). Its commentary records that the asymptotic of Pollack, Pomerance and Treviño [PPT13] for monotone runs answers the first question in the negative, the accepted partial claim on the Pollack–Pomerance–Treviño page, and that Chojecki and GPT-5.4 sketched the same asymptotic for an arbitrary strict pattern. Chojecki's manuscripts of April and July 2026, the July one answering all three questions no, are the pending full claim on the Chojecki page; the frontmatter standing follows from it.

Er36b: Erdős, P., On a problem of Chowla and some related problems. Proc. Cambridge Philos. Soc. (1936), 530-540.
ErGr80: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
PPT13: Pollack, Paul and Pomerance, Carl and Treviño, Enrique, Sets of monotonicity for Euler's totient function. Ramanujan J. (2013), 379-398.

Problem 415

Status

Proof claims

Discussion