Iiro Honkala
email: honkala@utu.fi

Tero Laihonen

Sanna Ranto

On Locating-Dominating Codes in Binary Hamming Spaces

Keywords: Locating-dominating codes, Hamming space, Identifying codes

Locating faulty processors in a multiprocessor system gives the motivation for locating-dominating codes. We consider these codes in binary hypercubes and generalize the concept for the situation in which we want to locate more than one malfunctioning processor.

Introduction and definitions

Let F = {0, 1} denote the binary field and F n the n-dimensional Cartesian product of it. A code is a subset of F n . The elements of F n (resp. a code) are called words (resp. codewords) and the Hamming distance d(x, y) between two words x, y ∈ F n is the number of coordinate positions in which they differ. The Hamming weight w(x) of a word x ∈ F n is the number of 1's in x. The minimum distance of a code is the smallest distance between any distinct pair of codewords (if the code consists of less than two codewords, then we define the minimum distance to be n + 1). We denote S i (x) = {y ∈ F n | d(x, y) = i} and the Hamming ball B r (x) = ∪ r i=0 S i (x). If X ⊆ F n , we denote by B r (X) the union of the sets B r (x) for x ∈ X. The cardinality of X is denoted by |X| and V (n, r) = |B r (x)|. We say that x r-covers or covers y if d(x, y) ≤ r.

Consider the binary hypercube (or an arbitrary graph). Assume that it is used to model a multiprocessor architecture, and that each node corresponds to a processor and each edge corresponds to a dedicated link between two processors. We choose some of the processors as codewords, and ask each of them to check its r-neighbourhood. Each codeword sends us the symbol 2 if it itself is malfunctioning, 1 if it itself is fine, but at least one processor in its rneighbourhood is malfunctioning, and 0 otherwise. When we have received the reports from all the codewords we wish to locate the malfunctioning processors, under the assumption that there are at most l of them. The integers r and l are given at the outset. This is the classical locating-dominating set problem [START_REF] Haynes | Fundamentals of Domination in Graphs[END_REF] if l = 1 (and then the requirement for the code C, i.e., the set of codewords, is that the sets B r (x) ∩ C are different and nonempty for all x ∈ F n \ C). This leads to the following definition. Definition 1. Let r and l be non-negative integers. A code C ⊆ F n is an (r, ≤ l)-locatingdominating code of type A -an (r, ≤ l)-LDA for short -if for all X ⊆ F n and Y ⊆ F n of size at most l, B r (X)

∩ C = B r (Y ) ∩ C (1)
X ∩ C = Y ∩ C (2)
implies that X = Y .

If X = ∅, then B r (X)∩C = ∅: so, in particular, the previous definition implies that B r (Y )∩C = ∅ whenever Y = ∅.

In the second variant we only consider subsets X and Y of F n \ C. Then X ∩ C and Y ∩ C are empty, (2) becomes void, and (1) takes the simple form B r (X) ∩ C = B r (Y ) ∩ C. This corresponds to a two-step testing procedure: we first fix all the codewords that have sent 2, and then immediately perform a second round, during which we only receive 1's and 0's.

Definition 2. Let r and l be non-negative integers

. A code C ⊆ F n is an (r, ≤ l)-locating- dominating code of type B -an (r, ≤ l)-LDB for short -if for all sets X ⊆ F n \ C and Y ⊆ F n \ C of size at most l, B r (X) ∩ C = B r (Y ) ∩ C implies that X = Y .
When l = 1, both definitions reduce to the definition of an r-locating-dominating code. Such codes have been considered, for instance, in Haynes, Hedetniemi and Slater [START_REF] Haynes | Fundamentals of Domination in Graphs[END_REF] and [START_REF] Slater | Dominating and reference sets in a graph[END_REF][START_REF] Rall | On location-domination numbers for certain classes of graphs[END_REF][START_REF] Slater | Locating dominating sets and locating-dominating sets[END_REF][START_REF] Slater | Fault-tolerant locating-dominating sets[END_REF][START_REF] Charon | Minimizing the size of an identifying or locatingdominating code in a graph is NP-hard[END_REF][START_REF] Charon | Identifying and locating-dominating codes: NPcompleteness results for directed graphs[END_REF].

The smallest cardinality of an (r, ≤ l)-LDA (resp. an (r, ≤ l)-LDB) of length n is denoted by

LA (≤l) r (n) (resp. LB (≤l) r (n)).
Both these concepts are closely related to that of an identifying code: by definition, a code C ⊆ F n is (r, ≤ l)-identifying, if for all X ⊆ F n and Y ⊆ F n of size at most l, the condition B r (X) ∩ C = B r (Y ) ∩ C implies that X = Y . This corresponds to the situation where each codeword only reports back whether it has detected problems in its r-neighbourhood or not (and each reply is therefore 0 or 1). The minimum cardinality of an (r, ≤ l)-identifying code of length n is denoted by M (≤l) r (n). Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] in 1998. Identifying codes in binary hypercubes have been further studied, for instance, in [START_REF] Blass | Bounds on identifying codes[END_REF][START_REF] Blass | On binary codes for identification[END_REF][START_REF] Honkala | On identifying codes in binary Hamming spaces[END_REF][START_REF] Honkala | On the complexity of the identification problem in Hamming spaces[END_REF][START_REF] Honkala | On codes identifying sets of vertices in Hamming spaces[END_REF][START_REF] Laihonen | Codes identifying sets of vertices[END_REF]. For results about identifying codes in other graphs, see, e.g., [START_REF] Cohen | New bounds for codes identifying vertices in graphs[END_REF][START_REF] Cohen | On identifying codes[END_REF].

Clearly, an (r, ≤ l)-identifying code is an (r, ≤ l)-LDA, and an (r, ≤ l)-LDA is an (r, ≤ l)-LDB.

Example 1. (i) Let C be the even-weight code of length n ≥ 5, i.e., it consists of all 2 n-1 words of length n that have even weight. An immediate consequence of Theorem 1 is that C a (1, ≤ ⌊(n + 1)/2⌋)-LDA. Clearly, C is not (1, ≤ 2)-identifying (take X = {100 . . . 0}, Y = {000 . . . 0, 100 . . . 0}).

(ii) The code C = F n-1 ⊕ {0}, n ≥ 2, is a (1, ≤ 2 n-1 )-LDB (and hence a (1, ≤ l)-LDB for all l). Clearly, C is not (1, ≤ 2)-LDA (take X = {(x, 0)} and Y = {(x, 0), (x, 1)} for any x ∈ F n-1 ).

(iii) An (r, ≤ l)-LDA (resp. an (r, ≤ l)-LDB) is always an (r, ≤ k)-LDA (resp. an (r, ≤ k)-LDB) for all k ≤ l.

In what follows we often utilize the following lemma, which is easy to check. Lemma 1. For a, b ∈ F n we have

|B 1 (a) ∩ B 1 (b)| =    n + 1 if a = b 2 if d(a, b) = 1 or 2 0 otherwise.
In Sections 2 and 3 we examine LDAs and LDBs, respectively, when l ≥ 2. Section 4 deals with the case l = 1 and the last section considers linear codes. In this paper, we study mainly the case r = 1.

Bounds and constructions on LDAs

We have the following characterization of the LDAs; cf. [START_REF] Laihonen | Sequences of optimal identifying codes[END_REF].

Theorem 1. Assume that l ≥ 3. A code C ⊆ F n is a (1, ≤ l)-LDA if and only if every element of F n \ C is covered by at least 2l -1 codewords of C.
Proof. Assume first that every element of F n \ C is covered by at least 2l -1 codewords of C. Assume that X and Y are two subsets of F n , each of size at most l, and that

X ∩ C = Y ∩ C and B 1 (X) ∩ C = B 1 (Y ) ∩ C. (3)
Assume that x ∈ X \ C does not belong to Y . Without loss of generality x = 000 . . . 0. As a non-codeword, x is covered by at least 2l -1 codewords, say c 1 , . . . , c 2l-1 ; and without loss of generality, they have been indexed in such a way that c 1 , . . . , c i ∈ X, whereas c i+1 , . . . ,

c 2l-1 / ∈ X (0 ≤ i ≤ l -1). The fact that X ∩ C = Y ∩ C immediately implies that c 1 , . . . , c i ∈ Y and c i+1 , . . . , c 2l-1 /
∈ Y . By (3), the codewords c i+1 , . . . , c 2l-1 are therefore covered by the at most li words of weight two of Y , each covering at most two of the codewords c i+1 , . . . , c 2l-1 . Because 2(li -1) < 2l -1i, there are exactly li words of weight two in Y (together with the remaining i words of weight one).

We first notice that the set X does not contain any word of weight four. Indeed, because X ∩ C = Y ∩ C, and Y does not contain any word of weight four, there is no codeword of weight four in X. Any non-codeword of weight four in X would be covered by at least (2l -1) -4 (> 0) codewords of weight five, which cannot be, because no word in Y could cover a codeword of weight five.

Assume that y ∈ Y \ C has weight two. We show that y ∈ X. By assumption, y is covered by at least 2l -1 codewords, of which at least 2l -3 have weight three; and they all must be covered by the words in X. Because there are no words of weight four in X, all these at least 2l -3 words of weight three must be covered by the at most l -1i words of weight two and three in X.

Because 2l -3 > l -1i for all l ≥ 3, and no word of weight two or three other than y itself covers more than one of these at least 2l -3 words, we conclude that y must belong to X.

We have shown that Y \ C ⊆ X. We already knew that Y ∩ C = X ∩ C ⊆ X, and hence Y ⊆ X. But Y has size l, and therefore Y = X, contradicting the fact that x ∈ X \ Y .

We have therefore shown that C is a (1, ≤ l)-LDA.

Assume conversely that C is a (1, ≤ l)-LDA, and let x ∈ F n \ C be arbitrary. Without loss of generality, x = 000 . . . 0. Assume that the codewords that cover x are c 1 , c 2 , . . . , c j . Let i = ⌈j/2⌉. We can choose i words x 1 , x 2 , . . . , x i ∈ F n \ {x} that together cover all the words c 1 , c 2 , . . . , c j . Then X = {x 1 , x 2 , . . . , x i , x} and Y = {x 1 , x 2 , . . . x i } satisfy ( 1) and ( 2), and both have cardinality at most i + 1 ≤ l, unless j ≥ 2l -1. Hence every non-codeword is covered by at least 2l -1 codewords of C.

Let us denote by K(n, r, µ, ν) the smallest cardinality of a code C ⊆ F n such that every noncodeword is r-covered by at least µ codewords and every codeword is r-covered by at least ν codewords.

From [17, proof of Theorem 1] we get the following lower bound.

Theorem 2. For l ≥ 3,

LA (≤l) 1 (n) = K(n, 1, 2l -1, 1) ≥ (2l -1)2 n n + 2l -1 .
Proof. By the previous theorem it suffices to prove the inequality. Assume that C ⊆ F n attains the bound K(n, 1, 2l -1, 1). We count in two ways the number of pairs (c, x), where c ∈ C, x ∈ F n and d(c, x) ≤ 1. Given c, there are n + 1 choices for x, so the number of such pairs equals (n + 1)|C|. Given x, there are at least 2l -1 choices for c if x is not a codeword, and at least one, if x is a codeword. Hence (n + 1)|C| ≥ (2l -1)(2 n -|C|) + |C|, which gives the claim.

From [START_REF] Laihonen | Sequences of optimal identifying codes[END_REF] we know that

M (≤l) 1 (n) (2l -1)2 n /(n + 1) → 1 for a given l ≥ 3 when n → ∞. Because LA (≤l) 1 (n) ≤ M (≤l) 1
(n), the previous theorem gives the following corollary.

Corollary 1. For a fixed l ≥ 3,

LA (≤l) 1 (n) ∼ (2l -1)2 n n when n → ∞.
We also get the following infinite family of exact values.

Theorem 3. Assume that l ≥ 3. Then LA (≤l) 1 ((2l -1)(2 s -1)) = 2 (2l-1)(2 s -1)-s
for all s = 1, 2, . . ..

Proof.

From [START_REF] Rains | Table of constant weight binary codes[END_REF] we know that for n = (2l -1)(2 s -1) the inequality of Theorem 2 is attained by a linear code whose parity check matrix has as its columns 2l -1 copies of every non-zero element in F s ; cf. the beginning of Section 5.

The direct sum of the codes

C 1 ⊆ F n1 and C 2 ⊆ F n2 is C 1 ⊕ C 2 = {(c 1 , c 2 ) | c 1 ∈ C 1 , c 2 ∈ C 2 } ⊆ F n1+n2 . Theorem 4. Let l ≥ 3. If C is a (1, ≤ l)-LDA then the direct sum C ⊕ F is also a (1, ≤ l)-LDA. Thus LA (≤l) 1 (n) ≤ 2LA (≤l) 1 (n -1).
Proof. The claim follows from Theorem 1 since the direct sum with F preserves the property that each non-codeword is covered by at least 2l -1 codewords.

Bounds and constructions on LDBs

