Bogdan Chornomaz

Keywords: Bogdan Chornomaz, Counting extremal lattices, 2015, hal-01175633v2 COUNTING EXTREMAL LATTICES

come

Counting extremal lattices.

Introduction

Extremal lattices arise in formal concept analysis in investigating concept lattices which are "large", that is, exponential in size with regards to the set of objects(attributes); or, restating it in terms of lattice theory, lattices that are exponential with regards to the number of join-irreducible elements.

An easy example of such lattice would be B(n), a boolean lattice on n atoms, which has n join-irreducible elements and is of size 2 n . Obviously, any lattice containing B(m) as a sublattice, with m compatible to n, would also be large. On the other hand, this is the only reason for a lattice to exhibit an exponential blowup, as the following bound holds Theorem 1.1. For a lattice L with n join-irreducible elements not containing an embedding of B(k) holds

( †) |L| ≤ k-1 i=0 n i .
In [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF], which is an extended version of [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF], it is shown that a lattice L does not contain B(k) if and only if the set family {J(x) | x ∈ L}, where J(x) is a set of join-irreducible elements bellow x, has Vapnik-Chervonekis (VC) dimension less than k. Theorem 1.1 is then known as Sauer-Shelah theorem [START_REF] Sauer | On the density of families of sets[END_REF], [5].

By analogy, we call the bound ( †) the Sauer-Shelah bound. This bound is precise and is reached on the class of extremal lattices. All bound, sharpness and characterization of extremal lattices are shown in the paper of Albano and Chornomaz [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF].

In this paper we make a deeper research into structure of extremal lattices and give an exact formula for the number of non-isomorphic extremal lattices with VC dimension at most 2.

All lattices considered in the paper are finite. The structure of the paper is as follows. In Section 2 we give basic definitions and properties regarding extremal lattices. In Section 3 we consider simple decompositions of extremal lattices. In Section 4 we introduce root decompositions, which play a central part in constructing an iterative formula. In Section 5 we briefly outline shortcomings of root decomposition, which prevent from constructing iterative formulas for extremal lattices with VC dimension greater than 2. In Section 6 we study connection between automorphisms of extremal lattices and of root decompositions. Finally, in Section 7 we come up with a formula for the number of lattices.

Definitions and recollections

For a lattice L and an element x ∈ L we denote the set of join-irreducible elements of L by J(L) and thee set of join-irreducible elements below x by J(x). Also we use commonly used notation for semi-intervals

(x] := {y | y ≤ x}, [x) := {y | y ≥ x}.
We say that a lattice L is B(k)-free if there is no order embedding of B(k) into L. Note that this is not equivalent to not having lattice embedding of B(k). For example, the lattice in Figure 1 below, which is B(4) with doubled element in the middle, contains B(4) as an order embedding, but not as a lattice embedding.

a b c d Figure 1
Alternative definition, which has more lattice-theoretic scent, is that a lattice L is B(k)-free if it does not contain a sublattice congruent to B(k). As we will not use this definition, we leave it without a proof.

We say that a lattice L is (n, k)-free if L is a B(k)-free lattice with n joinirreducible elements.

We say that a set X ⊆ J(L) is a representation of an element x if X = x. X is a minimal representation if no proper subset of X joins to x. Obviously, any element in L has some minimal representation, which might not be unique, and no two distinct elements can have a common minimal representation.

Let us denote the right-hand side of ( †) bound by f (n, k), that is

f (n, k) := k-1 i=0 n i .
The following crucial observation about (n, k)-free lattices is a weakened form of Lemma 2 in [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF].

Proposition 2.1. In an (n, k)-free lattice the size of every minimal representation of every element is at most k -1.

As there are no more that f (n, k) ways of choosing minimal representation of size at most k -1, the bound ( †) follows.

We call a lattice L (n, k)-extremal if it is (n, k)-free and it reaches Sauer-Shelah bound, that is, it has f (n, k) elements. Note that when dealing with (n, k)-free and (n, k)-extremal lattices we assume n ≥ 1 and k ≥ 2.

Summing up what we have said about minimal generators, we have the following easy but important property. Proposition 2.2. In an (n, k)-free lattice every element has unique minimal representation of size at most k -1; conversely, every set of join-irreducible elements of size at most k -1 is a minimal representation for some element.

For an element x of an extremal lattice we denote its minimal representation by G(x). A restatement of Proposition 4 in [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF] gives another important property of extremal lattices. Theorem 44 of [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] gives a broader scope of that property. Proposition 2.3. Every extremal lattice L is meet-distributive, that is, for any x, y ∈ L, |J(y) -J(x)| = 1 whenever x ≺ y. Proposition 2.4. For k ≥ 3 any (n, k)-extremal lattice is atomic.

For a poset L and its subposet K we define doubling of

K in L, denoted L[K],
as a poset with elements L ∪ • K, where • K is a disjoint copy of K, and order

≤ = ≤ ∪{(x, • y) ∈ L × • K | x ≤ y} ∪ {( • x, • y) ∈ • K × • K | x ≤ y}.
The following is Proposition 5 in [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF]. Theorem 2.6. For any n ≥ 1 and k ≥ 3

(1) An (n, 2)-extremal lattice is a chain of length n;

(2) An order-embedding of (n, k -1)-extremal lattice into an (n, k)-extremal lattice is also a (1, ∧)-embedding;

(3) For (n, k)-extremal lattice L and (n, k-1)-extremal lattice K order-embedded into L, L[K] is an (n + 1, k)-extremal lattice. Theorem 2.7. For (n, k)-extremal lattice L, n ≥ 2, k ≤ 3 and for any a ∈ G(1 L ), K := [a) is an (n -1, k -1)-extremal lattice, L := L -[a) is an (n -1, k)-extremal
lattice, and the mapping φ :

K → L , φ(x) = J(x) -{a} ,
defines an order-embedding of K into L .

Finally, Corollary 1 of [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF] establishes that the notion of an extremal lattice is not degenerate.

Proposition 2.8. For any n ≥ 1 and k ≥ 2 there exists an (n, k)-extremal lattice.

Basic decompositions

