10
$\begingroup$

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, 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.)

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Joshua Grochow Aug 10 '17 at 23:31
  • 1
    $\begingroup$ @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. $\endgroup$ – Andrew Morgan Aug 11 '17 at 2:52
  • $\begingroup$ 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? $\endgroup$ – John Machacek Aug 14 '17 at 21:52
  • $\begingroup$ @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. $\endgroup$ – Andrew Morgan Aug 15 '17 at 1:43
  • $\begingroup$ @AndrewMorgan Why is the polytope natural or have utility? The coordinates $x_i$ only capture size of $G$. $\endgroup$ – T.... Aug 20 '18 at 5:49
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.