proof

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

e is irrational

Proving a number is irrational is mostly done by contradiction. So first suppose e is rational: e = p/q where p, q are coprime integers.

We know that q≥2 as e is not an integer (in fact, it’s in between 2 and 3). Then

Screen Shot 2017-06-14 at 10.40.11 AM.png

Note that, as q!e and n are natural numbers, we must have that x is a natural number.

However,

Screen Shot 2017-06-14 at 10.41.02 AM.png

And so we can bound x in the following way

Screen Shot 2017-06-14 at 10.41.06 AMThis is a contradiction since q!e must be a natural number, but it is a sum of an integer n plus a non-integer x. Hence, e is irrational.

M x

NEWS: 13532385396179

Recently, James Davis found a counterexample to John H. Conway’s ‘Climb to a Prime’ conjecture, for which Conway was offering $1,000 for a solution.

The conjecture states the following:

Let n be a positive integer. Write the prime factorisation in the usual way, where the primes are written in ascending order and exponents of 1 are omitted. Then bring the exponents down to the line, omit the multiplication signs, giving a number f(n). Now repeat.”

For example, f(60) = f(2^2 x 3 x 5) = 2235. As 2235 = 3 x 5 x 149, f(2235) = 35149. Since 35149 is prime, we stop there.

Davis had a feeling that the counterexample would be of the form

Screen Shot 2017-06-10 at 2.37.23 PM.png

where p is the largest prime factor of n. This motivated him to look for x of the form

Screen Shot 2017-06-10 at 2.38.05 PM.png

The number Davis found was 13532385396179 = 13 x 53^2 x 3853 x 96179, which maps to itself under f (i.e. its a fixed point). So, f will never map this composite number to a prime, hence disproving the conjecture.

M x

Proof Without Words #2

My last post seemed to go down well so I thought I’d compile a few more images of proofs without words!

C93PNFXXUAAfP7z.png

Determinant is the area of a parallelogram, by Solomon Golomb, Mathematics Magazine, March 1985.

C6fZNSAWUAAdyzq.jpg

Jensen_graph.png

A visual proof of Jensen’s inequality, found on Wikipedia. Jensen’s inequality states that

Screen Shot 2017-05-02 at 7.51.38 AM.png

In the diagram, the dashed curve along the X axis is the hypothetical distribution of X, while the dashed curve along the Y axis is the corresponding distribution of Y values. Note that the convex mapping Y(X) increasingly “stretches” the distribution for increasing values of X.

EXwbl.png

 

Hope you enjoyed! M x

12th Polymath Project

The Polymath Project is a collaboration among mathematicians to solve important problem in mathematics by providing a platform for mathematicians to communicate with each other on how to find the best route to the solution.

It began in January 2009 when Tim Gowers posted a problem on his blog and asked readers to reply with partial ideas or answers. This experiment resulted in a new answer to a difficult problem, proving the benefits of collaboration.

Previous Polymath projects that have successfully led to proofs incude the density version of the Hales-Jewett theorem and the Erdös discrepancy problem, as well as famously reducing the bound on the smallest gaps between primes.

Recently the 12th Polymath Project has started; Timothy Chow of MIT has proposed a new Polymath Project – resolve Rota’s basis conjecture.

What is the Rota’s Basis Conjecture?

The Rota’s Basis Conjecture states:

“If B1, B2,…., Bn are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n x n grid of vectors (vij) such that:

  1. the n vectors in row i are the members of the ith basis Bi (in some order), and
  2. in each column of the matrix, the n vectors in that column form a basis of V.”

Although easy to state, this conjecture has revealed itself hard to prove (like Fermat’s Last Theorem)!

M x

Proof Without Words #1

I decided to start a new series called ‘Proof Without Words’: a collection of pictures which prove a mathematical fact with an image. Remember, these are in no way rigorous and are just meant to give an idea of why the fact is true!

1/2+1/4+1/8+1/16+1/32+ … = 1

Sum of the first n positive odd numbers = n^2

arctan(1) + arctan(2) + arctan(3) = π

Screen Shot 2017-02-21 at 9.21.36 PM.png

Screen Shot 2017-02-21 at 9.22.18 PM.png

Viviani’s Theorem

The sum of the distances from any interior point to the sides of an equilateral triangle equals the length of the triangle’s altitude.

Screen Shot 2017-02-21 at 9.24.11 PM.png

M x