## The Halting Problem For Linear Machines

* A small idea before the fireworks show *

Thoralf Skolem was a mathematician who worked in mathematical logic, set theory, and number theory. He was the only known PhD student of Axel Thue, whose Thue systems were an early word-based model of computation. Skolem had only one PhD student, Öystein Ore, who did not work in logic or computation. Ore did, however, have many students including Grace Hopper and Marshall Hall, Jr., and Hall had many more including Don Knuth.

Today Ken and I try to stimulate progress on a special case of Skolem’s problem on linear sequences.

Although Ore worked mainly on ring theory and graph theory the seeds still collected around Skolem’s tree: Hall’s dissertation was titled “An Isomorphism Between Linear Recurring Sequences and Algebraic Rings.” Sequences defined by a finite linear operator are about the simplest computational process we can imagine:

The coefficients and initial values can be integers or relaxed to be algebraic numbers. Skolem posed the *problem* of deciding whether there is ever an such that .

This is a kind of halting problem. It seems like it should be simple to analyze—it is just linear algebra—but it has remained open for over 80 years. We have discussed it several times before. This 2012 survey by Joel Ouaknine and James Worrell, plus this new one, give background on this and some related problems.

## The Sum-of-Powers Case

Let be

where each is an algebraic integer. Our problem is:

Does there exist a natural number so that ?

This is a special case of the Skolem problem. It arises when the coefficients are the evaluations of the elementary symmetric polynomials at with alternating signs. For example, with we get

which for and gives

and so on. For we have

Then means If the are nonzero integers then for odd this is asking whether is a solution to Pierre Fermat’s equation, and we can simply answer “no.” Of course whether is a solution can be easier than asking whether the equation has a solution, but this shows our case contains some of the flavor of Fermat’s Last Theorem.

We can point up some minor progress on this problem. Our methods can handle somewhat more general cases where the sum of -th powers is multiplied by for some fixed constants and , but we will stay with the simpler case. Our larger hope is that this case embodies the core of the difficulty in Skolem’s problem, so that solving it might throw open the road to the full solution.

## Proof

Let’s begin the proof for the case when is a prime . Suppose that . Recall

Clearly we can assume that . Note that this is decidable. Put . The key is to look at the quantity

where is a prime. We employ the following generalization of the binomial theorem:

where

The upshot is that all terms are divisible by a proper factor of except those from the cases , all other . Each gives a factor of and leaves the term . When is a prime this factor must include itself. Thus we get that for some of the form

where is an algebraic integer. But by the supposition this simplifies to , and so is divisible by . Thus

Since , too is divisible by . But is independent of Hence, acts as a bound on any possible prime such that . Testing the finitely many values of up to thus yields a decision procedure for this restricted case of Skolem’s problem.

## Fine-Tuning and Fireworks

Ken chimes in an observation that might be distantly related: The Vandermonde determinant

is the “smallest” alternating polynomial in variables. Together with the symmetric polynomials it generates all alternating polynomials. When the are the -th roots of unity it gives the determinant of the Fourier matrix up to sign. This determinant has absolute value

It is also the product of the lengths of the chords formed by equally-spaced points on the unit circle. The observation is that this 2-to-the-nearly-linear quantity is extraordinarily finely tuned.

To see how, let’s estimate the product of the chords in what is caricatured as the style of physicists: The length of an average chord is . So we can estimate the size of the product as

This is off by an order of magnitude *in the exponent*—not even close. We can be a little smarter and use the average length of a chord instead, integrating from to to get . This is still a number greater than and plugs in to yield anyway.

Such a calculation looks silly but isn’t. If we enlarge the circle by a factor of then every term in the product is multiplied by that factor and it dominates:

If we shrink the circle by the opposite happens: we divide by which crushes everything to make the analogous quantity virtually zero. Furthermore this “big crush” happens under more-plausible slight perturbations such as forbidding any of the points from occupying the arc between and radians, which prevents the equal-spacing maximization when . We covered this at length in 2011.

The underlying reality is that when you take the logarithm of the product of chords, the terms of all growth orders between and all magically cancel. There are many more chords of length than chords of length , but the latter can be unboundedly short in a way that perfectly balances the multitudes of longer chords. The actual value of seems tiny amidst these perturbative possibilities.

