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.

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 outline an algorithm to compute $\unicode[STIX]{x1D703}(z,\unicode[STIX]{x1D70F})$ in genus two in quasi-linear time, borrowing ideas from the algorithm for theta constants and the one for $\unicode[STIX]{x1D703}(z,\unicode[STIX]{x1D70F})$ in genus one. Our implementation shows a large speed-up for precisions as low as a few thousand decimal digits. We also lay out a strategy to generalize this algorithm to genus $g$.

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.

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.

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.

We investigate existence and uniqueness of p-means ep and the median e1 of a probability measure μ on a Finsler manifold, in relation with the convexity of the support of μ. We prove that ep is the limit point of a continuous time gradient flow. Under some additional condition which is always satisfied for p≥2, a discretization of this path converges to ep. This provides an algorithm for determining the Finsler center points.

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.

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$.

The object of this article is to examine a conjecture of Zassenhaus and certain variations of it for integral group rings of sporadic groups. We prove the ℚ-variation and the Sylow variation for all sporadic groups and their automorphism groups. The Zassenhaus conjecture is established for eighteen of the sporadic simple groups, and for all automorphism groups of sporadic simple groups G which are different from G. The proofs are given with the aid of the GAP computer algebra program by applying a computational procedure to the ordinary and modular character tables of the groups. It is also shown that the isomorphism problem of integral group rings has a positive answer for certain almost simple groups, in particular for the double covers of the symmetric groups.

A prime sieve is an algorithm that finds the primes up to a bound $n$. We say that a prime sieve is incremental, if it can quickly determine if $n+1$ is prime after having found all primes up to $n$. We say a sieve is compact if it uses roughly $\sqrt{n}$ space or less. In this paper, we present two new results.

–

We describe the rolling sieve, a practical, incremental prime sieve that takes $O(n\log \log n)$ time and $O(\sqrt{n}\log n)$ bits of space.

The second result solves an open problem given by Paul Pritchard in 1994.

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.

The author considers the development of algorithms for deciding whether a finitely generated matrix group over a field of positive characteristic is finite. A deterministic algorithm for deciding the finiteness is presented for the case of a field of transcendence degree one over a finite field.

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 provide strong experimental evidence for an upper bound on the number of endpoints of the cut locus from a point on a 2-surface of revolution. This bound is equal to the minimal number of intervals of monotone non-increasing or non-decreasing Gaussian curvature along one meridian from one pole to the other.

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.

Inspired by methods of N. P. Smart, we describe an algorithm to determine all Picard curves over $\mathbb{Q}$ with good reduction away from 3, up to $\mathbb{Q}$-isomorphism. A correspondence between the isomorphism classes of such curves and certain quintic binary forms possessing a rational linear factor is established. An exhaustive list of integral models is determined and an application to a question of Ihara is discussed.

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.