Sunday, May 6, 2018

Hoppas på 7-1 även i år!

När man pratar om 7-1-segern 2014 tänker väl särskilt tysklandsvännerna på fotboll, och på semifinalen i VM 2014 där tyskarna spelade skjortan av hemmalaget Brasilien.

Men i Sverige togs också en viktig 7-1-seger. Sverigedemokraterna var på väg framåt, och det började bli tydligt att miljöpartiets förhoppningar om en jämn match om tredje pris var på väg åt samma håll som Brasiliens.

Det stod klart att Åkesson och hans partivänner inte var några Bert Karlsson-typer med drag under galoscherna. De hade suttit en mandatperiod i riksdagen och ändå ökat i popularitet. I valet fick de nästan 13 procent, och politiker, journalister och allmänhet undrade vad övriga partier hade gjort för fel.

Mycket av resonemangen satt vid den här tiden fortfarande kvar i idén att nästan ingen egentligen tyckte som sverigedemokraterna. Om bara övriga partier hade fått fram sina budskap och om bara folk hade förstått vad sverigedemokraterna står för, så hade de åkt ur riksdagen med näsan före. Så felsökningen ledde till den ena hypotesen efter den andra. Än hade de övriga partierna låtit debatten handla för mycket om invandringen, än hade de inte tagit debatten om invandringen. Än hade Åkesson fått för mycket plats i media, än hade han inte granskats i media. Man talade fortfarande om "missnöjesröster".  

Från vänsterhåll påpekades med illa dold förtjusning att det var moderaterna som hade tappat mest till SD. Det visade, antydde man, att moderaterna egentligen är smygfascister. Fast det borde väl vara tvärtom?

Jag är överlag ingen vän av moderatpolitik, men en sak jag tycker Reinfeldt ska ha heder för är att han inte vek sig för den nationalistiska trenden. I det här klippet punkterar han Åkessons retorik genom att i fyra ord sammanfatta sverigedemokraternas hela idé: Det är invandrarnas fel. Reinfeldt förstod nog vartåt det lutade inför valet 2014, men han förlorade hellre 20 stolar i riksdagen än lät sitt eget parti glida med i den invandrarfientliga vågen.

Nu har det gått några år och vi har sett att nationalism och högerpopulism är en internationell trend. Hela förklaringen kan inte ligga i att svenska politiker har gjort något strategiskt fel. I stället har vi fått inse att de flesta som röstar på SD faktiskt tycker som de. De tycker att invandring, feminism, hbtq-rättigheter, miljötänk och så vidare har gått för långt, och de tycker att det är bättre om vi får en stark ledare och politisk styrning av media, domstolar, polis och skola.

Givet att det är så, betraktar jag det som hände i valet 2014 som i stort sett idealiskt. Att beskriva det som att "vi vann med 7-1" kan förstås låta som att på typiskt politikermaner skönmåla ett fiasko, men när 13 procent av väljarna röstar för nationalism och rasism, ser jag hellre att bara ett parti får deras röster, än att denna ideologi ska genomsyra hela politiken. När vi börjar fråga vad de andra partierna har gjort för fel som har misslyckats med att locka de här väljarna, är vi inne på en farlig väg. Jag tycker att de gjorde helt rätt, och att det var starkt att 7 riksdagspartier av 8 tog avstånd från högerpopulismen.










Saturday, May 5, 2018

Humanity's last outpost (on the chess board)

In the last five years or so, there's been a revolution in artificial intelligence. Before that, it used to be that computers were good only at well-defined tasks like arithmetic, sorting stuff, and searching for stuff they'd just sorted.

Basically, computers could do the things that we humans think when we do. It turned out that chess, the old holy grail of AI, could pretty much be reduced to plain calculation, like "I go bam, you go wham, I go swoosh..." and so on. The asian board game of Go on the other hand seemed to be much more about that mysterious intuition and didn't easily yield to "good old" programming techniques.

Then came deep learning. And now it's pretty much the opposite. Computers are now good at the things we do without thinking. As Andrew Ng puts it around 4.45 into this video, a useful rule of thumb is that anything a typical person can do in one second can now be automated. Like recognizing whether or not a picture is of a bird.

The comic 1425 from xkcd (Randall Munroe) illustrates what has happened.


What I now find fascinating about this comic is that it was published in 2014, and the character Ponytail thinks she only needs five years, not that it's impossible. Somehow Randall Munroe seems to have known what was going on, even though many people in AI have testified that they didn't see it coming.

Using deep learning, the program AlphaGo from Deep Mind clearly defeated the best human Go players, and in December last year, the new version AlphaZero shocked the world of chess and AI by beating Stockfish, a state-of-the-art chess program way beyond human level, by a clear margin in a match of 100 games.

So the new situation is that computers are good at everything that just requires following a simple recipe, like multiplying thousand-digit numbers, and everything that just takes instinct and learning from examples, like recognizing what's in a photo or whether a position in a board game looks generally promising.

But there are still purely intellectual tasks where the human mind rules, and where software isn't of much help.

