April 2020 – sylvy's mathsy blog

Saga hwæt ic hatte

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

Puzzle and meta-puzzle: Factorisation — SOLUTION

In an earlier post I posed the following problem:

Find the prime factorization of ${12318876808768112319}$ .

Solution.

Write $z:=12318876808768112319$ . As a first attempt we shall ask some straightforward questions:

Is ${z}$ even? No.
Is ${z}$ divisible by ${3}$ ? We use the “sum the digits” trick, and find that — yes — ${z}$ is divisible by ${3^{4}}$ , but not divisible by ${3^{5}}$ .
Is ${z}$ divisible by ${5}$ ? No.

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

Taking out these factors, namely ${3^{4}}$ and ${11}$ , we are still left with a large number:

$\displaystyle 13825899897607309.$

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- ${10}$ representation of ${z}$ . Let ${x:=12319}$ and let ${y:=10^{5}}$ . Then ${y-x=87681}$ , and $z=y^{3}(x-1)+y^{2}(y-x-1)+y(y-x)+x$ . Rearranging, we get

$\begin{array}{rl} z &= y^{3}x-y^{2}x-yx+x\\ &= x(y^{3}-y^{2}-y+1)\\ &= x(y-1)^{2}(y+1). \end{array}$

It now remains to find the prime factorizations of ${x=12319}$ , ${y-1=99999}$ , and ${y+1=100001}$ . The most attractive place to begin is with ${y-1=99999}$ :

$\begin{array}{rl} y-1 &= 99999\\ &= 3^{2}\cdot11111\\ &= 3^{2}\cdot41\cdot271. \end{array}$

I don’t know of any particularly neat way of finding the factors ${41}$ and ${271,}$ but it’s very easy by hand.

Next we consider ${y+1=10^{5}+1}$ :

$y+1 = 100001 = 11\cdot9091.$

The factor of ${11}$ is easy to find, but I don’t know a quick way to verify that ${9091}$ is prime, other than trial division, by checking for prime factors up to ${\lfloor\sqrt{9091}\rfloor=95}$ .

Finally, we consider ${x=12319}$ :

$x = 12319 = 97\cdot127.$

Again, I don’t know an easy way to find these factors, other than trial division, by checking for prime factors up to ${\lfloor\sqrt{12319}\rfloor=110}$ .

Putting all of this together, we have the prime factorization

$12318876808768112319 = 3^{4}\cdot11\cdot41^{2}\cdot97\cdot127\cdot271^{2}\cdot9091.$

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 ${G=(V,E)}$ be a graph, where we view ${E}$ as a set of ${2}$ -element subsets of ${V}$ . For ${v\in V}$ , denote by ${d(v)}$ the degree of ${v}$ . (Notation and terminology as in my graph theory lecture notes.)

Lemma 1. ${\sum_{uv\in E}d(u)+d(v) = \sum_{u\in V}d(u)^{2}}$ .

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 ${f:V\longrightarrow\mathbb{N}}$ be any function. Then

$\displaystyle \sum_{uv\in E}f(u)+f(v)=\sum_{v\in V}d(u)f(u).$

Proof: Given ${v}$ , the term ${f(v)}$ appears on the right hand side once for each edge of which ${v}$ is an endpoint. $\Box$

Lemma 1 follows by taking ${f=d}$ .

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

Theorem 3 (Mantel’s Theorem). Suppose that ${G}$ is triangle-free, of order ${n}$ , and of size ${e}$ . Then

$\displaystyle e\leq\Big\lfloor\frac{n^{2}}{4}\Big\rfloor.$

Proof: Since ${G}$ is triangle-free, for every ${uv\in E}$ we have ${N(u)\cap N(v)=\emptyset}$ . Therefore ${d(u)+d(v)\leq n}$ . Summing across edges and using Lemma 1, we have

$\displaystyle \begin{array}{rclr} \sum_{v\in V}d(v)^{2}=\sum_{uv\in E}d(u)+d(v) &\leq& ne. \end{array}$

