# How many arithmetic progressions are necessary to form an arbitrary subset of $\mathbb{Z}_n$?

I couldn't find a way to ask the question in under 150 characters, so I've rewritten it in a way that makes more sense.

Given an integer $$n$$, what is the minimum $$k$$ such that for any subset $$X \subseteq \mathbb{Z}/n\mathbb{Z}$$, there exists a set of order at most $$k$$ of arithmetic progressions whose union is exactly equal to $$X$$?

I am interested in the group ($$\mathbb{Z}/n \mathbb{Z}$$, +), so I would like to consider an arithmetic progression to be a set $$\{a, a+d, a+2d, \dots, a+kd\}$$, where addition is calculated mod $$n$$. For example, in $$\mathbb{Z}/12 \mathbb{Z}$$, I would consider $$9, 11, 1, 3$$ to be an arithmetic progression of length 4.

To give some examples of what I am thinking about, I will consider some subsets of $$\mathbb{Z}/24 \mathbb{Z}$$. The set $$\{0, 1, 2, \dots, 11\}$$ can be considered to be a single arithmetic progression. The set $$\{0,3,4,5,20,22\}$$ can be considered to the the union of the two arithmetic progressions $$(3,4,5)$$ and $$(20,22,0)$$. The set $$\{1,2,4,8,16\}$$ is not a union of two arithmetic progressions, but we can consider it to the union of three arithmetic progressions, namely $$(1,2)$$, $$(2,4)$$, and $$(8,16)$$. What I have shown is that given some subset of $$\mathbb{Z}/24 \mathbb{Z}$$, we may need three (or possibly more) arithmetic progressions in order to form a union exactly equal to that subset. So for $$n=24$$, $$k \geq 3$$.

Is there a general way to calculate $$k$$ for general $$n$$? Are there any results or conjectures that are related to this kind of question in any way?

Any help would be appreciated. Thank you.

• It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so. – Torsten Schoeneberg Dec 24 '18 at 18:54
• Conjecture: An $X$ with maximal $k$ is given by the first $k+1$ entries of $(0,1,3,6,10,15, ...)$, as soon as the distance of the last entry to $n$ is greater than all distances that occur before. This gives $k$ to be the largest number such that $\frac{k(k+1)}{2} +k \le n$, which is $k = \lfloor \sqrt{2n+\frac94} -\frac32 \rfloor$. – Torsten Schoeneberg Dec 24 '18 at 18:54