Lemma 4.6 — Code-assisted gap reduction (corrected: empty-universe factors)
OpenNearLogSetCover966.Main.Supplement.lemma_4_6p2o-batch-stoc27sp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
For all inputs of §4.2, one deterministic program computes the actual distributed clause construction. With , it produces indexed sets, retains both implications and , and has the uniform bounds
The supplied tables must be injective and list-recoverable, , and the separator is constructed as part of the algorithm. No property of its output is an input assumption.
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:
- correction: u0^c in size and running-time envelopes → max(1,u0)^c in both envelopes; reason: take n=q=2, k=ell=2, h=c=4, empty universe, identity additive code over F2; z=0 has empty Gamma and its unique empty witness map contributes an all-variable clause, so the actual universe is nonempty but the printed bound is zero
- encoding: least power-of-two field cardinality at least n → least power of two at least max(2,n); reason: q=1 is not a field cardinality; the n=1 input is retained using F2
- encoding: h,c thresholds and source O exponents → real h via its exact integer threshold, natural c, and uniform C,e before all inputs; reason: counts permit floor c without changing any list; h controls integer weights, and all bounds describe the same actual construction
Preamble
import Definitions.Def_NearLogSetCover966_Main_Supplement_CodeReduction set_option autoImplicit false
Formal statement
namespace NearLogSetCover966.Main.Supplement
/-- Lemma 4.6. At u₀=0, replace the zero universe factor by 1.
The actual clause construction, its completeness and strict soundness are retained. -/
theorem lemma_4_6 :
∃ (C : ℝ) (e : ℕ) (P : Program), 0 < C ∧ 1 ≤ e ∧
∀ (I : SCInstance) (k s ell c : ℕ) (h : ℝ) (f : Tables k s ell),
1 ≤ k → 1 ≤ I.sets.length → I.n ≤ I.sets.length → 1 ≤ ell → 1 ≤ c →
(k+ell : ℕ) ≤ h → LeastPower s (max 2 I.sets.length) → GoodCode f h c →
∃ (d : ℕ) (H : HashFamily (ell*s) d),
H.avoids (h^(k+ell)) ∧
let J := codeInstance I f H h c
J.sets.length = (k+ell)*2^s ∧
(J.n : ℝ) ≤ C * h^(C*(k+ell)*h) * (max 1 I.n : ℕ)^c * (log2 ((2:ℝ)^s)) ∧
(coverSmall I k → coverSmall J (k+ell)) ∧
(coverLarge I k → coverLarge J h) ∧
P.runs (codeReductionInput I f h c) (scEncode J)
(C * ((2:ℝ)^s * h^((k+ell)*h) * (max 1 I.n : ℕ)^c + 1)^e) := by sorry
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Lemma 4.6, printed p.19 (PDF p.21)