In the next academic year I’ll be one of the lecturers for Topics in Discrete Mathematics at the University of Bristol. This comes in two flavours- the level H/6 unit MATH30002 for third-year students, and the level M/7 unit MATHM0009 for those in the fourth year (which adds a project component).
This will be the first year such a course has been offered at Bristol, and it has been deliberately designed to allow some flexibility in the content. I’ll be covering the fundamentals of graph theory, and the main topics I intend to cover are Euler tours, Hamiltonian circuits, adjacency matrices / spectral graph theory, planarity, and the Platonic solids. This will be largely self-contained, although some confidence with linear algebra will be helpful in places. If you’re a student currently weighing up choices for next year, and have any questions about this part of the course, feel free to get in touch!
I’m offering a couple of possible projects for third-year students at Bristol (i.e., for MATH32001 or MATH32200 depending on amount of time) in the upcoming academic year (2012/13). Other topics in areas such as spectral graph theory or computational number theory could also be possibilities; students are welcome to get in touch (via my magdt@bristol account) to arrange a more in-depth discussion.
1) The Mathematics of Social Networks
This project would start with an introduction to the key concepts of graph theory, before turning to applications to ‘social’ graphs. For instance, how might we identify the most influential scientists from the graph of their collaborations? If two countries come into conflict, who are their neighbours more likely to ally with? And how can it be that, on average, your friends have more friends than you do- yet the same is true for them?
2) Discrete and Computational Geometry
Although the study of geometry is almost as old as mathematics itself, discrete and computational geometry – at the intersection of computer science and mathematics – has only attracted attention in the last few decades. Nonetheless, it has found many applications, such as terrain reconstruction, robot motion planning, and remarkable advances in the discipline of ‘mathematical origami’.
A project in this area might suit a student with a strong interest/ability in programming (particularly related to computer graphics), but the material can also be approached in a purely theoretical way.
These remarks started life as a series of short posts on Google+. But no-one uses Google+, so I’ve archived them here.
I: you can make Voronoi diagrams using fine sand and blocks with holes drilled in.
What’s a Voronoi diagram? In such an image, the plane is divided up into cells around sites, such that the closest site to any point is the one in the same cell. Thus the boundaries are equidistant between sites; for the sand, those are the raised ridges, with the sites being the holes.
There’s obvious applications to mapping, say, your nearest coffee shop; an early application was tracing the source of a cholera outbreak to a particular water pump. But it also explains natural processes that involve growing or spreading, such as the patterning of giraffes!
II: The one-cut theorem.
If you draw a shape out of straight lines then -even if it has holes, such as the letter A – there’s a way to fold a piece of paper such that a single straight cut will give you something which, when unfolded, is the shape you wanted. (Some example folding patterns which we used are at http://howtofoldit.org/ ). For more details, see The Fold-and-Cut Problem.
‘FastRunner‘ – prototype Ostrich-like legs that might be able to hit 30-50mph (I suspect they’re trying to make the roadrunner).< /li>
Robotic birds, from gliders that can land on a perch, to flight via flapping wings.
IV: Polyhedral unfoldings
V: The complexity of games and puzzles.
For instance, a common question in the study of games is whether there’s a way to determine if you have a winning move this turn- the ‘mate in one’ problem for chess. It turns out that if you generalise Settlers of Catan to arbitrary-sized boards, then you can’t even feasibly handle the ‘mate in zero’ problem – that is, determine if you’ve already won! We also learnt of the hardest game in the world, Rengo Kriegspiel, which is blindfolded team Go, and turns out to be undecidable.
A while ago I became interested in `captured lightning‘ Lichtenberg figures, but without access to megavolt-scale physics gear, I wondered if I could simulate them in software instead. I was reminded of this when I had my JMM art exhibition entry printed on glass, as this would give me something a bit closer to the acrylic blocks. Some initially vague google searches eventually lead me to Diffusion-limited aggregation, a process that generates trees somewhere between ferns and lightning bolts. I set about implementing this in processing, and you can play around with a small version of it by clicking through here (may ask for permission to run java):
I’ve been trying to extend the results of the work described in this post, and following a suggestion of Noam Elkies have changed my search strategy from points corresponding to simple EDS triples to those given by (A,u,c) parametrisations as described here. Experimenting with these revealed some serious deficiencies with the height function in SAGE, so EDS are still involved at a practical level- but with enough magma licenses, one could just test all the points directly.
In good news for maths but perhaps bad news for my would-be paper, this straightforward approach has yielded several new (and record-breaking) examples of small height points, which I’ve added to the tables. A few also match or improve upon the best known values for most, highest, and most consecutive integral multiples. The table below summarises these: for the point [0,0] on the curve E:Y2 + a1XY + a3Y = X3 + a2X2,with P the corresponding point on the minimal model of E, we list the values of n≤50 such that nP is integral.
Highest integral multiples: Over Q, the record is 31; this is exceeded by point A, at 35. Most integral multiples: Over Q, the record is 16. All seven examples above match or exceed this: point B has the most, at 22; followed by A at 20; C,D and G at 17; and E and F at 16. Most consecutive integral multiples: Over Q, the record is 14: points B and G both beat this, with their first 15 multiples being integral.
I have uploaded a preprint of some recent efforts to the arXiv. In a break from my cyclotomic matrix work, this revisits a project I first became interested in over four years ago: the search for points with small height on elliptic curves over number fields, through the use of elliptic divisibility sequences. There used to be a series of posts on this topic here on Modulo Errors, but I think the paper does a better job of summarising the bits that are right, whilst some of my other claims (on the related question of computing pairings via elliptic nets) I am now dubious about, and a lot of the SAGE code supplied is unusably out of date, so I’ve taken them down for now.
However, I have created a more permanent page that lists all the points/curves I recovered, in fuller detail than summarised in the paper: for each sequence one can easily write down two points on non-isomorphic curves, so in the interests of brevity I gave the recipe and then just one example per sequence. It’s my hope that new entries will be added to this list over time, by the eds method or others: in particular, I’m keen for it to include examples over number fields of higher degree than the quadratic cases it’s currently restricted to. Contributions welcome!
I gave the Number Theory Seminar at the Department of Pure Mathematics, University of Waterloo on Thursday, September 8th. My slides are available in presentation or handout form (except the latter is missing the interlacing demo which didn’t render into individual slides correctly).
I used this talk as an opportunity to present some results that were only at the conjectural stage last time I spoke on the topic. I have been working with Gary Greaves on Lehmer’s problem for matrices over the Gaussian and Eisenstein integers; we believe that we have proved the conjecture for those, and are slowly assembling a paper to that effect.
I’d recently ordered Ben Fry‘s Visualizing Data and started reading it this weekend; just a few pages in I learnt how to import data to processing and a project was born… Since New Orleans I’ve been increasingly interested in mathematical art, and whether in particular I could create something interactive. Here’s what I’ve come up with after a couple of rainy afternoons:
So what is it? Each point represents a number up to 10,000, arranged on an Archimedean spiral, and coloured depending on its smoothness: a smooth number is one with only small prime factors. More precisely, N is B-smooth if the largest prime dividing N is at most B (so 2-smooth numbers are powers of 2; 3-smooth numbers are multiples of 2 and/or 3 only; any number shown will obviously be at worst 10,000-smooth). You can adjust the smoothness bound with the slider: in ‘gradient’ mode the brighter a point, the smoother it is; whereas in ‘threshold’ mode a point is simply plotted or not depending on whether it passes the smoothness test (the mode can be toggled by pressing space).
The least smooth numbers are the primes, and it was thinking about prime spirals that lead me in this direction: the Ulam spiral is one of the first examples of computer-aided mathematics visualisation, and I’ve taken the circular layout from its close relative, the Sacks spiral. In fact, my original plan was to use the number of prime divisors, rather than smoothness, for deciding when to plot points, with the Sacks spiral as a special case. But the pictures for larger bounds weren’t particularly interesting- 10,000 just isn’t big enough to allow much of a range of behaviour. So I switched to smoothness, and whilst that means you can’t identify the primes directly, sometimes they’re conspicuous by their absence: in the Sacks spiral there are curves with an unusually high concentration of primes, and in the smoothness spiral there are similarly ‘missing’ curves. There seem to be lots of other features too- if you’d like a closer look, here’s an enormous render of the 101-smooth numbers shown above, created using processing’s PDF mode.
Lorenz Manifold at the Changing Perspectives Exhibition
Today’s post by Haggis the Sheep demonstrates how crochet can help understand some topologically-interesting surfaces, so I felt I should mention a similar piece of fibre art I encountered this weekend. The object on the left is a Lorenz Manifold made out of over 25,000 stitches (plus three wires), and took Bristol mathematician Hinke Osinga 85 hours to assemble. Osinga (along with Bernd Krauskopf) had been experimenting with computer visualisation of the manifold, and developed an algorithm which ‘grew’ the image from a small disc, adding layers with additional or fewer points at each step to specify the local features of the surface. This approach conveniently works just as well for wool as pixels – each row of a crochet pattern differs from the last by increasing or decreasing the number of stitches to alter the shape.
But what does it actually represent? Lorenz was one of the founders of chaos theory, discovering the ‘butterfly effect’, the way in which seemingly small changes to a system such as the weather could escalate into major differences in behaviour. The Lorenz oscillator is a set of rules for evolving the position of a point in 3-dimensional space which exhibits this chaotic nature: starting points generally find their way to the Lorentz attractor, a complex pattern that never repeats itself. However, points on the Lorenz manifold manage to avoid this trap, and instead settle at the origin, the ‘central’ point of space.
Some of Hinke and Krauskopf’s computer visualisations, their crochet of the manifold, and a rendition in steel by Benjamin Storch can be viewed for the rest of the month at The Bristol gallery, which can found down by the harbourside. They’re there as part of one of the Changing Perspectives exhibitions, which also includes work from my department’s invaluable Chrystal Cherniwchan: the photographic project Exploring the Valley, and the Mathematical Ethnographies films. As well as maths, there are exhibits inspired by scientific topics from shifting glaciers to high voltage electricity, so if you’re local, why not take a look in person? If not, well, you can get a taste from the links above, or if you’re feeling brave, grab the instructions to crochet your own Lorenz manifold!