[seqfan] Re: Any algorithm for sign of sums of square roots?

[Max Alekseyev]

I think a general approach would be:
1) construct (iteratively, adding square roots to the expression one
by one) a polynomial with integer coefficients having the given sum as
a root, and then
2) use Sturm theorem and dichotomy to isolate the roots of the
constructed polynomial from 0, i.e., determine intervals (not
containing 0) of its real roots:
http://en.wikipedia.org/wiki/Sturm_theorem

Regards,
Max

On Fri, Feb 17, 2012 at 6:44 AM, Richard Mathar
<mathar at strw.leidenuniv.nl> wrote:
>
> Here is what appears to be some sort of middle-school problem:
> Supposed there is a sum of terms of rational coefficients c_i
> and rational discriminants d_i, can we decide on
>  sum_i c_i*sqrt(d_i) > 0 ?
> All the c_i are in Q, and the d_i are in Q+, so we are in the
> realm of real numbers.
> The task is to compute the sign with integer arithmetic, so just
> conversion to floating point and adding (with some care on
> cancellation of digits) is not allowed.
>
> Is there an algorithm which by some mix of squaring, subtracting
> and moving terms around simplifies to some trivial comparison
> of some sum of rationals, for example?
>
> There are simple cases which can be decided easily:
> i) if all the c_i have the same sign; the sign of the
>  sum is just that common sign.
> ii) If there are two terms with different sign, move one of the
>  square roots to the other side,   c_1*sqrt(d_1) = -c_2*sqrt(d_2),
>  and compare the absolute value of both square by squaring.
>  Squaring translates both square roots to rationals, and these
>  are easily compared by cross-multiplication of the two denominators.
> iii) If there are three terms, two with the same sign and one with
>  another (otherwise, see above), move the term with the single
>  sign to one side of the equation, and again square both sides.
>    c_1*sqrt(d_1)+c_2*sqrt(d_2) > |c_3|*sqrt(d_3)  ?
>  The binomial formula reduces the number of square roots of the
>  left hand side to effectively one; moving all rations to one
>  side and isolating the square root plus another round of
>  squaring decides this too.
> iv) If there are four terms, gathering the one or two terms of one
>  sign on one side and the other sign on the other side, the squaring
>  method of (iii) also succeeds.
> iv) If there is the same number of positive and negative terms and
>  if they are well shuffled in the sense that ordering both subset
>  of terms leaves pairs of numbers where one number of a sign dominates
>  the associated number of the opposite sign, there is again one
>  dominating sign.
> v) In lucky cases, one may remove pairs of terms (which have decidable
>  sign by ii) and the remaining terms have the same sign as what was
>  removed. The sign of the full sum of terms is that common sign.
> The nasty point is that isolating terms of one sign on one side and squaring
> is only efficient if there are no more than three terms on each side;
> otherwise squaring both sides generates more square root terms in
> the inequality than the original problem.
>
> Is there some (perhaps recursive) way of reducing the  question
> for five and more terms? Is this perhaps not decidable for more
> than four terms (maybe by some property of non-solvability of 5th
> order polynomials)? Is there perhaps a method which factorizes
> such a sum so we can get the sign as a product of signs of simpler
> terms?
>
> RJM
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/