Questions tagged [mobius-inversion]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
44 views

Dirichlet Series of a given sequence

I am trying to calculate the dirichlet generating function of $(p(n)q( \log(n)))_{n \geq 1}$ where $p,q$ are arbitary polynoms. First I calculated the dirichlet genarating function of $(p(n))_{n \geq ...
user avatar
  • 639
2 votes
0 answers
36 views

Using Mobius Inversion Formula

We are given the following: $f(n)=\prod_{d|n}g(d)$ and asked to show: $g(n)=\prod_{d|n} f(d)^{\mu(\frac{n}{d})}$ The hint given says to use logarithms Here's what I tried doing: $log(f(n))=\prod_{d|n}...
user avatar
  • 131
1 vote
0 answers
37 views

Summatory function of Euler-phi

Let $F(n) = \sum_{d^2|n} \phi(d)$. We must show that if $F(1) = 1$, and if $n>1$ factors as $n=p^{a_1}_1p^{a_2}_2...p^{a_m}_m$, then $$ F(n)=\prod_{i=1}^{m} p^{[a_i/2]}_i. $$ If I understood ...
user avatar
6 votes
1 answer
62 views

Möbius inversion for categories instead of directed graphs

In Tom Leinster, The Euler Characteristic Of A Category, the author generalizes the notion of Möbius Inversion for posets to finite categories. This violates the principle of equivalence. A possible ...
user avatar
1 vote
0 answers
30 views

Mobius Inversion Theorem that is used in Chromatic Polynomial

I have made a shortcut on proving the Mobius Inversion Theorem, which states the following: Let $N_{e}(x)$ to be a real-valued function, defined for all $x$ in a locally finite partially ordered set $(...
user avatar
0 votes
1 answer
77 views

Finding Recurrence

Let be $C_k$, $k^{th}$ Catalam's number and $$f(n)=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}C_k\text{.}$$ I want to prove the following recurrence: $$f(n+1)+(-1)^{n}=f(0)f(n)+f(1)f(n-1)+\cdots+f(n)f(0)\text.{...
user avatar
  • 89
1 vote
0 answers
25 views

Incidence algebra zeta and mobius matrix?

Trying to follow the notes for understanding how to compute the zeta and mobius matrices from a graph. The graph is Zeta matrix entries defined by $\zeta(a,b)=\left\{\begin{matrix} 0 & if \quad a ...
user avatar
3 votes
0 answers
85 views

A question about the derivatives of the Möbius inversion formula for $\zeta(s)$

The following expression for the $\frac{1}{\zeta(s)}$ involving the Möbius function is well known: $$\frac{1}{\zeta(s)}=\sum _{n=1}^{\infty }\frac {\mu(n)}{n^s} \qquad s \in \mathbb{C},\Re(s) > 1$$ ...
user avatar
  • 2,539
1 vote
0 answers
35 views

Variant of Möbius inversion: $b(n) = \sum_{d^2 \mid n} a(n/d^2) d^\alpha$

I'm trying to understand a step in a classic paper of Rankin. In Rankin's paper Contributions to the theory of Ramanujan's function $\tau(n)$ and similar arithmetical functions, he defines $$ b(n) := \...
user avatar
  • 11
0 votes
0 answers
53 views

If n is even, prove that the summation (indexed over the divisors of n) ϕ(d)µ(d) = 0 [duplicate]

I am having great difficulty with the following proof: Prove that if $n$ is even, $\sum_{d|n} μ(d)ϕ(d) = 0$ First, I noticed a general pattern that we will use later: For any integer $a$, we see that ...
user avatar
0 votes
0 answers
27 views

Can lines intersect twice?

In inversion,we extend the euclidean plane by adding a single point at infinity which lies on all the lines.But doesn't that mean lines can intersect twice?I mean non parallel lines already intersect ...
user avatar
  • 461
2 votes
1 answer
55 views

Understanding a detail in the inclusion-exclusion Möbius Inversion proof in Introductory Combinatorics

In Introductory Combinatorics, by Brualdi, we have an explication on the Möbius Inversion. There's a line that I'm having a hard time believing, and would appreciate some explanation: Let $n$ be a ...
user avatar
1 vote
1 answer
62 views

Sums of Möbius between $x$ and $y$

For $z_1 > z_2 \geq 0$ define $$M(z_1,z_2) = \sum_{z_2 < a \leq z_1 } \mu(a),$$ where $\mu$ is the Möbius' function. Prove that $$\sum_{k=1}^{\infty} M\left(\frac{n}{k}, 0\right) = 1\,\text{ and ...
user avatar
  • 2,547
0 votes
0 answers
53 views

What happens if you compose the zeta function with two circle inversion mappings in this specific way?

Let $I^a_b : \mathbb{C} \to \mathbb{C}$ be defined as circle inversion mapping of a circle at the point $a \in \mathbb{C}$ of radius $b = \frac{1}{r}$ What happens to the zero's of the zeta function ...
user avatar
  • 4,194
2 votes
0 answers
61 views

Generalised Möbius inversion formula.

Lets recall the Möbius inversion formula: If we have two arithmetic functions $f,F$, such: $$F(n)=\sum_{d|n}f(d)$$ then we have: $$f(n)=\sum_{d|n}F(d)\mu(\frac{n}{d})$$ Suppose now that we have ...
user avatar
  • 1,320
0 votes
0 answers
59 views

Sum of inverse of a multiplicative function

I stumbled upon the following problem, while trying to come up with a recreational math question. Let $n$ be a positive integer with factorization $n=2^a\prod_{i=1}^{k}p_i^{e_i}$ Define the arithmetic ...
user avatar
2 votes
0 answers
78 views

Mobius Function of Young's Lattice

The Wikipedia page of Young's Lattice (https://en.wikipedia.org/wiki/Young%27s_lattice) states that for $p\leq q$ the Mobius function is $\mu(p,q)=\left\{ \begin{array}{ll} (-1)^{|p|-|q|} & \...
user avatar
  • 185
0 votes
1 answer
170 views

Dirichlet convolution of the small prime omega function and the Mobius function

I have seen that: $$(\omega\star\mu)(n)=\sum_{d\vert n}\mu(d)\omega\left(\frac{n}{d}\right)=\begin{cases}1 & n\ \text{is prime}\\ 0 &\text{otherwise} \end{cases}$$ where $\mu(n)=\delta_{\omega(...
user avatar
1 vote
1 answer
60 views

Possibly Möbius Inversion Formula Application

EDIT: I believe I've figured it out! Feel free to take a look in case I've made a mistake. Problem: Let $n$ and $d$ be positive integers and $m, b \in R$, some ring. If $F(n) = \sum_{d|n}f(d)$ and $\...
user avatar
  • 323
2 votes
2 answers
119 views

What does $\sum \mu(d)\lfloor{\frac{x}{d}}\rfloor$ count?

Where the sum is over all $d$, where $d$ only has prime factors $\leq \sqrt{x}$. I'm trying to determine, in plain English, precisely what this sum is counting. I know the Möbius function will be 0 if ...
user avatar
1 vote
0 answers
30 views

Relation between $f$ and $g$ satisfying $\sum_{r}^N f(x^r) = g(x)$ without mobius inversion?

Let's say for a particular function I have $f$: $$ f(x) + f(x^2)+ f(x^3)+ \dots +f(x^N) = g(x) $$ We start by considering the integral: $$ I_f = \int_0^{b} f (e^{-\frac{1}{x}}) dx $$ Using asymptotics ...
user avatar
2 votes
2 answers
251 views

Prove inversion formula involving binomial coefficients

Let's say that we have such an equation: $$f_k = \sum_{i=0}^{k}{k \choose i}g_i$$ Prove that in that case we can express $g_k$ like this: $$g_k = \sum_{i=0}^{k}(-1)^{k-i}{k \choose i}f_i$$ In order to ...
user avatar
3 votes
1 answer
89 views

Is $ \ln \delta \int_0^1 \frac{f(z)}{z(\ln z)^2} dz \sim \sum_{r=1}^\infty \mu(r) f(\delta^{1/r}) $?

Background I think I can show something interesting: $$ \ln \delta \int_0^1 \frac{f(z)}{z(\ln z)^2} dz \sim \sum_{r=1}^\infty \mu(r) f(\delta^{1/r}) $$ where $\delta \to 0$ and $\int_0^1 \frac{f(z)}{...
user avatar
0 votes
2 answers
205 views

Understanding the method of using inversion to solve a problem on touching circles

Need to prove: (1) The points of contact of the chain of circles $ (C_o, C_1, C_2..C_n)$ has the locus of a semi-circle (2) if radius of $C_n$ is $ r_n$, then height above L of the center of $ r_n$ is ...
user avatar
3 votes
2 answers
109 views

Intuition behind inversions of triangles in circles leading to similar triangles

In here the inversion of triangle $qab$ produces triangle $q \tilde{a} \tilde{b}$ but I find it a bit weird that $\angle qab = \angle q \tilde{b} \tilde{a}$ and $\angle q ab = \angle q \tilde{a} \...
user avatar
0 votes
2 answers
97 views

Proof that line passing through centre of circle is mapped to a line under inversion transformation

'Here b is an arbitary point on L, while a is the intersection of perpendicular line with q. By virtue of (5), $ <q\tilde{b}\tilde{a}=<qab= \frac{\pi}{2}$, $\tilde{b}$ lies on same line-segment $...
user avatar
0 votes
2 answers
87 views

How can I prove this functional equation?

Question:- If $$F(x)=f(x)+\frac12f(x^2)+\frac13f(x^3)+\frac14f(x^4)+\ldots\,,$$ then prove that $$f(x)=F(x)-\frac12F(x^2)-\frac13F(x^3)-\frac15F(x^5)+\frac16F(x^6)-\frac17F(x^7)+\frac1{10}F(x^{10})-\...
user avatar
  • 1,384
1 vote
2 answers
85 views

Finding $f$ with Möbius inversion formula

How to find an arithmetic function $f$, when the summatory function $F$ of $f$ is given by $F(n)=\begin{cases} 1 & \mathrm{if}\ n \mathrm{\ is \ a \ square \ number} \\ 0 & \mathrm{...
user avatar
  • 521
4 votes
0 answers
267 views

Mobius inversion on the partition lattice

For some $n \in \mathbb N$, let $(\Pi_n, \le)$ be the poset of partitions of the set $\{1, 2, \dots, n\}$, where two partitions $\pi, \rho \in \Pi_n$ have the relation $\pi \le \rho$ if $\pi$ is a ...
user avatar
  • 71
4 votes
0 answers
61 views

Correspondence between $k$-ary Lyndon words and $(k-1)$-ary Lyndon words without repetitions

At Counting Lyndon words with no adjacent character repeats, it turned out that for $n\ge3$ the number of $k$-ary Lyndon words of length $n$ without adjacent identical letters is the number of $(k-1)$-...
user avatar
  • 216k
1 vote
1 answer
78 views

Proof of an identity concerning the prime $\zeta$ function

I have to prove the following identity: let $P(s)=\sum_p\frac{1}{p^s}$, for $Re(s)>1$, then \begin{equation} P(s)=\sum_{n=1}^{\infty}\frac{\mu(n)}{n}\log(\zeta(ns)). \end{equation} I proved that \...
user avatar
2 votes
1 answer
91 views

Prove that the lower bound for the partial sums of the Möbius inverse of the Harmonic numbers minus $n$ is greater than $1$ minus a Harmonic number

Let $\varphi^{-1}(n)$ be the Dirichlet inverse of the Euler totient function: $$\varphi^{-1}(n) = \sum\limits_{d\mid n} d \cdot \mu(d) \tag{1}$$ and let the matrix $T$ be: $$T(n,k)=\varphi^{-1}(\...
user avatar
  • 6,770
1 vote
2 answers
427 views

Prove that H is orthocentre of ABC using inversion

Three equal circles pass through a given point $H$ and meet one another two by two at $A,B,C$ prove that $H$ is orthocentre of triangle $ABC$. My try - I proved it using elementary geometry methods ...
user avatar
1 vote
1 answer
62 views

Value of Möbius series involving $\log(n+1)$

Let $\mu$ be the Möbius function. It is known that $$\sum_{n \geq 1} \frac{\mu(n)}{n} \log n = -1$$ I'm looking for a closed-form expression of the similar series $$\sum_{n \geq 1} \frac{\mu(n)}{n} ...
user avatar
  • 5,070
1 vote
0 answers
47 views

Question on proof of relationships between $f(s)=\frac{s}{s+1}$ and the analytic Harmonic number function $H(s)$

This question assumes the following definitions where $s\in\mathbb{C}$. (1) $\quad f(s)=\frac{s}{s+1}$ (2) $\quad H(s)=\psi(s+1)+\gamma\qquad\text{(analytic harmonic number function)}$ Question: ...
user avatar
  • 4,553
2 votes
1 answer
79 views

Question on the coefficient of the Dirichlet series related to $\frac{\zeta(s+2)}{\zeta(s)}$

This question is about the evaluation of $a(n)$ defined in (1) below which is related to the Riemann zeta function $\zeta(s)$ as illustrated in (2) below. (1) $\quad a(n)=\sum\limits_{d|n}\frac{\mu\...
user avatar
  • 4,553
0 votes
1 answer
88 views

Dirichlet Self-Convolution Inversion

I am interested in finding out a method to invert Dirichlet selfconvolution. In math expressions it means: Find out $a$ once $b=a*a$ is known So a kind of squareroot of the Dirichlet product. I ...
user avatar
2 votes
2 answers
169 views

Möbius function and Posets

As usual, $\mathbb{C}$ denote the field of complex numbers. Let $\mu \in I_{\mathbb{C}}(P)$ (the $\mathbb{C}$ incidence-algebra of $P(X, \leq)$ a poset). I am asked to show the following are ...
user avatar
0 votes
1 answer
40 views

$\Phi_{2^n}(x) = x^{2^{n-1}}+1$ by Mobius Inversion

I want to prove that $\Phi_{2^n}(x) = x^{2^{n-1}}+1$. This is not hard to do by using recursion. However, I want to know if there's a simpler way to do this using the Mobius Inversion formula, which ...
user avatar
  • 1,174
1 vote
1 answer
220 views

Squarefree integers and floor function, Möbius function

On page 40, exercise 44 of Introduction to Analytic and Probabilistic Number Theory by Tenenbaum: Show that any integer $n\ge1$ can be uniquely decomposed as $n = qm^2$ , where $q$ is squarefree. ...
user avatar
  • 909
1 vote
0 answers
83 views

Number of subsets of size $k$ with a given GCD

Given a set $S = \left\{1, 2, \ldots,N \right\}$ of positive integers, we want to count the number of subsets of size $k$ with the GCD of all elements (henceforth referred to as the GCD of the set) ...
user avatar
  • 4,004
3 votes
1 answer
148 views

Need help with Möbius function

Suppose I need to find total subset of numbers of length $K$ in range $1$ to $N$ such that their $\gcd$ is $g$. How can I utilize Möbius function for that. So approach is we can choose $K$ numbers ...
user avatar
  • 143
1 vote
0 answers
145 views

Arbelos - Pappus chain radius of tangent circles

I would like to determine radius' of pappus chain circles which are tangent to Arbelos. Below I will put some photos from one book that showed how to determine it. The only thing that i don't ...
user avatar
  • 1,559
1 vote
1 answer
38 views

which domain does this Möbius map to $\Re(w) > 0$?

Given the following Möbius: $$ w = T(z) = \frac{1+z}{1-z} $$ How could I find the domain of $Z$ which $T$ maps to $\{\Re(w)>0\} $? I tried to inverse $T$ and got: $$ z = T^{-1}=\frac{w-1}{w+1} $$ ...
user avatar
  • 35
1 vote
1 answer
82 views

Continuation of the Riemann Prime Counting function

Let $f(x)=\sum_{n=1}^{\lfloor \ln(x)\rfloor} \frac {\pi(x^{\frac 1n})}n$ ($\pi(x)$ is the Riemann prime counting function, here are some more informations). It is thanks to Riemann well known that $\...
user avatar
  • 1,100
0 votes
1 answer
175 views

Inversive distance between concentric circles

I found an explication about Inversive distance in Coxeter book. But, i don't really understand some things in its explication. I can't imagine the meaning of: ''This inquiry almost forces us to ...
user avatar
  • 1,559
0 votes
0 answers
60 views

Construction of inverse point in sphere

i would like to know if my construction of inverse point of A in sphere, A' is right. First of all i constructed a line through pole $S$ and $A$, then i drew a line through $N$ perpendicular to $AS$. ...
user avatar
  • 1,559
0 votes
1 answer
111 views

Mobius inversion problem [closed]

Prove by Mobius inversion formula if $\frac{n}{\phi(n)}=\sum_{d\mid n} f(d)$ then $f(d)=\frac{\mu^2(d)}{\phi(d)}.$
user avatar
2 votes
1 answer
330 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}^...
user avatar
  • 3,500
1 vote
1 answer
259 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} &...
user avatar
  • 6,770