RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2005 Volume 326, Pages 214–234 (Mi znsl344)

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


 English version:
Journal of Mathematical Sciences (New York), 2007, 140:3, 461–471

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024