grandes-ecoles

Q1a Invariant lines and eigenvalues and vectors Diagonalize a matrix explicitly View

Let $n$ be a natural integer with $n \geqslant 2$. For any real number $x$, we consider the following matrix in $\mathscr{M}_{n}(\mathbb{R})$ $$M_{x} = \left(\begin{array}{ccccc} x & 1 & \cdots & 1 & 1 \\ 1 & x & \cdots & 1 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & \cdots & x & 1 \\ 1 & 1 & \cdots & 1 & x \end{array}\right)$$ Show that the matrix $-M_{0}$ is diagonalizable and determine its eigenvalues and eigenspaces.

Q1b Invariant lines and eigenvalues and vectors Determinant and Rank Computation View

Let $n$ be a natural integer with $n \geqslant 2$. For any real number $x$, we consider the following matrix in $\mathscr{M}_{n}(\mathbb{R})$ $$M_{x} = \left(\begin{array}{ccccc} x & 1 & \cdots & 1 & 1 \\ 1 & x & \cdots & 1 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & \cdots & x & 1 \\ 1 & 1 & \cdots & 1 & x \end{array}\right)$$ Deduce that for all $x \in \mathbb{R}$, we have $$\sum_{\sigma \in \mathfrak{S}_{n}} \varepsilon(\sigma) x^{\nu(\sigma)} = (x-1)^{n-1}(x+n-1)$$

Q2 Proof Combinatorial Structures on Permutation Matrices/Groups View

Calculate $$\sum_{\sigma \in \mathfrak{S}_{n}} \varepsilon(\sigma), \quad \sum_{\sigma \in \mathfrak{S}_{n}} \varepsilon(\sigma) \nu(\sigma) \quad \text{and} \quad \sum_{\sigma \in \mathfrak{S}_{n}} \frac{\varepsilon(\sigma)}{\nu(\sigma)+1}.$$

Q3 Permutations & Arrangements Combinatorial Structures on Permutation Matrices/Groups View

Establish that $$\operatorname{Card}\left\{\sigma \in \mathfrak{S}_{n} : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{S}_{n} : \varepsilon(\sigma) = -1\right\}$$ and deduce the probability that a permutation of $\mathfrak{S}_{n}$ drawn uniformly at random has a prescribed signature.

Q4 Permutations & Arrangements Combinatorial Structures on Permutation Matrices/Groups View

For $\sigma \in \mathfrak{S}_{n}$, specify the condition on $\nu(\sigma)$ for which $\sigma \in \mathfrak{D}_{n}$. Deduce that $$\operatorname{Card}\left\{\sigma \in \mathfrak{D}_{n} : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{D}_{n} : \varepsilon(\sigma) = -1\right\} + (-1)^{n-1}(n-1).$$

Q5a Binomial Theorem (positive integer n) Linear Transformation and Endomorphism Properties View

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Justify that the families $\left(1, X, \ldots, X^{m}\right)$ and $\left(1, (X-1), \ldots, (X-1)^{m}\right)$ are bases of $\mathbb{R}_{m}[X]$.

Q5b Matrices Linear Transformation and Endomorphism Properties View

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Show that the transpose of $M$ is the matrix of the linear map identity $$\begin{array}{ccc} \mathbb{R}_{m}[X] & \longrightarrow & \mathbb{R}_{m}[X] \\ P & \longmapsto & P \end{array}$$ in the bases $\left(1, X, \ldots, X^{m}\right)$ at the start and $\left(1, (X-1), \ldots, (X-1)^{m}\right)$ at the end.

Q5c Matrices Linear System and Inverse Existence View

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Establish that $M$ is invertible and explicitly determine its inverse.

Q5d Matrices Matrix Entry and Coefficient Identities View

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Deduce that for all $\left(u_{0}, \ldots, u_{m}\right), \left(v_{0}, \ldots, v_{m}\right) \in \mathbb{R}^{m+1}$, $$\text{if} \quad \forall k \leqslant m, \quad u_{k} = \sum_{\ell=0}^{k} \binom{k}{\ell} v_{\ell}, \quad \text{then} \quad \forall k \leqslant m, \quad v_{k} = \sum_{\ell=0}^{k} (-1)^{k-\ell} \binom{k}{\ell} u_{\ell}$$

Q6 Proof by induction Evaluation of a Finite or Infinite Sum View

Show that for any non-zero natural integer $n$, $$D_{n} = n! \sum_{k=0}^{n} \frac{(-1)^{k}}{k!}$$

Q7a Discrete Probability Distributions Proof of Distributional Properties or Symmetry View

