RHUL Pure Mathematics Seminar: 2007–2008

Autumn 2007

2nd October Peter Keevash (Queen Mary)
A hypergraph regularity method for generalised Turán problems (abstract)
9th October Marcus Appleby (Queen Mary)
Geometrie and Measurement (abstract)
16th October Laura Hitt (University College Dublin)
Hyperelliptic Curves in Cryptography (abstract)
23rd October Trevor Wooley, FRS (Bristol)
A singular approach to solving quintic equations (abstract)
30th October Artur Czumaj (Warwick)
Testing expansion in bounded-degree graphs (abstract)
6th November Nikolaos Fountoulakis (Birmingham)
Percolation on random graphs with a given degree sequence (abstract)
13th November Oliver Riordan (Oxford)
The diameter of G(n,p)
20th November Rhiannon Hall (Brunel)
A chain-type theorem for hyperplanes and a splitter-type theorem for cocircuits (abstract)
27th November Robert Morris (Cambridge)
Bootstrap percolation
4th December Mark Walters (Queen Mary)
Random geometric graphs
11th December Simon Blackburn (Royal Holloway)
Prolific IPP Codes (abstract)

Spring 2008

15th January Andrew Booker (Bristol)
Vinogrodov's three primes revisited (abstract)
22th January Sebastian von Wuthenau (Cambridge)
Geodesics in Surface Tessellations with Bounded Combinatorial Curvature (abstract)
29th January Daniel Appel (RHUL)
Congruence Subgroups of the Automorphism Group of a Free Group (abstract)
5th February Leslie Goldberg (University of Liverpool)
Inapproximability of the Tutte polynomial (abstract)
12th February Martin Bridson (Oxford)
Dimension rigidity for group actions (abstract)
19th February Kenny Paterson (RHUL)
From Fish to Phishing (abstract)
26th February Chris Brookes (Cambridge)
Iwasawa algebras
4th March Rachel Camina (Cambridge)
Recognising Zp[[t]]-analytic pro-p groups (abstract)
11th March Wouter Castryck (Leuven)
Effectively determining the number of points on curves over finite fields (abstract)
18th March Roger Heath-Brown (Oxford)
Sums and differences of three k-th powers (abstract)

Summer 2008

29th April Tuvi Etzion (Technion, Haifa)
Designs and Coding theory in projective space (abstract)
6th May Louigi Addario-Berry (Oxford)
Killed random branching walks (abstract)
13th May James McKee (RHUL)
Integer symmetric matrices of small spectral radius and small Mahler measure (abstract)
3rd June David Mireles-Morales (RHUL)
A geometric interpretation of the infrastructure of a real function field (abstract) (abstract)
10th June Peter Symonds (Manchester)
Group actions on polynomial rings (abstract) (abstract)

Peter Keevash: We introduce a method that we believe may be foundational for a comprehensive theory of generalised Turán problems. The cornerstone of our approach is a quasirandom counting lemma for quasirandom hypergraphs, which extends the standard counting lemma by not only counting copies of a particular configuration but also showing that these copies are evenly distributed. We demonstrate the power of the method by proving a conjecture of Mubayi on the codegree threshold of the Fano plane, that any 3-graph on n vertices for which every pair of vertices is contained in more than n/2 edges must contain a Fano plane, for n sufficiently large. For projective planes over fields of odd size we show that the codegree threshold is between n/2-q+1 and n/2, but for PG(2,4) we find the somewhat surprising phenomenon that the threshold is less than (1/2-c)n for some absolute c > 0.

Marcus Appleby: The solution of many problems in quantum information—for instance, the problem of devising a measurement scheme which maximises the tomographic efficiency—is critically dependent on the geometry of the space of density matrices. For a Hilbert space of dimension 2 this geometry is very simple: it is simply a sphere. However for Hilbert spaces of dimension greater than 2 the geometry is much more interesting, and this makes the problem of devising optimal measurement schemes both difficult, and (we suspect) mathematically deep. One approach, which has been known for a long time, is based on mutually unbiased bases. However, this approach has so far only been shown to work when the Hilbert space dimension is a power of a prime number. Recently a different approach has been proposed, based on symmetric, informationally complete positive operator valued measurements (SIC POVMs). Such POVMs have been constructed numerically for every Hilbert space dimension up to 45, which suggests that they may actually exist in every dimension. However, this has not been proved. In this talk we give an overview of the problem. We then go on to present some new results obtained in collaboration with Chris Fuchs (Bell Labs) and Hoan Dang (Princeton).

Laura Hitt: I will give an overview of hyperelliptic curves in cryptography, and in particular, such curves that are suitable for pairing-based cryptography. These “pairing-friendly” hyperelliptic curves over a finite field Fq, are those whose group of Fq-rational points of the Jacobian has size divisible by a large prime, whose embedding degree is small enough for computations to be feasible, and whose minimal embedding field is large enough for the discrete logarithm problem in it to be difficult. I will construct a sequence of Fq-isogeny classes for a family of Jacobians of curves of genus 2 over Fq, for q=2m, and give their corresponding small embedding degrees for the subgroup with large prime order.

Trevor Wooley, FRS: In 1957 a race was underway, and the outcome was almost a dead heat. Consider a homogeneous cubic polynomial with rational integral coefficients. The competition was to show, assuming that the cubic has “sufficiently many” variables, that the polynomial necessarily possesses a non-trivial integral zero (and more generally, linear spaces of rational solutions). The three contestants in the photo-finish (Birch, Davenport and Lewis) applied quite different methods, and later developments demonstrated these methods to be applicable in a wider context. In this talk we discuss what can be said for the analogous problem for quintic polynomials. The methods we present are based on simple geometry, linear algebra and harmonic analysis, and should be largely accessible to those less familiar with number theory.

Artur Czumaj: We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an a-expander is a graph G = (V,E) in which every subset U of V of at most |V|/2 vertices has a neighborhood of size at least a|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time O(n1/2). We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every a-expander with probability at least 2/3 and rejects every graph that is ε-far from an a*-expander with probability at least 2/3, where a* = θ(a2/(d2 log(n/ε)) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d2n1/2 log(n/ε)/(a2 ε3)).

Nikolaos Fountoulakis: What happens to a graph when we delete some of its edges or its vertices randomly? In this talk we will study the effect of such random deletions to the typical structure of a graph that is randomly chosen from a specific class of graphs. We will show that there is a critical proportion of deleted edges (or vertices), around which an abrupt change in the typical structure of the remaining graph takes place. We will also discuss some open problems.

Rhiannon Hall: Within matroid theory, there has been much interest for some time in being able to remove elements from 3-connected matroids while remaining (almost) 3-connected. Theorems of this nature are generally known as “chain-type” theorems. Furthermore, theorems in which you remove elements, remain (almost) 3-connected and retain a specific 3-connected minor are known as “splitter-type” theorems. In this talk, we discuss a chain-type theorem for hyperplane elements and a splitter-type theorem for cocircuit elements. The talk will be aimed at a general mathematical audience with the first half hour devoted to introducing matroid theory.

Simon Blackburn: Codes with the identifiable parent property (IPP codes) are combinatorial objects that were originally used in schemes for copyright protection. There are parallels between the theories of IPP codes and error correcting codes. This talk will explore some of these connections. In particular, I'll define a prolific IPP code by drawingan analogy with perfect error correcting codes and I'll discuss a theorem that classifies linear prolific IPP codes. This is joint work with Tuvi Etzion and Siaw-Lynn Ng, completed when Tuvi was visiting the department on an EPSRC grant earlier this year.

Andrew Booker: In a 1742 letter to Euler, Goldbach conjectured that every integer at least 6 is the sum of three prime numbers. I will give some background to the problem and touch on some work in progress, joint with H. Helfgott, toward the first complete proof of the “easy” half of the conjecture.

