RHUL Mathematics Seminar

Peter Keevash: A hypergraph regularity method for generalised Turán problems
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₂(4) we find the somewhat surprising phenomenon that the threshold is less than (1/2-c)n for some absolute c > 0.

Marcus Appleby: Geometrie and Measurement
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: Hyperelliptic Curves in Cryptography
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 F_q, are those whose group of F_q-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 F_q-isogeny classes for a family of Jacobians of curves of genus 2 over F_q, for q = 2m, and give their corresponding small embedding degrees for the subgroup with large prime order.

Trevor Wooley, FRS: A singular approach to solving quintic equations
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: Testing expansion in bounded-degree graphs
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(n^1/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^★ = θ(a²/d² 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(d²n^1/2 log(n/ε)/(a²ε³)).

Nikolaos Fountoulakis: Percolation on random graphs with a given degree sequence
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: A chain-type theorem for hyperplanes and a splitter-type theorem for cocircuits
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: Prolific IPP Codes
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: Vinogrodov's three primes revisited
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: Geodesics in surface tessellations with bounded combinatorial curvature
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:

• (a) Each face has at least 5 sides and each vertex has valency at least 4,

• (b) Each face has at least 9 sides, 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: (a) Each face has at least 4 sides and each vertex has valency at least p, for any positive integer p; (b) Each face has at least 8 sides. We also conjecture a generalization of this result to other surfaces.

Daniel Appel: Congruence subgroups of the automorphism group of a free group
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: Inapproximability of the Tutte polynomial
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: Dimension rigidity for group actions
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: From Fish to Phishing
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: Recognising Z_p[[t]]-analytic pro-p groups
We define a group theoretic criterion on a pro-p group that guarantees the existence of an analytic structure over Z_p[[t]].

Wouter Castryck: Effectively determining the number of points on curves over finite fields
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: Sums and differences of three kth powers
It is easy to show that any integer can be written as x²+y²-z² 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 kth powers in general.

Tuvi Etzion: Designs and Coding theory in projective space
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: Killed random branching walks
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 S_v which is the sum of the edge weights on the path from v to the root. For positive integers n, we let M_n be the maximum label of any vertex at depth n, and let M^★ = max {M_n : 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 M_n/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 T₀ 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 |T₀|. In the process, we also derive rather precise information about M^★. This answers a question of David Aldous.

James McKee: Integer symmetric matrices of small spectral radius and small Mahler measure
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: A geometric interpretation of the infrastructure of a real function field
Let C be a hyperelliptic curve given by a plane real model C : y² = 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: Group actions on polynomial rings
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.