Erdős Discrepancy Problem

Paul Erdos
Paul Erdos

Terrence Tao, a mathematician at UCLA, has recently – September 2015 – announced a proof to the Erdos Discrepancy Problem! This 80-year-old problem in number theory was posed by legendary Hungarian mathematician Paul Erdos. Having recently heard about this news, I was thrilled to be present at a time of such an exciting moment in mathematics, and concluded to quickly research about what this problem outlined. Overwhelmed by the complexity of mathematics presented on most websites that discuss this problem, I decided to summarise the problem in a blogpost for any budding mathematicians who are interested in these discoveries but, like me, do not yet have the mathematical capability to understand the nitty gritty details.

The Theorem

Let xn be a sequence and let C be a constant. Must there exist positive integers dk such that:

12afcfd778b08af8a2d187bde89f8362

Looking at this I was perplexed and so I decided to do a little further research. 

This simply states that if we have a sequence of numbers that is made up of 1 and -1, then we consider any finite sequence of length n spaced elements apart and take the sum of these numbers to find the discrepancy.

For example, if we look at this simple sequence with an obvious pattern:

1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, -1 etc.

Then if we

  • Start on the third number (or ‘element’) – 1
  • Chose a spacing of 2 – d = 2
  • Chose a length of 6

the discrepancy will be

1 – 1 + 1 + 1 – 1 + 1 + 1 = 3

This conjecture states that given a sequence xn, then for any integer C>0, there exists a subsequence xd, x2d, x3d,… xkd for some choice of positive integers k and d such that desequation

(the sum of these numbers -the discrepancy – is greater than C)

If you’re still confused then below I’ve presented a very good analogy that presents a simplified version of this problem, which I got from this article.

Imagine that you are imprisoned in a tunnel that opens out onto a precipice two paces to your left, and a pit of vipers two paces to your right. To torment you, your evil captor forces you to take a series of steps to the left and right. You need to devise a series that will allow you to avoid the hazards — if you take a step to the right, for example, you’ll want your second step to be to the left, to avoid falling off the cliff. You might try alternating right and left steps, but here’s the catch: You have to list your planned steps ahead of time, and your captor might have you take every second step on your list (starting at the second step), or every third step (starting at the third), or some other skip-counting sequence. Is there a list of steps that will keep you alive, no matter what sequence your captor chooses?

In this brainteaser, you can plan a list of 11 steps that protects you from death. But if you try to add a 12th step, you are doomed: Your captor will inevitably be able to find some skip-counting sequence that will plunge you over the cliff or into the viper pit.

Around 1932, Erdős asked, in essence, what if the precipice and pit of vipers are three paces away instead of two? What if they are N paces away? Can you escape death for an infinite number of steps? The answer, Erdős conjectured, was no — no matter how far away the precipice and viper pit are, you can’t elude them forever.

TerryTao-200x300
Terrance Tao

This problem has shown to be very difficult to prove. However, on September 17 2015, Field’s Medalist Terrance Tao posted a paper on arXiv announcing his proof for this conjecture.

So how did he do it? Tao measured the ‘entropy‘ of mathematical objects called multiplicative functions or sequences, which are deeply connected to the Erdos Discrepancy Problem, as well as problems in number theory, such as the distribution of the prime numbers.

On Tao’s solution, Andrew Granville – British number theorist at the University of Montreal and University College London – said: “it should be an immediate observation, but somehow it had to take vast amounts of deep ideas and cleverness to get there.”

The Millennium Prize Problems

As a young girl, I always dreamed of winning a Nobel Prize. Now, you can imagine my disappointment when, as a slightly older teenager interested in maths over science, I discovered the sad truth that in fact there was no Nobel Prize in mathematics. As soon as I learnt of The Millennium Prize Problems (thanks dad!), they quickly became my dream – I was going to prove one when I was older. So inspired by this dream, I have read books and watched countless documentaries on the proof of Fermat’s Last Theorem, Poincaré’s Conjecture and so on.

But what are the Millennium Prize Problems?

The Millennium Prize Problems are seven problems in mathematics, set by the Clay Mathematics Institute at the start of this century – 2000. The Prizes were created to record some of the most challenging problems in mathematics, to increase the awareness of mathematics to the general public and emphasise the importance of working towards a solution of the most difficult problems. Six problems still remain unresolved.

Although for many mathematicians, money is not their motivation for the work that they do, it is worth saying that $1 million is given to the individual who solves each problem.

The Millennium Prize Problems are:

  • Poincaré Conjecture (solved)
  • Birch and Swinnerton-Dyer Conjecture
  • Hodge Conjecture
  • Navier-Stokes Equation
  • P vs NP Problem
  • Riemann Hypothesis
  • Yang-Mills and Mass Gap

Poincaré Conjecture

Formulated in 1904 by Henri Poincaré, the Poincaré conjecture deals with the branch of math called topology. It states that  “every simply connected closed three-manifold is homeomorphic to the three-sphere”. What does this mean?

poincare conjectureImagine stretching a rubber band around the surface of a ball. If we shrink this rubber band, it will shrink down to a point without tearing it or allowing it to leave the surface of the ball. This means that the surface of the ball is ‘simply connected’. A good example of an object that isn’t simply connected is a doughnut, as there is no way of shrinking the rubber band to a point without breaking the band or the doughnut. Poincaré saw that the 2-dimensional sphere is characterised by this property, and so any 2-dimensional object that was simply connected could be deformed and shaped into a sphere, without breaking it apart. He then went on to conjecture that the same would be true in 3-dimensions.

Grigori Perelman
Grigori Perelman

This proved extremely difficult to show; it took almost a century for a solution to be found. In 2002 and 2003, Russian mathematician Grigori Perelman posted a series of papers on arXiv, which have withstood intense scrutiny by the mathematical community for the past four years. In his proof, Perelman used Richard Hamilton’s theory of Ricci flow, and made use of results on spaces of metrics due to Cheeger, Gromov, and Perelman himself.

I would recommend watching this video for more information.

Birch and Swinnerton-Dyer Conjecture

This conjecture is in the field of number theory and is named after Bryan Birch and Peter Swinnerton-Dyer who developed the conjecture during the first half of the 1960s. As of 2015, only special cases of the conjecture have been proven correct.

The conjecture focuses on describing whole number solutions to algebraic equations like:

Screen Shot 2015-09-18 at 4.55.58 PM

Although Euler managed to find the complete solution for this equation, with more complicated equations this becomes very difficult; in 1970 Yu. V. found that there is no general method to finding solutions to these types of equations.

Birch and Swinnerton-Dyer
Birch and Swinnerton-Dyer

When the solutions to these equations are the points of an abelian variety (a complete algebraic variety whose points form a group), the Birch and Swinnerton-Dyer conjecture says that the size of the group of rational points is related to the behaviour of an associated zeta function ζ(s) near the point s=1. Specifically, it asserts that if ζ(1) is equal to 0, then there are an infinite number of rational points or solutions, and conversely, if ζ(1) is not equal to 0, then there is only a finite number of such points.

Hodge Conjecture

William Hodge
William Hodge

Formulated by Scottish mathematician William Hodge between 1930 and 1940, this conjecture questions how well we can approximate the shape of a given object by gluing together simple geometric building blocks of increasing dimension. Due to the usefulness of this technique, it has been generalised in many different ways, thus developing powerful mathematical tools exploited by mathematicians. However, unfortunately the geometric origins became lost in these generalisations.

The Hodge conjecture states that for particularly ‘nice’ spaces, which are called projective algebraic varieties, the pieces called Hodge cycles are actually combinations of geometric pieces called algebraic cycles.

efa77cacaaafe21e6917b95a1ffd6dd6

Navier-Stokes Equation

