Questions tagged [mobius-inversion]
For questions related to Möbius inversion and its applications.
203 questions
0
votes
1
answer
102
views
Is it true that this quadruple sum involving $f(x,y,z,p)=x^p+y^p−z^p$, is equal to the sequence $1,0,0,0,...$ only if $p=1$ or $p=2$?
Consider the sum:
$$s(n) = \sum _{k=1}^n \left(\sum _{z=1}^n \left(\sum _{y=1}^n \left(\sum _{x=1}^n g(k)\left[\gcd (f(x,y,z,p),n)=k\right]\right)\right)\right)\label{1}\tag{1}$$
where
the minimal ...
- 7,524
0
votes
0
answers
66
views
Accentuating the appearance of convergence of the Möbius function Dirichlet series on the line $\sigma = \frac{2}{3}$ in the critical strip
Set the constant $c$ to:
$$c = -\frac{3}{4}$$
which is in the interval: $$-1 < c < 0$$
and let the matrix $A$ be:
$$A(n,k)=[k|n] - [n=k](1+c)$$
Then form the matrix power series:
$$M=\sum _{n \...
- 7,524
1
vote
0
answers
112
views
Bounding an equivalent expression of Mertens function
Some months ago, I derived the following formula for the Merten's function $M(n)$ using the inclusion-exclusion principle:
$$M(n)=1-\pi\left(n\right)+\sum_{p_{i}\leq\frac{n}{p_i}}\left(\pi\left(\frac{...
- 1,074
1
vote
1
answer
46
views
Question about step in proof for Mobius inversion formula
I came across this proof found in chapter 6.2 from Elementary Number Theory by David M. Burton, 7e and I am confused by one of the steps. Here is the theorem and proof as presented in the book:
...
- 65
1
vote
1
answer
54
views
Mobius Algebra Identity
I am working through Exercise 3.95 in Stanley’s Enumerative Combinatorics, which states in the Mobius algebra of a finite lattice $L$, given $z\in L$,
We have
$$\sum_{t\in L} \mu(0,t)t= \left(\sum_{u\...
- 125
3
votes
1
answer
104
views
definition of cyclotomic polynomials
The $n$th cyclotomic polynomial can be expressed via the Mobius function as follows:
$$\Phi_n(x) = \prod_{\substack{1\le d\le n\\d\mid n}}(x^d - 1)^{\mu(\frac{n}{d})}$$
In every reference I have ...
- 379
4
votes
1
answer
204
views
Does this function in $3$b$1$b has a name?
I was watching this video from $3$Blue$1$Brown channel, at minute 21:00 he introduced the following function:
$$
\chi(n)=
\begin{cases}
0 & \text{if } n=2k \\
1 & \text{if } n=4k+1\\
-1 & \...
- 6,267
2
votes
1
answer
51
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(...
- 1,074
0
votes
0
answers
60
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.
...
- 629
3
votes
1
answer
407
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 ...
- 1,074
0
votes
1
answer
54
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 ...
- 951
2
votes
0
answers
79
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 ...
- 1,074
4
votes
0
answers
189
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 ...
- 1,074
3
votes
1
answer
94
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
$$\...
- 1,305
0
votes
1
answer
64
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 ...
- 497
1
vote
0
answers
46
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 ...
- 7,524
2
votes
1
answer
345
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-...
- 14.5k
0
votes
1
answer
295
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 ...
- 141
1
vote
0
answers
55
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 \...
- 21.6k
1
vote
0
answers
130
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 ...
- 396
1
vote
0
answers
54
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-...
- 1,810
0
votes
1
answer
80
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 ...
user1107557
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 ...
- 157
-1
votes
1
answer
117
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(...
- 155
2
votes
1
answer
87
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]{...
- 1,173
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 ...
- 1
1
vote
1
answer
375
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 ...
- 10.3k
2
votes
1
answer
72
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 ...
- 50
3
votes
6
answers
439
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 ...
- 2,058
15
votes
1
answer
385
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....
- 24.7k
1
vote
2
answers
190
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\...
- 10.3k
2
votes
1
answer
657
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^...
- 10.3k
7
votes
1
answer
216
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)...
user1068604
0
votes
1
answer
85
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 ...
- 14.1k
2
votes
2
answers
108
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 $\{...
- 702
1
vote
0
answers
106
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 ...
- 1,070
2
votes
0
answers
102
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}...
- 199
1
vote
0
answers
49
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 ...
- 11
5
votes
1
answer
138
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 ...
1
vote
0
answers
67
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 $(...
0
votes
1
answer
100
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.{...
- 109
1
vote
0
answers
54
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 ...
- 633
3
votes
0
answers
115
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$$
...
- 3,211
1
vote
0
answers
54
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) := \...
- 11
0
votes
0
answers
49
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 ...
- 707
3
votes
1
answer
356
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 ...
1
vote
1
answer
146
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 ...
- 2,993
0
votes
0
answers
97
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 ...
- 4,374
2
votes
0
answers
79
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 ...
- 1,392
0
votes
0
answers
74
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 ...
user125368