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 k^th 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 k^th powers:

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 k^th 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!)

MATHS BITE: Even or Odd?

What are even and odd functions? These two terms get used very frequently in order to simplify problems such as integration or when finding Fourier coefficients, for example.

Even Function

An even function is such that for all x in the domain

f(x) = f(-x)

An even function is symmetric with respect to the y-axis.

Even Function | mathsisfun

Examples:

• Any polynomial p, where n is even for all xⁿ. For example f(x) = x²+2x⁴ – 6. Note that (x+1)² is not even.
• f(x) = cos(x)

Odd Function

An odd function is such that for all x in the domain

f(x) = -f(-x)

An odd function is symmetric with respect to the origin.

Odd Function | mathsisfun

Examples:

• x, x³, x⁵,… etc. Note that unlike even functions, an expression such as x³ + 1 is not odd.
• f(x) = sin(x)

Odd and/or Even?

A function can be neither odd nor even, for example x³ − x + 1:

Neither odd nor even | mathsisfun

Additionally, the only function that is even and odd is f(x) = 0.

Properties:

• Adding two even (odd) functions will give an even (odd) function.
• Adding an even and an odd function will give a function that is neither odd nor even.
• Both the product of two even functions and the product of two odd functions is even.
• The product of an even function and an odd function is odd.

Maths Behind Bitcoin

Bitcoin is a “worldwide cryptocurrency and digital payment system” that works without a central repository or single administrator. This system is peer-to-peer meaning that each computer can act as a server for the others, which allows for transactions to take place between users directly without an intermediary (or central server).

Bitcoins are not stored centrally, but rather exist as records in the block chain, which is a “distributed ledger”. To own a bitcoin simply means to have the ability to transfer control of it to someone else by creating a record of the transfer in the block chain. This ability is granted by access to an ECDSA (Elliptic Curve Digital Signature Algorithm) private and public key pair. What does this mean?

Algorithms

An algorithm is a process to make calculations. They are like machines: data comes in, and the algorithm does some work, and data comes out. ECDSA is the algorithm that creates the Bitcoin key pairs. To create a new key pair the elliptic curve is plotted across a finite field.

Elliptic Curves

An elliptic curve is represented algebraically as an equation of the form:

 y² = x³ + ax + b

Elliptic curves have useful properties, such as a non-vertical line intersecting two non-tangent points on the curve will always intersect a third point on the curve. Furthermore, if the non-vertical line intersects a point tangent to the curve it will intersect precisely one other point. Using these properties it is possible to define two operations:

• Point Addition: P + Q = R is defined as the reflection through the x-axis of the third intersecting point R’ on a line that includes P and Q.

• Point Doubling: P + P = R is defined by finding the line tangent to the point being doubled and taking a reflection through the x-axis of the intersecting point R’ on the curve.

Finite Fields

In relation to ECDSA, a finite field is a predefined range of positive numbers within which every calculation must fall. If a number is outside of this range, it will wrap around so that it does fall within this range.

In order to understand, consider taking the modulus operator. For example, mod 7: here the finite field is modulo 7 and all answers in this field lie in the range 0 – 6.

ECDSA

Bitcoin defines the formula for the curve and the parameters of the field so that every user has the same graph. The parameters include:

• the equation used;
• the prime modulo of the field;
• a base point that falls on the curve.

The order of the base point is not independent of the other parameters, and can be thought of graphically as “the number of times the point can be added to itself until its slope is infinite.” The base point is selected so that the order is a large prime number.

In the case of bitcoin:

Elliptic Curve Equation: y² = x³ + 7

Prime Modulo: 2²⁵⁶ – 2³² – 2⁹ – 2⁸ – 2⁷ – 2⁶ – 2⁴ – 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Base Point: 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Order: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Source: coindesk.com

In ECDSA the private key is chosen as a number between 1 and the order. Then the public key is given by:

public key = private key * base point

Practically, the computation of the public key is broken down into point doubling and point addition operations starting from the base point.

This shows that the maximum number of private keys possible is equal to the order. However, Bitcoin has an enormous field:

