Math Circle Session 13: Infinity

Given the number of questions we’ve been asked by the children about infinity in recent weeks, I decided that today we’d have a session just on infinity.

I opened the session by asking the children whether they had any questions about infinity they’d like to try to answer in this session. I received the following suggestions:

Why does infinity have the symbol $\infty$ ?
What is infinity plus infinity?
Why do we sometimes say infinity is a number and sometimes not?
What are the rules for adding and subtracting with Aleph numbers? (From a child who had discussed infinite cardinals at home in the past.)

We began the session by one child answering the first question: “it represents going round and round and never stopping, which would also be a circle, but that’s zero.” I hoped the others would crop up during the discussion that followed.

We began by discussing prime numbers. All children had heard of primes, but only the older children could give a clear unambiguous definition. I had them list out some prime numbers, and asked how many there were. Opinion was divided: one child thought there would be an infinite number (after all, the session was on infinity!), while another child thought that this can’t be true “because most numbers are not prime, and there are infinite counting numbers, so there can’t be infinite primes too.” I then showed them Euclid’s proof that there are infinite primes.

Starting first with a hotel with a finite number of rooms, I then explained Hilbert’s Hotel. For blog readers, there is an excellent animation of these ideas on TED. This seemed to get them quite excited, which is what I was hoping to see! We covered one new arrival and an infinitely large coach of new arrivals, each time stopping to see whether they could contrive of a construction that would allow the new arrivals to fit in the full hotel. The child who had previously seen infinite cardinals suggested a solution to one new arrival, but nobody came up with a solution to the infinitely large coach of new arrivals. However, it was great to see the thought going into this (most children wanted to move each person from their room to one infinitely further down the corridor.)

At this point, there were two directions I had thought we might go, given enough time: one on an infinite number of infinitely large coaches using a prime construction, given our proof of Euclid’s Theorem, and the other to look at a diagonal argument proof of the uncountability of the continuum, as a route into the final question the children asked. However, given we only had five minutes left, I decided it was better to just let the children’s discussion free-range, since they were still talkative after the hotel story. A variety of discussion points emerged involving infinity, and I just let them talk to each other: is space infinite, how can space not be infinite, are there an infinite number of life-supporting planets out there, what happened “before” the big bang, etc.! It was great to see this discussion, even if we hadn’t manage to answer all the questions posed at the beginning.

Math Circle Sesion 12: Eulerian Circuits

Yesterday we turned our attention to Eulerian circuits in math circle. This was a completely “homebrew” session.

We started by asking the children to solve the classical puzzle of drawing this “house” without taking pen off paper, and without retracing your steps.

Surprisingly, they hadn’t seen it before, but it didn’t take long for them to solve, and also to discover that the path was not unique. We then asked whether it is possible to draw the same shape, following the same rules, but ending up at the end of the drawing back where you started. The children made many attempts at this. Nobody could find a way, but nobody suggested a reason why it wasn’t possible. One child noticed that if you remove the bottom most edge, the problem has a solution.

As a result, we began to enumerate all the connected graphs with one vertex, with two vertices, with three vertices, and with four vertices. For each graph, children quickly solved the problem where it had a solution. For small enough graphs, where there wasn’t a solution, they could see this through complete enumeration of paths.

One child suggested that there may be a link between the parity of the number of vertices in the graph, and whether or not an Eulerian circuit exists, but I demonstrated this to be false by reference to the two houses – the complete one and the one with the missing floor.

I suggested we look at the act of entering and exiting a vertex, using two edges each time. That, combined with drawing the order on each vertex of each of the graphs we’d enumerated, resulted in the conjecture from one of the kids that Eulerian circuits can only exist when all vertices have even order, and we together constructed an argument why this should be the case.

I then posed the (much harder) converse question: does an Eulerian circuit exist for every connected graph with even order vertices. I am not sure the children clearly understood the difference between this and the previous question; since they had shown that every graph with an Eulerian circuit has even order vertices, I think this seemed “obvious” to them (we must look at logic during one session – any reader with a child-friendly introduction to logic, please let me know!) I asked them to try to produce a graph with even order vertices that does not admit an Eulerian circuit, and they tried for some time before suggesting it is not possible, though none were clear why.

In a step towards trying to answer this question, I wanted to demonstrate that every graph with only even order vertices contains a circuit. I had them first try to construct graphs where each vertex has even order but the graph contains no circuit. Some elaborate failed attempts ensued, but then one child made the following remarkable claim: “it’s possible if the number of vertices is infinite”. I queried this child, and he drew the following “graph”:

His argument was that all these vertices have order two, yet the graph clearly contains no circuit. I thought this a fairly remarkable construction for a 7 or 8 year old! After restricting ourselves to finite graphs (infinity crops up so often, and absorbs so much interest, we should have a session on infinity also!) we all agreed that every graph with even order vertices contains a cycle.

From that point it was a small step to prove by induction that every graph with even order vertices admits and Eulerian circuit. I think they understood this, but I don’t think I had time to properly emphasise the inductive nature of the proof, and again proof by induction is something we must revisit in the future.

As a final exercise, I had them find an Eulerian circuit in what I had imagined to be a complex case: a pentagram inscribed inside a pentagon, with vertices at all points of intersection. They solved this easily, after which my infinity-inspired child noticed that there is a small pentagon formed by the pentagram, and asked what would happen if we put a pentagram inside this pentagon, and so ad infinitum, forming a fractal graph: would the property still hold?

Lots of things to pick up in future sessions, I think! If I were to change anything when redoing this session, it would be to make the problems more concrete, e.g. using towns as vertices and roads as edges, as my wife had suggested before the session! I think the children “got” it without this, but it might have captured the imagination slightly more.

An Interlude: Is Infinity Odd or Even?

During the session, when infinity came up, I was asked a direct question by one of the younger children: “is infinity odd or even?” At a lull in the main session, I decided we should use this question as a way to talk about the importance of definitions once more. All children had presupposed an arithmetic in which infinity plays the same role as any “other number”, and therefore already had in their minds that, for example, $2 \times \infty = \infty$ and $\infty + 1 = \infty$ . I didn’t question these suppositions (again – a possible topic for another session!) but instead decided to work with them. I asked for a definition of even, and got:

Definition: A number is even if it is two times a whole number.

I asked for a definition of odd, and got:

Definition: A whole number is odd if it is not even.

To which I added an additional alternative definition:

Definition: A whole number is odd if it is one more than an even number.

Children then quickly worked out for themselves that by their definition (and under their arithmetic) infinity is even. By the first definition of odd, infinity is not odd, but by the second definition, infinity is both odd and even! Thus the two definition of odd coincide for integers but not for their version of arithmetic with infinities. We left that as a talking and discussion point about the importance of definitions, rather than trying to draw any strong conclusions.

Run Fast! (When You Can): Data-Dependent Pipelining

This week sees the IEEE International Symposium on Field-Programmable Custom Computing Machines hosted in Vancouver, BC, Canada. I have sent my PhD student, Junyi Liu, who is presenting some work we’ve done together with my former research fellow, now a member of staff at Xilinx, Sam Bayliss.

Junyi and I are interested in memory accesses about which we know something at compile time, but not quite enough to be able to have a complete picture of what they’ll be at run time. This means that existing analyses of code containing these accesses will typically result in suboptimal behaviour at run time.

The case we study in this paper is that of affine loop nests containing memory accesses whose addresses involve indeterminate variables that do not change value as the loop executes. The value of these variables can completely change the dependence structure of the loop, meaning that for some values, the loop can be highly pipelined and run extremely fast whereas for other values, the loop must run very slowly. We give the trivial example below in the paper:


for( int i=LB; i<=UB; i++ )
  A[i] = A[i+m] + 1;

The variable m does not change as the loop executes. For some values of m, each iteration of the loop must start execution when the previous one finishes. For other values of m, we can pipeline the loop so that iterations overlap in time. So how to discover this and take advantage of it automatically?

We present an approach based on an extension of the polyhedral model to parametric polyhedra, where the parameters are these parameters, like m, unknown at compile time. My former PhD student Qiang Liu (no relation), colleague Kostas Masselos and I were some of the first people to bring the polyhedral model to FPGA-based computation in our FCCM 2007 paper (Qiang is now an associate professor at Tianjin University) but to the best of my knowledge, parametric polyhedra are relatively understudied in this area.

The basic idea of this new work is simple: use static analysis to identify regions of the parameter space where you can run the loop fast, and synthesise light-weight detectors of these regions for runtime checks on entry to the loop nest. Since my original work with the polyhedral model, high level synthesis has become a commercial reality, so we build on top of Xilinx VivadoHLS, implementing our tool as a source-to-source transformation engine. This automatically inserts the appropriate VivadoHLS pragmas as well as the extra code for the runtime checks.

The results are very promising: some of our benchmarks show a 10x speedup in initiation interval (the time you need to wait before executing another iteration of the loop).