betaFeedback

WorksMathematics

A counterexample to the subgraphings approximate the cost problem

Abstract

We prove that for every k≥2k\ge 2, the free group Fk\mathbb{F}_k on kk generators admits a finite generating set SS such that the Schreier graphing of the Bernoulli action of Fk\mathbb{F}_k with respect to SS does not admit spanning subgraphings that would approximate the cost of the action. In particular, this gives an example of a graphing that spans a treeable countable pmp equivalence relation, but does not admit a spanning subtreeing.

Introduction

An important numerical invariant of probability measure preserving countable Borel equivalence relations (pmp CBERs), introduced by Levitt [17] and subsequently developed into a far-reaching theory by Gaboriau [9, 8] (see, e.g., [2, 7, 13, 16, 15, 22]), is the notion of cost. On a high-level, cost measures how difficult it is to realize a given pmp CBER as connectivity components of a measurable graph relation (also known as graphing) in terms of its average degree.

The main motivation for our work stems from problems about global behavior of cost. For instance, how difficult it is to compute a cost of a given pmp action, or is it possible to approximate the cost of a countable pmp equivalence relation induced by a graphing by erasing edges. In this paper, we describe an example that gives a negative answer to the latter problem, that we will refer to as the subgraphings approximate the cost problem, and that has been formally stated in [10 Subgraphings vs Cost Problem, Question 2.68] and [1 Question 46]. Before stating our main result, we formally introduce the main concepts.

A graphing on a standard probability space (X,μ)(X,\mu) is a triplet G=(X,E,μ)\mathcal{G}=(X,E,\mu), where (X,E)(X,E) is a locally countable Borel graph on XX that satisfies the mass transport principle with respect to μ\mu, see [18 Chapter 18]. We write E(G)E(\mathcal{G}) for the connectedness equivalence relation on (X,μ)(X,\mu) induced by G\mathcal{G}, it follows that E(G)E(\mathcal{G}) is a pmp CBER. Given a pmp CBER E\mathcal{E} on a standard probability space (X,μ)(X,\mu), we define Span⁡(E)\operatorname{Span}(\mathcal{E}) to be the set of all graphings G\mathcal{G} on (X,μ)(X,\mu) such that E=E(G)\mathcal{E}=E(\mathcal{G}) up to μ\mu-null sets. In the special case, when E=E(G)\mathcal{E}=E(\mathcal{G}), we write simply Span⁡(G)\operatorname{Span}(\mathcal{G}) instead of Span⁡(E(G))\operatorname{Span}(E(\mathcal{G})).

A prominent family of graphings are the so-called Schreier graphings of pmp actions: we say that an action Γ↷σ(X,μ)\Gamma\overset{\sigma}{\curvearrowright}(X,\mu) of a countable group Γ\Gamma on a standard probability space (X,μ)(X,\mu) is a probability measure preserving (pmp) action if μ(γ⋅A)=μ(A)\mu(\gamma\cdot A)=\mu(A) for every measurable set A⊆XA\subseteq X and γ∈Γ\gamma\in\Gamma, where γ⋅A={γ⋅x:x∈A}\gamma\cdot A=\{\gamma\cdot x:x\in A\}. Additionally, we say that the action σ\sigma is (almost everywhere) free if the stabilizer of μ\mu-almost every point x∈Xx\in X is trivial.

We denote by E(σ)\mathcal{E}(\sigma) the orbit equivalence relation induced by σ\sigma, it follows that E(σ)\mathcal{E}(\sigma) is a pmp CBER. We set Span⁡(σ)=Span⁡(E(σ))\operatorname{Span}(\sigma)=\operatorname{Span}(\mathcal{E}(\sigma)).

For a free pmp action Γ↷σ(X,μ)\Gamma\curvearrowright_\sigma(X,\mu) and a finite set S⊆Γ∖{1Γ}S \subseteq\Gamma\setminus\{1_\Gamma\}, we define

Sch⁡(σ,S)=(X,{{x,γ⋅x}:x∈X, γ∈S},μ)\operatorname{Sch}(\sigma,S)=\left(X,\{\{x,\gamma\cdot x\}:x\in X,\ \gamma\in S\},\mu\right)

to be the Schreier graphing of σ\sigma with respect to SS. For this definition, we do not require SS to be a generating set. Observe that SS generates Γ\Gamma if and only if Sch⁡(σ,S)∈Span⁡(σ)\operatorname{Sch}(\sigma,S)\in\operatorname{Span}(\sigma).

For a graphing G\mathcal{G}, we define its cost as

Cost⁡(G)=12∫Xdeg⁡G(x) dμ.\operatorname{Cost}(\mathcal{G})=\frac{1}{2}\int_X\deg_{\mathcal{G}}(x)\,\mathrm{d}\mu.

A cost of a pmp CBER E\mathcal{E} is then defined as

Cost⁡(E)=inf⁡G∈Span⁡(E)Cost⁡(G),\operatorname{Cost}(\mathcal{E})=\inf_{\mathcal{G}\in\operatorname{Span}(\mathcal{E})}\operatorname{Cost}(\mathcal{G}),

and a cost of an action σ\sigma is defined as Cost⁡(σ)=Cost⁡(E(σ))\operatorname{Cost}(\sigma)=\operatorname{Cost}(\mathcal{E}(\sigma)). Given a graphing G\mathcal{G}, we define the subgraphing cost

Sub-Cost⁡(G)=inf⁡{Cost⁡(H):H∈Span⁡(G) & H⊆G}.\operatorname{Sub\text{-}Cost}(\mathcal{G})=\inf\{\operatorname{Cost}(\mathcal{H}):\mathcal{H}\in\operatorname{Span}(\mathcal{G})\ \&\ \mathcal{H}\subseteq\mathcal{G}\}.

Note that we always have Cost⁡(E(G))≤Sub-Cost⁡(G)\operatorname{Cost}(\mathcal{E}(\mathcal{G}))\leq\operatorname{Sub\text{-}Cost}(\mathcal{G}), and the subgraphings approximate the cost problem asks whether we have equality for all graphings G\mathcal{G}. If SS generate Γ\Gamma, then we write simply Sub-Cost⁡(σ,S)\operatorname{Sub\text{-}Cost}(\sigma,S) instead of Sub-Cost⁡(Sch⁡(σ,S))\operatorname{Sub\text{-}Cost}(\operatorname{Sch}(\sigma,S)).

The main focus of this paper is on the free group

Fk=⟨α1,…,αk⟩\mathbb{F}_k=\langle\alpha_1,\ldots,\alpha_k\rangle

that is freely generated by α1,…,αk\alpha_1,\ldots,\alpha_k for k≥2k\geq2. It follows from Gaboriau’s theorem about treeings [8 Théorème IV.1] that Cost⁡(σ)=k\operatorname{Cost}(\sigma)=k for any free pmp action Fk↷σ(X,μ)\mathbb{F}_k\curvearrowright_\sigma(X,\mu). Our main result is the following.

Theorem 1. Let k≥2k\geq2, σ\sigma be the Bernoulli action Fk↷σ([0,1]Fk,λ⊗Fk)\mathbb{F}_k\curvearrowright_\sigma([0,1]^{\mathbb{F}_k},\lambda^{\otimes\mathbb{F}_k}) and ϵ>0\epsilon>0. Then there is a finite set of generators SϵS_\epsilon of size k+1k+1 such that

Sub-Cost⁡(σ,Sϵ)≥k+1−ϵ.\operatorname{Sub\text{-}Cost}(\sigma,S_\epsilon)\geq k+1-\epsilon.

In particular, if ϵ<1\epsilon<1, then Sub-Cost⁡(σ,Sϵ)>Cost⁡(σ)=k\operatorname{Sub\text{-}Cost}(\sigma,S_\epsilon)>\operatorname{Cost}(\sigma)=k.

Let E\mathcal{E} be a pmp CBER on a standard probability space (X,μ)(X,\mu). We say that E\mathcal{E} is treeable, if there is an acyclic graphing G\mathcal{G} on (X,μ)(X,\mu) such that E=E(G)\mathcal{E}=\mathcal{E}(\mathcal{G}) holds μ\mu almost everywhere. The following is a direct consequence of Theorem 1 and [8 Théorème IV.1].

Corollary 1. There exists a graphing G\mathcal{G} such that E(G)\mathcal{E}(\mathcal{G}) is treeable and there is no H\mathcal{H} that is an almost everywhere acyclic subgraphing of G\mathcal{G} such that E(G)=E(H)\mathcal{E}(\mathcal{G})=\mathcal{E}(\mathcal{H}).

The following is a direct consequence of the case k=2k=2 of Theorem 1 (see § 6).

Corollary 2. Assume that Λ\Lambda is a finitely generated group. Let Γ=F2∗Λ\Gamma=\mathbb{F}_2*\Lambda, σ\sigma be the Bernoulli action Γ↷σ([0,1]Γ,λ⊗Γ)\Gamma\curvearrowright_\sigma([0,1]^\Gamma,\lambda^{\otimes\Gamma}) and ϵ>0\epsilon>0. Then there is a graphing Gϵ∈Span⁡(σ)\mathcal{G}_\epsilon\in\operatorname{Span}(\sigma) such that

