AFTD Auto-Formalizing Theoretical Domains

four_block_concat_reduced

theoremverified

For any natural number m and Boolean functions g0, g1, g2, g3 on Fin m → ZMod 2, the four-block concatenation four_block_concat g0 g1 g2 (g1 + g2 + g3) is identically equal to the function sending v to (1 + y1) * (1 + y2) * g0 x + y1 * g1 x + y2 * g2 x + y1 * y2 * g3 x, where x = fun i => v (Fin.castAdd 2 i), y1 = v (Fin.natAdd m 0), and y2 = v (Fin.natAdd m 1).

Statement

theorem four_block_concat_reduced {m : ℕ} (g0 g1 g2 g3 : (Fin m → ZMod 2) → ZMod 2) :
    four_block_concat g0 g1 g2 (g1 + g2 + g3) =
    fun v =>
      let x : Fin m → ZMod 2 := fun i => v (Fin.castAdd 2 i)
      let y1 : ZMod 2 := v (Fin.natAdd m 0)
      let y2 : ZMod 2 := v (Fin.natAdd m 1)
      (1 + y1) * (1 + y2) * g0 x + y1 * g1 x + y2 * g2 x + y1 * y2 * g3 x
Source
arXiv:2610.29807, Lemma 3.1
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • four_block_concatThe four-block concatenation four_block_concat of four Boolean functions f0, f1, f2, f3 : (Fin m → ZMod 2) → ZMod 2 is the Boolean…
Used by 1

Read back from the Lean

For any natural number $m$ and any functions $g_0, g_1, g_2, g_3 : (\mathrm{Fin}\ m \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$, the function $\mathrm{four\_block\_concat}\ g_0\ g_1\ g_2\ (g_1 + g_2 + g_3)$ is equal to the function mapping each $v : \mathrm{Fin}\ (m + 2) \to \mathbb{Z}/2\mathbb{Z}$ to: $$(1 + y_1)(1 + y_2) g_0(x) + y_1 g_1(x) + y_2 g_2(x) + y_1 y_2 g_3(x)$$ where: - $x : \mathrm{Fin}\ m \to \mathbb{Z}/2\mathbb{Z}$ is defined by $x(i) = v(\mathrm{Fin.castAdd}\ 2\ i)$ (the restriction of $v$ to the first $m$ indices), - $y_1 = v(\mathrm{Fin.natAdd}\ m\ 0)$ (the element at index $m$), and - $y_2 = v(\mathrm{Fin.natAdd}\ m\ 1)$ (the element at index $m + 1$).

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 identity is proved by pointwise evaluation and polynomial simplification over ZMod 2. By function extensionality, the functions are evaluated on an arbitrary input vector v, reducing the theorem to an equality between two polynomials in the coordinates y₁, y₂ and the function values gᵢ x. Expanding both sides into ring normal form and simplifying using the characteristic 2 identity 2 = 0 eliminates the cross terms with coefficient 2, showing that the two functions are identically equal.

  1. The equality of functions reduces to an algebraic identity between the expanded expressions evaluated at an arbitrary input vector v.

    Applying function extensionality (`funext`) introduces an arbitrary vector v : Fin (m + 2) → ZMod 2. Unfolding the definition of `four_block_concat` and rewriting function addition pointwise with `Pi.add_apply` replaces (g₁ + g₂ + g₃) x with g₁ x + g₂ x + g₃ x, turning the goal into an equality between two explicit polynomial expressions in ZMod 2.

    lines 9–10

    uses four_block_concat, Pi.add_apply

      funext v
      simp only [four_block_concat, Pi.add_apply]
  2. 2 = 0 in ZMod 2.

    Because ZMod 2 has characteristic 2, the integer 2 is zero in this ring. This auxiliary fact h₂ is established by direct computation (`decide`).

    line 11

      have h2 : (2 : ZMod 2) = 0 := by decide
  3. Both expressions are equal after normalizing polynomial terms and eliminating multiples of 2.

    The `ring_nf` tactic expands both sides into polynomial normal form with integer coefficients. In this expanded form, the left-hand and right-hand sides are identical except that the left-hand side contains the additional terms 2 * y₁ * y₂ * g₁ x and 2 * y₁ * y₂ * g₂ x. Rewriting with h₂ (2 = 0) and simplifying via `mul_zero` and `add_zero` removes these terms, completing the proof.

    lines 12–13

    uses mul_zero, add_zero

      ring_nf
      simp only [h2, mul_zero, add_zero]
four_block_concat
The definition of four-block concatenation of functions f₀, f₁, f₂, f₃ on Fin m → ZMod 2 into a function on Fin (m + 2) → ZMod 2, defined by (1 + y₁) * (1 + y₂) * f₀ x + y₁ * (1 + y₂) * f₁ x + (1 + y₁) * y₂ * f₂ x + y₁ * y₂ * f₃ x.
Pi.add_apply
Pointwise addition of functions: (f + g) i = f i + g i.
mul_zero
Multiplication by zero on the right: a * 0 = 0.
add_zero
Addition of zero on the right: a + 0 = a.

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

/-- Over characteristic 2, the four-block concatenation g_0 || g_1 || g_2 || (g_1 + g_2 + g_3) simplifies to (1 + y_1)(1 + y_2) g_0 + y_1 g_1 + y_2 g_2 + y_1 y_2 g_3. -/theorem four_block_concat_reduced {m : ℕ} (g0 g1 g2 g3 : (Fin m → ZMod 2) → ZMod 2) :    four_block_concat g0 g1 g2 (g1 + g2 + g3) =    fun v =>      let x : Fin m → ZMod 2 := fun i => v (Fin.castAdd 2 i)      let y1 : ZMod 2 := v (Fin.natAdd m 0)      let y2 : ZMod 2 := v (Fin.natAdd m 1)      (1 + y1) * (1 + y2) * g0 x + y1 * g1 x + y2 * g2 x + y1 * y2 * g3 x := by  funext v  simp only [four_block_concat, Pi.add_apply]  have h2 : (2 : ZMod 2) = 0 := by decide  ring_nf  simp only [h2, mul_zero, add_zero]
See it in the graphDiscuss this resultChallenge it