[abetusk]

Why do you need the bounds for every combination of the N square roots? Isn't it enough to get the minimum distance between the two nearest elements in that list?

If so, why not consider the 2N degree polynomial where P(z) = \prod (z^2 - a_i) ? This polynomial is only 2N degree and gives you the bound you actually care about, the number of bits needed to sum two numbers in the list. Since you're summing 2N of them instead of just one, you might need on the order of lg(N) more bits in your representation (so 2N + lg(N) bits, say) but this is still well within "polynomial" bits.

[devit]

Not clear how a lower bound on the absolute value of the difference of any two of the square roots would help give a lower bound on the absolute value of the difference of the two sums of square roots.

[abetusk]

Sorry to be obtuse, but I don't understand your hesitation.

If you have a lower bound on the absolute value of the smallest difference of any/all pairs of roots, the lower bound on the sum of N of them is at most adding lg(N) bits.

EDIT:

I'm wrong, you're right. You've hit it on the head. My apologies.

Just because there's bounds on pairwise roots, doesn't mean they then can be bounded when they're all summed together.

In other words, say you have d_0 = |a_0 - a_1| and d_1 = |a_2 - a_3|, you might get into a situation where |d_0 - d_1] requires some exponential number of bits to represent.

[tgflynn]

I don't see the problem. Once you have enough bits to resolve every pairwise difference you're just reduced to the problem of comparing the sums of two lists of n bit integers and I'm pretty sure that's in P.

If it's not then that should be the main point here, sqrt has nothing to do with it.

EDIT: You also know what the largest possible error is on each pairwise delta so if you add log(N + 1) bits you handle even the worst case where one sum is +N x maxerror and the other -N x maxerror.