I don’t know if I’m crying from the beauty from this problem or its difficulty

This looks like a harder version of RMM 2020 A2. Since it’s from the USA, the author might even be the same.

Reminds me Putnam 2008 A5 ... , But seems too harder !

A sketchy solution: Step 1: $f$ is always nonnagative. It suffices to prove that from one set of points not forming a regular $2n$-gon,we can move it to another such set, so that at any time during this process, this set does not form a $2n$-gon,so by continuity,these two sets must agree on sign of $f$. Step 2:We can represent $f$ as a symmetric polynomial of $z_k,\bar{z_k}$,where $z_k=x_k+iy_k$.(meaning it remains unchanged when swapping two indices) We can add all the $f$ permuting the $x_i$s and conclude easily since $f\ge 0$ and that the vertices of a $2n$-gon can permute to remain a $2n$-gon. Step 3:Now we assume all $z_i$s are unit complex numbers.We consider what values this polynomial takes when $z_i$s form two regular $n$-gons. This polynomial is a polynomial of $\sum z_k^t,\sum \bar{z_k}^t$ where $t=0,1,\cdots,n$. However,the values agree for all $t \neq n$;if the degree is $n$ with the form $A+B\sum z_k^n+\sum \bar{z_k}^n+\text{Something Zero in this condition}$and we can see that the range is a interval containing the $f=0$ case,contradicting $f>0$;otherwise we cannot distinguish this case with the regular $2n$-gon case.

The answer is $2n$. Construction: We observe that the sufficient and necessary conditions for $(x_j,y_j)$'s to form a regular $2n$-agon is as follows: if $z_j = x_j + iy_j$ for all $j$, and $\mu = \frac{z_1+\cdots+z_{2n}}{2n}$, then $$\sum_{j=1}^{2n} (z_j-\mu)^k = 0 \forall k=2,\cdots,2n-1$$ This appears like it will give a polynomial of degree $4n-2$ by multiplying each newton sum by its conjugate and adding them. However, let $z'_j = z_j-\mu$, then we can actually force all $|z'_j|$ to be equal with another term $\sum_{j\ne k} ( |z'_j| - |z'_k|)^2$. Now that all moduli are equal, we just need $$\sum_{j=1}^{2n} (z'_j)^k = 0 \forall k=-n, -(n-1), \cdots, -1, 1, \cdots, n$$ Why? Consider $P(x) = \prod (x-z'_j)$. Then from $\sum_{j=1}^{2n} (z')_j^k = 0 \forall k=1, \cdots, n$ we can see that $P(x)$ has zero $x^j$-coefficient for $j=n,\cdots,2n-1$. Now, if we consider $Q(x) = \prod (x-(z')_j^{-1}) = \frac{x^{2n}}{\prod (z')_j} P(1/x)$, we get that $Q(x)$ has zero $x^j$-coefficient for $j=n,\cdots,2n-1$, which means $P(x)$ has zero $x^j$-coefficient for $j=1,\cdots,2n-1$, as desired. Therefore, since $\sum_{k=1}^{2n} \overline{(z')_j}^k = |z_1|^{2k} \sum_{k=1}^{2n} (z')_j^{-k}$, the polynomial $$\sum_{j=2}^{2n} (|(z')_j| - |(z')_k|)^2 + \sum_{j=2}^n (\sum_{k=1}^{2n} (z')_j^k)(\sum_{k=1}^{2n} \overline{(z')_j}^k)$$ works. We can use linear transformations to translate that back to $f$. Bound: We first apply a linear transformation so we focus on $g(z_1, \overline{z_1},\cdots, z_{2n}, \overline{z_{2n}})$. Then we consider $$R(x) = g(\omega_{2n}, \omega_{2n}^{-1}, \omega_{2n}^3, \omega_{2n}^{-3}, \cdots, \omega_{2n}^{2n-1}, \omega_{2n}^1, x, \overline{x}, x\omega_{n}, \overline{x\omega{n}}, \cdots, x\omega_{n}^{n-1}, \overline{x\omega_{n}^{n-1}})$$ We can see that $R$ vanishes whenever $x^n-1=0$. i.e. $x^n-1\mid R(x)$. We in fact prove something stronger, that $(x^n-1)^2 \mid R(x)$, which finishes the problem. Claim: (recall $R(x)\in \mathbb{R} \forall x\in \mathbb{C}$) $R(x)$ has the same sign for all $x\in \mathbb{C}, |x|=1$. Proof: suppose $R(a) > 0, R(b) < 0, |a|=|b|=1$. Since $R(sa+(1-s)b)$ is a polynomial with real range (and can actually be rewritten as a one-variable polynomial with real coefficients), then $R(sa+(1-s)b)=0$ for some $0<s<1$. However, $|sa+(1-s)b|<1$ and $R$ can only vanish on the unit circle. Contradiction. Claim: $R(x)$ has the same sign for all $x\in \mathbb{C}$. Proof: Consider a line passing through $x$ and a point on the unit circle that is not one of the $n$ roots of unity. Say it is of the form $S(a)=R(x+at)$. Since $R$ takes on real values (and can be written as a one-var poly with real coefficients), and we know that $S(a) \ne 0$ for all $a\in \mathbb{R}$, it readily follows that $S(0)=R(x)$ has the same sign as $R(x+am)$ where $|x+am|=1$. Since $f$ has the same sign for all $(x_1,\cdots,y_{2n}) \in \mathbb{R}^{4n}$, this imply that each of the $n$ roots of unity is a critical point of $R$, which readily implies that $(x^n-1)^2 \mid R(x)$.

