On new measures of pseudorandomness of binary lattices
For positive integers \(n\) and \(N\) an \(n\)-dimensional binary \(N\)-lattice \(\eta\) is a mapping from \(\{0,1,\ldots,N-1\}^n\) to \(\{-1,+1\}\). \textit{P. Hubert}, \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith.\ 125, No. ~1, 51--62 (2006; Zbl 1155.11044)] introduced the pseudorandom measure \(Q_\ell(\eta)\) of order \(\ell\) of \(\eta\) by \[ Q_\ell(\eta)=\max_{B,{\boldsymbol d}_1,\ldots,{\boldsymbol d}_\ell}\left| \sum_{{\boldsymbol x}\in B} \eta({\boldsymbol x}+{\boldsymbol d}_1)\cdots\eta({\boldsymbol x}+{\boldsymbol d}_\ell)\right| , \] where the maximum is taken over all distinct \({\boldsymbol d}_1,\ldots,{\boldsymbol d}_\ell\in \{0,1,\ldots,N-1\}^n\) and boxes \(B=\{x_1z_1{\boldsymbol e}_1+\ldots+x_nz_n{\boldsymbol e}_n : 0\leq x_iz_i\leq t_i<N,~i=1,\ldots,n\}\) with \({\boldsymbol e}_j=(0\ldots 1 \ldots 0)\) the \(j\)th unit vector and \(z_j\) a positive integer such that \(B+{\boldsymbol d}_1,\ldots,B+{\boldsymbol d}_\ell \subseteq \{0,1,\ldots,N-1\}^n\). The author introduces two new measures of pseudorandomness for binary lattices, the convex measure \(X_\ell(\eta)\) and the line measure \(L_\ell(\eta)\) of order \(\ell\) defined similarly but where the maximum is taken over all \({\boldsymbol x}\in K\cap \{0,1,\ldots,N-1\}^n\), where \(K\subseteq [0,N-1]^n\) is convex, and \({\boldsymbol x}\in L\), where \(L\) is of the form \(L=\{(a_1t+b_1,\ldots,a_nt+b_n) : t=0,1,\ldots,M-1\}\), respectively. She proves the relations \[ X_\ell(\eta)\leq N^{n-1}L_\ell(\eta) \] and \[ Q_\ell(\eta)\leq N^{n-1}L_\ell(\eta). \] Moreover, she shows that the line measure of a typical \(N\)-lattice is (up to a logarithmic factor and a constant depending on \(\ell\)) of order of magnitude \(N^{1/2}\). Finally, she gives an example of a lattice defined with Legendre symbols for which the linear measure has such an order of magnitude.
scientific article; zbMATH DE number 5990615