For $n$ a natural integer greater than or equal to 2, we consider the probability space $(\mathfrak{D}_{n}, \mathscr{P}(\mathfrak{D}_{n}))$ equipped with the uniform probability. We define a random variable $Y_{n}$ by $Y_{n}(\sigma) = \varepsilon(\sigma)$.
Explicitly state the distribution of $Y_{n}$.

Q7b Discrete Probability Distributions Limit and Convergence of Probabilistic Quantities View

For $n$ a natural integer greater than or equal to 2, we consider the probability space $(\mathfrak{D}_{n}, \mathscr{P}(\mathfrak{D}_{n}))$ equipped with the uniform probability. We define a random variable $Y_{n}$ by $Y_{n}(\sigma) = \varepsilon(\sigma)$.
Calculate, for all $\varepsilon \in \{-1, 1\}$, $\lim_{n \rightarrow +\infty} \mathbb{P}\left(Y_{n} = \varepsilon\right)$.

Q8a Discrete Probability Distributions Deriving or Identifying a Probability Distribution from a Random Process View

For $n$ a natural integer greater than or equal to 2, we consider the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability. We define a random variable $Z_{n}$ by $Z_{n}(\sigma) = \nu(\sigma)$.
Explicitly state the distribution of $Z_{n}$.

Q8b Discrete Probability Distributions Convergence proof and limit determination View

For $n$ a natural integer greater than or equal to 2, we consider the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability. We define a random variable $Z_{n}$ by $Z_{n}(\sigma) = \nu(\sigma)$.
Calculate, for any natural integer $k \leqslant n$, $\lim_{n \rightarrow +\infty} \mathbb{P}\left(Z_{n} = k\right)$.

Q8c Discrete Probability Distributions Expectation and Variance via Combinatorial Counting View

For $n$ a natural integer greater than or equal to 2, we consider the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability. We define a random variable $Z_{n}$ by $Z_{n}(\sigma) = \nu(\sigma)$.
Determine the average number of fixed points of a random permutation and its limit as $n$ tends to $+\infty$.

Q9 Discrete Probability Distributions Expectation and Variance via Combinatorial Counting View

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. We thus obtain a map $\omega : \mathfrak{S}_{n} \rightarrow \mathbb{N}$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_{n}$ such that $\omega(\sigma) = k$. We then consider, on the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability, the random variable $X_{n}$ defined by $X_{n}(\sigma) = \omega(\sigma)$.
Calculate, for $n \in \{2, 3, 4\}$, the quantity $\frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_{n}} \omega(\sigma)$.

Q12 Groups Convergence of Expectations or Moments View

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. We consider, on the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability, the random variable $X_{n}$ defined by $X_{n}(\sigma) = \omega(\sigma)$.
Prove that $\mathbb{E}\left[X_{n}\right] \underset{n \rightarrow +\infty}{=} \ln(n) + \gamma + O\left(\frac{1}{n}\right)$.

Q13a Groups Evaluation of a Finite or Infinite Sum View

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_{n}$ such that $\omega(\sigma) = k$.
Show that $$\frac{1}{n!} \sum_{k=1}^{n} k(k-1) s(n,k) = \sum_{i=1}^{n} \sum_{j=1}^{n} \frac{1}{ij} - \sum_{i=1}^{n} \frac{1}{i^{2}}.$$

Q13b Groups Expectation and Variance via Combinatorial Counting View

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_{n}$ such that $\omega(\sigma) = k$. We consider, on the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability, the random variable $X_{n}$ defined by $X_{n}(\sigma) = \omega(\sigma)$.
Deduce that $$\frac{1}{n!} \sum_{k=1}^{n} k^{2} s(n,k) = \mathbb{E}\left[X_{n}\right] + \left(\sum_{i=1}^{n} \sum_{j=1}^{n} \frac{1}{ij} - \sum_{i=1}^{n} \frac{1}{i^{2}}\right).$$

Q14a Groups Convergence of Expectations or Moments View

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$.
Show that $$\frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_{n}} \omega(\sigma)^{2} \underset{n \rightarrow +\infty}{=} (2\gamma+1)\ln(n) + c + \ln(n)^{2} + O\left(\frac{\ln(n)}{n}\right)$$ for a real number $c$ to be specified.

Q14b Groups Convergence of Expectations or Moments View

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$.
Show that $$\frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_{n}} (\omega(\sigma) - \ln(n))^{2} \underset{n \rightarrow +\infty}{=} \ln(n) + c + O\left(\frac{\ln(n)}{n}\right)$$

Q15 Groups Symmetric Group and Permutation Properties View

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. We consider, on the probability space $(\mathfrak{S}_{n}, \mathscr{P}(\mathfrak{S}_{n}))$ equipped with the uniform probability, the random variable $X_{n}$ defined by $X_{n}(\sigma) = \omega(\sigma)$.
Justify that there exists a positive real number $C > 0$ such that, for any real $\varepsilon > 0$ and any integer $n \geqslant 1$, we have $$\mathbb{P}\left(\left|X_{n} - \ln(n)\right| > \varepsilon \ln(n)\right) \leqslant \frac{C}{\varepsilon^{2} \ln(n)}$$

