Unital Sums of the Möbius and Mertens Functions

Jeffery Kline Madison, WI 53711 USA

                    jeffery.kline@gmail.com

Abstract

We use standard techniques of linear algebra to construct an infinite family of identities that involve finite weighted sums of the Möbius and Mertens functions, where the weights are equal to −1, 0, or 1. In a related manner, we construct, for each positive integer n, an n × n symmetric unimodular matrix, and each matrix is used to express an identity that involves a finite weighted sum of the Möbius function. We establish several results on the spectral decomposition of these matrices.

1 Introduction

The Möbius function is defined as

μ(k) := \begin{cases}1, & if k is squarefree and has an even number of prime factors; \\ −1, & if k is squarefree and has an odd number of prime factors; \\ 0, & otherwise. \end{cases}

Summatory behavior of μ is of great interest, in part due to the close connection that μ has to the distribution of the prime numbers. Indeed, it is known that the Mertens function, which we write as M(n) := ∑_{k≤n} μ(k), satisfies M(n) = o(n), and that this asymptotic bound is equivalent to the prime number theorem.

It is the goal of the first part of this paper to state and prove several summatory identities satisfied by μ and M that we have not found in prior work. These identities are stated in Proposition 1 and Corollary 3 of Section 2.1. In Section 3, we employ similar techniques to construct, for each positive integer n, an n × n symmetric matrix, Q_{n}, having integer entries and determinant 1 that satisfies ∑_{k≤n} Q_{n}(j, k)μ(k) = 0 when j > 1, and the sum equals 1 when j = 1. This is the content of Proposition 6. We also obtain asymptotic bounds on the extremal eigenvalues of Q_{n}. This is the content of Proposition 8. A corollary of these propositions is the asymptotic bound ∑_{i≤n} v_{n}(i)μ(i) ≤ n^{−3/2}C(1 + o(1)), where v_{n} is the normalized dominant eigenvector of Q_{n}, and C is a constant smaller than 3. This is stated in Corollary 9. We conclude with a conjecture about v_{n}.

We now briefly summarize Proposition 1 and Corollary 3 of the next section. For each m, n ≥ 1, we construct (−1, 0, 1)-valued functions, ϵ^{m,n} and E^{m,n}, that satisfy the identities

∑_{k≤n} ϵ^{m,n}(k)μ(k) = 1

and

∑_{k≤n} E^{m,n}(k)M(k) = 1.

Each function ϵ^{m,n} is the result of applying the transpose of Dirichlet convolution by the n-term sequence (1, 1, 1, …, 1) to a particular 4m-periodic function. Each function E^{m,n} is a finite difference operation applied to ϵ^{m,n}. Complete details are presented in Section 2.1. Before proceeding, we state a concise formula for ϵ^{m,n} in the special case m = 1. For all k ≥ 1,

ϵ^{1,n}(k) = ∑_{jk≤n} cos (\frac{π(jk − 1)}{2}) .  (1)

See Section 2.2 for further observations concerning the function ϵ^{1,n}.

Figure 1 displays ϵ^{m,n} for various choices of m and n. Both E^{m,n} and ϵ^{m,n} are 4mperiodic on the interval n/3 < k ≤ n. The behavior of E^{m,n} and ϵ^{m,n} near the origin is more complicated. In general, ϵ^{m,n} and E^{m,n} are sparse when m is large.

The body of literature on the functions μ and M is vast, and many results on sums with the form

∑_{k≤n} w(k)μ(k),

are known. Two well-known examples, both of which may be found in Apostol ([1, Theorem 2.1 and Theorem 3.12]), are

∑_{k|n} μ(k) = \begin{cases}1, & if n = 1; \\ 0, & otherwise, \end{cases}  (2)

Figure 1: Examples of the function ϵ^{m,n}.

and

∑_{k≤n} ⌊\frac{n}{k}⌋ μ(k) = 1.  (3)

This pair of identities is closely related to Proposition 6 of Section 3. The Mertens function is also known to satisfy similar kinds of identities. One example is

∑_{k≤n} M (\frac{n}{k}) = 1.

Lehman [5], Deléglise and Rivat [3] and Benito and Varona [2] have all leveraged this and similar identities to find efficient recursive methods of evaluating M and related functions at large values. We state a similar identity in Section 2.3.

2 The functions ϵ^{m,n} and E^{m,n}

2.1 Notation, statements of the main results, and proofs

The greatest common divisor of positive integers a, b ∈ ℕ is written (a, b). Let D be the matrix

D(i, j) := \begin{cases}1, & if j|i; \\ 0, & otherwise. \end{cases}

The action of this matrix on vectors corresponds to Dirichlet convolution by 1 := (1, 1, 1, …). In matrix notation, where the functions μ and δ := (1, 0, 0, 0, …) are treated as a column vectors, and ∗ denotes Dirichlet convolution,

1 ∗ μ = (∑_{d|k} μ(d) : k ≥ 1) = Dμ = δ.  (4)

We adopt the convention that the smallest index of sequences, vectors and matrices is 1, and not 0. Thus, the leading entry of δ is δ(1) = 1. Let δ_{m} be the column vector consisting of the m leading terms of δ and let

c^{m} := (δ_{2m}, −δ_{2m}, δ_{2m}, −δ_{2m}, …).  (5)

Then c^{m} is supported on integers k ≡ 1 (mod 2m) and c^{m} is 4m-periodic. We indicate the transpose operation using a ′ symbol. The functions of primary interest are now defined.

For each m, n ≥ 1, set

ϵ^{m,n} := D′_{n}c^{m,n},

where D_{n} denotes the nth leading principal submatrix of D, D′_{n} denotes the transpose of D_{n} and c^{m,n} consists of the n leading terms of c^{m}. Written explicitly, for 1 ≤ j ≤ n,

ϵ^{m,n}(j) = ∑_{\begin{matrix}k \\ jk≤n \end{matrix}} c^{m}(jk).  (6)

For example,

ϵ^{1,6} = D′_{6}c^{1,6} = (\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 \\ 0 \\ −1 \\ 0 \\ 1 \\ 0 \end{matrix}) = (\begin{matrix}1 \\ 0 \\ −1 \\ 0 \\ 1 \\ 0 \end{matrix}) .

The following proposition describes basic properties of ϵ^{m,n}. When applied to the above example, items 2 and 4 of Proposition 1 imply that ∥ϵ^{1,6}∥_{∞} ≤ 1 and ∑_{k≤6} ϵ^{1,6}(k)μ(k) = 1, which may be verified by inspection.

Proposition 1. In the established notation,

1. if 1 ≤ k ≤ n and (k, 2m) > 1, then ϵ^{m,n}(k) = 0;

2. ϵ^{m,n} ∈ {−1, 0, 1}^{n};

3. if n ≥ 3m, then ∥ϵ^{m,n}∥_{1} ≥ ⌊n/(3m)⌋ and max{k:ϵ^{m,n}(k) ≠ 0}= 2m⌊(n − 1)/(2m)⌋+1;

4. ∑_{k≤n} ϵ^{m,n}(k)μ(k) = 1.

Proof. For all 1 ≤ j ≤ n,

ϵ^{m,n}(j) = ∑_{\begin{matrix}k \\ jk≤n \end{matrix}} c^{m}(jk)

= ∑_{\begin{matrix}k≤n \\ k≡0 (mod j) \\ k≡1 (mod 4m) \end{matrix}} 1 − ∑_{\begin{matrix}k≤n \\ k≡0 (mod j) \\ k≡2m+1 (mod 4m) \end{matrix}} 1

= |A^{j}| − |B^{j}| ,

where

A^{j} := {jk ≤ n : k ∈ ℕ, jk ≡ 1 (mod 4m)}

and

B^{j} := {jk ≤ n : k ∈ ℕ, jk ≡ 2m + 1 (mod 4m)} .

To see item 1 of the proposition, observe that neither jk ≡ 1 (mod 4m) nor jk ≡ 2m + 1 (mod 4m) has an integer solution when (j, 2m) > 1. Consequently, ϵ^{m,n}(j) = |A^{j}| − |B^{j}| = 0 − 0 = 0 when (j, 2m) > 1.

For item 2, observe that either ϵ^{m,n}(j) = 0, or else (j, 2m) = 1 and

ϵ^{m,n}(j) = |A^{j}| − |B^{j}| = ∑_{\begin{matrix}k≤n/j \\ k≡j^{∗} (mod 4m) \end{matrix}} 1 − ∑_{\begin{matrix}k≤n/j \\ k≡(2m+1)j^{∗} (mod 4m) \end{matrix}} 1,

where j^{∗} is the unique integer satisfying both 1 ≤ j^{∗} ≤ 4m − 1 and jj^{∗} ≡ 1 (mod 4m). Then since j^{∗} is necessarily odd, (2m + 1)j^{∗} ≡ 2m + j^{∗} (mod 4m). Therefore,

ϵ^{m,n}(j) = ∑_{\begin{matrix}k \\ 0<j^{∗}+4mk≤n/j \end{matrix}} 1 − ∑_{\begin{matrix}k \\ 0<2m+j^{∗}+4mk≤n/j \end{matrix}} 1

= ∑_{0<2k+ \frac{j^{∗}}{2m} ≤ \frac{n/j}{2m}} 1 − ∑_{0<(2k+1)+ \frac{j^{∗}}{4m} ≤ \frac{n/j}{2m}} 1.

Hence,

ϵ^{m,n}(j) = ∑_{− \frac{j^{∗}}{2m} <v≤ \frac{n/j}{2m} − \frac{j^{∗}}{2m}} (−1)^{v} .  (7)

Consecutive terms in the last expression sum to 0. Since each individual term in the expression is either −1 or +1, the total sum is either −1, 0, or 1.

We now show the third claim. Assume n ≥ k > n/3. From Eq. (6), and since c^{m}(k) = 0 whenever k ≢ 1 (mod 2m),

ϵ^{m,n}(k) = c^{m}(k) + c^{m}(2k) = c^{m}(k).  (8)

Consequently,

∥ϵ^{m,n}∥_{1} ≥ ∑_{n/3<j≤n} |ϵ^{m,n}(j)| = ∑_{n/3<j≤n} |c^{m}(j)| = ∑_{\begin{matrix}n/3<j≤n \\ j≡1 (mod 2m) \end{matrix}} 1 = ∑_{n/3<1+2ml≤n} 1 = ∑_{\frac{n−3}{6m} <l≤ \frac{3n−3}{6m}} 1.

Since a < b implies |(b − a) − ∑_{a<j≤b} 1| < 1, it follows that

