In a paper of 1933, D. H. Lehmer continued Pierce's study of integral sequences associated to polynomials generalizing the Mersenne sequence. He developed divisibility criteria, and suggested that prime apparition in these sequences — or in closely related sequences — would be denser if the polynomials were close to cyclotomic, using a natural measure of closeness.

We review briefly some of the main developments since Lehmer's paper, and report on further computational work on these sequences. In particular, we use Mossinghoff's collection of polynomials with smallest known measure to assemble evidence for the distribution of primes in these sequences predicted by standard heuristic arguments.

The calculations lend weight to standard conjectures about Mersenne primes, and the use of polynomials with small measure permits much larger numbers of primes to be generated than in the Mersenne case.

For a $t$-nomial $f(x)=\sum _{i=1}^{t}c_{i}x^{a_{i}}\in \mathbb{F}_{q}[x]$, we show that the number of distinct, nonzero roots of $f$ is bounded above by $2(q-1)^{1-\unicode[STIX]{x1D700}}C^{\unicode[STIX]{x1D700}}$, where $\unicode[STIX]{x1D700}=1/(t-1)$ and $C$ is the size of the largest coset in $\mathbb{F}_{q}^{\ast }$ on which $f$ vanishes completely. Additionally, we describe a number-theoretic parameter depending only on $q$ and the exponents $a_{i}$ which provides a general and easily computable upper bound for $C$. We thus obtain a strict improvement over an earlier bound of Canetti et al. which is related to the uniformity of the Diffie–Hellman distribution. Finally, we conjecture that $t$-nomials over prime fields have only $O(t\log p)$ roots in $\mathbb{F}_{p}^{\ast }$ when $C=1$.

Abstract:We give an algorithm for finding the module of linear dependencies of the roots of a monic integral polynomial. Using this, we describe an algorithm for constructing the algebraic hull of a given matrix Lie algebra in characteristic zero.

We describe an algorithm to prove the Birch and Swinnerton-Dyer conjectural formula for any given elliptic curve defined over the rational numbers of analytic rank zero or one. With computer assistance we rigorously prove the formula for 16714 of the 16725 such curves of conductor less than 5000.

We analyse and drastically improve the running time of the algorithm of Mazur, Stein and Tate for computing the canonical cyclotomic p-adic height of a point on an elliptic curve E/Q, where E has good ordinary reduction at p ≥ 5.

We classify the radical p-subgroups and chains of the Fischer simple group Fi′24 and then verify the Alperin weight conjecture and the Uno reductive conjecture for Fi′24.

This paper presents an algorithm to construct cryptographically strong genus $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}2$ curves and their Kummer surfaces via Rosenhain invariants and related Kummer parameters. The most common version of the complex multiplication (CM) algorithm for constructing cryptographic curves in genus 2 relies on the well-studied Igusa invariants and Mestre’s algorithm for reconstructing the curve. On the other hand, the Rosenhain invariants typically have much smaller height, so computing them requires less precision, and in addition, the Rosenhain model for the curve can be written down directly given the Rosenhain invariants. Similarly, the parameters for a Kummer surface can be expressed directly in terms of rational functions of theta constants. CM-values of these functions are algebraic numbers, and when computed to high enough precision, LLL can recognize their minimal polynomials. Motivated by fast cryptography on Kummer surfaces, we investigate a variant of the CM method for computing cryptographically strong Rosenhain models of curves (as well as their associated Kummer surfaces) and use it to generate several example curves at different security levels that are suitable for use in cryptography.

A loop is (right) automorphic if all its (right) inner mappings are automorphisms. Using the classification of primitive groups of small degrees, we show that there is no non-associative simple commutative automorphic loop of order less than 212, and no non-associative simple automorphic loop of order less than 2500. We obtain numerous examples of non-associative simple right automorphic loops. We also prove that every automorphic loop has the antiautomorphic inverse property, and that a right automorphic loop is automorphic if and only if its conjugations are automorphisms.

The computation of growth series for the higher Baumslag–Solitar groups is an open problem first posed by de la Harpe and Grigorchuk. We study the growth of the horocyclic subgroup as the key to the overall growth of these Baumslag–Solitar groups BS(p,q), where 1<p<q. In fact, the overall growth series can be represented as a modified convolution product with one of the factors being based on the series for the horocyclic subgroup. We exhibit two distinct algorithms that compute the growth of the horocyclic subgroup and discuss the time and space complexity of these algorithms. We show that when p divides q, the horocyclic subgroup has a geodesic combing whose words form a context-free (in fact, one-counter) language. A theorem of Chomsky–Schützenberger allows us to compute the growth series for this subgroup, which is rational. When p does not divide q, we show that no geodesic combing for the horocyclic subgroup forms a context-free language, although there is a context-sensitive geodesic combing. We exhibit a specific linearly bounded Turing machine that accepts this language (with quadratic time complexity) in the case of BS(2,3) and outline the Turing machine construction in the general case.

A Maple package which performs the symbolic algebra central to problems in local singularity theory is described. This is a generalisation of previous projects, which dealt only with problems in elementary catastrophe theory. Applications to specific problems are described, and a survey given of the powerful techniques from singularity theory that are used by the package. A description of the underlying algorithm is given, and some of the more important computational aspects discussed. The package, user manual and installation instructions are available in the appendices to this article.

