7
$\begingroup$

A set $A \subset \mathbb{N}$ is said to be syndetic if the gaps in $A$ are bounded.

Is the set $\phi(\mathbb{N})$ syndetic? (where $\phi$ denotes de Euler totient function)

I've thought quite a bit about this problem, but could not solve it and don't even have a clear idea of what the answer may be (mainly because it's hard to extract information about the values that the function $\phi$ in consecutive integers). Any help? Thanks!

$\endgroup$
7
$\begingroup$

The answer is negative. Assuming that $\phi(\mathbb{N})$ is a syndetic set we have that the totient numbers (i.e. the numbers that are of the form $\phi(n)$ for some $n$) have a positive lower asymptotic density, but Wikipedia contradicts that, giving us that the number of totient numbers up to $x$ is

$$ \frac{x}{\log x}\,\exp\left((C+o(1))\left(\log\log\log x\right)^2\right) $$ for some constant $C = 0.8178146\ldots$.


That asymptotic is very interesting, because it shows that the problem is more or less equivalent to the trivial one:

Is the set of primes a syndetic set?

In such a case the answer is negative, since by considering primorials and by exploiting the PNT we have the existence of $k$ consecutive composite numbers less than $\exp((1+o(1))k)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.