2020-11-05

Gettysburg Address

Abraham Lincoln

Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.

Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this.

But, in a larger sense, we can not dedicate—we can not consecrate—we can not hallow—this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us—that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion—that we here highly resolve that these dead shall not have died in vain—that this nation, under God, shall have a new birth of freedom—and that government of the people, by the people, for the people, shall not perish from the earth.

2020-11-01

A Father To His Son

by Carl Sandburg

A father sees his son nearing manhood.
What shall he tell that son?
“Life is hard; be steel; be a rock.”
And this might stand him for the storms
and serve him for humdrum monotony
and guide him among sudden betrayals
and tighten him for slack moments.
“Life is a soft loam; be gentle; go easy.”
And this too might serve him.
Brutes have been gentled where lashes failed.
The growth of a frail flower in a path up
has sometimes shattered and split a rock.
A tough will counts. So does desire.
So does a rich soft wanting.
Without rich wanting nothing arrives.
Tell him too much money has killed men
and left them dead years before burial:
the quest of lucre beyond a few easy needs
has twisted good enough men
sometimes into dry thwarted worms.
Tell him time as a stuff can be wasted.
Tell him to be a fool every so often
and to have no shame over having been a fool
yet learning something out of every folly
hoping to repeat none of the cheap follies
thus arriving at intimate understanding
of a world numbering many fools.
Tell him to be alone often and get at himself
and above all tell himself no lies about himself
whatever the white lies and protective fronts
he may use against other people.
Tell him solitude is creative if he is strong
and the final decisions are made in silent rooms.
Tell him to be different from other people
if it comes natural and easy being different.
Let him have lazy days seeking his deeper motives.
Let him seek deep for where he is born natural.
Then he may understand Shakespeare
and the Wright brothers, Pasteur, Pavlov,
Michael Faraday and free imaginations
Bringing changes into a world resenting change.
He will be lonely enough
to have time for the work
he knows as his own.

2020-10-31

擬輓歌辭

作者：陶淵明

有生必有死，早終非命促。
昨暮同為人，今旦在鬼錄。
魂氣散何之？枯形寄空木。
嬌兒索父啼，良友撫我哭。
得失不復知，是非安能覺？
千秋萬歲後，誰知榮與辱！
但恨在世時，飲酒不得足。

在昔無酒飲，今但湛空觴。
春醪生浮蟻，何時更能嘗？
餚案盈我前，親舊哭我傍。
欲語口無音，欲視眼無光。
昔在高堂寢，今宿荒草鄉。
荒草無人眠，極視正茫茫。
一朝出門去，歸來良未央。

荒草何茫茫，白楊亦蕭蕭！
嚴霜九月中，送我出遠郊。
四面無人居，高墳正嶕嶢。
馬為仰天鳴，風為自蕭條。
幽室一已閉，千年不復朝。
千年不復朝，賢達無奈何！
向來相送人，各自還其家。
親戚或餘悲，他人亦已歌。
死去何所道，托體同山阿。

2020-10-30

LeetCode - Algorithms - 4. Median of Two Sorted Arrays

Problem

4. Median of Two Sorted Arrays

Follow up

The overall run time complexity should be O(log (m+n)).

Java

extra space

On the basis of 88. Merge Sorted Array, this is not preferable method, just better than nothing.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        final int m = nums1.length;
        final int n = nums2.length;
        if (m == 0)
            return (n & 1) == 1 ? nums2[n / 2] : (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
        if (n == 0)
            return (m & 1) == 1 ? nums1[m / 2] : (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
        int[] aux = merge(nums1, m, nums2, n);
        double median = ((m + n) & 1) == 1 ? aux[(m + n) / 2] : (aux[(m + n) / 2 - 1] + aux[(m + n) / 2]) / 2.0;
        return median;
    }

    private int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int[] aux = new int[m + n];
        if (m == 0) {
            for (int i = 0; i < n; i++)
                aux[i] = nums2[i];
            return aux;
        } else {
            for (int i = 0; i < m; i++)
                aux[i] = nums1[i];
        }
        int idx = m + n - 1;
        m--;
        n--;
        for (; m >= 0 && n >= 0; ) {
            if (nums1[m] < nums2[n]) {
                aux[idx--] = nums2[n];
                n--;
            } else {
                aux[idx--] = nums1[m];
                m--;
            }
        }
        if (n >= 0) {
            for (int i = 0; i <= n; i++)
                aux[i] = nums2[i];
        }
        return aux;
    }
}

