Given polynomials $P,Q\in\mathbb F[z]$ over a finite field $\mathbb F$, one can find a non-zero polynomial $T\in\mathbb F[x,y]$ such that $T(P(z),Q(z))=0$ for any $z\in\mathbb F$. Is there a way to control the degree of $T$? Can one guarantee that there exists $T$ with, say, $\deg T\le 2(\deg P+\deg Q)$, or something of this sort?

  • $\begingroup$ Well certainly $\deg T\leq 2|\Bbb{F}|$ is a simple bound. Also, I assume you are excluding $T=0$? $\endgroup$ – Servaes Apr 18 at 8:40
  • 1
    $\begingroup$ @Servaes: $T=0$ is excluded, for $\deg T\le 2|\mathbb F|$ - I have a still better bound $\deg T\le|\mathbb F|$, but I do not call it controlling the degree of $T$... $\endgroup$ – W-t-P Apr 18 at 8:50
  • 1
    $\begingroup$ @Servaes: For your second comment - sorry, I do not understand it. If $Q$ is constant, say $Q=C$, then $T(x,y)=y-C$ will do; thus, we can find $T$ with $\deg T=2$. $\endgroup$ – W-t-P Apr 18 at 8:57
  • $\begingroup$ @W-t-P You are right in both cases. Though I would say $\deg(y-C)=1$. $\endgroup$ – Servaes Apr 18 at 9:01
  • $\begingroup$ @Servaes: ... and you are right about $\deg(y-C)$ :-) $\endgroup$ – W-t-P Apr 18 at 9:06

Summary: As a function of $N=\max\{i,j\}$ the number of polynomials $P^iQ^j$ grows like a quadratic polynomial of $N$. But their degree grows like a linear polynomial of $N$. Sooner or later the former overtakes the latter, and at that point we are guaranteed to find a linear dependence relation, which is what we need.

Then the detailed version:

Assume that $\deg P(z)=n$, $\deg Q(z)=m$. Without loss of generality we can assume that $n\ge m$. The case $n=1$ is not interesting. Assuming that $n>1$ we see the existence of $T$ of degree $\le 2n-2=2\max\{n,m\}-2$ as follows.

Let $N$ be a natural number. The number of pairs $(i,j)$ such that $i+j\le N$ is easily seen to be equal to the triangular number $k(N):=(N+1)(N+2)/2$. If $(i,j)$ is such a pair, the degree of $P^iQ^j,i,j\in\Bbb{N},$ is equal to $ni+mj\le nN$. But the dimension of the space $P_M$ of polynomials $\in F[z]$ of degree $\le M$ is equal to $\dim P_M=M+1$.

If $k(N)>\dim P_{nN}$ we can deduce that the set of polynomials $P^iQ^j, i+j\le N$, is linearly dependent over $F$. Simply because the number of polynomials $P^iQ^j,i+j\le N,$ exceeds the dimension of the space they live in.

So we require that $$\frac{(N+1)(N+2)}2>nN+1.$$ Given the assumption $n>1$ this inequality holds if $(N+2)/2= n$, or when $N=2n-2$. Anyway, the conclusion is that there exists a non-trivial set of coefficients $a_{i,j}, 0\le i,j, i+j\le 2n-2$ such that $$ \sum_{i,j}a_{i,j}P^iQ^j=0 $$ implying that $T(x,y)=\sum_{i,j}a_{i,j}x^iy^j$ works.

Observe that it is irrelevant whether $F$ is finite or not.

  • $\begingroup$ It may be a fun game to try and optimize the maximum value of $ni+mj$ that we need. Effectively we are bounding the order of the pole of $P^iQ^j$ at infinity. On a curve more complicated than the projective line we can similarly use Riemann-Roch on the set of divisors allowing a single pole (at a selected point) only. $\endgroup$ – Jyrki Lahtonen Apr 19 at 4:40
  • $\begingroup$ Apart from working in any (not necessarily finite) field, your solution gives considerably more than I asked: namely, it shows that there is a nonzero, low-degree polynomial $T$ in two variables such that $T(P,Q)=0$. $\endgroup$ – W-t-P Apr 19 at 9:00
  • $\begingroup$ @W-t-P I didn't even notice that you only asked for the polynomial to vanish identically! Oops :-) That does explain the emphasis on finite fields! $\endgroup$ – Jyrki Lahtonen Apr 19 at 9:25
  • $\begingroup$ Anyway, if there is an imbalance between $n$ and $m$, the crossover point comes a bit earlier. $\endgroup$ – Jyrki Lahtonen Apr 19 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.