A group without fixed price

Proof. Choose, in each factor, representatives for the cosets gJ, with 1 representing J. Consider formal strings

where the r_i are nonidentity representatives, alternately from the two factors; the case n=0 is allowed. Define right multiplication by g in one factor as follows. If the last representative is from that factor, combine it with the final j and g, and write their product uniquely as rj' in that factor. Otherwise write jg=rj' and append r. Omit r when r=1.

This gives a right action of each factor on the strings. To check the action law for two successive multipliers in the same factor, retain the prefix ending in the other factor and simply multiply the remaining suffix in the chosen factor. This description continues to apply when the suffix representative becomes 1. The two actions agree for multipliers in J, which only multiply the final J-entry. They therefore define an action of the amalgam on the strings.

Acting on the identity string by a factor element recovers its coset decomposition, so the factors embed. Their possible strings intersect exactly in the strings with no representatives, proving A\cap B=J. Successively multiplying by an alternating sequence outside J adds one nonidentity representative at every step: for j\in J and g\notin J, one has jg\notin J. The resulting string has length n, whereas elements of J have length zero and factor elements have length at most one. This proves the stated normal-form assertions.

For J, expand any reduced nonempty word in the abstract generators b_1,\ldots,b_{99},w in the free basis of A. The word w=ab_1ab_2\cdots ab_{99}a starts and ends with a; w^{-1} starts and ends with a^{-1}. No boundary between a b_i^{\pm1} and w^{\pm1} cancels. Two successive w-symbols either have equal signs, in which case their boundary does not cancel, or would be inverse symbols, which reducedness excludes. Boundaries between b-symbols do not cancel either. Thus the expansion is a nonempty reduced word in A, proving that the displayed generators of J are a free basis.

Finally, the displayed generators of \Gamma generate both factors; the embedded copy of A makes \Gamma infinite, and finite generation makes it countable. The embedded copy of B also shows that t has infinite order in \Gamma.□

Proof. The exponent sum of a defines a homomorphism \chi_A:A\to\mathbb Z. Define \chi_B(jt^n)=\chi_A(j) on B=J\times\langle t\rangle. This is a homomorphism and agrees with \chi_A on J, so the amalgam’s universal property gives \chi. The formulas for u_i and w follow by their definitions. In particular, the restriction of \chi to J need not be zero: it sends w to 100. The homomorphism law verifies the right-action law in (3). Both coordinate actions preserve their measures. Freeness follows from freeness on the first coordinate, and the finite product remains standard Borel.□

Proof. In X, put

The set N_p is Borel, invariant under t, and null: the coordinates x(t^n) are independent, and the group elements t^n are distinct. Indeed, the probability that the condition holds for 0\leq n<N is (1-p)^N. Thus \nu_M(C_p)=p. If a t-orbit does not meet the first part of C_p, all its points belong to N_p\times\mathbb Z/M\mathbb Z. Hence C_p meets every t-orbit, including the exceptional ones.

Let j be one of b_1,\ldots,b_{99},w, and let z\in Y_M. Choose n\in\mathbb Z with zt^n\in C_p. The graphing contains the path

where the first and last portions use t or t^{-1}. The final identity uses jt=tj in B. Thus every generator of B is available everywhere in the generated relation. Conversely, all the graphing’s maps are restrictions of elements of B. Each of the 100 restricted generators costs p, and the full t-map costs one.□

Proof. Fix 0<p<1 and use the graphing of Lemma 2.3. Add the restriction of a to the union of the height fibers 0,1,\ldots,98. Its domain has measure 99/M, so the resulting graphing has cost

Let E be the equivalence relation it generates. It contains \mathcal R_B, and we will prove that it contains every a-edge.

Suppose that (z,za)\in E whenever the height of z is one of k,k+1,\ldots,k+98, interpreted modulo M. Given z at height k+99, set y=zu_{99}^{-1}, which has height k. The sequence

is connected by E: at its ith step apply a to yu_{i-1}, of height k+i-1, and then apply b_i. The a-edge is among those assumed available, and the b_i-edge belongs to \mathcal R_B. The w-edge also belongs to \mathcal R_B, and

Thus z and za are E-equivalent, proving the implication from 99 consecutive known source heights to the next one.

The heights 0,\ldots,98 are known initially. Apply this implication for the ordinary integers k=0,1,\ldots,M-100. It successively supplies source heights 99,100,\ldots,M-1; the last a-edges end at height 0 modulo M, as required. Hence all a-edges lie in E. Since B and a generate \Gamma, this graphing generates \mathcal R_\Gamma. Taking the infimum over graphings and then letting p\downarrow0 proves the bound.□

Proof. On the part W_k consisting of classes of size k, order each class into k Borel sheets. The map from B\cap W_k to any one sheet that stays within each class is a Borel partial isomorphism inside \mathcal R, so all k sheets have measure \lambda(B\cap W_k). Thus \lambda(W_k)=k\lambda(B\cap W_k). Summing over k proves the identity.□

Proof. On the union Z_{\mathrm{fin}} of finite \mathcal T-classes, choose the least point of each class. The resulting Borel set M_{\mathrm{fin}} has measure \kappa(\mathcal T) by Lemma 3.1.

On Z_{\mathrm{inf}}=Z\setminus Z_{\mathrm{fin}}, choose increasing finite Borel partitions \mathcal P_n that separate all points, for example those generated by the first n members of a countable separating Borel family. Let k_n(z) be the number of atoms of \mathcal P_n meeting [z]_{\mathcal T}. This function is Borel, and k_n(z)\longrightarrow\infty: any prescribed finite collection of distinct points in the infinite class is separated by some partition.

Fix 0<p<1 with p\lambda(Z_{\mathrm{inf}})<\varepsilon/2. At a fixed level n, mark each atom independently with probability p, and let A be the union of the marked atoms. The Borel set

meets every infinite \mathcal T-class for every marking. The displayed union is disjoint, and

The integral tends to zero by dominated convergence. For sufficiently large n the expectation is less than \varepsilon, so one of the finitely many markings has measure less than \varepsilon. Fix that marking and set M=M_{\mathrm{fin}}\cup M_{\mathrm{inf}}.□

Proof. Choose a Borel \mathcal T-complete set M from Lemma 3.2, and put

This set is Borel and \mathcal S-invariant. It is \mathcal T-complete and hence \mathcal Q-complete, since it contains M. Every \mathcal S-class outside Y is finite. In each finite \mathcal S-class in Y, choose a point of its intersection with M. Lemma 3.1 gives

Choosing and deleting one edge per class outside Y. Let d(z) be the least number of edges from \mathcal E, in either direction, needed to reach Y, allowing \mathcal S-steps for free. This distance is finite because Y is \mathcal Q-complete. Its sublevel sets are Borel: starting with Y, successively take images under the maps of \mathcal E and their inverses, and take \mathcal S-saturations. It is constant on \mathcal S-classes and vanishes precisely on Y.

For every \mathcal S-class K outside Y, choose an oriented edge instance from y_K\in K to y'_K with d(y'_K)=d(K)-1. Such an instance exists by a shortest path. To make the choice Borel, first choose the least eligible pair consisting of a map index and a direction, then choose the least eligible point in the finite class K. Eligibility of a map index and direction is detected by the \mathcal S-saturation of a Borel set. Thus all these choices are Borel. The set V=\{y_K\} is a Borel transversal of \mathcal S on Z\setminus Y, so

For each original map \varphi_i:D_i\to E_i, let V_i^+ be the chosen origins whose edge is traversed forward under \varphi_i, and let V_i^- be those whose edge is traversed under \varphi_i^{-1}. Delete the domain set

from D_i. The union is disjoint: a labeled edge instance chosen in both directions would make each endpoint class have smaller distance than the other. The sets V_i^+,V_i^- partition V, and inverse images under \varphi_i preserve measure. Consequently the residual family \mathcal E'=(\varphi_i|_{D_i\setminus H_i}) satisfies the exact identity

Different original indices count as different edge instances, even when their geometric edges coincide. Thus this accounting also covers graphings with repetitions.

Moving the remaining edges into Y. Define f:Z\to Y by f(x)=x for x\in Y, and, for x in an \mathcal S-class K outside Y, by

The recursion decreases the integer distance at every step. Defining f successively on the distance levels proves it is Borel. Each (x,f(x)) lies in \mathcal Q. Because Y is \mathcal S-invariant, f fixes each class inside Y pointwise and is constant on each class outside Y. It therefore sends \mathcal S-steps to \mathcal S-steps. Each deleted edge has equal images at its two endpoints.

The map f can be many-to-one. To obtain partial isomorphisms after moving the remaining edges, we must split their domains at both endpoints. Fix a residual edge map \varphi_i with domain D'_i. Partition D'_i into Borel pieces P_{i,r,s} according to the least indices r,s for which

These indices exist because the graph of f is contained in \mathcal Q\subseteq\mathcal R. On this piece the pushed edge is the partial isomorphism

Its domain and range are Borel, it preserves measure, and its graph is contained in \mathcal Q|Y. Its cost equals \lambda(P_{i,r,s}). Let \mathcal F consist of all these maps. Although the images of distinct pieces may overlap, graphing cost is the sum over the indexed family, and the original pieces partition each D'_i. Hence

One may discard identity maps or redundant instances, in which case the equality becomes an inequality in the needed direction.

Recovering the relation. For two \mathcal Q-related points in Y, take a finite path with steps in \mathcal S and \mathcal E and apply f to its vertices. The endpoints remain fixed. Each \mathcal S-step remains such a step, each deleted edge becomes stationary, and each surviving edge becomes an edge of \mathcal F. Therefore

For arbitrary x\mathrel{\mathcal Q}x', choose y\in[x]_{\mathcal T}\cap Y and y'\in[x']_{\mathcal T}\cap Y using completeness of Y. Then y\mathrel{\mathcal Q}y', so the preceding identity joins them using \mathcal S\subseteq\mathcal T and \mathcal F. Together with the first and last \mathcal T-steps this proves \mathcal Q=\mathcal T\vee\mathcal F.

Finally, by (5), (7), and (8),

This is (4).□

Proof. Let \mathcal E be a finite-cost generating graphing of the relation \mathcal Q. Apply Lemma 3.3 with \mathcal S=\mathrm{id} and \mathcal T=\mathcal Q. Since \kappa(\mathcal S)=1 and \kappa(\mathcal Q)=0, it gives 0\le C(\mathcal F)\le C(\mathcal E)-1+\varepsilon for every \varepsilon>0. Thus C(\mathcal E)\ge1. Infinite-cost graphings satisfy this bound as well; taking the infimum proves the assertion.□

Proof. We use right actions, so that (xg)(h)=x(gh). Choose representatives h_c for the cosets Ah_c in \Gamma, and let \Omega=[0,1]^{A\backslash\Gamma} with its product probability measure. The coordinate rearrangement

identifies the restriction of X_0 to A with \Omega^A, with independent base coordinates and right action (\xi q)(g)=\xi(qg). We write \mu for the product measure on this space. All graphing identities are considered on invariant conull subsets, so the restriction to X does not change the argument.

For every finite exact A-set V, define \theta:V\times A\to D_V on the free basis of A by

for each basis letter s. Extend by multiplying these values along a word. Cancellation of adjacent inverse letters cancels their two values at the corresponding sources. Since A is free, this gives a well-defined function satisfying

The word w=u_{99}a=ab_1ab_2\cdots ab_{99}a gives

Also \theta(v,b_i)=1 at every source. The inverse rule and (17) therefore give

Notice that \theta(v,g) depends on the group label g, not merely on the pair of endpoints (v,vg).

Fix a finite-cost graphing \mathcal E such that \mathcal R_J\vee\mathcal E=\mathcal R_A, and fix \epsilon>0. Such finite-cost graphings suffice for the infimum defining \delta_X: the full a-translation, together with \mathcal R_J, already generates \mathcal R_A. On an invariant conull free set, split each map in \mathcal E according to its unique displacement in A. This produces countably many restrictions

with \sum_\ell\mu(L_\ell)=C(\mathcal E).

A path type is a finite list of full J-translations and signed indices \ell of these paid maps. Its label is the product in A of its successive step labels. Almost every x has a valid path to xa. Freeness implies that every such path has label exactly a in A. There are countably many path types. Choose finitely many, each with label a, whose validity sets cover a set of measure at least 1-\epsilon. Let I be their finite set of paid indices, and let m_\ell count all occurrences of index \ell among these types.

Choose cylinder-measurable sets L'_\ell, depending on finitely many A-coordinates, such that

This approximation is available because finite-coordinate measurable sets form an algebra generating the product sigma-algebra. Its closure for the metric \mu(E\mathbin{\triangle}F) is a sigma-algebra, so every measurable set is approximable in this metric.

For clarity, a forward step of index \ell after a prefix with label h tests xh\in L_\ell. An inverse step after that prefix tests xhg_\ell^{-1}\in L_\ell. Replace these tests by the corresponding tests in L'_\ell, keeping all path labels unchanged. Each occurrence changes its validity predicate on a set of measure at most \mu(L_\ell\mathbin{\triangle}L'_\ell), by invariance of \mu. If P' is the union of the modified path validity sets, then

All sets L'_\ell and P' depend on a single finite coordinate set F\subset A: for example, a test of an F_\ell-cylinder after prefix h uses coordinates hF_\ell, or hg_\ell^{-1}F_\ell for an inverse step. This finite set is fixed before k tends to infinity.

