#

### Volume 2016

#### Article 7

Published by the Department of Computer Science, The University of Chicago.

#### A Note on Discrete Gaussian Combinations of Lattice Vectors

Divesh Aggarwal

Department of Computer and Communication Sciences,

EFPL, Lausanne, Switzerland;

`divesh.aggarwal AT epfl DOT ch `
Oded Regev

Courant Institute of Mathematical Sciences,

New York University, New York, USA;

`regev AT cims DOT nyu DOT edu`

*June 8, 2016*
#### Abstract

We prove a local central limit theorem for the sum of one-dimensional discrete
Gaussians in $n$-dimensional space. In more detail, we analyze the distribution of
$\sum_{i=1}^m v_i \mathbf{x}_i$ where $\mathbf{x}_1,\ldots,\mathbf{x}_m$
are fixed vectors from some
lattice $\mathcal{L} \subset \mathbb{R}^n$ and $v_1,\ldots,v_m$ are chosen
independently from a
discrete Gaussian distribution over $\mathbb{Z}$. We show that under a
natural constraint
on $\mathbf{x}_1,\ldots,\mathbf{x}_m$, if the $v_i$ are chosen from a
wide enough Gaussian, the
sum is statistically close to a discrete Gaussian over $\mathcal{L}$.
We also analyze the
case of $\mathbf{x}_1,\ldots,\mathbf{x}_m$ that are themselves chosen from a
discrete Gaussian distribution (and fixed).
Our results simplify and qualitatively improve upon a recent result by Agrawal,
Gentry, Halevi, and Sahai.

- The article:
**PDF** (233 KB)
- Source material: ZIP (156 KB)
**BibTeX** entry for this
article (288 bytes)

Submitted October 1st, 2014, revised April 19, 2016, published June 8, 2016.

Volume 2016, Article 6
Article 8

Volume 2016
Published articles