Skip to main content

Questions tagged [mobius-inversion]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
43 views

Which is the error in this application of Möbius inversion formula?

In Wikipedia the following generalisation of the Möbius inversion formula is given (and proved): Suppose $F(x)$ and $G(x)$ are complex-valued functions defined on the interval $[1, ∞)$ such that $$G(...
Juan Moreno's user avatar
  • 1,110
0 votes
0 answers
56 views

Sequence notation?

Cor. Mobius Inversion Formula for multiplicative functions. Let $f,F$ be multiplicative functions such that $F(n)=\sum\limits_{d\mid n}f(d)$. Then $f(n)=\sum\limits_{d\mid n}\mu(\frac nd)F(d)$. Proof. ...
Jason Xu's user avatar
  • 617
2 votes
1 answer
372 views

Sharp bounding of a sum involving Möbius function

I am trying to bound as sharply as possible the partial sum $$S(n)=\sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \left(\pi\left(\frac{n}{k}\right) + f(n,k)\right)$$ Where $\pi(x)$ is the ...
Juan Moreno's user avatar
  • 1,110
0 votes
0 answers
54 views

Generalization of Möbius inversion formula

A generalization of Möbius inversion formula guarantees that if we have $G(n)=\sum_{k=1}^{n} F\left(\frac{n}{k}\right)$, then $F(n)=\sum_{k=1}^{n} \mu(k) G\left(\frac{n}{k}\right)$. If we have $\sqrt{...
Juan Moreno's user avatar
  • 1,110
0 votes
1 answer
48 views

Prove the Fourier coefficients $c_S$ of $f\colon\mathbb{F}_2^n\to\mathbb{F_2}$ is $\sum_{\operatorname{supp}(x)\subseteq S}f(x)$

Given $n>0$. Suppose $f:\mathbb{F}_2^n\to\mathbb{F_2}$ can be expressed as $f(x)=\sum_{S\subseteq [n]}c_Sx^S \pmod{2}$, where $x=(x_1,\cdots,x_n)^T, c_S\in\mathbb{F}_2,x^S=\prod_{i\in S}x_i$. It is ...
qmww987's user avatar
  • 881
2 votes
0 answers
64 views

Möbius inversion formula and $\sum_{k\leq n} \frac{\mu(k)}{k}$

I have tried to apply what is stated at the Generalizations of Möbius inversion formula section of Wikipedia to bound $$\sum_{k\leq n} \frac{\mu(k)}{k}$$ The application seems simple and ...
Juan Moreno's user avatar
  • 1,110
4 votes
0 answers
178 views

Bounding a partial sum with Möbius inversion formula

I am trying to bound the partial sum $$S(n)=\sum_{k=1}^{\sqrt{n}} \mu(k) \pi\left(\frac{n}{k}\right)$$ Where $\pi(x)$ is the prime counting function, and $\mu(x)$ is the Möbius function. Empirical ...
Juan Moreno's user avatar
  • 1,110
3 votes
1 answer
92 views

Partial Möbius convolutions

I am well aware of the Möbius inversion formula, which states $$\sum_{d \mid q} \mu(q/d) = \mathbf{1}_{q=1}$$ Do we know how to give a closed formula for the "partial" such convolution $$\...
TheStudent's user avatar
  • 1,255
0 votes
1 answer
60 views

Problems about inversion map

Let $\tau_{\omega}$ be the inversion with respect to circle $\omega$ and $\omega$ is the unit circle in $\mathbb{E}^2$ with centre $O=(0,0)$. There are three cases: a. Find $\tau_{\omega}(\ell)$ where ...
End points's user avatar
1 vote
0 answers
44 views

Prime numbers as zeros of polynomials from the determinant of the form $P(x,N)=|\log(x) \gcd (n,k)-\phi (n)\log(\gcd (n,k))|$

Let $f(n)$ be some arbitrary sequence $\log(n),n,n^2,\dots$ $$f(n)=\log(n),n,n^2,\dots$$ and $$a(n)=\frac{\sum\limits_{d \mid n} f(d) \mu \left(\frac{n}{d}\right)}{\phi (n)}$$ and construct the ...
Mats Granvik's user avatar
  • 7,406
1 vote
1 answer
232 views

Proof of the dual Möbius Inversion Formula

The Dual Möbius Inversion Formula: Let $\mathcal D$ be a divisor closed set of natural numbers (i.e., if $d\in \mathcal D$ and $c \mid d$, then $c\in \mathcal D$.) Let $f$ and $g$ be two complex-...
stoic-santiago's user avatar
0 votes
1 answer
145 views

Applications of the mobius inversion in algebraic or arithmetic geometry

I was wondering if there were any generalisations or applications of the ideas of the Möbius inversion formula to more modern areas of mathematics such as algebraic or arithmetic geometry. I know they ...
Pambra iskra's user avatar
1 vote
0 answers
54 views

Is the set of divisor indicator functions at $x^2 - 1$: $B' = \{(d \mid x^2 - 1) : d \in \Bbb{N}\}$ a $\Bbb{Z}$-linearly independent set?

We know that the set $B = \{(d \mid x) = \begin{cases} 1, d \mid x \\ 0, \text{ otherwise} \end{cases}, \ d \in \Bbb{N}\}$ forms a $\Bbb{Z}$-module Schauder basis for the module $M =\{ \Bbb{N} \to \...
HighAsAKiteOnMath's user avatar
1 vote
0 answers
126 views

New $ \overset {s}{\underset{k=x}{ \lower 3pt { \LARGE\Xi}}} $ operator and Möbius function

At the beginning I will explain some concepts and at the end I will ask the specific question. Let's consider some operator $ \overset {s}{\underset{k=x}{ \lower 3pt { \LARGE\Xi}}} $ on function $f ...
Wreior's user avatar
  • 396
1 vote
0 answers
49 views

Characterization of Möbius-monotonicity

We say that an arithmetic function $f:\mathbb{Z}^+\to\mathbb{C}$ is Möbius-monotone if $\forall n\geq1:(\mu*f)(n)\geq0$ (where $*$ denotes de Dirichlet convolution), i.e. if there exists a non-...
K. Makabre's user avatar
  • 1,800
0 votes
1 answer
75 views

Applying the Möbius inversion formula to $f(n) = \sum_{p\mid n}g(p)$?

Is there a specific technique that exists to reducing summation over divisors to prime divisors? Specifically I am interested in applying the Möbius inversion formula to an arithemetic function of the ...
user avatar
1 vote
0 answers
26 views

Product of all reduced residues in relation with the function $\mu$: $\prod_{1\leq a\leq n,(a,n)=1}a=n^{\varphi(n)}\prod_{d|n}(d!/d^d)^{\mu(n/d)}$

We know that for any arithmetic function $f$ the Mobius inversion formula gives its inversion. Hence $$ F(n)=\prod_{d|n}f(d)\implies f(n)=\prod_{d|n} F(n/d)^{\mu(d)}.$$ The above statement can be ...
barbatos233's user avatar
-1 votes
1 answer
90 views

Product version of Möbius Inversion formula

I am currently learning about Möbius Inversion. In Wikipedia , the sum version is proved using convolutions which I can follow along with. However, it also lists a product version of this formula: $g(...
Meow's user avatar
  • 165
2 votes
1 answer
71 views

Möbius Inversion Forumla for for $\sum_{n}\pi(\sqrt[n]{x})$

Consider a function $$J(x)=\sum_{n}\frac{\pi(\sqrt[n]{x})}{n}$$ with the prime counting function $\pi(x)$. This sum is finite, because for $n$ big enough $\sqrt[n]{x}<2$ and therefore $\pi(\sqrt[n]{...
HyperPro's user avatar
  • 879
0 votes
0 answers
40 views

Task , given matrices, it is necessary to make the matrices "F" and "G" according to the scheme

enter image description here ( 2 ); B = (-2); C = (-1); D = = G₁ Task 3. Given matrices A = C= 1): D = (-2 1 2). 1) according to the schemes, make a mat matrices F and G. Find the products of matrices ...
G-man's user avatar
  • 1
1 vote
1 answer
299 views

Prove this generalization of Möbius inversion formula

Generalizations list this one as a generalization of Möbius inversion formula- Suppose $F(x)$ and $G(x)$ are complex-valued functions defined on the interval $[1, ∞)$ such that $$G(x)=\sum_{1\le n\le ...
Sayan Dutta's user avatar
  • 9,154
2 votes
1 answer
61 views

Is it possible or interesting to try to build Möbius inversion for non-locally finite posets?

In some of my free time I've been reading up a bit on Möbius inversion. What puzzles me is that in just about every discussion of incidence algebras that I can find there is the strict requirement of ...
H. Pecoraro 's user avatar
3 votes
6 answers
401 views

Möbius inversion and Möbius function as sum of cosines

Let $\mu (n)$ be the Möbius function. I want to prove the following formula: $$\mu (n)=\sum_{\substack{1\leq k \leq n\\ (k,n)=1}}\cos \frac{2k\pi}{n}.$$ Let $F(n)$ be the right hand side, then by ...
Ishigami's user avatar
  • 1,609
15 votes
1 answer
343 views

How many ways to arrange $n$ points in $(\Bbb F_q)^2$ with no three collinear?

How many ways are there to arrange $n$ points in the finite field plane $(\Bbb F_q)^2$ with no three of the points collinear? An easy upper bound is $(q^2)^n=q^{2n}$, but of course it's less than that....
Akiva Weinberger's user avatar
1 vote
2 answers
164 views

$\varphi(x,n)=\sum_{d|n}\mu(d)\left\lfloor\frac xd\right\rfloor$ and $\sum_{d|n}\varphi\left(\frac xd,\frac nd\right)=\lfloor x\rfloor$

If $x$ is real, $x\ge 1$, let $\varphi(x,n)$ denote the number of positive integers less than or equal to $x$ that are relatively prime to $n$. Prove that $$\varphi(x,n)=\sum_{d|n}\mu(d)\left\lfloor\...
Sayan Dutta's user avatar
  • 9,154
2 votes
1 answer
518 views

Product form of Mobius Inversion formula: $g(n)=\prod_{d|n}f(d)^{a(n/d)}\iff f(n)=\prod_{d|n} g(d)^{b(n/d)}$

Product form of the Möbius inversion formula: If $f(n)>0$ for all $n$ and if $a(n)$ is real, $a(1)\neq 0$, prove that $$g(n)=\prod_{d|n}f(d)^{a(n/d)}\iff f(n)=\prod_{d|n} g(d)^{b(n/d)}$$ where $b=a^...
Sayan Dutta's user avatar
  • 9,154
7 votes
1 answer
187 views

Count pairwise coprime triples such that the maximum number of the triple is not greater than N

Problem Statement: Given N you are to count the number of pairwise coprime triples which satisfy $1≤a,b,c≤N$. Example: For example N=3, valid triples are (1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,3,1)...
user avatar
0 votes
1 answer
84 views

Calculate arithmetic function - Möbius inversion

An arithmetic function $f$ has the property $$\sum_{d\mid n}f(d)=\begin{cases}0 & \text{ if n is divisible by a square of a prime} \\ n & \text{ otherwise}\end{cases}$$ Calculate $f(6300)$. I ...
Mary Star's user avatar
  • 14k
2 votes
2 answers
97 views

Prove: at most two circles are needed to be tangent to all the circle sequence

Construct a circle sequence $\{C_n\}$ (e.g., blue in the figure below) in 2D Cartesian coordiante system as: the $x$-coordiantes of centers of all the circle $C_n$ are $\frac{1}n$; all the circles $\{...
user6043040's user avatar
1 vote
0 answers
100 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 ...
Orb's user avatar
  • 1,060
2 votes
0 answers
95 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}...
user8083's user avatar
  • 131
1 vote
0 answers
48 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 ...
DrJimmour's user avatar
5 votes
1 answer
116 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 ...
Carla only proves trivial prop's user avatar
1 vote
0 answers
47 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 $(...
Musashi Aldover's user avatar
0 votes
1 answer
98 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.{...
Lorenzo's user avatar
  • 109
1 vote
0 answers
49 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 ...
Baklava Gain's user avatar
3 votes
0 answers
106 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$$ ...
Agno's user avatar
  • 3,191
1 vote
0 answers
52 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) := \...
dld's user avatar
  • 11
0 votes
0 answers
40 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 ...
a_i_r's user avatar
  • 671
3 votes
1 answer
290 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 ...
batteryhorse35's user avatar
1 vote
1 answer
134 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 ...
DesmondMiles's user avatar
  • 2,713
0 votes
0 answers
94 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 ...
Matt Calhoun's user avatar
  • 4,404
2 votes
0 answers
77 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 ...
mkultra's user avatar
  • 1,382
0 votes
0 answers
73 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
3 votes
0 answers
229 views

Möbius 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 Möbius function is $\mu(p,q)=\left\{ \begin{array}{ll} (-1)^{|p|-|q|} & \...
idocomb's user avatar
  • 339
0 votes
1 answer
389 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
74 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
2 votes
2 answers
194 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 ...
GraphMathTutor's user avatar
1 vote
0 answers
31 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 ...
More Anonymous's user avatar
3 votes
3 answers
718 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 ...
math-traveler's user avatar