Low-degree polynomial $T\in\mathbb F[x,y]$ with $T(P(z),Q(z))=0$

Question

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?

Answer 1

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.