Degree of polynomial gcd

In summary: However, your understanding may be that the requirement is that x and y must be relatively prime (meaning that there are no common factors other than 1 between them). If that is the case, then your understanding is correct and the answer is 3.
  • #1
e_to_the_i_pi
6
0
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=p4(y)x4+p3(y)x3+p2(y)x2+p1(y)x + p0(y), where each pi is a polynomial of degree at most 2 in y. Then there exist at most 2 integers i that cause p4(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?
 
Physics news on Phys.org
  • #2
e_to_the_i_pi said:
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=p4(y)x4+p3(y)x3+p2(y)x2+p1(y)x + p0(y), where each pi is a polynomial of degree at most 2 in y. Then there exist at most 2 integers i that cause p4(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 [tex]p_{4}(y)[/tex] 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.
 
  • #3
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.
 
  • #4
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)
 
Last edited:
  • #5
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.)
 
  • #6
e_to_the_i_pi said:
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.
 
Last edited:
  • #7
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.
 
Last edited:

What is the degree of a polynomial?

The degree of a polynomial is the highest exponent of its variable term. For example, in the polynomial 3x^2 + 5x + 2, the degree is 2.

What is the GCD of two polynomials?

The GCD (Greatest Common Divisor) of two polynomials is the largest polynomial that divides both of the original polynomials evenly. It is also known as the highest common factor.

How do you find the GCD of two polynomials?

To find the GCD of two polynomials, you can use the polynomial long division method or the Euclidean algorithm. Essentially, you divide the polynomials until you get a remainder of 0, and the last non-zero remainder is the GCD.

What is the significance of the degree of polynomial GCD?

The degree of polynomial GCD is important because it helps us determine the complexity of the GCD calculation and the number of common factors between two polynomials. It also helps us simplify and factorize polynomials.

Can the degree of polynomial GCD be higher than the degrees of the original polynomials?

Yes, it is possible for the degree of polynomial GCD to be higher than the degrees of the original polynomials. This happens when the two polynomials have a common factor with a higher degree than the individual polynomials.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
885
  • Linear and Abstract Algebra
Replies
3
Views
718
  • Linear and Abstract Algebra
Replies
8
Views
993
Replies
1
Views
915
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
343
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
Back
Top