Review: Love and Math by Edward Frenkel

I have a friend who thinks she does not understand maths (apologies to the American readers, I will use “maths” in this review rather than the “math” in the book title). She thinks maths is “all about numbers”. She thinks she’s not particularly good at it. She is wrong. Actually, I think she is remarkably gifted, primarily because she asks amazingly prescient questions. She has an inquisitive nature that I fear is often drilled out of most people by our “rigorous” schooling in the tedium of official school maths.

Over the past few months, I have spent quite a bit of time discussing maths with this friend, introducing her to set theory and trying to overcome a fear of algebra. (It is remarkable how many super bright people can reason about insanely complex general phenomena in their head without algebra in a way I never could, yet stumble over a simple equation!)

I saw this book reviewed elsewhere – I can’t quite remember where. It was a short but positive review, and the title is attractive to me, given my recent discussions. The author, Edward Frenkel, is a professor of mathematics at UC Berkeley, has made considerable contributions to mathematics himself, and also has a direct personal knowledge of many of the larger-than-life characters he talks about in the book. I knew nothing about his work, or his life, both of which turn out to be rather interesting, before reading this book.

The book is part autobiography and part introduction to the joy of mathematics. We learn about the author’s early career, the anti-Semitism he faced in Russia and his conversion as a teen from physics to mathematics, before the two come back together through quantum physics later in his career. We learn about his immersion in the Langlands Program.

As a book about “doing mathematics”, I think he does quite well at getting his feelings across. The detail of much of the mathematics is missing; sketches of subjects are given: Galois Groups, the Shimura-Taniyama-Weil Conjecture, Lie groups and Lie algebras, etc., but only very brief sketches. While this gives the reader insight into the depth of the subject areas covered by modern mathematics (and certainly helps to show the breadth of maths beyond school arithmetic) it doesn’t really show the reader mathematics. We read about proof, but we don’t experience proof. We read about revelation, but we don’t feel the revelation ourselves. We are told that mathematics rests on clear and unequivocal definitions, but these are absent from the book. Initially, this left me feeling unsatisfied. Slowly, I put aside my usual desire to understand everything I was reading, and began to enjoy the book as a novel, a love affair between the author and his subject, in which specific theorems appear only as partially sketched characters. From this perspective, the bulk of the book was very enjoyable, and provides insight not only into the beauty of mathematics, but also the ways in which mathematicians think. As an engineer, albeit one who has a lot of time for – and use for – pure mathematics, my way of thinking remains quite distinct from some of the methods and approaches outlined in this book. However, late in the book, where the author covers the links between this mathematics and quantum physics, I feel the unexplained mathematics again gets in the way. The author seems to acknowledge this, when he says (p.221), “All this stuff, as my dad put it, is quite heavy: we’ve got Hitchin moduli spaces, mirror symmetry, A-branes, B-branes, automorphic sheaves […] But my point is not for you to learn them all…”

The final chapter of the book takes a violent switch in direction as we learn of Frenkel’s artistic projects, in particular his film Rites of Love and Math. Had I known about this work beforehand, the book would have made a lot more sense! In this chapter, Frenkel provides his philosophical opinions on the nature of the material world, the world of our consciousness, and – in his view – the entirely separate Platonic world of mathematics. He says his approach to making the film was “let the viewers first feel rather than understand” – much the same could be said of this book.

The experience of reading this book has got me thinking in two directions.

Firstly, this is not the book I initially expected from the first few chapters. But how easy would it be to write a book which both conveys the joy of solving problems, say in Lie algebras, which Frenkel explores in some depth, and at the same time covers enough mathematics for a reasonably rigorous approach to the problem for a general reader? Perhaps such a task is impossible, and I ask too much. Does this mean that the beauty of modern mathematics is necessarily harder to access than than the beauty of modern art? Does this mean that we must necessarily pay the price of “boring maths” in order to be able to access “beautiful maths”? Or is there actually no “boring maths” and the prerequisite knowledge can also be described in a way that appeals and excites, even if not in one volume. I hope for the latter.

Secondly, the book has made me realise that I am far less certain of my own philosophical viewpoint on reality, Platonism, and knowledge than I used to be. It has made me want to explore these issues again and read more. Perhaps I will start with Penrose.