This problem in mathematical physics deals with the motion of fluid and viscous fluids, for example, waves and turbulent air currents. The solutions to the Navier-Stokes equations are believed to explain and predict the motion of such fluids. However, although these equations were written down in the 19th century, our understanding of them is still primitive and hence the challenge in to make significant progress toward a solid mathematical theory.

P vs NP Problem

I’ve always found this problem fascinating, as I genuinely do not know how you would even start to think of a solution it. It is a problem in computer science and asks: can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? So, the problem is to determine whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure.

P and NP refer to thee two types of maths problems:1000px-P_np_np-complete_np-hard.svg

  • P problems are fast for computers to solve,and so are considered “easy”.
  • NP problems are fast and therefore easy for a computer to check, but are not necessarily easy to solve.

So far no one has managed to prove that there is a problem whose answer cannot be feasibly generated with the help of a computer.

Riemann Hypothesis

This is the Millennium Prize problem that I find the most intriguing, as it involves prime numbers. To me, Riemann was a genius.

Although the distribution of such prime numbers among all natural numbers does not follow any regular pattern, Riemann noted that the frequency of prime numbers is very closely related to the behaviour of an elaborate function called the Riemann Zeta function:

Screen Shot 2015-09-18 at 5.38.47 PM

In 1859, Riemann hypothesised that all non-trivial solutions of the equation ζ(s) = 0 lie on a certain vertical straight line: real-part = 1/2. riemann1

This has been checked for the first 10,000,000,000 solutions. A proof that it is true for every interesting solution would shed light on many of the mysteries surrounding the distribution of prime numbers, and could possibly be disastrous for RSA encryption.

Although it is hard to explain and understand, I would recommend reading ‘Music of the Primes’ by Marcus du Sautoy as this book helped me truly grasp this problem. This video is also worth watching.

Yang-Mills and Mass Gap

This is another problem in the field of mathematical physics, which deals with quantum physics. Yang and Mills introduced a way to describe elementary particles using structures that also occur in geometry, which is called Quantum Yang-Mills theory, and is now the foundation to most elementary particle theory. Its predictions have been test by experiment, but the mathematical foundations are still shaky and remain unclear. The success of the theory relies on a property called the ‘mass gap’, which is that quantum particles have positive masses, even though the classical waves travel at the speed of light. The problem is to therefore establish the existence of the Yang-Mills Theory and mass gap theoretically using mathematics.

Don’t be discouraged if you don’t understand fully what these mean, I myself don’t either! I’m no expert, I just personally find them fascinating and I love learning about them.

Let me know which problem you find the most interesting! M x

Follow my blog with Bloglovin

Maths in the Media

I was inspired to write a blog post after reading this article about Maths in the media. Why is it that it’s so rare to see a news article on pure mathematics, even in Scientific magazines? I often find myself scouring the science section in the magazine shops, only to be disappointed by the lack of articles on maths (although I do manage to get sucked in by the astronomy and quantum physics headlines!). It’s frustrating, as a maths student, that the only real form of media that popularises mathematics are books. These can often be long and tedious to read and sometimes all I want is to dedicate 30 minutes to reading a good magazine!

The article seems to blame the lack of media coverage on maths on the difficulty for non-mathematicians to understand published papers on pure mathematics. Granted, even as an A-level student I still find it hard to find papers that I can understand! However, pure maths doesn’t have to be scary – there are plenty of topics that are easily accessible to anyone, for example cryptography, and plenty of authors who present these topics in a clear and concise manner, including Simon Singh. Also, maths is interesting! In fact, most people that I know (including my sister who is an English Literature student) find stories about maths, which veer away from the maths we learn at school, intriguing. The problem is that often it’s not applicable to our everyday lives; as beautiful as maths can be, the fact that it’s not “immediately practical”, as the article puts it, makes it harder to justify publishing articles on these  stories that have “little connection to a reader’s daily life”.

Due to the difficulty to find sources that would keep me up to date with the latest news in mathematics, without having to read journals and published papers that I can’t understand with my level of maths, I searched the internet and found quite a few websites:

I hope this is helpful for any of you budding mathematicians out there!

Let me know which one is your favourite website or if you have any other suggestions! M x

Follow my blog with Bloglovin

Modern Mathematicians: Maryam Mirzakhani

Maryam MirzakhaniMaryam Mirzakhani, an Iranian mathematician at Stanford University, became the first women to win the Field’s Medal in 2014. The Field’s Medal is the most prestigious prize in mathematics (I like to refer to it as the ‘Nobel Prize’ of mathematics), and was established in 1936.

Although as a young child Mirzakhani’s dream was to become a writer, she recalls her earliest memory of mathematics in an interview with The Guardian:

My first memory of mathematics is probably the time that he told me about the problem of adding numbers from 1 to 100… The solution was quite fascinating for me. That was the first time I enjoyed a beautiful solution, though I couldn’t find it myself.

I found this fascinating as I can truly relate to what Mirzakhani is saying. A question, which may appear difficult to solve, may have a simple solution, only found using mathematical tools. Such simple solutions hold such elegance and beauty to me, which I feel is common amongst those who love maths.

My favourite quote by Mirzakhani from her interview with The Guardian is “the more I spent time on mathematics, the more excited I became”, as I feel that Mirzakhani is describing something magical: the more you know about mathematics and the more tools you have to solve problems, the more intriguing the questions become. I have found this whilst studying my A-Levels, the more advanced the material becomes, the more I engage with it and develop a deep love for mathematics.

Mirzakhani has given Maryam Mirzakhani winning Fields Medalmany original contributions to the fields of geometry and dynamical systems, particularly in understanding the symmetry of curved surfaces, such as spheres, the surfaces of doughnuts and of hyperbolic objects. Although her work is considered ‘pure mathematics’ and is mostly theoretical, it could impact the theoretical physics of how the universe came to exist and, as it could inform quantum field theory, impact engineering and material science. Within mathematics, it has implications for the study of prime numbers and cryptography.

Although Mirzakhani’s work is too complex for me to understand, this video summarises it nicely and I would highly recommend you watch it.

Finally, the fact that she was the first woman awarded the Field’s Medal makes her a great role model for any aspiring women mathematicians and scientists. Personally, it is women like her that truly encourage me to continue to pursue mathematics as a career, despite the great gender imbalance (according to The Washington Post, just 9% of tenure-track positions in math are held by women!). However, slowly the numbers are rising, and so to mirror this, I think its very important to have these strong women role models in STEM subjects.

This is a great honour. I will be happy if it encourages young female scientists and mathematicians. I am sure there will be many more women winning this kind of award in coming years.

Let me know what other modern mathematicians I should research! M x

Follow my blog with Bloglovin

Mathematical Proof

As mentioned in a previous post, I find mathematical proof truly beautiful. To me, the timelessness of a theorem once it has been proved is truly unique to mathematics; work done by mathematicians who lived thousands of years ago still holds true today and is a vital component to modern day mathematics.

There are many ways to go about mathematical proof, and I would like to highlight three: proof by contradiction, proof by induction and direct proof.

Proof by Contradiction

To prove something by contradiction, we assume that what we want to prove is not true, and then show that the consequences of this assumption are not possible. This method of proof was favoured and skilfully used by Greek mathematicians.

One well-known use of this method is the proof that the square root of 2 is irrational:

q1

Source

Proof by Induction

I only learnt this form of proof when I studied Further Pure Mathematics 1 in AS Levels last year. However, I had come across the term when I read Simon Singh’s book ‘Fermat’s Last Theorem’, as it was using this technique that Andrew Wiles proved this theorem.

So how do we prove by induction?

inductionSuppose we have a statement P(n) about natural numbers, that may be true for some natural numbers n.

  1. Firstly, we must show that the first case (normally P(0) or P(1)) is true.
  2. We then suppose that P(n) is true.
  3. If we can then show that P(n+1) is true, P(n) must be true for all n greater or equal to the first case.

This works as, say we know that P(1) is true and P(n+1) is true, this signifies that P(1+1) = P(2) is true, which means P(2+1) = P(3) is true and so on until infinity.

Example:

0c48772687593b1491eb841151024671

  •  Show the statement holds true for P(0)

9006fc5bd9ccf49933f0e448e9725878

LHS = RHS, therefore true for P(0).

  • Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

Assume P(k) is true

c77cf1458332a342f78c3e4bde0fc587

Using this assumption, the left-hand side can be rewritten to:

b776bf5b11d1747d53d9405d17377294

Thus,

fff8f8c3a48949c7142c4cb3827b9b8f

Showing that P(k+1) is true, if P(k) is true.

Source

Direct Proof

To prove a theorem directly we start with something known to be true and then proceed by making small logical steps, which are clearly correct, until arriving at the desired result. So, because the starting point was true and each small step clearly correct, we know the result to be true. This is perhaps the most classic way to prove a theorem, however this method can be quite challenging, as breaking down a mathematical argument into small steps requires patience and clear thinking. Personally, I find this the hardest form of proof, as I never know where to start!

An example of this method being employed is in the proof of the formula for the roots of a quadratic equation:

Screen Shot 2015-09-06 at 5.01.15 PMScreen Shot 2015-09-06 at 5.01.23 PM

Source

Let me know your favourite proofs in the comments below! M x

Further Reading:

Collection of proofs

Article by Economist: ‘Proof and Beauty’

Follow my blog with Bloglovin

Modern Mathematicians: John Horton Conway

I have read many books about famous mathematicians, such as Pythagoras or Gauss, who lived many years ago, however I know little about modern mathematicians. So, I had the idea to start a series where I talk about those at the forefront of today’s research. To start, I choose John Horton Conway.

John ConwayJohn Horton Conway had been described as possibly the most charismatic mathematician of the modern day. Having studied a wide array of topics throughout his career, it is hard to condense his achievements into a small blurb.

However, perhaps the three most significant are his contribution to group theory, his creation of surreal numbers and his invention of the Game of Life.

Contributions to Group Theory

In 1965, John Leech found a dense packing of spheres in 24 dimensions, which is now known as the Leech lattice. Conway was able to show that the symmetry group G of the Leech lattice was an undiscovered finite simple group of order 8,315,553,613,086,720,000, when factored by a central subgroup of order 2. To understand the magnitude of this discovery just remember that Conway was working in 24 dimensions, meaning that he wasn’t just working with simple (x,y) coordinates, but with 24-dimensional coordinates (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)!

Creation of Surreal Numbers

In 1969, Conway discovered the surreal numbers, showing how even the number systems are a continuously evolving topic. The real charm of this discovery is that Conway was actually not trying to develop number systems, but rather was analysing the game of Go. He noticed that at the end of a game appeared like the sum of a lot of smaller games. By spotting the similarity of this behaviour in games in the behaviour of numbers, surreal numbers were born.

The Game of Life

Outside the world of mathematics, Conway is best known for his invention of the Game of Life – a cellular automation. The Game of Life is a zero-player game, which means that the evolution of this ‘game’ is determined by the starting conditions and requires no further input. Hence, the ‘player’ plays the game by inputting the initial conditions and then seeing how it evolves. More ‘advanced players’ may observe patterns by setting specific initial conditions and properties.

However, surprisingly Conway almost regrets creating the game expressing:

“Well, because I am pretty egotistical. When I see a new mathematical book for a general audience, I turn to the index, I look for a certain name in the back, and if I see this name, it shines out at me somehow. And it says, page 157, pages 293-298, or whatever. So I eagerly turn to those pages, hoping to see some mention of my discoveries. I only ever see the Game of Life. I am not ashamed of it; it was a good game. It said things that needed to be said. But I’ve discovered so many more things, and that was, from a certain point of view, rather trite—to me anyway. It is a bit upsetting to be known for this thing that I consider in a way rather trivial. There are lots of other things to be discovered about surreal numbers. And the Free Will Theorem is recent, and therefore I am still flushed with enthusiasm about it.

(From an Interview of John H.Conway by Dierk Schleicher published by the AMS.)

What now?

More recently, Conway founded the Free Will Theorem jointly with Simon Kochen. This theorem states, “if there exist experimenters with (some) free will, then elementary particles also have (some) free will.” Put simply, if some experimenters are able to behave in a way that is not completely predetermined (independent of the past) then the behaviour of elementary particles is also not a function of their prior history.

Further Reading

Guardian Article

Numberphile Video

The New York Times Article

Let me know who your favourite modern mathematician is below! M x

Follow my blog with Bloglovin

Autor Focus: Simon Singh

Simon Singh, a British popular science writer, was born in Somerset, England. I first came across his books when browsing through the mathematics section of my local bookshop, where I spotted ‘Fermat’s Last Theorem’.

51VG3HQ8HVLFermat’s Last Theorem

Written almost like a detective novel, I fell in love with Simon Singh’s way of writing and effortless ability to explain complex mathematics in a clear and simple way, understandable even to those with little mathematical background. Needless to say, I quickly devoured this book, gaining a deep interest and love in the art of mathematical proof and the rigour and intellect involved to turn a conjecture into a theorem.

“I have discovered a truly marvellous proof, which this margin is too narrow to contain…”

It was with these words that 17th century French mathematician Pierre de Fermat started the quest to seek out a proof to the seemingly simple theorem:

There are no three positive integers x, y and z

Picture1

for which for any integer n > 2.

ob_db3f72_wiles3
Andrew Wiles after announcing he proved Fermat’s Last Theorem, 1994.

To me, the true beauty of this theorem is how easily understandable it is, but how intensely difficult it was to prove it, baffling the finest mathematicians for centuries, until finally it was proved by Andrew Wiles in 1994.

I highly recommend this book for those who are fascinated by mathematical proof, like me, as I feel it truly depicts the full historical journey of how such a problem was solved in a clear and engaging way. Whilst reading the book, I learnt about the work of an array of brilliant and important mathematicians which all contributed to the final proof, which Singh managed to deliver in a lighthearted and interesting manner.

The Code Book
The Code BookI had been searching for a book about Cryptology for a while, so you can imagine that I was extremely excited to find that Singh had written a book on this called ‘The Code Book’, as I had greatly enjoyed reading ‘Fermat’s Last Theorem’. In this book, Singh scrolls through history, touching upon topics such as the story of Mary, Queen of Scots, Arabic cryptography, Charles Babbage, the Enigma machine, and the decryption of Linear B and other ancient writing systems. He also highlights more recent issues, such public-key cryptography and the significance of the development of quantum computers. However, to me the most fascinating part of the book was the detailed description of the Navajo Code Talkers who helped the Allies win World War II, as this was something that I had truly no idea about, but yet was so crucial towards the American cryptography during the war, especially against the Japanese. It was through this story, and others such as James Ellis, Clifford Cocks, Malcolm Williamson (supposedly were the first to develop public-key cryptography, although this did not become public knowledge until the research was declassified by the British government in 1997) and Alan Turing’s, that I was made fully aware of the secrecy surrounding achievements in cryptography and the injustice it may bring towards these individuals.

Simon Singh
Simon Singh

What was truly special about this book was the ingenious mixture of clear technical and mathematical explanations of a variety of different codes with the description of historical events, peppered with intriguing anecdotes of the code makers and breakers. I must say that, after reading this book, I consider cryptography one of my favourite areas in mathematics and really want to learn more about it. Once again, Singh demonstrated his unique ability to make a rather complex topic understandable as well as entertaining, making this book another ‘must read’ for any budding mathematician.

(Side Note: On a trip to the University of Southampton, I was surprised, but delighted to see this book displayed in the mathematics admissions tutor’s bookshelf!)

What’s Next?

I have only read two of his five books, but having absolutely loved them I am keen to read his others.

Do you have any special recommendations on which I should purchase next? M x

Follow my blog with Bloglovin