Skip to content

Dyson as a Mathematician

March 3, 2020


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.

Read more…

Reductions and Jokes

February 28, 2020


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?

February 24, 2020

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

February 20, 2020


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:

  1. Pull up gently on the shackle and hold it in place. Turn the dial clockwise listening carefully until you hear the lock click.

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

  3. 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{\neq} NP which means that there are essentially perfect digital locks. That is some digital locks make no noise.

P{\neq} 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.

  1. The failure to break a lock does not mean that someone cleverer cannot break it.

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

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

February 16, 2020


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, {2,3,5,7,11,13,17,19,23}. 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 {50} 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 {50} 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 {1} 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

\displaystyle  2+3+5+7+11+13+17+19+23=100.

The second is that the probability is {1} that the distances are the same after {50} 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 {50} 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 {50} 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

February 11, 2020


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 {x} such that for some power {a}, {x^a = 0}. 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 {i} in his work on solving cubic equations in 1545, but argument swirled on whether {i} is a true mathematical object. The term “imaginary number” was coined by René Descartes in 1637 to sneer at it, and {i} 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 {\epsilon} under assumptions like {\epsilon^2 = 0}, 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 {G^*} of a graph {G = (V,E)} is an isomorphism invariant so that {(G^{*})^* = G}. This requires shifting attention to the structure {(E,r_G)} where the rank function {r_G} is defined for all subsets {A} of {E} by

\displaystyle  r_G(A) = ||\{u \in V: (\exists v \in V)(u,v) \in A\}||.

Here {v = u} is allowed so {A} can have loops, and the definition if coherent even if {A} is a multiset—the ambiguity of which of multiple edges is “{(u,v)}” does not matter. The definition does exclude circles, which touch no vertex but can still belong to {A}. That is OK because circles contribute {0} to the rank in all cases.

There is, however, an asterisk: the structure {(E,r_G)} ignores any isolated nodes {G} may have. Isolated nodes do not contribute anything to any subset of {E}. Thus we really have {(G^{*})^* = G} iff {G} has no isolated nodes.

Our last post showed examples where deleting an edge in {G^*} corresponded to “exploding” it in {G}. Let us flip that around so that the deletion occurs in {G}, the explosion in {G^*}. Here is the example of the “lollipop” graph:

The operations do not quite commute because the deletion of the edge {b} leaves an isolated node, whereas the explosion of {b} 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 {\ominus}, whereas an ordinary isolated node is {\bullet}.

All uses of {\ominus} 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 {\ominus}. Exploding a circle leaves two: {\ominus~\ominus}.

A Simple Recurrence and Duality

At the end of a recent post we noted that for the planar dual or other surface dual {G'} of a graph {G}, deleting an edge in {G} contracts the corresponding edge of {G'}. This lends mathematical power to the deletion-contraction recurrence by which William Tutte defined his polynomial {T_G(x,y)}. We denote deletion by {G \setminus e}, contraction by {G/e}, and explosion by {G \backslash\!\backslash e}.

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 {\phi_G} that obeys a recurrence with deletion and matroid contraction (which we call explosion) instead:

  • If {G} is a disjoint union of {G'} and {G''}, then {\phi(G) = \phi({G'})\phi({G''})};

  • For any edge or loop {e} in {G},

    \displaystyle  \phi(G) = \alpha\phi({G \setminus e}) + \beta\phi({G \backslash\!\backslash e}). \ \ \ \ \ (1)

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 {\phi} are basically polynomials. Define:

\displaystyle  \phi({\emptyset}) = 1,\quad \phi(\bullet) = x,\quad \phi({\ominus}) = y.

Here {x} and {y} 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 {R_{G,\alpha,\beta}(x,y)}. It is not immediately clear that this is well defined—i.e., independent of the order in which edges {e} are chosen.

Now we look at the one-edge cases, which are the circle {\bigcirc}, the loop {G_1}, and the graph {G_2} of one regular edge. We obtain:

\displaystyle  \begin{array}{rcl}  R_{\bigcirc,\alpha,\beta}(x,y) &=& \alpha + \beta y^2;\\ R_{G_1,\alpha,\beta}(x,y) &=& \alpha x + \beta y;\\ R_{G_2,\alpha,\beta}(x,y) &=& \alpha x^2 + \beta. \end{array}

This is pleasingly symmetric, which bodes well for effective use of duality. Note that switching {x} with {y} and {\alpha} with {\beta} preserves {R_{G_1,\alpha,\beta}(x,y)} but interchanges {R_{\bigcirc,\alpha,\beta}(x,y)} with {R_{G_2,\alpha,\beta}(x,y)}. Recall from the previous post that {G_1} is self-dual while {G_2} and {\bigcirc} are dual to each other. This is no accident:

Theorem 1 For any generalized Tutte-Grothendieck invariant {R_{G,\alpha,\beta}(x,y)} and (graphical) 2-polymatroid {G},

\displaystyle  R_{G^*,\alpha,\beta}(x,y) = R_{G,\beta,\alpha}(y,x).

The proof is immediate by the base cases {\bullet} and {\ominus}, the form of the recursion (1), and the duality of deletion and explosion via {G \backslash\!\backslash e = (G^* \setminus e)^*}.

