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.

$\endgroup$
  • $\begingroup$ @Kevin, thanks a lot for pointing this out. The order does not matter. I will fix it now. $\endgroup$ – Anton Jan 23 '17 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$ – Seva Jan 23 '17 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$ – Anton Jan 23 '17 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$ – Will Sawin Jan 23 '17 at 20:56
  • $\begingroup$ This can be even made to give an explicit lower bound with enough effort. $\endgroup$ – Will Sawin Jan 23 '17 at 20:58

Your Answer

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

Browse other questions tagged or ask your own question.