9
$\begingroup$

it is motivated by Density of congruence classes covered by a set

Let say just "$n$-gon" for the set of vertices of a regular $n$-gon inscribed in a unit circle, "2-gon" for the set of two opposite points.

is it true that for given positive integers $1 < b_1 < b_2 < \dots < b_k$ the union of $b_i$-gons has the minimal cardinality when they all have a common vertex?

In other words, if $G_i$ are subgroups of the finite cyclic group $G$, is it true that $$|\cup_{i=1}^k x_iG_i|\ge |\cup_{i=1}^k G_i|$$ for arbitrary cosets $x_iG_i$?

$\endgroup$
13
  • $\begingroup$ "they share a vertex" = "they all share one vertex"? $\endgroup$ Nov 17, 2010 at 0:27
  • $\begingroup$ A 2-gon and a regular triangle can fit inside a 12-gon without having any vertex in common. Maybe I don't understand the question. $\endgroup$ Nov 17, 2010 at 0:36
  • $\begingroup$ @Gjergi, if I understand the question, your example shows the minimal cardinality for 2, 3, 12 is 12 - but that cardinality can (also) be achieved by a configuration in which all three polygons share a vertex. A true counterexample would be one where there's a configuration strictly better than any in which all polygons share a vertex. But I, too, confess to some uncertainty about the meaning of the question. $\endgroup$ Nov 17, 2010 at 2:08
  • $\begingroup$ @Gerry, but isn't the minimal cardinality just LCM(b_i)? $\endgroup$ Nov 17, 2010 at 2:53
  • $\begingroup$ @Gjergi, if $k=2$, $b_1=3$, $b_2=4$, then (provided, as ever, that I understand the problem) minimal cardinality is 6 whereas the lcm of the $b_i$ is 12. $\endgroup$ Nov 17, 2010 at 5:01

1 Answer 1

4
$\begingroup$

Let me attempt a proof using the group-theoretic formulation. I will use the additive notation for the group operation.

The proof is by induction on $n=|G|$, with the base being trivial. Let $n=p^rm$ for some prime $p$ with $\gcd(p,m)=1$. Consider $G' = pG$. Our goal is to reduce the problem for $G$ to its instance for $G'$. Let $R_j:=G' + jm$. Then $\{R_0,R_1,\ldots, R_{p-1}\}$ is a partition of $G$ into $G'$-cosets.

Let $G_i=d_iG$ be a subgroup of $G$ with $d_i | n$. If $p|d_i$ then $G_i \subseteq G'$ and every $G_i$ coset belongs to some $R_j$. In this case we say that $G_i$ is of the first kind. Otherwise, $d_i | m$, and translating $G_i$ by $m$ does not change $G_i$. We say that such $G_i$ is of the second kind.

Let $S = \cup_{i=1}^k (G_i+x_i)$ be the union under consideration, let $S_1$ be the union of cosets of the first kind among cosets comprising $S$, and $S_2$ -- of the second. Let $T_j=S_1 \cap R_j$ for $0\leq j \leq p-1$. Then $T_j$ is actually union of some of our cosets, and the sets $T_0,T_1,\ldots,T_{p-1}$ are disjoint. Let $T_j'=T_j-jm$: we shift all the cosets in $T_j$ from $R_j$ to $R_0=G'$. Note that $S_2-jm=S_2$ and therefore the intersection of $T_j$ and $S_2$ shifts with $T_j$. In particular, $|T_j'-S_2|=|T_j-S_2|$.

The set $S'=S_2 \cup (\cup_{j=0}^{p-1}T'_j) $ is still a union of cosets of $G_i$'s. We have

$|S'| \leq |S_2|+ \sum_{j=1}^{p-1}|T'_{j}-S_2| = |S_2|+ \sum_{j=1}^{p-1}|T_{j}-S_2|=|S|$.

Thus it suffices to consider $S'$, which means that we may assume that $S_1 \subseteq G'$. Let $G_i'=G_i \cap G'$ and let $x_i'$ be chosen so that $G_i'+x_i'= (G_i+x_i) \cap G'$. By the induction hypothesis applied to $G'$, we get

$a_1:=| \cup_{i=1}^k G_i' | \leq | \cup_{i=1}^k (G_i' + x_i')|=: b_1$

and also

$a_2:=|\cup_{i: G_i \not \subseteq G'} G_i'| \leq |\cup_{i: G_i \not \subseteq G'} (G_i' + x_i')|=:b_2$,

where in this second inequality we restrict our attention to $G_i$'s of the second kind. The set $S_2$ is the disjoint union of $p$ translates of its intersection with $G'$, which intersection is present on the right side of the inequality directly above. It follows that

$|S|=|S \cap G'|+|S_2 - G'|=b_1 + (p-1)b_2,$

while similarly we have

$|\cup_{i=1}^k G_i|=a_1 + (p-1)a_2$.

It follows that $|S| \geq |\cup_{i=1}^k G_i|$, as desired.


Finally, let me note that the inequality does not hold for non-cyclic groups. Already for $G = \mathbf{Z}_2 \times \mathbf{Z}_2$ the union of three distinct subgroups of $G$ of size $2$ is $G$, while it is possible to choose their cosets with the union of size $3$.

$\endgroup$
3
  • $\begingroup$ Looks like truth! $\endgroup$ Nov 18, 2010 at 20:17
  • $\begingroup$ Very nice. A couple of very small points. One, you've used the same symbol, $k$, for the amount of $p$ dividing $n$ and for the number of subgroups. Two, you're implicitly assuming $d_i$ has been chosen to be a divisor of $n$ (else, the "otherwise, $d_i\mid m$" clause does not apply). $\endgroup$ Nov 21, 2010 at 23:36
  • $\begingroup$ @Gerry Myerson: Thank you. I've implemented the suggested corrections. $\endgroup$ Nov 22, 2010 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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