Seven-dimensional cross product

In three dimensions, the familiar cross product is a bilinear function expressible in terms of the Levi-Civita alternating tensor. Specifically, a = b × c can be written as ai = εijk bj ck, which has the following beautiful properties:

  • Bilinearity: a is a linear function of b (when c is fixed), and a linear function of c (when b is fixed);
  • Complete antisymmetry: swapping any two of the indices flips the sign of the tensor;
  • Orthogonality: a is always perpendicular to b and c;
  • Isotropy: the tensor is unchanged when transformed in SO(3).

It should be evident that for orthogonality and isotropy, the cross product can only be defined in three dimensions. In two dimensions or lower, there are insufficiently many dimensions for orthogonality. On the other hand, in four or more dimensions, we can apply a rotation that preserves b and c whilst changing a, so the cross product cannot be well defined. Hence, it only exists in three dimensions (unless it is identically zero, which is stupid and trivial).

However, if we relax the condition of total isotropy, there exists a seven-dimensional analogue of the cross product. It is uniquely determined (up to automorphism of the underlying vector space) by the following conditions:

  • Bilinearity;
  • Complete antisymmetry;
  • Orthogonality.

Even though it doesn’t have full isotropy (i.e. the automorphism group of the tensor is smaller than SO(7)), it still retains a lot of symmetry. The automorphism group is the compact real form of the exceptional Lie group G2.

If we choose the canonical coordinate system, then the components of the tensor can be visualised as a three-dimensional array (where blue and red are +1 and −1, respectively):

7dtensor

The projection shown above highlights the antisymmetry of the tensor — reflecting in an axis causes the colours of the entries to alternate. Note that the position (x, y, z) is non-zero if and only if x, y and z are collinear on (a particular labelling of) the Fano plane.

Quaternions and octonions

With a slight abuse of notation, one can write a quaternion as a sum of a scalar and vector, such as λ + a, where λ is the real part and a is the (three-dimensional) imaginary part. Then, the rule for multiplying quaternions becomes:

  • (λ + a)*(μ + b) = (λμ − a · b) + (λb + μa + a × b)

In fact, if we define the one-dimensional cross product to be identically zero, then this is also the definition of multiplying complex numbers. Using a seven-dimensional cross product, we obtain the rule for multiplying weird eight-dimensional entities called octonions. Whilst quaternions are slightly bad (they’re not commutative), octonions are really bad (they’re non-associative, which means you need to use parentheses in products of three or more octonions)!

There’s a book by John Conway and Derek Smith about quaternions and octonions. Rather informatively, it’s entitled On Quaternions and Octonions.

Split octonions

The (squared) norm of an octonion is defined to be the sum of the squares of its components, just as one would define the norm of a complex number. Equivalently, we can consider it to be the length of an octonion as a vector in eight-dimensional space.

It transpires that the octonions have a more pathological cousin, the split octonions, where four of the coordinates are spacelike and the other four are timelike. In other words, they live in a (4+4)-dimensional Minkowski space. When the (seven-dimensional) subspace of purely imaginary octonions is projectivised (the origin is thrown away and real scalar multiples are associated), we get a beautiful six-dimensional projective space. John Baez and Huerta discovered that this is precisely the space of positions of a spinorial ball rolling on the surface of a projective ball of three times its diameter.

planets

Moreover, lines in this six-dimensional space are defined in a natural way, both in terms of the octonionic representation (as subplanes where all products have a norm of zero) and in terms of the rolling balls (as geodesic trajectories where the smaller ball rolls along a great circle of the larger ball).

And the symmetry group of this six-dimensional projective space? The split form of G2, naturally…

Posted in Uncategorized | Leave a comment

De Bruijn sequences

Given a finite alphabet Σ of size s and an integer n, a de Bruijn sequence is a cyclic string of s^n symbols, such that each n-symbol string over Σ appears exactly once. For example, taking Σ to be an alphabet of four colours and choosing n = 3 gives the following de Bruijn sequence of length 64:

de-bruijn-torus

It is, quite obviously, the shortest (oriented) loop that contains all possible strings of length 3 over an alphabet of 4 symbols. If we take the alphabet to be the four nucleotide bases of DNA, then this loop of 64 base pairs has the following interesting property: it contains all 64 possible DNA codons.

If one were to actually realise this loop of DNA and effect the process of transcription, then a continual periodic string of RNA would be produced, forming at a site which constantly circumnavigates the DNA loop. Due to the serendipity of 3 and 64 being coprime, this would be translated into a period-64 sequence of all possible amino acids.

Another application of de Bruijn sequences is attempting to break into an electronic safe, which opens when the last four digits pressed matches a particular passcode. The naïve approach of trying each passcode in lexicographical order involves 40000 key presses:

