Computational Irreducibility Begins to Bite

One way to think about prime numbers is as follows:

Take a one dimensional binary pattern with all the bits set to zero. Now take the number a and starting at bit 2a set the binary bits at 3a,4a,5a etc, thus effectively describing a periodic pattern of set bits with an interval of a. This simple selection scheme for setting bits can be represented by the elementary mathematical function y = an + a where n =1,2,3,4..etc and where values of y gives us the locations of the bits that must be set.

Now, let us carry out this process of setting bits for all values of a = 2,3,4,5,6,7…. until limited by the length of the binary pattern. When this procedure has been completed all the bits that have not been set are placed at bit locations whose position value is a prime number. Basically a prime number is a number that doesn’t get selected by any of the periodic selection schemes defined by the equation with form y=an+a.

Now consider the mathematical object called “The Ulam Spiral of primes”, a concept that I got from this very interesting blog post by Mark Chu-Carroll. In the diagram below the natural numbers are arranged in spiral pattern and the primes are plotted in red.

If this process is continued and viewed from a distance this is what you get:

As MarkCC puts it:

Look at how many diagonal line segments you get! And look how many diagonal line segments occur along the same lines! Why do the prime numbers tend to occur in clusters along the diagonals of this spiral? I don't have a clue. Nor, to my knowledge, does anyone else!

Intuitions about it are almost certainly wrong. For example, when I first thought about it, I tried to find a numerical pattern around the diagonals. There are lots of patterns. For example, one of the simplest ones is that an awful lot of primes occur along the set of lines f(n) = 4n²+bn+c, for a variety of values of b and c. But what does that tell you? Alas, not much. Why do so many primes occur along those families of lines?

Interpreting this spiral diagram in terms of the 1-D binary pattern model, these 2-D spiral models are another way of generating a “bit set” selection scheme, except that these schemes are not periodic but instead the space between selections is increasing in proportion to value of n – this leads to the n² term in MarkCC’s expression. What MarkCC is telling us is that some of these selection schemes pick up a high frequency of primes. He then asks the pertinent question:

Why do so many primes occur along those families of lines?

When I heard that question the first useful thought I had was to think of Stephen Wolfram’s work on computation and in particular of his concept of computational irreducibility. Taking our cue from Wolfram the answer may be that there is no answer to this question of “why?” other than to carry out the computation itself. Let me explain:

The time required to arrive at certain computed patterns cannot be shortened beyond a minimum computation length. Wolfram brings this concept out into sharp focus: He tells us that this irreducibility means what it says: Once we have the minimum length computation in our hands there is, by definition, no other computation available to demonstrate the result any quicker.

If computational irreducibility applies to the case in point then it would mean that the only way to show up those diagonals with a high incidence of primes is to do the long calculation of generating the spiral and the primes. When we ask the question “why” in this context we are, I suggest, looking for a succinct analytical answer to the question in the form of some relatively simple algorithm demonstrating the pattern in a relatively short execution time; in other words an analytical short cut. But according to Wolfram there may be no simpler way of demonstrating the pattern than to do it the long way. Or rather, the long way is in fact the short way because there is no shorter way to do it!

Of course, we don’t know for a fact that this particular problem is computationally/analytically irreducible. But even if it is reducible we may still find that the solution to the meta-problem of determining whether or not a task is reducible is a computation that itself is plagued by the limits of computational irreducibility.

I believe the generality of Wolfram’s views on this subject are valid. I also believe that it is possible to get an intuitive feel for why they are valid. As I have already said, when human beings ask “why?” they are asking for an answer in the form of some “short” algorithm that succeeds in arriving at an answer in a “short” execution time. We are human after all and we have limited space and limited time. Unsurprisingly, then, we want answers to be reached using as little space and time as possible. But if we are going to limit space and time the computations that are open to algorithmic demonstration are going to be accordingly limited; the reason for this is fairly obvious: As soon as we make stipulations limiting computational resources those stipulations automatically exclude the overwhelming number of computations that utilize either large algorithms or large execution times (or both). The number of short algorithms executing in short time is a limited resource and their allocation to problem solution runs out long, long before they have covered the whole domain of solutions. Thus the absence of a simple analytical solution to the question of the spiral and primes may be evidence of the demand pressure on the relatively short supply of succinctly performing algorithms: The demand for fast succinct algorithms outstrips their supply and thus most problems will have irreducibly long winded solutions.