Two of our final year undergraduate students, Xenia Dimitrakopoulou (BSc Mathematics with Economics) and Justin Tan (BSc Mathematics and Economics), give Maths@LSE an insight into the LMS Summer School they attended in July.

The London Mathematical Society organises undergraduate summer schools every summer, consisting of a two-week course held in a UK university. The summer school consists of short lecture courses which include problem-solving sessions as well as colloquium-style talks.

This year, the LMS Undergraduate Summer School was hosted by the University of Glasgow, and the two of us were fortunate to have had the opportunity to attend it. The programme consisted of six short lecture courses (three lectures and two exercise sessions each) and eight colloquia. We have selected four of the lecture courses to discuss below.

The Compactness Theorem by Professor Mike Prest (University of Manchester)

The first lecture series, on the Compactness Theorem, was given by Professor Mike Prest from the University of Manchester. After providing us with an introduction to ultrafilters and ultraproducts, he used Zorn’s lemma to prove the existence of a maximal ultrafilter containing any given filter. He defined (diagonal) embeddings, Łoś’s theorem, structures and definable sets and we proved the Compactness Theorem. Finally, a sketch proof of Łoś’s theorem followed. What we found particularly interesting about these lectures was how abstract algebra was used to prove such a fundamental result in predicate logic. Since neither one of us had ever taken such advanced courses in either field, we were fascinated by the challenging material and the highly demanding problem sets.

The Word Problem in Combinatorial Group and Semigroup Theory by Dr Robert Gray (University of East Anglia)

This lecture course focused on a question in combinatorial group and semigroup theory called the word problem.

Here we look at the word problem in the specific context of rewriting systems only. Consider a set of letters A={a,b}. Then words generated by this set are any finite sequence of letters in this set, such as 1 (the empty set which contains no letters), a, b, aa, aba, bbbaaaaabb, etc. To form a rewriting system (A,R), the set of letters is paired with a set of rewriting rules (call this R) that allow us to replace a word with another in the forward direction. For example, the rewriting rule aab allows us to state that baabbbb, bbaabbb and abaaaababaabbabbbb (we simply replaced aa with b). In this case, the words baab and bbaa represent the same element in this rewriting system since they can be transformed to each other using the rewriting rules. Our notation for this rewriting system would then be (A,R)=({a,b},{aab}).

A rewriting system has a decidable word problem if there is an algorithm which for any two words in the system decides whether or not they represent the same element in the rewriting system. In other words, is it possible to write a set of instructions such that for any two words, we can determine whether these two words can be rewritten into each other or some common word?

A rewriting system is noetherian if there is no infinite descending chain with the rewriting rules defined as reductions. The rewriting system ({a,b}, {ab}) is noetherian because for any word, taking the reduction ab, we can only replace a with b (remember that rewriting rules only apply in the forward direction in this context), so the number of a’s keeps decreasing (bounded below by 0), and there cannot be an infinite descending chain (i.e. at some point we cannot reduce further). For example, aabbababbababbbbbbbb. The rewriting system ({a,b},{ab,ba}) is not noetherian since ababab→… is an infinite descending chain (we can just keep alternating between the two rules forever). Another example of a non-noetherian rewriting system is ({a},{aa2}).

A rewriting system is confluent if whenever a word has two or more options for reduction (by applying two different rules or applying the same rule at two different positions), there is a word that both products can eventually be reduced to. The rewriting system ({a,b}, {ab}) is also confluent because with any word, our only option is to replace a with b, and the order in which we do this does not matter. For example, aaabbb and also aababb (note that the first reduction is done differently, but we reach bb in both cases). The rewriting system ({a,b,c},{ab,ac}) is not confluent since ab and ac (we have two options to reduce the word a), but we cannot apply any sequence of rules so that b and c are reduced to a common word (since there are no rules that act on b or c).

A theorem states that if A and R are both finite, and (A,R) is both noetherian and confluent, then (A,R) has a decidable word problem. Given any two words in the rewriting system, a simple word problem algorithm would be to reduce both of them until they can no longer be reduced (we know that this can be done, since by the noetherian property there are no infinite descending chains), and then check whether these two irreducible words are the same (a word is irreducible if no rewriting rule can be applied on them).

This is merely a small part of the word problem, which can be studied with various other approaches. In the short lecture course, we also looked at approaches using Cayley graphs (shown in the picture below) as well as one-relator groups.

Optimal Transport Theory by Dr David Bourne (University of Durham)

Gaspar Monge’s problem is the problem of moving a pile of sand to form an embankment. Which grain in the pile shall we move to which part of the embankment for maximum efficiency? This depends on how we measure efficiency. We consider the cost function c(s), where s is the displacement when moving each particle. If the cost function is convex (for example, s^2), it makes sense to translate (minimising the sum of squares of the distances moved for each particle)); if the cost function is concave (for example, |s|^0.5), it makes sense to flip (minimising the sum of square roots of the distances moved for each particle).

This led us to draw parallels with what we learnt in microeconomics, in the sense that our optimal household bundle depends on the characteristics of our utility function, and convex and concave utility functions lead to ‘opposite’ optimal bundles.

Local-Global Principles in Number Theory by Dr Shaun Stevens (University of East Anglia)

The lecture series presented a variety of theorems and lemmas aiming to help us understand the “local-global” question: if f has a root in R and in Qp, for all p, does then f have a root in Q? These lectures introduced us to beautiful ways analysis and abstract algebra are used to tackle a variety of number theoretic problems. The material in this lecture series was difficult (almost driving one of the authors to give up on math completely), and we discuss below one of the more interesting results (using field extensions).

For a field Q and a prime p, we defined a nonarchimedean value | |p.   Afterwards we proved the following two theorems:

Now, recall that a sequence ( xn)  is Cauchy if  , and that a metric space is complete if every Cauchy sequence converges.

Also, we say that a subset A of a topological space X is dense if if every point x in X either belongs to A or is a limit point of A.

*The above theorems allowed us to extend any field Q to a field Q, such that together with a nonarchimedean valuation | |p , Qcontains Q and:

  1. Qp is complete; and
  2. Q is dense in Qp.

Now,  | |p   in Q satisfies the first two theorems and together with (*) we get the following mind-blowing result:

To conclude, don’t tell the first year but the p-adic world is actually much nicer than the real one!

Final Thoughts

The University of Glasgow has a beautiful campus set in a historic town. We thoroughly enjoyed exploring the university and other sights in Glasgow. The LMS Summer School exposed us to exciting areas of mathematics which we would not normally learn in school, and motivated us to continue learning and deepening our mathematical knowledge.

Anyone who wants to explore the material further can check out the programme web page or email the authors at x.dimitrakopoulou@lse.ac.uk or j.tan18@lse.ac.uk.