3 ms·
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
by devit 5y ago
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_polynomial_roots#Root_separation 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 5y agoWhy 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 5y agoNot 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 5y agoSorry 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 5y agoI 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 5y agoYes, 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.
- adgjlsfhk1 5y agoThis is false. PSPACE is in EXPTIME.
- tgflynn 5y agoDo you have a reference for that claim ?
- fdej 5y agoCorrecting 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 5y agoThe 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.