A GROUP WITHOUT FIXED PRICE
A complete, self-contained exposition
==========================================================================

Abstract. Gaboriau asked whether every countable group has a single
"price": whether all of its essentially free probability-measure-preserving
(p.m.p.) actions need the same average number of edges to connect their
orbits. We build a finitely generated group Gamma with two free p.m.p.
actions of different cost. One action has cost at least 1 + a positive
constant; the other has cost arbitrarily close to 1. So fixed price fails
in general.

The group is an amalgam of a free group of rank 100 with a direct product
J x Z. The cheap action uses a finite height coordinate to recycle a few
a-edges; the expensive action is the plain Bernoulli shift, whose cost is
bounded below by the rank of an explicit finitely presented group coupled
to a large random finite model.

This text is written to be read straight through. Every statement used in
the final proof is proved here. The only background assumed is the
definition of a group, a group action, a probability space, and the free
group on a finite set.

==========================================================================
PART 0. THE ONE IDEA, IN PLAIN WORDS
==========================================================================

Take a countable group G acting on a probability space X by
measure-preserving bijections. Its orbit relation R connects two points
when one is the image of the other under a group element. A graphing of
R is a countable list of partially-defined bijections whose graphs sit
inside R and whose compositions connect every pair of R-related points,
up to a null set. The cost of a graphing is the sum of the measures of
its domains. The cost of R is the smallest such sum.

Cost asks: how many "edge slots", on average, are needed to wire up the
orbits? A free group of rank r acting freely needs exactly r edges per
point (its rank). An infinite amenable group can often be wired up with
cost barely above 1 by using a single cyclic "spine" and cheap shortcuts.

The fixed price question: does the cost of R depend only on G, not on the
action? For free groups, for many product groups, and for many amenable
groups the answer is yes. This paper shows the answer is no in general.

The trick. Let Gamma = A *_J (J x Z), where A is free of rank 100 and J
is a particular free subgroup of A of rank 100 (free on b_1,...,b_99 and a
long word w). There is a homomorphism chi : Gamma -> Z that counts a's.
Two actions:

  (1) the Bernoulli shift on X; cost we will bound below by 1 + eta, some
      positive eta;
  (2) the product of the shift with a cyclic height coordinate mod M. The
      height lets us recover most a-edges from a cheap spine, giving cost
      at most 1 + 99/M, which tends to 1.

Choosing M large makes the two costs differ. That is the whole strategy.
Everything below is the machinery needed to make steps (1) and (2) rigorous.

==========================================================================
PART 1. THE GROUP, THE COEFFICIENT HOMOMORPHISM, AND THE TWO ACTIONS
==========================================================================

1.1 The group.

Let A = F(a, b_1, b_2, ..., b_99) be the free group on 100 generators.
Inside A define words

    u_0 = 1,   u_i = u_{i-1} a b_i     (1 <= i <= 99),   w = u_99 a.

Written out:

    u_1 = a b_1,
    u_2 = a b_1 a b_2,
    ...
    u_99 = a b_1 a b_2 ... a b_99,
    w = u_99 a = a b_1 a b_2 ... a b_99 a.

So w is a word of length 199 with 100 a's and 99 b's, starting and ending
with a. Let

    J = < b_1, ..., b_99, w > <= A,
    B = J x ,       infinite cyclic,
    Gamma = A *_J B.

The embedding J -> B is j |-> (j, 1).

Lemma 1.1 (Normal form).
(a) A and B embed in Gamma and A cap B = J.
(b) If g_1, ..., g_n lie alternately in A \ J and B \ J then
    g_1...g_n is not in J for n >= 1, and for n >= 2 it lies in neither
    factor.
(c) J is free on b_1, ..., b_99, w; in particular J is infinite.
(d) Gamma is countably infinite and generated by a, b_1, ..., b_99, t.

Proof.
(a)+(b). In each factor choose coset representatives for the cosets gJ,
with 1 representing J. Consider formal strings r_1 r_2 ... r_n j where the
r_i are nonidentity representatives alternating between the two factors
and j in J (allow n = 0). Define right multiplication by an element g of
one factor: if the last representative comes from the same factor,
multiply the trailing j by g and rewrite as r j' in that factor; otherwise
write j g = r j' and append the representative r, omitting r when it is 1.
This defines a right action of each factor. To check the action law for two
multipliers in the same factor, keep the prefix ending in the other factor
and multiply the remaining suffix inside the chosen factor; the description
still works when the suffix representative becomes 1. The two factor
actions agree on J (which only post-multiplies the final j-entry), so
together they give an action of the amalgam Gamma.

Acting on the identity string recovers the coset decomposition of a factor
element, so A and B embed in Gamma. Their intersections correspond to
strings with no representatives, i.e. to J, so A cap B = J. Multiplying by
an alternating sequence outside J appends one nonidentity representative at
each step (because j g is not in J for j in J and g not in J). After n steps
the string has length n; strings of length 0 are exactly J, and strings of
length at most 1 are exactly the factor elements. This gives (b).

(c). Expand a reduced nonempty word in b_1,...,b_99,w inside the free basis
{a,b_1,...,b_99} of A. Since w and w^{-1} both begin and end with a^{+-1},
no boundary between a b-symbol and a w-symbol cancels; boundaries between
two w-symbols either have equal signs (no cancellation) or are inverse
symbols (forbidden by reducedness); boundaries between two b-symbols do not
cancel. The expansion is a nonempty reduced word in A, so the displayed
generators of J are a free basis. Hence J is infinite.

(d). The elements a, b_1,...,b_99 generate A, t generates the Z-part of B,
and A together with t generates both factors of Gamma. Finitely many
generators means Gamma is countable, and it is infinite because it contains
the infinite group J. QED

1.2 The coefficient homomorphism.

Define chi : Gamma -> Z by chi(a) = 1 and chi(b_i) = chi(t) = 0.

Lemma 1.2 (chi is well defined and freeness of the height action).
(a) chi is a well-defined homomorphism Gamma -> Z; it satisfies
    chi(u_i) = i and chi(w) = 100. Its restriction to J is not zero: it
    sends w to 100.
(b) For every positive integer M, the action on
        Y_M = X x Z/MZ
    (X introduced below, uniform height coordinate) given by
        (x, r) g = (xg, r + chi(g) mod M)
    is free and p.m.p. on a standard Borel probability space.

Proof.
(a). Let chi_A : A -> Z be the exponent sum in a. Since J = J, define
chi_B : B -> Z by chi_B(j t^n) = chi_A(j); this is a homomorphism and agrees
with chi_A on J, so the universal property of the amalgam gives chi. The
formulas chi(u_i) = i and chi(w) = 100 follow from the definitions.
(b). The homomorphism law of chi gives the right-action law; both coordinate
actions preserve their measures; freeness on the first coordinate (proved in
1.3) gives freeness of the product; the product is standard Borel. QED

1.3 The two probability spaces.

Let X_0 = [0,1]^Gamma with product Lebesgue measure mu_0 and the right
action (xg)(h) = x(gh). This is a standard Borel probability space (a
countable product of compact metric spaces). For g != 1 the equation xg = x
forces x(g) = x(1), two independent uniform coordinates, hence has
probability 0. Therefore

    X = { x in X_0 : x g != x for every g != 1 }

