text:
Miguel Couceiro
email: miguel.couceiro@inria.fr

Lucien Haddad
email: haddad-l@rmc.ca

Karsten Schölzel

On the nonexistence of minimal strong partial clones

Let k be a k-element set. We show that the lattice of all strong partial clones on k has no minimal elements. Moreover, we show that if C is a strong partial clone, then the family of all partial subclones of C is of continuum cardinality. We also show that in almost all cases, every strong partial clone contains a family of continuum cardinality of strong partial subclones.

I. PRELIMINARIES

In this section we recall basic concepts and terminology needed throughout the paper. For further background, see [START_REF] Börner | Maximal Partial Clones with no finite basis[END_REF], [START_REF] Couceiro | A Survey on Intersections of Maximal Partial Clones of Boolean Partial Functions[END_REF], [START_REF] Haddad | Countable Intervals of Partial Clones[END_REF] and [START_REF] Lau | Function algebras on finite sets. A basic course on many-valued logic and clone theory[END_REF].

Let A be a finite set with |A|≥ 2. If |A|= k ≥ 2, then we assume that A = k := {0, . . . , k -1}. For a positive integer n, an n-ary partial function on k is a map f : dom(f ) → k where dom(f ) is a subset of k n called the domain of f . We denote by Par (n) (k) the set of all n-ary partial functions on k and we set

Par(k) := ∪ n≥1 Par (n) (k).
For positive integers n, m ≥ 1, and f ∈ Par (n) (k) and g 1 , . . . , g n ∈ Par (m) (k), the composition of f with g 1 , . . . , g n is the partial function f [g 1 , . . . , g n ] ∈ Par (m) (k) whose domain dom(f [g 1 , . . . , g n ]) is the set of all ⃗ a ∈ m ∩ i=1 dom(g i ) such that (g 1 (⃗ a), . . . , g m (⃗ a)) ∈ dom(f ), and whose values are given by f [g 1 , . . . , g n ](⃗ a) := f (g 1 (⃗ a), . . . , g n (⃗ a)) for all ⃗ a ∈ dom(f [g 1 , . . . , g n ]). For every positive integer n and each 1 ≤ i ≤ n, we denote by e n i the n-ary i-th projection function (or, simply, projection) defined by e n i (a 1 , . . . , a n ) = a i for all (a 1 , . . . , a n ) ∈ k n . Furthermore, we use the notation

J k := {e n i : 1 ≤ i ≤ n, n ∈ N}
for the set of all projections.

Definition 1. A partial clone on k is a subset of Par(k) closed under composition and containing the set of all projection functions J k .

Remark 1. Partial clones can be equivalently defined in the formalism of Mal'cev; see, e.g., Chapter 20 of [START_REF] Lau | Function algebras on finite sets. A basic course on many-valued logic and clone theory[END_REF].

The set of partial clones on k forms a lattice L P k under inclusion, in which the infimum is the set-theoretical intersection. Thus the intersection of arbitrarily many partial clones on k is itself a partial clone on k. Clearly, the set J k of all projections on k is the smallest element in the lattice L P k of partial clones.

For f, g ∈ Par (n) (k), the partial function g is said to be a subfunction of f , fact that we denote by g ≤ f , if

g = f | dom(g) , i.e., if dom(g) ⊆ dom(f ) and g(⃗ a) = f (⃗ a) for all ⃗ a ∈ dom(g). Definition 2. A partial clone C on k is said to be strong if it is closed under taking subfunctions, i.e., if the condition g ≤ f =⇒ g ∈ C
holds for every f ∈ C and g ∈ Par(k). For F ⊆ Par(k), we denote its strong closure by Str(F ), i.e.,

Str(F ) := {g ∈ Par(k) : g ≤ f for some f ∈ F }. Example 1. It is easy to see that the set {f ∈ Par(k) : (0, . . . , 0) ∈ dom(f ) =⇒ f (0, . . . , 0) = 0}
is a strong partial clone on k.

Strong partial clones have been widely studied in the literature, see, e.g., [START_REF] Börner | Maximal Partial Clones with no finite basis[END_REF], [START_REF] Couceiro | A Survey on Intersections of Maximal Partial Clones of Boolean Partial Functions[END_REF], [START_REF] Haddad | Countable Intervals of Partial Clones[END_REF] and [START_REF] Lau | Function algebras on finite sets. A basic course on many-valued logic and clone theory[END_REF] for a long list of references. The recent paper [START_REF] Schölzel | Dichotomy on intervals of strong partial Boolean clones[END_REF] is dedicated to the study of strong partial clones of Boolean functions.

It is well known that a partial clone C is strong if and only if Str(J k ) ⊆ C (see, e.g., [START_REF] Börner | Maximal Partial Clones with no finite basis[END_REF], Lemma 2.11). Moreover, it is easy to see that the intersection of an arbitrary family of strong partial clones on k is also a strong partial clone. In fact, the set of all strong partial clones, ordered by inclusion, also forms a lattice L Str(P k ) whose smallest element is Str(J k ).

For F ⊆ Par(k), let pclone(F ) denote the strong partial clone generated by F , i.e., the intersection of all strong partial clones on k containing F . As it is well-known, strong partial clones coincide exactly with the sets of polymorphisms of relations on k, that we now briefly describe.

For m ≥ 1, let ρ be an m-ary relation on k (i.e., a subset of k m ). Denote by M(ρ, dom(f )) the set of all m × n matrices M on k whose columns M * j ∈ ρ, for j = 1, . . . , n and whose rows

M i * ∈ dom(f ) for i = 1, . . . , m. A partial function f ∈ Par (n) (k) is said to preserve ρ ⊆ k m if (f (M 1 * ), . . . , f (M m * )) ∈ ρ for all M ∈ M(ρ, dom(f )). Set pPol ρ := {f ∈ Par(k) : f preserves ρ}.
It is well known that pPol ρ is a strong partial clone on k called the partial clone determined by ρ. Note that f ∈ pPolρ if there is no matrix M with columns in ρ and rows in dom(f ).

In this paper we first show that minimal strong partial clones (i.e., atoms of L Str(P k ) ) do not exist. Then we show that the family {D : D is a partial clone and D ⊆ Str(J k )} is of continuum cardinality. Since every strong partial clone contains Str(J k ), it follows that any strong partial clone contains a family of partial subclones of continuum cardinality. However, partial clones strictly included in Str(J k ) are not strong. In the last section we thus go a bit further and show that, in almost all cases, a strong partial clone contains a family of strong partial subclones of continuum cardinality.

In what follows, by an n-ary partial projection we mean a subfunction of a projection function whose domain is a proper subset of k n .

II. MINIMAL STRONG PARTIAL CLONES

A minimal partial clone on k is a atom of the lattice L P k . In other words, a partial clone C is minimal if there is no partial clone C 0 such that J k ̸ = C 0 ⊂ C ⊂ Par(k). Minimal partial clones consisting of partial functions have been completely described in [START_REF] Börner | Minimal Partial Clones[END_REF], none of which is strong. The natural question is then to ask whether strong minimal partial clones exist, i.e., whether atoms of L Str(P k ) exist.

In this section we show that such partial clones do not exist. This result is not surprising, but to our knowledge it has never been published. The idea behind the proof we present here comes from a discussion between the second author and Ferdinand Börner just after the paper [START_REF] Börner | Minimal Partial Clones[END_REF] has appeared. We will show that, given a partial function g that is not a partial projection function, we can construct a partial function h ∈ pclone(g), with h ̸ ∈ Str(J k ) and such that g ̸ ∈ pclone(h).

Let g ̸ ∈ Str(J k ) be an n-ary partial function and C := pclone(g). We distinguish two cases:

Case 1. For every (a 1 , . . . , a n ) ∈ dom(g), g(a 1 , . . . , a n ) ∈ {a 1 , . . . , a n }.
Let f be a restriction of g so that any further restriction of the domain of f results in a partial projection. Let

m := |dom(f )| and let α 1 , . . . , α m ∈ dom(f ) ⊆ k n with α i := (a i 1 , . . . , a i n ) and such that f      a 1 1 . . . a 1 n a 2 1 . . . a 2 n . . . . . . . . . a m 1 . . . a m n      =      b 1 b 2 . . . b m      . ( 1
)
Since f is not a partial projection, the right tuple (b 1 , . . . , b m ) T is not a column of the matrix on the left. Let M be the m × n matrix in [START_REF] Börner | Minimal Partial Clones[END_REF] and let ρ M be the m-ary relation on k consisting of all columns of M . Clearly f ̸ ∈ pPol(ρ M ), and thus g ̸ ∈ pPol(ρ M ).

Let f be the (n + 2)-ary partial function given by

f (x 1 , . . . , x n+2 ) := f (x 1 , . . . , x n ) for all (x 1 , . . . , x n+2 ) ∈ dom(f ) × k 2 . Note that f ∈ pclone(f ) ⊆ pclone(g).
Now take a c ∈ k, c ̸ = b 1 and consider the subfunction h of f whose domain is the set of all rows of the following matrix:

        a 1 1 . . . a 1 n c b 1 a 1 1 . . . a 1 n b 1 c a 2 1 . . . a 2 n b 2 b 2 . . . . . . . . . . . . a m 1 . . . a m n b m b m         where b 1 , b 2 , . . . , b m are the values of the partial function f . We therefore have h         a 1 1 . . . a 1 n c b 1 a 1 1 . . . a 1 n b 1 c a 2 1 . . . a 2 n b 2 b 2 . . . . . . . . . . . . a m 1 . . . a m n b m b m         =        b 1 b 1 b 2 . . . b m        . Note that |dom(h)|= m + 1.
We show that any restriction of h to a set with at most m tuples is a partial projection. Let h ′ be a restriction of h

with |dom(h ′ )|≤ m. If (a 1 1 , . . . , a 1 n , c, b 1 ) ̸ ∈ dom(h ′ ), then h ′ ≤ e n+2 n+1 , i.e., h ′ is a partial projection on its (n + 1)-st coordinate. Similarly, if (a 1 1 , . . . , a 1 n , b 1 , c) ̸ ∈ dom(h ′ ), then h ′ ≤ e n+2 n+2 . On the other hand if (a i 1 , . . . , a i n , b i , b i ) ̸ ∈ dom(h ′ )
for some i = 2, . . . , m, then h ′ is a partial projection function on the same coordinate as the subfunction of f whose domain is contained in the set of rows of M except the i-th row. Now we show that h ∈ pPol(ρ M ). Let N be a m × (n + 2) matrix with all columns in ρ M and all rows in dom(h). Then as N has m rows, the restriction of h on the rows of N is a partial projection function and so it preserves any relation, including the relation