∥ϵ^{m,n}∥_{1} > \frac{n}{3m} − 1.

Since ∥ϵ^{m,n}∥_{1} is integer-valued, the first statement of the third item follows. The second statement of this item follows from the definition of c^{m} and Eq. (8).

To see the last claim, observe that Eq. (4) implies D_{n}μ_{n} = δ_{n}, where μ_{n} represents the leading n terms of μ. Then, by applying the definitions of c^{m,n} and ϵ^{m,n}, it follows that

∑_{1≤k≤n} ϵ^{m,n}(k)μ(k) = μ′_{n}ϵ^{m,n} = μ′_{n}D′_{n}c^{m,n} = (D_{n}μ_{n})′ c^{m,n} = δ′_{n}c^{m,n} = c^{m,n}(1) = 1.

Equation (1) of Section 1 follows from the above observations. To see this, let d^{k,n} denote column k of D_{n} and note that d^{k,n} is supported on integers jk ≤ n. Next, observe that

c^{1,n} = (1, 0, −1, 0, …) = (cos (\frac{π(k − 1)}{2}) : 1 ≤ k ≤ n) .

Hence,

ϵ^{1,n}(k) = (d^{k,n})′ c^{1,n} = ∑_{jk≤n} cos (\frac{π(jk − 1)}{2}),

which shows the claim.

Corollary 2. Let m, n, ∈ ℕ. For each positive integer k ≤ n set

ω^{m,n}(k) := \begin{cases}ϵ^{m,n}(k), & if k is odd; \\ ϵ^{m,⌊n/2⌋}(k/2), & if k is even. \end{cases}

Then ω^{m,n} ∈ {−1, 0, 1}^{n}. If n > 1, then ∑_{k≤n} ω^{m,n}(k)μ(k) = 0.

Proof. By Proposition 1 item 1, for all m, n ≥ 1, the function ϵ^{m,n} is supported on odd integers. Since μ(2k) = −μ(k) when k is odd, it follows by Proposition 1 item 4 that

∑_{k≤n} ω^{m,n}(k)μ(k) = ∑_{2k+1≤n} ϵ^{m,n}(2k + 1)μ(2k + 1) + ∑_{2k≤n} ϵ^{m,⌊n/2⌋}(k)μ(2k) = 1 − 1 = 0.

Our next aim is to develop analogous results for the summatory function of μ, i.e., the Mertens function, M. Let S_{n} ∈ {0, 1}^{n×n} denote the lower-triangular matrix with S_{n}(i, j) = 1 whenever j ≤ i. Then S_{n} is the matrix representation that corresponds to the operation of cumulative summation applied to n-vectors. Let M_{n} := (M(1), …, M(n)). Then M_{n} = S_{n}μ_{n}. Let Δ_{n} := (S′_{n})^{−1}. Then

Δ_{n} = (\begin{matrix}1 & −1 \\ & 1 & −1 \\ & & 1 & −1 \\ & & & ... & −1 \\ & & & & 1 \end{matrix}) ,  (9)

which is the matrix representation of a difference operation applied to n-vectors. Set

E^{m,n} := Δ_{n} ϵ^{m,n}.

The next corollary combines the above observations into a result that parallels Proposition 1.

Corollary 3. In the established notation,

1. E^{m,n} ∈ {−1, 0, 1}^{n};

2. if n ≥ 3m, then ∥E^{m,n}∥_{1} ≥ 2 ⌊n/(3m)⌋ − 1;

3. ∑_{k≤n} M(k)E^{m,n}(k) = 1.

Proof. Since ϵ^{m,n}(2k) = 0 for all k ≥ 1, the difference of adjacent entries of ϵ^{m,n} is −1, 0 or 1. This shows the first claim.

For 1 ≤ k < n,

|E^{m,n}(k)| = |ϵ^{m,n}(k)| + |ϵ^{m,n}(k + 1)| .

This fact, when combined with items 2 and 3 of Proposition 1 implies

∥E^{m,n}∥_{1} = ∑_{k<n} (|ϵ^{m,n}(k)| + |ϵ^{m,n}(k + 1)|) + |ϵ^{m,n}(n)|

= ∥ϵ^{m,n}∥_{1} + ∥ϵ^{m,n}∥_{1} − |ϵ^{m,n}(1)| ≥ 2 ⌊\frac{n}{3m}⌋ − 1.

This shows the second claim.

Finally, apply Proposition 1 and the respective definitions to find

M′_{n}E^{m,n} = (S_{n}μ_{n})′ Δ_{n} ϵ^{m,n} = μ′_{n}S′_{n} (S′_{n})^{−1} ϵ^{m,n} = μ′_{n}ϵ^{m,n} = 1.

2.2 Remarks on Eq. (1)

It follows from (1), that for all positive integers n and k ∈ ℕ satisfying k ≤ n, the value of ϵ^{1,n}(k) equals the real part of the sum, ∑_{1≤j≤⌊n/k⌋} i^{jk−1}, where i := \sqrt{−1}. This leads to a closed-form expression for ϵ^{1,n}(k). When k is even, it follows by Proposition 1 item 1 that ϵ^{1,n}(k) = 0. Now assume k is odd. One has

∑_{1≤j≤⌊n/k⌋} i^{jk−1} = i^{k−1} \frac{1 − i^{k⌊n/k⌋}}{1 − i^{k}} = (−1)^{⌊k/2⌋} \frac{(1 − i^{k⌊n/k⌋})(1 + i^{k})}{2}.

