Skip to content

Cleverer Automata Exist

August 3, 2020


A breakthrough on the separating words problem

Zachary Chase is a graduate student of Ben Green at Oxford. Chase has already solved a number of interesting problems–check his site for more details. His advisor is famous for his brilliant work—especially in additive combinatorics. One example is his joint work with Terence Tao proving this amazing statement:

Theorem 1 The prime numbers contain arbitrarily long arithmetic progressions.

Today we wish to report Chase’s new paper on a problem we have twice discussed before.
Read more…

A Brilliant Book on Combinatorics

July 27, 2020


And Razborov’s brilliant proof method

Stasys Jukna is the author of the book Extremal Combinatorics With Applications in Computer Science.

Today we talk about Jukna’s book on extremal combinatorics.

Read more…

Mathematical Search

July 18, 2020


A flying start from nearby Rochester

Anurag Agarwal and Richard Zanibbi are tenured faculty in Mathematics and Computer Science, respectively, at RIT. They partner with Clyde Lee Giles of Penn State and Douglas Oard of U.Md. on the MathSeer project. If the name reminds you of CiteSeer{{\,}^x}, no surprise: Giles co-originated that and still directs it.

Today we note last month’s release of a major piece of MathSeer called MathDeck and show how to have fun with it.

Read more…

Ron Graham, 1935–2020

July 10, 2020


Ron Graham passed away, but he lives on…

Cropped from tribute by Tom Leighton

Ron Graham just passed away Monday at the age of {84} in La Jolla near UCSD.

Today Ken and I wish to say a few words about Ron.

Read more…

Intellectual Fireworks?

July 4, 2020


Some different ideas for marking the Fourth

“Founding Frenemies” source

John Adams and Thomas Jefferson did not use Zoom. Their correspondence, from 1777 up to their deaths hours apart on July 4, 1826, fills a 600-page book.

Today, Independence Day in the US, we consider the kind of intellectual fireworks represented by the correspondence.

Read more…

Taking a Problem Down a Peg

June 29, 2020


By blowing up its objects

Composite crop of src1, src2

Joshua Greene and Andrew Lobb proved last month that every smooth Jordan curve in the plane and real {r \leq 1}, there are four points on the curve that form a rectangle with sides of ratio {r}.

Today we explain how this result relates to Otto Toeplitz’s famous “square peg conjecture,” which is the case {r = 1} when the curve need not be smooth.

Read more…

Some Real and Some Virtual News

June 21, 2020


Gossip and more.

Composite of , src1, src3

Jessica Deters, Izabel Aguiar, and Jacqueline Feuerborn are the authors of the paper, “The Mathematics of Gossip.” They use infection models—specifically the Susceptible-Infected-Recovered (SIR) model—to discuss gossip. Their work was done before the present pandemic, in 2017–2019. It is also described in a nice profile of Aguiar. Their analogy is expressed by a drawing in their paper:

Not just for today, but for the summer at least, Ken and I want to share some gossip, share some problems, and ask our readers a question.

Read more…

P<NP

June 16, 2020


Some thoughts on P versus NP

Norbert Blum is a computer science theorist at the University of Bonn, Germany. He has made important contributions to theory over his career. Another claim to fame is he was a student of Kurt Mehlhorn, indeed the third of Mehlhorn’s eighty-eight listed students.

Today I wish to discuss a new paper by Blum.

Read more…

Proof Checking: Not Line by Line

June 13, 2020


Proofs and perpetual motion machines

Leonardo da Vinci is, of course, famous for his paintings and drawings, but was also interested in inventions, and in various parts of science including mathematics and engineering. It is hard to imagine that he died over 500 years ago, given his continued impact on our world. He invented practical and impractical inventions: musical instruments, a mechanical knight, hydraulic pumps, reversible crank mechanisms, finned mortar shells, and a steam cannon.

Today I wish to discuss proofs and perpetual motion machines.

You might ask: What do proofs and perpetual motion machines have in common? Proofs refer to math proofs that claim to solve open problems like P {\neq} NP. Ken and I get such claims all time. I take a look at them, not because I think they are likely to be correct. Rather because I am interested in understanding how people think.

I started to work on discussing such proofs when I realized that such “proofs” are related to claims about perpetual motion machines. Let’s see how.

Perpetual Motion Machines

A perpetual motion machine is a machine that operates indefinitely without an energy source. This kind of machine is impossible, as da Vinci knew already:

Oh ye seekers after perpetual motion, how many vain chimeras have you pursued? Go and take your place with the alchemists.
—da Vinci, 1494

I like this statement about applying for US patents on such machines:

Proposals for such inoperable machines have become so common that the United States Patent and Trademark Office (USPTO) has made an official policy of refusing to grant patents for perpetual motion machines without a working model.

Here is a classic attempt at perpetual motion: The motion goes on “forever” since the right side floats up and the left side falls down.

The analogy of proofs and to perpetual motion machines is: The debunking such a machine is not done by looking carefully at each gear and lever to see why the machine fails to work. Rather is done like this:

Your machine violates the fundamental laws of thermodynamics and is thus impossible.

Candidate machines are not studied to find the exact flaw in their design. The force of fundamental laws allows a sweeping, simple, and powerful argument against them. There are similar ideas in checking a proof. Let’s take a look at them.

Proofs