In order t utilize the decomposition in Theorem 2.7, we develop a notation for it. For an (n, k)-extremal lattice L and a ∈ G(1 L ) we denote an (n -1, k)-extremal lattice L -[a) by L a and an embedding of (n -1, k -1)-extremal lattice [a) into L a by L ↑ a . We call the tuple (L a , L ↑ a ) a decomposition of L by a. Proposition 3.1. For an (n, k)-extremal lattice L and an element a ∈ G(1) the lattice L a can be represented as

L a = (a ],
where (a ] is a unique coatom of L not above a, a = (J(L) -{a }).

For a ∈ G(1 L ) and b ∈ G(1 La ) we denote by L ab the lattice (L a ) b . We refrain from developing in a similar fashion the notion of decomposition of higher order.

Note that in its present form decompositions do not address the task of counting isomorphism classes of extremal lattices, as non-isomorphic decompositions (although we have not yet defined this notion formally) can lead to the same lattice, as shown in Figure 2 below. Let us make several observations on general structure of extremal lattices. We start with noticing that in an (n, k)-extremal lattice all elements with minimal representation strictly smaller than k -1 are situated rather trivially.

Lemma 3.2. For an element x of an (n, k)-extremal lattice if G(x) < k -1 then G(x) = J(x).
Proof. Suppose on the opposite that G(x) J(x), that is, there is a ∈ J(x)-G(x). We denote by H the set G(x) ∪ {a} and observe that H = G(x) = x. However |H| ≤ k -1 and by Proposition 2.2 H is a minimal representation for some element of L, that is, H = G(x), a contradiction.

It follows from Proposition 2.3 that an (n, k)-extremal lattice L has height n. Now, Lemma 3.2 implies the following statement.

∈ G(1 L ) • if n ≤ k -1 then G(1 La ) = G(1 L ) -{a}; • if n > k -1 then there is b ∈ J(L) -G(1 L ) such that G(1 La ) = G(1 L ) - {a} + {b}. Proof. If n = k -1 then L is B(n)
and the claim is obvious. Now let us suppose that n > k -1. We split this into three cases.

If k = 2 then, as stated in Theorem 2.6, L is a chain of length n, and 1 La is a unique coatom with

G(1 L ) = 1 L , G(1 La ) = 1 La if n > 1 and G(1 La ) = ∅ if n = 1, which proves the claim. If k ≥ 4 then from Proposition 2.4 and Proposition 2.3 it follows that J(L ↑ a ) = J(L) -{a}. We denote L ↑ a by K and G K (1 K ) by H. Note that H has k -2 elements. Now, a ∨ L H = L {x ∨ a | x ∈ H} = L { • x | x ∈ H} = K H • = • 1 K = 1 L .
As the set H + {a} has k -1 elements and lie in J(L), from Proposition 2.2 it follows that G(1 L ) = H + {a}.

Another observation is that

1 La = 1 K ≥ K G La (1 La ) ≥ La G La (1 La ) = 1 La .
Thus, G La (1 La ) is a representation of 1 K in K, and consequently it contains the unique minimal representation H of 1 K in K as a subset. Proposition 3.3 implies that G La (1 La ) has k -1 element and consequently

G La (1 La ) = H + {b}, for some b in J(L a ) -H. Finally we may observe that L a = (1 La ] L and thus G La (1 La ) = G L (1 La ). Con- sequently G L (1 La ) = G La (1 La ) = H + {b} = G L (1 L ) -{a} + {b}.
At least let us consider the case when k = 3 and n > k -1. As earlier, we denote L ↑ a by K. Note that now K is a chain in L a and consequently J(K) does not lie in J(L).

Let us denote the minimal representation G(1 L ) by {a, b} and the coatoms of 1 L by a := 1 La and b := 1 L b . Notice that a ≥ b and b ≥ a. Also notice that (J(L) -{a, b}) = a ∧ b . Thus, every representation of a in L a contains b and consequently its minimal representation G(a ) also contains it. So G(a ) = {b, c} for some c ∈ J(L) -{a} and we get

G L (1 La ) = G La (b ) = {b, c} = G L (1 L ) -{a} + {c}.
The last case is illustrated in Figure 3 Let A := (a 1 , . . . , a l ) be a sequence without repetitions of elements of G(1 L ) for some (n, k)-extremal lattice L. Then Lemma 3.4 justifies notation L A to denote an (n -l, k)-extremal lattice obtained by consequent decomposition of L by a 1 , a 2 and so on. We claim that in fact the order of {a i } does not matter. Lemma 3.5. Let L be an (n, k)-extremal lattice, A := (a 1 , . . . , a l ) a sequence without repetition from G L (1) and σ a permutation on (1, . . . , l). Let B be a sequence defined as B := a σ(1) , a σ(2) , . . . , a σ(l) .

Then L A = L B .
Proof. By Proposition 3.1 we get L ai = (a i ] where a i = (J(L)-{a 1 }). Repeating this l times we get L A = (a] where a = (J(L) -{a 1 , . . . , a l }). Obviously, the construction of a does not depend on the order of {a i }, which proves our claim.

We emphasize the fact that in Lemma 3.5 L A and L B are not just isomorphic, but coincide as embeddings into L. Lemma 3.5 justifies notation L A for a set A ⊆ G(1 L ).

We end this section with several easy statements about extremal lattices. Proof. From Proposition 2.3 it follows that there is a chain (x m , . . . , x n ) in L with |J(x i )| = i, x m = x and x n = 1. We observe that x i is a coatom in (x i+1 ]. The claim is than follows by downward induction from x n to x m using Proposition 3.1.

Proposition 3.8. In (n, k)-extremal lattice an element of height m has exactly min(m, k -1) lower neighbors.

Proof. This is a straightforward application of Proposition 3.3, Proposition 3.6 and Proposition 3.7.

Root decompositions

Below we define root, root element and root decomposition of an (n, k)-extremal lattice. We stress that when dealing with these notions we would imply that k ≥ 3 and n ≥ k -1, without explicitly saying it each time. Note that by Property 2.4, k ≥ 3 implies that the lattice is atomic.

For an (n, k)-extremal lattice L we define the root of L, denoted R(L), as an embedding L G(1) , and the root element of L, denoted r(L), as 1 R(L) . Note that R(L) is an (n -k + 1, k)-extremal lattice.

An easy corollaries of Lemma 3.5 are the following properties.

Proposition 4.1. For an extremal lattice the root element is a meet of the coatoms of this lattice.

Proposition 4.2. For an (n, k)-extremal lattice L holds G(1) = J(L) -J(r(L)).

