Monika Pilsniak
email: pilsniak@agh.edu.pl

Mariusz Woźniak
email: mwozniak@agh.edu.pl

Monika Pilśniak

On packing of two copies of a hypergraph

Keywords:

A 2-packing of a hypergraph H is a permutation σ on V (H) such that if an edge e belongs to E(H), then σ(e) does not belong to E(H). Let H be a hypergraph of order n which contains edges of cardinality at least 2 and at most n -2. We prove that if H has at most n -2 edges then it is 2-packable.

Introduction

Let H = (V, E) be a hypergraph, where V is the vertex set and E ⊂ 2 V is the edge set. We allow empty edges for technical reasons, hence a complete simple hypergraph of order n has 2 n edges. We consider only finite hypergraphs. The edge of cardinality t is called t-edge, and 1-edge is called a singleton. A vertex is isolated if it does not belong to any edge. The number d(v) of edges containing a vertex v is called the degree of v ∈ V . A hypergraph is t-uniform if |e| = t for all e ∈ E. Let H be a hypergraph of order n. A packing of two copies of H (2-packing of H) is a permutation σ on V (H) such that, if an edge e = {x 1 , ..., x k } belongs to E(H), then the edge σ(e) = {σ(x 1 ), ..., σ(x k )} does not belong to E(H). Such a permutation (a packing permutation) is also called an embedding of H into its complement. Consider a hypergraph H and a permutation σ on V . We have σ(V ) = V and σ(∅) = ∅. So, if V ∈ E or ∅ ∈ E, then H cannot be packable.

We proved the following result in [START_REF] Pilśniak | A note on packing of two copies of a hypergraph[END_REF].

Theorem 1 If a hypergraph H of order n and size at most 1 2 n has neither the empty edge nor its complement, then H is 2-packable.

Observe that this bound is sharp. Namely, if H is a hypergraph of order n, and it has more than 1 2 n edges, and each edge is a singleton, then evidently H is not packable.

The aim of this paper is to show that if empty edges and singletons (and their complements, i.e. n-edges and (n -1)-edges) are excluded, then the bound on the size can be improved. We call a hypergraph H of order n admissible if 2 ≤ |H| ≤ n -2 holds for all edges H ∈ H.

We shall prove the following theorem.

Theorem 2 An admissible hypergraph H of order n and size at most n -2 is 2-packable.

Recall that a 2-uniform hypergraph is called a graph. The packing problems for graphs have been studied for about thirty years (see for instance chapters in the books by B. Bollobás or H. P. Yap ([2], [START_REF] Yap | Some Topics in Graph Theory[END_REF]), or survey papers by H. P. Yap or M. Woźniak ([9], [START_REF] Woźniak | Packing of graphs[END_REF], [START_REF] Woźniak | Packing of graphs and permutations -a survey[END_REF] and [START_REF] Woźniak | Embedding graphs of small size[END_REF])). One of the first results in this area was the following theorem (see [START_REF] Burns | Every (n, n -2) graph is contained in its complement[END_REF]).

Theorem 3 A graph G of order n and size at most n -2 is 2-packable.

This bound is tight. Namely, if G is a star (of order n and size n -1), then G is not packable. Let H be an admissible hypergraph of order n. First, denote by H k a k-uniform hypergraph of order n, which is induced by all k-edges in H, and let m k be the size of H k . Let m be the size of H. Thus

n -2 ≥ m = m 2 + m 3 + ... + m n-2 .
Let H = (V, E) be a hypergraph. Consider the hypergraph H = (V, Ẽ) with the same vertex set V and the edge set Ẽ, obtained from E in the following way: if e ∈ E has at most n 2 vertices then e belongs to Ẽ and if e has more than n 2 vertices, then e is replaced by V \ e, with the convention that a double edge conceivably created in this way is replaced by a single one.

Remark 4 Let H be an admissible hypergraph of order n. If the hypergraph H is 2-packable, then also H is 2-packable. Therefore, we shall assume that H of order n is restricted to have edges of size at most n/2 only.

Let H = (V, E) be an admissible hypergraph, and let x be a vertex of H. We define the hypergraph H = (V , E ) := H -x as follows: V = V \ {x}, and the set of edges is obtained from E by deleting 2-edges containing x, and replacing all remaining edges containing x by new edges with x deleted. It should be noted that it may happen that the assumption of Remark 4 does not apply to the hypergraph H. So, if necessary, we use H instead of H .

Lemmas

In the proof of Theorem 2, we shall use the following lemmas.

Lemma 5 Let H be an admissible hypergraph of order n ≥ 7. Let x be an isolated vertex in H 2 , and let y be a vertex of degree at least two in H 2 . Suppose that there does not exist any 3-edge e ∈ H such that x ∈ e and y ∈ e. If H = H -x -y is 2-packable, then H is also 2-packable. Moreover, H is an admissible hypergraph.

Proof: Let x and y be two vertices satisfying the assumptions. It is easy to see that H is an admissible hypergraph, since, by assumptions, there is no singleton in H , because there is no 3-edge e ∈ H such that x ∈ e and y ∈ e. On the other hand, since n ≥ 7, there is no (n -1)-edge in H (where n = n -2).

Let σ be a packing permutation of H . By the choice of x and y and the property of σ , it is easy to see that the permutation σ = σ • (xy), where (xy) denotes a transposition, is a packing permutation of H.

2

The proof of Lemma 6 is analogous to that of Lemma 5.

Lemma 6 Let H be an admissible hypergraph of order n ≥ 7. Let x and y be two not adjacent vertices of degree one in H 2 such that the neighbors x of x and y of y are distinct. Suppose that there does not exist any 3-edge e ∈ H such that x ∈ e and y ∈ e. If H = H -x -y is 2-packable, then H is also 2-packable. Moreover, H is an admissible hypergraph.

Lemma 7 Let H be an admissible hypergraph of order n and size at most

n -2. If m 2 ≤ n 2 , then H is 2-packable.
Proof: Using a probabilistic argument we shall show that a packing permutation exists for H.

Let e and f be two edges of H of the same cardinality and let σ be a random permutation on V . We say that edge e covers edge f (with respect to σ), if σ(e) = f . We denote this fact by (e f ). Let e and f be two k-edges. The event A such that e covers f (denoted by A(e f )) has probability equal to

P r(A(e f )) = k!(n -k)! n! = n k -1
.

Observe, that there are m 2 k ways to choose a pair e, f of k-edges such that e covers f . So, we have

P r   e,f ∈H A(e f )   ≤ e,f ∈H P r (A(e f )) = m 2 2 n 2 -1 + m 2 3 n 3 -1 + ... + m 2 n 2 n n 2 -1 . Since k ≤ n 2 , the sequence n 2 -1 , n 3
-1 , ... is decreasing, and we have

m 2 2 n 2 -1 + m 2 3 n 3 -1 + ... + m 2 n 2 n n 2 -1 ≤ m 2 2 n 2 -1 + n 3 -1 m 2 3 + ... + m 2 n 2 ≤ ≤ m 2 2 n 2 -1 + n 3 -1 (n -2 -m 2 ) 2 .
If m 2 = 0, then n ≥ 5, and

m 2 2 n 2 -1 + n 3 -1 (n -2 -m 2 ) 2 = n 3 -1 (n -2) 2 .
If m 2 = 1, then n ≥ 3, and

m 2 2 n 2 -1 + n 3 -1 (n -2 -m 2 ) 2 = n 2 -1 + n 3 -1 (n -3) 2 .
If m 2 ≥ 2, then n ≥ 4, and

m 2 2 n 2 -1 + n 3 -1 (n -2 -m 2 ) 2 ≤ 2n 2 4n(n -1) + 6(n -4) 2 n(n -1)(n -2)
.

It is easy to check that in each case

P r   e,f ∈H A(e f )   < 1.
Consequently, a 2-packing of an admissible hypergraph H of order n and size at most n -2 exists, if

m 2 ≤ n 2 . 2
3 Proof of Theorem 2

By Remark 4, we consider only hypergraphs with edges of cardinality at most n 2 . It is easy to see that for n ≤ 6, either H has only 2-edges, and we can apply Theorem 3, or the number of 2-edges is less than or equal to n/2, and we can apply Lemma 7. So, let n ≥ 7.

Observe that, by Lemma 7, our claim holds if H 2 is empty. Therefore, the proof will be divided into two main cases corresponding to the structure of H 2 which is supposed to be non-empty.

The proof goes by induction on n. Let x, y be two vertices satisfying the assumptions of Lemma 5 or of Lemma 6. A 3-edge containing both of them will be called a blocking edge. Observe that if there is no blocking edge in H, then the induction hypothesis can be applied. Below, we shall very often estimate the number of blocking edges in order to get a contradiction with the size of H. Case 1. There is no vertex of degree one in H 2 .

The hypergraph H 2 has at most n -2 edges, so it has at least two isolated vertices. Denote by w the number of non-isolated vertices in H 2 . Observe that w ≥ 3 and w ≤ m 2 . Let y be a vertex of degree at least 2 in H 2 . If we can choose an isolated vertex x in H 2 such that there is no 3-edge containing both x and y, then we are done. So, suppose that a 3-edge containing both x and y exists in H for every isolated vertex x in H 2 and for any y. Observe that one 3-edge can cover at most two pairs of vertices x, y satisfying the assumptions of Lemma 5. Hence,

m 3 ≥ 1 2 w(n -w) ≥ 1 2 w(n -m 2 ), 2m 3 + wm 2 ≥ wn. Hence, w(m 2 + m 3 ) ≥ wn, but m 2 + m 3 ≤ n -2, a contradiction.
Case 2. There is a vertex of degree one in H 2 .

Let b = m 3 + ... + m n 2 . If b = 0, then H is a graph, and the claim is true. Hence, let b > 0. Then m 2 = n -2 -b. Denote by t the number of tree components in H 2 . So, t ≥ b + 2. Next, denote by i the number of isolated vertices in H 2 , by j the number of isolated edges, by k the number of stars with at least two leaves, and by l the number of trees with diameter greater than two. Thus, t = i + j + k + l. We shall consider four subcases.

Case 2A. There are at least two vertices of degree at least two in H 2 , and j + k + l ≥ 2.

As above, we shall count, how many blocking edges have to be in H. Denote by n 2 the number of vertices of degree at least two in H 2 . By assumption, n 2 ≥ 2. So, if we are not able to apply Lemma 5, we should have at least ( 1 2 in 2 ) 3-edges in H. Similarly, if we are not able to apply Lemma 6, we should have at least

[ 1 3 • 4 • j+k+l 2
] 3-edges in H. Observe that one 3-edge can cover at most three pairs of vertices x, y which satisfy the assumptions of Lemma 6. Moreover, between every two tree components with at least two leaves, there are at least four such pairs. There are j+k+l 2 such pairs. Observe that all 3-edges mentioned above have to be distinct. Hence, we have

1 2 in 2 + 4 3 • j + k + l 2 ≤ b ≤ t -2 = i + j + k + l -2.
Observe that 1 2 in 2 ≥ i,

and 4 3 • 1 2 • (j + k + l)(j + k + l -1) ≥ 1 • 1 • (j + k + l -1).
Again, we obtain a contradiction.

Case 2B. There are at least two vertices of degree at least two in H 2 , and j + k + l < 2.

Thus, we have l ≤ 1 and n 2 ≥ 2. Analogously as in Case 2A, we consider blocking edges in H. If l = 0, we obtain two cases:

1) if j + k = 0, then i ≤ 1 2 in 2 ≤ b ≤ t -2 = i -2; 2) if j + k = 1, then i ≤ 1 2 in 2 ≤ b ≤ t -2 = i -1.
If l = 1 we have at least one blocking edge more. Then,

i + 1 ≤ 1 2 in 2 + 1 ≤ b ≤ t -2 = i + l -2 = i -1.
In all cases we get a contradiction.

Case 2C. There is at most one vertex of degree at least two in H 2 , and j + k + l < 2.

By definition, l = 0. Therefore, we have three subcases to consider. If k = j = 0 or k = 0 and j = 1, then by Lemma 7, our claim is true. Thus, let j = 0 and k = 1. So, H 2 consists of a star K 1,p and i isolated vertices. Observe that if p ≤ n 2 , then we are done by Lemma 7. Hence, let p > n 2 . Then, n = i + p + 1. Let y be the center of the star, and let x be an isolated vertex in H 2 . If for any vertex z, the set {x, y, z} is not an edge of H, then we are done by Lemma 5.

If the vertex y belongs to two edges of the form {x, y, z} ∈ E(H) for any isolated vertex x, then we have the inequality

