Mathematicians spark debate with 13 GB proof for Erdős problem

Try fitting THAT in the margins, math wonks

Next gen security for virtualised datacentres

When Pierre de Fermat famously complained that he didn't have space to write the proof of his famous “Fermat's Last Theorem”, he only ran out of space of the margin of a book. Now, a pair of mathematicians at the University of Liverpool in the UK have produced a 13GB proof that's sparked a debate about how to test it.

The mathematicians, Alexei Lisitsa and Boris Konev, were looking at what's called the “Erdős discrepancy problem” (it's appropriate to point to Wikipedia, for reasons you'll catch in a minute).

New Scientist describes the problem like this:

“Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s. Erdős was fascinated by the extent to which such sequences contain internal patterns. One way to measure that is to cut the infinite sequence off at a certain point, and then create finite sub-sequences within that part of the sequence, such as considering only every third number or every fourth. Adding up the numbers in a sub-sequence gives a figure called the discrepancy, which acts as a measure of the structure of the sub-sequence and in turn the infinite sequence, as compared with a uniform ideal.”

For any sequence, Paul Erdős believed, you could find a finite sub-sequence that summed to a number bigger than any than you could choose – but he couldn't prove it.

In this Arxiv paper, the University of Liverpool mathematicians set a computer onto the problem in what they call “a SAT attack” using a Boolean Satisfiability (SAT) solver. They believe they've produced a proof of the Erdős discrepancy problem, but there's a problem.

After six hours, the machine they used – an Intel i5-2500 running at 3.3 GHz with 16 GB of RAM – produced what they offer as a proof, but it's inconveniently large, at 13 GB. A complete Wikipedia (see, I told you it was relevant) download is only 10 GB.

As New Scientist points out, that raises a different problem: how can humans ever check the proof. However, at least one mathematician NS spoke to said “no problem”: after all, other computers can always be deployed to test the proof. ®

Secure remote control for conventional and virtual desktops

More from The Register

next story
Our LOHAN spaceplane ballocket Kickstarter climbs through £8000
Through 25 per cent but more is needed: Get your UNIQUE rewards!
LOHAN tunes into ultra long range radio
And verily, Vultures shall speak status unto distant receivers
EOS, Lockheed to track space junk from Oz
WA facility gets laser-eyes out of the fog
Volcanic eruption in Iceland triggers CODE RED aviation warning
Lava-spitting Bárðarbunga prompts action from Met Office
NASA to reformat Opportunity rover's memory from 125 million miles away
Interplanetary admins will back up data and get to work
That's right, OVER 9,000 beer tokens - and counting
Major cyber attack hits Norwegian oil industry
Statoil, the gas giant behind the Scandie social miracle, targeted
prev story


Endpoint data privacy in the cloud is easier than you think
Innovations in encryption and storage resolve issues of data privacy and key requirements for companies to look for in a solution.
Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
Advanced data protection for your virtualized environments
Find a natural fit for optimizing protection for the often resource-constrained data protection process found in virtual environments.
Boost IT visibility and business value
How building a great service catalog relieves pressure points and demonstrates the value of IT service management.
Next gen security for virtualised datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.