For the following definition of root decomposition we fix some order on J(L). Let a 1 , . . . , a k-1 be elements of G(1) enumerated in this order. Let L i denote an embedding L G(1)-{ai} . Then L ii = R(L) and thus R(L), L ↑

ii is a decomposition of L i .

We call k-tuple RD(L) := (R(L), P 1 (L), . . . , P k-1 (L)), where P i stands for L ↑ ii , a root decomposition of L.

Note that the order of P i matters, and that is why we needed to fix an order on J(L). However below we are going to define isomorphisms of decompositions, in a way that different orders of the same extremal lattice would lead to different but isomorphic decompositions.

We call a k-tuple (R, P 1 , . . . , P k-1 ), where R is an (n, k)-extremal lattice and P i are embeddings of (n, k -1)-extremal lattices into R, an (n, k)-decomposition. Thus, the root decomposition R is a mapping from (n + k -1, k)-extremal lattices to (n, k)-decompositions.

We define isomorphism between (n, k)-decompositions (R, P 1 , . . . , P k-1 ) and (R , P 1 , . . . , P k-1 ) as a tuple (φ, σ) for an isomorphism φ : R → R and a permutation σ on (1, . . . , k) such that φ P σ(i) = P i , for all i. (n, k)-decompositions for which there is an isomorphism, are called isomorphic. Proposition 4.3.

• isomorphism of (n, k)-decompositions is an equivalence relation, thus the name "isomorphism" is justified; • root decompositions of isomorphic (n, k)-extremal lattices are isomorphic. An essential point is that for (n, 3)-extremal lattices isomorphism of root decomposition also implies isomorphism of lattices themselves. Lemma 4.5. (n, 3)-extremal lattices are isomorphic if and only if their root decompositions are.

Proof. With Proposition 4.3 providing the "if" part, we only need to prove the "only if".

Here we adopt "proof by picture" approach. Notice that for an (n + 3 -1, 3)extremal lattice L and its root decomposition R(L) = (R, P 1 , P 2 ), L can be reconstructed from R(L) by doubling P 1 in R. To make next step and reconstruct L by R[P 1 ] and P 2 we must extend P 2 to a maximal chain in R[P 1 ], but there is exactly one way of doing so, namely by adding 1 R[P1] on top of P 2 . Then L = R[P 1 ][P 2 ], where P 2 is extended P 2 .

The fact that this procedure is unequivocal proves the isomorphism of thus reconstructed extremal lattices.

This argument is illustrated in Figure 4 below.

P 1 P 2 R 5 1 2 3 4 P 2 R[P 1 ] 5 1 2 3 4 6 R[P 1 ][P 2 ]
Figure 4. Reconstruction of an (6, 3)-extremal lattice by its root decomposition.

As we see, to count isomorphism classes of (n, 3)-extremal lattices we can count nonisomorphic (n -2, 3)-extremal decompositions, and indeed that is what we will do further. But can we adopt the same approach for larger k? 5. Why this does not work for (n, 4)-extremal lattices and higher.

For k > 3 counting non-isomorphic (n -k + 1, k)-decompositions certainly provides a lower bound for the number of non-isomorphic (n, k)-extremal lattice, as due to Proposition 4.3 isomorphic lattices yield isomorphic decompositions. The opposite does not hold even for k = 4, as different lattices may produce same decomposition, as shown in Figure 5 below.

Here we present only the initial step of the reconstruction, as resulting lattices are large and thus their diagrams are not very informative. It can be seen that there are two ways to extend each of P 1 and P 2 to (4, 3)-extremal embedding in R[P 1 ], which we denote by P 2 [P 1 ] and P 3 [P 1 ]. Thus, we get four ways to extend embeddings on the first step, and another choice of two possible extensions on the next step, resulting in eight possible ways of reconstructing L. Some of these reconstruction will be isomorphic, some will not. We also note, although without proving it, that the number of possible extensions of P i during the doubling of P j equals the number of ways to chose a maximal chain, that is (n, 2)-extremal embedding, in P i ∩ P j . Thus the degree of nondeterminism in choice may also vary depending on relative position of P i .

Automorphisms of extremal lattices.

We define an automorphism of (n, k)-decomposition (R, P 1 , . . . , P k-1 ) as an automorphism φ : R → R and a permutation σ on (1, . . . , k -1) such that φ(R σ(i) ) = R i , for all i. That is, as expected, an automorphism of a decomposition is an isomorphism of this decomposition to itself. Trivially, each decomposition has a trivial identity automorphism and all automorphisms of a decomposition form a group.

We recall that the notion of root decomposition of (n, k)-extremal lattice L involved a fixed order on J(L). As Proposition 4.3 infers, this order is nonessential in order to distinguish isomorphism classes of extremal lattices and their decompositions. However in order to work with automorphisms we need to pay this order a close look.

We note that automorphisms of (n, k)-extremal lattice L form a subgroup in the group of permutations on the set (1, . . . , n) of join-irreducible elements of L.

For an automorphism α of L by RD α (L) we denote root decomposition of L with order α on J(L).

We claim that automorphisms of L and isomorphisms of G(L) are in one-to-one correspondence.

Lemma 6.1. Automorphism group of an (n, k)-extremal lattice is a subgroup of automorphism group of its root decomposition.

Proof. Let L be an (n, k)-extremal lattice, k ≥ 3, n ≥ k, and F a fixed order on J(L). We denote the automorphism group of L by A and identify each automorphism of L with a permutation of J(L). Thus, A ≤ Sym(J(L)).

Obviously, any isomorphism α ∈ A maps coatoms to coatoms, thus by Proposition 4.1, α(r(L)) = R(L). We recall that by Proposition 4.2, J(L)-J(r(L)) = G(1). Thus, α can be represented as a tuple of permutations

α = (φ α , σ α ) ∈ Sym J(r(L)) ⊗ Sym G(1)) .
Note that φ α defines an isomorphism of R(L) and σ α is a permutation of k -1 elements of G(1).

Let us define δ : G(1) → (1, . . . , k -1) as a function that maps a join-irreducible element to its number in G(1) with regards to F . We argue that φ α [P δ(a) ] = P δσ(a) , for every α ∈ A and a ∈ G(1). Indeed, P δ(a) = π a L ↑ a , where a = G(1) -{a}, L ↑ a = (r(L) ∨ a] -(r(L)] and π a : L ↑ a → R(L) is a projection mapping defined as π a (x) = x ∧ r(L) = (J(x) -{a}) .

