Poisson Summation Sampling and Lattice Duality

Let $n\ge 1$. A full-rank lattice in ${\mathbb{R}}^n$ is a subgroup $\mathrm{\Lambda }\subseteq {\mathbb{R}}^n$ of the form

$\mathrm{\Lambda }=A{\mathbb{Z}}^n=\{{\sum }_{i=1}^n{k}_i{a}_i:k=(k_1,\dots ,k_n)\in {\mathbb{Z}}^n\},$

where $A$ is an invertible real $n\times n$ matrix with columns $a_1,\dots ,a_n$; here $Ak$ is the matrix product (Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes) and the column matrix $Ak$ is identified with the vector it represents. A full-rank lattice is exactly a full Euclidean lattice in the sense of Full Euclidean lattice and covolume: invertibility of $A$ makes its columns linearly independent over $\mathbb{R}$ (A finite square real matrix is invertible if and only if its determinant is nonzero), so they form a real basis of ${\mathbb{R}}^n$ and $\mathrm{\Lambda }$ is their $\mathbb{Z}$-span, and conversely the basis matrix of every full Euclidean lattice is invertible. The covolume of $\mathrm{\Lambda }$ is

$\mathrm{covol}(\mathrm{\Lambda }):=\mathrm{\mid }\det A\mathrm{\mid }>0,$

with the determinant and the real absolute value of For $n\ge 1$, the determinant over a commutative ring by the Leibniz formula, and $\mathrm{\mid }\det A\mathrm{\mid }$ for a real matrix, and the dual lattice is

${\mathrm{\Lambda }}^{\ast }:=\{\xi \in {\mathbb{R}}^n:\xi \cdot \lambda \in \mathbb{Z}\text{ for every }\lambda \in \mathrm{\Lambda }\}=A^{-T}{\mathbb{Z}}^n,$

where $\xi \cdot \lambda$ is the Euclidean inner product (The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$), $A^{-T}:=(A^{-1}{)}^T=(A^T{)}^{-1}$ is formed with the transpose of The transpose $A^{\mathsf{T}}$ of a matrix and the inverse of Invertible matrices and the general linear group ${\mathrm{GL}}_n(F)$ (Transpose is linear and involutive, and $(AB{)}^{\mathsf{T}}=B^{\mathsf{T}}{A}^{\mathsf{T}}$ for the identity $(A^{-1}{)}^T=(A^T{)}^{-1}$, and A finite square real matrix is invertible if and only if its determinant is nonzero for the existence of $A^{-1}$).

Well-definedness: the presentation does not matter. Suppose $B{\mathbb{Z}}^n=A{\mathbb{Z}}^n$ for a second invertible real matrix $B$. Then $U:=A^{-1}B$ has integer entries: each column $b_j$ of $B$ lies in $A{\mathbb{Z}}^n$, say $b_j=A{u}_j$ with $u_j\in {\mathbb{Z}}^n$, so $U=(u_1\cdots u_n)\in M_n(\mathbb{Z})$ (Finite rectangular matrices over a commutative ring, their entries, rows and columns, Entrywise ring-matrix operations, rectangular matrix products, identity matrices and transpose). Exchanging the roles of $A$ and $B$ shows likewise that $U^{-1}=B^{-1}A$ has integer entries. Hence $\det U\in \mathbb{Z}$ and $\det U^{-1}\in \mathbb{Z}$, and $\det U\cdot \det U^{-1}=\det (U{U}^{-1})=\det I_n=1$ (For same-sized finite square matrices over a commutative ring, $\det (AB)=\det (A)\det (B)$, Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes); by $(\mathbb{Z},\cdot ,1)$ is a commutative monoid whose group of units is $\{1,-1\}$; equivalently $u\mid 1$ holds exactly for $u=1$ and $u=-1$ the only way two integers can multiply to $1$ is $\det U=\det U^{-1}=\pm 1$ (with the same sign). Consequently $\mathrm{\mid }\det B\mathrm{\mid }=\mathrm{\mid }\det A\mathrm{\mid }\mathrm{\mid }\det U\mathrm{\mid }=\mathrm{\mid }\det A\mathrm{\mid }$, so the covolume is independent of the presentation. For the dual, $B^{-T}{\mathbb{Z}}^n=A^{-T}{U}^{-T}{\mathbb{Z}}^n$ by Transpose is linear and involutive, and $(AB{)}^{\mathsf{T}}=B^{\mathsf{T}}{A}^{\mathsf{T}}$, and $U^{-T}=(U^{-1}{)}^T$ as well as $U^T$ have integer entries (The transpose $A^{\mathsf{T}}$ of a matrix); matrices with integer entries send ${\mathbb{Z}}^n$ into ${\mathbb{Z}}^n$ under matrix multiplication (Entrywise ring-matrix operations, rectangular matrix products, identity matrices and transpose), so $U^{-T}{\mathbb{Z}}^n\subseteq {\mathbb{Z}}^n$ and, applying the same statement to the integer matrix $U^T=(U^{-T}{)}^{-1}$, also ${\mathbb{Z}}^n\subseteq U^{-T}{\mathbb{Z}}^n$. Hence $U^{-T}{\mathbb{Z}}^n={\mathbb{Z}}^n$ and $B^{-T}{\mathbb{Z}}^n=A^{-T}{\mathbb{Z}}^n$.