Claims are made about proofs of open problems all the time. Often these are made for solutions to famous open problems, like P{\neq}NP or the Riemann Hypothesis (RH).

Math proofs are used to try to get to the truth. As we said before proofs are only as good as the assumptions made and the rules invoked. The beauty of the proof concept is that arguments can be checked, even long and complex ones. If the assumptions and the rules are correct, then no matter how strange the conclusion is, it must be true.

For example:

{\bullet } The Riemann rearrangement theorem. A sum

\displaystyle  a_{1} + a_{2} + a_{3} + \dots

that is conditionally convergent can be reordered to yield any number. Thus there is series

\displaystyle  b_{1} + b_{2} + b_{3} + \dots

that sums conditionally to your favorite number {M} and yet the {b_{1},b_{2},\dots} is just a arrangement of the {a_{1},a_{2},\dots}. This says that addition is not commutative for infinite series.

{\bullet } Cover the largest triangle by two unit squares: what is the best? The following shows that it is unexpected:


The point of a proof is that it is a series of small steps. If each step is correct, then the whole is correct. But in practice proofs are often checked in other ways.

Checking Proofs

The starting point for my thoughts—joined here with Ken’s—are these two issues:

  1. A proof that only has many small steps but no global picture is hard to motivate.

  2. A proof with complex logic at the high level is hard to understand.

Note that a deep, hard theorem can still have straightforward logic. A famous theorem of Littlewood has for its proof the structure:

  • Case the RH is false: Then {\dots}

  • Case the RH is true: Then {\dots}

The RH-false case takes under a page. The benefit with this logic is that one gets to assume RH for the rest. The strategy for the famous proof by Andrew Wiles of Fermat’s Last Theorem (FLT)—incorporating the all-important fix by Richard Taylor—has this structure:

  • If {X} then {Y}.

  • If not-{X} then {Z}.

  • {Y} implies FLT.

  • {Z} implies FLT.

Wiles had done the last step long before but had put aside since he didn’t know how to get {Z}. The key was framing {X} so that it enabled bridged the gap in his originally-announced proof while its negation enabled the older proof.

Thus what we should seek are proofs with simple logic at the high level that breaks into cases or into sequential sub-goals so that the proof is a chain or relatively few of those goals.

Shapes and Barriers

This makes Ken and I think again about an old paper by Juris Hartmanis with his students Richard Chang, Desh Ranjan, and Pankaj Rohatgi in the May 1990 Bulletin of the EATCS titled, “On IP=PSPACE and Theorems With Narrow Proofs.” Ken’s post on it included this nice diagram of what the paper calls “shapes of proofs”:


Ken’s thought now is that this taxonomy needs to be augmented with a proof shape corresponding to certain classes believed to be properly below polynomial time—classes within the NC hierarchy. Those proofs branch at the top into manageable-size subcases, and/or have a limited number of sequential stages, where each stage may be wide but is shallow in its chains of dependencies. Call this shape a “macro-tree.”

The difference between the macro-tree shape and the sequential shapes pictured above is neatly captured by Ashley Ahlin on a page about “Reading Theorems”:

Note that, in some ways, the easiest way to read a proof is to check that each step follows from the previous ones. This is a bit like following a game of chess by checking to see that each move was legal, or like running a spell-checker on an essay. It’s important, and necessary, but it’s not really the point. … The problem with this is that you are unlikely to remember anything about how to prove the theorem, if you’ve only read in this manner. Once you’re read a theorem and its proof, you can go back and ask some questions to help synthesize your understanding.

The other high-level structure that a proof needs to make evident—before seeing it is reasonable to expend the effort to check it—is shaped by barriers. We have touched on this topic several times but maybe have not stated it full on for P versus NP. A recent essay for a course led by Li-Yang Tan at Stanford does so in just a few pages. A proof should state up front how it works around barriers, and this alone makes its strategy easier to follow.

The idea of barriers extends outside P versus NP, of course. Peter Scholze seems to be invoking it in a comment two months ago in a post by Peter Woit in April on the status of Shinichi Mochizuki’s claimed proof of the ABC conjecture:

I may have not expressed this clearly enough in my manuscript with Stix, but there is just no way that anything like what Mochizuki does can work. … The reason it cannot work is a[nother] theorem of Mochizuki himself. … If the above claims [which are negated by the theorem] would have been true, I would see how Mochizuki’s strategy might have a nonzero chance of succeeding. …

Thus what Ken and I conclude is that in order for a proof to be checkable chunk by chunk—not line by line—it needs to have:

  1. A top-level decomposition into a relatively small number of components and stages—like legs in a sailing race—and

  2. A demonstration of how the stages navigate around known barriers.

Lack of a clear plan in the first already says the proof attempt cannot avoid being snagged on a barrier, as surely as natural laws prevent building a perpetual-motion machine.

Open Problems

Does this help in ascertaining what shape a proof that resolves the P versus NP problem must have?

The Doomsday Argument in Chess

June 7, 2020


Framing a controversial conversation piece as a conservation law

Snip from Closer to Truth video on DA

John Gott III is an emeritus professor of astrophysical sciences at Princeton. He was one of several independent inventors of the controversial Doomsday Argument (DA). He may have been the first to think of it but the last to expound it in a paper or presentation.

Today we expound DA as a defense against thought experiments that require unreasonable lengths of time.

Read more…