Is the number of solutions of $\phi(x)=n!$ bounded? If yes, what is its bound?

Question

Pillai showed in 1929 that the function $A(n)$ giving the number solutions of the equation $\phi(x)=n$ is unbounded in (S. Pillai, On some functions connected with $\varphi(n)$, Bull. Amer. Math. Soc. 35 (1929), 832–836). I'm interested to know about bounds on solutions of $\phi(x)=n!$ which is assigned A055506 in OEIS, where it is claimed that if $\phi(x) = n!$, then $x$ must be a product of primes $p$ such that $p - 1$ divides $n!$. It is unclear to me if this allows me to prove that there are finitely many solutions of the equation $\phi(x) = n!$. Probably an equivalent question is to ask: is the number of solutions of $\phi(x)=n!$ bounded? If yes, what is its bound ?

Related question: https://math.stackexchange.com/q/3747571/156150

Answer 1

UPD. Bound simplified.

Here is a constructive bound for the number of solutions to $\phi(x)=m$.

Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $k\leq 1+\frac{\log(m)}{\log(p)}\leq 1+\frac{\log(m)}{\log(2)}$. Then the number of such $a$ is bounded by $$\prod_{d\mid m} (2+\frac{\log(m)}{\log(2)}) = (2+\frac{\log(m)}{\log(2)})^{\tau(m)}.$$

For $m>40$, we have $2+\frac{\log(m)}{\log(2)}\leq 2\log(m)$, and thus we generously bound the number of solutions by $$(2\log(m))^m.$$

Answer 2

We have $$\frac n{\varphi(n)}=\prod_{p\mid n}\bigl(1-p^{-1}\bigr)^{-1} \le2\prod_{\substack{p\mid n\\p\ge3}}\frac32 =2\prod_{\substack{p\mid n\\p\ge3}}3^{\log_3(3/2)} \le2\prod_{\substack{p\mid n\\p\ge3}}p^{\log_3(3/2)} \le2n^{\log_3(3/2)}$$ (where $p$ runs over primes), hence $$\varphi(n)\le m\implies n\le(2m)^{(1-\log_3(3/2))^{-1}}=(2m)^{\log_23}.$$ Using a larger cut-off $k$ in place of $3$, the same argument gives $$\varphi(n)\le m\implies n\le(c_km)^{\log_{k-1}k},$$ where $$c_k=\prod_{p<k}\bigl(1-p^{-1}\bigr)^{-1}.$$ Notice that $\log_{k-1}k\approx1+\frac1{k\log k}$ for large $k$.

I will not go into details, but it is easy to prove by well-known elementary arguments that $c_k=O(\log k)$, hence if we choose $k\approx\log m$, we obtain $$\varphi(n)\le m\implies n\le c\,m\log\log m$$ for some constant $c$.

Answer 3

Here is a simpler bound, based on the comment of R. van Dobben de Bruyn.

Let a solution of the equation be broken into two parts, c and d, where c is the n-smooth part of the solution, and is coprime to d, which of necessity is square free and has all prime factors bigger than n. (I leave the case n=1 to the reader.) Then c is at most n! (2/1)(3/2)(5/4)...((n+1)/n)which for n greater than three is strictly less than (n+1)n!. So c is less than (n+1)! .

Turning to d, each prime divisor of d contributes at least one power of 2 when subject to Euler's phi, so d has fewer than n prime divisors. So d is less than e times n!.

Since the shrinkage under phi of the product is at most e(n+1), the original solution must be less than 3(n+1)!. This is also a weak upper bound on the total number of solutions, but can probably be improved to show that the number and location of solutions generally is less than (n+1)!, leaving the case of small n to the reader where all creation (counterexamples, arrghh spellcheck!) must lie.

Edit 2020.07.09. GRP:

The argument above for bounding $n$ given $m=\phi(n)$ is made even simpler, as $ n/\phi(n)$ is a product of $k$ many terms of the form $p/(p-1)$ where the $p$ are distinct primes. This bounded above by $(2/1)(3/2 )(5/3)...$, which for all $k$ is less than $k+1$ and for large $k$ grows like $\log k$. Since $k$ is bounded by a function smaller than $\log m$, we can get an upper bound on $n$ that looks like $Cm\log\log m$, likely for $C$ less than 4. Even when $k$ is large, $n$ can't have many more distinct primes than powers of 2 dividing $m$.

Towards the original question, note that there are easy solutions of totient value being a factorial, and that some of them can be extended by replacing certain powers of small primes by a prime $q$ such that $q$ is bigger than the base of the factorial and such that $q-1$ equals the powers of the small primes and $q$ is not already a prime factor of the solution being modified. Thus it seems very likely that the number of solutions is not bounded as the size of the factorial grows.

End Edit 2020.07.09. GRP.

Gerhard "Leaving Hard Work To Others" Paseman, 2020.07.07.