2014-09-24 11:11:09 8 Comments

Let $(S,\le)$ be a distributive lattice. Is there a semigroup structure on $S$ such that $S$ is cancellative and always $(x\wedge y)(x\vee y)=xy$?

### Related Questions

#### Sponsored Content

#### 0 Answered Questions

### Relative strength and propositional indistinguishability of non-distributive lattices

**2019-05-08 22:05:08****Daniil Kozhemiachenko****104**View**1**Score**0**Answer- Tags: lo.logic lattice-theory

#### 0 Answered Questions

### Distributive generators of a lattice

**2019-04-15 14:08:29****Tom Q****60**View**2**Score**0**Answer- Tags: co.combinatorics lattice-theory

#### 2 Answered Questions

### [SOLVED] Order-embedding, but no lattice embedding between distributive lattices

**2018-03-15 07:33:14****Dominic van der Zypen****107**View**4**Score**2**Answer- Tags: order-theory posets lattice-theory

#### 0 Answered Questions

### Distributive lattices -> left regular bands -> Atomistic lower semimodular lattices

**2017-03-02 19:47:47****Olivier Bégassat****82**View**3**Score**0**Answer- Tags: reference-request lattice-theory semigroups-and-monoids

#### 2 Answered Questions

### [SOLVED] Finite-join antichains in lattices

**2016-10-23 03:04:36****Iian Smythe****160**View**3**Score**2**Answer- Tags: lo.logic set-theory lattice-theory

#### 1 Answered Questions

### [SOLVED] Is the top interval of a finite distributive lattice, a boolean lattice?

**2015-07-26 08:35:30****Sebastien Palcoux****231**View**3**Score**1**Answer- Tags: co.combinatorics posets lattice-theory

#### 1 Answered Questions

### [SOLVED] Is this a sufficient condition for distributivity of a lattice?

**2015-12-01 09:17:06****drhab****114**View**2**Score**1**Answer- Tags: lattice-theory

#### 0 Answered Questions

### Certain conditions on cancellative semigroups

**2015-02-02 23:59:53****Michał Masny****264**View**3**Score**0**Answer- Tags: ra.rings-and-algebras semigroups-and-monoids

#### 1 Answered Questions

### [SOLVED] Cancellable elements of a power semigroup

**2015-01-05 03:06:21****Michał Masny****312**View**4**Score**1**Answer- Tags: ra.rings-and-algebras semigroups-and-monoids

#### 1 Answered Questions

### [SOLVED] Lattice-ordered commutative monoids

**2010-11-13 18:09:13****François G. Dorais****876**View**7**Score**1**Answer- Tags: ac.commutative-algebra lattices semigroups-and-monoids universal-algebra

## 1 comments

## @Emil Jeřábek 2014-09-26 22:50:58

Exhaustive search confirms that the 18-element lattice of down-sets of the poset $P=(\{a,b,c,u,v,w\},\{(a,u),(a,v),(b,u),(b,w),(c,v),(c,w)\})$ is a counterexample.

EDIT: I used an ad hoc C program for the check. The code is posted below, but let me first explain how it works.

Let $L$ be a finite distributive lattice. Since the condition in the OP forces the semigroup to be commutative, and finite cancellative semigroups are groups, the condition is equivalent to the existence of an abelian group $A$, and a bijective mapping $\mu\colon L\to A$ satisfying $$\tag{$*$}\mu(x)+\mu(y)=\mu(x\land y)+\mu(x\lor y),\qquad x,y\in L.$$ By subtracting $\mu(0)$ if necessary, we may assume without loss of generality $$\tag{${*}{*}$}\mu(0)=0.$$ I will call a mapping $\mu$ satisfying $(*)$ and $(**)$ an $A$-valued measure on $L$. Now, how do such measures look like?

Let $(I,\le)$ be the Birkhoff dual of $L$, i.e., the poset of join-irreducible elements of $L$ under the induced order. $L$ is isomorphic to the lattice $D(I)$ of down-sets of $I$, wherefrom it is easy to see that for any sequence $\{a_i:i\in I\}$ of elements of $A$, $$\tag{${*}{*}{*}$}\mu(x)=\sum_{i\le x}a_i$$ defines a measure on $L$. On the other hand, let $\mu$ be a measure, and define $$a_i=\mu(i)-\sum_{\substack{j\in I\\j<i}}a_j$$ by well-founded induction on $i\in I$. Let $\mu'$ be as in $(*{*}*)$. Then $\mu'$ is a measure on $L$ that coincides with $\mu$ on join-irreducible elements. It follows by induction that $\mu(x)=\mu'(x)$ for all $x\in L$: if $x\ne0$ is not join-irreducible, we can write it as $x=y\lor z$ with $y,z<x$, hence $$\mu(x)=\mu(y)+\mu(z)-\mu(y\land z)=\mu'(y)+\mu'(z)-\mu'(y\land z)=\mu'(x)$$ by the induction hypothesis. Thus, measures on $L$ are exactly the mappings of the form $(*{*}*)$.

In the particular case of $P$, the lattice $D(P)$ has 18 elements, and the only abelian groups of that size are $C_{18}$ and $C_6\times C_3$. The code below does a brute-force search for a sequence $\{a_i:i\in P\}$ such that the corresponding measure $\mu\colon D(P)\to A$ as in $(*{*}*)$ is injective; the choice of $A$ is controlled by uncommenting the appropriate definition of the

`A(x,y)`

macro (the first line implements addition in $C_{18}$, the second one in $C_6\times C_3$).## @user47958 2014-09-26 22:57:35

Do you mean that a computer program can check that it is really a counterexample?

## @Emil Jeřábek 2014-09-26 23:07:06

Yes, exactly. I first tried to do it by hand with various tricks, but it got way too messy, and it turns out that a dumb computer search works like a charm.

## @user47958 2014-09-26 23:39:48

Which program did you use (gap, wolfram, etc)? Do I need to write a proram from scratch (eg with C++)?

## @Victor 2014-09-27 05:22:47

@EmilJeřábek: respect!

## @user47958 2014-09-27 14:11:35

cpp.sh/4l2