Thus

J(α • π a (x)) = α [J(x) -{a}] = α [J(x)] -{σ α (a)} = J(α(x)) -{σ α (a)} = J(π σα(a) • α(x)), implying α • π a = π σα(a)
• α, and we get

P δσ(a) = π σ(a) (r(L) ∨ σ α (a)] -(r(L)] = π σ(a) • α (r(L) ∨ a] -(r(L)] = α • π a (r(L) ∨ a] -(r(L)] = α P δ(a) = φ α P δ(a) .
Thus, the mapping α → (φ α , δ • σ -1 α ) establishes the desired embedding. This argument is illustrated in Figure 6 below. The embedding, provided by Lemma 6.1 may in general be proper. For example the automorphism group of decomposition on Figure 5 if Sym(3), while some lattices reconstructed from it may have no nontrivial automorphisms. However for (n, 3)-extremal lattice this embedding turns into isomorphism. Lemma 6.2. Automorphism group of an (n, 3)-extremal lattice is isomorphic to automorphism group of its root decomposition.

Proof. As in the proof of Lemma 4.5 the claim follows from the possibility of unique reconstruction of L by R(L) when L is (n, 3)-extremal. Proof. We recall that isomorphism group A of (n, 3)-decomposition D is a subgroup of Sym(n)⊗Sym [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF], where Sym(n) defines an isomorphism of R and Sym(2) a permutation in order of chains P 1 and P 2 . We claim that there is no two automorphisms (φ 1 , σ) and (φ 2 , σ), φ 1 = φ 2 , which would immediately imply the claim of the lemma. Indeed, if there are two such automorphisms, then (ϕ = φ -1 1 • φ 2 , id) is a nontrivial automorphism of D. in this case ϕ leaves all elements of P 1 in their places. However for any j ∈ J(R) there is exactly one pair of elements x and y in P 1 such that J(y) = J(x) + {j}, implying ϕ(j) = j. But this means that all join-irreducible elements of R, and consequently all elements of L, are fixed under ϕ, thus ϕ = id, a contradiction.

Note that the statement of Lemma 6.3 cannot be trivially extended to larger k, as automorphism group of an (n, k)-decomposition may not lie in Sym(k). For example, the (3, 4)-decomposition on Figure 7 has automorphism group Sym(2) ⊗ Sym(3). As a corollary of Lemma 6.2 and Lemma 6.3 we get the following statement.

Proposition 6.4. Automorphism group of an (n, 3)-extremal lattice is a subgroup of Sym(2).

7. Actual counting.

Theorem 7.1. Let C(n) Sym(2) and C(n) id denote the number of non-isomorphic (n, 3)-extremal lattices with automorphism group Sym(2) and {id} correspondingly, and C(n) denote the total number of non-isomorphic (n, 3)-extremal lattices. Then

(i) C(n) = C(n) Sym(2) + C(n) id ; (ii) C Sym(2) (1) = C id (2) = 0 and C id (1) = C Sym(2) (2) = 1; (iii) for n ≥ 3 the following recursive formula for C Sym(2) (n) and C id (n) holds C Sym(2) (n) C id (n) = 2 n-3 2 n-3 2 n-4 2 n-4 -1 2 n-4 2 n-3 -1 C Sym(2) (n -2) C id (n -2)
Proof. Cases (i) and (ii) are obvious, and to prove (iii) we use Lemma 4.5 and count the number of non-isomorphic (n -2, 3)-decompositions, while using Lemma 6.2 to keep track of isomorphism groups of corresponding lattices. For a fixed (m, 3)-extremal lattice R there are exactly 2 m-1 ways to embed a maximal chain, as by Proposition 3.8 we have two ways to pick an element of height l for l ≥ 2. Thus, in total there are 2 2(m-1) different decompositions, but some of them may be isomorphic.

We deal with this as follows, we say that there is a space D of 2 2(m-1) root decompositions on which in the obvious way acts group A = Aut(R) ⊗ σ(2). Decompositions are isomorphic exactly when they lie in the same orbit, so we need to count the number of orbits |D/A|. Notice also that for a decomposition We split the argument into two cases. First, let Aut(R) = Sym(2), that is, there is a nontrivial automorphism α of R. Also let us denote the nontrivial permutation of (1, 2) by σ. Then |A| = 4 and • there are 2 m-1 ways to pick decomposition fixed by (id, σ), namely we pick P 1 arbitrary and put P 2 = P 1 ; • there are 2 m-1 ways to pick decomposition fixed by (α, σ), namely we pick P 1 arbitrary and put P 2 := α(P 1 ); • there are no decompositions fixed by (α, id), as well as by both (id, σ) and (α, σ), because P 1 = α(P 1 ) fo any nontrivial α.

Decompositions in first two paragraphs correspond to orbits with 2 elements and have nontrivial automorphism, and there are 2 m-1 + 2 m-1 /2 = 2 m-1 of these orbits; all others have orbits of size 4 and no nontrivial automorphism, the number of orbits is 2 2m-2 -2 m-1 -2 m-1 /4 = 2 m-2 2 m-2 -1 . Secondly, let Aut(R) = {id}. As in the previous case, we denote the nontrivial permutation of (1, 2) by σ. Then |A| = 2 and

• there are 2 m-1 ways to pick decomposition fixed by (id, σ), namely we pick P 1 arbitrary and put P 2 = P 1 .

These decompositions correspond to orbits with 1 element and have nontrivial automorphism, there number of orbits is 2 m-1 ; all others have orbits of size 2 and no nontrivial automorphism, the number of orbits is 2 2m-2 -2 m-1 /2 = 2 m-2 2 m-1 -1 . Observing that for n ≥ 3 any (n, 3)-extremal lattice is defined by (n -2, 3)-decomposition finishes the proof. Figures 8 and9 illustrate how all possible isomorphism classes of (2, 3) and (3, 3)-decompositions look. Numbers in circles below each decomposition denote the size of the corresponding orbit. In both cases automorphism group of the underlying lattice is Sym [START_REF] Albano | Why concept lattices are large: Extremal theory for the number of minimal generators and formal concepts[END_REF]. It is unpractical to make similar illustration for the case when Aut(R) is {id}, as minimal nontrivial (n, 2)-extremal lattice satisfying this condition has 5 atoms and gives rise to 136 non-isomorphic decompositions.