The smallest possible degree is $2n$. In what follows, we will frequently write $A_i = (x_i, y_i)$, and abbreviate $f(x_1, y_1, \dots, x_{2n}, y_{2n})$ to $f(A_1, \dots, A_{2n})$ or as a function of any $2n$ points. Bound Suppose that $f$ is valid. First, we note a key property: Claim. [Sign of $f$] Either $f \ge 0$ or $f \le 0$. Proof. This follows from the fact that the zero-set of $f$ is very sparse: if $f$ takes on a positive and a negative value, we can move $A_1,\ \dots,\ A_{2n}$ from the negative value to the positive value without ever having them form a regular $2n$-gon—a contradiction. $\square$ The strategy for showing $\deg f \ge 2n$ is the following. We will animate the points $A_1,\ \dots,\ A_{2n}$ linearly in a variable $t$; then $g(t) \stackrel{\text{def}}= f(A_1, \dots, A_{2n})$ will have degree at most $\deg f$ (assuming it is not zero). The previous lemma establishes that any root of $g$ must be a multiple root, so if we can show that there are at least $n$ roots, we will have shown $\deg g \ge 2n$, and so $\deg f \ge 2n$. Geometrically, our goal is to exhibit $2n$ linearly moving points so that they form a regular $2n$-gon a total of $n$ times, but not always form one. We will do this as follows. Draw $n$ mirrors through the origin, as lines making angles of $\tfrac{\pi}n$ with each other. Then, any point $P$ has a total of $2n$ reflections in the mirrors, as shown below for $n = 5$. (Some of these reflections may overlap.)

