Quasi-symmetric functions and mod p multiple harmonic sums

Michael E. Hoffman

Dept. of Mathematics U. S. Naval Academy, Annapolis, MD 21402 and Max-Planck-Institut für Mathematik Vivatsgasse 7, D-53111 Bonn, Germany

                             meh@usna.edu

January 23, 2004

Keywords: Multiple harmonic sums, mod p harmonic sums, quasi-symmetric functions MR Classifications: Primary 11M06, 11B50; Secondary 05E05, 16W30

Abstract

We present a number of results about (finite) multiple harmonic sums modulo a prime, which provide interesting parallels to known results about multiple zeta values (i.e., infinite multiple harmonic series). In particular, we prove a “duality” result for mod p harmonic sums similar to (but distinct from) that for multiple zeta values. We also exploit the Hopf algebra structure of the quasi-symmetric functions to do calculations with multiple harmonic sums mod p, and obtain, for each weight n ≤ 9, a set of generators for the space of weight-n multiple harmonic sums mod p.

1 Introduction

In recent years there has been considerable interest in the multiple zeta values

ζ(i_{1}, i_{2}, …, i_{k}) = ∑_{n_{1}>n_{2}>···>n_{k}≥1} \frac{1}{n_{1}^{i_{1}}n_{2}^{i_{2}} ⋯ n_{k}^{i_{k}}} ,  (1)

which converge for i_{1} > 1; see, e.g. [2, 13, 14, 17, 16, 27, 28]. The multiple zeta values are limits of the finite harmonic sums

A_{(i_{1},i_{2},...,i_{k})}(n) = ∑_{n≥n_{1}>n_{2}>···>n_{k}≥1} \frac{1}{n_{1}^{i_{1}}n_{2}^{i_{2}} ⋯ n_{k}^{i_{k}}} ,  (2)

as n → ∞. In fact, these finite sums themselves are of interest in physics [1, 26]. Both types of quantities are indexed by the the exponent string (i_{1}, …, i_{k}): we refer to k as the length and i_{1} + ⋯ + i_{k} as the weight.

The multiple zeta values (1) form an algebra under multiplication. In fact, there are two distinct multiplications on the set of multiple zeta values, the harmonic (or “stuffle”) product and the shuffle product, coming from the representation of multiple zeta values as iterated series and as iterated integrals respectively (see §4 of [17] for a discussion). Only the first of these products applies to the finite sums (2).

In this paper we develop a theory of the mod p values (p a prime), of the finite harmonic sums (2) when n = p − 1. Our main tools are the structure of the algebra QSym of quasisymmetric functions (which formalizes the harmonic product) and a mod p duality result (Theorem 4.7 below) which corresponds to the duality theorem for multiple zeta values (see, e.g., Corollary 6.2 of [14]). The divisibility properties of finite harmonic sums are considered in [29], and there is some overlap between that paper and this one. But in this paper we focus only on congruences mod p, while [29] also considers congruences mod higher powers of p. A brief account of the results of §4 of this paper appeared earlier in the last section of [16].

The theory of mod p finite harmonic sums has several interesting differences and similarities to the theory of multiple zeta values. While the values of (1) with length k = 1 are the classical zeta values ζ(i_{1}), it is well known that the mod p value of

A_{(i_{1})}(p − 1) = ∑_{j=1}^{p−1} \frac{1}{j^{i_{1}}}

is zero when p > i_{1} + 1. But for k = 2 we have the relation

A_{(i_{1},1)}(p − 1) ≡ B_{p−i_{1}−1} mod p,

with Bernoulli numbers (see Theorem 6.1 below). In the case of multiple zeta values, it appears that that multiple zeta values not expressible in terms of the classical zeta values occur first in weight 8 (e.g., ζ(6, 2)); for the finite harmonic sums mod p, the first ones not expressible in terms of Bernoulli numbers appear to occur in weight 7 (see §7 below).

As we have already mentioned, there is a duality result in both theories. If we code the exponent strings (i_{1}, i_{2}, …, i_{k}) occurring in (1) and (2) by the monomial x^{i_{1}−1}y ⋯ x^{i_{k}−1}y in noncommuting variables x and y, then the duality map for multiple zeta values is the anti-automorphism of Q⟨x, y⟩ that exchanges x and y, while that for the mod p finite harmonic sums is the automorphism ψ of Z⟨x, y⟩ with ψ(x) = x + y and ψ(y) = −y.

The dimension d_{n} of the rational vector space of multiple zeta values of weight n was conjectured by Zagier [28] to be the Perrin numbers, i.e. d_{1} = 0, d_{2} = d_{3} = 1, and d_{n} = d_{n−2} + d_{n−3}. The corresponding numbers for the finite harmonic sums (2) are the minimal numbers c_{n} of weight-n harmonic sums needed to generate all weight-n harmonic sums mod p for p > n + 1. From the calculations of §7 below the first few values of c_{n} seem to be the following.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ c_{n} & 0 & 0 & 1 & 0 & 1 & 1 & 2 & 2 & 3 \end{matrix}

We do not have a conjecture about the c_{n} for general n, but we do conjecture that all multiple harmonic sums A_{I}(p − 1) can be written mod p as sums of products of sums of the form A_{(h,1,...,1)}(p − 1) (what we call “height one sums”; see §5 below) with h even.

This paper is organized as follows. In §2 we give an exposition of the algebra QSym of quasi-symmetric functions. In §3 we describe the Hopf algebra structure of QSym, particularly the antipode, and introduce some integral bases of QSym important in the sequel. In §4 we define bases A_{I} and S_{I} for the set of finite harmonic sums, and prove some basic results about the mod p case. In §5 we discuss a particular class of multiple harmonic sums, the height one sums. In §6 we obtain some results about S_{I}(p − 1) mod p when I has short length. Finally, in §7 we apply the preceding results to find sets of products of height one sums that generate all multiple harmonic sums mod p through weight 9.

This paper was written during a stay at the Max-Planck-Institut für Mathematik in Bonn, and the author thanks the directors of the Institut for their hospitality. The author also thanks Joe Buhler for his prompt response to a query about irregular primes.

2 Harmonic Algebra and Quasi-Symmetric Functions

Let ℌ be the underlying graded abelian group of the noncommutative polynomial algebra Z⟨x, y⟩, where x and y both have degree 1. For a word w of ℌ, we refer to the total degree of w as its weight (denoted |w|) and its y-degree as its length (denoted ℓ(w)). We can define a commutative multiplication ∗ on ℌ by requiring that it distribute over the addition and that it satisfy the following axioms:

H1. For any word w, 1 ∗ w = w ∗ 1 = w;

H2. For any word w and integer n ≥ 1,

x^{n} ∗ w = w ∗ x^{n} = wx^{n};

H3. For any words w_{1}, w_{2} and integers p, q ≥ 0,

x^{p}yw_{1} ∗ x^{q}yw_{2} = x^{p}y(w_{1} ∗ x^{q}yw_{2}) + x^{q}y(x^{p}yw_{1} ∗ w_{2}) + x^{p+q+1}y(w_{1} ∗ w_{2}).

Note that axiom (H3) allows the ∗-product of any pair of words to be computed recursively, since each ∗-product on the right has fewer factors of y than the ∗-product on the left-hand side. Induction on length establishes the following.

Theorem 2.1. The ∗-product is commutative and associative.

We refer to ℌ together with its commutative multiplication ∗ as the (integral) harmonic algebra (ℌ, ∗). Let ℌ^{1} be the additive subgroup Z1 + ℌy of ℌ; it is evidently a subalgebra of (ℌ, ∗). Note that any word w ∈ ℌ^{1} can be written in terms of the elements z_{i} = x^{i−1}y, and that the length ℓ(w) is the number of factors z_{i} of w when expressed this way. We can rewrite the inductive rule (H3) for the ∗-product as

z_{p}w_{1} ∗ z_{q}w_{2} = z_{p}(w_{1} ∗ z_{q}w_{2}) + z_{q}(z_{p}w_{1} ∗ w_{2}) + z_{p+q}(w_{1} ∗ w_{2}).  (3)

Now for each positive integer n, define a homomorphism ϕ_{n} : ℌ^{1} → Z[t_{1}, …, t_{n}] of graded abelian groups (where |t_{i}| = 1 for all i) as follows. Let ϕ_{n}(1) = 1 and

ϕ_{n}(z_{i_{1}}z_{i_{2}} ⋯ z_{i_{k}}) = ∑_{1≤n_{1}<n_{2}<···<n_{k}≤n} t_{n_{1}}^{i_{1}}t_{n_{2}}^{i_{2}} ⋯ t_{n_{k}}^{i_{k}}

for words of length k ≤ n, and let ϕ(w) = 0 for words of length greater than n; extend ϕ_{n} additively to ℌ^{1}. Because the rule (3) corresponds to multiplication of series, ϕ_{n} is an algebra homomorphism of (ℌ^{1}, ∗) into Z[t_{1}, …, t_{n}], and ϕ_{n} is evidently injective through degree n. For each m ≥ n, there is a restriction map

