Construction of pseudorandom binary lattices by using the multiplicative inverse (Q2482218): Difference between revisions

For positive integers \(N\) and \(n\) a function \[ \eta:\{0,1,\dots,N-1\}^n \rightarrow \{-1,+1\} \] is called an \(n\)-dimensional binary \(N\)-lattice. \textit{P. Hubert} and the authors [On pseudorandom binary lattices. Acta Arith. 125, No. 1, 51--62 (2006; Zbl 1155.11044)] introduced the pseudorandom measure \(Q_k(\eta)\) of order \(k\): \[ \begin{multlined} Q_k(\eta)=\max_{{\mathbf b},{\mathbf d}_1,\dots,{\mathbf d}_k,{\mathbf t}} \biggl| \sum_{j_1=0}^{t_1}\dots \sum_{j_n=0}^{t_n} \eta(j_1b_1{\mathbf u}_1+\dots +j_nb_n{\mathbf u}_n+{\mathbf d}_1)\\ \cdots \eta(j_1b_1{\mathbf u}_1+\dots+j_nb_n{\mathbf u}_n+{\mathbf d}_k)\biggr|,\end{multlined} \] where \({\mathbf u}_i\), \(i=1,\dots,n\), denotes the \(n\)-dimensional unit vector with \(i\)th coordinate \(1\) and all other coordinates \(0\) and the maximum is taken over all \(n\)-dimensional vectors \({\mathbf b}=(b_1,\dots,b_n)\), \({\mathbf d}_1,\dots,{\mathbf d}_k\), \({\mathbf t}=(t_1,\dots,t_n)\) such that their coordinates are non-negative integers, \(b_1,\dots,b_n\) are non-zero, \({\mathbf d}_1,\dots,{\mathbf d}_k\) are distinct, and all appearing points \(j_1b_1{\mathbf u}_1+\dots+j_nb_n{\mathbf u}_n+{\mathbf d}_i\in \{0,1,\dots,N-1\}^n\). In this paper \(Q_k(\eta)\) of the following lattice \(\eta\) is estimated: Let \(q=p^n\) be the power of an odd prime and \(a_1,\dots,a_l\) distinct elements of the finite field \(\mathbb F_q\) and put \[ f(x)=(x+a_1)\dots(x+a_l)\in \mathbb F_q[x]. \] Let \(\{v_1,\dots,v_n\}\) be a basis of \(\mathbb F_q\) over \(\mathbb F_p\). Define the boxes \[ \begin{alignedat}{2} B_1&=\Biggl\{\sum_{i=1}^n u_iv_i : 0\leq u_1\leq (p-3)/2,~u_2,\dots,u_n\in \mathbb F_p\Biggr\},&&{}\\ B_j&=\Biggl\{\sum_{i=1}^n u_iv_i : u_1=\dots =u_{j-1}=(p-1)/2,\;0\leq u_j\leq (p-3)/2, u_{j+1}&&,\dots,u_n\in \mathbb F_p \Biggr\} ,\\ &{}&&j=2,\dots,n, \end{alignedat} \] and put \(B=B_1\cup \dots \cup B_n.\) Define \(\eta\) by \[ \eta(x_1,\dots,x_n)=1\quad \text{if } f(x_1v_1+\dots+x_nv_n)\neq 0 \text{ and }f(x_1v_1+\dots+x_nv_n)^{-1}\in B \] and \(\eta(x_1,\dots,x_n)=-1\) otherwise. For \(k,l<p\), \(k+l\leq p+1\) and \(kl< q/2\) the authors prove \[ Q_k(\eta)<(2^{k+3}+1)kln^kq^{1/2}(\log p+2)^{n+k}. \] The proof is based on incomplete additive character sums over subboxes of \(\mathbb F_q\).