is an invariant Borel conull set. We write mu for the restricted probability
measure. This free Bernoulli action has the same orbit-relation cost as the
unrestricted action (restricting an orbit graphing to an invariant conull
set leaves each domain measure unchanged, and conversely).

RESTRICTION FACT (used repeatedly). For an essentially free action of a
countable group, the set of points with trivial stabilizer is Borel,
invariant, and conull; restricting to it makes the action pointwise free and
preserves the measure and the orbit-relation cost. More generally a Borel
conull set can be made invariant by intersecting its countably many
translates. Restricting any orbit graphing to that set keeps its edges inside
the set and does not change domain measures; a graphing on the restricted set
generates the original relation on a conull set at the same cost.

R_A, R_B, R_J, R_Gamma denote the orbit relations of the corresponding
subgroups acting on the space at hand. Cost means orbit-relation cost.

==========================================================================
PART 2. THE UPPER BOUND: A CHEAP ACTION
==========================================================================

Fix M > 100. Let nu_M = mu x (uniform measure on Z/MZ) on Y_M, and let
Gamma act on Y_M by the height action of Lemma 1.2. We will wrap R_B up
cheaply, then recover the a-edges from a thin slab of heights.

2.1 A cheap graphing of R_B.

Lemma 2.1 (small marker). For every 0 < p < 1 and every positive integer M
there is a Borel set C_p subset Y_M of measure p meeting every -orbit. The
graphing consisting of t on all of Y_M and of b_1,...,b_99,w restricted to
C_p generates R_B and has cost 1 + 100p.

Proof. Inside X put
    N_p = { x in X : x(t^n) >= p for every n in Z },
    C_p = ( { x in X : x(1) < p } cup N_p ) x Z/MZ.
The coordinates x(t^n) (n in Z) are independent (the group elements t^n are
distinct), and the probability that x(t^n) >= p for 0 <= n < N is (1-p)^N,
so N_p is null, Borel, and t-invariant. Thus nu_M(C_p) = mu({x : x(1) < p})
= p.

Every -orbit in Y_M has the form {x t^n : n in Z} x {r}; it is t-stable
so lies in a single height r. It meets the first part of C_p iff some
x t^n has (x t^n)(1) < p, i.e. x(t^n) < p. If it does not, then x(t^n) >= p
for all n, i.e. x lies in N_p, so the orbit meets N_p x Z/MZ. Hence C_p
meets every -orbit.

Now let j be one of b_1,...,b_99,w and let z in Y_M. Choose n with
z t^n in C_p. Since j in J commutes with t in B,
    z -> z t^n -> z t^n j -> z t^n j t^{-n} = z j
is a path in the graphing (the middle step uses the j-map restricted to C_p,
the outer steps use t or t^{-1}). Hence every generator of B is connected
everywhere in the generated relation. Conversely every map in the graphing
is a restriction of an element of B. Each of the 100 restricted generators
(b_1,...,b_99,w) costs p, and the full t-map costs 1. QED

2.2 Recovering the a-edges from a slab.

Proposition 2.2 (small cost). For every integer M > 100, the free p.m.p.
action Gamma on (Y_M, nu_M) satisfies
    Cost(R_Gamma on Y_M) <= 1 + 99/M.

Proof. Fix 0 < p < 1 and take the graphing of Lemma 2.1. Add the
restriction of a to the union of height fibers 0, 1, ..., 98; its domain has
measure 99/M. The total cost is 1 + 100p + 99/M. Let E be the generated
relation; E contains R_B, and we show it contains every a-edge.

Claim (propagation). Suppose (z, za) is in E whenever z has height one of
k, k+1, ..., k+98 (mod M). Then the same holds with source height k+99.

Indeed, given z of height k+99, set y = z u_99^{-1}; this has height
k + 99 - chi(u_99) = k + 99 - 99 = k. The points
    y = y u_0, y u_1, ..., y u_99 = z
are connected by E: at the i-th step, apply a to y u_{i-1} (of height
k + i - 1, which for 1 <= i <= 99 runs through k, ..., k+98, all inside the
assumed slab) and then apply b_i (a B-edge). The a-edge is assumed present;
the b_i-edge is in R_B; and y w = y u_99 a = z a fits the w-edge in R_B. So
z and za are E-equivalent. This proves the claim.

Heights 0,...,98 are known initially. Apply the claim for the ordinary
integers k = 0, 1, ..., M - 100; it supplies source heights 99, 100, ...,
M-1, and the last a-edges land at height 0 mod M. So every a-edge is in E.
Since B and a generate Gamma, E generates R_Gamma. Now let p -> 0. QED

==========================================================================
PART 3. THE LOWER BOUND: WHAT WE MUST PROVE
==========================================================================

The expensive action is the plain Bernoulli shift on X. Define the relative
quantity
    delta_X = inf { C(E) : E is a graphing in R_A with R_J v E = R_A }.
Only edges added to the free relation R_J are charged. The lower bound
factors into three independent estimates.

STEP 1 (Deploy and compress; Part 4). Cost(R_Gamma on X) >= 1 + delta_X.

STEP 2 (Transfer; Part 5). Along any asymptotically free sequence of finite
permutation models V_k of A,
    delta_X >= limsup_k rk(D_{V_k}) / |V_k|,
where D_{V_k} is an explicit finitely presented group built from V_k.

STEP 3 (Rank bound; Parts 6-8). Random permutation models V_k satisfy the
hypotheses of a deterministic rank theorem, which gives
    rk(D_{V_k}) > eta |V_k|     for large k.
Hence delta_X >= eta and Cost(R_Gamma on X) >= 1 + eta.

==========================================================================
PART 4. DEPLOYMENT AND COMPRESSION: STEP 1
==========================================================================

Throughout, Gamma = A *_J B is finitely generated, J is infinite, and Gamma
acts essentially freely and p.m.p. on a standard probability space (X, mu).

4.0 The engine: a compression lemma (proved in 4.1-4.2).

Setup. Let (Z, lambda) be a standard Borel space with a finite Borel measure
(not necessarily normalized). Let R be a Borel equivalence relation covered
by the graphs of countably many measure-preserving Borel partial isomorphisms
(psi_j). A partial isomorphism is a Borel bijection between Borel sets with
Borel inverse. For a Borel subrelation U of R and Borel W subset Z put
    kappa(U ; W) = int_W 1/|[z]_U| dlambda(z),   kappa(U) = kappa(U ; Z),
with 1/(infinite class size) = 0. A set is U-complete if it meets every
U-class. All relations are pointwise Borel. When identities hold only a.e.,
first delete the R-saturation of the exceptional null set (Borel and null,
since the psi_j preserve measure).

Lemma 4.0a (finite-class counting). Let W be a Borel U-invariant set, all
U-classes finite. If B subset W is Borel and meets each U-class exactly once, then
lambda(B) = kappa(U ; W).

Proof. On the part W_k where classes have size k, order each class into k
Borel sheets. The map from B cap W_k to any one sheet, staying inside classes,
is a Borel partial isomorphism inside R, so all k sheets have measure
lambda(B cap W_k). Thus lambda(W_k) = k lambda(B cap W_k). Sum over k. QED

Lemma 4.0b (small complete sets). For every Borel subrelation T subset R and every
eps > 0 there is a Borel T-complete set M subset Z with
lambda(M) <= kappa(T) + eps.

Proof. On the union Z_fin of finite T-classes, choose the least point of each
class (fix a Borel linear order on Z); this Borel transversal M_fin has
measure kappa(T) by Lemma 4.0a.