ρ_{m,n} : Z[t_{1}, …, t_{m}] → Z[t_{1}, …, t_{n}]

defined by

ρ_{m,n}(t_{i}) = \begin{cases}t_{i}, & i ≤ n \\ 0, & i > n. \end{cases}

The inverse limit

𝔓 = proj lim_{n} Z[t_{1}, …, t_{n}]

is the subalgebra of Z[[t_{1}, t_{2}, …]] consisting of those formal power series of bounded degree. The ϕ_{n} commute with the restriction maps, so they define a homomorphism ϕ : ℌ^{1} → 𝔓.

Inside 𝔓 is the algebra of symmetric functions

Sym = proj lim_{n} Z[t_{1}, …, t_{n}]^{Σ_{n}}

and also the algebra QSym of quasi-symmetric functions (first described in [9]). We say a formal series p ∈ 𝔓 is in QSym if the coefficient of t_{i_{1}}^{p_{1}} ⋯ t_{i_{k}}^{p_{k}} in p is the same as the coefficient of t_{j_{1}}^{p_{1}} ⋯ t_{j_{k}}^{p_{k}} in p whenever i_{1} < i_{2} < ⋯ < i_{k} and j_{1} < j_{2} < ⋯ < j_{k}. Evidently Sym ⊂ QSym. An integral basis for QSym is given by the monomial quasi-symmetric functions

M_{(p_{1},p_{2},...,p_{k})} = ∑_{i_{1}<i_{2}<···<i_{k}} t_{i_{1}}^{p_{1}}t_{i_{2}}^{p_{2}} ⋯ t_{i_{k}}^{p_{k}},

which are indexed by compositions (p_{1}, …, p_{k}). Since ϕ(z_{i_{1}} ⋯ z_{i_{k}}) = M_{(i_{1},...,i_{k})}, we have the following result.

Theorem 2.2. ϕ is an isomorphism of (ℌ^{1}, ∗) onto QSym.

As is well known, the algebra Sym of symmetric functions is generated by the elementary symmetric functions e_{i}, as well as by the complete symmetric functions h_{i}. The power-sum symmetric functions p_{i} generate Sym ⊗Q, but only generate a subalgebra of Sym over Z. It is easy to see that ϕ(z_{1}^{i}) = e_{i} and ϕ(z_{i}) = p_{i}.

A monomial quasi-symmetric function M_{I} is in Sym exactly when all parts of I are the same. Given I = (i_{1}, …, i_{k}), the symmetric group Σ_{k} on k letters acts on I by σ · I = (i_{σ(1)}, …, i_{σ(k)}), and the symmetrization

∑_{σ∈Σ_{k}} M_{σ·I}  (4)

of M_{I} is evidently in Sym. Hence the element (4) can be written as a sum of rational multiples of the power-sums p_{i} = M_{(i)}. But in fact (4) is a sum of products of the M_{(i)} with integral coefficients that can be given explicitly as follows. Theorem 2.3. Let I = (i_{1}, i_{2}, …, i_{k}) be a composition. Then

∑_{σ∈Σ_{k}} M_{σ·I} = ∑_{partitions ℬ = {B_{1}, …, B_{l}} of {1, …, k}} (−1)^{k−l}c(ℬ)M_{(b_{1})}M_{(b_{2})} ⋯ M_{(b_{l})},

where c(ℬ) = (card B_{1} − 1)! ⋯ (card B_{l} − 1)! and b_{s} = ∑_{j∈B_{s}} i_{j}. Proof. While the argument used to prove Theorem 2.2 of [13] can be adapted to prove this result, we shall use the Möbius inversion formula as follows. The set Π_{k} of partitions of the set {1, …, k}, with the partial order given by refinement, is a finite semimodular lattice. We also have, for any 𝒞 = {C_{1}, …, C_{p}} ∈ Π_{k},

M_{(c_{1})}M_{(c_{2})} ⋯ M_{(c_{p})} = ∑_{ℬ={B_{1},...,B_{l}}⪯𝒞} ∑_{σ∈Σ_{l}} M_{σ·(b_{1},...,b_{l})},

where b_{s} = ∑_{j∈B_{s}} i_{j} and c_{s} = ∑_{j∈C_{s}} i_{j}. Then the Möbius inversion formula gives

∑_{σ∈Σ_{p}} M_{σ·(c_{1},...,c_{p})} = ∑_{ℬ={B_{1},...,B_{l}}⪯𝒞} μ(ℬ, 𝒞)M_{(b_{1})} ⋯ M_{(b_{l})}.  (5)

The conclusion follows by taking 𝒞 = {{1}, {2}, …, {k}} in equation (5) and noting that in this case μ(ℬ, 𝒞)=(−1)^{k−l}c(ℬ) (see [24], Example 3.10.4).

The rational algebra of quasi-symmetric functions QSym ⊗Q was shown to be a polynomial algebra by Malvenuto and Reutenauer [22]. To describe the generators, we put an order on the words of ℌ by setting x < y and extending it lexicographically. A word is called Lyndon if it is smaller than any of its proper right factors, i.e. for w Lyndon we have w < v whenever w = uv for u, v ≠ 1. Let ℒ be the set of Lyndon words in ℌ^{1}. Then the following result was proved in [22]. Theorem 2.4. QSym ⊗Q is a polynomial algebra on the generators ϕ(w), where w ∈ ℒ.

The integral structure is more subtle. The result is again that the algebra is polynomial, but one has to use a different set of generators. Let ℒ^{mod} be the set of modified Lyndon words in ℌ^{1}, i.e., whenever w = z_{i_{1}}^{p_{1}} ⋯ z_{i_{k}}^{p_{k}} ∈ ℒ has a common factor d dividing all the exponents p_{i}, replace it with v^{d}, where v = z_{i_{1}}^{p_{1}/d} ⋯ z_{i_{k}}^{p_{k}/d}. The following result was first stated by Ditters, though the first correct proof seems to be due to Hazewinkel [12]. Theorem 2.5. QSym is a polynomial algebra on the generators ϕ(w), where w ∈ ℒ^{mod}.

3 Quasi-Symmetric Functions as a Hopf Algebra

For definitions and basic results on Hopf algebras we refer the reader to [23], [25], and [20]. The algebra (ℌ^{1}, ∗) ≅ QSym has a Hopf algebra structure with coproduct Δ defined by

Δ(z_{i_{1}}z_{i_{2}} ⋯ z_{i_{n}}) = ∑_{j=0}^{n} z_{i_{1}} ⋯ z_{i_{j}} ⊗ z_{i_{j+1}} ⋯ z_{i_{n}},  (6)

and counit ϵ with ϵ(u) = 0 for all elements u of positive degree. This extends the wellknown Hopf algebra structure on the algebra Sym (as described in [7]), in which the elementary symmetric functions e_{i} (↔ y^{i}) and complete symmetric functions h_{i} are divided powers, while the power sums p_{i} (↔ z_{i}) are primitive. The Hopf algebra (ℌ^{1}, ∗, Δ) is commutative but not cocommutative. Its (graded) dual is the Hopf algebra of noncommutative symmetric functions as defined in [8].

Now QSym has various integral bases besides the M_{I}, also indexed by compositions. For compositions I, J, we say I refines J (denoted I ≻ J) if J can be obtained from I by combining some of its parts. Then the fundamental quasi-symmetric functions are given by

F_{I} = ∑_{J⪰I} M_{J},  (7)

and the essential quasi-symmetric functions are given by

E_{I} = ∑_{J⪯I} M_{J}.  (8)

It will be useful to have some additional notations for compositions. We adapt the notation used the previous section for words, so for I = (i_{1}, …, i_{k}) the weight of I is |I| = i_{1} + ⋯ + i_{k}, and k = ℓ(I) is the length of I. For I = (i_{1}, …, i_{k}), the reversed composition (i_{k}, …, i_{1}) will be denoted Ī: of course reversal preserves weight, length and refinement (i.e., I ⪰ J implies Ī ⪰ J̄). We write I ⊔ J for the juxtaposition of I and J, so \overline{I ⊔ J} = J̄ ⊔ Ī.

Compositions of weight n are in 1-to-1 correspondence with subsets of {1, 2, …, n−1} via partial sums

(i_{1}, i_{2}, …, i_{k}) → {i_{1}, i_{1} + i_{2}, …, i_{1} + ⋯ + i_{k−1}},  (9)

and this correspondence is an isomorphism of posets, i.e., I ⪯ J if and only if the subset corresponding to I contains that corresponding to J. Complementation in the power set thus gives rise to an involution I → I^{∗}; e.g., (1, 1, 2)^{∗} = (3, 1). Evidently |I^{∗}| = |I| and ℓ(I) + ℓ(I^{∗}) = |I| + 1. Also, I ⪯ J if and only if I^{∗} ⪰ J^{∗}. The complementation operation commutes with reversal, so the notation Ī^{∗} is unambiguous.

Because of the correspondence (9) between the poset of compositions of n and the poset of subsets of {1, 2, …, n − 1}, it follows that the Möbius function for compositions of n is given by

μ(I, J) = (−1)^{ℓ(I)−ℓ(J)}.

Thus, e.g., the Möbius inversion formula applied to equation (8) is

M_{I} = ∑_{J⪯I}(−1)^{ℓ(I)−ℓ(J)}E_{J}.  (10)

Since QSym is a commutative Hopf algebra, its antipode S is an automorphism of QSym and S^{2} = id. Now S can be given by the following explicit formulas: for proof see [5] or [15].

Theorem 3.1. The antipode S of QSym is given by

1. S(M_{I}) = ∑_{I_{1}⊔I_{2}⊔···⊔I_{l}=I}(−1)^{l}M_{I_{1}}M_{I_{2}} ⋯ M_{I_{l}};

2. S(M_{I}) = (−1)^{ℓ(I)}EĪ.

Part (2) of this result implies a number of facts about the E_{I}. First, the E_{I} have almost the same multiplication rules as the M_{I}: if T is the automorphism of QSym sending M_{I} to MĪ, then ST takes any identity among the M_{I} to an identity among the E_{I} that differs only in signs. For example, since

M_{(2)}M_{(3)} = M_{(2,3)} + M_{(3,2)} + M_{(5)}

we have

E_{(2)}E_{(3)} = E_{(2,3)} + E_{(3,2)} − E_{(5)}.

Second, the coproduct formula (6), which in terms of the M_{I} says

Δ(M_{I}) = ∑_{J⊔K=I} M_{J} ⊗ M_{K},

can also be written

Δ(E_{I}) = ∑_{J⊔K=I} E_{J} ⊗ E_{K},

because of the standard Hopf algebra relation ΔS = (S ⊗ S)Δ^{op}. Finally, if we apply S to both sides of Theorem 2.3 we obtain, for any composition I = (i_{1}, …, i_{k}),

∑_{σ∈Σ_{k}} E_{σ·I} = ∑_{partitions ℬ = {B_{1}, …, B_{l}} of {1, …, k}} c(ℬ)M_{(b_{1})}M_{(b_{2})} ⋯ M_{(b_{l})},  (11)

where as above c(ℬ) = (card B_{1} − 1)! ⋯ (card B_{l} − 1)! and b_{s} = ∑_{j∈B_{s}} i_{j}.

Now define an automorphism ψ of Z⟨x, y⟩ by

ψ(x) = x + y, ψ(y) = −y.  (12)

Evidently ψ^{2} = id, and ψ(ℌ^{1}) = ℌ^{1}. Thus ψ defines an additive involution of ℌ^{1} ≅ QSym (which is not, however, a homomorphism for the ∗-product). We can describe the action of ψ on the integral bases for QSym as follows.

Theorem 3.2. For any composition I,

1. ψ(M_{I}) = (−1)^{ℓ(I)}F_{I};

2. ψ(E_{I}) = −E_{I^{∗}}.

Proof. Suppose w = w(I) is the word in x and y corresponding to a composition I. Then evidently substituting y in place of any particular factor x in w corresponds to splitting a part of I. With this observation, part (1) is clear (there is also one factor of −1 for each occurrence of y in w).

Now we prove part (2). We have

ψ(E_{I}) = ∑_{J⪯I} ψ(M_{J}) = ∑_{J⪯I}(−1)^{ℓ(J)}F_{J}

from part (1). From Example 1 of [15], S(F_{I}) = (−1)^{|I|}FĪ^{∗}, where S is the antipode of QSym. Thus

Sψ(E_{I}) = ∑_{J⪯I}(1)^{ℓ(J)+|J|}FJ̄^{∗} = − ∑_{J⪯I}(−1)^{ℓ(J^{∗})}FJ̄^{∗}

= − ∑_{J̄^{∗}⪰Ī^{∗}}(−1)^{ℓ(J̄^{∗})}FJ̄^{∗} = − ∑_{K⪰Ī^{∗}}(−1)^{ℓ(K)}F_{K}.

Now by Möbius inversion of equation (7)

M_{I} = ∑_{I⪯J}(−1)^{ℓ(I)−ℓ(J)}F_{J},

and so

Sψ(E_{I}) = −(−1)^{ℓ(Ī^{∗})}MĪ^{∗}

Apply S be both sides to get

ψ(E_{I}) = −(−1)^{ℓ(I^{∗})}(−1)^{ℓ(Ī^{∗})}E_{I^{∗}} = −E_{I^{∗}}.

4 Finite Multiple Sums and Mod p Results

In this section we consider the finite sums

A_{(i_{1},...,i_{k})}(n) = ∑_{n≥n_{1}>n_{2}>···>n_{k}≥1} \frac{1}{n_{1}^{i_{1}} ⋯ n_{k}^{i_{k}}}

and

S_{(i_{1},...,i_{k})}(n) = ∑_{n≥n_{1}≥n_{2}≥···≥n_{k}≥1} \frac{1}{n_{1}^{i_{1}} ⋯ n_{k}^{i_{k}}} ,

where the notation is patterned after that of [13]; the multiple zeta values are given by

ζ(i_{1}, …, i_{k}) = lim_{n→∞} A_{(i_{1},...,i_{k})}(n),

when the limit exists (i.e., when i_{1} > 1).

Let ρ_{n} = eT ϕ_{n}, where ϕ_{n} is the map defined in §2, T is the automorphism of QSym sending M_{I} to MĪ, and e is the function that sends t_{i} to \frac{1}{i}. Then ρ_{n} : (ℌ^{1}, ∗) → R is a homomorphism sending z_{i_{1}}z_{i_{2}} ⋯ z_{i_{k}} in ℌ^{1} to A_{(i_{1},...,i_{k})}(n). We can combine the homomorphisms ρ_{n} into a homomorphism ρ that sends w ∈ ℌ^{1} to the real-valued sequence n → ρ_{n}(w). We shall write A_{I} for the real-valued sequence n → A_{I}(n) (and similarly for S_{I}), so ρϕ^{−1} sends M_{I} to A_{I} and E_{I} to S_{I}. For example, we can apply ρϕ^{−1} to equation (10) above to get

A_{I} = ∑_{J⪯I}(−1)^{ℓ(I)−ℓ(J)}S_{J}  (13)

Applying the homomorphism ρ_{n}ϕ^{−1} to Theorem 2.3 and equation (11), we get formulas for symmetric sums of A_{I}(n) and S_{I}(n) in terms of length one sums S_{(m)}(n) (cf. Theorems 2.1 and 2.2 of [13]).

Theorem 4.1. For any composition I = (i_{1}, ⋯, i_{k}),

∑_{σ∈Σ_{k}} S_{σ·I}(n) = ∑_{partitions ℬ = {B_{1}, …, B_{l}} of {1, …, k}} c(ℬ)S_{(b_{1})}(n) ⋯ S_{(b_{l})}(n)
∑_{σ∈Σ_{k}} A_{σ·I}(n) = ∑_{partitions ℬ = {B_{1}, …, B_{l}} of {1, …, k}} (−1)^{k−l}c(ℬ)S_{(b_{1})}(n) ⋯ S_{(b_{l})}(n),

where c(ℬ) = (card B_{1} − 1)! ⋯ (card B_{l})! and b_{s} = ∑_{j∈B_{s}} i_{j}.

Remark. If I = (s, s, …, s), the second formula above gives a more explicit version of Lemma 2.11 of [29].

We consider two operators on the space R^{N} of real-valued sequences. First, there is the partial-sum operator Σ, given by

Σa(n) = ∑_{i=0}^{n} a(i)

for a ∈ R^{N}. Second, there is the operator ∇ given by

∇a(n) = ∑_{i=0}^{n} \binom{n}{i}(−1)^{i}a(i).

It is easy to show that Σ and ∇ generate a dihedral group within the automorphisms of R^{N}, i.e., ∇^{2} = id and Σ∇ = ∇Σ^{−1}. It follows that (Σ∇)^{2} = id. We have the following result on multiple sums.

Theorem 4.2. For any composition I, Σ∇S_{I} = −S_{I^{∗}}.

Proof. We proceed by induction on |I|. The weight one case is Σ∇S_{(1)} = ∇Σ^{−1}S_{(1)} = −S_{(1)}, i.e.,

∑_{k=1}^{n} \frac{(−1)^{k}}{k} \binom{n}{k} = − ∑_{k=1}^{n} \frac{1}{k},

a classical (but often rediscovered) formula which actually goes back to Euler [6]. For I = (i_{1}, i_{2}, …, i_{k}), it is straightforward to show that ∇S_{I}(n) = \frac{1}{n}f(n), where f ∈ R^{N} is given by

