## Miscellaneous news and sphere eversion

Before we begin, there are a few late items of news worth discussing:

• There is a free edition of Wolfram Mathematica for the Raspberry Pi, an increasingly popular versatile low-cost computer. More details are available over at The Aperiodical.
• The first round of the British Mathematical Olympiad has taken place. Marking is scheduled for the forthcoming weekend, and high scores will be published soon after. Until then, you can see the questions on Joseph Myers’ website.
• The TMS Call My Bluff (mentioned during the previous cp4space post) was won by the freshers’ team. They were winning 4-2, and James Munro gave each team a set of tangled Borromean rings as a tie-breaker (quite literally!). The non-freshers won the tie-breaker, increasing their score to 4-3. Many thanks to all who participated; it was a pleasure to host the event (and not merely because I was entitled to an excess of mince pies and port!).
• You may have noticed the recent Diwali-themed cp4space banner (thanks, by the way, to the CUHCS committee for organising an awesome celebration!). This will soon be replaced with a Saturnalia banner, then a Christmas one, and ultimately the New Year banner. Since cp4space is over a year old, these are very re-usable.

Anyway, you’re probably eagerly anticipating another cp4space article, so here goes:

### Sphere eversion

Suppose we have a circle in the plane, and wish to transform it into its reflection by a homotopy (continuous deformation). Moreover, at every point in time, the curve must be an immersion of the circle: it is allowed to smoothly self-intersect, but cannot have any cusps or singularities. Can the transformation be done?

The answer is no: we can approximate such a differentiable map by a smooth one. Then, the total curvature must be preserved during the homotopy, whereas a clockwise circle and anticlockwise circle have opposite total curvatures.

However, for a sphere in three-dimensional space, this proof fails and, remarkably, it is actually possible to evert a sphere. There’s a video explaining the problem and briefly demonstrating the solution discovered by Bill Thurston, who proved that it is possible to perturb an arbitrary homotopy to remove any singularities.

Another solution is symmetric with respect to time, with the half-way model being the Morin surface. If we conjugate a rotation of the Morin surface by 90° with a homotopy transforming a sphere into a Morin surface, then we get the complete sphere eversion. This is more ad hoc than Thurston’s corrugations, and does not generalise easily to more complicated surfaces.

The aforementioned Morin, who is a retired topologist, was blind from the age of six; despite this, he was able to not only find an explicit solution to sphere eversion, but also discover the first parametrisation of Boy’s surface, an immersion of the real projective plane.

Since the real projective plane can be described as a sphere where antipodal points are identified, we can deduce that Boy’s surface has an Euler characteristic of 1. It is also non-orientable, a property it shares with the better-known Klein bottle (which has Euler characteristic 0). Interestingly, the name of the Klein bottle and its common realisation as a bottle with its neck re-entering through a hole and connecting to the base are the result of a German mistranslation.

A very impressive theorem states that any connected compact surface can be identified uniquely up to homeomorphism by the Euler characteristic, orientability and number of boundary components. Hence, they can be described as connected sums of projective planes (‘crosscaps’), tori (‘handles’) and closed discs (‘holes’).

## Brouwer’s fixed-point theorem

Many theorems in analysis have combinatorial analogues, which turn out to be equivalent (in the sense that one can be derived from the other, and vice-versa, using significantly less maths than is necessary to prove either from first principles). A particularly useful theorem is Brouwer’s fixed-point theorem, which can be proved from its combinatorial discretisation, Sperner’s lemma.

Sperner’s lemma, not to be confused with the similarly-named theorem generalised by Hunter as mentioned in my earlier article about punting in clearings of arbitrarily small Lebesgue measure, is concerned with colouring vertices in a simplicial subdivision of a simplex. In two dimensions, we take an equilateral triangle and cut it into smaller triangles, like so:

We colour each of the vertices with one of three colours (or n + 1 for the n-dimensional version), such that all of the vertices of the original triangle (or simplex) are different colours. Also, if a vertex occurs on the boundary of the simplex, then it must be coloured with the same colour as one of the vertices of the facet in which it resides. (So, for example, any vertices on the bottom edge of the triangle above must be either blue or yellow.)

Then, Sperner’s lemma states that the number of triangles (or simplices) in the subdivision whose vertices are distinct colours (highlighted in grey in the diagram above) is odd. Crucially, that means that there must be at least one such simplex.

In one dimension, the lemma is completely trivial to prove. It states that if we have a finite sequence of vertices coloured red or blue, such that the leftmost vertex is red and the rightmost vertex is blue, then there are an odd number of pairs of adjacent differently-coloured vertices. For instance, the following diagram has five such edges, highlighted in yellow:

Proving Sperner’s lemma involves inducting on the number of dimensions. For instance, the two-dimensional statement can be deduced from the (trivial) one-dimensional statement. We consider the triangulation to be drawn on the surface of a sphere (so the large triangle also constitutes a triangle), and form a subgraph of the dual polyhedron by replacing each triangle with a vertex and connect vertices corresponding to triangles sharing an edge whose endpoints are (red, blue). Now, by Sperner’s lemma in one dimension, the big triangle has odd degree. Hence, by the handshaking lemma, we can find another triangle with odd degree, which must correspond to a triangle where all vertices are differently coloured.

As well as its use in proving Brouwer’s fixed point theorem (mentioned below), Sperner’s lemma is involved in the proof of Monsky’s theorem, that we cannot dissect the unit square into an odd number of triangles of equal area. The proof is reasonably short, but amazingly ingenious. I very much recommend reading it.

### Analytical analogue

We aim to prove Brouwer’s fixed point theorem, which states that any continuous function from the closed n-ball to itself must necessarily have a fixed point. An equivalent problem is to show that there is no continuous function f from the closed n-ball to its boundary S such that f restricted to S is the identity function (such an f is called a continuous retraction).

We shall demonstrate this for simplicial subdivisions of regular simplices, which are homeomorphic to balls, and intend to show that any continuous function f sending vertices to vertices (a simplicial map) that is the identity when restricted to the boundary must send one of the simplices in the subdivision to the big simplex.

In particular, let the vertices of the big simplex be {v_0, v_1, v_2, …, v_n}. Then we give a generic vertex w the colour i if f(w) is closer to v_i than any other v_j. After taking a deep breath, we realise that any continuous retraction must violate Sperner’s lemma, thus establishing that continuous retractions do not exist for simplicial subdivisions of regular simplices. And since any continuous function can be approximated by considering its effect on a sequence of progressively more refined simplicial complexes, we are done.

The special case of Brouwer’s fixed point theorem applied to homeomorphisms in three dimensions has a nice physical interpretation. Suppose we have a volume of pumpkin velouté in a glass vase, and stir it crazily in a continuous way. Then the fixed point theorem states that somewhere, a molecule of the velouté is in the same place whence it began.

### Midsummer House

Speaking of pumpkin velouté, that was, when punctuated with a la grecque mushrooms and Parmesan gnocchi, the first of eleven courses in a most delightful meal I enjoyed at Midsummer House on Thursday evening. Ordinarily, cp4space does not usually give reviews of double-Michelin-starred restaurants in articles about combinatorial proofs of analytical theorems, but this time I shall make an exception.

Not only was the food incomparably excellent, but also the atmosphere was absolutely perfect. We were seated on two extraordinarily comfortable chairs in the spacious solarium of a quaint Victorian villa overlooking the Cam. The ambient illumination was provided by contemporary candelabra situated around the boundary of the room, providing a warming glow on this late November evening.

Before the amazing dinner began, we were given champagne, canapés* and condiments, the latter of which had, in the case of the other person with whom I was dining, an unusually overwhelming affinity for the table cloth. Fortunately, its act of rebellion was expertly rectified by the means of a supplementary table cloth provided after the course of pumpkin velouté, when its disobedience became known to the brilliantly professional staff.

* Miniature cheese scones and suchlike. I would have added this in parentheses, but decided that a footnote allowed me to do so without interrupting the alliteration.

