Skip to content

Tools and Sensitivity

July 12, 2019

Cutting right through a 30-year-old conjecture

Cropped from Emory homepage

Hao Huang is a mathematician and computer scientist at Emory University. Last week he released a paper of only six pages that solves the Boolean Sensitivity Conjecture, which goes back at least to a 1992 paper by Noam Nisan and Mario Szegedy.

Today we discuss his brilliant proof and what it means for sensitivity of the tools one employs.
Read more…


Mathematics of Gerrymandering

July 3, 2019

Can theory help?

source; art by Bill Hennessy

John Roberts is the Chief Justice of the United States.

Today I will discuss the recent Supreme Court decision on gerrymandering.
Read more…

A Prime Breakthrough

June 29, 2019

A breakthrough on the Riemann Hypothesis

[ Composite of various sources ]

Michael Griffin, Ken Ono, Larry Rolen, and Don Zagier (GORZ) have recently published a paper on an old approach to the famous Riemann Hypothesis (RH).

Today we will discuss their work and its connection to P=NP.

Their paper is titled, “Jensen polynomials for the Riemann zeta function and other sequences.” The final version is in the Proceedings of the National Academy of Sciences (PNAS).

The RH is still open. We are not aware of any update on the status of Michael Atiyah’s claim to have solved it since this note on an AMS blog and our own discussion of his papers’ contents.

Recall the RH is a central conjecture in number theory, and it has the following properties:

  • If true, it would greatly enhance our understanding of the structure of the primes: {2,3,5,7,\dots}

  • It has resisted attacks for 160 years and counting.

  • There are an immense number of statements equivalent to the RH.

See, for example, the survey paper, “The Riemann Hypothesis,” by Brian Conrey.

Complexity theory has the P=NP question; number theory has the RH. Both seem to be beyond reach, and both are fundamental questions. The recent work of GORZ has created buzz among number theorists—perhaps they are on the verge of a breakthrough? Is there hope that we might see progress on P=NP? Or must we wait 160 years?

The buzz is reflected in a May 28 story in the online journal LiveScience. It quotes Enrico Bombieri, who wrote the official Clay Prize description of RH, as saying:

“Although this remains far away from proving the Riemann hypothesis, it is a big step forward. There is no doubt that this paper will inspire further fundamental work in other areas of number theory as well as in mathematical physics.”

Bombieri wrote an accompanying paper in PNAS, in which the above quoted sentences also appear. We will try to explain what the excitement is about.

The Approach and Results

RH is equivalent to the hyperbolicity of Jensen polynomials for the Riemann zeta function. Note: A real, polynomial {p(x)} is hyperbolic if all its roots are real—a fancy name for a simple concept.

There is an analytic function {E(z)} so that

\displaystyle  RH \iff E(z) \text{ has all real roots}.

Almost a hundred years ago, Johan Jensen and George Pólya created an approach to the RH based on {E(z)}. Rather than prove {E(z)} has only real roots, they showed it is enough to show that a family of polynomials {J(n, d)(x)} all are hyperbolic. The point is that polynomials are “simpler” than analytic functions—at least that is the hope.

What GORZ prove is this:

Theorem 1 For each {d} and almost all {n}, the polynomial {J(n, d)(x)} is hyperbolic.

Of course, “almost all” means that there at most a finite number of polynomials that are not hyperbolic. They also show that for degree {d} fixed,

\displaystyle  \lim_{n \rightarrow \infty} J(n, d)(x) = H_{d}(x).

Where the polynomials {H_{d}(x)} have only real roots.

This is explained further in a talk by Ono, which has this table showing how the polynomials converge:

Note: they use different notation for the polynomials.

The Approximation Property

There are many equivalent formulations of the RH. While all are equivalent, some are more equivalent than others. Some seem to be a more plausible path toward a resolution of the RH. Of course to date none have worked.

There is a way to distinguish equivalent formulations of the RH. Suppose that S depends on some parameter \beta. Suppose that as \beta increases the statement S(\beta) becomes a weaker version of the RH.
Then let us informally say that the formulation S(\beta) has the “Approximation Property” (AP). The point is that progress in proving caes of S(\beta)—even as partial progress—is exciting. But if the equivalence only holds for \beta=0, with no connections for higher \beta, then the partial progress could be seen as morally useful—but it is not really mathematically useful.