There are 10^82 atoms in the universe. If you made the entire Universe our finite field and you drew a giant elliptic curve through it, each “point” in the universe would about 300 square atoms. At that size, each cell in your body takes up the space of 1,150,000,000 Bitcoin key pairs.

– www.cryptocoinsnews.com

Bitcoin Addressess

A Bitcoin address is not a public key; it is an RIPEMD-160 hash of an SHA256 hash of a public key. SHA256 and RIPEMD-160 are also algorithms that, unlike ECDSA, generate a hash. I have taken an example from cryptocoinsnews to illustrate a simple example of a hash (SHA256 and RIPEMD-160 are much more complex):

Every letter has a value of its position in the alphabet: A = 1, B = 2, etc.
Our hash algorithm is this:

for i=0 to len(word):
h = h + (i + letter_value)

So for the word “ABC” using our hash would be:

Loop for ‘A’
h = 0 + (0 + 1)
Loop ‘B’
h = 1 + (1 + 2)
‘C’
h = 4 + (2 + 3)
h = 9

‘ABC’ hashes to 9.

How Bitcoin Actually Works

Your private key is kept secret. This key allows you to unlock funds that are owed to you in the Bitcoin block chain.

When making a transacting, it contains a script that has your private key’s signature and the matching public key. This is in order to prove that the public key provided matches the private key that was used to make the signature. If the public key hashes with the Bitcoin address in the unclaimed transaction, it can be spent.

Hope you enjoyed this basic explanation of Bitcoin! M x

Markov Chains: An Intro

The Markov Property

A stochastic process (“a mathematical object usually defined as a collection of random variables”) is said to have the Markov Property if, conditional on the present value, the future is independent on the past.

Let’s firstly introduce some notation: let S be a countable set called the state space and let X = (X_t: t ≥ 0) be a sequence of random variables taking values in S.

Then, the sequence X is called a Markov Chain if it satisfies the Markov Property:

for all t ≥ 0 and all x₀, x₁, …, x_t ϵ S.

Notation is simplified in the case where the Markov chain is homogeneous. This is when for all i, j ϵ S, the conditional probability P(X_t+1 = j | X_t = i) does not depend on the value of t.

Examples

• Branching Process: The branching process is a simple model of the growth of a population; each member of the n^th generation has a number of offspring that is independent of the past; X_n = size of the n^th generation.
• Random Walk: A particle performs a random walk on the line: let Z₁, Z₂, …, be independent with P(Z_i = 1) = p and P(Z_i = -1) = 1-p, then X_n =
  Z₁ + … + Z_n; at each epoch of time, it jumps a random distance that is independent of the previous jumps.
• Poisson Process: the Poisson process satisfies a Markov property in which time is a continuous variable rather than a discrete variable, and thus the Poisson process is an example of a continuous-time Markov chain; the Markov property still holds as arrivals after time t are independent of arrivals before this time.

Two Quantities

For simplification (and as this is only an intro to  Markov chains) we’ll assume that the Markov chains are homogeneous.

Two quantities that are needed in order to calculate the probabilities in a chain are the:

1. transition matrix: P = (p_i,j: i,j ϵ S) given by p_i,j = P(X₁ = j | X₀ = i);
2. initial distribution: λ = (λ_i : i ϵ S) given by λ_i = P(X₀ = i).

As we have assumed homogeneity we have that

p_i,j = P(Xn+1 = j | Xn = i) for n ≥ 0.

These quantities are characterised in the following way:

Proposition:

a) The vector λ is a distribution  in that λ_i ≥ 0 for i ϵ S and the sum of λ_i over i = 1.

b) The matrix P = (p_i,j) is a stochastic matrix in that p_i,j ≥ 0 for i, j ϵ S and the sum of p_i,j over j = 1 for i ϵ S (i.e. that P row sums to 1)

Proof:

a) As λ_i is a probability, it is clearly non-negative. Additionally, the sum of λ_i over i = the sum of P(X₀ = i) over i = 1.

b) Since p_i,j is a probability, it is non-negative. Finally, the sum of p_i,j over j = the sum of P(Xn+1 = j | Xn = i) over j = P(Xn+1 ϵ S | Xn = i) = 1.

