# Covering a finite ring with arithmetic progressions

Let $n\geq 2$ be a positive integer and $k$ be a number between $1$ and $n$. Recently, I came across the following question about $\mathbb Z/n\mathbb Z$ and I wonder if it was studied before. I'd be thankful for any references or any suggestions on how to approach the problem.

Find the smallest integer $t$ (or an upper bound on $t$) such that, no matter which $t$ distinct non-zero elements $i_1,i_2,\ldots,i_t \in \mathbb Z/n\mathbb Z$ you pick, each element $j\in \mathbb Z/n\mathbb Z$ can be written in the form

$$j \equiv \ell i_r \pmod n,$$

where $0\leq \ell \leq k$ and $1\leq r \leq t$. In other words, $t$ $(k+1)$-term arithmetic progressions of the form $0, i_r, 2i_r, \ldots, ki_r$ entirely cover $\mathbb Z/n\mathbb Z$.

I am especially interested in the case when $n$ is prime and $k \approx n/2$.

• My guess is that for arbitrary n and 2*k at most n, one will have t at least k+1. For n =2k+1 prime, I think one can prove that each member lies in exactly k of the n-1 nontrivial progressions. Gerhard "Consider The Negative Forms Also" Paseman, 2017.01.21. – Gerhard Paseman Jan 22 '17 at 5:34
• In general, consider some collection C of subsets of size k all contained in a set of size 2k. For some member z of the big set, at least half of the members of C miss z. Gerhard "Don't Need A Ring Structure" Paseman, 2017.01.21. – Gerhard Paseman Jan 22 '17 at 5:53

The case of prime $n$.
We may suppose that $j\ne 0$. Consider $t$ distinct elements $j/i_1,\dots,j/{i_{t}}$. If all of them belong to the set $\{k+1,\dots,n-1\}$, we get $t\leqslant n-k-1$. Thus for $t=n-k$ we may always find $r$ such that $j/i_r\in \{1,2,\dots,k\}$ as you need. For $t=n-k-1$ this is not always possible: take $j=1$, $i_r=1/(n-r)$ for $r=1,\dots,n-k-1$.
• Also, do you think the answer would change drastically if I demand $i_r \neq 0$ and $i_1=1$? Because this is the setup in which I am mostly interested in. Your answer was quite surprising to me, as I would expect (at least in my setup) that the upper bound on $t$ is of the form $cn/k$, where $c$ is a constant. – Anton Jan 22 '17 at 13:47
• Thanks a lot for your answer. I think there is something wrong with indexing. Did you mean to write $i_{t-1}$ instead of $i_{k-1}$ at the beginning? Also, at the end, I suspect that you mean $i_{n-k}=0$ and not $i_k=0$. – Anton Jan 22 '17 at 13:56
• I fixed indices according to he condition that all $i_r$ are non-zero. – Fedor Petrov Jan 22 '17 at 14:17