For questions related to Moebius inversion and its applications.

learn more… | top users | synonyms (1)

1
vote
2answers
40 views

Understanding the proof of Möbius inversion formula

I am trying to understand one step in the proof of the Möbius inversion formula. The theorem is Let $f(n)$ and $g(n)$ be functions defnined for every positive integer $n$ satisfying $$f(n) = ...
1
vote
1answer
37 views

Sphere inversion radius

The following question came to me while programming some visualizations for Mobius Transformations as a pet project to learn Mathematica. Generally, the inverse of a sphere under sphere-inversion is ...
0
votes
0answers
19 views

How do I use something related to mobius inversion to solve this problem?

The problem is given below: For two sequences of complex numbers $\{a_0, a_1, \cdots, a_n, \cdots\}$ and $\{b_0, b_1, \cdots, b_n, \cdots\}$ show that the following relations are equivalent: $$a_n = ...
0
votes
2answers
41 views

How can we have a circular sequence of $0$s and $1$s of length $d$ that are not periodic?

From: A Course in Combinatorics by van Lint / Wilson $M(d)$ is the number of circular sequences of length $d$ that are not periodic. How is this possible? If $d=1$, then the sequence $1$ is ...
4
votes
1answer
91 views

Why does the Möbius function take its values so often in $\{0,+1,-1\}$?

The Möbius function of a locally finite poset $P$ is defined on its intervals $[x,y] \subseteq P$ recursively by $$\mu([x,x])=1$$ $$\forall x < y : \mu([x,y])=-\sum_{x \leq z < y} \mu([x,z])$$ ...
0
votes
0answers
20 views

Can you analyze this identity involving the sum of divisors function and $rad(n)=\prod_{p\mid n}p$?

Let $\sigma(n)$ the sum of divisors function, then by Mobius inversion formula $$\sigma(n)=n-\sum_{\substack{d\mid n,d<n}}\sigma(d)\mu\left(\frac{n}{d}\right),$$ and since this function is ...
1
vote
0answers
34 views

Can this relation between the Merten's function be simplified?

