Welcome to the 2020 Mathologer Christmas video.
What a crazy crazy year. Right? Well let me finish off this crazy year with a really crazy video.
An intro to why physicists and mathematicians love playing dominoes. And we'll finish the
craziness with an explanation of the mysterious arctic circle theorem. Pretty sure you've
never heard of that one before, have you? But whatever it is arctic circle theorem
has a great Christmasy ring for our video, doesn't it? As a warm-up let's start with an
absolute classic: the mutilated chessboard puzzle. It goes like this: remove two opposite corners of
a chessboard, say those ones there. Can you tile this mutilated chess board with dominoes that
are just big enough to cover two squares? Well let's go for it and give it a try.
Pretty straightforward to start with. There, okay put that one, that one, that one, get a bit
stuck there, so move this one over. All right and then that one and that one and now we're stuck.
No matter what we do at this point we'll never be able to complete a tiling of our mutilated
chessboard. There doesn't work, doesn't work. We can repeat this as many times as we want from
scratch and we somehow never succeed. There, no luck. No luck again. And again. Very annoying
but did you notice that all of these failed attempts have something in common? Again look
at the previous one and the one before that. See it now? What all these failed
attempts have in common is that we are always left with two black squares.
Coincidence? Hardly :) so why is that? Well let's have a close look at the eight
times eight chessboard we started with. It's actually very easy to tile this
chessboard. For example like this. Okay now here's the thing. When we place a domino
on a chess board so that it covers two squares the two squares must be of different colours. They are
black and green or here, black and green. So one domino covers one black and one green square, two
dominoes cover two black and two green squares, three dominoes cover three black and three green
squares and in general a bunch of dominoes always cover the same number of black and green
squares. Can you guess where I'm going with this? Well the whole chess board can be tiled.
This means it contains the same number of black and green squares. 32 black and 32 green to be
precise. But you all knew this already right? But now when we mutilate the chessboard we are
removing two green squares there, they're gone. But this means… well what does that mean?
Well it means that the number of black and green squares is no longer equal. There are
now two fewer green squares than black ones and that proves the mutilated chessboard cannot
possibly be tiled. What a beautiful argument and how incredibly powerful don't you think? And think
of the alternative: how else might you prove that the mutilated board cannot be tiled? Just try all
the zillion impossible ways of tiling? Maybe not. This also explains why in our failed attempts we
always end up with two leftover black squares. But of course this nice parity
argument shows a lot more. The argument also proves that any mutilated board
with differing numbers of black and green squares cannot be tiled. Really easy to see right? There
more black than green squares so cannot be tiled. We can be sure just like that no mucking around
and no actual tiles required. Marvellous! Too easy? Okay let's make it trickier. What if we take
our full chess board and carve out one black and one green square? For example, let's choose these
two squares. Then the resulting board definitely has the same number of black and green tiles.
Can the resulting mutilated board be tiled? Hmm what do you think? Maybe pause the video
and give it a try. Well the answer is: yes, can be tiled. In fact no matter what
black and green square we discard the resulting mutilated board can always be tiled. And there's
also a really ingenious way to see this. Have a look at this. This is a round trip that visits
every square of our chessboard exactly once. Now the two squares we are carving out cut
this round trip into two parts. And now what? Can you guess what I'll say next? Well we can tile the mutilated chessboard by
tiling along those two parts like this. Easy right? And the special thing is this always
works no matter which black and green squares you choose to remove. Why? Well, first cover the
black square then all the green squares are an even number of squares away. There, zero squares
away, two squares away, four squares away, six, and so on. This means that when you carve out
that second green square there will always be an even number of squares between the holes along
the paths that can be covered with dominoes. And of course this works both ways. Easy. I just
love this stuff. Okay time for an easy challenge for you. Don't trust me? No, really, this one's
really really really easy. What if we cut out four squares two black and two green? Will you always
be able to tile the resulting mutilated board? Leave your answers in the comments. Okay
nice puzzles but is there more to this. Well, there's a lot more. Turns out that
domino tilings are important in physics. How? Important as the simplest possible model for
certain natural phenomena. Think of the squares of a grid as atoms. Now these atoms randomly form
two atom molecules, so they form domino molecules and these dominoes tile the grid. What
does such a random tiling look like? Can we detect any interesting structures in these
random tilings that mirror related structures in nature? What does what we find tell us about
nature? So today's mission is to let you in on three plus amazing and important domino tiling
facts that mathematicians and physicists have discovered and that hardly anybody apart
from the experts will ever have heard of. Youtube youtube premieres all
around as far as I can tell. One of the most amazing bits of mathematics I
know is the formula for the number of tilings of rectangular board. A version of this formula
was first published in 1961 by the physicist Piet Kasteleyn. What a stare! Kasteleyn clearly
takes his work very seriously doesn't he? Okay are you ready for Kasteleyn's crazy formula?
All right, pay attention Kasteleyn's watching you. Whoa what does it even mean and what's all the
triggy stuff doing in there? Shouldn't the number of tilings be a whole number a plain old integer?
Well clearly I have a lot of explaining to do. First to see how the formula works let's use it
to calculate the number of tilings of a standard eight times eight chess board. So we set all the
m's and ends in the formula to be 8 there. now a bit of calculation eight divided by two that's
four. We can ignore the strange brackets around the fours because four is an integer. They are
there just in case one of the side lengths of your board is an odd number say nine. Then you'd
get four point five at this point and the brackets would tell you to round up to five. In short
the four with brackets is just a plain four. Okay and that's a nine of course. Now the
monster symbols in the green box those guys are Greek letters they're capital pi’s and
they're telling us to take a product to multiply. So in the expression on the right we have to
substitute the numbers from one to four for j and k in all possible ways and then we have
to multiply the resulting numbers together. Okay start at the bottom if j is equal to
1 and k is equal to 1. Then we get this right. If j is equal to 1 and k is
equal to 2 then we get this, and so on. There, four times four that's 16 trig
monsters in total. Next compute the monsters. Oh yucky all of these numbers except for the
rogue 2 are irrational. Now comes the miracle when we multiply these numbers together all
this irrationality cancels out and we get yep 12 million and change a perfect integer, the
number of domino tilings of the 8 times 8 board. What an unbelievably crazy formula. And all this
irrationality cancelling out happens for boards of any dimensions. Also worth a mention: if both n
and m are odd numbers, then the m times n board has an odd number of squares and can therefore
not be tiled with dominoes and, yep, in this case the formula up there will spit out 0 as the
answer. Can you see at a glance how this works? That's your second challenge. Amazing, amazing, amazing but it gets even more
amazing when you have a look under the hood. What makes this formula tick is a super nifty way to
calculate the number of tilings of just about any mutilated chessboard not just rectangular ones.
Let me also quickly show you that. Now we start with a checkerboard of any size and draw a loopy
path through the squares like that. All we care is that the region on and inside the loop contains
an equal number of green and black squares. Notice that obtaining regions this way
ensures that there are no holes in the middle. This particular region has 11 green squares and
11 black squares. We want to calculate how many domino tilings there are. To do this first number
the black squares from 1 to 11 any way you want. Similarly number the green squares. Now
we record which black squares and green squares are neighbours and we do this in a square
table. Okay if two squares end up side by side then this is recorded as one. So in
this case green four and black eight there put a one. And here are the other ones.
Yeah there's obviously quite a few of them. Right okay. Each stacked pair is assigned the letter
I. So for example the stacked pair there's an i. What does the I stand for? Intersection I hear
you say. Nice try :) no I stands for, I stands for our good old friend the complex number I whose
square is -1. I told you it was crazy. Don't worry and just run with it for the moment. Anyway here
are the other i's corresponding to stacked pairs. Also quite a few, right. What about the other
spaces in the table? They stand for pairs of squares that are not neighbours and are
therefore all equal to … what do you think? Well 0 of course! Now add some brackets
and our table becomes a matrix. If you've seen matrices before you can probably
guess what comes next, right? There is this one magical way to distill all the entries of a
matrix into one very useful number the so-called determinant of the matrix. And if you calculate
this particular determinant over there you get … minus 88 i. Yep there's minus 88 I ways to tile
that region. Wait what? That can't be right! But it's almost right. Just zap the minus sign
and the I leaving the 88 and 88 really truly is the number of ways to tile that region. Now
that is real mathematical magic isn't it. And with what I've just told you you can
calculate the number of tilings of almost any weird shaped board you fancy. So just assemble
the matrix which is a no-brainer and then ask your fancy CAS calculator or Wolfram Alpha to
compute the determinant. Then your answer might have a minus sign or an I but just zap them if
they're there and you have the number of tilings. Of course for really small examples like
the tiny two times two fellow over there many of you will be able to calculate the
determinant by hand. Here the only thing to remember and the only thing that's ever used is
that I squared is equal to minus -1. Which reminds me here's a third challenge, a very nice one for
you. Calculate or enumerate by hand the numbers of tilings of the small two-by-something boards.
Two times one, two times two, two times three, and so on. Can you spot a simple pattern in the
sequence of numbers you get? A really nice aha moment is waiting for you, so don't miss it.
And as usual record your ahas in the comments. For the super keen among you at the end of
the video I'll show you a proof for why the determinant trick works and say a little bit
about how to derive Kasteleyn’s crazy formula from all this. Tristan one of my super cluey maths
checkers gave me a Christmas present a new pair of glasses. What's special about these glasses is the
number of ways it can be tiled. Challenge for you. What's that special number? Leave your answer
in the comments. Notice that this mutilated board has holes so it is not of the type that
we’re promised the determinant can handle. Having said that while this determinant
does not give the answer straight away it does contain it in a very strange way
anyway. Well if you are a bit crazy yourself also give calculating this determinant a try.
Well another one or two unmissable aha moments await the keen among you. Again don't miss
it and leave your answers in the comments. Okay for our next showstopper let's look at the
randomly chosen tiling of some square boards something you'd expect to come up if the tiling
arose in nature. Like that one there. Yep pretty random. Is there anything to say about it? Well
there are a couple of noteworthy features. For example there are lots of these long fault
lines. Let me highlight a couple for you. There the tiling even has one fault line that
cuts all the way through. There that one there. Interesting isn't it? I guess in nature it's
along those fault lines that things crack. What else can we see amidst the randomness. Well
let's distinguish the tiles that are lying down from those that are standing up. Here we get these
large connected regions of blue and orange. Neat. For this tiling you can walk all the way from left
to right just by stepping on the orange tiles. In nature it could also be significant. Also in a
random tiling we'd probably expect about half each of blue and orange which is exactly what
we see in this example. Okay now we'll use more colours to distinguish the tiles further. So let's
highlight the underlying checkerboard pattern, there. Okay for standing dominoes there
are two possibilities either the top half of the domino covers a black square or the
bottom half covers a black square right. I'll colour these two types of
standing dominoes using orange and red. I'll colour the two types of lying down dominoes
blue and green. Now for the whole board. On closer inspection we notice that regions of
one colour highlight brickwork pattern within the tiling. I guess in nature these regions
would correspond to parts of the structure that are particularly stable to
cracking perpendicular to the layers of the brickwork. Whatever. Now these
patches of brickwork are not particularly significant for the tiling of square boards
but the significance becomes evident in a very surprising manner when you ponder random tilings
of certain mutilated boards. Have a look. Amazing right? But what did we just witness?
Well what I just showed you were random tilings of the so-called Aztec diamond boards of
increasing size. Let's have a closer look. Here's the smallest Aztec tiling, known as A(1)
not very diamondy, I know, but it's coming. Here is the second Aztec diamond board A(2), the third
and the fourth Aztec diamonds are obtained by cutting the corners of square boards with even
side lengths. That's our eight times eight board again chop off the corners et voila that's
the order eight divided by two is equal to four, the order four Aztec diamond. Now it
turns out that random tilings of large Aztec diamonds like the ones I showed you in the video
feature those large regions of completely regular brickwork tiling in the corners and the roughly
circular chaotic region in the middle. So the regularly tiled regions in the corners are called
the frozen regions. Okay. And the boundary of the chaotic region in the middle is called the arctic
circle. In fact the arctic circle theorem says that if you push all this to infinity this is
the picture you get. So one more more and more infinity. A perfect circle inscribed in a perfect
diamond, you did not see that one coming right. And of course right in the middle of the
arctic circle is the north pole and Santa Clause which is why I thought this would make
a great topic for this 2020 Christmas video. One final amazing feature of Aztec diamonds: as
we've seen the formula for the number of ways to tile rectangular chess boards is a monster. But
the formula for the number of tilings of Aztec diamonds is super simple and super super pretty
and also super mysterious. All really fantastic stuff but of course this is Mathologer not
the discovery channel. So even though it's Christmas we won't be content until we dug into
the why have a sip of eggnog and let's get to it. The Aztec board over there has on the order of 10
to 447 tilings. How do you find a random tiling of this board? Well there's the Homer Simpson
method first make printouts of all these different tilings then put them together in a very big hat.
Now cover your eyes and dip into the hat and pick one. It's almost certain that your tiling will
look something like the tiling over there with an arctic circle in the middle. Almost certain
but not 100 % certain. There are also quite a few tilings in the hat that don't feature
any circles. For example this straight across brickwork tiling is one tiling that's also there.
Same with the straight down brickwork tilings that one. It's just that for large Aztec
diamonds the number of tilings without a circle is vanishingly small and so by picking one
at random we can be almost sure to see a circle. Of course there are a couple of problems with
our Homer Simpson random tiling generator :) for starters it's a bit tricky to print out all
10 to the power of 447 tilings of this board, not to mention finding a hat
large enough to put them in, right? No computer in existence can count to
10 to the power of 447 let alone do something substantial that many times. So how did
we find this random tiling over there? Well the key to finding these random tilings and
to the arctic circle theorem and to proving the beautiful formula for the number of tilings
of Aztec diamonds and to life the universe and everything is an absolutely magical way
to grow all tilings of all Aztec diamonds from the starter baby diamond. Let me show you.
Get ready for something really truly amazing. So we start with the smallest Aztec
diamond which is just a 2x2 board. There are two ways to tile this
board, this way and that way. Okay let's start with this one, doesn't
really matter. Now decorate the tile with arrows like this. The important thing
here is that the arrows are pointing out in opposite directions. Okay let's extend this
first Aztec tiling into the second one like this. Move the tiles one step in the direction of
the arrows like this. Two 2x2 regions appear. We fill these two by twos with pairs of
arrowed tiles, either like this or like that. Same for the other two by two. Either
like this or like that. Let's go with the pair of choices over there. Okay
now we have an arrowed tiling of A(2) extend to A(3) there. Now move all the dominoes
one step in the direction of the arrows. Pretty magical :) now three two by twos appear.
Again for every one of these two by twos there are two choices for filling them with pairs of arrowed
dominoes. Let's go for these choices there. All right expand to A(4). Now at this stage we cannot
slide straightaway because there are some arrows pointing towards each other, there.
Remove those clashing yellow tiles. Now slide. More magic and more
two by twos. Fill them randomly and repeat. There next diamond. Find the
pairs of clashing tiles and get rid of them. Move. Fill in the resulting two by twos randomly. Magic. And so on as far as you wish. Now this is
not obvious but all of the individual steps that are indicated will always work. In particular
dominos will never end up overlapping after the sliding phase and at the end of the sliding phase
the region left to be filled is a collection of two by twos, and so on. But even more is true.
All tilings of all Aztec diamonds can be reached from the basic diamond like this and by always
randomly filling in those two by twos we are creating random tilings of the various
diamonds in an extremely efficient way. That movie of the random tilings of those
growing Aztec diamonds I showed you earlier was generated this way. Now again it's not
at all obvious why any of this is true but once you know that this is what you're aiming
for, the proof is actually not that difficult. I won't go into details here but I will
leave some pointers to the nitty-gritties in the description. Okay I can't resist
the key to understanding the dance is the fact that the arrows are always pointing
at the vertices of this tilted square grid. A bit mysterious but let's leave it at
that. Anyway for the rest of the video let's just assume that this magical square dance
really works as advertised and use it to first derive the wonderfully simple formula for the
number of tilings of Aztec diamonds and second get some intuition for the arctic circle
phenomenon. Formula first. Okay so what we want to show is that these are the numbers of tilings
of the Aztec diamonds. Two to the power of one, two to the power of one plus two. Two to the
power of one plus two plus three, and so on. Of course the fact that the first diamond A(1)
has exactly two tilings is completely obvious. Then the idea for the proof is to argue from
top to bottom by what is called induction. So we'll start with the fact that A(1) has two
tilings then since all tilings of A(2) come from tilings of A(1) by the dance we'll check that
A(2) really has 2 to the power of 1 plus 2 tilings then since all tilings of A(3) come
from twilights of A(2) by the dance we'll check that A(3) really has two to the power
of one plus two plus three tilings, and so on. Now for the details. Clearly for the smallest
Aztec diamond A(1) there are two different tilings and our magic shuffle produces these tilings like
this: first interpret A(1) as one of those orange two by twos and then fill this two by two with
the arrow pair of tiles in the two different ways so there are two different tilings and of
course two is equal to two to the power of one. Works. Next, extend to A(2). Okay when we
extend like this we add one two times four okay there two times three times and four
times okay and of course these two times four extra squares turn into two orange
two by twos after shuffling. There. And as usual every one of the orange two
by twos can be filled in two different ways and so both the left and the right diagram turn into two
times two that's two to the power of two tilings. Easy so far right. And so there are a total of two
to the power of one times two to the power of two equals two to the power of one plus two different
tilings of the second Aztec diamond A(2). Very very nice don't you think. And i'm
sure you can guess how this continues. Anyway, let's just go for it and figure out the
number of tilings of the next Aztec diamond A(3). So let's extend. There, we're getting an extra
one two three times four extra squares. After the moving phase these three times four squares
will usually turn into three orange two by twos like here. Okay as usual there are two ways
each to fill these two by twos that means the total of two times two times two is equal to two
to the power of three tilings corresponding to this diagram. If all this worked out the same for
all tilings of the A(2) then this would give us a total of 2 to the power of 1 plus 2 times 2 to the
power of 3 equals 2 to the power of 1 plus 2 plus 3 tilings, exactly what we want. And we really
do get three orange two by twos in most cases. There. In the remaining two cases we have pairs
of colliding tiles appearing. Remember we have to throw away these colliding tiles in order to
continue. So let's throw them away. Now move. Four instead of three orange two by twos. But doesn't
that mean we'll get more tilings than we want? Well we don’t. Can you see why? Have a
close look at those two special diagrams. Can you see it? Of course you can.
Both of these diagrams are identical. What made them different was the
yellow bits that we threw away. We can make them different again by filling in one
of the orange squares in the two different ways. All right and at this point it's three orange two
by twos each and by filling them in all possible ways we get all two to the power of one plus
two plus three tilings as we've been predicting. Fantastic and arguing in the same
way to infinity proves the formula. One of those proofs that made my day when I
first found out about it. How about you? Like it? Of course it's also possible to calculate the
numbers of tilings of individual diamonds using the determinant trick? But i'm not sure whether
anybody has succeeded in actually deriving the full formula just using the determinant
and if so how complicated the proof is. Maybe another challenge for the real math
masters among you. Also for the programmers among you can you please implement the magic
square dance that includes all the steps extending filling the two by twos randomly and
zapping. There's really nothing out there at the moment that brings all this magic to life
which is a real pity. So do something about it. On we track towards the arctic circle. First we
have to navigate the surrounding frozen regions. Using our crazy dance it's not difficult to
see that these regularly tiled regions should be present in the corners for the vast majority
of tilings of large diamonds. Let's just focus on one of the tips. At any stage of
the dance there are only two ways in which these two end squares can be
covered. Either this way or that way. Suppose that “this is the way” :) i've been
watching something with my kids as you can see. So that the right tip is covered by one
single domino. Then that will be the case at the next stage and then the next stage and so
on forever. Do you see why? Well when we expand to the next larger diamond and move, then
the right tip of the larger diamond will be occupied by the same domino. Okay now what
if the right tip is covered the other way, like this. Then after expanding and moving we
get an orange two by two in the corner, right. Filling this two by two randomly with an
arrowed pair of domino tiles gives a 50:50 chance of a domino ending up in the tip, like
this which will then persist forever in the tip. If the pair ends up being oriented the other
way we get another 50:50 chance of ending up with a domino in the tip at the end of the next
growth step, like that. Okay let's expand again. Another orange thing, and so on. This shows that
after a few growth steps it's almost certain we'll have a single domino covering the tip.
We can continue to argue similarly to convince ourselves that as the diamonds grow there will be
a buildup of regularly tiled dominoes at the tips. Notice in particular that any buildup
like this will persist forever and ever. There. Right? This whole collection of dominoes
just moves as a whole to fill in the empty squares opening up on the right. And of course
the same thing is true for all the other tips. Oh and you probably already figured this
out yourself, the four different colours i'm using correspond to the four different
directions in which the arrows are pointing. Anyway given that our dance generates random
tilings of these diamonds I think it's clear where those frozen regions in the
corners of most tilings come from. Of course we're still a long way away from seeing
why the crazy chaotic region in the middle should be roughly circular and why it should become
more and more circular but that's really very nitty gritty technical stuff and I won't go into
any more detail in this respect today. Again there are links in the description for those
of you inspired to follow this particular rabbit hole. The wonderfully simple formula
for the number of tilings of Aztec diamonds was first conjectured by the physicists grenzing,
carlson and supp and goes back to 1979. In 1991 the mathematicians Noam Elkies, Greg Kuperberg,
Michael Larsen and James Propp published a number of proofs of this wonderful formula.
In their paper they also introduced the crazy dance which they called iterated shuffling and
used it in one of their proofs of the formula. The arctic circle theorem was published in 1995
by William Jockusch, James Propp and Peter Shor. Truly magical mathematics just right
for a Christmas video don't you think? To finish off let me tell you about
another type of super pretty arctic circle on another type of board and I'll give you
a really amazing puzzle to round things off. Our new game is played on boards that
are subdivided into equilateral triangles and the dominoes we're using are made to cover
two of the equilateral triangles. These dominoes look like this. Boards like this can also be
checkerboarded. Ooh Christmas tree. Anyway this means that as before mutilated boards that can be
tiled necessarily contain the same number of green and black triangles, right? There's also the
determinant formula that will give you the number of tilings for these new boards. This formula is
even nicer than in the square case in that every pairing is recorded by a one no complex nonsense
required. For example the number of tilings of a small hexagon-shaped board can be calculated
like this. So only 1s in the matrix and no I s. The counterparts of the Aztec diamonds in
this world of triangles are the boards that are shaped like hexagons. The one over there
is the smallest example. Here is a larger one there. Just like for the Aztec diamonds
the formula for the numbers of tilings of regular and irregular shaped hexagon
boards turns out to be super duper nice. There fantastic no nasty trg stuff inside. The
tilings of these boards have their own surprises in store for us. Take a look. Looks almost 3d
doesn't it? Well we can make it look even more 3d. There are essentially three different orientations
of our domino on this board. This, this and this orientation. Let's colour the different
oriented tiles in three different colours and whoa now it's really 3d. And this 3d is more than just
an illusion we can interpret these diamond tilings in terms of special stacks of cubes and this
interpretation leads to all sorts of nice conclusions. Now let me show you a randomly chosen
tiling of a larger hexagon. Can you see it? There another arctic circle is starting to materialize
and again in the limit it can be shown that things will look like this. Of course I could go on for
a couple more hours dishing out further arctic delicacies but I think it's already been plenty
of treats for one day. Instead let me give you one more beautiful puzzle to ponder all right? Ready?
Since this is a random tiling we'd expect roughly the same number of tiles of each colour, right?
Now here's something interesting. It turns out that there are exactly equal numbers of orange,
gray and blue tiles in every single tiling of any regular hexagon board like this. And that's
the puzzle for you. Why is this obvious? Hint: this is literally a case of thinking inside the
box. As promised there will be a mini master class after acknowledgments for those of you who want
to dig even deeper into the determinant magic. But for those of you who need to get to a Christmas
or new year's eve party that's it for today. Thank you all for watching these videos and for
your support over the years. Thank you, thank you, thank you, thank you, thank you to marty eddie
and Tristan for all your help with Mathologer and to jim Propp for his expert advice on
all things arctic. I wish you all a merry Christmas and I'll see you back in the new year
for what is hopefully a much less crazy 2021. You're still here for the mini master class.
Well that's great. That definitely gets you another Mathologer seal of approval. I hope
you took a little break had a cup of coffee or hot chocolate and are ready for a dash
up a snow-covered mathematical mountain. As promised I'd like to show you why this
determinant gives the number of tilings. I'll start out easy but you really need to know
a little bit about determinants of two times two and three times three matrices to be able to
appreciate everything I'll say in the following. Anyway did you already complete your homework and
calculate the determinant of the two times two board? Well okay then let's check your homework.
Remember this simple two times two board has two tilings here and there. We already had this couple
of times. The corresponding matrix is a nice manageable 2 times 2 which as many of you will
remember evaluates to 1 times 1 minus I times i. Now of course I times I is equal to minus one and
so one minus minus one is two, two tilings. Great. But just by looking at this expression
we can get a fairly good idea of the mathematical trickery that makes this work
remember that the two ones in the matrix stand for pairs of side by side squares,
these two. And then the one times one equals one in the determinant formula counts
this one tiling over there. All right. On the other hand the i's in the determinant
stand for the vertical ways of placing dominoes and the I times I in the formula records the
second tiling here. Okay so one term of the formula per tiling and of course I times I
being equal to -1 compensates for the minus in the formula for the determinant. Great. Also
if you start by labelling the board like this a bit different then the end result of the
calculation is minus two. So the two gets decorated with a minus sign. This illustrates that
the output of the determinant depends a little bit on the way you label the board. As I already
said the difference is just an extra minus sign or i. The positive integer, in this case 2,
is what counts. It's the number of tilings. Of course the two times two matrix is special
and deceptively simple in the sense that it does not have any zeros. So let's go the next step
and have a look at the two times three board. Remember one stands for side by side neighbours,
I stands for stacked neighbours and 0 for not neighbours. Now to get a sense for what is going
on let's have a look at the general formula for 3 times 3 determinants. So the matrix has nine
entries which are labeled by the row and column they are in. There that's the entry in the
second row and the third column. So how is this formula built? Well there are six terms half
of which are plus and the other half minus. Okay in every term three entries of the matrix
are multiplied together one from each row. There first second and third row and one from
each column one, two, three is also there. There one from each column one from each row,
one from each column … okay all good. Clearly there are permutations at work here, namely the
permutations of one two and three, here they are. That's all six of them and a term gets a plus
sign if its associated permutation is even. Those on top are the even ones. A term gets a
minus if its permutation is odd. Those are the ones at the bottom. Also remember when
you swap two symbols in a permutation, odd permutations turn into even permutations
and vice versa. Swap one and three in the odd permutation one three two and you
get the even permutation three one two. Swap two and one in the even permutation two three
one and you get the odd permutation one three two. Nifty stuff huh. All determinant formulas for
n times n matrix are built the same way. In particular the n times n formula has n factorial
terms, each consisting of n factors. Half get a plus half a minus, odd even and so on. I know
quite a bit to remember and quite abstract. Well the nuts and bolts of determinants are what
they are. Luckily things are about to get reassuringly tangible again. Let's have a look at
the particular determinant we want to evaluate. There are two zeros. Remember
these correspond to two squares each that are not neighbours. These zeros wipe
out all the terms of the formula they appear in. Right zero times whatever else is
there in those terms is just zero. Three terms have survived the attack of the zeros
and each of these corresponds to one tiling of our board. There one one, two two and three three
okay. And one one, two three and three two and one two, two one and three three. Very
nice. So one tiling per term that survives after the zeros did their wiping. And since we
run through all possible pairing permutations, it's also clear that we get all tilings this way
right? Now because all the three factors in the individual terms are either 1 or I and I squared
is minus 1 every term will either end up equaling 1, minus 1, I or minus i, right? So those are
the possibilities and of course since we have 3 tilings and 3 terms, for the formula to work
we better get the same answer for each term. All three terms equaling one will add to three,
and three minus ones will add to minus three, and so on. All conveying the same
essential information, three tilings. Let's focus on the term that's highlighted at the
moment. There are two horizontal tiles giving ones and one vertical tile gives an I there. And
the blue minus in front comes from the fact that the associated permutation 2 1 3 is
odd. This means that this term is equal to minus 1 times 1 times I so equal to minus i. So
why are all the other terms also equal to minus I? Here comes the nifty part. Take this two by
two block and twist it. That changes the two horizontal ones the two vertical i’s whose product
I times I is minus one right. And now in terms of the green permutation two one three the twist of
the two times two amounts to a switch of the green two and the green one. This means we're going
from an odd permutation to an even permutation and so the sign of the permutation switches.
Effectively we're multiplying by another minus one. So the net effect on the value of the term is
minus one times minus one which equals one, which means that the value of the term does not change.
In total twisting the two by two takes us here. Okay double check. Yep that's the term
that corresponds to the new tiling up there and its value is plus I times I times I which
equals minus i. Very nice and nifty. What about the remaining term? Well taking the second
2 times 2 block and twisting it gets us to the third tiling. Again the net change is minus
1 times minus 1 equaling 1 so nothing changes and that means that all three terms are equal
to the same number minus i. And it turns out that this going from tiling to tiling to tiling
with these two times two twists works for all mutilated boards under consideration. What
were these again? Remember we took any loop on a checkerboard without self-intersections and
we just had to ensure that the loop contains the same number of green and black squares like
that. Then it turns out that any tiling can be changed into any other tiling with a sequence
of these two times two twists and as we're going from tiling to tiling in this way we are proving
at the level of the determinant formula that all its non-zero terms are either all one, all minus
one, all I or all minus i, which then proves that the determinant formula works for these sorts
of boards. Very pretty proof don't you think? So to summarize after the non-neighbour zeros have
done their zapping of terms, there will be exactly one non-zero term tiling left over. And the fact
that we can transform any tiling into any other tiling via these two times two twists implies
that all of the remaining non-zero terms are equal which then proves that the determinant
gives the number of tilings. Nice nice. Now the determinant formula also works for some
other mutilated boards but doesn't work for many others that feature holes. For example as I
already mentioned it does not work for Tristan's glasses at least not straightaway. Having said
that, as is often the case with maths what I just described may seem pretty complete but is
really just the tip of a humongous iceberg which also contains more sophisticated versions of
the determinant trick that can count the number of tilings of any mutilated boards including those
with holes. Obviously I was really going for it in this little master class and you definitely
shouldn't feel bad if you did not get everything. If you got lost at some point, maybe go over
everything a second time, maybe even a third time, really worth it. Finally a few words about
how Kasteleyn’s formula up there is derived using the determinant trick. For those of you
knowing a bit of matrix algebra you'll know that the determinants of many square matrices
are just the products of their eigenvalues and Kasteleyn’s formula really is a product of
eigenvalues. However it's not the eigenvalues of our matrices but of some close related
matrices. Another level of trickiness. Again if you're interested in the details I'll link to
a nice article by jim Propp that explains it all. Enough for today? I sure think so! After this
crazy year and yet another video marathon I really need a long long long holiday. As usual,
please let me know in the comments which parts of this video you liked best. What worked for
you and what did not work for you. Stay safe!
I believe there is a simple intuitive perspective on the arctic circle theorem. Consider only the periphery of a tiled aztec diamond (i.e. the tiles that touch the outside). It is clear that on each of the four sides, the frozen regions must touch; otherwise you'd get holes in the tiling.
The spots where the frozen regions touch have gaps which are filled by the four "corners" of the chaotic region. In theory these contact points could be anywhere on each side, so why do we expect them to usually be in the middle? Having them in the middle makes the chaotic region as large as possible, which gives more ways to fill in the chaotic region (higher entropy). When the contact points are far from the middle, the chaotic region has a small area, so there are only a few ways to make tilings that look like that.
It's not clear from this why the chaotic region has to be a circle, but neither is it surprising that that's the arrangement that maximizes the area of the chaotic region.
The brilliant thing that I took away from this was that all tilings could be reached from each other by successively twisting 2x2 elements, and that you could encode the twist of a 2x2 tiling as a multiplication by 'i'. The imaginary unit naturally encodes a 90 degree rotation but the interplay with odd permutations in the determinant was really clever.
One of my favourite maths youtubers
I am a little confused by the boundary here. If I just focus on one corner, say the north corner, then isn't there only a 50% chance of the very corner being filled by a blue tile instead of 2 red ones, independent of how large the aztec diamond is? In what sense is this an "almost all" statement?
Oh wow my advisor makes a brief appearance in this video: he was one of the authors of the Aztec diamond paper. Didn’t expect that lol
does anyone have the arctic circle theorem in sage code? or any advice how to start making it?