More on Gale–Shapley Nobel prize

I’ve long been a fan of the Gale–Shapley matching algorithm, and related problems, so was happy to see that a Nobel Prize was awarded for it. Having seen Peter Rowlett’s article that laid down the following gauntlet:

“I see ‘Nobel week’ as an opportunity for mathematicians to go in search of the mathematics behind each prize, rather than to retreat and complain about the lack of a prize specifically for mathematics”,

I was surprised that none of the mathsy types in my tiny corner of internet seemed to have noticed that a mathematician won a Nobel prize essentially for mathematics. After growing slightly impatient, I realised I only had myself to blame for not acting earlier, so I sketched a quick news story contribution over at the Aperiodical (it’s short and so reproduced here in full):

Post on Aperiodical

I’ve written an article for the Aperiodical entitled “Ask a mathematician: where should we live?”.

Dear Mathematician,

My partner and I are trying to buy a house. We both work in different places, and neither of us enjoys commuting. How could we decide where to live?

Fictionally yours,

Norman Mettrick

Norman,

Thank you for your intriguing and entirely imaginary letter. The short and not terribly useful answer would be…

Want to know? Read the rest of it there.

Jenga blocks and Gowers’ hyperplane space

This post is an attempt to communicate some of the feel of Banach space theory to those who aren’t familiar with it. I once tried to explain my research to a six year old using Jenga blocks, but fortunately only got as far as the triangle inequality. Near the end of my Phd, at my supervisor’s suggestion, I started to explore the complicated Banach space that is Timothy Gowers’ solution to Banach’s hyperplane problem. These experiences inspired the following explanation of one relatively simple observation (that I included as an example in my thesis) through the delightful medium of building blocks.

Our object of study are towers of good old-fashioned building blocks. Each block has a number written on its side, so each tower built from these blocks gives a sequences of numbers . These don’t have to be positive natural numbers, but you won’t lose much by pretending, in this post, that they are. There are innumerably many different brands of towers, but we’ll concentrate on one particular brand: the ‘Gowers Towers’. Let’s say the number written on each block represents how heavy the block is, and is inversely proportional to the length of the block. So we’d represent the sequence with the Gowers Tower pictured.

It’s worth mentioning that the Gowers Towers include every individual tower of finite height that you can build with your unlimited set of Gowers branded building blocks (and lots of infinite height, but you don’t really need to worry about those here).

Let’s pretend we’ve got a measure of the instability of a tower (the norm of the sequence), and whenever we increase the instability beyond a certain threshold, , the tower collapses.

Blocks with higher numbers are heavier, as well as narrower and perhaps inherently more unstable. How the blocks of different weights at different heights affect the stability of the Towers of Gowers is extremely complicated. However, the towers do have some nice, intuitive properties.

Getting into Norms: Part II

In Part I of Getting into Norms, I talked about three different ways of measuring distance (I also considered  the accuracy of a series of guesses to be a ‘distance’). All three of these were norms, but there are many ways of measuring distances that aren’t norms.

So to study norms, mathematicians must define them really rigourously, using something known as axioms. These are the basic assumptions and definitions of mathematics. Once we’ve made these assumptions we can prove what has to follow from them.

We can think of norms as a measure of distance from the origin. If you think about it in this way, the following seem quite obvious, and appeal well to our instincts. A norm satisfies the following three axioms.

1. Distances are always positive!
2. If the distance from your location to the origin is zero, then you must be at the origin. Or alternatively, if two points are separate then the distance between them isn’t zero. Conversely, the distance from any point to itself is zero.
3. Taking a detour is always longer than travelling in a straight line. This is the triangle inequality: the sum of the length of any two sides of a triangle is longer than the length of the third.
4. Now we come to axiom four. This one is tough to describe in words. Here goes. If you walk a pace forwards and then take another in the same direction, then you will have walked twice the distance of the original pace. Also it doesn’t matter whether you take a pace forwards or backwards: they will give you the same distance.

When mathematicians want to be precise, we use symbols. The distance between points and is written as . The distance from to the origin is . We say that is a norm if whenever we pick vectors and , and a number , then the following axioms hold:

1. .
2. If then . And visa-versa.
3. .
4. .

These four conditions should match with our verbal descriptions above. You may recognise them from this blog’s exquisitely hand-drawn logo.

They were pretty trivial intuitions, once we thought of as being the distance of a point from the origin (the origin above is underlined to distinguish it from the normal , though we don’t choose a different notation because the origin behaves a lot like the number zero).

Dice and Dissection: a puzzle

This is a puzzle, first appearing in Martin Gardner’s column in 1978, with a new way of thinking about the solution. Before the puzzle, though, a cultural diversion.

Rolling it in

In the modern classic board game The Settlers of Catan, it’s very important to know, when you roll a pair of dice, the frequency with which each number occurs. Resources are given players only if they have a settlement adjacent to those tiles whose number is rolled. If you build your settlements next to a tile labelled 2 or 12, it will, on average, only be productive once every 36 rolls. Tiles labelled 6 or 8 will produce resources five times in 36 rolls. It’s so fundamental to the gameplay that the relative frequencies are visualised as dots on the pieces: sixes and eights are so important, they are marked in red (rolling a seven does something different).

Puzzle

The well-known puzzle is:

By relabelling the faces of two dice, can you design a new, unusual pair of six-sided dice that achieves rolls with the same frequencies as a pair of normal dice? All the faces must have a positive number of spots.

