Herzog–Schönheim conjecture

In mathematics, the Herzog–Schönheim conjecture is a combinatorial problem in the area of group theory, posed by Marcel Herzog and Jochanan Schönheim in 1974.

Let $G$ be a group, and let

$A=\{a_1{G}_1,\dots ,a_k{G}_k\}$

be a finite system of left cosets of subgroups $G_1,\dots ,G_k$ of $G$.

Herzog and Schönheim conjectured that if $A$ forms a partition of $G$ with $k>1$, then the (finite) indices $[G:G_1],\dots ,[G:G_k]$ cannot be distinct. In contrast, if repeated indices are allowed, then partitioning a group into cosets is easy: if $H$ is any subgroup of $G$ with index $k=[G:H]<\mathrm{\infty }$ then $G$ can be partitioned into $k$ left cosets of $H$.

Subnormal subgroups

In 2004, Zhi-Wei Sun proved a special case of the Herzog–Schönheim conjecture in the case where $G_1,\dots ,G_k$ are subnormal in $G$. A basic lemma in Sun's proof states that if $G_1,\dots ,G_k$ are subnormal and of finite index in $G$, then

$[G:\bigcap _{i=1}^k{G}_i]|\prod _{i=1}^k[G:G_i]$

and hence

$P\left(\right[G:\bigcap _{i=1}^k{G}_i\left]\right)=\bigcup _{i=1}^{k}P([G:G_i]),$

where $P(n)$ denotes the set of prime divisors of $n$.

Mirsky–Newman theorem

When $G$ is the additive group $\mathbb{\mathbb{Z}}$ of integers, the cosets of $G$ are the arithmetic progressions. In this case, the Herzog–Schönheim conjecture states that every covering system, a family of arithmetic progressions that together cover all the integers, must either cover some integers more than once or include at least one pair of progressions that have the same difference as each other. This result was conjectured in 1950 by Paul Erdős and proved soon thereafter by Leon Mirsky and Donald J. Newman. However, Mirsky and Newman never published their proof. The same proof was also found independently by Harold Davenport and Richard Rado.

In 1970, a geometric coloring problem equivalent to the Mirsky–Newman theorem was given as Problem 8 in the Soviet mathematical olympiad for 10th grade: suppose that the vertices of a regular polygon are colored in such a way that every color class itself forms the vertices of a regular polygon. Then, there exist two color classes that form congruent polygons. Nobody in the contestant had solved the problem.

Newman-Znám theorem

Štefan Znám in 1968 and subsequently Morris Newman in 1971 proved a general form of Mirsky–Newman theorem, namely given a disjoint covering system, suppose the maximum of the moduli $n$ occurs $l$ times, then $l\ge p$, the smallest prime dividing $n$. In 1986, an non-analytic proof of this general result was given.