Two computer scientists at at the University of Liverpool think they have successfully cracked the Erdős discrepancy problem (for a particular discrepancy bound C=2), an 80 year old maths puzzle proposed by the Hungarian mathematician Paul Erdős, who offered $500 for its solution.
They just can't be sure, because it is too big for a human to replicate.The resulting proof generated is an enormous 13 gigabytes, 30 percent larger than downloading all of the content on Wikipedia.
Erdős was fascinated by the extent to which an infinite sequence of numbers containing nothing but +1s and -1s contains 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.
Dr. Boris Konev and Dr. Alexei Lisitsa took a sequence 1,161 numbers long and managed to demonstrate that an infinite sequence will always have a discrepancy larger than two. The resulting proof and its 13 gigabytes is probably the longest proof ever and dwarfs another famously huge proof, the Classification Theorem of Finite Groups, which totaled 15,000 pages.
But, although checking this is beyond the reach of humans, they suggest future developments could change that landscape.
Lisitsa, from the University’s School of Electrical Engineering, Electronics and Computer Science, said, “On the one hand, it is true that our computer-generated solution is beyond the reach of humans to fully understand. On the other, all we can say for now is that at the moment there is no known ‘better’ human-comprehensible solution – but it does not mean that such a solution could not (or will not) be found in the future.”
Spot a pattern
Konev added, “Erdős’ hypothesis was that a discrepancy of any value can always be found, a far cry from the discrepancies of 1 and 2 that have now been proven. Our software has been running for weeks in an attempt to find a result for discrepancy 3. But even if subsequent programs show that higher and higher discrepancies exist for any infinite sequence, a computer cannot check the infinity of all numbers.”
Instead, it is likely that computer-assisted proofs for specific discrepancies will eventually enable a human to spot a pattern and come up with a proof for all numbers, Lisitsa concluded.
Source: University of Liverpool.
- PHYSICAL SCIENCES
- EARTH SCIENCES
- LIFE SCIENCES
- SOCIAL SCIENCES
Subscribe to the newsletter
Stay in touch with the scientific world!
Know Science And Want To Write?
- Could A Star Orbit A Planet? - Just For Fun
- Supertranslations And Eternal Ghosts: Black Holes No Closer To Being Understood
- Bel's Temple in Palmyra Is No More
- If Happy Meal Law Passes, NYC Kids Will Frown
- Blade Runner: The Science In The Fiction
- Highlights From ICNFP 2015
- Innate GMO Potato Deregulated By USDA
- "Could the Run 251244 Event 204117665 pp -> ZZ -> 2e2mu = 4L event be due to a Higgs mass state..."
- "There doesn't appear to be a particularly notable degree of collegiality here. Science isn't a..."
- "It is hard to admit it, but the suffering and death of civilians in Syria and elsewhere usually..."
- "We are living 21 century, everybody are thinking invention new technology. In this situation this..."
- "I wrote an article about this just today - why I think AI should not have emotions - and only very..."
- Not All Expensive Drugs Are Equal
- Conundrum Confronts DCIS Breast Cancer Patients
- Germany Rightly Skewered for GMO Nonsense; Kudos for WSJ
- Expect Only Frowns if Silly Happy Meal Law Passes
- “Shock Therapy” – Not a Cuckoo’s Nest, a Valid Depression Rx
- Innate: Simplot genetically engineered potato gets USDA nod for deregulation
- Relativistic Heavy Ion Collider confirms tiny drops of early universe 'perfect' fluid
- Magnetic fields provide a new way to communicate wirelessly
- With tobacco, what you don't know can kill you sooner
- Isthminia panamensis: New species of ancient river dolphin discovered
- Smoking prevalence stays the same but people who want to quit are up