Bernard Mourrain
email: bernard.mourrain@inria.fr

Philippe Tr Ébuchet

Philippe Trébuchet
email: philippe.trebuchet@lip6.fr

BORDER BASIS REPRESENTATION OF A GENERAL QUOTIENT ALGEBRA

In this paper, we generalized the construction of border bases to non-zero dimensional ideals for normal forms compatible with the degree, tackling the remaining obstacle for a general application of border basis methods. First, we give conditions to have a border basis up to a given degree. Next, we describe a new stopping criteria to determine when the reduction with respect to the leading terms is a normal form. This test based on the persistence and regularity theorems of Gotzmann yields a new algorithm for computing a border basis of any ideal, which proceeds incrementally degree by degree until its regularity. We detail it, prove its correctness, present its implementation and report some experimentations which illustrate its practical good behavior.

Introduction

Solving polynomial equations is an ubiquitous problem which has a long mathematical history and many applications. An important approach to find all the (complex) solutions of a system of polynomial equations f 1 (x 1 , . . . , x n ) = 0, . . . , f s (x 1 , . . . , x n ) = 0 is based on so-called "solving by quotient algebra" techniques. In this family of methods, the (complex) solutions of the system are recovered from the analysis of the quotient structure R/I where R = K[x 1 , . . . , x n ] is the ring of polynomials and I = (f 1 , . . . , f s ) is the ideal generated by the polynomials f 1 , . . . , f s .

This approach involves the construction of a projection with kernel I which maps R onto a vector space B spanned by a basis B ⊂ R (usually of monomials) so that we have R = B ⊕ I. Such a projection, also called a normal form modulo the ideal I, can for instance be defined as a reduction with respect to a family of polynomials of I. F.S Macaulay [START_REF] Macaulay | The Algebraic Theory of Modular Systems[END_REF] introduced the notion of an H-basis, which consists of generators of the ideal I with a normal form property for the reduction with respect to the components of highest degree. Replacing the usual graduation by a graduation associated to a monomial ordering, Gröbner bases (see [START_REF] Buchberger | An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal[END_REF] or [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF] for a modern presentation) provide also a normal form property for the reduction with respect to the leading monomials for the given monomial ordering. By the simplicity of the reduction and the combinatorial information it can provide on R/I, it became a classical tool in computer algebra and effective commutative algebra. H-bases have not been as extensively used as there is no general algorithm for computing it : in [START_REF] Möller | H-bases for polynomial interpolation and system solving[END_REF] an algorithm is proposed but it relies on the a priori knowledge of a system of generator of the first syzygy module which cannot be expected to be known in advance in most situations and in [START_REF] Barry | Numerical calculation of h-bases for positive dimensional varieties[END_REF] a numerical method is proposed provided some isolated points of the variety are known which also, cannot be expected to be easily found.

A less classical projection technique called border basis has been developed mostly over the last decade (see eg. [START_REF] Marinari | Gröbner bases of ideals given by dual bases[END_REF][START_REF] Mourrain | A new criterion for normal form algorithms[END_REF][START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF][START_REF] Kehrein | Characterizations of border bases[END_REF][START_REF] Kreuzer | Computational Commutative Algebra 2[END_REF][START_REF] Kehrein | Computing border bases[END_REF][START_REF] Mourrain | Symbolic-Numeric Computation, chapter Pythagore's Dilemma[END_REF][START_REF] Chen | Border bases of positive dimensional polynomial ideals[END_REF][START_REF] Mourrain | Stable normal forms for polynomial system solving[END_REF][START_REF] Kaspar | Computing border bases without using a term ordering[END_REF]). One of the motivations was to handle numerical instability issues which structurally appear in Gröbner basis computation when dealing with approximate coefficients, as this is the case in many applications [START_REF] Mourrain | Symbolic-Numeric Computation, chapter Pythagore's Dilemma[END_REF]. The main difference with previous graded reduction techniques is that the normal form property is related to the commutation property of operators of multiplication [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF]. The approach offers more freedom to choose a basis B of the quotient algebra R/I adapted to the geometry of the solutions and provides a numerically stable normal form algorithm [START_REF] Mourrain | Stable normal forms for polynomial system solving[END_REF]. The border basis approach can be seen as a generalization of Gröbner basis computation in the case of zero-dimensional ideals. Indeed if the projection is compatible with a monomial ordering, a border basis is a Gröbner basis for this monomial ordering. Unfortunately, their study and construction were essentially restricted to zero-dimensional ideals. The goal of the paper is to describe a new method to compute border basis for any ideal.

Contributions. The border bases that we consider hereafter are related to a set B of monomials connected to 1 (see Section 2). They are more general than the one considered in [START_REF] Kreuzer | Computational Commutative Algebra 2[END_REF][START_REF] Kehrein | Characterizations of border bases[END_REF][START_REF] Kehrein | Computing border bases[END_REF][START_REF] Chen | Border bases of positive dimensional polynomial ideals[END_REF][START_REF] Kaspar | Computing border bases without using a term ordering[END_REF], where B is assumed to be a set of monomials stable by division (called an order ideal).

We will not assume that B is known a priori or that the projection is compatible with a monomial ordering as in [START_REF] Kreuzer | Computational Commutative Algebra 2[END_REF][START_REF] Chen | Border bases of positive dimensional polynomial ideals[END_REF], since this leads to the construction of Gröbner bases, with well-developed monomial rewriting techniques but also with numerical instability problems that we want to avoid.

For the sake of simplicity, we restrict the present article to projections compatible with the usual degree. This is not a conceptual limitation.

So far, border bases have been developed essentially for zero-dimensional ideals, except in [START_REF] Chen | Border bases of positive dimensional polynomial ideals[END_REF] where the projection is compatible with a monomial ordering and thus leads to Gröbner basis computation.

The main contribution of this paper is to provide a new criterion of border bases for any projection compatible with the degree on a vector space spanned by a set B of monomials connected to 1. This criterion which applies to any ideal is based on the persistence and regularity theorems of G. Gotzmann [START_REF] Gotzmann | Eine Bedingung für die Flachheit und das Hilbertpolynom eines graduierten Ringes[END_REF].

The algorithm that we propose is an extension of the algorithm in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] for zerodimensional ideals. It exploits a new characterization of border bases up to a given degree, and proceeds incrementally degree by degree until the regularity criteria is satisfied. It is complete and has no possible case of "failure" as the algorithm for zero-dimensional ideals in [START_REF] Kaspar | Computing border bases without using a term ordering[END_REF]. As a byproduct, we obtain the Hilbert polynomial of the graded part of the ideal and thus the dimension and the degree of the solution set.

An implementation in C++ is also provided in the package borderbasix of the project Mathemagix and we report on some experimentations which illustrate the practical good behavior of the method.

The paper is organized as follows. In the next section, we give the definitions we need. In Section 3, we prove the theoretical results involved in the algorithm, which is described in Section 4. In Section 5, we report on some benchmarks of an implementation before the concluding section.

Notations

Let M be the set of monomials in the variables x 1 , . . . , x n . An element of M is of the form

x α = x α1 1 • • • x αn n with α = (α 1 , . . . , α n ) ∈ N n . Its degree is |α| = α 1 + • • • + α n . Let R = K[x 1 , . . . ,
x n ] be the ring of polynomials in the variables x 1 , . . . , x n with coefficients in a field K. For p = α∈A p α x α with p α = 0, A is the support of p and deg(p) = max α∈A |α|.

For any set S, #S is its number of elements of S.

For d ∈ N and F ⊂ R, let F ≤d (resp. F d ) be the set of polynomials in F of degree ≤ d (resp. d).

For f ∈ R, let f T be the homogeneous component of f of highest degree. Similarly for a set

F ⊂ R, F T = {f T | f ∈ F }.
For F ⊂ R, let F be the K-vector space spanned by F . Let

F + = F ∪ x 1 F ∪ • • • x n F and ∂F = F + \ F . For d ∈ N + , let F ≤d = {m f | m ∈ M, f ∈ F, deg(m f ) ≤ d} and F d = F ≤d \ F ≤d-1 . A set B ⊂ M is connected to 1 if 1 ∈ B and ∀m ∈ B \ {1}, there exists 1 ≤ i ≤ n and m ′ ∈ B, such that m = x i m ′ .
For a sequence F of polynomials in R and a sequence B of monomials in M, (F |B) is the matrix of coefficients of the polynomials in F for the monomials of B; a row of this matrix represents the coefficients of a polynomial in F ; the order for the rows (resp. columns) is the order of the elements in the sequence F (resp. B).

Theoretical Results

Let B ⊂ M be a set of monomials connected to 1 and let d ∈ N. In this section, we assume that we are given a projection π : B + ≤d → B ≤d such that π • π = π and π | B ≤d is the identity map, which is compatible with the degree: ∀b ∈ B + ≤d , deg(π(b)) ≤ deg(b). The kernel ker π of this projection is spanned by the elements:

f α = x α -π(x α ), x α ∈ (∂B) ≤d .
We denote by F this generating set of polynomials of ker π and call it the rewriting family of π.

Our objective is to characterize the projections π which are the restriction of a projection π : R → B such that I := ker π is the ideal generated by ker π. In such a case, we have R = B ⊕ I and π is a normal form modulo the ideal I.

The main idea behind border basis techniques is to relate this normal form property to commutation properties of multiplication operators [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF]. We define the operator of multiplication by x i associated to π as:

M i : B ≤d-1 → B ≤d b → π(x i b).
As π is compatible with the degree, the image by M i of an element of degree ≤ k is of degree

≤ k + 1 for 0 ≤ k < d. For a monomial x α = x α1 1 • • • x αn n ∈ M of degree ≤ d, we define x α (M) := M α1 1 • • • • • M αn n .
It is an operator from B ≤d-|α| to B ≤d . We extend this construction by linearity and for any p ∈ R ≤d , we define

p(M) : B ≤d-deg(p) → B ≤d .
As we will see, the commutation property of the multiplication operators M i is related to the projection of the following polynomials. Definition 3.1. For F ⊂ R and B ⊂ M, let C B (F ) be the set of polynomials in B + which are of the form

1) x i f with f ∈ F or 2) x i f -x j f ′ with f, f ′ ∈ F , 1 ≤ i < j ≤ n.
The polynomials in C B (F ) are called the commutation polynomials of F for B.

The subset of C B (F ) satisfying condition 1 (resp. 2) is denote by C 1 B (F ) (resp. C 2 B (F )), so that C B (F ) = C 1 B (F ) ∪ C 2 B (F ).
In the following, the set B will be fixed and we will simply write C B (F ) = C(F ). From this definition, we have

C(F ) ⊂ F + ∩ B + .
Next, we describe different equivalent conditions for a normal form in degree ≤ d. This theorem summarizes results which can be deduced from results in [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF], [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF], [START_REF] Mourrain | Stable normal forms for polynomial system solving[END_REF].

Theorem 3.2. Let d ≥ 2, let B be a subset of M connected to 1, let π : B + ≤d →
B ≤d be a projection and let F be the rewriting family of π. The following conditions are equivalent:

(1) (M i • M j -M j • M i ) | B ≤d-2 = 0 for 1 ≤ i < j ≤ n, (2
) there exists a unique projection π : R ≤d → B ≤d such that the restriction of π to B + ≤d is π and

ker π = F ≤d , (3) (F ≤d-1 ) + ∩ B + ⊂ F , (4) ∀r ∈ C(F ≤d-1 ), π(r) = 0. Proof. 1) ⇒ 2) : As B is connected to 1, 1 ∈ B and we can define π : R ≤d → B ≤d p → p(M)(1)
This construction is independent of the order in which we compose the operators M i since they are commuting.

Let us show that π is a projection of R ≤d on B ≤d , which extends π and such that ker π = F ≤d .

We first prove by induction on the degree that ∀m ∈ B, π(m) = m. The monomial of degree 0 of B is 1 and by definition π(1) = 1. The property is true for degree 0. Assume that it is true for degree 0 ≤ k -1 < d and let m ∈ B be a monomial of degree k. As B is connected to 1, there exists 1 ≤ i ≤ n and m ′ ∈ B of degree k -1 such that m = x i m ′ . As the operators M i are commuting and as π | B ≤d = Id, we have by induction hypothesis

π(m) = M i (m ′ (M)(1)) = π(x i m ′ ) = m. In particular, for any b ∈ B we have b(M)(1) = b. We now prove that ∀m ∈ (∂B) ≤d , π(m) = π(m). As m ∈ ∂B, there exist m ∈ B and 0 ≤ i ≤ n such that m = x i m. Thus we have π(m) = M i (m ′ (M)(1)) = π(x i m ′ ) = π(m).
In the next step, we prove that F ≤d ⊂ ker π. For m ∈ M and x α ∈ ∂B with deg(m) + |α| ≤ d, we show that m (x α -π(x α )) ∈ ker π: As π coincides with π on

B + ≤d and π(x α ) ∈ B , we have π(m (x α -π(x α ))) = m(M) • M α (1) -m(M)(π(x α )(M)(1)) = m(M) • M α (1) -m(M)(π(x α )) = m(M) • M α (1) -m(M)(π(x α )) = m(M) • M α (1) -m(M)(M α (1)) = 0 Finally, we prove that R ≤d = B ≤d ⊕ F ≤d . For any m ∈ M of degree 1 ≤ k ≤ d, there exist m ′ ∈ M of degree k -1 and 1 ≤ i ≤ n such that m = x i m ′ . We have m -π(m) = x i (m ′ -π(m ′ )) + (x i π(m ′ ) -π(x i m ′ ))
. By induction on the degree, we have (m

′ -π(m ′ )) ∈ F ≤k-1 and x i π(m ′ ) - π(x i m ′ ) = x i π(m ′ ) -π(x i π(m ′ )) ∈ F.
This shows that m -π(m) ∈ F ≤k . As for any p ∈ R ≤d , p = π(p) + p -π(p), we deduce that R ≤d = B ≤d + F ≤d . As F ≤d ⊂ ker π and π| B ≤d = Id, we have

R ≤d = B ≤d ⊕ F ≤d , with F ≤d = ker π. 2) ⇒ 3) : Let f ∈ (F ≤d-1 ) + ∩ B + . Then as (F ≤d-1 ) + ⊂ F ≤d = ker π, we have π(f ) = 0. But π coincides with π on B + so that we have π(f ) = 0, which shows that f ∈ ker π = F . 3) ⇒ 4) : Clearly, if r ∈ C(F ≤d-1 ) then r ∈ (F ≤d-1 ) + ∩ B + . By hypothesis (3), r ∈ F = ker π and π(r) = 0. 4) ⇒ 1) : Let m ∈ B of degree ≤ d -2 and 1 ≤ i < j ≤ n. Suppose that m 1 := x i m ∈ ∂B and m 2 := x j m ∈ ∂B. Let f 1 = m 1 -π(m 1 ), f 2 = m 2 -π(m 2 ) ∈ F . As x i m 2 = x j m 1 = x i x j m, we have (M i • M j -M j • M i )(m) = π(x i π(m 2 )) -π(x j π(m 1 )) = π(x i (m 2 -f 2 ) -x j (m 1 -f 1 )) = π(x j f 1 -x i f 2 ). As x j f 1 -x i f 2 = x i π(m 2 ) -x j π(m 1 ) ∈ C(F ≤d ), the hypothesis (4) implies that π(x j f 1 -x i f 2 ) = 0. A similar argument applies if x i m ∈ B or x j m ∈ B. Conse- quently, we have (M i • M j -M j • M i ) | B ≤d-2 = 0.
If one of these (equivalent) conditions is satisfied, we say that the rewriting family F is a border basis in degree ≤ d for B. Remark 3.3. As a border basis in degree ≤ d contains a border basis in degree ≤ k for 0 ≤ k ≤ d, this theorem implies that the restriction of π to R ≤k is the projection onto B ≤k along F ≤k . Remark 3.4. We can define a projection π : R ≤d → B ≤d such that for any x α ∈ M ≤d , π(x α ) = M α (1) ∈ B ≤d and we extend it by linearity on R ≤d . Any order in the composition of the operators M i can be used to define a projection π on a specific monomial of degree ≤ d. For any of these choices, we have a projection such that ∀p ∈ R ≤d , p -π(p) ∈ F ≤d (see 3).

However, if the operators M i commute in degree ≤ d -2, then this projection π is uniquely defined.

We are now going to show that a border basis in degree ≤ d is an H-basis when d is big enough. The notion of H-basis introduced by F.S. Macaulay [START_REF] Macaulay | The Algebraic Theory of Modular Systems[END_REF] corresponds to a generating set of an ideal, which allows to compute normal forms by reduction with respect to the components of highest degree. We recall that F is an H-basis of an ideal I if F ⊂ I and (F T ) = I T . A characterization of an H-basis involves syzygies that we define now:

Definition 3.5. For F = {f 1 , . . . , f l } ⊂ R and k ∈ N, Syz ≤k (F ) = { r = (r 1 , . . . , r l ) ∈ R l | l i=1 r i f i = 0 and deg(r i f i ) ≤ k for 1 ≤ i ≤ l }
denotes the vector space of syzygies of F in degree ≤ k.

We denote by Syz(F ) = ∪ k Syz ≤k (F ) the R-module of syzygies of F . We define by induction the i-th module of syzygies of F as the syzygy module of a minimal set of generators of the (i -1)-th module of syzygies, the 1-st syzygy module of F being Syz(F ) (see eg. [START_REF] Eisenbud | The geometry of syzygies[END_REF]).

For

H = {h 1 , . . . , h l } ⊂ R and r ∈ Syz(F ), let r(H) = l i=1 r i h i ∈ R.
Here is a characterization of H-basis in terms of syzygies (see [START_REF] Macaulay | The Algebraic Theory of Modular Systems[END_REF], [START_REF] Möller | H-bases for polynomial interpolation and system solving[END_REF] or [START_REF] Elkadi | Introduction à la résolution des systèmes polynomiaux[END_REF][Theorem 2.14, p.33]):

Theorem 3.6. Let F ⊂ R, G = F T , I = (F ) and {r 1 , . . . , r s } a generating family of Syz(G). F is an H-basis of I iff for all 1 ≤ i ≤ s, r i (F ) ∈ F ≤li where l i = deg(r i (F )).
We prove now that for a border basis F in degree ≤ d, the syzygies of F T lift to syzygies of F : Proposition 3.7. Assume that F is a border basis in degree ≤ d. Then for any r ∈ Syz ≤k (G), 0 ≤ k ≤ d, we have r(F ) ∈ F ≤l where l = deg(r(F )) < k.

Proof. If F is a border basis in degree ≤ d, by Theorem 3.2(2), π(r(F )) = 0 since r(F ) ∈ F ≤k . As r(G) = 0, r(F ) is of degree l < k. By remark 3.3, as π is the projection from R ≤l onto B ≤l along F ≤l , we deduce that r(F ) ∈ F ≤l . This proposition allows us to show that a border basis in degree ≤ d is an H-basis when d is bigger than the regularity of (F T ).

We recall that the (Castelnuovo-Mumford) regularity of an homogeneous ideal J ⊂ R, denoted reg(J), is the minimum m such that J is generated in degree ≤ m, and the k-th module of syzygies of J is generated in degree ≤ m+ k for k = 1, . . . , n (see [START_REF] Eisenbud | The geometry of syzygies[END_REF][chap. 4, p. 55]). We say that J is d-regular if reg(J) ≤ d. Theorem 3.8. Let B be a subset of M connected to 1, F a border basis in degree ≤ d for B, and

G = F T . If J = (G) is (d -1)-regular then F is an H-basis of I = (F ).
Proof. By definition of the regularity, Syz(G) has a generating set of syzygies r 1 , . . . , r s ∈ Syz ≤d (G) of degree less than d. By Proposition 3.7, we have r i (F ) ∈ F ≤li where l i = deg(r i (F )) < d and we deduce by Theorem 3.6 that F is an H-basis for I = (F ). Corollary 3.9. Let B be a subset of M connected to 1, F a border basis in degree

≤ d for B and G = F T . Then B k is a basis of R k /(G) k for 0 ≤ k ≤ d.
Proof. By Remark 3.3, for any polynomial p ∈ R ≤k of degree k ≤ d, we have p = f + b with f ∈ F ≤k , b ∈ B ≤k . Taking the components of degree k of each term in this decomposition, we have

p T = f k + b k with f k ∈ G k , b k ∈ B k . This shows that R k = G k + B k . Let p = G k ∩ B k . As p ∈ G k there exists f ∈ F ≤k such that p ′ = p -f ∈ R ≤k-1 so that π(p) = π(p ′ ) = p with p ∈ R k and p ′ ∈ R ≤k-1 .
As π is compatible with the degree, this implies that p = p ′ = 0 and we have

R k = G k ⊕ B k . As G is an homogeneous family of polynomials G k = (G) k and B k is a monomial basis of R k /(G) k .
Our next objective is to characterize the regularity of a homogeneous ideal J in terms of the dimension H R/J (d) = dim R d /J d (H R/J is called the Hilbert function of R/J). The first problem we consider is how to determine when the sequence fo integers α = {α 0 , α 1 , α 2 , . . . } is the Hilbert function of R/J for some homogeneous ideal J. This problem was solved by F.S. Macaulay, using the following decomposition: for any integer ν ∈ N and i ∈ N + , there exists a unique sequence of integers

g i > • • • > g 1 ≥ 0 such that ν = g i i + • • • + g 1 1 ,
assuming that g h = 0 if g < h. This decomposition is denoted by ν i,0 . For k ∈ N, we write ν i,k = gi+k i+k + • • • + g1+k 1+k . A theorem of Macaulay [START_REF] Macaulay | Some Properties of Enumeration in the Theory of Modular Systems[END_REF] says that the integer sequence ν = {ν 0 , ν 1 , ν 2 , . . . } is the Hilbert function of a homogeneous ideal = R if and only if ν 0 = 1 and ν i+1 ≥ ν i i,1 for all i ≥ 1. This theorem is based on the analysis of ideals L J generated in degree i by the H R (i) -H R/J (i) first monomials for the lexicographic ordering for all i ∈ N. The monomial ideal L J is called the lex-segment ideal of J.

