Assume the positive integers $\mathbb{N}$ are partitioned as $$\mathbb{N} = \cup_{i = 1}^n (a_i + b_i \mathbb{N})$$ where $a_i, b_i \in \mathbb{N}$. Prove that all such partitions are obtained by the following algorithm: partition $\mathbb{N}$ into a finite number of a.p.'s with equal steps, then partition one of these a.p.'s into a further union of a.p.'s with equal steps, then take one of the remaining a.p.'s (either with the first or second obtained step) and partition further into a.p.'s with equal steps etc.

A similar question has already been asked [1], but not about the structure. This question is posed as Problem 1.5., p. 6, in Mathematical Coloring Book, and is claimed to be equivalent to Problem 1.4. on the same page, however after some checking I couldn't see this. I imagine this is well studied.

An attempt at proving the claim: using generating functions as in [1], one has $$\frac{1}{1-x} = \sum_{i = 1}^k \frac{x^{a_i}}{1 - x^{b_i}}$$ Let $B = \max\{b_i\}$ and $S = \{i \mid b_i = B\}$. Then $|S| \geq 2$ and since the $B$-th cyclotomic polynomial $\Phi_B$ is irreducible, we must have $$\Phi_B(x) Q(x) = \sum_{i \in S} x^{a_i}$$ with $Q(x) \in \mathbb{Z}[x]$, where $a_i$ are taken modulo $B$. The claim would be to prove that $a_i$'s for $i \in S$ form themselves a finite disjoint union of arithmetic progressions (modulo $B$) and by induction on the number of steps in the algorithm above to prove the claim. This leads to studying vanishing sums of roots of unity as in e.g. article below, but I haven't succeeded in finding such a claim.

Mann, Henry B., On linear relations between roots of unity, Mathematika, Lond. 12, 107-117 (1965). ZBL0138.03102.

  • 2
    $\begingroup$ What you wanted might be "NDCS (natural disjoint covering systems)". But, there are disjoint covering systems which are not natural. $\endgroup$ – Zhi-Wei Sun Mar 19 at 0:02
  • 1
    $\begingroup$ For vanishing sums of roots of unity, see also Conway and Jones, Trigonometric diophantine equations, Acta Arith 30 (1976) 229-240, available at matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3033.pdf $\endgroup$ – Gerry Myerson Mar 19 at 0:03
  • 1
    $\begingroup$ This may be relevant. Lam and Leung, On vanishing sums of roots of unity. arxiv.org/abs/math/9511209 $\endgroup$ – kodlu Mar 19 at 0:04
  • 2
    $\begingroup$ These systems are also called "natural exact covering systems". A recent paper is Goulden et al., Natural exact covering systems and the reversion of the Mobius series, arxiv.org/abs/1711.04109. At the end of Section 2, it says, "It has also long been known that not every ECS is an NECS, e.g., Porubsky ́ [P74]. The smallest size for an ECS that is not an NECS is 13, [S15, Example 3.1]." P74 is S. Porubsky ́, Natural exactly covering systems of congruences, Czechoslovak Math. J. 24 (1974), 598–606. S15 is (continued, next comment) $\endgroup$ – Gerry Myerson Mar 19 at 0:13
  • 2
    $\begingroup$ (continued from previous comment) O. Schnabel, On the reducibility of exact covering systems, INTEGERS 15 (2015), Paper #A34, available at emis.de/journals/INTEGERS/papers/p34/p34.pdf $\endgroup$ – Gerry Myerson Mar 19 at 0:13

The Schnabel paper mentioned in the comments gives the example,


where $a(b)$ stands for $a+b{\bf N}$. This is said to follow from the impossibility of splitting the vanishing sum $$\zeta^5+\zeta^6+\zeta^{12}+\zeta^{18}+\zeta^{24}+\zeta^{25}$$ into two vanishing sums, where $\zeta$ is a primitive 30th root of unity.

  • $\begingroup$ The Porubsky paper mentioned in the comments gives two examples. One uses the moduli $6,10,15$ once each, and the modulus $30$, $20$ times. The other uses $2$ once, $12$ twice, $20$ four times, $30$ once, and $60$ six times. It is available via eudml.org/doc/12826 $\endgroup$ – Gerry Myerson Mar 19 at 0:37
  • $\begingroup$ Thanks a lot! Maybe the example by Porubsky is easier to justify, since it just uses the fact that the gcd of the steps (moduli) is > 1 for any NECS and the example with 6, 10, 15 x 1 and 30 x 20 clearly doesn't sastisfy this. $\endgroup$ – Ceka Mar 19 at 11:25
  • $\begingroup$ Another comment. The Porubsky paper and his "ab-systems" seem to give some structure to any exact coverings systems (ECS). The worst thing that can happen is to make some splitting (into a.p.'s as in the algorithm above) and then "collapse" some of these a.p.'s into a smaller one. This can be nicely described by using Hasse diagrams. $\endgroup$ – Ceka Mar 19 at 11:32
  • $\begingroup$ Just to note it here, your answer implies that Problem 1.5. from the "Mathematical Coloring Book" is false. $\endgroup$ – Ceka Mar 19 at 11:35

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.