Computing the theta function

Publication date 10 August 2022

General topics of discrete mathematics in relation to computer science (68R01) Approximation algorithms (68W25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Abstract: Let

f : {B b b R}^{n} l o n g r i g h t a r r o w B b b R

be a positive definite quadratic form and let

y i n {B b b R}^{n}

be a point. We present a fully polynomial randomized approximation scheme (FPRAS) for computing

s u m_{x i n {B b b Z}^{n}} e^{- f (x)}

, provided the eigenvalues of

f

lie in the interval roughly between

s

and

e^{s}

and for computing

s u m_{x i n {B b b 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 g e q 3

. To compute the first sum, we represent it as the integral of an explicit log-concave function on

{B b b R}^{n}

, and to compute the second sum, we use the reciprocity relation for theta functions. We then apply our results to test the existence of many short integer vectors in a given subspace

L s u b s e t {B b b R}^{n}

, to estimate the distance from a given point to a lattice, and to sample a random lattice point from the discrete Gaussian distribution.

This page was built for publication: Computing the theta function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407516)