British Mathematical Colloquium, day 2

Things may be a bit briefer from now on.

The first plenary talk was by Irit Dinur on the unique games conjecture. I think I understood roughly what this conjecture says, but what it has to do with games, unique or otherwise, still escapes me completely.

Some NP-hard problems are constraint satisfaction problems; examples include 3-COL (is a given graph 3-colourable?) and 3-SAT (is a conjunctive normal form formula where each clause has 3 literals satisfiable?) In each case, if the answer is no, we could ask what is the largest fraction of constraints which can be satisfied. For example, with 3-SAT, there is one constraint for each clause. By assigning Boolean values randomly to the literals, we see that seven of the eight assignments to each clause will make it true, and so the expected number of satisfied clauses is at least a fraction 7/8 of the total. In the same way, an edge gives a constraint on a colouring (its ends must have different colours), and so a random colouring will have at least 2/3 of the edges properly ccoloured.

The PCP-theorem says that there exists a positive δ such that it is NP-hard to distinguish betweem “all constraints satisfied” and “a fraction smaller than 1−δ of constraints satisfied.

The unique games conjecture says something about a particular kind of CSP called “label cover with 1:1 constraints”, asserting that it is hard to distinguish between fraction ε and 1&mimus;ε of constraints satisfied. The breakthrough result is this with the upper value replaced by (1/2)−;ε. This has a lot of consequences in related areas of complexity, but for fear of getting things wrong I will say no more.

After that, there was a wonderful talk by Clifford Cocks on the history of public-key cryptography. James Ellis at GCHQ had discovered the principles of public-key cryptography in 1969, and Cocks, arriving shortly afterwards, had constructed a practical scheme for doing it, almost identical with what we now call RSA (although technology wasn’t able to do the business until the 1980s); a later arrival, Malcolm Williamson, discovered another method, almost precisely the same as Diffie–Hellman key exchange.

On the other side of the Atlantic, Whitfield Diffie gave up his job in 1972 to learn about cryptography, and began working with Martin Hellman in 1974; by 1976 they had laid down the principles of PKC and had discovered Diffie–Hellman key exchange. Rivest, Shamir and Adelman read their paper and got to work; Rivest and Shamir tried many ideas, Adelman knocked them all down, until they came up with the RSA method. In one respect the Americans had advanced beyond the British; Diffie and Hellman realised the importance of authentication, and had discovered a method for providing it.

Having had a morning of computer-related things, I missed Mike Fellows’ talk on parameterized complexity, and listened instead to Marta Mazzocco on the geometry of the q-Askey scheme. This is a huge mountain, whose lower slopes on one side I have wandered among; Marta was approaching from the other side, and I am afraid that the landscape was almost completely unfamiliar to me. The q-Askey scheme is a poset with 29 boxes, each containing a type of orthogonal polynomials, with Askey–Wilson and q-Racah at the top. She talked mostly about the left-side, and I realised that the polynomials I am more familiar with, such as Krawtchouk and Hahn, were all on the other side. Her talk was full of discrete versions of Painlevé equations (six important families of non-linear differential equations), and was described by “chewing gum moves” on a certain Riemann surface; she has a duality which produces new information.

At lunchtime the rare books collection had put on a very nice exhibition, with works of (among many others) Pacioli, Fermat, Gauss, and Mary Somerville (who grew up in Burntisland).

After lunch, Nalini Joshi talked about building a bridge (motivated by the famous Harbour Bridge in her hometown Sydney) between apparently unrelated works by Japanese and European mathematicians. The talk began slowly with root systems and reflection groups, but picked up speed; I don’t feel competent to explain much of it, I’m afraid.

Then, not entirely by design, I found myself in the Algebra workshop. Tim Burness began with a talk on the length and depth of finite groups. The length of a finite group is the length of the longest chain of subgroups of the group. This is something I am interested in; in the early 1980s I found a beautiful formula for the length of the symmetric group S_n: take 3n/2, round up, subtract the number of 1s in the base 2 expansion of n, and subtract 1 from that.

The length has many nice properties; it is monotonic, and additive over composition factors. Tim has defined another parameter which he calls the depth, which is the minimum length of an unrefinable chain of subgroups (that is, each one maximal in the next). This failse these nice properties, and behaves very differently from length. For example, the depths of finite symmetric groups are bounded above by 24; the nice proof of this uses Helfgott’s proof of the Ternary Goldbach conjecture! But the depth of all finite simple groups is not bounded above. They have some results for algebraic groups as well (where the subgroups in the chain are restricted to be closed and connected).

Some of my colleagues are interested in something called the partition monoid. Maud de Visscher talked about the partition algebra, a slightly twisted version of the monoid algebra of the partition monoid. This arose in statistical mechanics; they have used it in representation theory, to get a better understanding of certain numbers called Kronecker coefficients arising from diagonal actions of symmetric groups on tensor products of Specht modules.

Finally, Marianne Johnson showed that the 2-variable identities of the bicyclic monoid (with two generators p and q satisfying the relation pq = 1) are identical to those of the 2×2 upper triangular matrices over the tropical semiring. A lovely and unexpected result!

The last event of the day was speed talks by PhD students, but your correspondent’s brain was full, so I cut this session.