Bill and Clyde’s new book

Bill Gasarch and Clyde Kruskal are colleagues in Computer Science at the University of Maryland. They have just seen the publication of their book Problems With a Point.

Today Dick and I congratulate them on the book and give a brief overview of it.

The tandem of Bill and Clyde were featured before on this blog in connection with a series of papers with James Glenn on sets of numbers that have no arithmetical progressions of length 3.

Can a “series” have only two members? We could add a third paper to the series, but it is by Glenn and Bill with Richard Beigel rather than Clyde and is on the different topic of multi-party communication complexity. But Clyde gets into the act since it is the topic of Chapter 19 of the book. That chapter analyzes a game form of problems that go back to a 1983 paper by Dick with Ashok Chandra and Merrick Furst. Does this mean Dick should get some royalties? Note that this last link is to Bill’s website. And ‘vdw’ in this link seems to refer to van der Waerden’s theorem, which is a pillar of both Ramsey theory and number theory, which in turn receive much attention in the book.

My last paragraph flits through divergent questions but they are representative of things that we working mathematical computing theorists think about every day—and of various kinds of content in the book. Of course, Bill partners on Lance Fortnow’s prominent blog and so has shared all kinds of these musings. The book, which incorporates numerous posts by Bill but is not a “blog book” per-se, furnishes contexts for them. Let’s look at the book.

## The Book

The book has three main parts, titled:

• Stories With a Point.

• Problems With a Point.

• Theorems With a Point.

All the chapters except three are prefaced with a section titled “Point”—or “The Point” or “Points”—after one sentence on prior knowledge needed, which often reads, “None.”

The first part begins with a chapter titled, “When Terms From Math are Used By Civilians,” one of several with social discussion. The second is about how human aspects of sports upset statistical regularities one might expect to see. For example, many more baseball hitters have had season batting averages of .300 than .299 or .301, evidently because .300 is a “goal number” everyone strives to meet. There are numerous things in the book I didn’t know.

The next chapter largely reproduces this record-long post on the blog but adds much extra commentary. Then there are chapters on what makes a mathematical function worth defining, on how mathematical objects are named, on Bill’s visit to a “Gathering for [Martin] Gardner” conference, on coloring the plane, two on imagined applications of Ramsey Theory to medieval history, and one on the methodological and social impact of having theorems that represent barriers to ways of trying to prove other theorems.

## Chapter Ten

This last chapter of Part I draws on several of Bill’s posts. It goes most to the heart of what we all in computational complexity grapple with daily and benefits from having more context: As we just mused in this blog’s 10-year anniversary post, the major questions in complexity are not only as open as when we started, but as open as when the field started 50-plus years ago. There has barely been any discernible direct progress, and this is not only a concern for entering students but a retardant on everyone—about which we’ve given exhortation.

There are instead barrier theorems saying why the main questions will not be resolvable by the very techniques that were used to build the field. Of three broad categories of barriers, “oracle results” de-fang all the methods typically taught in intro graduate complexity courses. Those methods meter computations at inputs and outputs but not how they “progress” inside toward a solution. Oracle languages supply blasts of external information that either make progress trivially quick or allow conditioning the terms of the complexity-class relation under analysis to information in the oracle that is tailored to obfuscate. Oracles of the former kind usually collapse complexity classes together, such as ${A =}$ any polynomial-space complete language making ${\mathsf{P}^A = \mathsf{NP}^A}$, whereas oracles ${B}$ of the latter kind drive them apart (so ${\mathsf{P}^B \neq \mathsf{NP}^B}$) but often for reasons that frustrate as much as enlighten. When contemplating a new complexity class relation it is incumbent to frame a “relativized” version of it and see if some oracles can make it true and others false. Such oracle constructions were initially easy to come by—“fast food” for research—but their ultimate besideness-of-the-point is reflected in this early post by Dick.

Next after oracles is the “Natural Proofs” barrier, which basically cuts against all the techniques taught in advanced graduate complexity courses unless they can somehow be weirdly narrow or intensely complex in their conceptual framing. The attitude on those is captured by the title of another early post by Dick titled, “Who’s Afraid of Natural Proofs?” The third barrier is algebrization, which cuts against efforts to escape from oracles.

Amid all this environment of obstruction, what of consequence can we prove? Well, the chapter on this has by far the highest concentration of Bill’s trademark all-capital letters and exclamation points. The initial “Point” section is titled, “Rant.” (The chapter also includes a page on the attempts to prove Euclid’s parallel postulate, which might be called the original “problem with a point.”)