Proposition 2 . 5 .

 25 If L and K are lattices and K (1, ∧)-embeds into L then L[K] is a lattice. Doublings play central role in construction and structure of extremal lattices, as shown in the following theorems, which are Theorem 3 and Theorem 4 in [1] correspondingly.

Figure 2 .

 2 Figure 2. Non-isomorphic decompositions of (5, 3)-extremal lattice.

Proposition 3 . 3 .

 33 In an (n, k)-extremal lattice every element of height at least k-1 has minimal representation of size k -1. Now, we are going to explore what happens to the minimal representation of the unit as we decompose an extremal lattice. Lemma 3.4. For (n, k)-extremal lattice L, and an element a

Figure 3 .

 3 Figure 3. Illustration for Lemma 3.4 for k = 3.

Proposition 3 . 6 .

 36 For an (n, k)-extremal lattice L there is a bijection between coatoms and the elements of G(1) established as• for a coatom a there is unique a ∈ G(1) such that a ≤ a;• for b ∈ G(1) there is a unique coatom b such that L b = (b ]).Proof. For a coatom a Proposition 2.3 establishes that |J(a)| = J(L) -1, so the uniqueness of a is clear, moreover, as (J(L) -{a }) = a < 1, it follows that a ∈ G(1). The uniqueness of b for b ∈ G(1) is established in Lemma 3.1. From this lemma also follows that a = a and b = b, so these mappings are mutually inverse and indeed establish a bijection. Proposition 3.7. For an (n, k)-extremal lattice L and an element x ∈ L of height m, lower interval (x] is a (m, k)-extremal lattice.

Proposition 4 .

 4 3 yields the following useful necessary condition for isomorphism of extremal lattices.

Proposition 4 . 4 .

 44 If (n, k)-extremal lattices are isomorphic then so are their roots.

Figure 5 .

 5 Figure 5. Initial step of reconstruction of an (6, 4)-extremal lattice by its root decomposition.

Figure 6 .

 6 Figure 6. Automorphisms of a (3, 3)-extremal lattice and of its decomposition.

P 1 = P 2 = P 3 Figure 7 .

 137 Figure 7. The (3, 4)-decomposition with automorphism group Sym(2) ⊗ Sym(3).

  d with orbit O(d) holds, O(d) = |G|/ |Aut(g)|, so Aut(G) = {id} if and only if |O(d)| = |G|.

2 2 Figure 8 .

 228 Figure 8. Two possible non-isomorphic (2, 3)-decompositions.

Table 1 .

 1 Table 7 below presents the actual values for C Sym(2) , C id and C for small n. Number of non-isomorphic (n, 3)-extremal lattices.

	n C Sym(2)	C id	C
	1	0	1	1
	2	1	0	1
	3	1	0	1
	4	2	0	2
	5	4	2	6
	6	16	24	40
	7	96	464	560
	8	1280	15744	17024
	9	35840	1030656 1066496

[5] Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41(1):247-261, 1972. E-mail address, B. Chornomaz: markyz.karabas@gmail.com Department of Computer Science, V.N. Karazin Kharkiv National University, Kharkiv, Ukraine


Innovative cropping systems under a GHG emissions constraint: assessment from a long-term field trial

Educagri Editions, Dijon, France, pp

winter wheat, mustard as catch crop (CC) and spring barley.

Carbone balance of the ICSs

Formula = CO 2 emissions -C sequestration (kg CO 2 -eq.ha -1 year -1 ) Assessment using Ges'tim 3 data and SIMEOS 4 tool over a 50-year period (S.O.M. = 1.6%)

Discussion -Conclusion

In the context of this long-term field trial, agronomic strategies implemented in the L-GHG ICS were not successful at reducing GHG emissions by 50% relative to the PHEP ICS. The main goal, i.e. increase C sequestration, was not reached because biomass productions were lower than expected: (i) cover crops did not grow three years out of six because of dry conditions in spring and (ii) faba bean growth was systematically lower than expected. Because the L-GHG ICS is expressed in reference to the PHEP ICS, the performance of this system plays an important role. In this ICS, crop residue quantities were regularly higher than expected (particularly for winter wheat) and cover crops sown in wet years produced high biomass quantities.

As a result, we need to redesign the L-GHG ICS in order to satisfy the goal of GHG mitigation. However, the L-GHG ICS satisfied the environmental criteria and yields, except for faba bean, were close to expectations and match current regional levels, i.e. those required to ensure food security.

More accurate data analyses need to be carried out to better understand why faba bean yields were low. These results need to be compared to the current regional system in order to put them in perspective and to judge their actual environmental performance.

The two ICSs achieved a high score in terms of overall sustainability. The main difference occurred in the economic assessment: for some species, yields in the L-GHG ICS were regularly lower than those in the PHEP ICS. For both ICSs, the environmental assessment scored very high, with a high performance in terms of GHG emissions and C sequestration. The social assessment scored high as well. This economic disparities need to be assessed in different economic contexts in order to analyze the sensitivity of the two ICSs to a diversity of economic contexts.

The two ICSs satisfy environmental criteria:

Yields Results vary according to crop:

-cereal and oilseed rape yields were frequently as expected -faba bean yields were systematically lower than expected

Agro-environmental indicators

calculated with the Indigo®tool for the ICSs

L-GHG ICS --PHEP ICS Min values (v ≥7) to satisfy environmental criteria

Context and Objectives

To mitigate global warming and make agriculture more sustainable, innovative cropping systems (ICSs) targeting low greenhouse gas emissions (GHG) need to be designed. Our objectives were (i) to design ICSs by prototyping (Reau and Doré, 2008 1 ) and (ii) to assess them in a long-term field system experiment.

Here, we present the results of two out of the four ICSs collected over the first complete rotation (2009-2014).

  soil C sequestration → many cereals, continuous soil cover, high yield targets, no ploughing (ii) decrease N 2 O emissions → high number of legume species in the crop rotation, N fertilization improvement, crops with taproots to reduce soil compaction 2. To satisfy multiple environmental criteria: idem PHEP ICS 3. To reach yield targets matching Ile-de-France yields Crop sequence: CC, maize, triticale, CC, spring faba bean, winter oilseed rape, winter wheat, CC, winter barley. the designed ICSs (Colnenne-David C. et al., 2014 2 ).


