Author: IMC

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*

Cracking this mathematical mystery will make someone rich, but its value to all of us could be incalculable. Jacob Aron explains why it matters if P = NP.

Dear Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.” So began an email sent in August 2010 to a group of leading computer scientists by Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California.

It was an incendiary claim. Deolalikar was saying he had cracked the biggest problem in computer science, a question concerning the complexity and fundamental limits of computation. Answer the question “Is P equal to NP?” with a yes, and you could be looking at a world transformed, where planes and trains run on time, accurate electronic translations are routine, the molecular mysteries of life are revealed at the click of a mouse – and secure online shopping becomes fundamentally impossible. Answer it with a no, as Deolalikar claimed to have done, and it would suggest that some problems are too irreducibly complex for computers to solve exactly.

One way or another, then, we would like an answer. But it has been frustratingly slow in coming. “It’s turned out to be an incredibly hard problem,” says Stephen Cook of the University of Toronto, Canada, the computer scientist who first formulated it in May 1971. “I never thought it was going to be easy, but now 40 years later it looks as difficult as ever.”

The importance of P = NP? was emphasised in 2000, when the privately funded Clay Mathematics Institute in Cambridge, Massachusetts, named it as one of seven “Millennium Prize” problems, with a $1 million bounty for whoever solves it. Since then Cook and other researchers in the area have regularly received emails with purported solutions. Gerhard Woeginger of the Eindhoven University of Technology in the Netherlands even maintains an online list of them. “We’ve seen hundreds of attempts, and we can more or less classify them according to the mistakes the proof makes,” he says.

Deolalikar’s attempt seemed different. For a start, it came from an established researcher rather than one of the legion of amateurs hoping for a pop at glory and a million dollars. Also, Cook initially gave it a cautious thumbs up, writing that it seemed to be a “relatively serious claim”. That led it to spread across the web and garnered it widespread attention in the press, New Scientist included (14 August 2010, p 7).

In the end, though, it was a false dawn. “It probably didn’t deserve all the publicity,” says Neil Immerman, a computer scientist at the University of Massachusetts, Amherst. He was one of an army of researchers who, working in an informal online collaboration, soon exposed fundamental flaws in the proof. Deolalikar has responded to some of them and submitted an expanded version to an academic journal. Till he hears back, he refuses to comment further.

The consensus now is that his proof – like all attempts before it – is unfixable. And so the mystique of P = NP? remains unbroken 40 years on. But what is the problem about? Why is it so important, and what happens if it is answered one way or the other?

“The consensus now is that last year’s proof is false – which just adds to the mystique of the problem”

What is P?

Computing power, we are accustomed to think, is the gift that keeps on giving. Every year or two that goes by sees roughly a doubling in our number-crunching capabilities – a march so relentless that it has acquired the label “Moore’s law”, after the Intel researcher, Gordon Moore, who first noted the trend back in the 1960s.

Talk of the ultimate limits of computation tends to be about how many transistors, the building blocks of microprocessors, we can cram onto a conventional silicon chip – or whatever technology or material might replace it. P = NP? raises the spectre that there is a more fundamental limitation, one that lies not in hardware but in the mechanics of computation itself.

P = NP should not be mistaken for a simple algebraic equation – if it were, we could just have N = 1 and claim the Clay institute’s million bucks. P and NP are examples of “complexity classes”, categories into which problems can be slotted depending on how hard it is to unravel them using a computer.

Solving any problem computationally depends on finding an algorithm, the step-by-step set of mathematical instructions that leads us to the answer. But how much number-crunching does an algorithm need? That depends on the problem.

The P class of problems is essentially the easy ones: an algorithm exists to solve them in a “reasonable” amount of time. Imagine looking to see if a particular number appears in a list. The simplest solution is a “linear search” algorithm: you check each number in turn until you find the right one. If the list has n numbers – the “size” of the problem – this algorithm takes at most n steps to search it, so its complexity is proportional to n. That counts as reasonable. So too do things that take a little more computational muscle – for instance, the manual multiplication of two n-digit numbers, which takes about n² steps. A pocket calculator will still master that with ease, at least for relatively small values of n. Any problem of size n whose solution requires n to the power of something (n^x) steps is relatively quick to crack. It is said to be solvable in “polynomial time”, and is denoted P.

What is NP?

Not all problems are as benign. In some cases, as the size of the problem grows, computing time increases not polynomially, as n^x, but exponentially, as xⁿ – a much steeper increase. Imagine, for example, an algorithm to list out all possible ways to arrange the numbers from 1 to n. It is not difficult to envisage what the solutions are, but even so the time required to list them rapidly runs away from us as n increases. Even proving a problem belongs to this non-polynomial class can be difficult, because you have to show that absolutely no polynomial-time algorithm exists to solve it.

