Skip to content

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]

4 Comments leave one →
  1. February 13, 2020 12:45 pm

    Are you insinuating #P is easy?

    • February 13, 2020 3:37 pm

      No. But there may be cases of evaluation that are easy or that are amenable to unusual notions of partial evaluation.

      • February 17, 2020 5:04 pm

        So what class of counting problem you think this would be helpful?

      • February 18, 2020 11:51 am

        As a full class, that’s especially hard to say. One of the ramifications I read into the P-vs-#P “dichotomy” work is that there probably is no good natural counting characterization of BQP. But cases of hard problems can be easy.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s