Submission Detail

2091 / 2091 test cases passed.
Runtime: 2 ms, faster than 99.73% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 10.39% of Java online submissions for Median of Two Sorted Arrays.

2020-10-28

LeetCode - Algorithms - 125. Valid Palindrome

Problem

125. Valid Palindrome

Java

Two pointers

class Solution {
    public boolean isPalindrome(String s) {
        final int N = s.length();
        char c1, c2;
        for (int i = 0, j = N - 1; i < j; ) {
            c1 = s.charAt(i);
            c2 = s.charAt(j);
            if (!Character.isLetterOrDigit(c1))
                i++;
            else if (!Character.isLetterOrDigit(c2))
                j--;
            else if (Character.toLowerCase(c1) != Character.toLowerCase(c2)) {
                return false;
            } else {
                i++;
                j--;
            }
        }
        return true;
    }
}

Submission Detail

481 / 481 test cases passed.
Runtime: 2 ms, faster than 98.05% of Java online submissions for Valid Palindrome.
Memory Usage: 39 MB, less than 5.64% of Java online submissions for Valid Palindrome.

alphanumeric and binary

class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        int N = s.length();
        for (int i = 0; i < N / 2; i++)
            if (s.charAt(i) != s.charAt(N - 1 - i))
                return false;
        return true;        
    }
}

Submission Detail

480 / 480 test cases passed.
Runtime: 883 ms, faster than 12.58% of Java online submissions for Valid Palindrome.
Memory Usage: 47.3 MB, less than 18.43% of Java online submissions for Valid Palindrome.

JavaScript

Algorithms, 4th Edition

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let str = s.toLowerCase().replace(/[^a-zA-Z0-9]/g, "");
    const N = str.length;
    for (let i = 0; i < N / 2; i++) {
        if (str.charAt(i) != str.charAt(N - 1 - i))
            return false;
    }
    return true;    
};

Submission Detail

480 / 480 test cases passed.
Runtime: 67 ms, faster than 96.43% of JavaScript online submissions for Valid Palindrome.
Memory Usage: 44.2 MB, less than 82.85% of JavaScript online submissions for Valid Palindrome.

Two pointers

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    const N = s.length;
    const ALPHANUMERIC = /^[a-z0-9]+$/i;
    let c1, c2;
    for (let i = 0, j = N - 1; i < j; ) {
        c1 = s.charAt(i);
        c2 = s.charAt(j);
        if (!ALPHANUMERIC.test(c1))
            i++;
        else if (!ALPHANUMERIC.test(c2))
            j--;
        else if (c1.toLowerCase() != c2.toLowerCase()) {
            return false;
        } else {
            i++;
            j--;
        }
    }
    return true;    
};

Submission Detail

480 / 480 test cases passed.
Runtime: 102 ms, faster than 45.96% of JavaScript online submissions for Valid Palindrome.
Memory Usage: 44.9 MB, less than 61.23% of JavaScript online submissions for Valid Palindrome.

2020-10-27

LeetCode - Algorithms - 234. Palindrome Linked List

Problem

234. Palindrome Linked List

Follow up

Could you do it in O(n) time and O(1) space?

Java

Break and reverse second half

We can use a fast and slow pointer to get the center of the list, then reverse the second list and compare two sublists. The time is O(n) and space is O(1).

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;

        //find list center
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode secondHead = slow.next;
        slow.next = null;

        //reverse second part of the list
        ListNode p1 = secondHead;
        ListNode p2 = p1.next;
        while (p1 != null && p2 != null) {
            ListNode temp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = temp;
        }
        secondHead.next = null;

        //compare two sublists now
        ListNode p = (p2 == null ? p1 : p2);
        ListNode q = head;
        while (p != null) {
            if (p.val != q.val)
                return false;
            p = p.next;
            q = q.next;
        }
        return true;
    }
}

