An olympiad analytic combinatorics question.

Question

Question

Answer

my doubt

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

Thank you

Answer 1

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.