One thing that (surprisingly?) hasn't been automated yet is research in mathematics. In this talk from a few years ago, Tim Gowers discusses the problem of getting a computer to discover mathematical ideas, and I think everything he says is still relevant. Even though computers outperform us in arithmetic, it has turned out to be extremely difficult to get software to explore and answer questions of the type "Does there exist a number with the property that ... ?". Reasoning about a generic number called $n$ is different than handling a particular one like 756767765776.

The situation is similar in the realm of board games. Stockfish and AlphaZero are mindbogglingly strong when it comes to the basic problem of choosing a move in a typical position. But if we start asking questions of the type "Does there exist a position with the following property ... ", they can't give us the answer. That's a type of question that belongs on a different level.

There has been quite some discussion about chess positions that supposedly baffle the best software. A few years ago the physicist Roger Penrose claimed that a certain chess problem holds the key to human consciousness. But I guess a neural network in combination with Monte Carlo tree search (what AlphaZero does) will solve such problems in the near future, at least if they can train the neural network during the game (to tune it to the position at hand).

Whether or not they do, there is an old and well-established domain of chess dealing with constructing positions with extraordinary properties, and so far there is no software that can challenge the human mind in that area. So in any case it's not true that computers beat humans in all aspects of chess.

The traditional form of a chess problem is "Mate in $n$" (again $n$ is a generic number!), which means that White makes the first move, and forces a checkmate in at most the stipulated number of moves, against every possible defence by Black. There is software for solving such problems, but now we're talking about the construction of chess problems. This is a form of art where the composer (yes, that's what it's called!) tries to present a chess position where the optimal play has some remarkable and surprising properties.

Sometimes this develops into a sort of contest, where problem composers challenge each other to come up with chess positions with certain stipulated properties (not unlike research!). One of their favorite topics is so-called underpromotion, meaning promotion of a pawn to a piece other than queen.

It is easy to think of a situation where it's better to promote to a knight than to a queen, since the knight can move in ways that the queen can't. But there also exist situations where it's better to promote to a rook or a bishop, even though it seems that a queen can do anything that those pieces can. These situations all have to do with the rule of stalemate, according to which the game is drawn if a player doesn't have any legal moves. Since it's not legal to put one's king en prise, it's sometimes better to have a weaker piece than a stronger one, either because you want to get stalemated, or to avoid stalemating your opponent.

For decades, a seemingly impossible challenge was the Babson task: Composing a problem where after White's initial move, Black can promote a pawn, and where in White's second move, the only solution is for White to promote one of their pawns to the same piece as the one Black chose!  

Several expert composers tried in vain to find such a position, and Pierre Drumare (who sort of solved the task in 1980 but with an illegal position) declared after twenty years that he didn't think such a position could exist. To begin to appreciate the difficulty, notice that (as I actually mentioned in one of my very first blog posts!) the defensive underpromotion to rook or bishop (in order to try to get stalemated) requires such special circumstances that in all of chess history, with databases of millions of games and libraries full of books, there is not a single known case of this happening in a real game. Even the offensive underpromotion (avoiding to stalemate one's opponent) is extremely rare, especially the promotion to bishop.

And the Babson task requires these promotions to work and to be necessary, simultaneously from the same position.

The task was first successfully achieved by Leonid Yarosh in 1983 (comment to establish that I was a nerd before it was cool: I knew about the Babson task before it was solved, in the days when this problem by Bo Lindgren was the best that had been achieved!), and in the following years a number of other Babson problems were composed by Yarosh, Drumare and others. Among them was the following particularly beautiful one, by some connoisseurs regarded as the most remarkable position ever set up on a chess board:

 Karlheinz Bachmann, Peter Hoffmann and Martin Hoffmann, Die Schwalbe 1987.


Mate in 4.  

White starts with the "key" 1. hxg7! Normally an initial capture is frowned upon in the problem world, but this key is thematic and opens up a flight square for the black king, so it's nice anyway.

If the black king takes back on g7, White will checkmate with 2. Ng5, 3. Rg8, and 4. Rg6 no matter what Black does. If Black promotes the d-pawn in move 2 (in any of the 12 possible ways!), then 3. Rg8 will be check, so Black doesn't have time for any counterplay. 

Given that Black cannot move the king in move 1, White's main threat is 2. g8Q and 3. Qg6 mate. Promoting on c1 or e1 can delay this plan by at most one move, so the question is whether a black promotion on d1 can throw a spanner into White's works.  

After 1. .. d1Q, 2. g8Q, Black can try to delay the checkmate with 2. .. Qxd4+. Now White cannot capture the queen because of stalemate, but instead White blocks the check with 3. c4!, at the same time pinning the black queen and checkmating in time. 

