Conjecture about commutative semigroups

Question

Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$ (note that $X$ and $Y$ need not be disjoint, and they can even be equal).

Proving it should be difficult, because it would imply the union-closed sets conjecture: if $S$ is a union-closed family without any element in at least half of the sets, then $a \setminus b \subseteq y_1 \cap \cdots \cap y_m \cap a = \emptyset$ and $b \setminus a \subseteq x_1 \cap \cdots \cap x_m \cap b = \emptyset$ and then $a = b$, a contradiction.

Is it easier to find a counterexample?

EDIT

I didn't mention my previous question, sorry. There, if I didn't make errors, I think I proved, but with a calculator, experimentally with an ILP, that any commutative magma (and therefore any commutative semigroup) of order $n=4$ satisfy the conjecture. Regarding the counterexamples found there for $n \ge 5$ I don't think they are semigroups.

Answer 1

This is not an answer, but it's too long for a comment: I'm going to show that the OP's conjecture is true in some (admittedly, rather special) cases. It is hoped that this will help to find a counterexample, if any exists.

---

Given a (multiplicatively written) semigroup $S$ and elements $a, b \in S$, denote by $R_S(a,b)$ the set of all pairs $(x,y) \in S \times S$ such that $x,y \notin \{a, b\}$ and $ax = by$, and let $r_S(a,b)$ be the largest integer $m \ge 0$ for which there exist $(x_1, y_1), \ldots, (x_m, y_m) \in R_S(a,b)$ with $x_i \ne x_j$ and $y_i \ne y_j$ for all $i,j \in [\![1,m]\!]$ with $i \ne j$. Next, define the invariant $$ r(S) := \sup \{r_S(a,b): a, b \in S \text{ and } a \ne b\}, $$ where $\sup \emptyset := 0$. The OP's conjecture can then be reformulated as follows:

Conjecture. If $S$ is a commutative, finite semigroup of order $n \ge 2$ other than the cyclic monoid/group of order $3$, then $r(S) \ge \lfloor (n-1)/2 \rfloor$.

This is not exactly the original conjecture, as it is not restricted to semigroups of order $n \ge 4$. However, the conjecture (in its new formulation) is clearly true for $n = 2$, as in this case $r(S) = \lfloor (n-1)/2 \rfloor = 0$. On the other hand, it is just tedious to check (see my other non-answer here) that the only order-$3$ exception to the conjecture is the cyclic group of order $3$ (which indeed is an exception, as pointed out by Fabius Wiesner in the comments). Lastly, let me say a few words about commutativity.

Remark. If $S$ is a left zero semigroup (meaning that $xy = x$ for all $x, y \in S$), then it is fairly obvious that $r(S) = 0$. That is, the conjecture fails for left zero semigroups of order $\ge 3$. This demonstrates that the conjecture does not carry over to the non-commutative setting, which counters a certain halo of arbitrariness in its current formulation and supports the restriction to the commutative setting.

Here is a summary of what's coming next (all relevant definitions will be given in due course):

• Proposition 1 is about monoids (of order $\ge 3$) whose group of units is non-trivial.
• Proposition 2 is about non-unital cyclic semigroups.
• Proposition 3 is about nilsemigroups.

To start with, recall that an element $a$ in a semigroup $S$ is cancellative if left and right multiplication by $a$ are both injective functions on $S$. Let me first show that we can get rid of semigroups that have more than one cancellative element.

Lemma. If a semigroup $S$ has a cancellative element $a$ of finite order, then $S$ is a monoid and $a$ is one of its units. Conversely, every monoid has a cancellative element of finite order (that is, the identity.)

Proof. This is a standard exercise. Since $a$ has finite order in $S$, there exist $m, n \in \mathbb N^+$ with $m < n$ such that $a^m = a^n$. Set $e := a^{n-m}$. By cancellativity), $a = a^{n-m+1} = ae = ea$. It follows that, for every $x \in S$, $ax = aex$ and $xa = xea$, which, again by cancellativity, yields $x = ex = xe$. So, $S$ is a monoid and $e$ is its identity element. Accordingly, $e = a^{n-m}$ implies that $a$ is a unit (its inverse in $S$ being $a^{n-m-1}$, which is equal to $e$ when $n = m+1$). []

Based on the lemma, we can focus our attention on three classes of semigroups: those with no cancellative elements, the monoids whose only unit is the identity, and the monoids with non-trivial units. Our first proposition shows that the OP's conjecture is true for the last class.

Proposition 1. Let $S$ be a finite monoid of order $n \ge 3$ but not a cyclic group of order $3$, and suppose, in addition, that $S$ has at least one non-trivial unit. Then $r(S) \ge n-\varepsilon$, where $\varepsilon$ is either $2$ or $3$, depending on whether $S$ has a unit of order $2$ or not, respectively. In particular, $S$ satisfies the OP's conjecture.

Proof. By hypothesis, $S$ is a finite monoid whose group of units is non-trivial. So, let $a$ be a unit of $S$, other than the identity $1_S$, that has minimal order in $S$. Let $a^{-1}$ be the inverse of $a$. Given $y \in S$, we have $a^{-1} y = 1_S$ iff $y = a$, and $a^{-1} y = a$ iff $y = a^2$. Since $(a^{-1}y, y) \in R_S(a, 1_S)$ for all $y \in S$ and left multiplication by $a^{-1}$ is an injective function on $S$, this yields $r(S) \ge r_S(a, 1_S) \ge n-\varepsilon$: in fact, if $a$ has order $2$ (that is, $a^2 = 1_S$), then $r_S(a,1_S) = n-2$; otherwise, $r_S(a, 1_S) \ge n-3$.

Now, if $n = 3$, then the order of $a$ in $S$ is necessarily equal to $2$ (or else $S$ is a cyclic group of order $3$), and hence $r(S) = 3-2 = \lfloor (3-1)/2 \rfloor = 1$. Otherwise, $r(S) \ge n-3 \ge \lfloor (n-1)/2 \rfloor$. In any case, $S$ satisfies the OP's conjecture. []

In the next proposition, we will consider the case when the semigroup $S$ is cyclic, meaning that there exists an element $g \in S$ such that, for every $x \in S$, one has $x = g^k$ for some $k \in \mathbb N^+$.

Proposition 2. If $S$ is a finite, cyclic semigroup of order $n \ge 3$ but not a monoid, then $r(S) = n-2$ and hence $S$ satisfies the OP's conjecture.

