This article is cited in
31 papers
On linguistic dynamical systems, families of graphs of large girth, and
cryptography
V. A. Ustimenkoab a Universidade de São Paulo, Instituto de Matemática e Estatística
b National University of Kiev-Mohyla Academy
Abstract:
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$.
UDC:
519.17,
519.729 Received: 15.04.2005
Language: English