This gigantic cancellation reminds Dick and me of the present argument over the tiny observed magnitude of the cosmological constant . Estimation via quantum field theory prescribes a value 120 orders of magnitude higher—one that would instantly cause our universe to explode in fireworks—unless vast numbers of terms exactly cancel. Quoting Wikipedia:

This discrepancy has been called “the worst theoretical prediction in the history of physics” … the cosmological constant problem [is] the worst problem of fine-tuning in physics: there is no known natural way to derive the tiny [value] from particle physics.

“Fine-tuning” of constants without explanation is anathema to science, and many scientists have signed onto theories that there is a multiverse with 500 or more orders of magnitude of universes, enough to generate some with the tiny needed to allow life as we know it. However, any fine-tuning discovered in mathematics cannot be anathema. Perhaps the universe picks up the Fourier fine balancing act in ways we do not yet understand. More prosaically, the fine balance in quantities similar to above could be just what makes Skolem’s problem hard.

## Open Problems

I believe that the general case of the Skolem can be handled, not just the simple case. But the problem of handling more than just primes seems hard. I believe that this method can be used to handle more cases than just primes. Ken and I are working on this. Meanwhile, we wish everyone Stateside a happy Fourth of July, whether or not that includes fireworks.

[added link to new survey in intro]

## We Say Branches And You Say Choices

* You like tomato and I like tomahto *

Oded Green, Marat Dukhan, and Richard Vuduc are researchers at Georgia Institute of Technology—my home institution. They recently presented a paper at the Federated Conference titled, “Branch-Avoiding Graph Algorithms.”

Today Ken and I would like to discuss their interesting paper, and connect it to quite deep work that arises in computational logic.

Read more…

## Fathering Randomized Fault Tolerance

* Plus visiting Michael Rabin and talking about Gödel’s Theorems *

Michael Ben-Or and Michael Rabin have won the 2015 Dijkstra Prize for Distributed Computing. The citation says,

In [two] seminal papers, published in close succession in 1983, Michael Ben-Or and Michael O. Rabin started the field of fault-tolerant randomized distributed algorithms.

Today Ken and I wish to congratulate both Michaels for the well deserved recognition for their brilliant work.

Read more…

## Security Via Surrender

* A new approach to protecting data and identity *

Cropped from src1, src2 |

David Sanger and Julie Davis are reporters for the paper of record—the New York Times. Their recent article starts:

WASHINGTON—The Obama administration on Thursday announced what appeared to be one of the largest breaches of federal employees’ data, involving at least four million current and former government workers in an intrusion that officials said apparently originated in China.

The compromised data was held by the Office of Personnel Management, which handles government security clearances and federal employee records. The breach was first detected in April, the office said, but it appears to have begun at least late last year.

The target appeared to be Social Security numbers and other “personal identifying information,” but it was unclear whether the attack was related to commercial gain or espionage. …

Today Ken and I want to suggest a new approach to data breaches like this.

Read more…

## Minor Insights Are Useful

* Some examples of small insights that help *

Cropped from src1, src2 |

Julia Chuzhoy and Chandra Chekuri are experts on approximation algorithms: both upper and lower bounds. Each is also interested in graph theory as it applies to algorithms.

Today Ken and I wish to talk about their recent papers on structural theorems for graphs.

Read more…

## Puzzling Evidence

* Exponential hardness connects broadly to quadratic time *

Cropped from src1, src2 |

Arturs Backurs and Piotr Indyk are student and advisor. The latter, Piotr, is one of the leading algorithms and complexity theorists in the world—what an honor it must be for Arturs to work with him as his advisor.

Today Ken and I want to talk about their paper on edit distance and an aspect that we find puzzling.

Read more…

## John and Alicia Nash, 1928,1933–2015

* Our condolences *

Awesome Stories source |

John Nash and his wife Alicia were killed in a taxi accident on the New Jersey Turnpike Saturday afternoon. They were on their way back from Norway where he and Louis Nirenberg had just accepted the 2015 Abel Prize. Besides meeting the king of Norway, Nash had also expressed a desire to meet world chess champion Magnus Carlsen during remarks at Princeton’s celebration of his Abel Prize in March, and that was also granted this past week.

Today Dick and I join many expressing shock and offering condolences.

Read more…