Category Archives: General

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):
Continue reading

Advertisements

Leave a comment

Filed under Accessible, Economics, General

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.

Comments Off on Post on Aperiodical

Filed under Accessible, General, Maths in Life

Jozef Schreier, Schreier sets and the Fibonacci sequence

This post has some more technical bits, as it’s aimed mainly at people with an undergraduate-level background in mathematics. I’ve included a historical note on Schreier, because it’s easy to forget that mathematical objects are named after real people.

These five sets (each of which have their elements written in numerical order) are Schreier sets:

\{1\},\{2,3\},\{2,6\},\{3,4,5\},\{3,6,17\},\{4,5\},\{5,6,7,8,9\}.

The following six sets are not Schreier sets:

\{1,2\},\{2,6,17\},\{3,4,5,6\},\{3,5,7,9,10\},

\{4,5,7,13,25\},\{5,6,7,8,9,10\}.

Can you spot the simple rule that defines whether a set of numbers is a Schreier set or not?

Historical Background

Jozef Schreier was born 1908/1909 in Lwów (then part of the Austro-Hungarian empire, now in Ukraine) and later based at the university there (whilst it was part of Poland). Schreier was killed in April 1943 during the Second World War in his home town of Drohobycz. In his book “Adventures of a Mathematician“, Stanislaw Ulam wrote about Schreier, his friend and collaborator:

We would meet almost every day, occasionally at the coffee house but more often at my house. His home was in Drohobycz, a little town and petroleum center south of Lwów. What a variety of problems and methods we discussed together! Our work, while still inspired by the methods then current in Lwów, branched into new fields: groups of topological transformations, groups of permutations, pure set theory, general algebra. I believe that some of our papers were among the first to show applications to a wider class of mathematical objects of modern set theoretical methods combined with a more algebraic point of view. We started work on the theory of groupoids, as we called them, or semi-groups, as they are called now.

Schreier was also a major contributor (ten questions) to the now famous Scottish book (an important book of questions, famous at least amongst Banach space theorists, and which you can read in English); in fact, he and Ulam pair were the only undergraduate student participants in the Scottish Cafe, a coffee shop where mathematicians from Lwów met, and scribbled maths directly onto the marble tabletops. The Scottish book was a notebook to save the work from being cleaned away at the end of the day.

The Baire-Schreier-Ulam and Schreier-Ulam theorems both bear Jozef Schreier’s name. He has on occasion been referred to as “Julian Schreier” (possibly by conflating him with Juliusz Schauder?): whereas Ulam’s account, the Portugese Wikipedia article, which seems to have been written by his family, and this journal from the time all name him Jozef (or a variant: Josef/Józef/Joseph). He definitely shouldn’t be confused with the contemporary mathematician Otto Schreier, who specialised in groups.

One of Jozef Schreier’s conjectures is now referenced in computer science literature: inspired by an article of Lewis Carroll, in the 1932 paper “On tournament elimination systems“, he conjectured that to find the second largest number in an unordered list requires at least n + \lceil \log_2 n \rceil -2 comparisons, which was later confirmed in the 1960s.

I’ve included a list of some of Schreier’s publications at the end of this article.

Schreier sets

In 1930, Schreier constructed a counterexample to a question of Banach and Saks using the following idea:

A (non-empty) subset X of the natural numbers is a Schreier set if its size is not larger than its least element.

|X| \leq \min X

The collection of all such subsets of \mathbb{N} is known as the (first) Schreier family. For example: \{1\}, \{2\} and \{3,5,42\} are all Schreier sets.  This definition is the first my PhD supervisor showed me in my very first supervision.

You can think of building Schreier sets by picking the smallest element, n say, and then filling the set up with at most (n-1) strictly greater distinct numbers.

The Schreier family has the following simple properties (that make it useful when defining norms on Banach spaces, especially the Schreier space):

  • The singleton \{n\} is Schreier set for all n \in \mathbb{N}
  • The family is hereditary: each (non-empty) subset of a Schreier set is itself a Schreier set.
  • The Schreier family is spreading: if \{m_1, m_2, \ldots m_k\} is a Schreier set and n_j \geq m_j for all 1 \leq j \leq k, then \{n_1, n_2,\ldots, n_k\} is also a Schreier set. (These don’t necessarily need to be in ascending order).

Schreier and Fibonacci

Many of areas of maths have links to the Fibonacci sequence: here’s one, involving the Schreier sets, that I haven’t seen before.

Define M_n to be all those Schreier sets whose greatest element is n. For instance M_5 = \{ \{5\}, \{5,2\}, \{5,3\}, \{5,4\}, \{5,4,3\} \}. Then the number of elements |M_n| = F_n the n-th Fibonacci number.

Continue reading

1 Comment

Filed under General, Technical

Out of the norm: an introduction

A norm is a general notion of distance that applies to vectors (most people have typically met vectors in two or three dimensions at school, for instance during GCSE maths). Several areas of mathematics arise out of the idea of a norm, such as Banach spaces and Banach algebras, the two areas I used to research as a PhD student and PostDoc.

Though mathematicians are stereotypically seen as bad communicators, it isn’t universally true. While mathematicians may on average be more socially awkward than, say, hairdressers, as in any walk of life there’s plenty of extroverts. It’s not even true of those at the top of the subject. Continue reading

Leave a comment

Filed under General