On Z_inf = Z \ Z_fin choose increasing finite Borel partitions P_n that
separate all points. Let k_n(z) be the number of atoms of P_n meeting
[z]_T; this is Borel and k_n(z) -> infinity. Fix 0 < p < 1 with
p lambda(Z_inf) < eps/2. At level n mark each atom independently with
probability p and let A be the union of marked atoms. The Borel set
    M_inf = A cup (Z_inf \ [A]_T)
meets every infinite T-class. The union is disjoint and
    E lambda(M_inf) = p lambda(Z_inf) + int_{Z_inf} (1-p)^{k_n(z)} dlambda(z),
and the integral tends to 0. For large n the expectation is < eps, so some
marking has measure < eps. Set M = M_fin cup M_inf. QED

Lemma 4.0c (compression). On (Z, lambda) with ambient R as above, suppose
S subset T subset Q subset R are Borel equivalence relations and Q = S v E, where
E = (phi_i : D_i -> E_i) is a countable family of measure-preserving Borel
partial isomorphisms with finite total cost C(E) = sum_i lambda(D_i). For
every eps > 0 there is a countable family F of measure-preserving Borel
partial isomorphisms inside Q with
    Q = T v F,    C(F) <= C(E) - kappa(S) + kappa(T) + eps.

Proof. Take a Borel T-complete set M from Lemma 4.0b and put
    Y = [M]_S cup { z : |[z]_S| = infinity }.
Y is Borel, S-invariant, T-complete (it contains M), hence Q-complete. Every
S-class outside Y is finite; in each finite S-class inside Y pick a point of
its intersection with M. Lemma 4.0a gives
    kappa(S ; Y) <= lambda(M).                                   (4.1)

Delete one edge per class outside Y. Let d(z) be the least number of E-edges
(in either direction) needed to reach Y, allowing S-steps for free. This is
finite (Y is Q-complete), Borel (sublevel sets are built from Y by taking
E- and E^{-1}-images and S-saturations), constant on S-classes, and zero
exactly on Y. For each S-class K outside Y pick an oriented E-edge instance
from y_K in K to y'_K with d(y'_K) = d(K) - 1 (it exists on a shortest
path); make the choice Borel by taking the least eligible (map index,
direction) and then the least point of the finite class K. The set V = {y_K}
is a Borel transversal of S on Z \ Y, so
    lambda(V) = kappa(S ; Z \ Y).                                (4.2)

