2

Let $Q(x, y)$ be a bivariate polynomial over some field $\mathbb{F}$, and $P(x)$ a univariate polynomial over $\mathbb{F}$ such that $Q(P(x), x) = 0$ for every $x$.

Show that then, $Q(x, y) = (y - P(x))A(x, y)$ for some polynomial $A(x, y)$.

This is a self-exercice from Arora & Barak "Computational complexity", Chapter 19. I am stuck.

[EDIT : this might be a mistake in the statement. See comments.]

Manuel Lafond
  • 3,374
  • Over $\mathbb{C}$, take $Q(x,y)=x-y^2$ and $P(x)=x^2$. Then $Q(P(x),x)=x^2-x^2=0$ but $Q$ is irreducible. – User3773 Jan 11 '16 at 20:21
  • Hmm that sounds right. Would you care to look at the problem statement from the book ? It's Exercice 19.16 at http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=2D058C551DBB88D5CBD5B5F884F6C5DB?doi=10.1.1.297.6224&rep=rep1&type=pdf#page=367. Did I miss something ? – Manuel Lafond Jan 11 '16 at 21:37
  • Actually, it is strange. What do you mean with bivariate and univariate? For what I read on Wolfram MathWorld they are just polynomial in two, resp. one, variables.. I am still convinced of my first comment and so I am tempted to say that maybe the statement is incomplete or the definition of bivariate is another one.. – User3773 Jan 12 '16 at 10:56
  • Or sometimes the solution is easier and there was just a typo: the claim should be $Q(x,y)=(x-P(y))A(x,y)$. The exercise requires nothing about the triviality of $A$ and hence my first comment fits perfectly in this case. – User3773 Jan 12 '16 at 11:06
  • You may be right...I don't know really ! At least, your statement works with the counter-example, and I can't find any other. I still can't prove it though, so if you have a proof, I'm interested :) – Manuel Lafond Jan 12 '16 at 19:13
  • Well, it seems to me quite intuitive and clear now. By the way, a geometric way to justify it is to put $V={(a,b)\in\mathbb{F},|,Q(a,b)=0}$ and $V'={(a,b)\in\mathbb{F},|,Q'(a,b)=0}$ where $Q'(x,y)=x-P(y)$. The hypothesis reads $V'\subset V$ and hence $Q$ factorises through $Q'$. – User3773 Jan 13 '16 at 14:13
  • Thank you for your explanations! It all makes sense now. – Manuel Lafond Jan 13 '16 at 16:41
  • Your welcome! Happy to be helpful. – User3773 Jan 13 '16 at 16:55
  • @ManuelLafond Do you know a proof for this claim? – Don Fanucci Nov 28 '17 at 18:59
  • @TrueTopologist Hm...I did understand Cla's last comment at the time, 2 years ago. But now I'm not sure. The argument is that whenever $x - P(y) = 0$, we have $Q(x, y) = 0$ (using the initial hypothesis on $Q$). And therefore, $Q$ must factorize through $x - P(y)$. I'm just not sure about the last "therefore" - I don't remember why that works. Maybe you'll have an idea :) – Manuel Lafond Nov 30 '17 at 22:36

0 Answers0