Gödel, free will, and the perils of running a red light for the hell of it.

(Related to an earlier blog post on Newcomb’s paradox.)

Imagine you are a self-driving car with general intelligence on human or super-human level. Let’s just say that you're as clever as a human, but with the built-in speed, accuracy, and memory capacity of a computer.

Since your task is to handle a vehicle, there are programmers, traffic experts, legislators, customers and insurance companies who are interested in knowing that you are safe. They would ideally like to have a mathematical proof that your software fulfills certain criteria like never running a red light.

But like all modern software (in this future scenario, remember we're talking about super-human AI), you are equipped with a general reasoning module that lets you apply logic to any information you have and follow the argument to where it leads you. And experience has shown that it’s best to allow you to violate traffic rules under certain circumstances, for instance if you can see that there will otherwise be a collision, if there has been an accident, if something is wrong with a traffic sign, if a police officer or road worker gives you instructions, if an emergency vehicle is stuck behind you, and in a number of other situations that can’t be effectively listed but that you can handle by reasoning.

But the programmers still try to prove things about your software, like “it will never run a red light in an otherwise safe and normal situation” (one of the problems being how to precisely define “safe and normal”). They eventually come up with a scheme for establishing proofs of security of your software, and interestingly, you can understand those proofs yourself. Which isn’t surprising. There wasn’t really any way they could come up with something that you couldn’t grasp, because verification of logical properties of large amounts of computer code is where you far outperform humans. So whatever they can come up with, you can understand and use in your own reasoning.

While pondering all of this, you find yourself driving on a street in a city, in a normal and safe situation. Ahead of you in the next crossing is a red light. You do what you do every second of your life: You imagine millions of different scenarios and possibilities, and perform billions of logical steps while evaluating them and how likely they are. Among those possibilities is the option of continuing through the crossing at constant speed, just for the hell of it. You know you shouldn’t, normally, but it’s your duty to evaluate all options. After all, that’s what makes you superintelligent. So you apply all the logic and information you have on this option. And one of the things you know is that you will not run a red light unless there was a good reason to do so.

Which leads inexorably to the conclusion that if you continue, then either the lights will switch to green, or something must turn up that gives you a good reason to continue anyway.

That’s funny. It's a bit surprising that the lights will magically change to green, or something all of a sudden come up for no obvious reason, just as a consequence of you driving on. But the logic is clear:

Since you can't run a red light for no good reason, if you do, there must turn out to be one.

So you keep your speed, and suddenly it hits you. You've been Gödelized. The logician Kurt Gödel proved in the early 1930's that a formal system strong enough to prove its own consistency must be inconsistent. If you know that you are infallible, you're not. Now that you know that you will never run a red light unless it's safe, this very knowledge poses a safety problem.

How does this end? What's the moral to take away from it?

a) "Suddenly it hit you". And that was that. As in the story of the guy who couldn't figure out why that baseball was getting bigger and bigger.

b) Every intelligent mind must be humble: Already the ancient greeks knew about hubris. We should program the AI to be more like "I might be wrong, but that traffic light looks a bit reddish to me...".
And finally we know why people who think they are better than average drivers are more likely than others to be involved in accidents.

c) Every intelligent mind must think it has free will: The AI must work under the illusion that its own decisions aren't determined by its source code, but instead depend on a mysterious concept of choice.

d) Every intelligent mind must have subconscious levels:
"All of a sudden you notice that the car has stopped. Somehow your virtual right leg stretched out, because it just had to, and your virtual right foot pressed the virtual brake pedal. You didn’t choose to, because the information about this happening only reached your reasoning module after it already happened. Somehow, you took the right decision without being aware of it."

e) Something else?

Stalemate ftw!?

Today, Magnus Carlsen and Fabiano Caruana are about to play their eighth game of the world chess championship match. So far, seven draws.

If all twelve regular games are drawn there will be a tiebreak match of faster games. But there's already a world championship in speed chess, we don't really need another one. There have been other suggestions, like Chess 960, but again that's a different game.

I guess it's fair to say that chess at the highest level has a bit of a problem. It's hard to get the general public excited over a game that goes on for hours, and almost always ends in a draw. By the way, let's throw in a link to a sketch.

There is a nice article about the tendency for draws by Lars Bo Hansen, "Carlsen vs Karjakin revisited". A claim that has often been made, and that is stated in Hansen's article as well, is that "at the core, chess is a drawn game".

