# Functions $f$ on $\mathbb{Z}/N\mathbb{Z}$ with $|f|$ and $|\widehat{f}|$ constant

Let $N$ be a positive integer; for simplicity I'm happy to assume it's an odd prime but I'm interested in the general case too.

Let $f \colon \mathbb{Z}/N\mathbb{Z} \to \mathbb{C}$ and let $\widehat{f}$ denote its Fourier transform, $\widehat{f}(\xi) = \frac{1}{N} \sum_x f(x) e^{-2 \pi i \xi x / N}$.

I'm interested in functions $f$ with $|f|$ constant and $|\widehat{f}|$ constant; with the above conventions, WLOG taking $|f| = 1$ we have $|\widehat{f}| = 1/\sqrt{N}$.

My question is: is anything known about such functions? Do they have a name? Is there perhaps even a precise classification of them? Any pointers or references would be appreciated.

It's maybe worth saying that, although apparently a question about analysis, it is actually surely strongly algebraic in nature. Indeed, the conditions can be phrased as an algebraic set over $\mathbb{R}$ which I believe has dimension $0$ when $N$ is prime (if we add the condition $f(0) = 1$ to remove the degeneracy), which would mean the collection of such $f$ is finite and the coefficients are algebraic numbers. Furthermore all the examples I've computed are exceedingly structured, e.g.

$$f(x) = e^{2 \pi i (\alpha x^2 + \beta x + \gamma) / N}$$

where $\alpha \in (\mathbb{Z}/N\mathbb{Z})^\times$, $\beta \in \mathbb{Z}/N\mathbb{Z}$, $\gamma \in \mathbb{R}$, as well as more complicated variants.

EDIT: given Sean Eberhard's partial answer below, I should maybe sketch an example to show that these quadratic examples are not the only ones, i.e. there are such functions $f$ whose values are not $N$th roots of unity.

Very briefly: let $f(x)$ be $1$ when $x$ is a square modulo $N$ and $\alpha$ otherwise for some fixed $\alpha \in \mathbb{C}$. It suffices to show that there is an $\alpha$ that works. Whenever $N \equiv 3 \pmod{4}$ is prime, this is the case, and in fact $$\alpha = \frac{ -(N-1) \pm 2 \sqrt{-N}}{N+1} \ .$$

• Apologies in advance for a "drive-by comment" (am rushing between chores) but some stuff might be in the literature under a different name, namely "circulant complex Hadamard matrices" – Yemon Choi Sep 19 '14 at 16:19
• Many thanks for this Yemon - this answers the "do they have a name" part of my question. It turns out arxiv.org/pdf/1311.5390v2.pdf includes what is essentially the proof of Sean's result below: in fact, they both reference the same MO post. I'd be very interested if anyone familiar with that literature could clarify the state of the art, maybe for prime $N$. – Freddie Manners Sep 19 '14 at 17:20

$\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.