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.

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.

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!

The Abel Prize 2017 has been awarded to Yves Meyer of the École normale supérieure Paris-Saclay in France due to his “pivotal role in the development of the mathematical theory of wavelets”, which has applications in data compression, medical imagery and the detection of gravitational waves.

Meyer, aged 77, will receive 6 million Norwegian krone (around £600,000) for the prize, which aims to recognise outstanding contributions to mathematics. It is often called the ‘Nobel Prize’ of mathematics.

The Abel Prize was previously won by Andrew Wiles in 2016, who solved Fermat’s Last Theorem.

Biography

Yves Meyer, born on the 19th July 1939, grew up in Tunis in the North of Africa. After graduating from École normale supérieure de la rue d’Ulm in Paris and completing a PhD in 1966 at the University of Strasbourg, he became a professor of mathematics at the Université Paris-Sud, then the École Polytechnique and then Université Paris-Dauphine. He then moved to École normale supérieure Paris-Saclay in 1995, until formally retiring in 2008, although he still remains an associate member of the research centre.

Vera Rubin died on 25th December 2016, aged 88. Rubin was an American astronomer who pioneered work on galaxy rotation rates.

In the 1960s and 70s, Rubin and her collogue Kent Ford noted a discrepancy between the predicted angular motion of galaxies and their observed motion, whilst studying galactic rotation curves.

This led Rubin to conclude that some unseen mass must be influencing the rotation of galaxies. As a result, in an attempt to explain the galaxy rotation problem, the theory of dark matter was created. The existence of this ‘invisible mass’ was first theorised by Fritz Zwicky in the 1930s but until Rubin and Ford’s work it had not been proven to exist.

Although initially it was met with skepticism from the scientific community, Rubin’s results have been confirmed over the subsequent decades.

Emily Levesque from the University of Washington said in an interview with Astronomy magazine:

This discovery “utterly revolutionised our concept of the universe and our entire field.”

It is considered one of the most significant results of the 20th century.

However, Rubin never received the Nobel Prize for Physics, although she was frequently mentioned as a candidate for it. It has been 53 years since a women has won a Nobel Prize in Physics, and now that Vera Rubin has passed away, she is no longer eligible. But, we can take some consolation in the fact that Rubin was indifferent to not being nominated for the Nobel Prize.

“Fame is fleeting,” Rubin said in 1990 to Discover magazine. “My numbers mean more to me than my name. If astronomers are still using my data years from now, that’s my greatest compliment.”

The Breakthrough Prizes is awarded in three categories: Life Sciences, Fundamental Physics and Mathematics, in recognition of great scientific advance.

This year, the Breakthrough Prize in Mathematics was awarded to Belgian mathematician Jean Bourgain, for his “multiple transformative contributions to analysis, combinatorics, partial differential equations, high-dimensional geometry and number theory”.

He has published, on average, 10 papers a year tackling some of the most challenging problems in a range of mathematical fields. For example, his most recent work is on the decoupling theorem: whilst Pythagoras showed that the length of the two shorter sides of a right-hand triangle are related to the hypotenuse, the decoupling theorem, proven by Bourgain and Ciprian Demeter, shows a similar relationship in the superposition of waves.

“It is of course an immense honour for me to be awarded the Breakthrough Prize and also an occasion to thank all those who helped me along my career. Over the years I have been fortunate to interact with several truly exceptional individuals who introduced me to different subjects and from whom I learned a lot. Collaborations on all levels played an important part in my work and are greatly valued. Appointments at research institutions such as the Institut des Hautes Études Scientifiques in Bures/Yvette (France) and the Institute for Advanced Study in Princeton provided ideal conditions for a full dedication to mathematics. I am most grateful for their trust. Last but not least, thanks to my family for their love and continuous support over the years.” – Jean Bourgain

This years Shaw Prize in mathematics was awarded to Professor Nigel Hitchin, from the University of Oxford. This award was honoured to him due to “his far reaching contributions to geometry, representation theory and theoretical physics. The fundamental and elegant concepts and techniques that he has introduced have had wide impact and are of lasting importance.”

Hitchin’s innovative work has had a profound impact on a variety of areas in Mathematics, including algebraic geometry, differential geometry, complex analysis, topology, integrable systems, mathematical and theoretical physics.

One of his most notable achievements was deriving the self-duality equations, which are a “special class of solutions of the self-dual Yang-Mills equations“. He discovered that when described on a compact Riemann surface – a surface that can be covered by a finite collection of planes – a “surprisingly rich space of solutions” is produced.

A typical feature of Hitchin’s work is as follows: he proves that objects in theoretical physics define new concepts in algebraic or differential geometry, and then uses rigorous mathematics to produce powerful and elegant results.

Marta Mazzocco describes how

“… Hitchin defies the stereotype that mathematicians need to be in their early thirties to produce great results. When already in his sixties, Hitchin introduced the notion of co-Higgs bundle …“.

An apt winner of the Shaw Prize, I hope to hear of his work for many years to come.

Erwin Schrödinger was an Austrian theoretical physicist, born in 1887, who contributed largely to the wave theory of matter and other fields in quantum mechanics.

Schrödinger’s wide array of interests began at a young age; he not only liked scientific disciplines, but also admired the logic of ancient grammar and the beauty of German poetry. In 1906, he became a student at the University of Vienna, where he studied under Fritz Hasenöhrl, Boltzmann’s successor, and stayed there for 4 years. During these years, Schrödinger mastered eigenvalue problems in the physics of continuous media, thus laying the foundation for his future work.

In 1921, Schrödinger took up a position at the University of Zurich, where he stayed for 6 years. It was here that he enjoyed huge amount of contact and friendship with many of his colleagues such as Hermann Weyl and Peter Debye and it was one of his most fruitful periods. He actively engaged in various subjects in theoretical physics; his papers of that time deal with heats of solids, problems in thermodynamics and atomic spectra, as well as some physiological studies of colour.

