MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A$ and $B$ be two polynomials in $\mathbf Z[X]$ which generate $\mathbf Z[X]$, that is assume that there exist polynomials $U$ and $V$ in $\mathbf Z[X]$ such that $$ A \cdot U + B \cdot V=1. $$

I realized only recently that (contrary to what happens over $\mathbf Q[X]$) one can not a priori bound the degrees of (some) $U$ and $V$ by a function of the degrees of $A$ and $B$. (The point is that I do not assume $A$ nor $B$ to be monic; therefore Euclidean division is not possible.)

For example, for two integers $p>1$ and $d> 1$ the polynomials $$ A=1-pX \qquad \text{ and } \qquad B=p^d X$$ do generate $\mathbf Z[X]$ for one can take $U_0=1 + pX +\dots + p^{d−1}X^{d−1}$ and $V_0= X^{d-1}$. Moreover, any such Bézout identity in $\mathbf Z[X]$ must have $U$ and $V$ with at least these degrees since reducing modulo $p^d$ shows that $\overline{U}$ is the inverse of $\overline{A}$ in $\mathbf Z/p^d\mathbf Z[X]$ and is therefore equal to $\overline{U_0}$.

The above example is taken from the introduction of the following article by Matthias Aschenbrenner: This article considers the problem for multivariate polynomials $A,B \in \mathbf Z[X_1, \cdots, X_N]$ and gives bounds as a certain complicated function of the degrees of $A$ and $B$ and the height of their coefficients.

I think the situation should however be dramatically simpler in the univariate case. My question thus is: give an explicit (and sharp) bound for the degree of some $U$ (or $V$) as a function of the coefficients of $A$ and $B$ and their degrees.

A subsidiary question would be: once a bound is found, determining for two given polynomials $A$ and $B$ whether they generate $\mathbf Z[X]$ becomes a linear algebra problem (over $\mathbf Z$). As far as I understood, one can use integral Gröbner basis to solve this problem. Is the Gröbner basis approach more or less equivalent to the linear algebra approach?

A sub-subsidiary question would be: what can be said when $A,B \in \mathbf Z[X,Y]$ (the article of Matthias Aschenbrenner suggests that the problem becomes more complicated (or at least less understood) when the number of indeterminates is $\geqslant 3$).

share|cite|improve this question
I wrote a little about this phenomenon in my paper, On Resultants, Proc Amer Math Soc 89 (1983) 419-420, available at… I gave the example $A=2x+1$, $B=2x+17$, which requires $U,V$ of degree 4. I suspect one can get a bound in terms of the largest $e$ such that $p^e$ divides the resultant of $A$ and $B$ for some prime $p$. – Gerry Myerson Jan 20 at 23:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.