Juhani Karhumäki

Yury Lifshits

Wojciech Rytter

Tiling Periodicity

Keywords: algorithms on word, periodicities, tilers

.

Introduction

The number p is a full period (period, in short) of a word w of length n iff p|n and w i = w i+p whenever both sides are defined. Define by period(w) the shortest nonzero full period of w.

In this paper we extend the notion of a full period. Namely, we are interested in tilings of a word where the tiles themselves may contain "transparent" letters. A tiler (or partial word) is a word over the alphabet Σ∪{ }, where is a special transparent (or undefined) letter. In other words, a tiler is a sequence of ordinary words over Σ (connected blocks) with gaps between the blocks. The size of a tiler is the number of defined symbols. Imagine that we have several copies of a tiler printed on transparencies. Then, this tiler is a period for some word, if we can put these copies into the stack such that they form a single connected word without overlapping of visible letters.

Thus, a tiler S is called a tiling period of an (ordinary) word T if we can split T into disjoint parallel copies of S satisfying the following:

(a) All defined (visible) letters of S-copies match the text letters;

(b) Every text letter is covered by exactly one defined (visible) letter. Similarly we define a tiling period y of a tiler x: x consists of several disjoint copies of y. The word (a tiler) is primitive if it has no proper tiling period. The tiling period of x is minimal iff it has minimum size. Denote by TILERS(w) the set of tilers of w.

Example. For example Both tilers have size 4, the first one is not primitive (it has a proper tiling period a b).

Problems. We investigate basic properties of tiling periodicity and compare it to the classical notion. We address the following questions:

1. How to enlist all possible tiling periods?

2. Does every word have a unique primitive tiling period?

3. How to find all tiling periods of minimal size?

4. How many periods can a word of length n have?

5. What is the relation between the primitive classical and the primitive tiling periods?

We have several reasons to be interested in tiling periodicity. Firstly of all, it is a natural generalization of classical notion, i.e. any full period is also a tiling period. Secondly, in the case when a tiling period is relatively small, we can describe a long word by just its tiling period and the length. Indeed, one can recover the original word by recursively adding another copy of the tiling period from the current leftmost uncovered position. Hence, we get a new class of words with low Kolmogorov complexity. Tiling periodicity might be useful for the new text compression methods (especially for generalizing runlength encoding). Note here, that the ratio between the "size" of tiling period and the length of classical full period may be arbitrarily small. Next, the notion of tiling periodicity provides a geometrical intuition about structure of the text. We have a conjecture that tiling periodicity is not expressible by word equations. Yet another motivation for studying tiling periodicity is a hope for applications in pattern discovery in some real data.

There are natural sources of tiling periodicity when considering multidimensional n 1 × • • • × n d rectangles. Let every integer point in it be colored. We sort all points in lexicographical order of their coordinates and write down all their colors in a single sequence. Assume that the initial rectangle was tiled by a smaller one m 1 × • • • × m d where m 1 |n 1 , . . . , m d |n d and every copy of the smaller rectangle was colored in the same way. Then the color sequence for the bigger rectangle has a tiling period. We comment this example later after introducing some useful terminology. Automatically generated texts and XML-files might be another possible sources of tiling periodicity. As an example, consider a periodic list of objects written in the following way: "attribute 1 of object 1, . . . , attribute 1 of object n, attribute 2 of object 1, . . . , attribute 2 of object n". This sequence has a tiling period but not necessary a classic one.

Our results. Tiling periodicity looks very simple and natural, but up to our knowledge it was never formulated before in its whole generality. We introduce a partial order on tiling periods and discover that contrary to the classical case there might be several incomparable primitive tiling periods. This helps to disprove a common subtiler conjecture by Tero Harju [START_REF] Harju | Defect theorem, lecture notes of "Combinatorics of words" Tarragona course[END_REF]. However we prove that every primitive tiling period of a word T is also a tiling period of the primitive full period of T . This property tells us that tiling periodicity lives "inside" classical one. Finally, we present an algorithm which in O(n log(n) log log(n)) time finds a tiling period of minimal size, the number of such periods and their compact representation. We present a complete hierarchy of all possible tiling periods. In particular we get a recursive formula for computing function L(n) that gives the maximal number of tiling periods for a unary word of length n. The value L(n) might be even more than the text length. Actually, Bodini and Rivals obtain this recursive formula a few months earlier: their paper [START_REF] Bodini | Tiling an interval of the discrete line[END_REF] was submitted in January 2006, while our results were reported only in May 2006 [START_REF] Karhumäki | Tiling periodicity[END_REF]. Here we keep our proof since (comparing to [START_REF] Bodini | Tiling an interval of the discrete line[END_REF]) it constructs explicit one-to-one correspondence between tilers and length factorizations, and introduces levels in the set of all tilers.

Related results

Prior to other work only tilings of a unary word were considered [START_REF] Bodini | Tiling an interval of the discrete line[END_REF]. In the paper [START_REF] Pisanti | Bases of motifs for generating repeated patterns with wild cards[END_REF] authors present an algorithm for finding all tilers that have at least q (quorum parameter) matches with the text.

Another related notion is cover [START_REF] Apostolico | Optimal superprimitivity testing for strings[END_REF]: a word C is a cover for a word T if any letter of T belongs to some occurrence of C in T . One of the most important results related to periodicity is a theorem by Fine and Wilf [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF]. They studied the necessary and sufficient condition under which from p-periodicity and q-periodicity we can derive gcd(p, q)-periodicity (recall that gcd is the greatest common divisor).

We tried to prove the similar property for tiling periods. Surprisingly, it does not hold. Even two tiling periods of the same text may have no common subperiod. Our attempt to generalize the notion of periodicity is not the first one.

Recently, Simpson and Tijdeman generalized Fine and Wilf theorem for multidimensional periodicity [START_REF] Simpson | Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester[END_REF]. Berstel and Boasson [START_REF] Boasson | Partial words and a theorem of Fine and Wilf[END_REF] followed by Shur and Konovalova (Gamzova) [START_REF] Shur | On the periods of partial words[END_REF][START_REF] Shur | Partial words and the periods' interaction property[END_REF] and Blanchet-Sadri [START_REF] Blanchet-Sadri | Periodicity on partial words[END_REF] extensively studied partial words and their periodicity properties.

However, overlapping of periods (where every letter of the text is covered exactly once) were not considered and therefore in their terms only partial words may have partial periods (i.e. periods with gaps). In the paper [START_REF] Iliopoulos | String regularities with don't cares[END_REF] borders of a partial word are studied. Katona and Szàsz introduced in [START_REF] Katona | Matching problems[END_REF] a sort of tiling periodicity in two dimensions. They consider tilers consisting only of two characters. The notion of periodicity was generalized for infinite words under the name almost periodic sequences, see e.g. [START_REF] Pritykin | Almost periodicity and finite automata[END_REF].

Multiperiods

Assume we count positions starting from 0. For a divisor p of n, by p-block we mean a subword of the form

x[i • p..(i + 1) • p -1], where 0 ≤ i ≤ (n -1)/p
We say that a word T = T 0 . . . T n-1 has a multi-period (a, b) (or a period a ranged by b) if b|n, and all b-blocks have a full period a. Observe that the word corresponding to this period can be different in each block. Classical full period p coincides with the multi-period (p, n). The weight of the muiltiperiod (p, q) is q p . In Figure 2 we have;

weight(1, 2) = 2 1 , weight(4, 8) = 8 4
, weight(16, 32) = 32 16 .

Each proper multiperiod gives a samller tiler and chains of multiperiods correspond to tilers, see Figure 2.

We make it more precise in the series of lemmas below.

Lemma 1. A word T has a tiling period with the code

n 1 •. . . •n 2k or n 1 •. . . •n 2k+1 iff it has multi-periods respectively (n 1 , n 1 n 2 ), . . . , ( 2k-1 i=1 n i , 2k i=1 n i ) or (n 1 , n 1 n 2 ), . . . , ( 2k-1 i=1 n i , 2k i=1 n i ).
Proof:

Step 1: from tiling period P to multiperiodicity. We use induction over tiler's level.

Consider the corresponding text tiling. Recall that all copies of P can be divided into groups of size n 2 with internal shifts 0, n 1 , . . . , n 1 (n 2 -1).

If we divide the whole text into the blocks of size n 1 n 2 , every block is covered by P -copies from the same groups, and therefore it is n 1 -periodic (inside the block). We proved (n 1 , n 1 n 2 )multiperiodicity. All others follow from the induction hypothesis for the plain power of P .

Step 2: from multi-periods to a tiling periodicity. Consider the top multi-period ( 2k-1

i=1 n i , 2k i=1 n i ).
Let us consider the text tiling by tiler Q with the code

( 2k-1 i=1 n i ) • n 2k
for the first statement of lemma and Q with the code ( 2k-1

i=1 n i ) • n 2k • n 2k+1 for the second case.
Directly from this top multiperiodicity every copy of Q has the same characters on the same places. Hence, Q is a tiling period for the text. Continuing the reasoning, with the help of the second multiperiodicity we find another tiling period R inside Q. Finally, the last multiperiodicity gives us the tiling period with the code we promised in the lemma's statement.

Lemma 2.

If the text T has a full period p and a multi-period (a, b), then either b|p or the text has also full period gcd(a, p).

Proof: Take any letter T i . We are going to make several moves of size ±p and +a for reaching position i + gcd(a, p). We want to have the same character after every move and hence we can not make a move of size +a from the last a-blocks in every b-block. As we know from extended Euclid algorithm, there exist integers k and l such that gcd(a, p) = ka -lp.

We will use the following greedy strategy. If we are able to make a move of size +a we do this. Otherwise we try to make several moves of size ±p. After making exactly k moves of size +a we just make all the remaining moves of size ±p and we are done. We cannot follow greedy strategy only if for some position j < p from all points j, j + p, . . . j + ( n p -1)p we cannot jump +a. This means that all that points belong to the last a-groups in b-blocks. Suppose now that p is not divided by b. there exists all residues h modulo b such that h ≡ j(mod u). Hence, one of these values is smaller than u which does not exceed b/2. But this means that the corresponding point does not belong to the last a-group in the b-block.

Theorem 1. Any primitive tiling period Q of word T is also a tiling period for the primitive full period of T .

Proof: We use induction over the text length. In the case of the text of length one the theorem is true. Let now p be the length of the full period and (a, b) be the top multiperiodicity from the code of Q (here we use Lemma 1). For p = n, the theorem follows immediately. Assume now that p < n. By hierarchial construction Q consists of some letters from the first a-block in every b-blocks in the text. Let us apply Lemma 2. If b|p, then we can produce a new tiling period Q restricting Q to the first p symbols in the text. By p-periodicity Q can be split in several parallel copies of Q with shifts 0, p, 2p, . . . , ( n p -1)p.

We get the contradiction against the primitivity of Q.

Therefore the text has full period gcd(a, p). But p is the minimal full period. Hence, p|a. Since the text is p-periodic, it is also a-periodic and b-periodic. That means that we can again restrict Q only for the first a-block. Either we get a new smaller tiling period Q (and that gives us contradiction) or b = n and all letters of Q belong to the first a-block.

We now see that both full period p and the tiling period Q are periods for the first a-block. Since a ≤ b/2 ≤ n/2, we can apply induction hypothesis. Since p and Q are primitive tiling/full periods for the first a block, induction hypothesis implies that Q is a tiling period of the primitive full period of word T . Theorem is proved.

Corollary 1. Take any tiling period Q and any full period p. Then they have a common "tiling subperiod".

Proof: Consider a primitive tiling period Q that is smaller than Q. Consider the primitive full period p . From folklore we know that p |p. By Theorem 2 Q is a tiling period for the first p -block of the text. Hence, Q is the required tiling subperiod for Q and p.

Remark. Using the technique from Lemma 1, Lemma 2 and Theorem 2 it is possible to prove that the primitive tiling period is unique for n = 2 k . The proof scheme goes as follows. Take two primitive incomparable tiling periods. Consider their top multiperiodicities. Apply the reasoning of Lemma 2. Either one of the periods is not primitive or these multiperiodicities are the same. Going down we prove either their equivalence or their non-primitivity.

Algorithm Compute-Minimal-Tilers

