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.$
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_{n-2}+a_n=2b_{n-1}$
$...$
$a_0+a_2=2b_1$
$a_{-1}+a_1=2b_{0}+1$
$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.
