Growth series of involution systems and their Coxeter companions

The companion graph of Example ex:EMIS-A2 is the Coxeter graph of type A ₂, and its Coxeter type is U₃ – both read off the 2-recognizable presentation

The companion graph of the rank-4 EMIS of:2017 is the paper's Gamma: m(a,b) = m(a,c) = m(b,c) = 3, m(a,d) = 2, m(b,d) = m(c,d) = infinity

W(q) = Wbar(q) = (1+q+q²)/(1-q)² to degree 16 for Example ex:EMIS-A2 – sphere sizes 1, 3, 6, 9, 12,... = 3n

W(q) = Wbar(q) = (1 + 3q + 4q² + 3q³ + q⁴)/(1 - q - 3q² - q³ + q⁴) to degree 12 for the rank-4 EMIS that is not a quasi-Coxeter system – sphere sizes 1, 4, 11, 27, 64, 152, 360, 853, 2021, 4788, 11344, 26876, 63675

Those coefficients are exact for the PRESENTED groups: the reduced-word upper bound meets the model lower bound at radius 12 (rank 3) and radius 8 (rank 4)

The models are quotients of the presented groups: every relator evaluates to the identity in Z² x| +-1, in the amalgam W_A *_(<a>) (<a> x <d>), and in the two integral Tits representations

Control (over-count): the Coxeter TYPE is the wrong graph – U₃ = C₂ * C₂ * C₂ gives 1, 3, 6, 12, 24, 48, 96 where the companion A ₂ gives 1, 3, 6, 9, 12, 15, 18

Control (over-count): deleting the relator (ad)² from the rank-4 EMIS gives the free product W_A * C₂ with sphere sizes 1, 4, 12, 33, 90, 246, 672, 1836, 5016 – different from n = 2 on, and exact on both sides

Control (under-count): dropping 'even' breaks the equality – <a,b,c | a²,b²,c²,abc> is C₂ x C₂ with 1 + 3q, while its Coxeter type C₂³ has 1 + 3q + 3q² + q³

Control (under-count): dropping 'meet-semilattice' breaks the equality – the source's 2-recognizable non-EMIS has |B(4)| <= 47 while its relator graph is of type A₄, i.e. S₅, with |B(4)| = 49

Positive control: the trivial system (rank 1) is its own Coxeter companion, both series 1 + q

The three shortlist classes with a redundant generator have models: every relator dies in the rank-3 integral Tits representation with the fourth generator bcb

Their sphere sizes are exact for the *presented* groups: the word upper bound meets the model ball through degree 6 (presRed2, presRed3) and degree 8 (presRed6); the lists are 1,4,7,8,8,…, 1,4,9,16,26,42,68,110,178,288 and 1,4,10,22,46,96,200,416,866,1802

The companion graph is not companionMat R₀: for these three classes m(a,d) = 2, 3, ∞ where companionMat says ∞, ∞, ∞, and m(c,d) = ∞ by the 2-recognizability budget together with ord(cd) = ord(ad) = ord(adcd) = ∞

A ℤ₂ letter weight certifies irreducibility: ψ(a)=1, ψ(b)=ψ(c)=ψ(d)=0 vanishes on every length-4 relator of presRed3 and presRed6 and not on the hexagons ababab, acacac, adadad, so those hexagons are irreducible cycles

Two of the eight shortlist classes are false positives: with the corrected companion W(q) = W̄(q) to degree 9 for abab,acac,bcbd (both (1+q)³/(1-q)) and for abab,acacac,bcbd; 48 of the 192 survivors fall

The class ababab, acacac, bcbd survives: W = ⟨a,b,c ∣ (ab)³,(ac)³⟩ with S = a,b,c,bcb has companion Γ forced (under the EMIS hypothesis) and W(q) ≠ W̄(q), first at degree 6 (200 against 201); its right weak order has no meet failure among the 112,747,636 pairs of elements of length ≤ 11. So this system is an EMIS only if qu:Growth has a negative answer

Controls on the weak-order machinery: (C₂³, x,y,z,xyz) is not an MIS and the test finds 3 failing pairs; Example ex:EMIS-A2 has none; and joinMat recovers Ã₂ for ex:EMIS-A2