We will animate $P$ on any line which intersects all $n$ bisectors, and let $P_1,\ \dots,\ P_{2n}$ be its reflections. Clearly, these are also all linearly animated, and because of the reasons above, they will form a regular $2n$-gon at least $n$ times. It's not difficult to see that they will not always form a regular $2n$-gon, so this establishes $\deg f \ge 2n$ for the reasons described previously. Construction We will construct a suitable $f$ as a sum of squares. This means that, if we write $f = f_1^2 + \dots + f_k^2$, then $f = 0$ if and only if $f_1 = \dots = f_k = 0$, and that if their degrees are $d_1,\ \dots,\ d_k$, then $f$ has degree at most $2 \max(d_1, \dots, d_k)$. Thus, it is sufficient to exhibit several polynomials, all of degree at most $n$, such that $2n$ points are the vertices of a regular $2n$-gon if and only if the polynomials are all zero at those points. First of all, we will instead find a polynomial which has this property, but only when points with sum zero are input. This still solves the problem, because then we can choose \[ f(A_1 - \overline{A}, \dots, A_{2n} - \overline{A}), \]where $\overline{A}$ is the centroid of $A_1,\ \dots,\ A_{2n}$. This has the upshot that we can now always assume $A_1 + \dots + A_{2n} = 0$, which will simplify the ensuing discussion. First, we will impose the constraints that all $|A_i|^2 = x_i^2 + y_i^2$ are equal. This uses multiple degree $2$ constraints. Now, we may assume that the points $A_1,\ \dots,\ A_{2n}$ lie on a circle with center $0$, and $A_1 + \dots + A_{2n} = 0$. If this circle has radius $0$, then all $A_i$ coincide, and we may ignore this case. Otherwise, the circle has positive radius. We will use the following lemma. Lemma. Suppose that $a_1,\ \dots,\ a_{2n}$ are complex numbers of the same nonzero magnitude, and suppose that $a_1^k + \dots + a_{2n}^k = 0$ for all $k \in \{1, \dots, n\}$. Then $a_1,\ \dots,\ a_{2n}$ form a regular $2n$-gon centered at the origin. (Conversely, this is easily seen to be sufficient.) Proof. Since all the hypotheses are homogenous, we may assume (mostly for convenience) that $a_1,\ \dots,\ a_{2n}$ lie on the unit circle. By Newton's sums, we obtain that the $k^{\text{th}}$ symmetric sums of $a_1,\ \dots,\ a_{2n}$ are all zero for $k \in \{1, \dots, n\}$. Taking conjugates gives that we also have \[ a_1^{-k} + \dots + a_{2n}^{-k} = 0 \]for all $k \in \{1, \dots, n\}$. Thus, we can repeat the above logic to obtain that the $k^{\text{th}}$ symmetric sums of $a_1^{-1},\ \dots,\ a_{2n}^{-1}$ are also all zero for $k \in \{1, \dots, n\}$. However, these are simply the $(2n-k)^{\text{th}}$ symmetric sums of $a_1,\ \dots,\ a_{2n}$ (divided by $a_1 \cdots a_{2n}$), so the first $2n-1$ symmetric sums of $a_1,\ \dots,\ a_{2n}$ are all zero. This implies that $a_1,\ \dots,\ a_{2n}$ form a regular $2n$-gon centered at the origin. $\square$ We will encode all of these constraints into our polynomial. More explicitly, write $a_r = x_r + y_ri$; then the constraint $a_1^k + \dots + a_{2n}^k = 0$ can be expressed as $p_k + q_k i = 0$, where $p_k$ and $q_k$ are real polynomials in the coordinates. To incorporate this, simply impose the constraints $p_k = 0$ and $q_k = 0$; these are conditions of degree $k \le n$, which is okay. To recap, taking the sum of squares of all of these constraints gives a polynomial $f$ of degree at most $2n$ which works whenever $A_1 + \dots + A_{2n} = 0$. Finally, the centroid-shifting trick gives a polynomial which works in general, as wanted. Remark. [Odd number of points] It is natural to wonder about what happens when the number of points is an odd integer $n \ge 3$. There is a construction of degree $\max(4, n-1)$, which is similar to the construction described for $n$ even. To obtain a bound, we could try to proceed as we did earlier, by solving the following: Quote: There are $n$ linearly animated points on the plane. Suppose that they form the vertices of a regular $n$-gon exactly $N$ times, where $N$ is finite. What is the maximum possible value of $N$? This problem is actually interesting in its own right (try it!): the answer turns out to be $\max(2, d)$, where $d$ is the largest proper divisor of $n$. (Observe that this gives $\tfrac12n$ for $n$ even, as expected.) So, this gives a lower bound of $\max(4, 2d)$ on the degree. Unfortunately, if $n$ is odd, this is only sharp when $n = 3$ and $n = 5$. My guess is that the true answer is closer to $n-1$ then $\max(4, 2d)$, but I don't see any way to improve either side. Here's some commentary and some info about the development timeline of the problem, if you're curious. I've also attached my original proposal.

Awesome problem Ankan, my first thought when seeing it on contest was "What a cool statement, this must be revenge for the 2020 proposal!"

As a co-author of said ill-fated RMM 2020 proposal, I am very happy to see this problem make the test and be well-regarded while posing quite a challenge to contestants. It's always nice to vicariously live through a friend's cool problem on a contest. My solution is biased by the other problem, as I essentially just tried to rework the solution to that problem for this problem. The idea is to change to a polynomial in complex numbers, restrict to the unit circle, and apply the same arguments as RMM 2020 proposal: for the bound, show that we cannot distinguish a regular $2n$-gon from two copies of a regular $n$-gon with low degree, and for the construction, force Newton sums to vanish up to degree $n$ using some gadget to combine conditions. Here, we need to integrate positivity properties into the bound argument to double the degree, while the gadget for the construction is squared magnitudes rather than transcendental/large numbers. After solving the problem, I was somewhat surprised that it made the test given the similarities to the other proposal in both both statement and solution ideas, but from the scores it seems to have been hard for contestants and likely not affected things too much anyway. CantonMathGuy wrote: Unfortunately, if $n$ is odd, this is only sharp when $n = 3$ and $n = 5$. My guess is that the true answer is closer to $n-1$ then $\max(4, 2d)$, but I don't see any way to improve either side. Here is one idea which should yield a non-constant but likely not sharp lower bound: given a set $S$ of $k$ distinct points in the plane, find a degree lower bound on $P\in\mathbb R[x_1,\ldots,x_k,y_1,\ldots,y_k]$ such that $P(x_1,y_1,\ldots,x_k,y_k)$ vanishes if and only if $\{(x_1,y_1),\ldots,(x_k,y_k)\}=S$. Then fixing three vertices of the $n$-gon uniquely determines the rest of the vertices, and so this bound will apply with $k=n-3$. This bound will essentially ignore the structure of the regular $n$-gon, so it may be pretty far off from the truth. I imagine that the bound for an arbitrary set of points should still be nontrivial, but it may require some real algebraic geometry machinery which I am not familiar with. I think the other solutions above that use the complex change of coordinates have some bugs, unless I'm misunderstanding what they're saying. thevictor wrote: Step 2:We can represent $f$ as a symmetric polynomial of $z_k,\bar{z_k}$,where $z_k=x_k+iy_k$.(meaning it remains unchanged when swapping two indices) We can add all the $f$ permuting the $x_i$s and conclude easily since $f\ge 0$ and that the vertices of a $2n$-gon can permute to remain a $2n$-gon.

