On the correlation measures of subsets (Q2189560)

The paper deals with subsets \(\mathcal{R}\) of \(\{1,2,\dots,N\}\), and measures of pseudorandomness for these. For such an \(\mathcal{R}\), define the function \[ f_{\mathcal{R}}(n):=\begin{cases} 1-\left|\mathcal{R}\right|/N & \text{ if }n\in\mathcal{R},\\ -\left|\mathcal{R}\right|/N & \text{ otherwise.} \end{cases} \] Then, the correlation measure of order \(k\) of \(\mathcal{R}\subset \{1,2,\dots,N\}\) is defined as \[ C_k (\mathcal{R},N)=\max_{M,D} \left|\sum_{n=1}^M f_{\mathcal{R}} (n+d_1) \cdots f_{\mathcal{R}}(n+d_k)\right|, \] where the maximum is considered over all (ordered nonnegative) \(k\)-tuples \(D=(d_1,\dots,d_k)\) and all \(M\) with \(0\leq d_1 <\cdots < d_k\leq N-M\). If \(C_k (\mathcal{R},N)\) is small in terms of \(N\) (as the authors point out, an order of magnitude close to \(\sqrt{N}\) is desirable), then this can be interpreted as an indication that \(\mathcal{R}\) is pseudorandom. In the paper, the authors study the minimal values of the correlation measures \(C_k\), and give lower and upper bounds for various instances of choices of \(k\).