grandes-ecoles 2020 QIV.5

grandes-ecoles · France · x-ens-maths-d__mp Number Theory Combinatorial Number Theory and Counting
5. In the remainder of this part, $p$ denotes a fixed odd prime integer. One may use without proof Wilson's theorem: $$(p-1)! + 1 \equiv 0 \quad [p]$$ We denote by $\mathbb{Z}_p$ the field $\mathbb{Z}/p\mathbb{Z}$ and if $a \in \mathbb{Z}$, we denote by $\bar{a}$ its class in $\mathbb{Z}_p$. For $1 \leq k \leq e_p$, we denote by $\mathcal{P}_k$ the set of subsets $P$ with $k$ elements of $\mathbb{Z}_p$ satisfying the condition $$\forall \alpha \in P, \quad \alpha + 1 \notin P.$$ a. For $P = \{\alpha_1, \ldots, \alpha_k\} \in \mathcal{P}_k$ and $\alpha \in \mathbb{Z}_p$, we set $\tau_\alpha(P) = \{\alpha_1 + \alpha, \ldots, \alpha_k + \alpha\}$. Show that the map $\alpha \mapsto \tau_\alpha$ is a homomorphism from $(\mathbb{Z}_p, +)$ to the group of bijections of $\mathcal{P}_k$. b. We define a relation $\mathscr{R}$ between elements of $\mathcal{P}_k$ as follows: if $A, B$ are in $\mathcal{P}_k$, $A \mathscr{R} B$ if and only if there exists $\alpha \in \mathbb{Z}_p$ such that $B = \tau_\alpha(A)$. Show that $\mathscr{R}$ is an equivalence relation on $\mathcal{P}_k$, and that each equivalence class has cardinality $p$ and admits a representative of the form $\{\bar{0}, \bar{a}_2, \ldots, \bar{a}_k\}$ with $0 < a_2 < \cdots < a_k < p$. We choose such a representative for each class and we denote by $R$ the set of representatives thus chosen. c. Prove that $$\overline{c_{p-1,k}} = \sum_{\{0, \ldots, a_k\} \in R} \sum_{1 \leq \ell \leq p-1} \bar{\ell}\, \overline{\ell+1}\, \overline{a_2 + \ell}\, \overline{a_2 + \ell + 1} \cdots \overline{a_k + \ell}\, \overline{a_k + \ell + 1}$$
5. In the remainder of this part, $p$ denotes a fixed odd prime integer. One may use without proof Wilson's theorem:
$$(p-1)! + 1 \equiv 0 \quad [p]$$
We denote by $\mathbb{Z}_p$ the field $\mathbb{Z}/p\mathbb{Z}$ and if $a \in \mathbb{Z}$, we denote by $\bar{a}$ its class in $\mathbb{Z}_p$. For $1 \leq k \leq e_p$, we denote by $\mathcal{P}_k$ the set of subsets $P$ with $k$ elements of $\mathbb{Z}_p$ satisfying the condition
$$\forall \alpha \in P, \quad \alpha + 1 \notin P.$$
a. For $P = \{\alpha_1, \ldots, \alpha_k\} \in \mathcal{P}_k$ and $\alpha \in \mathbb{Z}_p$, we set $\tau_\alpha(P) = \{\alpha_1 + \alpha, \ldots, \alpha_k + \alpha\}$. Show that the map $\alpha \mapsto \tau_\alpha$ is a homomorphism from $(\mathbb{Z}_p, +)$ to the group of bijections of $\mathcal{P}_k$.\\
b. We define a relation $\mathscr{R}$ between elements of $\mathcal{P}_k$ as follows: if $A, B$ are in $\mathcal{P}_k$, $A \mathscr{R} B$ if and only if there exists $\alpha \in \mathbb{Z}_p$ such that $B = \tau_\alpha(A)$. Show that $\mathscr{R}$ is an equivalence relation on $\mathcal{P}_k$, and that each equivalence class has cardinality $p$ and admits a representative of the form $\{\bar{0}, \bar{a}_2, \ldots, \bar{a}_k\}$ with $0 < a_2 < \cdots < a_k < p$. We choose such a representative for each class and we denote by $R$ the set of representatives thus chosen.\\
c. Prove that
$$\overline{c_{p-1,k}} = \sum_{\{0, \ldots, a_k\} \in R} \sum_{1 \leq \ell \leq p-1} \bar{\ell}\, \overline{\ell+1}\, \overline{a_2 + \ell}\, \overline{a_2 + \ell + 1} \cdots \overline{a_k + \ell}\, \overline{a_k + \ell + 1}$$