Problem 1 (yau-contest 2018)
Section: Analysis and Differential Equations

Suppose $\{f_n\}_{n=1}^\infty \in L^2(\mathbb{R})$ is a sequence that converges to $0$ in the $L^2$ norm. Prove that there exists a subsequence $\{f_{n_k}\}$ such that $f_{n_k} \to 0$ almost everywhere.

Problem 2 (yau-contest 2018)
Section: Analysis and Differential Equations

Let $\hat{f}(\xi)=\int e^{-ix\xi}f(x)\,dx$ be the Fourier transform on Schwartz function $f\in S(\mathbb{R})$. Suppose $f\in S(\mathbb{R})$ satisfies $f(2\pi n)=0$ and $\hat{f}(n)=0$ for all integers $n$. Prove that $f=0$.

Problem 3 (yau-contest 2018)
Section: Analysis and Differential Equations

If $f$ is integrable on $\mathbb{R}^d$, then
$$\lim_{m(B)\to 0,\, x\in B} \frac{1}{m(B)} \int_B f(y)\,dy = f(x),$$
for a.e. $x$, $B$ is an open ball centered at $x$.

Problem 4 (yau-contest 2018)
Section: Analysis and Differential Equations

Let $C[0,1]=\{f:[0,1]\to \mathbb{R}\mid f\text{ is continuous}\}$ be the space of continuous function on $[0,1]$. Let $\rho(f,g)=\int_0^1 |f(x)-g(x)|\,dx$ be a metric on $[0,1]$.

Show that $(C[0,1],\rho)$ is not a complete metric vector space.

Construct a complete metric vector space $(W,\tilde{\rho})$ such that $i:(C[0,1],\rho)\hookrightarrow (W,\tilde{\rho})$ is an isometric embedding such that $\tilde{\rho}|_{C[0,1]}=\rho,\ C[0,1]=W$.

Problem 5 (yau-contest 2018)
Section: Analysis and Differential Equations

Let $\Omega$ be a simply connected domain in $\mathbb{C}$. Consider a point $z_0\in \Omega$ and solve the Dirichlet problem in $\Omega$ with the boundary values $\log|\zeta-z_0|$. The solution is denoted by $G(z,z_0)$ and let $g(z,z_0)=G(z,z_0)-\log|z-z_0|$. Let $w=f(z):\Omega\to D_1=\{z\mid |z|<1\}$ be the one to one surjective conformal mapping with $f(z_0)=0$. Show that

1) $g(z,z_0)=-\log|f(z)|$.

2) $g(z,z_0)=g(z_0,z)$. (Hint: Let $g(z,z_1)=g_1,\ g(z,z_2)=g_2$, calculate the integral $g_1\ast dg_2- g_2\ast dg_1$ over the cycle $\partial\Omega- c_1- c_2$, where $c_1,c_2$ are small circles around $z_1,z_2$, $du=u_xdx+u_ydy,\ \ast du=-u_y dx+u_x dy$.)

Problem Problem 1 (yau-contest 2018)
Section: Probability and Statistics

Let $X_i$, $1\le i\le N$ be i.i.d. random variables. Here $X_1$ is uniformly distributed on $[0,1]$. We reorder them as
$$\tilde{X}_1\le \tilde{X}_2\le \cdots \le \tilde{X}_N.$$

a) Let $N=2m-1$, and $Y=\tilde{X}_m$, please find the $A$ and $B$ such that
$$\frac{Y-A}{N^B}$$
has nontrivial distribution, and please find this distribution.

b) Let $N=2m$, and $Y=\tilde{X}_m-\tilde{X}_{m-1}$, please find the $A$ and $B$ such that
$$\frac{Y-A}{N^B}$$
has nontrivial distribution, and please find this distribution.

Problem Problem 2 (yau-contest 2018)
Section: Probability and Statistics