But Black can be clever and instead promote to a rook! Then after 1. .. d1R, 2. g8Q Rxd4+, blocking with 3. c4 or taking the rook will be stalemate, and everything else allows Black to give one more check. To counter the stalemate idea, White too promotes to a rook so that after 1. .. d1R, 2. g8R! Rxd4+, 3. c4! (also perfectly blocking the bishop's diagonal!), there is 3. .. Kxf7 and 4. Rdf8 mate.

Black has yet another stalemate trap, the "self-paralysis" 1. .. d1B! after which the solution is 2. g8B!, allowing 2. .. Kg7. Since the black king is now confined to the long diagonal, White checkmates with 3. c4 and 4. d5.

Black's last trick is 1. .. d1N, which threatens to give not only one but two consecutive checks on the white king. White prevents this by being the first to give check: 2. g8N+! Kg7, 3. f6+ Kh7/g6, and 4. Qxc2 mate! 

In each case, White's echoing of the Black promotion is the only solution. For instance, in the queen variation White actually needs a piece that moves in all directions. And looking at the knight variation we realize that 2. g8N+ was a threat all along, but that any black piece on d1 except a knight prevents the checkmate 4. Qxc2.

Peter Hoffman has continued to explore variations on the Babson task where the White promotions aren't necessarily echos of the Black ones, but instead form a permutation of the four pieces. For instance, the following problem realizes the pattern Queen->Rook, Rook->Knight, Knight->Queen, Bishop->Bishop.

Peter Hoffman, Die Schwalbe 2008.


Mate in 4.

After 1. cxd7, d1Q, White plays 2. dxe8R! so that 2. .. Qd7+ can be met with 3. Bxd7 without stalemate. On 1. .. d1R, White must promote to a knight, since in this problem not even a rook stops the old stalemate trap 2. .. Rxd4+. On 1. .. d1N on the other hand, White can now allow Black to give a check on b2 or c3, provided that they have a queen on e8! Finally the self-paralysis 1. .. d1B is again met with a bishop promotion. As in the previous problem, there are numerous details that amazingly make these White promotions the only moves that work.

In what very much looks like a mathematical research project (in a sense it is!), Hoffman has so far demonstrated eight permutations of the 24. By the way, in the table summarizing the results, the original Babson pattern (Q->Q, R->R, B->B, N->N), is called the echo. Mathematicians would call it the identity permutation, but I think echo is both more descriptive and beautiful, and I wish we would use it in mathematics. Imagine reading in an algebra book that "the only automorphism of the field of rational numbers is the echo"!

Among the 16 permutations not yet realized, Hoffman mentions the "reciprocal" pattern Q->N, N->Q, R->B, B->R as particularly attractive. But beware, not even the "3/4-Babson" pattern Q->N, R->B, B->R has been demonstrated!

If you want to try this challenge, it might be useful to have a chess program available. But it's a bit like using a pocket calculator in mathematical research. Currently the only thing the software will do for you is to look for the quickest forced mate in a position that you set up. You can't use it to systematically search through positions, and it will never tell you that "Had it not been for the flight square on g5, this variation might have worked, perhaps we should try adding a white pawn on f4 or h4".

Even though the permuted Babson tasks are well-defined questions with a finite search space, exactly the sort of task where computers are supposed to excel, there is to my knowledge no software that can even meaningfully attack them. It doesn't make sense to randomly throw out pieces and check whether it led to a permuted Babson, because those positions are so rare that you won't find one in a million years. But in order to search intelligently, it seems one has to use concepts that go beyond the way current software represents chess.







Monday, April 30, 2018

Paradox of records

Which is harder to beat, an old record or a new one? The old one hasn't been beaten for a long time, so is obviously difficult to beat. But if it had been beaten recently, then that new record would have been even harder to beat, wouldn't it?

Let's make a probabilistic model, but first recall this concept called independence. Suppose we flip a coin twice. The probability of heads is $1/2$ each time, so the probability of heads-heads is $1/2 \cdot 1/2 = 1/4$. This is because the two coin flips are independent. If we get information about one of them, it doesn't affect what we believe about the other.

Suppose instead we throw an ordinary die once. The probability of a high number, 4, 5 or 6, is $1/2$. The probability of an even number, 2, 4, or 6, is also $1/2$. But the probability of a number that's high and even isn't $1/4$. It's $1/3$. The two events aren't independent. Among the high numbers there are two even and only one odd, so if you get the information that the number was high, it becomes more likely that it was also even. The two events are positively correlated, meaning they tend to occur together. If we know that one of them happened, it will increase the probability of the other one.

Now back to the records. Consider the following card game: Shuffle an ordinary deck and put three cards in a row face down on the table. Then turn them up one by one, from left to right. Let's say that a record is a card that's highest so far. The first card is always a record, the second is a record if it beats the first, and the third is a record if it's highest of the three. Suppose also that we decide on some ordering of the suits to break ties, so that of two cards, one is always higher than the other.

What is the correlation between the events that the second cards is a record, and that the third card is a record? Do those events tend to occur together or not?


To figure that out, let's pretend we know what the first card is. We can imagine it's a seven, for instance. Then if the second card is not a record, the third card only has to beat that seven in order to be a record. But if the second card is a record, the third card will have to beat that card, which is higher, in order to be a record. So if we get the information that the second card is a record, the probability that the third card is a record will decrease.

And it doesn't matter for this argument whether the first card was a seven or some other card. If the first card was a three, then again there is negative correlation: If the second card is not a record, we're pretty sure the third card will be, whereas if the second card is a record, the third one may or may not be. Same thing if the first card was a queen: If the second card beats the queen, the probability that the third one is a new record will decrease.    

So we conclude that the events are negatively correlated: Whenever we learn that one of them happens, the probability of the other one decreases.

Now let's look at the same thing from a different perspective. Suppose we turn up the second card before the first. And let's imagine that it is, well, whatever. A ten say. Now it's the other way around: If the second card is a record, that means that the first card is something smaller than a ten, so that the third card only has to beat the ten in order to be a record. But if the second card is not a record, the first card must be something higher, and the probability that the third is a record decreases.


So now it seems that the events are positively correlated: When we learn that one of them happens, the probability of the other increases. And again it doesn't matter if that second card was a ten or something else.

It's not that I don't know which of these two arguments is correct. Obviously none of them is. What bothers me a bit is that I may have thought, in some different context, that a similar argument was correct just because it led to what I knew was the right conclusion.

Finally let's reveal the answer about that correlation between records. The truth is that the second and  third card are records independently of each other! To see why, imagine we know what the third card is. Whether or not the second card is a record now only depends on the order of the first two cards, and that's clearly independent of whether or not they are both smaller than that third card!

Wait...





Wednesday, March 21, 2018

Perpetuum mobile drinking game

Let's imagine we're in a pub in some sort of Pippi Långstrump universe where (1) money comes in the form of physical coins that you can move around on a table, (2) you never really run out of them, and (3) you can buy a round of beer for a single coin.

Three people called A, B and C play a game: There is a six-sided die where three of the sides are labeled A, B, and C, and the other three are labeled Double. At the start of the game, each of the three players puts one coin on the table, and the die is thrown. If the side that comes up says Double, then each player doubles their amount of money on the table, and the die is thrown again. The doubling repeats any number of times, until one of the sides labeled with a player comes up. Whenever the die shows A, B, or C, that player loses and the other two split the pot evenly between them, concluding the round.

That's really all, but there is a final little twist: If the round ends after only one roll, without any doubling, the pot will consist of an odd number (three) of coins. The two winners get their coins back, but instead of using smaller change to split the third coin, the tradition is that the loser buys the next round of beer using that coin.

The game is zero-sum, meaning no money enters or leaves (unless we regard the twist as a proper part of the game). The game is also symmetric in the sense that all three players have the same status with respect to the rules. These are what we might call properties of fairness: What somebody wins, somebody else must have lost, and whatever somebody else wins or loses, you could have won or lost with exactly the same probability.

Let's calculate the probabilities of winning or losing a certain amount, and see if those probabilities somehow reflect this "fairness". First let's find the probability that a player, say A, loses exactly one coin. This happens if A loses without any doubling, and the probability is $1/6$ since it happens precisely when the first roll of the die is an A. In order for A to instead win one coin, there has to be one double and the second roll must be a B or a C, so that somebody else loses 2 coins and A gets half of that. The probability of starting with a double is $1/2$, and the probability of the second roll being a B or a C is $1/3$, so the probability of winning one coin is $1/6$ too.

It turns out that we also win or lose 2 coins with the same probability, and we start to see a pattern: Player A loses 2 coins of there is a Double and then an A, and wins 2 coins if there are two Doubles and then a B or a C. Both these scenarios have probability $1/12$. And to win or lose 4 coins, we have to win after 3 doubles or lose after 2, both of which have probability $1/24$. Winning or losing 8 coins requires winning after 4 doubles or losing after 3, probability $1/48$ each, and so on. Each of the scenarios has probability exactly half of the previous one. So the game has the property that winning $X$ coins is exactly as likely as losing $X$ coins. Perhaps we shouldn't be that surprised in view of that "fairness" we just discussed.

But wait, we forgot about winning half a coin! That scenario didn't match up with any scenario where we lose half a coin, because we never do! So it seems that a given player, say A, will win half a coin with probability $1/3$ (when the first roll is a B or a C), and break even in the remaining cases. So perhaps after all it's when we include that final twist as a proper part of the game that it becomes "fair", and our wins and losses exactly balance out.

But then the question is: Where does all that beer come from, if in the long run nobody is paying?

---

I discussed this sort of thing and related stuff in 2007 with the German probabilist Nina Gantert and my colleagues Jeff Steif and Olle Häggström. Thanks to Jeff who asked me about it a few days ago, because I had almost forgotten. I can't recall how it started, but I remember that when we met, Nina said she was from Münster, and I told her that I had been there and visited the Panzermuseum. Strangely she had never heard of it, and it turns out there isn't one. The Panzermuseum is in the small town Munster just south of Hamburg, some 200 km or so from the city of Münster. That's how well you know where you are when you're on tour with LiTHe Blås :)

