Ulam's Spiral: Has it been explained or not?

[Sequent]

@Mathochist

Also, please to note that that image appears on a website purporting to unseat mathematics in favor of Christianity. I call bullshit.

In fact, the density around a point distance r from the center should be on the order of r/ln(r), and that plot seems to go up faster that that with distance. Again: bullshit.

True dat. I was looking for a better source for the image, too. I found it on a site about math, though; indeed, one that was attempting to show that there wasn’t anything remarkable about the pattern? “Ulam’s Rose? Get a grip!” was how it described the image, I think.

Yes, I’ve got big problems with that image’s source, too. The one-pixel-per-integer image is easy enough to recreate, but I don’t know what scaling method was used for that one. I’d actually be interested to try to recreate it, though, to see if what I came up with was anywhere near as striking.

[Derleth]

@Sequent

A true random sequence, then. I take it we’ll only need one of those? You’re right, humans are poor judges of lots of things. Could a computer do it?

Only with external help. There’s no way to go from the deterministic (a computer plodding though a predefined series of steps) to the nondeterministic (a sequence of random numbers) without adding a nondeterministic element.

I’d also like to amplify ultrafilter’s reply: There is no way to know a sequence of numbers is random unless you know the sequence’s origin. And even if you do know the sequence came from something like a geiger counter turned towards a decaying hunk of metal, it still might not have the properties you want in a random sequence.

The thing to understand is that looking random has nothing to do with being random. The sequence ‘55555’ could well come out of that geiger counter. If you are having a bad day when you try to generate a new cryptographic key, it could keep coming out until you think you have a good 2048-bit key. It is no more unlikely than any other specific sequence.

It is, however, part of a rare group of sequences. The vast majority of possible 2048-bit random numbers behave as expected when we apply standard statistical tests, which is why we have those tests at all. It’s a crapshoot, but the odds of a sequence that pathological coming from a true hardware random-number generator are lower than shooting 20 7s in a row with unloaded dice.

My point being, of course, that you can’t hold a sequence, even a large one, up to the light and say for sure if it’s random or not. You aren’t interested in that anyway, most of the time: What you want is a sequence that exhibits certain properties we can test for.

[Omphaloskeptic]

@Mathochist

In fact, the density around a point distance r from the center should be on the order of r/ln(r), and that plot seems to go up faster that that with distance.

I noticed that too (in fact, the density seems to vary nonmonotonically with the Manhattan distance from the center). My only guess (assuming the image ever was a real Ulam’s spiral) is that at some point the image was rescaled and interpolated and “enhanced” somehow. Note that the claim (on the page that links to that image) is that the image is the spiral for the primes from 1 to 262144=2[sup]18[/sup]; so the image ought to be 512x512 pixels. Actually it’s 771x751 (not even square!), so the primes aren’t single pixels.

I created a 2000x2000 Ulam’s spiral last night (200K PNG; if you want to look at it or host it somewhere I’ll email it to you if you’d like), and indeed it looks nothing like that image (though it should contain the spiral in question). If you dither it (or look at it from far away) it looks like a fuzzy point in the center, very gradually dimming with distance (as Mathochist said, the prime density should be about 1/(2ln(r)) near the edge of a centered square of size r). To my eyes the diagonal lines are fairly obvious near the center but get somewhat less clear near the edges of this square (i.e., for primes ~4e6).

The integers along straight lines in the Ulam spiral are given by the values of quadratic equations f(x)=ax[sup]2[/sup]+bx+c, for whole x (or by the union over several such equations). It’s known that some such equations produce a lot of early primes (e.g. n[sup]2[/sup]+n+41); these are the obvious lines near the center. These lines all start getting breaks after a while (it’s known that no single-variable polynomial produces only prime values), though some do seem to have more primes than average all the way to the edges of my image. I don’t know what is known about the asymptotic density of primes along such lines (i.e., whether any of these lines continue to have more primes than expected).

[kniz]

@Sequent

What I didn’t suggest in my previous post, but will suggest here, is that you take out a dictionary and look up the word whose meaning you’ve quite nicely explored: nitpick. I guess you can claim to have discovered it, too. :rolleyes:

