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 | 1 Comment

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

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 | 20 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:

cone-vs-cylinder

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:

cavalieri

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.

dodecagon

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 | 3 Comments