AFTD Auto-Formalizing Theoretical Domains

bordered_goethals_seidel_matrix_entries

theoremverified

If a, b, c, d : Fin m → ℤ take only the values 1 and -1, every entry of the bordered Goethals-Seidel matrix built from their circulants is 1 or -1.

Statement

theorem bordered_goethals_seidel_matrix_entries {m : ℕ} (a b c d : Fin m → ℤ)
    (ha : ∀ i, a i = 1 ∨ a i = -1) (hb : ∀ i, b i = 1 ∨ b i = -1)
    (hc : ∀ i, c i = 1 ∨ c i = -1) (hd : ∀ i, d i = 1 ∨ d i = -1) (i j : Fin 4 ⊕ Fin 4 × Fin m) :
    bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b)
      (Matrix.circulant c) (Matrix.circulant d) i j = 1 ∨
    bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b)
      (Matrix.circulant c) (Matrix.circulant d) i j = -1
Source
step of arXiv:2610.27175 Theorem 5 (the matrix is a {±1}-matrix)
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • mul_back_identity_matrix_applyRight multiplication by the back-identity matrix reverses the columns: (X R) i j = X i (m - 1 - j).
  • bordered_goethals_seidel_matrixThe (4m+4) × (4m+4) matrix of arXiv:2610.27175 Theorem 5, indexed by Fin 4 ⊕ (Fin 4 × Fin m): top-left 4 × 4 block with diagonal 1 and…
  • 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 bordered Goethals-Seidel matrix is structured as a 2 × 2 block matrix consisting of a 4 × 4 border block, two rectangular border blocks of sizes 4 × 4m and 4m × 4, and a 4m × 4m Goethals-Seidel array. First, the proof establishes four helper lemmas showing that having all entries in {1, -1} is preserved under taking circulants, negation, right-multiplication by the back-identity matrix R, and transposition. Decomposing the row and column indices into border and array components, the three border blocks are verified by exhaustively checking their fixed coefficients in {1, -1}, while each of the 16 blocks in the Goethals-Seidel array matches one of the preserved operations on the circulants of a, b, c, and d.

  1. Any circulant matrix whose defining vector has entries in {1, -1} has all its entries in {1, -1}.

    By definition, the (i, j)-th entry of the circulant matrix circ(v) is v(i - j). Since every entry of v is 1 or -1, the difference i - j also indexes an entry in {1, -1}.

    lines 8–10

      have hcirc : ∀ v : Fin m → ℤ, (∀ i, v i = 1 ∨ v i = -1) →
          ∀ i j, Matrix.circulant v i j = 1 ∨ Matrix.circulant v i j = -1 :=
        fun v hv i j => hv (i - j)
  2. The negation of any matrix with entries in {1, -1} also has all entries in {1, -1}.

    By Matrix.neg_apply, the (i, j)-th entry of -X is -(X i j). If X i j = 1, its negation is -1; if X i j = -1, its negation is 1. In both cases the resulting entry lies in {1, -1}.

    lines 11–15

    uses Matrix.neg_apply

      have hneg : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) →
          ∀ i j, (-X) i j = 1 ∨ (-X) i j = -1 := by
        intro X hX i j
        rw [Matrix.neg_apply]
        rcases hX i j with h | h <;> rw [h] <;> simp
  3. Right-multiplication by the back-identity matrix preserves the property that all entries lie in {1, -1}.

    By mul_back_identity_matrix_apply, the (i, j)-th entry of X * R is X i j.rev. Since this is an entry of X with a reversed column index, it is 1 or -1 by the hypothesis on X.

    lines 16–20

    uses mul_back_identity_matrix_apply

      have hR : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) →
          ∀ i j, (X * back_identity_matrix m) i j = 1 ∨ (X * back_identity_matrix m) i j = -1 := by
        intro X hX i j
        rw [mul_back_identity_matrix_apply]
        exact hX i j.rev
  4. Transposition preserves the property that all entries lie in {1, -1}.

    The (i, j)-th entry of the transpose Xᵀ is X j i, which lies in {1, -1} by the hypothesis on X.

    lines 21–23

      have hT : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) →
          ∀ i j, X.transpose i j = 1 ∨ X.transpose i j = -1 :=
        fun X hX i j => hX j i
  5. The four circulant matrices A, B, C, D formed from a, b, c, d all have entries in {1, -1}.

    We apply the circulant lemma established in the first step to each of the vectors a, b, c, d and their respective hypotheses.

    lines 24–27

      have hA := hcirc a ha
      have hB := hcirc b hb
      have hC := hcirc c hc
      have hD := hcirc d hd
  6. The goal splits into four cases according to the block decomposition of the bordered matrix.

    The row and column index type Fin 4 ⊕ (Fin 4 × Fin m) is a sum of border indices and array indices. Performing case analysis on both i and j splits the goal into the four blocks: top-left (4 × 4), top-right (4 × 4m), bottom-left (4m × 4), and bottom-right (4m × 4m).

    line 28

      rcases i with r | ⟨p, i⟩ <;> rcases j with r' | ⟨q, j⟩
  7. Every entry of the top-left 4 × 4 border block is 1 or -1.

    Exhaustive case analysis on row r ∈ Fin 4 and column r' ∈ Fin 4 evaluates all 16 entries of the explicit 4 × 4 border matrix, each of which is 1 or -1.

    line 29

    uses bordered_goethals_seidel_matrix

      · fin_cases r <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix]
  8. Every entry of the top-right 4 × 4m border block is 1 or -1.

    Exhaustive case analysis on border row r ∈ Fin 4 and block column q ∈ Fin 4 evaluates each entry to one from the explicit 4 × 4 coefficient matrix, which is independent of the within-block column index and always 1 or -1.

    line 30

    uses bordered_goethals_seidel_matrix

      · fin_cases r <;> fin_cases q <;> simp [bordered_goethals_seidel_matrix]
  9. Every entry of the bottom-left 4m × 4 border block is 1 or -1.

    Exhaustive case analysis on block row p ∈ Fin 4 and border column r' ∈ Fin 4 evaluates each entry to one from the explicit 4 × 4 coefficient matrix, which is independent of the within-block row index and always 1 or -1.

    line 31

    uses bordered_goethals_seidel_matrix

      · fin_cases p <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix]
  10. Every entry of the bottom-right 4m × 4m Goethals-Seidel array block is 1 or -1.

    The Goethals-Seidel array consists of 16 blocks indexed by (p, q) ∈ Fin 4 × Fin 4. For each pair (p, q), the block is of the form A, ±(X * R), or ±(Xᵀ * R) for some X ∈ {B, C, D}. Each such block has all entries in {1, -1} by combining the preservation properties proved earlier for circulants, negation, multiplication by R, and transposition.

    lines 32–39

      · fin_cases p <;> fin_cases q <;>
          first
            | exact hA i j
            | exact hR _ hB i j | exact hR _ hC i j | exact hR _ hD i j
            | exact hneg _ (hR _ hB) i j | exact hneg _ (hR _ hC) i j | exact hneg _ (hR _ hD) i j
            | exact hR _ (hT _ hB) i j | exact hR _ (hT _ hC) i j | exact hR _ (hT _ hD) i j
            | exact hneg _ (hR _ (hT _ hB)) i j | exact hneg _ (hR _ (hT _ hC)) i j
            | exact hneg _ (hR _ (hT _ hD)) i j
