Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.