The dual in closed form. For $\xi =A^{-T}m$ with $m\in {\mathbb{Z}}^n$ and $\lambda =Ak$ with $k\in {\mathbb{Z}}^n$ one has $\xi \cdot \lambda =(A^{-T}m)\cdot (Ak)=m\cdot k\in \mathbb{Z}$, because $(A^{-T}m)\cdot (Ak)=m\cdot (A^{-1}Ak)$; so $A^{-T}{\mathbb{Z}}^n$ is contained in the defining set. Conversely, if $\xi \cdot \lambda \in \mathbb{Z}$ for every $\lambda \in \mathrm{\Lambda }$, then testing $\lambda =a_j=A{e}_j$ gives $\xi \cdot a_j=(A^T\xi {)}_j\in \mathbb{Z}$ for every $j$, so $A^T\xi \in {\mathbb{Z}}^n$ and $\xi =A^{-T}(A^T\xi )\in A^{-T}{\mathbb{Z}}^n$. This also shows that the second description of ${\mathrm{\Lambda }}^{\ast }$ depends only on $\mathrm{\Lambda }$. The dual is itself a full-rank lattice: $A^{-T}$ is invertible, its columns being a real basis, and $\mathrm{covol}({\mathrm{\Lambda }}^{\ast })=\mathrm{\mid }\det A^{-T}\mathrm{\mid }=\mathrm{\mid }\det A^{-1}\mathrm{\mid }=\mathrm{\mid }\det A{\mathrm{\mid }}^{-1}=\mathrm{covol}(\mathrm{\Lambda }{)}^{-1}$, using $\det A^{-T}=\det A^{-1}$ (For every square matrix over a commutative ring, $\det (A^{\mathsf{T}})=\det (A)$) and $\det A^{-1}=(\det A{)}^{-1}$ (If $A$ is invertible over a commutative ring, then $\det (A^{-1})=\det (A{)}^{-1}$). For $\mathrm{\Lambda }={\mathbb{Z}}^n$, that is $A=I_n$, one gets ${\mathrm{\Lambda }}^{\ast }={\mathbb{Z}}^n$ because $I_n^{-T}=I_n$ (Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes).

Characters. For ${\lambda }^{\ast }\in {\mathbb{R}}^n$ put ${\chi }_{{\lambda }^{\ast }}(x):=e^{2\pi i{\lambda }^{\ast }\cdot x}$, with the complex exponential of The complex exponential by its power series. Then ${\chi }_{{\lambda }^{\ast }}(x+\lambda )={\chi }_{{\lambda }^{\ast }}(x)e^{2\pi i{\lambda }^{\ast }\cdot \lambda }$ for every $\lambda \in \mathrm{\Lambda }$, so ${\chi }_{{\lambda }^{\ast }}$ is $\mathrm{\Lambda }$-periodic exactly when $e^{2\pi i{\lambda }^{\ast }\cdot \lambda }=1$ for every $\lambda \in \mathrm{\Lambda }$, that is ($\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$) exactly when ${\lambda }^{\ast }\cdot \lambda \in \mathbb{Z}$ for every $\lambda \in \mathrm{\Lambda }$ --- precisely the condition ${\lambda }^{\ast }\in {\mathrm{\Lambda }}^{\ast }$. Thus ${\lambda }^{\ast }\mapsto {\chi }_{{\lambda }^{\ast }}$ is a bijection from ${\mathrm{\Lambda }}^{\ast }$ onto the set of exponential characters ${\chi }_{{\lambda }^{\ast }}$ of the torus ${\mathbb{R}}^n\mathrm{/}\mathrm{\Lambda }$, and it is a group isomorphism for pointwise multiplication because ${\chi }_{{\lambda }^{\ast }+{\eta }^{\ast }}={\chi }_{{\lambda }^{\ast }}{\chi }_{{\eta }^{\ast }}$; this is the lattice case of the characters of The Pontryagin dual with the compact-open topology. The assertion is about the characters of the displayed exponential form; no claim is made here that every continuous character of ${\mathbb{R}}^n\mathrm{/}\mathrm{\Lambda }$ is of that form.

