Theoretical Foundations of Applied Discrete Mathematics

Some periodic and statistical properties of piecewise polynomial sequences over primary residue rings

A. R. Vasin, T. I. Lipina


Abstract: We study periodic and statistical properties of piecewise polynomial sequences (PP-sequences) over the primary residue ring $R=\mathbb{Z}_{p^n}$ modulo $p^n$. For an element $x \in R$ in the form $x = p^l \hat x$, $\hat x \in R^*$, $0 \le l \le n$, and a polynomial $F(x) = f_0 + f_1 x + \ldots + f_d x^d \in R[x]$ define a piecewise polynomial function $\phi_F \colon R\to R$ as $\phi_F(x) = \phi_F(p^l\hat{x}) = f_0 + p^l(f_1 \hat x + \ldots+ f_d \hat x^d)$, and a PP-sequence as $x_0,x_1 = \phi_F(x_0),\ldots,x_{m+1} = \phi_F(x_m),\ldots$ for some $x_0 \in R$. In the binary case $p=2$, we obtain a criterion for the transitivity of piecewise polynomial transformations in terms of the generating polynomial coefficients: a PP-function $\phi_F$ is transitive over $\mathbb{Z}_{2^n}$ for any $n \ge 1$, if and only if
$$f_0 \equiv 1 \pmod 2,\ f_1+f_3+\ldots+f_{d'} \equiv 1 \pmod 4,\ f_2+f_4+\ldots+f_{2\lfloor d/2 \rfloor} \equiv 0 \pmod 4,$$
where $d' = d$ if $d$ is odd, and $d'=d-1$ otherwise. For $p>2$, we derive nontrivial bounds for the discrepancy of normalized PP-sequence segments. Let $\{x_i\}_{i=0}^\infty$ be a PP-sequence of period $q$ over $R=\mathbb{Z}_{q}$, where $q = p^n$, $p > 2$, consider the sequence $P = \{y_i\}_{i=0}^\infty \in [0,1)^\infty$, where $y_i = x_i / q$. Let $V(R) = \dfrac{4}{\pi^2} n\ln p + \dfrac{4}{5}$. For $d \ge 2$, $(d,p)=1$, $1 \le l \le q$, the discrepancy $D_l$ of $P$ is bounded as
$$D_l(P) < 1/q + 3 V(R) p^{-1/(2s)} l^{-1/2} q^{1/2}, \text{where }s=d^{\sqrt{3p/2}+1}.$$
Also, we derive nontrivial estimates for the autocorrelation coefficients of PP-sequence segments of length $p^n$. Consider the autocorrelation coefficients $A_{\phi_F}(l,s,g)$ of a PP-sequence $\{x_i\}_{i=0}^\infty$ of period $q$ over $R=\mathbb{Z}_{q}$, $q=p^n$, $p>2$, which are defined as $A_{\phi_F}(l,s,g) = \sum\limits_{i=0}^{l-1} e^{2 \pi i g (x_i - x_{i+s})/q}$. For $d \ge 2$, $(d,p)=1$, and $h = q/(q, g)$, we have
$$|A_{\phi_F}(q,s,g)| < 4{,}41 h^{- 1/d^s}q + 2sp^{-1}q.$$


Keywords: piecewise polynomial sequences, transitivity, discrepancy, autocorrelation coefficients.

UDC: 512.547+519.714

DOI: 10.17223/2226308X/18/4