Submission Detail

26 / 26 test cases passed.
Runtime: 1 ms, faster than 95.13% of Java online submissions for Palindrome Linked List.
Memory Usage: 41.7 MB, less than 5.11% of Java online submissions for Palindrome Linked List.

extrap space

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<ListNode> list = new ArrayList<ListNode>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int n = list.size();
        for (int i = 0; i < n / 2; i++) {
            if (list.get(i).val != list.get(n - 1 - i).val)
                return false;
        }
        return true;
    }
}

Submission Detail

26 / 26 test cases passed.
Runtime: 2 ms, faster than 39.06% of Java online submissions for Palindrome Linked List.
Memory Usage: 42.8 MB, less than 5.11% of Java online submissions for Palindrome Linked List.

Recursion

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null)
            return true;
        if (head.next == null)
            return true;
        ListNode secondLast = head;
        while (secondLast.next.next != null) {
            secondLast = secondLast.next;
        }
        if (head.val == secondLast.next.val) {
            secondLast.next = null;
            return isPalindrome(head.next);
        } else {
            return false;
        }
    }
}

Submission Detail

26 / 26 test cases passed.
Runtime: 1406 ms, faster than 5.02% of Java online submissions for Palindrome Linked List.
Memory Usage: 42.7 MB, less than 5.11% of Java online submissions for Palindrome Linked List.

2020-10-26

LeetCode - Algorithms - 141. Linked List Cycle

Problem

141. Linked List Cycle

Java

Two pointers

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean b = false;
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
            if (fastPointer != null && fastPointer.next == slowPointer) {
                b = true;
                break;
            }
        }
        return b;
    }
}

Submission Detail

17 / 17 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Linked List Cycle.
Memory Usage: 39.3 MB, less than 12.07% of Java online submissions for Linked List Cycle.

extra space

import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean b = false;
        Set<ListNode> coll = new HashSet<ListNode>();
        ListNode node = head;
        while(node!=null) {
            if (!coll.contains(node)) {
                coll.add(node);
            }
            else {
                b = true;
                break;
            }
            node = node.next;
        }
        return b;
    }
}

Submission Detail

17 / 17 test cases passed.
Runtime: 3 ms, faster than 19.93% of Java online submissions for Linked List Cycle.
Memory Usage: 39.5 MB, less than 11.80% of Java online submissions for Linked List Cycle.

2020-10-26

LeetCode - Algorithms - 1290. Convert Binary Number in a Linked List to Integer

Problem

1290. Convert Binary Number in a Linked List to Integer

Java

Bit Manipulation

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        if (head == null)
            return 0;
        int d = head.val;
        while (head.next != null) {
            d = (d << 1) | head.next.val;
            head = head.next;
        }
        return d;
    }
}

Submission Detail

102 / 102 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Convert Binary Number in a Linked List to Integer.
Memory Usage: 36.4 MB, less than 11.21% of Java online submissions for Convert Binary Number in a Linked List to Integer.

my solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int n = 0;
        ListNode node = head;
        while (node != null) {
            n++;
            node = node.next;
        }
        node = head;
        int x = 0;
        for (int i = n - 1; i > 0; i--) {
            x += node.val * (2 << (i - 1));
            node = node.next;
        }
        x += node.val;
        return x;
    }
}

Submission Detail

102 / 102 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Convert Binary Number in a Linked List to Integer.
Memory Usage: 36.4 MB, less than 10.97% of Java online submissions for Convert Binary Number in a Linked List to Integer.

2020-10-25

Symmetry, reality's riddle - Marcus du Sautoy - TEDGlobal 2009 - Transcript

On the 30th of May, 1832, a gunshot was heard ringing out across the 13th arrondissement in Paris. A peasant, who was walking to market that morning, ran towards where the gunshot had come from, and found a young man writhing in agony on the floor, clearly shot by a dueling wound. The young man’s name was Evariste Galois. He was a well-known revolutionary in Paris at the time. Galois was taken to the local hospital where he died the next day in the arms of his brother. And the last words he said to his brother were, “Don’t cry for me, Alfred. I need all the courage I can muster to die at the age of 20.”

