<p>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]$.</p>

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

CC BY-SA 3.0
2017-09-11T10:22:15.840Z
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.
relG
CC BY-SA 3.0
2016-11-17T22:59:10.020Z
2016-11-17T22:59:10.020Z
Igor Shinkar
<p>I find the wording is confusing as well. I think what follows explains it. The idea is not to show that <span class="math-container">$E$</span> divides <span class="math-container">$P$</span>, but rather to show that if it didn't (so that <span class="math-container">$\widetilde{E}$</span> isn't a constant) we can derive a contradiction.</p>

<p>Set <span class="math-container">$A=k[X]$</span> and <span class="math-container">$F=k(X)$</span>. The irreducibles of <span class="math-container">$A[Y]$</span> are precisely</p>

<ul>
<li>the irreducibles of <span class="math-container">$A$</span></li>
<li>the (positive degree) polynomials <span class="math-container">$f\in A[Y]$</span> that have content 1 and are irreducible in <span class="math-container">$F[Y]$</span>.</li>
</ul>

<p>Let <span class="math-container">$\widetilde{E}$</span> and <span class="math-container">$\widetilde{P}$</span> be coprime in the UFD <span class="math-container">$k[X,Y]=A[Y]$</span>. If we assume that there are enough <span class="math-container">$x_i$</span> and <span class="math-container">$y_j$</span> as in the theorem, the resultant argument (which has its own (fixable) issues, see <a href="https://mathoverflow.net/q/348657/13700">this question</a>) establishes that <span class="math-container">$\mathrm{Res}_Y(\widetilde{E},\widetilde{P})\in A$</span> is zero, i.e. <span class="math-container">$\widetilde{E}$</span> and <span class="math-container">$\widetilde{P}$</span> aren't coprime in <span class="math-container">$F[Y]$</span>. To produce a contradiction, we will show that they aren't coprime in <span class="math-container">$A[Y]$</span> either.</p>

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

<hr>

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

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

<p>A similar reasoning applies to show that <span class="math-container">$b&lt;d$</span>.</p>

CC BY-SA 4.0
2019-12-20T18:36:24.417Z
2019-12-20T21:12:08.373Z
2019-12-20T21:12:08.373Z
Olivier Bégassat
<p>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. </p>

<p><strong>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</strong></p>

<p>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:
<a href="http://cs.yale.edu/homes/spielman/PAPERS/holographic.pdf" rel="noreferrer">http://cs.yale.edu/homes/spielman/PAPERS/holographic.pdf</a></p>

<p><strong>The problem</strong></p>

<p>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.</p>

<p>I am unable to see how Gauss's lemma trivially establishes this implication.</p>

<p>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]$.</p>

<p>(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.)</p>

CC BY-SA 3.0
2017-09-11T09:59:47.950Z
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.
relG
CC BY-SA 3.0
2017-09-14T09:56:44.897Z
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$.
relG
CC BY-SA 4.0
2019-12-18T19:42:08.390Z
Hi @Brat, I also have questions regarding this test. I posted them on mathoverflow, maybe you encountered the same issue ? https://mathoverflow.net/questions/348657/bivariate-polynomial-divisibility-test-of-spielman
Olivier Bégassat
CC BY-SA 4.0
2019-12-19T17:48:12.800Z
This isn't an answer to your question, simply an observation. The authors assume that $\deg_x(E)\leq \deg_x(P)$ and $\deg_y(E)\leq \deg_y(P)$ which isn't the case for $E=yx^2$ and $P=y^2x$.
Olivier Bégassat
CC BY-SA 4.0
2019-12-19T17:51:09.397Z
I guess that one could hope to do something like so: apply the reasoning relative to $Y$ and $X$, and thus show that the quotient lives in $k(X)[Y]\cap k(Y)[X]=k[X,Y]$, but I'm not sure that works (as the choic of working with polynomials in $Y$ is linked to an assumption $\alpha\geq \beta$ or so (don't remember atm).
Olivier Bégassat
<cc.complexity-theory><coding-theory><algebra><pcp><polynomials>
Bivariate low-degree polynomial testing of Polishchuk-Spielman
Brat
# Bivariate low-degree polynomial testing of Polishchuk-Spielman

(Asked by: username_0 on 2013-08-26)

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

**Tags:** cc.complexity-theory, coding-theory, algebra, pcp, polynomials

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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$.  
> **username_2**: Hi @username_0, I also have questions regarding this test. I posted them on mathoverflow, maybe you encountered the same issue ? https://mathoverflow.net/questions/348657/bivariate-polynomial-divisibility-test-of-spielman  
> **username_2**: This isn't an answer to your question, simply an observation. The authors assume that $\deg_x(E)\leq \deg_x(P)$ and $\deg_y(E)\leq \deg_y(P)$ which isn't the case for $E=yx^2$ and $P=y^2x$.  
> **username_2**: I guess that one could hope to do something like so: apply the reasoning relative to $Y$ and $X$, and thus show that the quotient lives in $k(X)[Y]\cap k(Y)[X]=k[X,Y]$, but I'm not sure that works (as the choic of working with polynomials in $Y$ is linked to an assumption $\alpha\geq \beta$ or so (don't remember atm).  

---

## 2 answers

### Answer by username_3 on 2016-11-17. Score: 2

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

> **Comments:**
> **username_1**: 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.  

---

### Answer by username_2 on 2019-12-20. Score: 0

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](https://mathoverflow.net/q/348657/13700)) 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 or $b. In reality, we must have *both* $a and $b. 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.


---

