Friedrich Wehrung Dedicated

George Grätzer

Tamás Schmidt

A SOLUTION TO DILWORTH'S CONGRUENCE LATTICE PROBLEM

Keywords: 2000 Mathematics Subject Classification. 06B15, 06B10, 06A12. Secondary 08A30, 08B10 Lattice, algebraic, distributive, congruence, congruence-compatible, semilattice, weakly distributive, free set

We construct an algebraic distributive lattice D that is not isomorphic to the congruence lattice of any lattice. This solves a long-standing open problem, traditionally attributed to R. P. Dilworth, from the forties. The lattice D has compact top element and ℵ ω+1 compact elements. Our results extend to any algebra possessing a congruence-compatible structure of a joinsemilattice with a largest element.

Introduction

For an algebra L (i.e., a nonempty set with a collection of operations from finite powers of L to L), a congruence of L is an equivalence relation on L compatible with all operations of L. A map f : L n → L (for some positive integer n) is congruence-compatible, if every congruence of L is a congruence for f . (This occurs, for example, in case f is a polynomial of L, that is, a composition of basic operations of L, allowing elements of L as parameters.) For elements x, y ∈ L, we denote by Θ L (x, y) the least congruence that identifies x with y, and we call the finite joins of such congruences finitely generated. We denote by Con L (resp., Con c L) the lattice (resp., (∨, 0)-semilattice) of all congruences (resp., finitely generated congruences) of L under inclusion. A homomorphism of join-semilattices µ : S → T is weakly distributive at an element x of S, if for all y 0 , y 1 ∈ T such that µ(x) ≤ y 0 ∨ y 1 , there are x 0 , x 1 ∈ S such that x ≤ x 0 ∨ x 1 and µ(x i ) ≤ y i , for all i < 2. We say that µ is weakly distributive, if it is weakly distributive at every element of S. (In case both S and T are distributive, this is equivalent to the definition presented in [START_REF] Wehrung | A uniform refinement property for congruence lattices[END_REF]. Moreover, it extends the original definition given by Schmidt [START_REF] Schmidt | The ideal lattice of a distributive lattice with 0 is the congruence lattice of a lattice[END_REF][START_REF] Schmidt | A survey on congruence lattice representations[END_REF].)

In the present paper we prove the following result (cf. Theorem 6.1).

Theorem. There exists a distributive (∨, 0, 1)-semilattice S such that for any algebra L with a congruence-compatible structure of a (∨, 1)-semilattice, there exists no weakly distributive (∨, 0)-homomorphism µ : Con c L → S with 1 in its range. Furthermore, S has ℵ ω+1 elements.

As every isomorphism is weakly distributive and by using an earlier result of the author that makes it possible to eliminate the bound 1 in L (cf. Section 7), it follows that the semilattice S is not isomorphic to Con c L, for any lattice L. Hence the ideal lattice of S is not isomorphic to the congruence lattice of any lattice.

We shall now give some background on the problem solved by our theorem. Funayama and Nakayama [START_REF] Funayama | On the distributivity of a lattice of lattice congruences[END_REF] proved in 1942 that Con L is distributive, for any lattice (L, ∨, ∧). Dilworth proved soon after that conversely, every finite distributive lattice is isomorphic to the congruence lattice of some finite lattice (see [4, pp. 455-456] and [START_REF] Grätzer | On the Congruence Lattice of a Lattice[END_REF]). Birkhoff and Frink [START_REF] Birkhoff | Representations of lattices by sets[END_REF] proved in 1948 that the congruence lattice of any algebra is what is nowadays called an algebraic lattice, that is, it is complete and every element is a join of compact elements (see [START_REF] Grätzer | General Lattice Theory[END_REF]). The question whether every algebraic distributive lattice is isomorphic to Con L for some lattice L, often referred to as CLP ('Congruence Lattice Problem'), is one of the most intriguing and longest-standing open problems of lattice theory. In some sense, its first published occurrence is with the finite case as an exercise with asterisk (attributed to Dilworth) in the 1948 edition of Birkhoff's lattice theory book [START_REF] Birkhoff | Lattice Theory[END_REF]. The first published proof of this result seems to appear in Grätzer and Schmidt's 1962 paper [START_REF] Grätzer | On congruence lattices of lattices[END_REF]. However, it seems that the earliest attempts at CLP were made by Dilworth himself, see [4, pp. 455-456].

This problem has generated an enormous amount of work since then, in a somewhat complex pattern of interconnected waves. Grätzer and Schmidt proved in 1963 that every algebraic lattice is isomorphic to the congruence lattice of some algebra [START_REF] Grätzer | Characterizations of congruence lattices of abstract algebras[END_REF]. The reader can find in Schmidt's monograph [START_REF] Schmidt | A survey on congruence lattice representations[END_REF] a survey about congruence lattice representations of algebras. The surveys by Grätzer and Schmidt [START_REF] Grätzer | Congruence Lattices[END_REF][START_REF] Grätzer | Finite lattices and congruences. A survey[END_REF] and Grätzer's monograph [START_REF] Grätzer | The Congruences of a Finite Lattice: a Proof-by-Picture Approach[END_REF] are focused on congruence lattices of (mainly finite) lattices, while the survey by Tůma and Wehrung [START_REF] Tůma | A survey of recent results on congruence lattices of lattices[END_REF] is more focused on congruence lattices of infinite lattices. The main connection between the finite case and the infinite case originates in Pudlák's idea [START_REF] Pudlák | On congruence lattices of lattices[END_REF] of lifting, with respect to the Con c functor, diagrams of finite distributive (∨, 0)-semilattices. Růžička, Tůma, and Wehrung prove in [START_REF] Růžička | Distributive congruence lattices of congruencepermutable algebras[END_REF] that there are bounded lattices of cardinality ℵ 2 whose congruence lattices are isomorphic neither to the normal subgroup lattice of any group, nor to the submodule lattice of any module; furthermore, the bound ℵ 2 is optimal. Some of the more recent works emphasize close connections between congruence lattices of lattices, ideal lattices of rings, dimension theory of lattices, and nonstable K-theory of rings, see for example [START_REF] Bergman | Von Neumann regular rings with tailor-made ideal lattices[END_REF][START_REF] Goodearl | Representations of distributive semilattices in ideal lattices of various algebraic structures[END_REF][START_REF] Goodearl | The complete dimension theory of partially ordered systems with equivalence and orthogonality[END_REF][START_REF] Růžička | Lattices of two-sided ideals of locally matricial algebras and the Γ-invariant problem[END_REF][START_REF] Wehrung | Non-measurability properties of interpolation vector spaces[END_REF][START_REF] Wehrung | A uniform refinement property for congruence lattices[END_REF][START_REF] Wehrung | Representation of algebraic distributive lattices with ℵ 1 compact elements as ideal lattices of regular rings[END_REF].

Distributive algebraic lattices are ideal lattices of distributive (∨, 0)-semilattices (see Section 2), and for a lattice L, Con L is isomorphic to the ideal lattice of Con c L. We obtain the following more convenient equivalent formulation of CLP (see [START_REF] Tůma | A survey of recent results on congruence lattices of lattices[END_REF] for details): CLP (semilattice formulation). Is every distributive (∨, 0)-semilattice representable, that is, isomorphic to Con c L, for some lattice L?

In particular, the semilattice S of our theorem provides a counterexample to CLP. Among the classical positive partial results are the following:

(1) Every distributive (∨, 0)-semilattice S of cardinality at most ℵ 1 is representable, see Huhn [START_REF] Huhn | On the representation of algebraic distributive lattices II[END_REF][START_REF] Huhn | On the representation of algebraic distributive lattices III[END_REF]. (2) Every distributive lattice with zero is representable, see Schmidt [START_REF] Schmidt | The ideal lattice of a distributive lattice with 0 is the congruence lattice of a lattice[END_REF].

