theorem

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.

Clique_950.gif

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:

IndependentSet_900.gif

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.

For a proof of this theorem, click here.

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.

Click here for an article on how to calculate R(4,3).

M x

Advertisements

Last Digit

How would we go about finding the last digit of very large numbers, such as Screen Shot 2017-08-24 at 4.27.22 PM.png?

There are a variety of different tools that we can use, including modular arithmetic and the Chinese remainder theorem, which I am going to talk about in today’s post.

Pattern Finding

A problem like this can be tackled by listing out the initial expansions of a power in order to determine a pattern. Then, by proving that this pattern holds (often by induction), the last decimal digit of a power can be solved completely. For example, the last digit of various powers of 1 to 9 are:

Screen Shot 2017-08-24 at 4.32.26 PM.png

Source: Brilliant

From this we can determine that:

  • the last digit of powers of 1 is always 1;
  • the last digits of powers of 2 repeat in a cycle of 4, 8, 6, 2;
  • the last digits of powers of 3 repeat in a cycle of 9, 7, 1, 3;
  • the last digits of powers of 4 alternate between 6 and 4;
  • the last digit of powers of 5 is always 5;
  • the last digit of powers of 6 is always 6;
  • the last digits of powers of 7 repeat in a cycle of 9, 3, 1, 7;
  • the last digits of powers of 8 repeat in a cycle of 4, 2, 6, 8;
  • the last digits of powers of 9 alternate between 1 and 9.

Example

Find the last digit of 2^2016.

The last digits of the powers of two repeat in a cycle of 2, 4, 8, 6. Dividing 2016 by 4 we get 504 (with no remainder). Hence the sequence of digits repeats 504 times with no extra entries, so the last digit should be 6. 

Modular Arithmetic

The above idea can be expressed more elegantly with modular arithmetic. Finding the last digit of a number is the same as finding the remainder when this number is divided by 10. In general, the last digit of a power in base n is its remainder upon division by n. So, for decimal numbers, we compute mod 10 to find the last digit, mod 100 to find the last two digits, etc.

For example,

Screen Shot 2017-08-24 at 5.22.44 PM.png

Chinese Remainder Theorem

The Chinese Remainder Theorem states that

if one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime

– Wikipedia

Applying this theorem, we can find a number mod 2^n and mod 5^n and then combine those results to find that number mod 10^n.

Example

Find the last two digits of 74^540.

Observe that 100 = 4 x 25 and gcd(4,25) = 1. So we can compute 74^540 mod 4 and mod 25, then combine these to find it mod 100. 

74^540 ≡ 2^540 x 37^540 ≡ 0 (mod 4)

and 

7^540 ≡ (-1)^540 ≡ 1 (mod 25)

The unique solution mod 100 to x ≡ 0 (mod 4), x ≡ 1 (mod 25) is 76, so this is the answer.

Euler’s Theorem

Euler’s Theorem states that

“if n and a are coprime positive integers, then

a^{\varphi (n)} \equiv 1 \pmod{n}

where \varphi (n) is Euler’s totient function.”

-Wikipedia

So an exponent b can be reduced modulo φ(n) to a smaller exponent without changing the value of a^b (mod n).

Example

Find the last two digits of 33^42.

φ(100) = 40, so 33^40≡ 1 (mod 100). So, 33^42 ≡ 33^2 (mod 100). This is easier to compute: 33^2 = 1089, so answer is 89.

Binomial Expansion

Another method is to expand the power using the Binomial theorem in such a way that many of the terms vanish mod 10. This is generally only useful when the base of the exponent is of the form 10k +/- 1.

Example

Find the last two digits of 31^25.

Screen Shot 2017-08-24 at 5.39.04 PM.png

After the second term, every term contains at least 2 zeros, and so they vanish mod 100. The first two terms = 751 ≡ 51 (mod 100) and so the last two digits of 31^25 are 51.

Hope you enjoyed this slightly longer post! M x

Noether’s Theorem

Today I thought I’d write a blog post about an interesting theorem I learnt whilst studying my Variational Principles module – Noether’s Theorem.

