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

[Max Alekseyev]

oh, and a final step:
3) compute the given of square roots with enough precision to match
one of the intervals. E.g., if the root intervals around 0 are
[-0.002,-0.001] and [0.001,0.002], precision of 0.001 would be enough
to match one of them.
Basically, Sturm theorem tells us the sufficient precision to which we
should evaluate the given sum.

P.S. Sturm theorem is implemented in PARI/GP as polsturm() and example
of its use for accurate roots isolation is present in
http://oeis.org/A077155

Regards,
Max

On Fri, Feb 17, 2012 at 10:03 AM, Max Alekseyev <maxale at gmail.com> wrote:
> 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/