We have reduced generation to finitely many cylinder tests. We now evaluate these same tests on V_k. For independent base labels (z_v)_{v\in V_k} with law \Omega, put

Exactness of the action gives \xi_{vq}=\xi_vq. If vg\ne vh for all distinct g,h\in F, the F-coordinates of \xi_v have exactly the product distribution. The fraction of exceptional sources is at most

which tends to zero by (16). Consequently, for every measurable F-cylinder E,

This uses no independence between different sources v.

For any realization of the labels, make a list containing \theta(v,g_\ell) for every \ell\in I and every v with \xi_v\in L'_\ell. If \xi_v\in P', follow a modified valid path from v. A forward paid factor occurs on this list. For an inverse paid step after prefix h, the factor is

and its inverse-domain test puts \theta(vhg_\ell^{-1},g_\ell) on the list. Each J-step contributes 1 by (18). Since the path label is exactly a, (17) expresses x_v=\theta(v,a) as a product from this list and its inverses. The finite configuration \xi_v need not be free; freeness was used only to select the original path labels.

Add x_v for every source with \xi_v\notin P'. The resulting list generates D_{V_k}, so for every labeling,

Taking expectations, using (20), and then letting k\to\infty gives

Let \epsilon tend to zero and then take the infimum over \mathcal E. All finite path and cylinder tests were fixed before taking the limit in k.□

Proof. First, a,u_1,\ldots,u_{99} is a free basis of A. Indeed, the substitutions defining u_i have the inverse substitutions

Between abstract free groups on the two proposed bases, these formulas give inverse homomorphisms: they recover b_i directly and recover u_i by induction. Assign independent uniform permutations of \{1,\ldots,n\} to the 100 elements of this basis. This defines an exact right A-action.

Fix an integer s with 1\le s\le\lfloor\alpha n\rfloor. If a set T of size s violates (21), then N(T) is contained in a set C of size 96s containing T, since u_0=1. Such a set exists because 96s<n. For fixed T there are \binom{n-s}{95s} possible sets C. For one uniform permutation \sigma, the probability that T\sigma\subseteq C is

Using independence of the 99 permutations assigned to u_1,\ldots,u_{99}, followed by the bounds \binom nr\le(en/r)^r, gives

The exponent is 99-1-95=3. Set q=K\alpha^3<1/2. For every fixed integer R\ge1, the sum of these bounds over all allowed sizes is at most

First let n\to\infty and then R\to\infty. Thus (21) holds with probability tending to one. This includes s=1; if \lfloor\alpha n\rfloor=0, the assertion is vacuous.

We also need (16). Fix a nonempty freely reduced word of length L in the random basis, and a starting vertex v_0. Follow the word, exposing permutation entries only when needed. Until the first repeated vertex, the current vertex has not occurred earlier except as the endpoint of its incoming edge. A positive next letter could request an already exposed domain entry only by immediately inverting that incoming edge. A negative next letter could request an already exposed range entry only in the same way. Both are excluded by free reduction. At step t, therefore, the requested partner is uniform among at least n-t+1 available vertices. At most t of these vertices have already been visited. For n\ge L,

The same bound holds for the expected fixed-point fraction. It tends to zero for each fixed nonidentity element of A.

Here is an explicit simultaneous choice. Enumerate the nonidentity elements of A as g_1,g_2,\ldots. At stage k, take n_k>n_{k-1} so large that expansion fails with probability at most 1/4, and

Markov’s inequality and a union bound show that the probability that some j\le k has fixed-point fraction greater than 1/k is at most 1/4. Choose an outcome with expansion and all these fixed-point bounds. This gives (16) for every fixed element, without requiring estimates uniform over words of increasing length.

Finally we deduce (22). A repeated column in row v gives vu_i=vu_j for some i\ne j, so v is fixed by the nonidentity word u_i u_j^{-1}. If two distinct columns are shared between rows v\ne y, choose indices with

Then i\ne j and k\ne l by distinctness of the columns, while i\ne k and j\ne l follow from injectivity of each permutation. Consequently v is fixed by

This word is nontrivial. In the cyclic order (i,k,l,j), neighboring indices differ. If all indices are nonzero, the displayed word is freely reduced. Removing one occurrence of u_0=1 joins letters of the same sign and leaves a nonempty reduced word. Two zero indices can occur only in opposite positions; the remaining two letters then have the same sign. Three zero indices are impossible. Thus every possible overlap gives a fixed point of a nonidentity word from a finite list. The union of the fixed sets in this list, together with the finite list for repeated columns, contains every bad row. Equation (16) now gives b(V_k)=o(n_k).□

