On the pseudorandom properties of subsets constructed by using primitive roots (Q2052844): Difference between revisions

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''.