# Ramsey’s Theorem

Ramsey’s theorem is a fundamental theorem in combinatorial mathematics, and initiated the combinatorial theory called Ramsey Theory. This theory aims to seek regularity in disorder: “general conditions for the existence of substructures with regular properties“.

Ramsey’s theorem states that:

“for each pair of positive integers k and l there exists an integer R(k,l) such that any graph with R(k,l) nodes contains a clique with at least k nodes or an independent set with at least l nodes.

Clique:

A clique of agraph G is a complete subgraph of G.

Source: MathWorld

Independent Set:

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of the graph. Below are some examples:

Source: MathWorld

Another formulation of the theorem states that “there exists a least positive integer R(rs) for which every blue-red edge colouring of the complete graph on R(rs) vertices contains a blue clique on vertices or a red clique on s vertices”. Extending this theorem, we can apply this to n colours rather than just 2.

### Ramsey Numbers

The numbers R(r,s) in Ramsey’s theorem are called Ramsey numbers. Ramsey numbers give the solution to the party problem that asks:

“the minimum number of guests, R(mn), that must be invited so that at least m will know each other or at least n will not know each other”

Connecting Ramsey numbers to graph theory, the Ramsey number is the minimum number of vertices, v = R(m,n), needed in order for all undirected graphs of order v to contain a clique of order m or an independent set of order n. Ramsey’s theorem tells us that this exists for all m and n.

M x

# MATHS BITE: The Kolakoski Sequence

The Kolakoski sequence is an infinite sequence of symbols {1,2} that is its own “run-length encoding“. It is named after mathematician Willian Kolakoski who described it in 1965, but further research shows that it was first discussed by Rufus Oldenburger in 1939.

This self-describing sequence consists of blocks of single and double 1s and 2s. Each block contains digits that are different from the digit in the preceding block.

To construct the sequence, start with 1. This means that the next block is of length 1. So we require that the next block is 2, giving the sequence 1, 2. Continuing this infinitely gives us the Kolakoski sequence: 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, etc.

M x

# Fermat’s Little Theorem

### Statement:

Let p be a prime then ap ≡ a (mod p), for any natural number a.

### Proof using Modular Arithmetic:

Firstly, we need to discuss Wilson’s theorem. This states:

(p-1)! ≡ -1 (mod p) is p is prime.

We must first prove this theorem:

If p is prime, then 1, 2, …, p-1 are invertible mod p. Now we can pair each of these numbers with its inverse (for example 3 with 4 in mod 11). The only elements that cannot be paired with a different number are 1 and -1, which are self-inverses, as shown below:

Now (p-1)! is a product of (p-3)/2 inverse pairs together with -1 and 1, whose product is -1.

So (p-1)! ≡ -1 (mod p).

Back to the proof of Fermat’s Little Theorem.

The statement of Fermat’s Little Theorem is equivalent to ap-1 ≡ 1 (mod p) if a ≢ 0 (mod p).

Consider the numbers a, 2a, …., (p-1)a. These are each distinct mod p and so they are congruent to 1, 2, …., (p-1) (mod p) in some order.

Hence a·2a···(p-1)a ≡ 1·2···(p-1) (mod p).

So ap-1(p-1)! ≡ (p-1)!.

And therefore ap-1 ≡ 1 (mod p).

We can extend this to a≡ a (mod p) as shown below:

When a ≡ 0 (mod p): 0≡ 0 (mod p). So a≡ a (mod p).

When a ≢ 0 (mod p): We can multiply through by a, as a and p are coprime. Then we get a≡ a (mod p), as required.

Hence, we have proved Fermat’s Little Theorem, a very important result in number theory.

M x

# Transcendental Numbers

A transcendental number is a number that is real or complex, but it not algebraic, meaning that it is not the root of a polynomial with non-zero integer coefficients. For example, √2 is algebraic as it is the solution to the polynomial equation x– 2 = 0.

### History

In 1844, Joseph Liouville proved the existence of transcendental numbers and in 1851 he gave the first example of such a number:

= 0.11000100000000000000000100……

(i.e. the nth digit after the decimal point is 1 if n = k! for some k, and 0 otherwise). This number is now known as the Liouville constant.

Only in 1873 was the first ‘non-constructed’ number shown to be transcendental when Charles Hermite proved that e was transcendental. Then, in 1882, Ferdinand von Lindemann proved that π was transcendental.

In fact, proving a number is transcendental is extremely challenging, even though they are known to be very common.

Why are they very common?

The algebraic numbers are countable (the set of algebraic numbers is the countable union of countable sets and so is therefore countable). However, the real numbers are uncountable. Therefore, since every real number is either algebraic or transcendental, the transcendentals must be uncountable. This implies that there are a lot more transcendental numbers than algebraic numbers.

