mathematics

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

VIDEO: Spiral Sculptures

John Edmark is an artist and professor at Stanford University who has used the Golden Angle to sculpt spirals. The Golden Angle is derived from the Golden Ratio: it is the smaller of the two angles created by dividing the circumference of a circle according to the golden ratio and comes out to be around 137.5°.

For more click here.

M x

Knapsack Problem

The knapsack problem is a problem in combinatorial optimisation.

Imagine you are going to visit your friends for whom you have bought lots of presents. So many, in fact, that you can’t fit them all in your luggage meaning you must leave some behind. If we decide to pack a combination of presents with the highest value but that doesn’t exceed the weight limit imposed by airline, how can we find such a combinations? This is the Knapsack Problem.

File:Knapsack.svg

Source: Wikipedia

We could solve this by trying all the possible combinations, calculating their value and weight and then picking one that is below the weight limit but maximises the value. Whilst this is okay when we are dealing with a small number of items, it is simply unfeasible when the number of items is large as the number of combinations is too big. So, is there an algorithm which can work for any number of items that doesn’t take too long?

Computer scientists have a way of measuring the complexity of a problem by how fast the time taken grows as the size of the input increases. Polynomial growth, i.e. if the size of the input is n then the time taken grows by a factor of n^k, describes and ‘easy problem’; the growth is nowhere near as “explosive” as  exponential growth, e.g. 2^n.

Whether or not a polynomial time algorithm exists to solve the knapsack problem is unknown, meaning it is in a class of problems called NP-Hard Problems.

Complexity classes

Source: plus.maths.org

Complexity Classes:

  • Class P: problems that can be solved in polynomial time
  • Class NP: a potential solution can be checked in polynomial time
    • NP-Complete: within the NP class but particularly hard
    • NP-Hard: as least as hard as the NP class.

It is possible that the NP class = P class, though this is still unknown (and is one of the Millennium Prize Problems), hence the two diagrams above.

M x

P.S. My posts may be more sporadic in the next month because I’m in exam term!

Physics and Riemann Hypothesis?

Researchers have recently discovered that solutions to the Riemann zeta function correspond to the solutions of another function that may make it easier to solve the Riemann hypothesis.

Dorje Brody, a mathematical physicist at Brunel University London, says that “to our knowledge, this is the first time that an explicit—and perhaps surprisingly relatively simple—operator has been identified whose eigenvalues [‘solutions’ in matrix terminology] correspond exactly to the nontrivial zeros of the Riemann zeta function“.

Now what remains to be proven is that all of the eigenvalues are real numbers rather than imaginary ones.

This newly discovered operator has close ties with quantum physics. In 1999, Michael Berry and Jonathan Keating made the conjecture (now called the Berry-Keating conjecture) that if such an operator exists, then it should correspond to a theoretical quantum system with particular properties. However, no one has ever found such a system before now.

In general, mathematicians are optimistic that the eigenvalues are actually real, and there is a strong argument for this based on PT symmetry (a concept from quantum physics which says that you can change the signs of all four components of space-time and the result will look the same as the original).

Source

Click here for more on the Riemann hypothesis. M x

200th post!

I can’t believe this is my 200th post! Thank you all so much for your continued support of my blog. I really enjoy learning about different topics and sharing my love of Maths with other people through my blog posts. I thought for my 200th post I would list my top 5 recent blog posts, whether that be from the attention and positive feedback they received or simply because I really enjoyed writing them:

  • Mandelbrot and Julia Sets
    • As a pure maths lover, I can’t help but be fascinated by Mandelbrot and Julia sets, thus when I discovered a connection between them I couldn’t help but write a blog post about it (plus the pictures are really pretty!).
  • Frieze Groups
    • After completing a project on Frieze groups, I thought I would create a little summary on what they are and where we can see them in real life!
  • Maths and Biology: Viruses
    • This is one of my most applied blog posts, and I was really proud of it as I felt that I pushed myself out of my comfort zone in researching an area of Mathematics I was completely unfamiliar with.
  • Maths on Trial
    • This blog post was inspired by a talk I attended, given by Leila Schneps, and really enjoyed. Rest assured I’ll be buying the book soon!
  • Unsolved Problems: Part 1 and Part 2
    • I am a big fan of writing series of blog posts, as you have probably guessed by now! My series on unsolved problems in Mathematics was one I really enjoyed researching about as it includes a variety of problems from different areas of maths.

I’d love to know what your favourite blog post that I have written recently is! M x

 

Pascal’s Triangle

Pascal’s triangle is filled with a wealth of interesting patterns, something I never learnt during secondary school when first introduced to this mathematical object. In this post, inspired by a Numberphile video, I want to show you some of these patterns that you might have never seen before.

Firstly, what is Pascal’s Triangle?

Pascal’s triangle is a triangular array of the binomial coefficients.

Pascal's triangle

To construct Pascal’s triangle, start with the two top rows, which are 1 and 1 1. To find any number in the next row, add the two numbers above it.

 

At the beginning and end of each row, where there is only one number above, write 1.

Symmetric

Pascal’s triangle is symmetric, a fact which follows directly from the formula for the binomial coefficient:

Screen Shot 2017-03-23 at 8.32.55 AM.png

It can also be seen by how the triangle is constructed, i.e. “by the interpretation of the entries as the number of ways to get from the top to a given spot in the triangle“.

Sum of entries in row n equals 2n

 

This fact can be proved by induction. The main point of the argument is that each entry in row n is added to two entries below. This gives us:

Screen Shot 2017-03-23 at 8.35.30 AM.png

Hence, the sum of entries in row n+1 is twice the sum of entries in row n.

Hockey Stick Pattern

In Pascal’s words: “In every arithmetical triangle each cell is equal to the sum of all the cells of the preceding row from its column to the first, inclusive”. This is easier to explain using a diagram:

Mathematically, this can be proved by induction and is denoted in the following way:

Screen Shot 2017-03-23 at 8.38.18 AM

Fibonacci Numbers

To see this, let us first rearrange Pascal’s triangle.

another form of Pascal's triangle

The successive Fibonacci numbers are the sums of the entries on the marked diagonals:

1 = 1

1 = 1

2 = 1 + 1

3 = 1 + 2

5 = 1 + 3 + 1

8 = 1 + 4 + 3

13 = 1 + 5 + 6 + 1

etc.

e

Recently, the Harlan brothers highlighted that e is hidden in Pascal’s triangle. This was discovered by considering products rather than sums.

 row products in Pascal Triangle

Denoting Sn as the product of the terms in the nth row, as n tends to infinity, we find that:

Screen Shot 2017-03-23 at 8.43.46 AM

Click here for the derivation.

Catalan Numbers

Catalan numbers can be found in Pascal’s triangle in a few ways, for example:

  • If you take each ‘middle’ element and subtract its adjacent entry, you get a Catalan number.

  • If you take a middle element and divide it by its position in the list of middle terms (e.g. divide the 5th middle term by 5), you will get a Catalan number.

 

There are many more patterns, and I encourage you to find out more about them! M x

Ulam Spiral

The Ulam Spiral, discovered in 1963 by Stanislaw Ulam, is a graphical depiction of the set of prime numbers.

If you were to arrange the positive numbers in a spiral, starting with one at the centre, then circle all of the prime numbers, what would you get? As prime numbers don’t have a predictive structure, you would expect to get little or even nothing out of arranging the primes this way. But, Ulam discovered something incredible:

i-aa21847004619e9491df4d005b0ce86c-ulam200.png

Ulam Spiral

To his surprise, the circled numbers tended to line up along diagonal lines. In the 200×200 Ulam spiral shown above, diagonal lines are clearly visible, confirming the pattern. Although less prominent, horizontal and vertical lines can also be seen.

Even more amazing, this pattern still appears even if we don’t start with 1 at the centre!

There are many patterns on this plot. One of the simplest ones is that there are many integer constants b and c such that the function:

f(n) = 4 n^2 + b n + c
generates, a number of primes that is large by comparison with the proportion of primes among numbers of similar magnitude, as n counts up {1, 2, 3, …}.

M x