hypercube_coord_reflect_maj
For any coordinate subset T of Fin n and any Boolean vectors x, y, z : Fin n → Bool, the coordinate reflection of their componentwise majority equals the componentwise majority of their coordinate reflections.
Statement
theorem hypercube_coord_reflect_maj {n : ℕ} (T : Finset (Fin n)) (x y z : Fin n → Bool) :
hypercube_coord_reflect T (hypercube_maj x y z) =
hypercube_maj (hypercube_coord_reflect T x) (hypercube_coord_reflect T y) (hypercube_coord_reflect T z)- Source
- arXiv:2610.38287 Proof of Theorem 2
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hypercube_coord_reflectGiven a coordinate subset T of Fin n and a Boolean vector x : Fin n → Bool, hypercube_coord_reflect T x is the Boolean vector obtained by…
- hypercube_majGiven three Boolean vectors x, y, z : Fin n → Bool, hypercube_maj x y z is their componentwise majority vector, defined by (x ⊓ y) ⊔ (y ⊓…
- Used by 1
- hypercube_d_convex_iff_majority_closed_and_has_relative_opposite_pairLet X : Finset (Fin n → Bool) be a nonempty finite subset of vertices of the unit hypercube. Then X is D-convex (hypercube_is_d_convex X)…
Read back from the Lean
For every natural number $n$, every subset $T \subseteq \mathrm{Fin}(n)$ (as a Finset), and any three Boolean vectors $x, y, z : \mathrm{Fin}(n) \to \mathrm{Bool}$, coordinate reflection along $T$ commutes with the coordinate-wise majority function: reflecting the majority of $x, y, z$ across the coordinates in $T$ yields the same vector as taking the majority of the reflections of $x$, $y$, and $z$ across $T$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that coordinate reflection along $T$ commutes with the componentwise majority operation by reducing vector equality to coordinate-wise equality. After unfolding the definitions, it splits into two cases depending on whether the coordinate index $i$ belongs to $T$. If $i \\notin T$, coordinates are unchanged and both sides are syntactically identical; if $i \\in T$, all three coordinates are negated, and the identity is verified by exhaustively checking all eight truth assignments for the three Boolean coordinates.
To prove the vectors are equal, it suffices to show that they agree coordinate-wise, which simplifies to an identity on Boolean values at an arbitrary coordinate $i$.
By function extensionality (`ext i`), two Boolean vectors are equal if and only if they agree at every coordinate $i \\in \\mathrm{Fin}\\ n$. Unfolding the definitions of coordinate reflection (`hypercube_coord_reflect`) and the majority function (`hypercube_maj`), and distributing evaluation across the pointwise infima and suprema using `Pi.inf_apply` and `Pi.sup_apply`, expresses each side in terms of min, max, and conditional coordinate negation at index $i$.
uses
hypercube_coord_reflect,hypercube_maj,Pi.inf_apply,Pi.sup_applyext i simp only [hypercube_coord_reflect, hypercube_maj, Pi.inf_apply, Pi.sup_apply]
The goal splits into two cases based on whether coordinate $i$ belongs to $T$.
The `split_ifs` tactic branches on the condition $i \\in T$ from the definition of coordinate reflection, yielding two subgoals: one where $i \\in T$ (where coordinates are negated) and one where $i \\notin T$ (where coordinates remain unchanged).
split_ifsWhen $i \\in T$, the majority of the negated coordinates equals the negation of their majority.
When $i \\in T$, each of the three coordinates is negated. Since $x(i), y(i), z(i) \\in \\mathrm{Bool}$, performing an exhaustive case analysis across their $2^3 = 8$ possible truth value combinations (`cases x i <;> cases y i <;> cases z i`) reduces each case to a trivial Boolean computation, which is closed by reflexivity (`rfl`).
· cases x i <;> cases y i <;> cases z i <;> rfl
When $i \\notin T$, the equality holds trivially.
When $i \\notin T$, coordinate reflection does not alter any coordinate. Both sides evaluate to the identical Boolean expression $\\max(\\max(\\min(x(i), y(i)), \\min(y(i), z(i))), \\min(z(i), x(i)))$, closing the goal immediately by reflexivity (`rfl`).
· rfl
Pi.inf_apply- The pointwise infimum (minimum or conjunction) of two functions evaluates at an index to the infimum of their individual values: $(f ⊓ g)(i) = f(i) ⊓ g(i)$.
Pi.sup_apply- The pointwise supremum (maximum or disjunction) of two functions evaluates at an index to the supremum of their individual values: $(f ⊔ g)(i) = f(i) ⊔ g(i)$.
hypercube_coord_reflect- The coordinate reflection of a Boolean vector $x$ along a subset $T$, defined by negating the $i$-th coordinate if $i ∈ T$ and leaving it unchanged otherwise.
hypercube_maj- The componentwise majority function on three Boolean vectors, defined as $(x ⊓ y) ⊔ (y ⊓ z) ⊔ (z ⊓ x)$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Coordinate reflection commutes with the majority operation on Boolean vectors. -/theorem hypercube_coord_reflect_maj {n : ℕ} (T : Finset (Fin n)) (x y z : Fin n → Bool) : hypercube_coord_reflect T (hypercube_maj x y z) = hypercube_maj (hypercube_coord_reflect T x) (hypercube_coord_reflect T y) (hypercube_coord_reflect T z) := by ext i simp only [hypercube_coord_reflect, hypercube_maj, Pi.inf_apply, Pi.sup_apply] split_ifs · cases x i <;> cases y i <;> cases z i <;> rfl · rfl