Tributes to cryptanalysts

Earlier on cp4space, I mentioned how there were a couple of planned tributes to Alan Turing and Bill Tutte. Subsequently, both of these projects have since been completed.

Firstly, the premiere of A Man From The Future was performed by the Pet Shop Boys at the BBC Proms. An excerpt, entitled He Dreamed Of Machines, is available on YouTube:

This single is due to appear in the forthcoming biographical film, The Imitation Game.

Similarly, the Bill Tutte memorial has now been unveiled. The main sculpture is an arrangement of panels inspired by punched card, which display an image of Tutte when viewed from the correct perspective:

This is part of a larger initiative designed to increase awareness of W. T. Tutte through various events and a local scholarship.

Posted in Uncategorized | Leave a comment

Hyperbolic Minecraft

(Firstly, this is a test to see whether WordPress is configured to automatically link to cp4space posts as tweets from apgox. Hopefully it will succeed.)

Yesterday, I received a rather interesting e-mail from Tim Hutton, lead developer of the reaction-diffusion software Ready. It was concerned with a (possibly facetious) post by Mike Stay concerned with the possibility of implementing a disproportionately popular video game in hyperbolic space. I haven’t personally encountered the aforementioned game, although one of my colleagues mentioned at a barbecue that his children were obsessed with it.

To summarise, we needed a way to construct the {4, 3, 5} honeycomb of hyperbolic space (the dual of the order-3 tiling by dodecahedra) to use as an underlying grid for Ready. Fortunately, I realised that the intersection of the honeycomb with the xy-plane is merely the bog-standard order-5 square tiling, which meant that I could reduce it to an easy two-dimensional problem. With some slight help from Mathematica’s FullSimplify routine, I prepared the following recipe:

  • Define t = (1 – sqrt(7 – 3 sqrt(5)))/3.
  • Let the `central cube’ have vertices (±t, ±t, ±t).
  • We define six `mirrors’ to be the spheres with radius sqrt(3 – sqrt(5)) and centred on one of the following six vertices: (1, 0, 0), (0, 1, 0), (0, 0, 1), (-1, 0, 0), (0, -1, 0), (0, 0, -1)
  • Sanity check: the central cube is the volume containing the origin and enclosed by the six mirrors.
  • Produce images of the central cube by `reflecting’ in the mirrors to your heart’s content. By `reflecting’, I mean this: http://en.wikipedia.org/wiki/Inversive_geometry#Circle_inversion
  • So, to reflect p about the mirror with centre q, you apply the transformation p –> q + (p – q)*(R^2/|p – q|^2) where R^2 = 3 – sqrt(5) is the squared radius of the mirrored sphere, and p and q are vectors in $\mathbb{R}^3$.
  • The result should be the {4, 3, 5} tiling of a Poincare ball of some radius I can’t be bothered to calculate.

Miraculous, this ad hoc sequence of instructions actually worked, and Tim was able to construct the first couple of shells of the hyperbolic tiling. For instance, here is the tessellation after the second shell has been added:

435_iteration2

So far, so good. However, there is the issue of avoiding duplicated blocks, which I addressed with the following (incredibly lazy) suggestion:

I would avoid duplicates by rejecting any new cubes whose centres coincide with existing cubes (by using a hashmap or something similar).

Often many problems in life reduce to the dichotomy of whether to `do maths’ or `use a hashmap’. I’ve decided to resort to the latter, by virtue of working for several weeks for a software engineering company. More diligent people actually design an elegant method of coordinatising hyperbolic space; one such mathematician is Maurice Margenstern, who wrote a paper addressing the two-dimensional analogue of this problem.

Anyway, Tim Hutton was satisfied with the hashmap solution, and this algorithm has since been incorporated into the Ready code (c.f. relevant section of the Subversion repository). As a preliminary trial, here is a Ready screenshot of an experiment with the Gray-Stott reaction-diffusion system running on the {4, 3, 5} tiling of hyperbolic space:

gray_scott_on_435_level6

 

Anyway, Tim decided to contribute an OEIS sequence containing the numbers of cubes within a distance of at most n from the central cube. Slightly more naturally, this sequence can be regarded as the partial sums of this sequence (which counts the number of cubes in each layer):

1, 6, 30, 126, 498, 1982, 7854, 31008, 120666, ...

