Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
"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
show 8 more comments

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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