ρ M . Thus h ∈ pPol(ρ M ), i.e., pclone(h) ⊆ pPol(ρ M ). Since g ̸ ∈ pPol(ρ M ) we conclude that g ̸ ∈ pclone(h) and thus pclone(h) ⊊ C. Case 2. There is an n-tuple (a 1 , . . . , a n ) ∈ dom(g) such that g(a 1 , . . . , a n ) ̸ ∈ {a 1 , . . . , a n }.
Let f be the restriction of g to the domain

{(a 1 , . . . , a n )} and let f (a 1 , . . . , a n ) = b with b ̸ ∈ {a 1 , . . . ,

III. CLONES OF PARTIAL PROJECTIONS

In this section we consider partial clones consisting only of projections and partial projection functions. For F ⊆ Par(k), let ⟨F ⟩ denote the partial clone generated by F , i.e., the intersection of all partial clones on k containing F . Notice that ⟨F ⟩ is not necessarily a strong partial clone.

Let R n denote the set of all n-tuples on k of weight 1, i.e.,

R n := {(x 1 , . . . , x n ) ∈ k n : n ∑ i=1 x i = 1}.
Furthermore, let p n be the n-ary partial projection given by

p n (x 1 , . . . , x n ) := { x 1 if (x 1 , . . . , x n ) ∈ R n undefined otherwise.
Let P := {p n : n ≥ 2}. We will show that for t ≥ 2, p t ̸ ∈ ⟨P \ {p t }⟩. Recall Lemma 2.10 in [START_REF] Börner | Maximal Partial Clones with no finite basis[END_REF].

Lemma 1. Let F ⊆ Par(k) and set D 0 := F ∪ J k .
For ℓ ≥ 0, define

D ℓ+1 := D ℓ ∪ {f [g 1 , . . . , g n ] | f ∈ D (n) 0 and g 1 , . . . , g n ∈ D (m) ℓ
for some n, m ≥ 1}.

Then ⟨F ⟩ = ∪ ℓ≥0 D ℓ .
Fix t ≥ 2 and F := P \ {p t }. Observe that, since F ⊆ Str(J k ), ⟨F ⟩ ⊆ Str(J k ), i.e., ⟨F ⟩ consists only of projections and partial projections.

Lemma 2. Let D 0 , D 1 , . . . be as in Lemma 1. Then, for each ℓ ≥ 0, D ℓ does not contain any partial projection p of arity t with R t ⊆ dom(p).

Proof. We prove Lemma 2 by induction on ℓ ≥ 0. For ℓ = 0, we have D 0 = (P \ {p t }) ∪ J k , which does not contain any partial projection of arity t. Now let ℓ ≥ 0 and suppose that D ℓ does not contain any partial projection p of arity t with R t ⊆ dom(p). We show that the same holds for D ℓ+1 . By the induction hypothesis and the definition of D ℓ+1 , we need to show that if f ∈ D

(n) 0 , n ≥ 1, g 1 , . . . , g n ∈ D (t) ℓ and p = f [g 1 , . . . , g n ],
then either p is a projection or a partial projection with R t ̸ ⊆ dom(p). Since g 1 , . . . g n ∈ D ℓ , it follows from the induction hypothesis that for every i = 1, . . . , n, either g i is a total projection or g i is a partial projection with R t ̸ ⊆ dom(g i ).

Suppose first that g i is a partial projection for some i = 1, . . . , n. Then R t ̸ ⊆ dom(g i ) and thus there is a ⃗ v ∈ R t \ dom(g i ). But then by the definition of the composition of partial functions p := f [g 1 , . . . , g n ] is not defined on the tuple ⃗ v, and thus ⃗ v ̸ ∈ dom(p). This shows that R t ̸ ⊆ dom(p).

Suppose now that each g 1 , . . . , g n is a total projection of arity t. If f ∈ J k is a projection, then p = f [g 1 , . . . , g n ] is a total projection and we are done.

So suppose that f is a partial projection. Since f ∈ D 0 , we have f = p n with n ̸ = t. Case 1. Let n < t. Then there is a j ∈ {1, . . . , t} such e t j ̸ ∈ {g 1 , . . . , g n }. Therefore ⃗ v j := (0, . . . , 0, 1

j-th position , 0, . . . 0) ̸ ∈ dom(p) (2)
since

g 1 (⃗ v j ) = • • • = g n (⃗ v j ) = 0 and (0, . . . , 0) ̸ ∈ dom(f ).
Case 2. Let t < n. Then there are j, k ∈ {1, . . . , t}, j ̸ = k, such that g j = g k . Without loss of generality, suppose that g j = g k = e t j . In this case, the t-tuple ⃗ v j defined in [START_REF] Börner | Maximal Partial Clones with no finite basis[END_REF] does not belong to dom(p), since the n-tuple (g 1 (⃗ v j ), . . . , g n (⃗ v j )) contains at least two entries equal to 1, and thus (g 1 (⃗ v j ), . . . , g n (⃗ v j )) ̸ ∈ dom(f ). This completes the proof of Lemma 2.

From Lemma 2, it follows that p t ̸ ∈ ⟨P \ {p t }⟩ for every t ≥ 2, and thus we have the following corollary.

Corollary 1. Let X, Y be two distinct subsets of {2, 3, . . . }.

Then ⟨{p i : i ∈ X}⟩ ̸ = ⟨{p j : j ∈ Y }⟩.
Let F J k be the set of all partial clones contained in Str(J k ).

Corollary 2. The set F J k is of continuum cardinality on k.

Now as every strong partial clone on k contains the set Str(J k ) we immediately have the following result. This is discussed in the next section.

IV. STRONG PARTIAL CLONES GENERATED BY A SINGLE PARTIAL FUNCTION

Let f be an n-ary partial function not in Str(J k ). Then there are m tuples α 1 , . . . , α m ∈ k n , with

α i := (a i 1 , . . . , a i n ), such that f         a 1 1 . . . a 1 n . . . . . . . . . a i 1 . . . a i n . . . . . . . . . a m 1 . . . a m n         =         b 1 . . . b i . . . b m        
and such that (b 1 , . . . , b m ) T is not a column of the matrix on the left hand side of the equation. Denote this m × n matrix by A. Also, throughout this section, assume that the n-ary partial function f , the matrix A and the number m of rows of A are fixed. Moreover, suppose throughout that the following condition is satisfied: (*) there is α ∈ k such that the m-tuple (α, . . . , α) T is not a column of A. We shall discuss the remaining cases for f in the next section. Now to simplify the notation, we assume α = 0, i.e., we assume that (0, . . . , 0) T is not a column of A.

Denote by I r the identity matrix of size r ≥ 2 on k, i.e., I r is the r × r matrix with symbol 1 on its diagonal and with 0 elsewhere. Furthermore, consider the following infinite set of positive integers

E := {2m r + ∑ 1≤i≤r m i-1 : r ≥ 0}.
Remark 2. Notice that, for each r ≥ 1, we have

2m r + m r-1 + • • • + m + 1 = m(2m r-1 + • • • + m + 1) + 1.
Consequently, if t > ℓ with t, ℓ ∈ E, then t ≥ mℓ + 1.

We will construct an infinite set of partial functions {f ℓ : ℓ ∈ E} each of which in pclone(f ), and with the property that for every

ℓ ∈ E, f ℓ ̸ ∈ pclone({f k : k ̸ = ℓ, k ∈ E}).
For ℓ ∈ E, let M ℓ be the matrix whose n first columns are

(a 1 i , . . . , a 1 i , a 2 i , . . . , a 2 i , . . . , a m i , . . . , a m i ) T , i = 1, . . . , n
and the m × ℓ last columns are the columns of the identity matrix I m×ℓ . Thus, M ℓ is a matrix with m × ℓ rows and n + m × ℓ columns. Note also that each of the tuples

(a i 1 , . . . , a i n ) is repeated ℓ times in M ℓ . M ℓ =                     a 1 1 . . . . . .
                   
Let ρ ℓ be the relation that consists of all columns of M ℓ . Note that ρ ℓ is a relation of arity m × ℓ over k.

Now let f ℓ be the partial function of arity n + m × ℓ whose domain is the set of all rows of the matrix M ℓ , and that is given by f

ℓ (⃗ v) = f (a i 1 , . . . , a i n )
, where (a i 1 , . . . , a i n ) are the first n coordinates of the tuple ⃗ v.

Example 2. Let k = {0, 1, 2}, and let f be the ternary partial function defined by

f   0 0 1 0 1 1 2 0 1   =   1 0 0   .
Here m = n = 3 and for 7 = 2 × 3 + 1 ∈ E, we get

f 7                        0 0 1 1 0 . . . 0 0 0 0 1 0 1 . . . 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 1 0 0 . . . 0 0 0 1 1 0 0 . . . 0 0 0 1 1 0 0 . . . 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 1 1 0 0 . . . 0 0 2 0 1 0 0 . . . 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 2 0 1 0 0 . . . 1 0 2 0 1 0 0 . . . 0 1

I21

Note that this matrix has 7 rows starting with (0, 0, 1), 7 rows starting with (0, 1, 1), and 7 rows starting with (2, 0, 1).

Lemma 3. For each ℓ ∈ E, we have that f ℓ ∈ pclone(f ) and that f ℓ is not a partial projection.

Proof. It is easy to see that f ℓ ∈ pclone(f ). Since f is not a partial projection, none of the n first columns of

) T . Lemma 4. If ℓ, t ∈ E, then f ℓ ∈ pPolρ t if and only if ℓ ̸ = t.
Proof. Clearly, f ℓ ̸ ∈ pPolρ ℓ . We show that if t ̸ = ℓ, then there is no matrix whose rows are rows of the matrix M ℓ and whose columns belong to the relation ρ t .

For the sake of contradiction, suppose that such a matrix B exists. Then B has m × t rows and n + m × ℓ columns. Let B [i, * ] , i = 1 . . . m × t, be all the rows of B and B [ * ,j] , j = 1, . . . , n + m × ℓ, be all its columns.

Case 1. t < ℓ.

For i = 1, . . . , m × t, the i-th row of B has the form will contain r 1's. Given that this column belongs to ρ t and given that each row of A occurs t times in M t , we conclude that r is a multiple of t.

B [i, * ] = (
For i = 0, 1, . . . , s let r i be the number of rows of M ℓ that are repeated i × t times in B, with r 0 being the number of rows in M ℓ that appear only once in B. Then counting the rows of B we get the equality

r 0 + t × r 1 + 2t × r 2 + 3t × r 3 + • • • + st × r s = m × t,
i.e., r 0 is a multiple of t. As m × ℓ is the total number of rows in M ℓ , and since at least one row of M ℓ is repeated in B, we have that r 0 < m × ℓ. Furthermore, as t ≥ m × ℓ + 1, we conclude that r 0 < m × ℓ < t and thus r 0 = 0. Hence, every row of M ℓ appears i × t times in B with i ≥ 1. It thus follows that B has no column with one 1 and m × t -1 0's, i.e., every column of B is one of the first n columns of M t .

Let B R be the block matrix consisting of the last m × ℓ columns to the right of the matrix B. Let us count the number of 0's in B R . Since the relation ρ t contains no zero tuple, every column of B R contains at least t 1's, i.e., every column in B R contains at most mt -t 0's. Given that there are m × ℓ columns in B R , there are at most m × ℓ × (m × t -t) 0's in B R . Furthermore, every row of B is a row of M ℓ , and thus every row of B R contains exactly one 1 and m × ℓ -1 0's.

Hence, there are

m × t × (m × ℓ -1) 0's in B R . Since m × t × (m × ℓ -1) > m × ℓ × (m × t -t),
we conclude that at least one column of B R must contain only 0's, which again yields a contradiction. V. FINAL REMARKS The construction we presented in Section IV does not hold if all constant columns belong to the domain. To illustrate this fact, consider the following example. For ℓ = 2 we have

M 2 =        
0 1 2 0 1 0 0 0 0 0 0 1 2 0 0 1 0 0 0 0 0 1 2 1 0 0 1 0 0 0 0 1 2 1 0 0 0 1 0 0 0 1 2 2 0 0 0 0 1 0 0 1 2 2 0 0 0 0 0 1

        of M 2 . The matrix below shows that f 3 ̸ ∈ pPolρ 2 . f 3        
0 1 2 0 1 0 0 0 0 0 0 0 0 0 1 2 0 0 1 0 0 0 0 0 0 0 0 1 2 1 0 0 0 1 0 0 0 0 0 0 1 2 1 0 0 0 0 1 0 0 0 0 0 1 2 2 0 0 0 0 0 0 1 0 0 0 1 2 2 0 0 0 0 0 0 0 1 0

        =         1 1 2 2 0 0        
Therefore our construction is not applicable if we start with an n-ary partial function f that has the following property: There are pairwise distinct i 0 , i 1 , . . . , i k-1 ∈ {1, 2, . . . , n} such that for every ⃗ v = (v 1 , . . . , v n ) ∈ dom(f ), we have

v i0 = 0, v i1 = 1, . . . , v i k-1 = k -1.
However, we conjecture that Corollary 4 holds for every

  a n }. Choose c ̸ = b and define the (n + 2)-ary partial function h by dom(h) = {(a 1 , . . . , a n , c, b), (a 1 , . . . , a n , b, c)} and h(a 1 , . . . , a n , c, b) = h(a 1 , . . . , a n , b, c) = b and proceed as in Case 1. Thus we have shown the following result. Theorem 1. Let C ̸ = Str(J k ) be a strong partial clone. Then there is a strong partial clone C ′ such that Str(J k ) ⊊ C ′ ⊊ C. Hence there are no strong minimal partial clones on k.

Theorem 2 .

 2 Let C be a strong partial clone on k. Then the interval of partial clones [J k , C] is of continuum cardinality. Note that none of the partial clones contained in Str(J k ) is strong. Therefore, Theorem 2 does not provide any insight into the interval of strong partial clones [Str(J k ), C]. Hence, for a strong partial clone C, it is natural to ask what is the size of the interval Clone(C) := {D : D is a strong partial subclone of C}.

  M ℓ is equal to (b 1 , . . . , b 1 , b 2 , . . . , b 2 , . . . , b n , . . . , b n ) T . Moreover, each of the last m × ℓ columns of M ℓ consists one 1 and mℓ -1 0's, and thus none of those columns can be equal to (b 1 , . . . , b 1 , b 2 , . . . , b 2 , . . . , b n , . . . , b n

Corollary 4 .

 4 Let C be a strong partial clone on k and suppose that C contains a partial function f ̸ ∈ Str(J k ) that satisfies ( * ). Then the set of strong partial clones contained in C is of continuum cardinality. Example 3. Let C be a strong partial clone on k and suppose that C contains a unary partial function g such that 1 ∈ dom(g) and g(1) = 0. Let f := g| {1} , i.e., f is given by dom(f ) = {1} and f (1) = 0. Since C is a strong partial clone, we have f ∈ C. Consider the set E defined above with m = 1, i.e., E = {2, 3, . . . }.For ℓ ∈ E, let f ℓ be the (ℓ + 1)-ary partial function whose domain is the set of rows of the matrix letf ℓ (⃗ v) := 0 for all ⃗ v ∈ dom(f ℓ ). Then f ℓ is a subfunction of f [e ℓ+1 1 ]and so f ℓ ∈ C. By Lemma 4 we have that pclone({f t : t ∈ X}) ̸ = pclone({f t : t ∈ Y }) for every X ̸ = Y ⊆ E and so the strong partial clone C contains each member of the family of strong partial clones of continuum cardinality {pclone({f t : t ∈ X}) : X ⊆ E}.

Example 4 .

 4 Let k = {0, 1, 2} and let f be the 4-ary partial function given by f Note that here m = 3 and n = 4. Thus E = {2, 7, 22, . . . }.

C

  ̸ = Str(k) : Conjecture. Let C ̸ = Str(k) be a strong partial clone over k. Then the family of all strong partial clones contained in C is of continuum cardinality.

  a s 1 , . . . , a s n , x 1 , . . . , x m×ℓ ) where s ∈ {1, . . . , m} and exactly one of x 1 , . . . , x m×ℓ is equal to 1 and all other are 0. Given that B consists of m × t such rows and given that mt < m × ℓ, there is a j ∈ {n + 1, . . . , n + m × ℓ} such that the column B [ * ,j] consists of only 0's. Hence, it does not belong to ρ t , which yields the desired contradiction. Therefore, if for some i ∈ {1, . . . , m × ℓ}, the i-th row M ℓ[i, * ] of M ℓ does not appear in B, then B [ * ,n+i] will contain only 0's, and it will not belong to the relation ρ t . Thus every row of M ℓ must appear in the matrix B. Since ℓ < t, some of the rows of M ℓ are repeated in B. Now if M ℓ[i, * ] appears repeated exactly r times in B, 2 ≤ r ≤ m × t, then B [ * ,n+i]

	Case 2. ℓ < t.
	As ℓ, t ∈ E, we must have t ≥ m × ℓ + 1, and
	M ℓ[i, * ] = (a s 1 , . . . , a s n , 0, . . . , 0,	1	, 0, . . . , 0)
		i-th position
	where 1 ≤ s ≤ m.

  Corollary 3. If X ⊆ E and ℓ ̸ ∈ X, then f ℓ ̸ ∈ pclone({f Now let C be a strong partial clone and suppose that C contains an n-ary partial function f ̸ ∈ Str(J k ) such that |dom(f )|= m. Suppose also that f satisfies condition ( * ). Reconsider the sets E and {f ℓ : ℓ ∈ E} defined above. By Corollary 3, for every X, Y ⊆ E with X ̸ = Y , the two strong partial clones pclone({f t : t ∈ X}) and pclone({f t : t ∈ Y }) are distinct and both are contained in pclone(f ) ⊆ C. Therefore, we have the following corollary.

t : t ∈ X}).

