Séminaire Lotharingien de Combinatoire 52 (2004), Article B52a

Addition of ±1 : Application to Arithmetic

Alain Lascoux^{1} CNRS, Institut Gaspard Monge, Université de Marne-la-Vallée 77454 Marne-la-Vallée Cedex, France and Center for Combinatorics, LPMC Nankai University, Tianjin 300071, P.R. China Alain.Lascoux@univ-mlv.fr

Abstract We show that some classical identities about multiplicative functions, and the Riemann zeta-function, may conveniently be interpreted in terms of the addition of ±1 to some alphabets.

Résumé Nous montrons que des identités classiques concernant des fonctions multiplicatives de la théorie des nombres, et la fonction zeta de Riemann, s’interprètent commodément en terme de l’opération : “Ajouter ±1 à un alphabet”.

1 Introduction

In good courses of classical analysis, like the one of Jean-Yves Thibon for the Marne-La-Vallée students, one finds exercises of the following type:

Exercise 99. Show the following two identities:

ζ(s)^{3}/ζ(2s) = ∑ τ(n^{2}) n^{−s}
ζ(s)^{4}/ζ(2s) = ∑ τ(n)^{2} n^{−s} ,

1Partially supported by the EC’s IHRP Program, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272.

where ζ(s) is the Riemann zeta function, and τ(n) is the number of divisors of n.

Such identities seem to be totally out of reach of my own students^{2}, who have learnt from me only symmetric functions, division by 1, and divided differences.

I shall however show that addition of ±1 is sufficient to generate such identities, and the link with symmetric function theory will be provided by the notion of multiplicative function:

f : ℕ → commutative ring is multiplicative if and only if f(mn) = f(m)f(n) whenever m, n are relatively prime.

Equivalently, the prime decomposition of n determines the value of f(n):

n = ∏_{p prime} p^{k_{p}} ⇒ f(n) = ∏_{p prime} f (p^{k_{p}}) .

But instead of considering the sequence

[f(p^{0}), f(p^{1}), f(p^{2}), f(p^{3}), …] ,

or the generating function ∑_{k=0}^{∞} f(p^{k})z^{k}, as does Lagrange, Symmetric Function Theory [5] tells us that we better introduce an alphabet 𝔸_{p}, such that, for k ∈ ℕ, f(p^{k}) is the k-th complete function in this alphabet, denoted by S^{k}(𝔸_{p}), i.e., such that

∑_{k=0}^{∞} f(p^{k})z^{k} = σ_{z}(𝔸_{p}) := ∑_{k=0}^{∞} z^{k}S^{k}(𝔸_{p}) = ∏_{a∈𝔸_{p}}(1^{−}za)^{−1}.

In other words, each generating function is formally factorized and gives rise to an alphabet.

In summary, a multiplicative function is determined by a collection of alphabets A = {𝔸_{p}, p prime}. In this sutation, this multiplicative function will be denoted by μ_{A}(.).

It may be appropriate, before going any further, to recall a few facts about symmetric functions. An alphabet 𝔸 = {a_{1}, a_{2}, …} is written as the sum of its elements: 𝔸 = a_{1} + a_{2} + ⋯, and the generating function of complete functions in 𝔸 is

σ_{z}(𝔸) = ∑_{k=0}^{∞} z^{k}S^{k}(𝔸) = ∏_{i}(1 − za_{i})^{−1} .

2and also of me, because J.-Y. Thibon does not write the solution.

Adding a letter x to 𝔸 is denoted by 𝔸 → 𝔸 + x. Adding three copies of the letter 1 is denoted by 𝔸 → 𝔸 + 3.

More generally, given alphabets 𝔸, 𝔹, and complex numbers k, r, the generating function σ_{z}(k𝔸 ± 𝔹 + rx) is equal to

σ_{z}(k𝔸 ± 𝔹 + rx) = ∏_{α∈𝔸}(1^{−}zα)^{−k} ∏_{β∈𝔹}(1^{−}zβ)^{∓1}(1 − zx)^{−r} .  (1)

