Abel Prize 2020

Congratulations to Gregory (Grisha) Margulis and Hillel (Harry) Furstenberg on being awarded the 2020 Abel Prize. The prize is one of the most prestigious in mathematics and is presented annually by the Norwegian Academy of Science and Letters.

The official announcement states that Margulis and Furstenberg were awarded the prize “for pioneering the use of methods from probability and dynamics in group theory, number theory and combinatorics” and their work is described by Hans Munthe-Kaas, chair of the Abel committee, as “bringing down the traditional wall between pure and applied mathematics”. So, who are they?

Gregory Margulis

Born in Moscow in 1946, Margulis gained international recognition aged only 16 when he received a silver medal at the International Mathematical Olympiad. He began his academic career at Moscow State University and began working towards his PhD under the supervision of 2014 Abel Prize Laureate Yakov Sinai. At the age of 32, he was awarded the 1978 Fields Medal for his work on the ‘arithmeticity and superrigidity theorems’, but was unable to travel to Finland to receive the medal as the soviet authorities refused to provide him with a visa.

Another major result followed in 1984 with his proof of the Oppenheimer Conjecture – a problem in Number Theory first stated in 1929. The ideas he introduced here centred on what is known as ‘ergodic theory’ (more on this later), and have since been used by three recent Fields Medallists: Elon Lindenstrauss, Maryam Mirzakhani and Akshay Venkatesh. In 2008, Pure and Applied Mathematics Quarterly ran an article listing Margulis’s major results which ran to more than 50 pages.

IMG_20190924_203021

Hillel Furstenberg

Originally thought to be a pseudonym for a group of mathematicians due to the vast range of ideas published in his early work, Furstenberg is a mathematician with a deep technical knowledge of countless areas of mathematics. He published his first papers as an undergraduate in 1953 and 1955, with the latter giving a topological proof of Euclid’s famous theorem that there are infinitely many prime numbers.

One of his key results came in 1977 when he used methods from ergodic theory to prove a celebrated result by 2012 Abel Prize Laureate Endre Szemerédi on arithmetic progressions of integers. The insights that came from his proof have led to numerous important results, including the recent proof by Ben Green and Terence Tao that the sequence of prime numbers includes arbitrarily large arithmetic progressions.

Screenshot 2020-03-24 at 15.36.43.png

So, what is ergodic theory?

Ergodic theory relates to probability and what we call ‘random walks’, best explained by thinking about a dog trying to find some treats buried in a garden…

If you hide some treats in your garden and let your dog try to to find them, it will most likely start sniffing in what seems to be an apparently random pattern. However, after a short period of time, the dog will more often than not successfully find the treats. This method of search might not seem to be systematic, but yet the dog is following its instinct telling it to randomly change its direction at regular intervals to maximise its chance of success. You can think of it as moving one step forwards, then flipping a coin to decide whether you next go left or right for one step, and repeating this indefinitely.

In maths, the dog’s behaviour is encoded in the concept of a random walk. A random walk is a mathematical object that describes a path consisting of a succession of random steps in some mathematical space. There are numerous examples of physical systems that are modelled by random walks: the behaviour of gas molecules, stock markets, the statistical properties of neurons firing in the brain… But, random walks can also be seen as a tool to explore a mathematical object, in the same way that the dog tries to understand the garden. Of course, Hillel Furstenberg and Gregory Margulis are not using random walks to find treats in a garden, they do random walks on graphs or on groups in order to reveal the secrets of these objects.

If the trajectory of the dog is ergodic, this means that the dog will eventually get close to the treat in the long term. In fact, if we were to draw a circle around the treat, of any size (even as small as you can possibly imagine), after some finite amount of time the dog will be sniffing inside the circle, and therefore will probably discover the treat. This is ergodic theory in a nutshell.

More information on the Abel Prize announcement can be found on the website of the Norwegian Academy of Sciences and Letters here or in the official citation here.

Brian – 1st year Maths

First year St John’s Maths student Brian discusses his favourite areas of undergraduate Maths (featuring a famous sequence) and his plans for a future career in Data Science. Produced for the SJC Inspire Programme.

