Feeds

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

Try fitting THAT in the margins, math wonks

High performance access to file storage

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. ®

High performance access to file storage

More from The Register

next story
Fancy joining Reg hack on quid-a-day challenge?
Recruiting now for charity starvation diet
Red-faced LOHAN team 'fesses up in blown SPEARS fuse fiasco
Standing in the corner, big pointy 'D' hats
KILLER SPONGES menacing California coastline
Surfers are safe, crustaceans less so
LOHAN's Punch and Judy show relaunches Thursday
Weather looking good for second pop at test flights
Discovery time for 200m WONDER MATERIALS shaved from 4 MILLENNIA... to 4 years
Alloy, Alloy: Boffins in speed-classification breakthrough
Elon Musk's LEAKY THRUSTER gas stalls Space Station supply run
Helium seeps from Falcon 9 first stage, delays new legs for NASA robonaut
Top Secret US payload launched into space successfully
Clandestine NRO spacecraft sets off on its unknown mission
New FEMTO-MOON sighted BIRTHING from Saturn's RING
Icy 'Peggy' looks to be leaving the outer rings
prev story

Whitepapers

Top three mobile application threats
Learn about three of the top mobile application security threats facing businesses today and recommendations on how to mitigate the risk.
Combat fraud and increase customer satisfaction
Based on their experience using HP ArcSight Enterprise Security Manager for IT security operations, Finansbank moved to HP ArcSight ESM for fraud management.
The benefits of software based PBX
Why you should break free from your proprietary PBX and how to leverage your existing server hardware.
Five 3D headsets to be won!
We were so impressed by the Durovis Dive headset we’ve asked the company to give some away to Reg readers.
SANS - Survey on application security programs
In this whitepaper learn about the state of application security programs and practices of 488 surveyed respondents, and discover how mature and effective these programs are.