Conference rusure::math

I saw this problem already, when I looked up the infinity lemma.  Isn't there
more to the tiles than you describe?  I believe Knuth uses square tiles, with
numbers on each of the sides, and the numbers are required to match those
of adjacent tiles.


				-- edp

Aha... tiles again...

I didn't follow the infinite discussion on 335 closely, but if you can tile
the "upper right corner" of the plane ( that is {(x,y)|x,y>=0} ), then you
can tile "bigger" corners ( e.g. {(x,y)|x,y>=-1} ) by a 1:1 transformation
of the previous "tiling". Now you have a sequence (with 0,-1,-2,...) of
"upper right corners" each containing the previous, each perfectly tiled.
can you use 335 now ?

Nitsan

That argument doesn't work, because each such transformation leaves the same
problem that you had before - you still have an unlimited space to cover.
What you need is an argument that shows how one can append an L-shaped
area while leaving the rest intact. That will provide a sound basis for an
induction argument.

Your approach reminds me of the argument that all girls have blue eyes:
assume it's true for N<k, then consider the k+1st girl in combination with
any (k-1) subset of the rest. That forms a set of k girls, which by the
hypothesis all have blue eyes, so the k+1st girl must have blue eyes. The
solution to this riddle is to stare into the eyes of a number of girls
until you get tired of the exercise...

Lynn Yarbrough

	Let's solve the one-dimensional case, which at least gets us
over the hurdle of considering infinity properly.

	Suppose we can tile the positive x-axis, can we tile the whole
x-axis?

	The key thing is that there's only a finite number of different
possible tiles.   Each of them will have a lhs and a rhs drawn from a
(necessarily finite) set A.   We can view each possible tile as an edge
in a directed graph G with vertex set A:

	edge e links a to a' IFF a is the lhs of e and a' is the rhs of e.

	Now, we know that there is a vertex s in G such that there is
an infinite path in G starting from s.   Since |A| is finite, this means
that there is a cycle in G.   Using this cycle and no other tiles, we can
trivially tile the x-axis.

Regards,
Andrew.

This problem is covered in Knuth's "The Art of Computer Programming",
Vol.1 (Fundamental Algorithms).  It can be found under "Infinity Lemma"
in the index.

The infinity lemma: In any infinite oriented tree for which every vertex
has finite degree, there is an "infinite path from the root," i.e., an
infinite sequence of vertices V_0, V_1, V_2, ... in which V_0 is the root
and fin(e[V_j+1]) = V_j for ajj j >= 0.

Following the brief proof, the book mentions that "students of calculus
may recognize that the argument used here is essentially like that used to
prove the classical Bolzano-Weierstrass theorem, "A bounded, infinite set
of real numbers has an accumulation point."  One way of stating [the infinity
lemma] as K�nig observed, is this: "If the human race never dies out, there is
a man now living having a line of descendants that will never die out.""

For the tiling problem, ... "The set of all solutions to the problem of tiling
squares with an even number of cells on each side forms an oriented tree, if the
sons of each 2nx2n solution x are the possible (2n+2)x(2n+2) solutions that can
be obtained by bordering x. ..."  This was observed by Hao Wang in the Nov 1965
issue of "Scientific American".

Frankly, I don't quite understand why Wang resorted to so bushy a tree; the
tree formed by larger and larger tilings of the upper right plane should also
meet the requisites for application of the infinity lemma.  Wang's proof *does*
hide any possible concerns regarding the "boundary" (along the x- and y-axes).

And then there's Kruskal's theorem, which runs counter to the infinity lemma.

>For the tiling problem, ... "The set of all solutions to the problem of tiling
>squares with an even number of cells on each side forms an oriented tree, if the
>sons of each 2nx2n solution x are the possible (2n+2)x(2n+2) solutions that can
>be obtained by bordering x. ..."  This was observed by Hao Wang in the Nov 1965
>issue of "Scientific American".

Neat!