It wasn’t, in fact, revolutionary politics for which Galois was famous. But a few years earlier, while still at school, he’d actually cracked one of the big mathematical problems at the time. And he wrote to the academicians in Paris, trying to explain his theory. But the academicians couldn’t understand anything that he wrote. This is how he wrote most of his mathematics.

So, the night before that duel, he realized this possibly is his last chance to try and explain his great breakthrough. So he stayed up the whole night, writing away, trying to explain his ideas. And as the dawn came up and he went to meet his destiny, he left this pile of papers on the table for the next generation. Maybe the fact that he stayed up all night doing mathematics was the fact that he was such a bad shot that morning and got killed.

But contained inside those documents was a new language, a language to understand one of the most fundamental concepts of science – namely symmetry. Now, symmetry is almost nature’s language. It helps us to understand so many different bits of the scientific world. For example, molecular structure. What crystals are possible, we can understand through the mathematics of symmetry.

In microbiology you really don’t want to get a symmetrical object, because they are generally rather nasty. The swine flu virus, at the moment, is a symmetrical object. And it uses the efficiency of symmetry to be able to propagate itself so well. But on a larger scale of biology, actually symmetry is very important, because it actually communicates genetic information.

I’ve taken two pictures here and I’ve made them artificially symmetrical. And if I ask you which of these you find more beautiful, you’re probably drawn to the lower two. Because it is hard to make symmetry. And if you can make yourself symmetrical, you’re sending out a sign that you’ve got good genes, you’ve got a good upbringing and therefore you’ll make a good mate. So symmetry is a language which can help to communicate genetic information.

Symmetry can also help us to explain what’s happening in the Large Hadron Collider in CERN. Or what’s not happening in the Large Hadron Collider in CERN. To be able to make predictions about the fundamental particles we might see there, it seems that they are all facets of some strange symmetrical shape in a higher dimensional space.

And I think Galileo summed up, very nicely, the power of mathematics to understand the scientific world around us. He wrote, “The universe cannot be read until we have learnt the language and become familiar with the characters in which it is written. It is written in mathematical language, and the letters are triangles, circles and other geometric figures, without which means it is humanly impossible to comprehend a single word.“

But it’s not just scientists who are interested in symmetry. Artists too love to play around with symmetry. They also have a slightly more ambiguous relationship with it. Here is Thomas Mann talking about symmetry in “The Magic Mountain.” He has a character describing the snowflake, and he says he “shuddered at its perfect precision, found it deathly, the very marrow of death.”

But what artists like to do is to set up expectations of symmetry and then break them. And a beautiful example of this I found, actually, when I visited a colleague of mine in Japan, Professor Kurokawa. And he took me up to the temples in Nikko. And just after this photo was taken we walked up the stairs. And the gateway you see behind has eight columns, with beautiful symmetrical designs on them. Seven of them are exactly the same, and the eighth one is turned upside down.

And I said to Professor Kurokawa, “Wow, the architects must have really been kicking themselves when they realized that they’d made a mistake and put this one upside down.” And he said, “No, no, no. It was a very deliberate act.” And he referred me to this lovely quote from the Japanese “Essays in Idleness” from the 14th century, in which the essayist wrote, “In everything, uniformity is undesirable. Leaving something incomplete makes it interesting, and gives one the feeling that there is room for growth.” Even when building the Imperial Palace, they always leave one place unfinished.

But if I had to choose one building in the world to be cast out on a desert island, to live the rest of my life, being an addict of symmetry, I would probably choose the Alhambra in Granada. This is a palace celebrating symmetry. Recently I took my family – we do these rather kind of nerdy mathematical trips, which my family love. This is my son Tamer. You can see he’s really enjoying our mathematical trip to the Alhambra. But I wanted to try and enrich him. I think one of the problems about school mathematics is it doesn’t look at how mathematics is embedded in the world we live in. So, I wanted to open his eyes up to how much symmetry is running through the Alhambra.

