Lemma 2.10 — Every finite group has logarithmically many generators
OpenAMRangeAvoid.Characterization.Supplement.lemma_2_10complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
For every finite group , including the trivial group, there exists a finite subset that generates and satisfies
The result is uniform over all finite groups, rather than restricted to permutation groups. In the trivial group the empty set suffices. It supplies the generator-count bound used by the graph reduction.
Differences from the source:
- encoding: a finite group and the ceiling of its binary logarithmic order → a group with Fintype, subgroup closure, and Nat.clog 2 of its cardinality; reason: these express the same generating condition and integer bound, including order one
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Complexity import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement
theorem lemma_2_10 (A : Type*) [Group A] [Fintype A] :
∃ Γ : Finset A, Subgroup.closure (Γ : Set A) = ⊤ ∧
Γ.card ≤ Nat.clog 2 (Fintype.card A) := by sorry
end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Lemma 2.10, printed p.11 (PDF p.13); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf