Failure of Orthogonality of Rounded Fourier Bases

Abstract

The purpose of this note is to prove estimates for $$ \left| \sum_{k=1}^{n} \mbox{sign} \left( \cos \left( \frac{2πa}{n} k \right) \right) \mbox{sign} \left( \cos \left( \frac{2πb}{n} k \right) \right)\right|,$$ when $n$ is prime and $a,b\in \mathbb{N}$. We show that the expression can only be large if $a^{-1}b\in {\mathbb{F}}_n$ (or a small multiple thereof) is close to $1$. This explains some of the surprising line patterns in $A^{T}A$ when $A\in {\mathbb{R}}^{n\times n}$ is the signed discrete cosine transform. Similar results seem to exist at a great level of generality.