Saturday, March 10, 2018

Akta så inte hjärnan kollapsar!

Till det tok som snurrar runt på internet adderar vi nu att om du tänker på Grahams tal, ett fantastiskt stort tal som dyker upp i den del av kombinatoriken som kallas Ramseyteori, så kollapsar din hjärna till ett svart hål. Det verkar komma från något skämt i en video från Numberphile. Jag får väl vara försiktig då :)

Om det här talet sägs ofta att det observerbara universum inte skulle räcka till för att skriva ut det i decimalform. Det är sant, men det fångar liksom inte hur stort Grahams tal är. Det är lite som att säga att Rubiks kub har över tre olika tillstånd.

Jag har ofta skrockat lite inombords åt uttrycket "astronomiskt stort tal" och tänkt "de skulle bara veta vilka tal som förekommer i andra sammanhang". Så här kommer ett förslag på klassificering av tal i storleksfamiljer ordnade efter olika vetenskaper.

1. Astronomiska tal. Det här är tal av typen hur många meter det går på ett ljusår. The scale of the universe, kan man säga. Animeringen här är hisnande, men det är ingen större svårighet att skriva ner ett tal med 50 eller 100 siffror med papper och penna.

2. Kryptologiska tal. Här har vi de tal som gör att vi kan skicka pengar och inloggningar säkert över internet. Kryptonycklar är slumpmässiga strängar av ettor och nollor som är så långa att det ska vara praktiskt omöjligt att gissa eller leta igenom för att hitta dem och knäcka krypteringen. Animeringen the scale of the universe sträcker sig över 62 tiopotenser. Ett kryptosystem med nyckellängd på 256 bitar har $2^{256}$, eller ungefär $10^{77}$, möjliga nycklar. System med offentlig nyckel (public key) måste ha kanske 8 eller 16 gånger längre nyckel. Nu blir det lite jobbigt att skriva för hand, men en sådan nyckel tar ändå bara upp en försvinnande liten del av ett datorminne. De kryptologiska talen är bara ett litet snäpp ovanför de astronomiska i min klassificering. Titta gärna på avsnitt 1.7 i boken Applied Cryptography av Bruce Schneier.

3. Fysikaliska tal. Här har vi tal som dyker upp i statistisk mekanik. Varför fryser vatten till is vid en viss temperatur? Varför kokar det vid en viss annan temperatur, och hur kan det ändå finnas vatten i luften fast det är kallare än så och vatten är tyngre än luft? Vad är det som händer när saker koagulerar, spricker, blir magnetiska och så vidare, och det där entropi, vad är det?
  För att reda ut sådana saker behöver man resonera om tal som är större än de astronomiska och kryptologiska. Det handlar inte om antalet molekyler i luften i ett rum, utan om på hur många sätt de kan arrangeras, om vi till exempel klassificerar dem efter huruvida de befinner sig i eller utanför en kastrull på spisen. Typiskt rör det sig om sådant som två upphöjt till Avogadros tal. Nu kan vi inte längre hantera talen med en miniräknare eller med datorns flyttal. Fast vi skulle fortfarande kunna skriva ner dem i decimalform om vi omvandlade några planeter till papper! Och någon liten måne till gem för att hålla ordning.

4. Talteoretiska tal. I den del av talteorin som handlar om fördelningen av primtal, händer det ofta att man upphöjer till någonting ett par, tre, fyra gånger. Gauss och Riemann hade kommit på redan på 1800-talet att antalet primtal mindre än ett tal $x$, vilket brukar skrivas $\pi(x)$, approximeras väldigt bra av funktionen \[\mathrm{li}(x) = \int_0^x \frac1{\log t}\,dt.\] I den här integralen blir det lite tjafs kring $t=1$, men vi tolkar det som ett principalvärde, dvs kancellerar oändligheterna. Det såg till en början ut som om $\pi(x)$ alltid är mindre än $\mathrm{li}(x)$. Hur långt man än tittar i primtalstabellerna, verkar primtalen aldrig komma ikapp.
  Men sedan bevisade Littlewood och Skewes att $\pi(x)$ och $\mathrm{li}(x)$ kommer att hoppa bock över varandra oändligt många gånger, och att första gången primtalen kommer ikapp den logaritmiska integralen är för något $x$ som är mindre än \[e^{e^{e^{79}}}.\]
  Det här talet, $e$ upphöjt till $e$ upphöjt till $e$ upphöjt till 79, är redan långt förbi vad som kan skrivas ut i decimalform med alla atomer i det kända universum. Talet $e^{79}$ är ett astronomiskt stort tal, och när vi tar $e$ upphöjt till det talet, får vi ett tal som det krävs astronomiska resurser för att skriva ner i decimalform. Sedan ska vi alltså ta $e$ upphöjt till det talet.

