Square-root sum problem

SRS is defined as follows:{{Cite journal |last=Goemans |first=Michel X. |date=1997-10-01 |title=Semidefinite programming in combinatorial optimization |url=https://doi.org/10.1007/BF02614315 |journal=Mathematical Programming |language=en |volume=79 |issue=1 |pages=143–161 |doi=10.1007/BF02614315 |s2cid=17221714 |issn=1436-4646}}

Given positive integers $a\_1,\backslash ldots,a\_k$ and an integer t, decide whether $\backslash sum\_\{i=1\}^k\; \backslash sqrt\{a\_i\}\; \backslash leq\; t$.

Given positive integers $a\_1,\backslash ldots,a\_k$ and $b\_1,\backslash ldots,b\_k$, decide whether $\backslash sum\_\{i=1\}^k\; \backslash sqrt\{a\_i\}\; \backslash leq\; \backslash sum\_\{i=1\}^k\; \backslash sqrt\{b\_i\}$.

The problem was posed in 1981,{{Cite journal |first=Joseph |last=O’Rourke |title=Advanced problem 6369 |journal= Amer. Math. Monthly | pages=769|volume=88|issue=10|year=1981}} and likely earlier.

SRS can be solved in polynomial time in the Real RAM model.{{Cite journal |last=Tiwari |first=Prasoon |date=1992-12-01 |title=A problem that is easier to solve on the unit-cost algebraic RAM |url=https://dx.doi.org/10.1016/0885-064X%2892%2990003-T |journal=Journal of Complexity |volume=8 |issue=4 |pages=393–397 |doi=10.1016/0885-064X(92)90003-T |issn=0885-064X}} However, its run-time complexity in the Turing machine model is open, as of 1997. The main difficulty is that, in order to solve the problem, the square-roots should be computed to a high accuracy, which may require a large number of bits. The problem is mentioned in the Open Problems Garden.{{Cite web |title=Complexity of square-root sum {{!}} Open Problem Garden |url=http://garden.irmacs.sfu.ca/?q=op/complexity_of_square_root_sum |access-date=2024-01-01 |website=garden.irmacs.sfu.ca}}

Blomer{{Cite web |title=CSDL {{!}} IEEE Computer Society |url=https://www.computer.org/csdl/proceedings-article/focs/1991/0185434/12OmNAKuoSa |access-date=2024-01-01 |website=www.computer.org}} presents a polynomial-time Monte Carlo algorithm for deciding whether a sum of square roots equals zero. The algorithm applies more generally, to any sum of radicals.

Allender, Burgisser, Pedersen and Miltersen{{Cite journal |last1=Allender |first1=Eric |last2=Bürgisser |first2=Peter |last3=Kjeldgaard-Pedersen |first3=Johan |last4=Miltersen |first4=Peter Bro |date=January 2009 |title=On the Complexity of Numerical Analysis |url=http://epubs.siam.org/doi/10.1137/070697926 |journal=SIAM Journal on Computing |language=en |volume=38 |issue=5 |pages=1987–2006 |doi=10.1137/070697926 |issn=0097-5397}} prove that SRS lies in the counting hierarchy (which is contained in PSPACE).

One way to solve SRS is to prove a lower bound on the absolute difference $\backslash left|t\; -\; \backslash sum\_\{i=1\}^k\; \backslash sqrt\{a\_i\}\; \backslash right|$ or $\backslash left|\backslash sum\_\{i=1\}^k\; \backslash sqrt\{a\_i\}\; -\; \backslash sum\_\{i=1\}^k\; \backslash sqrt\{b\_i\}\backslash right|$. Such lower bound is called a "separation bound" since it separates between the difference and 0. For example, if the absolute difference is at least 2^−d, it means that we can round all numbers to d bits of accuracy, and solve SRS in time polynomial in d.

This leads to the mathematical problem of proving bounds on this difference. Define r(n,k) as the smallest positive value of the difference $\backslash sum\_\{i=1\}^k\; \backslash sqrt\{a\_i\}\; -\; \backslash sum\_\{i=1\}^k\; \backslash sqrt\{b\_i\}$, where a_i and b_i are integers between 1 and n; define R(n,k) is defined as -log r(n,k), which is the number of accuracy digits required to solve SRS. Computing r(n,k) is open problem 33 in the open problem project.{{Cite web |last=Demaine |first=Erik D. |last2=Mitchell |first2=Joseph |last3=O'Rourke |first3=Joseph |title=TOPP: Problem 33: Sum of Square Roots |url=https://topp.openproblem.net/p33 |access-date=2024-01-01 |website=topp.openproblem.net}}

In particular, it is interesting whether r(n,k) is in O(poly(k,log(n)). A positive answer would imply that SRS can be solved in polynomial time in the Turing Machine model. Some currently known bounds are:

• Qian and Wang{{Cite journal |last1=Qian |first1=Jianbo |last2=Wang |first2=Cao An |date=2006-12-16 |title=How much precision is needed to compare two sums of square roots of integers? |url=https://www.sciencedirect.com/science/article/pii/S0020019006001396 |journal=Information Processing Letters |volume=100 |issue=5 |pages=194–198 |doi=10.1016/j.ipl.2006.05.002 |issn=0020-0190}} prove by an explicit construction that, for any k and n, $r(n,k)\backslash in\; O(n^\{-2k+3/2\})$, so $R(n,k)\backslash geq\; (2k-3/2)\backslash cdot\; \backslash log\{n\}$. This number is optimal for k=2, and also for a wide range of integers.
• Burnikel, Fleischer, Mehlhorn and Schirra{{Cite journal |last1=Burnikel |first1=C. |last2=Fleischer |first2=R. |last3=Mehlhorn |first3=K. |last4=Schirra |first4=S. |date=2000-05-01 |title=A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Radicals |url=https://doi.org/10.1007/s004530010005 |journal=Algorithmica |language=en |volume=27 |issue=1 |pages=87–99 |doi=10.1007/s004530010005 |s2cid=34502818 |issn=1432-0541}} proved an upper bound on the number of digits: $R(n,k)\backslash in\; O(2^\{2\; k\}\backslash cdot\; \backslash log\{n\})$.
• Cheng, Meng, Sun and Chen{{Cite journal |last1=Cheng |first1=Qi |last2=Meng |first2=Xianmeng |last3=Sun |first3=Celi |last4=Chen |first4=Jiazhe |date=April 2010 |title=Bounding the sum of square roots via lattice reduction |url=https://www.ams.org/mcom/2010-79-270/S0025-5718-09-02304-7/ |journal=Mathematics of Computation |language=en |volume=79 |issue=270 |pages=1109–1122 |doi=10.1090/S0025-5718-09-02304-7 |issn=0025-5718|doi-access=free |arxiv=0905.4487 |bibcode=2010MaCom..79.1109C }} showed that $R(n,k)\backslash in\; 2^\{O(n/\backslash log\{n\})\}\backslash cdot\; \backslash log\{n\}$.
• Cheng and Li{{Cite journal |last1=Cheng |first1=Qi |last2=Li |first2=Yu-Hsin |date=2011-09-09 |title=On the minimum gap between sums of square roots of small integers |journal=Theoretical Computer Science |volume=412 |issue=39 |pages=5458–5465 |doi=10.1016/j.tcs.2011.06.014 |issn=0304-3975|doi-access=free }} showed that $R(n,k)\backslash in\; 2^\{O(n/\backslash log\{n\})\}$. This implies an that SRS can be solved in time $2^\{o(k)\}\; \backslash cdot\; (\backslash log\{n\})^\{O(1)\}$, as long as n is in o(k log k). They also present an algorithm to compute r(n,k) in time $n^\{k+o(k)\}$.
• Eisenbrand, Haeberle and Singer{{Cite arXiv |eprint=2312.02057 |last1=Eisenbrand |first1=Friedrich |last2=Haeberle |first2=Matthieu |last3=Singer |first3=Neta |title=An improved bound on sums of square roots via the subspace theorem |date=2023 |class=cs.CG }} prove that $r(n,k)\backslash geq\; \backslash gamma\backslash cdot\; n^\{-2n\}$, where gamma is a constant that depends on the inputs a₁,...,a_n, and steps from the Subspace theorem. This improves the previous bound $r(n,k)\backslash geq\; \backslash left(\; n\backslash cdot\; \backslash max\_i\; (\backslash sqrt\{a\_i\})\backslash right)^\{-2^n\}$.

SRS is important in computational geometry, as Euclidean distances are given by square-roots, and many geometric problems (e.g. Minimum spanning tree in the plane and Euclidean traveling salesman problem) require to compute sums of distances.

Etessami and Yannakakis{{Cite journal |last1=Etessami |first1=Kousha |last2=Yannakakis |first2=Mihalis |date=2008-11-11 |title=Recursive Concurrent Stochastic Games |url=https://lmcs.episciences.org/1196 |journal=Logical Methods in Computer Science |volume= 4| issue = 4 |doi=10.2168/LMCS-4(4:7)2008 |issn=1860-5974|doi-access=free |arxiv=0810.3581 }} show a reduction from SRS to the problem of termination of recursive concurrent stochastic games.

SRS also has a theoretic importance, as it is a simple special case of a semidefinite programming feasibility problem. Consider the matrix $\backslash left($

\begin{matrix}

1 & x

\\

x & a

\end{matrix}

\right)

. This matrix is positive semidefinite iff $a\; -\; x^2\; \backslash geq\; 0$, iff $|x|\backslash leq\; \backslash sqrt\{a\}$. Therefore, to solve SRS, we can construct a feasibility problem with n constraints of the form $\backslash left($

\begin{matrix}

1 & x_i

\\

x_i & a_i

\end{matrix}

\right) \succeq 0

, and additional linear constraints $x\_i\backslash geq\; 0,\; \backslash sum\_\{i=1\}^n\; x\_i\; \backslash geq\; k$. The resulting SDP is feasible if and only if SRS is feasible. As the runtime complexity of SRS in the Turing machine model is open, the same is true for SDP feasibility (as of 1997).

Kayal and Saha{{Cite journal |last1=Kayal |first1=Neeraj |last2=Saha |first2=Chandan |date=2012-11-01 |title=On the Sum of Square Roots of Polynomials and Related Problems |url=https://doi.org/10.1145/2382559.2382560 |journal=ACM Transactions on Computation Theory |volume=4 |issue=4 |pages=9:1–9:15 |doi=10.1145/2382559.2382560 |s2cid=7225729 |issn=1942-3454}} extend the problem from integers to polynomials. Their results imply a solution to SRS for a special class of integers.

{{Reflist}}

Category:Numerical analysis

Category:Computational problems