AFTD Auto-Formalizing Theoretical Domains

bordered_goethals_seidel_cross_block

theoremverified

If the first columns a, b, c, d (m > 0) sum to 2, 0, 0, 0, then K Lᵀ + T Mᵀ = 0, where K is the 4 × 4 corner, L the 4m × 4 left border of ±jᵀ, T the top border and M the Goethals-Seidel array of the circulants and the back-identity: the off-diagonal block of H Hᵀ vanishes.

Statement

theorem bordered_goethals_seidel_cross_block {m : ℕ} [NeZero m] (a b c d : Fin m → ℤ)
    (hsa : ∑ i, a i = 2) (hsb : ∑ i, b i = 0) (hsc : ∑ i, c i = 0) (hsd : ∑ i, d i = 0) :
    !![(1 : ℤ), -1, -1, -1; -1, 1, -1, -1; -1, -1, 1, -1; -1, -1, -1, 1]
          * (Matrix.of fun (p : Fin 4 × Fin m) (c : Fin 4) =>
              !![(1 : ℤ), 1, 1, 1; -1, 1, 1, -1; -1, -1, 1, 1; -1, 1, -1, 1] p.1 c).transpose
        + (Matrix.of fun (r : Fin 4) (q : Fin 4 × Fin m) =>
              !![(1 : ℤ), 1, 1, 1; 1, -1, 1, -1; 1, -1, -1, 1; 1, 1, -1, -1] r q.1)
          * (goethals_seidel_array (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c)
              (Matrix.circulant d) (back_identity_matrix m)).transpose = 0
