[seqfan] Any algorithm for sign of sums of square roots?
Richard Mathar
mathar at strw.leidenuniv.nl
Fri Feb 17 12:44:22 CET 2012
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
More information about the SeqFan
mailing list