Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

1 Answer

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

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.