# Archive for July, 2009

### Banach and Mazur game

I want to rewrite here a part of my degree thesis speaking about a very nice way to describe residual sets.. I start with the abstract Bourbakist definition anyway.
Let $E$ be a topological space.

Definition
A set $S\subset E$ is called nowhere dense if it fails to be dense in every open subset of $E$: that is, for every nonempty open $U\subset E$ there is a nonempty open $V\subset U\setminus S$.

$S$ is then nowhere dense if and only if its closure $\bar{S}$ has empty interior; a finite union of nowhere dense sets is also nowhere dense; the topological boundary of a closed set or of an open set is nowhere dense.

Definition

A set $A\subset E$ is called of first (Baire) category if $A$ is a countable union of nowhere dense sets.
A set that is not of first category is called of second category.
The complement of a first category set is called residual.

Residual sets are then sets that are countable intersections of sets with dense interior. If a set is first category, then all its subsets are. In some sense the sets of first category are “small” (they are also called meagre sets because of this) and the sets of second category are “large”. We will show this using a description introduced by Banach and Mazur.

The Banach-Mazur game
Let $X$ be a metric space.

Suppose that there is given a subclass $\mathcal{E}$ of the subsets of $X$ having nonempty interior, such that each open set is contained in some member of $\mathcal{E}$. Suppose that there are given two sets $A\subset X$ and $B=X\setminus A$. The game $[A,B]$ is played according to the following rules: two players (A) and (B) alternately choose sets
$U_1\supset V_1\supset\ldots\supset U_n\supset V_n\supset\ldots$
from the class $\mathcal{E}$, with (A) choosing the $U_i$‘s and (B) choosing the $V_i$‘s, numerably many times. Such a nested sequence is called a play of the game. The player (B) is declared winner if
$\bigcap_{i=1}^{\infty}V_i\subset B$,
while otherwise (that is, if $\bigcap_{i=1}^{\infty}V_i\cap A\neq\emptyset$) the winner is (A).

To be more precise, we will call a strategy for (B) a sequence of functions $\beta=\{\beta_n\}$ giving for any sequence $(U_1,V_1,\ldots , U_n)$ of members of $\mathcal{E}$ as above, a new member

$V=\beta_n(U_1,V_1,\ldots, V_{n-1},U_n)\in\mathcal{E},\; V\subset U_n$

A play of the game $(U_i,V_i)_{i=1}^{\infty}$ is called consistent with a strategy $\beta$ if for all $n$,
$V_n= \beta_n(U_1,V_1,\ldots, V_{n-1},U_n)$
A strategy $\beta$ is winning for (B) if every play of the game consistent with $\beta$ ends up with a victory of B. If such a strategy exists, the game is said to be determined in favour of (B).
Clearly, in order to win, (A) will hope that the set $A$ is large, while (B) will have the same hopes for the set $B$. The right meaning for the word “large” in this context was (conjectured by Mazur and) proved by Banach to be the same as “residual”:

Theorem (Banach-Mazur)
The game $[A,B]$ is determined in favour of player (B) if and only if the set $B$ is residual in $X$.

Proof:
“if” part: Let $B\supset\cap_{i=1}^{\infty}G_i$ with $G_i$ open dense sets. We then choose
$V_n:=\beta_n(U_1,\ldots, U_n)\subset U_n\cap G_n,$
which can be done for the properties of $\mathcal{E}$ and of $G_n$. The resulting strategy $\beta=\{\beta_n\}$ is then easily seen to be winning, by the definition of the $G_i$‘s.
“only if” part: Let $\beta=\{\beta_n\}$ be a winning strategy for (B). We will call a consistent sequence of $n$ members of $\mathcal{E}$  a $\beta-$chain of order $latex n$, and the interior of $latex V_n$ will be called the interior of the chain. We will now inductively construct a sequence of dense open sets $\{G_n\}$ whose intersection is contained in the set $B$.
Let $F_1$ be a maximal subfamily of the $\beta-$chains of order 1 whose members have disjoint interiors, and let $G_1$ be the union of the interiors of the members of $F_1$. This open set is dense by maximality.
Then, among all the $\beta-$chains of order 2 that are continuations of some member of $F_1$ we choose a maximal subfamily $F_2$ with disjoint interiors, and let $G_2$ be the union of these interiors. The open set $G_2$ is again dense by maximality.
Iterating this procedure, we get a sequence of dense open sets $set{G_n}$. If $x\in \cap_{i=1}^{\infty}G_i$ then there is a unique sequence $\{C_n\}$ of $\beta-$chains $C_n\in F_n$ such that for each $n$, $x$ is in the interior of $C_n$. These $\beta-$chains are ordered by continuation and the limit play is consistent with $\beta$, so it must be a winning one. Thus $x\in B$, and since $x$ was arbitrary, $B\supset\cap_i G_i$.$\square$

As an application, we cite the following, which is usually proved using directly the definitions. We give instead a proof using the Banach-Mazur game:

Corollary

If the metric space $X$ is complete and $B\subset X$ is a dense $G_{\delta}$ set (i.e. a countable intersection of open sets), then $B$ is residual.

