Math Salad Incoherent mathematical writings

A note on the "trivial group presentation game": \(I\) has a winning strategy on the group \(F_2\)

In my post on the strong measure zero game, I mentioned a game , where player one, who I will call , presents player two, who I will call , a subset from a group , where the normal closure of the set is the full group, and , chooses one element from each set presented, trying to get a set whose normal closure is again the full group. The game lasts innings ( if you prefer that notation). Essentially the idea is that gives presentations of the trivial group, and is trying to end up with a presentation of the trivial group.

As a simple example, we can consider the group of integers . Since the group is abelian any group that normally generates the group, also generates the group. This also means that there is some linear combination of elements from any presented set that has value . What player can do to win, is choose a non identity element , where is the least among non identity elements. If , player has already chosen a set that normally generates and may choose arbitrarily. Suppose that has chosen , if we choose an arbitrary element. If we have , then choose an element , so that . Note that we can do that, since otherwise, every element in the presented set would have dividing it, hence the greatest common divisor of the set, without the identity, would be greater than or equal to , contradicting the set generates the group. So we can always decrease our greatest common divisor till we reach . So we have a strategy where will win every time. A similar argument can be used to show that wins in groups where every strictly ascending chain of infinite index subgroups, is finite.

It is pretty easy to find groups where wins, by using large groups, like , but what about finitely generated groups? We will show, in this post, that has a winning strategy to win , in fact it will be a “fixed strategy” where will play the same no matter what picks on ’s turns.

Our proof will use facts from small cancellation theory, in particular small cancellation groups are not trivial. I will explain a bit of the idea of small cancellation conditions, and give key definitions. All the small cancellation that we discuss can be found in Combinatorial Group Theory Lyndon and Schupp, or Geometry of Defining Relations in Groups by Ol’shanskii, or Wikipedia.

The idea of small cancellation theory is that, if you have a set of relations, satisfying a “small cancellation condition”, that is when you multiply the two different words, the length of the reduced product (remove the ) is not much shorter than the the sum of the lengths of the word. This, in a sense, gives control over what words end up representing the identity, and how words can be reduced using the relations that satisfy the small cancellation conditions.

Basic definition for small cancellation theory

The information in this section is all fairly basic stuff, you may want to skip this section, or just read the definition and come back if there are some words you do not know.

Basic definitions for words in free groups. related to words and free groups. A word is a string of elements from some some set called an alphabet. For example and are all (not equal) words from the alphabet . A word is reduced if there is no occurrence of or in the word, and cyclically reduced provided it is not a nontrivial conjugate, so and . The length of a word , which we call is the number of elements in the reduced version of the word; this is well defined. So , for example.

Definition of symmetrized presentation. Suppose . We say the set of relations is symmetrized provided it is closed under taking inverses, and taking cyclic permutations of words up to being cyclically reduced, and every word in is cyclical reduced. has a symmetrized presentation provided is symmetrized. For example

Definition of : We say that is a piece relative to provided there exists two distinct elements with and , where “” is word equality, so no cancellation. We way has condition if and where is a piece, then . There is an entirely similar definition for

The reason I only mention is that it is a strong enough small cancellation condition to guarantee a group is infinite. Note that you can have a group that has a presentation, but may not be given to you that way. It is an interesting fact that for , every group has a presentation. There are many other small cancellation conditions, and for example, and you can mix-and-match different conditions too, but that is really beyond this post.

Player has a winning strategy in

Let be the free group of rank , on the set . We will show that has a winning strategy, by showing that there is a sequence of sets, , that normally generate, even generates, the group , and any one element choice from each of these sets gives a set , which will correspond to a group, , that is , which means that can not normally generate . The strategy for player will be to play on the th turn.

There will be a couple parts where I make some estimates on inequalities, and make no attempt to make these as good as possible(the estimates I make are good enough). If you are sensitive to such disregard of sharp bounds, you will need to have your eyes covered for the rest of this proof. You have been warned.

Proposition 1. Let

Then we have that generates the group , but any one element choice from each results in a set of relations for a group. In particular this means that for any choice of ’s, where , that is an infinite group since it will be .

