Fix an integer $n \geq 3$. Determine the smallest positive integer $k$ satisfying the following condition: For any tree $T$ with vertices $v_1, v_2, \dots, v_n$ and any pairwise distinct complex numbers $z_1, z_2, \dots, z_n$, there is a polynomial $P(X, Y)$ with complex coefficients of total degree at most $k$ such that for all $i \neq j$ satisfying $1 \leq i, j \leq n$, we have $P(z_i, z_j) = 0$ if and only if there is an edge in $T$ joining $v_i$ to $v_j$. Note, for example, that the total degree of the polynomial $$ 9X^3Y^4 + XY^5 + X^6 - 2 $$is 7 because $7 = 3 + 4$. Proposed by Andrei Chiriță, Romania
Problem
Source: RMM 2025 P3
Tags: algebra
13.02.2025 00:44
Let the edges of the tree be $(v_{i_1},v_{j_1})$, $(v_{i_2},v_{j_2})$, $\ldots$, $(v_{i_{n-1}},v_{j_{n-1}})$. We claim $k=n-1$. If $\omega$ is a positive $n$th root of unity, then let $z_m=\omega^{m-1}$, and let the tree have edges $(v_m,v_{m+1})$ for $1\leq m\leq n-1$. Then, $P(x,\omega x)=0$ for $x=1$, $\omega$, $\ldots$, $\omega^{n-2}$, but $P(\omega^{n-1},\omega^n)=P(z_n,z_1)\neq0$. Therefore, $P(x,\omega x)$ has at least $n-1$ roots, so it has degree at least $n-1$ as a polynomial in $x$ as it is nonconstant. This implies $\deg P\geq n-1$, so $k\geq n-1$. Now, we show $k=n-1$ is achievable. For each edge $(v_{i_a},v_{j_a})$, there are two corresponding solutions $P(z_{i_a},z_{j_a})=0$ and $P(z_{j_a},z_{i_a})=0$. For $1\leq m\leq2n-2$, let all of these solutions be $(z_{c_m},z_{d_m})=Z_m$. Let $S$ be the set of all matchings of all the elements of $\{Z_1,\ldots,Z_{2n-2}\}$. Let $C_A$ for $A\in S$ be constants that we will choose later. We claim $$P(x,y)=\sum_{A\in S}C_A\prod_{\{(z_a,z_b),(z_c,z_d)\}\in A}(x(z_b-z_d)-y(z_a-z_c)+z_az_d-z_bz_c)$$works. If $T$ has an edge $v_i$ to $v_j$, then for all $A\in S$, some element of $A$ contains $(z_i,z_j)$, making the product zero. Then, $P(z_i,z_j)=0$. We claim if there is no edge from $v_i$ to $v_j$, then not all terms of $P(z_i,z_j)$ are zero. Let pairs denote the pairs $Z_m=(z_{c_m},z_{d_m})$. Suppose for all $A\in S$, we have $$\prod_{\{(z_a,z_b),(z_c,z_d)\}\in A}(z_i(z_b-z_d)-z_j(z_a-z_c)+z_az_d-z_bz_c)=0.$$Then, for some $\{(z_a,z_b),(z_c,z_d)\}\in A$, the expression is $0$. This is equivalent to $$(z_i-z_a)(z_j-z_d)=(z_i-z_c)(z_j-z_b),$$so $f_{ij}(a,b)=(z_i-z_a,z_j-z_b)$ and $f_{ij}(c,d)=(z_i-z_c,z_j-z_d)$ are proportional, meaning there exists $C$ such that $C(z_i-z_a)=z_i-z_c$ and $C(z_j-z_b)=z_j-z_d$ as none of the tuples are $(0,0)$. In particular, this forms an equivalence relation. Therefore, if this is true for all $A\in S$, then every matching must have some two equivalent pairs together. Since $f_{ij}(a,b_1)\equiv f_{ij}(a,b_2)$ if and only if $b_1=b_2$, each class has at most $n$ pairs. If a class has $n$ pairs, then it must include tuples $f_{ij}(I,j')$ and $f_{ij}(i',j)$ for some $i'$ and $j'$. However, this means $(0,z_j-z_{j'})$ and $(z_i-z_{i'},0)$ are proportional, impossible as $j'\neq j$ and $i'\neq i$. Therefore, each class has at most $n-1$ pairs. Now, let the $2n-2$ pairs be listed $t_1$, $t_2$, $\ldots$, $t_{2n-2}$ such that all equivalent pairs are consecutive. Then, $(t_1,t_n)$, $(t_2,t_{n+1})$, $\ldots$, $(t_{n-1},t_{2n-2})$ forms a matching with no equivalent pairs, contradiction. Therefore, at least one term in $P(z_i,z_j)$ is nonzero if there is no edge $v_i$ to $v_j$ in $T$. Now, pick all $C_A$ independently and uniformly at random from $[0,1]$. The probability $P(z_i,z_j)=0$ if $(v_i,v_j)$ is not an edge is zero as at least one term is nonzero. Adding over all $1\leq i\neq j\leq n$ gives probability $0$ that any such $P(z_i,z_j0=0$. Therefore, there exists a choice of $C_A$ such that $P(z_I,z_j)=0$ if and only if $(v_i,v_j)$ is an edge. As $|A|=n-1$ and every term in the product is linear, $P$ is the sum of degree $n-1$ terms, so $\deg P=n-1$, which means $k\leq n-1$. Therefore, $\boxed{k=n-1}$.
13.02.2025 01:02
Proposed by Andrei Chiriță, from Romania! :)
13.02.2025 01:13
Remind me to never cook again.
13.02.2025 03:20
Spent 4.5 hours on the bound and got swept @3above: What was your motivation for linearly combining the products with randomly sampled weights? I thought that surely the content of the problem would be to carefully construct one particular product that only vanishes on the edges, since the sum of multiple nonzero numbers can still vanish. Or is it simply false that such a product even exists in the first place? For reference, here's my thought process: since I've never worked with multivariate polynomials before, I spent a long time trying to construct a global "marker" that would vanish if and only if $x=z_i$ and $y=z_j$. My trouble was that null product is an or gate rather than an and gate, e.g. $(x-z_i)(y-z_j)$ wouldn't work, and since we're working over $\mathbb{C}$ we can't exploit any sort of bound, e.g. $(x-z_i)^2+(y-z_j)^2$. However I soon realized that we only need the marker to locally distinguish over $i,j\in[n]^2$, and so by what I suppose is a "random sampling" (or simply a dimensionality check), there exist weights $a_{i,j},b_{i,j}\in\mathbb{C}$ such that the value $c_{i,j}:=a_{i,j}z_i+b_{i,j}z_j$ is unique across $[n]^2$. Hence, multiplying over all $e_{i,j}\in G$, we attain the following bound for $k\le2n-2$, \[P(x,y):=\prod_{e_{i,j}\in G}(a_{i,j}x+b_{i,j}y-c_{i,j}).\]It's pretty clear the above is suboptimal: we're wasting a lot of degrees of freedom by sampling two variables $a,b$ only to ensure uniqueness, and surely there is a way to "share" markers between pairs $(i,j)$. In fact, it is easy for two pairs $(i,j)$ and $(k,\ell)$ to share a marker, and intuitively that is optimal by linear algebra or something: \[az_{i_1}+bz_{j_1}=az_{i_2}+bz_{j_2}=az_{i_3}+bz_{j_3}\iff\det\begin{bmatrix}1&1&1\\z_{i_1}&z_{i_2}&z_{i_3}\\z_{j_1}&z_{j_2}&z_{j_3}\end{bmatrix}=0,\]which intuitively shouldn't happen often. So I claimed that for every $(i,j)$, there exists a $(k,\ell)$ such that their shared linear combination is unique between them, and in fact that we can pair these up into $n-1$ pairs. How does it even come into your mind to instead consider each pair $(i,j)$ which isn't in $G$ and showing that it can't share markers with all pairs of edges across all possible matchings? @above: I don't know if your solution explains it, but why are linear markers optimal? Towards the end I started to go delusional and started to cite some Brill-Noether $\tfrac{(d+1)(d+2)}{2}$ nonsense, which is definitely incorrect but at least intuitively seems better than linear markers. In particular with a linear marker $ax+by-c$, you can interpolate through only $2$ pairs (so the marker is locally unique on those pairs); but since a degree $d$ marker has $\tfrac{(d+1)(d+2)}{2}$ coefficients and so that many degrees of freedom, can't it interpolate through $\mathcal{O}(\tfrac{d^2}{2})$ pairs, which is much more efficient? Is there something inherent about the linear markers that ensures local uniqueness that higher degree markers cannot?
14.02.2025 12:43
On the contest I was only able to provide an upper bound for $n$, but with the slightest of changes it becomes a bound for $n-1$. Here it is: Consider set $S$ of polynomials that vanish on edges. If all directed not-edges not vanish at least once, we can surely take a linear combination of polynomials in $S$ that vanishes exactly on edges. Hence further we suppose that all polynomials in $S$ vanish on some directed not-edge. Add this directed not-edge to $T$. Interpolation fact: there exists a polynomial $P(x,y)$ of total degree at most $n-1$ with any values at points $(x_1,y_{11}),(x_1,y_{12}),\ldots,(x_1,y_{1n}),(x_2,y_{21},\ldots,(x_2,y_{2,n-1}),\ldots,(x_n,y_{n1})$ for any pairwise different $x_i$. (to prove just do induction on $n$). Now our idea is to somehow make all edges of $T$ be among the points of interpolation, then we can choose where it should be 0 and where it is non-zero. Draw an arrow from $z_i$ to $z_j$ if $(z_i,z_j)$ is a point of interpolation. Then by interpolation fact we are allowed to draw from vertices $1,2,\ldots,n$ arrows in some order. Our goal is for initial edges of $T$ to have arrows in both directions and for the new edge in one correct direction. Notice that the added edge lies in the only cycle in the graph. Lemma. it is possible to draw arrows in the way described above We prove it by induction on $n$. If there is a leaf, take the deepest one, consider its parent $A$. Let $A_1,\ldots,A_k$ be all leaf-children of $A$. Then draw all $n$ arrows from $A$ and $1,\ldots,k$ arrows from $A_1,\ldots,A_k$. Now we can remove $A,A_1,\ldots,A_k$ from the graph and proceed by induction hypothesis. If there are no leafs, we are left with a cycle. Let $XY$ be the only directed edge. Draw one arrow from $Y$ and $2,\ldots,n$ from other vertices - done. On the contest I used the weaker form of interpolation, where you take $(z_1,z_1),\ldots,(z_1,z_n),(z_2,z_1),(z_2,z_2),\ldots,(z_2,z_{n-1}),\ldots,(z_n,z_1)$, and hence for the cycle we can only state the bound for degree $n$. But the coordinators turned on the strict mode and said that interpolation facts for two variables are not obvious(may I remind you that it is RMM and they were shown the sketch of the proof in scratch papers), and they lack a lot of details(may I remind you that they can't read a word in my paper and themselves asked to hand them a translation of the main facts and ideas not necessarily word by word, and after a translation word by word of the main facts and ideas of proofs, with only the order of them being changed, they claim that the translation does not coincide with the paper. And also usually on olympiads like IMO people get almost full points when writing a solution in rush which can not be really restored without the author). For a long time they couldn't just admit the fact that a solution where $P$ is not symmetric might exist. I wrote that coefficients for merging exist which can be easily proven by induction, and they started arguing that they need the induction to be written explicitly, although in the official solution they aren't even fcking bothered by the need to prove merging, they literally just say that merging is possible. And the same proof as for merging has appeared in my paper but in the part which is not needed for the solution, hence they never read it. In the result I didn't even get half of the points for the upper bound(and every person I know who read it agreed that it deserves only a deduction of one point)! When it is literally done if you replace weak interpolation by strong interpolation! Sorry for that childish drama-queen angry reaction, but had to write it somewhere.
16.02.2025 20:27
(quotes slightly out of order) peace09 wrote: @3above: What was your motivation for linearly combining the products with randomly sampled weights? I thought that surely the content of the problem would be to carefully construct one particular product that only vanishes on the edges, since the sum of multiple nonzero numbers can still vanish. Or is it simply false that such a product even exists in the first place? Consider the $n=4$ case, with a line graph. If you're trying to make an explicit construction like $n=1,2,3$, you'll find that $(x+y-(z_1+z_2))(x+y-(z_2+z_3))(x+y-(z_3+z_4))$ almost works, except when $z_2+z_3=z_1+z_4$. Any other such explicit constructions involving only products seem to have some degenerate case where it does not work. peace09 wrote: However I soon realized that we only need the marker to locally distinguish over $i,j\in[n]^2$, and so by what I suppose is a "random sampling" (or simply a dimensionality check), there exist weights $a_{i,j},b_{i,j}\in\mathbb{C}$ such that the value $c_{i,j}:=a_{i,j}z_i+b_{i,j}z_j$ is unique across $[n]^2$. Hence, multiplying over all $e_{i,j}\in G$, we attain the following bound for $k\le2n-2$, \[P(x,y):=\prod_{e_{i,j}\in G}(a_{i,j}x+b_{i,j}y-c_{i,j}).\] For visualization, let the complex numbers be $1$, $2$, $\ldots$, $n$, so you're trying to find a polynomial which is zero on some points in the square from $(1,1)$ to $(n,n)$. I first had this construction, which is drawing diagonal lines through the grid. To reach the lower bound of $n-1$, instead of each line having one point, each line must have two points. If you're only trying to have one product, this seems like a very difficult geometry problem, but in $\mathbb C^2$, which seems horrible. Although it's true that the sum of nonzero numbers can be zero, this feels very unlikely to happen. Intuitively, it feels like some choice of weights should definitely be able to make all of them nonzero. The random variables are just an easy way to make this easy to make rigorous. peace09 wrote: For reference, here's my thought process: since I've never worked with multivariate polynomials before, I spent a long time trying to construct a global "marker" that would vanish if and only if $x=z_i$ and $y=z_j$. My trouble was that null product is an or gate rather than an and gate, e.g. $(x-z_i)(y-z_j)$ wouldn't work, and since we're working over $\mathbb{C}$ we can't exploit any sort of bound, e.g. $(x-z_i)^2+(y-z_j)^2$. Addition basically acts like an and gate that fails with a very small probability. peace09 wrote: It's pretty clear the above is suboptimal: we're wasting a lot of degrees of freedom by sampling two variables $a,b$ only to ensure uniqueness, and surely there is a way to "share" markers between pairs $(i,j)$. In fact, it is easy for two pairs $(i,j)$ and $(k,\ell)$ to share a marker, and intuitively that is optimal by linear algebra or something: \[az_{i_1}+bz_{j_1}=az_{i_2}+bz_{j_2}=az_{i_3}+bz_{j_3}\iff\det\begin{bmatrix}1&1&1\\z_{i_1}&z_{i_2}&z_{i_3}\\z_{j_1}&z_{j_2}&z_{j_3}\end{bmatrix}=0,\]which intuitively shouldn't happen often. So I claimed that for every $(i,j)$, there exists a $(k,\ell)$ such that their shared linear combination is unique between them, and in fact that we can pair these up into $n-1$ pairs. How does it even come into your mind to instead consider each pair $(i,j)$ which isn't in $G$ and showing that it can't share markers with all pairs of edges across all possible matchings? The main motivation comes from the and gate observation earlier. My first construction with this idea took only horizontal and vertical lines, but only using horizontal and vertical lines does not seem enough. However, the and gate observation means that you can take the and of all possible matchings, and a point needs to be on all of the lines to be a zero. Now, the visualization is very helpful to try to prove this fact.
15.02.2025 01:00
15.02.2025 01:05
IAmTheHazard wrote: If $c=0$, then $P(0,y)=yQ(0,y)$ vanishes when $y=0$ and when $y \in \{z_1,\ldots,z_{n-1}\}$. But $Q$ must also be nonzero, so it actually has degree at least $n$. Nope, you missed the possibility $Q(x,y)=x$.
15.02.2025 02:08
atdaotlohbh wrote: IAmTheHazard wrote: If $c=0$, then $P(0,y)=yQ(0,y)$ vanishes when $y=0$ and when $y \in \{z_1,\ldots,z_{n-1}\}$. But $Q$ must also be nonzero, so it actually has degree at least $n$. Nope, you missed the possibility $Q(x,y)=x$. fixed
16.02.2025 02:34
This is my problem! I'm really proud of it and I think it's so well-fitting for RMM.
16.02.2025 10:12
The answer is $k=\boxed{n-1}$. First, we will show that $k\ge{}n-1$. We will pick $z_1,z_2,\cdots,z_n$ in the following manner. We will first define $z_k=z_{k+n}$ for all integers $k$. Let $\gamma$ be any conic symmetric about the line $x=y$. Define $f$ and $g$ as the involutions on $\gamma$ given by projecting through the points at infinity on the $x$ and $y$ axes, respectively. Then, we will pick a point $P=\left(z_n,z_1\right)$ on $\gamma$ and define $z_k$ for positive integers $k$ recursively such that $\left(z_{2k},z_{2k-1}\right)=f\left(\left(z_{2k-2},z_{2k-1}\right)\right)$ and $\left(z_{2k-1},z_{2k}\right)=g\left(\left(z_{2k-1},z_{2k-2}\right)\right)$. Then, we see that this construction suffices if and only if when $h=g\circ{}f$ we have that $P$ is a fixed point of $h^n$ and all of $z_1,z_2,\cdots,z_n$ are distinct when $n$ is odd. When $n$ is even, the same construction works if we have $h^{\frac{n}{2}}$ instead of $h^n$. We will choose $\gamma$ such that $h^n$ is the identity on $\gamma$ but $h^k$ and $f\circ{}h^k$ are not for $k=1,2,\cdots,n-1$. Then, we see that $P$ is a fixed point of $h^n$ and all of the points $\left(z_1,z_n\right),\left(z_2,z_1\right),\left(z_2,z_3\right),\cdots,\left(z_{n-1},z_n\right)$ are distinct for some choice of $P$, so $z_1,z_2,\cdots,z_n$ are distinct. Now, we will show that we can pick such a $\gamma$. We will affine transform $\gamma$ to a circle sending the points at infinity on the $x$ and $y$ axes to $\infty_X$ and $\infty_Y$, respectively. Then, we see that if $Q=f(P)$ and $R=h(P)$ then $\angle{}PQR=\angle\infty_XQ\infty_Y$ is a function $\alpha$ of $\gamma$, so $h$ is a rotation of $2\alpha\left(\gamma\right)$ around the center of $\gamma$. Varying $\gamma$ so that $\alpha\left(\gamma\right)=\left(\tfrac{180}{n}\right)^\circ$ gives the desired $\gamma$, as then $h^k$ is a rotation which is not the identity and $f\circ{}h^k$ is a reflection which is not the identity for $k=1,2,\cdots,n-1$. Now, let $T$ be a path from $v_1$ to $v_2$ and so on until $v_n$. Note that the degree $k$ curve $P(x,y)=0$ does not intersect $\gamma$ at $\left(x_n,x_1\right)$ or $\left(x_1,x_n\right)$, so by Bezout's theorem we see that it must intersect $\gamma$ at at most $2k$ points. However, we see that $P(x,y)=0$ intersects $\gamma$ at the $2(n-1)$ points $\left(x_k,x_{k+1}\right)$ and $\left(x_{k+1},x_k\right)$ for $k=1,2,\cdots,n-1$, so $k\ge{}n-1$. To show that $k=n-1$ suffices, we will show that there exist polynomials $Q(x,y)$ with complex coefficients and degree at most $k$ such that $Q\left(z_j,z_k\right)=0$ for all distinct $j,k\in\left\{1,2,\cdots,n\right\}$ with $v_j$ and $v_k$ connected but $Q\left(z_j,z_k\right)\ne0$ for some specific distinct $j,k\in\left\{1,2,\cdots,n\right\}$ so that $v_j$ and $v_k$ are not connected. Then, we can take a sufficient linear combination of these $Q$ to get the desired polynomial $P$. Let the $n-1$ points $\left(z_j,z_k\right)$ for all $j,k\in\left\{1,2,\cdots,n\right\}$ with $v_j$ and $v_k$ connected and $j<k$ be colored red, and let their reflections over $x=y$ be colored green. We will construct these $Q$ by taking $n-1$ lines joining pairs of red points $\left(z_a,z_b\right)$ and $\left(z_c,z_d\right)$ with $a,b,c,d\in\left\{1,2,\cdots,n\right\}$ and $a<b$ but $c>d$. For this to not work, we must have that all such $Q$ pass through a specific point $\left(z_j,z_k\right)$ for some distinct $j,k\in\left\{1,2,\cdots,n\right\}$ with $v_j$ and $v_k$ not connected. Let this point be $P$. Consider the bipartite graph on the red points and the green points so that a red point and a green point are not connected if and only if the line through them does not pass through $P$. We must not have a perfect matching on this graph, so by Hall's marriage theorem we see that there must exist $x$ red points which are connected to less than $x$ green points, so they are not connected to more than $n-x$ green points for some positive integer $x\le{}n$. Consider a red point $Q$ out of these $x$ red points. Then, we see that the line $\overline{PQ}$ passes through the more than $n-x$ green points. This implies that the more than $n$ red and green points out of the $x$ red points and more than $n-x$ green points all lie on a line through $P$. However, this means that at least $n+2$ of the points $\left(z_j,z_k\right)$ with $j,k\in\left\{1,2,\cdots,n\right\}$ are collinear, a contradiction, so we are done.