# union of regular polygons

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

-
"they share a vertex" = "they all share one vertex"? – Joseph O'Rourke Nov 17 '10 at 0:27
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. – Gjergji Zaimi Nov 17 '10 at 0:36
@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. – Gerry Myerson Nov 17 '10 at 2:08
@Gerry, but isn't the minimal cardinality just LCM(b_i)? – Gjergji Zaimi Nov 17 '10 at 2:53
@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. – Gerry Myerson Nov 17 '10 at 5:01

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

-
Looks like truth! – Fedor Petrov Nov 18 '10 at 20:17
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). – Gerry Myerson Nov 21 '10 at 23:36
@Gerry Myerson: Thank you. I've implemented the suggested corrections. – Sergey Norin Nov 22 '10 at 16:12