G Y Yang

Ph. D Huazhong Z Shu

G N Han

C Toumoulin

L M Luo

Efficient Legendre moment computation for grey level images

Keywords: Legendre Moments, Fast algorithm, Recurrence formula, Grey level images

Legendre orthogonal moments have been widely used in the field of image analysis. Because their computation by a direct method is very time expensive, recent efforts have been devoted to the reduction of computational complexity.

Nevertheless, the existing algorithms are mainly focused on binary images. We propose here a new fast method for computing the Legendre moments, which is not only suitable for binary images but also for grey levels. We first set up the recurrence formula of one-dimensional (1D) Legendre moments by using the recursive property of Legendre polynomials. As a result, the 1D Legendre moments of order p, L p = L p (0), can be expressed as a linear combination of L p-1 (1) and L p-2 (0). Based on this relationship, the 1D Legendre moments L p (0) is thus obtained from the array of L 1 (a) and L 0 (a) where a is an integer number less than p. To further decrease the computation complexity, an algorithm, in which no multiplication is required, is used to compute these quantities. The method is then extended to the calculation of the two-dimensional Legendre moments L pq . We show that the proposed method is more efficient than the direct method.

Introduction

Since Hu introduced the moment invariants [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF], moments and moment functions of image intensity values have been successfully and widely used in the field of image analysis, such as object recognition, object representation, edge detection [START_REF] Prokop | A survey of moment based techniques for unoccluded object representation[END_REF].

Orthogonal moments (e.g. Legendre moment and Zernike moment) can be used to represent an image with the minimum amount of information redundancy [START_REF] Teague | Image analysis via the general theory of moments[END_REF]. Since the computation of orthogonal moments of a two-dimensional (2D) image by a direct method involves a significant amount of arithmetic operations, some fast algorithms have been developed to reduce the computational complexity. However, the existing methods for fast computation of Legendre moments are mainly focused on binary image [START_REF] Mukundan | Fast computation of Legendre and Zernike moments[END_REF][START_REF] Shu | A new fast method for computing Legendre moments[END_REF][START_REF] Zhou | Two new algorithms for efficient computation of Legendre moments[END_REF]. Now the moments of a grey level image are also used in many applications, such as texture analysis [START_REF] Martinez | Efficient computation of local geometric moments[END_REF], therefore, we propose a fast algorithm for computing the Legendre moments for grey level images. The principle is as follows.

The recurrence formula of one-dimensional (1D) Legendre moments is firstly established by using the recursive property of Legendre polynomials. The 1D Legendre moments of order p, L p = L p (0), is expressed as a linear combination of L p-1 [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF] and L p-2 (0). Based on this relationship, the 1D Legendre moments L p (0) can thus be obtained from the array of L 1 (a) and L 0 (a) where a is an integer number less than p. An algorithm based on a systolic array in which no multiplication is required is used to compute these quantities. We propose then an extension of the method to the 2D Legendre moment L pq computation.

The remainder of this paper is organized as follows. In Section 2, we first describe a new approach for computing 1D Legendre moments for a 1D signal, and then extend the method to the 2D Legendre moment calculation. Section 3 gives the detailed analysis of the computational complexity and some experimental results.

Section 4 provides some concluding remarks.

Fast computation of 2D Legendre moments

The (p+q)th-order Legendre moment of an image with intensity function f(x, y) is defined by [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF] where P p (x) is pth order Legendre polynomial given by