Proof. As $S$ is a cyclic semigroup but not a monoid, we gather from the structure theorem of finite cyclic semigroups (see, for instance, Proposition 1.1 in the 2016 edition of Benjamin Steinberg's Representation Theory of Finite Monoids) that there exist an element $g \in S$ and a minimal positive integer $m \le n$ such that $g^m = g^{n+1}$ and the following condition holds:

$\text{(C)}$: $g^i = g^j$, for some $i, j \in [\![1, n]\!]$, if and only if (i) $i = j$ or (ii) $i, j \ge m$ and $i \equiv j \bmod d$, where $d := n-m+1$.

Set $a := g^\mu$ and $b := g^n$, where $\mu := \max(1,m-1)$. Since $n \ge 3$, it is clear from $\text{(C)}$ that $a \ne b$. In addition, for each $i \in [\![1,n]\!]$, we have $bg^i = g^{n+i} = g^{m+i-1} = ag^i$. It follows that $(x,x) \in R_S(a,b)$ for all $x \in S$, and hence $$ r(S) \ge r_S(a,b) \ge n-2 \ge \lfloor (n-1)/2 \rfloor. $$ We are thus done, as it is obvious that $r(S) \le n-2$. []

For the last proposition of this post, recall that a semigroup $S$ is nilpotent, or a nilsemigroup, if there is a (provably unique) element $0_S \in S$, called the zero of $S$, such that every $x \in S$ has a power $x^k$ (with $k \in \mathbb N^+$) equal to $0_S$.

Proposition 3. If $S$ is a finite nilsemigroup of order $n \ge 3$, then $r(S) = n-2$ and hence $S$ satisfies the OP's conjecture.

Proof. Let $0_S$ be the zero element of $S$. Since $S$ is finite, it satisfies the descending chain condition on principal right ideals (that is, on subsets of the form $\{a\} \cup aS$); and since $S$ has more than one element, this implies that there exists a maximal left divisor $a$ of $0_S$ in $S \setminus \{0_S\}$, where 'maximal' means that every left divisor of $0_S$ that is left divided by $a$ is either $0_S$ or $a$. It follows that $aS = \{0_S\}$; otherwise, $a = ax$ for some $x \in S$, and hence $0_S \ne a = ax^k$ for all $k \in \mathbb N^+$, which is however impossible because $S$ is nilpotent. Consequently, $(x,x) \in R_S(a,0_S)$ for every $x \in S$ and hence $$ r(S) \ge r_S(a,0_S) \ge n-2 \ge \lfloor (n-1)/2 \rfloor. $$ That is enough to conclude (cf. the last line of the proof of Proposition 2). []

Answer 2

As a complement to my previous non-answer, let me show that the OP's conjecture holds for any order-$3$ commutative semigroup $S$ that is not a group (equivalently, that is not a cyclic group of order $3$).

Up to the canonical anti-isomorphism between a semigroup and its opposite, there are $17$ semigroups of order $3$ (excluding the cyclic group of order $3$), of which only $11$ are commutative; see the Wikipedia article on order-$3$ semigroups here. Below, I'll list these $11$ commutative semigroups one by one and prove that they all satisfy the OP's conjecture. It may be a tedious task, but is going to help with another reduction.

All semigroups will be defined on the set $\{x, y, z\}$ through their Cayley tables. Since $\lfloor (3-1)/2 \rfloor = 1$, we need to find, for each semigroup on the list, a permutation $(a,b,c)$ of the triple $(x,y,z)$ such that $ac = bc$.

---

1. $S$ is the cyclic semigroup (with $y = x^2$, $z = x^3$, and $x^2 = x^4$) defined by the following table:

	x	y	z
x	y	z	y
y	z	y	z
z	y	z	y

It satisfies the OP's conjecture by Proposition 2 here.

2. $S$ is the cyclic semigroup (with $y = x^2$, $z = x^3$, and $x^3 = x^4$) defined by the following table:

	x	y	z
x	y	z	z
y	z	z	z
z	z	z	z

It satisfies the OP's conjecture by Proposition 2 here.

3. $S$ is the monoid (with identity element $z$) defined by the following table:

	x	y	z
x	z	y	x
y	y	y	y
z	x	y	z

It is isomorphic to the (unital) submonoid $\{0, \pm 1\}$ of the integers under multiplication. In particular, it has a non-trivial unit (namely, $x$); hence, it satisfies the OP's conjecture by Proposition 1 here.

4. $S$ is the monoid (with identity element $y$) defined by the following table:

	x	y	z
x	z	x	x
y	x	y	z
z	x	z	z

Its group of units is trivial, so we can't apply any of Propositions 1 to 3 here. However, $yx = zx = x$.

5. $S$ is the nilsemigroup (with zero element $z$) defined by the following table:

	x	y	z
x	z	x	x
y	x	z	z
z	x	z	z

It satisfies the OP's conjecture by Proposition 3 here.

6. $S$ is the null semigroup (with zero element $z$) defined by the following table (a null semigroup is a semigroup with zero in which any product of any two elements is zero):

	x	y	z
x	z	z	z
y	z	z	z
z	z	z	z

Every null semigroup is a nilsemigroup, so $S$ satisfies the OP's conjecture by Proposition 3 here.

7. $S$ is the non-unital semigroup defined by the following table:

	x	y	z
x	z	z	z
y	z	y	z
z	z	z	z

It is neither a cyclic semigroup nor a nilsemigroup ($y$ and $z$ are both idempotents), so we can't apply any of Propositions 1 to 3 here. However, $yx = zx = x$.

8. $S$ is the non-unital semigroup defined by the following table:

	x	y	z
x	z	y	z
y	y	y	y
z	z	y	z

It is neither a cyclic semigroup nor a nilsemigroup ($y$ and $z$ are both idempotents), so we can't apply any of Propositions 1 to 3 here. However, $xy = zy = y$.

9. $S$ is the non-unital semigroup defined by the following table:

	x	y	z
x	z	x	z
y	x	y	z
z	z	z	z

It is neither a cyclic semigroup nor a nilsemigroup ($y$ and $z$ are both idempotents), so we can't apply any of Propositions 1 to 3 here. However, $xz = yz = z$.

10. $S$ is the unital semilattice (with identity/bottom element $x$) defined by the following table (a semilattice is a commutative semigroup in which every element is idempotent):

	x	y	z
x	x	y	z
y	y	y	z
z	z	z	z

It is neither a cyclic semigroup nor a nilsemigroup, so we can't apply any of Propositions 1 to 3 here. However, $xz = yz = z$.

11. $S$ is the non-unital semilattice defined by the following table:

	x	y	z
x	x	z	z
y	z	y	z
z	z	z	z

It is neither a cyclic semigroup nor a nilsemigroup, so we can't apply any of Propositions 1 to 3 here. However, $xz = yz = z$. []

I hope I haven't made too many typos.

Answer 3

Here is a generalization of some of @SalvoTringali's ideas. My basic feeling is that probably this conjecture boils down to the case of meet semilattices and hence isn't so far from the original union-closed sets conjecture. I'm hoping this approach will allow for induction.

I'll give two slight improvements on @SalvoTringali's answer. If $s\in S$, let $H_s=\{t\in S\mid sS^1= tS^1\}$ (the $\mathcal H$-class of $s$) and $I_s=sS^1\setminus H_s$. Here $S^1$ means $S$ with an adjoined identity. Then standard finite semigroup theory tells you $I_s$ is an ideal, and that either $H_s$ is a group or $H_sH_s\subseteq I_s$. The element $s$ is (von Neumannn) regular if $H_s$ is a group and otherwise is called null.

I will use $s^{\omega}$ to denote the idempotent positive power of $s$ and $s^{\omega+1}$ for $s^{\omega}s$.

The first claim shows that if $sS^1$ is a maximal principal ideal with $H_s$ a nontrivial group, then the conjecture is true. This generalizes Salvo's Proposition 1.

This claim has a gap. I’ll leave it in case I can fix it. Claim 2 seems ok.

Claim 1. Suppose that $|S|\geq 4$ and $S$ has a maximal principal ideal $sS^1$ with $H_s$ a nontrivial group and $s$ not idempotent.

Proof. Let $e$ be the the identity of $H_s$ and let $s'$ be the inverse of $s$ in $H_s$. Then for any $z\in S$ we have that $ez = s'(sz)$. Assume now that $z\neq e,s,s^2$. Since $sS^1$ was maximal, we cannot have $s'z\in\{e,s\}$ unless $z\in H_s$, in which case $z=s,s^2$, which we excluded. There are $n-3$ choices of $z$, more than enough to meet the desired bound. []

The next claim generalizes Salvo's Propositions 2 and 3. It is trickier.

Claim 2. Suppose that there is a maximal principal ideal $sS^1$ with $H_s$ not a group. Then there are $a\neq b\in S$ such that $az=bz$ for all $z\in S\setminus \{a,b\}$.

Proof. Our assumption implies we can find a minimal principal ideal $tS^1$ subject to the property that if $tS^1\subseteq uS^1$, then $H_u$ is not a group. Indeed, our assumption gives us at least one principal ideal with this property and hence there is a minimal such by finiteness. Then since $H_tH_t\subseteq I_t$, we must have that $t^k\notin H_t$ for all $k>1$.

We claim that $I_t$ is a monoid with identity $t^{\omega}$. For if $uS^1$ is a maximal principal ideal of $S$ contained in $I_t$, then by choice of $t$, we must have that $H_u$ is a group. Write $u=tx$ with $x\in S^1$. Choose $k>1$ such that $u^k=u^{\omega}$ and $t^k=t^{\omega}$. Then $u=u^ku = t^kx^ku=t^{\omega}t^kx^ku=t^{\omega}u$. Now if $v\in I_s$ is any element, then $v\in uS^1$ for some maximal principal left ideal of $S$ contained in $I_s$, and so if $v=uy$, then $t^{\omega}v=t^{\omega}uy=uy=v$ by the previous case.

I claim that $tz=t^{\omega+1}z$ for all $z\in S\setminus \{t,t^{\omega+1}\}$. First we observe that if $z\in S$, then $tz\in I_t$. Indeed, if $tz\in H_t$, then $tzS^1=tS^1$ and so $tzy=t$ for some $y\in S^1$. Then $t(zy)^{\omega}=t$ and $tS^1\subseteq (zy)^{\omega}S^1$. But $(zy)^{\omega}$ is regular, so this contradicts the choice of $t$. Thus $tz\in I_t$, and so by the above claim $tz = t^\omega(tz) = t^{\omega+1}z$. []

So we are left with the case that each maximal $\mathcal H$-class is an idempotent. Now one should try to do some sort of induction to get to the case each element is an idempotent.