>Frankly, I don't quite understand why Wang resorted to so bushy a tree; the
>tree formed by larger and larger tilings of the upper right plane should also
>meet the requisites for application of the infinity lemma.  Wang's proof *does*
>hide any possible concerns regarding the "boundary" (along the x- and y-axes).

You need to have a rooted tree.   Sure, there are an infinite number of tilings
of the upper right plane, but if you pick any one of them, then you can only
extend it by a finite number of descendants from it, before you stop.

>And then there's Kruskal's theorem, which runs counter to the infinity lemma.

What's that?

	Question (for which I haven't looked for the answer):
	With one dimension, we know that if we can tile the naturals, then
there is a *periodic* tiling of the integers.   With two dimensions, we know
that if we can tile the upper right plane, we can tile the whole plane.   But
can we exhibit a set of tiles for which the only tilings of the plane are 
non-periodic?

	Penrose tiling is inadmissible here because we require each tile to
be square.   However a similar proof to the proof of non-periodicity for the
Penrose tiling is what I would look for first...

Regards,
Andrew.

>> why Wang resorted to so bushy a tree
>You need to have a rooted tree.   Sure, there are an infinite number of tilings
>of the upper right plane, but if you pick any one of them, then you can only
>extend it by a finite number of descendants from it, before you stop.

Suppose you can tile the upper right plane.  Let T(xa..xb,ya..yb) represent the
(xb-xa+1)x(yb-ya+1) tiling that starts at position (xa,xb).  Let T(0..0,0..0)
be the root of the tree; T(0..1,0..1) is its son, and in general, T(0..n,0..n)
has son T(0..n+1,0..n+1).  Why doesn't this tree fit the requirements of the
infinity lemma?

>Kruskal's theorem.  What's that?

See the reference in Knuth.

>But can we exhibit a set of tiles for which the only tilings of the plane are
>non-periodic?

Yes.  See the reference in Knuth.  One of the exercises gives 92 domino types
having nothing but non-periodic (nontoroidal) tilings of the plane.  The answer
mentions a similar set of only 35 domino types.

>Suppose you can tile the upper right plane.  Let T(xa..xb,ya..yb) represent the
>(xb-xa+1)x(yb-ya+1) tiling that starts at position (xa,xb).  Let T(0..0,0..0)
>be the root of the tree; T(0..1,0..1) is its son, and in general, T(0..n,0..n)
>has son T(0..n+1,0..n+1).  Why doesn't this tree fit the requirements of the
>infinity lemma?

	The tree as you define it here will certainly satisfy the infinity
lemma precondition and postcondition.   However...

	If that is how you are defining 'son' then all that you can do with it
is prove that you can tile the upper right plane!

	I fear I haven't followed what you were trying to say.   If you think 
it's worth it, then please clarify what your construction is and how it differs
from the existing solution.

>Yes.  See the reference in Knuth.  One of the exercises gives 92 domino types
>having nothing but non-periodic (nontoroidal) tilings of the plane.  The answer
>mentions a similar set of only 35 domino types.

	I must look it up some time.   35 seems a lot.

Regards,
Andrew.

>	If that is how you are defining 'son' then all that you can do with it
> is prove that you can tile the upper right plane!
>	I fear I haven't followed what you were trying to say.

Ayup; you've understood.  Now my confusion is this:  Why does Wang's tree
prove something more than just tiling an upper right plane?

Both trees satisfy the requirements of the infinity lemma in the same way.
The same result should pop out the other end, n'est pas? right?

>> Ayup; you've understood.  Now my confusion is this:  Why does Wang's tree
>> prove something more than just tiling an upper right plane?
>>
>> Both trees satisfy the requirements of the infinity lemma in the same way.
>> The same result should pop out the other end, n'est pas? right?

	If you follow one of the infinite paths that exists through
	one tree, you have a nested series of tilings the nth level
	of which covers, say, the square [-n,n] x [-,n].  The union
	of the levels covers the entire plane.  If you follow one of
	the infinite paths that exists through the other tree, however,
	you have a nested series of tilings the nth level of which
	covers, say, the square [0,n] x [0,n].  The union of the
	levels covers the upper right quarter plane.

	Dan