For each original map phi_i let V_i^+ be the chosen origins whose edge is
traversed forward under phi_i, and V_i^- those traversed under phi_i^{-1}.
Delete the domain set H_i = V_i^+ cup phi_i^{-1}(V_i^-) from D_i. The two parts
are disjoint: an instance chosen both ways would make each endpoint class
closer than the other. The V_i^+, V_i^- partition V and inverse images under
phi_i preserve measure, so the residual family E' = (phi_i restricted to
D_i \ H_i) satisfies the exact identity
    C(E') = C(E) - sum_i lambda(H_i) = C(E) - kappa(S ; Z \ Y).  (4.3)
(Count distinct indices even when geometric edges coincide; this handles
graphings with repetitions.)

Move the remaining edges into Y. Define f : Z -> Y by f(x) = x for x in Y
and, for x in an S-class K outside Y, f(x) = f(y'_K); recursive in the
integer distance, hence Borel. Each (x, f(x)) lies in Q. Because Y is
S-invariant, f fixes each class inside Y pointwise and is constant on each
class outside Y; so f sends S-steps to S-steps and every deleted edge has
equal images at its endpoints.

Because f may be many-to-one, split the surviving domains at both ends. For a
residual map phi_i with domain D'_i, partition D'_i into Borel pieces
P_{i,r,s} according to the least indices r, s with
    f(x) = psi_r(x),   f(phi_i(x)) = psi_s(phi_i(x))
(these exist since graph(f) subset Q subset R). On this piece the pushed edge is the
partial isomorphism
    phi^_{i,r,s} = psi_s o phi_i o psi_r^{-1} :
        psi_r(P_{i,r,s}) -> psi_s(phi_i(P_{i,r,s})),
measure-preserving, with graph in Q|Y, cost lambda(P_{i,r,s}). Let F be the
family of all these maps. The pieces partition each D'_i, so
    C(F) = sum_{i,r,s} lambda(P_{i,r,s}) = C(E').               (4.4)
(Discarding identities only lowers the cost.)

Recover the relation. For two Q-related points in Y take a finite path with
steps in S and E and apply f. Endpoints stay fixed; S-steps stay S-steps;
deleted edges become stationary; surviving edges become F-edges. Hence
Q|Y = (S|Y) v F. For arbitrary x Q x', pick y in [x]_T cap Y and y' in
[x']_T cap Y (T-completeness), so y Q y'. The preceding identity joins them
using S subset T and F, and two T-steps finish: Q = T v F.

Finally combine (4.1), (4.3), (4.4):
    C(F) <= C(E) - kappa(S ; Z \ Y) = C(E) - kappa(S) + kappa(S ; Y)
         <= C(E) - kappa(S) + lambda(M)
         <= C(E) - kappa(S) + kappa(T) + eps. QED

Corollary 4.0d (cost of infinite classes is at least 1). A countable p.m.p.
Borel equivalence relation on a standard probability space, all of whose
classes are infinite, has cost at least 1.

Proof. Let E be a finite-cost generating graphing of Q. Apply Lemma 4.0c
with S = identity and T = Q. Then kappa(S) = 1 and kappa(Q) = 0, giving
0 <= C(F) <= C(E) - 1 + eps for every eps > 0, so C(E) >= 1. Infinite-cost
graphings also satisfy this; take the infimum. QED

REMARK (normalization). The estimate uses the original finite measure
throughout; kappa(identity) = lambda(Z). The output graphing stays inside the
same relation Q, but no inclusion between old and new edge families is
claimed. These are exactly the features needed when the lemma is applied
repeatedly on an enlarged space.

4.1 A near-optimal Gamma-graphing, subdivided into factor edges.

Fix rho > 0. We claim there is a finite generating graphing of R_Gamma,
consisting of restrictions of nonidentity group translations, of cost c with
    c < Cost(R_Gamma) + rho.                                     (4.5)

Approximation argument. Start with a countable generating graphing of cost
< Cost(R_Gamma) + rho/2 and split each map into disjoint Borel pieces
according to its group displacement (cost unchanged; discard identity
pieces). Let Psi_N be the first N maps and T_N the relation they generate.
For a fixed finite generating set K of Gamma not containing 1 put
    D_{N,s} = { x in X : (x, xs) not in T_N },  s in K.
Each D_{N,s} is Borel (membership in T_N is witnessed by a finite path) and
the D_{N,s} decrease to a null set, so sum_{s in K} mu(D_{N,s}) -> 0. Adding
the translation by s on D_{N,s} for each s in K gives a finite generating
graphing, proving (4.5) for large N.

Write its maps as x |-> x g_h on Borel domains D_h (h in a finite index set),
and choose factor words g_h = g_{h,1} ... g_{h,L_h} with each g_{h,i} in
A cup B and L_h >= 1. For letters in J choose either factor type. Form a space
Z by adjoining L_h - 1 disjoint copies of D_h to X, one for each internal
vertex of the word. Give each copy its inherited measure and denote the
resulting unnormalized measure by lambda. Then
    lambda(Z) = 1 + sum_h (L_h - 1) mu(D_h) < infinity.
Define P : Z -> X as the identity on X and, on the copy indexed by (h, i),
    P(x, h, i) = x g_{h,1} ... g_{h,i}.
The restriction of P to each sheet is a measure-preserving Borel bijection
onto its image. For L = Gamma, A, B, J define the pullback relations
    Rbar_L = { (z, z') in Z^2 : (Pz, Pz') in R_L }.
These are countable p.m.p. Borel equivalence relations: if P_r, P_s are
sheet restrictions, the partial maps P_s^{-1} o (x |-> x l) o P_r, for l in L,
enumerate their pairs and preserve measure on their natural domains.

Replace each original edge by the chain through its new vertices, and divide
the successive edges by factor type into E_A^0 and E_B^0. Every chain edge
belonging to the h-th map has cost mu(D_h), so
    C(E_A^0) + C(E_B^0) = c + lambda(Z) - 1.                     (4.6)
Their join is Rbar_Gamma. (First connect base-sheet points by subdividing
paths of the original graphing; every extra point hangs off a base-sheet
point in the same projected orbit; this also connects pullback pairs.)

4.2 The iteration.

Set S_0 = identity on Z. We build relations S_n subset Rbar_J and graphings
E_i^n subset Rbar_i (i = A, B) with Q_i^n = S_n v E_i^n. Fix eps > 0 and choose
positive errors e_n with sum e_n < eps. At stage n choose i = A or B
alternately and set
    S_{n+1} = Q_i^n cap Rbar_J.
Then S_n subset S_{n+1} subset Q_i^n. Apply Lemma 4.0c with S = S_n, T = S_{n+1},
Q = Q_i^n, error e_n. It replaces E_i^n by E_i^{n+1} with
    Q_i^n = S_{n+1} v E_i^{n+1},
    C(E_i^{n+1}) <= C(E_i^n) - kappa(S_n) + kappa(S_{n+1}) + e_n.
Leave the other family fixed. The processed relation Q_i^{n+1} = Q_i^n; the
other grows because its supplied relation grows. Both sequences Q_i^n
increase, stay inside their factor relations, and their join is Rbar_Gamma
at every stage. (Edge families themselves need not increase.)

All costs and all kappa use lambda without normalizing. Summing the
compression inequalities and using kappa(S_0) = lambda(Z) and (4.6),
    C(E_A^n) + C(E_B^n) <= c - 1 + kappa(S_n) + eps,  n >= 0.    (4.7)
In particular every graphing used later has finite cost.

4.3 Exhausting the amalgamating relation.

Let S_inf = cup S_n and Q_i^inf = cup Q_i^n; both are Borel equivalence
relations. Monotonicity gives
    Q_A^inf v Q_B^inf = Rbar_Gamma,  Q_i^inf cap Rbar_J = S_inf.   (4.8)
(For the nontrivial inclusion in the second identity, a pair in
Q_i^n cap Rbar_J enters S_{m+1} at the next later stage m at which type i is
processed.)

Claim. S_inf = Rbar_J. Take a pair in Rbar_J and a shortest chain joining
its endpoints with steps in Q_A^inf or Q_B^inf. If the chain has at least two
steps, its types alternate (adjacent same-type steps compose), and no step
lies in Rbar_J (by (4.8) such a step would be in S_inf, hence in both factor
relations, and could be composed with a neighbor). Projecting to X, freeness
gives unique group displacements; they form an alternating word with letters
outside J whose product lies in J (projected endpoints are J-related),
contradicting amalgam normal form (Lemma 1.1b). So the shortest chain has
length at most one, and (4.8) puts its endpoint pair in S_inf.

Every Rbar_J-class is infinite: the class of z contains the distinct base
points P(z) j, j in J. Since [z]_{S_n} increases with this infinite union,
1/|[z]_{S_n}| decreases to 0; the integrands are bounded by 1 on the finite
space Z, so dominated convergence gives
    kappa(S_n) -> 0.                                             (4.9)

4.4 Returning to X.

Fix a finite stage n. For each map phi in E_i^n partition its domain by
source sheet r and target sheet s. On such a piece D the map
    P_s o phi o P_r^{-1} : P_r(D) -> P_s(phi(D))
is a p.m.p. Borel partial isomorphism on X, lies in R_i, and has cost
lambda(D). These maps form a graphing F_i^n with
    C(F_i^n) <= C(E_i^n).                                        (4.10)
(Only sheet restrictions of P are used; no injectivity of P on all of Z.)

Put T_i = R_J v F_i^n. Projecting paths from the base sheet gives
T_A v T_B = R_Gamma: every S_n-step projects into R_J, the rest into the
graphings. We show T_A = R_A. For a pair in R_A take a shortest chain with
steps from T_A, T_B. A chain of length >= 2 would alternate and contain no
R_J-step (that relation is inside both T_A and T_B); its displacement word
would alternate outside J, have length >= 2, and lie in A, contradicting
amalgam normal form. A single B-step between A-related endpoints has
displacement in A cap B = J, so already lies in T_A. Hence T_A = R_A.

So F_A^n is admissible in the definition of delta_X. By (4.7), (4.10), at
every finite stage
    delta_X <= C(F_A^n) <= C(E_A^n) + C(E_B^n) <= c - 1 + kappa(S_n) + eps.
Let n -> infinity using (4.9), then let eps -> 0 and rho -> 0 in (4.5).

PROPOSITION 4.11 (deployment). Let Gamma = A *_J B be finitely generated, J
infinite, Gamma acting essentially freely and p.m.p. on (X, mu). With
delta_X as above,
    Cost(R_Gamma on X) >= 1 + delta_X.

Proof. Combine 4.1-4.4: c -> Cost(R_Gamma) as rho -> 0, and the last chain
reads delta_X <= Cost(R_Gamma) - 1 + eps for every eps > 0. QED

==========================================================================
PART 5. TRANSFER TO FINITE MODELS: STEP 2
==========================================================================

5.1 Finite models and the group D_V.

A finite exact right A-set is a finite set V with a right action of A by
permutations (action laws hold as equalities). For such a V put
    D_V = < x_v (v in V) | x_v x_{v u_1} ... x_{v u_99} = 1  (v in V) >,
where u_0 = 1 and u_i = u_{i-1} a b_i, as in Part 1. (The row for v records
a-steps: w = u_99 a becomes trivial in this encoding, and every J-step is set
to the identity, matching the role of R_J being supplied for free.) Write
    Fix_V(g) = { v in V : v g = v },  n = |V|,  and rk(D) for the minimal
number of generators of D.

PROPOSITION 5.2 (transfer). Let V_k be finite exact right A-sets with
n_k = |V_k| -> infinity such that for every fixed g in A \ {1},
    |Fix_{V_k}(g)| / n_k -> 0.                                   (5.3)
Then, for the free Bernoulli action on X from Part 1,
    delta_X >= limsup_k rk(D_{V_k}) / n_k.

Proof. We use right actions, so (xg)(h) = x(gh). Choose representatives h_c
for the cosets A h_c in Gamma and let Omega = [0,1]^{A \ Gamma} with product
measure. The coordinate rearrangement x |-> ( (x(g h_c))_c )_{g in A}
identifies the restriction of X_0 to A with Omega^A (independent base
coordinates, right action (xi q)(g) = xi(qg)). Write mu for the product
measure; everything is on invariant conull sets, so the conull restriction to
X changes nothing.

Cocycle. For a finite exact A-set V define theta : V x A -> D_V on the free
basis of A by
    theta(v, a) = x_v,  theta(v, b_i) = 1,  theta(v, s^{-1}) = theta(v s^{-1}, s)^{-1}
for each basis letter s, extended multiplicatively along words. Cancellation
of adjacent inverse letters cancels their two values at the corresponding
sources; since A is free this is well defined and satisfies
    theta(v, gh) = theta(v, g) theta(vg, h).                     (5.4)
The word w = u_99 a = a b_1 a b_2 ... a b_99 a gives
theta(v, w) = x_v x_{v u_1} ... x_{v u_99} = 1, and theta(v, b_i) = 1.
The inverse rule and (5.4) then give
    theta(v, j) = 1   for all v in V, j in J.                    (5.5)
Note theta(v, g) depends on the label g, not only the endpoints (v, vg).

Paid maps. Fix a finite-cost graphing E with R_J v E = R_A and fix eps > 0.
(Finite-cost graphings suffice for delta_X: the full a-translation together
with R_J generates R_A.) On an invariant conull free set, split each map of E
by its unique displacement in A, giving countably many restrictions
    phi_l : L_l -> L_l g_l,  phi_l(x) = x g_l,  g_l in A,
with sum_l mu(L_l) = C(E).

Path types. A path type is a finite list of full J-translations and signed
paid indices l; its label is the product in A of the successive step labels.
Almost every x has a valid path to xa, and freeness forces such a path's
label to be exactly a. There are countably many path types; choose finitely
many, each of label a, whose validity sets cover measure >= 1 - eps. Let I
be their finite set of paid indices and m_l the total occurrences of index l.
Approximate by finite-coordinate cylinders: choose cylinder-measurable sets
L'_l depending on finitely many A-coordinates with
    sum_{l in I} (1 + m_l) mu(L_l symdiff L'_l) < eps                 (5.6)
(finite-coordinate sets form an algebra generating the product
sigma-algebra, and closure in the metric mu(E symdiff F) is a sigma-algebra).

Replacing each test "x h in L_l" (forward) or "x h g_l^{-1} in L_l"
(inverse) by the corresponding test in L'_l changes each validity predicate
on a set of measure at most mu(L_l symdiff L'_l). If P' is the union of the
modified validity sets, then
    sum_{l in I} mu(L'_l) <= C(E) + eps,   mu(P') >= 1 - 2 eps. (5.7)
All L'_l and P' depend on a single finite coordinate set F subset A (a test of an
F_l-cylinder after prefix h uses coordinates h F_l, or h g_l^{-1} F_l for an
inverse step). F is fixed before k -> infinity.

Evaluate on V_k. For independent base labels (z_v)_{v in V_k} with law Omega
put xi_v = (z_{v g})_{g in A}; exactness gives xi_{v q} = xi_v q. If v g != v h
for all distinct g, h in F, the F-coordinates of xi_v are exactly product
distributed. The exceptional fraction is at most
    rho_k(F) = sum_{g != h in F} |{ v : v g h^{-1} = v }| / n_k -> 0   (5.8)
by (5.3). Hence for every measurable F-cylinder E,
    | (1/n_k) sum_{v in V_k} Pr(xi_v in E) - mu(E) | <= rho_k(F). (5.9)
(No independence between different sources is used.)

Generating list. For any realization of labels, list theta(v, g_l) for every
l in I and every v with xi_v in L'_l. If xi_v in P', follow a modified valid
path from v. A forward paid factor occurs on the list; an inverse paid step
after prefix h contributes theta(vh, g_l^{-1}) = theta(v h g_l^{-1}, g_l)^{-1},
whose inverse-domain test puts theta(v h g_l^{-1}, g_l) on the list. Each
J-step contributes 1 by (5.5). Since the path label is exactly a, (5.4)
expresses x_v = theta(v, a) as a product of listed elements and inverses. (xi_v
need not be free; freeness only selected the original path labels.) Add x_v
for every source with xi_v not in P'. The resulting list generates D_{V_k},
so for every labeling
    rk(D_{V_k}) <= sum_{l in I} sum_{v in V_k} 1_{L'_l}(xi_v)
                 + sum_{v in V_k} 1_{(P')^c}(xi_v).
Take expectations, use (5.9), then let k -> infinity:
    limsup_k rk(D_{V_k})/n_k <= sum_{l in I} mu(L'_l) + 1 - mu(P')
                             <= C(E) + 3 eps     by (5.7).
Let eps -> 0 and take the infimum over E (all path and cylinder tests were
fixed before the limit). QED

==========================================================================
PART 6. RANDOM PERMUTATION MODELS: STEP 3, EXISTENCE
==========================================================================

Regard the defining relator for v as an ordered row with columns
v u_0, v u_1, ..., v u_99. For T subset V put
    N(T) = cup_{v in T} { v u_0, ..., v u_99 }.
Call a row bad if it has a repeated column or shares at least two distinct
columns with another row; let b(V) be the number of bad rows.

PROPOSITION 6.1 (models). Put K = e^{96} 96^{99} / 95^{95}. Fix
    0 < alpha < 1/200,   K alpha^3 < 1/2.
There is a sequence of finite exact right A-sets V_k with n_k = |V_k| ->
infinity satisfying (5.3) and
    |N(T)| > 96 |T|   for all T subset V_k with 1 <= |T| <= alpha n_k,  (6.2)
    b(V_k) = o(n_k).                                              (6.3)

Proof. (i) Change of basis. a, u_1, ..., u_99 is a free basis of A: the
substitutions defining u_i have inverse substitutions b_i = a^{-1} u_{i-1}^{-1}
u_i, which are inverse homomorphisms between the free groups on the two
proposed bases (they recover b_i directly and u_i by induction). Assign
independent uniform permutations of {1, ..., n} to the 100 elements of this
basis; this defines an exact right A-action.

(ii) Expansion. Fix 1 <= s <= floor(alpha n). If a set T of size s violates
(6.2), then N(T) lies in a set C of size 96 s containing T (since u_0 = 1,
T subset N(T)); such a C exists because 96 s < n. For fixed T there are
binom(n - s, 95 s) possible C. For one uniform permutation sigma,
    Pr(T sigma subset C) = (96 s)(96 s - 1)...(96 s - s + 1) /
                      (n (n-1)...(n-s+1))
                    <= (96 s / n)^s.
Using independence of the 99 permutations for u_1,...,u_99 and binom(n,r) <=
(e n / r)^r,
    Pr( there is T, |T| = s, |N(T)| <= 96 s )
        <= binom(n,s) binom(n, 95 s) (96 s / n)^{99 s}
        <= [ K (s/n)^3 ]^s,
the exponent being 99 - 1 - 95 = 3. Set q = K alpha^3 < 1/2. For every fixed
integer R >= 1 the sum over allowed sizes is at most
    sum_{s=1}^{min(R, floor(alpha n))} [K (s/n)^3]^s + q^{R+1}/(1-q).
First let n -> infinity, then R -> infinity; so (6.2) holds with probability
tending to 1 (including s = 1; if floor(alpha n) = 0 it is vacuous).

(iii) Fixed points. Fix a nonempty freely reduced word of length L in the
random basis and a start v_0; expose permutation entries only as needed.
Until the first repeated vertex the current vertex is new except as the
endpoint of its incoming edge, and free reduction forbids the next letter
from immediately re-requesting that edge. At step t the requested partner is
uniform among at least n - t + 1 available vertices, at most t already
visited. For n >= L,
    Pr(v_0 fixed by the word) <= sum_{t=1}^L t/(n - t + 1)
                              <= L(L+1) / (2(n - L + 1)) -> 0.
The same bound holds for the expected fixed-point fraction, tending to 0 for
each fixed nonidentity element of A.

(iv) Simultaneous choice. Enumerate nonidentity elements of A as g_1, g_2,
.... At stage k take n_k > n_{k-1} large enough that expansion fails with
probability <= 1/4 and E|Fix_V(g_j)|/n_k <= 1/(4 k^2) for 1 <= j <= k. Markov
plus a union bound gives: with probability <= 1/4, some j <= k has
fixed-point fraction > 1/k. Choose an outcome with expansion and all these
fixed-point bounds. This gives (5.3) for every fixed element, without uniform
estimates over words of growing length.

(v) Bad rows. A repeated column in row v gives v u_i = v u_j (i != j), so v
is fixed by the nonidentity word u_i u_j^{-1}. If two distinct columns are
shared by rows v != y, choose indices with v u_i = y u_k and v u_j = y u_l;
distinctness forces i != j, k != l, while injectivity of each permutation
forces i != k, j != l. So v is fixed by
    u_i u_k^{-1} u_l u_j^{-1}.
This word is nontrivial: in the cyclic order (i,k,l,j) neighboring indices
differ; if all indices are nonzero it is freely reduced; removing one u_0 = 1
joins letters of the same sign and leaves a nonempty reduced word; two zero
indices can only occur in opposite positions (remaining two letters of the
same sign); three zero indices are impossible. So every possible overlap
gives v fixed by a nonidentity word from a finite list. The union of the
corresponding fixed sets, plus the finite list for repeated columns, contains
every bad row; (5.3) gives b(V_k) = o(n_k). QED

For later use, the sequence of Proposition 6.1 eventually satisfies
    alpha n_k >= 1,   100 b(V_k) <= alpha n_k.                    (6.4)

==========================================================================
PART 7. THE PLANAR WORD LEMMA
==========================================================================

Let H be a group generated by a finite alphabet S, let U be a disjoint finite
alphabet, and put L = H * F(U). Words are written over S^{+-1} cup U^{+-1}. An
occurrence of a letter of U^{+-1} is exterior. Between successive exterior
occurrences is an S-word whose value in H is the coefficient gap (for a
cyclic word this includes the gap from the last exterior occurrence to the
first).

A cyclic word is cyclically H-reduced if no two successive exterior
occurrences are inverse letters separated by a gap equal to 1 in H. An
interval from one exterior occurrence through another matches a relator
interval if their signed exterior letters agree in order and all intervening
coefficient gaps have equal values in H, using no relator position more than
once. A full cyclic match means: after choosing cyclic start positions, the
complete signed exterior lists agree and all corresponding gaps, including
the closing gap, agree in H.

LEMMA 7.1 (planar word lemma). Let H be generated by finite S, U disjoint
finite, L = H * F(U). Let R be a family of words in L such that each r in R
has m(r) >= 7 exterior occurrences, all positive, with pairwise distinct
underlying generators; distinct relators share at most one generator from U.
Suppose the natural map H -> D := L / <> is injective. If a cyclically
H-reduced word W has an exterior occurrence and represents 1 in D, then at
least one of:
   (1) W has a full cyclic match with a relator or its inverse;
   (2) W has two intervals, disjoint in their exterior occurrences, each
       matching an interval of a cyclic relator or its inverse with at least
       m(r) - 3 exterior occurrences (r being the matched relator).

(The two intervals in (2) need not come from different relators. Matching
means equality in H of every gap strictly between the first and last matched
exterior letters; no bound on lengths of the spelling S-words is asserted.)

Proof. Preliminaries. Choose an expression for W in L as a product of
conjugates of relators from R^{+-1} using the least possible number N. A
cyclically H-reduced word with an exterior occurrence is nontrivial in L
(free-product reduction), so N > 0.

A finite filling over an arbitrary coefficient group. Give H the
presentation on S with all words trivial in H as relations. An equality in
this presentation uses finitely many relations (a product of finitely many
conjugates), so the chosen expression for W is witnessed by a finite set of
true H-relations. Let K_H be a finite presentation complex for these, and
wedge it with one circle per u in U; the result K has a natural map
pi_1(K) -> L (not assumed injective).

Realize the expression by a map from a sphere with N+1 open disks removed to
K. Let O be the distinguished boundary disk and B_1, ..., B_N the others,
all read with the disk orientation of the oriented sphere. The boundary of O
reads W^{-1}; 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; the remaining boundary reads the equality in L, filled by
the finitely many H-relations and free cancellations. Conversely, cutting any
such mapped punctured sphere along spokes writes W as a product of N
conjugates. Make everything piecewise linear (mapping cylinders and disks,
triangulated). 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 relations its equality uses). Minimality always concerns N in the actual
group L, not a larger finitely presented approximation.

Tracks and connectedness. For each u in U choose a point q_u in the interior
of its circle edge, avoiding the images of all vertices of a subdivision. Near
q_u the target is an interval; its inverse image is a union of line segments
across triangles joined in pairs across sides: 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
q_u. The two endpoints of an arc have opposite crossing signs (coorientation
plus the fact that all disk-boundary orientations are opposite the surface
boundary orientations).

Regard the disks as vertices and the arcs as edges of an embedded graph G on
the sphere; keep closed tracks as part of the map but not as edges of G.
Claim G is connected. Otherwise take a component C not containing O and a
small closed regular neighborhood of its disks and arcs, disjoint from all
other disks and tracks. Select the boundary curve gamma facing the component
containing O. The disk side away from O contains C and at least one inner
disk. The image of gamma avoids every q_u; cutting the exterior circles at the
q_u leaves a space retracting to K_H, so (after a basepoint change) the class
of gamma is an element of H inside L. Capping the relator holes on the far
side in a presentation space for D makes gamma trivial in D; injectivity
H -> D makes it trivial in H, hence in L. Replace that disk side by a filling
using only true H-relations and free cancellations: at least one relator disk
disappears, contradicting minimality of N. So G is connected. (This neither
removes closed tracks nor assumes they bound disks.)

Inner loops and dipoles. No graph loop at an inner vertex: all exterior
letters on that disk have the same sign, but an arc pairs opposite signs. No
edge joins two copies of the same relator: such copies have opposite
orientations and meet the unique occurrence of the same exterior generator u;
based at q_u, the positive boundary is s T p and the negative one p^{-1}
T^{-1} s^{-1}, which are inverse loops with the constant joining track
inserting no coefficient, so a small neighborhood has null boundary in L and
its interior can be replaced, removing two relator disks -- contradiction.
Copies of different relators share at most one exterior generator used once on
each, so at most one joining edge: between distinct inner vertices there is at
most one edge, and an inner vertex for 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 is a union of disks whose
boundary curves follow the face walks of G (even with repeats). Collapse the
exterior circles to the basepoint and take values in H; each track becomes
constant and each sector between successive track endpoints contributes its
coefficient gap. The map on each complementary disk shows the ordered product
of its sector values is 1 in H. Closed tracks do not affect this.

No monogon faces: an inner loop is excluded, and a monogon at O pairs two
inverse exterior occurrences across a gap trivial in H, against cyclic
H-reduction. Any bigon meeting an inner vertex uses two edges to O (no
parallel inner-inner edges; a length-2 walk traversing one edge twice would
force degree 1, impossible since m(r) >= 7). Such an inner-outer bigon
matches consecutive exterior letters and their gap: the exterior signs match
because O is labelled W^{-1}, and following W along the outer sector follows
the inner relator; the face equation "inner gap times inverse outer gap = 1"
gives equality in H (not merely up to conjugacy).

Corner count. Give weight 0 to every corner at O and to every corner of a
bigon. For any other corner at an inner vertex give weight 1/3 if both
incident edges go to inner vertices, 1/2 if exactly one goes to O, 1 if both
go to O (occurrences counted with multiplicity along face walks). A face of
length l has total weight at most l - 2: equality for a bigon; for l >= 3 with
no O the total is l/3 <= l - 2; with exactly one O the two neighboring corners
weigh 1/2 and the rest 1/3, total l/3; with at least two O's there are at most
l - 2 inner corners of weight <= 1. (These cases include repeated face walks
and loops at O.)

Let E, F be the numbers of edges and faces of G and c(v) the corner weight at
inner vertex v. Summing over faces and using Euler's formula for the connected
sphere graph with N+1 vertices,
    sum_{v != O} (2 - c(v)) >= 2N - 2E + 2F = 2.                 (7.2)

Call 2 - c(v) the contribution of v. A vertex of degree m >= 7 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 bounding
a bigon costs 0; a gap with no edge to an inner vertex but not bounding a
bigon costs 1; a gap with h >= 1 inner edges costs 1/2 + (h-1)/3 + 1/2 =
1 + (h-1)/3. So every gap not bounding a bigon costs at least 1.

If every gap bounds a bigon, all edges at v go to O; successive edges at v are
successive at O in the opposite rotation and exhaust the rotation at O (else a
half-edge would interrupt a bigon), and connectedness leaves no other vertex.
The bigon equations then match every exterior occurrence of W with this
relator, including all cyclic gaps: conclusion (1).

Otherwise positivity forces exactly one gap not to bound a bigon, containing
at most three inner edges (two such gaps cost >= 2; a gap with h >= 4 inner
edges costs >= 2). The other gaps form one consecutive string of bigons
joining at least m - 3 edges to O, and the bigon equations give a matching
interval with at least m - 3 exterior occurrences; the contribution of this
vertex is at most 1.

Unless (1) already occurred, every positive vertex contributes at most 1, and
(7.2) forces at least two distinct positive vertices. Take a matching interval
from each: each exterior occurrence of W is the endpoint of exactly one arc,
so intervals from different inner vertices have disjoint exterior occurrences.
This is conclusion (2). QED

==========================================================================
PART 8. THE DETERMINISTIC RANK BOUND
==========================================================================

THEOREM 8.1 (rank). Let V and T be sets of cardinality n. For each t in T let
    r_t = x_{c(t,0)} x_{c(t,1)} ... x_{c(t,99)},  c(t,i) in V,
    D = < x_v (v in V) | r_t = 1 (t in T) >.
For T' subset T put N(T') = { c(t,i) : t in T', 0 <= i <= 99 }. Call a row t bad
if it repeats a column or shares at least two distinct columns with another
row; let b be the number of bad rows. Suppose
    0 < alpha < 1/200,  alpha n >= 1,  100 b <= alpha n,
and
    |N(T')| > 96 |T'|  whenever 1 <= |T'| <= alpha n.            (8.2)
Then rk(D) > alpha n / 100.

Proof. Suppose D has at most alpha n / 100 generators. Four steps.

Step 1: a minimal labelled graph. Give each edge an orientation and a label
x_v or x_v^{-1}; reading an edge backwards inverts its label; path labels are
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
    beta(Y) = |E(Y)| - |V(Y)| + 1 <= alpha n / 100
and surjective loop-label map to D, choose one with the fewest edges; write
beta = beta(Y). Changing basepoint conjugates the loop image and preserves
surjectivity. So Y has no vertex of degree 1 (pruning it and moving the
basepoint if needed would give a smaller admissible graph).

Decompose Y into arcs by splitting at the basepoint p and at every vertex of
degree >= 3; an arc is an edge path with distinct interior vertices of degree
2, different from p (endpoints may coincide). If Y is a point there are no
arcs; if Y is a circle then beta = 1 and marking p gives one arc. Otherwise
    sum_{v in V(Y)} (deg(v) - 2) = 2 beta - 2
bounds the number of vertices of degree >= 3 by 2 beta - 2; suppressing all
degree-2 vertices except possibly p leaves at most 2 beta - 1 vertices and at
most 3 beta - 2 edges. In every case the number of arcs is at most 3 beta.

Step 2: saturating the coefficient alphabet. Start with S subset V the set of
columns occurring in bad rows. Apply either rule whenever it adds a column:
  (i) if an arc has at most 30 occurrences of labels with index outside S, put
      every index on that arc into S;
  (ii) if a row has at least 10 occurrences with index in S, put all its
      columns into S.
This terminates. Each arc contributes at most 30 new columns and is used once,
so the initial set plus all arc additions total at most
    100 b + 30 (3 beta) <= alpha n + 90 alpha n / 100 < 2 alpha n.  (8.3)
Each nontrivial row addition contributes at most 90 new columns.

Put s = floor(alpha n) >= 1. If s rows were processed by rule (ii), let T'
be the first s of them; at that moment N(T') subset S and |S| <= 2 alpha n + 90 s <
96 s, because alpha n < s + 1 <= 2 s < 3 s gives 2 alpha n < 6 s. But (8.2)
gives |N(T')| > 96 s, contradiction. So fewer than s rows are processed and
    |S| <= 2 alpha n + 90 (s - 1) <= 92 alpha n < n.              (8.4)
Put U = V \ S, nonempty. At termination every arc has either no U-labelled
edge or more than 30. Every row not entirely in S is good and has at most 9
S-occurrences, hence at least 91 distinct positive U-letters, and distinct
such rows share at most one U-letter.

Let H = < x_s : s in S > be the actual subgroup of D these generate. Then
    D ~= ( H * F(x_u : u in U) ) / << r_t : r_t not entirely in S >>.  (8.5)
Indeed the group on the right maps to D (every defining relation of H and
every displayed row holds in D), and conversely its generators satisfy all
original rows (an omitted row is a true relation of H, every other row is
retained). So the maps are inverse on generators. In particular the
coefficient group in (8.5) embeds in the quotient; no finite presentation of
H is assumed.

Step 3: a long segment in a shortest loop. Call an occurrence of x_u^{+-1}
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 (P may be empty). It has no immediate
backtracks, hence traverses complete arcs; therefore its number of exterior
occurrences is either 0 or > 30.

The label of P is linearly H-reduced: two consecutive exterior occurrences
cannot be inverse letters separated by an S-word R trivial in H. Otherwise the
relevant portion is e R f with R over S-edges of value 1 in H. If f = e^{-1} as
oriented edges, the detour e R f has value 1 in D and deleting it shortens P
without changing its value. Otherwise slide the initial incidence of f
backwards along R to the terminal vertex of e (keeping vertex and edge counts
and connectivity; replacing each traversal of f by R^{-1} f preserves all
based-loop values since R = 1 in D); now e^{-1} and f leave the same vertex
with the same label, so fold them, removing one edge, keeping the graph
connected, not increasing rank, preserving loop labels -- a smaller admissible
graph, contradiction. So P is linearly H-reduced.

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

Cyclically H-reduce this word (cancel adjacent inverse exterior letters across
gaps trivial in H) to a cyclic word W. W still has an exterior occurrence;
otherwise the original word is conjugate in L to an element of H trivial in D,
forcing it trivial in L by the embedding of H. Passing to W disrupts P in at
most one place: if no cancellation occurs it is the appended letter x_j^{-1}
(the seam letter); if cancellation occurs the first cancellation must involve
that appended letter (by linear H-reduction of P), after which all later
cancellations join the two ends of the remaining exterior list of P. The
surviving exterior occurrences form a contiguous block, intervening gaps are
unchanged, and only the closing (seam) gap may change.

Apply Lemma 7.1 to (8.5) 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); a seam gap can be crossed by at most
one interval (crossing uses both adjacent exterior occurrences). Either way an
interval with at least 91 - 3 = 88 exterior occurrences survives intact in P.
If instead the lemma gives an entire cyclic relator, remove the seam letter
when present or cut at the seam gap, leaving at least 90 exterior occurrences
intact in P.

So we obtain a subpath Q of P, beginning and ending with exterior edges,
matching a consecutive portion of a cyclic row or its inverse and having at
least 88 exterior occurrences, with distinct exterior indices. Its intervening
S-words equal, in H, the corresponding row segments (lengths need not agree).
The matching row segment has at least 88 of the 100 letters; its complement
has length at most 12, and the inverse complementary word gives a word z in
the original generators with
    [z]_D = [lab(Q)]_D,   1 <= |z| <= 12.                        (8.6)
(If the complement is empty take z = x_j x_j^{-1}.)

Step 4: shortening the graph. Decompose Q by its arc traversals, allowing
partial traversals at the ends. Some traversal carries more than 30 exterior
edges of Q; otherwise no complete traversal could have exterior edges (by
saturation) and the two partial traversals contribute at most 60, too few.
In the chosen traversal let I run from its first exterior edge through its last,
inclusive. Then
    Q = Q_1 I Q_2,   l := |E(I)| >= 31,
where I has distinct interior vertices of degree 2, none equal to p.

The paths Q_1, Q_2 avoid the edges and 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 an edge of I (degree 2), but that edge is exterior, so its two
occurrences in Q would repeat an exterior index. Second, any path entering the
interior of I from outside must use its first or last edge, both exterior and
already occurring in I. These also rule out a second traversal of an edge of I
(when I is closed the same boundary incidences apply).

Attach a new path Z between the endpoints of Q with label z, using new
interior vertices and k = |z| <= 12 new edges; delete the edges and interior
vertices of I. The old endpoints of I remain connected by Q_1^{-1} Z Q_2^{-1},
which avoids everything deleted, so the graph stays connected. The inserted
path has k - 1 new interior vertices and the deleted segment l - 1; both edge
and vertex counts change by k - l, so the graph rank is unchanged, and the
basepoint survives (it is not interior to I).

By (8.6), [lab(Q_1^{-1} Z Q_2^{-1})]_D = [lab(I)]_D. Every reduced loop at p
in the old graph that uses an edge of I must traverse all of I, in one
direction (interior vertices have degree 2 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, so the loop-label map stays surjective.
The edge count dropped by at least 31 - 12 = 19, contradicting minimality of Y.
QED

COROLLARY 8.7 (asymptotic form). Suppose a sequence of length-100 row systems
satisfies (8.2) for a fixed 0 < alpha < 1/200, has sizes n -> infinity, and
has bad-row counts b = o(n). Then
    rk(D) > alpha n / 100  for all large n,
    liminf_{n} rk(D)/n >= alpha / 100.
Proof. Eventually alpha n >= 1 and 100 b <= alpha n, so Theorem 8.1 applies.
QED

==========================================================================
PART 9. THE MAIN THEOREM
==========================================================================

THEOREM 9.1. Put K = e^{96} 96^{99} / 95^{95}. Choose
    0 < alpha < 1/200,   K alpha^3 < 1/2,   eta = alpha / 100.
For the group Gamma and actions of Part 1,
    Cost(R_{Gamma on X})   >= 1 + eta,
    Cost(R_{Gamma on Y_M}) <= 1 + 99/M     (M > 100).
Hence choosing an integer M > max{100, 99/eta} yields two essentially free
p.m.p. actions of one finitely generated group with strictly different costs;
general fixed price is false.

Proof. Lemma 1.1 shows Gamma is finitely generated with J infinite. The
actions of Part 1 are essentially free and p.m.p., and conull restriction does
not change their costs.

Lower bound. Fix alpha as in the statement and set eta = alpha/100 > 0.
Proposition 6.1 gives exact finite right A-sets V_k, sizes n_k -> infinity,
vanishing fixed-point fractions (5.3), expansion (6.2), and b(V_k) = o(n_k).
For all large k, alpha n_k >= 1 and 100 b(V_k) <= alpha n_k, so by (6.4) the
row systems defining D_{V_k} satisfy every hypothesis of Theorem 8.1, giving
    rk(D_{V_k}) > eta n_k    for all large k.
By the transfer Proposition 5.2,
    delta_X >= limsup_k rk(D_{V_k})/n_k >= eta.
By deployment Proposition 4.11,
    Cost(R_{Gamma on X}) >= 1 + delta_X >= 1 + eta.

Upper bound. For each integer M > 100, Proposition 2.2 gives
    Cost(R_{Gamma on Y_M}) <= 1 + 99/M.
The Y_M-orbits are infinite (Gamma is infinite and acts freely), so
Corollary 4.0d gives
    1 <= Cost(R_{Gamma on Y_M}) <= 1 + 99/M,
and these costs tend to 1 as M -> infinity.

Finally pick an integer M > max{100, 99/eta}; then 1 + 99/M < 1 + eta, so the
two costs are strictly different. QED

==========================================================================
APPENDIX. HOW THE PARTS FIT
==========================================================================
- Part 1 fixes the group, the homomorphism chi, and both actions.
- Part 2 proves the cheap upper bound 1 + 99/M using the height spine.
- Part 3 states the three-step lower-bound plan.
- Part 4 (compression + deployment) turns a Gamma-graphing into factor edges
  and produces Cost(R_Gamma on X) >= 1 + delta_X.
- Part 5 (transfer) bounds delta_X below by rk(D_{V_k})/|V_k|.
- Part 6 (random models) supplies V_k with expansion and few bad rows.
- Part 7 (planar lemma) is the small-cancellation matching statement.
- Part 8 (rank bound) turns expansion into rk(D) > alpha n / 100.
- Part 9 assembles everything into the strict inequality of costs.

References (bibliographic pointers; not needed to follow the proof):
  Levitt, "On the cost of generating an equivalence relation" (1995).
  Gaboriau, "Cout des relations d'equivalence et des groupes" (2000).
  Arzhantseva-Ol'shanskii (1996); Kapovich-Schupp, math/0210307 (2002).
  Greendlinger, "Dehn's algorithm for the word problem" (1960).