Proof. We first turn a least-relator expression for W into a planar graph. The edges of this graph pair exterior occurrences. Bigon faces give consecutive matches, and a corner count will produce either one full match or two long strings of bigons.

A finite filling over an arbitrary coefficient group. Choose an expression for W in L as a product of conjugates of words from \mathcal R^{\pm1} using the least possible number N of those words. Free-product reduction shows that a cyclically H-reduced word with an exterior occurrence is nontrivial in L, so N>0.

Give H the presentation on S with all words trivial in H as relations. An equality in this presentation uses finitely many relations: membership in their normal closure means a finite product of conjugates. Thus the chosen expression for W can be witnessed using a finite set of true H-relations. Let K_H be a finite presentation complex for this finite set of relations, and wedge it with one circle for each u\in U. The resulting complex K has a natural homomorphism \pi_1(K)\to L. We do not assume this homomorphism is injective.

Realize the expression by a map from a sphere with N+1 open disks removed to K. Denote the distinguished boundary disk by O, and the other disks by B_1,\ldots,B_N. Read every disk boundary using its disk orientation in the oriented sphere. The boundary of O reads W^{-1}, and each B_i reads one chosen relator or its inverse. To construct the map, cut the punctured sphere along disjoint spokes carrying the conjugating paths. Its remaining boundary reads the equality in L; the finitely many chosen H-relations and free cancellations fill this boundary. Conversely, cutting any such mapped punctured sphere along spokes expresses W as a product of N conjugates in L.

We may make the complex and map piecewise linear. For example, realize each relation with a mapping cylinder and a disk, triangulate, and use the finite filling just described. During later replacements we may enlarge the finite set of true H-relations: any loop trivial in L becomes fillable after adding the finitely many such relations used by its equality. Minimality throughout concerns N in the actual group L, not a possibly larger finitely presented approximation to it.

Tracks and connectedness. For every u\in U, choose a point q_u in the interior of its circle edge, avoiding the images of all vertices of a subdivision for the piecewise linear map. Near q_u the target is an interval. Its inverse image consists of line segments across triangles, joined in pairs across their sides. These form disjoint cooriented arcs and circles in the punctured sphere. Each exterior occurrence on a boundary is the endpoint of exactly one arc. Each arc and each circle maps constantly to its chosen point. The two endpoints of an arc have opposite crossing signs when read in the disk orientations. This follows from coorientation and the orientation of the surface; all disk-boundary orientations are opposite the corresponding orientations as boundaries of the punctured surface.

Regard the boundary disks as vertices and the arc tracks as edges of an embedded graph G on the sphere. Closed tracks are not edges of G; we retain them as part of the map. We claim that G is connected. If it were not, choose a component C not containing O and a small closed regular neighborhood of its disks and arc tracks. This neighborhood can be chosen disjoint from all other disks and tracks, including the finitely many closed tracks. Select the boundary curve \gamma facing the complementary component that contains O. The disk side of \gamma away from O contains C and at least one inner disk; it may also contain other components, which causes no problem.

The image of \gamma avoids every q_u. Cutting the exterior circles at these points leaves a space retracting to K_H. Consequently the class of \gamma, after a change of basepoint, is an element of H inside L. Cap all relator holes on the side away from O in a presentation space for D. The resulting mapped disk shows that this element is trivial in D. Injectivity of H\to D makes it trivial in H, hence \gamma is trivial in L. Replace that entire disk side by a filling using only true H-relations and free cancellations. At least one relator disk disappears, contradicting the choice of N. Thus G is connected. This argument neither removes individual closed tracks nor supposes that such tracks bound disks in the target.

Inner loops and dipoles. There is no graph loop at an inner vertex. All exterior letters on that disk have the same sign, whereas an arc pairs opposite signs. Nor can an edge join two copies of the same relator. Such copies would have opposite orientations and meet the unique occurrence of the same exterior generator u. Base their boundary loops at the point q_u on that occurrence. Writing the positive occurrence as u=ps, a positive based boundary has the form sTp, while the negative one is p^{-1}T^{-1}s^{-1}; these are inverse loops. The joining track is constant and inserts no conjugating coefficient. A small disk neighborhood of the two disks and this track therefore has null boundary in L. Replacing its interior removes both relator disks, again contradicting minimality. Other tracks crossing the boundary of this neighborhood impose no restriction on the replacement map.