Further works extended the class of all representable distributive (∨, 0)-semilattices, for example to all (∨, 0)-direct limits of sequences of distributive lattices with zero, see [START_REF] Wehrung | Forcing extensions of partial lattices[END_REF]. Moreover, the representing lattice L can be taken relatively complemented with zero. This also holds for case (2) above. However, the latter result has been extended further by Růžička [START_REF] Růžička | Lattices of two-sided ideals of locally matricial algebras and the Γ-invariant problem[END_REF], who proved that the representing lattice can be taken relatively complemented, modular, and locally finite. This is not possible for (1) above, as, for |S| ≤ ℵ 1 , one can take L relatively complemented modular [START_REF] Wehrung | Representation of algebraic distributive lattices with ℵ 1 compact elements as ideal lattices of regular rings[END_REF], relatively complemented and locally finite [START_REF] Grätzer | Congruence amalgamation of lattices[END_REF], but not necessarily both [START_REF] Wehrung | Semilattices of finitely generated ideals of exchange rings with finite stable rank[END_REF].

On the negative side, the works in [START_REF] Ploščica | Congruence lattices of free lattices in nondistributive varieties[END_REF][START_REF] Tůma | Simultaneous representations of semilattices by lattices with permutable congruences[END_REF][START_REF] Wehrung | Non-measurability properties of interpolation vector spaces[END_REF][START_REF] Wehrung | A uniform refinement property for congruence lattices[END_REF] show that lattices with permutable congruences are not sufficient to solve CLP. More precisely, there exists a representable distributive (∨, 0, 1)-semilattice of cardinality ℵ 2 that is not isomorphic to Con c L for any lattice L with permutable congruences. The finite combinatorial reason for this lies in the impossibility to prove certain 'congruence amalgamation properties'. The infinite combinatorial reason for this is Kuratowski's Free Set Theorem (see Section 2). The latter is used to prove that certain infinitary statements called 'uniform refinement properties' fail in certain distributive semilattices.

Our proof carries a flavor of commutator theory with the structure of a semilattice, essentially because of Lemma 5.1, the Erosion Lemma. A precedent of this sort of situation occurs with Bill Lampe's wonderful trick used in [START_REF] Freese | Congruence lattices of algebras of fixed similarity type. I[END_REF] to prove that certain algebraic lattices require, for their congruence representations, algebras with many operations: namely, the term condition used in commutator theory in, say, congruence-modular varieties (or larger, as considered in [START_REF] Kearnes | The relationship between two commutators[END_REF][START_REF] Tůma | Congruence lifting of diagrams of finite Boolean semilattices requires large congruence varieties[END_REF]).

Basic concepts

A (∨, 0)-semilattice S is distributive, if c ≤ a ∨ b
in S implies that there are x ≤ a and y ≤ b in S such that x ≤ a, y ≤ b, and c = x ∨ y. Equivalently, the ideal lattice of S is a distributive lattice, see [START_REF] Grätzer | General Lattice Theory[END_REF]Section II.5].

The assignment L → Con c L is extended, the usual way, to a functor from algebras with homomorphisms to (∨, 0)-semilattices with (∨, 0)-homomorphisms. For a positive integer m, an algebra L has (m + 1)-permutable congruences, if

a ∨ b = c 0 • c 1 • • • • • c m
where c i equals a if i is even and b if i is odd, for all congruences a and b of L (the symbol • denotes, as usual, composition of relations).

For an algebra L endowed with a structure of semilattice, with operation (thought of as a join operation) denoted by ∨, we put Θ + L (x, y) = Θ L (y, x∨y), for all x, y ∈ L. We say that the semilattice structure on L is congruence-compatible, if every congruence of L is a congruence for ∨ (this definition extends to any operation instead of ∨); equivalently, x ≡ y (mod a) implies that x ∨ z ≡ y ∨ z (mod a), for any x, y, z ∈ L and any a ∈ Con L. In such a case, Θ + L (x, z) ⊆ Θ + L (x, y) ∨ Θ + L (y, z), for any x, y, z ∈ L.

For partially ordered sets P and Q, a map f :

P → Q is isotone, if x ≤ y implies that f (x) ≤ f (y), for all x, y ∈ P .
We shall also use standard set-theoretical notation and terminology, referring the reader to [START_REF] Jech | Set Theory[END_REF] for further information. We shall denote by P(X) the powerset of a set X, by [X] <ω the set of all finite subsets of X, and by [X] n (for n < ω) the set of all n-element subsets of X. For a map Φ : [X] n → [X] <ω , we say that an (n + 1)-element subset U of X is free with respect to Φ, if x / ∈ Φ(U \ {x}) for all x ∈ U . The following statement of infinite combinatorics is one direction of a theorem due to Kuratowski [START_REF] Kuratowski | Sur une caractérisation des alephs[END_REF].

Kuratowski's Free Set Theorem. Let n be a natural number and let X be a set with |X| ≥ ℵ n . For every map Φ : [X] n → [X] <ω , there exists a (n + 1)-element free subset of X with respect to Φ.

We identify every natural number n with the set {0, 1, . . . , n -1}, and we denote by ω the set of all natural numbers, which is also the first limit ordinal. We shall usually denote elements in semilattices by bold math characters a, b, c, . . . .

Free distributive extension of a (∨, 0)-semilattice

As in [START_REF] Wehrung | Non-extendability of semilattice-valued measures on partially ordered sets[END_REF], we shall use the construction of a "free distributive extension" R(S) of a (∨, 0)-semilattice S given by Ploščica and Tůma in [24, Section 2] Section 1]. For convenience, we present an equivalent formulation here.

I K (E) presented in [35,
For a (∨, 0)-semilattice S, we shall put 1)-( 3)) below:

C(S) = {(u, v, w) ∈ S 3 | w ≤ u ∨ v}. A finite subset x of C(S) is projectable (resp., reduced ), if it satisfies condition (1) (resp., (
(1) x contains exactly one diagonal triple, that is, a triple of the form (u, u, u);

we put u = π(x). (2) (u, v, w) ∈ x and (v, u, w) ∈ x implies that u = v = w, for all u, v, w ∈ S. (3) (u, v, w) ∈ x \ {(π(x), π(x), π(x))} implies that u, v, w π(x), for all u, v, w ∈ S.
In particular, observe that if x is reduced, (u, v, w) ∈ x, and (u, v, w) is nondiagonal, then u = v and the elements u, v, and w are nonzero.

We denote by R(S) (resp., R(S)) the set of all projectable (resp., reduced) subsets of C(S), endowed with the binary relation ≤ defined by x ≤ y ⇐⇒ ∀(u, v, w) ∈ x \ y, either u ≤ π(y) or w ≤ π(y).

(3.1)

We call π the canonical projection from R(S) onto S. Observe that in general, π is not a join-homomorphism (however, see Remark 3.3). It is straightforward to verify that ≤ is a partial ordering on R(S) (and thus on the subset R(S)). Now we shall present, in terms of rewriting rules, the steps (i)-(iv) of the algorithm stated in [24, Lemma 2.1], aiming at Corollary 3.2.

For finite subsets x and y of C(S), let x → 1 y hold, if there exists a non-diagonal (a, b, c) ∈ x such that (b, a, c) ∈ x and y = (x \ {(a, b, c), (b, a, c)}) ∪ {(c, c, c)}.

Denote by → *

1 the reflexive and transitive closure of → 1 on finite subsets of C(S), and denote by R 1 (S) the set of all finite x ⊆ C(S) such that (a, b, c) ∈ x and (b, a, c)

∈ x implies that a = b = c, for all a, b, c ∈ S. Put R 1 (S) = R(S) ∩ R 1 (S). For a finite subset x of C(S), we put ϕ(x) = (x \ {(u, u, u) | u ∈ X}) ∪ X, X, X , where X = {u ∈ S | (u, u, u) ∈ x}.
For x ∈ R(S) and a finite subset y of C(S), let x → 2 y hold, if there exists a non-diagonal (a, b, c) ∈ x such that b ≤ π(x) and

y = (x \ {(a, b, c), (π(x), π(x), π(x))}) ∪ {(c ∨ π(x), c ∨ π(x), c ∨ π(x))}.
Observe that necessarily, y belongs to R(S) as well, and denote by → * 2 the reflexive and transitive closure of → 2 on R(S). Denote by R 2 (S) the set of all x ∈ R 1 (S) such that for all non-diagonal (a, b, c) ∈ x, the inequality b π(x) holds. For any x ∈ R(S), we put

ψ(x) = x \ {(a, b, c) ∈ x non-diagonal | either a ≤ π(x) or c ≤ π(x)}.
The correspondence with the algorithm stated in [24, Lemma 2.1] is as follows: the relation → 1 corresponds to step (i); the function ϕ corresponds to step (ii); the relation → 2 corresponds to step (iii); the function ψ corresponds to step (iv). The following lemma is a reformulation, in terms of → 1 , → 2 , ϕ, and ψ, of [24, Lemma 2.1].

Lemma 3.1. Let x, y ∈ R(S). Then there exists (z 1 , z 2 ) ∈ R 1 (S) × R 2 (S) such that x ∪ y → * 1 z 1 and ϕ(z 1 ) → * 2 z 2 .
Furthermore, for any such pair (z 1 , z 2 ), ϕ(z 1 ) belongs to R 1 (S) and ψ(z 2 ) is the join, in R(S), of x and y.

Corollary 3.2. The set R(S) is a (∨, 0)-semilattice under the partial ordering defined in (3.1). Furthermore, the map j S : S → R(S), x → {(x, x, x)} is a (∨, 0)embedding.

Remark 3.3. We shall identify x with the element {(x, x, x)} of R(S), for all x ∈ S. Then observe that the canonical map π : R(S) ։ S is isotone and that the restriction of π to S is the identity. The following is an easy consequence of (3.1).

x ≤ y ⇐⇒ x ≤ π(y), for all (x, y) ∈ S × R(S). (3.2)
Now the elements of R(S) \ S are exactly those subsets x of C(S) ∪ S (disjoint union) containing exactly one element of S, denoted by π(x), while x \ {π(x)} is nonempty and all its elements are triples (a, b, c) ∈ C(S) such that (b, a, c) / ∈ x and a, b, c π(x).

We shall use the symbol ⊲⊳ S , or ⊲⊳ if S is understood, to denote the elements of R(S) defined as

⊲⊳ S (u, v, w) =      w, if either u = v or v = 0 or w = 0, 0, if u = 0, {(0, 0, 0), (u, v, w)}, otherwise,
for all (u, v, w) ∈ C(S). Then one can prove easily the formula

x = (⊲⊳ S (a, b, c) | (a, b, c) ∈ x), for all x ∈ R(S). (3.3)
The following is a slight strengthening of [24, Theorem 2.3], with the same proof.

The uniqueness statement follows from (3.3).

Lemma 3.4. Let S and T be (∨, 0)-semilattices and let f : S → T be a (∨, 0)homomorphism. Furthermore, let ı : C(im f ) → T be a map such that ı(x, y, z) ∨ ı(y, x, z) = z and ı(x, y, z) ≤ x, for all (x, y, z) ∈ C(im f ). Then there exists a unique map f (ı) : R(S) → T such that f (ı) (⊲⊳ S (x, y, z)) = ı(f (x), f (y), f (y)), for all (x, y, z) ∈ C(S).

By applying Lemma 3.4 to the map j T • f and defining ı as the restriction of ⊲⊳ T to C(im f ), we obtain item (1) of the following result. Item (2) follows easily. Proposition 3.5.

(1) For (∨, 0)-semilattices S and T , every (∨, 0)-homomorphism f : S → T extends to a unique (∨, 0)-homomorphism R(f

) : R(S) → R(T ) such that R(f )(⊲⊳ S (u, v, w)) = ⊲⊳ T (f (u), f (v), f (w)), for all (u, v, w) ∈ C(S). (2) The assignment S → R(S), f → R(f ) is a functor.
Putting R 0 (S) = S and R n+1 (S) = R(R n (S)) for each n, the increasing union

D(S) = (R n (S) | n < ω) is a distributive (∨, 0)-semilattice extending S. Fur- thermore, putting D(f ) = (R n (f ) | n < ω)
for each (∨, 0)-homomorphism f , we obtain that D is a functor. The proof of the following lemma is straightforward. Lemma 3.6. Let S be a (∨, 0)-semilattice and let (S i | i ∈ I) be a family of (∨, 0)subsemilattices of S. The following statements hold:

(1)

R i∈I S i = i∈I R(S i ) and D i∈I S i = i∈I D(S i ). ( 2
)
If I is a nonempty upward directed partially ordered set and

(S i | i ∈ I) is isotone, then R i∈I S i = i∈I R(S i ) and D i∈I S i = i∈I D(S i ).
Definition 3.7. For a (∨, 0)-semilattice S and an element x ∈ D(S), we define the rank of x, denoted by rk x, as the least natural number n such that x ∈ R n (S).

The functors L and G

In the present section we shall construct the semilattice used in the counterexample and demonstrate one of its crucial properties, namely the Evaporation Lemma (Lemma 4.4).

For a set Ω, we denote by L(Ω) the (∨, 0)-semilattice defined by generators 1 and a ξ 0 , a ξ 1 (for ξ ∈ Ω), subjected to the relations a ξ 0 ∨ a ξ 1 = 1, for all ξ ∈ Ω. a ξ 0 = ({ξ}, ∅) and a ξ 1 = (∅, {ξ}), for all ξ ∈ Ω. We shall identify L(X) with the (∨, 0, 1)-subsemilattice of L(Ω) generated by the subset {a ξ i | ξ ∈ X and i < 2}, for all X ⊆ Ω. For sets X and Y , any map f : X → Y gives rise to a unique (∨, 0, 1)-homomorphism L(f

) : L(X) → L(Y ) such that L(f )(a ξ i ) = a f (ξ) i
, for all (ξ, i) ∈ X × {0, 1}. Of course, the assignment X → L(X), f → L(f ) is a functor from the category of sets with maps to the category of (∨, 0, 1)-semilattices and (∨, 0, 1)-homomorphisms.

Next, we put G = D • L, the composition of the two functors D and L. Hence, for a set Ω, the semilattice G(Ω) may be loosely described as a 'free distributive (∨, 0)-semilattice defined by generators a ξ i , for ξ ∈ Ω and i < 2, and relations (4.1)'. It is a distributive (∨, 0, 1)-semilattice, of the same cardinality as Ω in case Ω is infinite.

The proof of the following lemma is straightforward (see Lemma 3.6).

Lemma 4.1. Let Ω be a set and let (X i | i ∈ I) be a family of subsets of Ω. The following statements hold:

(1)

L i∈I X i = i∈I L(X i ) and G i∈I X i = i∈I G(X i ).
(2) If I is a nonempty upward directed partially ordered set and the family

(X i | i ∈ I) is isotone, then L i∈I X i = i∈I L(X i ) and G i∈I X i = i∈I G(X i ). Corollary 4.2.
For any set Ω and any x ∈ G(Ω), there exists a least (finite) subset X of Ω such that x ∈ G(X).

We shall call the subset X of Corollary 4.2 the support of x, and denote it by supp(x). Lemma 4.3. Let Ω be a set, let α ∈ Ω, and let i < 2. Then x ≤ y ∨ a α i implies that x ≤ y, for all x, y ∈ G(Ω \ {α}).

Proof. There exists a unique retraction r : L(Ω) ։ L(Ω \ {α}) such that r(a α i ) = 0. Put s = D(r), and observe that s(x) = x, s(y) = y, and s(a α i ) = 0. By applying s to the inequality x ≤ y ∨ a α i , we get the conclusion. The following crucial lemma describes an 'evaporation process' in G(Ω). Lemma 4.4 (Evaporation Lemma). Let α, β, δ be distinct elements in a set Ω, let i, j < 2, x ∈ G(Ω \ {β}), y ∈ G(Ω \ {α}), and z ∈ G(Ω \ {δ}). Then z ≤ x ∨ y, x ≤ a δ 0 , a α i , and y ≤ a δ 1 , a β j implies that z = 0.

Proof. For s ∈ ω and u ∈ R s+1 L(Ω) \ R s L(Ω), we shall denote by π(u) the image of u under the canonical projection from R s+1 L(Ω) to R s L(Ω). Put m = rk x, n = rk y, and k = rk z. We argue by induction on m + n + k. If z ≤ x, then z ≤ a δ 0 , thus, as z ∈ G(Ω \ {δ}), it follows from Lemma 4.3 that z = 0 so we are done. The conclusion is similar in case z ≤ y. So suppose that z x, y. If m = 0, then, as x ∈ L(Ω) and x ≤ a δ 0 , a α i with α = δ, we get x = 0, so z ≤ y, a contradiction; hence m > 0. Similarly, n > 0. Put l = max{m, n}, x * = x \ {π(x)}, and y * = y \ {π(y)} (see Remark 3.3). Furthermore, we define (using again Remark 3.3) a finite subset w of CR l-1 L(Ω) as

w =      x * ∪ y * ∪ {π(x) ∨ π(y)}, if m = n, y * ∪ {x ∨ π(y)}, if m < n, x * ∪ {π(x) ∨ y}, if m > n. (4.2)
Claim. The set w belongs to R l L(Ω), and x, y ≤ w.

Proof of Claim. We need to verify that w is a reduced subset of CR l-1 L(Ω), modulo the identification of elements with diagonal triples (see Remark 3.3). It is obvious that there exists exactly one element in w ∩ R l-1 L(Ω), namely,

π(w) =      π(x) ∨ π(y), if m = n, x ∨ π(y), if m < n, π(x) ∨ y, if m > n.
This settles item (1) of the definition of a reduced set. Now suppose that there exists a non-diagonal triple (a, b, c) of elements of R l-1 L(Ω) such that (a, b, c) ∈ w and (b, a, c) ∈ w. As both x and y are reduced sets, the only possibility is m = n and, say, (a, b, c) ∈ x and (b, a, c) ∈ y. As x ∈ G(Ω \ {β}) and y ∈ G(Ω \ {α}), all elements a, b, c belong to G(Ω \ {α, β}) (see Lemma 4.1). As (a, b, c) ∈ x and x ≤ a α i , it follows from (3.1) and the assumption that (a, b, c) is non-diagonal that either a ≤ a α i or c ≤ a α i . As a, c ∈ G(Ω \ {α}), it follows from Lemma 4.3 that either a = 0 or c = 0, a contradiction. This settles item (2) of the definition of a reduced set.

Finally, let (a, b, c) ∈ w be a non-diagonal triple of elements of R l-1 L(Ω), we must verify that a, b, c π(w). Suppose, for example, that a ≤ π(w). If m = n, then a ≤ π(x) ∨ π(y) and, say, (a, b, c) ∈ x * . From π(y) ≤ y ≤ a β j it follows that a ≤ π(x) ∨ a β j . As a, π(x) ∈ G(Ω \ {β}) and by Lemma 4.3, it follows that a ≤ π(x), which contradicts the assumption that (a, b, c) is a non-diagonal triple in x. If m < n, then (a, b, c) ∈ y * and a ≤ x ∨ π(y), so a ≤ a α i ∨ π(y), and so, as a, π(y) ∈ G(Ω\ {α}) and by Lemma 4.3, it follows that a ≤ π(y), which contradicts the assumption that (a, b, c) is a non-diagonal triple in y. The proof for the case m > n is similar. So we have proved that a π(w). The proofs for b and c are similar. This settles item (3) of the definition of a reduced set.

The verification of the inequalities x, y ≤ w (see (3.1)) is straightforward. In fact, it is not hard to verify, using Lemma 3.1, that w = x ∨ y.

Claim. Now we complete the proof of Lemma 4.4. From the claim above it follows that z ≤ w. If k < l then z ≤ π(w), hence, as π(w) ∈ {π(x) ∨ π(y), x ∨ π(y), π(x) ∨ y} and by the induction hypothesis, z = 0. So suppose from now on that k ≥ l; in particular, k > 0. As π(z) ≤ z ≤ x ∨ y, it follows from the induction hypothesis that π(z) = 0. Hence, if z = 0, then there exists a non-diagonal triple (a, b, c) ∈ z∩CR l-1 L(Ω). As z ≤ w, we obtain that either (a, b, c) ∈ w or a ≤ w or c ≤ w. In the first case, say, (a, b, c) ∈ x, we get ⊲⊳(a, b, c) ≤ x ≤ a δ 0 with a, b, c ∈ G(Ω \ {δ}) (because (a, b, c) ∈ z), so ⊲⊳(a, b, c) = 0 by Lemma 4.3, a contradiction. If either a ≤ w or c ≤ w, then, by the induction hypothesis, either a = 0 or c = 0, a contradiction. Therefore, z = 0.

The Erosion Lemma

The proofs of our negative results are based on the conflict between a nonstructure theorem on the semilattices G(Ω), here the 'Evaporation Lemma' (Lemma 4.4), and a structure theorem on arbitrary bounded semilattices, Lemma 5.1, that we shall now introduce. This lemma, the Erosion Lemma, contains, despite its extreme simplicity, the gist of the present paper. Moreover, further extensions of our methods seem to use the same formulation of the Erosion Lemma, while there seem to be many different 'Evaporation Lemmas' (such as Lemma 4.4).

From now on, we shall denote by ε the 'parity function' on the natural numbers, defined by the rule

ε(n) = 0, if n is even, 1, if n is odd,
for every natural number n.

(5.1)

Throughout this section, we let L be an algebra possessing a congruence-compatible structure of semilattice (L, ∨). We put

U ∨ V = {u ∨ v | (u, v) ∈ U × V }, for all U, V ⊆ L,
and we denote by Con U c L the (∨, 0)-subsemilattice of Con c L generated by all principal congruences Θ L (u, v), where (u, v) ∈ U × U .

Lemma 5.1 (The Erosion Lemma). Let x 0 , x 1 ∈ L, and let Z = {z i | 0 ≤ i ≤ n}, with n ∈ ω \ {0}, be a finite subset of L with i<n z i ≤ z n . Put

a j = (Θ L (z i , z i+1 ) | i < n, ε(i) = j), for all j < 2.
Then there are congruences u j ∈ Con {xj }∨Z c L, for j < 2, such that z 0 ∨x 0 ∨x 1 ≡ z n ∨x 0 ∨x 1 (mod u 0 ∨u 1 ) and u j ⊆ a j ∩Θ + L (z n , x j ), for all j < 2. Proof.

Put v i = Θ L (z i ∨ x ε(i) , z i+1 ∨ x ε(i) ), for all i < n. Observe that v i belongs to Con {x ε(i) }∪Z c L. From z n ≤ x ε(i) (mod Θ + L (z n , x ε(i) )
) and z i ≡ z i+1 (mod a ε(i) ) it follows, respectively (and using z i ∨ z n = z i+1 ∨ z n in the first case), that

v i ⊆ Θ + L (z n , x ε(i) ) and v i ⊆ a ε(i) . (5.2)
Now we put

u j = (v i | i < n, ε(i) = j), for all j < 2.
Hence u j ∈ Con {xj}∨Z c L, for all j < 2. Furthermore, from (5.2) it follows that

u j ⊆ a j ∩ Θ + L (z n , x j ). Finally, from z i ∨ x ε(i) ≡ z i+1 ∨ x ε(i) (mod v i ), for all i < n, it follows that z i ∨ x 0 ∨ x 1 ≡ z i+1 ∨ x 0 ∨ x 1 (mod u 0 ∨ u 1 ). Therefore, z 0 ∨ x 0 ∨ x 1 ≡ z n ∨ x 0 ∨ x 1 (mod u 0 ∨ u 1 ).

The proof

Our main theorem is the following. Theorem 6.1. Let Ω be a set of cardinality at least ℵ ω+1 and let L be an algebra. If L has a congruence-compatible structure of (∨, 1)-semilattice, then there is no weakly distributive (∨, 0)-homomorphism from Con c L to G(Ω) with 1 in its range.

The remainder of this section will be devoted to a proof of Theorem 6.1. Suppose, to the contrary, that L and µ : Con c L → G(Ω) are as above. We fix a congruencecompatible structure of (∨, 1)-semilattice on L. There are a positive integer m and elements t 0 , . . . , t m-1 in L such that r<m µΘ L (t r , 1) = 1. (

For each ξ ∈ Ω, as µΘ L (t r , 1) ≤ 1 = a ξ 0 ∨ a ξ 1 holds for each r < m, we obtain, by using the weak distributivity of µ at Θ L (t r , 1), an integer n ξ ≥ 2 and elements z ξ r,i ∈ L, for 0 ≤ r < m and 0 ≤ i ≤ n ξ , such that z ξ r,0 = t r , z ξ r,n ξ = 1, and

µΘ L (z ξ r,i , z ξ r,i+1 ) ≤ a ξ ε(i) , for all r < m and i < n ξ . (6.2)
(We recall that ε is the parity function defined in (5.1).) After replacing z ξ r,i by t r ∨ z ξ r,i , we may also assume that t r ≤ z ξ r,i holds, for all r < m, i ≤ n ξ , and ξ ∈ Ω. As |Ω| ≥ ℵ ω+1 and ℵ ω+1 is a regular cardinal (this is the reason why ℵ ω would not work a priori), there are a positive integer n and Ω ′ ⊆ Ω such that |Ω ′ | = ℵ ω+1 and n ξ = n for all ξ ∈ Ω ′ . Pick any retraction ρ : Ω ։ Ω ′ and replace µ by G(ρ) • µ. We might lose the weak distributivity of µ, but we keep the elements z ξ r,i and the statements (6.2), which are all that matters. Furthermore, after replacing L by L/θ where (x, y) ∈ θ iff µΘ L (x, y) = 0 (for all x, y ∈ L), we may assume that µ separates zero, that is, µ -1 {0} = {0}. Now pick δ ∈ U and put Y = U \ {δ}, so |Y | = 2 n . By applying Lemma 6.2 to k = n -1 and l = 2 n-1 , we obtain the equality (z η r,0 | η ∈ Y ) = 1, that is, t r = 1. But this holds for all r < m, which contradicts (6.1). This completes the proof of Theorem 6.1. Remark 6.3. In the assumptions of Theorem 6.1, it is sufficient to restrict the weak distributivity assumption of µ to congruences Θ L (t r , 1), for r < m, satisfying (6.1).

Consequences on congruence lattices of lattices

Observe that Theorem 6.1 applies to L a lattice with a largest element. We now extend this result to arbitrary lattices. Theorem 7.1. For any set Ω and any algebra L with a congruence-compatible lattice structure, if |Ω| ≥ ℵ ω+1 , then there exists no weakly distributive (∨, 0)-homomorphism µ : Con c L → G(Ω) with 1 in its range.

Proof. Denote by L lat the given congruence-compatible lattice structure on (the underlying set of) L. It is straightforward to verify that the canonical homomorphism from Con c (L lat ) to Con c L, that to each compact congruence of L lat associates the congruence of L that it generates, is weakly distributive. As the composition of two weakly distributive homomorphisms is weakly distributive, it suffices to prove the theorem in case L is a lattice.

So let µ : Con c L → G(Ω) be a weakly distributive (∨, 0)-homomorphism with 1 in its range, where |Ω| ≥ ℵ ω+1 . As 1 = i<n µΘ L (u i , v i ), for a positive integer n and elements [START_REF] Wehrung | A uniform refinement property for congruence lattices[END_REF]Proposition 1.2] that the canonical homomorphism  : Con c K → Con c L is weakly distributive. Hence µ •  is a weakly distributive homomorphism from Con c K to G(Ω) with 1 in its range, with K a bounded lattice. This contradicts Theorem 6.1.

u i ≤ v i in L, for i < n, we get 1 = µΘ L (u, v), where u = i<n u i and v = i<n v i . Put K = [u, v]. It follows from
In particular, we obtain a negative solution to CLP. By contrast, Lampe proved in [START_REF] Lampe | Congruence lattices of algebras of fixed similarity type[END_REF] that every (∨, 0, 1)-semilattice is isomorphic to Con c G for some groupoid G with 4-permutable congruences. In particular, G(ℵ ω+1 ) ∼ = Con c G for some groupoid G with 4-permutable congruences, while there is no lattice L such that G(ℵ ω+1 ) ∼ = Con c L. This shows a critical discrepancy between general algebras and lattices.

Discussion

8.1.

A new uniform refinement property. In many works such as [START_REF] Ploščica | Congruence lattices of free lattices in nondistributive varieties[END_REF][START_REF] Růžička | Distributive congruence lattices of congruencepermutable algebras[END_REF][START_REF] Tůma | Simultaneous representations of semilattices by lattices with permutable congruences[END_REF][START_REF] Tůma | A survey of recent results on congruence lattices of lattices[END_REF][START_REF] Wehrung | A uniform refinement property for congruence lattices[END_REF][START_REF] Wehrung | Semilattices of finitely generated ideals of exchange rings with finite stable rank[END_REF][START_REF] Wehrung | Non-extendability of semilattice-valued measures on partially ordered sets[END_REF], the classes of semilattices that are representable with respect to various functors are separated from the corresponding counterexamples by infinitary statements called uniform refinement properties. We shall now discuss briefly how this can also be done here. As the proofs do not seem to add much to the already existing results, we shall omit the details.

For a positive integer m and a nonempty set Ω, denote by Sem(m, Ω) the joinsemilattice defined by generators 0, 1, and k • ξ for 0 ≤ k ≤ m + 1 and ξ ∈ Ω, subjected to the relations 0

= 0 • ξ ≤ 1 • ξ ≤ • • • ≤ m • ξ ≤ (m + 1) • ξ = 1, for ξ ∈ Ω.
Definition 8.1. For an element e in a (∨, 0)-semilattice S, we say that S satisfies CLR(e), if for every nonempty set Ω and every family (a ξ i | (ξ, i) ∈ Ω × {0, 1}) with entries in S such that e ≤ a ξ 0 ∨ a ξ 1 for all ξ ∈ Ω, there are a decomposition Ω = (Ω m | m ∈ ω \ {0}) and mappings c m : Sem(m, Ω m ) × Sem(m, Ω m ) → S, for m ∈ ω \ {0}, such that the following statements hold for every positive integer m:

(1) p ≤ q implies that c m (p, q) = 0, for all p, q ∈ Sem(m, Ω m );

(2) c m (p, r) ≤ c m (p, q) ∨ c m (q, r), for all p, q, r ∈ Sem(m, Ω m );

(3) c m (p ∨ q, r) = c m (p, r) ∨ c m (q, r), for all p, q, r ∈ Sem(m, Ω m ); (4) c m ( 1, 0) = e;

(5) The inequality c m ((k + 1)

• ξ, k • ξ) ≤ a ξ ε(k) holds, for all ξ ∈ Ω m and all k ≤ m.
If, for a fixed m ∈ ω \ {0}, we can always take Ω m = Ω while Ω n = ∅ for all n = m, we say that S satisfies CLR m (e).

The statement CLR(e) is an analogue, for arbitrary lattices, of the 'uniform refinement property' introduced in [START_REF] Wehrung | A uniform refinement property for congruence lattices[END_REF], denoted by 'URP -at e' in [START_REF] Tůma | A survey of recent results on congruence lattices of lattices[END_REF]. It is easy to verify that for any (∨, 0)-semilattices S and T , any e ∈ S, and any weakly distributive (∨, 0)-homomorphism µ : S → T , if S satisfies CLR(e), then T satisfies CLR(µ(e)). A similar observation applies to CLR m . Furthermore, a straightforward, although somewhat tedious, modification of the proof of Theorem 6.1, gives, for example, the following result. Theorem 8.2. Let L be a lattice and let e be a principal congruence of L. Then Con c L satisfies CLR(e). Furthermore, if L has (m + 1)-permutable congruences (where m is a given positive integer ), then Con c L satisfies CLR m (e). On the other hand, G(ℵ ω+1 ) (resp., G(ℵ 2 m )) does not satisfy CLR(1) (resp., CLR m (1)). 8.2. Open problems. The most obvious problem suggested by the present paper is to fill the cardinality gap between ℵ 2 and ℵ ω . In the meantime, this problem has been solved by Pavel Růžička [START_REF] Růžička | Free trees and the optimal bound in Wehrung's theorem[END_REF], who introduced a strengthening of Kuratowski's Free Set Theorem that made it possible to prove, by using the original Erosion Lemma (Lemma 5.1) and modifications of both the Evaporation Lemma (Lemma 4.4) and the Descent Lemma (Lemma 6.2) the following result: For any set Ω such that |Ω| ≥ ℵ 2 , there are no algebra L with a congruence-compatible structure of bounded semilattice and no weakly distributive (∨, 0, 1)-homomorphism µ : Con c L → G(Ω). In fact, it is not hard to modify Růžička's proof to establish that for |Ω| ≥ ℵ 2 , the semilattice G(Ω) does not satisfy CLR(1) (cf. Subsection 8.1).

The discussion in Subsection 8.1 about CLR and CLR m also suggests the following problem.

Problem 1. Prove that there exists a lattice K such that for every positive integer m, there is no lattice L with m-permutable congruences such that Con K ∼ = Con L.

Of course, it is sufficient to find a counterexample for each m, as their direct product would then solve Problem 1. Now as we know that the answer to CLP is negative, a natural question is the corresponding one for congruence-distributive varieties.

Problem 2. Is every algebraic distributive lattice isomorphic to the congruence lattice of some algebra generating a congruence-distributive variety?

Recall the classical open problem asking whether every algebraic distributive lattice is isomorphic to the congruence lattice of some algebra with finitely many operations. In view of Theorem 6.1, we may try to find the algebra with a (∨, 0)semilattice (but not (∨, 1)-semilattice) operation.

Kearnes proves in [START_REF] Kearnes | Congruence lattices of locally finite algebras[END_REF] that there exists an algebraic lattice that is not isomorphic to the congruence lattice of any locally finite algebra. In light of this result, the following question is natural. Problem 3. Does there exist a lattice L such that Con L is not isomorphic to the congruence lattice of any locally finite lattice (resp., algebra)?

In [START_REF] Tůma | Simultaneous representations of semilattices by lattices with permutable congruences[END_REF], infinite semilattices considered earlier in [START_REF] Wehrung | A uniform refinement property for congruence lattices[END_REF][START_REF] Ploščica | Congruence lattices of free lattices in nondistributive varieties[END_REF][START_REF] Wehrung | Non-measurability properties of interpolation vector spaces[END_REF] are approximated by finite semilattices, yielding, in particular, a {0, 1} 3 -indexed diagram of finite Boolean semilattices that cannot be lifted, with respect to the Con c functor, by congruence-permutable lattices. The methods used in the present paper suggest that those works could be extended to find a {0, 1} 2 m +1 -indexed diagram of finite Boolean semilattices that cannot be lifted, with respect to the Con c functor, by lattices with (m + 1)-permutable congruences.

Tůma and Wehrung prove in [START_REF] Tůma | Congruence lifting of diagrams of finite Boolean semilattices requires large congruence varieties[END_REF] that there exists a diagram of finite Boolean semilattices, indexed by a finite partially ordered set, that cannot be lifted, with respect to the Con c functor, by any diagram of lattices (or even algebras in any variety satisfying a nontrivial congruence lattice identity). This leaves open the following problem. Problem 4. Prove that any diagram of finite distributive (∨, 0)-semilattices and (∨, 0)-homomorphisms, indexed by a finite lattice, can be lifted, with respect to the Con c functor, by a diagram of (finite?) lattices and lattice homomorphisms.

We conclude with the following problem, which also appears, with a slightly different formulation, as [START_REF] Grätzer | The Congruences of a Finite Lattice: a Proof-by-Picture Approach[END_REF]Problem 10.6].

Problem 5. Prove that there exists a lattice K such that there is no modular lattice M with Con K ∼ = Con M .

Acknowledgment

My deepest thanks go to the anonymous referees for their careful reading of the paper and valuable suggestions.

Added in proof

A recent survey article partly devoted to CLP, written by George Grätzer, just appeared, as "Two Problems That Shaped a Century of Lattice Theory", Notices Amer. Math. Soc. 54, no. 6 (2007), 696-707.

  . The larger semilattice R(S) is constructed by adding new elements ⊲⊳(a, b, c), for a, b, c ∈ S such that c ≤ a ∨ b, subjected only to the relations c = ⊲⊳(a, b, c) ∨ ⊲⊳(b, a, c) and ⊲⊳(a, b, c) ≤ a. It is a semilattice version of the dimension group construction

(4. 1 )

 1 Hence L(Ω) is the same semilattice as the one presented in [24,Section 3]. It is a semilattice version of the dimension group E K (Ω) presented in[START_REF] Wehrung | Non-measurability properties of interpolation vector spaces[END_REF] Section 2]. It can be 'concretely' represented as the (semi)lattice of all pairs (X, Y ) ∈ P(Ω) × P(Ω) such that either X and Y are finite and disjoint or X = Y = Ω, with

