Cyclic permutations of large subsets with polynomial values in multiplicative subgroups of finite fields

Abstract

Let $f(t)\in \mathbb{Z}[t]$ be a nonconstant polynomial with nonzero discriminant and let $k\ge 2$ be an integer. Inspired by the work of Alon and Bourgain, for sufficiently large prime $p\equiv 1(\mathrm{mod}k)$, we study cyclic orderings of subsets $A\subseteq {\mathbb{F}}_p$ for which $f(a_i+a_{i+1})$ is a nonzero $k$-th power for every consecutive pair. By combining mixed character-sum estimates, Fourier analysis on ${\mathbb{F}}_p$, and spectral graph methods, we establish a threshold $c(p,k,f)$ such that every subset $A$ with $\#A\ge c(p,k,f)$ admits such a cyclic ordering. We also give lower and upper bounds for the optimal threshold.

arXiv comment21 pages. Comments are welcome