Or is it number theory?

Julius Büchi was a Swiss mathematician who taught at Purdue University for many years. His is arguably a case of influence—in multiple fields—far exceeding a modest number of publications. A number of those, both at DBLP and his collected works, came after his untimely passing in 1984. His influence in logic was furthered by his association with Saunders Mac Lane; in computer science, through his PhD student Lawrence Landweber and a group of computer science logicians that included Paul Young.

Today we talk about a new book by Jeffrey Shallit that may extend this influence further.

We recently wrote about the seminal 1958 paper on finite automata by Michael Rabin and Dana Scott and its place in the early history of theory in the decade before and after. Büchi contributed by associating to a finite automaton the language of infinite words over the alphabet of that cause to be in an accepting state infinitely often. Another of Büchi’s close associates, Dirk Siefkes, wrote in his intro to Büchi’s collected works:

He is probably best known for using finite automata as combinatorial devices to obtain strong results on decidability and definability in monadic second-order theories, and extending the method to infinite combinatorial tools.

Siefkes goes on to observe how Rabin extended Büchi’s method to general infinite binary trees, modeled via a logical theory with two successor functions, and how melding this with work by Robert McNaughton yielded rich decidability and determinacy results for monadic second-order formulas over this logic.

Into Number Theory

Büchi posed a question that at first seems innocuous:

Are there five non-consecutive natural numbers that satisfy the recurrence

for ?

The entire infinite sequence of integers satisfies the recurrence since always equals 2. An example of four non-consecutive integers that do so is . But this sequence does not extend because is not a perfect square.

No example of five is known. However, no one has ruled out that such sequences of length exist for every finite . What Büchi proved is:

Theorem 1 If there exists such that the only length- sequences of natural numbers satisfying the recurrence (1) are consecutive integers, then the undecidability of Hilbert’s Tenth Problem applies all the way down to quadratic equations, indeed ones of the form where is a matrix of integers, is a vector of integers, and is a vector of squared variables. Moreover, existential sentences over Presburger arithmetic plus the predicate “ is a perfect square” would become undecidable.

The technical tour-de-force is how Büchi makes a length- sequence of nonconsecutive natural numbers that satisfy the recurrence become the only obstacle to a scheme for defining the graph of multiplication from predicates about perfect squares. The theory of addition and multiplication is of course undecidable—thanks to Kurt Gödel and Alan Turing.

Büchi’s Own Arithmetic

Büchi added a different predicate to Presburger arithmetic. Let denote the largest power of dividing . The resulting first-order theory is named in honor of Büchi.

This theory is decidable. And the big observation is that this is more powerful than we perhaps realized. Ken and I find this quite interesting.

The theory is decidable, but just barely. The addition of to Presburger makes the theory much stronger. So strong that adding two independent ‘s, that is where and are relatively prime, is dangerous, since becomes undecidable. This is neat. Indeed, has the power of all of Peano arithmetic.

The power possessed by with a single is to describe finite automata over a -letter alphabet. This plays both into why is decidable and into the applications collected by Shallit.

A New Book

Jeffrey Shallit recently sent a private message about his new book:

He wrote:

I thought maybe you might possibly be interested in my new book, which is about how a decision procedure for Büchi arithmetic–namely, –can be used to prove hundreds of old and new results in number theory, combinatorics on words, and automatic sequences. There is probably no big theoretical advance in the book, just a recognition that existing results might be more useful than we suspected.

The book comes with a software package called Walnut, which was written by Hamoon Mousavi while a student in Shallit’s department, and has been added to by other Waterloo students since. It executes a rendition of Büchi’s and others’ automata-based decision strategy.

An Example

Here is a simple example that begins the number theory chapter of the book.

Proposition. The numbers for cannot be written as the sum of two natural numbers, each having an even number of s in its binary representation. Every other number greater than can be so written.

Via a finite automaton that distinguishes “even” from “odd” and its use of but not multiplication, this can be formulated in . The software then cranks out a proof.

Further examples require absorbing the notion of automatic sequence in the book’s title, and we’ll stop here. Incidentally, the worst-case running time of Walnut on a formula with -many alternating quantifiers built via an -state finite automaton with output is

where there are -many s. The examples in the book—and maybe almost all examples one would devise using the approaches in the book—all halt within reasonable time. Why this is observed to hold might be a topic for another post.

What Is Combinatorics?

Igor Pak, who is a professor in the Mathematics Department at UCLA and works in the Combinatorics Group, has this to say on his webpages:

He says:

Combinatorics is a pretty diverse area and hard to characterize. Of course, combinatorics is about counting, but it is a lot more than just that. See here for more quotes about it.

As you all know, my field is Combinatorics. I care about it. I blog about it endlessly. I want to see it blossom. I am happy to see it accepted by the broad mathematical community. It’s a joy to see it represented at (most) top universities and recognized with major awards. It’s all mostly good.

Of course, not everyone is on board. This is normal. Changing views is hard. Some people and institutions continue insisting that Combinatorics is mostly a trivial nonsense (or at least large parts of it). This is an old fight best not rehashed again.

Open Problems

Enjoy Jeffrey’s book—thanks. See here to buy it. Ken’s current student Chen Xu already owns it and is referencing it for some of his work.

[“integers” -> “natural numbers” in a few places; inserted “of length k” in sentence before Büchi’s theorem]]