What’s your type? The Maths behind the ‘Qwerty’ Keyboard

The maths behind the most unshakeable technology of the 20th century

Martha Bozic

In 1867, a newspaper editor in Milwaukee contemplated a new kind of technology. He had previously patented a device which could be used to number the pages of books but, inspired by the suggestions of fellow inventors, he decided to develop it further. The idea itself wasn’t exactly new – it had been echoing around the scientific community for over 100 years. The challenge was to realise it in a way that was commercially viable, and Christopher Latham Sholes was ready.

His first design, in 1868, resembled something like a piano. Two rows of keys were arranged alphabetically in front of a large wooden box. It was not a success. Then, after almost 10 years of trial and error came something much more familiar. It had the foot-pedal of a sewing machine and most of the remaining mechanism was hidden by a bulky casing, but at the front were four rows of numbers, letters and punctuation… and a spacebar.

Surprisingly little is certain about why he chose to lay it out as he did, probably because to Sholes the layout was no more than a side-effect of the machine he was trying to create. But as the most influential component of the typewriter, the qwerty keyboard has attracted debates about its origin, its design and whether it is even fit for purpose. Without historical references, most arguments have centred on statistical evidence, jostling for the best compromise between the statistical properties of our language and the way that we type. More recently, questions have been posed about how generic ‘the way that we type’ actually is. Can it be generalised to design the perfect keyboard, or could it be unique enough to personally identify each and every one of us?

The first typewriter was designed for hunt-and-peck operation as opposed to touch typing.  In other words, the user was expected to search for each letter sequentially, rather than tapping out sentences using muscle-memory. Each of the 44 keys was connected to a long metal typebar which ended with an embossed character corresponding to the one on the key. The typebars themselves were liable to jam, leading to the commonly disputed myth that the qwerty arrangement was an effort to separate frequently used keys.

Throughout the 20th century new inventors claimed to have created better, more efficient keyboards, usually presenting a long list of reasons why their new design was superior. The most long-lasting of these was the Dvorak Simplified Keyboard, but other challengers arrived in a steady stream from 1909, four years after qwerty was established as the international standard.

Is it possible that there was a method behind the original arrangement of the keys? It really depends who you ask. The typebars themselves fell into a circular type-basket in a slightly different order to the one visible on the keyboard. Defining adjacency as two typebars which are immediately next to each other, the problem of separating them so that no two will jam is similar to sitting 44 guests around a circular dinner table randomly and hoping that no one is seated next to someone they actively dislike.

Picture 1
The qwerty keyboard and typebasket (Kay, 2013)

For any number, n, of guests, the number of possible arrangements is (n-1)!. That is, there are n places to seat the first guest, multiplied by (n-1) places left to seat the second guest, multiplied by (n-2) for the third guest and so on. Because the guests are seated round a circular table with n places, there are n ways of rotating each seating plan to give another arrangement that has already been counted. So, there are (n x (n-1) x (n-2) x…x 1)/n = (n-1) x (n-2) x…x 1 arrangements, which is written (n-1)!.

By pairing up two feuding guests and considering them as one, you can find the total number of arrangements where they are sat next to each other by considering a dinner party with one less person. From our calculation above we know the total number of possible arrangements is (n-2)!, but since the feuding pair could be seated together as XY or YX we have to multiply the total number of arrangements by two. From this, the final probability of the two feuding guests being sat together is 2(n-2)!/(n-1)! = 2/(n-1), and so the probability of them not being sat together is 1-(2/(n-1)) = (n-3)/(n-1).

But what if one or more of the guests is so unlikable that they have multiple enemies at the table? Say ‘h’ who has been known before now to clash with both ‘e’ and ‘t’. Assuming the events are independent (one doesn’t influence the other) we just multiply the probabilities together to get the chance of ‘h’ being next to neither of them as [(n-3)/(n-1)]2. And the probability that on the same table ‘e’ is also not next to her ex ‘r’ is [(n-3)/(n-1)]2 x [(n-3)/(n-1)] = [(n-3)/(n-1)]3. So, for any number of pairs of feuding guests, m, the probability of polite conversation between all is [(n-3)/(n-1)]m.