Since i^{k⌊n/k⌋} = (i^{⌊n/k⌋})^{k}, the above expression vanishes when ⌊n/k⌋ ≡ 0 (mod 4). Next, when ⌊n/k⌋ is odd, and since k is assumed odd, the real part of the above expression equals (−1)^{⌊k/2⌋} (1 − i^{k(⌊n/k⌋+1)}) /2, which vanishes when ⌊n/k⌋ ≡ −1 (mod 4). When ⌊n/k⌋ ≡ 1 (mod 4), one has i^{⌊n/k⌋} = i so that the right-hand side of the above sum reduces to

(−1)^{⌊k/2⌋} \frac{(1 − i^{k})(1 + i^{k})}{2} = (−1)^{⌊k/2⌋} \frac{1 − i^{2k}}{2} = (−1)^{⌊k/2⌋}.

Finally, when ⌊n/k⌋ ≡ 2 (mod 4), i^{⌊n/k⌋} = −1, and (recalling that k is assumed odd) the right-hand side of the above sum reduces to

(−1)^{⌊k/2⌋} \frac{(1 − (−1)^{k})(1 + i^{k})}{2} = (−1)^{⌊k/2⌋}(1 + i^{k}),

the real part of which is (−1)^{⌊k/2⌋}.

Therefore, for all positive integers n and k that satisfy k ≤ n,

ϵ^{1,n}(k) = \begin{cases}0, & if ⌊n/k⌋ ≡ r (mod 4) for some r ∈ \{0, −1\}; \\ sin (kπ/2) , & otherwise. \end{cases}  (10)

When 1 ≤ k ≤ n, an explicit formula for ϵ^{m,n}(k) is possible to derive. The case where (k, 2m) > 1 is discussed in Proposition 1 item 1, so we now assume (k, 2m) = 1. Let k^{∗} be any integer satisfying kk^{∗} = 1 (mod 4m). By Eq. (7), one has

ϵ^{m,n}(k) = ∑_{\begin{matrix}j \\ \frac{−k^{∗}}{2m} <2j≤ \frac{⌊n/k⌋−k^{∗}}{2m} \end{matrix}} 1 − ∑_{\begin{matrix}j \\ \frac{−k^{∗}}{2m} <2j+1≤ \frac{⌊n/k⌋−k^{∗}}{2m} \end{matrix}} 1

= ∑_{\begin{matrix}j \\ \frac{−k^{∗}}{4m} <j≤ \frac{⌊n/k⌋−k^{∗}}{4m} \end{matrix}} 1 − ∑_{\begin{matrix}j \\ \frac{−k^{∗}}{4m} − \frac{1}{2} <j≤ \frac{⌊n/k⌋−k^{∗}}{4m} − \frac{1}{2} \end{matrix}} 1

= (⌊\frac{⌊n/k⌋ − k^{∗}}{4m} ⌋ − ⌊\frac{−k^{∗}}{4m} ⌋) − (⌊\frac{⌊n/k⌋ − k^{∗}}{4m} − \frac{1}{2}⌋ − ⌊\frac{−k^{∗}}{4m} − \frac{1}{2}⌋)

= (⌊\frac{⌊n/k⌋ − k^{∗}}{4m} ⌋ − ⌊\frac{⌊n/k⌋ − k^{∗}}{4m} − \frac{1}{2}⌋) − (⌊\frac{−k^{∗}}{4m} ⌋ − ⌊\frac{−k^{∗}}{4m} − \frac{1}{2}⌋)

= ∑_{\begin{matrix}j \\ \frac{⌊n/k⌋−k^{∗}}{4m} − \frac{1}{2} <j≤ \frac{⌊n/k⌋−k^{∗}}{4m} \end{matrix}} 1 − ∑_{\begin{matrix}j \\ \frac{−k^{∗}}{4m} − \frac{1}{2} <j≤ \frac{−k^{∗}}{4m} \end{matrix}} 1.

Then, letting {x} := x − ⌊x⌋ denote the fractional part of x,

ϵ^{m,n}(k) = \begin{cases}1, & if (k, 2m) = 1, \{\frac{k^{∗}}{4m}\} ∈ (0, \frac{1}{2}] and \{\frac{k^{∗}−⌊n/k⌋}{4m}\} ∉ (0, \frac{1}{2}]; \\ −1, & if (k, 2m) = 1, \{\frac{k^{∗}}{4m}\} ∉ (0, \frac{1}{2}] and \{\frac{k^{∗}−⌊n/k⌋}{4m}\} ∈ (0, \frac{1}{2}]; \\ 0, & otherwise. \end{cases}

2.3 An identity involving a sparse sum

Benito and Varona ([2, Theorem 9]) establish the identity,

2M(n) + 3 = g(n, 1) + ∑_{3≤a≤n−1} h(a) (M (\frac{n}{a}) − M (\frac{n}{a + 1})) ,

where g(x, 1) and h(x) depend on the value of x (mod 6), and the values of both g and h are tabulated. The utility of this formula is that it leads to an efficient and recursive means of evaluating M. In Proposition 4 of this section, we establish a similar identity.

Before stating the identity, we introduce notation. The unique non-principal Dirichlet character mod 4 is

