Thursday, October 23, 2014

Fourier transform of the coprime numbers map

Disclaimer: the idea is not mine, I've found a low-resolution image and the idea behind it here.

Co-prime integers

A pair of integers is called co-prime, if their greatest common denominator is 1. For example, 4 and 21 are co-prime, while 14 and 21 are not.

First let's draw a map of co-prime pairs. The image below shows co-prime pairs with white color.

Map of the co-prime integers, (0,0) is at the top-left corner.

The map above clearly shows some regularities, but it is actually aperiodic. It is known that its average density is \( 6 / \pi^2 \), or about 61%.

Fourier transform

But what if you take a Fourier transform of this nearly periodic pattern? The result is the following mind-blowing image.

Logarithmic amplitude of 2d Fourier transform of the co-prime numbers map, 512x512 image.

Fourier transform discovers periodicity in the source data, so applying it to some data points with nearly periodic patterns can often produce interesting results. For example, see Fourier transform of the Hilbert curve images. Still, the 3-dimensional look of the resulting image is something totally unexpected for me. Below is the same image, but rendered for a bigger fragment of the plane, 2048x2048.

Logarithmic amplitude of the 2d Fourier transform of the co-prime numbers map, 2048x2048 image.

Finally, for those who like it big, here is a 4096x4096 image, 15 Mb large. Open the link and click "Download" to get the whole file.

Extensions

The idea can be extended by building the co-prime matrix not for integers but for some general integer sequence. This gallery contains some of the spectra, obtained for different sequences: Fibonacci numbers, \(n^2+1\), \(n^3+3\), \(n^2-n+41\) (Euler polynomial with many primes), partition function values and tribonacci numbers. Curious fact: the spectrum for the Fibonacci numbers is very similar visually to the original integers spectrum. But there is a difference, the image below shows two spectra superimposed, with yellow color for integers, and blue color for Fibonacci numbers.

Two spectra superimposed: integers (yellow) and Fibonacci numbers (blue).

Source code

The images above were generated by a simple Python script below. See it here, if the gist fails to load. To run it, you will need to install Numpy and PIL (Python Imaging Library). The code itself is fairly straightforward, in fact, the most complicated part is the adaptive calculation of the brightness diapason.

Friday, October 3, 2014

Cellular automata on hyperbolic {5,4} tiling, strobing rules

In the previous post on hyperbolic cellular automata I presented a program for simulating them (Pentagrid). One of the slightly disappointing discoveries I made using this tool was the fact that totalistic binary automata on the {5;4} hyperbolic tiling are either "explosive" (almost every initial configuration grows with time, that's class 3 by the Wolfram's classification), or "limited", unable to support spaceships (classes 1 or 2).

That's because if the minimal number of alive neighbors required to the cell birth is 3 or more, then due to the geometry of the {5;4} tiling, a compact pattern can't grow "outside". This prohibits spaceships and possibility of infinite growth in such rules. However, if 2 alive neighbors are enough to create a new alive cell, then 2-cell pattern will grow infinitely, and the rule becomes "explosive". (However, some of the explosive rules support spaceships!)

Strobing rules

There is one exception though: "strobing" rules, where a cell spontaneously becomes alive if it has 0 alive neighbors, and dies, if all its neighbors are alive.

In the standard B/S notation, strobing rules on the {5,4} tiling have B0 and don't have Sa (where "a" stands for 10 neighbors). Under such rules, empty field becomes completely filled in the next generation, and then it completely dies out one generation later.

In these rules, if a pattern starts with finitely many live cells on a background of dead cells, it will continue to have finitely many live cells on a background of dead cells in every even step, but in the odd steps the pattern is reversed: there are finitely many dead cells on a background of infinitely many live cells
(From the Growth and Decay in Life-Like Cellular Automata).

Naive simulation of such rules would either require making field finite or consume infinite amount of memory, but a simple trick could be used for effective simulation: consider evolution of the difference between the "flashing" background and the cells. This can be done by replacing one strobing rules with a pair of complementary stable rules without B0 part; where first rule is applied on even generations, and the second is on odd. For example rule B0157/S01 is replaced by the pair: B234689a/S23456789a, B59a/S359a.

It is possible to find such strobing rule, that the first rule of its non-strobing representation is "explosive", and the second is "stable". Careful choice of these rules allows to find that "edge of chaos" between stability and chaotic explosion, where interesting things could occur.

Below are some results of my small exploration of such rules. I used brute-force search in the rule space, searching for the rules that do not grow exponentially fast, but produce patterns away from the original random seed.

Rules with spaceships

Rule B0157/S01

The rule is stable, random initial patterns evolves into spaceships and few very rare oscillators. This is the first rule where I discovered a spaceship. The spaceship has 7 cells in one of its configuration. It has period 4 and velocity c/2.

The 332 spaceship, moving along the hyperbolic plane.

The spaceship virtually the only common pattern in this rule, but there are some rare oscillators too. One of them is 5-star:

Rule B0157A/S01

This rule is very similar to the previous. The same spaceship is present, but the 5-star oscillator has different period

5-star and its oscillator evolution in the B0157A/S01 rule.

Rule B01357/S01

This rule has a slightly different spaceship, made of 5 cells. Also, this rule is on the "explosive" side of the "edge of chaos". Though most small patterns are not growing infinitely, most big random patterns show gradual population growth. I has not identified a smallest pattern, that causes this behavior, probably, there are some natural replicators, puffers or rakes.

The 32 spaceship in the rule B01357/S01, period is 4, velocity is c/2.

5-star is stable in this rule, but there are different oscillators.

Rule B01357A/S01

This rule has the same 32-spaceship and several rare oscillators. Same as the previous, B01357/S01 shows slow infinite growth for large initial patterns. No minimal pattern with infinite growth identified.

Rule B01347/S013

The spaceship in this rule has different configuration, I dubbed it L-ship. It has period 8 and velocity c/2, same as the rest spaceships. This rule is stable, random initial pattern quickly evolves into some spaceships and very rare oscillators.

L-ship with period 8 and velocity c/2, in the rule B01347/S013.

Oscilators are rarely produced

One of the rare oscillators, 4-bar.

Rule B01367A/S013

This rule is stable, with c/2 spaceship which is the same as L-ship above, but because of the different intermediate steps, this spaceship does not coincides with its own mirror image.

L-ship in the rule B01367A/S013, same velocity c/2 and period 8.

Rules without spaceships

There also are some rules exhibiting slow growth, but without apparent spaceships or puffers. I haven't identified the mechanism of growth in them.

Rule B01568A/S013

No spaceships visible, but random initial patterns tends to grow slowly. Some oscillators are present.

Relatively common period-6 oscillator.

Rule B01568/S01

Same as above. No spaceships found, slow but steady growth, oscillators.

Rule B01478A/S01

Same as above. No spaceships found, slow but steady growth. Has 2 common oscillator patterns: 3-celled corner and 5-star.

Conclusion

Some properties are common for all of the explored strobing rules (that are the small part of the whole rule space).

  1. "Static" patterns are rare. This is natural, because the patterns that appear static in the simulation (hence quotes), are actually inverting on each step, together with background.
  2. The set of naturally occurring patterns is very limited. Usually, there is one or no spaceship with velocity c/2, and a few significantly rare oscillators. Some oscillators can be constructed manually, but almost never form naturally.
  3. Discovered spaceships have clear resemblance. The same velocity c/2 regardless the period, the same method of moving by growing a block of 2 cells on each even generation.

Open questions

Some questions I don't have an answer:

  1. Are there any other spaceship in these rules? Geometry of the hyperbolic plane seems to complicate formation of the "wide" spaceships, but "long" ones should be possible.
  2. What pattern causes very slow but infinite growth in some of the rules? Some patterns are visible, but they are relatively big and hard to grasp.
  3. Are there any significantly different rules with spaceships?

Software

To produce images and animations, self-written Pentagrid simulator was used. It is open source, and runs on every desktop platform supported by Java (Linux and Windows are tested). To run the program, download the pentagrid-0.x.jar file and run it with java -jar (usually double-click in Windows). Install Java runtime, if not installed (it is safe if you don't enable java plug-in in the browser). The program has very basic GUI and controlled by the hot keys, so read the readme first.