## Part II

Much of Part II involves the kind of problems that were used or considered for high-school mathematics competitions. By definition those are not research problems but they often point toward frontiers by representing accessible cases of them. The appealing ones blend equal parts research relevance, amusement value, and reward of technical command. Often they require mathematical “street smarts” and a repertoire of useful tricks and proof patterns. Practicing researchers will find this aspect of the book most valuable. The problems are mainly on the number-theory side of recreational mathematics, plus geometric and coloring problems. Egyptian fractions, prime-factor puzzles, sums over digits, summation formulas, and of course Ramsey theory all make their appearance. Here is one problem I mention partly to correct a small content error, where the correction seems to make the problem more interesting. Say that ${C(n,m)}$ holds if there are integers ${n_1,\dots,n_m}$ such that

$\displaystyle n_1 + \cdots + n_m = n \qquad\text{and}\qquad \frac{1}{n_1} + \cdots + \frac{1}{n_m} = 1.$

A general principle discovered by Joseph Sylvester gives cases such as ${C(1861,5)}$ being witnessed by

$\displaystyle 1861 = 2 + 3 + 7 + 43 + 1806 \qquad\text{and}\qquad 1 = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1806}.$

How can it and related ideas be extended to other cases? The particular problem is given ${n}$ to find ${m_n =}$ the least ${m}$ such that ${C(n,m)}$ holds—and to find a witnessing sum. The error is an assertion that ${m_n \leq n}$ “by writing ${n}$ as a sum of ${n}$ ${1}$‘s,” but then the reciprocals add up to ${n}$ not ${1}$. So is there any bound on ${m_n}$? That is rather fun to think about.

This problem’s chapter is made from a short post with an enormous comments section. There is also a chapter on the boundary between a fair problem and a “trick question” that much extends an April Fool’s post on the blog.

## Part III

Part III continues the nature of the problem content with emphasis on the worths of proofs of theorems. One illustration involving perfect numbers and sums of cubes notes that the proof loses value because it also applies to certain non-perfect numbers. Two things en-passant: First, Lemma 21.1 in this chapter needs qualification that ${a,b}$ are relatively prime and ${x+1}$ is prime. Second, this prompts me to note via Gil Kalai the discovery by Tim Browning that the number 33 is a sum of three cubes:

$\displaystyle 33 = 8,\!866,\!128,\!975,\!287,\!528^3 + (-8,\!778,\!405,\!442,\!862,\!239)^3 + (-2,\!736,\!111,\!468,\!807,\!040)^3.$

Gil points to a Quora post by Alon Amit. There is only the bare equation on Browning’s homepage, and nothing about his methods or how much he used computer search is known. The theme of proofs by computer runs through several chapters of Bill and Clyde’s book. It is also current on Scott Aaronson’s blog—we would be remiss if we did not mention Scott in this post—and more widely.

The penultimate chapter covers the beautiful theory of rectangle-free colorings of grids. We mentioned Bill’s involvement with this Ramsey-style problem in a post on what happened to be this blog’s third anniversary. We connected it to Kolmogorov complexity, which together with uncomputability is the subject of the last chapter. This and other chapters I’ve mentioned exemplify how the research ambit connects traditional mathematics with the terms and concerns of computing theory. How to work in this ambit may be the greatest value of the book for students. In all I found the book light, lighthearted, and enlightening.

## Open Problems

The big open problem with the book is how it might help gear us up to tackle the big open problems.

[sourced chapter near end of Part II to blog]

1. March 10, 2019 11:13 pm

New version update(March 11. 2019)

P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.

https://zenodo.org/record/2589813

2. March 11, 2019 3:20 pm

Without any restrictions on $n$, there’s not even any guarantee that $m_n$ need exist. For instance, take n=2; then one can either write 2=1+1, which doesn’t work (as 1/1+1/1=2), or as 2=2, which doesn’t work either (as 1/2=1/2). So you can’t really ask about a bound!

3. March 13, 2019 5:20 pm

Hi fellows,

Would you like to endorse the following paper in Arxiv?

https://zenodo.org/record/2589813 (See the abstract in the comment above)

It’s about a proof of P vs NP. If you will, then feel free to contact me in the following email

vega.frank@gmail.com