I copied and pasted this from WordNet

Overview of adj unexplored
The adj unexplored has 1 sense (first 1 from tagged texts)

1. (3) undiscovered, unexplored – (not yet discovered; ``undiscovered islands’’ )

I actually looked it up before I posted on [URL=http://dictionary.reference.com/search?r=66&q=unexplored]Dictionary.com

unexplored

adj : not yet discovered; “undiscovered islands” [syn: undiscovered]

[Mathochist]

I didn’t bother looking at how many numbers they worked out, but at that few you should still see the primes fitting into a checkerboard. All the even numbers (but one) have to be composite.

@Omphaloskeptic

the prime density should be about 1/(2ln(r)) near the edge of a centered square of size r)

Are you sure it’s not r/ln(r)? I did a quick BotE before. If nothing else, this’ll show people how this sort of stuff is really done.

Let the numbers be big enough to approximate by continua and all statements more about orders of magnitude than anything else.

number of numbers inside circle of radius r, thus less than the number at radius r
pi*r[sup]2[/sup]

number of those that are prime
pir[sup]2[/sup]/(ln(pir[sup]2[/sup]))

take differential to find the number in an annulus of width dr
dr2pir*(ln(pir[sup]2[/sup])-1)/ln(pir[sup]2[/sup])[sup]2[/sup]

divide by area of annulus to get density
(ln(pir[sup]2[/sup])-1)/ln(pir[sup]2[/sup])[sup]2[/sup]

at the relevant size of r, the “-1” term is swamped, so we ignore it and get
1/(ln(pi)+2ln(r))

and the ln(pi) is insignificant, so we’re left with
1/2ln(r)

Yep, you’re right. I wonder where I got that extra r…

[AHunter3]

Why is an “explanation” needed? You’re not graphing random numbers, you’re graphing primes (or, more specifically, you’re graphing the places that primes appear in the stream of integers). Why should it not form a pattern, simply because it does not form a simple cyclical/repetitive pattern? Anyone here ever read about chaos theory? Chaotic phenomena (i.e., phenomena not conforming to the kind of pattern that lets you predict the next occurrence) does tend to have patterns. Static in phone lines. Distribution of curves in shorelines. Etc. Old news at this point.

[AHunter3]

Sorry, that came off more know-it-all than I have any right to be in a mathematics thread. If there’s a reason why the existence of a pattern within such a graph of primes should still be surprising, feel free to tell me I’m an irrelevant kibitzer and move on.

[Mathochist]

@AHunter3

Sorry, that came off more know-it-all than I have any right to be in a mathematics thread. If there’s a reason why the existence of a pattern within such a graph of primes should still be surprising, feel free to tell me I’m an irrelevant kibitzer and move on.

Done, and done.

Basically, prime numbers haven’t yet yielded any predictable pattern in their distribution, other than the fact that there are roughly x/ln(x) of them less than x. If we knew a pattern, factoring would be a lot easier, among other things.

As for the whole “chaos” red herring, you fall into the (depressingly) standard pit of confounding chaos with disorder or randomness. Chaos is a jargon term, not a standard English word, and it refers to the sensitive dependance of the long-term behavior of a dynamical system on its initial conditions, among other things. Basically, prime distribution and chaos theory have a priori nothing to do with each other. That isn’t to say there isn’t a connection nobody’s seen yet, but it’s certainly not the obvious fact you call us short-sighted dolts out for not seeing.

[AHunter3]

Predictable pattern <> pattern. Static on long-distance telephone lines doesn’t follow any predictable pattern either, but if you graph the interval between one burst and the next against the interval between the latter and that one next to follow, you don’t get a random smear of dots but rather patterns. Data points are said to be drawn to “strange attractors”.

I am not telling you all this to educate you, I assume you know all this, and I’m just pointing to it to say “this stuff, this is what I was talking about”.

I see no reason to assume that prime numbers, which are not being distributed in a predictable pattern, are therefore distributed at true random. So as it turns out there’s a pattern (as the graph indicates), it’s just a pattern akin to the pattern of waterdrop intervals from the chaotically dripping faucet and so forth.

[Mathochist]

@AHunter3

