May | 2014 | Minimalist Mathematician

Month: May, 2014

I just today received the forms I need from U to apply for my student visa. Now all that remains is to explain repeatedly on forms and in an interview that no, I am not a terrorist. I’m still also only half way through my exam term. My senior thesis is submitted and four out of my eight exams are done. And then there is the oral defense of my senior thesis. But half of it is done. Today I’m going to explain something I came across revising for my combinatorics exam, namely Ramsey theory.

The basic idea is that any set which is sufficiently large will contain some ordered subset. One example is the Bolzano-Weierstrass theorem in analysis. In a simple form it states that every bounded sequence in $\mathbb{R}$ has a convergent subsequence. So there is a subset with some type of structure.

For Ramsey theory we instead look at graphs. We take the complete graph $K_n$ and colour each edge either red or blue. The Ramsey number $R(s,t)$ is the smallest positive integer such that any two-colouring of the edges of $K_{R(s,t)}$ contains a monochromatic red $K_s$ or a monochromatic blue $K_t$ . To see how this works, I suggest you try to colour the edges of a $K_6$ such that there is no monochromatic triangle ( $K_3$ ).

We are going to prove that $R(3,3) = 6$ . First, see the picture below for a colouring of $K_5$ with no monochromatic triangle. From this we deduce that $R(3,3) > 5$ .

Source: Wikipedia

Consider a $K_6$ . If we take the vertex labeled 1 and focus on the five edges incident to it, it is trivial to see that at least three of them must be of the same colour, say red. We call these edges $\{1, x_1 \}, \{1, x_2 \}, \{1, x_3 \}$ . Now, we look at the edges connecting the vertices $x_1, x_2, x_3$ . There are three of them and either all of them are blue, in which case we have a monochromatic blue triangle, or at least one of them is red, We assume that the edge $\{x_1, x_2 \}$ is red. Then we have that the triangle $1, x_1, x_2$ is monochromatic red. Hence we always have a monochromatic triangle in any colouring of $K_6$ and so $R(3, 3) = 6$ .

Ramsey’s theorem states that each of these Ramsey numbers exist. Proving it is not difficult, though it can be a bit fiddly. I would recommend looking up a book on Ramsey theory, because it is a very interesting subject. In practice, these numbers are very difficult to find. Only some of the smaller ones have been found, and others have been bounded. Finding a lower bound is as simple as presenting a colouring with no red $K_s$ or blue $K_t$ . Finding upper bounds is much more difficult, since the argument used above often does not work. So one either has to find another general method or check each colouring of the upper bound. Checking this is a computationally difficult problem and hence takes a lot of time.

Ramsey numbers can be extended to arbitrarily many colours and can be shown to exist for any finite number of colours. In this case, finding the precise numbers becomes even more difficult as they must be larger. We will prove that $R(3, 3, 3) \leq 18$ . To do this, we will assume that $R(3, 6) = 18$ .

We call the third colour yellow. First, we combine the colours blue and yellow into a colour blue-yellow. We then use our assumption to deduce that any colouring of $K_{18}$ must contain either a red $K_3$ , in which case we are done, or a blue-yellow $K_6$ . In the second case, we use that we have showed $R(3, 3) = 6$ to deduce that this blue-yellow $K_6$ must contain a monochromatic blue or yellow triangle. Hence we have shown that $R(3, 3, 3) \leq 18$ .

May 3, 2014

Elliptic Curves – Part 2

This post aims to clarify some of the background on elliptic crves over finite fields. I want to give some intuition on what an elliptic curve is, where the point at infinity comes from, and some cool things you can do with elliptic curves. In this post, we are working over a field $K$ , and its multiplicative group $K^*$ .

Elliptic curves are defined over the projective plane $\mathbb{P}$ . Simply put, on a regular plane, parallel lines never intersect. The projective plane can be thought of as a regular plane, with an extra point called the point at infinity where parallel lines intersect. We need to define what we mean by a curve on $\mathbb{P}$ . We need that if $(x : y : z)$ is on the curve, then $(\lambda x : \lambda y : \lambda z)$ also is, for all $\lambda \in K^*$ . In particular, if $F(x, y, x) = 0$ is the equation of a projective curve, then $F$ must satisfy $F(x, y, z) = 0 \Rightarrow F(\lambda x, \lambda y, \lambda z) = 0$ . So $F$ needs to be a homogeneous polynomial.

For now, we will assume that $char(K) \neq 2, 3$ , that is, $1 + 1 \neq 0, 1 + 1 + 1 \neq 0$ . Then one can simplify the general homogeneous polynomial of degree 3 as follows: $F(x, y, z) = ax^3 + bx^2y + cx^2z + \dots = yz^2 - x^3 - Axz^2 - Bz^3$ . You can see that this looks similar to the equation for an elliptic curve I gave last time.

First, we want to find the point at infinity. We want $F(x, y, z) = 0$ , and we know that the point at infinity is where $z = 0$ . But this implies that $x = 0$ , so the point at infinity is $(0 : 1 : 0)$ , since scalar multiples are the same point. We call this point $O$ , and it is on every elliptic curve.

The one additional condition we place on an elliptic curve is that the points must be non-singular. This means that $\nabla F(x : y : z)$ is non-zero. Again, we work with $F(x, y, x) = y^2z - x^3 - Axz^2 - Bz^3$ . We can calculate $\frac{\partial F}{\partial x} = -3x^2 - Az^2, \frac{\partial F}{\partial y} = 2yz, \frac{\partial F}{\partial z} y^2 - 2Axz - 3Bz^2$ . Then we have that $\nabla F(0, 1, 0) = (0, 0, 1)$ , which is non-zero. Hence the point at infinity is on every elliptic curve.

Now, let’s get back to finding the equation of a general elliptic curve. For all the affine points, $z \neq 0$ . Hence $F(x, y, z) = \frac{1}{z^3} F(x, y, z) = 0$ . Thus $(\frac{y}{z})^2 = (\frac{x}{z})^3 + A(\frac{x}{z}) + B \Rightarrow \tilde{y}^2 = \tilde{x}^3 + A\tilde{x} + B$ . This is called the $\emph{affine equation}$ of an elliptic curve. Now we have almost managed to properly define elliptic curves.

For the affine points, we have that $y^2 = x^3 + Ax + B$ . Hence a point $(x, y)$ is non-singular if and only if $3x^2 = A \neq 0$ or $2y \neq 0$ . Using this, we can deduce that the equation defines an elliptic curve if and only if $4A^3 + 27B^2 \neq 0$ . We call $A^3 + 27B^2 = \Delta$ the discriminant of the elliptic curve.

To finish up, I will mention two applications of elliptic curves. They can be used to share a secret key with a similar method as the discrete logarithm Diffie-Hellman key exchange. They can also be used to factor large integers, using an algorithm called Lenstra Elliptic Curve Factorisation. This method is based on adding points of elliptic curves. A basic outline of the algorithm is as follows. Given an integer $n$ , choose an elliptic curve $E$ over $\mathbb{F}_n$ and a point on this curve. Add this point to itself until calculating the sum gives a non-invertible denominator $d$ . Then applying Euclid’s Algorithm, you get $gcd(n, d) \neq 1$ as a non-trivial factor of $n$ .

Minimalist Mathematician

Month: May, 2014

May 10, 2014

Ramsey Theory

May 3, 2014

Elliptic Curves – Part 2