Combinatorial Identities Involving the Möbius Function

Mohamed El Bachraoui and Mohamed Salim Department of Mathematical Sciences United Arab Emirates University P.O. Box 17551 Al-Ain United Arab Emirates

                    melbachraoui@uaeu.ac.ae
                       msalim@uaeu.ac.ae

Abstract We derive some identities and inequalities concerning the Möbius function. Our

main tool is phi functions for intervals of positive integers and their unions.

1 Introduction

The Möbius function μ is an important arithmetic function in number theory and combinatorics that appears in various identities. We mention the following identities which are well known and can be found in books on elementary number theory and arithmetic functions. Let n be a positive integer. Then

∑_{d|n} μ(d) = \begin{cases}1, if n = 1; \\ 0, if n > 1. \end{cases}

If τ(n) is the number of divisors of n, then

∑_{d|n} μ(d)τ(n/d) = 1.

If n = ∏_{i=1}^{r} p_{i}^{k_{i}} is the prime decomposition of n, then

∑_{d|n} μ(d)λ(d) = 2^{r},

where λ denotes the Liouville lambda function defined as follows: If m = ∏_{i=1}^{s} p_{i}^{l_{i}} is the prime decomposition of m, then

λ(m) = (−1)^{∑_{i=1}^{s} l_{i}}.

For a survey on combinatorial identities we refer to Hall [6] and Riordan [9] and their references. In this note we shall prove the following two theorems on identities involving the Möbius mu function.

Theorem 1. Let m and n be positive integers such that n > 1. Then we have

(a) ∑_{d|n} μ(d)2^{⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} = ∑_{d|n} μ(d) (⌊\frac{m}{d}⌋ − ⌊\frac{m − 1}{d}⌋) = \begin{cases}0, if gcd(m, n) > 1; \\ 1, if gcd(m, n) = 1. \end{cases}

(b) ∑_{d|n} μ(d)2^{⌊ \frac{m+1}{d} ⌋−⌊ \frac{m−1}{d} ⌋} =

1, if gcd(m, n) > 1 and gcd(m + 1, n) > 1;

2, if gcd(m, n) = 1 and gcd(m + 1, n) > 1 or gcd(m, n) > 1 and gcd(m + 1, n) = 1; 3, if gcd(m, n) = gcd(m + 1, n) = 1.

Theorem 2. Let m and n be positive integers such that n > 1. Then we have:

(a) ∑_{d|n} μ(d) (⌊\frac{m + 1}{d}⌋ − ⌊\frac{m − 1}{d}⌋) =

0, if gcd(m, n) > 1 and gcd(m + 1, n) > 1;

1, if gcd(m, n) = 1 and gcd(m + 1, n) > 1 or gcd(m, n) > 1 and gcd(m + 1, n) = 1; 2, if gcd(m, n) = gcd(m + 1, n) = 1.

(b) ∑_{d|n} μ(d)\binom{⌊\frac{m+1}{d}⌋ − ⌊\frac{m−1}{d}⌋ + 1}{2} =

1, if gcd(m, n) > 1 and gcd(m + 1, n) > 1;

2, if gcd(m, n) = 1 and gcd(m + 1, n) > 1 or gcd(m, n) > 1 and gcd(m + 1, n) = 1; 3, if gcd(m, n) = gcd(m + 1, n) = 1.

Our proofs are combinatorial with phi functions for integer subsets as a main tool. For the sake of completeness we include the following result which is a natural extension of El Bachraoui [3, Theorem 2 (a)] on Möbius inversion for arithmetical functions in several variables. For simplicity we let

(\overline{m}_{a}, \overline{n}_{b}) = (m_{1}, m_{2}, …, m_{a}, n_{1}, n_{2}, …, n_{b})

and

(\frac{\overline{m}_{a}}{d} , [\frac{\overline{n}_{b}}{d} ]) = (\frac{m_{1}}{d} , \frac{m_{2}}{d} , …, \frac{m_{a}}{d} , [\frac{n_{1}}{d} ] , [\frac{n_{2}}{d} ] , …, [\frac{n_{b}}{d} ]) .

Theorem 3. If F and G are arithmetical of a + b variables, then

G(\overline{m}_{a}, \overline{n}_{b}) = ∑_{d| gcd(m_{1},m_{2},...,m_{a})} F (\frac{\overline{m}_{a}}{d} , [\frac{\overline{n}_{b}}{d} ])

if and only if

F (\overline{m}_{a}, \overline{n}_{b}) = ∑_{d| gcd(m_{1},m_{2},...,m_{a})} μ(d)G (\frac{\overline{m}_{a}}{d} , [\frac{\overline{n}_{b}}{d} ]) .

2 Phi functions

