Sets with Polynomials

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

20 users

TOPICS

No tags match your search

M

No tags match your search

M

Sets with Polynomials

G H J

Reveal topic tags

IMO Shortlist 2020

linear combination

L

G H BBookmark kLocked kLocked NReply

Source: ISL 2020 A2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

476 posts

#1 h Jul 20, 2021, 9:06 PM • 4 Y

Y by centslordm, Steve12345, HWenslawski, megarnie

Let $\mathcal{A}$ denote the set of all polynomials in three variables $x, y, z$ with integer coefficients. Let $\mathcal{B}$ denote the subset of $\mathcal{A}$ formed by all polynomials which can be expressed as
$\begin{align*} (x + y + z)P(x, y, z) + (xy + yz + zx)Q(x, y, z) + xyzR(x, y, z) \end{align*}$ with $P, Q, R \in \mathcal{A}$ . Find the smallest non-negative integer $n$ such that $x^i y^j z^k \in \mathcal{B}$ for all non-negative integers $i, j, k$ satisfying $i + j + k \geq n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

701 posts

#2 h Jul 20, 2021, 9:06 PM • 3 Y

Y by centslordm, HWenslawski, Want-to-study-in-NTU-MATH

solution

This post has been edited 1 time. Last edited by cadaeibf, Jul 20, 2021, 9:12 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

538 posts

#3 h Jul 20, 2021, 9:27 PM • 1 Y

Y by centslordm

Note that the following much harder (and much nicer!) generalization of the problem was given in the comments in the shortlist packet. I'm not sure if this is the exact wording (in fact, the official version might replace $100$ with a variable integer $n$ ). Amusingly, there is actually a solution which uses the fact that $101$ is prime, though this is not necessary for the problem to hold.

Let $\mathcal{A}$ denote the set of polynomials in $100$ variables $x_1, \ldots , x_{100}$ with integer coefficients. Find the smallest integer $N$ such that any monomial $x_1^{e_1}x_2^{e_2}\cdots x_{100}^{e_{100}}$ with $e_1 + e_2 + \ldots + e_{100} \ge N$ can be expressed in the form
$p_1q_1 + p_2q_2 + \ldots + p_{100}q_{100}$ where $p_i, q_i \in A$ for all $i$ , $q_i$
is a symmetric polynomial for all $i$ , and $q_i(0, 0, . . . , 0) = 0$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#4 h Jul 20, 2021, 9:43 PM • 2 Y

Y by centslordm, Want-to-study-in-NTU-MATH

I claim $n=4$ .

Part 1: Proving $n>3$ .

I claim that $x^2y$ (n=3) is unexpressable.This follows from the following lemma

Lemma: For all polynomials of the form
$f(x,y,z)=(x+y+z)\cdot P(x,y,z)+(xy+yz+zx)\cdot Q(x,y,z)+xyzR(x,y,z)$ it is true that in $f$
$(\text{ coef of } x^2y)+(\text{ coef of } y^2z)+(\text{ coef of } y^2z) = (\text{ coef of } xy^2)+(\text{ coef of } yz^2)+(\text{ coef of }x^z)$ where $\text{ coef of } x^ay^bz^c$ is the coefficient of the $x^ay^bz^c$ term in $f(x,y,z)$

Proof: Since all involved are 3rd degree, we will verify 2nd degree $P(x,y,z)$ and 1st degree $Q(x,y,z)$ , and all other terms in $P,Q,R$ will never contribute to any of the coefficients.

i) $P(x,y,z)=x^2$
$(x+y+z)x^2=x^3+x^2y+x^2z$ This will contribute equally to both sides $(x^2y, x^2z)$

ii) $P(x,y,z)=xy$
$(x+y+z)xy = x^2y+xy^2+xyz$ this will also contribute to both sides equally.

iii) $Q(x,y,z)=x$
$(xy+yz+zx)\cdot x = x^2y+xyz+x^2z$ this will also contribute equally.

All other deg =2 $\in P(x,y,z)$ terms and deg =1 $\in Q(x,y,z)$ terms follow from symmetry. Thus, for all monomials in $P,Q,R$ the Lemma is true, and since the lemma is preserved under the addition of two lemma-compliant polynomials, all $f(x,y,z)$ are lemma-compliant. $\blacksquare$ .

Now, from this it clearly follows that $f(x,y,z)=x^2y$ is impossible because $1=(\text{ coef of } x^2y)+(\text{ coef of } y^2z)+(\text{ coef of } y^2z) = (\text{ coef of } xy^2)+(\text{ coef of } yz^2)+(\text{ coef of }x^z)=0$
Thus, $1=0$ , absurd.

Part 2: $n=4$ works We only need to verify $x^iy^jz^k$ for $i\geq j\geq k$ . Note that dealing with $i+j+k=4$ will clearly also give us all higher degree solutions by just multiplying by some type of $x^ay^bz^c$ .

i) $i=4$ ; $x^4$
$(x+y+z)x^3-(xy+yz+xz)x^2+xyzx=x^4$
ii) $i=3,j=1;x^3y$
$(x+y+z)x^2y-(xy+yz+xz)xy+xyz\cdot y = x^3y$
iii) $i=2,j=2;x^2y^2$
$xy(xy+yz+xz)-(x+y)(xyz)=x^2y^2$
iv) $i=2,j=2,k=1;x^2yz$ ,
$x\cdot xyz = x^2yz$
Thus, for all $i+j+k=4, i\geq j\geq k$ , $x^iy^jz^k$ is expressable, so $n\geq 4$ clearly works and we are done. $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1247 posts

#5 h Jul 20, 2021, 10:50 PM • 1 Y

Y by centslordm

