Friday, December 4, 2009

Hilbert curve and fourier transform

Hilbert curve is a fractal curve of Hausdorf dimension 2 that fills the interior of a square. It provides continuous mapping from real interval [0;1] to unit square. This mapping is not invertible: some different points of [0;1] are mapped to the same points of the unit square.

Let us assign a color to each point of the unit interval, in simple repeating manner, and map the colored points to the square. This procedure will produce a monotonous flat pattern, which is not actually periodic.

Hilbert curve, 5th approximation (image from the Wikipedia)

Not an exciting sight. However 2D Fourier transform of this pattern reveals amazingly complex fractal structure:

Fourer transform of the Hilbert curve pattern
2D Fourier transform of the above image.

The picture above shows filtered (invert, despeckle and colorization filters were used) and scaled version of the transformed pattern. Apparently, it contains multiple images of some "rounded rectangle" shape. This shape always appears in the Fourier transform of the every repetitive Hilbert curve pattern. What is the equation of this shape? I don't know.

Monday, October 19, 2009

Irregular Mandelbrot fractals

A fragment of the irregular Mandelbrot set.

The famous Mandelbrot set is defined by the recurrent relation:
$$z_{n+1}=z_n^2+c.$$
Despite at the first glance this formula may seem simple, the set of points c, defining stable orbits of z, has incredibly complex structure:
However, when the first impression of infinite variation fades, you'll probably notice that the whole image is based on the same pattern, repeated with several variations (well, that's why it is called fractal, after all). And it is pretty boring.
Equations, other than canonical \(z_{n+1}=z_n^2+c\), can produce some different patterns,
Cubic Mandelbrot variation.
But the difference is not really drastic.
Non-homomorphic mapping functions produce significantly different patterns, but they are often too "dirty":
A Mandelbrot-like fractal, obtained from the non-homomorphic function.
This can be explained in the following way: on each iteration, non-homomorphic function scales small vicinity of each point non-uniformly. And even if the non-uniformity is small, after a number of iterations elements become "squeezed" in one directions, producing the "smeared" effect.

So, where the novelty hides?

Meet the idea: the irregular Mandelbrot set.
Instead of repetitive iteration of the same function, iterate two (or more), in an never-repeating pattern:
$$z_{n+1}=f_{Idx(n)}(z_n)+c.$$
Where \(Idx(n)\) is a non-periodic function, returning integers in the range [1..k], and \(f_1(z),...,f_k(z)\) are the different mapping functions. Non-periodicity guarantees that there are no stable cycles in Z.
Results seem interesting, at least for me. Because the mapping functions are homomorphic, there is no effect of "smearing", but non-periodicity destroys all of the repetitive, stable patterns. Here are few sample pictures:




Black-and-white palette is not a requirement, but to my artistic sense, these fractals look better without colors. See more in the album.

Saturday, January 24, 2009

36π/127 conjecture failed

My recent conjecture that the non-differentiable function
$$f(x) = \sum_{i=0}^\infty \frac{sin(2^i x)}{2^i}$$
reaches the maximum at the point \(x_0=36\pi/127\) appears to be false (thanks to people from sci.math group for pointing it out).
This is demonstrated by the following graph of the differential quotient \(\frac{f(x_0)-f(x_0-h)}h\), where \(x_0=\frac{36\pi}{127}\).

Logarithmic (by h) graph of the quotient (f(x0)-f(x0-h))/h. Horizontal axis is h.
Graph of a quotient with the bigger scale makes it more obvious:
Logarithmic (by x) graph of the same quotient (f(x0)-f(x0-h))/h, bigger scale.
As it can be seen from the graphs, at the certain point h between \(10^{-29}\) and \(10^{-28}\) the quotient becomes negative, which means that there exists such h, that \(f(x_0+h) > f(x_0)\). Apparently, the extremal value is h≈1.998e-29, giving \(f(x_0+h) - f(x_0) \approx 3.06\dot10^{-32}\).
f(x0)=1.329833276287310850440418286206506387707650784...
f(x0-1.998e-29)=1.329833276287310850440418286206535446963412182...
An important note about this calculation: the usual IEEE double accuracy (53 bits, about 16 decimal digits) is insufficient, and long doubles must to be used to obtain the result. For the above calculation I used 1000-bit long floating point values having roughly roughly 300 decimal digits. This, I believe, makes the numeric results trustworthy enough.
There is still a possibility that the maximum is reached at some rational multiple of π, but it never be as simple, as 36π/127. I feel a strange mix of frustration and enlightenment regarding this failure, the result seems absolutely counter-intuitive for me. Why \(x_0/\pi\) is so incredibly close to the rational value? Is it just a fantastic coincidence, or a consequence of a some deeper facts?
This result strongly resembles the "Almost Integer" values in mathematics. it can be re-formulated in the following way:
$$ N = \frac{127}\pi \mathrm{argmin} \sum_{i=0}^\infty \frac{sin(2^i x)}{2^i} = 36+\epsilon $$ where \( \left| \epsilon \right| < 10^{-27} \). I.e. N is an almost integer value.

Sunday, January 18, 2009

Billiard balls and fractals

Virtually any non-stable dynamic system may be used for generating of fractal images. Here is one example, based on ideal planar billiards.
Consider ideal billiard, consisting of round balls, moving and colliding without friction in the rectangular box.
Then let us measure, how much time needs first ball (green one at the picture) to get to the right wall. Below are the images, showing how time until wall collision depends from initial ball velocity. Horizontal and vertical coordinates at the picture plane correspond horizontal and vertical components of the initial ball velocity, color shows, how much time needed ball to reach the right wall. All pictures are 800x600, about 600K

The top-level view of the fractal

Slightly zoomed
High zoom with different color map
Another highly zoomed image


Increased number of balls. Image became more chaotic. Also, different color map chosen.

Tuesday, January 6, 2009

The 36π/127 conjecture

Update: the conjecture is apparently wrong.
There is a problem that bothers me for a long time. Consider function f(x), defined in the following way:
$$f(x) = \sum_{n=0}^\infty \frac{sin(2^n x)}{2^n}.$$
Obviously, this sum converges for every real x; and for every x, -2 < f(x) < 2; and f(x) is continuous (due to the uniform convergence of partial sums).
The special thing about f(x) is that it has no derivatives. It may be easily seen from it's graph:
Red graph denotes f(x), gray lines are sin(2nx)/2n.
The red line in the graph is f(x), is obviously a fractal. Using box-counting approach, it's dimension may be approximated as 1.03, though this value tends to decrease, when minimal box size is decreased.
Using numeric methods, I have found that f(x) achieves it's maximal value at point xmax = 0.8905302... (dash line at the graph above) which effectively equals to \(x_0=\frac{36}{127}\pi\). I am looking for the proof of this fact, but without success.
Following plot may give a key to the solution. It is a logarithmic graph, showing how the function behaves in the close vicinity of the point \(x_0\).
Graph of the f(x) in the vicinity of the point x0.
The notable feature of this graph is its periodicity. At other points, f(x) have more complex behavior:

Periodical structure appears only if x is a rational fraction of \(\pi\). For other values, graph shows chaotic structure: