In the talk, I will present an efficient algorithm to compute the decomposition of the Jacobians of modular curves of arbitrary level, using modular symbols. This is obtained by working intrinsically with the curve, unlike previous methods. I will also discuss the possible consequences for deriving equations of modular curves.

In this talk, we will overview several techniques to compute the Hodge cycles on surfaces.

We will start by studying the self-product of a curve, with the goal of computing the endomorphism of its Jacobian.

We will follow this with the problem of computing the Picard lattice of a K3 surface.

In this talk, I will describe a p-adic algorithm for computing the zeta function that does not rely on any cohomology theory. This algorithm takes as input a geometrically irreducible plane curve over a finite field and outputs the zeta function of the nonsingular completion of that curve. Unlike many other efficient algorithms for this problem, there are no smoothness or nondegeneracy conditions imposed on the input plane curve. The algorithm is based on Harvey's algorithm for counting points on hypersurfaces, which is applicable to a completely general hypersurface.

A version of this algorithm with time complexity O(p^2) is currently available in MAGMA. A version with time complexity O(p) will soon be implemented.

I will compare the performance of this new algorithm with that of Tuitman's algorithm, and provide examples of inputs that cannot be handled by Tuitman's algorithm but can be handled by the new algorithm.

Using Magma, we prove that the transitive permutation group 17T7 is a Galois group over the rationals, completing the list of transitive subgroups ordered by degree up to 23 (leaving the Mathieu group on 23 letters as the next missing group). We exhibit such a Galois extension as the field of definition of 2-torsion on an abelian fourfold with real multiplication defined over a real quadratic field with Galois alignment. We find such fourfolds using Hilbert modular forms. Finally, building upon work of Dembele, we show how to (conjecturally) reconstruct the period matrix for abelian variety attached to a Hilbert modular form; we then use this to construct an explicit degree 17 polynomial with Galois group 17T7. This is joint work with Raymond van Bommel, Edgar Costa, Noam Elkies, Timo Keller, and Sam Schiavone.

The computation of the normaliser of a permutation group in the full symmetric group is an important and hard problem in computational group theory. In this talk, I will report on an algorithm that builds a descending chain of overgroups to determine the normaliser. The performance is compared with other implementations. We end with an inspection of several interesting examples.

I will describe practical methods for the construction of ordinary representations of a finite group G via the extension of existing representations defined on a proper subgroup of G. I will also describe how, using an implementation of this algorithm within Magma, I was able to construct for the first time minimal-degree faithful ordinary representations of most of the large sporadic simple groups, such as the Baby Monster.

In this talk I will explain my work on the Linear System package of Magma. I will highlight the main optimizations and demonstrate their impact through practical algebraic geometry examples, in particular the computation of singular algebraic curves and surfaces.

Let $A=k[t]$ be the polynomial ring over the perfect field $k$ and $fın A[x]$ be a monic irreducible separable polynomial. Denote by $F/k$ the function field determined by $f$ and consider a given non-zero prime ideal $\mathfrak{p}$ of $A$. The Montes algorithm determines a new representation, so called OM-representation, of the prime ideals of the (finite) maximal order of $F$ lying over $\mathfrak{p}$. This yields a new representation of places of function fields. In this talk we summarize briefly some applications of this new representation; that are the computation of the genus, the computation of the maximal order, and the improvement of the computation of Riemann-Roch spaces.

When computing with subgroups of a finite symmetric group Sym(n), we generally seek algorithms whose worst-case running time is bounded by a low-degree polynomial in n. However, there are a range of problems where no such algorithms are known, and where the best current methods involve algorithms whose running time may be much worse than this. I'll give an introduction to this class of problems, present results on various special cases where we can recover polynomial running time, and briefly discuss some ongoing work on computing normalisers in the full symmetric group. The new material is joint work with Mun See Chang and Chris Jefferson at St Andrews.

Let $C$ be a smooth projective geometrically irreducible algebraic curve of genus $g$ over a field $k$. The Jacobian variety $J$ of $C$ is a $g$-dimensional algebraic group that parametrizes the degree zero divisors on $C$, up to linear equivalence. Khuri-Makdisi showed that the basic arithmetic in $J$ can be realized in an asymptotic complexity of $O(g^{3+\epsilon})$ field operations in $k$. Denote by $F=k(C)$ the function field of the curve. Then the elements of $J$ can be identified with divisor classes $[D]$ of the function field $F/k$ where $D$ can be represented by a lattice $L_D$ over the polynomial ring $k[t]$. In fact, the class $[D]$ can be parametrized in terms of invariants of the lattice $L_D$. The basic arithmetic (addition and inversion) in $J$ can then be realized asymptotically in $O(g^3)$ field operations in $k$ and beats the one of Khuri-Makdisi. Under reasonable assumptions the runtime can be reduced to $O(g^2)$ field operations.

A bielliptic surface over the complex numbers is a quotient of a product of elliptic curves by a finite group acting by a combination of translations and automorphisms of the elliptic curves. The study of these surfaces over number fields has played an important role in our understanding of rational points on algebraic varieties. I will review this history and then describe recent computations with Magma showing that Skorobogatov's famous bielliptic surface does indeed have a zero-cycle of degree 1, as predicted by a conjecture of Colliot-Thelene.

We consider the problem of solving multivariate systems of Boolean polynomial equations: starting from a system of $m$ polynomials of degree at most $d$ in $n$ variables, we want to find its solutions over GF(2). Except for $d=1$, the problem is known to be NP-hard, and its hardness has been used to create public cryptosystems; this motivates the search for faster algorithms to solve this problem. After reviewing the state of the art, we describe a new algorithm and show that it outperforms previously known methods in a wide range of relevant parameters. In particular, it can be used to solve all the Fukuoka Type~I MQ challenges, culminating with the resolution of a system of 148 quadratic equations in 74 variables in less than a day (and quite a lot of luck).

We will give an overview of a project to compute the orbits and stabilizers of subspaces in a module of small dimension over a finite group. This is work in progress.

I will describe a practical algorithm for the construction of an ordinary representation of a finite group $G$ via the extension of an existing representation defined on a proper subgroup of $G$. I will also describe how, using an implementation of this algorithm within Magma, I was able to construct (for the first time ever) explicit minimal-degree ordinary representations of several of the large sporadic finite simple groups, such as the Baby Monster.

A finitely presented group is called hyperbolic if geodesic triangles in its Cayley graph are uniformly thin or, equivalently, if its Dehn function is linear.

The programs in the author's KBMAG package, which is implemented in Magma, can verify hyperbolicity of a given finitely presented group.

In this talk we describe new methods for proving hyperbolicity and for estimating the Dehn function that are based on small cancellation theory and the analysis of the curvature of van Kampen diagrams for the group. The first version of a Magma implementation is available.

These methods are due to Richard Parker and many others. They have the disadvantage that they are not guaranteed to succeed on every hyperbolic group presentation, but when they do they are generally much faster than KBMAG. They can also sometimes be carried out by hand on infinite families of presentations, whereas KBMAG can only be applied to individual presentations.

Counting the number of solutions to polynomial equations over finite fields, or equivalently computing the zeta function of algebraic varieties over finite fields, is a very central problem in computational number theory. For example, it is important for investigating famous conjectures like the (generalised) Birch and Swinnerton-Dyer, Sato-Tate, Lang-Trotter conjectures and parts of the Langlands program, but also has applications to public key cryptography and coding theory. Up until recently (apart from trivial cases) Magma could only really compute zeta functions of hyperelliptic curves. Recent work and code of mine (partly joint with Wouter Castryck) extends this to a much larger class of curves. My talk will give a survey of what Magma could do before it included my code, what it can do now and what it might be able to do in the future. The talk will not be very technical and should have something interesting for anyone interested in computer algebra or number theory.

The slides from this talk are on Jan's web page at https://perswww.kuleuven.be/~u0055310/magma.pdf

The local global-principle states that two hermitian spaces over some number field $K$ are isometric if and only if they are isometric over every completion of $K$.

The genus of a lattice $L$ in an hermitian space consists of those lattices which are isometric to $L$ locally everywhere. Every genus decomposes into finitely many isometry classes. The number of isometry classes in a genus is called its class number. Hence the genera with class number one are precisely those lattices for which the local-global principle holds.

For indefinite lattices, the class number can be expressed a-priori in terms of some local invariants. For definite lattices, such a description is not possible. However, up to similarity, there are only finitely many genera with a given class number.

In my talk, I will present the classification of all definite hermitian lattices of class number one.

Given generators for a permutation group we want to quickly decide if the group is giant, that is, alternating or symmetric in their natural representation.

These groups are so much larger than other permutation groups of the the same degree that we need to take care in dealing with them.

I will look at a Monte Carlo algorithm that recognises these groups with very little random sampling. We get a practical algorithm that is better than current methods in Magma, and is also asymptotically good. The new algorithm solves knapsack problems, which in this case can be kept small, and hence solved quickly.

I will give an overview of the methods I used in the past years to count points on varieties over finite fields. In the second part, I will expain a p-adic method that can compute #V(F_p^d) for a hypersurface in polynomial time. Finally we will apply these methods to some K3 surfaces and analyze their exceptional behaviour.

We review the extent to which the Composition Tree based methods of Baarnhielm, Leedham-Green, O'Brien et al can be used to carry out structural computations in large matrix groups over finite field without resort to methods based on bases and strong generating sets. We concentrate particularly on the computation of element centralisers, subgroup normalisers, conjugacy classes, and (work in progress) character tables.

The computation of the Galois group of a polynomial with rational coefficients is done in magma by using Stauduhar's method. On a first glace this approach looks quite simple. But in its initial form it could only give heuristic results for polynomials of degree at most 7.

In this talk I will explain variations of the method that enable us to determine the Galois group of a degree 20 polynomial with moderate coefficients in about 1 second. Finally, we will have a try with a degree 63 polynomial.

The minimal permutation degree of a finite group $G$ is the smallest non-negative integer $n$ such that $G$ embeds inside $Sym(n)$. This invariant is easy to define but very difficult to calculate in general. Moreover, it doesn't behave well under algebraic constructions such as direct product and homomorphic image. For example, it is possible for the minimal degree of a homomorphic image to be strictly larger than that of the group -- such groups are called 'exceptional'.

In this talk, I will describe how this invariant maybe calculated by a greedy algorithm for nilpotent groups and report on recent work with Britnell and Skyner on classifying exceptional groups of order p^5.

I will describe a new formula for adding 2-coverings and 3-coverings of elliptic curves that avoids the need for any field extensions. By searching for rational points on the 6-coverings obtained, we can then find generators for the Mordell-Weil group of large height. However before searching for rational points, it helps to make a good choice of co-ordinates, by a combination of minimisation and reduction. I will discuss the minimisation problem for 6-coverings. In particular it turns out that adding a minimal 2-covering and a minimal 3-covering (using my formula) does not give a minimal 6-covering.

A family of hypergeometric motives can be determined by a coprime pair of products of cyclotomic polynomials, each product having the same degree $d$. For each $t$ not 0, 1, or infinity, one can then (following Katz) associate a motive $M_t$ to this data. At each prime $p$, one obtains an Euler factor by considering the monodromy action (over $Q_p$) on the solution space of the associated hypergeometric differential equation. For good primes, this can be explicitly calculated by a trace formula (again see Katz). There are three kinds of bad primes. The wild primes are those which divide one of the indices of the cyclotomic polynomials. The tame primes are with $v_p(t)$ nonzero, and the "multiplicative" primes are those with $v_p(t-1)$ nonzero. These last are the easiest to understand, in the complex case they correspond to the fact that there are $(d-1)$ independent holomorphic solutions about $t=1$. Indeed, one can consider the formal motive $M_1$ at $t=1$ -- as an example, in the case of $\Phi_5$ and $\Phi_1^4$, one obtains the weight 4 modular form of level 25.

We report specifically on a "database" of $t=1$ degenerations, including all choices (about 1500 total) of cyclotomic data up through degree 6. In each case, we are able to numerically determine the wild Euler factors and verify the functional equation of the L-function to (say) 15 digits of precision. Of additional interest is the fact that approximately half the relevant (odd motivic weight) examples of even parity appear to have analytic rank 2.

In this talk, I will report on joint work with Stephen Tawn.

In the course of an experiment analysing statistical properties of samples of random braids, we made two rather surprising observations: except for an initial and a final region whose lengths are uniformly bounded, the distributions of the factors of the normal form of sufficiently long random braids depend neither on the position in the normal form nor on the lengths of the random braids.

When multiplying the normal form of a braid on the right, the expected number of factors in the normal form that are modified, called the expected penetration distance, is bounded uniformly in the length of the braid.

It turns out that these observations can be explained by analysing two regular languages associated to normal forms of elements of Garside monoids. More specifically, there is a simple condition on the growth rates of these regular languages that characterises those Garside monoids that exhibit the phenomena mentioned above. In particular, all Artin--Tits monoids of spherical type do.

I will report on recent joint work with Andreas-Stephan Elsenhans, in which we construct explicit examples of K3 surfaces having real multiplication. Our examples are of Picard rank 16. The standard method for the computation of the Picard rank provably fails for the surfaces constructed. The existence of K3 surfaces having real multiplication was proven before, using a Hodge-theoretic approach, which did not lead to explicit equations. Our approach involves a massive computer search using MAGMA.

Given a permutation group G and a subgroup U, the ring of invariants of U is larger than the one for G. Thus, one can ask for a U-invariant that is not G-invariant. This is exactly the problem one has to solve for the computation of Galois groups.

As we deal with permutation groups, the first try is to use block systems to attack the problem. However in some cases this does not yield suitable invariants. I will explain how the transfer map and the Reynolds operator can be used to construct invariants. In the case of intransitive groups we will use the main theorem of subdirect products to solve the problem.

The methods suffice to construct invariants for all examples arising from the transitive permutation group database of all transitive groups up to degree 32.

http://smartfacts.cr.yp.to/

This talk presents extremely fast algorithms for code-based public-key cryptography, including full protection against timing attacks. For example, at a 2^128 security level, these algorithms achieve a reciprocal decryption throughput of just 60493 cycles (plus cipher cost etc.) on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks. This is joint work with Tung Chou (Technische Universiteit Eindhoven) and Peter Schwabe (Radboud Universiteit Nijmegen).

In this talk, we will review classical methods to write down and to compute invariants of homogeneous forms. This will lead us to a short inspection of covariants and contravariants.

In a second part, I will explain how to use these technics for an efficient numerical computation of invariants.

We will apply this to the case of plane quartic curves. This will lead to a complete system of invariants.

Finally we inspect invariants for cubic surfaces. In this case we can compute invariants for a surface and we can construct surfaces with prescribed invariants.

The Grunwald-Wang theorem is a result about the interaction of local and global arithmetic of the multiplicative group. I will discuss some analogs for elliptic curves and more generally abelian varieties.

Let $G$ be an arbitrary group such that $G/Z(G)$ is finite, where $Z(G)$ denotes the center of the group $G$. Then $\gamma_2(G)$, the commutator subgroup of $G$, is finite. This result is known as Schur's theorem. The converse of this result is not true in general as shown by infinite extra-special $p$-groups for odd primes. But when $G$ is finitely generated by $d$ elements (say) and $\gamma_2(G)$ is finite, it was proved by B. H. Neumann that $|G/Z(G)| łe |\gamma_2(G)|^d$. In this talk I start with this basic result, discuss a slight generalization and classify all non-abelian finite nilpotent groups $G$ minimally generated by $d := d(G)$ elements such that central quotient is maximal, i.e., $|G/Z(G)| = |\gamma_2(G)|^d$. First I reduce the problem to finite $p$-groups and then notice that such $p$-groups admit maximum number of (conjugacy) class-preserving automorphisms. Using this and some basic Lie theoretic techniques, I show that $d(G)$ is even. Moreover, when the nilpotency class of $G$ is at least $3$, then $d(G) = 2$. The situation is then divided into two cases, depending on whether $p$ is even (Magma is extremely useful in this case) or odd, and a complete classification is presented. All $p$-groups $G$ considered above satisfy the following condition: $|x^G| = |\gamma_2(G)|$ for all $x ın G - \Phi(G)$, where $x^G$ denotes the conjugacy class of $x$ in $G$ and $\Phi(G)$ denotes the Frattini subgroup of $G$. Let me call such a group Camina-type. One of my motives to visit the Computational Algebra group here is to find a solution to the following problem: Does there exist a finite Camina-type $p$-group $G$, $p$ odd, of nilpotency class at least $3$ such that $\gamma_2(G) < \Phi(G)$ and $\gamma_2(G)$ is non-cyclic ?

In their book "The Structure of Groups of Prime Power Order", C.R. Leedham-Green and S. McKay describe an approach to constructing certain types of maximal class p-groups using the ring of integers in a local cyclotomic number field. By implementing these computations (in Magma), I've been able to explore possible commutator structures, especially as they relate to some character degree questions. This talk will look at the computations and some of the results.

Certain areas of Iwasawa theory requires knowledge of only the p-part of the class group. Computing this unconditionally with the full class group algorithm is infeasible for all but the simplest number fields. In this talk I will present a p-adic algorithm for computing/verifying the p-valuation of class numbers of totally real abelian number fields. This is joint work with my supervisor Claus Fieker.

For each positive $d$, the elliptic curve $d*y^2 = x^3 - x$ has positive rank if and only if $d$ is the area of a right-angled triangle with rational sides, the latter being a question of antiquity. We do not address this question of positive rank per se, but rather present the results of some experiments trying to find $d$ such that the above elliptic curve has large rank. These can be seen as $d$ for which there exist "many" rational-sided triangles of area $d$.

Let X be a smooth double cover of a geometrically ruled surface over a separably closed field of characteristic different from 2. I will discuss recent work in which we give a finite presentation of the two-torsion in the Brauer group of X with generators given by central simple algebras over the function field of X and relations coming from the Neron-Severi group of X. I will also discuss some of the motivation for this coming from arithmetic applications such as computing Brauer-Manin obstructions to the existence of rational points. This is joint work with Bianca Viray.

I will begin with an informal presentation of motives and their associated L-series, with no technical prerequisites. I will next discuss Magma's current functionality in this context, including its ability to compute L-series of hypergeometric motives except for problematic factors associated with wild ramification. I will conclude by giving a new example illustrating a general method for computing these problematic factors.

This is joint work with Dr. Michael Monagan at Simon Fraser University. We present our recent work of scaling Maple's polynomial algorithms to multicore CPUs, including parallel algorithms with superlinear speedup and the new polynomial data structure that we have added to the kernel. The larger issue we hope to discuss is how to scale different computer algebra systems to future processors. Our strategy for Maple reflects its design as a small, compact kernel with high level library routines that scales down as well as up. The ideal strategy for Magma could be quite different, however I don't presume to know.

I will give an overview of work over the last year within Magma for computing discrete logarithms in finite fields of small characteristic. This is mostly based on Coppersmith's index calculus algorithm (with a simple extension beyond characteristic 2) and more recently a basic version of the "Double Rational" Function Field Sieve.

We present heuristic asymptotic formulae for the number of isogeny classes of pairing-friendly abelian varieties (PFAVs) over prime fields, generalising previous work of John Boxall on elliptic curves.
By enumerating Weil numbers satisfying "pairing-friendly" conditions we were able to count the number of PFAVs and compare with the heuristic value. In all the examples we computed, the results show good agreement with the heuristics.

I'll describe techniques used in the two new records that were announced in February. Joux computed discrete logs in GF(2^1778) and GF(2^4080), and Gogoglu-Granger-McGuire-Zumbragel (Dublin) in GF(2^1971).

Some startling records were recently announced, by Alain Joux for GF(2^1778) and GF(2^4080), and by a Dublin group for GF(2^1971).

I will explain the main ideas involved in the new techniques.

They developed from special variants of the "medium prime case" of the function field sieve (Joux + Lercier); this is a particularly simple formulation of the function field sieve. The earlier special variants were tricks based on using Kummer extensions, which would only be applicable for isolated fields. But these latest techniques apply more generally, each for a certain class of field.

Strikingly, Joux's algorithm has L(1/4,.) complexity whereas comparable algorithms always had L(1/3,.) at best. Another novelty in both algorithms is that the main phase is actually polynomial time while the descent phase is the bottleneck (usually, the phases are similar).

Continuation of the talk from last December. I will talk about some standard transformations and invariants of general algebraic surfaces and what functionality there currently is in Magma for computing these.

I will report on our work, joint with Andreas-Stephan Elsenhans, on the Brauer-Manin obstruction for certain cubic and K3 surfaces. Concerning cubic surfaces, the talk will present the case of a 2-torsion Brauer class, explain how the corresponding surface arise, and show why they violate weak approximation. Concerning K3 surfaces, a particular type of Kummer surfaces is considered, for which the transcendental Brauer-Manin obstruction is particularly well understood.

I will report on our work, joint with Andreas-Stephan Elsenhans, on the computation of the Picard rank for K3 surfaces over $\mathbb{Q}$.

Consider an algebraic ordinary differential equation (AODE), i.e. a polynomial relation between the unknown function and its derivatives. This polynomial defines an algebraic hypersurface. By considering rational parametrizations of this hypersurface, we can decide the rational solvability of the given AODE, and in fact compute the general rational solution. This method depends crucially on curve and surface parametrization and the determination of rational invariant algebraic curves. Transforming the ambient space by some group of transformations, we get a classification of AODEs, such that equivalent equations share the property of rational solvability. In particular we discuss affine and birational transformation groups.

I will discuss a p-adic formula for classical Heegner points on elliptic curves in terms of special values of certain p-adic L-functions - this is joint work with Henri Darmon and Victor Rotger. The formula has a natural generalisation which conjecturally yields other new types of global points. It was discovered experimentally using the Magma computer algebra package.

The number field sieve has been designed for factoring large numbers. It was also used for solving the discrete logarithm problem over prime fields.

In this talk, we discuss its applications to class group and unit group computation in a number field.

In the first part, we will describe the class group and the unit group of a number field and explain the relevance of their computation in computational number theory.

After an overview of the state of the art algorithms of such computations (mostly due to Buchmann), we will focus on the number field sieve. We will highlight the similarities between class group computation and factorization (and the resolution of the discrete logarithm problem), and then explain how to use the number field sieve for our purposes. Finally, we will present our implementation and discuss its performances.

One of the important operations with divisors on varieties is to decompose them into prime divisors. This is a special case of primary decomposition, but is theoretically simpler in many ways. I will describe various approache

I will discuss the current features for working with algebraic surfaces in Magma.

I will discuss a new algorithm for counting points on hyperelliptic curves over finite fields.

Magma computes Galois groups by using Stauduhar's method. In this talk I will describe some key steps of the implementation (done by Claus Fieker and Jurgen Kluners) that lead to the current performance. Finally, I will sketch some starting points for further improvements.

Polyhedral adjunction theory allows to study questions of classical adjunction theory for toric varieties from a purely combinatorial viewpoint. In my talk I will present the convex-geometric invariants corresponding to the (unnormalized) spectral value $\mu$ and the nef-value $\tau$ of a polarized toric variety associated to a lattice polytope. The polyhedral description allows explicit computations e.g. with the software polymake. As a main result I will show that a $d$-dimensional lattice polytope $P$ has lattice width one if $\mu\geq (d+2)/2$ and give some combinatorial and algebraic implications.

This is joint work with Benjamin Nill, Christian Haase, and Sandra Di Rocco (arxiv:1105.2415).

Computing with matrix groups over infinite rings is much more complicated then working with matrix groups over finite fields. For example, the membership problem is undecidable in general.

However, for subgroups of PSL(2, R) the situation is much betterr since we have geometric methods at hand.

In this talk, we will recall Rosenberger's classification of the discrete free subgroups G = < A, B> of PSL(2, R). Further, we will discuss how to solve the membership problem for such a group $G$ constructively. This is joint work with B. Eick and C. Leedham-Green.

Hypergeometric differential equations (dating to Gauss and before) are example of Fuchsian equations; their only singularities are regular at 0, 1, and infinity. A theorem of Pochhammer relates their monodromy to a group-theoretic question regarding pseudo-reflections, which was answered by Levelt in his 1961 thesis. In the arithmetic case, where the monodromy has (Galois-stable) roots of unity as eigenvalues, Katz gives an interpretation of the l-adic behaviour explicitly in terms of Gauss sums, and Rodriguez-Villegas conjectures the existence of a family of pure motives that realises this (at the level of Euler factors of the L-function). We give some examples of this jargon, discuss computations of Cohen, and describe the associated Magma package.

p-adic Hodge Theory deals with p-adic representations of p-adic Galois groups. Iwill present the results of my thesis on how to compute with objects involved in this theory. I will briefly recall notions on Galois representations with coefficients in finite fields. I will then present our main tool to study them: the theory of phi-modules. I will describe an algorithm for the reduction of phi-modules and explain how it can be used to compute invariants of Galois representations.

A nearfield is an algebraic structure which satisfies all the field axioms except perhaps the left distributive law and commutativity of multiplication.

The finite sharply doubly transitive permutation groups are in one-to-one correspondence with the finite nearfields and several large classes of non-Desarguesian projective planes can be constructed from nearfields.

User-defined types will be available in the next release of Magma and in this talk I review some of the structure theory of nearfields and report on their implementation via user-defined types.

In the talk we shall discuss methods for computing with finitely generated linear groups. We shall also present algorithms to solve a number of computational problems in this class of groups.

The $L_2$-quotient algorithm by Plesken and Fabianska finds for a given finitely presented group $G$ all quotients of $G$ which are isomorphic to some finite simple group $PSL(2, q)$, simultaneously for every prime power $q$. The $L_3$-$U_3$-quotient algorithm does the same for the quotients $PSL(3, q)$ and $PSU(3, q)$.

After giving a motivation for these algorithms, I will describe the basic ideas which combine methods from representation theory and commutative algebra. At the end, I will try to give a live demonstration of the algorithms with several examples.

I will outline a project to list Minkowski polynomials in four variables and sketch the connection with Fano 4-folds. This is experimental work in progress with Alessio Corti, Tom Coates, Sergei Galkin, and Vasily Golyshev.

Consider a system of polynomial equations with integer coefficients. For each prime number p, we may reduce modulo p to obtain a system of polynomials over the field of p elements, and then count the number of solutions. It is generally difficult to describe this count as an exact function of p, so instead we take a statistical point of view, treating the count as a random variable and asking for its limiting distribution as we consider increasing large ranges of primes. Conjecturally, this distribution can be described in terms of the conjugacy classes of a certain compact Lie group. We illustrate this in three examples: polynomials in one variable, where everything is explained in terms of Galois theory by the Chebotarev density theorem; elliptic curves, where the dichotomy of outcomes is predicted by the recently proved Sato-Tate conjecture; and hyperelliptic curves of genus 2, where even the conjectural list of outcomes was only found still more recently.

Kac-Moody algebras (work with Lisa Carbone)

W-graph ideals.

The geometry and topology of Coxeter groups

$q$-Schur Superalgebras and Kazhdan-Lusztig Combinatorics. This is joint work with Hebing Rui.

Plancherel Theorems for Coxeter groups and Hecke algebras: It is elementary that each trace functional on a finite dimensional semisimple complex algebra can be written as a linear combination of the irreducible characters of the algebra. Explicitly computing such a formula is called a Plancherel Theorem. In this talk we will: (1) Expand on what is meant by a Plancherel Theorem (for example, outside of the finite dimensional setting), and explain why we might care about them, (2) Sketch some well understood cases (finite dimensional Hecke algebras and affine Hecke algebras), and (3) Say what we would like to understand outside of these cases.

Bill Casselman will speak on recent work of Paul Gunnells and Mikhail Belolipetsky. Dan Roozemond will speak on Affine Kac-Moody algebras.

Jacobian varieties of hyperelliptic curves are a generalization of elliptic curves that are just as suitable for efficient computations and cryptographic applications. Their endomorphism ring plays a central role in applications such as constructing varieties with a prescribed cardinality over a prescribed finite field.

We will present the first subexponential-time algorithm for computing the endomorphism ring structure of ordinary varieties of dimension one and two over finite fields. It exploits the relationship between subgroups of a variety and the ideal class group of its endomorphism ring, which is known as complex multiplication theory.

For one-dimensional varieties, that is, elliptic curves, this algorithm is very efficient and its complexity can be rigorously proven under just the generalized Riemann hypothesis. In higher dimension, additional heuristics are required, but the algorithm is nevertheless able to perform record endomorphism ring computations.

In this talk we will introduce the methods of Chabauty and the Mordell-Weil Sieve. We will then show how a combination of these, together with a "descent" argument, can be used to fully determine the set of rational points of an algebraic curve (of genus greater than 1).

I will discuss some basics of how one might go about computing the set of rational solutions to an equation of the form y^q = f(x), where f(x) is a polynomial with rational coefficients and q is a prime number.

On this talk, we will talk about some new conjectures on critical values of L-functions twisted by a non-commutative Artin representations. It comes out from computation and may contribute to non-commutative Iwasawa theory.

Geometric invariant theory (GIT) has been used to construct many moduli spaces and birational models of moduli spaces. Predictions by Hassett and Keel suggest that one should get interesting models of $\bar{M}{g}$ (the moduli space of stable curves) by changing the parameters of Gieseker's GIT construction of $\bar{M}{g}$. Ian Morrison and I developed Grobner basis techniques to help us study these new GIT quotients. One trick we use relies heavily on the representation theory of automorphisms of curves. I'll explain how we used various software packages in the original project, and some of the tools I have implemented or would like to implement in Magma.

Is there any structure to the set of algebraic extensions of the field of rational numbers $\mathbb{Q}$? Can we describe the linear representations of its absolute Galois group? These questions lead to class field theory and, ultimately, the Langlands program. They become far simpler if $\mathbb{Q}$ is replaced by a local field such as $\mathbb{Q}_p$. We will give a motivated introduction to the ``local Langlands program'', which is an attempt to describe all the representations of the absolute Galois group via objects that seem to have nothing to do with Galois theory.

Theta-groups were introduced by Vinberg in the 70-s. They are a class of reductive algebraic groups for which there is a well-developed theory dealing with their orbits, allowing classifications of them. In this talk I will describe what theta-groups are, and then concentrate on the semisimple orbits. Vinberg showed that every semisimple orbit has a point in a subspace called Cartan subspace, two points of a Cartan subspace are conjugate iff they are conjugate under a certain complex reflection group, called the little Weyl group, and different orbits of the little Weyl group are separated by invariants. I will describe some computational techniques for computing a Cartan subspace and the little Weyl group, and the results obtained with them, using Magma.

The canonical height is an important tool in the study of the arithmetic of abelian varieties. We will discuss how the canonical height can be computed in practice in the case of Jacobian varieties and why this is an interesting problem.

We will show how a version of finite descent obstruction for curves is related to a problem on the existence of abelian varieties with prescribed Galois representations. The problem for elliptic curves over the rationals can be solved via Serre's conjecture in the affirmative. We will also discuss some possible counterexamples in other situations.

The most interesting invariant of a K3 surfaces is its Picard group. A method for the computation was introduced by van Luijk. In this talk I will present my work on improving and testing this method.

We will take a look on the arithmitic properties of cubic surfaces. The main focus will be on 27 lines and the Galois group action on them. Different descriptions of the moduli space of cubic surfaces are used to construct several Galois groups. Finally we will inspect the Manin conjecture for these surfaces.

The minimal model program (MMP) in Algebraic Geometry is a (almost complete) method for finding in each birational class a good representative. Singularities naturally crop up even if one starts from a smooth variety and computes its minimal model. We'll briefly describe the study of such singularities with respect to the (log) MMP to provide some background / motivations for examining the log canonical threshold (lct), a numerical invariant describing the severity of these singularities.

In Magma, I've been working on a package that will aid in the computation of lct globally on Fano G-varieties X, where G is a finite subgroup of Aut(X). The computation involves examining the splitting of the G-action on the Riemann-Roch space of a (pluri-)anti-canonical divisor to find the invariant parts of the (pluri-)anti-canonical linear system and then resolving the singularities of the worst of these parts to calculate their lct, all of which I'll illustrate with some examples. If there's time at the end we'll look at the correspondences between the global lct on Fano G-varieties and Kähler geometry, quotient singularities and with studying conjugacy classes in higher rank Cremona groups.

We have computed with divisors on curves for a decade. Analogous calculations are possible using curves on surfaces (rather than points on curves) with many new phenomena. Del Pezzo surfaces are the 2-dimensional analogues of conic curves. Their divisor class groups are lattices $\mathbb{Z}^d$, where the bilinear form comes from the intersection of curves on a surface. The basic geometrical theory is available in magma, and I want to explain that and then show how it relates to some arithmetic properties of surfaces. This has plenty of relations to what Martin and Steve have been doing recently, to Mike's sheaf code and to John Cremona's code for conic curves over a function field; for comparison later, Andrew is working on similar theory but with an added finite group action.

We study three-point covers of the projective line whose Galois group is either $PSL_2(\mathbb{F}_q)$ or $PGL_2(\mathbb{F}_q)$. We construct these covers by isolating certain subgroups of hyperbolic triangle groups which we call "congruence" subgroups. These groups include the classical congruence subgroups of $SL_2(\mathbb{Z})$, Hecke triangle groups, and 19 families of Shimura curves associated to arithmetic triangle groups. We determine the field of moduli of the curves associated to these groups and thereby realize the above groups regularly as Galois groups in many cases over explicitly given abelian number fields. This is joint work with Pete L. Clark.

Maximilian Kreuzer died on 26th November after many months fighting against a severe illness. I want to take this opportunity to talk about one of his most important contributions to toric geometry: the classification of the four dimensional reflexive polytopes that he produced with Skarke in 2000.

This classification of 473,800,776 polyhedra provides most famous source of Calabi-Yau threefolds (giving 30,108 distinct pairs of Hodge numbers), and is obviously of considerable importance in string theory. I'll attempt to sketch the methods used by Kreuzer and Skarke to obtain this result, and how the combinatorial data should be interpreted.

Some families of Diophantine equations, such as quadratic forms, have a very useful property: if an equation has solutions in the real numbers and in each p-adic field, then it has a rational solution. Such families of equations are said to satisfy the Hasse principle. In general the Hasse principle does not hold, but many violations are described by the so-called Brauer-Manin obstruction. This obstruction was first defined by Manin and is based on the Brauer group of the variety. I will talk about how to compute the Brauer-Manin obstruction for certain classes of varieties, using many ingredients from algebraic geometry and number theory.

Principally polarized abelian surfaces, of which Jacobians of genus 2 curves are important examples, play an important role in arithmetic geometry. In some sense, they are "the next step" after elliptic curves. It is therefore interesting to understand the possible relations between principally polarized abelian surfaces, which brings us to the study of isogenies. The simplest case of these (analogous to 2-isogenies on elliptic curves) is that of Richelot isogenies. These are well-known classically over the complex numbers. I will discuss some of the complications that arise when one considers more general base fields. Applications of this more general description of Richelot isogenies include a complete description of genus 2 curves admitting a degree 4 map to an elliptic curve.

The matrix group recognition project has reached the stage at which one can use the composition tree as a basis for further calculations. In particular, it is desirable to adapt the ``trivial Fitting'' paradigm, which is the basis for many successful permutation group algorithms. For this, it is necessary to obtain radical generators and a representation for the radical factor, to split the radical in elementary abelian factors, and to adapt the existing permutation group algorithms in aspects such as element tests in subgroups. Using the example of conjugacy classes of elements I will show how this can be done.

The Ore conjecture, posed in 1951, states that every element of every finite non-abelian simple group is a commutator. Despite considerable effort, it remained open for various infinite families of simple groups. Recently, in a joint project with Liebeck, Shalev and Tiep, we developed new strategies, combining character theoretic methods with other ingredients, and used them to establish the conjecture.

It is in general very difficult to compute ranks of elliptic curves over number fields, even if equipped with any conjectures that are available. On the other hand, the parity of the rank is (conjecturally) very easy to determine --- it is given as a sum of purely local terms, which have a reasonably simple classification. Since "odd rank" implies "non-zero rank" implies "the curve has infinitely many points", this leads to a number of (conjectural!) arithmetic phenomena.

Computing the ideal class group and the regulator of a number field is of both number theoretic and cryptographic interest. There exist a lot of similarities between algorithms for number fields and for Jacobians of algebraic curves, even if finding reductions between these problems is still an open problem.

After an introduction on number fields and the features of the ideal class group, we will present methods based on the quadratic sieve to enhance the subexponential algorithms for class group and regulator computation of quadratic number fields. We will also see how improvements to linear algebra algorithms can lead to significant speed-ups, and provide comparisons between our algorithms and those available in Magma.

This talk will summarize some distinctive features of 4-descent and of 3-descent. Also it will begin to discuss the problem of finding nice'' models of the covering curves, via linear change of variables (in fact this breaks into two algorithmic problems, referred to asminimisation'' and ``reduction'').

Continuing from the previous talk, I will discuss obstructions to descent, and the associated conjectures. I will also discuss the problem of finding models of the covering curves with minimal degree (as hyperelliptic curves in the case of 2-descent), and the obstruction to this. Then I will describe 4-descent and 3-descent.

I am going to talk about [arXiv:1001.2792 a recent paper] with Alicia Dickenstein, which extends work of Sandra Di Rocco, Ragni Piene and Alicia. We give an alternative way how to check whether a projective toric manifold associated to a smooth lattice polytope has dual defect. This involves a combinatorial invariant, called the codegree, which is of independent interest in the theory of lattice polytopes.

If time permits, I will explain how our result fits in nicely with a general conjecture of Beltrametti and Sommese in the adjunction theory of polarized manifolds.

I'll begin a short series of talks outlining the theory of the descent algorithms implemented in Magma, whose purpose is to determine the group of rational points on a given elliptic curve.

(For elliptic curves over $\mathbb{Q}$, we have 2-descent, 4-descent and now full-fledged 8-descent; alongside this, we have 3-descent and now 6- and 12-descent. Complementary to 4- and 8-descent, we have the Cassels-Tate pairing for 2- and 4-coverings.)

The first talk will describe 2-descent from an elementary point of view, so it will be accessible and will lay the foundations for the remaining talks.

Lie algebras are often used to study the algebraic groups from which they originate, but they are interesting objects in their own right as well. Many simple Lie algebras have a particular basis with special properties, invented by Chevalley. It is an extremely useful tool to identify and study Lie algebras.

Algorithms exist, and have been implemented, to compute the Chevalley basis of a Lie algebra that is represented in some way (for example as a structure constant algebra). Unfortunately, these algorithms break down in some special cases and in particular over fields of characteristic 2 and 3.

We show what problems arise in these cases and how they can be solved, and apply the newly found algorithms to the study of Lie algebras generated by extremal elements.

Golyshev conjectured that for any smooth Fano polytope $P$ with $\dim{P}łe 5$ the roots of the Ehrhart polynomial have real part equal to $-1/2$ (the ``canonical line hypothesis''). I shall sketch a proof of this conjecture. This is joint work with Gábor Hegedüs (see arXiv:1004.3817v1).

The aim of this talk is to give a brief introduction to convex bodies: polytopes, polyhedra, and cones. Starting with the most elementary definitions, and motivated in part by constructions from toric geometry, I hope to address: * The dual definitions of a polytope, and how this naturally gives rise to polyhedra; * The concept of finite part and tail cone; * The basic combinatorial properties of polytopes; * Computing the basis of a cone; * Lattice point counting.

I will explain the recent improvements of the toric geometry package. The improvents include integrating toric varieties with the other scheme structures, which allow to extend the possibilities of existing machinery, for instance curves. We also implemented new algorithms and improved existing ones.

I will survey Gentry's acclaimed fully homomorphic encryption scheme. A homomorphic encryption is a form of encryption performing some specific algebraic operation on ciphertexts implicitly performs some specific algebraic operation on the corresponding ciphertexts. Gentry's scheme allows one to homomorphically apply any algebraic function on the plaintexts. This had been an open for more than 30 years and was considered the `holy grail' of cryptography. Gentry's scheme relies on lattices corresponding to ideals in number fields, and its security relies (in part) on solving a variant of the closest vector problem for these lattices.

I will discuss a new algorithm for computing the zeta function of a projective hypersurface over a finite field of characteristic $p$ whose running time dependence on $p$ is roughly $p^{1/2}$.

A Brauer--Severi variety of dimension $n-1$ is a twist of projective space $\mathbb{P}^{n-1}$. The Hasse principle tells us how to decide whether a Brauer--Severi variety defined over a number field has rational points, but not how to find a point. I will discuss how some of the methods for solving conics (case $n=2$) generalise to other small values of $n$ (at least if we are working over the rationals).

The simplest kind of algebraic curve that is not utterly trivial is a conic curve $X^2 - AY^2 - BZ^2 = 0$. Here $A$ and $B$ lie in $\mathbb{Q}$ or a number field, and we are interested in finding a solution $(X:Y:Z)$ over that field. The Hasse principle holds, which means it's easy to decide whether a solution exists; also, from a single solution it's easy to find all solutions i.e. a parametrization.

The algorithmic problem of finding a single solution has received only belated attention: over $\mathbb{Q}$, the best known algorithm was given by Denis Simon in 2005; over number fields, the usual method is to solve the norm equation $N(X + \sqrt{A}Y) = B$, thus reducing the problem to a (sub-exponentially!) harder one.

In this talk, I'll describe techniques used in {{HasRationalPoint}} for conics over number fields, which I've developed gradually over the last few years.

In his 1997 thesis K. Wildanger developed an efficient method for computing such points over the rational integers. We improve and generalize his ideas. Replacing his methods from the geometry of numbers by a class field theoretic approach based on Hasse we expect to get a much more powerful algorithm. (This is a report on work in progress.)

The potential of solving norm equations is crucial for a variety of applications of algebraic number theory, especially in cryptography. In our talk we describe general effective methods for that task in global function fields which have been developed recently.

Bogomolov and Tschinkel showed that many nonsingular hypersurfaces of low degree and low dimension are densely covered by rational points (after allowing a finite extension of the base field). One of their methods involved building elliptic fibrations with good properties. I will sketch the ideas behind this and then show how to adapt methods of Cheltsov and Park to show the same in other concrete contexts. To some extent, this is about taking an ideal and working out how to push some of its variables into the coefficient field so that the rest resemble the ideal of an elliptic curve; sometimes you have to add new variables in a careful way to make it work, which I will illustrate with examples.

Joint work with Andrew Sutherland (MIT).

We make a practical comparison of several algorithms for computing the zeta functions of curves of genus up to 3 over finite fields, and computing L-series of such curves over number fields. These include optimized enumeration of points, generic group algorithms improving upon the Shanks baby step-giant step approach, and $p$-adic cohomology (work of David Harvey). If time permits, I may also touch upon some observations regarding exceptional distributions of Frobenius eigenvalues (i.e., higher-genus analogues of the CM exception to the Sato--Tate law).

I will explain some of the kinds of calculations we can expect to do for elliptic surfaces, and show, following Bogomolov and Tschinkel, how they relate to the potential density of rational points. I will sketch some of the current array of problems on threefolds.

In this talk I will survey current facilities for Lie theory computation in Magma. I will discuss both practical implementations and algorithmic aspects. This talk will cover: * Root systems * Coxeter groups and reflection groups * Lie algebras * Classical groups * Groups of Lie type (reductive algebraic groups) * Highest weight representations

I will also discuss possible future directions, including implementation of more general algebraic groups.

I'll explain what the online [http://grdb.lboro.ac.uk/ Graded Ring Database] is (and what it is not), sketch how new data can be added, and try to convince you that you might be interested in using it. In particular, I'll explain how Magma can extract data from the database.

This talk will contain no mathematics; the aim is to make people aware of a tool they might find useful. I hope to keep it brief.

An Artin group is a group defined by a presentation with a finite generating set, with all relations being of the form $xyxyłdots = yxyxłdots$ (both alternating words having the same length); at most one relation exists for each pair of distinct generators $x,y$. The Artin group is said to be of "large type" if each relation involves words of length at least 3.

It is conjectured that all Artin groups are biautomatic. This has been proved by Charney for Artin groups of finite type (corresponding Coxeter group finite), by Peiffer for those of extra large type (relations involve words of length at least 4), and by Brady and McCammond for Artin groups of large type with at most three generators. For general Artin groups the conjecture remains open.

In this talk, I shall briefly discuss my recent proof with Sarah Rees that all Artin groups of large type are (shortlex) automatic, and that their geodesics form a regular set. The proof is purely combinatorial. We hope to be able to address the question of their biautomaticity in the near future.

John Bray, Derek Holt and Colva Roney-Dougal are writing a book of which the aim is to classify maximal subgroups of all almost simple extensions of the classical groups $G$ over finite fields in dimension up to 12. (The geometric type subgroups in dimensions greater that 12 have been classified in an earlier book by Kleidman and Liebeck.)

In this talk, we shall discuss a few specific aspects of this project. We concentrate on almost simple subgroups (i.e. non-geometric type) in which the natural characteristic of the subgroup $H$ is unequal to the characteristic in the classical group G. The simple candidates for $Socle(H)$ have been listed in a paper of Hiss and Malle. But it becomes technically complicated when we try to ascertain which almost simple extensions of $H$ are subgroups of which almost simple extensions of $G$.

Techniques used involve use of representations of $H$ over number fields. Some nontrivial problems in number theory arise in a few cases.

Representations of finite groups over number fields are well understood in theory, but leave a large number of practical questions open. In my talk I will adress a few of them. In particular, for absolutely irreducible representations I will explain how * the number field can be chosen that affords the representation * to change the field * to decide if the representation is equivalent to an integral representation * find all classes of non-equivalent integral representation, thus giving a constructive version of the Jordan--Zassenhaus theorem

Projective Indecomposable modules for finite groups have a number of applications, such as computing higher dimensional cohomology groups by dimension shifting.

We consider possible methods for computing them. The most promising approach seems to be to find so-called peakwords for the irreducible modules in the group algebra of the group, and to use them to construct the projective indecomposables as summands of suitable permutation modules.

The [http://www.mpir.org/ MPIR project] is a library for multiple precision integer and rational arithmetic, based on the GNU MP library. Work on MPIR began about two years ago and the library has just had its fifth major release. Since that time multiple precision arithmetic has roughly doubled in speed.

I shall describe some of the recent algorithmic and other improvements which have been made in the area, as implemented in the MPIR library.

I will describe a practical Meataxe algorithm for decomposing A-modules over the rational field, and how this is applied in a system for the automatic construction of irreducible rational representations of a given finite group.

This talk will describe some recent advances in software speed for various computations in fields of characteristic 2. This talk will explain, for example, why the latest speed records for elliptic-curve cryptography use fields of characteristic 2, and why normal bases are being used instead of polynomial bases in software to attack the "infeasible" ECC2K-130 challenge.

In 1939, Coxeter first studied the family of groups defined by the presentations: $$(l,m,n;q) = < r, s | r^l, s^m, (rs)^n, [r,s]^q >.$$ Until recently, the finiteness of only 6 of these groups remained undecided: $$(2, 3, 13; 4), (3, 4, 9; 2), (3, 4, 11; 2), (3, 4, 13; 2), (3, 5, 6; 2)\text{ and }(3, 5, 7; 2).$$ We discuss a recent computational proof, carried out largely in Magma, by George Havas and myself that $(2, 3, 13; 4)$ is finite, and that $(3, 4, 13; 2)$ and $(3, 5, 7; 2)$ are infinite.

Lattice reduction is a fundamental tool in diverse fields of computational mathematics and computer science, like cryptography and algorithmic number theory... The LLL algorithm allows one to reduce a basis of a given lattice into a 'good' basis in time polynomial in both the dimension and the size of the entries. However, the size of the integers that arise during the execution of the algorithm make it unusable in practice for large inputs. We describe here a new proven LLL-type algorithm, H-LLL, that relies on Householder transformations to compute the QR decomposition of the basis. I will present the advantages and drawbacks of this over already existing methods.

Let $C$ be a projective smooth curve of genus $g$ over a field $k$. The Picard group of $C$ over $k$, consisting of $k$-rational divisors up to linear equivalence, is analogous to the ideal class group of a number field. In this talk, I will describe "geometric" algorithms for the group arithmetic in $Pic^0$ that boil down to linear algebra in vector spaces of dimension $O(g łog g)$. Using fast linear algebra, this yields a complexity of $O(g^{2.376})$ field operations in $k$ per group operation in the Picard group. In comparison, existing "arithmetic" algorithms based on the analogy with ideal class groups have a complexity of $O(g^4)$ for general curves of genus $g$, but attain $O(g^2)$ if one restricts to special classes of curves.

Dirichlet originally used Dirichlet characters to show that every admissible arithmetic progression in the integers has infinitely many primes. These were then generalised by Hecke to number fields, where an analogous result is the Chebatorev density theorem concerning splitting behaviour of ideals. With regard to class field theory, one can additionally put prescribe a norm-component, which leads to the so-called Hecke Grossencharacters, which are still multiplicative, though no longer of finite order. These turn out to be related to arithmetic (particularly complex multiplication) in various guises. We give a leisurely introduction to this theory, explaining what is now implemented in Magma.

Many methods for solving diophantine questions rely on knowing the group of rational points on an abelian variety. In only very few cases this is know to be a solvable problem at all. We do not even have an algorithm that is guaranteed to work for all elliptic curves (one dimensional abelian varieties).

We do have quite a collection of methods for elliptic curves that work quite well in many practical cases. We can also handle Jacobians of hyperelliptic curves in a fair number of practical settings. This motivated us to try Jacobians of non-hyperelliptic curves. The simplest examples occur as genus 3, smooth plane quartic curves.

We have mixed success. There are several theoretical and computational obstacles, although most theoretical obstructions can be replaced with much worse computation ones.

Ingredients we need: * Gröbner basis and resultant computations (these are not a bottleneck) * Rings of integers of degree 28 algebras with very large discriminants * S-unit groups of number fields up to degree 28 * Identification of galois groups and decomposition groups in $Sp(6,GF(2))$ * Cohomology of several $Sp(6,GF(2))$-modules over $GF(2)$ * Computations in $p$-adic extensions

In other words, we are using a very large part of magma and in many cases (judging from the bugs we ran into), drive it a little beyond its comfort range.

This will be more a progress report than a polished presentation and I will try to emphasise the interaction with magma we experienced.

This is joint work with Victor Flynn, Bjorn Poonen and Michael Stoll.

It would probably have been a big surprise for Hilbert to see that one of his famous problems was resolved with a negative answer:

As we know by the work of Davis, Putnam, Robinson and Matyasevitch, there is no algorithm that takes as input a multivariate polynomial $f(x_1,łdots,x_r)$ over the integers and gives as output whether or not the the equation $$f(x_1,łdots,x_r) = 0$$ has any integer solutions.

This result establishes that number theory, and in particular the study of diophantine equations, is generally hard.

If instead of integer points on hypersurfaces, we consider rational points on curves, the picture changes dramatically. In the last six years, a suprisingly simple method, now commonly referred to as Mordell--Weil sieving, has been developed. A heuristic argument by Bjorn Poonen indicates that this method should always be able to decide if a projective curve has any rational points.

I will discuss the method and give some experimental evidence of its efficacy.

We show the existence of an extremal 80-dimensional lattice that is even, unimodular, and whose automorphism group contains a copy of $SL_2(F_79)$. This lattice was constructed a few decades ago by Schulze-Pillot, and was given as a candidate for extremality (minimal norm 8). Although other 80-dimensional extremal lattices were known, the provenance for this one was yet unknown. Our method of proof involved the positivity of the Thets-series and finding over 7.5 trillion vectors of norm 10. This last step took about 2 cpu-months (4 days on a cluster), and made heavy use of new pruning methods for vector enumeration due to D. Stehlé.

I shall describe a family of 26-dimensional `algebras' whose automorphism groups are the large Ree groups ${}^2F_4(2^{2n+1})$. These algebras can be defined without reference to the usual underlying Lie theory, and can be used to give an elementary definition of the generalised octagon, and thereby compute the group orders and prove simplicity (for $n>0$).

We use explicit methods for computing in the cohomology of a Shimura curve to compute spaces of Hilbert modular forms. As a consequence, we construct nonsolvable finite extensions of the rational numbers ramified only at 3 and 5, respectively. This is joint work with Matthew Greenberg and Lassina Dembele.

The eigenvalues of Hecke operators give rise to arithmetically interesting data. This talk will begin with a brief overview of one approach to computing Hecke operators on classical modular forms, but phrased in terms of Voronoi polyhedra and sharblies. I will describe some of the complications that arise when the change is made from the rational numbers to a number field. Then I will specialize to imaginary quadratic fields, giving a brief demonstration in Magma.

The Leech lattice is a remarkable object with many applications in group theory, number theory, coding theory and elsewhere. It lives in 24-dimensional space, and its many constructions are all rather technical. I outline a new approach which uses octonions to avoid many of the difficulties.

Let $f$ be a newform for $\Gamma_1(N)$. There is attached to $f$ a family of Galois representations with $\ell$-adic coefficients. Calculating these Galois representations seems intractable, but if we only ask for the local Galois representations at a particular prime $p\neq \ell$, then we are led into some rather interesting territory, especially if $p^2$ divides $N$. These local representations are parametrized by certain infinite-dimensional representations of $GL_2(Q_p)$, according to the Local Langlands Correspondence. We show how to use Magma to determine these "local components". The computation involves working with modular symbols as well as with representations of finite matrix groups.

In this talk we make explicit the Galois action on the CM moduli for genus $2$ Jacobians. By using recently computed $(3,3)$-isogeny relations, we demonstrate how this can be used to improve the CRT algorithm for computing Igusa class polynomials, providing some examples.

In my talk I will present the idea of an algorithm for calculating the isomorphisms of function fields by looking on some induced maps on the the set of places and on some Riemann Roch spaces. Then I will try to explain how one can generalize this algorithm to one for calculating inclusions.

In a [arXiv:0810.2207v1 joint work] with Max Kreuzer and Benjamin Nill, techniques for classifying all toric log Del Pezzo surfaces up to some arbitrary index were described. Continuing the recent theme of toric talks, I will outline the methods involved and explain why polytopes are so important in toric classifications.

We consider several algorithms for testing irreducibility of sparse polynomials over finite fields of small characteristic. The algorithms that are fastest in theory turn out not to be best in practice. A hybrid algorithm that combines the classical approach with modular composition is suggested. As an application, we describe a search for irreducible trinomials (over $GF(2)$) whose degree is a large Mersenne exponent.

First, a brief summary of the Quantum Public Key Cryptosystem (QPKC) and its concrete scheme proposed in 2000 will be given. The scheme uses quantum computers only to generate public keys from private keys, but there are several practical problems even in generating private keys. To solve them, we propose a refined algorithm for implementing on classical computers. We propose an idea to increase the density or the pseudo-density of generated knapsack problems. We discuss how to generate public keys without quantum computers. We explain why we implement over imaginary quadratic fields and what are the practical difficulties.

Part 2: Homogeneous coordinate rings of toric varieties.

It turns out that a toric variety has a naturally-associated ring of functions -- it's just a polynomial ring, sometimes called the Cox ring, but it has a grading by a finitely-generated abelian group (i.e. a few $\mathbb{Z}$-gradings and then perhaps a little cyclic group grading too). We can use this ring to define varieties inside toric varieties (just as in the usual case of varieties in affine or projective space), to define maps, and anything else you'd expect.

In this talk we will review some toric geometry and how different models of elliptic curves proposed in the literature fit in this framework. Then we describe an algorithm to find good models admitting efficient arithmetic.

Part 1: cones and fans.

Affine 2-space $k^2$ (over a field $k$) has the polynomial ring $k[x,y]$ as its ring of (polynomial) functions. If $\sigma$ in $\mathbb{R}^2$ is the first quadrant and $M = \mathbb{Z}^2$ is the integral lattice in $\mathbb{R}^2$, then I can regard the set of all monomials $x^i y^j$ (and their multiplicative structure) as $\sigma \cap M$. Thus $k[x,y] = k[ \sigma \cap M ]$, and so I think of $\sigma$ (sitting in $M øtimes \mathbb{Q}$) as determining $k^2$.

Toric geometry makes a lot out of this by allowing other choices of cones than $\sigma$, allowing collections of cones, and considering maps between cones. Many features of geometry can be interpreted as questions about cones in lattices. I'll go through the famous first examples.

I will describe how L-functions can be attached to various number theoretic objects, and comment on the motivation for wanting to compute with these L-functions, in particular what types of conjectures they are supposed to obey. Then I will give some specific examples from work that has derived from an NSF Focused Research Group grant, particularly some experiments with rank 4 quadratic twists, and some appearances of eta-quotients with Waldspurger lifts of modular forms. With the latter, in some examples it is possible to write the $q$-series as a product of two weighted theta series, and then the use of FFT convolution can be used to get a large initial segment (up to $10^{10}$ in some cases).

We study complexity estimates for computing $n\times n$ matrix determinants and adjoints over an abstract ring R. Using a block Krylov approach, together with Strassen's avoidance of divisions, Kaltofen (1992) and Kaltofen & Villard (2004) propose an algorithm for computing the determinant in $O(n^{2.7})$ additions, subtractions, and multiplications. This is currently the best known complexity estimate for the problem. We will give an insight into the method, especially into its baby steps/giant steps strategy.

By the results of Baur and Strassen (1983), the determinant algorithm, actually a straight-line program, leads to an algorithm with the same complexity for computing the adjoint of a matrix. However, the latter adjoint algorithm is obtained by the reverse mode of automatic differentiation, hence somehow is not "explicit". We present an alternative (still closely related) algorithm for the adjoint that can be implemented directly, by which we mean without resort to an automatic transformation. The algorithm is deduced by applying program differentiation techniques "by hand" to the determinant program, and is completely described.

The talk will be about algorithms for some problems concerning ideals classes in quaternion algebras (over number fields). I'll summarise the theory describing ideals and ideal classes, and discuss the main ideas used in the algorithms.

For elliptic curve $E$ over a number field $K$, there are various 'modulo 2' versions of the Birch--Swinnerton-Dyer Conjecture, each sometimes called the Parity Conjecture. One sserts that the algebraic rank of $E/K$ has the same parity as the analytic rank (as given by the root number). Another one is the same statement for the $p$-infinity Selmer rank for some prime $p$. I will explain the proof of the second conjecture for all elliptic curves $E/Q$ and all $p$ (this completes earlier work by Greenberg, Guo, Monsky, Nekovar and Kim), and a weaker result over general number fields.

This is joint work with Vladimir Dokchitser.

We present methods for the resolution of decomposable form equations over global fields. In general, those equations are reduced to unit equations. Algorithms for solving the latter differ substantially in the number and function field case. Thue and norm form equations will be discussed in greater detail. Also, the fastest known method for computing all integral points on Mordell curves $y^2=x^3+k$ will be presented.

We present methods for the resolution of decomposable form equations over global fields. In general, those equations are reduced to unit equations. Algorithms for solving the latter differ substantially in the number and function field case. Thue and norm form equations will be discussed in greater detail. Also, the fastest known method for computing all integral points on Mordell curves $y^2=x^3+k$ will be presented.

Let $k$ be a field and $G$ a finite group, acting on the polynomial ring $$A:=k[x_1,łdots,x_d]$$ by graded $k$-algebra automorphisms. The ring of invariants $A^G:={fın A\ |\ g(f)=f}$ is the main object of study in Invariant Theory. The theory is very well developed in the classical case'', where the characteristic of $k$ is zero, but far less so in the case of positive characteristic, in particular themodular case'', where the characteristic divides the group order $|G|$.

In that case there are open questions about the constructive complexity of $A^G$, measured by degree bounds for generators, and about the structural complexity, measured by the depth (=length of maximal regular sequence, or ``cohomological co-dimension'') of $A^G$ as a module over a homogeneous system of parameters.

In my talk I will, after a brief introduction, report on some recent results dealing with both types of questions.

We present methods for the resolution of decomposable form equations over global fields. In general, those equations are reduced to unit equations. Algorithms for solving the latter differ substantially in the number and function field case. Thue and norm form equations will be discussed in greater detail. Also, the fastest known method for computing all integral points on Mordell curves $y^2=x^3+k$ will be presented.

Let $k$ be a field and $G$ a finite group, acting on the polynomial ring $A:=k[x_1,łdots,x_d]$ by graded $k$-algebra automorphisms. The ring of invariants $A^G:={fın A\ |\ g(f)=f}$ is the main object of study in Invariant Theory. The theory is very well developed in the classical case'', where the characteristic of $k$ is zero, but far less so in the case of positive characteristic, in particular themodular case'', where the characteristic divides the group order $|G|$.

In that case there are open questions about the constructive complexity of $A^G$, measured by degree bounds for generators, and about the structural complexity, measured by the depth (=length of maximal regular sequence, or ``cohomological co-dimension'') of $A^G$ as a module over a homogeneous system of parameters.

In my talk I will, after a brief introduction, report on some recent results dealing with both types of questions.

A hyperelliptic function field is a field of the form $k(x,y)$ where $k$ is a finite field of odd characteristic and $y^2 = D(x)$ with $D(x)$ a square-free polynomial with coefficients in $k$. If $D$ has even degree, or if $D$ has odd degree and the leading coefficient of $D$ is a non-square in $k$, then the Jacobian of the hyperelliptic curve $y^2 = D(x)$ is essentially isomorphic to the ideal class group of the ring $k[x,y]$. This is the finite Abelian group of fractional ideals of $k[x,y]$ modulo principal fractional ideals. Although generically, the 3-Sylow subgroup of this ideal class group is small (and frequently trivial), it is possible to generate hyperelliptic function fields -- even infinite families of such fields -- whose 3-rank is unusually large. This talk presents several methods for explictly constructing hyperelliptic function fields of high 3-rank, and more generally, high $l$-rank for any prime $l$ coprime to the characteristic of $k$. Some of these techniques are adapted from constructions originally proposed for quadratic number fields by Shanks, Craig, and Diaz y Diaz, while others are specific to the function field setting. In particular, we explore how extending the field of constants $k$ can lead to an increase in the 3-rank of the hyperelliptic function field.

This is joint work with Mark Bauer and Mike Jacobson, both of the University of Calgary, and Yoonjin Lee of Ewha Women's University in Seoul, South Korea.

Polynomial approximations are often used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite - and sometimes small - number of bits: this is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-$i$ coefficient has at most $m_i$ fractional bits: in other words, it is a rational number with denominator $2^{m_i}$. We provide one general method, based on linear programming, for finding the best polynomial approximation under this constraint and another method, fast and efficient, based on lattice reduction, that gives a very good approximant under this constraint. Moreover, our methods also apply if some other constraints (such as requiring some coefficients to be equal to some predefined constants, or minimizing relative error instead of absolute error) are required.

This is a joint work with Sylvain Chevillard, Jean-Michel Muller and Serge Torres.

The theme will be on lattice reduction, including: * Lattice point enumeration; * Strong reductions; * Enumeration and strong reductions together; * Hard lattice functions; * Applications of strong reductions in cryptanalysis and computer arithmetic; * New and further developments.

The theme will be on lattice reduction, including: * Lattice point enumeration; * Strong reductions; * Enumeration and strong reductions together; * Hard lattice functions; * Applications of strong reductions in cryptanalysis and computer arithmetic; * New and further developments.

I will report on old and new techniques to construct characters and representations of finite groups.

Since satisfactory algortihms are available for complex characters and for representations over finite fields, I will focus on representations over characteristic zero fields and will touch upon questions concerning Schur indices, central simple algebras and their minimal splitting fields.

Computation of subgroup structures of groups leads to understanding them better and to being able to answer questions about them and the geometric objects they act on.

In this talk, we will focus on the computation of the whole subgroup structure of finite (simple) groups. We will briefly recall what is the subgroup lattice of a group and explain how Magma does to compute it. We will then give some last minute results on the sporadic simple groups and some applications of these results.

The so-called pseudosquares can be employed in very powerful machinery for the primality testing of integers N. In fact, assuming reasonable heuristics (which have been confirmed for numbers to 280) they can be used to provide a deterministic primality test in time $O(łog N)^3+o(1)$, which some believe to be best possible. In the 1980s D.H. Lehmer posed a question tantamount to whether this could be extended to pseudo $r$-th powers. Very recently this was accomplished for $r =3$, which naturally leads to the question of whether anything can be achieved for $r > 3$. In this paper we show how these earlier results can be extended to all prime values of $r$.

Group cohomology and its computation renders a computationally efficient model to work with techniques defined for more generic settings in homological algebra. Thus, the basic calculational schemes already incorporated in Magma for the computation of group cohomology form a good illustration to a more generic workflow for computation of cohomologies in other modular categories - Lie algebras, Affine algebras, etc.

We shall discuss the basics of computing cohomology rings, and look into current research on computation of homotopy invariants applicable to these rings: most specifically, we shall look at computation of A-infinity products in group and basic algebra cohomology.

Hilbert modular forms are natural generalization of classical modular forms to totally real number fields. In this talk, I will introduce them briefly. Then, I will explain how one can compute them via the theory of Brandt modules. I will illustrate my presentation with several computational results that have been obtained during my visit here in Sydney.

In algebraic geometry, theoretical arguments are often based on the existence of smooth models. In practice, smooth models may be computed using the constructive resolution algorithms of Villamayor or Bierstone-Milman. But any algorithm relying on a resolution then suffers from the high computational complexity of those general algorithms.

In this talk we introduce formal desingularizations as a weak version of resolutions. We also show how they can be computed using the method of Jung--Abhyankar, a specialized resolution procedure for surfaces. As an application, and an indication of usefulness, we demonstrate how to compute the graded module associated to the direct image of the canonical sheaf.

We present the Double-Base Number system (DBNS) and its applications to cryptography, mainly to speed-up scalar multiplications on elliptic curves.

After a brief introduction, we focus on 2 practical contributions:

The first scalar multiplication algorithm having sublinear complexity. This method relies on a generalisation of the DBNS in the context of Koblitz curves

The fastest scalar multiplication algorithm for generic curves when some precomputations are available. This work relies on the so-called extended DBNS which is also a natural generalisation of the DBNS.

Classical elimination theory deals mainly with the question when partial solutions can be extended to complete solutions for a polynomial system. We ask whether it is possible to predict the exact number solutions of a system without actually solving it. In this talk, we present some a relationship between certain Grobner bases and the fibre structures of the solution variety for a polynomial system (that defines a $0$-dimensional radical ideal). We show that from a Grobner basis one can easily read out information about the numbers of extensions of partial solutions, and one can decompose the system into smaller systems that are easier to solve.

Joint work with Virginia M. Rodrigues (PUCRS, Brazil) and Jeffrey Stroomer (Xilinx, Inc.).

The question of the maximum number of moves needed to solve any state of Rubik's cube became a challenge problem for computer science almost since the invention of Rubik's cube in the late 1970s. In joint work with Daniel Kunkle, we recently showed that 26 moves suffice, and we hope soon to demonstrate that 25 moves suffice. An upper bound of 29 was found by Reid in 1995. This bound was reduced to 27 in 2006 by Radu. The best upper bound is suspected to be 20. (A move is a quarter- or a half-twist.)

The basis for our new approach is two-fold: (1) We developed a new group-theoretic algorithm for fast simulation of moves; and (2) We use 7 terabyes of distributed parallel disk for intermediate storage of a data structure related to hash tables, but more suitable for disk streaming access. The group-theoretic algorithm allows us to multipy a symmetrized coset (large classes of states closed under symmetries) by a generator at a rate of more than 10 million moves per second.

The first part of the algorithm (a variation of breadth-first search) is described. This first part already demonstrates that 27 moves suffice. A second part uses the data from the first part to eliminate potentially long solutions and further reduce the upper bound. The second part of the algorithm has already shown that 26 moves suffice, and further computation should further reduce the bound.

I will discuss new techniques for computing with matrix algebras and their modules over arbitrary fields. The key is a deterministic algorithm to construct a non-nilpotent element in any weakly-closed subset of a non-nilpotent matrix algebra. There are immediate applications of this construction to the problem of testing for isomorphism between two modules, and to obtaining certain decompositions of a module. The methods are quite elementary, requiring almost no structural knowledge of the algebra. Thus the hope is that the resulting algorithms are practicable for a broad range of fields, and I am particularly keen to discuss their practical potential during my visit to Sydney. (This is joint work with Gene Luks at the University of Oregon.)

Marsaglia recently introduced a class of ``xorshift'' random number generators (RNGs) with periods $2^n - 1$ for $n = 32, 64$, etc. We describe a generalisation of Marsaglia's xorshift generators in order to obtain fast and high-quality RNGs with extremely long periods.

RNGs based on primitive trinomials may be unsatisfactory because a trinomial has very small weight (number of nonzero terms). In contrast, our generators can be chosen so that their minimal polynomials have large weight. A search using Magma has found good generators for $n$ a power of two up to 4096. These have been implemented in a free software package xorgens. Aspects of the search using Magma, and a connection with Fermat numbers, will be mentioned.

We present some theoretic and heuristic estimates for the number of elliptic curves with low embedding which is essential for their applicability in pairing based cryptography. We also give estimates for the number of fields over which such curves may exist. The main ideas behind the proofs will be explained as well. Finally, we give a heuristic analysis of the so-called MNT algorithm and show that it produces a rather "thin" sequence of curves.

Let $X$ be a variety defined by a set of polynomial equations in several variables over a finite field $F_q$ with $q$ elements. In many applications, one is interested in the number of solutions of these equations over finite extensions $F_{q^r}$ of $F_q$. One can package these integers together into a generating series in a suitable way to obtain the zeta function of $X$, which possesses a marvelous structure and is a fundamental object in algebraic geometry.

In the first part of this talk, intended for a general audience, we will introduce the zeta function from scratch, provide several examples, and discuss its properties and applications. In the second part, we will discuss a new result on the computation of zeta functions using Dwork cohomology, and conclude with several interesting combinatorial and geometric implementational issues.

I'll discuss several topics in number theory where computing modular forms yields interesting information.

Some years ago Wilhelm Plesken mentioned to Arjeh Cohen that if $G$ is a group, the elements $g - g^{-1}$ span a Lie subalgebra of the group algebra of $G$. In this talk I shall describe the structure of this algebra when $G$ is a finite group and the group algebra is over the complex numbers. In particular, I will determine for which groups the construction produces a (semi)simple Lie algebra.

This will be a general talk and little knowledge of the theory of Lie algebras is required beyond the definition of a Lie algebra itself and the definitions of simple and semisimple Lie algebras.

I will reporton recent work on the determination of $p$-groups and associated nilpotent Lie rings, focusing on those of order dividing $p^7$ for arbitrary primes $p$.

In particular I will review the basic algorithm used and outline the use of the Baker--Campbell--Hausdorff formula to relate presentations for the ring and $p$-group.

Connected linear algebraic groups in characteristic zero are completely determined by their Lie algebras. In this talk I will discuss algorithms to make this correspondence effective. In particular I will talk about how to decide whether a given linear Lie algebra corresponds to an algebraic group, and on how to find the group if it does.

Whereas permutation groups can be analysed by computer through their subgroup structure, in the case of matrix groups defined over finite fields we have to use the normal subgroup structure. This makes the basic machinery for computing with matrix groups far more subtle than the corresponding machinery for permutation groups, with particular emphasis on simple groups. I shall give an outline of the approach used, aimed at the non-specialist.

I will describe an algorithm that solves the constructive recognition problem for the Big Ree groups. Different areas of computational algebra are used in the algorithm, and the implementation makes heavy use of Magma's machinery in these areas. The algorithm forms a part of the matrix group recognition project.

I will discuss the classification of transitive groups of degree 32. There are 2801324 up to conjugacy in Sym(32).

Given a finite group $G$, known to be isomorphic to a simple group $H$ (we regard $H$ is the {\em standard copy} of the simple group), we consider the algorithmic problem of writing down an explicit isomorphism from $H$ to $G$. This problem, known as the {\em constructive recognition problem}, has important applications to several other algorithmic problems of current interest. Among these are the problem of constructing a composition series for a finite matrix group, and constructing the maximal subgroups of a permutation group.

In this talk I will give a more precise definition of a constructive recognition algorithm and indicate how such algorithms are applied to the problems mentioned above. I will also outline some of the algorithmic difficulties one is confronted with when devising such algorithms.

After recalling braid groups and the Garside normal form, I will explain the Diffie-Hellman like key exchange introduced by Ko et al. and some related cryptographic protocols, which are all based on the conjugacy search problem (CSP) in braid groups.

In the second part of the talk I will present recent solutions to the CSP and we will see that they yield effective attacks on these cryptographic protocols in their present form.

Time permitting, I will finally discuss some possible modifications to the cryptographic protocols, such as appropriate choice of keys or replacing the CSP by the decomposition problem.

Lattice point enumeration is the basis of the best known algorithm to solve exactly the shortest vector problem. This is also the time-consuming part of Schnorr's block-based lattice reductions, that are very famous in the cryptography community. This enumeration algorithm, known as Fincke-Pohst algorithm for number theorists and Kannan's algorithm for cryptographers, has a $d^{d/2 +o(d)}$ complexity, where d is the lattice dimension. This upper bound was proved by Hellfrich more than 20 years ago. In this talk, I will show that this analysis is far from being tight, and describe the proof of an improved upper bound.

We use random matrix theory to give heuristics for the moments of L-values of elliptic curves, and via a BSD-based discretisation proceed to estimate the number of elliptic curves (up to X) with rank 2. We discuss the difference between various ways of ordering the elliptic curves, and present some computational data related the heuristics we derive.

In this talk I'll present some recent results from an ongoing project with Derek Holt (Warwick) and John Bray (Queen Mary) to classify the maximal subgroups of the classical groups in dimension less than 13. The talk will focus in particular on dimension 6, as this is a good representative case. I'll show how to derive a list containing all groups that might be maximal, and then give some sketch proofs of both maximality and nonmaximality.

I'll discuss some old work of mine on the problem of efficiently computing isomorphisms between finite fields (expressed as quotients of polynomial rings over the prime field). The main result (refining some ideas of Pinch) is a probabilistic algorithm for this problem that for most fields $GF(p^n)$ (or all, given some reasonable number-theoretical assumptions) has complexity $O(n M(n))$, where $M(n)$ is the complexity of multiplication in the field.

This talk describes several variations of the number field sieve to compute discrete logarithms in finite fields of the form $GF(p^n)$, with p a medium to large prime. We show that when n is not too large, this yields a $L_p^n(1/3)$ algorithm with efficiency similar to that of the regular number field sieve over prime fields. This approach complements the recent results of Joux and Lercier on the function field sieve. Combining both results, we deduce that computing discrete logarithms have heuristic complexity $L_p^n(1/3)$ in all finite fields. To illustrate the efficiency of the algorithm, we provide details of a discrete logarithm computation in a 120-digit finite field $F_p^3$.

A not-so-short introduction to Lie groups and their representations will be followed by a short overview of the capabilities of the LiE program and some comments on their incorporation into Magma.

Tutorial style talk demonstrating how to work with curves in Magma. The examples will be mainly related to cryptography but there may be some other wacky stuff.

Asymptotically-fast algorithms for polynomial and matrix problems generally reduce to fast multiplication. I will show how this can be implemented very effectively, in practice, in a variety of situations. In particular, the Brent-Kung modular composition algorithm can be implemented to apply fast algorithms for both polynomial and matrix multiplication in a nice way.

The Lenstra Lenstra Lovász algorithm is massively used in the MAGMA computational algebra system, making it crucial to have a LLL routine which is as reliable and as fast as possible. For this purpose, the underlying code has been almost entirely rewritten, and the user interface has been changed.

In this talk, we will stress the improvements over the previous version by considering a few examples, explain what are the new algorithms and heuristics that have been implemented and finally describe the user interface and a few LLL-based routines that have been updated/added.

We will give a brief introduction to the theory of Groups of Lie type and an overview of functionality available in Magma for these groups and related topics (Root data, Coxeter Groups, Lie Algebras). We will also discuss some of the algorithms available in Magma, among which are new or improved algorithms for element multiplication and for working in twisted groups of Lie type.