That does not mean we have to give up on hard problems. With some problems that are difficult to solve in a reasonable time, inspired guesswork might still lead you to an answer whose correctness is easy to verify. Think of a sudoku puzzle. Working out a solution can be fiendishly difficult, even for a computer, but presented with a completed puzzle, it is easy to check that it fulfils the criteria for being a valid answer (see diagram). Problems whose solutions are hard to come by but can be verified in polynomial time make up the complexity class called NP, which stands for non-deterministic polynomial time.

Constructing a valid sudoku grid – in essence asking the question “Can this number fill this space?” over and over again for each space and each number from 1 to 9, until all spaces are compatibly filled – is an example of a classic NP problem, the Boolean satisfiability problem. Processes such as using formal logic to check software for errors and deciphering the action of gene regulatory networks boil down to similar basic satisfiability problems.

And here is the nub of the P = NP? problem. All problems in the set P are also in the set NP: if you can easily find a solution, you can easily verify it. But is the reverse true? If you can easily verify the solution to a problem, can you also easily solve it – is every problem in the set NP also in P? If the answer to that question is yes, the two sets are identical: P is equal to NP, and the world of computation is irrevocably changed – sudoku becomes a breeze for a machine to solve, for starters. But before we consider that possibility, what happens if P is found to be not equal to NP?

What if P ≠ NP?

In 2002, William Gasarch, a computer scientist at the University of Maryland in College Park, asked 100 of his peers what they thought the answer to the P = NP? question would be. “You hear people say offhand what they think of P versus NP. I wanted to get it down on record,” he says. P ≠ NP was the overwhelming winner, with 61 votes. Only nine people supported P = NP, some, they said, just to be contrary. The rest either had no opinion or deemed the problem impossible to solve.

If the majority turns out to be correct, and P is not equal to NP – as Deolalikar suggested – it indicates that some problems are by their nature so involved that we will never be able to crunch through them. If so, the proof is unlikely to make a noticeable difference to you or me. In the absence of a definitive answer to P = NP?, most computer scientists already assume that some hard problems cannot be solved exactly. They concentrate on designing algorithms to find approximate solutions that will suffice for most practical purposes. “We’ll be doing exactly the same as we’re currently doing,” says Woeginger.

Proving P ≠ NP would still have practical consequences. For a start, says Immerman, it would shed light on the performance of the latest computing hardware, which splits computations across multiple processors operating in parallel. With twice as many processors, things should run twice as fast – but for certain types of problem they do not. That implies some kind of limitation to computation, the origin of which is unclear. “Some things seem like they’re inherently sequential,” says Immerman. “Once we know that P and NP are not equal, we’ll know why.”

It could also have an impact on the world of cryptography. Most modern encryption relies on the assumption that breaking a number down to its prime-number factors is hard. This certainly looks like a classic NP problem: finding the prime factors of 304,679 is hard, but it’s easy enough to verify that they are 547 and 557 by multiplying them together. Real encryption uses numbers with hundreds of digits, but a polynomial-time algorithm for solving NP problems would crack even the toughest codes.

So would P ≠ NP mean cryptography is secure? Not quite. In 1995, Russell Impagliazzo of the University of California, San Diego, sketched out five possible outcomes of the P = NP? debate. Four of them were shades-of-grey variations on a world where P ≠ NP. For example, we might find some problems where even though the increase in complexity as the problem grew is technically exponential, there are still relatively efficient ways of finding solutions. If the prime-number-factoring problem belongs to this group, cryptography’s security could be vulnerable, depending where reality lies on Impagliazzo’s scale. “Proving P is not equal to NP isn’t the end of our field, it’s the beginning,” says Impagliazzo.

Ultimately, though, it is the fifth of Impagliazzo’s worlds that excites researchers the most, however unlikely they deem it. It is “Algorithmica” – the computing nirvana where P is indeed equal to NP.

What if P = NP?

If P = NP, the revolution is upon us. “It would be a crazy world,” says Immerman. “It would totally change our lives,” says Woeginger.

That is because of the existence, proved by Cook in his seminal 1971 paper, of a subset of NP problems known as NP-complete. They are the executive key to the NP washroom: find an algorithm to solve an NP-complete problem, and it can be used to solve any NP problem in polynomial time.

Lots of real-world problems are known to be NP-complete. Satisfiability problems are one example; versions of the knapsack problem (below), which deals with optimal resource allocation, and the notorious travelling salesman problem (above) are others. This problem aims to find the shortest-distance route for visiting a series of points and returning to the starting point, an issue of critical interest in logistics and elsewhere.

If we could find a polynomial-time algorithm for any NP-complete problem, it would prove that P=NP, since all NP problems would then be easily solvable. The existence of such a universal computable solution would allow the perfect scheduling of transport, the most efficient distribution of goods, and manufacturing with minimal waste – a leap and a bound beyond the “seems-to-work” solutions we now employ.

It could also lead to algorithms that perform near-perfect speech recognition and language translation, and that let computers process visual information as well as any human can. “Basically, you would be able to compute anything you wanted,” says Lance Fortnow, a computer scientist at Northwestern University in Evanston, Illinois. A further curious side effect would be that of rendering mathematicians redundant. “Mathematics would be largely mechanisable,” says Cook. Because finding a mathematical proof is difficult, but verifying one is relatively easy, in some way maths itself is an NP problem. If P=NP, we could leave computers to churn out new proofs.

