In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in http://arxiv.org/abs/0911.1388 , the following polyhedron arises:
The variables $x_i$ are indexed by $i \in M_n$. The inequalities are
$ x_i \ge 0$ for all $i \in M_n$.
$\sum_{i \in M_n} \chi(i) x_i \ge 0$ for all additive characters $\chi: M_n \rightarrow \pm 1$.
This comes up when $f_A: M_n \rightarrow \{0,1\}$ is the characteristic function of a subset $A$ of $M_n$ (in this case the putative complement $A$ which is the set of elements for which would translate $V$ to create a partition of $M_n$). Then $x_i =f_A \ast f_A(i)$ gives an element of the above polyhedron. This polyhedron is homogeneous, so it is convenient to add the additional constraints to make it a polytope:
$x_0 = a$ for some $a >0 $ and $\sum_{i \in M_n} x_i = b$ for some $b>0$.
In the case that the $x_i$ come from a function like the $f_A$ above (associated with a subset $A$) we have $a = |A|$ and $b = |A|^2$. I'm wondering if there's a nice description of this polytope -- for example a description of its vertices/faces, etc. Has anybody looked at this before?
There are a lot of symmetries of this polytope. The group $\text{GL}_n(\mathbb{F}_2)$ operates it via $x_i \rightarrow x_{i \cdot g}$.