Corollary 7 . 2 .

 72 Let Ω be a set. If |Ω| ≥ ℵ ω+1 , then there exists no lattice L with Con c L ∼ = G(Ω).

F. WEHRUNG

Hence we shall assume, from now on, that µ separates zero and n ξ = n for all ξ ∈ Ω. For every finite subset X of Ω, we shall denote by S(X) the joinsubsemilattice of L generated by {z ξ r,i | 0 ≤ r < m, 0 ≤ i ≤ n, and ξ ∈ X}. As S(X) is finite, Φ(X) = (supp µΘ L (x, y) | x, y ∈ S(X)) is a finite subset of Ω.

As |Ω| ≥ ℵ 2 n , it follows from Kuratowski's Free Set Theorem that there exists a (2 n + 1)-element subset U of Ω which is free with respect to the restriction of Φ to 2 n -elements subsets of Ω.

For all natural numbers k, l with k ≤ n -1 and l ≤ 2 k , let P (k, l) hold, if for all r < m and all disjoint X, Y ⊆ U with |X| = 2 k -l and |Y | = 2l, the following equality E r (X, Y ) holds:

The method used to prove Lemma 6.2 below could be described as 'the erosion method': namely, prove, using the Erosion Lemma, that joins of larger and larger subsets of L of the form

with k larger and larger, remain equal to 1. For large enough k, this will lead naturally to t r = 1. Lemma 6.2 (Descent Lemma). The statement P (k, l) holds, for all natural numbers k, l such that k ≤ n -1 and l ≤ 2 k . Proof. We argue by induction on 2 k + l. Obviously, P (0, 0) holds. Assuming that P (k, l) holds, we shall establish P (k ′ , l ′ ) for the next value (k ′ , l ′ ). As P (k, 2 k ) is equivalent to P (k + 1, 0), we may assume that l < 2 k , so

, for all j < 2. (6.

3)

It follows from the induction hypothesis that

, for all j < 2. (6.4)

Now recall that, by (6.2),

, for all j < 2. Using (6.3) and (6.4), it follows that µΘ L (x j , 1) ≤ a ηj ε(n-k-1) , for all j < 2. Therefore, using Lemma 5.1 with z δ r,i in place of z i , for 0 ≤ i ≤ n, and observing that t r ≤ x 0 ∨ x 1 (because t r ≤ z ξ r,i everywhere), we obtain congruences u j ∈ Con S(X∪Y ′ ∪{ηj ,δ}) c L, for j < 2, such that Θ L (x 0 ∨ x 1 , 1) ≤ u 0 ∨ u 1 and µ(u j ) ≤ a ηj ε(n-k-1) , a δ j , for all j < 2. (6.5) It follows from the definition of Φ that µ(u j ) ∈ GΦ(X ∪ Y ′ ∪ {η j , δ}) and µΘ L (x 0 ∨ x 1 , 1) ∈ GΦ(X ∪ Y ). Using the monotonicity of Φ and the freeness of U with respect to the restriction of Φ to 2 n -element subsets, we obtain

As µΘ L (x 0 ∨x 1 , 1) belongs to GΦ(X∪Y ) and by using (6.5) together with Lemma 4.4, we obtain that µΘ L (x 0 ∨ x 1 , 1) = 0, that is, since µ separates zero, x 0 ∨ x 1 = 1, which completes the proof of the equality E r (X, Y ).


Daniela Pison
email: daniela.pison@fhnw.ch

F Alonso

K Wårdell

Member, IEEE J Coste

J J Lemaire

E Schkommodau

Member, IEEE S Hemm- Ode

Dr Simone Hemm
email: simone.hemm@fhnw.ch

Prof Karin Wårdell

A METHOD FOR ELECTRIC FIELD SIMULATIONS AND ACCELERATION MEASUREMENT FOR INTRAOPERATIVE TEST SIMULATION IN DBS

Background

Despite an increasing use of deep brain stimulation (DBS) the fundamental mechanisms underlying therapeutic and adverse effects as well as the optimal stimulation site remain largely unknown. So far no group has considered simulations of electric entities for intraoperatively obtained test stimulation data to identify the stimulated volume around intraoperative DBS electrodes. The aim of the present paper is to introduce a method allowing patient-specific electric field simulations for stimulation amplitudes at different anatomical positions and taking into account the obtained clinical results objectively evaluated by acceleration measurements [1].

Methods

Institute

Results

• 115 electric field simulations performed for the eight trajectories • Data can be visualized in 3D and together with the anatomical images (Fig. 3) • E-field maps show that not always best intraoperative clinical results can be observed in the VIM but in the surrounding regions (Fig. 4)

Discussion

• Workflow and methodology for electrical field simulations on manually outlined anatomical structures have been designed and successfully applied to two patients.

• First results seem to confirm published data hypothesizing that the stimulation of other structures than the VIM might at least partially be responsible for good clinical effects: Vassal et al. [START_REF] Vassal | [END_REF] already suggested that parts of the ventro-oral nucleus (VO) could be appropriate targets as well. • New concept including a detailed analysis of the isofield maps will allow the analysis of a high amount of intraoperative data which might help to elucidate the mechanism of action of DBS.

• New successful methodology for the interpretation of multiple patients' intraoperative data in relation to the anatomical structures and the objective clinical improvements.

Figure 2 :

 2 Figure 2: Workflow for generation of patient-specific electric field simulations on patient specific anatomy

Figure 1 :

 1 Figure 1: 3D view of the manually outlinig of structures in iPlan (Brainlab). Right side: abbreviation of the structures' name.

Figure 3 :

 3 Figure 3: : Isofieldlines simulated for patient 2 for three positions on each central electrode track, color coded following the induced clinical change (green: high improvement; red: low or no improvement) and superimposed to the anatomical structures (brownish color). a) MRI T1 axial image superimposed to 3D structures and isoelectrical fields. b) 3D frontal view of structures and isoelectrical fields.

Figure 4 :

 4 Figure 4: Comparison of the structure appearance (x-axis) in function of the obtained clinical improvement (y-axis) including all performed simulations. Structures appearing in the same simulation have the same improvement value (=same horizontal level). The radius of the circles is proportional to the volume of the structures inside the isoelectrical field [%].

•

  The visual representation for all performed simulations (Fig.4) of the structures and structure combinations touched by the isoeletrical field and in relation to the corresponding clinical improvement shows: → VO and VCM often appear together with the VIM → In several cases, FF or PLR are touched by the isoelectrical field when the improvement is higher → LaCM and VCL especially appear for lower improvements


Member, IEEE Jerome Coste
email: jcoste@chu-clermontferrand.fr

J J Lemaire

E Schkommodau

Member, IEEE R Guzman

E Taub

S Hemm-Ode

Dr Simone Hemm
email: simone.hemm@fhnw.ch

Ashesh Shah
email: ashesh.shah@fhnw.ch

USING ACCELERATION SENSORS TO IDENTIFY RIGIDITY RELEASE THRESHOLD DURING DEEP BRAIN STIMULATION SURGERY

Background

Deep brain stimulation (DBS) is now a widely accepted surgical treatment for Parkinson's disease (PD). Electrodes are implanted in the patient's brain after intraoperative test stimulation. Changes in parkinsonian rigidity during test stimulation are detected by an evaluator, usually a neurologist, by identifying changes in the resistance of the patient's arm to a passive movement. When a stimulation-induced reduction in rigidity is observed, the stimulation amplitude is noted; this is the clinical rigidity release threshold. The aim of the present study was to test the hypothesis that, at the moment of reduction in rigidity, the speed with which the evaluator moves the patient's arms increases, and that this change and its amplitude can be detected with an acceleration sensor.

Methods

Institute for Medical and Analytical Technologies, Head: Prof. Dr.-Ing. Erik Schkommodau, Gründenstrasse 40, 4132 Muttenz, Switzerland. http://www.fhnw.ch/lifesciences/ima

Step 1: Data recording setup. A 3 axis accelerometer evaluation board (STEVAL-MKI022V1, ST) housed in a non-conductive printed plastic case (FullCure 830 Vero White, Objet Geometries Ltd) is mounted on the evaluators wrist using a Velcro strap. This sensor is connected to a laptop with in-house developed recording software. This software is also connected to the deep brain stimulation system which provides current during the test stimulations.

Rigidity Release Threshold Identification

Standard Deviation Signal Energy Peak Frequency Amplitude

Step 4: The data set with the highest change compared to baseline is identified and the stimulation amplitude corresponding to this data set is defined as the "Quantitatively identified rigidity release threshold"

Max

Data Processing

Feature Extraction

Clinical Application

• Clinical study carried out in University Hospital Clermont-Ferrand, France.

• Data was recorded from 9 PD patients who underwent DBS surgery • A total of 190 test stimulations were performed and data analysed following steps 1 to 4.

Results

• Three statistical features were identified to well describe rigidity release (Standard Deviation, Signal Energy and Spectral Amplitude of the Peak Frequency) • Out of the 190 test stimulations, rigidity release thresholds were found using the clinical method for 144 evaluations, while using quantitative method, 160 thresholds were found. For 138 test stimulations, thresholds were found using both the methods. • The rigidity release thresholds found using accelerometer evaluation are significantly lower than those found clinically (Fig 5).

Discussion

• The additional acceleration measurements during the surgery did not increase operation time or the patient's discomfort. • Sufficient baseline data is necessary for proper identification of acceleration thresholds. • There is an inherent subjective component in the acceleration analysis because the evaluation is done by the neurologist. • Further analysis in relation to anatomy could result in better target structures and could raise additional knowledge of the mechanisms of action of DBS

Threshold Identification

Results of Clinical Application

  Synchronization of two data sets. Accelerometer data is recorded during all test stimulations in synchronization with the electrophysiology system.

•

  Fig 5: Box plot showing comparison between clinical threshold and quantitative threshold

Acknowledgements

This research has been supported by the Swiss National Science Foundation (SNSF) and the Germaine de Stael program.


Luu Duy Tung
email: duy-tung.luu@ensicaen.fr

Jalal Fadili
email: jalal.fadili@ensicaen.fr

Christophe Chesneau
email: christophe.chesneau@unicaen.fr

Agrégation à poids exponentiels : Algorithmes d'échantillonnage

Keywords: Diffusion de Langevin, regularisation Langevin diffusion, Moreau-Yosida smoothing, exponential weighted aggregation