CANBANKAN wrote: We can see that $R$ vanishes whenever $x^n-1=0$. i.e. $x^n-1\mid R(x)$. We in fact prove something stronger, that $(x^n-1)^2 \mid R(x)$, which finishes the problem. I'm a bit confused what you mean here, since $R$ is a polynomial in both $x$ and $\bar x$. It does not follow here that $x^n-1\mid R(x,\bar x)$ in $\mathbb C[x,\bar x]$, since we only know that $R$ vanishes when $x^n=1$ and $x$ and $\bar x$ are complex conjugates, not when $x^n=1$ unconditional on $\bar x$. For example, the polynomial $P(x,\bar x)=|x^n-1|^2+||x|^2-1|^2$ vanishes only when $x^n=1$ and is positive everywhere else in $\mathbb C$, but $P(y,z)=(y^n-1)(z^n-1)+(yz-1)^2$ is not divisible by $y^n-1$ in $\mathbb C[y,z]$. Maybe this can be repaired with some scale/translation/rotation invariance arguments, but more is required here to conclude $x^n-1\mid R(x,\bar x)$. If you mean to restrict $x$ to the unit circle so $\bar x=x^{-1}$ and $R$ becomes a Laurent polynomial, then there is another issue: we cannot conclude from $(x^n-1)^2\mid R(x)$ that $\deg f\ge 2n$, only that $\deg f\ge n$. For instance, it is possible that $R(x)=x^n+x^{-n}-2$, which could result from having terms $z^n$ and $\bar z^n$ in $g$. This approach was one of my first attempts, but I couldn't get it to work all the way up to $2n$. Perhaps there is an alternate argument directly from here, but it seems like the issue is that fixing one of the $n$-gons destroys a lot of degree contributing terms in $g$. The way I got around this was to introduce a second variable to allow both $n$-gons to vary. Here is my solution, which hopefully correctly implements the idea to work with complex polynomials: The answer is $2n$. First, we note that the set of points $(x_1,y_1),\ldots,(x_{2n},y_{2n})$ that do not form a regular $2n$-gon is path-connected in $\mathbb R^{4n}$. This can be done by moving the points one by one continuously, and at each step there is at most one point to avoid to not make a regular $2n$-gon. Since $f$ does not vanish on this set, it must take the same sign on this set. Hence, we may WLOG assume that $f\ge0$. Now, we make a change of coordinates $(z,\bar z)=(x+iy,x-iy)$. This is a linear transformation that turns $f$ into a polynomial $g$ with complex coefficients in $z_1,\bar z_1,\ldots,z_{2n},\bar z_{2n}$ with the same degree as $f$. Furthermore, $g(w_1,\bar w_1,\ldots,w_{2n},\bar w_{2n})$ is a nonnegative real number for all $w_1,\ldots,w_{2n}\in\mathbb C$. Conversely, any such polynomial satisfying this property transforms under the inverse change of coordinates $(x,y)=\left(\frac{z+\bar z}2,\frac{z-\bar z}{2i}\right)$ back into a real polynomial because a polynomial with complex coefficients that is real on all real inputs has real coefficients. Now, we consider the Laurent polynomial $h(z_1,\ldots,z_{2n})=g(z_1,z_1^{-1},\ldots,z_{2n},z_{2n}^{-1})$. Note that for all $z_1,\ldots,z_{2n}$ with $|z_1|=\cdots=|z_{2n}|=1$, $h(z_1,\ldots,z_{2n})$ is a nonnegative real number, with $h(z_1,\dots,z_{2n})=0$ if and only if $z_1,\ldots,z_{2n}$ form a regular $2n$-gon. Hence, the two-variable Laurent polynomial $P(r,s)=h(r\omega,s\omega^2,\ldots,r\omega^{2n-1},s\omega^{2n})$, where $\omega=e^{\frac{2\pi i}{2n}}$, is nonnegative on unit circle inputs and vanishes when $r/s$ is an $n$th root of unity. We claim that $(r^n-s^n)^2\mid P(r,s)$ as Laurent polynomials. Indeed, we make a change of variables $t=r/s$ so that $P(r,s)=Q(r,t)$, so for all $|r|=|t|=1$, $Q(r,t)$ is a nonnegative real with $Q(r,t)=0$ whenever $t$ is an $n$th root of unity. In particular, for any fixed $r$ on the unit circle, $Q(r,t)$ is a Laurent polynomial in $t$ that vanishes at the $n$th roots of unity. Furthermore, the derivative along the unit circle, hence the complex derivative, vanishes at the $n$th roots of unity, so $(t^n-1)^2\mid Q(r,t)$ for each fixed $r$ on the unit circle. Because a Laurent polynomial in $r$ that vanishes for all $|r|=1$ is identically zero, this implies that $(t^n-1)^2\mid Q(r,t)$ as Laurent polynomials by a standard division algorithm argument. This is equivalent to $(r^n-s^n)^2\mid P(r,s)$ by changing coordinates back via $s=r/t$, as desired. Finally, $P$ is nonzero for $r/s$ not an $n$th root of unity, so it cannot be identically zero. Since it is divisible by $(r^n-s^n)^2$, there must be monomials $r^as^b$ and $r^cs^d$ with nonzero coefficients with $|a-c|+|b-d|\ge4n$. For example, consider such a monomial $r^as^b$ with $a$ maximal, and then $P$ must have a nonzero term with monomial $r^{a-m}s^{b+m}$ for some $m\ge2n$ by considering the homogenous component of $P$ with degree $a+b$. On the other hand, if $g$ has degree less than $2n$, then it can only produce nonzero terms in $P$ of the form $r^js^k$ with $|j|+|k|<2n$. For all $(a,b)$ and $(c,d)$ in this region we have $|a-c|+|b-d|<4n$, a contradiction. Thus, $\deg f=\deg g\ge 2n$. For the construction, we abbreviate by $w_i$ the quantity $z_i-\frac{z_1+\cdots+z_{2n}}{2n}$ for all $i$, representing the displacement of $z_i$ from the centroid of $z_1,\ldots,z_{2n}$. This is a linear transformation of $z_1,\ldots,z_{2n}$, so it suffices to construct a polynomial $Q$ in $w_1,\ldots,w_{2n},\bar w_1,\ldots,\bar w_{2n}$ of degree $2n$ that tests for $z_1,\ldots,z_{2n}$ being a $2n$-gon that is real on all complex inputs. We take \[Q(w_1,\ldots,w_{2n},\bar w_1,\ldots,\bar w_{2n})=\sum_{i\ne j}\left||w_i|^2-|w_j|^2\right|^2+\sum_{k=1}^n\left|w_1^k+\cdots+w_{2n}^k\right|^2.\]Note that this is indeed a polynomial in those variables because the squared magnitude of a complex number is equal to the product of it and its conjugate. Furthermore, $Q$ vanishes if and only if $|w_i|^2-|w_j|^2=0$ for all $i\ne j$ and $w_1^k+\cdots+w_{2n}^k=0$ for all $1\le k\le n$. This is clearly satisfied for any potentially degenerate regular $2n$-gon $z_1,\ldots,z_{2n}$. Conversely, $|w_i|^2-|w_j|^2=0$ implies that $w_1,\ldots,w_{2n}$ lie on a circle centered at $0$. If this circle is nondegenerate, then taking the conjugate of $w_1^k+\cdots+w_{2n}^k=0$ and renormalizing implies that $w_1^{-k}+\cdots+w_{2n}^{-k}=0$ as well. Hence, if $P(x)$ is the monic polynomial with roots $w_1,\ldots,w_{2n}$, then the coefficients of $x^{2n-1},\ldots,x^n$ in both $P(x)$ and $x^{2n}P(x^{-1})$ are zero, so the only nonzero coefficients in $P(x)$ are the leading and constant terms. It follows that $w_1,\ldots,w_{2n}$ are the $n$th roots of some complex number, which corresponds to $z_1,\ldots,z_{2n}$ being the vertices of a regular $2n$-gon, as desired.

