For a positive integer $n$, let $\mu(n) = 0$ if $n$ is not squarefree and $(-1)^k$ if $n$ is a product of $k$ primes, and let $\sigma(n)$ be the sum of the divisors of $n$. Prove that for all $n$ we have \[\left|\sum_{d|n}\frac{\mu(d)\sigma(d)}{d}\right| \geq \frac{1}{n}, \] and determine when equality holds. Wenyu Cao.
Problem
Source: ELMO Shortlist 2010, N1
Tags: inequalities, function, number theory proposed, number theory
29.07.2012 22:36
Let $g(n) = \sum_{d|n} \frac{\mu(d)\sigma(d)}{d}$. Then remark that $g(n)$ is multiplicative as $\frac{\mu(d)\sigma(d)}{d}$ ismultiplicative. Hence it suffices to show $|g(p^k)| \ge \frac{1}{p^k}$ for all prime powers $p^k$. However, $g(p^k) = g(p) = \frac{1}{1} - \frac{p+1}{p} = \frac{-1}{p}$. Thus $|g(p^k)| \ge \frac{1}{p^k}$, and hence we are done. Equality case is whenever $\mu(n) \neq 0$, i.e. $n$ is squarefree. Remark: If $n = p_1^{e_1}p_2^{e_2}...p_m^{e_m}$, then $g(n) = \prod_{i=1}^m \frac{-1}{p_i}$ assuming no stupid errors.
13.05.2020 14:54
It's easy to see that LHS is the same in both $n_1=p_1^{a_1}...p_k^{a_k}$ and $n_2=p_1...p_k$ and thus we know $\frac{1}{n_2}\ge \frac{1}{n_1}$ , we should just prove it for $n$ which is squarefree . We should just say $A_{n}=|\sum_{d|n}\frac{n\mu(d)\sigma(d)}{d}|>0$ For proof that we use induction : for $k=2$ the problem is obvious , suppose that we prove it for $k-1$ and we want to proof that for $k$ . We have $n=p_1...p_k$ where $p_1<p_2<…<p_k$ , and get $C_{k-1}=\sum_{d|m}\frac{m\mu(d)\sigma(d)}{d}$ for $m=p_1...p_{k-1}$ So we have $A_{n}=|C_{k-1}.p_k-p_1...p_{k-1}p_kC_{k-1}-p_1...p_{k-1}C_{k-1}|$ and it's easy to check that it's not zero . $\blacksquare$
13.05.2020 17:06
Let $f(n)=\sum_{d \mid n}\mu(d)\sigma(d)\frac{n}{d}$. Then $$f(n)=(-1)^{\omega(n)}\frac{n}{rad(n)}$$ Where $\omega(n)$ is the number of distinct prime factors of $n$, $rad(n)$ is the product of distinct prime factors of $n$. Then the result follows. And equality occurs for square free $n$
16.09.2021 19:00
Zhero wrote: For a positive integer $n$, let $\mu(n) = 0$ if $n$ is not squarefree and $(-1)^k$ if $n$ is a product of $k$ primes, and let $\sigma(n)$ be the sum of the divisors of $n$. Prove that for all $n$ we have \[\left|\sum_{d|n}\frac{\mu(d)\sigma(d)}{d}\right| \geq \frac{1}{n}, \]and determine when equality holds. Wenyu Cao. Define $g(n):=\sum_{d|n} \frac{\mu(d)\sigma(d)}{d}$ with $f(n):=\sum_{d|n} \mu(d)$ and $X(n):=\sum_{d|n} \frac{d\sigma({\frac{n}{d})}}{n}$($X(n)=\sum_{d_1|n} \frac{\sigma(d_1)}{d_1}$ which is multiplicative) Then $(f \cdot X)(n):=\sum_{d|n} \mu(d)X(\frac{n}{d})=\sum_{d|n} \frac{\mu(d)\sigma(d)}{d}=g(n)$ implying $g(n)$ is a convulution of two multiplicative functions hence $g(n)$ is multiplicative.Hence it suffices to show $|g(p^k)| \ge \frac{1}{p^k}$ for all prime powers $p^k$ which is trival.Equality when $n$ is squarefree.
26.03.2023 16:19
cazanova19921 wrote: Let $f(n)=\sum_{d \mid n}\mu(d)\sigma(d)\frac{n}{d}$. Then $$f(n)=(-1)^{\omega(n)}\frac{n}{rad(n)}$$ Where $\omega(n)$ is the number of distinct prime factors of $n$, $rad(n)$ is the product of distinct prime factors of $n$. Then the result follows. And equality occurs for square free $n$ Could you please expand on how you got $f(n)=(-1)^{\omega(n)}\frac{n}{rad(n)}$?