We define the size of tiling period as the number of defined letters in it. In the algorithm we use the fact that for every tiling period there is a corresponding chain of embedded multiperiodicities (a 1 , b 1 ), . . . , (a k , b k ). By "embedded" we mean that b i+1 |a i holds for every i. Notice that the size of a tiling period is equal to n 3. Find in G a path π having maximal product val(π) of its node-weights; 4. Output tiler(w, π) constructed by algorithm in Lemma 2, the size of the computed tiler is n val(π) . Comment: the number of minimal tilers equals the number of maximum weight paths in the acyclic graph G.

We describe how to construct the tiler tiler(w, π) corresponding to a path π of multi-periods: π = (p 1 , q 1 ) → (p 2 , q 2 ) → (p 3 , q 3 ) → . . . (p k , q k ). For each p i -block of w we replace all symbols which are not in the first q i block in this block by . Then from the resulting word we remove all ending 's.

Remark. The following O(n) size max-paths graph representation G ⊆ G of all tiling periods of minimal size can be constructed with additional linear work (since the graph is extremely small). For each vertex v of G compute all outgoing edges which are on a maximal path starting from v. The graph of all edges on maximal-product paths represents all tiling periods of minimal size. In particular we can compute easily the number of such periods. [START_REF] Shur | On the periods of partial words[END_REF]32) (4,8) (1,2)

Efficient implementation of algorithm Compute-Minimal-Tilers

We describe now an efficient implementation. Let w be a word of length n and let Divisors(n) denotes the set of divisors of n. The subwords are given by their starting-ending positions in w. Recall that by p-block we always mean a subword of length p with a starting position being multiple of p. Denote by period(w) the size of the smallest full period of a word w. The basic operation in the algorithm Compute-Minimal-Tilers is the boolean function M ultiP eriod(q, p), called main query, which can be expressed in terminology of the blocks as follows:

MultiPeriod(q, p): for given p, q ∈ Divisors(n) check if each p-block has a full period q.

Theorem 2. [Fast-Preprocessing]

We can preprocess the word in O(n log n log log n) time in such a way that each MultiPeriod query can be answered in constant time.

The algorithm Compute-Minimal-Tilers is doing a sublinear number of MultiPeriod queries, hence the theorem implies immediately the following speed-up result.

Theorem 3. The minimal-size tiler of a word can be found in O(n log n log log n) time.

We now show the proof of Theorem 2. Firstly we introduce and concentrate on small queries. A small query operation is to compute for a given subword u of w (given by interval in w) the value period(u).

We say that a natural number is a 2-power number if it is a power of two. We use the idea of basic factors: the subwords with 2-power lengths. Denote by subword k (i) the subword of size 2 k starting at position i in a given word w. We can add suitable number of endmarkers to guarantee that for each original position we have subword of the corresponding length.

Define the table N EXT such that for each

0 ≤ k ≤ log n, 0 ≤ i < n the value of N EXT [k, i] is the first position j > i such that subword k (i) = subword k (j). If there is no such j then N EXT [k, i] = -1.
Our basic data structure is the dictionary of basic factors, we refer to [START_REF] Crochemore | Jewels of stringology: text algorithms[END_REF] for detailed definition. Denote this data structure by DBF (w). For each position i in w and 0 ≤ k ≤ log n we have a unique label Proof: The table N AM E is the basic part of DBF (w) and can be computed within required complexity using Karp-Miller-Rosenberg algorithm, see [START_REF] Crochemore | Jewels of stringology: text algorithms[END_REF].

N AM E[k, i] ∈ [1..n] such that subword k (i) = subword k (j) ⇔ N AM E[k, i] = N AM E[k, j].
We show how to compute the table N EXT . Let us fix k ≤ log n. We sort lexicographically the pairs (N AM E[k, i], i). Then the block of elements in the sorted sequence with the same first component r gives the increasing sequence of positions i with the same value

N AM E[k, i] = r. Let SORT ED 1 [j], SORT ED 2 [j]
be the first and second component of the j-th pair in the sorted sequence.

We execute:

for i := 0 to n -1 do NAME[k,i]:=-1; for j := 1 to n -1 do if SORT ED 1 [j -1] = SORT ED[j] then N EXT [k, SORT ED 2 [j -1] := SORT ED 2 [j];
The radix sorting of pairs of integers can be done in linear time for each k. We have logarithmic number of k's, hence the whole computation of N EXT takes O(n log n) time. This completes the proof of the lemma.

Lemma 5. [Small Queries]

Assume the tables NAME and NEXT are already computed. Then for any subword u of w (given by interval in w) we can compute period(u) in O(log n) time.

Proof:

We show now how we compute period(u) for u = w[p..q]. We can check if u has a full period of length u/2 or u/3 in constant time, since we can check equality of constant number of subwords in constant time. The DBF data structure allows to check in constant time equality of subwords which lengths are not necessarily 2-powers (decomposing them into ones which are, possibly overlapping each other). Now let us go to smaller candidate periods, assume period(u) ≤ |u|/4. Let us take the prefix v of u which size is a largest power

2 k such that |u|/4 ≤ 2 k ≤ |u|/2. Claim. Let u = w[p..q], if period(w[p..q]) ≤ |v|/4 then period(v) is equal to N EXT [k, p] -p.
The claim follows from the fact that period(u) in this case is a size of a primitive word v such that u is a full power of v. This primitive word can start an occurrence only at positions which are multiples of v, due to primitivity. Hence the first such internal position after p should be equal to |v| = period(u). We can verify this "candidate period" in O(log n) time using NAME table. This completes the proof of the lemma.

We define now the following data structure. For each p ∈ Divisors(n) define LCM [p] as the least common multiple of the smallest full periods of all p-blocks of w. Lemma 6. We can precompute the table LCM in O(n log n log log n) time.

To construct the new tiler Q we take every block of P , divide it into m 3 groups of size m 1 • m 2 , and in every such group keep only first m 1 letters. We can notice that P can be tiled by m 2 copies of Q (with shifts 0, m 1 , . . . , m 1 •(m 2 -1)). Hence, Q is also a tiling period for the text with the code m 1 •m 2 •m 3 •n 2 • . . . •n k . Note, that our construction maintains the inequality n 2 , . . . , n k ≥ 2 for all codes.

We now prove that any tiling period is included in our construction. Consider a tiler P . Let s be the block size and g • s be the length of the first gap. The plain power of P is defined as the union of P -copies shifted by 0, s, 2s, . . . , g • s.

Claim. The plain power of any tiling period P is also a tiling period.

Proof of the claim.

Take a text splitting in P -copies. Let s be the block size and g • s be the length of the first gap. We divide all copies of P into groups of g + 1 copies in the following way. Consider all P -copies from the left to the right. The gap between first two blocks of the first copy can be filled only by first blocks of other P -copies.

These copies together with the first one form the first group. Now assume that we already formed several such groups. Consider the first copy of P unused so far. Look at its first gap. All P -copies from the previous groups has long (at least s • (g + 1)) continuous blocks. Hence, this gap is also filled by new, still unused P -copies. Since we process all copies from the left one to the right one, all of them contribute to this gap filling by their first block.

Therefore these copies form the next group we need. Every group itself is exactly a plain power of P . Hence, the initial text has also splitting in the plain power copies. The claim is proved.

Assume now that there exists some P outside of our construction. Then there also exists some tiling period P such that (1) it is outside of our hierarchy and (2) its plain power Q is included in our hierarchy. Let us derive a contradiction from that.

Indeed, let n 1 •. . . •n k be the code of Q, let s be the block size of P and s • g be the length of its first gap.

Then n 1 is the block size of Q and it is a multiple of s • (g + 1). Let m 1 = s, m 2 = g + 1, m 3 = n 1 /(s • (g + 1)). Now we see that P is in fact included in our hierarchy as a tiling period with the code

m 1 • m 2 • m 3 • n 2 • . . . •n k .
Therefore, our hierarchy is complete.

Corollary 2. Let L(n) be the number of tiling periods for the word of length n over a unary alphabet. Then the following recurrence rule is true:

L(1) = 1; L(n) = 1 + d|n,d =n L(d).
Proof of Corollary 2: The theorem above states that L(n) is equal to the number of factorizations n = n 1 •. . . •n k , where n 2 , . . . , n k ≥ 2. By grouping all decompositions by the rightmost factor we obtain the recurrence formula of Corollary 2.

Remark. Two related sequences are included in the On-line Encyclopedia of Integer Sequences [START_REF] Sloane | The on-line encyclopedia of integer sequences[END_REF] maintained by N.J.A. Sloane. The sequence A067824 is defined by the formula in Corollary 2.

The sequence A107736 is the number of polynomials p with coefficients in {0, 1} that divide x n -1 and such that (x n -1)/((x -1)p(x)) has all coefficients in {0, 1}. But this is exactly the number of tiling periods for the unary text of the length n. Indeed, multiplying p by some polynomial with coefficients in {0, 1} we are trying to split n "ones" in several parallel copies of p without overlapping. Till August 2006 Encyclopedia indicated that "A067824 and A107736 agree at least on first 300 terms, but no proof of equivalence is known".

After recent work [START_REF] Bodini | Tiling an interval of the discrete line[END_REF], Theorem 1 and Corollary 2 give a new independent proof of their equality. Indeed, the number of polynomials is equal to the number of tiling periods, the number of tiling periods is equal to the number of factorizations (Theorem 1), the number of factorizations satisfies the recursive formula (Corollary 2). The function L(n) and the number of factorizations also appear in Knuth's book [START_REF] Knuth | The Art of Computer Programming[END_REF]. However, no closed formula for L(n) is known so far.

Primitive and incomparabe minimal tilers

We say that one tiler S is smaller than another tiler Q, and write S ≺ Q, if S is a proper tiling period of Q. In the case of full periodicity any text has a single primitive full period. We are interested in the following question: is it true that for every ordinary word there exists a unique primitive tiling period (i.e. it is smaller than any other tiling period)? It can be reformulated in an alternative way: do any two tiling periods have a common tiling "subperiod"? Surprisingly, the answer is negative. Figure 4 presents the shortest known example T (24 letters) with two incomparable periods.

We can get more incomparable tiling periods. Let T a1b1 and T a2b2 be obtained from T by just using different letters.

We construct the text T 2 by replacing every a in T by T a1b1 and every b in T by T a2b2 . Now we can describe four incomparable tiling periods for T 2 . The text T 2 has length 24 2 . Group all letters to 24 blocks of 24 letters. Choose 12 of blocks using one of two partial words above.

Then inside each block also keep only 12 letters using either first or second tiling period (the same in every block).

We can repeat the construction several times. The text T k has size 24 k and has 2 k incomparable periods. Asymptotically it has n In 2003 in his lecture course [START_REF] Harju | Defect theorem, lecture notes of "Combinatorics of words" Tarragona course[END_REF] Tero Harju asked the following question. Assume that some colored cellular figure has tiling by one pattern and by another one. Is it always true that there exists the third one such that both first two can be tiled by that third one? This question is motivated by studying defect effect in combinatorics of words [START_REF] Harju | Many aspects of defect theorems[END_REF]. Our example shows that the answer is negative even for one-dimensional (but disconnected!) figures.

Directions for Further Work

There are a lot of natural, important and perhaps not so difficult questions we can suggest for further work on tiling periodicity. They are summarized in the list below.

1. Introduce and study not full tiling periodicity, approximate tiling periodicity, tilings by two (or more) partial words. This kind of tilings might be even more useful for compression purposes.

2. Calculate how often do words have proper tiling periods for various models of random words.

Compare the answer with the classical case. Characterize the equivalent of primitive words.

3. Is it true that all primitive tiling periods are minimal-size tiling periods?

  TILERS(a a a a b b b b a a a a b b b b), a b c d ∈ TILERS(a b b a a b b c c d d c c d d)

Fig. 1 :Fig. 2 :

 12 Fig. 1: a b c d is a tiler of ((a 2 b 2 ) 2 (c 2 d 2 ) 2 ) 2 .

  Then u = gcd(p, b) ≤ b 2 Since p|n and b|n. Among the numbers j mod b, . . . , j + ( n p -1)p mod b

1 .

 1 Compute the set M of multiperiods (a, b) of w; 2. Construct the following acyclic tiling graph G = (V, E) of multi-periods. (a) The set V of vertices of G is M ; (b) E = {(a, b) → (c, d) : d|a}. (c) Assign the weight to every node (a, b) ∈ V as the wight b a of the corresponding multiperiod.

Fig. 3 :

 3 Fig. 3: The graph G for the word w = aabbaabbccddccddaabbaabbccddccdd. The path with maximal product of weights is π : (16, 32) → (4, 8) → (1, 2). We have val(π) = 8 and tiler(w, π) = a b c d. The size of tiler(w, π) equals 32 8 , since n = |w| = 32.

Lemma 3 .

 3 Assume we can preprocess the word in time O(F (n)) to compute each query MultiPeriod in logarithmic time. Then the algorithm works in time O(n + F (n)), Proof: By d(n) we denote the number of divisors of n. It is known that d(n) = O(n ), for any constant > 0. Hence the number of nodes and edges is O(n). The construction of the graph can be done in linear time after preprocessing. Computation of a maximal path in time O(n) is very easy, since it is an acyclic graph with linear number of edges.

Lemma 4 .

 4 The tables NAME and NEXT can be computed in O(n log n) time.

5 √Fig. 4 :

 54 Fig.4: Two primitive tiling periods of an example word, both of size 12.

† Supported by grant N 8206039 of the Academy of Finland. ‡ Supported by grants INTAS 04-77-7173 and NSh-8464.2006.1. The results of this paper have been first presented at the

Proof: Assume we constructed tables N EXT and N AM E. We can do it within required complexity due to Lemma 4. Then for each p ∈ Divisors(n) we can compute the set of periods of p-blocks in time O(p log n) due to Lemma 5. Then we compute the lowest common multiple of all these periods in time O(p log n) for each p. Now the thesis follows from the well known number-theory fact that

This completes the proof of the lemma.

We can finish now the proof of Theorem 2. We know that M ultiP eriod(p, q) = true iff LCM [p] is a divisor of q. This property can be checked in constant time using the precomputed values of LCM [p]. Consequently, this completes the proof of Theorem 2.

Tilers of unary words

We consider now the situation when the number of tilers in a word is maximal. This happens for a unary word of length n (i.e only one character is used).

Then we reformulate tiling periodicity in the algebraic terms (like s i = s i+p for full periodicity). This reformulation helps us to prove that any primitive tiling period is smaller than the primitive full period and to compute all tiling periods of minimal size. Lemma 7. Take any tiling period P . Then all continuous blocks in P are of the same size s and the length of any gap in P is a multiple of s.

Proof: Indeed, in the text tiling the second copy of P is shifted by the size of the first block s 1 . Hence, for avoiding overlapping all other blocks are smaller or equal than s 1 . Assume now, that the block b is the first one which is strictly smaller than s 1 .

Then the gap between b in the first copy of P and b in the second copy of P is smaller than s 1 . Hence, that gap cannot be filled by anything. Every gap in P is filled by one or several blocks of some copies of P . Hence it must be a multiple of s.

Theorem 4. There is a one-to-one correspondence between tiling periods of a unary word and decompositions n = n 1 • . . . •n k , where n 2 , . . . , n k ≥ 2.

Proof: At first, we describe a set of tiling periods (hierarchial construction) for the word of length n over the unary alphabet. Then we prove that this set is complete, i.e. contains all possible tiling periods.

We divide the set of all periods in levels. Every period in our system is associated with a special code. The whole text itself is the only period from 0-level and has the code n. For every decomposition n = n 1 • n 2 with n 2 ≥ 2 the block of size n 1 is a period from 1-level with a code n 1 • n 2 . The 0-level and 1-level actually represent all classical (i.e. connected) full periods.

We now explain how to construct a period Q of k + 1-level from a period P of k -1-level with the code n 1 • . . . •n k .

Take any decomposition n 1 = m 1 • m 2 • m 3 with m 2 , m 3 ≥ 2. Through all our construction the first number of a code is equal to block size of a tiling period (all continuous blocks have equal sizes in our constructions).


Robert F Bailey
email: robert.bailey@uregina.ca.

Karen Meagher
email: karen.meagher@uregina.ca.

On the metric dimension of Grassmann graphs

Keywords:

The metric dimension of a graph Γ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. We consider the Grassmann graph Gq(n, k) (whose vertices are the k-subspaces of F n q , and are adjacent if they intersect in a (k -1)-subspace) for k ≥ 2. We find an upper bound on its metric dimension, which is equal to the number of 1-dimensional subspaces of F n q . We also give a construction of a resolving set of this size in the case where k + 1 divides n, and a related construction in other cases.

Introduction

In this paper, we are concerned with finding an upper bound on the metric dimension of Grassmann graphs. We use the notation of [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF]. To define the metric dimension of a graph, we need the following concept.

Definition 1 A resolving set for a graph Γ = (V, E) is a set of vertices S = {v 1 , . . . , v k } such that for all w ∈ V , the list of distances D(w|S) = (d(w, v 1 ), . . . , d(w, v k )) uniquely determines w.

That is, S is a resolving set for Γ if for any pair of vertices u, w, D(u|S) = D(w|S) if and only if u = w. We call the list of distances D(w|S) the code of the vertex w, so S is a resolving set if and only if each vertex has a different code.

Definition 2

The metric dimension of Γ, denoted µ(Γ), is the smallest size of a resolving set for Γ.

Metric dimension was first introduced in the 1970s, independently by Harary and Melter [START_REF] Harary | On the metric dimension of a graph[END_REF] and by Slater [START_REF] Slater | Leaves of trees[END_REF]. In recent years, a considerable literature has developed (see [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF] for details). A particularly interesting case is that of distance-regular graphs (we refer the reader to the book by Brouwer, Cohen and Neumaier [START_REF] Brouwer | Distance-Regular Graphs[END_REF] for background on this topic). In fact, in the case of primitive distance-regular graphs, bounds on a parameter equivalent to the metric dimension were obtained in 1981 by Babai [START_REF] Babai | On the order of uniprimitive permutation groups[END_REF] (where they were used to obtain combinatorial bounds on the possible orders of primitive permutation groups: see [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF] for further details).

Many families of distance-regular graphs are so-called "graphs with classical parameters" (see [START_REF] Brouwer | Distance-Regular Graphs[END_REF]Chapter 9]): these include the well-known Hamming graphs and Johnson graphs, for which metric dimension has already been studied. In the case of Hamming graphs, various results on the metric dimension have been obtained (although not always phrased in these terms: see [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF]). For the Johnson graphs J(n, k), where the vertices are k-subsets of an n-set, and two k-subsets are adjacent if they intersect in a (k -1)set, the exact value is known for k = 2: this was obtained by Cameron and the first author in [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF]. For k ≥ 3 bounds have been obtained by the authors and others in [START_REF] Bailey | Resolving sets in Johnson and Kneser graphs[END_REF][START_REF] Cáceres | Dimensión métrica y número determinante de los grafos de kneser y los grafos de johnson[END_REF]; the following result appears in [START_REF] Bailey | Resolving sets in Johnson and Kneser graphs[END_REF].