Combining these things, we have

$\displaystyle \begin{array}{rclr} 4e^{2} &=& \big(\sum_{v\in V}d(v)\big)^{2} &\text{by the degree formula}\\\\ &\leq& n\sum_{v\in V}d(v)^{2} &\text{by Cauchy--Schwarz}\\\\ &\leq& n^{2}e, \end{array}$

as required. $\Box$

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 ${K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}}$ is triangle-free and has size ${\lfloor\frac{n^{2}}{4}\rfloor}$ .

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

Proposition 4. Let ${G}$ be triangle-free, of order ${n}$ , and of size ${e(G)=\lfloor\frac{n^{2}}{4}\rfloor}$ . Then ${G}$ is isomorphic to ${K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}}$ .

Proof: If ${e(G)=\lfloor\frac{n^{2}}{4}\rfloor}$ , then each inequality in the above proof of Mantel’s Theorem must be an equality. In particular, for each ${uv\in E}$ we have ${d(u)+d(v)=n}$ . Thus the neighbourhoods of ${u}$ and of ${v}$ form a partition of the vertex set of ${G}$ . It follows that ${G}$ is complete bipartite, and up to isomorphism the only such graph to have size ${\lfloor\frac{n^{2}}{4}\rfloor}$ is ${K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}}$ . $\Box$

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). The extended complex plane is ${\overline{\mathbb{C}}:=\mathbb{C}\cup\{\infty\}}$ , i.e. ${\mathbb{C}}$ together with an entirely new element, denoted ${\infty}$ .

For now, we won’t extend the domains of ${+}$ and ${\cdot}$ to include ${\infty}$ ; 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 ${f:\overline{\mathbb{C}}\longrightarrow\overline{\mathbb{C}}}$ such that

