# Leetcode Contest 22

class Solution(object):
def findPairs(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if k < 0:
return 0
ans = 0
d = {}
for n in nums:
d[n] = d.get(n, 0) + 1
if k == 0:
for a, b in d.items():
if b > 1:
ans += 1
else:
for a in d.keys():
if a+k in d:
ans += 1
return ans


# Leetcode Contest 21

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = []
def inorder(root):
if not root:
return
inorder(root.left)
ans.append(root.val)
inorder(root.right)
inorder(root)
return min(ans[i+1]-ans[i] for i in xrange(len(ans)-1))


# Leetcode Contest 20

class Solution(object):
def detectCapitalUse(self, word):
"""
:type word: str
:rtype: bool
"""
if all('A' <= c <= 'Z' for c in word):
return True
if all('a' <= c <= 'z' for c in word):
return True
return 'A' <= word[0] <= 'Z' and all('a' <= c <= 'z' for c in word[1:])


# Idempotented algebra

This post is a reading note to Bernstein’s Le “centre” de Bernstein, on the part of idempotented algebras (section 1.1 to 1.7, ibid.). Let $R$ be a ring, an element $e$ is called an idempotent if $e^2=e$. Let $k$ be a field.

Definition 1. A $k$-idempotented algebra $(H, I)$ is a $k$-algebra $H$ together with the set idempotents $I$ satisfying

(*) For any finite family $(x_i)$, there exists an idempotent $e \in I$ such that $ex_ie = x_i$ for all $i$.

The $k$-structures of $H$ is not involved in the discussion of this post, so we will ignore it. Let $(H, I)$ be an idempotented algebra for the rest of the post.

Lemma 2. Let $e, f \in I$. The following are equivalent.

(1) $eHe \subset fHf$
(2) $e \in fHf$
(3) $e = fef$

# 我的2015

Quand on voit ce qu'on fut sur terre et ce qu'on laisse
Seul le silence est grand; tout le reste est faiblesse

－－－－－

2015年中我觉得对我最重要的事情就是换导师了。我原来的导师Prof. Yuval Flicker今年三四月份的时候退休了，我只好另选导师了。我对表示论感兴趣，但是系里只有三两个教授在做表示论，再仔细考虑一下自己以后可能要做的方向，那么就只剩下Prof. Yuval Flicker和Prof. James Cogdell了。我并没有其他选择，所以当Prof. Flicker退休之后，我在他们两人都同意之下，就正式更换了导师。Prof. Cogdell主要的工作在于L函数方面，所以我慢慢也往L函数这个方向靠拢了。如果现在有人问我是做什么方向的，我会回答是Representation theory of p adic groups。而现在我主要的研究一些表示的L函数的性质。在Prof. Cogdell的帮助下，我在12月考过了Candidacy Exam。希望我能在2016年里做出一些成果。

# Gelfand pairs of finite groups

In this post, I mainly focus on introducing Gelfand pairs of finite groups.

### Representations of finite groups

Let’s recall some concepts. Let $G$ be a finite group. A (complex) representation of $G$ is a pair $(\rho, V)$ where $V$ is a vector space over $\C$ and $\rho: G \to GL(V)$ is a group homomorphism. Let $(\rho_1, V_1)$ and $(\rho_2, V_2)$ be representations of $G$, a $G$-morphism, or simply a morphism, between these two representations is a linear map $\varphi: V_1 \to V_2$ such that for any $g \in G$ and $v \in V_1$, $\varphi(\rho_1(g)v) = \rho_2(g)\varphi(v).$ Then $\mathrm{Hom}_G(\rho_1, \rho_2)$, the set of morphisms between $\rho_1$ and $\rho_2$, is a vector space over $\C$. A representation $(\rho, V)$ is irreducible, if there is no proper subspace $W \subset V$, such that $\rho(g)w \in W$ for any $g \in G$ and $w \in W$. Between irreducible representations, we have Schur’s lemma.

Theorem 1 (Schur’s lemma). Let $\rho_1$ and $\rho_2$ be irreducible representations of $G$. Then $\begin{equation*} \mathrm{Hom}_G(\rho_1, \rho_2) \cong \left\{ \begin{array}{ll} \C, & \text{ if } \rho_1 \cong \rho_2; \\ 0, & \text{ otherwise.} \end{array} \right. \end{equation*}$

It’s well known that $G$ is semisimple, i.e., any representation of $G$ decomposes into a direct sum of irreducible representations. A representation $(\rho, V)$ of $G$ is called multiplicity free, if any irreducible representation appearing in the decomposition of $(\rho, V)$ appears exactly once, up to isomorphism.

Let $H$ be a subgroup of $G$. If $(\rho, V)$ is a representation of $G$, we can certainly restrict the group homomorphism $\rho: G \to GL(V)$ to $H$ so that we can regard $(\rho, V)$ as a representation of $H$. This is called the restriction of representations from $G$ to $H$, and the restricted representation of $\rho$ will be denoted as $r^G_H(\rho)$. Conversely, if $(\pi, W)$ is a representation of $H$, we can build a representation $(\rho, V)$ of $G$ out of $\pi$, which is the induced representation, as follow.

# Unfolding of a global integral for $GL_n \times GL_m$

Let $(\pi, V_\pi)$ and $(\pi^\prime, V_{\pi^\prime})$ be cuspidal, unitary, irreducible automorphic representations of $GL_n(\mathbb{A})$ and $GL_m(\mathbb{A})$ respectively. We assume $m < n$. Let $\varphi \in V_\pi$ and $\varphi \in V_{\pi^\prime}$. To pair $\varphi$ and $\varphi^\prime$ suitably together, we first need to project $\varphi$ correspondingly.

Let $\psi$ be a additive continuous automorphic character of $\mathbb{A}$. We can extend it to a character of $N_n(\mathbb{A})$, the standard Borel subgroup of $GL_n(\mathbb{A})$, in the standard way: $\psi(u) = \psi\left(\sum_{i=1}^{n-1}u_{i,i+1}\right),$ for $u = (u_{i,j}) \in N_n(\mathbb{A})$. Let $Y=Y_{n, m}$ be the standard unipotent radical associated to the partition $(m+1, 1, \dots, 1)$ of $GL_n$, i.e., $Y=\left\{\left(\begin{array}{cc}I_{m+1}&*\\ 0&u\end{array}\right): u \in N_{n-m-1}\right\} \subset N_n.$ Let $P_{m+1}$ be the mirabolic subgroup of $GL_{m+1}$, then for $p \in P_{m+1}(\mathbb{A})$ define $\mathbb{P}^n_m \varphi(p) = |\det p|^{-\frac{n-m-1}{2}}\int_{Y(k)\backslash Y(\mathbb{A})} \varphi\left(y\left(\begin{array}{cc} p& \\ & I_{n-m-1} \end{array}\right)\right)\psi^{-1}(y) dy.$

Now we can pair $\varphi$ and $\varphi^{\prime}$ in the following way: $I(s; \varphi, \varphi^\prime) = \int_{GL_m(k)\backslash GL_m(\mathbb{A})} \mathbb{P}^n_m \varphi\left(\begin{array}{cc} h& \\ &1\end{array}\right)\varphi^\prime(h)|\det h|^{s-\frac{1}{2}}dh.$

# Nontrivial bound for a sum involving characters

To find a non-trivial bound for an expression is an essential task in analytic number theory. For example, to derive a asymptotic formula for the number of primes less than or equal to $x$, i.e. $\pi(x)$, we investigate into the function $\Psi(x) = \sum_{\substack{n \le x \\ n = p^k}} \log p.$ Along the way to the asymptotic formula for $\Psi(x)$, it’s important to bound the error terms so that they won’t overweight the dominant term. Nowadays, many mathematicians are interested in finding non-trivial bounds for weighted $\Psi(x)$, i.e., $\Psi(x) = \sum_{\substack{n \le x \\ n = p^k}} a_n \log p,$ where $a_n \in \C$. If $a_n = \chi(n)$ for some character $\chi \text{ mod }q$, this is actually $\Psi(x, \chi)$. Trivially, we can have $\left\lvert \Psi(x) \right\rvert \le \sum_{\substack{n \le x \\ n = p^k}} |a_n| \log p.$ Therefore, it seems that we can just work with $a_n \in \R_{\ge 0}$. Truly, this will give us a bound for $\Psi(x)$, but it ignores all the cancellation encoded in the signs of $a_n$, thus it won’t provide any good bounds.

Another kind of expressions that many mathematicians work with are those sums involving characters. The simplest example is $\displaystyle \sum_{n=m+1}^{m+N} \chi(n)$ for a character $\chi \text{ mod }q$. The trivial bound for it is $N$, since $|\chi(n)| \le 1$, which is certainly a coarse bound. Actually, we have

Theorem 1 (Pólga-Vinogradov inequality). Let $\chi \text{ mod }q$ be a primitive character and $q \ge 3$. Then $\left\lvert \sum_{n=m+1}^{m+N} \chi(n) \right\rvert < \sqrt{q}\log q.$

This non-trivial bound doesn’t depend on the length $N$ at all, but only depends on the modulus $q$. If the primitive condition is dropped, then it is bounded by $2 \sqrt{q}\log q$.

In this post, I will give a non-trivial bound for the sum $\displaystyle \sum_{n=1}^{N} \chi(n)\chi(n+1)$, which was originally asked by my friend Yongxiao, as a practice for my analytic number theory course.

# 2014年

2014年我经历了哥村的零下20度，听了马友友的小提琴，暑假回国跟亲人好友见面，过了口语可以教书，选了导师成了Tango Club的President，第一次教书是教微积分1，现在在Florida的迪士尼等烟花。新年快乐。

Let $G$ be a group. A linear representation of $G$ is a pair $(\rho, V)$, where $V$ is a finite dimensional vector space over $\mathbb{C}$ and $\rho: G \to GL(V)$ is a group homomorphism. Without ambiguity, we will call $\rho$ a representation of $G$. Let $(\rho_1, V_1)$ and $(\rho_2, V_2)$ be two representations of $G$, an intertwining operator between them is a linear map $T: V_1 \to V_2$ such that for any $g \in G$, the following diagram commutes: $$$\label{eq:diagram} \require{AMScd}\begin{CD} V_1 @>T>> V_2 \\ @V{\rho_1(g)}VV @VV{\rho_2(g)}V \\ V_1 @>T>> V_2 \end{CD}$$$ Let $\text{Hom}_G(\rho_1, \rho_2)$ be the space of all intertwining operators between $\rho_1$ and $\rho_2$.
Let $(\rho, V)$ be a representation of $G$. Let $H$ be a subgroup of $G$, then we can restrict $\rho$ to $H$ to get a representation of $H$. We will use $\text{Res}^G_H \, \rho$ to denote the restricted representation of $H$ from $\rho$. Conversely, if $\pi$ is a representation of $H$, then we can construct a representation of $G$ from $\pi$, which is known as induced representation of $G$ from $\pi$, denoted as $\text{Ind}_H^G \, \pi$. In this post, I will first talk about the precise description of induced representations and the relations between $\text{Res}^G_H$ and $\text{Ind}_H^G$. I will then discuss Mackey’s theorem, which dictates a further relation between restricted and induced representations.