Lemma 5.3 — Vector Sum to simultaneous VC-controlled gap
OpenNearLogSetCover966.Main.Supplement.lemma_5_3Fix a positive dimension coefficient . There are , an exponent and one deterministic program, uniform over all vector-sum instances with , and
It outputs the actual §5 incidence construction using separator dimension , where . The same output has exactly indexed sets, universe at most , time at most , both gap implications, and
The separator size and zero-root bounds of the polynomial-evaluation variant at threshold are included as output properties. The program receives only the vector instance and the exact integer weight threshold; it computes the separator dimension itself. This support result supplies both VC bounds for Theorem 5.4.
Formalization Note Binary encodings and the inherited finite incidence and actual-machine conventions are used. All resource witnesses are uniform as specified above.
Differences from the source:
- encoding: fixed coefficient in D=O(k log n) → L is fixed before alpha, C, e, the program and all instances; reason: these constants may depend on the fixed dimension envelope and never on a particular input
- encoding: Section 5 construction with ell=ceil(log2 n/h) → the same neighborhood-class construction at t=floor h, with ell=ceil(log2 n/t) and separator/root conclusions for t; reason: integer assignment weights make the rejecting assignments and strict cover threshold identical at h and floor h; t remains in the entire source admissible range, and bounds at t imply the displayed bounds at h
- encoding: real h and the positive logarithmic regime → real h retained, n>2, only floor h supplied in the constructor code; reason: the program computes the least integer ell with n≤2^(ell floor h) by integer comparisons; no independently supplied separator dimension or exact-real comparison oracle is needed
import Definitions.Def_NearLogSetCover966_Main_Supplement_VC set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
/-- Lemma 5.3, with the dimension constant fixed before all instances.
Use the exact integer weight threshold t=floor h. The program computes the
separator dimension ceil(log₂ n/t); it receives no separately supplied dimension.
For integer cover sizes, strict soundness at t is exactly strict soundness at h. -/
theorem lemma_5_3 :
∀ L : ℝ, 0 < L → ∃ (α C : ℝ) (e : ℕ) (P : Program), 0 < α ∧ 0 < C ∧
∀ (I : VectorSum) (h : ℝ), 2 ≤ I.k → 2 < I.n →
(I.D : ℝ) ≤ L * I.k * log2 I.n → (I.k : ℝ) ≤ h →
h ≤ α * log2 I.n / (I.k * log2 (log2 I.n)) →
let t := (⌊h⌋₊ : ℝ)
∃ H : HashFamily I.D ⌈log2 I.n / t⌉₊,
H.avoids ((t/I.k)^I.k) ∧
(H.maps.length : ℝ) ≤ ⌈(I.D : ℝ) * (t/I.k)^I.k / ⌈log2 I.n/t⌉₊⌉₊ ∧
(∀ z : Vec I.D, z ≠ 0 →
(H.zeros z : ℝ) < (I.D : ℝ) / ⌈log2 I.n/t⌉₊) ∧
let J := vcInstance I H h
J.sets.length = I.k*I.n ∧ (J.n : ℝ) ≤ C*(I.n : ℝ)^e ∧
(I.yes → coverSmall J I.k) ∧ (¬ I.yes → coverLarge J h) ∧
(primalVC J : ℝ) ≤ C * I.k * h * log2 h ∧
(dualVC J : ℝ) ≤ C*h ∧
P.runs (vsEncode I ++ thresholdCode h) (scEncode J) (C*(I.n : ℝ)^e) := by sorry
end NearLogSetCover966.Main.Supplement