Nous proposons dans cet article des algorithmes d'échantillonage de distributions dont la densité est ni lisse ni log-concave. Nos algorithmes sont basés sur la diffusion de Langevin de la densité lissée par la régularisation de Moreau-Yosida. Ces résultats sont ensuite appliqués pour établir des agrégats à poids exponentiels dans un contexte de grande dimension.

Introduction

Consider the following linear regression

y = Xθ 0 + ξ (1)
where y ∈ R n is the response vector, X ∈ R n×p is a deterministic design matrix, and ξ are errors. The objective is to estimate the vector θ 0 ∈ R p from the observations in y. Generally, the problem ( 1) is either under-determined or determined (i.e., p ≤ n), but X is ill-conditioned, and then (1) becomes ill-posed. However, θ 0 generally verifies some notions of low-complexity. Namely, it has either a simple structure or a small intrinsic dimension. One can impose the notion of low-complexity on the estimators by considering a prior promoting it.

Exponential weighted aggregation (EWA) EWA consists to calculate the following expectation

θ EWA n = R p θ µ(θ)dθ, µ(θ) ∝ exp (-V (θ)/β), (2)
where β > 0 is called temperature parameter and

V (θ) def = F (Xθ, y) + W λ • D (θ),
where F : R n × R n → R is a general loss function assumed to be differentiable, W λ : R q → R ∪ {+∞} is a regularizing penalty depending on a parameter λ > 0, and D ∈ R p×q a analysis operator. W λ promotes some specific notion of low-complexity.

Langevin diffusion The computation of θ

EWA n corresponds to an integration problem which becomes very involved to solve analytically, or even numerically in highdimension. A classical approach is to approximate it using a Markov chain Monte-Carlo (MCMC) method which consists in sampling from µ by constructing a Markov chain via the Langevin diffusion process, and to compute sample path averages based on the output of the Markov chain. A Langevin diffusion L in R p , p ≥ 1 is a homogeneous Markov process defined by the stochastic differential equation (SDE)

dL(t) = 1 2 ρ(L(t))dt + dW (t), t > 0, L(0) = l 0 , (3)
where ρ = ∇ log µ, µ is everywhere non-zero and suitably smooth target density function on R p , W is a pdimensional Brownian process and l 0 ∈ R p is the initial value. Under mild assumptions, the SDE (3) has a unique strong solution and, L(t) has a stationary distribution with density µ. This opens the door to approximating integrals R p f (θ)µ(θ)dθ, where f : R p → R, by the average value of a Langevin diffusion, i.e., 1 T T 0 f (L(t))dt for a large enough T . In practice, we cannot follow exactly the dynamic defined by the SDE (3). Instead, we must discretize it by the forward (Euler) scheme, which reads

L k+1 = L k + δ 2 ρ(L k ) + √ δZ k , t > 0, L 0 = l 0 ,
where δ > 0 is a sufficiently small constant discretization step-size and {Z k } k are iid ∼ N (0, I p ). The average value L k where T /δ denotes the interger part of T /δ. For a complete review about sampling by Langevin diffusion from smooth and log-concave densities, we refer the studies in [START_REF] Dalalyan | Theoretical guarantees for approximate sampling from a smooth and log-concave density[END_REF]. To cope with non-smooth densities, several works have proposed to replace log µ with a smoothed version (typically involving the Moreau-Yosida regularization) [START_REF] Dalalyan | Sparse regression learning by aggregation and langevin monte-carlo[END_REF][START_REF] Pereyra | Proximal markov chain monte carlo algorithms[END_REF][START_REF] Durmus | Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm[END_REF][START_REF] Durmus | Sampling from convex non continuously differentiable functions, when Moreau meets Langevin[END_REF].

Algorithm and guarantees

Our main contribution is to englarge the family of µ covered in [START_REF] Dalalyan | Sparse regression learning by aggregation and langevin monte-carlo[END_REF][START_REF] Pereyra | Proximal markov chain monte carlo algorithms[END_REF][START_REF] Durmus | Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm[END_REF][START_REF] Durmus | Sampling from convex non continuously differentiable functions, when Moreau meets Langevin[END_REF] by relaxing the underlying conditions. Namely, in our framework, µ is structured as µ with W λ is not necessarily differentiable nor convex. Let F β = F (X•, y)/β and W β,λ = W λ /β. To apply the Langevin Monte-Carlo approach, we regularize W β,λ by a Moreau envelope defined as

γ W β,λ (u) def = inf w∈R q w -u 2 2 2γ + W β,λ (w), γ > 0.
Define also the corresponding proximal mapping as

prox γW β,λ (u) def = Argmin w∈R q w -u 2 2 2γ + W β,λ (w), γ > 0.
To establish the algorithm, let us state some assumptions.

(H.1) W β,λ is proper, lsc and bounded from below.

(H.2) prox γW β,λ is single valued.

(H.3) prox γW β,λ is locally Lipschitz continuous. (H.4) ∃K 1 > 0, ∀θ ∈ R p , D θ, prox γW β,λ (D θ) ≤ K(1 + θ 2 2 ). (H.5) ∃K 2 > 0, ∀θ ∈ R p , θ, ∇F β (θ) ≤ K 2 (1 + θ 2 2 ).
A large family of W β,λ satisfies (H.1)-(H.3). Indeed, one can show that the functions called prox-regular (and a fortiori convex) functions verify these assumptions. The following proposition ensures differentiability of W β,λ and expresses the gradient

∇ γ W β,λ through prox γW β,λ . Proposition 2.1. Assume that (H.1)-(H.2) hold. Then γ W β,λ ∈ C 1 (R q ) with ∇ γ W β,λ = 1 γ I q -prox γW β,λ .
Consider the Langevin diffusion L ∈ R p defined by the following SDE

dL(t) = - 1 2 ∇ F β + ( γ W β,λ ) • D (L(t))dt+dW (t), (4
) when t > 0 and L(0) = l 0 . Here W is a p-dimensional Brownian process and l 0 ∈ R p is the initial value. Proposition 2.2. Assume that (H.1)-(H.5) hold. For every initial point L(0) such that E L(0) 2 2 < ∞, SDE (4) has a unique solution which is strongly Markovian, nonexplosive and admits an unique invariant measure

µ γ ∝ exp -F β (θ) + ( γ W β,λ ) • D (θ) .
The following proposition answers the natural question on the behaviour of µ γ -µ as a function of γ. Proposition 2.3. Assume that (H.1) hold. Then µ γ converges to µ in total variation as γ → 0.

Inserting the identities of Lemma 2.1 into (4), we get dL(t) = A(L(t))dt + dW (t), L(0) = l 0 , t > 0. [START_REF] Pereyra | Proximal markov chain monte carlo algorithms[END_REF] where A = -1 2 ∇F β + γ -1 D I q -prox γW β,λ • D . Consider now the forward Euler discretization of (5) with step-size δ > 0, which can be rearranged as

L k+1 = L k + δA(L k ) + √ δZ k , t > 0, L 0 = l 0 . (6)
From ( 6), an Euler approximate solution is defined as

L δ (t) def = L 0 + t 0 A(L(s))ds + t 0 dW (s)ds,
where

L(t) = L k for t ∈ [kδ, (k + 1)δ[. Observe that L δ (kδ) = L(kδ) = L k , hence L δ (t) and L(t)
are continuous-time extensions to the discrete-time chain {L k } k . Mean square convergence of the pathwise approximation (6) and of its first-order moment is described below. Our algorithm has been applied in several numerical problems. Figure 1 shows an application in Inpainting using EWA with SCAD and 1,2 penalties.

  t)dt can then be naturally approximated via the Riemann sum δ/T T /δ -1 k=0

Theorem 2 . 1 .

 21 Assume that (H.1)-(H.5) hold, andE L(0) p 2 < ∞ for any p ≥ 2. Then E L δ (T ) -E [L(T )] 2 ≤ E sup 0≤t≤T L δ (t) -L(t) 2 -→ δ→0 0.

FIGURE 1 -

 1 FIGURE 1 -(a) : Masked image (b) : Inpainting with EWA -1,2 . (c) Inpainting with EWA -SCAD.