5. Kombinatoriska tal. Här kommer Grahams tal och dess släktingar. Längst ner i det här skiktet ligger tornen. I stället för att som Skewes och Littlewood nöja oss med tre-fyra exponentieringar, bygger vi ett torn av en viss höjd, så här \[2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}.\] Om vi sätter höjden till exempelvis 10, är vi redan i en helt annan bollpark än talteoretikerna.
  Här är ett problem där torn dyker upp: Tänk dig att du bor på en oändligt lång gata, där varje hus ska målas rött, grönt, eller blått. Det blir inte snyggt om två grannar väljer samma färg, så det vill vi undvika. Enkelt, du hör ju bara efter med dina två grannar hur de har tänkt måla, och vad de än säger, finns det åtminstone en färg kvar. Problemet är bara att de har sina andra grannar att tänka på, så de kanske kommer och frågar dig först. Vi antar att vi kan singla slant för att lösa upp situationer av typen "ok, vi tänker båda måla blått, så då får en av oss byta". Men informationen i grannarnas kommunikation hinner bara gå en ändlig sträcka, säg $n$ hus, på den vecka eller så man har på sig att välja färg. Då visar det sig att det inte går att garantera att alla grannar väljer olika! Som Alexander Holroyd berättade för oss på Chalmers förra våren, kommer det ungefär på ett ställe av $Tower(n)$ (ett torn av höjd $n$) att köra ihop sig och på grund av ändringar hit och dit i sista sekunden sluta med att två grannar målar sina hus i samma färg!
  Grahams tal, som är ännu mycket större än till exempel $Tower$ av något talteoretiskt tal, handlar om i vilken dimension en viss variant av tic-tac-toe inte längre kan sluta oavgjort. Där får vi börja med att skapa torn vars höjd bestäms av tidigare torn, och så vidare, och då har vi "ändå inte sett någonting än" som de säger på engelska. Jag får hänvisa till Numberphile igen.

6.  Datavetenskapliga tal. Alla tal vi har diskuterat hittills har varit möjliga att beräkna i princip. Det vore en enkel sak att skriva ett datorprogram som, om det kördes på en idealisk dator med oändlig hastighet och oändligt mycket minne, skulle spotta ut $Tower(1000)$ eller Grahams tal. Ett program för $Tower(1000)$ skulle kunna vara (i pseudokod):
\[N=1; \quad \mathrm{for} \,\, (k=1,\dots, 1000)\,\, \mathrm{do} \,\, N=2^N; \quad \mathrm{return}\, N.\] Det fick plats på en rad här. Och vi skulle kunna använda $Tower$ som en subrutin i ett något längre program för att beräkna de följande hisnande nivåerna upp till Grahams tal. Hela programmet skulle nog med bred marginal få plats på säg 50 rader om 20 tecken vardera, dvs det skulle ha färre än 1000 tecken om det skrevs i något vanligt programmeringsspråk. Låt oss nu definiera $f(N)$ som det största tal som ett sådant idealiskt datorprogram med högst $N$ tecken kan skriva ut. Då är $f(1000)$ minst lika med Grahams tal, och förmodligen ofattbart mycket större. Lägg märke till att programmet alltså måste stanna för att det ska räknas. Ett program som bara fortsätter att skriva ut siffror i oändlighet är inte en beskrivning av något tal, och räknas inte.
  Med de datavetenskapliga talen passerar vi gränsen för vad som överhuvudtaget kan beräknas. Funktionen $f$ är en variant av det som kallas Busy Beaver, och är ett av standardexemplen på vad som i likhet med Alan Turings halting problem inte går att beräkna med någon algoritm.
  Nu skulle man kunna tro att de datavetenskapliga talen ligger väldigt långt från de pussel och tankenötter som vanligt folk håller på med. Men även de är allestädes närvarande och dyker upp i just pussel. Wang tiles är fyrkantiga pusselbitar som ska läggas så att färgerna matchar. För en given uppsättning är frågan om det går att täcka hela planet. Hur stor är den största kvadrat som kan byggas av någon uppsättning av $n$ stycken Wang tiles som inte kan täcka hela planet? Svaret är att det i allmänhet inte går att räkna ut överhuvudtaget! Det är en funktion av busy-beavertyp, vilket innebär att om vi ställer den frågan för till exempel $n=1000$ tiles, kommer svaret att vara större än de tal jag nyss kallade "kombinatoriska".
  Jag och Urban Larsson har ett papper där vi visar att de datavetenskapligt stora talen lurar bakom barnspel med tändstickor.

Men det finns en vetenskap kvar på min lista, och de tal man kan stöta på där är så löjligt stora att vi ytterligare en gång får konstatera att vi inte hade sett någonting än.