For copies of different relators there is at most one joining edge: the relators share at most one exterior generator, used once on each disk. Thus between any two inner vertices there is at most one edge. Every inner vertex corresponding to r has degree exactly m(r).

Face equations and bigon matches. The complement of a small regular neighborhood of the connected disk-and-arc graph consists of disks. Their boundary curves follow the face walks of G, even when a walk repeats vertices or edges. Collapse the exterior circles of K to its basepoint and then take values in H. Each track becomes constant, and a sector between successive track endpoints on a disk contributes its coefficient gap. The map on each complementary disk proves that the ordered product of its sector values is 1 in H. Closed tracks inside that disk do not affect this argument.

There are no monogon faces. An inner loop has already been excluded; a monogon at O would pair two inverse exterior occurrences across a gap trivial in H, contrary to cyclic H-reduction. Any bigon incident to an inner vertex consists of two edges joining that vertex to O. Indeed, there are no parallel edges between inner vertices. A face walk of length two that traverses one edge twice would require degree one at its inner endpoint, which is impossible since m(r)\geq7.

Such an inner–outer bigon matches consecutive exterior letters and their intervening coefficient gap. The exterior signs match because O is labelled W^{-1} in its disk orientation. Following W along the outer sector follows the corresponding inner relator in its disk orientation. The face equation, with this convention, is the inner gap times the inverse of the outer gap equal to 1. It therefore gives equality of the two elements of H, rather than equality merely up to conjugacy.

We have now reduced the desired word matches to strings of bigons. The remaining argument forces either a full cyclic string or two long strings at different inner vertices.

The corner count. Give weight zero to every corner at O and to every corner of a bigon. For any other corner at an inner vertex, assign weight

Occurrences are counted with multiplicity along a face walk. A face of length \ell has total weight at most \ell-2. For a bigon this is equality. For \ell\geq3 with no occurrence of O, the total is \ell/3\leq\ell-2. With exactly one occurrence of O, the two neighboring corners have weight 1/2 and the remaining \ell-3 corners weight 1/3, again totaling \ell/3. With at least two occurrences of O, there are at most \ell-2 inner corners, each of weight at most one. These cases include repeated face walks and loops at O.

Write E and F for the numbers of edges and faces of G, and c(v) for the total corner weight at an inner vertex v. Summing over faces and using Euler’s formula for the connected sphere graph with N+1 vertices gives

Call 2-c(v) the contribution of v. A vertex of degree m\geq7 with no edge to O has c(v)=m/3>2, so a positive vertex has an edge to O. At such a vertex, consider the cyclic gaps between successive edges to O. A gap that bounds a bigon costs zero. A gap containing no edge to an inner vertex, but not bounding a bigon, costs one. A gap containing h\geq1 edges to inner vertices costs

Each gap not bounding a bigon therefore costs at least one.

If every gap bounds a bigon, all edges at v go to O. Successive edges at v are also successive at O, in the opposite rotation. They exhaust the cyclic rotation at O: otherwise a further half-edge would interrupt one of these bigons. Connectedness leaves no other vertex. The bigon equations then match every exterior occurrence of W with this relator, including all cyclic gaps. This is the first conclusion.

Otherwise positivity means that exactly one gap does not bound a bigon, and that gap contains at most three edges to inner vertices. Indeed, two such gaps cost at least two, while a gap containing h\geq4 inner edges also costs at least two. The other gaps form one consecutive string of bigons joining at least m-3 edges to O. Its bigon equations give a matching interval with at least m-3 exterior occurrences. The contribution of this vertex is at most one.

Unless the first conclusion has already occurred, every positive vertex contributes at most one. The total contribution is at least two, so there are at least two distinct positive vertices. Take a matching interval from each. Each exterior occurrence of W is the endpoint of exactly one arc track, so intervals arising from different inner vertices have disjoint exterior occurrences. This proves the second conclusion.□

Proof. Suppose instead that D has at most \alpha n/100 generators. We proceed in four steps: choose a minimal graph, saturate a small coefficient alphabet, locate a long relator segment, and shorten the graph.

A minimal labelled graph

Give each edge of a finite graph an orientation and a label x_v or x_v^{-1}; reading the edge backwards inverts its label. Path labels are words in these letters, evaluated in D. A generating set written as words in the x_v gives a subdivided rose whose based loops map onto D. Among all finite connected labelled graphs Y with

and surjective loop-label map to D, choose one with the fewest edges. Write \beta=\beta(Y). Changing basepoint conjugates the loop image in D, so it preserves surjectivity. Consequently Y has no vertex of degree one: pruning such a vertex and its edge, and moving the basepoint if necessary, would give a smaller graph with the same property.