f(n) = \begin{cases}S_{(i_{2},...,i_{k})}(n), & if i_{1} = 1; \\ Σ^{−1}S_{(i_{1}−1,i_{2},...,i_{k})}(n), & otherwise. \end{cases}

Now suppose the theorem has been proved for all I of weight less than n, and let I = (i_{1}, …, i_{k}) have weight n. There are two cases: i_{1} = 1, and i_{1} > 1. In the first case, let (i_{2}, …, i_{k})^{∗} = J = (j_{1}, …, j_{r}). By the assertion of the preceding paragraph and the induction hypothesis,

Σ∇S_{I}(n) = Σ(\frac{1}{n}∇S_{J^{∗}}(n)) = Σ(\frac{1}{n}Σ^{−1}S_{J}(n)) = −S_{(j_{1}+1,j_{2},...,j_{r})}(n).

But evidently I^{∗} = (j_{1} + 1, j_{2}, …, j_{r}), so the theorem holds in this case.

If i_{1} > 1, we instead write (i_{1} − 1, i_{2}, …, i_{k})^{∗} = J = (j_{1}, …, j_{r}). Then

Σ∇S_{I}(n) = Σ(\frac{1}{n}∇Σ^{−1}S_{J^{∗}}(n)) = Σ(\frac{1}{n}Σ∇S_{J^{∗}}(n)) = −Σ(\frac{1}{n}S_{J}(n)) = −S_{(1,j_{1},...,j_{r})}(n).

But in this case I^{∗} = (1, j_{1}, …, j_{r}), so the theorem holds in this case as well.

The proof of the preceding result is essentially a formalization of the procedure in App. B of [26]. Recalling the automorphism ψ of ℌ^{1} defined by equation (12), we note that Theorem 4.2, together with part (2) of Theorem 3.2, says that the diagram

QSym ⟶^{ψ} QSym
ρ↓  ^{ρ}↓
R^{N} ⟶^{Σ∇} R^{N}

(14)

commutes.

We now turn to mod p results about S_{I}(p−1) and A_{I}(p−1), where p is a prime. Since the sums A_{I}(p − 1) and S_{I}(p − 1) contain no factors of p in the denominators, they can be regarded as elements of the field Z/pZ. The following result about length one harmonic sums is well known (cf. [11], pp. 86-88).

Theorem 4.3. S_{(k)}(p − 1) ≡ 0 mod p for all prime p > k + 1.

Proof. Since the group of units in Z/pZ has order p − 1, we have

x^{p−1} − 1 = (x − 1)(x − 2) ⋯ (x − p + 1)

in Z/pZ. Thus, in the expansion

x(x − 1) ⋯ (x − p + 1) = ∑_{i=1}^{p}(−1)^{p−i}e_{p−i}(1, 2, …, p − 1)x^{i},

where e_{i} is the ith elementary symmetric function, we must have e_{p−i}(1, …, p − 1) ≡ 0 mod p except for e_{0}(1, …, p − 1) ≡ 1 and e_{p−1}(1, …, p − 1) ≡ −1 mod p. Thus, the Newton formulas

∑_{i=1}^{r}(−1)^{i−1}p_{i}(1, …, p − 1)e_{r−i}(1, …, p − 1) = re_{r}(1, …, p − 1),

where p_{i} is the ith power-sum symmetric function, reduce mod p to

p_{r}(1, …, p − 1) ≡ −re_{r}(1, …, p − 1) ≡ 0 mod p

when p > r + 1. But

p_{r}(1, …, p − 1) ≡ S_{(r)}(p − 1) mod p

since inversion permutes the units of Z/pZ, so the result follows.

Combining the preceding result with Theorem 4.1 gives the following.

Theorem 4.4. For any composition I = (i_{1}, …, i_{k}) and prime p > |I| + 1,

∑_{σ∈Σ_{k}} A_{σ·I}(p − 1) ≡ ∑_{σ∈Σ_{k}} S_{σ·I}(p − 1) ≡ 0 mod p.

In particular it follows that, for I = (r, r, …, r) (k repetitions), we have

A_{I}(p − 1) ≡ S_{I}(p − 1) ≡ 0 mod p  (15)

for prime p > rk + 1 (cf. Theorem 2.13 of [29]). There is the following result relating sums associated to I and Ī (cf. Lemma 3.2 of [29]).

Theorem 4.5. For any composition I, A_{I}(p−1) ≡ (−1)^{|I|}AĪ(p−1) mod p, and similarly S_{I}(p − 1) ≡ (−1)^{|I|}SĪ(p − 1) mod p.

Proof. Let I = (i_{1}, …, i_{k}). Working mod p, we have

A_{I}(p − 1) ≡ ∑_{p>a_{1}>···>a_{k}>0} \frac{1}{a_{1}^{i_{1}} ⋯ a_{k}^{i_{k}}} ≡ ∑_{p>a_{1}>···>a_{k}>0} \frac{(−1)^{i_{1}+···+i_{k}}}{(p − a_{1}^{i_{1}}) ⋯ (p − a_{k}^{i_{k}})}

≡ ∑_{0<b_{1}<···<b_{k}<p} \frac{(−1)^{i_{1}+···+i_{k}}}{b_{1}^{i_{1}} ⋯ b_{k}^{i_{k}}} = (−1)^{|I|}AĪ(p − 1),

and similarly for S_{I}.

An immediate consequence is that S_{I}(p − 1) ≡ A_{I}(p − 1) ≡ 0 mod p if I = Ī and |I| is odd. Another consequence is that S_{(i,j)}(p − 1) ≡ A_{(i,j)}(p − 1) ≡ 0 mod p when p > i + j + 1 and i + j is even. This is because

S_{(i,j)}(p − 1) + S_{(j,i)}(p − 1) ≡ 0 mod p

for p > i + j + 1 by Theorem 4.1, while S_{(i,j)}(p − 1) ≡ S_{(j,i)}(p − 1) mod p when i + j is even by Theorem 4.5.

We have the following result relating S_{I} and S_{I^{∗}}.

Theorem 4.6. S_{I}(p − 1) ≡ −S_{I^{∗}}(p − 1) mod p for all primes p.

Proof. Let f be a sequence. From the definition of ∇

Σ∇f(n) = ∑_{i=0}^{n} \binom{n + 1}{i + 1}(−1)^{i}f(i),

so taking n = p − 1 gives

Σ∇f(p − 1) ≡ (−1)^{p−1}f(p − 1) ≡ f(p − 1) mod p.

Now take f = S_{I} and apply Theorem 4.2.

Define, for each prime p, a map χ_{p} : ℌ^{1} → Z/pZ by χ_{p}(w) = ρ_{p−1}(w). Then we can use the commutative diagram (14) to restate Theorem 4.6 in the following “algebraic” form, which corresponds to the duality theorem for multiple zeta values as formulated in Corollary 6.2 of [14].

Theorem 4.7. As elements of Z/pZ, χ_{p}(w) = χ_{p}(ψ(w)) for words w of ℌ^{1}.

For example, since ψ(x^{2}y^{3}) = −x^{2}y^{3} − xy^{4} − yxy^{3} − y^{5}, we have

A_{(3,1,1)}(p−1) ≡ −A_{(3,1,1)}(p−1)−A_{(2,1,1,1)}(p−1)−A_{(1,2,1,1)}(p−1)−A_{(1,1,1,1,1)}(p−1) mod p.

(In fact, for p > 6 it follows from Theorem 7.1 below that both sides are congruent mod p to \frac{1}{2}B_{p−5}, where B_{i} is the ith Bernoulli number.)

5 Harmonic Sums of Height One

Following the terminology of [16], we say a word of ℌ^{1} of the form x^{h−1}y^{k} has height one. We shall call the corresponding multiple harmonic sums A_{(h,1,...,1)}(n) sums of height one. Harmonic sums of this form have a number of special properties, which we discuss in this section.

In this section only we use superscripts for repetition in compositions, so (n, 1^{k}) means the composition of weight n + k with k repetitions of 1. For compositions of this form, we have the following result relating the two kinds of harmonic sums mod p.

Theorem 5.1. For any prime p > k,

S_{(h,1^{k−1})}(p − 1) ≡ (−1)^{h}A_{(h,1^{k−1})}(p − 1) mod p.

Proof. Equate parts (1) and (2) of Theorem 3.1 and apply the homomorphism ρ_{p−1} to get

(−1)^{ℓ(I)}SĪ(p − 1) = ∑_{I_{1}⊔···⊔I_{l}=I}(−1)^{l}A_{I_{1}}(p − 1) ⋯ A_{I_{l}}(p − 1)  (16)

for any p. Now set I = (1^{k−1}, h) in equation (16) and reduce both sides mod p. The hypothesis insures that all terms on the right-hand side are zero mod p except the one with l = 1, and so we have

(−1)^{k−1}S_{(h,1^{k−1})}(p − 1) ≡ A_{(1^{k−1},h)}(p − 1) mod p,