7. Logiska tal. På samma sätt som programmeringens språk gjord att vi kunde definiera $f(n)$ som det största tal som kan beräknas av ett $n$ tecken långt program, kan vi använda matematiska språk för att definiera det största tal som kan definieras med $n$ tecken.
  Då måste vi konstruera ett språk som gör att vi kan definiera matematiska begrepp formellt, inuti språket. Sådana språk har konstruerats, och ett av dem, ZFC, har kommit att bli en standard för den här typen av resonemang, även om det inte mig veterligen finns någon som faktiskt använder ZFC på det sätt som programmeringsspråk används.
  ZFC står för Zermelo-Fraenkels system utvidgat med the axiom of Choice, och det är i princip tillräckligt kraftfullt för att man ska kunna definiera begrepp som Turingmaskin. Det gör att vi med ett sådant språk formellt kan definiera funktionen $f$ ovan, trots att vi inte har något sätt att beräkna den. Vi kan sedan bland annat definiera en hel hierarki av olika varianter av Turingmaskiner, utökade  med svarta lådor som beräknar lägre nivåers busy-beaverfunktioner. Så om vi definierar $N$ som det största tal som kan definieras i ZFC med högst en miljon tecken, får vi något som slår till och med de datavetenskapliga talen med hästlängder.
  Scott Aaronson har en väldigt trevlig uppsats som bland annat förklarar detta i mer detalj, och nu ser jag att han har skrivit om detta på sin blogg ganska nyligen.
  Men är det inte lite paradoxalt att vi kan prata om detta tal $N$ i en bloggpost med färre än en miljon tecken? Kan vi definiera ännu större tal genom att formalisera våra resonemang om ZFC?
  Då hamnar vi i frågor om huruvida olika utvidgningar av ZFC är motsägelsefria, och snart är vi i vad Scott Aaronson kallar Gödels träsk. Så vi kan lika gärna avsluta med

Det största tal du kan tänka på plus ett, stjärnstopp stjärnstopp stjärnstopp!

 Här är förresten en snygg affisch.





Sunday, March 4, 2018

Infinite lake surrounded by lighthouses: Why $1+1/4+1/9+\dots = \pi^2/6$

The Youtube channel 3Blue1Brown has made a wonderful video based on one of my papers! It's called The stunning geometry behind this surprising equation, and shows a geometrical proof of Leonhard Euler's amazing equation \[1 + \frac14 + \frac19 + \frac1{16} + \dots = \frac{\pi^2}6.\]
By the way, this means that a prediction from my very first blog post is coming true!


Several people notified me of this video already the same day it was posted (first of them was a student in my discrete math course), and it really is awesome!

 I have seen some videos from 3Blue1Brown before, but never checked out who makes them. This one was created by the team of Grant Sanderson and Ben Hambrecht. Grant Sanderson is the creator of 3Blue1Brown, and from their about-page I quote:

"...what excites me the most is finding that little nugget of explanation that really clarifies why something is true, not in the sense of a proof, but in the sense that you come away feeling that you could have discovered the fact yourself".

I wish I had said that myself. I mean I come away feeling that I could have!

About my personal relation to the Basel problem:

I remember thinking about the sum $1+1/4+1/9+\dots$ before I knew the answer. I asked one of my teachers about it, but he didn't know.

When I was something like 16 or 17 years old, I found a book in our school library called Högre matematik för poeter och andra matematiska oskulder (Higher mathematics for poets and other mathematical virgins). That book was my first encounter with Fourier series. I played around with the series for the saw-tooth and related functions, and used my pocket calculator to check the amazing results. Somehow I figured out that those series provided the answer to my question, and I was astonished to realize that it wasn't pi times something, it was pi squared!

I also realized I could integrate those series and sum the inverse powers whenever the exponent was even. I think I went as far as \[1+\frac1{2^{14}}+\frac1{3^{14}}+\dots = \frac{2\pi^{14}}{18243225},\] and used that to compute digits of pi on a computer in school.
I had a lot of fun discovering those things myself although I realized they had to be well-known. Later on I learned about the Riemann Zeta-function, Bernoulli numbers, and stuff.

By the way, and related to a discussion in the video, my friend Peter Grenholm from the years in Uppsala once said that "If there's a pi, there's a circle!". I think we were contemplating the mysteries of the normal distribution.

In 2004 I found an apparently new proof of the Wallis product formula, another amazing formula involving pi. That's another story, but while searching the literature to see if that proof was new (I still have doubts!) I stumbled upon a marvellous paper by the twin brothers Akiva and Isaak Yaglom from 1953. The paper was in Russian, but it was so short, elegant, and well written that I could understand it all by just looking at the equations. They derived three famous formulas by Wallis, Leibniz, and Euler, all involving pi. And they did it using trigonometric identities only, not calculus as in all the proofs I had seen before.

Those trigonometric identities were cute but still quite sophisticated, depending on complex numbers and a fair bit of algebra. But one day when I was teaching "Grunken" in Linköping, a sort of preparatory course for new students, one of the students asked me about a problem in their book. The problem was about expressing $\tan(x/2)$ in terms of $\tan x$. I knew there was such a formula, but hadn't really thought about it. But when we went through the solution, I immediately realized that the identities from the Yaglom-Yaglom paper could be easily derived, at least when a certain number $n$ was a power of 2. We discussed this in the coffee room in Linköping with some of my colleagues, and somebody, maybe Mats Aigner (?), showed me a paper by Josef Hofbauer where Euler's identity was derived in precisely this way (but Mats Aigner is not the M. Aigner cited in Hofbauer's paper, that's Martin Aigner).

So the idea was already known, but I still felt that there was something there that needed to be sorted out and simplified even further. If that trigonometry was so simple, why wouldn't the whole thing be just plain euclidean geometry?

