Questions tagged [mobius-inversion]

For questions related to Möbius inversion and its applications.

Filter by
Sorted by
Tagged with
1
vote
1answer
32 views

Number of Regions for a Central Hyperplane Arrangement

This question has likely been answered in full detail before, so any references would be greatly beneficial. The question I have is as follows: Suppose we have $m$ central hyperplanes in $\mathbb{R}^...
1
vote
1answer
149 views

Prove that this linear programming problem is bounded by $O(k^{1/2})$

The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems: $$\begin{array}{ll} \text{minimize} &...
1
vote
2answers
40 views

How to write $\zeta(s)^3$ as a function of the generalized Mobius function?

Popovici (1963) (see link), created a way to extend the Mobius function, $\mu(n)$, to the complex plane. The Mobius $\mu(n)$ function is such that: $\frac{1}{\zeta{(s)}}=\sum_{n=1}^{\infty}\frac{\mu(...
0
votes
1answer
20 views

Simplifying expression Mobius Function

Can anybody help me simplify this expression using Mobius Inversion Formula or any other result in order to calculate F(3500) in a simple way?? $$F(n)=\sum_{d\mid n} \mu(d)d$$
1
vote
1answer
33 views

Two sequence relations are equivalent.

For two sequences of complex numbers $\{a_0, a_1, ..., a_n, ...\}$ and $\{b_0, b_1, ..., b_n, ...\}.$ Show that the following relations are equivalent: \begin{equation} a_n = \sum_{k=0}^n b_k \iff b_n ...
1
vote
1answer
61 views

Number of words with length $n$ and symbols $\{1,2,3\}$ which are not equal to any of their cyclic shifts, with Möbius Inversion.

Let $t_{n}$ be the number of words with length $n$ and symbols $\{1,2,3\}$ which are not equal to any of their cyclic shifts. For example, the word $1232$ has cyclic shifts $2123, 3212, 2321$, none of ...
2
votes
1answer
60 views

Easy way to prove property of prime indicator

Let $\mu$ be the Möbius function, and let $\nu(n)$ be the number of distinct prime factors of $n$. Then we can define $p = \mu * \nu$, i.e. $$ p(n) = \sum_{d \mid m} \mu(d) \nu(n/d). $$ An exercise in ...
5
votes
1answer
128 views

Proof of Mobius inversion formula - the other direction

The Mobius inversion formula states that if we define $f$ as $$f(m)=\sum_{d|m}g(d)$$ then $$g(m)=\sum_{d|m}f\left(\frac md\right)\mu(d)$$ We know that the other direction is also true: if we define $...
5
votes
1answer
71 views

How to show that $\sum_{d\mid n} \gcd(d,k) \mu(n/d)=0$?

Let $k\in \Bbb{N}$ and $k>2$. Fix $k$, define $f_k(n)=\gcd(n,k)$ for $\forall\ n>1$. Let $\mu$ denote the Möbius function. Notice that $$\sum_{d\mid n}f_k(d)\mu\left(\frac{n}{d}\right)=0$$ for ...
1
vote
1answer
47 views

Mobius transformation producing a curved triangle with 3 intersecting circles

Let $ABC$ be a curved triangle on a plane, whose side $AB$, $BC$ and $CD$ are arcs of circles $S_1$, $S_2$ and $S_3$ passing though a point $D$ (i.e. $S_1∩S_2∩S_3 = D$, $D≠A$, $D≠B$, $D≠C$). Assume ...
-1
votes
2answers
42 views

$f(n) = \Sigma_{d|n} \mu(n/d)F(d)$

The question says: If $F(n) = \Sigma_{d|n} f(d)$ for every positive integer $n$, prove that $f(n) = \Sigma_{d|n} \mu(n/d)F(d)$. What I know so far is that divisors of $n$ can be paired together. ...
2
votes
1answer
103 views

Proving relationship between Euler's totient function and Mobius function

I'm trying to prove that $$\phi(n)=\sum_{d|n}\mu(d)\phi(d)$$ My attempt is the following: Mobius inversion formula tells us that, since $$n=\sum_{d|n}\phi(d)$$ then $$\phi(n)=\sum_{d|n}\mu(d)\...
1
vote
1answer
60 views

A functional ecuation using divizors

It’s a functional equation. We have a function f defined on pozitive integers (greater than 0) with values on real numbers. Also, for any pozitive (and non zero) integer n. It asks to find function f. ...
3
votes
1answer
280 views

Reasoning about factorials: is this equation correct?

I was playing around with the möbius inversion formula and factorials and I came up with an equation that I found interesting: $$\prod_{i\ge2}\left\lfloor\frac{x}{i}\right\rfloor! = \prod_{i \ge 2}\...
0
votes
0answers
29 views

Möbius inversion across all natural numbers (no divisors)

EDITED TO ACCOMMODATE COMMENTS: I'm trying (self-taught) to understand more about Möbius inversion. Take two arithmetic functions $f$ and $g$ defined by $$g(n)=\sum_{d|n}f(d)$$ (Presumably $d$ ...
0
votes
0answers
33 views

How to invert an arithmetic function where Möbius inversion may not apply?

I'm playing around with problems in order to gain a very basic insight into number theory, and I am looking at the process of inversion. Take a convergent arithmetic function of the general form $$f(...
0
votes
0answers
54 views

Reasoning with factorials and the Möbius inversion — does this make sense?

It is well known that a factorial can restated as a product of least common multiples: $$\log(x!) = \sum_{m=1}^{\infty}\psi\left(\frac{x}{m}\right)$$ Using Möbius inversion formula, it occurs to me ...
0
votes
0answers
55 views

Sum of a multiplicative arithmetic function

Prime factorization of $n$ is $\prod p_i^{e_i}$ Then radical of $n$ is defined as $\text{rad}(n)=\prod p_i$ Let $S(N) = \sum_{n=1}^{N}\text{rad}(n)$ I want to calculate $S(N)$ for very large value ...
0
votes
1answer
149 views

Identity involving the Möbius function and the first derivative of the Riemann zeta function

Working on the derivatives of the Riemann zeta function, I noted that, for any positive integer $n>1$, the following identity holds: $$\frac{\zeta'(n)}{\zeta^2(n)}=\sum_{x=1}^\infty \mu(x) \frac{\...
0
votes
0answers
24 views

usig mobius inversion to solve this problem?

let be the functional equation $$ g(x) = f(x/2)log(2) +f(x/3)log(3)+ f(x/4)log(4).... $$ where log is the logarithm in basis 'e' how could i use mobius inversion formula to obtain the function$ f(x)...
-1
votes
1answer
44 views

Using Mobius inversion to determine coefficients.

Suppose we have a fixed positive integer $n$ and three functions $f:\mathbb N \longrightarrow \mathbb N$ and $g:\mathbb N\times \mathbb N\longrightarrow \mathbb N$ and $a:\mathbb N\rightarrow \mathbb ...
0
votes
0answers
23 views

moebius and powers. how do they behave?

Suppose $f(n)=q^n$, where $q$ is an integer $>2$. (In the original formulation, $q$ should have been a prime, but I think it doesn't really matter) Define the function $$ g(n) = \sum_{d|n} \mu\...
5
votes
1answer
170 views

On the Lambert series for the Möbius function

The Lambert series for the Möbius function is given by : $$\sum_{n=1}^{\infty}\mu(n)\frac{q^{n}}{1-q^{n}}=\sum_{n=1}^{\infty}\frac{\mu(n)}{q^{-n}-1}=q \;\;\;\;\;\; |q|<1$$ This follows from Möbius ...
3
votes
1answer
153 views

How many number of bracelets of length $n$ with black-white beads?

How many number of bracelets of length $n$ with black-white beads? I'm trying to find a formula for counting the number of such bracelets. What i've done so far is to think of the bracelets as binary ...
2
votes
2answers
122 views

Prove $ \left\vert \sum_{n=1}^N \frac{\mu(n)}{n} \right\vert \leqslant 1,$ where $\mu(n)$ is the Mobius function.

Given a positive integer $N$, show that $$ \left\vert \sum_{n=1}^N \frac{\mu(n)}{n} \right\vert \leqslant 1,$$ where $\mu(n)$ is the Mobius function. How do I approach this question? I guess a ...
5
votes
1answer
263 views

Circle inversion and the Pappus chain paradox

As is well-known, lines and circles are converted into lines and circles by circle inversion, or by any Möbius transformation for that matter. What bothers me is what happens in the Pappus's classical ...
2
votes
1answer
129 views

How do I prove the following equality using Mobius inversion.

$$\sum_{i=1}^n \frac{n}{gcd(i,n)} = \sum_{d|n} d\times\phi(d) $$ Where $\phi(d)$ is the Euler totient function of d. I want to prove it using Mobius Inversion formula. Please give a formal step by ...
0
votes
0answers
126 views

What is the use of Proposition 1 (Section 6) or Rota (1964)?

In the paper "On the Foundations of Combinatorial Theory I. Theory of Miibius Functions" published in 1964, Gian Carlo Rota laid down te means for the widespread use of the Mobius inversion formula in ...
0
votes
0answers
106 views

In the definition of the Mobius function and basic properties, can we change square-free to something else?

The Mobius function isolates square-free numbers ie numbers. Can we do this with other numbers with certain properties?
3
votes
2answers
546 views

Intuition for Möbius function on a poset

I am attempting to learn about Möbius inversion in the context of partial order theory. However, I'm hitting a bit of a mental block when it comes to understanding the Möbius function, and I'm looking ...
1
vote
3answers
233 views

Regarding Multiplicative functions and the Möbius Inversion Formula

I am out to prove that if $$f(n)=\prod\limits_{d|n}g(d)$$ then $$g(n)=\prod\limits_{d|n}f(d)^{\mu{n\over{d}}}$$ I have been grappling with this for a bit too long now, and would really appreciate some ...
0
votes
0answers
137 views

Alternative second Mobius Inversion Formula.

I've seen in some places an alternative version of the Mobius Inversion Formula. Instead of the usual: $$ F(x) = \sum_{n=1}^{\infty} G(x/n) \iff G(x) = \sum_{n=1}^{\infty} \mu(n) F(x/n)$$ I've seen: $...
3
votes
1answer
54 views

Variation of Möbius inversion

I was looking at a slight variation of the Möbius inversion and tried to prove the following direction: If $$ g(n) = \sum_{\substack{d \in \mathcal{D}\\n | d}}{\mu\left(\frac{d}{n}\right) f(d)}$$ for ...
0
votes
0answers
133 views

Möbius Inversion for Infinite series

The Möbius Inversion for an infinite series(assuming absolute convergence) is given by, if \begin{equation} b(n) = \sum_{k=1}^\infty a(kn) \iff a(n) = \sum_{k=1}^\infty \mu(k)\, b(kn) \end{equation} ...
1
vote
0answers
133 views

Can this be Mobius inverted?

Let $n\in N$. Let $\mu (n)$ be the classical Mobius function. In other words, it vanishes at square-full numbers, equals $+1$ if $n$ has an even number of distinct prime factors, and equals $-1$ is $...
1
vote
0answers
42 views

Mobius inversion and number of orbit

Problem: Given a cyclic group $ C=\langle c\rangle$ of order $ n $ acting on a finite set $ X $, let $$ B\left(d\right)=\#\{x \in X:x \text{ is fixed by at least the subgroup } C_d=\langle c^{n/d}\...
0
votes
1answer
62 views

Convergence of the limit of a series involving Möbius and Floor functions

Studying and working with some problems involving the Möbius function, I (erroneously and somewhat randomly) found the following series/limit. I am curious about it, since I don't know wether it ...
1
vote
0answers
92 views

Möbius inversion exercise

I have been given the following exercise: Get a function $G(x)$ so that, being $x$ a positive integer, $$x+\sqrt{x}= \sum^x_{n=1} \mu(n) G(\frac{x}{n})$$ The result does not have to be exact, but ...
2
votes
0answers
80 views

Rate of convergence of a series

What would be the rate of convergence of: $$\sum^N_n \frac{\mu(n) \log(n)}{n}$$ ? I know that as $N \to \infty$ the series approaches to $-1$, but I am not able to get how fast it does converge ...
2
votes
1answer
87 views

How to show this equality using Mobius function?

Let $n$ be a natural number greater than $1$. Prove the following: $$\sum_{d|n} \mu(d) \sigma(d)=(-1)^rp_1...p_r$$where $p_1,...,p_r$ are the distict prime factors of $n$ and $\mu$ is the Mobius ...
2
votes
2answers
59 views

Prove $\sum_{d|n} \frac{\Phi(d)}{d} = \prod_{i=1}^r (1 + a_i - \frac{a_i}{p_i})$

I want to prove $\sum_{d|n} \frac{\Phi(d)}{d} = \prod_{i=1}^r (1 + a_i(1 - \frac{1}{p_i}))$, where $\Phi(n)$ is the Euler phi function and given the prime factorisation $n = \prod_{i=1}^r p_i^{a_i} $. ...
1
vote
1answer
414 views

Fractals and Kleinian groups - Rendering the limit set

I am talking about this: I recently read the book "The fractal geometry of nature" by Benoit B. Mandelbrot. There was one particular fractal I found very beautiful: A limit set of some group of ... ...
1
vote
0answers
152 views

Generalization of Möbius Inversion

I understand the proof of the Möbius inversion formula by moving the inner summation of $$ \sum_{d|n}\mu(n/d)\sum_{k|d}g(k) \\ $$ outside, giving: $$ \sum_{k|n}g(k)\sum_{q|n/k}\mu(n/kq) = g(n) $$ ...
3
votes
1answer
63 views

Why does $N$ divide $\sum_{d|N} p^{md} \mu\bigg(\frac{N}{d}\bigg)$?

Let $p$ be a prime and $m,N$ positive integers. Then $$ N | \sum_{d|N} p^{md} \mu\bigg(\frac{N}{d}\bigg). \tag{1} $$ For example with $p=7,m=2$ and $N=12$, we find that $7^{24}-7^{12}-7^8+7^4 \equiv ...
1
vote
1answer
460 views

Prove that $\sum_{d|n, d \geq 1}{|\mu(d)|} = 2^{\omega(n)}$

Let n ∈ Z with n > 0 and let ω(n) denote the number of distinct prime numbers dividing n. Prove that $$\sum_{d|n, d \geq 1}{|\mu(d)|} = 2^{\omega(n)}$$ I'm not sure how to approach this problem. ...
2
votes
2answers
801 views

Showing $\sum_{d\mid n} \mu(d)\tau(n/d)=1$ and $\sum_{d\mid n} \mu(d)\tau(d)=(-1)^r$ [closed]

Need some help on this question from Victor Shoup Let $\tau(n)$ be the number of positive divisors of $n$. Show that: $\sum_{d\mid n} \mu(d)\tau(n/d)=1$; $\sum_{d\mid n} \mu(d)\tau(d)=(-1)...
3
votes
2answers
109 views

If $a$ is the arithmetic function with $\sum_{d\mid n}a(d)=2^n$, then $n\mid a(n)$

Problem: Let $a:\mathbb N \rightarrow \mathbb C $ a function with the property: $$\displaystyle{\sum_{d\mid n}a(d)=2^n, \forall n \in \mathbb N}.$$ Prove that $n\mid a(n), \forall n \in \mathbb ...
5
votes
1answer
258 views

Invert: $\sum\limits_{d|n} \mu(d) \lambda(d)=2^{\omega(n)}$

Inverting $\displaystyle\sum_{d|n} \mu(d) \lambda(d)=2^{\omega(n)}$ into $\displaystyle\sum_{d|n} \lambda(n/d) 2^{\omega(d)}=1$ ,where $n \geq1$, by using Mobius Inversion Formula. I'm able to solve ...
3
votes
1answer
55 views

On the behaviour of $\sum_{\substack{n\leq x\\(n,k)=1}}\frac{1}{\sqrt[\alpha]{n}}$

For integers $a,b\geq 1$ we denote with $(a,b)$ their greatest common divisor, and the $\alpha$th root with $ \sqrt[\alpha]{x} =x^{1/\alpha}$, where $\alpha\geq 2$. Here with $\mu(n)$ we denote the ...
0
votes
1answer
39 views

Proving non-negativity of möbius inversion of set function

I have the following problem. I have given a set $$N = \{1,2,3,...,n\}, n \in \mathbb N$$ and a function $$v:2^N \rightarrow \mathbb Z, v(A) = |A|^{|A|}$$. I want to prove that the mobius inversion ...