Throughout let k, l, m, l_{1}, l_{2}, m_{1}, m_{2} and n be positive integers such that l ≤ m and l_{1} ≤ m_{1} ≤ l_{2} ≤ m_{2}, let [l, m] = {l, l + 1, …, m}, and let A be a nonempty finite set of positive integers. The set A is called relatively prime to n if gcd(A ∪ {n}) = gcd(A, n) = 1.

Definition 4. Let

Φ(A, n) = #{X ⊆ A : X ≠ ∅ and gcd(X, n) = 1}

and

Φ_{k}(A, n) = #{X ⊆ A : #X = k and gcd(X, n) = 1}.

Nathanson, among other things, introduced Φ(n) and Φ_{k}(n) (in our terminology Φ([1, n], n) and Φ_{k}([1, n], n) respectively) along with their formulas in Nathanson [7]. Formulas for Φ([m, n], n) and Φ_{k}([m, n], n) can be found in El Bachraoui [3] and Nathanson and Orosz [8] and formulas for Φ([1, m], n) and Φ_{k}([1, m], n) are obtained in El Bachraoui [4]. Ayad and Kihel in [1, 2] considered extensions to sets in arithmetic progression and obtained formulas for Φ([l, m], n) and Φ_{k}([l, m], n) as consequences. Recently the following formulas for Φ([1, m_{1}] ∪ [l_{2}, m_{2}]) and Φ_{k}([1, m_{1}] ∪ [l_{2}, m_{2}]) have been found in El Bachraoui [5].

Theorem 5. We have

\begin{aligned}(a) Φ([1, m_{1}] ∪ [l_{2}, m_{2}], n) & = ∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋−⌊ \frac{l_{2}−1}{d} ⌋}, \\ (b) Φ_{k}([1, m_{1}] ∪ [l_{2}, m_{2}], n) & = ∑_{d|n} μ(d) \binom{⌊\frac{m_{1}}{d} ⌋ + ⌊\frac{m_{2}}{d} ⌋ − ⌊\frac{l_{2}−1}{d}⌋}{k}. \end{aligned}

3 Phi functions for [l_{1}, m_{1}] ∪ [l_{2}, m_{2}]

We need two lemmas.

Lemma 6. Let

Ψ(l_{1}, m_{1}, l_{2}, m_{2}, n) = #{X ⊆ [l_{1}, m_{1}] ∪ [l_{2}, m_{2}] : l_{1}, l_{2} ∈ X and gcd(X, n) = 1},

Ψ_{k}(l_{1}, m_{1}, l_{2}, m_{2}, n) = #{X ⊆ [l_{1}, m_{1}] ∪ [l_{2}, m_{2}] : l_{1}, l_{2} ∈ X, |X| = k, and gcd(X, n) = 1}.

Then

(a) Ψ(l_{1}, m_{1}, l_{2}, m_{2}, n) = ∑_{d| gcd(l_{1},l_{2},n)} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋− \frac{l_{1}+l_{2}}{d}} ,

(b) Ψ_{k}(m_{1}, l_{2}, m_{2}, n) = ∑_{d| gcd(l_{1},l_{2},n)} μ(d)\binom{⌊\frac{m_{1}}{d} ⌋ + ⌊\frac{m_{2}}{d} ⌋ − \frac{l_{1}+l_{2}}{d}}{k − 2}.

Proof. (a) Assume first that m_{2} ≤ n. Let P(l_{1}, m_{1}, l_{2}, m_{2}) denote the set of subsets of [l_{1}, m_{1}] ∪ [l_{2}, m_{2}] containing l_{1} and l_{2} and let P(l_{1}, m_{1}, l_{2}, m_{2}, d) be the set of subsets X of [l_{1}, m_{1}] ∪ [l_{2}, m_{2}] such that l_{1}, l_{2} ∈ X and gcd(X, n) = d. It is clear that the set P(l_{1}, m_{1}, l_{2}, m_{2}) of cardinality 2^{m_{1}+m_{2}−l_{1}−l_{2}} can be partitioned using the equivalence relation of having the same gcd (dividing l_{1}, l_{2} and n). Moreover, the mapping A ↦ \frac{1}{d}X is a one-to-one correspondence between P(l_{1}, m_{1}, l_{2}, m_{2}, d) and the set of subsets Y of [l_{1}/d, ⌊m_{1}/d⌋] ∪ [l_{2}/d, ⌊m_{2}/d⌋] such that l_{1}/d, l_{2}/d ∈ Y and gcd(Y, n/d) = 1. Then

#P(l_{1}, m_{1}, l_{2}, m_{2}, d) = Ψ(l_{1}/d, ⌊m_{1}/d⌋, l_{2}/d, ⌊m_{2}/d⌋, n/d).

