Let $p > 3$ be a prime number, and let $F_p$ denote the (finite) set of residue classes modulo $p$. Let $S_d$ denote the set of $2$-variable polynomials $P(x, y)$ with coefficients in $F_p$, total degree $\le d$, and satisfying $P(x, y) = P(y,- x -y)$. Show that $$|S_d| = p^{\lceil (d+1)(d+2)/6 \rceil}$$. The total degree of a $2$-variable polynomial $P(x, y)$ is the largest value of $i + j$ among monomials $x^iy^j$ appearing in $P$.
Problem
Source: RMM Shortlish 2016 A2
Tags: ceiling function, algebra, polynomial, prime
25.06.2021 05:05
Any solution?
10.10.2021 22:06
Call a polynomial satisfying the condition exquisite. If we let $g(d)$ be the number of linearly independent homogeneous exquisite polynomials of degree $d$ up to a constant, it is enough to show $\sum_{l=0}^d g(l) = \bigg\lceil \frac{(d+1)(d+2)}{6} \bigg \rceil$, since then a generic exquisite polynomial can be expressed as a linear combination of these homogeneous parts. This allows us to focus on homogenous $P$ of degree $n$. Crucial claim: if we let $U=x^2+xy+y^2$, $V=xy(x+y)$ and $W=x^3-3xy^2-y^3$, then $P$ is exquisite iff it can be written as $Q(U,V,W)$, where the degree of $U$ is $\leq 2$. For the easy implication, observe that $U,V,W$ are all exquisite, so $Q(U,V,W)$ is exquisite as well. For the other direction, we construct $Q$ from $P$ inducting on $n$, and there is an observation which will be useful. Observation: if $y|P$ then $V|P$. This follows from $P(x,y)=P(y,-x-y)=P(-x-y,x)$. Now we can proceed to prove the claim by induction. The base cases ($n \leq 3$) can be done by hand, so assume $n \geq 4$. Let $n=3k+2j$, with $k \geq 0$ and $j \in \{0,1,2\}$. If $P$ is exquisite and the coefficient of $x^n$ is $a$, then $P-aU^jW^k$ is exquisite and is divisible by $y$, so it is a multiple of $V$ and we have $P=aU^jV^k+VP'$, where $P'$ is exquisite and has degree $n-3$, and by inductive hypothesis there is a $Q(U,V,W)=P'(x,y)$ which gives that $P$ can be written in that form as well. Notice that this procedure ensures that the degree of $U$ in the resulting polynomial is $\leq 2$ (and it can be easily seen that its exactly equal to $j$, by looking at the degrees mod $3$). For the counting part, observe that $V^k, V^{k-1}W, \cdots W^k$ are all linearly independent, so $U^jV^k, U^jV^{k-1}W, \cdots U^jW^k$ are as well. Since the crucial claim tells us that their linear combinations spans the space of degree $n$ exquisite polynomials, we get $g(3k+2j)=k+1$ (and $g(1)=0$), and from this the conclusion follows. Remark: the characterization of exquisite polynomials we found remains the same if $F_p$ is replaced by any field with characteristic $ \neq 3$. For fields with characteristic $3$ it is slightly different, as the exquisite polynomials are generated by $x-y$ and $xy(x+y)$ (this is due to the fact that $U$ and $W$ are the same as $(x-y)^2$ and $(x-y)^3$), but the proof is no different. In the case of $F_3$ the answer to the question would be $|S_d|= 3^{\lceil (d+1)(d+3)/4 \rceil }$.