Similar sequences have been created for two-dimensional tilings. Indeed, the order-3 heptagonal tiling has the remarkable property that the number of tiles in each layer is seven times a Fibonacci number:

Specifically, if we divide the number of tiles in each layer by seven, we obtain the sequence (1, 3, 8, 21, …), which are alternate Fibonacci numbers. Similarly, a three-dimensional honeycomb is dictated by a third-order linear recurrence relation; unlike its dual tiling, this happened to be in the OEIS.

Posted in Uncategorized | 3 Comments

First female Fields medallist

Tomorrow, this year’s Fields medals were awarded*. The four recipients of this prestigious quadrennial accolade have made profound advancements in their respective areas of mathematics, specifically:

  • Artur Avila has revolutionised the study of dynamical systems, proving many hitherto open conjectures in the field. This is exciting from both a pure perspective, augmenting our understanding of the ergodic theory of various systems; and from an applied point of view, giving a deeper insight into the behaviour of chaotic systems such as phase transitions.
  • Manjul Bhargava‘s research massively generalises Gauss’s composition law, as well as enabling one to enumerate rings of finite rank with a particular discriminant. This has subtle connections to the theory of algebraic curves, including new bounds on the average rank of elliptic curves.
  • Martin Hairer made extremely notable discoveries about stochastic partial differential equations, which generalise PDEs by including the effects of random noise. In doing so, he has provided solutions to many new families of SPDEs, several of which have physical interpretations.
  • Finally, Maryam Mirzakhani has contributed immensely not only to the geometry of Riemann surfaces and their moduli spaces, but also their dynamics. Incidentally, she is the first female Fields medallist (whilst several great female mathematicians flourished in the twentieth century, including Emmy Noether, Julia Robinson and Ruth Lawrence, the award remained elusive until now), and the remainder of this article is dedicated to her outstandingly brilliant accomplishments.

*International Date Line.

Maryam Mirzakhani

Her work is concerned primarily with compact Riemann surfaces of a given genus. From a merely topological perspective, these are multi-holed tori. Riemann surfaces, however, are endowed with a complex structure and therefore a natural metric, which is much deeper and more interesting.

With the exception of the trivial cases of the sphere and torus, these compact Riemann surfaces are quotients of the hyperbolic plane (c.f. Uniformisation Theorem). These quotient spaces are really exciting, and admit an intuitive classification thanks to Thurston’s beautiful theory of orbifolds. Maryam’s early work established a formula for the number of simple closed geodesics on these Riemann surfaces, together with asymptotics for their lengths.

Her next advancements were related to the moduli spaces of Riemann surfaces.

Moduli spaces

So, what’s a moduli space? It’s probably easiest to explain in the genus-one case, which is simple enough to understand, without being completely trivial. Recall that we can obtain a torus by taking a parallelogram and associating edges. Or equivalently by taking the plane and quotienting by a lattice:

freedom

In choosing the fundamental parallelogram, we have a huge amount of freedom. Both the red pair and blue pair of vectors above generate the same lattice, and therefore describe geometrically identical tori.

Now, we can consider the four-dimensional parameter space of fundamental parallelograms (i.e. the space of points (x, y, z, w), corresponding to the parallelograms generated by the vectors (x, y) and (z, w)). At the moment this is just plain old \mathbb{R}^4, but it is more geometrically meaningful to identify points that describe the same lattice. The resulting quotient space, the moduli space, is a four-dimensional manifold.

Observe that rotating and scaling the two vectors results in geometrically similar lattices (therefore geometrically similar Riemann surfaces). We can consider a further quotient of this four-dimensional space, namely a two-dimensional orbifold. You may recognise this as being the quotient of the upper half-plane by the action of the modular group, or the fundamental region of Klein’s j-function:

So, that’s basically what a moduli space is. Maryam discovered a formula for the volume of moduli spaces of a particular genus, resulting in a remarkably elegant new proof of Witten’s conjecture.

Dynamics

Not merely content with providing a marvellous insightful proof about the geometry of moduli spaces, she decided to investigate their dynamics! Firstly, she demonstrated the ergodicity of Thurston’s ‘earthquake deformation’ of hyperbolic space, which is certainly no mean feat!

Ergodic theory is largely concerned with the topological closure of orbits of points. For example, if we take a geodesic on a torus, it will either form a closed loop (e.g. a torus knot) or an irrational cable:

