Theorem 5.1 — tensor codes are -low-acceptance locally testable
OpenLowAccLTC.Supplement.theorem_5_1_tensor_low_acceptancecoding-theorylocally-testable-codesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1tensor-codes
Let be a field, let , let be a linear code whose relative distance is at least , and let . Suppose
Then is an -low-acceptance locally testable code under the uniform axis-parallel hyperplane test. Explicitly, for every word , if
then
Thus even when the average local agreement is only at least , it certifies global agreement at least one quarter as large.
Formalization Note is the natural logarithm. The published HasRelDistAtLeast predicate gives the distance parameter lower-bound semantics, and directions and coordinates are represented by zero-based Fin types.
Differences from the source:
- generalization: C₀ is a linear code of distance δ → B has relative distance at least δ, with 0 ≤ δ ≤ 1; reason: the conclusion is monotone in the code's actual relative distance, and taking δ equal to the actual distance recovers every source instance
- encoding: a code has block length n and tensor order r in ℕ → n and r are natural numbers and the LA-LTC predicate records 0 < n and 0 < r; reason: the source's relative Hamming distance and uniform vertex test require nonempty coordinate and direction sets, and the displayed rank bound already forces r > 0
- encoding: ε < 1/2 in Theorem 5.1, under Definition 2.3 where ε ∈ (0,1) → separate hypotheses 0 < ε and ε < 1/2; reason: positivity is implicit in the source definition and is also required for the displayed reciprocal and logarithm
- encoding: log and the sets [n] and [r] → Real.log and zero-based types Fin n and Fin r; reason: the base mission's natural-log and finite-coordinate conventions, with the same uniform test and tensor code
- encoding: φ:[0,1]→ℝ+ is monotone nondecreasing and the LA-LTC implication holds → IsLALTCHyperplane represents φ on ℝ and bundles its nonnegativity and monotonicity on [0,1], the parameter ranges, and the implication; reason: this is the direct real-valued Lean encoding of Definition 2.3, and x↦x/4 satisfies the bundled conditions
Preamble
import Definitions.Def_LowAccLTC_Supplement_IsLALTCHyperplane
Formal statement
namespace LowAccLTC
namespace Supplement
/-- **Theorem 5.1** (Ben Yaacov–Dikstein–Liu,
*Randomness-Efficient Robust LTCs in the Low-Acceptance Regime from HDXs*, unpublished
manuscript, sha256 04242e17…, p.43 = PDF p.46).
Let `0 < n`, `0 < ε < 1/2` and
`r ≥ 10^34 / ε^16 · log²(5·10^5 / ε²)`. If the linear code `B ⊆ F^[n]` has relative
distance at least `δ ∈ [0,1]` and `δ^r ≥ 1 - ε²/36`, then `B^{⊗r}` is an
`(ε, x ↦ x/4)`-low-acceptance locally testable code with respect to the vertex test, which in
this setting is the uniform axis-parallel hyperplane test.
**Formalization Note.** `log` is the natural logarithm. The paper's "distance `δ`" is used with
lower-bound semantics through `HasRelDistAtLeast`; the conclusion is monotone under increasing
the actual distance. Coordinates and tensor directions are zero-based `Fin` types. -/
theorem theorem_5_1_tensor_low_acceptance {F : Type*} [Field F] (n : ℕ) (hn : 0 < n)
(B : Submodule F (Fin n → F)) (δ ε : ℝ) (hδ : 0 ≤ δ ∧ δ ≤ 1)
(hB : HasRelDistAtLeast B δ) (hε0 : 0 < ε) (hε : ε < 1 / 2) (r : ℕ)
(hr : (10 : ℝ) ^ 34 / ε ^ 16 * (Real.log (5 * (10 : ℝ) ^ 5 / ε ^ 2)) ^ 2 ≤ (r : ℝ))
(hpow : 1 - ε ^ 2 / 36 ≤ δ ^ r) :
IsLALTCHyperplane B r ε (fun x => x / 4) := by sorry
end Supplement
end LowAccLTC
Source
Ben Yaacov, Dikstein, Liu, Randomness-Efficient Robust LTCs in the Low-Acceptance Regime from HDXs (manuscript, sha256 04242e17…), Theorem 5.1, p.43 (PDF p.46); Definition 2.3, p.14 (PDF p.17)