Sebastian von Wuthenau: Baues and Peyerimhoff introduced a notion of combinatorial curvature of a corner in a tessellation and showed that a tessellation in the Euclidean plane has empty cut locus if all corners have negative combinatorial curvature. The cylinder has the same curvature as the Euclidean plane, but cylinder tessellations with negative combinatorial curvature can have non-empty cut locus. The main difference with the Euclidean plane is that the cylinder has a larger variety of paths between two faces. This allows examples with non-empty cut locus that have more sides in every face. If we want a face f in the cut locus of a face g, then the neighbours of f can be approached by geodesics starting at g following paths belonging to the different “classes of paths”, creating as few planar cycles as possible. This suggest than a generalization of this result to other surfaces or other dimensions would need to take in consideration the different varieties of paths of the surface.

Our main result for cylinder tessellations is that every cylinder tessellation satisfying at least one of the following conditions:

has the property that any finite geodesic can be expanded as a geodesic. We show that this result is sharp by providing examples of geodesics that can not be extended as geodesics in tessellations with any of the following properties:

We also conjecture a generalization of this result to other surfaces.

Daniel Appel: We briefly recall the notion of a free group F and its automorphism group Aut(F). We then introduce congruence subgroups of Aut(F). These finite index subgroups of Aut(F) arise as stabilisers in a natural action of Aut(F) on the set of epimorphisms from F onto finite groups.

The Congruence Subgroup Problem asks whether every finite index subgroup of Aut(F) contains a congruence subgroup. We present related work on the structure of certain congruence subgroups of Aut(F) and we explain some connections to classical problems concerning generating pairs of finite groups.

Leslie Goldberg: The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y — take as input a graph G, and output a value which is a good approximation to T(G;x,y). The precise formulation of the problem uses notions from computational complexity, which will be explained in the talk. Our main interest is in determining for which points (x,y) the computational problem is feasible. Jaeger, Vertigan and Welsh have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is feasible along the hyperbola (x-1)(y-1)=1 and at four “special” points. At any other fixed point (x,y), the computation is infeasible, in the sense that the problem is #P-hard. We aim to map the complexity of approximately computing the polynomial. We give several results, including a large region of intractability which includes the specialisation of the Tutte polynomial to the “flow polynomial” F(G, λ) for λ > 2. This implies, for instance, that subject to complexity-theoretic assumptions, there is no fully-polynomial randomised approximation scheme for counting nowhere-zero 6 flows, even though the corresponding decision problem can be solved in polynomial time. The talk will discuss these and other results, and will also point out open questions, such as whether there is an approximation scheme for T(G;2,0), which is the number of acyclic orientations of G. (Joint work with Mark Jerrum)

Martin Bridson: Following a brief discussion of rigidity and super-rigidity for group actions, I shall focus on actions of SL(n,Z) and explain how to prove theorems of the following type:

Theorem 1: SL(n,Z) cannot act non-trivially by homeomorphisms on a sphere of dimension less than (n-1) or a contractible manifold of dimension less than n (these being the dimensions of the standard linear actions).

Theorem 2: For every compact manifold M there exists an integer N(M) such that SL(n,Z) cannot act by homeomorphisms on M if n > N(M).

The heart of the proof involves Smith theory (which I shall explain) and an understanding of the torsion in SL(n,Z).

Kenny Paterson: Cryptography, a thriving academic discipline at the intersection of mathematics and computer science, plays an important role in securing many facets of everyday life. This talk will discuss problems that crop up when cryptography is used in the real world, beginning with Fish, an important cipher from World War II, and ending with Phishing, a modern phenomenon in which fraudsters trick victims into revealing personal information such as credit card details. It will show what cryptography can (and cannot) do for us.

Rachel Camina: We define a group theoretic criterion on a pro-p group that guarantees the existence of an analytic structure over Zp[[t]].

Wouter Castryck: This talk is about the problem of developing an algorithm that, given a curve over a finite field, outputs the number of points on it. Partly due to its cryptographical relevance, the problem has seen detailed study in the past 20 years. A complete solution still seems far off, but over finite fields of fixed (small) characteristic, already fairly large classes of curves can be handled using p-adic cohomology, by following combined ideas of Takakazu Satoh, Kiran Kedlaya and Alan Lauder. I will sketch these ideas, and summarize the state of the art in point counting, anno 2008.

