[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


More information about the SeqFan mailing list