29

Let $G := \langle a, b, c \rangle < {\rm Sym}(\mathbb{Z}^2)$ be the group generated by the permutation $$ a: \ (m,n) \ \mapsto \ (m-n,m) $$ of order $6$ and the involutions $$ b: \ (m,n) \ \mapsto \ \begin{cases} (m,2n+1) & \text{if} \ n \equiv 0(\text{mod} \ 2), \\ (m,(n-1)/2) & \text{if} \ n \equiv 1(\text{mod} \ 4), \\ (m,n) & \text{if} \ n \equiv 3(\text{mod} \ 4) \\ \end{cases} $$ and $$ c: \ (m,n) \ \mapsto \ \begin{cases} (m,2n+3) & \text{if} \ n \equiv 0(\text{mod} \ 2), \\ (m,(n-3)/2) & \text{if} \ n \equiv 3(\text{mod} \ 4), \\ (m,n) & \text{if} \ n \equiv 1(\text{mod} \ 4). \\ \end{cases} $$ Drawing spheres of radius $r$ about $(0,0)$ for "large enough" $r$ reveals fractal-like structures.

Added on July 28, 2014: A video showing more pictures is now available on YouTube here. The video starts with a sequence showing entire spheres of small radii, i.e. from $r = 8$ to $r = 24$, and continues with pictures showing smaller parts of spheres of larger radii up to $r = 45$. Monochrome pictures show only one sphere, respectively, a part thereof; colored pictures show multiple spheres in different colors.

Added on March 16, 2014: Pictures of the spheres of radius $30$ and $36$ can be downloaded here:

Radius 30 (3487 x 3079 pixels, 111KB), Radius 36 (10375 x 9103 pixels, 693KB).

