We denote by $\lambda _ { 1 }$ (respectively $\lambda _ { N }$) the smallest (respectively largest) eigenvalue of $A$, and we define $$\Lambda _ { k } = \{ Q \in \mathbb { R } [ X ] \mid \operatorname { deg } ( Q ) \leq k , Q ( 0 ) = 1 \}$$
Show that $$\left\| e _ { k } \right\| _ { A } \leq \left\| e _ { 0 } \right\| _ { A } \min _ { Q \in \Lambda _ { k } } \max _ { t \in \left[ \lambda _ { 1 } , \lambda _ { N } \right] } | Q ( t ) |$$

In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), the map $\omega \mapsto \sigma(\omega)$ is bijective from $\Omega_{n}$ to $S_{n}$ and induces a bijection between the event $(X_{n} = m)$ and the set of permutations of $S_{n}$ having $m-1$ ascents. We denote by $A_{n,m}$ the number of elements of $S_{n}$ with $m$ ascents.
Let $m \in \llbracket 1, n \rrbracket$. Determine, for any integer $n \geqslant 2$ and any $m \in \llbracket 0, n-1 \rrbracket$, the number $A_{n,m}$ of permutations of $S_{n}$ having $m$ ascents.

For $j \in \mathbb{N}$, we denote by $Y_{n,j}$ the set of partitions whose first term $\alpha_1$ is less than or equal to $j$ and by $y_{n,j}$ the cardinality of $Y_{n,j}$; we set $y_{0,0} = 1$.
We propose to show that, if $2 \leqslant j \leqslant n$, then $y_{n,j} = y_{n,j-1} + y_{n-j,\min(j,n-j)}$.
For $j < n$, verify that $y_{n,j} = y_{n,j-1} + y_{n-j,j}$. Conclude.

For $j \in \mathbb{N}$, we denote by $Y_{n,j}$ the set of partitions whose first term $\alpha_1$ is less than or equal to $j$ and by $y_{n,j}$ the cardinality of $Y_{n,j}$; we set $y_{0,0} = 1$.
Write a Python function that takes as argument an integer $n \geqslant 1$ and returns $y_{n,n}$.

Compare the result of question 48 (the value of $y_{n,n}$, the number of partitions of $n$) to that of question 40 (the maximum cardinality of a set of pairwise non-similar nilpotent matrices of size $n$).

We consider a function $f : \mathbb{R}^n \rightarrow \mathbb{R}$. a. For all $x, y \in \mathbb{R}^n$, let $\varphi_{x,y} : \mathbb{R} \rightarrow \mathbb{R}$ be the function defined by $\varphi_{x,y}(t) = f(x + t(y-x))$ for all $t \in \mathbb{R}$. Show that $f$ is convex if and only if for all $x, y \in \mathbb{R}^n$, $\varphi_{x,y}$ is convex. b. Suppose that $f$ is differentiable on $\mathbb{R}^n$. Show that for all $x, y \in \mathbb{R}^n$, the function $\varphi_{x,y}$ is differentiable, and show that for all $t \in \mathbb{R}$, $\varphi_{x,y}^{\prime}(t) = \langle \nabla f(x + t(y-x)), y-x \rangle$. c. Deduce that if $f$ is differentiable on $\mathbb{R}^n$, then $f$ is convex if and only if for all $x, y \in \mathbb{R}^n$, $$f(y) \geqslant f(x) + \langle \nabla f(x), y-x \rangle.$$ d. Show that if $f : \mathbb{R}^n \rightarrow \mathbb{R}$ is differentiable on $\mathbb{R}^n$, then $f$ is convex if and only if for all $x, y \in \mathbb{R}^n$, $$\langle \nabla f(y) - \nabla f(x), y-x \rangle \geqslant 0.$$

Let $f : \mathbb{R}^n \rightarrow \mathbb{R}$ be a convex function differentiable on $\mathbb{R}^n$, and $x^{\star} \in \mathbb{R}^n$. Show that if $\nabla f(x^{\star}) = 0$ then $f$ admits a global minimum at $x^{\star}$.

We consider a real number $\alpha \in \mathbb{R}_+^{\star}$ and a function $f : \mathbb{R}^n \rightarrow \mathbb{R}$ differentiable on $\mathbb{R}^n$. Recall that $f$ is $\alpha$-convex if for all $x, y \in \mathbb{R}^n$, $$f(y) \geqslant f(x) + \langle \nabla f(x), y-x \rangle + \frac{\alpha}{2}\|y-x\|^2.$$ a. We consider the function $g_{\alpha} : \mathbb{R}^n \rightarrow \mathbb{R}$ defined by $g_{\alpha}(x) = f(x) - \frac{\alpha}{2}\|x\|^2$ for all $x \in \mathbb{R}^n$. Calculate $\nabla g_{\alpha}(x)$ for all $x \in \mathbb{R}^n$, and show that $f$ is $\alpha$-convex if and only if $g_{\alpha}$ is convex. b. Deduce that $f$ is $\alpha$-convex if and only if for all $x, y \in \mathbb{R}^n$, $$\langle \nabla f(y) - \nabla f(x), y-x \rangle \geqslant \alpha \|y-x\|^2.$$