The second course encompassed mackerel tartare, chervil, fennel and passion fruit, arranged in an aesthetically pleasing symmetrical configuration. This was accompanied by the first of a flight of wines designed to perfectly complement the exquisite dishes.

This was followed by great confusion when a large metal trolley arrived; we were assured that the explanation as to its imposing presence would become apparent in the immediate future. Due to unbridled inquisitiveness, I was compelled to consult the menu to deduce its purpose in life, correctly inferring that it harboured the ‘open coals’ on which the beetroot was to be cooked.

Unsurprisingly, the beetroot was extremely flavoursome, and by far the best beetroot I had ever had the fortune to sample. Indeed, this statement would remain true if ‘beetroot’ were to be replaced by many of the other culinary delights on the menu. Including the course of sautéed scallop, celeriac and truffle. The celeriac was arranged in alternating layers of parallel lines, forming a precise Cartesian grid when viewed from above.

According to the menu, the next course comprised roast quail, shallot purée, grapes, celery and sour dough, positioned on various strata of an interesting bowl, the structure of which was analogous to the discrete energy levels occupied by an electron in a hydrogen atom. This was accompanied by a pleasant surprise, namely the delicacy of quail’s eggs. Unlike most eggs, which are conventionally and eponymously ovoid*, these were spherical. The interior was a luscious yolk.

* The most common explanation for the deviation from a sphere or prolate spheroid is so that, when rolled, the egg travels in a closed path rather than escaping arbitrarily far from the origin and falling from the bird’s nest; this presents an evolutionary advantage.

For the following course, we had a choice between bass and monkfish, and decided upon the latter on the basis that I was already accustomed to the taste of bass. When asked what monkfish was, and due to the temporary cognitive modification that results from having consumed considerably more wine than my opponent, I bluffed with total conviction that they are marine animals, which live totally detached lives in monasteries (and in the immortal words of Meat Loaf, two out of three ain’t bad). She was not fooled by this ruse.

I distinctly remember quince appearing on the menu, as I was asked to describe it and quite satisfyingly was able to respond with ‘a fruit with botanical name Cydonia oblonga‘. (The reason for knowing the Linnaean name of a quince is another story, involving a friend of mine called Quincy, and is far too tangential to describe here.)

The next course was a pousse café, a delicious combination of several liquids of distinct densities, which formed strata in a hemispherical receptacle atop a glass vessel. The uppermost layer, which was delightfully creamy, was peppered with fragmented mint leaves. This was followed by a range of artisanal cheeses.

The penultimate course was an indescribably delectable dessert of lemon posset, lemon espuma and blueberries. In fact, it was so amazingly orgasmically excellent that it would be assigned some non-recursive transfinite ordinal on Vishal Patil’s famous dessert quality scale, which hitherto only ranged from 0 to 10.

The eleventh and final course included caramel, chocolate and chestnuts (ooh, another triple alliteration!), providing an ideal culmination for this fabulous gastronomic experience. It was accompanied by a sweet dessert wine, the seventh of the glasses in the flight of wines, which complemented the course perfectly.

At the end of the meal, which was over three hours of absolute Elysium, we spent a rather long time exploring the balcony, overlooking the river (which would have been moonlit had I had the foresight to ensure that the evening coincided with the correct lunar phase), and enjoying the satisfyingly secluded gardens of this Victorian villa, until ultimately retreating into the Fellows’ Garden of Trinity College…

So, yes, I thoroughly recommend this splendid restaurant. The Empress of TMAS described it as:

‘The nicest forfeit I’ve ever been on’

(Specifically, she agreed to do absolutely anything in return for being removed from the freshers’ team for the Trinity Mathematical Society Call My Bluff — which you should definitely attend on Monday 2nd December — and I decided that this would be appropriately awesome.)

### Borsuk-Ulam and Tucker’s lemma

Returning from that rather brief aside, there are other examples of theorems in analysis with combinatorial counterparts. In particular, the Borsuk-Ulam theorem (mentioned in Desert Island Theorems) has Tucker’s lemma as its discrete version.

## Crash course in Gaussian integers