Is anything known about the ring $\mathbb{Z}[x,y,z]/(x+y+z,xy+yz+zx,xyz)$ (or the general case in #3)? The problem implies that the ring is nilpotent and gives a bound on the indices of elements.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1963 posts

ABCDE

#6 h Jul 20, 2021, 11:22 PM • 4 Y

Y by Th3Numb3rThr33, PRMOisTheHardestExam, golue3120, MatteD

Th3Numb3rThr33 wrote:

Is anything known about the ring $\mathbb{Z}[x,y,z]/(x+y+z,xy+yz+zx,xyz)$ (or the general case in #3)? The problem implies that the ring is nilpotent and gives a bound on the indices of elements.

There are some representation theoretic connections. The codimension of the space of homogenous polynomials of degree $k$ that can be expressed in the given form is equal to the coefficient of $q^k$ in $(1+q)(1+q+q^2)...(1+q+...+q^{n-1})=n!_q$ . According to Ricky Liu, it is related to coinvariants and the Chevalley-Shephard-Todd theorem from invariant theory. This blog post also says something about this.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#7 h Jul 20, 2021, 11:25 PM • 1 Y

Y by Want-to-study-in-NTU-MATH

The answer is $4$ .

Proof of Bound It suffices to show $x^2y$ is not expressible. Suppose it was. Plugging in $z=-x-y$ gives
$\big(xy-(x+y)^2\big)Q(x,y,-x-y) + xy(-x-y)P(x,y,-x-y)=x^2y.$ Since the RHS is degree $3$ , all non-degree $3$ terms on the LHS must be $0$ . Only considering the degree $3$ terms on the LHS, we have
$(x^2+xy+y^2)(c_1x + c_2y) + xy(x+y)d_1 = x^2y$ for some constants $c_1,c_2,d_1$ . Expanding, notice that the coefficients of $x^2y$ and $xy^2$ are equal on the LHS, contradiction. Therefore, no $n\le 3$ works.

Construction We show that any monomial of degree $n\ge 4$ is expressible. Call it $x^ay^bz^c$ .

Case 1: $a,b,c\ge 1$ . This is divisible by $xyz$ , so just use $R$ .
Case 2: and $a,b\ge 1$ . (Other such cases follow by symmetry.)
- Subcase 2.1: $a,b\ge 2$ . Then $x^ay^b=x^{a-1}y^{b-1}(xy+yz+zx)-(x^{a-2}x^{b-1}-x^{a-1}y^{b-2})xyz.$
- Subcase 2.2: $a=1$ and $b\ge 2$ . (The case $b=1$ and $a\ge 2$ is analogous.) In fact, $b\ge 3$ since $xy^b$ must have degree at least $4$ . Notice $xy^b=xy^{b-1}(x+y+z)-x^2y^{b-1} - xy^{b-1}z.$ The second term is expressible from Subcase 2.1, and the last term is divisible by $xyz$ , done.
Case 3: $c=0,b=0,a\ge 4$ . (Other such cases follow by symmetry.) We want to construct $x^a$ . Notice $x^a=(x+y+z)x^{a-1} - x^{a-1}y - x^{a-1}z.$ The final two terms are expressible by Subcase 2.2, and we are done.

In all cases, $x^ay^bz^c$ is expressible, so we have proved the construction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1753 posts

#8 h Jul 20, 2021, 11:47 PM • 7 Y

Y by rama1728, sabkx, Zsigmondy, IAmTheHazard, LLL2019, axolotlx7, Kingsbane2139

spartacle wrote:

Let $\mathcal{A}$ denote the set of polynomials in $100$ variables $x_1, \ldots , x_{100}$ with integer coefficients. Find the smallest integer $N$ such that any monomial $x_1^{e_1}x_2^{e_2}\cdots x_{100}^{e_{100}}$ with $e_1 + e_2 + \ldots + e_{100} \ge N$ can be expressed in the form
$p_1q_1 + p_2q_2 + \ldots + p_{100}q_{100}$ where $p_i, q_i \in A$ for all $i$ , $q_i$
is a symmetric polynomial for all $i$ , and $q_i(0, 0, . . . , 0) = 0$ .

The answer is $\binom{100}2+1=4951$ .

\bigskip

Proof $N\ge4951$ work: I contend we can express all monomials of degree $e_1+\cdots+e_{100}\ge4951$ in the form $p_1S_1+p_2S_2+\cdots+p_{100}S_{100},$ where $S_i$ is the $i$ th elementary symmetric polynomial ( $S_1=x_1+\cdots+x_{100}$ , $S_2=x_1x_2+\cdots+x_{99}x_{100}$ , etc.).

Say the character of a monomial $x_1^{e_1}\cdots x_{100}^{e_{100}}$ is $e_1^2+e_2^2+\cdots+e_{100}^2$ . We will strong induct on character, with the base case as follows: If all 100 variables appear with positive exponent, we are done by factoring out $x_1x_2\cdots x_{100}$ .

Now assume without loss of generality $e_1\ge e_2\ge\cdots\ge e_{100}=0$ . We can find an $i$ with $e_{i+1}\le e_i-2$ ; otherwise, $e_{100}=0$ , $e_{99}\le1$ , $e_{98}\le2$ , \ldots, and thus $e_1+\cdots+e_{100}\le4950$ , contradiction. Then subtract off $x_1^{e_1-1}x_2^{e_2-1}\cdots x_i^{e_i-1}x_{i+1}^{e_{i+1}}x_{i+2}^{e_{i+2}}\cdots x_{100}^{e_{100}}\cdot S_i.$ The remaining monomials have strictly smaller character, so by the inductive hypothesis they are already expressible in the desired form. \bigskip

Proof $N=4950$ fails: I claim the monomial $x_2^1x_3^2\cdots x_{100}^{99}$ does not have this property.

Decompose the polynomials $p_i$ into monomials and $q_i$ into homogeneous polynomials, so we have $x_2^1x_3^2\cdots x_{100}^{99}=\sum_ip_i(x_1,\ldots,x_{100})\cdot q_i(x_1,\ldots,x_{100}),$ with $p_i$ monomials and $q_i$ homogeneous and symmetric. Ignore all terms where $\deg p_i+\deg q_i\ne4950$ , so all terms in the expansion have degree 4950.

Now consider the following, where we sum over permutations $\pi$ of $\{1,\ldots,100\}$ : $\sum_\pi\operatorname{sgn}(\pi)\cdot x_{\pi(2)}^1\cdots x_{\pi(100)}^{99} =\sum_iq_i(x_1,\ldots,x_{100})\cdot\sum_\pi p_i(x_{\pi(1)},\ldots,x_{\pi(100)})\cdot\operatorname{sgn}(\pi),$ However, observe the following:

Claim: If $p_i$ is a monomial with $\deg p_i\le4949$ , then $\sum_\pi p_i(x_{\pi(1)},\ldots,x_{\pi(100)})\cdot\operatorname{sgn}(\pi)=0.$
Proof. Two exponents must be equal; otherwise, $\deg p_i\ge0+1+\cdots+99=4950$ , contradiction. If the exponents of $x_i$ and $x_j$ are equal, we can pair permutations that swap $i$ and $j$ , which will cancel out in the summation. $\blacksquare$

It follows that $\sum_\pi\operatorname{sgn}(\pi)\cdot x_{\pi(2)}^1\cdots x_{\pi(100)}^{99}\equiv0,$ which is absurd.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

138 posts

sman96

#9 h Jul 21, 2021, 5:22 AM • 1 Y

Y by Springles

$\underline{\textbf{Answer:}}$ The smallest possible value for $n$ is $4$ .

$\underline{\textbf{Proof:}}$

$\boxed{\text{\underline{Claim 1:} For all } i+j+k \geq 4, \ x^iy^jz^k \in \mathcal{B} }$
Proof for claim:
$\boxed{\text{\underline{Case 1:}}\ i,j,k \geq 1}$
In this case we are done by taking, $P(x,y,z) = 0 ; \ Q(x,y,z) = 0 ;\ R(x,y,z) = x^{i-1}y^{j-1}z^{k-1}$ $\boxed{\text{\underline{Case 2:}} \ k=0,i\geq 3,j\geq 0}$ [And symmetrically others]
Here we can take, $P(x,y,z) = x^{i-1}y^{j} ;\ Q(x,y,z) = -x^{i-2}y^{j} ;\ R(x,y,z) = x^{i-3}y^{j}$ $\boxed{\text{\underline{Case 3:}} \ k=0,i\geq 2,j\geq 2}$ [And symmetrically others]
In this case we can take, $P(x,y,z) = 0 ;\ Q(x,y,z) = x^{i-1}y^{j-1} ;\ R(x,y,z) = -(x^{i-2}y^{j-1} + x^{i-1}y^{j-2})$

$\boxed{\text{\underline{Claim 2:}} \ x^2y \notin \mathcal{B}}$
Proof for claim: For the sake of contradiction let's assume that $x^2y \in \mathcal{B}$
So, $x^2y = (x+y+z)P(x,y,z) + (xy+yz+zx)Q(x,y,z) + xyzR(x,y,z)$ for some $P,Q,R \in \mathcal{A}$ .
Here, the term $x^2y$ must be generated from $(x+y+z)P(x,y,z) \text{ or } (xy+yz+zx)Q(x,y,z)$ .
$\boxed{\text{\underline{Case 1:}} \ x^2y \text{ is generated from } (x+y+z)P(x,y,z)}$
For this there must be a term $xy$ or $x^2$ in $P(x,y,z)$ . But the coefficient of $x^2$ in $P(x,y,z)$ must be equal to the coefficient of $x^3$ in expression $(x+y+z)P(x,y,z) + (xy+yz+zx)Q(x,y,z) + xyzR(x,y,z)$ so it must be $0$ [Same for coefficient of $y^2,z^2$ in $P(x,y,z)$ ].
So, there must be a term $xy$ in $P(x,y,z)$ which generates $x^2y+xy^2+xyz$ . Now to cancel out term $xy^2$ there must be $-y$ in $Q(x,y,z)$ and that generates $-xy^2-y^2z-xyz$ .Again to cancel out term $-y^2z$ we need $yz$ in $P(x,y,z)$ and continuing this process will eventually generates $xy+yz+zx$ in $P(x,y,z)$ and $(-x-y-z)$ in $Q(x,y,z)$ . So in $(x+y+z)P(x,y,z) + (xy+yz+zx)Q(x,y,z)$ they all cancel out each other and results in a $0$ .

$\boxed{\text{\underline{Case 2:}} \ x^2y \text{ is generated from } (xy+yz+zx)Q(x,y,z)}$
As the same, we need a term $x$ in $Q(x,y,z)$ and to cancel out the term $zx^2$ we need $-xz$ in $P(x,y,z)$ and as in Case 1, continuing this process also results in a $0$ . And we are done. $\blacksquare$

This post has been edited 1 time. Last edited by sman96, Jul 21, 2021, 6:19 AM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5007 posts

#10 h Jul 27, 2021, 10:04 PM

Y by

The answer is $4$ . Note that
$\begin{align*} (x+y+z)x^2-(xy+yz+zx)x+xyz&=x^3\\ (xy+yz+zx)xy-xyz(x+y)&=x^2y^2\\ xyz&=xyz. \end{align*}$ Of course, symmetrical variants also hold. Since $x^iy^jz^k \in \mathcal{B} \implies x^{i+1}y^jz^k \in \mathcal{B}$ , and the same for $y$ and $z$ , so it follows that $4$ works. I will now show that $x^2y \not \in \mathcal{B}$ , so $3$ fails. Suppose otherwise; let $P'(x,y,z)$ be the polynomial obtained by taking only the degree $2$ terms of $P(x,y,z)$ , $Q'(x,y,z)$ be the polynomial obtained by taking the degree $1$ terms of $Q(x,y,z)$ , and $R'(x,y,z)$ be the polynomial obtained by taking the degree $0$ (constant) terms of $R(x,y,z)$ . Then we have
$(x+y+z)P'(x,y,z)+(xy+yz+zx)Q'(x,y,z)+xyzR'(x,y,z)=x^2y.$ By considering the $x^3,y^3,z^3$ coefficients of the LHS, we find that $P'(x,y,z)$ is of the form $axy+byz+czx$ . Now let $Q'(x,y,z)=dx+ey+fz$ and $R'(x,y,z)=g$ , where $a,b,c,d,e,f,g \in \mathbb{Z}$ . Then the LHS is equal to
$(a+d)x^2y+(b+e)y^2z+(c+f)z^2x+(a+e)xy^2+(b+f)yz^2+(c+d)zx^2+(a+b+c+d+e+f+g)xyz.$ Equating coefficients, we find that $a+e=b+f=c+d=0 \implies a+b+c+d+e+f=0$ , but also $a+d=1,b+e=c+f=0 \implies a+b+c+d+e+f=1$ , which is a clear contradiction, so $x^2y \not \in \mathcal{B}$ and we're done. $\blacksquare$

Remark: No idea why integer coefficients are specified. Even complex-coefficient polynomials are fine?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1189 posts

L567

#11 h Jul 29, 2021, 9:36 AM

Y by

I claim the answer is $n = 4$

To show that this is possible, note the identities $x^3y = (x+y+z)(x^2y) + (xy+yz+zx)(-xy) + (xyz)(-x)$
and $x^2y^2 = (x+y+z)(x^2y+x^2z) + (xy+yz+zx)(-x^2-xz) + (xyz)(-z)$
To get any other thing, just multiply one of these or their permutations by $x,y,z$ etc.

Now, I claim $x^2y \notin B$ , which will finish the problem. Suppose it was possible.

First, see that we $P$ cannot have any term that contains only one of $x,y,z$ , for example suppose it had $x^p$ , then there is a term of $x^p$ in the whole expression, which is going to remain and not get cancelled off.

Suppose $P = axy + byz + czx + P'(x,y,z)$ and $Q = px + qy + rz + Q'(x,y,z)$

Now, we must have $xyz | (x+y+z)P+(xy+yz+zx)Q-x^2y$ , for it to be possible

But see that this means

$xyz | (ax^2y + cx^2z + axy^2 + by^2z + byz^2 + cxz^2) + (px^2y + px^2z + qy^2x + qy^2z + rz^2x + rz^2y) - (x^2y) + X$ where $X$ is a bunch of terms, not containing any term of the form $x^2y$ or its permutations.

So, for this to be divisible by $xyz$ , the first part must be $0$

So, we must have $a + p = 1, c+p = 0, a+q = 0, b+q = 0, b+r = 0, c+r = 0$ , which is impossible since it means $a = 1 - p = 1 -(-c) = 1+c = 1-r = 1+b = 1-q = 1+a$ , a contradiction.

This means this is impossible and so the least value of $n$ is indeed $4$ , as claimed. $\blacksquare$

This post has been edited 1 time. Last edited by L567, Nov 20, 2021, 1:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1481 posts

CT17

#12 h Jul 30, 2021, 2:00 AM

Y by

We claim $4$ is the smallest value of $n$ . First we prove sufficiency. Clearly we can assume WLOG that $i\le j\le k$ .

If $i,j,k\ge 1$ , we can set $P = 0$ , $Q = 0$ , and $R = x^{i-1}y^{j-1}z^{k-1}$ .

If $i=0$ and $j,k\ge 2$ , we can set $P = 0$ , $Q = y^{j-1}z^{k-1}$ , and $R =-y^{j-2}z^{k-1}-y^{j-1}z^{k-2}$ .

If $i=0$ , $j=1$ , and $k\ge 3$ , we can set $P = yz^{k-1}$ , $Q = -yz^{k-2}$ , and $R = yz^{k-3}$ .

If $i = j = 0$ and $k\ge 4$ , we can set $P = z^{k-1}$ , $Q = -z^{k-2}$ , and $R = z^{k-3}$ .

To prove necessity, let $S = \{xy^2,yx^2,xz^2,zx^2,yz^2,zy^2\}$ and let $R(x,y,z)$ be a monomial with coefficient $1$ such that either $R(x,y,z)(x+y+z)$ or $R(x,y,z)(xy+xz+yz)$ has a term in $S$ . Then, by symmetry, that product has $2$ terms in $S$ , so the expression in the problem contains an even number of elements of $S$ . It follows that the expression cannot equal any element of $S$ , and hence $n\ge 4$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2811 posts

#13 h Jul 31, 2021, 6:26 PM

Y by

I claim the answer is $\boxed{4}$ . We will provide a construction by observing cases.

If $i,j,k \ge 1$ , then $(P(x,y,z),Q(x,y,z),R(x,y,z)) = (0,0,x^{i-1}y^{j-1}z^{k-1})$ will work.

If $i \ge 1$ , $j \ge 3$ , and $k=0$ , then $(P(x,y,z),Q(x,y,z),R(x,y,z)) = (x^{i+1}y^{j-2},-x^{i}y^{j-2},y^{j-2})$ will work.

Finally, if $i=0,j=0$ and $k \ge 4$ the construction $(x^{k-1},-x^{k-2},x^{k-2})$ will work.

These three cases and their symmetries are enough to show that our answer is a valid construction. Next, we desire to show that $4$ is the minimal value of $n$ . It is enough to show that $x^2y \neq (x + y + z)P(x, y, z) + (xy + yz + zx)Q(x, y, z) + xyzR(x, y, z)$ for any polynomials $P(x,y,z),Q(x,y,z),R(x,y,z)$ .

To begin, note that $x^2y$ is either "from" $(x + y + z)P(x, y, z)$ or $(xy + yz + zx)Q(x, y, z)$ . Assume that $x^2y \in \mathcal{B}$ . We will consider cases on where $x^2y$ is from and the form of $P(x,y,z)$ or $Q(x,y,z)$ .

Case $1$ : $P(x,y,z) = xy + f(x,y,z)$ for some arbitrary polynomial $f(x,y,z)$ that doesn't contain a $-xy$ term.

If so, then we get that $Q(x,y,z) = -y+g(x,y,z)$ for some arbitrary polyomial $g(x,y,z)$ . Hence we get that $(x+y+z)f(x,y,z) + (xy+yz+za)g(x,y,z) + (xyz)R(x,y,z)$ This is our original problem statement, so it shows that this case won't yield us $x^2y$ .

Case $2$ : $P(x,y,z) = x^2 + f(x,y,z)$ for some arbitrary polynomial $f(x,y,z)$ that doesn't have a $-x^2$ term.

Our first term contains a $x^3$ , which can't be "eliminated" in the last two terms, so this case won't give us $x^2y$ .

Case $3$ : $Q(x,y,z) = x + g(x,y,z)$ for some arbitrary polynomial $g(x,y,z)$ that doesn't have a $-x$ term.

Observing, we see that $P(x,y,z) = -xz + f(x,y,z)$ for some arbitrary polynomial $f(x,y,z)$ and that $R(x) = 1 + h(x,y,z)$ for some arbitrary polynomial $h(x)$ . Expanding, we get that $(x + y + z)f(x, y, z) + (xy + yz + zx)g(x, y, z) + (xyz)h(x, y, z) = xz^2$ . Hence this case won't give us $x^2y$ .

We have exhausted all possible cases, and none gave us the desired result. Hence we have a contradiction, so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

225 posts

#14 h Jan 18, 2022, 6:45 AM

Y by

The answer is $n = 4$ . We first show that for all $n \geq 4$ , $x^iy^jz^k \in \mathcal{B}$ . If $i, j, k \geq 1$ , we observe that the construction $P(x, y, z) = 0, Q(x, y, z) = 0, R(x, y, z) = x^{i-1}y^{j-1}z^{k-1}$ generates $x^iy^jz^k$ .
Now suppose two among $i, j, k$ are zero. WLOG, let $i > 0$ and $j = k = 0$ . We shall find a construction when $i \geq 3$ . Observe that $P(x, y, z) = x^{i-1}, Q(x, y, z) = -x^{i-2}, R(x, y, z) = x^{i-3}$ shows that $x^i \in \mathcal{B} ~~ \forall i \geq 3$ .
Finally, suppose only one among $i, j, k$ are zero. WLOG $k = 0$ . If $\min (i, j) > 1$ then $(P, Q, R) = (0, x^{a-1}y^{b-1}, -(x^{a-2}y^{b-1} + x^{a-1}y^{b-2}))$ works. Otherwise, if $i \geq 3 > j = 1$ , then $(P, Q, R) = (x^{i-1}y, -x^{i-2}y, x^{i-3}y)$ works. This characterizes solutions for every $x^iy^jz^k$ where $i + j + k \geq 4$ .

Now we show that $x^2y \not \in \mathcal{B}$ .
Suppose, by way of contradiction, $\exists ~~ (P, Q, R)$ satisfying $x^2y = (x+y+z)P(x, y, z) + (xy + yz + xz)Q(x, y, z) + xyzR(x, y, z)$ . Let $P(x, y, z) = uxy + vyz + wxz + F(x, y, z)$ and $Q(x, y, z) = px + qy + rz + G(x, y, z)$ where $u, v, w, p, q, r \in \mathbb{Z}$ . We will ignore all term containing $x^ly^mz^n$ because they are not relevant in constructing $x^y$ and $R(x, y, z)$ can handle all such terms. Now expanding $(uxy + vyz + wxz + F(x, y, z))(x+y+z) + (px + qy + rz + G(x, y, z))(xy + yz + xz)$ we get $(u-p)x^2y$ as one of the terms, implying that $p = -(u-1)$ because there are is no other way to generate the monomial $x^2y$ and our final result must be $x^2y$ ( $x^2(x+y+z)$ can generate $x^2y$ term but we cannot have $x^2(x+y+z)$ because it generates an $x^3$ term which cannot be nullified by any term in $Q(x, y, z)$ and $R(x, y, z)$ ). Furthermore, we will have the term $(u-q)xy^2$ indicating that $q = -u$ since there are no other ways to get the monomial $xy^2$ . Similarly, we get $q = -u = -v, r = -v = -w, p = -(u-1) = -w$ . But this means that $-(u-1)=p = -w = r = -v = q = -u \implies -(u-1) = -u$ , absurd.

Thus, $x^2y \not \in \mathcal{B}$ and $n \geq 4$ . $\blacksquare$

This post has been edited 2 times. Last edited by green_leaf, Jan 18, 2022, 6:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5718 posts

#15 h Mar 22, 2022, 2:17 AM

Y by

We claim the answer is $\boxed{4}$ .

Proof of bound: We will show $x^2y\not\in \mathcal{B}$ .

Suppose it was. Set $z=-x-y$ . So $x^2y$ can be expressed as $(xy-(x+y)^2)Q(x,y,z)+xy(-x-y)R(x,y,z)=(-x^2-xy-y^2)Q(x,y,-x-y)-(x^2y+xy^2)R(x,y,-x-y)$
Only the degree 1 terms of $Q(x,y,-x-y)$ and constant term of $R(x,y,-x-y)$ matter because all non degree 3 terms must cancel out to zero.

So we get $-c_1x^3-c_1x^2y-c_1xy^2-c_2x^2y-c_2xy^2-c_2y^3-c_3x^2y-c_3xy^2,$ where $c_1$ , $c_2$ are the coefficients of $x$ and $y$ in $Q(x,y,-x-y)$ , respectively, and $c_3$ is the constant term of $R$ . Here, the coefficient of $x^2y$ is the same as the coeffieicnt of $xy^2$ , a contradiction. $\blacksquare$

Proof that $n=4$ works: By symmetry and multiplying by $x^ay^bz^c$ for some $a,b,c$ gives that we only must prove that $x^iy^jz^k\in \mathcal{B}$ for $i\ge j\ge k$ with $i+j+k=4$ .

1) $x^4$ .
Set $P(x,y,z)=x^3, Q(x,y,z)=-x^2, R(x,y,z)=x$ . It's easy to check this works.

2) $x^3y$
Set $P(x,y,z)=x^2y$ , $Q(x,y,z)=-xy$ , $R(x,y,z)=y$ . It's easy to check that this works.

