AFTD Auto-Formalizing Theoretical Domains

hypercube_coord_reflect_maj

theoremverified

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

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.

  1. 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$.

    lines 5–6

    uses hypercube_coord_reflect, hypercube_maj, Pi.inf_apply, Pi.sup_apply

      ext i
      simp only [hypercube_coord_reflect, hypercube_maj, Pi.inf_apply, Pi.sup_apply]
  2. 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).

    line 7

      split_ifs
  3. When $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`).

    line 8

      · cases x i <;> cases y i <;> cases z i <;> rfl
  4. 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`).

    line 9

      · 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

/-- 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
See it in the graphDiscuss this resultChallenge it