If I didn’t require you to use a positive number of spots on each face: then dice labelled {0, 1, 2, 3, 4, 5} and {2, 3, 4, 5, 6, 7} would work as a pair. If you allow negative numbers, there’s infinitely many solutions!

Percentages for sceptics: part III

I wanted to do some self-criticism of my previous two posts in this series:

1. You can calculate the minimum of responses from a single percentage by hand (no need for computer programmes or look-up tables).
2. I’ve made a very rough model to estimate how many people the program typically returns when fed six percentages (as I did several times here).

In between, I’ve collected some links to demonstrate how great continued fractions can be.

Handy calculations

There are many ways of writing real numbers (fractions and irrationals) apart from in decimal notation. You can represent them in binary, for instance , or in other bases. These have their uses: there is a formula to calculate the th binary digit of without calculating all the preceding digits.

For our purposes we will use continued fractions. People write as : this notation means that 3 is a good first approximation to , the well-known is the closest you can be with any fraction with . Then is the best with , and the fourth term 

is a very good approximation, as the next number in the square brackets, 292, is very large (I’ll motivate this observation at the end of the section). The golden ratio is sometimes called the ‘most irrational’ number because it has a continued fraction expansion with all ones, so the sequence converges slowly.

Oil tanks and dipsticks

[If you're looking for the partial volume equations of a horizontal oil-tank, this article by Dan Jones has a nice write-up. Of course, you could just get someone to make a dipstick for you. My article only gives an overview of the problem, and how to approach it, from the perspective of a pure mathematician.]

This is the second post about real-life enquiries sent to my maths department, this one from a local engineer. Again, here’s the relevant section of the e-mail, partly to illustrate that, what might not at first seem an engaging problem for a pure mathematician, can turn out to be.

I need to calculate the capacity of a cylindrical tank laid horizontally with domed ends, in order to make an accurate dipstick. I would need to do the calculation several times in order to obtain capacities at varying levels.

This post is about how I went about finding a solution to this problem, and checking how good a solution it was. So now, if you happen to need a dipstick that fits these requirements (or just of a simple cylindrical tank), you can have one precision engineered to order. To continue the barge theme from the previous enquiry, you can also get a dipstick made for your barge’s diesel tank.

From rope-cutting to Golomb rulers, via magic

I’ve been learning a bit about Golomb rulers recently: a ruler which has so few markings that if you can use it to measure some whole number length, then you can only measure it in one way. I first read about them on the monthly AMS feature column, about their applications inside and outside of maths (to codes, radar, sonar and suchlike), and then watched an excellent TED talk using one particularly useful two-dimensional generalisation (a Costas array) to create a piece of piano music so dissonant that no time-step or jump in pitch between any pair of notes (not necessarily adjacent) is the same.

A perfect Golomb ruler with markings at 0,1,4 and 6, can measure any whole length from 1 to 6, but each in only one way.

I started to wonder about whether Golomb rulers had anything to do with a real-life problem I’ve previously written about, that someone who owned a barge had wanted answered. He asked about how to cut ropes into different lengths so you can knot them together in combinations and get a large variety of new lengths. I had decided the link was merely thematic, until someone else asked me whether they were the same, and prompted me to have a closer look. It turns out the two are somewhat linked, and what’s more, the link can be viewed as a silly little piece of mathemagic!

Planes, manes and pigeonholes

All aboard?

I was recently travelling on a budget flight with a friend, with no assigned seating. Walking up to the queue, we wondered whether we would be able to sit together. As people joined behind us, my friend, who whole-heartedly detests maths in any disguise, pointed out that we certainly could. To be so full-up to mean that we couldn’t, each row of three would need at least two people sitting in it. Since we could see from the queue that we had more than a third of the passengers still left to board after us, then as long as we weren’t trampled in a boarding stampede, we could certainly sit together.

This was actually a subconscious application of the pigeonhole principle, one of the most intuitive theorems that mathematicians use. It states that if you have objects to put in boxes then one of those boxes must contain at least two of the objects.

  

Or if you put pigeons in pigeonholes (or envelopes in pigeon-holes) then, if , at least one of the holes has at least two pigeons. So far, the type of maths you wouldn’t be shocked to see explained on television by a primary-coloured puppet.

All for one and none for all! Diversification, regulation and the tragedy of the commons.

Some proverbs come in contradictory pairs, for instance “Too many cooks spoil the broth” and “Many hands make light work”. I’d like to present an example that I feel illustrates two of these simultaneously. Everyone knows “Don’t put all your eggs in one basket”, including banks, which diversify by holding many different investments of different types. But while it may be in banks’ best interests to lower their levels of risk through diversification, it may plausibly raise the risk of a system-wide failure: if all banks follow that same advice, the rest of us may be “In for a penny, in for a pound”.

This is the argument given by Beale et al. in their paper Individual versus systemic risk and the Regulator’s Dilemma. Here’s a simple example that illustrates the main idea, adapted from a related comment in the earlier paper Systemic risk: the dynamics of model banking system.

Some people are playing a dice game. Each of them rolls a single fair die once and receives £1 for rolling a 1, £2 for a 2, and so on, up to £6 for a 6. However, afterwards they each have to pay £1.50 for the privilege of playing this rewarding game. Each of them starts out with no money, and so if they roll a 1, they go bankrupt.

If you play this game, there’s a chance that you’d go bankrupt on your roll. Let’s say ten people play the game: the chance of all of them going bankrupt on their single throw is , which is about one in sixty million.