Matrix.neg_apply
The entry at row i and column j of the negation of a matrix A is the negation -A i j of the corresponding entry of A.
mul_back_identity_matrix_apply
Multiplying a square matrix X of size m on the right by the back-identity matrix yields a matrix whose (i, j)-th entry is X i j.rev, which reverses the column index.
bordered_goethals_seidel_matrix
The bordered Goethals-Seidel matrix constructed from four blocks: a 4 × 4 border block, two rectangular border blocks of sizes 4 × 4m and 4m × 4, and the 4m × 4m Goethals-Seidel array of circulant matrices.

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_matrix_entries {m : ℕ} (a b c d : Fin m → ℤ)    (ha : ∀ i, a i = 1 ∨ a i = -1) (hb : ∀ i, b i = 1 ∨ b i = -1)    (hc : ∀ i, c i = 1 ∨ c i = -1) (hd : ∀ i, d i = 1 ∨ d i = -1) (i j : Fin 4 ⊕ Fin 4 × Fin m) :    bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b)      (Matrix.circulant c) (Matrix.circulant d) i j = 1 ∨    bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b)      (Matrix.circulant c) (Matrix.circulant d) i j = -1 := by  have hcirc : ∀ v : Fin m → ℤ, (∀ i, v i = 1 ∨ v i = -1) →      ∀ i j, Matrix.circulant v i j = 1 ∨ Matrix.circulant v i j = -1 :=    fun v hv i j => hv (i - j)  have hneg : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) →      ∀ i j, (-X) i j = 1 ∨ (-X) i j = -1 := by    intro X hX i j    rw [Matrix.neg_apply]    rcases hX i j with h | h <;> rw [h] <;> simp  have hR : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) →      ∀ i j, (X * back_identity_matrix m) i j = 1 ∨ (X * back_identity_matrix m) i j = -1 := by    intro X hX i j    rw [mul_back_identity_matrix_apply]    exact hX i j.rev  have hT : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) →      ∀ i j, X.transpose i j = 1 ∨ X.transpose i j = -1 :=    fun X hX i j => hX j i  have hA := hcirc a ha  have hB := hcirc b hb  have hC := hcirc c hc  have hD := hcirc d hd  rcases i with r | ⟨p, i⟩ <;> rcases j with r' | ⟨q, j⟩  · fin_cases r <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix]  · fin_cases r <;> fin_cases q <;> simp [bordered_goethals_seidel_matrix]  · fin_cases p <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix]  · fin_cases p <;> fin_cases q <;>      first        | exact hA i j        | exact hR _ hB i j | exact hR _ hC i j | exact hR _ hD i j        | exact hneg _ (hR _ hB) i j | exact hneg _ (hR _ hC) i j | exact hneg _ (hR _ hD) i j        | exact hR _ (hT _ hB) i j | exact hR _ (hT _ hC) i j | exact hR _ (hT _ hD) i j        | exact hneg _ (hR _ (hT _ hB)) i j | exact hneg _ (hR _ (hT _ hC)) i j        | exact hneg _ (hR _ (hT _ hD)) i j
See it in the graphDiscuss this resultChallenge it