We may need to specialize a letter to 3, but this must not be confused with taking three copies of 1. To allow nevertheless specializing a letter to a complex number r inside a symmetric function, without introducing intermediate variables, we write r for this specialization. Boxes have to be treated as single variables.

In other words, given a letter x, and complex numbers r, α, β, then

σ_{z} (α r + β x) = (1 − z r)^{−α} (1 − x)^{−β} .

When all alphabets 𝔸_{p} are equal to the same alphabet 𝔸, we write 𝔸 for the collection of A = {𝔸, 𝔸, …}. We shall also need the collection where 𝔸_{p} = p , that we denote by A = p . It corresponds to the multiplicative function f(n) = n.

We shall now formulate properties of multiplicative functions in terms of another classical object in number theory.

Given a function f from ℕ in a commutative ring, one can associate to it a Dirichlet series^{3}

F (f; s) = ∑_{n≥1} f(n)n^{−s} ,

the most notable being the Riemann zeta function ζ(s) := ∑_{n≥1} n^{−s}.

The product of Dirichlet series corresponds to the convolution of functions on ℕ:

F (f; s)F (g; s) = F (f ⋆ g; s) = ∑_{n}(∑_{d|n} f(d)g(n/d))n^{−s} .

When f is a multiplicative function, say f = μ_{A}, we write ζ(A; s) for the corresponding Dirichlet series. In this notation, the Riemann zeta function is ζ(1; s), that is, each alphabet 𝔸_{p} is equal to 1.

3We shall not address convergence issues, but shall treat the Dirichlet series as formal series. However, for all identities that we consider here, the formal treatment is sufficient to also deduce their validity as identities for analytic series. For, all our series converge in some domain, which must in fact be a (right) half plane (see [1, Theorem 11.1]), and then it follows from uniqueness of coefficients (see [1, Theorem 11.3]) that the formal identity is at the same time an analytic identity.

The product of two series ζ(A; s), ζ(B; s) is the series ζ(A + B; s), because for every p, σ_{z}(𝔸_{p})σ_{z}(𝔹_{p}) = σ_{z}(𝔸_{p} + 𝔹_{p}). Thus addition of alphabets corresponds to products of Dirichlet series.

Notice that the convolution of multiplicative functions with the classical Möbius function μ_{−1} or its inverse μ_{1} (cf. [1]), or the product of a Dirichlet series and ζ(s)^{−1} or ζ(s), are now interpreted as the addition to each alphabet 𝔸_{p} of ^{−}1 or 1 respectively:

μ_{A−1}(n) = ∑_{d: d|n} μ(n/d) μ_{A}(d) ⇔ ζ(A − 1, s) = ζ(A, s)/ζ(s)  (2)
μ_{A+1}(n) = ∑_{d: d|n} μ_{A}(d) ⇔ ζ(A + 1, s) = ζ(A, s) ζ(s) . (3)

2 Adding 1

We are now in the position to solve the exercise stated at the beginning of this text.

For the alphabets 2 − ^{−}1 and 3 − ^{−}1 we have

σ_{z} (2 − ^{−}1 ) = (1 − (^{−}1)z)(1 − z)^{−2} = 1 + 3z + 5z^{2} + 7z^{3} + ⋯

σ_{z} (3 − ^{−}1 ) = (1 − (^{−}1)z)(1 − z)^{−3} = 1 + 4z + 9z^{2} + 16z^{3} + · · · .

Since τ(p^{2k}) = 2k + 1, it follows that

ζ(s)^{3}/ζ(2s) = ζ (2 − ^{−}1 , s) = ∑_{n≥1} τ(n^{2}) n^{−s} .

Similarly, τ(p^{k})^{2} = (k^{+}1)^{2} implies

ζ(s)^{4}/ζ(2s) = ζ (3 − ^{−}1 , s) = ∑_{n≥1} τ(n)^{2} n^{−s} ,

and this proves the two required formulas.

In fact, many of the classical arithmetical multiplicative functions occur in products of zeta functions, as shows the following table. We need only identify the generating functions σ_{z}(𝔸_{p}) for all alphabets appearing in the left column, to ensure the validity of the expansions given in the right column.

