# Covering integers by finitely many arithmetic progressions structure

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.

• What you wanted might be "NDCS (natural disjoint covering systems)". But, there are disjoint covering systems which are not natural. – Zhi-Wei Sun Mar 19 at 0:02
• 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 – Gerry Myerson Mar 19 at 0:03
• This may be relevant. Lam and Leung, On vanishing sums of roots of unity. arxiv.org/abs/math/9511209 – kodlu Mar 19 at 0:04
• 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) – Gerry Myerson Mar 19 at 0:13
• (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 – Gerry Myerson Mar 19 at 0:13

$$2(6),4(6),1(10),3(10),7(10),9(10),0(15),5(30),6(30),12(30),18(30),24(30),25(30)$$
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.
• 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 – Gerry Myerson Mar 19 at 0:37