00000001000200030004 [...] 99959996999799989999

Much more efficient is the use of a de Bruijn sequence, which (when the first three digits are re-appended to the end to produce a linear, rather than cyclic, string) is only 10003 digits long.

It can be shown that de Bruijn sequences exist for any ordered pair (s, n), and that the number of such sequences is \dfrac{(k!)^{k^{n-1}}}{k^n}. Even more impressive is that the concept generalises to de Bruijn tori, which are known to exist in the square case. For example, here is a 4 \times 4 torus with 2 colours and every possible 2 \times 2 block as a subregion:

de-bruijn-torus2

Permutations instead of tuples

Nathaniel Johnston considers a similar problem, where the shortest linear string containing all permutations of {1, 2, …, n} is desired. Optimal solutions are known for n \leq 4, but larger cases are beyond the capabilities of brute-force exhaustive search.

The analogous problem to the electronic safe-cracking is a situation in which a monk has to ring every permutation of six monastery bells. The usual approach is to perform each permutation in succession by use of the Steinhaus-Johnson-Trotter algorithm. However, this particular monk is very lazy, so decides to employ the suspected optimal solution to reduce his workload from 4320 bells to just 873 (see Sloane’s A180632).

Posted in Uncategorized | Leave a comment

Cipher 38: 60 percent wordsearch

Update: In my blithering ineptitude, I accidentally missed the bottom row off of the cipher. It has now been amended, and should be a 20 × 20 grid:

40-percent-vigenere

The backdrop is a photograph of the Dumbbell Nebula, which I captured over a year ago by remotely controlling a two-metre optical telescope in Hawaii.

Posted in Ciphers | Leave a comment

Further news

As usual, I’ll start this post by mentioning the current state of the bounded gaps between primes project. The current values are k_0 = 720, H = 5414, with an unconfirmed result giving a value of H below 5000. It’s surprising how far these sieve methods are successfully being pushed — significantly below Ben Green’s estimate that 10000 would be the limit.

Anyway, the 54th International Mathematical Olympiad finished a few days ago. There are no prizes for guessing which country came first (China), closely followed by South Korea. The United Kingdom came first in the EU and ninth in the world, which is the best result since 1996. Congratulations go to Geoff Smith for leading the team, Dominic Yeo for acquiring refreshments (and the other things that deputy leaders do), and especially to the six excellent contestants* who, between them, attained two gold medals, three silvers and a bronze. This is an excellent achievement!

* In lexicographical order by surname, they are Andrew Carlotti, Gabriel Gendler, Daniel Hu, Sahl Khan, Warren Li and Matei Mandache. Andrew is now the country’s most prolific IMO contestant, with three gold medals and a bronze. Our other triple gold medallists are John Rickard (c.f. Treefoil) and Simon Norton (co-discoverer of the Harada-Norton sporadic group).

The next impending mathematical Olympiad worthy of mention is the Mathematical Olympiad for Girls (or MOG), which is used for finding the UK EGMO team. I’ll be mentioning it closer to the time, combined in an article with the Miracle Octad Generator (purely on the basis that they have the same acronym). I think that my recommendation that medals and certificates be awarded as opposed to gold stickers on returned scripts has been effected, although if this is not the case and you have been affected by this issue, do not hesitate to contact me.

In other news, Stuart Gascoigne recently overtook Joseph Myers on the cipher-solving leaderboard.

Posted in Uncategorized | Leave a comment

Converting problems into elliptic curves

Several geometric problems and Diophantine equations can be converted into the task of finding rational points on elliptic curves. The canonical example is to determine for which rational numbers n can a right-angled triangle with rational side lengths have an area of n. (The integers with this property are called congruent numbers.)

Before we can proceed, it is helpful to find all pairs of rational numbers (a, b) such that a² + b² = c², where c is a predetermined rational number. Equivalently, we want to find rational points on the circle of radius c, which is reasonably trivial. It is well known that if one root of a quadratic equation with rational coefficients is rational, then so must the other one. In particular, this means that the rational points on the circle are precisely the points for which the line in the following diagram has rational gradient:

stereo

By geometric inversion in the circle with centre (0, c) and radius 2c, it is straightforward to derive that (a,b) = (\dfrac{4qc^2}{q^2+4c^2},\dfrac{cq^2-4c^3}{q^2+4c^2}) and n = \dfrac{2qc^3(q^2-4c^2)}{(q^2+4c^2)^2}. If you plot c and q on the complex projective plane, the resulting surface is a topological torus; it is said to have a genus (number of holes) of 1. This means that algebraic massage can convert it into an elliptic curve. Let’s attempt this. Firstly, we want a polynomial, so the obvious step is to eliminate the denominator:

