1
$\begingroup$

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

Improve this question
$\endgroup$
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$ Commented Jan 22, 2017 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$ Commented Jan 22, 2017 at 5:53

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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$ Commented Jan 22, 2017 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$ Commented Jan 22, 2017 at 13:56
  • $\begingroup$ I fixed indices according to he condition that all $i_r$ are non-zero. $\endgroup$ Commented Jan 22, 2017 at 14:17

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.