Summer Reading in Theory

Some formative books in mathematics and computing theory

LSE source: “Calculus on Clay?”

Norman Biggs is the author of the wonderful book Algebraic Graph Theory. Both Ken and I read it long ago, and both of us have it out now because of its relevance to Hao Huang’s beautiful short proof of the Boolean Sensitivity Conjecture.

Today we wish to ask, What are your top five favorite books on mathematics and theory for summer reading?

There’s an aporia in that question. A working definition of aporia is: “a self-contradiction that isn’t.” The point is that books for summer reading should be new, so how would you already know which are your favorites? Well, we are thinking of books that are so rich you can always find new things in them—and that also played formative roles earlier in our careers.

Ken knew Biggs during his first year at Oxford when Biggs was visiting there from London. He took part in a weekly sitting-room seminar organized by Peter Neumann. Biggs’s book was a central reference for Ken’s undergraduate senior thesis at Princeton, and both he and Ken presented material based on it.

Best Five Books—Dick

Here are my votes for all-time best books in mathematics and in computer science theory.

Algebraic Graph Theory, by Norman Biggs. A wonderful book. First appeared in 1974.

An Introduction to Probability Theory and Its Applications, Vol. 1, by William Feller. This is the book I used to learn probability theory.

An Introduction to the Theory of Numbers, by Godfrey Hardy and Edward Wright. Now updated by Andrew Wiles, Roger Heath-Brown, and Joseph Silverman.

Elements of Number Theory, by Ivan Vinogradov. Another small book that is loaded with ideas.

The Art of Counting, by Paul Erdős and Joel Spencer. This book changed my life. Today the book is of course The Probabilistic Method, by Noga Alon and Joel Spencer.

Best Five Books—Ken

Ken reaches back to his teen years but it’s still the same span of years as my list. Here he tells it:

All books by Martin Gardner—in particular, the books of collections of his “Mathematical Games” columns in Scientific American. Here is an overview.

Scarne on Dice and Scarne on Cards. Originally it was neither of these books—nor John Scarne’s Complete Guide to Gambling—but a different book on in which both Scarne and Gardner figured prominently. Alas I, Ken, cannot trace it. That’s what I used to learn probability theory.

Spectra of Graphs, by Dragoš Cvetković, Michael Doob, and Horst Sachs. I could put Biggs’s book here, but this is the one that got me on to the whole subject just before my senior year at Princeton. It was fresh out in 1980—I recall the tactile sensation of the dark green spanking new cover in the Fine Hall Library’s copy. A great book with pictures and algebra.

Ideals, Varieties, and Algorithms, by David Cox, John Little, and Donal O’Shea. Fast forward to 1997. Having realized that techniques from algebraic geometry could surmount the “Natural Proofs” barrier (see also GCT), I went whole-hog after it. See “Manic Monomials” in this post for one thing that tripped it up. The book remains incredibly stimulating. It has a sequel, Using Algebraic Geometry.

Quantum Computation and Quantum Information by Michael Nielsen and Isaac Chuang. As with Hardy and Wright, it has its own Wikipedia page. Dick and I can say this is nominating a competitor, but Chaung & Nielsen is really in a class by itself for the sheer richness and writing style. One odd mark of its influence: In 2006 when I reacted to the sensational and frightening accusations of cheating at the world championship match, my first thought was to apply distributional distance measures of the kind used in its later chapters. Among such measures is (quantum) fidelity, and although I focused more on Jensen-Shannon divergence before deciding on simpler stuff, my chess research website retains “fidelity” in its name as part of a multi-way reference to FIDE, faith, and playing in good faith.

Open Problems

What books most influenced you? What are your votes for the best books that might influence others?

Advertisements

Tools and Sensitivity

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.

Mathematics of Gerrymandering

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.

A Prime Breakthrough

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:

• 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 is hyperbolic if all its roots are real—a fancy name for a simple concept.

There is an analytic function so that

Almost a hundred years ago, Johan Jensen and George Pólya created an approach to the RH based on . Rather than prove has only real roots, they showed it is enough to show that a family of polynomials 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 and almost all , the polynomial 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 fixed,