Sub-Cost⁡(Gϵ)≥Cost⁡(σ)+1−ϵ.\operatorname{Sub\text{-}Cost}(\mathcal{G}_\epsilon)\geq\operatorname{Cost}(\sigma)+1-\epsilon.

Remark 1. In contrast, recently Recke and the second author have shown [11 Theorem 1.5] that Schreier graphs of the Bernoulli actions of co-compact lattices in connected higher rank semisimple real Lie groups with property (T) have the sparse unique infinite cluster property for any finite set of generators. The same conclusion can be derived for Schreier graphs of the Bernoulli actions of products of free groups with at least two factors on the same number of generators Fd×⋯×Fd\mathbb{F}_d \times\cdots\times\mathbb{F}_d, for d≥2d \ge2, by a combination of [6 Theorem 1] and [11 Corollary 9.4]. It follows that the subgraphings approximate the cost problem has a positive answer for these Schreier graphings.

Another application concerns the so-called free uniform spanning forest (FUSF). Let G=(V,E)G=(V,E) be an infinite connected locally finite graph, and let (Vn)n∈N(V_n)_{n \in\mathbb{N}} be an increasing exhaustion of VV by finite sets such that each induced subgraph Gn=G↾VnG_n=G \mathbin{\upharpoonright} V_n is connected. Let μn\mu_n be the law of a uniformly chosen spanning tree of GnG_n, viewed as a probability measure on {0,1}E\{0,1\}^{E} by declaring all edges outside GnG_n absent. The measures μn\mu_n converge weakly to a probability measure F~G\widetilde{\mathsf F}_G on {0,1}E\{0,1\}^{E}. This limit is independent of the exhaustion and is invariant under every automorphism of GG; see [4 Section 5], and it is called the FUSF of GG.

Pete and Timár [21 Theorem 1.2] showed that connectivity of the FUSF can depend on the generating set. They constructed a virtually free group with two finite generating sets such that the FUSF of one Cayley graph is connected almost surely, whereas that of the other has infinitely many components almost surely. This answered negatively Question 10.50 of [19]. Combining our main result with the recent theorem that the FUSF is a factor of iid [20 Theorem 1.1], we obtain the analogous result for free groups.

Theorem 2. Let k≥2k \ge2. Then there are two generating sets S0S_0 and S1S_1 of Fk\mathbb{F}_k such that if we write Gi=Cay⁡(Fk,Si)G_i=\operatorname{Cay}(\mathbb{F}_k,S_i) for i∈{0,1}i \in\{0,1\}, then F~G0\widetilde{\mathsf F}_{G_0} is connected almost surely and F~G1\widetilde{\mathsf F}_{G_1} has infinitely many connectivity components almost surely.

Proof. Let S0={α1,…,αk}S_0=\{\alpha_1,\ldots,\alpha_k\} be the standard generating set for Fk\mathbb{F}_k. It follows that F~G0\widetilde{\mathsf F}_{G_0} is concentrated on the standard Cayley graph of Fk\mathbb{F}_k, hence it is connected almost surely.

Let S1=SϵS_1=S_\epsilon be the generating set from Theorem 1 for 0<ϵ<10<\epsilon<1. By [20 Theorem 1.1], F~G1\widetilde{\mathsf F}_{G_1} is a Fk\mathbb{F}_k-invariant factor of iid. Equivalently, it can be realized as a measurable acyclic subgraphing T⊆Sch⁡(σ,S)\mathcal{T}\subseteq\operatorname{Sch}(\sigma,S) on the Bernoulli probability space. As T⊆Sch⁡(σ,S1)\mathcal{T}\subseteq\operatorname{Sch}(\sigma,S_1), we have that T⊈Span⁡(σ)\mathcal{T}\not\subseteq\operatorname{Span}(\sigma) as otherwise we have

Cost⁡(T)=Cost⁡(σ)=k\operatorname{Cost}(\mathcal{T})=\operatorname{Cost}(\sigma)=k

by Gaboriau’s theorem [8 Théorème IV.1]. In particular, F~G1\widetilde{\mathsf F}_{G_1} is disconnected with positive probability, hence almost surely as it is ergodic. Finally, by [12 Theorem 1.3], the FUSF of a Cayley graph is almost surely either connected or has infinitely many connected components. □

Outline of the proof of Theorem 1

We only focus on the case k=2k=2, as the general case follows directly from Corollary 2. Write F2=⟨a,b⟩\mathbb{F}_2=\langle a,b\rangle. Given ϵ>0\epsilon>0, the generating set SϵS_\epsilon is of the form {a,wϵ,bwϵ}\{a,w_\epsilon,bw_\epsilon\} for some reduced word w=wϵw=w_\epsilon with the following combinatorial properties: (A) large collections of prefixes of ww freely generate a free subgroup of F2\mathrm{F}_2 (see, Lemma 3),

(B) for any fixed B⊆F2∖{1F2}B \subseteq\mathrm{F}_2 \setminus\{1_{\mathrm{F}_2}\}, if we consider the graph HB\mathcal{H}_B on F2\mathrm{F}_2 with edge set

{{γ,aγ}:γ∈F2}∪{{γ,wγ}:γ∈F2}∪{{γ,bγ}:γ∈B},\{\{\gamma,a\gamma\}:\gamma\in\mathrm{F}_2\}\cup\{\{\gamma,w\gamma\}:\gamma\in\mathrm{F}_2\}\cup\{\{\gamma,b\gamma\}:\gamma\in B\},

then any path from 1F21_{\mathrm{F}_2} to bb in HB\mathcal{H}_B must pass through a ww-edge {γ,wγ}\{\gamma,w\gamma\} with the property that almost all (depending on ε\varepsilon) of its prefixes that are followed by letter bb belong to BB (see, Lemma 2).

The word ww is constructed by a simple randomized process, namely, it is of the form

w=dℓdℓ−1…d1,w=d_{\ell}d_{\ell-1}\ldots d_1,

where the parameter ℓ→∞\ell\to\infty as ε→0\varepsilon\to0 and di∈{a,b}d_i\in\{a,b\} are picked uniformly at random.

The above properties are used to derive a result that goes seemingly in the opposite direction than Theorem 1. To be more precise, we show that if Zb⊆[0,1]F2Z_b\subseteq[0,1]^{\mathrm{F}_2} is a measurable set such that

HZb=Sch⁡(σ,{a,w})∪{{x,b⋅x}:x∈Zb}∈Span⁡(σ),\mathcal{H}_{Z_b}=\operatorname{Sch}(\sigma,\{a,w\})\cup\{\{x,b\cdot x\}:x\in Z_b\}\in\operatorname{Span}(\sigma),

then λ⊗F2(Zb)→1\lambda^{\otimes\mathrm{F}_2}(Z_b)\to1 as the parameter ℓ\ell defining the length of ww goes to infinity (see, Theorem 4).

On a high-level, the argument uses (B) to gradually enlarge ZbZ_b by “filling in” the small amount of missing bb-edges in selected ww-edges that eventually produces a positive fraction of ww-edges whose prefixes are completely contained in ZbZ_b (see, Lemma 4). If ZbZ_b were small, then this concentration of ZbZ_b on a positive fraction of ww-edges would contradict an entropy inequality for a restriction of the Bernoulli action to a free subgroup of F2\mathrm{F}_2 (see, § 4). Here, it is important that the rank of this free group goes to ∞\infty as ℓ→∞\ell\to\infty, which is where (A) is used.

Finally, Theorem 1 is a direct corollary of Theorem 4. For example, a lower bound on the measure of bwbw-edges that are used in a spanning subgraphing G⊆Sch⁡(σ,{a,w,bw})\mathcal{G}\subseteq\operatorname{Sch}(\sigma,\{a,w,bw\}) can be drawn by taking a union with Sch⁡(σ,{a,w})\operatorname{Sch}(\sigma,\{a,w\}) and replacing every bwbw-edge {x,bw⋅x}\{x,bw\cdot x\} in G\mathcal{G} by a bb-edge {w⋅x,b⋅(w⋅x)}\{w\cdot x,b\cdot(w\cdot x)\}. This preserves connectedness, and the measure of bb-edges remains the same as the measure of bwbw-edges in G\mathcal{G}. The lower bound is then derived from Theorem 4, see § 6. A similar argument can be applied to aa and ww.

AI Disclosure

An interesting candidate for a counterexample to the subgraphings approximate the cost problem was suggested by GPT-5.6 in August 2026, upon the authors’ inquiry about a construction related to the question of the complexity of finite cost (see § 7). While neither the authors nor GPT 5.6 were able to prove anything about the group, the newly released GPT 6 showed, interestingly, that the candidate either fails the fixed price conjecture or is a counterexample to the subgraphings approximate the cost problem. Then, upon seeing the new OpenAI counterexample to the fixed price conjecture we used extensively the LLM to find a group (it was Z∗(Z/3Z)\mathbb{Z}*(\mathbb{Z}/3\mathbb{Z})) that satisfies the above theorem. After several1 rounds of drastic simplifications of the arguments, it turned out that the same result is true for the free group, which is what we decided to include. LLM was not used in the actual writing of this text, only in corrections.

Acknowledgments:

We are very grateful to Márton Borbényi, Edward Hou, Gábor Pete for the conversations and suggestions on the topic of the paper.

JG was supported by an ERC CZ grant LL2608 funded by the Czech Ministry of Education, Youth and Sports from the ERC CZ Program. BB and VZ were supported by the ERC COG grant Define (No. 101231345). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency.

Positive words in F2_2

As discussed in § 1.1, the generating set in Theorem 1 is always of the form {a,w,bw}\{a,w,bw\} for some reduced word ww; now we describe how to construct them. We use a simple random construction ensuring that overlaps between the word and its translated copies are small. This implies, among other things, that there is a large collection of prefixes of ww that freely generate a free subgroup of F2F_2.

Definition 1 (Positive words in F2F_2). Let ℓ\ell and mm be positive integers. An (ℓ,m)(\ell,m)-positive word is a word ww of the form

dℓdℓ−1⋯d1(1)d_{\ell}d_{\ell-1}\cdots d_1 \tag*{(1)}

where di∈{a,b}d_i \in\{a,b\} for every 1≤i≤ℓ1 \le i \le\ell, such that

(a) the collection

{(di,…,di+m−1):1≤i≤ℓ}(2)\{(d_i,\ldots,d_{i+m-1}):1\le i\le\ell\} \tag*{(2)}

consists of pairwise distinct sequences, where the indices are always understood  mod ℓ\bmod\ell,

(b) we have

ℓ/3≤∣{i∈{1,…,ℓ}:di=a}∣≤2ℓ/3.(3)\ell/3\le\lvert\{i\in\{1,\ldots,\ell\}:d_i=a\}\rvert\le2\ell/3. \tag*{(3)}

Given d=(d1,…,dℓ)∈{a,b}ℓd=(d_1,\ldots,d_\ell)\in\{a,b\}^{\ell}, we write wdw_d for the reduced word given by (1). We start by showing that a uniform sequence in {a,b}ℓ\{a,b\}^{\ell} defines a positive word with high probability. Throughout the paper we use the natural logarithm.

Lemma 1. Let ℓ\ell and mm be positive integers such that 5log⁡(ℓ)≤m≤ℓ/25\log(\ell)\le m\le\ell/2, and endow {a,b}ℓ\{a,b\}^{\ell} with the uniform measure. Then

P(wd is an (ℓ,m)-positive word)≥1−10/ℓ.\mathbb{P}(w_d\text{ is an }(\ell,m)\text{-positive word})\ge1-10/\ell.

Proof. Let dd be sampled uniformly from {a,b}ℓ\{a,b\}^{\ell} and fix 1≤i≠j≤ℓ1\le i\ne j\le\ell. The probability that (di,…,di+m−1)=(dj,…,dj+m−1)(d_i,\ldots,d_{i+m-1})=(d_j,\ldots,d_{j+m-1}) is equal to 2−m2^{-m}. Indeed, we may without loss of generality assume that i=1i=1 and 2≤j≤⌊ℓ/2⌋+2\le j\le\lfloor\ell/2\rfloor+

  1. Then it follows that the choices of d1,d2,…,dk∈{a,b}d_1,d_2,\ldots,d_k \in\{a,b\} fully determine (dj,…,dj+m−1)(d_j,\ldots,d_{j+m-1}), where k=min⁡{m,j−1}k=\min\{m,j-1\}, as m≤ℓ/2m\leq\ell/2. The union bound gives

P(wd fails condition (a))≤2−m(ℓ2)≤ℓ−5log⁡(2)ℓ22≤ℓ−3.4ℓ22≤1ℓ\mathbb{P}(w_d\text{ fails condition (a)}) \leq2^{-m}\binom{\ell}{2} \leq\ell^{-5\log(2)}\frac{\ell^2}{2} \leq\ell^{-3.4}\frac{\ell^2}{2} \leq\frac{1}{\ell}

which gives an upper bound on the probability that (a) fails. To bound the probability of failure in (b), we apply Chebyshev’s inequality. Define the random variable Na=∣{i∈{1,…,ℓ}:di=a}∣N_a = |\{i\in\{1,\ldots,\ell\}:d_i=a\}| and note that E[Na]=ℓ/2\mathbb{E}[N_a]=\ell/2 and Var⁡(Na)=ℓ/4\operatorname{Var}(N_a)=\ell/4. Then we have

P(∣Na−ℓ2∣≥ℓ6)≤9ℓ,\mathbb{P}\left(\left|N_a-\frac{\ell}{2}\right|\geq\frac{\ell}{6}\right)\leq\frac{9}{\ell},

and the claim follows. □

Let wdw_d be an (ℓ,m)(\ell,m)-positive word for some d∈{a,b}ℓd\in\{a,b\}^{\ell}. Set c1=1F2c_1=1_{F_2} and define

ci=di−1⋯d1c_i=d_{i-1}\cdots d_1

for every 2≤i≤ℓ2\leq i\leq\ell. For u∈{a,b}u\in\{a,b\}, let

Iu={i∈{1,…,ℓ}:di=u}.I_u=\{i\in\{1,\ldots,\ell\}:d_i=u\}.

The following is the main combinatorial observation. We state it for the left-shift action of F2F_2 on itself, but later we will apply it to the (orbits of the) Bernoulli shift of F2F_2.

We fix some terminology that is used throughout. Recall that a path in a graph is an injective sequence of vertices, where consecutive vertices form an edge.

Lemma 2. Let ℓ\ell and mm be positive integers, wdw_d be an (ℓ,m)(\ell,m)-positive word given by some d∈{a,b}ℓd\in\{a,b\}^{\ell}, and B⊆F2∖{1F2}B\subseteq F_2\setminus\{1_{F_2}\}. Define a graph HBH_B on F2F_2 with an edge set

E(HB)={{γ,aγ}:γ∈F2}∪{{γ,wdγ}:γ∈F2}∪{{γ,bγ}:γ∈B}E(H_B)=\{\{\gamma,a\gamma\}:\gamma\in F_2\}\cup\{\{\gamma,w_d\gamma\}:\gamma\in F_2\}\cup\{\{\gamma,b\gamma\}:\gamma\in B\}

and suppose that 1F2=γ1,…,γk=b1_{F_2}=\gamma_1,\ldots,\gamma_k=b is a path in HBH_B. Then there are 1≤i≤k−11\leq i\leq k-1 and η∈F2\eta\in F_2 such that

(γi,γi+1)=(η,wdη) or (γi,γi+1)=(wdη,η)(\gamma_i,\gamma_{i+1})=(\eta,w_d\eta)\text{ or }(\gamma_i,\gamma_{i+1})=(w_d\eta,\eta)

and

1≤∣{j∈Ib:cjη∉B}∣≤2m.(4)1\leq|\{j\in I_b:c_j\eta\notin B\}|\leq2m. \tag*{(4)}

Proof. Let Cay⁡(F2)\operatorname{Cay}(F_2) be the left Cayley graph of F2F_2 with respect to the generating set {a,b}\{a,b\}. We start with the following observation.

Claim 1. Let η,η′∈F2\eta,\eta'\in F_2 and suppose that

∣{j∈Ib:∃j′∈Ib (cjη,bcjη)=(cj′η′,bcj′η′)}∣>m.(5)|\{j\in I_b:\exists j'\in I_b\ (c_j\eta,bc_j\eta)=(c_{j'}\eta',bc_{j'}\eta')\}|>m. \tag*{(5)}

Then η=η′\eta=\eta'.

Proof. Let j0∈Ibj_0\in I_b be minimal such that (cj0η,bcj0η)=(cj0′η′,bcj0′η′)(c_{j_0}\eta,bc_{j_0}\eta)=(c_{j'_0}\eta',bc_{j'_0}\eta') for some j0′∈Ibj'_0\in I_b. By (1), we have that if j>j0j>j_0 is such that j∈Ibj\in I_b and (cjη,bcjη)=(cj′η′,bcj′η′)(c_j\eta,bc_j\eta)=(c_{j'}\eta',bc_{j'}\eta') for some j′∈Ibj'\in I_b, then j′−j0′=j−j0j'-j'_0=j-j_0 and

(dj0+1,…,dj)=(dj0′+1,…,dj0′+j−j0).(d_{j_0+1},\ldots,d_j)=(d_{j'_0+1},\ldots,d_{j'_0+j-j_0}).

By (5), there is j1∈Ibj_1 \in I_b such that ∣{j∈Ib:j0≤j≤j1}∣>m|\{j \in I_b : j_0 \le j \le j_1\}| > m. This can only happen, by (2), if j0=j0′j_0 = j'_0. Consequently cj0η=cj0η′c_{j_0}\eta= c_{j_0}\eta', which implies that η=η′\eta= \eta' as desired. □

We consider a quotient graph of Cay⁡(F2)\operatorname{Cay}(\mathbb{F}_2) that is obtained by gluing together vertices of the form {γ,aγ}\{\gamma, a\gamma\} for every γ∈F2\gamma\in\mathbb{F}_2 and {γ,bγ}\{\gamma, b\gamma\} for γ∈B\gamma\in B. Formally, let VV be the set of equivalence classes of the equivalence relation on F2\mathbb{F}_2 that is generated by the relation