Let $\mathbf{X}=(\mathbb{Z}_2)^{\mathbb{N}}$, i.e., $\mathbf{X}=(X_1,X_2\cdots,X_N\cdots)$, $X_i\in\{0,1\}$. It can be considered as countable lightbulbs. 0 means off, 1 means on. We start with $\mathbf{X}_0=0$. Keep generating independent geometric random variables, whose distribution are $\mathrm{geom}(1/2)$. Denote them as $K_1, K_2\cdots$. Now let $\mathbf{X}_m$ (for $m\ge 1$) be as follows
$$(\mathbf{X}_m-\mathbf{X}_{m-1})_k=1(k=K_m),\quad \mathbb{Z}_2,$$
i.e., in the $m$–th turn, we only change the status of the $K_m$–th light bulb. Then what is the probability of all lights being off again, i.e.,
$$\mathbb{P}\,(\exists m>1,\ \mathbf{X}_m=0)\,?$$

Problem Problem 3 (yau-contest 2018)
Section: Probability and Statistics

Let $x_1,x_2,\ldots,x_n$ be $d$–dimensional vectors of real numbers with $n$ sufficiently large but the exact value is not of importance.

A function of $\mu$ is defined to be
$$\ell(\mu)=\sup\left\{\sum_{i=1}^n \log p_i\;:\; \sum_{i=1}^n p_i x_i=\mu;\ \sum_{i=1}^n p_i=1,\ p_1>0,\ldots,p_n>0\right\}$$
on the space of the interior of the convex hull of $x_1,\ldots,x_n$.

(a) Show that this is a concave function of $\mu$ on the convex hull.

(b) Let $\bar{x}=n^{-1}\sum_{i=1}^n x_i$. Let $a$ be a vector of length $d$. Prove that $\ell(\bar{x}+ta)$ is a decreasing function of $t$ when $t>0$.

Problem 4 (yau-contest 2018)

Consider the histogram estimator, defined as follows. We observe iid random variables $X_1,\ldots,X_n$, taking values in $[0,1]$ according to the distribution with PDF $f$ (assuming it is sufficiently smooth). Define bins

$$B_1=\left[0,\frac{1}{m}\right),\; B_2=\left[\frac{1}{m},\frac{2}{m}\right),\ldots,\; B_m=\left[\frac{m-1}{m},1\right].$$

Let $h=1/m$, $v_j$ be the number of observations in bin $B_j$, and define $\hat p_j=v_j/n$ and $p_j=\int_{B_j} f(u)\,du$. Then the histogram estimator of the density $f$ is

$$\hat f_n(x)=\sum_{j=1}^m \frac{\hat p_j}{h}\, I\{x\in B_j\}.$$

1. Find the (exact) mean and variance of $\hat f_n(x)$.
2. Explain why increasing the number of bins decreases the bias of $\hat f_n(x)$.
3. If our goal is to minimize the mean-squared error

$$MSE=E\left[\int (f(x)-\hat f_n(x))^2 dx\right],$$

please give some advice on how to choose $m$.

Problem 5 (yau-contest 2018)

Let $X_i\sim N(\theta_i,1)$ independently for $i=1,\ldots,k$. We are interested in estimating $\tau=\theta_1^2+\cdots+\theta_k^2$ given observations $X_1,\ldots,X_k$.

1. A possible estimator of $\tau$ is $\tilde{\tau}=\sum_{i=1}^k X_i^2-k$. Show that it is unbiased and compute its sampling variance.
2. Now assume the proper prior $\theta_i\sim N(0,A)$, independently for $i=1,\ldots,k$ and a given $A>0$. Since $A$ is unknown, please provide an estimator $\hat A$ of $A$ and also derive the empirical Bayes estimator of $\tau$, denoted as $\hat\tau_B$. (Hint: $\hat\tau_B=E(\tau\mid X_1,\ldots,X_k,\hat A)$.)
3. How do you compare the two estimators, $\tilde{\tau}$ and $\hat\tau_B$?

Problem 1 (yau-contest 2018)
Section: Geometry and Topology