Proof. Since ℓ ̸ ∈ X, by Lemma 4 we have that f t ∈ pPolρ ℓ for every t ∈ X, and thus pclone({f t : t ∈ X}) ⊆ pPolρ ℓ . Since f ℓ ̸ ∈ pPolρ ℓ , we have f ℓ ̸ ∈ pclone({f t : t ∈ X}).

Acknowledgement. The authors wish to express their many thanks to one of the referees for his / her valuable and constructive remarks.

* This research was partially conducted while the second and the third authors were visiting LORIA and the Université de Lorraine, in 2016


domain: info math

text:
Miguel Couceiro
email: miguel.couceiro@inria.fr

Lucien Haddad
email: haddad-l@rmc.ca

Victor Lagerkvist
email: victor.lagerqvist@tu-dresden.de

Biman Roy
email: biman.roy@liu.se

On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations

A strong partial clone is a set of partial operations closed under composition and containing all partial projections. Let X be the set of all Boolean strong partial clones whose total operations are the projections. This set is of practical interest since it induces a partial order on the complexity of NP-complete constraint satisfaction problems. In this paper we study X from the algebraic point of view, and prove that there exists two intervals in X , corresponding to natural constraint satisfaction problems, such that one is at least countably infinite and the other has the cardinality of the continuum. 1/3

) appears to be an insurmountable task.

II. PRELIMINARIES

In this section we introduce the basic terminology that will be used throughout the paper.

A. Operations and Relations

Let X be a finite and non-empty set of values. Without loss of generality we may assume that X ⊂ N. In the particular case

I. INTRODUCTION

A k-ary polymorphism of a relation R is a homomorphism from the kth power of R to R. It is well-known that the set of all polymorphisms of a set of relations Γ form a clone, that is a set of operations closed under composition and containing all projections. The notion of a clone easily generalizes to partial operations, and it is known that the set of all partial polymorphisms of a set of relations Γ, pPol(Γ), form a strong partial clone, which is a set of partial operations closed under composition and containing all partial projections. Clone theory is not only a well-studied topic in universal algebra, but has many practical applications in computational complexity. One such example is the constraint satisfaction problem over a set of relations Γ (CSP(Γ)), which can be viewed as the problem of deciding whether an existentially quantified conjunctive formula over Γ admits at least one model. For example, the NP-complete problem 1-in-3-SAT can be seen as a CSP problem over the ternary relation R 1/3 = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}. It has been proven that the polymorphisms of Γ determine the complexity of the CSP problem over Γ up to polynomial-time many-one reductions [START_REF] Jeavons | Closure properties of constraints[END_REF], while the partial polymorphisms of Γ can be used to study the complexity of the CSP problem over Γ with respect to stronger notions of reductions [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF], [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF]. More specifically, Jonsson et al. [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF] proved that if pPol(Γ) ⊆ pPol(∆) then CSP(∆) is solvable in O(c n ) time whenever CSP(Γ) is solvable in O(c n ) time (if Γ and ∆ are both finite sets of relations). Hence, the partial polymorphisms of finite sets of relations induce a partial order on the complexity of NP-complete CSPs. Moreover, if Γ is a Boolean set of relations such that each operation in Pol(Γ) is idempotent, then CSP(Γ) is NP-complete if and only if Pol(Γ) consists only of projections [START_REF] Post | The two-valued iterative systems of mathematical logic[END_REF], [START_REF] Schaefer | The complexity of satisfiability problems[END_REF]. Put together, this implies that the set of strong partial clones containing only projections as total operations is a particularly interesting object of study, due to its relationship with NP-complete CSP problems. With these observation Jonsson et al. [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF] then proved that there exists a relation R = = =01 1/3 such that (1) the CSP problem over R = = =01 1/3 is NP-complete but (2) there does not exist any NP-complete Boolean CSP problem with a strictly lower worst-case timecomplexity. It is worth noting that the relation

