Eugene Curtin

Cubic Cayley graphs with small diameter

Keywords: Cayley graph, cubic graph, diameter, Pólya's Theorem, permutation group

In this paper we apply Pólya's Theorem to the problem of enumerating Cayley graphs on permutation groups up to isomorphisms induced by conjugacy in the symmetric group. We report the results of a search of all three-regular Cayley graphs on permutation groups of degree at most nine for small diameter graphs. We explore several methods of constructing covering graphs of these Cayley graphs. Examples of large graphs with small diameter are obtained.

Introduction

The (∆, D) problem asks for the largest value n such that a graph on n vertices exists with diameter D and maximum vertex degree ∆. The Moore bound for the diameter D of a graph with n vertices and maximum vertex degree ∆ ≥ 3 gives n ≤ 1 + ∆ + (∆ -1)∆ + (∆ -1) 2 ∆ + • • • + (∆ -1) D-1 ∆. Very few graphs satisfy equality in the Moore bound. The evaluation of n(∆, D), the largest integer such that a graph on n(∆, D) vertices with maximum vertex degree ∆ and diameter D exists, appears to be an intractable problem in general. Even the more modest goal of proving the existence of a family of graphs satisfying D ≤ log ∆-1 (n)+O(1) seems difficult in the case ∆ = 3. For random regular graphs D = log ∆-1 (n log n)+O(1), and similar results have been obtained for constructions with random components. For details see [START_REF] Bollobás | The diameter of a cycle plus a random matching[END_REF] and [START_REF] Bollobás | The diameter of random regular graphs[END_REF]. Jerrum and Skyum [START_REF] Jerrum | Families of fixed degree graphs for processor interconnection[END_REF] have obtained the best non-random constructive results known for an infinite family of cubic graphs. Their constructions yield graphs which satisfy approximately D = 1.47 log 2 n. Kantor [Kan92] has shown the existence of cubic Cayley graphs with diameter O(log n), however the constant c such that D ≤ c log 2 n implicit in his estimate is very large. In addition to the random graph results and the constructions of infinite families, there is much interest in the construction of specific large graphs with small diameters. For a table of the largest known graphs for ∆ ≤ 10 and D ≤ 10, see [START_REF]The degree-diameter problem for graphs[END_REF]. These graphs establish lower bounds for n(∆, D).

We examine all three-regular Cayley graphs on permutation groups of degree at most nine. While the graphs obtained with D ≤ 10 are not as large as those in the table, these Cayley graphs form the building block for constructing larger graphs which can easily be analyzed. By forming covering graphs of the Cayley graphs in various ways we obtain graphs of D ≤ 21 which give good lower bounds for n(3, D) for 11 ≤ D ≤ 21. Moreover several examples of bipartite graphs with low degree and diameter are obtained.

We consider only undirected graphs, so the generator set A of our Cayley graphs will have three elements, and A = A -1 where A -1 = {α -1 | α ∈ A}. We refer to such sets as Cayley sets. For three-regular graphs the Cayley sets will have the form A = {σ, σ -1 , τ} for some σ and τ where τ has order two and σ has order at least three, or A = {τ 1 , τ 2 , τ 3 } where τ i has order two for each i. If α ∈ S n let α β = β -1 αβ be the conjugate of α by β, and if A ⊂ S n let A β = {α β | α ∈ A}. If A and B are Cayley sets in S n and A β = B for some β ∈ S n , then the Cayley graphs generated by A and B are isomorphic. Isomorphism of Cayley graphs from non-conjugate Cayley sets is difficult to determine from the Cayley sets alone. Thus in searching three-regular Cayley graphs we first address the problem of enumerating the possible Cayley sets up to conjugation. Although we are primarily interested in the sets generating cubic graphs, we tackle this problem in the more general setting.

Enumeration of Cayley Sets up to Conjugacy

Any Cayley graph of vertex degree m has a generator set of the form

S = {σ 1 , . . . , σ k , σ -1 1 , . . . , σ -1 k , τ 1 , .
. . , τ l } where each σ i has order at least three, each τ j is an involution, and 2k + l = m. We will call such a set a Cayley set of type (k, l). Let X n be the set of equivalence classes in S n under the equivalence relation x ∼ = y if and only if x = y or x = y -1 . We will denote these equivalence classes by any appropriate representative. There is a one-to-one correspondence between Cayley sets of type (k, l) and the subsets of X n the form {σ 1 , . . . , σ k , τ 1 , . . . , τ l }. We will call these subsets of X n Cayley sets of type (k, l) also.

The action of S n on S n by conjugation induces an action of S n on X n . Enumerating the Cayley graphs of vertex degree m on S n up to isomorphisms induced by conjugation in S n is equivalent to enumerating the sets of type (k, l) in X n with 2k + l = m up to the action of S n by conjugation. To accomplish this we compute the cycle index of the action of S n by conjugation on X n . We first recall some notation and basic facts. We refer to [START_REF] Palmer | Enumeration under two representations of the wreath product[END_REF] for background on cycle indices and Pólya's Theorem.

If G is a permutation group acting on a set X with n elements and g ∈ G then the we denote the cycle type of g by the monomial m(g) = ∏ n 1 x c i i , where g has c i cycles of length i in its disjoint cycle decomposition. The cycle index of G is defined as Z(G) = 1 |G| ∑ g∈G m(g) and the cycle sum by ZS(G) = ∑ g∈G m(g). We use Z(G; w 1 , w 2 . . . , w n ) to denote Z(G) with w i substituted for x i for each i. We denote Z(G; x r , x 2r . . . , x nr ) by Z r (G).

Let P n be the set of partitions of n. We also denote the elements of P n by monomials ∏ n 1 x c i i where ∑ n 1 ic i = n. Let h(a) be the number of permutations on S n with cycle type a.

h( n ∏ i=1 x c i i ) = n! ∏ n i=1 c i ! i c i and Z(S n ) = 1 n! ∑ a∈P n h(a) a. ( 1
)
Let C n and D n be the cyclic and dihedral groups of degree n. Then regarding C n and D n as permutation groups on {1, 2, . . . , n} in the usual manner we have

Z(C n ) = 1 n ∑ d|n φ(d) x n/d d (2)
and

Z(D n ) = 1 2 Z(C n ) + 1 2 x 1 x (n-1)/2 2 if n is odd 1 4 (x n/2 2 + x 2 1 x (n-2)/2 2 ) if n is even (3)
where φ denotes the Euler Phi function.

For each permutation α ∈ S n we will need the cycle index of the centralizer C(α) = {β ∈ S n |α β = α} and the cycle index of the pseudo-centralizer PC(α) = C(α) ∪ F(α), where F(α) = {β ∈ S n |α β = α -1 }. Since these cycle indices will depend only on the cycle type m(α) we will sometimes use the notations

Z(C(m(α))) and Z(PC(m(α))). If α is a permutation of cycle type x j k in S k j then C(α) ∼ = S k [C j ],
the wreath product of S k with C j . Pólya [START_REF] Pólya | Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen[END_REF] showed that cycle index of the wreath product

A[B] is given by Z(A[B]) = Z(A; Z 1 (B), Z 2 (B), . . .) and thus Z(C(α)) = Z(C(x k j )) = Z(S k ; Z 1 (C j ), Z 2 (C j ), . . .). (4)
The centralizer of a permutation α of cycle type ∏ n 1 x c i i is isomorphic to the product of the centralizers of permutations α i of type x c i i in S ic i , hence

Z(C( n ∏ i=1 x c i i )) = n ∏ i=1 Z(S c i ; Z 1 (C i ), Z 2 (C i ), . . .). (5)
To obtain the cycle index of the pseudo-centralizer PC(α), we need to consider separately the set F(α).

Let F n = D n -C n for n ≥ 3 and F n = C n for n ≤ 2.
We identify F n with the set of permutations in S n mapping an n-cycle to its inverse under conjugation. Although F n is not a group for n ≥ 3 we may consider its cycle index, and

Z(F n ) = Z(C n ) for n ≤ 2 and Z(F n ) = 2Z(D n ) -Z(C n ) for n ≥ 3.
By equations 2 and 3 we obtain explicitly that

Z(F n ) = x 1 x (n-1)/2 2 if n is odd 1 2 (x n/2 2 + x 2 1 x (n-2)/2 2 ) if n is even. (6)
Now consider F(α) where α ∈ S k j has cycle type x k j . Denote the cycle-index of F(α) by Z(F(x k j )) as it depends only on the cycle type. Note that if g ∈ F(α) then g determines a permutation γ(g) ∈ S k of the k j-cycles w 1 , w 2 , . . . , w k of α. If (w t 1 , w t 2 , . . . , w t r ) is in an r-cycle of γ(g) then g r determines a permutation of the elements of each w t s . Thus g r determines an element of F j (r odd) or C j (r even) when we consider its action on the elements of w t 1 . Each l cycle of F j or C j determined by g r determines an rl cycle of g. Moreover there are j r-1 possible permutations of the r j elements of the r j-cycles w t 1 , w t 2 , . . . , w t r determining the same r-cycle (w t 1 , w t 2 , . . . , w t r ) and β in F j or C j . Therefore the contribution of each x r in the cycle-sum ZS(S k ) to the cycle sum ZS(F(x j k )) is given by j r-1 ZS r (F j ) = j r Z r (F j ) (r odd) or j r-1 ZS r (C j ) = j r Z r (C j ) (r even). Thus ZS(F(x j k )) = ZS(S k ; jZ 1 (F j ), j 2 Z 2 (C j ), j 3 Z 2 (F j ), j 4 Z 4 (C j ), . . .), and dividing both sides by j k k! yields

Z(F(x j k )) = Z(S k ; Z 1 (F j ), Z 2 (C j ), Z 3 (F j ), Z 4 (C j ), . . .). (7)
Now if α has cycle type ∏ n 1 x c i i , there is an isomorphism between ∏ n 1 PC(α i ) and a subgroup of S n mapping the product

