betaFeedback

WorksComputer Science

A faster algorithm for commutator length in free groups

Abstract

We compute the commutator length \cl(w) of a reduced word w∈[F,F]w\in[F,F] of length MM in a free group. Given a target g≥1g\ge1, a deterministic algorithm decides \cl(w)\le g and, when it holds, returns a decomposition into at most gg commutators, in O(M3g)O(M^{3g}) steps; trying g=1,2,…g=1,2,\dots gives \cl(w) in O(M^{3\cl(w)}) steps. For g=1g=1 the same test takes O(M)O(M) expected steps on a uniformly random reduced input in [F,F][F,F]. All bounds are in the unit-cost model.

Introduction

Let FF be the free group on a finite set XX with ∣X∣≥2|X| \ge2, the case of one generator having [F,F]=1[F,F]=1; throughout, ww is a reduced word over X∪X−1X \cup X^{-1} of length M=∣w∣M=|w|. For w∈[F,F]w \in[F,F] put

cl⁡(w)=min⁡{k≥0:w=∏i=1k[ui,vi]},[u,v]=uvu−1v−1,(1)\operatorname{cl}(w)=\min\left\{k\ge0:w=\prod_{i=1}^{k}[u_i,v_i]\right\},\qquad[u,v]=uvu^{-1}v^{-1}, \tag*{(1)}

and cl⁡(w)=∞\operatorname{cl}(w)=\infty when w∉[F,F]w\notin[F,F], the set above being empty. Throughout, g≥1g\ge1 is the target, the bound on the number of commutators given as part of the input: the task is to decide cl⁡(w)≤g\operatorname{cl}(w)\le g and, when that holds, to exhibit a decomposition. The exponent below is linear in gg, so for each fixed target the bounds are polynomial in MM, as in [2]. At a node of the recursion rem denotes the target still available there.

Culler [3] identifies cl⁡(w)\operatorname{cl}(w) with the least genus of a one-face map with boundary ww. The best published bound we know is that of Bartholdi, Fialkovski and Ivanov [2] (henceforth BFI): their Theorem A gives, for non-trivial w∈[F,F]w\in[F,F], a cancellation-free factorisation

w=W1a−1W2b−1W3aW4bW5,a,b∈X∪X−1,(2)w=W_1a^{-1}W_2b^{-1}W_3aW_4bW_5,\qquad a,b\in X\cup X^{-1}, \tag*{(2)}

with cl⁡(W1W4W3W2W5)=cl⁡(w)−1\operatorname{cl}(W_1W_4W_3W_2W_5)=\operatorname{cl}(w)-1. Repeating those four cut points at each of the gg levels costs O(M4g)O(M^{4g}) on an FF-RAM (their Corollary C), and their §2.4 improves the cl⁡=1\operatorname{cl}=1 case to an average O(M2)O(M^2) by a 2×22\times2 matrix trace test.

2020 Mathematics Subject Classification. Primary 68Q25, 68W40; Secondary 20E05, 20F10.

We keep this recursion and replace two of its ingredients. Base case: one Manacher sweep builds an arc graph in which a word of class one shows up as a walk of at most three arcs from a vertex to its antipode (O(M3)O(M^3) worst case, O(M)O(M) in expectation, Theorem 2.8). Recursion: a peel is an exchange of two blocks, so three cut points replace four and the worst case is O(M3g)O(M^{3g}). That bound alone does not make the search complete: Theorem 3.6 supplies, at every node, a peel lowering the class by exactly one.

All bounds are in the unit-cost model, one step per letter read, lookup or comparison. BFI count group operations, so a residual of length MM is MM steps here and one there, and their O(M4g)O(M^{4g}) is O(M4g+1)O(M^{4g+1}) steps: comparing exponents alone is the conservative choice.

Theorem 1.1 (main). For a reduced w∈[F,F]w \in[F,F] of length MM and a target g≥1g \ge1, a deterministic algorithm returns a decomposition of ww into at most gg commutators, or reports cl⁡(w)>g\operatorname{cl}(w) > g, in O(M3g)O(M^{3g}) steps and O(M2)O(M^2) space. The algorithm is deterministic; for g=1g = 1 its expected running time is O(M)O(M) when the input is drawn uniformly from reduced words of length MM conditioned on lying in [F,F][F,F] — the expectation is over inputs only.

For w=1w = 1 the answer is the empty decomposition; assume w≠1w \ne1 below, so M≥4M \ge4. Only targets g≤⌊M/4⌋g \le\lfloor M/4 \rfloor need be searched. By Culler [3] the class of ww is the genus κ\kappa of a one-face map whose edges are the inverse pairs of letters of ww, so that map has E=M/2E = M/2 edges and Euler’s formula gives $2\kappa = E - V + 1 \le E = M/2$; hence cl⁡(w)≤M/4\operatorname{cl}(w) \le M/4, and being an integer, cl⁡(w)≤⌊M/4⌋\operatorname{cl}(w) \le\lfloor M/4 \rfloor. A target g>⌊M/4⌋g > \lfloor M/4 \rfloor is replaced by min⁡(g,⌊M/4⌋)\min(g,\lfloor M/4 \rfloor) and searched at that value: the search still returns a decomposition into at most cl⁡(w)≤⌊M/4⌋≤g\operatorname{cl}(w) \le\lfloor M/4 \rfloor\le g commutators. Throughout the search gM≤M2gM \le M^2.

The class-one case: an expected-linear base test

Notation and the cost model

Write w=w0⋯wM−1w = w_0 \cdots w_{M-1} and read the indices mod MM. A cc-word is a word of class one. By Wicks [5] a cyclically reduced word w≠1w \ne1 is a cc-word iff some cyclic shift of it equals UVWU−1V−1W−1UVWU^{-1}V^{-1}W^{-1} without cancellation, UU, VV, WW being contiguous blocks, possibly empty; in general ww is a cc-word iff it is conjugate to such a word. The three cut points of that shift are what the base test looks for, on the cyclically reduced residual. A word of [F,F][F,F] has even length and trivial abelianisation. Since cl⁡\operatorname{cl} is conjugacy-invariant we first strip the longest mirror-inverse prefix w[0:s]w[0:s], that is the largest s=smax⁡s = s_{\max} with wj=wM−1−j−1w_j = w^{-1}_{M-1-j} for all j<sj < s. Then w=xzx−1w = xzx^{-1} with x=w[0:smax⁡]x = w[0:s_{\max}] and z=w[smax⁡:M−smax⁡]z = w[s_{\max}:M-s_{\max}]; for w∈[F,F]w \in[F,F] reduced and non-trivial one has smax⁡≤half−2s_{\max} \le\mathit{half} - 2, where half=M/2\mathit{half} = M/2, so zz keeps at least four letters and is cyclically reduced (Lemma 2.6).

Cost model. Letters are integers. An average is taken over ww uniform among the A(A−1)M−1A(A-1)^{M-1} reduced words of length MM over X∪X−1X \cup X^{-1}, where A=2∣X∣≥4A = 2|X| \ge4; these are the words the algorithm has on hand, and the average of Theorem 2.8 is over those of them that lie in [F,F][F,F], that is, conditioned on w∈[F,F]w \in[F,F]. Free reduction and the test w∈[F,F]w \in[F,F] are O(M)O(M) stack passes, dominated by every bound below.

Pruning invariant. Let rr be a reduced residual and write r=xzx−1r=xzx^{-1}, where zz is its cyclically reduced core, unique up to cyclic rotation. For an ordered pair U=abU=ab of letters, let bUb_U be the number of cyclic positions qq of zz with zqzq+1=Uz_qz_{q+1}=U, indices read mod ∣z∣|z|. No such block is its own inverse, since zz is cyclically reduced. The defect is

DH⁡(r)=∑{U,U−1}∣bU−bU−1∣.(3)\operatorname{DH}(r)=\sum_{\{U,U^{-1}\}}\lvert b_U-b_{U^{-1}}\rvert. \tag*{(3)}

A cyclic rotation of zz permutes the counted blocks, so DH⁡(r)\operatorname{DH}(r) does not depend on the chosen rotation of the core or on where rr was anchored. We use the following self-contained bound.

Lemma 2.1 (defect bound). For every reduced non-trivial r∈[F,F]r \in[F,F],

cl⁡(r)≥DH⁡(r)+612=DH⁡(r)12+12.(4)\operatorname{cl}(r)\ge\frac{\operatorname{DH}(r)+6}{12}=\frac{\operatorname{DH}(r)}{12}+\frac{1}{2}. \tag*{(4)}

