Comparing Numbers of Diagonal Subsemigroups and Congruences for Semigroups

1. Problem Statement

The paper addresses the structural relationship between congruences and diagonal subsemigroups within finite semigroups.

• Definitions:
  • A congruence on a semigroup $S$ is an equivalence relation compatible with multiplication.
  • A diagonal subsemigroup is a reflexive relation on $S$ that is compatible with multiplication (i.e., a subsemigroup of the direct square $S \times S$ containing the diagonal $\Delta_S = \{(s,s) : s \in S\}$).
  • Every congruence is a diagonal subsemigroup, but the converse is not always true.
• The DSC Coefficient: The authors define the DSC coefficient $\chi(S)$ for a finite semigroup $S$ as the ratio of the number of congruences to the number of diagonal subsemigroups:
  $$\chi(S) = \frac{|\text{Cong}(S)|}{|\text{Diag}(S)|}$$
  Since the set of congruences is a subset of diagonal subsemigroups, $\chi(S) \in \mathbb{Q} \cap (0, 1]$.
• The Core Question: Previous work established that $\chi(S) = 1$ if and only if $S$ is a group. The authors investigate the spectrum of possible values for $\chi(S)$ across all finite semigroups. Specifically, they aim to prove that for any rational number $\alpha \in (0, 1]$, there exists a finite semigroup $S$ such that $\chi(S) = \alpha$.

2. Methodology

The authors utilize the Rees Matrix Construction to generate semigroups with controllable DSC coefficients.

A. Theoretical Framework: Rees Matrix Semigroups

They focus on Rees matrix semigroups $S = M[G; I, \Lambda; P]$, where:

• $G$ is a group.
• $I$ and $\Lambda$ are index sets.
• $P$ is a $\Lambda \times I$ matrix with entries in $G$.
• Multiplication is defined as $(i, g, \lambda)(j, h, \mu) = (i, gp_{\lambda j}h, \mu)$.

B. Characterization of Structures

The paper establishes a bijection between algebraic structures on $S$ and triples derived from $G, I,$ and $\Lambda$:

1. Congruences: Based on Preston's theorem, congruences on $S$ correspond to linked equivalence triples $(N, S, T)$, where $N$ is a normal subgroup of $G$, and $S, T$ are equivalence relations on $I$ and $\Lambda$ respectively, satisfying specific "linked" conditions involving matrix extracts.
2. Diagonal Subsemigroups: The authors prove a new characterization (Theorem 2.7) showing that if $G$ is a DSC group (a group where every diagonal subsemigroup is a congruence; all finite groups are DSC), then diagonal subsemigroups on $S$ correspond to linked reflexive triples.
   • The key difference is that $S$ and $T$ need only be reflexive relations (not necessarily equivalence relations).

C. Counting Strategy

The DSC coefficient is expressed as a ratio of counts of these triples:
$$\chi(S) = \frac{\sum_{k} |E_{I,k}| |E_{\Lambda,k}|}{\sum_{k} |R_{I,k}| |R_{\Lambda,k}|}$$
Where:

• $k$ indexes the normal subgroups of $G$.
• $E$ denotes the set of linked equivalence relations.
• $R$ denotes the set of linked reflexive relations.
• The authors analyze how the structure of the matrix $P$ and the group $G$ forces the "linked" conditions to either be trivial (allowing all relations) or restrictive (forcing relations to be diagonal).

3. Key Contributions and Results

A. Characterization of Diagonal Subsemigroups (Section 2)

The authors provide the first complete classification of diagonal subsemigroups on Rees matrix semigroups. They prove that these structures are in one-to-one correspondence with linked reflexive triples, provided the underlying group is DSC. This extends the known classification of congruences (linked equivalence triples) to the broader class of diagonal subsemigroups.

B. Bounds on the DSC Coefficient (Theorem 3.4)

For a Rees matrix semigroup $M[G; I, \Lambda; P]$ with $|I|=a$ and $|\Lambda|=b$ ($a,b > 1$):

• Lower Bound: The coefficient is bounded below by the DSC coefficient of the rectangular band $I \times \Lambda$:
  $$\frac{B(a)B(b)}{2^{a^2-a} 2^{b^2-b}} \leq \chi(S)$$
  where $B(n)$ is the $n$-th Bell number (counting equivalence relations) and $2^{n^2-n}$ counts reflexive relations.
• Upper Bound: $\chi(S) < 1$ (since $S$ is not a group).
• Surjectivity: The authors prove that for any rational $\alpha$ in the interval $[\text{Lower Bound}, 1)$, there exists a specific group $G$ and matrix $P$ such that $\chi(S) = \alpha$.

C. Main Theorem: Spectrum of Values (Theorem 1.2)

The paper proves the main result: The set of DSC coefficients for finite semigroups is exactly $\mathbb{Q} \cap (0, 1]$.

• Proof Strategy: By choosing a cyclic group $G = \mathbb{Z}_{p^k}$ and carefully constructing the matrix $P$ using powers of 2, the authors manipulate the number of normal subgroups that satisfy the "linked" condition.
• They show that by varying the parameters, the ratio of congruences to diagonal subsemigroups can be tuned to any rational number between the theoretical lower bound (determined by the size of index sets) and 1.
• Since the lower bound approaches 0 as the index sets grow, any rational $\alpha \in (0, 1)$ can be achieved.

D. Comparison with Clifford Semigroups (Section 4)

The authors briefly analyze Clifford semigroups (semilattices of groups).

• They establish that $\chi(S) \leq \chi(Y)$, where $Y$ is the underlying semilattice.
• Unlike Rees matrix semigroups, where the lower bound converges to 0 as index sets grow, the upper bound for Clifford semigroups (determined by the semilattice) appears to converge to 0 as the semilattice grows. This suggests that Clifford semigroups may not be sufficient to generate the full spectrum of rational values, highlighting the unique utility of Rees matrix constructions for this problem.

4. Significance

• Completeness of the Spectrum: The paper resolves the question of what values the DSC coefficient can take, proving that the set of values is dense and complete within the rationals $(0, 1]$.
• Structural Insight: It deepens the understanding of the relationship between congruences and diagonal subsemigroups, showing that the "gap" between them can be precisely controlled via the Rees matrix construction.
• Methodological Innovation: The introduction of "linked reflexive triples" as a tool to count diagonal subsemigroups provides a new algebraic framework that could be applied to other classes of semigroups.
• Counter-Intuitive Results: The result contrasts with the behavior of Clifford semigroups, where the coefficient is bounded above by the semilattice structure, suggesting that the "complexity" of the index sets in Rees matrix semigroups is the driving factor for generating diverse DSC coefficients.

In summary, Barber and Ruškuc demonstrate that the ratio of congruences to diagonal subsemigroups is a highly flexible invariant in finite semigroup theory, capable of taking any rational value between 0 and 1 through the strategic construction of Rees matrix semigroups.