Introduction
A variety is a class of algebras closed under taking subalgebras, homomorphic images, and arbitrary direct products. By Birkhoff’s theorem, varieties are precisely the classes defined by sets of identities [1 ] . Such a set is called an equational basis . A variety is finitely based if it admits a finite equational basis, and nonfinitely based otherwise. An algebra has the corresponding property when the variety it generates does. The finite basis problem asks which algebras and varieties admit finite equational bases. A variety is hereditarily finitely based if all its subvarieties are finitely based; it is a limit variety if it is nonfinitely based but all its proper subvarieties are finitely based. Thus limit varieties mark the boundary between finite and nonfinite basability in subvariety lattices.
An additively idempotent semiring , or ai-semiring , is an algebra ( S , + , ⋅ ) (S,+,\cdot) ( S , + , ⋅ ) in which ( S , + ) (S,+) ( S , + ) is a commutative idempotent semigroup, ( S , ⋅ ) (S,\cdot) ( S , ⋅ ) is a semigroup, and the distributive identities
x ( y + z ) ≈ x y + x z , ( x + y ) z ≈ x z + y z x(y+z) \approx xy+xz,\qquad(x+y)z \approx xz+yz x ( y + z ) ≈ x y + x z , ( x + y ) z ≈ x z + y z
hold. Its addition induces the natural order: for a , b ∈ S a,b \in S a , b ∈ S , the relation a ≤ b a \le b a ≤ b holds if and only if a + b = b a+b=b a + b = b . This is a partial order compatible with multiplication, and a + b a+b a + b is the join of a a a and b b b . In particular, ai-semirings may be viewed as semilattice-ordered semigroups. Throughout this paper we work in the binary signature ( + , ⋅ ) (+,\cdot) ( + , ⋅ ) , without named constants. The notation p ⪯ u \mathbf p \preceq\mathbf u p ⪯ u for an absorption identity between terms will be introduced separately in Section 2; it is distinct from the order ≤ \le ≤ on elements of a semiring.
The general theory of semirings and its applications is surveyed in [9 , 3 ] . Early work on finite ai-semirings includes the nonfinitely based example of Dolinka [2 ] , the varieties of order-two ai-semirings classified by Shao–Ren [21 ] , and the commutative Burnside-type varieties considered by Ren–Zhao [18 ] . Systematic classifications of four-element ai-semirings appear in [17 , 29 , 16 ] . Further finite- and nonfinite-basis phenomena in specific inverse and Brandt semirings are exhibited in [24 , 23 ] .
2020 Mathematics Subject Classification . Primary 16Y60; Secondary 08B15, 08B05, 05C60.
Key words and phrases. Additively idempotent semiring, mirror word, zero extension, infinite axiomatic rank, subvariety interval, limit variety.
The finite basis problem for ai-semirings has also been studied in particular for flat semirings and for semirings obtained by adjoining a zero. Jackson–Ren–Zhao [11 ] developed flat-semiring methods for nonfinite basability, and Wu–Ren–Zhao [26 ] proved that S 7 0 S_7^0 S 7 0 is nonfinitely based. Gao–Jackson–Ren–Zhao [5 ] further analyzed ai-semirings related to S 7 S_7 S 7 . Gao–Ren–Zhao [7 ] subsequently obtained general finite- and nonfinite-basis results for flat word semirings S ( W ) S(W) S ( W ) , while their work on zero adjunction [6 ] established continuum-sized intervals between varieties generated by S S S and S 0 S^0 S 0 . Related examples in which adjoining a zero changes the finite basis behavior occur in [28 ] . For the flat semirings themselves , rather than their zero extensions, Wang–Wang [25 ] established finite identity bases for arbitrary sets of linear words. Gao–Zhou [8 ] obtained further finite bases and continuum-sized subvariety intervals using interval semirings of posets. These linear-word results do not, by themselves, settle the corresponding problems for zero extensions of words with repeated letters.
The study of limit varieties provides another perspective on the finite basis problem. Ren–Jackson–Zhao–Lei [15 ] constructed limit varieties from flat extensions of finite groups. Lyu–Ren–Yue [13 ] proved that the six-element semiring S R 6 SR_6 S R 6 generates a limit variety, and Shao–Ren–Gao [22 ] established the corresponding property for a different six-element semiring T R 6 TR_6 T R 6 . These examples motivate the search for limit subvarieties inside varieties generated by zero extensions of flat word semirings.
We consider the mirror words
m n = a 1 ⋯ a n a n ⋯ a 1 ( n ≥ 1 ) , m_n = a_1\cdots a_n a_n\cdots a_1 \qquad(n \ge1), m n = a 1 ⋯ a n a n ⋯ a 1 ( n ≥ 1 ) ,
where a 1 , a 2 , … a_1, a_2, \ldots a 1 , a 2 , … are distinct letters. Let A n = S ( m n ) A_n = S(m_n) A n = S ( m n ) be the flat semiring of their nonempty contiguous factors, with absorbing top element ∞ \infty ∞ , and let A ^ n = A n 0 \widehat{A}_n = A_n^0 A n = A n 0 be obtained by adjoining a new additive identity and multiplicative zero 0 ≠ ∞ 0 \ne\infty 0 = ∞ . We write
V n = V ( A n ) , W n = V ( A ^ n ) , W ∞ = ⋁ n ≥ 2 W n . \mathcal{V}_n = \mathcal{V}(A_n), \qquad\mathcal{W}_n = \mathcal{V}(\widehat{A}_n), \qquad\mathcal{W}_\infty= \bigvee_{n \ge2} \mathcal{W}_n. V n = V ( A n ) , W n = V ( A n ) , W ∞ = n ≥ 2 ⋁ W n .
Since the mirror words contain repeated letters, the associated zero extensions have features not covered by the linear-word constructions.
Shao–Gao [19 Theorem 1.1] determined the finite basis property of S ( W ) 0 S(W)^0 S ( W ) 0 for every nonempty set of nonempty words W W W . In particular, their theorem implies that A ^ n \widehat{A}_n A n is finitely based precisely when n = 1 n = 1 n = 1 . Their Corollary 4.8 also yields infinite axiomatic rank for each W n \mathcal{W}_n W n with n ≥ 2 n \ge2 n ≥ 2 . More substantially, Shao–Gao [19 Theorems 1.3 and 14.2] proved that every variety between a common limit subvariety V ( B 15 ) \mathcal{V}(B_{15}) V ( B 15 ) and the join of their linear-word zero-extension varieties has infinite axiomatic rank. Thus interval-wide infinite axiomatic rank is already known for zero extensions of flat word semirings. A related uniform construction for power semirings of finite groups appears in [20 ] . Our result concerns a different interval. Indeed, x 2 y ≈ x y 2 x^2y \approx xy^2 x 2 y ≈ x y 2 holds in every linear-word zero extension but fails in A ^ 2 \widehat{A}_2 A 2 (take x = b x=b x = b , y = a y=a y = a in S ( a b b a ) 0 S(abba)^0 S ( abba ) 0 ), so W 2 \mathcal{W}_2 W 2 is not contained in their linear-word upper variety. We prove that every variety in [ W 2 , W ∞ ] [\mathcal{W}_2,\mathcal{W}_\infty] [ W 2 , W ∞ ] has infinite axiomatic rank, using finite local quotients and a six-element classification of evaluation kernels rather than the linear-word argument of Shao–Gao.
We also investigate intervals of subvarieties. For every n ≥ 1 n \ge1 n ≥ 1 , we construct an order embedding of the power-set order into [ W n , W n + 1 ] [\mathcal{W}_n,\mathcal{W}_{n+1}] [ W n , W n + 1 ] using finite context quotients and graph-separating identities. For n ≥ 2 n \ge2 n ≥ 2 , we apply the cyclic semirings and identities of Shao–Gao [19 Sections 10–11] , after checking the necessary endpoint conditions, to obtain a continuum-sized interval [ V n , W n ] [\mathcal{V}_n,\mathcal{W}_n] [ V n , W n ] . These methods also imply that the chain W 1 ⊊ W 2 ⊊ ⋯ \mathcal{W}_1 \subsetneq\mathcal{W}_2 \subsetneq\cdots W 1 ⊊ W 2 ⊊ ⋯ is strict and that W ∞ \mathcal{W}_\infty W ∞ is locally finite.
Finally, we study limit subvarieties. We show that V ( S R 6 ) \mathcal{V}(SR_6) V ( S R 6 ) is the unique limit subvariety of W 1 \mathcal{W}_1 W 1 . For n ≥ 2 n \ge2 n ≥ 2 , we construct from an infinite directed path a new limit variety U = V ( T ∞ ) \mathcal{U} = \mathcal{V}(T_\infty) U = V ( T ∞ ) such that U ⊆ W n \mathcal{U} \subseteq\mathcal{W}_n U ⊆ W n but U ⊈ V n \mathcal{U} \nsubseteq\mathcal{V}_n U ⊈ V n . Moreover,
U ∩ V ( B 15 ) = V ( S ( a b c ) ) , \mathcal{U} \cap\mathcal{V}(B_{15}) = \mathcal{V}(S(abc)), U ∩ V ( B 15 ) = V ( S ( ab c )) ,
and U \mathcal{U} U is incomparable with both limit varieties constructed by Shao–Gao [19 Theorems 1.2 and 22.1] . Together with the known acyclic-graph limit variety, these results yield at least five pairwise incomparable limit subvarieties of W n \mathcal{W}_n W n for each n ≥ 2 n \ge2 n ≥ 2 .
Theorem 1.1 (Shao–Gao). For every integer n ≥ 1 n \ge1 n ≥ 1 , the semiring A ^ n \widehat{A}_n A n is finitely based if and only if n = 1 n = 1 n = 1 .
Theorem 1.2. The inclusions W 1 ⊊ W 2 ⊊ ⋯ \mathcal{W}_1 \subsetneq\mathcal{W}_2 \subsetneq\cdots W 1 ⊊ W 2 ⊊ ⋯ are strict. Each interval [ W n , W n + 1 ] [\mathcal{W}_n,\mathcal{W}_{n+1}] [ W n , W n + 1 ] , n ≥ 1 n \ge1 n ≥ 1 , contains an order-embedded copy of ( P ( N ) , ⊆ ) (\mathcal{P}(\mathbb{N}),\subseteq) ( P ( N ) , ⊆ ) and has cardinality 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 . The same cardinality and power-set embedding hold for [ V n , W n ] [\mathcal{V}_n,\mathcal{W}_n] [ V n , W n ] when n ≥ 2 n \ge2 n ≥ 2 , by applying the cyclic construction of Shao–Gao; also ∣ [ V n , W ∞ ] ∣ = 2 ℵ 0 |[\mathcal{V}_n,\mathcal{W}_\infty]| = 2^{\aleph_0} ∣ [ V n , W ∞ ] ∣ = 2 ℵ 0 . Every K \mathcal{K} K with W 2 ⊆ K ⊆ W ∞ \mathcal{W}_2 \subseteq\mathcal{K} \subseteq\mathcal{W}_\infty W 2 ⊆ K ⊆ W ∞ has infinite axiomatic rank. The variety V ( S R 6 ) \mathcal{V}(SR_6) V ( S R 6 ) is the unique limit subvariety of W 1 \mathcal{W}_1 W 1 . For every n ≥ 2 n \ge2 n ≥ 2 , a new limit variety U = V ( T ∞ ) \mathcal{U} = \mathcal{V}(T_\infty) U = V ( T ∞ ) lies in W n \mathcal{W}_n W n but not in V n \mathcal{V}_n V n ; it is incomparable with the two limit varieties of Shao–Gao. In particular, W n \mathcal{W}_n W n contains at least five pairwise incomparable limit subvarieties.
Section 2 gives the notation and basic properties. Section 3 treats the uniform axiomatic-rank obstruction, and Section 4 establishes the continuum intervals and local finiteness. Sections 5 and 6 prove the limit-subvariety results.
Preliminaries and mirror-word zero extensions
For a nonempty word w w w , let Fac + ( w ) \operatorname{Fac}^{+}(w) Fac + ( w ) be the set of its nonempty contiguous factors. As in the standard construction [11 Lemma 2.5] , the flat word semiring S ( w ) S(w) S ( w ) has underlying set Fac + ( w ) ∪ { ∞ } \operatorname{Fac}^{+}(w) \cup\{\infty\} Fac + ( w ) ∪ { ∞ } and operations
u + v = { u , u = v , ∞ , u ≠ v , u ⋅ v = { u v , u v ∈ Fac + ( w ) , ∞ , otherwise . u+v =
\begin{cases}
u, & u=v,\\
\infty, & u\ne v,
\end{cases}
\qquad
u\mathbin{\cdot}v =
\begin{cases}
uv, & uv\in\operatorname{Fac}^{+}(w),\\
\infty, & \text{otherwise}.
\end{cases} u + v = { u , ∞ , u = v , u = v , u ⋅ v = { uv , ∞ , uv ∈ Fac + ( w ) , otherwise .
Here ∞ \infty ∞ absorbs both operations. The factors are words in the free semigroup, so no commutativity is imposed; in particular, S ( w ) S(w) S ( w ) is distinguished from the commutative word semiring S c ( w ) S_c(w) S c ( w ) . For an ai-semiring S S S , its zero extension S 0 S^0 S 0 is obtained by adjoining a new element 0 0 0 such that
0 + s = s + 0 = s , 0 s = s 0 = 0 ( s ∈ S 0 ) . 0+s=s+0=s,\qquad0s=s0=0\qquad(s\in S^0). 0 + s = s + 0 = s , 0 s = s 0 = 0 ( s ∈ S 0 ) .
The new element 0 0 0 is distinct from every element of S S S , including any multiplicative zero already in S S S .
Lemma 2.1. For every n ≥ 1 n \ge1 n ≥ 1 , the mirror-word zero extension satisfies ∣ A n ^ ∣ = 2 n 2 + 2 |\widehat{A_n}| = 2n^2 + 2 ∣ A n ∣ = 2 n 2 + 2 . Moreover, every x ∈ A n x \in A_n x ∈ A n satisfies x 3 = ∞ x^3 = \infty x 3 = ∞ , whereas 0 3 = 0 0^3 = 0 0 3 = 0 in A n ^ \widehat{A_n} A n . The two-element distributive lattice semiring D 2 = ( { 0 , 1 } , ∨ , ∧ ) D_2 = (\{0,1\}, \vee, \wedge) D 2 = ({ 0 , 1 } , ∨ , ∧ ) is a homomorphic image of A n ^ \widehat{A_n} A n .
Proof. The adjacent factors of length two in m n \mathbf{m}_n m n are pairwise distinct. Consequently, every factor of length at least two occurs exactly once, while the factors of length one are the n n n distinct letters. Thus the number of nonempty factors is ( 2 n 2 ) + n = 2 n 2 \binom{2n}{2} + n = 2n^2 ( 2 2 n ) + n = 2 n 2 . Adjoining ∞ \infty ∞ and 0 0 0 gives the asserted cardinality. Since each letter occurs exactly twice in m n \mathbf{m}_n m n , the cube of any nonempty factor cannot be a factor; the same identity x 3 = ∞ x^3 = \infty x 3 = ∞ holds when x = ∞ x = \infty x = ∞ . Finally, sending the adjoined 0 0 0 to 0 0 0 and every element of A n A_n A n to 1 1 1 gives a surjective semiring homomorphism onto D 2 D_2 D 2 . The same homomorphism exists for the zero extension of any nonempty ai-semiring. □
Let X X X be a countably infinite set of variables and X + X^+ X + the free semigroup on X X X . By distributivity and additive idempotence, an ai-semiring term may be identified with a finite nonempty set of words in X + X^+ X + ; see [12 Theorem 2.5] . We use bold letters for formal words and terms, and ordinary italic letters for variables and elements of semirings. We write u = u 1 + ⋯ + u r \mathbf{u} = \mathbf{u}_1 + \cdots+ \mathbf{u}_r u = u 1 + ⋯ + u r for the term corresponding to { u 1 , … , u r } \{\mathbf{u}_1,\ldots,\mathbf{u}_r\} { u 1 , … , u r } , and regard its word summands as members of u \mathbf{u} u . For a word p \mathbf{p} p , let c ( p ) c(\mathbf{p}) c ( p ) denote its content and ℓ ( p ) \ell(\mathbf{p}) ℓ ( p ) its length . For a term u \mathbf{u} u , put c ( u ) = ⋃ p ∈ u c ( p ) c(\mathbf{u}) = \bigcup_{\mathbf{p}\in\mathbf{u}} c(\mathbf{p}) c ( u ) = ⋃ p ∈ u c ( p ) . For elements a , b a,b a , b of an ai-semiring, the natural order is defined by a ≤ b a \le b a ≤ b if and only if a + b = b a+b=b a + b = b . Following the identity notation of [22 Section 2] , for ai-semiring terms p , u \mathbf{p},\mathbf{u} p , u write p ≼ u \mathbf{p} \preccurlyeq\mathbf{u} p ≼ u (or, equivalently, u ≽ p \mathbf{u} \succcurlyeq\mathbf{p} u ≽ p ) for the absorption identity u ≈ u + p \mathbf{u} \approx\mathbf{u}+\mathbf{p} u ≈ u + p . In particular, S ⊨ p ≼ u S \models\mathbf{p} \preccurlyeq\mathbf{u} S ⊨ p ≼ u means that φ ( p ) ≤ φ ( u ) \varphi(\mathbf{p}) \le\varphi(\mathbf{u}) φ ( p ) ≤ φ ( u ) in the natural order of S S S for every evaluation φ \varphi φ . Thus ≼ \preccurlyeq ≼ denotes an identity between formal terms, whereas ≤ \le ≤ compares elements of a semiring. Every identity between finite sums of words is equivalent to its word-absorption identities; it therefore suffices to consider q ≼ u \mathbf{q} \preccurlyeq\mathbf{u} q ≼ u with q ∈ X + \mathbf{q} \in X^+ q ∈ X + .
For a word q ∈ X + \mathbf{q} \in X^+ q ∈ X + and a term u \mathbf{u} u , following Gao–Ren–Zhao [6 Proposition 2.1] and Shao–Gao [19 Eq. (2)] , put
D q ( u ) = { p ∈ u : c ( p ) ⊆ c ( q ) } . D_{\mathbf{q}}(\mathbf{u}) = \{\mathbf{p} \in\mathbf{u} : c(\mathbf{p}) \subseteq c(\mathbf{q})\}. D q ( u ) = { p ∈ u : c ( p ) ⊆ c ( q )} .
The set D q ( u ) D_{\mathbf{q}}(\mathbf{u}) D q ( u ) may be empty. In expressions involving q ≼ D q ( u ) \mathbf{q} \preccurlyeq D_{\mathbf{q}}(\mathbf{u}) q ≼ D q ( u ) , nonemptiness is explicitly required, since an empty sum is not a term in the present binary signature. The absorption criterion for zero adjunction gives a convenient test for arbitrary term identities by applying it to each word summand on both sides.
Lemma 2.2 (Identity criterion for zero extensions). Let S S S be an ai-semiring, and let u , v \mathbf{u},\mathbf{v} u , v be ai-semiring terms. Then S ⊨ u ≈ v S \models\mathbf{u} \approx\mathbf{v} S ⊨ u ≈ v if and only if
D p ( v ) ≠ ∅ and S ⊨ p ≼ D p ( v ) for every p ∈ u , D_{\mathbf{p}}(\mathbf{v}) \ne\varnothing\text{ and } S \models\mathbf{p} \preccurlyeq D_{\mathbf{p}}(\mathbf{v}) \quad\text{for every } \mathbf{p} \in\mathbf{u}, D p ( v ) = ∅ and S ⊨ p ≼ D p ( v ) for every p ∈ u , D q ( u ) ≠ ∅ and S ⊨ q ≼ D q ( u ) for every q ∈ v . D_{\mathbf{q}}(\mathbf{u}) \ne\varnothing\text{ and } S \models\mathbf{q} \preccurlyeq D_{\mathbf{q}}(\mathbf{u}) \quad\text{for every } \mathbf{q} \in\mathbf{v}. D q ( u ) = ∅ and S ⊨ q ≼ D q ( u ) for every q ∈ v . Proof. An identity u ≈ v \mathbf{u} \approx\mathbf{v} u ≈ v is equivalent to the absorptions p ≼ v \mathbf{p} \preccurlyeq\mathbf{v} p ≼ v for all p ∈ u \mathbf{p} \in\mathbf{u} p ∈ u and q ≼ u \mathbf{q} \preccurlyeq\mathbf{u} q ≼ u for all q ∈ v \mathbf{q} \in\mathbf{v} q ∈ v . Applying the zero-adjunction absorption criterion of Wu–Ren–Zhao [26 Proposition 1.5] (see also Gao–Ren–Zhao [6 Proposition 2.1] ) to each of these absorptions gives precisely the stated conditions. The criterion and its proof are recalled below. □
The following word-absorption criterion is an established result of Wu–Ren–Zhao [26, Proposition 1.5] and Gao–Ren–Zhao [6, Proposition 2.1]; see also Shao–Gao [19, Lemma 4.5] for flat word semirings. We include a short proof for completeness.
Proposition 2.3 (Zero-adjunction criterion). Let S S S be an ai-semiring, u \mathbf{u} u an ai-semiring term, and q ∈ X + \mathbf{q} \in X^{+} q ∈ X + a word. Then the zero extension S 0 S^{0} S 0 satisfies q ⪯ u \mathbf{q} \preceq\mathbf{u} q ⪯ u if and only if both D q ( u ) ≠ ∅ D_{\mathbf{q}}(\mathbf{u}) \ne\varnothing D q ( u ) = ∅ and S ⊨ q ⪯ D q ( u ) S \models\mathbf{q} \preceq D_{\mathbf{q}}(\mathbf{u}) S ⊨ q ⪯ D q ( u ) .
Proof. Suppose S 0 ⊨ q ⪯ u S^{0} \models\mathbf{q} \preceq\mathbf{u} S 0 ⊨ q ⪯ u . Assign the adjoined zero to every variable outside c ( q ) c(\mathbf{q}) c ( q ) and arbitrary elements of S S S to those in c ( q ) c(\mathbf{q}) c ( q ) . The word q \mathbf{q} q then has its value in S S S . Hence at least one word of u \mathbf{u} u must survive, so D q ( u ) ≠ ∅ D_{\mathbf{q}}(\mathbf{u}) \ne\varnothing D q ( u ) = ∅ ; the surviving words also give S ⊨ q ⪯ D q ( u ) S \models\mathbf{q} \preceq D_{\mathbf{q}}(\mathbf{u}) S ⊨ q ⪯ D q ( u ) .
Conversely, consider an arbitrary evaluation in S 0 S^{0} S 0 . If a variable occurring in q \mathbf{q} q is assigned 0 0 0 , then q \mathbf{q} q evaluates to 0 0 0 , which is the additive least element of S 0 S^{0} S 0 . Otherwise q \mathbf{q} q and every word of D q ( u ) D_{\mathbf{q}}(\mathbf{u}) D q ( u ) evaluate in S S S , and the assumed absorption identity gives φ ( q ) ≤ φ ( D q ( u ) ) ≤ φ ( u ) \varphi(\mathbf{q}) \leq\varphi(D_{\mathbf{q}}(\mathbf{u})) \leq\varphi(\mathbf{u}) φ ( q ) ≤ φ ( D q ( u )) ≤ φ ( u ) in the natural order of S 0 S^{0} S 0 . Thus S 0 ⊨ q ⪯ u S^{0} \models\mathbf{q} \preceq\mathbf{u} S 0 ⊨ q ⪯ u .
Infinite axiomatic rank in the mirror-word hierarchy
Shao–Gao [19, Theorem 1.1 and Corollary 4.8] already determine the finite-basis property and infinite axiomatic rank of each individual A ^ n \widehat{A}_{n} A n . We address the stronger question of infinite axiomatic rank for every intermediate variety in [ W 2 , W ∞ ] [\mathcal{W}_{2},\mathcal{W}_{\infty}] [ W 2 , W ∞ ] . The proof constructs finite countermodels from identities of A ^ 2 \widehat{A}_{2} A 2 and does not invoke the equational theory of the unextended word semirings.
Theorem 3.1. Every variety K \mathcal{K} K of ai-semirings satisfying W 2 ⊆ K ⊆ W ∞ \mathcal{W}_{2} \subseteq\mathcal{K} \subseteq\mathcal{W}_{\infty} W 2 ⊆ K ⊆ W ∞ has infinite axiomatic rank; that is, no identity basis of K \mathcal{K} K has a uniform finite bound on the number of variables. In particular, it is nonfinitely based.
Finite local quotients
Fix a nonempty finite variable set X X X . Define an equivalence on X + X^{+} X + by keeping every word of length at most four in a singleton class and identifying two words of length at least five exactly when they have the same content. This is a semigroup congruence: multiplication preserves the length threshold, and the content of a product is the union of the contents of its factors. Denote the resulting finite quotient semigroup by X ‾ + \overline{X}^{+} X + . Identifying short words with their singleton classes, we obtain
X ‾ + = { w ∈ X + : 1 ≤ ℓ ( w ) ≤ 4 } ∪ { λ C : ∅ ≠ C ⊆ X } . \overline{X}^{+}=\{w\in X^{+}:1\leq\ell(w)\leq4\}\cup\{\lambda_{C}:\varnothing\ne C\subseteq X\}. X + = { w ∈ X + : 1 ≤ ℓ ( w ) ≤ 4 } ∪ { λ C : ∅ = C ⊆ X } .
Here λ C \lambda_{C} λ C is the class of words of length at least five with content C C C . If ∣ X ∣ = r |X|=r ∣ X ∣ = r , then
∣ X ‾ + ∣ = r + r 2 + r 3 + r 4 + 2 r − 1. |\overline{X}^{+}|=r+r^{2}+r^{3}+r^{4}+2^{r}-1. ∣ X + ∣ = r + r 2 + r 3 + r 4 + 2 r − 1.
Consider its power semiring
P X : = ( P ( X ‾ + ) , ∪ , ⋅ ) , U V = { u v : u ∈ U , v ∈ V } . P_{X}:=\bigl(\mathcal{P}(\overline{X}^{+}),\cup,\cdot\bigr),\qquad UV=\{uv:u\in U,\ v\in V\}. P X := ( P ( X + ) , ∪ , ⋅ ) , U V = { uv : u ∈ U , v ∈ V } .
The empty subset is the additive identity and the multiplicative zero. We identify each singleton subset with its unique member.
Lemma 3.2 (Evaluation extension). Every assignment α : X → A ^ 2 \alpha:X\to\widehat{A}_{2} α : X → A 2 extends uniquely to a semiring homomorphism α ^ : P X → A ^ 2 \widehat{\alpha}:P_{X}\to\widehat{A}_{2} α : P X → A 2 with α ^ ( ∅ ) = 0 \widehat{\alpha}(\varnothing)=0 α ( ∅ ) = 0 . In particular, α ^ ( λ C ) = 0 \widehat{\alpha}(\lambda_{C})=0 α ( λ C ) = 0 if some variable of C C C has value 0 0 0 , and it equals 1 1 1 otherwise.
Proof. For a word of length at least five, an evaluation gives the new zero 0 0 0 whenever one of its variables takes that value. Under an all-old evaluation the word instead evaluates to ∞ \infty ∞ , since five nonempty old factors cannot concatenate to a factor of a b b a abba abba . Its value therefore depends only on its variable content, which makes evaluation well defined on X ‾ + \overline{X}^{+} X + .
Extend evaluation to a subset of X ‾ + \overline{X}^{+} X + by summing the values of its members, with the empty subset assigned 0 0 0 . Union is preserved by construction, and distributivity gives preservation of setwise multiplication. The resulting homomorphism extends α \alpha α and is unique, since the singleton classes and the empty subset generate P X \mathcal{P}_{X} P X . □
Let Id ≤ k ( A ^ 2 ) \operatorname{Id}_{\leq k}(\widehat{A}_{2}) Id ≤ k ( A 2 ) be the set of identities of A ^ 2 \widehat{A}_{2} A 2 involving at most k k k variables. Denote by Θ k , X \Theta_{k,X} Θ k , X the semiring congruence on P X \mathcal{P}_{X} P X generated by all substitution instances of these identities, allowing arbitrary substitutions into P X \mathcal{P}_{X} P X . Put
D k , X = P X / Θ k , X . D_{k,X}=\mathcal{P}_{X}/\Theta_{k,X}. D k , X = P X / Θ k , X .
Proposition 3.3 (Finite local model). The semiring D k , X D_{k,X} D k , X is finite and satisfies every identity of A ^ 2 \widehat{A}_{2} A 2 involving at most k k k variables. Moreover, if U Θ k , X V U\mathrel{\Theta_{k,X}}V U Θ k , X V , then U U U and V V V have the same value under every assignment X → A ^ 2 X\to\widehat{A}_{2} X → A 2 .
Proof. Every substitution instance of an identity involving at most k k k variables belongs to the generating congruence. Thus the quotient satisfies each of these identities, as claimed.
To verify that the quotient relation preserves all evaluations, fix α : X → A ^ 2 \alpha:X\to\widehat{A}_{2} α : X → A 2 and let α ^ \widehat{\alpha} α be its extension from Lemma 3.2. Every generating pair of Θ k , X \Theta_{k,X} Θ k , X lies in ker α ^ \ker\widehat{\alpha} ker α , because substitution in P X \mathcal{P}_{X} P X followed by α ^ \widehat{\alpha} α is an ordinary evaluation in A ^ 2 \widehat{A}_{2} A 2 . Since the kernel is a congruence, it contains all of Θ k , X \Theta_{k,X} Θ k , X . Thus Θ k , X ⊆ ker α ^ \Theta_{k,X}\subseteq\ker\widehat{\alpha} Θ k , X ⊆ ker α , proving the second assertion. Finally, D k , X D_{k,X} D k , X is finite because P X \mathcal{P}_{X} P X is finite. □
Separating identities and their evaluations
We may freely rename the letters of m n m_n m n as t 1 , … , t n t_1,\ldots,t_n t 1 , … , t n when discussing its factors. Fix m ≥ 2 m\geq2 m ≥ 2 and introduce
Z m = { a , b 0 , … , b m , c 0 , … , c m − 1 } , ∣ Z m ∣ = 2 m + 2 , Z_m=\{a,b_0,\ldots,b_m,c_0,\ldots,c_{m-1}\},\qquad|Z_m|=2m+2, Z m = { a , b 0 , … , b m , c 0 , … , c m − 1 } , ∣ Z m ∣ = 2 m + 2 ,
Q m = a b 0 2 a + a b m a + ∑ i = 0 m − 1 ( a b i c i + a b i + 1 c i ) , Q_m=ab_0^2a+ab_ma+\sum_{i=0}^{m-1}(ab_ic_i+ab_{i+1}c_i), Q m = a b 0 2 a + a b m a + i = 0 ∑ m − 1 ( a b i c i + a b i + 1 c i ) ,
K m = ( ∏ z ∈ Z m z ) 5 . K_m=\left(\prod_{z\in Z_m}z\right)^5. K m = ( z ∈ Z m ∏ z ) 5 .
The order in the product is fixed but arbitrary. Its image in Z ‾ m + \overline{Z}_m^{+} Z m + is λ Z m \lambda_{Z_m} λ Z m .
Lemma 3.4 (Rigidity of the central square). Fix n ≥ 2 n\geq2 n ≥ 2 and, within this proof and the next, write m n = t 1 ⋯ t n t n ⋯ t 1 m_n=t_1\cdots t_nt_n\cdots t_1 m n = t 1 ⋯ t n t n ⋯ t 1 . If nonempty words s , t s,t s , t satisfy s t 2 s ∈ Fac + ( m n ) st^2s\in\operatorname{Fac}^{+}(m_n) s t 2 s ∈ Fac + ( m n ) , then
t = t n , s = t n − 1 , s t 2 s = t n − 1 t n t n t n − 1 . t=t_n,\qquad s=t_{n-1},\qquad st^2s=t_{n-1}t_nt_nt_{n-1}. t = t n , s = t n − 1 , s t 2 s = t n − 1 t n t n t n − 1 .
Proof. Number the positions of m n m_n m n by 1 , … , 2 n 1,\ldots,2n 1 , … , 2 n ; the two occurrences of t j t_j t j are at j j j and 2 n + 1 − j 2n+1-j 2 n + 1 − j . If the first copy of t t t begins with t j t_j t j , the second begins at the other occurrence, so
ℓ ( t ) = ( 2 n + 1 − j ) − j = 2 n + 1 − 2 j . (1) \ell(t)=(2n+1-j)-j=2n+1-2j. \tag*{(1)} ℓ ( t ) = ( 2 n + 1 − j ) − j = 2 n + 1 − 2 j . (1)
For j < n j<n j < n this length is at least 3. The second letter of the first copy is then t j + 1 t_{j+1} t j + 1 (at position j + 1 j+1 j + 1 ), whereas the corresponding position in the second copy is 2 n + 2 − j 2n+2-j 2 n + 2 − j , which does not carry t j + 1 t_{j+1} t j + 1 . Thus j = n j=n j = n and t = t n t=t_n t = t n .
The two copies of t \mathbf{t} t occupy positions n , n + 1 n,n+1 n , n + 1 . Writing h = ℓ ( s ) ≥ 1 h=\ell(\mathbf{s})\ge1 h = ℓ ( s ) ≥ 1 , the first letters of the two copies of s \mathbf{s} s occur at n − h n-h n − h and n + 2 n+2 n + 2 , respectively. Hence
t n − h = t n − 1 , h = 1 , s = t n − 1 , t_{n-h}=t_{n-1},\qquad h=1,\qquad\mathbf{s}=t_{n-1}, t n − h = t n − 1 , h = 1 , s = t n − 1 ,
and the asserted central factor follows.
Lemma 3.5 (Global validity). For every m ≥ 2 m\ge2 m ≥ 2 , the identity
δ m : Q m ≈ Q m + K m \delta_m:\qquad\mathbf{Q}_m\approx\mathbf{Q}_m+\mathbf{K}_m δ m : Q m ≈ Q m + K m holds throughout W ∞ \mathcal{W}_\infty W ∞ .
Proof. Fix n ≥ 2 n\ge2 n ≥ 2 and an evaluation in A ^ n \widehat{\mathbf{A}}_n A n . If any variable takes the new zero 0 0 0 , then K m = 0 \mathbf{K}_m=0 K m = 0 , and the absorption is automatic. Suppose all variables take old values. Every such value is either ∞ \infty ∞ or a nonempty factor of m n \mathbf{m}_n m n . Thus
K m = ∞ : \mathbf{K}_m=\infty: K m = ∞ : this holds if some factor is ∞ \infty ∞ , and otherwise because K m \mathbf{K}_m K m repeats every variable five times whereas each letter of m n \mathbf{m}_n m n occurs only twice.
Assume Q m ≠ ∞ \mathbf{Q}_m\ne\infty Q m = ∞ . Flat addition forces all its summands to be the same old non-top factor. Applying Lemma 3.4 to a b 0 2 a ab_0^2a a b 0 2 a , and then cancelling the external letters in a b m a ab_ma a b m a , gives
a = t n − 1 , b 0 = t n , b m = t n 2 . a=t_{n-1},\qquad b_0=t_n,\qquad b_m=t_n^2. a = t n − 1 , b 0 = t n , b m = t n 2 . For 0 ≤ i < m 0\le i<m 0 ≤ i < m the summands a b i c i ab_ic_i a b i c i and a b i + 1 c i ab_{i+1}c_i a b i + 1 c i also have the same non-top value. Left and right cancellation in the free semigroup gives
b i = b i + 1 ( 0 ≤ i < m ) . b_i=b_{i+1}\qquad(0\le i<m). b i = b i + 1 ( 0 ≤ i < m ) . Hence b m = b 0 = t n b_m=b_0=t_n b m = b 0 = t n , contrary to b m = t n 2 b_m=t_n^2 b m = t n 2 since t n t_n t n is a nonempty word. Therefore Q m = ∞ \mathbf{Q}_m=\infty Q m = ∞ under every all-old evaluation, and Q m + K m = Q m \mathbf{Q}_m+\mathbf{K}_m=\mathbf{Q}_m Q m + K m = Q m in both cases. Since n n n was arbitrary, δ m \delta_m δ m holds in W ∞ \mathcal{W}_\infty W ∞ .
Deletion assignments and absorption. Arrange the variables other than a a a in a path
P m : b 0 , c 0 , b 1 , c 1 , … , c m − 1 , b m . P_m:\quad b_0,c_0,b_1,c_1,\ldots,c_{m-1},b_m. P m : b 0 , c 0 , b 1 , c 1 , … , c m − 1 , b m .
For every path vertex x x x , define an assignment θ x : Z m → A ^ 2 \theta_x:\mathcal{Z}_m\to\widehat{\mathbf{A}}_2 θ x : Z m → A 2 by θ x ( a ) = a \theta_x(a)=a θ x ( a ) = a , θ x ( x ) = 0 \theta_x(x)=0 θ x ( x ) = 0 , and the following table:
Table 2.
Here y x yx y x and x y xy x y label only the relative positions of y y y and x x x along P m P_m P m , not necessarily adjacent letters in a word. Let
s m = c m − 1 b m a , t m = a b m c m − 1 , s_m=c_{m-1}b_ma,\qquad t_m=ab_mc_{m-1}, s m = c m − 1 b m a , t m = a b m c m − 1 ,
S m = { a b 0 2 a , a b m a , s m } ∪ { a b i c i , a b i + 1 c i : 0 ≤ i < m } . \mathcal{S}_m=\{ab_0^2a,ab_ma,s_m\}\cup\{ab_ic_i,ab_{i+1}c_i:0\le i<m\}. S m = { a b 0 2 a , a b m a , s m } ∪ { a b i c i , a b i + 1 c i : 0 ≤ i < m } .
For subsequent use, define the sum
R m = a b 0 2 a + a b m a + ∑ i = 0 m − 2 ( a b i c i + a b i + 1 c i ) + a b m − 1 c m − 1 . \mathbf{R}_m=ab_0^2a+ab_ma+\sum_{i=0}^{m-2}(ab_ic_i+ab_{i+1}c_i)+ab_{m-1}c_{m-1}. R m = a b 0 2 a + a b m a + i = 0 ∑ m − 2 ( a b i c i + a b i + 1 c i ) + a b m − 1 c m − 1 .
Thus Q m = R m + t m \mathbf{Q}_m=\mathbf{R}_m+t_m Q m = R m + t m ; the sum R m \mathbf{R}_m R m contains precisely those summands of Q m \mathbf{Q}_m Q m other than t m t_m t m .
Lemma 3.6 (Deletion assignment). For each x ∈ P m x\in P_m x ∈ P m and each v ∈ S m \mathbf{v}\in\mathcal{S}_m v ∈ S m ,
v θ x = { 0 x ∈ c ( v ) , a b b a x ∉ c ( v ) , and Q m θ x = a b b a . \mathbf{v}^{\theta_x}=
\begin{cases}
0 & x\in c(\mathbf{v}),\\
abba & x\notin c(\mathbf{v}),
\end{cases}
\qquad\text{and}\qquad
\mathbf{Q}_m^{\theta_x}=abba. v θ x = { 0 abba x ∈ c ( v ) , x ∈ / c ( v ) , and Q m θ x = abba . Proof. For each relational monomial a b i c j ab_i c_j a b i c j , the vertices b i , c j b_i,c_j b i , c j are adjacent in P m P_m P m . If neither vertex is x x x , they lie on the same side of x x x . In either case, substituting their prescribed images into a b i c j ab_i c_j a b i c j gives a b b a abba abba . When defined away from the deleted vertex, the left and right anchors evaluate respectively as a b 2 a = a b b a ab^2a=abba a b 2 a = abba and a ( b b ) a = a b b a a(bb)a=abba a ( bb ) a = abba . The additional word s m s_m s m also evaluates to a b b a abba abba whenever neither of its adjacent path vertices is deleted: they then lie to the right of x x x . Any word containing x x x evaluates to 0 0 0 . At least one of the two anchor monomials avoids x x x , so the sum Q m \mathbf{Q}_m Q m evaluates to a b b a abba abba .
Lemma 3.7 (A three-variable exchange identity). The following identity holds in A ^ 2 \widehat{A}_2 A 2 :
x y x + x y z ≈ x y x + z y x . xyx+xyz\approx xyx+zyx. x y x + x y z ≈ x y x + z y x . Consequently,
R m + t m ≈ R m + t m + s m ≈ R m + s m \mathbf{R}_m+t_m\approx\mathbf{R}_m+t_m+s_m\approx\mathbf{R}_m+s_m R m + t m ≈ R m + t m + s m ≈ R m + s m holds in A ^ 2 \widehat{A}_2 A 2 .
Proof. If any variable is assigned 0 0 0 , direct inspection shows that both sides agree. For all-old assignments, if x y x = ∞ xyx=\infty x y x = ∞ , both sides are ∞ \infty ∞ . Otherwise, the only non-top value of a product x y x xyx x y x in S ( a b b a ) S(abba) S ( abba ) is a b b a abba abba , necessarily with x = a x=a x = a and y = b b y=bb y = bb . Then x y z xyz x y z and z y x zyx z y x are simultaneously a b b a abba abba when z = a z=a z = a , and otherwise both are ∞ \infty ∞ . This establishes the identity. Substitute x = a x=a x = a , y = b m y=b_m y = b m , z = c m − 1 z=c_{m-1} z = c m − 1 and add the remaining monomials of R m \mathbf{R}_m R m . Adding the two equivalent forms by idempotent addition yields the intermediate sum with both t m t_m t m and s m s_m s m .
Lemma 3.8. If m ≥ 2 m\ge2 m ≥ 2 , w ∈ Z m + \mathbf{w}\in Z_m^+ w ∈ Z m + , and ℓ ( w ) ≤ 4 \ell(\mathbf{w})\le4 ℓ ( w ) ≤ 4 , then the identity Q m ≈ Q m + w \mathbf{Q}_m\approx\mathbf{Q}_m+\mathbf{w} Q m ≈ Q m + w holds in A ^ 2 \widehat{A}_2 A 2 if and only if w ∈ S m \mathbf{w}\in\mathcal{S}_m w ∈ S m .
Proof. Every w ∈ S m \mathbf{w}\in\mathcal{S}_m w ∈ S m is absorbed by Q m \mathbf{Q}_m Q m by idempotence and Lemma 3.7.
Conversely, suppose A ^ 2 ⊨ Q m ≈ Q m + w \widehat{A}_2\models\mathbf{Q}_m\approx\mathbf{Q}_m+\mathbf{w} A 2 ⊨ Q m ≈ Q m + w . We must have a ∈ c ( w ) a\in c(\mathbf{w}) a ∈ c ( w ) : assigning a = 0 a=0 a = 0 and the remaining variables nonzero old factors gives Q m = 0 \mathbf{Q}_m=0 Q m = 0 but w ≠ 0 \mathbf{w}\ne0 w = 0 if a ∉ c ( w ) a\notin c(\mathbf{w}) a ∈ / c ( w ) . For any omitted path vertex x ∈ P m ∖ c ( w ) x\in P_m\setminus c(\mathbf{w}) x ∈ P m ∖ c ( w ) , Lemma 3.6 gives Q m θ x = a b b a \mathbf{Q}_m^{\theta_x}=abba Q m θ x = abba . Since w \mathbf{w} w is absorbed by Q m \mathbf{Q}_m Q m , flat addition gives w θ x = a b b a \mathbf{w}^{\theta_x}=abba w θ x = abba . Such a vertex exists, since ∣ P m ∣ = 2 m + 1 ≥ 5 |P_m|=2m+1\ge5 ∣ P m ∣ = 2 m + 1 ≥ 5 and w \mathbf{w} w contains a a a and at most three distinct path variables. All nonzero θ x \theta_x θ x -images lie in { a , b , b b , b a } \{a,b,bb,ba\} { a , b , bb , ba } . The only decompositions of a b b a abba abba into three or four factors from this set are
a b b a = a ⋅ b ⋅ b ⋅ a = a ⋅ b ⋅ b a = a ⋅ b b ⋅ a . abba=a\cdot b\cdot b\cdot a=a\cdot b\cdot ba=a\cdot bb\cdot a. abba = a ⋅ b ⋅ b ⋅ a = a ⋅ b ⋅ ba = a ⋅ bb ⋅ a . Consequently ℓ ( w ) ∈ { 3 , 4 } \ell(\mathbf{w})\in\{3,4\} ℓ ( w ) ∈ { 3 , 4 } .
Case ℓ ( w ) = 4 \ell(\mathbf{w})=4 ℓ ( w ) = 4 . The middle letters are b b b -variables; the endpoints are a a a or c c c -variables, with at least one endpoint equal to a a a . If the other endpoint is c h c_h c h and b m ∉ c ( w ) b_m\notin c(\mathbf{w}) b m ∈ / c ( w ) , deletion of b m b_m b m makes c h c_h c h evaluate to b a ba ba , not the required endpoint a a a . If b m ∈ c ( w ) b_m\in c(\mathbf{w}) b m ∈ c ( w ) , it occurs in a middle position; an omitted path vertex preceding b m b_m b m makes its image
b b bb bb , not the required one-letter factor b b b . Thus both endpoints are a a a and w = a b i b j a \mathbf{w}=ab_ib_ja w = a b i b j a . Deleting c 0 c_0 c 0 forces both middle variables to be b 0 b_0 b 0 :
w = a b 0 2 a . \mathbf{w}=ab_0^2a. w = a b 0 2 a .
Case ℓ ( w ) = 3 \ell(\mathbf{w})=3 ℓ ( w ) = 3 . The middle position is a b i b_i b i , the endpoints belong to { a } ∪ { c h : 0 ≤ h < m } \{a\}\cup\{c_h:0\le h<m\} { a } ∪ { c h : 0 ≤ h < m } , and at least one is a a a . There are three possibilities:
w ∈ { c h b i a , a b i a , a b i c j } . \mathbf{w}\in\{c_hb_ia,\ ab_ia,\ ab_ic_j\}. w ∈ { c h b i a , a b i a , a b i c j } .
For c h b i a c_hb_ia c h b i a , deletion of b m b_m b m excludes i < m i<m i < m , and deletion of c m − 1 c_{m-1} c m − 1 excludes h < m − 1 h<m-1 h < m − 1 ; hence w = c m − 1 b m a = s m \mathbf{w}=c_{m-1}b_ma=s_m w = c m − 1 b m a = s m . For a b i a ab_ia a b i a , deletion of b m b_m b m excludes i < m i<m i < m , giving w = a b m a \mathbf{w}=ab_ma w = a b m a . Finally, for a b i c j ab_ic_j a b i c j , the vertices b i , c j b_i,c_j b i , c j must lie on the same side of every omitted path vertex; otherwise their prescribed images cannot multiply with a a a to give a b b a abba abba . Hence they are adjacent in P m P_m P m , and
w ∈ { a b i c i , a b i + 1 c i : 0 ≤ i < m } . \mathbf{w}\in\{ab_ic_i,\ ab_{i+1}c_i:0\le i<m\}. w ∈ { a b i c i , a b i + 1 c i : 0 ≤ i < m } .
These are precisely the remaining members of S m \mathcal{S}_m S m .
Lemma 3.9. For every w ∈ Z m + \mathbf{w}\in Z_m^+ w ∈ Z m + with ℓ ( w ) ≥ 5 \ell(\mathbf{w})\ge5 ℓ ( w ) ≥ 5 , the identity Q m ≈ Q m + w \mathbf{Q}_m\approx\mathbf{Q}_m+\mathbf{w} Q m ≈ Q m + w holds in A ^ 2 \widehat{A}_2 A 2 if and only if c ( w ) = Z m c(\mathbf{w})=Z_m c ( w ) = Z m .
Proof. If the content is all of Z m Z_m Z m , any assignment with a new zero sends w \mathbf{w} w to 0 0 0 , and any all-old assignment sends both Q m \mathbf{Q}_m Q m (Lemma 3.5) and w \mathbf{w} w to ∞ \infty ∞ . Conversely, if a ∉ c ( w ) a\notin c(\mathbf{w}) a ∈ / c ( w ) , assign a = 0 a=0 a = 0 and all other variables nonzero old values: then Q m = 0 \mathbf{Q}_m=0 Q m = 0 and w = ∞ \mathbf{w}=\infty w = ∞ . If a path vertex x x x is omitted from the support, use θ x \theta_x θ x : it sends Q m \mathbf{Q}_m Q m to a b b a abba abba but sends the length-at-least-five word w \mathbf{w} w , involving only nonzero old values, to ∞ \infty ∞ . Thus the identity fails unless the content is all of Z m Z_m Z m .
The six-element kernel class
Hereafter fix X = Z m X=Z_m X = Z m . As in the singleton convention for P X P_X P X , the notation λ Z m \lambda_{Z_m} λ Z m also denotes { λ Z m } ∈ P X \{\lambda_{Z_m}\}\in P_X { λ Z m } ∈ P X when used as an additive summand. For U , V ∈ P X U,V\in P_X U , V ∈ P X , write U ∼ m V U\sim_m V U ∼ m V if and only if
α ^ ( U ) = α ^ ( V ) for every α : Z m → A ^ 2 . \widehat{\alpha}(U)=\widehat{\alpha}(V)\quad\text{for every }\alpha:Z_m\to\widehat{A}_2. α ( U ) = α ( V ) for every α : Z m → A 2 .
This is the kernel congruence of the joint evaluation map. Since Θ k , Z m ⊆ ker α ^ \Theta_{k,Z_m}\subseteq\ker\widehat{\alpha} Θ k , Z m ⊆ ker α for each α \alpha α , we have Θ k , Z m ⊆ ∼ m \Theta_{k,Z_m}\subseteq\sim_m Θ k , Z m ⊆ ∼ m .
Lemma 3.10 (Necessary short monomials). If U ∼ m Q m U\sim_m\mathbf{Q}_m U ∼ m Q m , then the short-word part of U U U contains every monomial of R m R_m R m and at least one of t m , s m t_m,s_m t m , s m .
Proof. First, U ∼ m Q m U\sim_m\mathbf{Q}_m U ∼ m Q m implies A ^ 2 ⊨ Q m + U ≈ Q m \widehat{A}_2\models\mathbf{Q}_m+U\approx\mathbf{Q}_m A 2 ⊨ Q m + U ≈ Q m . Thus every member of U U U is absorbed by Q m \mathbf{Q}_m Q m . By Lemmas 3.8 and 3.9,
U ⊆ S m ∪ { λ Z m } . U\subseteq\mathcal{S}_m\cup\{\lambda_{Z_m}\}. U ⊆ S m ∪ { λ Z m } . We now force the necessary short summands. In each test below, all unspecified variables take the new zero; hence λ Z m \lambda_{Z_m} λ Z m also has value 0 0 0 .
(i) Setting a = a a=a a = a , b 0 = b b_0=b b 0 = b isolates a b 0 2 a = a b b a ab_0^2a=abba a b 0 2 a = abba . Setting a = a a=a a = a , b m = b b b_m=bb b m = bb isolates a b m a = a b b a ab_ma=abba a b m a = abba .
(ii) Setting a = a a=a a = a , b 0 = b b_0=b b 0 = b , c 0 = a c_0=a c 0 = a gives
( a b 0 2 a ) α = a b b a , ( a b 0 c 0 ) α = ∞ , (ab_0^2a)^\alpha=abba,\qquad(ab_0c_0)^\alpha=\infty, ( a b 0 2 a ) α = abba , ( a b 0 c 0 ) α = ∞ , while all other allowed monomials have value 0 0 0 ; here a b a aba aba is not a factor of a b b a abba abba . This forces a b 0 c 0 ab_0c_0 a b 0 c 0 .
(iii) For 1 ≤ i < m 1 \le i < m 1 ≤ i < m , setting a = a a=a a = a , b i = b b_i=b b i = b , c i = b a c_i=ba c i = ba isolates ( a b i c i ) α = a b b a (ab_i c_i)^\alpha=abba ( a b i c i ) α = abba . For 0 ≤ i < m − 1 0 \le i < m-1 0 ≤ i < m − 1 , setting a = a a=a a = a , b i + 1 = b b_{i+1}=b b i + 1 = b , c i = b a c_i=ba c i = ba isolates ( a b i + 1 c i ) α = a b b a (ab_{i+1}c_i)^\alpha=abba ( a b i + 1 c i ) α = abba .
(iv) Finally, setting a = a a=a a = a , b m = b b b_m=bb b m = bb , c m − 1 = b c_{m-1}=b c m − 1 = b gives
( a b m a ) α = a b b a , ( t m ) α = ( s m ) α = ∞ , (ab_m a)^\alpha=abba,\qquad(t_m)^\alpha=(s_m)^\alpha=\infty, ( a b m a ) α = abba , ( t m ) α = ( s m ) α = ∞ ,
with every other allowed monomial taking value 0. Therefore at least one of t m , s m t_m,s_m t m , s m occurs in U U U .
In each of (i)–(iii), omitting the indicated monomial would make U U U and Q m Q_m Q m evaluate differently; (iv) rules out omitting both t m , s m t_m,s_m t m , s m . This proves the claim. □
Theorem 3.11 (The six-element kernel class). P U b P_{U b} P U b
F m = { R m + t m , R m + s m , R m + t m + s m } , F m + λ Z m : = { U + λ Z m : U ∈ F m } . F_m=\{R_m+t_m,\ R_m+s_m,\ R_m+t_m+s_m\},\qquad F_m+\lambda Z_m:=\{U+\lambda Z_m:U\in F_m\}. F m = { R m + t m , R m + s m , R m + t m + s m } , F m + λ Z m := { U + λ Z m : U ∈ F m } .
Then, for every m ≥ 2 m\ge2 m ≥ 2 ,
[ Q m ] ∼ m = F m ∪ ˙ ( F m + λ Z m ) . [Q_m]_{\sim_m}=F_m\mathbin{\dot\cup}(F_m+\lambda Z_m). [ Q m ] ∼ m = F m ∪ ˙ ( F m + λ Z m ) . In particular, this kernel class has exactly six elements.
Proof. By Lemmas 3.8 and 3.9, the only possible members of an element semantically equivalent to Q m Q_m Q m are the short monomials of S m \mathcal{S}_m S m and λ Z m \lambda Z_m λ Z m . By Lemma 3.10 , the short part contains all monomials in R m R_m R m and at least one of t m , s m t_m,s_m t m , s m . This yields only the six stated candidates. Lemma 3.7 makes the three short candidates equivalent, while Lemma 3.5 makes adjoining λ Z m \lambda Z_m λ Z m semantically inert. Hence the kernel class contains exactly these six elements. □
Lemma 3.12. If [ Q m ] Θ k , Z m = [ Q m + K m ] Θ k , Z m [Q_m]_{\Theta_{k,Z_m}}=[Q_m+K_m]_{\Theta_{k,Z_m}} [ Q m ] Θ k , Z m = [ Q m + K m ] Θ k , Z m , then some elementary congruence step generated by a valid identity in at most k k k variables, after substitution and application of a unary polynomial context, connects one member of F m F_m F m with one of ( F m + λ Z m ) (F_m+\lambda Z_m) ( F m + λ Z m ) .
Proof. A congruence generated by a family of pairs consists of the pairs connected by finite chains of elementary replacements, allowing substitutions, unary polynomial contexts, and reversed steps. Apply this description to the presumed equality. Proposition 3.3 ensures that each step preserves every evaluation in A ^ 2 \widehat{A}_2 A 2 , so every intermediate element is one of the six listed in Theorem 3.11 . The initial element is Q m ∈ F m Q_m\in F_m Q m ∈ F m ; the final one is Q m + K m ∈ ( F m + λ Z m ) Q_m+K_m\in(F_m+\lambda Z_m) Q m + K m ∈ ( F m + λ Z m ) . Some adjacent pair must therefore lie in different parts of the kernel class. We use only that a finite chain connecting the two parts must contain a crossing; the parts need not be congruence classes. In particular, no bounded-variable derivation between distinct short representatives is assumed. The argument also applies when k = 1 k=1 k = 1 or 2 2 2 . □
The uniform obstruction
Proposition 3.13 (Absorption normal form). Over the axioms of additively idempotent semirings, an identity p = u 1 + ⋯ + u r ≈ q = v 1 + ⋯ + v s p=u_1+\cdots+u_r\approx q=v_1+\cdots+v_s p = u 1 + ⋯ + u r ≈ q = v 1 + ⋯ + v s is equivalent to the conjunction
p ≈ p + v j ( 1 ≤ j ≤ s ) , q ≈ q + u i ( 1 ≤ i ≤ r ) . p\approx p+v_j\quad(1\le j\le s),\qquad q\approx q+u_i\quad(1\le i\le r). p ≈ p + v j ( 1 ≤ j ≤ s ) , q ≈ q + u i ( 1 ≤ i ≤ r ) . Consequently, a replacement by an identity valid in A ^ 2 \widehat{A}_2 A 2 can be factored into finitely many replacements by valid single-monomial absorption identities, without introducing new source variables.
Proof. If p ≈ q \mathbf{p} \approx\mathbf{q} p ≈ q , then p ≈ p + q \mathbf{p} \approx\mathbf{p}+\mathbf{q} p ≈ p + q . Since p + v j \mathbf{p}+\mathbf{v}_j p + v j is an additive subterm of p + q \mathbf{p}+\mathbf{q} p + q , each v j \mathbf{v}_j v j is absorbed by p \mathbf{p} p ; interchanging the two sides gives the second family. Conversely, summing the first family yields p ≈ p + q \mathbf{p} \approx\mathbf{p}+\mathbf{q} p ≈ p + q , and summing the second yields q ≈ p + q \mathbf{q} \approx\mathbf{p}+\mathbf{q} q ≈ p + q , hence p ≈ q \mathbf{p} \approx\mathbf{q} p ≈ q . The same deductions, under any substitution and any fixed context, supply a finite chain from one side to the other.
Lemma 3.14 (Linearization of polynomial contexts). By distributivity, a polynomial context containing its placeholder z z z exactly once has the schematic form
E + M z N , \mathbf{E}+\mathbf{M}z\mathbf{N}, E + M z N , where E \mathbf{E} E is a term independent of z z z (possibly absent), and M , N \mathbf{M},\mathbf{N} M , N are products independent of z z z (either factor may be absent). These are local placeholders for the context, reused in the proof of Theorem 3.17, rather than additional operations or distinguished elements of the semiring. A context containing several occurrences of z z z can be handled by replacing the occurrences one at a time. Omitted summands and factors are purely notational; they do not introduce named additive or multiplicative constants.
Proof. For a context with one occurrence of z z z , induct on its expression tree. The base z z z has the stated form with E , M , N \mathbf{E},\mathbf{M},\mathbf{N} E , M , N formally omitted. Adding a z z z -free term enlarges E \mathbf{E} E ; multiplying by a z z z -free term on either side, followed by distributivity, incorporates that term into the corresponding multiplier of the unique z z z . Thus the context has form E + M z N \mathbf{E}+\mathbf{M}z\mathbf{N} E + M z N , with the omissions interpreted as in the statement.
For a context with several occurrences, distinguish them as z 1 , … , z r z_1,\ldots,z_r z 1 , … , z r and write C ( x 1 , … , x r ) C(x_1,\ldots,x_r) C ( x 1 , … , x r ) for the same expression with these occurrences separately named. The successive terms in the replacement sequence have the forms
C ( p β , … , p β ) , C(\mathbf{p}^{\beta},\ldots,\mathbf{p}^{\beta}), C ( p β , … , p β ) ,
C ( q β , p β , … , p β ) , C(\mathbf{q}^{\beta},\mathbf{p}^{\beta},\ldots,\mathbf{p}^{\beta}), C ( q β , p β , … , p β ) ,
C ( q β , … , q β ) . C(\mathbf{q}^{\beta},\ldots,\mathbf{q}^{\beta}). C ( q β , … , q β ) .
At each step, one occurrence is replaced using the same substituted identity, with the other occurrences fixed. Every step preserves evaluation in A ^ 2 \widehat{A}_2 A 2 ; hence all intermediate terms lie in [ Q m ] ∼ m [\mathcal{Q}_m]_{\sim_m} [ Q m ] ∼ m whenever the initial one does. The steps can also be performed in reverse order.
Lemma 3.15 (Common old-factor realization on a proper support). If S ⊊ Z m S \subsetneq Z_m S ⊊ Z m and a ∈ S a \in S a ∈ S , there is an assignment α : Z m → A ^ 2 \alpha: Z_m \to\widehat{A}_2 α : Z m → A 2 such that every v ∈ S m \mathbf{v} \in\mathcal{S}_m v ∈ S m with c ( v ) ⊆ S c(\mathbf{v}) \subseteq S c ( v ) ⊆ S evaluates to a b b a \mathit{abba} abba .
Proof. Choose x ∈ Z m ∖ S x \in Z_m \setminus S x ∈ Z m ∖ S ; then x ∈ P m x \in P_m x ∈ P m . Every indicated v \mathbf{v} v avoids x x x , so θ x \theta_x θ x from Lemma 3.6 evaluates it to a b b a \mathit{abba} abba .
Lemma 3.16. Let p ≈ p + w \mathbf{p} \approx\mathbf{p}+\mathbf{w} p ≈ p + w be a valid absorption identity of A ^ 2 \widehat{A}_2 A 2 using at most k k k source variables. Let β \beta β be an arbitrary substitution into P X P_X P X . Fix actual short words s , t \mathbf{s},\mathbf{t} s , t , either of which may be formally omitted, and put d = ℓ ( s ) + ℓ ( t ) d=\ell(\mathbf{s})+\ell(\mathbf{t}) d = ℓ ( s ) + ℓ ( t ) . Assume
∅ ≠ s p β t ⊆ S m , s w β t ≠ ∅ , ∣ Z m ∣ > 4 k . (2) \varnothing\ne\mathbf{s}\mathbf{p}^{\beta}\mathbf{t} \subseteq\mathcal{S}_m,\qquad\mathbf{s}\mathbf{w}^{\beta}\mathbf{t}\ne\varnothing,\qquad|Z_m|>4k. \tag*{(2)} ∅ = s p β t ⊆ S m , s w β t = ∅ , ∣ Z m ∣ > 4 k . (2) Then ℓ ( w ) ≤ 4 \ell(\mathbf{w})\le4 ℓ ( w ) ≤ 4 . Furthermore, every variable occurring in w \mathbf{w} w is substituted by a nonempty set consisting entirely of words of length at most 4 − d 4-d 4 − d ; no long support class occurs in those substituted values.
Proof. 1. Remove empty substitution images. Since ∅ ≠ sp β t ⊆ S m \varnothing\ne\operatorname{sp}^{\beta}t \subseteq\mathcal{S}_m ∅ = sp β t ⊆ S m , all its words have length three or four and d ≤ 3 d \le3 d ≤ 3 . For a formally omitted multiplier, its length is counted as zero and its content as empty; this is notation only, not a multiplicative identity adjoined to the semiring. Put
Y 0 = { y : β ( y ) = ∅ } . Y_0=\{y:\beta(y)=\varnothing\}. Y 0 = { y : β ( y ) = ∅ } .
and delete from p \mathbf{p} p all monomials containing a variable in Y 0 Y_0 Y 0 ; denote the nonempty remaining sum by p 0 \mathbf{p}_0 p 0 . The condition sw β t ≠ ∅ \operatorname{sw}^{\beta}t\ne\varnothing sw β t = ∅ in (1) implies c ( w ) ∩ Y 0 = ∅ c(\mathbf{w})\cap Y_0=\varnothing c ( w ) ∩ Y 0 = ∅ . Assigning the new zero to all variables of Y 0 Y_0 Y 0 in the valid source identity gives
A ^ 2 ⊨ p 0 ≈ p 0 + w . \widehat{A}_2\models\mathbf{p}_0\approx\mathbf{p}_0+\mathbf{w}. A 2 ⊨ p 0 ≈ p 0 + w .
Every y ∈ c ( p 0 ) y\in c(\mathbf{p}_0) y ∈ c ( p 0 ) has β ( y ) ≠ ∅ \beta(y)\ne\varnothing β ( y ) = ∅ .
2. Bound every substituted word. Fix y ∈ c ( p 0 ) y\in c(\mathbf{p}_0) y ∈ c ( p 0 ) and any v ∈ β ( y ) \mathbf{v}\in\beta(y) v ∈ β ( y ) . Choose a surviving monomial of p 0 \mathbf{p}_0 p 0 containing y y y and a member of the nonempty image for each of its other variable occurrences. The resulting product belongs to sp β t ⊆ S m \operatorname{sp}^{\beta}t\subseteq\mathcal{S}_m sp β t ⊆ S m . A long-support class among its factors would produce a long class, while a genuine word of length greater than 4 − d 4-d 4 − d would give a product longer than four (or a long class). Both contradict the displayed containment. Thus, for every y ∈ c ( p 0 ) y\in c(\mathbf{p}_0) y ∈ c ( p 0 ) ,
∅ ≠ β ( y ) ⊆ { v ∈ Z m + : 1 ≤ ℓ ( v ) ≤ 4 − d } . \varnothing\ne\beta(y)\subseteq\{\mathbf{v}\in Z_m^+:1\le\ell(\mathbf{v})\le4-d\}. ∅ = β ( y ) ⊆ { v ∈ Z m + : 1 ≤ ℓ ( v ) ≤ 4 − d } .
This applies to all members of each substitution image, not only to the factors of one chosen expansion.
3. Construct a common old evaluation. For each y ∈ c ( p 0 ) y\in c(\mathbf{p}_0) y ∈ c ( p 0 ) choose one fixed v y ∈ β ( y ) \mathbf{v}_y\in\beta(y) v y ∈ β ( y ) and use it at every occurrence of y y y . Let
S = c ( s ) ∪ c ( t ) ∪ ⋃ y ∈ c ( p 0 ) c ( v y ) . S=c(\mathbf{s})\cup c(\mathbf{t})\cup\bigcup_{y\in c(\mathbf{p}_0)}c(\mathbf{v}_y). S = c ( s ) ∪ c ( t ) ∪ y ∈ c ( p 0 ) ⋃ c ( v y ) .
As ∣ c ( p 0 ) ∣ ≤ k |c(\mathbf{p}_0)|\le k ∣ c ( p 0 ) ∣ ≤ k and each chosen word v y \mathbf{v}_y v y contains at most 4 − d 4-d 4 − d variable occurrences, while ∣ c ( s ) ∪ c ( t ) ∣ ≤ d |c(\mathbf{s})\cup c(\mathbf{t})|\le d ∣ c ( s ) ∪ c ( t ) ∣ ≤ d , we have
∣ S ∣ ≤ d + ∣ c ( p 0 ) ∣ ( 4 − d ) ≤ d + k ( 4 − d ) ≤ 4 k < ∣ Z m ∣ . |S|\le d+|c(\mathbf{p}_0)|(4-d)\le d+k(4-d)\le4k<|Z_m|. ∣ S ∣ ≤ d + ∣ c ( p 0 ) ∣ ( 4 − d ) ≤ d + k ( 4 − d ) ≤ 4 k < ∣ Z m ∣.
The last inequality uses 0 ≤ d ≤ 3 0\le d\le3 0 ≤ d ≤ 3 and k ≥ 1 k\ge1 k ≥ 1 ; no distinctness among the letters of different v y \mathbf{v}_y v y is assumed. Every surviving monomial u \mathbf{u} u of p 0 \mathbf{p}_0 p 0 yields a nonempty expansion s u ( v y ) t ∈ S m \mathbf{s}\mathbf{u}(\mathbf{v}_y)\mathbf{t}\in\mathcal{S}_m su ( v y ) t ∈ S m , so a ∈ S a\in S a ∈ S . Lemma 3.15 now provides an assignment α : Z m → A ^ 2 \alpha:Z_m\to\widehat{A}_2 α : Z m → A 2 under which all these expansions have value a b b a abba abba . The actual factors among s \mathbf{s} s , t \mathbf{t} t , v y \mathbf{v}_y v y therefore take old non-top values. Set γ ( y ) = v y \gamma(y)=\mathbf{v}_y γ ( y ) = v y for each y ∈ c ( p 0 ) y\in c(\mathbf{p}_0) y ∈ c ( p 0 ) . For every monomial u \mathbf{u} u of p 0 \mathbf{p}_0 p 0 ,
s α u γ t α = a b b a . \mathbf{s}^{\alpha}\mathbf{u}^{\gamma}\mathbf{t}^{\alpha}=abba. s α u γ t α = abba .
These are non-top equalities of concatenated words. Cancelling the same left and right factors yields one old non-top word h h h such that
u γ = h ( u a monomial of p 0 ) , p 0 γ = h ≠ ∞ . \mathbf{u}^{\gamma}=h\quad(\mathbf{u}\text{ a monomial of }\mathbf{p}_0),\qquad\mathbf{p}_0^{\gamma}=h\ne\infty. u γ = h ( u a monomial of p 0 ) , p 0 γ = h = ∞.
The consistency of the choice v y \mathbf{v}_y v y at all occurrences is essential for this common assignment γ \gamma γ .
4. Bound the query word. If some y ∈ c ( w ) ∖ c ( p 0 ) y\in c(\mathbf{w})\setminus c(\mathbf{p}_0) y ∈ c ( w ) ∖ c ( p 0 ) existed, extend γ \gamma γ by assigning y = ∞ y=\infty y = ∞ and arbitrary old nonabsorbing factors to the remaining variables outside c ( p 0 ) c(\mathbf{p}_0) c ( p 0 ) . Then
p 0 γ = h ≠ ∞ , w γ = ∞ . \mathbf{p}_0^{\gamma}=h\ne\infty,\qquad\mathbf{w}^{\gamma}=\infty. p 0 γ = h = ∞ , w γ = ∞.
contrary to p 0 ≈ p 0 + w \mathbf{p}_0 \approx\mathbf{p}_0+\mathbf{w} p 0 ≈ p 0 + w . Consequently c ( w ) ⊆ c ( p 0 ) c(\mathbf{w}) \subseteq c(\mathbf{p}_0) c ( w ) ⊆ c ( p 0 ) . All variables of w \mathbf{w} w therefore take old non-top factor values under γ \gamma γ . If ℓ ( w ) ≥ 5 \ell(\mathbf{w}) \ge5 ℓ ( w ) ≥ 5 , their product is ∞ \infty ∞ , again contradicting p 0 γ = h ≠ ∞ \mathbf{p}_0^\gamma= h \ne\infty p 0 γ = h = ∞ . Hence
ℓ ( w ) ≤ 4 , ∅ ≠ β ( y ) ⊆ { v ∈ Z m + : 1 ≤ ℓ ( v ) ≤ 4 − d } ( y ∈ c ( w ) ) , \ell(\mathbf{w}) \le4,\qquad\varnothing\ne\beta(y) \subseteq\{ \mathbf{v} \in Z_m^+ : 1 \le\ell(\mathbf{v}) \le4-d\}\quad(y \in c(\mathbf{w})), ℓ ( w ) ≤ 4 , ∅ = β ( y ) ⊆ { v ∈ Z m + : 1 ≤ ℓ ( v ) ≤ 4 − d } ( y ∈ c ( w )) ,
as required. Both bounds will be used in Theorem 3.17 . □
Theorem 3.17. For m ≥ 2 m \ge2 m ≥ 2 , k ≥ 1 k \ge1 k ≥ 1 , suppose
∣ Z m ∣ = 2 m + 2 > max { 4 k , 16 } . |Z_m| = 2m+2 > \max\{4k,16\}. ∣ Z m ∣ = 2 m + 2 > max { 4 k , 16 } . No identity valid in A ^ 2 \widehat{A}_2 A 2 using at most k k k variables can, by arbitrary polynomial substitution and arbitrary polynomial context, induce an elementary congruence step from F m F_m F m to ( F m + λ Z m ) (F_m+\lambda Z_m) ( F m + λ Z m ) .
Proof. Suppose that such a crossing step exists. By Proposition 3.13 and Lemma 3.14 , refine it into a finite chain of valid monomial-absorption steps
E + M p β N ≈ E + M ( p + w ) β N . \mathbf{E}+\mathbf{M}\mathbf{p}^{\beta}\mathbf{N}\approx\mathbf{E}+\mathbf{M}(\mathbf{p}+\mathbf{w})^{\beta}\mathbf{N}. E + M p β N ≈ E + M ( p + w ) β N .
where p ≈ p + w \mathbf{p}\approx\mathbf{p}+\mathbf{w} p ≈ p + w has at most k k k source variables. Every intermediate expression remains in [ Q m ] ∼ m [\mathbf{Q}_m]_{\sim_m} [ Q m ] ∼ m , so at least one refined step crosses between F m F_m F m and F m + λ Z m F_m+\lambda Z_m F m + λ Z m . Orient that step from the part without λ Z m \lambda Z_m λ Z m to the other part. By Theorem 3.11 ,
M p β N ⊆ S m , λ Z m ∈ M w β N . \mathbf{M}\mathbf{p}^{\beta}\mathbf{N}\subseteq\mathcal{S}_m,\qquad\lambda Z_m\in\mathbf{M}\mathbf{w}^{\beta}\mathbf{N}. M p β N ⊆ S m , λ Z m ∈ M w β N .
The old-side product is nonempty. A formally omitted multiplier contributes no factor; ∅ ∈ P X \varnothing\in\mathcal{P}_X ∅ ∈ P X , by contrast, annihilates products. The second displayed condition therefore ensures that every actual multiplier is nonempty. If M p β N = ∅ \mathbf{M}\mathbf{p}^{\beta}\mathbf{N}=\varnothing M p β N = ∅ , then p β = ∅ \mathbf{p}^{\beta}=\varnothing p β = ∅ and w β ≠ ∅ \mathbf{w}^{\beta}\ne\varnothing w β = ∅ . But the map
P X ⟶ { 0 , ∞ } ≤ A ^ 2 , U ⟼ { 0 , U = ∅ , ∞ , U ≠ ∅ \mathcal{P}_X\longrightarrow\{0,\infty\}\leq\widehat{A}_2,\qquad U\longmapsto
\begin{cases}
0,&U=\varnothing,\\
\infty,&U\ne\varnothing
\end{cases} P X ⟶ { 0 , ∞ } ≤ A 2 , U ⟼ { 0 , ∞ , U = ∅ , U = ∅
is a semiring homomorphism: the union of sets and the product of nonempty subsets of X + X^+ X + preserve nonemptiness. Applying this map after β \beta β to the valid identity p ≈ p + w \mathbf{p}\approx\mathbf{p}+\mathbf{w} p ≈ p + w would give 0 = ∞ 0=\infty 0 = ∞ , a contradiction. Thus
M p β N ≠ ∅ . \mathbf{M}\mathbf{p}^{\beta}\mathbf{N}\ne\varnothing. M p β N = ∅ .
Fix a witness and apply the sparse bound. Choose a single product witness for λ Z m ∈ M w β N \lambda Z_m\in\mathbf{M}\mathbf{w}^{\beta}\mathbf{N} λ Z m ∈ M w β N , taking its left and right factors to be s , t \mathbf{s},\mathbf{t} s , t (with a formally omitted side absent). Fixing these same factors, p β ≠ ∅ \mathbf{p}^{\beta}\ne\varnothing p β = ∅ ensures
∅ ≠ s p β t ⊆ S m , λ Z m ∈ s w β t . \varnothing\ne\mathbf{s}\mathbf{p}^{\beta}\mathbf{t}\subseteq\mathcal{S}_m,\qquad\lambda Z_m\in\mathbf{s}\mathbf{w}^{\beta}\mathbf{t}. ∅ = s p β t ⊆ S m , λ Z m ∈ s w β t .
No chosen multiplier can be a long-support class, since the first product consists of short words. Write d = ℓ ( s ) + ℓ ( t ) d=\ell(\mathbf{s})+\ell(\mathbf{t}) d = ℓ ( s ) + ℓ ( t ) . Lemma 3.16 gives ℓ ( w ) ≤ 4 \ell(\mathbf{w})\le4 ℓ ( w ) ≤ 4 and bounds each substituted word occurring in an expansion of w \mathbf{w} w by 4 − d 4-d 4 − d . The concrete concatenation representing the chosen full-support class will be denoted by v \mathbf{v} v . Its length satisfies
ℓ ( v ) ≤ d + ℓ ( w ) ( 4 − d ) ≤ d + 4 ( 4 − d ) = 16 − 3 d ≤ 16. \ell(\mathbf{v})\le d+\ell(\mathbf{w})(4-d)\le d+4(4-d)=16-3d\le16. ℓ ( v ) ≤ d + ℓ ( w ) ( 4 − d ) ≤ d + 4 ( 4 − d ) = 16 − 3 d ≤ 16.
On the other hand, a word in λ Z m \lambda Z_m λ Z m contains all ∣ Z m ∣ > 16 |Z_m|>16 ∣ Z m ∣ > 16 distinct variables; its length is at least ∣ Z m ∣ |Z_m| ∣ Z m ∣ . This contradiction rules out the crossing step. □
Finite countermodels and consequences
For each k ≥ 1 k \ge1 k ≥ 1 , take
m ( k ) = max { 2 k , 8 } , X k = Z m ( k ) , D k = D k , X k . m(k)=\max\{2k,8\}, \qquad X_k=\mathbb{Z}_{m(k)}, \qquad D_k=D_{k,X_k}. m ( k ) = max { 2 k , 8 } , X k = Z m ( k ) , D k = D k , X k .
We have ∣ X k ∣ = 2 m ( k ) + 2 > max { 4 k , 16 } |X_k|=2m(k)+2>\max\{4k,16\} ∣ X k ∣ = 2 m ( k ) + 2 > max { 4 k , 16 } .
Theorem 3.18. For every k ≥ 1 k \ge1 k ≥ 1 , the finite idempotent semiring D k D_k D k satisfies
D k ⊨ Id ≤ k ( A ^ 2 ) , D k ∉ W ∞ . D_k \models\operatorname{Id}_{\leq k}(\widehat{A}_2), \qquad D_k \notin\mathcal{W}_{\infty}. D k ⊨ Id ≤ k ( A 2 ) , D k ∈ / W ∞ .
Proof. By Proposition 3.3, D k ⊨ Id ≤ k ( A ^ 2 ) D_k \models\operatorname{Id}_{\leq k}(\widehat{A}_2) D k ⊨ Id ≤ k ( A 2 ) . If D k ∈ W ∞ D_k \in\mathcal{W}_{\infty} D k ∈ W ∞ , then Lemma 3.5 would yield
D k ⊨ Q m ( k ) ≈ Q m ( k ) + K m ( k ) . D_k \models Q_{m(k)} \approx Q_{m(k)}+K_{m(k)}. D k ⊨ Q m ( k ) ≈ Q m ( k ) + K m ( k ) .
Evaluating at the canonical singleton generators gives
[ Q m ( k ) ] Θ k , X k = [ Q m ( k ) + K m ( k ) ] Θ k , X k . [Q_{m(k)}]_{\Theta_{k,X_k}}=[Q_{m(k)}+K_{m(k)}]_{\Theta_{k,X_k}}. [ Q m ( k ) ] Θ k , X k = [ Q m ( k ) + K m ( k ) ] Θ k , X k .
By Lemma 3.12, this requires an elementary crossing from F m ( k ) F_{m(k)} F m ( k ) to F m ( k ) + λ Z m ( k ) F_{m(k)}+\lambda Z_{m(k)} F m ( k ) + λ Z m ( k ) , contrary to Theorem 3.17. Hence D k ∉ W ∞ D_k \notin\mathcal{W}_{\infty} D k ∈ / W ∞ . □
We now complete the proof of Theorem 3.1.
Proof. Suppose, more generally, that K \mathcal{K} K has an identity basis Σ \Sigma Σ (possibly infinite) whose members each involve at most k k k variables, and that W 2 ⊆ K ⊆ W ∞ \mathcal{W}_2 \subseteq\mathcal{K} \subseteq\mathcal{W}_{\infty} W 2 ⊆ K ⊆ W ∞ . As W 2 ⊆ K \mathcal{W}_2 \subseteq\mathcal{K} W 2 ⊆ K , every identity of Σ \Sigma Σ holds in A ^ 2 \widehat{A}_2 A 2 . By Theorem 3.18, D k ⊨ Σ D_k \models\Sigma D k ⊨ Σ , whence D k ∈ K ⊆ W ∞ D_k \in\mathcal{K} \subseteq\mathcal{W}_{\infty} D k ∈ K ⊆ W ∞ , contrary to the construction of D k D_k D k .
For n ≥ 2 n \ge2 n ≥ 2 , the central four-letter block of m n m_n m n is t n − 1 t n t n t n − 1 t_{n-1}t_nt_nt_{n-1} t n − 1 t n t n t n − 1 . Its nonempty factors, together with the old top and the new zero, form a subsemiring of A ^ n \widehat{A}_n A n isomorphic to A ^ 2 \widehat{A}_2 A 2 : both letters of the central block occur nowhere outside this block in m n m_n m n , so no new concatenation factor involving these letters arises. Consequently W 2 ⊆ W n ⊆ W ∞ \mathcal{W}_2 \subseteq\mathcal{W}_n \subseteq\mathcal{W}_{\infty} W 2 ⊆ W n ⊆ W ∞ . □
The individual finite-basis classification in Theorem 1.1 follows directly from the theorem of Shao–Gao.
Proof. Shao–Gao [19 Theorem 1.1] proved that the zero extension S ( W ) 0 S(W)^0 S ( W ) 0 of a flat word semiring is finitely based in the binary signature if and only if every defining word has length at most two. Since ∣ m n ∣ = 2 n |m_n|=2n ∣ m n ∣ = 2 n , the classification follows immediately. □
Corollary 3.19 (Shao–Gao). For every n ≥ 2 n \ge2 n ≥ 2 , the variety W n \mathcal{W}_n W n has infinite axiomatic rank.
Proof. The word set { m n } \{m_n\} { m n } is finite and contains a word of length 2 n ≥ 4 2n \ge4 2 n ≥ 4 , so the cited corollary applies. □
Corollary 3.20. For every n ≥ 2 n \ge2 n ≥ 2 , every variety in [ W n , W n + 1 ] [\mathcal{W}_n,\mathcal{W}_{n+1}] [ W n , W n + 1 ] has infinite axiomatic rank, and hence is nonfinitely based. The interval [ W 1 , W 2 ] [\mathcal{W}_1,\mathcal{W}_2] [ W 1 , W 2 ] contains both a finitely based variety and a nonfinitely based variety.
Proof. The first assertion is a consequence of Theorem 3.1. For the second, Theorem 1.1 shows that W 1 \mathcal{W}_1 W 1 is finitely based whereas W 2 \mathcal{W}_2 W 2 is not. □
Corollary 3.21 (Lower bound on identity-variable complexity). Let ρ ( m ) = min { k ≥ 1 : [ Q m ] Θ k , Z m = [ Q m + K m ] Θ k , Z m } \rho(m)=\min\{k\ge1:[Q_m]_{\Theta_k,Z_m}=[Q_m+K_m]_{\Theta_k,Z_m}\} ρ ( m ) = min { k ≥ 1 : [ Q m ] Θ k , Z m = [ Q m + K m ] Θ k , Z m } . For m ≥ 8 m\ge8 m ≥ 8 ,
⌈ m + 1 2 ⌉ ≤ ρ ( m ) ≤ 2 m + 2 , and thus ρ ( m ) ⟶ ∞ . \left\lceil\frac{m+1}{2}\right\rceil\le\rho(m)\le2m+2,\qquad\text{and thus }\rho(m)\longrightarrow\infty. ⌈ 2 m + 1 ⌉ ≤ ρ ( m ) ≤ 2 m + 2 , and thus ρ ( m ) ⟶ ∞. Proof. The identity δ m \delta_m δ m itself uses 2 m + 2 2m+2 2 m + 2 variables and is valid in A ^ 2 \widehat{A}_2 A 2 , giving the upper bound. For k < ⌈ ( m + 1 ) / 2 ⌉ k<\lceil(m+1)/2\rceil k < ⌈( m + 1 ) /2 ⌉ one has 4 k < 2 m + 2 4k<2m+2 4 k < 2 m + 2 , and for m ≥ 8 m\ge8 m ≥ 8 also 16 < 2 m + 2 16<2m+2 16 < 2 m + 2 . Theorem 3.17 , combined with Lemma 3.12, excludes equality in the defining set for such k k k . □
Variety inclusions and continuum intervals
We first establish the strict ascending chain of zero-extension varieties and then obtain continuum-sized consecutive intervals by an independent graph construction. The intervals between a flat word variety and its zero extension are treated separately, using the cyclic semirings of Shao–Gao and checking their endpoint conditions.
The chain of mirror-word varieties
Proposition 4.1. For every n ≥ 1 n\ge1 n ≥ 1 , W n ⊊ W n + 1 \mathcal{W}_n\subsetneq\mathcal{W}_{n+1} W n ⊊ W n + 1 and V n ⊊ W n \mathcal{V}_n\subsetneq\mathcal{W}_n V n ⊊ W n .
Proof. The central mirror block embeds A n A_n A n into A n + 1 A_{n+1} A n + 1 , and the embedding extends to the new zero. The identity
z 1 ⋯ z n + 1 z n + 1 ⋯ z 1 ≈ z 1 ⋯ z n + 1 z n + 1 ⋯ z 1 + z 1 3 ⋯ z n + 1 3 z_1\cdots z_{n+1}z_{n+1}\cdots z_1\approx z_1\cdots z_{n+1}z_{n+1}\cdots z_1+z_1^3\cdots z_{n+1}^3 z 1 ⋯ z n + 1 z n + 1 ⋯ z 1 ≈ z 1 ⋯ z n + 1 z n + 1 ⋯ z 1 + z 1 3 ⋯ z n + 1 3 holds in A ^ n \widehat{A}_n A n : with a zero variable both words are zero, and otherwise both have absorbing old value. It fails in A ^ n + 1 \widehat{A}_{n+1} A n + 1 under z i = a i z_i=a_i z i = a i . The old algebra is a subalgebra of its extension. The identity x 3 ≈ y 3 x^3\approx y^3 x 3 ≈ y 3 holds in A n A_n A n and fails in the extension at x = 0 x=0 x = 0 , y = a n y=a_n y = a n , so the containment is proper. □
Graph constructions and separating identities
We use finite context quotients to encode graph homomorphisms in the consecutive intervals; compare [6 ] . This is the restriction of the conjunctive syntactic semiring congruence of a language, as used by Polák [14 ] , to the free ai-semiring of nonempty finite subsets of X + X^+ X + . Thus we use its constant-free positive-word fragment, rather than introducing a new operation.
Let X X X be a finite alphabet and let P ⊆ X + P\subseteq X^+ P ⊆ X + be a finite, nonempty language. Let P f ( X + ) \mathcal{P}_f(X^+) P f ( X + ) be the free ai-semiring on X X X : its elements are finite nonempty subsets of X + X^+ X + , with union and setwise concatenation as operations. For each nonempty finite F ⊆ X + F\subseteq X^+ F ⊆ X + , define its context profile by
ρ P ( F ) = { ( u , v ) ∈ X ∗ × X ∗ : u F v ⊆ P } . \rho_P(F)=\{(u,v)\in X^*\times X^*:uFv\subseteq P\}. ρ P ( F ) = {( u , v ) ∈ X ∗ × X ∗ : u F v ⊆ P } .
Declare F ≡ P G F \equiv_P G F ≡ P G when ρ P ( F ) = ρ P ( G ) \rho_P(F) = \rho_P(G) ρ P ( F ) = ρ P ( G ) . For nonempty finite F , G , C ⊆ X + F,G,C \subseteq X^+ F , G , C ⊆ X + and contexts u , v ∈ X ∗ \mathbf{u},\mathbf{v} \in X^* u , v ∈ X ∗ , addition is reflected in the profile identity
ρ P ( F ∪ G ) = ρ P ( F ) ∩ ρ P ( G ) . \rho_P(F \cup G) = \rho_P(F) \cap\rho_P(G). ρ P ( F ∪ G ) = ρ P ( F ) ∩ ρ P ( G ) .
Moreover, ( u , v ) ∈ ρ P ( F C ) (\mathbf{u},\mathbf{v}) \in\rho_P(FC) ( u , v ) ∈ ρ P ( F C ) if and only if ( u , c v ) ∈ ρ P ( F ) (\mathbf{u},c\mathbf{v}) \in\rho_P(F) ( u , c v ) ∈ ρ P ( F ) for every c ∈ C c \in C c ∈ C . Similarly, ( u , v ) ∈ ρ P ( C F ) (\mathbf{u},\mathbf{v}) \in\rho_P(CF) ( u , v ) ∈ ρ P ( C F ) if and only if ( u c , v ) ∈ ρ P ( F ) (\mathbf{u}c,\mathbf{v}) \in\rho_P(F) ( u c , v ) ∈ ρ P ( F ) for every c ∈ C c \in C c ∈ C . Thus ≡ P \equiv_P ≡ P is a semiring congruence. Denote the quotient by D ( P ) D(P) D ( P ) , with absorbing element ∞ \infty ∞ represented by an empty context profile. Put L = max { ℓ ( p ) : p ∈ P } L = \max\{\ell(\mathbf{p}) : \mathbf{p} \in P\} L = max { ℓ ( p ) : p ∈ P } . If ρ P ( F ) ≠ ∅ \rho_P(F) \ne\varnothing ρ P ( F ) = ∅ , every f ∈ F f \in F f ∈ F has length at most L L L and every ( u , v ) ∈ ρ P ( F ) (\mathbf{u},\mathbf{v}) \in\rho_P(F) ( u , v ) ∈ ρ P ( F ) satisfies ℓ ( u ) + ℓ ( v ) < L \ell(\mathbf{u})+\ell(\mathbf{v}) < L ℓ ( u ) + ℓ ( v ) < L . There are therefore only finitely many profiles, and D ( P ) D(P) D ( P ) is finite. The empty word is used solely in contexts, not as a semiring constant.
In the notation of Section 2, for each finite nonempty set P = { p 1 , … , p r } P = \{\mathbf{p}_1,\ldots,\mathbf{p}_r\} P = { p 1 , … , p r } the corresponding term is
w = p 1 + ⋯ + p r . \mathbf{w} = \mathbf{p}_1+\cdots+\mathbf{p}_r. w = p 1 + ⋯ + p r .
We use only this ordinary finite sum of words; its order is immaterial, and the empty sum is not a term.
Proposition 4.2. Let K \mathcal{K} K be a variety of ai-semirings and let P = { p 1 , … , p r } ⊆ X + P = \{\mathbf{p}_1,\ldots,\mathbf{p}_r\} \subseteq X^+ P = { p 1 , … , p r } ⊆ X + be finite and nonempty. Put w = p 1 + ⋯ + p r \mathbf{w} = \mathbf{p}_1+\cdots+\mathbf{p}_r w = p 1 + ⋯ + p r . Suppose that every q ∈ X + \mathbf{q} \in X^+ q ∈ X + satisfying K ⊨ q ⪯ w \mathcal{K} \models\mathbf{q} \preceq\mathbf{w} K ⊨ q ⪯ w belongs to P P P . Then D ( P ) ∈ K D(P) \in\mathcal{K} D ( P ) ∈ K .
Proof. Let s ≈ t \mathbf{s} \approx\mathbf{t} s ≈ t hold in K \mathcal{K} K , and substitute arbitrary nonempty finite languages for its variables. Write F , G F,G F , G for the resulting nonempty word sets. Thus
K ⊨ F ≈ G , \mathcal{K} \models F \approx G, K ⊨ F ≈ G ,
where, as in Section 2, each finite word set is identified with its additive term.
Fix α , β ∈ X ∗ \alpha,\beta\in X^* α , β ∈ X ∗ with α F β ⊆ P \alpha F\beta\subseteq P α F β ⊆ P . Context closure of s ≈ t \mathbf{s} \approx\mathbf{t} s ≈ t , followed by additive idempotence, gives
K ⊨ α F β ≈ α G β , w ≈ w + α F β , w ≈ w + α G β . \mathcal{K} \models\alpha F\beta\approx\alpha G\beta,\qquad\mathbf{w} \approx\mathbf{w}+\alpha F\beta,\qquad\mathbf{w} \approx\mathbf{w}+\alpha G\beta. K ⊨ α F β ≈ α Gβ , w ≈ w + α F β , w ≈ w + α Gβ .
For every g ∈ G \mathbf{g} \in G g ∈ G we obtain K ⊨ α g β ⪯ w \mathcal{K} \models\alpha\mathbf{g}\beta\preceq\mathbf{w} K ⊨ α g β ⪯ w . The hypothesis therefore gives α g β ∈ P \alpha\mathbf{g}\beta\in P α g β ∈ P . Hence α G β ⊆ P \alpha G\beta\subseteq P α Gβ ⊆ P . Interchanging F , G F,G F , G proves the reverse implication, so ρ P ( F ) = ρ P ( G ) \rho_P(F) = \rho_P(G) ρ P ( F ) = ρ P ( G ) . Every identity valid in K \mathcal{K} K is therefore valid in D ( P ) D(P) D ( P ) , whence D ( P ) ∈ K D(P) \in\mathcal{K} D ( P ) ∈ K . □ \square □
For a finite simple graph G G G without isolated vertices and with at least one edge, the following constructions are defined using a variable y v y_v y v for each vertex v ∈ V ( G ) v \in V(G) v ∈ V ( G ) . The anchor and vertex symbols in these languages are formal variables; letters in the fixed defining words are distinguished by context.
For n ≥ 2 n \ge2 n ≥ 2 , put h = 2 n h = 2n h = 2 n . Choose h − 2 h-2 h − 2 distinct anchor letters indexed by
a 1 , … , a n − 1 , a n + 2 , … , a h , a_1,\ldots,a_{n-1},\quad a_{n+2},\ldots,a_h, a 1 , … , a n − 1 , a n + 2 , … , a h ,
and a distinct letter y v y_v y v for each vertex of G G G . For every oriented edge ( u , v ) (u,v) ( u , v ) , form the word of length h h h with y u , y v y_u,y_v y u , y v in positions n , n + 1 n,n+1 n , n + 1 and the anchors in their indicated positions. Include also all words obtained by independently interchanging the letters in positions ( j , h + 1 − j ) (j,h+1-j) ( j , h + 1 − j ) for 2 ≤ j ≤ n − 1 2 \le j \le n-1 2 ≤ j ≤ n − 1 . The pair of outer positions ( 1 , h ) (1,h) ( 1 , h ) is never interchanged. Let P n , G P_{n,G} P n , G be this finite set of linear words and put
T n , G = D ( P n , G ) , u n , G = p 1 + ⋯ + p r for P n , G = { p 1 , … , p r } . T_{n,G}=D(P_{n,G}),\qquad\mathbf{u}_{n,G}=\mathbf{p}_1+\cdots+\mathbf{p}_r\quad\text{for }P_{n,G}=\{\mathbf{p}_1,\ldots,\mathbf{p}_r\}. T n , G = D ( P n , G ) , u n , G = p 1 + ⋯ + p r for P n , G = { p 1 , … , p r } .
For n = 1 n=1 n = 1 , put
P 1 , G = { a y u y v : ( u , v ) is an oriented edge of G } , P_{1,G}=\{a y_u y_v : (u,v)\text{ is an oriented edge of }G\}, P 1 , G = { a y u y v : ( u , v ) is an oriented edge of G } ,
T 1 , G = D ( P 1 , G ) , u 1 , G = p 1 + ⋯ + p r for P 1 , G = { p 1 , … , p r } . T_{1,G}=D(P_{1,G}),\qquad\mathbf{u}_{1,G}=\mathbf{p}_1+\cdots+\mathbf{p}_r\quad\text{for }P_{1,G}=\{\mathbf{p}_1,\ldots,\mathbf{p}_r\}. T 1 , G = D ( P 1 , G ) , u 1 , G = p 1 + ⋯ + p r for P 1 , G = { p 1 , … , p r } .
Proposition 4.3. For every n ≥ 1 n \ge1 n ≥ 1 , the finite semiring T n , G T_{n,G} T n , G belongs to W n + 1 W_{n+1} W n + 1 . For every finite simple graph H H H without isolated vertices and with at least one edge, there is an identity β n , H \beta_{n,H} β n , H that holds in W n W_n W n . It holds in T n , G T_{n,G} T n , G if and only if there is no graph homomorphism from H H H to G G G .
Proof. 1. Membership for n ≥ 2 n \ge2 n ≥ 2 . Put
w n = b 1 ⋯ b n b n ⋯ b 2 c w_n=b_1\cdots b_nb_n\cdots b_2c w n = b 1 ⋯ b n b n ⋯ b 2 c
where c c c is distinct from the b i b_i b i , and define the nonerasing morphism
φ ( b 1 ) = a 1 a 2 , φ ( b j ) = a j + 1 ( 2 ≤ j ≤ n ) , φ ( c ) = a 2 a 1 \varphi(b_1)=a_1a_2,\qquad\varphi(b_j)=a_{j+1}\ (2\le j\le n),\qquad\varphi(c)=a_2a_1 φ ( b 1 ) = a 1 a 2 , φ ( b j ) = a j + 1 ( 2 ≤ j ≤ n ) , φ ( c ) = a 2 a 1
The codewords have distinct initial letters, so φ \varphi φ is injective, and φ ( w n ) = m n + 1 \varphi(w_n)=m_{n+1} φ ( w n ) = m n + 1 . Moreover, every occurrence of a codeword in m n + 1 m_{n+1} m n + 1 starts and ends at a block boundary: a 1 a 2 a_1a_2 a 1 a 2 occurs only at the beginning, a 2 a 1 a_2a_1 a 2 a 1 only at the end, and the remaining codewords are single letters. Consequently, the word t t t is a factor of w n w_n w n if and only if φ ( t ) \varphi(t) φ ( t ) is a factor of m n + 1 m_{n+1} m n + 1 . In particular φ \varphi φ preserves factor and non-factor products, while injectivity preserves the flat addition. The map on factors, extended by ∞ ↦ ∞ \infty\mapsto\infty ∞ ↦ ∞ and then by 0 ↦ 0 0\mapsto0 0 ↦ 0 , gives embeddings
S ( w n ) ↪ A n + 1 , S ( w n ) 0 ↪ A ^ n + 1 . S(w_n)\hookrightarrow A_{n+1},\qquad S(w_n)^0\hookrightarrow\widehat{A}_{n+1}. S ( w n ) ↪ A n + 1 , S ( w n ) 0 ↪ A n + 1 .
We apply Proposition 4.2 with P = P n , G P=P_{n,G} P = P n , G and K = W n ∨ V ( S ( w n ) ) \mathcal{K}=W_n\vee V(S(w_n)) K = W n ∨ V ( S ( w n )) . Suppose that
K ⊨ q ⪯ u n , G ( q ∈ X + ) . \mathcal{K}\models\mathbf{q}\preceq\mathbf{u}_{n,G}\qquad(\mathbf{q}\in X^+). K ⊨ q ⪯ u n , G ( q ∈ X + ) .
We prove q ∈ P \mathbf{q}\in P q ∈ P by five restrictions.
(i) Variables. Fold the paired anchors to the corresponding letters of m n m_n m n and all vertex variables to its central letter. Each summand of u n , G \mathbf{u}_{n,G} u n , G then evaluates to the proper factor m n m_n m n . Assigning ∞ \infty ∞ to any extra variable of q \mathbf{q} q would violate absorption; hence
c ( q ) ⊆ c ( P ) . c(\mathbf{q})\subseteq c(P). c ( q ) ⊆ c ( P ) .
(ii) Edge support. Since D 2 ∈ W n D_2\in W_n D 2 ∈ W n , assign 1 1 1 precisely to the variables in c ( q ) c(\mathbf{q}) c ( q ) , and 0 0 0 to the others. The value of q \mathbf{q} q is 1 1 1 ; absorption forces some r ∈ P \mathbf{r}\in P r ∈ P to take value 1 1 1 . Thus
c ( r ) ⊆ c ( q ) , ∣ c ( r ) ∣ = h = 2 n . c(\mathbf{r})\subseteq c(\mathbf{q}),\qquad|c(\mathbf{r})|=h=2n. c ( r ) ⊆ c ( q ) , ∣ c ( r ) ∣ = h = 2 n .
Here r \mathbf{r} r contains the h − 2 h-2 h − 2 distinct anchors and the two distinct endpoints of an edge.
(iii) Length. Under the folding assignment in (i), absorption forces q \mathbf{q} q to have the same proper value m n m_n m n . Each variable has a one-letter image, so ℓ ( q ) = h \ell(\mathbf{q})=h ℓ ( q ) = h . Together with (ii), this says that q \mathbf{q} q is a linear word consisting of exactly the h h h letters of some r ∈ P \mathbf{r}\in P r ∈ P .
(iv) Internal positions. Equality of the folded word with m n m_n m n restricts every letter of q \mathbf{q} q to one of the two mirror positions associated with its letter of r \mathbf{r} r . The defining language P P P includes all exchanges of internal pairs 2 ≤ j < n 2\le j<n 2 ≤ j < n and both orientations of the central edge.
(v) Outer positions. In S ( w n ) S(w_n) S ( w n ) , assign the outer anchors b 1 , c b_1,c b 1 , c , each internal mirror pair b j b_j b j , and all vertex variables b n b_n b n . Every member of P P P evaluates to w n w_n w n . If the two outer anchors of q \mathbf{q} q were interchanged, its value would begin with c c c and end with b 1 b_1 b 1 , hence be ∞ \infty ∞ , contrary to the assumed absorption. Thus the outer pair is fixed, and (i)–(v) give q ∈ P \mathbf{q} \in P q ∈ P . Proposition 4.2 now yields
T n , G ∈ W n ∨ V ( S ( w n ) ) ⊆ W n + 1 . T_{n,G} \in W_n \vee V(S(\mathbf{w}_n)) \subseteq W_{n+1}. T n , G ∈ W n ∨ V ( S ( w n )) ⊆ W n + 1 .
*2. Separation for n ≥ 2. ∗ C h o o s e n \ge2.* Choose n ≥ 2. ∗ C h oose \mathbf{t}_H \in P_{n,H}$ and interchange its two outer letters to obtain q H \mathbf{q}_H q H . Define the absorption identity
β n , H : u n , H ≈ u n , H + q H . \beta_{n,H}: \qquad\mathbf{u}_{n,H} \approx\mathbf{u}_{n,H} + \mathbf{q}_H. β n , H : u n , H ≈ u n , H + q H .
We first show W n ⊨ β n , H W_n \models\beta_{n,H} W n ⊨ β n , H . Fix an evaluation in A ^ n \widehat{A}_n A n and let f f f be the value of u n , H \mathbf{u}_{n,H} u n , H . If f = ∞ f = \infty f = ∞ , absorption is immediate. If f = 0 f = 0 f = 0 , then the summand t H \mathbf{t}_H t H has value 0 0 0 , so one of its variables takes the new zero. Since c ( q H ) = c ( t H ) c(\mathbf{q}_H) = c(\mathbf{t}_H) c ( q H ) = c ( t H ) , the value of q H \mathbf{q}_H q H is also 0 0 0 . Finally, suppose f f f is a proper old factor. Then t H \mathbf{t}_H t H has the same proper value. Its h = 2 n h = 2n h = 2 n factors are all nonempty old factors, and their concatenation is a factor of m n \mathbf{m}_n m n of length at most 2 n 2n 2 n . Hence each factor is a single letter and their product is exactly m n \mathbf{m}_n m n . The outer letters coincide, so their interchange leaves the product unchanged. In all cases, β n , H \beta_{n,H} β n , H holds in A ^ n \widehat{A}_n A n .
We next prove that T n , G T_{n,G} T n , G fails β n , H \beta_{n,H} β n , H if and only if a graph homomorphism from H H H to G G G exists. If ψ : H → G \psi: H \to G ψ : H → G is a graph homomorphism, substitute singleton anchor letters and y v ↦ y ψ ( v ) y_v \mapsto y_{\psi(v)} y v ↦ y ψ ( v ) . Every summand of u n , H \mathbf{u}_{n,H} u n , H belongs to P n , G P_{n,G} P n , G , whereas q H \mathbf{q}_H q H with its reversed outer pair does not. Since all these words have length h h h , the empty-context pair belongs to the premise profile but not to the query profile. Thus T n , G ⊭ β n , H T_{n,G} \not\models\beta_{n,H} T n , G ⊨ β n , H .
Conversely, suppose β n , H \beta_{n,H} β n , H fails in D ( P n , G ) D(P_{n,G}) D ( P n , G ) . Lift the witnessing valuation to nonempty finite word sets. Because addition in the quotient is intersection of context profiles, there exist u , v ∈ X ∗ \mathbf{u}, \mathbf{v} \in X^* u , v ∈ X ∗ such that
u F v ⊆ P n , G , u Q v ⊈ P n , G , \mathbf{u}F\mathbf{v} \subseteq P_{n,G}, \qquad\mathbf{u}Q\mathbf{v} \not\subseteq P_{n,G}, u F v ⊆ P n , G , u Q v ⊆ P n , G ,
where F F F is the expanded premise language and Q Q Q is the expanded query language. Every word of P n , G P_{n,G} P n , G has length h h h , while each expanded premise monomial contains h h h nonempty word factors. Therefore u = v = ε \mathbf{u} = \mathbf{v} = \varepsilon u = v = ε , and every word in each substituted language occurring in a premise monomial has length one. Since H H H has no isolated vertices, this applies to every vertex variable. The positional restrictions in P n , G P_{n,G} P n , G must also be used. For each position 1 ≤ i ≤ h 1 \le i \le h 1 ≤ i ≤ h , let Λ i \Lambda_i Λ i be the set of letters that occur in position i i i among the words of P n , G P_{n,G} P n , G . For a variable z z z of the premise, let J z J_z J z be the set of positions occupied by z z z in some defining word of P n , H P_{n,H} P n , H . Since every word obtained by independently choosing one letter from each substituted language lies in P n , G P_{n,G} P n , G , the (nonempty) one-letter language L z L_z L z assigned to z z z satisfies
L z ⊆ ⋂ i ∈ J z Λ i . L_z \subseteq\bigcap_{i \in J_z} \Lambda_i. L z ⊆ i ∈ J z ⋂ Λ i .
The outer anchors therefore have their prescribed outer letters as their only possible images; internal anchors have images among the anchor letters permitted in their mirror-position pair. The two central positions admit only vertex letters of G G G . Every vertex variable of H H H occurs in an edge word, since H H H has no isolated vertices; hence its image language contains only vertex letters of G G G . The latter conclusion uses full-language containment as well as the positional restriction, not merely the length bound.
The language substituted for y u y_u y u thus consists of vertex letters of G G G . Let B w ≠ ∅ B_w \ne\varnothing B w = ∅ be their set of vertex indices. For each edge { w , w ′ } ∈ E ( H ) \{w,w'\} \in E(H) { w , w ′ } ∈ E ( H ) and every choice of b ∈ B w b \in B_w b ∈ B w and b ′ ∈ B w ′ b' \in B_{w'} b ′ ∈ B w ′ , choose these letters in the corresponding expanded premise monomial and choose any letters from the nonempty anchor languages. Full-language containment ensures that each resulting word belongs to P n , G P_{n,G} P n , G , not merely that one such choice belongs to it. Its two central letters therefore form an oriented edge of G G G . Both orientations of each source edge are included, so
B w × B w ′ ⊆ E o r ( G ) , E o r ( G ) = { ( z , z ′ ) : { z , z ′ } ∈ E ( G ) } . B_w \times B_{w'} \subseteq E^{\mathrm{or}}(G), \qquad E^{\mathrm{or}}(G)=\{(z,z'):\{z,z'\}\in E(G)\}. B w × B w ′ ⊆ E or ( G ) , E or ( G ) = {( z , z ′ ) : { z , z ′ } ∈ E ( G )} .
Choose ψ ( w ) ∈ B w \psi(w) \in B_w ψ ( w ) ∈ B w for every w ∈ V ( H ) w \in V(H) w ∈ V ( H ) . The displayed containment implies { ψ ( w ) , ψ ( w ′ ) } ∈ E ( G ) \{\psi(w),\psi(w')\} \in E(G) { ψ ( w ) , ψ ( w ′ )} ∈ E ( G ) whenever { w , w ′ } ∈ E ( H ) \{w,w'\} \in E(H) { w , w ′ } ∈ E ( H ) . Thus ψ : H → G \psi:H\to G ψ : H → G . The argument allows arbitrary nonempty finite-language substitutions, not merely singleton valuations.
3. Membership for n = 1 n=1 n = 1 . We apply Proposition 4.2 directly in W 2 \mathcal{W}_2 W 2 . Suppose
A ^ 2 ⊨ q ⪯ u 1 , G . \widehat{\mathcal{A}}_2 \models\mathbf{q} \preceq\mathbf{u}_{1,G}. A 2 ⊨ q ⪯ u 1 , G .
Assign the anchor a a a to the old letter a a a and every vertex variable to b b b . The premise then has proper value a b b abb abb . Assigning ∞ \infty ∞ to an extra variable of q \mathbf{q} q shows
c ( q ) ⊆ c ( P 1 , G ) . c(\mathbf{q}) \subseteq c(P_{1,G}). c ( q ) ⊆ c ( P 1 , G ) .
Next apply the homomorphism A ^ 2 → D 2 \widehat{\mathcal{A}}_2 \to D_2 A 2 → D 2 sending the new zero to 0 0 0 and each old element to 1 1 1 . Assign 1 1 1 precisely to c ( q ) c(\mathbf{q}) c ( q ) , and 0 0 0 elsewhere. Absorption forces some r = a y u y v ∈ P 1 , G \mathbf{r}=ay_uy_v \in P_{1,G} r = a y u y v ∈ P 1 , G to satisfy
c ( r ) ⊆ c ( q ) . c(\mathbf{r}) \subseteq c(\mathbf{q}). c ( r ) ⊆ c ( q ) .
Under the all-old assignment a ↦ a a \mapsto a a ↦ a , y v ↦ b y_v \mapsto b y v ↦ b , the value of q \mathbf{q} q must be a b b abb abb . Therefore q \mathbf{q} q has length three, contains exactly the distinct variables of r \mathbf{r} r , and begins with a a a . Since both orientations of every edge are in P 1 , G P_{1,G} P 1 , G , it follows that q ∈ P 1 , G \mathbf{q} \in P_{1,G} q ∈ P 1 , G ; hence T 1 , G ∈ W 2 T_{1,G} \in\mathcal{W}_2 T 1 , G ∈ W 2 .
4. Separation for n = 1 n=1 n = 1 . Choose an oriented edge ( u , v ) (u,v) ( u , v ) of H H H , let q H = y u a y v \mathbf{q}_H=y_uay_v q H = y u a y v , and define
β 1 , H : u 1 , H ≈ u 1 , H + q H . \beta_{1,H}:\qquad\mathbf{u}_{1,H}\approx\mathbf{u}_{1,H}+\mathbf{q}_H. β 1 , H : u 1 , H ≈ u 1 , H + q H .
This identity holds in W 1 \mathcal{W}_1 W 1 . When the premise is ∞ \infty ∞ , absorption is immediate. When it is 0 0 0 , the summand a y u y v ay_uy_v a y u y v and q H \mathbf{q}_H q H are both 0 0 0 . The premise cannot take a proper old value, since every product of three old elements in A ^ 1 \widehat{\mathcal{A}}_1 A 1 equals ∞ \infty ∞ .
A homomorphism ψ : H → G \psi:H\to G ψ : H → G gives a counterevaluation in D ( P 1 , G ) D(P_{1,G}) D ( P 1 , G ) by substituting singleton letters, since the premise has a nonempty context profile while q H \mathbf{q}_H q H , beginning with a vertex letter, has empty profile. Conversely, lift any counterevaluation to nonempty finite languages. The common length three of the defining words forces an empty context and one-letter factors in all expanded premise words. The first position of every word in P 1 , G P_{1,G} P 1 , G is a a a , whereas the other two positions contain only vertex letters; thus the anchor language consists only of a a a . Since every vertex of H H H occurs in an oriented premise word, its one-letter language consists entirely of vertex letters of G G G . For each source edge and every choice of one letter from either endpoint language, the corresponding expanded premise word lies in P 1 , G P_{1,G} P 1 , G . Consequently the Cartesian product of the two endpoint index sets is contained in E o r ( G ) E^{\mathrm{or}}(G) E or ( G ) , not merely one selected pair. Choosing one index from each nonempty vertex language defines the required homomorphism H → G H\to G H → G . This proves both statements when n = 1 n=1 n = 1 .
Continuum intervals
Theorem 4.4 (Consecutive mirror-word intervals). For every n ≥ 1 n \ge1 n ≥ 1 , the interval [ W n , W n + 1 ] [W_n,W_{n+1}] [ W n , W n + 1 ] has cardinality 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 and contains an order-embedded copy of ( P ( N ) , ⊆ ) (\mathcal{P}(\mathbb{N}),\subseteq) ( P ( N ) , ⊆ ) .
Proof. Choose finite simple graphs G 0 , G 1 , … G_0,G_1,\ldots G 0 , G 1 , … without isolated vertices such that both their chromatic numbers and their odd girths strictly increase, with all chromatic numbers at least three and all odd girths at least five. Their existence follows from Erdős’s theorem [4 ] . The graphs form an antichain for graph homomorphisms: a homomorphism cannot increase chromatic number, and it cannot map an odd cycle into a graph of larger odd girth.
For J ⊆ N J \subseteq\mathbb{N} J ⊆ N set
K n , J = W n ∨ ⋁ j ∈ J V ( T n , G j ) . \mathcal{K}_{n,J}=W_n\vee\bigvee_{j\in J}V(T_{n,G_j}). K n , J = W n ∨ j ∈ J ⋁ V ( T n , G j ) .
By Proposition 4.3 ,
W n ⊆ K n , J ⊆ W n + 1 . W_n\subseteq\mathcal{K}_{n,J}\subseteq W_{n+1}. W n ⊆ K n , J ⊆ W n + 1 .
The identity β n , G i \beta_{n,G_i} β n , G i holds in K n , J \mathcal{K}_{n,J} K n , J if and only if i ∉ J i\notin J i ∈ / J . Consequently, for subsets J , J ′ ⊆ N J,J'\subseteq\mathbb{N} J , J ′ ⊆ N , the inclusion J ⊆ J ′ J\subseteq J' J ⊆ J ′ holds if and only if K n , J ⊆ K n , J ′ \mathcal{K}_{n,J}\subseteq\mathcal{K}_{n,J'} K n , J ⊆ K n , J ′ . Thus J ↦ K n , J J\mapsto\mathcal{K}_{n,J} J ↦ K n , J is an order embedding of ( P ( N ) , ⊆ ) (\mathcal{P}(\mathbb{N}),\subseteq) ( P ( N ) , ⊆ ) into the interval. This gives the lower bound 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 . The binary semiring signature has countably many identities, hence at most 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 equational theories, giving the matching upper bound. □
Zero-extension intervals via cyclic semirings
We apply the cyclic semiring family E p E_p E p and separating identities of Shao–Gao [19 Sections 10–11] , rather than repeating a second graph construction. Their letter notation for linear words is kept distinct from our mirror-word notation. For every integer p ≥ 2 p\ge2 p ≥ 2 , with indices taken modulo p p p , put
c p = ∑ i ∈ Z / p Z ( x i y i z 0 + x i y i + 1 z 1 ) , q p = x 0 y 0 z 1 , c_p=\sum_{i\in\mathbb{Z}/p\mathbb{Z}}(x_i y_i z_0+x_i y_{i+1}z_1),\qquad q_p=x_0y_0z_1, c p = i ∈ Z / p Z ∑ ( x i y i z 0 + x i y i + 1 z 1 ) , q p = x 0 y 0 z 1 ,
and write
ε p : c p ≈ c p + q p . \varepsilon_p:\qquad c_p\approx c_p+q_p. ε p : c p ≈ c p + q p .
By Shao–Gao [19 Proposition 10.2] , for m , p ≥ 2 m,p\ge2 m , p ≥ 2 the semiring E m E_m E m satisfies ε p \varepsilon_p ε p if and only if m ∤ p m\nmid p m ∤ p .
Lemma 4.5 (Endpoint verification). For every n ≥ 2 n\ge2 n ≥ 2 and p ≥ 2 p\ge2 p ≥ 2 ,
E p ∈ W n , A n ⊨ ε p . E_p\in W_n,\qquad A_n\models\varepsilon_p. E p ∈ W n , A n ⊨ ε p .
Proof. We begin with E p ∈ W n E_p\in W_n E p ∈ W n . This requires checking the mirror-word endpoint rather than directly transferring the linear-word result. The three-word permutation identities
x y z ≈ y x z , x y z ≈ x z y , x y z ≈ z y x xyz\approx yxz,\qquad xyz\approx xzy,\qquad xyz\approx zyx x y z ≈ y x z , x y z ≈ x z y , x y z ≈ z y x
all fail in A ^ 2 = S ( a b b a ) 0 \widehat{A}_2=S(abba)^0 A 2 = S ( abba ) 0 . Indeed, with ( x , y , z ) = ( a , b , b ) (x,y,z)=(a,b,b) ( x , y , z ) = ( a , b , b ) , the nonabsorbing product a b b abb abb differs from b a b bab bab and b b a bba bba , while with ( x , y , z ) = ( b , b , a ) (x,y,z)=(b,b,a) ( x , y , z ) = ( b , b , a ) the nonabsorbing product b b a bba bba differs from b a b bab bab . Thus Shao–Gao [19 Theorem 23.2] yields V ( S ( a b c ) ) ⊆ W 2 \mathsf{V}(S(abc))\subseteq W_2 V ( S ( ab c )) ⊆ W 2 for distinct letters a , b , c a,b,c a , b , c . Their Theorem 22.2 then gives
V ( S ( a b c ) 0 ) ⊆ W 2 . \mathsf{V}(S(abc)^0)\subseteq W_2. V ( S ( ab c ) 0 ) ⊆ W 2 .
Their cyclic construction places E p ∈ V ( R 3 ) ⊆ V ( S ( a b c ) 0 ) E_p\in\mathsf{V}(R_3)\subseteq\mathsf{V}(S(abc)^0) E p ∈ V ( R 3 ) ⊆ V ( S ( ab c ) 0 ) (see [19 Proposition 10.1 and Section 5] ). Consequently E p ∈ W 2 ⊆ W n E_p\in W_2\subseteq W_n E p ∈ W 2 ⊆ W n , where the last inclusion follows from Proposition 4.1 . We next verify A n ⊨ ε p A_n \models\varepsilon_p A n ⊨ ε p . Evaluate c p c_p c p in A n = S ( m n ) A_n = S(m_n) A n = S ( m n ) . When its value is ∞ \infty ∞ , the absorption ε p \varepsilon_p ε p is automatic. Otherwise all its cubic summands have one and the same value, a nonempty factor of m n m_n m n . In particular, the assigned values U i , V i , Z 0 , Z 1 U_i,V_i,Z_0,Z_1 U i , V i , Z 0 , Z 1 of x i , y i , z 0 , z 1 x_i,y_i,z_0,z_1 x i , y i , z 0 , z 1 are nonempty words, and
U i V i Z 0 = U i V i + 1 Z 1 ( i ∈ Z / p Z ) . U_iV_iZ_0 = U_iV_{i+1}Z_1 \qquad(i \in\mathbb{Z}/p\mathbb{Z}). U i V i Z 0 = U i V i + 1 Z 1 ( i ∈ Z / p Z ) .
Taking word lengths gives ∣ V i + 1 ∣ − ∣ V i ∣ = ∣ Z 0 ∣ − ∣ Z 1 ∣ |V_{i+1}| - |V_i| = |Z_0| - |Z_1| ∣ V i + 1 ∣ − ∣ V i ∣ = ∣ Z 0 ∣ − ∣ Z 1 ∣ . Summing around the cycle shows ∣ Z 0 ∣ = ∣ Z 1 ∣ |Z_0| = |Z_1| ∣ Z 0 ∣ = ∣ Z 1 ∣ and hence ∣ V i ∣ = ∣ V i + 1 ∣ |V_i| = |V_{i+1}| ∣ V i ∣ = ∣ V i + 1 ∣ for all i i i . Cancellation in the free semigroup, followed by comparison of these equal-length prefixes and suffixes, gives V i = V i + 1 V_i = V_{i+1} V i = V i + 1 and Z 0 = Z 1 Z_0 = Z_1 Z 0 = Z 1 . It follows that U 0 V 0 Z 1 = U 0 V 0 Z 0 U_0V_0Z_1 = U_0V_0Z_0 U 0 V 0 Z 1 = U 0 V 0 Z 0 , which is an existing summand value of c p c_p c p . Thus A n ⊨ ε p A_n \models\varepsilon_p A n ⊨ ε p . □
Corollary 4.6 (Zero-extension continuum intervals). For every n ≥ 2 n \ge2 n ≥ 2 , the interval [ V n , W n ] [\mathcal{V}_n,\mathcal{W}_n] [ V n , W n ] has cardinality 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 and contains an order-embedded copy of ( P ( N ) , ⊆ ) (\mathcal{P}(\mathbb{N}),\subseteq) ( P ( N ) , ⊆ ) .
Proof. For each set J J J of prime numbers, define
J n , J = V n ∨ ⋁ p ∈ J V ( E p ) . \mathcal{J}_{n,J}=\mathcal{V}_n \vee\bigvee_{p\in J} V(E_p). J n , J = V n ∨ p ∈ J ⋁ V ( E p ) .
By Lemma 4.5 and A n ≤ A ^ n A_n \le\widehat{A}_n A n ≤ A n , each J n , J \mathcal{J}_{n,J} J n , J belongs to [ V n , W n ] [\mathcal{V}_n,\mathcal{W}_n] [ V n , W n ] . For every prime p p p , the same lemma and Shao–Gao [19 Proposition 10.2] show that the identity ε p \varepsilon_p ε p holds in J n , J \mathcal{J}_{n,J} J n , J if and only if p ∉ J p \notin J p ∈ / J . Hence J ↦ J n , J J \mapsto\mathcal{J}_{n,J} J ↦ J n , J is an order embedding. The power set of the primes has cardinality 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 , and the general countable-signature bound gives the reverse inequality. □
Corollary 4.7. For every n ≥ 2 n \ge2 n ≥ 2 , the interval [ V n , W ∞ ] [\mathcal{V}_n,\mathcal{W}_\infty] [ V n , W ∞ ] has cardinality 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 and contains a chain and an antichain of that cardinality.
Proof. The interval [ W n , W n + 1 ] [\mathcal{W}_n,\mathcal{W}_{n+1}] [ W n , W n + 1 ] is contained in [ V n , W ∞ ] [\mathcal{V}_n,\mathcal{W}_\infty] [ V n , W ∞ ] . Apply Theorem 4.4 and the countable-signature upper bound. □
Corollary 4.8. The subvariety lattice of W ∞ \mathcal{W}_\infty W ∞ has cardinality 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 .
Proof. The interval [ W 2 , W 3 ] [\mathcal{W}_2,\mathcal{W}_3] [ W 2 , W 3 ] is contained in the subvariety lattice of W ∞ \mathcal{W}_\infty W ∞ ; the theorem gives the lower bound and the countable-signature argument gives the upper bound. □
Local finiteness
Proposition 4.9. The variety W ∞ \mathcal{W}_\infty W ∞ is locally finite.
Proof. Fix an r r r -element variable set X r X_r X r . Only finitely many words over X r X_r X r contain each variable at most twice. For any other word w w w put D = c ( w ) D=c(w) D = c ( w ) . In every A ^ n \widehat{A}_n A n we have
w ≈ ∏ x ∈ D x 3 , w \approx\prod_{x\in D} x^3, w ≈ x ∈ D ∏ x 3 ,
with the order of factors on the right fixed arbitrarily. Indeed, if some variable in D D D takes the new value 0 0 0 , both sides are 0 0 0 ; otherwise both are ∞ \infty ∞ . Thus every term over X r X_r X r is equivalent to a nonempty sum of words from a finite set: the words in which each variable occurs at most twice, together with one word ∏ x ∈ D x 3 \prod_{x\in D}x^3 ∏ x ∈ D x 3 for each nonempty D ⊆ X r D\subseteq X_r D ⊆ X r . Idempotence of addition now implies that the r r r -generated free semiring of W ∞ \mathcal{W}_\infty W ∞ is finite. □
The unique limit subvariety of W 1 W_1 W 1
Identities and normal forms in the four-element variety
Throughout this section, a finite nonempty set of words P = { p 1 , … , p r } P=\{p_1,\ldots,p_r\} P = { p 1 , … , p r } is represented by the ordinary ai-semiring term p 1 + ⋯ + p r p_1+\cdots+p_r p 1 + ⋯ + p r , exactly as in Section 2. We never use an empty additive term.
By Zhao–Wu [30 ] , the variety W 1 = V ( A ^ 1 ) W_1=V(\widehat{A}_1) W 1 = V ( A 1 ) , where A ^ 1 ≅ S c ( a 2 ) 0 \widehat{A}_1\cong S_c(a^2)^0 A 1 ≅ S c ( a 2 ) 0 , is finitely based. We now give a self-contained completeness proof for the following six-identity basis in the binary ai-semiring signature. The proof uses the absorption criterion in Proposition 2.3 and the normal forms below.
Set b = a 2 b=a^2 b = a 2 . The operations on A ^ 1 = { 0 , a , b , ∞ } \widehat{A}_1=\{0,a,b,\infty\} A 1 = { 0 , a , b , ∞ } are
Table 3.
Table 4.
Proposition 5.1 (A six-identity equational basis). Relative to the ai-semiring axioms, the following six identities constitute an equational basis of W 1 W_1 W 1 :
x y ≈ y x , (3) xy \approx yx, \tag*{(3)} x y ≈ y x , (3) x y z ≈ x 3 y z , (4) xyz \approx x^3yz, \tag*{(4)} x y z ≈ x 3 y z , (4) x + x 2 ≈ x 3 , (5) x+x^2 \approx x^3, \tag*{(5)} x + x 2 ≈ x 3 , (5) x + x y ≈ x + x y + x 3 y , (6) x+xy \approx x+xy+x^3y, \tag*{(6)} x + x y ≈ x + x y + x 3 y , (6) x 3 + x y ≈ x 3 , (7) x^3+xy \approx x^3, \tag*{(7)} x 3 + x y ≈ x 3 , (7) x 2 + y 2 ≈ x 2 + y 2 + x y . (8) x^2+y^2 \approx x^2+y^2+xy. \tag*{(8)} x 2 + y 2 ≈ x 2 + y 2 + x y . (8)
Each identity is verified directly from the four-element Cayley tables of A ^ 1 \widehat{A}_1 A 1 . We derive the required word normal forms before completing the proof of Proposition 5.1.
First, we derive two additional identities from the six identities above. By (4) and additive idempotence,
x 2 + x 3 ≈ x 2 + ( x + x 2 ) ≈ x + x 2 ≈ x 3 . x^2+x^3 \approx x^2+(x+x^2)\approx x+x^2\approx x^3. x 2 + x 3 ≈ x 2 + ( x + x 2 ) ≈ x + x 2 ≈ x 3 .
Multiplying (4) by x x x and distributing gives x 3 + x 3 ≈ x 4 x^3+x^3\approx x^4 x 3 + x 3 ≈ x 4 . Hence
x 3 ≈ x 4 . (9) x^3\approx x^4. \tag*{(9)} x 3 ≈ x 4 . (9)
Using (3) with ( x , y , z ) = ( x , x , t ) (x,y,z)=(x,x,t) ( x , y , z ) = ( x , x , t ) and then (8), we obtain
x 2 t ≈ x 4 t ≈ x 3 t . (10) x^2t\approx x^4t\approx x^3t. \tag*{(10)} x 2 t ≈ x 4 t ≈ x 3 t . (10)
By commutativity, these relations give
x 2 y ≈ x 2 y 3 by (3) with ( y , x , x ) , ≈ x 3 y 3 by (9) with t = y 3 , ≈ x 3 y 2 by (9) with x , y interchanged, in reverse, ≈ x y 2 by (3) with ( x , y , y ) , in reverse. \begin{aligned}
x^2y&\approx x^2y^3 &&\text{by (3) with }(y,x,x)\text{,}\\
&\approx x^3y^3 &&\text{by (9) with }t=y^3\text{,}\\
&\approx x^3y^2 &&\text{by (9) with }x,y\text{ interchanged, in reverse,}\\
&\approx xy^2 &&\text{by (3) with }(x,y,y)\text{, in reverse.}
\end{aligned} x 2 y ≈ x 2 y 3 ≈ x 3 y 3 ≈ x 3 y 2 ≈ x y 2 by (3) with ( y , x , x ) , by (9) with t = y 3 , by (9) with x , y interchanged, in reverse, by (3) with ( x , y , y ) , in reverse.
Thus we may also use
x 2 y ≈ x y 2 . (11) x^2y\approx xy^2. \tag*{(11)} x 2 y ≈ x y 2 . (11)
The preceding reductions yield a convenient normal form. Fix a total order on the variable set.
Lemma 5.2. Modulo (2), (3), (8), and (10), every word is equivalent either to a linear word x x x , to a quadratic word x 2 x^2 x 2 or x y xy x y with x < y x < y x < y , or to
x 3 ∏ z ∈ c ( w ) ∖ { x } z x^3 \prod_{z \in c(\mathrm{w}) \setminus\{x\}} z x 3 z ∈ c ( w ) ∖ { x } ∏ z where ℓ ( w ) ≥ 3 \ell(\mathrm{w}) \ge3 ℓ ( w ) ≥ 3 and x x x is the least variable in c ( w ) c(\mathrm{w}) c ( w ) . An empty final product is omitted.
Proof. By commutativity, order the letters of w \mathrm{w} w . The identities (3) (with two equal factors) and (8) give
x 2 y ≈ x 3 y , x k ≈ x 3 ( k ≥ 3 ) . x^2y \approx x^3y,\qquad x^k \approx x^3\quad(k \ge3). x 2 y ≈ x 3 y , x k ≈ x 3 ( k ≥ 3 ) . Thus any word of length at least three has a cubic pivot: use a repeated letter if one exists, and otherwise apply (3) to a square-free word. For each other letter, (10) gives
x 3 y 2 ≈ x 4 y ≈ x 3 y , x^3y^2 \approx x^4y \approx x^3y, x 3 y 2 ≈ x 4 y ≈ x 3 y , so its multiplicity reduces to one. Finally,
x 3 y ≈ x 2 y 2 ≈ x y 3 x^3y \approx x^2y^2 \approx xy^3 x 3 y ≈ x 2 y 2 ≈ x y 3 (multiply (10) by x x x and by y y y ) transfers the pivot to the least letter of c ( w ) c(\mathrm{w}) c ( w ) . The degree-one and degree-two forms require no reduction. □ \square □
Completion of the proof of Proposition 5.1. It remains to prove completeness. We work with normal forms from Lemma 5.2. For a nonempty finite variable set C C C , let c c c be its least element and set
t C = c 3 ∏ z ∈ C ∖ { c } z . t_C = c^3 \prod_{z \in C \setminus\{c\}} z. t C = c 3 z ∈ C ∖ { c } ∏ z .
As usual, the final product is omitted when C = { c } C = \{c\} C = { c } . The preliminary identities below hold modulo the six displayed identities.
Absorption consequences. First, (4) and idempotence give c 3 + c ≈ c 3 c^3 + c \approx c^3 c 3 + c ≈ c 3 . For every word m \mathrm{m} m and every nonempty D ⊆ c ( m ) D \subseteq c(\mathrm{m}) D ⊆ c ( m ) , we claim
t D + m ≈ t D . t_D + \mathrm{m} \approx t_D. t D + m ≈ t D .
Indeed, if d d d is the least variable of D D D and v \mathrm{v} v lists once each variable of D ∖ { d } D \setminus\{d\} D ∖ { d } , commutativity permits m = d v r \mathrm{m} = d\mathrm{v}\mathrm{r} m = d vr for some possibly empty word r \mathrm{r} r . Thus the claim follows by multiplying d 3 + d r ≈ d 3 d^3 + d\mathrm{r} \approx d^3 d 3 + d r ≈ d 3 by v \mathrm{v} v ; when r \mathrm{r} r is omitted we use d 3 + d ≈ d 3 d^3 + d \approx d^3 d 3 + d ≈ d 3 , and otherwise we use (6) with y = r y = \mathrm{r} y = r . No multiplicative identity is introduced by an omitted word.
Second, if a term u \mathrm{u} u has a linear summand x x x and also a quadratic summand p \mathrm{p} p containing x x x , then
u + t c ( p ) ≈ u . \mathrm{u} + t_{c(\mathrm{p})} \approx\mathrm{u}. u + t c ( p ) ≈ u .
For p = x 2 \mathrm{p} = x^2 p = x 2 , apply (4); for p = x y \mathrm{p} = xy p = x y with x ≠ y x \ne y x = y , apply (5) and normalize the added cubic word using Lemma 5.2. All remaining summands of u \mathrm{u} u are unchanged.
Exhaustion of valid normal-word absorptions. Let u \mathrm{u} u be a nonempty term whose summands are normal words, and let q \mathrm{q} q be a normal word. The case q ∈ u \mathrm{q} \in\mathrm{u} q ∈ u is immediate, so we assume q ∉ u q \notin\mathbf{u} q ∈ / u . By the zero-adjunction criterion (Proposition 2.3 ), this absorption is valid in A ^ 1 \widehat{A}_1 A 1 precisely when
D q ( u ) ≠ ∅ , S ( a 2 ) ⊨ q ⪯ D q ( u ) . D_q(\mathbf{u}) \ne\varnothing,\qquad S(a^2) \models q \preceq D_q(\mathbf{u}). D q ( u ) = ∅ , S ( a 2 ) ⊨ q ⪯ D q ( u ) .
We now describe all such absorptions. In the following cases, the mentioned summands belong to the restricted support D q ( u ) D_q(\mathbf{u}) D q ( u ) , and the necessity arguments use the old flat semiring S ( a 2 ) = { a , b , ∞ } S(a^2)=\{a,b,\infty\} S ( a 2 ) = { a , b , ∞ } , with b = a 2 b=a^2 b = a 2 .
Case 1: q = x \mathbf{q}=x q = x . The restricted support can contain only x x x , x 2 x^2 x 2 , x 3 x^3 x 3 . Validity forces x x x or x 3 x^3 x 3 to occur. Otherwise the only possible surviving word is x 2 x^2 x 2 ; assigning x = a x=a x = a gives the source value b b b and the target value a a a , contradicting absorption. Conversely, x x x is already absorbed by itself, and x 3 + x ≈ x 3 x^3+x\approx x^3 x 3 + x ≈ x 3 handles the other possibility.
Case 2: q = x 2 \mathbf{q}=x^2 q = x 2 . Again the restricted support consists of words among x x x , x 2 x^2 x 2 , x 3 x^3 x 3 . Validity forces x 2 x^2 x 2 or x 3 x^3 x 3 to occur: otherwise evaluation at x = a x=a x = a separates the source x x x from the target b b b . Conversely, idempotence handles x 2 x^2 x 2 , and x 3 + x 2 ≈ x 3 x^3+x^2\approx x^3 x 3 + x 2 ≈ x 3 follows from the already derived relation x 2 + x 3 ≈ x 3 x^2+x^3\approx x^3 x 2 + x 3 ≈ x 3 .
Case 3: q = x y \mathbf{q}=xy q = x y , x ≠ y x\ne y x = y . The valid cases are precisely the following: x y xy x y already occurs; both x 2 x^2 x 2 and y 2 y^2 y 2 occur; a high-degree normal word t D t_D t D with ∅ ≠ D ⊆ { x , y } \varnothing\ne D\subseteq\{x,y\} ∅ = D ⊆ { x , y } occurs; or a linear summand also occurs in one of the quadratic summands. These cases are derivable, respectively, by idempotence, (7), the high-degree absorption proved above, or first the linear–quadratic overlap reduction proved above and then the high-degree absorption proved above. To prove necessity, assume that none occurs. Then the restricted support has no high-degree word, has no x y xy x y , has at most one of x 2 , y 2 x^2,y^2 x 2 , y 2 , and has no linear–quadratic overlap. With no square, the assignment x = y = a x=y=a x = y = a makes the source either 0 0 0 (if the restriction is empty) or a a a , while the target has value b b b . If x 2 x^2 x 2 is the sole square, the only possible linear word is y y y ; take x = a x=a x = a and y = b y=b y = b . The source has value b b b and the target x y xy x y has value ∞ \infty ∞ . The argument with y 2 y^2 y 2 is symmetric. Thus the absorption fails unless one of the stated alternatives holds.
Case 4: q = t C \mathbf{q}=t_C q = t C for nonempty C C C . The absorption is valid precisely when the restricted source D q ( u ) D_q(\mathbf{u}) D q ( u ) contains a high-degree normal word, or when one of its linear variables also occurs in a quadratic summand. For sufficiency, a high-degree word must be t D t_D t D with ∅ ≠ D ⊆ C \varnothing\ne D\subseteq C ∅ = D ⊆ C , and the high-degree absorption proved above absorbs q \mathbf{q} q . A linear–quadratic overlap first gives such a t D t_D t D via the linear–quadratic overlap reduction proved above. For necessity, suppose neither condition holds. Let L L L be the set of variables of linear summands of D q ( u ) D_q(\mathbf{u}) D q ( u ) , and let Q Q Q be the set of variables occurring in its quadratic summands; these sets are disjoint. Assign b b b to the variables in L L L , and a a a to the variables of C ∖ L C\setminus L C ∖ L . Every surviving source word then has value b b b (or the restricted source is empty), while t C t_C t C has value ∞ \infty ∞ . Hence the required absorption fails in A ^ 1 \widehat{A}_1 A 1 .
Completion. Every term is equivalent, using Lemma 5.2, to a nonempty sum of the four kinds of normal words treated above. Every valid absorption of one normal word by such a term is covered by one of the four cases, and each case shown to be valid has been derived from the six identities. Finally, let u ≈ v \mathbf{u}\approx\mathbf{v} u ≈ v be an arbitrary identity of A ^ 1 \widehat{A}_1 A 1 . Normalize the word summands of both sides. For each word p \mathbf{p} p of u \mathbf{u} u , derive p ⪯ v \mathbf{p}\preceq\mathbf{v} p ⪯ v ; for each word q \mathbf{q} q of v \mathbf{v} v , derive q ⪯ u \mathbf{q}\preceq\mathbf{u} q ⪯ u . Adding the finitely many absorbed words one at a time then gives
u ≈ u + v ≈ v . \mathbf{u}\approx\mathbf{u}+\mathbf{v}\approx\mathbf{v}. u ≈ u + v ≈ v .
Thus every identity of A ^ 1 \widehat{A}_1 A 1 follows from the six displayed identities and the ai-semiring axioms. This proves that they form an equational basis of W 1 W_1 W 1 . □
The position of S R 6 SR_6 S R 6 in W 1 W_1 W 1
Proposition 5.3. The variety V ( S R 6 ) V(SR_6) V ( S R 6 ) is a subvariety of W 1 W_1 W 1 .
Proof. Shao–Gao [19 Proposition 25.3] prove that V ( S R 6 ) ⊆ V ( S ( a 2 ) 0 ) V(SR_6) \subseteq V(S(a^2)^0) V ( S R 6 ) ⊆ V ( S ( a 2 ) 0 ) . Since A ^ 1 ≅ S c ( a 2 ) 0 ≅ S ( a 2 ) 0 \widehat{A}_1 \cong S_c(a^2)^0 \cong S(a^2)^0 A 1 ≅ S c ( a 2 ) 0 ≅ S ( a 2 ) 0 , the asserted inclusion follows. □
The limit subvariety and the hereditary finite-basis reduction
By Lyu–Ren–Yue [13 ] , V ( S R 6 ) V(SR_6) V ( S R 6 ) is a limit variety. Yue [27 Corollary 3.35] identifies V ( S R 6 ) V(SR_6) V ( S R 6 ) and V ( S c ( a b c ) ) V(S_c(abc)) V ( S c ( ab c )) as the only limit subvarieties of V ( S 9 0 ) V(S^0_9) V ( S 9 0 ) . The arguments below use the valid identities of Proposition 5.1 and the resulting normal forms in Lemma 5.2.
We use the semiring-inequality notation introduced in Section 2. A variety is hereditarily finitely based if all its subvarieties are finitely based. The following theorem yields the asserted uniqueness.
Theorem 5.4. Let K ⊆ W 1 K \subseteq W_1 K ⊆ W 1 be a subvariety such that V ( S R 6 ) ⊈ K V(SR_6) \nsubseteq K V ( S R 6 ) ⊈ K . Then K K K is hereditarily finitely based. Consequently, V ( S R 6 ) V(SR_6) V ( S R 6 ) is the unique limit subvariety of W 1 W_1 W 1 .
The reduction will be formulated using four additional identities:
λ : x + x y ≈ x y , σ : x y ≈ x 2 + y 2 , ρ : x y ≈ x 2 y , η : x 1 x 2 + x 2 x 3 + x 3 x 4 ≈ x 1 x 2 + x 2 x 3 + x 3 x 4 + x 1 x 4 . \begin{aligned}
\lambda&: x+xy \approx xy,\\
\sigma&: xy \approx x^2+y^2,\\
\rho&: xy \approx x^2y,\\
\eta&: x_1x_2+x_2x_3+x_3x_4 \approx x_1x_2+x_2x_3+x_3x_4+x_1x_4.
\end{aligned} λ σ ρ η : x + x y ≈ x y , : x y ≈ x 2 + y 2 , : x y ≈ x 2 y , : x 1 x 2 + x 2 x 3 + x 3 x 4 ≈ x 1 x 2 + x 2 x 3 + x 3 x 4 + x 1 x 4 .
Denote by W 1 [ ε ] W_1[\varepsilon] W 1 [ ε ] the subvariety of W 1 W_1 W 1 defined by an additional identity ε \varepsilon ε .
Proposition 5.5. The varieties W 1 [ λ ] W_1[\lambda] W 1 [ λ ] , W 1 [ σ ] W_1[\sigma] W 1 [ σ ] , and W 1 [ ρ ] W_1[\rho] W 1 [ ρ ] are hereditarily finitely based. More precisely,
W 1 [ λ ] = V ( E n i l ) , W 1 [ σ ] = V 1 , W 1 [ ρ ] = V ( R c h ) , W_1[\lambda] = V(E_{\mathrm{nil}}), \qquad W_1[\sigma] = V_1, \qquad W_1[\rho] = V(R_{\mathrm{ch}}), W 1 [ λ ] = V ( E nil ) , W 1 [ σ ] = V 1 , W 1 [ ρ ] = V ( R ch ) , where E n i l = { e , ∞ } E_{\mathrm{nil}} = \{e,\infty\} E nil = { e , ∞ } has e + ∞ = ∞ e+\infty=\infty e + ∞ = ∞ and all products ∞ \infty ∞ , and R c h = { 0 , e , ∞ } R_{\mathrm{ch}} = \{0,e,\infty\} R ch = { 0 , e , ∞ } is the chain 0 < e < ∞ 0<e<\infty 0 < e < ∞ with 0 0 0 multiplicatively absorbing and all products of elements of { e , ∞ } \{e,\infty\} { e , ∞ } equal to ∞ \infty ∞ .
Proof. 1. The λ \lambda λ -branch. Suppose first that λ \lambda λ holds in W 1 W_1 W 1 . Substituting y = x y=x y = x into λ \lambda λ and using (4) gives x 2 ≈ x 3 x^2 \approx x^3 x 2 ≈ x 3 . Multiplication of λ \lambda λ by x x x and (6) now yield
x 2 + x 2 y ≈ x 2 y , x 2 + x 2 y ≈ x 2 ; x^2+x^2y \approx x^2y,\qquad x^2+x^2y \approx x^2; x 2 + x 2 y ≈ x 2 y , x 2 + x 2 y ≈ x 2 ;
thus x 2 y ≈ x 2 x^2y \approx x^2 x 2 y ≈ x 2 . By (10) and commutativity,
x 2 ≈ x 2 y ≈ x y 2 ≈ y 2 . x^2 \approx x^2y \approx xy^2 \approx y^2. x 2 ≈ x 2 y ≈ x y 2 ≈ y 2 .
Denote this common square term by c c c . Equations (4)–(6) then give x + c ≈ c x+c \approx c x + c ≈ c , c x ≈ c cx \approx c c x ≈ c , and x + x y ≈ c x+xy \approx c x + x y ≈ c . Using λ \lambda λ we obtain x y ≈ c xy \approx c x y ≈ c . Consequently the variety is that of join semilattices with a greatest element which is the value of every product. Such a semilattice is separated by homomorphisms into E n i l E_{\mathrm{nil}} E nil : for a a ≰ b a \not\leq b a ≤ b , the map taking elements below b b b to e e e and the remaining elements to ∞ \infty ∞ is a semilattice homomorphism (and preserves multiplication). Hence W 1 [ λ ] = V ( E n i l ) W_1[\lambda]=V(E_{\mathrm{nil}}) W 1 [ λ ] = V ( E nil ) . Every nontrivial subvariety contains E n i l E_{\mathrm{nil}} E nil , so this variety has only two subvarieties.
The σ \sigma σ -branch
Equation (8) shows that σ \sigma σ is equivalent over W 1 W_1 W 1 to x 2 + x y ≈ x y x^2+xy\approx xy x 2 + x y ≈ x y . In W 1 [ σ ] W_1[\sigma] W 1 [ σ ] ,
x 3 + y 3 ≈ x 2 y 2 ≈ x 3 y ⪯ x 3 . x^3+y^3\approx x^2y^2\approx x^3y\preceq x^3. x 3 + y 3 ≈ x 2 y 2 ≈ x 3 y ⪯ x 3 .
Here the first equality follows by applying σ \sigma σ to x 2 , y 2 x^2,y^2 x 2 , y 2 and using (9) , the second from (11) , and the absorption from (7) , with y y y replaced by x 2 y x^2y x 2 y . Interchanging x , y x,y x , y gives x 3 ≈ y 3 x^3\approx y^3 x 3 ≈ y 3 . Let c \mathbf{c} c denote this common term. By (5) , x + c ≈ c x+\mathbf{c}\approx\mathbf{c} x + c ≈ c ; (7) makes c \mathbf{c} c absorb every quadratic term. Every term is therefore reducible either to c \mathbf{c} c or to
F ( L , Q ) = p 1 + ⋯ + p r , \mathbf{F}(L,Q)=\mathbf{p}_1+\cdots+\mathbf{p}_r, F ( L , Q ) = p 1 + ⋯ + p r ,
{ p 1 , … , p r } = L ∪ { y 2 : y ∈ Q } , \{\mathbf{p}_1,\ldots,\mathbf{p}_r\}=L\cup\{y^2:y\in Q\}, { p 1 , … , p r } = L ∪ { y 2 : y ∈ Q } ,
L ∩ Q = ∅ , L ∪ Q ≠ ∅ . (12) L\cap Q=\varnothing,\qquad L\cup Q\ne\varnothing. \tag*{(12)} L ∩ Q = ∅ , L ∪ Q = ∅ . (12)
Indeed, σ \sigma σ removes mixed quadratic terms; (3) and (4) , together with (9) and (11) , reduce higher-degree terms to c \mathbf{c} c , and (5) removes a linear term accompanied by its square. For separation, put b = a 2 b=a^2 b = a 2 . For each pair ( L , Q ) (L,Q) ( L , Q ) , define the valuation
ν L , Q ( x ) = { b , x ∈ L , a , x ∈ Q , ∞ , x ∉ L ∪ Q . \nu_{L,Q}(x)=
\begin{cases}
b, & x\in L,\\
a, & x\in Q,\\
\infty, & x\notin L\cup Q.
\end{cases} ν L , Q ( x ) = ⎩ ⎨ ⎧ b , a , ∞ , x ∈ L , x ∈ Q , x ∈ / L ∪ Q .
Then F ( L , Q ) ν L , Q = b \mathbf{F}(L,Q)^{\nu_{L,Q}}=b F ( L , Q ) ν L , Q = b , whereas c ν L , Q = ∞ \mathbf{c}^{\nu_{L,Q}}=\infty c ν L , Q = ∞ . Moreover, for a nonempty F ( L ′ , Q ′ ) \mathbf{F}(L',Q') F ( L ′ , Q ′ ) to have value b b b under this valuation, each variable of L ′ L' L ′ must lie in L L L and each variable of Q ′ Q' Q ′ must lie in Q Q Q . Indeed, a linear summand has value b b b only at b b b , and a squared summand has value b b b only at a a a ; any other value of a summand makes the flat sum different from b b b . Consequently, if neither ( L ′ , Q ′ ) (L',Q') ( L ′ , Q ′ ) nor ( L , Q ) (L,Q) ( L , Q ) is coordinatewise contained in the other, one of the two associated valuations distinguishes the forms. If ( L ′ , Q ′ ) ≠ ( L , Q ) (L',Q')\ne(L,Q) ( L ′ , Q ′ ) = ( L , Q ) and, say, L ′ ⊆ L L'\subseteq L L ′ ⊆ L , Q ′ ⊆ Q Q'\subseteq Q Q ′ ⊆ Q , then ν L ′ , Q ′ \nu_{L',Q'} ν L ′ , Q ′ gives b b b on F ( L ′ , Q ′ ) \mathbf{F}(L',Q') F ( L ′ , Q ′ ) and not on F ( L , Q ) \mathbf{F}(L,Q) F ( L , Q ) . The latter contains a summand with value ∞ \infty ∞ , from a variable in ( L ∖ L ′ ) ∪ ( Q ∖ Q ′ ) (L\setminus L')\cup(Q\setminus Q') ( L ∖ L ′ ) ∪ ( Q ∖ Q ′ ) . This also covers changes from linear to quadratic status. Thus the forms, including c \mathbf{c} c , are pairwise distinct in A 1 A_1 A 1 . For clarity, both inclusions are needed here. The old subsemiring A 1 = { a , b , ∞ } A_1=\{a,b,\infty\} A 1 = { a , b , ∞ } of A ^ 1 \widehat{A}_1 A 1 satisfies σ \sigma σ by its multiplication and flat-addition tables. Hence V ( A 1 ) ⊆ W 1 [ σ ] \mathop{\mathrm{V}}(A_1)\subseteq W_1[\sigma] V ( A 1 ) ⊆ W 1 [ σ ] . Conversely, the preceding normal-form reduction applies in W 1 [ σ ] W_1[\sigma] W 1 [ σ ] , and A 1 A_1 A 1 separates any two distinct normal forms. Therefore every identity holding in A 1 A_1 A 1 holds in W 1 [ σ ] W_1[\sigma] W 1 [ σ ] , proving W 1 [ σ ] ⊆ V ( A 1 ) W_1[\sigma]\subseteq\mathop{\mathrm{V}}(A_1) W 1 [ σ ] ⊆ V ( A 1 ) .
For hereditary finite basability, reduce identities to absorptions q ⪯ u \mathbf{q}\preceq\mathbf{u} q ⪯ u , with u = F ( L , Q ) \mathbf{u}=\mathbf{F}(L,Q) u = F ( L , Q ) and, after decomposing a quadratic query under σ \sigma σ , q ∈ { x , x 2 , c } \mathbf{q}\in\{x,x^2,\mathbf{c}\} q ∈ { x , x 2 , c } up to the identities of V 1 \mathcal{V}_1 V 1 . Mark the query variable when q = x \mathbf{q}=x q = x or x 2 x^2 x 2 ; for c \mathbf{c} c , use the cube of a fresh query variable. The finite state records the query type and whether its mark lies in L L L , in Q Q Q , or outside L ∪ Q L\cup Q L ∪ Q . Let M M M be the set of marks and put
d ( u , q ) = ( ∣ L ∖ M ∣ , ∣ Q ∖ M ∣ ) ∈ N 2 . d(\mathbf{u},\mathbf{q})=(|L\setminus M|,|Q\setminus M|)\in\mathbb{N}^2. d ( u , q ) = ( ∣ L ∖ M ∣ , ∣ Q ∖ M ∣ ) ∈ N 2 .
For equal states, compare the vectors coordinatewise. By Dickson’s lemma this is a well-quasi-order. If d ( u , q ) ≤ d ( u ′ , q ′ ) d(\mathbf{u},\mathbf{q})\leq d(\mathbf{u}',\mathbf{q}') d ( u , q ) ≤ d ( u ′ , q ′ ) , map the marked variable to its corresponding mark, and inject the remaining L L L - and Q Q Q -variables separately into their larger supports. Map a fresh cube variable to a fresh cube variable when q = c \mathbf{q}=\mathbf{c} q = c . This single renaming satisfies θ ( q ) ≈ q ′ \theta(\mathbf{q})\approx\mathbf{q}' θ ( q ) ≈ q ′ and u ′ ≈ θ ( u ) + r \mathbf{u}'\approx\theta(\mathbf{u})+\mathbf{r} u ′ ≈ θ ( u ) + r , so the absorption derivation is
u ′ + q ′ ≈ θ ( u ) + r + θ ( q ) ≈ u ′ . \mathbf{u}'+\mathbf{q}'\approx\theta(\mathbf{u})+\mathbf{r}+\theta(\mathbf{q})\approx\mathbf{u}'. u ′ + q ′ ≈ θ ( u ) + r + θ ( q ) ≈ u ′ .
Here the last step uses the smaller absorption under θ \theta θ ; if there are no extra summands, omit r r r . Therefore the valid absorptions of any subvariety have finitely many minimal generators among the finitely many states. Together with σ \sigma σ and a finite basis for W 1 W_1 W 1 [30 ] , these form a finite basis for that subvariety.
3. The ρ \rho ρ -branch. Substitution of y = x y=x y = x gives x 2 ≈ x 3 x^2 \approx x^3 x 2 ≈ x 3 . By ρ \rho ρ , (10) and (3), any word of degree at least two depends only on its content: for ∅ ≠ Y \varnothing\ne Y ∅ = Y , represent it by
u Y = { x 2 , Y = { x } , ∏ x ∈ Y x , ∣ Y ∣ ≥ 2. u_Y =
\begin{cases}
x^2, & Y=\{x\},\\
\prod_{x\in Y}x, & |Y|\ge2.
\end{cases} u Y = { x 2 , ∏ x ∈ Y x , Y = { x } , ∣ Y ∣ ≥ 2.
Whenever Y ⊆ Z Y\subseteq Z Y ⊆ Z , (6) and ρ \rho ρ imply u Y + u Z ≈ u Y u_Y+u_Z\approx u_Y u Y + u Z ≈ u Y . Indeed, u Y 2 ≈ u Y u_Y^2\approx u_Y u Y 2 ≈ u Y , so (6) with x = u Y x=u_Y x = u Y yields u Y + u Y z ≈ u Y u_Y+u_Yz\approx u_Y u Y + u Y z ≈ u Y . If ∣ Y ∣ ≥ 2 |Y|\ge2 ∣ Y ∣ ≥ 2 , the content reduction identifies u Z u_Z u Z with u Y u_Y u Y multiplied by the variables in Z ∖ Y Z\setminus Y Z ∖ Y . If Y = { x } Y=\{x\} Y = { x } and Z ⊋ Y Z\supsetneq Y Z ⊋ Y , the ρ \rho ρ -instance x z ≈ x 2 z xz\approx x^2z x z ≈ x 2 z , where z z z is the product of the variables of Z ∖ { x } Z\setminus\{x\} Z ∖ { x } , gives the same identification with u Y = x 2 u_Y=x^2 u Y = x 2 . The case Z = Y Z=Y Z = Y follows by additive idempotence. Moreover (4) gives x + x 2 ≈ x 2 x+x^2\approx x^2 x + x 2 ≈ x 2 . Hence each term has the finite-word form
F ( L , A ) = p 1 + ⋯ + p r , { p 1 , … , p r } = L ∪ { u Y : Y ∈ A } , F(L,A)=p_1+\cdots+p_r,\qquad\{p_1,\ldots,p_r\}=L\cup\{u_Y:Y\in A\}, F ( L , A ) = p 1 + ⋯ + p r , { p 1 , … , p r } = L ∪ { u Y : Y ∈ A } ,
where A A A is an antichain of nonempty subsets of variables, x ∉ L x\notin L x ∈ / L if { x } ∈ A \{x\}\in A { x } ∈ A , and the support is nonempty. Distinct forms are separated in R c h R_{\mathrm{ch}} R ch as follows. For each nonempty finite set Y Y Y of variables, let ν Y \nu_Y ν Y take value e e e on Y Y Y and 0 0 0 elsewhere. For this evaluation, u Z ν Y = ∞ u_Z^{\nu_Y}=\infty u Z ν Y = ∞ if and only if Z ⊆ Y Z\subseteq Y Z ⊆ Y , while every linear summand takes value at most e e e . Suppose A ≠ A ′ A\ne A' A = A ′ . Choose an inclusion-minimal set Y Y Y that belongs to exactly one of A A A and A ′ A' A ′ , and, after interchanging the two forms if necessary, let Y ∈ A ∖ A ′ Y\in A\setminus A' Y ∈ A ∖ A ′ . No member Z ∈ A ′ Z\in A' Z ∈ A ′ can be contained in Y Y Y : equality is excluded, and a proper subset would also belong to exactly one of the two antichains, contrary to the choice of Y Y Y . Under ν Y \nu_Y ν Y , the first form therefore takes value ∞ \infty ∞ while the second takes value at most e e e . This works regardless of their linear supports. If A = A ′ A=A' A = A ′ but L ≠ L ′ L\ne L' L = L ′ , choose x x x belonging to exactly one of L , L ′ L,L' L , L ′ , and assume x ∈ L ∖ L ′ x\in L\setminus L' x ∈ L ∖ L ′ . The normalization condition implies { x } ∉ A \{x\}\notin A { x } ∈ / A . Under ν { x } \nu_{\{x\}} ν { x } , every quadratic summand of either form is 0 0 0 , and only the first form contains the linear summand x = e x=e x = e . Hence the two values are e e e and 0 0 0 , respectively. The normal forms are therefore distinct in R c h R_{\mathrm{ch}} R ch . The subset { 0 , b , ∞ } \{0,b,\infty\} { 0 , b , ∞ } of A ^ 1 \widehat{A}_1 A 1 is a subsemiring isomorphic to R c h R_{\mathrm{ch}} R ch (the product of any two elements in { b , ∞ } \{b,\infty\} { b , ∞ } is ∞ \infty ∞ ). Its table satisfies ρ \rho ρ , so V ( R c h ) ⊆ W 1 [ ρ ] V(R_{\mathrm{ch}})\subseteq W_1[\rho] V ( R ch ) ⊆ W 1 [ ρ ] . The preceding normal-form reduction and separation show that every identity of R c h R_{\mathrm{ch}} R ch holds in W 1 [ ρ ] W_1[\rho] W 1 [ ρ ] . Hence W 1 [ ρ ] ⊆ V ( R c h ) W_1[\rho]\subseteq V(R_{\mathrm{ch}}) W 1 [ ρ ] ⊆ V ( R ch ) , and the required equality follows.
The three-element semiring R c h R_{\mathrm{ch}} R ch is isomorphic to the zero extension S ( a ) 0 S(a)^0 S ( a ) 0 : its elements are 0 , a , ∞ 0,a,\infty 0 , a , ∞ , its addition is 0 < a < ∞ 0<a<\infty 0 < a < ∞ , and all products of the two old elements a , ∞ a,\infty a , ∞ equal ∞ \infty ∞ . Shao–Gao [19, Theorem 25.2] prove that V ( S ( a ) 0 ) V(S(a)^0) V ( S ( a ) 0 ) has precisely five subvarieties and that each is finitely based. Since we established W 1 [ ρ ] = V ( R c h ) W_1[\rho]=V(R_{\mathrm{ch}}) W 1 [ ρ ] = V ( R ch ) above, this proves the hereditary finite-basis assertion directly. Note that Shao–Gao denote V ( S ( a ) 0 ) V(S(a)^0) V ( S ( a ) 0 ) by V 1 \mathcal{V}_1 V 1 , whereas our V 1 = V ( S ( a 2 ) ) \mathcal{V}_1=V(S(a^2)) V 1 = V ( S ( a 2 )) ; these two notations refer to different varieties.
We treat W 1 [ η ] W_1[\eta] W 1 [ η ] by means of graph normal forms and a well-quasi-order on their finite encodings.
Proposition 5.6. Every subvariety of W 1 [ η ] W_1[\eta] W 1 [ η ] is finitely based.
Proof. 1. Collapse of all words of length at least three. We first show that all cubes agree in W 1 [ η ] W_1[\eta] W 1 [ η ] . Put a = x 3 a=x^3 a = x 3 , b = y 3 b=y^3 b = y 3 and substitute ( a , b , b , a ) (a,b,b,a) ( a , b , b , a ) into η \eta η . Since a b + b 2 ≈ b ab+b^{2}\approx b ab + b 2 ≈ b by (9) and (7) , this instance reduces to b + a 2 ≈ b b+a^{2}\approx b b + a 2 ≈ b . As a 2 ≈ a a^{2}\approx a a 2 ≈ a by (9) , we obtain b + a ≈ b b+a\approx b b + a ≈ b . Interchanging x x x and y y y gives a + b ≈ a a+b\approx a a + b ≈ a . By commutativity of addition, x 3 ≈ y 3 x^{3}\approx y^{3} x 3 ≈ y 3 . Denote the common cube value by c \mathbf{c} c . The derived identities now give
x 3 y ≈ y 3 y ≈ y 4 ≈ y 3 = c , x^{3}y\approx y^{3}y\approx y^{4}\approx y^{3}=\mathbf{c}, x 3 y ≈ y 3 y ≈ y 4 ≈ y 3 = c ,
x + c ≈ x + x 2 + x 3 ≈ x 3 = c , x+\mathbf{c}\approx x+x^{2}+x^{3}\approx x^{3}=\mathbf{c}, x + c ≈ x + x 2 + x 3 ≈ x 3 = c ,
c + x y ≈ c . \mathbf{c}+xy\approx\mathbf{c}. c + x y ≈ c .
Here the first line uses the common cube and (9) , the second uses (5) , and the third uses (7) . Finally, (6) yields the explicit deduction
x + x y ≈ x + x y + x 3 y by (5) ≈ x + x y + c since x 3 y ≈ c ≈ x + c since c + x y ≈ c ≈ c since x + c ≈ c . \begin{aligned}
x+xy&\approx x+xy+x^{3}y &&\text{by (5)}\\
&\approx x+xy+\mathbf{c} &&\text{since }x^{3}y\approx\mathbf{c}\\
&\approx x+\mathbf{c} &&\text{since }\mathbf{c}+xy\approx\mathbf{c}\\
&\approx\mathbf{c} &&\text{since }x+\mathbf{c}\approx\mathbf{c}.
\end{aligned} x + x y ≈ x + x y + x 3 y ≈ x + x y + c ≈ x + c ≈ c by (5) since x 3 y ≈ c since c + x y ≈ c since x + c ≈ c .
Consequently,
x 3 ≈ c , c x ≈ c , x + c ≈ c , x + x y ≈ c . (13) x^{3}\approx\mathbf{c},\qquad\mathbf{c}x\approx\mathbf{c},\qquad x+\mathbf{c}\approx\mathbf{c},\qquad x+xy\approx\mathbf{c}. \tag*{(13)} x 3 ≈ c , c x ≈ c , x + c ≈ c , x + x y ≈ c . (13)
In particular every word of length at least three represents c \mathbf{c} c , and a linear term occurring also in a quadratic term makes the entire sum equal to c \mathbf{c} c .
We next describe the remaining terms by finite graphs. By Lemma 5.2 and (13) , a term other than c \mathbf{c} c is a sum of distinct linear words indexed by a set L L L and quadratic words indexed by the edges (loops permitted) of a finite graph G G G , with L ∩ V ( G ) = ∅ L\cap V(G)=\varnothing L ∩ V ( G ) = ∅ . The identity η \eta η adds an edge across every three-edge walk. For an odd walk v 0 , … , v 2 m + 1 v_{0},\ldots,v_{2m+1} v 0 , … , v 2 m + 1 , induct on m m m :
m = 0 : v 0 v 1 ∈ E ( G ) , m = 1 : v 0 v 3 is added by η , m ≥ 2 : v 0 v 2 m − 1 , v 2 m − 1 v 2 m , v 2 m v 2 m + 1 , v 0 v 2 m + 1 by η . \begin{aligned}
m=0 &: \quad v_{0}v_{1}\in E(G),\\
m=1 &: \quad v_{0}v_{3}\text{ is added by }\eta,\\
m\ge2 &: \quad v_{0}v_{2m-1},\ v_{2m-1}v_{2m},\ v_{2m}v_{2m+1},\\
&\quad v_{0}v_{2m+1}\text{ by }\eta.
\end{aligned} m = 0 m = 1 m ≥ 2 : v 0 v 1 ∈ E ( G ) , : v 0 v 3 is added by η , : v 0 v 2 m − 1 , v 2 m − 1 v 2 m , v 2 m v 2 m + 1 , v 0 v 2 m + 1 by η .
The induction hypothesis supplies the first edge in the last line. Each induction step applies η \eta η in the additive context of the unchanged summands. Consequently each bipartite connected component of G G G may be replaced by a complete bipartite graph, while each nonbipartite component becomes a complete graph with a loop at every vertex. If two looped components occur, choose a loop x 2 x^{2} x 2 in the first and a loop y 2 y^{2} y 2 in the second. The instance x 2 + y 2 ≈ x 2 + y 2 + x y x^{2}+y^{2}\approx x^{2}+y^{2}+xy x 2 + y 2 ≈ x 2 + y 2 + x y of (8) joins them by an edge; odd-walk closure then combines them into a single complete looped component. Repeating the argument merges all such components. Thus every term is equivalent either to c \mathbf{c} c or to
u = p 1 + ⋯ + p r , P ( L , G ) = { p 1 , … , p r } = L ∪ { x y : x y ∈ E ( G ) } . (14) \mathbf{u}=p_{1}+\cdots+p_{r},\qquad P(L,G)=\{p_{1},\ldots,p_{r}\}=L\cup\{xy:xy\in E(G)\}. \tag*{(14)} u = p 1 + ⋯ + p r , P ( L , G ) = { p 1 , … , p r } = L ∪ { x y : x y ∈ E ( G )} . (14)
where each undirected edge is represented by either order of its endpoints (the result is independent of this choice by (3) ), and where the linear vertices are disjoint from G G G , the nonlooped components are complete bipartite graphs with both shores nonempty, and there is at most one complete looped component. The sum in (14) is nonempty. We do not assert that these representatives are unique; the subsequent argument uses their existence and the fact that the displayed operations are obtained by identities valid in W 1 [ η ] W_{1}[\eta] W 1 [ η ] .
Finite encoding of absorption identities
Let K ⊆ W 1 [ η ] \mathcal{K} \subseteq W_1[\eta] K ⊆ W 1 [ η ] and consider its absorption identities. In an ai-semiring, for nonempty sums u = p 1 + ⋯ + p r \mathbf{u} = \mathbf{p}_1 + \cdots+ \mathbf{p}_r u = p 1 + ⋯ + p r and v = q 1 + ⋯ + q s \mathbf{v} = \mathbf{q}_1 + \cdots+ \mathbf{q}_s v = q 1 + ⋯ + q s , the identity u ≈ v \mathbf{u} \approx\mathbf{v} u ≈ v holds if and only if all the absorptions
p i ⪯ v ( 1 ≤ i ≤ r ) , q j ⪯ u ( 1 ≤ j ≤ s ) \mathbf{p}_i \preceq\mathbf{v} \quad(1 \leq i \leq r), \qquad\mathbf{q}_j \preceq\mathbf{u} \quad(1 \leq j \leq s) p i ⪯ v ( 1 ≤ i ≤ r ) , q j ⪯ u ( 1 ≤ j ≤ s )
hold. Indeed, the first family gives u + v ≈ v \mathbf{u} + \mathbf{v} \approx\mathbf{v} u + v ≈ v , whereas the second gives u + v ≈ u \mathbf{u} + \mathbf{v} \approx\mathbf{u} u + v ≈ u . Thus, modulo the six identities in Proposition 5.1 and η \eta η , it suffices to consider absorptions q ⪯ u \mathbf{q} \preceq\mathbf{u} q ⪯ u with q \mathbf{q} q a word and u \mathbf{u} u a nonempty sum of words. Absorptions with source u = c \mathbf{u} = \mathbf{c} u = c are automatic by (12) and may be discarded. For the remaining absorptions, u \mathbf{u} u has the form (13) and q \mathbf{q} q is either c \mathbf{c} c , a linear word, or a quadratic word (a loop is allowed). In the latter two cases mark the at most two variables of q \mathbf{q} q . We shall use the following comparison of the resulting pairs ( u , q ) (\mathbf{u},\mathbf{q}) ( u , q ) .
The marked configurations are classified by the form of the query and the positions of its variables. After normalization, the query is either c \mathbf{c} c , x x x , x 2 x^2 x 2 , or x y xy x y with x ≠ y x \ne y x = y . Each marked variable is either absent from the source, occurs in its linear part, or belongs to a bipartite or looped component of the graph. For x y xy x y , we also record whether its variables belong to the same graph component; if they lie in the same bipartite component, we distinguish the same shore from opposite shores. A square has one marked variable, whereas x y xy x y has two distinct marks. Since the linear part is disjoint from the graph and there is at most one looped component, these possibilities exhaust all configurations. The presence or absence of the looped component is also recorded in the finite state. Within a fixed state, distinguish the at most two bipartite components containing marked vertices, and orient their shores consistently with the marks. The state also records how many of the two query marks occupy each distinguished component, so the sizes below count only unmarked vertices. For an unmarked bipartite component choose either shore orientation; these components can be listed in any fixed order. The source is encoded by a vector of nonnegative integers consisting of the unmarked linear vertices, the unmarked vertices of the looped component (if present), and the two unmarked shore sizes in each distinguished bipartite component, together with a finite sequence
( s 1 , t 1 ) , … , ( s j , t j ) ( s i , t i ≥ 1 ) (s_1,t_1),\ldots,(s_j,t_j) \qquad(s_i,t_i \geq1) ( s 1 , t 1 ) , … , ( s j , t j ) ( s i , t i ≥ 1 )
for the unmarked bipartite components. Whether the looped component is present is included in the finite state.
To avoid comparing arbitrarily chosen representations, fix one encoding for each pair ( u , q ) (\mathbf{u},\mathbf{q}) ( u , q ) . Orient the shores of each unmarked component so that the smaller shore comes first, and list these components in lexicographic order of the resulting size pairs. Resolve ties by a fixed convention. Represent a chosen encoding as
e = ( τ ; d ; ( s 1 , t 1 ) , … , ( s j , t j ) ) , e = (\tau;\mathbf{d};(s_1,t_1),\ldots,(s_j,t_j)), e = ( τ ; d ; ( s 1 , t 1 ) , … , ( s j , t j )) ,
where τ \tau τ is the finite state and d \mathbf{d} d the finite vector just described. Declare e ≤ e ′ e \leq e' e ≤ e ′ precisely when their states agree, d ≤ d ′ \mathbf{d} \leq\mathbf{d}' d ≤ d ′ coordinatewise, and some indices 1 ≤ i 1 < ⋯ < i j ≤ j ′ 1 \leq i_1 < \cdots< i_j \leq j' 1 ≤ i 1 < ⋯ < i j ≤ j ′ satisfy
( s k , t k ) ≤ ( s i k ′ , t i k ′ ) ( 1 ≤ k ≤ j ) (s_k,t_k) \leq(s'_{i_k},t'_{i_k}) \qquad(1 \leq k \leq j) ( s k , t k ) ≤ ( s i k ′ , t i k ′ ) ( 1 ≤ k ≤ j )
coordinatewise. Dickson’s lemma for the vectors and N 2 \mathbb{N}^2 N 2 , followed by Higman’s lemma [10 ] , implies that every infinite sequence of fixed encodings has an increasing pair (there are only finitely many states). The empty list encodes zero unmarked components; absence of the unique looped component belongs to τ \tau τ . Neither denotes an empty polynomial.
A single substitution for each comparison. We realize every encoding comparison by one substitution and an equational derivation. Suppose ( u , q ) (\mathbf{u},q) ( u , q ) has an encoding below that of ( u ′ , q ′ ) (\mathbf{u}',q') ( u ′ , q ′ ) . Match the (at most two) marked variables of q q q to the corresponding variables of q ′ q' q ′ , preserving whether they coincide and which part of the source each occupies. Send the unmarked linear variables injectively into the corresponding linear variables of u ′ \mathbf{u}' u ′ ; the coordinate inequality guarantees room for them. Do the same for the unique looped component, if present, and for each of the at most two marked bipartite components, embedding the two shores separately while fixing all marked vertices. For an unmarked bipartite component, the Higman subsequence matching selects a distinct target component; possibly reverse its shores and inject each of the two vertex sets into the corresponding target shore. Map every query variable outside u \mathbf{u} u to its designated query variable outside u ′ \mathbf{u}' u ′ . The choices are made simultaneously and define a single injective renaming θ \theta θ . In particular, every occurrence of a source variable receives the same image; choosing separate images for individual graph edges would not define a substitution.
The construction handles every source variable according to one of four disjoint cases:
A marked variable is sent to the matching marked variable, preserving equality or distinctness of the marks.
An unmarked linear variable is sent injectively to an unmarked linear variable; a mark in the linear part has already been fixed in the first case.
An unmarked vertex of the looped component or of a marked bipartite component is sent injectively within the corresponding target component and shore, avoiding the previously fixed marks.
A vertex of an unmarked bipartite component is sent into the distinct target component selected by the Higman subsequence match, preserving its shore after the permitted orientation reversal.
Variables occurring only in q q q belong to the first case; when q = c q=c q = c a fresh cubic variable is fixed separately. The recorded finite state fixes the positions of all marks, so the injections in the other three cases have disjoint images. Completeness of the bipartite and looped components ensures that every source edge maps to a target edge; linear summands map to linear summands. Consequently θ \theta θ sends every summand of u \mathbf{u} u to a summand of u ′ \mathbf{u}' u ′ . This is a single injective renaming, not a family of independent edgewise assignments. If q q q is linear or quadratic, θ ( q ) = q ′ \theta(q)=q' θ ( q ) = q ′ by the marks; if q = c q=c q = c , represent it by z 3 z^3 z 3 with a fresh z z z and set θ ( z ) = z ′ \theta(z)=z' θ ( z ) = z ′ , using the equality of all cubes. Hence, modulo the identities of W 1 [ η ] W_1[\eta] W 1 [ η ] ,
q ′ ≈ θ ( q ) , u ′ ≈ θ ( u ) + r , q' \approx\theta(q), \qquad\mathbf{u}' \approx\theta(\mathbf{u})+\mathbf{r}, q ′ ≈ θ ( q ) , u ′ ≈ θ ( u ) + r ,
where r \mathbf{r} r consists of the extra summands of u ′ \mathbf{u}' u ′ . When none remain, the second relation reads u ′ ≈ θ ( u ) \mathbf{u}' \approx\theta(\mathbf{u}) u ′ ≈ θ ( u ) with no empty-sum term.
For completeness, the actual equational deduction is
u ′ + q ′ ≈ θ ( u ) + r + θ ( q ) ≈ θ ( u ) + θ ( q ) + r ≈ θ ( u ) + r ≈ u ′ . \begin{aligned}
\mathbf{u}'+q' &\approx\theta(\mathbf{u})+\mathbf{r}+\theta(q)\\
&\approx\theta(\mathbf{u})+\theta(q)+\mathbf{r}\\
&\approx\theta(\mathbf{u})+\mathbf{r}\approx\mathbf{u}'.
\end{aligned} u ′ + q ′ ≈ θ ( u ) + r + θ ( q ) ≈ θ ( u ) + θ ( q ) + r ≈ θ ( u ) + r ≈ u ′ .
The middle step is the θ \theta θ -instance of the assumed absorption u + q ≈ u \mathbf{u}+\mathbf{q}\approx\mathbf{u} u + q ≈ u , used inside an additive context. If r \mathbf{r} r is absent, the same calculation is read without it.
5. Finite basis. The displayed derivation shows that the absorptions valid in K \mathcal{K} K form an upward-closed set in the encoding order. This order is a well-quasi-order by Dickson’s and Higman’s lemmas; hence the set has finitely many minimal generators. These absorptions, together with η \eta η and a finite basis for W 1 \mathcal{W}_1 W 1 (available by [30 ] ), form a finite equational basis for K \mathcal{K} K . □ \square □
For the remaining reduction we record the evaluations in S R 6 SR_6 S R 6 . We label its elements 1 , … , 6 1,\ldots,6 1 , … , 6 as in [13 ] . The element 1 1 1 is the additive top and is multiplicatively absorbing; all squares and all products of length at least three are 1 1 1 . The products distinct from 1 1 1 are
2 ⋅ 6 = 5 ⋅ 6 = 5 ⋅ 4 = 3 2 \cdot6 = 5 \cdot6 = 5 \cdot4 = 3 2 ⋅ 6 = 5 ⋅ 6 = 5 ⋅ 4 = 3
and their symmetric counterparts. The element 3 3 3 has 3 + z = 1 3+z=1 3 + z = 1 for every z ≠ 3 z\ne3 z = 3 . Direct evaluation in the Cayley tables shows that the substitution ( x 1 , x 2 , x 3 , x 4 ) = ( 2 , 6 , 5 , 4 ) (x_1,x_2,x_3,x_4)=(2,6,5,4) ( x 1 , x 2 , x 3 , x 4 ) = ( 2 , 6 , 5 , 4 ) gives the left side of η \eta η value 3 3 3 and its right side value 1 1 1 ; hence S R 6 SR_6 S R 6 does not satisfy η \eta η .
Lemma 5.7. Let K ⊆ W 1 \mathcal{K}\subseteq\mathcal{W}_1 K ⊆ W 1 and suppose V ( S R 6 ) ⊈ K \mathcal{V}(SR_6)\not\subseteq\mathcal{K} V ( S R 6 ) ⊆ K . Then K \mathcal{K} K is contained in one of W 1 [ λ ] \mathcal{W}_1[\lambda] W 1 [ λ ] , W 1 [ σ ] \mathcal{W}_1[\sigma] W 1 [ σ ] , W 1 [ ρ ] \mathcal{W}_1[\rho] W 1 [ ρ ] , W 1 [ η ] \mathcal{W}_1[\eta] W 1 [ η ] .
Proof. 1. A failing absorption and its bipartite source. Choose an identity holding in K \mathcal{K} K but failing in S R 6 SR_6 S R 6 . By distributivity and additive idempotence, one of its component absorptions q ⪯ u \mathbf{q}\preceq\mathbf{u} q ⪯ u is valid in K \mathcal{K} K but fails in S R 6 SR_6 S R 6 ; here q \mathbf{q} q is a word and u \mathbf{u} u a nonempty sum of words. All words may be taken commutative. Since S R 6 SR_6 S R 6 has a valuation at which u ≠ 1 \mathbf{u}\ne1 u = 1 , its multiplication table shows that u \mathbf{u} u contains only linear words and square-free quadratic words. Write
u = p 1 + ⋯ + p r , { p 1 , … , p r } = P ( L , G ) , P ( L , G ) = L ∪ { x y : x y ∈ E ( G ) } , \mathbf{u}=p_1+\cdots+p_r,\qquad\{p_1,\ldots,p_r\}=P(L,G),\qquad P(L,G)=L\cup\{xy:xy\in E(G)\}, u = p 1 + ⋯ + p r , { p 1 , … , p r } = P ( L , G ) , P ( L , G ) = L ∪ { x y : x y ∈ E ( G )} ,
with each edge word represented in either order, as permitted by (2). The graph G G G is bipartite and L ∩ V ( G ) = ∅ L\cap V(G)=\varnothing L ∩ V ( G ) = ∅ : indeed every quadratic summand must have value 3 3 3 , so the endpoints of its edges must be assigned elements in the two classes { 2 , 5 } \{2,5\} { 2 , 5 } and { 4 , 6 } \{4,6\} { 4 , 6 } ; an odd cycle is impossible, and a variable occurring also as a linear summand cannot simultaneously have value 3 3 3 . Conversely, such a sum has a valuation of value 3 3 3 , by assigning 5 , 6 5,6 5 , 6 on the two shores and 3 3 3 to the linear variables. The case E ( G ) = ∅ E(G)=\varnothing E ( G ) = ∅ is included.
2. Reduction to a two-letter source. For each bipartite component choose its shores U , V U,V U , V , and use the simultaneous substitution
θ ( z ) = { s , z ∈ U , t , z ∈ V , s t , z ∈ L . \theta(z)=
\begin{cases}
s, & z\in U,\\
t, & z\in V,\\
st, & z\in L.
\end{cases} θ ( z ) = ⎩ ⎨ ⎧ s , t , s t , z ∈ U , z ∈ V , z ∈ L .
For this simultaneous substitution, θ ( u ) ≈ s t \theta(\mathbf{u})\approx st θ ( u ) ≈ s t . Variables outside c ( u ) c(\mathbf{u}) c ( u ) may be sent to s , t s,t s , t , or s t st s t as specified in the cases below. Each component is oriented independently, but every occurrence of a variable receives the same image.
3. Linear, square, and higher-degree queries. If q \mathbf{q} q has degree at least three, or is a square, the image θ ( q ) \theta(\mathbf{q}) θ ( q ) is a word of degree at least two and is not s t st s t . By commutativity, (8) and (10), its possibilities modulo the identities of W 1 \mathcal{W}_1 W 1 reduce to
s 2 , t 2 , s 3 , t 3 , s 2 t (with s 2 t ≈ s t 2 ). s^2,\qquad t^2,\qquad s^3,\qquad t^3,\qquad s^2t\quad\text{(with }s^2t\approx st^2\text{).} s 2 , t 2 , s 3 , t 3 , s 2 t (with s 2 t ≈ s t 2 ).
One-variable powers of degree at least three become cubes, and mixed words of degree at least three become s 2 t s^{2}t s 2 t by (8) and (10). Because K ⊨ θ ( q ) ⪰ s t \mathcal{K} \models\theta(\mathbf{q}) \succeq st K ⊨ θ ( q ) ⪰ s t , the possibilities yield the following consequences, with their hypotheses stated explicitly:
hypothesis s t + s 2 ≈ s t : s t ≈ s t + s 2 + t 2 ≈ s 2 + t 2 ( σ ) , hypothesis s t + s 3 ≈ s t : s t + s + s 2 ≈ s t + s 3 ≈ s t ( λ ) , hypothesis s t + s 2 t ≈ s t : s t ≈ s 2 t ( ρ ) . \begin{aligned}
\text{hypothesis } st+s^{2}\approx st &: \quad st\approx st+s^{2}+t^{2}\approx s^{2}+t^{2} \quad(\sigma),\\
\text{hypothesis } st+s^{3}\approx st &: \quad st+s+s^{2}\approx st+s^{3}\approx st \quad(\lambda),\\
\text{hypothesis } st+s^{2}t\approx st &: \quad st\approx s^{2}t \quad(\rho).
\end{aligned} hypothesis s t + s 2 ≈ s t hypothesis s t + s 3 ≈ s t hypothesis s t + s 2 t ≈ s t : s t ≈ s t + s 2 + t 2 ≈ s 2 + t 2 ( σ ) , : s t + s + s 2 ≈ s t + s 3 ≈ s t ( λ ) , : s t ≈ s 2 t ( ρ ) .
For the first line interchange s s s and t t t and use (7); for the second use (4); for the third use s t + s 2 t ≈ s 2 t st+s^{2}t\approx s^{2}t s t + s 2 t ≈ s 2 t , obtained by multiplying (4) by t t t and applying (9). The t 2 , t 3 t^{2},t^{3} t 2 , t 3 cases are symmetric. If q \mathbf{q} q is linear, it cannot belong to L L L (because q ⪯ u \mathbf{q}\preceq\mathbf{u} q ⪯ u would then hold in S R 6 SR_{6} S R 6 ). Orient its graph component, or assign it if absent from c ( u ) c(\mathbf{u}) c ( u ) , so that θ ( q ) = s \theta(\mathbf{q})=s θ ( q ) = s . Thus K ⊨ s ⪯ s t \mathcal{K}\models s\preceq st K ⊨ s ⪯ s t , giving λ \lambda λ .
Square-free quadratic queries
Let q = x y \mathbf{q}=xy q = x y with x ≠ y x\ne y x = y . If either endpoint belongs to L L L or is absent from u \mathbf{u} u , map that endpoint to s t st s t and orient the remaining components as above. The image of q \mathbf{q} q has degree at least three. If x , y x,y x , y lie in different components of G G G , or on the same shore of one component, the orientations can instead be chosen so that both map to s s s . We obtain s t ⪰ s 2 st\succeq s^{2} s t ⪰ s 2 and hence σ \sigma σ .
In the remaining case x , y x,y x , y lie in opposite shores of the same connected component. Since the absorption fails in S R 6 SR_{6} S R 6 , the word x y xy x y cannot be a summand of u \mathbf{u} u . Choose a shortest odd path x = v 0 , … , v 2 m + 1 = y x=v_{0},\ldots,v_{2m+1}=y x = v 0 , … , v 2 m + 1 = y with m ≥ 1 m\ge1 m ≥ 1 . Let C 0 C_{0} C 0 be their component, with shores U ∋ x U\ni x U ∋ x and V ∋ y V\ni y V ∋ y . For each other component C C C , choose shores U C , V C U_{C},V_{C} U C , V C . Define the single substitution
θ ( z ) = { x 1 , z = x , x 4 , z = y , x 3 , z ∈ ( U ∖ { x } ) ∪ ⋃ C ≠ C 0 U C , x 2 , z ∈ ( V ∖ { y } ) ∪ ⋃ C ≠ C 0 V C , x 2 x 3 , z ∈ L . \theta(z)=
\begin{cases}
x_{1}, & z=x,\\
x_{4}, & z=y,\\
x_{3}, & z\in(U\setminus\{x\})\cup\bigcup_{C\ne C_{0}}U_{C},\\
x_{2}, & z\in(V\setminus\{y\})\cup\bigcup_{C\ne C_{0}}V_{C},\\
x_{2}x_{3}, & z\in L.
\end{cases} θ ( z ) = ⎩ ⎨ ⎧ x 1 , x 4 , x 3 , x 2 , x 2 x 3 , z = x , z = y , z ∈ ( U ∖ { x }) ∪ ⋃ C = C 0 U C , z ∈ ( V ∖ { y }) ∪ ⋃ C = C 0 V C , z ∈ L .
The cases are disjoint and assign one word to each source variable. Thus
θ ( u ) ≈ x 1 x 2 + x 2 x 3 + x 3 x 4 , θ ( q ) = x 1 x 4 . \theta(\mathbf{u})\approx x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{4},\qquad\theta(\mathbf{q})=x_{1}x_{4}. θ ( u ) ≈ x 1 x 2 + x 2 x 3 + x 3 x 4 , θ ( q ) = x 1 x 4 .
Indeed the first and last edges of the chosen path produce x 1 x 2 x_{1}x_{2} x 1 x 2 and x 3 x 4 x_{3}x_{4} x 3 x 4 ; an internal edge produces x 2 x 3 x_{2}x_{3} x 2 x 3 . No edge produces x 1 x 4 x_{1}x_{4} x 1 x 4 , since x y ∉ E ( G ) xy\notin E(G) x y ∈ / E ( G ) . Here no additional edge image is possible: an edge incident with x x x maps to x 1 x 2 x_{1}x_{2} x 1 x 2 , one incident with y y y maps to x 3 x 4 x_{3}x_{4} x 3 x 4 , and every other edge within this component maps to x 2 x 3 x_{2}x_{3} x 2 x 3 . All other components and all linear summands also map to x 2 x 3 x_{2}x_{3} x 2 x 3 . The shortest path has length at least three and supplies all three displayed source terms. The image of the query is x 1 x 4 x_{1}x_{4} x 1 x 4 , so K \mathcal{K} K satisfies η \eta η . The cases exhaust every query word: linear, square or higher-degree, or square-free quadratic; for the last type, the endpoints are outside/in the linear part of the source, in distinct components, on the same shore, or on opposite shores of one component. Each construction uses one substitution for all source summands. Hence one of λ , σ , ρ , η \lambda,\sigma,\rho,\eta λ , σ , ρ , η holds in K \mathcal{K} K . The final odd-path substitution also appears in Yue [27 Proposition 3.21] .
The hereditary finite-basis reduction now yields Theorem 5.4.
Proof. Proposition 5.3 gives V ( S R 6 ) ⊆ W 1 V(SR_{6})\subseteq\mathcal{W}_{1} V ( S R 6 ) ⊆ W 1 without using a defining identity basis for W 1 \mathcal{W}_{1} W 1 . The variety V ( S R 6 ) V(SR_{6}) V ( S R 6 ) is a limit variety by [13 ] .
Let K ⊆ W 1 \mathcal{K} \subseteq\mathcal{W}_1 K ⊆ W 1 with V ( S R 6 ) ⊈ K \mathop{\mathrm{V}}(SR_6) \nsubseteq\mathcal{K} V ( S R 6 ) ⊈ K . By Lemma 5.7 , K \mathcal{K} K lies in one of the four subvarieties listed there. Each of these is hereditarily finitely based by Propositions 5.5 and 5.6 . This proves the first assertion.
Suppose that K \mathcal{K} K is a limit subvariety of W 1 \mathcal{W}_1 W 1 distinct from V ( S R 6 ) \mathop{\mathrm{V}}(SR_6) V ( S R 6 ) . Then either V ( S R 6 ) ⊈ K \mathop{\mathrm{V}}(SR_6) \nsubseteq\mathcal{K} V ( S R 6 ) ⊈ K , contradicting the first assertion, or V ( S R 6 ) ⊊ K \mathop{\mathrm{V}}(SR_6) \subsetneq\mathcal{K} V ( S R 6 ) ⊊ K , contradicting the definition of a limit variety. Therefore V ( S R 6 ) \mathop{\mathrm{V}}(SR_6) V ( S R 6 ) is the unique limit subvariety of W 1 \mathcal{W}_1 W 1 . □ \square □
A limit variety generated by T ∞ T_\infty T ∞
The limit property of V ( S R 6 ) \mathop{\mathrm{V}}(SR_6) V ( S R 6 ) is due to Lyu–Ren–Yue [13 ] ; the uniqueness statement proved in § 5 is relative to W 1 \mathcal{W}_1 W 1 . We construct a further limit variety, distinct from V ( S R 6 ) \mathop{\mathrm{V}}(SR_6) V ( S R 6 ) , which lies in every W n \mathcal{W}_n W n for n ≥ 2 n \ge2 n ≥ 2 but in no V n \mathcal{V}_n V n . The proof has three parts: nonabsorbing triple products encode directed edges; finite directed cycles provide countermodels to finite basability; and a bound on directed-path length controls proper subvarieties. The embedding and separating identities are verified before the structural argument.
Semirings attached to directed paths and their location in W 2 \mathcal{W}_2 W 2
For k ≥ 2 k \ge2 k ≥ 2 , let
T k = { ∞ , ω , e } ∪ { u i , p i , q i : 1 ≤ i ≤ k } . T_k = \{\infty, \omega, e\} \cup\{u_i, p_i, q_i : 1 \le i \le k\}. T k = { ∞ , ω , e } ∪ { u i , p i , q i : 1 ≤ i ≤ k } .
Addition is flat: a + a = a a+a=a a + a = a and a + b = ∞ a+b=\infty a + b = ∞ for distinct elements. The products different from ∞ \infty ∞ are precisely
u i e = p i , e u i = q i ( 1 ≤ i ≤ k ) , u_i e = p_i,\qquad e u_i = q_i \qquad(1 \le i \le k), u i e = p i , e u i = q i ( 1 ≤ i ≤ k ) ,
p i u i + 1 = ω , u i q i + 1 = ω ( 1 ≤ i < k ) . p_i u_{i+1} = \omega,\qquad u_i q_{i+1} = \omega\qquad(1 \le i < k). p i u i + 1 = ω , u i q i + 1 = ω ( 1 ≤ i < k ) .
All remaining products, including products involving ω \omega ω or ∞ \infty ∞ , equal ∞ \infty ∞ . Define T ∞ T_\infty T ∞ by the same rules with indices in the positive integers and put
U = V ( T ∞ ) . \mathcal{U} = \mathop{\mathrm{V}}(T_\infty). U = V ( T ∞ ) .
We retain the endpoint elements p k p_k p k and q 1 q_1 q 1 , although neither occurs in a nonabsorbing triple product of T k T_k T k . Thus T k T_k T k is a subsemiring of T k + 1 T_{k+1} T k + 1 and T ∞ = ⋃ k ≥ 2 T k T_\infty= \bigcup_{k \ge2} T_k T ∞ = ⋃ k ≥ 2 T k .
Lemma 6.1. The algebras T k T_k T k and T ∞ T_\infty T ∞ are flat a i ai ai -semirings. They satisfy x 2 ≈ x 3 x^2 \approx x^3 x 2 ≈ x 3 , and every product of four elements equals ∞ \infty ∞ . Moreover
U = V ( { T k : k ≥ 2 } ) . \mathcal{U} = \mathop{\mathrm{V}}(\{T_k : k \ge2\}). U = V ({ T k : k ≥ 2 }) .
Proof. First consider distributivity. In each row and column of the multiplication table, all values other than ∞ \infty ∞ are distinct. This is exactly the ∞ \infty ∞ -cancellation property: if a b = a c ≠ ∞ ab=ac\ne\infty ab = a c = ∞ then b = c b=c b = c , and symmetrically on the right. For flat addition, ∞ \infty ∞ -cancellation ensures that multiplying the sum of two distinct elements agrees with the sum of their products. The case of equal summands is immediate from idempotence. Hence both distributive laws hold.
We next verify associativity and nilpotence. The only nonabsorbing products of length three are
( u i e ) u i + 1 = u i ( e u i + 1 ) = ω . (u_i e)u_{i+1}=u_i(eu_{i+1})=\omega. ( u i e ) u i + 1 = u i ( e u i + 1 ) = ω .
Conversely, a triple product can be nonabsorbing only if its first two factors form u i e = p i u_i e=p_i u i e = p i and its last two form e u i + 1 = q i + 1 e u_{i+1}=q_{i+1} e u i + 1 = q i + 1 , so the two possible associations agree. Every other triple product evaluates to ∞ \infty ∞ under both associations, proving associativity. All squares equal ∞ \infty ∞ , and every product of four factors is ∞ \infty ∞ .
:::
Finally, consider the generated variety. Each finite set of elements of T ∞ T_{\infty} T ∞ is contained in some T k T_k T k . Since an identity involves only finitely many variables, it holds in T ∞ T_{\infty} T ∞ exactly when it holds in every T k T_k T k ; the asserted equality of generated varieties follows. □ \square □
For later use, if G G G is a finite directed path with at least two vertices (all edges coherently oriented), or a directed cycle of length at least four, write T ( G ) T(G) T ( G ) for the semiring with elements ∞ , ω , e , u i , p i , q i \infty,\omega,e,u_i,p_i,q_i ∞ , ω , e , u i , p i , q i indexed by the vertices of G G G , with u i e = p i u_i e=p_i u i e = p i and e u i = q i e u_i=q_i e u i = q i . The products p i u j p_i u_j p i u j and u i q j u_i q_j u i q j both equal ω \omega ω if and only if i → j i\to j i → j is an edge of G G G ; all other products are ∞ \infty ∞ . Thus T k = T ( P k ) T_k=T(P_k) T k = T ( P k ) , where P k P_k P k has k k k vertices, and we put C m = T ( C ~ m ) C_m=T(\widetilde{C}_m) C m = T ( C m ) for the directed m m m -cycle, m ≥ 4 m\ge4 m ≥ 4 .
Proposition 6.2. For every finite directed path G G G with at least two vertices and coherently oriented edges, and for every directed cycle G G G of length at least four, T ( G ) ∈ W 2 T(G)\in\mathcal{W}_2 T ( G ) ∈ W 2 .
Consequently U ⊆ W n \mathcal{U}\subseteq\mathcal{W}_n U ⊆ W n for all n ≥ 2 n\ge2 n ≥ 2 .
Proof. Let G G G have vertex set { 1 , … , k } \{1,\ldots,k\} { 1 , … , k } and put S = A ^ 2 = S ( a b b a ) 0 S=\widehat{A}_2=S(abba)^0 S = A 2 = S ( abba ) 0 . We compare the kernels of evaluation in S S S and in T ( G ) T(G) T ( G ) on the same generating variables. Denote the newly adjoined zero by 0 0 0 , so that 0 ≠ ∞ 0\ne\infty 0 = ∞ . We construct a subsemiring of a finite power of S S S that admits T ( G ) T(G) T ( G ) as a homomorphic image. The required power is S 1 + k + ( k 2 ) S^{1+k+\binom{k}{2}} S 1 + k + ( 2 k ) . Define vectors g 1 , … , g k , h g_1,\ldots,g_k,h g 1 , … , g k , h as follows. In a common coordinate, put g i = a g_i=a g i = a for every i i i and h = b b h=bb h = bb . In the coordinate labelled { i } \{i\} { i } , put g i = a g_i=a g i = a , all other g j = 0 g_j=0 g j = 0 , and h = b b h=bb h = bb . In the coordinate labelled { i , j } \{i,j\} { i , j } , when i → j i\to j i → j , put g i = a g_i=a g i = a , g j = b g_j=b g j = b , h = b h=b h = b , and all other g s = 0 g_s=0 g s = 0 ; reverse the assignments to g i , g j g_i,g_j g i , g j when j → i j\to i j → i . If i , j i,j i , j are nonadjacent, put g i = g j = a g_i=g_j=a g i = g j = a , h = b b h=bb h = bb , and the remaining g s = 0 g_s=0 g s = 0 . These instructions are unambiguous because G G G has neither loops nor opposite directed edges; for a directed path the coherent orientation hypothesis is used throughout.
Let H = ⟨ g 1 , … , g k , h ⟩ ≤ S 1 + k + ( k 2 ) H=\langle g_1,\ldots,g_k,h\rangle\le S^{1+k+\binom{k}{2}} H = ⟨ g 1 , … , g k , h ⟩ ≤ S 1 + k + ( 2 k ) . Our claim is that the assignment
g i ⟼ u i ( 1 ≤ i ≤ k ) , h ⟼ e g_i\longmapsto u_i\quad(1\le i\le k),\qquad h\longmapsto e g i ⟼ u i ( 1 ≤ i ≤ k ) , h ⟼ e
induces a surjective homomorphism H ↠ T ( G ) H\twoheadrightarrow T(G) H ↠ T ( G ) . To prove that the assignment is well defined, it suffices to show that whenever two polynomial terms have the same value in H H H , they also have the same value under the corresponding assignment in T ( G ) T(G) T ( G ) . Every term on g 1 , … , g k , h g_1,\ldots,g_k,h g 1 , … , g k , h expands into a nonempty sum of multiplicative words. In the common coordinate, its potentially nonabsorbing words have exactly the five forms
g i , h , g i h , h g i , g i h g j . g_i,\qquad h,\qquad g_i h,\qquad h g_i,\qquad g_i h g_j. g i , h , g i h , h g i , g i h g j .
All other words have common-coordinate value ∞ \infty ∞ . For the five listed forms, the coordinate values and their images in T ( G ) T(G) T ( G ) are
Table 5.
Consequently a term with nonabsorbing image has one of these five common-coordinate types. A term with two different types, or with any common-coordinate absorbing word, has absorbing image and absorbing common coordinate, so cannot coincide as a vector with a term having nonabsorbing image. We next distinguish the values represented within each common-coordinate type. For the first four types, the k k k singleton coordinates record the relevant indices: at coordinate { i } \{i\} { i } the relevant value is respectively a a a , b b bb bb , a b b abb abb , b b a bba bba for the indicated index (the common h h h has value b b bb bb in every singleton coordinate), whereas indices absent from that coordinate contribute the added zero 0 0 0 . Thus a term of type g i g_i g i , g i h g_i h g i h , or h g i h g_i h g i has a nonabsorbing image only if all its words carry one and the same index; two different nonabsorbing images cannot yield the same vector. The type h h h has only the image e e e .
For the fifth type, we must distinguish edges from nonedges: a term has nonabsorbing image precisely when every word g i h g j g_i h g_j g i h g j corresponds to an edge i → j i \to j i → j ; its image is then ω \omega ω . Suppose the term includes a non-edge g i h g j g_i h g_j g i h g j . If i = j i=j i = j , at the singleton coordinate { i } \{i\} { i } this word equals a b b a abba abba , while every edge word equals 0 0 0 . If i ≠ j i \ne j i = j are nonadjacent, their pair coordinate has the same property. If the reverse edge j → i j \to i j → i is present, at its pair coordinate the non-edge word g i h g j g_i h g_j g i h g j has value b b a bba bba , while the unique edge word supported on the pair has value a b b abb abb ; all other edge words give 0 0 0 . In all three cases, adding the non-edge word changes the coordinate value of any sum consisting only of edge words: the result is respectively a b b a abba abba or ∞ \infty ∞ (and in the reversed-edge case b b a bba bba or ∞ \infty ∞ ), never the edge-only value 0 0 0 or a b b abb abb . Hence a term with absorbing image cannot share its vector value with a term whose image is ω \omega ω .
We now complete the HSP construction. The coordinate tests prove the required inclusion of evaluation kernels, and hence the map on generators extends uniquely to a well-defined semiring homomorphism H → T ( G ) H \to T(G) H → T ( G ) . Its image contains u i u_i u i and e e e , and hence p i p_i p i , q i q_i q i , ω \omega ω and ∞ \infty ∞ , so the map is surjective. Thus T ( G ) ∈ HS ( S 1 + k + ( k 2 ) ) T(G) \in\operatorname{HS}(S^{1+k+\binom{k}{2}}) T ( G ) ∈ HS ( S 1 + k + ( 2 k ) ) .
In particular T k ∈ W 2 T_k \in\mathcal{W}_2 T k ∈ W 2 for all k ≥ 2 k \ge2 k ≥ 2 and hence U ⊆ W 2 \mathcal{U} \subseteq\mathcal{W}_2 U ⊆ W 2 at the level of generated varieties. Finally, Ab 2 \operatorname{Ab}_2 Ab 2 is a subsemiring of Ab n \operatorname{Ab}_n Ab n obtained from the central factor a b b a abba abba of m n m_n m n (renaming its two letters). This gives W 2 ⊆ W n \mathcal{W}_2 \subseteq\mathcal{W}_n W 2 ⊆ W n . □
Nonfinite basis and separation
Lemma 6.3. The variety V ( T ∞ ) \mathcal{V}(T_\infty) V ( T ∞ ) is nonfinitely based.
Proof. We begin with a family of identities valid in T ∞ T_\infty T ∞ . For m ≥ 1 m \ge1 m ≥ 1 consider
χ m : ∑ i = 1 m x i y x i + 1 ≈ z 3 , x m + 1 = x 1 . (15) \chi_m:\quad\sum_{i=1}^{m} x_i y x_{i+1} \approx z^3,\qquad x_{m+1}=x_1. \tag*{(15)} χ m : i = 1 ∑ m x i y x i + 1 ≈ z 3 , x m + 1 = x 1 . (15)
It holds in T ∞ T_\infty T ∞ : if the left-hand side were different from ∞ \infty ∞ , all its summands would equal ω \omega ω . The multiplication table then forces y = e y=e y = e , each x i = u j i x_i=u_{j_i} x i = u j i and j i + 1 = j i + 1 j_{i+1}=j_i+1 j i + 1 = j i + 1 , including the return from j m j_m j m to j 1 j_1 j 1 . This is impossible. On the other hand, C m C_m C m violates χ m \chi_m χ m for m ≥ 4 m \ge4 m ≥ 4 , taking x i = u i x_i=u_i x i = u i and y = e y=e y = e .
We then examine the small generated subsemirings of the countermodels. Fix r < m r<m r < m . Apart from ∞ , ω , e \infty,\omega,e ∞ , ω , e , each of any r r r chosen elements of C m C_m C m involves at most one vertex index. If S S S is the set of indices occurring in r r r chosen generators, their generated subsemiring is contained in
{ ∞ , ω , e } ∪ { u i , p i , q i : i ∈ S } . \{\infty,\omega,e\}\cup\{u_i,p_i,q_i:i\in S\}. { ∞ , ω , e } ∪ { u i , p i , q i : i ∈ S } .
Choose a vertex outside S S S and cut the directed cycle there. The remaining vertices form a directed path, and translation along this path, preserving gaps between the indices in S S S , embeds the generated subsemiring into T ∞ T_\infty T ∞ . Thus every r r r -generated subsemiring of C m C_m C m belongs to U \mathcal{U} U , and consequently C m C_m C m satisfies every identity of T ∞ T_{\infty} T ∞ involving at most r r r variables. If U \mathcal{U} U had a finite basis, choose r r r bounding the number of its variables and then m > max { r , 3 } m > \max\{r, 3\} m > max { r , 3 } . The semiring C m C_m C m would satisfy the basis but violate (14), a contradiction. □ \square □
Proposition 6.4. For every n ≥ 2 n \ge2 n ≥ 2 , U ⊈ V n \mathcal{U} \not\subseteq\mathcal{V}_n U ⊆ V n .
Proof. Let
x 1 y x 2 + x 2 y x 3 + x 3 y x 4 ≈ x 1 y x 2 + x 2 y x 3 + x 3 y x 4 + x 1 y x 4 . (16) x_1yx_2 + x_2yx_3 + x_3yx_4 \approx x_1yx_2 + x_2yx_3 + x_3yx_4 + x_1yx_4. \tag*{(16)} x 1 y x 2 + x 2 y x 3 + x 3 y x 4 ≈ x 1 y x 2 + x 2 y x 3 + x 3 y x 4 + x 1 y x 4 . (16) We verify the identity in A n A_n A n directly from the factor multiplication. If one of the first three summands is ∞ \infty ∞ , their sum is ∞ \infty ∞ , and absorption makes the equation true. Otherwise the three values must coincide with one nonabsorbing factor F \mathbf{F} F of m n m_n m n , by flatness. Express their values as U 1 V U 2 = U 2 V U 3 = U 3 V U 4 = F \mathbf{U}_1\mathbf{V}\mathbf{U}_2 = \mathbf{U}_2\mathbf{V}\mathbf{U}_3 = \mathbf{U}_3\mathbf{V}\mathbf{U}_4 = \mathbf{F} U 1 V U 2 = U 2 V U 3 = U 3 V U 4 = F , with all U i \mathbf{U}_i U i , V \mathbf{V} V nonempty words. Comparing the lengths of the first and second factorizations, and then of the second and third, yields ℓ ( U 1 ) = ℓ ( U 3 ) \ell(\mathbf{U}_1) = \ell(\mathbf{U}_3) ℓ ( U 1 ) = ℓ ( U 3 ) and ℓ ( U 2 ) = ℓ ( U 4 ) \ell(\mathbf{U}_2) = \ell(\mathbf{U}_4) ℓ ( U 2 ) = ℓ ( U 4 ) . The first and third expressions represent the very same word F \mathbf{F} F . Their prefixes of length ℓ ( U 1 ) = ℓ ( U 3 ) \ell(\mathbf{U}_1) = \ell(\mathbf{U}_3) ℓ ( U 1 ) = ℓ ( U 3 ) therefore agree, giving U 1 = U 3 \mathbf{U}_1 = \mathbf{U}_3 U 1 = U 3 ; comparing suffixes in the same way gives U 2 = U 4 \mathbf{U}_2 = \mathbf{U}_4 U 2 = U 4 . Consequently U 1 V U 4 = U 1 V U 2 = F \mathbf{U}_1\mathbf{V}\mathbf{U}_4 = \mathbf{U}_1\mathbf{V}\mathbf{U}_2 = \mathbf{F} U 1 V U 4 = U 1 V U 2 = F , which is exactly the required absorbed fourth summand. In T 4 T_4 T 4 , however, put x i = u i x_i = u_i x i = u i and y = e y = e y = e . The first three summands all equal ω \omega ω , whereas u 1 e u 4 = ∞ u_1eu_4 = \infty u 1 e u 4 = ∞ . Thus (15) fails in T 4 T_4 T 4 , and the assertion follows from T 4 ∈ U T_4 \in\mathcal{U} T 4 ∈ U . □ \square □
Bounded paths and hereditary finite basability
To establish the limit property, we place every proper subvariety of U \mathcal{U} U inside a finitely based variety with a finite subvariety lattice. We use two results of Jackson–Ren–Zhao [11 Lemmas 2.1–2.2] . Every subdirectly irreducible member of the variety generated by flat ai-semirings is flat; we require only this direction, not the converse assertion that every flat ai-semiring is subdirectly irreducible. The variety is axiomatized, within the class of ai-semirings, by the 16 identities
x 1 u x 2 + y 1 u y 2 + y 1 v y 2 ≈ x 1 v x 2 + y 1 u y 2 + y 1 v y 2 , (17) x_1ux_2 + y_1uy_2 + y_1vy_2 \approx x_1vx_2 + y_1uy_2 + y_1vy_2, \tag*{(17)} x 1 u x 2 + y 1 u y 2 + y 1 v y 2 ≈ x 1 v x 2 + y 1 u y 2 + y 1 v y 2 , (17)
where each of the four contexts x 1 x_1 x 1 , x 2 x_2 x 2 , y 1 y_1 y 1 , y 2 y_2 y 2 may independently be omitted. Flat ai-semirings are also ∞ \infty ∞ -cancellative: whenever a b = a c ≠ ∞ ab = ac \ne\infty ab = a c = ∞ , one has b = c b = c b = c ; likewise b a = c a ≠ ∞ ba = ca \ne\infty ba = c a = ∞ entails b = c b = c b = c . Here omission of a context in (16) is an abbreviation for an identity in our unchanged language, not an introduction of a multiplicative identity.
Define the ambient variety F \mathcal{F} F by the following finite set of identities. Throughout this paragraph, κ \kappa κ denotes a term abbreviation for the common value of all cubes, not a new constant symbol:
x 3 ≈ y 3 , x + x 3 ≈ x 3 , x 2 ≈ x 3 , x 4 ≈ x 3 , x y z t ≈ x 3 . (18) x^3 \approx y^3,\qquad x + x^3 \approx x^3,\qquad x^2 \approx x^3,\qquad x^4 \approx x^3,\qquad xyzt \approx x^3. \tag*{(18)} x 3 ≈ y 3 , x + x 3 ≈ x 3 , x 2 ≈ x 3 , x 4 ≈ x 3 , x y z t ≈ x 3 . (18)
In F \mathcal{F} F , κ \kappa κ is both the additive maximum and multiplicative zero, represented by a term rather than a named constant. In the next family, w ∈ { q y r , r y a } \mathsf{w} \in\{qyr, rya\} w ∈ { q y r , r y a } and w ′ ∈ { b y s , s y b } \mathsf{w}' \in\{bys, syb\} w ′ ∈ { b y s , sy b } abbreviate the corresponding finitely many word identities; w , w ′ \mathsf{w}, \mathsf{w}' w , w ′ are not new variables. In addition to the ai-semiring axioms and (16) and (17), require
x y z + u v w ≈ x y z + u v w + x v z (19) xyz+uvw \approx xyz+uvw+xvz \tag*{(19)} x y z + uv w ≈ x y z + uv w + xv z (19)
x y z + y t ≈ κ , x y z + t y ≈ κ (20) xyz+yt \approx\kappa,\qquad xyz+ty \approx\kappa \tag*{(20)} x y z + y t ≈ κ , x y z + t y ≈ κ (20)
w + w ′ + a b ≈ κ (21) \mathbf{w}+\mathbf{w}^{\prime}+ab \approx\kappa \tag*{(21)} w + w ′ + ab ≈ κ (21)
w + a b + b d ≈ κ , w + d b + b a ≈ κ (22) \mathbf{w}+ab+bd \approx\kappa,\qquad\mathbf{w}+db+ba \approx\kappa \tag*{(22)} w + ab + b d ≈ κ , w + d b + ba ≈ κ (22)
x y + y z + z t ≈ κ . (23) xy+yz+zt \approx\kappa. \tag*{(23)} x y + y z + z t ≈ κ . (23)
Here κ \kappa κ abbreviates the cube of a fresh variable; all the displayed identities belong to the constant-free language.
We verify the five additional families in T ∞ T_{\infty} T ∞ . A sum in a flat semiring is different from ∞ \infty ∞ only when all its summands have the same non-top value. The only non-top triple products in T ∞ T_{\infty} T ∞ are u i e u i + 1 = ω u_i e u_{i+1}=\omega u i e u i + 1 = ω , and the only binary products with value ω \omega ω are
p i u i + 1 = ω = u i q i + 1 ( i ≥ 1 ) . p_i u_{i+1}=\omega=u_i q_{i+1}\qquad(i\geq1). p i u i + 1 = ω = u i q i + 1 ( i ≥ 1 ) .
For (18), the identity is automatic if one of x y z xyz x y z , u v w uvw uv w equals ∞ \infty ∞ . Otherwise both are ω \omega ω , and their middle factors y y y , v v v are both e e e ; thus x v z = x y z = ω xvz=xyz=\omega xv z = x y z = ω . For (19), if x y z = ω xyz=\omega x y z = ω , then y = e y=e y = e ; no product e t et e t or t e te t e equals ω \omega ω , so each displayed sum equals ∞ \infty ∞ . For (20), if both w \mathbf{w} w , w ′ \mathbf{w}^{\prime} w ′ have value ω \omega ω , their distinguished variables a a a , b b b are vertices u i u_i u i , u j u_j u j , respectively, and a b = ∞ ab=\infty ab = ∞ . This argument applies separately to both placements of a a a and both placements of b b b in the abbreviations defining w \mathbf{w} w , w ′ \mathbf{w}^{\prime} w ′ . For (21), a non-top w \mathbf{w} w again forces a = u i a=u_i a = u i for some i i i . The only possible non-top a b ab ab is u i q i + 1 = ω u_iq_{i+1}=\omega u i q i + 1 = ω , whereas every product with left factor q i + 1 q_{i+1} q i + 1 equals ∞ \infty ∞ ; hence a b ab ab and b d bd b d cannot both equal ω \omega ω . Similarly, if b a = ω ba=\omega ba = ω , then b = p i − 1 b=p_{i-1} b = p i − 1 (when defined), and no product d b db d b equals ω \omega ω . Thus each of the two identities in (21) holds. Finally, the directed graph of the binary products with value ω \omega ω has only the one- and two-edge chains p i , u i + 1 , q i + 2 p_i,u_{i+1},q_{i+2} p i , u i + 1 , q i + 2 , whose consecutive products are ω \omega ω (with any missing terminal edge omitted). In particular, there is no chain of three such products, which proves (22). Hence
U ⊆ F . \mathcal{U}\subseteq\mathcal{F}. U ⊆ F .
The identities χ m \chi_m χ m in (14) involve a closed cycle, whereas the following identities describe open directed paths. They are not interchangeable by reindexing. For N ≥ 1 N\geq1 N ≥ 1 , define D N ⊆ F D_N\subseteq\mathcal{F} D N ⊆ F by
Φ N : ∑ i = 0 N x i y x i + 1 ≈ κ . \Phi_N:\qquad\sum_{i=0}^{N}x_i y x_{i+1}\approx\kappa. Φ N : i = 0 ∑ N x i y x i + 1 ≈ κ .
The displayed axioms form a finite basis for D N D_N D N . The same variety is locally finite: by (17), every term is a sum of words of length at most three or has value κ \kappa κ . Thus an r r r -generated member has at most 2 r + r 2 + r 3 + 1 2^{r+r^2+r^3}+1 2 r + r 2 + r 3 + 1 elements.
Proposition 6.5. Let S S S be a nontrivial finite subdirectly irreducible member of F \mathcal{F} F . There is a unique element ω ≠ ∞ \omega\ne\infty ω = ∞ with ω S = S ω = { ∞ } \omega S=S\omega=\{\infty\} ω S = S ω = { ∞ } . If S S S has a nonabsorbing triple product, all such products equal ω \omega ω and have the same middle factor e e e . Put
A = { a : a is an endpoint of a nonabsorbing triple } . A=\{a:a\text{ is an endpoint of a nonabsorbing triple}\}. A = { a : a is an endpoint of a nonabsorbing triple } . Define a directed edge a → b a\to b a → b on A A A precisely when a e b = ω aeb=\omega a e b = ω .
B = { p a = a e : a → b for some b } , C = { q b = e b : a → b for some a } , B=\{p_a=ae:a\to b\text{ for some }b\},\qquad C=\{q_b=eb:a\to b\text{ for some }a\}, B = { p a = a e : a → b for some b } , C = { q b = e b : a → b for some a } ,
and let R = S ∖ ( { ∞ , ω , e } ∪ A ∪ B ∪ C ) \mathcal{R}=S\setminus(\{\infty,\omega,e\}\cup A\cup B\cup C) R = S ∖ ({ ∞ , ω , e } ∪ A ∪ B ∪ C ) . These sets form a disjoint union
S = { ∞ , ω , e } ∪ ˙ A ∪ ˙ B ∪ ˙ C ∪ ˙ R . S=\{\infty,\omega,e\}\mathbin{\dot\cup}A\mathbin{\dot\cup}B\mathbin{\dot\cup}C\mathbin{\dot\cup}\mathcal{R}. S = { ∞ , ω , e } ∪ ˙ A ∪ ˙ B ∪ ˙ C ∪ ˙ R .
The digraph ( A , → ) (A,\to) ( A , → ) has indegree and outdegree at most one. Each of its finite acyclic components is a directed path; it may have at most one incoming R \mathcal{R} R -leaf at its initial vertex and one outgoing R \mathcal{R} R -leaf at its terminal vertex. The other members of R \mathcal{R} R form disjoint directed paths of one or two edges under r s = ω rs=\omega r s = ω . Products of elements from distinct components are ∞ \infty ∞ , apart from interactions with the common element e e e . If there is no nonabsorbing triple product, the digraph with vertex set S ∖ { ∞ , ω } S\setminus\{\infty,\omega\} S ∖ { ∞ , ω } and edge relation x ⇝ y x\rightsquigarrow y x ⇝ y defined by x y = ω xy=\omega x y = ω is a disjoint union of directed paths with one or two edges.
Proof. 1. The unique terminal element. Fix s ≠ ∞ s\ne\infty s = ∞ . Starting with the one-factor word s s s , extend it on either side as long as its value remains non-top. No non-top product has four factors, so a word of maximal possible length is reached after at most three factors. Its value w w w satisfies w S = S w = { ∞ } wS=Sw=\{\infty\} w S = S w = { ∞ } ; otherwise another non-top extension would be possible. Thus for every non-top element s s s there is a finite sequence of non-top values
s = s 0 , s 1 , … , s r = w , w S = S w = { ∞ } , s=s_0,s_1,\ldots,s_r=w,\qquad wS=Sw=\{\infty\}, s = s 0 , s 1 , … , s r = w , w S = S w = { ∞ } ,
where each s i + 1 s_{i+1} s i + 1 is obtained by multiplying s i s_i s i on the left or right by an element of S S S . If w ≠ w ′ w\ne w' w = w ′ are terminal, then { ∞ , w } \{\infty,w\} { ∞ , w } and { ∞ , w ′ } \{\infty,w'\} { ∞ , w ′ } are ideals: flat addition keeps sums with these sets inside them, and multiplication always gives ∞ \infty ∞ . Their Rees congruences identify respectively just the pairs ( ∞ , w ) (\infty,w) ( ∞ , w ) and ( ∞ , w ′ ) (\infty,w') ( ∞ , w ′ ) (and their reverses), so each is nontrivial while their intersection is the diagonal congruence. This contradicts subdirect irreducibility. Thus the terminal element ω \omega ω is unique. Every nonabsorbing triple product is terminal and hence equals ω \omega ω .
Common middle factor of nonabsorbing triples. Suppose now that a nonabsorbing triple exists. If a b c = a ′ b ′ c ′ = ω abc=a'b'c'=\omega ab c = a ′ b ′ c ′ = ω , substitute the two triples into (18). Since the first two summands both have value ω \omega ω , flat addition forces the added summand a b ′ c ab'c a b ′ c to have that same value ω \omega ω : otherwise the sum would be ∞ \infty ∞ . From a b c = a b ′ c = ω ≠ ∞ abc=ab'c=\omega\ne\infty ab c = a b ′ c = ω = ∞ , left ∞ \infty ∞ -cancellation gives b c = b ′ c bc=b'c b c = b ′ c ; right ∞ \infty ∞ -cancellation then gives b = b ′ b=b' b = b ′ . Call this common middle factor e e e . Its square is ∞ \infty ∞ , and neither e e e nor any endpoint of a nonabsorbing triple can be the value of a nonabsorbing binary product: substituting such a binary product into the indicated triple would give a nonabsorbing product of four factors.
Let x y = d ∉ { ∞ , ω } xy=d\notin\{\infty,\omega\} x y = d ∈ / { ∞ , ω } . Since d d d is not terminal, some z z z satisfies d z = ω dz=\omega d z = ω or z d = ω zd=\omega z d = ω . If x y z = ω xyz=\omega x y z = ω , uniqueness of the middle factor gives y = e y=e y = e , x , z ∈ A x,z\in A x , z ∈ A , and d = e y d=ey d = ey . If z x y = ω zxy=\omega z x y = ω , it gives x = e x=e x = e , z , y ∈ A z,y\in A z , y ∈ A , and d = e y d=ey d = ey . Thus every nonterminal binary value has the form a e ae a e or e b eb e b with a , b ∈ A a,b\in A a , b ∈ A . These two forms cannot represent the same nonterminal element. Indeed, suppose d = a e = e b ′ d=ae=eb' d = a e = e b ′ for a , b ′ ∈ A a,b'\in A a , b ′ ∈ A . From d = a e d=ae d = a e and the nonterminality of d d d , its extension to a nonabsorbing triple must be on the right: there is b ∈ A b\in A b ∈ A with
d b = ( a e ) b = ω . db=(ae)b=\omega. d b = ( a e ) b = ω .
But then ( e b ′ ) b = ω (eb')b=\omega ( e b ′ ) b = ω is a nonabsorbing triple with middle factor b ′ ≠ e b'\ne e b ′ = e , contrary to the uniqueness of the middle factor e e e . Hence the two possibilities are disjoint. Moreover, applying (19) to a triple with middle factor e e e shows that e t ≠ ω et\ne\omega e t = ω and t e ≠ ω te\ne\omega t e = ω for every t t t . Thus a e ae a e or e b eb e b , if nonabsorbing, is nonterminal. It must extend in a triple: a e ae a e cannot extend to the left, as the resulting triple would have middle factor a ≠ e a \ne e a = e , and e b eb e b cannot extend to the right. Consequently, a e ae a e is nonabsorbing if and only if a → b a \to b a → b for some b b b . Likewise, e b eb e b is nonabsorbing if and only if a → b a \to b a → b for some a a a . The p a p_a p a are pairwise distinct, as are the q b q_b q b , by cancellation. Nor can p a = q b = d p_a=q_b=d p a = q b = d : a nonterminal element d d d extends to d z = ω dz=\omega d z = ω or z d = ω zd=\omega z d = ω ; the first would make e b z = ω ebz=\omega e b z = ω with middle factor b ≠ e b \ne e b = e , while the second would make z a e = ω zae=\omega z a e = ω with middle factor a ≠ e a \ne e a = e . The same length-four argument above separates B , C \mathcal{B},\mathcal{C} B , C from A ∪ { e } \mathcal{A}\cup\{e\} A ∪ { e } , and ω \omega ω is terminal. This proves the asserted disjointness.
Cancellation makes the edge relation functional in both directions: if a → b a\to b a → b and a → c a\to c a → c , then b = c b=c b = c ; if a → c a\to c a → c and b → c b\to c b → c , then a = b a=b a = b . Associativity also identifies the two products associated with an edge. Whenever p a p_a p a and q b q_b q b are defined, each of the following conditions holds if and only if the others do:
p a b = ω , a → b , a q b = ω . (24) p_ab=\omega,\qquad a\to b,\qquad aq_b=\omega. \tag*{(24)} p a b = ω , a → b , a q b = ω . (24)
3. Classification of nonabsorbing products. We classify products by ordered factor type. Apart from A e ⊆ B ∪ { ∞ } Ae\subseteq B\cup\{\infty\} A e ⊆ B ∪ { ∞ } , e A ⊆ C ∪ { ∞ } eA\subseteq C\cup\{\infty\} e A ⊆ C ∪ { ∞ } and (23), only A R AR A R , R A RA R A and R R RR R R may take the nonabsorbing value ω \omega ω . To exclude the other cases, note that A A = ∞ AA=\infty AA = ∞ by (20) and the nonterminal-value classification. Products with two factors in B ∪ C B\cup C B ∪ C have length at least four. The types A B , C A , e B , C e , R B , C R AB,CA,eB,Ce,RB,CR A B , C A , e B , C e , R B , C R would give a triple with middle factor other than e e e ; B e , e C Be,eC B e , e C contain e 2 e^2 e 2 ; and B R , R C BR,RC B R , R C would force an R R R -element to be a triple endpoint. Finally, e R , R e eR,Re e R , R e cannot be nonterminal and are excluded by (19). Products involving ω \omega ω or ∞ \infty ∞ equal ∞ \infty ∞ . Thus the complete table is as follows, where ω / ∞ \omega/\infty ω /∞ denotes the two permitted possibilities subject to the edge relations:
Table 1.
To read the table, note for example that a non-top product in B A BA B A must be p a b = ( a e ) b = ω p_ab=(ae)b=\omega p a b = ( a e ) b = ω , hence comes from the triple a e b aeb a e b ; conversely every edge a → b a\to b a → b forces this product and also a ( e b ) = ω a(eb)=\omega a ( e b ) = ω . For a factor in C C C on the left, ( e b ) t (eb)t ( e b ) t would be a non-top triple with middle factor b ≠ e b\ne e b = e ; for a factor in B B B on the right, t ( a e ) t(ae) t ( a e ) would have middle factor a ≠ e a\ne e a = e . These eliminate entire ordered rows or columns, rather than relying on an implicit symmetry. The table describes possible values, not independent choices for its ω / ∞ \omega/\infty ω /∞ entries. The products involving e e e and the edge products p a b p_ab p a b , a q b aq_b a q b are determined by → \to → ; the only residual types are A R AR A R , R A RA R A , and R R RR R R , whose nonabsorbing values must equal ω \omega ω . We now determine which such products can occur.
4. Directed paths and possible attached leaves. It remains to restrict the terminal products of types A R AR A R , R A RA R A , and R R RR R R . Write x ∼ y x\sim y x ∼ y when x y = ω xy=\omega x y = ω . Fix a nonabsorbing triple a e b = ω aeb=\omega a e b = ω with a , b ∈ A a,b\in A a , b ∈ A . For any a , b ∈ A a,b\in A a , b ∈ A , choose a non-top triple with a a a as an endpoint and another with b b b as an endpoint. Each can be written in one of the forms a y r ayr a y r , r y a rya r y a and b y s bys b y s , s y b syb sy b , respectively. If a b = ω ab=\omega ab = ω , all three summands in the corresponding instance of (20) equal ω \omega ω , contradicting that identity. Hence a b ≠ ω ab\ne\omega ab = ω . This argument covers all four choices of endpoint positions, not only triples having a a a and b b b in their first positions. No such product can be a nonterminal value either, by the already established classification of nonterminal binary products. Thus A A = ∞ AA=\infty AA = ∞ .
The remaining possibilities are excluded without any graph terminology. If x ∈ B x \in\mathcal{B} x ∈ B and x y ≠ ∞ xy \ne\infty x y = ∞ , write x = a e x=ae x = a e ; then ( a e ) y = ω (ae)y=\omega ( a e ) y = ω and a e y = ω aey=\omega a ey = ω , so y ∈ A y \in A y ∈ A . If y ∈ C y \in C y ∈ C and x y ≠ ∞ xy \ne\infty x y = ∞ , write y = e b y=eb y = e b ; then x ( e b ) = ω x(eb)=\omega x ( e b ) = ω and x e b = ω xeb=\omega x e b = ω , so x ∈ A x \in A x ∈ A . If x ∈ C x \in C x ∈ C , a nonabsorbing x y xy x y would make e b y eby e b y a triple with middle factor b ∈ A b \in A b ∈ A , contrary to the uniqueness of e e e . Dually, a nonabsorbing x y xy x y with y ∈ B y \in\mathcal{B} y ∈ B would make x a e xae x a e a triple with middle factor a ∈ A a \in A a ∈ A . A nonabsorbing product involving e e e can only be a e ∈ B ae \in\mathcal{B} a e ∈ B or e b ∈ C eb \in C e b ∈ C : the other alternatives either force a triple with middle factor distinct from e e e , or contradict (19) when their value is ω \omega ω . Finally, no element of R \mathcal{R} R can be a factor of a nonterminal product. To see this, suppose x y = d ∉ { ∞ , ω } xy=d \notin\{\infty,\omega\} x y = d ∈ / { ∞ , ω } . By the preceding extension argument, either x y z = ω xyz=\omega x y z = ω for some z z z , in which case y = e y=e y = e and x ∈ A x \in A x ∈ A , or z x y = ω zxy=\omega z x y = ω , in which case x = e x=e x = e and y ∈ A y \in A y ∈ A . Thus neither x x x nor y y y belongs to R \mathcal{R} R . In particular, for r ∈ R r \in\mathcal{R} r ∈ R , neither e r er er nor r e re r e can be nonterminal; neither can equal ω \omega ω , by (19). Hence
e R ⊆ { ∞ } , R e ⊆ { ∞ } . e\mathcal{R} \subseteq\{\infty\}, \qquad\mathcal{R}e \subseteq\{\infty\}. e R ⊆ { ∞ } , R e ⊆ { ∞ } .
The same argument excludes R \mathcal{R} R from all other nonterminal product types. This proves that the displayed multiplication table lists all nonabsorbing binary products.
Cancellation makes the relation ⇝ \rightsquigarrow ⇝ have at most one outgoing and one incoming edge at each vertex. Identity (22) forbids a walk of three such edges: if x ⇝ y ⇝ z ⇝ t x \rightsquigarrow y \rightsquigarrow z \rightsquigarrow t x ⇝ y ⇝ z ⇝ t , then x y + y z + z t = ω ≠ κ xy+yz+zt=\omega\ne\kappa x y + y z + z t = ω = κ . Since every square is κ = ∞ \kappa=\infty κ = ∞ , loops are impossible. A two-cycle would contradict (22) by taking ( x , y , z , t ) = ( r , s , r , s ) (x,y,z,t)=(r,s,r,s) ( x , y , z , t ) = ( r , s , r , s ) ; a cycle of length at least three contains a three-edge walk and is also excluded.
Identity (21) forbids a two-edge ⇝ \rightsquigarrow ⇝ -walk whose initial or terminal vertex belongs to A A A . To see the first assertion, let a ∈ A a \in A a ∈ A and choose one of the words w = a y r \mathbf{w}=ayr w = a y r or w = r y a \mathbf{w}=rya w = r y a which expresses a nonabsorbing triple with a a a in the indicated end position. If a ⇝ b ⇝ d a \rightsquigarrow b \rightsquigarrow d a ⇝ b ⇝ d , then w + a b + b d = ω ≠ κ \mathbf{w}+ab+bd=\omega\ne\kappa w + ab + b d = ω = κ , contradicting the first identity in (21). If instead d ⇝ b ⇝ a d \rightsquigarrow b \rightsquigarrow a d ⇝ b ⇝ a , use w + d b + b a \mathbf{w}+db+ba w + d b + ba and the second identity. The choice of w \mathbf{w} w is possible because every a ∈ A a \in A a ∈ A is an endpoint of a triple. If r ⇝ a r \rightsquigarrow a r ⇝ a for r ∈ R r \in\mathcal{R} r ∈ R , a ∈ A a \in A a ∈ A , then a a a has no incoming edge b → a b \to a b → a , since otherwise p b a = r a = ω pba=ra=\omega p ba = r a = ω and right cancellation gives r = p b ∈ B r=pb \in\mathcal{B} r = p b ∈ B . As every member of A A A occurs in some triple, a a a is therefore the initial vertex of its → \to → -component. Likewise, a ⇝ r a \rightsquigarrow r a ⇝ r can occur only at the terminal vertex. There is at most one such leaf at either end, and an attached R \mathcal{R} R -vertex has no further incident ⇝ \rightsquigarrow ⇝ -edge, by the two-edge restriction (and cancellation). Every remaining r ∈ R r \in\mathcal{R} r ∈ R has an incident ⇝ \rightsquigarrow ⇝ -edge: otherwise r r r would be another terminal element. Its edges join it only to members of R \mathcal{R} R , by the preceding multiplication classification. Such components are directed paths of one or two edges. Here a component includes its A A A -vertices, the associated p a , q b p_a,q_b p a , q b , and any R \mathcal{R} R -leaves attached to its endpoints; other R \mathcal{R} R -paths are separate components. Every non-top product listed in the table either has both non-e e e factors in the same such component or involves e e e . Thus products between distinct components are ∞ \infty ∞ , with e e e serving as the only common nonterminal multiplier.
Thus no other residual nonabsorbing product is possible: R A \mathcal{R}A R A and A R A\mathcal{R} A R can attach leaves only at the initial and terminal vertices, respectively, while R R \mathcal{R}\mathcal{R} RR -edges form directed paths of at most two edges. The exclusions above follow from cancellation and (21)–(22).
The case without nonabsorbing triples. If there is no nonabsorbing triple, every nonabsorbing binary product must equal ω \omega ω , since any other binary value could be
extended to such a triple. Cancellation and (22) make the resulting digraph a union of directed paths of at most two edges; all vertices outside { ∞ , ω } \{\infty,\omega\} { ∞ , ω } lie on such an edge. Indeed, an element outside this pair with no incident non-top product would itself be terminal, contradicting uniqueness of ω \omega ω . This argument is independent of the case with a common middle factor.
A finite semiring S S S is called critical if it does not belong to the variety generated by its proper subsemirings and proper homomorphic images.
Proposition 6.6. For every N ≥ 1 N \ge1 N ≥ 1 , D N D_N D N has finitely many subvarieties, and each of them is finitely based.
Proof. 1. Bounded component types. Let S S S be a finite nontrivial subdirectly irreducible member of D N D_N D N . The graph ( A , → ) (A,\to) ( A , → ) of Proposition 6.5, when present, has no directed walk a 0 → a 1 → ⋯ → a N + 1 a_0 \to a_1 \to\cdots\to a_{N+1} a 0 → a 1 → ⋯ → a N + 1 . Indeed, the substitution x i ↦ a i x_i \mapsto a_i x i ↦ a i and y ↦ e y \mapsto e y ↦ e would send every summand x i y x i + 1 x_i y x_{i+1} x i y x i + 1 of Φ N \Phi_N Φ N to ω \omega ω , and hence its left side to ω ≠ ∞ = κ \omega\ne\infty= \kappa ω = ∞ = κ . This contradicts S ⊨ Φ N S \models\Phi_N S ⊨ Φ N . Thus its components are directed paths of at most N N N edges. A component with j j j edges has j + 1 j+1 j + 1 vertices, j j j elements of B \mathcal{B} B , j j j of C \mathcal{C} C and at most two attached R \mathcal{R} R -leaves, hence at most 3 j + 3 3j+3 3 j + 3 elements outside the common part K = { ∞ , ω , e } K=\{\infty,\omega,e\} K = { ∞ , ω , e } . Up to isomorphism fixing K K K , there are at most four types for each 1 ≤ j ≤ N 1 \le j \le N 1 ≤ j ≤ N , according to the two optional leaves. There are also the one- and two-edge components made entirely of R \mathcal{R} R -vertices. In the no-triple case the common part is K = { ∞ , ω } K=\{\infty,\omega\} K = { ∞ , ω } and only the last two types occur. Therefore there are at most 4 N + 2 4N+2 4 N + 2 types in either case, each with at most 3 N + 3 3N+3 3 N + 3 elements outside K K K . The set K K K is a common subsemiring, not the kernel of a homomorphism. Both operations on K K K close in K K K ; the component classification shows that products of elements from distinct components are ∞ \infty ∞ , whereas operations within one component, including those with e ∈ K e \in K e ∈ K , stay in that component together with K K K . For addition, distinct non-top elements likewise sum to ∞ \infty ∞ .
Removing repeated components. Suppose a component type occurs r ≥ 3 r \ge3 r ≥ 3 times. We show that one of these components can be removed without changing the generated variety. Components here are the blocks outside K K K , with the same common part K K K ; an occurrence of a type means an isomorphism fixing K K K and preserving all products with elements of K K K . Let S r e d S_{\mathrm{red}} S red be obtained by deleting the elements outside K K K of one such component. The multiplication description in Proposition 6.5 shows that S r e d S_{\mathrm{red}} S red is a proper subsemiring. Choose two retained components of this type, numbered 1 , 2 1,2 1 , 2 , and distinct words c 1 , … , c r ∈ { 1 , 2 } d c_1,\ldots,c_r \in\{1,2\}^d c 1 , … , c r ∈ { 1 , 2 } d with 2 d ≥ r 2^d \ge r 2 d ≥ r . Fix isomorphisms of all r r r components onto each of the two retained components, acting identically on K K K . For an element s s s in component i i i let the t t t -th coordinate of ι ( s ) \iota(s) ι ( s ) be its image in component c i ( t ) c_i(t) c i ( t ) . Map the elements of K K K and of other types diagonally. The resulting map of underlying sets ι : S → ( S r e d ) d \iota:S\to(S_{\mathrm{red}})^d ι : S → ( S red ) d is injective, but need not preserve the operations. Indeed, distinct original components may share the same retained component in some coordinates, so a product that is ∞ \infty ∞ in S S S need not have value ι ( ∞ ) \iota(\infty) ι ( ∞ ) in every coordinate. The homomorphism will be obtained only after taking a Rees quotient. Let C = ι ( S ) C=\iota(S) C = ι ( S ) and set
I = { v ∈ C : some coordinate of v equals ∞ } . I=\{v\in C:\text{ some coordinate of }v\text{ equals }\infty\}. I = { v ∈ C : some coordinate of v equals ∞ } .
The vector ( ∞ , … , ∞ ) = ι ( ∞ ) (\infty,\ldots,\infty)=\iota(\infty) ( ∞ , … , ∞ ) = ι ( ∞ ) lies in I I I , whereas ι ( s ) ∉ I \iota(s)\notin I ι ( s ) ∈ / I whenever s ≠ ∞ s\ne\infty s = ∞ , so I I I is nonempty and proper. Since a coordinate equal to ∞ \infty ∞ stays equal to ∞ \infty ∞ under either addition or multiplication with any other coordinate, I I I is absorbing under both operations against elements of C C C . The relation identifying all members of I I I and leaving C ∖ I C \setminus I C ∖ I as singletons is therefore a congruence for each basic operation; the Rees quotient C / I C/I C / I is a semiring.
Verification of the quotient homomorphism
We verify the induced map into the Rees quotient for both basic operations and then prove injectivity. For ∘ ∈ { + , ⋅ } \circ\in\{+,\cdot\} ∘ ∈ { + , ⋅ } , first suppose s ∘ t ≠ ∞ s \circ t \ne\infty s ∘ t = ∞ . Then either s , t s,t s , t belong to the same component together with K K K , or one belongs to K K K . The distinguished common part is fixed pointwise by every chosen component isomorphism; in particular, this includes the cases e a ea e a and a e ae a e , as well as products involving ω \omega ω . On each coordinate, the chosen component isomorphism preserves ∘ \circ ∘ ; hence
ι ( s ) ∘ ι ( t ) = ι ( s ∘ t ) . \iota(s) \circ\iota(t) = \iota(s \circ t). ι ( s ) ∘ ι ( t ) = ι ( s ∘ t ) .
If s ∘ t = ∞ s \circ t = \infty s ∘ t = ∞ , either the corresponding operation is already ∞ \infty ∞ inside one component or with K K K (and hence is ∞ \infty ∞ in every coordinate), or s , t s,t s , t belong to different components. For two different original components of the same repeated type, their codes differ in some coordinate. In that coordinate their images outside K K K lie in different retained components, so both their sum and product are ∞ \infty ∞ . Thus distinct binary codes are essential: assigning every original component to a single retained copy would not preserve the absorbing products. Components of different types remain distinct in every coordinate and give the same conclusion. Thus in all cases ι ( s ) ∘ ι ( t ) ∈ I \iota(s) \circ\iota(t) \in I ι ( s ) ∘ ι ( t ) ∈ I . The case s = t s=t s = t for addition follows by idempotence.
Thus, for ∘ ∈ { + , ⋅ } \circ\in\{+,\cdot\} ∘ ∈ { + , ⋅ } , we have established
{ ι ( s ) ∘ ι ( t ) = ι ( s ∘ t ) , s ∘ t ≠ ∞ , ι ( s ) ∘ ι ( t ) ∈ I , s ∘ t = ∞ . \begin{cases}
\iota(s) \circ\iota(t) = \iota(s \circ t), & s \circ t \ne\infty,\\
\iota(s) \circ\iota(t) \in I, & s \circ t = \infty.
\end{cases} { ι ( s ) ∘ ι ( t ) = ι ( s ∘ t ) , ι ( s ) ∘ ι ( t ) ∈ I , s ∘ t = ∞ , s ∘ t = ∞.
All products whose original value is ∞ \infty ∞ therefore become the ideal class of the Rees quotient. No ι ( s ) \iota(s) ι ( s ) with s ≠ ∞ s \ne\infty s = ∞ belongs to I I I : component isomorphisms take non-top elements to non-top elements, and K K K is mapped diagonally. If s , t s,t s , t are distinct members of a single component, injectivity of its component isomorphism separates their images in every coordinate. If they belong to different repeated components, their distinct binary codes separate them in at least one coordinate, where their images lie in different retained components; distinct component types remain separate in every coordinate. Elements of K K K are also distinct from images outside K K K . Thus different non-top elements have different images in the Rees quotient. Define
π : S ⟶ C / I , π ( s ) = { I , s = ∞ , [ ι ( s ) ] , s ≠ ∞ . \pi:S \longrightarrow C/I,\qquad
\pi(s)=
\begin{cases}
I, & s=\infty,\\
[\iota(s)], & s\ne\infty.
\end{cases} π : S ⟶ C / I , π ( s ) = { I , [ ι ( s )] , s = ∞ , s = ∞.
The two cases above yield, for both ∘ = + \circ=+ ∘ = + and ∘ = ⋅ \circ=\cdot ∘ = ⋅ ,
π ( s ∘ t ) = π ( s ) ∘ π ( t ) : \pi(s\circ t)=\pi(s)\circ\pi(t): π ( s ∘ t ) = π ( s ) ∘ π ( t ) :
if s ∘ t ≠ ∞ s\circ t\ne\infty s ∘ t = ∞ , its image remains a nonideal class and coordinatewise operations agree; if s ∘ t = ∞ s\circ t=\infty s ∘ t = ∞ , at least one coordinate has value ∞ \infty ∞ and both sides are the ideal class. The separation argument proves that π \pi π is injective. For surjectivity, we prove by induction on the formation of terms over the generating set ι ( S ) \iota(S) ι ( S ) that every element v ∈ C v\in C v ∈ C either lies in I I I or equals ι ( s ) \iota(s) ι ( s ) for some s ∈ S ∖ { ∞ } s\in S\setminus\{\infty\} s ∈ S ∖ { ∞ } . For a generator, this holds by definition of ι \iota ι (the generator ι ( ∞ ) \iota(\infty) ι ( ∞ ) lies in I I I ). Suppose it holds for v 1 , v 2 ∈ C v_1,v_2\in C v 1 , v 2 ∈ C and put v = v 1 ∘ v 2 v=v_1\circ v_2 v = v 1 ∘ v 2 , with ∘ ∈ { + , ⋅ } \circ\in\{+,\cdot\} ∘ ∈ { + , ⋅ } . If some v i ∈ I v_i\in I v i ∈ I , then v ∈ I v\in I v ∈ I because I I I is absorbing under both operations. Otherwise write v i = ι ( s i ) v_i=\iota(s_i) v i = ι ( s i ) with s i ≠ ∞ s_i\ne\infty s i = ∞ . The two-case calculation above gives either v = ι ( s 1 ∘ s 2 ) v=\iota(s_1\circ s_2) v = ι ( s 1 ∘ s 2 ) when s 1 ∘ s 2 ≠ ∞ s_1\circ s_2\ne\infty s 1 ∘ s 2 = ∞ , or v ∈ I v\in I v ∈ I when s 1 ∘ s 2 = ∞ s_1\circ s_2=\infty s 1 ∘ s 2 = ∞ . This completes the induction and yields
C ∖ I = ι ( S ∖ { ∞ } ) . C\setminus I=\iota(S\setminus\{\infty\}). C ∖ I = ι ( S ∖ { ∞ }) .
Thus every nonideal class of C / I C/I C / I is π ( s ) \pi(s) π ( s ) for some s ≠ ∞ s\ne\infty s = ∞ , while the ideal class is π ( ∞ ) \pi(\infty) π ( ∞ ) . Therefore π \pi π is surjective, and
S ≅ C / I ∈ HS ( ( S r e d ) d ) . S\cong C/I\in\operatorname{HS}((S_{\mathrm{red}})^d). S ≅ C / I ∈ HS (( S red ) d ) .
In particular, S S S belongs to the variety generated by the proper subsemiring S r e d S_{\mathrm{red}} S red , not merely to a class generated by another semiring of unbounded size. Consequently a critical member of D N \mathcal{D}_N D N cannot contain three components of the same type. The common part K K K , including e e e when present, is retained. The two surviving copies provide the distinct code symbols needed to separate original components.
4. Uniform bound for critical members. We now obtain a uniform bound for critical algebras. A critical finite semiring must be subdirectly irreducible: otherwise two nontrivial congruences with diagonal intersection provide a subdirect embedding into a product of proper homomorphic images. This contradicts criticality. The same argument applies to a finite subdirect decomposition by selecting a finite separating family of kernels. Thus every critical member of D N \mathcal{D}_N D N satisfies
∣ S ∣ ≤ ∣ K ∣ + 2 ⋅ ( number of component types ) ⋅ ( maximum component size ) ≤ 3 + 2 ( 4 N + 2 ) ( 3 N + 3 ) . |S|\le|K|+2\cdot(\text{number of component types})\cdot(\text{maximum component size})
\le3+2(4N+2)(3N+3). ∣ S ∣ ≤ ∣ K ∣ + 2 ⋅ ( number of component types ) ⋅ ( maximum component size ) ≤ 3 + 2 ( 4 N + 2 ) ( 3 N + 3 ) .
There are only finitely many isomorphism types below this bound because the language has two binary operations and a finite universe admits only finitely many such operation tables. Every subvariety of the locally finite D N \mathcal{D}_N D N is generated by its finite members and, by induction on their orders, by its critical members: each noncritical member belongs to the variety generated by its proper subsemirings and homomorphic images. Hence D N \mathcal{D}_N D N has only finitely many subvarieties.
5. Finite subvariety lattices and finite bases. Let X ⊊ Y \mathcal{X}\subsetneq\mathcal{Y} X ⊊ Y be a cover relation in the finite lattice of subvarieties of D N \mathcal{D}_N D N . Choose an identity valid in X \mathcal{X} X but failing in Y \mathcal{Y} Y . Within Y \mathcal{Y} Y , the models of this identity form a subvariety containing X \mathcal{X} X but properly contained in Y \mathcal{Y} Y ; by the cover property, this subvariety must equal X \mathcal{X} X . Choose a finite saturated chain descending from D N \mathcal{D}_N D N to an arbitrary subvariety. One separating identity for each cover in the chain, together with the finite axiom set of D N \mathcal{D}_N D N , defines the final subvariety. This proves its finite basability. □
Theorem 6.7. The variety V ( T ∞ ) \mathcal{V}(T_\infty) V ( T ∞ ) is a limit variety. Moreover, for each n ≥ 2 n\ge2 n ≥ 2 ,
V ( T ∞ ) ⊆ W n , V ( T ∞ ) ⊈ V n . \mathcal{V}(T_\infty)\subseteq\mathcal{W}_n,\qquad\mathcal{V}(T_\infty)\nsubseteq\mathcal{V}_n. V ( T ∞ ) ⊆ W n , V ( T ∞ ) ⊈ V n .
Proof. We prove that every proper subvariety X ⊊ U \mathcal{X}\subsetneq\mathcal{U} X ⊊ U is finitely based. Since X \mathcal{X} X omits an identity of T ∞ T_\infty T ∞ , it omits some T k T_k T k ; otherwise it would contain every T k T_k T k and hence U \mathcal{U} U . Fix k k k with T k ∉ X T_k\notin\mathcal{X} T k ∈ / X .
We examine the finite subdirectly irreducible members of X \mathcal{X} X . Let B B B be a finite subdirectly irreducible member of X \mathcal{X} X . The ambient variety F \mathcal{F} F and Proposition 6.5 apply. If B B B has no nonabsorbing triple product then B ≅ Φ k B\cong\Phi_k B ≅ Φ k . Otherwise its triple-edge graph has no directed cycle. Indeed, a cycle of length m m m would contradict X m \mathcal{X}_m X m , which belongs to Id ( V ) \operatorname{Id}(\mathcal{V}) Id ( V ) by Lemma 6.3. Hence the finite components of this functional graph are directed paths. We show that a sufficiently long path would contain a copy of T k T_k T k . Suppose, toward a contradiction, that a directed path has k + 1 k+1 k + 1 edges, v 0 → v 1 → ⋯ → v k → v k + 1 v_0 \to v_1 \to\cdots\to v_k \to v_{k+1} v 0 → v 1 → ⋯ → v k → v k + 1 . The set
S = { ∞ , ω , e } ∪ { v i , v i e , e v i : 1 ≤ i ≤ k } S=\{\infty,\omega,e\}\cup\{v_i,v_ie,ev_i:1\le i\le k\} S = { ∞ , ω , e } ∪ { v i , v i e , e v i : 1 ≤ i ≤ k }
is a subsemiring of B B B isomorphic to T k T_k T k . The edges incident with v 0 v_0 v 0 and v k + 1 v_{k+1} v k + 1 ensure that e v 1 ev_1 e v 1 and v k e v_ke v k e are nonabsorbing. Cancellation and disjointness of A A A , P P P , Q Q Q show that ∣ S ∣ = 3 k + 3 |S|=3k+3 ∣ S ∣ = 3 k + 3 . By (24) , the only nonabsorbing products in S S S are v i e v_ie v i e , e v i ev_i e v i and ( v i e ) v i + 1 = v i ( e v i + 1 ) = ω (v_ie)v_{i+1}=v_i(ev_{i+1})=\omega ( v i e ) v i + 1 = v i ( e v i + 1 ) = ω for 1 ≤ i < k 1\le i<k 1 ≤ i < k . All other products in S S S are ∞ \infty ∞ by the classification in Proposition 6.5; flat addition is closed because ∞ ∈ S \infty\in S ∞ ∈ S . The bijection from T k T_k T k taking u i u_i u i to v i v_i v i , p i p_i p i to v i e v_ie v i e and q i q_i q i to e v i ev_i e v i is thus an isomorphism. This contradicts T k ∉ X T_k\notin\mathcal{X} T k ∈ / X . The external vertices v 0 , v k + 1 v_0,v_{k+1} v 0 , v k + 1 are not in S S S ; they serve only to ensure the presence of q 1 = e v 1 q_1=ev_1 q 1 = e v 1 and p k = v k e p_k=v_ke p k = v k e . Thus S S S contains all 3 k + 3 3k+3 3 k + 3 distinct elements of T k T_k T k .
The preceding contradiction excludes paths with k + 1 k+1 k + 1 edges in each finite subdirectly irreducible member of X \mathcal{X} X . A nonabsorbing value of the left side of Φ k \Phi_k Φ k would require a directed walk with k + 1 k+1 k + 1 edges. Therefore every finite subdirectly irreducible member of X \mathcal{X} X satisfies Φ k \Phi_k Φ k . By finite subdirect representation and preservation of identities under products and subalgebras, every finite member of X \mathcal{X} X satisfies Φ k \Phi_k Φ k . Since X ⊆ F \mathcal{X}\subseteq\mathcal{F} X ⊆ F is locally finite, every finitely generated member is finite; hence every member satisfies Φ k \Phi_k Φ k . Therefore X ⊆ D k \mathcal{X}\subseteq\mathcal{D}_k X ⊆ D k . By Proposition 6.6 , X \mathcal{X} X is finitely based. Lemma 6.3 proves that U \mathcal{U} U is not finitely based, while Proposition 6.2 and Proposition 6.4 give the asserted inclusions and noninclusions. □ \square □
Corollary 6.8. The limit variety U \mathcal{U} U is distinct from V ( S R 6 ) \mathop{\rm V}(SR_6) V ( S R 6 ) and is not contained in W 1 \mathcal{W}_1 W 1 .
Proof. The following identity distinguishes the two varieties. In T ∞ T_\infty T ∞ every square equals ∞ \infty ∞ ; moreover, whenever x y xy x y and y x yx y x are both nonabsorbing, they cannot take the same value. Consequently
x y + y x ≈ y x + y 2 xy+yx\approx yx+y^2 x y + y x ≈ y x + y 2
holds in U \mathcal{U} U . It fails in S R 6 SR_6 S R 6 : with the usual table labels, 2 ⋅ 6 = 6 ⋅ 2 = 3 2\cdot6=6\cdot2=3 2 ⋅ 6 = 6 ⋅ 2 = 3 whereas 6 2 = 1 = ∞ 6^2=1=\infty 6 2 = 1 = ∞ . The two limit varieties are therefore distinct. Since W 1 \mathcal{W}_1 W 1 has only the limit subvariety V ( S R 6 ) \mathop{\rm V}(SR_6) V ( S R 6 ) by Theorem 5.4 , U \mathcal{U} U cannot be a subvariety of W 1 \mathcal{W}_1 W 1 . □ \square □
Corollary 6.9. None of the varieties W n \mathcal{W}_n W n (n > 1 n>1 n > 1 ) or W ∞ \mathcal{W}_\infty W ∞ is a Cross variety. Furthermore, W n \mathcal{W}_n W n is not a limit variety for any n ≥ 2 n\ge2 n ≥ 2 .
Proof. Recall that a Cross variety is finitely based, is generated by a finite algebra, and has a finite subvariety lattice. For n ≥ 2 n\ge2 n ≥ 2 , W n \mathcal{W}_n W n is nonfinitely based by Theorem 1.1 , as is W ∞ \mathcal{W}_\infty W ∞ by Theorem 3.1 ; hence none is Cross. The variety W 1 \mathcal{W}_1 W 1 contains the nonfinitely based limit subvariety V ( S R 6 ) \mathop{\rm V}(SR_6) V ( S R 6 ) by Theorem 5.4 . To justify the use of the finite-subvariety-lattice condition, note that every subvariety of a finitely based variety with a finite subvariety lattice is itself finitely based. Indeed, fix a subvariety V \mathcal{V} V of such an ambient variety. For each other subvariety not contained in V \mathcal{V} V , choose an identity holding in V \mathcal{V} V but failing in that other subvariety. There are only finitely many such subvarieties; adjoining all selected identities to a finite basis for the ambient variety defines V \mathcal{V} V . Thus W 1 \mathcal{W}_1 W 1 is not Cross either. Finally U ⊈ W 2 \mathcal{U}\nsubseteq\mathcal{W}_2 U ⊈ W 2 : containment follows from Theorem 6.7 , and it is proper because U \mathcal{U} U satisfies x 2 ≈ y 2 x^2\approx y^2 x 2 ≈ y 2 whereas A ^ 2 \widehat{A}_2 A 2 does not. Thus each W n \mathcal{W}_n W n for n ≥ 2 n \ge2 n ≥ 2 contains a proper nonfinitely based subvariety U \mathcal{U} U , so it cannot be a limit variety. □
Comparison with the limit varieties of Shao–Gao
Put A = V ( S ( a b c ) ) \mathcal{A} = \mathsf{V}(S(abc)) A = V ( S ( ab c )) , where a , b , c a,b,c a , b , c are distinct letters. Put L S G = V ( B 15 ) \mathcal{L}_{\mathrm{SG}} = \mathsf{V}(B_{15}) L SG = V ( B 15 ) , and let M \mathcal{M} M be the limit variety whose existence is proved in Shao–Gao [19 Theorem 22.1] . In their notation, let
R 3 = ( S ( a b c ) × D 2 ) / ( { ∞ } × D 2 ) , R 3 = V ( R 3 ) . R_3 = (S(abc) \times D_2)/(\{\infty\} \times D_2), \qquad\mathcal{R}_3 = \mathsf{V}(R_3). R 3 = ( S ( ab c ) × D 2 ) / ({ ∞ } × D 2 ) , R 3 = V ( R 3 ) .
Their results give
A ⊊ M ⊆ R 3 , M ∩ L S G = A , L S G ∩ Mod ( ρ 0 ) = A , (25) \mathcal{A} \subsetneq\mathcal{M} \subseteq\mathcal{R}_3, \qquad\mathcal{M} \cap\mathcal{L}_{\mathrm{SG}} = \mathcal{A}, \qquad\mathcal{L}_{\mathrm{SG}} \cap\operatorname{Mod}(\rho_0) = \mathcal{A}, \tag*{(25)} A ⊊ M ⊆ R 3 , M ∩ L SG = A , L SG ∩ Mod ( ρ 0 ) = A , (25)
where ρ 0 \rho_0 ρ 0 is the rectangular absorption identity
ρ 0 : x y + x z + t z ≈ x y + x z + t z + t y . (26) \rho_0:\quad xy+xz+tz \approx xy+xz+tz+ty. \tag*{(26)} ρ 0 : x y + x z + t z ≈ x y + x z + t z + t y . (26)
Here Mod ( ρ 0 ) \operatorname{Mod}(\rho_0) Mod ( ρ 0 ) denotes the variety of ai-semirings satisfying ρ 0 \rho_0 ρ 0 . The last equality in (25) is [19 Corollary 7.12] .
Proposition 6.10. The limit variety U = V ( T ∞ ) \mathcal{U} = \mathsf{V}(T_\infty) U = V ( T ∞ ) satisfies
U ∩ L S G = A . \mathcal{U} \cap\mathcal{L}_{\mathrm{SG}} = \mathcal{A}. U ∩ L SG = A . Consequently, U \mathcal{U} U and L S G \mathcal{L}_{\mathrm{SG}} L SG are distinct and incomparable limit varieties.
Proof. We first establish A ⊆ U \mathcal{A} \subseteq\mathcal{U} A ⊆ U by constructing a concrete homomorphic image of T 2 T_2 T 2 . In T 2 T_2 T 2 put
I = { ∞ , q 1 , p 2 } . I = \{\infty, q_1, p_2\}. I = { ∞ , q 1 , p 2 } .
By the multiplication rules in Subsection 6.1, each of q 1 q_1 q 1 and p 2 p_2 p 2 annihilates every element on either side, with product ∞ \infty ∞ . Since the addition is flat, I + T 2 ⊆ I I + T_2 \subseteq I I + T 2 ⊆ I and I T 2 ∪ T 2 I ⊆ I IT_2 \cup T_2I \subseteq I I T 2 ∪ T 2 I ⊆ I . Thus I I I is a semiring ideal. The quotient T 2 / I T_2/I T 2 / I has the seven elements represented by ∞ , u 1 , e , u 2 , p 1 , q 2 , ω \infty, u_1, e, u_2, p_1, q_2, \omega ∞ , u 1 , e , u 2 , p 1 , q 2 , ω . The assignment
[ I ] ↦ ∞ , u 1 ↦ a , e ↦ b , u 2 ↦ c , p 1 ↦ a b , q 2 ↦ b c , ω ↦ a b c [I] \mapsto\infty,\quad u_1 \mapsto a,\quad e \mapsto b,\quad u_2 \mapsto c,\quad p_1 \mapsto ab,\quad q_2 \mapsto bc,\quad\omega\mapsto abc [ I ] ↦ ∞ , u 1 ↦ a , e ↦ b , u 2 ↦ c , p 1 ↦ ab , q 2 ↦ b c , ω ↦ ab c
is a semiring isomorphism T 2 / I ≅ S ( a b c ) T_2/I \cong S(abc) T 2 / I ≅ S ( ab c ) : its only nonabsorbing products of distinct positive factors are u 1 e = p 1 u_1e = p_1 u 1 e = p 1 , e u 2 = q 2 eu_2 = q_2 e u 2 = q 2 , and p 1 u 2 = u 1 q 2 = ω p_1u_2 = u_1q_2 = \omega p 1 u 2 = u 1 q 2 = ω , precisely corresponding to a b ab ab , b c bc b c , and a b c abc ab c . As T 2 T_2 T 2 is a subsemiring of T ∞ T_\infty T ∞ , we obtain A ⊆ U \mathcal{A} \subseteq\mathcal{U} A ⊆ U .
Next we prove T ∞ ⊨ ρ 0 T_\infty\models\rho_0 T ∞ ⊨ ρ 0 . Every multiplication row of T ∞ T_\infty T ∞ has pairwise distinct values other than ∞ \infty ∞ , as observed in the proof of Lemma 6.1 . Under an arbitrary evaluation, if x y + x z + t z = ∞ xy+xz+tz = \infty x y + x z + t z = ∞ , adjoining t y ty t y leaves the value unchanged. Otherwise flatness forces
x y = x z = t z ≠ ∞ . xy = xz = tz \ne\infty. x y = x z = t z = ∞.
Left cancellation of nonabsorbing products in the row indexed by x x x implies y = z y = z y = z ; consequently t y = t z ty = tz t y = t z and the right-hand side has the same value. Hence U ⊆ Mod ( ρ 0 ) \mathcal{U} \subseteq\operatorname{Mod}(\rho_0) U ⊆ Mod ( ρ 0 ) .
The Shao–Gao intersection theorem now gives the exact intersection. (25) gives
A ⊆ U ∩ L S G ⊆ L S G ∩ Mod ( ρ 0 ) = A , \mathcal{A} \subseteq\mathcal{U} \cap\mathcal{L}_{\mathrm{SG}} \subseteq\mathcal{L}_{\mathrm{SG}} \cap\operatorname{Mod}(\rho_0) = \mathcal{A}, A ⊆ U ∩ L SG ⊆ L SG ∩ Mod ( ρ 0 ) = A ,
which establishes the equality. Since A \mathcal{A} A is properly contained in L S G \mathcal{L}_{\mathrm{SG}} L SG and U \mathcal{U} U is a limit variety by Theorem 6.7 , the two limit varieties are different. Two distinct limit varieties cannot be comparable: otherwise the larger would have a proper nonfinitely based subvariety. Therefore
U ⊈ L S G , L S G ⊈ U . \mathcal{U} \not\subseteq\mathcal{L}_{\mathrm{SG}}, \qquad\mathcal{L}_{\mathrm{SG}} \not\subseteq\mathcal{U}. U ⊆ L SG , L SG ⊆ U .
Proposition 6.11. With M \mathcal{M} M as above, one has
U ⊈ R 3 . \mathcal{U} \not\subseteq\mathcal{R}_3. U ⊆ R 3 . In particular, U ≠ M \mathcal{U} \ne\mathcal{M} U = M , and these two limit varieties are incomparable:
U ⊈ M , M ⊈ U . \mathcal{U} \not\subseteq\mathcal{M}, \qquad\mathcal{M} \not\subseteq\mathcal{U}. U ⊆ M , M ⊆ U . Proof. Consider the identity
τ : x y + y z ≈ x 2 . (27) \tau:\qquad xy+yz\approx x^2. \tag*{(27)} τ : x y + y z ≈ x 2 . (27) It holds in S ( a b c ) S(abc) S ( ab c ) . Indeed, every square evaluates to ∞ \infty ∞ , since the defining word has no repeated letter. If x y + y z ≠ ∞ xy+yz\ne\infty x y + y z = ∞ , flatness would give x y = y z ≠ ∞ xy=yz\ne\infty x y = y z = ∞ . The nonempty factor representing y y y would then be a proper suffix of the factor representing x y xy x y and a proper prefix of that same factor representing y z yz y z . This is impossible, because every nonempty factor of a b c abc ab c has distinct letters and hence no nonempty proper border. Consequently both sides of τ \tau τ always equal ∞ \infty ∞ in S ( a b c ) S(abc) S ( ab c ) .
For every evaluation in S ( a b c ) × D 2 S(abc)\times D_2 S ( ab c ) × D 2 , the first coordinates of both sides of τ \tau τ therefore equal ∞ \infty ∞ . Since the quotient defining R 3 \mathcal{R}_3 R 3 collapses all of { ∞ } × D 2 \{\infty\}\times D_2 { ∞ } × D 2 , it follows that R 3 ⊨ τ \mathcal{R}_3\models\tau R 3 ⊨ τ , and so R 3 ⊨ τ \mathcal{R}_3\models\tau R 3 ⊨ τ .
By contrast, in T 3 T_3 T 3 , take x = p 1 x=p_1 x = p 1 , y = u 2 y=u_2 y = u 2 , and z = q 3 z=q_3 z = q 3 . The multiplication rules give
x y = p 1 u 2 = ω , y z = u 2 q 3 = ω , x 2 = p 1 2 = ∞ . xy=p_1u_2=\omega,\qquad yz=u_2q_3=\omega,\qquad x^2=p_1^2=\infty. x y = p 1 u 2 = ω , y z = u 2 q 3 = ω , x 2 = p 1 2 = ∞. Thus x y + y z = ω ≠ ∞ = x 2 xy+yz=\omega\ne\infty=x^2 x y + y z = ω = ∞ = x 2 , so T 3 ⊭ τ T_3\not\models\tau T 3 ⊨ τ . Since T 3 ≤ T ∞ T_3\leq T_\infty T 3 ≤ T ∞ , U ⊈ R 3 \mathcal{U}\not\subseteq\mathcal{R}_3 U ⊆ R 3 . On the other hand M ⊆ R 3 \mathcal{M}\subseteq\mathcal{R}_3 M ⊆ R 3 by [19 Theorem 22.1] . Therefore U ⊈ M \mathcal{U}\not\subseteq\mathcal{M} U ⊆ M and in particular U ≠ M \mathcal{U}\ne\mathcal{M} U = M . Finally M \mathcal{M} M and U \mathcal{U} U are both limit varieties by [19 Theorem 22.1] and Theorem 6.7 , respectively. The same minimality argument as in Proposition 6.10 excludes the reverse containment.
Corollary 6.12. For every n ≥ 2 n\geq2 n ≥ 2 , the variety W n \mathcal{W}_n W n contains at least five pairwise incomparable limit subvarieties:
V ( S R 6 ) , L S G , M , U , V a c , \mathcal{V}(SR_6),\qquad\mathcal{L}_{\mathrm{SG}},\qquad\mathcal{M},\qquad\mathcal{U},\qquad\mathcal{V}_{\mathrm{ac}}, V ( S R 6 ) , L SG , M , U , V ac , where V a c \mathcal{V}_{\mathrm{ac}} V ac is the acyclic directed-graph limit variety of Gao–Ren as recorded in Shao–Gao [19 Proposition 25.3] .
Proof. Proposition 5.3 gives V ( S R 6 ) ⊆ W 1 \mathcal{V}(SR_6)\subseteq\mathcal{W}_1 V ( S R 6 ) ⊆ W 1 . By Shao–Gao [19 Theorem 1.2] , L S G ⊆ V ( S ( a b c ) 0 ) \mathcal{L}_{\mathrm{SG}}\subseteq\mathcal{V}(S(abc)^0) L SG ⊆ V ( S ( ab c ) 0 ) , and Lemma 4.5 puts this linear-word variety in W 2 \mathcal{W}_2 W 2 . Shao–Gao’s Theorem 22.2 therefore gives M ⊆ W 2 \mathcal{M}\subseteq\mathcal{W}_2 M ⊆ W 2 ; Theorem 6.7 gives U ⊆ W 2 \mathcal{U}\subseteq\mathcal{W}_2 U ⊆ W 2 .
Both S ( a 2 ) 0 S(a^2)^0 S ( a 2 ) 0 and S ( a b ) 0 S(ab)^0 S ( ab ) 0 are homomorphic images of S ( a b b a ) 0 S(abba)^0 S ( abba ) 0 . To see this, fix v ∈ { b b , a b } v\in\{bb,ab\} v ∈ { bb , ab } and take the natural factor map S ( a b b a ) ↠ S ( v ) S(abba)\twoheadrightarrow S(v) S ( abba ) ↠ S ( v ) which fixes the nonempty factors of v v v and sends all other old factors, including the old top, to ∞ \infty ∞ . This is a homomorphism because every factor of a retained word is again retained; a discarded factor cannot occur in a product whose result is retained. Extend this map to the zero extensions by sending the new element 0 0 0 to the new 0 0 0 . This proves the asserted surjections (renaming b b b to a a a in the first target). In particular, the map keeps the old top ∞ \infty ∞ and the new zero 0 0 0 distinct. Shao–Gao’s Corollary 4.2 gives
V ( S ( a 2 , a b ) 0 ) = V ( S ( a 2 ) 0 ) ∨ V ( S ( a b ) 0 ) ⊆ W 2 . \mathcal{V}(S(a^2,ab)^0)=\mathcal{V}(S(a^2)^0)\vee\mathcal{V}(S(ab)^0)\subseteq\mathcal{W}_2. V ( S ( a 2 , ab ) 0 ) = V ( S ( a 2 ) 0 ) ∨ V ( S ( ab ) 0 ) ⊆ W 2 . Their Proposition 25.3 now places V a c \mathcal{V}_{\mathrm{ac}} V ac in W 2 \mathcal{W}_2 W 2 . All five varieties thus belong to W n \mathcal{W}_n W n for n ≥ 2 n\geq2 n ≥ 2 .
The variety V ( S R 6 ) \mathcal{V}(SR_{6}) V ( S R 6 ) is commutative, whereas each of the other four fails commutativity. This separates the first variety from the other four. Moreover, V a c ⊨ x y z ≈ x 2 \mathcal{V}_{\mathrm{ac}}\models xyz\approx x^{2} V ac ⊨ x y z ≈ x 2 , while each of L S G , M , U L_{\mathrm{SG}},\mathcal{M},\mathcal{U} L SG , M , U contains V ( S ( a b c ) ) \mathcal{V}(S(abc)) V ( S ( ab c )) , which refutes that identity. Theorem 22.1 of Shao–Gao separates L S G L_{\mathrm{SG}} L SG from M \mathcal{M} M , and Propositions 6.10 and 6.11 distinguish U \mathcal{U} U from both. Hence the five limit varieties are distinct. Two distinct limit varieties cannot contain one another. □
The preceding propositions distinguish U \mathcal{U} U from both limit varieties of Shao–Gao. We make no claim about the exact intersection U ∩ M \mathcal{U}\cap\mathcal{M} U ∩ M .
Conclusion
The mirror-word zero extensions give the strict chain W 1 ⊊ W 2 ⊊ ⋯ \mathcal{W}_{1}\subsetneq\mathcal{W}_{2}\subsetneq\cdots W 1 ⊊ W 2 ⊊ ⋯ . By Theorem 4.4 , every consecutive interval [ W n , W n + 1 ] [\mathcal{W}_{n},\mathcal{W}_{n+1}] [ W n , W n + 1 ] (n ≥ 1 n\geq1 n ≥ 1 ) contains an order-embedded power-set lattice and hence has cardinality 2 ℵ 0 2^{\aleph_{0}} 2 ℵ 0 . For n ≥ 2 n\geq2 n ≥ 2 the same cardinality holds for [ V n , W n ] [\mathcal{V}_{n},\mathcal{W}_{n}] [ V n , W n ] by Corollary 4.6 ; this latter argument uses the cyclic semirings of Shao–Gao and verifies the endpoint conditions for the mirror words. It follows that ∣ [ V n , W ∞ ] ∣ = 2 ℵ 0 |[\mathcal{V}_{n},\mathcal{W}_{\infty}]|=2^{\aleph_{0}} ∣ [ V n , W ∞ ] ∣ = 2 ℵ 0 for n ≥ 2 n\geq2 n ≥ 2 . Proposition 4.9 establishes local finiteness of W ∞ \mathcal{W}_{\infty} W ∞ .
Finite local quotients, six-element evaluation kernels and the uniform short-word bound establish infinite axiomatic rank throughout [ W 2 , W ∞ ] [\mathcal{W}_{2},\mathcal{W}_{\infty}] [ W 2 , W ∞ ] ; see Corollary 3.21 for variable bounds. The finite-basis classification of individual zero extensions instead follows from Shao–Gao [19 ] .
The variety V ( S R 6 ) \mathcal{V}(SR_{6}) V ( S R 6 ) is the unique limit subvariety of W 1 \mathcal{W}_{1} W 1 by Theorem 5.4 . The directed-path construction of Theorem 6.7 yields a distinct limit variety U = V ( T ∞ ) \mathcal{U}=\mathcal{V}(T_{\infty}) U = V ( T ∞ ) that is contained in every W n \mathcal{W}_{n} W n (n ≥ 2 n\geq2 n ≥ 2 ) but is not contained in any V n \mathcal{V}_{n} V n . Proposition 6.10 proves
U ∩ V ( B 15 ) = V ( S ( a b c ) ) . \mathcal{U}\cap\mathcal{V}(B_{15})=\mathcal{V}(S(abc)). U ∩ V ( B 15 ) = V ( S ( ab c )) .
Together with the two limit varieties of Shao–Gao and the previously known acyclic-graph example, this gives at least five pairwise incomparable limit subvarieties of each W n \mathcal{W}_{n} W n for n ≥ 2 n\geq2 n ≥ 2 , as recorded in Corollary 6.12.
School of Mathematics, Northwest University, Xi’an, 710127, Shaanxi, P. R. China Email address: 2025213777@stumail.nwu.edu.cn
School of Mathematics, Northwest University, Xi’an, 710127, Shaanxi, P. R. China Email address: myayue@yeah.net