Lemma 8.1: fixing all of two-list OV except one vector leaves at least subfunctions
OpenHypercliqueAC0.FixedDepth.Supplement.lemma_8_1Let and put
Let be integers, and consider two-list Orthogonal Vectors on a first list of vectors and a second list of vectors from : it outputs one exactly when some vector of the first list and some vector of the second list have no coordinate where both are one. Fix any vector of the first list. As the variables outside vector range over all assignments, the resulting functions of vector take at least
distinct values, i.e. there are at least that many distinct subfunctions on vector .
This count is the input to Nechiporuk's formula lower bound in the proof of the depth-three wire bound for .
Formalization Note The count is the cardinality of the set of distinct functions , not the number of assignments. is natural-number division.
Differences from the source:
- encoding: two lists of vectors from → Boolean variables indexed by ; reason: a relabeling bijection preserves every instance
- encoding: "distinct functions of this vector" after fixing the other variables → the cardinality of the image of all full assignments under the map sending an assignment to the function of vector with the other variables taken from it; reason: the assignment's own values on vector are overwritten, so the image is exactly the set of subfunctions
- reading: "outside one vector of the first list" → for every vector of the first list; reason: the universal reading is the stronger one, and the two readings are equivalent because permuting the first list preserves the function
import Mathlib import Definitions.Def_HypercliqueAC0_FixedDepth_Supplement_TwoListOV noncomputable section
namespace HypercliqueAC0.FixedDepth.Supplement
open scoped BigOperators
/-- Lemma 8.1, p. 24 (PDF 26). `M_d = C(d, ⌊d/2⌋)` (`d / 2` is natural division). For every
vector `i` of the first list, the number of distinct functions of that vector obtained by fixing
all other variables of two-list `2-OV` is at least `∑_{s=0}^{min(n₂, M_d)} C(M_d, s)`. -/
theorem lemma_8_1 (d : ℕ) (hd : 2 ≤ d) (n₁ n₂ : ℕ) (hn₁ : 1 ≤ n₁) (hn₂ : 1 ≤ n₂)
(i : Fin n₁) :
∑ s ∈ Finset.range (min n₂ (Nat.choose d (d / 2)) + 1), Nat.choose (Nat.choose d (d / 2)) s ≤
(subfunctionsOnFirstVector (twoListOV n₁ n₂ d) i).card := by sorry
end HypercliqueAC0.FixedDepth.Supplement