Low-acceptance local testability under the axis-parallel hyperplane test
DefinitionLowAccLTC_Supplement_IsLALTCHyperplaneLet be a linear code and let be its -fold tensor power. The axis-parallel hyperplane test samples a direction and a value uniformly, then compares the restriction of a word to the local tensor code on the hyperplane . Write
For nonempty coordinate and direction sets, the tensor code is an -low-acceptance locally testable code under this test if , the function is nonnegative and monotone nondecreasing on , and every word satisfies
This specializes Definition 2.3 to the vertex test used for tensor codes in Section 5.1.
Formalization Note Directions and coordinates are zero-based Fin types, and both choices are uniform. The source type is represented by a real-valued function together with nonnegativity and monotonicity on the closed unit interval.
import Definitions.Def_LowAccLTC_tensorCode
namespace LowAccLTC
namespace Supplement
/-! Ben Yaacov, Dikstein, Liu, *Randomness-Efficient Robust LTCs in the Low-Acceptance Regime
from HDXs*, unpublished manuscript (sha256 04242e17…); page references are printed pages
(PDF page − 3). -/
variable {F : Type*} [Field F] {n : ℕ}
/-- `B^{⊗k}` is an `(ε, φ)`-LA LTC (low-acceptance locally testable code) with respect to
the axis-parallel hyperplane test (Definition 2.3, p.14 = PDF p.17, specialized as in §5.1,
p.43 = PDF p.46): for every word `f`, if
`x := 1 - E_{i,a}[dist(f|_{x_i=a}, B^{⊗(k-1)})] ≥ ε`, then
`1 - dist(f, B^{⊗k}) ≥ φ(x)`.
**Formalization Note.** The test samples `i : Fin k` and `a : Fin n` uniformly, so the coordinate
and direction types are required to be nonempty. The source's function `φ : [0,1] → ℝ+` is encoded
as a real-valued function that is nonnegative and monotone on `Set.Icc 0 1`. -/
def IsLALTCHyperplane (B : Submodule F (Fin n → F)) (k : ℕ) (ε : ℝ) (φ : ℝ → ℝ) : Prop :=
0 < n ∧ 0 < k ∧ 0 < ε ∧ ε < 1 ∧
(∀ x ∈ Set.Icc (0 : ℝ) 1, 0 ≤ φ x) ∧ MonotoneOn φ (Set.Icc 0 1) ∧
∀ f : (Fin k → Fin n) → F, ε ≤ 1 - hyperplaneTestDist B f →
φ (1 - hyperplaneTestDist B f) ≤ 1 - relDistTo Finset.univ f (tensorCode B k)
end Supplement
end LowAccLTC