Q16 Integration by Parts Evaluation of a Finite or Infinite Sum View

Let $\left(a_{n}\right)_{n \geqslant 2}$ be a sequence of real numbers. For $t \in \mathbb{R}$, we set $A(t) = \sum_{2 \leqslant k \leqslant t} a_{k}$. Let $b : [2, +\infty[ \rightarrow \mathbb{R}$ be a function of class $\mathscr{C}^{1}$. Show that for any integer $n \geqslant 2$, $$\sum_{k=2}^{n} a_{k} b(k) = A(n) b(n) - \int_{2}^{n} b^{\prime}(t) A(t) \mathrm{d}t.$$

Q17a Number Theory Prime Counting and Distribution View

The objective of this question is to prove that if $n$ is a non-zero natural integer, then $\prod_{\substack{p \leqslant n \\ p \text{ prime}}} p \leqslant 4^{n}$.
Handle the cases $n \in \{1, 2, 3\}$.

Q17b Proof Prime Counting and Distribution View

The objective of this question is to prove that if $n$ is a non-zero natural integer, then $\prod_{\substack{p \leqslant n \\ p \text{ prime}}} p \leqslant 4^{n}$.
We now assume $n \geqslant 4$ and the result is known at rank $k$ for any integer $k$ between 1 and $n-1$. Establish the result at rank $n$ if $n$ is even.

Q17c Proof Prime Counting and Distribution View

The objective of this question is to prove that if $n$ is a non-zero natural integer, then $\prod_{\substack{p \leqslant n \\ p \text{ prime}}} p \leqslant 4^{n}$.
We now assume $n \geqslant 4$ and the result is known at rank $k$ for any integer $k$ between 1 and $n-1$. Let $n = 2m+1$ with $m \in \mathbb{N}$. Justify that $\prod_{\substack{m+1 < p \leqslant 2m+1 \\ p \text{ prime}}} p$ divides $\binom{2m+1}{m}$ and show that $\binom{2m+1}{m} \leqslant 4^{m}$.

Q17d Proof Prime Counting and Distribution View

The objective of this question is to prove that if $n$ is a non-zero natural integer, then $\prod_{\substack{p \leqslant n \\ p \text{ prime}}} p \leqslant 4^{n}$.
Conclude.

Q18 Number Theory Divisibility and Divisor Analysis View

Let $n$ be a non-zero natural integer and let $p$ be a prime number. Justify the formula $\nu_{p}(n!) = \sum_{k=1}^{+\infty} E\left(\frac{n}{p^{k}}\right)$ and show that $$\frac{n}{p} - 1 < \nu_{p}(n!) \leqslant \frac{n}{p} + \frac{n}{p(p-1)}$$

Q19a Sign Change & Interval Methods Asymptotic Equivalents and Growth Estimates for Sequences/Series View

By comparison with an integral, establish that $$\sum_{k=1}^{n} \ln(k) \underset{n \rightarrow +\infty}{=} n\ln(n) - n + O(\ln(n))$$

Q19b Number Theory Prime Counting and Distribution View

Justify that $n! = \prod_{\substack{p \leqslant n \\ p \text{ prime}}} p^{\nu_{p}(n!)}$ and deduce that $$n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} - n\ln(4) < \ln(n!) \leqslant n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} + n \sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p(p-1)}.$$

Q19c Sign Change & Interval Methods Convergence/Divergence Determination of Numerical Series View

Justify that the series $\sum_{k \geqslant 2} \frac{\ln(k)}{k(k-1)}$ converges.

Q19d Number Theory Prime Counting and Distribution View

Conclude that $\sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{\ln(p)}{p} \underset{n \rightarrow +\infty}{=} \ln(n) + O(1)$.

Q20a Number Theory Prime Counting and Distribution View

For all real $t \geqslant 2$, we define $$R(t) = \sum_{\substack{p \leqslant t \\ p \text{ prime}}} \frac{\ln(p)}{p} - \ln(t)$$ Show, using the result from question 16, that $$\sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{1}{p} = 1 + \ln_{2}(n) - \ln_{2}(2) + \frac{R(n)}{\ln(n)} + \int_{2}^{n} \frac{R(t)}{t(\ln(t))^{2}} \mathrm{~d}t$$

Q20b Number Theory Convergence/Divergence Determination of Numerical Series View