Let us first give a lower bound on the cardinality of a (1, ≤ l)-LDB for l ≥ 2. Because trivially LB (≤l) 1

(1) = 1 and LB (≤l) 1

(2) = 2, we may assume in what follows that n ≥ 3. Let C ⊆ F n . In the sequel, when there is no ambiguity on which code is considered, it is convenient to denote (X ⊆ F n )

I(X) = x∈X (C ∩ B 1 (x)).
This is called the I-set of X and we denote I({v 1 , . . . , v s }) = I(v 1 , . . . , v s ).

We denote

N = F n \ C, C i = {c ∈ C | |I(c)| = i}, N i = {x ∈ N | |I(x)| = i} and C i,j = ∪ j k=i C k and further N i,j = ∪ j k=i N k . Theorem 5. Let 2 ≤ l ≤ n -1. Then LB (≤l) 1 (n) ≥ l n + l -1 2 n . Proof. Assume that C ⊆ F n is a (1, ≤ l)-LDB where 2 ≤ l ≤ n -1.
Let us count in two ways the number of pairs (x, c) where

x ∈ N 1,l-1 , c ∈ C n and d(c, x) = 1. Every x ∈ N 1,l-1 has at least one c ∈ C n in I(x), since otherwise there would exist y i ∈ N ∩ S 2 (x) ∩ B 1 (c i ) for all c i ∈ I(x) and thus I(y 1 , . . . , y |I(x)| ) = I(y 1 , . . . , y |I(x)| , x)
which is a contradiction, since |I(x)| ≤ l -1. On the other hand, each c ∈ C n can have at most one x ∈ N 1,l-1 at distance one from it. Therefore,

|N 1,l-1 | ≤ |C n |. (4)
Next we compute in two ways the number of pairs (x, c) where c ∈ C 1 , x ∈ N l+1,n and d(x, c) = 1. All the non-codewords at distance one from c ∈ C 1 belong to N l+1,n . Indeed, assume that there were a word x at distance one from c such that I(x) = {c 1 , . . . , c i , c} (0 ≤ i ≤ l -1). If i = 0, let y be any word other than x which is at distance 1 from c. Then I(y) = I(y, x). Assume that i ≥ 1. Denoting by y i the unique word other than x such that d(c, y i ) = d(y i , c i ) = 1, we get the contradiction (note that y i ∈ N ) I(y 1 , . . . , y i ) = I(y 1 , . . . , y i , x).

On the other hand, a non-codeword x ∈ N l+1,n can have at most n elements of C 1 at distance one from it. Consequently,

|C 1 | ≤ |N l+1,n |.
Finally, we count the number of pairs (x, c) such that x ∈ F n , c ∈ C and d(x, c) ≤ 1. Now using (4) and the previous inequality, we obtain

|C|(n + 1) = n i=1 i|N i | + n+1 i=1 i|C i | ≥ l|N | -(l -1)|N 1,l-1 | + |N l+1,n | + 2|C| -|C 1 | + (n -2)|C n | ≥ l|N | + 2|C|.
This yields the claim. (n) ≥ 2 n-1 . The claim now follows from Example 1 (ii).

Theorem 7. If C is a (1, ≤ l)-LDB, then C ⊕ F is also a (1, ≤ l)-LDB. In particular, LB (≤l) 1 (n + 1) ≤ 2LB (≤l) 1 (n).
Proof. Suppose C is a (1, ≤ l)-LDB of length n. Divide the words of F n+1 into two layers O 0 and O 1 depending on the last bit of the word, i.e., O i = F n ⊕ {i} for i ∈ F . Only a codeword can have in its I-set a codeword from the other layer than where it itself lies. Thus the I-set of a set of non-codewords on the layer O i has codewords only from the same layer. So, if

|X| ≤ l, then |X ∩ O i | ≤ l for both i ∈ F , and because C is a (1, ≤ l)-LDB, I(X ∩ O i ) ⊆ O i uniquely identifies X ∩ O i for both i ∈ F .
The covering radius of a code C ⊆ F n is defined to be max x∈F n min c∈C d(x, c).

We denote by K(n, R) the smallest cardinality of a code C ⊆ F n such that it has covering radius at most R. For an account of this subject, consult [START_REF] Cohen | Covering Codes[END_REF].

We denote by A(n, d, w) the smallest cardinality of a code of length n and minimum distance d whose codewords all have weight w. For values of this function, see [START_REF] Rains | Table of constant weight binary codes[END_REF]. Denote S i = S i (00 . . . 0).

Theorem 8. For l ≤ n/2 -1 we have

LB (≤l) 1 (n) ≤ K(n, l + 1)(V (n, l) -A(n, 6, l)).
Proof. Let D be a code attaining the value K(n, l + 1), A a code attaining the value A(n, 6, l), and B = B l (00 . . . 0). We shall show that the code The previous theorem is interesting in the light of the well-known conjecture [5, p. 352] that for every fixed R

C = D + (B \ A) = {c + b | c ∈ D, b ∈ B \ A}
lim n→∞ K(n, R)V (n, R) 2 n = 1.
Namely, for every fixed l ≥ 2 Theorems 5 and 8 give the bounds

l n 2 n (1 + f (n)) ≤ LB (≤l) 1 (n) ≤ l + 1 n 2 n (1 + g(n)),
where both f (n) and g(n) tend to zero when n → ∞.

Let us next improve on the lower estimate of Theorem 5 for

√ n + 1 ≤ l ≤ n -1. Lemma 2. Let C ⊆ F n be a (1, ≤ l)-LDB with 2 ≤ l ≤ n -1. If j is a non-negative integer satisfying l -j ≥ 1 and l + j ≤ n, then (l -j)|N 1,l+j | ≤ (n -l + j + 1)|C l-j,n-1 | + (l -j)|C n |.
Proof. Let us count the number of pairs (c, x), where c ∈ C l-j,n , x ∈ N 1,l+j and d(x, c) = 1, in two ways. As mentioned in the proof of Theorem 5, if x ∈ N 1,l-1 , then there exists at least one such pair (c, x).

Let us then concentrate on x ∈ N l,l+j . If there is c ∈ I(x) such that c ∈ C n , then there exists again one sought pair. Assume then that for all c ∈ I(x) we have |I(c)| ≤ n -1. Denote by M l,l+j the subset of N l,l+j which consists of all such elements x.

Let x ∈ M l,l+j and without loss of generality x = 00 . . . 0. Denote by P a maximal subset of

{y ∈ N ∩ S 2 | |I(y) ∩ I(x)| = 2} such that its minimum distance is at least four. Since C is a (1, ≤ l)-LDB, we must have l ≤ |I(x)| -|P |. (5)
Indeed, suppose

|I(x)| -|P | ≤ l -1. Denote by y i a word in N ∩ S 2 such that d(y i , c i ) = 1 for c i ∈ R = I(x) \ I(P )
. Notice that such words y i exist for every c i because x ∈ M l,l+j . Now this leads to

I(P ∪ {y 1 , . . . , y |R| }) = I(P ∪ {y 1 , . . . , y |R| , x})
which is impossible because

|P ∪ {y 1 , . . . , y |R| , x}| = |I(x)| -|P | + 1 ≤ l.
Clearly, by ( 5), 0

≤ |P | ≤ |I(x)| -l ≤ j. Hence, by virtue of (5), |R| = |I(x)| -2|P | ≥ l -|P | ≥ l -j. Since P is maximal, {y ∈ S 2 | |I(y) ∩ R| = 2} ⊆ C,
and consequently, we get at least lj pairs from every x ∈ M l,l+j .

All in all the number of sought pairs is at least

|N 1,l-1 | + |N l,l+j \ M l,l+j | + (l -j)|M l,l+j | = |N 1,l-1 | + |N l,l+j | + (l -j -1)|M l,l+j |.
On the other hand, at distance one from c ∈ C l-j,n-1 (resp. c ∈ C n ) there are at most nl + j + 1 words (resp. one word) of N and hence possibly of N 1,l+j . Thus the number of sought pairs is at most

(n -l + j + 1)|C l-j,n-1 | + |C n |.
Furthermore, one immediately verifies the modification of (4

) that |N 1,l-1 | + |N l,l+j \ M l,l+j | ≤ |C n |.
Multiplying this by lj -1 and adding it to the inequality which we get from the estimates of the number of pairs proves the claim.

Theorem 9. Let √ n + 1 ≤ l ≤ n -1. Denote k = min l 2 -n -1 1 + l + n , n -l -1 .
Then

LB (≤l) 1 (n) ≥ l + k + 1 n + l + k + 1 2 n . Proof. Let C ⊆ F n be a (1, ≤ l)-LDB with √ n + 1 ≤ l ≤ n -1. Obviously, |C|(n + 1) ≥ (l + k + 1)|N | -(k + 1)|N l,l+k | -(l + k)|N 1,l-1 | +|C| + (l -k -1)|C l-k,n-1 | + (n -1)|C n |.
Since l ≤ n -1 we get by (4) that

|C|(n + 1) ≥ (l + k + 1)|N | -(k + 1)|N l,l+k | -(k + 1)|N 1,l-1 | +|C| + (l -k -1)|C l-k,n-1 | + (n -l)|C n |.
The choice of k satisfies

l -k -1 ≥ (k + 1)(n -l + k + 1) l -k and furthermore n -l ≥ k + 1.
Consequently, it is easy to check that we can use Lemma 2 for j = k and hence

|C|(n + 1) ≥ (l + k + 1)|N | + |C|.
The claim follows immediately from this.

If l ≥ 1 2 ( √ 2n 2 + 2n + 1 -1), n ≥ 3, then k = nl -1 and the previous theorem combined with Example 1(ii) and Theorem 6 gives the following result.

Theorem 10. Let n ≥ 3. If l ≥ 1 2 ( √ 2n 2 + 2n + 1 -1), then LB (≤l) 1 (n) = 2 n-1 .
Next we construct some (1, ≤ 2)-LDBs.

Theorem 11. Let n ≥ 5 and C be a code attaining the bound K(n, 3). Then the code To cover this word c we need one more word in the set X. This word cannot have weight one since then it should belong to Y as well, which is impossible. So, without loss of generality, the other word in X is 0111 . . .. But then 0101 . . . and 0011 . . . belong to I(X) but not to I(Y ), which gives the required contradiction.

D = C ∪ {c + x | c ∈ C, x ∈ F n , w(x) = 2} is a (1, ≤ 2
Example 2. The repetition code {0000000, 1111111} has the properties of Theorem 11. Thus we can construct a (1, ≤ 2)-LDB of length 7 and cardinality 44. From this we get by Theorem 7 a (1, ≤ 2)-LDB of length 8 and cardinality 88. We know by [START_REF] Ranto | Two families of optimal identifying codes in binary Hamming spaces[END_REF] 4 On the case l = 1

In this section we examine the case l = 1. We denote

L(n) = LA (≤1) 1 (n) = LB (≤1) 1 (n).
From [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] we know that M (≤1) 1

(n) ≤ nK(n, 2). This implies trivially that L(n) ≤ nK(n, 2). Denote by e 1 the word of weight one whose first coordinate equals one.

Theorem 13. For all n ≥ 4,

L(n + 1) ≤ (2n -1)K(n, 2). Proof. Let C ⊆ F n (n ≥ 4) be a code with covering radius two and K(n, 2) codewords. De- note C 1 = {w ∈ F n | w ∈ S 1 (c) for some c ∈ C} and C 2 = {w ∈ F n | w ∈ S 1 (c) \ {c + e 1 } for some c ∈ C}. We claim that D = C 1 ⊕ {0} ∪ C 2 ⊕ {1} is 1-locating-dominating.
We again denote O i = F n ⊕ {i} for i = 0, 1. By the construction, I(x) = ∅ for all x ∈ F n+1 . Assume that x, y ∈ F n+1 \ D and x = y. It is shown in [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] that C 1 is (1, ≤ 1)-identifying. Hence, if x, y ∈ O 0 , then I(x) = I(y). Let us recall the notion of excess (see, e.g., [START_REF] Cohen | Covering Codes[END_REF]Chapter 6], [START_REF] Van Wee | Improved sphere bounds on the covering radius of codes[END_REF]). Assume that the covering radius of C ⊆ F n is at most 1. We denote the excess on x ∈ F n by E(x) = |I(x)| -1 and

E(X) = x∈X E(x).
Theorem 15.

L(n) ≥

n 2 2 n+1 n 3 + 2n 2 + 3n -2 .

Proof. (Cf. [START_REF] Blass | Bounds on identifying codes[END_REF].) Suppose C is an optimal 1-locating-dominating code of length n. Denote by K the cardinality of C. It is not difficult to check that there can be only four kinds of words in F n :

1. a word which is covered by exactly one codeword, A word of type 3 is called a father. A word of type 4 is called a son; the word x such that I(y) ⊂ I(x) is called its father (it is easy to see that x is uniquely defined). A family consists of a father and its sons. The families, couples and points with excess zero partition the whole space

F n .
Suppose that a father is covered by i codewords. Then there are at most i 2 sons in the family. The average excess on the points in a family whose father is covered by exactly i ≥ 3 codewords is therefore at least