χ(k) = \begin{cases}1, & if k ≡ 1 (mod 4); \\ −1, & if k ≡ −1 (mod 4); \\ 0, & otherwise. \end{cases}

The sine-factor in the non-vanishing case of (10) satisfies sin (kπ/2) = χ(k) for all integers k. Next, we define

M(x, χ) := ∑_{k≤x} μ(k)χ(k),

and set

η(k) := \begin{cases}1, & if k ≡ r (mod 4) for some r ∈ \{1, 2\}; \\ 0, & otherwise. \end{cases}

We are now ready to state the identity.

Proposition 4. For all n ≥ 1,

∑_{1≤k≤n} η(k) (M (\frac{n}{k}, χ) − M (\frac{n}{k + 1}, χ)) = 1.

Proof. One has

∑_{1≤k≤n} η(k) (M (\frac{n}{k}, χ) − M (\frac{n}{k + 1}, χ)) = ∑_{\begin{matrix}k,j \\ k≡r (mod 4),r∈\{1,2\} \\ \frac{n}{k+1} <j≤ \frac{n}{k} \end{matrix}} μ(j)χ(j)

= ∑_{4l+3>⌊n/j⌋≥4l+1} μ(j)χ(j)

= ∑_{j} ϵ^{1,n}(j)μ(j)

= 1,

where the third equality follows from Eq. (10) and the definition of χ, and the last equality from Proposition 1 item 4.

3 A family of unimodular matrices

The classical identities expressed in Eq. (2) and Eq. (3) of the introduction are equivalent. Indeed, for any integer n ∈ ℕ, Eq. (2) states D_{n}μ_{n} = δ_{n}. Multiplication of both sides by S_{n} yields, S_{n}D_{n}μ_{n} = S_{n}δ_{n} = 1_{n}, which is (3). Equivalence follows by observing that S_{n} is invertible. This observation generalizes to yield the infinite family of identities, S_{n}^{k}D_{n}μ_{n} = S_{n}^{k}δ_{n}, where k, n ∈ ℕ are arbitrary. The next proposition describes a closely-related family of identities. We first state a lemma that generalizes the identity, ∑_{d|n} ϕ(d) = n, where ϕ is Euler’s totient function.

Lemma 5. For positive j, k ∈ ℕ, write ϕ^{k}(j) := ∑_{ℓ≤j/k, (ℓ,j)=1} 1. Let R_{n} := D_{n}^{−1}S_{n}D_{n}. Then for all 1 ≤ j, k ≤ n, R_{n}(j, k) = ϕ^{k}(j).

Proof. Column k of S_{n}D_{n} equals (⌊1/k⌋ , ⌊2/k⌋ , …, ⌊n/k⌋). Let ϕ_{n}^{k} denote the column vector consisting of the n leading terms of ϕ^{k}. Our aim is to demonstrate that

(D_{n}ϕ_{n}^{k})(j) = ∑_{d|j} ϕ^{k}(d) = ⌊j/k⌋  (11)

holds when 1 ≤ j, k ≤ n. Once this has been shown, one arrives at (D_{n}^{−1}S_{n}D_{n})(j, k) = ϕ^{k}(j) by applying D_{n}^{−1} to both sides. Fix j and k. For each integer d with d|j, define the set

S_{d} := {s ∈ ℕ : 1 ≤ s ≤ j/k and (s, j) = j/d} .

Then S_{d} consists of all integers with the form (t)(j/d), where 1 ≤ t ≤ d/k and (t, d) = 1. Then |S_{d}| = ϕ^{k}(d). Each integer between 1 and ⌊j/k⌋ belongs to a unique S_{d}. Summing over d, one has (11).

Proposition 6. For positive n ∈ ℕ, set Q_{n} := R′_{n}R_{n}. Then Q_{n} is a positive definite matrix, both Q_{n} and (Q_{n})^{−1} ∈ ℤ^{n×n}, and det Q_{n} = det (Q_{n})^{−1} = 1. Additionally,

1. Q_{n}μ_{n} = δ_{n};

2. Q_{n}(i, j) > 0 for all 1 ≤ i, j ≤ n;

3. Q_{n}(1, 1) = ∑_{1≤k≤n} ϕ(k)^{2}.

Proof. Recall that D is the matrix representation of Dirichlet convolution by 1, and the inverse operation is Dirichlet convolution by μ. In particular, the matrix D_{n}^{−1} is (−1, 0, 1)- valued. Since each of D_{n}, D_{n}^{−1} and S_{n} live in ℤ^{n×n}, it follows that Q_{n} ∈ ℤ^{n×n}.

Also, each of D_{n}, D_{n}^{−1} and S_{n} are lower-triangular with 1 along the main diagonal, so each has determinant equal to 1, as do their transposes. Since det is multiplicative, det Q_{n} = 1, from which it follows (by Cramer’s rule) that (Q_{n})^{−1} ∈ ℤ^{n×n}. Additionally, since for all x ∈ ℝ^{n} \ {0} one has x′Q_{n}x = ∥(D_{n}^{−1}S_{n}D_{n})x∥^{2} ≥ 0, Q_{n} is nonnegative definite. But det Q_{n} = 1 > 0, so it has full rank. In particular, x′Q_{n}x > 0, which implies, since x ≠ 0 is arbitrary, that Q_{n} is positive definite.

We now establish item 1 of the proposition’s statement. The first column of S_{n} equals the first column of D_{n}, both of which equal 1_{n}. Thus, recalling Eq. (4),

R_{n}μ_{n} = D_{n}^{−1}S_{n}D_{n}μ_{n} = D_{n}^{−1}S_{n}δ_{n} = D_{n}^{−1}1_{n} = δ_{n}.

The first column of each of the upper-triangular matrices (D_{n}^{−1})′, D′_{n} and S′_{n} equals δ_{n}, so

Q_{n}μ_{n} = R′_{n}R_{n}μ_{n} = D′_{n}S′_{n} (D_{n}^{−1})′ δ_{n} = D′_{n}S′_{n}δ_{n} = D′_{n}δ_{n} = δ_{n}.

For the proof of item 2, note that ϕ^{k} of Lemma 5 satisfies ϕ^{k}(l) > 0 whenever l ≥ k. Therefore Q_{n}(j, k) = ∑_{l≤n} ϕ^{j}(l)ϕ^{k}(l) ≥ ϕ^{j}(n)ϕ^{k}(n) > 0 when 1 ≤ j, k ≤ n. Item 3 is also immediate from Lemma 5. Indeed, Q_{n}(1, 1) = ∑_{j≤n} (ϕ^{1}(j))^{2} = ∑_{j≤n}(ϕ(j))^{2}.

In the discussion below, it may be helpful to have a reference example of R_{n}, Q_{n} and Q_{n}^{−1}:

R_{7} = (\begin{matrix}1 \\ 1 & 1 \\ 2 & 1 & 1 \\ 2 & 1 & 1 & 1 \\ 4 & 2 & 1 & 1 & 1 \\ 2 & 1 & 1 & 1 & 1 & 1 \\ 6 & 3 & 2 & 1 & 1 & 1 & 1 \end{matrix}) , Q_{7} = (\begin{matrix}66 & 33 & 22 & 14 & 12 & 8 & 6 \\ 33 & 17 & 11 & 7 & 6 & 4 & 3 \\ 22 & 11 & 8 & 5 & 4 & 3 & 2 \\ 14 & 7 & 5 & 4 & 3 & 2 & 1 \\ 12 & 6 & 4 & 3 & 3 & 2 & 1 \\ 8 & 4 & 3 & 2 & 2 & 2 & 1 \\ 6 & 3 & 2 & 1 & 1 & 1 & 1 \end{matrix}) ,

and

(Q_{7})^{−1} = (\begin{matrix}1 & −1 & −1 & & −1 & 1 & −1 \\ −1 & 2 \\ −1 & & 3 & −1 & 2 & −2 & 1 \\ & & −1 & 2 & −1 & & 1 \\ −1 & & 2 & −1 & 4 & −3 & 2 \\ 1 & & −2 & & −3 & 4 & −3 \\ −1 & & 1 & 1 & 2 & −3 & 5 \end{matrix}) .

Item 1 of the proposition states that μ_{n} is the first column of (Q_{n})^{−1}. The second column of (Q_{n})^{−1} has a far simpler form, namely q := (−1, 2, 0, 0, 0, …, 0). To see this, observe that R_{n}(2, 1) = R_{n}(2, 2) = 1. When j > 2, R_{n}(j, 2) = ⌊R_{n}(j, 1)/2⌋, and since R_{n}(j, 1) = ϕ^{1}(j) = ϕ(j) is even, ⌊R_{n}(j, 1)/2⌋ = R_{n}(j, 1)/2. Noting that R′_{n} is uppertriangular and R(1, 1) = 1, one has

R′_{n}R_{n}q = R′_{n} (−1 ; 1 ; 0 ; ⋮ ; 0) = (0 1 0 ⋮ 0) .

Since Q_{n} is Hermitian, the eigenvalues of Q_{n} are real. Let λ_{1} ≤ λ_{2} ≤ … ≤ λ_{n} denote the eigenvalues of Q_{n}. By item 2, we may invoke the Perron-Frobenius theorem to conclude that λ_{n} is simple and that the eigenvector associated with λ_{n}, denoted v_{n}, satisfies v_{n}(j) > 0 for 1 ≤ j ≤ n.

The following two propositions concern the spectrum of Q_{n}. Table 1 illustrates these propositions.

Proposition 7. The eigenvalues of Q_{n} interlace the eigenvalues of Q_{n+1}. That is, if λ_{i} is the ith eigenvalue of Q_{n} and γ_{i} the ith eigenvalue of Q_{n+1}, then

γ_{1} ≤ λ_{1} ≤ γ_{2} ≤ ⋯ ≤ γ_{n} ≤ λ_{n} ≤ γ_{n+1}.

Table 1: Eigenvalue λ_{i} of Q_{n}.
i n = 999  n = 1000  n = 1001
1 4.588 × 10^{−4} 4.580 × 10^{−4} 4.573 × 10^{−4}
2 6.887 × 10^{−4} 6.879 × 10^{−4} 6.859 × 10^{−4}
⋯
n − 1 4.458 × 10^{4} 4.471 × 10^{4} 4.487 × 10^{4}
n 2.344 × 10^{8} 2.346 × 10^{8} 2.355 × 10^{8}