R = = =01 1/3
is also interesting from a purely algebraic point of view since it is known that pPol

(R = = =01 1/3
) is the largest set of Boolean partial operations which does not contain any total operations (except the projections) [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF], [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF]. Jonsson et al. [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF] then conjectured that the set of strong partial clones between pPol(R 1/3 ) and pPol(R = = =01 1/3

) had a particularly simple structure consisting of only five elements. This conjecture turned out to be incorrect, and Lagerkvist & Roy [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF] proved that the cardinality of this set is at least countably infinite.

In this paper we continue the investigation of pPol(R = = =01 1/3

), with a particular focus on the strong partial clones between pPol(R 1/3 ) and pPol(R = = =01 1/3

). After having introduced the basic notions in Section II, we begin (in Section III-B) by proving that there exists at least countably many strong partial clones between pPol(R 1/3 ) and pPol(R 01 1/3 ), where R 01 1/3 = R 1/3 × {(0)} × {(1)}. To prove this, we find a class of relations σ k with the property that pPol(R

1/3 ) ⊂ pPol({σ k , R 01 1/3 }) ⊂ pPol(R 01 1/3 ) and pPol({σ k , R 01 1/3 }) ⊂ pPol({σ k+1 , R 01 1/3 }), for each k ≥ 4.
In Section III-C we study the strong partial clones between pPol(R 01 1/3 ) and pPol(R = = =01 1/3

), and prove that this set is of continuum cardinality, and therefore strengthen the results from Lagerkvist & Roy [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF]. Hence, even for extremely simply relations such as R 1/3 , trying to fully determine the strong partial clones between pPol(R 1/3 ) and pPol(R = = =01 when |X| = 2 we assume that X = {0, 1} and denote this set by B. A k-ary operation over X, k ≥ 1, is a function X k → X. We write OP X for the set consisting of all operations over the set X. We will sometimes denote Boolean operations by their defining logical formulas, and for example write x for the operation 1 -x, and we use x ⊕ y to denote addition modulo 2. A k-ary partial operation over X is a map D → X where D ⊆ X k , and we write PAR X for the set of all partial operations over X. The set D is called the domain of the partial operation f and we let dom(f ) = D. For both total and partial operations we let ar(f ) denote the arity of f . If f and g are two k-ary partial operations g is said to be a suboperation of f if dom(g) ⊆ dom(f ) and f (x) = g(x) for all x ∈ dom(g). We write f |D for the suboperation obtained by restricting f to a set D ⊆ dom(f ).

A k-ary relation over X is a subset of X k . The set of all relations over X is denoted by Rel X . For R 1 , R 2 ∈ Rel X of arity n and m, we let

R 1 × R 2 = {(x 1 , . . . , x n+m ) | (x 1 , . . . , x n ) ∈ R 1 , (x n+1 , . . . , x n+m ) ∈ R 2 } denote their Cartesian product. Given a k-ary tuple t = (x 1 , . . . , x k ) ∈ X k we let t[i] = x i denote
(R) = {Proj i1,...,i k (t) | t ∈ R}.
As a notational shorthand we let 0 k and 1 k denote the k-ary tuples (0, . . . , 0) and (1, . . . , 1).

It will be convenient to view a sequence of tuples t 1 , . . . , t n from a k-ary relation R as a k × n matrix where the ith column consists of the tuple t i . We let

Rows(t 1 , . . . , t n ) = ((t 1 [1], . . . , t n [1]), . . . , (t n [k], . . . , t n [k]))
denote the tuple consisting of all rows of this matrix. When the exact ordering is not important we instead write RowSet(t 1 , . . . , t n ) = {(t 1 [START_REF] Bodnarchuk | Galois theory for Post algebras[END_REF], . . . , t n [START_REF] Bodnarchuk | Galois theory for Post algebras[END_REF]), . . . , (t n [k], . . . , t n [k])} to denote the set consisting of all rows. For example, if t 1 = (0, 0, 0), t 2 = (0, 1, 0), and t 3 = (1, 1, 0) then Rows(t 1 , t 2 , t 3 ) = ((0, 0, 1), (0, 1, 1), (0, 0, 1)) while RowSet(t 1 , t 2 , t 3 ) = {(0, 0, 1), (0, 1, 1)}.

We will sometimes represent a relation as the set of models of a first-order formula, and if Γ is a set of relations we use the notation R(x 1 , . . . , x k ) ≡ ϕ(x 1 , . . . , x k ), where ϕ(x 1 , . . . , x k ) is a first-order formula over Γ with the free variables x 1 , . . . , x k , to define the relation

R = {(f (x 1 ), . . . , f (x k )) | f is a model of ϕ(x 1 , . . . , x k )}.

B. Clones

Let Π X be the set of all projections over X ⊆ N, i.e. all operations π n i of the form π n i (x 1 , . . . , x i , . . . , x n ) = x i . A clone over X is a set of operations C ⊆ OP X such that (1) C ⊇ Π X and (2) C is closed under functional composition. More formally, the latter condition means that if f, g 1 , . . . , g m ∈ C, where f has arity m and the functions g 1 , . . . , g m all have the same arity n, then the composition f

• (g 1 , . . . , g m )(x 1 , . . . , x n ) = f (g 1 (x 1 , . . . , x n ), . . . , g m (x 1 , . . . , x n )) for all x 1 , . . . , x n ∈ X, is included in C.
For a set of total operations F we let [F ] be the smallest clone containing F , and call F a basis of [F ]. A clone C is said to be finitely generated if there exists a finite set F such that [F ] = C, and is said to be infinitely generated otherwise. Every Boolean clone is known to be finitely generated, and the lattice of Boolean clones, Post's lattice, is countably infinite [START_REF] Post | The two-valued iterative systems of mathematical logic[END_REF].

C. Strong Partial Clones

A partial projection is a suboperation of a projection. Let Π p X be the set of all partial projections over a set X. A set of partial operations C is a strong partial clone if (1) C ⊇ Π p X and (2) C is closed under composition of partial operations. It is well-known that this definition implies that C is closed under taking suboperations [START_REF] Romov | The algebras of partial functions and their invariants[END_REF]. Composition of partial operations is defined analogously to the total case, i.e., if f, g 1 , . . . , g m ∈ PAR X , ar(f ) = m, and ar(g 1 ) =

. . . = ar(g m ) = n, then f • (g 1 , . . . , g m )(x 1 , . . . , x n ) = f (g 1 (x 1 , . . . , x n ), . . . , g m (x 1 , . . . , x n ))
, and the resulting function is defined for every tuple

(x 1 , . . . , x n ) ∈ m i=1 dom(g i ) such that (g 1 (x 1 , . . . , x n ), . . . , g m (x 1 , . . . , x n )) ∈ dom(f ).
For a set of partial operations F we let [F ] s be the smallest strong partial clone containing F , and similar to the total case the set F is said to be a basis of [F ] s . A strong partial clone C is said to be finitely generated if there exists a finite set of partial operations F such that [F ] s = C, and is infinitely generated otherwise.

D. Galois Connections

It is known that clones and strong partial clones admit relational representations. As a shorthand we let

f (t 1 , . . . , t n ) = (f (t 1 [1], . . . , t n [1]), . . . , f (t 1 [k], . . . , t n [k]))
and say that a relation R is closed or invariant under f if f (t 1 , . . . , t n ) ∈ R for every sequence t 1 , . . . , t n ∈ R. We also say that f is a polymorphism of R and let Pol(R) denote the set of all polymorphisms of the relation R. A relation R with Pol(R) = Π X is said to be strongly rigid. Similarly, for a set of relations Γ we let Pol(Γ) = R∈Γ Pol(R), and it is readily verified that f is a polymorphism of Γ if it preserves every relation in Γ. These notions can be generalized to partial operations, and we say that the n-ary

partial operation f is a partial polymorphism of a k-ary relation R if f (t 1 , . . . , t n ) ∈ R for every sequence t 1 , . . . , t n ∈ R such that (t 1 [1], . . . , t n [1]), . . . , (t 1 [k], . . . , t n [k]) ∈ dom(f ).
We then let pPol(R) denote the set of all partial polymorphisms of the relation R, and let pPol(Γ) denote the set of all partial polymorphisms of the set of relations Γ. It is not difficult to verify that sets of the form Pol(Γ) and pPol(Γ) form clones and strong partial clones, respectively. Moreover, if we let Inv(F ) be the set of all invariant relations under the set of (partial) operations F , it is well-known (cf. Chapter 2.9 in Lau [START_REF] Lau | Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory[END_REF]) that Pol(•) and Inv(•) give rise to a Galois connection.

Theorem 1 ([1], [START_REF] Bodnarchuk | Galois theory for Post algebras[END_REF], [START_REF] Geiger | Closed systems of functions and predicates[END_REF], [START_REF] Romov | The algebras of partial functions and their invariants[END_REF]): Let Γ and Γ be two sets of relations. Then Γ ⊆ Inv(Pol(Γ )) if and only if Pol(Γ ) ⊆ Pol(Γ).

An analogous result is known for Inv(•) and pPol(•), due to Geiger [START_REF] Geiger | Closed systems of functions and predicates[END_REF] and Romov [START_REF] Romov | The algebras of partial functions and their invariants[END_REF]. Theorem 2 ([4], [START_REF] Romov | The algebras of partial functions and their invariants[END_REF]): Let Γ and Γ be two sets of relations. Then Γ ⊆ Inv(pPol(Γ )) if and only if pPol(Γ ) ⊆ pPol(Γ).

As a shorthand we let Γ ∃ = Inv(pPol(Γ)). It is known that Γ ∃ is a set of relations closed under quantifier-free primitive positive definitions, (qfpp-definitions) over Γ, i.e., logical formulas of the form

ϕ(x 1 , . . . , x n ) ≡ R 1 (x 1 ) ∧ . . . ∧ R m (x m )
where each R i ∈ Γ ∪ {Eq} and each x i is a tuple of variables over x 1 , . . . , x n . Here, Eq denotes the equality relation {(x, x) | x ∈ X} over X. Hence, we can prove that pPol(Γ) ⊆ pPol(Γ ) by proving that each relation in Γ admits a qfpp-definition over Γ.

E. Weak Bases

It turned out that the lattice of partial clones on a set with at least two elements is very complex, and significant efforts were made by several authors to study parts of it. The question of describing the general position of the lattice of all total clones within the lattice of partial clones was raised by D. Lau. For example, given a total clone C, determine cardinality of the set of the partial clones on X whose total component is C. For B, this problem was completely solved in [START_REF] Couceiro | A solution to a problem of D. Lau: Complete classification of intervals in the lattice of partial boolean clones[END_REF] and the corresponding problem for strong partial clones was solved in [START_REF] Schölzel | Dichotomy on intervals of strong partial Boolean clones[END_REF]. We need the following definition: Definition 3: Let C be a clone over X. We let

Int(C) = {pPol(Γ) | Γ ⊆ Rel X , Pol(Γ) = C}.
We will sometimes be concerned with even more finegrained sets of strong partial clones and, given two strong partial clones C 1 and C 2 , write Int(C 1 , C 2 ) to denote the set

{pPol(Γ) | Γ ⊆ Rel X , C 1 ⊆ pPol(Γ) ⊆ C 2 }.
It is worth noting that the smallest element in the set Int(C) is simply [C] s , the strong partial clone obtained by closing C under suboperations, but it is also known that each such set admits a largest element.

Theorem 4: [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF] Let C be a finitely generated clone. Then

pPol(Γ)∈Int(C) pPol(Γ) ∈ Int(C).
It is also known that whenever Inv(C) is finitely generated, there exists a relation R over X such that

pPol(R) = pPol(Γ)∈Int(C) pPol(Γ).
Using the terminology of Schnoor and Schnoor [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF] we call a relation satisfying this condition a weak basis of Inv(C). Moreover, for the Boolean domain, all weak bases have been fully described [START_REF] Lagerkvist | Weak bases of Boolean co-clones[END_REF]. In this paper we have a particular interest in the weak basis R = = =01 1/3 = {(0, 0, 1, 1, 1, 0, 0, 1), (0, 1, 0, 1, 0, 1, 0, 1), (1, 0, 0, 0, 1, 1, 0, 1)} of Rel B . Note that Proj 1,2,3 (R = = =01 1/3 ) = R 1/3 , that the third, fourth, and fifth arguments are complement of the three first, and that the two last arguments are constant 0 and 1, respectively. As remarked in Section I, pPol(R = = =01 1/3

) can be viewed as the set of all Boolean partial operations f such that [{f }] s ∩ OP B = Π B . Hence, it is the largest Boolean strong partial clone whose only total operations are the projections. Somewhat surprisingly, it is known that this strong partial clone is not finitely generated, in contrast to the strong partial clone consisting of all Boolean partial operations (which can be generated by a partial Sheffer operation). ) is infinitely generated.

