This is probably my favorite problem that I have ever written. I sent it to 2020 USA TST, where it was deemed as very nice but too hard for the contest (but at least I managed to fool people about my other problem ). Afterwards I submitted it to 2020 RMM but it did not make the test. Unfortunately I was not aware of the rule that any submitted problems that did not make the test would be put on an extra problems list made available to all team leaders but not published officially, which means that they cannot be submitted elsewhere and even worse, most people would never be able to see the problems. Since the 2021 RMM problems are now out, I'm posting the problem here now since I think it's worth sharing. Enjoy!

This is the best olympiad algebra problem I have ever seen, and it might be the best olympiad problem I have ever seen (yes, I think it's better than SL 2020 C8). Unless I'm unaware of a reference, it's a real shame that it wasn't used for RMM 2020. (To be honest, if I had known that the fiasco with RMM would have happened, I would have advocated harder for this problem to get on USA TST.) I think it'll be a long time before I see a problem that I think is as good as this one, and I wouldn't be surprised if I never do see such a problem. (To be clear, I did not solve this problem. You should still try it anyways. It's obscenely good.)

bumping this nice problem

Bump.$~~~~~~$

Construction only. Let $n=\prod\limits_{i=1}^k p_i^{e_i}$. I will exhibit a polynomial with degree $\frac{n}{p_1}$ where $p_1$ is the smallest prime dividing $n$. First, for $n=p^k$ then I claim $P(a_1,\cdots,a_n)=\sum\limits_{i=0}^{k-1} X_i \sum\limits_{j=1}^n a_j^{p^i}$ works if $\frac{X_i}{\sum\limits_{j>i} X_j} > p^k$ If I write it as a polynomial in $\omega_{p^k}=e^{\frac{2\pi i}{p^k}}$, then its minimal polynomial is $\sum\limits_{i=0}^{p-1} x^{ip^{k-1}}$ Let $c_i$ be the number of solutions to $a_j=\omega_{p^k}^i$ and let $x=\omega_{p^k}$. Then, the value of $P$ is $Q(x)$ where $Q(x)=\sum\limits_{i=0}^{p^k-1} d_ix^i$. Here all the $x^{cp^k+t}$ coefficients are merged into the $x^t$ coefficient, and indices $d$ are taken mod $p^k$. Then $d_t=d_{p^{k-1}+t}$ since $$Q(x)=\left(\sum\limits_{j=0}^{p^{k-1}-1} a_jx^j \right) \left(\sum\limits_{j=0}^{p-1} x^{p^{k-1}j}\right)$$ Where $a_j\in \mathbb{Z}$. Let's write $d$ in terms of $c$: $d_t=\sum\limits_{i=0}^{k-1} X_i \sum\limits_{j: jp^i\equiv t(\bmod\; p^k)} c_j$ We will show, via induction on $t$, that $c_m=c_{m+p^{k-t}}$ for all $t\le k$. Base Case: $t=1$. Note the "dominant" term in $d_t$ is $X_0c_t$. Since, $d_t=d_{t+p^{k-1}}$, the difference $X_0(c_t-c_{t+p^{k-1}})$ is made up with the other terms. If it were nonzero, has absolute value at least $X_0$ which cannot be made up with the other terms. Therefore, $c_t=c_{t+p^{k-1}}$ for all $t$. Inductive Step: Assume $c_m=c_{m+p^{k-t}}$. What to show: $c_m=c_{m+p^{k-t-1}}$ Consider $d_{p^tm}=d_{p^tm+p^{k-1}}$. Expanding $d_{p^tm}$ gives $c_{p^tm}+pc_{p^{t-1}m}+\cdots+p^tc_m$ by inductive hypothesis. Since $X_0(c_{p^tm}-c_{p^tm+p^{k-1}})$ makes such a big difference, they cancel out. Without them in mind, the $c_{p^{t-1}m}$ difference also makes a big difference, so they cancel out. We can do this all the way till we have $0=p^t(c_m-c_{m+p^{k-t-1}})$, as needed. Now, here is a sketch for general $n$. Let $n=\prod\limits_{i=1}^k p_i^{e_i}$ Let's first sketch an alternate criteria for when $Q(\omega_n)$ vanishes. After compressing coefficients, I claim this is true if and only if there exist $P_i(x)$ with degree at most $p_i^{e_i}-1$ such that $Q(x)=\sum\limits_{i=1}^k P_i(x)\frac{x^n-1}{x^{p_i^{e_i}}-1}$ Proof: Show that $\gcd(\frac{x^n-1}{x^{p_i^{e_i}}-1})$ for $1\le i\le k$ is $\Phi_n(x)$ (up to a constant) by considering each $n$th root of unity. Now, there is a nice way to characterize the coefficients. A similar size bounding approach with the same type of polynomial works. This polynomial uses all of $\sum a_i^{\frac{n}{p_j}}$ for $1\le j\le k$

Bound only. Let $l=\frac{n}{p_1}$, where $p_1$ is the smallest prime dividing $n$, and suppose $P(a_1, a_2, \cdots a_n)$ works. Then, if we let $\omega$ be a primitive $n$-th root of unity, the single-variable polynomial $R(x)=P(x, \omega, \omega^2,\cdots \omega^{p_1}x, \omega^{p_1+1},\cdots \omega^{2p_1}x, \cdots\omega^{n-1})$ has to vanish at $x=1, \omega^{p_1},\cdots \omega^{(l-1)p_1}$, so it is divisible by $x^l-1$, but it can't be identically zero since it shouldn't vanish at $x=\omega$ $\implies$ its degree is at least $l$, and since the degree of $R$ is at most equal to the degree of $P$, the latter has to have degree $\geq l$.

MatteD wrote: Bound only. Let $l=\frac{n}{p_1}$, where $p_1$ is the smallest prime dividing $n$, and suppose $P(a_1, a_2, \cdots a_n)$ works. Then, if we let $\omega$ be a primitive $n$-th root of unity, the single-variable polynomial $R(x)=P(x, \omega, \omega^2,\cdots \omega^{p_1}x, \omega^{p_1+1},\cdots \omega^{2p_1}x, \cdots\omega^{n-1})$ has to vanish at $x=1, \omega^{p_1},\cdots \omega^{(l-1)p_1}$, so it is divisible by $x^l-1$, but it can't be identically zero since it shouldn't vanish at $x=\omega$ $\implies$ its degree is at least $l$, and since the degree of $R$ is at most equal to the degree of $P$, the latter has to have degree $\geq l$. Oh wow this is slick. I got the construction part pretty quick but was stuck on bounding it before going to bed yesterday. For the construction part, the following is a relatively easier way compared to the one above. Let $\omega$ be the primitive $n$-th root of unity. Then let $\pi$ be such that $\pi\in\mathbb{C}\backslash\overline{\mathbb{Q}[\omega]}$, and \[P(a_1,\ldots,a_n) = \sum_{d|n, d<n}\pi^d\sum_{i=1}^{n}a_i^d.\]Then clearly $P(a_1,\ldots,a_n)=0$ for some $a_1,\ldots,a_n\in\mathcal{S}$ if and only if $\sum_{i=1}^{n}a_i^d=0$ for any $d|n, d<n$. It is also clear that if $a_1,\ldots,a_n$ are distinct elements in $\mathcal{S}$ then $P(a_1,\ldots,a_n)=0$ and so it remains to show that there are no other common zeroes in $\mathcal{S}^n$. Let $a_1,\ldots,a_n = \omega^{b_1},\ldots,\omega^{b_n}$ where $0\leq b_i<n$. Let $Q(x) = \sum_{i=1}^{n}x^{b_i}$. Then $P(a_1,\ldots,a_n)=0$ implies that $\sum_{d|n, d<n}Q(\omega^d)=0$. Note that the conjugates of $\omega^d$ are $\omega^m$ with $\gcd(m,n)=d$ for any $d|n, d<n$. Therefore $Q(\omega^m)=0$ for any $1\leq m<n$, showing that $1+x+\cdots+x^{n-1}\mid Q(x)$. This forces $\{b_1,\ldots,b_{n}\}=\{0,1,\ldots,n-1\}$, as desired.

USJL wrote: Oh wow this is slick. I got the construction part pretty quick but was stuck on bounding it before going to bed yesterday. Funnily enough, it was quite the opposite for me. I had the idea to get all the symmetric sums to vanish, but wasnt able to show this implies all the values being distinct (which needed the idea of looking at the conjugates).

MatteD wrote: USJL wrote: Oh wow this is slick. I got the construction part pretty quick but was stuck on bounding it before going to bed yesterday. Funnily enough, it was quite the opposite for me. I had the idea to get all the symmetric sums to vanish, but wasnt able to show this implies all the values being distinct (which needed the idea of looking at the conjugates). Yeah that part is also a bit tricky. I can see people solving either part quickly and stuck on the other part forever lol.

ABCDE wrote: This is probably my favorite problem that I have ever written. [...] Enjoy! It certainly is a great problem! Let me post the solution as it appears in the RMM 2021 Shortlist, for the sake of completeness. The required minimum is the largest proper divisor $d{}$ of $n{}$; alternatively, but equivalently, it is $n/p$, where $p{}$ is the smallest prime divisor of $n{}$. Let $\zeta$ be a primitive $n{}$-th root of unity, write $\zeta_k = \zeta^k$, and consider the degree $k{}$, $n{}$-variable polynomials \[R_k(x_1, \ldots , x_n) = \sum_{j=1}^k x_j^k.\]Letting $D$ denote the set of positive proper divisors of $n{}$, we first exhibit a degree $d{}$, $n{}$-variable polynomial $P{}$ with complex coefficients, satisfying the condition in the statement. The argument hinges on Lemma 1 below. Lemma 0. For all positive integers $k<n$ it is satisfied that $\zeta_1^k+\zeta_2^k+\cdots+\zeta_n^k=0$. Lemma 1. If $a_1, \ldots , a_n\in \mathcal{S}$, then $R_k(a_1, \ldots , a_n) = 0$ for all $k{}$ in $D{}$ if and only if $a_1, \ldots , a_n$ are pairwise distinct. Proof. If $a_1, \ldots , a_n$ are pairwise distinct members of $\mathcal{S}$, then $R_k(a_1, \ldots , a_n) = 0$ for all positive integers $k < n$, by Lemma 0; in particular, for every $k{}$ in $D{}$. To prove the converse, write $a_j=\zeta_{e_j}, 0 \leqslant e_j < n$, and let $R(x)=x^{e_1}+x^{e_2}+\cdots+x^{e_n}$. As $R(\zeta_k)=R_k(a_1, \ldots , a_n)$, it follows that $R(\zeta_k) = 0$ for every $k{}$ in $D{}$, so $R{}$ is divisible by every cyclotomic polynomial $\Phi_{n/k}$, $k{}$ in $D{}$. Because $\Phi_{n/k}$ are pairwise relatively prime $R{}$ is divisible by their product \[\prod_{k\in D}\Phi_{n/k}=\frac{x^n-1}{x-1}=1+x+\cdots+x^{n-1}.\]Finally, observe that $\deg R \leqslant n - 1$ and $R(1) = n$, to infer that $R(x) =1 + x + \cdots + x^{n-1}$, and conclude thereby that $a_1,\ldots, a_n$ are indeed pairwise distinct. This concludes the proof. To exhibit a degree $d{}$, $n{}$-variable polynomial satisfying the required conditions, consider the $(n + 1)$-variable polynomial \[P(t,x_1,\ldots,x_n)=\sum_{k\in D}t^k R_k(x_1,\ldots,x_n).\]For every choice of $a_1, \ldots , a_n$ in $\mathcal{S}$, $P(t, a_1, \ldots , a_n)$ is a polynomial in $t{}$. By Lemma 1, this polynomial vanishes identically if and only if $a_1, \ldots , a_n$ are pairwise distinct. For any other choice, it has finitely many (at most $d{}$) complex roots. Because there are finitely many choices $a_1, \ldots , a_n$ with at least two equal entries, there are (infinitely many) non-zero complex numbers $a$ at which none of the corresponding $P(t, a_1, \ldots , a_n)$ vanishes. For such an $a{}$, the degree $d{}$, $n{}$-variable polynomial $P(a, x_1, \ldots , x_n)$ clearly fits the bill. There are multiple approaches to show that an $n{}$-variable polynomial $P{}$ satisfying the condition in the statement has degree at least $d{}$. We present two of them. First Approach (Allen Liu). Suppose that $\deg P < d$. Let $\mathcal{T}{}$ be the set of $d{}$-th roots of unity. Consider the polynomial \[Q(y_1,\ldots,y_p)=\sum_{j=1}^p P(\zeta_j y_j,\zeta_{p+j} y_j,\ldots,\zeta_{p(d-1)+j} y_j).\]Note that if $b_1, \ldots , b_p$ are members of $\mathcal{T}{}$, then $Q(b_1, \ldots , b_p) = 0$, since the $n = pd$ arguments in $P{}$ are all pairwise distinct elements of $\mathcal{S}$. Lemma 2 below shows that $Q{}$ vanishes identically, so \[P(\zeta_p, \zeta_{2p}, \ldots , \zeta_{pd}, \zeta_p, \zeta_{2p}, \ldots , \zeta_{pd}, \ldots , \zeta_p, \zeta_{2p}, \ldots , \zeta_{pd}) = Q(\zeta_{p-1}, \zeta_{p-2}, \ldots , \zeta_0) = 0,\]a contradiction since the arguments in $P{}$ are clearly not pairwise distinct. Lemma 2. Let $m{}$ be a positive integer, and let $F{}$ be an $m{}$-variable polynomial with complex coefficients. If $\deg F < |\mathcal{T}|$ and $F{}$ vanishes on $\mathcal{T}^m$, then $F{}$ vanishes identically. Proof. Induct on $m$. The base case, $m = 1$, follows as the single variable polynomial vanishes at a greater number of points than its degree. If $m > 1$, write \[F(x_1,\ldots,x_m)=\sum_{k=0}^{d-1}x_m^k F_k(x_1,\ldots,x_{m-1}),\]where each $\deg F_k < d = |\mathcal{T}|$. By the base case the $F_k$ all vanish on $\mathcal{T}^{m-1}$, and by the induction hypothesis they all vanish identically. Consequently, so does $F{}$. This completes induction and establishes the lemma. Second Approach (Authors). Let $\mathcal{P}$ be the set of polynomials with degree less than $n{}$ of the form \[\sum_{k=1}^{n-1}Q_kR_k,\]for some $Q_1, \ldots , Q_{n-1}\in\mathbb{C}[x_1, \ldots , x_n]$, where the $R_k$ are those defined at the beginning of the solution. Notice that $\mathcal{P}$ is closed under addition, and also closed under multiplication by arbitrary polynomials as long as the degree remains less than $n{}$. Lemma 3. For all $1\leqslant k\leqslant n-1$, there is a homogeneous polynomial $G_k \in \mathcal{P}$ of degree $k{}$ in only the variables $x_k, \ldots , x_n$ with an $x_k^k$ coefficient of 1. Proof. Define $p_k(X) = (X-x_1)(X-x_2) \cdots (X -x_k) = a_0X^k + a_1X^{k-1} + \cdots+ a_k$. We claim that each $a_j$ can be written in the form \[a_j=P_j+F_j(x_{k+1},x_{k+2},\ldots,x_n)\]where $P_j\in\mathcal{P}$ and $F_j$ are both homogeneous of degree $j$ (or identically 0). We proceed by strong induction. The base case $j = 0$ follows because $a_0 = 1 = 0+1$. Suppose $j > 0$. Further, define $H_l$ as $x_1^l+x_2^l+\cdots x_k^l$. By Newton sums, $ja_j+a_{j-1}H_1+a_{j-2}H_2+\cdots+a_0H_j=0$. By induction, \[a_j=-\frac{1}{j}\sum_{i=0}^{j-1}a_iH_{j-i}=-\frac{1}{j}\sum_{i=0}^{j-1}(P_i+F_i)H_{j-i}=-\frac{1}{j}\left(\sum_{i=0}^{j-1}P_iH_{j-i}+F_iR_{j-i}\right)+\frac{1}{j}\sum_{i=0}^{j-1}F_i\sum_{s=k+1}^{n}x_s^{j-i}\]so we may take $P_j$ to be the left summand and $F_j$ to be the right summand in the latter. Now consider $p_k(x_k)$. We have \[0=p_k(x_k)=x_k^k+\sum_{i=1}^ka_kx_k^{k-i}=x_k^k+\sum_{i=1}^k(P_i+F_i)x_k^{k-i},\]implying $G_k:=x_k^k+F_1x_k^{k-1}+F_2x_k^{k-2}+\cdots+F_k\in\mathcal{P}$. This concludes Lemma 3. Lemma 4. The set $\mathcal{Q}$ of polynomials $Q$ in $\mathbb{C}[x_1, \ldots , x_n]$ of degree less than $n{}$ with \[Q(\zeta_{\sigma(1)}\ldots,\zeta_{\sigma(n)})=0,\]for all permutations $\sigma$ of $1,\ldots,n$ is equal to $\mathcal{P}$. Proof. Lemma 0 implies that $\mathcal{P}\subset\mathcal{Q}$. Further, note that $\mathcal{P},\mathcal{Q}$ are closed under addition. We claim that given any $Q\in\mathcal{Q}$, we can subtract some $L\in\mathcal{P}$ so that for each $1\leqslant i\leqslant n$, $Q-L$ has degree at most $i-1$ in the variable $x_i$. We prove this by strong induction on $i{}$. For each $1\leqslant i\leqslant n-1$, starting from $i = 1$, write $Q = x_i^iQ_1+Q_2$ where $\deg_{x_i} Q_2 < i$ Subtract $G_iQ_1$, which reduces $\deg_{x_i}Q$ and does not increase the degree in any earlier variables. We repeatedly do this until the degree conditions are satisfied for $x_i$ before moving on to $x_{i+1}$. For $i = n$, the degree condition is satisfied because we do not increase the overall degree because the $G_k$ are homogeneous, thus at the end the total degree (and thus the degree in $x_n$) is less than $n{}$. Let $Q' = Q - L$ and note that $Q'\in\mathcal{Q}$. Let $k\leqslant n$ be a positive integer. We claim that if $R\in\mathcal{Q}$ is a polynomial in only $x_k, \ldots , x_n$, and $\deg_{x_j} R < j$ for all $j$, then $R = 0$. We proceed using reverse induction from $k = n$ to $k = 1$. The base case follows as $R$ is a single variable polynomial in $x_n$ of degree less than $n{}$ which vanishes on all of $\mathcal{S}$, thus it is identically $0{}$. For the inductive step, write $R=R_0+R_1x_k+\cdots+R_{k-1}x_k^{k-1}$ where $R_i\in\mathbb{C}[x_{k+1}, \ldots , x_n]$ for all $i{}$. Substituting $x_i = \zeta_{\sigma(i)}$ for an arbitrary permutation $\sigma$, $R\in\mathcal{Q}$ implies \[\sum_{i=0}^{k-1}R_i(\zeta_{\sigma(k+1)},\ldots,\zeta_{\sigma(n)})\zeta_{\sigma(k)}^i=0.\]However, leaving $\sigma(k+1)+\cdots+\sigma(n)$ fixed, there are $k$ distinct choices for $\zeta_{\sigma(k)}$, implying that all the coefficients of this polynomial in $\zeta_{\sigma(k)}$ vanish, thus $R_i\in\mathcal{Q}$ for all $i{}$. By the induction hypothesis they are identically $0{}$, implying $R = 0$, which completes the induction. Finally, $k=1$ implies that $Q' = 0$, so $Q = L\in\mathcal{P}$. This shows that $\mathcal{Q}\subset\mathcal{P}$ and completes the proof of the lemma. Suppose that $\deg P < d$. By Lemma 4 there exist $P_1, \ldots , P_{n-1}\in\mathbb{C}[x_1, \ldots , x_n]$ with $P = P_1R_1 + \cdots + P_{n-1}R_{n-1}$. Since $\deg P < d$, homogeneous components of degree at least $d{}$ all cancel out, so $P = Q_1R_1 + \cdots + Q_{d-1}R_{d-1}$ for some $Q_1, \ldots , Q_{d-1}\in\mathbb{C}[x_1, \ldots , x_n]$. However, note that $R_k(\zeta_p, \ldots , \zeta_{np}) = R_{pk}(\zeta_1, \ldots , \zeta_n) = 0$ for all $1 \leqslant k<d$ by Lemma 0, so $P(\zeta_p, \ldots , \zeta_{np}) = 0$, a contradiction as $\zeta_p = \zeta_{(d+1)p}$. This concludes the solution. Remarks. While the first approach is much shorter, the authors find that the second approach is more natural in that it is essentially trying to find an explicit characterization for polynomials which satisfy the problem condition. Despite the lengthy proof of Lemma 4, its main idea of trying to reduce $Q{}$ to $0{}$ by reducing it to a point where $\deg_{x_i} < i$ is a natural extension of the immediate idea to eliminate each variable one by one, which is possible for the first variable but one soon finds they are unable to eliminate another completely.

Really good problem, somehow got the slick bounding and slick solution after lots of failure . I got the construction first by small examples and knowing say symm poly theory. I spent a long time trying to force $P$ to be symmetric for small $\deg P$, which didn't lead anywhere but has nonzero time. For the bound motivation, you can note that by taking $P$ and adding say $\pi^i \cdot Q_i$ for any symmetric $Q_i$ of degree less than $\frac{n}{p_1}$, which means that by a claim in construction that our contradictory case should really be related to when the lowest nonzero coefficient of $\prod (x - a_i) - 1$ is at $x^{\frac{n}{p_l}}$, which can only occur if it also factorizes as say $\prod (x^{\frac{n}{p_l}} - b_i)$ for some $b_1, \dots, b_p$, or in other words you have the merging of $p_1$ tuples of the form $\{a, a\omega^p, a\omega^{2p}, \dots, a\omega^{n-p}\}$. We claim the answer is $\frac{n}{p_1}$ where $p_1$ is the smallest prime divisor of $n$. Let $\omega = e^{\frac{2\pi i}{n}}$. Construction Define $\sigma_i = \sum_{\text{sym}} x_1 \dots x_i$ as the $i$th symmetric sum. Then define \[ P(x_1, x_2, \dots, x_n) = \sum_{i=k}^{\frac{n}{p_1}} \left(\sum_{i=1}^n x_i^k \right) \cdot \alpha_i \]where $\alpha_1, \alpha_2, \dots, \alpha_i$ are linearly independent with all elements of ${\mathbb Q}[\omega]$ and each other. Then $P \equiv 0$ if and only if all $\sigma_i$ evaluate to $0$. This holds for $\{a_1, a_2, \dots, a_n\} = \{1, \omega, \dots, \omega^{n-1}\}$ since \[ (x - 1)(x - \omega) \dots (x - \omega^{n-1}) = x^n - 1. \]We now show the converse. Claim: Let $M = \{x_1, \dots, x_n\}$ be a multiset of elements of $\mathcal{S}$ such that $P(M) = 0$. Then $M = \mathcal{S}$. Proof. Note that this rewrites as \[ \sum_{i=1}^n x_i^k = 0 \tag{$\clubsuit$} \]for all $1 \le k \le \frac{n}{p_1}$. If we let $x_i = \omega^{b_i}$, then $\omega$ is thus a root of the polynomial. \[ \sum_{i=1}^n x^{b_ik} = 0 \]Since $\Phi_n(x)$ is the minimal polynomial of $\omega$, it follows that $\omega^p$ for $\gcd(p, n) = 1$ is also a root, and thus $(\clubsuit)$ holds for all $k \ne 0$ which can be written as $k_1p$ for $\gcd(p, n) = 1$ and $1 \le k_1 \frac{n}{p_1}$. This is true by taking $k_1 = \gcd(k, n)$. As such, by Newton sums, this implies $\sigma_1 = \sigma_2 = \dots = \sigma_{n-1} = 0$ and thus the result follows. $\blacksquare$ Bound Suppose such a polynomial $P$ of degree $l < \frac{n}{p_l} = t$ exists. Define \begin{align*} Q(a_1) = P(&a_1, a_1 \omega^p, \dots, a_1 \omega^{tp-p}, \\ &\omega^2, \omega^{2+p}, \dots, \omega^{2+tp-p}, \\ &\dots, \dots, \dots, \dots, \\ &\omega^p, \omega^{2p}, \dots, a_p \omega^{tp}) \end{align*}Then note that $Q(a_i)$ is $0$ for $a_1 = \omega^{m}$ iff $m \equiv 1 \pmod{p}$ which occurs exactly $\frac{n}{p_l}$ times, which implies $Q$ and thus $P$ has degree at least $\frac{n}{p_l}$ by the Fundamental Theorem of Algebra.