<p>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. </p>

<p>On the positive side. </p>

<p><strong>Theorem</strong>:
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.</p>

<p>This is because the family of subgroups is a union of two laminar families.</p>

<p>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. </p>

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

<p><strong>Counterexample</strong>: $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.</p>

<p>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$.</p>

CC BY-SA 4.0
2018-08-19T21:52:43.503Z
2018-08-19T21:52:43.503Z
Chao Xu
<p>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:</p>

<p>$$\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}$$</p>

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

<hr>

<p>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 <em>not</em> integral when $\Gamma$ is any of $S_3$, $D_4$, and $D_5$, so abelianness is apparently essential.</p>

<p>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$.</p>

<p>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.</p>

<p>This system is very reminiscient of those defining <a href="https://en.wikipedia.org/wiki/Polymatroid" rel="nofollow noreferrer">polymatroids</a>, 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.</p>

<p>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.)</p>

CC BY-SA 3.0
2017-08-10T23:31:57.237Z
Really interesting question! In the case of $\mathbb{F}_2^n$, you might be able to get some mileage out of the analysis by noting that the automorphism group acts transitively on the non-identity elements (in fact, in a sense "n-transitively", in that it sends any n-tuple of linearly independent group elements to any other such n-tuple). To get started, you can assume WLOG that $x_{1000\dotsc 0}$ is the largest among the non-identity elements and that $x_{e_2}$ is the second-largest...
Joshua Grochow
CC BY-SA 3.0
2017-08-11T02:52:07.483Z
@JoshuaGrochow Thanks! I'm not sure that sorting the coordinates is the way to go, but symmetries are almost always useful. Another place to use them is on the constraints---automorphisms send subgroups to subgroups, after all. Something that seems useful is, for any point $x$, averaging it over all automorphisms that fix the set of constraints tight at $x$. I don't know how to make that quantity manageable though.
Andrew Morgan
CC BY-SA 3.0
2017-08-14T21:52:48.577Z
Yes this is a very interesting and curious question. (If you don't mind sharing) Was there motivation to look at these particular polytopes? Or just something that was stumbled upon by chance?
John Machacek
CC BY-SA 3.0
2017-08-15T01:43:56.107Z
@JohnMachacek I was attempting to characterize distributions on $\mathbb{F}_2^n$ which arise from a choice of linear subspace from an arbitrary distribution and then selecting uniformly at random an element of the subspace. This can be expressed as a covering LP whose dual has the above polytope as its feasible region. The fact that it happened to be integral in such interesting circumstances seemed too interesting not to share with tcs.se.
Andrew Morgan
CC BY-SA 4.0
2018-08-20T05:49:22.373Z
@AndrewMorgan Why is the polytope natural or have utility? The coordinates $x_i$ only capture size of $G$.
Turbo
CC BY-SA 4.0
2018-08-20T20:51:25.720Z
@user124864 I don't know of any uses. Whether it's natural is more subjective, but I'd argue it is. The construction is firstly functorial in the sense of category theory; ie, it's not like I'm picking some gobbledygook polytope for every group. Moreover, the polytope encodes the subgroup structure of $\Gamma$, and this is actually a lot of information. (But not necessarily "everything"- though it *is* everything if the group is abelian. See [here](https://mathoverflow.net/questions/35455).) If you want more than that, I guess I don't see how to convince you.
Andrew Morgan
CC BY-SA 4.0
2018-08-20T21:40:08.903Z
@AndrewMorgan I don't understand how capturing cardinality of subgroup captures structure.
Turbo
<gr.group-theory><fourier-analysis><convex-geometry>
Is this "subgroup packing" polytope integral?
Andrew Morgan
# Is this "subgroup packing" polytope integral?

(Asked by: username_0 on 2017-08-10)

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| & \forall G \le \Gamma \\
x\_g \ge 0 & \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&1&1\\1&0&1\\1&1&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](https://en.wikipedia.org/wiki/Polymatroid), 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.)

**Tags:** gr.group-theory, fourier-analysis, convex-geometry
> **Comments:**
> **username_1**: Really interesting question! In the case of $\mathbb{F}_2^n$, you might be able to get some mileage out of the analysis by noting that the automorphism group acts transitively on the non-identity elements (in fact, in a sense "n-transitively", in that it sends any n-tuple of linearly independent group elements to any other such n-tuple). To get started, you can assume WLOG that $x_{1000\dotsc 0}$ is the largest among the non-identity elements and that $x_{e_2}$ is the second-largest...  
> **username_0**: @JoshuaGrochow Thanks! I'm not sure that sorting the coordinates is the way to go, but symmetries are almost always useful. Another place to use them is on the constraints---automorphisms send subgroups to subgroups, after all. Something that seems useful is, for any point $x$, averaging it over all automorphisms that fix the set of constraints tight at $x$. I don't know how to make that quantity manageable though.  
> **username_2**: Yes this is a very interesting and curious question. (If you don't mind sharing) Was there motivation to look at these particular polytopes? Or just something that was stumbled upon by chance?  
> **username_0**: @JohnMachacek I was attempting to characterize distributions on $\mathbb{F}_2^n$ which arise from a choice of linear subspace from an arbitrary distribution and then selecting uniformly at random an element of the subspace. This can be expressed as a covering LP whose dual has the above polytope as its feasible region. The fact that it happened to be integral in such interesting circumstances seemed too interesting not to share with tcs.se.  
> **username_3**: @AndrewMorgan Why is the polytope natural or have utility? The coordinates $x_i$ only capture size of $G$.  
> **username_0**: @user124864 I don't know of any uses. Whether it's natural is more subjective, but I'd argue it is. The construction is firstly functorial in the sense of category theory; ie, it's not like I'm picking some gobbledygook polytope for every group. Moreover, the polytope encodes the subgroup structure of $\Gamma$, and this is actually a lot of information. (But not necessarily "everything"- though it *is* everything if the group is abelian. See [here](https://mathoverflow.net/questions/35455).) If you want more than that, I guess I don't see how to convince you.  
> **username_3**: @AndrewMorgan I don't understand how capturing cardinality of subgroup captures structure.  

---

## 1 answers

### Answer by username_4 on 2018-08-19. Score: 5 | Accepted answer

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


---

