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 | 2 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.

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:

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:

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:

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

Posted in Uncategorized | 12 Comments

Cipher 70: Wild goose chase

Once again it is Cipher Tuesday, and this time I actually have a cipher to release:

1. Frg hc n purffobneq va gur fgnegvat cbfvgvba.
2. Ba n cvrpr bs 90tfz N4 cncre, qenj gur Qlaxva qvntenz bs gur fdhner va juvpu gur oynpx xvat erfvqrf.
3. Nybat gur rvtugu ebj bs n Fpenooyr obneq, jevgr gur flfgrzngvp anzr bs gur zbyrphyr jubfr fxryrgny qvntenz lbh unir whfg qenja.
4. Cynpr frira zber qvtvgf ba gur Fpenooyr obneq fb gung obgu gur yrsg pbyhza naq obggbz-yrsg fdhner ner cresrpg.
5. Cynpr sbhegrra zber yrggref va gur cernagrcrahygvzngr ebj gb tvir n pneobulqengr punva.
6. Cynpr rkgen yrggref gb fbyir gur qbja' pyhrf bs guvf pebffjbeq:
(1) Gevnathyne ahzore (8)
(3) Pbagenpgvba ------- gurberz (7)
(5) Zl zneiryybhf --------- (9)
(7) Cynargnel pbyyvarnevgl (6)
(9) Flfgrzngvp (10)
(11) Synjyrff; pnaabg or rebqrq ol oveqf' ornxf (10)
(13) Gur Zban Yvfn vf na rknzcyr bs guvf (8)
(15) Yhpvsre (9)
7. Vagreyrnir n ulcura naq gur yrggref bs cnebyr' vagb gur 10gu ebj gb tvir nabgure betnavp zbyrphyr.
8. Vagrepunatr gjb yrggref, bar sebz rnpu bs gjb bs gur zbyrphyrf, gb tvir gjb arj betnavp zbyrphyrf naq nabgure inyvq jbeq.
9. Cynpr na K ba gur obneq fhpu gung gur rkcerffvba va gur ebj va juvpu vg vaunovgf vf cebcbegvbany gb gur irpgbe nobir vg.
10. Pbeerpg gur fcryyvat nppbeqvatyl.
11. Erzbir gur fvqr-punva sebz bar bs gur zbyrphyrf fb gung vg abj cregnvaf gb n pyretlzna.
12. Ercrng sbe gur bgure betnavp zbyrphyr.
13. Ba gur cvrpr bs cncre hfrq va fgrc 2, jevgr qbja gur ragver qrpvzny rkcnafvba bs Tenunz'f ahzore.
14. Haqb fgrc a, jurer a vf gur crahygvzngr qvtvg lbh jebgr.
15. Ercynpr gjb bs gur qvtvgf va gur svefg pbyhza jvgu gur qvtvg a, fhpu gung gur obneq abj pbagnvaf n cebprffbe.
16. Erzbir gur nsberzragvbarq cebprffbe sebz gur obneq.
17. Qevax a tynffrf bs jvar.
18. Vagrepunatr gur erznvavat qvtvg jvgu gur yrggre qverpgyl nobir gur K.
19. Erzbir nal yrggre sebz gur obneq gung bpphef va gur jbeq ohmm'.
20. Plpyvpnyyl crezhgr guerr yrggref fb gung gur svany pbyhza vf ubzbtrarbhf naq gur 9gu ebj pbagnvaf na npghny jbeq.
21. Erzbir n svir-yrggre znevar irffry sebz gur obneq.
22. Ercynpr bar bs gur gvyrf erzbirq va fgrc 19 gb erpbire gur fheanzr bs n Yvoreny Qrzbpeng cbyvgvpvna.
23. Erzbir zr naq rirelguvat ryfr gung qbrf abg orybat gb gur ynetrfg pbaarpgrq pbzcbarag.
24. Zbir rnpu N' gb gur ybjrfg habpphcvrq fdhner va vgf pbyhza, hayrff qbvat fb jbhyq pnhfr gur N' gb zbir hcjneqf.
25. Zbir gur frpbaq-ynetrfg pbaarpgrq pbzcbarag bar fcnpr qbjajneqf.
26. Va fgrc 24, lbh perngrq irefvba 3K bs n cnegvphyne ynathntr. Bar bs gur pbyhzaf pbagnvaf gur yrggref bs gbqnl' jevggra va gung ynathntr. Erzbir gubfr svir gvyrf.
27. Bar bs gur yrggref lbh erzbirq erfrzoyrf gur funcr bs gur frpbaq-ynetrfg pbaarpgrq pbzcbarag. Cynpr n juvgr ovfubc ba gur fdhner inpngrq ol gur erzbiny bs gung yrggre.
28. Gjb nqwnprag pbyhzaf rnpu pbagnva cerpvfryl bar yrggre. Erzbir gubfr yrggref.
29. Fjnc gur ovfubc jvgu gur havdhr pbafbanag vg guerngraf.
30. Ercynpr gur 3' jvgu gur yrggre juvpu fubhyq orybat va gur ybjrfg habpphcvrq fcnpr va gung pbyhza.
31. Zbir rnpu bs zl zvqqyr vavgvnyf qbjajneqf bar fcnpr, hayrff gur fdhner vf nyernql bpphcvrq.
32. Fjnc gur K' jvgu gur gvyr bpphclvat gur uvturfg cbfvgvba.
33. Fjnc gjb bs gur yrggref va gur ybjrfg ebj fhpu gung gur ovfubc vf vebavpnyyl cbfvgvbarq nobir n oynfcurzvp vavgvnyvfz.
34. Ercynpr evqr' jvgu evbg'.
35. Gurer ner gjb zngrevnyf ba gur obneq. Pbapngrangr gurz va qrpernfvat beqre bs qrafvgl.
Posted in Ciphers | 7 Comments