You see it already. Immediately you go in, the reflective symmetry in the water. But it’s on the walls where all the exciting things are happening. The Moorish artists were denied the possibility to draw things with souls. So they explored a more geometric art. And so what is symmetry? The Alhambra somehow asks all of these questions. What is symmetry? When [there] are two of these walls, do they have the same symmetries? Can we say whether they discovered all of the symmetries in the Alhambra?

And it was Galois who produced a language to be able to answer some of these questions. For Galois, symmetry – unlike for Thomas Mann, which was something still and deathly – for Galois, symmetry was all about motion. What can you do to a symmetrical object, move it in some way, so it looks the same as before you moved it? I like to describe it as the magic trick moves. What can you do to something? You close your eyes. I do something, put it back down again. It looks like it did before it started.

So, for example, the walls in the Alhambra – I can take all of these tiles, and fix them at the yellow place, rotate them by 90 degrees, put them all back down again and they fit perfectly down there. And if you open your eyes again, you wouldn’t know that they’d moved. But it’s the motion that really characterizes the symmetry inside the Alhambra. But it’s also about producing a language to describe this. And the power of mathematics is often to change one thing into another, to change geometry into language.

So I’m going to take you through, perhaps push you a little bit mathematically – so brace yourselves – push you a little bit to understand how this language works, which enables us to capture what is symmetry. So, let’s take these two symmetrical objects here. Let’s take the twisted six-pointed starfish. What can I do to the starfish which makes it look the same? Well, there I rotated it by a sixth of a turn, and still it looks like it did before I started. I could rotate it by a third of a turn, or a half a turn, or put it back down on its image, or two thirds of a turn. And a fifth symmetry, I can rotate it by five sixths of a turn. And those are things that I can do to the symmetrical object that make it look like it did before I started.

Now, for Galois, there was actually a sixth symmetry. Can anybody think what else I could do to this which would leave it like I did before I started? I can’t flip it because I’ve put a little twist on it, haven’t I? It’s got no reflective symmetry. But what I could do is just leave it where it is, pick it up, and put it down again. And for Galois this was like the zeroth symmetry. Actually, the invention of the number zero was a very modern concept, seventh century A.D., by the Indians. It seems mad to talk about nothing. And this is the same idea. This is a symmetrical – so everything has symmetry, where you just leave it where it is.

So, this object has six symmetries. And what about the triangle? Well, I can rotate by a third of a turn clockwise or a third of a turn anticlockwise. But now this has some reflectional symmetry. I can reflect it in the line through X, or the line through Y, or the line through Z. Five symmetries and then of course the zeroth symmetry where I just pick it up and leave it where it is. So both of these objects have six symmetries. Now, I’m a great believer that mathematics is not a spectator sport, and you have to do some mathematics in order to really understand it.

So here is a little question for you. And I’m going to give a prize at the end of my talk for the person who gets closest to the answer. The Rubik’s Cube. How many symmetries does a Rubik’s Cube have? How many things can I do to this object and put it down so it still looks like a cube? Okay? So I want you to think about that problem as we go on, and count how many symmetries there are. And there will be a prize for the person who gets closest at the end.

But let’s go back down to symmetries that I got for these two objects. What Galois realized: it isn’t just the individual symmetries, but how they interact with each other which really characterizes the symmetry of an object. If I do one magic trick move followed by another, the combination is a third magic trick move. And here we see Galois starting to develop a language to see the substance of the things unseen, the sort of abstract idea of the symmetry underlying this physical object. For example, what if I turn the starfish by a sixth of a turn, and then a third of a turn?

So I’ve given names. The capital letters, A, B, C, D, E, F, are the names for the rotations. B, for example, rotates the little yellow dot to the B on the starfish. And so on. So what if I do B, which is a sixth of a turn, followed by C, which is a third of a turn? Well let’s do that. A sixth of a turn, followed by a third of a turn, the combined effect is as if I had just rotated it by half a turn in one go. So the little table here records how the algebra of these symmetries work. I do one followed by another, the answer is it’s rotation D, half a turn. What I if I did it in the other order? Would it make any difference? Let’s see. Let’s do the third of the turn first, and then the sixth of a turn. Of course, it doesn’t make any difference. It still ends up at half a turn.

And there is some symmetry here in the way the symmetries interact with each other. But this is completely different to the symmetries of the triangle. Let’s see what happens if we do two symmetries with the triangle, one after the other. Let’s do a rotation by a third of a turn anticlockwise, and reflect in the line through X. Well, the combined effect is as if I had just done the reflection in the line through Z to start with. Now, let’s do it in a different order. Let’s do the reflection in X first, followed by the rotation by a third of a turn anticlockwise. The combined effect, the triangle ends up somewhere completely different. It’s as if it was reflected in the line through Y.

Now it matters what order you do the operations in. And this enables us to distinguish why the symmetries of these objects – they both have six symmetries. So why shouldn’t we say they have the same symmetries? But the way the symmetries interact enable us – we’ve now got a language to distinguish why these symmetries are fundamentally different. And you can try this when you go down to the pub, later on. Take a beer mat and rotate it by a quarter of a turn, then flip it. And then do it in the other order, and the picture will be facing in the opposite direction.

Now, Galois produced some laws for how these tables – how symmetries interact. It’s almost like little Sudoku tables. You don’t see any symmetry twice in any row or column. And, using those rules, he was able to say that there are in fact only two objects with six symmetries. And they’ll be the same as the symmetries of the triangle, or the symmetries of the six-pointed starfish. I think this is an amazing development. It’s almost like the concept of number being developed for symmetry. In the front here, I’ve got one, two, three people sitting on one, two, three chairs. The people and the chairs are very different, but the number, the abstract idea of the number, is the same.

And we can see this now: we go back to the walls in the Alhambra. Here are two very different walls, very different geometric pictures. But, using the language of Galois, we can understand that the underlying abstract symmetries of these things are actually the same. For example, let’s take this beautiful wall with the triangles with a little twist on them. You can rotate them by a sixth of a turn if you ignore the colors. We’re not matching up the colors. But the shapes match up if I rotate by a sixth of a turn around the point where all the triangles meet. What about the center of a triangle? I can rotate by a third of a turn around the center of the triangle, and everything matches up. And then there is an interesting place halfway along an edge, where I can rotate by 180 degrees. And all the tiles match up again. So rotate along halfway along the edge, and they all match up.

Now, let’s move to the very different-looking wall in the Alhambra. And we find the same symmetries here, and the same interaction. So, there was a sixth of a turn. A third of a turn where the Z pieces meet. And the half a turn is halfway between the six pointed stars. And although these walls look very different, Galois has produced a language to say that in fact the symmetries underlying these are exactly the same. And it’s a symmetry we call 6-3-2.

Here is another example in the Alhambra. This is a wall, a ceiling, and a floor. They all look very different. But this language allows us to say that they are representations of the same symmetrical abstract object, which we call 4-4-2. Nothing to do with football, but because of the fact that there are two places where you can rotate by a quarter of a turn, and one by half a turn.

Now, this power of the language is even more, because Galois can say, “Did the Moorish artists discover all of the possible symmetries on the walls in the Alhambra?” And it turns out they almost did. You can prove, using Galois’ language, there are actually only 17 different symmetries that you can do in the walls in the Alhambra. And they, if you try to produce a different wall with this 18th one, it will have to have the same symmetries as one of these 17.

But these are things that we can see. And the power of Galois’ mathematical language is it also allows us to create symmetrical objects in the unseen world, beyond the two-dimensional, three-dimensional, all the way through to the four- or five- or infinite-dimensional space. And that’s where I work. I create mathematical objects, symmetrical objects, using Galois’ language, in very high dimensional spaces. So I think it’s a great example of things unseen, which the power of mathematical language allows you to create.

So, like Galois, I stayed up all last night creating a new mathematical symmetrical object for you, and I’ve got a picture of it here. Well, unfortunately it isn’t really a picture. If I could have my board at the side here, great, excellent. Here we are. Unfortunately, I can’t show you a picture of this symmetrical object. But here is the language which describes how the symmetries interact.

