For questions related to Moebius inversion and its applications.

learn more… | top users | synonyms (1)

0
votes
1answer
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 ...
4
votes
0answers
115 views
+50

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) = \#\{ ...
0
votes
0answers
35 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
13 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
0answers
7 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
99 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
32 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
29 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
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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. ...
2
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
5
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
7
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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. ...
7
votes
2answers
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 ...
4
votes
1answer
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.
5
votes
1answer
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 ...
0
votes
4answers
569 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
283 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
51 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
80 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
212 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) = ...
5
votes
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 ...
2
votes
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 ...
7
votes
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 ...
2
votes
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 ...
4
votes
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 ...
2
votes
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 ...
1
vote
2answers
2k views

Are all finite groups cyclic?

I've been reading about Number Theory and I came across this proof that the finite subgroups of the multiplicative group of a field is cyclic. However, it seems the proof applies to all finite groups ...
20
votes
1answer
358 views

Combinatorial Interpretation of a Certain Product of Factorials

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 ...