Lemma 4.1 — Dictionary size on a spectral group walk
OpenFiniteGroupTesting.LinearQuery.Supplement.lemma_4_1group-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1property-testingquery-complexity
Let be a group of order , and fix signed generators whose symmetric Cayley operator has spectral accuracy . For , start at a uniform group element and take independent uniform signed steps. If is the set of visited labels, including the start, then
This is the dictionary-size guarantee conditioned on a fixed good spectral setup. It is uniform in the group, the spectral tuple and the allowed dictionary length.
Differences from the source:
- generalization: the randomly selected generator tuple, conditioned on its spectral event → every fixed positive-length generator tuple satisfying that spectral bound; reason: the collision estimate is pointwise in the fixed Cayley operator and therefore specializes to the stated conditional law
- encoding: an absolute n_0 and fixed c_D<=1/500, lambda_0<=1/3000 → n_0=1500, c_D=1/500 and lambda_0=1/3000; reason: the proof on pp. 25–26 gives E[C_coll]/m<=3/1000 at these values
- encoding: a genuine input group table ([n],*) whose dictionary walk steps by the queried inverse candidates t_i = s_i^(n-1) → an arbitrary finite group G whose walk steps by s_i and s_i^(-1); reason: on a genuine group t_i = s_i^(-1) by Lagrange (p. 25), and every group table on [n] is such a finite group, so the source instance is covered
Preamble
import Definitions.Def_FiniteGroupTesting_LinearQuery_Supplement_UpperTester set_option autoImplicit false
Formal statement
namespace FiniteGroupTesting.LinearQuery.Supplement
theorem lemma_4_1 {G : Type} [Group G] [Fintype G] [DecidableEq G]
(hn : 1500 ≤ Fintype.card G) {k : ℕ} (hk : 0 < k) (s : Fin k → G)
(hs : CayleyExpansion s spectralAccuracy) (m : ℕ) (hm : 1 ≤ m)
(hmn : (m : ℝ) ≤ (Fintype.card G : ℝ) / 500) :
(99/100 : ℝ) ≤ uniformProbability (fun sample : G × (Fin m → Signed k) =>
(m : ℝ) / 2 ≤ ((walk (· * ·) (signedMark s) sample.1
(List.ofFn sample.2)).toFinset.card : ℝ)) := by sorry
end FiniteGroupTesting.LinearQuery.Supplement
Source
Nader Bshouty, STOC 2027 submission #622 (October 2026), p. 25, Lemma 4.1