I see no reason to assume that prime numbers, which are not being distributed in a predictable pattern, are therefore distributed at true random. So as it turns out there’s a pattern (as the graph indicates), it’s just a pattern akin to the pattern of waterdrop intervals from the chaotically dripping faucet and so forth.

There’s not even anything yet discovered as predictable as an attractor. Primes are not distributed by a dynamic map, so the analogy you’re trying to draw is really not there. The notion of an attractor (which is, let’s be honest, a lot more subtle than the idea you seem to have in your head) just doesn’t apply the way you think it does. There’s no motion so there’s no attraction.

And besides, the entire notion of a “pattern” is that there’s some amount of predictability. Not deterministic, maybe, but if there’s no predictability at all there’s no pattern.

[snailboy]

I can predict that the 1,000th prime number is an odd integer. Is that predictable enough for you? Perhaps not, but it’s more than I can tell you about the 1,000th digit of pi.

[Omphaloskeptic]

@AHunter3

Why is an “explanation” needed? You’re not graphing random numbers, you’re graphing primes (or, more specifically, you’re graphing the places that primes appear in the stream of integers). Why should it not form a pattern, simply because it does not form a simple cyclical/repetitive pattern? Anyone here ever read about chaos theory? Chaotic phenomena (i.e., phenomena not conforming to the kind of pattern that lets you predict the next occurrence) does tend to have patterns. Static in phone lines. Distribution of curves in shorelines. Etc. Old news at this point.

“Why is an explanation needed?” – Well, because that’s what mathematicians do: try to figure out why various mathematical structures exist. In this case in particular, mathematicians don’t really know much about the distribution of primes, and they’d really like to know more. Some of the most famous unsolved mathematical conjectures involve primes: more specifically, primes and addition. Primes and prime factorizations, being defined multiplicatively, behave nicely under multiplication, but become very confusing when addition is involved. For example: Goldbach’s conjecture (Every even number greater than 2 is the sum of two primes), the twin-primes conjecture (there exist an infinite number of prime pairs (p,p+2)), and the Riemann hypothesis (the nontrivial zeroes of the Riemann zeta function have real part 1/2–this is related in a somewhat subtle way to the distribution of primes) all are of this type.

Just calling this “chaos theory: old news” is too dismissive. The thing about chaos theory is that, although its name might suggest otherwise, it’s really quite well understood. Once the governing equations of the system are known, they can be analyzed in a pretty straightforward way to see if the system is expected to be chaotic or not. For chaotic systems like the ones you mention above, there are dynamical models that predict the onset of chaotic behavior as various parameters are tweaked. (These can be more or less accurate depending on the fidelity of the underlying model, but we think we understand more or less why things become chaotic.)

But in this case we haven’t got any good ideas what the underlying “dynamic” equations might look like. (Of course, the primes are not a dynamic system at all, but you might look at the sequence of primes, or the prime differences p[sub]n+1[/sub]-p[sub]n[/sub], or maybe the prime differences divided by ln(n) to normalize out the obvious growth, and consider these to be samples from a Poincare section of some prime-namical system.) Without knowing what the equations are, there’s no way to honestly call this a “chaotic” system, since we don’t have any way of knowing whether what we’re seeing is really the same lack of order as the lack of order seen in chaos.

[Sequent]

I decided to recreate Omphaloskeptic’s test, first with a 512x512 spiral and then a 2000x2000 spiral, not because I don’t trust him, but just as an experiment so I could play around with the spiral on my own. (Call me a geek; I find this stuff fascinating). My results were quite similar to what he describes above: a small, dense “cloud” of points in the center surrounded by a diffusion of points which becomes less dense towards the edges. In short, nothing like the more flowerful picture to which I linked before.

And it does make sense, as Mathochist pointed out, the primes get less dense the higher one counts, so the dark lines in the “flower” image suggest clusterings of primes that simply are not there. Also, something I neglected to point out before, look at the center of the flower image: there’s nothing there! Assuming the center represents the origin starting with 0 or one, there should be at least a dark cluster there representing all the early primes, but there’s not.

