Tagged Questions

For questions related to Moebius inversion and its applications.

59 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 ...
115 views
+50

47 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 ...
41 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 ...
59 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 ...
33 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 ...
65 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. ...
58 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 ...
83 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 ...
43 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 ...
103 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 ...
93 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 ...
83 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 ...
46 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 ...
117 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 ...
269 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 ...
150 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 ...
188 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. ...
211 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 ...
100 views

Continuous version of the Möbius inversion theorem

Is there a continuous version of Möbius Inversion. Essentially, using integrals instead of sums.
343 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 ...
569 views

212 views

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) = ... 1answer 962 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 ... 2answers 489 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 ... 0answers 179 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 ... 1answer 349 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 ... 2answers 1k views Sum of primitive roots is congruent to \mu(p-1) using Moebius inversion? Wikipedia has the result that Gauss proved that for a prime number p the sum of its primitive roots is congruent to \mu(p − 1) \pmod{p} in Article 81. I read it, but is there a faster proof ... 1answer 198 views Question on Euler Totient, and finding a function Determine f(n) such that for all n\geq 1,$$\frac{1}{\varphi (n)}=\sum_{d\vert n}\left(\frac{1}{d}\right)f\left(\frac{n}{d}\right) This is not a homework question, just a question I stumbled ...
Let $\mu$ denote the Moebius function. What is a combinatorial interpretation of the following integer, \begin{align} \prod_{d \mid n} d!^{\,\mu(n/d)}, \end{align} where the product is taken over ...