Roger Heath-Brown: It is easy to show that any integer can be written as x2 + y2 - z2 in infinitely many ways. We can write 1 as a sum of three cubes (allowing negative values) in infinitely many ways. This talk will look at the number of respresentations of integers as sums and differences of three k-th powers in genereral.

Tuvi Etzion: Designs in projective spaces were defined in 1987 by Thomas. Recent interest in the area with applications in coding (by Ahlswede, Aydinian, and Khachatrian [2001]) and in cryptography (Wang, Xing, and Safavi-Naimi [2003]) drew some attention. But, the area became very active in the last year due to a recent application for error-correction in network coding given last year by Koetter and Kschischang. First, we will show that there is a strong necessary condition for the existence of designs with λ = 1, which make the existence of nontrivial or simple ones very unlikely. We continue by showing several lower and upper bounds on the sizes of error-correcting codes, which are akin to known bounds in the Hamming scheme. Interesting codes which are better than the Reed-Solomon like codes of Koetter and Kschischang will be presented. Finally, we will examine the existence of algebraic and combinatorial structure of such codes. In particular we will examine the existence of codes which form large linear spaces and codes which have complements or quasi-complements.

Louigi Addario-Berry: Joint work with Nicolas Broutin. The problem is related to searching in trees. Suppose we are given a complete binary tree (a rooted tree in which the root has degree 3 and every other vertex has degree 2) with independent, identically distributed random edge weights (say copies of some random variable X). The depth d(v) of a vertex v is the number of edges on the path from v to the root. We give each vertex v the label Sv which is the sum of the edge weights on the path from v to the root. For positive integers n, we let Mn be the maximum label of any vertex at depth n, and let M* = max {Mn: n =0,1,...}. It is of course possible that M* is infinity.

Under suitable moment assumptions on X, it is known that there is a constant A such that Mn/n → A almost surely and in expectation. We call the cases A > 0, A = 0, and A < 0 supercritical, critical, and subcritical, respectively. When A ≤ 0 it makes sense to try to find the vertex of maximum weight M* in the whole tree.

One possible strategy is to only explore the subtree T0 containing the root consisting only of vertices of non-negative weight.

With probability bounded away from zero this strategy finds the vertex of maximum weight. We derive precise information about the expected running time strategy. Equivalently, we derive precise information about the random variable |T0|. In the process, we also derive rather precise information about M*. This answers a question of David Aldous.

James McKee: This is joint work with Chris Smyth (Edinburgh). We determine all integer symmetric matrices of sprectral radius at most 2.019, and all whose Mahler measure is at most 1.3. In particular, we solve the strong version of Lehmer's problem for integer symmetric matirces: the Mahler measure is either 1 or at least “Lehmer's number” 1.17628...

David Mireles-Morales: Let C be a hyperelliptic curve given by a plane real model C: y2=F(x). Let R denote the set of principal reduced ideals in the ring C[x,y]. Every ideal in R can be assigned an integer called the distance of the ideal. The distance gives R an ‘almost group’ structure. Why R fails to be a group (or why it displays an ‘almost group’ structure) has so far not been completely understood.

In this talk we will construct a map from the infrastructure into the class group of the curve that preserves the `group-like' structure. This will allow us to give an explicit interpretation of the distance and give a precise description of why R fails to be a group. We also prove that the problem of computing the distance of a random ideal is equivalent to the discrete logarithm problem in the class group of the curve.

Peter Symonds: We consider a group acting on a polynomial ring over a finite field by linear substitutions and we want to understand the ring as a module for the group.

We consider some examples that lead to a Structure Theorem that has various interesting consequences. For example only finitely many different isomorphism classes of indecomposable summands can occur. We also obtain an a priori bound on the degrees of the generators.

Last modified: 23/02/13. Email: mark.wildon@rhul.ac.uk