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 .
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
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 .
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). The extended complex plane is , 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). A Möbius transformation is a function such that
for 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
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 the Mö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
Equivalently, such that the three equations
hold. It suffices to satisfy which can indeed be accomplished.