Exercise 10, § 12

Let t, $n$, k be three integers $\geq 1$ such that $t \leq n$ and $n$ divides $2^k - 1$. Let S be the smallest set of integers such that $(1, t) \subset S \subset (1, n)$ and the condition « i $\in S$, $2i \equiv j \pmod{n}$ and $1 \leq j \leq n$ » implies $j \in S$. Put $m = \mathrm{Card}\ S$. Let $\xi$ be an element of order $n$ in $\mathbf{F}_{2^k}^*$ and put $P(X) = \prod_{j \in S} (X - \xi^j)$. a) Prove that $P(X) \in \mathbf{F}_2[X]$. b) Show that if $R(X) \in \mathbf{F}_2[X]$ is of degree $< n$ and is a non-zero multiple of $P(X)$, then there are strictly more than t non-zero coefficients. c) Deduce the construction of a mapping $Q : \mathbf{F}_2^n \to \mathbf{F}_2^m$ such that if $u, v \in \mathbf{F}_2^n$ are distinct and have at most t distinct coordinates then $Q(u) \equiv Q(v)$. d) Calculate S, $m$ and P when $t = 6,\ n = 15,\ k = 4$.