Theorem 3 The metric dimension of the Johnson graph J(n, k) is at most n.

After the Johnson graphs, the obvious next family to consider is the Grassmann graphs. Throughout this paper, V (n, q) denotes the n-dimensional vector space over the finite field F q .

Definition 4 The Grassmann graph G q (n, k) has as its vertex set the set of all k-dimensional subspaces of V (n, q), and two vertices are adjacent if the corresponding subspaces intersect in a subspace of dimension k -1.

Note that if k = 1, we have a complete graph, so we shall assume that k ≥ 2. Also, it is not difficult to show that G q (n, k) ∼ = G q (n, n -k), so it suffices to consider k ≤ n/2. The number of vertices is simply the Gaussian binomial coefficient:

n k q = k-1 i=0 (q n -q i ) (q k -q i ) .
The Grassmann graph is a distance-regular graph of diameter k: the distance between two vertices X and

Y is k -dim(X ∩ Y ).
It is considered to be the "q-analogue" of the Johnson graph J(n, k).

Having defined the Grassmann graphs, we are now ready to state our main result.

Theorem 5 Let G q (n, k) be the Grassmann graph, where 2 ≤ k ≤ n/2. Then the metric dimension of G q (n, k) is at most n 1 q . This bound, and its proof, are inspired by a similar result for the Johnson graph J(n, k) given in Theorem 3 above.

Proof of the bound

The proof of Theorem 5 uses linear algebra, and is similar to an analogous proof given in [START_REF] Bailey | Resolving sets in Johnson and Kneser graphs[END_REF] for the Johnson graphs. We observe that a collection of k-subspaces {U 1 , . . . , U m } of V (n, q) is a resolving set for the Grassmann graph G q (n, k) if and only if, for any pair of distinct k-subspaces A, B ≤ V (n, q), we have

(dim(A ∩ U 1 ), . . . , dim(A ∩ U m )) = (dim(B ∩ U 1 ), . . . , dim(B ∩ U m )). (1)
Consider the collection of all 1-dimensional subspaces of V (n, q), and label these as L 1 , . . . , L N (where N = n 1 q ). The incidence vector of a k-subspace U is the vector (u 1 , . . . , u N ) ∈ R N whose entries are

u i = 1 if L i ≤ U , 0 otherwise.
Furthermore, given a collection of k-subspaces S = {U 1 , . . . , U m }, the incidence matrix of S is the m × N matrix whose rows are the incidence vectors of U 1 , . . . , U m .

Lemma 6 If M is the incidence matrix of a family S = {U 1 , . . . , U m } of k-subspaces of V (n, q), and rank(M ) = n 1 q , then S is a resolving set for G q (n, k).

Proof: Suppose we have two distinct k-subspaces A, B ≤ V (n, q), whose incidence vectors are a, b respectively. Now, consider the entries of the vector M a T : by construction, we have that the entry in position i of M a T is precisely the number of 1-dimensional subspaces in A ∩ U i , which is di 1 q (where

d i = dim(A ∩ U i )). Consequently, it follows that if M a T = M b T , then condition (1) holds. Also, it is clear that if rank(M ) = n
1 q , the linear transformation represented by M is one-to-one, and thus M a T = M b T for any distinct vectors a, b.

Hence, if rank(M ) = n 1 q , condition (1) holds for any distinct k-subspaces A, B, and therefore S is a resolving set for G q (n, k).

2

So to prove Theorem 5, it remains to show that a family of subsets which such an incidence matrix actually exists. We will do this by showing that the incidence matrix of all k-subspaces has rank n 1 q . Recall that, for any real matrix M , we have rank(M T M ) = rank(M ).

Lemma 7 Let M be the incidence matrix of the set of all k-subspaces of V (n, q). Then rank(M ) = n 1 q .

Proof: Consider the matrix M T M , which is an n 1 q × n 1 q square matrix. Now, the diagonal entries of M T M are all n-1 k-1 q : this corresponds to the number of k-subspaces containing a given 1-subspace. Also, the off-diagonal entries of M T M are all n-2 k-2 q : this corresponds to the number of k-subspaces containing a given pair of 1-subspaces. Therefore, we have

M T M = n -2 k -2 q J + n -1 k -1 q - n -2 k -2 q I
(where I is the identity matrix and J the all-ones matrix). It is then a straightforward exercise to see that det(M T M ) = 0, and thus rank(M ) = rank(M T M ) = n 1 q . 2 Proof of Theorem 5: Let M denote the incidence matrix of all k-subspaces of V (n, q). By Lemma 7, this matrix has rank n 1 q ; in particular, M has an invertible n 1 q × n 1 q submatrix M . By Lemma 6, M is the incidence matrix of a resolving set for G q (n, k) of size n 1 q . Consequently the metric dimension of

G q (n, k) is at most n 1 q . 2 3

Constructions of resolving sets

The disadvantage of the proof of Theorem 5 given above is that it does not provide an explicit construction of a resolving set for the Grassmann graph G q (n, k). In this section, we address this issue; once again, we adapt earlier results for Johnson graphs.

In [START_REF] Cáceres | Dimensión métrica y número determinante de los grafos de kneser y los grafos de johnson[END_REF], Cáceres et al. give a construction of a resolving set for the Johnson graph J(n, k), which has size (k + 1) n/(k + 1) . This is explained most easily in the case where k + 1 divides n, where one partitions the n-set into a collection of disjoint (k + 1)-sets, and in each part taking all k-subsets, to obtain a resolving set for J(n, k). Various refinements can be made to obtain slight improvements to the size, but the principle of the construction remains the same. (See [START_REF] Bailey | Resolving sets in Johnson and Kneser graphs[END_REF] for details.)

To obtain resolving sets for the Grassmann graphs, we will give separate constructions for two cases: the first, when n is divisible by k + 1, is considered in Proposition 9; the second, when n is not divisible by k + 1, is considered in Proposition 11. We could have combined the two separate cases into one construction, but in doing so risks losing the intuition of how the constructions arise.