Cavalieri’s principle

Disclaimer (mainly to Marcus du Sautoy): The Ancient Greeks did not invent integration, and whilst I shall use Ancient Greek principles of mensuration to justify Riemann and Lebesgue integration, the Ancient Greeks did no such thing.

Finding volumes of cones and spheres

So, suppose you want to calculate the volume of a sphere, and hitherto only know that the volume of a cylinder is πr²h. We cannot use a clever argument involving cutting the cylinder into finitely many compact pieces with piecewise-smooth boundaries and reassembling them into a sphere, as you can convince yourself that the quantity:

I = total area of convex spherical surface − total area of concave spherical surface

must remain invariant under the operations of dissecting and reassembling. And since a cylinder has I = 0 whereas a sphere has I > 0, they are not scissors-congruent.

A more powerful idea is Cavalieri’s principle, which states that if every horizontal plane through two bodies A and B intersects them to give cross-sections of equal area, then A and B have the same volume. We can use this to deduce that a cone and pyramid of the same base area and height have the same volume. We can also deduce that a cylinder and square-based prism of the same cross-sectional area and height have the same volume.

Then, using a dissection argument, we can show that a pyramid has one third of the volume of its bounding cuboid. Putting these three facts together leads to a simple relationship between the volumes of a cone and cylinder of the same base area and height:

In other words, a cone has volume πr²h/3.

The next part is a significantly more sophisticated application of Cavalieri. Suppose we have a sphere of radius R centred on the origin, and consider the intersection with the horizontal plane z = a. By Pythagoras’ theorem, this has area r² − a², which is coincidentally also the area of an annulus bounded between concentric circles of radii r and a. Consequently, we can apply Cavalieri’s principle to show that a sphere has the same volume as the solid obtained by removing a double-cone from a cylinder:

Now, the cylinder has volume 2πr³ and double-cone has volume 2πr³/3, so the sphere must have volume equal to their difference, 4πr³/3.

Riemann versus Lebesgue integration