I really thank ABCDE for pointing out my mistake. Here is my corrected proof of the bound: $f$ is either nonnegative or nonpositive in $\mathbb{R}^{4n}$ We will fix the first $3$ points $(x_1,y_1), (x_2,y_2), (x_3,y_3)$ such that there is no way we get a regular $2n$-agon (this occurs almost always). This means if there exists $(a_4,b_4),\cdots,(a_{2n},b_{2n})$ and $(c_4,d_4), \cdots, (c_{2n},d_{2n})$ such that $$f(a_1,\cdots,a_{2n},b_{2n}) > 0 > f(a_1, \cdots, b_3, c_4, \cdots, d_{2n})$$ Then let $v_1 = \langle a_1,\cdots,b_{2n}\rangle$, $v_2=\langle a_1,\cdots, b_3, c_4, d_4, \cdots, d_{2n} \rangle$, $h(t) = f(v_1+t(v_2-v_1))$ be a one variable polynomial, then $h(t) \ne 0$ for all $t\in [0,1]$. This contradicts the intermediate value theorem. We can use this to similarly get $f(v)\ge 0$ for all $v\in \mathbb{R}^{4n}$, or $f(v)\le 0$ for all $v\in \mathbb{R}^{4n}$ Step 2: Using two variables and Laurent Polynomial Manipulation . We first restrict $z_1,\cdots,z_{2n}$ to the unit circle. Hence our polynomial will be of the form $$g(z_1, z_1^{-1}, \cdots, z_{2n}, z_{2n}^{-1})$$ Furthermore, let $\omega=\exp(\frac{2\pi i}{n})$. We let $z_j=x\omega^{j-1}$ and $z_{n+j} = y\omega^{j-1}$ for $j=1,\cdots,n.$ We now view $g$ as a laurent polynomial $$P(x,y)=(x,x^{-1}, x\omega, (x\omega)^{-1}, \cdots, (x\omega^{n-1}), (x\omega^{n-1})^{-1}, y, y^{-1}, \cdots, (y\omega^{n-1}), (y\omega^{n-1})^{-1}) $$ $$\in \mathbb{C}[x,y,x^{-1},y^{-1}]$$ Clarifications on variables: $x,y,z$ will be variables that we will use to exhibit polynomials, and $r,s,\zeta,\omega$ will be values that we plug into the polynomials. The key claim is that there exists $T(x,y)\in \mathbb{C}[x,y,x^{-1},y^{-1}]$ such that $(x^n+y^n)^2 T(x,y)= P(x,y)$. We first prove a lemma. Lemma If $P(x,y)$ is a laurent polynomial such that if $r=\zeta s$ and $|r|=|s|=1$, then $P(r,s)=0$. Then there exists another laurent polynomial $R(x,y)$ such that $P(x,y)=(x-\zeta y)R(x,y)$. Proof of Lemma. Let $z=\frac yx$, and let $Q$ be another Laurent polynomial such that $Q(x,z)=P(x,y)$. We know that $Q(r,\zeta)=0$ for all $\zeta \in \{\omega, \omega^3, \cdots, \omega^{2n-1}\}$ and $|r|=1$. Fix $\zeta$. If $x^N Q(x,\zeta) \in \mathbb{C}[x]$, then since this polynomial has infinitely many roots, this is the zero polynomial, so $Q(r,\zeta)=0$ for all $r\in \mathbb{C}\setminus \{0\}$. Let $$Q(x,z) = \sum_j Q_j(z)x^j$$ For all $j$, we know that $Q_j(\zeta)=0$. Since $Q_j(z) \in \mathbb{C}[z,z^{-1}]$, we can show that there exists a polynomial $R_j(z)\in \mathbb{C}[z,z^{-1}]$ such that $Q_j(z) = (z-\zeta)R_j(z)$. Therefore, $$Q(x,z) = \sum_j Q_j(z)x^j = \sum_j (z-\zeta)R_j(z)x^j = (z-\zeta) \left( \sum_j R_j(z)x^j \right)$$ $$P(x,y)=Q\left(x,\frac yx\right) = \left( \frac yx - \zeta \right) \left( \sum_j R_j(y/x)x^j \right)$$ Our lemma is proven. Corollary If $P(x,y)$ is a laurent polynomial such that if $r^n+s^n=0$ and $|r|=|s|=1$, then $P(r,s)=0$. Then there exists another laurent polynomial $R(x,y)$ such that $P(x,y)=(x^n+y^n)R(x,y)$. We go back to the problem. Whenever $r^n+s^n=0$, we can see that $z_1,\cdots,z_{2n}$ is $r, r\exp(\frac{2\pi i}{2n}), \cdots, r\exp(\frac{2\pi i (2n-1)}{2n})$ in some order, which is indeed a regular $2n$-agon, so $P(r,s)=0$. By corollary 1, $P(r,s)=(r^n+s^n)T(r,s)$ for some laurent polynomial $T$. Furthermore, at any $(r,s)\in \mathbb{C}^2$ with $|r|=|s|=1$ and $r^n+s^n=0$, we can see that $\frac{\partial}{\partial s} P(r,s)=0$ because $P(r,s)=0$ and $P(r,t)\ge 0$ for all $|t-s| < \delta$ for some $\delta\in \mathbb{R}^+$ by step 1. This implies that (by the product rule) $$0=\frac{\partial P}{\partial y} (r,s) = (r^n+s^n) \frac{\partial T}{\partial y} (r,s) + T(r,s) \frac{\partial x^n+y^n}{\partial y}(r,s) = T(r,s)ns^{n-1}$$ Therefore, $T(r,s)=0$ whenever $r^n+s^n=1$. Applying corollary 1 once again yields $T(x,y)=(x^n+y^n)R(x,y)$ for some Laurent Polynomial $R$. It follows that $P(x,y) = (x^n+y^n)^2 R(x,y)$ for some Laurent Polynomial $R$, which completes step 2. Step 3: Degree bounding of $g$. We need to bound the degree of $g(z_1,z_1^{-1}, \cdots, z_{2n}, z_{2n}^{-1})$. Lemma A term $x^cy^d$ in $P$ corresponds to a term in $g$ with degree at least $|c|+|d|$. Proof of Lemma. A term $x^cy^d$ can map to $z_1^{a_1} z_1^{-a_2} \cdots z_{2n}^{a_{4n-1}} z_{2n}^{-a_{4n}}$ in $g$, which is a term of degree $\sum\limits_{j=1}^{4n} a_j$ (note $a_j\ge 0$ for all $1\le j\le 4n$). By comparing degrees, we can see that $\sum_{j=1}^{2n} (-1)^{j+1} a_j = c, \sum_{j=2n+1}^{4n} (-1)^{j+1} a_j=d$. Therefore, by triangular inequality, $$|c|+|d| \le \sum_{j=1}^{2n} |a_j| + \sum_{j=2n+1}^{4n} |a_j| = \sum_{j=1}^{4n} a_j$$ This proves our lemma. Now consider any term $(x^n+y^n)^2 x^ay^b = x^{2n+a}y^b + x^ay^{2n+b} + 2x^{n+a}y^{n+b}$. We can see that $$\max\{ |2n+a|+|b|, |a|+|2n+b| \} \ge \frac{|2n+a|+|b|+ |a|+|2n+b|}{2} $$ $$\ge \frac{|2n+a-a|+|2n+b-b|}{2} = 2n$$ Therefore, by our lemma, there exists at least one term of degree $\ge 2n$ in $g$. This proves our desired bound.

Nice lemma and corollary! My approach was the same, as I already applied it during constructing the original RMM 2019 P6.

Orzing CANBANKAN!!! I have a similar proof which have some errors to cbk firstly submitted. As we have a long talk,he teached me the corrected proof. What a beautiful solution!

Algebraic geometry？

I'll skip the lower bound since others have got that sorted. Suppose we can do better than $2n$. WLOG assume the points have centroid 0. First, make $f(x_1, y_1, x_2, y_2, ... , x_{2n}, y_{2n})=0$, and consider $f(\alpha x_1, \alpha y_1, \alpha x_2, \alpha y_2, ... , \alpha x_{2n}, \alpha y_{2n})$ using the same values for all $x_j$, $y_j$. This is a polynomial in $\alpha$, 0 for all $\alpha$, and so is identically 0. This implies that if $f_{d}$ represents all terms of $f$ with degree $d$, $f(x_1, y_1, ...)=0 \implies f_d(x_1, y_1, ...)=0$. Recast $f$ as a polynomial in $z_j$ and $\overline{z_j}$, where $z_j=x_j+iy_j$. (This is possible because $x_j=\frac{z_j+\overline{z_j}}{2}$ and $y_j=\frac{z_j-\overline{z_j}}{2i}$). Also note that terms of degree $d$ specifically give rise to other terms of degree $d$ so $f_d$ still makes sense. Let $z_{I_1}$ be the set of the first n points and $z_{I_2}$ the set of the last n points. Suppose that $z_{I_1}$ and $z_{I_2}$ form regular n-gons and $f(z_{I_1}, \overline{z_{I_1}}, z_{I_2}, \overline{z_{I_2}})=0$ by abuse of notation. Fix $z_{I_1}$ and $z_{I_2}$, and consider $f_{d}(q\cdot z_{I_1}, \overline{q\cdot z_{I_1}},\overline{q} \cdot z_{I_2}, \overline{\overline{q} \cdot z_{I_2}})$, where $q$ is an arbitrary complex number. This gives a homogenous polynomial $g$ of degree $d$ in $q$ and $\overline{q}$. Divide it by $\overline{q}^{d}$ to get a polynomial g in $\frac{q}{\overline{q}}=z$. Observe that as long as $z$ is a $2n$th root of unity, the points $q\cdot z_{I_1}$ and $\overline{q} \cdot z_{I_2}$ form a regular 2n-gon. Therefore, $g(z)=0$ for all 2nth roots of unity, however degree(g)=d<2n which implies that g is identically 0 and any value for $z=\frac{q}{\overline{q}}$ makes $f_{d}(q\cdot z_{I_1}, \overline{q\cdot z_{I_1}},\overline{q} \cdot z_{I_2}, \overline{\overline{q} \cdot z_{I_2}})=0$. This is true for all d, so $f(q\cdot z_{I_1}, \overline{q\cdot z_{I_1}},\overline{q} \cdot z_{I_2}, \overline{\overline{q} \cdot z_{I_2}})=0$. Choosing any value for $\frac{q}{\overline{q}}$ that is not a 2nth root of unity yields a set of points that is not a regular 2n-gon, but for which $f(q\cdot z_{I_1}, \overline{q\cdot z_{I_1}},\overline{q} \cdot z_{I_2}, \overline{\overline{q} \cdot z_{I_2}})=0$, a contradiction. So degree 2n is necessary.