∏ n 1 F(α i ) to F(α), where α i ∈ S ic i has type x c i i . This gives Z(F(∏ n 1 x c i i )) = ∏ n 1 Z(F(x c i i )
), so by 5 and 7 we obtain the cycle index of the pseudo-centralizer:

Z(PC( n ∏ i=1 x c i i )) = 1 2 n ∏ i=1 Z(S c i ; Z 1 (C i ), Z 2 (C i ), . . .) + 1 2 n ∏ i=1 Z(S c i ; Z 1 (F i ), Z 2 (C i ), Z 3 (F i ), Z 4 (C i ), . . .). ( 8
)
If G is any subgroup of S n and b is a cycle type, we use G.b to denote G regarded as a permutation group acting on the elements of X n of cycle type b by conjugation. We will identify a cycle type b with the set of permutations in S n having that cycle type. Recall from equation 1 that h(b) is the number of permutations in S n with cycle type b. We use o(β) for the order of a permutation β ∈ S n , and as this depends only on cycle type we use o(b) for the order of any element of cycle type b. We use

[t]Q to denote the coefficient of a monomial t in a polynomial Q. Also if α has cycle type a = ∏ n 1 x c i i then the cycle type of α d is given by ∏ n 1 x c i (i,d) i/(i,d)
, where (i, d) is the greatest common divisor of i and d. We may denote this cycle type as a d , as it depends only on a and d. We denote the Möbius function by µ. With these preliminaries, we are now in a position to calculate the cycle index of the action of S n by conjugation on X n .

Enumeration Theorem:

Z(G.b) = 1 |G| ∑ g∈G ∏ k|o(g) x c(m(g),k,b) k where c(a, k, b) = 1 k ∑ d|k µ(k/d) w(a d , b), and w(a, b) = n! h(a)
[a]Z(PC(b)).

Proof: . Therefore given

If α 1 ∈ S n and b is a cycle-type, let f (α 1 , b) = |{β ∈ b|β α 1 = β or β -1 }|. Now f (α 1 , b) depends only on the cycle type a of α 1 , thus for any β 1 ∈ b h(a) f (α 1 , b) = |{(α, β) ∈ a × b|β α = β or β -1 }| = |{(α, β) ∈ a × b|α ∈ PC(β)}| = h(b) |a ∩ PC(β 1 )| = h(b) [a]ZS(PC(β 1 )). (9)
Z(G) = 1 |G| ∑ g∈G m(g) we obtain Z(G.b) = 1 |G| ∑ g∈G ∏ k|o(g) x c(m(g),k,b) k (12)
as claimed.✷

In considering the cycle index of the action of subgroups of S n on X n by conjugation we use a different set of variables for each transitivity set b. We let x (b,i) denote an i-cycle of elements of type b, so that now

m(a, b) = ∏ k|o(a) x c(a,k,b) (b,k) , and m(a, X n ) = ∏ b∈P n m(a, b
) is the monomial of the action of a permutation of cycle type a on X n . Now if G is any subgroup of S n we obtain the cycle-index Z(G.X n ) for the action of G on X n by conjugation by replacing each monomial a by m(a, X n ). In particular for G = S n we obtain Z(S n .X n ) = 1 n! ∑ a∈P n h(a) m(a, X n ). Let F n (x, y) be the polynomial obtained from Z(S n .X n ) by substituting (1 + x i ), (1 + y i ) or 1 for each x (b,i) according to whenever o(b) ≥ 3, o(b) = 2 or o(b) = 1. By Pólya's Theorem the coefficient of x k y l in F n (x, y) will give the number of inequivalent (k, l) subsets of X n . Thus these polynomials are the generating functions for the number of (k, l) subsets of X n . We give the terms of F n (x, y) in Table 1 below up to O(y 7 ) for 3 ≤ n ≤ 10, considering x as O(y 2 ). We have investigated the three-regular Cayley graphs on subgroups of S 9 . We see from F 9 (x, y) that there are 2641 of these with generating set of type (1,1) and 12022 of type (0,3) for a total of 14,663 Cayley sets. When generating a complete list of 14,663 inequivalent Cayley sets it is desirable to know how many there are with each possible set of cycle-types for the generators. This information is contained in the polynomial Z(S n .X n ). For example the substitution of (1 + y i ) for x (x 3 1 x 3 2 ,i) , (1 + z i ) for x (x 1 x 4 2 ,i) and 1 for every other variable in Z(S 9 .X 9 ) enables us to read the number of inequivalent Cayley sets with three generators of type x 3 1 x 3 2 or x 1 x 4 2 in S 9 . Alternatively we could use the above techniques to compute the action of C(α) on the set of permutations of types x 3 1 x 3 2 or x 1 x 4 2 in X 9 by conjugation, where α has type x 3 1 x 3 2 .

One further approach to enumeration of the Cayley sets with a specified set of cycle types for the generators is worthy of note. Let us consider the case of counting the number of Cayley sets in S 9 with three permutations of type x 1 x 4 2 . The type x 1 x 4 2 may be identified with an unlabeled graph Γ on 9 points with 4 disjoint edges. Any permutation α of type x 1 x 4 2 may be identified with a labeling of the graph Γ with numbers {1, 2, . . . , 9}. Equivalence up to relabeling in the graph context corresponds to equivalence up to conjugation with permutations. The number of unlabeled superpositions of n differently colored copies of Γ gives the number of inequivalent ordered n-tuples of permutations of type x 1 x 4 2 . If we regard the colors as interchangeable then the number of unlabeled superpositions of n differently colored copies of Γ gives the number of inequivalent n-multisets of permutations of type x 1 x 4 2 . We wish to count the number of three-sets. The three-multisets which do not have three distinct elements are in one-to-one correspondence with ordered pairs. Palmer and Robertson [START_REF] Palmer | Enumeration under two representations of the wreath product[END_REF] show how to count superpositions of colored graphs. Their techniques cover the cases of interchangeable and non-interchangeable colors. There are 548 superpositions of three differently colored copies of Γ where the colors are interchangeable, and 12 superpositions of two copies of Γ where the colors are not interchangeable. Therefore we obtain 548 -12 = 536 inequivalent Cayley sets with three permutations of type x 1 x 4 2 in S 9 . The graph analogy needs some modification for permutations which are not involutions, however the same technique remains applicable.

Table 1: Generating Functions for Number of (k,l)-Subsets of X n .

F 3 (x, y) = 1 + x + y + x y + y 2 + x y 2 + y 3 + x y 3 F 4 (x, y) = 1 + 2 x + 3 x 2 + 5 x 3 + 2 y + 7 x y + 15 x 2 y + 5 y 2 + 20 x y 2 + 47 x 2 y 2 + 10 y 3 + 41 x y 3 +12 y 4 + 56 x y 4 + 12 y 5 + 10 y 6 + O(y 7 ) F 5 (x, y) = 1 + 4 x + 26 x 2 + 215 x 3 + 2 y + 24 x y + 315 x 2 y + 8 y 2 + 173 x y 2 + 3070 x 2 y 2 + 37 y 3 +1077 x y 3 + 149 y 4 + 5404 x y 4 + 535 y 5 + 1658 y 6 + O(y 7 ) F 6 (x, y) = 1 + 7 x + 166 x 2 + 9090 x 3 + 3 y + 95 x y + 6682 x 2 y + 20 y 2 + 1781 x y 2 + 211359 x 2 y 2 +197 y 3 + 33957 x y 3 + 2245 y 4 + 564974 x y 4 + 26616 y 5 + 290929 y 6 + O(y 7 ) F 7 (x, y) = 1 + 11 x + 1011 x 2 + 480924 x 3 + 3 y + 267 x y + 143355 x 2 y + 29 y 2 + 15316 x y 2 +15432773 x 2 y 2 + 676 y 3 + 1004405 x y 3 + 25948 y 4 + 55582020 x y 4 +1071459 y 5 + 39494992 y 6 + O(y 7 ) F 8 (x, y) = 1 + 17 x + 7032 x 2 + 32374554 x 3 + 4 y + 909 x y + 3841393 x 2 y + 60 y 2 + 163651 x y 2 +1416913393 x 2 y 2 + 3094 y 3 + 36907736 x y 3 + 380762 y 4 + 6895794512 x y 4 +53589180 y 5 + 6683796440 y 6 + O(y 7 ) F 9 (x, y) = 1 + 25 x + 54952 x 2 + 2692273145 x 3 + 4 y + 2641 x y + 118640929 x 2 y + 83 y 2 + 1825707 x y 2 +153502228335 x 2 y 2 + 12022 y 3 + 1497261258 x y 3 + 5667310 y 4 +972152058485 x y 4 + 2840588522 y 5 + 1229693537151 y 6 + O(y 7 ) F 10 (x, y) = 1 + 36 x + 505742 x 2 + 272445118869 x 3 + 5 y + 8969 x y + 4311730098 x 2 y + 151 y 2 +23565356 x y 2 + 20353301123666 x 2 y 2 + 55912 y 3 + 71501074475 x y 3 + 96948583 y 4 +168911533776760 x y 4 + 177992264581 y 5 + 280252256218298 y 6 + O(y 7 )

3 Graphs of Small Diameter.

We refer to a Cayley graph with generator set of type (0, 3) or type (1, 1) in X 9 as a G(3, 9) graph. We examined every possible generating set for G(3, 9) up to equivalence under conjugation, using the enumeration results as a check on the correctness of the lists obtained. We performed an exhaustive examination of these graphs and tabulated below examples of graphs of diameter D such that no larger G(3, 9) graph of diameter D exists. For most values of D the largest G(3, 9) graph of diameter D is not unique, and for each such D we have selected one example rather that listing them all. While the G(3, 9) graphs do not yield any new lower bounds for n(3, D) with D ≤ 10, it is natural to explore further with the examples which have relatively low diameter. Given a generator set {σ 1 , τ 1 } for a G(3, 9) we may consider generator sets {σ 1 σ 2 , τ 1 τ 2 } where σ 2 and τ 2 are permutations fixing {1, 2, . . . , 9}, and τ 2 has order at most 2. The resulting graph will be a covering graph of the original graph. Taking σ 2 to be a k-cycle and τ 2 to be the identity yields a d-fold cover of the initial graph for some d dividing k.