3) $x^2y^2$
Set $P(x,y,z)=0, Q(x,y,z)=xy, R(x,y,z)=x+y$ . It's easy to check this works.

4) $x^2yz$ .
Set $P(x,y,z)=0, Q(x,y,z)=0, R(x,y,z)=x$ . It's easy to check this works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11449 posts

#16 h Mar 30, 2022, 3:14 PM

Y by

We claim that $n=4$ . First, we will show that $x^iy^jz^k\in\mathcal B$ if $i+j+k\ge n$ ., then that $x^2y\notin\mathcal B$ .

WLOG $i\ge j\ge k$ . We do the first part in four cases:
Case 1: $i\ge4,j\ge0,k\ge0$
Let $P(x,y,z)=x^{i-1}$ , $Q(x,y,z)=-x^{i-2}$ , $R(x,y,z)=x^{i-3}$ , then $x^iy^jz^k\in\mathcal B$ .
Case 2: $i\ge3,j\ge1,k\ge0$
Let $P(x,y,z)=x^{i-1}y^j$ , $Q(x,y,z)=-x^{i-2}y^j$ , $R(x,y,z)=x^{i-3}y^j$ , then $x^iy^jz^k\in\mathcal B$ .
Case 3: $i\ge2,j\ge2,k\ge0$
Let $P(x,y,z)=0$ , $Q(x,y,z)=x^{i-1}y^{j-1}$ , $R(x,y,z)=-x^{i-1}y^{j-2}-x^{i-2}y^{j-1}$ , then $x^iy^jz^k\in\mathcal B$ .
Case 4: $i\ge2,j\ge1,k\ge1$
Let $P(x,y,z)=0$ , $Q(x,y,z)=0$ , $R(x,y,z)=x^{i-1}y^{j-1}z^{k-1}$ , then $x^iy^jz^k\in\mathcal B$ .

Now assume FTSOC that $x^2y\in\mathcal B$ . Let $C:\mathcal A^2\to\mathbb Z$ be defined by $C(P_1(x,y,z),P_2(x,y,z))$ being the coefficient of $P_2(x,y,z)$ in $P_1(x,y,z)$ for any $P_1,P_2\in A$ .
Then there exist polynomials $P,Q,R$ such that:
$x^2y=(x+y+z)P(x,y,z)+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z)$ so:
$\begin{align*} 1&=C((x+y+z)P(x,y,z)+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z),x^2y)\\ &=C((x+y+z)P(x,y,z),x^2y)+C((xy+yz+zx)Q(x,y,z),x^2y)+C(xyzR(x,y,z),x^2y)\\ &=C((x+y)P(x,y,z),x^2y)+C(xyQ(x,y,z),x^2y)\\ &=C(xP(x,y,z),x^2y)+C(yP(x,y,z),x^2y)+C(xyQ(x,y,z),x^2y)\\ &=C(P(x,y,z),xy)+C(P(x,y,z),x^2)+C(Q(x,y,z),x). \end{align*}$ But, on the contrary, we can show that $C(P(x,y,z),x^2)=0$ and that $C(Q(x,y,z),x)=C(Q(x,y,z),z)$ and that $C(Q(x,y,z),y)=C(Q(x,y,z),z)$ and that $C(P(x,y,z),xy)+C(Q(x,y,z),y)=0$ , which together imply that $1=0$ , absurd.

Claim 1: $C(P(x,y,z),x^2)=0$
Because:
$\begin{align*} 0&=C((x+y+z)P(x,y,z)+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z),x^3)\\ &=C(xP(x,y,z),x^3)\\ &=C(P(x,y,z),x^2). \end{align*}$ Cyclical variations also hold.

Claim 2: $C(Q(x,y,z),x)=C(Q(x,y,z),z)$ , $C(Q(x,y,z),y)=C(Q(x,y,z),z)$
We can compare the following two assertions:
$\begin{align*} 0&=C((x+y+z)P(x,y,z)+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z),x^2z)\\ &=C(xP(x,y,z),x^2z)+C(zP(x,y,z),x^2z)+C(zxQ(x,y,z),x^2z)\\ &=C(P(x,y,z),xz)+C(P(x,y,z),x^2)+C(Q(x,y,z),x)\\ &=C(P(x,y,z),xz)+C(Q(x,y,z),x)\\ \end{align*}$ and
$\begin{align*} 0&=C((x+y+z)P(x,y,z)+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z),xz^2)\\ &=C(xP(x,y,z),xz^2)+C(zP(x,y,z),xz^2)+C(zxQ(x,y,z),xz^2)\\ &=C(P(x,y,z),z^2)+C(P(x,y,z),xz)+C(Q(x,y,z),z)\\ &=C(P(x,y,z),xz)+C(Q(x,y,z),z)\\ \end{align*}$ to get $C(Q(x,y,z),x)=C(Q(x,y,z),z)$ . Similarly, $C(Q(x,y,z),y)=C(Q(x,y,z),z)$ .

Claim 3: $C(P(x,y,z),xy)+C(Q(x,y,z),y)=0$
Similarly to the above claims, we have:
$\begin{align*} 0&=C((x+y+z)P(x,y,z)+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z),xy^2)\\ &=C(xP(x,y,z),xy^2)+C(yP(x,y,z),xy^2)+C(xyQ(x,y,z),xy^2)\\ &=C(P(x,y,z),y^2)+C(P(x,y,z),xy)+C(Q(x,y,z),y)\\ &=C(P(x,y,z),xy)+C(Q(x,y,z),y). \end{align*}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1784 posts

awesomeming327.

#17 h Jul 22, 2022, 6:32 PM

Y by

We claim that $x^2y$ is not expressible. If $(x+y+z)P(x,y,z)$ has a term $x^2y$ in its expansion, we decompose $P(x,y,z)$ into monic monomials, and suppose that the monomial $a(x,y,z)$ is part of that expansion.

$~$
If $a(x,y,z)\cdot x=x^2y$ then $a(x,y,z)\cdot y=xy^2$ is also in the expansion. If $a(x,y,z)\cdot y=x^2y$ then $a(x,y,z)\cdot y=x^2z$ so for every term in $(x^2y,y^2z,z^2x)$ in the expansion of $(x + y + z)P(x, y, z)$ there is a term $(xy^2,yz^2,zx^2).$ Similarly can be said for $(xy+yz+zx)Q(x,y,z)$ , so $x^2y$ is never achievable.

$~$
Now, we provide the following constructions for monomials of degree $4$ :
$x^4=(x+y+z)(x^3)+(xy+yz+zx)(-x^2)+x(xyz)$ $x^3y=(x+y+z)(x^2y)+(xy+yz+xz)(-xy)+y(xyz)$ $x^2y^2=(xy+yz+xz)(xy)+(-x-y)xyz$ $x^2yz=x(xyz)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

669 posts

#18 h Dec 4, 2022, 5:56 PM

Y by

spartacle wrote:

Note that the following much harder (and much nicer!) generalization of the problem was given in the comments in the shortlist packet. I'm not sure if this is the exact wording (in fact, the official version might replace $100$ with a variable integer $n$ ). Amusingly, there is actually a solution which uses the fact that $101$ is prime, though this is not necessary for the problem to hold.

Let $\mathcal{A}$ denote the set of polynomials in $100$ variables $x_1, \ldots , x_{100}$ with integer coefficients. Find the smallest integer $N$ such that any monomial $x_1^{e_1}x_2^{e_2}\cdots x_{100}^{e_{100}}$ with $e_1 + e_2 + \ldots + e_{100} \ge N$ can be expressed in the form
$p_1q_1 + p_2q_2 + \ldots + p_{100}q_{100}$ where $p_i, q_i \in A$ for all $i$ , $q_i$
is a symmetric polynomial for all $i$ , and $q_i(0, 0, . . . , 0) = 0$ .

One can show for any $k \ge 0$ that
$(x_1 \cdots x_{k+1})^{100-k}$ and similar stuff is representable. Which means all its multiples are then representable.

Using this, we can show $x^{e_1} \cdots x_{100}^{e_{100}}$ is representable whenever
$e_1 + \cdots + e_{100} \ge (0 + 1 + \cdots + 99) + 1$

This post has been edited 1 time. Last edited by guptaamitu1, Dec 4, 2022, 5:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

#19 h Jun 9, 2023, 4:52 AM

Y by

The answer is $n=4$ .

We first show that if any of $i,j,k\geq3$ , then $x^iy^jz^k \in \mathcal B$ . WLOG let $i\geq 3$ . Set $P(x,y,z) = -yz + x(x-y-z)$ , $Q(x,y,z) = y+z$ and $R(x,y,z) = 1$ . Then $G(x,y,z) := (x + y + z)P(x, y, z) + (xy + yz + zx)Q(x, y, z) + xyzR(x, y, z) = x^3.$ Multiply $P,Q,R$ by $x^{i-3}y^jz^k$ to get $x^iy^jz^k$ . To get $x^2 y^2$ , note that $(xy + yz + xz)xy - xyz(y+x) = x^2y^2.$ Of course, its permutations are also expressible. Thus $n\geq 4$ .

To show $n = 3$ fails, we show that $x^2 y$ cannot be expressed. Call any monomial of form $a^2b$ good. We show that there must be an even number of them. Define the set $S_P = \{x^2,y^2,z^2,xy,yz,xz\}$ . Any of them in $P$ will induce an even number of good monomials, e.g. each $xy$ creates $x^2y$ and $y^2x$ terms in $(x+y+z)P$ , contributing $2$ good monomials. Use a similar argument for $(xy+yz+xz)Q$ with $S_Q = \{x,y,z\}$ . Thus, $G(x,y,z)$ always contain an even number of good monomials. But the RHS $x^2y$ has $1$ good monomial, a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

everythingpi3141592

90 posts

everythingpi3141592

#20 h Oct 10, 2023, 3:29 PM

Y by

The answer is $n = 4$

Note that whenever some polynomial $P$ can be achieved, we can remove all terms containing all $3$ $x$ , $y$ , $z$ in them. For the same reason, all terms with all three $x$ , $y$ , $z$ can be expressed this way. Note by taking $P = 0$ , $Q = x$ , we get $x^2(y+z)$ is achievable. Multiplying by $y$ , $x^2y^2$ is achievable. Taking $P = x^2$ and subtracting this binomial, $x^3$ is achievable, and therefore so is $x^3y$ . This implies that in fact, for $n = 4$ , all such monomials can be achieved. For $n /geq 4$ , we can induct by multiplying each of $P$ , $Q$ , $R$ by either $x$ , $y$ or $z$ and getting a monomial with $1$ greater degree.

For $n = 3$ , to prove we cannot achieve $x^2y$ , just note that the number of terms of the form of $x^2y$ or analogous (for another permutation of the variables) is even.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4194 posts

#21 h Feb 12, 2024, 5:38 PM • 1 Y

Y by megarnie

The answer is $4$ .

Degree 1 is clearly not possible. For degree 2, note that we cannot use $xyz$ , so the sum of coefficents must be a multiple of 3 so it is not possible.

For degree 3, although we have $x^3=x^2(x+y+z)-x(xy+xz+yz)+xyz$ and $xyz=xyz,$ we will show that $x^2y$ is not achievable. Call a term half mixed if its $x,y,z$ coefficients are $2,1,0$ in some order. We will show that the sum of all half mixed coefficients must be even. We only have to consider degree 3 terms. Note that in $(x+y+z)(ax^2+by^2+cz^2+dxy+exz+fyz),$ when we distribute this, $x$ causes $bxy^2+cxz^2+dx^2y+ex^2z$ in terms of half mixed coefficents, so it contributes $b+c+d+e$ . Summing cyclically, the total contribution of this is $2(a+b+c+d+e+f),$ which is even. For $(xy+xz+yz)(ax+by+cz),$ we do the same with $2(a+b+c)$ . Thus, the sum of all half mixed coefficents are even, so $x^2y$ is not achievable.

Now, we show that degree 4 is possible. For $x^4$ , we multiply the $x^3$ construction by $x$ , and for $x^3y$ , we multiply it by $y$ , For $x^2yz$ , we multiply the construction for $xyz$ by $x$ . This leaves only $x^2y^2$ . However, we have $xy(xy+xz+yz)=x^2y^2+x^2yz+xy^2z.$ However we already know that $x^2yz$ and $xy^2z$ are doable, so $x^2y^2$ is also doable.

Finally, all degree $n$ being possible implies all degree $n+1$ being possible, since we can decrease one of the exponents by 1, construct the polynomial for degree $n$ , and multiply $P,Q,R$ by the variable that was divided out to get back to degree $n+1$ . Hence, $n=4$ works and we are done.

remark: in my opinion, the main part of this problem is showing that $x^2y$ is not achievable. Once again, playing around with examples helps here. One would notice that terms that look like what we want "comes in pairs", which is making it difficult to isolate one of them. The solution here quickly follows from this intuition.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

33 posts

Acclab

#22 h Feb 28, 2024, 5:01 PM

Y by

Let $I$ be the set of all possible polynomials able to be expressed as such. Clearly $I$ is closed under addition and "scalar" multiplication (coefficient from $A$ ). Exploring we get $x^2-yz \in I, x^3 \in I, x^2y^2-y^3z \in I$ and thus finally $x^2y^2 \in I$ . For $f = x^i y^j z^k$ if either $i, j, k \geq 3$ we have $f \in I$ as it is a multiple of $x^3, y^3$ or $z^3$ , so any $n \geq 7$ suffices. But $f \in I$ also if all $i, j, k \geq 1$ as $xyz \in I$ , so $n \geq 5$ suffices. Finally, $x^2y^2 \in I$ so $n \geq 4$ suffices. We claim $n=4$ is the minimal by proving $1, x, x^2, x^2y \notin I$ . Indeed, $x^2y \notin I$ is enough.

We further claim $f \in I$ implies the sum of coefficients of $x^2y, y^2z, z^2x$ and $xy^2, yz^2, zx^2$ are the same. Indeed, writing $f = (x+y+z)P + (xy+yz+xz)Q + xyzR$ we can see that a term of degree $2$ in $P$ : $x^2$ or $xy$ (up to permutation), the former contributes the same to both $x^2y$ , $x^2z$ and the latter to both $x^2y$ and $xy^2$ . The terms of degree $1$ in $Q$ are similar, so we are done. This claim is enough to show $x^2y \notin I$ , which shows $n=4$ is the minimal.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

59 posts

#23 h Mar 17, 2024, 10:01 PM • 1 Y

Y by YaoAOPS

We solve the problem in $n$ variables $x_1,x_2,\ldots,x_n$ . The answer is $\binom{n}{2}+1$ . Let $e_i$ denote the degree- $i$ elementary symmetric polynomial. Let $h_i$ denote the degree- $i$ complete homogeneous symmetric polynomial. Let the ideal $I$ be defined as $I=(e_1(x_1,x_2,\ldots,x_n),e_2(x_1,x_2,\ldots,x_n),\ldots,e_n(x_1,x_2,\ldots,x_n))$ .

It is well known that $I=(h_1(x_1,x_2,\ldots,x_n),h_2(x_1,x_2,\ldots,x_n),\ldots,h_n(x_1,x_2,\ldots,x_n))$ . Repeatedly using the identity $h_k(x_i,x_{i+1},\ldots,x_n)=x_ih_{k-1}(x_i,x_{i+1},\ldots,x_n)+h_k(x_{i+1},x_{i+2},\ldots,x_n)$ , we find that $I=(h_1(x_1,x_2,\ldots,x_n),h_2(x_2,x_3,\ldots,x_n),\ldots,h_n(x_n))$ .

We claim that this forms a Gröbner basis under the lex ordering. The leading term of $h_i(x_i,x_{i+1},\ldots,x_n)$ is $x_i^i$ , so $S(h_i(x_i,x_{i+1},\ldots,x_n),h_j(x_j,x_{j+1},\ldots,x_n))=x_i^i\operatorname{red}_1(x_j^j,h_j(x_j,x_{j+1},\ldots,x_n))-x_j^j\operatorname{red}_1(x_i^i,h_i(x_i,x_{i+1},\ldots,x_n))$ . The second term does not contain a term divisible by $x_i^i$ but the first does. So we can reduce the $S$ -polynomial by $h_i(x_i,x_{i+1},\ldots,x_n)$ to $\operatorname{red}_1(x_i^i,h_i(x_i,x_{i+1},\ldots,x_n))\operatorname{red}_1(x_j^j,h_j(x_j,x_{j+1},\ldots,x_n))-x_j^j\operatorname{red}_1(x_i^i,h_i(x_i,x_{i+1},\ldots,x_n))=-h_j(x_j,x_{j+1},\ldots,x_n)\operatorname{red}_1(x_i^i,h_i(x_i,x_{i+1},\ldots,x_n))$ , which we can then reduce to 0. Thus $(h_1(x_1,x_2,\ldots,x_n),h_2(x_2,x_3,\ldots,x_n),\ldots,h_n(x_n))$ is a Gröbner basis for $I$ .

Therefore, an integral polynomial $P$ is in $I$ if and only if it can be reduced to 0 by $(h_1(x_1,x_2,\ldots,x_n),h_2(x_2,x_3,\ldots,x_n),\ldots,h_n(x_n))$ . For the lower bound, $x_2^1x_3^2\cdots x_n^{n-1}$ cannot be reduced to 0 since it cannot be reduced at all. For the upper bound, let $P$ be a homogeneous integral polynomial that cannot be reduced to 0. Then the reduced version of $P$ must have leading term $x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n}$ where $a_i<i$ . Since all of the polynomials in the basis are homogeneous, the reduction of $P$ is still homogeneous and the reduction cannot change the degree unless the polynomial gets reduced to 0. Therefore $\deg P\le\binom{n}{2}$ . So all homogeneous integer polynomials of degree at least $\binom{n}{2}+1$ are in $I$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7584 posts

#24 h Apr 27, 2024, 10:54 PM

Y by

Notice
$x^3=(x+y+z)(x^2)+(xy+yz+zx)(-x)+(xyz)(1)$ and
$x^2y^2=(x+y+z)(0)+(xy+yz+zx)(xy)+(xyz)(-x-y)$ and by multiplying these monomials by some $x^ay^bz^c$ we can achieve $n\ge 4$ .

Now we show that $x^2y$ is not achieveable. As it turns out there is a perfect way to prove this: we must use $xy$ in the coefficient of $x+y+z$ which yields $xy^2$ to achieve, or we can use $x$ in the coefficient of $xy+yz+zx$ which yields $x^2z$ to achieve. Graph theory shenanigans should rigorize, or we can assign variables and obtain the lemma in #4.

Actually I'll rigorize anyways. Let $a$ , $b$ , and $c$ be the coefficients of $yz$ , $zx$ , and $xy$ in $P(x,y,z)$ . Let $d$ , $e$ , and $f$ be the coefficients of $x$ , $y$ , and $z$ in $Q(x,y,z)$ . Notice that the coefficient of any single-variable term of $P(x,y,z)$ is $0$ . Then
$1=c+d$ $0=c+e$ $0=a+e$ $0=a+f$ $0=b+f$ $0=b+d$ where the last five equations come from coefficients of $xy^2$ and so on.
Adding odd-numbered and even-numbered equations yields $1=0$ , a contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8904 posts

#25 h Jun 24, 2024, 7:26 PM

Y by

I wish this were IMO1 or IMO4! It's so enjoyable and satisfying.

The answer is $n=4$ .

Construction: It suffices to verify that we can form the monomials $x^2yz$ , $x^3y$ , $x^2y^2$ , and $x^4$ by symmetry. Note that if $A \in \mathcal B$ and $B \in \mathcal B$ then $A+B \in \mathcal B$ . Consider:

We can form $x^2yz$ by letting $P \equiv Q \equiv 0$ and $R \equiv x$ .
By letting $Q \equiv xy$ , $x^2yz+x^2y^2+xy^2z \in \mathcal B$ , so $x^2y^2 \in B$ by the above.
By letting $P \equiv x^2y$ , $x^3y + x^2y^2 + x^2yz \in \mathcal B$ , so $x^3y \in \mathcal B$ .
Finally, by letting $P \equiv x^3$ , $x^4 + x^3y+x^3z \in \mathcal B$ , so $x^4 \in \mathcal B$ .

Bound: I claim that $x^2y \not \in B$ . Assume that there are some polynomials $P_0, Q_0, R_0$ such that $P_0(x, y, z)(x+y+z) + Q_0(x, y, z)(xy+yz+zx) + R_0(x,y, z)(xyz) = x^2y.$ Notice that $P_0(x, y, z)$ cannot contain any terms that are in only one of the variables $x, y, z$ .

We let
$\begin{align*} P_0(x, y, z) &= a_1yz + a_2 xz + a_3 xy + P_0'(x, y, z)\\ Q_0(x, y, z) &= b_1 x + b_2 y + b_3z + Q_0'(x, y, z) \end{align*}$ where the coefficients $a_i$ and $b_i$ are real numbers (possibly zero). It follows that
$x^2 y = (a_3+ b_1) x^2 y + (a_3+b_2) xy^2 + (a_2+b_1) x^2z + (a_2+b_3) xz^2 + (a_1+b_2) y^2z + (a_1+b_3) yz^2 + R_1(x, y, z)$ where $R_1(x, y, z)$ does not contain any $x^2y$ terms or cyclic permutations. In particular, we must have $a_3+b_1$ nonzero and all the other coefficients zero. But observe that
$(a_3+b_1) + (a_2+b_3) + (a_1 + b_2) = (a_3+b_2) + (a_2+b_1) + (a_1+b_3)$ where the LHS is nonzero and the RHS is zero, contradiction. So $x^2 y \not\in \mathcal B$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1633 posts

#26 h Dec 14, 2024, 4:09 AM

Y by

We solve the generalization

Replace $100$ with $n$ in the above.

Claim: This is equivalent to showing that any monomial $x_1^{e_1} x_2^{e_2} \dots x_{n}^{e_{n}}$ can be expressed as $p_1 q_1 + p_2 q_2 + \dots + p_{k} q_{k}$ for any $k$ .
Proof. By the fundamental theorem of symmetric polynomials or Newton Sums, we can express any integral symmetric polynomial $q_i$ as an integral polynomial of $\sigma_1, \sigma_2, \dots, \sigma_n$ where $\sigma_i = \sum_{\text{sym}} x_1x_2 \dots x_i$ $\blacksquare$
Let $I$ be the ideal generated by symmetric polynomials $q_i$ . Call a symmetric polynomial one-term if it can be written in the form $c\sum_{\text{sym}} x_1^{a_1}x_2^{a_2} \dots x_k^{a_k}$
Claim: We have that $(x_1x_2 \dots x_k)^{n+1-k} \in I$ for all $1 \le k \le n$ .
Proof. Fix $k$ . We consider $(x_1x_2 \dots x_k)^{n+1-k}$ in the form $\sum P_iQ_i$ where $P_i = \sum_{\text{sym}} T_p$ is a one term symmetric polynomial in $x_1, x_2, \dots, x_k$ and $Q_i = \sum_{\text{sym}} x_{k+1} \dots x_{k+1+v}$ is a one term symmetric polynomial in $x_{k+1}, \dots, x_n$ for some $v$ . We claim in general for each individual $P_iQ_i \in I$ , whenever $e + v \ge n + 1 - k$ where $e$ is the minimal exponent in $T_p$ . We can then induct downward on the size of $v$ with base case $v = n - k, m \ge 1$ (which holds by divisibility with $x_1x_2 \dots x_n$ ) as follows. Write $P_i = P_i' \cdot (x_1x_2 \dots x_k)$ and consider $P_iQ_i - P_i' \cdot \sum_{\text{sym}} x_1x_2 \dots x_{n+v} = \sum_{j} P_jQ_j$ where we can check each resulting $P_j$ has $e$ decreased by at least $1$ and $v$ increased by the same amount, allowing us to induct downward. Then taking $P_i = (x_1x_2 \dots x_k)^{n+1-k}, Q_i = 1$ suffices. $\blacksquare$
This allows us to prove that any monomial of degree at least $\binom{n}{2} + 1$ lies in $I$ by using the above.

Claim: $S = x_2x_3^2x_4^3\dots x_n^{n-1}$ does not lie in $I$ .
Proof. Call a term a staircase if its of the above form up to a permutation. Then FTSOC suppose that $p_1q_1 + p_2q_2 + \dots + p_kq_k$ equals a staircase. Split such that each $p_i$ is one term with leading coefficient one, and each $q_i = \sum_{\text{sym}} T_q$ is one term symmetric. Then we can set $p_i$ such that all its terms have degree $\binom{n}{2} - \deg p_i$ as removing expanded terms without degree $\binom{n}{2}$ has no results.
Consider each $p_i \cdot q_i$ individually. We claim that its expansion has an even number of staircase terms.
Now, suppose that $p_i \cdot T_q(x_1, x_2, \dots, x_n)$ is a staircase term, WLOG let it be the initial $S$ . Note that $p_1$ can't be staircase unless $T_q$ is zero. Then note that $p_1$ if we let $p_i = x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}$ , then for some $i$ , there are multiple $P = \{i_1, i_2, \dots\}$ with the same exponent in $p_i$ . Then we can create equivalence classes of size $|P|!$ by permuting the indices in $T_q$ with said exponent, which implies an even number of staircase terms.
This gives a contradiction. $\blacksquare$

This post has been edited 2 times. Last edited by YaoAOPS, Dec 14, 2024, 4:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

253 posts

pie854

#27 h Feb 5, 2025, 2:52 PM

Y by

It is fairly trivial to see that $xy^2$ cannot be written in this form. Hence, $n > 3$ . Now we'll show that if $i+j+k \geq 4$ then $x^iy^jz^k \in \mathcal B$ . Some casework follows:

$i,j,k>0$ : Take $P=Q=0$ , $R=x^{i-1}y^{j-1}z^{k-1}$ .
One of them is $0$ : Let's do for $x^i y^j$ . Suppose $i \geq j$ . If $i \geq 3$ , take $P=x^{i-1}y^j$ , $Q=-x^{i-2}y^j$ , $R=-x^{i-2}y^{j-1}+x^{i-3}y^j+x^{i-2}y^{j-1}$ . If $i=j=2$ , take $P=0$ , $Q=xy$ , $R=-x-y$ .
Two of them are $0$ : Taking $P=x^{i-1}$ , $Q=-x^{i-2}$ , $R=x^{i-3}$ does it for $x^i$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1360 posts

ezpotd

#28 h May 18, 2025, 9:32 PM

Y by

The answer is $n = 4$ .

Proof that $n = 3$ is impossible: Consider the degree $2$ terms of $P(x,y,z) = ax^2 + by^2 + cz^2 + dyz + exz + fxy$ , and the degree $1$ terms of $Q(x,y,z) = gx + hy + iz$ , we ignore all other terms of a different degree or terms on $R$ as they do not contribute to expressions of the form $x^2y$ . We then show isolating $x^2y$ is impossible. The sum of the coefficients on the terms of the form $x^2y$ is $2(a+b+c+d+e+f+g+h+i)$ , which can never be $1$ , thus we can never isolate $x^2y$ .

Construction for $n = 4$ : We can easily make any term that has $i,j,k > 0$ . Then to make any term with at least one of $i,j,k$ at least $3$ , take the construction $P(x,y,z) = x^2, Q(x,y,z) = -x, R(x,y,z) = 1$ to get the resulting expression as $x^3$ , then multiplying all polynomials by whatever is left suffices. The only thing left is terms of the form $x^2y^2$ , which can be formed by $P(x,y,z) = x^2y$ , which gives $(x + y + z)P(x,y,z) = x^3y + x^2y^2 + x^2yz$ , we can easily construct the first and last term and subtract their polynomials to isolate $x^2y^2$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a