Question Can this relationship be simplified further? $ \def\lf{\left\lfloor} \def\rf{\right\rfloor} $ $$ \sum_{i=1}^n \mu(i)(\lf \frac{n}{i}\rf \ln(\lf \frac{n}{i}\rf + 1) + \frac{1}{2}\ln(\lf ...
0
votes
2answers
60 views

Number of proper divisors $d_1 < \cdots < d_j$ of $n$ such that $\gcd(d_1, \ldots, d_j) = d$

Let $n$ be a positive integer and let $D^*(n)$ be the set of proper divisors of $n$, i.e., positive divisors of $n$ excluding $n$. For every $j \geq 1$, define the function $f_j : D^*(n) \to ...
0
votes
1answer
49 views

How to compute the sum with Mobious function

Suppose $d = p_1p_2 \dots p_k$. How to compute $\sum\limits_{lm = d} g(l)\tau(m)\log{m}$, where $g(l) = \sum\limits_{d~|~l} \mu(d)\mu\left(\dfrac{l}{d}\right)$ Any ideas or hints would be greatly ...
2
votes
1answer
55 views

Sum over divisors of gcd of two numbers

How can I calculate this sum? $\sum\limits_{d~|~(n_1, n_2)} \mu(d) \tau\left(\dfrac{n_1}{d}\right) \tau\left(\dfrac{n_2}{d}\right)$, where $(n_1, n_2)$ is gcd of $n_1$ and $n_2$, $\mu$ is Mobius ...
6
votes
0answers
159 views

Are known these identities, that I've deduce using Mobius inversion formula?

I would to know if this formula is right and know (these formula are the same by exponentiation), since I deduce this easily by a standar way (perhaps there are mistakes) using Mobius inversion from ...
2
votes
1answer
70 views

Infinite sum of a function $g(n)=\sum_{d|n \; d\ne n}g(d)$

Let the function $g:\Bbb{N}\to\Bbb{N}$ be defined as $$g(n)=\sum_{d|n \; d\ne n}g(d)$$ with $g(1)=1$, how can we evaluate a sum like $$\sum_{i=0}^\infty{g(15^i)\over15^i} \tag1$$ Need we find a ...
0
votes
1answer
75 views

Show that there are infinitely many $k$-consecutive positive integers s.t. Möbius function takes the same value.

That is to say $\forall k \in \mathbb{N}$, there exist infinitely many $n\in \mathbb{N}$ s.t. $\mu \left ( n+1 \right )=\mu \left ( n+2 \right )=\cdots=\mu \left ( n+k \right )$, where $\mu$ is the ...
2
votes
0answers
38 views

Motivation for looking at the coalgebra structure of incidence algebra resp. group algebra

In basic combinatorics course we learn about the incidence algebra of a poset. Now i've read that one could start by defining the co-incidence algebra and then it is a fact that the dual vector space ...
1
vote
0answers
36 views

How to prove Crapo's Lemma

Crapo's Lemma states: Let $X$ be a subset of a lattice $L$, and let $n_k$ be the number of $k$-element subsets of $X$ with join equal to $\hat{1}$ and meet equal to $\hat{0}$. Then $$\sum_k ...
1
vote
0answers
45 views

What happens to the $\color{red}s$ in Möbius' Inversion Formula?

At the end of the Wiki page on Möbius' Inversion Formula, the following relation is given: $$ g(x) = \sum_{m=1}^\infty \frac{f(mx)}{m^\color{red}s}\quad\mbox{ for all } x\ge ...
0
votes
0answers
28 views

f is a biholomorphic function, because finite values imply a bijection

I am reading a solution of a problem and don't get the argument. It is shown that $$f:\mathbb{C}\backslash\{i\}\to\mathbb{C}\backslash\{1\}\text{ with }f(z)=\frac{z-i}{z+i}$$ is not only biholomorphic ...
4
votes
2answers
116 views

Was this arithmetic Möbius/Mangoldt function ever used for something?

Definition: Let $n=\prod_k p_k^{c_k}$, with $p_k \in \mathbb P$ and $$ A(n)=\sum_{d|n} \mu(d)\Lambda(d)=\sum_\limits{c_k\neq 0} \log p_k , $$ with the Möbius function $\mu(n)$, which is: ...
-1
votes
1answer
101 views

Pairs of integers with gcd equal to a given number

Given integers $N$ and $D$, find how many pairs of integers $(i, j)$ such that $1 \le i \le j \le N$ have the greatest common divisor exactly $D$. I know it involves Mobius inversion somehow, but I ...
4
votes
0answers
144 views

A lower bound for an arithmetic function

Let $N \in \mathbb{N}$ such that $\phi(N) \sim N$, where $\phi$ is the Euler's totient function. Let $A \subset [N] := \{1, 2, \ldots, N\}$. For $n \in \mathbb{N}$ define the function $$ C_A(n) = \#\{ ...
2
votes
2answers
61 views

Why does the inversion of the unit circle centered at $-i$ give the horizontal line $y = \frac{1}{2}$?

Inverting the circle centered at $-i$ with radius $1$, gives the horizontal line $y = \frac{1}{2}$, but why does the line have to be horizontal? Why not another straight line passing through the ...
0
votes
0answers
68 views

How to use mobius-inversion to solve this problem?

Currently, I'm trying to solve this problem using mobius-inversion. the function f(d) means the number of (i, j, k) equals d, and function g(d) means the numbers that satisfying: d | (i, j, k). Then ...
0
votes
0answers
17 views

Is the Möbius inversion applicable in the case of number functions with values in $Q(x)$

I am looking for the cause of an erroneous calculation I did the details I cant present here. I guess a "Möbius inversion" I apply might be the cause. Normally the Möbius inversion is valid for ...
0
votes
1answer
19 views

Calculating Moebius inversion of a poset with a minimum element.

If P is a poset that has a minimum element. We let x be an element of P that covers 1 single element y.Assume that y is not the minimum element, how do I prove that μ(minimum element,x) = 0? So ...
1
vote
1answer
156 views

How to compute the Mobius function

I have no clue how to begin this problem. It involves computing the Mobius inversion function $\mu$. This problem comes from Stanley's $\textit{Enumerative Combinatorics}$, vol 1, problem 70, Chapter ...
2
votes
1answer
41 views

A question about step in the proof of Selberg's formula

Recently I've found the following paper, discussing and proving Selberg's symmetry formula: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Balady.pdf My question concerns proofs of ...
2
votes
0answers
31 views

Mobius transform answer check for $0$ to $2$,$-2i$ to $0$, $i$ to $\frac32$

Continuation of this question Is this the correct answer for the mobius transformation corresponding to: $0$ to $2$ $-2i$ to $0$ $i$ to $\frac32$ $$\frac{az+b}{cz+d}\cong ...
2
votes
0answers
56 views

Value of a Moebius sum

Let $q$ be a power of a prime, let $n \in \mathbb{N}$. Is the value of the following sum known? $$ \sum_{d \mid q^n-1} \mu\left( \dfrac{q^n-1}{d} \right) q^{ord_d(q)}, $$ where $ord_d(q)$ denotes ...
1
vote
1answer
46 views

Sum on divisors is almost- ever zero

Take a positive integer $k$. Let $S \subseteq \mathbb{N}$ be the set of squarefree, and define $\displaystyle \rho_k = \mu*\omega^k$, where $ \displaystyle f* g = \sum_{d \mid n} f(d)g(n/d)$ . Show ...
1
vote
0answers
69 views

Generalized Möbius Inversion formulae

I am having as problem with inverting a relation of the form $f(i)=\sum_{j=0}^i g(i,j)h(j)$ I would like to have h in terms of f and g. I know that if my formula was of the form $f(i)=∑_j^ih(j)$ I ...
0
votes
1answer
44 views

About the inversion of hyperbel into lemniscate

I assume you know that a lemniscate $r^2 = \cos{(2\phi)}$ (polar coordinates) transforms during the inversion w.r.t. a unit circle into $r^{-2} = \cos{(2\phi)}$. I wonder what happpens with the two ...
4
votes
1answer
133 views

Interpreting the Möbius function of a poset

I have just learned about incidence algebras and Möbius inversion. I know that the Möbius function is the inverse of the zeta function, and that it appears in the important Möbius inversion formula. ...
2
votes
2answers
83 views

Finding a unique Mobius Transformation

Let $z_1, z_2, z_3$ be three distinct points in $\widetilde{\mathbb{C}}$. (1) show that there is a unique mobius transformation $g$ such that $g(z_1)=0, g(z_2)=1, g(z_3)=\infty$ (2) show ...
1
vote
0answers
85 views

Apply Möbius inversion to formal power series

Let $e$ be a positive natural number, there is the following equality of formal power series ...
0
votes
1answer
46 views

Why is this Moebius equivalence true?

I would like to know why the following is true: $$\tau(n^2) = \sum_{d | n} \mu(n/d)(\tau(d))^2$$ I cannot derive it. It is on OEIS but I'd like to know how this was found. $\tau(n)$ is the count of ...
4
votes
1answer
148 views

Prove $\sum_{k = 1}^n \mu(k)\left[ \frac nk \right] = 1$ [duplicate]

I need to prove the identity $$\sum_{k = 1}^n \mu(k)\left[ \frac{n}{k} \right] = 1$$ where $n$ is a natural number, and $[n]$ denotes the floor function. The proof also should not use the Möbius ...
5
votes
2answers
122 views

Prove $\sum_{k\mid n}{\mu(k)d(k)}=(-1)^{\omega{(n)}}$

I have the following exercise. I am supposed to show that for all natural numbers $n$, that the following equality holds $$\sum_{d|n}{\mu{(d)}d(d)}=(-1)^{\omega{(n)}}$$ Where $\mu$ is the Mobius ...
2
votes
1answer
117 views

Stupid Möbius inversion problem

I feel that this is a very stupid question to be asking, but I can't figure it out. I've been trying to figure out the Möbius inversion formula, with pretty much no experience in this direction at ...
1
vote
1answer
51 views

moebius transforms preserve sum of signed curvatures

Let $P$ be a point where three arcs of circle meet at equal angles (120 degrees). Suppose that the sum of the curvatures (with sign given by orientation) of the three arcs is zero. Is it true that ...
8
votes
1answer
162 views

Intuitive basis of Mobius inversion?

If we're given $f(n)= \sum_{d|n}g\left(\frac{n}{d}\right),n \in \mathbb{N},$ then Mobius inversion gives $$g(n)=\sum_{d|n}\mu \left( d\right) f \left( \frac{n}{d}\right).$$ Also, the generalised ...
1
vote
1answer
336 views

Number of triplets for which $\gcd(a,b,c)=1$ and $c=n$

As stated in A123323: Number of triples a,b,c with a<=b<=c<a+b, gcd(a,b,c)=1 and c=n. ...... A123323(n)=sumdiv(n, d, floor((d+1)^2/4)*moebius(n/d)) How ...
1
vote
0answers
167 views

Infinite sum of mobius function

Show that if $|q| < 1$, then $\displaystyle{\sum_{n=1}^{\infty}} \frac{\mu(n)*q^n}{1-q^n} = q$. I have a feeling that $\displaystyle{\sum_{n=0}^{\infty}}q^n = \frac{1}{1-q}$ (for $|q|<1$) is ...
2
votes
1answer
228 views

Simple Divisor Sum Transformation by Changing the Order of Double Summation

Show that $$\sum_{d|n} \frac{n}{d} \sigma(d) = \sum_{d|n} d \tau(d)$$ by changing the order of summations from each side to the other. $\sigma$ and $\tau$ are divisor sum functions. ...
9
votes
2answers
263 views

Simple Divisor Summation Inequality (with Moebius function)

Show that $$\left| \sum_{k=1}^{n} \frac {\mu(k)}{k} \right| \le 1 $$ where $\mu$ is Moebius function and n is a positive integer. The hard thing here is that the sum is not directly ...
4
votes
1answer
108 views

Continuous version of the Möbius inversion theorem

Is there a continuous version of Möbius Inversion. Essentially, using integrals instead of sums.
6
votes
1answer
416 views

Rigorously Defining Log of Polynomials?

Below is a proof that the cyclotomic polynomial $\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}$ using Möbius inversion. However, it requires that we take the log of a polynomial, which (to my knowledge) is ...
1
vote
4answers
948 views

Seeking for a proof on the relation between Euler totient and Möbius function

Can someone help me prove the relation $\varphi\left(n\right)={\displaystyle \sum_{d|n}}d\mu\left(n/d\right)$, where $\mu$ is the Möbius function defined by $$ \mu\left(n\right)=\begin{cases} 1 & ...
1
vote
1answer
324 views

Question - Möbius inversion formula

I need your help in the next question: Prove directly from the definition the Möbius inversion formula. (Möbius function defined as follows: μ(n) = 1 if n is a square-free positive integer with ...
0
votes
1answer
52 views

Looking for suggestions on how to proceed with showing that:

for $x \ge 2863:$ $$\ln\left(\left\lfloor\frac{x}{6}\right\rfloor!\right) < \sum_{k=5}^{\infty}-\mu(k)\ln\left(\left\lfloor\frac{x}{k}\right\rfloor!\right)$$ I've written a java application which ...
3
votes
1answer
102 views

Can the Möbius inversion formula be applied to the second Chebyshev function?

Is this a valid application of the Möbius Inversion Formula: Define: $$\psi\left(x\right) = \sum\limits_{p^k \le x} \log p$$ So that: $$\log x! = ...