AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The sum of square roots problem over integers is the task of lower bounding the absolute value of a nonzero difference S = C - D, where C and D are sums of n square roots of integers. Assume that every integer under the square root has value at most N. A fundamental open question in numerical analysis and computational geometry is whether |S| > 1/2^poly(n,log N). We study a formulation of this problem over polynomials: Given an expression S = sum_{i=1}^{n}{c_i.sqrt(f_i(x))}, where c_i's belong to a field of characteristic 0 and f_i's are univariate polynomials with degree bounded by d (and f_i(0) \neq 0 for all i), is it true that the minimum exponent of x which has a nonzero coefficient in the power series S is bounded by a fixed polynomial in n and d, unless S=0? We answer this question affirmatively. Further, we show that this result over polynomials can be used to settle (positively) the sum of square roots problem for a special class of integers:- Suppose each integer under the square root is of the form, X^d + b_1.X^{d-1} + ... + b_d, where X is a positive real number and b_i's are integers. Let B = max{|b_i|}. We show, if X > (B+1)^{dn^2}, then a nonzero S is lower bounded as, |S| > 1/X^{dn^2}. (Joint work with Neeraj Kayal)

Chandan Saha

--email hidden

passcode not visible

logged in users only