Yesterday, I attended the UKMT mentoring conference in Murray Edwards College (affectionately abbreviated to ‘Medwards’), which mainly consisted of an excellent dinner in the Fellows’ dining room and informal discussion about various topics. Speaking of mentoring, I recently prepared for one of my mentees a crash course in the application of Gaussian integers to solving certain olympiad-style Diophantine equations.

What follows is an almost verbatim regurgitation of that e-mail.

### Brief introduction

So, basically a Gaussian integer is a complex number of the form a + bi, where a and b are both integers. When plotted in the complex plane, they form a square lattice, as shown in the left-hand diagram below.

The hexagonal lattice of blue points is the ring of Eisenstein integers, which shares many of the same interesting properties as the Gaussian integers. Now, the most important fact about Gaussian integers is this:

Gaussian integers are a Unique Factorisation Domain.

The ordinary integers are also a Unique Factorisation Domain, as I’ll explain below.

### Unique factorisation domains

Basically, the elements of $\mathbb{Z}$ (the ring of integers) can be categorised as follows:

• Zero: 0
• Units: +1 and -1
• Irreducibles: +2, -2, +3, -3, +5, -5, +7, -7, +11, -11, …
• Composite numbers: +4, -4, +6, -6, +8, -8, +9, -9, …

Units are defined as elements whose reciprocals also belong to the ring. In particular, every non-zero element in a field is a unit. Irreducibles are defined to be elements that cannot be expressed as a product of two non-units; everything else is composite.

Now, we define a prime to be a number p such that if p|ab, then p|a or p|b. It’s straightforward to show logically that every prime must be an irreducible. It’s very non-trivial to show that the converse holds (that all irreducibles are primes), and there are rings in which this is not the case, such as $\mathbb{Z}[\sqrt{-3}]$. But for the integers, this is true, because they form a Principal Ideal Domain.

The integers are also a Unique Factorisation Domain (this follows from the property that all irreducibles are primes), which essentially means that the Fundamental Theorem of Arithmetic holds. Specifically:

Every integer can be uniquely expressed as a product of irreducibles, up to reordering and multiplication by units.

A proof of this from the prime property is given in the bottom-right corner of the second page of this GRM revision sheet I prepared earlier. Anyway, now that I’ve described these concepts in terms of the ordinary integers, I’ll now explain the Gaussian integers.

### The Gaussian integers

The Gaussian integers, written Z[sqrt(-1)], also form a PID (hence a UFD), so we have the nice property that all irreducibles are primes. Firstly, we need to identify which elements are units; in this case, they are +1, -1, +i and -i.