Let $X$ be $(S^2\times S^2)\cup_{S^2} D^3$, where we attach the 3-disk via the map $S^2\to S^2\vee S^2$ which crushes a great circle connecting the north and south poles. Compute the homology groups of $X$.

Problem 2 (yau-contest 2018)
Section: Geometry and Topology

(a) Let $A$ be a single circle in $\mathbb{R}^3$. Compute the fundamental group $\pi_1(\mathbb{R}^3-A)$.

(b) Let $A$ and $B$ be disjoint circles in $\mathbb{R}^3$, supported in the upper and lower half space, respectively. Compute $\pi_1(\mathbb{R}^3-(A\cup B))$.

Problem 3 (yau-contest 2018)
Section: Geometry and Topology

Consider the differential 1-form $\omega=x\,dy-y\,dx+dz$ in $\mathbb{R}^3$ with coordinates $(x,y,z)$. Prove that $f\omega$ is not closed for any nowhere zero function $f:\mathbb{R}^3\to\mathbb{R}$.

Problem 4 (yau-contest 2018)
Section: Geometry and Topology

Show that
$$Q^n:=\{(x^1,\ldots,x^{n+1})\in\mathbb{R}^{n+1};\ \sum_{i=1}^{n+1}(x^i)^4=1\}$$
is a differentiable manifold.

Problem 5 (yau-contest 2018)
Section: Geometry and Topology

Let $M$ be a closed surface in $\mathbb{R}^3$. Prove that
$$\int_M |K|\,d\sigma \ge 4\pi(1+g),$$
where $K$, $g$ and $d\sigma$ are the Gaussian curvature, the genus and the area element of $M$, respectively.

Problem 6 (yau-contest 2018)
Section: Geometry and Topology

Let $M$ be an $n$-dimensional compact and simply connected Riemannian manifold. If the sectional curvature $K_M$ of $M$ satisfies
$$\frac{1}{4}<K_M\le 1,$$
then $M$ is homeomorphic to $S^n$.

Problem 1 (yau-contest 2018)
Section: Algebra and Number Theory

Recall that a ring $E$ is said to be local if for every $u\in E$, at least one of the elements $u$ and $1-u$ is invertible. Let $R$ be a ring and let $M$ be an $R$-module.

(a) Show that if $\operatorname{End}_R(M)$ is a local ring, then $M$ is indecomposable.

(b) Assume $M$ indecomposable and of finite length. Prove the Fitting lemma: Every endomorphism $u$ of $M$ is either invertible or nilpotent. Deduce that $\operatorname{End}_R(M)$ is a local ring.

Problem 2 (yau-contest 2018)
Section: Algebra and Number Theory

(a) Let $n \ge 2$ be an integer. Show that there exists an integer $m$ with $1 \le m \le n-1$ such that the binomial coefficient $\binom{n}{m}$ satisfies $\binom{n}{m} \ge 2^n/n$.

(b) Let $0 \le m \le n$ be integers with $n \ge 1$. Show that for every prime number $p$,
$$v_p\!\left(\binom{n}{m}\right) \le \log_p(n)$$
Here $v_p$ is the $p$-adic valuation: $v_p(p^a b)=a$ for integers $b$ prime to $p$ and $a \ge 0$.

(c) Let $n \ge 2$ be an integer and let $\pi(n)$ denote the number of prime numbers $p \le n$. Deduce the following inequality of Chebyshev:
$$\pi(n) \ge \frac{n}{\log_2 n} - 1.$$

Problem 3 (yau-contest 2018)
Section: Algebra and Number Theory

Let $n \ge 1$ be an integer and let $\Phi_n(X) \in \mathbb{Q}[X]$ denote the $n$-th cyclotomic polynomial, i.e.
$$\Phi_n(X) := \prod_{\xi} (X-\xi),$$
where $\xi$ runs through primitive $n$-th roots of unity in $\mathbb{C}$. Recall that $X^n-1=\prod_{d\mid n}\Phi_d(X)$ and $\Phi_n(X)$ belongs to $\mathbb{Z}[X]$. Let $p$ be a prime number such that $p\nmid n$. Denote by $\overline{\Phi_n}$ the residue class of $\Phi_n$ in $\mathbb{F}_p[X]$. Prove the following statements:

(a) The roots of $\overline{\Phi_n}=0$ in the algebraic closure $\overline{\mathbb{F}_p}$ of $\mathbb{F}_p$ are exactly the primitive $n$-th roots of $1$ in $\overline{\mathbb{F}_p}$.

(b) $\overline{\Phi_n}$ is irreducible in $\mathbb{F}_p[X]$ if and only if $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is a cyclic group generated by the class of $p$.

Problem 4 (yau-contest 2018)
Section: Algebra and Number Theory

Let $G$ be a finite group. Let $V$ be a finite-dimensional complex representation of $G$ and let $\chi: V \to \mathbb{C}$ be the associated character.

(a) Show that there exists a subfield $L \subseteq \mathbb{C}$ containing the image of $\chi$ such that $L/\mathbb{Q}$ is a finite Galois extension. Show moreover that
$$B(\chi) = \prod_{\sigma \in \operatorname{Gal}(L/\mathbb{Q})} \prod_{g \in G} \sigma(\chi(g))$$
belongs to $\mathbb{Z}$.

(b) Suppose that $\chi$ is irreducible and $\dim(V) \ge 2$. Show that there exists $g \in G$ with $\chi(g)=0$. (Hint. One may apply the inequality of arithmetic and geometric means to $|B(\chi)|^2$.)

Problem 5 (yau-contest 2018)
Section: Algebra and Number Theory

Let $F$ be a field, $V$ an $F$-vector space of dimension $d$ and $W \subseteq V$ a subspace. Let $f: W \to V$ be an $F$-linear map. Assume that the only subspace $W' \subseteq W$ such that $f(W') \subseteq W'$ is $\{0\}$.

(a) Let $v \in V$ be a non-zero vector. Show that there exists a unique integer $k(v) \ge 0$ such that $v, f(v), f^2(v), \dots, f^{k(v)-1}(v) \in W$ but $f^{k(v)}(v) \notin W$. Show moreover that $v, f(v), \dots, f^{k(v)}(v)$ are linearly independent over $F$.

(b) Prove that given $\lambda_1, \dots, \lambda_d \in F$, there exists an $F$-linear extension of $f$ to $\hat f : V \to V$ such that the characteristic polynomial of $\hat f$ is $\prod_{i=1}^d (\lambda - \lambda_i)$. (Hint. You may first treat the special case $V = \bigoplus_{i=0}^{k(v)} F f^i(v)$. For the general case, consider the subset $W_n \subseteq V$ of vectors $v \in V$ with $k(v) \ge n$ or $v = 0$.)

Problem 1 (yau-contest 2018)
Section: Applied Math. and Computational Math.

Let $H$ be a bipartite graph with the bipartition $V = V_1 \cup V_2$, where $|V_1| = |V_2| = n$. We say that $H$ satisfies the $(p,q)$-condition if (i) for all subsets $I \subseteq V_1$ of cardinality at most $p$, the inequality $|I| \le |N(I)|$ holds, and (ii) for all subsets $J \subseteq V_2$ of cardinality at most $q$, the inequality $|J| \le |N(J)|$ holds. Note that the $(n,0)$-condition is Hall’s original condition in his marriage theorem.

Prove that if $H$ satisfies the $(p,q)$-condition with $n \le p + q$, then $H$ contains a matching of size $n$.

Problem 2 (yau-contest 2018)
Section: Applied Math. and Computational Math.

