For $f:\mathbb{Z}/p^k \mathbb{Z}\to \mathbb{C}$, define the Fourier transform $\widehat{f}:\mathbb{Z}/p^k \mathbb{Z}\to \mathbb{C}$ in the usual way, viz., $\widehat{f}(\xi) = \sum_x f(x) e(-\xi x/p)$, where $e(t) = e^{2\pi i t}$. What is an example of a function $f:\mathbb{Z}/p^k \mathbb{Z}\to \{-1,1\}$ such that $|\widehat{f}(\xi)|\ll p^{k/2}$ for all $\xi$?

For $k=1$, there are lots of choices: we can let $f(\xi) = \left(\frac{\xi}{p}\right)$ for $\xi\ne 0$, and $f(\xi) = 1$ (say) for $\xi = 0$, but other things (such as $f(\xi) = \left(\frac{\xi^3 + a \xi + b}{p}\right)$, or other algebraic-geometrical choices) also work.

What I want is an explicit construction (preferrably one that is as "clean" as possible) for $k>1$. Existence is not hard.