proof of Lemma 1. First it is clear that each generates since we can multiply to cancel on each term to end up with , which generates the group. Let be the smallest symmetrized set of words containing the word , which is all the cyclically reduced, cyclic permutations of the word and their inverses. For all pieces are of the form , where (note that for many can not actually be obtained). So the length of a pieces are bounded by

and the length of each is bounded from below by

We get that

which for we have the right hand side is less than . A very similar argument can be carried out for and , and in fact you can use the same bounds, since our bounds are so rough. So each , for , gives a presentation. Say that and , and , and we consider . Note, that at “worst” the amount of cancellation between words in and will be bounded by the cancellation bounds we established above for , since elements in have small enough exponents on their ’s that they can not completely cancel out a term in . This worked for arbitrary choices. So let be a sequence where , then is a symmetrized set of relations, and we know that between two words, the cancellation is less than the length of either of the words, so it gives a presentation, hence is a group, and is infinite.

I came up with this game in a class I took on selection principles, and studied it as a final project, and at the time I knew very little group theory (I still know very little), and even thought all finitely generated groups had a winning strategy for player . At the end of the class I only really found some conditions for player winning in finitely generated groups. It had been at the back of my mind since the class, I would pick it up and work on it for a while before setting down, multiple times. In a way, thinking about this problem and closely related things really influenced my mathematical interests, I have a feeling it will show in future posts. In the end I am actually not to sure these ideas are of interest, at least in the finitely generated group case. I suspect it will be a while before I discuss these games on groups again, but I will end this with a couple questions to ponder:

  • For finitely generated groups is there a nice demarcation line between player or having a winning strategy? For groups in general?
  • Are there groups where there is no winning strategy for either player? Are there finitely generated groups where there is no winning strategy?
  • There are a couple of other, similar ideas to consider, one where you replace normally generate with simply generate, or replace with generate finite index subgroup, or normally generate finite index subgroup, or mix-and-match the different sets. (I have not really thought about them much, but there are probably a lot of equivalences, because once you reach a finite index subgroup, in many cases, reach the full group) Are there any interesting connections and differences among them?
  • For those who have looked up the connection of these sorts of games with selection principles and Ramsey statements(see the references in the strong measure zero game post): are there interesting connection between those and the games for finitely generated groups? For countable groups? For groups? In particular what would the Ramsey statements be?
  • Can you think of any cool group theoretic consequences of a group that has a winning strategy for , how about for ?

The Strong Measure Zero Game

Background

Originally, my first post was going to be an introduction to selection principles, especially those in topology, and a few other related concepts. I decided I could not do justice to the subject in one post (especially with my minimal knowledge), and have opted to present some very cool results that will, hopefully, give a taste of the ideas that come up when studying the subject.

Definition of the game . Let and be collections of sets, we define the game to be a game with two players, that we will denote and , and the game will have innings, where each inning consists of a turn by and then a turn by . By innings we mean there is an inning for each (if you prefer ). The innings follow this pattern: player starts off, in inning , by presenting a nonempty set from which marks the end of player ’s turn, and then player picks an . At the end of the innings we are left with a play

of what happened in that game. Player wins if and wins otherwise.

A couple of examples to consider:

  • Let consist of all dense subsets of . Consider .
  • Let be a countable subset of some topological space and is the set of all open covers of , and the set of covers for . Consider .
  • is a finite dimensional rational vector space, and is the set of infinite vector subspaces of , and is the set of sets that contain infinite rational vector subspaces of . Consider
  • Let be an ultrafilter on some set. Consider .
  • Let be a group and the set of subsets of that normally generate the group. Consider . There are also variation of considering sets that generate the group , and looking at , , (there is a very good chance I am going to write about this bullet point, and related ideas, in future posts, since it is basically the reason I started the blog).
  • etc. Think of some others!

A strategy for a player is a function that takes what has been played and outputs the next move. So will be strategies for players respectively, and , and . We get a similar description for . Basically they are instructions on a game tree that tell the player what to do next given where they are in the game tree. We call a winning strategy provided the cooresponding player will always win following that strategy. It is interesting that in some games there is no winning strategy for either player, and in fact the two main theorems that will be presented will give such an example(assuming Borel’s conjecture is false)