! ! " " + + = 1 1 1 1 ) , ( ) ( ) ( 4 ) 1 2 )( 1 2 ( dxdy y x f y P x P q p L q p pq
] 1 , 1 [ , )! 2 ( )! ( ! )! 2 2 ( ) 1 ( 2 1 ) ( 2 / 0 2 " " ! ! ! ! = # = ! x x k p k p k k p x P n k k p k p p . ( 2
)
For a digital image of size N!N, Eq. ( 1) can be approximated by

!! = = " + + = N i j i j q N j i p pq y x f y P x P N q p L 1 1 2 ) , ( ) ( ) ( ) 1 ( ) 1 2 )( 1 2 ( (3)
with x i = (2i -N -1)/(N -1), y j = (2j -N -1)/(N -1).

The Legendre polynomial obeys the following recursive relation

1 ), ( 1 ) ( 1 1 2 ) ( 1 1 ! + " + + = " + p x P p p x xP p p x P p p p (4) with P 0 (x) = 1, P 1 (x) = x.
In the following, we present an algorithm for the fast calculation of the 2D Legendre moment for grey level images. For the sake of simplicity, let us first consider the computation of the 1D Legendre moments.

For a 1D discrete signal f(x i ) 1 " i " N the 1D Legendre moment is given by

) ( ) ( 1 1 2 1 i N i i p p x f x P N p L ! = " + = (5)
Let us now introduce the following notation

) ( ) ( 1 1 2 ) ( 1 i N i i p a i p x f x P x N p a L ! = " + = (6)
It can be easily seen that L p = L p (0). Thus, we turn to the fast computation of L p (a) in the following.

Substitution of Eq. ( 4) into Eq. ( 6) yields

! ! ! = = " " + = " " " " " + " " " " + = # $ % & ' ( " " " " + = N i N i i i p a i i i p a i i N i i p i p i a i p x f x P x N p p p p p x f x P x N p p p x f x P p p x P x p p x N p a L 1 1 2 1 1 1 2 1 ) ( ) ( 1 3 2 3 2 1 2 1 ) ( ) ( 1 1 2 1 2 ) ( ) ( 1 ) ( 1 2 1 1 2 ) ( (7)
therefore, we have the following recurrence relation for p # 2

! " # $ % & ' ' ' + + = ' ' ) ( 3 2 1 ) 1 ( 1 2 ) ( 2 1 a L p p a L p p a L p p p (8) with ! = " = " = N i N i a i a G N x f x N a L 1 0 ) ( 1 1 ) ( 1 1 ) ( (9)
) 1 ( 1 3 ) ( 1 3 ) ( 1 1 1 + " = " = ! = + a G N x f x N a L N N i i a i (10) ! = = N i i a i N x f x a G 1 ) ( ) ( (11)
The above discussion shows that the 1D Legendre moments L p = L p (0), for p # 2, can be deduced from the values of L 0 (a) and L 1 (a) where a is an integer less than p, L 0 (a) and L 1 (a) being obtained by G N (a). The calculation of Eq. ( 11) leads to distinguish two different cases: N odd and N even.

(1) N = 2L + 1

Since x i = (2i -N -1)/(N -1), we deduce from Eq. ( 11) that

[ ] [ ] ! ! ! " ! ! ! # $ + + + + + + + + + + + + + + + + + = + + = % & ' ( ) * + + = + + + + + + + = + = + , , even is , ) ( ... ) ( 2 ) ( ) ( ... ) ( ) 1 ( ) ( 1 odd is , ) ( ... ) ( 2 ) ( ) ( ... ) ( ) 1 ( ) ( 1 ) ( ) 1 ( 1 ) ( 2 2 2 2 ) ( 1 2 3 2 2 1 1 2 3 2 2 1 1 2 1 1 2 1 1 2 a x f L x f x f x f x f L x f L L a x f L x f x f x f x f L x f L L x f L i L x f L L i a G L a L a L L a a a L a L a L L a a a L i i a a L i i a L (12)
Eq. ( 12) can be rewritten as

! ! " ! ! # $ = % % = = + L i i a a L i i a a L a x g i L a x g i L a G 1 2 1 1 1 2 even is ), ( 1 odd is ), ( 1
) ( ( 13
) with L i x f x f x g i L i L i ,..., 2 , 1 ) ( ) ( ) ( 1 1 1
= ! = + ! + + (14) L i x f x f x g i L i L i ,..., 2 , 1 ) ( ) ( ) ( 1 1 2 = + = + ! + + (15) (2) N = 2L Eq. (11) becomes [ ] [ ] ! ! ! ! " ! ! ! ! # $ + + + + + + + + + + + + + + + + + + + + + + + = + + + = % & ' ( ) * + + + = + + + + = = , , even is , ) ( ) 1 2 ( ... ) ( 3 ) ( ) ( ... ) ( ) 3 2 ( ) ( ) 1 2 ( ) 1 2 ( 1 odd is , ) ( ) 1 2 ( ... ) ( 3 ) ( ) ( ... ) ( ) 3 2 ( ) ( ) 1 2 ( ) 1 2 ( 1 ) ( ) 1 2 2 ( ) 1 2 ( 1 ) ( 1 2 1 2 2 ) ( 2 2 1 2 1 2 2 1 2 1 2 1 2 1 2 a x f L x f x f x f x f L x f L L a x f L x f x f x f x f L x f L L x f L i L x f L L i a G L a L a L L a a a L a L a L L a a a L i i a a L i i a L (16) or ! ! " ! ! # $ % % % % = & & = = L i i a a L i i a a L a x g i L a x g i L a G 1 4 1 3 2 even is ), ( ) 1 2 ( ) 1 2 ( 1 odd is ), ( ) 1 2 ( ) 1 2 ( 1 ) ( (17)
with

L i x f x f x g i L i L i ,..., 2 , 1 ) ( ) ( ) ( 1 3 = ! = + ! + (18) L i x f x f x g i L i L i ,..., 2 , 1 ) ( ) ( ) ( 1 4 = + = + ! + (19)
We discuss, in the following two subsections, the way to efficiently calculate G N (a) from Eqs. ( 13) or (17), according to the different modalities of the 1D signal

f(x i ). 2.1. f(x i ) = 1, for i = 1, 2, …, N.
In this case, Eqs. ( 13) and (17) become

! " ! # $ = % = + L i a a L a i L a a G 1 1 2 even is , 2 odd is , 0 ) ( (20)
! "

! # $ % & ' ( ) * + + = + + = , , , = = = L i L i L i a a a a a a L a i i L i L a a G 1 2 1 1 2 even is , 2 ) 1 2 ( 2 ) 1 2 ( ) 1 2 ( 2 odd is , 0 ) ( (21)
The above equations show that to obtain the values of G N (a), we only need to calculate the following summation

! = = M i a M i a H 1 ) ( (22)
For the computation of Eq. ( 22), which is just the 1D geometric moment of order a of a 'binary' signal, we use the formulae proposed by Spiliotis and Mertzios [START_REF] Spiliotis | Real-time computation of two-Dimension Moments on binary images by using image block representation[END_REF] 30

) 1 3 3 )( 1 2 )( 1 ( ) 4 ( , 4 ) 1 ( ) 3 ( 6 ) 1 2 )( 1 ( ) 2 ( , 2 ) 1 ( ) 1 ( 2 2 2 + + + + = + = + + = + = M M M M M H M M H M M M H M M H M M M M (23)
and for a # 4, the recurrence formula

) 1 ( ) 1 ( ) ( 1 ... ) 2 ( 2 1 ) 1 ( 1 1 1 + ! + = " " # $ % % & ' + + + " " # $ % % & ' + + " " # $ % % & ' + + M M a H a a H a H a a M M M (24) where )! ( ! ! j i j i j i ! = " " # $ % % & '
is a combination number.

2. 2. f(x i ) $ f(x j ) for some i $ j

Eq. ( 17) can be written as

! ! " ! ! # $ % % = & & = = L i i a a L i i a a L a x h i L a x h i L a G 2 1 2 2 1 1 2 even is ), ( ) 1 2 ( 1 odd is ), ( ) 1 2 ( 1 ) ( (25)
where

! " # = + otherwise 0, odd is if ), ( ) ( 2 / ) 1 ( 3 1 i x g x h i i (26) ! " # = + otherwise 0, odd is if ), ( ) ( 2 / ) 1 ( 4 2 i x g x h i i (27)
Here g 3 (x i ) and g 4 (x i ) are given by Eqs. ( 18) and (19), respectively.

It can be seen from Eqs. (13) and (25) that we need to calculate the summation of the form

! = = M i i a M x g i a S 1 ) ( ) ( (28)
Note that S M (a) is the 1D geometric moment of order a of an arbitrary 1D signal.

Since many algorithms are available in the literature to speed up the computation of Eq. ( 28), we decided to choose the method proposed by Chan et al. [START_REF] Chan | An all adder systolic structure for fast computation of moments[END_REF]. Their method is able to efficiently compute the grey level image moments. It makes use of a systolic array for computing the moments in which no multiplication is required. We recently applied such a method to efficiently calculating the Zernike moments [START_REF] Gu | A novel algorithm for fast computation of Zernike moments[END_REF].

Thus, the 1D Legendre moments L p (0), for 0 " p " M (M denoting the maximal order we want to calculate), can be efficiently obtained using the previously presented algorithm. Fig. 1 shows the computation order of L p (0) for p varied from 0 to 5.

Let us now describe the method for fast computation of the 2D Legendre moments L pq . The double summation in Eq. ( 3) can be split into the following separate form

! ! ! !! = = = = = " + = # # $ % & & ' ( " + " + = " + + = N i iq i p N i N j j i j q i p N i j i j q N j i p pq Y x P N p y x f y P N q x P N p y x f y P x P N q p L 1 1 1 1 1 2 ) ( 1 1 2 ) , ( ) ( 1 1 2 ) ( 1 1 2 ) , ( ) ( ) ( ) 1 ( ) 1 2 )( 1 2 ( (29)
where Y iq is the qth-order row moment of row i given by

! = " + = N j j i j p iq y x f y P N q Y 1 ) , ( ) ( 1 1 2 (30)
These equations show that the computation of 2D Legendre moments of grey level images can be decomposed into two steps. First, the 1D Legendre moments Y iq , for 1" i " N and 0 " q " M, are computed by using the algorithm described in Subsections 2.1 and 2.2, according to the different image modalities of f(x i , y j ). Then, the row moments Y iq are applied to compute the 2D Legendre moments L pq . That is, after the first step, the 2D Legendre moments L pq can be calculated as a 1D moments by setting the image intensity function f(x i , y j ) to the Y iq previously computed. The algorithm for computing the 2D Legendre moments is depicted in figure 2. It should be pointed out that such a strategy can also be realized in parallel.

Computation complexity and experimental results

Let the image size be N!N pixels, and M the maximum order of Legendre moments to be calculated. The direct computation of Eq. ( 3) requires approximately M 2 N 2 /2 additions and multiplications, respectively. In the following, we give a detailed analysis of the computational complexity of our algorithm.

We first briefly describe the computational complexity of the algorithm when applied to binary images. From Ref. [START_REF] Spiliotis | Real-time computation of two-Dimension Moments on binary images by using image block representation[END_REF], the computation of the geometrical moments up to the order M of a binary image with N!N pixels, requires approximately 4M power calculations, 2M 2 multiplications, and M 2 additions (note that these numbers are not dependent on N). The computation of the 2D Legendre moments L pq , by using the recursive algorithm, needs O(NM 3 ) additions and O(M 3 ) multiplications.

Therefore, the algorithm is very efficient in comparison with the direct method.

The computational complexity of the method for grey level images takes into account the parity of N.

(1) For odd value of N Let us first consider the number of operations required in the computation of ith row moments Y iq (0 " q " M). Note that the functions g 1 (x) and g 2 (x) defined by Eqs. When all Y iq , for 1 " i " N and 0 " q " M, are obtained, the 2D Legendre moments L pq , for 0 " p+q " M, can be calculated in a similar way. The corresponding addition and multiplication numbers are M 3 N/12+M 2 N and 2M 3 /3+2M 2 .

Accordingly, the overall computation makes use of M 2 N 2 /2+M 3 N/12 additions and 2M 2 N+2M 3 /3 multiplications approximately.

(2) For even value of N

The functions h 1 (x) and h 2 (x), that are defined by Eqs. ( 26) and (27), will be used in the computation of G N (a). The only difference between case (2) and case (1) is that Eq. ( 25) is adopted instead of (13). The computation of Eq. (25) requires twice additions more than that is needed in Eq. (13). Thus, the total computational complexity is approximately M 2 N 2 +M 3 N/6 additions and 2M 2 N+2M 3 /3 multiplications.

The computational complexities of the proposed algorithm and the direct method are summarized in Table 1. The displayed values show that the new algorithm uses a much fewer number of multiplications than the direct method, what consequently leads to a more efficient computation time.

We illustrate the algorithm efficiency with two binary and grey level images of size 256!256, respectively (first column of Table 2). The first one displays a Chinese character while the second one shows some butterflies. In both cases, the reconstruction of the image was performed using the following relation

!! = = " " = M p p q j q i q p q q p j i y P x P L y x f 0 0 , ) ( ) ( ) , ( ˆ (31)
The results are provided for different orders of the moments, and are shown in Table 2.

Conclusion

In this paper, a new fast algorithm for computing the 2D Legendre moments of grey level images has been presented. The proposed method has the following advantages:

(1) The 1D Legendre moments can be obtained by a recurrence relation. Moreover, the initial value used in the iterative method can be calculated with additions only.

(2) The 2D moment computation can be decomposed into two 1D moment calculation.

(3) It does not require so many multiplications that as the direct method, leading thus to a better efficiency in terms of computational time.

(4) The algorithm can be implemented in parallel.

L 2 (3) L 1 (2)
L 0 (3) L 1 [START_REF] Mukundan | Fast computation of Legendre and Zernike moments[END_REF] for i = 1 to N computing L 0 (q) (0 " q " M-2) and L 1 (q) (0 " q " M-1) using Eqs. ( 9) and [START_REF] Gu | A novel algorithm for fast computation of Zernike moments[END_REF] for q = 0 to M computing Y iq for each row i of the image using Eq. ( 8) endfor endfor for p = 0 to M computing L 0 (a) (0 " a " M-p-2) and L 1 (a) (0 " a " M-p-1) using Eqs. ( 9) and (10) from pre-calculated Y iq for q = 0 to Mp computing the 2D Legendre moments L pq using recursive method endfor endfor Fig. 2. Algorithm for computing L pq

(

  14) and (15) are used for odd value of N. To obtain the values of Y iq , we must calculate G N (a) with Eq. (13) for 0 " a " M. This step needs only (M+1)2 (N/2-1) additions. The computation of Y iq (for 0 " q " M) from the pre-calculated G N (a), requires M(M-1)/2 additions and 2M(M-1) multiplications. Therefore, the computation of N rows Y iq (for 1 " i " N) needs approximately M 2 (N 2 +N)/2 additions and 2M 2 N multiplications.

Fig. 1 .

 1 Fig. 1. Computation process of L p (0) with p from 0 to 5. Grey level boxes correspond