Let $C_n$ be the $n$ dimensional hypercube, i.e., the graph whose vertex set $V$ is $\{0,1\}^n$, and whose edges are defined by: two vertices $u = u_1u_2\ldots u_n$ and $v = v_1v_2\ldots v_n$ are adjacent iff $u_i \ne v_i$ for exactly one $i \in [n]$. Let $\mathbb{R}[V]$ be the vector space of all the functions $f : V \to \mathbb{R}$. The space $\mathbb{R}[V]$ has a natural inner product. For $f,g \in \mathbb{R}[V]$, 
$$\langle f,g \rangle = \sum_{u\in\{0,1\}^n} f(u)g(u).$$

The standard basis of $\mathbb{R}[V]$ is the set $\{f_u : u \in \{0,1\}^n\}$ where $f_u(v) = \delta_{u,v}$, the Kronecker delta, for $u,v \in \{0,1\}^n$. Denote by $B_1$ the standard basis.

(1) For any two vertices $u,v \in \{0,1\}^n$, $u \cdot v$ is defined to be $\sum_i u_i v_i$. For each $u \in \{0,1\}^n$, define a function $\chi_u \in \mathbb{R}[V]$ by letting
$$\chi_u(v) = (-1)^{u\cdot v}.$$
Prove that the set $\{\chi_u : u \in \{0,1\}^n\}$ is orthogonal with respect to the inner product of $\mathbb{R}[V]$, i.e.,
$$\langle \chi_u, \chi_v \rangle = \delta_{u,v} 2^n,$$
for all $u,v \in \{0,1\}^n$.

(2) Prove that the set $\{\chi_u : u \in \{0,1\}^n\}$ forms a basis of the vector space $\mathbb{R}[V]$. Denoted by $B_2$ this basis.

(3) For $1 \le i \le n$, let $e_i = (0,\ldots,0,1,0,\ldots,0) \in \{0,1\}^n$ where the only $1$ occurs in position $i$. Let $S = \{e_1, e_2, \ldots, e_n\}$. Define a linear transformation $\Phi : \mathbb{R}[V] \to \mathbb{R}[V]$ as follows. For $f \in \mathbb{R}[V]$, $\Phi f$ is the element in $\mathbb{R}[V]$ which is given by
$$ (\Phi f)(v) = \sum_{e_i \in S} f(v + e_i) $$
where $v + e_i$ is the usual vector addition modulo $2$.
Prove that the matrix of $\Phi$ with respect to the standard basis $B_1$ is just $A(C_n)$, the adjacency matrix of the hypercube $C_n$.

(4) Prove that $\Phi \chi_u = \lambda_u \chi_u$ for each $u \in \{0,1\}^n$, where
$$ \lambda_u = \sum_{e\in S} (-1)^{u\cdot e} = n - 2|u|, $$
where $|u|$ is the number of $1$’s in $u = u_1u_2\ldots u_n.

(5) Compute the eigenvalues of the matrix $A(C_n)$.

Problem 3 (yau-contest 2018)
Section: Applied Math. and Computational Math.

Let $A \in \mathbb{R}^{n\times n}$, and assume that there are unitary matrix $Q$ and diagonal matrix $D = \operatorname{diag}(\lambda_1, \cdots, \lambda_n)$ such that $A = Q D Q^*$. Let $E_k$ be the space spanned by the first $k$ columns of $Q$. We let
$$ \hat{P} = (\, I_k \quad 0 \,), \qquad P = Q \hat{P} Q^* $$
where $I_k$ is the $k \times k$ identity matrix.

(1) Show that $P$ is an orthogonal projection onto $E_k$.

(2) Assume that
$$ |\lambda_1| \ge \cdots \ge |\lambda_k| > |\lambda_{k+1}| \ge \cdots \ge |\lambda_n|. $$
Let $X^{(0)} \in \mathbb{R}^{n\times k}$ and assume $P X^{(0)}$ is injective. We define the iterations
$$ X^{(m+1)} = A X^{(m)}. $$
Show that there is a matrix $\Lambda \in \mathbb{R}^{k\times k}$ such that
$$ \frac{\lVert (A X^{(m)} - X^{(m)} \Lambda) y \rVert}{\lVert P X^{(m)} y \rVert} \le \left( \frac{|\lambda_{k+1}|}{|\lambda_k|} \right)^m \frac{\lVert (A X^{(0)} - X^{(0)} \Lambda) y \rVert}{\lVert P X^{(0)} y \rVert}, \qquad \forall\, y \in \mathbb{R}^k\setminus\{0\}. $$

