Problem 1 (yau-contest 2016)

Consider the implicit leapfrog scheme
$$
\frac{u_m^{n+1}-u_m^{n-1}}{2k} + a\left(1+\frac{h^2}{6}\,\delta^2\right)^{-1}\delta_0 u_m^n = f_m^n
$$
for the one-way wave equation
$$
u_t + a u_x = f.$$
Here $\delta^2$ is the central second difference operator, and $\delta_0$ is the central first difference operator.

(1) Show that the scheme is of order $(2,4)$.

(2) Show that the scheme is stable if and only if $\left|\dfrac{a k}{h}\right| < \dfrac{1}{\sqrt{3}}$.

Problem 2 (yau-contest 2016)

A simple version of an enzyme-mediate chemical reaction process is given by
$$
\mathrm{S} + \mathrm{E} \xrightleftharpoons[k_2]{k_1} \mathrm{C} \xrightarrow{k_3} \mathrm{P} + \mathrm{E}
$$
where $S$ is the substrate reactant and $P$ is the concentration of the desired product. An enzyme (or catalyst) $E$ is a compound whose special property is that it allows for intermediate reaction steps that lead to a the overall reaction,
$$
\mathrm{S} \longrightarrow \mathrm{P}.
$$
Assume the initial conditions
$$
S(0)=S_0,\quad E(0)=E_0,\quad C(0)=0,\quad P(0)=0;
$$
$k_1,k_2,k_3$ are reaction rate constants.

(a) Convert the chemical reaction equation into a system of rate equations (ODEs) for $S(T)$, $E(T)$, $C(T)$, and $P(T)$ where $T$ is the dimensional time. Nondimensionalize the equations using the scalings
$$
T=\frac{t}{k_1E_0},\quad S(T)=S_0\,s(t),\quad P(T)=S_0\,p(t),\quad E(T)=E_0\,e(t),\quad C(T)=E_0\,c(t),
$$
$$
\epsilon=\frac{E_0}{S_0}\ll1,\quad \lambda=\frac{k_2}{k_1S_0},\quad \mu=\frac{k_2+k_3}{k_1S_0}.
$$

(b) Use the expansions $s(t)=s_0(t)+\epsilon s_1(t)+O(\epsilon^2)$, $c(t)=c_0(t)+\epsilon c_1(t)+O(\epsilon^2)$, etc., to determine the equations for the leading order slow solution. Show that $s_0(t)$ and $p_0(t)$ satisfy the following Michaelis–Menten equations
$$
\dot{s}_0(t)=-(\mu-\lambda)\,\frac{s_0}{\mu+s_0},\qquad \dot{p}_0(t)=(\mu-\lambda)\,\frac{s_0}{\mu+s_0}.
$$

Problem 3 (yau-contest 2016)

We say that a vector $\mathbf{u}=(u_1,\ldots,u_n)\in\mathbb{N}^n$ is multiplicatively dependent if there is a non-zero vector $\mathbf{k}=(k_1,\ldots,k_n)\in\mathbb{Z}^n$ for which
$$
 u_1^{k_1}\cdots u_n^{k_n}=1.
$$
This notion plays a very important role in many number theoretic algorithms, such as factorisation and primality testing. It also (in a more general form) appears in some questions in algebraic dynamics. However the algorithm to decide whether $\mathbf{u}$ is multiplicatively dependent is not immediately obvious. The following statement informally means that if $\mathbf{u}$ is multiplicatively dependent then the exponents $k_1,\ldots,k_n$ can be chosen to be reasonably small. Prove that if $\mathbf{u}=(u_1,\ldots,u_n)\in\mathbb{N}^n$ is multiplicatively dependent with $\|\mathbf{u}\|_\infty\le H$ where $\|\mathbf{u}\|_\infty=\max_{1\le i\le n}|u_i|$, then there is a non-zero vector $\mathbf{k}=(k_1,\ldots,k_n)\in\mathbb{Z}^n$ with
$$
\|\mathbf{k}\|_\infty\le\left(\frac{2n\log H}{\log 2}\right)^{n-1}
$$
(and hence for a fixed $n$ it can be found in polynomial time of order $(\log H)^{n(n-1)}$).

