0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Maybe you should explain what is the span of a Laurent polynomial. $\endgroup$
    – Lierre
    Dec 22, 2012 at 9:19
  • $\begingroup$ It is the difference between the highest power of x and the lowest one appearing in the polynomial. $\endgroup$
    – Adam
    Dec 23, 2012 at 1:14

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 26, 2013 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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