Combinatorial properties of certain Toeplitz matrices

Abstract

In additive combinatorics, a family of finite sets $A_i$ is said to have bounded doubling if there exists a uniform constant $K$ such that
$|A_i + A_i|< K|A_i|$ for all i. In this paper, we study such families in the context of certain symmetric Toeplitz matrices over a field F. In particular, we show that if each matrix has bandwidth b and diagonal entries chosen from a finite set $S \subset F$, then the resulting family admits a doubling constant that depends only on b and the additive properties of $S$, but is independent of the matrix dimension. Also, if the diagonals lie in the image of a fixed-dimensional linear map $L: F^m \to F^{b+1}$, then the doubling constant depends on m rather than b. We include examples to illustrate how one-dimensional constraints on S lead to especially small doubling constants.