and the conclusion follows by Theorem 4.5.

Combining the preceding result with the duality theorem gives the following congruence. It can be compared with Theorem 4.4 of [13], which asserts that ζ(h + 1, 1^{k−1}) = ζ(k + 1, 1^{h−1}) for positive integers h and k.

Theorem 5.2. If p is a prime with p > max{k, h}, then

A_{(h,1^{k−1})}(p − 1) ≡ A_{(k,1^{h−1})}(p − 1) mod p.

Proof. First note that (h, 1^{k−1})^{∗} = (1^{h−1}, k). So, combining Theorems 4.6 and 4.5,

S_{(h,1^{k−1})}(p − 1) ≡ −S_{(1^{h−1},k)}(p − 1) ≡ (−1)^{h+k}S_{(k,1^{h−1})}(p − 1) mod p.  (17)

Now by the preceding result

S_{(h,1^{k−1})}(p − 1) ≡ (−1)^{h}A_{(h,1^{k−1})}(p − 1) mod p,
S_{(k,1^{h−1})}(p − 1) ≡ (−1)^{k}A_{(k,1^{h−1})}(p − 1) mod p,

so the conclusion follows from congruence (17).

The height one harmonic sums can be written in terms of Stirling numbers. The (unsigned) Stirling numbers of the first kind (Stirling cycle numbers) are given by

\left[{n \atop k}\right] = number of permutations of \{1, 2, …, n\} with k disjoint cycles,

and the Stirling number of the second kind (Stirling subset numbers) are given by

\left\{{n \atop k}\right\} = number of partitions of \{1, 2, …, n\} with k blocks.

For basic properties of Stirling numbers see, e.g., [10]. Note that

\left[{n + 1 \atop k + 1}\right] = e_{n−k}(1, 2, …, n),

since each side is the coefficient of x^{k} in the expansion of x(x + 1) ⋯ (x + n). Hence

\left[{n + 1 \atop k + 1}\right] = n! ∑_{n≥j_{1}>···>j_{n−k}≥1} \frac{j_{1} ⋯ j_{n−k}}{n!} = n! ∑_{n≥i_{1}>···>i_{k}≥1} \frac{1}{i_{1} ⋯ i_{k}} = n!A_{(1^{k})}(n). (18)

An immediate consequence is the following result, which expresses height one sums in terms of Stirling numbers of the first kind.

Theorem 5.3. For positive integers h, k, and n,

A_{(h,1^{k−1})}(n) = ∑_{j=k}^{n} \frac{\left[{j \atop k}\right]}{j^{h−1}j!}.

Proof. We have

A_{(h,1^{k−1})}(n) = ∑_{n≥i_{1}>···>i_{k}≥1} \frac{1}{i_{1}^{h}i_{2} ⋯ i_{k}} = ∑_{j=k}^{n} \frac{1}{j^{h}} A_{(1^{k−1})}(j − 1) = ∑_{j=k}^{n} \frac{\left[{j \atop k}\right]}{j^{h}(j − 1)!}

(where we used equation (18) in the last step), from which the conclusion follows.

In doing computations, the following mod p result is often useful.

Theorem 5.4. For prime p and positive integers h, k < p,

A_{(h,1^{k−1})}(p − 1) ≡ ∑_{j=1}^{p−k}(−1)^{j}(−j)^{p−h}(j − 1)!\left\{{p − k \atop j}\right\} mod p.

Proof. We start by setting n = p−1 and reversing the order of summation in the preceding result:

A_{(h,1^{k−1})}(p − 1) = ∑_{j=1}^{p−k} \frac{\left[{p−j \atop k}\right]}{(p − j)^{h−1}(p − j)!}.

By Fermat’s theorem, (p − j)^{1−h} ≡ (p − j)^{p−h} ≡ (−j)^{p−j} mod p. Also, since

(−1)^{j−1} ≡ \binom{p − 1}{j − 1} ≡ \frac{(p − 1)!}{(j − 1)!(p − j)!} mod p,

it follows that

\frac{1}{(p − j)!} ≡ (−1)^{j}(j − 1)! mod p

since (p − 1)! ≡ −1 mod p by Wilson’s theorem. Hence

A_{(h,1^{k−1})}(p − 1) ≡ ∑_{j=1}^{p−k}(−1)^{j}(j − 1)!(−j)^{p−h}\left[{p − j \atop k}\right] mod p.  (19)

The conclusion then follows from congruence (19) and a mod p relation between the two kinds of Stirling numbers:

\left[{n \atop k}\right] ≡ \left\{{p − k \atop p − n}\right\} mod p

for prime p and 1 ≤ k ≤ n ≤ p − 1, which follows by induction on n using the recurrence relations for the two kinds of Stirling numbers.

6 Results for Short Lengths

In this section we prove some results about the sums S_{I}(p − 1) for ℓ(I) ≤ 5, which will be useful for the calculations of the next section. (Similar results hold for the A_{I}(p − 1), but the S_{I}(p − 1) are more convenient in view of Theorem 4.6.) Henceforth we will assume that all congruences are mod p. The following result expresses S_{I}(p − 1) in terms of a Bernoulli number when ℓ(I) = 2 (cf. [29], Theorem 3.1).

Theorem 6.1. For i, j positive and prime p > i + j + 1,

S_{(i,j)}(p − 1) ≡ \frac{(−1)^{i}}{i + j} \binom{i + j}{i}B_{p−i−j}.

Proof. We use the standard identity expressing sums of powers in terms of Bernoulli numbers (see, e.g., [19]):

∑_{a=1}^{n−1} a^{r} = \frac{1}{r + 1} ∑_{k=0}^{r} \binom{r + 1}{k}B_{k}n^{r+1−k}.  (20)

Using Fermat’s theorem and equation (20), we have

S_{(i,j)}(p − 1) ≡ A_{(i,j)}(p − 1) = ∑_{a=1}^{p−1} \frac{1}{a^{i}} ∑_{b=1}^{a−1} \frac{1}{b^{j}} ≡ ∑_{a=1}^{p−1} \frac{1}{a^{i}} ∑_{b=1}^{a−1} b^{p−1−j}

= ∑_{a=1}^{p−1} \frac{1}{a^{j}} \frac{1}{p − j} ∑_{k=0}^{p−1−j} \binom{p − j}{k}B_{k}a^{p−j−k} = \frac{1}{p − j} ∑_{k=0}^{p−1−j} \binom{p − j}{k}B_{k} ∑_{a=1}^{p−1} a^{p−i−j−k}.

Now ∑_{a=1}^{p−1} a^{p−i−j−k} ≡ 0 unless k = p − i − j. So the sum reduces to

S_{(i,j)}(p − 1) ≡ \frac{1}{p − j} \binom{p − j}{p − i − j}B_{p−i−j}(p − 1) ≡ \frac{1}{j}\binom{p − j}{i}B_{p−i−j},

from which the conclusion follows.

Since odd Bernoulli numbers are zero, this result implies our earlier observation that S_{(i,j)}(p − 1) ≡ 0 when i + j is even. Note also that it implies S_{(i,1)}(p − 1) ≡ B_{p−1−i} for i even, so we can restate it as

S_{(i,j)}(p − 1) ≡ \frac{(−1)^{i}}{i + j} \binom{i + j}{i}S_{(i+j−1,1)}(p − 1),  (21)

i.e., all double sums of odd weight n can be written in terms of S_{(n−1,1)}(p − 1). In fact, if the weight is odd we can write all triple sums in terms of the same quantity (cf. [29], Theorem 3.5).

Theorem 6.2. If n = i + j + k is odd and p > n + 1, then

S_{(i,j,k)}(p − 1) ≡ \frac{1}{2n} [(−1)^{i}\binom{n}{i} + (−1)^{i+j}\binom{n}{i + j}] S_{(n−1,1)}(p − 1).

Proof. From Theorem 3.1 it follows that

A_{I}(m) = ∑_{I_{1}⊔I_{2}⊔···⊔I_{l}=I}(−1)^{ℓ(I)−l}SĪ_{1}(m)SĪ_{2}(m) ⋯ SĪ_{l}(m)  (22)

for any composition I and positive integer m. In particular, for ℓ(I) = 3 we have

A_{(i,j,k)}(m) = S_{(i)}(m)S_{(j)}(m)S_{(k)}(m) − S_{(j,i)}(m)S_{(k)}(m) − S_{(i)}(m)S_{(k,j)}(m) + S_{(k,j,i)}(m).

But also, from equation (13),

A_{(i,j,k)}(m) = S_{(i,j,k)}(m) − S_{(i+j,k)}(m) − S_{(i,j+k)}(m) + S_{(i+j+k)}(m).

In the case m = p − 1, this gives the congruence

S_{(k,j,i)}(p − 1) ≡ S_{(i,j,k)}(p − 1) − S_{(i+j,k)}(p − 1) − S_{(i,j+k)}(p − 1),

using Theorem 4.3, and if in addition i + j + k is odd, we have