Two other interesting results on Hilbert functions are proved in [START_REF] Green | Generic initial ideals[END_REF][Theorems 3.8 and 3.11], [START_REF] Bruns | Cohen-Macaulay rings[END_REF][Theorems 4.3.2 and 4.3.3] (see also [START_REF] Gotzmann | Eine Bedingung für die Flachheit und das Hilbertpolynom eines graduierten Ringes[END_REF]): Theorem 3.10. Let J be a homogeneous ideal in the polynomial ring R = K[x 1 , . . . , x n ]. Set ν i = dim k (R/J) i for i ≥ 0. Let s be such that ν s+1 = ν s s,1 and assume that J is generated in degrees ≤ s + 1 then

(1) (Gotzmann's Persistence Theorem) ν i+1 = ν i i,1 = ν s s,i+1-s for all i ≥ s. (2) (Gotzmann's Regularity Theorem) reg(J) ≤ s.

The property that the lex-segment L J has a Hilbert function with minimal growth is used to prove these results.

Remark 3.11. The condition ν s+1 = ν s s,1 is reached for some degree s ∈ N, since it means that the lex-segment ideal L J associated to J is generated in degrees ≤ s. Theorem 3.12. Let B be a subset of M connected to 1, F a border basis in degree

≤ d for B, ν d-1 = #B d-1 , ν d = #B d . If ν d = ν d-1 d-1,1 , then F is an H-basis of I = (F ). Proof. Let G = F T ⊂ R ≤d and J = (G). By Corollary 3.9, H R/J (d -1) = ν d-1 , H R/J (d) = ν d . By Theorem 3.10(2) reg(J) ≤ d -1. By Theorem 3.8, F is an H-basis of I = (F ).
This theorem allows us to recover the Hilbert function of J = (F T ) and thus numerical invariants such as the dimension of the solutions of F = 0 or the degree. For ν ∈ N with a d-th decomposition

ν d,0 = g d d +• • •+ g1 1 with g d > • • • > g 1 ≥ 0, we define λ d (ν) = max 0≤i≤d (g i -i) and δ d (ν) = #{i | g i -i = λ d (ν), 0 ≤ i ≤ d}.
Corollary 3.13. Let B be a subset of M connected to 1, F a border basis in degree

≤ d for B, ν k = #B k for 0 ≤ k ≤ d with ν d = ν d-1 d-1,1 , I = (F ), J = I T . Then • H R/J (i) = ν d-1 d-1,i-d+1 for i ≥ d -1, • R/I is of (algebraic) dimension λ d-1 (ν d-1 ) + 1, • The degree of R/I is δ d-1 (ν d-1 ) if λ d-1 (ν d-1 ) ≥ 0 and k ν k otherwise.
Proof. By Theorem 3.10(1), the Hilbert function of R/J (or R/L J ) is given for

i ≥ d -1 by H R/J (i) = ν d-1 d-1,i-(d-1) = g d-1 + i -d + 1 i + • • • + g 1 + i -d + 1 i -d + 2 = i + g d-1 -(d -1) g d-1 -(d -1) + • • • + i + g 1 -(d -1) g 1 -1
where

ν d-1 = g d-1 d-1 + • • • + g1 1 with g d-1 > • • • > g 1 ≥ 0. Let λ := λ d-1 (ν d-1 ) and δ := δ d-1 (ν d-1 ). If λ ≥ 0, H R/J (i) expands as a polynomial in i which highest degree term is δ λ! i λ .
Thus the dimension of R/J (resp. R/I) is λ (resp. λ + 1) and its degree is δ. If λ ≤ 0, then B d-1 is empty, B is finite and its number of elements

k ν k is the degree of R/I. Remark 3.14. If ν d = ν d-1 d-1,1
, we also have that reg(J) ≤ d-1 so that J = I T and I are generated in degree ≤ d -1, and the k-th module of syzygies of J and I are generated in degree d + k -1 for 0 ≤ k ≤ n.

In this case, generators of a H-basis and of its first syzygy module of are known in degree d and we will stop the border computation and say the F = ker π is an H-border basis.

Algorithm

The algorithm presented in this section allows us to compute a border basis representation of the quotient by any ideal up to a degree where the generators form an H-basis (see Remark 3.14). It consists of constructing incrementally degree by degree a monomial set B connected to 1 together with a projection π from B + onto B and to test if the commutation condition of Theorem 3.2(1) is satisfied up to a given degree. If the commutation property is not satisfied, new polynomials are deduced and used to update the set B and the projection π. This computation is repeated until the regularity test is satisfied.

To compute such a set B, we will use the same strategy as the one described in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF], which relies on a choice function. Definition 4.1. A choice function γ is a function from R to M, such that given a polynomial f , γ(f ) is one of the monomials of the support of f . We say that a choice function refines the degree if the returned monomial is of maximal degree among the monomials of f . This choice function can be the function which "chooses" the leading monomial for a given monomial ordering. In this case we shall obtain a Gröbner basis. But it can be more general and not necessarily related to a monomial ordering of M which is compatible with the multiplication by monomials. It can also take into account the numerical value of the coefficients (see examples in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]).

This choice function will be used to select monomials outside B. In the following, the set B will be a union of intersections of monomial ideals with the complement of other monomial ideals.

The computation is made more efficient by an early prediction of what should be B and by checking that the prediction is correct up to a given degree. This is done by projecting a small set of polynomials, namely the commutation polynomials, in order to check the condition (4) of Theorem 3.2. When the projected polynomials are not 0, they are used to update the projection so that they belong to the kernel of the new projection. This computation is repeated until the regularity test of Theorem 3.10 is satisfied for a set B and a degree d.

We now state the algorithm of computation of H-border bases, which is based on the algorithm described in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]:

Algorithm 4.1: H-border basis

Input: A set of polynomials F = {f 1 , . . . , f s } and γ a choice function refining the degree. Output: A H-border basis for I = (f 1 , . . . , f s ).

•

Initialization(k, F k , B, F ) • While not(is reg?(B, k)) or k < max f ∈F deg(f ); (1) Compute C 1 k+1 := C 1 B (F k ) and A k+1 := (B + ) k+1 . (2) Construct the matrix M k+1 := (C 1 k+1 |A k+1 ). ( 3
) If #(A k+1 \ B k+1 ) = r k+1 , -compute A ′ k+1 ⊂ A k+1 such that #A ′ k+1 = r k+1 = rank (F k+1 | A ′ k+1 ) 5
; for instance looking at the monomials indexing the columns of a maximal invertible submatrix of M k+1 .

-compute B ′ k+1 = A k+1 \ A ′ k+1 ; -add the monomials B ′ k+1 to B; (6)
Define π k+1 : B + ≤k+1 → B ≤k+1 as the extension of π k such that C 1 k+1 ⊂ ker π k+1 and F k+1 as the new polynomials of degree k + 1 in the corresponding rewriting family. The function Initialization(k, F k , B, F ) performs initializing steps:

(7) Compute C 2 k+1 := π k+1 (C 2 B (F k )) ∪ πk+1 (F k+1 ). (8) If C 2 k+1 = {0},
• Find a linearly independent set of polynomials, F k , of minimum degree, k, from F . (a basis of the K-vector subspace spanned by the polynomials of minimum degree of the K-vector generated by F ). • Define B as the monomial set M\(γ(F k )).

The regularity test is reg?(B, d) is implemented as follows: For steps 9 and 10, a triangulation of the coefficient matrix (C 2 k+1 | B k+1 ) is also computed by applying the choice function γ to select the pivots. This transformation is then used to update B and F k+1 .

For more details on these computations, see [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF].

Notice that in the update of B (step 5), it can happen that the set B is extended and not reduced (some monomials are added to B). These are cases where algorithms as in [START_REF] Kaspar | Computing border bases without using a term ordering[END_REF] fail to construct a basis B stable by division (see eg. [10, Step (T7), Prop. 3.8]), showing that it is necessary to consider more general families of monomial bases B which are connected to 1, if we want to deal with general choice functions.

The previous algorithm is correct and stops after a finite number of steps on any input as we prove now.

We recall here Lemma 4.6 of [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] which proof also applies our case:

Lemme 4.2. For all d ∈ N, there exist finitely many F k containing polynomials whose leading monomials are of degree less than d.

This lemma is used to prove the termination of the H-border basis algorithm:

Theorem 4.3. The algorithm stops for some k and outputs a H-border basis of I = (f 1 , . . . , f s ).

Proof. The monomial set B maintained in the algorithm is connected to 1 by construction. By Lemma 4.2, for every degree k 0 there exists an iteration of the While loop, from which k does not drop under k 0 + 1. Hence for each k ∈ N, the set F k if defined becomes unchanged at a certain point in the algorithm.

As R is noetherian, the sequence of ideals (∪ i≤k F T i ) eventually becomes stationary. Let J be this ideal.

Again, according to Lemma 4.2, Theorem 3.10, Corollary 3.9 and Remark 3.11, there exists an iteration of the While loop such that all commutation polynomials project to 0 by π k , J is generated in degree ≤ k -1 and the regularity test applies. Theorem 3.8 allows us to conclude the proof.

Implementation/Benchmarks

We have implemented the previous algorithm in C++. It is available in the package borderbasix of the project Mathemagix1 . We report here on its experimentation. The main criterion, Macaulay decomposition and Gotzman persistence test correspond to approximately 200 lines. Less than 3000 lines (among 200000) had to be modified in the implementation of [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] in order to handle efficiently the regularity criterion (this includes the computation of the list of monomials in B at degree k).

We report first a comparision between the zero dimensional implementation of [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] and the one with the regularity test. As the polynomials computed are the same with or without the criterion, and in order to emphasize the overhead introduced here we perform computation with the smallest type of coefficients available in the package borderbasix, i.e. modular coefficients with support in 16-bit integers.

We use here a choice function that chooses one monomial of maximal partial degree among the available monomials (named mac in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]).

The experiments reported here have been performed on a Core2 Duo 2.26GHz, with 4Go of DDR2 800Mhz with a 64bit linux 3.2 kernel. As it can be seen, the overhead introduced by the new regularity test is completely negligible compared to the rest of the computation.

Example

We report here the timings and degree stop for some examples; the notation -n eq means that n equations have been discarded. There is a huge difference in time between kastura n and the same problem with one equation discarded. This comes from the difference of size of the matrices to be inverted and from the fact that one has to go much further in degree. The difference of behavior with respect to the choice function is somehow masked here, the coefficient growth does not appear as the degree increases.

Example

It is interesting to notice that Gotzman persistence is detected in degree more than the Castelnuovo Mumford regularity. It is the subject of a further work to improve the stopping criterion.

Conclusion