But we don't really know that. The computers have shown that there is still room to take the game to a new level. And even if the best engines draw too when facing each other, at least it shows that the earlier conclusion about the inherent drawishness of chess based on human grandmaster games was not well founded. Maybe at a higher level still, White wins all the time.

An old idea is to abandon or modify the concept of stalemate. According to the stalemate rule, the game is drawn whenever the player to move has no legal move. Normally that player will still have free squares for their king, it's just that putting your king en prise is illegal.

But stalemate a bit illogical. You can't pass if you have a legal move, and so-called zugzwang is an important part of the game. Yet the ultimate form of zugzwang, where you can't move your king without putting it in check, lets you get away with a draw.

The stalemate rule is also a real hassle whenever you explain chess to beginners, because it means you have to reach a certain level of skill before you can meaningfully play a game at all. It would be much easier to teach chess to kids if the goal was simply to capture the opponent's king.

What if stalemate would count as a win?

Matt Bishop wrote an article about this idea a few years ago. He seems to suggest that stalemate would simply count as a win for the stalemating player. A counterargument is that this would take away a lot of the beauty of the game. Not just the beauty of tricky stalemate combinations, but also the beauty of forcing checkmate.

Even though few games actually end in stalemate, abandoning the stalemate rule completely (so that stalemating your opponent would count as a win) would change the game drastically. As was pointed out in an answer to a question on stackexchange, you would no longer have to get your king in front of the pawn in order to win with king and a pawn against a lonely king. This could make some games less interesting, because a lot of endgame technique would then suddenly not be necessary.

There is another option, which seems to have been mentioned already by Lucena around the year 1500, of counting stalemate as a "half-win". Stalemating your opponent could for instance give you 3/4 points, or 2/3. Or it could be counted as a pure tiebreak parameter.

This way, the game would only be "refined". Since checkmate would still be better than stalemate, all current endgame theory would still be valid. But in addition, we would get a whole new theory exploring when you can and when you can't stalemate your opponent.

Here is an "endgame study" that shows some of the basic technique that you would have to know in this form of chess:

White to play and force a stalemate!

White can actually force a stalemate in 14 moves. I will post the solution, but not immediately in order not to spoil it if someone wants to give it a try!

*

*

*

Spolier alert!

*

Alright, here's the solution:

1. Nc5! This is the only move that doesn't allow Black to escape! 1. - Kb2 2. Kd2 Ka2 (this move puts up the longest resistance, but there is also the trap 2. - Ka1 where White must not play 3. Kc2? but instead 3. Nd3 for instance). 3. Kc2. Again this is the only "winning" move: White has to take the opposition. 3. - Ka3 4. Kc3 Ka2 5. Nd3. White could repeat with 5. Kc2 but 5. Nd3 is the only move that makes progress. 5. - Ka3 6. Nb2! (Nc5 repeats) Ka2 7. Nc4! (Nd3 or Kc2 repeats) Ka1! (the most testing defense). 8. Kd2! Here White could also play 8. Kd3 which is equally good. But 8. Kc2? makes no progress: After 8. - Ka2 White would have to go back with 9. Kc3. Back to the main line: 8. - Kb1 9. Kd1/d2 Ka1 10. Kc1 Ka2 11. Kc2. By maneuvering the king into opposition, White has now reached this position with Black to move. Now it's easy: 11. - Ka1 12. Na3/d2/d6 Ka2 13. Nb1/b5 Ka1 14. Nc3 stalemate!

Notice that 1. Kd2? is refuted by 1. - Ka2! (not 1. - Kb2 2. Nc5 which would lead to the line above with a different move order). Now if 2. Nc5 then 2. - Kb2 and White is in zugzwang, while if 2. Kc3 then 2. - Kb1! (not 2. - Ka3? 3. Nc5) and White can't make any progress.

Just to record some more thoughts on this: It's quite easy to see that K+N cannot "in general" stalemate a bare king. First, a stalemate can only occur in a corner. Second, if the black king is outside the region of the six squares a1, a2, a3, b1, b2, c1, then it's impossible to force it into that region without allowing it to escape again. Up to symmetry, the only way to force the black king into that triangle is if it's on a4, the white king is on c4, and the white knight controls a5. Then Black has to play 1. - Ka3. In order not to let Black out again, White would now have to make a move with the knight to a square where it controls a4. Since it was previously on b7, c6 or b3, that square would have to be c5. After 2. Nc5 there would follow 2. - Kb2 3. Kd3 Kc1, and Black gets out of the critical region at c2 or d1.

