6.1. Introduction🔗

HexSparsePoly provides canonical sparse univariate polynomials: a polynomial is a sorted array of (exponent, coefficient) terms with strictly increasing exponents and no stored zero coefficient. Costs scale with the number of stored terms rather than the degree, so a two-term polynomial of degree one million is two array entries. The representation is canonical, so equality is structural and decidable.

The executable library is Mathlib-free. It depends on HexBasic for array equality and fold algebra, and on HexPoly for the dense representation it converts to and from. It is a second representation next to Hex.DensePoly, not a replacement: callers name the representation they hold and convert explicitly, because the same named operation can differ in cost by a factor of the degree between the two. HexSparsePolyMathlib, described in the correspondence section, identifies the type with Mathlib's Polynomial R.