China TST 2020/1 Let $\omega$ be a primitive $n$ -th root of unity. Given complex numbers $a_1,a_2,\cdots,a_n$, and $p$ of them are non-zero. Let $b_k=\sum_{i=1}^n a_i \omega^{ki}$ for $k=1,2,\cdots, n$. Prove that if $p>0$, then at least $\tfrac{n}{p}$ numbers in $b_1,b_2,\cdots,b_n$ are non-zero.

JustPostChinaTST wrote: Let $\omega$ be a $n$ -th root of unity. Given complex numbers $a_1,a_2,\cdots,a_n$, and $p$ of them are non-zero. Let $b_k=\sum_{i=1}^n a_i \omega^{ki}$ for $k=1,2,\cdots, n$. Prove that if $p>0$, then at least $\tfrac{n}{p}$ numbers in $b_1,b_2,\cdots,b_n$ are non-zero.

Verify that $a_k = \frac{1}{n}\sum_{j=1}^n b_k \omega^{-jk}$. Since $p$ of them are nonzero, we can write $$b_k = \sum_{j=1}^p a_{i_j}\omega^{i_jk}$$therefore $\{b_k\}$ is a linearly recurrent relation of degree at most $p$. In particular, if $p$ consecutive values are 0, then all $b_k$ are zero and so all $a_k$ are zero, which is a contradiction. So no $p$ consecutive values of $b_k$ are zero (i.e. at least $n/p$ values are nonzero).

Let $A=\{1\leq j \leq n : a_j \neq 0\}$ $B=\{1\leq j \leq n : b_j \neq 0\}$ it's well-known that $|b_1|^2 + \cdots +|b_n|^2 = n(|a_1|^2 + \cdots +|a_n|^2)$ i.e. $\sum_{j\in B} |b_j|^2 =n(\sum_{j\in A}|a_j|^2)$ since $ |b_j| \leq \sum_{j\in A}|a_j|$ and apply Cauchy on RHS it follows that $|B| \geq \frac{n}{|A|} = \frac{n}{p}$

VicKmath7 wrote: China TST 2020/1 Let $\omega$ be a $n$ -th root of unity. Given complex numbers $a_1,a_2,\cdots,a_n$, and $p$ of them are non-zero. Let $b_k=\sum_{i=1}^n a_i \omega^{ki}$ for $k=1,2,\cdots, n$. Prove that if $p>0$, then at least $\tfrac{n}{p}$ numbers in $b_1,b_2,\cdots,b_n$ are non-zero. It should be added that $\omega$ is also primitive.

This could also be done using tools of Fourier Analysis on finite groups, for those who are looking for more Fourier Analysis, check the given link: https://arxiv.org/abs/math/0308286. Okay, now we will use few theorems and define some things from Fourier Analysis on finite groups! Let $\mathbb{A}=\mathbb{Z}_{d_{1}}\times \cdots \times\mathbb{Z}_{d_{n}} $ and let $E:\mathbb{A} \times \mathbb{A} \rightarrow \mathbb{C}$ be a function defined as follows: $E(x,\epsilon)=(e^{2\pi i/d_{1}})^{x_{1}\epsilon_{1}}\cdots(e^{2\pi i/d_{n}})^{x_{n}\epsilon_{n}}$. Okay. Now we define Fourier Transform of function $f:\mathbb{A}\rightarrow\mathbb{C}$ as follows: $\hat{f}(\epsilon)=\sum_{x\in \mathbb{A}}f(x)E(x,\epsilon)$ for all $\epsilon \in \mathbb{A}$. And now important theorem which is also in paper given above, Uncertainty principle: Define $supp(f)$ to be the set of all values $x \in \mathbb{A}$ such that function evaluated at that point is not zero. Now we have $|supp(f)||supp(\hat{f})|\geq|\mathbb{A}|$, and we will use this to solve this problem. So define $f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{C}$ like this: $f(x)=\sum_{i=0}^{n-1} a_i \omega^{ix}$, so just name sequence different since $\omega^{n}=\omega^{0}$. We need to prove that $|supp(f)|\geq \frac{n}{p}$. By double summation we have that $\hat{f}(\epsilon)=\sum_{i=0}^{n-1} a_{i}\sum_{x=0}^{n-1}\omega^{x(i+\epsilon)}$, and using the lemma that $\sum_{i=0}^{n-1}\omega^{ix}$ is either equal to $0$ if $n$ doesn't divide $x$ and $n$ otherwise we get that $\hat{f}(\epsilon)=$ $n\sum_{n|i+\epsilon}a_{i}$, and since $i$ and $\epsilon$ are both $\leq n-1$ we get that $\hat{f}(\epsilon)=na_{n-\epsilon}$. Since there are $p$ of nonzero values of $a_{i}$ we easily get the result by Uncertainty principle, since $|supp(\hat{f})|=p$ and $|\mathbb{A}|=n$. $\textbf{Note}$: For those who read the paper this result can be used to prove that, if n is a prime number then there would be at least $n-p+1$ nonzero values.

POLYNOMIALS!! Take indices mod $n$. By pigeonhole principle, there exist $a_j=a_{j+1}=\cdots=a_{j+k-1}=0$ for some $k\ge \frac np-1$ Consider the polynomial $P(x)=\sum\limits_{i=0}^{n-1} a_{i+j+k}x^i$. Notice $[x^m]P(x)$ for $m>n-\frac np$ is 0 by our setup. Therefore, $\deg P\le n-\frac np$, so $P(x)$ has at most $n-\frac np$ roots. Furthermore, $P(\omega^k)=0$ if and only if $\sum\limits_{i=1}^n a_i\omega^{ki}=0$. Therefore, we are done.