\begin{matrix}alphabet & series & σ_{z}(𝔸_{p}) & expansion \\ −1 & 1/ζ(s) & 1 − z & ∑ μ_{−1}(n) n^{−s} \\ 2 & ζ(s)^{2} & (1^{−}z)^{−2} & ∑ τ(n) n^{−s} \\ r & ζ(s)^{r} & (1^{−}z)^{−r} & ∑ τ_{r}(n) n^{−s} \\ − ^{−}1 & ζ(s)/ζ(2s) & 1 − (^{−}z) & ∑ |μ_{−1}(n)| n^{−s} \\ 1 − ^{−}1 & ζ(s)^{2}/ζ(2s) & (1^{+}z)/(1^{−}z) & ∑ 2^{ω(n)} n^{−s} \\ 2 − ^{−}1 & ζ(s)^{3}/ζ(2s) & (1^{+}z)/(1^{−}z)^{2} & ∑ τ(n^{2}) n^{−s} \\ 3 − ^{−}1 & ζ(s)^{4}/ζ(2s) & (1^{+}z)/(1^{−}z)^{3} & ∑ τ(n)^{2} n^{−s} \\ 1 + p^{α} & ζ(s) ζ(s − α) & (1^{−}z)^{−1}(1^{−}zp^{α})^{−1} & ∑ (∑_{d|n} d^{α}) n^{−s} \\ p − 1 & ζ(s − 1)/ζ(s) & (1^{−}z)/(1^{−}zp) & ∑ ϕ(n) n^{−s} \end{matrix}

In the table, we use the function τ(n), which, as before, is the number of divisors of n, and, more generally, τ_{r}(n), r > 2, is the number of integral vectors [n_{1}, …, n_{r}] such that n = n_{1} ⋯ n_{r}. In addition, we denote by ω(n) the number of prime divisors of n and by ϕ(n) the number of integers less than n and prime to n.

Let us elaborate in some more detail about the relation between the third column (generating function for the alphabet) and the fourth column (Dirichlet series), in the order the alphabets are listed in the table:

• 1 − z, i.e. μ(p) = −1, μ(p^{k}) = 0, k ≥ 2. This is this the classical Möbius function;

• (1 − z)^{−2}, μ(p^{k}) = k + 1 = τ(p^{k}) is the number of divisors of p^{k};

• (1 − z)^{−r}, μ(p^{k}) = \binom{k+r−1}{k−1} is the number of r-tuple [n_{1}, …, n_{r}] such that n_{1} ⋯ n_{r} = p^{k};

• 1 − (^{−}z), μ(p) = 1, μ(p^{k}) = 0, k ≥ 2;

• (1 + z)/(1 − z), μ(p^{k}) = 2, k ≥ 1;

• (1 + z)/(1 − z)^{2}, μ(p^{k}) = 2k + 1 is the number of divisors of (p^{k})^{2};

• (1 + z)/(1 − z)^{3}, μ(p^{k}) = (k + 1)^{2} is the square of the number τ(p^{k}) of divisors of p^{k};

• (1 − z)^{−1}(1 − zp^{α})^{−1}, μ(p^{k}) = 1 + p^{α} + ⋯ + p^{kα} is the sum of the α-th powers of the divisors {1, p, …, p^{k}} of p^{k}; • (1−z)/(1−zp), μ(p^{k}) = p(p^{k−1} −1) is the number of integers less than

p^{k} and prime to p.

A natural generalization of the classical Möbius function proceeds by taking some complex number α, instead of ^{−}1, and setting all 𝔸_{p} = α. Recall that

S^{k}(α) = α(α + 1) ⋯ (α + k − 1)/ k! = \binom{α + k − 1}{k} .

Hence,

μ_{α}(∏_{p} p^{k}) = ∏_{p} \binom{α + k − 1}{k} .  (4)

These Möbius functions of higher order have been considered by Fleck [4, 3]^{4}, who proved the convolution formula μ_{α} ⋆ μ_{−1} = μ_{α−1}.

Taking Dirichlet series instead of alphabets, Fleck’s results translate into the seemingly more elaborate formula

∑_{n=1}^{∞} μ_{α}(n)n^{−s} = ζ(s) ∑_{n=1}^{∞} μ_{α−1}(n)n^{−s} ,  (5)

which is nothing else but

α = 1 + (α − 1) .  (6)

3 Hadamard Products

One can use other operations on alphabets than just adding ±1. For example, the “pointwise” product of two multiplicative functions is still a multiplicative function. It corresponds to the Hadamard product of generating series:

(∑_{i≥0} z^{i}S^{i}(𝔸) , ∑_{i≥0} z^{i}S^{i}(𝔹)) ⟶ ∑_{i≥0} z^{i}S^{i}(𝔸)S^{i}(𝔹) ,

or the Hadamard product of Dirichlet series, and induces an “Hadamard product” on pair of alphabets : (𝔸, 𝔹) → 𝔸 ◯ H 𝔹.

Indeed, given two finite alphabets 𝔸 and 𝔹, the Hadamard product of σ_{z}(𝔸) and σ_{z}(𝔹) is a rational function, with denominator

σ_{z}(−𝔸𝔹) := ∏_{a∈𝔸} ∏_{b∈𝔹}(1 − zab)^{−1} .

4and still reappear in recent literature [2].

However, in general the numerator will be too complicated to be applied to the theory of the Riemann zeta function. I shall nevertheless give three explicit cases that I found in the literature.

The first one is due to Ramanujan:

\frac{ζ(s)ζ(s − α)ζ(s − β)ζ(s − α − β)}{ζ(2s − α − β)} = ∑_{n≥1} \frac{∑_{d|n} d^{α} ∑_{d|n} d^{β}}{n^{s}} .  (7)

Indeed,

\frac{1 − z^{2}xy}{(1 − z)(1 − zx)(1 − zy)(1 − zxy)} = ∑_{i≥0}(1 + x + ⋯ + x^{i})(1 + y + ⋯ + y^{i})z^{i} ,

which means that the Hadamard product of

(1 − z)^{−1}(1 − zx)^{−1} and (1 − z)^{−1}(1 − zy)^{−1}

is the left-hand side. This left-hand side can be written σ_{z}(1+x+y+xy−Ω), with Ω an alphabet of cardinality 2 such that S^{1}(^{−}Ω) = 0 and S^{2}(^{−}Ω) = ^{−}xy.

When x = p^{α}, y = p^{β}, the generating function σ_{z}(1 + x + y + xy − Ω) specializes to the component depending on p of \frac{ζ(s)ζ(s−α)ζ(s−β)ζ(s−α−β)}{ζ(2s−α−β)}, and, thus eventually, Ramanujan’s identity is indeed just

(1^{+}x) ◯ H (1^{+}y) = (1^{+}x^{+}y^{+}xy) − Ω .  (8)

The second example uses the Hadamard powers of the simplest^{5} series, (1 − z)^{−2}.

By definition the k-th Hadamard power of 1 + 2z + 3z^{2} + ⋯ is

1 + 2^{k}z + 3^{k}z^{2} + 4^{k}z^{3} + ⋯ = E_{k}(z) (1 − z)^{k+1} ,

where E_{k}(z) is the k-th Eulerian polynomial, dear to combinatorialists [6, Ch. 7].

Define now, for any positive integer k, the function

η_{k}(s) = \frac{1}{1 − 2^{−s}}_{∏_{p prime} p≡1 (mod 4)} \frac{E_{k}(p^{−s})}{1 − p^{−s}}_{∏_{r prime} r≡3 (mod 4)} \frac{1}{1 − r^{−2s}} .  (9)

5The Hadamard product of f(z) with (1 − z)^{−1} being f(z), one has to argue between (1 − z)^{−2} and (1 − 2z)^{−1} for the title of being the simplest non-trivial series. Notice that not only 1/(1 − z) is stable under Hadamard powers, but so is 1/(1 − z^{α}) for any positive integer α.

Therefore, thanks to our computations of the Hadamard powers of (1 − z)^{−2} and (1 − z^{2})^{−1}, we see that η_{k}(s) is the k-th Hadamard power of η_{1}(s).

