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.

This isn’t immediately obvious (I never noticed during my PhD, where I used Schreier sets heavily!), but here’s how to prove it. Morally, if the claim is true, there should be some way of constructing M_{n+2} if we know both M_{n} and M_{n+1}. Let’s define two maps:

  • Replace: R_n(X) takes the greatest element of a set X and replaces it with n.
  • Shift: S_n(X) adds 1 to each element of the set X, and then appends n.

For instance, R_6(\{5,4,3\})=\{6,4,3\}, and S_6(\{4,2\}) = \{6\} \cup \{4+1,2+1\} = \{6, 5, 3\}.

I now claim that if the set X is in M_{n+1}, then R_{n+2}(X) is in M_{n+2}: it will be admissible with maximum element n+2. The new maximum is easy to see, and the number of elements stays the same, whilst the minimum element doesn’t decrease (it stays the same and only increases when acting on a singleton set). Furthermore, the mapping is one-to-one (or injective) on M_{n+1}: if you apply R_n to two different inputs from M_{n+1}, you get two different outputs. And if you start with an input X from M_{n+1}, then R_{n+2}(X) cannot contain n+1.

In a similar way, S_{n+2} is a one-to-one mapping from M_n to M_{n+2}, and the image always contains n+1. The number of elements increases by one, but so does the minimum element.

It’s also possible to reverse these mappings, and S_{n+2}^{-1} is an injective map to M_n, from those elements of M_{n+2} that contain n+1, and R_{n+2}^{-1} is an injective mapping to M_{n+1} from those elements of M_{n+2} that do not contain n+1.

Therefore, both of these maps are bijections onto their images, and:

R_{n+2}(M_{n+1}) \cup S_{n+2}(M_n)

= \{X \in M_{n+2}: (n+1) \notin X\} \cup \{X \in M_{n+2}: (n+1) \in X\} = M_{n+2},

as those sets which do contain (n+1) and those that don’t, together account for the whole of M_{n+2}. Therefore:

|M_{n+1}|+|M_n|=|R_{n+2}(M_{n+1})|+|S_{n+2}(M_n)|=|M_{n+2}|.

The final step of the proof is to note that M_1=\{\{1\}\} and M_2 = \{ \{2\} \}, so |M_1|=F_1=1 and |M_2|=F_2=1.

Ordering

I’ve ordered the Schreier sets by writing them in binary and using the natural ordering. For example, write \{4,3,2\} as 1110, which is greater than \{4,2\} or 1010. This means we can write the Schreier sets in order as:

\{1\},\{2\},\{3\},\{3,2\}, \{4\}, \{4,2\}, \{4,3\} \ldots.

This order is just what we get when we write M_1, M_2, M_3, M_4, \ldots, or

M_1, R_2(M_1), R_3(M_2), S_3(M_1), R_4(M_3), S_4(M_2), \ldots.

In binary this looks like:

1,10,100,110,1000,1010,1100, 10000,10010,10100,11000,11100, \ldots

Converting to natural numbers gives:

1,2,4,6,8,10,12,16,18,20,24,28,32,34,36,40,44,48,52,56, 64 \ldots.

Every F_{n}th term in this sequence is a power of two: 2^{(n-1)}. You can prove this by thinking about the sum of the first n Fibonacci terms and using

The differences between these are quite infuriatingly:

1,2,2,2,2,2,4,2,2,4,4,4,2,2,4,4,4,4,4,8, \ldots.

A challenge: if you can see a nice algorithmic way to generate one Schreier set from the previous one (not necessarily with the ordering given here), I’m sure someone would find it interesting. I would, at least. It would also be acceptable to move through each M_n starting with \{n\}, or restricting yourself to the maximal Schreier sets

Maximal Schreier sets

During my research, I was mainly interested in the maximal Schreier sets: ones to which no further numbers could be added. With the above method of generating Schreier sets (with replacement or shifting), if you start with the maximal Schreier set \{3,2\} and apply these two moves, you will generate only maximal subsets, and all the maximal subsets, except the singleton \{1\} (The proof of this goes like the Fibonacci proof above).

Further Afield

I referred to the Schreier family as the first Schreier family. This is because higher-order Schreier families have become a focus of study. The second Schreier family is defined by choosing a Schreier set with minimum m, and then adding at most (m-1) Schreier sets (with higher minima), and taking the union.

For instance \{3,5,10\} \cup \{11,12,13\} \cup \{6,10,13,14,16,19\} = \{3,5,6,10,11,12,13,14,16,19\} is a second-order Schreier set. Higher Schreier sets are then defined by induction, and transfinite induction to give infinite versions of the Schreier sets.

These higher-order Schreier families are used to define nasty Banach spaces, and often applied in conjunction with Ramsey theory. They were independently discovered by Ramsey theorists, and seem to be intrinsically linked to hereditary families of sets.

Some Publications

Here you will find a list of fifteen of Jozef Schreier’s papers. You can find links to many of his papers here and here. Four of Schreier’s papers are referenced on Google Scholar, and more usefully you can see recent papers that cite them. Eight of his collaborations with Ulam should be found in the book: “Stanislaw Ulam: Sets, Numbers, and Universes”,  MIT Press, 1974:

Ein Gegenbeispiel zur theorie der schwachen konvergenz
J Schreier – Studia Mathematica 2 (1930) 58–62.

Sur une propriete de la mesure de M. Lebesgue
J Schreier, S Ulam – Comptes Rendus de L’Academie des Sciences 192 (1931) 539–542.

“O systemach eliminacji w turniejach” (“On elimination systems in tournaments”/”On tournament elimination systems”).
Mathesis Polska 7 (1932) 154–160.

Sur le groupe des permutations de la suite des nombres naturels
J Schreier, S Ulam – Comptes Rendus de L’Academie des Sciences 197 (1933) 737–738.

Sur les transformations continues des spheres euclidiennes
J Schreier, S Ulam – Comptes Rendus de L’Academie des Sciences 197 (1933) 967–968.

Über die Permutationsgruppe der natürlichen Zahlenfolge
J Schreier, S Ulam – Studia Mathematica 4 (1933) 134–141.

Eine Bemerkung zum starken Gesetz der großen Zahlen
ZW Birnbaum, J Schreier – Studia Mathematica 4 (1933) 85–89.

Über die Drehungsgruppe im Hilbertschen Raum
J Schreier, Studia Mathematica 5 (1934) 107–110.

Über topologische Abbildungen der euklidischen Sphären
J Schreier, S Ulam – Fundamental Mathematical 23 (1934) 102–118.

Eine Bemerkung über die Gruppe der topologischen Abbildungen der Kreislinie auf sich selbst
J Schreier, S Ulam – Studia Mathametica 5 (1934) 155–159.

Eine Bemerkung über Erzeugende in kompakten Gruppen
J Schreier – Fundamenta Mathematicae 25 (1935) 198–199.

Sur le nombre des générateurs d’un groupe topologique compact et connexe
J Schreier, S Ulam – Fundamenta Mathematicae 24 (1935) 302–304.

Über die Automorphismen der Permutationsgruppe der natürlichen Zahlenfolge
J Schreier, S Ulam – Fundamenta Mathematicae 28 (1937) 258–260.

Über Abbildungen einer abstrakten Menge auf ihre Teilmengen
J Schreier – Fundamenta Mathematicae 28 (1937) 261–264.

Eine Eigenschaft abstrakter Mengen
J Schreier – Studia Mathematica 7 (1938) 155–156.

1 Comment

Filed under General, Technical

One response to “Jozef Schreier, Schreier sets and the Fibonacci sequence

  1. Pingback: Mathblogging.org Weekly Picks « Mathblogging.org — the Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s