On \(p\)-pseudorandom binary sequences (Q558307): Difference between revisions

The authors study binary sequences where the two elements are chosen with probability \(p\) and \(1-p\), respectively. The case \(p=1/2\) has been studied in a series of papers starting with \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith. 82, No. 4, 365--377 (1997; Zbl 0886.11048)]. More precisely, they consider finite binary sequences \[ E_N=\{e_1,\ldots,e_N\}\in \{1-p,-p\}^N \] and define the \(p\)-well distribution measure of \(E_N\) as \[ W(E_N,p)=\max_{a,b,t} \biggl| \sum_{j=0}^{t-1} e_{a+jb}\biggr| , \] where the maximum is taken over all positive integers \(a,b,t\) with \(1\leq a\leq a+(t-1)b\leq N\), and the \(p\)-correlation measure of order \(k\) of \(E_N\) as \[ C_k(E_N)=\max_{M,D}\biggl| \sum_{n=1}^M e_{n+d_1}\cdots e_{n+d_k}\biggr| , \] where the maximum is taken over all \(D=(d_1,\ldots,d_k)\) and \(M\) with \(0\leq d_1<\ldots<d_k\leq N-M\). They analyze these pseudorandom measures for a ``truly random'' sequence showing that \(p\)-well distribution measure and \(p\)-correlation measure of order \(k\) (for fixed \(k\)) are around \(N^{1/2}\) with ``near \(1\)'' probability. This extends earlier results for the case \(p=1/2\) of \textit{J. Cassaigne, C. Mauduit} and \textit{A. Sárközy} [Acta Arith. 103, No. 2, 97--118 (2002; Zbl 1126.11330)]. Moreover, they give the following example of a sequence with ``good'' \(p\)-well distribution and \(p\)-correlation measure. Let \(q\) be an odd prime, \(g\) a primitive root modulo \(q\), and put \(N=q-1\). Then define \(E_N=\{e_1,\ldots,e_N\}\) by \[ e_n=\begin{cases} 1-p, & \text{if}\;1\leq \text{ind}\;n\leq p(q-1),\\ -p,&\text{if}\;p(q-1)<\text{ind}\;n\leq q-1,\end{cases} \] where ind~\(n\) denotes the discrete logarithm of \(n\) in the range \(1\leq \text{ind}\;n\leq q-1\). The upper bounds on the \(p\)-well-distribution and \(p\)-correlation measure of this sequence are based on the character sum bounds of Polya-Vinogradov and Weil.