Do any of the above (bulleted)examples have winning strategies for one of the players? How about the games you came up with?

Definition of strong measure zero. A set is strong measure zero if, for all sequences of positive real numbers, then there exists a sequence of intervals , where the length of is less than for all , and .

Every strong measure zero set is Lebesgue measure zero, although not every measure zero set is strong measure zero, the Cantor set provides such an example. It is also easy to see that every countable set is strong measure zero. In fact Borel’s conjecture actually conjectures that every strong measure zero set is countable. That conjecture ended up being independent of the usual axioms, ZFC, so it is consistent for there to be uncountable strong measure zero sets, and consistent for there to be only countable strong measure zero sets. Luzin sets provide examples of strong measure zero sets that are not countable.

Let , , be the set of all intervals of length less than , and say , and the set of open covers of some set (where the open sets come from and not with the subspace topology).

Definition of the strong measure zero game. Let . Then the strong measure zero game is the game .

There are a couple of other definitions I could have chosen, but I want to stress that the game has a very strong connection to strong measure zero, since player can choose a sequence of and play , in inning , and then tries to cover by collecting one interval from each .

A very natural question to ask is when does player have a winning strategy, and when does player have a winning strategy in ? This brings us to “the main event”:

Theorem 1. Player has a winning strategy in the strong measure zero game, if, and only if, is countable.

Theorem 2. Player has a winning strategy in the strong measure zero game, if, and only if, is not strong measure zero.

One of the things that makes these results interesting is that this means it is consistent for winning strategies to always exist, that is when all strong measure zero sets are countable, and it is consistent for there to be sets where there is no winning strategy, which is when there are uncountable strong measure zero sets(as an example the Luzin sets mentioned before).

The Proofs of Theorem 1 and 2

The proofs of Theorem 1 and 2, that will be presented, is Galvin’s with some modification and can be found in his paper Indeterminacy of point-open games. I found out about this proof in a class, taught by Marion Scheepers, a few years ago.

First, some notation, will be the set of infinite sequences of order type , will be the set of finite sequences indexed by finite ordinals. And if are sequences, then will be the concatenation of the sequences. As examples

and

Lemma 3. Let be a set and suppose that for each we have that a set , which is a set of positive integer, finite length, sequences such that:

  1. For every infinite sequence there is a such that .
  2. For each finite sequence ,

then we have that ( is countable).

proof of Lemma 3. We will prove by contradiction, so suppose that is an uncountable set with the above properties. This means that

since the part that is being removed from is countable. Let be an element from this nonempty set. By the definition of the above set, we know that has the property, that for any sequence , that there is an such that . Starting with the empty sequence, , we know there is a least such that , and we can continue doing this inductively, constructing sequences of length . This contradicts property 1.

Theorem 1. Player has a winning strategy in the strong measure zero game, if, and only if, is countable.

proof of Theorem 1. It is easy to see that has a winning strategy, when is countable, since we can enumerate the set , and in turn , covers the -th element. For the other direction, we will need to define a different game. Let be a separable metric space, so it also has a countable basis. (Separable means contains a countable dense set subset.) The game has these rules:

  1. There is an inning for each .
  2. In inning player chooses a set , where is open and the distance between and is positive, where distance between the two sets is defined to be . We will call such pairs playable
  3. Player chooses one of the sets, which we will call .
  4. Player wins if .

Lets call this game , or the disjoint open ball game on . We will now show that when has a winning strategy for then the set is countably infinite. Let be a winning strategy for . Note that we may assume that only plays from sets from a basis, and since we have a countably basis, we may assume that plays from some countable basis. Let where is an enumeration of all playable , where are from our chosen countable basis. For we define

Given that is a winning strategy for , we can see that for any and sequence that some segment , since otherwise for all , so contradicting that set being empty. Hence we have condition 1, from Lemma 3. We will now show condition 2 of Lemma 3. Suppose that we have distinct

for . We can choose playable pairs

where the index on the open sets says that it contains but not the where , since we are in a metric space. And note that only one of the can be in , hence other two, , are not contained in that set. This is true for each combination, so we have

So we get that , and by shuffling things around, we get that each of the three points, , have cooresponding sets that they are not in, hence they are not in the intersection of all those sets. This worked for an arbitrary choice of three points, so it must be

Using Lemma 3, we get that the space is countable.

Let be a winning strategy for in the strong measure zero game on . We are going to show that the strategy will help us construct a winning strategy in the game , hence will be countable.

Say that player plays in , and plays in the strong measure zero game. We will have player play , and then will be an element disjoint from , which we can pick since the length of is less than . So we can define a strategy where if and otherwise. We will now show that this is in fact a winning strategy. Note that

but the union part covers the whole space so the intersection on the left must be empty. So player has a winning strategy for when has a winning strategy for the strong measure zero game. Thus is countable.

Lemma 4 (Lebesgue covering lemma). If is a compact metric space, then for any open cover of , there exists a postive real number , the Lebesgue number, such that: for any of diameter less than there is a in the open cover such that .

proof of Lemma 4. This is a well known theorem, so no proof will be given.

Theorem 2. Player has a winning strategy in the strong measure zero game, if, and only if, is not strong measure zero.

proof of Theorem 2. First we will prove (), so suppose that is not strong measure zero. Hence there is a sequence for such that, such that for all sequences of intervals , for , length of is less than or equal too . So have player plays in inning , so player can not cover the space, since it will only pick intervals less than at inning .

We will know prove (), we will do the contrapositive, so we will show that if is strong measure zero then does not have a winning strategy. Let be an arbitrary strategy for player , and is strong measure zero. We will show that there is a play, by player that will beat this strategy. Here are some things that we are going to assume, to make the problem a bit easier:

  1. That we are playing on strong measure zero sets, that are subsets of compact sets, and in fact we will assume to be working with . This is enough since we can write as a countable union of compact sets, for example , and partition the innings, into countably infinite many infinite sets (think of sets of the form , prime ), so we play the strong measure zero game on the th compact set when the inning we are in is in the th partition.
  2. We will assume that the ’s that are played by player have ’s of the form , since for some we can just move to a smaller number of the form without losing any generality.
  3. Let be some sequence of turns, that is in the domain of player ’s strategy , then we define .

We will now construct a play in which which beats player strategy . Say that . Lets say is a finte open cover of (which exists since is compact). Consider , and we will choose large enough so that:

  1. ,
  2. ,
  3. and is a Lebesgue number of the cover .

Basically we are going to go down, and play every possible outcome of the strategy possible. Let , be a finite open cover, so in particular this works as a subcover for for since . Then we are going to choose an large enough so that:

  1. (this also means that for , which are the corresponding “n_i” terms ),
  2. ,
  3. And is a Lebesgue number of the cover .

Basically we continue in this fashion, and construct , for arbitrary (which if that statement was good enough for you, I recommend skipping this paragraph). Suppose that we have constructed. Then we are going to construct by letting be a finite open cover. Then we choose large enough such that:

  1. ,
  2. ,
  3. And is a Lebesgue number of the cover .

So know we have a sequence , where each is a Lebesgue number of the coverings . Since is strong measure zero we have that there is a covering where each has length less than . Since is a Lebesgue number of the cooresponding coverings, we can find an such that . We can choose the as our sets, and so we found a play where wins, hence is not a winning strategy, and since was arbitrary we are done.

Resources

You can find out more about these sorts of things from this, non-exhaustive, list:

  • F. Galvin, Indeterminacy of point-open games, Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 26 :5 (1978), 445–449 (this is sort of difficult to find, so included all the information, for libraries)
  • “The combinatorics of open covers (I): Ramsey theory” by Marion Scheepers,
  • “The combinatorics of open covers (II)” by Winfried Just, Arnold W. Miller, Marion Scheepers, and Paul J. Szeptycki,
  • “The combinatorics of open covers ()” by … (well there are at least 11 of these…),
  • “Ramsey theory of open covers lecture 1” by Nadav Samet and Boaz Tsaban,
  • “Ramsey theory of open covers lecture 5” by Nadav Samet and Boaz Tsaban.
  • You can browse around here

The “Ramsey theory of open covers” are more accessible and shorter than “The combinatorics of open covers…” and discuss some of the Ramsey theoretic aspects that are related to these games and to “selection principles” (which I did not discuss here, although are very related to games ).