Robert Tichy: Equidistribution and Pseudorandomness

Speaker
Robert Tichy, TU Graz

Abstract
In 1997 C. Mauduit and A. Sark\H{o}zy [Acta Arith vol. 82] introduced various measures for pseudo randomness of binary sequences over \(\{-1, +1\}\). In this talk the focus lies on the correlation measure of order \(s\). Let \(E_{N}=\{e_{1},\ldots, e_{N}\}\) be a finite binary sequence, \(M\) a positive integer and \(\underline{d}= (d_{1}\ldots, d_{s})\in \mathbb{N}^{s}\) a correlation vector such that \(O \leq d_{1} < d_{2} < \ldots < d_{s} \leq N - M\). We set \begin{equation} V (E_{N},M,\underline{d})= \sum^{M}_{n=1}e_{n+d_{1}}e_{n+d_{2}}\ldots e_{n+d_{s}}. \end{equation} Then the correlation measure of order \(s\) of \(E_{N}\) is defined as \begin{equation} C_{s}(E_{N})= \max_{M,\underline{d}}\mid V (E_{N}, M, \underline{d})\mid. \end{equation} We construct binary sequences from certain functions \(f(x)\) of polynomial growth by \(e_{n}= \chi (f(n)),\) where \begin{equation} \chi(x)= \begin{cases}+1\; \text{for} & 0 \leq \{x\} < \frac{1}{2}\\ -1\; \text{for} & \frac{1}{2}\leq \{x\} < 1\end{cases}, \end{equation} where \(\{\cdot\}\) denotes the fractional part. The approach works for functions \(f(x)= x^{c}\) \((c > 1\; \text{not an integer})\) and for Hardy fields as introduced by Boshernitzan (1994) to equidistribution theory. The main result is an estimate of the form \(C_{s}(E_{N})\ll N^{1-\eta}\) for some positive constant \(\eta\). In contrary, we have for \(f(x) = x^{c}\) with \(0< c < 1\) \begin{equation} C_{2}(E_{N})\gg N, \end{equation} whereas such sequences are still uniformly distributed modulo 1. The method is based on van der Corput like estimates of exponential sums. I will also give an overview on measures of pseudorandomness and want to address possible connections to pair correlations as considered by Z. Rudnick, P. Sarnak and followers.