Questions tagged [mobius-function]
Questions on the Möbius function μ(n), an arithmetic function used in number theory.
315
questions
1
vote
0answers
27 views
Summation of certain divisible numbers
Let $C(N,m)$ be the number of positive integers $\le N$ which are relatively prime to $m$. It can be found by following equation
\begin{align}
C(N,m)=\sum_{d|m}\mu (d)\left\lfloor\frac{N}{d}\right\...
5
votes
0answers
60 views
Tight bounds on the partial Möbius sum $\sum_{\substack{d|n\\d<Q}}\mu(d)$
An important area of study in Analytic Number Theory is the behavior of the Möbius function $\mu(n)$. I was trying to prove a different theorem when I came about a very interesting behavior. If you ...
2
votes
0answers
29 views
Question related to the expression of prime, twin-prime, and Sophie Germain prime counting functions in terms of Mertens function
This question assumes the following definitions.
(1) $\quad\pi(x)==\sum\limits_{p\le x}1\qquad\text{(prime counting function where $p\in P$ is a prime})$
(2) $\quad\pi_2(x)==\sum\limits_{p_2\le x}1\...
0
votes
2answers
19 views
Proving identity using Dirichlet L functions
I'm trying to prove the following identity using Dirichlet L functions :
${\displaystyle \sum _{d\mid n}\varphi (d)=n}$
I have shown proved that the Dirichlet Series of $\varphi (n)$ equals to
${\...
1
vote
2answers
38 views
Mobius Function
Find all integers $n, 1 ≤ n ≤ 100$ such that $µ(n) = 1$. My initial idea was to find all the primes between 1 and 100 using techniques of finding prime numbers. If p is prime then $µ(p)=-1$ so with ...
2
votes
0answers
59 views
Is anything known about bounds of $\sum_{n<x} \frac{\mu(n)}{\sqrt{n}}$?
Without assuming Riemann hypothesis, is anything known about bounds of partial sum $\sum_{n<x} \frac{\mu(n)}{\sqrt{n}}$ where $\mu(n)$ is Möbius function and $n \in \mathbb{N}$. It is known that ...
3
votes
0answers
34 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 ...
0
votes
2answers
62 views
Determine the number of irreducible polynomials of degrees 2, 3, and 6 over a prime field.
Determine the number of irreducible polynomials of degrees 2, 3, and 6 over the prime field $\mathbb F_p$.
My question is related to the answer posted for the above question. I was scratching my head ...
1
vote
1answer
34 views
Can we prove that partial sum $|\sum_1^N \mu(n)/n| \le 1/2$ when $N > 1$?
Here, $\mu(n)$ is Möbius function.
From this, we can see that partial sum $|\sum_1^N \frac{\mu(n)}{n}| \le 1$. when $N \in \mathbb{N}$.
We also know the series converges to $0$ and is not monotone.
...
0
votes
0answers
33 views
Möbius function of partition lattice
I know we can use Weisner's Theorem to obtain $\mu(\Pi_n)=(-1)^{n-1}(n-1)!$ where $\Pi_n$ is the partition lattice on an $n$-set. However, I was wondering if we could derive this result using the ...
0
votes
2answers
43 views
I need help understand this Möbius transformation
Show $w=\frac{z-i}{z+i}$ maps upper half plane into a unit disk centered at origin.
I rewrote the equation as $z=-i(\frac{w+1}{w-1})$ and since $|z|>0$ on upper half plane. I say $|-i(\frac{w+1}{w-...
0
votes
0answers
45 views
Evaluating $\sum_{n=1}^\infty \mu (n)$
Riesel and Gohl show in Some Calculations Related to Riemann's Prime Number Formula that
$$\sum_{n=1}^N \frac{\mu (n)}{n}\left(\int_{x^{\frac{1}{n}}}^\infty \frac{\mathrm dt}{t(t^2-1)\ln t}-\ln 2\...
1
vote
0answers
96 views
co-prime perfect power summation
The following link shows 10000 perfect power.
I was wondering how many numbers are there less than $n$ that are perfect power and also co-prime with $n$. i.e. $gcd(n,k) = 1$.
In general I would like ...
1
vote
0answers
34 views
Interpolation of the Möbius function
The Möbius function $\mu (n)$ can be computed using
$$\mu (n)=\sum_{\stackrel{1\le k \le n }{ \gcd(k,\,n)=1}} e^{2\pi i \frac{k}{n}}$$
(from An Introduction to the Theory of Numbers by Hardy and ...
1
vote
1answer
90 views
Show that $\frac{1}{\zeta(s)} = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^{s}}$.
Show that $$\frac{1}{\zeta(s)} = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^{s}}.$$
I'm trying to show the above and we haven't covered Euler's product formula yet so I don't think we can use that in our ...
0
votes
0answers
32 views
A sum of characters of a cyclic group
For a cyclic group $G$ of order $n$, with $g\in G$ not a generator of $G$, prove that
$$\sum_{d\mid n}\frac{\mu(d)}{\phi(d)}\sum_{\chi\in \hat G_d}\chi(g)=0,$$
where $\hat G_d$ is the set of all ...
1
vote
2answers
39 views
How to prove $\sum_{d|n} \mu(\frac{n}{d}) P(d) = 1$?
Background
I came up with an unorthodox proof of the following:
$$\sum_{d|n} \mu(\frac{n}{d}) P(d) = 1$$
Where $n \neq 1$, $P(d)$ is a function which counts the number of primes of $d$ and $\mu$ ...
0
votes
0answers
24 views
Why is $ \mathcal{O} \left(\sum_{d|P_z}\mu(d)\right) = \mathcal{O}\left(2^z\right) $?
Let $P_z$ denote the product of all primes less than $z$. Why does
$$
\mathcal{O} \left(\sum_{d|P_z}\mu(d)\right) = \mathcal{O}\left(2^z\right)
$$
hold?
Here, $\mathcal{O}$ is the Big $O$ notation ...
0
votes
0answers
30 views
Do we know the Mobius inverse of e^x?
I'm refereing to the The Generalized Möbius Inversion:
Suppose F(x) and G(x) are complex-valued functions defined on the interval [1,∞) such that
$$ G(x)=\sum _{1\leq n\leq x}F\left({\frac {x}{n}}\...
1
vote
0answers
29 views
Finding a simple upper bound for the number of primes in $x, x+p_k\#, x+2p_k\#, \dots, x+(p_k\#-1)p_k\#$
Let:
$p_k$ be the $k$th prime.
$p\#$ be the primorial for $p$
gcd$(a,b)$ the the greatest common divisor of $a$ and $b$
$\mu(x)$ be the möbius function
$x$ be an integer such that $p_k < x < ...
1
vote
1answer
34 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} ...
1
vote
1answer
33 views
Estimating the maximum number of primes in the sequence $x, x+p\#, x + 2p\#, \dots, x+ (p\#-1)p\#$ where $p$ is prime and $p\#$ is the primorial
Let:
$p$ be a prime
$p\#$ be the primorial for $p$
gcd$(a,b)$ be the greatest common divisor of $a$ and $b$.
$x$ be an integer such that $p < x < p\#$ and gcd$(x,p\#)=1$
$X$ be the set of of ...
0
votes
1answer
28 views
Methods for counting the number of bracelets for a 2-coloring.
Many answers given about the counting the number of necklaces and bracelets always refer to Burnside's Lemma or PET. It gives a relatively easy way to compute the number of ways with a formula. But I ...
0
votes
1answer
52 views
prove that $\sum_{d|n}{|\mu(d)|} = 2^{k}$
Let k be the number of prime factors other than a positive integer n. Prove that
$$\sum_{d|n}{|\mu(d)|} = 2^{k}$$
I'm not sure how to approach this problem. Can anyone give me a hint about how to ...
1
vote
0answers
56 views
Sum of members from multiplicative group of prime order $k$ modulo prime $P$? $c$ in: $\sum_{n=1}^{k} (g^n \bmod P) = c \cdot P$ ($g$ prime order $k$)
Let $P$ be a prime ($>2$) and $g$ a value between $2$ and $P-2$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$
If $g$ is a ...
2
votes
0answers
108 views
Are the non-trivial zeros of $\zeta(s)$ related specifically to the primes?
This question assumes the following definitions.
(1) $\quad \psi(x)=\sum\limits_{n\le x}\Lambda(n)\qquad\text{(second Chebyshev function)}$
(2) $\quad M(x)=\sum\limits_{n\le x}\mu(n)\qquad\text{(...
0
votes
1answer
30 views
Poset and Mobius function
Suppose that $P = (X,\leq)$ is a poset such that for $x,y \in X, x \neq y$, we have that either $|[x,y]| = 0$ or $|[x,y]| = 2$ or $|[x,y]| = 6$. I asked to compute the Möbius function for this poset. ...
2
votes
0answers
55 views
Do these arithmetic functions have an infinite number of integer zeros?
This question assumes the following definitions.
(1) $\quad a(n)=\sum\limits_{d|n}\mu(d)\,\mu\left(\frac{n}{d}\right),\qquad \frac{1}{\zeta(s)^2}=\sum\limits_{n=1}^\infty\frac{a(n)}{n^s}\qquad$(see ...
2
votes
2answers
147 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 ...
1
vote
1answer
70 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. ...
0
votes
0answers
24 views
sum of Mobius function over arithmetic progression in function field case
I am trying to find an estimate for the following sum:
$$S_\mu =\sum_{f\in M_n \\f\equiv A\bmod {Q}} \mu(f),$$ where $\mu(f)$ is the Mobius function and $ M_n$ is the set of all monic polynomials.
...
2
votes
0answers
34 views
Questions related to the Dedekind psi function $\psi(n)$
The Wikipedia article Dedekind psi function indicates the Dedekind psi function defined in formula (1) below was introduced by Richard Dedekind in connection with modular functions.
(1) $\quad\psi(n)=...
4
votes
1answer
82 views
Convergence of Mobius sum to $\frac{1}{\zeta(2)}$
It is well known that
$$\frac{1}{\zeta(s)}=\sum_{n=1}^{\infty}\frac{\mu(n)}{n^s}$$
which for $s=2$ gives a convergence to $6/\pi^2$.
If we consider the partial sum, Apostol gives
$$\sum_{n\leq x}
...
0
votes
1answer
26 views
Mobius and Divisor-Counting function
While looking at the function $$f(x)=\sum_{k|x} \mu(k)*\sigma_0(k)$$ where $\mu(x)$ is the mobius function and $\sigma_0(x)$ is the number of divisors of $x$, I noticed that $f(x)$ is either $1$ or $-...
1
vote
1answer
31 views
Mobius function and exponential sums
It is easy to show that if $a$ and $n$ are positive integers with $\gcd(a,n)=1$, then
$$ \sum_{\substack{z=0 \\ \gcd(z,n)=1}}^{n-1} e^{2\pi i \frac{az}n} = \mu(n). $$
What is the general form of ...
1
vote
0answers
37 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) ...
3
votes
1answer
74 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 ...
0
votes
0answers
29 views
Calculating Mobius Function for large numbers
Is there any known algorithm for calculating whether a large, squarefree $N$ has an odd or even number of prime factors? That is, whether $\mu(N)=1$ or $\mu(N)=-1$, where $\mu(N)$ is the Mobius ...
2
votes
0answers
26 views
Inequality involving the Möbius function
Let $a$ be an integer such that $a>1$, $n\in\mathbb{N}$ and define the number $x_{m}$ by
$$x_{m}=\sum_{d|m}\mu(d)(-1)^{n}[a^{\frac{m/d}{(m/d,n)}}-1]^{(m/d,n)}$$
I must to proof that $x_{m}\neq 0, ...
0
votes
1answer
72 views
Mobius Function and Triangular Numbers
The Mobius function for the positive integers µ : $\mathbb Z^+$ → {$−1,0,1$} is defined on page 17 of the course notes. The triangular numbers are the positive integers of the form $n \choose 2$ for $...
1
vote
2answers
33 views
Understanding a proof of an Identity involving the Möbius Function
Lemma: For each integer $N\geq 1$, we have
$$\sum_{(k,N)=1}\frac{t^k}{k}=-\sum_{d|N}\frac{\mu(d)}{d}log(1-t^d)$$
Proof. Let $c_{k}=1$ if $(k,N)=1$ and $c_{k}=0$ otherwise. By basic propierties of ...
2
votes
1answer
32 views
Question on Potential Relationship between Mertens Function and Perfect Number Counting Function
This question assumes the following definitions where $M(x)$ is the Mertens function and $f(x)$ is the perfect number counting function. See here for more information on the Wolfram Language ...
1
vote
1answer
58 views
What is the image of D under the map $f(z)=bz+\frac{1}{z}$?
Let $f:\mathbb C_\infty\to \mathbb C_\infty$ be a sum of Mobius transformations defined by $f(z)=bz+\frac{1}{z}$, where $-1<b<1$.
I've succeeded to find the image of the unit closed disc $D$...
-1
votes
1answer
82 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)}.$
3
votes
1answer
109 views
Questions on a formula for the Mertens function
The Mertens function $M(x)$ is defined as follows.
(1) $\quad M(x)=\sum\limits_{n=1}^x\mu(n)$
I've noticed the Merten's function can also be evaluated as follows which is related to OEIS entry ...
1
vote
0answers
35 views
Software for computing Möbius function of a poset
Is there any software available (possibly free) for computing the Möbius function of a finite partially ordered set (poset) and related things?
For a definition of Möbius function of a poset see ...
1
vote
1answer
105 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}^...
4
votes
2answers
510 views
How to calculate the GCD?
How to evaluate the following with the help of Mobius function ?
$$\displaystyle\sum_{i=1}^n \sum_{j=i+1}^n \sum_{k=j+1}^n \sum_{l=k+1}^n {gcd(i,j,k,l)^4} .$$
In other words, we have to ...
4
votes
1answer
78 views
Can this relationship between the Harmonic Number, Mertens, and Sum-of-Divisors functions be proven?
I've verified conjectured relationship (3) below for several thousand values of $x$ and suspect that it's true.
(1) $\quad H(x)=\sum\limits_{n=1}^x\frac{1}{n}\qquad\qquad\qquad\quad$(Harmonic Number ...
0
votes
0answers
23 views
Rational number sets which grow in cardinality and a related sequence of numbers.
Define the collection of sets $\left\{Q_n\right\}$ as follows:
$$Q_1 = \{0\};\quad Q_2 = \left\{\frac{1}{2}\right\} \cup Q_1; \quad Q_3 = \left\{\frac{1}{3}, \frac{2}{3}\right\} \cup Q_2;$$
$$\left\{\...
