# Minimal number of different values in the sequence $(\mu(d_i)\varphi(d_i))_{i=\overline{{1,\tau(m)}}}$

Let $m=p_1\ldots p_k$ be the prime factorization of some positive integer $m$ and $k\geq 2$.

Let $d_1,\ldots,d_{\tau(m)}$ be all divisors of $m$, where $\tau(m)$ counts the number of divisors of $m$.

For a given $k$, I am trying to find the minimal number of different values in the sequence $(\mu(d_i)\varphi(d_i))_{i=\overline{{1,\tau(m)}}}$, where $\varphi$ and $\mu$ are Euler's totient and Mobius functions, respectively.

It seems very likely to me that the value is equal to $2 ({{k-2}\choose {3}}+{{k}\choose {2}}+1)$. Moreover, is it possible to find $p_1,\ldots,p_k$ such that the number of different values of the sequence is equal to some given $l$, where $l$ takes the values between lower and uper bound?

Thank you in advance for any suggestion.

• What is the reasoning behind your very specific guess of what the answer should be? Also, is there some larger context in which this question arose? – Michael Zieve Jul 2 '16 at 12:23
• @Michael Put p1=2 and find p2, ..., pk from the system of equation p(i+1)-1=(p2-1)(pi-1), for 3<= i <= k-1. Than, after a heavy calculation I counted the number of diferent values $\mu(d_i)\varphi(d_i)$. Тhere may be a faster way to obtain the same result since the formula is not so comlicated. There is no some special wider context. – Robert Jul 2 '16 at 13:44

I assume that $m$ is squarefree, for otherwise the minimum would be equal to 2 no matter what $k$ is.
Let $p_1, \ldots, p_k$ be the set of all prime numbers of the form $2^a3^b+1$, where $a, b<t$. Then for all divisors $d$ of $n=p_1\cdots p_k$ we have $\varphi(d)$ that is of the form $2^a 3^b$,$a, b<t^2$. As far as I know the best known upper bound for the number of primes of the given form is $\mathcal{O}(\frac{t^2}{\log t})$. Of course, we would expect much fewer primes, but if this upper bound was in fact the true order of magnitude, then minimal values of the size $k^2\log k$ would be possible.
For this construction to work we need a unrefutable, but highly unbelievable assumption. A similar construction together with the standard probabilistic heuristics leads one to expect that the minimum is at most $k^{2+\epsilon}$: Fix $\ell$, and take all primes $p$, such that $p=1+\prod_{i=1}^\ell p_i^{e_i}$, where $e_i<t$, and $p_1, \ldots, p_\ell$ are the first $\ell$ primes. Since the probability that an integer $n$ s prime is $\frac{1}{\log n}$, we expect that there are $\gg t^{\ell-1}$ such primes, while there are $<t^{2\ell}$ values for $\varphi(d)$.