Catalan’s Conjecture

Although popularly known as Catalan’s conjecture, this is in fact a theorem in number theory, proven by Preda Mihăilescu in 2002, 158 years after it was conjecture in 1844 by French and Belgian mathematician Eugène Charles Catalan.

The theorem states that the only solution in the natural numbers of

{\displaystyle x^{a}-y^{b}=1}

for a,b>1; x,y>0 is x = 3, a=2, y=2, b=3.

Catalan ‘Near Misses’ (i.e. xa – yb <= 10; 2 <= x,y,a,b <= 100; a,b prime)

  • 33 – 52 = 2
  • 27 – 53 = 3
  • 23 – 22 = 62 – 25 = 53 – 112 = 4
  • 25 – 33 = 5
  • 25 – 52 = 42 – 32 = 27 – 112 = 7
  • 42 – 23 = 8
  • 52 – 42 = 62 – 33 = 152 – 63 = 9
  • 133 – 37 = 10

Proving the Conjecture

Similarly to Fermat’s last theorem, the solution to this conjecture was assembled over a long period of time. In 1850, Victor Lebesgue established that b cannot equal 2. But then it was only after around 100 years, in 1960, that Chao Ko constructed a proof for the other quadratic case: a cannot equal 2 unless x = 3.

Hence, this left a,b odd primes. Expressing the equation as (x-1)(xa-1)/(x-1) = yb one can show that the greatest common divisor of the two left hand factors is either 1 or a. The case where the gcd = 1 was eliminated by J.W.S Cassels in 1960. Hence, only the case where gcd = a remained.

It was this “last, formidable, hurdle” that Mihailescu surmounted. In 2000, he showed that a and b would have to be a ‘Wieferich pair’, i.e. they would have to satisfy ab-1 ≡ 1 (mod b2) and ba-1 ≡ 1 (mod a2). In 2002,  he showed that such solutions were impossible!

Video

M x

12th Polymath Project

The Polymath Project is a collaboration among mathematicians to solve important problem in mathematics by providing a platform for mathematicians to communicate with each other on how to find the best route to the solution.

It began in January 2009 when Tim Gowers posted a problem on his blog and asked readers to reply with partial ideas or answers. This experiment resulted in a new answer to a difficult problem, proving the benefits of collaboration.

Previous Polymath projects that have successfully led to proofs incude the density version of the Hales-Jewett theorem and the Erdös discrepancy problem, as well as famously reducing the bound on the smallest gaps between primes.

Recently the 12th Polymath Project has started; Timothy Chow of MIT has proposed a new Polymath Project – resolve Rota’s basis conjecture.

What is the Rota’s Basis Conjecture?

The Rota’s Basis Conjecture states:

“If B1, B2,…., Bn are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n x n grid of vectors (vij) such that:

  1. the n vectors in row i are the members of the ith basis Bi (in some order), and
  2. in each column of the matrix, the n vectors in that column form a basis of V.”

Although easy to state, this conjecture has revealed itself hard to prove (like Fermat’s Last Theorem)!

M x

abc Conjecture

What is it?

The abc conjecture was first posed by Joseph Oesterlé in 1985 and David Masser in 1988. The conjecture begins by presenting 3 distinct positive integers a, b and that are relatively prime and satisfy the equation a + b = c. It states that, if the number d  is the product of the distinct prime numbers of abc, then d is usually much larger smaller than c. This product is defined mathematically as the ‘radical’ of abc and hence the conjecture can be expressed more formally as:

If a, b, and c are coprime positive integers such that a + b =c, it turns out that “usually” c < rad(abc). 

There are a few exceptions to this. To deal with this, the abc conjecture specifically states that:

For every ε > 0, there exist only finitely many triples (a, b, c) of coprime positive integers, with a +b = c, such that:

c>\operatorname {rad} (abc)^{1+\varepsilon }.

 

Consequences if it is TRUE

The abc conjecture is linked to many other questions in number theory; if it were to be true, then it would imply that many other conjectures are also true, including:

and many more.

Proof

 

In 2012, the Japanese mathematician Shinchi Mochizuki published a 500 page proof of the abc conjecture. However, it was so complex that no mathematicians could understand it due to the fact that it used a new mathematical framework known as inter-universal Teichmüller Theory. In a verification report published on December 2014, Mochizuki stated that

“With the exception of the handful of researchers already involved in the verification activities concerning IUTeich (inter-universal Teichmüller Theory) discussed in the present report, every researcher in arithmetic geometry throughout the world is a complete novice with respect to the mathematics surrounding IUTeich, and hence, in particular, is simply not qualified to issue a definitive (i.e., mathematically meaningful) judgment concerning the validity of IUTeich on the basis of a ‘deep understanding’ arising from his/her previous research achievements.”

However, a few weeks ago, four dozen mathematicians converged to hear Mochizuki present his own work at a conference in Kyoto University. This was a ‘breakthrough’ as described by Ivan Fesenko: “It was the key part of the meeting… He was climbing the summit of his theory, and pulling other participants with him, holding their hands.”

Now, around 10 mathematicians have a solid understanding of this new theory, giving a glimmer of hope for our future understanding of this proof.

Video

Sources: 1 | 2 | 3 | 4 | 5 | 6

M x

 

Collatz Conjecture

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:

 f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}
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 is defined as the smallest such that ai (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:

 R(n) = \begin{cases} \{2n\} & \text{if } n\equiv 0,1 \\ \{2n,(2n-1)/3\} & \text{if } n\equiv 2 \end{cases} \pmod{3}.
Source: Wikipedia

Collatz Graph | Source: jasondavies.com
Proof?

This conjecture has been checked for all starting values up to 260 . 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