Is this the book I wanted for my friend? Probably not, but it’s certainly stimulated my thinking, and probably would also stimulate the thinking of others, regardless of their current level of mathematical maturity.

Math Circle Session 8: The Circle Game & Puzzles

Today was the 8th session of our math circle for primary school children. We only had four of the original six children today, for a variety of reasons, but it seemed to work well.

We first ran through a puzzle we set the kids to think about over the last week. The idea of the puzzle, taken from Martin Gardner’s book, is as follows. Take a piece of paper shown below. Imagine this is a map, that you have to fold up (I find folding up maps really hard!)

You have to fold only along the lines shown, and must form a folded “map” with the 1 on top, facing up. The next number down after the 1 must be the 2, after the 2 must be the 3, and so on until the 8 lies on the bottom.

Some kids had tried this at home, some had not (as a policy, we never make “homework” compulsory) but none had found the solution, so we covered this today.

We then moved onto the main part of the session, “The Circle Game”, adapted from Rozhkovskaya’s book. The kids were each given a worksheet consisting of 16 points equally spaced around a circle, and asked to play a game in pairs. The rules of the game are as follows:

take it in turns
on each turn, connect one point to another point with a straight line; any pair of points can be chosen, but no line drawn can cross another line already drawn

The last player to be able to draw a line is the winner.

The kids enthusiastically played this game, trying to outsmart each other. However, at the end of play, we had three games in which the first player to move had always won (though the points selected were different). I also asked the kids to count the number of moves made, which was found to be 29 in each game. The question was posed: “why does the first player always win?”

One child quickly pointed out that if the number of moves is an odd number, it must always be the first player who wins. Another child suggested that we should try 17 points around the circle as then “it would be an even number of moves and Player 2 would win”. I suggested that instead of making the game more complicated, we simplify it to the smallest possible number of points on the circle, which the children identified as two points.

Children very quickly found that two points would always result in one move, three points in three moves, and four points in five moves. At this point the child who suggested that 17 points would result in a win for Player 2 withdrew his opinion, and all children were convinced that the number of moves would always be odd and therefore Player 1 would always win.

We then looked at generalising the number of moves required for $n$ points. Children very quickly noticed that the number of moves increased by two for each new point added. Due to the significant difference in ages in the group, I wasn’t sure how comfortable children would be with an algebraic generalisation of the result, but it turns out that even the youngest was comfortable with the formula $moves = 2 \times points - 3$ , which they got to via my suggestion that if the numbers were going up by two each time, try looking at the relationship between $moves$ and $2 \times points$ .