Our constructions require some notions from finite geometry.

Definition 8 A t-spread of V (n, q) is collection of t-subspaces {W 1 , . . . , W m } with the following properties:

(i) any non-zero vector x ∈ V (n, q) belongs to exactly one W i ;

(ii

) if i = j, then W i ∩ W j = {0}.
A classical result (see Dembowski [7, p. 29]) shows that a t-spread of V (n, q) exists if and only if t is a divisor of n. The number of subspaces in a t-spread is necessarily (q n -1)/(q t -1).

Proposition 9 Suppose k + 1 divides n, and that S = {W 1 , . . . , W m } is a (k + 1)-spread of V (n, q). Let M denote the union of the collections of all k-subspaces of each W i ; that is,

M = m i=1 {U ≤ W i : dim(U ) = k}.
Then M is a resolving set for G q (n, k) of size n 1 q .

Proof: We will show that M is a resolving set by demonstrating that whenever A and B are two distinct k-subspaces of V (n, q), there exists some U ∈ M with dim(A ∩ U ) = dim(B ∩ U ).

We consider how A and B intersect with the members W 1 , . . . , W m of the (k + 1)-spread S.

Case 1. If either of A or B (say A) is contained within some member of S, then clearly A ∈ M, and we are done (as dim(A ∩ B) = k).

So we suppose not. For each i, let

A i = A ∩ W i and B i = B ∩ W i .
There are now two possible cases.

Case 2. Suppose there exists some i where dim

(B i ) < dim(A i ). Since dim(A i ) < k, there must exist some k-subspace U of W i which contains A i as a subspace. Therefore dim(A i ∩ U ) = dim(A i ), while dim(B i ∩ U ) ≤ dim(B i ) < dim(A i ).
In particular, we have dim

(A i ∩ U ) = dim(B i ∩ U ), and thus dim(A ∩ U ) = dim(B ∩ U ), where U ∈ M.
Case 3. The remaining scenario is that dim(A i ) = dim(B i ) for all i. However, there must exist some i where A i = B i (and where both are non-zero); otherwise we would have A = B. For that particular value of i, suppose dim

(A i ) = dim(B i ) = d < k. Now, for any k-subspace U of W i , we must have dim(A i ∩ U ) ≥ d -1 and dim(B i ∩ U ) ≥ d -1 (this follows from the identity dim(A i ∩ U ) = dim(A i ) + dim(U ) -dim(A i + U ), and that dim(A i + U ) ≤ dim(W i ) = k + 1; likewise for dim(B i ∩ U ))
. Thus, for there to be a k-subspace U with dim(A i ∩U ) = dim(B i ∩U ), we must have (without loss of generality) that A i is a subspace of U , and B i is not. We aim to construct such a U .

Take a basis {a 1 , . . . , a d } for A i . Since A i = B i , there exists a vector x ∈ B i \ A i . Now, because x ∈ A i , we have that the set {a 1 , . . . , a d , x} is linearly independent. Extend this to a basis {a 1 , . . . , a d , x, w 1 , . . . , w k-d } for W i . Now let U be the k-subspace spanned by the vectors {a 1 , . . . , a d , w 1 , . . . , w k-d }: by construction, A i is a subspace of U , but B i is not, since x ∈ B i \U .

In particular, we see that

d = dim(A i ∩ U ) = dim(B i ∩ U ) = d -1, and thus dim(A ∩ U ) = dim(B ∩ U ), where U ∈ M.
In all cases, we have U ∈ M with dim(A ∩ U ) = dim(B ∩ U ), so therefore M is a resolving set. Finally, we observe that

|M| = q n -1 q k+1 -1 k + 1 1 q = q n -1 q k+1 -1 q k+1 -1 q -1 = n 1 q . 2
We remark that Proposition 9 provides an alternative proof of Theorem 5 in the case where k +1 divides n. We also remark that Lemma 6 can be applied to show that the set M of Proposition 9 is a resolving set for G q (n, k): the incidence matrix of M is a block-diagonal matrix, where each block is the incidence matrix of the collection of all k-subspaces of V (k + 1, q). By Lemma 7, this has full rank, and thus so does the incidence matrix of M.

We would also like to obtain a construction of a resolving set when k + 1 does not divide n. In that situation, there is no (k + 1)-spread of V (n, q); however, a result of Beutelspacher [START_REF] Beutelspacher | Partitions of finite vector spaces: an application of the Frobenius number in geometry[END_REF] provides an alternative. Following his notation, where T is a set of positive integers, a T -partition of V (n, q) is a partition of the non-zero vectors of V (n, q) into subpaces whose dimensions form the set T . Thus if T = {t}, then a T -partition of V (n, q) is simply a t-spread of V (n, q). The following lemma is an immediate consequence of Lemma 3 in Beutelspacher's 1978 paper [START_REF] Beutelspacher | Partitions of finite vector spaces: an application of the Frobenius number in geometry[END_REF].

Lemma 10 (Beutelspacher [START_REF] Beutelspacher | Partitions of finite vector spaces: an application of the Frobenius number in geometry[END_REF]) Suppose n = r(k + 1) + t, where 0 < t < k + 1. Then there exists a {k + 1, t}-partition of V (n, q). Beutelspacher's construction works as follows: write s = r(k + 1) (so that n = s + t) and take a (k + 1)-spread of V (s, q). The remaining q n -q s vectors in V (n, q) \ V (s, q) are then partitioned into the non-zero vectors of t-subspaces (of which there are necessarily q s ). In what follows, we suppose that P is a {k + 1, t}-partition of V (n, q). We write this as P = S ∪ T , where S = {W 1 , . . . , W m } is a (k + 1)-spread of V (s, q), and where T = {X 1 , . . . , X } consists of t-subspaces covering the remaining vectors. We also let Z denote a fixed (k -t + 1)-dimensional subspace of V (s, q). Proposition 11 Suppose n = s + t, where (k + 1) divides s and 0 < t < k + 1. Let P = S ∪ T and Z be as above. For each W i ∈ S, take all the k-subspaces (as in Proposition 9); for each X j ∈ T , extend to the (k + 1)-subspace X j ⊕ Z, and take all k-subspaces of this. Let M denote the union of these collections: that is,

M = m i=1 {U ≤ W i : dim(U ) = k} ∪ j=1 {U ≤ X j ⊕ Z : dim(U ) = k}.
Then M is a resolving set for G q (n, k), of size at most (n-t)+(k+1) 1 q .

Proof: To show that M is a resolving set, we show that whenever A and B are two distinct k-subspaces of V (n, q), there exists some

U ∈ M with dim(A ∩ U ) = dim(B ∩ U ).
If A or B are entirely contained within V (s, q), then we are done; by the arguments used in the proof of Proposition 9, M contains a resolving set for the subgraph G q (s, k). Also, if A ∩ V (s, q) = B ∩ V (s, q), the proof of Proposition 9 shows that a vertex of the resolving set for G q (s, k) is able to distinguish A and B. Thus the only situation remaining is when both A and B intersect non-trivially with V (n, q) \ V (s, q), and where A ∩ V (s, q) = B ∩ V (s, q).

Since A = B but A ∩ V (s, q) = B ∩ V (s, q), it follows that there exists a t-subspace X i ∈ T where A ∩ X i = B ∩ X i . Suppose without loss of generality that dim(A ∩ X i ) ≤ dim(B ∩ X i ). Then there exists a vector

x ∈ (B ∩ X i ) \ A. It follows that x ∈ B ∩ (X i ⊕ Z) but x ∈ A ∩ (X i ⊕ Z); consequently, we have A ∩ (X i ⊕ Z) = B ∩ (X i ⊕ Z)
. By the arguments in Cases 2 and 3 of Proposition 9, it follows that there exists a k-subspace U ≤

X i ⊕ Z satisfying dim(A ∩ U ) = dim(B ∩ U ). By construction, U ∈ M.
Finally, we obtain the bound by observing that

|M| ≤ s 1 q + q s k + 1 1 q = q s -1 q -1 + q s q k+1 -1 q -1 = q s+k+1 -1 q -1 = (n -t) + (k + 1) 1 q . 2
We remark that the bound on the size of M given in Proposition 11 is likely to be an over-estimate, for two reasons. First, it is possible that for distinct X i , X j , we may have X i ⊕ Z = X j ⊕ Z; second, even if X i ⊕ Z = X j ⊕ Z, they may have a common k-subspace. The precise number of repetitions will be dependent on the choice of Z and the structure of the partition P = S ∪ T , and thus counting the actual size of M will be difficult in general. However, in the case t = 1, it is straightforward. First, if t = dim(X i ) = 1, we can count precisely the number of 1-subspaces in (X i ⊕ Z) \ Z to be q k ; second, if (X i ⊕ Z) = (X j ⊕ Z), the only k-subspace that can be contained in

(X i ⊕ Z) ∩ (X j ⊕ Z) is Z itself.
Since the choice of Z was arbitrary, we can take Z to be one of the k-subspaces of some W j . Hence, if t = 1, we have

|M| = n -1 1 q + q n-1 q k k + 1 1 q -1 = n 1 q + q n-k k -1 1 q .
4 Discussion

A natural question is to compare our result in Theorem 5 with the previously-known upper and lower bounds on metric dimension. An implicit, approximate lower bound can be obtained using [3, Proposition 3.6], which in the case of Grassmann graphs yields

µ(G q (n, k)) log k n k q .
This bound is clearly much smaller than the upper bound we obtained in Theorem 5. However, this lower bound is obtained only by considering the diameter of a graph and not its structure, and is often far from the actual value of µ. (See [3, §3.1] for a more detailed discussion.) As mentioned in the introduction, there are known upper bounds due to Babai [START_REF] Babai | On the order of uniprimitive permutation groups[END_REF] which can be applied here (see [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF] for an interpretation of these in terms of metric dimension of distance-regular graphs). For the Grassmann graphs, Babai's most general bound (see [START_REF] Babai | On the order of uniprimitive permutation groups[END_REF]Theorem 2.1]; see also [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF]Theorem 3.15]) yields

µ(G q (n, k)) < 4 n k q log n k q (2)
while his stronger bound (see [START_REF] Babai | On the order of uniprimitive permutation groups[END_REF]Theorem 2.4]; see also [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF]Theorem 3.22]) yields

µ(G q (n, k)) < 2k n k q n k q -M log n k q (3)
where

M = max 0≤j≤k q j 2 n -k j q k j q .
These bounds are difficult to evaluate exactly, so we conducted some experiments using MAPLE to compare these bounds with the one obtained in Theorem 5. Our experiments indicate that for k > 2, our constructive bound of n 1 q is an improvement on Babai's weaker bound. When k = 2 and q is large, Babai gives a better bound. They also suggest that Babai's stronger bound is, for fixed q and n, is descreasing in k (in comparison, our bound is independent of k and thus stays fixed), and gives a better bound for larger values of k. However, it should be mentioned that Babai's results are obtained using a result of Lovász on fractional covers in hypergraphs [START_REF] Lovász | On the ratio of optimal integral and fractional covers[END_REF], and are not explicit, whereas (in the case where k + 1 divides n), our bound is met by an explicit construction of a resolving set. Also, the proof of Theorem 5 implictly gives a method of constructing resolving sets, by sequentially adding k-subspaces so that the incidence matrix has full rank.

Another natual question concerns the Grassmann graphs being the q-analogue of the Johnson graphs, and comparing our result with known bounds for the metric dimension of those graphs. Often, when one has obtained an invariant of the Grassmann graph G q (n, k) as a function of q, then by taking the limit as q → 1, one obtains the same invariant for the Johnson graph J(n, k). Now, if we consider our bound from Theorem 5, it is easy to see that

lim q→1 n 1 q = n,
which is precisely the bound for the Johnson graphs in Theorem 3. Finally, we remark that it is likely that one can refine the constructions in Propositions 9 and 11 (in the manner of the results for Johnson graphs in [START_REF] Bailey | Resolving sets in Johnson and Kneser graphs[END_REF]) to obtain a tighter bound on the metric dimension. However, unlike the case of the Johnson graphs, we believe it is unlikely that such refinements will affect the order of magnitude of the bound too much, or that they would have such a tidy form.

Acknowledgements

The authors would like to thank J. Cáceres for first communicating the results of [6], and P. J. Cameron, J. Guo and K. Wang for pointing out errors in earlier versions of this paper.

