Inequality with Mobius function and sum of divisors

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Inequality with Mobius function and sum of divisors

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: ELMO Shortlist 2010, N1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2043 posts

Zhero

#1 h Jul 5, 2012, 1:55 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#2 h Jul 29, 2012, 7:36 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

65 posts

Arefe

#3 h May 13, 2020, 11:54 AM

Y by

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$

This post has been edited 1 time. Last edited by Arefe, May 13, 2020, 11:58 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

542 posts

#4 h May 13, 2020, 2:06 PM

Y by

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$

This post has been edited 2 times. Last edited by cazanova19921, May 13, 2020, 2:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#5 h Sep 16, 2021, 4:00 PM

Y by

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.

This post has been edited 4 times. Last edited by Sprites, Sep 16, 2021, 6:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

wasikgcrushedbi

52 posts

wasikgcrushedbi

#6 h Mar 26, 2023, 1:19 PM

Y by

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)}$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

26 posts

#7 h Thursday at 5:01 PM

Y by

Easy problem!

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a