Proof. Write r=xzx−1r=xzx^{-1} as above, m=∣z∣=2nm=|z|=2n, and let κ=cl⁡(z)=cl⁡(r)\kappa=\operatorname{cl}(z)=\operatorname{cl}(r). Choose a pairing π\pi attaining the maximum in Proposition 3.2 below and set σ=ρπ\sigma=\rho\pi, with ρ=(0 1 ⋯ m−1)\rho=(0\ 1\ \cdots\ m-1) and c=c(σ)c=c(\sigma); then 2κ=n+1−c2\kappa=n+1-c. Cyclically reducedness gives σ(q)≠q\sigma(q)\ne q for all qq, since σ(q)=q\sigma(q)=q would mean π(q)=q−1\pi(q)=q-1, that is, adjacent inverse letters across the cyclic seam of zz. A block zqzq+1z_qz_{q+1} has an inverse block at π(q+1)\pi(q+1) precisely when π(q)=π(q+1)+1\pi(q)=\pi(q+1)+1, equivalently σ2(q+1)=q+1\sigma^2(q+1)=q+1; as σ\sigma has no fixed points, this happens exactly when q+1q+1 lies in a 2-orbit of σ\sigma. Each 2-orbit {a,b}\{a,b\} yields exactly the two matched block positions a−1,b−1a-1,b-1, one block and its inverse. Let tt be the number of 2-orbits, so 2t2t positions are matched. Fix an inverse-pair class {U,U−1}\{U,U^{-1}\} with original counts b,b′b,b' and cUc_U matched blocks of each kind. Removing the matched pairs subtracts the same cUc_U from both counts, so the imbalance stays ∣b−b′∣|b-b'|; the unmatched positions of the class number (b−cU)+(b′−cU)=∣b−b′∣+2(min⁡(b,b′)−cU)≥∣b−b′∣(b-c_U)+(b'-c_U)=|b-b'|+2(\min(b,b')-c_U)\ge|b-b'|. Summing the imbalance over classes gives at most the total number m−2tm-2t of unmatched positions: DH⁡(z)≤m−2t\operatorname{DH}(z)\le m-2t. Let the remaining orbits have lengths L1,…,Ls≥3L_1,\ldots,L_s\ge3. Then m=2t+∑iLim=2t+\sum_iL_i and m−2c=∑i(Li−2)m-2c=\sum_i(L_i-2). Since Li≤3(Li−2)L_i\le3(L_i-2) for Li≥3L_i\ge3,

DH⁡(r)≤∑iLi≤3∑i(Li−2)=3(m−2c)=12κ−6,\operatorname{DH}(r)\le\sum_iL_i\le3\sum_i(L_i-2)=3(m-2c)=12\kappa-6,

which is (4). □\square

In general, a residual whose own target is tt is rejected at DH⁡≥12t−5\operatorname{DH}\ge12t-5: then (4) gives cl⁡≥t+112\operatorname{cl}\ge t+\frac{1}{12}, hence cl⁡≥t+1\operatorname{cl}\ge t+1 above its target. Thus at the root t=remt=rem, while a child of a node with target remrem has t=rem−1t=rem-1.

The arc graph and a three-hop walk

Definition 2.2. Let MM be even, half=M/2half = M/2. There is an arc of length ℓ\ell from xx, written x→x+ℓx \to x+\ell (1≤ℓ≤half1 \le\ell\le half), if

wx+t=wx+half+ℓ−1−t−1(0≤t<ℓ).w_{x+t}=w^{-1}_{x+half+\ell-1-t}\qquad(0 \le t < \ell).

indices mod MM. The arc graph G(w)G(w) has vertex set Z/M\mathbb{Z}/M, with an arc x→x+ℓx \to x+\ell for every pair (x,ℓ)(x,\ell) satisfying the condition.

On abca−1b−1c−1abc a^{-1}b^{-1}c^{-1} three unit arcs give 0→1→2→30 \to1 \to2 \to3, while [ab,c][ab,c] needs the length-2 arc 0→20 \to2. For fixed xx the conditions are not nested in ℓ\ell, but for a fixed centre they are: the arc x→x+ℓx \to x+\ell has centre

c≡2x+ℓ−1(modM),(5)c \equiv2x+\ell-1 \pmod M, \tag*{(5)}

and its ℓ\ell conditions are one palindromic sweep of an interleaved word about c+12c+\frac{1}{2}.

Lemma 2.3 (the arcs of one centre). Read v2j=wjv_{2j}=w_j, v2j+1=whalf+j−1v_{2j+1}=w^{-1}_{half+j} on Z/2M\mathbb{Z}/2M, so that vv has length 2M2M. The arc x→x+ℓx \to x+\ell of centre cc exists iff the 2ℓ2\ell positions 2x,…,2x+2ℓ−12x,\ldots,2x+2\ell-1 of vv form a palindrome of even radius ℓ\ell about c+12c+\frac{1}{2}; hence, rcr_c being the radius of vv there, the arcs of centre cc are the lengths ℓ≤min⁡(rc,half)\ell\le\min(r_c,half) with ℓ≡c+1(mod2)\ell\equiv c+1 \pmod2.

Proof. With q=x+half+ℓ−1−tq=x+half+\ell-1-t the condition is wx+t=wq−1w_{x+t}=w_q^{-1}, that is

v2x+2t=v2(q−half)+1;v_{2x+2t}=v_{2(q-half)+1};

by v2j+1=whalf+j−1v_{2j+1}=w^{-1}_{half+j} the letter wq−1w_q^{-1} sits at v2(q−half)+1v_{2(q-half)+1}, and 2(q−half)+1=2x+2ℓ−1−2t2(q-half)+1=2x+2\ell-1-2t. The two indices add up to 2c+12c+1: each condition is one mirror pair about c+12c+\frac{1}{2}, and the ℓ\ell of them walk through the block [2x,2x+2ℓ−1][2x,2x+2\ell-1] from its ends inwards. Conversely such a palindrome meets all ℓ\ell conditions of the arc at x≡(c+1−ℓ)/2x \equiv(c+1-\ell)/2, so xx is an integer exactly when ℓ≡c+1(mod2)\ell\equiv c+1 \pmod2.

The centre of (5) is a class modulo MM; in vv, whose indices are modulo 2M2M, it has the two lifts c+12c+\frac{1}{2} and c+M+12c+M+\frac{1}{2}. That is what identifies the two twin sources: the arc at xx has its palindrome centre at c+12c+\frac{1}{2} in vv, the arc at x+halfx+half at the antipodal c+M+12c+M+\frac{1}{2}, and the two radii agree on lengths ℓ≤half\ell\le half, because the shift x↦x+halfx \mapsto x+half carries arcs to arcs and the mirror pairs about c+M+12c+M+\frac{1}{2} read wy=whalf+c−y−1w_y=w^{-1}_{half+c-y} as well — the same ℓ\ell conditions, read at the antipodal positions. The full radii of vv at the two centres need not agree, but only lengths up to halfhalf are arcs, so one radius per centre suffices and the sweep of vv sees every arc. □

So a length determines its two sources, xx and x+halfx+half. One Manacher sweep [4] on three copies of vv, a word of length 6M6M, so that no radius is cut off at an end, computes all circular radii in O(M)O(M) and lists the arcs of a centre in time proportional to their number: the two sources are twins sharing the centre, and an arc’s centre is determined by its source and its length, so nothing is emitted twice. Building GG costs O(M+ν)O(M+\nu) with ν=∣E(G)∣\nu=|E(G)|; let Δ\Delta be the maximum degree, in or out, and Q=∑vdeg⁡−(v)deg⁡+(v)Q=\sum_v \deg^{-}(v)\deg^{+}(v) the number of two-arc paths, so Q≤ΔνQ\le\Delta\nu.

The search. The shift x↦x+halfx\mapsto x+half carries the arc (x,ℓ)(x,\ell) to (x+half,ℓ)(x+half,\ell), so it is an automorphism of GG and it suffices to test the halfhalf starts i<halfi<half.

Arcs are read modulo MM, so the intermediate vertices of a longer walk may wrap; in this range the only arc that could be missed is the single arc i→i+halfi \to i + half of length halfhalf, which cyclic reducedness forbids as in the proof of Proposition 2.4. So only two and three hops need testing. Mark the in-neighbours of i+halfi + half in a Boolean array that carries a version stamp, so that a slot counts as marked only during the start that wrote it and no array is cleared between starts; then run through the arcs out of ii. A first hop i→ui \to u is already a hit if uu is marked; otherwise the arcs out of uu are looked up in the array one by one, deg⁡+(u)\deg^{+}(u) queries of O(1)O(1). Every walk of at most three arcs from ii is inspected this way, and the first hit returns its intermediate vertices as cut points.

Proposition 2.4 (Wicks’ criterion as a walk). Let w≠1w \ne1 be a cyclically reduced word of even length. Then cl⁡(w)=1\operatorname{cl}(w) = 1 iff, for some i<halfi < half, G(w)G(w) has a walk of at most three arcs from ii to i+halfi + half; the intermediate vertices are the cut points.

Proof. If w=UVWU−1V−1W−1w = UVW U^{-1}V^{-1}W^{-1} without cancellation, with p1=0p_1 = 0, p2=∣U∣p_2 = |U|, p3=∣UV∣p_3 = |UV|, the three blocks give arcs p1→p2p_1 \to p_2, p2→p3p_2 \to p_3, p3→p1+halfp_3 \to p_1 + half of lengths ∣U∣,∣V∣,∣W∣|U|, |V|, |W|, which sum to halfhalf; an empty block simply drops an arc.

Conversely, let a walk of at most three arcs lead from ii to i+halfi + half, and pad it by repeating vertices until it reads i→y→z→i+halfi \to y \to z \to i + half, with lengths ℓ1,ℓ2,ℓ3≥0\ell_1,\ell_2,\ell_3 \ge0; a length 00 is the degenerate arc at a repeated vertex and contributes an empty block. Their sum lies in [0,3half][0,3half] and is ≡half(modM)\equiv half \pmod{M}, hence equals halfhalf or 3half3half. No arc of length halfhalf can occur: such an arc out of any xx requires wx+half−1=wx+half−1w_{x+half-1} = w^{-1}_{x+half}, and those two letters are cyclically adjacent in a cyclically reduced ww. Hence the sum cannot be 3half3half, and when it is halfhalf every ℓi<half\ell_i < half: the single-arc case (half,0,0)(half,0,0) and its permutations are excluded too, and the walk is monotone.

Now cut at yy and zz. We get U=w[i:y]U = w[i:y], V=w[y:z]V = w[y:z], W=w[z:i+half]W = w[z:i + half], and the arc conditions say that the antipodal half reads U−1V−1W−1U^{-1}V^{-1}W^{-1}. Every junction but the base one joins adjacent letters of the reduced word ww; the base one does not cancel, again by cyclic reducedness. That is Wicks’ form, so cl⁡(w)=1\operatorname{cl}(w) = 1. The decomposition is explicit: UVWU−1V−1W−1=[UV,WU−1]UVW U^{-1}V^{-1}W^{-1} = [UV, WU^{-1}], so the search returns u=UVu = UV and v=WU−1v = WU^{-1}. These decompose the cyclically reduced residual; a node holding r=xzx−1r = xzx^{-1} returns [xux−1,xvx−1][xux^{-1}, xvx^{-1}]. □

Proposition 2.5 (correctness and worst case). Let ww be as in Proposition 2.4. If ww is a cc-word, the build and search above return its cut points. One pass costs O(M+ν+Q)O(M+\nu+Q), hence O(M3)O(M^3) in the worst case.

Proof. The build is O(M+ν)O(M+\nu) and correctness is Proposition 2.4. For the search, a start ii pays deg⁡−(i+half)\deg^{-}(i+half) for the marking, and deg⁡+(u)\deg^{+}(u) for each arc i→ui \to u out of it; summing over the starts gives at most ν+Q\nu+Q per pass, and the build adds ν\nu. With ν≤Mhalf≤M2\nu\le M\mathit{half} \le M^2 (one arc of each length per vertex) and Q≤Δν≤M3Q \le\Delta\nu\le M^3, that is O(M3)O(M^3).

The bound is attained on [a,bm][a,b^m], M=6m+6M=6m+6, which is not a cc-word, so every one of the half\mathit{half} starts is examined. Each of its three bmb^m runs faces a b−mb^{-m} run at the antipodal position, and for each length 2≤ℓ≤m2\le\ell\le m this yields 6(m−ℓ+1)6(m-\ell+1) arcs of length ℓ\ell, plus MM arcs of length one; hence ν=M+3m(m−1)=3m2+3m+6=Θ(M2)\nu=M+3m(m-1)=3m^2+3m+6=\Theta(M^2). Convolving the in/out degrees of this arc family gives Q=m3+11m=Θ(M3)Q=m^3+11m=\Theta(M^3). □

The expected cost

Lemma 2.6 (the longest strip suffices). Let w∈[F,F]w\in[F,F] be reduced, non-trivial and of even length. Then smax⁡≤half−2s_{\max}\le\mathit{half}-2, the residual z=w[smax⁡:M−smax⁡]z=w[s_{\max}:M-s_{\max}] is cyclically reduced, and cl⁡(z)=cl⁡(w)\operatorname{cl}(z)=\operatorname{cl}(w); so the base test decides $\operatorname{cl}(w)=1 correctly.

Proof. Put M=2s+mM=2s+m with s=smax⁡s=s_{\max} and z=w[s:M−s]z=w[s:M-s], so ∣z∣=m|z|=m and w=xzx−1w=xzx^{-1} with x=w[0:s]x=w[0:s]; conjugation gives cl⁡(z)=cl⁡(w)\operatorname{cl}(z)=\operatorname{cl}(w). The mirror condition holds at level j<sj<s exactly when wj=wM−1−j−1w_j=w^{-1}_{M-1-j}. At the next level j=sj=s it reads ws=wM−1−s−1w_s=w^{-1}_{M-1-s}, and since z0=wsz_0=w_s and zm−1=wM−s−1=wM−1−s−1z_{m-1}=w_{M-s-1}=w_{M-1-s}^{-1}, this is precisely z0=zm−1−1z_0=z_{m-1}^{-1}: the two ends of the residual are inverse. Thus if zz were not cyclically reduced the prefix would extend to s+1s+1, contradicting maximality. This covers s=0s=0, where z=wz=w, and m=2m=2, where a reduced two-letter word is automatically cyclically reduced.

If s≥halfs\ge\mathit{half}, then j=half−1<sj=\mathit{half}-1<s and the condition at that level reads whalf−1=wM−half−1=whalf−1w_{\mathit{half}-1}=w^{-1}_{M-\mathit{half}}=w^{-1}_{\mathit{half}}, which reducedness forbids; hence smax⁡≤half−1s_{\max}\le\mathit{half}-1. Equality would give m=2m=2 and z=whalf−1whalfz=w_{\mathit{half}-1}w_{\mathit{half}}, which is reduced, hence not aa−1aa^{-1}, and has non-trivial abelianisation, contradicting w∈[F,F]w\in[F,F]. Therefore s≤half−2s\le\mathit{half}-2, zz is cyclically reduced, and Proposition 2.4 decides cl⁡(z)=1\operatorname{cl}(z)=1, that is cl⁡(w)=1\operatorname{cl}(w)=1. □

Lemma 2.7 (the abelianisation of a random reduced word). Let zz be uniform among the reduced words of length mm over X∪X−1X\cup X^{-1}, and let S(z)=∑izi∈Z∣X∣S(z)=\sum_i z_i\in\mathbb{Z}^{|X|} be its abelianisation, so that z∈[F,F]z\in[F,F] reads S(z)=0S(z)=0. Then

(i) the letters form a Markov chain, z0z_0 uniform on X∪X−1X\cup X^{-1} and, given zi−1z_{i-1}, ziz_i uniform among the A−1A-1 letters not inverse to zi−1z_{i-1}; (ii) there are c1,c2,c3>0c_1,c_2,c_3>0, depending only on XX, with

c1m−∣X∣/2≤P(S(z)=δ)≤c2m−∣X∣/2if ∥δ∥≤c3mc_1m^{-|X|/2}\le\mathbb{P}(S(z)=\delta)\le c_2m^{-|X|/2}\qquad\text{if }\|\delta\|\le c_3\sqrt{m}

for every δ\delta whose parity is compatible with mm, and the upper bound P(S(z)=δ)≤c2m−∣X∣/2\mathbb{P}(S(z)=\delta)\le c_2m^{-|X|/2} holds for all δ\delta; (iii) if BB is a union of at most KK intervals of positions with ∣B∣≤m/2|B|\le m/2, and uu is a pattern on BB, then

P(z∣B=u∣S(z)=0)≤c4P(z∣B=u),\mathbb{P}(z|_B=u\mid S(z)=0)\le c_4\mathbb{P}(z|_B=u),

where c4c_4 depends only on XX and KK; moreover c2/c1→1c_2/c_1\to1 as m→∞m\to\infty.

Proof. (i) is the measure itself: z0z_0 is uniform on X∪X−1X\cup X^{-1}, and each subsequent letter is uniform on the A−1A-1 letters other than the inverse of its predecessor. Proof of (ii). Observe first that S(z)=∑iziS(z)=\sum_i z_i is an additive functional of the aperiodic irreducible chain of (i). Its increment has stationary mean zero and stationary increment covariance 1∣X∣I\frac{1}{|X|}I; the transition operator has eigenvalue −1/(2∣X∣−1)-1/(2|X|-1) on the mean-zero symmetric subspace and +1/(2∣X∣−1)+1/(2|X|-1) on the antisymmetric one, so the chain is uniformly ergodic. The observable zi∈Z∣X∣z_i\in\mathbb{Z}^{|X|} is antisymmetric, hence lies in the latter eigenspace, with λ=1/(2∣X∣−1)\lambda=1/(2|X|-1), and Var⁡(S(z))∼m∣X∣−1I=1∣X∣1+λ1−λmI≻0\operatorname{Var}(S(z))\sim\frac{m}{|X|-1}I=\frac{1}{|X|}\frac{1+\lambda}{1-\lambda}mI\succ0.

Fourier inversion now gives P(S(z)=δ)≍m−∣X∣/2\mathbb{P}(S(z)=\delta)\asymp m^{-|X|/2} uniformly for ∥δ∥=O(m)\|\delta\|=O(\sqrt{m}). Write φ(θ)=E[ei⟨θ,S(z)⟩]\varphi(\theta)=\mathbb{E}[e^{i\langle\theta,S(z)\rangle}]. Since every letter contributes ±ex\pm e_x, S(z)S(z) lies in the index-two coset Lm={δ:∑xδx≡m(mod2)}L_m=\{\delta:\sum_x\delta_x\equiv m\pmod2\}. Let ab⁡(d)=±ex\operatorname{ab}(d)=\pm e_x denote the vector of a letter dd, so that P^θ(c,d)=P(c,d)ei⟨θ,ab⁡(d)⟩\widehat{P}_\theta(c,d)=P(c,d)e^{i\langle\theta,\operatorname{ab}(d)\rangle} and ∣P^θ∣=P|\widehat{P}_\theta|=P. Since PP is irreducible and aperiodic, Wielandt’s equality case forces P^θ=λDPD−1\widehat{P}_\theta=\lambda_DPD^{-1}, with ∣λD∣=1|\lambda_D|=1 and DD diagonal unitary, whenever ρ(P^θ)=1\rho(\widehat{P}_\theta)=1. Entrywise this reads ei⟨θ,ab⁡(d)⟩=λei(ϕc−ϕd)e^{i\langle\theta,\operatorname{ab}(d)\rangle}=\lambda e^{i(\phi_c-\phi_d)} for every d≠cd\ne c; the left side is independent of cc and each dd has A−1≥3A-1\ge3 predecessors, so all ϕc\phi_c coincide and ei⟨θ,ab⁡(d)⟩=λe^{i\langle\theta,\operatorname{ab}(d)\rangle}=\lambda for every dd. Taking d=xd=x and d=x−1d=x^{-1} gives eiθx=e−iθx=λe^{i\theta_x}=e^{-i\theta_x}=\lambda: all θx\theta_x share one common value c=±1c=\pm1, so the only characters of modulus one are θ=0\theta=0 and θ∗=(π,…,π)\theta_*=(\pi,\ldots,\pi). Near θ=0\theta=0, ∣φ(θ)∣≤exp⁡(−cm∥θ∥2)|\varphi(\theta)|\le\exp(-cm\|\theta\|^2), and θ∗\theta_* carries the same peak since φ(θ∗+ϵ)=(−1)mφ(ϵ)\varphi(\theta_*+\epsilon)=(-1)^m\varphi(\epsilon); the two add on LmL_m and cancel off it. Away from both, ∣φ(θ)∣≤ϱm|\varphi(\theta)|\le\varrho^m (ϱ<1\varrho<1). The main term is the same Gaussian integral in the upper and lower bounds, whence c2/c1→1c_2/c_1\to1; the same bounds give the upper estimate for every δ\delta, with no restriction on its size.

Proof of (iii). Write the complement of BB as K+1K+1 gaps, some empty, with r1,…,rK+1≥0r_1,\ldots,r_{K+1}\ge0 free letters and r=∑jrj=m−∣B∣≥m/2r=\sum_jr_j=m-|B|\ge m/2. An interior gap has both flanking letters fixed by uu; only the two end gaps have an endpoint outside BB. Condition further on a complete assignment β\beta of those at most two outer endpoint letters. Given uu and β\beta, the letters in distinct gaps are independent: a gap with rj≥1r_j\ge1 free letters is a Markov bridge of rj+1r_j+1 transitions between its fixed endpoints, its increment weight being the corresponding product of the refined transition matrix P(⋅,⋅;s)P(\cdot,\cdot;s), s∈Z∣X∣s\in\mathbb{Z}^{|X|} (the fixed right endpoint shifts ss by a constant); an empty gap contributes the point mass 11 at 00.

The spectral gap gives Pt(a,b)=π(b)(1+O(ϱt))P^t(a,b)=\pi(b)(1+O(\varrho^t)) uniformly in a,ba,b, so fixed endpoints cost a factor bounded independently of them; the Fourier estimate of (ii) applies to the refined product and gives P(Sgap,j=s∣u,β)≤c2rj−∣X∣/2\mathbb{P}(S_{\mathrm{gap},j}=s\mid u,\beta)\le c_2r_j^{-|X|/2} uniformly in ss and in the endpoints when rj≥1r_j\ge1. Since S(z)=SB(u)+∑jSgap,jS(z)=S_B(u)+\sum_jS_{\mathrm{gap},j} and the gap increments are independent given u,βu,\beta, the conditional law of S(z)S(z) is the convolution of the K+1K+1 gap laws, shifted by SB(u)S_B(u). A convolution’s point mass is at most the largest point mass of any factor, and some gap has rj≥r/(K+1)≥m/(2K+2)r_j\ge r/(K+1)\ge m/(2K+2), giving P(S(z)=0∣u,β)≤c5m−∣X∣/2\mathbb{P}(S(z)=0\mid u,\beta)\le c_5m^{-|X|/2} uniformly in β\beta.

Averaging over the at most A2A^2 values of β\beta preserves this bound, so P(S(z)=0∣z∣B=u)≤c5m−∣X∣/2\mathbb{P}(S(z)=0\mid z|_B=u)\le c_5m^{-|X|/2}. Dividing by the lower bound of (ii) at δ=0\delta=0 (here mm is even) proves (iii). □\square

Theorem 2.8 (expected linear time). The cl = 1 test runs in O(M)O(M) expected steps on a uniformly random reduced word of length MM, conditioned on w∈[F,F]w\in[F,F], in the unit-cost model.

Proof. There is a constant C>0C>0 with

T(w)≤C(M+ν+Q)(6)T(w) \le C(M+\nu+Q) \tag*{(6)}

for every ww: the sweep is O(M)O(M), emitting the arcs is O(ν)O(\nu), and the walk costs at most ν+Q\nu+Q by Proposition 2.5.

The unconditional measure. We first estimate in the uniform measure on reduced residuals zz of length mm, so half=m/2half=m/2 here; at the end m≤Mm\le M. Write x:=1/(A−1)x:=1/(A-1). For a fixed arc candidate (x0,ℓ)(x_0,\ell) the ℓ\ell conditions pair the positions x0+tx_0+t and x0+half+ℓ−1−tx_0+half+\ell-1-t for 0≤t<ℓ0\le t<\ell. These pairs are disjoint, and a pair whose positions are adjacent has probability 00 by reducedness. Otherwise reveal the word from left to right: when the later endpoint of a pair is reached, the earlier letter is already known, and the Markov rule prescribes its inverse with probability either 00 (if forbidden by the preceding letter) or exactly xx. Multiplying over the ℓ\ell pairs gives P(arc of length ℓ)≤xℓ\mathbb{P}(\text{arc of length }\ell)\le x^\ell.

A vertex carries at most one arc of each length, so a union bound over the mm halfhalf candidate arcs gives E[ν]≤m∑ℓ≥1xℓ=mx/(1−x)\mathbb{E}[\nu]\le m\sum_{\ell\ge1}x^\ell=mx/(1-x). A two-arc path with lengths (ℓ1,ℓ2)(\ell_1,\ell_2) presupposes the longer of its two arcs, hence has probability at most xmax⁡(ℓ1,ℓ2)x^{\max(\ell_1,\ell_2)}, so

E[Q]≤m∑ℓ1,ℓ2≥1xmax⁡(ℓ1,ℓ2)=mx(1+x)(1−x)2.\mathbb{E}[Q]\le m\sum_{\ell_1,\ell_2\ge1}x^{\max(\ell_1,\ell_2)}=m\frac{x(1+x)}{(1-x)^2}.

Adding the three terms of (6) applied to zz gives E[T]≤C(1+x1−x+x(1+x)(1−x)2)m<3Cm≤3CM\mathbb{E}[T]\le C\left(1+\frac{x}{1-x}+\frac{x(1+x)}{(1-x)^2}\right)m<3Cm\le3CM for A≥4A\ge4: a bound linear in MM.

Two conditionings. The measure of the theorem differs from the one the test actually runs under in two ways; we handle them in turn. First fix k=smax⁡k=s_{\max}. Writing w=xzx−1w=xzx^{-1} with ∣x∣=k|x|=k and ∣z∣=m=M−2k|z|=m=M-2k, we have smax⁡=ks_{\max}=k exactly when z0≠zm−1−1z_0\ne z_{m-1}^{-1} and xx is reduced with xk−1∉{z0−1,zm−1}x_{k-1}\notin\{z_0^{-1},z_{m-1}\}, the two junctions. Indeed x−1x^{-1} reads xk−1−1⋯x0−1x_{k-1}^{-1}\cdots x_0^{-1}, so wM−1−j=xj−1=wj−1w_{M-1-j}=x_j^{-1}=w_j^{-1} for every j<kj<k whatever xx is; the prefix extends to j=kj=k only when z0=zm−1−1z_0=z_{m-1}^{-1}. Under z0≠zm−1−1z_0\ne z_{m-1}^{-1} the two forbidden last letters of xx are distinct.

For k≥1k\ge1 a reduced word of length kk has (A−1)k−1(A-1)^{k-1} continuations for each prescribed last letter, so exactly (A−2)(A−1)k−1(A-2)(A-1)^{k-1} words xx are admissible; for k=0k=0 the only admissible xx is the empty word, a count of one. Distinct xx give distinct ww. For each fixed kk the tilt is therefore a constant, independent of zz: conditional on smax⁡=ks_{\max}=k, zz is uniform among the reduced words of length mm with z0≠zm−1−1z_0\ne z_{m-1}^{-1}. The event E={z0≠zm−1−1}E=\{z_0\ne z_{m-1}^{-1}\} has probability bounded away from 00 and 11: the letter chain has P(z0=a,zm−1=b)=(1/A)Pm−1(a,b)=(1+o(1))/A2\mathbb{P}(z_0=a,z_{m-1}=b)=(1/A)P^{m-1}(a,b)=(1+o(1))/A^2, so P(E)=1−A−1+o(1)\mathbb{P}(E)=1-A^{-1}+o(1).

The abelianisation conditioning. Second, as xx and x−1x^{-1} cancel, w∈[F,F]w\in[F,F] reads S(z)=0S(z)=0. Intervals are those of the linear word zz, of length mm; a block wrapping across the end splits into at most two, so an arc occupies at most four intervals and a two-arc path at most eight. We need the conditioning on S(z)=0S(z)=0 only through its denominator. Write Nt=#{z∈Rt:S(z)=0}N_t=\#\{z\in\mathcal{R}_t:S(z)=0\}, where Rt\mathcal{R}_t is the set of reduced words of length tt. A word with z0=zm−1−1z_0=z_{m-1}^{-1} is z=aya−1z=aya^{-1} with y∈Rm−2y\in\mathcal{R}_{m-2} and S(y)=0S(y)=0; as aa has AA choices this gives P(Ec∣S(z)=0)≤ANm−2/Nm\mathbb{P}(E^c\mid S(z)=0)\leq AN_{m-2}/N_m. By (ii), for even t≥t0t\geq t_0 one has Nt≍A(A−1)t−1t−∣X∣/2N_t\asymp A(A-1)^{t-1}t^{-|X|/2}, with t0t_0 depending only on XX, not on mm or MM; only even tt can have Nt>0N_t>0. For the finitely many even m<t0m<t_0 the cost is bounded by a constant depending only on XX, absorbed by enlarging CC in (6). Hence, for m≥t0m\geq t_0,

P(Ec∣S(z)=0)≤A(A−1)2c2c1(mm−2)∣X∣/2=A(A−1)2+o(1)≤49+o(1)<12.\mathbb{P}(E^c\mid S(z)=0)\leq\frac{A}{(A-1)^2}\frac{c_2}{c_1}\left(\frac{m}{m-2}\right)^{|X|/2} =\frac{A}{(A-1)^2}+o(1)\leq\frac{4}{9}+o(1)<\frac{1}{2}.

Hence P(E∣S(z)=0)≥12\mathbb{P}(E\mid S(z)=0)\geq\frac{1}{2}, and Bayes with P(S(z)=0)≍m−∣X∣/2\mathbb{P}(S(z)=0)\asymp m^{-|X|/2} from (ii) gives P(S(z)=0∣E)≍m−∣X∣/2\mathbb{P}(S(z)=0\mid E)\asymp m^{-|X|/2} uniformly in kk.

Transferring the pattern estimate. Let A={z∣B=u}A=\{z|_B=u\} be a pattern event with ∣B∣≤m/2|B|\leq m/2. Bayes and P(E∣S(z)=0)≥12\mathbb{P}(E\mid S(z)=0)\geq\frac{1}{2} give

P(A∣E,S(z)=0)=P(A∩E∣S(z)=0)P(E∣S(z)=0)≤P(A∣S(z)=0)P(E∣S(z)=0)≤2cP(A),\mathbb{P}(A\mid E,S(z)=0)=\frac{\mathbb{P}(A\cap E\mid S(z)=0)}{\mathbb{P}(E\mid S(z)=0)} \leq\frac{\mathbb{P}(A\mid S(z)=0)}{\mathbb{P}(E\mid S(z)=0)} \leq2c\mathbb{P}(A),

using (iii) in the form P(A∣S(z)=0)≤cP(A)\mathbb{P}(A\mid S(z)=0)\leq c\mathbb{P}(A); the bound is relative to the unconditional pattern probability (not to P(A∣E)\mathbb{P}(A\mid E), which need not hold). With K=8K=8, a pattern on a union BB of at most eight intervals with ∣B∣≤m/2|B|\leq m/2 therefore obeys P(z∣B=u∣E,S(z)=0)≤c′P(z∣B=u)\mathbb{P}(z|_B=u\mid E,S(z)=0)\leq c'\mathbb{P}(z|_B=u) with c′=2cc'=2c: the m−∣X∣/2m^{-|X|/2} from the bridge convolution cancels the same factor in the denominator. An arc or a path is specified by its position set, a union of at most eight intervals (for a path ∣B∣≤2(ℓ1+ℓ2)|B|\leq2(\ell_1+\ell_2)). The patterns uu compatible with a fixed position set define disjoint events, and c′c' does not depend on uu: fix the position set BB of a candidate arc or path first, then sum the display over all uu compatible with BB, which costs at most the same constant since ∑uP(z∣B=u)≤1\sum_u\mathbb{P}(z|_B=u)\leq1. Hence the arc bound survives as soon as ℓ≤m/4\ell\leq m/4 and the path bound as soon as ℓ1+ℓ2≤m/4\ell_1+\ell_2\leq m/4.

The remaining patterns have ∣B∣>m/2|B|>m/2: an arc then has ℓ>m/4\ell>m/4, and a two-arc path has max⁡(ℓ1,ℓ2)>m/8\max(\ell_1,\ell_2)>m/8. They are counted on the residual, of length mm, so there are O(m2)O(m^2) arcs and O(m3)O(m^3) paths; each has probability at most xℓx^\ell or xmax⁡(ℓ1,ℓ2)x^{\max(\ell_1,\ell_2)}, and conditioning multiplies this by at most (P(E)P(S(z)=0∣E))−1=O(m∣X∣/2)\bigl(\mathbb{P}(E)\mathbb{P}(S(z)=0\mid E)\bigr)^{-1}=O(m^{|X|/2}): the Bayes factor over EE costs P(E)−1=O(1)\mathbb{P}(E)^{-1}=O(1), since P(E)\mathbb{P}(E) is bounded below, and the denominator P(S(z)=0∣E)\mathbb{P}(S(z)=0\mid E) was just computed. Since mO(1)xm/8m^{O(1)}x^{m/8} is uniformly bounded in mm, their total contribution is O(1)≤O(M)O(1)\leq O(M). Thus the expectation in (6) is O(M)O(M) in the conditional measure too, with larger constants; here m=M−2k≤Mm=M-2k\leq M, and the strip and the full-input sweep are already covered by (6). □\square

Higher class: recursion and completeness

Peels are exchanges

3.1. Peels are exchanges. A peel is a triple of cut points 0≤i≤j≤k≤M0\leq i\leq j\leq k\leq M: it splits w=ABCDw=ABCD into four blocks and keeps the reduced word

z=red⁡(ACBD)(7)z=\operatorname{red}(ACBD) \tag*{(7)}

as the residual. There are (M+33)=Θ(M3)\binom{M+3}{3} = \Theta(M^3) triples, one nested loop fewer than the four cut points of (2) require; the range is the whole one, degenerate triples with an empty block included, and the exact peel of Theorem 3.6 is among them.

Proposition 3.1 (a peel removes one commutator). With u=ABA−1u = ABA^{-1}, v=ACA−1v = ACA^{-1},

w=[u,v]z,z=red⁡(ACBD),(8)w = [u,v]z,\qquad z = \operatorname{red}(ACBD), \tag*{(8)}

so cl⁡(w)≤cl⁡(z)+1\operatorname{cl}(w) \le\operatorname{cl}(z) + 1. Free reduction never lengthens a word, so ∣z∣≤∣w∣|z| \le|w|, with strict inequality as soon as one of the junctions A∣CA|C, C∣BC|B, B∣DB|D cancels.

Proof. Multiplying out and cancelling gives, in the free group,

[u,v]ACBD=ABCB−1C−1CBD=ABCD=w;[u,v]ACBD = ABCB^{-1}C^{-1}CBD = ABCD = w;

these equalities survive reduction.

For the length bound, before reduction ACBDACBD has the length of ww; reduction never increases it, and a cancelling junction makes it strictly smaller (a cascade may delete more than two letters). This proves the proposition. □

Exact peels and completeness

Proposition 3.1 gives only cl⁡(w)≤cl⁡(z)+1\operatorname{cl}(w) \le\operatorname{cl}(z) + 1, while the recursion needs a peel that lowers the class by exactly one at every node.

The proof runs in four steps, one per lemma below: pairings give the orbit count that computes cl⁡\operatorname{cl} (Proposition 3.2); a peel left-multiplies by a 3-cycle (Lemma 3.3); the gain is two exactly for one cyclic order of its entries (Lemma 3.4); a descent count produces such entries (Lemma 3.5).

Proposition 3.2 (the cycle-count formula, after Culler and Bardakov). Let w=w0⋯wM−1≠1w = w_0 \cdots w_{M-1} \ne1 be reduced with w∈[F,F]w \in[F,F] and M=2n≥2M = 2n \ge2, let ρ=(0 1 ⋯ M−1)\rho= (0\ 1\ \cdots\ M-1). Call a fixed-point-free involution π\pi of {0,…,M−1}\{0,\ldots,M-1\} with wπ(p)=wp−1w_{\pi(p)} = w_p^{-1} a pairing. Then

cl⁡(w)=12(n+1−max⁡πc(ρπ)),\operatorname{cl}(w) = \frac{1}{2}\left(n+1-\max_{\pi} c(\rho\pi)\right),

the maximum over all pairings, where cc counts orbits.

Proof. Pairings exist because the abelianisation of ww vanishes. Place one dart for each letter of ww around a single vertex, in the order ρ\rho, and glue them in pairs as π\pi prescribes. The resulting map has one vertex and nn edges. Walking a face alternates crossing an edge, which is π\pi, with turning to the next dart, which is ρ\rho; so the faces are the orbits of ρπ\rho\pi and F=c(ρπ)F = c(\rho\pi). Euler’s formula V−E+F=2−2γV-E+F = 2-2\gamma with V=1V=1 and E=nE=n gives γ=12(n+1−c(ρπ))\gamma= \frac{1}{2}(n+1-c(\rho\pi)), and Culler’s theorem, in the permutation form given by Bardakov [1], identifies cl⁡(w)\operatorname{cl}(w) with the least genus of such a map. Minimising the genus means maximising c(ρπ)c(\rho\pi). □

Let π\pi be an optimal pairing, one maximising c(ρπ)c(\rho\pi), and put

σ:=ρπ,κ:=cl⁡(w),c0:=c(σ)=n+1−2κ.\sigma:= \rho\pi,\qquad\kappa:= \operatorname{cl}(w),\qquad c_0 := c(\sigma) = n+1-2\kappa.

Since cl⁡\operatorname{cl} is a conjugacy invariant we may take ww cyclically reduced: if w=uw′u−1w = u w' u^{-1} and w′=A′B′C′D′w' = A'B'C'D' has cl⁡(A′C′B′D′)=κ−1\operatorname{cl}(A'C'B'D') = \kappa- 1, then A=uA′A = uA', B=B′B = B', C=C′C = C', D=D′u−1D = D'u^{-1} give ACBD=u(A′C′B′D′)u−1ACBD = u(A'C'B'D')u^{-1}, of the same class. A pairing pairs inverse letters, so cyclically reducedness restricts π\pi twice: π(p)=p+1\pi(p) = p + 1 would force wp+1=wp−1w_{p+1} = w_p^{-1} at adjacent positions, and π(0)=M−1\pi(0) = M - 1 would force wM−1=w0−1w_{M-1} = w_0^{-1} across the cyclic seam; both are forbidden. Hence every pair {p,q}\{p,q\} with p<qp < q has q≥p+2q \ge p + 2 and {p,q}≠{0,M−1}\{p,q\} \ne\{0,M - 1\}, and since σ(p)=π(p)+1(modM)\sigma(p) = \pi(p) + 1 \pmod M, the permutation σ\sigma has no fixed point.

Lemma 3.3 (a peel multiplies by a 3-cycle). Let w=ABCDw = ABCD with cut points $0 \le i < j < k \le M - 1$, let z0=ACBDz_0 = ACBD, and let π\pi be a pairing of ww. Transporting π\pi along the block move ϕ:ABCD↦ACBD\phi: ABCD \mapsto ACBD gives a map on z0z_0 whose face permutation has the orbit count of ρ~π\widetilde{\rho}\pi, where ρ~:=ϕ−1ρϕ\widetilde{\rho} := \phi^{-1}\rho\phi. Moreover

ρ~π=δσ,δ:=ρ~ρ−1=(i j k).\widetilde{\rho}\pi= \delta\sigma,\qquad\delta:= \widetilde{\rho}\rho^{-1} = (i\ j\ k).

Proof. The block move is the permutation

ϕ(p)=p(p∈A∪D),\phi(p) = p \qquad(p \in A \cup D),
ϕ(p)=i+(p−j)(p∈C),\phi(p) = i + (p - j) \qquad(p \in C),
ϕ(p)=p+(k−j)(p∈B),\phi(p) = p + (k - j) \qquad(p \in B),

which is order preserving inside each block. Hence ρ~(p)=ϕ−1(ϕ(p)+1)\widetilde{\rho}(p) = \phi^{-1}(\phi(p) + 1) equals p+1(modM)p + 1 \pmod M except where the successor in z0=ACBDz_0 = ACBD leaves a block. Reading the three junctions off the new boundary gives (indices in the first column modulo MM, so p=i−1p = i - 1 is M−1M - 1 when i=0i = 0)

pplast dart ofρ~(p)\widetilde{\rho}(p)
i−1i - 1AA (or DD if i=0i = 0)jj
j−1j - 1BBkk
k−1k - 1CCii

Table 1.

For i>0i > 0 the last dart of DD still goes to 00, as under ρ\rho; for i=0i = 0 it is the i−1i - 1 row of the table and goes to jj. Since ρ−1(q)=q−1\rho^{-1}(q) = q - 1, evaluating δ(q)=ρ~(q−1)\delta(q) = \widetilde{\rho}(q - 1) gives

qqiijjkk
q−1q - 1i−1i - 1j−1j - 1k−1k - 1
δ(q)\delta(q)jjkkii

Table 2.

and δ(q)=q\delta(q) = q elsewhere, so δ=(i j k)\delta= (i\ j\ k). For a concrete check, M=10M = 10, (i,j,k)=(2,5,7)(i,j,k) = (2,5,7) has ρ~(1)=5\widetilde{\rho}(1) = 5, ρ~(4)=7\widetilde{\rho}(4) = 7, ρ~(6)=2\widetilde{\rho}(6) = 2 and ρ~(p)=p+1\widetilde{\rho}(p) = p + 1 otherwise, hence δ(2)=5\delta(2) = 5, δ(5)=7\delta(5) = 7, δ(7)=2\delta(7) = 2. Finally ρ~π=(ρ~ρ−1)(ρπ)=δσ\widetilde{\rho}\pi= (\widetilde{\rho}\rho^{-1})(\rho\pi) = \delta\sigma.

The transport is a conjugation: ϕ\phi carries the letter at pp to position ϕ(p)\phi(p), so ϕπϕ−1\phi\pi\phi^{-1} pairs two positions of z0z_0 carrying inverse letters, that is, it is again a pairing. Its face permutation is conjugate to ρ~π\widetilde{\rho}\pi, so the two have the same orbit count.

Reading the darts around the single vertex in cyclic order gives the word z0=ACBDz_0 = ACBD (equivalently, the dual one-face map has boundary z0z_0), which need not be reduced; it spells the element red⁡(z0)\operatorname{red}(z_0), and Culler’s theorem bounds cl⁡(red⁡(z0))\operatorname{cl}(\operatorname{red}(z_0)) by the genus of the map — it refers to the element, not to the spelling — so nothing asks z0z_0 to be reduced. □

Lemma 3.4 (when a 3-cycle adds two orbits). Let τ=(a b c)\tau=(a\ b\ c) and let σ\sigma be any permutation. Then c(τσ)−c(σ)=2c(\tau\sigma)-c(\sigma)=2 if a,b,ca,b,c lie on one σ\sigma-orbit in the cyclic order a→c→b→aa\to c\to b\to a, and c(τσ)≤c(σ)c(\tau\sigma)\le c(\sigma) otherwise.

Proof. Write τ=(a c)(a b)\tau=(a\ c)(a\ b), the right factor acting first. For a transposition t=(x y)t=(x\ y) we have c(tσ)=c(σ)+1c(t\sigma)=c(\sigma)+1 if xx and yy lie on one orbit of σ\sigma, and c(σ)−1c(\sigma)-1 if they lie on two. Set t1=(a b)t_1=(a\ b) and t2=(a c)t_2=(a\ c); we apply these two rules in turn.

If a,ba,b lie on distinct orbits, t1t_1 merges them (−1-1) and t2t_2 adds at most 11, so the net change is non-positive. Otherwise t1t_1 splits their orbit into the arc from aa to σ−1(b)\sigma^{-1}(b) and the arc from bb to σ−1(a)\sigma^{-1}(a), a gain of 1. If the cyclic order is a→⋯→c→⋯→b→⋯→aa\to\cdots\to c\to\cdots\to b\to\cdots\to a, then cc lies on the first arc and t2t_2 cuts again, giving 2. In the other order, or if cc lies on another orbit, aa and cc are on distinct orbits of t1σt_1\sigma and t2t_2 merges them, giving 0. □

Call (i,j,k)(i,j,k) with i<j<ki<j<k a 132-triple if its entries lie on one σ\sigma-orbit in the cyclic order i→k→j→ii\to k\to j\to i. With τ=δ=(i j k)\tau=\delta=(i\ j\ k), the two lemmas give

c(ρ~π)=c0+2⟺(i,j,k) is a 132-triple.(9)c(\tilde{\rho}\pi)=c_0+2 \Longleftrightarrow(i,j,k)\text{ is a 132-triple}. \tag*{(9)}

So an exact peel exists as soon as σ\sigma contains a 132-triple.

Lemma 3.5 (a 132-triple exists). Let π\pi be an optimal pairing of a cyclically reduced w∈[F,F]w\in[F,F] with cl⁡(w)=κ≥1\operatorname{cl}(w)=\kappa\ge1. Then σ=ρπ\sigma=\rho\pi has a 132-triple.

Proof. Descents. Put dp:=(σ(p)−p)mod⁡Md_p:=(\sigma(p)-p)\mathbin{\operatorname{mod}}M and, for an orbit CC, let DC:=#{p∈C:σ(p)<p}D_C:=\#\{p\in C:\sigma(p)<p\} be its number of descents. We claim

∑pdp=M(n+1),∑CDC=n+1,∑C(DC−1)=2κ≥2.\sum_p d_p=M(n+1),\qquad\sum_C D_C=n+1,\qquad\sum_C(D_C-1)=2\kappa\ge2.

Write each pair of π\pi as {p,q}\{p,q\} with p<qp<q. Since σ(p)=π(p)+1(modM)\sigma(p)=\pi(p)+1\pmod M and q≥p+2q\ge p+2,

dp=q+1−p,dq=M+p+1−q,d_p=q+1-p,\qquad d_q=M+p+1-q,

so dp+dq=M+2d_p+d_q=M+2, and the nn pairs give ∑pdp=n(M+2)=M(n+1)\sum_p d_p=n(M+2)=M(n+1) because M=2nM=2n. On an orbit CC the increments σ(p)−p\sigma(p)-p cancel, while dpd_p exceeds σ(p)−p\sigma(p)-p by MM exactly when σ(p)<p\sigma(p)<p; hence ∑p∈Cdp=MDC\sum_{p\in C}d_p=MD_C. Comparing the two expressions for ∑pdp\sum_p d_p gives ∑CDC=n+1\sum_C D_C=n+1. Each DC≥1D_C\ge1, because σ(p)>p\sigma(p)>p for all p∈Cp\in C fails at the largest element of CC. Since there are c0=n+1−2κc_0=n+1-2\kappa orbits, ∑C(DC−1)=(n+1)−c0=2κ≥2\sum_C(D_C-1)=(n+1)-c_0=2\kappa\ge2.

Reading a triple off an orbit. By the claim some orbit CC has DC≥2D_C\ge2; an orbit of two points has exactly one descent, so ∣C∣=L≥3|C|=L\ge3. Let pp be the least element of CC and write its σ\sigma-cycle as p=s0→s1→⋯→sL−1→pp=s_0\to s_1\to\cdots\to s_{L-1}\to p. Since pp is the least element and σ\sigma has no fixed point, σ(p)=s1>p\sigma(p)=s_1>p. The last step is a descent, since it returns to the least element, and it is not the only one, so the least index tt with st+1<sts_{t+1}<s_t satisfies 1≤t≤L−21\le t\le L-2. Then p=s0<s1<⋯<stp=s_0<s_1<\cdots<s_t. Put i:=pi:=p, j:=st+1j:=s_{t+1} and k:=stk:=s_t. Then i<j<ki<j<k, because st+1≠ps_{t+1} \ne p (the cycle meets pp only at its two ends), and the cycle read from ii reaches kk before jj, so (i,j,k)(i,j,k) is a 132-triple. □

Theorem 3.6 (exact peel). Every reduced w∈[F,F]w \in[F,F] with cl⁡(w)=κ≥1\operatorname{cl}(w)=\kappa\ge1 has cut points $0 \le i \le j \le k \le |w|$ whose residual (7) satisfies cl⁡(z)=κ−1\operatorname{cl}(z)=\kappa-1; the cut points may be taken with i<j<ki<j<k.

Proof. The cyclically reduced core. Write w=uw′u−1w=uw'u^{-1} with w′w' cyclically reduced (possibly u=1u=1), and let π′\pi' be an optimal pairing of w′w'; thus cl⁡(w′)=cl⁡(w)=κ\operatorname{cl}(w')=\operatorname{cl}(w)=\kappa and, for σ′=ρ′π′\sigma'=\rho'\pi', c(σ′)=n+1−2κc(\sigma')=n+1-2\kappa with n=∣w′∣/2n=|w'|/2. Lemma 3.5 applied to w′w' and π′\pi' gives a 132-triple (i′,j′,k′)(i',j',k'). Cut w′=A′B′C′D′w'=A'B'C'D' there and set z0′=A′C′B′D′z'_0=A'C'B'D'.

The genus drops by one. Lemma 3.3 and (9), now applied to w′w', give c(ρ′π′~)=c(σ′)+2c(\widetilde{\rho'\pi'})=c(\sigma')+2, so the one-vertex map obtained by transporting π′\pi' to z0′z'_0 has genus

γ=12(n+1−c(σ′)−2)=12(n+1−(n+1−2κ)−2)=κ−1.\gamma=\frac{1}{2}\left(n+1-c(\sigma')-2\right)=\frac{1}{2}\left(n+1-(n+1-2\kappa)-2\right)=\kappa-1.

and the map has boundary z0′z'_0 and genus γ\gamma. A pair ee−1ee^{-1} in the boundary is a spur: in this one-vertex map it bounds a monogon face, so deleting the edge lowers both the edge count nn and the face count c=c(ρ′π′~)c=c(\widetilde{\rho'\pi'}) by one, with V=1V=1 fixed. Hence 2γ=n+1−c2\gamma=n+1-c and the genus are unchanged. Repeating removes every spur; the boundary becomes red⁡(z0′)\operatorname{red}(z'_0) and the genus stays γ\gamma, so Proposition 3.2 gives cl⁡(red⁡(z0′))≤γ=κ−1\operatorname{cl}(\operatorname{red}(z'_0))\le\gamma=\kappa-1. Reduction preserves the class, so cl⁡(z0′)=cl⁡(red⁡(z0′))\operatorname{cl}(z'_0)=\operatorname{cl}(\operatorname{red}(z'_0)) — Culler’s theorem, as noted above, refers to the element, not the spelling.

Restoring the conjugation. Now put A=uA′A=uA', B=B′B=B', C=C′C=C', D=D′u−1D=D'u^{-1}, so w=ABCDw=ABCD, the cut points i=∣u∣+i′i=|u|+i', j=∣u∣+j′j=|u|+j', k=∣u∣+k′k=|u|+k' are positions of ww, and ACBD=uz0′u−1ACBD=uz'_0u^{-1}. For the residual z=red⁡(ACBD)z=\operatorname{red}(ACBD) of (7), reduction and conjugation preserve the class, so cl⁡(z)=cl⁡(z0′)≤κ−1\operatorname{cl}(z)=\operatorname{cl}(z'_0)\le\kappa-1.

The reverse inequality. Conversely, multiplying out as in Proposition 3.1,

wz0−1=ABCD⋅D−1B−1C−1A−1=A[B,C]A−1,wz_0^{-1}=ABCD\cdot D^{-1}B^{-1}C^{-1}A^{-1}=A[B,C]A^{-1},

so κ=cl⁡(w)≤1+cl⁡(z0)=1+cl⁡(z)\kappa=\operatorname{cl}(w)\le1+\operatorname{cl}(z_0)=1+\operatorname{cl}(z) and cl⁡(z)≥κ−1\operatorname{cl}(z)\ge\kappa-1. The two bounds agree. □

The algorithm never invokes the theorem: it enumerates the triples of (7) and recurses on the survivors, which is complete by Lemma 3.7.

Lemma 3.7 (completeness). Let r≠1r\ne1 be a reduced residual of even length and trivial abelianisation, held by a node with target rem⁡≥cl⁡(r)\operatorname{rem}\ge\operatorname{cl}(r). Then the subtree below that node contains a leaf: a node whose target is 11, or one whose residual is empty.

Proof. Induct on rem⁡\operatorname{rem}. For rem⁡=1\operatorname{rem}=1 the node is itself such a leaf: by Lemma 2.6 and Proposition 2.4 the base test decides cl⁡(r)=1\operatorname{cl}(r)=1 correctly. For rem⁡≥2\operatorname{rem}\ge2 Theorem 3.6 applies, because cl⁡(r)≥1\operatorname{cl}(r)\ge1, and gives a peel whose residual zz is reduced, even and of trivial abelianisation, a peel only permuting blocks. The filters reject only through (4), a lower bound for cl⁡(z)\operatorname{cl}(z), so this candidate survives. If cl⁡(r)=1\operatorname{cl}(r)=1 then z=1z=1 and the child is a leaf with empty residual; otherwise cl⁡(z)=cl⁡(r)−1≥1\operatorname{cl}(z)=\operatorname{cl}(r)-1\ge1, so z≠1z\ne1 and, as rem⁡−1≥cl⁡(z)\operatorname{rem}-1\ge\operatorname{cl}(z), induction applies to the child. □\square

The filter stack

A candidate is screened by a single pass over zz. The count (3) is read on the cyclically reduced core of z=red⁡(ACBD)z=\operatorname{red}(ACBD), so it is independent of the chosen anchor; it is computed afresh from zz itself, never carried over from the parent, and a cancellation at a junction cannot corrupt it. The pass strips the longest mirror-inverse prefix, the largest xx with z=xz′x−1z=xz'x^{-1} (the smax⁡s_{\max} of § 2), leaving a cyclically reduced core z′z', counts the cyclic blocks of the core and forms the differences bU−bU−1b_U-b_{U-1}, in O(∣z∣)O(|z|) time and space, the order of producing zz from the four blocks of the parent. The candidate is rejected as soon as DH⁡(z)≥12(rem⁡−1)−5\operatorname{DH}(z)\ge12(\operatorname{rem}-1)-5: by (4) this forces cl⁡(z)≥rem⁡−1+112\operatorname{cl}(z)\ge\operatorname{rem}-1+\frac{1}{12}, hence cl⁡(z)≥rem⁡\operatorname{cl}(z)\ge\operatorname{rem}, one more than the child’s target, and the rejection rests on (4) alone.

So a candidate costs O(M)O(M) and the filters do not enter the exponent of Theorem 3.8, only the constant; their role is practical, discarding a child whose class provably exceeds the target before any recursion starts.

The cost of the recursion

The recursion. A node holds a reduced residual rr of even length and a target rem⁡\operatorname{rem}. If rem⁡=1\operatorname{rem}=1 it runs the base test of § 2; otherwise it tries every triple 0≤i≤j≤k≤∣r∣0\le i\le j\le k\le|r| of (7), filters the candidates, and recurses on the survivors with target rem⁡−1\operatorname{rem}-1; an empty residual ends its branch.

Theorem 3.8 (higher-class worst case). For a word of length MM and a target g≥2g\ge2, the search runs in O(M3g)O(M^{3g}) steps in the unit-cost model, in O(M2)O(M^2) space.

Proof. Correctness. For w=1w=1 the answer is the empty decomposition, so assume w≠1w\ne1. The filters never discard a residual whose class is within its target: they reject only through (4). Hence Lemma 3.7 applies at every node that is reached, and the search returns a decomposition into at most gg commutators whenever g≥cl⁡(w)g\ge\operatorname{cl}(w). For g<cl⁡(w)g<\operatorname{cl}(w) it reports cl⁡(w)>g\operatorname{cl}(w)>g, which is correct: a leaf at depth at most g−1g-1 would have exhibited ww as a product of at most gg commutators. Every returned answer is a product of commutators equal to ww: at an internal node by (8), at a base node once the stripped conjugation r=xzx−1r=xzx^{-1} is put back.

The time bound. Let md≤Mm_d\le M bound the residual length at depth dd. A node with target at least 2 enumerates (m+33)≤(m+1)3\binom{m+3}{3}\le(m+1)^3 triples and spends f(m)=O(m)f(m)=O(m) on each, so such a node costs O(m4)O(m^4); a node with target 1 runs the base test, at Cm3Cm^3 by Proposition 2.5. The target, not the length, drops by one per level, so a node at depth dd has target g−dg-d and the tree has depth at most g−1g-1; with N0=1N_0=1 and Nd+1≤Nd(md+1)3N_{d+1}\le N_d(m_d+1)^3 this gives Nd≤(M+1)3dN_d\le(M+1)^{3d}, and md≤Mm_d\le M. Hence

T≤∑d=0g−2Ndmd3f(md)+Ng−1Cmg−13≤f(M)∑d=0g−2(M+1)3d+3+C(M+1)3g=O(M3g),\begin{aligned} T\le\sum_{d=0}^{g-2}N_dm_d^3f(m_d)+N_{g-1}Cm_{g-1}^3 \\ &\le f(M) \sum_{d=0}^{g-2} (M+1)^{3d+3} + C(M+1)^{3g} \\ &= O(M^{3g}), \end{aligned}

when f(M)=O(M)f(M)=O(M). Here md3f(md)=O(md4)m_d^3 f(m_d)=O(m_d^4) is the per-node cost: md3m_d^3 triples at f(md)=O(md)f(m_d)=O(m_d) each. The sum is dominated by its last term: the internal layers contribute O(M3g−2)O(M^{3g-2}) against the O(M3g)O(M^{3g}) of the base layer, so the factor mm spent on each candidate by the filter does not raise the exponent.

The space bound. The base test of Proposition 2.5 keeps the arc graph, which has ν≤M2\nu\le M^2 arcs, while a peel node keeps its residual and the candidate it is screening, O(M)O(M) letters: the enumeration is depth first, recursing on a survivor as soon as it passes the single-pass filter and resuming where it left off on return, so no list of survivors is stored. The stack of residuals holds O(M)O(M) letters per level and the depth is at most min⁡(g,cl⁡(w))≤M\min(g,\operatorname{cl}(w)) \le M, so it is O(M2)O(M^2) as well, and the total is O(M2)O(M^2). □

Nor can two cut points suffice. A two-cut peel has three blocks and exchanges the last two, so a two-cut search enumerates Θ(M2)\Theta(M^2) such exchanges per level and would give O(M2(g−1)+3)=O(M2g+1)O(M^{2(g-1)+3})=O(M^{2g+1}). Ten letters defeat it. The word

w=w0⋯w9=aba−1cb−1dc−1ed−1e−1=[aba−1,ca−1][cdc−1,ec−1](10)w=w_0\cdots w_9=ab a^{-1}c b^{-1}d c^{-1}e d^{-1}e^{-1}=[ab a^{-1},c a^{-1}][cd c^{-1},e c^{-1}] \tag*{(10)}

is cyclically reduced of length 10 and a product of two commutators, but has no arc, so cl⁡(w)=2\operatorname{cl}(w)=2 by Proposition 2.4. Its five inverse pairs sit at 0↔20\leftrightarrow2, 1↔41\leftrightarrow4, 3↔63\leftrightarrow6, 5↔85\leftrightarrow8, 7↔97\leftrightarrow9. A two-cut exchange ABC↦ACBABC\mapsto ACB changes only three adjacencies; checking the 36 nondegenerate cuts shows that every child has arcs only of length at most 1. Here a child is the residual red⁡(ACB)\operatorname{red}(ACB) of (7); reducing it to its cyclically reduced core costs at most one inverse pair, so that core still has length at least 8. Yet a cc-word of length at least 8 has arcs whose lengths sum to half ≥4\ge4, hence one of length at least 2. So no child is a cc-word, no child has class 1, and a two-cut search never reaches a leaf. The exponent is 3g3g, not 2g+12g+1.

References

  1. [1]V. G. Bardakov, Computing commutator length in free groups, Algebra and Logic 39, No. 4 (2000), 224–251.DOI
  2. [2]L. Bartholdi, D. Fialkowski, S. O. Ivanov, On commutator length in free groups, Groups Geom. D., 18 (2024), 191–202.
  3. [3]M. Culler, Using surfaces to solve equations in free groups, Topology 20 (1981), 133–145.DOI
  4. [4]G. Manacher, A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach. 22 (1975), 346–351.DOI
  5. [5]M. J. Wicks, Commutators in free products, J. London Math. Soc. 37 (1962), 433–444.DOI

Paper details

vlnc:W_egnbetxh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents