## A Polemical Overreach?

*Our 1977 paper on the role of formal methods*

[ Harvard ] |

Harry Lewis is known for his research in mathematical logic, and for his wonderful contributions to teaching. He had two students that you may have heard of before: a Bill Gates and a Mark Zuckerberg.

Today I wish to talk about a recent request from Harry about a book that he is editing.

Read more…

## A Diophantine Obvious Problem

*With a short solution that was hard for me to find.*

[ Royal Society ] |

Sir Timothy Gowers is a Fields medalist and fellow blogger. Sometimes he (too) writes about simple topics.

Today I would like to talk about a simple problem that came up recently.

The problem is a simple to state “obvious fact”. The reason I thought you might be interested is that I had a tough time finding the solution. I hope you find the explanation below interesting.

The general issue of proving obviously true statements is discussed here for example. Here is an example from Gowers:

Let be intervals of real numbers with lengths that sum to less than , then their union cannot be all of .

He says:

It is quite common for people to think this statement is more obvious than it actually is. (The “proof” is this: just translate the intervals so that the end point of is the beginning point of , and so on, and that will clearly maximize the length of interval you can cover. The problem is that this argument works just as well in the rationals, where the conclusion is false.)

## The Problem’s Statement

The following simple problem came up the other day. Suppose that is an odd number. Show there is some so that

Here is the gcd, the greatest common divisor of and . For example,

This result seems totally obvious, must be true, but I had trouble finding a proof.

## The Problem’s Cousin

There is a unproved conjecture in number theory that says: There are an infinite number of so that both and are prime. This clearly shows that there is an for our problem.

I like conjectures like this since they give you an immediate insight that a statement is likely to be true. But we would like a proof that does not use any unproved conjectures. Our problem can be viewed as a poor version of some of these conjectures. Suppose that you have a conjecture that there are an infinite number of so that

are all prime for some given functions . Then the poor version is to prove that there are so that these numbers are all relatively prime to some given . There are some partial results to the prime version by Ben Green and Terence Tao.

## The Problem’s Failed Proofs

My initial idea was to try to set to something like . The point is that this always satisfies the first constraint: that is for any . Then I planned to try and show there must be some that satisfies the second constraint. Thus the goal is to prove there is some so that

But this is false. Note that if divides then

and so is always divisible by . Ooops.

My next idea was to set to a more “clever” value. I tried

Here I thought that I could make special and control the situation. Now

This looked promising. I then said to myself that why not make a large prime . Then clearly

Since and are relatively prime by the famous Dirichlet’s Theorem on arithmetic progressions we could make a prime too by selecting . This would satisfy the second constraint, and we are done.

Not quite. The trouble is that we need to have also that

Now this is

The trouble is that might not be relatively prime to . So we could just This seems like a recursion and I realized that it might not work.

## The Problem’s Solution

I finally found a solution thanks to Delta Airlines. My dear wife, Kathryn Farley, and I were stuck in DC for several hours waiting for our delayed flight home. This time was needed for me to find a solution.

The key for me was to think about the value . It is usually a good idea to look at the simplest case first. So suppose that , then clearly the constraints

are now trivial. The next simplest case seems to be when is a prime. Let’s try . Now works. Let’s generalize this to any prime . The trick is to set so that

Then is equal to modulo , which is not divisible by . This shows that when is an odd prime there is always some .

Okay how do we get the full result? What if is the product of several primes? The Chinese remainder theorem to the rescue. Suppose that is divisible by the distinct odd primes . We can easily see that we do not care if there are repeated factors, since that cannot change the relatively prime constraints.

Then we constraint by:

and

for all primes . Then the Chinese remainder theorem proves there is some . Done.

## Open Problems

Is there some one line proof of the problem? Do you know any references? There are several obvious generalizations of this simple problem, perhaps someone might look into them.

## Writing 33 as a Sum of Cubes

*Cracking a Diophantine problem for 42 too*

Andrew Booker is a mathematician at the University of Bristol, who works in analytic number theory. For example he has a paper extending a result of Alan Turing on the Riemann zeta function. Yes our Turing.

Today Ken and I will talk about his successful search for a solution to a 64 year old problem.

Read more…

## Quantum Switch-Em

*A recipe for changing the objectives of problems*

Composite crop of src1, src2, src3 |

Aram Harrow, Avinatan Hassidim, and Seth Lloyd are quantum stars who have done many other things as well. They are jointly famous for their 2009 paper, “Quantum algorithm for linear systems of equations.”

Today Ken and I discuss an aspect of their paper that speaks to a wider context.

Read more…

## Separating Words by Automata

*Another exponential gap in complexity theory?*

[ From his home page ] |

Jeffrey Shallit is a famous researcher into many things, including number theory and being a skeptic. He has a colorful website with an extensive quotation page—one of my favorites by Howard Aiken is right at the top:

Don’t worry about people stealing an idea. If it’s original, you will have to ram it down their throats.

Today I thought I would discuss a wonderful problem that Jeffrey has worked on.

Jeffrey’s paper is joint with Erik Demaine, Sarah Eisenstat, and David Wilson. See also his talk. They say in their introduction:

Imagine a computing device with very limited powers. What is the simplest computational problem you could ask it to solve? It is not the addition of two numbers, nor sorting, nor string matching—it is telling two inputs apart: distinguishing them in some way.

More formally:

Let and be two distinct long strings over the usual binary alphabet. What is the size of the smallest deterministic automaton that can accept one of the strings and reject the other?

That is, how hard is it for a simple type of machine to tell apart from ? There is no super cool name for the question—it is called the *Separating Words Problem* (SWP).

## Some History

Pavel Goralčik and Vaclav Koubek introduced the problem in 1986—see their paper here. Suppose that and are distinct binary words of length . Define to be the number of states of the smallest automaton that accepts and rejects or vice-versa. They proved the result that got people interested:

Theorem 1For all distinct binary words and of length ,

That is the size of the automaton is asymptotically sub-linear. Of course there is trivially a way to tell the words apart with order states. The surprise is that one can do better, always.

In 1989 John Robson obtained the best known result:

Theorem 2For all distinct binary words and of length ,

This bound is pretty strange. We rarely see bounds like it. This suggest to me that it is either special or it is not optimal. Not clear which is the case. By the way it is also known that there are and so that

Thus there is an exponential gap between the known lower and upper bounds. Welcome to complexity theory.

What heightens interest in this gap is that whenever the words have different lengths, there is always a logarithmic-size automaton that separates them. The reason is our old friend, the Chinese Remainder Theorem. Simply, if there is always a short prime that does not divide , which means that the DFA that goes in a cycle of length will end in a different state on any of length from the state on any of length . Moreover, the strings and where equals plus the least common multiple of require states to separate. Padding these with s gives equal-length pairs of all lengths giving **SEP**(x,y).

Some other facts about SWP can be found in the paper:

- (a) It does not matter whether the alphabet is binary or larger.
- (b) For random distinct , the expected number of states needed to separate them is at most .
- (c) All length- pairs can be distinguished by deterministic pushdown automata (with two-way input tape) of size .

Point (b) underscores why it has been hard to find “bad pairs” that defeat all small DFAs. All this promotes belief that logarithmic is the true upper bound as well. Jeffrey stopped short of calling this a conjecture in his talk, but he did offer a 100-pound prize (the talk was in Britain) for improving Robson’s bound.

## Some Questions

There are many partial results in cases where and are restricted in some way. See the papers for details. I thought I would just repeat a couple of interesting open cases.

How hard is it to tell words from their reversal? That is, if is a word can we prove a better bound on

Recall is the reversal of the word . Of course we assume that is not the same as its reversal—that is, we assume that is not a palindrome.

How hard is it to tell words apart from their cyclic shifts?

How hard is it to tell words from their You get the idea: try other operations on words.

## Open Problems

The SWP is a neat question in my opinion. I wonder if there would be some interesting consequence if we could always tell two words apart with few states. The good measure of a conjecture is: how many consequences are there that follow from it? I wonder if there could be some interesting applications. What do you think?

## Self-Play Is Key?

*Self-play and Ramsey numbers*

[ Talking about worst case ] |

Avrim Blum is the CAO for TTIC. That is he is the Chief Academic Officer at the Toyota Technological Institute of Chicago. Avrim has and continues to make key contributions to many areas of theory—including machine learning, approximation algorithms, on-line algorithms, algorithmic game theory, the theory of database privacy, and non-worst-case analysis of algorithms.

Today I want to discuss a suggestion of Avrim for research on self-play. Read more…