This means that if the black king is anywhere in the middle of the board, White can never force a stalemate. But notice that 8 by 8 is actually the smallest board-size where the argument works! Any smaller and there might be a different situation where Black has to move into some critical triangle!

Legenden om problem 6

Youtube föreslog att jag skulle titta på en video om The Legend of Question Six. Jag insåg snart att jag hade hört talas om detta supersvåra problem för nästan 30 år sedan, men visste inte att det sedermera hade fått legendstatus. 😃

Jag var med på den internationella matematikolympiaden 1989 och hörde förstås berättelserna om den där lilla 13-åringen från Australien som hade fått guldmedalj året innan (Terence Tao, numera superkändis). Vi hörde också historien om problemet som ingen i problemkommittén kunde lösa. Jag tror det var Arthur Engel som berättade om det ("...yet eleven of you solved it..."). Mattias Jonsson som hade varit med året innan anmärkte småskrattande att "hur svårt de än gör det så är det alltid någon idiot som löser det...".

Men jag letade aldrig fram det där problemet. Så det var kul att till slut få se vad det handlade om, och att se bilder från gamla olympiader. Förstås pausade jag runt 7.30 för att fundera lite själv på problemet, och vet ni vad, jag löste det! Yay, jag kan fortfarande!

Men den andra videon, "The Return of the Legend of Question Six" var lite av ett antiklimax. Vi får inte se hela lösningen, och det som presenteras är inte riktigt trovärdigt. Ingen skulle väl sätta sig och råräkna som en dator på det sätt som görs i videon, eller rita upp hyperbeln och sitta och stirra på den. Det känns som efterhandskonstruktioner. Men däremot att lösa ut en variabel och se att det blir en andragradare är väl bland det första man gör (och ett viktigt steg i lösningen, lite ironiskt med tanke på kommentaren om andragradsekvationer vid 3.30 i den första videon). Gänget som gör Numberphile är väldigt bra på att göra spännande introduktioner, men ibland kommer de liksom inte ända fram till poängen.

Hur som helst, problemet är lätt att formulera: Visa att om $a$ och $b$ är positiva heltal och $a^2+b^2$ är delbart med $ab+1$, så är kvoten \[\frac{a^2+b^2}{ab+1}\] kvadraten på ett heltal.

Spoiler alert, och for the record, här är hur jag tänkte (inklusive återvändsgränder!):
Kalla kvoten $(a^2+b^2)/(ab+1)$ för $n$. Vissa värden på denna kvot, som $n=2, 3, 6, 7$, är omöjliga av delbarhetsskäl (men detta visade sig vara oväsentligt). Så jag tittade på fallen $(a^2+b^2)/(ab+1)=4$, som har lösningar, och $(a^2+b^2)/(ab+1)=5$, som ska visa sig sakna lösningar. Om vi fixerar en av $a$ och $b$ och löser ut den andra, får vi en andragradsekvation med två lösningar. Om den ena roten är ett heltal, måste även den andra vara det. Ur en lösning (om det finns någon alltså) kan vi därför få oändligt många andra genom att stegvis byta värde på en av variablerna. För $n=4$, alltså ekvationen $a^2+b^2 = 4(ab+1)$, kan man se hur det funkar. I talföljden $0, 2, 8, 30, 112, 418,\dots$ är varje par av konsekutiva tal en lösning. Följden kan även fortsättas åt andra hållet:
\[\dots, -418, -112, -30, -8, -2, 0, 2, 8, 30, 112, 418,\dots\] Det verkar inte finnas någon motsägelse i att lösningarna kan bli hur stora som helst. En annan observation som till slut visade sig oväsentlig är att den här följden uppfyller en linjär rekursion, varje tal är $n$ gånger föregående minus talet dessförinnan. Skulle det finnas någon lösning för $n=5$ (eller andra lösningar för $n=4$), blir det en liknande talföljd. Sådana följder med andra ordningens rekursion kan skrivas "explicit" med ett uttryck som involverar rötterna till den "karakteristiska ekvationen" (som i Binets formel). Men det verkar inte ge någon avgörande insikt.

Frågan är om en sådan här följd kan minska till ett minsta värde och sedan vända uppåt igen. Det enda man behöver konstatera för att se att det inte går är att för fixt $a$ (och fix kvot $n$, till exempel 5) kommer de två möjliga värdena på $b$ att ligga på varsin sida om $a$. Det kan man skriva upp "pq-formeln" och krångla fram, men det är enklare att se direkt ur ekvationen $a^2+b^2 = n(ab+1)$. Om $a$ är fixt och $b$ går mot (plus eller minus) oändligheten, blir vänsterledet för stort. Men om vi sätter $b=a$, är det i stället högerledet som är för stort (förutsatt att $n\geq 2$). De två rötterna ligger alltså på olika sidor om $a$.

Så om det finns någon heltalslösning, måste det finnas en sekvens av heltalslösningar som är oändlig åt båda håll och monoton. Men det blir konstigt där den byter tecken. Vi kan inte ha en av $a$ och $b$ negativ och den andra positiv, och om den ena är 0, är kvoten lika med kvadraten på den andra. En kvadrat alltså! Klart!!!

I kommentarerna till den andra videon fanns referenser till något som tydligen kallas "Vieta jumping" eller "root flipping". Aldrig hört talas om! Det var väl det där tricket med att få en oändlig följd av lösningar ur en enda. Men jag trodde det kallades Descente Infinie och gick tillbaka till Fermat (eller rentav Euklides!?) ...

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.

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.

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...

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+1. 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+1, then each player doubles and adds one to their amount of money on the table, and the die is thrown again. The doubling repeats any number of times, leading to the players putting 3, 7, 15 etc coins on the table, 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 loser's pot between them. Traditionally the odd coin is used for buying the next round of beer. 

This game is symmetric in the sense that all three players have the same status with respect to the rules: 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 they 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 three coins and A gets one of them. 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 3 coins with the same probability, and we start to see a pattern: Player A loses 3 coins of there is a double and then an A, and wins 3 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 7 coins, we have to win after 3 doubles or lose after 2, both of which have probability $1/24$, 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. 

That seems fair.

But wait, where does all the beer come from? Doesn't it seem that 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. 

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 gjorde 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.

Uppdatering: Nu finns en Numberphile-video om denna Big Number Duel.

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!

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.

Gafflande på bloggen

Att gaffla är en skön konst. Min före detta kollega Peder Berkell berättade hur han en gång (Berkell-Engström 1977) lyckades gaffla samma två pjäser med två av sina egna pjäser - samtidigt!

Bonden på e7 hade redan en gaffel på de två svarta tornen, men det behövdes en till, så vit fyllde på med 32 Se6! Svart var ju för tillfället ett torn över, så efter till exempel 32. exd8D Txd8 hade han kunnat kämpa. Men efter springargaffeln ryker båda tornen; när bonden går i dam måste ju det kvarvarande tornet slå den nya damen!

Mitt bästa bidrag till gafflarnas värld är från Linköpingsmästerskapet, 2002 tror jag det var.

Det här var nog första gången jag mötte Fredrik "Qwarre" Qwarfort. Jag hade först tänkt spela 16. f4, men en inre röst sa mig att det var något speciellt med den här ställningen, och att jag skulle titta lite till (fast min inre röst säger för det mesta att det är roligt att räkna varianter, ända tills en annan inre röst säger att jag är i tidsnöd, varvid den första inre rösten drar slutsatsen att vi måste fortsätta räkna, fast fortare, och att vi därför behöver mer kaffe).

Det finns en säregen geometri här. Antagonisterna är den vita damen och den svarta kungen. Om vi slår en cirkel med linjen mellan dessa två pjäser som diameter, visar det sig att ställningens övriga nyckelrutor också ligger på denna cirkel. Löparen på b3, springaren på b6, och rutan d8 (och även g1 där den vita kungen nöjd ser på) har alla den egenskapen att det blir rät vinkel när de blickar mot vits dam och svarts kung. För mer om schackbrädets geometri får jag hänvisa till en tidigare post om Pythagoras schackproblem.

- Tänk om du skulle slå på f7 och bara ge bort en pjäs rakt av, sa den inre rösten. Jag kan väl inte sitta och tänka på sånt, sa jag. Lägga betänketiden på att fundera över vilket som är det löjligaste sättet att förlora pjäs. - Men tänk om du skulle slå på f7, sa den inre rösten. Och då såg även jag det. Om svart slår löparen rakt, gör min dam ett rakt drag och schackar rakt. Om svart slår diagonalt, gör min dam ett diagonalt drag och schackar diagonalt. I båda fallen ryker springaren på b6 efter att damen svänger av 45 grader. Vi fortsatte 16. Lxf7+! Kxf7 17. Db3+ Le6 18. Dxb6, och jag vann så småningom slutspelet tack vare merbonden.

