Lemma 3.1 (Swap Identity)
ProvedHypercliqueFalse.lemma_3_1algebraic-algorithmsfine-grained-complexityhypercliquep2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let and for all . Then
This identity regroups the terms of a split polynomial into "main" terms and "correction" terms; it is the algebraic core of the recursive step (Lemma 4.1).
Differences from the source:
- encoding: indices i, j ∈ [q] = {1, …, q} → Fin q (0-based); the sum over 1 ≤ i < j ≤ q is ∑ i, ∑ j ∈ Finset.Ioi i; reason: Lean convention; same identity
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace HypercliqueFalse
/-- **Lemma 3.1 (Swap Identity).** Fischer, *The Hyperclique Hypothesis is False*, arXiv:2611.03880 (held version, sha256 6bd5cf5d…7730), Lemma 3.1, p.6: "Let q ≥ 2, and
let U_{ij} ∈ Z^{a×b}, V_{ij} ∈ Z^{b×a} for all i, j ∈ [q]. Then:
Σ_{i,j∈[q]} tr(U_{ij}V_{ij}) = Σ_{i,j∈[q]} tr(U_{ij}V_{ji}) + Σ_{1≤i<j≤q} tr((U_{ij} − U_{ji})(V_{ij} − V_{ji}))."
**Formalization Note.** Indices `[q]` are `Fin q` (0-based); the last sum is over `j ∈ Ioi i`, i.e.
`i < j`. -/
theorem lemma_3_1 (q a b : ℕ) (hq : 2 ≤ q) (U : Fin q → Fin q → Matrix (Fin a) (Fin b) ℤ)
(V : Fin q → Fin q → Matrix (Fin b) (Fin a) ℤ) :
∑ i, ∑ j, (U i j * V i j).trace =
∑ i, ∑ j, (U i j * V j i).trace +
∑ i, ∑ j ∈ Finset.Ioi i, ((U i j - U j i) * (V i j - V j i)).trace := by sorry
end HypercliqueFalse
Source
Fischer, The Hyperclique Hypothesis is False, arXiv:2611.03880 (held version, sha256 6bd5cf5d…7730), Lemma 3.1, p.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.