So I tinkered with various ways of realizing the trigonometric identities geometrically. The problem was that in most of those constructions, the key quantities were tending either to zero or to infinity with increasing $n$. But finally I came up with a model that didn't need any annoying rescaling. I thought of it as stars revolving around a common center of gravity, and the relevant quantity was the total amount of light received at some other point in their orbit. But light-houses, as in the video, are arguably easier to move around!

I gave a talk about this at Chalmers in 2010, and put a LaTeXed version on my web page, mostly so that I wouldn't forget about it myself.

When I heard about the new video I didn't even remember which version of the paper I had put on my webpage. I had a different one where all the stars in the universe were on a line, and the theoretical physicists were debating the total amount of light. And then a little girl asked what would happen if the universe was finite and the stars were on a circle. A few years ago I had dinner with Lotta Olsson, an author of children's books, and we talked about poetry, mathematics, and Tönis Tönisson's book. Then I tried to rewrite the whole paper with rhymes in her style, but I didn't get it to work (yet!).

One of the funny things is that my paper isn't published anywhere except somewhere near the bottom of this webpage of mine that I only rarely update. It's not even on the arXiv. There is this industry (what should we call it?) in academia called bibliometry, where publications and citations are counted, but only in certain journals. A publication only counts as a "real" publication if a commercial publisher like Elsevier can trick universities to pay for it (using money from tax-payers of course). To enforce this corrupt system they talk about h-index, impact factors, and "outreach". This paper of mine has zero "outreach" of course, since it's not even a real paper according to this standard.

But somehow the internet tends to find what you put there. I have seen it mentioned on some blog somewhere, and I've been asked if I'm the author. And now, after a weekend, the 3Blue1Brown video explaining the paper has been viewed more than 200,000 times. I guess that means that most people who ever came across any of my mathematics did so in the last couple of days!









Sunday, February 18, 2018

Trenden på lång sikt

På internet diskuteras allt som oftast mordstatistik, jordens medeltemperatur med mera. Ny Teknik har till exempel nyligen publicerat en artikel om havsytans nivå och dess förväntade ökning under innevarande sekel. På facebook slår en kommentator fast att havsnivån inte har stigit sedan 2015, medan en annan (inte jag alltså, utan en annan kommentator) förklarar hur havsnivån ständigt förändrats under jordens historia och att det bara är att anpassa sig. Tonen är på andra ställen i tråden ganska hård, men lyckligtvis utbyts inga okvädesord mellan företrädarna för dessa två till synes oförenliga ståndpunkter. Istället tycks de förenas i sitt avfärdande av "miljötalibanerna" och deras prat om en trend över de senaste decennierna.

Det här med trender kan vara knepigt. Fast borde det inte bara vara att ta det stora perspektivet, så ser man tydligare vart den verkliga, långsiktliga, trenden pekar?

Jag tänkte vi kunde titta lite på en matematisk funktion. Det är förstås bara ett räkneexempel (ja ja, den som vill får googla "bara ett räkneexempel") men ändå. Låt oss ta funktionen

\[ \begin{multline} f(x) = \sum_{k=1}^\infty (-1)^{k+1} \frac{10^k\sin(x/10^k)}k = \\10\sin(x/10) - \frac{100\sin(x/100)}2 + \frac{1000\sin(x/1000)}3 - \frac{10000\sin(x/10000)}4 +\dots.\end{multline}\]

Det kanske inte är så lätt att se vad det är frågan om, så låt oss titta på en figur, där värdena på $x$ ligger mellan $-10$ och $10$.


Här ser man klart att funktionen $f$ växer: Ju större $x$ är, desto större blir $f(x)$. Men är detta verkligen den långsiktliga trenden? Vi zoomar ut och låter $x$ gå mellan $-100$ och $100$.



Oj, nu ser vi istället sanningen. Trenden är i själva verket avtagande, och den lilla ökningen vi såg i förra figuren var bara ett obetydligt och tillfälligt brott i denna trend. Ännu tydligare borde det bli om vi zoomar ut ännu mer, till $-1000\leq x \leq 1000$.


Aha, det är NU vi ser sanningen. I själva verket hade vi rätt hela tiden (utom nyss när vi hade fel), den SANNA trenden är växande. Nu tittar vi på intervallet $-10000$ till $10000$:


Ok, du som läsare ser nog vart jag vill komma. Den här funktionen har "trender" åt olika håll på alla olika skalor. Varje gång vi zoomar ut med en faktor 10, visar sig den föregående trenden bara vara ett kort avbrott i en ännu större och motsatt riktad trend. Vi tar en sista, från $-100000$ till $100000$:



Så vad är då sanningen? Jo den är att alla de här "trenderna" existerar samtidigt, och att ingen av dem gäller "på lång sikt". Men ska du gissa dig till funktionens "framtida" beteende baserat på dess "historia", är inte alla trender lika relevanta. Ska vi gissa oss till klimatet om femtio år, behöver vi inte ta hänsyn till vare sig tidvattnet eller förändringen i jordaxelns lutning.