proof

Waring’s Problem

Statement:

Take any whole number k that is greater than or equal to 2.  Show that there is some number s (that is allowed to depend on k) so that every positive whole number is a sum of s kth powers.

Proof

This problem was first solved by David Hilbert, and was then later proved by G.H. Hardy and John Littlewood in a different way. In this case, the second proof actually gave a lot more insight to the problem. To solve Waring’s problem as it has been stated you don’t need to give an s, you only need to show that one exists.  Finding the smallest s that works is a much more challenging (although arguably more interesting) problem. Using the, now named, Hardy-Littlewood circle method, Hardy and Littlewood wrote down an expression that approximated the number of ways to write N as a sum of s kth powers:

latex.png

The proof of Waring’s problem comes from that fact that since this must be positive and also be a whole number, there must be some way to write N as a sum of s kth powers.

Click here for more.

M x

(Sorry for missing a post last week, my university work is getting a bit hectic so posts may be more sporadic!)

Advertisements

Lychrel numbers

Lychrel number is a natural number that cannot form a palindrome by the 196-algorithm: an iterative process of repeatedly reversing a numbers’ digits and adding the resulting numbers.

Whilst in other bases (powers of two) certain numbers can be proven to never form a palindrome, in base 10 (the base system we use in everyday life) no Lychrel numbers have been proven to exist. However many numbers, such as 196, are suspected to be a Lychrel number on “heuristic and statistical grounds“.

The name Lychrel was coined by Wade Van Landingham in 2002 as an anagram of Cheryl, his girlfriend’s name.

196-Algorithm

The reverse-and-add process is when you add a number to the number formed by reversing the order of its digits.

Examples of non-Lychrel numbers are (taken from Wikipedia):

  • 56 becomes palindromic after one iteration: 56+65 = 121.
  • 57 becomes palindromic after two iterations: 57+75 = 132, 132+231 = 363.
  • 59 becomes a palindrome after 3 iterations: 59+95 = 154, 154+451 = 605, 605+506 = 1111
  • 89 takes an unusually large 24 iterations to reach the palindrome 8,813,200,023,188.
  • 1,186,060,307,891,929,990 takes 261 iterations to reach the 119-digit palindrome 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544, which is the current world record for the Most Delayed Palindromic Number. It was solved by Jason Doucette‘s algorithm and program in 2005.

196

196 is the smallest number suspected to never reach a palindrome in base 10 and has thus received the most attention:

  • In 1985 a program by James Killman ran unsuccessfully for over 28 days, cycling through 12,954 passes and reaching a 5366-digit number.
  • John Walker began his 196 Palindrome Quest in 1987. His program ran for almost three years, then terminated (as instructed) in 1990 with the message:

    Stop point reached on pass 2,415,836.
    Number contains 1,000,000 digits.
  • In 1995, Tim Irvin and Larry Simkins reached the two million digit mark in only three months without finding a palindrome.
  • Jason Doucette then reached 12.5 million digits in May 2000.
  • Wade Van Landingham used Jason Doucette’s program to reach a 13 million digit. By May 2006, Van Landingham had reached the 300 million digit mark.
  • In 2011 Romain Dolbeau completed a billion iterations to produce a number with 413,930,770 digits, and in February 2015 his calculations reached a number with billion digits.

 A palindrome has yet to be found.

For more on Lychrel numbers, click here or here.

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

Proof Without Words #3

Proof of the identity

Screen Shot 2017-07-30 at 5.34.22 PM.png

HCfGOYp.gif


dkoCZ.png

The figure for general n is similar, with n right pyramids, one with an (n-1)-cube of side length xk as its base and height xk for each k=1,….,n.


The derivative of sin is cosine.

g4n8SZX.jpg



From ‘Proof without words‘ by Roger Nelsen

Screen Shot 2017-07-30 at 5.47.56 PM.png

By Sidney H. Kung

Screen Shot 2017-07-30 at 5.48.12 PM.png

By Shirley Wakin


Previous ‘Proof Without Words‘: Part 1 | Part 2

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

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