# Megaminx IV

Long term readers of this blog will know of my frustration with low-quality megaminxes in years gone by, and even that I chose not to purchase one at the HKnow store in Causeway Bay in Hong Kong when it still existed. But I can now say that I am a proud owner of a QiHeng S Megaminx (stickerless, non-magnetic).

At some point in the past year, I discovered that the physical incarnation of speedcube.com.au was in a Melbourne suburb, in Blackburn North to be precise. So naturally I had to pay it a visit. Fortunately it is located very near to the Koonung Creek Trail, which makes for a pleasant ride to the shop.

As to be expected from the name, this shop specialises in all things speedcubing, at the expense of stocking more exotic puzzles for the serious collector. I finally decided I wanted a working megaminx, and with the rise of speedcubing, surmised (correctly as it turns out), that I would be able to get a reliable one at a speedcube shop. I chose a non-magnetised one since I won’t be trying to speedsolve it, but also walked away with a 3x3x3.

I was by far the oldest customer. How come so many kids are into cubing these days?

In the past, I have claimed that the megaminx is easy. Here is my simple solution.

1. Solve all but one layer and an adjacent corner-edge pair. This is intuitive and much more efficient if when solving a corner piece, you first pair it with an adjacent edge piece and insert them together.

2. Solve the remaining 6 edges. Intuitive. Easier than on the 3x3x3 since turning one face is a 5-cycle of edges, which is an even permutation.

3. Solve the remaining 6 corners using corner 3-cycles.

# An efficient 4x4x4 parity algorithm, intuitively.

The 4x4x4 cube is more complicated to solve than the 3x3x3 due to having a parity problem. If you have never solved a 4x4x4 before, I encourage you to go away and try solving it yourself, then come back to this article later.

The parity I refer to is as follows (speedcubers call this OLL parity): After solving the centres of the cube, look at the 24 edge pieces. If they form an odd permutation, then I say we have a parity problem we need to fix. The reason this is non-trivial is that most/all of the easy to create algorithms that preserve the centres of the cube perform an even permutation of these 24 edges. Odd permutations are possible (in conjunction with performing simultaneously an odd permutation of the indistinguishable centre squares).

I will aim for the following: An odd permutation of the 24 edge pieces, with three of the four layers solved, and all the edge pairs on the last layer preserved. This is for compatibility with common approaches to solving the 4x4x4 – usually only after solving three layers and pairing the edges is it fast to recognise the existence of a parity problem.

Since we have to perform an odd permutation, let’s do that first and perform the move l. (I won’t define the notation but will link to alg.cubing.net so you can see the moves visually).

Our goal now is to solve as much of the cube from this state as possible using even permutations. Instead of thinking of needing to perform a quarter turn of half a cube, it will be more productive to think of us as needing to perform a 4-cycle of 1x2x3 blocks to completely solve the cube.

Now a 4-cycle of these blocks is not happening, but a 3-cycle of these blocks is easy to construct. It is well-known and easy to construct 3-cycles as simple commutators (here’s an example). We can also create block 3-cycles from similar simple processes. For example, here is a 3-cycle of 1x2x3 blocks:

This doesn’t quite permute the three 1x2x3 blocks we’d want (we want to permute three all on the left side of the cube). We can get around that by conjugating by F r. So now we’re at

Let’s look at where we are. Our biggest problems are that we have to solve the two centres on the F and D faces, and re-pair the UF and DF edges.

We will look at the centres first. The usual way to solve centres in this type of position is the simple 4-mover r U2 r’ U2. But look, that move also swaps the edge pairing of exactly two edges! So we look to see if some version of this algorithm in the right direction and right orientation can solve our two problems, and it turns our that we can with [D2, l]. So altogether we now have

l [F2 r: [r’ 3Dw2 r, U2]] [D2, l]

which solves our problem, giving us a parity fix algorithm.

When the cancelling moves are cancelled, it is 15 moves long.

I will not discuss questions of optimising this algorithm for speed.

If one does look online for speed algorithms, then one will quickly come across something like the following (also 15 moves long)

Now that we’ve done our analysis, we can see the same structure in that algorithm, just in a different order. We see setup moves, the block 3-cycle, the 4-move centres solving and a single turn inserted to ensure odd parity.

# Latex in WordPress

To activate Latex support in this blog, I have now activated the QuickLatex plugin. This has solved the problems with vertical alignment of mathematics that previously plagued this blog (only in new posts using QuickLatex, the back catalogue has not been converted).

The plugin webpage linked above shows its usage (for both posts and comments), allowing Latex to be typed natively once the word “latexpage” in square parentheses appears (so no inserting of the word “latex” after a dollar symbol anymore).