Comment: To solve this problem, you can use the following statement (without proof) which informally means that if a system of homogeneous equations with integer coefficients has a nontrivial solution then it has an integer solution with reasonably small components. It is required in many applications. Let $A=(a_{ij})$ be an $m\times n$ matrix of rank $r\le n-1$ with integer entries of size at most $H$, that is,
$$
|a_{ij}|\le H,\qquad 1\le i\le m,\ 1\le j\le n.
$$
Then there is an integer non-zero vector $\mathbf{x}=(x_1,\ldots,x_n)\in\mathbb{Z}^n$ such that $A\mathbf{x}=0$ and
$$
\|\mathbf{x}\|_\infty\le (2nH)^{n-1},
$$
where $\|\mathbf{x}\|_\infty=\max_{1\le i\le n}|x_i|.$

Problem 4 (yau-contest 2016)

Consider a symmetric matrix $A_{n\times n}$, and let $\lambda_i$ be a simple eigenvalue of $A$ with
$$
|\lambda_j-\lambda_i|=O(1), \quad j\ne i.
$$
In inverse iteration of compute eigenvalue and eigenvector, one needs to solve the following linear system
$$
(A-\mu I)\,y_{k+1}=x_k,
$$
where $\mu$ is an approximation of eigenvalue $\lambda_i$, $\|x_k\|=1$ and obtain
$$
 x_{k+1}=\frac{y_{k+1}}{\|y_{k+1}\|}.
$$
However, for $\mu$ close to $\lambda_i$, $A-\mu I$ has a very small eigenvalue and the linear system will be ill-conditioned. So there may be large error in the numerical solution to the linear system, denoted by $\tilde{y}_{k+1}$. Even though we may get large error in $\tilde{y}_{k+1}$, the $\tilde{x}_{k+1}$ we get from $\tilde{x}_{k+1}=\dfrac{\tilde{y}_{k+1}}{\|\tilde{y}_{k+1}\|}$ is accurate.

Problem unknown (yau-contest 2016)

(1) $\bar{y}_{k+1}$ satisfies
$$(A - \mu I + \delta A)\bar{y}_{k+1} = x_k,$$
where $\|\delta A\| = O(\epsilon)$ and $\epsilon$ is the machine precision. Show that
$$(A - \lambda_i) \frac{\bar{y}_{k+1}}{\|\bar{y}_{k+1}\|} \le \|\mu - \lambda_i\| + \|\delta A\| + \frac{1}{\|\bar{y}_{k+1}\|}.$$
(2) Let $\alpha_i = x_k^t q_i$, where $q_i$ is the normalized eigenvector corresponding to $\lambda_i$. Show that
$$\|\bar{y}_{k+1}\| \ge \frac{|\alpha_i|}{|\mu - \lambda_i| + \|\delta A\|}.$$
(3) Conclude that
$$\|x_{k+1} - (\pm)q_i\| = O(|\lambda_i - \mu| + \epsilon).$$

Problem 5 (yau-contest 2016)

A function $f : \mathbb{R}^n \to \mathbb{R}$ in $C^2$ is called strongly convex if its Hessian matrix satisfies $\nabla^2 f \succeq mI$ for some $m > 0$. Show that the following statements are equivalent:
(a) $f$ is strongly convex, i.e. $\nabla^2 f(x) \succeq mI$ for all $x \in \mathbb{R}^n$;
(b) For any $t \in [0, 1]$, any $x, y \in \mathbb{R}$,
$$f(tx + (1 - t)y) \le t f(x) + (1 - t) f(y) - \frac{m}{2} (1 - t)\|x - y\|^2;$$
(c) $\langle \nabla f(x) - \nabla f(y), x - y \rangle \ge m\|x - y\|^2$ for any $x, y \in \mathbb{R}^n$.