2S_{(i,j,k)}(p − 1) ≡ S_{(i+j,k)}(p − 1) + S_{(i,j+k)}(p − 1)

from Theorem 4.5. Now use congruence (21).

For a composition I = (i_{1}, i_{2}, …, i_{k}) of odd weight and length k > 1 it is convenient to define

C(I) = ∑_{j=1}^{k−1}(−1)^{i_{1}+···+i_{j}} \binom{|I|}{i_{1} + ⋯ + i_{j}},  (23)

so Theorem 6.2 says that

S_{I}(p − 1) ≡ \frac{1}{2n}C(I)S_{(n−1,1)}(p − 1)

when n = |I| is odd and ℓ(I) = 3. It is easy to show that the function C(I) mirrors the properties of S_{I}(p − 1) with regard to reversal and duality, i.e., C(Ī) = −C(I) and C(I^{∗}) = −C(I).

In the even-weight case, we can express all length-4 sums in terms of triple sums and products of lower-weight sums as follows.

Theorem 6.3. If n = i + j + k + l is even and p > n + 1, then

2S_{(i,j,k,l)}(p − 1) ≡ S_{(i+j,k,l)}(p − 1) + S_{(i,j+k,l)}(p − 1)+ S_{(i,j,k+l)}(p − 1) + S_{(i,j)}(p − 1)S_{(k,l)}(p − 1).

Proof. From equation (22) with ℓ(I) = 4,

A_{(i,j,k,l)}(m) = −S_{(l,k,j,i)}(m) + S_{(i)}(m)S_{(l,j,k)}(m) + S_{(j,i)}(m)S_{(l,k)}(m) + S_{(k,j,i)}(m)S_{(k)}(m)

− S_{(i)}(m)S_{(j)}(m)S_{(l,k)}(m) − S_{(i)}(m)S_{(k,j)}(m)S_{(l)}(m) − S_{(j,i)}(m)S_{(k)}(m)S_{(l)}(m)

+ S_{(i)}(m)S_{(j)}(m)S_{(k)}(m)S_{(l)}(m).

Set m = p − 1 and reduce mod p to get

A_{(i,j,k,l)}(p − 1) ≡ −S_{(l,k,j,i)}(p − 1) + S_{(j,i)}(p − 1)S_{(l,k)}(p − 1).

But equation (13) gives, after reduction mod p,

A_{(i,j,k,l)}(p − 1) ≡ S_{(i,j,k,l)}(p − 1) − S_{(i+j,k,l)}(p − 1) − S_{(i,j+k,l)}(p − 1) − S_{(i,j,k+l)}(p − 1),

and the conclusion follows by the use of Theorem 4.5.

If we specialize the preceding result to the case k = i, l = j, we have

2S_{(i,j,i,j)}(p − 1) ≡ S_{(i+j,i,j)}(p − 1) + S_{(i,i+j,j)}(p − 1) + S_{(i,j,i+j)}(p − 1) + S_{(i,j)}(p − 1)^{2}.

But the sum of the first three terms on the right-hand side is zero mod p by Theorem 4.4, so we have

2S_{(i,j,i,j)}(p − 1) ≡ S_{(i,j)}(p − 1)^{2}.  (24)

We note that we also have A_{(i,j,i,j)}(p − 1) ≡ S_{(i,j,i,j)}(p − 1), which follows from equation (13), Theorem 4.4, and the comments following Theorem 4.5. If i and j have the same parity, then i + j is even and the right-hand side of (24) is zero mod p by Theorem 4.5, so in this case

S_{(i,j,i,j)}(p − 1) ≡ A_{(i,j,i,j)}(p − 1) ≡ 0.

This proves the case n = 2 of the first part of Conjecture 3.9 of [29].

It is evident that the ideas of the two preceding results can be used to write S_{I}(p − 1), where |I| and ℓ(I) are of the same parity, in terms of sums of shorter lengths, together with products of sums of lower weight. We state one more result of this type, since we need it for our computations in weight 9; we omit the proof, which is straightforward.

Theorem 6.4. If I = (i, j, k, l, m) is a composition of odd weight n and p > n + 1, then

2S_{I}(p − 1) ≡ S_{(i+j,k,l,m)}(p − 1) + S_{(i,j+k,l,m)}(p − 1) + S_{(i,j,k+l,m)}(p − 1) + S_{(i,j,k,l+m)}(p − 1)

− \frac{1}{2n}C(I)S_{(n−1,1)}(p − 1) + S_{(i,j)}(p − 1)S_{(k,l,m)}(p − 1) + S_{(i,j,k)}(p − 1)S_{(l,m)}(p − 1),

where C(I) is given by equation (23).

7 Calculations in Low Weights

In this section, we find, for n ≤ 9, sets of quantities that generate all multiple harmonic sums S_{I}(p − 1) of weight n mod p when p > n + 1. In fact, all our generators will be sums of the form S_{(2h,1,...,1)}(p − 1) (≡ A_{(2h,1,...,1)}(p − 1) by Theorem 5.1), or products of such sums. To make the notation less cumbersome we will use an abbreviated form in referring to specific sums, e.g., we write S_{221} instead of S_{(2,2,1)}(p − 1). We will also assume that p > |I| + 1 in considering any sum S_{I}(p − 1).

The congruence (15) implies S_{I}(p − 1) ≡ 0 when I has length 1 or |I|, so the only sums S_{I}(p − 1) with |I| ≤ 3 that are (possibly) nonzero mod p are S_{21} ≡ B_{p−3} and S_{12} ≡ −B_{p−3}. Now p divides the numerator of B_{p−3} only for certain irregular primes p, the only examples with p < 1.2 × 10^{7} being p = 16, 843 and p = 2, 124, 679 [18, 4, 3].

For I of weight 4 we have S_{I}(p − 1) ≡ 0; this follows from congruence (15) if ℓ(I) = 1 or 4, by the remarks following Theorem 4.5 if ℓ(I) = 2, and by duality if ℓ(I) = 3 (since in that case ℓ(I^{∗}) = 2).

In weight 5, it suffices by duality to consider S_{I}(p − 1) with ℓ(I) ≤ 3. Theorems 6.1 and 6.2 give the following result, which implies that all weight 5 sums vanish mod p if and only if p divides the numerator of B_{p−5}; the only known p for which this happens is p = 37, and this is the only such p < 1.2 × 10^{7} [3].

Theorem 7.1. All S_{I}(p − 1) with |I| = 5 are multiples of S_{41} ≡ B_{p−5}. In particular, S_{32} ≡ −2S_{41}, S_{311} ≡ −\frac{1}{2}S_{41}, and S_{221} ≡ \frac{3}{2}S_{41}.

For |I| = 6, it follows from the remarks after Theorem 4.5 and duality that S_{I}(p−1) ≡ 0 unless ℓ(I) = 3 or 4. By duality it suffices to consider length 3. Here we have the following result, which implies that all harmonic sums of weight 6 vanish if and only if p divides B_{p−3}.

Theorem 7.2. All the S_{I}(p − 1) with |I| = 6 are multiples of S_{411} ≡ −\frac{1}{6}B_{p−3}^{2}. In particular, S_{141} ≡ −2S_{411}, S_{312} ≡ −S_{411}, S_{321} ≡ −2S_{411}, and S_{231} ≡ 3S_{411}.

Proof. From Theorem 4.4, the symmetric sum

S_{411} + S_{141} + S_{114} ≡ 2S_{411} + S_{141}

is congruent to zero, from which the statement about S_{141} follows. For the same reason

S_{3111} + S_{1311} + S_{1131} + S_{1113} ≡ 2S_{3111} + 2S_{1311}

is congruent to zero; applying duality, we get S_{411} + S_{312} ≡ 0. Theorem 4.4 also gives

S_{321} + S_{231} ≡ −S_{312} ≡ S_{411}  (25)

Now multiplying in QSym and reducing mod p, we have

0 ≡S_{1}S_{221}
≡S_{1221} + S_{2121} + 2S_{2211} − S_{321} − S_{231} − S_{222}
≡S_{2121} + 2S_{2211} − S_{321} − S_{231}.

Apply duality (and Theorem 4.5) to obtain from this

3S_{321} + 2S_{231} ≡ 0,  (26)

and solve congruences (25) and (26) to obtain S_{321} and S_{231} in terms of S_{411}.

Finally, S_{2121} ≡ \frac{1}{2}S_{21}^{2} by congruence (24), while from duality we have S_{2121} ≡ −S_{231}. Since we’ve already shown S_{231} ≡ 3S_{411}, the congruence S_{21}^{2} ≡ −6S_{411} follows.

In weight 7, we need only consider sums of length 4 or less. By Theorems 6.1 and 6.2 we can express all sums of length 2 and 3 in terms of S_{61} ≡ B_{p−7}, as follows.

