An olympiad analytic combinatorics question. Question

Answer

my doubt
Can anyone explain the red underlined  equation?  And why cube root of unity is used here?
Thank you

We will take the specific case when $n=3$ so as to check the arguments in the solution. 
We have numbers $a_1,a_2, a_3$. WLOG, assume $a_1< a_2<a_3$. (Whenever two of them are equal, we can delete one of the two.) $$f(X)=X^{a_1} + X^{a_2}+X^{a_3}.$$
$$\begin{aligned}f(X)f(X^{-1})&= (X^{a_1} + X^{a_2}+x^{a_3})(X^{-a_1} + X^{-a_2}+x^{-a_3})\\
&=3+ (X^{a_1-a_2}+ X^{a_2-a_1})+ X(^{a_1-a_3}+ X^{a_3-a_1})+ (X^{a_3-a_2}+ X^{a_2-a_3})\\
&= 3+ \sum_{k\text{ runs through }a_2-a_1,\ a_3-a_1,\ a_3-a_2}(X^k+ X^{-k})\\
&= 3+ \sum_{k\in\{a_2-a_1,\ a_3-a_1,\ a_3-a_1\}}b_k(X^k+ X^{-k})\quad\text{for some constants } b_k.\\
\end{aligned}$$ 
Note that $a_2-a_1,\ a_3-a_1,\ a_3-a_1$ may not be distinct. It may happen that $a_2-a_1=a_3-a_2$. So, $b_k$ could be $1$ or $2$. (In general, $1\le b_k\le n-1$ when all $a_i$ are distinct.)
What is important is that $b_k\ge1$ if and only if there exist $a_i$ and $a_j$ such that $k=a_j-a_i$.
$$\sum_{k=-{n\choose 2}}^{n\choose2}X^k=1+ \sum_{k\in\{1,\,2,\,3\}}(X^k+X^{-k})$$
So, $$f(X)f(X^{-1})-\sum_{k=-{n\choose 2}}^{n\choose2}X^k
= 2+ \sum_{k\in\{a_2-a_1,\ a_3-a_1,\ a_3-a_1\}\cup\{1,2,3\}}c_k(X^k+ X^{-k})\tag{***}\label{***}$$ 
where $c_k$ is some constant depending on $a_1,a_2,a_3$ and $k$.

*

*If $k\in\{1,2,3\}\setminus\{a_2-a_1,\ a_3-a_1,\ a_3-a_1\}$, then $c_k=-1$

*If $k\in\{a_2-a_1,\ a_3-a_1,\ a_3-a_1\}\setminus\{1,2,3\}$, then $c_k=b_k\ge1$

*If $k\in\{a_2-a_1,\ a_3-a_1,\ a_3-a_1\}\cap\{1,2,3\}$, then $c_k=b_k-1\ge0$
So, every $c_k\ge-1$, and $c_k=-1$ exactly if $k$ is "missed".
$\sum_{c_k<0}-c_k$ is exactly the number of the "missed" terms (denoted by $t$).
Substituting $1$ for $X$ in $\eqref{***}$, we see that the left-hand side is $n\cdot n-(2{n\choose 2} + 1)=n-1$. The right-hand side is $(n-1)+2\sum c_k$. So $\sum c_k=0$. So $\sum|c_k|=2t$.
As remarked by Sarvesh Ravichandran Iyer, "the introduction of generating functions is done to capture the number of times that a particular term can be written as $a_i−a_j$."


Why cube root of unity is used here?

What is great about analytical method here is that we have an equality $\eqref{***}$ that involves a variable $X$, whose value can be whatever number. For example, let $X$ be $1$ as we have done above, we have found the $\sum|c_k|=2t$.
To obtain another fact about $t$, $\omega=\exp(\frac{3\pi i}{n^2-n+1})$ is used for $X$. Note that although a root of unity, $\omega$ is never a cube root of unity. ($\omega^{2(n^2-n+1)/3}=1$ if $n\equiv_32$. $\omega^{2(n^2- n +1)}=1$ otherwise.)
This choice for $X$ has several advantages that enables us to compute a nontrivial lower bound for $t$ easily.

*

*Since $|\omega|=1$, $\omega$ and $\omega^{-1}$ are conjugate to each other. So $f(\omega)f(\omega^{-1})$, $\sum_{k=-{n\choose 2}}^{n\choose2}\omega^k$ and $\omega^k+\omega^{-k}$ for all $k$ are self-conjugate. So they are all real numbers.

*$|\omega^k+\omega^{-k}|\le1+1=2$. The right-hand side is at most $(n-1)+ (2t)\cdot 2=(n-1)+4t$. (The solution made a typo, referring to "the left-hand side").

*The left-hand side is $$|f(\omega)|^2-\sum_{k=-{n\choose 2}}^{n\choose2}\omega^k.$$ where the solution made another typo. It is $-$, not $+$.
$\sum_{k=-{n\choose 2}}^{n\choose2}\omega^k$ is "quite negative", since about one third of the terms $\omega^k$, $-\frac{n^2-n}2\le k\le\frac{n^2-n}2$ has nonnegative real parts, $\Re(\omega^k)\ge0 \iff \frac{-\pi}2\le\frac{3\pi}{n^2-n+1}k\le\frac{\pi}2\iff -\frac{n^2-n+1}{6}\le k\le\frac{n^2-n+1}{6}$.  ("A third" comes from the fraction $\frac{\frac{n^2-n+1}{6}}{\frac{n^2-n}2}\approx\frac13$.)
On average roughly, each $\omega^k$ contributes $-\frac2{3\pi}$ to the real part of their sums.
Hence, the left-hand side is roughly bigger than $\frac2{3\pi}\dot(n^2-n+1)\approx \frac{4n^2}{19}$, which is the conclusion.

