On the complexity of families of pseudo-random subsets (Q486751)

Let \(p\) a prime, \(\mathbb{F}_{p}\) the finite field with \(p\) elements, \(S\subset \mathbb{F}_{p}\) and \(\mathcal{P}\subset\mathbb{F}_{p}[X]\) a set of polynomials of bounded degree \(\leq d\). The authors consider the problem to determine the integer \(k\) such that for all subsets \(\mathcal{A}, \mathcal{B}\subset\; \mathbb{F}_{p}\) satisfying \(\mathcal{A}\cap \mathcal{B}=\emptyset\) and \(|\mathcal{A}\cup \mathcal{B}| =k,\) there exists \(P\in \mathcal{P}\) such that \(P(x)\in S\) if \(x\in \mathcal{A}\) and \(P(x)\notin S\) if \(x\in \mathcal{B}\). This problem is related to the study of the complexity of certain pseudorandom subsets. The proofs are based on deep upper bounds for exponential sums and on character sums in finite fields. Furthermore, methods from additive number theory are used.