Proof. We claim that (Q_{n})^{−1} is a leading principal submatrix of (Q_{n+1})^{−1}. Assume, for the moment, that this has been established. Then by Cauchy’s interlacing theorem, the eigenvalues of (Q_{n})^{−1} interlace those of (Q_{n+1})^{−1}. That is, letting λ_{i}^{−1} and γ_{i}^{−1} denote the eigenvalues of (Q_{n})^{−1} and (Q_{n+1})^{−1}, respectively,

γ_{n+1}^{−1} ≤ λ_{n}^{−1} ≤ γ_{n}^{−1} ≤ ⋯ ≤ γ_{2}^{−1} ≤ λ_{1}^{−1} ≤ γ_{1}^{−1}.

Since all quantities in this expression are positive scalars, the proposition follows.

We now show that (Q_{n})^{−1} is a leading principal submatrix of (Q_{n+1})^{−1}. From the definition of Q_{n}, we have that

Q_{n}^{−1} = (R′_{n}R_{n})^{−1} = (R_{n})^{−1}(R′_{n})^{−1} = (R_{n})^{−1}(R_{n}^{−1})′.  (12)

Recall from Lemma 5 the entrywise equality, R_{n}(j, k) = ϕ^{k}(j). Since the right-hand side does not depend on n, the (j, k) entry of R_{n} does not depend on n. Therefore, R_{n} is a leading principal submatrix of R_{m} whenever m ≥ n. Since R_{n} is lower-triangular, it follows (by consideration of block matrix inversion, for example) that (R_{n})^{−1} is a leading principal submatrix of (R_{m})^{−1} for all m ≥ n. This also shows that (R_{n}^{−1})′ is a leading principal submatrix of (R_{m}^{−1})′ whenever m ≥ n.

For 1 ≤ j ≤ n, define r^{j} as the jth column of (R_{n+1}^{−1})′. Since (R_{n}^{−1})′ is a leading principal submatrix of (R_{n+1}^{−1})′, the first n entries of r^{j} agree with the jth column of (R_{n}^{−1})′. This, combined with Eq. (12) and the fact that R_{n}^{−1} is lower-triangular, implies that the jth column of (Q_{n})^{−1} equals the column vector that is comprised of the first n entries of (R_{n+1})^{−1}r^{j}. Eq. (12) also implies that the jth column of (Q_{n+1})^{−1} equals (R_{n+1})^{−1}r^{j}. This applies to all 1 ≤ j ≤ n, so it follows that (Q_{n})^{−1} is a leading principal submatrix of (Q_{n+1})^{−1}.

The next proposition establishes bounds on the extremal eigenvalues of Q_{n}.

Proposition 8. Let λ_{n} denote the dominant eigenvalue of Q_{n}. Then

(c + o(1)) n^{3} ≤ λ_{n} ≤ \frac{π^{2}}{18}n^{3} + O(n^{2}),

where c is a constant that is approximately equal to 0.1427. Let λ_{1} denote the smallest eigenvalue of Q_{n}. Then

λ_{1} ≤ \frac{π^{2}}{6} n^{−1} + O (n^{−3/2}).

Proof. We first show the lower bound on λ_{n}. Since λ_{n} is the dominant eigenvalue of Q_{n}, applying item 3 of Proposition 6 one has,

λ_{n} ≥ \frac{δ′_{n}Q_{n}δ_{n}}{∥δ_{n}∥^{2}} = Q_{n}(1, 1) = ∑_{k≤n} (ϕ(k))^{2} .

We estimate the right-hand sum by applying the Wiener-Ikehara Theorem to the function H(s) := ∑_{k≥1} ϕ(k)^{2}k^{−s}. A comment associated with the sequence \underline{A127473} asserts that H(s) = ζ(s−2) ∏_{p prime} (1 − 2p^{1−s} + p^{−s}). Since this is a known fact, but no proof is provided in the citation, we sketch a proof here. To start, if n = ∏_{p} p^{r}, then ϕ(n) = ∏_{p|n} p^{r} − p^{r−1}. Since n ↦ ϕ(n)n^{−s} is a multiplicative function, one has the Euler product,

H(s) = ∏_{p prime} (1 + ∑_{r≥1} \frac{(p^{r} − p^{r−1})^{2}}{p^{rs}} )

= ∏_{p prime} (1 + ∑_{r≥1} \frac{p^{2r}}{p^{rs}} − 2\frac{p^{2r−1}}{p^{rs}} + \frac{p^{2r−2}}{p^{rs}} )

= ∏_{p prime} (1 + (1 − \frac{2}{p} + \frac{1}{p^{2}} ) \frac{p^{2−s}}{1 − p^{2−s}} )

= ∏_{p prime} (1 − p^{2−s} + p^{2−s} − 2p^{1−s} + p^{−s}) (\frac{1}{1 − p^{2−s}} )

= ζ(s − 2) ∏_{p prime} (1 − 2p^{1−s} + p^{−s}) .

At s = 3, the infinite product converges and ζ(s − 2) has a simple pole with residue equal to 1. Therefore, H has a simple pole at s = 3, with residue equal to the product of the right-hand side. We now apply the Wiener-Ikehara Theorem to conclude that

∑_{k≤n} (ϕ(x))^{2} ∼ \frac{n^{3}}{3} ∏_{p prime} (1 − 2p^{−2} + p^{−3}) = (\frac{n^{3}}{3} ) (0.42824950 …)

We now show the upper bound on λ_{n}. Indeed,

Trace (Q_{n}) = ∑_{k=1}^{n} Q_{n}(k, k)

