Take the 2-minute tour ×

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|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 S Sikora Dec 23 '12 at 1:14

1 Answer 1

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|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


