[devit]

Does that actually work?

It seems that the degree of minimal polynomial having as root the sum of N square roots might be up to 2^N, and if you then apply the bound at https://en.wikipedia.org/wiki/Geometrical_properties_of_poly... (where n = 2^N) you get a bound on the order of at least 2^N digits (more precisely 2^N (N + D)).

So it doesn't seem to lead to a proof of a subexponential number of equal digits, unless the degree of the minimal polynomial is actually subexponential.

[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.

[fdej]

Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which is false.

[tgflynn]

Do you have a reference for that claim ?

[fdej]

Correcting myself, the bound is worse than exponential (so read "at least exponential in N"), but the point I wanted to make is that it is explicit.

Again, this follows from the general theory of algebraic numbers: the degree and height of a sum, product or root of algebraic numbers can be bounded explicitly (resultants + Mignotte bound for factors), and finally root separation bounds can be applied to the resulting polynomial.

[tgflynn]

The author says that this problem is in PSPACE. That's not obvious to me because I don't know how you sum arbitrarily long binary numbers in polynomial space.

However if you and he are both right that would suffice to prove P != PSPACE, so this problem is potentially very important. Unfortunately I don't even know what this kind of problem is called, which makes googling a bit difficult.

[adgjlsfhk1]

This is false. PSPACE is in EXPTIME.