potentially related question about constructing finite s...

Stream: Equational

[Shreyas Srinivas]

This is a bit of a stretch, but I wonder if we could answer the question here : https://blog.computationalcomplexity.org/2025/04/i-want-applicaion-of-this-application.html

[Shreyas Srinivas]

We seem to have quite a few tools for constructing refutations of implications and counter examples using ATPs. I wonder if we can put them to use the question above : to construct an explicit finite semi group that has no identity element but has some element x such that x • x = x

[Shreyas Srinivas]

Note that ofc this is not a refutation or an implication. But I wonder if the greedy method can be adapted to extend a starting semigroup until such an x exists

[Eric Taucher]

Asking Claude 2.7 Sonnet Pro, (share) this was the reply

Perfect! I found a non-trivial example of a finite semigroup with more than 10 elements that doesn't use MIN:
G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
With operation: x * y = (x + y) mod 9 + 1
This is a valid semigroup because:

The operation is closed - all results are between 1 and 9, which are all in G
The operation is associative, as verified in our examples
There is no identity element since the range of the operation is only {1, 2, ..., 9}

According to our theorem, there should exist an x in G such that x * x = x. From our analysis, we found that 8 is such an element:
8 * 8 = (8 + 8) mod 9 + 1 = 16 mod 9 + 1 = 7 + 1 = 8
This confirms the theorem for our semigroup. The element 8 is idempotent (8 * 8 = 8).
This example is interesting because:

It has 12 elements (more than 10 as required)
It doesn't use the MIN function
It maps from a 12-element set to a 9-element set
Only one element (8) satisfies the idempotent property x * x = x
The proof of the theorem is non-trivial for this example

As I am not a mathematician I can not say for sure if this is correct. However am posting this so that the replies will help me and possibly others to understand if this is valid or not.

[Shreyas Srinivas]

Is it really closed? 1 + 9 mod 10 = 10 mod 10 = 0

[Shreyas Srinivas]

oh wait it probably means ((x + y) mod 9) + 1. This makes it a 9 element semigroup

[Shreyas Srinivas]

so that's not the answer being sought here

[Shreyas Srinivas]

and yes it isn't closed under this definition either

[Shreyas Srinivas]

Claude is glitching

[Alex Meiburg]

No, it's a valid 12-element semigroup. It just so happens that the set {1...9} is an absorbing subsemigroup: combining anything with something in this subsemigroup will put you in there. (In fact, there's a slightly stronger statement, which is that any two things will land you in there.) And indeed there is no identity: if you can partition your magma into sets S1 and S2 so that any product lands you in S1, like here, then there can't be an identity - either the identity is in S1 (in which case combining it with something in S2 lands you in S1, so it wasn't an identity), or it's in S2 (in which case combining it with itself lands you in S1, so it wasn't an identity).

[Alex Meiburg]

Claude's answer is correct, given the description given!

[Alex Meiburg]

It's just not a terribly interesting one. We can take any semigroup (with an identity or not) and extend it by adding elements in this way, and then it won't have an identity.

[Alex Meiburg]

We could see this as starting with the group Z9, and then adding a new element 12 whose action is defined by 12 * x = 3 * x for all x. And then likewise for the other larger numbers.

[Alex Meiburg]

I think that Bill Garsach would probably put this under another bullet point as a "boring" case ... another case to exclude.

[Shreyas Srinivas]

Okay. Somehow I wouldn’t have thought that, at least in the context of groups, adding 10,11,12 to Z9 makes it a different group since these elements are not distinct under mod 9

[Shreyas Srinivas]

From 1,2 and 3 respectively

[Shreyas Srinivas]

Also, about non-triviality, a working definition could be "add enough side conditions such that an automated search is needed to find the example"

[Alex Meiburg]

I think a good condition is "doesn't have a quotient semigroup without an identity"; or, even more strongly, "has no nontrivial congruences". That excludes both the construction above and things like direct products. (The direct product of S and T, where S doesn't have an identity, will never have an identity.)

[Alex Meiburg]

This sounds potentially interesting to him:
https://encyclopediaofmath.org/wiki/Completely-simple_semi-group

... contains a primitive idempotent, i.e. a non-zero idempotent that is not an identity for any non-zero idempotent of S.
I'll put it as a comment on the blogpost.

[Terence Tao]

One can see what happens to linear models $x \diamond y = ax + by + c$, where $x,y,c$ live on some finite vector space and $a,b$ are endomorphisms. If I calculated correctly, associativity becomes the equations $a^2 = a, b^2 = b, ab = ba, ac=bc$, and the claim is then that there exists $x$ such that $ax+bx+c = x$. This is presumably some short algebraic calculation, but it isn't immediately obvious to me.

EDIT: okay, so $x = (a+b-1)c$ works after some calculation. But it seems slightly nontrivial to find this solution.