Bivariate low-degree polynomial testing of Polishchuk-Spielman

Question

In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate polynomials.

The following paragraph just provides some information about the paper and context for my question. Strictly speaking, it may be skipped. My question itself is concerned with simple multivariate polynomial algebra

Essentially, to test if the function values on a set of evaluation points correspond to a bivariate polynomial of maximum degrees $(d,d)$, we check whether the restriction of this to axis parallel lines (i.e. rows and columns) are all degree $d$ univariate polynomials (This is an equivalence condition in the absolute case, which is easy to verify. The interesting part is the robustness of the test: that is, if the function values on the restrictions to axis parallel lines agree with low-degree polynomials on "most" points, then there is a bivariate low degree polynomial which also agrees with the function on most evaluation points). The proof of robustness uses the notion of error-corrector polynomial to capture the "bad" evaluation points, polynomial interpolation and then uses resultants. I am intentionally not being too precise here because none of this is relevant to my actual doubt, which is probably a minor algebraic technicality in a part of the proof: http://cs.yale.edu/homes/spielman/PAPERS/holographic.pdf

The problem

Consider section 5: "Piecing it together" in the above paper. The polynomials $P(x,y)$ and $E(x,y)$ are interpreted as univariate polynomials in $y$ over the field of rational functions in $x$ over $\mathbb{F}$, that is $\mathbb{F}(x)$ . We would ultimately like to show that $E(x,y)$ divides $P(x,y)$ as bivariate polynomials in $\mathbb{F}[x,y]$, and this is shown by arguing that $E(x,y)$ divides $P(x,y)$ as univariate polynomials in $y$ over $\mathbb{F}(x)$, and then use Gauss's lemma to imply the former.

I am unable to see how Gauss's lemma trivially establishes this implication.

For instance, suppose $P(x,y)=y^2x$ and $E(x,y)=yx^2$. Then $E$ does divide $P$ as polynomials in $y$ over $\mathbb{F}(x)$, but clearly not as bivariate polynomials in $\mathbb{F}[x,y]$.

(Gauss's lemma states that if a univariate polynomial in $\mathbb{D}[x]$ (where $\mathbb{D}$ is a UFD) is reducible as a polynomial in $\mathbb{K}[x]$ (where $\mathbb{K}$ is the field of fractions of $\mathbb{D}$), then it is reducible in in $\mathbb{D}[x]$ itself.)

Answer 1

If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$.

But in the beginning of the proof of Lemma 8 they assume without loss of generality that $P$ and $E$ do not have a common factor. More specifically, they show that if $P$ and $E$ have a common factor then they can use induction to show that $E$ divides $P$.

Answer 2

I find the wording is confusing as well. I think what follows explains it. The idea is not to show that $E$ divides $P$, but rather to show that if it didn't (so that $\widetilde{E}$ isn't a constant) we can derive a contradiction.

Set $A=k[X]$ and $F=k(X)$. The irreducibles of $A[Y]$ are precisely

• the irreducibles of $A$
• the (positive degree) polynomials $f\in A[Y]$ that have content 1 and are irreducible in $F[Y]$.

Let $\widetilde{E}$ and $\widetilde{P}$ be coprime in the UFD $k[X,Y]=A[Y]$. If we assume that there are enough $x_i$ and $y_j$ as in the theorem, the resultant argument (which has its own (fixable) issues, see this question) establishes that $\mathrm{Res}_Y(\widetilde{E},\widetilde{P})\in A$ is zero, i.e. $\widetilde{E}$ and $\widetilde{P}$ aren't coprime in $F[Y]$. To produce a contradiction, we will show that they aren't coprime in $A[Y]$ either.

There is thus an irreducible polynomial $f(Y)\in F[Y]$ dividing both $\widetilde{E}$ and $\widetilde{P}$ in $F(Y)$. Constants aren't irreducible in $F(Y)$ so $f$ has positive degree. Furthermore (chasing denominators) we can assume WLOG $f\in A[Y]$ of content $1$, i.e. $f$ positive degree irreducible of $A[Y]$. By denominator chasing there are $\theta(X)\in A$ and $Q_E,Q_F\in A[Y]$ such that $$ \begin{cases} f(Y)Q_E(Y) = \theta(X)\widetilde{E}\\[1mm] f(Y)Q_P(Y) = \theta(X)\widetilde{P} \end{cases} $$ Now everything is in $A[Y]$ (i.e. $f$, $\theta$, $Q_E$, $Q_P$, $\widetilde{E}$ and $\widetilde{P}$ belong to $A[Y]=k[X,Y]$) and it follows from the description of irreducibles in $A[Y]$ (and the fact that irreducibles are prime in UFDs) that $f\in A[Y]$ divides both $\widetilde{E},\widetilde{P}$. This contradicts the fact that $\widetilde{E}$ and $\widetilde{P}$ are coprime in $A[Y]$.

---

Note In the original paper the author define $\widetilde{E}=E/G$ and $\widetilde{P}=P/G$ where $G$ is the GCD of $E$ and $P$ (they use the letter $F$ which I've already for other purposes). They want to show that $E\mid P$ i.e. (up to rescaling by some element in $k$) that $E=G$. Suppose not, and let's consider $(a,b)=(\deg_X(G),\deg_Y(G))$, $(c,d)=(\deg_X(E),\deg_Y(E))$. Then $0\leq a\leq c$ and $0\leq b\leq d$.

The argument goes by contradiction: suppose $G\neq E$. Then $a<c$ or $b<d$. In reality, we must have both $a<c$ and $b<d$. Indeed, if say $a=c$, then $E(X,Y)= Q(Y) G(X,Y)$ for some polynomial $Q\in k[Y]$. Then substituting $X$ with $x_i$ we get $$ \forall x_i,\quad Q(Y) G(x_i,Y) = E(x_i,Y) \mid P(x_i,Y) $$ So that $Q(Y)\mid P(x_i,Y)$ for all $i$. Then by Lagrange interpolation we get $$ P(X,Y) = \sum_{i=1}^m P(x_i,Y) L_i(X) \equiv \text{ multiple of }Q(Y) $$ where the $L_i(X)=L_{x_i,(x_1,\dots,x_m)}(X)\in k[X]$ are the Lagrange interpolation polynomials wrt to the $x_i$. But then $Q(Y)$ divides both $E$ and $P$. But this is in contradiction with $G$ being the GCD of $E$ and $P$.

A similar reasoning applies to show that $b<d$.