On linguistic dynamical systems, families of graphs of large girth, and

V. A. Ustimenko

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XIII, Tome 326 (2005), pp. 214-234

Résumé

The paper is devoted to the study of a linguistic dynamical system of dimension $n\ge 2$ over arbitrary commutative ring $K$, i.e. a family $F$ of nonlinear polynomial maps $f_\alpha\colon K^n\to K^n$ depending on “time” $\alpha\in\{K-0\}$ such that $f_\alpha^{-1}=f_{-\alpha}$, $f_{\alpha_1}(x)=f_{\alpha_2}(x)$ for some $x\in K^n$ implies $\alpha_1=\alpha_2$, and each map $f_\alpha$ has no invariant points. The neighbourhood $\{f_\alpha(v)|\alpha\in K-\{0\}\}$ of an element $v$ defines the graph $\Gamma(F)$ of a dynamical system on the vertex set $K^n$. We shall refer to $F$ as a linguistic dynamical system of rank $d\ge 1$ if for each string $\mathrm{a}=(\alpha_1,\dots,\alpha_s)$, $s\le d$, where $\alpha_i+\alpha_{i+1}$ is a nonzero divisor for $i=1,\dots,d-1$, the vertices $v$ and $v_{\mathrm{a}}=f_{\alpha_1}\times\dots\times f_{\alpha_s}(v)$ in the graph are connected by a unique pass. For each commutative ring $K$ and even integer number $n\ne 0$ mod 3 there is a family of linguistic dynamical systems $L_n(K)$ of rank $d\ge 1/3n$. Let $L(n, K)$ be the graph of a dynamical system $L_n(q)$. If $K=F_q$, the graphs $L(n, F_q)$ form a new family of graphs of large girth. The projective limit $L(K)$ of $L(n,K)$, $n\to\infty$, is well defined for each commutative ring $K$, in the case of integral domain $K$ the graph $L(K)$ is a forest. If $K$ has zero divisors, then the girth of $K$ is dropping to 4. We introduce some other families of graphs of large girth related to the dynamical systems $L_n(q)$ in the case of even $q$. The dynamical systems and related graphs can be used for the development of symmetric or asymmetric cryptographical algorithms. These graphs allow us establish the best known upper bounds on the minimal order of regular graphs without cycles of length $4n$, with $n$ odd $\ge 3$.