This is a dense subset of the torus, so its topological closure is the torus itself. On more complicated manifolds, such as the moduli spaces considered by Mirzakhani, the topological closures of geodesics can be infinitely intricate fractal structures.

In a similar vein to how holomorphic functions are much more well-behaved than real analytic ones, Mirzakhani settled a long-open conjecture and proved that closures of complex geodesics are always algebraic subvarieties (which are smooth and tame, unlike the pathological fractals that arise in the ergodic theory of real geodesics).

Posted in Uncategorized | 2 Comments

How to do geometry properly

For literally thousands of years, people have been writing books about elementary geometry. Many of these, such as Bradley and Gardiner’s Plane Euclidean Geometry, are concerned with solving problems in Euclidean geometry. They are subsequently bought by many adolescents intending to compete in the International Mathematical Olympiad.

This is completely pointless.

We shall instead explore Tarski’s cool, slender, axiomatic approach to geometry. This has numerous advantages over the cumbersome alternatives:

  • Simplicity: there are only three concepts, namely the idea of a ‘point’ and the relations of ‘betweenness’ and ‘congruence’. These could be understood by the entire populace of the Clapham omnibus.
  • Brevity: memorising hundreds of definitions, lemmas and theorems will provoke a reaction of ‘tl;dr‘ from all but the most hardened tediophiles. Fortunately, Tarski only has eleven axioms which rest on top of the seven axioms and two inference rules of first-order logic.
  • Decidability: we can algorithmically decide whether or not a statement is true, and provide a perfectly rigorous proof without all of that mucking about with diagram dependency.
  • Innumeracy: no arithmetic is required, let alone algebra.

So, without further ado, we shall introduce the framework. To make this entirely self-contained (and therefore giving geometry textbooks an unfair advantage, since they assume knowledge of concepts such as algebra) we shall include first-order logic here.

Language

The language is an especially simple one, in that it is first-order and involves no function symbols. It is constructed inductively as follows:

  • Variables are typically written as lowercase letters, such as x and y, and understood to represent geometrical points. We allow the use of the prime symbol to enable an unbounded number of variables with a finite alphabet (such as x‘, x”, x”’, x”” and so on).
  • Atomic formulae are expressions of the following form (where wxyz are variables):
    • (xy), (read as ‘x and y are the same point’);
    • B(xyz), (read as ‘y lies on the line segment with endpoints x and z‘);
    • C(wx, yz), (read as ‘the distance between w and x is the same as the distance between y and z‘);
    • ⊥, (read as ‘false’).
  • Formulae are constructed inductively in terms of atomic formulae:
    • Every atomic formula is a formula;
    • If P and Q are formulae, then so is (P ⇒ Q) (read as ‘P implies Q’);
    • If x is a variable and P is a formula, then (∀x.P) is a formula (read as ‘for all x, P is true’).
  • Sentences are formulae in which every variable is bound (every variable x is enclosed within the scope of a ∀quantifier).

That is all.

Axioms

Axioms are formulae which are assumed without proof. Firstly, we have seven logical axiom-schema:

  1. Axiom K: for all formulae P and Q, the formula (P ⇒ (Q ⇒ P)) is an axiom.
  2. Axiom S: for all formulae P, Q and R, the formula ((P ⇒ (Q ⇒ R)) ⇒ ((P ⇒ Q) ⇒ (P ⇒ R))) is an axiom.
  3. Double negative elimination: for every formula P, the formula (((P ⇒ ⊥) ⇒ ⊥) ⇒ P) is an axiom.
  4. Reflexivity of equality: for every variable x, the formula (∀x.(xx)) is an axiom.
  5. Instantiation of equality: if x and y are variables, and P is a formula not containing ∀y, then (∀x.(∀y.((xy) ⇒ (P ⇒ P[y/x])))) is an axiom, where P[y/x] is the formula obtained by replacing every instance of x in the formula P with y.
  6. Universal instantiation: if x and y are variables and P is a formula, then (∀x.(P ⇒ P[y/x])) is an axiom.
  7. Seventh axiom: if x is a variable and P and Q are formulae, with x not occurring unbound in P, then ((∀x.(P ⇒ Q)) ⇒ (P ⇒ (∀x.Q))) is an axiom.