= ∑_{k=1}^{n} ∑_{j=1}^{n} (ϕ^{k}(j))^{2}

≤ ∑_{k=1}^{∞} ∑_{j=1}^{n} (\frac{j}{k} )^{2}

= \frac{n(n + 1)(2n + 1)}{6} ∑_{k=1}^{∞} k^{−2}

= \frac{π^{2}}{18}n^{3} + O(n^{2}),

where we have used the elementary identity ∑_{j=1}^{n} j^{2} = n(n+1)(2n+1)/6 and Euler’s identity ∑_{i=1}^{∞} i^{−2} = π^{2}/6. Finally, recall that Q_{n} is positive definite and Trace (Q_{n}) = ∑_{i=1}^{n} λ_{i} ≥ λ_{n}.

We now show the upper bound on λ_{1}. We have by item 1 of Proposition 6 that

\frac{μ′_{n}Q_{n}μ_{n}}{∥μ_{n}∥^{2}} = \frac{μ′_{n}δ_{n}}{∥μ_{n}∥^{2}} = \frac{μ(1)}{∑_{k≤n} μ_{n}(k)^{2}} = \frac{1}{∑_{k≤n} |μ_{n}(k)|} ≥ λ_{1}.

The penultimate expression is the reciprocal of the number of squarefree integers not exceeding n. The desired bound is a consequence of this, combined with an application of Gegenbauer’s estimate [4, p. 47],

∑_{k≤n} |μ_{n}(k)| = \frac{6}{π^{2}} n + O(n^{1/2}).

That is,

λ_{1} ≤ (∑_{k≤n} |μ_{n}(k)|)^{−1} = \frac{π^{2}}{6} n^{−1} + O(n^{−3/2}).

Corollary 9. In the established notation, |v′_{n}μ_{n}| ≤ n^{−3/2}C(1 + o(1)), where the constant C is approximately 2.6467.

Proof. For 1 ≤ i ≤ n, let v_{i} satisfy Q_{n}v_{i} = λ_{i}v_{i}. We may assume that v′_{i}v_{j} = 0 whenever i ≠ j, that v′_{i}v_{i} = 1 for all 1 ≤ i ≤ n and that the space spanned by {v_{i} : 1 ≤ i ≤ n} has dimension n. Then μ_{n} = ∑_{1≤i≤n}(v′_{i}μ_{n})v_{i}. By item 1 of Proposition 6, μ′_{n}Q_{n}μ_{n} = 1. Since λ_{i} > 0 for all i,

1 = μ′_{n}Q_{n}μ_{n} = ∑_{1≤i≤n} λ_{i} |v′_{i}μ_{n}|^{2} ≥ λ_{n} |v′_{n}μ_{n}|^{2} ≥ n^{3}(c + o(1)) |v′_{n}μ_{n}|^{2} ,

where the last inequality is from Proposition 8. The constant C in the Corollary statement is c^{−1/2}.

We conclude with a conjecture. Recall that the dominant eigenvector of Q_{n}, which is denoted v_{n}, was shown to satisfy v_{n}(j) > 0, for all 1 ≤ j ≤ n. Assume we have normalized v_{n}, so that ∥v_{n}∥_{2} = 1. Let h(k) := k^{−1} and let h_{n} denote the nth truncation of h. Then

lim_{n→∞} n ∥h_{n} − (v′_{n}h_{n})v_{n}∥_{∞} = 1. (Conjecture)

The sequence h_{n} arises in combination with μ_{n} in the asymptotic estimate,

h′_{n}μ_{n} = ∑_{k=1}^{n} \frac{μ(k)}{k} = o(1),

which is equivalent to the prime number theorem [6].

4 Acknowledgments

We thank the anonymous referees for the extraordinary, insightful comments. One anonymous referee contributed most of Section 2.2, all of Section 2.3, strengthened the main theorem of section 2.1, strengthened the bounds in Proposition 8, and contributed arguments that greatly improved many proofs. Computing resources for this research were provided by American Family Insurance.

References

[1] Tom M. Apostol, Introduction to Analytic Number Theory, Undergrad. Texts Math., Springer, 1998.

[2] Manuel Benito and Juan Varona, Recursive formulas related to the summation of the Möbius function, Open Math. J. 1 (2008), 25–34.

[3] Marc Deléglise and Joël Rivat, Computing the summation of the Möbius function, Exp. Math. 5 (1996), 291–295.

[4] Leopold Gegenbauer, Asymptotisch Gesetze der Zahlentheorie, Denkschriften der Akad. Wiss. zu Wien 49 (1885), 37–80.

[5] R. Sherman Lehman, On Liouville’s function, Math. Comp. 14 (1960), 311–320.

[6] Harold Shapiro, Some assertions equivalent to the prime number theorem for arithmetic progressions, Comm. Pure Appl. Math. 2 (1949), 293–308.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11K31. Keywords: Möbius function, Mertens function, Dirichlet convolution, (−1, 0, 1)-valued function, Hermitian matrix.

(Concerned with sequences \underline{A002321}, \underline{A008683}, \underline{A056594}, \underline{A127473}, and \underline{A327580}.)

Received September 21 2019; revised versions received September 22 2019; December 29 2019; July 7 2020. Published in Journal of Integer Sequences, August 7 2020.

Return to Journal of Integer Sequences home page.