Problem 4 (yau-contest 2018)
Section: Applied Math. and Computational Math.

For the one-way equation
(1) $$ u_t + a u_x = f, $$
consider the multistep scheme given by
(2) $$ \frac{3u_m^{n+1} - 4u_m^{n} + u_m^{n-1}}{2k} + a\, \frac{u_{m+1}^{n+1} - u_{m-1}^{n+1}}{2h} = f_m^{n+1}. $$

(1) Show that the scheme is second order accurate.

(2) Show that the scheme is unconditionally stable.

(Hint: (i) apply von Neumann analysis to the scheme with $f \equiv 0$ and find the characteristic polynomial. (ii) show that for all $k,h$, the characteristic polynomial satisfies the root condition: all roots reside in the unit disk, and all roots on the unit circle are simple. (iii) for a root $r$ of the characteristic polynomial, it would be more convenient to study the form $\dfrac{1}{r} = X + iY$ and prove that $X^2 + Y^2 \ge 1$.)

Problem 5 (yau-contest 2018)

For a convex function \(f : D \to \mathbb{R}\), where \(D \subseteq \mathbb{R}^n\) is convex and open, define a subgradient of \(f\) at \(x_0 \in D\) to be any vector \(s \in \mathbb{R}^n\) such that
\[
f(x) - f(x_0) \ge s \cdot (x - x_0)
\]
for all \(x \in D\). The subgradient is a plausible choice for generalizing the notion of a gradient at a point where \(f\) is not differentiable. The subdifferential \(\partial f(x_0)\) is the set of all subgradients of \(f\) at \(x_0\).

(1) What is \(\partial f(0)\) for the function \(f(x) = |x|\).

(2) Suppose we wish to minimize a convex and continuous function \(f : \mathbb{R}^n \to \mathbb{R}\), which may not be differentiable everywhere. Propose an optimality condition involving subdifferential for a point \(x_*\) to be a minimizer of \(f\). Show that your condition holds if and only if \(x_*\) is a globally minimizer \(f\).

(3) The subgradient method extends the gradient descent to a wider class of functions. Analogously to the gradient descent, the subgradient method performs the iteration
\[
x_{k+1} = x_k - \alpha g_k,
\]
where \(\alpha > 0\) is small stepsize that is known as the learning rate, and \(g_k\) is any subgradient of \(f\) at \(x_k\). This method might not decrease \(f\) in each iteration, so instead we keep track of the best iterate we have seen so far, \(x_k^{\text{best}}\).

In the following parts, assume that \(f\) is Lipschitz continuous with constant \(L > 0\), \(\|x_1 - x_*\|_2 \le B\) for some \(B > 0\). Under these assumptions we will show that
\[
\lim_{k \to \infty} f\big(x_k^{\text{best}}\big) \le f(x_*) + \frac{L^2}{2}\alpha,
\]
a bound characterizing convergence of the subgradient method.

(a) Derive an upper bound for the error \(\|x_{k+1} - x_*\|_2^2\) of \(x_{k+1}\) in terms of \(\|x_k - x_*\|_2^2\), \(g_k\), \(\alpha\), \(f(x_k)\) and \(f(x_*)\).

(b) By recursively applying the result from Problem 3a, provide an upper bound for \(\|x_{k+1} - x_*\|_2^2\).

(c) Incorporate \(f\big(x_k^{\text{best}}\big)\) into your upper bound in Problem 3b, and take a limit as \(k \to \infty\) to obtain the desired convergence result (3).

(d) Suggest a best choice of the learning rate \(\alpha\).