Følner sets and polynomial growth

DefinitionBall in the word metric#✓fully proved

For a finite subset \(S\) of a group \(\Gamma\) and a natural number \(n\), the ball \(B_S(n)\) of radius \(n\) is the set of products of at most \(n\) elements of \(S \cup S^{-1}\), the empty product \(1\) included.

def wordBall {Γ : Type*} [Group Γ] (S : Finset Γ) (n : ℕ) : Set Γ :=
  {g | ∃ l : List Γ, l.length ≤ n ∧ (∀ x ∈ l, x ∈ S ∨ x⁻¹ ∈ S) ∧ l.prod = g}

Used by 1

Used byPolynomial growth with respect to a finite subset

DefinitionPolynomial growth with respect to a finite subset#✓fully proved

Let \(S\) be a finite subset of a group \(\Gamma\), and let \(B_S(n)\) be the ball of radius \(n\) for \(S\), the set of products of at most \(n\) elements of \(S \cup S^{-1}\). Then \(\Gamma\) has polynomial growth with respect to \(S\) if there are natural numbers \(C\) and \(d\) such that for every natural number \(n\) the ball \(B_S(n)\) has at most \(C\,(n + 1)^d\) elements.

def HasPolynomialGrowth {Γ : Type*} [Group Γ] (S : Finset Γ) : Prop :=
  ∃ C d : ℕ, ∀ n : ℕ, (wordBall S n).encard ≤ ((C * (n + 1) ^ d : ℕ) : ℕ∞)

Uses 1 · Used by 1

Statement usesBall in the word metric

Used byVaillant's question on Følner exhaustions of polynomial size (Kourovka 14.27)

DefinitionBoundary of a finite subset of a group#✓fully proved

For a group \(\Gamma\) and finite subsets \(S\) and \(F\) of \(\Gamma\), the boundary of \(F\) with respect to \(S\) is the set \(\partial F = \{\gamma \in \Gamma \setminus F : \gamma s \in F \text{ for some } s \in S\}\).

def boundary {Γ : Type*} [Group Γ] (S F : Finset Γ) : Set Γ :=
  {γ | γ ∉ F ∧ ∃ s ∈ S, γ * s ∈ F}

Used by 1

Used byVaillant's question on Følner exhaustions of polynomial size (Kourovka 14.27)

DefinitionVaillant's question on Følner exhaustions of polynomial size (Kourovka 14.27)#✓fully proved

The statement that for every group \(\Gamma\) generated by a finite subset \(S\) the following holds: if there are finite subsets \(F_0 \subsetneq F_1 \subsetneq F_2 \subsetneq \cdots\) of \(\Gamma\) whose union is \(\Gamma\) such that \(|\partial F_k| / |F_k| \to 0\) as \(k \to \infty\), where \(\partial F_k\) is the boundary of \(F_k\) with respect to \(S\), and such that for some real \(c \ge 0\) and some natural number \(d \ge 1\) we have \(|F_k| \le c\,(k + 1)^d\) for every \(k\), then \(\Gamma\) has polynomial growth with respect to \(S\).

The Kourovka Notebook indexes the sets from \(F_1\), so its size condition \(|F_k| \le c\,k^d\) reads \(|F_k| \le c\,(k + 1)^d\) here.

def polynomialFolnerExhaustionImpliesPolynomialGrowth : Prop :=
  ∀ (Γ : Type) [Group Γ] (S : Finset Γ), Subgroup.closure (S : Set Γ) = ⊤ →
    ∀ F : ℕ → Finset Γ, (∀ k, F k ⊂ F (k + 1)) → (∀ γ, ∃ k, γ ∈ F k) →
      Filter.Tendsto (fun k => ((boundary S (F k)).ncard : ℝ) / (F k).card) Filter.atTop
        (nhds 0) →
      (∃ (c : ℝ) (d : ℕ), 0 ≤ c ∧ 1 ≤ d ∧ ∀ k, ((F k).card : ℝ) ≤ c * ((k : ℝ) + 1) ^ d) →
      HasPolynomialGrowth S

Uses 2 · Used by 1

Statement usesPolynomial growth with respect to a finite subset · Boundary of a finite subset of a group

Used byFølner exhaustions of polynomial size need not give polynomial growth

TheoremFølner exhaustions of polynomial size need not give polynomial growth#●ready to prove

There exist a group \(\Gamma\) generated by a finite subset \(S\) and finite subsets \(F_0 \subsetneq F_1 \subsetneq F_2 \subsetneq \cdots\) of \(\Gamma\) whose union is \(\Gamma\) such that \(|\partial F_k| / |F_k| \to 0\) as \(k \to \infty\), where \(\partial F_k\) is the boundary of \(F_k\) with respect to \(S\), and such that for some real \(c \ge 0\) and some natural number \(d \ge 1\) we have \(|F_k| \le c\,(k + 1)^d\) for every \(k\), while \(\Gamma\) does not have polynomial growth with respect to \(S\). That is, the answer to Kourovka Problem 14.27 is negative.

By Bardakov, every finitely generated group of intermediate growth (such groups exist by Grigorchuk) has such a sequence of subsets.

public theorem_wanted polynomialFolnerExhaustionImpliesPolynomialGrowth_refuted :
    ¬ polynomialFolnerExhaustionImpliesPolynomialGrowth

Sources

• E. I. Khukhro and V. D. Mazurov (eds.), Unsolved Problems in Group Theory: The Kourovka Notebook, 21st issue, arXiv:1401.0300v49 (2026), Archive of Solved Problems, Problem 14.27 (A. G. Vaillant); resolution: V. G. Bardakov, Algebra and Logic 40 (2001), no. 1, 12-16, Kourovka Archive, Problem 14.27: every group of intermediate growth has such a sequence (answer: No, not always).

Uses 1

Statement usesVaillant's question on Følner exhaustions of polynomial size (Kourovka 14.27)

4 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.