Note that the number 2 is not a prime in the Gaussian integers, since (1 + i)(1 – i) = 2, and neither 1 + i nor 1 – i is a unit. 1 + i and 1 – i are irreducibles (and called `associates’ since they differ only by multiplication by a unit, analogous to the irreducibles +3 and -3 in the ordinary integers). In fact, we can show the following:

A positive integer is a Gaussian prime if and only if it is prime (as an ordinary integer) of the form p = 4k + 3.

One direction is easy to prove; p cannot be divisible by any integers >= 2 (by primality), so we need to show that it can’t be expressed as the product of two (complex conjugate) Gaussians, p = (a + bi)(a – bi) = a^2 + b^2. But p is congruent to 3 mod 4, so is not the sum of two squares.

In the other direction, a prime of the form p = 4k + 1 can be expressed of the form a^2 + b^2 = (a + bi)(a – bi), so factorises over the Gaussians and is therefore not a Gaussian primes. There’s a nice proof of this based on Wilson’s theorem, and relying on the notion of Gaussian integers.

It might be informative for you to see what the Gaussian primes look like. Here’s a lovely picture by David Eppstein:

The Gaussian primes are shown as white islands. This particular image is concerned with the ‘Gaussian moat’ (open) problem, which Imre Leader happened to mention to me whilst on a train from Oxford:

Suppose a grasshopper begins at the origin, and can jump to any Gaussian prime within a radius of R. If we choose R sufficiently large at the beginning, is it possible for the grasshopper to escape to infinity?

It has been shown that R = 5 is not sufficient.

### Applying Gaussian integers to IMO-style Diophantine equations

Anyway, I guess I should apply this technique to solving an IMO-style problem.

Find all integer solutions to x^2 + 4 = y^3

If that plus had instead been a minus, then you could have easily factorised the left-hand side over the integers. But if we consider factorisations over the Gaussian integers instead, then we get the following:

(x + 2i)(x – 2i) = y^3

The greatest common divisor of x + 2i and x – 2i divides 4, so no primes (with the exception of 1 + i and its associates) can divide both x + 2i and x – 2i. Note that the left-hand side and right-hand side, when fully factorised into primes, must be the same (as the Gaussians are a UFD). Paying particularly careful attention to the prime 1 + i and its associates, we can deduce that x + 2i and x – 2i must be perfect cubes over the Gaussians!

x + 2i = (a + bi)^3 = (a^3 – 3ab^2) + (3a^2b – b^3)i

Hence, equating real and imaginary parts, we get x = a^3 – 3ab^2 and 2 = (3a^2 – b^2)b. The second of these is easy to solve, noting that b must be in the set {-2, -1, +1, +2} (by virtue of dividing 2), leading to the following solutions:

(a,b) = (±1, 1) or (±1, -2)

Substituting back into x = a^3 – 3ab^2, this gives the solutions x = ±2 and x = ±11, respectively, leading to the following integer solutions:

• 2² + 4 = 2³
• 11² + 4 = 5³

and no others.

### Miscellaneous exercises

So, you’ve now seen how one can use “Gaussians form a UFD” to kill an otherwise difficult Diophantine equation. There are many other useful UFDs, such as Z[sqrt(-2)] — that is to say numbers of the form a + b sqrt(-2), where a and b are integers. Here are a few questions concerned with that particular UFD:

1. Identify the units of Z[sqrt(-2)].
2. Give examples of irreducible and composite numbers in Z[sqrt(-2)].
3. Find all integer solutions to x^2 + 2 = y^3.

The Eisenstein integers are also pretty awesome (and a PID). They’re numbers of the form a + bω, where ω = (-1/2 + sqrt(3) i/2) is a complex cube-root of unity. When plotted on the complex plane, they form a nice hexagonal lattice, as shown in the diagram nearer the beginning of this article.

1. What are the units in the Eisenstein integers, Z[ω]?

(You can look at the Wikipedia page on Eisenstein integers if you want to understand them better, but the ‘Properties’ section gives a spoiler to question 4.)

There are also rings that don’t form unique factorisation domains. Here’s an example:

1. In Z[sqrt(-5)] (i.e. numbers of the form a + b sqrt(-5), where a and b are integers), find a number that is expressible as a product of irreducibles in more than one way.

Hence, Z[sqrt(-5)] is not particularly useful for solving problems, since the Fundamental Theorem of Arithmetic does not carry over. The Stark-Heegner theorem states that the only imaginary quadratic fields where the Fundamental Theorem of Arithmetic applies to the integral elements are Q[sqrt(-n)] for n = 1, 2, 3, 7, 11, 19, 43, 67, and 163.

Posted in Uncategorized | 4 Comments

## Bounded gaps update

A few months ago, Yitang Zhang announced that there are infinitely many pairs of primes, separated by a distance no more than 70000000. This initiated an extensive collaborative effort (known as polymath8) to reduce this bound by optimising different parts of the proof, until eventually reaching a bound of about 5000. This seemed to be the limit of sieve methods, and interest in this area dried up slightly.

However, recently Terry Tao and James Maynard independently developed a new method (also exploiting short admissible k0-tuples), reducing the bound to 600. This, whilst being much closer to the conjectured bound of 2, is not the most exciting result proved by Tao and Maynard. Indeed, they have shown that for any m, we can find H(m) such that there exist infinitely many intervals of width H(m) containing m + 1 primes.

The research is detailed in Andrew Granville’s paper on the topic.

## Hearing the shape of a drum

(There appears to be a recent week-long awkward silence on cp4space, partially due to the end of Season II of ciphers. Here’s an attempt to rectify it.)

Suppose we have a square drum, consisting of a membrane fixed at its perimeter. The membrane vibrates according to the wave equation, which is the following partial differential equation:

$\nabla^2 u = \dfrac{\partial^2 u}{\partial^2 t}$

The Laplacian ∇²u gives the sum of second partial derivatives of the amplitude u with respect to the x and y axes. (More generally, if the square membrane is replaced by the closure of a different manifold, the Laplacian is the sum of second partial derivatives with respect to an orthonormal basis of tangent vectors.)

Eigenfunctions of the Laplacian correspond to steady states of the wave equation, known as normal modes. The simplest case is a one-dimensional vibrating string, where the normal modes are stationary sinusoidal waves with an integral number of half-periods along the length of the string. In the animation below, the first three modes are shown, together with the arithmetic mean of the first and third (which is also a solution by linearity, but not an eigenfunction therefore not a normal mode):

The associated eigenvalues form the spectrum of the drum, about which we can deduce certain properties of the drum. For example, Hermann Weyl, whom you may recognise from such things as Weyl groups and Weyl vectors, discovered a formula for the area (or volume, depending on the dimension of the drum) of the drum based on the asymptotic growth of the eigenvalues.

Specifically, if d is the dimension of the drum and N(R) counts the number of eigenvalues less than R, the volume is given by:

Hence, we can determine the size of a drum simply by the spectrum of eigenvalues. Additionally, circular drums have different eigenfunctions (based on Bessel functions) from square drums, and the associated spectrum of eigenvalues is also different. Consequently, basic facts about the shape of the drum can also be deduced. This motivated the following question by Mark Kac, whom you may recognise from such things as Kac-Moody algebras:

Can the shape of a drum be determined by the eigenvalues of the Laplacian?

### Milnor’s 16-dimensional toroidal drums

You may want to read my earlier article about the Leech lattice, if you’re not acquainted with lattices (geometric lattices, not posets). Alternatively, you could acquire a copy of Sphere Packings, Lattices and Groups.

Recall that the eight-dimensional E8 lattice is defined to be the set of all points in $\mathbb{R}^8$ with the following properties:

• Either all coordinates are integers or all coordinates are half-integers;
• The sum of the coordinates is an even integer.

The sixteen-dimensional even unimodular lattice D16+ is constructed in precisely the same way, but in $\mathbb{R}^{16}$. We can obtain another sixteen-dimensional even unimodular lattice, E8², by taking the Cartesian product of the E8 lattice with itself. D16+ and E8² are distinct lattices, but share many properties (such as the same theta series).

Milnor took the quotient of 16-dimensional Euclidean space by each of these lattices, producing two distinct tori with the same set of eigenvalues, and therefore answering Kac’s question in the negative. It would be nice to have an example in two dimensions, as this could be realised as an actual physical drum*.

* Actually, these 16-dimensional quotients of Euclidean space by even unimodular lattices have applications in theoretical physics, where they underpin certain string theories. But a two-dimensional example would still be nice.

### Two-dimensional drums

It took a long time (until 1992) before a pair of indistinguishable drums was discovered in the plane. The original example by Gordon, Webb and Wolpert was quite sophisticated, so we shall instead exhibit a simpler example by Buser, Doyle, Semmler and Conway. Intriguingly, this involves constructing a pair of identical (enantiomorphic) drums in hyperbolic space, which are then ‘flattened out’ into two distinct Euclidean drums with the same spectrum.

These hyperbolic drums are two distinct orbifolds for the *424242 hyperbolic symmetry group, which are two distinct index-7 covers of the triangular orbifold for the *444 group. If we find the intersection of all *424242 groups, we obtain an index-168 normal subgroup I of the full *444 symmetry group, with quotient isomorphic to PSL(2,7). The two *424242 groups, when quotiented by I, give two non-conjugate index-7 subgroups of PSL(2,7). These groups are isospectral, which means that the corresponding Euclidean drums (obtained by connecting seven copies of an acute-angled scalene triangle in the natural way) are also isospectral (by a theorem of Sunada).

Using a similar approach, Conway and Doyle found two ‘peacocks’, which are drums which vibrate in the same way when hit at a particular node. This is stricter than having merely the same eigenvalues:

The nodes in question are the obvious ones where six triangles (whose disjoint union is an equilateral triangle) meet.

Posted in Uncategorized | 5 Comments

## Quantum logic gates

You are probably aware of classical logic gates, such as the Boolean AND and OR gates. The input(s) and output(s) of a logic gate take values in the set {0, 1}, usually identified with ‘false’ and ‘true’, respectively.

One example with multiple inputs and outputs is the full adder, so called because of its ability to perform binary addition, which has three inputs (A, B, C) and two outputs (S, C’). It can be represented by a truth table, which gives the values of S and C’ given any combination of A, B, C:

Thinking of this as a function from {0, 1}^3 to {0, 1}^2, we can also represent this as a binary matrix with eight columns and four rows, where every column contains a single ’1′. This matrix is particularly interesting when it is a permutation matrix, corresponding to a bijective function. (Of course, this is only possible when the logic gate has equally many inputs and outputs.) These logic gates are known as reversible logic gates. It is a remarkable fact that reversible gates can perform any classical computation, and that there is a three-input universal gate, namely the Fredkin gate. This has three inputs, A, B and C, and three outputs, A’, B’, C’, with the following definition:

(A’, B’, C’) = (A, B, C) if C = 0, and (A’, B’, C’) = (B, A, C) if C = 1.

Anyway, if we generalise the definition of a logic gate to include any unitary matrix, rather than merely permutation matrices, then we obtain logic gates capable of creating a quantum superposition of outputs. For instance, the Hadamard gate has one input and one output, and corresponds to the following matrix:

Another example is the controlled phase gate, which is a diagonal matrix with entries $(1, 1, 1, e^{i \theta})$. Conditional on the first qubit (quantum bit) being in state |1›, this rotates the Bloch sphere (space of possible states, which is isomorphic to the complex projective line or Riemann sphere) of the second qubit. It was used by Peter Shor to construct a circuit of logic gates capable of applying the quantum Fourier transform.

### Quantum computing

The primary interest in quantum logic gates derives from the fact that they can actually be implemented as physical systems, relying on quantum-mechanical phenomena such as quantum entanglement and the ability for the system to occupy a superposition of states. Certain problems have known solutions in probabilistic polynomial time with quantum computing, but no known probabilistic polynomial time solutions with classical computing. These include the problems of integer factorisation, discrete logarithm and its counterpart over elliptic curves. All of these are solved in cubic time by Shor’s algorithm.

At the moment, quantum computing is still very much in its infancy. Shor’s algorithm has indeed been implemented, but the largest number to be factored in this way was 21 (until recently, the record was 15). As technology improves, quantum computers executing Shor’s algorithm could considerably compromise RSA cryptography and elliptic curve cryptography. Indeed, I’m not sure whether there is a known public-key cryptosystem that isn’t known to have a polynomial-time quantum attack.

Posted in Uncategorized | 4 Comments

## Yf and only Yf?

There are plenty of triangle centres. One of the lesser-known triangle centres is Kimberling’s X(174), the Yff centre of congruence. It can be defined by considering lines known as isoscelisers, which are lines perpendicular to the angular bisectors of the triangle. If we’re careful, then they can intersect in such a way that three of the triangles formed (by an edge of the triangle and the isoscelisers of the two adjacent vertices) are congruent. This gives a degree of freedom:

The Yff central triangle is the case where the triangle formed by the three isoscelisers (red) is also congruent to the other three. When this triangle vanishes, we obtain the Yff centre of congruence. Apparently they’re named after their discoverer, Peter Yff, who was responsible for discovering several other triangle centres.

In particular, he rediscovered the second Morley centre. Morley’s theorem is quite a subtle result in Euclidean geometry, not least because the points concerned cannot be constructed by Euclidean methods. More precisely, they lie outside the field containing the vertices of the triangle and closed under the operation of taking geometric means. Anyway, the statement of the theorem is as follows:

Consider a triangle ABC. We form the point A’ by letting the angle trisector of ABC (closest to BC) meet the angle trisector of BCA (closest to BC). We similarly define B’ and C’. Then A’B'C’ is an equilateral triangle.

This is called the first Morley triangle. I seem to recall that if you take a cardioid inscribed within ABC, then its centre will lie on the perimeter of A’B'C’, and indeed the perimeter of A’B'C’ is the locus of possible centres. There’s a paper exploring this property and its relation to certain interesting cubics* in the plane of the triangle.

* You’re probably familiar with ‘interesting points’ (namely triangle centres), ‘interesting lines’ (such as the Euler line) and ‘interesting circles’ (the incircle, circumcircle, Euler-Apollonius lollipop etc.). In the same fashion, there are conics, cubics and higher-order algebraic curves passing through plenty of triangle centres.

Anyway, if we chose the other two angle bisectors and joined them, we would get a point A” opposite A’. Then, the triangle A”B”C” is also equilateral (it follows from the fact that, algebraically, it is defined in precisely the same way as the first Morley triangle), and called the second Morley triangle.

It can be shown that ABC, A’B'C’ and A”B”C” are in pairwise perspective (Desargues-style!), so we obtain three more points, P, Q and R, as perspectors. Taking these twelve points together with the nine lines of perspective and three of the original angle trisectors gives a self-dual projective configuration of 12 points and 12 lines discovered by Zacharias.

But then we can form its incidence graph! This is a bipartite symmetric cubic (3-regular) graph known as the Nauru graph. The etymology of this graph is derived from its drawing as a generalised Petersen graph, whose interior star polygon resembles the 12-pointed star on the flag of Nauru:

So, I guess it’s appropriate to explain the labels and coloured edges. We can think of this as the Cayley graph of the group S4 (with generators corresponding to transpositions (1 2), (1 3) and (1 4)), or as the map of admissible moves in a corresponding groupoid puzzle. I’ll describe the latter. We have four pedestals, each capable of accommodating precisely one Ferrero Rocher, of which we have one of each of three varieties. Then, on each move we can select a Ferrero Rocher and move it to the unoccupied pedestal. The graph of positions where edges correspond to legal moves is then the Nauru graph.

The Nauru graph has many other interesting properties such as symmetrical embeddings on a torus. David Eppstein investigated how these aspects are connected, and developed a theory of xyz graphs (basically cubic graphs that can be embedded as (possibly self-intersecting) orthogonal polyhedra). He has a series of articles on this topic, which, despite being on the same website, do not appear to share an index page. Hence, I’ll link to them here in chronological order:

1. Inverted permutohedron, exhibiting the first example of a xyz graph.
2. A projective plane in a 3d grid, which defines the concept of an xyz graph and explores a particular example, which is shown (by the easy classification of surfaces according to orientability and Euler characteristic) to be homeomorphic to the real projective plane.
3. Topology of xyz graphs, which expands on the previous ideas and realises all such compact surfaces (which can be formed by gluing finitely many handles and crosscaps to a sphere, as shown in The Symmetries of Things) as surfaces of immersions of xyz graphs.
4. 3-colouring and xyz graphs, which gives (rather beautiful) necessary and sufficient conditions for one to be able to convert a graph drawn on an abstract topological surface back into an immersion of an xyz graph, rather than the usual reverse process.
5. st-orientation and xyz graph recognition, which mentions the theory behind an exponential-time algorithm for recognising xyz graphs.
6. Ambiguously xyz, which exhibits an xyz graph that can be immersed in two distinct ways. It is proposed that this could be used as a method for reducing NP problems into the problem of determining whether a graph is an xyz graph, thereby strongly suggesting that there are no polynomial-time to perform xyz graph recognition.

Roughly at this point, he published the material in the form of a paper. However, later posts appeared, particularly involved with cubic symmetric xyz graphs (such as the Nauru graph itself). Indeed, we have:

1. Cubic symmetric xyz graphs, which is fairly self-explanatory.
2. More on cubic symmetric graphs.
3. The many faces of the Nauru graph, investigating embeddings on hyperbolic surfaces.
4. Not the Nauru graph.
Posted in Uncategorized | 3 Comments