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$?

1$\begingroup$ @user47958: do you check some lattices $L_n$ (of divisors of $n$)? $\endgroup$– Sebastien PalcouxCommented Sep 24, 2014 at 13:14

1$\begingroup$ @SébastienPalcoux: The lattice of divisors of $n$ is a direct product of linear lattices. For linear lattices, the identity is vacuously true (as long as the semigroup is commutative, which it always has to be), so one can just take e.g. a cyclic group structure on each factor. $\endgroup$– Emil JeřábekCommented Sep 24, 2014 at 13:19

1$\begingroup$ Assuming your $\mathbb N$ doesn’t contain $0$ (otherwise multiplication is not cancellative), $(\mathbb N,)$ is a direct sum of countably many linear lattices, and as such it has a group structure by the same argument: e.g., let $p_1^{a_1}\dots p_k^{a_k}*p_1^{b_1}\dots p_k^{b_k}=p_1^{f^{1}(f(a_1)+f(a_2))}\dots p_k^{f^{1}(f(a_k)+f(b_k))}$, where $f(a)=a/2$ for $a$ even, and $f(a)=(1+a)/2$ for $a$ odd. Now, what is not clear to me is whether there is any cancellative semigroup structure on $(\mathbb N,)$ when $\mathbb N$ includes $0$. $\endgroup$– Emil JeřábekCommented Sep 24, 2014 at 14:00

1$\begingroup$ Oh, there is: make $0$ a unit, and put $n*m=2nm$ for $n,m\ne0$. $\endgroup$– Emil JeřábekCommented Sep 24, 2014 at 14:29

2$\begingroup$ That’s an immediate consequence of the fact that every distributive lattice can be embedded in a Boolean algebra. (A Boolean algebra is also an abelian group, in fact, a commutative ring.) $\endgroup$– Emil JeřábekCommented Sep 24, 2014 at 18:34
1 Answer
Exhaustive search confirms that the 18element lattice of downsets 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 joinirreducible elements of $L$ under the induced order. $L$ is isomorphic to the lattice $D(I)$ of downsets 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 wellfounded induction on $i\in I$. Let $\mu'$ be as in $(*{*}*)$. Then $\mu'$ is a measure on $L$ that coincides with $\mu$ on joinirreducible elements. It follows by induction that $\mu(x)=\mu'(x)$ for all $x\in L$: if $x\ne0$ is not joinirreducible, 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 bruteforce 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$).
#include <stdio.h>
#include <assert.h>
#define N 18
#define A(x,y) ((x + y) % N)
// #define A(x,y) ((x + y  3 * (((x % 3) + (y % 3)) >= 3)) % N)
#define TEST(s,x) { unsigned tmp = 1 << (x); if (tmp & s) { cnt++; continue; } s = tmp; }
int main (void)
{
unsigned a, cnt = 0;
for (a = 1; a < N; a++) {
unsigned b, sa = 1;
TEST(sa, a);
for (b = 1; b < N; b++) {
unsigned c, sb = sa, ab = A(a, b);
TEST(sb, b);
TEST(sb, ab);
for (c = 1; c < N; c++) {
unsigned u, sc = sb, ac = A(a, c), bc = A(b, c), abc = A(ab, c);
TEST(sc, c);
TEST(sc, ac);
TEST(sc, bc);
TEST(sc, abc);
for (u = 1; u < N; u++) {
unsigned v, su = sc, abu = A(ab, u), abcu = A(abc, u);
TEST(su, abu);
TEST(su, abcu);
for (v = 1; v < N; v++) {
unsigned w, sv = su, acv = A(ac, v), abcv = A(abc, v), abcuv = A(abcu, v);
TEST(sv, acv);
TEST(sv, abcv);
TEST(sv, abcuv);
for (w = 1; w < N; w++) {
unsigned sw = sv, bcw = A(bc, w), abcw = A(abc, w), abcuw = A(abcu, w), abcvw = A(abcv, w), abcuvw = A(abcuv, w);
TEST(sw, bcw);
TEST(sw, abcw);
TEST(sw, abcuw);
TEST(sw, abcvw);
TEST(sw, abcuvw);
assert (sw == (1 << N)  1);
printf ("%u,%u,%u;%u,%u,%u\n", a, b, c, u, v, w);
return 1;
}
}
}
}
}
}
printf ("no (%u)\n", cnt);
return 0;
}

$\begingroup$ Do you mean that a computer program can check that it is really a counterexample? $\endgroup$ Commented Sep 26, 2014 at 22:57

$\begingroup$ 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. $\endgroup$ Commented Sep 26, 2014 at 23:07

$\begingroup$ Which program did you use (gap, wolfram, etc)? Do I need to write a proram from scratch (eg with C++)? $\endgroup$ Commented Sep 26, 2014 at 23:39

1