Which gave me an idea: I tried a plot that “blotted” out the central cluster (a 50x50 square) on my plot (much like a weather radar eliminating ground clutter) in order to see if the outer diagonals that, as Omphaloskeptic notes, do seem to contain more primes than normal, were simply a function of my mind trying to extend the pattern it sees toward the center. The outer diagonals didn’t stand out quite as much, but they’re still definitely there. Still, nothing that makes you jump out of your seat.

Anyway, I’m only marginally interested in what the Christian Numerologists did to make the flower image; I mean, enough transforms and scaling and you could probably make the spiral look like Elvis, right? What I am interested in doing is extending the spiral out to a range where scaling would become necessary to view it as a 2000x2000 image.

So instead of showing the distribution of primes in the first 4 million numbers, the same size grid (2Kx2K) would show the primes in the first, say, 16 million numbers. In order to do that, we’d have a grid where 1 pixel represents 4 numbers instead of 1, yes? If we then made the image a 4-color greyscale instead of black, assigning the colors such that white = 0 primes…black = 4 primes, would that make for an accurate representation, or am I completely off base?

[Mathochist]

@Sequent

Anyway, I’m only marginally interested in what the Christian Numerologists did to make the flower image; I mean, enough transforms and scaling and you could probably make the spiral look like Elvis, right?

Forget transforms and scaling. Occam’s Razor tells you what they did: they lied. Plain and simple. Frankly, as would be the case with anyone else purporting to unseat the validity of mathematics, I’m entirely unsurprised.

So instead of showing the distribution of primes in the first 4 million numbers, the same size grid (2Kx2K) would show the primes in the first, say, 16 million numbers. In order to do that, we’d have a grid where 1 pixel represents 4 numbers instead of 1, yes? If we then made the image a 4-color greyscale instead of black, assigning the colors such that white = 0 primes…black = 4 primes, would that make for an accurate representation, or am I completely off base?

It could work. Two nits to pick, though. What you’re suggesting would require five colors: 0, 1, 2, 3, and 4. On the other hand, three is all you really need, since in any 2x2 square at least two of the spaces can’t be prime, since they represent even numbers.

So, call the colors w, g, and b for 0, 1, or 2 primes in the square. Up to 100, it looks like:

wgggw
bgwbg
wbbbg
bggww
bwggg

[Sequent]

Of course, five colors! :smack: The old off-by-one error. And yes, we’d be providing coverage for situations that couldn’t possibly exists…it’s just easier for me to think of it that way. Hardly nitpicks–those are valid points. A nitpick would be, say, me pointing out a subject-verb disagreement in your last post.

And them Christians ain’t supposed to bear false witness, neither.

[Sequent]

@Mathochist

If we knew a pattern, factoring would be a lot easier, among other things.

I was thinking about this vis a vis the whole RSA thing: if we had a method for predicting the primes–let’s say one that worked perfectly, always predicting the next prime accurately–factoring would be easier, but not so much easier that it wouldn’t still be extremely difficult in some cases, right?

The only benefit I can think of right away is that trial division would become a lot faster if we could limit our trial divisors to numbers we could be sure were prime. Obviously, the discovery of such a pattern would probably lead to many other discoveries regarding the primes that might, in turn, make factoring much easier.

But aside from that, for the RSA thing…they could just keep choosing larger and larger keys, such that the set of possible prime divisors for a key–even if we had a way to know the contents of that set exactly–could still be so large as to make trial division impractical, right?

[ultrafilter]

Instead of having sqrt(n) trial divisors, you’d have roughly sqrt(n)/ln(sqrt(n)). You could still choose a large enough key that it would be difficult to factor by brute force, but it would become significantly less complex in a technical sense.

[Sequent]

@ultrafilter

You could still choose a large enough key that it would be difficult to factor by brute force, but it would become significantly less complex in a technical sense.

How so? The process (trial division) hasn’t changed–just the number of trial divisors? I mean, you could eliminate the need to check a trial divisor for primality, but other than that, how does it simplify things?

[ultrafilter]

Because there are asymptotically fewer trial divisors, as I mentioned in the first sentence of the post you quoted.

[The_Controvert]

Has anyone tried playing with the start parameter? How does shifting the spiral affect the patterns?