Now, returning to the problem of the typebars, a frequency analysis of the English language suggests there are roughly 12 pairings which occur often enough to be problematic. For n=44 symbols, the dinner party formula gives a probability of [(44-3)/(44-1)]12 = [41/43]12 = 0.56. That is a better than 50% chance that the most frequently occurring letter pairs could have been separated by random allocation. An alternative theory suggests that Sholes may have looked for the most infrequently occurring pairs of letters, numbers and punctuation and arranged these to be adjacent on the typebasket. The statistical evidence for this is much more compelling, but rivals of qwerty had other issues with its design.

August Dvorak and his successors treated keyboard design as an optimisation problem. With the advantage of hindsight now that the typewriter had been established, they were able to focus on factors which they believed would benefit the learning and efficiency of touch typing. Qwerty was regularly criticised as defective and awkward for reasons that competing keyboards were claimed to overcome.

The objectives used by Dvorak, qwerty’s biggest antagonist and inventor of the eponymous Dvorak Standard Keyboard (DSK), were that:

  • the right hand should be given more work than the left hand, at roughly 56%;
  • the amount of typing assigned to each finger should be proportional to its skill and strength;
  • 70% of typing should be carried out on the home row (the natural position of fingers on a keyboard);
  • letters often found together should be assigned positions such that alternate hands are required to strike them, and
  • finger motions from row to row should be reduced as much as possible.
Picture 2
The Dvorak Simplified Keyboard (Wikimedia commons)

To achieve these aims, Dvorak used frequency analysis data for one-, two-, three-, four- and five- letter sequences, and claimed that 35% of all English words could be typed exclusively from the home row. He also conducted multiple experiments on the ease of use of his new design over qwerty, although the specifics were sparsely published.

Of course, however good Dvorak’s new design may have been, there was a problem. Qwerty being pre-established meant that finding subjects who were unfamiliar with both keyboards was difficult. Participants who tested the DSK had to ‘unlearn’ touch typing, in order to relearn it for a different layout, while those using qwerty had the advantage of years of practice. The main metric used to determine the ‘better’ design was typing speed but clearly this was not only a test of the keyboard, it was also a measure of the skill of the typist.

Alone, average typing speed would not be enough to distinguish between individuals – any more than 40 words per minute (wpm) is considered above average and since a lot more than 40 people are average or below average typists, some of them must have the same wpm – but other information is available. Modern computer keyboards send feedback from each letter you type, leading to a wealth of data on the time between each consecutive key press. This can be broken down into the time between any particular letter pairing, building a profile on an individuals specific typing patterns, and combined with typing speed it is surprisingly effective at identifying typists.

In a battle of the keyboards, despite its suboptimal design and uncertain past, qwerty has remained undefeated. Today it is so ubiquitous that for most people to see a different layout would be jarring, yet our interactions with it are still identifiably unique. Nearly 150 years after its conception, the keyboard is embedded in our culture – it’s an old kind of technology, just not the one Scholes thought he was inventing.

How to catch a Serial Killer with Hannah Fry

Hannah Fry (UCL) explains how police detectives use maths to help them catch a serial killer.

The second video featuring Hannah discussing the Maths of Data, first part here.

Find out how this method can be used to pinpoint the probable home of ‘Jack the Ripper’ courtesy of Tom Rocks Maths intern and Oxford University student Francesca Lovell-Read here.

Global Math Week 2019

As part of the celebrations for Global Math Week 2019, my video on how to use simple probability to improve your chances of winning at the board game Monopoly has been featured as a ‘Random Act of Mathematical Delight’. Check out the other amazing contributors via the Global Math Project website.

Tom Rocks Maths: S02 E07

More great music and great maths from Tom Rocks Maths on Oxide Radio – Oxford University’s student radio station. Featuring special guest Yuxiao who explains the Monty Hall problem, tackles the infamous numbers quiz, and sets us not one, but THREE problems in a bumper edition of the weekly puzzle. Plus, music from ACDC, Gym Class Heroes and The Offspring. This is maths, but not as you know it…

Thanks to Alice Taylor for production assistance.

WordPress.com.

Up ↑