Lemma 3.1 — Schläfli:
ProvedKServerConj.lemma_3_1competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1valuationswork-function-algorithm
For every matrix over a commutative ring, the matrix of the induced map on quadratic forms, in the monomial basis , satisfies
The exponent counts how often a basis vector occurs among the products : twice in its square and once in each of its mixed products. It is the source of the factor in the terminal bound of the potential (Lemma 5.1), and it shows that is unchanged by a normalization with .
Differences from the source:
- generalization: every invertible k × k matrix A over K → every k × k matrix over every commutative ring; reason: the identity is a polynomial identity with integer coefficients in the entries of A; the invertible case over K is a special case
- encoding: the monomial basis (e_ie_j)_{1≤i≤j≤k} in lexicographic order → rows and columns indexed by Sym2 (Fin k); reason: a determinant is unchanged by the same reordering of rows and columns
Preamble
import Mathlib import Definitions.Def_KServerConj_symProd
Formal statement
namespace KServerConj
/-- **Lemma 3.1 (Schläfli).** Coester, Koutsoupias, Zbysiński, *The k-server conjecture is true*,
arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…), printed p.9 (PDF p.10): "For every
invertible k × k matrix A, det(Sym² A) = (det A)^{k+1}. (15)"
**Formalization Note.** `sym2Mat A` is the matrix of `Sym² A` in the monomial basis
`(e_ie_j)_{i≤j}`, indexed by `Sym2 (Fin k)`. The identity is stated for every square matrix over
every commutative ring: it is a polynomial identity in the entries of `A`, so the invertible case
over the paper's field `K` is a special case. -/
theorem lemma_3_1 {R : Type*} [CommRing R] {k : ℕ} (A : Matrix (Fin k) (Fin k) R) :
(sym2Mat A).det = A.det ^ (k + 1) := by sorry
end KServerConj
Source
Coester, Koutsoupias, Zbysiński, The k-server conjecture is true, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…), Lemma 3.1, p.9 (pdf p.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.