[seqfan] Re: Any algorithm for sign of sums of square roots?
Max Alekseyev
maxale at gmail.com
Fri Feb 17 16:03:59 CET 2012
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/
More information about the SeqFan
mailing list