Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

$\def\Z{\mathbf{Z}}$If $N$ is prime and $f(x)$ has the form $\zeta^{g(x)}$, where $\zeta$ is an $N$th root of unity and $g$ is some function from $\Z/N\Z$ to $\Z$, then $g$ must be quadratic. The following argument is very similar to the argument given in the answer https://mathoverflow.net/a/136046/20598, so I feel at liberty to be brief on details.

For each fixed $t\in\Z/N\Z$ the sum $$\sum_x \zeta^{g(x) + tx}$$ has absolute value $\sqrt{N}$ by assumption. This implies (Cavior, S.: Exponential sums related to polynomials over GF(p), Proc. A.M.S. 15 (1964) 175-178) that $$\sum_x \zeta^{g(x) + tx} = \sum_x \zeta^{ax^2 + s}$$ for some $a,s\in\Z/N\Z$ depending on $t$, and this implies that $g(x)+tx$ takes the same values and multiplicities as $ax^2+s$. In particular $g(x)+tx$ takes each value at most twice. By Segre's theorem $g$ must be quadratic.

Sean Eberhard
  • 9.7k
  • 30
  • 57