| > < Note 315.3 by R2ME2::GILBERT > 11-AUG-1985
> As far as the first two questions go, does everyone give up?
Not so fast, Peter.
Q1. Well, suppose I have a shape, S, which has two distinct
dissections into tesselations T and T' of an oriented tile A. Call this
property Ethel. Suppose further, that S is minimal: that there is no smaller
shape which is Ethel.
Examine the squares on the Western-most column of S. Each of these
squares in T and T' must correspond to the one of the Western-most squares
of A. Which one? Well, most of them we don't know. But the Northern-
most of the Western-most column of S can only be the Northern-most of the
Western-most of A. But knowing one square fixes the whole tile. So T and
T' both contain the same tile in the same place. So we can remove it, and
the shape S\{A} is Ethel. But S was defined to be minimal Ethel.
Contradiction. Therefore no Ethel S exists.
Q2. Zilliards of examples. Q2 really just served as a entry to Q3,
of the which I find myself admiring Lynn's idea. To prove Lynn's suggestion,
however:
Suppose we have a shape, S, satisfying property Mavis, which is defined
in the obvious way, given Lynn's construction. Suppose further that S is
minimal Mavis.
Once again, let's examine that Western-most column of S. And once
again, let's pick the Northern-most square, N, of that column. Is the square
below N of S? If 'no', then in both T and T', N is the Western-most blob of
the cross. If 'yes', then in both T and T', N is the North-Western corner
of a square. But in either case, we can remove the shape to leave some
shape S\{?} which is still Mavis, contradicting the minimality of S. So
no Mavis S exists.
Let me offer another pair of tiles, which have the same effect, but
the reasoning seems to me to be marginally different.
+---+ +---+
| | | |
+---+ + +---+ +
| | | |
+---+ + +---+---+
| |
+---+---+---+
(Q4) Can you prove it?
(Q5) So, can we make some kind of statement about what pairs of oriented
tile will force uniqueness of tiling? Peter said he had an example "which
wasn't as good as Lynn's". Can you recall it?
Andrew.
|
| Let's crisp up the terminology, which was getting woolly even by
my standards. We define an aligned shape as an equivalence class under
translations (but not rotations or reflections) of finite connected subsets of
Z�, where connectivity is defined by horizontal or vertical (but not diagonal)
adjacency.
We pick two aligned shapes, A and A'. Take an arbitrary aligned
shape, S. We define a *parse* of S, to be a tiling of S with copies of
A and A'. S may have 0, 1 or many parses. We'll refer to S being unparsed,
well-defined, and ambiguous, in those three respective cases. We are
interested in pairs {A, A'} for which no S is ambiguous. Let's call them
*efficient*. There is obvious scope for generalization to triplets, quads,
etc, but for the moment, let's stick to pairs.
The grammatical analogy is useful. In coding theory, I can
have a set of strings over an alphabet, each string being a message. If
the set of messages satisfy the unique prefix condition, then I can unravel any
concatenation of messages into their constituent messages unambiguously. The
unique prefix condition says that there are no messages s1 and s2 for
which s1 = s2.t where . is concatenation, and t is some sequence of characters
drawn from the alphabet. Note that u.p.c. is sufficient but not necessary
for unambiguous unravelling of concatenated messages.
We could say that the same idea is used in many of the proofs so far.
Let's take a concrete example, where A and A' are respectively:
** and *
* **
The same proof that worked for Lynn's cross-and-square works here.
Assume there exists an ambiguous S, which without loss of generality we will
take to be locally minimal (no subset of S is ambiguous). We look at the
top row of S. Why? Because it is from the top that A and A' have
unique prefixes. This top row, running from l to r, is a concatenation
of various messages, drawn from the population "**", "*_", and "_", which are
taken over the alphabet {*,_}. (Here I take underscore to represent a blank).
This set of messages satisfies the unique prefix condition, so there is a
unique parsing of the top row.
Note that there's some reasoning to show that the population contains
"*_" and not "*". Consider modifying A to be just
**
and then consider S which is
***
****
(Parenthetically, a problem: if A is **, what is the smallest A' which
will make {A,A'} efficient. I have a solution which I believe to be the
smallest possible.)
Now we need to show that this unique parsing of the top row determines
unique covering of the top row of S with tiles. Since each of A and A' has
a different top row (applying u.p.c. top-to-bottom, over an alphabet which
*is* the messages {"**","*_","_"}), we are home, and have the usual
contradiction to the local minimality of S, disproving it.
I hope you recognize this as essentially the same argument as -.1's
proof of Lynn's construction, but recast in a more abstract form.
Pause for breath.
Now the interest in:
* & *
** **
***
is that there is no obvious u.p.c like activity to be found. If we
take the top row, then it is a concatenation of "*_", "*_" (sic) and "_".
There is no u.p.c. Or unique suffix condition either. Or try the bottom
row: "**", "***" & "_". Again, no u.p.c.
The concrete proof runs as follows. Let's look at the left of the
the bottom row, for a locally minimal ambiguous S. It must be tileable, by the
local minimality of S, with either A or A'. Ie. S looks like:
...
...
...
...*...
...***...
****...
This leaves unassigned, and unassignable, the second * in the next from
bottom row. Therefore, only A' can fit in the bottom-left-hand corner of S,
contradicting the local minimality of S. This is actually much simpler
to work out for yourself than it is to explain!
The question is, how to generalize this?
|
| re .5:
Very nice!
> (Parenthetically, a problem: if A is **, what is the smallest A' which
> will make {A,A'} efficient. I have a solution which I believe to be the
> smallest possible.)
Let A" be the smallest A' which makes {A,A'} efficient. Such a A'
exists, because the following A' is efficient with A.
*****
** * **
Now, A" is not
** ** * * **
* *** ** **** *** *** or **
because the following (respectively) are ambiguous:
** ** ****** ** **** *** *** **
**** ** ***** ***** **
Thus, A" must have 5 or more squares.
|
| >> What is the smallest A' which makes {**,A'} efficient?
> <<< Note 315.6 by KOBAL::GILBERT "Ownership Obligates" >>>
> Let A" be the smallest A' which makes {A,A'} efficient. Such a A'
> exists, because the following A' is efficient with A.
>
> *****
> ** * **
>
> Now, A" is not
>
> ** ** * * **
> * *** ** **** *** *** or **
>
> because the following (respectively) are ambiguous:
>
> ** ** ****** ** **** *** *** **
> **** ** ***** ***** **
>
(Nit) Also need to check what happens if you rotate these shapes
by 90 degrees.
> Thus, A" must have 5 or more squares.
Suppose each row of A" is a single strip of stars, without gaps,
denoted *???* , then *???* concatenated with ** is the same as ** concatenated
with *???* . We can do this for each row, and hence have constructed an
ambiguous shape. Therefore, there exists a row of A' with a hole in it.
The smallest such shape, unique up to relection, is:
* *
***
Note that the top row is such that {**, *_*, _} satisfy the u.p.c,
and that from the parsed top row we can parse the top shapes uniquely, as
discussed in -.2, so this *is* A".
[Btw, I have realized that there are quite a number of questions and
topics which I looked at but didn't or couldn't solve, and where there are
still questions open. I will go into 'retrospective mode' for a while to tidy
some of them up. I hope to look at: 7,624,834,836,865,886,913,914,975,982,
1041,1095,1098,1149,1153,1154, if anyone cares to anticipate me.]
Andrew.
|