Let $n$ be a non-zero natural number. We set $$\Phi_n : \left\lvert\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$
Show that $\Phi_n$ is well-defined by verifying $\operatorname{Im} \Phi_n \subset \llbracket 0, 2^n - 1 \rrbracket$.

(a) Show that if $p$ is a prime number and $k \geq 1$ is an integer, then $$\Phi _ { p ^ { k } } = X ^ { ( p - 1 ) p ^ { k - 1 } } + X ^ { ( p - 2 ) p ^ { k - 1 } } + \cdots + X ^ { p ^ { k - 1 } } + 1$$ (b) Calculate $\Phi _ { n }$ for $n = 1,2,3,4,5,6$.

Let $n$ be a non-zero natural number and $\Phi_n : \{0,1\}^n \rightarrow \llbracket 0, 2^n - 1 \rrbracket$, $(x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} x_j 2^{n-j}$.
Specify $\operatorname{Im} \Phi_n$ as a function of $A_n$, where $A_n = \left\{\sum_{j=1}^{n} x_j 2^{n-j}, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n\right\}$.

We assume that $n \geqslant 3$. Let $u$ be an endomorphism of $E$ nilpotent of index 2 and of rank $r$.
Assume $\operatorname{Im} u \neq \operatorname{Ker} u$. Show that there exist vectors $e_1, e_2, \ldots, e_r$ in $E$ and vectors $v_1, v_2, \ldots, v_{n-2r}$ belonging to $\operatorname{Ker} u$ such that $\left(e_1, u\left(e_1\right), e_2, u\left(e_2\right), \ldots, e_r, u\left(e_r\right), v_1, \ldots, v_{n-2r}\right)$ is a basis of $E$.

Let $n$ be a non-zero natural number and $\Phi_n : \{0,1\}^n \rightarrow \llbracket 0, 2^n - 1 \rrbracket$, $(x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} x_j 2^{n-j}$.
Using the results of Q8--Q10, deduce that $\Phi_n$ is bijective.

Let $P \in \mathbb { Z } [ X ]$ be a monic polynomial of degree $n \geq 1$, irreducible in $\mathbb { Q } [ X ]$ and all of whose complex roots have modulus 1. Let $z _ { 1 } , \ldots , z _ { n }$ be the complex roots of $P$ counted with their multiplicities, so that $P = \prod _ { i = 1 } ^ { n } \left( X - z _ { i } \right)$. For every integer $k \geq 0$ we denote $a _ { k } = z _ { 1 } ^ { k } + z _ { 2 } ^ { k } + \cdots + z _ { n } ^ { k }$.
(a) Show that the series $\sum _ { k \geq 0 } a _ { k } z ^ { k }$ converges for all $z \in \mathbb { C }$ such that $| z | < 1$.
(b) Let $z \in \mathbb { C }$ be non-zero such that $| z | < 1$ and let $f ( z )$ be the sum of the series $\sum _ { k \geq 0 } a _ { k } z ^ { k }$. Show that $$z f ( z ) P \left( \frac { 1 } { z } \right) = P ^ { \prime } \left( \frac { 1 } { z } \right)$$ (c) Deduce that $a _ { k } \in \mathbb { Z }$ for all $k \geq 0$.

Prove Theorem 2: Let $n \geq 1$ be an integer and $A(z) = \sum_{k=0}^{n-1} a_k z^k$ a nonzero polynomial such that $a_k \in \{-1, 0, 1\}$ for all $0 \leq k \leq n-1$. Then for all integer $L \geq 1$ we have $$\sup_{\theta \in \left[-\frac{\pi}{L}, \frac{\pi}{L}\right]} \left|A\left(e^{i\theta}\right)\right| \geq \frac{1}{n^{L-1}}$$

We have $D_n = \left\{\sum_{j=1}^{n} \frac{x_j}{2^j}, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n\right\}$ and $D = \bigcup_{n \in \mathbb{N}^{\star}} D_n$.
Establish the monotonicity in the sense of inclusion of the sequence $(D_n)_{n \geqslant 1}$ and then verify $D \subset [0,1[$.

Let $P \in \mathbb { Z } [ X ]$ be a monic polynomial of degree $n \geq 1$, irreducible in $\mathbb { Q } [ X ]$ and all of whose complex roots have modulus 1. Let $z _ { 1 } , \ldots , z _ { n }$ be the complex roots of $P$ counted with their multiplicities. For every integer $k \geq 0$ we denote $a _ { k } = z _ { 1 } ^ { k } + z _ { 2 } ^ { k } + \cdots + z _ { n } ^ { k }$.
(a) Show that there exist two integers $0 \leq k < l$ such that $a _ { k + i } = a _ { l + i }$ for all $i \in \{ 0,1 , \ldots , n \}$. We fix two such integers $k , l$ in questions 12b and 12c.
(b) Show that $\sum _ { i = 1 } ^ { n } F \left( z _ { i } \right) \left( z _ { i } ^ { l } - z _ { i } ^ { k } \right) = 0$ for every polynomial $F \in \mathbb { C } [ X ]$ of degree at most $n$.
(c) Show that $z _ { 1 } , z _ { 2 } , \ldots , z _ { n }$ are pairwise distinct. Deduce that $z _ { i } ^ { l - k } = 1$ for all $i \in \{ 1,2 , \ldots , n \}$ and conclude.

We have $\pi_n(x) = \frac{\lfloor 2^n x \rfloor}{2^n}$ for all $(x,n) \in \mathbb{R} \times \mathbb{N}$.
Establish $$\forall (x,n) \in \mathbb{R} \times \mathbb{N}, \quad \pi_n(x) \leqslant x < \pi_n(x) + \frac{1}{2^n}.$$

Let $z \in \mathbb { P } _ { n }$ and let $p$ be a prime number not dividing $n$.
(a) Let $F , G \in \mathbb { Z } [ X ]$. Show that there exists $H \in \mathbb { Z } [ X ]$ such that $$( F + G ) ^ { p } = F ^ { p } + G ^ { p } + p H$$ (b) Show that $\Pi _ { z } \in \mathbb { Z } [ X ]$ and deduce the existence of a polynomial $F \in \mathbb { Z } [ X ]$ such that $$\Pi _ { z } \left( X ^ { p } \right) = \Pi _ { z } ( X ) ^ { p } + p F ( X )$$ (c) Show that $\frac { \Pi _ { z } \left( z ^ { p } \right) } { p }$ is an algebraic integer.

We have $\pi_n(x) = \frac{\lfloor 2^n x \rfloor}{2^n}$ and $d_{n+1}(x) = 2^{n+1}(\pi_{n+1}(x) - \pi_n(x))$ for all $(x,n) \in \mathbb{R} \times \mathbb{N}$.
Justify $$\forall x \in [0,1[, \forall k \in \mathbb{N}, \quad \pi_k(x) = \sum_{j=1}^{k} \frac{d_j(x)}{2^j}.$$

We have $d_{n+1}(x) = 2^{n+1}(\pi_{n+1}(x) - \pi_n(x))$ for all $(x,n) \in \mathbb{R} \times \mathbb{N}$.
Establish $$\forall (x,j) \in \mathbb{R} \times \mathbb{N}^{\star}, \quad d_j(x) \in \{0,1\}.$$

We have $D_n = \left\{\sum_{j=1}^{n} \frac{x_j}{2^j}, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n\right\}$ and $\pi_n(x) = \frac{\lfloor 2^n x \rfloor}{2^n}$.
Let $n \in \mathbb{N}^{\star}$. Justify $x \in D_n \Longleftrightarrow 2^n x \in \llbracket 0, 2^n - 1 \rrbracket$.

Let $n \in \mathbb{N}^{\star}$. Show that the application $$\Psi_n : \begin{gathered} \{0,1\}^n \rightarrow D_n \\ (x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} \frac{x_j}{2^j} \end{gathered}$$ is bijective.

We keep the notations from Parts II and III. We denote $e _ { k } = x _ { k } - \tilde { x }$ and $e _ { 0 } = x _ { 0 } - \tilde { x }$. We recall that $I _ { N }$ is the identity matrix of order $N$, and $\| \cdot \|$ denotes the matrix norm defined in question 2.
Show that $$\left\| e _ { k } \right\| _ { A } \leq \left\| e _ { 0 } \right\| _ { A } \min \left\{ \left\| I _ { N } + A Q ( A ) \right\| \mid Q \in \mathbb { R } [ X ] , \operatorname { deg } ( Q ) \leq k - 1 \right\}$$ (One may use the properties of $A ^ { 1 / 2 }$ demonstrated in question 6.)

Let $n \in \mathbb{N}^{\star}$ and $x = \sum_{j=1}^{n} \frac{x_j}{2^j}$ with $(x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n$. Show $$\forall k \in \mathbb{N}, \quad \pi_k(x) = \sum_{j=1}^{\min(n,k)} \frac{x_j}{2^j}.$$

Let $k$ be a non-negative integer. We define the function $f _ { k }$ from the interval $[ - 1,1 ]$ to itself by $f _ { k } ( x ) = \cos ( k \arccos x )$, and $T_k$ is the polynomial of degree $k$ that identifies with $f_k$ on $[-1,1]$. We recall that $A \in \mathcal{S}_N^+(\mathbb{R})$ is not proportional to the identity, $\lambda_1$ is the smallest eigenvalue of $A$, $\lambda_N$ is the largest eigenvalue of $A$, and $$\Lambda _ { k } = \{ Q \in \mathbb { R } [ X ] \mid \operatorname { deg } ( Q ) \leq k , Q ( 0 ) = 1 \}$$
We set $\omega _ { k } = \frac { 1 } { T _ { k } \left( - \frac { \lambda _ { N } + \lambda _ { 1 } } { \lambda _ { N } - \lambda _ { 1 } } \right) }$. Show that $\omega _ { k }$ is well defined, that the polynomial $$Q _ { k } ( X ) = \omega _ { k } T _ { k } \left( \frac { 2 X - \lambda _ { 1 } - \lambda _ { N } } { \lambda _ { N } - \lambda _ { 1 } } \right)$$ is an element of $\Lambda _ { k }$, and that the maximum of $| Q _ { k } ( t ) |$ on $\left[ \lambda _ { 1 } , \lambda _ { N } \right]$ is $\left| \omega _ { k } \right|$.

Show that if the union of a finite number of vector subspaces $F_1, \ldots, F_r$ of $E$ is a vector subspace, then one of the vector subspaces $F_i$ contains all the others.

We keep the notations from the previous parts. In particular, we still denote by $x _ { k }$ the minimizer of $J$ on $x _ { 0 } + H _ { k }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$
Show that there exists a family $\left( p _ { 0 } , \ldots , p _ { m - 1 } \right)$ of vectors in $\mathbb { R } ^ { N }$ such that
(i) For all $k \in \{ 1 , \ldots , m \}$, the family $( p _ { 0 } , \ldots , p _ { k - 1 } )$ is a basis of $H _ { k }$.
(ii) The family is orthogonal with respect to the inner product associated with $A$, that is $$\forall i , j \in \{ 0 , \ldots , m - 1 \} \quad i \neq j \Rightarrow \left\langle A p _ { i } , p _ { j } \right\rangle = 0$$

We keep the notations from the previous parts. In particular, we still denote by $x _ { k }$ the minimizer of $J$ on $x _ { 0 } + H _ { k }$.
Assume that a family $\left( p _ { 0 } , \ldots , p _ { m - 1 } \right)$ of vectors satisfying the properties of question 24 is known. Show that $x _ { k + 1 } - x _ { k }$ is then collinear with $p _ { k }$ for all integer $k \in \{ 0 , \ldots , m - 1 \}$.

We are given $x _ { 0 } \in \mathbb { R } ^ { N }$. We consider the finite real sequences $\left( \alpha _ { k } \right)$ and $\left( \beta _ { k } \right)$, as well as the finite sequences $\left( \tilde { x } _ { k } \right) , \left( \tilde { r } _ { k } \right)$ and $\left( \tilde { p } _ { k } \right)$ of elements of $\mathbb { R } ^ { N }$, constructed according to the following recurrence relations, for $k \in \{ 0 , \ldots , m - 1 \}$, $$\begin{aligned} \alpha _ { k } & = \frac { \left\| \tilde { r } _ { k } \right\| ^ { 2 } } { \left\langle A \tilde { p } _ { k } , \tilde { p } _ { k } \right\rangle } \\ \tilde { x } _ { k + 1 } & = \tilde { x } _ { k } + \alpha _ { k } \tilde { p } _ { k } \\ \tilde { r } _ { k + 1 } & = \tilde { r } _ { k } - \alpha _ { k } A \tilde { p } _ { k } \\ \beta _ { k } & = \frac { \left\| \tilde { r } _ { k + 1 } \right\| ^ { 2 } } { \left\| \tilde { r } _ { k } \right\| ^ { 2 } } \\ \tilde { p } _ { k + 1 } & = \tilde { r } _ { k + 1 } + \beta _ { k } \tilde { p } _ { k } \end{aligned}$$ with $\tilde { x } _ { 0 } = x _ { 0 } , \tilde { r } _ { 0 } = b - A x _ { 0 }$ and $\tilde { p } _ { 0 } = \tilde { r } _ { 0 }$.
Show that the following properties are satisfied:
(i) For all $k \in \{ 0 , \ldots , m - 1 \}$, for all $i \in \{ 0 , \ldots , k - 1 \}$, we have $$\left\langle \tilde { r } _ { i } , \tilde { r } _ { k } \right\rangle = 0 , \left\langle \tilde { p } _ { i } , \tilde { r } _ { k } \right\rangle = 0 , \left\langle \tilde { p } _ { i } , A \tilde { p } _ { k } \right\rangle = 0$$
(ii) For all $k \in \{ 0 , \ldots , m \} , \tilde { x } _ { k }$ is identified with $x _ { k }$, the minimizer of $J$ on $x _ { 0 } + H _ { k }$ defined in question 13.
(iii) For all $k \in \{ 0 , \ldots , m \} , \tilde { r } _ { k }$ is identified with $r _ { k } = b - A x _ { k }$.
(iv) The family $\left( \tilde { p } _ { 0 } , \ldots , \tilde { p } _ { k } \right)$ is a basis of $H _ { k + 1 }$, for all $k \in \{ 0 , \ldots , m - 1 \}$.

We denote by $d$ the degree of $\pi_f$, $E_1 = \operatorname{Vect}(e_1, e_2, \ldots, e_d)$ where $e_i = f^{i-1}(x_1)$, and $\Phi$ is the $d$-th coordinate form. Let $\Psi$ be the linear map from $E$ to $\mathbb{K}^d$ defined, for all $x \in E$, by
$$\Psi(x) = \left(\Phi\left(f^i(x)\right)\right)_{0 \leqslant i \leqslant d-1} = \left(\Phi(x), \Phi(f(x)) \ldots, \Phi\left(f^{d-1}(x)\right)\right)$$
Show that $\Psi$ induces an isomorphism between $E_1$ and $\mathbb{K}^d$.

We denote by $d$ the degree of $\pi_f$, $E_1 = \operatorname{Vect}(e_1, e_2, \ldots, e_d)$ where $e_i = f^{i-1}(x_1)$, $F = \{x \in E \mid \forall i \in \mathbb{N}, \Phi(f^i(x)) = 0\}$, and $\Psi$ is the linear map from $E$ to $\mathbb{K}^d$ defined by $\Psi(x) = \left(\Phi(f^i(x))\right)_{0 \leqslant i \leqslant d-1}$.
Show that $E = E_1 \oplus F$.

Deduce that there exist $r$ vector subspaces of $E$, denoted $E_1, \ldots, E_r$, all stable under $f$ such that:

• $E = E_1 \oplus \cdots \oplus E_r$;
• for all $1 \leqslant i \leqslant r$, the endomorphism $\psi_i$ induced by $f$ on the vector subspace $E_i$ is cyclic;
• if we denote by $P_i$ the minimal polynomial of $\psi_i$, then $P_{i+1}$ divides $P_i$ for all integer $i$ such that $1 \leqslant i \leqslant r-1$.