\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{JMO 2020/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 16}
\maketitle
\section*{Problem}
Let $n \ge 2$ be an integer.
Let $P(x_1, x_2, \dots, x_n)$ be a nonconstant
$n$-variable polynomial with real coefficients.
Assuming that $P$ vanishes whenever two of its arguments are equal,
prove that $P$ has at least $n!$ terms.
\section*{Video}
\href{https://www.youtube.com/watch?v=r7j0oRtpErA&t=4905}{\texttt{https://youtu.be/r7j0oRtpErA}}
\newpage
\section*{Solution}
We present Ankan's original solution.
Begin with the following observation:
\begin{claim*}
Let $1 \le i < j \le n$.
There is no term of $P$ which omits both $x_i$ and $x_j$.
\end{claim*}
\begin{proof}
Note that $P$ ought to become identically zero
if we set $x_i = x_j = 0$,
since it is zero for any choice of the remaining $n-2$ variables,
and the base field $\RR$ is infinite.
\end{proof}
\begin{remark*}
[Technical warning for experts]
The fact we used is not true if $\RR$ is replaced by a field
with finitely many elements, such as $\FF_p$,
even with one variable.
For example the one-variable polynomial $X^p-X$ vanishes
on every element of $\FF_p$,
by Fermat's little theorem.
\end{remark*}
We proceed by induction on $n \ge 2$ with the base case $n=2$ being clear.
Assume WLOG $P$ is not divisible by any of $x_1$, \dots, $x_n$,
since otherwise we may simply divide out this factor.
Now for the inductive step, note that
\begin{itemize}
\ii The polynomial $P(0, x_2, x_3, \dots, x_n)$
obviously satisfies the inductive hypothesis
and is not identically zero since $x_1 \nmid P$,
so it has at least $(n-1)!$ terms.
\ii Similarly, $P(x_1, 0, x_3, \dots, x_n)$
also has at least $(n-1)!$ terms.
\ii Similarly, $P(x_1, x_2, 0, \dots, x_n)$
also has at least $(n-1)!$ terms.
\ii \dots and so on.
\end{itemize}
By the claim, all the terms obtained in this way
came from different terms of the original polynomial $P$.
Therefore, $P$ itself has at least $n \cdot (n-1)! = n!$ terms.
\begin{remark*}
Equality is achieved by the
Vandermonde polynomial
$P = \prod_{1 \le i < j \le n} (x_i-x_j)$.
\end{remark*}
\end{document}