论文标题
计算theta功能
Computing the theta function
论文作者
论文摘要
令$ f：{\ bbb r}^n \ longrightArrow {\ bbb r} $为积极的确定二次形式，让$ y \ in {\ bbb r}^n $是一个点。我们提出了一个完全多功能的随机近似方案（FPRA），用于计算$ \ sum_ {x \ in {\ bbb z}^n} e^{ - f（x）} $，提供$ f $的特征在$ s $和$ s $ and $ e^{s $ sum_ sum_ sum bb in $ f $的特征中z}^n} e^{ - f（x-y）} $，向$ e^{ - s} $和$ s^{ - 1} $之间的间隔大约在间隔中撒在$ e^geq 3 $之间。要计算第一个总和，我们将其表示为在$ {\ bbb r}^n $上显式log-conconcove函数的组成部分，并且要计算第二个总和，我们将互惠关系用于theta函数。然后，我们应用结果来测试给定子空间$ l \ subset {\ bbb r}^n $中许多短整数向量的存在，以估算从给定点到晶格的距离，并从离散高斯分布中进行随机晶格点。
Let $f: {\Bbb R}^n \longrightarrow {\Bbb R}$ be a positive definite quadratic form and let $y \in {\Bbb R}^n$ be a point. We present a fully polynomial randomized approximation scheme (FPRAS) for computing $\sum_{x \in {\Bbb Z}^n} e^{-f(x)}$, provided the eigenvalues of $f$ lie in the interval roughly between $s$ and $e^{s}$ and for computing $\sum_{x \in {\Bbb 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 \geq 3$. To compute the first sum, we represent it as the integral of an explicit log-concave function on ${\Bbb 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 \subset {\Bbb 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.