III. THE STRUCTURE BETWEEN pPol

(R 1/3 ) AND pPol(R = = =01 1/3 ) Jonsson et al. [6] conjectured that Int(pPol(R 1/3 ), pPol(R = = =01 1/3 )) consisted of pPol(R 1/3 ), pPol(R 01 1/3 ), pPol(R =01 1/3 ), pPol(R = =01 1/3 ), and pPol(R = = =01 1/3
), where

R = =01 1/3 = Proj 1,2,3,4,5,7,8 (R = = =01 1/3 ), R =01 1/3 = Proj 1,2,3,4,6,7 (R = =01 1/3 ), and R 01 1/3 = R 1/3 × R 0 × R 1 . This was disproven by Lagerkvist & Roy who proved that Int(pPol(R 01 1/3 ), pPol(R = = =01 1/3
)) is at least countably infinite [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF]. However, the questions of whether pPol(R 1/3 ) is covered by pPol(R 01 1/3 ), and whether Int(pPol(R 01 1/3 ), pPol(R = = =01 1/3

)) is in fact of continuum cardinality, were left open. After introducing some simplifying notation in Section III-A, we answer both of these questions in Section III-B and Section III-C. Before reading these sections in greater detail, the reader may first consult Figure 1 for a visualization of the main results.

A. Partial Polymorphisms of Strongly Rigid Relations

In order to describe the partial polymorphisms of strongly rigid relations we make the following definition. Definition 6: Let R be a relation and f a k-ary partial operation. We let

Cover R (dom(f )) = { RowSet(t 1 , . . . , t k ) | t 1 , . . . , t k ∈ R, RowSet(t 1 , . . . , t k ) ⊆ dom(f )}.
This immediately gives rise to the following lemma.

Lemma 7: Let R be a strongly rigid relation and f a partial operation over a finite set X.

If f |C ∈ Π p X for every C ∈ Cover R (dom(f )) then f ∈ pPol(R).
For R 1/3 and related relations the following concept can be used to characterize )). A directed arrow from Γ to ∆ means that pPol(Γ) ⊂ pPol(∆). Some inclusions are omitted.

Cover R 1/3 (dom(f )). For k, k ≥ 1, a set {ω 1 , . . . , ω k } ⊆ B k is an exact k -cover if ω 1 [i]+. . .+ω k [i] = 1 for every i ∈ {1, . . . , k}.
B. pPol(R 1/3 ) and pPol(R 01 1/3 )

In this section we study the structure of the set Int(pPol(R 1/3 ), pPol(R 01 1/3 )) and prove that it is at least countably infinite. First we define a useful class of relations. Definition 8: For each k ≥ 4 let σ k denote the relation

{(x 1 , . . . , x k , x 1 , . . . , x k , y 1 , . . . , y k-3 , y 1 , . . . , y k-3 , 0) | Σ k i=1 x i = 1, y 1 + x 1 + x 2 = 1, . . . , y k-3 + Σ k-2 i=1 x i = 1}.
Hence, if t 1 , . . . , t k ∈ σ k then RowSet(t 1 , . . . , t k ) contains an exact k -cover, the complement of these tuples, 2(k -3) tuples determined by the exact k -cover, and a constant 0 tuple. For example, the relation σ 5 may be visualized as

                       0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0                        .
We first claim that pPol(R 1/3 ) ⊆ pPol(σ 4 ). To see this, note that σ 4 can be qfpp-defined as

σ 4 (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 , y 1 , z 1 , C 0 ) ≡ R 1/3 (x 1 , x 2 , y 1 ) ∧ R 1/3 (x 3 , x 4 , z 1 ) ∧ R 1/3 (y 1 , z 1 , C 0 )∧ 4 i=1 (x i , x i+4 , C 0 ).
It is then not difficult to see that the partial operation f (0, 0, 1) = f (0, 1, 0) = f (1, 0, 0) = 0 preserves σ 4 and R 01 1/3

but not R 1/3 . Since pPol(R 1/3 ) ⊂ pPol(R 01 1/3 ) it therefore follows that pPol(R 1/3 ) ⊂ pPol({σ 4 , R 01 1/3 }). More generally it also holds that pPol({σ

k , R 01 1/3 ) ⊂ pPol({σ k+1 , R 01 1/3 }). Lemma 9: pPol({σ k , R 01 1/3 }) ⊃ pPol({σ k-1 , R 01 1/3 }) for each k ≥ 5. Proof: To prove the inclusion pPol({σ k , R 01 1/3 }) ⊇ pPol({σ k-1 , R 01 1/3 }) we show that σ k ∈ {σ k-1 } ∃ , via the qfpp-definition σ k (x 1 , . . . , x k , x k+1 , . . . , x 2k , y 1 , . . . , y k-3 , z 1 , . . . , z k-3 , C 0 ) ≡ σ k-1 (x 1 , . . . , x k-2 , y k-3 , x k+1 , . . . , x 2k-2 , z k-3 , y 1 , . . . , y k-4 , z 1 , . . . , z k-4 , C 0 ) ∧ σ k-1 (x k , x k-1 , . . . , x 3 , z 1 , x 2k , x 2k-1 , . . . , x k+3 , y 1 , z k-3 , z k-4 , . . . , z 1 , y k-4 , . . . , y 1 , C 0 ).
For the proper inclusion, define the (k -1)-ary partial operation f such that dom(f ) = RowSet(σ k-1 ), and let f ( 0 k-1 ) = 1 and f (x) = π k-1 1 (x) otherwise. By definition f does not preserve σ k-1 , and it directly follows from Theorem 10 in Lagerkvist & Roy that f preserves R 01 1/3 [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF]. Hence, all that remains is to prove that f preserves σ k , which we do by showing that Cover σ k (dom(f )) = ∅. Assume there exists t 1 , . . . , t k-1 ∈ σ k such that RowSet(t 1 , . . . , t k-1 ) ⊆ dom(f ). Since Σ k j=1 t i [j] = 1 for each i ∈ {1, . . . , k -1} and k > k -1, there exists l ∈ {1, . . . , k} such that t

1 [l] = . . . = t k-1 [l] = 0. But due to Definition 8, t 1 [l + k] = . . . = t k [l + k] = 1, implying that RowSet(t 1 , . . . , t k-1 ) ⊆ Cover σ k (dom(f )) since 1 k-1 / ∈ dom(f ).
We have thus proved the following.

Theorem 10: The set Int(pPol(R 1/3 ), pPol(R 01 1/3 )) is at least countably infinite. C. pPol(R 01 1/3 ) and pPol(R = = =01 1/3
) Following Lagerkvist & Roy [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF] we define the following class of relations.

Definition 11: Let k ≥ 5. The relation α k is defined as

α k (x 1 , . . . , x k , y 1 , . . . , y k-3 , z 1 , . . . , z k-3 , w 1 , . . . , w k-4 , C 0 , C 1 ) ≡ ∃x k+1 , . . . , x 2k . k-2 i=3 R 1/3 (x 1 , x i , w i-2 ) ∧ R 1 (C 1 )∧ σ k (x 1 , . . . , x k , x k+1 , . . . , x 2k , y 1 , . . . , y k-3 , z 1 , . . . , z k-3 , C 0 ).
For each k ≥ 5, let α 1 , . . . , α k be an enumeration of the tuples in

α k such that α 1 [k] = 1, α 2 [k -1] = 1, . . ., α k [1] = 1.
Under this enumeration of tuples we for example see that the matrix corresponding to α 6 can be visualized as:

                         0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1                          . Let V k = Rows(α 1 , . . . , α k )[2(k-2)+2(k-3)],
and define the k-ary partial operation

f k as dom(f k ) = RowSet(α 1 , . . . , α k ) and f k (x) = π k 1 (x) for every x ∈ dom(f k ) \ {V k } and f k (V k ) = α 1 [2(k -2) + 2(k -3)] ⊕ 1.
For example, we have that V 6 = (1, 1, 0, 1, 1, 0) and therefore that f (V 6 ) = 0. We then have the following result from Lagerkvist & Roy [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF].

Theorem 12 (Lagerkvist & Roy [8]): Let k ≥ 5. Then ( 1)

pPol(R 01 1/3 ) ⊂ pPol(α k ) ⊂ pPol(R = = =01 1/3
) and ( 2)

f k / ∈ pPol(α k ) but f k ∈ pPol(α k ) for every 5 ≤ k < k .
We will shortly see that f k preserves α k whenever k ≥ 5 and k = k. First we state the following lemma, whose proof is trivial due to the fact that f k is defined as a projection on the first argument whenever its arguments are distinct from V k .

Lemma 13: Let k, k ≥ 5. Then f k |C ∈ Π p B for every C ∈ Cover α k (dom(f k )) such that V k / ∈ C.
Before the proof of the following lemma we make a few observations regarding the domain of the function f k . Due to Definition 11 this set consists of 1) k tuples x 1 , . . . , x k such that {x 1 , . . . , x k } forms an exact k-cover, 2) k-3 tuples y 1 , . . . , y k-3 such that {x 1 , . . . , x i , y i-1 },