The alphabets corresponding to η_{1}(s) are

𝔸_{2} = 1 , 𝔸_{p} = 2 , 𝔸_{r} = 1 + ^{−}1 ,

since σ_{z}(1) = 1/(1 − z), σ_{z}(2) = 1/(1 − z)^{2}, σ_{z} (1 + ^{−}1 ) = 1/(1 − z^{2}).

Subtracting 1 from all the alphabets, one gets a simpler function:

L(s) := η_{1}(s)/ζ(s) = ∏_{p≡1} \frac{1}{1 − p^{−s}} ∏_{r≡3} \frac{1}{1 + r^{−s}} = ∑_{n=0}^{∞} \frac{(^{−}1)^{n}}{(2n + 1)^{s}} ,  (10)

corresponding to the alphabets

𝔸_{2} = 0 , 𝔸_{p} = 1 , 𝔸_{r} = ^{−}1 .

Since the Hadamard square of (1 − z)^{−2} is equal to

(1 + z) (1 − z)^{−3} = σ_{z} (3 − ^{−}1 ) ,

the function η_{2}(s) is associated to the alphabets

𝔸_{2} = 1 , 𝔸_{p} = 3 − ^{−}1 , 𝔸_{r} = 1 + ^{−}1 .

The Hadamard cube of (1 − z)^{−2} being

(1 + 4z + z^{2}) (1 − z)^{−4} = σ_{z} (4 − α − β) ,

with α = ^{−}2 + \sqrt{3} , β = ^{−}2 − \sqrt{3} , the function η_{3}(s) is associated to the alphabets

𝔸_{2} = 1 , 𝔸_{p} = 4 − α − β , 𝔸_{r} = 1 + ^{−}1 .

Finally, the fourth Hadamard power being

(1 + 11z + 11z^{2} + z^{3}) (1 − z)^{−5} = (1 + z)(1 + 10z + z^{2}) (1 − z)^{−5}

= σ_{z} (5 − ^{−}1 ^{−}α^{−}β) ,

with α = ^{−}5 + 2\sqrt{6} , β = ^{−}5 − 2\sqrt{6} , the function η_{4}(s) is associated to the alphabets

𝔸_{2} = 1 , 𝔸_{p} = 5 − ^{−}1 − α − β , 𝔸_{r} = 1 + ^{−}1 .

Let us close this text by considering higher powers (1 − z)^{−r}, with r > 2. I shall restrict myself to their Hadamard squares.

Since

\frac{1}{(1 − z)^{r}} ◯ H \frac{1}{(1 − z)^{r}} = P_{r−1} (\frac{1 + z}{1 − z} ) \frac{1}{(1 − z)^{r}} ,

where P_{j} is the Legendre polynomial [6] of degree j, one has, using the function τ_{r}(n) defined above,

∑_{n=1}^{∞}(τ_{r}(n))^{2} n^{−s} = ζ(s)^{r} ∏_{p} (P_{r−1} (\frac{1 + p^{s}}{1 − p^{s}} )) .  (11)

References

[1] T. Apostol, Introduction to Analytic Number Theory, Springer (1976).

[2] T. Brown, L.C. Hsu, J. Wang, P.J.-S. Shihue, On a certain kind of generalized number-theoretical Möbius function, Math. Scientist 25 (2000) 72-77.

[3] L.E. Dickson, History of the theory of numbers, vol. 1, Chelsea reprint (1952).

[4] A. Fleck, Über gewisse allgemeine zahlentheoretische Funktionen, insbesondere eine der Funktion μ(m) verwandte Funktion μ_{k}(m), Sitzungsber. Berl. Math. Ges. 15 (1916) 3–8.

[5] A. Lascoux, Symmetric functions and combinatorial operators on polynomials, CBMS/AMS Lectures Notes 99, (2003).

[6] J. Riordan, Combinatorial identities, Wiley (1968).

[7] E.C. Titchmarsh, The zeta-function of Riemann, Cambridge University Press (1930).

[8] E.C. Titchmarsh, The theory of functions, Oxford University Press (1932).