f (i) := i 2 + i -1 i 2 + 1
.

Theorem 6 .

 6 If n ≥ 3 and l ≥ n -1, then LB (≤l) 1 (n) = 2 n-1 .Proof. By Example 1 (iii) and the previous theorem, LB

is a ( 1 ,

 1 ≤ l)-LDB. In the code C there are at most K(n, l + 1)(V (n, l) -A(n, 6, l)) codewords. Suppose there are sets X ⊆ N and Y ⊆ N such that X = Y, |X|, |Y | ≤ l and I(X) = I(Y ). There is a word x ∈ X such that x ∈ Y. Since x ∈ C there exists a codeword c ∈ D such that d(x, c) = l or l + 1. Without loss of generality we can assume that c = 00 . . . 0. If d(x, c) = l, then x is covered by l codewords of weight l -1. None of them can belong to I(Y ) since B l-1 (00 . . . 0) ∩ N = ∅ and non-codewords in S l \ {x} are at least at distance six from x. Suppose now that d(x, c) = l + 1. Then l ≤ |I(x) ∩ S l | ≤ l + 1. If y ∈ Y covers a codeword of weight l in I(x), then the weight of y must be l + 1; and since y = x, y can cover only one codeword of weight l in I(x). Because |Y | ≤ l, this implies that |I(x) ∩ S l | = l, |Y | = l, Y ⊆ S l+1 , and each word in Y covers one codeword from I(x) ∩ S l . If y ∈ Y , then |I(y) ∩ S l | = l + 1, because the minimum distance of non-codewords of weight l is six. As we have already seen (for x whose role y now assumes), this is only possible if y ∈ X. Consequently, X must contain all the l elements of Y together with x / ∈ Y , which is impossible, since |X| ≤ l.

  )-LDB and has cardinality at most K(n, 3)(1 + n 2 ). Proof. Suppose there are X, Y ⊆ F n \ D such that |X|, |Y | ≤ 2, X = Y and I(X) = I(Y ). By the definition of D, every y / ∈ D has distance 1 or 3 to C. We first claim that any word y ∈ Y for which there is a codeword c ∈ C such that d(c, y) = 1 also belongs to X. Indeed, such a word y is covered by n (≥ 5) codewords of D and thus by Lemma 1 no set of size at most two where y does not belong to can cover all those words. Thus in order to have I(X) = I(Y ) we must also have y ∈ X. Since X = Y , we can assume that Y contains a word y / ∈ X, and we can assume that d(y, c) = 3, where c ∈ C. Without loss of generality, c = 0000 . . . and y = 1110 . . .. Then y is covered by the codewords 1100 . . ., 1010 . . . and 0110 . . . of D. If an element x of X ⊆ F n \ D covers at least one these three words, then x has weight one or three. If w(x) = 3, then x ( = y) covers at most one of them. Consequently, there is a word x ∈ X of weight one which covers two of them. But being of weight one, x must also belong to Y . Without loss of generality, x = 1000 . . .. Still we have one codeword c = 0110 . . . which is not in I(x).

  Suppose x ∈ O 0 and y ∈ O 1 . Because x / ∈ D, the structure of C 1 implies that |I(x) ∩ O 0 | ≥ 2 whereas |I(y) ∩ O 0 | ≤ 1. Hence again I(x) = I(y). Assume next that x, y ∈ O 1 \ D. There exists c ∈ C ⊕ {1} such that d(c, x) ≤ 2. If x = c, then |I(x) ∩ S 1 (c)| ≥ 3 and |I(y) ∩ I(x)| ≤ 2 by Lemma 1. If x = c + e 1 , then I(x) ∩ O 0 = ∅ and thus I(x) = I(y). Assume then that x ∈ S 2 (c) and that x covers two elements of I(c). In this case only y = c could cover both elements of I(x) ∩ S 1 (c), and this is impossible as we have seen. Suppose finally that x ∈ S 2 (c) and only covers one element of I(c): in other words, that c + e 1 / ∈ D, d(x, c + e 1 ) = 1. Then y should cover the unique element in I(x) ∩ S 1 (c) and consequently y ∈ S 2 (c), but then y would cover also another codeword of I(c), which gives I(x) = I(y).By[START_REF] Slater | Locating dominating sets and locating-dominating sets[END_REF] Theorem 10] we have the next theorem.