There are equivalences of the RH that have AP and some that seem not to have it. The approximation for the RH is natural. The RH states that there is no zero \sigma + it of the Riemann zeta function with \sigma above 1/2. The weaker statement: If \sigma + it is a zero, then \sigma >  \alpha is unknown for any \alpha in the open interval (1/2,1). This can be used to get a property with the AP.

For example, this 2003 paper by Luis Baez-Duarte, titled “A new necessary and sufficient condition for the Riemann hypothesis,” has the AP. He notes, in our terminology, that his property is an AP.

Open Problems

Does the approach of GORZ have the AP? The issue is that while we get a universal statement in terms of d, the “all but finitely many” condition on n works against its being an approximation—what if the finite sets of exceptions grow in terms of d in ways that offset the purpose behind the equivalence?

Computer Science Gender Gap

June 23, 2019

NY Times article on the paper

LinkedIn source

Lucy Lu Wang is the lead author of a paper released this Friday on gender parity in computer science. The paper is from the Allen Institute for Artificial Intelligence. The authors are Wang, Gabriel Stanovsky, Luca Weihs, and Oren Etzioni. We will call them WSWE for short.

Today we will discuss some of the issues this study raises.

The paper was highlighted by the New York Times in an article titled, “The Gender Gap in Computer Science Research Won’t Close for 100 Years.” The news article begins with an equally sobering statement of this conclusion:

Women will not reach parity with men in writing published computer science research in this century if current trends hold, according to a study released on Friday.

We are for gender-neutral opportunities and have always promoted this—see our earlier discussions here and here. We are for doing a better job in supporting women in computer science. The study by WSWE is an important paper that helps frame the problem. Quoting them:

The field has made more of an effort to reach a more balanced gender status. But the data seems to show that even with all the progress, we are still not making the change fast enough.

I suggest that you might wish to read the paper. Unfortunately there are many papers with similar conclusions—see this by Natalie Schluter, for example.

Main Points

Here are some points of the paper by WSWE:

{\bullet } There is a measurable gap. No one would, I believe, doubt this. But it is important to see that it is measurable.

{\bullet } The gap is shrinking, but slowly. Again this seems correct, but whether it is shrinking in all relevant measures of publication weight is still an issue.

{\bullet } The predictions. Perhaps it will not be closed for over a century.

{\bullet } Modern technology allows such a study. This is one aspect that we can all applaud. WSWE used automated tools that allowed this study to search millions of papers.


WSWE filtered a corpus of 2.87 million papers tagged as in computer science. The volume constrained their approaches to handling several basic issues.

{\bullet} How to tell the gender of an author? They use first names and try to detect gender from that alone. This is not easy. Not only can differently-gendered names in different nations or language groups have the same Romanized form, many names apply to both genders within those groups. The names Taylor and Kelley are perfect examples pf the latter.

WSWE used a statistical weighing method. So “Taylor,” for example, would be weighted as 55 percent female, 45 percent male. The weightings come from a large database called Gender API compiled from government and social agencies not directly related to computer science.

{\bullet} Another issue concerns the prediction part of their paper. They attempt to extrapolate and guess when there will be parity between female and male authorship.

As all predictions this is not easy. It is my main complaint with this and other papers on the gender-gap issue. They predict that parity will not be reached until 2167, in 168 years. An earlier study puts the parity point at 280 years away.

Open Problems

I believe that a major issue is hiring by computer science departments and other institutions. A major CS department just hired {N>1} assistant professors, of which {N} were male. This is a problem.

Should studies on the gender gap count all papers? Perhaps they should weight the papers by some citation indices. Are women writing more impactful papers? What percent of papers by gender have citations rate above X?—you get the idea.

Finally I wonder if parity is the right goal? How about aiming for more women papers than men? Why not?

[various formatting and word edits]

Diophantine Equations

June 19, 2019

Complexity of solving polynomial equations

[ Jeff ]

Jeff Lagarias is a mathematician or a professor at the University of Michigan.

Today I wish to discuss Diophantine equations.

Note, the “or” is a poor joke: For mathematicians {A \text{ or } B} is true also when both {A} and {B} are true.

Jeff has a paper titled Complexity of Diophantine Equations and related talk version. It is a nice review of some of the issues around Diophantine equations.

He has worked on number theory, on complexity theory, and on many other problems. Some are applied and some theoretical. He with Peter Shor solved an open problem years ago that was first stated by Ott-Heinrich Keller in 1930. Our friends at Wikipedia state:

In geometry, Keller’s conjecture is the conjecture that in any tiling of Euclidean space by identical hypercubes there are two cubes that meet face to face.

For dimensions ten or more it is now proved to be false thanks to Jeff and Peter. I am amazed by such geometric results, since I have no geometric intuition. Ten dimensions is way beyond me—although curiously I am okay in {n} dimensions. Strange? Jeff has a relevant quote:

Every dimension is special.

Complexity of Diophantine Equations

Recall the main problem is to find solutions to equations usually restricted to be integers or rationals. This restriction makes the problems hard as in open, and hard as in computationally difficult.


Jeff mentions the following hardness result in his talk: Solving in nonnegative integers for {x,y}

\displaystyle  (x+2)(y+2) = N,

is as hard as integer factoring. This follows since {x+2} and {y+2} must be non-trivial factors of {N}. Note this relies on the fact that {x+2} and {y+2} are both greater than or equal to {2}.

We can delete “nonnegative” in the above by the following simple idea. Suppose that {N} has two factors that are both congruent to {3} modulo {8}. If not, then we can still factor, but I believe the idea is clearer without adding extra complications. Then solve in integers

\displaystyle  (8x + 3)(8y+3) = N.

By assumption on {N} there is a solution of this equation. Moreover suppose that {x,y} are some solution. The key is that {8x + 3} cannot be {\pm 1} and {8y+3} also cannot be {\pm 1}. Then it follows that each is also not equal to {N} in absolute value. Thus

\displaystyle  1 < |8x+3| < N,

and we have factored {N}.


Jeff points out that it is unlikely that Diophantine problems are going to be classified by the NP-hard machinery. He says

{\dots} shows the (possible) mismatch of “natural” Diophantine problems with the P versus NP question.

Factoring is one of those in between problems that could be in P, but most believe that it could not be NP-hard.

Rational Case

The problem of deciding whether a polynomial has a rational root is still open. That is given a polynomial with integer coefficients, does the equation

\displaystyle  F(x,y,z,\dots)= 0,

have a rational solution {x,y,z,\dots}? Of course the famous Hilbert’s Tenth problem asks for integer solutions of polynomials and is undecidable. The rational case is open. We have discussed it before here. See this for a survey.

I had tried to see if we could at least prove the following: The decision problem over the rationals is at NP-hard. I thought for a while that I could show that solving equations over the rationals is at least NP-hard. My idea was to try to replace (x+2)(y+2) by a equation that works over the rationals. The attempt failed. I was also unable to find a reference for such a result either. So perhaps it is open.

Open Problems

Is it undecidable to determine whether a polynomial has a root over the rationals? Can we at least get that it is factoring hard?

Contraction and Explosion

June 17, 2019

Different ways of recursing on graphs

Bletchley Park 2017 source

William Tutte was a British combinatorialist and codebreaker. He worked in a different group at Bletchley Park from that of Alan Turing. He supplied several key insights and algorithms for breaking the Lorenz cipher machine. His algorithms were implemented alongside Turing’s on Colossus code-breaking computers.

Today we discuss graph recursions discovered by Tutte and Hassler Whitney.

Tutte wrote a doctoral thesis after the war on graph theory and its generalization into matroid theory. We will follow the same arc in this and a followup post. He joined the faculty of the universities of Toronto and then Waterloo, where he was active long beyond his retirement.

For more on Tutte and his work, see this article and lecture by Graham Farr, who is a professor at Monash University and a longtime friend of Ken’s from their Oxford days. We covered some of Tutte’s other work here.

Deletion and Contraction

The two most basic recursion operations are deleting and contracting a chosen edge {e} in a given graph {G = (V,E)}:


These operations produce graphs denoted by {G \setminus e} and {G/e}, respectively. A motive for them harks back to Gustav Kirchhoff’s counting of spanning trees:

  • A spanning tree of {G} avoids using edge {e} if and only if it is a spanning tree of the graph {G \setminus e} with {e} deleted.

  • A spanning tree of {G} uses edge {e} if and only if the rest of it is a spanning tree of the graph {G/e} after contracting {e}.

Well, this is not how Kirchhoff counted trees. Counting via the recursion would take exponential time. Our whole object will be telling which cases of the recursions can be computed more directly.

Note that contracting one edge of the triangle graph {C_3} produces a multi-graph {C_2} with one double-edge. Then contracting one edge of {C_2} yields the loop graph {C_1}.


Thus contraction yields non-simple undirected graphs, but the logic of counting their spanning trees remains valid.

