Month: August 2004

Richard Schwartz, a mathematician at Brown University has found a solution to the problem of how small a Möbius band can be made without intersecting itself—at least for a smooth piece of paper. The paper is published on the arXiv preprint server.

A Möbius strip (or band) is both a physical and mathematical object. A sample can be constructed by twisting a simple strip of paper one time and then taping the ends together. Since they were first discovered back in the mid-1800s, mathematicians have been scratching their heads trying to determine one simple constraint—what is the shortest strip necessary for making one? Back in the late 1970s, a pair of mathematicians, Charles Sidney Weaver and Benjamin Rigler Halpern, found that the problem could be made simpler by allowing self-intersections—that changed the problem to one that involved seeking the minimum amount of strip needed to avoid self-intersections.

Four years ago, Schwartz found himself intrigued by the problem and, as he describes in his paper, became “hooked” on finding a solution. Two years ago, he thought he had finally found it and published a proof showing his work—it involved breaking down the problem into multiple pieces and then using geometry principles to solve the puzzle as a whole.

Unfortunately, there turned out to be a major flaw in his work that he did not discover until much more recently. He found it by creating physical samples and cutting them in different ways to see how they worked on a deeper level. He discovered that the 2D strip was not shaped like a parallelogram as had been thought—instead, it was a trapezoid.

Inspired by his discovery, he went back to this original proof and corrected the error, and in doing so, found that the proof worked much better than it had originally. It was also much simpler. He also used the proof to work out the optimization problem, and got what he was hoping for: √3. He notes that while pleased with his own work, he has already turned his attention to another problem—to determine how short a band can be if it is twisted three times instead of once.\

For more such insights, log into our website https://international-maths-challenge.com

Credit of the article given to Bob Yirka, Phys.org

Third time’s a charm: just weeks after cracking an elusive problem involving the number 42, mathematicians have found a solution to an even harder problem for the number 3.

Andrew Booker at Bristol University, UK, and Andrew Sutherland at the Massachusetts Institute of Technology have found a big solution to a maths problem known as the sum of three cubes.

The problem asks whether any integer, or whole number, can be represented as the sum of three cubed numbers.

There were already two known solutions for the number 3, both of which involve small numbers: 1³ + 1³ + 1³ and 4³ + 4³ + (-5)³.

But mathematicians have been searching for a third for decades. The solution that Booker and Sutherland found is:

569936821221962380720³ + (-569936821113563493509) ³ + (-472715493453327032) ³ = 3

Earlier this month, the pair also found a solution to the same problem for 42, which was the last remaining unsolved number less than 100.

To find these solutions, Booker and Sutherland worked with software firm Charity Engine to run an algorithm across the idle computers of half a million volunteers.

For the number 3, the amount of processing time was equivalent to a single computer processor running continuously for 4 million hours, or more than 456 years.

When a number can be expressed as the sum of three cubes, there are infinitely many possible solutions, says Booker. “So there should be infinitely many solutions for three, and we’ve just found the third one,” he says.

There’s a reason the third solution for 3 was so hard to find. “If you look at just the solutions for any one number, they look random,” he says. “We think that if you could get your hands on loads and loads of solutions – of course, that’s not possible, just because the numbers get so huge so quickly – but if you could, there’s kind of a general trend to them: that the digit sizes are growing roughly linearly with the number of solutions you find.”

It turns out that this rate of growth is extremely small for the number 3 – only 114, now the smallest unsolved number, has a smaller rate of growth. In other words, numbers with a slow rate of growth have fewer solutions with a lower number of digits.

The duo also found a solution to the problem for 906. We know for sure that certain numbers, such as 4, 5 and 13, can’t be expressed as the sum of three cubes. There now remain nine unsolved numbers under 1000. Mathematicians think these can be written as the sum of three cubes, but we don’t yet know how.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Donna Lu*

Alan Turing: still casting a long shadow over mathematics

One hundred and fifty years of mathematics will be proved wrong if a new computer program stops running. Thankfully, it’s unlikely to happen, but the code behind it is testing the limits of the mathematical realm.

