Researchers edge closer to solving 270-year-old math problem thanks to grid computing

In the summer of 1742, Christian Goldbach, a famous Prussian mathematician and former tutor to Tsar Peter II, exchanged a series of letters with his friend, the great Swiss mathematician Leonhard Euler. Out of this exchange came the Goldbach conjecture, which in its simplest form states: "every even integer greater than 2 can be written as the sum of two primes".

For example:
4 can be expressed as 2 + 2,
6 can be expressed as 3 + 3,
8 can be expressed as 3 + 5,
10 can be expressed as 5 + 5 or 7 + 3,
12 can be expressed as 5 + 7,
14 can be expressed as 3 + 11 or 7 + 7,
16 can be expressed as 3 + 13 or 5 + 11, etc.

Despite the simple formulation of this conjecture, it is notoriously difficult to find a proof; 270 years later, one still remains to be found. While there have been numerous attempts at providing one, the most recent high-profile effort having been published in the ArXiv just two months ago, none have thus far been accepted by the wider mathematical community In fact, such has been the difficulty in finding a rigorous mathematical proof that in 1992, UK publishing company Faber and Faber offered $1,000,000 to anyone who could provide a compelling proof within the decade. However, the prize went unclaimed.

The stunt was an attempt on behalf of the publisher to promote Apostolos Doxiadis's new book, Uncle Petros and Goldbach's Conjecture. And, while the prize offered may not have led directly to a proof, the novel did at least inspire Silvio Pardi, a computer-science technologist at the Italian National Institute for Nuclear Physics (INFN). Pardi's day job involves working for the SuperB experiment at a Tier 2 center of the Worldwide LHC Computing Grid (WLCG), supporting CERN's ATLAS experiment. However, after reading the book he decided to get in touch with a pair of mathematicians who were working on finding a proof for the Goldbach conjecture to offer his help. Tomás Oliveira e Silva and Siegfried Herzog had been working together on the problem since 2001, using an algorithm to verify that the Golbach conjecture held for ever larger numbers. This method of numerical verification is by no means a proof, but it certainly does go a long way towards helping mathematicians trying to find one. After some tests, which demonstrated the processing power of the grid infrastructure at Pardi's disposal, the pair acquiesced to his request to join the collaboration. Thus, by allowing Pardi to run their algorithm using the grid computing infrastructure at his INFN site - along with resources at the SCoPE data center - the research was able to progress at a much faster rate and the team set a new world record for the highest number for which the Goldbach conjecture has been verified: one quintillion! That's 4 X 10¹⁸ in other words. Or, to write it out in full: 4,000,000,000,000,000,000. That's a full four more zeros than the previous record holders had achieved prior to 2001.

According to Oliveira e Silva, the principal investigator behind the project, achieving a higher verification limit is a highly important step in the quest to find a mathematical proof. He cites a recent paper published by Fields medalist Terence Tao as a great example of how strict mathematical proofs can be underpinned by such numerical verification. In this paper, Tao provides proof for the statement that every odd number larger than 1 is the sum of at most five primes. Oliveira e Silva explains that achieving ever-higher numerical verification limits could lead to the statement 'at most five primes' gradually being whittled down to 'at most four', and then 'at most three primes' over time. This could lead to a proof for what is known as the 'weak' Goldbach conjecture (see box), which in turn would mean that the Goldbach conjecture must also be true in its 'strong' form.

Thanks to the adoption of the grid infrastructure in September 2011, the speed at which Oliveira e Silva's team were able to run their algorithm increased six fold. "We reached this record at least two or three years earlier than would have otherwise been possible," says Pardi. "In just the final seven months that the grid was used, 19% of the total calculations were carried out."

Pardi also explains that the project was a great opportunity for him to test the reliability of the grid at the INFN site. He created a set of scripts to analyze the incoming results from each run of the algorithm and search for submission or execution errors. Where faults were found, jobs, which each required around six hours of intensive computation on a single core, were simply rescheduled on the grid. At the same time, analysis of these scripts was used to maintain a blacklist of all the computing elements in which computations were failing, thus allowing Pardi to improve the reliability of the computing center through the use of a real-time fault avoidance strategy.

Consequently, in helping bring researchers closer to solving a 270-year-old math problem, a computer science technician - inspired by a novel he had once read - was able to help ensure the reliability of grid computing systems used to identify the Higgs boson, a particle which until very recently was considered almost as elusive as the proof to Goldbach's conjecture.

Who knows, thanks to a little help from the grid, perhaps this too will not remain elusive for much longer?