For questions related to Moebius inversion and its applications.

learn more… | top users | synonyms (1)

1
vote
0answers
31 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
58 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
41 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
42 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 ...
2
votes
0answers
45 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
0answers
28 views

Is it possible to use Möbius inversion on the last equation to get $\mathrm{core}(n)$?

From this question here: Moreover, if multiplicative function $\mathrm{core}(n)$ is defined to map positive integers "$n$" to square-free numbers by reducing the exponents in the prime power ...
0
votes
1answer
52 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 ...
1
vote
0answers
29 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
35 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
44 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
26 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
99 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
94 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
140 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
52 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
61 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
15 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
17 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
133 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
40 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
30 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
53 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
45 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
66 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
39 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 ...
3
votes
1answer
117 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
75 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
84 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
127 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
112 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 ...
1
vote
1answer
108 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 ...
7
votes
1answer
147 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
314 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
157 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
209 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. ...
8
votes
2answers
249 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
105 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
396 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
792 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
315 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
96 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! = ...
8
votes
1answer
240 views

Looking for help understanding the Möbius Inversion Formula

I was recently told that the Möbius Inversion Formula can be applied to the Chebyshev Function. Let $\vartheta(x)$,$\psi(x)$ be the first and second Chebyshev functions so that: $$\vartheta(x) = ...
7
votes
1answer
1k views

Monic Irreducible Polynomials over Finite Field

Let $F=\mathbb{F}_{q}$ be a finite field (so $q=p^k$ for some prime $p$ and positive integer $k$), and let $\varphi(d)$ denote the number of monic irreducible polynomials of degree $d$ in $F[X]$. I'm ...
2
votes
2answers
600 views

Show that $\sigma(n) = \sum_{d|n} \phi(n) d(\frac{n}{d})$

This is a homework question and I am to show that $$\sigma(n) = \sum_{d|n} \phi(n) d\left(\frac{n}{d}\right)$$ where $\sigma(n) = \sum_{d|n}d$, $d(n) = \sum_{d|n} 1 $ and $\phi$ is the Euler Phi ...
7
votes
0answers
185 views

Prime numbers, analysis of polylogarithms

Can any interesting results concering prime numbers be obtained using the analytic properties of the polylogarithm, similar to how analytic methods are used on the zeta function to obtain results ...
2
votes
1answer
400 views

Existence of an irreducible polynomial over $\mathbb F_p$. [duplicate]

Possible Duplicate: Lack of understanding of the proof of the existence of an irreducible polynomial of any degree $n \geq 2$ in $\mathbb{Z}_p[x]$ Existence of irreducible polynomials over ...