On the image of convolutions along an arithmetic progression

Abstract

We consider the question of determining the structure of the set of all $d$-dimensional vectors of the form $N^{-1}(1_A\ast 1_{-A}(x_1),...,1_A\ast 1_{-A}(x_d))$ for $A\subseteq \{1,...,N\}$, and also the set of all $(2N+1{)}^{-1}(1_B\ast 1_B(x_1),...,1_B\ast 1_B(x_d))$, for $B\subseteq \{-N,-N+1,...,0,1,...,N\}$, where $x_1,...,x_d$ are fixed positive integers (we let $N\to \infty$). Using an elementary method related to the Birkhoff-von Neumann theorem on decompositions of doubly-stochastic matrices we show that both the above two sets of vectors roughly form polytopes; and of particular interest is the question of bounding the number of corner vertices, as well as understanding their structure.