2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so. $\endgroup$ – Torsten Schoeneberg Dec 24 '18 at 18:54
  • 1
    $\begingroup$ 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$. $\endgroup$ – Torsten Schoeneberg Dec 24 '18 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.