S_{52} ≡ − 3S_{61}  (27)
S_{43} ≡ 5S_{61}  (28)
S_{511} ≡ − S_{61}  (29)
S_{421} ≡ 3S_{61}  (30)
S_{412} ≡ S_{61}  (31)
S_{241} ≡ 2S_{61}  (32)
S_{331} ≡ − 2S_{61}  (33)
S_{322} ≡ − 4S_{61}  (34)

For the length 4 sums we have the following result.

Theorem 7.3. The length 4 harmonic sums of weight 7 can be written in terms of S_{61} ≡ B_{p−7} and S_{4111}. In particular S_{3121} ≡ S_{2221} ≡ S_{4111}, and

S_{1411} ≡ 3S_{61} − 3S_{4111}
S_{1321} ≡ 9S_{61} − 3S_{4111}
S_{1312} ≡ −9S_{61} + 5S_{4111}
S_{3211} ≡ −6S_{61} + S_{4111}.

Proof. Duality gives S_{1411} ≡ S_{3112}, S_{3121} ≡ S_{2311}, and S_{2212} ≡ S_{1321}. Thus, it suffices to consider the seven length-four sums S_{4111}, S_{1411}, S_{3121}, S_{2212}, S_{1312}, S_{2221}, and S_{3211}. We can obtain relations among these sums and S_{61} by multiplying lower-weight sums in QSym, reducing mod p, and then applying congruences (27-34) above to get all terms of length three or less in terms of S_{61}. For example, multiplying S_{1} by S_{411} gives

3S_{61} ≡ S_{1411} + 3S_{4111}.  (35)

Similarly, consideration of the products S_{2}S_{311}, S_{2}S_{221}, S_{21}S_{31}, and S_{11}S_{32} gives respectively

−3S_{61} ≡ 2S_{3121} + S_{3211} + S_{1411}  (36)
9S_{61} ≡ 3S_{2221} + S_{2212}  (37)
−3S_{61} ≡ −S_{1312} + 3S_{3121} + 2S_{3211}  (38)
−3S_{61} ≡ S_{1411} + S_{2212} + S_{1312} + S_{3211}.  (39)

Finally, multiplying S_{1} by S_{3111} and using duality gives

−3S_{61} ≡ S_{4111} + S_{1411} + S_{3211} + S_{3121}  (40)

The six congruences (35-40) can then be solved for S_{61} and S_{4111} to obtain the conclusion.

Remark. While it does not appear that S_{4111} is a multiple of S_{61}, we have not been able to prove this. There is no known prime p for which B_{p−7} ≡ 0; in particular, B_{p−7} ≢ 0 for all p < 1.2 × 10^{7} [3].

In weight 8, it suffices by duality to consider I with ℓ(I) ≤ 4. By Theorem 6.3, we can write all length 4 sums in terms of triple sums and S_{41}S_{21}, and of course all double sums are zero. So it is enough to consider length 3, where we have the following result.

Theorem 7.4. All length 3, weight 8 sums can be written in terms of S_{611} and S_{41}S_{21} ≡ B_{p−5}B_{p−3}. In particular,

S_{521} ≡ S_{611} + S_{41}S_{21}  (41)
S_{512} ≡ \frac{1}{2}(−7S_{611} − S_{41}S_{21})  (42)
S_{431} ≡ \frac{1}{2}(−25S_{611} − 9S_{41}S_{21})  (43)
S_{413} ≡ \frac{1}{2}(5S_{611} + S_{41}S_{21})  (44)
S_{332} ≡ S_{422} ≡ 10S_{611} + 2S_{41}S_{21}.  (45)

Proof. Consideration of the products S_{1}S_{211111} ≡ 0 and S_{1}S_{121111} ≡ 0, using duality, gives respectively

S_{611} + S_{521} + S_{431} + S_{341} + S_{251} + S_{161} ≡ 0,  (46)
S_{521} + S_{512} + S_{422} + S_{332} + S_{242} + S_{152} ≡ 0.  (47)

Now from symmetry (Theorem 4.4), S_{161} = −2S_{611}, S_{251} ≡ −S_{521} − S_{512}, and S_{341} ≡ −S_{431} − S_{413}. Using these facts, congruences (46-47) reduce to

S_{413} ≡ S_{611} − S_{512},  (48)
S_{332} ≡ S_{422}.  (49)

Now consider the product S_{1}S_{31111} ≡ 0. Using duality, this gives

5S_{611} + S_{512} ≡ S_{4211} + S_{3311} + S_{2311}.

Using Theorem 6.3, the right-hand side can be expressed in terms of triple sums and S_{41}S_{21}, and then applying the preceding relations we obtain

S_{521} ≡ −6S_{611} − 2S_{512}.  (50)

Applying similar techniques to the product S_{2}S_{2111} and using congruences (48-50) gives congruences (41), (42), and (44).

Finally, using duality on the product S_{2}S_{2112} ≡ 0 gives

0 ≡ 4S_{1421} + 2S_{4112} + 2S_{2312} + S_{1331}.

Now rewrite this using Theorem 6.3 and apply the previously established relations to obtain (43); congruence (45) then follows.

Remark. It cannot be the case that S_{611} = uS_{41}S_{21}, where u is a unit of Z/pZ for all p > 9, since when p = 37 we have S_{611} ≡ 7 and S_{41} ≡ 0.

For sums of weight 9, duality allows us to restrict attention to S_{I}(p−1) with ℓ(I) ≤ 5. Using Theorem 6.4 (and Theorem 7.2), we can rewrite the length 5 sums in terms of length 4 sums, S_{81}, and the product S_{411}S_{21}. So it is enough to consider the sums S_{I}(p − 1) with ℓ(I) = 4, for which we have the following result.

Theorem 7.5. All length 4, weight 9 harmonic sums can be written in terms of the three quantities S_{6111}, S_{81} ≡ B_{p−9}, and S_{21}S_{411} ≡ −\frac{1}{6}B_{p−3}^{3}. In particular,

S_{1611} ≡ −3S_{6111} + \frac{80}{9}S_{81}  S_{5211} ≡ S_{6111} − \frac{310}{27}S_{81} + \frac{1}{3}S_{21}S_{411}
S_{5112} ≡ −4S_{6111} + \frac{190}{27}S_{81} − \frac{1}{3}S_{21}S_{411}  S_{5121} ≡ S_{6111} − \frac{70}{27}S_{81} + \frac{1}{3}S_{21}S_{411}
S_{2511} ≡ 2S_{6111} − \frac{89}{27}S_{81} − \frac{1}{3}S_{21}S_{411}  S_{2151} ≡ −7S_{6111} + \frac{544}{27}S_{81} − \frac{1}{3}S_{21}S_{411}
S_{1521} ≡ −3S_{6111} + \frac{137}{9}S_{81} − S_{21}S_{411}  S_{4311} ≡ S_{6111} + \frac{13}{3}S_{81}
S_{4131} ≡ −6S_{6111} + \frac{56}{3}S_{81} − S_{21}S_{411}  S_{4113} ≡ 7S_{6111} − \frac{133}{9}S_{81} + S_{21}S_{411}
S_{3411} ≡ −2S_{6111} − \frac{20}{9}S_{81}  S_{3141} ≡ 8S_{6111} − \frac{182}{9}S_{81} + S_{21}S_{411}
S_{1431} ≡ 4S_{6111} − \frac{64}{3}S_{81} + S_{21}S_{411}  S_{4221} ≡ S_{6111} + \frac{82}{27}S_{81} − \frac{1}{3}S_{21}S_{411}
S_{4212} ≡ −4S_{6111} + \frac{617}{27}S_{81} − \frac{2}{3}S_{21}S_{411}  S_{4122} ≡ 3S_{6111} − \frac{370}{27}S_{81} + \frac{1}{3}S_{21}S_{411}
S_{2421} ≡ 2S_{6111} − \frac{124}{27}S_{81} + \frac{4}{3}S_{21}S_{411}  S_{2412} ≡ −2S_{6111} + \frac{110}{9}S_{81}
S_{2241} ≡ \frac{122}{27}S_{81} − \frac{2}{3}S_{21}S_{411}  S_{3321} ≡ −2S_{6111} + \frac{290}{27}S_{81} − \frac{2}{3}S_{21}S_{411}
S_{3312} ≡ 2S_{6111} − \frac{289}{27}S_{81} + \frac{1}{3}S_{21}S_{411}  S_{3231} ≡ −\frac{292}{27}S_{81} + \frac{4}{3}S_{21}S_{411}
S_{2331} ≡ \frac{1}{9}S_{81} − S_{21}S_{411}  S_{3213} ≡ 4S_{6111} − \frac{64}{3}S_{81}
S_{3132} ≡ −\frac{43}{27}S_{81} − \frac{2}{3}S_{21}S_{411}  S_{2322} ≡ −\frac{28}{3}S_{81}
S_{3222} ≡ −6S_{81}.

