On \(p\)-pseudorandom binary sequences (Q558307): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: András Sárközy / rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1023/b:mahu.0000040540.74204.be / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2023394903 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:37, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On \(p\)-pseudorandom binary sequences |
scientific article |
Statements
On \(p\)-pseudorandom binary sequences (English)
0 references
5 July 2005
0 references
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.
0 references
pseudorandom
0 references
correlation
0 references
distribution
0 references
binary sequences
0 references