There are many examples where this leads to a larger graph with little or no corresponding increase in the diameter. Taking σ 2 = τ 2 = (n + 1 n + 2) yields a bipartite double cover of the initial graph, assuming it was not bipartite to begin with. The girth calculations were performed by comparing the sequence of sphere sizes about the identity in the initial graph and comparing it to the corresponding sequence for the bipartite double cover. We also pursued taking combinations {σ 1 σ 2 , τ 1 τ 2 } where both {σ 1 , τ 1 } and {σ 2 , τ 2 } generated low diameter graphs. Likewise we investigated covering graphs of G(3, 9) graphs with generating sets {τ 1 , τ 2 , τ 3 } where each τ i is an involution for 1 ≤ i ≤ 3 by graphs with generating sets {τ 1 τ 4 , τ 2 τ 5 , τ 3 τ 6 }, where each τ j is an involution or the identity for 4 ≤ j ≤ 6. The best examples obtained are in Table 3 below. We include only examples which improve over the degree nine results.

Delorme [START_REF] Delorme | Large bipartite graphs with given degree and diameter[END_REF] defines b(∆, D) as the largest integer such that a bipartite graph on b(∆, D) vertices with maximum vertex degree ∆ and diameter D exists. The diameter 7 graph on 168 vertices and the diameter 12 graph on 2160 vertices in Table 3 are bipartite. Other large bipartite graphs found include a diameter 10 graph on 672 vertices of girth 8 and generator set {(1 2)(3 4)(5 6)(9 10), (1 3)(5 7)(6 8)(9 10), (1 4)(2 5)(3 8)(6 7)(9 10)} and a diameter 9 graph on 360 vertices with girth 10 and generator set {(1 2), (2 6 7 8)(3 4 5)}. The resulting bounds b(3, 9) ≥ 360 and b(3, 10) ≥ 672 match those obtained in [START_REF] Bond | New large bipartite graphs with given degree and diameter[END_REF], and the bound b(3, 7) ≥ 168 improves the bound given there. However the cubic symmetric graphs F364E and F720C of the Foster Census [START_REF] Royle | Cubic symmetric graphs (The Foster census)[END_REF] improve these bounds to b(3, 9) ≥ 364 and b(3, 10) ≥ 720. The Foster Census includes a complete listing of the cubic symmetric graphs of up to 768 vertices, so all of our smaller graphs have isomorphic copies on this list. None of the examples supersede the records for the smallest cubic graphs of given girth. The most notable example for girth was the bipartite graph with generator set {(1 2)(3 4)(5 6), (1 3 2 5 4 6 7 8)(9 10 11)}, which has 1008 points, diameter 12 and girth 16. The smallest known graph of girth 16 has 990 points. See [START_REF] Biggs | Constructions for cubic graphs with large girth[END_REF] for a survey of girth results. In Tables 2 and 3 below diameter is denoted by D, the order of the graph by n, and the girth by g. We indicate in the b column whether or not each graph is bipartite.

