3
$\begingroup$

For the totient function $\phi$, we have the well known "Euler's product formula" (as named on Wikipedia) $$\phi(n) = n \prod_{p | n} \left( 1 - \frac{1}{p} \right)$$ This is easy to show knowing multiplicativity of $\phi(n)$ and the fact that $\phi(p^k) = p^{k-1}(p-1)$. However, I was applying the Sieve method to find an upper bound for the number of integers $k$ such that some separable polynomial $f(k)$ avoided some residue classes, and a quantity of the form $ \phi(n) \prod_{p | n} \left(1 - \frac{1}{\phi(p)} \right) $ showed up. I realized that the Euler product formula is just the statement that if for multiplicative functions $g(n)$ we define $$F_g(n) := g(n) \prod_{p | n} \left(1 - \frac{1}{g(p)} \right)$$ then for $g(n) = n$, we have $F_g(n) = \phi(n)$. Further, $F_g(n)$ is always multiplicative as when $(m,n) = 1$ we have $$ F_g(mn) = g(mn) \prod_{p | mn} \left( 1 - \frac{1}{g(p)} \right) = g(m) \prod_{p |m} \left( 1- \frac{1}{g(p)} \right) g(n) \prod_{p |n} \left( 1 -\frac{1}{g(p)} \right) = F_g(m)F_g(n) $$ So my question is: What multiplicative function is $F_g(n)$ when $g(n) = \phi(n)$? Is there an expression for it in terms of the well-known arithmetic functions? If not $g(n) = \phi(n)$, besides $g(n) = n$ for what other multiplicative $g(n)$ can we find $F_g(n)$ in terms of standard arithmetic functions? Another quantity that shows up while sieving for a slightly different set is, for $ a \in \mathbb{Z}^{+}$ $$ F^a_g(n) := g(n) \prod_{p | n} \left( 1 - \frac{a}{g(p)} \right) $$ In particular, $F^2_{\phi(n)}$ had shown up, but I realized I could not even find an expression for $F^a_{\text{Id}(n)}$ where $\text{Id}(n) := n$ for $a > 1$.

If it helps, even resolving the question for $n$ squarefree is of interest, but for the purposes I intend to work with it for I only need to estimate the growth of this quantity with $n$

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

A lot can be deduced from the following property: \begin{equation} \left(1-\frac{1}{x}\right)\left(1-\frac{1}{x-1}\right)\cdots \left(1-\frac{1}{x-k}\right)=1-\frac{k+1}{x} \end{equation} Now, we define \begin{align*} F^a_g(n) &:= g(n) \prod_{p | n} \left( 1 - \frac{a}{g(p)} \right) \\ F_g(n) &:= g(n) \prod_{p | n} \left(1 - \frac{1}{g(p)} \right)=F^1_g(n)\\ \end{align*} Now, when $g=\text{Id}$, in other words $g(n)=n$, the Euler's product formula tells us that $$F^1_\text{Id}(n)=\phi(n)=n \prod_{p | n} \left(1 - \frac{1}{p}\right)$$ So, when evaluating $F_{\phi}$, we have: \begin{align*} F_{\phi}(n) &= \phi(n) \prod_{p | n} \left(1 - \frac{1}{\phi(p)}\right) \\ &= n \prod_{p | n} \left(1 - \frac{1}{p}\right)\prod_{p | n} \left(1 - \frac{1}{p-1}\right) \\ &= n \prod_{p | n} \left(1 - \frac{2}{p}\right) \\ &= F_{\text{Id}}^2(n) \\ \end{align*} This leads to a recursion: \begin{align*} F_{\text{Id}}^k(n) &=n \prod_{p | n} \left(1 - \frac{k}{p}\right) \\ &= n \prod_{p | n}\left(1 - \frac{k-1}{p}\right)\left(1 - \frac{1}{p-k+1}\right) \\ &= F_{\text{Id}}^{k-1}(n)\prod_{p | n}\left(1 - \frac{1}{p-(k-1)}\right) \\ &= F_{\text{Id}}^{k-1}(n)\prod_{p | n}\left(1 - \frac{1}{F_{\text{Id}}^{k-1}(p)}\right) \\ &= F_{F_{\text{Id}}^{k-1}}(n) \end{align*} But we can apply this recursion with every starting function, for example you asked for $F_{\phi}^2(n)$: \begin{align*} F_{\phi}^2(n) &=\phi(n)\prod_{p | n}\left(1 - \frac{2}{\phi(p)}\right) \\ &=\phi(n)\prod_{p | n}\left(1 - \frac{1}{\phi(p)}\right)\left(1 - \frac{1}{\phi(p)-1}\right) \\ &=F_{\phi}(n)\prod_{p | n}\left(1 - \frac{1}{\phi(p)-1}\right) \\ &=F_{\phi}(n)\prod_{p | n}\left(1 - \frac{1}{p-2}\right) \\ &=F_{\phi}(n)\prod_{p | n}\left(1 - \frac{1}{F_{\phi}(p)}\right) \\ &=F_{F_{\phi}}(n) \\ \end{align*}

I recognise that all of this is not computationally helpful, but I think it partially answers the question, providing links between the functions defined in the OP.

To answer your second question "for what other multiplicative $g(n)$ can we find $F_g(n)$ in terms of standard arithmetic functions", if $g(n)=\mu(n)$, the Möbius function, then \begin{align*} F_{\mu}^a(n) &= \mu(n)\prod_{p | n}\left(1 - \frac{a}{\mu(p)}\right) \\ &= \mu(n)\prod_{p | n}(1+a) \\ &= \mu(n)\cdot (1+a)^{\omega(n)} \end{align*} where $\omega(n)$ is the prime omega function.

Similarly, when $g(n)=\sigma_0(n)$ is the number of divisor function, we have $$F_{\sigma_0}^a(n)=\sigma_0(n)\prod_{p | n}\left(1-\frac{a}{2}\right)=\sigma_0(n)\left(1-\frac{a}{2}\right)^{\omega(n)} $$

$\endgroup$

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.