Bivariate polynomial divisibility test of Spielman

Question

Setup

In his thesis (lemma 4.2.18, p. 97-98) Spielman describes a divisibility test for bivariate polynomials $E,P\in k[X,Y]$, where $k$ is a field (of positive characteristic for what I'm interested in). It is a converse to the observation that if $E\mid P$ in $k[X,Y]$, then for any $u\in k$, substituting $X$ with $u$ yields a divisibility relation $E(u,Y)\mid P(u,Y)$ within $k[Y]$. So as to not distract from my actual question, I state a vague version of his result.

Lemma. If there are enough $x_1,\dots,x_m\in k$ and $y_1,\dots,y_n\in k$ such that $E(x_i,Y)\mid P(x_i,Y)$ and $E(X,y_j)\mid P(X,y_j)$ then $E\mid P$.

The proof works in two steps: prove the assertion for coprime polynomials $E$ and $P$, and reduce the general case to the coprime case. In the coprime case, he considers $E,P\in R[Y]$ to be polynomials with coefficients in the ring $R=k[X]$: $$ E=\sum_{i=0}^{\deg_Y(E)}E_i(X) Y^i,\quad P=\sum_{i=0}^{\deg_Y(P)}P_i(X) Y^i $$ he associated resultant ($\deg_Y(E)=\beta n$ and $\deg_Y(P)=(\beta+\epsilon)n$ in his notation) $\mathrm{Res}(E,P)=k[X]$ must be nonzero and there is an easy bound on the degree. The gist of the proof is to show that $R$ has too many roots counted with multiplicities to be nonzero, and to derive a contradiction from there.

---

My problem

It seems the justification for the multiplicity count given in the paragraph below is lacking in two ways

1. I see no reason why there should be the claimed linear dependence. What is preventing a situation where say $E(x_i,Y)=1$ and $\deg_Y(P(x_i) = \deg_Y(P)$ for instance (in which case the matrix $M(E,P)(x_i)$ is invertible and $x_i$ is not a root of $\mathrm{Res}(E,P)$) ? All I can safely say is that if $\deg_Y P - \deg_Y P(x_i,Y) \geq \deg_Y E - \deg_Y E(x_i,Y)$ then the claim is true.
2. There is another difficulty arising from the fact that Spielman uses vanishing of derivatives to obtain information about multiplicities, but it was suggested to me that one can salvage the argument using ``hyper derivatives'' and this seems plausible.

---

Questions

1. Are these concerns valid?
2. Is there a way to resolve the first one?
3. Are there missing assumptions?
4. Has this result been written up and corrected elsewhere?

Also please feel free to migrate this question to the theoretical computer science stack.exchange if necessary. There already is a question about that proposition on there, but the question is different.

Answer 1

One possible fix is as follows: let us write $(\deg_X(E),\deg_Y(E))=(a,b)$ and $(\deg_X(P),\deg_Y(P))=(c,d)$. Let us assume $a<c$ and $b<d$ and $E$ coprime with $P$ in the factorial ring $k[X,Y]$. Suppose we have $x_1,\dots,x_n$ distinct points in $k$ such that $E(x_i,Y)\mid P(x_i,Y)$ in $k[Y]$.

The usual matrix $M(E,P)\in M_n(k[X])$ with coefficients in $k[X]$ whose determinant is the resultant $\mathrm{Res}_Y(E,P)\in k[X]$ is the matrix of the linear map $$ \phi = \phi_{E,P}: \left\{ \begin{array}{ccc} K_{<d}[Y]\times K_{<b}[Y] & \longrightarrow & K_{<b+d}[Y]\\ (U,V) & \longmapsto & UE+VP \end{array} \right. $$ where $K=k(X)$.

Suppose $\mathbf{E_b(x_i)\neq 0}$: then $E(x_i,Y)$ is a degree $b$ polynomial in $Y$ and the quotient $E(x_i,Y)Q_i=P(x_i,Y)$ has $$\begin{array}{rcl} \deg_Y(Q_i) & = & \deg(P(x_i,Y))-\deg(E(x_i,Y))\\ & = & \deg(P(x_i,Y))-\deg_Y(E(X,Y))\\ & \leq & \deg_Y(P)-\deg_Y(E) = d-b \end{array}$$ and thus we can write $$ \phi(Y^\ell Q_i, -Y^\ell)(x_i) = E(x_i,Y)\cdot Y^\ell Q_i - Y^\ell P(x_i,Y) =0 $$ for $\ell=0,\dots,b-1$, we have $0\leq \deg(Y^\ell Q_i)<b+\deg(Q_i)\leq d$ and $\deg(-Y^\ell)<b$ so that these are (linearly independent vectors) of the kernel of $M(E,P)(x_i)$. It is easy to deduce from that (the fact that the kernel of $M(E,P)(x_i)$ has dimension (exactly) $b$) that $x_i$ is a root of multiplicity at least $b$ of the resultant $\mathrm{Res}_Y(E,P)$.

Also $\deg\big(\mathrm{Res}_Y(E,P)\big)\leq ad+bc$. Since $E_b$ has degree $\leq \deg_X(E)=a$, then if there are $m>a$ different $x_i$ satisfying the divisibility property, then $\mathrm{Res}_Y(E,P)$ has at least $m-a$ distinct roots of multiplicity at least $b$, so if $$ (m-a)b>ad+bc $$ then $\mathrm{Res}_Y(E,P)=0$ and we have reached a contradiction.

Answer 2

If $E(x_i,y)$ divides $P(x_i, y)$ in the ring $k[y]$ this by definition means there exist a polynomial $G(y) \in k[y]$ such that $P(x_i, y) = G(y)E(x_i, y)$

Let $G(y) = a_0 + a_1 y + \dots + a_l y^l,\; l = \epsilon n$

I claim that that the first row of your matrix is a linear combination of consecutive $\epsilon n$ rows starting with $(E_{\beta n}, \dots, E_{0}, 0, \dots, 0)$ where the coefficients of linear dependence are precisely $a_l, a_{l-1}, \dots, a_0$ (in order to prove simply compare the coefficients on LHS and RHS $P(x_i, y) = G(y)E(x_i, y)$.

Exactly the same logic can be applied to the other rows of the matrix (or note that they are just a "shift" of the considered case).

Hope, this helps.