The calculations pertaining to this paper were performed using Mathematica [START_REF] Wolfram | The Mathematica Book[END_REF]. Searches of the GAP [START_REF]GAP-Groups, Algorithms, and Programming[END_REF] small group and transitive permutation group libraries did not yield any larger cubic graphs of given diameter. However we emphasize that these searches were not exhaustive.

  Now let w(α, b) denote the number of elements of X n of cycle type b fixed under conjugation by α. If o(b) ≤ 2 then w(α, b) = f (α, b) and |PC(β 1 )| = |C(β 1 )| = n!/h(b) for any β 1 of type b. If o(b) ≥ 3 then w(α, b) = (1/2) f (α, b) and |PC(β 1 )| = 2|C(β 1 )| = 2(n!)/h(b) for any β 1 of cycle type b. In either case substitution into equation 9 yields w(α, b) = n! h(a) [a]Z(PC(b)). (10) Note that w(α, b) depends only on the cycle type a of α, so we define w(a, b) by equation 10 for cycletypes a and b. If c(a, k, b) is the number of k-cycles of the action of any α of cycle type a by conjugation on the elements of X n of cycle type b, thenw(α k , b) = w(a k , b) = ∑ d|k d c(a, d, b) and c(a, k, b) = 1 k ∑ d|k µ(k/d) w(a d , b)) (11)The terms on the right hand side of equation 11 can therefore be evaluated using equations 8 and 10. Thus we obtain the monomial m(a, b) for the action of any α of cycle type a by conjugation on b by m(a, b) = ∏ k|o(a) x c(a,k,b) k

  2)(3 4)(5 6)(7 8), (1 3)(2 9)(5 7), (1 9)(5 8)} 14 5040 10 n {(1 2)(3 4), (1 3)(2 5), (1 4)(2 6)(3 7)} 15 10080 12 n {(1 2)(3 4)(5 6)(7 8), (1 2)(3 4)(5 9), (1 7)(2 9)(5 8)} 16 10080 10 y {(1 2)(3 4)(5 6)(7 8), (1 2)(3 4)(5 7)(6 9), (1 2)(3 6)(5

Table 2 . Largest G(3, 9) Graphs of Given Diameter.

 2

	D	n	g	b	Generators
	1	4	3	n	{(1 2), (3 4), (1 2)(3 4)}
	2	8	4	n	{(1 3 5 7 2 4 6 8), (1 2)(3 4)(5 6)(7 8)}
	3	14	6	y	{(1 2)(3 4)(5 6), (13 )(2 5)(4 7), (1 4)(3 6)(5 7)}
	4	24	6	y	{(1 2), (1 3), (1 4)}
	5	60	9	n	{(1 2)(3 4), (2 3 4 8)(5 6 7)}
	6	72	8	n	{(1 2), (1 3)(4 5), (1 4)(2 5)(3 6)}
	7	144	8	y	{(1 2 3 4 5 6 7 8), (1 2)(3 6)(4 9)}
	8	240	12	n	{(1 2), (1 3)(4 5), (2 4)(6 7)}
	9	504	12	n	{(1 2)(3 4)(5 6)(7 8),


Nir Namman

Raphael Rom
email: rom@ee.technion.ac.il

Analysis of Transmission Scheduling with Packet Fragmentation

Keywords: scheduling, bin packing, fragmentation, CATV, algorithm, average case analysis

We investigate a scheduling problem in which packets, or datagrams, may be fragmented. While there are a few applications to scheduling with datagram fragmentation, our model of the problem is derived from a scheduling problem present in data over CATV networks. In the scheduling problem, datagrams of variable lengths must be assigned (packed) into fixed length time slots. One of the capabilities of the system is the ability to break a datagram into several fragments. When a datagram is fragmented, extra bits are added to the original datagram to enable the reassembly of all the fragments.

We convert the scheduling problem into the problem of bin packing with item fragmentation, which we define in the following way: we are asked to pack a list of items into a minimum number of unit capacity bins, each item may be fragmented in which case overhead units are added to the size of every fragment. The cost associated with fragmentation renders the problem NP-hard; therefore, an approximation algorithm is needed. We define a version of the well-known Next-Fit algorithm, capable of fragmenting items, and investigate its performance. We present both worst case and average case results and compare them to the case where fragmentation is not allowed.

Introduction

We address the class of transmission scheduling problems in which packets of variable lengths must be assigned into fixed length time slots (see e.g., [START_REF] Coffman | Stochastic analysis of a slotted FIFO communication channel[END_REF]). Our model of the problem is derived from a scheduling problem present in data over CATV (Community Antenna Television) networks. In particular we refer to Data-Over-Cable Service Interface Specification (DOCSIS), standard of the Multimedia Cable Network System (MCNS) standard committee (see [START_REF]Data-Over-Cable Service Interface Specifications -Radio Frequency Interface Specification (status: interim)[END_REF] for a detailed description). When using CATV networks for data communication the data subscribers are connected via a cable modem to the headend. The headend is responsible for the scheduling of all transmissions in the upstream direction (from the cable modem to the headend). Scheduling is done by dividing the upstream, in time, into a stream of numbered mini-slots. The headend receives requests from the modems for allocation of datagram transmission. The length of each datagram can vary and may require a different number of mini-slots. From time to time, the headend 1365-8050 c 2001 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France publishes a MAP in which it allocates mini-slots to one modem or a group of modems. The scheduling problem is that of allocating the mini-slots to be published in the MAP, or in other words, how to order the datagram transmission in the best possible way.

The headend must consider two kinds of datagram allocations:

1. Fixed Location -allocations for connections with timing demands, such as a CBR (constant bit rate) connection. These connections must be scheduled so as to ensure delivering the guaranteed service. Fixed location datagrams are therefore scheduled in fixed, periodically located mini-slots.

2. Free Location -allocations for connections without timing demands, such as a best effort connection. Free location datagrams can use any of the mini-slots.

The headend therefore performs the allocation in two stages. In the first stage it schedules, or allocates, all fixed location datagrams. We assume that after the fixed allocations have been made, a gap of U mini-slots is left between successive fixed allocations. In the second stage all free location datagrams are scheduled. The free allocations must fit into the gaps left by the fixed allocations. One of the capabilities of the system is the ability to break a datagram into smaller pieces called fragments. When a datagram is fragmented, i.e., transmitted over non successive mini-slots, extra bits are added to the original datagram to enable the reassembly of all the fragments at the headend. In a typical CATV network one mini-slot is added to every fragment.

We model the scheduling problem as a bin packing problem. The relation to the bin packing problem should be clear. The items are the free location datagrams that should be scheduled, each of which may require a different number of mini-slots. The bins are defined by the gaps between every two successive fixed allocations in the MAP. The goal is to use the available mini-slots in the MAP in the best way.

Because of its applicability to a large number of applications and because of its theoretical interest bin packing has been widely researched and investigated (see, e.g., [START_REF] Friesen | Analysis of a compound bin packing algorithm[END_REF], [START_REF] Johnson | Worst-case performance bounds for simple one-dimensional packing algorithms[END_REF] and [START_REF] Coffman | Approximation algorithms for bin packing: A survey[END_REF] for a comprehensive survey). Since the problem, as many of its derivatives, is NP-hard [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] many approximation algorithms have been developed for it (see, e.g., [START_REF] Johnson | Fast algorithms for bin packing[END_REF], [START_REF] Karmarkar | An efficient approximation scheme for the one-dimensional bin packing problem[END_REF] and [START_REF] Coffman | Approximation algorithms for binpacking: An updated survey[END_REF] for a survey). To analyze the scheduling problem we introduce a new variant of bin packing which we call bin packing with item fragmentation. We convert the scheduling problem into the problem of bin packing with item fragmentation and show that the two are strongly related. The subject of item fragmentation in bin packing problems has received almost no attention so far. This paper concentrates on aspects that were heretofore never researched, such as developing an algorithm for the problem and investigating its performance.

The cost associated with fragmentation renders the bin packing problem nontrivial. In the scheduling problem, where items correspond to datagrams, the cost is due to the extra overhead bits that are added to each fragment for reassembly purposes. Other fragmentation costs can be those resulting from processing time or reassembly delay. It is interesting to note that when the cost associated with fragmentation is ignored the packing problem becomes trivial, and when the cost is very high, it does not pay to fragment items and we face the classical bin packing problem. Hence, the problem is interesting with the middlerange costs. It has been shown in [START_REF] Mandal | Complexity of fragmentable object bin packing and an application[END_REF] that for non zero cost, the problem of bin packing with item fragmentation is NP-hard.

We present an analysis of the Next-Fit (NF) algorithm, which is perhaps the simplest algorithm for bin packing. The algorithm keeps only one open bin and packs items according to their order, into the open bin. When an item does not fit in the open bin, the bin is closed and a new bin is opened. The NF algorithm is very simple, can be implemented to run in linear time, and requires only one open bin (bounded space).

It is therefore interesting to investigate the performance of such an algorithm before considering other, more complicated, algorithms.

We point out that the practical scheduling problem may actually be somewhat more complicated than the problem we present here since the bins may not be of uniform size. This situation is likely to happen for example when the fixed location allocations are a result of several CBR connections with different intervals between successive allocations. In such cases we may also face a situation where some items are bigger than some of the bins. While the problem of variable size bins is beyond the scope of this paper, we do mention some results we obtained while analyzing this case. The analysis of variable size bins, as well as the analysis of algorithms other than NF, appears in [START_REF] Menakerman | Bin packing problems with item fragmentation[END_REF].

Our work contains several contributions. We introduce the variant of bin packing with item fragmentation and relate it to scheduling problems where datagrams may be fragmented. Our analysis of the scheduling algorithm contributes new results to the literature of bin packing. Finally, we developed a new technique for average case analysis which has some important advantages over existing techniques.

The remainder of the paper is organized as follows. In Section 2 we formally define the problem. Section 3 presents worst case analysis of the scheduling algorithm. Section 4 is devoted to average case analysis.

Problem Statement and Definitions

In this section we formally define the problem of bin packing with item fragmentation and show its relation to the scheduling problem. We define the problem similar to the classical bin packing problem. In the classical one-dimensional bin packing problem, we are given a list of items L = (a 1 , a 2 , ..., a n ), each with a size s(a i ) ∈ (0, 1] and are asked to pack them into a minimum number of unit capacity bins. To handle fragmentation, we use a discrete version of the problem and add a fragmentation cost function that adds overhead bits to each fragment. We proceed to formally define the problem.

Bin Packing with Item Fragmentation (BP-IF):

We are given a list of n items L = (a 1 , a 2 , ..., a n ), each with a size s(a i ) ∈ {1, 2, ...,U}. The items must be packed into a minimum number of bins, which are all the size of U units. When packing a fragment of an item, one unit of overhead is added to the size of every fragment.

The analysis of bin packing algorithms is traditionally divided into worst case analysis and average case analysis. In worst case analysis we are usually interested in the asymptotic worst case performance ratio. For a given list of items, L and algorithm A, let A(L) be the number of bins used when algorithm A is applied to list L, let OPT (L) denote the optimum number of bins for a packing of L, and let R A (L) ≡

A(L)/OPT (L). The asymptotic worst case performance ratio R ∞

A is defined to be

R ∞ A ≡ inf{r ≥ 1 : for some N > 0, R A (L) ≤ r for all L with OPT (L) ≥ N} (1)
A different approach for estimating the performance of an algorithm is an average case analysis. In this case we assume that item sizes are taken from a given distribution H and we try to estimate the performance ratio of an algorithm, when it is applied to a list taken from that distribution. For a given algorithm A and a list of n items L n , generated according to distribution H, the asymptotic expected performance ratio is defined as follows:

R ∞ A (H) ≡ lim n→∞ E [R A (L n )] = lim n→∞ E A(L n ) OPT (L n ) (2)
Schedule Efficiency: To evaluate the performance of a scheduling algorithm A, we compare the channel utilization achieved by A to that of the best possible schedule. Let s(L) denote the total sum of all item sizes in L, the channel utilization of algorithm A is C A (L) = s(L) A(L)•U . The worst case schedule efficiency, which we denote by η A , is exactly the inverse of the worst case performance ratio of A

η A (L) = s(L)/(A(L) •U) s(L)/(OPT (L) •U) = (R A (L)) -1 (3) η ∞ A = (R ∞ A ) -1
The expected schedule efficiency is the inverse of the expected performance ratio of A:

η ∞ A = (R ∞ A ) -1
. In this paper we analyze the performance of the Next-Fit algorithm. We denote by NF f the version of NF capable of fragmenting items and define the NF f algorithm similarly to NF.

Algorithm In the reminder of this paper we concentrate on the bin packing problem. We calculate both the worst case and the expected asymptotic performance ratio of the NF f algorithm and compare it to known results about the NF algorithm. The schedule efficiency of the algorithms is easily derived from the performance ratio using (3).

Worst Case Analysis

The NF algorithm is the least efficient among all standard bin packing algorithms. The asymptotic worst case performance ratio of the algorithm is the worst possible

R ∞ NF = 2U U + 1 , for every U ≥ 2. ( 4
)
We now analyze the performance of the NF f algorithm for the problem of bin packing with item fragmentation. As we shell see, the ability to fragment items may considerably improve the performance of the NF algorithm.

Theorem 1 The asymptotic worst case performance ratio of algorithm NF

f is R ∞ NF f = U U-2 , for every U ≥ 6.
Proof : We first prove the upper bound and then provide an example to establish the lower bound.

Claim 3.1 R ∞ NF f ≤ U U-2
, for every U > 2. Proof : The NF f algorithm may pack at most two fragments in each bin (one fragment when the bin is opened and another when the bin is closed). There are therefore at most 2 overhead units in a bin which means that the number of bins used when the algorithm is applied to list L is at most ⌈s(L)/(U -2)⌉. The optimal packing of L requires at least ⌈s(L)/U⌉ bins and the claim follows.

✷ Claim 3.2 R ∞ NF f ≥ U U-2
, for every U ≥ 6. Proof : We present an example that proves the lower bound. Let us first consider the case where the bin size U is an even number. As a worst case example we choose the following list L: The first item is of size U/2, the next U 2 -2 items are of size 1. The rest of the list repeats this pattern kU times. The optimal packing avoids fragmentations by packing bins with two items of size U/2, or U items of size 1. The total number of bins used is OPT (L) = (U -2)k. On the other hand, algorithm NF f fragments each item of size U/2 (except for the first item). Overall 2(kU -1) units of overhead are added to the packing and the number of bins used by NF f is therefore

NF f (L) = U 2 k + 2 kU -1 U + U 2 -2 k = Uk - 2 U = Uk.
A worst case example for the case where U is an odd number is similar. The first item in L is of size (U -1)/2, the next U-1 2 -1 items are of size 1. The rest of the list repeats this pattern kU times. It is easy to verify that this list produces the same ratio. It follows from the examples that:

R ∞ NF f = NF f (L) OPT (L) ≥ U U-2 , U ≥ 6.
✷

The combination of the above claims proves the theorem. ✷

There is a considerable difference between the worst case performance ratios of NF and NF f . Since both algorithms work in a similar way, we conclude that the improved performance ratio of NF f is due to its ability to fragment items. Note that the performance ratio of any algorithm that adopts the simple rule of filling a bin whenever an item is fragmented, cannot be worse than that of NF f . Finally, we point out a few more properties of the worst case performance ratio of the NF f algorithm. The results are taken from [START_REF] Menakerman | Bin packing problems with item fragmentation[END_REF] and we present them here without a proof.

• When the bin size is very small Theorem 1 does not hold (because items of size 2 are not fragmented). For the values 3 ≤ U ≤ 5 we show that the worst case asymptotic performance ratio of

NF f is R ∞ NF f = 3 2 .
• For a more general case, where r (instead of 1) units of overhead are added to the size of every fragment, it can be shown by similar arguments that R ∞ NF f = U U-2r , for every U > 4r + 2.

• As we mentioned, in the scheduling problem the bins may be of different sizes. We denote by U the average bin size and show that for the case of variable size bins the worst case performance ratio of

NF f is R ∞ NF f = U U-2
, for every U ≥ 5. • The worst case results do not change if we allow the items to be of any size, that is, we assume that the size of some items may be larger than the size of some (or all) of the bins.

Average Case Analysis

The worst case analysis we presented, provides an upper bound on the performance ratio of the NF f algorithm. However, from a practical point of view it may be too pessimistic, since the worst case may rarely occur. To learn about the typical behavior of the algorithm we present an average case analysis.

Since the results of an average case analysis depend on the item-size distribution, it is desirable to be able to calculate results for any given distribution. We therefore consider some general item-size distribution assuming only that the items are independent, identically distributed (i.i.d). Let us define the problem in a formal way.

Average case analysis of BP-IF:

We are give a list of n items L = (a 1 , a 2 , ..., a n ). The size of each item is independently chosen from the finite set s(a t ) ∈ {1, 2, ...,U}. The probability to choose an item of size i is h i , i.e., for all t: h i = Pr(s(a t ) = i). The goal is to pack the items into a minimum number of bins of equal size U. When packing a fragment of an item, one unit of overhead is added to the size of every fragment.

The first average case analysis of the NF algorithm was done by Coffman, So, Hofri and Yao [START_REF] Coffman | A Stochastic model of bin packing[END_REF] who showed that the asymptotic expected performance ratio for continuous uniform distribution is R ∞ NF = 4 3 . For discrete uniform distribution, in the range s(a t ) ∈ {1, 2, ...,U}, it has been shown in [START_REF] Coffman | Stochastic analysis of a slotted FIFO communication channel[END_REF] that the NF algorithm has the following asymptotic expected performance ratio:

R ∞ NF = 2(2U + 1) 3(U + 1) . ( 5
)
Note that the result for the continuous uniform distribution is reached when U → ∞.

The above mentioned results were achieved by using different techniques, all of which are fairly complicated (see, for example [START_REF] Coffman | A Stochastic model of bin packing[END_REF], [START_REF] Hofri | A Probabilistic analysis of the Next-Fit bin packing algorithm[END_REF] and [START_REF] Karmarkar | Probabilistic analysis of some bin packing algorithms[END_REF]). We present here, what we believe to be a much easier method of calculating the asymptotic expected performance ratio. We first use this method to repeat the analysis of the NF algorithm. We next apply it to the new problem of bin packing with item fragmentation, to find the expected performance ratio of the NF f algorithm.

Average Case Analysis of the NF Algorithm

We use a Markov chain to describe the packing of the algorithm. The state of the algorithm, which we denote by N t , is the content of the open bin after t items were packed. Since the bin size is U and there are n items to pack, the possible states of the algorithm are 1 ≤ N t ≤ U, 1 ≤ t ≤ n. The probability distribution for N t+1 is completely determined by the value of N t , which renders the process a Markov chain. We consider only the cases where the Markov chain describing the algorithm is ergodic. Note that this is very reasonable since the chain is finite and for most item size distributions it would also be irreducible and acyclic, hence ergodic. If the chain is not ergodic, it is necessary to apply the analysis we present on the irreducible part of the chain which is accessible from the initial state (empty bins).

Assume N t-1 = j and the algorithm now packs item a t . If the open bin cannot contain the item, i.e., j + s(a t ) > U, the item is packed in a new bin. The previous open bin contains Uj unused units which we call overhead units. We say that the overhead units "increased" the size of a t and define its combinedsize to be the actual size of the item, plus the overhead units it created. For example, say the algorithm is in state N t = 2 and the next item is of size U. The overhead in this case is U -2 units and we say the combined size of the item is U +U -2.

Denote by oh t the overhead added to the size of item a t . For an algorithm A and a list L n of n items, we define the expected average combined size of all items to be

I n av (A) ≡ E 1 n n ∑ t=1 (s(a t ) + oh t ) (6)
We define the expected asymptotic average combined size of all items as

I av (A) ≡ lim n→∞ I n av (A) (7)
Since I A (H) accounts for both the used and wasted space in the bins, we can state the following relation between I A (H) and A(L):

I A (H) = lim n→∞ E U • A(L n ) n ( 8
)
We now use a property of the optimal packing that ensures that for any item size distribution the tails of the distribution of OPT (L n ) decline rapidly enough with n [START_REF] Rhee | Martingale inequalities and NP-complete problems[END_REF], so that as

n → ∞, E[A(L n )/OPT (L n )] and E[A(L n )]/E[OPT (L n )
] converge to the same limit [START_REF] Coffman | Probabilistic Analysis of Packing and Partitioning Algorithms[END_REF]. Therefore the asymptotic expected performance ratio is given by

R ∞ A = lim n→∞ E A(L n ) OPT (L n ) = lim n→∞ E [A(L n )] E [OPT (L n )] = lim n→∞ U n E [A(L n )] U n E [OPT (L n )] = I av (A) I av (OPT ) (9)
To find the asymptotic expected performance ratio of the NF algorithm, we must calculate both I av (OPT ) and I av (NF). Since bin packing is NP-hard, finding I av (OPT ) for certain item size distributions may require exponential time in n. Fortunately, we do know that for several important distributions, including the uniform distribution, the overhead of the optimal packing can be neglected [START_REF] Coffman | Approximation algorithms for bin packing: A survey[END_REF]. For such distributions we have

I av (OPT ) = U ∑ i=1 i • h i = h ( 10
)
In cases where I av (OPT ) is not known we can still find the channel utilization of the algorithm by replacing I av (OPT ) with h, i.e., the average item size of the given distribution.

To find I av (NF) we use the Markov chain describing the algorithm. Denote by P the transition matrix of the Markov chain and by Π = (Π 1 , ...Π U ) the equilibrium probability vector satisfying Π = ΠP. Assume NF packs a long list of n items; denote by n j the number of visits in state j during the packing. Since we consider ergodic chains, we have the following property:

Pr lim n→∞ n j n = Π j = 1, which is usually written as lim n→∞ n j n = Π j , a.s. (almost surely). We now denote by n j,i the number of items of size i packed when the algorithm is in state j. The probability for the next item in the list to be of size i, h i , is unrelated to the state of the algorithm. Therefore we can use the Law of large numbers to establish the following property of n j,i :

lim n→∞ n j,i n = lim n→∞ n j n • h i = Π j • h i , a.s. ( 11
)
The overhead added to each item is related to both the state of the algorithm and the size of the item. We denote by oh i ( j) the overhead added to an item of size i which is packed when the algorithm is in state j. We calculate the average combined size of the items in the following way:

I av (NF) = lim n→∞ I n av (NF) = lim n→∞ E 1 n U ∑ j=1 U ∑ i=1 n j,i • (i + oh i ( j)) (12) = E U ∑ j=1 U ∑ i=1 lim n→∞ n j,i n • (i + oh i ( j))
Substituting [START_REF] Johnson | Worst-case performance bounds for simple one-dimensional packing algorithms[END_REF] we get

I av (NF) = U ∑ j=1 U ∑ i=1 Π j • h i • (i + oh i ( j)) ( 13
)
To simplify [START_REF] Karmarkar | Probabilistic analysis of some bin packing algorithms[END_REF] we use the following definitions:

h ≡ ∑ U i=1 i • h i average size of items (without overhead) OH( j) ≡ ∑ U i=1 h i • oh i ( j) average overhead in state j OH ≡ ∑ U j=1 Π j • OH( j) average overhead size (14)
Equation ( 13) now becomes:

I av (NF) = U ∑ j=1 Π j • U ∑ i=1 i • h i + U ∑ j=1 Π j • U ∑ i=1 h i • oh i ( j) = h + U ∑ j=1 Π j • OH( j) = h + OH ( 15
)
The expression in ( 15) is very intuitive; the asymptotic average combined size of the items is made of the average size of the items plus the average size of the overhead. To calculate the expected performance ratio we must find two components:

1. The equilibrium probabilities of the Markov chain, Π. We find Π by constructing the transition matrix P and calculating the equilibrium probability vector satisfying: Π = ΠP.

2. The overhead components oh i ( j). This is easily obtained from the packing rules of the algorithm.

Our technique of average case analysis has two advantages: it is suitable for analyzing any (i.i.d) item size distribution, both discrete and continuous, and the calculation is relatively easy. These properties are important since in most real-world applications of bin packing the items are drawn from a finite set, which is rarely uniform.

In the next subsection we calculate specific results for the case of discrete uniform distribution.

Discrete Uniform Distribution

Discrete uniform distribution means that h i = 1 U , ∀i. It is easy to see that in this case the Markov chain is ergodic. An important characteristic of the discrete uniform distribution is that the overhead of the optimal packing is negligible. To state it formally, let L n be a list of n items drawn from a discrete uniform distribution H and let s(L n ) be the total size of all items in L n . The expected wasted space of the optimal packing has the following property [START_REF] Coffman | Bin packing with discrete item sizes, Part I: Perfect packing Theorems and the average case behavior of optimal packings[END_REF]:

W n OPT (H) = E [U • OPT (L n ) -s (L n )] = O √ n
From the above result we conclude that

lim n→∞ E U•OPT (L n ) s(L n ) = 1.
We therefore neglect the overhead of the optimal packing in calculating the asymptotic expected performance ratio. Calculating I av (OPT ) is now trivial

I av (OPT ) = U ∑ i=1 i • h i = 1 U U ∑ i=1 i = U + 1 2 (16)
We use [START_REF] Koraitim | Performance analysis of multiple access protocols for multimedia satellite networks[END_REF] to find the average combined size of the items. We first find the equilibrium probabilities of the Markov chain. Let P be the U ×U transition matrix describing the chain and let Π = (Π 1 , ..., Π U ) be the equilibrium probability vector satisfying: Π = ΠP. There is a symmetry in the lines of the transition matrix P, in a sense that line j and line Uj are identical. For j ≤ U 2 we have

P j,k = 1 U •            0 1 ≤ k ≤ j 1 j < k ≤ U -j 2 U -j < k ≤ U 1 ≤ j ≤ U 2 (17)
The last line is

P U,k = 1 U , 1 ≤ k ≤ U.
The simple structure of the matrix P enables an easy solution to the set of equations Π = Π P.

Π j = 2 j U(U + 1) (18)
Next we compute the overhead component OH( j). When the NF algorithm is in state j any item bigger than Uj creates an overhead of Uj units; all other items are packed without overhead. Hence, the average overhead in state j is

OH( j) = U ∑ i=1 h i • oh i ( j) = U ∑ i=U-j+1 U -j U = j(U -j) U (19)
We now use [START_REF]Data-Over-Cable Service Interface Specifications -Radio Frequency Interface Specification (status: interim)[END_REF] and ( 19) to find the average combined size of the items

I av (NF) = h + U ∑ j=1 Π j • OH( j) = U + 1 2 + U ∑ j=1 2 j U(U + 1) • j(U -j) U (20) = U + 1 2 + U ∑ j=1 2 j 2 (U -j) U 2 (U + 1) = 2U + 1 3
We use I av (NF) and I av (OPT ) to obtain the asymptotic expected performance ratio

R ∞ NF = I av (NF) I av (OPT ) = (2U + 1)/3 (U + 1)/2 = 2(2U + 1) 3(U + 1) (21)
The result we obtain for the asymptotic expected performance ratio is in accordance with results reported in [START_REF] Coffman | Stochastic analysis of a slotted FIFO communication channel[END_REF]. The asymptotic worst case performance ratio is given in [START_REF] Coffman | Bin packing with discrete item sizes, Part I: Perfect packing Theorems and the average case behavior of optimal packings[END_REF]. We compare the two, for several values of U, in Table 1. We observe that in both cases the asymptotic performance ratio increases with the bin size. There is, however, a dramatic difference between the worst case performance ratio and the expected performance ratio. The average case results are therefore not as bad as the worst case analysis indicates.

Tab. 1: Expected and worst case asymptotic performance ratio of the NF algorithm.

Bin Size Worst case ratio Average case ratio

U R ∞ NF R ∞ NF 3 1.

Average Case Analysis of the NF f Algorithm

We now use the same method we used for analyzing the NF algorithm, to analyze the case where item fragmentation is allowed, i.e., the NF f algorithm. In this subsection we assume the items are taken from a discrete uniform distribution, that is h i = 1 U , ∀i. Note that the overhead this time is due to fragmentation or an unused free space (if the content of a closed bin is U -1).

The first stage in our analysis of NF f , is to find the equilibrium probabilities of the Markov chain. Let us describe the components of the transition matrix P

P j,k = 1 U •            0 k ≤ 2, k ≤ j ≤ U -k 2 j ∈ {k -2, k -1} 3 ≤ k 1 else (22)
The set of equations defined by Π = Π P is

Π 1 = 1 U Π U (23) Π 2 = 1 U (Π 1 + Π U-1 + Π U ) (24)
Π j = 1 U (1 + Π j-1 + Π j-2 ), 3 ≤ j ≤ U (25)
Note that the solution to (25) (if it were the only equation) is

Π j = 1 U-2 .
Unlike the case of NF, the solution to the set of equations ( 23)-( 25) is not simple. We therefore defer the calculation of a closed form solution to subsection 4.2.1 and proceed to calculate OH( j), the average overhead in state N = j. Note that when an item is fragmented over two bins, 2 units of overhead are added to it. In state N = U -1 all items of size 2 or more are packed in the next bin, so only 1 unit of overhead is added to them. The average overhead in state N = j is therefore

OH( j) = 1 U •            2 j 1 ≤ j ≤ U -2 U -1 j = U -1 0 j = U (26)
We can now express the average combined size of the items

I av (NF f ) = U + 1 2 + U ∑ j=1 Π j • OH( j) = U + 1 2 + U -1 U Π U-1 + U-2 ∑ j=1 Π j • 2 j U ( 27
)
Similar to ( 16), the overhead of the optimal packing is negligible I av (OPT ) = U+1 2 . The asymptotic expected performance ratio is therefore

R ∞ NF f = 1 + 2 U + 1 U -1 U ΠU-1 + U-2 ∑ j=1 Π j • 2 j U ( 28
)
At this point we do not have a closed form solution to the equilibrium probabilities and therefore we cannot present the expected performance ratio in closed form. It is easy, however, to find a numerical solution for every value of U. In Table 2 we present the asymptotic expected and worst case performance ratio of NF f for several values of U.

Tab. 2: Expected and worst case asymptotic performance ratio of the NF f algorithm. Recall that, according to Theorem 1, the worst case performance ratio of NF 1 and2 present the asymptotic expected performance ratio of the NF f and NF algorithms together with the worst case performance ratio of NF f . We observe that the difference between the worst case and the average case for NF f is not as significant as in NF, that is, the expected performance ratio of the NF f algorithm is not far from its worst case performance ratio. This is obvious for large values of U since the worst case ratio converges to one, but it also indicates that even under a uniform distribution the NF f algorithm produces almost the worst possible packing. An interesting question, which we leave open, is whether other, more efficient, algorithms can produce a better packing. In this respect we note that in the case where fragmentation is not allowed, there is a big difference between the performance of NF and the performance of other online algorithms, such as First-Fit and Best-Fit, for which the asymptotic expected performance ratio, for any value of U, is [START_REF] Coffman | Approximation algorithms for bin packing: A survey[END_REF]: R

Bin Size Worst case ratio Average case ratio

U R ∞ NF f R ∞ NF f 3 1. 5
f is R ∞ NF f = U U-2 . Figures
∞ FF = R ∞ BF = 1.
Finally we note that it is not difficult to repeat the analysis we presented, for the general case, where r units of overhead are added to the size of every fragment. We show in [START_REF] Menakerman | Bin packing problems with item fragmentation[END_REF] that in this case the equivalent of (28) is

R ∞ NF f = 1 + 2 U + 1 U-2r ∑ j=1 Π j • 2 j r U + U ∑ j=U-2r+1 Π j • j (U -j) U (29)

Calculating the Expected Performance Ratio

In this subsection we derive a closed form solution of the expected performance ratio. Since this closed form solution is rather complex, we also provide an approximation of the expected performance ratio.

The approximation is much easier to use and the approximation error, for all but small values of U, is insignificant. We substitute N = E[N] = ∑ U j=1 j • Π j in (28), to express R ∞ NF f in the following way: To calculate the value of N we use a generating function: G(z) = ∑ U j=1 Π j z j . We use the equilibrium equations ( 23) -(25) to get

R ∞ NF f = 1 + 2 U + 1 2 U N - U -1 U Π U-1 -2Π U (30)
G(z) = Π 1 z + Π 2 z 2 + U ∑ j=3 1 U (1 + Π j-1 + Π j-2 ) z j (31) = 1 U Π U z + 1 U Π U-1 + U + 1 U Π U z 2 + U ∑ j=3 1 U (1 + Π j-1 + Π j-2 ) z j
Arranging the above expression we get

G(z) = Π U z U+2 + (Π U + Π U-1 ) z U+1 -(Π U + Π U-1 ) z 2 -Π U z -∑ U j=3 z j z 2 + z -U (32)
To find N we calculate the derivative of the generating function at z = 1

N = dG(z) dz | z=1 = U(U + 1) -4UΠ U -2(U -1)Π U-1 2(U -2) ( 33
)
There are several possible extensions to the work presented in this paper; some of them are addressed in [START_REF] Menakerman | Bin packing problems with item fragmentation[END_REF]. From a practical point of view, other bin packing algorithms, should also be considered. We expect algorithms such as First-Fit (FF) and First-Fit Decreasing (FFD) [START_REF] Johnson | Worst-case performance bounds for simple one-dimensional packing algorithms[END_REF], to perform better than NF. The improved performance has to be weighed against the advantages of the NF f algorithm. Another interesting extension is to consider the case where the fixed allocations in the MAP create variable size gaps. This time the scheduling problem is modeled as a variant of variable size bin packing.

  NF f -In each stage there is only one open bin. The items are packed, according to their order in the list L, into the open bin. When an item does not fit in the open bin it is fragmented into two parts. The first part fills the open bin and the bin is closed. The second part is packed into a new bin which becomes the open bin.

Fig. 1 :

 1 Fig. 1: Expected and worst case performance ratio of the NF f and NF algorithms.

Fig. 2 :

 2 Fig. 2: Expected and worst case performance ratio of the NF f and NF algorithms for values of U ≤ 15.

Nir Namman and Raphael Rom

Substituting (33) in (30) we get an expression for the asymptotic expected performance ratio

We now have an expression which is a function of Π U-1 and

Observe that the first part of the expression is equivalent to the worst case performance ratio. The second part constitutes the difference between the worst case and the average case.

To find the expected performance ratio we must now calculate the probabilities Π U , ΠU-1. We do so by exploring the roots of the generating function given in (32). Note that the denominator is a square polynomial with two roots. Since the generating function is analytic for any value of z, the roots of the denominator are necessarily roots of the numerator also. This information provides two equations from which Π U and Π U-1 can be found. Denote by z 1 and z 2 the roots of the denominator

Substituting z 1 in the numerator we get

We get the same equation if we substitute z 2 in the numerator. Using the two equations it is now a straightforward algebraic exercise to find Π U and Π U-1 .

To find the expected performance ratio we substitute (37) and (38) in ( 35). The expression we obtained for the expected performance ratio enables exact calculation for any value of U but does not provide too much insight. To get a better understanding we note that (25) gives us a very good approximation:

The approximation is getting better the larger U is. Using the approximation we get

Comparing the exact value of the asymptotic expected performance ratio to the approximation, we find that for U = 7 the difference is about 0.3%, for U = 10 the difference is less than 0.003% and for larger values of U the approximation error is insignificant.

General Item Size Distribution

In this subsection we demonstrate how the analysis can be applied to any item size distribution. We assume the items are i.i.d and the probability to draw an item of size i is h i . As we mentioned earlier, since finding I av (OPT ) may be difficult, we calculate the bin utilization which requires finding I av (NF f ) only. We use [START_REF] Koraitim | Performance analysis of multiple access protocols for multimedia satellite networks[END_REF] to calculate the average combined size of the items. The construction of the transition matrix and the calculation of the equilibrium probabilities is similar to the one presented in the previous section. The calculation of the overhead component oh i ( j) (overhead added to an item of size i which is packed in state j) is simple

Example: We present an example using typical parameters of a data over CATV network. We assume a mini-slot is 25 microsecond and 16 bytes are transmitted in each mini-slot. In data over CATV networks a cable modem transfers IP datagrams using Ethernet packets. We therefore assume the datagram have typical Ethernet distribution with datagram sizes of 4, 8, 16, 64, and 94 mini-slots, and with the following probabilities: h 4 = 0.5, h 8 = 0.1, h 16 = 0.05, h 64 = 0.15, and h 94 = 0.2. The average item size of the given distribution is h = 32. We assume the bin size is U = 100 mini-slots, which corresponds to 2.5 millisecond.

We are interested in the channel utilization of algorithms NF and NF f . Using our average case analysis we find that I av (NF) = 40.

Conclusions

We studied a scheduling problem in which datagrams my be fragmented. Such scheduling problem is present in data over CATV networks as well as in several other applications (e.g., [START_REF] Coffman | Stochastic analysis of a slotted FIFO communication channel[END_REF], [START_REF] Mandal | Complexity of fragmentable object bin packing and an application[END_REF]). The analysis we presented can also serve as a tool for evaluating the benefits of fragmentation in other systems. For example, several reservation-based satellite systems present a similar scheduling problem to that of data over CATV (see e.g., [START_REF] Guntsch | Analysis of the ATDMA/PRMA++ protocol in a mobile satellite system environment[END_REF], [START_REF] Koraitim | Performance analysis of multiple access protocols for multimedia satellite networks[END_REF]) but fragmentation is not currently implemented in such systems.

To analyze the scheduling problem we introduced a new variant of bin packing that allows item fragmentation. We converted the scheduling problem into the problem of bin packing with item fragmentation and showed that the two problems are strongly related. We defined the NF f algorithm and performed both worst case and average case analysis to evaluate the schedule efficiency of the algorithm. We developed a new technique, based on calculating the overhead produced during the packing, to derive our average case results. This technique may prove useful in analyzing other problems.

We found that fragmentation can considerably improve the schedule efficiency of an algorithm. An important characteristic is that the schedule efficiency is increasing with the bin size (the gap between fixed allocations). This means that for large bin sizes, the efficiency of NF f is not far from the optimum. While NF f is not very efficient, it may still be chosen as a practical scheduling algorithm since it has some important advantage over other algorithms; NF f is very simple and is suitable for online and boundedspace scheduling. Moreover, it keeps a first-in-first-out order of transmissions.


Vince Grolmusz
email: grolmusz@cs.elte.hu

-MOD_p) Circuits

Keywords: Circuit complexity, modular circuits, composite modulus

. Perhaps the most important application is an exponential lower bound for the size of (MOD q , MOD p ) circuits computing the fan-in n AND, where the input of each MOD p gate at the bottom is an arbitrary integer valued function of cn variables (c < 1) plus an arbitrary linear function of n input variables.

Introduction

Boolean circuits are one of the most interesting models of computation. They are widely examined in VLSI design, in general computability theory and in complexity theory context as well as in the theory of parallel computation.

Almost all of the strongest and deepest lower bound results for the computational complexity of finite functions were proved using the Boolean circuit model of computation ( [START_REF] Razborov | Lower bounds for the monotone complexity of some Boolean functions[END_REF], [START_REF] Yao | Separating the polynomial-time hierarchy by oracles[END_REF], [START_REF] Håstad | Almost optimal lower bounds for small depth circuits[END_REF], [START_REF] Razborov | Lower bounds on the size of bounded depth networks over a complete basis with logical addition[END_REF], [START_REF] Smolensky | Algebraic methods in the theory of lower bounds for Boolean circuit complexity[END_REF], or see [START_REF] Van Leeuwen | Handbook of Theoretical Computer Science, volume A, chapter 14. The complexity of finite functions[END_REF] for a survey).

Even these famous and sophisticated lower bound results were proven for very restricted circuit classes. Bounded depth and polynomial size is one of the most natural restrictions. Ajtai [START_REF] Ajtai | ∑ 1 1 formulae on finite structures[END_REF], Furst, Saxe, and Sipser [START_REF] Furst | Parity, circuits and the polynomial time hierarchy[END_REF] proved that no polynomial sized, constant depth circuit can compute the PARITY function. Yao [START_REF] Yao | Separating the polynomial-time hierarchy by oracles[END_REF] and Håstad [START_REF] Håstad | Almost optimal lower bounds for small depth circuits[END_REF] generalized this result for sub-logarithmic depths. Since the modular gates are very simple to define, and they are immune to the random restriction techniques in lower bound proofs for the PARITY function, the following natural question was asked by several researchers: How powerful will become the Boolean circuits if -beside the standard AND, OR and NOT gates -MOD m gates are also allowed in the circuit? Here a MOD m gate outputs 1 iff the sum of its inputs is in a set A ⊂ {0, 1, 2, . . . , m -1} modulo m.

Razborov [START_REF] Razborov | Lower bounds on the size of bounded depth networks over a complete basis with logical addition[END_REF] showed that for computing MAJORITY with AND, OR, NOT and MOD 2 gates, exponential size is needed with constant depth. This result was generalized by Smolensky [START_REF] Smolensky | Algebraic methods in the theory of lower bounds for Boolean circuit complexity[END_REF] for MOD p gates instead of MOD 2 ones, where p denotes a prime.

Very little is known, however, if both MOD p and MOD q gates are allowed in the circuit for different primes p, q, or, if the modulus is a non-prime power composite, e.g., [START_REF] Grolmusz | A weight-size trade-off for circuits with mod m gates[END_REF]. For example, it is consistent with our present knowledge that depth-3, linear-size circuits with MOD 6 gates only, recognize the Hamiltonian graphs (see [START_REF] Barrington | Non-uniform automata over groups[END_REF]). The existing lower bound results use diverse techniques from Fourier-analysis, communication complexity theory, group-theory and several forms of random restrictions (see [START_REF] Barrington | Non-uniform automata over groups[END_REF], [START_REF] Krause | On the computational power of depth 2 circuits with threshold and modulo gates[END_REF], [START_REF] Szegedy | Functions with bounded symmetric communication complexity and circuits with MOD m gates[END_REF], [START_REF] Tardos | A lower bound on the MOD 6 degree of the OR function[END_REF], [START_REF] Smolensky | On interpolation by analytic functions with special properties and some weak lower bounds on the size of circuits with symmetric gates[END_REF], [START_REF] Grolmusz | Separating the communication complexities of MOD m and MOD p circuits[END_REF], [START_REF] Grolmusz | A weight-size trade-off for circuits with mod m gates[END_REF], [START_REF] Grolmusz | On the weak mod m representation of Boolean functions[END_REF], [START_REF] Barrington | Representing Boolean functions as polynomials modulo composite numbers[END_REF], [START_REF] Kahn | On mod p transversals[END_REF]).

It is not difficult to see that constant-depth circuits with MOD p gates only (p prime), cannot compute even simple functions: the fan-in n OR or AND functions, since they can only compute constant degree polynomials of the input variables over GF p (see [START_REF] Smolensky | Algebraic methods in the theory of lower bounds for Boolean circuit complexity[END_REF]).

But depth-2 circuits with MOD 2 and MOD 3 gates, or MOD 6 gates can compute the n-fan-in OR and AND functions [START_REF] Kahn | On mod p transversals[END_REF], [START_REF] Barrington | Non-uniform automata over groups[END_REF]. Consequently, these circuits are more powerful than circuits with MOD p gates only.

By the famous results of Yao [START_REF] Yao | On ACC and threshold circuits[END_REF] and Beigel and Tarui [START_REF] Beigel | On ACC[END_REF], and Toda [START_REF] Toda | PP is as hard as the polynomial-time hierarchy[END_REF], every polynomial-size, constant-depth circuit with AND, OR, NOT and MOD m gates can be converted to a depth-2 circuit with a SYMMETRIC gate at the top and quasi-polynomially many AND gates of poly-logarithmic fan-in at the bottom. One might hope that this result is an excellent tool for bounding the power of circuits containing modular gates. Unfortunately, the existing lower bound techniques are not strong enough to bound the computational power of these circuits.

Our main contribution here is a lemma, the Degree Decreasing Lemma, which yields a tool for dealing with low-fan-in AND gates at the bottom of (MOD q , MOD p ) circuits. We believe that -in the light of the result of Yao, Beigel and Tarui -our result may have further important consequences in modular circuit theory. All of our gates are of unbounded fan-in, and we allow to connect inputs to gates or gates to gates with multiple wires. Let us remark, that we are interested mainly in circuits with modular gates and with constant moduli; consequently, the number of wires is polynomially related to the number of gates.

Preliminaries

In the literature MOD m gates are sometimes defined to be 1, iff the sum of their inputs is divisible by m, and sometimes they are defined to be 1, iff the sum of their inputs is not divisible by m. The following, more general definition covers both cases.

Definition 2

We say that gate G is a MOD m -gate, if there exists a non-empty A ⊂ {0, 1, . . . , m -1}, such that G(x 1 , x 2 , . . . ,

x n ) = 1, if ∑ n i=1 x i mod m ∈ A 0 otherwise.

A is called the 1-set of G. MOD m gates with 1-set A are denoted by MOD A

m . Definition 3 Let p be a prime. We say that polynomial P(x 1 , x 2 , . . . , x n ) over the p element field is a depth-d polynomial, if it can be computed by an arithmetic circuit from inputs x 1 , x 2 , . . . , x n and constants 1 and 0, as follows: the arithmetic circuit is levelled, the variables and constants 0 and 1 are situated on the lowest level, and multiple wires (i.e., constant multipliers) are allowed in the circuit. The levels of the circuit contains ADDITION and MULTIPLICATION gates, the ADDITION gates are of unbounded fan-in, the MULTIPLICATION gates are of fan-in 2. There are only d levels where MULTIPLICATION gates occur, and within the same level, one input of each MULTIPLICATION gates are connected to the same node (called the common multiplier on the level), situated one level lower.

In other words, if on the same level there are several MULTIPLICATION gates, and one of them computes PQ, then all the other MULTIPLICATION gates on the same level should compute PR 1 , PR 2 ,...,PR s or, alternatively, R 1 Q, R 2 Q,...,R s Q, where P, Q and R i for i = 1, 2, . . . , s denote polynomials, computed in the nodes just below our level.

Note, that we have not bounded the number of gates in the arithmetic circuit, just the number of levels containing multiplications and the structure within the levels.

Lemma 4 Any multi-linear polynomial with n variables is a depth-(n -1) polynomial.

Proof: We prove by induction. Our induction hypothesis is the following: If P(x 1 , x 2 , . . . , x n ) is a multilinear polynomial of n variables, then it can be computed by an arithmetic circuit of Definition 3 such that on the first (lowest) multiplication level the common multiplier is x 2 , on the second multiplication level the common multiplier is x 3 , ...., on the n -1st multiplication-level the common multiplier is x n .

The base case is obvious. The induction step: If P(x 1 , x 2 , . . . , x n ) is a multi-linear polynomial, then P = x n Q + R where Q and R are multi-linear polynomials of variables x 1 , x 2 , . . . , x n-1 . Consequently, for Q and R the induction hypothesis is satisfied with depth n -2, so we are done. ✷

We remark, that linear polynomials are depth-0 polynomials. Polynomial

(x 1 + x 2 + x 3 + x 4 + x 5 )(x 2 + x 4 + x 5 ) 2 (x 3 + x 5 + 2) + (x 2 + x 4 + x 5 )(x 3 + x 1 + x 5 ) + 12
is a depth-2 polynomial.

Definition 5 Let p and q be two different primes, and let d be a non-negative integer. Then (MOD q , MOD p ; depthd) denotes a (MOD q , MOD p ) circuit, where the input of each MOD p -gate is a depth-d polynomial.

3 The Degree-Decreasing Lemma

The following lemma is our main tool. It exploits a surprising property of (MOD p , MOD q )-circuits, which lacks in (MOD p , MOD p ) circuits, since constant-depth circuits with MOD p gates are capable only to compute a constant degree polynomial of the inputs, and this constant depends on the depth, and not on the size.

Remark 1. Generally, the inputs of the modular gates are Boolean variables. Here, however, for wider applicability of the lemma, we allow input x for a general MOD m gate to be chosen from set {0, 1, . . . , m -1}. This will allow us to substitute polynomials into the variables of the lemma.

Remark 2. The output of the general MOD m gates depend only on the sum of the inputs. In the next lemma it will be more convenient to denote MOD A m (y 1 , y 2 , . . . , y ℓ ) i.e., gate MOD A m with inputs y 1 , y 2 , . . . , y ℓ , by MOD A m (y 1 + y 2 + • • • + y ℓ ). Lemma 6 (Degree Decreasing Lemma) Let p and q be different primes, and let x 1 , x 2 , x 3 be variables with values from {0, 1, . . . , p -1}. Then

MOD B q (MOD A p (x 1 x 2 + x 3 )) = MOD B q (H 0 + H 1 + • • • + H p-1 + β),
where H i abbreviates

H i = α p-1 ∑ j=0 MOD A p (ix 2 + x 3 + j(x 1 -i))
for i = 0, 1, . . . , p -1, where α is the multiplicative inverse of p modulo q: αp ≡ 1 (mod q), and β is a positive integer satisfying β = -|A|(p -1)α mod q.

In the special case of (MOD 3 , MOD

2 ) circuit, the statement of Lemma 6 is illustrated on Figure 1.

2 ) case: on the left the input is a degree-2 polynomial, on the right the inputs are linear polynomials.

  † A preliminary version of this work appeared in the Proceedings of ICALP'98, Springer Verlag, LNCS 1443, pp. 215-222. 1365-8050 c 2001 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France

Fig. 1 :

 1 Fig. 1: Degree-decreasing in the (MOD 3 , MOD

  -gate on the top, G 2 gates on the second level, G 3 gates on the third level from the top,..., and G ℓ gates on the last level. Multi-linear polynomials (i.e., polynomials where the exponent of every variable is 0 or 1) with integer coefficients and of input-variables x 1 , x 2 , . . . , x n of degree at most d are connected to G ℓ gates on the last level. The size of a circuit is defined to be the total number of the gates G 1 , G 2 , . . . , G ℓ in the circuit.

Definition 1 A fan-in n gate is an n-variable Boolean function. Let G 1 , G 2 , . . . , G ℓ be gates of unbounded fan-in. Then a (G 1 , G 2 , . . . , G ℓ ; d)circuit denotes a depth-ℓ circuit with a G 1

Acknowledgment. The author is indebted to Dániel Varga, Katalin Friedl, Zoltán Király, and Gábor Tardos for fruitful discussions on this work. Supported in part by grants OTKA T030059, FKFP 0607/1999.

Proof: Let x 1 = k and let 0 ≤ i ≤ p -1, k = i. Then

and

since for any fixed x 2 , x 3 , i, k expression ix 2 + x 3 + j(ki) takes on every value exactly once modulo p while j = 0, 1, . . . , p -1; so MOD A p (ix 2 + x 3 + j(ki)) equals to 1 exactly |A| times. Consequently,

✷ 4 Applications of the Degree Decreasing Lemma

The following theorem facilitates the applications of the Degree Decreasing Lemma:

Theorem 7 Suppose, that function f : {0, 1} n → {0, 1} can be computed by a (MOD B q , MOD A p ; depthd) circuit of size s, where p and q are two different primes, and d is a non-negative integer. Then f can also be computed by a (MOD B q , MOD A p ; 1) circuit of size (p 2d + 1)s.

Proof:

We first show, that our (MOD B q , MOD A p ; depthd) circuit of size s can be converted into a (MOD B q , MOD A p ; depth -(d -1)) circuit of size at most p 2 s + 1. Repeating this conversion d -2 times, the statement follows.

We know that the input of every MOD A p -gate can be constructed with at most d multiplications in an arithmetic circuit. Let us consider a fixed MOD A p -gate. Suppose, that the last multiplication, which computes its input-polynomial is PQ + R, where P, Q, R are depth-(d -1) multi-linear polynomials of n variables. This MOD A p -gate, using the Degree Decreasing Lemma (Lemma 6), can be converted to at most p 2 MOD A p -gates, each with depth-(d -1) polynomials as inputs, plus (possibly) a leftover MOD A p -gate with input 1 (which may be connected to the MOD B q gate with multiple wires) such that the sum of these gates give the same output modulo q as the original one. If the conversion is done for all MOD A p -gates, the result is a (MOD B q , MOD A p ; depth-(d -1)) circuit of size at most p 2 s+1, since the "leftover" MOD A p -gate with input 1 should be counted once. ✷

Constant Degree Hypothesis

Barrington, Straubing and Thérien in [START_REF] Barrington | Non-uniform automata over groups[END_REF] conjectured that any (MOD B q , MOD A p ; d) circuit needs exponential size to compute the fan-in n AND function. They called it the Constant Degree Hypothesis (CDH), and proved the d = 1 case, with group-theoretic techniques.

Yan and Parberry [START_REF] Yan | Exponential size lower bounds for some depth three circuits[END_REF] -using Fourier-analysis -proved also the d = 1 case for (MOD {1,2,...,q-1} q , MOD {1} 2 ; 1) circuits, but their method also works for the special case of the CDH where the sum of the degrees of the monomials g i on the input-level satisfies:

-O(1).

Our Theorem 7 yields the following generalization of this result:

Theorem 8 For any prime p there exists a constant 0 < c p < 1, such that for any 0 < c < c p there exists a 0 < c ′ < 1, such that if a (MOD B q , MOD A p , depth -⌊cn⌋) circuit computes the n-fan-in AND function, then its size is at least 2 c ′ n .

Proof: From the result of [START_REF] Barrington | Non-uniform automata over groups[END_REF] and from Theorem 7 the statement is immediate. ✷

We should add, that Theorem 8 does not imply the CDH, but it greatly generalizes the lower bounds of [START_REF] Yan | Exponential size lower bounds for some depth three circuits[END_REF] and of [START_REF] Barrington | Non-uniform automata over groups[END_REF], and it works not only for the constant degree, but degree-cn polynomials as well.

Corollary 9 For any prime p there exists a constant 0 < c p < 1, such that for any 0 < c < c p there exists a 0 < c ′ < 1, such that if the fan-in n AND function is computed by a circuit with a MOD B q gate at the top, MOD A p gates at the next level, where the input of each MOD A p gate is an arbitrary integer-valued function of cn variables plus an arbitrary linear polynomial of n variables, then the circuit must contain at least 2 c ′ n MOD A p gates. Proof: First we convert the integer-valued function of cn variables into a polynomial over GF(p), for each MOD A p gates. These polynomials have degree at most cn, and depend on at most cn variables. Consequently, the circuit is a (MOD B q , MOD A p , depth -(⌊cn⌋ -1)) circuit, and Theorem 8 applies. ✷

We should mention, that Corollary 9 is much stronger than Yan and Parberry's result [START_REF] Yan | Exponential size lower bounds for some depth three circuits[END_REF], since here the degree-sum of the inputs of each MOD A p gate can be even exponentially large in n, vs. the small linear upper bound of [START_REF] Yan | Exponential size lower bounds for some depth three circuits[END_REF].

The ID function

circuit computes the 2n-fan-in ID function, then its size is at least 2 cεn , where 0 < c < 1 depends only on p.

Proof: From the result of [START_REF] Krause | Variation ranks of communication matrices and lower bounds for depthtwo circuits having nearly symmetric gates with unbounded fan-in[END_REF] and from Theorem 7 the statement is immediate. ✷

Unfortunately, the methods of [START_REF] Krause | Variation ranks of communication matrices and lower bounds for depthtwo circuits having nearly symmetric gates with unbounded fan-in[END_REF] do not generalize for MOD B q gates with unrestricted B's.

The MOD r function

Krause and Pudlák [START_REF] Krause | On the computational power of depth 2 circuits with threshold and modulo gates[END_REF] proved that any (MOD

q ; 1) circuit which computes the MOD {0} r function has size at least 2 c ′′ n , for some c ′′ > 0, where p, q and r are different primes. We also generalize this result as follows:

Theorem 11 There exist 0 < c ′ < c < 1 for different primes p, q, r, and positive integer k, if circuit (MOD {0} p k , MOD {0} q ; depth -⌊cn⌋) computes MOD {0} r (x 1 , x 2 , . . . , x n ), then its size is at least 2 c ′ n .

Proof: From the result of [START_REF] Krause | On the computational power of depth 2 circuits with threshold and modulo gates[END_REF] and from Theorem 7 the statement is immediate. ✷