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$.

  • $\begingroup$ 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. $\endgroup$ Jan 22 '17 at 5:34
  • $\begingroup$ 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. $\endgroup$ 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$.

  • $\begingroup$ 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. $\endgroup$
    – Anton
    Jan 22 '17 at 13:47
  • $\begingroup$ 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$. $\endgroup$
    – Anton
    Jan 22 '17 at 13:56
  • $\begingroup$ I fixed indices according to he condition that all $i_r$ are non-zero. $\endgroup$ Jan 22 '17 at 14:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.