Problem 1064

Prove that $\phi(n)>\phi(n-\phi(n))$ for almost all $n$ , but that $\phi(n)<\phi(n-\phi(n))$ for infinitely many $n$ , where $\phi$ is Euler's totient function.

Source: erdosproblems.com/1064

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved (the site's label). The answer to both parts is yes, and the page lists the two parts as almost_all and infinitely_often. Luca and Pomerance [LuPo02] prove the first inequality on a set of density one, by a margin of any order below $n$ , refereed in Colloquium Mathematicum and credited by the site, which the corpus accepts on the claim page Luca and Pomerance 2002 as settling the first part. The second inequality was proved by Grytczuk, Luca and Wójtowicz [GLW01], with a gap growing like $2^k$ along explicit families; they also gave the first inequality a lower density of at least $0.54$ . The site credits the infinitude to that paper, and the corpus accepts it on Grytczuk, Luca and Wójtowicz 2001 as settling the second part. Luca and Pomerance state the second inequality in the stronger form $\phi(n)<c\,\phi(n-\phi(n))$ for every $c>0$ as a remark without proof, and for the infinite families they cite [GLW01].

GLW01: Grytczuk, A. and Luca, F. and Wójtowicz, M., A conjecture of Erdős concerning inequalities for the Euler totient function. Publ. Math. Debrecen (2001), 9-16.
Gu04: Guy, Richard K., Unsolved problems in number theory. Third edition, Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp.; doi:10.1007/978-0-387-26677-0. Section B42 "Behavior of $\phi(\sigma(n))$ and $\sigma(\phi(n))$ ", p. 150, opens by asking for the two inequalities of the statement. Library home: Guy 2004.
Er80f: Erdős, P., Research problems: How many pairs of products of consecutive integers have the same prime factors? Amer. Math. Monthly (1980), 391-392 (MR 1539384). The site's reference record gives this key that entry, which it shares with Problem 850 and whose subject is products of consecutive integers. The totient conjecture of this problem is Erdős's Proposed problem P. 294, Canad. Math. Bull. 23 (1980), 505, which Luca and Pomerance cite for it ([8] of [LuPo02]).
LuPo02: Luca, Florian and Pomerance, Carl, On some problems of M\polhk akowski-Schinzel and Erd\H os concerning the arithmetical functions $\phi$ and $\sigma$ . Colloq. Math. (2002), 111-130.

Problem 1064

Status

Proof claims

Discussion