Abbreviate {R_{G,1,1}} for the case {\alpha,\beta = 1} to just {R_G}. We will connect {R_G} to the polynomial {S_G(x,y)} 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 {\alpha,\beta = 1} 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 {G = (V,E)} stand for a graph augmented with both circles and negative isolated nodes. The associated G2PM is {(E,r)} where {r = r_G} is the rank function as above. Let {n_{\ominus}} stand for the number of negative isolated nodes and {n} for the count of nodes in which each {\ominus} counts {-1}. That is, {n = |V| - 2n_{\ominus}}.

Theorem 2 (Recipe Theorem) For all {G,\alpha,\beta}, with {\rho = \sqrt{\frac{\beta}{\alpha}}},

\displaystyle  R_{G,\alpha,\beta}(x,y) = \alpha^{|E|}\rho^n R_G(\frac{x}{\rho}, \rho y). \ \ \ \ \ (2)

Proof: For the base case of a completely empty graph, we have {|E| = 0} and {n = 0}, so {R_{\emptyset,\alpha,\beta}(x,y) = R_{\emptyset}(\frac{x}{\rho}, \rho y) = 1}. For the base case of a single isolated node, {|E| = 0} but {n = 1}, so we get

\displaystyle  \rho R_{\bullet}(\frac{x}{\rho}, \rho y) = \rho\frac{x}{\rho} = x,

as required. For {\ominus} we have {n = -1} so we get

\displaystyle  \rho^{-1} R_{\ominus}(\frac{x}{\rho}, \rho y) =\rho^{-1} \rho y = y,

again as required of {R_{\ominus,\alpha,\beta}(x,y)}. If {G} is a disjoint union of {G'} and {G''}, multiplicativity goes through because {n = n' + n''} and {|E| = |E'| + |E''|} for the respective components.

Now let {e} be any edge in {G}. Note that in {G' = G \backslash\!\backslash r}, the new {n'} equals {n-2} whether {e} is a regular edge or a loop, the latter owing to introducing one {\ominus}. Supposing by induction that (2) is valid for {G} and for {G \setminus e}, that is all we need in order to calculate:

\displaystyle  \begin{array}{rcl}  R_{G,\alpha,\beta}(x,y) &=& \alpha R_{G \setminus e,\alpha,\beta}(x,y) \;+\; \beta R_{G \backslash\!\backslash e,\alpha,\beta}(x,y)\\ &=& \alpha \alpha^{|E|-1}\rho^n R_{G\setminus e}(\frac{x}{\rho}, \rho y) \;+\; \beta \alpha^{|E|-1}\rho^{n-2} R_{G \backslash\!\backslash e}(\frac{x}{\rho}, \rho y)\\ &=& \alpha^{|E|}\rho^n R_{G\setminus e}(\frac{x}{\rho}, \rho y) \;+\; \rho^2 \alpha^{|E|}\rho^{n-2} R_{G \backslash\!\backslash e}(\frac{x}{\rho}, \rho y)\\ &=& \alpha^{|E|} \rho^n (R_{G\setminus e}(\frac{x}{\rho}, \rho y) \;+\; R_{G\backslash\!\backslash e}(\frac{x}{\rho}, \rho y))\\ &=& \alpha^{|E|} \rho^n R_G(\frac{x}{\rho}, \rho y). \;\Box \end{array}

Representation Theorem

The analogous recipe theorem in Oxley and Whittle’s paper bases everything on their rank-generating function for an arbitrary 2-polymatroid {(E,f)}:

\displaystyle  S_E(x,y) = \sum_{A \subseteq E}x^{f(E) - f(A)} y ^{2|A| - f(A)}.

Although isolated nodes are immaterial for graphical 2-polymatroids, we augment them to include {\bullet} and {\ominus}. We replace {f(E)} by the signed node count {n} and use its negative portion {n_{\ominus}} separately. By characterizing {R_G}, the recipe theorem extends this representation even further:

Theorem 3 (Representation Theorem) For any G2PM {G} with rank function {r = r_G},

\displaystyle  R_G(x,y) = (xy)^{n_{\ominus}} \sum_{A \subseteq E}x^{n - r(A)} y ^{2|A| - r(A)}. \ \ \ \ \ (3)

This says that {R_G} is just an extension of {S_G} 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 {A = \emptyset} and all exponents are zero, so the value is {1} as required. For {\bullet}, we have the term for {A = \emptyset} with {n = 1} (and {n_{\ominus} = 0}), which leaves {x}. For {\ominus}, we have {n = -1} and also {n_{\ominus} = 1}. The result is {x^{-1}xy = y}, again as required.

Because this is proving confluence, the only case of disjoint graphs we need to consider is adding one {\bullet} or {\ominus}. The above shows that the effect is to multiply by {x}, or respectively, by {y}. To save the case of recursing on {e = \bigcirc} below, we include that here: {G \setminus e} is just {G} without adding the circle, whereas {G \backslash\!\backslash e} adds two {\ominus}, so the net effect is multiplying by {(1 + y^2)}, again as required.

This also lets us suppose that {G} has no isolated nodes, so {n = r(E)} after all, and we may let {e} be any member of {E}. Again write {G'} for {G\backslash\!\backslash e}; note that both {G'} and {G \setminus e} may have {\bullet} and/or {\ominus}. Consider subsets {B} of {E} that do not contain {e}. Then {r_{G \setminus e}(B) = r_G(B)} Therefore when we begin the induction:

\displaystyle  \begin{array}{rcl}  R_G(x,y) &=& R_{G \setminus e}(x,y) + R_{G'}(x,y)\\ &=& \sum_{B \subseteq E \setminus \{e\}}x^{n - r(B)} y ^{2|B| - r(B)} + R_{G'}(x,y), \end{array}

the first term already gives us the part of the sum in (3) that is over {B} without {e}. So we need only show that

\displaystyle  \sum_{B \subseteq E \setminus \{e\}}x^{n - r(B \cup \{e\})} y ^{2|B|+ 2 - r(B \cup \{e\})} = R_{G'}(x,y). \ \ \ \ \ (4)

Note that the edge set {E'} of {G'} can be identified with {E \setminus \{e\}}, even though some edges may become loops or circles. If {e} is a loop then {G'} still has {n' = n - 2} but {n_{\ominus} = 1}. Thus we have by induction:

\displaystyle \begin{array}{rcl} R_{G'}(x,y) &=& (xy)^{n_{\ominus}}\sum_{B \subseteq E \setminus \{e\}}x^{n' - r'(B)} y ^{2|B| - r'(B)}\\ &=& (xy)^{n_{\ominus}}\sum_{B \subseteq E \setminus \{e\}}x^{n - 2 - r'(B)} y ^{2|B| - r'(B)}. \end{array}  \ \ \ \ \ (5)

Equating (4) and (5) as formal polynomials gives the same necessary and sufficient condition on the powers of {x} and {y}:

\displaystyle  r(B \cup \{e\}) = r'(B) + (2 - n_{\ominus}).

This is true because {B \cup \{e\}} always touches the one-or-two nodes that are exploded away, whereas {B} does not touch them in {G'} (but touches everything else {B} touches in {G}) and the difference is {2 - n_{\ominus}}. \Box

Combined with the recipe theorem we obtain the following, which re-emphasizes that {R_{G,\alpha,\beta}(x,y)} for real {\alpha,\beta} is always a real polynomial:

Corollary 4 For any augmented G2PM {G} with rank function {r}, and all {\alpha,\beta \neq 0}:

\displaystyle  R_{G,\alpha,\beta}(x,y) = (xy)^{n_{\ominus}} \sum_{A \subseteq E} \beta^{|A|} \alpha^{|E \setminus A|} x^{n - r(A)} y ^{2|A| - r(A)}. \ \ \ \ \ (5)

The Points

The quick finish to the proof of Theorem 3—combining what could be several cases of {r(B \cup \{e\})} versus {r(B)} into one—can also be viewed through the lens of duality. Then the complement {B'} of {B \cup \{e\}} in {E} does not include {e}, so {r^*(B')} is unchanged by removing {e}. As we noted in the previous post, however, {r^*} 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 {\bullet,\ominus}, so as to give {R_E} extending {S_E}.

The beauty of the recipe theorem is that a whole host of recursions become encoded by evaluations of the polynomials {R_G(x,y)}. As we noted with the Tutte polynomial {T_G(x,y)} and with the Oxley-Whittle polynomial {S_G(x,y)}, evaluations of them at certain points {(x_0,y_0)} convey information about the graphs. For many points {(x_0,y_0)} the information is {\mathsf{\#P}}-hard.

The case we care most about now is {\alpha = 1}, {\beta = -\frac{1}{2}}. We showed how this evaluates the tractable subclass of quantum stabilizer circuits. This makes {\rho = \sqrt{\beta/\alpha}} imaginary, but by Corollary 4 the values at real points are real.

When {y = 2} we have {\rho y = \pm \sqrt{2}i}, so the value {R_{G,1,-1/2}(x,2)} agrees with the polynomial {Q(x)} in that post. The fact that {(\rho y)^2 = -2} evades the {\mathsf{\#P}}-hardness technique in the paper by Steve Noble which we also discussed there. So let us now abbreviate {R_{G,1,-1/2}(x,y)} as {Q_G(x,y)}. Then {Q_G(1,2)} evaluates stabilizer circuits in polynomial time.

What other points {Q_G(x_0,y_0)} are easy to evaluate, given {G}?

The point {(0,2)} may even be nontrivial. If {G} has no isolated nodes then the sum is over spanning edge-subsets {A} and becomes

\displaystyle  Q_{G}(0,2) = \sum_{\text{spanning} A \subseteq E} (-\frac{1}{2})^{|A|} 2 ^{2|A| - n} = \frac{1}{2^n} \sum_{\text{spanning} A \subseteq E} (-2)^{|A|}.

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 {R_G} and {Q_G}? What can be done with {k}-polymatroids with {k > 2}, which might allow evaluating more quantum circuits?


[some word improvements]

Counting Votes By Humans

February 7, 2020


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…