The author gives a large family of pseudorandom binary sequences constructed by using the multiplicative inverse.
We have to start with some notation. For a pseudorandom binary sequence \[ E_N=(e_1,\ldots,e_N)\in\{-1,+1\}^N, \] the well-distribution measure of \(E_N\) is defined by \[ W(E_N)=\max_{a,b,t}|\sum_{j=0}^{t-1}e_{a+jb}|, \] where \(a,b,t\in\mathbb{N}\) with \(1\leq a\leq a+(t-1)b\leq N.\) The correlation measure of order \(\ell\) of \(E_N\) is defined as \[ C_\ell(E_N)=\max_{M,D}|\sum_{n=1}^Me_{n+d_1}\cdots e_{n+d_\ell}|, \] where \(d=(d_1,\ldots,d_\ell)\) and \(0\leq d_1<\ldots<d_\ell\leq N-M.\)
The first main result is the following theorem (Theorem 1.1). Suppose that \(p\) is a prime and \(f(x)\in\mathbb F_p[x]\) has degree \(k\) with \(0<k<p.\) Denote by \(R_p(n)\) the least non-negative residue of \(n\) modulo \(p,\) and for \((a,p)=1,\) denote by \(a^{-1}\) the multiplicative inverse of \(a\) satisfying \(aa^{-1}\equiv 1\mod p\) and \(1\leq a^{-1}\leq p-1.\) Define the binary sequence \(E_p=(e_1,\ldots,e_p)\) by \[ e_n= +1\text{ if }(f(n),p)=1,\; R_p(f(n)^{-1})<p/ 2, \] and \[ e_n=-1\text{ if either }(f(n),p)=1\text{ and }R_p(f(n)^{-1})>p/ 2,\text{ or }p|f(n). \] Then \[ W(E_p)\ll kp^{1/ 2}(\log p)^2. \] If \(0\) is the unique zero of \(f\) in \(\mathbb F_p\) then also \[ C_\ell(E_p)\ll k\ell p^{1/ 2}(\log p)^{\ell+1}. \]
The second main result gives the construction of \(n\)-dimensional binary \(N\)-lattice, i.e., the function \(\eta:I_N^n\to\{-1,+1\},\) where \(I_N^n=\{(x_1,\ldots,x_n):x_j\in\{0,1,\ldots,N-1\}\}\) with small pseudorandom measure of order \(k.\) The precise statement is given in Theorem 1.2.