Campus Event Calendar

Event Entry

New for: D3

What and Who

The Sum of Square Roots Problem over Polynomials and a Special Class of Integers

Chandan Saha
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI  
AG Audience

Date, Time and Location

Friday, 29 October 2010
30 Minutes
E1 4


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

Chandan Saha, 10/22/2010 12:43
Chandan Saha, 10/22/2010 12:40 -- Created document.