lemkeoliver

Code related to the paper, “Uniform exponent bounds on the number of primitive extensions of number fields”, by Robert J. Lemke Oliver

This folder contains the Magma code needed to verify many of the invariant theory computations from my paper Uniform exponent bounds on primitive extensions of number fields. Specifically, it includes:

• The file find-invariants.mag provides many of the workhorse functions, described below.
• The folder receipts/ contains the verification of specific computations quoted in the paper. Specifically, this includes:
  • The code verifying Lemma 4.18 (which finds the minimal invariants of the Mathieu groups)
  • The code verifying Theorem 5.9 (which gives bounds on small degree extensions of number fields)
  • The code for, and output of, experiments related to the groups PGL(2,q), PGammaL(2,q), PGL(3,q), and PGammaL(3,q), described in the remark after the proof of Lemma 4.9.

Inside the file find-invariants.mag, the key functions are:

• FindIndependentInvariants(G,d)
  Output = [Invariant degrees], success, corank

  This computes all G-invariant polynomials of degree up to d, then computes the rank of the partial derivative matrix associated with these invariants, evaluated at a random n-tuple of integers (n being the degree of G) between -height and height. (Default: height:=10)

  If the matrix has full rank n, the function returns the degrees of the associated invariants (along with success=true and corank=0). If the matrix does not have full rank, it recomputes the rank evaluated at a different random tuple, up to trials times. (Default: trials:=10)

  If none of these matrices have full rank, the function returns [], false, corank, where corank is n minus the maximum rank seen.

• GuessInvariantDegree(G)
  Output = [Invariant degrees?]

  This function computes a Molien series for the permutation group G. This provides a list of the dimensions of spaces of G-invariants with given degrees. From this, it then iteratively computes the dimension of the subspace generated by polynomials in smaller degrees – assuming there are no algebraic relations. Thus, this should be regarded as computing a lower bound on the degrees of algebraically independent invariants.

  Very often this lower bound is the correct answer (especially for primitive groups), and it is useful to do this before calling the function FindIndependentInvariants above, as increasing the parameter d in that function can be very expensive. However, the list of invariant degrees produced by this function are not verified in any way.

• FindMinimalInvariants(G)
  Output = [Invariant degrees], success

  This function marries the previous two together (e.g., as in the computation described in the proof of Lemma 4.18). In particular, it first computes a lower bound on the invariant degrees coming from GuessInvariantDegree(G). It then calls FindIndependentInvariants(G,d), where d is the largest degree seen from the lower bound. If these two sets of degrees agree, they are provably minimal, and the output is the list of invariant degrees, with success=true. If these lists do not agree, then it returns [], false.

  In practice, this procedure frequently works, but the failure rate for groups that can succeed is higher for certain groups than I would naively expect. The first transitive group where this process appears to genuinely fail is 8T42. There are optional parameters in this function (trials:=10, height:=10) that are passed to FindIndependentInvariants. Perhaps the default values could be tuned better to avoid the failure of the random approach?