We have presented an extension of the border basis algorithm of [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF], which computes a border basis description of the quotient by any ideal up to any degree. This algorithm stops at a degree bigger than or equal to the regularity of the ideal. It outputs an H-basis of the ideal and its Hilbert polynomial. The stopping criterion exploits a characterization of a border basis up to a given degree, in terms of the projection of commutation polynomials and the persistence and regularity theorems of Gotzmann. A C++ implementation is also provided and some benchmarks illustrate the good practical behavior of the approach.

Though this new method addresses the main drawback of border basis methods, namely the restriction to zero-dimensional ideals, all is not said on this topic. Several interesting problems remain open. One of them is to relate the stopping degree more closely with the regularity of the ideal. Further investigations are also needed to analyze the syzygy modules of the border basis along the lines developed in [START_REF] Mourrain | Stable normal forms for polynomial system solving[END_REF]. The approach has also potential applications in relaxation methods used to compute radicals or real radicals [START_REF] Lasserre | Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals[END_REF], when the (real) radical is not zero dimensional. Generalizing the method to projections not necessarily compatible with the degree should also be detailled and implemented.

  ) Compute r k+1 := rank M k+1 . (4) If C 1 k+1 contains polynomials of degree < k + 1, add them to F and start a new loop with k := min p∈C 1 k+1 deg(p). (

  then start new loop with k := k + 1. (9) If C 2 k+1 contains polynomials of degree < k + 1, add them to F and start a new loop with k := min p∈C 2 k+1 deg(p). (10) Apply γ to C 2 k+1 , remove the monomial ideal generated by γ( C 2 k+1 ) from B and update π k+1 : B + ≤k+1 → B ≤k+1 and F k+1 , so that C 2 k+1 ⊂ ker π k+1 .

Algorithm 4 . 2 :

 42 Regularity testInput: A set of monomials B and a degree d. Output: A boolean indicating that the ideal has reached Gotzmann persistence.• Compute ν = dim K ( B d-1 ). • Compute the Macaulay decomposition ν d-1,0 of ν. • If dim K ( B d ) = ν d,1 then return true;else return false;For steps 4 and 5, a triangulation of M k+1 is computed. The choice function γ is used to select the pivots. The rank of M k+1 is read off from the triangular form. The transformation on the rows of M k+1 are reported on the polynomial vector C 1 k+1 . The zero-rows of the triangulation yield the polynomials of degree < k + 1 in C 1 k+1 . In step 5, the monomials B ′ k+1 are added to B by updating the representation of B as a union of intersections of monomial ideals with the complementary of other monomial ideals. Only the monomials of B ′ k+1 are added to this description but not their multiples. By construction, this yields a new set B of monomials, which is connected to 1.In step 6, to define the projection π k+1 from (B + ) ≤k+1 to B ≤k+1 , we invert (F k+1 | A ′ k+1 ), and construct new elements in F k+1 with one monomial in A ′ k+1 and the other monomials in B. This defines the new set F k+1 of polynomials of degree k + 1 of the rewriting family associated to π k+1 . In step 7, the commutation polynomials C 2 B (F k ) ⊂ B + ≤k+1 are projected on B ≤k+1 by π and the elements F k+1 of degree k + 1 of F are projected on B ≤k+1 by π (see Remark 3.4).

  In this table, nv is the number of variables, deg the degree of the quotient algebra R/I, time the average time (over 1000 runs) for the whole computation in seconds, memory the memory size used by the test, Isreg the time spent in the regularity test in seconds.

		nv deg	time memory Isreg
	kat8	8	256	0.5s	40M	0.001s
	kat9	9	512 3.49s	55M	0.002s
	kat10	10 1024 26.66s	79M	0.002s
	cyclic5	5	70	0.16s	20M	0.001s

www.mathemagix.org


Bazin

Marc Vernet

est destinée au dépôt

As we know, censorship always incubates on its own; a "Voltairian" country such as France flatly refuses the term "censorship." Censors speak of contrôle and classement, and never directly of censure. Nor do they ever actively censor, instead limiting themselves to an opinion or recommendation, and handing responsibility over to the producer or director who can choose whether to follow it or not so as to obtain the notorious certificate, which is not even technically a "censor's" certificate. In order to smooth over political responsibility in the case of the refusal of a certificate in a given case (this refusal must be publicly backed up and accorded the force of law under the jurisdiction of a political leader), the censors put into place a commission, that is, a censorship group, but under the rubric of "inspection" or "classification" and consisting of a large body representing all the entities presumed to be involved in the political as well as professional side. The profession would delegate the delicate task of any negative judgment to representatives of the audience. In the postwar era, all this resulted in the formation of the "state-profession parity commission" (41 members, according to Bazin himself, who seems to be including the deputies, among whom are those from the ciné-clubs and from criticism, as stakeholders in the profession). It comprises a representative from each putatively pertinent ministry (the Interior, Foreign Affairs, National Education...) and from every related entity (the profession, which largely names representatives from criticism and ciné-clubs, who will then bring on board, in turn, representatives of constituencies, chiefly families). Censorship rests on two major official bases: good morals (what can be shown or implied in the movie theater) and public order (preventing demonstrations on the streets outside the theater).

Cinema as a major political tool

What we have to remember is that in the middle of the 50s, cinema, as a mass medium, was still a political tool in the broad sense, falling under the same heading as the journalistic press and radio. Television was still mainly a technological curiosity, a luxury that had not yet found its way into every home (Bazin watched television, and films on TV; one of his final articles on censorship deals precisely with the question of censorship on television as it relates to young audiences 1 ). And yet, compared to these two "rivals" (newspapers and radio), cinema benefited from an asset considered both unique and formidable: the image in movement. This confers it with a particularly emotional power, whether beneficial or harmful. Bazin believed in this power, believed in its reversibility, and thought it his duty to participate in channeling it in the direction of the good and the beautiful, and against its possible perversion. This is still the era of Catholic parish screening rooms, and of ciné-clubs run by Communist sympathizers and laymen. Recall that in the middle of the 50s the Communist party still believed its message could be heard via cinema, whether it be Bel Ami (1954) by Louis Daquin, made in Soviet-controlled Austria and East Germany, or Paul Carpita's Le Rendez-vous des quais (1953-1955), made illegally in Marseille. In the case of Marcel Pagliero's Un homme marche dans la ville (A Man Walks in the City, 1950) the party believed it had to defend itself and so had it outlawed in Communist municipalities in the major French ports (Sadoul would later issue his mea culpa for having successfully prosecuted this case). From this point of view, Carpita's Rendez-vous des quais can be seen as an attempted recovery of the Pagliero film, a kind of censorhip by substitution, a reformed film correcting "the poor image" given by Pagliero of the ports and the dockers.

Bazin's involvement:

Surely it is for all of these reasons that André Bazin agreed to become a member of the Commission de contrôle, between 1953 and 1957, along with his friend Jacques Doniol-Valcroze. Their presence can be verified in the Commission's screening files, which include all the films that sought to obtain a censor's certificate, a notice with or without certain restrictions to minors and to particular districts of the French Empire. In several of Bazin's articles he explicitly refers to the Commission's work, breaking a promise of confidentiality.

We can consider the French censorship system to be in crisis starting in 1953, leading, after several aborted plans, to those reforms of 1960-1961, greatly advanced by Bazin's analyses and reflections. The reasons for this crisis are numerous.

-The Cold War climate that took hold in France in 1947, and the last serious attempts by the Communist party to return to power in '53-'55. -The dismemberment of France's colonial empire and the end of the Indochina War, at the same time that the war in Algeria begins, following the independence of Tunisia and Morocco. -The difficult winding down of the wartime economy (still felt in the consumer and housing markets --the winter of 54 and Abbé Pierre's famous "uprising of kindness"), and therefore a sort of détente in cinematic production, on the economic end, but also from a moral standpoint of what can be shown.

Here and there starting in 1953, these three elements can be found in the articles that Bazin devoted to censorship and its deployment, whether from a Communist or anti-Communist standpoint; just note the titles of his articles on Resnais's Les Statues meurent aussi and Yves Allégret's Méfiez-vous fillettes: respectively "Encore la censure: les films meurent aussi" and "Les fillettes doivent-elles se méfier des censeurs?" 2

Why did Bazin take part in this Commission de Contrôle? Because as noted, it comprised representatives from the profession and the public, and therefore critics. Bazin was the most distinguished of critics and so found himself in this position of responsibility. We could then say prima facie that Bazin defends three things: criticism (it must be practiced, it must stay vigilant and take responsibility for itself), youth (they have to be protected, yet encouraged to love cinema), and cinema itself (which must remain an art of very high standards, even while taking risks). Criticism, because he believes that it must fully play its role in the French system, including in the Commission. This legal role must not be abandoned (more practically, the Commission is also the ideal place for the viewing of films before their released in theaters).

Youth, because cinema has the power to influence minds; this was a recognized and noble objective after World War Two, and one of the principles behind the foundation of the Institute of Filmology, since cinema had served too many questionable causes during the war. Lastly, cinema, because censorship can put pressure on producers who too readily aim at easy profits without thinking of the importance of art. His last two articles ("Les fillettes doiventelles se méfier des censeur", July 1957, and "Censeurs, sachez censurer", December 1957) devoted to censorship, and supported by the aggressive position of François Truffaut, are clearly centered on producers' lack of willingness to organize themselves, whether to manage self-censorship or to resist the blows of the censors when the issue seems to merit it.

The independence of Bazin:

For those who have read articles on cinema in the 50s or taken an interest in censorship problems in France, it is impossible not to be astonished by the absolute and nearly immediate position taken by Bazin. While everyone is in the midst of uproar, denunciation, and a call to basic principles and sentiments, (for increasingly varied but always noble and indisputable reasons-which is to say quite disputable, but behind the mask of partisanship), Bazin respects complexity. His analyses, whether for or against his own views, stand at the crossroads of various perspectives-comparing points of view. He is able to maintain an uncompromising equilibrium that owes everything to his subtlety of intelligence, to his carefully laid out style of criticism, and perhaps foremost to the honesty of his remarks and the exactitude of his information. Bazin is one of the rare scrupulous writers that I have read on cinematic censorship, even in his journalism, writing with incontestable rigor. Only Alain Resnais is his equal in discussing censorship and appropriate responses to it. This is why Bazin seldom sparks controversy regarding censorship. He does not intervene except when the debate seems skewed, the controversy useless or poorly engaged; in short, when public opinion seems to be centered on biased ideas. He wanted not to be a "righter of wrongs," so much as a "righter of debates," since for him, from the start, the question of censorship is always an open one, always up in the air, always difficult, always complex, and his interventions aim to emphasize just that: things are even more complicated than whatever is said, and discussion can not validly proceed unless we take all of the (numerous) overlapping aspects into consideration. If censorship exists, if it should exist for cinema, this is never self-evident; for censorship comes neither from nature nor from right (droit).

The address to the politicians, then to the professionals

