$D$-dimensional cellular automata provide Salem's singular function $L_{\alpha }$ with $\alpha =1/(2D+1)$ and $1/(2^D+1)$

Abstract

Salem's singular function is strictly increasing, continuous, and has a derivative equal to zero almost everywhere in $[0,1]$; it is also known as de Rham's singular function or Lebesgue's singular function. The parameter of Salem's singular function $L_{\alpha }$ is $\alpha \in (0,1)$ and $\alpha \ne 1/2$. Our previous studies have shown that for some cases of which the limit set of spatio-temporal pattern of a cellular automaton (CA) is fractal, Salem's singular function with $\alpha =1/3$, $1/4$, or $1/5$ is given by projecting the pattern onto the time axis. However, it remained unclear whether there exists a CA that gives Salem's singular function with a parameter $\alpha$ equal to the multiplicative inverse of an integer greater than $5$. In this paper, we construct CAs giving Salem's singular function with $\alpha =1/(2D+1)$ and $\alpha =1/(2^D+1)$ for each dimension $D\ge 1$. This implies that there exist CAs that give Salem's function with a parameter $\alpha$ equal to the multiplicative inverse of any integer greater than or equal to $3$. We also present the results of numerical experiments showing that for $D\le 5$, the functions given by $D$-dimensional linear symmetric $2$-state radius-$1$ CAs other than the above two types cannot be Salem's function with $\alpha =1/M$ for $M\in {\mathbb{Z}}_{\ge 3}$. In addition to the square lattice, the triangular and hexagonal lattices can be considered as regular lattices in the two-dimensional plane, and we also discuss functions obtained from CAs on these lattices.

21 pages