Sample snippets of the large -- about $200$ megapixels at $r = 38$ to about $3$ gigapixels at $r = 45$ -- pictures are (black pixel = belongs to sphere, white pixel = doesn't belong to sphere):

A part of the sphere of radius 40 about (0,0) under the action of G

A part of the sphere of radius 38 about (0,0) under the action of G

A part of the sphere of radius 45 about (0,0) under the action of G

A part of the sphere of radius 45 about (0,0) under the action of G

A part of the sphere of radius 40 about (0,0) under the action of G

A part of the sphere of radius 45 about (0,0) under the action of G

A part of the sphere of radius 45 about (0,0) under the action of G

A part of the sphere of radius 45 about (0,0) under the action of G

The images above show parts of the spheres of radius $38$, $40$ and $45$.

Question: How can the observed patterns be explained?

Remark 1: The cardinalities of the spheres of radii $r = 0, \dots, 45$ about $(0,0)$ are

1, 2, 4, 8, 14, 26, 39, 68, 114, 188, 289, 404, 560, 827, 1341, 2052, 3158, 4540, 
6091, 8630, 12241, 17739, 27727, 41846, 61234, 86647, 117806, 163795, 233939, 340659, 
523862, 768739, 1110855, 1569204, 2148377, 2994661, 4287462, 6195498, 9389566, 
13568954, 19542862, 27619364, 38048372, 53304607, 76433012, 109839303.

The entire sphere of radius $20$ looks as follows (the overall shape of the larger spheres is roughly similar):

The entire sphere of radius 20 about (0,0) under the action of G

Added: At a scale of about $1:100$, the entire sphere of radius $45$ looks as follows:

The entire sphere of radius 45 about (0,0) under the action of G, at a scale of about 1:100

Remark 2: In the notation of this and this question, $b$ and $c$ induce on the second coordinate the class transpositions $\tau_{0(2),1(4)}$ and $\tau_{0(2),3(4)}$, respectively. Further, in the notation of (1) and (2) we have $G < {\rm RCWA}(\mathbb{Z}^2)$.

Community
  • 1
Stefan Kohl
  • 19,498
  • 21
  • 73
  • 136
  • 1
    Hm, what do you mean by the sphere here? You are looking at the forward orbit of (0,0) under all maps, are you not? – Per Alexandersson Mar 11 '14 at 20:00
  • @PerAlexandersson: see my comment below your answer. – Stefan Kohl Mar 11 '14 at 20:36
  • 2
    This is a wonderful question! – Noah Schweber Mar 12 '14 at 02:48
  • 3
    Why don't you put the tags ds.dynamical-systems and fractals ? Experts of these subjects could help you (there are others fractal-like phenomenons on discrete strutures, for example the Rauzy fractals). – Sebastien Palcoux Mar 12 '14 at 12:51
  • 1
    Besides the fractal structure, the spheres look like to an explosion, I had never seen such pattern in pure mathematics. I don't know if there is something to say mathematically about that, perhaps such group actions appear in a discrete modelling of physical explosions. – Sebastien Palcoux Mar 14 '14 at 18:45
  • 2
    What beautiful pictures! An animation showing successively all the spheres from radius 0 to radius 45 would be interesting too: one animation with a fixed scale, and one with a renormalized scale. Do you observe that the shape of the spheres (at renormalized scale) "converge" to a (unique) fractal shape (I hope my question is understandable) ? – Sebastien Palcoux Mar 17 '14 at 11:31
  • this appears to be a case of what are known by some as "collatz like functions". eg sec 1.4 & others of new/recent paper Problems in number theory from busy beaver competition by Michel. basically these problems are difficult to study & lie at the boundary of decidable and undecidable & are an open/active area of research. – vzn Apr 15 '14 at 18:16

2 Answers2

11

This phenomenon can be understood as follows:

Let $\Gamma < Sym(\mathbb{Z}^{2})$ be a transitive hyperbolic group (and non virtually cyclic).

Through this faithful transitive action of $\Gamma$ on $\mathbb{Z}^{2}$ (and orbit of (0,0)), the Cayley graph of $\Gamma$ (Gromov hyperbolic geometry) is projected (in a manner not too degenerate) on $\mathbb{Z}^2$ (euclidean geometry).
Then the emergence of explosive and fractal-like structures on the spheres is not surprising.

So any (non virtually cyclic) hyperbolic group would generate beautiful fractal-like pictures.

Example: $\Gamma = \langle a,b \rangle < Sym(\mathbb{Z}^{2})$ such that

  • $a: (m,n) \to (m+1,m+n)$
  • $b: (m,n) \to (m+n,n+1)$

To be confirmed: $\Gamma$ acts transitively on $\mathbb{Z}^{2}$.
Remark: $\Gamma$ is neither free nor hyperbolic nor torsion-free (see the comments below).

The cardinalities of the spheres of radii $r=0,\dots,14$ about $(0,0)$ are :
$1,4,11,20,47,100,238,512,1124,2540,5569,12101,26208,56720,122600$

The entire sphere of radius $14$: enter image description here

The entire ball of radius $14$ with a rainbow gradient according to the spheres: enter image description here

Remark: I don't know if your group $G$ is hyperbolic, but we could have the same understanding for all the finitely generated groups of exponential growth.

Sebastien Palcoux
  • 25,922
  • 2
    Nice picture! -- In fact, there are many diffferent possibilities how these pictures may look like for a particular group -- for some groups one just gets more-or-less random-looking ring-shaped pixel clouds, for others one gets various geometric patterns with varying complexity, and for some groups one observes fractal-like patterns like for the group my question is about. Some much simpler examples are shown here: http://www.gap-system.org/DevelopersPages/StefanKohl/rcwa/pictures.html – Stefan Kohl Mar 18 '14 at 00:02
  • @StefanKohl: I guess this action of $\mathbb{F}_2$ reveals also fractal-like structures, but I can't (yet) compute a sphere of radius large enough for seeing them. – Sebastien Palcoux Mar 18 '14 at 14:08
  • 2
    @StefanKohl: These pictures are not defined as a non-escaping set of a complex function (because the group acts transitively...), nevertheless I ask myself if there is a way to define a transformation such that its non-escaping set is exactly the renormalized limit of the spheres. What do you think? Also, by taking $\Gamma<Sym(\mathbb{Z}^3)$ (non virtually cyclic) transitive hyperbolic, one should obtain nice 3D fractals! There is an expert in mathematical imagery: Jos Leys, he often works with Etienne Ghys. – Sebastien Palcoux Mar 18 '14 at 16:45
  • 1
    The spheres in your action of $\mathbb{F}_2$ on $\mathbb{Z}^2$ are all star-shaped, with the star getting finer and finer as the radius grows, as far as I can tell. -- I have computed the spheres up to radius 18, see here. In particular the images are much different than those for the group my question is about. – Stefan Kohl Mar 18 '14 at 23:41
  • 1
    As to "renormalized limit" of the spheres: I don't know for which groups and in which precise sense such limits do exist. In any case I think one needs to be careful with the definitions here, otherwise one might easily get something unintuitive like the empty picture or a single point as the limit. As to $\Gamma < {\rm Sym}(\mathbb{Z}^3)$: yes, this would be interesting -- but good visualization in 3 dimensions (and high resolution!) is not so easy. – Stefan Kohl Mar 18 '14 at 23:56
  • 1
    @StefanKohl: One should better see the global fractal structure of these entire spheres by applying a logarithmic contraction (for offsetting the explosive deformation). – Sebastien Palcoux Mar 19 '14 at 01:16
  • @StefanKohl: I think a reason why the spheres for this action of $\mathbb{F}_2$ give more and more fine structures is that the total space of $\mathbb{F}_2$ (its Cayley graph) is topological dimension $1$. One should obtain "thicker" spheres with (non-virtually cyclic) torsion-free hyperbolic groups whose total space is $n$-dim. with $n>1$, for example the surface group $\Gamma_2=\langle a_1,b_1,a_2,b_2 \vert [a_1,b_1][a_2,b_2]=e \rangle$ (is there a relevant injection of $\Gamma_2$ into $Sym(\mathbb{Z}^2)$?). – Sebastien Palcoux Mar 19 '14 at 01:23
  • @StefanKohl: Thank you for the computation of the spheres of my example up to radius $18$. I am not convinced that "local" fractal-like structures (as for your example) will not appear for higher radii, because they are not yet revealed for your own example at radius even $20$. So the spheres of my example should be computed up to radius $30$ or $35$ for forming an opinion. The problem is that the cardinality of the spheres of my example increases much much faster, so perhaps they can't be computed at radius $35$ in a reasonable time, with a normal computer. – Sebastien Palcoux Mar 20 '14 at 00:39
  • 3
    This one vaguely resembles the s. c. "Farey sunbursts" obtained by joining consecutive $(m,n)$s corresponding to the $m/n$s in the Farey sequence... – მამუკა ჯიბლაძე Mar 21 '14 at 11:00
  • 3
    In fact this particular group is not free: for example, $$ ba^{-1}bab^{-1}a(m,n)=a^{-1}bab^{-1}ab(m,n)=(m+2,n). $$ Still most likely it is hyperbolic... – მამუკა ჯიბლაძე Mar 21 '14 at 17:26
  • @მამუკაჯიბლაძე: Very nice! So the topological dimension of the total space of $\Gamma$ is at least $2$. – Sebastien Palcoux Mar 21 '14 at 18:14
  • 1
    @მამუკაჯიბლაძე: Indeed. -- The sizes of the spheres of radii $0, \dots, 8$ about the identity in this group are $1, 4, 12, 36, 108, 324, 944, 2716, 7619$, which shows a deviation from the free group starting from radius $r = 6$ (by $28$ at $r = 6$, by $200$ at $r = 7$ and by $1129$ at $r = 8$). In particular the relation you give is shortest possible. – Stefan Kohl Mar 21 '14 at 18:31
  • 1
    @SébastienPalcoux: I think in your example you may be able to find a way to compute small parts of larger spheres separately -- what is needed for this is to know a computationally easy way to find the shortest path from a given point to $(0,0)$. -- Since your example doesn't involve divisions, this looks feasible (though I haven't tried). However I think having mere affine mappings as generators significantly limits the complexity of the structure of the images (though I don't know how and to what extent). – Stefan Kohl Mar 21 '14 at 20:52
  • 1
    I don't know whether this is useful but your group also has some torsion: e. g. $$ b^2a^{-1}b^{-1}ab^{-2}a(m,n)=(m-n,m) $$ has order 6. – მამუკა ჯიბლაძე Mar 21 '14 at 21:00
  • 1
    @მამუკაჯიბლაძე: This happens to be the first generator of my example. – Stefan Kohl Mar 21 '14 at 21:19
  • 2
    @მამუკაჯიბლაძე: By your first comment, the element $g_1:(m,n) \to (m+2,n)$ is in $\Gamma$. By symmetry, $g_2:(m,n) \to (m,n+2)$ is also in $\Gamma$. But $\langle g_1 , g_2 \rangle \simeq \mathbb{Z}^2$. Then $\mathbb{Z}^2$ is a subgroup of $\Gamma$, and so $\Gamma$ is not hyperbolic. But $\mathbb{Z}^2 \triangleleft \Gamma$, so perhaps $\Gamma / \mathbb{Z}^2$ is hyperbolic. – Sebastien Palcoux Mar 21 '14 at 23:26
  • Oh yes you are right of course. That's interesting. The action of the quotient $\Gamma/\mathbb Z^2$ on the torus $(\mathbb R/2\mathbb Z)^2$ has an orbit ${(0,0),(1,0),(0,1),(1,1)}$ on which it acts as the full symmetric group; the stabilizer contains ($\mathbb Z^2$-residue classes of) things like $a^4$, $aba(bab)^{-1}$, etc. If it is torsion free, the picture might be completely clarified. – მამუკა ჯიბლაძე Mar 22 '14 at 06:39
  • On the afterthought though, that stabilizer still has some torsion - e. g. the cube of the above order 6 element – მამუკა ჯიბლაძე Mar 22 '14 at 06:48
3

This is just a partial answer, but it looks like your figures are not "pure" fractals, but a union of different fractals (with different fractal dimensions). If I am not mistaken, these are called multi-fractals.

It looks like part of your figure is the Dragon curve fractal.

This particular fractal is space-filling, so it would not surprise me if your set is actually everything, (unless I have misinterpreted something).

Also, your dynamics looks a lot like some two-dimensional version of the iterations of something similar to the Collatz conjecture, which give rise to a fractal behaviour. Look at the corresponding wikipedia page, there is an analytic continuation of the functions that are iterated, and I think something similar can be done in your case.

Ok, so you can make a continuous version of your map $b$: Let $s(n)=\frac12 \sin\frac{\pi n}{2} (1 + \sin \frac{\pi n}{2})$. Note that $s(n)$ is periodic, with period 4: $1,0,0,0,1,0,\dots$.

Now, we can define $b(m,n)$ as

$$ b(m,n)= \left(m, (2 n + 1) (s[n + 1] + s[n + 3]) + s[n + 2]n + s[n] (n - 1)/2 \right) $$ and this is now a continuous extension of your map, seen as a map on $\mathbb{R}^2$. You can do a similar thing with the other maps.

Now it might be easier to draw this, for example, this is exactly the kind of maps that the most common fractal drawing software works with. What you have is a Hutchinson operator, so check wikipedia again.

Per Alexandersson
  • 15,598