The 192-member rank-4 survivor shortlist is 8 classes under relabelling the generators, each of full size 24; the 144 of first decisive degree 6 are 6 classes; exactly 3 classes (72 survivors) contain a length-4 relator on three letters, and they are the three of G12–G17

Controls on the canonical form: it is invariant under all 24 relabellings, its eight class keys are pairwise distinct, and the paper's own rank-4 EMIS of:2017 — which is not a survivor — gets a key outside the list

Five involution systems and four Coxeter companions have finite complete shortlex rewriting systems: every rule is a consequence of the relators, every rule decreases shortlex, every critical pair resolves, every relator dies — so sphere sizes are exact at every degree, with no model and no radius limit

Two more shortlist classes are settled and both are new candidates: abab,acacac,bcdbdc and abab,acacac,bcdcbd have companion Γ forced under the EMIS hypothesis (one ∞ edge, one 2 edge sharing a vertex, four 3 edges) and W(q) ≠ W̄(q), first at degree 6, 280 against 281; 48 more of the 192 survivors settled

W(q) is rational with an explicit closed form for all five systems and all four companions — the first half of qu:Growth for each — and presRed2, presRed3 are false positives *in every degree*, their W(q) and W̄(q) being the same rational function; presRed6 has W(q) = (1+q)²(1+q+q²)/(1-q-2q²-q³+q⁴) against W̄(q) = (1+3q+5q²+6q³+5q⁴+3q⁵+q⁶)/(1-q-q²-2q³-q⁴-q⁵)

A meet failure of least ℓ(u)+ℓ(v) has its two maximal common lower bounds with disjoint descent sets, so only pairs sharing two left descents need testing — a factor of 64 at cap 8 — and there is no meet failure of length ≤ 8 in Lean for any of the three candidate systems, nor of length ≤ 11 externally for any of them — reproducing the r2 exhaustive length-11 result for presRed6 from 2.9 million pairs instead of 112.7 million

Two model-free certificates: a hexagon is irreducible as soon as it uses a letter no 4-cycle of Cay(W,S) uses — which settles dbcdcb, on which *every* ℤ₂ letter weight of row G15 provably vanishes — and w has infinite order as soon as one long enough power of w is irreducible for the rewriting system

The minimal-upper-bound criterion is implemented and controlled: mubIdx (T2's local descent test) agrees with mubSlow (the prefix-set definition) on three systems; it fires with three minimal upper bounds per pair on (C₂³,a,b,c,abc), and with counts 3,1,1,1,1,3 on the paper's own non-EMIS (:1383), where the pair a,b's minimal upper bounds abc, abab, abdc contain both elements of the paper's own meet-failure witness at:1387; and the atom test agrees with the unpruned meet test at cap 8 on all eleven systems of this family that have a complete rewriting system (nine (true,true), two (false,false))

presRed6 (row G17's candidate): no generator pair has two distinct minimal upper bounds of length ≤ 12. The five bounded pairs have exactly one each — a∨b = aba, a∨c = aca, a∨d = abadab, b∨c = bd, b∨d = bc — and c,d has no common upper bound in B(12); |B(12)| = 31,257. The join abadab has length 6 against a longest relator of length 6, so the naive escape bound 2ℓ(s∨t) ≤ max|r| is false inside a live candidate

presXbdc and presXcbd (row G22's candidates): same verdict at radius 12, |B(12)| = 55,932 each. presXbdc counts 1,0,1,1,1,1 with joins aba, ad, bdb, bcd, cbd; presXcbd counts 1,1,1,1,1,0 with joins ada, ac, abd, bcb, bad. The two 0s sit exactly on the pairs the companion matrices call ∞

Cost, measured in Lean on presXbdc at radius 12: the G24 pruned meet test is 470.9 s and examines 25,010,580 element pairs; the atom test is 75.2 s and examines 335,592 elements against 6 generator pairs — 74.5× fewer objects, 6.3× less wall time. The whole file costs 497.4 s / 1.58 GB (0.14 CPU-h) for 27 theorems, of which the two refutation sweeps are 47 s (38,441 systems, 1.2 ms each) and 39 s (2,846 systems, 14 ms each)

T1: for an even involution system with S finite, (W,S) is an MIS iff every bounded pair of distinct generators has a join s ∨_R t — the meet-semilattice property, a condition on all of W × W, is equivalent to a condition on the C(|S|,2) pairs of atoms

T2: u is a minimal upper bound of s,t in the right weak order of an EIS iff s,t ∈ D_L(u) and D_R(u) ∩ D_R(su) ∩ D_R(tu) = ∅; hence a join exists iff U(s,t) has exactly one minimal element, and two minimal upper bounds found anywhere refute MIS with no radius caveat

A refutation sweep for T1: 38,441 involution systems ⟨S⟩ ≤ F₂ⁿ (n = 3,4,5, |S| ∈ 2,3,4), of which 33,456 are EIS, and the atom test and the meet test give the same verdict on every one. 1,197 EIS systems fail both, 32,259 pass both, and the cell that would kill T1 — EIS, meet fails, atoms pass — is empty; the 4,985 non-EIS systems happen to agree too

The same refutation sweep where the group is not abelian: 2,846 involution systems ⟨S⟩ ≤ Sₙ (n = 4, |S| ∈ 2,3,4; n = 5, |S| ∈ 2,3), subgroup orders 4,6,8,10,12,24,60,120, of which 846 are EIS — and again the atom test and the meet test agree on every one. 246 EIS systems fail both, 600 pass both, and the killing cell is empty

Escape-bound route E2 measured, and only half of it survives: the right-multiplier word-difference sets of the shortlex normal forms are |D_R| = 11 (presRed6), 18, 18 at radius 10 with longest difference 2, 4, 4 — three orders under the kill criterion 10⁴ and stable for three to four radii — while the left-multiplier sets, the half E2 needs, are |D_L| = 27,143 / 45,932 / 45,900 with longest difference 21 ≈ 2 × 10 and still growing. Shortlex-automatic, not shortlex-biautomatic. Separately, closing D_R under the unrestricted transition d ↦ nf(a⁻¹ d b) diverges (5,365 / 14,346 / 15,298 within four rounds), so closure alone is not the finite check it looks like

Four cactus groups over Coxeter systems — J₃, J₄, the cactus group over B₃, and the one over the affine (3,3,3) triangle group — have complete shortlex rewriting systems, and their Coxeter companions are right-angled: every bounded pair of generators has exactly one minimal upper bound, of length 2, with exactly two reduced words

The source's own certified-EMIS family answers qu:Growth positively. W(q) = W̄(q) at every degree, with the same rational function on both sides: (1+q)²/(1-q) for J₃; (1+q)³/(1-3q+q²) for J₄ and for the cactus group over B₃ (spheres 1,6,20,55,145,380,995,2605,…, growth rate (3+√5)/2); (1+q)²/(1-4q+q²) for the affine (3,3,3) one (spheres 1,6,24,90,336,1254,4680,…, growth rate 2+√3). The same holds for the cactus group over all 56 rank-3 Coxeter systems with m ∈ 2,3,4,5,6,∞

The right-angled descent automaton of T3 (G38) is implemented and validated: built from (Γ, α) alone — a graph and one involution per generator — it reproduces the exact sphere sizes of all four cactus groups and, untwisted, those of their companions; and for every (Γ, α) on ≤ 4 letters (396 2-recognizable length-4 relator sets, of which 276 pass integrality) the twisted and untwisted totals agree to degree 34. Externally on 5 letters: 51,407 sets, 15,337 integral, 0 disagreements

T3: in an EMIS in which every bounded pair of distinct generators has ℓ(s ∨_R t) = 2, the right descent set transits by D_R(ws) = s ∪ αₛ(D_R(w) ∩ N(s)), where αₛ(t) is the second letter of the reduced word for s ∨_R t beginning with s and is an involution of N(s). T4: since every v of length n+1 has exactly |D_R(v)| predecessors, the descent-set distribution obeys a finite linear recursion on the cliques of Γ. T5: hence W(q) = W̄(q) for such a system is equivalent to a finite statement about the pair (Γ, α)

Where a counterexample to qu:Growth can live. No right-angled EMIS of rank ≤ 4 has W(q) ≠ W̄(q) — so a counterexample must have a bounded pair of generators with ℓ(s ∨_R t) ≥ 3, i.e. a companion edge with 3 ≤ m < ∞. Cactus groups are excluded outright (their relators all have length 4). This family's own three candidates satisfy the constraint: presRed6 has a ∨ b = aba and a ∨ d = abadab, and compXbdc, compXcbd carry entries 3