2 ≤ i ≤ k -2, forms an exact k-cover, 3) k -3 tuples y 1 , . . . , y k-3 such that {x k , . . . , x i+1 , y i-1 }, 2 ≤ i ≤ k -2, forms an exact k-cover, 4) k -4 tuples z 1 , . . . , z k-4 such that {x 1 , x i , z i-2 }
forms an exact k-cover for 3 ≤ i ≤ k -2, and 5) two constant tuples 0 k and 1 k .

It is also worth remarking that each y i satisfies the condition that y i [j] = 1 if 1 ≤ j ≤ k-i+1 and y i [j] = 0 if k-i+1 < j ≤ k, and that z i [k] = 0, z i [i + 2] = 0, and z i [j] = 1 otherwise. In particular, dom(f k ) contains the tuple V k , which satisfies V k [START_REF] Couceiro | A solution to a problem of D. Lau: Complete classification of intervals in the lattice of partial boolean clones[END_REF] = 0 and V k [k] = 0, and V k [i] = 1 otherwise. We are now ready to prove the main result of this section.

Lemma 14: Let k ≥ 5. Then f k / ∈ pPol(α k ) but f k ∈ pPol(α k ) for every k ≥ 5 such that k = k.
Proof: Assume first that k > k. Then the result follows from Theorem 12. Hence, in the forthcoming proof, assume that k < k. We will prove that whenever C ∈ Cover α k (dom(f k )) then V k / ∈ C, which by combining Lemma 7 and Lemma 13 proves that f k ∈ pPol(α k ). Hence, for t 1 , . . . , t k ∈ α k let (a 1 , . . . , a k , b 1 , . . . , b k -3 , c 1 , . . . , c k -3 , d 1 , . . . , d k -4 , 0 k , 1 k ) denote the tuples in Rows(t 1 , . . . , t k ). There are now a few cases to consider. However, if

V k = a i , 1 ≤ i ≤ k , or if V k = b i , V k = c i for 1 ≤ i ≤ k -3,
then the proof follows the same argument as Lemma 13 in Lagerkvist & Roy [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF].

Therefore, assume there exists some i ∈ {1, . . . , k -4} such that d i = V k . This implies that {a 1 , a i+2 , d i } forms an exact k-cover, and we may without loss of generality assume that

0 k / ∈ {a 1 , a i+2 , d i } as otherwise V k ∈ {a 1 , a i+2 , d i }, which is impossible since V k / ∈ dom(f k ).
Note in particular that this implies that a 1 and a i+2 both contain exactly one entry equal to 1. Assume without loss of generality that a 1 [k] = 1 and that a i+2 [3] = 1. We will first prove that Σa j = 1 for any j ∈ {1, . . . , k -2}, where Σa j = a j [START_REF] Bodnarchuk | Galois theory for Post algebras[END_REF]

+ . . . + a j [k].
First, assume that a j = 0 k for some j ∈ {1, . . . , k -2}. The case when j = 1 cannot occur since we have already established that Σa 1 = 1, and j = 2 is impossible since it implies that b 1 = a 1 / ∈ dom(f ), due to the fact that {a 1 , a 2 , b 1 } must be an exact k-cover. Similarly, we see that d j-2 = a 1 / ∈ dom(f ) if Σa j = 0 for j ∈ {3, . . . , k -2}, since {a 1 , a j , d j-2 } must be an exact k-cover.

Second, assume that Σa j > 1 for some 1 ≤ j ≤ k -2. Since the cases when j = 1 or j = i + 2 are impossible we assume that j = 1 and that j = i + 2. Since a 1 = (0, 0, . . . , 0, 1) and a i-2 = (0, 0, 1, 0, . . . , 0), this implies that a j = (1, 1, 0, . . . , 0), as otherwise a j / ∈ dom(f k ). But then, since {a 1 , a j , d j-2 } must form an exact k-cover, f k cannot be defined on d j-2 .

Hence, Σa j = 1 for each 1 ≤ j ≤ k -2, but since k < k this implies that Σa k -1 > 1 or that Σa k > 1. We assume that Σa k -1 > 1 since the case when Σa k > 1 is entirely symmetric. Due to the assumption that a k -1 ∈ dom(f k ), a 1 = (0, . . . , 0, 1) and a i-2 = (0, 0, 1, 0, . . . , 0), this in fact implies that a k -1 = (1, 1, 0, . . . , 0). Now, since {a

k -1 , a k , c k -2 } must form an exact k-cover, either a k = 0 k or c k -2 = 0 k , as otherwise a k / ∈ dom(f k ) or c k -2 / ∈ dom(f k ).
However, the latter case is impossible since it implies that a k -1 = a k , which cannot happen since {a 1 , . . . , a k } is an exact k-cover, and since Σa j = 1 for 1 ≤ j ≤ k -2. Hence, a k = 0 k , and c k -2 = a k . Now, since Σa j = 1 for every 1 ≤ j ≤ k -2, it follows that |{t 3 , . . . , t k }| = k -2, i.e., the tuples t 3 , . . . , t k do not contain any repetitions. However, since t 1 / ∈ {t 3 , . . . , t k }, and there cannot exist t j such that t j [k ] = 1, there are only k -2 tuples to choose from. This is impossible since k < k, and we conclude that V k / ∈ RowSet(t 1 , . . . , t k ). )) is of continuum cardinality.

Proof: Let N ≥5 = N \ {0, 1, 2, 3, 4}. We will prove that there exists an injective function h from {X | X ⊆ N ≥5 } to Int(pPol(R 01 1/3 ), pPol(R = = =01 1/3

)). Define h(X) = pPol({α i | i ∈ X}) for every X ⊆ N ≥5 . We claim that pPol({α i | i ∈ X}) = pPol({α i | i ∈ Y }) whenever X, Y ⊆ N ≥5 and X = Y . Indeed, if X = Y then there exist i 1 ∈ X or i 2 ∈ Y such that i 1 / ∈ Y or i 2 / ∈ X. But then f i1 / ∈ pPol({α i | i ∈ X})

and f i1 ∈ pPol({α i | i ∈ Y }), or f i2 / ∈ pPol({α i | i ∈ X}) and f i2 ∈ pPol({α i | i ∈ Y }), due to Lemma 14.

IV. CONCLUDING REMARKS

We have studied the set Int(Π B ), with a particular focus on describing the strong partial clones between pPol(R 1/3 ) and pPol(R = = =01 1/3

). By generalizing the results from Lagerkvist & Roy [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF] we have proven that Int(pPol(R 1/3 ), pPol(R 01 1/3 )) is at least countably infinite and that Int(pPol(R 01 1/3 ), pPol(R = = =01 1/3

)) is of continuum cardinality. These results open up a few distinct directions for future research. First, note that Lemma 9 raises the possibility that pPol({R 01 1/3 , σ k }) is covered by pPol({R 01 1/3 , σ k+1 }), i.e., that there does not exist any strong partial clone inbetween. If this is indeed the case then the cardinality of Int(pPol(R 1/3 ), pPol(R 01 1/3 )) might be countably infinite. Second, it would be interesting to determine the strong partial clones covered by pPol(R = = =01 1/3

). Since pPol(R = = =01 1/3

) is infinitely generated (by Theorem 5) a good starting point is to determine whether every strong partial subclone of pPol(R = = =01 1/3

) is contained in a maximal strong partial subclone of pPol(R = = =01 1/3

), or if there exists a countably infinite chain of strong partial clones in Int(Π B ) such that the union of this chain equals pPol(R = = =01 1/3

).

