Dyson as a Mathematician
With a lemma from 1947 that might be useful today?
Cropped from article on his letters |
Freeman Dyson passed away last February 28th, one day short of the leap day, February 29th. He was one of the great physicists, one of the great writers about science, and one of the great thinkers of all time. He is missed.
Today we wish to discuss a tiny part of Dyson’s contributions to mathematics—and ask whether it has been developed further.
Reductions and Jokes
Plus a teaching idea that’s no joke?
Cropped from Maths History source |
Emil Post was the first to use the formal notion of reduction between problems. We discussed Post’s wonderful work and its relevance to complexity earlier here.
Today Ken and I want to discuss the notion of reduction, and also perhaps some jokes for your amusement.
Read more…
Should We Teach Coding in High School?
Robert Sedgewick and Larry Cuban faced off today in the Wall Street Journal (WSJ) on the issue:
Should everyone be taught coding in high school?
Today we will discuss their recent comments on this issue.
Read more…
P=NP: A Story
The P=NP story without symbols.
[ The Movie ] |
Dr. Strangelove is the classic 1964 movie about the potential for nuclear war between the US and the Soviet Union during the cold war. The film was directed by Stanley Kubrick and stars Peter Sellers, George Scott, Sterling Hayden, and Slim Pickens.
Today we try to explain the P=NP problem in an “analog” fashion.
In Dr. Strangelove, US President Merkin Muffley wishes to recall a group of US bombers that are incorrectly about to drop nuclear weapons on Russia. He hopes to stop war. Here is the conversation between General Turgidson played by Scott and Muffley played by Sellers, in which Turgidson informs that the recall message will not be received…
Turgidson: …unless the message is preceded by the correct three-letter prefix.Muffley: Then do you mean to tell me, General Turgidson, that you will be unable to recall the aircraft?
Turgidson: That’s about the size of it. However, we are plowing through every possible three letter combination of the code. But since there are seventeen thousand permutations it’s going to take us about two and a half days to transmit them all.
Muffley: How soon did you say the planes would penetrate Russian radar cover?
Turgidson: About eighteen minutes from now, sir.
This is the problem that P=NP addresses. How do you find a solution to a problem that has many potential solutions? In this case there are over thousands of possible combinations. Since each requires sending a message to an electronic unit that sits on a plane, thousands of miles away, and since messages cannot be sent too often, it will take much too long to find the secret message.
The central P=NP question is: Can we do better than trying all possibilities? The answer is yes—at least in the case of the movie, the secret combination is indeed found. More on that in a moment.
Opening Mechanical Locks
In Dr. Strangelove the issue is finding the three letter code for a certain device that sits on the bombers. The protocol is: Send a three letter code to the bombers. If the code is correct, then the bombers will be recalled, and all is saved. If the code is wrong, then nothing happens.
Instead of this, consider the same type of problem for finding the combination to a mechanical lock. That is a lock that is often at a gym, for example, to protect your belongings. Recall you spin the lock’s dial three times to the right, stop on the first number, then turn one time to the left, stop on the second number, and finally go to the right to stop at the third number. Then you pull the lock open.
This works provided you know the combination. In general there are 64,000 such combinations. So unless you know the numbers, you are in trouble. Trying all possible combinations is not possible for mortals. But there is hope. It is possible to find the combination without knowing it. This is possible provided: You have the combination lock in your hands.
If you only can send a possible combination to someone else to try, you are out of luck. Unfortunately in Dr. Strangelove the device on the bomber is not in your hands. So as the General says, we are trying all the possible combinations one at a time. But if the device is local you can do better.
Breaking The Locks
There are many sites on the web that explain how to do much better. Here is one way to find the first number for a lock:
- Pull up gently on the shackle and hold it in place. Turn the dial clockwise listening carefully until you hear the lock click.
- Start with a good deal of pressure and gently let up as you spin it around, until you meet resistance in only one place. It should catch in only one place, making a click.
- Add 5 to that number and write it down.
This is the first number in the combination. There are similar methods to get the remaining two numbers. But already you have reduced the choices for the combination from 64,000 by a factor of 40. The rest of the how-to-do rules help you get the remaining two numbers.
Note this attack relies on physical properties of the lock. A lock is made from springs and gears and rods, and is not perfect. As you turn the dial the mechanical parts rub and make noises. These noises reveal information, that is useful to you. Information that can reveal the combination of the lock.
Opening Digital Locks
The point is that there is a way to open a lock without knowing the combination. Here the trick is that you can try and use the lock and play with it in a way that it reveals information about its secret combination. This is what the P=NP question asks:
Are there ways to manipulate a digital lock and get it to reveal information?
Put another way: Do digital locks make noise?
Essentially P=NP is true if digital locks all are imperfect, like mechanical locks. That is, if digital locks all make noise. It is widely believed that is false. The belief is that P NP which means that there are essentially perfect digital locks. That is some digital locks make no noise.
P NP
Why is it believed that digital locks can be perfect? Well the answer is simple. To date certain types of digital locks have not been broken. That is no one yet knows how to make them click and reveal information. This is of course a dangerous position for several reasons.
- The failure to break a lock does not mean that someone cleverer cannot break it.
- There are reasons that if some people knew how to break certain digital locks that they would not tell anyone. They might prefer to keep their ability secret to make money or cause harm.
- Finally, it seems dangerous to guess that anything can be done without noise.
The latter point is that making systems work perfectly is usually impossible. Mechanical systems must have friction of some kind, and it seems possible that digital systems will also. We will see.
Smart Search
Colonel Ripper, played by Hayden, is the one that launched the bombers against Russia. The recall code is found and the bombers are recalled. An officer named Mandrake, played by Sellers too, notices some doodles on a pad by the crazy Ripper. It is covered with an interlocking pattern of the words Peace On Earth, and Purity Of Essence. Ripper is obsessed with these ideas—do not ask why.
Mandrake: Peace on Earth. Peace on Earth. Peace on Earth: P O E.
Purity of essence. O P E. (whispers) O P E.
This is the key. This information is sent to the Pentagon and soon the bombers are recalled. The search space is cut down from thousands to 6 possible orders. Success. Well if you’ve seen the movie, you know it was not exactly success, but that failure has nothing to do with our attempt to explain the P=NP question.
This second idea is different from whether locks make noise. It is whether every lock has a giveaway by dint of the process by which we obtained that particular lock to begin with. Note that the lock is not the definition of the problem itself, like SAT or graph 3-coloring, but rather a particular instance of the problem. We have discussed how instances of factoring that tend to be generated by algorithms have collective giveaways in an earlier post—which quotes another part of Dr. Strangelove.
Open Problems
I love the movie Dr. Strangelove, and love any excuse to talk about it. So please forgive me this story about P=NP. I hope that trying to understand the P=NP question without complex notation may help us better understand it. What do you all think?
A Beetle Math Puzzle
Lessons from a puzzle about prime numbers
[ Wikipedia ] |
Doron Zeilberger is a famous combinatorial mathematician based at Rutgers. He is noted for actively using computers in research. His computers even get co-authorship credit under the name “Shalosh B. Ekhad,” which is Hebrew for 3B1—a computer that came from building 3, corridor B, room 1 of AT&T Bell Labs.
Today I thought we would talk about a recent joint paper of Zeilberger on Covering Systems.
This paper has one co-author who is human, Anthony Zaleski, also of Rutgers. It starts with a puzzle about beetles on a circular track. The puzzle does not need a computer to solve—though a computerized visualization would make it more enjoyable. It makes several interesting points, points that are distinctly human, and I hope you might enjoy it.
The Puzzle
They ascribe the puzzle to Jean-Paul Delahaye, who modified Peter Winkler’s writeup of a folk puzzle that Winkler stated about ants.
One places nine beetles on a circular track, where the nine arc distances, measured in meters, between two consecutive beetles are the first nine prime numbers, . The order is arbitrary, and each number appears exactly once as a distance.
At the starting time, each beetle decides randomly whether she would go, traveling at a speed of 1 meter per minute, clockwise or counter-clockwise. When two beetles bump into each other, they immediately do a “U-turn”, i.e. reverse direction. We assume that the size of the beetles is negligible. At the end of minutes, after many collisions, one notices the distances between the new positions of the beetles.
Note that there are two levels of probability: the initial order of the vector of distances and the initial direction of each beetle. Yet after minutes there is a high probability of the distances being exactly the same: the first nine prime numbers. Is this a miracle? What is the probability?
The Lessons
The point is we have deliberately stated the puzzle to make it harder. The way we stated it is misleading and the following lessons are hints to help solve the puzzle.
- That the arc lengths are prime numbers is unimportant. The puzzle works whether or not the distances between the beetles are prime numbers.
- The probability is that the beetles are at the given positions. There is no chance that they will not arrive at the antipode points. None.
The Solution
The first observation is that the circular track’s length is
The second is that the probability is that the distances are the same after minutes. Imagine that each beetle carries a flag. Instead of reversing direction when they collide, let the beetles exchange their flags and continue moving as before. Now the flags always are moving in the same direction at the same speed. This means that after minutes the flags are at the antipode position. But the beetles are located at the same places as flags, and so the distances are the same as before. Note, the beetles are each located at the position of some unique flag, but which flag can change many times.
The only constraint is that the distance traveled in minutes divides the length of the circular track. The fact that the distances are primes is never used.
Open Problems
Zaleski and Zeilberger say:
We point out that very often primes are red herrings. This is definitely the case for covering system, and who knows, perhaps also for the Riemann Hypothesis.
I assume this is a bit tongue in cheek, but their point is valid. Do we miss solutions to problems when we use information that is not really important? How do we decide which information is key and which is redundant? This why I like this puzzle.
Using Negative Nodes to Count
A deeper basis for generalized Tutte-Grothendieck invariants
Via Psychology Today article |
Alexander Grothendieck peppered algebraic geometry with nilpotent elements. He augmented spaces with elements such that for some power , . Despite debates over whether such ephemeral entities could be “natural,” they make many calculations nicer.
Today we ask whether some additions to graph theory may have similar effect.
Adding extra elements to avoid special cases is an old idea that happens throughout mathematics. Gerolamo Cardano made perhaps the first mention of in his work on solving cubic equations in 1545, but argument swirled on whether is a true mathematical object. The term “imaginary number” was coined by René Descartes in 1637 to sneer at it, and took over a century more to gain wide acceptance.
Regarding nilpotents, a commenter in a MathOverflow item nine years ago expressed the motivation in terms analogous to our purpose:
Grothendieck introduced nilpotents for many reasons … to get correct counting in degenerate situations, it is typically necessary to allow nilpotents; they are also the bedrock of [other] ideas in algebraic geometry.
His comment went on to describe a situation where nilpotents allow one to reduce the task of checking certain properties to well-behaved cases. he continued:
This is a powerful method, which … comes up in lots of places, e.g. in establishing basic properties of abelian schemes, by reducing to the abelian variety case.
Other comments show how nilpotents make counting come out right. An early-2015 obituary by the algebraic geometers David Mumford and John Tate gave the motivation of modeling small under assumptions like , and my own memorial post gave other aspects of them. We wonder whether something roughly analogous can make a counting tool in combinatorics—one already co-named for Grothendieck—more acute for purposes such as evaluating quantum circuits.
Duality and Isolated Nodes
In our previous post we discussed how the 2-polymatroid dual of a graph is an isomorphism invariant so that . This requires shifting attention to the structure where the rank function is defined for all subsets of by
Here is allowed so can have loops, and the definition if coherent even if is a multiset—the ambiguity of which of multiple edges is “” does not matter. The definition does exclude circles, which touch no vertex but can still belong to . That is OK because circles contribute to the rank in all cases.
There is, however, an asterisk: the structure ignores any isolated nodes may have. Isolated nodes do not contribute anything to any subset of . Thus we really have iff has no isolated nodes.
Our last post showed examples where deleting an edge in corresponded to “exploding” it in . Let us flip that around so that the deletion occurs in , the explosion in . Here is the example of the “lollipop” graph:
The operations do not quite commute because the deletion of the edge leaves an isolated node, whereas the explosion of in the dual—as it was defined—does not. What should go in place of the ‘(?)’? We contend that the answer is: a negative isolated node. We denote it by , whereas an ordinary isolated node is .
All uses of that we need can come from one extra clause in the definition of explosion given there and in the major reference of our post on explosion last summer:
Exploding a loop, as opposed to a regular edge, also introduces one . Exploding a circle leaves two: .
A Simple Recurrence and Duality
At the end of a recent post we noted that for the planar dual or other surface dual of a graph , deleting an edge in contracts the corresponding edge of . This lends mathematical power to the deletion-contraction recurrence by which William Tutte defined his polynomial . We denote deletion by , contraction by , and explosion by .
What we call “explosion” is the effect on graphs of the notion of contraction that applies to matroids, in particular graphic 2-polymatroids (G2PMs). James Oxley and Geoff Whittle, in their 1993 paper which we featured in a previous post, define a generalized Tutte-Grothendieck invariant (GTGI) to be any algebraic quantity that obeys a recurrence with deletion and matroid contraction (which we call explosion) instead:
Their definition does not specify base cases. All previous papers we’ve found have used one-edge graphs as their base cases. Our first benefit of negative isolated nodes is that we can define a basis for zero edges in a way that reveals even more cleanly that GTGIs are basically polynomials. Define:
Here and can be arbitrary objects, not just variables, but the point is that we can always treat them as variables. Thus all of these rules define a polynomial which we call . It is not immediately clear that this is well defined—i.e., independent of the order in which edges are chosen.
Now we look at the one-edge cases, which are the circle , the loop , and the graph of one regular edge. We obtain:
This is pleasingly symmetric, which bodes well for effective use of duality. Note that switching with and with preserves but interchanges with . Recall from the previous post that is self-dual while and are dual to each other. This is no accident:
Theorem 1 For any generalized Tutte-Grothendieck invariant and (graphical) 2-polymatroid ,
The proof is immediate by the base cases and , the form of the recursion (1), and the duality of deletion and explosion via .
Abbreviate for the case to just . We will connect to the polynomial introduced by Oxley and Whittle as discussed in our post. They use the term “recipe theorem” for the general idea that all GTGIs are evaluations of the single at different points, ascribing it to work by Oxley with Dominic Welsh, who was my own doctoral advisor a few years after Oxley.
Re-Basing the Recipe Theorem
Henceforth let stand for a graph augmented with both circles and negative isolated nodes. The associated G2PM is where is the rank function as above. Let stand for the number of negative isolated nodes and for the count of nodes in which each counts . That is, .
Theorem 2 (Recipe Theorem) For all , with ,
Proof: For the base case of a completely empty graph, we have and , so . For the base case of a single isolated node, but , so we get
as required. For we have so we get
again as required of . If is a disjoint union of and , multiplicativity goes through because and for the respective components.
Now let be any edge in . Note that in , the new equals whether is a regular edge or a loop, the latter owing to introducing one . Supposing by induction that (2) is valid for and for , that is all we need in order to calculate:
Representation Theorem
The analogous recipe theorem in Oxley and Whittle’s paper bases everything on their rank-generating function for an arbitrary 2-polymatroid :
Although isolated nodes are immaterial for graphical 2-polymatroids, we augment them to include and . We replace by the signed node count and use its negative portion separately. By characterizing , the recipe theorem extends this representation even further:
Theorem 3 (Representation Theorem) For any G2PM with rank function ,
This says that is just an extension of from G2PMs to our augmented class of graphs. We give a fresh proof of the theorem.
Proof: For the completely empty graph, there is just the term and all exponents are zero, so the value is as required. For , we have the term for with (and ), which leaves . For , we have and also . The result is , again as required.
Because this is proving confluence, the only case of disjoint graphs we need to consider is adding one or . The above shows that the effect is to multiply by , or respectively, by . To save the case of recursing on below, we include that here: is just without adding the circle, whereas adds two , so the net effect is multiplying by , again as required.
This also lets us suppose that has no isolated nodes, so after all, and we may let be any member of . Again write for ; note that both and may have and/or . Consider subsets of that do not contain . Then Therefore when we begin the induction:
the first term already gives us the part of the sum in (3) that is over without . So we need only show that
Note that the edge set of can be identified with , even though some edges may become loops or circles. If is a loop then still has but . Thus we have by induction:
Equating (4) and (5) as formal polynomials gives the same necessary and sufficient condition on the powers of and :
This is true because always touches the one-or-two nodes that are exploded away, whereas does not touch them in (but touches everything else touches in ) and the difference is .
Combined with the recipe theorem we obtain the following, which re-emphasizes that for real is always a real polynomial:
Corollary 4 For any augmented G2PM with rank function , and all :
The Points
The quick finish to the proof of Theorem 3—combining what could be several cases of versus into one—can also be viewed through the lens of duality. Then the complement of in does not include , so is unchanged by removing . As we noted in the previous post, however, need not be the rank function of a graph. Thus the proof gives a handle on manipulating a wider class of structures via graph theory. It moreover seems extendable to all 2-polymatroids augmented with , so as to give extending .
The beauty of the recipe theorem is that a whole host of recursions become encoded by evaluations of the polynomials . As we noted with the Tutte polynomial and with the Oxley-Whittle polynomial , evaluations of them at certain points convey information about the graphs. For many points the information is -hard.
The case we care most about now is , . We showed how this evaluates the tractable subclass of quantum stabilizer circuits. This makes imaginary, but by Corollary 4 the values at real points are real.
When we have , so the value agrees with the polynomial in that post. The fact that evades the -hardness technique in the paper by Steve Noble which we also discussed there. So let us now abbreviate as . Then evaluates stabilizer circuits in polynomial time.
What other points are easy to evaluate, given ?
The point may even be nontrivial. If has no isolated nodes then the sum is over spanning edge-subsets and becomes
Is this in polynomial time?
Open Problems
What more can we gain from this augmentation and streamlining of Tutte-Grothendieck invariants? Can we find further characterizations of the polynomials and ? What can be done with -polymatroids with , which might allow evaluating more quantum circuits?
[some word improvements]
Counting Votes By Humans
A new way to agree on calculations
Cropped from ABC News source |
Troy Price is the Iowa Democratic Party Chair. He was in charge of Iowa’s primary vote. The vote totals were due Monday night but have not been finished, now three nights later, and may need to be re-tallied. At a press conference to explain the cause for the delay—mainly a failed phone app—Price was asked, “How can anyone trust you now?”
Today, Ken and I discuss a way to make counting votes quickly checkable by humans.
Read more…