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

Статья посвящена изучению лингвистических динамических систем размерности $n\ge 2$ над произвольным коммутативным кольцом $K$, т.е. семейство $F$ нелинейных полиномиальных отображений $f_\alpha\colon K^n\to K^n$, зависящих от “времени” $\alpha\in\{K-0\}$, таких что $f_\alpha^{-1}=f_{-\alpha}$ and $f_{\alpha_1}(x)=f_{\alpha_2}(x)$ для некоторых $x\in K^n$ implies $\alpha_1=\alpha_2$, причем каждое отображение $f_\alpha$ не имеет инвариантных точек.
Окрестность $\{f_\alpha(v)|\alpha\in K-\{0\}\}$ элемента $v$ определяет граф $\Gamma(F)$ динамической системы на множестве вершин $K^n$.
Мы будем называть $F$ лингвистической динамической системой ранга $d\ge 1$, если для каждой строки $\mathrm{a}=(\alpha_1,\dots,\alpha_s)$, $s\le d$, где $\alpha_i+\alpha_{i+1}$ – ненулевой дивизор для $i=1,\dots,d-1$, вершины $v$ и $v_{\mathrm{a}}=f_{\alpha_1}\times\dots\times f_{\alpha_s}(v)$ графа соединимы единственным путем.
Для каждого коммутативного кольца $K$ и четного целого $n\ne 0$ mod 3 существует семейство лингвистических динамических систем $L_n(K)$ ранга $d\ge 1/3n$. Пусть $L(n, K)$ – граф динамической системы $L_n(q)$.
Если $K=F_q$, графы $L(n,F_q)$ образуют семейство графов большого обхвата. Проективный предел $L(K)$ графов $L(n,K)$, $n\to\infty$, определен для каждого коммутативного кольца $K$. Если $K$ – область целостности, то граф $L(K)$ является деревом, если $K$ имеет делители нуля, то обхват $K$ падает до 4.
Мы вводим в рассмотрение некоторые другие семейства графов большого обхвата, связанных с динамическими системами $L_n(q)$ в случае четного $q$. Динамические системы и связанные с ними графы можно использовать для разработки симметричных или асимметричных криптографических алгоритмов. Эти графы позволяют наилучшие из известных верхние границы для минимального порядка регулярных графов без циклов длины $4n$, $n\ge 3$. Библ. – 42 назв.