Don't understand lemma about primitive polynomial product

[swampwiz]

I was reading about Gauss's Lemma here:

https://cims.nyu.edu/~kiryl/Algebra/Section_3.10--Polynomials_Over_The_Rational_Field.pdf

Unfortunately, I am stuck on Lemma 3.10.1 that concludes that the product of a pair of primitive polynomials is itself primitive.

I understand about how there is some index in each polynomial at which the polynomial becomes imprimitive, and that the term c_{j + k} is of the form:

c_{j + k} = a_j b_k + T_a g_a + T_b g_b

where g_a & g_b are the Greatest Common Divisor of the terms below a_j & b_k, respectively (here, I use T_a & T_b to denote general numbers that are multiplied by g_a & g_b to get the terms for the summation of the products of a & b terms whose index is less than i & j, respectively)

So the proof follows that it presumes that c_{j + k} has a prime divisor. Now, if I presume that this divisor is the same as g_a & g_b, then I get the contradiction that c_{j + k} has no divisor. Fine. However if I only presume that the divisor is the same as g_a, but not g_b, I get

(here U is a general number like T)

c_{j + k} = g_a U = a_j b_k + T_a g_a + T_b g_b

a_j b_k = g_a ( U - T_a ) - g_b T_b

Now I don't know what prime factors a_j or b_k have, and it seems that I have no way of proving that the RHS of this doesn't coincidentally sum up to a number that happens to be a multiple of whatever prime factors a_j or b_k

What am I missing here?

 

[mathman]

The point is f(x) and g(x) are primitive, so the assumed prime p which divides f(x)g(x) cannot divide f(x) or g(x). Therefore there exists $a_j,\ b_k$ which are not (and lowest indices having this property). $c_{j+k}$ is the sum of three terms, two if which have p as a divisor. Therefore the third term $a_jb_k$ must also have p as a divisor, but this a contradiction, because p does not divide either factor.

 

[fresh_42]

I was reading about Gauss's Lemma here:

https://cims.nyu.edu/~kiryl/Algebra/Section_3.10--Polynomials_Over_The_Rational_Field.pdf

Unfortunately, I am stuck on Lemma 3.10.1 that concludes that the product of a pair of primitive polynomials is itself primitive.

I understand about how there is some index in each polynomial at which the polynomial becomes imprimitive, and that the term c_{j + k} is of the form:

c_{j + k} = a_j b_k + T_a g_a + T_b g_b

where g_a & g_b are the Greatest Common Divisor of the terms below a_j & b_k, respectively (here, I use T_a & T_b to denote general numbers that are multiplied by g_a & g_b to get the terms for the summation of the products of a & b terms whose index is less than i & j, respectively)

So the proof follows that it presumes that c_{j + k} has a prime divisor. Now, if I presume that this divisor is the same as g_a & g_b, then I get the contradiction that c_{j + k} has no divisor. Fine. However if I only presume that the divisor is the same as g_a, but not g_b, I get

(here U is a general number like T)

c_{j + k} = g_a U = a_j b_k + T_a g_a + T_b g_b

a_j b_k = g_a ( U - T_a ) - g_b T_b

Now I don't know what prime factors a_j or b_k have, and it seems that I have no way of proving that the RHS of this doesn't coincidentally sum up to a number that happens to be a multiple of whatever prime factors a_j or b_k

What am I missing here?

Your change of notation makes it tough to argue. You need to have a closer look on what $g_a$ and $g_b$ actually are. The proof assumes that a prime $p$ divides $c_{j+k}$ and in addition that $p | a_0 , \dots , a_{j-1}$ as well as $p | b_0 , \dots , b_{k-1}.$ Therefore both of your $g_a$ and $g_b$ must be divisible by $p$, hence $c_{j+k} - g_a T_a - g_b T_b = a_j b_k$ is divisible by $p$ which can't be, because neither $a_j$ nor $b_k$ is.

 

[swampwiz]

Your change of notation makes it tough to argue. You need to have a closer look on what $g_a$ and $g_b$ actually are. The proof assumes that a prime $p$ divides $c_{j+k}$ and in addition that $p | a_0 , \dots , a_{j-1}$ as well as $p | b_0 , \dots , b_{k-1}.$ Therefore both of your $g_a$ and $g_b$ must be divisible by $p$, hence $c_{j+k} - g_a T_a - g_b T_b = a_j b_k$ is divisible by $p$ which can't be, because neither $a_j$ nor $b_k$ is.

OK, but should the statement "f( x ) and g( x ) are primitive polynomials" be interpreted such that terms below i & j are divisible by the same prime?

E.G.

f( x ) = 2 x³ + 7 x² + 4 x + 2

g( x ) = 11 x³ + 5 x² + 9 x + 3

below i = 2, f( x ) is divisible by 2

below j = 2, g( x ) is divisible by 3

Here they are not divisible by the same prime, but each of them are primitive (and imprimitive up to i or j = 1 )

Using my notation:

a₂ b₂ = 35

g_a = 2

T_a = 9

g_b = 3

T_b = 11

U = T_a + ( a₂ b₂ + g_b T_b ) / g_a = 9 + [ ( 7 ) ( 5 ) + ( 3 ) ( 11 ) ] / ( 2 ) = 9 + 68 / 2 = 43

c_{2 + 2} = g_a U = ( 2 ) ( 43 ) = 86

The presumption was that c_{2 + 2} would be divisible by g_a, which would mean that U would be an integer. This presumption was supposed to end being proven false.

 

[fresh_42]

OK, but should the statement "f( x ) and g( x ) are primitive polynomials" be interpreted such that terms below i & j are divisible by the same prime?

No. Primitive polynomials cannot be divided by any prime, that's the definition.
The assumption is that $f(x) \cdot g(x)$ is divided by a prime $p_0$ (in order to show that this cannot be the case either and thus proving that there is no $p_0,$ which in turn means that $f(x) \cdot g(x)$ is primitive, too.)

Because $f(x)$ and $g(x)$ are primitive, the $p_0$ from our assumption cannot divide them, i.e $p_0$ cannot divide all coefficients. Therefore there must be a first index $j$ for $f(x)$ and $k$ for $g(x)$ so that the coefficients $a_j$ and $b_k$ are not divided by $p_0$.
Since we took the first, all from $0$ to $j-1$, $0$ to $k-1,$ resp. are divisible by $p_0$. This makes your $g_a$ and $g_b$ divisible by $p_0,$ too, and in the end $a_j \cdot b_k$ divisible by $p_0.$ Since $p_0$ doesn't divide neither $a_j$ nor $b_k$ because we choose them not to do, it cannot divide their product - a contradiction, i.e. the assumptions that there is a $p_0$ dividing $f(x) \cdot g(x)$ was wrong.

(I wrote $p_0$ simply to emphasize that it is a special prime number assumed to exist, dividing the product, not the single polynomials. The proof then shows it cannot exist. Since there isn't any special prime, it means there isn't any at all.)

 

[swampwiz]

No. Primitive polynomials cannot be divided by any prime, that's the definition.
The assumption is that $f(x) \cdot g(x)$ is divided by a prime $p_0$ (in order to show that this cannot be the case either and thus proving that there is no $p_0,$ which in turn means that $f(x) \cdot g(x)$ is primitive, too.)

Because $f(x)$ and $g(x)$ are primitive, the $p_0$ from our assumption cannot divide them, i.e $p_0$ cannot divide all coefficients. Therefore there must be a first index $j$ for $f(x)$ and $k$ for $g(x)$ so that the coefficients $a_j$ and $b_k$ are not divided by $p_0$.
Since we took the first, all from $0$ to $j-1$, $0$ to $k-1,$ resp. are divisible by $p_0$. This makes your $g_a$ and $g_b$ divisible by $p_0,$ too, and in the end $a_j \cdot b_k$ divisible by $p_0.$ Since $p_0$ doesn't divide neither $a_j$ nor $b_k$ because we choose them not to do, it cannot divide their product - a contradiction, i.e. the assumptions that there is a $p_0$ dividing $f(x) \cdot g(x)$ was wrong.

(I wrote $p_0$ simply to emphasize that it is a special prime number assumed to exist, dividing the product, not the single polynomials. The proof then shows it cannot exist. Since there isn't any special prime, it means there isn't any at all.)

My example showed that g_a = 2 & g_b = 3, so there is no prime that divides both of them. Are you trying to say that this lemma would not apply to my example because they don't share a common divisor (i.e., up to the point at which they become primitive)? But the lemma says that this applies to any primitive polynomials. Are not my f( x ) & g( x ) primitive, and therefore covered by the lemma definition?

 

[swampwiz]

OK, I think I finally have it! I have no idea why that author felt the need to give such a complicated explanation.

If there are 2 primitive polynomials φ( x ) & ψ( x ) such that f( x ) = φ( x ) ψ( x ) and then f( x ) were presumed to be imprimitive, then there must be some integral polynomial h( x ) and a prime number p such that f( x ) = p h( x ), which would imply that either φ( x ) or ψ( x ) must be the product of p and some integral polynomial, thereby contradicting the initial proposition that the pair were both primitive.

Is it this simple?

 

[fresh_42]

OK, I think I finally have it! I have no idea why that author felt the need to give such a complicated explanation.

If there are 2 primitive polynomials φ( x ) & ψ( x ) such that f( x ) = φ( x ) ψ( x ) and then f( x ) were presumed to be imprimitive, then there must be some integral polynomial h( x ) and a prime number p such that f( x ) = p h( x ), which would imply that either φ( x ) or ψ( x ) must be the product of p and some integral polynomial, thereby contradicting the initial proposition that the pair were both primitive.

Is it this simple?

The "difficulty" comes in what I highlighted in your question. Why would this be implied? The answer to it is the "complicated" proof the author gave. Of course it is as simple, but you have to rule out, that you cannot "create" a divisor $p_0$ in the product, because the coefficients of the product polynomial aren't simply products of the coefficients of the factor polynomials but sums of them. So one has to show that summation doesn't "create" a divisor where there have not been one in the summands. This is what it's all about!

(Concerning your previous post: It doesn't matter whether $2 = g_a$ or $3 =g_b$. The assumption (to achieve the contradiction) is that there is one divisor of the product knowing there isn't one for the single factors.)

 

[swampwiz]

OK, now I really think I have it. I had misinterpreted the meaning of the what i & j represent; they represent not the first term that makes the polynomials primitive, but rather the first term that does not divide some proposed prime p, and for the polynomials to be primitive, all there needs to be is that this i & j exist for every prime - which makes sense since if there were a p in which this i & j didn't exist, the polynomials would not be primitive! So what is happening is that this analysis goes forward for every prime (which means that for "almost all" primes, i & j are both simply 0). My notion of an independent g_a & g_b was incorrect, as the parameters should be the p that is proposed, and thus my condition of both g_a & g_b being equal in essence was coincidentally correct for the case of the proposed prime being that value. The summation to get T_a & T_b was also correct, but both of these parameters should have been multiplied by the proposed prime p, an hence, what should be done is for every prime p

c_{i + j} = a_i b_j + p ( T_a & T_b )

if the product of the polynomials is not primitive, then there must be a non-empty set of primes for which

c_{i + j} % p = 0

c_{i + j} % p = [ a_i b_j + p ( T_a & T_b ) ] % p = ( a_i b_j ) % p

but by the very definition of i & j (for every prime) is that they don't divide that specific prime, so ( a_i b_j ) % p != 0 and thus
c_{i + j} % p != 0, which is a contradiction of the premise, and thus the product must be primitive.