Robert Tichy: Equidistribution and Pseudorandomness

Abstract:

In 1997 C. Mauduit and A. Sarkő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\) 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.