Hope you enjoyed this brief introduction to a Markov Chain!

M x

Mind the Gap

Having now been through one full year of university, I thought I’d write a blog post on the differences between secondary school and university mathematics in the British curriculum.

Personally, the main difference that I found was the focus on mathematical proof, something that is not taught in secondary school. For example, one of my lecture courses in first year was Numbers and Sets, which focused on learning how to construct a proof, rather than teaching a lot theory. The technique of writing a proof is something that, as a mathematician, I will carry with me throughout the rest of my academic career so I worked hard to learn this skill well. Becoming used to the language and symbols used in mathematical documents was definitely challenging but vital in order to be able to understand lectures.

The only part of A-Levels that prepared me for this major aspect of university maths was the fact that in order to score all the method marks we had to demonstrate all the steps in our working out. However, I must stress that this is not the same; mathematical proofs, especially in pure maths, often require more explanation in each step and a more logical succession of steps.

The other big difference is not understanding everything! For me, A-Level maths was not a big challenge. Yes, I studied hard, but things came easily for me and I found that I wouldn’t be stuck on a question for a very long time. Fast-forward to now, I find myself stuck on a question for hours! Whilst this can often be very frustrating, I love and thrive off the challenge – this year I have progressed so much as a mathematician!

Finally, mathematics at university is much less computational. There are some more applied courses where computation is essential, however the pure courses require almost no calculations! In secondary school, they label pure maths as what I now call applicable maths. This is maths that still requires are fair bit of computational work, however it is not directly linked to another subject, such as physics. For example, differential equations.

Hope you enjoyed this brief overview of my thoughts on the differences between university and secondary school mathematics. If you would like me to go more in depth please leave me a comment below! M x

MATHS BITE: Heptadecagon

A heptadecagon (or a 17-gon) is a seventeen sided polygon.

Regular Heptadecagon | Wikipedia

Constructing the Heptadecagon

In 1796, Gauss proved, at the age of 19 (let that sink in…) that the heptadecagon is constructible with a compass and a straightedge, such as a ruler. His proof of the constructibility of an n-gon relies on two things:

• the fact that “constructibility is equivalent to expressibility of the trigonometric functions of the common angle in terms of arithmetic operations and square root extractions“;
• the odd prime factors of n are distinct Fermat primes.

Constructing the regular heptadecagon involves finding the expression for the cosine of   in terms of square roots, which Gauss gave in his book Disquistiones Arithmeticae:

Source: Wikipdia

An explicit construction was given by Herbert Willian Richmond in 1893.

Source: Wikipedia

M x

Friedman Numbers

A Friedman number is an integer that can be obtained combining all its digits with the 5 arithmetic operations (+, -, x, /, ^) and concatenation. Note that parentheses can be used in the expressions in order to “override the default operator precedence“. These numbers are named after mathematician Erich Friendman.

For example, 13125 is a Friedman number as it can be written as .

A nice Friedman number is one where the digits in the expression can be arranged to be in the same order as the number itself. An example of this is 127 = -1 + 2^7.

Friedman numbers can be repdigits, such as

or pandigital numbers, like

This link will take you to a list of Friedman numbers and their decompositions up to 10^6.

Michael Brand showed that the density of Friedman numbers among the naturals is 1. This means that the probability of a number chosen randomly and uniformly between 1 and n to be a Friedman number tends to 1 as n tends to infinity.

Finding 2-digit Friedman Numbers

2-digit Friedman numbers are the easiest to find, although there are less of them than 3-digit Friedman numbers.

Working in base 10 Let’s represent a 2-digit number by 10m + n, where n is an integer from 0 to 9. Now, we only need to check each possible combination of m and n against the equalities:

10m + n = m^n and 10m + n = n^m 

We do not have to worry about m + n, m x n, m – n and m/n as these will always be smaller than 10m + n when n < 10.

To read more click here.

M x

New Books in Maths: October 2017

The Perfect Bet: How Science and Math are Taking the Luck Out of Gambling

Author: Adam Kucharski

Release Date: September 26th 2017

In The Perfect Bet, mathematician Adam Kicharski tells the story about how experts have succeeded in “pull[ing] the rug out from under Lady Luck”. In the process they have revolutionised mathematics and science; Kucharski demonstrates how the search for theperfect bet has been crucial for “the scientific pursuit of a better world”

“An elegant and amusing account…. Anyone planning to enter a casino or place an online bet would be advised to keep this book handy.”

-Wall Street Journal

Goodreads

The Maths Behind…

Author: Colin Beveridge

Release Date: 5th October 2017

In this book, Colin Beveridge explores the maths behind over 60 everyday phenomena, including why traffic jams often turn out to have no cause when you get to the end of the queue and whether some lotteries might be easier to win than others.

The Maths Behind… takes a scientific view of our everyday world, giving answers to all the “niggling questions” in your life as well as to those that you never even thought of asking.

Foolproof, and Other Mathematical Meditations

Author: Brian Hayes

Release Date: 13th October 2017

In Foolproof, and Other Mathematical Meditations, Brian Hayes convinces the reader that mathematics is too important and too fun to be left only to mathematicians. Topics explores range from Markov chains to Sudoku. As a non-mathematician, he argues that maths is an essential tool to understand the world, whilst also being a world in itself filled “with objects and patterns that transcend earthly reality”.

“Hayes makes math seem fun. Whether he’s tracing the genealogy of a well-worn anecdote about a famous mathematical prodigy, or speculating about what would happen to a lost ball in the nth dimension, or explaining that there are such things as quasirandom numbers, Hayes wants readers to share his enthusiasm.”

-Amazon

M x

 

Surreal Numbers

Surreal numbers were first invented by John Horton Conway in 1969, but was introduced to the public in 1974 by Donald Knuth through his book ‘Surreal Numners: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness‘.

What are Surreal Numbers?

Surreal numbers are the ‘most natural’ collection of numbers that include both real numbers and the infinite ordinal numbers of Georg Cantor. The surreals have many of the same properties as the reals, including the usual arithmetic operations. Hence, they form an ordered field.

For a surreal number x we write x = {XL|XR} and call XL and XR the left and right set of x,respectively. These will be explained below.

Conway Construction

“Surreal numbers are constructed inductively as equivalence classes of pairs of sets of surreal numbers, restricted by the condition that each element of the first set is smaller than each element of the second set.”

– Wikipedia

Using the Conway construction, we construct the surreal numbers in stages along with an ordering ≤ such that for any two surreal numbers a and b either a ≤ b or b ≤ a.

Every number corresponds to two sets of previously created numbers, such that no member of the left set is greater than or equal to any member of the right set. Therefore, if x = {XL|XR} then for each xL ∈ XL and xR ∈ XR, xL is not greater than xR.

In the first stage of construction, there are no previously existing numbers so the only representation must use the empty set: { | } = 0.

Subsequent stages yield the following:

• {0|} = 1, {1|} = 2, {2|} = 3, etc;
• {|0} = -1, {|1} = -2, {|2} = -3, etc.

For more, click here.

M x

NEWS: Earliest Known Use of Zero?

“Today we take it for granted that the concept of zero is used across the globe and our whole digital world is based on nothing or something. But there was a moment when there wasn’t this number.”

-Marcus du Sautoy

So when was the number zero conceptualised?

Recently, scientists have traced the origins of zero to an ancient Indian text, called the Bakhshali manuscript, which has been housed in the UK since 1902. Radiocarbon dating has revealed that this script originated in the third or fourth century. This is about 500 years earlier than scholars previously believed.

The Bakhshali manuscript, which was first found by a farmer in 1881 in what is now Pakistan, is inscribed on 70 pieces of birch bark and contains hundreds of zeroes.

 

Front Page of Folio 16 dating back to 224-383 AD | Source: Guardian

Several ancient cultures independently came up with symbols for the concept of ‘nothing’, however the dot symbol in the Bakhshali script is the one that evolved into the hollow-centred version of the symbol that we use today.

“It also sowed the seed for zero as a number, which is first described in a text called Brahmasphutasiddhanta, written by the Indian astronomer and mathematician Brahmagupta in 628AD.”

-Guardian

For more, click here.

M x