MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 , 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}$.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.