# The binary tetrahedral group as a p-adic Galois group.

Let be the binary tetrahedral group. This group appears as the double cover of the group of rotations of the tetrahedron (under ), as a group of units in an appropriate -form of the quaternion group, or as .

Consider a local field of residue characteristic . Now consider the Galois group of a finite Galois extension. It has a large pro- part, together with two cyclic parts corresponding to the tamely ramified part and the unramified part. This structure alone shows that cannot be such a group unless .

Alternatively, every 2-dimensional irreducible representation of the Galois group of a local field of odd residue characteristic is induced, and has no index two subgroups, so again cannot occur as a Galois group when is odd.

So what about when is even? By considering the fixed field of a Sylow-2-subgroup, we see that if appears as a Galois group, then it is the Galois closure of a degree 8 extension.

Now the degree 8 extensions of are finite and number and have all been computed, together with their Galois groups. They can be found at this online database. A quick examination shows that our binary tetrahedral group does not appear.

But it does appear as an inertia group. So is not a Galois group over , but is a Galois group over the unramified quadratic extension of .

# An exceptional isomorphism

We will construct the exceptional isomorphism $S_6\cong Sp_4(\mathbb{F}_2)$.

The group $S_6$ acts on $\mathbb{F}_2^6$ preserving the usual pairing $\langle e_i,e_j\rangle=\delta_{ij}$ where the $e_i$ are the usual basis vectors.

There is an invariant line $L$, the span of $\sum_i e_i$ and an invariant hyperplane $H=\{\sum_i a_ie_i|\sum_i a_i=0\}$. Let $V=H/L$. $S_6$ acts on $V$.

Since $L$ is the radical of the pairing $\langle \cdot,\cdot\rangle$ on $H$, the pairing $\langle \cdot,\cdot\rangle$ descends to a non-degenerate bilinear pairing on $V$. As it is symmetric and we are in characteristic 2, it is automatically skew-symmetric.

The $S_6$-action preserves this pairing, hence we get our desired homomorphism from $S_6$ to $Sp_4(\mathbb{F}_2)$.

To check injectivity, it suffices to show that $(12)$ is not in the kernel, since we know all normal subgroups of $S_6$. Surjectivity then follows by a counting argument, so we get our desired isomorphism.

# Simon Marais Problem Competition 2017

A couple of weeks ago, there was the inaugural Simon Marais Mathematics Competition, a new maths competition for undergraduate students living in the time zones between New Zealand and India inclusive.

The students’ scripts have not yet been marked. As a member of the problem committee, I will be especially interested to see how they did. The questions and solutions can be found on the Simon Marais website. There will be a greater variety of solutions posted some time in November after the scripts have been marked. I will currently permit myself a few brief comments on the problems.

I actually came up with B1, which surprised me! The idea here was to specifically come up with an easy problem. One day I was leafing through some old Olympiad material, and on a sheet of preparatory problems for a maths camp from when I was a student, I saw a problem about classifying configurations of 4 points in the plane such that the sum of the distances from each point to the other points was the same. I wondered to myself what happened in three dimensions and the problem was born.

Problem A4 is expected to be very hard and has an interesting solution which I found and wrote up here. This is similar to an approach to the fundamental theorem of algebra which I believe goes back to Gauss and which I may discuss here if I have time.

As a member of the problem committee, I am always looking out for problem submissions for future competitions and welcome anybody who has what they think might be a suitable problem to submit it (which can be directly to me, or the chair of the committee, via email).

# The medians of a triangle are concurrent

In case anyone reading this does not know, a median is a line connecting a vertex of a triangle to the midpoint of the opposite edge. The theorem is that the three medians of a triangle are concurrent (i.e. they meet in a single point). Here are four proofs.

Proof 1: (Transformation geometry)

Let E and F be the midpoints as shown and let BE and CF intersect at G. Consider the dilation about A with factor 2. It sends E to C, F to B and G to Q (this is the definition of Q). Then EG and CQ are parallel, as are FG and BQ. Thus BGCQ is a parallellogram and the diagonals of a parallelogram bisect each other QED.

Proof 2: (Vectors. Efficient and boring). Write ${\bf a}$, ${\bf b}$ and ${\bf c}$ for A, B and C respectively. Let G be $({\bf a}+{\bf b}+{\bf c})/3$. It is easy then to check that the midpoint D of AB is $({\bf a}+{\bf b})/2$ and that A, D and G are concurrent.

Proof 3: (Why not just prove Ceva’s Theorem)

Ceva’s Theorem states that in the situation shown, AD, BE and CF are concurrent if and only if

$\displaystyle \frac{BD}{DC}\frac{CE}{EA}\frac{AF}{FB}=1.$

