Computing the theta function

arXiv2208.05405MaRDI QIDQ6407516FDOQ6407516

Publication date: 10 August 2022

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.

Mathematics Subject Classification ID

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)

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)