Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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.