I was surprised by how quickly we had reached this point in the session, so I rounded off the exploration by demonstrating an inductive proof of this formula in graphical form on the whiteboard (see, for example, Theorem 1.8 at http://press.princeton.edu/chapters/s9489.pdf).

One child was keen to play this game with his dad, and it was suggested that the “youngest goes first” rule should be applied, possibly after agreeing a prize for winning!

With the remaining spare time for the session, we set the following puzzle – also from Gardner’s book – to begin during the session and to continue to think about over the week. Consider the grid below.

The puzzle is to fill each empty cell with a single digit, so that the bottom row forms a number between $0$ and $10^{10}-1$ . The challenge is that the digit under the heading zero must equal the total number of zero digits in this number, the digit under the 1 must equal the total number of 1 digits in this number, and so on. I thought it might be hard for the kids to understand the puzzle, but actually they understood it quite easily. They were amazed when I told them that the answer is unique: there is only one of the 10 billion possible numbers that works! It was interesting to observe the different reactions to this: some kids decided they’d never be able to find the solution, and therefore decided not to put much effort into the task. Others decided this was a challenge, and kept plugging away. One child was determined to take it home so that his dad would help.

Overall, I think this session went very well.

Update: I received an email tonight from the school headteacher with the solution to this number puzzle. I love that he’s so into it!

Math Circle Session 7: Combinatorics, Pascal’s Triangle, and the Sierpinski Triangle Again

Today saw Session 7 of our math circle. No blog on Session 6, as I was away for work – my wife explored The Towers of Hanoi in my absence.

Today’s session was based on a combination of two sessions in Rozhkovskaya’s book. The idea is as follows. Imagine a maze at a tourist attraction. The maze is such that there is one entrance, but seven exits labelled 0 to 6. Imagine that you are standing facing north at the entrance. At this entrance, and at each intersection, you can move ahead-left on a bearing of 315 degrees by one unit or ahead-right on a bearing of 45 degrees by one unit until you meet the next intersection or exit. Thus the maze decomposes into 7 levels (including the entrance and exits). Now further imagine that you must roll a die at each decision point, taking the left route if you roll even and the right route if you roll odd.

The first question: If I were an ice-cream vendor, where should I place my van to capture most people coming out? Children had an intuitive feeling that most people would come out in the middle. Only one child (the oldest) offered a reasoned explanation for this: “we expect as many odd throws as even throws, which means the most likely exit would be the middle one”.

We got the children to experiment by rolling routes through the maze, and collected a tally of how many trials ended up at each exit, confirming this suspicion. Children naturally noticed that exits zero and seven were unlikely, as they would require rolling “all odd” or “all even”.

This naturally led onto the next part of the exercise, to annotate each decision point with the number of ways in which it could be reached. Children found this hard, and made many mistakes, because they were trying to count all the ways to reach a given decision point from the maze entrance from scratch for each decision point. I explained that there are only at most two ways to reach any decision point, so it is sufficient to sum the possibilities found to these two preceding points.

Thus, Pascal’s triangle was revealed. We asked the kids to sum the rows of Pascal’s triangle, and they discovered they summed to successive powers of two.

Finally, we had the kids colour all the even numbers in a large version of Pascal’s triangle (pre-printed). One of the kids immediately recognised a fractal-like shape. Once complete, we pointed out the resemblance to Sierpinski’s triangle, created in Session 7. Oddly (to me) this wasn’t immediately apparent, even to the kids who were there.

Overall, I was a little disappointed with today’s session. I think the material was good, but it was a sunny day, and two of the kids showed no sign of wanting to be there, inside after school. This meant I had to spend a lot more time than I ever imagined trying to get these kids on task, meaning a lot less time to discuss the mathematics of what we were seeing, which was a shame. My one rule for Math Circle was that the kids should want to be there and, for whatever reason, I don’t think this was true for 1/3 of them this time. I hope it’s a temporary blip, but I need to ask for views from primary school teachers; I was again reminded today how different kids are to the adults I’m used to!

Coherence When You Need It

This week, my PhD student Felix Winterstein presented our work (joint with Intel and MIT) on how to customise memory systems to support parallel applications, at the FPGA 2015 conference.

If you are working with FPGAs, you have a huge freedom to develop an arbitrary on-chip memory system to support your application. Tools are getting quite good at developing such systems for regular array based code. But pointer manipulating programs that build, operate on, and destroy memory structures on the fly will not pass through commercial HLS tools, let alone produce good quality results.

We’ve shown that this issue can be addressed using a tool we’ve developed based on the theoretical foundation of Separation Logic. The tool automatically figures out when functional units can have private on-chip caches, which functional units need shared coherent caches, and – in the latter case – when commands can be reordered to aid parallelisation. It uses this analysis to automatically produce C source code that will pass through commercial HLS tools, providing the necessary hints and pragmas to parallelise the code, and automatically generates the on chip caches to support the parallel datapath.

I’m really very excited about this work, I view it as a big step towards efficient automatic hardware implementation of full-featured C code.

Math Circle Session 5: Powers, Limits, and Fractals

Yesterday saw the next installment of our math circle with primary school children. Again, following but extending Rozhkovskaya’s book, we used fractals as an interesting way in to consolidate (and in the case of the younger pupils, introduce) powers of numbers, to explore the children’s intuition about infinite series, and to make some pretty pictures!

We started by producing a fractal tree. The rule is simple: after Year 1, the trunk has grown. At the end of Year 2, two branches have grown from that, after Year 3, two further branches from each existing branch, and so on. Children were quickly able to tell us that the number of branches doubled each year, some took great pleasure in calculating or reciting powers of two. The template for this exercise was taken from Rozhkovskaya’s book, and is quite clever: lines are drawn across the page heights of 8 squares, 12 squares, 14 squares, 15 squares, and 15.5 squares, and each successive year’s branches should be drawn to reach the corresponding height. A bird is drawn flying around 18 squares up. The question is posed: will the tree ever reach the bird?

The children had mixed views on whether the tree will reach the bird. The most common view was that it must. One of the older children was able to provide a line of reasoning: “Each time, the height of the tree increases. Since it is always increasing, even by small amounts, it must eventually reach any height.” We then looked at how much gap there is between the height of the tree and a line of height 16 as the years progress: 16 at the beginning, 8 at the end of Year 1, 4 at the end of Year 2, and so on. Children could see that there was always a positive gap between the height of the tree and the height 16, for any finite number of years. However, this clashed with several children’s intuition, and it took quite a lot of discussion before it was generally accepted that an infinite series can sum to a finite limit. One of the youngest children in the group asked some very probing questions, such as “is infinity a number”, which led to some useful side discussions. Random banter between children later in the session about “hacking” their siblings’ passwords led onto a consolidation of this discussion by asking the question “If you had to press an infinite number of keys on a keyboard, could you do it in a finite amount of time? No? What if the first key took 8 seconds to press, the next 4, the next 2, and so on…”

We then moved onto a practical activity of constructing a sequence of approximations to the Sierpinski triangle by sticking little white triangles on coloured paper (pictured). One of the children noticed quickly, and was able to clearly explain, that the number of white triangles was increasing in powers of three. At this point we ran out of time, and our session ended. I intend to pick up and use the Sierpinski triangle again soon in math circle, through Pascal’s triangle modulo 2.

Math Circle Session 4: Ciphers

Today saw the fourth session of our math circle. Attendance was down, and there was a sombre mood, due to a tragic event to hit the the school community today.

We went ahead with the three children who came, looking at ciphers. Following the guidance and resources in Rozhkovskaya’s book, we looked at the following activities:

We started with some plaintext words and one ciphertext word, and the kids very quickly spotted, without any help, which plaintext word corresponded to the ciphertext word, on the basis that both had a double letter in a certain place and they had the same number of symbols.
We showed how a coding wheel can be used to produce a Caesar shift cipher, and got them to actually build such a wheel.
We queried how many possible ciphers could be constructed with such a wheel. Interestingly, this was not obvious to the children at first, and a common answer was “infinite”. On questioning, this is because they were considering all integer shifts, i.e. mapping the letter $n$ to the letter $n+k$ for some key $k$ , and forgetting the modulo arithmetic in play, despite having the wheel in front of them.
We got them to produce coded messages to each other using the wheel, which they seemed to enjoy. Our initial plan was to have them pass the message and the key to the next child to decode. However, they immediately attempted to decode without they key by looking for patterns, so we didn’t stop this. One key pattern they spotted included the limited number of two letter words in English, allowing them to enumerate possible keys on two-letter words in the ciphertext. Another was the limited number of letters in the alphabet that can appear twice consecutively in an English word, again allowing for enumeration.

There’s a lot more that can be done with ciphers, and I expect we’ll continue this for another session.

Review: Three Views of Logic: Mathematics, Philosophy, and Computer Science

I read this book largely by accident, because I was attracted by the title. As an academic in (or rather, on the edge of) computer science, I come across logic regularly, both in teaching and research. Mathematics underpins almost everything I do, and I’m certainly interested in whether a mathematician’s view of logic differs significantly from that of a theoretical computer scientist (as a keen reader of mathematics, I’m well aware that standard mathematical practice of proof differs quite strongly from the formal approach studied in computer science, but this isn’t quite the same thing!) I once had a strong interest in philosophy, most significantly in epistemology, which is being rekindled by my involvement in education at the school level, and so combining all these factors, the title was very appealing. What I actually discovered when I started reading wasn’t exactly what I expected. But this book turns out to be an excellent, crystal clear, textbook suitable for undergraduates and those with just a limited level of mathematical maturity. The book is explicitly partitioned into three sections, but in practice I found that the first two sections, proof theory and computability theory (the “maths” and the “computer science”) were very familiar material for any computer scientist, and from my perspective there was no very clear difference in approach taken, just a difference in the range of topics covered.

Part 1, by Loveland, covers propositional and predicate logic, with a particular focus on automated proof by resolution. I found the description of resolution to be very clear, with a particular focus on the difference between resolution for propositional and predicate logic, and with one of the clearest descriptions of completeness results I’ve seen.

Part 2, by Hodel, covers computability theory. Again, the clarity is exemplary. The first chapter discusses concepts informally, the second precisely defines two machine models in a way very accessible to a computer engineer (effectively one supporting general recursion and one supporting only primitive recursion) and discusses their relative computational power. The insistence of an informal discussion first makes these distinctions come to life, and allows Hodel to frame the discussion around the Church-Turing thesis. The focus on compositionality when preserving partial recursiveness, and the emphasis on the ‘minimalisation’ operator (bounded and unbounded) was new to me, and again very clearly presented. Most introductory texts I’ve read only tend to hint at the link between Gödel’s Incompleteness Theorem and Church’s Undecidability Theorem, whereas Hodel makes this link precise and explicit in Section 6.6, Computability and the Incompleteness Theorem.

Part 3, by Sterrett, covers philosophical logic. In particular, Sterrett considers the existence of alternatives to (rather than extensions of) classical logics. She focuses on the logic of entailment aka relevance logic introduced by Anderson and Belnap, into which she goes into depth. This logic comes from rethinking the meaning ascribed to the connective, $\rightarrow$ , logical implication. In classical logic, this is a most confusing connective (or at least was to my students when I taught an introductory undergraduate course in the subject long ago). I would give my students examples of true statements such as “George is the Pope” implies “George is Hindu” to emphasise the difference between the material implication of classical logic and our everyday use of the word. It is exactly this discrepancy addressed by Anderson and Belnap’s logic. I was least familiar with the content of this part of the book, therefore the initial sections came as something of a surprise, as I found them rather drawn out and repetitive for my taste, certainly compared to the crisp presentation in Parts 1 and 2. However, things got exciting and much more fast moving by Chapter 8, Natural Deduction, where there are clear philosophical arguments to be had on both sides. In general, I found the discussion very interesting. Clearly a major issue with the line of reasoning given by my Pope/Hindu example above is that of relevance. Relevance might be a slippery notion to formalise, but it is done so here in a conceptually simple way: “in order to derive an implication, there must be a proof of the consequent in which the antecedent was actually used to prove the consequent.” Actually making this work in practice requires a significant amount of baggage, based on tagging wffs with relevance indices, which get propagated through the rules of deduction, recalling to my mind, my limited reading on the Curry-Howard correspondence. The book finishes with a semantics of Anderson and Belnap’s logic, based on four truth values rather than the two (true/false) of classical logic.

I can’t emphasise enough how easy this book is to read compared to most I’ve read on the subject. For example, I read all of Part 1 on a single plane journey. I will be recommending this book to any of my research students who need a basic grounding in computability or logic.

Math Circle Session 3: Knots

Today saw the third session of the primary school math circle we’ve been running for kids in Year 2 to Year 6. (I was absent for Session 2, where my wife covered mathematical card tricks.)

Today we looked at knots, drawing inspiration from Rozhkovskaya’s book as well as Adams’ introduction to knot theory. In particular, we covered the following points:

(Medial) graph representations of knot projections, moving backward and forward between them (see http://en.wikipedia.org/wiki/Knots_and_graphs)
The importance of assigning an (under/over) decision to crossings
Getting the kids to think of their own ideas for what knot equivalence might mean (shape, size, rotation, deformation – of what type) etc.

The key innovation we used here, which I think really brought the session to life, was to get the kids actually physically making the knots using Wikkistix, wax-coated string which allowed them to make, break, and remake their knots.

The kids really ran with this, and made their own discoveries, in particular:

One child discovered that some knots corresponding to the graph $K_3$ could be manipulated to produce the unknot, some could not.
A child discovered that it is possible to produce two interconnected knots, forming a link. Another child came to the same conclusion from the graph representation.
Consider the graph with vertex set $\{v_1,\ldots,v_n\}$ and edge set $\{\{v_i,v_{i+1}\} | 1 \leq i \leq n-1\}\} \cup \{\{v_n,v_1\}\}$ (is there a name for these graphs?). One child completely independently found that for $n$ even, this corresponds to a link of two knots, whereas for $n$ odd, it corresponds to a single knot.

I certainly had a lot of fun this afternoon – I hope they did too!

Where High Performance Reconfigurable Computing Meets Embedded Systems

I have just returned from attending HiPEAC 2015 in Amsterdam. As part of the proceedings, I was asked by my long-time colleague Juergen Becker to participate in a panel debate on this topic.

Panels are always good fun, as they give one a chance to make fairly provocative statements that would be out of place in a peer review publication, so I took up the opportunity.

In my view, there are really two key areas where reconfigurable computing solutions provide an inherent advantage over most high performance computational alternatives:

In embedded systems, notions of correct or efficient behaviour are often defined at the application level. For example, in my work with my colleagues on control system design for aircraft, the most important notion of incorrect behaviour is would this control system cause the aircraft to fall out of the sky? An important metric of efficient behaviour might be how much fuel does the aircraft consume? These high level specifications, which incorporate the physical world (or models thereof) in its interaction with the computational process, allow a huge scope for novelty in computer architecture, and FPGAs are the ideal playground for this novelty.
In real time embedded systems, it is often important to know exactly how long a computation will take in advance. Designs implemented using FPGA technology often provides such guarantees – down to the cycle – where others fail. There is, however, potentially a tension between some high level design methodologies being proposed and the certainty of the timing of the resulting architecture.

Despite my best attempts to stir up controversy, there seemed to be very few dissenters to this view from other members of the panel, combined with a general feeling that the world is no longer one of “embedded” versus “general purpose” computing. If indeed we can draw such divisions, they are now between “embedded / local” and “datacentre / cloud”, though power and energy concerns dominate the design process in both places.

Starting a Math Circle

I’ve been intrigued for a couple of years by the idea of math circles. Over Christmas I finally plucked up the courage to start one at a local primary school with my wife, a maths teacher. The school was happy, and recruited six pupils from Year 2 to Year 6 to attend.

Armed with a number of publications from the American Mathematical Society’s Mathematical Circles Library, our first task was to find a suitable topic for Session 1. Our primary goal was to find a topic that was clearly not everyday school maths, preferably as far away from the National Curriculum as possible, and ideally including practical activities.

In the end, we decided to look at Möbius strips. In the traditional of journal keeping for Mathematical Circles, I thought I would report the experience here in case anyone else wants to give it a go. In particular, we took the following approach:

Make zero half-turn bands (loops) and colour the outside in one colour. Then colour the inside in a different colour.
Repeat with a one half-turn band. This caused some surprise when it became apparent that one colour coloured the whole band.
Predict what would happen if you cut the zero half-turn band down the centre (prediction was universally that you’d get two zero half-turn bands). Try it.
Now predict for the one half-turn band. Children were less sure about this case, but the most popular prediction was two half-turn bands. More surprise when it turned out to create a single four half-turn band. One child then went off on his own exploring what happened when you cut one of these four half-turn bands (two four half-turn bands).

By this time some of children were already off under their own steam, trying out their own experiments. This was great, but even with only six children and with two adults, I found it hard to pull together the outcomes of these experiments in any systematic way in real time.

Eventually we discovered together that:

If the initial number of half-turns is odd, cutting gives you one larger band with more half turns. (I was hoping we’d be able to quantify this, but it turns out to be very difficult to count the number of half-turns in a strip – even for me, let alone for the younger children!)
If the initial number of half-turns is even, cutting gives you two interlinked bands with the same number of half-turns.

This took up pretty much the whole 50mins we had for Session 1, though I did briefly try to show them an explanation of why this might be the case, following the diagrammatic representation in this document from the University of Surrey. I probably didn’t leave enough time to do this properly, and they were anyway keen on cutting and exploring by that time, so with hindsight I probably should have just left them to it.

What delighted me was the child who wanted to take home his Möbius strip to show his dad. So, not a bad start to the Math Circle. Let’s see how we get on!