To understand Noether’s Theorem, we must first understand what is meant by a symmetry of a functional.

Given

Screen Shot 2017-08-08 at 11.45.48 AM.png

suppose we change the variables by the transformation t –> t*(t) and x –> x*(t) to obtain a new independent variable and a new function. This givesScreen Shot 2017-08-08 at 11.45.51 AM.png

where α* = t*(α) and β* = t*(β).

If F*[x*] = F[x] for all x, α and β, then this transformation * is called a symmetry.

What is a continuous symmetry?

Intuitively, a continuous symmetry is a symmetry that we can do a bit ofFor example, a rotation is a continuous symmetry, but a reflection is not. 

Noether’s Theorem

Noether.jpg

Noether’s Theorem – proven by mathematician Emmy Noether in 1915 and published in 1918 – states that every continuous symmetry of F[x] the solutions (i.e. the stationary points of F[x]) will have a corresponding conserved quantity.

Why?

Consider symmetries that involve only the x variable. Then, up to first order, the symmetry can be written as:

t –> t, x(t) –> x(t) + εh(t)

where h(t) represents the symmetry transformation. As the transformation is a symmetry, we can pick ε to be any small constant number and F[x] does not change, i.e. δF = 0. Also, since x(t) is a stationary point of F[x], we know that if ε is any non-constant, but vanishes at the end-points, then we have δF = 0 again. Combining these two pieces of information, we can show that there is a conserved quantity in the system.

For now, do not make any assumptions about ε. Under the transformation, the change in F[x] is given by

Screen Shot 2017-08-08 at 11.57.37 AM.png

Firstly, consider the case where ε is constant. Then the second integral vanishes and we obtain

Screen Shot 2017-08-08 at 11.58.21 AM.png

Screen Shot 2017-08-08 at 11.58.38 AM.png

So we know that

Screen Shot 2017-08-08 at 11.58.41 AM.png

Now, consider a variable ε that is not constant, but vanishes at the endpoints. Then, as is a solution, we must have that δF = 0. Therefore,

Screen Shot 2017-08-08 at 12.00.00 PM.png

If we integrate the above expression by parts, we get that

Screen Shot 2017-08-08 at 12.00.03 PM.png

Hence the conserved quantity is:

Screen Shot 2017-08-08 at 12.01.56 PM.png

Not all symmetries involve just the x variable, for example we may have a time translation, but we can encode this as a transformation of the x variable only.

M x

MATHS BITE: Shoelace Theorem

The Shoelace theorem is a useful formula for finding the area of a polygon when we know the coordinates of its vertices. The formula was described by Meister in 1769, and then by Gauss in 1795.

Formula

Let’s suppose that a polygon P has vertices (a1, b1), (a2, b2), …, (an, bn), in clockwise order. Then the area of P is given by

\[\dfrac{1}{2} |(a_1b_2 + a_2b_3 + \cdots + a_nb_1) - (b_1a_2 + b_2a_3 + \cdots + b_na_1)|\]

The name of this theorem comes from the fact that if you were to list the coordinates in a column and mark the pairs to be multiplied, then the image looks like laced-up shoes.

Screen Shot 2017-08-04 at 11.59.29 AM.png

Proof

(Note: this proof is taken from artofproblemsolving.)

Let $\Omega$ be the set of points that belong to the polygon. Then

\[A=\int_{\Omega}\alpha,\]

where $\alpha=dx\wedge dy$.

Note that the volume form $\alpha$ is an exact form since $d\omega=\alpha$, where

\[\omega=\frac{x\,dy}{2}-\frac{y\,dx}{2}.\label{omega}\]

Substitute this in to give us

\[\int_{\Omega}\alpha=\int_{\Omega}d\omega.\]

and then use Stokes’ theorem (a key theorem in vector calculus) to obtain

\[\int_{\Omega}d\omega=\int_{\partial\Omega}\omega.\]

where

$\partial \Omega=\bigcup A(i)$

and $A(i)$ is the line segment from $(x_i,y_i)$ to $(x_{i+1},y_{i+1})$, i.e. Screen Shot 2017-08-04 at 12.05.20 PM.png is the boundary of the polygon.

Next we substitute for $\omega$:

\[\sum_{i=1}^n\int_{A(i)}\omega=\frac{1}{2}\sum_{i=1}^n\int_{A(i)}{x\,dy}-{y\,dx}.\]

Parameterising this expression gives us

\[\frac{1}{2}\sum_{i=1}^n\int_0^1{(x_i+(x_{i+1}-x_i)t)(y_{i+1}-y_i)}-{(y_i+(y_{i+1}-y_i)t)(x_{i+1}-x_i)\,dt}.\]

Then, by integrating this we obtain

\[\frac{1}{2}\sum_{i=1}^n\frac{1}{2}[(x_i+x_{i+1})(y_{i+1}-y_i)- (y_{i}+y_{i+1})(x_{i+1}-x_i)].\]

This then yields, after further manipulation, the shoelace formula:

\[\frac{1}{2}\sum_{i=1}^n(x_iy_{i+1}-x_{i+1}y_i).\]

M x

New Podcast!

Today is a quick post to let you know that the writer of one of my favourite blogs Roots of Unity, Evelyn Lamb, and the mathematician Kevin Knudson from the University of Florida have created a new podcast called ‘My Favourite Theorem‘!

Lamb says:

In each episode, logically enough, we invite a mathematician on to tell us about their favourite theorem. Because the best things in life are better together, we also ask our guests to pair their theorem with, well, anything: wine, beer, coffee, tea, ice cream flavours, cheese, favourite pieces of music, you name it. We hope you’ll enjoy learning the perfect pairings for some beautiful pieces of math.

Click here to listen to the first episode, which features Lamb and Knudson telling us about their favourite theorems!

M x

Goodstein Theorem

On reading a magazine on Gödel’s Incompleteness Theorems, I came across a family of sequences of non-negative integers called Goodstein sequences and the Goodstein Theorem involving these sequences.

Goodstein’s thoerem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence converges to 0.

What is a Goodstein Sequence?

To understand what a Goodstein sequence, first we must understand what hereditary base-n notation is. Whilst this notation is very similar to the usual base-n notation, base-n notation is not sufficient for Goodstein’s theorem.

To convert a base-n representation to a hereditary base-n notation, first rewrite all of the exponents in base-n notation. Then rewrite any exponents inside the exponents, and continue this way until every number in the expression has been converted to base-n notation.

For example, 35 = 25 + 2 + 1 in ordinary base-2 notation but Screen Shot 2017-07-11 at 5.37.45 PM.png in hereditary base-2 notation.

Now we can define the Goodstein sequence G(m) of a natural number m. In general the (n+1)-st term G(m)(n+1) of the Goodstein sequence of m is given as follows (taken from Wikipedia):

  • Take the hereditary base-n + 1 representation of G(m)(n).
  • Replace each occurrence of the base-n + 1 with n + 2.
  • Subtract one. (Note that the next term depends both on the previous term and on the index n.)
  • Continue until the result is zero, at which point the sequence terminates.

In spite of the rapid growth of the terms in the sequence, Goodstein’s theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.

Mathematicians Laurie Kirby and Jeff Paris proved in 1982 that Goodstein’s theorem is not provable in ordinary Peano arithmetic. In other words, this is the type of theorem described in 1931 by Gödel’s incompleteness theorem.

M x

VIDEO: Banach–Tarski Paradox

The Banach-Tarski Paradox is a theorem in geometry which states that:

“It is possible to decompose a ball into five pieces which can be reassembled by rigid motions to form two balls of the same size as the original.”

It was first stated in 1924, and is called a paradox as it contradicts basic geometric intuition.

An alternate version of this theorem tells us that:

“It is possible to take a solid ball the size of a pea, and by cutting it into a finite number of pieces, reassemble it to form a solid ball the size of the sun.”

Below is an awesome video explaining how this paradox works:

 

M x