Degree of polynomial gcd

[e_to_the_i_pi]

Problem: Let R=Q[y] and suppose f,g \in F[x] both have degree 10 with respect to x and degree 6 with respect to y. Suppose h = gcd(f,g) has degree 4 with respect to x and degree 2 with respect to y. Derive an upper bound (as good as possible) on the number of distinct integers i such that gcd(f(x,i), g(x,i)) \in Q[x] has degree not equal to 4.

Start of solution: We can write h as h=p₄(y)x⁴+p₃(y)x³+p₂(y)x²+p₁(y)x + p₀(y), where each p_i is a polynomial of degree at most 2 in y. Then there exist at most 2 integers i that cause p₄(y) to evaluate to zero, thus dropping the degree of h.

Also, evaluating f(x,i) is equivalent to computing f(x,y) mod (y-i). I know that there are results that say precisely when gcd(f mod i, g mod i) = gcd(f,g) mod i, and I suspect that these are required to find the remainder of the cases. But that's about as far as I can get. What results should I use to proceed?

 

[ramsey2879]

Problem: Let R=Q[y] and suppose f,g \in F[x] both have degree 10 with respect to x and degree 6 with respect to y. Suppose h = gcd(f,g) has degree 4 with respect to x and degree 2 with respect to y. Derive an upper bound (as good as possible) on the number of distinct integers i such that gcd(f(x,i), g(x,i)) \in Q[x] has degree not equal to 4.

Start of solution: We can write h as h=p₄(y)x⁴+p₃(y)x³+p₂(y)x²+p₁(y)x + p₀(y), where each p_i is a polynomial of degree at most 2 in y. Then there exist at most 2 integers i that cause p₄(y) to evaluate to zero, thus dropping the degree of h.

Also, evaluating f(x,i) is equivalent to computing f(x,y) mod (y-i). I know that there are results that say precisely when gcd(f mod i, g mod i) = gcd(f,g) mod i, and I suspect that these are required to find the remainder of the cases. But that's about as far as I can get. What results should I use to proceed?

This is not my subject but if there are at most 2 integers i that could cause $$p_{4}(y)$$ to equal zero then that would seem to be the answer. My gut feeling is that it doesn't matter what the other values may be for they cannot result in a polynomial of degree less than 4 in x.

 

[e_to_the_i_pi]

That does indeed seem to be the intuitive answer, however I suspect it is incorrect.

The reason is this: in general gcd(f(x) mod p, g(x) mod p) \neq gcd(f(x),g(x)) mod p. In particular, if p divides the gcd of the leading coefficients of f and g, then the two gcd's are different (and usually the gcd of f(x) mod p and g(x) mod p has degree higher than the true gcd -- but it can be proven that the degree of the gcd is never lower). For this reason I am pretty sure that I have described all cases in which the degree is less than 4, but there are probably remaining cases when the gcd is greater than 4 (since f(x,i) = f(x,y) mod (y-i) and g(x,i) = g(x,y) mod (y-i)). To count them, I suspect, relies on the degrees of f and g with respect to x and y.

 

[ramsey2879]

I stand by my answer since my understanding is that h(x) = gcd(f(x,y),g(x,y)) is to the fourth degree in x and the 2nd degree in y. Thus only if one of two specific values of y are chosen, can the coefficient of x^4 be zero. As that appears to me to be apparent from the statement of the problem, you didn't convince me otherwise. ramsey2879 (note although adding powers of x and y can for specific terms add to 6, f(x,i) assumes a constant y value)

 

[e_to_the_i_pi]

And I stand by my objection to your answer, since (I believe) it is simply not the case that gcd(f(x,y),g(x,y)) evaluated at i is equal to gcd(f(x,i),g(x,i)) in general. (That is, the operations of taking a gcd and evaluating at a point only commute when certain conditions are satisfied. If I could find precisely what these conditions are, I could finish the problem. When I do, I will post what I have found here.)

 

[ramsey2879]

And I stand by my objection to your answer, since (I believe) it is simply not the case that gcd(f(x,y),g(x,y)) evaluated at i is equal to gcd(f(x,i),g(x,i)) in general. (That is, the operations of taking a gcd and evaluating at a point only commute when certain conditions are satisfied. If I could find precisely what these conditions are, I could finish the problem. When I do, I will post what I have found here.)

We may be working on two differing understandings of the same problem. My understanding is that the requirements of f(x,y) and g(x,y) are that the gcd(f(x,y),g(x,y)) is limited to degree 4 in x and degree 2 in y (although in general the gcd is not so limited) and thereafter x is kept variable while y takes the constant value of i. Is that your understanding also?
Edit: Also while gcd(f(x,i),g(x,i)) at specific points may calculate differently than h(x,i), I think the problem is asking for what values of y is h(x,y) in effect of a degree lower than 4 in x.

 

[e_to_the_i_pi]

Ok, here goes.

Let's consider f(x,y) and g(x,y) as polynomials in x with coefficients in Q[y]. Then Computing gcd( f(x,i), g(y,i) ) is equivalent to computing gcd( f(x,y) mod (y-i), g(x,y) mod (y-i) ), where each y-i is a prime Q[y].

Thus, in order to determine when gcd( f(x,i), g(x,i) ) = h(x,i) where h(x,y)=gcd( f(x,y),g(x,y) ) over Q[x,y], we must compute the resultant of f/h and g/h; then, any prime dividing the resultant may yield a polynomial of the incorrect degree. We do this by using taking the determinant of the Sylvester matrix of these two polynomials.

Because both f and g have degree 10 w.r.t. x and degree 6 w.r.t. y, while h has degree 4 w.r.t x and degree 2 w.r.t. y, it follows that f/h and g/h each have degree 6 w.r.t. x and degree 2 w.r.t. y.

Thus, the Sylvester matrix is a 12x12 matrix where the entries are are polynomials of degree 2 w.r.t. y. Therefore, the determinant has degree at most 2*12=24 w.r.t. y. In the worst case, this means that the resultant has 24 linear factors. Hence, there are at most 24 distinct values of i that yield a gcd with degree not equal to 4.

EDIT: this post characterizes all instances when the degree of the gcd is greater than 4. My initial post characterized all instances in which the degree of the gcd is smaller than 4, thus the total is actually 24+2=26.