A week in Vienna

Mathematics Faculty, University of Vienna

Last week, in the second week of Spring break in St Andrews, I was in Vienna, giving a course of lectures to the PhD students, at the invitation of Tomack Gilmore, a Queen Mary undergraduate now finishing his PhD with Christian Krattenthaler at the University of Vienna.

The lectures were titled “Permutation groups and transformation semigroups”, but didn’t cover everything that can be said about those topics; my aim was to present an exposition of some of the work I have been doing with João Araújo in Lisbon for the last nearly ten years. I lectured twice a day for five days, and so the course naturally fell into five parts. I assumed some knowledge of group theory, but the first day was an introduction to semigroup theory, including both standard material such as regularity and idempotent generation, the analogues of Cayley’s theorem for semigroups and inverse semigroups (the latter is the Vagner–Preston theorem), and the condition for a transformation to have a power which is an idempotent of the same rank, as well as odd extras such as the results of Laradji and Umar constructing inverse semigroups whose orders are central binomial coefficients and Bell and Catalan numbers. The second day was an introduction to the theory of permutation groups, with the basic reductioin theorems as far as the O’Nan–Scott theorem, and a very brief discussion of multiply transitive groups.

The third and fourth days were the heart of the course. Day 3 covered synchronization: the Černý conjecture, the characterisation of non-synchronizing semigroups in terms of graph homomorphisms, the definition and basic properties of synchronizing permutation groups. Day 4 concerned conditions on a permutation group G which guarantee that, for any map s of given rank k, the semigroup generated by G and s, with the elements of G removed, is regular or is idempotent-generated. The condition for the first is the k-universal transversal property of G (that, given any k-set A and k-partition P, there is an element of G mapping A to a transversal for P. This condition is necessary for idempotent-generation of the semigroup (it is necessary and sufficient for the existence of an idempotent with rank equal to that of s), but not sufficient. In general we do not have a combinatorial equivalent of idempotent generation, but in the case k = 2 we do: it is the road closure property, which I have discussed here before.

The final day dealt with miscellaneous topics: automorphisms of transformation semigroups, lengths of chains of subgroups or sub-semigroups, and separating permutation groups. The notes also include a bibliography of books and papers as well as a number of open problems. (The notes are here.)

Doing all this in a week would have been challenging enough, but as well I gave a 90-minute seminar talk on orbital polynomials, a colloquium on the random graph, and a “junior colloquium” on the ADE affair. So quite a busy week, and I am afraid that other jobs had to be put on hold temporarily.

With all this there was not a great deal of time to see Vienna. Though it was early spring, the weather at the weekend was not kind, cold and rainy, though during the week it was better, and the blossom had come out by the time we left.

Academy of Fine Arts

So much of the sightseeing was indoors. I will mention just the most astonishing thing I saw. Among other galleries, we went to the Academy of Fine Arts (part of the outside is shown above). The picture gallery in the Academy has the famous tryptich on the Last Judgment by Hieronymus Bosch. We think of his work as being mostly either of people doing unspeakable things to each other in gardens, or demons doing unspeakable things to people in Hell; this one certainly has plenty of that, with toads frying sinners in large frying pans or stirring them up in cooking pots. But the real surprise for me was on the back. The tryptich was hung with the side panels folded very slightly forward so that, with care, you could see the painting that would be shown if the panels were closed. This was completely different. The left-hand panel showed St James on a pilgrimage (probably to Santiago de Compostela), taking up most of the panel. He was dressed in dull blue robes and the mountainous landscape behind was in very subdued blue-grey, and the image looked forward to a later period of painting, being an astonishing portrait, of whom I don’t know. The right panel depicted a saint from Ghent giving alms to the poor, in even more subdued style.

The Danube has four branches in Vienna, three of which I saw: the regular river, the old, the new, and the Donaukanal. The last of these is not a canal, nor an open sewer (the meaning of German kanal according to Wikipedia), but a branch which has always existed and was “controlled” in 1598. Unlike the main river, it flows near the centre of town. I don’t know the story of the Alte Donau, which seems to be disconnected now and consist of a series of lakes. The Neue Donau was built for flood control after a serious flood in 1954, though it took a while to reach the decision to build it; work began in 1972 and was finished in 1988. Between the Donau and Neue Donau is a long, straight, and very thin island (which no doubt is crowded in the summer, but when we were there everything was closed and there were only a very few joggers and cyclists to be seen; a sad look to everything).

Danube Island

Posted in events, Lecture notes, Uncategorized | Tagged , , , , , , , , | 2 Comments

A scary evening

Tommy Flowers

The picture is of Tommy Flowers, who built Colossus, the first computer. It was built to break the German High Command’s Fish cipher (Sägefisch) in the second world war; its construction would be regarded as heroic or despicable depending on which side you were on, I suppose. Nowdays, some similar uses of computers completely lack the heroic element: more on this below.

The picture hangs in the headquarters of the Institution of Engineering and Technology (formerly the IEE) in Savoy Place in London, just off the Embankment near Waterloo Bridge. We were there for a public lecture, the Stevenson Science Lecture, put on by Royal Holloway University of London. The series has been running for the best part of a century; but this was the first time it had been held in London, despite the University’s name (it is actually in Surrey).

The title of the lecture was “Should I have just clicked on that?” – quite scary when emails came about changes in the timing – and it was a triple act, put on by Lorenzo Cavallaro and Stephen Wolthusen from the School of Mathematics and Information Security and Marco Cinnerella from the Psychology Department. (Note that two out of three are among those being used as bargaining counters by the despicable Theresa May.) It was a polished performance; it was clear that time and thought had been put into the sequencing.

As the title suggests, there was quite a bit about phishing and ransomware emails. They pointed out that now you don’t even have to click on a link to suffer the penalty: if you use the autoplay setting on Facebook (whatever that may be), by the time the video of fluffy kittens starts playing the malware has already been downloaded onto your computer. But a lot of people click on ill-advised links because their attention isn’t fully engaged; as Marco put it, they haven’t “throttled up” their brains. I think that Julian Jaynes would say that we live much of our lives unconsciously; things only come into consciousness if they are significantly different from usual. But maybe psychologists don’t like talking about the unconscious these days: Freud gave it a bad name.

So why do they do it? Just business. You don’t even need infrastructure. Twenty dollars’ worth of computer time from Amazon is enough to crack the average password, and then you can earn much more than your investment by installing malware, using the computer for DDOS attacks, or simply selling on the information to those who will use it. Also, many permissions nowdays are transitive, so even if you haven’t explicitly given your login details to some organisation, they have had it passed on from someone you did give it to, quite legitimately. (So yes, choosing secure passwords is important!)

There are even more worrying things. A modern car has an order of magnitude more computer code in it than a Dreamliner; a program that large is bound to have weak points which can be attacked. Moreover, the car is connected to the internet, both for the satnav and for the infotainment system. It seems that the steering wheel, accelerator and brake pedals are not mechanically connected to the front wheels or the engine respectively; when you turn the wheel or put your foot on the pedal, you are telling the computer that you want something to happen, and it is the computer’s job to do your bidding. But, if control of the computer has been taken over by an outsider, it may be given an instruction to turn the front wheels when you are travelling at high speed down the motorway. This is said to be a very efficient way of getting rid of enemies, and may already have been used for this purpose.

How do we avoid these things? Well, my shoes are not yet connected to the internet, so I am probably safe walking to work. But as for keeping your computer safe, part of the problem is that different cultures take very different attitudes to imposed security measures. Some regard them as simply something to be got around by ingenuity. In some cultures, when a security investigator interviews staff about their working practices, people will say what they think he wants to hear rather than what they actually do. I think we simply have to try to be a little more conscious of what we are doing when at the computer (and at other times too).

Posted in events | Tagged , , , , , , | 2 Comments

The ADE affair, 6

Earlier this semester, we had a beautiful seminar by Pierre-Philippe Dechant, whose work has thrown some entirely new light on this beautiful work of art. I would like to explain a bit about this here. For more details, see his papers, for example,

  • Pierre-Philippe Dechant, A 3D spinorial view of 4D exceptional phenomena, in Symmetries in Graphs and Polytopes (ed. J. Širáň and R. Jaycay), Springer, 2016, pp. 81-95.
  • Pierre-Philippe Dechant, The E8 geometry from a Clifford perspective, Advances in Applied Clifford Algebras (2016).
  • Pierre-Philippe Dechant, The birth of E8 out of the spinors of the icosahedron, Proc. Roy. Soc. (A) 472 (2016).

Pierre has done much more than simply add to the literature on the ADE affair. As he puts it in one of his papers,

[The] Lie-centric view point of much of theoretical physics … has unduly neglected the non-crystallographic groups.

Some of his work is well outside pure mathematics, on viruses which have icosahedral symmetry, of which there are many. Why? I never really thought about this before. But a virus has only a tiny amount of genetic material compared to us, and has to reproduce itself using components which are very simple to specify and to assemble: making an icosahedron out of triangles is a good solution to this problem!

The story so far

The ADE affair refers, loosely, to mathematical classification problems where the answer is “two infinite families and three isolated examples”. These come in two main flavours:

  • Root systems (with all roots of the same length) and related things such as root lattices, Lie algebras, and cluster algebras: the root systems are of type An, Dn, E6, E7 and E8.
  • The 3-dimensional finite rotation groups, and associated reflection groups: the rotation groups are the cyclic and dihedral groups together with the three groups of the regular polyhedra (tetrahedron, octahedron/cube, and icosahedron/dodecahedron).

The relation between the two flavours had been known for some time, but a precise form of it was given by John McKay, who pointed out that the extended Coxeter–Dynkin diagrams associated with the simple Lie algebras coincide with the representation graphs of the binary groups (the double covers of the 3-dimensional rotation groups, pullbacks under the two-to-one isomorphism from the 2-dimensional unitary group to the 3-dimensional orthogonal group).

Precise it may be, but it is rather inexplicit and lacking in explanatory power. Can we do better?

Clifford algebras

We are dealing here with real Clifford algebras; the complications in characteristic 2 will not affect things.

Pierre Dechant describes a Clifford algebra as a kind of deformation of the exterior algebra by a quadratic form.

The exterior algebra is the largest anticommutative algebra generated by a given vector space V. That is, it is spanned by all products e1∧…∧er, where e1, … er are chosen from a basis for V. The anticommutative law wv = −vw, and its consequence vv = 0, imply that we can start with an ordering of the basis and take e1, …, er in increasing order. So the dimension of the exterior algebra is equal to the number of subsets of the basis, that is, 2n if dim(V) = n.

Now suppose that there is an inner product · on V. The Clifford algebra has the same underlying vector space as the exterior algebra, but the multiplication is given by

vw = v·w+vw

on V, extended to the whole algebra. The symmetric and antisymmetric parts of the product are given by the inner product and exterior product, and can be recovered from the Clifford algebra product.

Reflections on V have a particularly simple form in the Clifford algebra; the reflection in the hyperplane perpendicular to a is the map taking v to −ava. Note that the reflections defined by a and −a are the same, so that the group they generate in the Clifford algebra is a double cover of the reflection group they generate on V. The entire group generated by these maps on the Clifford algebra is the Pin group of v, and the corresponding cover of the special orthogonal group (consisting of products of even numbers of reflections) is the Spin group.

So the 120 elements of the group H3 of rotations and reflections of the icosahedron give us 240 elements of the 8-dimensional Clifford algebra; these are, amazingly, the roots in the root system E8.

And more …

There is much more to say, though I won’t say it right now; I might try to persuade Philippe to write it up himself at some point.

For example, the 8-dimensional Clifford algebra is a direct sum of even and odd parts, each 4-dimensional; there is a folding of the E8 root system onto H4 in 4 dimensions. There is also a process called spinor induction which lifts from spinors on 3-space to vectors in 4-space. The correspondence works for other root systems and reflection groups too, forming a 3×3 array, which (row by row) looks like

(A3, B3, H3) → (D4, F4, H4) → (E6, E7, E8).

For now I simply say: Take a look at Philippe’s papers if you want more of this story!

Posted in exposition | Tagged , , , , , , , | Leave a comment

Conference announcement

Poster

The organisers have asked me to advertise this event, which I am happy to do The closing date for reduced rate registration is at the end of March. Please think about coming!


Conference in honour of Peter Cameron / abstract submissions

Please join us in Lisbon to honour and celebrate the mathematical achievements of Peter J. Cameron from the 24th to the 27th of July, 2017. The deadline to register at a reduced rate is approaching fast (the end of March).

Attached to the conference, on the 28th July 2017 and in the same place, there will be a satellite workshop

Symmetry in Finite and Infinite Structures

for which the submission of abstracts is welcome (in combinatorics, groups, logic, semigroups or statistics).

More details can be found at:

http://cameron17.campus.ciencias.ulisboa.pt/

The invited speakers of the main conference include: Laszlo Babai, Rosemary A. Bailey, Wolfram Bentz, Robert Calderbank, Peter J. Cameron, Gregory Cherlin, Persi Diaconis, Cameron Freer, Michael Giudici, Robert Gray, Alexander, Hulpke, Gareth Jones, Michael Kinyon, Dimitri Leemans, Henrique Leitão, Dugald Macpherson, António Malheiro, Francesco Matucci, John Meakin, James D. Mitchell, Peter M. Neumann, Jaroslav Nesetril, Peter P. Pálfy, Cheryl E. Praeger, Colva Roney-Dougal, Ben Steinberg, Pedro Silva, Leonard, H. Soicher, Pablo Spiga, Misha Volkov and Boris Zilber.

A larger version of the poster of the conference is available here. Please distribute it to friends and colleagues.

The organising committee

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Not what it seems

There are many outstanding books explaining the latest developments at the frontiers of theoretical physics to general audiences. This is not an easy thing to do, but the physicists who have stepped up tend to be very good writers and expositors: I am thinking of people like Roger Penrose, Julian Barbour, and Lee Smolin.

The latest such book that I have read is Carlo Rovelli’s Reality is not what it seems, published (in English translation) by Allen Lane last year.

In brief, what distinguishes this book is that the author’s research is in loop quantum gravity, one of the more successful approaches to quantum gravity, and his feeling is that this approach has been successful so far. (Of the other main contender, string theory, whose main concern, he says, “is not so much studying the quantum properties of space and time, but rather writing a unified theory of all known fields, an objective that might be premature given current knowledge”.

There are chapters devoted to classical physics (Newton), special and general relativity (Einstein), and quantum mechanics (Einstein again, Heisenberg, Dirac), before we come to the viewpoint he proposes, that space and time are not fundamental properties of the universe, but emerge from quantum processes on a very small scale.

But the book has a couple of features that distinguish it from the average popular physics book.

First, the endeavour is traced back to the journey of Leucippus from Miletus (then the centre of Greek philosophy, with Thales, Anaximander, Hecataeus, and others) to Abdera in about 450BCE. There, he found a disciple, Democritus, and together they developed the philosophy of atomism. Crudely, this says that the world is made of atoms and the void, and the achievement of quantum gravity is to get rid of the void. But there is much more to it: the philosophy of these two was based on the notion that “the world can be comprehended using reason”, and science has no need to appeal to the authority of gods or ancient texts. Atomism was also a richer theory than is often portrayed: Democritus regarded atoms as like letters, which can be combined so as to obtain “comedies or tragedies, ridiculous stories or epic poems”. Incidentally, atomism resolves Zeno’s paradox of Achilles and the Tortoise: if space is not infinitely divisible, the paradox simply does not arise.

Democritus was extremely prolific, but almost all his works have been lost. (Rovelli lists them in a footnote which takes up the best part of an entire page.) What we know of his thought is almost all contained in the poem De rerum natura by the Latin poet Lucretius. Rovelli speculates on what might have happened if we had retained the work of Democritus and lost that of Plato and Aristotle.

The second feature is that Rovelli is not afraid to write down equations, not accepting the “wisdom” that every equation halves the sales. Figure 7.7 is a schematic picture of a T-shirt with the equations of loop quantum gravity on it (though I don’t think he expects most readers to understand them: the point is that the formulation is concise and elegant). Other equations are more important to the flow of the argument.

For example, he tells the story of Matvei Bronštein, the Soviet physicist who first showed that general relativity and quantum mechanics, taken together, show that there is a smallest scale of length. The argument goes like this. Suppose we want to measure a small region of space. We must place something in this space in order to identify it. The finer our measurement, the more confined the particle is. According to the Uncertainty Principle, this implies more uncertainty in its momentum, and hence (I will come back to this) in its energy. Special relativity shows that energy is equivalent to mass, and general relativity that mass bends spacetime; so a sufficiently energetic particle in a small region of space will produce a black hole, and our proposed measurement will become impossible. Rovelli remarks that the argument is much more precise and general than indicated, and leads to a calculation of this minimal length (now called the Planck length) in terms of the gravitational constant, Planck’s constant, and the speed of light. The equation is at the top of page 130.

My caveat is that, except for zero-rest-mass particles like photons, the energy is not determined by the momentum. I am not sure how to get around this.

Rovelli goes on to tell the fate of Bronštein. When Stalin came to power, he (and other physicists) who had followed Lenin, were mildly critical of Stalin; Bronštein was arrested and condemned to death, and executed on the same day. Let us all hope that such things are not going to return in our lifetime!

The main message of the book, then, is that everything, even space-time, is “granular”; infinity does not exist in nature. This view disposes of the infinities that have troubled physics, which result from the possibility of things becoming arbitrarily close (for example, a point charge interacting with itself).

As I said earlier, Rovelli gives the impression that loop quantum gravity has provided us with a workable basis for the union of relativity and quantum theory. But, like Democritus, he realises that we are not at the end of the journey. Signs from these and other investigations suggest that the basic currency of the universe might be, not space-time, but information; time might arise from the entropy of the small-scale structure. But he admits that he doesn’t know how this might work. A refreshing view after the premature announcement of the “theory of everything” a couple of decades ago.

Posted in books | Tagged , , , , , , , | 1 Comment

Algebraic properties of chromatic polynomials, 2

My paper with Kerri Morgan on algebraic properties of chromatic roots (described here) has just appeared in the Electronic Journal of Combinatorics: you can find it here.

I won’t say any more about it, except to pose a challenge which we were unable to solve. We found graphs for which the Galois groups of irreducible factors of the chromatic polynomial include all transitive groups of degree at most 4, and all of degree 5 with a single exception; for larger degree, the gaps become wider and wider … So here is the challenge:

Is there a graph whose chromatic polynomial has an irreducible factor with Galois group cyclic of order 5? [Preferably the chromatic polynomial should be a product of this factor and n−5 linear factors.]

Posted in open problems, Uncategorized | Tagged , , | 2 Comments

Polynomials taking integer values

This is not a hot new result, just part of general mathematical culture.

If a polynomial f(x) has integer coefficients, then its values at integer arguments are clearly integers. The converse is false; the simplest example is the polynomial x(x−1)/2.

Also, if a polynomial vanishes at infinitely many different arguments, then it vanishes everywhere. But it is not true that a polynomial which has integer values at infinitely many integer arguments takes integer values at all integer arguments. The simplest counterexample is x/2.

On the other hand, we might often be in the situation where we know that a polynomial takes integer values at all positive integers (for example, because it counts something). Does it follow that it takes integer values at all integers?

This is on my mind as a result of thinking about reciprocal polynomials, as described in a recent post. The cycle polynomial of a permutation group, divided by the group order, takes integer values at positive integers, since it counts something; if a reciprocal polynomial is to have the same property, then the original polynomial should take integer values at negative integers as well.

The answer is yes. If you haven’t thought about this before, please do so now before reading on.

Here is the outline of a simple argument for a more general fact:

If a polynomial of degree n takes integer values at n+1 consecutive integer arguments, then it takes integer values at all integer arguments.

Clearly by translation we may assume that f(0), f(1), …, f(n) are integers. Our proof is by induction on n; starting the induction at n = 0 is immediate. If f has degree n and satisfies the hypothesis, let g be the difference polynomial defined by g(x) = f(x+1)−g(x). Then g has degree n−1 and takes integer values at 0, 1, … n−1; so it takes integer values at all integer arguments, from which we see that the same is true for f.

Richard Stanley, in his celebrated book, gives the very nice representation theorem for such polynomials. The polynomial g in the preceding proof is the first difference polynomial of f; inductively one can define the ith difference polynomial for any i. Now the result is:

Let f be a polynomial of degree n taking integer values at all integers. Then f(x) is an integer linear combination of the “binomial coefficient” polynomials {x choose k}, for k = 0,…n; the coefficient is the kth difference polynomial evaluated at 0.

Of course, this theorem, lovely though it is, is not the most efficient representation in all situations. For example, if n is even, say n = 2m, then (x2m+xm)/2 is the cycle polynomial of the group consisting of the identity and a fixed-point-free involution (divided by the group order); I don’t know how to write it in terms of binomial coefficients.

Posted in exposition | Tagged , , , | 4 Comments