I am currently working on an idea in the context of lattice-based cryptography, but the problem that I am currently stuck on seems to have almost nothing to do with lattices anymore.
In particular, my problem refers to the "Number-theoretic Transform" (NTT), i.e. the discrete weighted Fourier Transform in the context of a finite field, when applied to small vectors. So let $p$ be a prime with $p \equiv 1 \mod 2n$ ($n$ a power of two), thus there is a primitive $2n$-th root of unity $\zeta \in \mathbb{F}_p$. Furthermore, we consider all "short" vectors $y \in \mathbb{Z}^n \setminus \{0\}$ (e.g. $\|y\|_\infty \leq O(1)$, $\|y\|_2 \leq O(\sqrt{n})$, etc. - I am not yet sure about what is the best notion here). Now we can consider the NTT of $y$, i.e. $$ \hat{y}_k = \sum_{i = 0}^{n - 1} y_i \zeta^{ik} \in \mathbb{F}_p \quad \text{where $k \in (\mathbb{Z}/2n\mathbb{Z})^*$} $$ I don't think it makes much difference, but notice that this is not the standard DFT, but the evaluation at all primitive $2n$-th roots of unity.
The question is now: Can it happen that there is some short $y$ such that for "most"/all $k$, also $\hat{y}_k$ is small, e.g. bounded by $p/4$ (technically, we mean that the absolute value of the shortest lift of $\hat{y}_k \in \mathbb{F}_p$ is small)? If yes, can we say something about the primes $p$ where this happens? Do they have to be rare?
Any ideas/related problems/references are welcome, I am more asking for some directions to explore than for a proof or solution.
I am currently not sure which notions of small or most are best. I am interested in an asymptotic setting (as $n, p \to \infty$), and the example notions should give an idea of my idea of "small".
The context As I said, I do not think it is relevant here, but if you are interested - feel free to skip it: I want to prove a fact about a lattice whose dual depends on the "unit vectors" in the decomposition $$ \mathbb{F}_p[X]/(X^n + 1) \cong \bigoplus_{i = 1}^n \mathbb{F}_p $$ via $f \mapsto (f(\zeta^k))_k$. This plays an important role in RLWE-based cryptography. The unit vectors are clearly $n^{-1} \sum_i X^i \zeta^{ki}$, and thus the above NTT of short $y$ appear naturally when taking the inner product of a short vector $y \in \mathbb{Z}[X]/(X^n + 1)$ with a shortest lift of of some "unit vector" (the used inner product is the one in the Minkowski space, but for $n$ power of two, it is equivalent to the coefficient-wise inner product).
While not being the angle that I approached this from, I think there is a much more fundamental reason why this problem appears: In RLWE, we consider "error vectors" $e$ that are short in the Minkowski-space norm (thus in the coefficient norm). The security of cryptosystems depends on the fact that the solution to linear equations over $\mathbb{F}_p[X]/(X^n + 1)$ is hard to find, if the equations are "perturbed" by such an error. If now a not-too-small amount of these errors were also small in the decomposition of $\mathbb{F}_p[X]/(X^n + 1)$ as $\mathbb{F}_p^n$ (or even just distinguishable from uniform), then one could find the error in each component separately, thus breaking RLWE.
My ideas so far I have tried to investigate a probabilistic approach. This gives a trivial bound in the case that we have an additional constant that is chosen at random - i.e. $c\hat{y}_k$ is not small for all $y$ and many $k$, assuming we pick specific $c \in \mathbb{F}_p$ and require that $p$ is absolutely huge compared to $n$. While the constant itself is not problem at all in my case, the "absolutely huge" is. In particular, my bound holds even when replacing the $\zeta^{ik}$ with almost arbitrary, fixed elements. I would really hope that we can better in the case of roots of unity.
However, using a probabilistic approach here seems very difficult, as the dependency between $p$ and $\zeta$ seems very intractable.
I am sorry for asking such a fuzzy question here. I am mainly working with cryptographers, and so I don't have the opportunity to discuss this kind of question with a pure mathematician at my institution.
