Let $a \in E$ and let $U$ be an open set of $E$ containing $a$. Let $f : U \rightarrow E$ be an application of class $\mathscr{C}^1$ on $U$ such that $df(a) = \operatorname{Id}_E$. We fix a real number $r > 0$ such that $\overline{B(a,r)} \subset U$ and $$\forall x_1, x_2 \in \overline{B(a,r)}, \quad \left\|f(x_1) - f(x_2)\right\| \geqslant \frac{1}{2} \left\|x_1 - x_2\right\|.$$ We denote by $W = \left\{y \in E \left\lvert\, \|y - f(a)\| < \frac{r}{4}\right.\right\}$ and $V = f^{-1}(W) \cap B(a,r)$.
Show that $$f_{\mid V} : \begin{array}{lcc} V & \longrightarrow & W \\ x & \longmapsto & f(x) \end{array}$$ is a continuous bijection from $V$ to $W$ whose inverse is a continuous function on $W$.

For all $g = (\tau, R) \in \operatorname{Dep}(\mathbb{R}^{d})$, we denote by $\phi_{g} : \mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ the map defined by $\phi_{g}(x) = Rx + \tau$. Let $g \in \operatorname{Dep}(\mathbb{R}^{d})$.

• [(a)] Show that $\phi_{g}$ is bijective. We denote by $\phi_{g}^{-1}$ its inverse map.
• [(b)] Show that there exists a unique $g^{\prime} \in \operatorname{Dep}(\mathbb{R}^{d})$, which we will express in terms of $g$, such that $\phi_{g^{\prime}} = \phi_{g}^{-1}$. We denote $g^{\prime} = g^{-1}$.
• [(c)] Verify that $ge = eg = g$ and then that $gg^{-1} = g^{-1}g = e$.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. We now assume that $\lim _ { n \rightarrow + \infty } \left( n ^ { \omega _ { 0 } } p _ { n } \right) = + \infty$. Justify that for all natural integers $q$ and $r$ satisfying $1 \leq q \leq r$, we have : $$\binom { r } { q } r ^ { - q } \geq \frac { 1 } { q ! } \left( 1 - \frac { q - 1 } { q } \right) ^ { q }$$ and deduce that for $k \in \llbracket 1 , s _ { 0 } \rrbracket$, we have $\Sigma _ { k } = \mathrm { o} \left( \left( \mathbf { E } \left( X _ { n } ^ { 0 } \right) \right)^{ 2 } \right)$ when $n$ tends to $+ \infty$.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. We now assume that $\lim _ { n \rightarrow + \infty } \left( n ^ { \omega _ { 0 } } p _ { n } \right) = + \infty$. Show that $\lim _ { n \rightarrow + \infty } \frac { \mathbf { V } \left( X _ { n } ^ { 0 } \right) } { \left( \mathbf { E } \left( X _ { n } ^ { 0 } \right) \right) ^ { 2 } } = 0$ where $\mathbf { V } \left( X _ { n } ^ { 0 } \right)$ denotes the variance of $X _ { n } ^ { 0 }$.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$, and let $$\omega _ { 0 } = \min _ { \substack { H \subset G _ { 0 } \\ a _ { H } \geq 1 } } \frac { s _ { H } } { a _ { H } }$$ Show that the sequence $\left( k ^ { - \omega _ { 0 } } \right) _ { k \geq 2 }$ is a threshold function for the property $\mathcal { P } _ { n }$ : ``contain a copy of $G_0$''.

Recover the result of question 16 and determine a threshold function for the property ``containing a copy of the star with $d$ branches'' with $d$ a fixed integer greater than 1.

Let $V$ be a finite-dimensional vector space, let $h$ be an endomorphism of $V$ and let $W$ be a subspace stable by $h$. We denote by $h_W$ the endomorphism of $W$ induced by $h$, that is $h_W : W \rightarrow W$, $v \mapsto h(v)$. Prove that if $h$ is diagonalizable, then $h_W$ is also diagonalizable.

For a square matrix $M$ and a nonzero natural integer $k$, we denote $$\delta_k(M) = -\operatorname{dim}\ker M^{k-1} + 2\operatorname{dim}\ker M^k - \operatorname{dim}\ker M^{k+1}.$$ Prove that if two square matrices $M$ and $M'$ are similar, then $\delta_k(M) = \delta_k(M')$ for all $k$.

Let $r$ be a nonzero natural integer. Verify that for all nonzero integer $k$, $\delta_k(J_r)$ equals 1 if $k = r$ and 0 otherwise.

Let $M_1$ and $M_2$ be two square matrices and let $M = \operatorname{diag}(M_1, M_2)$. Prove the relation $\operatorname{dim}\ker M = \operatorname{dim}\ker M_1 + \operatorname{dim}\ker M_2$ and then that for all nonzero integer $k$, $$\delta_k(M) = \delta_k(M_1) + \delta_k(M_2).$$ One may use without proof the fact that all these relations extend to a block diagonal matrix $\operatorname{diag}(M_1, \ldots, M_s)$.

Deduce that $$\forall x \in \Lambda_n, \quad n\left(-h - \beta\frac{\lambda_{\max}}{2}\right) \leqslant H_n(h,x) \leqslant n\left(h - \beta\frac{\lambda_{\min}}{2}\right).$$

Let $F$ be an element of $\mathbb{C}[X^{\pm 1}]$. Prove that $\widehat{\xi}(\Pi(F)) = \widehat{\xi}(F)$.

Let $P$ be a polynomial and let $F$ be an element of $\mathcal{D}$. Prove that $P(\xi)(F) = \Pi(PF)$.

Let $\left( X _ { i } \right) _ { i \in [ 1 , n ] }$ be a sequence of independent random variables all following a Rademacher distribution. Show that $$\forall t \in \mathbf { R } , \quad \operatorname { ch } ( t ) \leq \mathrm { e } ^ { t ^ { 2 } / 2 }$$

Problem 1: calculation of an integral
For $x \geqslant 0$ we define $$f ( x ) = \int _ { 0 } ^ { \infty } \frac { e ^ { - t x } } { 1 + t ^ { 2 } } \mathrm {~d} t \quad \text { and } \quad g ( x ) = \int _ { 0 } ^ { \infty } \frac { \sin t } { t + x } \mathrm {~d} t$$
Using the expression of $g$ obtained in question 2.b., show that $g$ is continuous at 0.

Let $n$ be a natural integer. Prove that $\xi^n$ is surjective and give a basis of the kernel of $\xi^n$.

Let $r$ be a nonzero natural integer. Prove that the smallest vector subspace $\mathcal{D}_r$ of $\mathcal{D}$ containing $X^{-r}$ and stable by $\xi$ has as basis $(X^{k-r})_{0 \leqslant k \leqslant r-1}$. Write the matrix of the endomorphism $\xi_{\mathcal{D}_r}$ induced by $\xi$ on $\mathcal{D}_r$ in this basis.