No choice principle is used anywhere in this item.

The normalised sinc function is $\mathrm{sinc}:\mathbb{R}\to \mathbb{C}$, given for $t\mathrm{\ne }0$ by the quotient and at the origin by continuity,

$\mathrm{sinc}(t):=\frac{\sin (\pi t)}{\pi t}(t\mathrm{\ne }0),\mathrm{sinc}(0):=1.$

The values displayed show that $\mathrm{sinc}$ is real-valued: the sine and the identity of The derivatives of sine and cosine are cosine and minus sine are real functions there, and the quotient of real numbers is real.

Well-definedness. At every $t\mathrm{\ne }0$ the numerator and denominator are defined and $\pi t\mathrm{\ne }0$, so the quotient of real numbers is defined (The complex exponential by its power series is needed only to fix the ambient convention in which $\pi$, $\sin$ and the real numbers are embedded in $\mathbb{C}$). The value at $t=0$ is assigned separately; it is the correct limit, ${\lim }_{t\to 0}\mathrm{sinc}(t)=1$, because $\pi t\to 0$ as $t\to 0$ and ${\lim }_{u\to 0}\sin (u)\mathrm{/}u=1$ (The limit of sin x divided by x at zero is one), the substitution $u=\pi t$ being the case of Composition of limits holds under either hypothesis: $f$ is defined at $L$ with value $M$, or $g$ avoids $L$ on a punctured neighbourhood of $c$ in which the inner function $\pi t$ does not take the value $0$ away from $t=0$; with this value $\mathrm{sinc}$ is continuous at $0$, and it is continuous at every $t\mathrm{\ne }0$ because $t\mapsto \sin (\pi t)$ is a composite of continuous functions (The derivatives of sine and cosine are cosine and minus sine gives differentiability, hence continuity, and A composite of continuous functions is continuous, with no side hypothesis of the kind the composition of limits needs) and $t\mapsto 1\mathrm{/}(\pi t)$ is a quotient with nonvanishing denominator, so Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function gives the quotient.

Symmetry and integer values. Sine is odd (Parity and the Pythagorean identity for sine and cosine), so for $t\mathrm{\ne }0$, $\mathrm{sinc}(-t)=\sin (-\pi t)\mathrm{/}(-\pi t)=\sin (\pi t)\mathrm{/}(\pi t)=\mathrm{sinc}(t)$, and the same identity holds at $t=0$; thus $\mathrm{sinc}$ is even. For an integer $k\mathrm{\ne }0$, $\sin (\pi k)=0$ by the zero set of sine (The zero sets of sine and cosine and the least positive common period 2 pi), so $\mathrm{sinc}(k)=0$, while $\mathrm{sinc}(0)=1$. Hence $\mathrm{sinc}(k)=0$ for every nonzero integer $k$, and the kernel vanishes at every sampling point except its own.

Bounds. For every real $t$, $\mathrm{\mid }\mathrm{sinc}(t)\mathrm{\mid }\le 1$: at $t=0$ this is an equality, and for $t\mathrm{\ne }0$ the one-Lipschitz estimate $\mathrm{\mid }\sin u-\sin 0\mathrm{\mid }\le \mathrm{\mid }u\mathrm{\mid }$ (Sine and cosine are $1$-Lipschitz on $\mathbb{R}$) with $u=\pi t$ and $\sin 0=0$ (The derivatives of sine and cosine are cosine and minus sine) gives $\mathrm{\mid }\sin (\pi t)\mathrm{\mid }\le \pi \mathrm{\mid }t\mathrm{\mid }$, which proves the bound after division by $\mathrm{\mid }\pi t\mathrm{\mid }$. For every $t\mathrm{\ne }0$ one also has $\mathrm{\mid }\mathrm{sinc}(t)\mathrm{\mid }\le 1\mathrm{/}(\pi \mathrm{\mid }t\mathrm{\mid })$, since $\mathrm{\mid }\sin (\pi t)\mathrm{\mid }\le 1$ (Parity and the Pythagorean identity for sine and cosine) and division by $\mathrm{\mid }\pi t\mathrm{\mid }$ gives this tail estimate.

This is the normalisation used by the sampling theorem on this page: the reconstruction series is $f(x)={\sum }_{k}f(hk)\mathrm{sinc}(x\mathrm{/}h-k)$, and the kernel vanishes at every sampling point except its own, as proved above. The Fourier identity $\mathrm{sinc}(t)={\int }_{-1\mathrm{/}2}^{1\mathrm{/}2}{e}^{-2\pi it\xi }d\xi$ is not asserted by this definition; it is proved directly where the sampling theorem consumes it, from the complex primitive of the exponential. The complex exponential convention $e^{2\pi it}=\exp (2\pi it)$ underlying that display is $\exp (x+iy)=e^x(\cos y+i\sin y)$, $\mathrm{\mid }\exp (x+iy)\mathrm{\mid }=e^x$, and $e^{i\pi }+1=0$.

No choice principle is used in this item.

Let $A$ be an invertible real $n\times n$ matrix and put $(A^{\ast }f)(y):=f(Ay)$. If $f\in \mathcal{S}({\mathbb{R}}^n)$ then $A^{\ast }f\in \mathcal{S}({\mathbb{R}}^n)$; more precisely, for every pair of multi-indices $\alpha ,\beta$ there are a constant $C_{\alpha \beta }$ and a finite set of Schwartz seminorms of $f$ with $p_{\alpha \beta }(A^{\ast }f)\le C_{\alpha \beta }{\max }_{\mathrm{\mid }\delta \mathrm{\mid }\le \mathrm{\mid }\alpha \mathrm{\mid },\mathrm{\mid }\gamma \mathrm{\mid }\le \mathrm{\mid }\beta \mathrm{\mid }}{p}_{\delta \gamma }(f)\mathrm{.}$ Hence $f\mapsto f\circ A$ is a continuous linear endomorphism of $\mathcal{S}({\mathbb{R}}^n)$ with continuous inverse $f\mapsto f\circ A^{-1}$. No choice principle is used.

Assume Countable Choice (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)). Let $A$ be an invertible real $n\times n$ matrix, $\mathrm{\Lambda }=A{\mathbb{Z}}^n$ a full-rank lattice, and $F:=A((0,1{]}^n)=\{{\sum }_{i=1}^n{t}_i{a}_i:0<t_i\le 1\},$ where $a_1,\dots ,a_n$ are the columns of $A$, the fundamental parallelotope of $\mathrm{\Lambda }$. Then every $x\in {\mathbb{R}}^n$ has a unique representation $x=\lambda +p$ with $\lambda \in \mathrm{\Lambda }$ and $p\in F$; consequently the translates $F+\lambda$ ($\lambda \in \mathrm{\Lambda }$) are pairwise disjoint and cover ${\mathbb{R}}^n$. Moreover $F$ is Lebesgue measurable and ${\lambda }_n(F)=\mathrm{\mid }\det A\mathrm{\mid }=\mathrm{covol}(\mathrm{\Lambda })$. Countable Choice is inherited by the box-measure and linear change-of-variables suppliers in the volume computation; the unique representation is choice-free.

Assume Countable Choice (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)). Let $A$, $\mathrm{\Lambda }=A{\mathbb{Z}}^n$ and $F$ be as in Fundamental parallelotopes of a lattice tile Euclidean space with covolume volume, and let ${\lambda }^{\ast },{\eta }^{\ast }\in {\mathrm{\Lambda }}^{\ast }$. Then $\frac{1}{\mathrm{covol}(\mathrm{\Lambda })}{\int }_F{e}^{2\pi i({\lambda }^{\ast }-{\eta }^{\ast })\cdot x}dx=\{\begin{array}{ll}1,& {\lambda }^{\ast }={\eta }^{\ast },\\ 0,& {\lambda }^{\ast }\mathrm{\ne }{\eta }^{\ast }\mathrm{.}\end{array}$

Assume Countable Choice (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)). Let $f\in \mathcal{S}({\mathbb{R}}^n)$ and let $\mathrm{\Lambda }$ be a full-rank lattice. Then the periodisation $P_{\mathrm{\Lambda }}f(x):={\sum }_{\lambda \in \mathrm{\Lambda }}f(x+\lambda )$ converges absolutely for every $x\in {\mathbb{R}}^n$, locally uniformly together with the derivative series ${\sum }_{\lambda \in \mathrm{\Lambda }}{\mathrm{\partial }}^{\beta }f(x+\lambda )$ for every multi-index $\beta$; the sum $P_{\mathrm{\Lambda }}f$ is smooth and $\mathrm{\Lambda }$-periodic with ${\mathrm{\partial }}^{\beta }(P_{\mathrm{\Lambda }}f)={\sum }_{\lambda \in \mathrm{\Lambda }}{\mathrm{\partial }}^{\beta }f(x+\lambda )$.