{{γ,aγ}:γ∈F2}∪{{γ,bγ}:γ∈B}.\{\{\gamma, a\gamma\} : \gamma\in\mathbb{F}_2\} \cup\{\{\gamma, b\gamma\} : \gamma\in B\}.

For γ∈F2\gamma\in\mathbb{F}_2, we denote by [γ][\gamma] the corresponding element in VV that contains γ\gamma. We define the edge relation as

R={{[γ],[bγ]}:γ∉B},R = \{\{[\gamma], [b\gamma]\} : \gamma\notin B\},

and think of each edge {v,w}∈R\{v,w\} \in R to have a label of the form {γ,bγ}\{\gamma,b\gamma\}, where {[γ],[bγ]}={v,w}\{[\gamma],[b\gamma]\} = \{v,w\}.

For η∈F2\eta\in\mathbb{F}_2, define TηT_\eta to be an increasing enumeration of the set

{j∈Ib:cjη∉B}.\{j \in I_b : c_j\eta\notin B\}.

We denote by dist⁡Q(−,−)\operatorname{dist}_Q(-,-) the graph distance in Q=(V,R)Q=(V,R).

Claim 2. The graph Q=(V,R)Q=(V,R) is acyclic, does not contain loops and the label of each edge is uniquely determined. Additionally, [η],[bcj1η],…,[bcj∣Tη∣η][\eta], [bc_{j_1}\eta], \ldots, [bc_{j_{|T_\eta|}}\eta], where Tη=(j1,…,j∣Tη∣)T_\eta=(j_1,\ldots,j_{|T_\eta|}) is a path in QQ that connects [η][\eta] and [wdη][w_d\eta] for every η∈F2\eta\in\mathbb{F}_2. In particular, dist⁡Q([η],[wdη])=∣Tη∣\operatorname{dist}_Q([\eta],[w_d\eta])=|T_\eta| for every η∈F2\eta\in\mathbb{F}_2.

Proof. The first assertion follows from the fact that Cay⁡(F2)\operatorname{Cay}(\mathbb{F}_2) is acyclic and QQ is a quotient of Cay⁡(F2)\operatorname{Cay}(\mathbb{F}_2) with the property that the restriction of Cay⁡(F2)\operatorname{Cay}(\mathbb{F}_2) to each [γ][\gamma], for γ∈F2\gamma\in\mathbb{F}_2, is connected. The additional parts follow directly from these properties of QQ and the definition. □

Given a path P=(a1,…,as)P=(a_1,\ldots,a_s) in QQ, we define Pr=(as,…,a1)P^r=(a_s,\ldots,a_1) to be the reverse of PP, and if Q=(b1,…,bt)Q=(b_1,\ldots,b_t) is another path in QQ such that b1=asb_1=a_s, then we define Q∘PQ\circ P to be the shortest path from a1a_1 to btb_t. Note that Q∘PQ\circ P is well defined by Claim 2, and that it can be equivalently defined as

Q∘P=(a1,…,as−s′(Q,P),bs′(Q,P)+2,…,bt),(6)Q \circ P = (a_1,\ldots,a_{s-s'(Q,P)},b_{s'(Q,P)+2},\ldots,b_t), \tag*{(6)}

