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.

  • $\begingroup$ 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? $\endgroup$ – Michael Zieve Jul 2 '16 at 12:23
  • $\begingroup$ @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. $\endgroup$ – 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)$.

  • $\begingroup$ Wouldn't a chain of k divisors show the minimum is k (and not 2) for any number with k (possibly repeated) prime factors? Also, for your general construction for p, don't you need a 1+ in front of the product? Gerhard "Been Working With Phi Lately" Paseman, 2016.07.02. $\endgroup$ – Gerhard Paseman Jul 2 '16 at 18:59
  • $\begingroup$ Ah, I get the square free point now and the idea about 2 being minimal for a prime power. Gerhard "Not Working Enough With Mu" Paseman, 2016.07.02. $\endgroup$ – Gerhard Paseman Jul 2 '16 at 20:03
  • $\begingroup$ Right, added the +1. $\endgroup$ – Jan-Christoph Schlage-Puchta Jul 3 '16 at 7:31

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.