Now, this new symmetrical object does not have a name yet. Now, people like getting their names on things, on craters on the moon or new species of animals. So I’m going to give you the chance to get your name on a new symmetrical object which hasn’t been named before. And this thing – species die away, and moons kind of get hit by meteors and explode – but this mathematical object will live forever. It will make you immortal. In order to win this symmetrical object, what you have to do is to answer the question I asked you at the beginning. How many symmetries does a Rubik’s Cube have?

Okay, I’m going to sort you out. Rather than you all shouting out, I want you to count how many digits there are in that number. Okay? If you’ve got it as a factorial, you’ve got to expand the factorials. Okay, now if you want to play, I want you to stand up, okay? If you think you’ve got an estimate for how many digits, right – we’ve already got one competitor here. If you all stay down he wins it automatically. Okay. Excellent. So we’ve got four here, five, six. Great. Excellent. That should get us going. All right.

Anybody with five or less digits, you’ve got to sit down, because you’ve underestimated. Five or less digits. So, if you’re in the tens of thousands you’ve got to sit down. 60 digits or more, you’ve got to sit down. You’ve overestimated. 20 digits or less, sit down. How many digits are there in your number? Two? So you should have sat down earlier. (Laughter) Let’s have the other ones, who sat down during the 20, up again. Okay? If I told you 20 or less, stand up. Because this one. I think there were a few here. The people who just last sat down.

Okay, how many digits do you have in your number? (Laughs) 21. Okay good. How many do you have in yours? 18. So it goes to this lady here. 21 is the closest. It actually has – the number of symmetries in the Rubik’s cube has 25 digits. So now I need to name this object. So, what is your name? I need your surname. Symmetrical objects generally – spell it for me. G-H-E-Z No, SO2 has already been used, actually, in the mathematical language. So you can’t have that one. So Ghez, there we go. That’s your new symmetrical object. You are now immortal. (Applause)

And if you’d like your own symmetrical object, I have a project raising money for a charity in Guatemala, where I will stay up all night and devise an object for you, for a donation to this charity to help kids get into education in Guatemala. And I think what drives me, as a mathematician, are those things which are not seen, the things that we haven’t discovered. It’s all the unanswered questions which make mathematics a living subject. And I will always come back to this quote from the Japanese “Essays in Idleness”: “In everything, uniformity is undesirable. Leaving something incomplete makes it interesting, and gives one the feeling that there is room for growth.” Thank you. (Applause)

2020-10-25

Galois theory

Go to the roots of these calculations! Group the operations. Classify them according to their complexities rather than their appearances! This, I believe, is the mission of future mathematicians. This is the road on which I am embarking in this work.

Ne pleure pas, Alfred ! J’ai besoin de tout mon courage pour mourir à vingt ans ! (Don’t cry, Alfred! I need all my courage to die at twenty!) - Évariste Galois(1811 – 1832)

No episode in the history of thought is more moving than the life of Evariste Galois — the young Frenchman who passed like a meteor about 1828, devoted a few feverish years to the most intense meditation, and died in 1832 from a wound received in a duel, at the age of twenty. He was still a mere boy, yet within these short years he had accomplished enough to prove indubitably that he was one of the greatest mathematicians of all time. When one sees how terribly fast this ardent soul, this wretched
and tormented heart, were consumed, one can but think of the beautiful meteoric showers of a summer night. But this comparison is misleading, for the soul of Galois will burn on throughout the ages and be a perpetual flame of inspiration. His fame is incorruptible; indeed the apotheosis will become more and more splendid with the gradual increase of human knowledge. (George Sarton)

The Paris circles with their intensive mathematical enterprise, produced around 1830 with Evariste Galois a genius of the highest quality, who, like a comet, vanished just as fast as he had appeared. (Dirk Jan Struik)

In many ways, Galois is to be regarded as the father of modern algebra.

Several hundred years passed without anyone finding a radical formula for the roots of a general quintic polynomial. There was a good reason for this. There is no such formula. Nor is there a formula for polynomials of degree greater than 5. This fact was first established in the early nineteenth century by Abel(who died aged twenty-six), after which Galois(who died aged twenty-one) built an entirely new theory of equations that not only explained the nonexistence of formulas but laid the foundations for a whole edifice of algebra and number theory known as Galois theory, a major area of modern-day research. (The Princeton Companion to Mathematics - Part V Theorems and Problems, V.21 The Insolubility of the Quintic, by Martin W. Liebeck)

