6
$\begingroup$

Tarski proved that equalities and inequalities in can be decided over $\mathbb{R}[x].$ Richardson proved that adding composition with the sine and exponential functions caused the problem to become undecidable. What are the best results sharpening this gap?

Laczkovich (improving Wang) was able to show undecidability for the ring generated by the integers, $x$, $\sin x^n,$ and $\sin(x\sin x^n)$ which is the best result I know of in this direction. I don't know of any results on the decidable side.

In particular, is it known whether inequalities over the ring $\mathbb{Z}[x,\sin x]$ are decidable?

$\endgroup$
2

1 Answer 1

5
$\begingroup$

This seems unlikely to have a simple or known decision procedure. Consider the question: For $x>1$, is $x^4$ always greater than $1 + x^4 \sin(x)$?

This is a question of Diophantine approximation. It comes close for $x$=2 or 8 or 33 or 573204. The last one is half a numerator in a continued fraction approximant of $\pi$, and the evaluations of the two terms start with the same 13 digits.

So the concrete question might be nice for people to ponder, and I doubt we'll get an algorithm to solve the question in the original post. A proof of undecidability seems more likely, and difficult.

$\endgroup$
2
  • 1
    $\begingroup$ I agree -- I was asking for the current state of the art, because I don't know where it's at. Do you know of any strengthenings of Tarski's theorem (in this direction) which retain decidability? $\endgroup$
    – Charles
    Feb 13, 2015 at 3:29
  • $\begingroup$ I don't have references for you, but the reference-request tag might help. $\endgroup$
    – user44143
    Feb 13, 2015 at 13:29

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.