These are augmented with eleven geometric axioms:

  1. Reflexivity of congruence: (∀x.(∀y.C(xyyx))) is an axiom, which is logically equivalent to the symmetry property of metric spaces.
  2. Identity of congruence: (∀x.(∀y.(∀z.(C(xyzz) ⇒ (xy))))), which is logically equivalent to another metric property.
  3. Transitivity of congruence: (∀u.(∀v.(∀w.(∀x.(∀y.(∀z.(C(uvwx) ⇒ (C(uvyz) ⇒ C(wxyz))))))))), which (together with reflexivity of congruence) implies that congruence of line segments is an equivalence relation.
  4. Identity of betweenness: (∀x.(∀y.(B(xyx) ⇒ (xy)))), which means that if a point lies on a degenerate line segment with equal endpoints, then it is the endpoints.
  5. Pasch’s axiom: (∀u.(∀v.(∀x.(∀y.(∀z.(B(xuz) ⇒ (B(yvz) ⇒ ((∀w.(B(uw, y) ⇒ (B(v, w, x) ⇒ ⊥))) ⇒ ⊥)))))))), which means that any two internal cevians intersect at a point.
  6. Existence of triangles: ((∀x.(∀y.(∀z.((((B(xyz) ⇒ ⊥) ⇒ B(yzx)) ⇒ ⊥) ⇒ B(zxy))))) ⇒ ⊥), which forces the geometry to be non-empty and at least two-dimensional.
  7. Continuity: for any formulae φ(x) and ψ(y), each with only one free variable, we have the axiom (∀w.((∀x.(∀y.(φ(x) ⇒ (ψ(y) ⇒ B(wxy))))) ⇒ ((∀z.((∀x.(∀y.(φ(x) ⇒ (ψ(y) ⇒ B(xzy))))) ⇒ ⊥)) ⇒ ⊥))), which means that we can construct a point given by a Dedekind cut whose sets are definable subsets of a ray.
  8. Five segment: (∀u.(∀x.(∀y.(∀z.(∀u.(∀x’.(∀y’.(∀z’.(((xy) ⇒ ⊥) ⇒ (B(xyz) ⇒ (B(x‘, y‘, z‘) ⇒ (C(yxy‘, x‘) ⇒ (C(yzy‘, z‘) ⇒ (C(uxu‘, x‘) ⇒ (C(u, yu‘, y‘) ⇒ C(uzu‘, z‘)))))))))))))))), which means that a triangle with an extended edge is rigid.
  9. Segment construction: (∀u.(∀v.(∀x.(∀y.((∀z.(B(xyz) ⇒ (C(yzuv) ⇒ ⊥))) ⇒ ⊥))))), which means that we can construct the other endpoint of a segment with a specified endpoint, length and direction.
  10. Euclid’s axiom: To forbid hyperbolic geometry, introduce the axiom (∀u.(∀v.(∀x.(∀y.(∀z.(((xu) ⇒ ⊥) ⇒ (B(xuv) ⇒ (B(yuz) ⇒ ((∀a.(∀b.(B(xya) ⇒ (B(avb) ⇒ (B(bzx) ⇒ ⊥))))) ⇒ ⊥))))))))), which is equivalent to the parallel postulate.
  11. All points are coplanar: To forbid higher-dimensional geometry, introduce the axiom (∀u.(∀v.(∀x.(∀y.(∀z.(((uv) ⇒ ⊥) ⇒ (C(ux, vx) ⇒ (C(uy, vy) ⇒ (C(uz, vz) ⇒ ((B(zxy) ⇒ ⊥) ⇒ ((B(yzx) ⇒ ⊥) ⇒ B(xyz)))))))))))), which means that the perpendicular bisector of two given distinct points is a line.

Rules of inference

A theorem is a formula that is provably true. In order to assign truth to formulae, we are allowed the following rules of inference:

  1. Every axiom is automatically a theorem.
  2. Modus ponens: If P and (P ⇒ Q) are theorems, then so is Q.
  3. Generalisation: If P is a theorem, and x is a variable, then (∀x.P) is also a theorem.

Armed with these axioms and rules of inference, we can prove many theorems in geometry. It is a remarkable fact (known as completeness), first established by Alfred Tarski, that if P is a sentence then either P is a theorem or its negation (P ⇒ ⊥) is a theorem. This is really awesome, since it leads to the following corollary:

Decidability of geometry: We can decide whether a sentence in geometry is true or false, simply by exhaustively proving things until we establish either the sentence or its negation as a theorem.

The theory of algebraically-closed fields of characteristic 0 is also decidable (Lefschetz principle), as is the first-order theory of the reals (also proved by Tarski, and used as a lemma in proving that geometry is decidable). Peano arithmetic is undecidable, a fact known as Gödel’s Incompleteness Theorem.

We are now ready to prove things using this system. Here’s a simple problem:

Exercise 1 (triangle inequality): Prove (∀a.(∀b.(∀x.(∀y.(∀z.(C(xzxa) ⇒ (C(yzyb) ⇒ (B(xya) ⇒ (B(xyb) ⇒ B(xab)))))))))) using the Tarski axioms together with the rules of inference.

If you found that too easy, here’s a slightly more challenging one:

Exercise 2 (question 6, IMO 2011): Prove (∀a.(∀b.(∀c.(∀d.(∀a‘.(∀b‘.(∀c‘.(∀o‘.(∀o.(∀p.(∀q.(∀r.(∀s.(∀t.(∀u.(∀v.(C(o, a, o, b) ⇒ (C(o, b, o, c) ⇒ (C(o, c, o, d) ⇒ (C(oddp) ⇒ (B(odp) ⇒ (C(qaoa) ⇒ (C(rapa) ⇒ (C(qa‘, ra‘) ⇒ (C(qbob) ⇒ (C(rbpb) ⇒ (C(qb‘, rb‘) ⇒ (C(sbob) ⇒ (C(tbpb) ⇒ (C(sb’tb’) ⇒ (C(scoc) ⇒ (C(tcpc) ⇒ (C(s, ctc) ⇒ (C(ucoc) ⇒ (C(vcpc) ⇒ (C(uc’vc’) ⇒ (C(uaoa) ⇒ (C(vapa) ⇒ (C(uava) ⇒ (((q = o) ⇒ ⊥) ⇒ (((r = p) ⇒ ⊥) ⇒ (((s = o) ⇒ ⊥) ⇒ (((t = p) ⇒ ⊥) ⇒ (((uo) ⇒ ⊥) ⇒ (((v = p) ⇒ ⊥) ⇒ (C(o‘, a‘, o‘, b‘) ⇒ (C(o‘, c‘, o‘, b‘) ⇒ ((∀z.(C(ozoa) ⇒ (C(o‘, zo‘, a‘) ⇒ ((((B(oo‘, z) ⇒ ⊥) ⇒ B(o‘, zo)) ⇒ ⊥) ⇒ B(zoo‘))))) ⇒ ⊥)))))))))))))))))))))))))))))))))))))))))))))))) using the Tarski axioms together with the rules of inference.

 

Posted in Uncategorized | 9 Comments

I’m still alive

So, there hasn’t been a cp4space post for over a fortnight now. I’ll now attempt to excuse this massive lapse, and hopefully convince you that what I’ve been doing in the meantime is still somewhat worthwhile. Amongst other things, I met the world-famous model theorist Ehud Hrushovski completely by coincidence in a random pub in Edinburgh.

Obviously, I’ve been working full-time, and being human it is also necessary to sleep. The evenings are primarily occupied by social events of some nature, which only really leaves the weekends to conduct any projects. So, in reverse chronological order, here is what I’ve been investigating in the last two weekends:

Last weekend: <s, t : s^10 = t^3 = (st)^2 = 1>

This is a surprisingly exciting group.

Firstly, it is straightforward to verify from its presentation that the group is a hyperbolic Dyck group, i.e. the orientation-preserving symmetries of the kaleidoscopic tiling of the hyperbolic plane by triangles with interior angles (π/2, π/3, π/10).

In other words, it is the group generated by the following Möbius transformations:

  • s(z) = z exp(i pi/5);
  • any t with the property that t(t(t(z))) = s(t(s(t(z)))) = z for all z.

Now, this is a ring-theoretic definition, so we can apply a ring automorphism and replace exp(pi/5) with exp(3pi/5) in the above definition without changing the resulting abstract group. However, this is entirely different from a topological perspective, since we have a group of spherical symmetries — rotations — rather than hyperbolic symmetries.