The great Austrian mathematician Emil Artin wrote about Galois, “Since my mathematical youth, I have been under the spell of the classical theory of Galois. This charm has forced me to return to it again and again.”

Galois’s invention of groups was a stroke of genius. After all, the great mathematician Abel, who worked on the problem of solvability by radicals at the same time, did not come up with group theory. Indeed, only Cauchy, on his return to France in the 1840s, seemed to appreciate Galois’s achievement, and Cauchy’s intense group theoretical studies led to the use of group theory in other fields of mathematics. (Joseph Rotman, the University of Illinois)

Galois wrote three letters the night before he was entangled in the game of Russian roulette that led to his death. One of these had further details of the brilliant mathematical theory he had developed. Mathematician Hermann Weyl said of this testament, “This letter, if judged by the novelty and profundity of ideas it contains, is perhaps the most substantial piece of writing in the whole literature of mankind.” After his tragic death, his brother passed his papers to a leading French mathematician, Joseph Liouville, who edited Galois’s collected works for publication in 1846. Only then did his extraordinary brilliance become apparent to the mathematical world.

The main object of Évariste Galois’s investigations is the conditions of solvability of equations by radicals. The author constructs the fundamentals of a general theory which he applies in detail to any equation whose power is a prime number. ・・・ my diligence was rewarded and I felt extraordinary content at the moment when, having made some minor corrections, was convinced in the validity of the method Galois used to prove this beautiful theorem. (Joseph Liouville)

But Liouville’s article was still too far-fetched for other mathematicians to enjoy and understand. It took another 24 years to find a French mathematician outstanding enough to better understand Galois and make his ideas limpid. This outstanding mathematician is Camille Jordan. In fact, Jordan’s 1870 book on Galois theory was so well-written that German mathematician Felix Klein found it as readable as a German book!

It would take another 82 years for the great Austrian mathematician Emil Artin to finally give the Galois theory its modern form.

Instead of using infinite groups, Galois began with a particular equation and constructed his group from a handful of solutions to the equation. It was groups from the solutions to quintic equations which allowed Galois to derive his results about these equations. A century and a half later, Wiles would use Galois’s work as the foundation for his proof of the Taniyama—Shimura conjecture. (Fermat’s Last Theorem, Simon Singh)

There is a general principle, which is very fruitful in mathematics that if you want to learn something about a mathematical object, investigate its automorphism group (Symmetry, Hermann Weyl)

Galois theory paved the way for modern algebraic thinking.

Galois theory is a very difficult topic usually only introduced in the final year of an undergraduate mathematics degree.

Felix Klein: There is a contradiction here that should be deplored by both students and teachers. On the one hand, instructors are eager to teach Galois theory because of the brilliance of its discovery and the far-reaching nature of its results; on the other hand, this subject presents immense difficulties to the average beginner’s understanding. In most cases the sad result is that the instructors’ inspired and enthusiastic efforts make no impression on most of the audience, awaken no understanding. The particular difficulty of the task which Galois theory presents to the expositor must bear its share of the blame for this result.

Galois theory is a very big subject, and until you are quite immersed in mathematical study in a way which is unusual unless studying for a degree in maths, it can seem quite pointless.

To understand Galois theory, you have to be comfortable with vector spaces and finite group theory. If you are not comfortable with those concepts, you should learn those first. Do not attempt to study Galois theory or any mathematical subject before you’ve mastered the prerequisites. It’s pointless, frustrating, and damaging.

Before embarking on the study of Galois theory, you will need to have mastered basic linear algebra really well, up to and including linear algebra over arbitrary fields, the idea of dimension, linear transformations, kernels, images, subspaces, bases and linear independence.

A better preparation includes knowing about groups, homomorphisms, the isomorphism theorems, permutations and parity, cyclic groups, abelian groups and ideally solvable groups. A good first course in group theory will make it a lot easier for you.