I have located twelve articles he wrote on the topic between 1950 and 1957; they imply both an evolution, and echoes of the past. An evolution, because the first two (1950 and 1953) portray Bazin as relatively unassuming (in the second, he devotes half his article to quotations) and opposed to censorship. But starting in 1954 and up to the end, he clearly becomes more engaged in a double-combat, both criticizing and defending the French system of censorship. Some echoes can be heard, for example, between "Les films changent, la censure demeure" (Cahiers du cinéma n. 19, January 1953) and "Encore la censure: les films meurent aussi" (1957), as well between his article devoted to La neige était sale and Voyage au bout de la nuit (Parisien libéré, March 8, 1954) and the one written about Yves Allégret's film Méfiez-vous fillettes, which Bazin deems, like the two just mentioned, overly dark. But note the accuracy of the title of his first article on the topic, coming out in Le Parisien libéré of November 13th, 1950: "Censure et censures au cinéma" ("Censorship and Censors in Cinema"), which must remain a constant reference point for his position. According to him, if we continue to talk about censorship, then we must talk about all of the various gears and levels where the interests of the French administration and those of cinematic production intersect.

Though the series of articles starts in 1950 with a condemnation of censorship ("a disgraceful constraint"), by 1957, producers are invited to clean up their own act and take charge; they know all the facts, so they may as well challenge the reigning system. This evolution also pertains to the scope of these articles' publication: at first he writes within the framework of Parisien libéré (large print, not much space) while toward the end he has moved to France Observateur (very small print, nearly the entire page). These two journals are privileged due to their periodicity, the first being daily and the other weekly, since questions of censorship are current events-though for Bazin this topic should not call for haste --and they will not wait for the following month. This confirms Bazin's double attitude regarding censorship, at once reflective and interventionist.

More precisely, in 1950 Bazin opened his file on censorship with a clearly negative prejudice, but straight away (this is very Bazin) it is corrected, or more exactly, relativized, with precisions and necessary distinctions. Censorship on the national level is a guarantee for the producer and the spectator because it saps strength from the more discreet and thus more efficient local censors. Though he does not say it here, we see that Bazin understood and was familiar with the American system, 3 in a much more detailed sense than many of his contemporaries and many of his successors. In short, Bazin knows that in terms of cinema, one censorship always hides another. He therefore explicitly points to the municipal Communist censorship, especially in the major French port cities, in reference to Un Homme marche dans la ville, the example he would bring up again later for good reason. At the end of this initial censorship article, Bazin notes that one should not "attack the censorship of films one likes while blocking the distribution of those one doesn't like." This is a position and an argument that will remain constant throughout his analysis of the "censorship" phenomenon.

Beyond good conscience: a respect of complexity