“Proving P = NP would have the curious side effect of rendering mathematicians redundant”

What if there’s no algorithm?

There is an odd wrinkle in visions of a P = NP world: that we might prove the statement to be true, but never be able to take advantage of that proof. Mathematicians sometimes find “non-constructive proofs” in which they show that a mathematical object exists without actually finding it. So what if they could show that an unknown P algorithm exists to solve a problem thought to be NP? “That would technically settle the problem, but not really,” says Cook.

There would be a similar agonising limbo if a proof that P=NP is achieved with a universal algorithm that scales in complexity as n to the power of a very large number. Being polynomial, this would qualify for the Clay institute’s $1 million prize, but in terms of computability it would not amount to a hill of beans.

Will we have an answer soon?

When can we expect the suspense to be over, one way or another? Probably not so soon. “Scientometrist” Samuel Arbesman of the Harvard Medical School in Boston, Massachusetts, predicts that a solution of “P = NP?” is not likely to arrive before 2024 (New Scientist, 25 December 2010, p 24). In Gasarch’s 2002 poll of his peers, only 45 per cent believed it would be resolved by 2050. “I think people are now more pessimistic,” he says, “because after 10 years there hasn’t been that much progress.” He adds that he believes a proof could be up to 500 years away.

Others find that excessively gloomy, but all agree there is a mammoth task ahead. “The current methods we have don’t seem to be giving us progress,” says Fortnow. “All the simple ideas don’t work, and we don’t know where to look for new tools,” says Woeginger. Part of the problem is that the risk of failure is too great. “If you have already built up a reputation, you don’t want to publish something that makes other people laugh,” says Woeginger.

Some are undeterred. One is Ketan Mulmuley at the University of Chicago. He declined to comment on his work, which is currently under review for publication, but fellow researchers say his ideas look promising. In essence it involves translating the P = NP? problem into more tractable problems in algebraic geometry, the branch of mathematics that relates shapes and equations. But it seems even Mulmuley is not necessarily anticipating a quick success. “He expects it to take well over 100 years,” says Fortnow.

Ultimately, though, Mulmuley’s tactic of connecting P = NP? to another, not obviously related, mathematical area seems the most promising line of attack. It has been used before: in 1995, the mathematician Andrew Wiles used work linking algebraic geometry and number theory to solve another high-profile problem, Fermat’s last theorem. “There were a lot of building blocks,” says Fortnow. “Then it took one brilliant mind to make that last big leap.”

Woeginger agrees: “It will be solved by a mathematician who applies methods from a totally unrelated area, that uses something nobody thinks is connected to the P versus NP question.” Perhaps the person who will settle P = NP? is already working away in their own specialised field, just waiting for the moment that connects the dots and solves the world’s hardest problem.

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

*Credit for article given to Jacob Aron*

AI can search through numbers and equations to find patterns

Artificial intelligence’s ability to sift through large amounts of data is helping us tackle one of the most difficult unsolved problems in mathematics.

Yang-Hui He at City, University of London, and his colleagues are using the help of machine learning to better understand the Birch and Swinnerton-Dyer conjecture. This is one of the seven fiendishly difficult Millennium Prize Problems, each of which has a $1 million reward on offer for the first correct solution.

The conjecture describes solutions to equations known as elliptic curves, equations in the form of y² = x³ + ax + b, where x and y are variables and a and b are fixed constants.

Elliptic curves were essential in cracking the long-standing Fermat’s last theorem, which was solved by mathematician Andrew Wiles in the 1990s, and are also used in cryptography.

To study the behaviour of elliptic curves, mathematicians also use an equation called the L-series. The conjecture, first stated by mathematicians Bryan Birch and Peter Swinnerton-Dyer in the 1960s, says that if an elliptic curve has an infinite number of solutions, its L-series should equal 0 at certain points.

“It turns out to be a very, very difficult problem to find a set of integer solutions on such equations,” says He, meaning solutions only involving whole numbers. “This is part of the biggest problem in number theory: how do you find integer solutions to polynomials?”

Finding integer solutions or showing that they cannot exist has been crucial. “For example, Fermat’s last theorem is reduced completely to the statement of whether you can find certain properties of elliptic curves,” says He.

He and his colleagues used an AI to analyse close to 2.5 million elliptic curves that had been compiled in a database by John Cremona at the University of Warwick, UK. The rationale was to search the equations to see if any statistical patterns emerged.

Plugging different values into the elliptic curve equation and plotting the results on a graph, the team found that the distribution takes the shape of a cross, which mathematicians hadn’t previously observed. “The distribution of elliptic curves seems to be symmetric from left to right, and up and down,” says He.

“If you spot any interesting patterns, then you can raise a conjecture which may later lead to an important result,” says He.  “We now have a new, really powerful thing, which is machine learning and AI, to do this.”