### Examples of Transcendental Numbers

• ea if a is algebraic and non-zero
• π
• eπ
• ab where a,b are algebraic, but a ≠ 0,1
• in particular,  the Gelfond-Schenider Constant
• Continued Fraction Constant

If you want to find out more examples, click here.

Would you like to see a blog post specifically on Liouville numbers? M x

# Prime Number Theorem

Today I thought I’d quickly discuss a extremely important theorem in one of my favourite areas in mathematics: Number Theory (as you can probably tell by the number of posts that I’ve published about primes!).

Perhaps the first property of π(x) – the number of primes less than or equal to x – is that π(x) tends to infinity as x tends to infinity. In other words, the prime numbers are infinite, which was proved by Euclid in “Elements”. A more precise result, established by Euler in 1737, was that the series of reciprocals of the prime numbers:

is a divergent series. In doing so, Euler found an alternative way to prove that there was an infinite number of primes, as if there wasn’t then the series would have a finite value.

The Prime Number Theorem states that if π(x) is the number of primes less than or equal to x, then

Although the notation ~ may be unfamiliar, it simply means that π(x) is asymptotically equal to x/lnx, i.e.

Note that the prime number theorem is equivalent to saying that the nth prime number pn satisfies the following relationship:

The PNT was proposed by Gauss in 1792 when he was only 15 years old! (Makes you wonder what you’ve been doing with your life so far…) He later refined this estimate to

HAPPY HALLOWEEN! M x

# abc Conjecture

## What is it?

The abc conjecture was first posed by Joseph Oesterlé in 1985 and David Masser in 1988. The conjecture begins by presenting 3 distinct positive integers a, b and that are relatively prime and satisfy the equation a + b = c. It states that, if the number d  is the product of the distinct prime numbers of abc, then d is usually much larger smaller than c. This product is defined mathematically as the ‘radical’ of abc and hence the conjecture can be expressed more formally as:

If a, b, and c are coprime positive integers such that a + b =c, it turns out that “usually” c < rad(abc).

There are a few exceptions to this. To deal with this, the abc conjecture specifically states that:

For every ε > 0, there exist only finitely many triples (a, b, c) of coprime positive integers, with a +b = c, such that:

## Consequences if it is TRUE

The abc conjecture is linked to many other questions in number theory; if it were to be true, then it would imply that many other conjectures are also true, including:

and many more.

## Proof

In 2012, the Japanese mathematician Shinchi Mochizuki published a 500 page proof of the abc conjecture. However, it was so complex that no mathematicians could understand it due to the fact that it used a new mathematical framework known as inter-universal Teichmüller Theory. In a verification report published on December 2014, Mochizuki stated that

“With the exception of the handful of researchers already involved in the verification activities concerning IUTeich (inter-universal Teichmüller Theory) discussed in the present report, every researcher in arithmetic geometry throughout the world is a complete novice with respect to the mathematics surrounding IUTeich, and hence, in particular, is simply not qualified to issue a definitive (i.e., mathematically meaningful) judgment concerning the validity of IUTeich on the basis of a ‘deep understanding’ arising from his/her previous research achievements.”

However, a few weeks ago, four dozen mathematicians converged to hear Mochizuki present his own work at a conference in Kyoto University. This was a ‘breakthrough’ as described by Ivan Fesenko: “It was the key part of the meeting… He was climbing the summit of his theory, and pulling other participants with him, holding their hands.”

Now, around 10 mathematicians have a solid understanding of this new theory, giving a glimmer of hope for our future understanding of this proof.

## Video

Sources: 1 | 2 | 3 | 4 | 5 | 6

M x

# The Basel Problem

The Basel Problem is a problem in number theory posed by Pietro Mengoli in 1644, and solved by Leonhard Euler in 1734. As the problem remained open for 90 years, Euler’s solution brought him immediate fame at the age of 28.

The Basel Problem asks the result of the sum

i.e. the sum of the inverse of the square numbers.

As there are infinitely many square numbers, this sum has infinitely many terms. It is possible to find the ‘result’ of this sum due to the fact that the sum converges to a particular limiting value as the denominator approaches infinity. Part of the difficulty of solving this series is because it converges very slowly; when n = 106, the result is only accurate to 5 decimal places.

Euler found that the result had the value of:

But how did he do this?

Firstly, recall the Taylor series expansion of sin(x):

If we divide by x, this gives us:

Applying the Weierstrass factorisation theorem, which states that “entire functions can be represented by a product involving their zeroes” we obtain the expression:

If we multiply out this product and collect all x2 terms we get:

In the expansion of sin(x)/x the coefficient of x2 is -1/(3!). By comparing coefficients and noting that they must be equal on each side, we can equate this as:

Hence, reaching a final result of

Sources: 1 | 2 | 3

M x