Two-list Orthogonal Vectors with lists of lengths , and its subfunctions on one vector
DefinitionHypercliqueAC0_FixedDepth_Supplement_TwoListOVFix natural numbers . An instance consists of a first list and a second list of vectors in , one Boolean variable per coordinate of each vector. Two-list Orthogonal Vectors is
For a function of these variables and a vector of the first list, a subfunction of on vector is the function of obtained by fixing every other variable to a constant . The definition records the set of distinct such functions, as ranges over all assignments to the other variables.
These objects let one count the subfunctions of two-list on one vector, which feeds Nechiporuk's formula lower bound in the depth-three wire bound.
Formalization Note The variables are indexed by with represented by Fin n. The set of subfunctions is the image of all full assignments under y\mapsto(z\mapsto f(\text{yiz})); the values of on vector are overwritten, so this is exactly the set of functions obtained by fixing the other variables. Lists of unequal lengths are allowed, unlike the published ErrAmpOV.kOV.
import Mathlib
noncomputable section
namespace HypercliqueAC0.FixedDepth.Supplement
attribute [local instance] Classical.propDecidable Classical.decEq
/-- The variables of two-list Orthogonal Vectors: coordinate `q` of vector `i` of the first list
is `.inl (i, q)`, coordinate `q` of vector `j` of the second list is `.inr (j, q)`. -/
abbrev TwoListVar (n₁ n₂ d : ℕ) := (Fin n₁ × Fin d) ⊕ (Fin n₂ × Fin d)
/-- Two-list `2-OV` with list lengths `n₁, n₂` (Lemma 8.1, p. 24, PDF 26; §3.1, p. 10, PDF 12):
one iff some vector of the first list and some vector of the second list are orthogonal, i.e.
have no coordinate where both are one. -/
def twoListOV (n₁ n₂ d : ℕ) (x : TwoListVar n₁ n₂ d → Bool) : Bool :=
decide (∃ i : Fin n₁, ∃ j : Fin n₂, ∀ q : Fin d,
x (.inl (i, q)) = false ∨ x (.inr (j, q)) = false)
/-- The assignment that agrees with `y` everywhere except on vector `i` of the first list, which
is set to `z`. -/
def setFirstVector {n₁ n₂ d : ℕ} (i : Fin n₁) (y : TwoListVar n₁ n₂ d → Bool)
(z : Fin d → Bool) : TwoListVar n₁ n₂ d → Bool
| .inl (i', q) => if i' = i then z q else y (.inl (i', q))
| .inr v => y (.inr v)
/-- The subfunctions of `f` on vector `i` of the first list (§3.1, p. 10, PDF 12: fix every
variable outside the vector to a constant): the set of distinct functions
`z ↦ f (z on vector i, y elsewhere)` as `y` ranges over all assignments. The values of `y` on
vector `i` itself are overwritten, so `y` effectively ranges over the assignments to the other
variables. -/
def subfunctionsOnFirstVector {n₁ n₂ d : ℕ} (f : (TwoListVar n₁ n₂ d → Bool) → Bool)
(i : Fin n₁) : Finset ((Fin d → Bool) → Bool) :=
Finset.univ.image (fun y => fun z => f (setFirstVector i y z))
end HypercliqueAC0.FixedDepth.Supplement