Supported by an NSERC Discovery Grant.

1365-8050


Yidong Sun

Yanjie Xu

The largest singletons in weighted set partitions and its applications

Keywords: Set partition, Bell polynomial, Permutation, Derangement

Recently, Deutsch and Elizalde studied the largest fixed points of permutations. Motivated by their work, we consider the analogous problems in weighted set partitions. Let A n,k (t) denote the total weight of partitions on [n + 1] = {1, 2, . . . , n + 1} with the largest singleton {k + 1}. In this paper, explicit formulas for A n,k (t) and many combinatorial identities involving A n,k (t) are obtained by umbral operators and combinatorial methods. In particular, the permutation case leads to an identity related to tree enumerations, namely,

where D k is the number of permutations of [k] with no fixed points.

Introduction

A partition of a set [n] = {1, 2, . . . , n} is a collection π = {B 1 , B 2 , . . . , B r } of nonempty and mutually disjoint subsets of [n], called blocks, whose union is [n]. For a block B, we denote by |B| the size of the block B, that is the number of the elements in the block B. A block B will be called singleton if |B| = 1. If {k} is a singleton of a partition, we denote it by k for short. If |B| = j, we assign a weight t j for B. The weight w(π) of a partition π is defined to be the product of the weight of each block of π.

It is well known that the weight of partitions of [n] with r blocks is the partial Bell polynomial B n,r t 1 , t 2 , . . . [START_REF] Comtet | Advanced Combinatorics[END_REF] on the variables {t j } j≥1 , that is

B n,r t 1 , t 2 , . . . = κn(r) n! r 1 !r 2 ! • • • r n ! t 1 1! r1 t 2 2! r2 • • • t n n! rn ,
where the summation κ n (r) is over all the nonnegative integer solutions of r 1 + r 2 + • • • + r n = r and r 1 + 2r

Y(t; x) = n≥0 Y n t 1 , t 2 , . . . x n n! = exp j≥1 t j x j j! .
Let A n,k denote the set of partitions of [n + 1] with the largest singleton k + 1. Let A n,k (t) denote the total weight of partitions in A n,k . Clearly,

A n,0 (t) = t 1 Y n 0, t 2 , . . . and A n,n (t) = t 1 Y n t 1 , t 2 , . . . ,
where Y n 0, t 2 , . . . is the weight of partitions of [n] without singletons.

Recently, Deutsch and Elizalde [START_REF] Deutsch | The largest and the smallest fixed points of permutations[END_REF] studied the largest fixed points of permutations, which is the special case when t j = (j -1)! for j ≥ 1. Later, Sun and Wu [START_REF] Sun | The largest singletons of set partitions[END_REF] considered the largest singletons in set partitions, which is the special case when t j = 1 for j ≥ 1.

In this paper we will investigate the largest singletons in weighted set partitions generally. The next section is devoted to studying the properties of A n,k (t), involving its explicit formulas and many combinatorial identities for A n,k (t). In the third section, we consider the permutation case, i.e., the special case when t j = (j -1)! for j ≥ 1, and derive a surprising identity analogous to the Riordan identity related to tree enumerations.

The properties of A n,k (t)

According to the definition of A n,k (t), for any weighted partition π of [n + 1] with the largest singleton k + 1, if k is also a singleton, delete the singleton k + 1 and subtracting one from all the entries larger than k + 1, we obtain a partition of [n] with the largest singleton k. This contributes the weight t 1 A n-1,k-1 (t); if k is not a singleton, exchange k and k + 1, we obtain a partition of [n + 1] with the largest singleton k. This contributes the weight A n,k-1 (t). Consequently, we obtain a recurrence for n, k ≥ 1,

A n,k (t) = A n,k-1 (t) + t 1 A n-1,k-1 (t) (1)
with the initial conditions A n,0 (t) = t 1 Y n 0, t 2 , . . . for n ≥ 0.

Lemma 2.1 The bivariate exponential generating function for A n+k,k (t) is given by

A(t; x, y) = n,k≥0 A n+k,k (t) x n n! y k k! = t 1 e -xt1 Y(t; x + y). Proof: Define A k (t; x) = n≥0 A n+k,k (t)
x n n! .

Clearly, A 0 (t; x) = t 1 e -xt1 Y(t; x). From (1), one can derive that

A k (t; x) = t 1 A k-1 (t; x) + ∂ ∂x A k-1 (t; x), which produces A k (t; x) = (t 1 + ∂ ∂x )A k-1 (t; x) = (t 1 + ∂ ∂x ) k A 0 (t; x). Then A(t; x, y) = k≥0 A k (t; x) y k k! = k≥0 y k (t 1 + ∂ ∂x ) k k! A 0 (t; x) = e yt1+y ∂ ∂x t 1 e -xt1 Y(t; x) = t 1 e yt1 e y ∂ ∂x e -xt1 Y(t; x) = t 1 e yt1 e -(x+y)t1 Y(t; x + y) = t 1 e -xt1 Y(t; x + y).
This completes the proof. 2

Theorem 2.2 For any integers n, m ≥ 0 and any indeterminate λ, there hold

n k=0 k + λ -1 k A n+m,m+k (t) = n k=0 n + λ k n + λ -k -1 n -k A m+k,m (t)t n-k 1 , (2)
n k=0 k + λ -1 k A n+m,m+k (t) = n k=0 (-1) n-k n + λ k Y m+k (t)t n-k+1 1 . (3)
Proof: With the umbra Y t , given by Y n t = Y n (t), Y(t; x) may be written as Y(t; x) = e Ytx . (See, for example, [START_REF] Gessel | Applications of the classical umbral calculus[END_REF][START_REF] Roman | The Umbral Calculus[END_REF][START_REF] Roman | The umbral calculus[END_REF]). Then, by Lemma 2.1, we have A(t; x, y) = t 1 e Yt(x+y)-t1x = t 1 e (Yt-t1)x e Yty .

When comparing the coefficient of x n y k n!k! , A n+k,k (t) can be represented umbrally as

A n+k,k (t) = t 1 Y k t (Y t -t 1 ) n . (4)
Let [x n ]f (x) denote the coefficient of x n in the formal power series f (x). Then we get

n k=0 k + λ -1 k A n+m,m+k (t) = n k=0 (-1) k -λ k t 1 Y m+k t (Y t -t 1 ) n-k = t 1 Y m t (Y t -t 1 ) n n k=0 -λ k - Y t Y t -t 1 k = t 1 Y m t (Y t -t 1 ) n n k=0 [x k ] 1 - xY t Y t -t 1 -λ = t 1 Y m t (Y t -t 1 ) n [x n ] 1 1 -x 1 - xY t Y t -t 1 -λ = t 1 Y m t (Y t -t 1 ) n [x n ] 1 (1 -x) λ+1 1 - x (1 -x) t 1 (Y t -t 1 ) -λ = t 1 Y m t (Y t -t 1 ) n [x n ] n k=0 -λ n -k x n-k (1 -x) n+λ-k+1 - t 1 Y t -t 1 n-k = n k=0 (-1) k -(n + λ -k + 1) k -λ n -k t 1 Y m t (Y t -t 1 ) k (-t 1 ) n-k = n k=0 n + λ k n + λ -k -1 n -k A m+k,m (t)t n-k 1 ,
which proves [START_REF] Clarke | A combinatorial interpretation of the Seidel generation of q-derangement numbers[END_REF]. By the identity

n k k i = n i n -i k -i ,
and Vandermonde's convolution identity

n k=0 a k b n -k = a + b n ,
we have

n k=0 k + λ -1 k A n+m,m+k (t) = n k=0 n + λ k -λ n -k t 1 Y m t (Y t -t 1 ) k (-t 1 ) n-k = n k=0 n + λ k -λ n -k k i=0 k i t 1 Y m+i t (-t 1 ) n-i = n i=0 t 1 Y m+i t (-t 1 ) n-i n k=i n + λ k -λ n -k k i = n i=0 n + λ i t 1 Y m+i t (-t 1 ) n-i n k=i -λ n -k n + λ -i k -i = n i=0 n + λ i t 1 Y m+i t (-t 1 ) n-i = n k=0 (-1) n-k n + λ k Y m+k (t)t n-k+1 1 , which proves (3). 2
The case λ = 0 in (3) yields an explicit formula for A n+m,m (t).

Corollary 2.3 For any integers n, m ≥ 0, there holds

A n+m,m (t) = n k=0 (-1) n-k n k t n-k+1 1 Y m+k (t). (5)
Corollary 2.4 For any integers n, m ≥ 0, there hold

n k=0 A n+m,m+k (t) = t 1 Y n+m+1 (t) -A n+m+1,m (t) t 1 , (6)
n k=0 (k + 1)A n+m,m+k (t) = A n+m+2,m (t) -t 1 Y n+m+2 (t) + (n + 2)t 2 1 Y n+m+1 (t) t 2 1 , (7)
n k=0 (n -k + 1)A n+m,m+k (t) = t 1 Y n+m+2 (t) -A n+m+2,m (t) -(n + 2)t 1 A n+m+1,m (t) t 2 1 . (8)
Proof: By combining (5) with n replaced by n + 1 (resp. n + 2) and with the case λ = 1 (resp. λ = 2) in (3), we obtain (6) (resp. ( 7)). Moreover, (8) can be easily obtained from ( 6) and [START_REF] Gessel | Applications of the classical umbral calculus[END_REF]. 2

Theorem 2.5 For any integers n, m, k ≥ 0, there holds

A n+m+k,m+k (t) = m j=0 m j t m-j 1 A n+k+j,k (t). (9)
Proof: Here we provide a combinatorial proof. For any π ∈ A n+m+k,m+k , suppose that π has exactly m -j singletons in {k + 1, . . . , k + m}, which contributes the weight t m-j

1

, and there are m j ways to do this. The remaining j elements in {k + 1, . . . , k + m} can not be singletons in π. These j elements can be regarded as the roles that greater than m + k + 1, so the remaining n + k + j + 1 elements can be partitioned with the largest singleton m + k + 1, these cases contribute the weight A n+k+j,k (t). Thus the total weight of such partitions is m j t m-j 1 A n+k+j,k (t). Summing up all the possible cases yields (9). 2

Theorem 2.6 For any integers n, m ≥ 0 and any indeterminate y, there hold

n k=0 n k A n+m,m+k (t)y k = n k=0 (-1) n-k n k Y m+k (t)(y + 1) k t n-k+1 1 , (10)
n k=0 n k A m+k,m (t)y n-k = t 1 n k=0 n k Y m+k (t)(y -t 1 ) n-k . ( 11
)
Proof: By (4), we have

n k=0 n k A n+m,m+k (t)y k = n k=0 n k t 1 Y m+k t (Y t -t 1 ) n-k y k = t 1 Y m t ((y + 1)Y t -t 1 ) n = n k=0 (-1) n-k n k (y + 1) k Y m+k t t n-k+1 1 = n k=0 (-1) n-k n k (y + 1) k Y m+k (t)t n-k+1 1 ,
which proves [START_REF] Riordan | Enumeration of linear graphs for mappings of finite sets[END_REF]. Similarly, (11) can be obtained, but here we provide a combinatorial proof. Let X n,m = n j=0 X n,m,k and X n,m,k denote the set of pairs (π, S) such that

• S is an (n -k)-subset of [m + 2, n + m + 1] = {m + 2, . . . , n + m + 1}
, and each element of S is colored by t 1 or y -t 1 ;

• π is a partition of the set [n + m + 1] -S with the largest singleton m + 1, and each element of

[n + m + 1] -S is only colored by 1. Let Y n,m = n k=0 Y n,m,k and Y n,m,k denote the set of pairs (π, S) such that • S is an (n -k)-subset of [m + 2, n + m + 1]
and each element of S is only colored by y -t 1 ;

• π is a partition of the set [n + m + 1] -S such that m + 1 must be a singleton, and each element of

[n + m + 1] -S is only colored by 1.
The weight of (π, S) is defined to be the product of the weight of π and the color of each element of

[n + m + 1].
Clearly, the weights of X n,m and Y n,m are counted respectively by the left and right sides of [START_REF] Riordan | Forests of labeled trees[END_REF]. Given any pair (π, S) ∈ X n,m , S can be partitioned into two parts S 1 and S 2 such that each element of S 1 is colored by y -t 1 and each element of S 2 is colored by t 1 . Regard each element of S 2 as a singleton which is weighted by t 1 and colored by 1, together with π, we obtain a partition π 1 of [n + m + 1] -S 1 such that m + 1 is always a singleton. Then the pair (π 1 , S 1 ) lies in Y n,m .