For all real $t \geqslant 2$, we define $$R(t) = \sum_{\substack{p \leqslant t \\ p \text{ prime}}} \frac{\ln(p)}{p} - \ln(t)$$ Justify that the function $t \mapsto \frac{R(t)}{t(\ln(t))^{2}}$ is integrable on $[2, +\infty[$.

Q20c Number Theory Asymptotic Equivalents and Growth Estimates for Sequences/Series View

For all real $t \geqslant 2$, we define $$R(t) = \sum_{\substack{p \leqslant t \\ p \text{ prime}}} \frac{\ln(p)}{p} - \ln(t)$$ Establish that $\sum_{\substack{p \leqslant n \\ p \text{ prime}}} \frac{1}{p} \underset{n \rightarrow +\infty}{=} \ln_{2}(n) + c_{1} + O\left(\frac{1}{\ln(n)}\right)$, for a real $c_{1} \in \mathbb{R}$ to be determined.

Q21a Number Theory Combinatorial Number Theory and Counting View

Let $x$ be a positive real number greater than or equal to 1 and $q \in \mathbb{N}^{*}$. Justify that the quantity $$\operatorname{Card}\{n \in \mathbb{N} \cap [1,x] : n \equiv 0 \pmod{q}\} - \frac{x}{q}$$ is bounded in absolute value by a real number independent of $x$ and $q$.

Q21b Number Theory Arithmetic Functions and Multiplicative Number Theory View

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Prove, using a summation interchange, that $\frac{1}{x} \sum_{n \leqslant x} \omega(n) \underset{x \rightarrow +\infty}{=} \ln_{2}(x) + O(1)$.

Q22a Number Theory Arithmetic Functions and Multiplicative Number Theory View

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Show that $$\frac{1}{x} \sum_{n \leqslant x} \left(\omega(n) - \ln_{2}(x)\right)^{2} \underset{x \rightarrow +\infty}{=} \frac{1}{x}\left(\sum_{n \leqslant x} \omega(n)^{2}\right) - \ln_{2}(x)^{2} + O\left(\ln_{2}(x)\right).$$

Q22b Number Theory Arithmetic Functions and Multiplicative Number Theory View

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Show that $$\sum_{n \leqslant x} \omega(n)^{2} = \sum_{\substack{p_{1} \leqslant x \\ p_{1} \text{ prime}}} \sum_{\substack{p_{2} \leqslant x \\ p_{2} \text{ prime}}} \operatorname{Card}\left\{n \in \mathbb{N}^{*} : n \leqslant x, p_{1} \mid n \text{ and } p_{2} \mid n\right\}$$

Q22c Number Theory Prime Counting and Distribution View

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Show that $$\left(\sum_{\substack{p_{1}, p_{2} \leqslant x \\ p_{1} \neq p_{2} \text{ prime}}} \operatorname{Card}\left\{n \in \mathbb{N}^{*} : n \leqslant x, p_{1} \mid n \text{ and } p_{2} \mid n\right\}\right) - x\ln_{2}(x)^{2} \underset{x \rightarrow +\infty}{=} O\left(x\ln_{2}(x)\right)$$ One may estimate the cardinality of the set of pairs of prime numbers $(p_{1}, p_{2})$ such that $p_{1} p_{2} \leqslant x$ as $x$ tends to $+\infty$.

Q22d Number Theory Arithmetic Functions and Multiplicative Number Theory View

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ Conclude that $\frac{1}{x}\left(\sum_{n \leqslant x} \left(\omega(n) - \ln_{2}(x)\right)^{2}\right) \underset{x \rightarrow +\infty}{=} O\left(\ln_{2}(x)\right)$.

Q23 Number Theory Combinatorial Number Theory and Counting View

For any non-zero natural integer $n$, we set $$\omega(n) = \operatorname{Card}\{p \text{ prime} : p \mid n\} = \sum_{\substack{p \mid n \\ p \text{ prime}}} 1.$$ We define $\mathscr{S} = \left\{n \geqslant 3 : \left|\frac{\omega(n) - \ln_{2}(n)}{\sqrt{\ln_{2}(n)}}\right| \geqslant \left(\ln_{2}(n)\right)^{1/4}\right\}$. Show that $$\lim_{x \rightarrow +\infty} \frac{1}{x} \operatorname{Card}\{n \leqslant x : n \in \mathscr{S}\} = 0$$ One may begin by writing $\operatorname{Card}(\mathscr{S} \cap [1,x]) \underset{x \rightarrow +\infty}{=} \operatorname{Card}(\mathscr{S} \cap [\sqrt{x}, x]) + O(\sqrt{x})$ and note that in the sum on the right-hand side, the difference $\left|\ln_{2}(n) - \ln_{2}(x)\right|$ remains bounded.

grandes-ecoles

Papers (176)

2024 polytechnique-maths-a__mp