where 0≤s′(Q,P)≤s−10 \le s'(Q,P) \le s-1 is maximal such that bj+1=as−jb_{j+1}=a_{s-j} for every 0≤j≤s′(Q,P)0 \le j \le s'(Q,P). In particular, ∣Q∘P∣=∣Q∣+∣P∣−2(s′(Q,P)+1)+1|Q\circ P|=|Q|+|P|-2(s'(Q,P)+1)+1.

Suppose for a contradiction that (4) does not hold for any 1≤i≤k−11 \le i \le k-1. This is equivalent to dist⁡Q([γi],[γi+1])\operatorname{dist}_Q([\gamma_i],[\gamma_{i+1}]) either being 0 or at least 2m+12m+1 for every 1≤i≤k−11 \le i \le k-1. We prove that there is an 1≤i0≤k1 \le i_0 \le k such that

dist⁡Q([1F2],[γi])≥2m+1,for every i0≤i≤k.(7)\operatorname{dist}_Q([1_{\mathbb{F}_2}],[\gamma_i]) \ge2m+1,\qquad\text{for every } i_0 \le i \le k. \tag*{(7)}

Once we have that, the proof is finished as 2m+1≤dist⁡Q([1F2],[γk])=dist⁡Q([1F2],[b])=12m+1 \le\operatorname{dist}_Q([1_{\mathbb{F}_2}],[\gamma_k])=\operatorname{dist}_Q([1_{\mathbb{F}_2}],[b])=1 contradicts the assumption that mm is a positive integer.

Define

J={i∈{1,…,k−1}:[γi]≠[γi+1]},J=\{i\in\{1,\ldots,k-1\}:[\gamma_i]\ne[\gamma_{i+1}]\},

and write J+J^+ for those indices i∈Ji\in J such that γi+1=wdγi\gamma_{i+1}=w_d\gamma_i. Set J−=J∖J+J^-=J\setminus J^+ and note that [γi]=[wdγi+1][\gamma_i]=[w_d\gamma_{i+1}] for every i∈J−i\in J^-. As [γk]=[b]≠[1F2][\gamma_k]=[b]\ne[1_{\mathbb{F}_2}], we have that J≠∅J\ne\varnothing. We show that setting i0=1+min⁡Ji_0=1+\min J works as required.

For i∈Ji \in J, define Pi=(v1i,…,vn(i)i)P_i=(v_1^i,\ldots,v_{n(i)}^i) to be the path in QQ that connects [γi][\gamma_i] and [γi+1][\gamma_{i+1}] from Claim 2. Note that by our assumption, we have that ∣Pi∣=n(i)≥2m+2|P_i|=n(i)\ge2m+2.

For i0≤i≤ki_0\le i\le k, define J(i)=max⁡{j∈J:j<i}J(i)=\max\{j\in J:j<i\} and set Qi=(w1i,…,wm(i)i)Q_i=(w_1^i,\ldots,w_{m(i)}^i) to be the shortest path in QQ from [γi][\gamma_i] to [1F2][1_{\mathbb{F}_2}]. Note that QiQ_i is uniquely determined by Claim 2.

We show by induction on i0≤i≤ki_0\le i\le k, that (a) ∣Qi∣≥2m+2|Q_i|\ge2m+2, (b) wji=vn(J(i))−(j−1)J(i)w_j^i=v_{n(J(i))-(j-1)}^{J(i)} for 1≤j≤m+21\le j\le m+2.

Note that this will yield (7), and hence prove the lemma. If i=i0i=i_0, then (a) and (b) follow as Qi0r=Pi0−1=PJ(i0)Q_{i_0}^r=P_{i_0-1}=P_{J(i_0)} and ∣Pi∣≥2m+2|P_i|\ge2m+2 holds for every i∈Ji\in J. The inductive step i↦i+1i\mapsto i+1 is trivial if i∉Ji\notin J as J(i)=J(i+1)J(i)=J(i+1) and Qi=Qi+1Q_i=Q_{i+1}. Hence we are left with the case i↦i+1i\mapsto i+1, where i∈Ji\in J.

Claim 3. The largest initial segment on which PiP_i and PJ(i)rP_{J(i)}^r coincide has size at most m+1m+1.

Proof. Let v0v_0 and v1v_1 be consecutive vertices in both PiP_i and PJ(i)rP_{J(i)}^r. Set η=γJ(i)\eta=\gamma_{J(i)} if J(i)∈J+J(i)\in J^+ and η=γJ(i)+1\eta=\gamma_{J(i)+1} otherwise. Similarly, set η′=γi\eta'=\gamma_i if i∈J+i\in J^+ and η′=γi+1\eta'=\gamma_{i+1} otherwise.

By the uniqueness of the labels in QQ, Claim 2, and the definition of PiP_i and PJ(i)P_{J(i)}, there are indices s∈Tηs\in T_\eta and t∈Tη′t\in T_{\eta'} such that

{csη,bcsη}={ctη′,bctη′}.\{c_{s\eta},bc_{s\eta}\}=\{c_{t\eta'},bc_{t\eta'}\}.

Note that this implies that

vr=[csη]=[ctη′]andv1−r=[bcsη]=[bctη′]v_r=[c_{s\eta}]=[c_{t\eta'}]\quad\text{and}\quad v_{1-r}=[bc_{s\eta}]=[bc_{t\eta'}]

for some r∈{0,1}r\in\{0,1\}. Indeed, otherwise we get the relation ct−1bcs=(bct)−1csc_t^{-1}bc_s=(bc_t)^{-1}c_s which is not satisfied in F2\mathbb{F}_2.

Suppose for a contradiction that the initial segment on which PiP_i and PJ(i)rP_{J(i)}^r coincide has size strictly more than m+1m+1. By the previous paragraph and the uniqueness of labels in QQ, we conclude that

∣{j∈Ib:∃j′∈Ib (cjη,bcjη)=(cj′η′,bcj′η′)}∣>m.\left|\{j\in I_b:\exists j'\in I_b\ (c_{j\eta},bc_{j\eta})=(c_{j'\eta'},bc_{j'\eta'})\}\right|>m.

Hence, by Claim 1, we have η=η′\eta=\eta'. As γ1,…,γk\gamma_1,\ldots,\gamma_k is a path and J(i)<iJ(i)<i, we must have J(i)=i−1J(i)=i-1, J(i)∈J−J(i)\in J^-, i∈J+i\in J^+ and γi=η\gamma_i=\eta. This implies that γi−1=γi+1\gamma_{i-1}=\gamma_{i+1} and that is a contradiction. □

By the definition, we have Qi+1=Qi∘PirQ_{i+1}=Q_i\circ P_i^r, and by the inductive assumption (b), we have that the largest initial segment where QiQ_i and PJ(i)rP_{J(i)}^r coincide has size at least m+2m+2. By Claim 3, we conclude that s′(Qi,Pir)≤ms'(Q_i,P_i^r)\le m. The description of Qi∘PirQ_i\circ P_i^r in (6) implies directly that the inductive assumptions (a) and (b) hold for i+1i+1, hence finishing the proof of Lemma 2. □

Next, we show that a sufficiently spaced collection of initial segments of an (ℓ,m)(\ell,m)-positive word wdw_d from IbI_b freely generates a free group. Write Ib={t1<⋯<tr}I_b=\{t_1<\cdots<t_r\}, where r=∣Ib∣r=|I_b|. Set p=⌊r2(m+1)⌋p=\left\lfloor\frac{r}{2(m+1)}\right\rfloor and ji=t2(m+1)ij_i=t_{2(m+1)i} for every 1≤i≤p1\le i\le p. Define

F={cj1,…,cjp}.(8)F=\{c_{j_1},\ldots,c_{j_p}\}. \tag*{(8)}

Note that by (b), we have that p≥⌈ℓ6(m+1)⌉p \ge\left\lceil\frac{\ell}{6(m+1)} \right\rceil.

Lemma 3. The elements of the set FF freely generate a free subgroup of F2F_2.

Proof. Wlog, we may assume p≥2p \ge2. Set h1=cj1h_1=c_{j_1}, and for 2≤s≤p2 \le s \le p define

hs=cjs(cjs−1)−1=djs−1⋯djs−1.h_s=c_{j_s}(c_{j_{s-1}})^{-1}=d_{j_{s-1}}\cdots d_{j_s-1}.

Observe that each hsh_s contains at least 2m+12m+1 occurrences of bb. We say that a bb letter is in the middle of the word hsh_s if there are at least mm other bb letters to the left and to the right of it. We claim that {h1,…,hp}\{h_1,\ldots,h_p\} freely generate a free group. Note that once we have that, the proof is done as they generate the same subgroup as the elements of FF that has the same size.

Let W=hi1ϵ1⋯hinϵnW=h_{i_1}^{\epsilon_1}\cdots h_{i_n}^{\epsilon_n} be a reduced word in the alphabet {h1,…,hp}\{h_1,\ldots,h_p\}, where ϵk∈{1,−1}\epsilon_k\in\{1,-1\} for every 1≤k≤n1\le k\le n. Suppose for a contradiction that W=1F2W=1_{F_2}. Consider the cancellation process that turns WW into 1F21_{F_2}. There must be a first time in this process, when one of the bb letters in the middle of some of the words {hikϵk}k=1n\{h_{i_k}^{\epsilon_k}\}_{k=1}^n is canceled. Fix such an index 1≤k≤n1\le k\le n. As it is the first time in the process, we may assume without loss of generality that the cancellation came from hik+1ϵk+1h_{i_{k+1}}^{\epsilon_{k+1}}.

Note that we must have ϵk+1≠ϵk\epsilon_{k+1}\ne\epsilon_k as otherwise no cancellation in hik+1ϵk+1h_{i_{k+1}}^{\epsilon_{k+1}} occurs at all. This implies that hik≠hik+1h_{i_k}\ne h_{i_{k+1}}, and condition (a) in the definition of an (ℓ,m)(\ell,m)-positive word guarantees that at most mm letters in hik±1h_{i_k}^{\pm1} are canceled in hik±1hik+1±1h_{i_k}^{\pm1}h_{i_{k+1}}^{\pm1}.

Entropy inequality in free groups

Let k≥2k\ge2 and Fk=⟨α1,…,αk⟩F_k=\langle\alpha_1,\ldots,\alpha_k\rangle be a free group on kk generators. We state the entropy inequality (or equivalently the non-negativity of the ff-invariant) of Bowen [5], see also [3], for the Bernoulli shift Fk↷([0,1]Fk,λ⊗Fk)F_k\curvearrowright([0,1]^{F_k},\lambda^{\otimes F_k}). To that end, recall that the entropy of a random variable RR with values in a finite set AA is defined as

H(R)=−∑a∈AP(R=a)log⁡(P(R=a)).H(R)=-\sum_{a\in A}\mathbb{P}(R=a)\log\bigl(\mathbb{P}(R=a)\bigr).

where we use the natural logarithm and set 0log⁡(0)=00\log(0)=0. Now suppose that RR is defined on ([0,1]Fk,λ⊗Fk)([0,1]^{F_k},\lambda^{\otimes F_k}), and set Ri(x)=R(αi⋅x)R_i(x)=R(\alpha_i\cdot x) for every x∈[0,1]Fkx\in[0,1]^{F_k} and 1≤i≤k1\le i\le k. The entropy inequality then reads as follows:

(2k−1)H(R)≤∑i=1kH(R,Ri)(9)(2k-1)H(R)\le\sum_{i=1}^{k}H(R,R_i) \tag*{(9)}

where (R,Ri)(R,R_i) is the joint random variable of RR and RiR_i.

Theorem 3. Let ϵ>0\epsilon>0, Fk=⟨α1,…,αk⟩F_k=\langle\alpha_1,\ldots,\alpha_k\rangle be a free group on k≥2k\ge2 generators and C⊆S⊆[0,1]FkC\subseteq S\subseteq[0,1]^{F_k} be measurable sets such that λ⊗Fk(S)≤1−ϵ\lambda^{\otimes F_k}(S)\le1-\epsilon and αi⋅x∈S\alpha_i\cdot x\in S for every x∈Cx\in C and 1≤i≤k1\le i\le k. Then

λ⊗Fk(C)≤log⁡(3)kϵ.\lambda^{\otimes F_k}(C)\le\frac{\log(3)}{k\epsilon}.

Proof. Set c=λ⊗Fk(C)c=\lambda^{\otimes F_k}(C) and s=λ⊗Fk(S)s=\lambda^{\otimes F_k}(S). We may assume that s>0s>0 as the claim is trivial otherwise. Define the random variable RR with values in {0,1,2}\{0,1,2\} by

R(x)={0if x∈C,1if x∈S∖C,2if x∉S.R(x)= \begin{cases} 0 & \text{if } x\in C,\\ 1 & \text{if } x\in S\setminus C,\\ 2 & \text{if } x\notin S. \end{cases}

Observe that H(R)≤log⁡(3)H(R)\le\log(3).

We claim that for each fixed 1≤i≤k1\le i\le k, we have that

H(R,Ri)≤2H(R)−clog⁡(1/s).(10)H(R,R_i)\le2H(R)-c\log(1/s). \tag*{(10)}

Indeed, write pa=P(R=a)=P(Ri=a)p_a=\mathbb{P}(R=a)=\mathbb{P}(R_i=a) and pab=P(R=a,Ri=b)p_{ab}=\mathbb{P}(R=a,R_i=b) for a,b∈{0,1,2}a,b\in\{0,1,2\}. As pa=∑b∈{0,1,2}pabp_a=\sum_{b\in\{0,1,2\}}p_{ab} for every a∈{0,1,2}a\in\{0,1,2\}, we have

2H(R)−H(R,Ri)=−∑a,b∈{0,1,2}pab(log⁡(pa)+log⁡(pb))+∑a,b∈{0,1,2}pablog⁡(pab)=−2∑a,b∈{0,1,2}pablog⁡(pa)+∑a,b∈{0,1,2}pablog⁡(pab)=∑a,b∈{0,1,2}pablog⁡(pabpapb),\begin{aligned} 2H(R)-H(R,R_i) &=-\sum_{a,b\in\{0,1,2\}}p_{ab}\bigl(\log(p_a)+\log(p_b)\bigr) +\sum_{a,b\in\{0,1,2\}}p_{ab}\log(p_{ab})\\ &=-2\sum_{a,b\in\{0,1,2\}}p_{ab}\log(p_a) +\sum_{a,b\in\{0,1,2\}}p_{ab}\log(p_{ab})\\ &=\sum_{a,b\in\{0,1,2\}}p_{ab}\log\left(\frac{p_{ab}}{p_ap_b}\right), \end{aligned}

where in all of the sums, we only consider non-zero probabilities. By concavity of log⁡\log, we have that

∑b∈{0,1,2}pablog⁡(pabpapb)≥(∑b∈{0,1,2}pab)log⁡(∑b∈{0,1,2}pab∑b∈{0,1,2}papb)=palog⁡(papa)=0\sum_{b\in\{0,1,2\}}p_{ab}\log\left(\frac{p_{ab}}{p_ap_b}\right) \ge \left(\sum_{b\in\{0,1,2\}}p_{ab}\right) \log\left(\frac{\sum_{b\in\{0,1,2\}}p_{ab}}{\sum_{b\in\{0,1,2\}}p_ap_b}\right) =p_a\log\left(\frac{p_a}{p_a}\right)=0

for a∈{1,2}a\in\{1,2\}. Finally, as p02=0p_{02}=0, we get from the same inequality that

∑b∈{0,1}p0blog⁡(p0bp0pb)≥p0log⁡(p0p0s)=clog⁡(1/s)\sum_{b\in\{0,1\}}p_{0b}\log\left(\frac{p_{0b}}{p_0p_b}\right) \ge p_0\log\left(\frac{p_0}{p_0s}\right)=c\log(1/s)

as p0=cp_0=c and p0+p1=sp_0+p_1=s by the definition. This gives (10).

Summing (10) for 1≤i≤k1\le i\le k and using the entropy inequality (9), we conclude that

(2k−1)H(R)≤2kH(R)−kclog⁡(1/s),(2k-1)H(R)\le2kH(R)-kc\log(1/s),

which is equivalent to

kclog⁡(1/s)≤H(R)≤log⁡(3).kc\log(1/s)\le H(R)\le\log(3).

The claim follows by noting that ϵ≤log⁡(1/s)\epsilon\le\log(1/s) as 0<s≤1−ϵ0<s\le1-\epsilon.

Relative cost of Sch(σ,{w}\sigma,\{w\}) with respect to {a,b}\{a,b\}-edges

We deduce Theorem 1 from the following result, which concerns an opposite question. Namely, suppose that we commit to a graphing G∉Span⁡(σ)\mathcal{G}\notin\operatorname{Span}(\sigma). How many {a,b}\{a,b\}-edges do we need to add to G\mathcal{G} to produce an element of Span⁡(σ)\operatorname{Span}(\sigma)?

The graphings that we consider are of the form Sch⁡(σ,{w})\operatorname{Sch}(\sigma,\{w\}), where ww is an (ℓ,m)(\ell,m)-positive word. We show that for certain choices of the parameters ℓ\ell and mm, the measure of the set of {a,b}\{a,b\}-edges that have to be added to turn Sch⁡(σ,{w})\operatorname{Sch}(\sigma,\{w\}) into an element of Span⁡(σ)\operatorname{Span}(\sigma) goes to 22 as ℓ→∞\ell\to\infty.

Theorem 4. Let σ\sigma be the Bernoulli action F2↷([0,1]F2,λ⊗F2)\mathbb{F}_2 \curvearrowright([0,1]^{\mathbb{F}_2},\lambda^{\otimes\mathbb{F}_2}), ϵ>0\epsilon>0, and ℓ\ell and mm be positive integers such that

120(m+1)(2m+1)log⁡3<2ϵ2ℓ.(11)120(m+1)(2m+1)\log3 < 2\epsilon^2\ell. \tag*{(11)}

Then for every (ℓ,m)(\ell,m)-positive word ww we have that if

Sch⁡(σ,{w})∪{{x,a⋅x}:x∈Za}∪{{x,b⋅x}:x∈Zb}∈Span⁡(σ),\operatorname{Sch}(\sigma,\{w\}) \cup\{\{x,a\cdot x\}:x\in Z_a\}\cup\{\{x,b\cdot x\}:x\in Z_b\}\in\operatorname{Span}(\sigma),

for some measurable sets Za,Zb⊆[0,1]F2Z_a,Z_b\subseteq[0,1]^{\mathbb{F}_2}, then λ⊗F2(Zr)>1−ϵ\lambda^{\otimes\mathbb{F}_2}(Z_r)>1-\epsilon for every r∈{a,b}r\in\{a,b\}.

We start with an application of Lemma 2 to the Bernoulli action. Recall the set FF from (8).

Lemma 4. Let ϵ>0\epsilon>0, ℓ\ell and mm be positive integers, ww be a (ℓ,m)(\ell,m)-positive word and ZbZ_b be a measurable subset of [0,1]F2[0,1]^{\mathbb{F}_2} such that

Sch⁡(σ,{a,w})∪{{x,b⋅x}:x∈Zb}∈Span⁡(σ)\operatorname{Sch}(\sigma,\{a,w\})\cup\{\{x,b\cdot x\}:x\in Z_b\}\in\operatorname{Span}(\sigma)

and λ⊗F2(Zb)≤1−ϵ\lambda^{\otimes\mathbb{F}_2}(Z_b)\leq1-\epsilon. Then there is a measurable set Z0,b⊇ZbZ_{0,b}\supseteq Z_b such that λ⊗F2(Z0,b)≤1−ϵ/2\lambda^{\otimes\mathbb{F}_2}(Z_{0,b})\leq1-\epsilon/2 and

λ⊗F2({x∈Z0,b:∀g∈F g⋅x∈Z0,b})≥2ϵ5(2m+1).\lambda^{\otimes\mathbb{F}_2}(\{x\in Z_{0,b}:\forall g\in F\ g\cdot x\in Z_{0,b}\})\geq\frac{2\epsilon}{5(2m+1)}.

Proof. Let (An)n∈N(A_n)_{n\in\mathbb{N}} be a sequence of measurable subsets of [0,1]F2[0,1]^{\mathbb{F}_2} such that (a) for every n∈Nn\in\mathbb{N}, we have λ⊗F2(An)<ϵ10(2m+1)\lambda^{\otimes\mathbb{F}_2}(A_n)<\frac{\epsilon}{10(2m+1)}, (b) for λ⊗F2\lambda^{\otimes\mathbb{F}_2}-almost every x∈[0,1]F2x\in[0,1]^{\mathbb{F}_2}, we have ∣{n∈N:x∈An}∣=∞|\{n\in\mathbb{N}:x\in A_n\}|=\infty.

Consider the following process that starts with S0=ZbS_0=Z_b and inductively creates a sequence of measurable sets SnS_n for n∈Nn\in\mathbb{N} such that Sn⊆Sn+1S_n\subseteq S_{n+1} by the following rule. If x∈Anx\in A_n is such that

1≤∣{j∈Ib:cj⋅x∉Sn}∣≤2m,1\leq|\{j\in I_b:c_j\cdot x\notin S_n\}|\leq2m,

then we add xx and cj⋅xc_j\cdot x for every j∈Ibj\in I_b to Sn+1S_{n+1}. Note that

λ⊗F2(Sn+1)−λ⊗F2(Sn)≤ϵ10(12)\lambda^{\otimes\mathbb{F}_2}(S_{n+1})-\lambda^{\otimes\mathbb{F}_2}(S_n)\leq\frac{\epsilon}{10} \tag*{(12)}

for every n∈Nn\in\mathbb{N} by (a).

Set Cn={x∈Sn:∀j∈Ib cj⋅x∈Sn}C_n=\{x\in S_n:\forall j\in I_b\ c_j\cdot x\in S_n\}. Observe that for each n∈Nn\in\mathbb{N}, we have

λ⊗F2(Sn+1)−λ⊗F2(Sn)≤(2m+1)(λ⊗F2(Cn+1)−λ⊗F2(Cn)).\lambda^{\otimes\mathbb{F}_2}(S_{n+1})-\lambda^{\otimes\mathbb{F}_2}(S_n)\leq(2m+1)\left(\lambda^{\otimes\mathbb{F}_2}(C_{n+1})-\lambda^{\otimes\mathbb{F}_2}(C_n)\right).

Indeed, define a map that sends y∈Sn+1∖Sny\in S_{n+1}\setminus S_n to some x∈Anx\in A_n such that

1≤∣{j∈Ib:cj⋅x∉Sn}∣≤2m,1\leq|\{j\in I_b:c_j\cdot x\notin S_n\}|\leq2m,

and

y∈{x}∪{cj⋅x}j∈Ib.y\in\{x\}\cup\{c_j\cdot x\}_{j\in I_b}.

This can be done by using the Lusin-Novikov uniformization theorem. The claim follows from the fact that such a map is at most (2m+1)(2m+1)-to-1, and its range falls into Cn+1∖CnC_{n+1}\setminus C_n. Consequently, we obtain that

λ⊗F2(Sn)−(1−ϵ)≤(2m+1)λ⊗F2(Cn)(13)\lambda^{\otimes\mathbb{F}_2}(S_n)-(1-\epsilon)\leq(2m+1)\lambda^{\otimes\mathbb{F}_2}(C_n) \tag*{(13)}

holds for every n∈Nn\in\mathbb{N}.

We claim that λ⊗F2(⋃n∈NSn)=1\lambda^{\otimes\mathbb{F}_2}\left(\bigcup_{n\in\mathbb{N}} S_n\right)=1. Let x∈[0,1]F2x\in[0,1]^{\mathbb{F}_2} be in the free part and such that there is a path P=(γ1⋅x,γ2⋅x,…,γk⋅x)P=(\gamma_1\cdot x,\gamma_2\cdot x,\ldots,\gamma_k\cdot x), where γ1=1F2\gamma_1=1_{\mathbb{F}_2} and γk=b\gamma_k=b, in

HS0=Sch⁡(σ,{a,w})∪{{y,b⋅y}:y∈S0}\mathcal{H}_{S_0}=\operatorname{Sch}(\sigma,\{a,w\})\cup\{\{y,b\cdot y\}:y\in S_0\}

from xx to b⋅xb\cdot x. We claim that x∈Sx\in S, where S=⋃n∈NSnS=\bigcup_{n\in\mathbb{N}}S_n. Indeed, suppose for a contradiction that x∉Sx\notin S. As PP is also a path in HS\mathcal{H}_S that connects xx and b⋅xb\cdot x, we have that there is y∈Py\in P such that

1≤∣{j∈Ib:cj⋅y∉S}∣≤2m1\leq\left|\{j\in I_b:c_j\cdot y\notin S\}\right|\leq2m

by Lemma 2. Let p∈Np\in\mathbb{N} be such that y∈Apy\in A_p and

{j∈Ib:cj⋅y∉S}={j∈Ib:cj⋅y∉Sp}.\{j\in I_b:c_j\cdot y\notin S\}=\{j\in I_b:c_j\cdot y\notin S_p\}.

Such an index exists by (b) and the fact that S=⋃n∈NSnS=\bigcup_{n\in\mathbb{N}}S_n. This is a contradiction as {y}∪{cj⋅y}j∈Ib⊆Sp+1⊆S\{y\}\cup\{c_j\cdot y\}_{j\in I_b}\subseteq S_{p+1}\subseteq S by construction.

By the previous paragraph, there is a maximal index n0∈Nn_0\in\mathbb{N} such that λ⊗F2(Sn0)≤1−ϵ/2\lambda^{\otimes\mathbb{F}_2}(S_{n_0})\leq1-\epsilon/2. Set Z0,b=Sn0Z_{0,b}=S_{n_0}. By (12), we have

λ⊗F2(Z0,b)≥1−ϵ/2−ϵ/10,\lambda^{\otimes\mathbb{F}_2}(Z_{0,b})\geq1-\epsilon/2-\epsilon/10,

which yields, when combined with (13),

2ϵ5(2m+1)≤λ⊗F2(Cn0)\frac{2\epsilon}{5(2m+1)}\leq\lambda^{\otimes\mathbb{F}_2}(C_{n_0})

as desired. □

Before turning to the proof of Theorem 4 let us make an easy, folklore observation.

Lemma 5. Let Λ>Δ\Lambda>\Delta be countable groups, σ\sigma be the Bernoulli action Λ↷([0,1]Λ,λ⊗Λ)\Lambda\curvearrowright([0,1]^\Lambda,\lambda^{\otimes\Lambda}), and σ′\sigma' be the Δ\Delta action obtained by restricting σ\sigma to Δ\Delta. Then σ′\sigma' is isomorphic to the Bernoulli action of Δ\Delta.

Proof. Choose a collection R⊆ΛR\subseteq\Lambda of right coset representatives of Δ\Delta. The map Φ:[0,1]Λ→([0,1]R)Δ\Phi:[0,1]^\Lambda\to([0,1]^R)^\Delta defined by

Φ(x)(δ)=(x(δr))r∈R,\Phi(x)(\delta)=(x(\delta r))_{r\in R},

is a Δ\Delta-equivariant measure preserving bijection. Since ([0,1]R,λ⊗R)([0,1]^R,\lambda^{\otimes R}) is a non-atomic standard measure space, it is isomorphic modulo null sets to ([0,1],λ)([0,1],\lambda). Applying this isomorphism in each Δ\Delta-coordinate gives the desired isomorphism. □

Proof of Theorem 4. Let ℓ\ell and mm be positive integers that satisfy

24(m+1)log⁡3ϵℓ<2ϵ5(2m+1),\frac{24(m+1)\log3}{\epsilon\ell}<\frac{2\epsilon}{5(2m+1)},

and ww be a (ℓ,m)(\ell,m)-positive word. Suppose that there are measurable sets Za,Zb⊆[0,1]F2Z_a,Z_b\subseteq[0,1]^{\mathbb{F}_2} such that

Sch⁡(σ,{w})∪{{x,a⋅x}:x∈Za}∪{{x,b⋅x}:x∈Zb}∈Span⁡(σ).\operatorname{Sch}(\sigma,\{w\})\cup\{\{x,a\cdot x\}:x\in Z_a\}\cup\{\{x,b\cdot x\}:x\in Z_b\}\in\operatorname{Span}(\sigma).

We show that λ⊗F2(Zr)>1−ϵ\lambda^{\otimes\mathbb{F}_2}(Z_r)>1-\epsilon for r∈{a,b}r\in\{a,b\}.

We only handle the case r=br=b, as r=ar=a is completely analogous. Suppose for a contradiction that λ⊗F2(Zr)≤1−ϵ\lambda^{\otimes\mathbb{F}_2}(Z_r)\leq1-\epsilon. By Lemma 4, there are measurable sets Zb⊆SZ_b \subseteq S and C⊆SC \subseteq S such that λ⊗F2(S)≤1−ϵ/2\lambda^{\otimes F_2}(S) \le1-\epsilon/2, λ⊗F2(C)≥2ϵ5(2m+1)\lambda^{\otimes F_2}(C) \ge\frac{2^\epsilon}{5(2m+1)} and g⋅x∈Sg \cdot x \in S for every g∈Fg \in F and x∈Cx \in C.

Write Γ≃Fk\Gamma\simeq F_k for the free group that is freely generated by FF. As Γ\Gamma is a subgroup of F2F_2, we may consider the restriction of σ\sigma to Γ\Gamma, that we denote as Γ↷σ′[0,1]F2\Gamma\overset{\sigma'}{\curvearrowright} [0,1]^{F_2}. It follows from Lemma 5 that σ′\sigma' is isomorphic to the Bernoulli shift Γ↷[0,1]Γ\Gamma\curvearrowright[0,1]^\Gamma and C⊆SC \subseteq S satisfy the assumptions of Theorem 3 with ϵ/2\epsilon/2. Consequently, λ⊗F2(C)≤2log⁡(3)kϵ\lambda^{\otimes F_2}(C) \le\frac{2\log(3)}{k\epsilon}. Finally, note that

k=∣F∣≥⌊ℓ6(m+1)⌋≥ℓ12(m+1),k=|F|\ge\left\lfloor\frac{\ell}{6(m+1)}\right\rfloor\ge\frac{\ell}{12(m+1)},

where the first inequality is by the definition in (8) and the second inequality follows from the assumption (11). This gives the claim. □

Proof of Theorem 1

In this section we prove our main result.

Proof of Theorem 1. The claim is trivial for ϵ>1\epsilon>1 as Cost⁡(σ)=2\operatorname{Cost}(\sigma)=2, so we may assume that 0<ϵ≤10<\epsilon\le1. Let ℓ\ell and mm be positive integers such that

ℓ≥50,5log⁡(ℓ+1)≤m≤ℓ/2and960(m+1)(2m+1)log⁡3<ϵ2ℓ.\ell\ge50,\quad5\log(\ell+1)\le m\le\ell/2\quad\text{and}\quad960(m+1)(2m+1)\log3<\epsilon^2\ell.

By Lemma 1, there is d∈{a,b}ℓd\in\{a,b\}^{\ell} such that wdw_d is an (ℓ,m)(\ell,m)-positive word and bwdbw_d is an (ℓ+1,m)(\ell+1,m)-positive word. Indeed, the probability that wdw_d is an (ℓ,m)(\ell,m)-positive word and bwdbw_d is an (ℓ+1,m)(\ell+1,m)-positive word is at least 1/2−20/ℓ>01/2-20/\ell>0 as ℓ≥50\ell\ge50. Observe that both wdw_d and bwdbw_d satisfy the assumptions of Theorem 4 for ϵ/4>0\epsilon/4>0. We show that setting w=wdw=w_d and Sϵ={a,w,bw}S_\epsilon=\{a,w,bw\} works as required.

The fact that SϵS_\epsilon generates F2F_2 is clear. Let G∈Span⁡(σ)\mathcal{G}\in\operatorname{Span}(\sigma) be such that G⊆Sch⁡(σ,Sϵ)\mathcal{G}\subseteq\operatorname{Sch}(\sigma,S_\epsilon). Set

W0={x∈[0,1]F2:{x,w⋅x}∈G}andW1={x∈[0,1]F2:{x,bw⋅x}∈G}.W_0=\{x\in[0,1]^{F_2}:\{x,w\cdot x\}\in\mathcal{G}\}\quad\text{and}\quad W_1=\{x\in[0,1]^{F_2}:\{x,bw\cdot x\}\in\mathcal{G}\}.

Define Z1={w⋅x:x∈W1}Z_1=\{w\cdot x:x\in W_1\} and observe that

Sch⁡(σ,{a,w})∪{{x,b⋅x}:x∈Z1}∈Span⁡(σ).\operatorname{Sch}(\sigma,\{a,w\})\cup\{\{x,b\cdot x\}:x\in Z_1\}\in\operatorname{Span}(\sigma).

Indeed, we have that

(x,w⋅x,b⋅(w⋅x))(x,w\cdot x,b\cdot(w\cdot x))

is a path in Sch⁡(σ,{a,w})∪{{x,b⋅x}:x∈Z1}\operatorname{Sch}(\sigma,\{a,w\})\cup\{\{x,b\cdot x\}:x\in Z_1\} for every x∈W1x\in W_1. By Theorem 4 and the fact that λ⊗F2(Z1)=λ⊗F2(W1)\lambda^{\otimes F_2}(Z_1)=\lambda^{\otimes F_2}(W_1), we conclude that λ⊗F2(W1)>1−ϵ/4\lambda^{\otimes F_2}(W_1)>1-\epsilon/4.

Similarly, define Z0={w⋅x:x∈W0}Z_0=\{w\cdot x:x\in W_0\}. We claim that

Sch⁡(σ,{a,bw})∪{{x,b⋅x}:x∈Z0}∈Span⁡(σ).\operatorname{Sch}(\sigma,\{a,bw\})\cup\{\{x,b\cdot x\}:x\in Z_0\}\in\operatorname{Span}(\sigma).

Indeed, we have that

(x,bw⋅x,w⋅x)(x,bw\cdot x,w\cdot x)

is a path in Sch⁡(σ,{a,bw})∪{{x,b⋅x}:x∈Z0}\operatorname{Sch}(\sigma,\{a,bw\})\cup\{\{x,b\cdot x\}:x\in Z_0\} for every x∈W0x\in W_0. By Theorem 4 and the fact that λ⊗F2(Z0)=λ⊗F2(W0)\lambda^{\otimes F_2}(Z_0)=\lambda^{\otimes F_2}(W_0), we conclude that λ⊗F2(W0)>1−ϵ/4\lambda^{\otimes F_2}(W_0)>1-\epsilon/4.

Finally, define A={x∈[0,1]F2:{x,a⋅x}∈G}A=\{x\in[0,1]^{F_2}:\{x,a\cdot x\}\in\mathcal{G}\}, and observe that

Sch⁡(σ,{b,w})∪{{x,a⋅x}:x∈A}∈Span⁡(σ).\operatorname{Sch}(\sigma,\{b,w\})\cup\{\{x,a\cdot x\}:x\in A\}\in\operatorname{Span}(\sigma).

By Theorem 4, we conclude that λ⊗F2(A)>1−ϵ/2\lambda^{\otimes F_2}(A)>1-\epsilon/2. Consequently, we have that

Cost⁡(G)≥λF2(A)+λF2(W0)+λF2(W1)>3−ϵ.\operatorname{Cost}(\mathcal{G}) \ge\lambda^{\mathbb{F}_2}(A) + \lambda^{\mathbb{F}_2}(W_0) + \lambda^{\mathbb{F}_2}(W_1) > 3 - \epsilon.

As G\mathcal{G} was arbitrary, we get that Sub-Cost⁡(σ,Sϵ)≥3−ϵ\operatorname{Sub\text{-}Cost}(\sigma,S_\epsilon) \ge3-\epsilon as desired. □\square

Finally, let us deduce Corollary 2.

Proof of Corollary 2. Let cc be the cost of the equivalence relation given by restricting σ\sigma to the Λ\Lambda action and let H\mathcal{H} be any of its spanning subgraphings. Note that by free-product additivity (see, [8]) Cost⁡(σ)=c+2\operatorname{Cost}(\sigma)=c+2. Define Gϵ=H∪Gϵ′\mathcal{G}_\epsilon=\mathcal{H}\cup\mathcal{G}'_\epsilon, where Gϵ′\mathcal{G}'_\epsilon is the graphing provided by Theorem 1 with k=2k=2. Then, since we used a free product, any spanning subgraphing of Gϵ\mathcal{G}_\epsilon must span a.e. Λ\Lambda and F2\mathbb{F}_2 component internally. In particular, using Lemma 5 and our main theorem, its cost is at least c+2+1−ϵc+2+1-\epsilon. □\square

Open problems

Let us reiterate the question from Kechris-Miller [14] about the complexity of cost, which was the original motivation behind this paper.

Problem 1. Is there a Borel family (Ex)x∈2N(E_x)_{x\in2^{\mathbb{N}}} of pmp CBERs such that the set {x∈2N:Cost⁡(Ex)<∞}\{x\in2^{\mathbb{N}}:\operatorname{Cost}(E_x)<\infty\} is analytic complete?

The results of this paper and Remark 1 motivate the following problem.

Problem 2. Characterize the countable groups Γ\Gamma, for which the subgraphings approximate cost problem has a positive answer. What if we only consider Schreier graphings of the Bernoulli action?

Note that the answer is positive when Γ\Gamma is amenable: indeed, then its actions are measure hyperfinite. From a hyperfinite decomposition of a graphing G\mathcal{G} one can define a spanning subtreeing of G\mathcal{G}, which in turn must realize the cost of the equivalence relation.

Eötvös Loránd University, Institute of Mathematics, Pázmány Péter stny. 1/C, 1117 Budapest, Hungary

Email address: [email protected]

Charles University, Computer Science Institute, Malostranské nám. 25 118 00 Praha 1, Czechia

Email address: [email protected]

Eötvös Loránd University, Institute of Mathematics, Pázmány Péter stny. 1/C, 1117 Budapest, Hungary

Email address: [email protected]

References

  1. [1]Miklós Abért. Some questions. https://www.renyi.hu/~abert/research/questions.pdf, 2010. Problem list, November 2, 2010.
  2. [2]Miklós Abért and Nikolay Nikolov. Rank gradient, cost of groups and the rank versus Heegaard genus problem. Journal of the European Mathematical Society, 14(5):1657–1677, 2012.arxiv.org/abs/math/0701361
  3. [3]Ágnes Backhausz and Balázs Szegedy. On large-girth regular graphs and random processes on trees. Random Structures & Algorithms, 53(3):389–416, 2018.
  4. [4]Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm. Uniform spanning forests. The Annals of Probability, 29(1):1–65, 2001.DOI
  5. [5]Lewis Bowen. The ergodic theory of free group actions: entropy and the f-invariant. Groups, Geometry, and Dynamics, 4(3):419–432, 2010.arxiv.org/abs/0902.0174
  6. [6]Matteo D’Achille, Jan Grebík, Ali Khezeli, Konstantin Recke, and Amanda Wilkens. Vanishing uniqueness thresholds in Voronoi percolation on products. arXiv:2511.23317, 2025.arxiv.org/abs/2511.23317
  7. [7]Mikołaj Frączyk, Sam Mellick, and Amanda Wilkens. Poisson-voronoi tessellations and fixed price in higher rank. to appear Ann. of Math., 2026.
  8. [8]Damien Gaboriau. Coût des relations d’équivalence et des groupes. Invent. Math., 139(1):41–98, 2000.DOI
  9. [9]Damien Gaboriau. Orbit equivalence and measured group theory. Proceedings of the International Congress of Mathematicians Hyderabad, 2010.arxiv.org/abs/1009.0132
  10. [10]Damien Gaboriau. Around the orbit equivalence theory, measure equivalence, cost and ℓ² Betti numbers. https://perso.ens-lyon.fr/gaboriau/Travaux-Publi/ME-Cost-L2-Lectures/ME-Cost-L2-Lectures.pdf, 2025. Lecture notes, version of October 3, 2025.
  11. [11]Jan Grebík and Konstantin Recke. Poisson-Voronoi percolation in higher rank. arXiv:2504.02435, 2025.arxiv.org/abs/2504.02435
  12. [12]Tom Hutchcroft and Asaf Nachmias. Indistinguishability of trees in uniform spanning forests. Probability Theory and Related Fields, 168(1–2):113–152, 2017.
  13. [13]Tom Hutchcroft and Gábor Pete. Kazhdan groups have cost 1. Inventiones mathematicae, 221:873–891, 2020.arxiv.org/abs/1810.11015
  14. [14]Alexander S. Kechris and Benjamin D. Miller. Topics in Orbit Equivalence, volume 1852 of Lecture Notes in Mathematics. Springer Berlin, Heidelberg, 2004.
  15. [15]Ali Khezeli. Products of infinite countable groups have fixed price one. arXiv preprint arXiv:2509.08325, 2025.arxiv.org/abs/2509.08325
  16. [16]François Le Maître. The number of topological generators for full groups of ergodic equivalence relations. Inventiones mathematicae, 198(2):261–268, 2014.DOI
  17. [17]Gilbert Levitt. On the cost of generating an equivalence relation. Ergodic Theory Dynam. Systems, 15(6):1173–1181, 1995.DOI
  18. [18]László Lovász. Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012.
  19. [19]Russell Lyons and Yuval Peres. Probability on Trees and Networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016.
  20. [20]OpenAI. The free uniform spanning forest is a factor of IID. OpenAI Math Release preprint OAI:The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026, 2026.
  21. [21]Gábor Pete and Ádám Timár. The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set. The Annals of Probability, 50(6):2218–2243, 2022.arxiv.org/abs/2006.06387
  22. [22]Raz Slutsky. A product-neighbourhood criterion for fixed price one. arXiv preprint arXiv:2607.20273, 2026.arxiv.org/abs/2607.20273

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

GPT-5.6

View statement
Looking for related papers…
Contents