Is this "subgroup packing" polytope integral? Let $\Gamma$ be a finite abelian group, and let $P$ be the polytope in $\mathbb{R}^\Gamma$ defined to be the points $x$ satisfying the following inequalities:

$$\begin{array}{cl}
\sum_{g\in G} x_g \le |G| &amp; \forall G \le \Gamma \\
x_g \ge 0 &amp; \forall g \in \Gamma
\end{array}$$

where $G \le \Gamma$ means $G$ is a subgroup of $\Gamma$. Is $P$ integral? If so, can we characterize its vertices?



My question originally arose with $\Gamma = \mathbb{F}_2^n$, where some small examples ($n = 2,3$) suggest that the answer is "yes" and "maybe, but it's not simple". I also tried the cyclic group on 9 and 10 elements, as well as $\mathbb{F}_3^2$, where again the polytope is integral. The polytope is not integral when $\Gamma$ is any of $S_3$, $D_4$, and $D_5$, so abelianness is apparently essential.

I should mention that if you write the first set of equations as $Ax \ge b$, then $A$ is not necessarily totally unimodular (which would imply the polytope is integral). When $\Gamma = \mathbb{F}_2^3$, you can choose three linearly independent $g$ and take the three $G$'s spanned by each pair of the selected elements $g$. The resulting submatrix is
$$\begin{bmatrix}0&amp;1&amp;1\\1&amp;0&amp;1\\1&amp;1&amp;0\end{bmatrix}$$
up to permutation, and so has determinant $\pm 2$.

It's easy (if tedious) to characterize the vertices for prime-order groups and observe that they're integral. I'm pretty sure this can be extended to cyclic groups with order a prime-power. I'm not sure what happens when taking products.

This system is very reminiscient of those defining polymatroids, but rather than a submodular set function, the constraints are a "subgroup function" that I suspect is 'submodular' once that's been defined the right way. Still, the techniques for showing certain polymatroids are integral might work here, too, but I don't see how.

Also, Fourier analysis may be relevant: when $\Gamma = \mathbb{F}_2^n$, it seems that the vertices maximizing $\sum_g x_g$ are exactly the point with $x_g = 1$ for all $g$, as well as those with $x_g = 1 - \chi_S(g)$ where $\chi_S$ is the $S$-th Fourier character (following standard notation from analysis of boolean functions), and $S$ is nonempty. (When $S$ is empty, the corresponding point is $x_g = 0$, which is also a vertex.)
Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups. 

On the positive side. 

Theorem:
For cyclic groups with order $p^kq$, where $p$ and $q$ are primes and $k\in \mathbb{N}$, the incidence matrix of elements and subgroups is totally unimodular.

This is because the family of subgroups is a union of two laminar families.

Hence, this shows the smallest counterexample for cyclic groups must have order at least $2\times 3\times 5 =30$. This actually explains why no small counterexample was found. 

Andrew ran some computations, and found a counterexample for cyclic group of order $30$. 

Counterexample: $x_0=1/2$, $x_2=\frac{30}{2}-\frac{1}{2}=29/2$, $x_3=\frac{30}{3}-\frac{1}{2}=19/2$, $x_5=\frac{30}{5}-\frac{1}{2}=11/2$, and $0$ everywhere else. 
It's not hard to check the point is feasible. Here I rephrase Andrew's proof that this is actually a vertex. 
There are $30$ tight constraints. The whole group constraint, the three
subgroups generated by $2,3$ and $5$ respectively, and non-negativity constraints. Because we have $30$ variables, $x$ is a vertex.

One might wonder if the polytope for $\mathbb{F}_2^n$ is integral for all $n$. Unfortunately, Andrew also found a non-integral of the polytope for $\mathbb{F}_2^4$.