NEWS: World’s Largest Proof

Recently, a trio of mathematicians – Marijn Heule from the University of Texas, Victor Marek from the University of Kentucky, and Oliver Kullmann from Swansea University – have solved a problem in mathematics and the solution takes up 200 terabytes of basic text (just consider the fact that 1 terabyte can hold 337,920 copies of War and Peace)! This breaks the previous recorded of a 13-gigabyte proof, which was published in 2014.

The mathematics problem is named the ‘Boolean Pythagorean Triples problem’, and was posed by Ronald Graham in the 1980s, who offered a $100 prize for the solution.

The problem is part of Ramsey theory and asks:

“Is it possible to colour all the integers either red or blue so that no Pythagorean triple of integers a, b, c, satisfying a^2+b^2=c^2 are all the same colour. For example if you would colour a and b red, and c blue, this would successfully not satisfy the tested triple, but all triples would have to be tested.”

Andrew Moseman from Popular Mechanics details how:

“What makes it so hard is that one integer can be part of multiple Pythagorean triples. Take 5. So 3, 4, and 5 are a Pythagorean triple. But so are 5, 12, and 13. If 5 is blue in the first example, then it has to be blue in the second, meaning either 12 or 13 has to be red.

The proof found that it is only possible to colour the numbers in such a way up to the number 7,824 and that 102,300 such colourings exist. Hence, there is no solution to the problem question. The proof took a supercomputer two days to solve, and generated 200TB of data!

The paper describing the proof was published on arXiv on the 3rd of May 2016.

Although the computer has proved that the colouring is impossible, it has not provided the underlying reason why this is, or explored why the number 7,824 is important. This highlights the objection to the value of computer-assisted proofs; yes, they may be correct, but to what extent are they mathematics?

Sources: 1 | 2

Let me know what you think of computer assisted proofs below! M x

Boolean Algebra

Today I thought I would give you a short introduction on Boolean Algebra.

George Boole color.jpg
George Boole

Boolean Algebra was named after the English mathematician, George Boole (1815 – 1864), who established a system of logic which is used in computers today. In Boolean algebra there are only two possible outcomes: either 1 or 0.

It must be noted that Boolean numbers are not the same as binary numbers as they represent a different system of mathematics from real numbers, whereas binary numbers is simply a alternative notation for real numbers.

Operations

Boolean logic statements can only ever be true or false, and the words ‘AND’, ‘OR’ and ‘NOT’ are used to string these statements together.

OR can be rewritten as a kind of addition:

0 + 0 = 0 (since “false OR false” is false)
1 + 0 = 0 + 1 = 1 (since “true OR false” and “false OR true” are both true)
1 + 1 = 1 (since “true OR true” is true)

OR is denoted by:

Screen Shot 2016-05-04 at 5.49.41 PM.png

AND can be rewritten as a kind of multiplication:

0 x 1 = 1 x 0 = 0 (since “false AND true” and “true AND false” are both false)
0 x 0 = 0 (since “false AND false” is false)
1 x 1 = 1 (since “true AND true” is true)

AND is denoted by:

 Screen Shot 2016-05-04 at 5.49.36 PM.png

NOT can be defined as the complement:

If A = 1, then NOT A = 0
If A = 0, then NOT A = 1
A + NOT A = 1 (since “true OR false” is true)
A x NOT A = 0 (since “true AND false” is false)

This is denoted by:

Screen Shot 2016-05-04 at 5.49.45 PM

Venn diagrams these operations | Source: Wikipedia

Expressions in Boolean algebra can be easily simplified. For example, the variable B in A + A x B is irrelevant as, no matter what value B has, if A is true, then A OR (A AND B) is true. Hence:

A + A x B = A

Furthermore, in Boolean algebra there is a sort of reverse duality between addition and multiplication, depicted by de Morgan’s Laws:

(A + B)’ = A‘ x B‘ and (A x B)’ = A‘ + B

Uses

 

In 1938, Shannon proved that Boolean algebra (using the two values 1 and 0) can describe the operation of a two-valued electrical switching circuit. Thus, in modern times, Boolean algebra is indispensable in the design of computer chips and integrated circuits.

Sources: 1 | 2 | 3