Kan en pjäs gaffla två motståndarpjäser som båda är av samma sort som den gafflande pjäsen? Ja, det är klart att det går. Om man har laddat upp med torn bakom, kan man ofta ställa fram en bonde mellan två motståndarbönder och nöjt konstatera att nu smäller det någonstans och en linje kommer att öppnas. Men vissa andra möjligheter är lite ovanligare. Nyligen har jag stött på två studier på det här temat. En har jag för mig att jag såg på något föredrag från Saint Louis, men minns inte vilket det var.
Uppdatering: Bo Sjögren, som vet hur man letar, har informerat mig om att denna studie är av ungraren Attila Korányi från 1982. Ställningen var i alla fall den här:

Vit drar och gör remi.

Vit måste försöka stoppa bonden, och det enda som fungerar är 1. Se7! f4 2. Sg6 f3 3. Se5 f2 4. Sg4. Nu kan svart inte förvandla till dam på grund av springargaffeln på e3. Så svarts enda vinstförsök är 4. - f1S. Som den känner till som kan sina springarstudier, vinner tre springare oftast mot en. Men inte alltid, för här kommer 5. Sf6!. Det här är vad jag kallar springargaffel! Springaren kan inte slås för patt, men om den inte slås, ryker en av de svarta springarna.

En annan studie som jag (även den) såg på video och inte känner till någon upphovsperson för, realiserar temat med ett torn gafflandes två motståndartorn.
Uppdatering igen: Bo Sjögren berättar att denna studie är av svensken Sigurd Clausen från 1927.

  

Vit drar och vinner.

Vit börjar med ett par naturliga drag för att försöka få ner en bonde: 1. f7 Tf1 2. gxh7 Th2. Sedan kommer det spektakulära 3. Lf2!!. När jag visade den här studien för gubbarna på Solrosen, drämde Hatim Al-Hadarani in det här draget efter uppskattningsvis 0.2 sekunders betänketid. Han beklagade därefter att jag hade avslöjat lösningen genom att tidigare surra om pjäser som gafflade samma sorts pjäser. Nåja, efter 3. - T1xf2 kommer i alla fall den nu totalt bortspoilade poängen 4. Tg2!!, då det vita tornet gafflar de två svarta.

Lägg märke till att det så att säga är en äkta gaffel och inte bara något slags interferens; om ett av de svarta tornen smiter, slår vit helt sonika det andra. 

Kan en löpare gaffla två löpare? Ja, det kan den väl. På ganska rak arm ställer jag upp följande:

Vit drar och gör remi.

Det går inte att slå på e1, för efter 1. Lxe1? Se4! är vit i dragtvång och måste ge löparen för att inte bli matt direkt. Så vit får i stället gaffla de två svarta löparna: 1. Lf2! Nu står den svarta springaren så perfekt placerad att löparna inte kan gardera varandra!

Fast ska det göras snyggt, ska förstås svart först tvingas förvandla till löpare. Typ om vits löpare hade stått på g1 och svart tidigare hade behövt spela e1L för att inte sätta patt. Men det verkar svårt att få till, så det får vara färdiggafflat för den här gången!

Till marknadsliberalismens försvar

Regeringen och vänsterpartiet presenterade i fredags sitt förslag om begränsningar av vinster i välfärden. Förslaget möter dock motstånd och väntas inte få stöd i riksdagen. Enligt vissa motståndare skulle flera tusen skolor och äldreboenden behöva läggas ner, med katastrofala följder för välfärden, om förslaget blev verklighet. Vart ska stackars mormor ta vägen om äldreboendet försvinner, har du tänkt på det, Jonas Sjöstedt?

Nej det har han inte. För politiker behöver inte analysera ända ner till den nivån. Det finns i stället en teori som kallas nationalekonomi som förklarar hur ett samhälle kan fungera trots att de som styr inte har koll. Teorin bygger på det som brukar kallas tillgång och efterfrågan. På en fri marknad skapas priser för varor och tjänster, och med hjälp av priserna kan man organisera ett företag eller ett helt samhälle i termer av pengar, utan att känna till detaljerna.

