Complex Projective 4-Space

The usual method of generating the primes below N is to use a prime number sieve, such as the Sieve of Eratosthenes. This requires O(N log log N) operations for a random access machine, but can be reduced to O(N) by refining the algorithm. There is an implementation in Conway’s Game of Life that generates the primes in linear time, O(N), utilising the potential for parallel processing:

[youtube=http://www.youtube.com/watch?v=68nEX5CEmZE]

A more efficient prime number sieve is the Sieve of Atkin. This involves counting the number of solutions to certain quadratic Diophantine equations, and (when optimised) has an asymptotic time complexity of O(N/log log N). An efficient implementation generates all primes below 10^9 in just eight seconds.

Nevertheless, a new prime-generating machine has since been discovered. Bizarrely, it was expected to output natural logs, but instead produces the primes in succession. An online demonstration of the machine is included here. It is estimated that it would claim the EFF prize of 150000 USD for a 100-million-digit prime long before the year 10^10^8.

In 2010, Evangelos Kranakis and Danny Krizanc published an academic paper with a rather bizarre title. The Urinal Problem investigates a particular mathematical model arising from the behaviour of men selecting urinals in a bathroom arrangement. Rather atypical of mathematical publications, one of the figures is a full-colour photograph of a line of urinals:

Figure 1 of The Urinal Problem

One particular model is where each entrant stands at the unoccupied urinal as distant as possible from the existing people. Randall Munroe added the restriction that no two men may stand adjacent to each other, resulting in a rather light-hearted analysis of the subject. Making the additional assumption that the first entrant stands at one extremum, he derived the ultimate packing density as a function of the number of urinals.

Randall Munroe’s graph of packing density against length

Asymptotically, the best packing density is 1/2, and the worst packing density is 1/3.

Continuous model

I decided to consider what would happen in the alternate environment, where discrete urinals are replaced by a continuous trough (in the Netherlands, there is a specific word to refer to this construct, namely ‘pisbak‘). Assuming without loss of generality that the trough is of unit length, people will stand at an enumeration of the dyadic rationals in increasing order of denominator (and, where two dyadics have equal denominator, the ordering is arbitrary).

Extending this to two dimensions (where the trough is replaced with a field*), the behaviour is more interesting. Here’s an animated GIF I prepared earlier, where the colour of a point indicates the minimum distance to a person:

For a circular field, the problem is much more chaotic, and I don’t believe that there is a nice characterisation of which points are occupied. Indeed, it may be influenced by the arbitrary choices of earlier occupants. In principle, we can generalise further to any metric space.

* No, not a ring where all nonzero elements are invertible. (I realise that if I didn’t include this footnote myself, some of you will have commented…)

Line-of-sight considerations

In addition to separation, it is usually desirable not to be making eye contact with fellow occupants. The problem of situating urinals in a bathroom to avoid this resembles a dual of the art gallery problem, which involves placing guards in a polygonal art gallery such that they can view every point. If we want to give n people privacy, it certainly suffices for the room to have 2n edges. For instance, here is a solution to the Privacy Problem for n = 7:

Unfortunately, architects frequently fail to take this into consideration, and actually exacerbate the situation by adding mirrors in bathrooms. For example, Michael Dunn Goekjian (another person with three adjacent unit quaternions in his name, c.f. my IMO report) commented on the poor planning that went into the layout of the bathroom of the Babbage Lecture Theatre, with particular emphasis on the lavatory X orthogonal to the mirror Y:

Nevertheless, even if the entirety of the walls are covered with a reflective surface, it is (amazingly) possible to solve the Privacy Problem. Lionel and Roger Penrose realised that the focal properties of an ellipse can be exploited to achieve this:

I believe it is an open problem as to whether a polygonal room can have this property.

Suppose we have a unit square ABCD. Is it possible to place a point P in the plane of ABCD, such that PA, PB, PC and PD are all rational? It’s not too difficult to show that such a point must necessarily have rational coordinates with respect to the natural choice of axes.

In the latest BMO2 paper, this question was posed with the additional restriction that P must lie on the circle inscribed in the square. This greatly simplifies the problem (not least because the original problem is apparently unsolved!), and it’s quite easy to show that no such configuration exists.

Similarly, if P is constrained to lie on one of the sides of the square, it becomes equivalent to showing that there are no non-trivial rational points on the elliptic curve . This is a considerably more difficult problem (it cannot be bashed by modular arithmetic) than the BMO2 counterpart, yet elliptic curves are understood sufficiently well that questions such as this one can usually be solved.

Euler’s formula famously relates the number of vertices, edges and faces of a polyhedron. Specifically, it gives , where V, E and F are the numbers of vertices, edges and faces, respectively. For example, the dodecahedron has 20 vertices, 30 edges and 12 faces, and can be easily seen to obey Euler’s formula. A proof is obtained by puncturing one of the faces and ‘unfolding’ it into a planar graph, whence you can proceed by induction on the number of vertices and edges.

It does, however, assume that the polyhedron is homeomorphic to a sphere. We can find a counter-example to Euler’s formula, such as this torus:

Here, there are n vertices, n faces and 2n edges. A refinement of Euler’s formula is , where is the Euler characteristic expressed in terms of the genus (number of holes).

Even this refinement of the formula makes an assumption, namely that none of the faces contain holes. For instance, the following polyhedron (composed of two tetrahedra, one of which penetrates the other) has 7 vertices, 15 edges and 8 faces, but a genus of 0, and therefore disobeys Euler’s formula.

John Conway and David Wilson wondered whether or not it would be possible for all faces of a polyhedron to contain holes. They coined the term ‘holyhedron’ to refer to this, even though no explicit examples were known at the time. Two years later, in 1999, Jade Vinson employed a ‘just do it’ construction to synthesise an example. The construction was incredibly fiddly, resulting in a holyhedron with 78585627 faces, which is explained very clearly in Vinson’s paper. John Conway offered a prize of USD for a holyhedron, so this would be worth 12.7 millicents.

A much more reasonable example is a 492-face beast discovered by Don Hatch. It features many interpenetrating tetrahedra and pentagonal pyramids, based around a central dodecahedron.

It was constructed in layers, shown in different colours in the above image. He has included a digraph (directed graph) detailing which layers penetrate the faces of the other layers to achieve the property of being a holyhedron. Eight vertices on the exterior do not penetrate anything; these form the convex hull of the polyhedron.

It’s a well-known fact that the harmonic series (i.e. the sum of the reciprocals of the natural numbers) diverges to infinity. There are at least two reasonably straightforward ways to prove this, the first being the Cauchy condensation test. Essentially, in this case, it involves observing the following inequality:

It can also be upper-bounded by a similar series, leading to the revelation that the series diverges logarithmically. Alternatively, you can obtain the result by comparing with the integral of 1/x. Specifically, the series can be expressed as the integral of a stepped function, trapped between the areas of two hyperbolae (which differ by 1).

Hence, we can deduce that the following limit exists, and is bounded somewhere between 0 and 1:

γ is the Euler-Mascheroni constant, which is roughly 0.577.

Prime harmonic series

If we instead repeat this process with a subset of the natural numbers, the resulting series may converge. For instance, the sum of the reciprocals of the squares, known as ζ(2), converges to π²/6. What about the sum of the reciprocals of the primes? This turns out to diverge, albeit extremely slowly. Euler provided a heuristic argument (it lacks the rigour to be an actual proof) that it diverges at an asymptotic rate of log(log(n)). With a little work, it’s possible to rigorously prove that the sums of reciprocals of primes is bounded below by log(log(n)) − 1:

Indeed, there’s an analogy of the Euler-Mascheroni constant called the Meissel-Mertens constant:

The previous proof demonstrates that M ≥ −1. In fact, our lower bound is quite poor, as M is approximately equal to 0.2615.

Brun’s constant

The sum of the reciprocals of Mersenne primes is obviously convergent, since it can be bounded above by the series 1 + 1/2 + 1/4 + 1/8 + …, which converges to 1. It transpires that the sum of the reciprocals of twin primes also converges (the proof is much more difficult); the limit of this series is Brun’s constant. When computing the twin primes, Professor Thomas Nicely discovered a bug in the floating-point arithmetic of the Pentium processor.

Green-Tao theorem and Erdős’ conjecture

The τ theorem (named after Professors Ben Green and Terry Tao) states that there exist arbitrarily long arithmetic progressions in the prime numbers. For example, a sequence of 26 primes in arithmetic progression is {43142746595714191, 48425980631694091, 53709214667673991, 58992448703653891, 64275682739633791, 69558916775613691, 74842150811593591, 80125384847573491, 85408618883553391, 90691852919533291, 95975086955513191, 101258320991493091, 106541555027472991, 111824789063452891, 117108023099432791, 122391257135412691, 127674491171392591, 132957725207372491, 138240959243352391, 143524193279332291, 148807427315312191, 154090661351292091, 159373895387271991, 164657129423251891, 169940363459231791, 175223597495211691} (sequence A204189 in the OEIS). On the other hand, there are no infinite arithmetic progressions of primes; the proof of this is trivial.

The primes are described as a substantial set, which means that the sum of their reciprocals diverges. Erdős conjectured that the Green-Tao theorem generalises to all substantial sets, offering a prize of 3000 USD for a proof. This conjecture would generalise Szemerédi’s theorem (since all sets of positive lower density are substantial), and therefore van der Waerden’s theorem (since in any k-colouring of the integers, we can find a colour with a lower density at least 1/k). For an explanation of these theorems, together with proofs of some other generalisations, consult the third chapter (Combinatorics II) of MODA.

Generalising further?

In the same way that the Hales-Jewett theorem generalises van der Waerden’s theorem, and that the density analogue of Hales-Jewett extends Szemerédi’s theorem, it seems natural to consider this (conjectural) generalisation of Erdős’ conjecture:

• Suppose we have a set A of natural numbers, such that the sum of the reciprocals of elements of A diverges. Write the elements of A in base n, for n ≥ 2. Then I conjecture that there exists a combinatorial line of length n.

For example, it conjectures the existence of an arithmetic progression of 10 primes, which form a combinatorial line when written in decimal. Problem 51 of Project Euler asks you to find the first partial combinatorial line of 8 primes, and provides an explicit example (56**3) with 7 primes: {56003, 56113, 56333, 56443, 56663, 56773, 56993}. If you can find a combinatorial line of 10 primes, I’ll be impressed.

One way to avoid all combinatorial lines is to take the integers whose decimal expansions do not contain any 9s. This sequence begins {1,2,3,4,5,6,7,8,10,11,12,…}. If the sum of the reciprocals of these integers diverged, then we would have a simple counter-example to my conjecture. However, it is straightforward to prove that the sum of the reciprocals of 9-less integers (the Kempner series) converges; the limit is roughly 22.92. The proof generalises in the obvious way to any combination of radix and digit.