Library mathcomp.field.finfield

Additional constructions and results on finite fields FinFieldExtType L == a FinFieldType structure on the carrier of L, where L IS a fieldExtType F structure for an F that has a finFieldType structure. This does not take any existing finType structure on L; this should not be made canonical FinSplittingFieldType F L == a SplittingFieldType F structure on the carrier of L, where L IS a fieldExtType F for an F with a finFieldType structure; this should not be made canonical finvect_type vT == alias of vT : vecType R equipped with canonical instances for finType, finNzRing, etc structures (including FinFieldExtType above) for abstract vectType, falgType and fieldExtType over a finFieldType pPrimeCharType pcharRp == the carrier of a nzRingType R such that pcharRp : p \in [pchar R] holds. This type has canonical nzRingType, ..., fieldType structures compatible with those of R, as well as canonical lmodType 'F_p, ..., algType 'F_p structures, plus an falgType structure if R is a finUnitRingType and a splittingFieldType structure if R is a finFieldType FinSplittingFieldFor nz_p == sigma-pair whose sval is a splittingFieldType that is the splitting field for p : {poly F} over F : finFieldType, given nz_p : p != 0 PrimePowerField pr_p k_gt0 == sigma2-triple whose s2val is a finFieldType of characteristic p and order m = p ^ k, given pr_p : prime p and k_gt0 : k > 0 FinDomainFieldType domR == a finFieldType structure on a finUnitRingType R, given domR : GRing.IntegralDomain.axiom R. This is intended to be used inside proofs, where one cannot declare Canonical instances Otherwise one should construct explicitly the intermediate structures using the ssralg and finalg constructors, and finDomain_mulrC domR finDomain_fieldP domR to prove commutativity and field axioms (the former is Wedderburn's little theorem). FinDomainSplittingFieldType domR pcharRp == a splittingFieldType structure that repackages the two constructions above

TODO: automatize parameter inference to do all of these

By card_vspace order K = #|K| for any finType structure on L; however we do not want to impose the FinVector instance here.

While the existence of finite splitting fields and of finite fields of arbitrary prime power order is mathematically straightforward, it is technically challenging to formalize in Coq. The Coq typechecker performs poorly for some of the deeply nested dependent types used in the construction, such as polynomials over extensions of extensions of finite fields. Any conversion in a nested structure parameter incurs a huge overhead as it is shared across term comparison by call-by-need evalution. The proof of FinSplittingFieldFor is contrived to mitigate this effect: the abbreviation map_poly_extField alone divides by 3 the proof checking time, by reducing the number of occurrences of field(Ext)Type structures in the subgoals; the successive, apparently redundant 'suffices' localize some of the conversions to smaller subgoals, yielding a further 8-fold time gain. In particular, we construct the splitting field as a subtype of a recursive construction rather than prove that the latter yields precisely a splitting field. The apparently redundant type annotation reduces checking time by 30%.

This is Witt's proof of Wedderburn's little theorem.