Conversely, for any pair (π 1 , S 1 ) ∈ Y n,m , let S denote the union of S 1 and the singletons of π 1 greater than m + 1, then π 1 can be partitioned into two parts π and π such that π is a partition of [n + m + 1] -S with the largest singleton m + 1 and π is the singletons of π 1 greater than m + 1. By regarding π as a subset of [m + 2, n + m + 1] in which each element is colored by t 1 , together with S 1 . Then we obtain an

(n -k)-subset of [m + 2, n + m + 1]
for some k such that each element of S is colored by t 1 or y -t 1 . Then the pair (π, S) lies in X n,m .

Clearly we find a bijection between X n,m and Y n,m , which proves [START_REF] Riordan | Forests of labeled trees[END_REF]. 2

The cases y = -1 in (10) and y = t 1 in (11) lead to Assume that S 1 = {i 1 , i 2 , . . . , i k } for some 0 ≤ k ≤ n in increasing order. If S 1 is the empty set ∅, which implies that S = ∅ and all elements of [n + m + 1] are colored by 1, it is obvious that (π, ∅) ∈ Y * n,m . Then define ϕ(π, ∅) = (π, ∅). If S 1 is not the empty set, exchanging m + 1 and i k in π, we obtain a partition π 1 , it is easily to verify that (π 1 , S 1 ) ∈ Y * n,m and has the same weight as (π, S). Then define ϕ(π, S) = (π 1 , S 1 ).

Conversely, for any

(π 1 , S 1 ) ∈ Y * n,m , if S 1 = ∅, so π 1 has the largest singleton m + 1, then (π 1 , ∅) ∈ X * n,m and define ϕ -1 (π 1 , ∅) = (π 1 , ∅). If S 1 = ∅, assume that S 1 = {i 1 , i 2 , .
. . , i k } for some 1 ≤ k ≤ n in increasing order, let S denote the set of all the elements in S 1 such that each forms a singleton of π 1 . Now exchanging m + 1 and i k in π 1 , we obtain a partition π, it is easy verifiable that (π, S) ∈ X * n,m which has the same weight as (π 1 , S 1 ). Then define ϕ -1 (π 1 , S 1 ) = (π, S).

Clearly, ϕ is indeed a bijection between X * n,m and Y * n,m , which proves [START_REF] Roman | The Umbral Calculus[END_REF]. 2

3 The special case for permutations

When the parameter t in A n,k (t) takes some special value, that is to assign a special structure to each block of partitions of [n + 1]. For example, the case t = (1 0 , 2 1 , 3 2 , . . .) indicates that each block of partitions is assigned by a (rooted and labeled) tree structure, such partitions are equivalent to labeled forests; The case t = (1, 1, 0, . . .) leads to involutions on [n + 1].

In this section, we just present an interesting specialization, but leave others to inclined readers. Consider the special case when t = (0!, 1!, 2!, . . .), that is to assign a cycle structure to each block of partitions, such partitions is equivalent to permutations. Let P n,k = A n,k (t) with t = (0!, 1!, 2!, . . .), i.e., P n,k is the number of permutations of [n + 1] with the largest fixed point k + 1. From ( 5) and ( 9), one has the explicit formulas for P n,k In fact {P n,k } n≥k≥0 forms the difference table introduced by Euler, which has been investigated in depth in derangement theory [START_REF] Clarke | A combinatorial interpretation of the Seidel generation of q-derangement numbers[END_REF][START_REF] Dumont | Matrices d'Euler-Seidel[END_REF][START_REF] Dumont | Dérangements et nombres de Genocchi[END_REF][START_REF] Rakotondrajao | k-Fixed-points permutations[END_REF][START_REF] Rakotondrajao | On Euler's difference table[END_REF]. Chen [START_REF] Chen | The skew, relative, and classical derangements[END_REF] gave two other interpretations for P n,k using krelative derangements on [n] and skew derangements from [n] to {-k + 1, . . . , -1, 0, 1, . . . , n -k} for 0 ≤ k ≤ n. Moreover, Chen established a bijection between these two settings. Recently, Deutsch and Elizalde [START_REF] Deutsch | The largest and the smallest fixed points of permutations[END_REF] gave a new interpretation of derangement number D n+2 as the sum of the values of the largest fixed points of all non-derangements of length n + 1, namely, n k=0 (k + 1)P n,k = D n+2 , which is the special case of (7) when t = (0!, 1!, 2!, . . .) and m = 0.

P n+k,k = n j=0 (-1) n-j n j (k + j)! = k j=0 k j D n+j . Clearly, P n,n = n! = Y n (0!,
Next, we can explore some new relations between P n,k and other classical sequences such as Bell numbers or Fibonacci numbers. Extracting the coefficient of x n n! in P (x, x 2 ), we have

It should be noted that ( 13) and ( 14) have close relations to the (re-normalized) Charlier polynomials C n (u, v) [START_REF] Gessel | Applications of the classical umbral calculus[END_REF] defined by

C n (u, v) = n k=0 n k (u) k v n-k ,
where (u) k = u(u + 1) • • • (u + k -1) for k ≥ 1 and (u) 0 = 1. In fact ( 13) is (y+1) n m! C n (m + 1, -1 y+1 ) and ( 14) is equal to 1 m! C n (m + 1, y -1).

Example 3 . 1

 31 By Lemma 2.1, one can derive the bivariate exponential generating function for P n+k,k , i.e., P (x, y) = n,k≥0P n+k,k x n n! y k k! = e -x 1 -x -y .

  k , where F k is the k-th Fibonacci number defined by 1 1-x-x 2 = k≥0 F k x k . Example 3.2 When t = (0!, 1!, 2!, . . .), (10) and (11) reduce to n k=0 n k P n+m,m+k y k = n k=0 (-1) n-k n k (m + k)!(y + 1) k , k)!(y -1) n-k .

  2 + • • • + nr n = n. The total weight for partitions of [n] is the complete Bell polynomial Y n (t) = Y n t 1 , t 2 , . . . =

	n
	B n,r t 1 , t 2 , . . . ,
	r=0
	which has the exponential generating function

Table 1 .

 1 The values of P n,k for n and k up to 6.

	n/k	0	1	2	3	4	5	6
	0	1
	1	0	1
	2	1	1	2
	3	2	3	4	6
	4	9	11 14 18 24
	5	44 53 64 78 96 120
	6	265 309 362 426 504 600 720

1!, 2!, . . .) and P n,0 = D n = Y n (0, 1!, 2!, . . .), where D n is the derangement number of [n], i.e., the number of permutations of [n] without fixed points. See Table

1

for some small values of P n,k .

Acknowledgements

The authors are grateful to the anonymous referees for the helpful suggestions and comments.

This work is supported by The National Science Foundation of China (Grant No. 10801020), by the Fundamental Research Funds for the Central Universities (Grant No. 2011QN056), and by The National Science Foundation of Liaoning Province (Grant No. 201102015). 1365-8050

Corollary 2.7 For any integers n, m ≥ 0, there hold

The case y = yt1 y+1 in [START_REF] Riordan | Forests of labeled trees[END_REF], together with [START_REF] Riordan | Enumeration of linear graphs for mappings of finite sets[END_REF] generates the following result which has a combinatorial interpretation.

Corollary 2.8 For any integers n, m ≥ 0, there holds

Proof: • π is a partition of the set [n + m + 1] such that i k must be the largest singleton if S is not empty and m + 1 must be the largest singleton if S is empty;

• each element of [m + 2, n + m + 1] -S must not be a singleton.

The weight of (π, S) is defined to be the product of the weight of π and the colors of all elements in Recall that, by (4), P n,k can be represented umbrally as

where P = Y t with t = (0!, 1!, 2!, . . .). In particular, D n = (P -1) n and n! = P n . Hence, the case y = P -1 in ( 13) and the case y = P in [START_REF] Rota | The number of partitions of a set[END_REF] generate

With the Bell umbra B [START_REF] Gessel | Applications of the classical umbral calculus[END_REF][START_REF] Roman | The Umbral Calculus[END_REF][START_REF] Roman | The umbral calculus[END_REF], given by B = Y t with t = (1, 1, 1, . . .), the Bell number can be written as B n = B n and B n+1 = (B + 1) n . Then the case y = B in ( 13) and the case y = B + 1 in ( 14) generate

Using the Riordan identity [3, 11, P173],

the case in [START_REF] Roman | The umbral calculus[END_REF] with m = 1 and y = -n+2 n+1 and the case in [START_REF] Rota | The number of partitions of a set[END_REF] with m = 1 and y = n + 2 generate respectively

where we use the relation P k+1,1 = D k + D k+1 . By the well-known recurrence D k+2 = (k + 1)(D k + D k+1 ) for derangement numbers D k , together with D 1 = 0, after routine computation, ( 15) is equivalent to

which was also obtained by Riordan [START_REF] Riordan | Enumeration of linear graphs for mappings of finite sets[END_REF]. In a forthcoming paper [START_REF] Sun | λ-factorials of n[END_REF], using functional digraph theory, we will give a combinatorial interpretation for a more general identity involving the Riordan identity and (16) as special cases.


Gábor Horváth
email: ghorvath@science.unideb.hu

Csaba Szabó

The extended equivalence and equation solvability problems for groups

Keywords: complexity, extended equation solvability, extended equivalence, groups

We prove that the extended equivalence problem is solvable in polynomial time for finite nilpotent groups, and coNPcomplete, otherwise. We prove that the extended equation solvability problem is solvable in polynomial time for finite nilpotent groups, and NP-complete, otherwise.

Introduction

The algorithmic aspects of the equivalence problem and the equation solvability problem have received increasing attention in the past two decades. The equivalence problem for a finite algebra A asks whether or not two (term or polynomial) expressions s and t are equivalent over A (denoted by A |= s ≈ t), i.e. if s and t determine the same function over A. The equation solvability is one of the oldest problems of algebra: it asks whether or not two (term or polynomial) expressions s, t can attain the same value for some substitution over a finite algebra A, i.e. if the equation s = t can be solved. The complexity of the equivalence and equation solvability problems have been thoroughly investigated for finite classical algebras, e.g. for finite rings [START_REF] Burris | The equivalence problem for finite rings[END_REF]; [START_REF] Hunt | The complexity for equivalence for commutative rings[END_REF]; [START_REF] Lawrence | The complexity of solving polynomial equations over finite rings[END_REF]; [START_REF] Cs | The equivalence problem over finite rings[END_REF], for finite groups [START_REF] Burris | Results on the equivalence problem for finite groups[END_REF]; [START_REF] Goldmann | The complexity of solving equations over finite groups[END_REF]; [START_REF] Horváth | The complexity of the equivalence and equation solvability problems over nilpotent rings and groups[END_REF]; [START_REF] Horváth | The complexity of the equivalence problem for nonsolvable groups[END_REF]; [START_REF] Horváth | The complexity of checking identities over finite groups[END_REF], or for finite semigroups and monoids [START_REF] Almeida | Complexity of the identity checking problem for finite semigroups[END_REF]; [START_REF] Kisielewicz | Complexity of semigroup identity checking[END_REF]; [START_REF] Klíma | Unification Modulo Associativity and Idempotency[END_REF][START_REF] Klíma | Complexity issues of checking identities in finite monoids[END_REF]; [START_REF] Plescheva | Checking identities in 0-simple semigroups (in Russian)[END_REF]; [START_REF] Seif | Computational complexity of checking identites in 0-simple semigroups and matrix semigroups over finite fields[END_REF]. The complexity of these questions is determined with respect to the length of the input term or polynomial expressions.

In many situations a term or polynomial can be expressed in a more concise way using new operations, not only the basic operations of the algebra. For example, the length of [[[x 1 , x 2 ] , x 3 ] , . . . , x n ] is n if expressed by using the commutator, and is O (2 n ) if expressed by using the group multiplication. Such a change in the length suggests that the complexity of the equivalence or of the equation solvability problems may change as well. It is indeed the case in some situation: in [START_REF] Horváth | Equivalence and equation solvability problems for the group A 4[END_REF] it is shown that for the alternating group on four elements these problems have complexity in P; but if the group is extended by the commutator as an extra operation, then the equivalence problem is coNP-complete and the equation solvability problem is NP-complete. Such a complexity change cannot occur for two element algebras [START_REF] Gorazd | The complexity of problems connected with two-element algebras[END_REF]. To further investigate whether or not additional operations can affect the complexity of the equivalence and equation solvability problems, we introduce their extended version for finite groups.