Thus

2^{m_{1}+m_{2}−l_{1}−l_{2}} = ∑_{d|(l_{1},l_{2},n)} #P(l_{1}, m_{1}, l_{2}, m_{2}, d) = ∑_{d|(l_{1},l_{2},n)} Ψ(l_{1}/d, ⌊m_{1}/d⌋, l_{2}/d, ⌊m_{2}/d⌋, n/d),

which by Theorem 3 is equivalent to

Ψ(l_{1}, m_{1}, l_{2}, m_{2}, n) = ∑_{d|(l_{1},l_{2},n)} μ(d)2^{⌊m_{1}/d⌋+⌊m_{2}/d⌋−(l_{1}+l_{2})/d}.

Assume now that m_{2} > n and let a be a positive integer such that m_{2} ≤ n^{a}. As gcd(X, n) = 1 if and only if gcd(X, n^{a}) = 1 and μ(d) = 0 whenever d has a nontrivial square factor, we have

Ψ(l_{1}, m_{1}, l_{2}, m_{2}, n) = Ψ(l_{1}, m_{1}, l_{2}, m_{2}, n^{a})

= ∑_{d|(l_{1},l_{2},n^{a})} μ(d)2^{⌊m_{1}/d⌋+⌊m_{2}/d⌋−(l_{1}+l_{2})/d}

= ∑_{d|(l_{1},l_{2},n)} μ(d)2^{⌊m_{1}/d⌋+⌊m_{2}/d⌋−(l_{1}+l_{2})/d}.

(b) For the same reason as before, we may assume that m_{2} ≤ n. Noting that the correspondence X ↦ \frac{1}{d}X defined above preserves the cardinality and using an argument similar to the one in part (a), we obtain the following identity

\binom{m_{1} + m_{2} − l_{1} − l_{2}}{k − 2} = ∑_{d|(l_{1},l_{2},n)} Ψ_{k}(l_{1}/d, ⌊m_{1}/d⌋, l_{2}/d, ⌊m_{2}/d⌋, n/d)

which by Theorem 3 is equivalent to

Ψ_{k}(l_{1}, m_{1}, l_{2}, m_{2}, n) = ∑_{d|(l_{1},l_{2},n)} μ(d)\binom{⌊m_{1}/d⌋ + ⌊m_{2}/d⌋ − (l_{1} + l_{2})/d}{k − 2}.

By arguments similar to the ones in the proof of Lemma 6 we have: Lemma 7. Let

ψ(l, m, n) = #{X ⊆ [l, m] : l ∈ X and gcd(X, n) = 1},
ψ_{k}(l, m, n) = #{X ⊆ [l, m] : l ∈ X, #X = k, and gcd(X, n) = 1}.

Then

ψ(l, m, n) = ∑_{d| gcd(l,n)} μ(d)2^{⌊m/d⌋−l/d},

ψ_{k}(l, m, n) = ∑_{d| gcd(l,n)} μ(d)\binom{⌊m/d⌋ − l/d}{k}.

We are now ready to prove the main theorem of this section. Theorem 8. We have

(a) Φ([l_{1}, m_{1}] ∪ [l_{2}, m_{2}], n) = ∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋−⌊ \frac{l_{1}−1}{d} ⌋−⌊ \frac{l_{2}−1}{d} ⌋},

(b) Φ_{k}([l_{1}, m_{1}] ∪ [l_{2}, m_{2}], n) = ∑_{d|n} μ(d)\binom{⌊\frac{m_{1}}{d} ⌋ + ⌊\frac{m_{2}}{d} ⌋ − ⌊\frac{l_{1}−1}{d}⌋ − ⌊\frac{l_{2}−1}{d}⌋}{k}.

Proof. (a) Clearly Φ([l_{1}, m_{1}] ∪ [l_{2}, m_{2}], n) =

(1) Φ([1, m_{1}] ∪ [l_{2}, m_{2}], n) − ∑_{i=1}^{l_{1}−1} ∑_{j=l_{2}}^{m_{2}} Ψ(i, m_{1}, j, m_{2}, n) − ∑_{i=1}^{l_{1}−1} ψ(i, m_{1}, n) =

∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋−⌊ \frac{l_{2}−1}{d} ⌋} − ∑_{i=1}^{l_{1}−1} ∑_{j=l_{2}}^{m_{2}} ∑_{d|(i,j,n)} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋− \frac{i+j}{d}} − ∑_{i=1}^{l_{1}−1} ∑_{d|(i,n)} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋− \frac{i}{d}} ,

where the second identity follows by Theorem 5, Lemma 6, and Lemma 7. Rearranging the triple summation in identity (1), we get