Source
step of arXiv:2610.27175 Theorem 5 (off-diagonal blocks of H Hᵀ, via row sums 2, 0, 0, 0)
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • back_identity_matrixThe back-identity (reversal) matrix R of order m over ℤ: R i j = 1 when i + j ≡ m - 1 (mod m), equivalently i + j + 1 = m for indices…
  • circulant_mul_back_identity_matrix_row_sumEvery row of X R, X the circulant with first column v and R the back-identity, sums to the sum of v.
  • sum_comp_negFor v : Fin m → ℤ with m > 0, the sum of v(-j) over j equals the sum of v.
  • fin_sum_sub_leftFor v : Fin m → ℤ with m > 0 and any i, the sum of v(i - j) over j equals the sum of v.
  • goethals_seidel_arrayThe Goethals-Seidel array of order 4m in four m × m matrices A, B, C, D and R, indexed by (block row, row): rows of blocks (A, BR, CR,…
Used by 1
  • bordered_goethals_seidel_is_hadamardLet m be even and let A, B, C, D be circulant {±1}-matrices of order m (first columns a, b, c, d) with AAᵀ + BBᵀ + CCᵀ + DDᵀ = (4m+4)I -…

The proof, explained

The proof verifies that the off-diagonal block K Lᵀ + T Mᵀ vanishes by entrywise computation. Extensionality reduces the matrix equality to scalar identities for each row r ∈ {0, 1, 2, 3} and column (p, i) ∈ {0, 1, 2, 3} × Fin m. The product T Mᵀ involves row sums of the circulant and circulant-times-reversal blocks of the Goethals–Seidel array, each of which reduces to the sum of its generating vector (a, b, c, or d). Because ∑ b = ∑ c = ∑ d = 0 and ∑ a = 2, the sub-index i disappears entirely, leaving 16 explicit numerical identities in r and p that all evaluate to zero by basic integer arithmetic.

  1. It suffices to show that each entry of K Lᵀ + T Mᵀ at row r ∈ Fin 4 and column (p, i) ∈ Fin 4 × Fin m is zero.

    By matrix extensionality (`ext`), two matrices are equal if and only if all corresponding entries are equal. We introduce arbitrary indices r for the row and a pair ⟨p, i⟩ representing the block index p ∈ Fin 4 and sub-index i ∈ Fin m for the column.

    line 10

      ext r ⟨p, i⟩
  2. The entry (r, (p, i)) of the matrix sum expands into ∑ j, K r j * L p j + ∑ x, T r x * ∑ x₁, M (p, i) (x, x₁) = 0, isolating the row sums of each block of M.

    Unfolding matrix addition (`Matrix.add_apply`), multiplication (`Matrix.mul_apply`), transpose (`Matrix.transpose_apply`), and the zero matrix (`Matrix.zero_apply`) expresses the (r, (p, i)) entry as index sums. The double summation over the column indices of T and row indices of Mᵀ is split into an outer sum over block index x ∈ Fin 4 and an inner sum over x₁ ∈ Fin m using `Fintype.sum_prod_type`. The definitions of L and T are evaluated via `Matrix.of_apply`. Applying `Finset.mul_sum` in reverse factors the scalar T r x out of the inner sum over x₁, leaving the row sum of the (p, x)-th block of the Goethals–Seidel array.

    lines 11–13

    uses Matrix.add_apply, Matrix.mul_apply, Matrix.transpose_apply, Fintype.sum_prod_type, Matrix.of_apply, Matrix.zero_apply, Finset.mul_sum

      simp only [Matrix.add_apply, Matrix.mul_apply, Matrix.transpose_apply, Fintype.sum_prod_type,
        Matrix.of_apply, Matrix.zero_apply]
      simp only [← Finset.mul_sum]
  3. For each column block p ∈ {0, 1, 2, 3}, the row sums of the Goethals–Seidel blocks evaluate to fixed integers, eliminating the sub-index i and reducing the goal to an explicit vector identity in r.

    We split into four cases on the column block index p ∈ Fin 4 (`fin_cases p`). In each case, `goethals_seidel_array` expands into its four m × m circulant blocks. The row sum of a circulant matrix circulant(v) is evaluated to ∑ v by `fin_sum_sub_left`, the row sum of circulant(v) * R is evaluated by `circulant_mul_back_identity_matrix_row_sum`, transposes of circulants are rewritten by `Matrix.transpose_circulant` with their row sum preserved by `sum_comp_neg`, and minus signs are factored out with `Finset.sum_neg_distrib`. Expanding the outer sum over the four blocks using `Fin.sum_univ_four` and substituting the hypothesis values ∑ a = 2 (`hsa`), ∑ b = 0 (`hsb`), ∑ c = 0 (`hsc`), and ∑ d = 0 (`hsd`) replaces every block row sum with a constant. Consequently, all dependence on the sub-index i vanishes, leaving an explicit vector expression evaluated at r.

    lines 14–17

    uses goethals_seidel_array, Fin.sum_univ_four, Matrix.transpose_circulant, Finset.sum_neg_distrib, circulant_mul_back_identity_matrix_row_sum, sum_comp_neg, fin_sum_sub_left

      fin_cases p <;>
        simp [goethals_seidel_array, Fin.sum_univ_four, Matrix.transpose_circulant,
          Finset.sum_neg_distrib, circulant_mul_back_identity_matrix_row_sum,
          sum_comp_neg, fin_sum_sub_left, hsa, hsb, hsc, hsd] <;>
  4. The identity holds for all row indices r ∈ {0, 1, 2, 3}, completing the proof.

    For each of the four block cases p, we perform a case analysis on the row index r ∈ Fin 4 (`fin_cases r`), resulting in 16 scalar cases. In every case, all vector components are concrete values in {1, -1, 2}, and integer arithmetic (`simp`) verifies that the sum is 0.

    line 18

        fin_cases r <;> simp
Matrix.add_apply
The (i, j) entry of the sum of two matrices is the sum of their (i, j) entries.
Matrix.mul_apply
The (i, k) entry of the matrix product M * N is the sum ∑ j, M i j * N j k.
Matrix.transpose_apply
The (i, j) entry of the transpose matrix Mᵀ is M j i.
Fintype.sum_prod_type
A sum over a Cartesian product type α₁ × α₂ equals the iterated sum over α₁ and α₂.
Matrix.of_apply
The (i, j) entry of a matrix defined by a function f is f i j.
Matrix.zero_apply
Every entry of the zero matrix is 0.
Finset.mul_sum
Left multiplication distributes over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
goethals_seidel_array
The 4 × 4 block matrix constructed from four m × m matrices A, B, C, D and the back-identity matrix R.
Fin.sum_univ_four
The sum of a function over Fin 4 equals f 0 + f 1 + f 2 + f 3.
Matrix.transpose_circulant
The transpose of the circulant matrix of v is the circulant matrix of the negated index vector j ↦ v (-j).
Finset.sum_neg_distrib
The sum of negated terms equals the negation of the sum: ∑ x, -f x = -∑ x, f x.
circulant_mul_back_identity_matrix_row_sum
Every row sum of the product of a circulant matrix circulant(v) with the back-identity matrix equals ∑ j, v j.
sum_comp_neg
Summing a vector over Fin m under index negation j ↦ -j gives the same result as summing the vector directly.
fin_sum_sub_left
For any fixed row index i, the sum ∑ j, v (i - j) over Fin m equals the total sum ∑ j, v j.

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

theorem bordered_goethals_seidel_cross_block {m : ℕ} [NeZero m] (a b c d : Fin m → ℤ)    (hsa : ∑ i, a i = 2) (hsb : ∑ i, b i = 0) (hsc : ∑ i, c i = 0) (hsd : ∑ i, d i = 0) :    !![(1 : ℤ), -1, -1, -1; -1, 1, -1, -1; -1, -1, 1, -1; -1, -1, -1, 1]          * (Matrix.of fun (p : Fin 4 × Fin m) (c : Fin 4) =>              !![(1 : ℤ), 1, 1, 1; -1, 1, 1, -1; -1, -1, 1, 1; -1, 1, -1, 1] p.1 c).transpose        + (Matrix.of fun (r : Fin 4) (q : Fin 4 × Fin m) =>              !![(1 : ℤ), 1, 1, 1; 1, -1, 1, -1; 1, -1, -1, 1; 1, 1, -1, -1] r q.1)          * (goethals_seidel_array (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c)              (Matrix.circulant d) (back_identity_matrix m)).transpose = 0 := by  ext r ⟨p, i⟩  simp only [Matrix.add_apply, Matrix.mul_apply, Matrix.transpose_apply, Fintype.sum_prod_type,    Matrix.of_apply, Matrix.zero_apply]  simp only [← Finset.mul_sum]  fin_cases p <;>    simp [goethals_seidel_array, Fin.sum_univ_four, Matrix.transpose_circulant,      Finset.sum_neg_distrib, circulant_mul_back_identity_matrix_row_sum,      sum_comp_neg, fin_sum_sub_left, hsa, hsb, hsc, hsd] <;>    fin_cases r <;> simp
See it in the graphDiscuss this resultChallenge it