WAVE EQUATION

His greatest discovery – Schrödinger’s wave equation – was conceived at the end of his time in Zurich (in the first half of 1926), and was published in Annalen der Physik in the paper entitled ‘Quantisierung als Eigenwertproblem’. This wave equation correctly calculated energy values for electrons in an atom. In the paper, Schrödinger gave a derivation of the wave equation for time-independent systems and showed that it gave the correct energy eigenvalues for a hydrogen-like atom. This paper has been celebrated as one of the most important achievements in quantum mechanics in the 20th century.

Schrodinger’s Equation | Source: phys.org

This result came as a result of his dissatisfaction with the quantum condition in Bohr’s orbit model and his belief that atomic spectra should really be determined by a eigenvalue problem.

Source: Wikipedia

“Schrödinger was breaking new ground and did the heroic job of getting the right equation. How you get the right equation, is less important than getting it. He did such a wonderful job of then deriving the hydrogen atom wave function and much more. So did he understand what he had? You bet, he was really right on target.”

– Marlan O. Scully, a physics professor at Texas A&M University

In 1927, he succeeded Max Planck at the Friedrich Wilhelm University in Berlin, where he met Albert Einstein. However, in 1934 Schrödinger decided to leave Germany due to the Nazis’ growing anti-semitism. As a result he moved to the United Kingdom, where he became a Fellow of Magdalen College in the University of Oxford. It was here that Schrödinger learned that he had won the 1933 Nobel Prize in Physics, sharing the award with Paul Dirac. In his Nobel Prize acceptance speech, Schrödinger stated that his mentor, Hasenöhrl, would be accepting the award if he hadn’t died during World War I.

POST NOBEL PRIZE

In 1939, he moved to work at Institute for Advanced Studies in Dublin, Ireland, heading its School for Theoretical Physics. He remained in Dublin until the mid-1950s, returning in 1956 to Vienna, where he continued his career at his alma mater.

In 1944, Schrödinger wrote the book ‘What is Life?‘, which contains a discussion on the negative entropy of living systems, and the concept of a complex molecule with the genetic code for living organisms. According to James Watson‘s memoir ‘The Secret of Life‘, this book gave him the inspiration to research this gene, leading to the discovery of the DNA double helix structure in 1953.

LEGACY

Sadly, in 1961 Schrödinger died in Vienna. To this day, Schrödinger is considered as the father of quantum mechanics. A few of his

During (and after) his lifetime, Schrödinger acquired many honours and awards apart from the Nobel Prize, including:

Max Planck Medal in 1937: awarded for extraordinary achievements in theoretical physics

Elected a Foreign Member of the Royal Society in 1949

The large crater Schrödinger, on the far side of the Moon, is named after him.

The Erwin Schrödinger International Institute for Mathematical Physics was established in Vienna in 1993.

Schrödinger’s Cat??

Many of you may recognise the name ‘Schrödinger’ due to Schrödinger’s cat, which is a though experiment devised by Schrödinger in 1935. The video below will help explain it:

Hope you enjoyed this post. Make sure to check out the first installment of this series on Richard Feynman! Please let me know if you have any requests on people or fields of maths which you would like me to talk about next! M x

In 1937, Lothar Collatz, a German mathematician, posed the famous Collatz conjecture, which remains unsolved today. Paul Erdős has offered $500 for its solution.

What is the Collatz Conjecture?

Take any positive number n:

If n is even, divide it by two;

If n is odd, triple it and add one.

In modular arithmetic notation, the function f is defined as:

Source: Wikipedia

Next, we form a sequence by repeating this over and over again, taking each result as the input for the next step.

The Collatz Conjecture states that:

“This process will eventually reach the number 1, regardless of which positive integer is chosen initially.”

The conjecture suggests that, regardless of the starting number, the sequence will always reach the number 1, and form a 4 – 2 – 1 loop which will repeat infinitely.

The total stopping time of n is defined as the smallest i such that a_{i} (the ith number of the sequence) is equal to one. If for some n, such an i doesn’t exist, then the conjecture is false – n has an infinite stopping time. However, no such n has been found.

Total stopping time of numbers from 1 – 9999 | Source: Wikipedia

Reverse Collatz

An alternative form of the conjecture is that 1 leads to all natural numbers using the reverse relation. However, we must remove the 1 – 2 – 4 loop (the inverse to the 4 – 2 – 1 loop). To avoid this, mathematicians substitute the relation 3n+1 of function f, by a ‘shortcut’ relation (3n+1)/2. Hence, the ‘Collatz Graph’, which is created as a result, is defined as follows:

Source: Wikipedia

Collatz Graph | Source: jasondavies.com

Proof?

This conjecture has been checked for all starting values up to 2^{60} . However, this brute-force method will only be sufficient as proof if the conjecture is false and a counterexample is found, as we cannot check an infinite amount of numbers in finite time.

In 2011, Gerhard Opfer posted a paper that claims to prove the Collatz Conjecture. However, it was later revealed that there was a flaw in the proof.

Importance of this Conjecture

The Collatz conjecture is one of the simplest open problems in mathematics; you can explain to all your non-mathematical friends or even small children and they will understand it. Despite its simplicity, it relates to not only number theory, but also to topics such as:

Chaos: in cellular automata;

Decidability: John Conway showed that similar questions are formally undecidable;

The foundations of mathematics and computation: Emil Post’s tag systems.

When I read about this conjecture I was fascinated by its simplicity, and it reminded me of Fermat’s Last Theorem in the sense that it is easy to understand but overwhelmingly difficult to prove.

What are your favourite undecided problems in mathematics? M x