When Archimedes calculated upper and lower bounds for the value of π, he did so by bounding a circle between a circumscribed and inscribed 96-gon. By increasing the number of sides of the polygons, we can obtain tighter bounds.

If the supremum of the lower bounds agrees with the infimum of the upper bounds (which it does for these regular polygonal approximations), then we have the exact area of the circle. Riemann integration uses precisely this method of exhaustion to find the area under general curves.

Unfortunately, not all functions are Riemann-integrable. The standard counter-example is the function defined on [0, 1] by f(x) = 1 if x is rational, and f(x) = 0 otherwise. The infimum of the upper bounds is 1, whereas the supremum of the lower bounds is 0, so we cannot obtain a precise value of the integral.

We can, however, use Cavalieri’s principle to produce a function g with the same area as f, but such that g is Riemann-integrable. In particular, for a general measurable function f, take g to be as follows:

g(x) = supremum of y such that {z | f(z) ≤ y} has Lebesgue measure ≥ x.

Then f and g are Cavalieri-equivalent on a co-countable (untable?) set of values of y, so f and g must have the same area. But g is a monotonically decreasing function, so is therefore integrable. This gives the Lebesgue integral of f. In the case of the indicator function of the rationals, the Lebesgue integral is 0.

Posted in Uncategorized | 1 Comment

Cipher 69: A void

Before this week’s cipher, I have a few late items of news:

• Professor Stephen Hawking has recently committed a Eugenia Cheng, publishing a formula for the perfect penalty shootout.
• There is a biographical movie about Srinivasa Ramanujan, unsurprisingly entitled Ramanujan, currently pending release.
• It is apparently rumoured that someone may have possibly surpassed Arran Fernandez and the protagonist of Nikita Lalwani’s bestseller, Gifted, in terms of premature matriculation, being the youngest undergraduate at Cambridge since William Pitt the Younger.

Posted in Ciphers | 2 Comments

Bounded gaps: one year on…

It’s been just over a year since Zhang’s seminal proof that there exist infinitely many pairs of primes separated by a distance at most H = 70000000. There have been many advancements since then, and the current status is a bound of H = 246:

If we assume the Elliott-Halberstam conjecture, then we obtain the much improved value of k0 = 3, corresponding to a bound of H = 6 given by the following admissible 3-tuple:

* _ _ _ * _ *

Consequently, assuming Elliott-Halberstam, there are either infinitely many pairs of twin primes, cousin primes or sexy primes. (Most probably, there are infinitely many pairs of each.)

Other Polymath projects

The bounded gaps effort is not the only massively collaborative mathematical project in recent history, although it is probably the best known. Some of the others are summarised below:

• Polymath1: This project successfully resulted in a combinatorial proof of the Density Hales-Jewett theorem of Ramsey theory, giving results such as Szemeredi’s theorem for free. This provides improved bounds and is more elementary than the earlier proofs using ergodic theory.
• Polymath4: Is there a deterministic algorithm to find a prime of at least N digits in time polynomial in N? Obviously, there are probabilistic algorithms, such as randomly choosing primes and applying the AKS primality test until we obtain a positive result. A deterministic algorithm would also result from the truth of Cramér’s conjecture.
• Polymath5: The Erdös discrepancy conjecture claims that if we have an infinite sequence where each term is +1 or −1, then we can find arithmetic progressions of the form {d, 2d, 3d, …, kd} whose sum has arbitrarily large absolute value. (Note that anchoring the AP at zero is necessary; otherwise, this would be a trivial corollary of van der Waerden’s theorem, which in turn follows from Polymath1.) Using a SAT solver, it was proved that every sequence of length 1161 or longer must have a zero-anchored arithmetic progression with a sum of ±3.
• Polymath7: The Hot Spots Conjecture states that if we have a non-uniformly heated compact sheet of metal and allow the heat to diffuse, then there will be a time beyond which the hottest point lies on the boundary of the sheet. It has been refuted for certain domains, and proved in others (such as obtuse- and right-angled triangles). This project attempts to prove the conjecture for acute-angled triangles.