Ic eom mare þonne þes middangeard

læsse þonne hondwyrm leohtre þonne mona

swiftre þonne suna sæs me sind ealle

flodas on fæðmum on þes foldan bearm

grene wongas grundum ic hrine

helle underhnige heofonas oferstige

wuldres eðel wide ræce

ofer engla eard eorðan gefylle

ealne middangeard ond merestreamas

side mid me sylfum saga hwæt ic hatte

# Month: April 2020

## Puzzle and meta-puzzle: Factorisation — SOLUTION

In an earlier post I posed the following problem:

Find the prime factorization of .

**Solution.**

Write . As a first attempt we shall ask some straightforward questions:

- Is even? No.
- Is divisible by ? We use the “
*sum the digits*” trick, and find that — yes — is divisible by , but not divisible by . - Is divisible by ? No.

Etc. We can directly calculate for other small primes, and if we push on we will find a factor of .

Taking out these factors, namely and , we are still left with a large number:

How should we proceed? We seek a more systematic approach, or at least some sort of shortcut.

Fortunately, in this special case, such a short cut is available: we exploit the repetition of various strings of digits in the base- representation of . Let and let . Then , and . Rearranging, we get

It now remains to find the prime factorizations of , , and . The most attractive place to begin is with :

I don’t know of any particularly neat way of finding the factors and but it’s very easy by hand.

Next we consider :

The factor of is easy to find, but I don’t know a quick way to verify that is prime, other than trial division, by checking for prime factors up to .

Finally, we consider :

Again, I don’t know an easy way to find these factors, other than trial division, by checking for prime factors up to .

Putting all of this together, we have the prime factorization

As mentioned in the original post, perhaps the real challenge is to come up with a problem that retains the trickiness of this example, but avoids the cumbersome checking.

## A fun little formula from Graph Theory

This note is aimed at those taking my fourth-year Graph Theory course.

Let be a graph, where we view as a set of -element subsets of . For , denote by the degree of . (Notation and terminology as in my graph theory lecture notes.)

Lemma 1..

It’s easy to let this little formula go by without much thought. It gets used in the proof of Mantel’s Theorem. But I want to bring it to the fore, as an example of a simple but perhaps opaque statement, which becomes clearer with a little abstraction.

Consider the following stronger statement.

Lemma 2.Let be any function. Then

*Proof:* Given , the term appears on the right hand side once for each edge of which is an endpoint.

Lemma 1 follows by taking .

Let’s see how Lemma 1 is used in a proof of Mantel’s Theorem.

Theorem 3 (Mantel’s Theorem).Suppose that is triangle-free, of order , and of size . Then

*Proof: * Since is triangle-free, for every we have . Therefore . Summing across edges and using Lemma 1, we have

Combining these things, we have

as required.

So there we have it. Lemma 1 has a straightforward application in this proof of Mantel’s Theorem.

Note also that the complete bipartite graph is triangle-free and has size .

Often bundled into the statement of Mantel’s Theorem is the additional claim:

Proposition 4.Let be triangle-free, of order , and of size . Then is isomorphic to .

*Proof:* If , then each inequality in the above proof of Mantel’s Theorem must be an equality. In particular, for each we have . Thus the neighbourhoods of and of form a partition of the vertex set of . It follows that is complete bipartite, and up to isomorphism the only such graph to have size is .

## Möbius transformations

Teaching note: **Möbius Transformations**

This short note is written for those taking my second-year analysis course.

Möbius transformations are brilliant. They are conformal (=angle preserving) maps from the *extended complex plane* to itself.

Definition 1 (The extended complex plane).Theextended complex planeis , i.e. together with an entirely new element, denoted .

For now, we won’t extend the domains of and to include ; so the extended complex plane has no more algebraic structure than the field of complex numbers.

Definition 2 (Möbius transformations).AMöbius transformationis a function such thatfor some such that .

The second and third cases in the definition above are important, but we specify a Möbius transformation simply by writing e.g.

and leave the other two cases implicit.

Nevertheless, such a Möbius transformation does not determine the quadruple , but does determine the tuple in projective space. For a trivial example: the identity map is a Möbius transformation, equal to .

Example 1.Consider the Möbius transformation defined by Note that really is a Möbius transformation since . A few example evaluations: , , and .

Proposition 3.The composition of two Möbius transformations is a Möbius transformation.

*Proof:* For , consider a Möbius transformation , where . The composition is which is a Möbius transformation since is not zero.

Proposition 4.Möbius transformations are bijections.

*Proof:* Let , with . We find the candidate for its inverse, and check it really is. Define

by

We compose:

the identity! The composition is the identity by the same calculation.

Definition 5 (Möbius group).The set of Möbius transformations, equipped with composition, forms theMöbius group, denoted .

We are able to represent Möbius transformations as matrices, in the following way.

Definition 6.Define the map

Naturally we wonder whether, under this representation of Möbius transformations as matrices, the composition of functions corresponds to the multiplication of matrices.

Proposition 7.is an isomorphism.

*Proof:* It is clear that is a bijection. For , consider defined by , where .

The composition is

and we have

which shows that is a homomorphism.

Proposition 8.Möbius transformations act -transitively on .

*Proof sketch:* To see this, let be three distinct elements of the extended complex plane. We wish to choose such that

satisfies

Equivalently, such that the three equations

hold. It suffices to satisfy which can indeed be accomplished.