A report of my Princeton generals exam

April 26, 2011April 27, 2011 ConanLeave a comment

Well, some people might be wondering why I haven’t updated my blog since two weeks ago…Here’s the answer: I have been preparing for this generals exam — perhaps the last exam in my life.

For those who don’t know the game rules: The exam consists of 3 professors (proposed by the kid taking the exam, approved by the department), 5 topics (real, complex, algebra + 2 specialized topics chosen by the student). One of the committee member acts as the chair of the exam.

The exam consists of the three committee members sitting in the chair’s office, the student stands in front of the board. The professors ask questions ranging in those 5 topics for however long they want, the kid is in charge of explaining them on the board.

I was tortured for 4.5 hours (I guess it sets a new record?)
I have perhaps missed some questions in my recollection (it’s hard to remember all 4.5 hours of questions).

Conan Wu’s generals

Commitee: David Gabai (Chair), Larry Guth, John Mather

Topics: Metric Geometry, Dynamical Systems

Real analysis:

Mather: Construct a first category but full measure set.

(I gave the intersection of decreasing balls around the rationals)

Guth: $F:S^1 \rightarrow \mathbb{R}$ 1-Lipschitz, what can one say about its Fourier coefficients.

(Decreasing faster than $c*1/n$ via integration by parts)

Mather: Does integration by parts work for Lipschitz functions?

(Lip imply absolutely continuous then Lebesgue’s differentiation theorem)

Mather: If one only has bounded variation, what can we say?

( $f(x) \geq f(0) + \int_0^x f'(t) dt$ )

Mather: If $f:S^1 \rightarrow \mathbb{R}$ is smooth, what can you say about it’s Fourier coefficients?

(Prove it’s rapidly decreasing)

Mather: Given a smooth $g: S^1 \rightarrow \mathbb{R}$ , given a $\alpha \in S^1$ , when can you find a $f: S^1 \rightarrow \mathbb{R}$ such that
$g(\theta) = f(\theta+\alpha)-f(\theta)$ ?

(A necessary condition is the integral of $g$ needs to vanish,
I had to expand everything in Fourier coefficients, show that if $\hat{g}(n)$ is rapidly decreasing, compute the Diophantine set $\alpha$ should be in to guarantee $\hat{f}(n)$ being rapidly decreasing.

Gabai: Write down a smooth function from $f:\mathbb{R}^2 \rightarrow \mathbb{R}$ with no critical points.

(I wrote $f(x,y) = x+y$ ) Draw its level curves (straight lines parallel to $x=-y$ )

Gabai: Can you find a such function with the level curves form a different foliation from this one?

(I think he meant that two foliations are different if there is no homeo on $\mathbb{R}^2$ carrying one to the other,
After playing around with it for a while, I came up with an example where the level sets form a Reeb foliation, and that’s not same as the lines!)

We moved on to complex.

Complex analysis:

Guth: Given a holomorphic $f:\mathbb{D} \rightarrow \mathbb{D}$ , if $f$ has $50$ $0$ s inside the ball $B_{1/3}(\bar{0})$ , what can you say about $f(0)$ ?

(with a bunch of hints/suggestions, I finally got $f(0) \leq (1/2)^{50}$ — construct polynomial vanishing at those roots, quotient and maximal modulus)

Guth: State maximal modulus principal.

Gabai: Define the Mobius group and how does it act on $\mathbb{H}$ .

Gabai: What do the Mobius group preserve?

(Poincare metric)

Mather: Write down the Poincare metric, what’s the distance from $\bar{0}$ to $1$ ? (infinity)

(I don’t remember the exact distance form, so I tried to guess the denominator being $\sqrt{1-|z|}$ , but then integrating from $0$ to $1$ does not “barely diverge”. Turns out it should be $(1-|z|^2)^2$ .)

Gabai: Suppose I have a finite subgroup with the group of Mobius transformations acting on $\mathbb{D}$ , show it has a global fixed point.

(I sketched an argument based on each element having finite order must have a unique fixed point in the interior of $\mathbb{D}$ , if two element has different fixed points, then one can construct a sequence of elements where the fixed point tends to the boundary, so the group can’t be finite.)

I think that’s pretty much all for the complex.

Algebra:

Gabai: State Eisenstein’s criteria

(I stated it with rings and prime ideals, which leaded to a small discussion about for which rings it work)

Gabai: State Sylow’s theorem

(It’s strange that after stating Sylow, he didn’t ask me do anything such as classify finite groups of order xx)

Gabai: What’s a Galois extension? State the fundamental theorem of Galois theory.

(Again, no computing Galois group…)

Gabai: Given a finite abelian group, if it has at most $n$ elements of order divisible by $n$ , prove it’s cyclic.

(classification of abelian groups, induction, each Sylow is cyclic)

Gabai: Prove multiplicative group of a finite field is cyclic.

(It’s embarrassing that I was actually stuck on this for a little bit before being reminded of using the previous question)

Gabai: What’s $SL_2(\mathbb{Z})$ ? What are all possible orders of elements of it?

(I said linear automorphisms on the torus. I thought it can only be $1,2,4,\infty$ , but turns out there is elements of order $6$ . Then I had to draw the torus as a hexagon and so on…)

Gabai: What’s $\pi_3(S^2)$ ?

( $\mathbb{Z}$ , via Hopf fibration)

Gabai: For any closed orientable $n$ -manifold $M$ , why is $H_{n-1}(M)$ torsion free?

(Poincare duality + universal coefficient)

We then moved on to special topics:

Metric Geometry:

Guth: What’s the systolic inequality?

(the term ‘aspherical’ comes up)

Gabai: What’s aspherical? What if the manifold is unbounded?

(I guessed it still works if the manifold is unbounded, Guth ‘seem to’ agree)

Guth: Sketch a proof of the systolic inequality for the n-torus.

(I sketched Gromov’s proof via filling radius)

Guth: Give an isoperimetric inequality for filling loops in the 3-manifold $S^2 \times \mathbb{R}$ where $S^2$ has the round unit sphere metric.

(My guess is for any 2-chain we should have

$\mbox{vol}_1(\partial c) \geq C \mbox{vol}_2(c)$

then I tried to prove that using some kind of random cone and grid-pushing argument, but soon realized the method only prove

$\mbox{vol}_1(\partial c) \geq C \sqrt{\mbox{vol}_2(c)}$ .)

Guth: Given two loops of length $L_1, L_2$ , the distance between the closest points on two loops is $\geq 1$ , what’s the maximum linking number?

(it can be as large as $c L_1 L_2$ )

Dynamical Systems:

Mather: Define Anosov diffeomorphisms.

Mather: Prove the definition is independent of the metric.

(Then he asked what properties does Anosov have, I should have said stable/unstable manifolds, and ergodic if it’s more than $C^{1+\varepsilon}$ …or anything I’m familiar with, for some reason the first word I pulled out was structurally stable…well then it leaded to and immediate question)

Mather: Prove structural stability of Anosov diffeomorphisms.

(This is quite long, so I proposed to prove Anosov that’s Lipschitz close to the linear one in $\mathbb{R}^n$ is structurally stable. i.e. the Hartman-Grobman Theorem, using Moser’s method, some details still missing)

Mather: Define Anosov flow, what can you say about geodesic flow for negatively curved manifold?

(They are Anosov, I tried to draw a picture to showing the stable and unstable and finished with some help)

Mather: Define rotation number, what can you say if rotation numbers are irrational?

(They are semi-conjugate to a rotation with a map that perhaps collapse some intervals to points.)

Mather: When are they actually conjugate to the irrational rotation?

(I said when $f$ is $C^2$ , $C^1$ is not enough. Actually $C^1$ with derivative having bounded variation suffice)

I do not know why, but at this point he wanted me to talk about the fixed point problem of non-separating plane continua (which I once mentioned in his class).

After that they decided to set me free~ So I wandered in the hallway for a few minutes and the three of them came out to shake my hand.

Graph, girth and expanders

April 11, 2011November 1, 2011 Conan2 Comments

In the book “Elementary number theory, group theory and Ramanujan graphs“, Sarnak et. al. gave an elementary construction of expander graphs. We decided to go through the construction in the small seminar and I am recently assigned to give a talk about the girth estimate of such graphs.

Given graph (finite and undirected) $G$ , we will denote the set of vertices by $V(G)$ and the set of edges $E(G) \subseteq V(G)^2$ . The graph is assumed to be equipped with the standard metric where each edge has length $1$ .

The Cheeger constant (or isoperimetric constant of a graph, see this pervious post) is defined to be:

$\displaystyle h(G) = \inf_{S\subseteq V_G} \frac{|\partial S|}{\min\{|S|, |S^c|\}}$

Here the notation $\partial S$ denote the set of edges connecting an element in $S$ to an element outside of $S$ .

Note that this is indeed like our usual isoperimetric inequalities since it’s the smallest possible ratio between size of the boundary and size of the set it encloses. In other words, this calculates the most efficient way of using small boundary to enclose areas as large as possible.

It’s of interest to find graphs with large Cheeger constant (since small Cheeger constant is easy to make: take two large graphs and connect them with a single edge).

It’s also intuitive that as the number of edges going out from each vertice become large, the Cheeger constant will become large. Hence it make sense to restrict ourselves to graphs where there are exactly $k$ edges shearing each vertex, those are called $k$ -regular graphs.

If you play around a little bit, you will find that it’s not easy to build large k-regular graphs with Cheeger constant larger than a fixed number, say, $1/10$ .

Definition: A sequence of k-regular graphs $(G_i)$ where $|V_{G_i}| \rightarrow \infty$ is said to be an expander family if there exists constant $c>0$ where $h(G_i) \geq c$ for all $i$ .

By random methods due to Erdos, we can prove that expander families exist. However an explicit construction is much harder.

Definition: The girth of $G$ is the smallest non-trivial cycle contained in $G$ . (Doesn’t this smell like systole? :-P)

In the case of trees, since it does not contain any non-trivial cycle, define the girth to be infinity.

The book constructs for us, given pair $p, q$ of primes where $p$ is large (but fixed) and $q \geq p^8$ , a graph $(p+1)$ -regular graph $X^{p,q}$ with

$\displaystyle h(X^{p,q}) \geq \frac{1}{2}(p+1 - p^{5/6 + \varepsilon} - p^{1/6-\varepsilon})$

where $0 < \varepsilon < 1/6$ .

Note that the bound is strictly positive and independent of $q$ . Giving us for each $p$ , $(X^{p,q})$ as q runs through primes larger than $p^8$ is a $(p+1)$ -regular expander family.

In fact, this constructs for us an infinite family of expander families: a $(k+1)$ -regular one for each prime $k$ and the uniform bound on Cheeger constant gets larger as $k$ becomes larger.

One of the crucial step in proving this is to bound the girth of the graph $X^{p,q}$ , i.e. they showed that $g(X^{p,q}) \geq 2 \log_p(q)$ and if the quadratic reciprocity $(\frac{p}{q}) = -1$ then $g(X^{p,q}) \geq 4 \log_p(q) - \log_p(4)$ . This is what I am going to do in this post.

Let $\mathbb H ( \mathbb Z)$ be the set of quaternions with $\mathbb Z$ coefficient, i.e.

$\mathbb H ( \mathbb Z) = \{ a+bi+cj+dk \ | \ a,b,c,d \in \mathbb Z \}$

Fix odd prime $p$ , let

$\Lambda' = \{ \alpha \in \mathbb H(\mathbb Z) \ | \ \alpha \equiv 1 (mod 2) \}$

$\cup \ \{\alpha \in \mathbb H(\mathbb Z) \ | \ N(\alpha) = p^n \ \mbox{and} \ \alpha \equiv i+j+k (mod 2) \}$

where the norm $N$ on $\mathbb H(\mathbb Z)$ is the usual $N(a+bi+cj+dk) = a^2 + b^2 +c^2+d^2$ .

$\Lambda'$ consists of points with only odd first coordinate or points lying on spheres of radius $\sqrt{p^n}$ and having only even first coordinate. One can easily check $\Lambda'$ is closed under multiplication.

Define equivalence relation $\sim$ on $\Lambda'$ by

$\alpha \sim \beta$ if there exists $m, n \in \mathbb{N}$ s.t. $p^m \alpha = \pm p^n \beta$ .

Let $\Lambda = \Lambda' / \sim$ , let $Q: \Lambda' \rightarrow \Lambda$ be the quotient map.

Since we know $\alpha_1 \sim \alpha_2, \beta_1 \sim \beta_2 \Rightarrow \alpha_1\beta_1 \sim \alpha_2\beta_2$ , $\Lambda$ carries an induced multiplication with unit.

In elementary number theory, we know that the equation $a^2+b^2+c^2+d^2 = p$ has exactly $8(p+1)$ integer solutions. Hence the sphere of radius $p$ in $\mathbb H(\mathbb Z)$ contain $8(p+1)$ points.

In each $4$ -tuple $(a,b,c,d)$ exactly one is of a different parity from the rest, depending on whether $p\equiv1$ or $3 (mod 4)$ . Restricting to solutions where the first coordinate is non-negative, having different parity from the rest (in case the first coordinate is $0$ , we pick one of the two solutions $\alpha, -\alpha$ to be canonical), this way we obtain exactly $p+1$ solutions.

Let $S'_p = \{ \alpha_1, \bar{\alpha_1}, \cdots, \alpha_k, \bar{\alpha_k}, \beta_1, \cdots, \beta_l \}$ be this set of $p+1$ points on the sphere. Note that the $\beta$ s represent the solutions where the first coordinate is exactly $0$ .

Check that $S'_p$ generates $\Lambda'$ .

We have $\alpha_i \bar{\alpha_i} = p$ and $-\beta_j^2 = p$ . By definition $S'_p \subseteq \Lambda'$ and $Q$ is injective on $S'_p$ . Let $S_p = Q(S'_p)$ .

Consider the Cayley graph $\mathcal G (\Lambda, S_p)$ , this is a $(p+1)$ -regular graph. Since $S_p$ generares $\Lambda$ , $\mathcal G (\Lambda, S_p)$ is connected.

Claim: $\mathcal G (\Lambda, S_p)$ is a tree.

Suppose not, let $(v_0, v_1, \cdots, v_k=v_0)$ a non-trivial cycle. $k \geq 2$ . Since $\mathcal G$ is a Cayley graph, we may assume $v_0 = e$ .

Hence $v_1 = \gamma_1, \ v_2 = \gamma_1\gamma_2, \cdots, v_k = \gamma_1 \cdots \gamma_k$ , for some $\gamma_1, \cdots, \gamma_k \in S_p$ .

Since $v_{i-1} \neq v_{i+1}$ for all $1\leq i \leq k-1$ , the word $\gamma_1, \cdots, \gamma_k$ cannot contain either $\alpha_i\bar{\alpha_i}$ or $\beta_i^2$ , hence cannot be further reduced.

$\gamma_1, \cdots, \gamma_k = e$ in $\Lambda$ means for some $m, n$ we have

$\pm p^n \gamma_1, \cdots, \gamma_k = p^m$ .

Since every word in $\Lambda'$ with norm $N(\alpha) = p^k$ must have a unique factorization $\alpha = \pm p^r w_m$ where $w_m$ is a reduces word of length $m$ in $S'_p$ and $2r+m = k$ .

Contradiction. Establishes the claim.

Now we reduce the group $\mathbb H (\mathbb Z)$ mod $q$ :

$\pi_q: \mathbb H (\mathbb Z) \rightarrow \mathbb H (\mathbb{F}_q)$

One can check that $\pi_q(\Lambda') = \mathbb H (\mathbb{F}_q)^\times$ .

Let $Z_q = \{ \alpha \in \mathbb H (\mathbb{F}_q)^\times \ | \ \alpha = \bar{\alpha} \}$ , $Z_q < \mathbb H (\mathbb{F}_q)^\times$ is a central subgroup.

For $\alpha, beta \in \Lambda'$ , $\alpha \sim \beta \Rightarrow \pi_q(\alpha)^{-1}\pi_q(\beta) \in Z_q$ . Which means we have well defined homomorphism

$\Pi_q: \Lambda \rightarrow \mathbb H (\mathbb{F}_q)^\times / Z_p$ .

Let $T_{p,q} = \Pi_q(S_p)$ , if $q > 2\sqrt{q}$ we have $\Pi_q$ is injective on $S_p$ and hence $latex $| T_{p,q} | = p+1$ .

Now we are ready to define our expanding family:

$X^{p,q} = \mathcal{G}( \Pi_q(\Lambda), T_{p,q})$ .

Since $S_p$ generates $\Lambda$ , $T_{p,q}$ generates $\Pi_q(\Lambda)$ . Hence $X^{p,q}$ is $(p+1)$ -regular and connected.

Theorem 1: $g(X^{p,q}) \geq 2 \log_p(q)$

Let $(e, v_1, \cdots, v_k=e)$ be a cycle in $X^{p,q}$ , there is $t_1, \cdots, t_k \in T_{p,q}$ such that $v_i = t_1 t_2 \cdots t_k$ for $1 \leq i \leq k$ .

Let $\gamma_i = \Pi_q^{-1}(t_i), \ \gamma_i \in S_p$ , $\alpha = a_0 + a_1 i+a_2 j +a_3 k = \gamma_1 \cdots \gamma_k \in \Lambda$ . Note that from the above arguement we know $\alpha$ is a reduced word, hence $\alpha \neq e_{\Lambda}$ . In particular, this implies $a_1, a_2, a_3$ cannot all be $0$ .

Also, since $\alpha$ is reduced, $\displaystyle N(\alpha) = \Pi_{i=1}^k N(\gamma_i) = p^k$ .

By Lemma, since $\Pi_q(\alpha) = 1$ , $\alpha \in \mbox{ker}(\Pi_q)$ hence $q$ divide $a_1, a_2, a_3$ , we conclude

$N(\alpha) = a_0^2 + a_1^2 +a_2^2 +a_3^2 \geq q^2$

We deduce $p^k \geq q^2$ hence $k \geq \log_p(q)$ for all cycle. i.e. $g(X^{p,q}) \geq \log_p(q)$ .

Theorem 2: If $q$ does not divide $p$ and $p$ is not a square mod $q$ (i.e. $(\frac{p}{q}) = -1$ ), then $g(X^{p,q}) \geq 4 \log_p(q) - \log_p(4)$ .

For any cycle of length $k$ as above, we have $N(\alpha) = p^k \equiv a_0^2 (\mbox{mod} \ q)$ , i.e. $(\frac{p^k}{q}) = 1$ .