On new measures of pseudorandomness of binary lattices
type: Item
instance of: scholarly article
title: On new measures of pseudorandomness of binary lattices
zbMATH Open document ID: 1240.11082
author: Katalin Gyarmati
published in: Acta Mathematica Hungarica
publication date: 2011-12-19T00:00:00Z
review text: 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.
reviewed by: Arne Winterhof
Mathematics Subject Classification ID: 11K45
zbMATH DE Number: 5990615
zbMATH Keywords: pseudorandomness
zbMATH Keywords: binary lattices
zbMATH Keywords: line measure
zbMATH Keywords: convex measure
MaRDI profile type: Publication
full work available at URL: s10474-010-0041-7
OpenAlex ID: W2169807031
cites work: Measures of Pseudorandomness for Finite Sequences: Minimal Values
cites work: Measures of pseudorandomness for finite sequences: typical values
cites work: On finite pseudorandom binary sequences VII: The measures of pseudorandomness
cites work: On a pseudorandom property of binary sequences
cites work: Q3184618
cites work: On pseudorandom binary lattices
cites work: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
cites work: Q5794285
DOI: 10.1007/S10474-010-0041-7
description: scientific article; zbMATH DE number 5990615