The program is a simulated Turing machine, a mathematical model of computation created by codebreaker Alan Turing. In 1936, he showed that the actions of any computer algorithm can be mimicked by a simple machine that reads and writes 0s and 1s on an infinitely long tape by working through a set of states, or instructions. The more complex the algorithm, the more states the machine requires.

Now Scott Aaronson and Adam Yedidia of the Massachusetts Institute of Technology have created three Turing machines with behaviour that is entwined in deep questions of mathematics. This includes the proof of the 150-year-old Riemann hypothesis – thought to govern the patterns of prime numbers.

Turing’s machines have long been used to probe such questions. Their origins lie in a series of philosophical revelations that rocked the mathematical world in the 1930s. First, Kurt Gödel proved that some mathematical statements can never be proved true or false – they are undecidable. He essentially created a mathematical version of the sentence “This sentence is false”: a logical brain-twister that contradicts itself.

No proof of everything

Gödel’s assertion has a get-out clause. If you change the base assumptions on which proofs are built – the axioms – you can render a problem decidable. But that will still leave other problems that are undecidable. That means there are no axioms that let you prove everything.

Following Gödel’s arguments, Turing proved that there must be some Turing machines whose behaviour cannot be predicted under the standard axioms – known as Zermelo-Fraenkel set theory with the axiom of choice (C), or more snappily, ZFC – underpinning most of mathematics. But we didn’t know how complex they would have to be.

Now, Yedidia and Aaronson have created a Turing machine with 7918 states that has this property. And they’ve named it “Z”.

“We tried to make it concrete, and say how many states does it take before you get into this abyss of unprovability?” says Aaronson.

The pair simulated Z on a computer, but it is small enough that it could theoretically be built as a physical device, says Terence Tao of the University of California, Los Angeles. “If one were then to turn such a physical machine on, what we believe would happen would be that it would run indefinitely,” he says, assuming you ignore physical wear and tear or energy requirements.

No end in sight

Z is designed to loop through its 7918 instructions forever, but if it did eventually stop, it would prove ZFC inconsistent. Mathematicians wouldn’t be too panicked, though – they could simply shift to a slightly stronger set of axioms. Such axioms already exist, and could be used to prove the behaviour of Z, but there is little to be gained in doing so because there will always be a Turing machine to exceed any axiom.

“One can think of any given axiom system as being like a computer with a certain limited amount of memory or processing power,” says Tao. “One could switch to a computer with even more storage, but no matter how large an amount of storage space the computer has, there will still exist some tasks that are beyond its ability.”

But Aaronson and Yedidia have created two other machines that might give mathematicians more pause. These will stop only if two famous mathematical problems, long believed to be true, are actually false. These are Goldbach’s conjecture, which states that every even whole number greater than 2 is the sum of two prime numbers, and the Riemann hypothesis, which says that all prime numbers follow a certain pattern. The latter forms the basis for parts of modern number theory, and disproving it would be a major, if unlikely, upset.

Practical benefits

Practically, the pair have no intention of running their Turing machines indefinitely in an attempt to prove these problems wrong. It’s not a particularly efficient way to attack that problem, says Lance Fortnow of the Georgia Institute of Technology in Atlanta.

Expressing mathematical problems as Turing machines has a different practical benefit: it helps to work out how complex they are. The Goldbach machine has 4888 states, the Riemann one has 5372, while Z has 7918, suggesting the ZFC problem is the most complex of the three. “That would match most people’s intuitions about these sorts of things,” Aaronson says.

Yedidia has placed his code online, and mathematicians may now compete to reduce the size of these Turing machines, pushing them to the limit. Already a commenter on Aaronson’s SaiBlog claims to have created a 31-state Goldbach machine, although the pair have yet to verify this.

Fortnow says the actual size of the Turing machines are irrelevant. “The paper tells us that we can have very compressed descriptions that already go beyond the power of ZFC, but even if they were more compressed, it wouldn’t give us much pause about the foundations of math,” he says.

But Aaronson says shrinking Z further could say something interesting about the limits of the foundations of maths – something Gödel and Turing are likely to have wanted to know. “They might have said ‘that’s nice, but can you get 800 states? What about 80 states?’” Aaronson says. “I would like to know if there is a 10-state machine whose behaviour is independent of ZFC.”

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Jacob Aron*