6
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ This is not good that such a fundamental result has holes. While reading Spielman's Thesis a while back, also the routing reduction was very hand wavy. $\endgroup$ – relG Sep 11 '17 at 9:59
  • $\begingroup$ The statement that seems almost correct that is actually used is that if $E$ and $P$ have a common factor in $F(x)[y]$ they have a common factor in $F[x][y]$. But this is problematic when say, $E$ and $P$ are different irreducibles only in $x$. $\endgroup$ – relG Sep 14 '17 at 9:56
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I don't understand why Gauss's Lemma implies this. It implies, for example, that if P can be factored to rational functions it can be factors into polynomials. But I don't see how you proceed from there. $\endgroup$ – relG Sep 11 '17 at 10:22

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.