[Algebra]
Problem: Let $n \geqslant 2$ be an integer, and let $f$ be a $4 n$-variable polynomial with real coefficients. Assume that, for any $2 n$ points $\left(x_{1}, y_{1}\right), \ldots,\left(x_{2 n}, y_{2 n}\right)$ in the plane, $f\left(x_{1}, y_{1}, \ldots, x_{2 n}, y_{2 n}\right)=0$ if and only if the points form the vertices of a regular $2 n$-gon in some order, or are all equal.



Determine the smallest possible degree of $f$.

Solution: The smallest possible degree is $2 n$. In what follows, we will frequently write $A_{i}=$ $\left(x_{i}, y_{i}\right)$, and abbreviate $P\left(x_{1}, y_{1}, \ldots, x_{2 n}, y_{2 n}\right)$ to $P\left(A_{1}, \ldots, A_{2 n}\right)$ or as a function of any $2 n$ points.



Suppose that $f$ is valid. First, we note a key property:



Claim (Sign of $f$ ). $f$ attains wither only nonnegative values, or only nonpositive values.



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}, \ldots, A_{2 n}$ from the negative value to the positive value without ever having them form a regular $2 n$-gon - a contradiction.



The strategy for showing $\operatorname{deg} f \geq 2 n$ is the following. We will animate the points $A_{1}, \ldots, A_{2 n}$ linearly in a variable $t$; then $g(t)=f\left(A_{1}, \ldots, A_{2 n}\right)$ will have degree at most $\operatorname{deg} f$ (assuming it is not zero). The claim above then 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 $\operatorname{deg} g \geq 2 n$, and so $\operatorname{deg} f \geq 2 n$.



Geometrically, our goal is to exhibit $2 n$ linearly moving points so that they form a regular $2 n$-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 $\frac{\pi}{n}$ with each other. Then, any point $P$ has a total of $2 n$ reflections in the mirrors, as shown below for $n=5$. (Some of these reflections may overlap.)



Draw the $n$ angle bisectors of adjacent mirrors. Observe that the reflections of $P$ form a regular $2 n$ gon if and only if $P$ lies on one of the bisectors.



We will animate $P$ on any line $\ell$ which intersects all $n$ bisectors (but does not pass through the origin), and let $P_{1}, \ldots, P_{2 n}$ be its reflections. Clearly, these are also all linearly animated, and because of the reasons above, they will form a regular $2 n$-gon exactly $n$ times, when $\ell$ meets each bisector. So this establishes $\operatorname{deg} f \geq 2 n$ for the reasons described previously.



Now we pass to constructing a polynomial $f$ of degree $2 n$ having the desired property. First of all, we will instead find a polynomial $g$ which has this property, but only when points with sum zero are input. This still solves the problem, because then we can choose



$$
f\left(A_{1}, A_{2}, \ldots, A_{2 n}\right)=g\left(A_{1}-\bar{A}, \ldots, A_{2 n}-\bar{A}\right)
$$



where $\bar{A}$ is the centroid of $A_{1}, \ldots, A_{2 n}$. This has the upshot that we can now always assume $A_{1}+\cdots+A_{2 n}=0$, which will simplify the ensuing discussion.



<img_3624>



We will now construct a suitable $g$ as a sum of squares. This means that, if we write $g=g_{1}^{2}+g_{2}^{2}+$ $\cdots+g_{m}^{2}$, then $g=0$ if and only if $g_{1}=\cdots=g_{m}=0$, and that if their degrees are $d_{1}, \ldots, d_{m}$, then $g$ has degree at most $2 \max \left(d_{1}, \ldots, d_{m}\right)$.



Thus, it is sufficient to exhibit several polynomials, all of degree at most $n$, such that $2 n$ points with zero sum are the vertices of a regular $2 n$-gon if and only if the polynomials are all zero at those points.







First, we will impose the constraints that all $\left|A_{i}\right|^{2}=x_{i}^{2}+y_{i}^{2}$ are equal. This uses multiple degree 2 constraints.



Now, we may assume that the points $A_{1}, \ldots, A_{2 n}$ all lie on a circle with centre 0 , and $A_{1}+\cdots+A_{2 n}=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}, \ldots, a_{2 n}$ are complex numbers of the same non-zero magnitude, and suppose that $a_{1}^{k}+\cdots+a_{2 n}^{k}=0, k=1, \ldots, n$. Then $a_{1}, \ldots, a_{2 n}$ form a regular $2 n$-gon centred 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}, \ldots, a_{2 n}$ lie on the unit circle. By Newton's sums, the $k$-th symmetric sums of $a_{1}, \ldots, a_{2 n}$ are all zero for $k$ in the range $1, \ldots, n$.



Taking conjugates yields $a_{1}^{-k}+\cdots+a_{2 n}^{-k}=0$, $k=1, \ldots, n$. Thus, we can repeat the above logic to obtain that the $k$-th symmetric sums of $a_{1}^{-1}, \ldots, a_{2 n}^{-1}$ are also all zero for $k=1, \ldots, n$. However, these are simply the $(2 n-k)$-th symmetric sums of $a_{1}, \ldots, a_{2 n}$ (divided by $a_{1} \cdots a_{2 n}$ ), so the first $2 n-1$ symmetric sums of $a_{1}, \ldots, a_{2 n}$ are all zero. This implies that $a_{1}, \ldots, a_{2 n}$ form a regular $2 n$-gon centred at the origin.



We will encode all of these constraints into our polynomial. More explicitly, write $a_{r}=x_{r}+y_{r} i$; then the constraint $a_{1}^{k}+\cdots+a_{2 n}^{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 \leq n$, so their squares are all of degree at most $2 n$.



To recap, taking the sum of squares of all of these constraints gives a polynomial $f$ of degree at most $2 n$ which works whenever $A_{1}+\cdots+A_{2 n}=0$. Finally, the centroid-shifting trick gives a polynomial which works in general, as wanted.

Final answer: $2n$