The ARCTIC CIRCLE THEOREM or Why do physicists play dominoes?
I only stumbled across the amazing arctic circle theorem a couple of months ago while preparing the video on Euler's pentagonal theorem. A perfect topic for a Christmas video.
Before I forget, the winner of the lucky draw announced in my last video is Zachary Kaplan. He wins a copy of my book Q.E.D. Beauty in mathematical proof.
00:00 Intro
00:35 Chapter 1: mutilated chessboards
07:23 Chapter 2: Monster formula
15:12 Chapter 3: Aztec gold
20:07 Chapter 4: Square dance
30:41 Chapter 5: Ice
34:35 Chapter 6: Hexagon
38:25 Credits
40:46 Mini masterclass
In response to my challenge here are some nice implementations of the dance:
Dmytro Fedoriaka: fedimser.github.io/adt/adt.html (special feature: also calculates pi based on random tilings. First program contributed.)
Viktor Chlumský • Aztec Diamond Procedur... (no program but a VERY beautiful animation made with the software Shadron by Victor)
Cannot fit any more links in this description because of the character limit. For lots of other amazing implementations check out the list in my comment pinned to the top of the comment section of the video.
For the most accessible exposition of iterated shuffling that I am aware of have a look at the relevant chapter in the book "Integer partitions" by Andrews and Eriksson. They also have a nice set of exercises that walk you through proofs for the properties of iterated shuffling that I mention in this video.
I used Dan Romik's old Mac program "ASM Simulator" to produce the movie of the random tilings of growing Aztec diamond boards www.math.ucdavis.edu/~romik/s... Sadly this program does not work on modern Macs.
The arctic heart at the end of the video is a "chistmasized" version of an image from the article "What is a Dimer" by Richard Kenyon and Andrei Okounkov www.ams.org/notices/200503/wh... Thank you for letting me use this image.
Around the same time that Kasteleyn published the paper I showed in the video, the physicists Temperley and Fisher published similar results, Dimer problem in statistical mechanics-an exact result, Philosophical Magazine, 6:68, (1961) 1061-1063. The way Kasteleyn as well as Temperley and Fisher calculated the numbers of tilings of boards with square tiles was a bit more complicated than the nice refinement that I show in the video which is due to Jerome K. Percus, One more technique for the dimer problem. J. Mathematical Phys., 10:1881-1888, 1969.
Some great articles and websites to check out:
A very accessible introduction to domino and other tilings by Federico Adila and Richard Stanley www.claymath.org/library/senio...
An accessible article about tilings with rectangles by my colleague Norm Do at Monash Uni. In particular, it's got some more good stuff about the maths of fault lines in tilings that I only hinted at in the video:
users.monash.edu/~normd/docume...
A nice article about Kasteleyn's method by James Propp. Includes a proof of the crazy formula arxiv.org/abs/1405.2615
A fantastic survey article about enumeration of tilings by James Propp. This one's got everything imaginable domino and otherwise. Also the bibliography at the end is very comprehensive faculty.uml.edu/jpropp/eot.pdf
An introduction to the dimer model by Richard Kenyon
arxiv.org/abs/math/0310326
Alternating sign matrices and domino tilings by Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp arxiv.org/abs/math/9201305
Random Domino Tilings and the Arctic Circle Theorem by William Jockusch, James Propp, and Peter Shor arxiv.org/abs/math/9801068
A website by Alexei Borodin full of amazing 3d representations of domino tilings. A must-see math.mit.edu/~borodin/aztec.html
James Propp's name pops up a couple of times throughout this video and in this description. He's one of the mathematicians who discovered all the beautiful arctic mathematics that I am talking about in this video and helped me get my facts straight. Check out his blog mathenchant.org and in particular in this post he talks a little bit about the discovery of the arctic circle phenomenon mathenchant.wordpress.com/201...
As usual the music in the video is from the free KZhead audio library: Night Snow by Asher Fulero and Fresh fallen snow by Chris Haugen.
Today's t-shirts I got ages ago. Don't think they still sell those exact same ones. Having said that just google "HO cubed t-shirt" and "i squared keep it real t-shirt" ... :)
Jokes:
1. Aztec diamond = Crytek logo; 2. no. tilings of Arctic diamond: 2^(-1/12). 3. ℝeal mathematical magic, 4. (HO)³ : joke for mathematicians (HO)₃ : joke for chemists
Bug:
Here one of the tiles magically disappears (damn :( tinyurl.com/ya6mqmhh
Nice insight:
If all holes in a mutilated board can be tiled with dominoes the determinant will work. Why is that?
Merry Christmas,
burkard
(HO)³ : A Christmas joke for mathematicians (HO)₃ : A Christmas joke for chemists
:)
Brilliant
the chemist version of the joke is very "basic"..pun intended.
A joke for linguists: Carissimus Dei.
Hydroxide, hydroxide, hydroxide!
When he said “what a crazy, crazy year right?” I’ve been conditioned to expect him to say “Wrong!” 😂
Hahahaha yeah
Hahaa
The crazy year means Corona Virus 😭😭😭
"It gets even crazier!"
+++
20:00 Number of tilings of the Arctic Circle: 2^(-1/12). Got it. 😏
:)
#(A(n)) = 2^(n(n + 1)/2), therefore #(A(|ℕ|)) = = 2^(|ℕ|(|ℕ|+1)/2) = = 2^(|ℕ|) = |ℝ|
which is about 0.94
Wait; I got stuck at A2, I see 10 possible tilings, not 8
Riemann with his lame continuations, Mathologer is gonna need his medications, There’ll be trouble in town tonight! You call this steamed ζ(-1) despite the fact that it’s clearly grilled?
I find really wholesome this man's dedication to speak and explain so passionly for 50+ minutes straight. As a phisicist that I am, I love how matematicians like this one continiously inspire us all everytime they can. Keep on the good work, stay amazed and happy holidays!
I love his videos, but he doesn't speak "for 50+ minutes straight". There are many cuts in the video, with unfilmed time between, and no doubt a number of bloopers we never see.
@@jursamaj well, he DOES talk for 50+ minutes straight as a uni lecturer
Merry Christmas! 6:11 - You could pick the two blacks in the top left corner. It would isolate the corner green square, so not every combination of 4 squares removed is tileable. 10:13 - say m = 2p-1 and n=2q-1. The denominators in the cosines will be 2p and 2q. Carrying out the product, when j=p and m=q, we will have a term (4cos²(π/2)+4cos²(π/2)), which is 0, cancelling out everything else 13:50 - Lets say T(n) is the number of ways to tile a 2xn rectangle. First two are obviously T(1)=1 and T(2)=2. For the nth one, lets look at it from left to right. We can start by placing a tile vertically, which will isolate a 2x(n-1) rect. - so T(n-1) ways of doing it in this case. If we instead place a tile horizontally on the top, we will be forced to place another one directly below, so we don't isolate the bottom left square, this then isolates a 2x(n-2) - so T(n-2) ways of doing it in this case. ---- We have T(n) = T(n-1) + T(n-2). Since 1 and 2 are fibonacci numbers, the sequence will keep spitting out fibonacci numbers 14:33 - It's 666. I did it by considering all possible ways the center square can be filled and carrying out the possibilities. It was also helpful to see that the 2x3 rectangles at the edges are always tiled independently. I was determined to do all the homework in this video, but hell no I wont calculate that determinant, sorry 30:12 - I'll leave this one in the back of my mind, but for now I'm not a real math master. I'm also not a programmer, but this feels like somehting fun to program 37:28 - Just look at the cube stack straight from one of the sides, all you'll see is an nxn wall, either blue, yellow, or gray
Very, very good, more than full marks :)
The determinate is also 666 actually. Yes I calculated it.
I feel like I watch this guy 20% for his amazing math demonstrations and 80% for him laughing at his own jokes
same here, it's adorable and endearing. I think that's one thing about the best teachers that I try to emulate, is they all unironically embrace their own cringe juuuust enough to help their audience push past discomfort and really get engaged.
I just realized: for the hexagon, if you turned it into a 3D broken cube, then looked at it from any of the open faces (assuming you're looking directly at the face from a single point), you would see a complete square of one color. This would be the same from all three open sides, and there would be no hidden faces. Thus, the sides being equal, there will always be an equal number of each color domino
I did it like this: with no cubes you have the same number. Everytime you place a new cube it must touch three sides (which get covered) and adds three of its own (aka, all numbers (of each color) stay the same). It is the same argument as yours, of course.
Yes, that is a nice property - and easy to understand from a spatial visualization point of view.
This also means that there is a predetermined amound of a given color in each "column", going 1, 2, 3, 4, ..., 4, 3, 2, 1 (but this works only in one way for each color if I'm not mistaken)
9:45 12 million "and change"?? I'll take your change then, thank you!
:)
more like 13 million minus change
@@SunroseStudios wouldn’t it be 13E6-(1-change).
Ok, can we take a moment to appreciate the slide transition at 25:40? It's magnificent.
Na
For the m x n board with m and n being odd numbers: Since m and n are odd, the denominators (m + 1, n + 1) in the fractions inside cos will always be even. And, since we round up in the expression above the PIs, j and k will in one factor both be exactly half of m + 1 and n + 1 respectively. When this happens we get cos(Pi/2) for both terms. Squaring the cos of course changes nothing. And when the product has one zero factor the entire thing will equal zero. Much fun this one!
Very good :)
I made a graph in desmos to visually see that when m and n are odd that the value is 0. www.desmos.com/calculator/apqualyl52
Yes, I spotted that one (i.e. cos(pi/2=0) as well.
Implementations of the crazy dance: In response to my challenge here are some nice implementations of the dance: Dmytro Fedoriaka: fedimser.github.io/adt/adt.html (special feature: also calculates pi based on random tilings. First program contributed.) Shadron kzhead.info/sun/dqeFZ5t6jKujhpE/bejne.html (no program but a VERY beautiful animation) Charly Marchiaro charlymarchiaro.github.io/magic-square-dance/ (special feature: let’s you introduce a bias in the way the arrowed pairs are generated either with a horizontal or vertical orientation. 100% true to the way I did things in the video :) Jacob Parish: jacobparish.github.io/arctic-circle/ (the first program to feature the bias idea) chrideedee: chridd.nfshost.com/tilings/diamond(special feature: allows to go forwards and backwards) Philip Smolen: tradeideasphilip.github.io/aztec-tiles/ Bjarne Fich: rednebula.com/html/arcticcircle.html The Coding Fox: www.thecodingfox.com/interactive/arctic-circle/ WaltherSolis: wrsp8.github.io/ArcticCircle/index.html ky lan: editor.p5js.org/kaschatz/sketches/GHCkS-FyN Jacob Parish: jacobparish.github.io/arctic-circle/ Michael Houston arctic-circle.netlify.app/ Martkjn Jasperse: github.com/mjasperse/aztec_diamond Jackson Goerner: kzhead.info/sun/fKqGkrGbn5yVjac/bejne.html gissehel webgiss.github.io/CanvasDrawing/arcticcircle.html (require keyboard) pianfensi github.com/Pianfensi/arctic-circle Lee Smith s3.eu-north-1.amazonaws.com/dev.dj-djl.com/arctic-circle-generator/index.html Gino Perrotta github.com/ginop/AztecDiamonds aldasundimer simonseyock.github.io/arctic_circle/ Shadron kzhead.info/sun/dqeFZ5t6jKujhpE/bejne.html David Weirich github.com/weirichd/ArcticCircle Richard Copley: bustercopley.github.io/aztec/ Pierre Baillargeon github.com/pierrebai/AztecCircle Baptiste Lafoux github.com/BaptisteLafoux/aztec_tiling ) Peter Holzer: github.com/hjp/aztec_diamond/ TikiTDO codesandbox.io/s/inspiring-browser-6mq10?file=/src/CpArcticCircle.tsx Christopher Phelps trinket.io/library/trinkets/5b574f6671 Rick Gove artic-circle-theorem.djit.me Before I forget, the winner of the lucky draw announced in my last video is Zachary Kaplan. He wins a copy of my book Q.E.D. Beauty in mathematical proof. Congratulations! Zachary please get in touch with me via a comment in this video or otherwise. I really did not think I could finish this video in time for Christmas. Just so much work at uni until the very last minute and I only got to shoot, edit, and upload the video on the 23rd, a real marathon. But it’s done :) The arctic circle theorem, something extra special today. I’d never heard of this amazing result until fairly recently although it’s been around for more than 20 years and I did know quite a bit about the prehistory. Hope you enjoy it. As usual please let me know what you liked best. Also please attempt some of the challenges. If you only want to do one, definitely try the what’s next challenge. What’s the number of tilings of the 2x1, 2x2, 2x3, etc. boards? Fairly doable and a really nice AHA moment awaits you. And let’s do another lucky draw for a chance to win another one of my books among those of you who come up with animations/simulators of the magical crazy dance that I talk about in this video. Apart from that, I hope you enjoy the video. Merry Christmas, Fröhliche Weihnachten.
Is that the me Zachary Kaplan? Thats very exciting, if so! I really enjoyed this video; combinatorics is one of my favorite subjects, and the arguments used were very clever. Next up on my list is to really read about how that crazy monster formula for the square chessboards is derived!
@@fibbooo1123 It's you :)
@@Mathologer how can I contact you brother
For the hexagon puzzle: looking at the picture as a 3D stack of blocks, it is obvious that each tiling can be gotten by adding one block at a time. This corresponds to rotating a hexagon with side length 1 by 180 degrees. Thus the number of tiles in each color doesn't change. But the numbers are equal when there are no stacked blocks.
Yeah makes sense. If you looked at the stacked cubes from a side, it would be completely one color. Since you can probably build each tileing by stacking cubes it would always be the case.
I got the proof by using the hexagon version of the square dance
@@angelodc1652 That's definitely the easiest way to see its true. How did I forget about it.
First challenge: The chessboard cannot always be tiled after removing 2 black & 2 green. Suppose we remove the two black squares adjacent to the upper-left corner and the two green squares adjacent to the lower-left corner. Then the left corner squares are no longer adjacent to any other squares, so the board cannot be tiled. EDIT: Second challenge: if m and n are odd, then ⌈m/2⌉ = (m+1)/2 and ⌈n/2⌉ = (n+1)/2. Now the j=(m+1)/2, k=(n+1)/2 term of the product is 4cos²(π/2) + 4cos²(π/2) = 0, so the product is 0. Moreover, if m is not odd, then 0 ≤ j < (m+1)/2 in all terms of the product, hence 0 ≤ jπ/(m+1) < π/2 in all terms, so cos²(jπ/(m+1)) > 0 in all terms, so each term of the product is nonzero. This means the formula gives a nonzero answer whenever m is even -- symmetrically, the answer is nonzero whenever n is even. Thus, the formula returns 0 if and only if m and n are both odd.
Beat me to it!
I do wonder if you add the condition that you do not subdivide the board in to uneven boards if it remains possible for the first challenge. I know that with sufficient tiles removed, you can create untileable even boards, but is such a configuration possible with only four removed? I can't think of a way to partition off such a section, but there may very well be a non-partitioned board that would do it
@@BandanaDrummer95 that was my question exactly
the answer to the first challenge was the same as mine by coinendence xD
Third challenge: Fibonacci
First challenge: no, you can cut out the angle of the board
Yes, that was nice doable warmup challenge. Let's see how you fare with the other ones. Some more doable ones but also a killer or two :)
Second problem: cos(pi/2) is 0. If both m and n are odd then m+1 and n+1 are both even and when j=m/2 and k=n/2 both cos terms are 0, since we're multiplying this makes the whole thing 0
@@complainer406 its christmas
but, isn't the rest of the board in your case coverable with dominoes trivially? i mean when all dominoes are oriented in the same way
We need to cover whole board with this angle. Also, the board without it will have an odd number of squares, so it'll be impossible to cover it
The Arctic Circle with hexagons can also be called Q*Bert's Heaven.
Underrated comment
It's 12 : 00 AM in India Looking forward to the following 50 minutes And Merry Christmas!!
same but in pakistan
From India
But I'm watching it 10 hrs later
Those are some pretty non-christmassy glasses if you ask me, you're a beast.
Dunno... I could see Elton John wearing them, allright!
However, near-round glasses are PERFECT! :)
@@dhpbear2 can accept that if a guy who looks like santa is saying that
Fun Fact: If that Hexagon tiling were blocks in Minecraft, then if that represented a sloped hill/mountain in Minecraft, it would be scalable as there is a path from the bottom to the top. Although it's not really obvious that that would be the case.
why is that? and hexagonal prisms? Instead of cubes?
@@averywilliams2140 hexagons are the bestagons
@@averywilliams2140 Visualize the hexagonal tiling as a perspective drawing of cubes.
@@qovro oh shit right. I forgot how beautiful that was
@@qovro like two sheet of hex lattice shifting over one another changing the point in a stack of cubes
Never thought I'd see such a detailed video on this topic. I've heard a little bit about all of these concepts (Aztec squares, Kesteleyn's formula, rhombic tilings, etc.) while watching Federico Ardila's great lecture series on combinatorics on KZhead, and I really think the accessibility of this subject benefits from visual-oriented, thorough, and intuition-driven videos like these. As always, great video.
Hey there Mathologer, I had to share this with you. I presented the first 5 minutes of this video to my 8-year-old daughter, who is now immediately proceeding to find a chess board and make dominoes to experiment. This wouldn't be so remarkable but for the fact that she's never initiated a mathematical exploration, nor shown any interest in doing the same. Thanks for helping me have this moment.
I was wondering what could possibly be interesting about the number of ways to tile the glasses. I couldn't have guessed it would be the number of the beast! I also didn't realise that the number of the beast could be written in a neat little expression involving only the first 4 primes: 666 = 3^2(5^2+7^2)
My favourite number :)
How did you find that one? I’m struggling with it.
@@zacharyjoseph5522 It's a bit tricky to explain without diagrams, but I'll do my best. Let us call the whole shape G for glasses. First consider the pair of 2x3 rectangles at the extreme left and right of the glasses. If a domino is placed which crosses the border between the 2x3 and the rest of the glasses, then the 2x3 is left with a region of size 5, so cannot be covered. We therefore know that the dominoes covering the pair of 2x3 areas are necessarily wholly within the 2x3 areas, so the tilings would be the same if the 2x3 regions were actually disconnected from the glasses. So if we let G' be the glasses without this pair of 2x3 regions and if we let N be the function counting the number of tilings of a shape, then we have N(G) = N(2x3)^2*N(G'), as the tilings of the pair of 2x3 regions and the tiling of G' are independent. We'll need names for a few other things, so we'll call the boundary of a hole E for eye. So the eye is the 10 squares directly surrounding the hole. Consider the middle 2x2 in G'. Imagine a vertical line L cutting this 2x2 into two pieces. This line divides G' into two equal copies of the same shape, an eye with a 2x1 hanging off one side and a 2x2 hanging off the other. We'll call this shape E+2x2+2x1 Now if we consider tilings with no domino crossing L, then clearly the number is N(E+2x2+2x1)^2, as the tilings of the two shapes on either side of L are independent. If instead we have a domino crossing L, then we must in fact have 2 dominoes crossing L. This is because otherwise we'd create a region of odd size, which couldn't be tiled. In this arrangement with 2 dominoes crossing L, we again have two identical regions to tile, but this time they are E+2x2, following the naming convention for the previous shape. In this case there are N(E+2x2)^2 tilings. So we've shown that N(G') = N(E+2x2+2x1)^2+N(E+2x2)^2. Next we consider E+2x2+2x1. If the 2x1 area is covered by one domino, then we're left with tiling E+2x2. Otherwise, then the tiling is forced all the way to a remaining 2x2 region. Therefore N(E+2x2+2x1) = N(E+2x2)+N(2x2). Now we consider E+2x2. Imagine a line L' dividing the E from the 2x2. If no domino crosses L', then the E and 2x2 are tiled separately, so we get N(E)*N(2x2) tilings. If instead a domino crosses L', then the rest of tiling is forced, so we get 1 such tiling. Therefore N(E+2x2) = N(E)*N(2x2)+1. The remainder is not especially hard to check. N(E) = N(2x2) = 2, so N(E+2x2) = 2*2+1 = 5, N(E+2x2+2x1) = 5+2 = 7, N(G') = 7^2+5^2 = 74. Finally N(2x3) = 3, so N(G) = 3^2*74 = 666.
I put it in a matrix calculator and it gave 666 only but I could be wrong because of typing and other mistakes
@@danieldarroch4775 Minor correction: the 2x3 regions contribute 3*3 possibilities, not 2*3. 666 = 2 * 3 * 3 *37, not 2 * 2 * 3 *37 which is 444.
Removing two black and two green cannot always work. By counterexample: you can isolate a corner square. But sometimes you *can*: example: just remove the squares occupied by any two dominoes of a domino-filled chessboard.
Almost word for word what I would have said...
@@etienneschramm83 _Almost word for word for what I would have said..._ Nearly word for word for what I would have said...
isolating a corner equates to creating 2 odd boards, neither of which can be filled, and as such should it be considered a legal move? It's about as useful as removing 63 out of the 64 squares... And as such some constraints would be handy. Such as one might only remove squares such that all squares on the grid must have at least 1 unique neighbor. A single rule that would suffice to make all boards complete-able.
@@livedandletdie A diagonal neighbor won't suffice either, since you can remove two greens from one corner and isolate a black square or vice versa.
I've just discovered there's no greater way to start a Christmas day than with a Mathologer video x
Second challenge: it is obvious that in this hexagon there is the same number of dominoes of each color because transposing this 3D volume(from isometric axonometry) into projects on the XOYZ axes we obtain identical squares on OX , OY and OZ planes so an identical number at any scale of dominoes ;(and whenever we place the dominoes , the projections will always be squere).
Very good, that's it (except it's not the second challenge :)
@@Mathologer How do you know every configuration must resemble 3D cubes? Maybe some configuration might look like some strange irregular (for example, non-manifold or having holes or floating cube or other strange whatever) shape. I know that won't happen but how do you prove it?
@@cr1216Every domino points in one of three directions, so they can be interpreted in three dimensions.
A fun intuition for why the frozen sections show up with high probability: Imagine the left corner of the n'th Aztec Diamond has a horizontally-oriented block on it. If you draw it on paper, you will see that this completely determines that the entire left side of the diamond is only horizontally-oriented blocks, what remains undetermined is nothing more than the (n-1)'th Aztec Diamond. So the number of configurations with a horizontal domino in the left corner is equal to A(n-1), which is fairly intuitively a small fraction of A(n).
This clears things up a lot, thanks! I was very confused by why it was always such a solid, perfect mass, since I was thinking of it as having multiple, off-center nucleation sites, so the probability of it being so perfect seemed low. But since we're not looking at just the likely tilings from placing random pieces and trying to make it work, we're looking at the whole collection of tilings, your way of looking at it is a better one.
Thanks, this really cleared it up for me as well. The algorithm for creating these tilings felt so biased. Of course if tiles always move in the direction they point, you will end up with regions full of tiles pointing that direction. I thought it was an artifact of the procedure. This algorithm doesn't just generate *a* tiling, it seems to generate the most average random tilings. Still weirds me out that the vast majority of tilings have these solid regions to them.
I'm going to tile my floor with randomly generated aztec square arctic circles, in shades of grey.
Loved finding your channel this year sir. Looking forward to many more years enjoying the content. Happy holidays!
What a fascinating result. Thanks for gifting us with this masterpiece of a video!
Thank you for this Christmas gift for us all.
The determinant or closely relevant tricks are still intriguing topics nowadays. Leslie Valiant even introduced the name and opened a new subarea, “Holographic algorithms”, for these types of reductions (from seemingly irrelevant problems to linear algebraic ones).
Merry Christmas Burkard! Thanks for making this hard year a more bearable one.
Merry Christmas! & Thank you for all the fascinating videos! Can't get enough of 'em!
Nuclear physicists play dominoes because they like starting chain reactions, according to my own interpretation of game theory.
Brilliant
Domino tumbling, there is another nice topic to explore ...
Good one
Lolllll
but they like the domino chains where the pushed tiles per time grow exponentionally
Hi
Daddy Flammy
Hi Papa Flammy What is the set of letters after "Papa Flammy's advent calendar"?
Loved this video so much. Thanks for all the great content this year. Also, this was directly inspiring for my research - what a treat!
I love the way this guy teaches! Amazing when someone loves what they do...
The best Christmas gift
I find it particularly interesting how a square grid can give rise to a circle... basically you get rotational symmetry out of something that is not... And why does it have to be L2 symmetry not some other Lp?
Waited the whole month for your vid :D you're the best!
I have always loved the unbridled beauty of mathematics and even studied it at university, but don’t get around to flexing that mental muscle much in my day to day. Your videos & clear passion for the field always make me fall in love again and I can’t thank you enough for that :) Merry (belated) Christmas!
animation autopilot is getting smoother day by day (I can see the damn hard work) Merry Christmas mathologer and wishes for another year of masterclasses.
The slideshow for this one is made up of 521 slides :)
@@Mathologer O_O wow
@@Mathologer what programm do you use to animate your stuff?
@mathologer i would also like to know which program do you used to animate this, it came out beautiful!!
The dance algorithm is incredibly cool. I think my favorite “aha” or maybe even a forehead-slapper in this video was “but how does the powers of two accommodate the deleting of some pairs?! Oh!!!!! Because those add a degeneracy which can be resolved exactly with a multiple of 2!” That was very satisfying.
Merry Christmas Prof Burkard. Thank you for the amazing years!
You need more views. Your videos are really detailed, structured and interesting. Merry Christmas!!!
I figured out the puzzle at the end! I imagined the hexagon as a cube made from cubes. If I look at any of the three sides, I will see a solid color, and each of the three sides is the same, so there is an equal amount of each color.
"Hey programmers" I see my work is requested.
waiting for github link
@@lumotroph github.com/selplacei/magic-square-dance here's mine, still in progress and the code is shit but i'm having fun
Also waiting for github link
Actually just finished doing this, but it needs some optimization still
@@lumotroph Made a web implementation here for those of you who don't want to run a python program jacobparish.github.io/arctic-circle/
Your video description is very thorough. An area often overlooked. Thank you for delivering top quality.
Thank you so much for sharing such an amazing and beautiful result. I hope that you all have a merry Christmas and get plenty of rest.
maybe once explain us the Poincaré Theorem proof :D
@Mr. Virtual it's been proven
First challenge: It can always be done when removing an even number of tiles as long as there is a round trip that always carves out green and black tiles one after the other and not for example two blacks before one green space is removed
A lot of kudos for the description below your videos, the links you provided are very useful.
Stunning! Many moons ago we studied some of these patterns in a class I took at Stanford (late 80's). Nothing comes close to these results. The trick with determinants is beautiful.
6.10. : Me: What if you cut out 2 black and 2 green squares? 6.20. : Mathologer: What if you cut out 2 black and 2 green squares? It's like he read my mind.
The tiling of 2 by grids is Fibonacci series with first term 1 and second term 2
Exactly :)
By implication, the 0x2 (empty) board should be defined as having 1 tiling
Absolutely outstanding! Great presentation as always.
What a clever mathematical exploration! I loved seeing the circle come in the limit of both the diamond and the hexagon, it was so elegant. I suspect that this area of study has applications in metallurgy, crystallography, and materials science.
Funny piece of trivia : the Arctic circle theorem is linked to the alternate sign matrices, described by no other than Lewis Carroll
I suspect he signed that proof “C. Dodgson”.
31:20 That magic moment when one needs to watch the Mathologer to finally understand where the abundance of "this is the way" memes is coming from all of a sudden...
Thank you for the beautiful Christmas gift. This video should be under my Christmas tree! Congratulations and continue with your work!
Extraordinary! Merry Christmas to you!
6:20 No, as you can isolate a corner, which clearly not be tiled over
That's it :)
Removing 2 black and 2 green can you always tile the board. It depends on how you define "a board." If "a board" is defined as a continuous connected surface, in other words a surface where you can get from any square to any other square via horizontal and vertical hopping from tile to tile (but not diagonal), simply put, if you cut it out of a sheet of paper, you can pick it up as 1 piece, then the answer is *"yes."* However, if your definition of "a board" doesn't require such continuity, e.g. an isolated corner separated from the main body is ok, or if you accept corner/diagonal connection as making it continuous, then the answer is *"no,"* as you can isolate a single square.
Wow, there's so many takeaways from this video(the Fibonacci one was so subtle and satisfying). Quality content, as always! And the tshirt was so cute 😁😁 (HO)^3 😂 Happy holidays, Sir!
I loved the hexagonal tilings. This is yet another great video. Well done and thank you.
I saw a variant of that tiling 2 by n board problem during a competitive programming contest, where you were allowed to use not just 2 by 1 tiles, but also 1 by 1 and L pieces. Really awesome stuff.
14:02 Yes. If I lay the leftmost domino of the 2xN rectangle on its side, there's 1 option to fill out the bottom and X(N-2) ways to fill out the N-2 columns to the right. If I put it upright, there's N-1 columns left to fill. So X(N) = X(N-2) + X(N-1), with 1 way to fill a space of 0 columns. Thus, we get the Fibonacci sequence.
37:14 There are an equal number of tiles of each colour because if you were to think about it as a 3d tiling of cubes, looking at it from above would make it look like a perfect square of orange square tiles. This is also true for looking from the other two orthogonal directions. Of course, since the squares are all the same size, they would contain the same amount of tiles.
Merry Christmas and happy new year mathologer. That was a great video! Greetings and wishes from Greece.
What a fabulous video.The thing I liked the most in this video is how we approached to solve the problem, and that is absolutely we all need to know to sharpen our brains.
I was looking forward to this whole december :). Merry Christmas from Czechia!
vesele vanoce
@@toniokettner4821 Vesele Vanoce :)
Hi everyone, I know I am a bit late to the party, but here is my implementation of the magic square dance: jarusek.wz.cz/ArcticCircle/index.html I tried to implement all steps of the animation, as seen in the video. Hopefully at least someone will see this and I wish you Happy New Year 2021! :)
21:30 As soon as you started talking about magic, I knew recursion would be involved. Recursion is the basis of all reality, my friends.
Also, as an aside, I was very surprised you didn’t talk about these tricks as “conservation rules”. They provide a beautiful connection to Noether’s theorem via that interpretation.
Those glasses are beastly things.
Maybe it's just me, but I immediately identified the four corners of the diamond with the four kingdoms of Oz: Gillikins in the North, Munchkins in the East, Quadlings in the South and Winkies in the West. Which would place the Emerald City at the center of the circle. Pretty fitting given our math wizard host's country of residence, don't you think? ;-)
I respect this man for interacting with his fans
I love the humor you bring into these videos.
8:10 that's a big ππ formula indeed
6:22 Remove (0, 1) and (1, 0) (=> same color) and 2 others of the opposite color anywhere except the corner (0, 0). That's 2 black + 2 green removed and you won't be able to tile the corner (0, 0) :-)
Proof by contradiction: Remove A1, B2, C1, D1 Now tile B1 is a single tile which can never be tiled!
Yes, that was nice doable warmup challenge. Let's see how you fare with the other ones. Some more doable ones but also a killer or two :)
Love how the 3-d interpretation of the hexagonal aztec tiling makes the answer to the last question literally obvious.
Excellent as always!
Regarding the arrangement of dominoes in a 2 by “n” grid ... I see a pattern for the first five grids that’s featured in previous Mathologer videos. Perhaps one that gave rise to a certain partition / pentagonal number theorem in recent memory? ;)
14:40 Those glasses should work with the determinant, because you can build the matrix as given and give the 4 squares in the holes the highest numbers (23 and 24). That would give the matrix for the board without holes. For our case: Just ignore the "new" last two rows and columns, so get the sub-determinat which would be exactly the same as if we had built the matrix just as is. So why does this not work for any holes? Where could it go wrong?
I think I got it. Think of the Laplace expansion along the first row. You get a problem, when you can't number a board with holes such that both "1s" are non-adjacent to a hole. A counter example would be a 3x3 ring, ie a 3x3 board missing it's center. It's determinant is 0 but there are 2 tilings.
Very good. One other person actually bothered to check. Evil me :) In fact the determinant will always work if you can fill the holes with dominoes (use the 2x2 switch argument in the masterclass to convince yourself of this fact). To get a board that does not work you need a hole that cannot be tiled with dominoes. For example, have a look at a 3x3 with the middle square removed.
@@Mathologer Yep, I answered myself two minutes after you did, before I just saw yours. Thank you!
@@xario2007 Ah, yes, see it now. That's great :)
Mathologer what a way to close this year. Thanks for the fascinating and (thanks to you) accesible material you share with all of us. really great!
thank you, excellent as always.
7:52 "Kasteleyn's watching you" i'm... genuinely scared now, im sitting in a dark room
THE BIGGEST HONOR A MATHOLOGER VIEWER CAN GET, A HEART FROM THE BIG M HIMSELF
It may not be the best program but I wanted it to be a christmas gift, so it had to be done (timestamp: Germany 19:51) github.com/Pianfensi/arctic-circle (Press space bar when everything is initiated in python) EDIT: Updated a couple of things
Thank you!
@@user-cn4qb7nr2m yeah somebody appreciate it. Sadly mathologer only favors html based solutions :/ so my time was not that wasted
Wow, this video really blew my mind! Some very amazing combinatorics! Now I think I know how to solve one of the projecteuler problems that stumped me for several years, namely figuring out the number of domino tilings of a 3 x 2n board.
brilliant (as always!), I think I might be watching it several times, whilst I'm sober to try and understand it! Frohes neues Jahr!
I wonder : if one were to 3D print these pseudo3d timings into actual 3D shapes, would the « arctic circle » turn into an arctic section of a sphere of sorts? What about matching pairs? And what about higher dimensional tilings ?
I wanna know specifically if it's possible to move into 3D with the triangular grid. The first problem is that there isn't an obvious, clean analogy to the triangular tiling in 3D; the tetrahedron in particular cannot tesselate 3D space. Well, let's look at that quirk of the triangular domino tiling: that it looks like an isometric view of a certain kind of stack of cubes. Particularly, the envelope of any side of a cube at a particular orientation is a sqrt(2) rhombus (that is, a rhombus made from two triangles). We might think to find a polyhedron which is an envelope of a hypercube, and then more specifically the envelopes of each cubic cell of the hypercube. Without knowing a whole lot about higher-dimensional geometry, I think our best bet is the sqrt(2) Trigonal Trapezohedron for our "dominos." Four of these can pack together into a Rhombic Dodecahedron, which is an envelope for the hypercube, and that will fill the same role as a hexagon does in the triangular grids with rhombic dominos. Our trapezohedron can be constructed from two tetrahedrons and an octahedron, all regular. Now, while our "dominos" and hexagon-stand-ins both tile 3D space, the Trapezohedron can't be split into two shapes that are very symmetrical like the 2D rhombus could into triangles. However, we can tile space using _both_ tetrahedrons and octahedrons together. This, for unclear reasons, is known as the tetrahedral-octahedral honeycomb. Using this honeycomb as a grid, we can define our particular Trapezohedron as a 'Tromino' (polyomino of 3 elements, like a _d_omino or _tetr_omino). [Actually, it's not called a domino on the triangular grid, it's called a 'diamond,' which is the 2-polyiamond, and you've got the triamond and the tetriamond. But this is 3D, not 2D. There's a bunch of names for poly_cubes_, so like with a cubic grid. Not quite what we're doing. Really, it's too many names. I'll call this a Tromino, because it's easier.] I think, but I don't know for sure, that you can make a Rhombic Dodecahedron by tiling together these trominos inside the tetrahedral-octahedral grid. This would be like making a hexagon from the rhombuses in a triangular grid. Put like that it sounds reasonable, but not obvious. I have a hunch that just using the tetrahedral-octahedral honeycomb isn't enough, and you actually need the _gyrated_ tetrahedral-octahedral honeycomb. The difference is as wierd as it sound, but not complicated. In the normal such honeycomb, you can think of the two different shapes, the tetrahedron and the octahedron, as the two colors of a checkers board: they alternate when you move from one to the next. The graphics on Wikipedia use red tetrahedra and blue octahedra. Now picture a checkers board, but you switch the colors part-way up. Now you have two squares of the same color next to each other, for each pair along the whole row. This is what's done in the gyrated honeycomb; along a whole plane, the tetrahedra to one side are next to tetrahedra on the other side, and likewise octahedra. My hunch is that the strange way the trapezohedra need to be placed to make a Rhombic Dodecahedron would put an octahedron next to an octahedron, which would symmetrically happen twice, and also with a bunch of tetrahedra. Using the gyrated honeycomb would allow this. You'd then want to have this switch actually happen repeatedly, every other 'layer,' as they're called. This gyrated form has less symmetry, though (remember that there was one plane, or layer, that was preferred for this 'switching' of shapes), so I'd hope it could be done without. That's about all I can wrap my head around without making any models, graphical or physical, and I'm not much of a modeler, graphical or physical.
Really appreciate the perspective of a determinant as a sum of permutations, I've never seen that before. I feel like an actual intuition for the determinant may not be too far behind. Trace has been similarly confusing for me my whole life - what possible simple interpretation could it have, and why is it so conserved?
It might also help to notice that both the determinant and the trace are coefficients in the characteristic polynomial.
You probably won't find this helpful but the trace is the linear map End(V) ≅ V* ⨂ V → K where K is the base field. The isomorphism V* ⨂ V ≅ End(V) is given by φ ⨂ v ↦ (x ↦ φ(x)∙v). The linear map V* ⨂ V → K is given by φ ⨂ v ↦ φ(v). Since both of these are base-independent, the trace is also base-independent. That's why it is conserved.
@@usernamenotfound80 Nice i will learn that fact prolly next semester since we learned duality in this one :)
But that with permutations is basically how we built up the determinant formula, with the leibniz formula and then proving that it is equal to develop it to a row or column or how you say that in english
Stunning!
Thank you for your amazing Christmas present !
My non-mathematician intuition tells me that the Aztec diamond is some sort of parallell to how observable time is only able to move forwards, as colliding time cancels out and disappears. The four corners would be the 4 observable dimensions we live in. And; may the 4th be with you all as we travel inevitably into the year of 2021.
Is it a known fact that you can get from any domino tiling to any other tiling by rotating 2x2 squares? Seems true for non-hole boards...
And indeed if you look at the formula for rectangular boards, it always spits out an even number.
He mentions this at 49:00
Yes, very good insight :)
Challenge 3: 14:00 The corresponding matrix is n by n with the main diagonal composed of only entries of i with the diagonal above and below consisting of 1 and all other entries are 0. Performing the cofactor expansion on the first row reveals that the determinant (d_n) is i * d_(n-1) - d_(n-2). Computing the first two values and following the formula reveals that the number of ways is precisely the nth Fibonacci number! Very neat!
Very nice :)
This is a nice Christmas present. Thank you. ❤️
I don’t understand why, when you are explaining how to grow a random tiling at 22:41, you split up the empty 2x4 region into two 2x2 regions. Wouldn’t there be more possible tilings if you were allowed to also split it into 2x1 + 2x2 + 2x1? It seems to me that there would be. And while the tiling you get would be identical in tile positions to one you could have gotten another way, the arrow directions would be different and they would grow into different tilings at the next step.
I think splitting into 2x1+2x2+2x1 after expanding the 2x2 vertical-vertical baby diamond introduces an overcounting. The seemingly new ways of tiling are actually already included by the other choice of the initial 2x2 baby diamond (horizontal-horizontal) because the two 2x1's at the start and end of 2x1+2x2+2x1 would correspond to having top and bottom being horizontal, which would've resulted from expanding an initial horizontal-horizontal 2x2 baby diamond.
@@lezhilo772 No, there's one tiling that can't be reached from doing two 2x2's. If you use 2x1 for each end, then swap the orientation of the 2x2 in the middle so it's opposite the ends, you can't get that tiling from just using two 2x2's.
@@Xeridanus Let me try to type out all the tilings, hopefully the formatting works. Im going to use HH for a horizontal tile, and V V for a vertical tile. So we start from a 2x2 baby diamond, which is either VV VV or HH HH For the VVVV baby diamond, after expanding, we get __ V__V V__V __ and using the two 2x2 block formalism, there will be four possible outcomes HH VHHV VHHV HH HH VHHV VVVV VV VV VVVV VHHV HH VV VVVV VVVV VV For the other baby diamond, we have four more cases HH VVVV VVVV HH HH HHVV HHVV HH HH VVHH VVHH HH HH HHHH HHHH HH Suppose you take one of these 8 cases, and switch the middle 2x2 blocks, it will be sent to another case. Example: if I take case 8 HH HHHH HHHH HH and switch the middle 2x2 block so I end up with HH HVVH HVVH HH then it would seem like I have a different case. But a vertical HH is not possible: it's actually just a vertical VV, so we cannot just rotate the middle 2x2 block, instead, it would be HH VVVV VVVV HH which is just case 5. So I think the key to answering your question is that it is impossible to just rotate any 2x2 block without affecting others, unless they are in some special positions, defined by the expanding diamond algorithm. I think what the algorithm does is that by expanding the diamond like this, all these superfluous degrees of freedom will be eliminated.
@@lezhilo772 No, you don't get it at all. You're right but you're misunderstanding the problem. HH HHHH HHHH HH You can't swap the two in the middle because they're joined to the two on the outside. HH VVVV VVVV HH can be swapped to this: HH VHHV VHHV HH Which does produce a different tiling that can't be reached by the method in the video.
@@Xeridanus This tiling can be reached by the method in the video: start with a VVVV 2x2 baby diamond, expand, and pick both 2x2s to be HHHH (case 1 in my list).
No. The counterexample is easy, remove a2, a3, b1, c1. a1 is isolated and therefore no tiling is possible
Thank you for the video!!! Merry Christmas!!!
Best maths videos in 2020 and no doubt in 2021 and next years! Thank you!
That Hex board Reminds me of One qbert video game.
Same