3 ms·
> There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots What is it?
by edflsafoiewq 5y ago
> There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots
What is it?
- dooglius 5y agoYou just have to take out square factors from each, and combine terms with matching sqrt(n), and that will be unique
- edflsafoiewq 5y agoHow do you know its unique?
- aliceryhl 5y agoI don't think there's an elementary proof, but you will see a proof if you study algebraic number theory.
- deleted 5y ago[deleted]
- jepler 5y agoThat is to say, rewrite each sqrt(N_i) as P_i * sqrt(Q_i) where P and Q are integers and Q contains no squares. So 2 becomes 1 * sqrt(2), 4 becomes 2 * sqrt(1) and 8 becomes 2 * sqrt(2). Now, you can subtract equal terms from each side of the equation and if you can reach 0=0 then the numbers are equal. If you're left with something like sqrt(3) = 5 * sqrt(2) the the numbers are unequal. This stems from the fact, that I give without proof, that for integers X, Y and Z that contain no squares that sqrt(x) + sqrt(y) is never equal to sqrt(z). So there's no way to (say) add a bunch of square roots of 2 and have it become equal to a square root of 3 or 5. A number contains no squares if its prime factorization contains no repeated factors. Since this seems to involve factorization, plus a step of matching up numbers from both sides, the computational complexity would seem to be at least the complexity of factorization. The term-matching step is presumablty the easier step of the two.