Let $f : \mathbb{R}^n \rightarrow \mathbb{R}$ be a continuous and coercive function. Show that if $K$ is a non-empty closed set of $\mathbb{R}^n$, then there exists $x^{\star} \in K$ such that $f(x^{\star}) = \inf_{x \in K} f(x)$.

Let $f : \mathbb{R}^n \rightarrow \mathbb{R}$ be a function differentiable on $\mathbb{R}^n$ and $\alpha$-convex, where $\alpha \in \mathbb{R}_+^{\star}$. Show that if $K$ is a non-empty closed convex set of $\mathbb{R}^n$, then $f$ admits a unique minimum on $K$.

Let $C$ be a non-empty closed convex set of $\mathbb{R}^n$ and $x \in \mathbb{R}^n$. a. Show that there exists a unique point $P_C(x) \in C$ such that $\|P_C(x) - x\| = \inf_{y \in C} \|y - x\|$. b. Let $\bar{x} \in C$. Show that $\bar{x} = P_C(x)$ if and only if $$\langle x - \bar{x}, y - \bar{x} \rangle \leqslant 0 \text{ for all } y \in C.$$ Hint: one may consider the function $\psi_y : t \in \mathbb{R} \mapsto \|x - (\bar{x} + t(y - \bar{x}))\|^2$, where $y \in C$. c. Deduce that if $x, y \in \mathbb{R}^n$, then $\|P_C(y) - P_C(x)\| \leqslant \|y - x\|$.

Describe $\mathcal{A}_K(x)$ in the case where $x$ is in the interior of $K$.

Show that if $f : \mathbb{R}^n \rightarrow \mathbb{R}$ is differentiable at $x^{\star} \in K$ and admits a local minimum on $K$ at $x^{\star}$, then $$\forall h \in \mathcal{A}_K(x^{\star}), \quad \langle \nabla f(x^{\star}), h \rangle \geqslant 0.$$ What does this result express in the particular case where $x^{\star}$ is in the interior of $K$?

Throughout Part II, we consider a function $f : \mathbb{R}^n \rightarrow \mathbb{R}$ differentiable on $\mathbb{R}^n$ and $\alpha$-convex, where $\alpha \in \mathbb{R}_+^{\star}$. We set $$K = \left\{ x \in \mathbb{R}^n, g_1(x) \leqslant 0, \ldots, g_p(x) \leqslant 0 \right\}$$ where $p \in \mathbb{N}^{\star}$ and $g_1, \ldots, g_p$ are convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, differentiable on $\mathbb{R}^n$. We further assume that the set $K$ is non-empty. Show that there exists a unique element $x^{\star} \in K$ such that $f(x^{\star}) = \inf_{x \in K} f(x)$.

For all $k \in \mathbb{N}$, we introduce the function $f_k : \mathbb{R}^n \rightarrow \mathbb{R}$ defined by $$f_k(x) = f(x) + k\Psi(x) \text{ for all } x \in \mathbb{R}^n$$ where $\Psi : \mathbb{R}^n \rightarrow \mathbb{R}$ is the function defined by $\Psi(x) = \sum_{i=1}^{p} \max(0, g_i(x))^2$ for all $x \in \mathbb{R}^n$. For all $x \in \mathbb{R}^n$, calculate $\lim_{k \rightarrow \infty} f_k(x)$.

For all $k \in \mathbb{N}$, we introduce the function $f_k : \mathbb{R}^n \rightarrow \mathbb{R}$ defined by $$f_k(x) = f(x) + k\Psi(x) \text{ for all } x \in \mathbb{R}^n$$ where $\Psi : \mathbb{R}^n \rightarrow \mathbb{R}$ is the function defined by $\Psi(x) = \sum_{i=1}^{p} \max(0, g_i(x))^2$ for all $x \in \mathbb{R}^n$. Show that for all $k \in \mathbb{N}$, there exists a unique $x_k \in \mathbb{R}^n$ such that $f_k(x_k) = \inf_{x \in \mathbb{R}^n} f_k(x)$. Hint: one may begin by showing that if $g : \mathbb{R}^n \rightarrow \mathbb{R}$ is a convex function, and $h : \mathbb{R} \rightarrow \mathbb{R}$ is a convex increasing function, then $h \circ g$ is convex.

For all $k \in \mathbb{N}$, we introduce the function $f_k : \mathbb{R}^n \rightarrow \mathbb{R}$ defined by $$f_k(x) = f(x) + k\Psi(x) \text{ for all } x \in \mathbb{R}^n$$ where $\Psi : \mathbb{R}^n \rightarrow \mathbb{R}$ is the function defined by $\Psi(x) = \sum_{i=1}^{p} \max(0, g_i(x))^2$ for all $x \in \mathbb{R}^n$, and $x_k$ denotes the unique minimizer of $f_k$ on $\mathbb{R}^n$, and $x^\star$ the unique minimizer of $f$ on $K$. Show that for all $k \in \mathbb{N}$, $f(x_k) \leqslant f(x^{\star})$.

For all $k \in \mathbb{N}$, we introduce the function $f_k : \mathbb{R}^n \rightarrow \mathbb{R}$ defined by $$f_k(x) = f(x) + k\Psi(x) \text{ for all } x \in \mathbb{R}^n$$ where $\Psi : \mathbb{R}^n \rightarrow \mathbb{R}$ is the function defined by $\Psi(x) = \sum_{i=1}^{p} \max(0, g_i(x))^2$ for all $x \in \mathbb{R}^n$, and $x_k$ denotes the unique minimizer of $f_k$ on $\mathbb{R}^n$, and $x^\star$ the unique minimizer of $f$ on $K$. We consider a subsequence $(x_{\varphi(k)})_{k \in \mathbb{N}}$ of $(x_k)_{k \in \mathbb{N}}$ that converges to $\bar{x} \in \mathbb{R}^n$. a. Show that $\bar{x} \in K$. b. Deduce that $\bar{x} = x^{\star}$.

For all $k \in \mathbb{N}$, we introduce the function $f_k : \mathbb{R}^n \rightarrow \mathbb{R}$ defined by $$f_k(x) = f(x) + k\Psi(x) \text{ for all } x \in \mathbb{R}^n$$ where $\Psi : \mathbb{R}^n \rightarrow \mathbb{R}$ is the function defined by $\Psi(x) = \sum_{i=1}^{p} \max(0, g_i(x))^2$ for all $x \in \mathbb{R}^n$, and $x_k$ denotes the unique minimizer of $f_k$ on $\mathbb{R}^n$, and $x^\star$ the unique minimizer of $f$ on $K$. Deduce that the sequence $(x_k)_{k \in \mathbb{N}}$ converges to $x^{\star}$.

For all $k \in \mathbb{N}$, we introduce the function $f_k : \mathbb{R}^n \rightarrow \mathbb{R}$ defined by $$f_k(x) = f(x) + k\Psi(x) \text{ for all } x \in \mathbb{R}^n$$ where $\Psi : \mathbb{R}^n \rightarrow \mathbb{R}$ is the function defined by $\Psi(x) = \sum_{i=1}^{p} \max(0, g_i(x))^2$ for all $x \in \mathbb{R}^n$, and $x_k$ denotes the unique minimizer of $f_k$ on $\mathbb{R}^n$, and $x^\star$ the unique minimizer of $f$ on $K$. Show that the sequence $(f_k(x_k))_{k \in \mathbb{N}}$ converges to $f(x^{\star})$.

Let $m \in \mathbb{N}^{\star}$ and $(u_1, \ldots, u_m)$ be a family of vectors of $\mathbb{R}^n$. We denote $$C = \left\{ \sum_{i=1}^{m} \mu_i u_i, \mu_i \geqslant 0 \; \forall i \in \llbracket 1, m \rrbracket \right\}.$$ The purpose of this question is to show that $C$ is a closed convex set of $\mathbb{R}^n$. a. Show that $C$ is convex. b. Show that if $(u_1, \ldots, u_m)$ is a free family, then $C$ is closed. c. For all $I \subset \llbracket 1, m \rrbracket$, we set $C_I = \left\{ \sum_{i \in I} \mu_i u_i, \mu_i \geqslant 0 \; \forall i \in I \right\}$. Show that $$C = \bigcup_{I} C_I,$$ where the union is taken over the sets $I \subset \llbracket 1, m \rrbracket$ such that $(u_i)_{i \in I}$ is a free family. Deduce that $C$ is closed.

Let $m \in \mathbb{N}^{\star}$ and $(u_1, \ldots, u_m)$ be a family of vectors of $\mathbb{R}^n$. We denote $$C = \left\{ \sum_{i=1}^{m} \mu_i u_i, \mu_i \geqslant 0 \; \forall i \in \llbracket 1, m \rrbracket \right\}.$$ We consider a vector $v \in \mathbb{R}^n \setminus C$. a. Show that $\langle P_C(v), P_C(v) - v \rangle = 0$. b. We set $w = P_C(v) - v$. Show that $\langle v, w \rangle < 0$ and $\langle u_i, w \rangle \geqslant 0$ for all $i \in \llbracket 1, m \rrbracket$.

Let $m \in \mathbb{N}^{\star}$ and $(u_1, \ldots, u_m)$ be a family of vectors of $\mathbb{R}^n$. We denote $$C = \left\{ \sum_{i=1}^{m} \mu_i u_i, \mu_i \geqslant 0 \; \forall i \in \llbracket 1, m \rrbracket \right\}.$$ Lemma 1 states: If $v \in \mathbb{R}^n$, then one and only one of the following two assertions is verified: (i) $v \in C$, (ii) there exists $w \in \mathbb{R}^n$ such that $\langle v, w \rangle < 0$ and $\langle u_i, w \rangle \geqslant 0$ for all $i \in \llbracket 1, m \rrbracket$. Conclude the proof of Lemma 1.

Let $p \in \llbracket 1, n \rrbracket$. We assume that $f, g_1, \ldots, g_p$ are differentiable functions from $\mathbb{R}^n$ to $\mathbb{R}$, that $f$ is $\alpha$-convex for some $\alpha \in \mathbb{R}_+^{\star}$, and that the functions $g_1, \ldots, g_p$ are convex. We further assume that $$K = \left\{ x \in \mathbb{R}^n, g_1(x) \leqslant 0, \ldots, g_p(x) \leqslant 0 \right\}$$ is non-empty. We denote $g(x) = \begin{pmatrix} g_1(x) \\ \vdots \\ g_p(x) \end{pmatrix}$ for all $x \in \mathbb{R}^n$. We introduce the function $\mathcal{L} : \mathbb{R}^n \times \mathbb{R}_+^p \rightarrow \mathbb{R}$ defined by $$\mathcal{L}(x, \mu) = f(x) + \sum_{i=1}^{p} \mu_i g_i(x)$$ for all $x \in \mathbb{R}^n$ and all $\mu = (\mu_1, \ldots, \mu_p) \in \mathbb{R}_+^p$. For all $\mu \in \mathbb{R}_+^p$, we denote $G(\mu) := \inf_{x \in \mathbb{R}^n} \mathcal{L}(x, \mu) = \mathcal{L}(x_\mu, \mu)$. (Uzawa's Theorem). Let $A \in \mathcal{M}_{p,n}(\mathbb{R})$ be a matrix of rank $p$ and $b \in \mathbb{R}^p$. We assume that the function $g$ is of the form $$g : x \mapsto Ax + b.$$ a. Show that for all $\mu \in \mathbb{R}_+^p$, $\nabla f(x_\mu) = -{}^t A \mu$, and deduce that the function $\mu \mapsto x_\mu$ is continuous on $\mathbb{R}_+^p$. b. Show that $(P)$ admits a unique solution $x^{\star} \in K$, and that $(Q)$ admits a unique solution $\mu^{\star} \in \mathbb{R}_+^p$. Let $\rho > 0$. We define the sequence $(\mu^k)_{k \in \mathbb{N}}$ by recursion as follows:

• we fix $\mu^0 \in \mathbb{R}_+^p$,
• for all $k \in \mathbb{N}$, we set $\mu^{k+1} = P_{\mathbb{R}_+^p}\left(\mu^k + \rho g(x_{\mu^k})\right)$,

where $P_{\mathbb{R}_+^p} : \mathbb{R}^p \rightarrow \mathbb{R}_+^p$ denotes the projection onto the closed convex set $\mathbb{R}_+^p$ of $\mathbb{R}^p$. c. Show that $\mu^{\star} = P_{\mathbb{R}_+^p}\left(\mu^{\star} + \rho g(x_{\mu^{\star}})\right)$. We now assume that $\|Ax\| \leqslant \sqrt{\frac{\alpha}{\rho}} \|x\|$ for all $x \in \mathbb{R}^n$. d. Show that the sequence $(x_{\mu^k})_{k \in \mathbb{N}}$ converges to $x^{\star}$. e. Show that the sequence $(\mu^k)_{k \in \mathbb{N}}$ converges to $\mu^{\star}$.

1. a. Verify that the relative extrema of functions in $S$ are strict. b. Let $f \in S$. Show that the restriction of $f$ to the closure of each component of $\mathbb{R} \backslash E(f)$ is strictly monotone. Deduce that if $x \in E(f) \backslash \{\operatorname{Max} E(f)\}$ is a relative maximum (resp. minimum), the smallest element $y$ of $E(f)$ satisfying $y > x$ is a relative minimum (resp. maximum). c. Let $f \in S_n$ with $n \geq 2$. We set $\mathscr{E}(f) = f(E(f))$. Let $\sigma_f$ be the element of $\Sigma_n$ defined by $$\sigma_f = \beta_{\mathscr{E}(f)} \circ f \circ \beta_{E(f)}^{-1}$$ Show that $\sigma_f \in \operatorname{MD}(n) \cup \operatorname{DM}(n)$.