On the pseudorandom properties of subsets constructed by using primitive roots
Let \(\mathcal{R}\subset \{1, 2, \dots, N\}\) and define the sequence \[ \{e_1, e_2, \dots, e_N\} \in \left\{ 1 - \frac {|\mathcal{R}|}{N}, -\frac{|\mathcal{R}|}{N}\right\}^N \] by \[ e_n = \begin{cases} 1 - \frac {|\mathcal{R}|}{N} &\text{for } n \in \mathcal{R},\\ - \frac {|\mathcal{R}|}{N} &\text{for } n \notin \mathcal{R}. \end{cases} \] \textit{C. Dartyge} and \textit{A. Sárközy} [Period. Math. Hung. 54, 183--200 (2007; Zbl 1174.05001)] introduced the following two measures of pseudorandomness: the \textit{well-distribution measure} of \(\mathcal{R}\) is defined by \[ W(\mathcal{R}, N) = \max_{a,b,t} \left|\sum_{j=0}^{t-1}e_{a+jb}\right|, \] where the maximum is taken over all \(a, b, t \in \mathbb{N}\) with \(1\le a\le a+(t-1)b\le N\), and the \textit{correlation measure of order k} of \(\mathcal{R}\) is defined by \[ C_k(\mathcal{R}, N) = \max_{M,L}\left| \sum_{n=1}^M e_{n+\ell_1}\cdots e_{n+\ell_k}\right|, \] where the maximum is taken over all \(L=(\ell_1, \dots, \ell_k)\) and \(M\) with \(0\le \ell_1< \dots < \ell_k\le N-M\). The subset \(\mathcal{R}\) is considered to be a pseudorandom subset if both \(W(\mathcal{R}, N)\) and \(C_k(\mathcal{R}, N)\) (at least for small \(k\)) are small in terms of \(N\). Let \(p>2\) be a prime, \(s, r \in \mathbb{N}\), \(f(x)\in\mathbb{F}_p[x]\) of degree \(D\), let \(\mathcal{G}_p\) be the set of the primitive roots modulo \(p\) and define the subset \(\mathcal{R} \subset \mathbb{F}_p\) by \[ \mathcal{R} = \{g^s : g\in \mathcal{G}_p, \; \text{ exists } x \in\mathbb{F}^*_p \text{ with } f(g^s)=x^r \}. \] \textit{C. Dartyge}, \textit{A. Sárközy} and the reviewer [Combinatorica 30, 139--162 (2010; 1259.11072] proved the following estimates: If \(f(x)\) is \textit{irreducible} over \(\mathbb{F}_p\), then we have \[ W(\mathcal{R}, p) \ll D 2^{\omega \big(\frac {p-1}{(s, p-1)}\big)}p^{\frac {1}{2}} \log p. \tag{1} \] Moreover, if we also assume that \(D\ge 2\) or \(D=r=1\), we also have \[ C_k(\mathcal{R}, p)\ll kD\big( \big( 1+ O \big(Dp^{-\frac {1}{2 }}\big)\big) 2^{\omega \big({\frac {p-1}{(s, p-1)}}\big)}\big)^k p^{\frac {1}{2}} \log p. \tag{2} \] It is also conjectured that (1) holds probably for all \(f(x)\) of degree \(D\ge 1\) and (2) for polynomials of type \(f_1f_2^{\alpha}\), where \(f_1, f_2\) are irreducible and \(\alpha \ge 2\). In the paper under review the authors prove (1) for monic \(f(x)\) of degree \(D\ge 2\) satisfying \(f(0)\ne 0\) in Theorem 1.1. Their Theorem 1.2 shows that \(\mathcal{R}\) is not always ``good if all the zeros of \(f(x)\) are single in \(\mathbb{F}_p\) since for \(f(x)=(x+2)(x+3)\), \(s|r\), \(s>1\), \[ C_4(\mathcal{R}, p) \gg \frac {\varphi^4\big(\frac {p-1}{(s, p-1)}\big)}{p^3}. \] Theorem 1.3 says that (2) does not hold for \(f(x)=\left(x+(p+1)/2\right)x^2,\; s|r,\; s>1, \text{ odd } r\) since then \[ C_2(\mathcal{R}, p) \gg \frac {\varphi^2\big(\frac {p-1}{(s, p-1)}\big)}{p}. \] Theorem 1.4 shows that a \textit{subset} of the set of primitive roots is not always ``good.
- On the pseudo-randomness of subsets related to primitive roots
- Pseudo-random subsets constructed by using Fermat quotients
- On pseudo-random subsets of \({\mathbb{Z}}_n\)
- Pseudorandom subsets formed by power residues with composite moduli
- Pseudorandom subsets with composite moduli
- A note on pseudorandom subsets formed by generalized cyclotomic classes
- On pseudo-random subsets of the set of the integers not exceeding \(N\)
- On multi-dimensional pseudorandom subsets
- On the complexity of families of pseudo-random subsets
- On pseudorandom subsets in finite fields. I: Measure of pseudorandomness and support of Boolean functions
- A note on pseudorandom subsets formed by generalized cyclotomic classes
- Construction of large families of pseudorandom binary sequences
- Distribution of residues and primitive roots
- Equations in finite fields with restricted solution sets. I: Character sums
- Equations over finite fields. An elementary approach
- scientific article; zbMATH DE number 3119376 (Why is no real title available?)
- scientific article; zbMATH DE number 3370402 (Why is no real title available?)
- Large families of pseudo-random subsets formed by generalized cyclotomic classes
- Large families of pseudorandom subsets formed by power residues
- On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
- On large families of subsets of the set of the integers not exceeding \(N\)
- On pseudo-random subsets of the set of the integers not exceeding \(N\)
- On the distributions of quadratic residues and primitive roots over finite fields
- On the pseudo-randomness of subsets related to primitive roots
- Pairs of Consecutive Primitive Roots Modulo a Prime
- On pseudo-random subsets of \({\mathbb{Z}}_n\)
- Large families of subsets arising from Woods problem and their pseudorandomness
- On the pseudo-randomness of subsets related to primitive roots
- On pseudorandom subsets in finite fields. I: Measure of pseudorandomness and support of Boolean functions
- On the correlation measures of subsets
- On multi-dimensional pseudorandom subsets
- Large family of pseudorandom subsets of the set of the integers not exceeding N
- A note on pseudorandom subsets formed by generalized cyclotomic classes
- Pseudo-random subsets constructed by using Fermat quotients
- A technique to study the correlation measures of binary sequences
This page was built for publication: On the pseudorandom properties of subsets constructed by using primitive roots
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052844)