To see whether a theoretical explanation exists for the cross-shaped distribution, He consulted number theorists. “Apparently, nobody knows,” says He.

“Machine learning hasn’t yet been applied very much to problems in pure maths,” says Andrew Booker at the University of Bristol, UK. “Elliptic curves are a natural place to start.”

“Birch and Swinnerton-Dyer made their conjecture based on patterns that they observed in numerical data in the 1960s, and I could imagine applications of machine learning that tried to detect those patterns efficiently,” says Booker, but the approach so far is too simple to turn up any deep patterns, he says.

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

*Credit for article given to Donna Lu*

I work on the mathematics of sharing resources, which has led me to consider emotions such as envy, behaviour such as risk-taking and the best way to cut a cake.

Like, I suspect, many women, my wife enjoys eating dessert but not ordering it. I therefore dutifully order what I think she’ll like, cut it in half and invite her to choose a piece.

This is a sure-fire recipe for marital accord. Indeed, many mathematicians, economists, political scientists and others have studied this protocol and would agree. The protocol is known as the “cut-and-choose” procedure. I cut. You choose.

Cut-and-choose

Cut-and-choose is not limited to the dining table – it dates back to antiquity. It appears nearly 3,000 years ago in Hesiod’s poem Theogeny where Prometheus divides a cow and Zeus selects the part he prefers.

In more recent times, cut-and-choose has been enshrined in the UN’s 1982 Convention of the Law of the Sea where it was proposed as a mechanism to resolve disputes when dividing the seabed for mining.

To study the division of cake, cows and the seabed in a more formal way, various mathematical models have been developed. As with all models, these need to make a number of simplifying assumptions.

One typical assumption is that the people employing the cut-and-choose method are risk-averse. They won’t adopt a risky strategy that may give them less cake than a more conservative strategy.

With such assumptions in place, we can then prove what properties cake cutting procedures have and don’t have. For instance, cut-and-choose is envy free.

You won’t envy the cake I have, otherwise you would have taken this piece. And I won’t envy the piece you have, as the only risk-averse strategy is for me to cut the cake into two parts that I value equally.

On the other hand, the cutting of the cake is not totally equitable since the player who chooses can get cake that has more than half the total value for them.

With two players, it’s hard to do better than cut-and-choose. But I should record that my wife argues with me about this.

She believes it favours the second player since the first player inevitably can’t divide the cake perfectly and the second player can capitalise on this. This is the sort of assumption ignored in our mathematical models.

My wife might prefer the moving-knife procedure which doesn’t favour either player. A knife is moved over the cake, and either player calls “cut” when they are happy with the slice.

Again, this will divide the cake in such a way that neither player will envy the other (else they would have called “cut” themselves).

Three’s a crowd

Unfortunately, moving beyond two players increases the complexity of cutting cake significantly.

With two players, we needed just one cut to get to an envy free state. With three players, a complex series of five cuts of the cake might be needed. Of course, only two cuts are needed to get three slices.

The other three cuts are needed to remove any envy. And with four players, the problem explodes in our face.

An infinite number of cuts may be required to get to a situation where no one envies another’s cake. I’m sure there’s some moral here about too many cake cutters spoiling the dessert.

There are many interesting extensions of the problem. One such extension is to indivisible goods.

Suppose you have a bag of toys to divide between two children. How do you divide them fairly? As a twin myself, I know that the best solution is to ensure you buy two of everything.

It’s much more difficult when your great aunt gives you one Zhu Zhu pet, one Bratz doll and three Silly Bandz bracelets to share.

Online

More recently, I have been studying a version of the problem applicable to online settings. In such problems, not all players may be available all of the time. Consider, for instance, allocating time on a large telescope.

Astronomers will have different preferences for when to use the telescope depending on what objects are visible, the position of the sun, etcetera. How do we design a web-based reservation system so that astronomers can choose observation times that is fair to all?

We don’t want to insist all astronomers log in at the same time to decide an allocation. And we might have to start allocating time on the telescope now, before everyone has expressed their preferences. We can view this as a cake-cutting problem where the cake is made up of the time slots for observations.

The online nature of such cake-cutting problems poses some interesting new challenges.

How can we ensure that late-arriving players don’t envy cake already given to earlier players? The bad news is that we cannot now achieve even a simple property like envy freeness.

No procedure can guarantee situations where players don’t envy one another. But more relaxed properties are possible, such as not envying cake allocated whilst you are participating in the cutting of the cake.

Ham sandwich

