Proof. Choose, in each factor, representatives for the cosets \(gJ\), with \(1\) representing \(J\). Consider formal strings \[r_1\cdots r_n j, \qquad j\in J,\] 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 \[N_p=\{x\in X:x(t^n)\geq p\text{ for every }n\in\mathbb Z\}, \qquad C_p=(\{x\in X:x(1)<p\}\cup N_p)\times\mathbb Z/M\mathbb Z.\] 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 \[z\longrightarrow zt^n\longrightarrow zt^nj \longrightarrow zt^njt^{-n}=zj,\] 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 4. 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 \[1+100p+\frac{99}{M}.\] 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 \[y=yu_0,\quad yu_1,\quad\ldots,\quad yu_{99}=z\] is connected by \(E\): at its \(i\)th 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 \[yw=yu_{99}a=za.\] 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 6.

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 \[M_{\mathrm{inf}} =A\cup\bigl(Z_{\mathrm{inf}}\setminus[A]_{\mathcal T}\bigr)\] meets every infinite \(\mathcal T\)-class for every marking. The displayed union is disjoint, and \[\mathbb E\lambda(M_{\mathrm{inf}}) =p\lambda(Z_{\mathrm{inf}}) +\int_{Z_{\mathrm{inf}}}(1-p)^{k_n(z)}\,d\lambda(z).\] 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 7, and put \[Y=[M]_{\mathcal S} \cup\{z:|[z]_{\mathcal S}|=\infty\}.\] 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 6 gives \[ \kappa(\mathcal S;Y)\leq\lambda(M). \tag{5}\]

Proof. Let \(\mathcal E\) be a finite-cost generating graphing of the relation \(\mathcal Q\). Apply Lemma 8 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 \[x\longmapsto \bigl((x(gh_c))_c\bigr)_{g\in A}\] 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 \[\theta(v,a)=x_v,\qquad \theta(v,b_i)=1, \qquad \theta(v,s^{-1})=\theta(vs^{-1},s)^{-1}\] 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 \[ \theta(v,gh)=\theta(v,g)\theta(vg,h). \tag{17}\] The word \(w=u_{99}a=ab_1ab_2\cdots ab_{99}a\) gives \[\theta(v,w)=x_vx_{vu_1}\cdots x_{vu_{99}}=1.\] Also \(\theta(v,b_i)=1\) at every source. The inverse rule and (17) therefore give \[ \theta(v,j)=1\qquad(v\in V,\ j\in J). \tag{18}\] 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 \[\varphi_\ell:L_\ell\longrightarrow L_\ell g_\ell, \qquad \varphi_\ell(x)=xg_\ell, \qquad g_\ell\in A,\] 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 \[\sum_{\ell\in I}(1+m_\ell) \mu(L_\ell\mathbin{\triangle}L'_\ell)<\epsilon.\] 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 \[ \sum_{\ell\in I}\mu(L'_\ell)\le C(\mathcal E)+\epsilon, \qquad \mu(P')\ge1-2\epsilon. \tag{19}\] 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 \[\xi_v=(z_{vg})_{g\in A}.\] 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 \[\rho_k(F):= \sum_{\substack{g,h\in F\\g\ne h}} \frac{|\{v\in V_k:vgh^{-1}=v\}|}{n_k},\] which tends to zero by (16). Consequently, for every measurable \(F\)-cylinder \(E\), \[ \left|\frac1{n_k}\sum_{v\in V_k} \Pr(\xi_v\in E)-\mu(E)\right|\le\rho_k(F). \tag{20}\] 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 \[\theta(vh,g_\ell^{-1}) =\theta(vhg_\ell^{-1},g_\ell)^{-1},\] 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, \[\operatorname{rk}(D_{V_k})\le \sum_{\ell\in I}\sum_{v\in V_k}\mathbf1_{L'_\ell}(\xi_v) +\sum_{v\in V_k}\mathbf1_{(P')^c}(\xi_v).\] Taking expectations, using (20), and then letting \(k\to\infty\) gives \[\limsup_k\frac{\operatorname{rk}(D_{V_k})}{n_k} \le\sum_{\ell\in I}\mu(L'_\ell)+1-\mu(P') \le C(\mathcal E)+3\epsilon.\] 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 \[b_i=a^{-1}u_{i-1}^{-1}u_i.\] 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 \[\frac{(96s)(96s-1)\cdots(96s-s+1)}{n(n-1)\cdots(n-s+1)} \le \left(\frac{96s}{n}\right)^s.\] Using independence of the 99 permutations assigned to \(u_1,\ldots,u_{99}\), followed by the bounds \(\binom nr\le(en/r)^r\), gives \[\begin{align*} \Pr\bigl(\exists T:\ |T|=s,\ |N(T)|\le96s\bigr) &\le\binom ns\binom n{95s} \left(\frac{96s}{n}\right)^{99s}\\ &\le\left[K\left(\frac{s}{n}\right)^3\right]^s. \end{align*}\] 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 \[\sum_{s=1}^{\min(R,\lfloor\alpha n\rfloor)} [K(s/n)^3]^s+\frac{q^{R+1}}{1-q}.\] 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\), \[\Pr(v_0\text{ is fixed by the word}) \le\sum_{t=1}^L\frac{t}{n-t+1} \le\frac{L(L+1)}{2(n-L+1)}.\] 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 \[\mathbb E\frac{|\operatorname{Fix}_{V}(g_j)|}{n_k} \le\frac1{4k^2}\qquad(1\le j\le k).\] 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 \[vu_i=yu_k,\qquad vu_j=yu_l.\] 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 \[u_i u_k^{-1}u_lu_j^{-1}.\] 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)\). ◻