Despite its popularity, the Lenstra Lenstra Lovász reduction algorithm remains mysterious in many ways. It has been widely reported that it behaves much more nicely than what could be expected from the worst-case proved bounds, both in terms of the running time and the output quality.

In this talk, after a few reminders on the LLL algorithm itself, we investigate this puzzling statement. We discuss what is meant by lattice reduction on the average, and we present extensive experiments on the average case behaviour of LLL, to give a clearer picture of the differences/similarities between the average and worst cases. We will focus on three main points: the running-time, the output quality and the numerical behaviour.

Condensation is a method of studying the structure of modules over an algebra by transferring the structure to modules over a smaller algebra. In the best of circumstances one has an equivalence of the module categories for the two algebras. In the computational setting we usually settle for something less in the hopes of reducing a large calculation to a smaller one. In this lecture we will review some of the theory of condensation and propose a different form of condensation for implementation in the MAGMA system.

Shimura curves lie at the crossroads of many areas of mathematics: complex analysis, number theory, Diophantine equations, group theory, noncommutative algebra, algebraic geometry, Lie theory--even coding theory!

The study of the first examples of these curves (the modular curves) can be traced back as far back as Gauss, and then later Klein and Fricke; recently, they have played an important role in the proof of Fermat's last theorem and in the solution of other number theoretic problems. In this survey, we introduce Shimura curves for a general audience with an outlook toward computational algebra and discuss some of the central algorithmic problems for Shimura curves.

This talk is an abbreviated and repeated version of talks #1 and #3 from April 4 and 11.

This talk will be a report on joint work with Gabi Nebe, begun during her visit to Sydney in March.

We deal with characteristic zero representations and characters of a finite group $G$. The Schur index of an absolutely irreducible character is the minimal degree of an extension of the character field so that there is a representation of $G$ over the extension field that affords the character. The Schur index also lets us work out the characters of irreducible representations over a given field. Both these issues are important and can be difficult to resolve when computing characteristic zero representations.

We aim for an algorithm that computes Schur indices using character theory and computation in $G$, i.e. without computing any representations, for use in resolving the issues above.

The problem has a long history and there are plenty of published results that we can use. In this talk I will give a brief and biased survey of the theory and discuss how we have put together such an algorithm for computing Schur indices over subfields of cyclotomic fields and their completions.

I will describe some classical covariants and contravariants of a ternary cubic, and indicate how these constructions can be generalised to genus one normal curves of degrees 4 and 5. I will then explain how these formulae can be used to write down equations for certain visible elements in the Tate-Shafarevich group of an elliptic curve.

We continue our discussion about algorithms for quaternion algebras. Taking our base field to be a number field, we give an algorithm to compute a maximal order, which is the analogous question to computing the ring of integers of a number field. We also characterize the complexity class of this problem.

In this talk we present a new subfield algorithm which computes all intermediate fields of a separable field extension $K/k$. In the case of number fields we can prove that the new algorithm computes all "generating subfields" in polynomial time. In case that there are only polynomial many subfields we are able to compute all subfields in polynomial time.

The algorithm is based on factoring polynomials and solving linear system of equations. There are (non-trivial) examples (of degree 60) where this algorithm succeeds to find the first subfield of degree 30 within 90 seconds. This is a joint work with Mark van Hoeij.

The Kneser-Hecke-operator $K$ is a linear operator defined on the complex vector space of formal linear combinations of the equivalence classes in a family of self-dual codes of fixed length. It maps a linear self-dual code $C$ over a finite field to the formal sum of the equivalence classes of those self-dual codes that intersect $C$ in a codimension 1 subspace.

These analogues of the well-known Hecke operators in the theory of modular forms act on weight-enumerators of codes,and hence on the invariant ring of the associated Clifford-Weil group.

In the coding theory case the possible eigenvalues of $K$ can be calculated à priori and the corresponding eigenspaces are exactly the analogues of the spaces of Siegel cusp-forms.

This allows for instance to give the first coefficients of the Molien series of quite large groups (app. order $10^{76}$)

The aim of the algorithm of Lenstra, Lenstra and Lovász (LLL) is to reduce bases of euclidean lattices. Since its introduction, it proved central in many areas, ranging from algorithmic number theory to public-key cryptanalysis. Given as input a basis of a euclidean lattice in $\mathbb{Z}^d$ with integer vectors of norms smaller than B, the LLL algorithm computes a so-called LLL reduced basis in time $O(d^6łog^3 B)$, by using arithmetic operations on integers of lengths $O(dłog B)$. This running-time is too high to tackle lattice bases of large dimension or with large entries. Instead of the text-book LLL, one uses in practice floating-point variants, where the integer/rational arithmetic within the Gram-Schmidt orthogonalization (central and cost-dominant in LLL) is replaced by floating-point arithmetic with small mantissas.

In this talk, after some reminders on the LLL algorithm, I will describe the $L^2$ algorithm. It is a natural floating-point variant of the LLL algorithm, that always outputs LLL-reduced bases in time $O(d^5 (d+łog B)łog B)$. The code derived from this algorithm is the fastest available so far.

In 1970 on the ICM in Nice, A.M. Gleason presented his famous theorem that the weight enumerator of a doubly-even self-dual binary code is an element of the polynomial ring generated by the weight enumerators of the Hamming code of length 8 and the Golay code of length 24. The proof uses the fact that this polynomial ring is the invariant ring of the complex reflection group G9 of order 192.

In the meantime, many variations of this theorem have been proven. Together with E. Rains and N. Sloane, we develop a theory that allows us to prove that, in a quite general situation, the weight enumerators of codes of a given Type over a not necessary commutative finite ring span the invariant ring of the associated Clifford-Weil group. These are finite complex matrix groups given by explicit generators.

This talk presents our work in computer interfaces for pen-based mathematics. The goal of our project is to understand how best to build pen-based computer interfaces for mathematics that can be used across a wide variety of applications from PDAs to digital white boards. A robust system for pen-based mathematical computation will comprise a number of components, many of which are sophisticated software systems in their own right. We present the components of our pen-based interface for mathematics, and describe the relationship among them. We describe in some detail:

our approach to recognition of characters from large sets of mathematical symbols,

our use of empirical sub-expression frequency data, and

our portable architecture for a pen-based component that may be embedded in Maple or Microsoft Office.

A quaternion algebra is a central simple algebra of dimension 4 over a field $\mathbb{F}$; they are noncommutative analogues of quadratic field extensions, and hence arise naturally in many different areas of mathematics. In this talk, we introduce quaternion algebras and survey some basic algorithmic questions: giving a standard representation and determining if a quaternion algebra is isomorphic to a matrix ring.

A quaternion algebra is a central simple algebra of dimension 4 over a field $\mathbb{F}$; they are noncommutative analogues of quadratic field extensions, and hence arise naturally in many different areas of mathematics. In this talk, we introduce quaternion algebras and survey some basic algorithmic questions: giving a standard representation and determining if a quaternion algebra is isomorphic to a matrix ring.

The discrete logarithm problem in the class group of a curve over a finite field can be used for constructing cryptographic primitives. The case of elliptic curves is particularly well known. However, one needs to choose the curve with some care, as there are various techniques for computing discrete logarithms that work well on special classes of curves.

In general, one needs to use curves of low genus, as high genus curves are subject to index calculus attacks. In certain cases, it is possible to cover a low genus curve with a higher genus one in such a way that the index calculus attack also affects the security of the low genus curve. This kind of attack is called a cover attack.

In the first talk, I'll give a brief introduction to curve cryptography, and I'll discuss some aspects of index calculus, including some recent developments. In the second talk, I'll discuss various constructions of covering curves that weaken the discrete logarithm problem on low genus curves.

Starting with the field of rational numbers, we can consider the extension field obtained by adjoining all possible radicals (i.e., roots of polynomials $X^n - c$). By repeating this, we obtain a hierarchy of radical extensions, that poses many interesting algorithmic questions. I will consider some of those in this talk, including special cases of the denesting problem, that asks for the least field in the hierarchy a given nested radical will reside in. One such case was considered by Ramajuan and relates to generators for abelian fields.

When dealing with radicals in Magma, one has to deal with problems of ambiguity due to multivaluedness of radicals. I will propose some solutions.

The discrete logarithm problem in the class group of a curve over a finite field can be used for constructing cryptographic primitives. The case of elliptic curves is particularly well known. However, one needs to choose the curve with some care, as there are various techniques for computing discrete logarithms that work well on special classes of curves.

In general, one needs to use curves of low genus, as high genus curves are subject to index calculus attacks. In certain cases, it is possible to cover a low genus curve with a higher genus one in such a way that the index calculus attack also affects the security of the low genus curve. This kind of attack is called a cover attack.

In the first talk, I'll give a brief introduction to curve cryptography, and I'll discuss some aspects of index calculus, including some recent developments. In the second talk, I'll discuss various constructions of covering curves that weaken the discrete logarithm problem on low genus curves.

Let $\mathcal{X}$ be an irreducible algebraic curve defined over the finite field $\mathbb{F}_q$. The number $M_q$ of rational points on $\mathcal{X}$ satisfied the Hasse-Weil upper bound, $$M_qłe q+1+2g\sqrt{q},$$ where $g$ is the genus of $\mathcal{X}$.

This works well when $q$ is large compared to $g$ but not otherwise. In the latter case, the Stöhr--Voloch bound works better. A special case of this is the following, for a plane curve of degree $n$ with not all points as inflexions and $q$ odd: $$M_qłe\frac{1}{2}n(n-1+q).$$ Various aspects of these results will be discussed.

Function fields of algebraic curves share many properties with number fields, such as the field of rational numbers $\mathbb{Q}$. An example of a function field is the field of rational functions $k(t)$ over a field $k$. A consequence is that elliptic curves $E$ over number fields and function fields behave similarly. In both cases one has the Mordell--Weil Theorem that states that the group of points on $E$ is finitely generated, and it is a computational challenge to find points that generate this group, and to compute its rank.

However, one difference is that in the function field case, one can consider an elliptic curve over $k(t)$ as a surface over $k$. In this talk I will discuss how the theory of surfaces can help with determining the group of points on $E$.

The computation of Galois groups is the only problem out of Zassenhaus's four main problems in computational algebra that still has no general solution.

While substantial progress has been made in the recent years, computation of Galois groups of polynomials of degree up to 23 are now routinely done (using Magma), no degree-independent algorithm has been published so far.

In my talk I will explain what computational challenges need solving to remove the dependence on pre-computed data and report on recent advances in doing so.

I will give a detailed overview of the many structures and algorithms in the Magma Computer Algebra system for computing in Linear and Polynomial Algebra. The key challenges and successes will be highlighted, particularly in the goal of practical implementations of asymptotically-fast algorithms.

Exterior algebra methods give a method to compute the cohomology of coherent sheaves. This talk explains the underlying principle such as the Bernstein--Gelfand--Gelfand correspondence, Tate resolution and Beilinson monads.

As an application we sketch how to compute the Chow form of a scheme, and derive certain resultant formulas.

This is joint work with David Eisenbud.

The higher direct image complex of a coherent sheaf (or finite complex of coherent sheaves) under a projective morphism is a fundamental construction that can be defined via a Cech complex or an injective resolution, both inherently infinite constructions. Using exterior algebras we give an alternate description in finite terms.

Using this description we can give explicit descriptions of the loci in the base spaces of flat families of sheaves in which some cohomological conditions are satisfied---for example, the loci where vector bundles on the projective space line splits in a certain way, or the loci where a projective morphism has higher dimensional fibers.

Our approach is so explicit that it yields an algorithm suited for computer algebra systems.

(Based on joint work with Gavin Brown and Michael Kerber)

I first recall briefly the graded ring approach to polarised varieties, the orbifold Riemann--Roch formula giving their Hilbert series. The general program for classifying $\mathbb{Q}$-K3 surfaces and $\mathbb{Q}$-Fano 3-folds was outlined in [Singa]. There has been considerable progress on this in the last 2 or 3 years due to Gavin Brown and others. In particular, the combinatorics of the Hilbert series, and the large number of cases that happen, are handled by a convenient online Magma database (see [GRDB]).

A main aim is to treat the 142 numerical families of codim~4 Fano 3-folds by Gorenstein projections of the simplest type. The database tells us that 116 of the 142 numerical families have one or more numerical Type~I projection to codim 3. We show that in each of these 116 x (one or more) cases, there is at least one Tom and one Jerry construction, leading to quasismooth Fano 3-folds that are not isomorphic; in particular, in each of these numerical cases the Hilbert scheme of codim~4 Fanos has at least two irreducible components containing quasismooth Fanos.

[Singa] S. Altnok, G. Brown and M. Reid, Fano 3-folds, K3 surfaces and graded rings, in Topology and geometry: commemorating SISTAG (National Univ. of Singapore, 2001), Ed. A. J. Berrick and others, Contemp. Math. 314, AMS, 2002, pp. 25--53, preprint arXiv:math/0202092v1, 29 pp.

[GRDB] Gavin Brown, [http://grdb.lboro.ac.uk/ Graded ring database]

This talk is divided into two parts. The first part is about finding the classification of small-dimensional solvable Lie algebras. This is done by extending a solvable Lie algebra of smaller dimansion by a derivation. Subsequently, the Groebner basis facilities of Magma are used to find isomorphisms, and obtain a non-redundant list. This procedure has been used to find the classification of the solvable Lie algebras of dimensions 3, 4.

The second part is about the electronic version of the classification of the solvable Lie algebras. I have written Magma functions for constructing the Lie algebras that appear in the classification. This is complemented by a function that, given a solvable Lie algebra of dimension $łe 4$, finds an isomorphism with a Lie algebra from the classification. Here Groebner bases are no longer used; the algorithm is based on the proof of the correctness of the classification.

We survey some recent additions and improvements to various functionality in MAGMA related to number theory. In particular, we will discuss: descent on elliptic curves, Heegner points on elliptic curves, a new method for computing the Weierstrass $p$-function, and the MAGMA implementation of LLL for indefinite Gram matrices (with particular consideration of nonzero isotropic vectors). Most of these functions require high-precision real-number calculations, and thus we will also give some comments regarding MAGMA's new real/complex numbers.

According to Thurston's geometrization conjecture (now probably proven by Perelman) we can decompose 3 manifolds into geometric pieces, each with one of 8 geometries. With the classification problem solved for 7 of the geometries, the interesting and difficult case of hyperbolic geometry remains. Since these manifolds are $K(\pi,1)$'s they are classified up to homotopy equivalence by their fundamental groups. Of course it is not known what this rather interesting family of infinite groups is! Mostow-Prasad rigidity says that homotopy equivalence implies isometry. Thus any geometric invariant, such as the volume of a hyperbolic 3-manifold, is at the same time an invariant of the topology and the fundamental group. There are many fascinating ways to exploit this "bridge".

One is to realize the fundamental group of an (orientable) finite volume hyperbolic 3-manifold as a Kleinian group -- namely the group of covering transformations of the manifold -- with entries in $PSL(2,\mathbb{C})$. The traces squared of these matrices turn out to be algebraic and generate a number field called the "invariant trace field" of the manifold (or Kleinian group). This is a commensurability invariant of the group, i.e. it is unchanged on passing to finite index subgroups. Further commensurability invariants are obtained by taking the quaternion algebra over the invariant trace field spanned by the matrices themselves.

My work on "snap" with Craig Hodgson and Walter Neumann has been to extend the computer program SnapPea with computations in high-precision and algebraic numbers so as to compute these invariants. Using the classification of quaternion algebras over a number field we obtain powerful commensurability invariants for all Kleinian groups. For the so-called arithmetic Kleinian groups this gives a complete classification up to commensurability.

Let $K$ be a $p$-adic field. We give an explicit characterization of the abelian extensions of $K$ of degree $p$ by relating the coefficients of the generating polynomials of extensions $L/K$ of degree $p$ to the norm group $N_{L/K}(L^*)$. This is applied in the construction of class fields of degree $p^m$.

We will firstly recall the scientific objectives of the [http://www.mpfr.org/ MPFR library], present the functionalities of the current release (2.1.1), and discuss some applications built on top of mpfr. Then we will present recent developments that will be available in the next major release, in terms of efficiency, functionality, portability, and algorithm design. Finally we will discuss some of the main challenges we want to address in the future.

This talk will introduce some applications of pairings in elliptic curve public key cryptography. In particular, I will present some new results on efficient implementation of pairings. This is joint work with Barreto, O HEigherty and Scott.

The problem is to find all normal subgroups up to a given finite index $n$ in a given finitely presented group $G$. Peter Dobcsanyi developed a method of doing this which essentially involved finding all subgroups of index up to n, using the standard low index subgroups algorithm, and then picking out the normal ones - of course, he used a number of tricks to avoid traversing branches of the search tree that could not possibly lead to normal subgroups.

We describe an alternative method, developed and implemented in Magma by David Firth, which runs considerably faster on the examples considered by Dobcsanyi, such as finding the normal subgroups of up to index 1500. We still use the low index subgroups algorithm, but only to find the normal subgroups of $G$ with perfect quotients, for which we need the subgroups of $G$ up to a much smaller index than $n$. This is because the normal subgroups arise as cores in $G$ of the subgroups $H$ of $G$ found by low index subgroups. Normal subgroups with soluble quotients are found by using the $p$-quotient algorithm. The method works recursively, and for each normal subgroup $H$ of $G$, we compute a presentation of H and, if necessary, apply the algorithm to $H$ up to index $n/|G:H|$. New normal subgroups are also found as intersections of existing ones.

It has been succesfully applied for $n$ up to 50000 in some examples.

I'll describe an algorithm to compute isomorphisms of function fields or, equivalently, compute birational maps between algebraic curves. The basic technique is to find fairly unique models and then compare. The algorithm can also be used to compute automorphism groups.

There are many algorithms for permutation groups that rely on the availability of a BSGS for the group. With matrix groups a BSGS can not always be found efficiently. In this talk I will talk out computing in large degree matrix groups using Ascgbacher's Theorem. In particular the construction of a chief series, re-ordering this chief series into the standard Trivial Fitting model and computing Sylow subgroups.

Linear differential operators over a rational function field can be factored, just like polynomials over number fields. The main difference between these two, however, is that the multiplication of differential operators is non-commutative. The order of the multiplication is therefore important. There are a few algorithms known for determining a class of factorisations. The one that currently is being implemented uses factorisations over Laurent series rings. These can be used later for the factorisation over rational fields. In this talk I plan to talk about the series implementations and the ideas behind them, and mention some similarities with the number theory case.

I will explain some techniques that work well in practice to exhibit suspected non-trivial elements of order 2 in Tate-Shafarevich groups of Jacobians of hyperelliptic curves. I will concentrate on some phenomena that occur in genus 2 that have no analogue in the genus 1 case.

This talk will describe techniques for constructing the maximal subgroups of finite permutation groups. Apart from being interesting in themselves, the maximal subgroups of a group have many applications: for instance one may use them to investigate the full subgroup lattice, or to determine the character table of the group.

I will start by presenting the general approach taken by recent algorithms. We will then examine the techniques used to compute the maximal subgroups of various families of almost simple groups, before descibing recent work of Derek Holt and myself on constructing the maximal subgroups of finite black box classical groups.

Let $S$ be a non-empty proper subset of the set of places of a global function field $\mathbb{F}$ and $E$ a cyclic Kummer or Artin--Schreier--Witt extension of $\mathbb{F}$. I will present a method to efficiently compute the ring of elements of $E$ which are integral at all places of $S$.

This will be an informal talk on matrix algebra computations.

In the late 1990s Jean--Charles Faugere introduced an algorithm for computing Groebner bases which is a lot faster than the traditional Buchberger algorithm. I will describe the major ideas behind this algorithm and my implementation of it in Magma, and how it can be applied to several types of problems, including cracking the HFE cryptosystem.

This talk will be an elementary survey of the machinery for algebraic maps between schemes in Magma with some examples of their use.

I will explain the relation between severi-brauer varieties and central simple algebras. Firstly I will show known ways for passing from the algebra to its Severi--Brauer variety, afterwards an algorithm for the opposite direction in the case of surfaces. We will see how to use the corresponding algebra for finding a rational point on the surface.

Since the advent of class field theory one of the main problems has been its abstract nature that prevented researchers from computing examples. Thus although class field theory classifies abelian extensions of global fields, it failed to provide explicit defining equations for them. Recent progress in computational number theory now permits us to close the gap.

In this talk I will explain how one can find explicit defining equations utilizing Kummer, Artin-Schreier and Witt theory. Applications of these techniques include the explicit construction of good linear codes.

In the end, time permitting, I will also discuss other approaches based on Drinfeld theory.

I will describe a new algorithm for computing the character table of a finite group. The main ingredients of the algorithm are Brauer's theorem on induced characters and lattice reduction by LLL. We find that for many interesting groups it performs far better than using the current standard method (Burnside--Dixon--Schneider). I will report on the performance of the algorithm in computing character tables of various groups, including local subgroups of $3Fi_{24}$ and some maximal subgroups of the Monster.

We discuss a problem a Zagier regarding finding large integral points on elliptic curves, and show how this reduces to a system of polynomial equations. There are four cases where a nontrivial solution is likely to exist, with the easiest being 4 equations in 4 unknowns and the most difficult having 12 of each. The first case was solved in 1988 by Elkies using MACSYMA. We have found a nontrivial solution in the second case using neither Grobner bases nor (multi)resultants, but multidimensional p-adic Newton iteration. We discuss in what circumstances such a technique might be useful.

After a short introduction into the theory of quantum groups I will sketch a few algorithms for computing with them; namely an algorithm to compute with PBW-type bases, an algorithm to compute elements of the canonical basis, and algorithms to compute irreducible representations.

I'll identify ten rules that people follow in finding large factors of integers. I'll explain how all of the rules can be, and how most of them should be, violated. Prior exposure to factorization algorithms is not required.

In my talk I will give a short introduction on quantum error correction. On the physics' side, the underlying mathematical model is based on complex finite dimensional vector spaces and their tensor products. Errors are modelled by linear transformations on these spaces. Surprisingly, despite its continuous nature, the problem of constructing error-correcting codes for quantum systems can be tackled with the help of discrete mathematics. The reduction of this problem uses concepts from representation theory and symplectic vector spaces. Finally we can employ classical error-correcting codes in constructing their quantum counterparts.

The slides are available in [http://iaks-www.ira.uka.de/home/grassl/paper/DiscMathMeetsPhysics.ps.gz compressed post script] or in [http://iaks-www.ira.uka.de/home/grassl/paper/DiscMathMeetsPhysics.pdf.gz compressed pdf] format.

In this talk we give a concise introduction to the objects $K_0, K_1, K_2$ for commutative unital rings, especially rings of algebraic integers. For number fields $F$ the group $K_2$ has a finite subgroup, the so-called wild kernel. We present new ideas for computing the $l$-rank of that kernel for any prime number $l$. For this we employ local and global methods from computational algebraic number theory.

There is no known polynomial time $4$-colouring algorithm for planar graphs, except the algorithms derived from the proofs of the four-colour theorem (4CT) by Appel, Haken, Koch (1977) and Robertson, Sanders, Seymour, Thomas (1994).

Short of doing this, one way to colour planar graphs is to investigate the problem of finding $k$-flows in graphs:

There is an equivalence between $k$-colouring a planar graph and finding a $k$-flow in a graph.

Let $G$ be a graph, $E$ its edge set, and $D$ an orientation of its edges.

For any vertex $u$ of $G$, define $E_u$ to be the set of edges in $E$ with end-vertex $u$.

A \emph{k-flow} for $G$ is defined as a map $f:E\mapsto\frac{\mathbb{Z}}{k\mathbb{Z}}\setminus{0}$ such that for all vertices $u$ in $G$, $\sum_{eın E_u}f(e) = 0$.

If one could find a reasonable'' algorithm to construct a 4-flow (or a 3-flow) in a graph then one would have areasonable'' algorithm to colour planar graphs. (Note that the decision problem is in general NP-complete.)

In my talk I will discuss these various issues and show how I used Magma's toolbox in this context.

In this lecture I will discuss two theorems. One, the Skolem--Mahler--Lech theorem, deals with linear recurrent sequences, where the $n$-th value of the sequence depends linearly on the previous values. For such a sequence $( a(n) : n = 1, 2, łdots )$, it describes the shape of the set ${ n : a(n) = 0 }$. The other theorem, by Chabauty, gives a partial result in the direction of the now fully known fact that a general algebraic curve has only finitely many rational points. Coleman derived a quantitative statement from Chabauty's method. These seemingly unrelated theorems share a common method of proof: they are based on p-adic analysis. In this talk I will sketch the proofs and point out the similarities between them. I will emphasise the analogies that can be drawn between the quite elementary Skolem--Mahler--Lech Theorem and Chabauty's construction.

Let $\mathbb{K} = \mathbb{Q}(a_1,a_2,łdots,a_m)$ be a number field with $m>0$ field extensions. Let $f_1$ and $f_2$ be polynomials in $\mathbb{K}[x_1,x_2,łdots,x_n]$ and let $g = GCD(f_1,f_2)$ be the greatest common divisor of $f_1$ and $f_2$. In this talk I will outline an algorithm for computing $g$, present my Magma implementation of this algorithm and compare my code with the built-in Gcd operation in Magma.

The reason for my interest in this problem is because I believe it is the one of the most important and difficult computational problems in a general purpose computer algebra system to get right; my timings will give some indication as to why this is the case but I will seek to give general reasons to justify this.

I would like also to present for dicussion three problems that I encountered when writing the Magma code and possible solutions that Allan, Claus and I have ``mulled over'' for more general discussion.

Fermat himself determined all rational points on the curve $X^4 + Y^4 = 1$, namely $(X,Y) = (0,1),(0,-1),(1,0),(-1,0)$. The generalisation of this to $X^n + Y^n = 1$ has been well publicised! Instead, we consider a different generalisation, to all curves of the form: $a X^4 + b Y^4 = c$, where $a,b,c$ are integers, and in particular the case $X^4 + Y^4 = c$.

For many values of $c$ one can find all rational points using elementary congruence arguments or by maps to elliptic curves. However, there remain occasional values of $c$, such as $c = 17, 82, łdots$ etc, for which these elementary techniques are unsuccessful. Serre asks how one might in particular try to solve the case $c = 17$. We discuss various alternative lines of attack to try to deal with these exceptional values of $c$, including the line of attack which allowed Flynn and Wetherell finally to solve the case $c = 17$ in 1999.

In this talk we present some basic concepts of the Galois theory of linear differential equations. We introduce the differential Galois group and a strongly related group, the monodromy group, of a linear differential equation.

At the end we present a method of calculating rational solutions of a linear differential equation, that has been implemented in MAGMA. Examples are given throughout the talk.

We shall give a summary of some of the main ideas in the area, beginning with conics (that is, curves which can be described by linear and quadratic equations, such as circles, lines, etc) and the group law on an elliptic curve. We then move onto higher genus curves, describing the Jacobian of a curve and its group law, and points of finite order on the Jacobian. We describe how recent advances in the constructive side of the subject have allowed the solution of several specific problems concerning cycles of quadratic polynomials, and $\mathbb{Q}$-derived polynomials (that is: polynomials all of whose roots are in $\mathbb{Q}$, all of whose derivatives also have the same property).

Computing the cardinality of the Jacobian of a curve of genus 2 is an important task for cryptography. Mestre has proposed an algorithm based on the computation of the $p$-adic canonical lift using Richelot isogenies. We explain this algorithm and how to adapt it to use the many improvements that exist for elliptic curves.

Computations in the $p$-adics and their extensions is important for many reasons, including most recently point counting algorithms for elliptic curves. I will briefly outline the theory behind the $p$-adics, motivate their use, and then give an overview of the algorithms and tricks underlying Magma's new implementation of the $p$-adics.

I will discuss the isomorphism problem for modular group algebras of $p$-groups. The question is: suppose that $G$ and $H$ are $p$-groups and that their group algebras $kG$ and $kH$ are isomorphic where $k$ is a field of characteristic $p$. Is it necessary that $G$ and $H$ be isomorphic? It is known that the answer is yes for groups of order 128 ($p = 2$).

Éamonn O'Brien and I are working on a program to check the groups of order 256. The idea is to use the packages for basic algebras and for finitely presented algebras to create a test for isomorphism of local algebras.

Let $G = $ be a finitely presented group acting on a $KG$-module $M$, with $|X|=r$, $|R|=s$, $dim(M)=n$. In the first talk, we showed how the first cohomology group $H^1(G,M)$ could be computed as $$Nullspace(C_1) / Rowspace(C_0),$$ for a certain $n\times nr$ matrix $C_0$ and $nr\times ns$ matrix $C_1$ over $K$.

In this talk, we discuss the computation of $H^2(G,M)$. This is another important object to compute because the group extensions $$0 \rightarrow M \rightarrow E \rightarrow G \rightarrow 1$$ in which the module action of $G$ on $M$ is induced by conjugation in E are classified up to equivalence by $H^2(G,M)$.

Once again, the main effort of the computation occurs in the calculation of the nullspace of a certain matrix. This works out nicely when $G$ is a pc-group, but for a general finite group we have to work harder to reduce the size of the matrix involved. If $G$ is a permutation group, then we can sometimes make use of a base and strong generating set to reduce this size to manageable proportions. Furthermore, if we are only interested in the order of the group $H^2(G,M)$, rather than in constructing the extensions explicitly, then we can use some cohomology theory to reduce the computation from $G$ to certain $p$-subgroups of $G$.

I will explain two ways in which the abstract notion of the Jacobian of a curve can be made concrete enough for a computer to deal with. These two descriptions of the Jacobian both have their own strengths and weaknesses. I will explain how one (and the computer) can translate back and forth between the two descriptions. This allows one to have the best of both worlds.

These methods can be used to prove that two genus 2 curves are isogenous or that a genus 2 curve has complex multiplication.

In arithmetic geometry, people study systems of polynomial equations and their solutions over number fields and other non-algebraically closed domains. Even the problem of deciding whether there are any solutions at all over such domains is, in general, an unsolved problem.

Interestingly enough, the question becomes easier if one enlarges the domain. For instance, if one puts a topology on a number field and takes the completion, then any solvable system of equations over the number field necessarily also has a solution over this larger field. The latter turns out to be a solvable problem. I will explain how one can do this in practice.

This will be an elementary talk defining the first cohomology group $H^1(G,M)$ of a group $G$ acting on a module $M$, and explaining how to compute it as the nullspace of a system of linear equations. Here $M$ can be an arbitrary finitely generated abelian group.

We describe applications to finding complements in extensions of $M$ by $G$, and to the computation of subgroups of a finite group and of the automorphism group of a finite group.

There are many methods of constructing an explicit representation of a given group, starting from only theoretical information about the group such as characters and subgroup structure. These range from (a) constructing a set of generators and relations from the subgroups, and then using Todd-Coxeter to make a permutation representation, to (b) making matrix representations of subgroups and gluing them together to make a matrix representation of the whole group.

I shall concentrate on the latter, illustrating with a 3-dimensional example the basic ideas that apply even to making a 196882-dimensional representation of a group of order 808017424794512875886459904961710757005754368000000000.

I shall continue from where I left off last time. Particular topics I intend to cover in some detail are:

• \emph{peakword} condensation and its uses to find submodule lattices (here we generalise from an idempotent $e$ -- satisfying $vee = ve$ for all $v$ in $V$ -- to a \emph{word} $w$ merely satisfying $Vww = Vw$);
• \emph{direct} condensation without writing down the permutations;
• the trace equation and other methods of calculating character values directly from condensed modules.

The talk will of necessity be rather more technical than the first one.

My master thesis was about prime factorisation. Given an integer $N$, the task is to find the prime factors of $N$. Before 1970 it was hardly possible to factorise a random $N$ consisting of more than 20 digits. Each decade since the 70's has had a dominating factorisation algorithm:

• The Continued Fraction Factorisation Algorithm in the 70's.
• The Quadratic Sieve (QS) in the 80's.
• The Number Field Sieve (NFS) in the 90's and today.

These algorithms have raised the number of digits of $N$ to about 160 for a random $N$ and more than 200 digits for special $N$. The three algorithms all build on the same principle, that is, to find non-trivial integer solutions $x$ and $y$ to the equation $x^2 = y^2\ (\mod N)$.

In my talk I will describe QS and NFS.

The term \emph{condensation} refers to a variety of techniques whose common element is that they \emph{condense} a large module for a large algebra to a small module for a small algebra, while retaining enough structure so that easily computed information about the small module yields useful information about the big module.

I shall describe at an elementary level the case where the algebra is a finite group algebra and the module is a permutation module, and if time permits I shall mention more advanced techniques which enable us to calculate explicitly character values of (for example) degree $10^7$ constituents of degree $10^9$ permutation modules.

I describe a new database of (the numerical data associated to) K3 surfaces. This is available in Magma as the {{K3Database}}. In due course, the data will also be available on-line.

(Addendum: For details of the theory see [http://projecteuclid.org/getRecord?id=euclid.em/1175789798 "A database of polarized K3 surfaces"]. The database is [http://grdb.lboro.ac.uk/ available on-line].)

The foundations for the field of quantum computation were laid by Richard Feynman, Paul Benioff, and Yuri Manin already in the early 80s by studying the relationship between the physical and computational processes. Starting from the observation that quantum mechanical processes are hard to simulate on classical computers, they concluded that quantum mechanics might help to speed-up some computations. After preliminary results which were mainly of a theoretical nature, in 1994 Peter Shor presented an algorithm of practical interest for a computer based on the principles of quantum mechanics [Sho94]. His quantum algorithm for factoring integers is exponentially faster than any classical algorithm known so far. Another algorithm showing the advantage of quantum mechanical systems is the quantum "search" algorithm of Grover [Gro96]. This algorithm achieves a square root speed-up compared to a classical algorithm when solving the satisfiability problem of an unstructured Boolean function.

After an introduction to the mathematical framework of quantum information processing, I will present the algorithms of Grover and Shor. The latter gives rise to a large class of algorithms which solve the so-called hidden subgroup problem establishing a connection to group theory and representation theory in particular.

[Sho94] Shor, P. W., "Algorithms for Quantum Computation: Discrete Logarithm and Factoring". \emph{Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS)}, 1994, pp. 124--134.

[Gro96] Grover, L. K., "A fast quantum mechanical algorithm for database search". \emph{Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC)}, 1996, pp. 212--219.

(For further references, see e. g. the [http://iaks-www.ira.uka.de/QIV website of the quantum computing group] in Karlsruhe.)

In the talk I introduce the subresultant method to solve over-determined multivariate polynomial systems over C. The main idea is to construct a linear system such that its solutions give either a rational representation of the solution set of the polynomial system or an approximation of it. I will describe several constructions for such linear systems, and sketch an argument why they are equivalent.

We describe an algorithm to solve orbit-stabilizer problems for an infinite polycyclic group acting on a free abelian group. This method facilitates solutions to a number of fundamental problems in computations with infinite polcyclic groups such as the determination of centralizers, normalizers or intersections as well as solutions to the conjugacy-problem for elements and subgroups.

In the first half of the talk I will give an introduction to the construction of modular symbols, which are used for computing with modular forms. In the last part of the talk I will describe several different lattices of modular symbols I have been looking at recently.

I will describe the current work on completing the classification of these permutation groups. We will briefly visit the O'Nan Scott theorem and linger a little longer on Aschbacher's theorem. Then I will describe the techniques that are being used to classify the irreducible subgroups of $GL(d, p)$ for $p^d$ less than 1001. I may finish by presenting some new results.

I will show how to compute defining equations for class fields using the Artin map. As an application I will (briefly) explain how to use this to construct fields with certain interesting Galois groups.

In this talk, I will present a research project going on in Brussels since 1990 in which we try to find a unified geometric interpretation of all the finite simple groups. I will show some of the algorithms we had to build in that context to convert geometric properties into group theoretical questions. I will also give an update on the project itself.

A standard problem in elliptic curve cryptography is the selection of elliptic curves as the basis for a secure cryptosystem. The principle requirement is that structure of the group of rational points be of prime or near-prime order. One approach to the problem is to select curves at random and to count points---an expensive option. The alternative is to use the theory complex multiplication to construct elliptic curves with known endomorphism ring structure, whose reduction is known to have a predetermined number of points. This construction is also applied to the problem of primality proving. For this purpose the minimal polynomial of the $j$-invariant of those curves with fixed endomorphism ring $R$ is computed over $\mathbb{Q}$, and reduced modulo a prime. For example for $disc(R) = -23$, this class polynomial is: $$x^3 + 3491750x^2 - 5151296875x + 12771880859375$$ The disadvantage the size of the coefficients grows in proportion to the size of the square root of the discrimiant, which limits the Noting that the function $j$ is a generator for the function field of the moduli space $X(1)$ of elliptic curves, we can generalize this construction to use functions on modular curves of higher level which parametrize an elliptic curve plus additional isogeny structure. Taking a function on the modular curve $X_0(101)$, the resulting class polynomial takes the much simpler form: $$x^3 - x + 1.$$ We will discuss this construction, its benefits and limitations, and other applications in constructive class field theory.

Knowing whther or not a particular finitely presented group is finite or infinite is very important in many applications of group theory, especially to geometry and topology. In this talk I will present a procedure which is able to quickly decide this question for almost all examples published in the literature.

Let $h_n$ the homogenous symmetric function of degree $n$. You can look at it as the generating function of weakly increasing sequences of integers of length $n$. Let $m_I$ be the monomial symmetric function. You can look at it as the generating function of weakly increasing sequeces, whose weight is a permutation of $I$. We will give an algorithm to compute the decomposition of the plethysm $S_n[m_I]$ as a sum of monomial symmetric functions.

Computing the number of points of an elliptic curve defined over a large finite field of characteristic 2 is one of the most tricky part of the development of an elliptic curve cryptosystem. A few years ago, Satoh proposed a new algorithm based on the computation of the canonical $p$-adic lifting of the curve. We will first recall some basics and the general lines of Satoh's algorithm. Based on an idea of Mestre, we will then explain how the Arithmetic-Geometric Mean can be used to speed-up the computations and provides an easy extension to the case of genus 2 curves.

Let $H$ be the upper half complex plane. The classical modular curves $X_0(N)$ are defined as quotients of $H$ by finite index subgroups of $PSL_2(Z)$. The class $X_0^D(N)$ of Shimura curves are defined analogously, generalising $X_0(N)$, in terms of the actions on $H$ of twisted matrix groups coming from subgroups of units in indefinite quaternion rings. I will define the relevant class of groups and their actions on the upper half plane, and describe the computational problem of determining a fundamental domain, illustrated with examples.

Sparse linear systems are frequently encoutered in different areas of computer algebra, numerical analysis, and physics. Dedicated algorithms exist for dealing with such systems, taking advantage of their tiny number of non-zero coefficients. We will concentrate on the systems occuring in computer algebra, defined over (either large or small) finite fields. We will address the structured gaussian elimination and the Wiedemann algorithm, as well as the Lanczos method (much more briefly). We will also try to discuss the recent ``block'' generalizations of the two latter algorithms, which permit a partial distribution of the computations.

The ability of a computer to find approximate roots to polynomials is very useful when we deal with "flabby", or topological, properties of the polynomials. In this talk I will introduce a simple topological problem involving polynomials and describe a primitive method to solve the problem in small cases. Already these small cases are more complicated than most examples that appear in current research. More precisely, the lecture considers the problem of calculating fundamental groups of complements of plane curves, although knowledge of fundamental groups will not be necessary.

According to a theorem of Mordell, the set of rational points on an elliptic curve form a finitely generated commutative group. The rank of an elliptic curve over a number field is defined to be the rank of the subgroup of elements of infinite order.

Already Pierre de Fermat succeeded in proving that the rank of one particular elliptic curve is $0$, which enabled him to prove that $x^4+y^4=z^4$ does not have positive integral solutions.

Although a great deal of research has been done on the subject, the only unconditional method of getting upper bounds on the rank of an elliptic curve is essentially Fermat's method of infinite descent.

In this talk, I will discuss how one can perform this construction in a more modern language. I will be following an approach taken by Cassels, Flynn and Schaefer rather than the style used by Birch, Cremona and Swynnerton-Dyer. This approach takes better advantage of the interplay of several groups involved and is sometimes referred to as the "number field method" rather than the "homogeneous spaces method".

It has the advantage of being less susceptible to combinatorial explosion and of being readily generalisable to number fields other than the rationals.

If time permits, I will show how one can use descent techniques over quadratic extensions to sharpen the rank bound obtained from a descent over the base field. This relates closely to a phenomenon generally referred to as "visualising Sha"

Let $p$ be a prime and let $n,k$ be integers, $gcd(p,n)=1$ and $k>1$. Calderbank and Sloane characterised cyclic codes of length n over the integers modulo $p^k$ in a form which intuitively suggested a 'minimal strong Groebner basis (SGB)' over the integers modulo $p^k$.

Let $D$ be a principal ideal domain. The structure of a minimal SGB for an ideal of $D[x_1,...,x_n]$ is due to Becker and Weisspfenning, Lazard and others. We outline an effective theory of minimal SGB's for ideals of $R[x_1,...,x_n]$, where $R$ is an arbitrary principal ideal ring (e.g. the integers modulo $p^k$), generalising the PID case.

We then characterise cyclic codes of arbitrary length over $R$ using minimal SGB's. This yields the result of Calderbank and Sloane as a special case.

This is joint work with Ana Salagean, Nottingham Trent University, UK.

I will compute an element of order 5 in the Shafarevich-Tate group of a 20-dimensional abelian variety, right before your eyes!

I want to give an overview of some project for computing group cohomology and extending the techniques to the computations of cohomology over other algebras. The projects have raised issues concerning Gröbner bases and the design of the packages for dealing with algebras in Magma.

I will give an elementary introduction to congruence subgroups and their action on the upper half complex plane, using a java program to illustrate some of the ideas. I will briefly discuss some background and motivation. Then I will talk about the methods used for computing fundamental domains for this action, in particular the method of Kulkarni. I will give a demonstration and illustration of this method as implemented in magma, and I will discuss problems for further work and computation.

The Picard--Fuchs differential equation of a family of varieties is useful for describing the variation of Hodge structure of the family. I will give the definition of the Picard--Fuchs equation in general, and describe its computation. I will give examples for the case of families of elliptic curves and families of K3 surfaces.

I will concentrate on the case of modular families of of elliptic curves, which leads to differential equations for modular forms, and if there is time I will also describe a relationship between a solution of the Picard-Fuchs equation and equation the L-series of the ambient space in certain cases.

The group generated by the Weierstrass points of a smooth curve in its Jacobian is an interesting intrinsic invariant of the curve. We compute this group for some families of plane quartics. As an application, we get some information on the rank and on the torsion part of this group for a generic quartic having a fixed number of hyperflexes.

This will be a nontechnical (beyond knowing something about curves) introduction to some of my favourite surfaces. Just as for curves, there is a classification statement and the different parts of the classification have different aspirations, techniques and results.

The Magma system has a lot of functions for working with algebraic curves. I will review the classification of curves and compare it to the Magma typing regime. Then I'll give an overview of the classification of surfaces to show how a similar typing system might work.

I will present some recently developed algorithms for solving fundamental matrix problems in Computational Algebra. The algorithms not only have very good asymptotic complexity, but perform extremely well in practice (they have been implemented within Magma). Emphasis will be on matrices over finite fields, the integers and the rationals, and I will present a very new fast algorithm for computing the Hermite Normal Form of an integer matrix.

Let $C$ be a curve of genus 2 over a finite field for which we want to find the number of points. This problem can be reduced to counting points on the Jacobian of $C$, which is easier, due to its group structure.

After recalling some basics about these objects, we will describe a Schoof-like algorithm which gives a solution to our problem in polynomial runtime and has been implemented in Magma.

Still, this algorithm is not yet enough to treat large examples and the natural question is how to extend to the genus 2 the methods of Elkies-Atkin which have proved to be efficient for elliptic curves. We will present a construction of some modular equations that can be useful in this context.

A natural problem in the computational treatment of finite matrix groups is the recognition of simple groups. That is, given a matrix group $G$ known to be quasi-simple, determine the isomorphism type of $G$. If $G$ is known to be of Lie type in given characteristic $p$, Babai, Kantor, Palfy and Serres describe an algorithm to solve this recognition problem. We report about an implementation of this (joint work with Eamonn O'Brien) as well as on an approach to guess the right characteristic $p$.

A group is called polycyclic if it has a subnormal series with cyclic factors. This characterisation can be used to design effective and practical algorithms for polycyclic groups. For finite polycyclic groups such methods have been developed over the last 30 years and they are used successfully in computations with finite polycyclic groups. The infinite case is much less investigated and it is the aim of this talk to report on some recent developments in the design of practical algorithms for (possibly infinite) polycyclic groups.

We describe an efficient new algorithm for factoring a polynomial $\Phi(x)$ over a field $K$ that is complete with respect to a discrete prime divisor. For every irreducible factor $\phi(x)$ of $\Phi(x)$ this algorithm returns an integral basis for $K[x]/\phi(x)K[x]$ over $K$.

The method of adjoints is one of the most common approaches to the computational theory of algebraic curves, especially to constructing Riemann--Roch spaces and canonical embeddings. The underlying theory generalizes easily to surfaces and even higher dimensions. In fact, adjoints have played a crucial role in the theory of algebraic surfaces in the classical Italian school (Cremona, Castelnuovo, Enriques,..). In the first part of the talk, we will discuss several applications. The computational foundation for the method of adjoints is an efficient method for computing adjoints. The fastest way to do this uses two-dimensional analogues of Puiseux expansions. In the second part of the talk, this approach will be explained.