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

Is there an algorithm to determine for given $P,Q$ in $\mathbb Z[x,x^{-1}]$ with $gcd(P,Q)=1$, the value of $min\lbrace Span(A)+Span(B): A,B\in \mathbb Z[x,x^{-1}],\ A\cdot P+B\cdot Q=1\rbrace$, where $Span()$ is the span of a Laurent polynomial?

More generally, determine the set of all pairs $(n,m)$ of positive integers such that $AP+BQ\ne 1$ for all $P,Q$ with $Span(A) < n$ and $Span(B) < m.$

share|cite|improve this question
Maybe you should explain what is the span of a Laurent polynomial. – Lierre Dec 22 '12 at 9:19
It is the difference between the highest power of x and the lowest one appearing in the polynomial. – Adam Dec 23 '12 at 1:14

This is too long for a comment.
I don't think the minimum always exists, i.e. that Bézout's identity can be fulfilled. In $\mathbb Q[x,x^{-1}]$ it would be the case, but not in $\mathbb Z[x,x^{-1}]$. Take $P=x+\frac1x$ and $Q=-2$. Supposing there are $A,B\in\mathbb Z[x,x^{-1}]$ such that $AP+BQ=1$, say
$A=a_nx^n+\cdots+a_{-n}x^{-n}$ and $B=b_nx^n+\cdots+b_{-n}x^{-n}$ (possible by choosing $n$ big enough). Equating coefficients we get the system

$a_n\qquad \quad =0$
$a_{n-1}\qquad =2b_n$
$a_{ -2}+a_0=2b_{-1}$
$a_{-n}+a_{-n+2} =2b_{-n+1}$
$.\qquad a_{-n+1} =2b_{-n}$
$.\qquad a_{-n}\quad =0$

So we find successively from the top $a_{n-1}\equiv a_{n-2}\equiv \cdots\equiv a_1\equiv 0\pmod 2$ and from the bottom $a_{-n+1}\equiv a_{-n+2}\equiv \cdots\equiv a_{-1}\equiv 0\pmod 2$ which yields a contradiction in the middle.

So even though the $gcd$ may be well-defined, it looks like $\mathbb Z[x,x^{-1}]$ is not an Euclidean domain.

share|cite|improve this answer
Perhaps a simpler proof: if $AP+BQ=1$, then $(x^2+1)A^*+2B^*=x^r$ for some polynomials $A^*$ and $B^*$ and some $r$, but at $x=1$ the left side is even, the right, odd. – Gerry Myerson Feb 26 '13 at 22:23

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.