The 1953 Cahiers du cinéma article, "Les films changent, la censure demeure," may seem quite dialectical but, all told, it comes off rather "black and white," both against (the restriction of freedom of expression) and for (the still-living protagonists in the judicial affair). His final argument may be taken to be quasi "pro-life": it is a grievous decision not to allow a film to be born (this concerned Antonioni's episode in Sans amour, censored because of a rather sensational J3 case which, citing the breakdown of morals among postwar youth, declared that the French state should not permit the exportation to Italy of footage shot in France).

The least we can say is that Bazin's position, while unchanging, at least stands as nuanced. He shows a concern for modernizing the gears of the complex and ambiguous mechanism of censorship; he takes care to dismiss back-to-back the declared adversaries of the day, the Communists and the anti-Communists ; and he offers an undisguised defense of the moral code system of the Catholic Church. 4 Political censorship forms one of the more difficult areas of the topic. Sometimes Bazin seems to justify it, 5 and sometimes he condemns it. 6 Looking closely, we see that there is a pacifist side to Bazin (he hates the quarrels between left and right caused by cinema in the name of the Cold War), and so he disapproves of warmongering movies. He thus finds that political censorship can be justified. But then he condemns it (the case of the Resnais film) when it is Franco-French, linked to the personal or localized interests of politicos who operate from behind a mask. He would quite like to see censorship disappear, and wants the public to judge for itself (always a temptation in his articles; look at the text on the Allégret film that, according to him, does not deserve so much attention and publicity), but at the same time he recognizes that censorship gives birth to pre-censorship, which kills creativity; but creativity is killed only by cowardly producers who ought to have the courage of their craft. 7 Here he explicitly revives a position maintained by François Truffaut on the cowards of the film profession.

In reality, the pro-censorship Bazin defends four things: peace (he does not appreciate firestarters), youth (like everyone else), but also, and not so paradoxically after all, cinema both as work (oeuvre) and as risk. He attacks hypocrisy and the lowering moral standards (to him morals and "darkness" go hand in hand with a useless kind of despair that cinema should not exist to promote). Finally, in questioning his fellow critics (at Humanité and Figaro), he defends an idea of criticism based on its responsibility to provide honest and unbiased information, while upholding a vision of the profundity of cinema towards ends as unpartisan as possible. As for censors, producers, and critics: in the end Bazin invites them all to sweep up their own porches before attacking their neighbors.

In 1960, Henri Mercillon published three feature articles in Le Monde on the French censorship system --its domains, its dysfunctions, and prospects for its reform. 8 These articles mark the first big turning point on the subject since the Liberation; in the first article, Mercillon revives nearly word-for-word the analyses and arguments laid out by Bazin over the course of his final years. He came up with the following formula which could very well sum up one of the overarching aspects of Bazin's perspective: when it comes to the censorship of cinema in France, we find a happy marriage of vice, hypocrisy, and tartufferie.

self-regulates nationally and internationally to avoid the backlash of local censors (thus treating a country of exportation to be one such local censor). 4 Bazin, "Le Vatican, l'Humanité et la censure," Nouvel Observateur, February 23, 1956. 5 Ibid. 6 He condemns it in the article on les Statues meurent aussi, ridiculing the minister who declared while opening of the Cannes Festival that he was going to abolish censorship --Parisien libéré May 26, 1955 ("Première bonne nouvelle: le ministre déclare souhaiter la disparition de la censure..."). 7 Bazin France Observateur on July 11, 1957. 8 Henri Mercillon, "La réforme du contrôle des films," Le Monde, April 6, 7, and 8, 1960.

André Bazin, "Censeurs, sachez censurer," Revue du cinéma, 411 (December 1, 1957).

Bazin,"France Observateur, January 17, 1957, and France Observateur, January 11, 1957.

The Production Code is indeed a system defined and maintained by the profession (to protect its sectors of the market), and not a state-or religious-based system. It is the profession (and not some administrative authority) that


W De Mulder
email: wim.demulder@ugent.be

Generalized hard cluster analysis

Keywords: hard clustering, (m,n)-set, transitivity, matrix representation, equivalent clusterings hard clustering, matrix representation, transitivity, (m, n)-set, equivalent clusterings AMS Subject Classification: CR Category: I.5.3

In this paper we generalize the hard clustering paradigm. While in this paradigm a data set is subdivided in disjoint clusters, we allow different clusters to have a nonempty intersection. The concept of hard clustering is then analyzed in this general setting, and we show which specific properties hard clusterings possess in comparison to more general clusterings. We also introduce the concept of equivalent clusterings and show that in case of hard clusterings equivalence and equality coincide. However, if more general clusterings are considered, these two concepts differ and this implies the undesired fact that equivalent clusterings can have different representations in the traditional view on clustering. We show how a matrix representation can solve this representation problem.

Introduction

Cluster analysis is the partitioning of a data set into subsets (clusters), such that the data elements in each subset are similar to each other and dissimilar to the data elements in other subsets [START_REF] Jain | Data clustering: a review[END_REF][START_REF] Rui | Survey of clustering algorithms[END_REF]. Similarity and dissimilarity are defined in terms of a distance measure. A clustering algorithm is an algorithm that accomplishes this partitioning [START_REF] Dubes | Algorithms for clustering data[END_REF]. The resulting set of clusters, after applying a clustering algorithm, is called a clustering. The contribution of this paper is to generalize hard cluster analysis by allowing that a given data element can belong to more than one cluster, while in hard cluster analysis a given data element belongs to one and only one cluster [START_REF] Jain | Data clustering: a review[END_REF]. The most well-known hard clustering algorithm is k-means [START_REF] Tzortzis | The global kernel k-Means algorithm for clustering in feature space[END_REF]. An interesting discussion about the evolution of this still widely used algorithm is given in [START_REF] Jain | Data clustering: 50 years beyond K-means[END_REF]. Furthermore, we extend hard cluster analysis in a different way than fuzzy cluster analysis [START_REF] Bezdeck | FCM: fuzzy c-means algorithm[END_REF]. Fuzzy cluster analysis also allows that a given data element belongs to more than one cluster, but only to a certain degree between 0 and 1. Moreover, a typical fuzzy clustering algorithm requires that the sum of the degrees equals 1, while in the context of generalized hard cluster analysis we allow that a given data element belongs fully, i.e. to degree 1, to several clusters, although a given data element cannot belong to a cluster to a degree between 0 and 1. What is the relevance of allowing that a data element can belong to several clusters? We see both theoretical and practical advantages of this generalization. An important theoretical advantage is that a generalized setting allows to derive properties that are specific for hard clusterings, i.e. properties not shared by clusterings for which overlap between clusters is allowed. One practical advantage is that if two different hard clustering algorithms are applied to the same data set, results are mostly different. It is considered to be very hard to find an optimal way to combine these different clusterings [START_REF] Fern | Cluster ensemble selection[END_REF][START_REF] Hu | Cluster ensemble and its applications in gene expression analysis[END_REF]. The basic reason for the difficulty of combining different clustering results is the inconsistency between the clusterings, more precisely the fact that while a data element belongs to one cluster according to the first algorithm, it belongs to another cluster according to the second algorithm. This inconsistency may be eliminated by allowing that the considered data element belongs to both clusters in the final clustering. The relaxation of the requirement that each data element belongs to a single cluster thus greatly facilitates the integration of clusterings produced by different hard clustering algorithms, each having its own view on the given data set. The combination of different clusterings is the main topic of the theory of cluster ensembles [START_REF] Hore | A scalable framework for cluster ensembles[END_REF][START_REF] Strehl | Cluster ensembles -a knowledge reuse framework for combining multiple partitions[END_REF][START_REF] Thangavel | Ensemble based distributed k-harmonic means clustering[END_REF].

To give a specific application of generalized hard cluster analysis, consider the cluster analysis of gene expression data sets (the topic of the cluster analysis of gene expression data sets is discussed in, e.g., [START_REF] Jiang | Cluster analysis for gene expression data: a survey[END_REF]). The purpose of gene-based cluster analysis is to group together co-expressed genes (where co-expression is defined in terms of a similarity measure), which indicate co-function and co-regulation. However, it was recently found that the old paradigm that one gene makes one protein does not hold, and that through mechanisms that include alternative splicing, one gene can direct the synthesis of many proteins [START_REF] Venter | The sequence of the human genome[END_REF]. This implies that one gene can be involved in several, different processes and thus can have several functions. Generalized hard cluster analysis offers a solution in this case, since it allows that a gene is member of several clusters, and thus this method recognizes that one gene can have several functions. In this application, each cluster could correspond to a certain biological function.

Notice that generalized hard cluster analysis is even more suitable than fuzzy cluster analysis for this application, since a typical fuzzy clustering algorithm assigns each data element to every cluster to a certain degree, but such that the sum of these degrees, for a given element, equals 1. This is not desired in this case, because a gene can fulfill several functions, as discussed above, and it would be inappropriate to say that a gene fulfills a certain function only to a certain degree.

In this work, the focus is on the theoretical side of the mentioned generalization, developing a rigorous framework for generalized hard clustering and deriving specific properties for hard clusterings within this framework. At the same time, some interesting properties that apply to generalized hard clusterings, but not necessarily to hard clusterings, are proven. For example, in section 5 the maximum number of clusters that is needed to arbitrarily subdivide a data set into overlapping clusters is derived.

(m, n) -sets

In this section we introduce the concept of (m, n)-sets that will be used to represent a generalized hard clustering. Throughout the paper, in particular for the definitions and theorems, it is assumed that a data set is given. arbitrary nature. Since cluster analysis is about grouping objects, it is supposed that n ≥ 2.

Definition 2.1 Given m, n ∈ N an (m, n)-set is a set Φ = (Φ 1 , . . . , Φ m ) such that Φ i ∈ {(a 1 , . . . , a n ) | a j ∈ {0, 1}, ∀ 1 ≤ j ≤ n}. Given Φ i ∈ Φ we denote by Φ j i the jth element of Φ i , i.e. Φ i = (Φ 1 i , . . . , Φ j i , . . . , Φ n i ).
The set of all (m, n)-sets is denoted as M m,n .

Example 1. Given m = 2, n = 3, the set Φ = {(1, 0, 0), (0, 0, 1)} is an element of M 2,3 . Our purpose is to use an (m, n)-set Φ to represent a generalized hard clustering, where elements of Φ, namely Φ i , correspond to clusters. Thus in the above example the element (1, 0, 0) would represent a cluster consisting of d 1 , while the element (0, 0, 1) corresponds to a cluster containing d 3 . However, since we require that each element belongs to at least one cluster, the above definition is too general to be used directly as representation for generalized hard clusterings. Consequently, we define the following subset of M m,n .

Definition 2.2 C m,n = Φ = (Φ 1 , . . . , Φ m ) ∈ M m,n such that 1. m i=1 Φ j i ≥ 1, ∀ 1 ≤ j ≤ n 2. Φ i = (0, . . . , 0), ∀ 1 ≤ i ≤ N Definition 2.3 A clustering is an element of C N,n with N = n(n -1)/2 if n ≥ 3 and N = 2 if n = 2.
Remark 1 It is implicitly understood that the term clustering in this work refers to a generalized hard clustering.

Remark 2 As will become clear below, the first requirement ensures that each data element belongs to at least one cluster.

Remark 3 As will become clear below, the second requirement excludes empty clusters. Empty clusters are not interesting to consider, and excluding them avoids the need to give attention to special cases that are related to the presence of empty clusters.

Remark 4

The motivation for the definition and use of N will be given in section 5.

Remark 5 Notice the abstractness of the definition: no reference is made to, e.g., a distance measure.

Definition 2.4

H m,n = Φ = (Φ 1 , . . . , Φ m ) ∈ C m,n such that 1. m i=1 Φ j i = 1, ∀ 1 ≤ j ≤ n 2. Φ i = (0, . . . , 0), ∀ 1 ≤ i ≤ N Remark 6
The set H m,n thus contains all (m, n)-sets for which for a given j there

F
= (Φ 1 , . . . , Φ N ) ∈ C we define F(Φ i ) = {d j ∈ D | Φ j i = 1}
for i = 1, . . . , N . The sets F(Φ i ) are called the clusters of Φ.

Remark 7

The function F thus links an element of a clustering Φ ∈ C to a subset of the data set.

Example 2. Given D = {d 1 , d 2 , d 3 } the following is a clustering: Φ = ((1, 1, 0), (0, 1, 1), (0, 0, 1)) and {{d 1 , d 2 }, {d 2 , d 3 }, {d 3 }} is the corresponding set of clusters. Notice that Φ ∈ C N,n with n = 3, but Φ ∈ H N,n , since 3 i=1 Φ 2 i = 2 = 1 which contradicts definition 2.4.
From definition 2.6 and example 2 it is seen that each element Φ i ∈ Φ corresponds to a cluster. This means that the representation of clusterings by (m, n)-sets is equivalent to the classical representation of a clustering where a clustering consists of groups of data elements. Below it will be shown that this representation is suitable for hard clusterings, but inappropriate to represent generalized hard clusterings. In section 5 an alternative representation will be presented that is more convenient for generalized hard clusterings.

Definition 2.7 Given Λ ⊆ {1, . . . , n} and Φ ∈ C N,n we define Φ Λ i = 1 if and only if Φ j i = 1, ∀j ∈ Λ and Φ Λ i = 0 if and only if Φ j i = 0, ∀j ∈ Λ. Definition 2.8 Given Λ ⊆ {1, . . . , n} and Φ ∈ C N,n we define Φ Λ = {Φ i ∈ Φ | Φ Λ i = 1}. Remark 8
From the above definition it follows that if Φ i ∈ Φ Λ , then {d j ∈ D |j ∈ Λ} ⊆ F(Φ i ). Thus Φ i ∈ Φ Λ corresponds to a cluster that contains, at least, all data elements d j with j ∈ Λ.

Example 3. Given the results of example 2 we have, for example, Φ {2,3} = {(0, 1, 1)}. These are all the clusters, in this case only one, such that both d 2 and

d 3 belong to them. Another example is Φ {2} = {(1, 1, 0), (0, 1, 1)}. Theorem 2.9 C N,n = {Φ ∈ M N,n | Φ {j} = ∅, ∀ 1 ≤ j ≤ n, Φ i = (0, . . . , 0), ∀ 1 ≤ i ≤ N }. Proof Let Φ ∈ C N,n . From definition 2.1 and 2.2 it follows that Φ j i ∈ {0, 1} and N i=1 Φ j i ≥ 1, ∀ 1 ≤ j ≤ n. This is equivalent to saying that given 1 ≤ j ≤ n there exists a 1 ≤ i ≤ N for which Φ j i = 1. By definition 2.8 this is equivalent to Φ {j} = ∅, ∀ 1 ≤ j ≤ n. Conversely, if Φ ∈ M N,n and Φ {j} = ∅ then, by definition 2.8, there exists a 1 ≤ i ≤ N such that Φ j i = 1 and thus N i=1 Φ j i ≥ 1. Since this holds for all 1 ≤ j ≤ n it follows from definition 2.2 that Φ ∈ C N,n .
Discussion. The above theorem states that, loosely speaking, a clustering is a subdivision of a data set into clusters such that each data element belongs to at least one cluster. The theorem could also be interpreted as stating that (m, n)-sets are the right concept for representing generalized hard clusterings, where each data element belongs to at least one cluster. However, in the next section we develop the concept of equivalent clusterings, and in light of this concept we will conclude that (m, n)-sets fall short in providing an adequate representation of generalized hard clusterings.

Equivalent generalized hard clusterings

Since clustering is about grouping similar objects, we should describe two clusterings in which the same objects are considered as similar, as being equal. However, it is possible that two such clusterings have a different representation in terms of (m, n)-sets, as will be shown in a moment. Thus the fact that two clusterings represent the same grouping of objects cannot be expressed by stating that their representation by (m, n)-sets are equal. To resolve this, we introduce the concept of equivalent clusterings.

Definition 3.1 Φ ≡ Ψ if the following holds: Φ {i,j} = ∅ ⇔ Ψ {i,j} = ∅, ∀i, j ∈ {1, . . . , n}.
Remark 1 The interpretation of the definition is that two equivalent clusterings represent the same grouping of objects. For example, let d 1 , d 2 and d 3 be elements of a cluster in Φ ≡ Ψ, i.e. ∃ Φ i such that {d 1 , d 2 , d 3 } ⊆ F(Φ i ). By definitions 2.6 and 2.7 this implies that Φ {1,2,3} i = 1. In particular, Φ {1,2} i = 1 and thus, by definition 2.8, Φ {1,2} = ∅. This implies, by the above definition, that Ψ {1,2} = ∅. In the same way we find that Ψ {1,3} = ∅ and Ψ {2,3} = ∅. Thus in the clustering Ψ it holds that d 1 and d 2 are grouped together, as well as d 1 and d 3 , and d 2 and d 3 , although it is not required that there is one cluster in Ψ such that all these three elements belong to it. It is however clear that adding a cluster to Ψ consisting of d 1 , d 2 and d 3 should not alter the information contained in Ψ, and this precisely means that equivalent clusterings should be considered as equivalent, in the sense of representing the same subdivision of the given data set.

Example 4. Consider Φ = ((1, 1, 0), (1, 0, 1), (0, 1, 1)) and Ψ = ((1, 1, 1), (0, 0, 1), (1, 0, 0)). Then it is easily verified that Φ ≡ Ψ. It is noticed however that Φ = Ψ.

Definition 3.2 R Φ = {Ψ ∈ C | Ψ ≡ Φ}.
Given a finite set A the notation |A| is used to denote its number of elements.

Theorem 3.3 Φ ∈ H ⇒ R Φ ∩ H = {Φ}. Proof Given is Φ = (Φ 1 , . . . , Φ N ) ∈ H. Since definition 3.1 assures that Φ ≡ Φ it follows that Φ ∈ R Φ ∩ H. Now suppose that there exists a Ψ = (Ψ 1 , . . . , Ψ N ) ∈ H ∩ R Φ with Φ = Ψ. Thus there exists a i such that either Ψ i ∈ Ψ \Φ or Φ i ∈ Φ \Ψ.
Since both cases are entirely similar we consider only the case where = 1. This can now be repeated for k 3 , . . . , k s from which it is found that Φ A1 j = 1, which is contradictory to

Ψ i ∈ Ψ \ Φ. Let A 1 = {j ∈ {1, . . . , n} | Ψ j i = 1} and A 0 = {1, . . . , n} \ A 1 . Since Ψ i ∈ Φ we either have that Φ A1 i = 1, ∀ 1 ≤ i ≤ N or Φ A0 i = 0, ∀ 1 ≤ i ≤ N . Case 1: Φ A1 i = 1, ∀ 1 ≤ i ≤ N . This implies that |A 1 | ≥ 1,
Φ A1 i = 1, ∀ 1 ≤ i ≤ N .
Case 2: the case Φ A0 i = 0, ∀ 1 ≤ i ≤ N is handled entirely analogous as above. Discussion. The above theorem says that when attention is restricted to hard clustering the concepts of equivalence and equality are the same. Thus in case of hard clustering an (m, n)-set provides a unique representation for a given set of equivalent clusterings. Since equivalent clusterings represent the same subdivision of a given data set, the representation by (m, n)-sets is thus well-suited for the special case of hard clustering. However, extending hard clusterings to generalized hard clusterings it is no longer true that equivalence and equality in terms of (m, n)-sets are the same concepts, as example 4 illustrates. In the section 5 we show how generalized hard clusterings can be represented in matrix form and that in terms of this matrix representation equivalence and equality are the same concept.

In the next section we define the concept reflective transitivity and show that this property is characteristic for hard clusterings.

{d i1 , d i2 } ⊆ F(Φ i ), {d i2 , d i3 } ⊆ F(Φ j ) ⇒ ∃ Ψ ∈ R Φ , ∃k ∈ {1, . . . , N } : {d i1 , d i2 , d i3 } ⊆ F(Ψ k ).

Remark 1

The above definition states that, given any three data elements d i1 , d i2 , d i3 , a clustering is transitive if it holds that d i1 and d i2 belong to the same cluster and the same is true for d i2 and d i3 , then all three elements belong to the same cluster in a equivalent clustering. Thus the definition does not require that the cluster, or clusters, to which these three elements belong, is an element of the given clustering, but only that it is an element of an equivalent clustering.

The next theorem states the above definition in another form, without making reference to F . Theorem 4.2 Φ ∈ C is transitive if and only if the following holds:

Φ {i1,i2} = ∅, Φ {i2,i3} = ∅ ⇒ ∃ Ψ ∈ R Φ : Ψ {i1,i2,i3} = ∅.
Proof Suppose that Φ ∈ C is transitive and Φ {i1,i2} = ∅, Φ {i2,i3} = ∅. Then by definition 2.8 there exist a i and j such that Φ {i1,i2} i = 1, Φ {i2,i3} j = 1 and by definition 2.6 we can write that {d i1 , d i2 } ⊆ F(Φ i ), {d i2 , d i3 } ⊆ F(Φ j ). By definition 4.1 there exists a Ψ ∈ R Φ , ∃k ∈ {1, . . . , N } such that {d i1 , d i2 , d i3 } ⊆ F(Ψ k ).

Applying definition 2.6 again this means that Ψ

i1 k = Ψ i2 k = Ψ i3 k = 1 and thus Ψ {i1,i2,i3} = ∅. Conversely, suppose that Φ {i1,i2} = ∅, Φ {i2,i3} = ∅ ⇒ ∃ Ψ ∈ R Φ : Ψ {i1,i2,i3} = ∅. Suppose that {d i1 , d i2 } ⊆ F(Φ i ), {d i2 , d i3 } ⊆ F(Φ j )
. By definitions 2.6 and 2.8, this is equivalent to saying that Φ {i1,i2} = ∅, Φ {i2,i3} = ∅. By assumption it then follows that there exists a Ψ ∈ R Φ for which Ψ {i1,i2,i3} = ∅ and definition 2.8 then guarantees that there exists a k ∈ {1, . . . , N } such that Ψ {i1,i2,i3} k = 1 or in other words: {d i1 , d i2 , d i3 } ⊆ F(Ψ k ) from which we conclude that Φ is transitive.

Definition 4.3 A clustering Φ ∈ C is reflective transitive if the following holds: {d i1 , d i2 } ⊆ F(Φ i ), {d i2 , d i3 } ⊆ F(Φ j ) ⇒ ∃k ∈ {1, . . . , N } : {d i1 , d i2 , d i3 } ⊆ F(Φ k ).
Remark 2 Notice that unlike definition 4.1, the above definition requires that the

Φ {i1,i2} = ∅, Φ {i2,i3} = ∅ ⇒ Φ {i1,i2,i3} = ∅.
Proof The proof is entirely analogous to the proof of theorem 4.2. Theorem 4.5 If Φ ∈ H then Φ is reflective transitive.

Proof Suppose that Φ {i1,i2} = ∅, Φ {i2,i3} = ∅. By definition 2.8 there exists a i, j such that Φ {i1,i2} i = Φ {i2,i3} j = 1. Since Φ ∈ H the condition N m=1 Φ i2 m = 1 holds, which is only possible if i = j. Thus Φ {i1,i2,i3} i = 1 which proves the proposition.

Remark 3

The above theorem and the corresponding proof ensure that, in case of hard clustering, if d 1 and d 2 belong to the same cluster and the same is true for d 2 and d 3 , then d 1 , d 2 and d 3 belong to the same cluster. It is interesting to notice that this transitive property does not necessarily hold for a generalized hard clustering. This is seen in example 2 where Φ {1,2} = ∅, Φ {2,3} = ∅, but Φ {1,2,3} = ∅.

I A = {1 ≤ i ≤ n | d i ∈ A}.
In fact, definition 4.7 defines the set of all possible subdivisions of a given data set. This is now proved. Theorem 4.9

F C = {F 1 , . . . , F N } | F i ⊆ D, ∪ N i=1 I Fi = {1, . . . , n} .
Proof Consider any Φ = (Φ 1 , . . . , Φ N ) ∈ C and 1 ≤ j ≤ n. From definition 2.6 we can already conclude that F(Φ i ) ⊆ D. Since Φ ∈ C we know that N i=1 Φ j i ≥ 1. Thus there exists at least one i such that Φ j i = 1 and thus d j ∈ F(Φ i ) by definition 2.6, which implies that j ∈ I F (Φi) . This allows to write that {1, . . . , n} ⊆ ∪ N i=1 I F (Φi) . Furthermore, since F(Φ i ) ⊆ D it follows that I F (Φi) ⊆ {1, . . . , n} and thus ∪ N i=1 I F (Φi) ⊆ {1, . . . , n}. It then that ∪ N i=1 I F (Φi) = {1, . . . , n} and thus

F(Φ) ∈ F C . Conversely, given {F 1 , . . . , F N } for which F i ⊆ D and ∪ N i=1 I Fi = {1, . . . , n} define Φ = (Φ 1 , . . . , Φ N ) with Φ j i = 1 if d j ∈ F i
F H = {F 1 , . . . , F N } | F i ⊆ D, ∪ N i=1 I Fi = {1, . . . , n}, F i ∩ F j = ∅ if i = j .
F(Φ i ) ∩ F(Φ j ) = ∅ if i = j. Suppose that d k ∈ F(Φ i ) ∩ F(Φ j ), i = j. Then Φ k i = Φ k j =
1 by definition 2.6. This is only compatible with the properties that N p=1 Φ k p = 1 and Φ k p = 0 or 1, if i = j which is a contradiction.

Thus F(Φ i ) ∩ F(Φ j ) = ∅ if i = j. Conversely, given {F 1 , . . . , F N } for which F i ⊆ D, ∪ N i=1 I Fi = {1, . . . , n} and F i ∩ F j = ∅ if i = j define: Φ = (Φ 1 , . . . , Φ N ) with Φ j i = 1 if d j ∈ F i and Φ j i = 0 otherwise, for j = 1, . . . , n. It is easy to check that F(Φ) = {F 1 , . . . , F N }.
It remains to check that Φ ∈ H. Consider any m ∈ {1, . . . , n} = ∪ N i=1 I Fi . Then there exists a i such that m ∈ I Fi which implies that Φ m i = 1. Suppose that there is a i 2 for which Φ m i2 = 1. This implies that d m ∈ F i ∩ F i2 which is only possible if i = i 2 . Thus N i=1 Φ m i = 1 implying that Φ ∈ H. Discussion. We conclude from theorems 4.9 and 4.11 that a generalized hard clustering can represent any subdivision of a given data set, allowing overlap, while a hard clustering can only subdivide a given data set in disjoint clusters. Thus our abstract definition 2.4 of a hard clustering conforms the common notion that hard clusters do not overlap.

Matrix representation of a clustering

Given A ∈ R n×n and ∅ ⊂ Λ, Γ ⊆ {1, . . . , n} we use the notation A(Λ, Γ) to denote the submatrix of A containing the elements A(i, j) for which i ∈ Λ, j ∈ Γ. The notation A(i, j) will be used as shorthand for A({i}, {j}). Definition 5.1 Given Φ ∈ C we define its matrix representation, denoted as M (Φ), as

M (Φ)(i, j) = 1 ⇔ Φ {i,j} = ∅ = 0 otherwise
Remark 1 Thus if for a given clustering Φ we have that M (Φ)(i, j) = 1, then it holds that there exists a cluster in this clustering to which both d i and d j belong.

Theorem 5.2 Φ ≡ Ψ ⇒ M (Φ) = M (Ψ).
Proof By definition 4.1: Φ ≡ Ψ if Φ {i,j} = ∅ ⇔ Ψ {i,j} = ∅ for all i, j ∈ {1, . . . , n}. From this it is easily seen that M (Φ) = M (Ψ).

Theorem 5.3 Φ ≡ Ψ ⇒ M (Φ) = M (Ψ).
Proof Given is that Φ ≡ Ψ. Thus there exists a i and j such that Φ {i,j} = ∅ and Ψ {i,j} = ∅ or Φ {i,j} = ∅ and Ψ {i,j} = ∅. Without loss of generality we suppose that Φ {i,j} = ∅ and Ψ {i,j} = ∅. Then M (Φ)(i, j) = 0 and M (Ψ)(i, j) = 1, and thus M (Φ) = M (Ψ). Theorems 5.2 and 5.3 taken together give: M (Φ) = M (Ψ) ⇔ Φ ≡ Ψ. Thus while an (m, n)-set gives a unique representation for a set of equal clusterings, a matrix representation gives a unique representation for a set of equivalent clusterings. Since equivalent clusterings represent the same subdivision of a data set, the matrix representation should be preferred over the representation by (m, n)-sets when dealing with generalized hard clusterings. ), i = 1, . . . , K .

