2
$\begingroup$

I am considering the following inequality involving Euler’s totient function $\varphi$:

For every integer $x>4$, $$ x \le \varphi(x-3) + \varphi(x-2) + \varphi(x-1). $$

$x$ from $5$ to $200{,}000$ no counterexample. The only case of equality seems to be $x=5$, since $$ \varphi(2)+\varphi(3)+\varphi(4)=1+2+2=5. $$ For all $x \ge 6$, the right-hand side appears to be strictly larger than $x$. Question

  1. Has this inequality appeared in the literature (or as a known problem) before?
  2. Does anyone know a proof (or a counterexample) showing that it holds for all $x>4$?
  3. If not, is this type of inequality approachable using standard estimates for $\varphi(n)$ (e.g., $\varphi(n) \ge c n / \log\log n$) or would it require more delicate arguments related to the structure of the divisors of $x-3$, $x-2$, and $x-1$?

Any ideas, references, or comments would be greatly appreciated.

New contributor
Vô Pseudonym is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
3
  • 4
    $\begingroup$ Seems to me unlikely to be true. All you need for a counterexample is a prime number $n$ such that $n-r$ has lots of divisors for $r=1,2,3$. $\endgroup$ Commented Nov 27 at 12:29
  • $\begingroup$ Sorry, but the $\log\log$ should tell you that counterexamples will be way beyond of $200,000$! $\endgroup$ Commented Nov 27 at 13:43
  • $\begingroup$ Perhaps so, and that’s why I think this problem is quite difficult and very likely still open $\endgroup$ Commented Nov 27 at 13:50

1 Answer 1

Reset to default
2
$\begingroup$

For a counterexample, it is almost sufficient to have $\frac{\phi(x-r)}{x-r}<1/3$ for $r=1,2,3$. One has

$$\frac{\phi(x)}{x}=\prod_{p|x} \frac{p-1}{p}$$

So if enough primes divide each $x-r$ we should be cooking. However the number needed will be huge. Sets of primes which give $\phi(x)/x<1/3$ include $\{2,3,5\}$ but other sets will need a lot of primes. If we keep computing the RHS of this until it is less than $1/3^3$ we should be able to get our sets of primes. The first 3 primes brings the value to $1/3$, the first 35 primes brings it to $1/3^2$ and the first $N$ primes brings it under $1/3^3$ (my computer can't handle this, in fact you probably can't even write down $N$). Thus make $x-1$ divisible by the first 3 primes, then $x-2$ divisible by the next 32 primes, then make $x-3$ divisible by the next $N-35$ primes. You can do this with the chinese remainder theorem. This number should work, but if not make the $x-r$ divisible by a couple more and then it should work.

$\endgroup$
3
  • 2
    $\begingroup$ It's not that bad. Take $x$ odd, then we have the factor $\frac{1}{2}$ twice, and by Mertens $$\prod_{p \leqslant x} \frac{p-1}{p} \sim \frac{1}{e^{\gamma} \log x}\,,$$ so $x \approx \exp \frac{27}{2e^{\gamma}} \approx 1958$ and roughly $300$ primes should do it. $\endgroup$ Commented Nov 27 at 18:51
  • $\begingroup$ I want to ask the community if anyone can confirm whether this argument is rigorous and complete. I want to be sure before accepting this answer. Can anyone verify this proof? $\endgroup$ Commented 2 days ago
  • $\begingroup$ The community has accepted this idea, there is just debate on how to optimise to use smaller numbers. I did not do the optimal approach, as Dermot Craddock has noted. Note that even with the optimisations, your number is on the order of the product of the first 300 primes, which is a big number, hence your failure to find it by brute force. $\endgroup$ Commented 2 days ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.