Demostrar que $|S|< \frac{2p}{k+1}$

Question

Dado un número primo $p$ . Sea $a_1,a_2 \cdots a_k$ ( $k \geq 3$ ) sean números enteros no divisibles por $p$ y que tienen diferentes residuos cuando se dividen por $p$ . Sea $$ S= \{ n \mid 1 \leq n \leq p-1, (na_1)_p < \cdots < (na_k)_p \} $$ Aquí $(b)_p$ denota el residuo cuando el entero $b$ se divide por $p$ . ¿Cómo se puede demostrar que $|S|< \frac{2p}{k+1}$ ?

Answer 1

Si algo está mal o es incomprensible, no dude en comentarlo. Soy un novato en inglés, por lo que alguna frase que haga puede tener muchos errores gramaticales y ser confusa al leerla. Intentaré explicar mis pensamientos lo mejor posible :D

En primer lugar, dejamos que $a_0 = 0$ y $a_{k+1} = p$ , ampliando así la secuencia $\{a_i\}$ .

Definimos $\{b_l\}_{l=0}^k$ para ser $b_l = a_{l+1}- a_l$ .

Tenga en cuenta que para todos los $n \in S$ ,

$$\begin{align} \sum_{l=0}^k (n b_l)_p = {} & (na_1)_p + \left((na_2)_p - (na_1)_p\right) + \\ {} & \cdots + \left( (na_k)_p - \left(na_{k-1} \right)_p \right) + \left(p - (na_k)_p\right) \\ = {} & p \end{align}$$

Ahora evaluamos $$T = \sum_{n \in S}\sum_{l=0}^k (n b_l)_p$$ de dos maneras diferentes. La primera forma es evaluarla directamente utilizando la fórmula anterior. $$T = \sum_{n \in S}\sum_{l=0}^k (n b_l)_p = \sum_{n \in S} p = p |S|$$

La segunda forma es la siguiente.

$$ \begin{align*} T = & \sum_{n \in S}\sum_{l=0}^k (n b_l)_p = \sum_{l=0}^k\sum_{n \in S} (n b_l)_p \geq \sum_{l = 0}^k \sum_{m = 1}^{|S|} m = \frac{(k+1)|S|(|S|+1)}{2} \end{align*} $$ Obsérvese que la desigualdad se mantiene porque para cada $0 \leq l \leq k$ y $n_1, n_2 \in S$ , si $n_1 \neq n_2$ , $n_1b_l \not\equiv n_2b_l \mod p$ . Por lo tanto, cada $(nb_l)_p$ son diferentes entre sí y son mayores que 0 para cada $l$ .

Combinando los resultados, obtenemos $$p|S| = T \geq \frac{(k+1)|S|(|S|+1)}{2}$$ entonces $$\frac{2p}{k+1} \geq |S| + 1 > |S|$$