Proof. There are 56 length-4 sums, but by reversal (Theorem 4.5) we can reduce to 28 of them. Next we go from 28 length-4 sums to 14 length-4 sums, together with S_{81}, by considering various products in QSym. For example, from the products S_{1}S_{422}, S_{2}S_{421}, and S_{2}S_{412} respectively, we obtain the relations

\frac{23}{3}S_{81} ≡ −S_{2241} + S_{4122} + S_{4212} + S_{4221}
\frac{73}{3}S_{81} ≡ S_{2421} + 2S_{4221} + S_{4212}
\frac{23}{3}S_{81} ≡ S_{2412} + S_{4212} + 2S_{4122}

which we can use to write S_{2241}, S_{2421}, and S_{2412} in terms of S_{4221}, S_{4212}, S_{4122}, and S_{81}. Similarly, we eliminate S_{1611}, S_{2511}, S_{2151}, S_{1521}, S_{3411}, S_{3141}, S_{1431}, S_{2331}, S_{3213}, S_{3132}, and S_{2322}. Now we consider the eight products S_{1}S_{311111}, S_{1}S_{221111}, S_{1}S_{131111}, S_{1}S_{113111}, S_{1}S_{212111}, S_{1}S_{211211}, S_{1}S_{211121}, and S_{1}S_{122111}. Using duality and rewriting in terms of our 14 length-4 sums, we have the relations

\frac{28}{3}S_{81} ≡ 2S_{6111} + S_{5121} + S_{5112} + S_{4131} + S_{4113}
\frac{11}{3}S_{81} ≡ S_{5211} + S_{4221} + S_{4212} − S_{3321}
\frac{29}{3}S_{81} ≡ −S_{5112} − 2S_{4122} + S_{3312}
−\frac{61}{3}S_{81} ≡ −S_{4113} + S_{4122} + 2S_{3312}
\frac{4}{3}S_{81} ≡ S_{4311} − S_{4221} + S_{3321} + S_{3312}
11S_{81} ≡ −S_{4113} + S_{3141} + S_{4311} + S_{3321} + S_{3231} + S_{4122} + S_{4212} + S_{4221}
−13S_{81} ≡ S_{5211} + S_{5112} + S_{5121} + S_{4122} − S_{4221} − S_{3231} − S_{3321} − S_{3312}
−6S_{81} ≡ S_{3222}.

We can use these congruences to solve for all the length-4 sums in terms of the seven quantities S_{81}, S_{6111}, S_{5211}, S_{5112}, S_{5121}, S_{4311}, and S_{4221}.

From duality, S_{41211} ≡ S_{33111}. Expanding out both sides using Theorem 6.4, we obtain the congruence

S_{5211} + S_{4311} + S_{4131} + S_{4122} ≡ S_{6111} + S_{3411} + S_{3321} + S_{3312},

which (after rewriting in terms of our seven chosen quantities), allows us to solve for S_{4221} in terms of the remaining six quantities. Now apply Theorem 6.4 similarly to the duality relations S_{41112} ≡ S_{15111}, S_{12411} ≡ S_{31122}, and S_{21411} ≡ S_{31131} to obtain respectively

−S_{4311} + 2S_{5121} + S_{5211} − 2S_{61111} + 21S_{81} ≡ S_{21}S_{411}  (51)
3S_{4311} − S_{5121} + 4S_{5211} − 6S_{61111} + \frac{91}{3}S_{81} ≡ S_{21}S_{411}  (52)
−3S_{4311} + 2S_{5121} + S_{5211} + \frac{89}{3}S_{81} ≡ S_{21}S_{411}.  (53)

Add 3 times congruence (51) to congruence (52), and compare the resulting expression for S_{21}S_{411} with that obtained by adding congruence (53) to (52); the result is

S_{5121} ≡ S_{5211} + \frac{80}{9}S_{81}.  (54)

Next substitute congruence (54) into the result of subtracting congruence (52) from (51) to get

S_{4311} ≡ S_{6111} + \frac{13}{3}S_{81}.  (55)

Using congruences (54) and (55), any of the congruences (51-53) can be used to write S_{5211} in terms of S_{6111}, S_{81}, and S_{21}S_{411}.

Finally, consideration of the product S_{11}S_{2221} gives the relation

3S_{3231} + 3S_{3321} + 3S_{4221} + 2S_{3222} + 2S_{2331} + S_{2241} + S_{2421} ≡ 3S_{31221} + 3S_{32121} + 2S_{32211} + 2S_{22131} + S_{21231} + S_{23121},

which can be used to write S_{5112} in terms of S_{6111}, S_{81}, and S_{21}S_{411}.

Remark. The only primes p < 1.2 × 10^{7} with B_{p−9} ≡ 0 are p = 67 and p = 877 [3]. Here is a table of the values of our generators at these primes, and at p = 16, 843, computed using Mathematica and Theorem 5.4.

\begin{matrix}p & 67 & 877 & 16,843 \\ S_{6111} & 7 & 253 & 16,690 \\ S_{81} & 0 & 0 & 14,820 \\ S_{21}S_{411} & 4 & 354 & 0 \end{matrix}

References

[1] J. Blümlein and S. Kurth, Harmonic sums and Mellin transforms up to two-loop order, Phys. Rev. D 60 (1999), art. 01418.

[2] D. Bowman and D. M. Bradley, Multiple polylogarithms: a brief survey, in q-Series with Applications to Combinatorics, Number Theory, and Physics, Contemp. Math., Vol. 291, American Mathematical Society, Providence, 2001, pp. 71-92.

[3] J. Buhler, personal communication.

[4] J. Buhler, R. Crandall, R. Ernvall, and T. Metsänkylä, Irregular primes and cyclotomic invariants up to four million, Math. Comp. 61 (1993), 151-153.

[5] R. Ehrenborg, On posets and Hopf algebras, Adv. Math. 119 (1996), 1-25.

[6] L. Euler, Demonstratio insignis theorematis numerici circa unicias potestatum binomialium, Nova Acta Acad. Sci. Petropol. 15 (1799/1802), 33-43; reprinted in Opera Omnia, Ser. I, Vol. 16(2), B. G. Teubner, Leipzig, 1935, pp. 104-116.

[7] L. Geissinger, Hopf algebras of symmetric functions and class functions, in Combinatoire et représentation de groupe symmétrique (Strasbourg, 1976), Lecture Notes in Math., Vol. 579, Springer-Verlag, New York, 1977, pp. 168-181.

[8] I. M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. S. Retakh, and J.-Y. Thibon, Noncommutative symmetric functions, Adv. Math. 112 (1995), 218-348.

[9] I. M. Gessel, “Multipartite P-partitions and inner products of skew Schur functions,” in Combinatorics and Algebra, Contemp. Math., Vol. 34, American Mathematical Society, Providence, 1984, pp. 289-301.

[10] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, Reading, Mass., 1994.

[11] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 4th ed., Oxford University Press, London, 1960.

[12] M. Hazewinkel, The algebra of quasi-symmetric functions is free over the integers, Adv. Math. 164 (2001), 283-300.

[13] M. E. Hoffman, Multiple harmonic series, Pacific J. Math. 152 (1992), 275-290.

[14] M. E. Hoffman, The algebra of multiple harmonic series, J. Algebra 194 (1997), 477-495.

[15] M. E. Hoffman, Quasi-shuffle products, J. Algebraic Combin. 11 (2000), 49-68.

[16] M. E. Hoffman, Algebraic aspects of multiple zeta values, preprint math.QA/0309425.

[17] M. E. Hoffman and Y. Ohno, Relations of multiple zeta values and their algebraic expression, J. Algebra 262 (2003), 332-347.

[18] W. Johnson, Irregular primes and cyclotomic invariants, Math. Comp. 29 (1975), 113-120.

[19] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Spring-Verlag, New York, 1982.

[20] C. Kassel, Quantum Groups, Springer-Verlag, New York, 1995.

[21] I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd ed., Oxford University Press, New York, 1995.

[22] C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra 177 (1995), 967-982.

[23] J. W. Milnor and J. C. Moore, On the structure of Hopf algebras, Ann. of Math. (2) 81 (1965), 211-261.

[24] R. Stanley, Enumerative Combinatorics, Vol. 1, Wordsworth and Brooks/Cole, Monterey, California, 1986.

[25] M. Sweedler, Hopf Algebras, W. A. Benjamin, Inc., New York, 1969.

[26] J. A. M. Vermaseren, Harmonic sums, Mellin transforms and integrals, Int. J. Mod. Phys. A 14 (1999), 2037-2076.

[27] M. Waldschmidt, Valeurs zêta multiples. Une introduction, J. Théor. Nombres Bordeaux 12 (2000), 581-595.

[28] D. Zagier, Values of zeta functions and their applications, in First European Congress of Mathematics, Vol. II (Paris, 1992), Birkhäuser, Boston, 1994, pp. 497-512.

[29] J. Zhao, Partial sums of multiple zeta value series I: Generalizations of Wolstenholme’s theorem, preprint math.NT/0301252.