PR #6453: the composite matrix equals multiplication in the CRT basis
ProvedCRTBasis.crt_basis_mulalgebracomplexity-theoryinteger-multiplication
In the CRT basis, the composite of two multiplications is multiplication, and its matrix is the diagonal of the product.
Let be a field and a product of copies of it — the image of a ring under the Chinese remainder theorem for coprime moduli. Multiplication by a vector is the -linear map . In the standard basis of its matrix is the diagonal matrix , so the composite of multiplication by with multiplication by has matrix : the composite matrix is multiplication, coordinatewise.
This is the algebraic content of the module identity the construction's word realises, in the basis the CRT supplies.
Preamble
import Definitions.Def_Pr6453_CRT set_option autoImplicit false
Formal statement
namespace CRTBasis
theorem crt_basis_mul {ι : Type*} [Fintype ι] [DecidableEq ι] {K : Type*} [Field K] (x y : ι → K) :
LinearMap.toMatrix' ((mulLin x).comp (mulLin y)) = Matrix.diagonal (x * y) ∧
(LinearMap.toMatrix' (mulLin x)) * (LinearMap.toMatrix' (mulLin y)) =
Matrix.diagonal (x * y) := by
sorry
end CRTBasisSource
CrocSwap/integer-mult-bounds, PR #6453, head b1a3e525793eca35c56324aa7ffd0b714cf606d4, RESULT.json (module block).