$\displaystyle f(z)=\left\{\begin{array}{ll}\frac{az+b}{cz+d}&z\neq-\frac{d}{c},\infty\\\infty&z=-\frac{d}{c}\\\frac{a}{c}&z=\infty,\end{array}\right.$

for some ${a,b,c,d\in\mathbb{C}}$ such that ${ad-bc\neq0}$ .

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

$\displaystyle f(z):=\frac{az+b}{cz+d},$

and leave the other two cases implicit.

Nevertheless, such a Möbius transformation does not determine the quadruple ${(a,b,c,d)}$ , but does determine the tuple ${[a;b;c;d]}$ in projective space. For a trivial example: the identity map ${z}$ is a Möbius transformation, equal to ${\frac{2z}{2}}$ .

Example 1. Consider the Möbius transformation ${g:\overline{\mathbb{C}}\longrightarrow\overline{\mathbb{C}}}$ defined by ${g(z):=\frac{1}{z-1}.}$ Note that ${g}$ really is a Möbius transformation since ${-1\neq0}$ . A few example evaluations: ${g(0)=-1}$ , ${g(1)=\infty}$ , and ${g(\infty)=0}$ .

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

Proof: For ${i=1,2}$ , consider a Möbius transformation ${f_{i}(z):=\frac{a_{i}z+b_{i}}{c_{i}z+d_{i}}}$ , where ${a_{i}d_{i}-b_{i}c_{i}\neq0}$ . The composition is $\displaystyle \begin{array}{rcl} f_{2}\circ f_{1}(z)&=&\frac{(a_{1}a_{2}+c_{1}b_{2})z+b_{1}a_{2}+d_{1}b_{2}}{(a_{1}c_{2}+c_{1}d_{2})z+b_{1}c_{2}+d_{1}d_{2}},\end{array}$ which is a Möbius transformation since $\displaystyle (a_{1}a_{2}+c_{1}b_{2})(b_{1}c_{2}+d_{1}d_{2}) - (a_{1}c_{2}+c_{1}d_{2})(b_{1}a_{2}+d_{1}b_{2}) = (a_{1}d_{1}-b_{1}c_{1})(a_{2}d_{2}-b_{2}c_{2})$ is not zero. $\Box$

Proposition 4. Möbius transformations are bijections.

Proof: Let ${f(z)=\frac{az+b}{cz+d}}$ , with ${ad-bc\neq0}$ . We find the candidate for its inverse, and check it really is. Define ${g:\overline{\mathbb{C}}\longrightarrow\overline{\mathbb{C}}}$
by

$\displaystyle g(w)=\frac{dw-b}{-cz+a}.$

We compose:

$\displaystyle \begin{array}{lll} g\circ f(z) &=& \frac{d\frac{az+b}{cz+d}-b}{-c\frac{az+b}{cz+d}+a}\\ &=& \frac{(ad-bc)z}{ad-bc}\\ &=& z, \end{array}$

the identity! The composition ${f\circ g}$ is the identity by the same calculation. $\Box$

Definition 5 (Möbius group). The set of Möbius transformations, equipped with composition, forms the Möbius group, denoted ${\mathbf{M}}$ .

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

Definition 6. Define the map

$\displaystyle \begin{array}{rcl} \Phi:\mathbf{M} &\longrightarrow& \mathrm{PGL}_{2}(\mathbb{C})\\ \frac{az+b}{cz+d} &\longmapsto& \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{array}$

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. ${\Phi}$ is an isomorphism.

Proof: It is clear that ${\Phi}$ is a bijection. For ${i=1,2}$ , consider ${f_{i}\in\mathbf{M}}$ defined by ${f_{i}(z):=\frac{a_{i}z+b_{i}}{c_{i}z+d_{i}}}$ , where ${a_{i}d_{i}-b_{i}c_{i}\neq0}$ .
The composition is

$\displaystyle \begin{array}{rcl} f_{2}\circ f_{1}(z)&=&\frac{(a_{1}a_{2}+c_{1}b_{2})z+b_{1}a_{2}+d_{1}b_{2}}{(a_{1}c_{2}+c_{1}d_{2})z+b_{1}c_{2}+d_{1}d_{2}},\end{array}$

and we have

$\displaystyle \begin{array}{rcl} \Phi(f_{2})\Phi(f_{1}) &=& \begin{pmatrix}a_{2} & b_{2} \\ c_{2} & d_{2} \end{pmatrix}\begin{pmatrix} a_{1} & b_{1} \\ c_{1} & d_{1} \end{pmatrix}\\&=& \begin{pmatrix} a_{1}a_{2}+c_{1}b_{2} & b_{1}a_{2}+d_{1}b_{2} \\ a_{1}c_{2}+c_{1}d_{2} & b_{1}c_{2}+d_{1}d_{2} \end{pmatrix}\\&=& \Phi(f_{2}\circ f_{1}),\end{array}$

which shows that ${\Phi}$ is a homomorphism. $\Box$

Proposition 8. Möbius transformations act ${3}$ -transitively on ${\overline{\mathbb{C}}}$ .

Proof sketch: To see this, let ${w_{0},w_{1},w_{\infty}}$ be three distinct elements of the extended complex plane. We wish to choose ${[a;b;c;d]}$ such that

$\displaystyle f(z)=\frac{az+b}{cz+d}$

satisfies

$\displaystyle f(0)=w_{0},\,f(1)=w_{1},\,f(\infty)=w_{\infty}.$

Equivalently, such that the three equations

${\frac{b}{d}=w_{0}}$
${\frac{a+b}{c+d}=w_{1}}$
${\frac{a}{c}=w_{\infty}}$

hold. It suffices to satisfy $\displaystyle w_{\infty}c+w_{0}d=w_{1}c+w_{1}d,$ which can indeed be accomplished. $\Box$

	sylvyanscombe on Saga hwæt ic hatte
	Puzzle and meta-puzz… on Puzzle and meta-puzzle: F…
	sylvyanscombe on Möbius transformations
	sylvyanscombe on Henselianity in the language o…
	Puzzle corner: Solut… on Sylvy’s weekly puzzle…