On p-pseudorandom binary sequences
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.
- On a pseudorandom property of binary sequences
- On pseudorandom \([0,1)\) and binary sequences
- On a family of pseudorandom binary sequences
- On pseudorandomness of families of binary sequences
- On finite pseudorandom binary sequences IV: The Liouville function, II
- On finite pseudorandom binary sequences. V: On \((n\alpha)\) and \((n^2\alpha)\) sequences
- On finite pseudorandom binary sequences and their applications in cryptography
- Pseudorandom binary sequences and lattices
- On the measures of pseudorandomness of binary sequences.
- On pseudo-random subsets of \({\mathbb{Z}}_n\)
- On the measures of pseudorandomness of binary sequences.
- On a pseudorandom property of binary sequences
- On the pseudo-random properties of n^c.
- On pseudorandom properties of some Dirichlet characters
- On pseudo-random subsets of the set of the integers not exceeding \(N\)
- Pseudorandom sequences constructed by the power generator
- Modular constructions of pseudorandom binary sequences with composite moduli
- On a family of pseudorandom binary sequences
- On the correlation of pseudorandom binary sequences using additive characters
- scientific article; zbMATH DE number 5116825 (Why is no real title available?)
- New pseudorandom sequences constructed by quadratic residues and Lehmer numbers
- Pseudorandom sequences of binary vectors
- On pseudorandom \([0,1)\) and binary sequences
- On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
- Binary pseudorandom sequences of period 2/sup m/-1 with ideal autocorrelation generated by the polynomial z/sup d/+(z+1)/sup d/
- On finite pseudorandom binary sequences IV: The Liouville function, II
- A note on certain modular constructions of pseudorandom binary sequences with composite moduli
- On the complexity of families of pseudo-random subsets
- On uniformly distributed \([0,1)\) sequences and binary sequences constructed by discrete logarithms
- On irregularities of distribution of binary sequences relative to arithmetic progressions. I: General results
- On the pseudorandomness of binary and quaternary sequences linked by the Gray mapping
- A family of pseudorandom binary sequences constructed by the multiplicative inverse
- Measures of pseudorandomness for finite sequences: typical values
- On the discrepancy and pseudorandomness of new sequences
- scientific article; zbMATH DE number 6401788 (Why is no real title available?)
- On pseudo-random properties of \(P(n)\) and \(P(n+1)\)
- Large families of pseudo-random subsets formed by generalized cyclotomic classes
- On the lifetime of a random binary sequence
- On large families of subsets of the set of the integers not exceeding \(N\)
This page was built for publication: On \(p\)-pseudorandom binary sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558307)