To prove this, note that in the case of concurrence

$\displaystyle \frac{BD}{DC}=\frac{|ABG|}{|ACG|}.$

The rest of the proof is routine.

Proof 4: (my favourite) WLOG the triangle is equilateral. Now the statement is obvious (e.g. by symmetry).

Perhaps some elaboration should be made to the WLOG. An affine transformation of $\mathbb{R}^2$ is a map of the form ${\bf{v}}\mapsto A{\bf{v}}+{\bf{b}}$ where $A$ is an invertible matrix and ${\bf{b}}$ is a vector. The affine transformations act transitively on the set of (nondegenerate) triangles and the property of having concurrent medians is clearly invariant under these transformations.

Acknowledgements: Thanks to Inna Lukyanenko for the first proof and tikz files, and to pdftoppm for converting the .pdf output to .png.

# A different proof of the fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every integer can be uniquely written as a product of primes (i.e. $\mathbb{Z}$ is a unique factorisation domain).

The usual proof proceeds through the Euclidean algorithm. Yesterday at lunch I was surprised to learn (thanks to Ole Warnaar) of a different proof bypassing the Euclidean algorithm which I reproduce below. Its primary attraction is its cuteness, as it provides a weaker result than the usual proof (i.e. doesn’t prove that $\mathbb{Z}$ is a Euclidean domain, or even a principal ideal domain).

Suppose that $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ where $p_1,p_2,\ldots,p_k$ are distinct primes. Consider the finite cyclic group $C_n$. It has a composition series where the group $C_{p_i}$ appears $a_i$ times as a simple subquotient (and no other simple factors appear). Therefore by the Jordan-Holder theorem, the primes $p_i$ together with their multiplicities $a_i$ are unique. QED.

# Pi is trancendental

First the rabbit. The introduction of this function is the part which I don’t know how to motivate. Let $f$ be a polynomial and define

$\displaystyle I(z,f)=\int_0^z e^{z-t}f(t)\,dt.$

Integration by parts gives the recursion

$\displaystyle I(z,f)=e^z f(0)-f(z)+I(z,f')$

and therefore we have the formula

$\displaystyle I(z,f)=e^z\sum_{j\geq 0} f^{(j)}(0) - \sum_{j\geq 0}f^{(j)}(z).$

Now suppose (for want of a contradition) that $\pi i \in \overline{\mathbb{Q}}$. Let the set of Galois conjugates of $\pi i$ be $\{a_1,\ldots,a_k\}.$ Then we have $\prod_{i=1}^k (1+e^{a_i})=0$, expand this as $\sum_{J\subset[k]}e^{\sum_{j\in J}a_j}=0$ and rewrite as

$\displaystyle (2^k-d)+\sum_{i=1}^d e^{\theta_i}=0$

where the $\theta_i$ are the nonzero exponents.

Now consider

$\displaystyle \sum_{i=1}^d I(\theta_i,f)=(d-2^k)\sum_{j\geq 0}f^{(j)}(0)-\sum_{j\geq 0}\sum_{i=1}^df^{(j)}(\theta_i)$

Let $N$ be an integer such that $N\pi i$ is an algebraic integer. Let $p$ be a (large) prime and we choose to take

$\displaystyle f(x)=N^{dp}x^{p-1}\prod_{i=1}^d(x-\theta_i)^p\in\mathbb{Z}[x].$

There are absolute constants $A$ and $B$ (independent of $p$) such that

$\displaystyle |\sum_{i=1}^d I(\theta_i,f)|\leq A B^p$

(look at the integral definition of $I(z,f)$ and apply the naive estimate).

Now consider $\sum_{i=1}^d I(\theta_i,f)$. It is a Galois-invariant algebraic integer, hence an integer. We have

$\displaystyle \sum_{i=1}^d I(\theta_i,f)=(d-2^k)f^{(p-1)}(0)+\text{higher order terms}.$

Here higher order means at least $p$ derivatives appearing. Each of these higher order terms is divisible by $p!$, hence by $p$. Since $p$ is prime, for large enough $p$, $\sum_{i=1}^d I(\theta_i,f)$ is not divisible by $p$, hence nonzero.

Now every term is divisible by $(p-1)!$, so we get the lower bound

$\displaystyle |\sum_{i=1}^d I(\theta_i,f)|\geq (p-1)!$

As there are infinitely many primes, we can send choose $p$ large enough to get a contradiction, QED.

# I found the bike racks at Brisbane airport

There are about six of them at the domestic terminal, not under cover, on the ground floor, near the rental cars and the lift to the overpass to the terminals. Here is a map with their location, together with the cycle routes in and out.

As you can see from the map, openstreetmap also knows where these bike racks are.