So we can regard this as a dense subgroup of SO(3) generated by two rotations. It transpires that these are precisely the actions on the Bloch sphere by braiding three Fibonacci anyons — weird quasiparticles which can only exist in two dimensions. The element s corresponds to interchanging two strands by a twist whilst leaving the third in situ; the element t corresponds to cyclically permuting the three strands.

Interestingly, this behaviour could be used to build a fault-tolerant topological quantum computer; I’m currently writing an essay on the subject at the moment. See arXiv article 0902.3275 for a description of Fibonacci anyons, and 0707.1889 for a general review of topological quantum computation. It is important that the subgroup of SO(3) is dense, since this means any single-qubit unitary gate can be emulated to arbitrary accuracy by braiding anyons.

The resulting quantum computer, if realisable, would be so beautiful — all computations are performed simply by twisting particles around each other on the plane. Rather like a two-dimensional abacus, but so much more exciting!

Returning to the group, observe it has an index-6 normal subgroup. Specifically, we have a homomorphism into the symmetric group S3, by either considering the action of the braid group on the three strands, or of the hyperbolic group on the colours {red, blue, yellow} in the diagram above. I suspect that this subgroup is simple, since there doesn’t seem to be any obvious normal subgroup. A way to verify this would be to show that given a non-trivial group element, its conjugacy class generates the entire group.

Penultimate weekend: half-baked knightships

For several months, Dave Greene, Chris Cain and Ivan Fomichev have been collaborating on building a variable-speed oblique spaceship in Conway’s Game of Life. After all of the components had been discovered, however, I had no qualms about spending a day writing an object-oriented Python script to assemble the components in an epic display of corollary-sniping!

The pattern file can be obtained from Golly’s online pattern archive. More information is on the ConwayLife wiki page, which seems to give me far more credit than I deserve (not that I’m complaining!). Chris Cain later optimised the design, reducing the period by an entire order of magnitude.

Anyway, as mentioned at the start of the article, it is vitally important that I sleep. Failure to do so could lead to fatigue-induced errors appearing in telecommunications software serving millions of people…

Posted in Uncategorized | 3 Comments

If sunflowers were square

What did Alan Turing ever do for us? Answering this question is much more subtle than one would initially imagine. He has shaped the world in at least three diverse waves of influence, which despite being apparently disparate are inextricably linked both historically and mathematically.

The first of these three waves, and by far the most well-known, was his cryptanalysis of the Enigma cipher at Bletchley Park. This was pivotal in determining the outcome of the Second World War, and his contribution is considered equal to that of Winston Churchill. One can liken this accomplishment to a supernova — whilst being singularly spectacular, its effects were immediate.

The second of these waves was the development of computer science. This began in Cambridge with his seminal paper addressing the Entscheidungsproblem, and its effects today are more apparent than ever before: practically every electronic device we own is orchestrated by a variant of Turing’s idea of a universal machine. Again, this wave has recently culminated: different paradigms such as parallel computing, functional programming and even quantum computation are emerging to surpass the limitations of the Turing machine.

The third wave of influence, which is by far the least known, is still in its infancy. It began with a paper entitled The Chemical Basis of Morphogenesis, in which Turing proposed an explanation for how sophisticated patterns such as leopard spots can emerge through the processes of chemicals reacting and diffusing to adjacent cells. Here is an animation of such a reaction-diffusion system on the surface of an actual leopard in Tim Hutton’s Ready program.

leopard

Alan also investigated the phyllotaxis (arrangement of seeds) in the head of a sunflower. The number of ‘spirals’ in each direction is typically a Fibonacci number; this was recently confirmed by a Manchester-based public project, Turing’s Sunflowers. The usual model of phyllotaxis is a parametric equation for the position of the nth seed, namely z = \sqrt{n} \exp(2 \pi i n/\phi). This produces a stunningly realistic and very efficient packing of seeds:

Whilst this is an incredibly accurate model of how sunflower seeds are arranged, it fails to explain why they are arranged in this manner. Obviously, the reason for doing so is to utilise the space efficiently, but the mechanism by which this is achieved is much more mysterious. After all, the process of placing seeds positioned at distances of sqrt(n) and rotated by multiples of the golden angle is not easy, especially by a plant with no internal computer!