p + 2 • i 2 ≤ n -2.
Since p + 2 • i 2 = n -1, we obtain a contradiction. Therefore, there exists an isolated vertex x such that H contains exactly one 3-edge {x, y, z}. Now, we construct a hypergraph H = (V , E ) such that V = V -{x, y} and the set of edges is obtained from E as follows: we delete all 2-edges as well as the edge {x, y, z}, and we replace all remaining edges containing x or y (or x and y) by new edges with these vertices deleted. Then H has two vertices less, and at least p + 1 edges less than H.

We shall show that there exists a packing permutation σ of H without fixed points.

By the choice of x and y and the property of σ , it is easy to see that the permutation σ = σ • (xy), where (xy) denotes a transposition, will be a packing permutation of H.

An edge of the form {x, s, t} ∈ H (where s = y and t = y) will be called an x-edge. Analogously, an edge of the form {y, s, t} ∈ H (where s = x and t = x) will be called a y-edge.

First, we consider the case where H has either x-edges or y-edges. We construct the hypergraph H = (V , E ) as follows: V = V , and the set of edges is obtained from E by deleting all x-edges and y-edges. So m 2 = 0 in H . Now, we use a probabilistic argument as in the proof of Lemma 7.

P r

  e,f ∈H A(e f )   ≤ n 3 -1 (n -2 -p -1) 2 ≤ 6(n -6) 2 4(n -2)(n -3)(n -4) < 1 e - 1 n! .
It is easy to observe that the last inequality holds for n ≥ 6. (Recall that the probability that a random permutation has no fixed point is greater than or equal to 1 e -1 n! .) Now, suppose that there are ξ x-edges and η y-edges in H. Observe that we have at least p+3 edges in H (there are p edges of the star, the edge {x, y, z}, at least one x-edge and at least one y-edge). Then, p + 3 ≤ n -2. But p > n 2 , hence n ≥ 11. In general, we have at least (ξ + η + 1 + p) edges in H. Therefore ξ + η ≤ n 2 -3. Then a product ξη is maximal if ξ = η = 1 2 ( n 2 -3). Analogously as above, we use a probabilistic argument to show that there is a packing permutation σ without fixed points of H . Observe that there are ξ + η edges in H 2 , and an x-edge cannot be mapped by σ onto a y-edge (and vice versa). We have

P r   e,f ∈H A(e f )   ≤ 2 • 2ξη • (n -2)! n! + n 3 -1 (n -2 -p -3) 2 ≤ ≤ (n -6) 2 4n(n -1) + 3(n -10) 2 2(n -2)(n -3)(n -4) < 1 e - 1 n! .
It is easy to check that the last inequality is satisfied for n ≥ 11, and consequently, there exists a packing permutation of H without fixed points.

This research was partially supported by the Polish Ministry of Science and Higher Education 1365-8050

Case 2D. There is at most one vertex of degree at least two in H 2 , and j + k + l ≥ 2.

Then, H 2 has only tree components, l = 0 and k ≤ 1.

If k = 0, then j ≥ 2 and j ≤ n 2 (because j is the number of isolated edges in H 2 ). Then, by Lemma 7, the conclusion holds. On the other hand, n -

Observe that the number of 3-edges in H is at least i 2 (because of Lemma 5), and at least 2pj 2 (because of Lemma 6). (In the latter case, we may assume that one of the leaves comes from the star.)

We know from a structure of the hypergraph that n = i + 2j + p + 1, so it follows from the above inequality that 2j + p + 1 -4 2 ≥ pj.

This inequality together with the fact that 2pj ≥ 2p + 2j for p, j ≥ 2, implies 2j + p -3 ≥ 2pj ≥ 2p + 2j, a contradiction.

This ends the proof of the theorem.


Min Chen
email: chenmin@zjnu.cn.

André Raspaud
email: raspaud@labri.fr

Weifan Wang

8-star-choosability of a graph with maximum average degree less than 3

Keywords: ] List star coloring, maximum average degree, in-coloring, orientation

A proper vertex coloring of a graph G is called a star-coloring if there is no path on four vertices assigned to two colors. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring

The star list chromatic number of G, denoted by χ l s (G), is the smallest integer k such that G is k-star-choosable. In this article, we prove that every graph G with maximum average degree less than 3 is 8-star-choosable. This extends a result that planar graphs of girth at least 6 are 8-star-choosable [A.

Introduction

Only simple graphs are considered in this paper unless otherwise stated. A plane graph is a particular drawing of a planar graph in the Euclidean plane. For a graph G, we use V (G), E(G), |G|, and δ(G) to denote its vertex set, edge set, order, and minimum degree, respectively. The girth g(G) of G is the length of a shortest cycle in G.

A proper k-coloring of G is an assignment of k colors 1, 2, • • • , k to V (G) such that adjacent vertices receive different colors. If G has a proper k-coloring, then G is said to be k-colorable. The chromatic number, denoted by χ(G), is the smallest integer k such that G is k-colorable. A proper vertex coloring of a graph G is acyclic if there is no bicolored cycle in G. In other words, the graph induced by the union of every two color classes is a forest. The acyclic chromatic number, denoted by χ a (G), of G is the smallest integer k such that G has an acyclic k-coloring.

The notion of acyclic coloring of graphs was first introduced by Grünbaum in [START_REF] Grünbaum | Acyclic colorings of planar graphs[END_REF]. In 1979, Borodin [START_REF] Borodin | On acyclic coloring of planar graphs[END_REF] confirmed Grünbaum's conjecture that every planar graph is acyclically

mad(G) = max{ 2|E(H)| |V (H)| : H ⊆ G}.
Kündgen and Timmons [START_REF] Kündgen | Star coloring planar graphs from small lists[END_REF] proved the following.

Theorem 1 [START_REF] Kündgen | Star coloring planar graphs from small lists[END_REF]) Let G be a graph.

(1) If mad(G) < 8 3 , then χ l s (G) ≤ 6.

(2) If mad(G) < 14 5 , then χ l s (G) ≤ 7.

(3) If G is planar and g(G) ≥ 6, then χ l s (G) ≤ 8.

It is well known that a planar graph G with girth g(G) satisfies mad(G) < 2g(G) g(G)-2 . Using this fact and (1) and (2) in Theorem 1, we immediately deduce that for a planar graph G, we have χ l s (G) ≤ 6 if g(G) ≥ 8, and χ l s (G) ≤ 7 if g(G) ≥ 7. The purpose of this paper is to extend the result (3) in Theorem 1 to graphs with maximum average degree less than 3. More precisely, we will prove the following:

Theorem 2 Every graph G with mad(G) < 3 is 8-star-choosable.

Preliminaries

For simplicity, we use i + to denote a number of at least i. A k-vertex, k + -vertex, or k --vertex is a vertex of degree k, at least k, or at most k. A k(d)-vertex is a k-vertex adjacent to d 2-vertices. For v ∈ V (G), let n 2 (v) denote the number of 2-vertices adjacent to v, and N G (v) denote the set of neighbors of v in G. A walk of G is a non-empty alternating sequence of vertices and edges denoted by

W = v 1 e 1 v 2 e 2 • • • e k-1 v k , where e i = v i v i+1 for each 1 ≤ i ≤ k -1. If all the vertices of a walk v 1 e 1 v 2 e 2 • • • e k-1 v k are
mutually distinct, then we call such a walk a path, simply denoted by Let xy ∈ E(G). We use x → y to denote that the edge xy is oriented from x to y. For a simple undirected graph G, an orientation of G is obtained by assigning a direction to each edge, denoted by

P = v 1 v 2 • • • v k-1 v k . We say that v 1 , v k are the endpoints of P and v 2 , • • • , v k-1 are internal vertices of P . For S ⊆ V (G), let G -S
- → G . For v ∈ V ( - → G ), we define the outdegree vertices set of v by D + - → G (v) = {u|u ∈ N-→ G (v) and v → u}. A special orientation - → G of G is an orientation in which each vertex v satisfies |D + - → G (v)| ≤ 2.
In order to study the star chromatic number of graphs, Albertson et al. [START_REF] Albertson | Coloring with no 2-colored p4's[END_REF] introduced the following useful concept.

A proper coloring of an oriented graph G is called an in-coloring if for every 2-colored P 3 on three vertices in G, the edges are directed towards the middle vertex. A coloring of G is an in-coloring if it is an in-coloring of some orientation of G. An L-in-coloring of G is an in-coloring of G such that the colors are chosen from the lists assigned to each vertex. We say that a graph G with a given orientation is

k-in-choosable if it is L-in-colorable for every list assignment L with |L(v)| ≥ k for all v ∈ V (G0).
Though the proof of the following Lemma 1 is very similar to that of Lemma 3.2 in [START_REF] Albertson | Coloring with no 2-colored p4's[END_REF], we like to write, for completeness, its details.

Lemma 1 An L-coloring of a graph G is an L-star-coloring if and only if it is an L-in-coloring of some orientation of G.

Proof. Given an L-star-coloring, we can construct an orientation by directing the edges towards the center of the star in each star-forest corresponding to the union of two color classes.

Conversely, consider an L-in-coloring of -→ G , an orientation of G. Let P 4 = uvwz be any path on four vertices in G. We may assume that the edge vw is directed towards w in -→ G . For the given coloring to be an L-in-coloring at v, we must have three different colors on u, v and w.

2 So, in order to control the number of colors used in an in-coloring, it is useful to bound the maximum outdegree of the orientation -→ G . In 1981, [START_REF] Tarsi | On the decomposition of a graph into stars[END_REF] observed the fact that a graph has an orientation with maximum outdegree at most d if and only if mad(G) ≤ 2d. This implies that every graph with mad(G) < 3 has an orientation with maximum outdegree at most 2. Therefore, to obtain our Theorem 2, by Lemma 1, we only need to prove the following Theorem 3.

Theorem 3 Every graph G with mad(G) < 3 has an orientation of maximum outdegree at most 2 that makes the graph 8-in-choosable.

The following section is dedicated to the proof of Theorem 3. For all figures depicted in Section 3, a vertex is represented by a solid point when all of its incident edges are drawn; otherwise it is represented by a hollow point.

Proof of Theorem 3

In what follows, let L be an uncolorable list assignment of G with |L(v)| = 8 for all v ∈ V (G). Suppose that G is a counterexample with the least number of vertices to Theorem 3. Thus G is connected. Moreover, any subgraph H with |H| < |G| admits an L-in-coloring of some special orientation -→ H . We first discuss some properties of G, then use discharging technique to derive a contradiction.

By the definition of maximum average degree and Tarsi's observation, we first note the following statement.

Observation 1 Every subgraph H ⊆ G admits a special orientation.

So, in the following, we always admit a special orientation

- → H of H. Moreover, for v ∈ V ( - → H ), define N * - → H (v) = D + - → H (v) ∪ {v}. It is obvious that |N * - → G (v)| ≤ 3. For simplicity, we write N * (v) for N * - → H (v).
We further use S(v) to denote the set of vertices whose coloring is forbidden on v by the definition of L-in-coloring when we are about to color v.

In the proofs below, in the subgraph in question the vertices will be taken in an appropriate order in such a way that when we color a vertex v, in the subgraph which is colored before v, the number of vertices putting a constraint to v is smaller than the list size of v, and therefore each vertex can get a color from its list in this order.

Claim 1 G contains no 1-vertex.

Proof. Suppose that x is a 1-vertex of G and y is the neighbor of x. Let H = G-{x}. By the minimality of G, H admits an L-in-coloring c of some special orientation -→ H . We orient the edge xy from x to y to establish an orientation -→ G of G. Clearly, the resulting orientation -→ G is special. Now, we assign a color to x in L(x), different from the colors of the vertices in N * (y). It is easy to see that the color for x is proper and thus we extend c to G, which is a contradiction. 2

In the proofs of Claims 2 to 8, we use B to denote the set of all solid vertices, depicted in Fig. 1 to Fig. 6. Let H = G -B. By the minimality of G, H admits an L-in-coloring c of some special orientation -→ H . We give an orientation of G[B] and those edges between V (H) and B such that the resulting orientation -→ G is special. Then we extend c to B to obtain an L-in-coloring of -→ G , which contradicts the choice of G.

v 1 v 1 ' v 1 k v 1 ' k v k v 1 v 2 v i v 1 n v n v 1 ' v 2 ' v ' i v 1 ' n v ' n v Fig. 1: is a ( -1)-vertex. v k k 1 2
Fig. 2: A good path .

n P v v v Claim 2 G contains no k(k -1)-vertex for any 2 ≤ k ≤ 5. Proof. Assume to the contrary that v is a k(k -1)-vertex with 2 ≤ k ≤ 5. Let v 1 , • • • , v k denote the neighbors of v. Without loss of generality, assume that d(v i ) = 2 for all i ∈ {1, • • • , k -1} and d(v k ) ≥ 2. For each i ∈ {1, • • • , k -1}, let v i be the other neighbor of v i different from v. Let B = {v, v 1 , • • • , v k-1 } and H = G -B.
By the minimality of G, H has an L-in-coloring c of some special orientation -→ H . We construct an orientation for the edge set E(G [B]) and those edges between V (H) and B, as shown in Fig. 1. The resulting orientation