Definition 5.4 M n×n C = {A ∈ R n×n | A(i, j) ∈ {0, 1}, A(i, j) = A(j, i), A(i, i) = 1, 1 ≤ i, j ≤ n}
Case 1: A(i, k) = A(k, i) = 0 ∀ 1 ≤ i ≤ k -1. Define Φ i = ( Φ1 i , . . . , Φk-1 i , 0) for 1 ≤ i ≤ K , Φ K +1 = (0, . . . , 0, 1) and Φ i = (1, 0, . . . , 0) if K + 1 < i ≤ K. Then it is easily checked that Φ ∈ C K,k and M (Φ) = A. Case 2: ∃ 1 ≤ i ≤ k -1 for which A(i, k) = A(k, i) = 1. Let I = {i ∈ {1, . . . , k - 1} | A(k, i) = 1}. Then we define Φ i = ( Φ1 i , . . . , Φk-1 i , 0) if 1 ≤ i ≤ K and Φ K +i = 0 for i ∈ {1, . . . , k -1} \ I; finally we define for i ∈ I: Φ i K +i = Φ k K +i = 1 and Φ j K +i = 0 if j ∈ {i, k}. Notice that K +i ≤ K +(k -1) = (k -1)(k -2)/2+k -1 = k(k -1)/2 = K,
which is a first requirement to have that Φ ∈ C K,k . The other requirements are easily checked and we conclude that Φ ∈ C K,k . We now prove that M (Φ) = A which amounts to show that A(i, j) = 1 ⇔ Φ {i,j} = ∅ and A(i, j) = 0 otherwise. If {i, j} ⊆ {1, . . . , k -1} this is already true by induction and by the construction of Φ from Φ. So suppose that i = k and that Φ {k,j} = ∅ which implies the existence of a 1 ≤ m ≤ K such that Φ j m = Φ k m = 1. By construction of Φ it has to be that Φ j m is of the form Φ j K +j with j ∈ I. From the definition of I it then follows that A(k, j) = 1. If j = k then by definition 5.4 we have that A(k, k) = 1. Finally, if Φ {k,j} = ∅ it follows from the construction of Φ that j ∈ I which implies that A(k, j) = 0.

