Skip to main content
3 of 4
added figure

Minimal density hitting set for k-length arithmetic progressions

This is problem which came up in the process of designing a game. Thus, I don't know any previous work relevant to the problem.

Fix a small set $D$ of a natural numbers. For example, $D=\{1,2,3\}$. Also fix natural number $k$, e.g., $k=5$.

We wish to consider a hitting set of all $k$-length arithmetic sequences $\{a, a+d, a+2d,...a+(k-1)d\}$ where $d \in D$ and $a > 0$.

Such a hitting set is a subset of the natural numbers $H$ such that for any $d \in D$ and $a > 0$, at least one of $a, a+d, ..., a+(k-1)d$ is contained in $H$

If the limit $\lim_{n \to \infty} |H \cap \{1,...,n\}|/n = \delta$ exists, then we say that $\delta$ is the density of the hitting set $H$. For any given set $D$ and number $k$, there exists an infimal density $\delta_0$ of all such hitting sets. I would like to estimate the infimal density $\delta_0$ for an arbitrary set $D$ and number $k$.

I give some concrete examples.

Let $D=\{1\}$. Then the optimal hitting set is $C=\{k,2k,...\}$ with a density of $1/k$.

Let $D$ be a singleton $D=\{d\}$. Then the optimal hitting set is $C=\{1,2,...,d-1,1+kd,2+kd,..,d-1+kd,1+2kd,...,d-1+2kd,...\}$ with a density of $1/k$.

Let $D=\{1,2\}$ and $k=2$. Then an example of a hitting set is $C=\{n: n \mod 3 \in \{1,2\}\} = \{1,2,4,5,7,8,...\}$ with a density of 2/3. However, I don't know whether a hitting set with a lower density exists. (EDIT: The answer is no, see comment by domotorp)

EDIT:

A visualization of the problem. The top figure depicts the $k$-length arithmetic sequences for $k=6$ and $D=\{1,2,3\}$. hit by an element $n$, the red dot. The black pixels in the first row are the values $a$ for which the $d=1$ sequences are hit by $n$. The black pixels in the second row are the values $a$ for which the $d=2$ sequences are hit by $n$. Analogously for the third row. The figure on the bottom depicts a hitting set for the problem $k=6, D=\{1,2,3\}$ with a density $3/8$.

enter image description here