Comparing sums of square roots

Definitions and mathematical statement

Given nonnegative integers $a_1,\ldots,a_m,b_1,\ldots,b_n$ in binary, consider the real algebraic number \[ D=\sum_{i=1}^m\sqrt{a_i}-\sum_{j=1}^n\sqrt{b_j}, \] where square roots are the nonnegative ones. Let $L$ be the total binary input length, including list delimiters. The computational question is whether a deterministic Turing machine can output the exact sign of $D$ in time polynomial in $L$. Equality is an allowed outcome. Comparing a single sum with an integer is included by using one square radicand on the other side.

A related separation problem asks for a polynomial $p$, independent of the input, such that every nonzero $D$ satisfies $|D|\ge2^{-p(L)}$. Such a bound would make sufficiently accurate rational interval approximations decisive, with equality handled by the same separation gap. It would therefore suffice for polynomial-time comparison.

The catalogue calls these requests equivalent, but no converse is assumed here: an exact symbolic decision algorithm need not obtain its answer from a uniform numerical separation bound. The computational model is bit arithmetic, not a real-arithmetic model in which arbitrary radicals and their comparisons are single unit-cost operations.

Short English statement

Can two sums of integer square roots be compared exactly using only polynomially many bit operations? A polynomial separation bound would be one sufficient route, rather than an assumed equivalent statement.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3900014 (AMR-038-0014), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Eppstein - The Geometry Junkyard: Open Problems, Comparing sums of square roots. Original source indexed by AMR-038-0014. https://ics.uci.edu/~eppstein/junkyard/open.html.
• S3 David Eppstein, Geometry Junkyard, Radical difference. https://ics.uci.edu/~eppstein/junkyard/small-dist.html.