Choose a basepoint p. Decompose Y into arcs by splitting at p and at every vertex of degree at least three. An arc is an edge path with distinct interior vertices, all of degree two and different from p; its endpoints may coincide. If Y is a point, it has no arcs. If Y is a circle, then \beta=1 and marking p gives one arc. In all other cases, the identity

bounds the number of vertices of degree at least three by 2\beta-2. Suppressing all degree-two vertices except possibly p leaves at most 2\beta-1 vertices and therefore at most 3\beta-2 edges. In particular, in every case the number of arcs is at most 3\beta.

Saturating the coefficient alphabet

Start with S\subseteq V equal to the set of columns occurring in bad rows. Apply either of the following rules whenever it adds a new column:

1. 1.

   If an arc has at most 30 occurrences of labels with index outside S, put every index occurring on that arc into S.

2. 2.

   If a row has at least 10 occurrences with index in S, put all its columns into S.

The process terminates, since each step enlarges S\subseteq V. An arc can contribute at most 30 new columns and is used at most once. Thus the initial set and all arc additions together contribute at most

Every nontrivial row addition contributes at most 90 new columns.

Put s=\lfloor\alpha n\rfloor\ge1. If s rows were processed by the second rule, let T consist of the first s such rows. At that moment,

For the strict inequality, use \alpha n<s+1\le2s<3s. This contradicts (24). Thus fewer than s rows are processed, and the final set satisfies

Let U=V\setminus S, which is nonempty. At termination, every arc has either no U-labelled edge or more than 30 such occurrences. Moreover, every row not entirely in S is good and has at most nine S-occurrences. Such a row has at least 91 distinct positive U-letters, and distinct such rows share at most one U-letter.

Let H=\langle x_s:s\in S\rangle be the actual subgroup of D generated by these elements. There is an isomorphism

Indeed, the group on the right maps to D because every defining relation of H and every displayed row hold in D. Conversely, its generators satisfy all the original rows: an omitted row is a true relation of H, and every other row is retained. The resulting maps are inverse on the generators, hence are inverse isomorphisms. In particular, the coefficient group in (27) embeds in the quotient. No finite presentation of H is being assumed.

Finding a long segment in a shortest loop

Call an occurrence of x_u^{\pm1} with u\in U exterior. Choose j\in U and a shortest edge loop P based at p whose label represents x_j in D. This includes the possibility that P is empty. It has no immediate backtracks and therefore traverses complete arcs. Its number of exterior occurrences is consequently either zero or greater than 30.

The label of P is linearly H-reduced: two consecutive exterior occurrences in its linear list cannot be inverse letters separated by an S-word trivial in H. To prove this, suppose that the relevant portion of P is eRf, where R uses only S-edges and has value 1 in H. If f=e^{-1} as oriented edges, the closed detour eRf has value 1 in D, so deleting it shortens P without changing its value. Otherwise e and f are different unoriented edges, and R uses neither of them. Slide the initial incidence of f backwards along R to the terminal vertex of e. This keeps the numbers of vertices and edges unchanged and keeps the graph connected: the path R is still present. Each old traversal of f can be replaced by R^{-1}f in the slid graph, and a reverse traversal by its inverse. Since R has value 1 in D, these substitutions preserve the values of all based loops, so the loop-label image still surjects onto D. Now e^{-1} and f leave the same vertex with the same label. Fold them together. This removes one edge and identifies either zero or one pair of distinct vertices; the graph remains connected, its rank does not increase, and the quotient preserves all loop labels. It is therefore a smaller admissible graph, contrary to the choice of Y. This proves linear H-reduction.

Put L=H*F(x_u:u\in U). The normal form in this free product shows that a linearly H-reduced word representing x_j in L has exactly one exterior occurrence: after evaluating its H-gaps, adjacent free letters separated by trivial gaps form freely reduced blocks. Since P has zero or more than 30 exterior occurrences, its label does not equal x_j in L. Thus \operatorname{lab}(P)x_j^{-1} is nontrivial in L but trivial in D.

Cyclically H-reduce this word by cancelling adjacent inverse exterior letters across gaps trivial in H. Let W be the resulting cyclic word. It still has an exterior occurrence. Otherwise the original word would be conjugate in L to an element of H trivial in D; the embedding of H would make that element, and hence the original word, trivial in L.

There is just one possible disruption of the original path when passing to W. If no cancellation occurs, it is the appended letter x_j^{-1}, which we call the seam letter. If cancellation occurs, the first cancellation must involve that appended letter, by linear H-reduction of P. All later cancellations occur between the two ends of the remaining exterior list of P. The surviving exterior occurrences form a contiguous block of that list, all its intervening gaps are unchanged, and only its closing gap, called the seam gap, may have changed.

Apply Lemma 6.1 to (27) and W. Each mixed row has at least 91 exterior occurrences. If the lemma gives two exterior-disjoint intervals, at least one avoids the seam letter, when present. When there is a seam gap, at most one interval can cross it, because a crossing uses both adjacent exterior occurrences. In either case an interval with at least 91-3=88 exterior occurrences remains intact in P. If the lemma instead gives an entire cyclic relator, remove the seam letter, when present, or cut at the seam gap. This leaves at least 90 exterior occurrences intact in P.

We have therefore obtained a subpath Q of P, beginning and ending with exterior edges, that matches a consecutive portion of a cyclic row or its inverse and has at least 88 exterior occurrences. Its exterior indices are distinct. Its intervening S-words have the same values in H as the corresponding row segments, although their lengths need not agree. The matching row segment has at least 88 of the original 100 letters. Its complementary segment has length at most 12, so the inverse complementary word gives a word z in the original generators such that

If the complementary word is empty, use x_jx_j^{-1} for z.

Shortening the graph

Decompose Q according to its arc traversals, allowing partial traversals at its two ends. Some such traversal contains more than 30 exterior edges of Q. Otherwise no complete traversal could have exterior edges, by saturation, and the two partial traversals would contribute at most 60 exterior occurrences in total. In the chosen traversal, let I run from its first exterior edge through its last exterior edge, inclusive. Then

The segment I has distinct interior vertices of degree two, none equal to p; its endpoints may coincide.

The paths Q_1,Q_2 avoid both the edges and the interior vertices of I. First, neither endpoint of Q is interior to I: at such a vertex the first or last edge of Q would be one of the edges of I, because that vertex has degree two. That edge is exterior, so its two occurrences in Q would repeat an exterior index. Next, any path entering the interior of I from outside must use its first or last edge. Both are exterior and already occur in I, so neither Q_1 nor Q_2 can enter this way. These arguments also exclude a second traversal of an edge of I; when I is closed, the same two boundary incidences give the identical conclusion.

Figure 1 illustrates the construction.

Attach a new path Z between the endpoints of Q with label z, using new interior vertices and k=|z|\le12 new edges. Then delete the edges and interior vertices of I. The old endpoints of I are still connected by the path

which avoids everything deleted. Thus the new graph is connected. The inserted path has k-1 new interior vertices, and the deleted segment has \ell-1 interior vertices, also when either path has coincident endpoints. Hence the changes in the numbers of edges and vertices are both k-\ell, and the graph rank is unchanged. The basepoint survives, since it is not an interior vertex of I.

Equation (28) gives

Every reduced loop at p in the old graph that uses an edge of I must traverse all of I, in one direction or the other: its interior vertices have degree two and do not contain p. Replacing each such traversal by the displayed bypass, or its inverse, gives a loop in the new graph with the same value in D. The loop-label map of the new graph therefore remains surjective. Its edge count has decreased by at least 31-12=19, contradicting minimality of Y. This proves the theorem.□

Proof. Eventually \alpha n\ge1 and 100b\le\alpha n, so Theorem 7.1 applies.□

Proof of Theorem 1.1. Lemma 2.1 shows that \Gamma is finitely generated and that J is infinite. The actions of Section 2 are essentially free and p.m.p., and conull restriction does not change their costs.

Fix \alpha with the inequalities in the theorem, and set \eta=\alpha/100>0. Proposition 5.2 gives exact finite right A-sets V_k of sizes n_k\to\infty, with vanishing fixed-point fractions for every nonidentity A-element, expansion (21), and b(V_k)=o(n_k). For all sufficiently large k, we have \alpha n_k\ge1 and 100b(V_k)\le\alpha n_k. The row systems defining D_{V_k} then satisfy every hypothesis of Theorem 7.1. Hence

By Proposition 5.1,

Proposition 4.1 therefore gives

For every integer M>100, Proposition 2.4 gives

The Y_M-orbits are infinite, because \Gamma is infinite and its action is free. Corollary 3.4 therefore gives

so these costs tend to one as M\to\infty. An integer M>\max\{100,99/\eta\} exists and satisfies 1+99/M<1+\eta. The two costs are therefore strictly different, which proves the theorem.□