The order of edges does not matter as long as one avoids disconnecting the graph, and the base case is a tree (ignoring any loops) which contributes {1}.

Tutte’s Polynomial

A similar recursion counts colorings {c: V \rightarrow \{1,...,k\}} that are proper, meaning that for each edge {e = (u,v)}, {c(u) \neq c(v)}.

  • A proper coloring {c} of {G \setminus e} makes {c(u) \neq c(v)} iff it is a proper coloring of {G}.

  • A proper coloring {c} of {G \setminus e} makes {c(u) = c(v)} iff it induces a proper coloring of {G/e}.

This leads to the recursive definition of the chromatic polynomial:

\displaystyle    P_G(x) = P_{G\setminus e}(x) - P_{G/e}(x).

The base cases are that an isolated vertex contributes {x}, whereas an isolated loop contributes {0} since its single edge is never properly colored. The final rule is that {P_G(x)} is always the product of {P_H(x)} over all connected components {H} of {G}. Then {P_G(k)} counts the number of proper {k}-colorings.

This is like the recursion for coutning spanning terees except for the minus sign. Tutte’s brilliant insight, which was anticipated by Whitney in less symbolic form, was that the features can be combined by using two variables {x} and {y}. Call an edge a bridge if it is not part of any cycle. If {e} is not a bridge, the recursion is

\displaystyle    T_G(x,y) = T_{G \setminus e}(x,y) + T_{G/e}(x,y).

The base case is now a graph {G} with some number {k} of bridges and some number {\ell} of loops, which gives {T_G(x,y) = x^k y^\ell}. An important feature is that all {n}-vertex trees have the same Tutte polynomial {x^{n-1}}, since there are {n-1} edges and they are all bridges. The following are just some of the beautiful rules that {T_G} follows. Let {c = c_G} stand for the number of connected components of {G}.

  • {T_G(1,1)} counts the number of spanning trees forests. This counts the number of spanning trees if {G} is connected.

  • {T_G(1-x,0)}, when multiplied by {(-1)^{n-c} x^c}, yields the chromatic polynomial.

  • {T_G(1,2)} counts the number of spanning subgraphs.

  • {T_G(2,2)} is just {2^{|E|}}.

  • {T_G(x,\frac{1}{x})} gives the Jones polynomial of a knot related to {G}.

There are many further relations. The Jones polynomial has many applications including in quantum physics.

Contraction With a Twist

Recall our definition of the “amplitude” {a(G)} of an undirected {n}-vertex graph {G} from the “Net-Zero Graphs” post:

\displaystyle    a(G) = \frac{c_0 - c_1}{2^n},

where {c_0} is the number of black-and-white 2-colorings that make an even number of edges have both nodes colored black, and {c_1} for an odd number.

There does not seem to be a simple recursion for {a(G)} from {G \setminus e} and {G/e}. We can, however, obtain one by using another kind of contraction that adds a loop at the combined vertex:


We denote this by {G/\!/e}. We have not found a simple reference for this. We obtain the following recursive formula:

\displaystyle    a(G) = a(G\backslash e) + \frac{1}{2}a(G/\!/e) - \frac{1}{2}a(G/e).

This recursion allows {e} to be a bridge, so the base cases are {1} for an isolated vertex and {0} for a loop. More generally, the basis is {1} for a node with an even number of loops, {0} for odd. Here is an example for the ‘star graph’ {S_4} on 4 vertices:


The diagram would need another layer to get down to (products of) base cases, which we have shortcut by putting values of {a(H)} for each graph {H} at a leaf. Adding the products over all branches gives {a(G)}. For the star graph,

\displaystyle    a(S_4) = \frac{1}{2} + \frac{1}{4} - \frac{1}{4} + \frac{1}{4} + \frac{1}{8} - \frac{1}{8} - \frac{1}{4} - \frac{1}{8} + \frac{1}{8} = \frac{1}{2}.

Clearly this brute-force recursion grows as {3^n}. This is slower than the order-{2^n} time of using the coloring definition directly, but what all this underscores is how singular it is to be able to compute {a(G)} in polynomial time, indeed {O(n^\omega)} time. The search for a more-efficient recursion, one that might apply to {\mathsf{NP}}-hard quantities, leads us to consider a more-drastic operation on edges.

Exploding Edges

The new recursion operation is well illustrated by this figure:


Two vertices disappear, not just one. Not only does the edge {e = (u,v)} disappear, but any other edge incident to {u} or {v} from a vertex {w \neq u,v} gets “recoiled” into a loop at {w}. We denote this operation by {G \backslash\!\backslash e} to connote that {e} is not just deleted but “exploded.”

Properly speaking, we need to specify what happens if there are other edges between {u} and {v} or loops at {u} or {v}. In an upcoming post we will see that those become circles in a graphical polymatroid which generalizes the notion of a graph. For now, however, it suffices to let {r} be the total number of vaporized edges, including {e}. Then we obtain a two-term recursive formula:

\displaystyle    a(G) = a(G \backslash e) + \frac{(-1)^r}{2} a(G\backslash \!\backslash e).   \ \ \ \ \ (1)

The base cases for isolated vertices are the same as before, but explosion also needs a base case for pure emptiness. This contributes {1}. In the following example diagram, for the path graph {P_4} on four nodes, we denote such base cases by `w’ for “wisp”:


Note again the rule that when the recursion disconnects the graph, the component values multiply together. Thus the value is

\displaystyle    a(P_4) = (1 - \frac{1}{2})(1 - \frac{1}{2}) - 0 = \frac{1}{4}.

This is different from the amplitude {\frac{1}{2}} of the star graph. What this means is that {a(G)} does not obey the rules of the Tutte polynomial, which is the same for both of these 4-vertex trees.

To prove the recursion equation (1), for {e = (u,v)}, note that every coloring has the same odd/even parity of black-black edges for {G\setminus e} as for {G} except those that color both {u} and {v} black. Let {c_0^{uv}} denote the colorings among the latter that make an even number of black-black edges (including {e}) overall, {c_1^{uv}} for an odd number. Then

\displaystyle    a(G) = a(G \setminus e) + \frac{2}{2^n}(c_1^{uv} - c_0^{uv}).

Now if there are no other edges between or loops at {u} and {v}, then {c_1^{uv}} is the same as the number of colorings of {G \backslash\!\backslash e} that make an even number of black-black edges, and {c_0^{uv}} becomes the odd case in {G \backslash\!\backslash e} again because we subtracted {e}. Considering the sign change from other {(u,v)} edges or loops and {\frac{2}{2^n} = \frac{1/2}{2^{n-2}}} yields equation (1). It is also possible to “explode” a loop, and our readers may enjoy figuring out how to define it.

The Amplitude Polynomial

We can expand on this by defining a polynomial {Q_G(x)} such that {a(G) = Q_G(1)}. The base cases are {x} for an isolated vertex but still {1} for a “wisp” and {0} for a loop. The basis extends to give {x} for an isolated node with an even number of loops and {0} for odd. Another way to put it is that two edges with the same endpoints, or two loops at the same node, can be removed. The above diagram shows that for the path graph {P_4},

\displaystyle    Q_{P_4}(x) = (x^2 - \frac{1}{2})^2 = x^4 - x^2 + \frac{1}{4}.

Whereas, the recursion for the star graph—noting that the “star” {S_2} on two nodes is just a single edge—gives:

\displaystyle  \begin{array}{rcl}    Q_{S_4}(x) &=& xQ_{S_3}(x) - \frac{1}{2}0\\   &=& x^2 Q_{S_2}(x) - \frac{1}{2}0 - \frac{1}{2}0\\   &=& x^4 - x^2 \frac{1}{2}(1\!\cdot\! 1) - \frac{1}{2}0 - \frac{1}{2}0 = x^4 - \frac{1}{2}x^2.   \end{array}

This is not the same polynomial as {Q_{P_4}(x)}, again implying that {Q_G(x)} is not a specialization of the Tutte polynomial. We will show in the last post in this series that {Q_G(x)} does specialize the polynomial {S_G(x,y)} introduced in this 1993 paper titled, “A Characterization of Tutte Invariants of 2-Polymatroids” and covered further in this 2006 paper.

Open Problems

What other rules does our “amplitude polynomial” follow? We will explore this in the mentioned upcoming post. What other quantities can it be made to count?

What we called “explosion” is in fact attested as the natural form of contraction for the polymatroids considered in these papers. What further uses might “explosion” have in graph theory apart from polymatroids?

How To Make A Polynomial Map Nicer

June 12, 2019

Stability theory and polynomials

[ Essen ]

Arno van den Essen is the author of the book on the Jacobian Conjecture.

Today I want to highlight one of the ideas he presents in his book.
Read more…