Proof:
Let $B=\cap_m A_m$, where the sets $A_m$ are open. We take $\mathcal{E}$ be the family of all closed balls, and we describe the winning strategy of player (B) in the game $[X\setminus B, B]$: let $U_n$ be the closed ball chosen by (A) at his $n$-th move. Since $B$ is dense, $B\cap$ int$U_n$ is nonempty. So int$U_n\cap A_n$ is a nonempty open set. By regularity there exists a ball of radius less than $2^{-n}$  whose closure is contained in the above set. We then choose that ball as $V_n$. We obtain that the sequence $(U_{i+1})$ refines the Cauchy filter basis $(V_i)$ and by completeness it has as intersection a single point $x$, contained in each $A_n$, and thus in $B$. $\square$

### inscribed triangle and square problem

I have found today this problem (or conjecture, if you wish):

Does every Jordan curve $\Gamma$ have 4 points on it which form the vertices of a square?

There is a survey about partial results on the Quomodocumque blog, but I have no access to a library from where I am now, so I think trying to figure it out alone might be a nice idea.

Jordan’s theorem When I mention it I mean this: any Jordan curve $\Gamma$ has an interior and an exterior, which are open connected by arcs sets such that the one called interior is bounded and together they form the complement of $\Gamma$. In particular any path (i.e. continuous curve) starting inside $\Gamma$ and ending outside it must pass through $\Gamma$.

Easy part: the triangle case

I already previously had come in contact with the analogous problem where one looked for inscribed equilateral triangles instead of squares, and that is easier: the answer was yes, by some topological argument, as follows.

There is a ($2$-valued) function $c$ with values in $\mathbb R^2$ depending continuously on $a, b\in\Gamma$ such that $[a,b,c]$ is an equilateral triangle. Using this and Jordan’s theorem, (with some patience) one verifies that there are couples $(a,b), (a',b')$ such that $c, c'$ are respectvely in the interior  and in the exterior of $\Gamma$. Moving the couple $(a,b)$ in $(a',b')$, by Jordan’s theorem again one has a nice equilateral triangle $[a,b,c'']$ with vertices all on $\Gamma$.

The procedure which works for equilateral triangles also works for any kind of triangle (you just have to use the ordering on edge lenghts carefully in each step, and after some trial and error you manage the right combination).

The square case

This case is really square. The problem with the above continuity methods based on Jordan’s theorem seems to be that as 2 vertices wander on $\Gamma$ the other two may pass independently from one connected component of $\mathbb R^2\setminus \Gamma$ to the other.

1) If you suppose the curve is smooth (say $C^1$) then you might try to take an inscribed “half-square” triangle $[a,b,c]$ (i.e. isosceles with one $\pi/2$ angle in $b$) which exists by the above theorem, and try to perturb it still leaving it inscribed, seeing what happens to the $4$th vertex $d$ of the square. To help intuition, suppose that near $a$ and $b$ the graph of the curve is a piece of line (recall you assumed $\Gamma\in C^1$ so this is not far from true). Then perturbations of $a,b$ give a $2$-dimensional set of perturbations of $c$‘s if and only if the lines representing $\Gamma$ near $a,b$ do not form an angle of $3\pi/4$. If this happens, then by the inverse function theorem one can find for each $a$ one $b$ such that $c$ completing the half square is still on $\Gamma$.

Then you could try to reason like before, asking yourself if there are two squares $[abcd], [a',b',c',d']$ with $a,b,c, a',b',c'\in\Gamma$ and $d, d'$ in different connected components of $\mathbb R^2\setminus \Gamma$. You can construct them as follows:

– if $a,b\in \Gamma$ are very close then there are 2 vertices completing the square inside $\Gamma$ (this uses the regularity of $\Gamma$). Then you can move $b$ along $\Gamma$ until the first time when one of $c,d$ touch $\Gamma$.

– if $a',b'\in \Gamma$ realize the diameter of $\Gamma$ then you can move $b'$ towards $a'$ until the first hitting as above and you get the second square.

Now you move $a, a'$ closer together until they become the same point, and let $b,c,b',c'$ follow them staying on $\Gamma$ and forming half-squares as discussed earlier, and $d,d'$ follow them completing at each moment the respective squares. During all this procedure by Jordan’s theorem $d, d'$ have kept on staying on opposite components of the complement of $\Gamma$. However nothing tells that there is a general way of moving one onto the other while $3$ vertices of the cubes stay all the time on the curve.

2) Let’s use the $3\pi/4$ angle found above to try producing a counterexample. The first idea I get is starting from a regular octahedron and moving two adjacent sides parallel to themselves towards the center, leaving all the other sides supported on the same lines. Exercise: find a square inscribed in this figure!

(there is no square in the original octagon that “survives” on this new one. However:)

3) Lemma: in all convex curves there is an inscribed square: just take any small square completely inside and “blow it up”, immagining that the curve represents a “rigid hole” in outside which the square cannot pass (but it can slide if this helps continuing to “expand”). At a certain point you cannot blow anymore: the square has at least 3 vertices on the curve and has reached the maximal size. Now suppose 3 vertices $a,b,c$ of $[abcd]$ are on $\Gamma$ and $d$ isn’t. This implies that the tangent cone to the interior of $[abcd]$ in $a$ and $c$ do not contain the sides $[ad],[cd]$ else by convexity $d\in\Gamma$. Then it (is easy to see that it) is not true that you cannot blow anymore. $\square$