2qc^3(q^2-4c^2) = n(q^2+4c^2)^2

For this to be in Weierstrass normal form, we want one side of the equation to be a square, and the other side to be a cubic function of a single variable. The right-hand side is almost a square itself, rectifiable by multiplying both sides by n³. Additionally, q and c are equidimensional, so we can do some further manipulation:

16(\dfrac{qn}{2c})(\dfrac{q^2n^2}{4c^2}-n^2)c^6 = n^4(q^2+4c^2)^2

Finally, dividing both sides by (4c³)² gives the beautiful elliptic curve:

y² = x³ − n²x, where x = \dfrac{qn}{2c} and y = \dfrac{n^2(q^2+4c^2)}{4c^3}. It is easy to show that we can express q and c as rational functions of x,y,n, so rational points on this elliptic curve correspond to rational right-angled triangles with area n. Assuming the Birch and Swinnerton-Dyer conjecture, the existence of rational solutions can be verified by a finite calculation, so the congruent numbers are a recursive set. If the conjecture is false, however, then there is no known algorithm for computing the congruent numbers.

Posted in Uncategorized | Leave a comment

Cipher 37: Honeycomb II

As 37 is a centred hexagonal number, I decided to opt for a vaguely hexagonal arrangement:

totalistic

Click to enlarge.

As usual, there is a password-protected solvers’ area.

Posted in Ciphers | Leave a comment

Mathematical Ashes

The competition known as the Mathematical Ashes was created by analogy with the better-known cricketing Ashes, and is an annual competition between Britain and Australia. At the moment, Britain is in the lead, with Australia attempting to reduce the gap. Results should be released in the next 24 hours on Joseph Myers’ website.

For the convenience of being in the propinquity of the IMO location, the Ashes are taking place in Colombia. Last year, concerns were raised as to how difficult it would be to depart Colombia with a suspicious urn of white powder, and whether the airport security would believe some contrived story about a mathematical competition between Britain and Australia.

It transpires that this is not the only hype arising from this year’s competition. There is a website following the competition from an interesting point of view, which has been producing such delightful headlines as ‘Shakira in Ashes row’ (when she had no involvement whatsoever, other than being born in the right place several decades earlier).

Does anyone know who is responsible for this website? The skewed perspective and colloquialism ‘Pom’ is indicative of it being of Antipodal origin, although their esteemed leader Angelo Di Pasquale* would not lower himself to producing tabloid journalism. Hence, one can only assume that it is the opus of one of the members of the Australian team.

Anyway, the latest headline on the website portrays members of the British team as being economical with the truth, substantiating it with quotations**. I assure you that I have known not a single student who attempted this Machiavellian trick, and that the article is a gross travesty.

Footnotes

* Not, as James Cranch was quick to point out, related to the charitable bank robber Pasquale D’Angelo.

** Probably fabricated, since during my time as a student the term ‘cross’ was never used as an intransitive verb to refer to the obliteration of an erroneous proof.

Posted in Uncategorized | Leave a comment

Von Neumann universe

The von Neumann universe V is the hierarchy of all set-theoretic sets. It is itself too large to be a set, and therefore is considered to be a proper class. There’s a very simple systematic construction of the von Neumann universe, beginning with the empty set, V0.

  • V0 = Ø = {}

We then obtain the next stage by taking the power set of the previous stage. They get very large very quickly, but the next four stages are easily manageable. V1 is the set containing the empty set, and V2 is the set containing both the empty set and the set containing the empty set. V0 to V4, inclusive, are given below:

first-four-stages

V5 is the power set of V4, and is too large to embed into this post. Nevertheless, I’ve made a zipped text file (206 kB; decompresses to 8960 kB) containing V5 in all its glory. So, it’s small enough to store as a reasonably sized text file, and when compressed it even fits on a 3½-inch floppy.

V6 is a different story altogether. Whereas the observable universe contains about 10^79 atoms, V6 contains approximately 2.00 \times 10^{19728} sets. So it’s really big. In general, Vn contains 2 \uparrow \uparrow n sets.

Continuing in this way, we get Vn for all positive integers n. Taking their union gives the countably infinite set Vω, which contains all sets expressible as finite strings of curly brackets and commas. More generally, if α is a limit ordinal, then we define Vα to be the union of Vβ for all β < α.

Now that we have the successor and arbitrary limit operations, we can reach arbitrary ordinals in this manner.

Taking the union over all Vα gives V, the von Neumann universe, or ‘collection of all sets’.

Packing problems

Instead of drawing curly brackets and commas, we can represent sets as closed curves, with their elements drawn within. Insisting that we draw them on a grid, with walls and gaps of width 1 (Chebyshev distance), here are diagrams of V0 to V4:

V0-to-V4

The representations of V0 to V3 are definitely optimal. On the other hand, I was somewhat disappointed that I couldn’t quite get V4 to fit in a 75 by 75 square (the overhang increases it to 75 by 79). This suggests a few exercises to the reader:

  • Can we fit V4 in a 75 × 75 square?
  • More generally, for which a, b (of the form 4k + 3, naturally) can we fit V4 in an a × b box? The minimal width is 19.
  • What is the width of the smallest square that can accommodate V5? A very weak upper bound is 20483, and I’m sure that you can do much better (below 15000, probably).
  • Does anyone want to create an image of V5?
Posted in Uncategorized | 8 Comments

Cipher 36: Concube cum cerebro

Despite currently suffering from hay fever, I was able to combine the following attributes into a cipher:

  • The title is in alliterative Latin.
  • The index of the cipher (36) is a perfect square, as is the length of the cipher text (784). Moreover, this is true even when one restrictively interprets ‘perfect square’ as ‘square of a perfect number’, in which case these are the first two perfect squares!
>++++[>++++<-]>[>++>+++>++++>+++++>++++++>+++++++<<<<<<-
]>>>+++.>>+++++++++++++++.-.-------.>++.<------.>++.+.<+
++++++++++.-----------.>-.<++++++++.++++++.-.>-.<<<<<.>>
>>--------.+++++++++.>-.<<<<<.>>>>-----------.+.--.+++++
+.>--.<-.---.>++.<++++.+++++.-------.<<<<.>>>>>++.<+.+.>
-.<<<<<++++++++++++++.--------------.>>>++++.>-.---.<<<<
.>>>>>---.<----.>+++..++++.<++++++++++++++.>-----.<-----
------.<<<<.>>>>+++++.>+.<<<<<.>>>>------.++++++++++++.>
-.<-.---------.>.<<<<<++++++++++++++.--------------.>>++
+++++++.>>----.>++.<++++++++.+++++.<<<<.>>>>-----.>-.<<<
<<.>>>>--.++++++++..-----------.<<<<.>>>>++.+++++++++.>-
.<<<<<.>>>>.-------------.++++.>+++.--.<---.--.>+.<+++++
+++.+++++.-------.<<<<.>>>>>----.++.<++++++++.---------.
-----.+++++++++++++.-----.>++.+++++.<<<<<++++++++++++++.

Enjoy.

Posted in Ciphers | Leave a comment

Generalised TFAE

The abbreviation TFAE (the following are equivalent) is often used in the statement of various theorems. Of course, a completely synonymous phrase would be ‘any one of these implies the other n − 1′. This then admits a natural generalisation to ‘any k of these together imply the other nk‘. We shall refer to these situations as (n,k)-TFAE.

It is obviously possible to construct artificial examples for any k, such as the following set of statements:

  • a = 0
  • b = 0
  • c = 0
  • a + b + … + c = 0

However, these examples are completely boring, so we’ll just concentrate on more interesting examples instead. The case k = 1 is just regular TFAE, so the next thing to try is k = 2, i.e. ‘any two of these imply the others’. One such example is the new Mersenne conjecture, formulated by Bateman, Selfridge and Wagstaff:

Let p be an odd natural number (only interesting when p is prime). Then, any two of these implies the third:

(a) p = 2k ± 1 or p = 4k ± 3
(b) 2p – 1 is a (Mersenne) prime
(c) (2p + 1)/3 is a (Wagstaff) prime

Of course, this is only conjectural, although heuristically it is expected to be true (with the three properties being simultaneously satisfied only by 3, 5, 7, 13, 17, 19, 31, 61 and 127).

These cases of ‘any two conditions imply the third’, or (3,2)-TFAE, are reasonably common. If P and Q are two finite sets, and f is a function with domain P and codomain Q, then any two of the following statements imply the third:

  • f is an injection.
  • f is a surjection.
  • P and Q are of equal cardinality.

Obviously, the case where all statements are true corresponds to f being a bijection. Equally obviously, this does not hold in general if P and Q are allowed to be infinite.

2-tfae

A more interesting example of (n,2)-TFAE, where there are four statements rather than three, is from Euclidean geometry. Suppose we have a pencil of four distinct lines passing through a common point, as shown above. Then, any two of the following statements together imply the other two:

  • Lines A and C are perpendicular.
  • A is an angular bisector of BD.
  • C is an angular bisector of BD.
  • (A, C; B, D) is a harmonic pencil.

I don’t have any other examples of (4,2)-TFAE, or indeed any examples of (n,k)-TFAE with k > 2. Using the ‘comments’ feature below, please post any non-trivial examples of (n,k)-TFAE (k > 1) you can find:

Posted in Uncategorized | Leave a comment