Definition 1 Let G = (G, •) be a finite group. We say that the extended equivalence (equation solvability) problem over G is in P, if for arbitrary terms f 1 , . . . , f k the equivalence (equation solvability) problem over (G, •, f 1 , . . . , f k ) is in P. We say that the extended equivalence problem over G is coNP-complete (the equation solvability problem is NP-complete), if there exist terms f 1 , . . . , f k such that the equivalence problem over (G,

•, f 1 , . . . , f k ) is coNP-complete (the equation solvability problem over (G, •, f 1 , . . . , f k ) is NP-complete).
It is clear that the complexity of an extended problem is at least as hard as the original problem. Definition 1 can be extended to arbitrary algebras, e.g. for rings. Considering finite rings and applying the methods described in [START_REF] Burris | The equivalence problem for finite rings[END_REF]; [START_REF] Horváth | The complexity of the equivalence and equation solvability problems over nilpotent rings and groups[END_REF]; [START_REF] Hunt | The complexity for equivalence for commutative rings[END_REF] one can arrive at a similar dichotomy theorem for the extended problems as for the one about the original problems.

Theorem 2 Let R be a finite ring. If R is nilpotent, then the extended equivalence and extended equation solvability problems can be solved in polynomial time. If R is non-nilpotent, then the extended equivalence problem is coNP-complete, and the extended equation solvability problem is NP-complete.

The main results of this paper are two similar theorems for groups.

Theorem 3 Let G = (G, •) be a finite group. If G is nilpotent, then the equivalence problem over G can be solved in polynomial time. If G is non-nilpotent, then there exists a term f over G such that the equivalence problem over (G, •, f ) is coNP-complete.

Theorem 4 Let G = (G, •) be a finite group. If G is nilpotent, then the equation solvability problem over G can be solved in polynomial time. If G is non-nilpotent, then there exists a term f over G such that the equation solvability problem over (G, •, f ) is NP-complete.

For non-nilpotent, solvable groups we prove Theorems 3 and 4 by induction. The initial case of the induction is considered in Section 2, then we prove Theorems 3 and 4 in general in Section 3. We finish the paper by mentioning some open problems in Section 4.

Abelian normal subgroup

Let G = (G, •) be a finite, solvable, non-nilpotent group. Let us consider the lower central series of

G: γ 0 (G) = G, γ i (G) = [G, γ i-1 (G)].
Let us denote by γ (G) the normal subgroup in which this decreasing sequence terminates, and let T be the smallest positive integer such that γ T (G) = γ (G). We prove the solvable, non-nilpotent group case of Theorems 3 and 4 by induction on the order of the group. The initial case is where both γ (G) and G/C G γ (G) are commutative.

Theorem 5 Let G = (G, •) be a finite, solvable, non-nilpotent group. Assume that the groups γ (G) and G/C G γ (G) are commutative. Then there exists a term f such that the equivalence problem over (G, •, f ) is coNP-complete, and the equation solvability problem over (G, •, f ) is NP-complete.

Proof: We prove that there exists a term f such that the equivalence problem over

(G, •, f ) is coNP- complete. Let A = γ (G) and B = G/C G γ (G) . Let End A denote the endomorphism ring of A.
The group G acts on A by conjugation. This action of G is isomorphic to B. We identify B with its image in End A. Let ϕ : G → B denote the natural homomorphism from G onto B. Let R be the ring generated by B in End A, i.e. R = B End A . Since B is commutative, R is commutative as well. Moreover 1 ∈ B implies 1 ∈ R. Note that A is a faithful left-module over End A, and therefore it is a faithful module over the commutative ring R.

Denote the action of the ring element r ∈ R on a ∈ A by a r . For example, if

a ∈ A, g ∈ G, b = ϕ (g), then a 1 = a, a b = a ϕ(g) = g -1 ag, and a b-1 = a ϕ(g)-1 = a -1+ϕ(g) = a -1 g -1 ag = [a, g].

Let us denote the set of commutator actions in End

A by C: C = { b -1 | b ∈ B }. Let R c ≤ End A
be the subring of R generated by the commutator actions:

R c = C R = b -1 | b ∈ B R = ϕ (g) -1 | g ∈ G R . Note, that A is a faithful R c -module, as well. Note that |B| = |C|. Let c = |C|, and let d = |R c |. Let J c denote the Jacobson radical of R c .
We prove the theorem in the following steps.

1. We prove in Lemma 6 that there exists a polynomial p with integer coefficients such that R c = p (ϕ (G)).

2. We prove in Lemma 7 that the ring

R c is non-nilpotent, that is R c /J c is a direct sum of finite fields F 1 , . . . , F l . Assume that |F 1 | ≥ • • • ≥ |F l |.
3. Let q 1 denote the number of elements of F 1 . We prove in Lemma 8 that q 1 ≥ 3.

