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

  • 1
    $\begingroup$ 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" $\endgroup$ – Yemon Choi Sep 19 '14 at 16:19
  • 2
    $\begingroup$ 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$. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.