2. a codeword, say c 1 ,

 1 which forms a couple with another codeword c 2 such that I(c 1 ) = I(c 2 ) = {c 1 , c 2 }, 3. a word x which has E(x) ≥ 2, and 4. a word y which has E(y) = 1 and for which there exists a word x such that E(x) ≥ 2 and I(y) ⊂ I(x).

  that M ≤ 2)-identifying code of length 8 is of cardinality 96. Let C be the perfect binary Golay code of length 23, dimension 12 and minimum distance 7 (and covering radius 3). By Theorem 11 we can construct a (1, ≤ 2)-LDB of length 23 with cardinality 212 (1 + 232 ) = 1040384. It is known[START_REF] Ranto | Two families of optimal identifying codes in binary Hamming spaces[END_REF] that M

			(≤2) 1	(7) = 48, and the
	best known (1, (≤2) 1	(23) = 2 20 = 1048576.
	Theorem 12.
	LB 1 (≤2)	(6) ≤ 29.
	Proof. The code C = {000000, 110000, 101000, 100100, 010100, 010001, 001010, 001001, 000110, 000011, 110010, 100101, 100011, 011100, 011010, 001101, 111010, 111001, 110011, 101110, 101101,
	100111, 011110, 011101, 010111, 111101, 111011, 110111, 011111} is a (1, ≤ 2)-LDB of cardinality 29 and length 6.

† The research of this author was supported by the Academy of Finland under Grants #44002 and #200213. ‡ The research of this author was supported by the Academy of Finland under Grants #46186 and #207303. 1365-8050

This is decreasing function on i ≥ 4; and f (3) = f [START_REF] Cohen | New bounds for codes identifying vertices in graphs[END_REF]. Assume that n ≥ 6. Then f (i) ≥ f (n) for all 3 ≤ i ≤ n. Since C is an optimal code there is no codeword c ∈ C such that |I(c)| = n + 1.

The excess on F n is K(n + 1) -2 n . We now estimate it in a different way. There are at most 2K words outside the families. We can estimate

from which we get the claimed lower bound on K for n ≥ 6.

When n = 5 then the minimum of f (3), f (4) and f (5) is f (3). Now we can estimate 6K -2 5 ≥ (2 5 -2K)f [START_REF] Charon | Identifying and locating-dominating codes: NPcompleteness results for directed graphs[END_REF]. From this we get K ≥ 9. And thus the lower bound holds for n = 5. Similarly when n = 4 we notice that the lower bound holds. For 1 ≤ n ≤ 3 the lower bound is true by Theorem 14.

Theorem 16. If C is 1-locating-dominating with the property that d(c, C \ {c}) = 1 for all c ∈ C,

Proof. Assume that x, y ∈ F n , x = y. We show that I(x) = I(y).

We again denote

Assume first that x, y ∈ O 0 (the case x, y ∈ O 1 can be proved in the same way). If x, y / ∈ D, then they can be separated (their I-sets are different) by the locating-dominating property of C. (5) ≥ 15 from Theorem 9. (n) for short lengths and l = 1, 2, 3.

Optimal linear locating-dominating codes

A binary code C ⊆ F n is said to be linear if it is a k-dimensional subspace of F n . In this section we consider linear (1, ≤ l)-LDBs and (1, ≤ l)-LDAs. We denote by LB (≤l) 1

[n] (resp. LA (≤l) 1

[n]) the smallest cardinality of a linear (1, ≤ l)-LDB (resp. (1, ≤ l)-LDA) of length n.

A linear k-dimensional code C ⊆ F n can always be defined by choosing an (nk) × n matrix H -called its parity check matrix -such that x ∈ C if and only if Hx T = 0. Let x ∈ F n be arbitrary, and consider its syndrome Hx T . If Hx T appears in H as the i-th column, then clearly the word obtained by changing the i-th bit in x belongs to C. Consequently, if x is a codeword, the number of codewords within distance one from it equals one plus the number of zero columns in H; if x is a non-codeword, the number of codewords within distance one from it equals the number of times the syndrome of x appears as a column in H.

The next auxiliary lemma from [START_REF] Ranto | Optimal linear identifying codes[END_REF] will be used often.

Let us first consider the case l = 1 and denote

where r is the smallest integer such that the latter inequality holds.

Proof. Suppose C is a linear (1, ≤ 1)-LDB of length n and |C| = K. There can be K noncodewords which are covered by one codeword each. All the other non-codewords must be covered by at least three codewords. Namely, if I(x) = {c 1 , c 2 } for some x ∈ C, then for y = x + c 1 + c 2 , I(y) = I(x) by Lemma 3. Thus we have 2K + 3(2 n -2K) ≤ K(n + 1), from which the claim follows.

Proof. The lower bound follows from Theorem 17.

Because n ≥ 3 • 2 k -5, we can choose a k × n matrix H in which every nonzero column appears at least three times except for one nonzero column which appears exactly once. Let C be the code with parity check matrix H. We claim that C is a (1, ≤ 1)-LDB. Each non-codeword which is covered by at least three codewords is clearly identified since in the intersection of three Hamming balls of radius one there is at most one word. Each non-codeword of N 1 is also identified, because for each c ∈ C, there is exactly one word of N 1 at distance one from c.

Proof. See the proof of (4) for the first claim.

If

where r is the smallest integer such that the latter inequality holds.

Proof. Let C be a linear (1, ≤ 2)-LDB of cardinality K. [n] = 2 n-k .

Proof. The lower bound follows from Theorem 19. Let H be a k × n matrix where every nonzero k-tuple appears at least five times, and let C be the code which has parity check matrix H. Now every non-codeword is covered by five codewords of C, and this code is a (1, ≤ 2)-LDB. Namely, if X, Y ⊆ F n \ C have both size at most two and x ∈ X \ Y , then by Lemma 1, the at most two words in Y cannot cover all the at least five codewords in I(x).

Theorem 21. For l ≥ 3 and n ≥ 2l -1,

where r is the smallest integer such that the latter inequality holds.

Proof. Assume that C is a linear (1, ≤ l)-LDB of length n and cardinality K.

If there is a word x / ∈ C such that |I(x)| = 1, then the beginning of the previous proof (since C is trivially also a (1, ≤ 2)-LDB) shows that K ≥ 2 n-1 , and since we have assumed that n ≥ 2l -1, we are already done.

Assume now that |I(x)| ≥ 2 for all x / ∈ C. We shall show that each non-codeword must be covered by at least 2l -1 codewords. Assume to the contrary that x / ∈ C, |I(x)| = j for some 2 ≤ j ≤ 2l -2, and that I(x) = {c 1 , . . . , c j }. For all i, 1 ≤ i ≤ j/2, let x i = x + c 2i-1 + c 2i (which is the unique word other than x at distance one from both c 2i-1 and c 2i ). If j is odd, define

Thus we have K + (2l -1)(2 n -K) ≤ K(n + 1), and the claim follows.

Theorem 22. Let l ≥ 3 and n = (2l -1)(2 k -1) + s, for k ≥ 1 and 0 ≤ s < (2l -1)2 k . Then LB (≤l) 1

[n] = 2 n-k .

Proof. The lower bound follows from Theorem 21. Let H be a k × n matrix in which every nonzero k-tuple appears at least 2l -1 times. The code which has H as a parity check matrix is (1, ≤ l)-LDB by Theorem 1, and has the required dimension.

The previous proof in fact gives the following theorem as an immediate corollary.

Theorem 23. Let l ≥ 3. For all n ≥ 2l -1, the smallest dimension of a linear (1, ≤ l)-LDA of length n is the same as the smallest dimension of a linear (1, ≤ l)-LDB of length n.

Theorem 24. For all n ≥ 5, the smallest dimension of a linear (1, ≤ 2)-LDA of length n is the same as the smallest dimension of a linear (1, ≤ 2)-LDB of length n.

Proof. By Theorems 20, 22 and 23 we know that for all n ≥ 5, LB (≤2) 1

[n] = LB (≤3) 1

[n] = LA (≤3) 1

[n]. Trivially, LA (≤3) 1

[n] ≥ LA (≤2) 1

[n] ≥ LB (≤2) 1

[n], and the claim follows.


Rajendra M Pawale

A note on t-designs with t intersection numbers

Keywords:

We use the Ray-Chaudhuri and Wilson inequality for a 0-design with t intersection numbers to prove that 'For a fixed block size k, there exist finitely many parametrically feasible t-designs with t intersection numbers and λ > 1'.

Introduction

Let X be a finite set of v elements, called points, and let β be a finite family of distinct k-subsets of X, called blocks. Then the pair D = (X, β) is called a t-design with parameters (v, k, λ) if any t-subset of X is contained in exactly λ members of β. If λ i denotes the number of blocks containing i points, i = 0, 1, 2, . . . ,t -1, then λ i is independent of the choice of the i points and λ i k-i t-i = λ v-i t-i . In particular, b = λ 0 is the number of blocks, and λ 1 = r is the number of blocks through any point of D. A 0-design is a pair (X, β) where β is a collection of k-subsets of X. For 0 ≤ x < k, x is called intersection number of D if there exists B, B ′ ∈ β such that |B ∩ B ′ | = x. A 2-design with two intersection numbers is said to be a quasi-symmetric design.

For a 0-design with t intersection numbers, Ray-Chaudhuri and Wilson proved that b ≤ v t (see [START_REF] Beth | Design Theory[END_REF]). This result is used by Sane and Shrikhande [START_REF] Sane | Quasi-symmetric 2,3,4-designs[END_REF] to prove that, for a fixed value of the block size k, there exist finitely many quasi-symmetric designs with λ > 1.

In the literature many finiteness results for quasi-symmetric designs and quasi-symmetric 3-designs are proved by using this result by Sane and Shrikhande (see [START_REF] Pawale | Inequalities and Bounds for Quasi-symmetric 3-designs[END_REF], [START_REF] Pawale | Quasi-symmetric 3-designs with a fixed block intersection number[END_REF], [START_REF] Sane | Quasi-symmetric 2,3,4-designs[END_REF], [START_REF] Shrikhande | Quasi-symmetric designs[END_REF]).

Our main aim in this paper is to extend the result by Sane and Shrikhande to t-designs with t intersection numbers. More specifically, we obtain a relation between the parameters of a t-design with t intersection numbers, and we use it to show that, for a fixed value of the block size k, v takes finitely many values. Finally, we use the result by Ray-Chaudhuri and Wilson to complete the proof.

(0 < t ≤ k ≤ v -t) intersection numbers x 1 , x 2 , . . . , x t (0 ≤ x 1 < x 2 < . . . < x t < k). Then b ≤ v t . Lemma 2.2 Let D be a t-design with t intersection numbers x 1 , x 2 , . . . , x t (0 ≤ x 1 < x 2 < . . . < x t < k).
Then the following relation holds:

x 2 -x 1 • • • x t -x 1 x 1 (b -1) -(r -1) x 2 2 - x 1 2 • • • x t 2 - x 1 2 x 1 2 (b -1) - k 2 (λ 2 -1) . . . . . . . . . . . . x 2 t - x 1 t • • • x t t - x 1 t x 1 t (b -1) - k t (λ t -1) = 0. ( 1
)
Proof: Let a i , 2 ≤ i ≤ t, be the number of blocks intersecting B 0 in x i points. Fix a block B 0 and count in two ways the number of ( j + 1)-tuples ({p 1 , p 2 , . . . , p j }, B), where B is a block of D other that B 0 , and where p 1 , p 2 , . . . , p j are distinct points of D contained in B ∩ B 0 . For j = 1, 2, . . . ,t, we have

t ∑ i=2 x i j a i + x 1 j b -1 - t ∑ i=2 a i - k j (λ j -1) = 0.
We rewrite these equations as follows:

t ∑ i=2 x i j - x 1 j a i + x 1 j (b -1) - k j (λ j -1) = 0.
These are t equations in t -1 unknowns a 2 , a 3 , . . . , a t . Since a 2 , a 3 , . . . , a t , 1 cannot be simultaneously zero, the coefficient matrix is singular. Hence the determinant given in equation ( 1) must be zero. ✷

We would like to point out that equation ( 1) is an extension of equation ( 1) of [START_REF] Sane | Quasi-symmetric 2,3,4-designs[END_REF]. The latter is found to be useful in the study of quasi-symmetric designs. An immediate application of (1) is given in the following theorem. Theorem 2.3 For a fixed block size k, there exist finitely many parametrically feasible t-designs with t intersection numbers x 1 , x 2 , . . . , x t (0 ≤ x 1 < x 2 . . . < x t < k) and λ > 1.

Proof: By Theorem 2.1, the inequality b ≤ v t holds for any t-design with t intersection numbers. Hence it suffices to show that for a fixed k, v takes finitely many values.

We divide the proof in two parts, by considering the cases x 1 = 0 and x 1 = 0 separately. For x 1 = 0, we have the equality

t ∑ i=2 (x i -x 1 )a i = k(r -1) -x 1 (b -1). This implies k(r -1) -x 1 (b -1) > 0. Hence, x 1 < k(r-1) b-1 < kr b = k 2 v . Now it is easy to see that v < k 2 x 1 .
For x 1 = 0, by Lemma 2.2 we have

x 2 • • • x t k (r -1) x 2 2 • • • x t 2 k 2 (λ 2 -1)
. . . . . . . . . . . .

x 2 t -1 • • • x t t -1 k t -1 (λ t-1 -1)
x 2 t • • • x t t k t (λ t -1) = 0. Now we put λ j = v-j t-j λ k-j t-j , j = 1, 2, . . . ,t -1, to get A k k 2 . . . k t -1 k t = λ A k v -1 t -1 k -1 t -1 k 2 v -2 t -2 k t -1 . . . k t -1 v -t + 1 1 k -t + 1 1 k t , where A =              x 2 • • • x t x 2 2 • • • x t 2 . . . . . . . . . x 2 t -1 • • • x t t -1 x 2 t • • • x t t              .
We simplify the above equation as follows:

k k 2 A . . . k t -1 k t = λ k (v -1)(v -2) • • • (v -t + 2)(v -t + 1) (k -1)(k -2) • • • (k -t + 2)(k -t + 1) k 2 (v -2)(v -3) • • • (v -t + 2)(v -t + 1) (k -2)(k -3) • • • (k -t + 2)(k -t + 1) A . . . k t -1 v -t + 1 k -t + 1 k t . Now we multiply both sides by (k -1)(k -2) • • • (k -t + 2)(k -t + 1), to get k k 2 A . . . k t -1 k t (k -1)(k -2) • • • (k -t + 2)(k -t + 1) = λ k(v -1)(v -2) • • • (v -t + 2)(v -t + 1) k 2 (v -2)(v -3) • • • (v -t + 2)(v -t + 1)(k -1) A . . . k t -1 (v -t + 1)(k -1)(k -2) • • • (k -t + 2) k t (k -1)(k -2) • • • (k -t + 2)(k -t + 1)
.

Note that λ divides the left hand side. Hence λ takes finitely many values only. It is clear from the above equation, by expanding the right hand side determinant with respect to the last column of the matrix, that vt + 1 divides

(k -1)(k -2) • • • (k -t + 1)              k k 2 A . . . k t -1 k t -λ k t x 2 • • • x t x 2 2 • • • x t 2 . . . . . . . . . x 2 t -1 • • • x t t -1              .
For a fixed k, this is a finite number. If it is non-zero, then v takes only finitely many values, otherwise

v -t + 2 divides k t -1 (k -1)(k -2) • • • (k -t + 2) x 2 • • • x t x 2 2 • • • x t 2 . . . . . . . . . x 2 t -2 • • • x t t -2 x 2 t • • • x t t .
This can be simplified to

k t -1 (k -1)(k -2) • • • (k -t + 2) x 2 x 3 • • • x t 2! 3! • • • (t -2)!t! 1 • • • 1 x 2 • • • x t . . . . . . . . . x t-3 2 . . . x t-3 t x t-1 2 . . . x t-1 t .
It is easy to check that the above determinant is non-zero. This completes the proof. ✷

In [START_REF] Sane | Quasi-symmetric 2,3,4-designs[END_REF], Sane and Shrikhande proved analogues of Theorem 2.3 for quasi-symmetric designs. As in our paper, they also divide their proof in two parts, depending on whether or not the smaller intersection number, x, is non-zero or not. The case x 1 = 0 of Theorem 2.3 is similar to that of x = 0 of [START_REF] Sane | Quasi-symmetric 2,3,4-designs[END_REF]. But to prove their result for the case x = 0, they use a rather long argument, whereas our proof is elementary and short.

  1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France Theorem 2.1 (Ray-Chaudhuri and Wilson) Let D be a 0-design with t

Rajendra M. Pawale


Carsten Schneider
email: carsten.schneider@risc.uni-linz.ac.at

The Summation Package Sigma: Underlying Principles and a Rhombus Tiling Application

Keywords:

We give an overview of how a huge class of multisum identities can be proven and discovered with the summation package Sigma implemented in the computer algebra system Mathematica. General principles of symbolic summation are discussed. We illustrate the usage of Sigma by showing how one can find and prove a multisum identity that arose in the enumeration of rhombus tilings of a symmetric hexagon. Whereas this identity has been derived alternatively with the help of highly involved transformations of special functions, our tools enable to find and prove this identity completely automatically with the computer.

Introduction

The overall object of this article is to give an introductory overview of how a huge class of multisum identities can be proven and discovered with the summation package Sigma [START_REF] Schneider | Symbolic summation in difference fields[END_REF], which is based on the computer algebra system Mathematica. The algebraic platform of Sigma is built on the constructive difference field theory of ΠΣ-fields [Kar81, Kar85, Bro00, Sch00, Sch01, Sch04b] that not only allows to simplify indefinite and definite sums of (q-)hypergeometric terms, like [Gos78, Zei90, PS95a, PWZ96, PR97], but of ΠΣ-terms , i.e., rational terms of arbitrarily nested indefinite sums and products. Due to the generality of ΠΣ-terms, this opens up a new class of symbolic summation problems that cannot be treated by the algorithms and implementations [START_REF] Wegschaider | Computer generated proofs of binomial multi-sum identities[END_REF][START_REF] Riese | qMultisum -A package for proving q-hypergeometric multiple summation identities[END_REF] developed for (q-)hypergeometric multisums or by those [START_REF] Chyzak | Non-commutative elimination in ore algebras proves multivariate identities[END_REF][START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF] developed for holonomic and ∂-finite terms.

In the first part of this article we shall discuss relevant techniques of symbolic summation, and we shall explain how these ideas can be applied in the difference field setting of ΠΣ-fields and in difference ring extensions like (-1) n ; see [START_REF] Schneider | Symbolic summation in difference fields[END_REF][START_REF] Schneider | Product representations in ΠΣ-fields[END_REF]. More precisely, this means that sequences, that may consist of rational terms of arbitrarily nested indefinite sums and products, are translated in a natural way into the corresponding difference field/ring setting [START_REF] Karr | Theory of summation in finite terms[END_REF][START_REF] Schneider | Product representations in ΠΣ-fields[END_REF], and, by using a very general algebraic machinery [Kar81, AP94, Bro00, Sch02b, Sch04a, Sch02a, Sch04c], the corresponding summation principles (telescoping, creative telescoping, solving recurrences) are applied in this setting. This allows to carry over Zeilberger's paradigm from hypergeometric terms [PWZ96] to so-called ΠΣterms: given a definite nested multisum, find a recurrence and, if possible, solve the recurrence in terms of simpler expressions than the definite sum itself. Then the right combination of that solutions might give a closed form evaluation of the definite sum itself. The interplay of these summation techniques in the difference field setting can be summarized with the definite summation spiral that is graphically illustrated in Figure 1.

In the second part of this article we shall demonstrate how these summation techniques within Sigma enable the user to find an alternative, completely automatic proof of a non-trivial multisum identity that arises in [START_REF] Fulmek | The number of rhombus tilings of a symmetric hexagon which contains a fixed rhombus on the symmetric axis[END_REF]. In this article, M. Fulmek and C. Krattenthaler count the number of rhombus tilings of a symmetric hexagon with side lengths N, M, N, N, M, N, with N and M having the same parity, which contain a particular rhombus next to the center of the hexagon. Within this counting there arises the subproblem of finding a closed form evaluation S

(1)

n + n! (n+3)! S (2)
n for the two sums

S

(1)

n := n-1 ∑ k=0 (-1) n+k (n + k + 4)! ∑ k j=0 1 j+1 (k + 2)!(k + 3)!(n -k -1)! , S (2)
n := n-1 ∑ k=0 (-1) k (n + k + 4)!(1 -(-1) n (n + 2)) (k + 1)(k + 2)! 2 (n -k -1)! .
In order to achieve this, the authors in [START_REF] Fulmek | The number of rhombus tilings of a symmetric hexagon which contains a fixed rhombus on the symmetric axis[END_REF] derive closed form evaluations for these sums, namely,

S

(1)

n = - 1 + (-1) n (n 2 + 3n + 3) n + 2 -(1 -(-1) n (n + 2)) n ∑ k=0 2 k + 1 (1)
and

S (2) n = (1 -(-1) n (n + 2)) n ∑ k=0 2 k + 1 - (-1) n + 2n 3 + 11n 2 + 19n + 11 (n + 1)(n + 2)(n + 3) , (2)
which finally delivers the identity

S (1) n + n! (n + 3)! S (2) n = (-1) n (n + 2) -2 (3)
for all n ≥ 0. However, the proof of this identity, given in [FK00, Lemma 26], fills about four pages involving highly complicated transformations of special functions.

In [START_REF] Fulmek | The number of rhombus tilings of a symmetric hexagon which contains a fixed rhombus on the symmetric axis[END_REF], the authors were already aware that the sum identity (3) could be proven with a prototype version [START_REF] Schneider | An implementation of Karr's summation algorithm in Mathematica[END_REF] of our Sigma package [START_REF] Schneider | Symbolic summation in difference fields[END_REF]. At that time, we were able to derive recurrence relations for the two sums S

(1) n and S

(2) n . Afterwards, we combined those two recurrences using "gfun" (see [START_REF] Salvy | Gfun: A package for the manipulation of generating and holonomic functions in one variable[END_REF], or [START_REF] Mallinger | Algorithmic manipulations and transformations of univariate holonomic functions and sequences[END_REF] for a Mathematica implementation) to one recurrence of order 10 which contains

S (1) n + n! (n+3)! S (2)
n as a solution. It is then a simple task to check that the right hand side of identity (3) is also a solution of this combined recurrence. The fact that both sides of the equation (3) agree with the first 10 initial values finally shows the correctness of (3). However, at that time we were not able to find the explicit evaluations (1) and (2). This has been changed partially in [START_REF] Schneider | An implementation of Karr's summation algorithm in Mathematica[END_REF], where we could find those evaluations by assuming that the right hand sides of (1) and (2) depend on the harmonic numbers

H n = ∑ n i=1 1 i .
In this article we shall show that meanwhile also the task of finding the evaluations (1) and (2) can be carried out with the summation package Sigma, without any guessing part, but only with computer algebra methods. In other words, we present an alternative proof of [FK00, Lemma 26] that not only shows the correctness of identity (3), but also delivers the explicit evaluations of the sums in (1) and (2). Moreover we shall illustrate that the proof of [FK00, Lemma 26] becomes completely automatic, if one uses Sigma, and hence feasible without advanced knowledge of hypergeometric functions and their transformations.

In principle, a reader may jump directly to the rhombus tiling application in Section 3. At every algorithmic step there, a pointer to the appropriate subsection of Section 2 is given where the ideas behind are outlined.

Symbolic Summation in Difference Fields

Symbolic summation usually is divided into two different subbranches, namely indefinite and definite summation. In contrast to indefinite summation, definite summation problems have closed form evaluations only for specifically chosen summation ranges. For instance, the sum ∑ b k=a n k in general cannot be simplified further, whereas for the specific bounds a = 0 and b = n that sum evaluates to 2 n .

In the following two subsections we will explain in more details, how indefinite and definite summation can be treated with the summation package Sigma [START_REF] Schneider | Symbolic summation in difference fields[END_REF]. Moreover, additional information is given in "ΠΣ-Remarks" how the summation problems are rephrased internally in the difference field setting of ΠΣ-fields. Finally, we will summarize all these underlying difference field aspects in Subsection 2.3.

Indefinite summation

Indefinite summation deals with the problem of eliminating summation quantifiers without using any knowledge about the summation range. More precisely, following [START_REF] Paule | Symbolic summation -some recent developments[END_REF], we are interested in the following problem. Given an indefinite sum ∑ n k=0 f (k) where f belongs to some "nice" domain of sequences and f (k) is independent of n. Find g(k) in the same class or some suitable extension of it such that

n ∑ k=0 f (k) = g(n).
Alternatively, indefinite summation asks for solving Problem T: Telescoping.

Given f (k); find g(k) such that g(k + 1) -g(k) = f (k) (4)
holds within a certain range of k.

Then, given such a telescoper g(k) of f (k), one derives by telescoping

b ∑ k=a f (k) = g(b + 1) -g(a) (5) if b -a ∈ N 0 .
There are various algorithms that solve Problem T for "nice" domains of sequences f (k), like [START_REF] Gosper | Decision procedures for indefinite hypergeometric summation[END_REF][START_REF] Paule | A Mathematica version of Zeilberger's algorithm for proving binomial coefficient identities[END_REF] for hypergeometric terms, [START_REF] Paule | A Mathematica q-analogue of Zeilberger's algorithm based on an algebraically motivated aproach to q-hypergeometric telescoping[END_REF] for q-hypergeometric terms, or [START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF] for holonomic and ∂-finite terms.

In the summation package Sigma the sequences f (k) and its telescoper g(k) are described in the algebraic setting of difference fields, more precisely of ΠΣ-fields [START_REF] Karr | Summation in finite terms[END_REF][START_REF] Karr | Theory of summation in finite terms[END_REF], and certain difference rings; for more details see ΠΣ-Remark 1. This domain of sequences essentially covers (q-)hypergeometric terms, see [START_REF] Schneider | Product representations in ΠΣ-fields[END_REF], and an important subclass of holonomic and ∂-finite terms that occurs frequently in symbolic summation. More generally, our approach allows to formulate sequences in terms of rational expressions consisting of arbitrarily nested indefinite sums and products that are out of scope of [START_REF] Gosper | Decision procedures for indefinite hypergeometric summation[END_REF][START_REF] Paule | A Mathematica q-analogue of Zeilberger's algorithm based on an algebraically motivated aproach to q-hypergeometric telescoping[END_REF][START_REF] Chyzak | Non-commutative elimination in ore algebras proves multivariate identities[END_REF][START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF].

Without going into more details, we call all those sequences f (k) ΠΣ-terms (in k) that can be described in terms of ΠΣ-fields. Typical examples for ΠΣ-terms are for instance

H k = k ∑ i=1 1 i , H (2) k = k ∑ i=1 1 i 2 , k! = k ∏ i=1 i, n k = k ∏ i=1 n -i + 1 i , 1 + H k (n -2k) n k , H 2 k H (2) k , H k k ∑ i=1 ∏ i j=1 (H 2 j + j!) H 3 j + j! . (6)
One of the crucial properties of a ΠΣ-term f (k) is that the sums and products in the shifted version f (k +1) can be expressed by the sums and products given in f (k), like H k+1 = H k + 1 k+1 or (k + 1)! = (k + 1) k!. On the contrary, sums like ∑ k i=1 H i (i+k) 4 are not in the scope of ΠΣ-terms. ΠΣ-Remark 1. In the sequel a brief introduction of ΠΣ-fields is given; further information can be found in [START_REF] Karr | Summation in finite terms[END_REF][START_REF] Karr | Theory of summation in finite terms[END_REF][START_REF] Bronstein | On solutions of linear ordinary difference equations in their coefficient field[END_REF][START_REF] Schneider | Symbolic summation in difference fields[END_REF][START_REF] Schneider | Solving parameterized linear difference equations in ΠΣ-fields[END_REF][START_REF] Schneider | Product representations in ΠΣ-fields[END_REF]. A difference field [START_REF] Cohn | Difference Algebra[END_REF], usually denoted by (F, σ), is nothing else than a field ‡ F together with a field automorphism σ : F → F. Karr built up a difference field theory in a completely constructive manner that enables one to describe a huge class of nested multisums. In short, the class of ΠΣ-fields contains difference fields (F, σ) that can be defined as follows. Basically F is constructed by a tower of finite field extensions

K = E 0 < E 1 < • • • < E n = F with constant field K, i.e., K = {σ(g) = g | g ∈ F i } for all 0 ≤ i ≤ n. Moreover the following conditions for 1 ≤ i ≤ n hold: E i := E i-1 (t i )
is a transcendental extension of E i-1 and we either have σ(t i ) = a i t i (a product/Π-extension) or σ(t i ) = t i + a i (a sum extension) for some a i ∈ E i-1 \ {0}. In other words the class of ΠΣ-fields contains difference fields such as F := K(t 1 )(t 2 ) . . . (t n ) where F is a field of rational functions over K. Moreover these transcendental extensions allow to describe recursively defined nested sums and products in rational terms. Besides such product and sum extensions, a ΠΣ-field can contain more general extensions of the type σ(t i ) = α i t i + β i with α i , β i ∈ E \ {0} together with some technical side conditions that are described further, for instance, in [Kar81, Kar85, Bro00, Sch01, Sch02b, Sch04b]. ‡ Throughout this article all fields will have characteristic 0.

Clearly, rational functions as f (k) ∈ K(k) with the shift operator σ(k) = k + 1 are contained in the class of ΠΣ-fields; also, most of the (q-)hypergeometric terms like f (k) = 2 k or f (k) = k! can be rephrased in a ΠΣ-field (K(k)(h), σ) with σ(h) = 2 h or σ(h) = (k + 1) h; for more details see [START_REF] Schneider | Product representations in ΠΣ-fields[END_REF]. In particular, all the terms given in (6) can be formulated in ΠΣ-fields.

On the other hand, frequently used objects like (-1) k cannot be formalized in ΠΣ-fields, since we have the algebraic relation ((-1) k ) 2 = 1. To overcome this problem, Sigma allows to handle objects like α k , 1 = α an nth root of unity, in ring extensions of the type F[x] where (F, σ) is a ΠΣ-field with constant field K, α ∈ K, σ(x) = α x, and x n = 1. In particular, this means that σ : F[x] → F[x] is a ring automorphism, i.e., (F[x], σ) forms a difference ring, or a difference ring extension of (F, σ). For more details see [START_REF] Schneider | Symbolic summation in difference fields[END_REF][START_REF] Schneider | Product representations in ΠΣ-fields[END_REF].

For instance, with Sigma one can produce the right hand sides of the identities

a ∑ k=0 1 + (n -2k)H k n k = (n -a)H a n a + 1, a ≥ 0, ( 7
) a ∑ k=0 1 + 2(n -2k)H k n k 2 = (n -a) 2 n 2 (1 + 2nH a ) n a 2 , a ≥ 0; (8)
note that the special case a = n of theses identities is treated in [START_REF] Paule | Computer proofs of a new family of harmonic number identities[END_REF]; see also [START_REF] Driver | Padé approximations to the logarithm II: Identities, recurrences, and symbolic computation[END_REF][START_REF] Chu | Hypergeometric series and harmonic number identities[END_REF][START_REF] Krattenthaler | Hypergéométrie et fonction zêta de Riemann[END_REF].

We illustrate the usage of our package Sigma by discovering and proving identity (7). First we start a Mathematica session by loading the package

In[1]:= << Sigma'
Sigma -A summation package by Carsten Schneider c RISC-Linz and defining the sum S(a) = mySum on the left hand side of (7) as follows:

In[2]:= mySum = SigmaSum[(1 + (n -2k)SigmaHNumber[k])SigmaBinomial[n, k], {k, 0, a}] Out[2]= a ∑ k=0 (1 + (-2 k + n) H j ) n k .
Generally, the functions SigmaSum and SigmaProduct are used to define ΠΣ-terms (in addition we allow summation objects like (-1) n that can be only formulated in difference ring extensions). For this purpose there are also several other functions available, like SigmaHNumber, SigmaBinomial or SigmaPower to define harmonic numbers, binomials or powers in terms of sums and products which itself can be converted into ΠΣ-fields or certain difference ring extensions. For instance, SigmaHNumber[k] produces the kth harmonic number H k which alternatively could be described by SigmaSum[1/i,{i,1,k}].

Then, by applying the Sigma-function SigmaReduce to mySum = S(a), we obtain the closed form evaluation:

In[3]:= SigmaReduce[mySum] Out[3]= 1 + (-a + n) H a n a .
ΠΣ-Remark 2. Internally, the Sigma-package proceeds as follows. 1. Construction of the ΠΣ-field (F, σ): Take the rational function field

F := Q(n)(k)(b)(h) and define the field automorphism σ : F → F by σ(c) = c for c ∈ Q(n), σ(k) = k + 1, σ(b) = n-k k+1 b and σ(h) = h + 1 k+1 . Note that the k-shifts S k n k = n k+1 = n-k k+1 n k and S k H k = H k+1 = H k + 1
k+1 are reflected by the action of σ on b and h. 2. Solving the telescoping problem in (F, σ):

Sigma [Sch02b] finds the solution g ′ = b(h k -1) for the telescoping equation σ(g ′ ) -g ′ = f ′ with f ′ = b(1 + (n -2k)h). This means that g(k) = (kH k -1) n k is a telescoper for f (k) = (1 + (n - 2k)H k ) n k . Hence Sigma finds the telescoper g(k) = (kH k -1) n k and the shifted version g(k + 1) = (n -k)H k n k .
The correctness of (4) for 0 ≤ k ≤ a is immediate and therefore the closed form is verified.

Similarly, one obtains a closed form of the sum

In[4]:= mySum = n ∑ k=0 (3 + 2 k) (-1) k . k ∑ j=1 1 + j j (2 + j) ;
by applying it to the function call SigmaReduce:

In[5]:= SigmaReduce[mySum] Out[5]= -3 (1 + n) (2 + n) + 2 3 + 3 n + n 2 (-1) n . + 4 (1 + n) (2 + n) 2 (-1) n . ∑ n ι 1 =1 1+ι 1 ι 1 (2+ι 1 ) 4 (1 + n) (2 + n) If one takes the shifted telescoper g(k + 1) of f (k) = (3 + 2k)(-1) k ∑ k j=1 1+ j j(2+ j) to be the expression in Out[5] with n replaced by k, the proof of identity § n ∑ k=0 (3 + 2k)(-1) k k ∑ j=1 1 + j j(2 + j) = - 3 4 + (n 2 + 3n + 3)(-1) n 2(n + 1)(n + 2) + (n + 2)(-1) n n ∑ i=1 i + 1 i(i + 2) (9)
for n ≥ 0 can be carried out similarly to the proof of identity (7) from above.

In general, suppose that we are given a sum S(a, b)

= ∑ b k=a f (k) with a ΠΣ-term f (k). If mySum = S(a, b) is defined with Sigma-functions as carried out in In[2], by typing in SigmaReduce[mySum]
one looks for a telescoper g(k) in terms of sums and products that are given by the ΠΣ-term f (k). More precisely, first a ΠΣ-field is constructed in which the sums and products occurring in f (k) can be expressed formally. Afterwards one tries to solve the telescoping equation in this ΠΣ-field. If such a g(k) can be computed, by telescoping, see (5), the outermost summation quantifier in the sum S(a, b) can be eliminated. ΠΣ-Remark 3. More precisely, the following difference field machinery is activated in Sigma; see also ΠΣ-Remark 2. First a concrete ΠΣ-field (F, σ) is constructed for the ΠΣ-term f (k) in (4). In particular, this means, one has to define a map which links the given summation objects, i.e., sequences f (k), with elements f ′ , say, in the constructed ΠΣ-field; in other words, f ′ ∈ F represents f (k); for more details § Note that this sum simplification will play an important role in Section 3. see [Sch01, Chapter 2.5]. Given this translation machinery, it is decided constructively, if there exists a solution g ′ ∈ F for the telescoping problem

σ(g ′ ) -g ′ = f ′ . ( 10
)
If one finds such a g ′ , one constructs a sequence g(k) in terms of sums and products for which (4) holds. This finally gives the evaluation in (5).

Based on Karr's difference field theory [START_REF] Karr | Summation in finite terms[END_REF], the translation between ΠΣ-terms and corresponding ΠΣfields can be carried out completely automatically for most instances. Problematic cases can be treated by building up the underlying ΠΣ-field manually; for more details see [START_REF] Schneider | Product representations in ΠΣ-fields[END_REF]. This user controlled construction can be achieved by calling ¶ SigmaReduce with the option Tower → {s 1 (k), . . . , s k (k)}, where s i (k) are ΠΣ-terms in k. This means that Sigma first tries to construct the ΠΣ-field for the term s 1 (k) and then extends the field in order to represent the remaining s i (k) following the input order; finally, the ΠΣ-field is enlarged with necessary extensions in order to represent also f (k).

Note that Sigma can also treat indefinite summation problems in terms of (-1) k that can be only treated in difference rings. For more details we refer to Subsection 2.3.

We want to point out that so far we only dealt with indefinite summation problems where the telescoper g(k) is searched in the domain given by the input sequence f (k). But already for the slightly more general sum expression

In[6]:= mySum = n ∑ k=0 (3 + 2 k) (x) k . k ∑ j=1 1 + j j (2 + j) ;
we would fail to find such a telescoper in the ground field. Such kind of problems motivated us to generalize the indefinite summation approach to the following refined version [START_REF] Schneider | Symbolic summation with single-nested sum extensions[END_REF]: with the Sigmapackage one is able to decide constructively if certain classes of sum extensions provide simpler solutions. More precisely, given a ΠΣ-term f (k), Sigma can search for a telescoper g(k) of f (k) that not only consists of sums and products given by f (k) but that can contain sum extensions with the following property: they are not more nested than the given ΠΣ-term f (k) and their summands are composed by ΠΣ-terms that occur in f (k).

By setting the additional option SimplifyByExt → Depth in the function call SigmaReduce this refined algorithm can be activated.

In[7]:= res = SigmaReduce[mySum, SimplifyByExt → Depth] Out[7]= x (-5 -2 n + 3 x + 2 n x) x n . ∑ n ι 1 =1 1+ι 1 ι 1 (2+ι 1 ) -∑ n ι 1 =1 (1+ι 1 ) (-3+x-2 ι 1 +2 x ι 1 ) x ι 1 . ι 1 (2+ι 1 ) (-1 + x) 2
In this example Sigma finds the additional sum extension

E x (n) := ∑ n k=1 (1+k)(-3+x-2k+2xk)x k k(2+k)
that allows to find the closed form evaluation given in Out[7] with the same nested depth than the summand itself. (If one considers the special case x = -1, the sum E -1 (x) can be simplified further to 3 -2(3+3n+n 2 )(-1) n (n+1)(n+2) which finally gives (9).) ¶ Analogously, this translation process can be controlled in the Sigma-functions CreativeTelescoping, GenerateRecurrence and SolveRecurrence that are explained later.

ΠΣ-Remark 4. In the difference field setting the following problem is solved in Sigma. First a ΠΣfield (F, σ) is constructed in which the ΠΣ-term f (k) can be represented with f ′ ∈ F. Then it is decided constructively, if there exists a bigger ΠΣ-field (F(x 1 , . . . , x e ), σ) with σ(x i )-x i ∈ F and a g ′ ∈ F(x 1 , . . . , x e ) with σ(g ′ )g ′ = f ′ where g ′ is not more nested than f ′ itself. If Sigma finds such a g ′ , it constructs a telescoper g(k) of f (k) in terms of additional sums whose depth is not larger than the ΠΣ-term f (k) itself.

For algorithmic details we refer to [START_REF] Schneider | Symbolic summation in difference fields[END_REF][START_REF] Schneider | Symbolic summation with single-nested sum extensions[END_REF].

Further examples, like

In[8]:= mySum = n ∑ k=0 H 2 k H (2) k In[9]:= SigmaReduce[mySum, SimplifyByExt → Depth] Out[9]= 1 3 -6 H n + 3 H 2 n -H 3 n + 3 (1 + 2 n) -3 (1 + 2 n) H n + 3 (1 + n) H 2 n H (2) n + n ∑ ι 1 =1 1 ι 3 1 and In[10]:= mySum = m ∑ k=1 H k k ∑ j=1 ∏ j i=1 (H 2 i + i! . ) H 3 j + (j! . ) 2 ; In[11]:= SigmaReduce[mySum, SimplifyByExt → Depth] Out[11]= (-m + (1 + m) H m ) m ∑ ι 1 =1 ∏ ι 1 j=1 (H 2 j + j! . ) H 3 ι 1 + ι 1 ! . 2 - m ∑ ι 1 =1 (-ι 1 + H ι 1 ι 1 ) ∏ ι 1 j=1 (H 2 j + j! . ) H 3 ι 1 + ι 1 ! . 2
show that these new ideas significantly enhance the algorithmic tool box.

Definite summation and the definite summation spiral

In general, the problem of definite summation is harder than indefinite summation, since in addition one also has to take into account the summation range. Up to now, all definite summation algorithms deal with such kind of problems by following Zeilberger's paradigm [PWZ96]: given a definite sum, find a recurrence (with polynomial coefficients) that contains the definite sum as a solution. If one can guess a closed form evaluation for a given definite sum, one may prove this identity by showing that the conjectured right hand side is also a solution of the computed recurrence and checking that the first initial values are the same. More generally, one also tries to find solutions of a derived recurrence. Here the crucial point is that the computed solutions should be of a "simpler type" than the given definite sum expression. If one succeeds in this, one cannot only prove identities but even derive "closed form" evaluations.

Subsequently we will work out the interplay between those subproblems and methods that can be summarized with our definite summation spiral in Figure 1. Finally, a concrete example will illustrate these aspects in Section 3.

Creative telescoping

The first step in our definite summation spiral consists of solving the following problem. Given a definite sum

S(n) := b ∑ k=a f (n, k) (11)
c 0 (n) S(n) + • • • + c d (n) S(n + d) = h(n). ( 12
)
Most relevant summation algorithms accomplish this task by solving Problem CT or variations of it.

Problem CT: Creative Telescoping.

Given f (n, k) and d ∈ N; find c 0 (n), . . . , c d (n), free of k and not all zero, and g(n, k) such that

g(n, k + 1) -g(n, k) = c 0 (n) f (n, k) + • • • + c d (n) f (n + d, k) (13)
holds within a certain range of n and k.

The basic idea behind this is as follows. Suppose one succeeds in computing such c i (n) and g(n, k) for given f (n, k) and d. Then summing equation ( 13) over k from a to b gives

g(n, b + 1) -g(n, a) = c 0 (n) b ∑ k=a f (n, k) + • • • + c d (n) b ∑ k=a f (n + d, k). ( 14
)
Then with some mild extra conditions, one can express the sums ∑ b k=a f (n + i, k) in (13) in terms of S(n+i). This implies a not necessarily homogeneous recurrence (12) for the definite sum S(n). A concrete example in Remark 2 illustrates in details how this transformation from (13) to (12) can be carried out.

Summarizing, solving Problem CT for a sequence f (n, k) with a fixed d ∈ N enables one to construct a recurrence of order d that contains the above defined sum S(n) as solution. Note that d must be specifically chosen for each attempt to solve Problem CT. Usually, one first tries to solve Problem CT for d = 1, and increments d until one finds a solution.

Originally, creative telescoping has been introduced in [START_REF] Zeilberger | A fast algorithm for proving terminating hypergeometric identities[END_REF] for hypergeometric terms f (n, k) and g(n, k); for a Mathematica implementation see for instance [START_REF] Paule | A Mathematica version of Zeilberger's algorithm for proving binomial coefficient identities[END_REF]. Various other approaches in more general settings, like [START_REF] Paule | A Mathematica q-analogue of Zeilberger's algorithm based on an algebraically motivated aproach to q-hypergeometric telescoping[END_REF] for q-hypergeometric terms, [START_REF] Chyzak | Non-commutative elimination in ore algebras proves multivariate identities[END_REF][START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF] for holonomic and ∂-finite terms, or [START_REF] Wegschaider | Computer generated proofs of binomial multi-sum identities[END_REF][START_REF] Riese | qMultisum -A package for proving q-hypergeometric multiple summation identities[END_REF] for (q-)hypergeometric multisum terms follow this idea of creative telescoping or related paradigms.

With the summation package Sigma one can try to solve Problem CT for a given d ∈ N and a ΠΣterm f (n, k) in k, which also depends on an extra parameter n, if the following property holds : also the shifted versions f (n + i, k) for 1 ≤ i ≤ d are ΠΣ-terms in k and all those ΠΣ-terms can be represented in a common ΠΣ-field. Then, given such a d and f (n, k), one can search for a solution of Problem CT, where g(n, k) consists of sums and products that occur in f (n, k). Due to the generality of the input class of ΠΣ-terms, this approach opens up the possibility to tackle various definite summation problems that cannot be treated by the earlier approaches [PR97, CS98, Chy00, Weg97, Rie03].

ΠΣ-Remark 5. Given a ΠΣ-term f (n, k) and d ∈ N, creative telescoping is handled in Sigma as follows.

First a ΠΣ-field (F, σ) is constructed with constant field K(n), n transcendental over K, in which the ΠΣ-

terms f (n + i, k) in k can be expressed by f ′ i ∈ F for 0 ≤ i ≤ d.
Then one decides constructively, if there exist c i (n) ∈ K(n), not all zero, and a g ′ ∈ F with

σ(g ′ ) -g ′ = c 0 (n) f ′ 0 + • • • + c d (n) f ′ d . (15)
If one succeeds in finding such solutions c i (n) and g ′ , a ΠΣ-term g(n, k) is constructed that gives a solution for Problem CT. We want to remark that with Sigma one can search for creative telescoping solutions also in algebraic difference ring extensions like (-1) n .

Suppose that we are given d ∈ N and a definite sum one obtains the resulting recurrences of the form (12) for the sum S(n) that one can compute from the creative telescoping solutions. All these steps can be carried out in one stroke by using the Sigma-

S(n) = ∑ b k=a f (n, k) as in (11) f (n + i, k) is a ΠΣ-term in k for 0 ≤ i ≤ d. Then, if mySum = S(n) is
function call † † GenerateRecurrence[mySum, n, RecOrder → d].
As example we refer to the computation steps In[13], In[14] and In [22] in the Mathematica session that will be carried out in Section 3. Further examples can be found in [START_REF] Schneider | Symbolic summation in difference fields[END_REF][START_REF] Paule | Computer proofs of a new family of harmonic number identities[END_REF][START_REF] Driver | Padé approximations to the logarithm II: Identities, recurrences, and symbolic computation[END_REF][START_REF] Driver | Padé approximations to the logarithm III: Alternative methods and additional results[END_REF]. We want to emphasize that for our input class of ΠΣ-terms, i.e., indefinite nested sums and products, we can verify the correctness of the obtained recurrence by the following recipe: check that the computed telescoping equation of Problem CT is correct for all k with a ≤ k ≤ b. Then it suffices to verify that the inhomogeneous part h(n) in ( 12) is correctly determined. In Remark 2 we will illustrate with a concrete example how these verification steps can be carried out with the computer.

Solving recurrences

Suppose that we have derived a recurrence for a definite sum, say S(k), of the type

a m (k) S(k + m) + • • • + a 0 (k) S(k) = b(k) ( 16
)
where the coefficients a i (k) and the inhomogeneous part b(k) are ΠΣ-terms; note that exactly this type of recurrences can be computed with the Sigma-function call GenerateRecurrence. The next step in Figure 1 asks for solving the recurrence in terms of simpler expressions than the definite sum itself. Then the right linear combination of those solutions might give the closed form evaluation of the definite sum itself.

With the package Sigma there are various possibilities to achieve this task. The simplest strategy is to search for the solutions in the ground field given by the coefficients and the inhomogeneous part in (16). Namely, if a recurrence of the form ( 16) is inserted properly in the computer algebra system Mathematica, say in the variable rec like in In[15], using the function call

SolveRecurrence[rec, S[k]]

the user can look for all solutions in terms of sums and products given by the a i (k) and b(k). The result of this function call is of the form

{{0, h 1 (k)}, . . . , {0, h r (k)}} or {{0, h 1 (k)}, . . . , {0, h r (k)}, {1, g(k)}} (17)
where {h 1 (k), . . . , h r (k)} gives a solution set of the homogeneous version of the recurrence and g(k) gives a particular solution of the recurrence itself. Concrete applications can be found in the computation steps In[16] and In [24]. ΠΣ-Remark 6. Internally, a ΠΣ-field (F, σ) is constructed in which the coefficients a i (k) and the inho-

mogeneous part b(k) can be expressed by a ′ i ∈ F and b ′ ∈ F. Then in Sigma all solutions g ′ ∈ F with a ′ m σ m (g ′ ) + • • • + a ′ 0 g ′ = b ′ (18)
are searched. More precisely, a solution set {h ′ 1 , . . . , h ′ r } ⊆ F, linearly independent over the constant field {c ∈ F | σ(c) = c}, is computed for the homogeneous version of (18). Moreover, a particular solution g ′ ∈ F for (18) is searched. The found solutions are then reinterpreted in form of ΠΣ-terms h i (k), g(k) that give the solutions (17) for the original recurrence. Note that the search of the solutions for (18) can be also carried out in algebraic extensions like (-1) k , i.e., the a i (k) and b(k) may depend on (-1) k .

In many instances the underlying difference field is too small in which the solutions S(k) are searched. However, the guessing of additional ΠΣ-terms is a highly non-trivial task. In order to dispense the user from extending the underlying difference field manually, the following two possibilities should be applied.

• Finding (q-)hypergeometric solutions. Due to the pioneering work [START_REF] Petkovšek | Hypergeometric solutions of linear recurrences with polynomial coefficients[END_REF][START_REF] Van Hoeij | Rational solutions of linear difference equations[END_REF][START_REF] Abramov | q-Hypergeometric solutions of q-difference equations[END_REF], one has powerful solvers in hand that allow to find all solutions S(k) in (q-)hypergeometric terms of a homogeneous recurrence with polynomial coefficients in k or q k . These solvers perfectly complement the summation package Sigma.

• Finding nested sum solutions and d'Alembertian solutions. With the function call

SolveRecurrence[rec, S[k], Tower → {s 1 , . . . , s e }, NestedSumExt → ∞]
the user can compute all nested sum solutions of a given recurrence rec of the form

n ∑ k 1 =0 b 1 (k 1 ) k 2 ∑ k 2 =0 b 2 (k 2 ) • • • k r-1 ∑ k r =0 b r (k r ) (19)
where the b i (k i ) are ΠΣ-terms in terms of sums and products given by the s i and by the a i (k) and b(k) in the recurrence (16). Typical sum solutions can be found in Out[17] and Out[26].

Remark 1. Internally, those solutions can be obtained by factorizing its linear difference equation as much as possible into linear right factors over the given difference field or ring; then each factor corresponds basically to one indefinite summation quantifier; see [START_REF] Abramov | D'Alembertian solutions of linear differential and difference equations[END_REF][START_REF] Schneider | Symbolic summation in difference fields[END_REF]. An important result is that the class of "linearly" nested sum solutions (19) over the given ΠΣ-terms contains also all solutions that consist of rational terms of arbitrarily nested sums over the given ΠΣ-terms; for the rational case see [START_REF] Hendriks | Solving difference equations in finite terms[END_REF] and for the general ΠΣ-field case see [START_REF] Schneider | Symbolic summation in difference fields[END_REF]. Note that the class of sum solutions is contained in the class of d'Alembertian solution [START_REF] Abramov | D'Alembertian solutions of linear differential and difference equations[END_REF] which again is included in the class of Liouvillian solutions [START_REF] Hendriks | Solving difference equations in finite terms[END_REF]. An important special case is the "rational case", i.e., the coefficients of the recurrence are in the field K(k) with the shift operator S(k) = k + 1. Then the d'Alembertian solutions are of the type (19) where b i (k i ) are hypergeometric terms over K(k i ). Here the crucial observation is that a hypergeometric term solution of a recurrence gives also a linear right factor of a recurrence. Therefore, the application of algorithms like [START_REF] Petkovšek | Hypergeometric solutions of linear recurrences with polynomial coefficients[END_REF][START_REF] Van Hoeij | Rational solutions of linear difference equations[END_REF] might contribute to a refined factorization of a given recurrence into linear right factors, and thus to further solutions of the recurrence; see [START_REF] Abramov | D'Alembertian solutions of linear differential and difference equations[END_REF][START_REF] Schneider | Symbolic summation in difference fields[END_REF]. In combination with [START_REF] Abramov | D'Alembertian solutions of linear differential and difference equations[END_REF][START_REF] Schneider | Symbolic summation in difference fields[END_REF] and manual extensions of the solution domain (with the option Tower), the user can compute all those d'Alembertian solutions with the summation package Sigma; for further details and illustrative examples we refer to [START_REF] Paule | Computer proofs of a new family of harmonic number identities[END_REF][START_REF] Driver | Padé approximations to the logarithm III: Alternative methods and additional results[END_REF].

Indefinite summation

Nested sum solutions and d'Alembertian solutions consist of non-trivial and highly nested indefinite sums of the form (19). If such solutions contribute to the closed form evaluation of the original definite sum expression, in most instances the found evaluation is not simpler, but even more complex, namely more nested. In order to overcome this problem, one has to reduce those nested sums to expressions which are less nested than the originally given definite multisum. It turns out that all nested sum solutions and many d'Alembertian solutions can be expressed in ΠΣ-fields or difference ring extensions like (-1) k ; see [START_REF] Schneider | Product representations in ΠΣ-fields[END_REF]. In this case one can apply our indefinite summation algorithms described in Section 2.1 in order to simplify those sum solutions and d'Alembertian solutions further. This simplification step is carried out, for instance, in In[18] and In[27].

Combination of solutions.

Now assume that we managed to compute a recurrence of order d for a definite sum S(n) that holds for all n ≥ n 0 , n 0 an integer, and we found a set of solutions of that recurrence that holds for all n ≥ n 0 . More precisely, suppose that in a Mathematica session mySum stands for our definite sum S(n) and recSol for our set of solutions of the recurrence that is given in the form (17) with replaced by n. Then with

FindLinearCombination[recSol, mySum, d, MinInitialValue → n 0 ]
the user can try to find a linear combination of the solutions of the homogeneous version of the recurrence plus one particular solution of the inhomogeneous recurrence that evaluates to the same initial values for n ∈ {n 0 , n 0 + 1, . . . , n 0 + d -1} as the given definite sum. If Sigma succeeds in finding such a linear combination, this expression equals S(n) for all n ≥ n 0 . Note that Sigma might fail to find this linear combination if a particular solution or some solutions of the homogeneous version of the recurrence are missing in recSol.

The "Master Problem" for symbolic summation in difference fields

The summation problems sketched in the previous ΠΣ-Remarks can be summarized by Problem PLDE: Solving Parameterized Linear Difference Equations.

Given a ΠΣ-field (F, σ) with constant field K, a 0 , . . . , a m ∈ F, and f 0 , . . . , f d ∈ F; find all g ∈ F and all c 0 , . . . ,

c d ∈ K with a m σ m (g) + • • • + a 0 g = c 0 f 0 + • • • + c d f d .
Namely, specializing to d = 0 and m = 1 with a 1 = 1 and a 2 = -1, one considers the telescoping problem (10) for indefinite summation. Moreover, specializing to m = 1 with a 1 = 1 and a 2 = -1, one can formulate the creative telescoping problem (15) if K = K ′ (n) and f i ∈ F stands for the ΠΣ-term f (n + i, k) ∈ F in k for 0 ≤ i ≤ d. Furthermore, if one sets d = 0, one considers the problem to solve linear difference equations (18) of order m.

In [START_REF] Karr | Summation in finite terms[END_REF][START_REF] Karr | Theory of summation in finite terms[END_REF], M. Karr developed a complete algorithm that solves Problem T in the general ΠΣ-field setting; only some additional properties are required for the constant field, that are worked out in [START_REF] Schneider | Product representations in ΠΣ-fields[END_REF]. In some sense, Karr's algorithm [START_REF] Karr | Summation in finite terms[END_REF] is the summation counterpart to Risch's algorithm [START_REF] Risch | The problem of integration in finite terms[END_REF][START_REF] Risch | The solution to the problem of integration in finite terms[END_REF] for indefinite integration. In [START_REF] Schneider | An implementation of Karr's summation algorithm in Mathematica[END_REF][START_REF] Schneider | Symbolic summation in difference fields[END_REF], it was observed for the first time that Karr's algorithm not only can solve Problem T but also Problem CT in ΠΣ-fields. More precisely, Karr's algorithm can solve Problem PLDE with m = 1. Analogously to the fact that the extended version of Gosper's algorithm [START_REF] Zeilberger | A fast algorithm for proving terminating hypergeometric identities[END_REF] represents a significant generalization to definite hypergeometric summation, with this observation Karr's algorithm can be viewed as a major step forward with respect to definite summation in general. Based on results in [Bro00], Karr's algorithm was streamlined in [START_REF] Schneider | Symbolic summation in difference fields[END_REF][START_REF] Schneider | Solving parameterized linear difference equations in ΠΣ-fields[END_REF] to a more compact and efficient algorithm. Moreover, in [START_REF] Schneider | Solving parameterized linear difference equations in ΠΣ-fields[END_REF][START_REF] Schneider | A collection of denominator bounds to solve parameterized linear difference equations in ΠΣ-extensions[END_REF][START_REF] Schneider | Degree bounds to find polynomial solutions of parameterized linear difference equations in ΠΣ-fields[END_REF] together with results from [START_REF] Bronstein | On solutions of linear ordinary difference equations in their coefficient field[END_REF], this streamlined algorithm was generalized to a method that enables the user to search for all solutions of Problem PLDE for an arbitrary order m. Although there are still open problems in the resulting algorithms, one finds eventually all the solutions for Problem PLDE by repeating the computation process and increasing step by step the range in which the solutions may exist; these ideas are presented in [START_REF] Schneider | Solving parameterized linear difference equations in ΠΣ-fields[END_REF].

Furthermore we want to emphasize that Sigma provides methods that enable the user to search for solutions of Problem PLDE in difference ring extensions, like (-1) k , that contain zero-divisors, like (1 -(-1) k )(1 + (-1) k ) = 0; for more details see [START_REF] Schneider | Symbolic summation in difference fields[END_REF]. Those ideas are partially needed in the computation steps In

A Rhombus Tiling Application

In the sequel we will prove the multisum identities (1) and (2) that arise in [START_REF] Fulmek | The number of rhombus tilings of a symmetric hexagon which contains a fixed rhombus on the symmetric axis[END_REF]. Following our definite summation spiral in Figure 1, those identities will not only be proven with our package Sigma, but we will also find their right hand sides.

First we set up the summation problem S

(1) n = mySum1 as carried out in In [2].

In[12]:= mySum1 = n ∑ k=1 - H k (3 + k + n)! . (-1) k . (-1) n . (1 + k)! . 2 (2 + k) (-k + n)! . ;

Finding a recurrence with creative telescoping

Given this sum expression, we are able to compute a recurrence relation of order three by solving the creative telescoping problem; see Problem CT.

In[13]:= creaSol1 = CreativeTelescoping[mySum1, n, RecOrder → 3] Out[13]= {0, 0, 0, 0, 1}, (2 + n) (3 + n) (4 + n) 2 (5 + n) (9 + 2 n), -(3 + n) (4 + n) (5 + n) (9 + 2 n) 13 + 8 n + n 2 , -(3 + n) (4 + n) (5 + n) (5 + 2 n) 6 + 6 n + n 2 , (3 + n) 2 (4 + n) (5 + n) 2 (5 + 2 n), -2 (1 + k) (5 + n) (5 + 2 n) (7 + 2 n) (9 + 2 n) ((-3 + k -n) (4 + k + n) + k (3 + n) (4 + n) H k ) (3 + k + n)! . (-1) k . (-1) n . / (1 -k + n) (2 -k + n) (3 -k + n) (1 + k)! . 2 (-k + n)! .
Here the second entry in the output of Out[13], say {c 0 (n), c 1 (n), c 2 (n), c 3 (n), g(n, k)}, gives the solution of Problem CT for d = 3 and the summand

f (n, k) = - H k (n + k + 3)!(-1) k (-1) n (k + 2)(k + 1)! 2 (n -k)! (20)
of S

(1) n = ∑ n k=1 f (n, k). Then, as described in Subsection 2.2.1, we can generate from this result a recurrence for S

(1) n with the function call

In[14]:= TransformToRecurrence[creaSol1, mySum1, n] Out[14]= (1 + n) (2 + n) 2 (3 + n) (4 + n) (9 + 2 n) n! . SUM[n]- (1 + n) (2 + n) (3 + n) (9 + 2 n) 13 + 8 n + n 2 n! . SUM[1 + n]- (1 + n) (2 + n) (3 + n) (5 + 2 n) 6 + 6 n + n 2 n! . SUM[2 + n]+ (1 + n) (2 + n) (3 + n) 2 (5 + n) (5 + 2 n) n! . SUM[3 + n] == -2 (5 + 2 n) (7 + 2 n) (9 + 2 n) (3 + n)! . (-1) n .

This means that SUM[n] = S

(1) n (=mySum1) satisfies the output recurrence Out[14]. We could also carry this out in one step by the call GenerateRecurrence[mySum, n, RecOrder → 3] which just gives the same recurrence as in Out[14]. We want to emphasize that the user can verify the correctness of recurrences independently of the steps of the algorithm, see the following remark.

(n + i, k) = f (n, k) f i where f 0 = 1, f 1 = - n + 4 + k n + 1 -k , f 2 = (n + 4 + k)(n + 5 + k) (n + 1 -k)(n + 2 -k) , f 3 = - (n + 4 + k)(n + 5 + k)(n + 6 + k) (n + 1 -k)(n + 2 -k)(n + 3 -k) .
Moreover note that the ΠΣ-term g(n, k) shifted in k can be rewritten as

g(n, k + 1) = - 2(k + 1)(n + 5)(n + 4 + k)(2n + 5)(2n + 7)(2n + 9) (k + 2)(n + 2 -k) × (H k (n 2 + 7n + 12) + k + 2) (n + k + 3)!(-1) k (-1) n (k + 1)! 2 (n -k)!
by using the relations H n+1 = H n + 1 n+1 and (-1) n+1 = -(-1) n . Then with these representations, we verify that (13) with d = 3 holds for all 0 ≤ k ≤ n. First we check that there do not occur any poles during the evaluation in the chosen representations of g(n, k), g(n, k + 1) and f (n + i, k) for 0 ≤ i ≤ 3 within the range 0 ≤ k ≤ n. Then we substitute those specific terms in g

(n, k + 1) -g(n, k) -(c 0 (n) f (n, k) + • • • + c 3 (n) f (n + 3, k))
, bring these expressions over a common denominator, and check symbolically that the polynomial expression in the numerator vanishes. This shows the correctness of (13) for 0 ≤ k ≤ n. Moreover, summing equation (13) over k from 0 to n gives

c 0 (n) n ∑ k=0 f (n, k) + • • • + c 3 (n) n ∑ k=0 f (n + 3, k) = g(n, n + 1) -g(n, 0).
(1 + n) ∑ n ι 1 =1 1+ι 1 ι 1 (2+ι 1 ) 2 (1 + n) , 1, (3 + 3 n + n 2 ) (-1) n . + 2 (1 + n) (2 + n) 2 (-1) n . ∑ n ι 1 =1 1+ι 1 ι 1 (2+ι 1 ) (1 + n) (2 + n)
Looking closer at this result, from the partial fraction decomposition of the summand

n ∑ i=1 i + 1 i(i + 2) = 1 2 n ∑ i=1 1 i + n ∑ i=1 1 i + 2
one sees immediately that this sum can be expressed in terms of the harmonic numbers H n . This cosmetic change of the solution representation can be also achieved by solving the recurrence again in the solution domain extended with H n .

Finding a closed form evaluation by combining the solutions

So far we computed a recurrence relation of order 3 for the definite sum S

(1) n , that holds for all n ≥ 0 (see Remark 2), and found solutions for that recurrence, that hold for all n ≥ 0 (see Remark 3). Therefore a closed form of S (1) n can be obtained by composing the particular linear combination of the homogeneous solutions plus the inhomogeneous solution that matches the first three initial values of (1) n for n = 0, 1, 2; see Subsection 2.2.4.

In[20]:= FindLinearCombination[recSol1, mySum1, 3, MinInitialValue → 0]

Out[20]= -5 -3 n -2 (1 + n) (2 + n) H n + 5 + 2 n -2 n 2 -n 3 + 2 (1 + n) (2 + n) 2 H n (-1) n . (1 + n) (2 + n)
This shows that

S

(1)

n = -5 -3n -2(1 + n)(2 + n)H n + 5 + 2n -2n 2 -n 3 + 2(1 + n)(2 + n) 2 H n (-1) n (1 + n)(2 + n) ,
or equivalently (1), holds for all n ≥ 0. which finally shows that (2) holds for all n ≥ 0.

Conclusions

In this survey article we illustrated how closed form evaluations of a very general class of definite multisums can be discovered with the summation package Sigma following the definite summation spiral. As example, we derived and proved the closed form evaluations of S (1) n and S

(2) n from [START_REF] Fulmek | The number of rhombus tilings of a symmetric hexagon which contains a fixed rhombus on the symmetric axis[END_REF] purely algorithmically with computer algebra methods. For these computations the user is completely dispensed from working explicitly in difference fields or rings; instead one can work conveniently in terms of usual sum and product expressions.

Fig. 1 :

 1 Fig. 1: The definite summation spiral.

  where a, b are of the form a = a 1 n + a 2 and b = b 1 n + b 2 with a 1 , b 1 ∈ Z and a 2 , b 2 independent of n. Find a recurrence of the form

  defined with Sigma-functions as carried out in In[2], by typing in creaSol = CreativeTelescoping[mySum, n, RecOrder → d] a set of creative telescoping solutions with (13) is searched where each found solution is encoded in the form * * {c 0 (n), c 1 (n), . . . , c d (n), g(n, k)}. Moreover, by entering TransformToRecurrence[creaSol, mySum, n] Note that this property holds for almost all ΠΣ-terms f (n, k) in k. * * In our implementation the trivial solution {0, . . . , 0, 1} with 1 -1 = 0 f (n, k) + • • • + 0 f (n + d, k) is always included in the set of output solutions. There might be several non-trivial solutions, if d is chosen too big.

  Therefore, Sigma provides the possibility to extend the underlying solution domain manually. Namely, by the function call SolveRecurrence[rec, S[k], Tower → {s 1 , . . . , s e }] one can search for all solutions S(k) in terms of sums and products occurring in the a i (k) and b(k) together with the additional sums and products given by s i (k); see also ΠΣ-Remark 3. The application of this feature is demonstrated in the computation steps In[19], In[25], and In[28].

  [5], In[18], In[19], In[25], and In[28].

Remark 2 .

 2 With the c i (n) and g(n, k) given in Out[13] one can show that S (1)n is a solution of the recurrence Out[14] as follows. For (20) observe that f

  In[18]:= SolveRecurrence[rec1, SUM[n], NestedSumExt → ∞] Out[18]= {0, 1}, {0, (2 + n) (-1) n . }, 0, -1 -2

  In[19]:= recSol1 = SolveRecurrence[rec1, SUM[n], Tower → {H n }] Out[19]= {0, 1}, 0, 3n 2 + 2 (1 + n) (2 + n) H n (1 + n) (2 + n) , {0, (2 + n) (-1) n . }, 1, (9 + 10 n + 3 n 2 + 2 (1 + n) (2 + n) 2 H n ) (-1) n . (1 + n) (2 + n)Remark 3. We want to point out that the correctness of the solutions in Out[19] for n ≥ 0 (or of the representations Out[17] or Out[18] from above) can be verified similarly as in Remark 2 by substituting the solutions in the recurrence of Out[15] and checking equality for the resulting equation. For instance, for the solutions given in Out[19], this can be achieved by applying the relations H n+1 = H n + 1 n+1 and (-1) n+1 = -(-1) n .

In[ 27 •

 27 ]:= SolveRecurrence[rec2, SUM[n], Tower → {(-1) n . }, NestedSumExt → ∞] Out[27]= {0, (1 + n) (2 + n) (3 + n)}, {0, (-1) n . }, 1, 1 + 3 n + n 2 + 2 (1 + n) (2 + n) (3 + n)In the end, we just solve the recurrence again in terms of H n and (-1) n which gives:In[28]:= recSol2 = SolveRecurrence[rec2, SUM[n], Tower → {H n , (-1) n . }] Out[28]= {0, (1 + n) (2 + n) (3 + n)}, {0, (-1) n . }, 1, 13 + 13 n + 3 n 2 + 2 (1 + n) (2 + n) (3 + n) H nThe correctness of these solutions for n ≥ 0 can be verified as sketched in Remark 3.Combining the solutions gives the closed form evaluation of T n = mySum2, namelyIn[29]:= FindLinearCombination[recSol2, mySum2, 2, MinInitialValue → 0] Out[29]= 1 -9 n -9 n 2 -2 n 3 + 2 (1 + n) (2 + n) (3 + n) H n -(-1) n .

† † If the option RecOrder → d is omitted in the function calls CreativeTelescoping or GenerateRecurrence, Sigma tries to solve Problem CT first for d = 1 and then for d = 2, 3, . . . until a solution is found; the termination is not guaranteed in this case.

Acknowledgements

I would like to thank Christian Krattenthaler for his valuable comments.

† Supported by the Austrian Academy of Sciences, the SFB-grant F1305 of the Austrian FWF and by grant P16613-N12 of the Austrian FWF 1365-8050 c 2004

Then with

for i ≥ 0, the correctness of the recurrence rec with SUM[n] = S

(1)

n follows for all n ≥ 0. Dividing the output recurrence in Out[14] by the non-zero factor (n + 3)(n + 2)(n + 1)n! (for n ≥ 0) gives the simplified version:

Solving the recurrence with sum solutions (d'Alembertian solutions)

In the next step we try to find solutions of the recurrence rec1 given in Out [15]. To accomplish this task, Sigma provides the following function call; see Subsection 2.2.2.

Internally Sigma constructs the underlying difference ring = Q(n)[(-1) n ] given by the objects in the recurrence and afterwards tries to solve the recurrence formulated in this algebraic setting A. In this case Sigma finds two linearly independent solutions of the homogeneous version of the recurrence, namely 1 and (n + 2)(-1) n .

Obviously, those solutions are not sufficient to describe the whole set of solutions of the given recurrence. Therefore we try to extend the underlying difference ring in form of sum solutions by setting in addition the option ‡ ‡ NestedSumExt → ∞; see Subsection 2.2.2.

In this example Sigma succeeded completely since it was able to compute three linearly independent solutions of the homogeneous version of the recurrence and one particular solution of the inhomogeneous recurrence itself.

Simplifying the solutions with indefinite summation

Now the essential step is that those two sum solutions in Out[17] can be simplified further with Sigma's indefinite summation algorithm; see identity (9). By default, i.e., omitting the option IndefiniteSummation → False, those sum solutions are simplified immediately which results in: ‡ ‡ Remarks concerning the option IndefiniteSummation → False are given in the next paragraph.

In the same spirit we are able to find a closed form evaluation for the hypergeometric sum

where S

(2) n = (1 -(-1) n (n + 2))T n . More precisely, we first compute a recurrence for T n = mySum2.

This means that SUM[n] = T n (=mySum2) satisfies the output recurrence Out [22] for n ≥ 0. Given the creative telescoping solution, the verification of this recurrence relation is immediate and is omitted here. Note that this recurrence could have been computed with any other implementation that can deal with creative telescoping for definite hypergeometric sums [Zei90, PWZ96], like for instance [START_REF] Paule | A Mathematica version of Zeilberger's algorithm for proving binomial coefficient identities[END_REF].

Dividing the output recurrence Out[22] by the non-zero term (n + 1)(n + 3)n! (for n ≥ 0) gives the simplified version:

Subsequently we solve the recurrence rec2 given in In

which gives just a solution of the homogeneous recurrence.

• Next, we ask for hypergeometric solutions of the homogeneous version of the recurrence. For instance, the implementations [START_REF] Petkovšek | Hypergeometric solutions of linear recurrences with polynomial coefficients[END_REF][START_REF] Van Hoeij | Rational solutions of linear difference equations[END_REF] give the additional solution (-1) n . This gives the following result.

• Finally, we look for sum solutions of the recurrence and get additionally an inhomogeneous solution. 6 + 13 ι 1 + 9 ι 2 1 + 2 ι 3 1 (-1) ι 1 .

Removing the option IndefiniteSummation → False in the previous function call, i.e., applying in addition Sigma's indefinite summation algorithm, leads to: