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: http://www.math.ucla.edu/~matthias/pdf/ideal2.pdf. 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$).

  • $\begingroup$ I wrote a little about this phenomenon in my paper, On Resultants, Proc Amer Math Soc 89 (1983) 419-420, available at ams.org/journals/proc/1983-089-03/S0002-9939-1983-0715856-2/… 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$. $\endgroup$ – Gerry Myerson Jan 20 '16 at 23:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.