- → G is also special. Notice that |N * (u)| ≤ 3 for each u ∈ {v 1 , • • • , v k-1 , v k }. Based on c, we can color v, v 1 , • • • , v k-1 , successively, because • S(v) = N * (v k ) ∪ {v 1 , • • • , v k-1 }; • S(v i ) = N * (v i ) ∪ {v, v k }, for each i ∈ {1, • • • , k -1}.
Obviously, for each vertex x ∈ B we have

|S(x)| ≤ 3 + (k -1) = k + 2 ≤ 7 because 2 ≤ k ≤ 5. So the resulting coloring is an L-in-coloring of - → G , which is a contradiction. 2 Assume that P = v 1 v 2 • • • v n is an induced path with n ≥ 3 and all internal vertices are 3-vertices. If d(v 1 ) = d(v n ) = 2 then P is called a good path. If d(v 1 ) = 2 and d(v n ) ≥ 4 then P is called a bad path. If d(v 1 ) = 2 and d(v n ) = 3 then P is called a terrible path.
For simplicity, we use P (v 1 → v n ) to denote an orientation for the edge set E(P ) in such a way that

v i → v i+1 for each i ∈ {1, • • • , n -1}.
Claim 3 There is no good path in G.

Proof. Assume to the contrary that there exists a good path

P = v 1 v 2 • • • v n with n ≥ 3 in G.
By definition, v 1 , v n are both 2-vertices and the remaining vertices are all 3-vertices. Since P is an induced path, for each vertex v i ∈ V (P ), we may let v i be the other neighbor of v i which is not on P .

Let

B = {v 1 , • • • , v n } and H = G -B.
By the minimality of G, H has an L-in-coloring c of some special orientation -→ H . We define an orientation for the edge set

E(G[B]) ∪ {v 1 v 1 , • • • , v i v i , • • • , v n v n } in the following way: P (v 1 → v n ) and v j → v j for each j ∈ {1, • • • , n}, as depicted in Fig. 2. The resulting orientation - → G is special. We can color v 1 , v 2 , • • • , v n , successively, because • S(v 1 ) = N * (v 1 ) ∪ {v 2 }; • S(v 2 ) = N * (v 2 ) ∪ {v 1 , v 1 , v 3 }; • S(v i ) = N * (v i ) ∪ {v i-1 , v i-2 , v i-1 , v i+1 }, for each i ∈ {3, • • • n -1}; • S(v n ) = N * (v n ) ∪ {v n-1 , v n-2 , v n-1 }. Since |S(v)| ≤ 7 for each vertex v ∈ B, the obtained coloring is an L-in-coloring of G, which is a contradiction. 2 2 u 1 u i u m u ' m u 2 ' u ' i u 1 2 1 Fig. 3: A good cycle . m C u u u u A cycle C is called good if C is formed from a good path P = v 1 v 2 • • • v n by identifying 2-vertices v 1 and v n .
Claim 4 There is no good cycle in G.

Proof. Suppose to the contrary that

C = u 1 u 2 • • • u m u 1 is a good cycle such that d(u 1 ) = 2 and d(u i ) = 3 for all i ∈ {2, • • • , m}.
Notice that m ≥ 3. Since C is formed from a good path which is also an induced path, we may let u i be the third neighbor of u i that is not on C,

for each i ∈ {2, • • • , m}. Let B = {u 1 , • • • , u m } and H = G -B.
By the choice of G, H admits an L-in-coloring c of a special orientation -→ H . We define an orientation for the edge set

E(G[B]) ∪ {u 2 u 2 , • • • , u i u i , • • • , u m u m } in the following way: for each j ∈ {2, • • • , m-1}, set u j → u j+1 , u j → u j ; we further set u 1 → u 2 , u m → u 1
and u m → u m , see Fig. 3. We notice that the resulting orientation

- → G is also special. Based on c, we can color u 2 , u 3 , • • • , u m , u 1 , successively, because • S(u 2 ) = N * (u 2 ) ∪ {u 3 }; • S(u i ) = N * (u i ) ∪ {u i-1 , u i-2 , u i-1 , u i+1 }, for each i ∈ {3, • • • , m -1}; • S(u m ) = N * (u m ) ∪ {u 2 , u m-1 , u m-2 , u m-1 }; • S(u 1 ) = {u 2 , u 2 , u 3 , u m , u m , u m-1 }. Since |S(v)| ≤ 7 for each vertex v ∈ B, the resultant coloring is an L-in-coloring of G. 2 A cycle C is called light if every vertex is of degree 3. A chordless light cycle is a light cycle that is chordless. Suppose that C = v 1 v 2 • • • v n v 1 is a chordless light cycle. If there exists a terrible path P connecting one vertex in C, say v 1 , such that V (P ) ∩ V (C) = {v 1 }, then C is called a removable cycle, where v 1 is called a heavy 3-vertex of C. i v 2 v m v 1 v ' i v ' m v 1 x 2 x j x 1 t x t x 1 ' x 2 ' x ' j x 1 ' t x 2 ' v ' t x 1 2 1 1
Fig. 4: A removable cycle with a heavy 3-vertex .

m C v v v v v

Claim 5 There is no removable cycle in G.

Proof. Suppose to the contrary that there exists a removable cycle

C = v 1 v 2 • • • v m v 1 with a heavy 3- vertex v 1 such that P = x 1 • • • x t v 1 is a terrible path.
Namely, x 1 is a 2-vertex and the remaining other vertices of P are 3-vertices such that V (P ) ∩ V (C) = {v 1 }. For each i ∈ {2, • • • , m}, let v i be the other neighbor of v i not on C. Since P is an induced path, we further let x j be the other neighbor of x j not on P for each j ∈ {1, • • • , t}. In the following, denote

A 1 = {x 1 , • • • , x t } and A 2 = {v 2 , • • • , v m }.
We have to consider the following two cases.

Case 1 wz / ∈ E(G) for all w ∈ A 1 and z ∈ A 2 .

It means that the third neighbor of x j is not in C, for all j. Let B = V (C) ∪ V (P ) and H = G -B. By the choice of G, H admits an L-in-coloring c of a special orientation -→ H . We define an orientation for the edge set E(G[B]) and those edges between V (H) and B, as shown in Fig. 4. We note that

- → G is a special orientation. So we can color v 2 , • • • , v m , v 1 , x t , • • • , x 1 , successively, because • S(v 2 ) = N * (v 2 ) ∪ {v 3 }; • S(v i ) = N * (v i ) ∪ {v i-1 , v i-2 , v i-1 , v i+1 }, for each i ∈ {3, • • • , m -1}; • S(v m ) = N * (v m ) ∪ {v m-1 , v m-2 , v m-1 , v 2 }; • S(v 1 ) = {v 2 , v 2 , v 3 , v m , v m , v m-1 }; • S(x t ) = N * (x t ) ∪ {x t-1 , v 1 , v 2 }; • S(x t-1 ) = N * (x t-1 ) ∪ {x t-2 , x t , x t , v 1 }; • S(x j ) = N * (x j ) ∪ {x j-1 , x j+1 , x j+2 , x j+1 }, for each j ∈ {t -2, • • • , 2}; • S(x 1 ) = N * (x 1 ) ∪ {x 2 , x 2 , x 3 }.
Case 2 wz ∈ E(G), for some w ∈ A 1 and z ∈ A 2 .

Case 2.1 w = x 1 and z ∈ A 2 .

This means that

x 1 v s ∈ E(G), where s ∈ {2, 3, • • • , m}. If none of v s+1 , • • • , v m is adjacent to x j for some fixed j ∈ {2, • • • , t}, then x 1 x 2 • • • x t v 1 v m v m-1 • • • v s x 1 is a good cycle, which contradicts Claim 4. Otherwise, we may suppose that x j v k ∈ E(G) for some fixed k ∈ {s + 1, • • • , m} such that there is no edge between {x 2 , x 3 • • • , x j-1 } and {v s+1 , v s+2 , • • • , v k-1 }. However, a good cycle x 1 x 2 • • • x j v k v k-1 • • • v s x 1 is established, contradicting Claim 4. Case 2.2 w ∈ {x 2 , x 3 , • • • , x t } and z ∈ A 2 .
We may suppose that

x j v s ∈ E(G) for some fixed s ∈ {2, • • • , m} such that there is no edge between {x 2 , x 3 • • • , x j-1 } and V (C) -{v 1 }. If x l v q / ∈ E(G) for all l ∈ {j + 1, j + 2, • • • , t} and q ∈ {s + 1, s + 2, • • • , m}, then a removable cycle x j x j+1 • • • x t v 1 v m v m-1 • • • v s x j
with a heavy 3-vertex x j is formed and then the proof is reduced to the former Case 1. Otherwise, we may suppose that x k v q ∈ E(G) for some fixed q ∈ {s + 1, s + 2, • • • , m} such that there is no edge between {x j+1 , x j+2 ,

• • • , x k-1 } and {v s+1 , v s+2 , • • • , v q-1 }. However, a removable cycle x j x j+1 • • • x k v q v q-1 • • • v s x j
with a heavy 3-vertex x j is constructed which has been settled in the previous Case 1.

2

Suppose that P = v 1 v 2 • • • v n is a bad path such that d(v 1 ) = 2, d(v n ) ≥ 4, and d(v i ) = 3 for all i ∈ {2, • • • , n -1}. We say that v n is a sponsor of v 2 and v 2 is a target of v n . Moreover, let T (v n ) denote the set of targets of v n and let SP(v 2 ) denote the set of sponsors of v 2 . Claim 6 For each 4 + -vertex v, we have |T (v)| ≤ d(v) -n 2 (v).
Proof. Let x 1 be a 3 + -vertex adjacent to v. It suffices to show that there is at most one bad path starting from edge vx 1 . If d(x 1 ) ≥ 4, then vx 1 is not a bad path and thus we are done. Otherwise, we may suppose that

P = vx 1 • • • x m is a bad path with a target x m-1 such that d(x m ) = 2 and d(x i ) = 3 for all i = 1, • • • , m -1.
Next, we are going to show that there is no other bad path starting from edge vx 1 and thus conclude the proof of Claim 6.

Without loss of generality, assume that

P = P = vx 1 • • • x i x i+1 • • • x s-1 x s is a bad path with a target x s-1 of v. So d(x s ) = 2 and d(x k ) = 3 for all k ∈ {i + 1, • • • , s -1}. Let B 1 = {x i+1 , x i+2 , • • • , x s } and B 2 = {x i+1 , x i+2 , • • • , x m }. The proof is divided into the two cases below. Case 1 wz / ∈ E(G) for all w ∈ B 1 and z ∈ B 2 . This implies that B 1 ∩ B 2 = ∅. It is easy to observe that a good path x m x m-1 • • • x i+1 x i x i+1 x i+2 • • • x s is established. This contradicts Claim 3. Case 2 wz ∈ E(G), where w ∈ B 1 and z ∈ B 2 .
By symmetry, we only need to consider the following two possibilities.

Case 2.1 w ∈ {x i+1 , x i+2 , • • • , x s-1 } and z ∈ {x i+1 , x i+2 , • • • , x m-1 }. Denote z = x k for some fixed k ∈ {i + 1, i + 2, • • • , m -1}.
We may assume x j = w such that x j x k ∈ E(G) and x j is the nearest 3-vertex to x i on P . In other words, there are no edges between

{x i+1 , x i+2 , • • • , x j-1 } and {x i+1 , x i+2 , • • • , x k-1 }. It is obvious that x i x i+1 • • • x k x j x j-1 • • • x i+1 x i is a chordless light cycle with a heavy 3-vertex x k . Such kind of cycle is removable, which is a contradiction to Claim 5. Case 2.2 w ∈ {x i+1 , x i+2 , • • • , x s-1 } and z = x m . Denote w = x j , where j ∈ {i + 1, • • • , s -1}. Obviously, x m x m-1 • • • x i+1 x i x i+1 • • • x j x m is a good cycle, which is impossible by Claim 4. 2 1 z i z 1 t z t z 1 ' z ' i z ' t z 1 ' t z v 1 x 1 ' x 1 y 1 ' y 1 w 1 z i z 1 t z 1 t z x 1 ' z ' i z 1 ' t z v 1 y 1 ' y 1 w -1
Fig. 5: is a 4(2)-vertex with a target . (1) { , }. Proof. Let v be a 4(2)-vertex with four neighbors x 1 , y 1 , w 1 , z 1 such that d(x 1 ) = d(y 1 ) = 2 and d(z 1 ), d(w 1 ) ≥ 3. Suppose to the contrary that |T (v)| ≥ 1. We further suppose that P = vz 1 • • • z t is a bad path connecting v and v's target z t-1 . Let N G (x 1 ) = {v, x 1 } and N G (y 1 ) = {v, y 1 }. For each k ∈ {1, • • • , t}, let z k be the other neighbor of z k that is not on P . Obviously,