There’s a brilliantly named piece of mathematics due to Arthur H. Stone and [John Tukey](http://www.morris.umn.edu/~sungurea/introstat/history/w98/Tukey.html, the Ham Sandwich Theorem which proves we can always cut a three-layered cake perfectly with a single cut.

Suppose we have three objects. Let’s call them “the top slice of bread”, “the ham filling” and “the bottom slice of bread”. Or if you prefer “the top layer” of the cake, “the middle layer” and “the bottom layer”.

The ham sandwich theorem proves a single slice can always perfectly bisect the three objects. Actually, the ham sandwich theorem works in any number of dimensions: any n objects in n-dimensional space can be simultaneously bisected by a single (n − 1) dimensional hyperplane.

So, in the case of the three-layered cake, n = 3, and the three-layered cake can be bisected (or cut) using a single, two-dimensional “hyperplane”. Such as, say, a knife.

Who would have thought that cutting cake would lead to higher dimensions of mathematics by way of a ham sandwich?

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

*Credit for article given to Toby Walsh*

The diagram above (known as the tetractys) shows the first four triangular numbers (1, 3, 6, 10, …). Although there is a simple formula for calculating these numbers directly, t(n) = 1/2(n(n+1)), constructing them by these layered-triangle diagrams helps to show their geometric and recursive properties.

More generally, polygonal numbers arise from counting arrangements of dots in regular polygonal patterns. Larger polygons are built from smaller ones of the same type by adding additional layers of dots, called gnomons. Beginning with a single dot, k-sided polygons are built by adding gnomons consisting of k-2 segments, with each segment of the gnomon having one more dot than the segments of the previous layer. In this way, the nth gnomon consists of segments each n dots long, but with k-3 dots shared by adjoining segments (the corners).

This post describes how you can draw figures that illustrate the polygonal numbers and explore the polygonal numbers in general (triangular, square, pentagonal, hexagonal, etc.) using either TinkerPlots or Fathom. Both TinkerPlots and Fathom work well, but TinkerPlots creates nicer pictures, and allows for captions directly on the graph.
Without describing the details of how you create Fathom or TinkerPlot documents, here are the attributes that you will want to define in order to draw diagrams like the ones shown.

Required attributes
Create a slider k. This will allow you to set what kind of polygonal number you want to draw (k=3 gives triangular numbers, k=4 gives square numbers, etc.)
Define the following attributes:

n The number itself. This is a natural number beginning at 1 and continuing through the number of cases.

gnomon This states which “layer” or gnomon the number belongs in. It is calculated based on a number of other attributes.

g_index This is the position of the number within the gnonom – it ranges from 1 up until the next k-polygonal number is hit.

s_index Each gonom is broken up into sections or sides – what is the position within the side? Each side is of length equal to the gonom number. The first gonom has sides of length 1, the second has length 2, etc.

corner This keeps track of whether or not the number is a “corner” or not. This is based primarily on the s_index attribute.

c_index This keeps track of how many corners we have so far. There are only k-1 corners in a gnomon (the first number n=1 is the remaining corner). So, when we hit the last corner, we know we are at a polygonal number.

k_poly Records whether or not the number n is k-polygonal. It does this by checking to see if it is the last corner of a gnonom.
The attributes listed above are required for finding the position of each number within the figure; th following attributes are used in actually drawing the figures.

angle The base corner angle for the polygon is determined by k. This is the external angle for each corner.

current_angle We have to add to the base angle at each corner as we turn at each corner. This attribute is used to keep track of the total current angle.

dx This is the x-component of the unit direction vector that we are travelling in. Each new dot moves one dx over in the x-direction. It is given by the cosine of the current angle.

dy This is the y-component of the unit direction vector that we are travelling in. Each new dot moves one dy over in the y-direction. It is given by the sine of the current angle.

prev_g_1_x This is the x-coordinate of the first dot in the previous gonom layer. We need to know this because it will be the starting point for the next layer – each layer starts back at the “beginning” of the figure.

prev_g_1_y This is the y- coordinate of the first dot in the previous gonom layer.

x This is the x-coordinate of the current dot, calculated either from the previous dot or from the first dot in the previous layer.

y This is the y-coordinate of the current dot, calculated either from the previous dot or from the first dot in the previous layer.

caption Used to display the number on the plot (TinkerPlots only)
Below are the formulas for each attribute, written in “ascii” math. They are presented without a full explanation, in the hopes that if you try to implement this you will think about and explore each using the formulas and the descriptions above as a guide. Alternate methods for drawing the diagrams are possible, and you might find other formulas that achieve the same goals. Note that there are nested if() statements in several formulas.

n = caseIndex

gnomon = if(n=1){1, if(prev(k_poly)){prev(gnomon)+1, prev(gnomon)

g_index = if(n=1){ 1, if(prev(k_poly){1, prev(g_index) +1

s_index = if(n=1){ 1, if(prev(k_poly){1, if(prev(s_index) = gnomon){2,prev(s_index)

corner = (s_index=1) or (s_index=gnomon)

c_index= if(g_index=1){1, if(corner){prev(c_index)+1, prev(c_index)

k_poly = if(n=1){true, (c_index=k-1)

prev_g_1_x = if (n=1){0, if(g_index=2){prev(x), prev(prev_g_1_x)

prev_g_1_y = if(n=1){0, if(g_index=2){prev(y), prev(prev_g_1_y)

angle = pi-((k-2)*(pi/k))

current_angle = if(g_index =1) {pi-angle, if(pref(corner)){prev(current_angle)-angle, prev(current_angle)

dx = cos(current_angle)

dy = sin(current_angle)

x= if(n=1){0, if(g_index=1){prev_g_1_x +dx, prev(x) +dx

y =if(n=1){0, if(g_index=1){prev_g_1_y +dy, prev(y) +dy

caption = if(k_poly){n,””

To actually draw the diagrams, create a new plot with the x and y attributes as the horizontal and vertical axis, respectively. Add cases to the collection to populate the diagram. Optionally you can show connecting lines, and (in TinkerPlots) add a legend using the caption attribute.

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

*Credit for article given to dan.mackinnon*

An analysis of a mathematical economic game suggests that even learning from past mistakes will almost never help us optimise our decision-making – with implications for our ability to make the biggest financial gains.

When people trade stocks, they don’t always learn from experience

Even when we learn from past mistakes, we may never become optimal decision-makers. The finding comes from an analysis of a mathematical game that simulates a large economy, and suggests we may need to rethink some of the common assumptions built into existing economic theories.

In such theories, people are typically represented as rational agents who learn from past experiences to optimise their performance, eventually reaching a stable state in which they know how to maximise their earnings. This assumption surprised Jérôme Garnier-Brun at École Polytechnique in France because, as a physicist, he knew that interactions in nature – such as those between atoms – often result in chaos rather than stability. He and his colleagues mathematically tested whether economists are correct to assume that learning from the past can help people avoid chaos.

They devised a mathematical model for a game featuring hundreds of players. Each of these theoretical players can choose between two actions, like buying or selling a stock. They also interact with each other, and each player’s decision-making is influenced by what they have done before – meaning each player can learn from experience. The researchers could adjust the precise extent to which a player’s past experiences influenced their subsequent decision-making. They could also control the interactions between the players to make them either cooperate or compete with each other more.

With all these control knobs available to them, Garnier-Brun and his colleagues used methods from statistical physics to simulate different game scenarios on a computer. The researchers expected that in some scenarios the game would always result in chaos, with players unable to learn how to optimise their performance. Economic theory would also suggest that, given the right set of parameters, the virtual players would settle into a stable state where they have mastered the game – but the researchers found that this wasn’t really the case. The most likely outcome was a state that never settled.

Jean-Philippe Bouchaud at École Polytechnique, who worked on the project, says that in the absence of one centralised, omniscient, god-like player that could coordinate everyone, regular players could only learn how to reach “satisficing” states. That is, they could reach a level that satisfied minimum expectations, but not much more. Players gained more than they would have done by playing at random, so learning was not useless, but they still gained less than they would have if past experience had allowed them to truly optimise their performance.

“This work is such a powerful new way of looking at the problem of learning complex games and these questions are fundamental to the construction of models of economic decision-making,” says Tobias Galla at the Institute for Cross-Disciplinary Physics and Complex Systems in Spain. He says the finding that learning typically does not lead to outcomes better than satisficing could also be important for processes like foraging decisions by animals or for some machine learning applications.

Bouchaud says his team’s game model is too simple to be immediately adopted for making predictions about the real world, but he sees the study as a challenge to economists to drop many assumptions that currently go into theorising processes like merchants choosing suppliers or banks setting interest rates.

“The idea that people are always making complicated economic computations and learn how to become the most rational agents, our paper invites everyone to move on [from that],” he says.

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

*Credit for article given to Karmela Padavic-Callaghan*

 

Some students get their first look at manipulating equations when they learn how to convert a repeating decimal to its corresponding fraction (rational numbers yield terminating decimals, or non-terminating repeating decimals). Playing with fractions and decimals is always good in itself, but there are also two nice side-benefits to this simple calculation: first, you can see the surprising result that  0.999… = 1, and second, it helps answer the question ‘which fractions lead  to terminating decimals, and which lead to repeating decimals?’ Better still, it leads to other questions.

1. The calculation – turning decimals into fractions

A repeating decimal like 0.633633… can be written as a fraction by writing out the equation x =  0.633633…, and then manipulating it so that the infinitely long repeated parts get eliminated. The manipulation is done by multiplying the equation by the right power of 10 to shift the digits, and then subtracting off the original equation.

Perhaps you have a more complicated repeating decimal that you want to fractionalize. The procedure remains essentially the same: obtain two equations that have the same “decimal part” that can be eliminated by subtracting. You might have to shift twice in order to accomplish this. Here is an example:

2. Showing that 0.999… = 1

This school mathematics result has been made into a popular topic of discussion on the Internet. Try doing a search on “0.999 = 1”, and see what you find.

3. Which fractions terminate, and which keep going?

A fraction can sometimes give us a terminating decimal, and sometimes a repeating decimal. It is reasonable to wonder what kind of fractions lead to each kind of decimal.

Thinking about the procedure above might give you an idea for how to think about this question.

If we have a situation where a fraction x = p/q is a terminating decimal, it means that there must be some power of 10, say 10^n, that if we multiply x by  this power we can completely eliminate the decimal (i.e. multiplying by 10^n gives us an integer). This could only happen if the denominator q divides 10^n. This would require q to be of the form (2^m)(5^k), where the exponents m and k are non negative integers (possibly zero), and n = max(m, k).

So, a fraction p/q terminates if and only if the denominator is of the form (2^m)(5^k). Consequently, fractions such as 1/2, 3/5, 9/25, 7/8, 3/200, are all terminating, and, for example, any fraction of the form 1/p where p is a prime that is not 2 or 5, will be non-terminating and repeating.

It is reasonable to ask questions about how long the decimals or their repeating parts can be. For a non-terminating repeating decimal, questions about the length of the repeating part are harder to answer.

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

*Credit for article given to dan.mackinnon*

Maths tells us the best way to cover a surface with copies of a shape – even when it comes to jigsaw puzzles, says Katie Steckles.

WHAT do a bathroom wall, a honeycomb and a jigsaw puzzle have in common? Obviously, the answer is mathematics.

If you are trying to cover a surface with copies of a shape – say, for example, you are tiling a bathroom – you ideally want a shape like a square or rectangle. They will cover the whole surface with no gaps, which is why these boring shapes get used as wall tiles so often.

But if your shapes don’t fit together exactly, you can still try to get the best coverage possible by arranging them in an efficient way.

Imagine trying to cover a surface with circular coins. The roundness of the circles means there will be gaps between them. For example, we could use a square grid, placing the coins on the intersections. This will cover about 78.5 per cent of the area.

But this isn’t the most efficient way: in 1773, mathematician Joseph-Louis Lagrange showed that the optimal arrangement of circles involves a hexagonal grid, like the cells in a regular honeycomb – neat rows where each circle sits nestled between the two below it.

In this situation, the circles will cover around 90.7 per cent of the space, which is the best you can achieve with this shape. If you ever need to cover a surface with same-size circles, or pack identical round things into a tray, the hexagon arrangement is the way to go.

But this isn’t just useful knowledge if you are a bee: a recent research paper used this hexagonal arrangement to figure out the optimal size table for working a jigsaw puzzle. The researchers calculated how much space would be needed to lay out the pieces of an unsolved jigsaw puzzle, relative to the solved version. Puzzle pieces aren’t circular, but they can be in any orientation and the tabs sticking out stop them from moving closer together, so each takes up a theoretically circular space on the table.

By comparing the size of the central rectangular section of the jigsaw piece to the area it would take up in the hexagonal arrangement, the paper concluded that an unsolved puzzle takes up around 1.73 times as much space.

This is the square root of three (√3), a number with close connections to the regular hexagon – one with a side length of 1 will have a height of √3. Consequently, there is also a √3 in the formula for the hexagon’s area, which is 3/2 × √3 × s², where s is the length of a side. This is partly why it pops out, after some fortuitous cancellation, as the answer here.

So if you know the dimensions of a completed jigsaw puzzle, you can figure out what size table you need to lay out all the pieces: multiply the width and height, then multiply that by 1.73. For this ingenious insight, we can thank the bees.

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

*Credit for article given to Katie Steckles*

There are plenty of probability problems that have counter-intuitive solutions. Problems like these, and how they can undermine common sense, are among the best reasons for looking at probability theory. One set of humbling questions is the family of Monty Hall problems. Another are those related to conditional probability; nice examples of these are problems that involve medical tests that give ‘false positive’ results.

Simulation is a way of exploring these problems that reveals more than mere theoretical probability calculations do. The structure of the simulation can reflect interesting aspects of the structure of the original problem, and the results reveal a variability that is not apparent when you simply calculate the theoretical probabilities on their own.

This post shows an example of a ‘false positive’ probability problem and a Fathom simulation for it. This problem was adapted from one found in the 4th edition of Ross’s A First Course in Probability (p.75):

A laboratory blood test is 95 percent effective in detecting a certain disease when it is, in fact, present. However, the test also yields a “false positive” result for one percent of healthy persons. (That is, if a healthy person is tested, there is a 0.01 probability that they will test positive for the disease, even though they don’t really have it.) If 0.5 percent of the population actually has the disease, what is the probability that a person who has a positive test result actually has the disease?

Here are the attribute definitions that you could use to build a Fathom simulation for this problem:

The attributes are enough to run the simulation, but it is better to also add the following measures:

To run the simulation you can add new cases (try ~500). Using a measures collection, you can re-run this experiment hundreds of times (collecting a 100 measures re-runs the 500 person experiment 100 times).

If you are calculating the theoretical probability by hand, it helps to write down all of the probabilities (fill in the blanks…):

It also helps to visualize the probabilities in a tree diagram:

The outer tips of the tree are filled in using the multiplicative rule for conditional probabilities:

One nice thing about doing this is that you can see how the tree diagram used to calculate the theoretical probabilities is structured in the same way as the “if” statements in the simulation.

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

*Credit for article given to dan.mackinnon*

Our best efforts to gauge threats may be counter-productive.

Assessing risk is something everyone must do every day. Yet few are very good at it, and there are significant consequences of the public’s collective inability to accurately assess risk.

As a first and very important example, most people presume, as an indisputable fact, that the past century has been the most violent in all history — two devastating world wars, the Holocaust, the Rawanda massacre, the September 11 attacks and more — and that we live in a highly dangerous time today.

And yet, as Canadian psychologist (now at Harvard) Steven Pinker has exhaustively documented in his new book The Better Angels of Our Nature: Why Violence Has Declined, the opposite is closer to the truth, particularly when normalised by population.

As Pinker himself puts it:

“Believe it or not — and I know most people do not — violence has been in decline over long stretches of time, and we may be living in the most peaceful time in our species’ existence. The decline of violence, to be sure, has not been steady; it has not brought violence down to zero (to put it mildly); and it is not guaranteed to continue.

“But I hope to convince you that it’s a persistent historical development, visible on scales from millennia to years, from the waging of wars and perpetration of genocides to the spanking of children and the treatment of animals.”

How could the public perception be so wrong? The news media is partly to blame — good news doesn’t sell much advertising space. But the problem might go even deeper: we may be psychologically disposed to miscalculate risk, perhaps as an evolutionary response to danger.

One well-known problem is the “conjunction fallacy” — the common predilection to assign greater probability to a more specialised risk.

One indication of our inability to objectively assess risk is the fanatical and often counter-productive measures taken by parents nowadays to protect children. Some 42 years years ago, 67% of American children walked or biked to school, but today only 10% do, in part stemming from a handful of highly publicised abduction incidents.

Yet the number of cases of real child abduction by strangers (as opposed to, say, a divorced parent) has dwindled from 200-300 per year in the 1990s to only about 100 per year in the US today.

Even if one assumes all of these children are harmed (which is not true), this is still only about 1/20 the risk of drowning and 1/40 of the risk of a fatal car accident.

Such considerations many not diminish the tragedy of an individual loss, but they do raise questions of priority in prevention. Governments worldwide often agonise over marginal levels of additives in certain products (agar in apples in the 1980s and asbestos insulation in well-protected ceilings), while refusing to spend money or legislate for clear social good (smoking in the developing world, gun control, infectious disease control, needle exchange programs and working conditions in coal mines).

One completely absurd example is the recent surge of opposition in the U.S. (supposedly on health concerns) to “smart meters,” which once an hour send usage statistics to the local electric or natural gas utility.

The microwave exposure for these meters, even if you are standing just two feet from a smart meter when it broadcasts its data, is 550 times less than standing in front of an active microwave oven, up to 4,600 times less than holding a walkie-talkie at your ear, and up to 1,100 times less than holding an active cell phone at your ear.

It is even less than sitting in a WiFi cyber cafe using a laptop computer.

A much more serious example is the ongoing hysteria, especially in the UK and the US, over childhood vaccinations. Back in 1998, a study was published in the British medical journal Lancet claiming that vaccination shots with a certain mercury compound may be linked to autism, but other studies showed no such link.

In the meantime, many jumped on the anti-vaccination bandwagon, and several childhood diseases began to reappear, including measles in England and Wales, and whooping cough in California. We should note the rate of autism is probably increasing.

Finally, in January 2011, Lancet formally acknowledged that the original study was not only bad science (which had been recognised for years), but further an “elaborate fraud”.

Yet nearly one year later, opposition to vaccination remains strong, and irresponsible politicians such as would-be-US-President Michele Bachmann cynically (or ignorantly?) milk it.

A related example is the worldwide reaction to the Fukushima reactor accident. This was truly a horrible incident, and we do not wish to detract from death and environmental devastation that occurred. But we question decisions such as that quickly made by Germany to discontinue and dismantle its nuclear program.

Was this decision made after a sober calculation of relative risk, or simply from populist political pressure? We note this decision inevitably will mean more consumption of fossil fuels, as well as the importation of electricity from France, which is 80% nuclear.

Is this a step forward, or a step backward? We also note that concern about global warming is, if anything, more acute than ever in light of accelerating carbon consumption.

This kind of over-reaction — to which many of us are prey — is exacerbated by cynical and exploitive individuals, such as Bill and Michelle Deagle and Jeff Rense, who profit from such fears by peddling bogus medical products, speaking at conspiracy conventions for hefty fees, and charging for elite information.

This is just one instance of a large, growing and dangerous co-evolution of creationist, climate-denial and other anti-science movements.

How do we protect against such misinformation and misperceptions? The complete answers are complex but several things are clear.

First of all, science education must be augmented to address the assessment of risk — this should be a standard part of high school mathematics, as should be more attention to the information needed to make informed assessment.

Second, the press needs to be significantly more vigilant in critically commenting on dubious claims of public risk by citing literature, consulting real experts, and so on. Ideally, we should anticipate scientifically trained and certified scientific journalists.

Third, mathematicians and scientists themselves need to recognise their responsibility to help the public understand risk. Failure to do so, well, poses a serious risk to society.

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

*Credit for article given to Jonathan Borwein (Jon)*