Theorem 5 : 3 }

 53 [START_REF] Lagerkvist | The power of primitive positive definitions with polynomially many variables[END_REF] Let Γ be a finite set of relations over a finite domain such that Pol(Γ) has a basis consisting of unary operations. Then pPol(Γ) is infinitely generated.Since Pol({R = = =01 1/) = Π B , it can be generated by a single projection, and so by Theorem 5 we have that pPol(R = = =01 1/3

{α 5 , α 6 } {α 5 , α 7 } {α 6 , α 7 } . . . {α 5 , α 6 , α 7 ,

 565767567

Fig. 1 .

 1 Fig. 1. A visualization of Int(pPol(R1/3), pPol(R = = =01 1/3

Theorem 15 :

 15 The set Int(pPol(R 01 1/3 ), pPol(R = = =01 1/3

  the ith component of t, and we let Proj i1,...,i k (t) = (x i1 , . . . , x i k ), 1 ≤ k ≤ k, denote the projection of t on the coordinates i 1 , . . . , i k ∈ {1, . . . , k}. Similarly, if R is a k-ary relation we let Proj i1,...,i k

ACKNOWLEDGEMENTS

We thank the anonymous reviewers for several helpful suggestions on how to improve the paper. The third author has received funding from the DFG-funded project "Homogene Strukturen, Bedingungserfüllungsprobleme, und topologische Klone" (Project number 622397).


R Zentar

P Y Hicher

G Moulin

Identi®cation of soil parameters by inverse analysis

This paper presents a methodology for identifying soil parameters that takes into account dierent constitutive equations. The procedure, applied here to identify the modi®ed Cam± Clay parameters from a pressuremeter curve, is based on an inverse analysis approach, which consists of minimizing the function representing the dierence between the experimental data and the data obtained by integrating the model along the loading path in in-situ testing. The numerical process implemented here is based on the interaction of two numerical tools; an optimization code (SiDoLo) and a general ®nite element code (CESAR-LCPC).

Introduction

The increasing use of ®nite elements method in geotechnics design has also to be accompanied by appropriate methods in order to identify the parameters of the adopted soil model.

These parameters are generally assessed on the basis of laboratory test results. However, some bias in the values of the parameters can be introduced because of the disturbance to the samples due to boring, extraction and transport. In order to overcome these diculties, it is recommended to carry out in-situ tests. Furthermore, in-situ testing is now far more developed in the industrial sector because of their cost eectiveness.

Among in-situ tests, the pressuremeter test consists in studying the expansion of a cylindrical cavity within the soil.

There are dierent ways of interpreting the pressuremeter test results. They can be divided into three categories:

. those based on empirical or semi-empirical relationships between soil properties and pressuremeter parameters [1±5]; . those based on the theoretical development of cylindrical cavity expansion solutions [1,6±11]; . and those based on numerical simulations of the test [12±15].

In practice, semi-empirical methods are preferred, although in some cases it is possible to apply theoretical methods for cavity expansion. The analytical methods are developed for linear and non linear elastic material, perfectly plastic incompressible material, strain-hardening and strain-softening incompressible material, and dilating material. During the past few decades, increased research work has allowed improved constitutive models to be developed which describe in a more accurate fashion the stress-strain behaviour of soils. However, these models, when interpreting pressuremeter tests, require the use of numerical solutions.

In this paper, we propose an alternative method that is based on an inverse analysis technique which we applied in order to identify the constitutive parameters of the modi®ed Cam-Clay model. For this purpose two codes are used. The ®rst one, SiDoLo, is a parameter optimization tool. The second one, CESAR-LCPC, is a ®nite elements code directed to geomechanics. The SiDoLo code (SiDoLo: Simulation and iDenti®cation of constitutive models) is a general simulation and optimization code. The greater part of the code is strictly reserved for optimization, whereas a few subroutines are available for performing simple simulations directly within the code. The initial version of the code is described by Pilvin [START_REF] Pilvin | Identi®cation and inverse problems related to material behaviour[END_REF]. The CESAR-LCPC code is a general ®nite elements code, which has been developed at the LCPC Laboratoire Central des Ponts et Chausse es (LCPC). Several plastic and viscoplastic constitutive equations have been implemented in the code.

First, we describe the inverse analysis method and the numerical tools we used, secondly, we present the algorithm of resolution of the inverse problem. The performance of the computation system is then illustrated by an example of how the modi®ed Cam±Clay parameters can be identi®ed from pressuremeter test results.

Methodology and numerical tools

If we wish to calculate the response (R) of a system including the constitutive model (M) and its parameters (m) subjected to the actions (X), we would call it the direct problem (Fig. 1). However, if part of the system (S) were unknown to us, we would have to consider the inverse problem (Fig. 2). In the present case, no information about the parameters (m) of the constitutive model is available. In compensation, it is necessary to have complementary data concerning the response (R) in order to determine the unknown information.

The determination of the parameters of the constitutive model from the pressuremeter test consists in solving the following inverse problem: to ®nd a set of parameters (m) which minimize the dierence between the experimental data [here the pressuremeter curve de®ned as the applied pressure (p) versus the cavity wall deformation (u aa)] and the results of the calculation from a given set of parameters. This problem is classically de®ned by a function which evaluates, for a given set of parameters, the discrepancy between the model prediction and the experimental data. The formal expression of this function is:

L n P 1 t 1 À t 0 R Ã t À R PY t dt I
where the symbol k..k represents a norm in the space of the observable variables, (t 1 À t 0 ) the length of observation and [R Ã t À R PY t ], the dierence between experimental data and calculation results from a given set of model parameters. While the measurements were carried out at discrete moments, the integral in Eq. ( 1) can be replaced by a sum and the length of observation by the number of measurements. Using the Euclidean norm and introducing a diagonal weighting matrix D, Eq. (1) becomes:

L n P 1 M n M qn i R Ã i À R i À Á T D R Ã i À R i À Á P
A diagonal weighting matrix D is introduced to transform the observable variables into adimensional quantities. The quality of the measure is taken into account at this level by choosing as diagonal terms in this matrix the square of the inverse of the error estimation within the measure of each variable.

The algorithm used to resolve the non-linear optimisation problem [Eq. ( 2)], combines two classical minimisation techniques: the steepest descent method at the beginning of the process, in order to improve the initial guessing of the parameters, and a variant of the Levenberg±Marquardt method [START_REF] Nougier | Me thodes de calcul nume riques[END_REF] in order to accelerate the convergence in the ®nal phase of the identi®cation. The evaluation of the gradient, in SiDoLo optimisation code [START_REF] Pilvin | Identi®cation and inverse problems related to material behaviour[END_REF], is performed numerically. This last feature is important, as it allows the user to work with a totally disconnected program to evaluate the response of the model, without any kind of modi®cation.

The numerical method used for the resolution of the non linear optimisation problem formulated as an inverse problem to identify constitutive model parameters is schematically presented in Fig. 3. This method is composed of an optimization code (SiDoLo), a ®nite element code (CESAR-LCPC), and an interface, whose functions are the following:

. reading the new coecients proposed by the optimization code, . updating the data ®le for the ®nite element code and running the simulation problem, . reading the results and computing the new values of the observable variables used in the following iteration of the optimization procedure.

Numerical modelling of a pressuremeter test

The problem of the cylindrical cavity expansion was treated, through a modi®ed Cam±Clay model [START_REF] Roscoe | On the generalise stress±strain behaviour of wet clay[END_REF], in view of interpreting pressuremeter tests performed in a clayey soil.

The modi®ed Cam±Clay model version used in the present study is a linear elastic, plastic model. The elastic part includes two parameters: the Young's modulus, E, and the Poisson's ratio, #. The plastic part includes the slope of the critical state line in the qY p H diagram (M), the parameter , which gouverns the amplitude of the plastic volumetric strain, and can be related to the classical Cam±Clay model parameters by

l À

, p H 0 which is the initial value of the hardening variable p H and depends on the initial void ratio e 0 . In order to calculate stress and pore pressure changes in the soil caused by the expansion of the pressuremeter cavity, a coupled analysis was carried out. During this analysis, the soil was considered as saturated and the soil permeability was kept constant during the expansion test. The initial stress state was de®ned by ' H v0 , ' H r0 ' H 0 . The required parameters for this analysis are summarised in Table 1.

Loading conditions around the probe were modelled as an axisymmetric problem in plane strain conditions. The dimensions for the problem are shown in Fig. 4. The probe, with radius, a, applies the pressure on the cavity wall. The soil boundaries considered for the numerical simulations are far enough from the probe to ensure that they do not aect the measurements, as shown by Nahra and Frank [START_REF] Nahra | Contributions nume riques et analytiques a l'e tude de laconsolidation autour du pressiomeÁ tres[END_REF] and Acar et al. [START_REF] Accar | Interpretation of the dissipation of penetration pore pressure[END_REF], and thus can be regarded as ®xed boundaries. For simplicity, symmetry in the horizontal plane was assumed. With reference to the middle point of the membrane, the dimensions of the solid section to be considered are 30a width and unit height. The soil around the probe is modelled using a mesh of 304 nodes and 81 eight-node isoparametric elements, with additional degrees of freedom for assessing the pore pressure.

In¯uence of Cam±Clay parameters on the numerical results

From the pressuremeter curve, we intend to determine several parameters of the modi®ed Cam±Clay model. It is evident, however, that from one curve an important number of parameters is impossible to determine. That is why, before testing the numerical process developed here to identify the modi®ed Cam-Clay parameters from pressuremeter tests, it is necessary to know which parameters can be easily determined from this test, that is, which parameter can aect the numerical response in a signi®cant way.

The ®rst calculation, called the reference calculation, is performed with the set of parameter values as presented in Table 2. These values are representative of a natural soft clay. In all analyses, the permeability ratio k r ak z is assumed to be 1.

In order to examine their eects on the calculated pressuremeter curve, we present, for each Cam±Clay parameter (E, #, , M, p H 0 ), the comparison between the curve obtained with the reference set (Table 2) and the curve obtained by changing the value of one parameter by 50%, all the other parameters being kept equal to the reference value (Fig. 5).

This study shows that the calculation is greatly aected by the variation of Young's modulus, E, by the preconsolidation pressure, p H 0 , and by the critical state constant M; it is slightly aected by the variation of Poisson's ratio, # and not aected by the value of .

Taking into account these results, the numerical process developed above was then tested in order to identify the Cam±Clay parameters aecting the pressuremeter curve calculation, i.e. E, M and p H 0 .

Validation procedure

In order to avoid all the problems derived from the capacity of the modi®ed Cam± Clay model to describe the soil behaviour and from the uncertainties on the soil characteristics, we propose to base the validation of the methodology at ®rst on the numerical curve obtained with the reference set of parameters, which is considered as the result of a real pressuremeter test.

In the ®rst place, we used the proposed procedure to determine one parameter. All the other parameters are kept at their reference values (Table 2) while we try to determine one parameter by allocating it an initial value dierent by 50% from the reference value. We observe that a satisfactory determination of the unknown parameter is achieved, the calculation taking only few iterations.

For example, to determine the preconsolidation pressure starting with an initial value of 40 kPa, we obtain the real value of 80 kPa after 12 iterations. The determination of the Young's modulus E, and of the critical state constant M produce the same good results (Fig. 6).

Secondly, we made an attempt to use our procedure to determine the parameter pairs: (E, #); (E, p H 0 ); (E, M); (#, p H 0 ); (#, M); (p H 0 , M). All the other parameters are kept at the reference values (Table 2), while we try to determine the two other parameters, whose initial values were dierent by 50% from there reference values. We note that the proposed procedure made it possible to obtain with accuracy the reference curve and the reference values for the parameter pairs (E, p H 0 ); (E, M); (#, p H 0 ); (#, M) (Fig. 7a±d). For the determination of the pair (E, #), the calculated curve reproduces accurately the reference curve (Fig. 7e), but the parameter values determined are dierent from the reference values (deduced parameters: E=923 kPa, #=0.2).

This result can be justi®ed by the fact that the pressuremeter test is a deviatoric test, and thus, the stress-strain relationship of the cavity wall is governed by the shear modulus G. G Ea 2 Ã 1 # Q Thus, an in®nite number of (E, #) parameter pairs corresponding to the same value of the shear modulus G can minimize the distance between the reference curve and the calculated curve, as long as Eq. ( 3) is veri®ed. If we calculate, from the (E, #) value obtained after the optimization procedure, the value of the shear modulus, we obtain exactly the reference value (G=384.6 kPa).

For the determination of the pair (p H 0 , M), the calculated pressuremeter curve reproduces accurately the reference curve (Fig. 7f), but the optimized parameter values are dierent from the reference values. Moreover, as shown in Table 4, for two dierent initial values of M and p H 0 , the parameter values obtained, according to inverse calculation, are dierent. We can notice that the dierence obtained between the calculated and the reference values aects the pore water pressure curve. Therefore, in order to overcome this diculty, we intend to introduce the pore water pressure data as complementary information in the numerical process to identify M and p H 0 . In these conditions, it is possible, with the same initial values presented in Table 4, to reach the reference values of M and p H 0 after a few iterations. The two references curves (pressuremeter curve and pore pressure evolution) are accurately reproduced (Fig. 8).

Thus, by introducing the pore water pressure as complementary information, we could uncouple the in¯uence of the two parameters M and p H 0 . The origin of the coupling between the parameters M and p H 0 can be explained by the fact that the soil behavior is gouverned by the eective stresses, while the optimization process is driven by the knowledge of the total stress at the cavity wall. Under these conditions several couples M, p H 0 can produce the same numerical results in terms of total stress, i.e. the pressure±volume change of the cavity relationship, but all the solutions correspond to dierent eective stress paths. If the eective stress condition at the cavity wall are imposed by the pore pressure evolution, the optimization procedure leads in that case to the determination of a sole couple M, p H 0 corresponding to the reference values.

Application to pressuremeter tests on Saint-Herblain Clay

The application of the inverse method to interpret pressuremeter test has shown that from an ideal pressuremeter test, we are able to identify several parameters of the modi®ed Cam±Clay model. In the ideal case, wherever the information about pore water pressure is available, we showed that three parameters can be identi®ed: the shear modulus G, the preconsolisolidation pressure p H 0 and the critical state constant M. In practice however, the measurement of the pore water pressure is often not available, so in this case only two parameters can be identi®ed. We decided to concentrate on the determination of the shear modulus G and of the critical state constant M. The preconsolidation pressure, p H 0 , the gradient of the swelling line, , and the gradient of the normal consolidation line, l can be identi®ed from onedimensional consolidation tests.

The studied site, named Saint-Herblain (in the vicinity of Nantes) is situated in the Loire Palaeolithic period. It is constituted by modern river clayey alluvium deposits. This clay is characterised by a high plasticity index and is slightly or moderately organic and overconsolidated at the surface. At the studied depth (6.50±7.50 m), one pressuremeter test and two one-dimensional consolidation test were performed. The pressuremeter test was performed at a depth of 7.00 m. The equipment used was a Me nard pressuremeter. The drilling of the borehole was done under bentonitic mud injection, in order to reduce the soil decompression around the cavity.

The two one-dimensional consolidation tests were performed on samples between 7.30 and 7.38 m. At this depth, the clay is slightly overconsolidated (OCR=1.6). Table 5 summarises the physical characteristics of the clay specimen.

The one-dimensional consolidation apparatus used in this study was modi®ed so that the pore pressure could be monitored and measured during the test. The initial pore pressure was considered to be equal to the in-situ pore pressure. Lateral stresses could also be measured during the test.

The one-dimensional consolidation curves for the two specimens are presented in Fig. 9a. and b. On the same graphs, the dierence between the pore water pressure generated at the base of the specimen (ub) and the back pressure applied (uc) is reported. To derive the soil parameters from these curves, the procedure recommended by LCPC was used [START_REF] Mieussens | Essais de compressibilite aÁ l'oedomeÁ tre. Proce dures recomman-de es par les Laboratoires des Ponts et Chausse es[END_REF].

The dierent parameters deduced from the two one-dimensional consolidation curves are presented in Table 6. We can note the high values of the initial void ratio (between 3.56 and 3.86), and of the compression index C (between 2.33 and 2.77) for the two specimens. Results obtained on the two specimens are comparable and representative of a highly plastic clay.

We know that the value of the preconsolidation pressure is aected by the strain rate [22±24]. In order to derive the value of the preconsolidation pressure for the strain rate of 2Â10 À4 s À1 , corresponding to the average strain rate at the cavity wall during the pressuremeter test, we used the following relation [START_REF] Moulin | Etat limite d'une Argile Naturelle, L'argile de Pornic[END_REF]:

' H p 4 ' H p 4 o 4 4 0 ! Ce CcÀCs ' H p 60 2 Â 10 À4 0X66 Â 10 À6 0X14 2X77À0X14 ' H p 81 k
Having determined the values of l, and ' H p (note that the value of ' H p was considered close to that of p H 0 ), and assuming that the initial stress state is de®ned at 7 m depth by: we can now apply the identi®cation procedure to the pressuremeter test in order to determine the values of the two remaining parameters G and M. We can see in Fig. 10 that we have a very close agreement between calculated and experimental curves. The values of the shear modulus G and of the critical state constant M obtained from the optimisation procedure are respectively 705 kPa and 1.19. This last value is We can therefore propose a methodology of the identi®cation of Cam±Clay parameters based on data obtained from two tests: one-dimensional consolidation test and pressuremeter test. The main advantage is that these two tests can be considered as routine tests for geotechnics projects. Table 7 summarizes the approach.

À' r0 ' 0 p 0 70 k À' v 105 k Àu 50 k

Conclusions

In this study, our aim was to develop a complete inverse method which could be applied to various problems dealing with geomechanics, by associating a ®nite element code with an optimization code. In the present paper we applied this method to the identi®cation of soil parameters by using in-situ testing, i.e. the pressuremeter test.

The resolution of the inverse problem of the cylindrical cavity expansion in an elastoplastic medium showed the ability of the method to determine soil parameters wherever the modi®ed Cam±Clay model was used.

The parametric study of the pressuremeter test calculation with the ®nite elements method lighlighted the in¯uence of each parameter on the numerical response. From these results, we proposed to use the pressuremeter results in order to determine the most in¯uential ones.

This study revealed the diculty in the inverse analysis to de®ne parameters whenever a strong coupling exists between them.

In the case of a coupling between E and # because of the test type (purely deviatoric), the inverse analysis cannot be used to identify these two parameters simultaneously.

In the case of coupling between M and p H 0 , the problem can be solved by considering the pore water pressure as complementary information in the calculation of the pressuremeter test. The application on pressuremeter tests performed in Saint-Herblain clay con®rmed the ability of the proposed procedure to identify the shear modulus G and the critical state constant M. This study showed that the parameters values deduced from the pressuremeter test optimization are close to those deduced from classical laboratory tests, in particular the triaxial test.

We can therefore propose a methodology of Cam±Clay parameters identi®cation based on the data obtained simultaneously from one-dimensional consolidation tests and pressuremeter tests, considered as routine tests in geotechnics projects. The method can be generalized to dierent in-situ testing and also to other constitutive models, provided that the values of the parameters to be determined have a signi®cant in¯uence on the results of the ®nite elements calculation of the given insitu test. The number of parameters which can be derived from inverse analysis depends on the available number of in-situ tests on the same soil and on the number of variables measured during each test.

Fig. 1 .

 1 Fig. 1. Resolution of the direct problem.

Fig. 2 .

 2 Fig. 2. Resolution of the inverse problem.

Fig. 3 .

 3 Fig. 3. Numerical process to identify relationship parameters.

E

  Fig. 4. Axial symmetric model of a soil thickness unit in the vertical plane (simpli®ed mesh).

Fig. 5 .

 5 Fig. 5. Modi®ed Cam±Clay parameter eects on the pressuremeter curve.

Fig. 6 .

 6 Fig. 6. Application results of the numerical process to identify M and p H 0 .

Fig. 7 (

 7 Fig. 7(c±f). Results of the identi®cation of the parameter pairs.

Fig. 10 .

 10 Fig. 10. Application results of the numerical process to identify G and M from pressuremeter test on Saint-Herblain clay at 7 m depth.

  found to be close to the one deduced from triaxial tests (CUC) on Saint-Herblain Clay at the same depth as shown in Fig. 11 (M=1.25).

Table 1 Modi®ed

 1 Cam±Clay parameters

Table 2

 2

	Parameter values of the simulation procedure
	E	#	G	l		M	À 0	p H 0	k r k z	' H r0 ' H 0	' H v0
	(kPa)		(kPa)					(kPa)	m/s	(kPa)	(kPa)
	1000	0.3	384	1.0	0.1	1.2	2.0	80	10 À9	50	60

Table 4

 4 Initial and ®nal values after back calculation to identify the (M, p H

	0 ) pair

Fig. 8. Result of the back calculation of the pressuremeter test taking into account the porewater pressure as complementary information.

Table 5

 5

	Physical characteristics of Saint-Herblain clay samples
	Physical characteristic	Specimen 1	Specimen 2
	Depth (m)	7.30±7.34	7.34±7.38
	Water content (%)	134.3	145.4
	Dry unit weight (KN/m 3 )	5.59	5.34
	Unit weight (KN/m 3 )	13.09	13.20

Table 6

 6 Parameters of Saint Herblain clay specimens deduced from one-dimensional consolidation

			Fig. 9. One-dimensional consolidation test results for two specimens.
	Specimen	C s	C s a2X3	C	l C a2X3	C s aC	e o	' H p (kPa)	4 10 À6 s À1	C e	C e a C
	1	0.16	0.07	2.33	1.01	0.07	3.56	65	3.33
	2	0.14	0.06	2.77	1.15	0.04	3.85	60	0.66	0.14	0.05

Table 7

 7 Identi®cation of Cam±Clay parametersOne dimensional consolidation test l, , p H H 0 can also be obtained from pressuremeter tests if the pore water pressure is measured during the test.

	c0

a p