Remark 2

The proof of the above theorem shows why we have chosen N = n(n -1)/2 if n ≥ 3: this ensures that the mapping M : C → M n×n C is surjective. The case where n = 2 is rather a basic case and the proof also shows why in this case N = 2 is chosen. In other words: since clusterings from C represent any subdivision of a given data set (see theorem 4.9) and since the above mapping M : C N,n → M n×n C is surjective if N = n(n -1)/2 for n ≥ 3 and N = 2 i n = 2, this ensures that one needs never more than N clusters to arbitrary subdivide a given data set.

Definition 5.6 M n×n H = {A ∈ M n×n C | A(i, j) = 1, A(j, k) = 1 ⇒ A(i, k) = 1} Theorem 5.7 The mapping M : H → M n×n H is injective.
Proof Given Φ, Ψ ∈ H with Φ = Ψ we have to proof that M (Φ) = M (Ψ). Since Φ, Ψ ∈ H and Φ = Ψ it follows from theorem 3.3 that Ψ ∈ R Φ , thus Φ ≡ Ψ. Thus there exist i, j with i = j such that Φ {i,j} = ∅, Ψ {i,j} = ∅ (or vice versa). By definition of the mapping M it then follows that M (Φ)(i, j) = 1, M (Ψ)(i, j) = 0 and thus in particular: M (Φ) = M (Ψ).

. , Φ K ) ∈ H K,k such that M (Φ) = A. Define K = (k -1)(k -2)/2. By induction there exists a Φ = ( Φ1 , . . . , ΦK ) ∈ H K ,k-1 for which M ( Φ) = A({1, . . . , k -1}, {1, . . . , k -1}). Case 1: A(i, k) = A(k, i) = 0, ∀ 1 ≤ i ≤ k -1.
This case can be handled in the same way as in theorem 5.5, giving Φ i = ( Φ1 i , . . . , Φk-1 i , 0) for i = 1, . . . , K , Φ K +1 = (0, . . . , 0, 1) and Φ i = (1, 0, . . . , 0) for K + 1 < i ≤ K. It is seen that K i=1 Φ k i = 1. By induction and by the construction of Φ from Φ:

K i=1 Φ j i = 1, ∀1 ≤ j ≤ k -1, and since Φ j p = 0 for p = K + 1, . . . , K this is equivalent to K i=1 Φ j i = 1, ∀1 ≤ j ≤ k -1 implying that Φ ∈ H K,k . Case 2: ∃ 1 ≤ i ≤ k -1 for which A(i, k) = A(k, i) = 1. Let I = {i ∈ {1, . . . , k - 1} | A(k, i) = 1}. Consider any α ∈ I. Since by induction K j=1 Φα j = 1 there exists exactly one 1 ≤ m ≤ K such that Φα m = 1. Define Φ m = ( Φ1 m , . . . , Φk-1 m , 1
). Furthermore define Φ j = ( Φ1 j , . . . , Φk-1 j , 0) for 1 ≤ j = m ≤ K and Φ j = 0 if K < j ≤ K. We now prove that Φ ∈ H K,k . By induction and by the construction of Φ from Φ it follows, in the same way as in case 1, that K j=1 Φ

i j = 1 if 1 ≤ i ≤ k -1. The fact that Φ k j = 1 if and only if j = m implies that K j=1 Φ k j = 1.
Finally we prove that M (Φ) = A. Thus consider i, j for which Φ {i,j} = ∅. If i, j ∈ {1, . . . , k -1} induction ensures that M (Φ)(i, j) = 1. Suppose that i = k, i.e. there exists a t such that Φ k t = Φ j t = 1. If j = k we have that A(k, k) = 1 by definition of M H , so suppose that j = k. By construction we know that Φ α m = Φ k m = 1 and thus that Φ {α,k} = ∅. Since Φ {α,k} = ∅ and Φ {j,k} = ∅ theorem 4.5 implies that Φ {α,j,k} = ∅. Thus Φ {j,α} = ∅ and since 1 ≤ j, α ≤ k -1 it follows from induction that A(j, α) = 1. Together with A(k, α) = 1 and the transitive property of M H it follows that A(k, j) = 1. Finally, if Φ {k,j} = ∅ it follows from the construction of Φ that j ∈ I which implies that A(k, j) = 0.

Discussion. Theorem 5.7 and 5.8, together with definition 5.6, indicate that transitivity is the distinctive property of hard clusterings compared to general clusterings. Theorem 4.11 showed that the distinctive property of hard clusterings Φ is given by F(Φ i ) ∩ F(Φ j ) = ∅ if i = j; informally this can also be stated as the absence of overlap. Definition 2.4 indicates that the fact that each data element belongs to exactly one cluster is also the distinctive property of hard clusterings. From these three considerations it can be concluded that absence of overlap, transitivity and the property that each data element belongs to exactly one cluster, are equivalent properties.

Conclusion and future work

We generalized the hard clustering paradigm by allowing that a data element can belong to more than one cluster. It is shown that generalized hard clusterings can be represented by (m, n)-sets, a new concept that we discussed in this paper, and by matrices. The concept of equivalent generalized hard clusterings was defined and it was shown that in light of this concept the representation by matrices should be preferred. Another new concept we introduced was that of transitive clusterings. Using the paradigm of generalized hard clusterings, it was demonstrated that transitivity, absence of overlap between clusters and the property that each data element belongs to exactly one cluster are synonymous characteristics of hard clusterings. ber of clusters, given a generalized hard clustering. This is a relevant question, since it is possible that redundant or useless information is present in a generalized hard clustering. For example, consider the generalized hard clustering Φ = ((1, 1, 0), (0, 1, 0), (0, 0, 1)). This corresponds to three clusters where the first cluster represents the information that d 1 and d 2 are similar to each other, the second cluster states that d 2 is similar to itself and the third cluster states that d 3 is similar to itself. It is easily seen that only the first cluster contains relevant information, and thus the other two clusters redundant.

  since otherwise we would have that (0, . . . , 0) ∈ Ψ. This is contradictory to Ψ ∈ H, by definition 2.4. Thus |A 1 | ≥ 1, let us say A 1 = {k 1 , . . . , k s }. Since Φ ∈ H it follows from definition 2.4 that N m=1 Φ k1 m = 1 and thus there exists exactly one j for which Φ k1 j = 1. Now since Φ ≡ Ψ and Ψ A1 i = 1 it follows that Φ {k1,k2} = ∅, thus there exists a j 2 such that Φ {k1,k2} j2 = 1. Again applying the condition N m=1 Φ k1 m = 1 results in the fact that j = j 2 , thus Φ {k1,k2} j

  4. TransitivityDefinition 4.1 Φ ∈ C is transitive if the following holds:

  d i1 , d i2 and d i3 belong to a cluster of the given clustering, and not just to a cluster of an equivalent clustering. Theorem 4.4 Φ ∈ C is reflective transitive if and only if the following holds:

Definition 4 . 6

 46 Given Φ ∈ C we define:F(Φ) = {F(Φ 1 ), . . . , F(Φ N )}. Definition 4.7 F C = {F(Φ) | Φ ∈ C}. Remark 4 It is easily seen that F : C ⇒ F C is invertible.Definition 4.8 Given A ⊆ D we define its index set, denoted I A , as

  and Φ j i = 0 otherwise, for j = 1, . . . , n. It is then easily seen that F(Φ) = {F 1 , . . . , F N }. Furthermore given any m ∈ {1, . . . , n} = ∪ N i=1 I Fi there exists a i such that m ∈ I Fi or equivalently d m ∈ F i , and by construction of Φ we thus have that Φ m i = 1. From this it follows thatN i=1 Φ m i ≥ 1 and consequently Φ ∈ C. Thus F(Φ) = {F 1 , . . . , F N } ∈ F C by definition 4.7. Definition 4.10 F H = {F(Φ) | Φ ∈ H}.The above definition represents all possible subdivisions of a given data set in disjoint classes (clusters), as ensured by the following theorem.

Theorem 4. 11

 11

Proof

  Consider any Φ = (Φ 1 , . . . , Φ N ) ∈ H. By the previous theorem it remains only to proof that

Theorem 5 . 5

 55 Notice that from definition 5.1 it easily follows that M (C) ⊆ M n×n C (we remind the reader that C is used as shorthand for C N,n ). More is true. The mappingM : C → M n×n C is surjective. Proof Given A ∈ M n×n Cwe have to proof that there exists a Φ ∈ C such that M (Φ) = A. We prove this by induction on n. First suppose that n = 2. Then either A(1, 2) = A(2, 1) = 1 or A(1, 2) = A(2, 1) = 0. In the first case define Φ = {(1, 1), (1, 0)} and in the second case define Φ = {(1, 0), (0, 1)}. Then Φ ∈ C 2,2 and M (Φ) = A. Suppose that the theorem holds for n = 2, . . . , k -1. Consider now n = k and an arbitrary A ∈ M k×k C . We are in search for a Φ = (Φ 1 , . . . , Φ K ) ∈ C K,k such that M (Φ) = A, where K = k(k-1)/2. By induction there exists a Φ = ( Φ1 , . . . , ΦK ) ∈ C K ,k-1 with K = (k -1)(k -2)/2 for which M ( Φ) = A({1, . . . , k -1}, {1, . . . , k -1}). Denote Φi = ( Φ1 i , . . . , Φk-1 i

Theorem 5 . 8

 58 The mapping M : H → M n×n H is surjective.Proof We prove this again by induction on n. The case n = 2 is the same as in theorem 5.5, so suppose the theorem holds up to k -1, k ≥ 2. Consider now n = k and an arbitrary A ∈ M k×k H . It is asked to give a Φ = (Φ 1 , . .

  An interesting and important open question is how to deduce the minimal num-Page 10 of 11 URL: http://mc.manuscriptcentral.com/gcom E-mail: ijcm@informa.

  A hard clustering is an element of H N,n .If no confusion can arise, the shorter notations C and H are used instead of C N,n resp. H N,n .

	February 2, 2011	23:7	International Journal of Computer Mathematics	paper-IJCM-revision
		4	W. De Mulder
		exists one and only one i such that Φ j i = 1, and such that no Φ i equals (0, . . . , 0).
		Definition 2.5 Definition 2.6 Given Φ
			o
			r
			P
			e e r
			R e v i e w
				O n
				l y

URL: http://mc.manuscriptcentral.com/gcom E-mail: ijcm@informa.comInternational Journal of Computer Mathematics

Acknowledgements

Financial support from BOF (Special Research Fund of Ghent University) is gratefully acknowledged. I am grateful to Bart Wyns for his useful comments.