3
$\begingroup$

Let $n \in \mathbb Z$ with $n \ge 3$ and let $p$ be a prime number such that $n|p-1$. Let $a_1,a_2,\dots,a_{2n-1} \in \mathbb Z/p\mathbb Z$. Suppose that the same class is represented by at most $n-1$ elements in the sequence of $a_i$'s. Since $\frac{2n-1}{n-1} > 2$, there are at least $3$ distinct classes in the sequence $a_1,\dots,a_{2n-1}$.

Let $s$ such that $ord_p(s) = n$ and consider $b_1s^{n-1} + b_2s^{n-2} + \dots + b_{n-1}s + b_n \pmod p$. A "valid operation" is to choose $n$ numbers among $a_1,\dots,a_{2n-1}$ and replace them in place of $b_1, \dots, b_n$ in some order.

It's easy to show that the cyclic permutations reach only the class $0 \pmod p$ or reach $n$ distinct classes $\pmod p$, because if $1 \le l < k \le n$ then: $$b_{k+1}s^{n-1} + \dots + b_ns^k + b_1s^{k-1} + \dots + b_k \equiv b_{l+1}s^{n-1} + \dots + b_ns^l + b_1s^{l-1} + \dots + b_l \pmod p$$ $$\iff (s^{n-k-2} - s^{n-l-2})(b_1s^{n-1} + \dots + b_n) \equiv 0 \pmod p$$ $$\iff l = k \text{ (contradiction, so all cyclic permutations are distinct) or }$$ $$b_1s^{n-1} + \dots + b_n \equiv 0 \pmod p \Rightarrow b_{k+1}s^{n-1} + \dots + b_ns^k + b_1s^{k-1} + \dots + b_k \equiv 0 \pmod p,$$ so all cyclic permutations reach $0 \pmod p$.

Question: Is it possible to show that valid operations reach at least $n+1$ classes $\pmod p$? I just need one more element.

For example, if $n = 3$ and $p = 7$ then the possibilities for $a_1,\dots,a_5$ are the following: $a,a,b,b,c$; $a,a,b,c,d$ and $a,b,c,d,e$ (where different letters represent different classes $\pmod p$).

I can answer this question if $n=3$. In fact, let $p \equiv 1 \pmod 3$ and consider $ord_p(s) = 3$. Select $a,b,c$ distinct classes in the sequence of $5$ elements. We only need to show that $as^2 + cs + b \not\in \{as^2 + bs + c, bs^2 + cs + a, cs^2 + as + b\}$ as classes $\pmod p$, and this is just an easy calculation (we use $s \not\in \{-1,0,1\} \pmod p$).

Perhaps Cauchy-Davenport inequality will help us. Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ can you please clarify what is a "valid operation"? some examples will be welcome. $\endgroup$
    – WhatsUp
    Jul 31, 2016 at 2:23
  • $\begingroup$ Sure! For example, take $n=5$, $p=11$ and $s = 4$. Suppose that we have a sequence $a_1, \dots, a_9 \in \mathbb Z_{11}$ such that each class $\pmod {11}$ is represented by at most 4 elements. Some examples of this sequences are: 1) $0,0,0,0,7,7,7,7,3$ 2) $0,1,2,3,4,5,6,7,8$ 3) $1,3,5,7,8,8,9,9,9$ A valid operation consists on taking any 5 elements $b_1,\dots,b_5$ in one of these kind of sequences and valuate it on $c_1s^4 + c_2s^3 + c_3s^2 + c_4s + c_5$, where $\{b_1,\dots,b_5\} = \{c_1,\dots,c_5\} \pmod {11}$ (we are free to choose the order of the coefficients). (next comment) $\endgroup$
    – Sávio
    Aug 6, 2016 at 19:58
  • $\begingroup$ Now, I would like to show that these kind of evaluations reaches at least 6 classes $\pmod{11}$. For example, in the sequence (1) above one may take $\{b_1,\dots,b_5\} = \{0,0,0,0,7\}$ and it'll just generate 5 elements $\pmod {11}$, namely $7s^4, 7s^3, 7s^2, 7s, 7$. But we instead can take $\{b_1,\dots,b_5\} = \{0,0,0,7,3\}$ and it generates $3s^4 + 7s^3 \equiv 6, 3s^3 + 7s^2 \equiv 7, 3s^2 + 7s \equiv 10, 3s + 7 \equiv 8, 3 + 7s^4 \equiv 2 \pmod{11}$ (5 distinct elements). But it also generates $7s + 3 \equiv 9 \pmod{11}$, so we generate at least 6 distinct elements $\pmod{11}$. (see next..) $\endgroup$
    – Sávio
    Aug 6, 2016 at 20:14
  • $\begingroup$ So, the sequences with at least 3 classes $0$, one class $7$ and one class $3$ satisfy what I want. I'd like to show that for every sequence (with $2n-1$ elements such that all classes $\pmod p$ are represented by at most $n-1$ elements) we can take a subsequence $b_1,\dots,b_n$ and valuate it on $c_1s^{n-1} + \dots + c_{n-1}s + c_n$ (where $\{b_1,\dots,b_n\} = \{c_1,\dots,c_n\}$) returning $n+1$ distinct elements (by permuting coefficients). (I now it's a bit confusing...) $\endgroup$
    – Sávio
    Aug 6, 2016 at 20:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.