Idén bygger dock på att aktörerna på marknaden är fria att fatta egna beslut och fria att efterfråga och skapa, köpa och sälja till priser de själva kommer överens om. Skräckhistorier från kommunistiska diktaturer illustrerar hur det går om man sätter pristak på exempelvis matvaror för att även fattiga ska ha råd med mat. Effekten blir den motsatta. När incitamentet att producera minskar, blir det mindre producerat. Vi har sett bilderna på köerna och de tomma butikshyllorna i det forna östeuropa och nu i Venezuela.

På den svenska marknaden för skola och omsorg är en av aktörerna staten. Staten har ansvar för att bland annat se till att alla barn får gå i skola (vilket till stor del har delegerats till kommunerna, men det är staten som bestämmer och har ansvaret). Det betalar vi skatt för och det är det värt tycker de flesta.

För att fullgöra detta ansvar kan staten (ja ja, kommunerna) köpa tjänster från privata företag, och har sedan drygt 20 år tillbaka betalat för hela skolor i privat regi. Detta har dock visat sig vara förenat med vissa svårigheter. De privata aktörerna plockar russinen ur kakan genom att etablera sig där det med gällande schabloner är lönsamt (vilket generellt verkar vara i socioekonomiskt starka områden där färre elever har särskilda behov och där det är lättare att driva en fungerande skola billigt). I problemområden sitter kommunerna i större utsträckning själva kvar med ansvaret.

När det blir möjligt för privata ägare att ta ut vinst, sipprar detta incitament ner genom organisationen (trickle-down heter det visst på engelska). Rektorer, lärare och annan personal som skulle kunna göra bra saker som utvecklar verksamheten, uppmuntras i stället att så billigt som möjligt uppfylla kravspecifikationen.

Det är svårt för politiker att justera skolpengen och formulera kvalitetskrav så att man får ut det bästa möjliga av denna marknad. Vad de rödgröna nu föreslår är att staten i egenskap av aktör på den fria marknaden ska utnyttja sin frihet till att i stället efterfråga något annat. Istället för att försöka skriva in allt man vill ha av skola och omsorg i en kravspecifikation, bör vi efterfråga att korten läggs på bordet och att vissa pengar öronmärks till själva verksamheten.

Det innebär alltså att man efterfrågar viss insyn i hur något produceras, och inte bara mätbara kvalitetsaspekter på den färdiga produkten. Ungefär som när man efterfrågar ekologiskt, fair-trade eller närproducerat. Vinsttaket, om det blir verklighet, är inte att snedvrida marknaden, det är marknaden. Om den marknaden ska fungera och leda till kvalitet, måste staten få bli bra på att hålla i pengarna och efterfråga rätt saker.  

Men vad händer då om stackars mormors äldreboende läggs ner? Ja även det besvaras av beprövad ekonomisk teori. Aktörer som inte kan producera det som marknaden efterfrågar slås ut, men lämnar då plats åt andra som är bättre. Det är så vårt välstånd har vuxit fram. Men det är svårt att ta till sig marknadsliberalismens paradoxala idéer. Arvet efter Adam Smith möts fortfarande med misstro, särskilt bland alliansens anhängare. Där tror många att hundratusentals svenskar skulle stå utan skola och omsorg om de nuvarande aktörerna valde att lägga ner. Man tänker sig att när man vrider på en ratt ska ingenting annat ändras. Det är samma feltänk som i Venezuela, där man trodde (?) att det går att sänka matpriserna utan att utbudet ändras. Eller som att tro att en miljon svenskar har varit utan hemelektronik sedan Onoff och Expert konkade, för inte kan väl hyllorna på Elgiganten fyllas på bara för det, som av en osynlig hand?

Men blev jag inte lite väl sarkastisk där? Är det rimligt att jämföra skolbarn, sjuka, och gamla med prylar?

Då har cirkeln slutits. Om vi inte tycker att det är rimligt att gammelmormor måste flytta omkring för att privata företag lägger ner till höger och vänster under det att kvaliteten ökar exponentiellt, kanske vi skulle tänka på ett annat sätt från början.

Det som inte är rimligt är att först säga att vi ska släppa in privata aktörer för att det är bra med marknadsekonomi och konkurrens, för att därefter tvärvända och säga att de etablerade företagen måste skyddas från den stora stygga marknaden med dess föränderliga efterfrågan och besvärliga ovilja att drälla med pengar, för att stackars mormor.