Where the polynomials 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 depends on some parameter . Suppose that as increases the statement becomes a weaker version of the RH.
Then let us informally say that the formulation has the “Approximation Property” (AP). The point is that progress in proving caes of —even as partial progress—is exciting. But if the equivalence only holds for , with no connections for higher , 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 of the Riemann zeta function with above . The weaker statement: If is a zero, then is unknown for any in the open interval . 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 , the “all but finitely many” condition on works against its being an approximation—what if the finite sets of exceptions grow in terms of in ways that offset the purpose behind the equivalence?

Computer Science Gender Gap

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:

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

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.

The predictions. Perhaps it will not be closed for over a century.

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.

Issues

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

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.

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 assistant professors, of which 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

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 is true also when both and 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 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.

Factoring-Hard

Jeff mentions the following hardness result in his talk: Solving in nonnegative integers for

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

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

By assumption on there is a solution of this equation. Moreover suppose that are some solution. The key is that cannot be and also cannot be . Then it follows that each is also not equal to in absolute value. Thus

and we have factored .

NP-hard

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

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

have a rational solution ? 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 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

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 in a given graph :

These operations produce graphs denoted by and , respectively. A motive for them harks back to Gustav Kirchhoff’s counting of spanning trees:

• A spanning tree of avoids using edge if and only if it is a spanning tree of the graph with deleted.

• A spanning tree of uses edge if and only if the rest of it is a spanning tree of the graph after contracting .

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 produces a multi-graph with one double-edge. Then contracting one edge of yields the loop graph .

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 .

Tutte’s Polynomial

A similar recursion counts colorings that are proper, meaning that for each edge , .

• A proper coloring of makes iff it is a proper coloring of .

• A proper coloring of makes iff it induces a proper coloring of .

This leads to the recursive definition of the chromatic polynomial:

The base cases are that an isolated vertex contributes , whereas an isolated loop contributes since its single edge is never properly colored. The final rule is that is always the product of over all connected components of . Then counts the number of proper -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 and . Call an edge a bridge if it is not part of any cycle. If is not a bridge, the recursion is

The base case is now a graph with some number of bridges and some number of loops, which gives . An important feature is that all -vertex trees have the same Tutte polynomial , since there are edges and they are all bridges. The following are just some of the beautiful rules that follows. Let stand for the number of connected components of .

• counts the number of spanning trees forests. This counts the number of spanning trees if is connected.

• , when multiplied by , yields the chromatic polynomial.

• counts the number of spanning subgraphs.

• is just .

• gives the Jones polynomial of a knot related to .

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” of an undirected -vertex graph from the “Net-Zero Graphs” post:

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

There does not seem to be a simple recursion for from and . We can, however, obtain one by using another kind of contraction that adds a loop at the combined vertex:

We denote this by . We have not found a simple reference for this. We obtain the following recursive formula:

This recursion allows to be a bridge, so the base cases are for an isolated vertex and for a loop. More generally, the basis is for a node with an even number of loops, for odd. Here is an example for the ‘star graph’ 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 for each graph at a leaf. Adding the products over all branches gives . For the star graph,

Clearly this brute-force recursion grows as . This is slower than the order- time of using the coloring definition directly, but what all this underscores is how singular it is to be able to compute in polynomial time, indeed time. The search for a more-efficient recursion, one that might apply to -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 disappear, but any other edge incident to or from a vertex gets “recoiled” into a loop at . We denote this operation by to connote that is not just deleted but “exploded.”

Properly speaking, we need to specify what happens if there are other edges between and or loops at or . 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 be the total number of vaporized edges, including . Then we obtain a two-term recursive formula:

The base cases for isolated vertices are the same as before, but explosion also needs a base case for pure emptiness. This contributes . In the following example diagram, for the path graph 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

This is different from the amplitude of the star graph. What this means is that 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 , note that every coloring has the same odd/even parity of black-black edges for as for except those that color both and black. Let denote the colorings among the latter that make an even number of black-black edges (including ) overall, for an odd number. Then

Now if there are no other edges between or loops at and , then is the same as the number of colorings of that make an even number of black-black edges, and becomes the odd case in again because we subtracted . Considering the sign change from other edges or loops and 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 such that . The base cases are for an isolated vertex but still for a “wisp” and for a loop. The basis extends to give for an isolated node with an even number of loops and 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 ,

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

This is not the same polynomial as , again implying that is not a specialization of the Tutte polynomial. We will show in the last post in this series that does specialize the polynomial 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?