2
$\begingroup$

While doing my research, I came across yet another problem in $\mathbb Z/n\mathbb Z$ (see my previous question on a related matter here).

Let $n$ be a prime and let $k$ be an integer, $1 \leq k \leq n-1$. Determine a number $t$ such that, whichever distinct non-zero elements $i_1, i_2, \ldots, i_t \in \mathbb Z/n\mathbb Z$ you pick, there would always exist distinct indices $t_1$ and $t_2$, $1 \leq t_1, t_2 \leq t$, and an integer $k_1$, $1 \leq k_1 \leq k$, such that

$$ i_{t_2} \equiv k_1i_{t_1} \pmod{n}. $$

I am especially interested in the case when $n$ is prime and $k \approx n/2$. At first I thought that, in this special setting, $t \leq cn/k$ for some constant $c$, but I guess this is way too optimistic. Any thoughts on the problem would be very much appreciated.

Improve this question
$\endgroup$
5
  • $\begingroup$ @Kevin, thanks a lot for pointing this out. The order does not matter. I will fix it now. $\endgroup$ Commented Jan 23, 2017 at 18:27
  • $\begingroup$ A trivial observation is that $t=n-k+1$ suffices: scaling appropriately, we can assume that $i_1=1$, and then at least one of $i_2,\dotsc i_t$ does not belong to $[k+1,n-1]$ in view of $t-1>n-1-k$; now if, say, $i_s\in[1,k]$, then also $i_s/i_1\in[1,k]$. $\endgroup$ Commented Jan 23, 2017 at 19:53
  • $\begingroup$ @Seva, I consider this upper bound trivial, sorry for not mentioning it in the statement of the problem. I wonder if one could come up with an upper bound that is o(n). $\endgroup$ Commented Jan 23, 2017 at 19:56
  • $\begingroup$ I think deligne's RH is sufficient to prove that for any fixed $t$, as $n$ goes to infinity, for $i_1, i_t$ random, the ratios $(i_{t_1}/i_{t_2})/n$ behave like independent, identically distributed variables in $\mathbb R/\mathbb Z$ and so for large $n$ they are all in $(1/2,1)$ with probability approaching $1/2^{n(n-1)/2}$. So no bound of the form $cn/k$ is valid as we can make $t$ arbitrarily large with $k=n/2$. $\endgroup$ Commented Jan 23, 2017 at 20:56
  • $\begingroup$ This can be even made to give an explicit lower bound with enough effort. $\endgroup$ Commented Jan 23, 2017 at 20:58

0

Reset to default

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.