Much more recently, an applied mathematician called Matt Pennybacker decided to investigate the partial differential equation that models the transmission of auxins (plant hormones associated with growth). He discovered that it can be idealised as follows:

sunflower-PDE

Given an initial distribution of auxins on the circumference of a homogeneous disc, this partial differential equation causes an annular front to propagate towards the centre, laying down an incredibly convincing distribution of primordia:

Unlike typical reaction-diffusion systems, this involves only a single chemical u. Nevertheless, the same complexity and variety of behaviour is possible, since the underlying differential equation is fourth-order rather than second-order. These one-chemical fourth-order systems have been recently implemented in Tim Hutton’s Ready, some of which behave like the canonical two-chemical Gray-Scott model shown in the leopard animation. The result of running the sample pattern phyllotaxis_fibonacci.vti results in the following:

phyllotaxis

This is realistic near the centre, but suffers from boundary effects near the edge. The fact that this is on a square, rather than a disc, causes it to display qualitatively different behaviour from the usual sunflower. Indeed, if sunflowers were square, they would probably resemble the picture above.

Unfortunately, Turing’s untimely cyanide-induced death interrupted his fruitful investigation of biological pattern formation. Nevertheless, this year it was finally confirmed experimentally that pattern formation does indeed work in the way Turing proposed (albeit slightly refined to include heterogeneity).

At the beginning of the article, I mentioned three sequential discoveries initiated by Turing, namely mechanised cryptanalysis, computer science and pattern formation, and how the latter is still in its infancy. This suggests that there may be a fourth term in the sequence — a field that hasn’t even begun yet. A possible candidate for this is artificial intelligence; whilst some people claim that Eugene Goostman passes the test, it actually exhibits profound displays of logical inconsistency. We can, however, be certain that this article will have a sequel as soon as the next Turing-inspired breakthrough happens…

Further resources

  • If you’re interested in experimenting with reaction-diffusion systems (which you should be, given that you’re reading cp4space), you can download Ready here.
  • There’s a lot of really exciting stuff on Tim Hutton’s Google+ page, including more examples of partial differential equations modelling pattern formation.
  • What happens when you breed white-spotted black fish with black-spotted white fish? It transpires that you actually get a labyrinthine pattern, which is the result of naively interpolating between the two reaction-diffusion equations. The results are here.
Posted in Uncategorized | 1 Comment

Applications of quaternions

Quaternions were discovered by Sir William Rowan Hamilton in a flash of inspiration as he crossed Brougham Bridge, inscribing the following relations into one of the stones:

i² = j² = k² = ijk = −1

Specifically, a quaternion is a number of the form qabicjdk, where a, b, c, and d are real and the elements ij and k satisfy the above relations.

Note that multiplication of quaternions is non-commutative, but the other field axioms hold as expected. In particular, addition forms an Abelian group, multiplication is associative and distributes over addition, and we have a multiplicative identity, 1. Moreover, the real line occurs as a subspace of the quaternions; this is precisely the centre of the multiplicative group.

The notions of ‘absolute value’ and ‘complex conjugation’ generalise to quaternions in the obvious way. Specifically, the multiplicative inverse of q is given by:

q^-1 = q*/|q|² = (a − bi − cj − dk)/(a² + b² + c² + d²)

Also, note that if q is a non-real quaternion, the R-linear subspace spanned by 1 and q is isomorphic to the field of complex numbers.

Rotations in \mathbb{R}^3 and \mathbb{R}^4

In two dimensions, a general rotation can be expressed in the form z → az, where a is a complex number of unit norm. One may naïvely assume that the same result holds for quaternions. However, this is untrue: we require a pair of unit quaternions, (a, b), to represent a general rotation q → aqb*. Moreover, (ab) and (-a, -b) represent the same rotation, so S³ × S³ is isomorphic to Spin(4), the double-cover of SO(4).

The diagonal subgroup {(a, a) : a in S³} has the property of fixing all points on the real line. Consequently, the three-space spanned by {i, j, k} is preserved by this subgroup, so we can represent three-dimensional rotations by unit quaternions. Indeed, S³ is isomorphic to Spin(3), the double-cover of SO(3).

Question 3 of NST1 2011

The following question appeared on a selection test for the British IMO team:

NST2011

 

See if you can solve it (solutions are welcome in the comments at the foot of this page).

 

Posted in Uncategorized | 12 Comments