Lemma 6.2 — Hidden-copy instances are one-sixth far
OpenFiniteGroupTesting.LinearQuery.Supplement.lemma_6_2group-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1property-testingquery-complexity
For all sufficiently large consecutive prime pairs with , put and . Embed into the labels and write its addition on the square of its image. Every deterministic completion outside that square satisfies
for every group operation on all labels. In particular every table in the source's NO distribution is -far. The threshold on is uniform in the embedding, completion and comparison group.
Differences from the source:
- encoding: labels [n]={1,...,n} → Fin n with zero representing paper label 1; reason: bijective relabelling preserves all tables, distances and query policies
- generalization: constant outside completion equal to paper label 1 → every deterministic outside completion; reason: the proof lower-bounds disagreements inside the hidden image squared, independently of outside entries
- encoding: additive F_p and F_q coordinates → addition modulo p and q on Fin p and Fin q; reason: these are additive coordinate labellings of exactly the same prime fields
Preamble
import Definitions.Def_FiniteGroupTesting_LinearQuery_Supplement_TranscriptModel set_option autoImplicit false
Formal statement
namespace FiniteGroupTesting.LinearQuery.Supplement
theorem lemma_6_2 :
∃ N : ℕ, ∀ p q : ℕ, N ≤ p → ConsecutivePrimes p q → q - p ≤ 600 →
∀ (f : PairH p q ↪ Fin (p ^ 2 * q ^ 3)) (outside : Table (p ^ 2 * q ^ 3)),
Far (1/6 : ℝ) (encodedTable pairAddH f outside) := by sorry
end FiniteGroupTesting.LinearQuery.Supplement
Source
Nader Bshouty, STOC 2027 submission #622 (October 2026), p. 35, Lemma 6.2