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

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?

• Well certainly $\deg T\leq 2|\Bbb{F}|$ is a simple bound. Also, I assume you are excluding $T=0$? – Servaes Apr 18 at 8:40
• @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$... – W-t-P Apr 18 at 8:50
• @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$. – W-t-P Apr 18 at 8:57
• @W-t-P You are right in both cases. Though I would say $\deg(y-C)=1$. – Servaes Apr 18 at 9:01
• @Servaes: ... and you are right about $\deg(y-C)$ :-) – 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.

• 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. – Jyrki Lahtonen Apr 19 at 4:40
• 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$. – W-t-P Apr 19 at 9:00
• @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! – Jyrki Lahtonen Apr 19 at 9:25
• Anyway, if there is an imbalance between $n$ and $m$, the crossover point comes a bit earlier. – Jyrki Lahtonen Apr 19 at 12:11