∑_{i=1}^{l_{1}−1} ∑_{j=l_{2}}^{m_{2}} ∑_{d|(i,j,n)} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋− \frac{i+j}{d}} = ∑_{d|n} ∑_{\begin{matrix}i=1 \\ d|i \end{matrix}}^{l_{1}−1} ∑_{\begin{matrix}j=l_{2} \\ d|j \end{matrix}}^{m_{2}} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋− \frac{i+j}{d}}

= ∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋} ∑_{i=1}^{⌊ \frac{l_{1}−1}{d} ⌋} 2^{−i} ∑_{j=⌊ \frac{l_{2}−1}{d} ⌋+1}^{⌊ \frac{m_{2}}{d} ⌋} 2^{−j}

(2)  = ∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋−⌊ \frac{l_{2}−1}{d} ⌋}(1 − 2^{−⌊ \frac{m_{2}}{d} ⌋+⌊ \frac{l_{2}−1}{d} ⌋}) ∑_{i=1}^{⌊ \frac{l_{1}−1}{d} ⌋} 2^{−i}

= ∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋−⌊ \frac{l_{2}−1}{d} ⌋}(1 − 2^{−⌊ \frac{m_{2}}{d} ⌋+⌊ \frac{l_{2}−1}{d} ⌋})(1 − 2^{−⌊ \frac{l_{1}−1}{d} ⌋}).

Similarly the double summation in identity (1) gives

(3)  ∑_{i=1}^{l_{1}−1} ∑_{d|(i,n)} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋− \frac{i}{d}} = ∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋}(1 − 2^{−⌊ \frac{l_{1}−1}{d} ⌋}).

Combining identities (1), (2), and (3) we find

Φ([l_{1}, m_{1}] ∪ [l_{2}, m_{2}], n) = ∑_{d|n} μ(d)2^{⌊ \frac{m_{1}}{d} ⌋+⌊ \frac{m_{2}}{d} ⌋−⌊ \frac{l_{1}−1}{d} ⌋−⌊ \frac{l_{2}−1}{d} ⌋}.

This completes the proof of part (a). Part (b) follows by similar ideas. Corollary 9. (Ayad and Kihel [2]) We have

Φ([l, m], n) = ∑_{d|n} 2^{⌊ \frac{m}{d} ⌋−⌊ \frac{l−1}{d} ⌋},

Φ_{k}([l, m], n) = ∑_{d|n} \binom{⌊\frac{m}{d}⌋ − ⌊\frac{l−1}{d}⌋}{k}.

Proof. Use Theorem 8 with l_{1} = l, m_{1} = m − 1, and l_{2} = m_{2} = m.

4 Proofs of the main results

Proof of Theorem 1. (a) Apply Corollary 9 to l = m and k = 1.

(b) Apply Corollary 9 to the interval [m, m + 1]. Proof of Theorem 2. (a) Apply Theorem 8(b) to l_{1} = m, m_{1} = m + 1, l_{2} = m_{2} = n, and k = 1 and use the fact that ∑_{d|n} μ(d) = 0 whenever n > 1.

(b) Apply Theorem 8(b) to l_{1} = m, m_{1} = m + 1, l_{2} = m_{2} = n, and k = 2.

5 Acknowledgment

The authors are grateful to the referee for valuable comments and interesting suggestions.

References

[1] M. Ayad and O. Kihel, On the number of subsets relatively prime to an integer, J. Integer Sequences 11 (2008), Article 08.5.5.

[2] M. Ayad and O. Kihel, On relatively prime sets, Integers 9 (2009), 343-352.

[3] M. El Bachraoui, The number of relatively prime subsets and phi functions for sets {m, m + 1, …, n}, Integers 7 (2007), A 43.

[4] M. El Bachraoui, On the number of subsets of [1, m] relatively prime to n and asymptotic estimates, Integers 8 (2008), A 41.

[5] M. El Bachraoui, On relatively prime subsets and supersets, To appear.

[6] M. Hall, Combinatorial Theory, Second edition, Wiley 1986.

[7] M. B. Nathanson, Affine invariants, relatively prime sets, and a phi function for subsets of {1, 2, …, n}, Integers 7 (2007), A 1.

[8] M. B. Nathanson and B. Orosz, Asymptotic estimates for phi functions for subsets of {m + 1, m + 2, …, n}, Integers 7 (2007), A 54.

[9] J. Riordan, Combinatorial Identities, Wiley, 1968.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11B05, 11B75. Keywords: Combinatorial identities, Möbius function, relatively prime sets, phi functions, Möbius inversion formula.

(Concerned with sequence \underline{A0xxxxx}.)

Received March 2 2010; revised version received August 7 2010. Published in Journal of Integer Sequences, September 3 2010.

Return to Journal of Integer Sequences home page.