0
$\begingroup$

Assuming two polynomials $P_1,P_2 \in \mathbb{Z}_p[r]$ of degree $n$, with no common factors, we know that there exist polynomials $Q_1,Q_2$ s.t.: $Q_1P_1 + Q_2P_2 =1$. From Bezout's identity we also know that $deg(Q_i)<n$ for $i=1,2$.

I am wondering how the above is generalized in the case of more than two polynomials. More specifically, given polynomials $P_i$ for $i=1,...,t$ of degree $n$ with $GCD(P_1,...,P_t) = 1$ there exist polynomials $Q_i$ s.t.: $\sum_{i=1}^tQ_iP_i = 1$. What is the maximum degree of these polynomials $Q_i$? Notice that polynomials $P_i$ may have some common factors when taken pairwise, however there is no common factor shared by all $t$ of them,

I can think of examples of where at least some of the $Q_i$'s have degree larger than $n$ but for all the cases I can come up with, the total sum of their degrees is less than $tn$. That is, $\sum_{i=1}^tdeg(Q_i) < tn$, however I am not able to come up with a proof for this claim.

Can someone point out some direction towards such a proof or invalidate it if it false?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You can just recursively compute the gcd of $t\ge 2$ polynomials by $$ \gcd(P_1, P_2, \dots , P_t) = \gcd( P_1, \gcd(P_2, \dots , P_t)), $$ starting with $\gcd(P_{t-1},P_t)$, $\gcd(P_{t-2}, \gcd(P_{t-1},P_t))$ etc. If you do this with the extended Euclidean algorithm you obtain the Bezout-coefficients, i.e., polynomials $Q_1,\ldots ,Q_t$, and one can estimate the degree (also the degree of a gcd of univariate polynomials can be estimated by Barnett's theorem, see http://www.sciencedirect.com/science/article/pii/S0747717102905420).

Edit: The estimate on the degrees obtained in this way may not be optimal, of course. However, as soon as one can find $P_i$ and $P_j$ with $\gcd(P_i,P_j)=1$, one has $1=Q_iP_i+Q_jP_j=\sum_{k=1}^tQ_kP_k$ with all other $Q_k=0$, and $\sum_{k=1}^t\deg (Q_k)\le 2n$. Otherwise each pair $(P_i,P_j)$ has a non-trivial gcd, and this should help to reduce the total degree of the $Q_i$'s.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer but it does not really address my point. I am interested in explicitly constructing polynomials $Q_i$ and not in computing the GCD (after all, I already know the GCD is 1 in the situation I am working at). Of course recursively applying the extended Euclidean will give the GCD and help compute the polynomials $Q_i$. If at each step I compute polynomials $L_i,R_{i+1}$ s.t. $L_iP_i + R_{i+1}P_{i+1} = gcd(P_i,P_{i+1}$ for $i=t-1,...,1$, the polynomials $Q_i$ will be computed as a multiplication of the $L_i$'s and $R_i$'s. I am interested in an upper bound on their degree. $\endgroup$
    – Jonathan Naysmith
    Commented Jul 16, 2013 at 13:40
  • $\begingroup$ So are you saying the the degree of each $Q_i$ can be be up to $(t-1)n$ (due to $t-1$ multiplications of up to $n$ degree polynomials)? $\endgroup$
    – Jonathan Naysmith
    Commented Jul 16, 2013 at 14:15
  • $\begingroup$ Not each $Q_i$. Try $t=3$ with $P_1,P_2,P_3$ and $gcd(P_2,P_3)=R_2P_2+R_3P_3$ $1=gcd(P_1,P_2,P_3)=Q_1P_1+Q_2R_2P_2+Q_2R_3P_3$. $\endgroup$
    – Dietrich Burde
    Commented Jul 16, 2013 at 14:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .