{'fraction_non_alphanumeric': 0.07312216068205862, 'fraction_numerical': 0.00784118489016118, 'mean_word_length': 3.4063613929256924, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Ergodic actions of countable groups and finite generating partitions

We prove that if an ergodic action of a countable group on a probability space admits a generating partition having finite Shannon entropy then it admits a finite generating partition.


Introduction
Let G be a countable group acting by measure preserving bijections on a probability space (X, µ). For a partition α of X, we denote by G·α the smallest σ-algebra containing the sets g · A for g ∈ G and A ∈ α. The partition α is generating (or a generator ) if for every measurable set B ⊆ X there is some B ′ ∈ G · α with µ(B△B ′ ) = 0. The Shannon entropy of a partition α is Sofic entropy and f-invariant entropy have strong similarities with Kolmogorov-Sinai entropy, and in fact when the acting group is amenable these entropies agree with Kolmogorov-Sinai entropy. Furthermore, f-invariant entropy is essentially a special case of sofic entropy. The theories of sofic entropy and f-invariant entropy, being quite new, are currently poorly understood. In particular, it is not clear what relationships sofic entropy and f-invariant entropy have with generating partitions. As with Kolmogorov-Sinai entropy, sofic entropy and f-invariant entropy are easier to use, define, and compute when there are generating partitions with finite Shannon entropy (in fact, the definition of f-invariant entropy still requires a generating partition having finite Shannon entropy). So theorems along the lines of Krieger's theorem and Rohlin's theorem mentioned above would certainly benefit the theories of sofic entropy and f-invariant entropy. Thus the question arises as to what can be said about generating partitions outside of the realm of actions of amenable groups.
Although we draw motivation from sofic entropy and f-invariant entropy (which deal with actions of sofic groups and finitely generated free groups, respectively), our main theorem deals with actions of general countable groups. We prove the following finite generator theorem. Theorem 1.1. Let G be a countable group acting ergodically by measure preserving bijections on a standard probability space (X, µ). If this action admits a generating partition having finite Shannon entropy, then it admits a finite generating partition.
We mention that although our proof is constructive, it does not immediately imply any relationship between the Shannon entropy of the original partition and the size of the finite partition constructed.
We obtained the above theorem while trying to establish a Krieger finite generator theorem for f-invariant entropy. However, we found that Krieger's theorem and Rohlin's theorem fail in this setting.
For an action G (X, µ) we let ∆ * G (X, µ) denote the infimum of the Shannon entropies of the generating partitions (this is +∞ if there are no such partitions) and we let ∆ G (X, µ) denote the smallest size of a finite generating partition (again this is +∞ if there are no such partitions). If G is a finitely generated free group then we denote the f-invariant entropy of the action G (X, µ) by f G (X, µ). We remark that f G (X, µ) is only defined when there is a generating partition having finite Shannon entropy. When f G (X, µ) is defined it takes values in R ∪ {−∞}.
where the supremums are taken over all essentially free ergodic probability measure preserving actions G (X, µ) with f G (X, µ) defined and f G (X, µ) = h.
Since f-invariant entropy is currently only defined when there is a generating partition having finite Shannon entropy, it follows from our main theorem that ∆ * G (X, µ) and ∆ G (X, µ) are finite for any ergodic action G (X, µ) in which f G (X, µ) is defined (so in particular for the actions considered in the proposition above).
We wish to emphasize that this proposition only says that the most obvious translations of Krieger's theorem and Rohlin's theorem to the setting of f-invariant entropy are false. There is still opportunity for subtle modifications of Krieger's theorem and Rohlin's theorem to be true for f-invariant entropy (we will mention such a possible modification).
We obtain a similar but much weaker result for sofic entropy. With sofic entropy the situation is much different though because the sofic entropy of a sofic group action G (X, µ) is not a single number but a collection of numbers. These numbers are indexed by sofic approximation sequences to the group. It is known that different sofic approximation sequences can give different sofic entropy values, however it is not yet understood how widespread this phenomena is. For a sofic group G, a sofic approximation sequence Σ to G, and an action G (X, µ), we denote the corresponding sofic entropy by h Σ G (X, µ). We remark that h Σ G (X, µ) is always defined and takes values in {−∞} ∪ [0, +∞]. Proposition 1.3. There exists a sofic group G, a sofic approximation sequence Σ to G, and an essentially free ergodic action G (X, µ) such that h Σ G (X, µ) = −∞ but ∆ * G (X, µ) = ∆ G (X, µ) = +∞. We do not view the above corollary as sufficient grounds to say that Krieger's theorem and Rohlin's theorem fail for sofic entropy. The fact is that having h Σ G (X, µ) = −∞ reflects almost nothing about the action; it only means that Σ is inadequate for modeling the action G (X, µ). We do not know if Rohlin's theorem and Krieger's theorem hold for actions whose sofic entropy is not negative infinity.
Organization. In Section 2 below, we prove Theorem 1.1. Then in Section 3 we prove Propositions 1.2 and 1.3. These two sections are written independently of one another.

Construction of finite generators
We begin with an equivalent characterization of generating partitions. For a partition α of X and a point x ∈ X, we write α(x) to denote the unique member A ∈ α with x ∈ A. Lemma 2.1. Let X be a standard Borel space, let µ be a Borel probability measure on X, and let G be a countable group acting by measure preserving bijections on X. The following are equivalent for a countable measurable partition α of X (i) α is a generating partition; Proof. The equivalence of (i) and (ii) is by definition.
(ii) ⇒ (iii). Since X is a standard Borel space, there is a countable collection (B n ) n∈N of Borel subsets of X such that the σ-algebra generated by {B n : n ∈ N} is precisely the collection of all Borel subsets of X and such that (B n ) n∈N separates points, meaning that for x = y ∈ X there is n ∈ N with either x ∈ B n and y ∈ B n or x ∈ B n and y ∈ B n [6, Proposition 12.1]. For each n ∈ N let C n ∈ G · α be such that µ(B n △C n ) = 0. Set Then µ(X ′ ) = 1. Now fix x, y ∈ X ′ with x = y. Then there is n ∈ N with B n containing either x or y but not containing both. Since x, y ∈ X ′ we have x ∈ B n if and only if x ∈ C n , and similarly y ∈ B n if and only if y ∈ C n . Therefore C n contains either x or y, but it does not contain both. Since C n lies in the σ-algebra generated by the sets {g · A : g ∈ G, A ∈ α}, there must be g ∈ G and A ∈ α with g · A containing either x or y but not both. Then . By replacing X ′ with g∈G g · X ′ if necessary, we may suppose that g · X ′ = X ′ for every g ∈ G. Let β be the partition of X ′ induced by α. Since µ(X \ X ′ ) = 0, it suffices to show that for every Borel set . If x = y ∈ X ′ then by assumption there is g ∈ G with β(g · x) = β(g · y) and thus φ(x) = φ(y). So φ is injective. The function φ is Borel since the inverse image of any open set in β G is Borel. Consider the partition It is readily seen that the G-translates of the members of ξ generate the open subsets of β G . Therefore G · ξ is precisely the collection of Borel subsets of β G . Notice that Clearly C is a σ-algebra and g · C A ∈ C for every g ∈ G and For a finite set S we let S <ω denote the set of all finite words with letters in S (the ω in the superscript denotes the first infinite ordinal). For z ∈ S <ω we let |z| denote the length of the word z. In the first step of the proof of [10, Theorem 2.1], Krieger proves the following.
As a convenience to the reader, we include the proof below.
Proof. This is clear if α is finite. So suppose that α is countably infinite and enumerate α as Notice that the sequence (t(m)) ∞ m=1 is non-decreasing. Set N 1 = 1 and for m > 1 define This follows from the fact that |L( The function L above can be extended to X by setting L(x) = L(α(x)). The above lemma then says that the labeling L : X → {1, 2, 3} <ω has finite length on average. The idea behind the proof of Theorem 1.1 is to rearrange the L "data" within each orbit to obtain a new function (a relabeling) R : X → {1, 2, 3, 4} <ω which has uniformly bounded length. The function R would then have finite image and thus induce a finite partition of X. In order for this partition to be generating, one must ensure that the function L can be recovered from R. In [10], Krieger carried out this argument in the case of Z actions, obtaining a weak form of his finite generator theorem which did not specify the smallest possible size of a finite generator. While our proof is inspired by his argument, our proof is quite distinct as Krieger's argument relied heavily on properties of Z.
The following lemma is essential for the task of rearranging the L data within each orbit.
If G acts on (X, µ) and A ⊆ X, then we say that x, y ∈ X are A-symmetric if for every g ∈ G g · x ∈ A ⇔ g · y ∈ A. Proof. We first define auxiliary functions Q 1 , Q 2 , and θ which will play roles similar to P 1 , P 2 , and ψ, respectively. The idea is to define Q 1 , Q 2 , and θ to achieve clauses (i), (iii), (iv), and (v) and then use these functions repeatedly to perform a type of exhaustion argument and achieve clause (ii). Fix any well ordering, , of G. If A, B ⊆ X are measurable and (G · A) ∩ B = ∅ then we set Q 1 (A, B) = Q 2 (A, B) = θ(A, B) = ∅. If (G · A) ∩ B = ∅ then we let h ∈ G be the -least element of G satisfying (h · A) ∩ B = ∅. In this case we set (A, B)). Notice that Q 1 (A, B) and Q 2 (A, B) are measurable subsets of X and θ(A, B) is a measurable function. If P 1 , P 2 , and ψ are replaced with Q 1 , Q 2 , and θ, respectively, then clauses (i), (iv), and (v) are clearly satisfied (clause (v) immediately follows from the simple definition of θ(A, B)). Clause (iii) is also satisfied, for if we assume Q 1 (A, B) and Q 2 (A, B) are non-empty (clause (iii) is trivial otherwise) and let h be as above, then for any x ∈ X and g ∈ G we have g · We have Q 1 (A, B) ⊆ A and Q 2 (A, B) ⊆ B. By repeatedly using the functions Q 1 and Q 2 we seek to exhaust (in measure) either A or B. We recursively define This completes the proof.
We are now ready to prove the main theorem.
Theorem 2.4. Let G be a countable group acting ergodically by measure preserving bijections on a standard probability space (X, µ). If this action admits a generating partition having finite Shannon entropy, then it admits a finite generating partition.
The function L : X → {1, 2, 3} <ω on average has finite length, so the idea now is to rearrange the L-data within each orbit so that in the end every point of X has a word of uniformly finite length associated to it. In doing this, one must take care not to lose data, and more importantly one must rearrange the data in such a way that the original function L can be decoded from the new data. The functions appearing in the previous lemma play the critical role of achieving these requirements.
First we need to determine how long the new words we create should be. Since So there is C ≥ 1 such that n>C n · µ({x ∈ X : |L(x)| = n}) < 1 4 .
After rearranging the L-data, the new words we construct will have length bounded above by C + 2.
We now use the previous lemma to determine how to rearrange the L-data.
We now define a new labeling function R : X → {1, 2, 3, 4} <ω by the rule (below the symbol ⌢ denotes concatenation of words and ↾ denotes restriction) Notice that in the second and third cases in the definition of R(x) we automatically have θ −1 n (x) ∈ B n since x ∈ T n . Clearly |R(x)| < C + 3 for every x ∈ X. So the image of R is finite. Let β be the partition of X obtained from R, i.e. define the classes of β so that x, y ∈ X lie in the same class of β if and only if R(x) = R(y). Then β is a finite measurable partition of X. We claim that β is a generating partition.
By Lemma 2.1 and the definition of β, we have that β is a generating partition if and only if there is a set X ′ ⊆ X with µ(X ′ ) = 1 such that for every x = y ∈ X ′ there is g ∈ G with R(g · x) = R(g · y). Since α is a countable generating partition, there is a set X ′′ ⊆ X with µ(X ′′ ) = 1 such that for all x = y ∈ X ′′ there is g ∈ G with α(g · x) = α(g · y). Set Then µ(X ′ ) = 1. Fix x = y ∈ X ′ . We proceed by cases to show that there is g ∈ G with R(g · x) = R(g · y).
Case 1: There is n ≥ 1 such that x and y are not B n -symmetric. Let n ≥ 1 be least such that there is u ∈ G with B n containing precisely one of u · x and u · y. To be specific, say u ·x ∈ B n and u ·y ∈ B n (the other case is nearly identical). If n = 1 then the letter 4 appears in R(u · y) but not R(u · x) and thus R(u · x) = R(u · y). So suppose that n > 1. Since n was chosen to be minimal, we must have that x and y are B k -symmetric for all k < n. So by clause (iii) of Lemma 2.3 x and y are T 1 -symmetric. It readily follows from a simple induction argument that x and y are both B k -symmetric and T k -symmetric for every 1 ≤ k < n. So u · x ∈ B n ⊆ B n−1 implies u · y ∈ B n−1 and clause (v) of Lemma 2.3 implies that there is h ∈ G with θ n−1 (u · x) = hu · x and θ n−1 (u · y) = hu · y (we use here the fact that x, y ∈ X ′ implies u · x, u · y ∈ E n−1 and thus θ n−1 (u · x) and θ n−1 (u · y) are defined). Then the letter 4 appears once in R(hu · x) = R(θ n−1 (u · x)) (since u · x ∈ B n−1 ∩ B n ) but appears twice in R(hu · y) = R(θ n−1 (u · y)) (since u · y ∈ B n−1 \ B n ). Thus R(hu · x) = R(hu · y).
Case 2: For every n ≥ 1 x and y are B n -symmetric. Fix u ∈ G with α(u · x) = α(u · y) (such a u exists since x, y ∈ X ′ ⊆ X ′′ ). If u · x is not in B 1 then neither is u · y, and we have that L(u · x) and L(u · y) are prefixes of R(u · x) and R(u · y), respectively. Thus R(u · x) = R(u · y) if u · x ∈ B 1 . So suppose that u · x ∈ B 1 . We have |L(u · x)| = C + n, where n is maximal with u · x ∈ B n . Since x and y are B ksymmetric for every k ≥ 1, we must have |L(u·x)| = |L(u·y)|. Since L(u·x) = L(u·y) and |L(u · x)| = |L(u · y)|, there is k ≥ 1 with L(u · x)(k) = L(u · y)(k). If k ≤ C then from the first case in the definition of R it follows that R(u · x)(k) = R(u · y)(k) and thus R(u·x) = R(u·y). If k > C then u·x, u·y ∈ B k−C . Our symmetry assumption and clause (v) of Lemma 2.3 imply that there is h ∈ G with θ k−C (u · x) = hu · x and θ k−C (u · y) = hu · y (as in Case 1, we again use the fact that u · x, u · y ∈ E k−C since x, y ∈ X ′ ). Then L(u · x)(k) is the letter in R(hu · x) which follows the first occurrence of 4, and L(u · y)(k) is the letter in R(hu · y) which follows the first occurrence of 4. Therefore R(hu · x) = R(hu · y).

Counter-examples for f-invariant and sofic entropies
In this section we prove Propositions 1.2 and 1.3. We handle f-invariant entropy first.
We remind the reader the definition of an induced action. Let G be a countable group and let H ≤ G be a subgroup of finite index. Let G/H denote the set of left H-cosets {gH : g ∈ G}, and let ζ be the uniform probability measure on G/H. We let G act on (G/H, ζ) by defining g · (aH) = gaH. Fix any function σ : G/H → G with σ(H) = 1 G and σ(gH) ∈ gH for all g ∈ G. We abuse notation and let σ(g) denote σ(gH) for g ∈ G. Let γ : (G/H) × G → H be the cocycle defined by γ(aH, g) = σ(ga) −1 · g · σ(a).
If H acts by measure preserving bijections on a probability space (Y, ν), then we define a measure preserving action of G on the probability space ((G/H) × Y, ζ × ν) by g · (aH, y) = (gaH, γ(aH, g) · y).
One can check that this is a well defined action of G. It is called the action of G induced from H (Y, ν). It is well known that the induced action of G is ergodic if and only if H (Y, ν) is ergodic [19].