On the pseudorandom properties of subsets constructed by using primitive roots (Q2052844): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:41, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the pseudorandom properties of subsets constructed by using primitive roots |
scientific article |
Statements
On the pseudorandom properties of subsets constructed by using primitive roots (English)
0 references
29 November 2021
0 references
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''.
0 references
primitive root
0 references
pseudorandom subset
0 references
character sum
0 references