4. We introduce the term f using the polynomial p from Step 1. We polynomially reduce the GRAPH q 1 -coloring problem to the equivalence problem over (G, •, f ). The instance of the GRAPH q 1coloring problem is a graph Γ, and it asks whether or not the vertices of Γ can be colored by q 1 colors such that no two adjacent vertices share the same color. This problem is well-known to be NP-complete [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. For an arbitrary graph Γ we construct a term expression

t Γ over (G, •, f ) such that (G, •, f ) |= t Γ ≈ 1 if and only if the graph Γ is not q 1 -colorable.
The length of t Γ will be linear in the size of Γ.

In step 1 we prove that R c is a verbal subring of R.

Lemma 6 There exists a polynomial p with integer coefficients such that R c = p (B) = p (ϕ (G)).

Proof:

Let C = { u 1 , . . . , u c } and R c = { r 1 , . . . , r d }.
As R c = C R , for every r i ∈ R c there exist a polynomial p i with integer coefficients such that p i has no constant coefficient and r i = p i (u 1 , . . . , u c ).

For every r i ∈ R c let us fix such a polynomial p i . Let

p (x 1,1 , . . . , x d,c ) = d i=1 p i (x i,1 -1, x i,2 -1, . . . , x i,c -1) . Clearly, p (B) ⊆ R c . Let b j = u j + 1 for 1 ≤ j ≤ c. Then B = { b 1 , . . . , b c }. Let us fix 1 ≤ i ≤ d and consider the substitution x i,j = b j , x l,j = 1 (l = i).
For this substitution the value of p is

p i (u 1 , . . . , u c ) = r i . Hence r i ∈ p (B) yielding R c = p (B) = p (ϕ (G)). P
We continue with step 2 of the proof.

Lemma 7

The ring R c is non-nilpotent.

Proof: Let F (G) denote the Fitting subgroup of G, the unique largest nilpotent normal subgroup of G [START_REF] Robinson | A course in the theory of groups[END_REF]. As G is non-nilpotent, F (G) = G, and F (G) is the set of left-Engel elements [START_REF] Baer | Engelsche elemente noetherscher gruppen[END_REF]. An element g ∈ G is a left-Engel element, if for every h ∈ G there exists a positive integer k h , such that the k h -iterated commutator of h by g is the identity element:

[[[h, g], g] . . . g] = 1. Let g ∈ G
be arbitrary, and let r = ϕ (g) -1. We prove that g is a left-Engel element if and only if r is nilpotent. Assume that g is a left-Engel element. Now, for every h ∈ G there exists a positive integer k h , such that the k h -iterated commutator of h by g is the identity element:

[[[h, g], g] . . . g] = 1. Let k be the maximum of these numbers: k = max { k h | h ∈ G }. Recall that as γ (G) ¡ G and γ (G) is abelian, we have γ (G) ⊆ F (G). Then for every a ∈ A we have [[[a, g], g] . . . g] = 1
. By [a, g] = a ϕ(g)-1 = a r we obtain a r k = 1, yielding r k = 0, i.e. r is nilpotent. Now, assume that r is nilpotent. Let k be the smallest positive integer such that r k = 0. That is, for every a ∈ A we have a r k = 1. From a r = [a, g], we obtain that the k-iterated commutator of a by g is the identity of (Jacobson, 1945, Theorem 27). In step 3 we prove that at least one of these fields contains more than two elements.

G: [[[a, g], g] . . . g] = 1. Let T be the positive integer for which A = γ T (G). Let h ∈ G be arbitrary, then the T -iterated commutator of h by g is an element of A: [[[h, g], g] . . . g] ∈ A. Thus the (T + k)-iterated commutator of h by g is the identity element of G: [[[h, g], g] . . . g] = 1 Therefore g is a left-Engel element. P Let J c denote the Jacobson radical of R c . Now, R c /J c is a direct sum of finite fields
Lemma 8 For the ring R c we have R c /J c = Z l 2 .

Proof: We prove the lemma indirectly: assume that R c /J c = Z l 2 for some positive integer l. Now, r 2 + r ∈ J c for every r ∈ R c . Let t be the smallest positive integer for which r t is idempotent for every r ∈ R c and the exponent of G divides t. Thus R c /J c = Z l 2 implies r 2 + r t = 0 for every r ∈ R c .

Let b = ϕ (g) for some g ∈ G \ F (G). In the proof of Lemma 7 it is shown that commuting with g is a non-nilpotent action, that is

(b -1) is non-nilpotent. Let r = (b -1), then r ∈ R c . Let us calculate the value of r 2 + r t in the ring R. Since R is a commutative unital ring, r 2 + r t = r t • (r + 1) t = r t • b t .
The exponent of G divides t, hence b t = ϕ (g) t = ϕ (g t ) = ϕ (1) = 1. Thus r 2 + r t = 0 yields r t = 0, contradicting that r is a non-nilpotent element. P

We continue with step 4 of the proof. Let F 1 , . . . , F l be the fields occurring as a direct summand in

R c /J c (with multiplicity), i.e. R c /J c = ⊕ l i=1 F i . Assume that |F 1 | ≥ • • • ≥ |F l |, and let q 1 = |F 1 |.
By Lemma 8 we have q 1 ≥ 3. By Lemma 6 we can define the term f . Let p be the polynomial in Lemma 6. The polynomial p depends on dc variables, where c = |C|, d = |R c |. Let x1 and x2 be disjoint vectors of dc variables, that is the set of variables of x1 is disjoint from the set of variables of x2 . Let f be defined in the following way:

f (y, x1 , x2 ) = y (p(x1)-p(x2)) , (1)
Now, f is a term over G and it depends on 2dc + 1 variables. We shall polynomially reduce the GRAPH q 1 -coloring to the equivalence problem over (G, •, f ). By Lemma 8 we have q 1 ≥ 3, thus the GRAPH q 1 -coloring is NP-complete [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Let Γ = (V, E) be an arbitrary simple graph with no loops. Let V = { v 1 , . . . , v n } be its set of vertices and let E = { e 1 , . . . , e m } be the set of its edges. Let t be the smallest positive integer such that for every r ∈ R c the element r t is idempotent. In particular, if r ∈ J c then r t = 0. Let

u Γ (z 1 , . . . , z n ) = vivj ∈E (z i -z j ) t . (2)
We would like to express y uΓ(z1,...,zn) using f defined by (1), where each z i runs through R c and y runs through A. We achieve this in two steps. We construct W (y, x1 , . . . , xn ) = y uΓ(p(x1),...,p(xn)) = y v i v j ∈E (p(xi)-p(xj )) t for disjoint x1 , . . . , xn vectors of dc variables, ensuring that the arguments of u Γ will be in R c . Then we guarantee that the value of y will be in A.

Let x denote the vector of all 'x' variables, i.e. x = (x 1 , . . . , xn ). Now, we want to express W (y, x). Although, W is a term over G, its length would be exponential in the size of Γ using only the group multiplication. We shall express W using f , and thus the length of W will be linear in the size of Γ. For every edge e = v i v j let w e (y, x) be the t-times iterated version of f (y, xi , xj ):

w e (y, x) = f • f • • • • • f (y, xi , xj ) = y (p(xi)-p(xj )) t .
Let W (y, x) denote the composition of the terms w e :

W (y, x) = w e1 • w e2 • • • • • w em (y, x) = y uΓ(p(x1),...,p(xn)) .
As A is a verbal normal subgroup of G, there exists a term s (ȳ) of variables ȳ = (y 1 , . . . , y k ) such that s (G) = A. Finally, let t Γ (ȳ, x) = W (s (ȳ) , x) .

(3)

The length of t Γ is linear in the size of Γ: for every edge e ∈ E we have

w e ≤ 2tcd + 1 = O (1). Moreover, W ≤ w e1 + • • • + w em + 1 = O (m). Finally, t Γ ≤ W • s = O (m)
, as s depends only on G and not on Γ.

We prove that Γ is not colorable by q 1 colors if and only if (G, •, f ) |= t Γ ≈ 1. Assume that Γ is q 1 -colorable. Color the vertices of Γ by the elements of F 1 . Thus there exist elements r 1 , . . . , r n ∈ R c such that the color of v i is the r n ) is 1, and u Γ (r 1 , . . . , r n ) = 0. Therefore there exists an element a ∈ A such that a uΓ(r1,...,rn) = 1. For every

F 1 -component of r i . That is, if ψ : R c → F 1 is the natural homomor- phism, then ψ (r i ) is the color of v i . Now, for every edge v i v j the F 1 -component of (r i -r j ) is not 0. Hence (r i -r j ) t = 1 in F 1 for every edge v i v j . That is, the F 1 -component of u Γ (r 1 , . . . ,
1 ≤ i ≤ n let ḡi ∈ G dc such that r i = p (ḡ i ) and let ḡ = (ḡ 1 , . . . , ḡn ). Let h ∈ G k such that a = s h . Now,
t Γ h, ḡ = s h uΓ(p(ḡ1),...,p(ḡn)) = a uΓ(r1,...,rn) = 1.

Assume now, that Γ is not q 1 -colorable. Consider an arbitrary substitution of t Γ . Let h ∈ G k be arbitrary and for every 1 ≤ i ≤ n let ḡi ∈ G dc be arbitrary. Let ḡ = (ḡ 1 , . . . , ḡn ). Let a = s h and let On the other hand, if t ≈ 1 over (G, •, f ), then there exists an evaluation ȳ1 , . . . , ȳk such that t = 1. Now, for the elements

h i = s(ȳ i ) we have t(h 1 , . . . , h n ) = 1, hence t ≈ 1 over (V, •, f ). Thus t ≈ 1 over (V, •, f ) if and only if t ≈ 1 over (G, •, f ).
The reduction is polynomial in the length of t because the length of t is the product of the length of t and the length of s, and s depends only on the group G. P

Note that the converses of the statements of Lemma 9 are not true. With G = A 4 (the alternating group on 4 elements), V = G and f being the commutator we have that the equivalence problem for (G, •, f ) is coNP-complete and is in P for (V, •, f ), and similarly, equation solvability for (G, •, f ) is NP-complete and is in P for (V, •, f ).

By the following lemma the equivalence problem can be reduced to the factor by the centralizer of a verbal subgroup, while the equation solvability problem can be reduced to the factor by a verbal subgroup.

Lemma 10 Let V be a verbal subgroup of G = (G, •). Let H 1 = (H 1 , •) = G/C G (V) and let H 2 = (H 2 , •) = G/V. Let f be a group term. 1. If the equivalence problem over (H 1 , •, f ) is coNP-complete, then the equivalence problem over (G, •, f ) is coNP-complete. 2. If the equation solvability problem over (H 2 , •, f ) is NP-complete, then the equation solvability problem over (G, •, f ) is NP-complete.
Proof: We prove (1). We give a polynomial reduction from the equivalence problem of

(H 1 , •, f ) to the equivalence problem of (G, •, f ). For every term t(x 1 , . . . , x n ) over (H 1 , •, f ) we present a term t over (G, •, f ) such that t ≈ 1 over (H 1 , •, f ) if and only if t ≈ 1 over (G, •, f ).
As V is verbal, there exists a term s(x 1 , . . . , x k ) over G such that s(G) = V. Let ȳ = (y 1 , . . . , y k ). Let t (x 1 , . . . , x n ) be a term over (H 1 , •, f ) and let x = (x 1 , . . . , x n ). Let the exponent of G be N . Consider the following term over (G, •, f ):

t (x, ȳ) = t (x) N -1 s (ȳ) N -1 t (x) s (ȳ) = [t (x) , s (ȳ)] . Assume first that (H 1 , •, f ) |= t ≈ 1. Then for every ḡ ∈ G n we have t (ḡ) ∈ C G (V). For arbitrary h ∈ G k we have s h ∈ V. Thus t (ḡ) , s h = 1, that is (G, •, f ) |= t ≈ 1. Assume now that (G, •, f ) |= t ≈ 1. If ȳ runs through G k , then s (ȳ) runs through V. Then for every ḡ ∈ G n we have t (ḡ) ∈ C G (V), i.e. (H 1 , •, f ) |= t ≈ 1. Thus t ≈ 1 over (H 1 , •, f ) if and only if t ≈ 1 over (G, •, f ).
The reduction is polynomial in the length of t because t ≤ N ( t + s ).

The proof of (2) is the same, except that instead of t one should consider the following term:

t (x, ȳ) = t (x) s (ȳ) N -1 .
P Now, we prove Theorems 3 and 4. If G is not solvable, then the equivalence problem over (G, •) is coNP-complete [START_REF] Horváth | The complexity of the equivalence problem for nonsolvable groups[END_REF], and the equation solvability problem over (G, •) is NP-complete [START_REF] Goldmann | The complexity of solving equations over finite groups[END_REF]. Thus for an arbitrary term f the equivalence problem over (G, •, f ) is coNP-complete, and the equation solvability problem over (G, •, f ) is NP-complete.

If G is nilpotent, then by Lemma 5 in [START_REF] Horváth | The complexity of the equivalence and equation solvability problems over nilpotent rings and groups[END_REF] there exists a positive integer d (depending only on G) such that for an arbitrary polynomial t (x 1 , . . . , x n ) we have

t (G, . . . , G) = { t (h 1 , . . . , h n ) | (h 1 , . . . , h n ) ∈ T d } ,
where

T d = { (h 1 , . . . , h n ) | |{ h i : h i = 1 }| ≤ d } .
That is we can obtain t (G, . . . , G) by substituting only from T d . Now,

|T d | ≤ d j=0 n j • |G| j ≤ d j=0 (n • |G|) j ≤ (d + 1) • (n |G|) d = O t d .
Hence Case 2: G is nilpotent, and G = 1. Since G is non-nilpotent and G is nilpotent, we see from (Robinson, 1995, 5.

(G , •, f ) is coNP-complete. By (1) of Lemma 9 the equivalence problem over (G, •, f ) is coNP-complete. Case 2: G is nilpotent, but G/C G (G ) is non-nilpotent. Let H = G/C G (G ). As G is nilpotent 1 = Z(G ) ≤ C G (G ), hence |H| < |G|. Since H = (H, •) is non-nilpotent,
≤ C G (G ). Moreover, A ≤ G implies A ≤ C G (G ) ∩ G = C G (G ) = Z(G ), i.e. A is commutative. From A ≤ C G (G ) we have C G (A) ≥ C G (C G (G )) ≥ G . Therefore G/C G (A) ≤ G/G ,

Open questions

The term f in Theorems 3 and 4 varies from group to group. As it is mentioned in the Introduction, the commutator can significantly change the length of expressions. It is proved in [START_REF] Horváth | Equivalence and equation solvability problems for the group A 4[END_REF] that the complexities of the equivalence and equation solvability problems change if we extend the alternating group A 4 by the commutator. One may wonder if f can be chosen as the commutator for every finite group.

Problem 1 For every finite group G = (G, •), determine the complexity of the equivalence and equation solvability problems for (G, •, [, ]).

The smallest group for which it would be interesting to know how the commutator affects the complexity of the equivalence and equation solvability problems is S 3 .

Problem 2 Determine the complexity of the equivalence and equation solvability problems for (S 3 , •, [, ]).

  by the induction hypothesis there exists a term f such that the equivalence problem over (H, •, f ) is coNP-complete. By (1) of Lemma 10 the equivalence problem over (G, •, f ) is coNP-complete.Case 3: G and G/C G (G ) are both nilpotent. Let A be the terminal element of the lower central series of G, i.e. A = γ (G). We prove that A and G/C G (A) are commutative groups. Now, G/C G (G ) is nilpotent, and A is the terminal element of the lower central series, thus A

  and G/C G (A) is commutative. Hence A and G/C G (A) are both commutative. Theorem 5 finishes the proof. Finally, we prove Theorem 4 for solvable, non-nilpotent groups by induction on the order of G. Case 1: G = (G , •) is non-nilpotent. As |G | < |G|, by the induction hypothesis there exists a term f such that the equation solvability problem over (G , •, f ) is NP-complete. By (2) of Lemma 9 the equation solvability problem over (G, •, f ) is NP-complete.

  2.10) that G/G is non-nilpotent. Let H = G/G . As G = 1, we have |H| < |G|. Since H = (H, •) is non-nilpotent,by the induction hypothesis there exists a term f such that the equation solvability problem over(H, •, f ) is NP-complete. By (2) of Lemma 10 the equation solvability problem over (G, •, f ) is NP-complete.Case 3: G is nilpotent, G = 1. Let A be the terminal element of the lower central series of G, i.e. A = γ (G). We prove that A and G/C G (A) are commutative groups. Now, G = 1 thus G is commutative and A ≤ G yields that A is commutative, as well. Moreover, from A ≤ G we haveC G (A) ≥ C G (G ) ≥ C G (G ) = Z (G ) = G . Thus G/C G (A) ≤ G/G and G/C G (A) is commutative.Hence A and G/C G (A) are both commutative. Theorem 5 finishes the proof. P

  Now, we prove Theorem 3 for solvable, non-nilpotent groups by induction on the order of G. Case 1: G = (G , •) is non-nilpotent. As |G | < |G|, by the induction hypothesis there exists a term f such that the equivalence problem over

we can obtain t (G, . . . , G) with O(n d ) many substitutions, thus in polynomial time of the length of t. Now, t ≈ 1 if and only if t (G, . . . , G) = { 1 }. Moreover, t = 1 can be solved if and only if 1 ∈ t (G, . . . , G).

Acknowledgements

This research was partially supported by the Hungarian National Foundation for Scientific Research grants K67870, N67867.

r i = p i (ḡ i ). Now, a ∈ A and t Γ h, ḡ = s h uΓ(p(ḡ1),...,p(ḡn)) = a uΓ(r1,...,rn) .

We prove that u Γ (r 1 , . . . , r n ) = 0. For this substitution, let us define the color of v i to be the F 1component of r i . Since Γ is not q 1 -colorable, there exists an edge v i v j such that the F 1 -components of r i and r j are the same. Thus the

Finally, we prove that the equation solvability over (G, •, f ) is NP-complete. The proof is literally the same as the proof of the coNP-completeness of the equivalence problem, apart from the following differences. Let r ∈ R c be an idempotent such that its F 1 -component is 1, and its F k -component is 0 (for 2 ≤ k ≤ l). If Γ is q 1 -colorable then, as we proved in the coNP-completeness part, there exists elements r 1 , . . . , r n ∈ R c such that u Γ (r 1 , . . . , r n ) = 0. From the same argument, r • u Γ (r 1 , . . . , r n ) = r follows, as well. Let a ∈ A, a = 1 be arbitrary for which a r = a. Then t Γ = a is solvable if and only if Γ is q 1 -colorable. P

3 Proof of Theorems 3 and 4

In this section we prove Theorems 3 and 4. By the following lemma the equivalence and equation solvability problems can be reduced to verbal subgroups.

Lemma 9 Let V = (V, •) be a verbal subgroup of the group G = (G, •). Let f be a group term.

1. If the equivalence problem over (V, •, f ) is coNP-complete, then the equivalence problem over (G, •, f ) is coNP-complete.

2. If the equation solvability problem over (V, •, f ) is NP-complete, then the equation solvability problem over (G, •, f ) is NP-complete.

Proof: We prove only (1), as the proof of (2) is similar. We give a polynomial reduction from the equivalence problem of (V, •, f ) to the equivalence problem of (G, •, f ). For every term t(x 1 , . . . ,

While ȳi runs through all the k-tuples of G, the value of s(ȳ i ) attains every element of V. Thus if t = 1 at some evaluation (h 1 , . . . , h n ) ∈ V n , then we can choose the tuples ȳi such that s(ȳ i ) = h i . Thus there exists an evaluation of t such that t = 1.