6. We assume that $f$ is absolutely monotone on $[ a , b ]$. Show that, for every polynomial $P \in \mathbb { R } [ X ]$ split in $] a , b [$, the function $Q ( f , P )$ is absolutely monotone on $[ a , b ]$.

Second Part

Let $I = [ - 1,1 ]$. We fix an integer $n \geqslant 2$ for this entire part. Let $f : I \rightarrow ] 0 , + \infty [$ be a continuous function. We recall that we define an inner product on $\mathbb { R } _ { n } [ X ]$ by setting, for all $P , Q \in \mathbb { R } [ X ]$,
$$\langle P , Q \rangle = \int _ { - 1 } ^ { 1 } P ( x ) Q ( x ) f ( x ) d x$$
Let $D \in \mathbb { R } _ { n } [ X ]$ be a polynomial having $n$ distinct real roots $r _ { 1 } > \cdots > r _ { n }$ in $I$. We further assume that $D \in \mathbb { R } _ { n - 1 } [ X ] ^ { \perp }$.
7a. Show that there exist real numbers $\lambda _ { 1 } , \ldots , \lambda _ { n }$ such that, for all $P \in \mathbb { R } _ { n - 1 } [ X ]$,
$$\int _ { - 1 } ^ { 1 } P ( x ) f ( x ) d x = \sum _ { i = 1 } ^ { n } \lambda _ { i } P \left( r _ { i } \right)$$
7b. Show that if $P \in \mathbb { R } _ { 2 n - 1 } [ X ]$, we have
$$\int _ { - 1 } ^ { 1 } P ( x ) f ( x ) d x = \sum _ { i = 1 } ^ { n } \lambda _ { i } P \left( r _ { i } \right)$$
Hint: one may consider the Euclidean division of $P$ by $D$. 7c. By evaluating equality 1 on the polynomial $\prod _ { \substack { 1 \leqslant j \leqslant n \\ j \neq i } } \left( X - r _ { j } \right) ^ { 2 }$, show that $\lambda _ { i } > 0$ for all $1 \leqslant i \leqslant n$. For $1 \leqslant j \leqslant n - 1$ and $t \in \mathbb { R }$, we set $f _ { j } ( t ) = \prod _ { i = 1 } ^ { j } \left( r _ { i } - t \right)$ as well as $f _ { 0 } ( t ) = 1$. If $0 \leqslant j \leqslant n - 1$ and $P , Q \in \mathbb { R } _ { n } [ X ]$, we set
$$\langle P , Q \rangle _ { j } = \left\langle P , Q f _ { j } \right\rangle$$
7d. Show that, for all $0 \leqslant j \leqslant n - 1 , \langle \cdot , \cdot \rangle _ { j }$ defines an inner product on $\mathbb { R } _ { n - j - 1 } [ X ]$. In questions 8. to 12. below, we fix a natural integer $0 \leqslant j \leqslant n - 1$.
8a. Show that there exists a unique family $q _ { 0 } , \ldots , q _ { n - j - 1 }$ of monic polynomials of $\mathbb { R } [ X ]$ such that $\operatorname { deg } \left( q _ { i } \right) = i$ for $0 \leqslant i \leqslant n - j - 1$ and such that for all $0 \leqslant i \neq i ^ { \prime } \leqslant n - j - 1$,
$$\left\langle q _ { i } , q _ { i ^ { \prime } } \right\rangle _ { j } = 0$$
8b. We set $q _ { n - j } = \prod _ { i = j + 1 } ^ { n } \left( X - r _ { i } \right)$. Show that $q _ { n - j }$ is the unique monic polynomial of degree $n - j$ satisfying, for all $0 \leqslant i \leqslant n - j - 1$,
$$\left\langle q _ { i } , q _ { n - j } \right\rangle _ { j } = 0$$
9a. Let $2 \leqslant i \leqslant n - j$. Show that there exist real numbers $a _ { i }$ and $b _ { i }$ such that
$$q _ { i } - X q _ { i - 1 } = a _ { i } q _ { i - 1 } + b _ { i } q _ { i - 2 }$$
9b. Show that
$$b _ { i } \left\langle q _ { i - 2 } , q _ { i - 2 } \right\rangle _ { j } = - \left\langle X q _ { i - 1 } , q _ { i - 2 } \right\rangle _ { j }$$
9c. Show that $b _ { i } < 0$.
10a. For $i \in \{ 0,1 \}$, show that the polynomial $q _ { i }$ has exactly $i$ roots in $\mathbb { R }$ (note that we do not require the roots to belong to the interval $I$ ).
10b. Show that, for all $1 \leqslant i \leqslant n - j$, the polynomial $q _ { i }$ has exactly $i$ distinct real roots, these roots are simple and if $x _ { 1 } < x _ { 2 }$ are two consecutive roots of $q _ { i }$, there exists a unique root of $q _ { i - 1 }$ in the interval $] x _ { 1 } , x _ { 2 } [$.
10c. Deduce that, for all $0 \leqslant i \leqslant n - j - 1$, we have $q _ { i } \left( r _ { j + 1 } \right) > 0$. For $0 \leqslant i \leqslant n - j - 1$, there therefore exists a unique real number $\alpha _ { i }$ such that
$$q _ { i + 1 } \left( r _ { j + 1 } \right) + \alpha _ { i } q _ { i } \left( r _ { j + 1 } \right) = 0$$
We fix $0 \leqslant i \leqslant n - j - 1$ and we set
$$p _ { i } = \frac { q _ { i + 1 } + \alpha _ { i } q _ { i } } { X - r _ { j + 1 } }$$
We denote $c _ { 0 } , \ldots , c _ { i } \in \mathbb { R }$ the coordinates of $p _ { i }$ in the basis $\left( q _ { 0 } , \ldots , q _ { i } \right)$ of $\mathbb { R } _ { i } [ X ]$. 11a. Show that, for $0 \leqslant \ell \leqslant i$,
$$\left\langle q _ { i + 1 } + \alpha _ { i } q _ { i } , \frac { q _ { \ell } - q _ { \ell } \left( r _ { j + 1 } \right) } { X - r _ { j + 1 } } \right\rangle _ { j } = 0$$
11b. Show that, for every integer $0 \leqslant \ell \leqslant i$, there exists a real $\gamma _ { \ell } > 0$ such that $c _ { \ell } = \gamma _ { \ell } c _ { 0 }$ and deduce that $c _ { \ell } > 0$.

6. We assume that $f$ is absolutely monotone on $[ a , b ]$. Show that, for every polynomial $P \in \mathbb { R } [ X ]$ split in $] a , b [$, the function $Q ( f , P )$ is absolutely monotone on $[ a , b ]$.

Second Part

Let $I = [ - 1,1 ]$. We fix an integer $n \geqslant 2$ for this entire part. Let $f : I \rightarrow ] 0 , + \infty [$ be a continuous function. We recall that we define an inner product on $\mathbb { R } _ { n } [ X ]$ by setting, for all $P , Q \in \mathbb { R } [ X ]$,
$$\langle P , Q \rangle = \int _ { - 1 } ^ { 1 } P ( x ) Q ( x ) f ( x ) d x$$
Let $D \in \mathbb { R } _ { n } [ X ]$ be a polynomial having $n$ distinct real roots $r _ { 1 } > \cdots > r _ { n }$ in $I$. We further assume that $D \in \mathbb { R } _ { n - 1 } [ X ] ^ { \perp }$.
Ya. Show that there exist real numbers $\lambda _ { 1 } , \ldots , \lambda _ { n }$ such that, for all $P \in \mathbb { R } _ { n - 1 } [ X ]$,
$$\int _ { - 1 } ^ { 1 } P ( x ) f ( x ) d x = \sum _ { i = 1 } ^ { n } \lambda _ { i } P \left( r _ { i } \right)$$
7b. Show that if $P \in \mathbb { R } _ { 2 n - 1 } [ X ]$, we have
$$\int _ { - 1 } ^ { 1 } P ( x ) f ( x ) d x = \sum _ { i = 1 } ^ { n } \lambda _ { i } P \left( r _ { i } \right)$$
Hint: one may consider the Euclidean division of $P$ by $D$. łc. By evaluating equality (1) on the polynomial $\prod _ { \substack { 1 \leqslant j \leqslant n \\ j \neq i } } \left( X - r _ { j } \right) ^ { 2 }$, show that $\lambda _ { i } > 0$ for all $1 \leqslant i \leqslant n$.
For $1 \leqslant j \leqslant n - 1$ and $t \in \mathbb { R }$, we set $f _ { j } ( t ) = \prod _ { i = 1 } ^ { j } \left( r _ { i } - t \right)$ as well as $f _ { 0 } ( t ) = 1$. If $0 \leqslant j \leqslant n - 1$ and $P , Q \in \mathbb { R } _ { n } [ X ]$, we set
$$\langle P , Q \rangle _ { j } = \left\langle P , Q f _ { j } \right\rangle .$$
7èd. Show that, for all $0 \leqslant j \leqslant n - 1 , \langle \cdot , \cdot \rangle _ { j }$ defines an inner product on $\mathbb { R } _ { n - j - 1 } [ X ]$./ In questions 8. to 12. below, we fix a natural integer $0 \leqslant j \leqslant n - 1$.

Verify that the set $$\mathcal{J} = \{P \in \mathbb{C}[X],\, P(u)(v) \in W\}$$ is an ideal of $\mathbb{C}[X]$.

Prove that there exists a natural integer $n$ such that $X^n \in \mathcal{J}$. Deduce that $\mathcal{J}$ is generated by the monomial $X^r$ for a suitable natural integer $r$ that we do not ask you to specify.

Let $W'$ be the subspace of $V$ defined by $$W' = \{P(u)(v) + w,\, P \in \mathbb{C}[X] \text{ and } w \in W\}.$$ Verify that $W'$ contains $W$ and $v$ and that it is stable by $u$.

We denote $G_v = \varphi(u^r(v))$. Prove that there exists an element $F_v$ of $\mathcal{D}$ such that $$G_v = \xi^r(F_v).$$

Let $P$ be a polynomial and let $w$ be an element of $W$. Prove that if $P(u)(v) = w$, then $P(\xi)(F_v) = \varphi(w)$.

Let $x$ be an element of $W'$. Let $P$ be a polynomial and let $w$ be an element of $W$ such that $x = P(u)(v) + w$. Prove that the element $\varphi'(x) = P(\xi)(F_v) + \varphi(w)$ depends only on $x$ and not on the choice of $P$ and $w$. Verify then that the application $\varphi'$ thus defined is an extension of $\varphi$ to $W'$ compatible with $u$ (it is not asked to verify that $\varphi'$ is linear, which we will admit).