Back to Patch Notes
Patch Notes

Magma V2.30-1 Patch Notes

Patch release for Magma V2.30-1. Updated areas: Algebraic Geometry, Algebraic Number Fields and Orders, Coding Theory, Language/System, Algebraic Curves and 27 more.

32 areas

Changes and Removals

Algebraic Geometry

Algebraic Number Fields and Orders

Coding Theory

  • The Coding Theory part of the Handbook has been reorganized. The Pseudo-random Bit Sequences chapter now lives there, and documents the SHA1 digest function alongside the linear feedback shift register, Berlekamp-Massey, correlation, and decimation functions. A small number of application-specific intrinsics that had accumulated around these chapters are no longer included.

Language/System

New Features

Algebraic Curves

Algebraic Number Fields

  • Support of the rationals as a subfield of an embedded number field was added. (Issue #127) Reported by Jeroen Sijsling.

Elliptic Curves

  • TracesOfFrobenius for elliptic curves over the rationals accepts a new signature TracesOfFrobenius(E, Ps), returning the traces of Frobenius at the primes in the sequence Ps, with the i-th result corresponding to Ps[i]. The entries may be given in any order and may repeat, and each entry is checked to be prime. A sequence with more entries than a result sequence can contain is rejected with an error. The traces are computed by the same fast path as the existing bound and range forms, using the threads set by SetNthreads.

  • TracesOfFrobenius for elliptic curves over the rationals is now substantially faster when computing the traces of Frobenius at many good primes. On non-CM curves the traces are found through a bulk path that runs in parallel across the threads set by SetNthreads; CM curves, primes of bad reduction, and any prime outside that path use the existing per-prime computation. The returned traces are unchanged for bounds accepted by the pre-existing two-argument form, which now takes any non-negative bound that fits a machine integer and whose result fits in a sequence rather than only a small one; on a standard build that second limit already rejects a bound of about 2.5e10.

    A new signature TracesOfFrobenius(E, B0, B1) returns one trace of Frobenius for every prime in the interval [B0, B1], including primes of bad reduction. Its results are in increasing order of prime, one for each prime of the interval; for instance, over a range where PrimesInInterval(B0, B1) can be called, the i-th result corresponds to its i-th entry. Both this and TracesOfFrobenius(E, B) sieve the primes of the range, so an upper endpoint beyond the reach of that sieve is rejected with an error naming the largest endpoint the sieve can address; that reach depends on the binary variant, and is about 1.15e18 on a standard build. A request whose result would hold more traces than a sequence can contain is also rejected with an error, before any traces are computed.

Finite Fields

  • Discrete logarithms by the function field sieve

    A new implementation of the function field sieve (FFS) for discrete logarithms in non-prime finite fields of medium characteristic has been added, following the variant of Joux and Lercier. It is used automatically by Log (and hence by Log(b, x)) for a field GF(p^k) with \(7 < p < 2^{20}\) and at least \(2^{32}\) elements when the largest prime dividing \(p^k - 1\) is at least \(2^{37}\) and no stored Coppersmith table applies to the field (apart from a few special cases). Previously such fields, and in particular every such field with \(p > 100\), could only be handled by the Pohlig-Hellman algorithm, whose running time grows with the square root of that largest prime, so that logarithms in them were in practice out of reach.

    As with the other index-calculus methods, there is a precomputation stage which computes the logarithms of a factor base (the irreducible polynomials over GF(p) up to some degree \(B\)) and is done once for each \(p\) and \(k\); each individual logarithm is then computed quickly from the stored factor base logarithms, for any field of that cardinality whatever its defining polynomial. For example, the precomputation takes about 3 seconds for GF(101^13), GF(211^11) or GF(1013^9), about 6 seconds for GF(101^17) and about 5 minutes for GF(223^21), after which individual logarithms take a small fraction of a second. All parameters are chosen automatically.

Graphs

  • The new intrinsic PetersenGraph returns the Petersen graph, the odd graph \(O_3\) on the \(2\)-subsets of a \(5\)-set.

Groebner Bases

  • The Faugere \(F_4\) Groebner basis linear algebra core now has optimized vectorization for prime finite fields of size 65 to 128 bits (about 20 to 30 times faster than the old version). There is also complete use of \(\sim\)64-bit primes in modular algorithms for robustness and to avoid running out of primes in very large examples.

Language/System

  • Intrinsics SetEnv(s, v) and UnsetEnv(s) (also SetEnvironmentValue and UnsetEnvironmentValue) have been added, to set and remove an external environment variable, alongside the existing GetEnv.

  • Magma now keeps the interactive command history across sessions. It is on by default, saved to a file in the user’s home directory, so the up arrow and incremental search reach commands from earlier runs. It can also be turned off. See The History File for details.

    Users can also optionally save each session separately and browse the saved sessions with %b; see Saved Sessions and the Browser. History commands now accept full names such as %print, and the new %o shows the history settings, which are kept in an options file; see The Options File.

Local Fields

  • Factorization of polynomials over local rings defined by an arbitrary polynomial has been improved.

Number Fields

  • Added a new NumberField intrinsic for algebraically closed fields, returning a number field isomorphic to the subfield generated by the elements introduced so far together with a bidirectional map between the two. By default the number field is a tower with one extension for each variable of the algebraic closure, which avoids the cost of an absolute presentation; the parameter Absolute returns an absolute number field instead.

    A second form, NumberField of an element \(a\) of an algebraically closed field, returns the number field generated by \(a\), defined by its minimal polynomial, together with its embedding into the algebraically closed field.

Bug Fixes

Algebraic Curves

  • EulerFactor of genus-2 curves over the rationals at large odd bad primes could run out of memory, grind for hours, or fail with “Could not compute local data”. These factors are now computed in seconds.

Algebraic Function Fields

  • Coercion of ideals to smaller orders has been fixed. Reported by Arix Eggink.

  • CoveringStructure of orders has been fixed for orders of algebraic function fields where one was the suborder of the other.

  • Equality of orders of algebraic function fields has been improved when linear extensions are involved.

Algebraic Geometry

  • A bug in ParametrizeRationalNormalCurve causing problems in CurveQuotient was fixed.

  • Fixed an error that aborted DualResolutionGraph for some normal surface singularities, such as the \(E_6\) singularity \(x^2+y^3+z^4\) over a field where two exceptional curves meet in a Galois-conjugate point. The related minimal-graph, fibre zeta function and fibre point-count intrinsics are fixed likewise.

  • Corrected ZetaFunctionOfResolutionFibre and NumberOfPointsOnResolutionFibre (and their minimal-resolution variants) over finite fields. When the Frobenius folds conjugate exceptional curves together, the fibre zeta function could be returned in an invalid form (constant term not equal to 1) and the fibre point count could come back with the wrong sign or change depending on whether the zeta function or the point count was requested first. Both now agree and return the correct value.

  • Fixed a “Bad argument types” runtime error in Genus for a blow-up divisor of a surface desingularisation when DualResolutionGraph had already been computed for the same desingularisation. Requesting the genus first was unaffected, so the call succeeded or aborted depending on the order of the two requests; it now returns the genus in both orders.

  • Fixed runtime-error aborts in MinimalDualResolutionGraph (such as “Bad argument types”) on resolutions that require contracting a \((-1)\)-curve. It now returns the minimal dual graph and its intersection matrix instead of aborting.

  • Corrected the values of SelfIntersection, CanonicalIntersection and ArithmeticGenus for exceptional divisors that are Galois orbits of conjugate curves, such as the two conjugate exceptional curves in the resolution of \(x^2+y^4+z^8\) over \(\mathbb{Q}\). The reported values came from a single geometric component and under-counted the orbit; they now agree with the orbit-folded intersection matrix.

  • Fixed a crash in surface singularity resolution (ResolveSingularSurface, ResolveSingByBlowUp) over base fields other than finite fields and the rationals, such as number fields like \(\mathbb{Q}(i)\).

  • Fixed a crash in surface singularity resolution (ResolveSingularSurface, ResolveSingByBlowUp) that aborted with an internal assertion error on some singular surfaces, such as a quartic surface over GF(2) or a quintic surface over \(\mathbb{Q}\). A singular curve that had already been resolved could be rediscovered and blown up again, producing a spurious extra exceptional divisor that the resolution could not reconcile. These surfaces now resolve correctly.

Algebraic Number Fields

  • The signatures of EmbeddedNumberField that take a real or complex approximation now return only the embedded number field. They previously returned a boolean followed by the field. They report an error when no embedding extends the labelled embedding of the base field and sends the generator to the given number. This can happen when the input is inconsistent or the approximation lacks enough precision. The signatures taking an embedding number are unchanged. The new HasEmbeddedNumberField takes the same arguments. It returns false when no embedding fits or when several embeddings fit. Otherwise it returns true followed by the embedded number field. An approximation too coarse to distinguish two embeddings previously selected the first match. HasEmbeddedNumberField now returns false for this input, and EmbeddedNumberField reports an error. For a relative extension with two close base-field embeddings, the returned field could previously be labelled over the wrong one. It now always extends the labelled embedding of the base field. For a degree-one field with a large generator, EmbeddedNumberField could previously accept a number too far from the generator. For example, it accepted \(10^{30} + 0.1\) at 80 digits for the field defined by \(x - 10^{30}\) because it compared only 30 digits. It now uses every digit of the approximation.

  • Composite and Subfield for number fields with labelled embeddings now name the complex embedding they could not identify. They previously stopped with a bare assertion failure. No input is known to reach either error. EmbeddedNumberField now reports that the base field must have a labelled embedding when given an extension of an unlabelled number field. It previously stopped with an assertion failure.

  • Operations on relative Artin representations, those returned by ArtinRepresentations for an extension E/F with F not the rationals, failed with errors from character arithmetic: Kernel, Decomposition and RationalDecomposition compared characters of different groups, and sums, products, tensor powers, integer multiples and Symmetrization built the result over the absolute field. These now work in the Galois group of F, and return relative representations. IsRamified, IsWildlyRamified, DirichletCharacter, HeckeCharacter, Minimize and OptimizedRepresentation are not yet defined in the relative setting and now say so, instead of failing inside character arithmetic.

  • An incorrect result in IsSubfield for number fields has been fixed. Reported by Siman Wong.

  • Embed has been fixed when linear extensions are involved.

  • Fixed an error in AutomorphismGroup when computing the automorphisms of RationalsAsNumberField over itself. (Issue #124)

  • NormEquation could print the run report of the lp_solve library on standard output and standard error. This has been fixed. (Issue #148) Reported by Edgar Costa.

  • Fixed a crash when intersecting a number field with a labelled complex embedding with its labelled relative extension, using meet or Intersection. (Issue #156) Reported by Edgar Costa.

  • Fixed a crash in AutomorphismGroup for non-Galois absolute number fields where evaluating the returned map on non-identity group elements could trigger an internal error. Also fixed the reverse map (@@phi) returning wrong group elements on Galois fields with three or more automorphisms. (Issue #25) Reported by Edgar Costa.

  • Composite could stop with an assertion failure or a coercion error when the second labelled number field was a relative extension. This occurred, for example, for \(\Q(2^{1/3})\) and \(\Q(\sqrt{2})(2^{1/3})\) labelled at different complex cube roots of 2. These composites are now constructed correctly.

  • EmbeddedNumberField, Composite, Intersection, Subfield, IsSubfieldEmb and meet could run without end when a field had two close embeddings. For example, the field defined by \((x-1)^2 - 2/10^{40}\) has two real embeddings that send its generator to \(1 \pm \sqrt{2}/10^{20}\). These operations now distinguish such embeddings and finish. For a relative tower, IsSubfieldEmb could stop with an assertion failure when an intermediate field had closer embeddings than the top field. It now uses the tolerance of each intermediate field. Composite now reports incompatible embeddings when two fields restrict to different close embeddings of a shared base field. It previously ran without end for these inputs. IsSubfieldEmb now reports incompatible embeddings when two fields restrict to different close embeddings of a shared base field. It previously returned true for these inputs.

Algebraic Number Fields and Orders

  • Relations of an order of a number field are now returned over the field of fractions as they are not always integral.

  • CoveringStructure of orders has been fixed for orders of algebraic number fields where one was the suborder of the other.

  • Equality of orders of algebraic number fields has been improved when linear extensions are involved.

Algebraic Surfaces

  • Additional input checking for IntersectionMatrixOnDegree2K3 was added, as the input was required to be reduced, but no checking was done. Reported by Edgar Costa.

Algebraically Closed Fields

  • Roots of a polynomial over the algebraic closure of a prime field GF(p) with p larger than 2^30 could fail with an internal error. This has been fixed. Reported by Edgar Costa.

  • Simplify on an algebraically closed field, and computations that simplify one internally, could fail with an internal error or give wrong results. This has been fixed.

Algebras

  • Fixed Eltseq on an element of a group algebra created with Rep := "Terms", which aborted with an internal error on Apple silicon (and crashed on optimized builds) while returning the correct answer elsewhere. The sequence of coefficient and group element pairs is now built correctly on every platform. Reported by Edgar Costa.

Associative Algebras

  • A crash has been fixed in powering of elements of orders of associative algebras .

Coding Theory

Commutative Algebra

  • MinimalPolynomial of a constant in an algebraic closure in which no roots had yet been taken could fail with an internal error. This has been fixed. Reported by Edgar Costa.

Complex Field

  • Fixed a memory leak in Root for complex numbers.

Elliptic Curves

  • EllipticCurve applied to a genus 1 hyperelliptic curve over a finite field failed when the curve had no rational Weierstrass point and no rational point at infinity. It now finds a rational point itself.

  • A numerical precision problem in the reduction of elliptic curves over number fields has been fixed. Reported by David Zureick-Brown.

  • A slowness in the point counting for elliptic curves over finite fields has been fixed. Reported by Eric Rains.

Finite Fields

  • In Magma format (print F : Magma;), a prime field F printed as GF(p, 1) for \(p > 2^{30}\) in the Standard version of Magma. The Large version did so for \(p > 2^{62}\), and a matrix over such a field padded its entries to the widest entry. Prime fields now print as GF(p) for every p in both versions, with matrix entries over them padded to the number of digits of p. (Issue #154)

  • In the Large version of Magma, Conway polynomials for primes \(p \ge 131\) were not found in the external Conway polynomial database, so ExistsConwayPolynomial(p, n) wrongly returned false and GF(p^n) was constructed with a non-primitive defining polynomial (e.g. \(x^2 + 1\) for GF(131^2)). Code relying on the generator of GF(q) being a primitive element, such as RecogniseSL2 applied to SimpleGroup(2134), consequently failed. The database reader now handles the 32-bit vs 64-bit issues properly, so both versions of Magma agree. Reported by Eamonn O’Brien.

Finitely Presented Groups

  • An internal error in Index for finitely presented groups has been fixed. (Issue #29) Reported by Don Taylor.

  • In the Large version of Magma, RWSMonoid and RWSGroup misread the Weights of the “WtLex” ordering and the Levels of the “Wreath” ordering. A rewrite rule could then point the wrong way: with Weights := [3, 1], the relation \(a = b^2\) could come back as \(b^2 = a\). The Large version now returns the same rewrite systems as the Standard version.

Galois Groups

  • Linear extensions have been better handled in Galois group computations. Reported by Markus Grassl.

  • In the Large version of Magma, the old Galois group algorithm (GaloisGroup with parameter Old set to true) failed with an internal error when reading its group tables from the Galois data files (because of 32-bit vs 64-bit issues). The files are now read with fixed widths, so both versions of Magma agree.

  • GaloisGroup with parameter Old set to true (the old Galois group algorithm) could crash with a segmentation fault for some polynomials, for example \(x^7 - 7x + 3\), because a complex world used for precision bounds was freed while still in use. This is now fixed.

Global Fields

  • In rare cases, the class group proof algorithm stopped with the error No class group proof found. This is caused by reaching the give up bound of the algorithm. The bound is raised to make this error extremely unlikely. A further inspection of the example resulted in several speedups, the given example is now twice as fast. Reported by Armand Brumer.

Graphs

  • Fixed AutomorphismGroup with Al := "Traces" on graphs whose canonical labelling reaches the group order outside the main Traces search. The internal record of the order’s prime factorisation was allocated too late, and was reset after part of the order had already been computed, so such a call either failed with an internal error or returned a group whose order was too small while its generators were correct. The factorisation is now allocated and made available once per call, before any factor is contributed. (Issue #139) Reported by Saul D Freedman.

Groebner Bases

  • An occasional crash in the multi-threaded version of the linear algebra phase of the \(F_4\) algorithm when a very large number of threads were used has been fixed.

  • On Apple Silicon (arm64) Macs, GroebnerBasis using the multi-threaded \(F_4\) algorithm (after SetNthreads with more than one thread) could return a wrong basis, such as the unit ideal for the cyclic-8 system at 4 threads, and with many threads could also fail with an internal error, hang or crash. Several hand-offs of data between the threads were not ordered on that architecture. This has been fixed. Reported by Eran Assaf.

  • The multi-threaded linear algebra phase of the \(F_4\) algorithm could, very rarely, fail with an internal error or hang at the end of a step when there were more threads than free cores. This has been fixed. Reported by Edgar Costa.

  • The multi-threaded \(F_4\) algorithm in GroebnerBasis no longer slows down badly when SetNthreads is given more threads than there are free cores. For example, on a 10-core machine the cyclic-7 system over the rationals took 42.7 seconds with 20 threads (against 0.3 seconds with 8); it now takes 0.6 seconds.

Hilbert Modular Forms

  • NewformDecomposition for Hilbert modular forms could fail with “Failed to find isomorphism class for right ideal” in a seed-dependent way. The small-prime path in the Hecke operator precomputation calls Subideals_of_ideal_newer, which assumes that the Hecke prime P does not divide the norm of any right ideal class representative. When that assumption fails, the computed subideals are wrong and their isomorphism class cannot be identified. The fix detects this condition and falls back to the large-prime (colon-ideal) method, which handles the degenerate case correctly. Reported by Lassina Dembele.

Hyperelliptic Curves

  • In the Large version of Magma, Theta could fail to return for a period matrix of genus 2 or more, while its memory use kept growing. One example is zero characteristic and zero argument with period matrix \(\mathrm{diag}(i, i)\). The lattice-point search in Theta now handles the 32-bit vs 64-bit issue properly, so both versions of Magma agree.

Language/System

  • StringToInteger(s, b) rejected every digit above F, whatever the base. Since b may be as large as 36, and IntegerToString writes the bases above 16 using the letters G to Z, a string Magma had written itself could not be read back. The digits of every base up to 36 are now accepted. The Handbook entry also gave the base as a MonStgElt rather than a RngIntElt, and now states the permitted range of b. Reported by David Roe.

  • Fixed a bug where binary and hexadecimal integers caused a syntax error when following an arithmetic operator. (Issue #42)

  • Fixed a memory leak and handle safety issues in complex Gamma.

  • After an error partway through an arithmetic expression, such as a source file ending just after a +, the statement read next was still taken to be part of a polynomial and was rejected with an unrelated message such as “Illegal left hand side of an assignment statement”. This has been fixed.

  • A hexadecimal or binary integer literal whose leading digit was not 0, such as 9xff or 5b10, was accepted and read as though the leading digit had been 0. Such literals are now rejected.

  • A system package import (import !) now resolves against the directory named by MAGMA_SYSTEM_PACKAGE_ROOT when that environment variable is set. The supplied magma script sets it to the installation’s package directory, so SetLibraryRoot does not move system imports in that case. When the variable is unset, imports retain the previous behaviour: they resolve from the package directory beside the current library root. SetLibraryRoot still moves system imports in that case.

  • Fixed precision parameter passed to PARI in JacobiThetaNullK.

Local Rings

  • Computing valuation of a polynomial over an inexact ring is no longer used when computing GCD of polynomials over inexact rings. (Issue #126) Reported by Sachi Hashimoto.

  • IsZero for elements of local fields now no longer returns true for imprecise zeros.

  • Sqrt, IsSquare, Root and IsPower of an imprecise zero \(O(\pi^v)\) of negative valuation over a \(p\)-adic field returned a root whose valuation was too large, claiming precision the root need not have. For an \(n\)-th root the valuation of the result is now Ceiling(\(v/n\)), the sharpest bound that is still correct.

Matrices

  • On macOS (Apple Silicon), printing a sparse matrix, or a dense matrix with few non-zero entries, at the Magma print level could show column numbers and the number of columns 2^32 too large. This has been fixed.

Matrix Groups

  • The file con.m of the Husert package for conjugacy in \(GL_n(\mathbb{Z})\) (package/Group/GrpMat/GLnZ-conjugacy/husert) has been renamed conj.m, because CON is a reserved device name on Windows.

Polynomial Rings

  • Discriminant for a polynomial over Integers(M) with M composite, or over a p-adic quotient ring, or over a polynomial ring over such a ring, could give an internal error or a wrong result when the leading coefficient is a zero divisor. This has been fixed.

  • Multiplying two univariate polynomials with at least 3 terms each in a multivariate polynomial ring over a ring with zero divisors, such as Integers(4), gave an internal error when the product is zero. This has been fixed.

Quaternion Algebras

  • Embed of a quadratic order into an Eichler order of a quaternion algebra could fail with a spurious “Arguments must have the same right order” error when the conjugating element it searched for produced a non-sated ideal (one whose true right order is larger than the given order). The ideal is now formed over its own right order, so the embedding is found and returned as expected. (Issue #48) Reported by Steve Huang.

Rational Curves and Conics

  • Random for a conic over a finite field returned two values, a boolean and then the point, instead of just the point. This has been fixed. Reported by Jim Stark.

Series Rings

  • Improvements have been made to precision handling in arithmetic with elements of extensions of series rings. Improvements have been made to precision handling when computing images under homomorphisms from series rings into extensions of series rings. (Issue #108)

  • Derivative(f, n) for a power series f gave an internal error when n was negative, instead of a runtime error. This has been fixed. (Issue #129) Reported by Edgar Costa.

System

  • The macOS launcher explains how to select the Intel engine under Rosetta when an Intel-only installation is opened on Apple silicon.

Back to Patch Notes