IMC 2017 · Day 1 · P5

Let $M = \{ z : z^n = 1 \}$, $A = \{ z \in M : f(z) \ne 0 \}$ and $A^{-1} = \{ z^{-1} : z \in A \}$. We have to prove $|A| \ge k$.

Claim. $$A \cdot A^{-1} = M.$$ That is, for any $\eta \in M$, there exist some elements $a, b \in A$ such that $a b^{-1} = \eta$.

Proof. As is well-known, for every integer $m$, $$\sum_{z \in M} z^m = \begin{cases} n & \text{if } n | m \\ 0 & \text{otherwise.} \end{cases}$$ Define $c_{n-1} = 1$ and consider $$\begin{align*} \sum_{z \in M} z^2 f(z) f(\eta z) &= \sum_{z \in M} z^2 \sum_{j=0}^{n-1} c_j z^j \sum_{\ell=0}^{n-1} c_\ell (\eta z)^\ell = \sum_{j=0}^{n-1} \sum_{\ell=0}^{n-1} c_j c_\ell \eta^\ell \sum_{z \in M} z^{j+\ell+2} = \\ &= \sum_{j=0}^{n-1} \sum_{\ell=0}^{n-1} c_j c_\ell \eta^\ell \begin{Bmatrix} n & \text{if } n | j + \ell + 2 \\ 0 & \text{otherwise} \end{Bmatrix} = c_{n-1}^2 n + \sum_{j=0}^{n-2} c_j c_{n-2-j} \eta^{n-2-j} n = n \ne 0.$$

\end{align*} Therefore there exists some $b \in M$ such that $f(b) \ne 0$ and $f(\eta b) \ne 0$, i.e. $b \in A$, and $a = \eta b \in A$, satisfying $a b^{-1} = \eta$.

By double-counting the elements of $M$, from the Claim we conclude $$|A| \bigl( |A| - 1 \bigr) \ge \bigl| M \setminus \{1\} \bigr| = n - 1 \ge k^2 - 3k + 3 > (k-1)(k-2)$$ which shows $|A| > k - 1$.