x 1 = y 1 . Let B = V (P ) ∪ {x 1 , y 1 } and H = G -B.
Let c denote an L-in-coloring of H for its special orientation -→ H . By the symmetry of G, we only need to consider the two cases below.

Case 1 z t / ∈ {x 1 , y 1 }.

We define an orientation for the edge set E(G [B]) and the edges between V (H) and B, as depicted in Fig. 5(1). The resulting orientation of -→ G is a special orientation. Based on c, we can color v, x 1 , y

1 , z 1 , • • • , z t , successively, because • S(v) = N * (w 1 ) ∪ {x 1 , y 1 , z 1 }; • S(x 1 ) = N * (x 1 ) ∪ {v, w 1 }; • S(y 1 ) = N * (y 1 ) ∪ {v, w 1 }; • S(z 1 ) = N * (z 1 ) ∪ {v, w 1 , z 2 }; • S(z 2 ) = N * (z 2 ) ∪ {z 1 , z 1 , v, z 3 }; • S(z i ) = N * (z i ) ∪ {z i-1 , z i-2 , z i-1 , z i+1 }, for each i ∈ {3, • • • , t -1}; • S(z t ) = N * (z t ) ∪ {z t-1 , z t-1 , z t-2 }.
Case 2 z t = y 1 .

We define an orientation for the edge set E(G [B]) and those edges between V (H) and B, as shown in Fig. 5(2). We observe that the resulting orientation of

- → G is special. Based on c, we may color v, x 1 , z 1 , • • • , z t , successively, because • S(v) = N * (w 1 ) ∪ {x 1 , z 1 }; • S(x 1 ) = N * (x 1 ) ∪ {v, w 1 }; • S(z 1 ) = N * (z 1 ) ∪ {v, w 1 , z 2 }; • S(z 2 ) = N * (z 2 ) ∪ {z 1 , z 1 , v, z 3 }; • S(z i ) = N * (z i ) ∪ {z i-1 , z i-2 , z i-1 , z i+1 }, for each i ∈ {3, • • • , t -1}; • S(z t ) = {v, w 1 , z t-1 , z t-1 , z t-2 }.
Therefore, we have completed the proof of Claim 7. 2

1 z i z 1 t z t z 1 ' z ' i z ' t z 1 ' t z v 1 1
Fig. 6 (1): .

s t x y z x 1 y j y 1 s y s y ' s y 1 ' s y 1 ' y ' j y 1 x 1 ' x 1 w 1 z i z 1 t z t z 1 ' z ' i z ' t z 1 ' t z v 1
Fig. 6 (2): .

s t x y z ! 1 y j y 1 s y 1 s y x 1 ' s y 1 ' y ' j y 1 w Claim 8 If v is a 4(1)-vertex, then |T (v)| ≤ 1.
Proof. Let v be a 4(1)-vertex with four neighbors x 1 , y 1 , w 1 , z 1 such that x 1 is a 2-vertex and y 1 , z 1 , w 1 are all 3 + -vertices. Suppose to the contrary that |T (v)| ≥ 2. Now, assume that there exist two bad paths P and P starting from vy 1 , vz 1 , respectively. We denote them by P = vy 1 • • • y s and P

= vz 1 • • • z t .
Obviously, d(y s ) = d(z t ) = 2 and the remaining internal vertices of P and P are all 3-vertices. Let x 1 denote the other neighbor of x 1 distinct from v. Let y j be the third neighbor of y j that is not on P . Similarly, let z k be the third neighbor of z k that is not on P . For our convenience, we denote

C 1 = {y 1 , • • • , y s } and C 2 = {z 1 , • • • , z t }.
We only need to consider the two cases as follows.

Case

1 yz / ∈ E(G) for all y ∈ C 1 and z ∈ C 2 This implies that C 1 ∩ C 2 = ∅. Let B = V (P ) ∪ V (P ) ∪ {x 1 } and H = G -B. Let c denote an L-in-coloring of H for its special orientation - → H .
To complete the proof of Case 1, we have to discuss the following two possibilities, depending on the situations of x 1 , y s and z t .

Case 1.1 x 1 = y s = z t = x 1 .

We define an orientation for the edge set E(G [B]) and those edges between V (H) and B, as shown in Fig. 6(1). The resulting orientation of -→ G is also special. We can color v, x 1 , y 1 , • • • , y s , z 1 , • • • , z t , successively, because

• S(v) = N * (w 1 ) ∪ {x 1 , y 1 , z 1 };

• S(x 1 ) = N * (x 1 ) ∪ {v, w 1 };

• S(y 1 ) = N * (y 1 ) ∪ {v, w 1 , y 2 };

• S(y 2 ) = N * (y 2 ) ∪ {y 1 , y 1 , v, y 3 };

• S(y j ) = N * (y j ) ∪ {y j-1 , y j-2 , y j-1 , y j+1 }, for each j ∈ {3, • • • , s -1};

• S(y s ) = N * (y s ) ∪ {y s-1 , y s-1 , y s-2 };

• S(z 1 ) = N * (z 1 ) ∪ {v, w 1 , z 2 };

• S(z 2 ) = N * (z 2 ) ∪ {z 1 , z 1 , v, z 3 };

• S(z i ) = N * (z i ) ∪ {z i-1 , z i-2 , z i-1 , z i+1 }, for each i ∈ {3, • • • , t -1};

• S(z t ) = N * (z t ) ∪ {z t-1 , z t-1 , z t-2 }.

Case 1.2 x 1 = y s = z t .

We define an orientation for the edge set E(G [B]) and those edges between V (H) and B, as depicted in Fig. 6(2). The resulting orientation of -→ G is special. We can color v, y 1 , • • • , y s , z 1 , • • • , z t , successively, because

• S(v) = N * (w 1 ) ∪ {y 1 , z 1 };

• S(y 1 ) = N * (y 1 ) ∪ {v, w 1 , y 2 };

• S(y 2 ) = N * (y 2 ) ∪ {y 1 , y 1 , v, y 3 };

• S(y j ) = N * (y j ) ∪ {y j-1 , y j-2 , y j-1 , y j+1 }, for each j ∈ {3, • • • , s -2};

• S(y s-1 ) = N * (y s-1 ) ∪ {y s-2 , y s-2 , y s-3 , v};

• S(y s ) = {v, w 1 , y s-1 , y s-1 , y s-2 };

• S(z 1 ) = N * (z 1 ) ∪ {v, w 1 , z 2 };

• S(z 2 ) = N * (z 2 ) ∪ {z 1 , z 1 , v, z 3 };

• S(z i ) = N * (z i ) ∪ {z i-1 , z i-2 , z i-1 , z i+1 }, for each i ∈ {3, • • • , t -1};

• S(z t ) = N * (z t ) ∪ {z t-1 , z t-1 , z t-2 }.

  denote the subgraph of G obtained by deleting the vertices in S and all edges incident to some vertices in S. Let G[S] denote the subgraph of G induced by S.

  If v is a 4(2)-vertex, then |T (v)| = 0.

  Fig.6(3):( ) and .

  Fig.6 (4):( ) and .

  Fig.6(5):( ) and .

Acknowledgements

The authors would like to thank the referees for their valuable suggestions that helped to improve this work. The first author's research was supported by NSFC (No. 11101377). The third author's research was supported by NSFC (No. 11071223), ZJNSFC (No. Z6090150), ZJIP (No. T200905), ZJEDSRF (No. Y200805398), ZSDZZZZXK08 and IP-OCNS-ZJNU.

Case 2 yz ∈ E(G), where y ∈ C 1 and z ∈ C 2 .

We need to consider the following two subcases, according to the situation of z.

Case 2.1 z ∈ {z 1 , • • • , z t-1 }.

We may denote z = z j such that z j is the 3-vertex nearest to v on P . The proof is divided into two possibilities.

Case 2.1.1 y = y s . This means that z j y s ∈ E(G) for some fixed j ∈ {1, • • • , t}. Let B = V (P ) ∪ {x 1 , z 1 , • • • , z j } and H = G -B. Let c denote an L-in-coloring of H for its special orientation -→ H . We define an orientation for the edge set E(G [B]) and those edges between V (H) and B, as shown in Fig. 6(3). The resulting orientation

Without loss of generality, we may let y = y k . If z j y s ∈ E(G), then a good cycle y s y s-1 • • • y k z j y s is formed, contradicting Claim 4. If z j y l ∈ E(G) for some fixed l ∈ {k + 1, k + 2, • • • , s -1}, then a removable cycle y l y l-1 • • • y k z j y l with a heavy 3-vertex y l is formed, contradicting Claim 5. So, in what follows, we suppose that there is no edge connecting z j and one vertex belonging to {y k+1 , • • • , y s }. On the other hand, we recall that z q with q ∈ {1,

We need to deal with the following two possibilities, according to the situations of x 1 and y s .

We define an orientation for the edge set E(G [B]) and those edges between V (H) and B, as depicted in Fig. 6(4). Clearly, the resulting orientation of

We define an orientation for the edge set E(G[B]) and those edges in V (H) and B, as shown in Fig. 6(5). The resulting orientation of

The proof can be reduced to the previous Case 2.1.1. Therefore, we have completed the proof of Claim 8.

2

Now we use a discharging argument with initial charge ω(v) = d(v) at each vertex v and with the following two discharging rules (R1) and (R2). We write ω * to denote the charge at each vertex v after we apply the discharging rules. Note that the discharging rules do not change the sum of the charges. To complete the proof, we show that ω * (v) ≥ 3 for all v ∈ V (G). This leads to the following obvious contradiction:

Hence no counterexample can exist.

Our discharging rules are defined as follows:

(R1) Each 2-vertex gets 1 2 from each of its neighbors.

(R2) Each 3(1)-vertex gets 1 4 from each of its sponsors.

Let us check that ω * (v) ≥ 3 for each v ∈ V (G). By Claim 1, we derive that δ(G) ≥ 2. In the following argument, we let

Then ω(v) = 3. Recall that SP(v) denotes the set of sponsors of v, which was defined before Claim 6. We begin with the following claim.

Proof. Without loss of generality, suppose that v 1 is a 2-vertex and v 2 , v 3 are both 3 + -vertices. By Claim 3, it is easy to deduce that there exist at least two bad paths starting from vv 2 and vv 3 , respectively. It follows immediately that |SP(v)| ≥ 2.

2

According to Claim 2, we infer that v is neither a 3(2)-vertex nor a 3(3)-vertex. So, it suffices to consider the following two subcases.

• If v is a 3(0)-vertex, then v sends nothing to each v i by (R1) and (R2) and thus ω * (v) = 3.

• Now we suppose that v is a 3(1)-vertex. Without loss of generality, assume that d(v 1 ) = 2 and d(v 2 ), d(v 3 ) ≥ 3. By (R1), v sends a charge 1 2 to v 1 . On the other hand, by Claim 9, we observe that v has at least two sponsors, each of which sends a charge 1 4 to v by (R2). Therefore,

This implies that ω(v) = 4. By using Claim 2, we derive that v is neither a 4(4)-vertex nor a 4

. Finally, we suppose that v is a 4(0)-vertex. It means that n 2 (v) = 0. Then |T (v)| ≤ 4 by Claim 6 and we conclude that ω * (v) ≥ 4 -1 4 × 4 = 3 by (R2). Case 4 d(v) = 5.

Obviously, ω(v) = 5. By Claim 2, we deduce that n 2 (v) ≤ 3. Moreover, it follows immediately from Claim 6 that |T (v)| ≤ 5 -n 2 (v). So, by applying (R1) and (R2), we obtain that ω * (v) ≥ 5 -1 2 n 2 (v) -


Nurullah Ankaralioglu

Ákos Seress

Computing tensor decompositions of finite matrix groups

Keywords:

We describe an algorithm to compute tensor decompositions of central products of groups. The novelty over previous algorithms is that in the case of matrix groups that are both tensor decomposable and imprimitive, the new algorithm more often outputs the more desirable tensor decomposition.

Background

A recent active area of computational group theory is the so-called matrix group recognition project. Let V be a finite dimensional vector space over a finite field GF (q). Given G = X ≤ GL(V ), the goal is to compute quantitative and structural information about G such as the order, a composition series, and important characteristic subgroups like the largest solvable normal subgroup of G.

There are two main approaches to matrix group recognition. The geometric approach, initiated by Neumann and Praeger [START_REF] Neumann | A recognition algorithm for special linear groups[END_REF] and currently led by Leedham-Green and O'Brien [START_REF] Leedham-Green | The computational matrix group project[END_REF], [START_REF] O'brien | Algorithms for matrix groups[END_REF], is based on Aschbacher's classification of matrix groups [START_REF] Aschbacher | On the maximal subgroups of the finite classical groups[END_REF]. Aschbacher defines nine categories of matrix groups G. In seven of these categories, there is a natural normal subgroup N ¡ G that can be used to divide the recognition problem into two smaller subproblems on N and G/N . Based on that result, the geometric approach tries to find a homomorphism ϕ : G → H into an appropriate permutation or matrix group H, and recursively recognize Im(ϕ) and Ker(ϕ). In contrast, the black-box group approach of Babai and Beals [START_REF] Babai | A polynomial-time theory of black box groups. I[END_REF] aims for the abstract group theoretic structure of G. Babai and Beals define a series of characteristic subgroups, present in all finite groups, and initiate a program that tries to compute a composition series going through these characteristic subgroups.

The original aim of the black-box group approach was the development of an algorithm with fast asymptotic running time. This aim was recently achieved in [START_REF] Babai | Polynomial-time theory of matrix groups[END_REF]. In that paper, a Las Vegas algorithm is described that computes |G| and a composition series, and sets up a data structure for membership testing in G. The running time is polynomial in the input length, plus the cost of using number theoretic oracles for discrete logarithm computation and for the factorization of integers, with the assumption that the composition factors of G are nice. "Nice" for a nonabelian simple group S means that S can be constructively recognized (i.e., an isomorphism with a natural copy of S can be built) in polynomial time, using number theory oracles. Currently, the "nice" category includes all sporadic, alternating, and classical groups, and most exceptional groups defined over small fields [START_REF] Beals | A black-box group algorithm for recognizing finite symmetric and alternating groups, I[END_REF], [START_REF] Brooksbank | Fast constructive recognition of black-box unitary groups[END_REF], [START_REF] Brooksbank | Fast constructive recognition of black box symplectic groups[END_REF], [START_REF] Brooksbank | On constructive recognition of a black box PSL(d, q)[END_REF], [START_REF] Brooksbank | Fast constructive recognition of black box orthogonal groups[END_REF], [START_REF] Kantor | Black-box exceptional groups[END_REF]. We note that the use of number theory oracles seems to be unavoidable, since the cited cryptographic problems arise already in the case of 1 × 1 matrix groups.

In contrast, the primary goal of the geometric approach is the development of a practical algorithm for matrix group recognition. There is great success in this direction as well: a data structure to accommodate homomorphisms, and glueing the results of the subproblems in kernels and images of homomorphisms, was designed and implemented both in Magma [START_REF] Bosma | Handbook of MAGMA functions[END_REF] (by O'Brien) and in GAP [START_REF]Algorithms and Programming[END_REF] (by Neunhöffer and Seress [START_REF] Neunhöffer | A data structure for a uniform approach to computations with finite groups[END_REF], [START_REF] Neunhöffer | GAP Package "recogbase[END_REF], [START_REF] Neunhöffer | GAP Package "recog[END_REF]). Many mathematicians contributed algorithms and implementations for homomorphisms and for the handling of terminal nodes of the recursion tree, to be included in these frameworks.

Although the original aim of the geometric approach was the development of a practical algorithm and the guiding principle of the black-box group approach was a rigorous complexity analysis, recent developments combine the two aims very successfully. New subroutines with polynomial running time are designed and analyzed in the geometric approach, while methods and ideas from the black-box approach are utilized in practical algorithms.

The present paper is a contribution to the growing library of algorithms for the geometric approach, in the case of tensor product groups.

Tensor products

One of the Aschbacher classes (class C4 in the notation of Kleidman and Liebeck [START_REF] Kleidman | The Subgroup Structure of the Finite Classical Groups[END_REF], which is becoming the standard of the area) is the class of tensor products: the underlying vector space V of dimension mn can be written as a tensor product V = U ⊗ W of an n-dimensional space U and an m-dimensional space W , and G ≤ A × B for some irreducible A ≤ GL(U ) and B ≤ GL(W ). We assume that A and B are nonabelian groups. The goal is to recognize the tensor structure of V and construct the homomorphisms ϕ U : G → P GL(U ) and ϕ W : G → P GL(W ). Note that the homomorphisms ϕ U , ϕ W are necessarily projective, because of the ambiguity of the tensor decomposition of scalar matrices.

A recent polynomial-time solution for this problem was announced by Ryba [START_REF] Ryba | Personal communication at the Oberwolfach workshop on Computational Group Theory[END_REF]. Given G ≤ GL(V ), Ryba's algorithm constructs the tensor decomposition of V if the decomposition exists, or returns fail. However, the algorithm works in vector spaces with dimension the square of the dimension of V , so in its current form it is not suitable for implementation.

In the special, but frequently occurring, case of G = A • B with the central product taken over the scalar matrices, a more practical algorithm called SMASH was described by Holt et al [START_REF] Holt | Computing matrix group decompositions with respect to a normal subgroup[END_REF]. The algorithm SMASH tries to construct some g ∈ G which actually belongs to A or B, and computes the normal closure C := g G . Then a composition series for the C-module V is computed; if all composition factors are isomorphic then the tensor decomposition of V can be read from the embedding of composition factors in V and their identifications by the isomorphisms. Algorithms based on this idea are implemented both in Magma and GAP.

If, in addition, the group G also belongs to the Aschbacher category C2 (case of imprimitive groups, which means that there exists a direct sum decomposition

V = V 1 ⊕ V 2 ⊕ • • • ⊕ V k
so that G permutes the subspaces V i ) then the algorithm described in the previous paragraph usually does not find the tensor decomposition of V . Rather, the composition factors fall into more than one isomorphism types, and the union of embeddings of isomorphic factors gives a subspace V i in an imprimitivity decomposition. This outcome is sufficient in the recursive procedure of matrix recognition, because a homomorphism of G into the permutation group Sym(k) can be computed. However, finding a tensor decomposition is a more valuable outcome, because it defines two homomorphisms so that the intersection of kernels fixes V pointwise (note that V may be a section of a larger vector space, occurring in the middle of a recursive procedure). In contrast, the kernel of the homomorphism into an imprimitivity decomposition acts on a sum of many invariant subspaces and finding the pointwise stabilizer of V may require much more additional work. Therefore, we set out the goal of designing and implementing an algorithm with the following properties.

(i) If the input group is nonabelian, belongs to category C4, and G = A • B, then the algorithm constructs a tensor decomposition or imprimitivity decomposition of V .

(ii) If both tensor and imprimitivity decompositions exist then the algorithm has a good chance to find the tensor decomposition.

(iii) The algorithm succeeds and fails fast.

Goal (iii) may require some explanation. Of course, succeeding fast is the desirable outcome for algorithms. However, we should not forget that our algorithm is used in a big recursive scheme, for exploring inputs G where we have no idea whether G is in category C4. In the case when G is not a C4 group, the algorithm should fail fast, and not spend too much time for trying to construct the nonexisting tensor decomposition.

The novelty of our approach is the goal (ii). Although we cannot give a complexity analysis, and it is easy to construct tensor decomposable inputs on which the algorithm fails, the practical performance is quite satisfactory. We shall give some running times and frequency of success counts in Section 4.

The tensor product input groups known to us, where the algorithm fails completely, are all solvable. Fortunately, failing on that class of groups is not fatal for the overall success of matrix group recognition. Solvable groups can be treated efficiently by specialized algorithms both in theory by Luks [START_REF] Luks | Computing in solvable matrix groups[END_REF] and in practice. Depending on the organization of subroutines in a composition tree computation, our algorithm may never encounter such an input.

The algorithm

The input is G = X = GL(V ) ∼ = GL(d, q), and the output is one of the three possibilities below. The first of these outcomes is the most desirable, if the input group is indeed tensor decomposable. we choose particular values for k 1 , k 2 so that the restriction matrix M 1 (g) does not consist of all 0 entries. We regard M 1 (g) modulo scalar matrices, to define a projective transformation. Similarly, ϕ W : G → P GL(W ) is defined by restricting M (g) to the entries in positions {(in+k 1 , jn+k 2 ) | 0 ≤ i, j ≤ m -1} for some fixed k 1 , k 2 chosen so that 1 ≤ k 1 , k 2 ≤ n and the restriction matrix M 2 (g) does not consist of all 0 entries.

(b) A decomposition V = V 1 ⊕ V 2 ⊕ • • • ⊕ V k such that the subspaces V i are permuted by G.
(c) The report fail.

The algorithm has three major parts. In the high-level description below, we assume that G ≤ A • B and G is tensor decomposable; for other inputs, the algorithm will output fail.

Algorithm 3.1 (TENSORDECOMPOSE)

Input: G = X = GL(V ) ∼ = GL(d, q).
Step 1: Construct a list L containing some elements of G that are candidates to belong either to A or B.

Step 2: Choose a sublist L 1 of L, consisting of candidates all belonging to A, or all belonging to B.

If L 1 is empty then output fail. Construct the normal closure C := L G 1 .
Step 3: Check whether C defines a tensor decomposition or imprimitivity decomposition of V . Now we give details of the three main steps.

Step 1.

For this step, we utilize two standard techniques. One of them is to take (pseudo)random elements g ∈ G, compute the projective order |g|, and for all prime divisors p of |g|, add g |g|/p to L. The idea is that for g = ab, with a ∈ A and b ∈ B, there is a hope that different powers of p divide |a| and |b|. In this case, g |g|/p ∈ A or g |g|/p ∈ B. Some justification for the hope is given by the following theorem of Babai, Pálfy, and Saxl [START_REF] Babai | On the number of p-regular elements in finite simple groups[END_REF]. Theorem 3.2 [START_REF] Babai | On the number of p-regular elements in finite simple groups[END_REF] If a simple group S is a quotient of a group H ≤ GL(n, q) and p is an arbitrary prime then the proportion of elements of S of order not divisible by p is at least min{1/31, 1/(2n)}.

Hence, if both A and B have simple nonabelian quotients, or cyclic quotients of different size, then we have a fair chance that some prime will divide exactly one of |a|, |b| for the decomposition of a random g ∈ G, g = ab.

The second method to generate elements of the list L is Neunhöffer's involution jumper (IJ) [START_REF] Neunhöffer | Constructive Recognition of Finite Groups[END_REF]. Although the IJ is one of the most powerful techniques to construct elements in proper normal subgroups, the method may not be widely known (yet) and so we give a pseudocode description. The pseudocode (including the jesting stopping condition) was copied from [START_REF] Neunhöffer | Talk at the Univ[END_REF].

Algorithm 3.3 (INVOLUTIONJUMPER)

Input: G = X and an involution x ∈ G. The group elements c, z constructed by the IJ are the outputs of Bray's algorithm [START_REF] Bray | An improved method for generating the centralizer of an involution[END_REF] to construct elements of C G (x) and, if one of them happen to be of even order, then IJ outputs the involution that is the appropriate power of c or z. Neunhöffer [START_REF] Neunhöffer | Constructive Recognition of Finite Groups[END_REF] proved the following. Theorem 3.4 [START_REF] Neunhöffer | Constructive Recognition of Finite Groups[END_REF] The algorithm IJ defines a Markov chain on the conjugacy classes of involutions of G. This Markov chain is irreducible and aperiodic, and so in the stationary distribution every involution class has non-zero probability.

In particular, if at least one of the groups A, B modulo scalars has even order then repeated applications of IJ may construct an element belonging to A or B. In the implementation, we add powers of 10 random elements to L, and the results of 10 applications of the involution jumper.

Step 2.

This step is the novelty of our approach. Previous algorithms, after assembling a list of candidates such that at least one of them belongs to some proper normal subgroup, try to combine them to one group element x that belongs to a proper normal subgroup. To this end, the best technique is Beals and Babai's blind descent [START_REF] Beals | Las Vegas algorithms for matrix groups[END_REF] (see also [START_REF] Seress | Permutation Group Algorithms[END_REF]Ex. 2.7]). Applying blind descent (or any variant) to our list L, the output x may fall into a proper normal subgroup of A or B; in particular, if A or B is in the Aschbacher class C2 then x may fix pointwise an imprimitivity decomposition of U or W and the tensor decomposition algorithm also outputs a less desirable imprimitivity decomposition of V . Therefore, we proceed the following way.

We define the non-commuting graph of the list L. This is a graph with vertex set L, and g, h ∈ L are connected if and only if they do not commute.

Step 3.

For Step 3, we simply use the subroutine RECOG.SortOutReducibleNormalSubgroup from the GAP package recog, written by Max Neunhöffer, and described in [START_REF] Neunhöffer | Constructive Recognition of Finite Groups[END_REF]. That program computes a composition series of the C-module V , and checks whether the factor modules are isomorphic. If they are then we obtain the output (a) described at the beginning of Section 3; if there are more than one isomorphism classes of C-modules then we obtain output (b); finally, if C acts irreducibly on V then we report fail.

Some runtimes

We ran both the new program and RECOG.FindHomMethodsProjective.D247 at least 100 times on each example. We report the percentage of the three possible outcomes (tensor decomposition C4, imprimitivity decomposition C2, and fail), and the average running time in seconds.

In general, the algorithm in the recog package runs faster. In the cases when the reported running times are roughly the same, the average for recog was increased significantly by some "unlucky" cases, or because recog tries harder for a positive outcome. In such cases, the new program may more readily report failure. As advertised, the advantage of the new approach is that in some cases it may construct a tensor decomposition with higher probability than the recog package.

  (a) A factorization d = mn of the input dimension and a base change matrix M such that group elements written in the new basis B are Kronecker products of an n × n matrix and an m × m matrix. The homomorphism ϕ U : G → P GL(U ) is defined by restricting the matrix M (g) in B of some g ∈ G to the entries in positions {(k 1 n + i, k 2 n + j) | 1 ≤ i, j ≤ n}. No matter which values 0 ≤ k 1 , k 2 ≤ m -1 are chosen, the restriction matrices are scalar multiples of each other;

  repeat y := random element of G c := x -1 y -1 xy and o := |c| if o is even then return c o/2 else z := y • c (o-1)/2 and o := |z| if o is even then return z o /2 until patience lost return fail

  Tab. 1: G = GL(10, 7) • GL(10, 7) ≤ GL(100, 7)

	new	C4	C2 fail recog	C4	C2 fail
	frequency		100% 0%	0%	100% 0%	0%
	time		2.3s	-	-	0.4s	-	-
	new		C4	C2	fail recog	C4	C2	fail
	frequency	57.9% 35.8% 6.3%	2.5% 97.5%	0%
	time		0.4s	0.4s	02.s	0.2s	0.4s	-
	new		C4	C2	fail recog C4	C2	fail
	frequency		7.1% 52.1% 40.8%	0% 100%	0%
	time		0.6s	0.6s	02.s	-	0.6s	-
				Tab. 4: G = GL(100, 7)
	new C4 C2 fail recog C4 C2 fail
	frequency		0% 0% 100%	0% 0% 100%
	time		-	-	5.1s	-	-	5.0s

Tab. 2: G = (GL(2, 7) C7) • (GL(2, 7) S5) ≤ GL(140, 7)

Tab. 3: G = (GL(2, 7) C7) • (GL(2, 7) C7) ≤ GL

(196,[START_REF] Bosma | Handbook of MAGMA functions[END_REF]

Acknowledgements

We are indebted to Max Neunhöffer both for theoretical advice and for his help with the implementation of the algorithm.

research partially supported by the NSF and by ARC Grant DP1096525 1365-8050 c 2011

If, for some x, y ∈ L, we have x ∈ A and y ∈ B then of course x and y commute. On the other hand, if x, y both have nontrivial projections on A (or B) then, with positive probability, x and y do not commute. Hence, by removing the vertices of large valency from Γ, we hope that we deleted all vertices of Γ that have nontrivial projections on both A and B, and the remaining group elements are in A ∪ B. If indeed this happens then all vertices in a connected component are in A, or they are all in B, and the group C constructed by the algorithm satisfies

The gain compared to previous approaches is that we have better chance for achieving C = A or C = B. If we used L to construct only one element x in A ∪ B then it may have happened with larger probability that C := x G is a proper subgroup of A or B.

Steps 1 and 2 can be executed in a "grey-box" setting. By that, we mean that with one exception, the algorithm in Steps 1 and 2 uses only multiplication, inversion, and comparison of group elements (i.e., black-box operations); the only additional requirement is an oracle to compute element orders.

Considering Steps 1 and 2 as a grey-box algorithm, the costliest operation is the construction of the non-commuting graph of L. However, this subtask can be sped up significantly by randomization, and exploiting that L contains elements from a matrix group. To check whether x, y ∈ L commute, instead of the matrix multiplications xy and yx we computed and compared vxy and vyx, for two randomly chosen vectors from V . The justification follows from the following simple lemma. Lemma 3.6 Let x, y ∈ GL(d, q). If x and y do not commute then, for a randomly chosen vector v ∈ GF (q) d , Prob(vxy = vyx) ≥ 1 -1 q .

Proof: If x and y do not commute then the fixed point space F of xyx -1 y -1 has dimension at most d -1.

Hence Prob(vxy = vyx) = Prob(v ∈ F ) ≤ q d-1 /q d = 1/q. P


Péter Pál Pach

Csaba Szabó

On the minimal distance of a polynomial code

Keywords: near-ring code, minimal distance, prime

For a polynomial f (x) ∈ Z2[x] it is natural to consider the near-ring code generated by the polynomials f • x, f • x 2 , . . . , f • x k as a vectorspace. It is a 19 year old conjecture of Günter Pilz that for the polynomial f (x) =

The conjecture is equivalent to the following purely number theoretical problem. Let m = {1, 2, . . . , m} and A ⊂ N be an arbitrary finite subset of N. Show that the number of products that occur odd many times in n • A is at least n. Pilz also formulated the conjecture for the special case when A = k. We show that for A = k the conjecture holds and that the minimal distance of the code is at least n/(log n) 0.223 . While proving the case A = k we use different number theoretical methods depending on the size of k (respect to n). Furthermore, we apply several estimates on the distribution of primes.

For an arbitrary finite subset A ⊂ N it was proved that |m * A| ≥ π(m) + 1, where π(x) is the prime counting function, and the following conjecture was formulated (Pilz (1992)):

Conjecture 2 Let n be a positive integer and K ⊂ N be a finite set of integers. Then |n * K| ≥ n.

These purely number theoretical problems originate in the theory of near-ring codes. A near-ring can be described as a ring, where the addition is not necessarily commutative and only one of the distributive laws is required. A typical example is the near-ring of polynomials, where the addition is the usual polynomial addition, and multiplication is the composition of the polynomials. In this example the addition is commutative and only the right distributive law holds. Near-rings play an important role in combinatorics: They are used to construct block designs that give rise to efficient error correcting codes. For more information on these codes see [START_REF] Eggetsberger | On constructing codes from planar nearrings[END_REF], [START_REF] Pilz | The theory and its applications[END_REF] and [START_REF] Pilz | Near-rings: What they are and what they are good for[END_REF]. A special and very interesting near-ring code is defined in the following way: Let f ∈ Z 2 [x] be a polynomial and C(f, k) the code generated (as a subspace) by the polynomials f

= f •x, f •x 2 , . . . , f •x k . For f = x+x 2 +• • •+x n a typical codeword is i∈K f • x i = j∈K * n x j ,
where K is a finite subset of k. As C(f, k) is a linear code, its minimal distance is equal to the minimal weight of any nonzero codeword. Hence the minimum distance of C(f, k) is the minimal value of |n * K| for some K ⊆ k.

In this paper we settle Conjecture 1, and prove that for arbitrary n ∈ N and finite set

K ⊂ N we have |n * K| ≥ c • n log 0.223 n
for some c > 0. Note that the minimal distance in C(f, k) depends heavily on f .

If, for example, we start with f (

x) = x + x 2 + x 4 + • • • + x 2 k , then f • x + f • x 2 = x + x 2 k+1
, hence the minimal distance of the corresponding code is 2.

The natural logarithm will be denoted by log through the whole paper.

The general case

Let us denote by g(n) the minimal size of the set n * K, where K is a finite subset of the positive integers.

In Pilz (1992) it is proved that g(n) ≥ π(n) + 1. In this section we improve this lower bound and prove that g(n) ≥ c • n log 0.223 n for some c > 0. The proof is based on the following lemma:

Proposition 1 For every positive integer n

g(n) ≥ p≤n g ( n/p αp ) ,
where the sum goes over the primes less than n, and α p is the largest integer such that p αp ≤ n.

Proof: Let p ≤ n be a prime and K p ⊆ K the subset of K containing the elements that are divisible by the largest power of p occuring as divisor of some element of K (possibly p 0 = 1). Similarly, let n p ⊆ n be the set of elements of n that are divisible by p αp . Note that n p is never empty. By the maximality of the exponents of p in K p and n p , for any a ∈ n p , b ∈ K p and c ∈ n, d ∈ K if ab = cd, then c ∈ n p and d ∈ K p hold. We prove that for p < q ≤ n different primes n p • K p and n q • K q are disjoint. If for some a ∈ n and b ∈ K we have ab ∈ n p • K p ∩ n q • K q , then a ∈ n p ∩ n q . Thus a = pqd , and ā = p 2 d < a is in n. The exponent of p in ā is larger than the one in a, which is contradiction. Hence, n * K contains the disjoint union of the sets n p

|n p * K p | = | n/p αp * K p | ≥ g( n/p αp ).
By (1) we have

g(n) ≥ p≤n g ( n/p αp ) ,
and this is what we wanted to prove. 2

Theorem 2 For every λ > λ 0 there exists a c = c(λ) > 0 such that for every n > 1

g(n) ≥ c • n log λ n ,
where λ 0 satisfies

1 0 2 y λ0 1 2 -y dy = 1. Note that λ 0 ∼ 0.2223... Proof: Fix 1 > λ > λ 0 .
We claim that there exists some c > 0 such that the inequality

g(n) ≥ c • n log λ n (2)
holds for every n > 1. The proof is by induction on n. First we discuss the induction step. Assume that (2) holds for n < m. Now, we show that it holds for n = m, as well. The value of c will be chosen later.

By Proposition 1 and the induction hypothesis:

g(m) ≥ √ m<p≤m g ( m/p ) ≥ √ m<p<m/2 c • m/p log λ ( m/p ) ≥ ≥ √ m<p<m/2 c • m/p log λ ( m/p ) ≥ √ m<p<m/2 c • m/p -1 log λ ( m/p ) = = √ m<p<m/2 c • m/p log λ ( m/p ) - √ m<p<m/2 c • 1 log λ ( m/p ) . (3)
In [START_REF] Rosser | Approximate formulas for some functions of prime numbers[END_REF]

it is proved that π(m) < 1.25506m log m for every m > 1, hence π(m/2) - π( √ m) ≤ π(m) < 1.5 • m log m
. For the second term of the last line of (3) we obtain:

√ m<p<m/2 c • 1 log λ ( m/p ) ≤ √ m<p<m/2 c • 1 (log 2) λ ≤ 1.5 • m log m • c log 2 = o m log λ m , (4)
since λ < 1.

Now we estimate the main term. By Mertens' theorem, there exists a constant M such that p≤x 1 p = log log x + M + o(1). Hence, for every ε > 0 there exists

B = B(ε) such that for B ≤ a ≤ b a<p<b 1 p -log log b + log log a < ε (5) holds. For m > 2 2K we have m 1 2 + K-1 2K < m/2. Applying (5) to the interval I h = (m 1 2 + h-1 2K , m 1 2 + h 2K ], where h is an integer satisfying 1 ≤ h ≤ K -1 we obtain that p∈I h 1 p > log K + h K + h -1 -ε. (6) If p ∈ I h , then log λ (m/p) ≤ log λ (m)( K-h+1 2K ) λ .
Substituting into the main term of the last line of (3), omitting the integer parts and rearranging we get that

√ m<p<m/2 c • m/p log λ ( m/p ) ≥ cm √ m<p<m/2 1/p log λ (m/p) ≥ ≥ cm log λ m K-1 h=1 p∈I h 2K K -h + 1 λ • 1 p ≥ ≥ cm log λ m K-1 h=1 2K K -h + 1 λ log K + h K + h -1 -ε K-1 h=1 2K K -h + 1 λ . (7)
Now we show that there exists some K such that

S K = K-1 h=1 2K K -h + 1 λ log K + h K + h -1 > 1. (8) Let f K (y) = 2 y λ K • log 1 + 1 K(2 -y) and f (y) = 2 y λ • 1 2 -y
. The sequence of functions f K converges to f . Then

S K = f K ( 1 K ) + f K ( 2 K ) + • • • + f K ( K K ) K - f K ( 1 K ) K .
Let

T K = f ( 1 K ) + f ( 2 K ) + • • • + f ( K K ) K .
As 1 > λ > λ 0 , the Riemann-sum T k converges to

1 0 f > 1. As f K ( 1 K )/K converges
to 0, it is easy to see that S K -T K converges to 0. Hence we can fix a K such that S K > 1. Now, we can choose some

ε > 0 such that η = K-1 h=1 2K K -h + 1 λ log K + h K + h -1 -1 -ε K-1 h=1 2K K -h + 1 λ > 0.
According to (4) there exists some R such that if R < m, then

√ m<p<m/2 c • 1 log λ ( m/p ) ≤ η • c • m log λ m .
By ( 3) and ( 7) we obtain that g(m) ≥ c • m log λ m holds. If we choose c > 0 such that (2) holds for

n ≤ max(2 2K , B 2 (ε), R), then (3) is gained. 2 3 The case K = k
In this section we prove Conjecture 1. We distinguish cases according to how large is k according to n.

The conjecture is true for k ≤ 8. (Pilz (1992))

Case 1:

9 ≤ k ≤ 1.34 • log n
We show that in this case the number of elements that occur exactly once in the product n • k is at least n. We shall need the following two observations. Lemma 3 Let n/2 < a ≤ n and b ∈ k such that a is relatively prime to every number less than k. Then ab occurs once in n • k.

Proof: Let us assume that a 1 , a 2 ∈ n and b 1 , b 2 ∈ k satisfy the conditions of the lemma, and a 1 b 1 = a 2 b 2 . Now, a 1 |a 2 b 2 and a 1 and b 2 are relatively prime, hence a 1 |a 2 . As a 1 > n/2 we have 2a 1 > n ≥ a 2 , thus

a 1 = a 2 , which implies b 1 = b 2 . 2 Lemma 4 If k ≥ 14, then p≤k 1 - 1 p ≥ 0.5 log k .
Proof: In [START_REF] Rosser | Approximate formulas for some functions of prime numbers[END_REF] it is shown that for k > 1

e -γ log k 1 - 1 log 2 k ≤ p≤k 1 - 1 p ,
where γ is the Euler constant. For k > 21 by using the monotonicity of the logarithm function and e -γ > 0.56 we get that

e -γ log k 1 - 1 log 2 k ≥ 0.56 log k 1 - 1 log 2 22 > 0.5 log k .
For 14 ≤ k ≤ 21 it is enough to check the statement when k = 14, 17 and 19. For these numbers the values of (log k) • Proof: We show that there are at least n products satisfying the conditions of Lemma 3. For this we need to estimate the number of integers between n/2 and n that are not divisible by a prime less than k. This number will be denoted by D. By the inclusion-exclusion principle

D = n -n/2 + r h=1 (-1) h 1≤i1<...<i h ≤r n p i1 . . . p i h n/2 p i1 . . . p i h , (9)
where π(k) = r and p 1 , . . . , p r are the primes up to k. Applying x -1 < x ≤ x to all 2 r+1 terms of the right side we get that

D ≥ n -n/2 + r h=1 (-1) h 1≤i1<...<i h ≤r n p i1 . . . p i h - n/2 p i1 . . . p i h -2 r = = n 2 p≤k 1 - 1 p -2 r . ( 10
)
If k ≥ 14, Lemma 4 applies, and

D ≥ n 2 p≤k 1 - 1 p -2 r ≥ 0.25n log k -2 r
As k ≤ 1.34 log n, for k ≥ 14 we have the estimation For 9 ≤ k ≤ 13 we have

2 r = 2 π(k) ≤ 2 k/2 ≤ 1 100 log k • e k 1.
|n * k| ≥ Dk ≥   n 2 p≤k 1 - 1 p -2 π(k)   k.
For 10 ≤ k ≤ 13 it is obtained by calculation that the right hand side is greater than n if n ≥ e k/1.34 . For k = 9 the inequality holds if n > 5040. By brute force the statement can be checked for k = 9 and n ≤ 5040. Thus we obtained |n * k| > n. 2

Case 2:

1.34 • log n ≤ k ≤ n - 0.22 • n log n and n ≥ 1410.
Let k 1 = max(k, n/7) and k 1 < p ≤ n a prime. As k < p, the set of elements of n * k, which are divisible by p is {p, 2p, . . . , n/p p} * k. This set has the same cardinality as the set n/p * k. Now, n/p ≤ 6, hence | n/p * k| ≥ k. It is easy to see that for p > q > n/7 an element of n * k cannot be divisible by both p and q. Hence, |n * k| ≥ (π(n) -π(k 1 ))k.

At first, suppose that k ≤ n/7. By a theorem of [START_REF] Dusart | The kth prime is greater than k(ln k + ln ln k -1) for k ≥ 2[END_REF] for x ≥ 17

x log x ≤ π(x) ≤ x log x 1 + 1.2762 log x holds. Hence, π(n) -π(n/7) ≥ 0.749 • n log n for n ≥ 1410. As 1.34 • log n ≤ k, we have |n * k| ≥ 1.34 • 0.749 • n > n.
Secondly, let us consider the case when n

/7 < k ≤ n/2. As π(n) -π(n/2) ≥ 7, |n * k| ≥ (π(n) -π(k 1 ))k > 7 • n/7 = n. Finally, let n/2 < k < n - 0.22 • n log n .
Then by the estimates in [START_REF] Dusart | The kth prime is greater than k(ln k + ln ln k -1) for k ≥ 2[END_REF] and [START_REF] Robin | Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n[END_REF] there are at least two primes between k and n if n > 90000. It can be checked that this also holds for n > 1410.

Thus |n * k| ≥ (π(n) -π(k))k ≥ 2(n/2) = n.
We continue with the case when k is "large", that is, n -0.4•n log n+1.02 ≤ k. By calculation we have n -0.4•n log n+1.02 ≤ n -0.22•n log n for n ≥ 4.

Case 3:

n - 0.4 • n log n + 1, 02
≤ k ≤ n and n > 5000.

If k = n, then k • n = {1, . . . , n} • {1, . . . , n}. If a = b, then pairing ab with ba only the products of the form a • a are left, hence n * k = {1 2 , 2 2 , . . . , n 2 }. Thus

|n * k| = n. Assume now that k < n. Then |n * k| = |(k * k)∆((n \ k) * k)| = |k * k| + |(n \ k) * k| -2|(k * k) ∩ ((n \ k) * k)|. (11)
For the first term on the right side of (11) we have

|k * k| = |{1 2 , 2 2 , . . . , k 2 }| = k. ( 12
)
Lemma 6 For the second term of (11) we have

|(n \ k) * k| ≥ 2k -n. (13)
Proof: We use the following observation: If

i ≤ k n -k and k + 1 ≤ j ≤ n, then ij appears exactly once in (n \ k) • k, so ij ∈ (n \ k) * k. Let us assume that ij = i j such that 1 ≤ i ≤ k and k + 1 ≤ j ≤ n. If i = i , then j = j . If i < i, then 1 ≤ i ≤ k n -k and k + 1 ≤ j ≤ n.
Now, changing the roles of (i, j) and (i , j ) we may assume that i < i . As ij = i j , we have i i = j j and

i i ≤ i i + 1 ≤ k n-k k n-k + 1 = k n < k + 1 n ≤ j j ,
which is a contradiction. For (n \ k) * k we obtain that

|(n \ k) * k| ≥ k n -k (n -k) ≥ k n -k -1 (n -k) = k -(n -k) = 2k -n. (14)
2

Now, we focus on the third term of (11).

Lemma 7 For the third second term of ( 11)

|(k * k) ∩ ((n \ k) * k)| ≤ 0.431 • k. ( 15
)
holds.

Proof: It is enough to show that among the numbers 1 2 , 2 2 , ..., k 2 at most 0.431k many has a divisor in the interval

[k + 1, n]. Let k + 1 ≤ m ≤ n and m = a m b 2 m
, where b 2 m is the largest square divisor of m. Since a m is squarefree, m|i 2 if and only if a m b m |i. Let S denote the following upper bound of the number of elements of the set {1 2 , 2 2 , . . . , k 2 } which have a divisor in [k + 1, n]:

S = n m=k+1 k a m b m ≤ n m=k+1 k a m b m = k n m=k+1 b m m . Recall that m = a m b 2 m , where a m is squarefree. Now, summing by j = b m ≤ √ m: S = k √ n j=1 j 2 |m, k+1≤m≤n, |µ(m/j 2 )|=1 j m ≤ k √ n j=1 j j 2 |m, k+1≤m≤n 1 m .
Rewrite S = k(S 1 + S 2 ), where

S 1 := √ n/2 j=1 j j 2 |m, k+1≤m≤n 1 m and S 2 := √ n j= √ n/2 +1 j j 2 |m, k+1≤m≤n 1 m .
First, we give an upper bound for S 1 .

Lemma 8

S 1 ≤ log n 2 + 0.31 (log n -log k) + n + 2 √ n 8k . (16)
Proof: Let r j = k + 1 j 2 and s j = n j 2 . Then

S 1 = √ n/2 j=1 j sj l=rj 1 lj 2 = √ n/2 j=1 1 j sj l=rj 1 l . (17)
The function 1

x is a nonnegative decreasing function on (0, ∞), hence we can estimate the inside sum by

sj l=rj 1 l ≤ sj rj 1/x + 1 r j = log s j -log r j + 1 r j .
As k j 2 ≤ r j and s j ≤ n j 2 we have log s j -log r j = log s j r j ≤ log n/j 2 k/j 2 = log n -log k.

Substituting into (17) we obtain

S 1 ≤ √ n/2 j=1 1 j log s j -log r j + 1 r j ≤ √ n/2 j=1 1 j log n -log k + j 2 k . ( 18
) Since √ n/2 j=1 1 j ≤ log √ n/2 + 1 ≤ log n 2 -log 2 + 1 ≤ log n 2 + 0.31. (19)
and

√ n/2 j=1 j = √ n/2 • ( √ n/2 + 1) 2 ≤ n + 2 √ n 8 , (20)
from the inequalities (18), ( 19), (20) we get ( 16). 2

Now we give an upper bound for S 2 .

Lemma 9

S 2 ≤ 1 + 1 √ 2 + 1 √ 3 • n -k 2 √ k • √ n k + 3 √ n k < 1.15 • (n -k) √ n k 3/2 + 3 √ n k . ( 21
)
Proof:

S 2 = √ n j= √ n/2 +1 j 2 |m, k+1≤m≤n j m (22)
In ( 22) for every j we have n ≥ j 2 ≥ ( √ n/2 + 1) 2 > n 4 .

Hence m = j 2 or 2j 2 or 3j 2 . As k < m ≤ n, for m = ij 2 (i = 1, 2, 3) we get

k i < j ≤ n i and j m ≤ √ n k .
For fixed i, the number of j such that m = ij 2 is at most:

√ n - √ k √ i = 1 √ i • n -k √ n + √ k ≤ 1 √ i • n -k 2 √ k + 1, thus S 2 ≤ 1 + 1 √ 2 + 1 √ 3 • n -k 2 √ k • √ n k + 3 √ n k < 1.15 • (n -k) √ n k 3/2 + 3 √ n k ,
and this is what we wanted to show. 2

Summarizing the results, from ( 16) and ( 21) we obtain:

S = k(S 1 + S 2 ) ≤ ≤ k log n 2 + 0.31 (log n -log k) + n + 2 √ n 8k + 1.15 • (n -k) √ n k 3/2 + 3 √ n k . (23)
We assumed that n -0.4•n log n+1.02 ≤ k and n ≥ 5000. By using the inequality e -x < 1 1+x we obtain that ne = n -0.4•n log n+1.02 ≤ k. As n ≥ 5000, we have that k n > 0.958.

  subsets of the positive integers, A and B let A * B = {ab | a ∈ A, b ∈ B and ab occurs odd many times in A • B}. In other words, if A = {a 1 , . . . , a k }, then A * B = a 1 B∆ • • • ∆a k B, where ∆ denotes the symmetric difference. For a positive integer m let m = {1, 2, . . . , m}. Conjecture 1 If n, k are positive integers, then |n * k| ≥ n.

Proposition 5

 5 506, 0.511 and 0.503, respectively, hence the statement holds. 2 Let 9 ≤ k ≤ 1.34 • log n. Then |n * k| ≥ n.

-

  As p αp ≤ n < p αp+1 , clearly, n p = {p αp , 2p αp , . . . , n/p αp p αp }, where n/p αp < p. Dividing by p αp , we obtain that |n p * K p | = | n/p αp * K p |, thus by the definition of g we get

	• K p for p ≤ n, so
	|n * K| ≥	|n p * K p |.	(1)
	p≤n

By easy calculation from these inequalities the following ones can be deduced:

Adding ( 24), ( 25) and ( 26) using ( 23) we arrive at:

Then from inequalities ( 12), ( 13) and ( 15) in case k/n > 0.958 we get

thus we proved the statement in Case 3 as well. 2

We proved the statement for all pairs n, k where n ≥ 5000. Cases k ≤ n ≤ 5000 can be checked by brute force.


Helmut Prodinger
email: hproding@sun.ac.za.

Philippe Flajolet

Digital search trees with m trees: Level polynomials and insertion costs

Keywords: Digital search tree, level polynomial, Rice's method, cancellations, q-analysis

revisited Digital Search Trees and understood the power of Rice's integrals

Introduction

Digital search trees (=DSTs), level polynomials and insertion costs are certainly classical subjects: [START_REF] Knuth | The Art of Computer Programming, volume 3: Sorting and Searching[END_REF]; [START_REF] Flajolet | Analytic Combinatorics[END_REF]; [START_REF] Mahmoud | Evolution of Random Search Trees[END_REF]; [START_REF] Flajolet | Digital search trees revisited[END_REF]; [START_REF] Louchard | Exact and asymptotic distributions in digital and binarysearch trees[END_REF]; [START_REF] Kirschenhofer | Further results on digital search trees[END_REF]; [START_REF] Szpankowski | A characterization of digital search trees from the successful search viewpoint[END_REF]; [START_REF] Prodinger | Digital search trees and basic hypergeometric functions[END_REF].

The following sentences from our own [START_REF] Prodinger | Digital search trees and basic hypergeometric functions[END_REF], which never appeared in a proper journal, can be reproduced here almost verbatim:

A DST is constructed like a binary search tree, but the decision to go down to the left or right is done according to the representation of the key as a binary string of bits. If the first bit is 0, the item goes to the left, otherwise to the right. Then the second bit is responsible for left or right, etc., until there is an empty node where the item can be stored. Decisions are made independently.

The classic book [START_REF] Knuth | The Art of Computer Programming, volume 3: Sorting and Searching[END_REF] contains a more elaborate description. Now, in order to study the average search costs in a DST built from n random data (i.e., in every decision, 0 and 1 is equally likely), the polynomial H n (u), which has as the coefficient of u k the expected number of nodes on this level, is studied. By convention, the root is at level 0.

The formula for the level polynomials

H n (u) = n k=1 n k (-1) k-1 (u) k-1 , n ≥ 1, H 0 (u) = 0,
appears already in Knuth's book (Knuth, 1973, p. 504), compare also (Mahmoud, 1992, Section 6).

Here, we use the (classic) notation (u) k := (1 -u)(1 -uq) . . . (1 -uq k-1 ); for applications to DSTs, we take q = 1 2 . We also need the infinite product (x) ∞ := (1 -x)(1 -xq) . . . . Guy [START_REF] Louchard | Exact and asymptotic distributions in digital and binarysearch trees[END_REF] gave explicit expressions for the coefficients of H n (u); see also (Mahmoud, 1992, Section 6). We write [u k ]H n (u) for the coefficient of u k in H n (u), and similarly for generating functions in 2 variables.

DSTs and Approximate Counting are very similar when it comes to analysis, see for instance [START_REF] Prodinger | Hypothetic analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet[END_REF]. In 2011, Cichon [START_REF] Cichoń | Approximate counters for flash memory[END_REF]) had a novel idea about Approximate Counting, by introducing an additional parameter m, see also [START_REF] Prodinger | Approximate counting with m counters: a detailed analysis[END_REF].

Translating this idea to the world of DSTs goes as follows: Instead of keeping one DST, we keep m DSTs, and an incoming data is attached to one of them. For algorithmic purposes (insertion and searching), this must be deterministic, but for the analysis we assume that a random DST is chosen with probability 1 m . The meaning of the level polynomial is then obvious: the coefficient of u k is the expected number of data on level k in all m DSTs combined.

Considering m-DSTs is equivalent (by adding an extra root) to the investigation of a tree structure with a prescribed root degree. This is not uncommon in Combinatorics and Computer Science; we just give one citation as an illustration: [START_REF] Kemp | The average height of r-tuply rooted planted plane trees[END_REF].

An explicit formula for the level polynomials

We start from the classic formula (derived e. g., in [START_REF] Prodinger | Digital search trees and basic hypergeometric functions[END_REF]) for the level polynomials for classical DSTs h n (u)

h n (u) = n k=1 n k (-1) k-1 (u) k-1
and note that h n (1) = n. Then the level polynomials H N (u) for the m-version satisfy

H N (u) = m -N n1+•••+nm=N N n 1 , . . . , n m h n1 (u) + • • • + h nm (u) ,
which is easy to see since a total of N data splits into n 1 , . . . , n m data each, building the m DSTs, and the individual level polynomials have to be added. The final explicit formula for the coefficients of H N (u) appears at the end of the following computations in Theorem 2.1. We can simplify:

H N (u) = m 1-N n1+•••+nm=N N n 1 , . . . , n m h n1 (u) = m 1-N N n=0 N n h n (u)(m -1) N -n = m 1-N N n=1 N n n k=1 n k (-1) k-1 (u) k-1 (m -1) N -n = m 1-N N k=1 N k (-1) k-1 (u) k-1 N n=k N -k n -k (m -1) N -n = N k=1 N k (-1) k-1 (u) k-1 m 1-k .
So the difference is just this extra factor m 1-k . Note again that for our DST application we have q = 1 2 , although the computations hold for general q.

Now we form a bivariate generating function:

H(u, x) = N ≥1 H N (u)x N = N ≥1 N k=1 N k (-1) k-1 (u) k-1 m 1-k x N = k≥1 N ≥k N k (-1) k-1 (u) k-1 m 1-k x N = k≥1 (-1) k-1 (u) k-1 m 1-k x k (1 -x) k+1 = x (1 -x) 2 k≥0 (-1) k (u) k m -k x k (1 -x) k = x (1 -x) 2 k≥0 (u) k z k with z = x m(x -1)
.

We need the classic transformation of Heine [START_REF] Andrews | The Theory of Partitions, volume 2 of Encyclopedia of Mathematics and its Applications[END_REF]:

n≥0 (a) n (b) n t n (q) n (c) n = (b) ∞ (at) ∞ (c) ∞ (t) ∞ n≥0 (c/b) n (t) n b n (q) n (at) n and the corollary n≥0 (y) n z n = (y) ∞ n≥0 y n (q) n (1 -zq n ) ,
which is obtained by setting a = q, b = y, c = 0, and t = z and noticing that

(qz) ∞ (z) ∞ = 1 1 -z and (z) n (qz) n = 1 -z 1 -zq n . Now we can continue: H(u, x) = x (1 -x) 2 (u) ∞ n≥0 u n (q) n (1 -zq n ) = x (1 -x) 2 (u) ∞ n≥0 u n (q) n (1 - x m(x-1) q n ) = x (1 -x) (u) ∞ n≥0 u n (q) n (1 -x + x m q n ) = m(u) ∞ n≥0 (u/q) n (q) n 1 1 -x - 1 1 -x(1 -q n m ) = m 1 (1 -x)(1 -u/q) -m(u) ∞ n≥0 (u/q) n (q) n 1 1 -x(1 -q n m )
.

We can read off coefficients:

[x N ]H(u, x) = m[x N ] 1 (1 -x)(1 -u/q) -m(u) ∞ [x N ] n≥0 (u/q) n (q) n 1 1 -x(1 -q n m ) = m 1 1 -u/q -m(u) ∞ n≥0 (u/q) n (q) n 1 - q n m N and further [x N u l ]H(u, x) = mq -l -m[u l ](u) ∞ n≥0 (u/q) n (q) n 1 - q n m N = mq -l -m l k=0 (1/q) k (q) k 1 - q k m N [u l-k ](u) ∞ = mq -l -m l k=0 q -k (q) k 1 - q k m N (-1) l-k q ( l-k 2 ) (q) l-k .
This is the explicit formula that we wanted to derive. In it, we used an expansion due to Euler:

(u) ∞ = n≥0 (-1) n u n q ( n 2 ) (q) n .
Theorem 2.1 The expected number of data on level l in an m-DST built from N random data is explicitly given by

mq -l -m l k=0 q -k (q) k 1 - q k m N (-1) l-k q ( l-k 2 ) (q) l-k
.

The instance m = 1 has been known before, see [START_REF] Louchard | Exact and asymptotic distributions in digital and binarysearch trees[END_REF]; [START_REF] Prodinger | Digital search trees and basic hypergeometric functions[END_REF]; [START_REF] Mahmoud | Evolution of Random Search Trees[END_REF].

Insertion cost

The quantity H N (u) N is the probability generating function of a random variable called insertion cost. While it is well studied in the classical instance, we will provide here average and variance for general (fixed) m, both, explicitly and asymptotically. (The impatient reader can already jump forward to Theorem 3.1 for the results.) We need

H N (1) = N k=2 N k (-1) k Q k-2 m 1-k , H N (1) = 2 N k=2 n k (-1) k-1 Q k-2 T k-2 m 1-k with T (k) := k j=1 1 2 j -1
. We use the notation

Q n = n k=1
(1 -2 -k ), common in Computer Science, as well as (q) n . Now we can engage into the asymptotics, using Rice's method. This method has been described in [START_REF] Flajolet | Mellin transforms and asymptotics: Finite differences and Rice's integrals[END_REF]:

An alternating sum can be written as a contour integral:

N k=2 N k (-1) k f (k) = 1 2πi C (-1) N N ! z(z -1) . . . (z -N ) f (z)dz.
Here, the positively oriented curve C enclosed the poles 2, 3, . . . , N , and no others. This formula follows from simple residue calculations. Note also that

(-1) N N ! z(z -1) . . . (z -N ) = - Γ(N + 1)Γ(-z) Γ(N + 1 -z) .
Extending the curve of integration, we encounter extra residues; in order to keep the formula correct, these residues must be subtracted. They give us the terms of the asymptotic expansion of interest. There is in all our examples a pole at z = 1, and it will give us the dominant contribution.

Neglecting tiny oscillations, we can write in a suggestive way:

N k=2 N k (-1) k f (k) ∼ Res z=1 Γ(N + 1)Γ(-z) Γ(N + 1 -z) f (z).
For the expected value, we use f (z) = (q) z-2 m 1-z , with (q) z := (q) ∞ (q z+1 ) ∞ .

For convenience, we use w = z -1, so that the expansions are around w = 0.

Just recently in our paper [START_REF] Prodinger | Approximate counting with m counters: a detailed analysis[END_REF] we used (with Q = 1 q = 2 and L = log Q = log 2)

Q w-1 = Q w 1 -2 -w ∼ 1 -Lαw + L 2 2 (α 2 + α + β)w 2 1 1 -2 -w ∼ 1 Lw + 1 2 -α + L 2 α 2 + β + 1 6 w.
Here,

α = j≥1 1 2 j -1 and β = j≥1 1 (2 j -1) 2 .
So we must consider (q) w-1 m -w Γ(N + 1)Γ(-w -1) Γ(N -w) ;

the residue can be computed by a computer:

N log 2 N -log 2 m + 1 2 -α + γ -1 L + O(1).
Now, we have traditionally

T z-2 = T w-1 = α - 1 2 w -1 - j≥1 1 2 j+w -1 ∼ - 1 Lw + 1 2 - Lw 12 + L(α + β)w.
For the second factorial moment we use

f (z) = -2Q z-2 T z-2 m 1-z , so that we have to expand -2(q) w-1 T w-1 m -w Γ(N + 1)Γ(-w -1) Γ(N -w)
around w = 0 and compute the residue, which we don't display in full:

N log 2 2 N + 2 log 2 N • γ -1 L -α -log 2 m + further terms .
When we compute the variance via

H N (1) N + H N (1) N - H N (1) N 2 ,
there are many cancellations. Altogether we summarize our results. Theorem 3.1 Expectation and variance of the parameter insertion cost in m-DSTs admit the asymptotic expansions

expectation ∼ log 2 N -log 2 m + 1 2 -α + γ -1 L + δ 1 (log 2 N ), variance ∼ π 2 6L 2 -α -β + 1 12 + 1 L 2 + δ 2 (log 2 N )
, where δ 1 (x) and δ 2 (x) are tiny fluctuating functions that we did not compute explicitly here.

The computation of the fluctuating functions is not difficult, and very similar computations have appeared in the relevant literature many times; here is an incomplete list of references: [START_REF] Kirschenhofer | Further results on digital search trees[END_REF]; [START_REF] Kirschenhofer | Approximate counting: An alternative approach[END_REF]; [START_REF] Flajolet | Mellin transforms and asymptotics: Finite differences and Rice's integrals[END_REF]. Note that the variance is (asymptotically) a constant (plus a tiny fluctuation) which does not depend on m; δ 1 (x) also does not depend on m. For m = 1, this result appeared already in [START_REF] Kirschenhofer | Further results on digital search trees[END_REF]; [START_REF] Szpankowski | A characterization of digital search trees from the successful search viewpoint[END_REF].

So, as far as the main terms in the asymptotics are concerned, the dependency on m of average and variance is very minor, and m-DSTs don't show any improved behaviour. But such a statement can only be made after some thorough analysis, which is, why we provided it here.