Computing theta function
share
Let f: R^n ⟶ R be a positive definite quadratic form and let y ∈ R^n be a point. We present a fully polynomial randomized approximation scheme (FPRAS) for computing ∑_x ∈ Z^n e^-f(x), provided the eigenvalues of f lie in the interval roughly between s and e^s and for computing ∑_x ∈ Z^n e^-f(x-y), provided the eigenvalues of f lie in the interval roughly between e^-s and s^-1 for some s ≥ 3. To compute the first sum, we represent it as the integral of an explicit log-concave function on R^n, and to compute the second sum, we use the reciprocity relation for theta functions. Choosing s ∼log n, we apply the results to test the existence of sufficiently many short integer vectors in a given subspace L ⊂ R^n or in the vicinity of L.
READ FULL TEXT