This paper provides details of a Magma computer program for calculating various homotopy-theoretic functors, defined on finitely presented groups. A copy of the program is included as an Add-On. The program can be used to compute: the nonabelian tensor product of two finite groups, the first homology of a finite group with coefficients in the arbirary finite module, the second integral homology of a finite group relative to its normal subgroup, the third homology of the finite p-group with coefficients in Zp, Baer invariants of a finite group, and the capability and terminality of a finite group. Various other related constructions can also be computed.

Let K denote a number field, and G a finite abelian group. The ring of algebraic integers in K is denoted in this paper by $/cal{O}_K$, and $/cal{A}$ denotes any $/cal{O}_K$-order in K[G]. The paper describes an algorithm that explicitly computes the Picard group Pic($/cal{A}$), and solves the corresponding (refined) discrete logarithm problem. A tamely ramified extension L/K of prime degree l of an imaginary quadratic number field K is used as an example; the class of $/cal{O}_L$ in Pic($/cal{O}_K[G]$) can be numerically determined.

We develop the theory of Abelian functions associated with algebraic curves. The growth in computer power and the advancement of efficient symbolic computation techniques have allowed for recent progress in this area. In this paper we focus on the genus three cases, comparing the two canonical classes of hyperelliptic and trigonal curves. We present new addition formulae, derive bases for the spaces of Abelian functions and discuss the differential equations such functions satisfy.

Supplementary materials are available with this article.

The four colour theorem states that the vertices of every planar graph can be coloured with at most four colours so that no two adjacent vertices receive the same colour. This theorem is famous for many reasons, including the fact that its original 1977 proof includes a non-trivial computer verification. Recently, a formal proof of the theorem was obtained with the equational logic program Coq [G. Gonthier, ‘Formal proof–the four color theorem’, Notices of Amer. Math. Soc. 55 (2008) no. 11, 1382–1393]. In this paper we describe an implementation of the computational method introduced by C. S. Calude and co-workers [Evaluating the complexity of mathematical problems. Part 1’, Complex Systems 18 (2009) 267–285; A new measure of the difficulty of problems’, J. Mult. Valued Logic Soft Comput. 12 (2006) 285–307] to evaluate the complexity of the four colour theorem. Our method uses a Diophantine equational representation of the theorem. We show that the four colour theorem is in the complexity class ℭU,4. For comparison, the Riemann hypothesis is in class ℭU,3 while Fermat’s last theorem is in class ℭU,1.

We classify the simple Lie algebras of dimension at most 9 over GF(2). There is one of dimension 3 and one of dimension 6, there are two of dimension 7 and two of dimension 8, and there is one of dimension 9. The two simple Lie algebras of dimension 8 are restricted Lie algebras. If we extend the ground field to GF(4), then the six-dimensional algebra is no longer simple, and if we extend the ground field to GF(8) then the nine-dimensional algebra is no longer simple. But the other algebras are all central simple.

We construct explicit examples of E8 lattices occurring in arithmetic for which the natural Galois action is equal to the full group of automorphisms of the lattice, i.e., the Weyl group of E8. In particular, we give explicit elliptic curves over Q(t) whose Mordell-Weil lattices are isomorphic to E8 and have maximal Galois action.

Our main objects of study are del Pezzo surfaces of degree 1 over number fields. The geometric Picard group, considered as a lattice via the negative of the intersection pairing, contains a sublattice isomorphic to E8. We construct examples of such surfaces for which the action of Galois on the geometric Picard group is maximal.

Long-term solutions of the theta method applied to scalar nonlinear differential equations are studied in this paper. In the case where the equation has a stable steady state, lower bounds on the basin of non-oscillatory, monotonic attraction for the theta method are derived. Spurious period two solutions are then analysed. Under mild assumptions, precise results are obtained concerning the generic nature and stability of these solutions for small timesteps. Particular problem classes are studied, and direct connections are made between the existence and stability of period two solutions and the dynamics of the theta method. The analysis is extended to a wide class of semi-discretized partial differential equations. Numerical examples are given.

Suppose that p is 3,5,7,11 or 13. We classify the radical p-chains of the Monster 𝕄 and verify the Alperin weight conjecture and Uno’s reductive conjecture for 𝕄, the latter being a refinement of Dade’s reductive conjecture and the Isaacs–Navarro conjecture.

The aim of this paper is to extend the previous work on transfer matrix compression in the case of graph homomorphisms. For H-homomorphisms of lattice-like graphs we demonstrate how the automorphisms of H, as well as those of the underlying lattice, can be used to reduce the size of the relevant transfer matrices. As applications of this method we give currently best known bounds for the number of 4- and 5-colourings of the square grid, and the number of 3- and 4-colourings of the three-dimensional cubic lattice. Finally, we also discuss approximate compression of transfer matrices.

The zeros of certain different sequences of orthogonal polynomials interlace in a well-defined way. The study of this phenomenon and the conditions under which it holds lead to a set of points that can be applied as bounds for the extreme zeros of the polynomials. We consider different sequences of the discrete orthogonal Meixner and Kravchuk polynomials and use mixed three-term recurrence relations, satisfied by the polynomials under consideration, to identify bounds for the extreme zeros of Meixner and Kravchuk polynomials.