5
$\begingroup$

I've been working with a collaborator (Arek Goetz) on a dynamics problem involving piecewise isometries (a map $T$ on a domain $X$ (say a subset of the plane) such that $X$ is divided into a finite number of polygonal regions and a separate isometry is applied to each).

In the case where the defining isometries are all rotations through rational angles, it is often possible to use exact computer arithmetic to define points, lines, regions etc. in terms of integer linear combinations of roots of unity.

The following algorithmic question then arises:

Let $(a_i)_{i=1}^n$ be a finite sequence of integers and $(p_i/K)_{i=1}^n$ be a sequence of rationals. Is there a non-analytic algorithm to decide the sign of $\sum a_i\sin(2\pi p_i/K)$?

More generally, given a real algebraic number $\zeta$, is there any nice way to decide the sign of an integer polynomial in $\zeta$ (I can do the quadratic case!)

Improve this question
$\endgroup$
4
  • $\begingroup$ What is an analytic algorithm? $\endgroup$
    – Qiaochu Yuan
    Commented Jul 8, 2011 at 18:18
  • $\begingroup$ I'm guessing that Anthony means "closed-form" or "exact" non-iterative method when he says analytic algorithm $\endgroup$
    – Suvrit
    Commented Jul 8, 2011 at 18:53
  • $\begingroup$ Sorry. What I had in mind here is that one possibility is to use something like an $n$th order Taylor series to estimate the sum. This will also give you an error bound which decreases to 0 in $n$. Since you can be sure that the sum is not 0 (this is finitely checkable since everything is algebraic) you are on one side of zero or the other. The intervals that you obtain from Taylor's theorem will therefore be eventually in the positive reals or eventually in the negative reals $\endgroup$
    – Anthony Quas
    Commented Jul 8, 2011 at 19:39
  • $\begingroup$ Your question suggests that the p_i are integers. Are they? If so, what about using addition formulae to reduce or eliminate some of the summands? Gerhard "Email Me About System Design" Paseman, 2011.07.08 $\endgroup$
    – Gerhard Paseman
    Commented Jul 9, 2011 at 1:48

1 Answer 1

Reset to default
1
$\begingroup$

See

http://cgi.di.uoa.gr/~et/papers/et-computations-alg-numbers2.pdf

particularly section 3.3

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks very much for the reference. I'll try and see to what extent this answers the question. $\endgroup$
    – Anthony Quas
    Commented Jul 8, 2011 at 19:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .