今晚吃的是韩式烧烤：羊肉和豆腐。

这次比赛有四题，题目都比较基础，可惜打错了一个变量名字WA了一次。

第一题Diameter of Binary Tree

递归想法：对于每个树节点，计算经过该树节点最长路径的长度。只要修改求每个节点高度的程序就行。先算当前左子树的高度l和右子树的高度r，那么以该经过该节点最长路径的长度就是l+r+1，然后返回该节点的高度max(l, r)+1

# 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 diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        def height(root, ans):
            if not root:
                return 0
            l = height(root.left, ans)
            r = height(root.right, ans)
            ans[0] = max(ans[0], l+r+1)
            return max(l, r)+1

        ans = [0]
        height(root, ans)
        return ans[0]-1

今晚有手撕鸡，玉米鸡汤，红烧牛排骨和金鲳鱼。本来还准备了要做个豆豉炒苦瓜的，但是那手撕鸡实在太大了，所以就苦瓜没有必要做了。这手撕鸡很好吃：先是用鸡熬两个小时做鸡汤，然后将鸡过冷水去骨撕条，在鸡肉上放上辣椒面与白芝麻并浇以热油，最后加上些许醋拌匀即可。

这次比赛比较简单，但是还是WA了两次了，顺带吐槽一下自己写代码的速度。

第一题Reverse String II

没什么好说的，就直接干就好：首先将字符串按长度为2k分块，然后处理每一个分块。

class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        lst = []
        for i in xrange(0, len(s), 2*k):
            lst.append(s[i:i+2*k])
        for i, s in enumerate(lst):
            lst[i] = s[:k][::-1]+s[k:]
        return ''.join(lst)

今晚吃得有点撑：排骨汤，花池鱼，红烧羊肉和炒青菜。

除了第一题WA了一次之外，其他三题都一次过了！

第一题K-diff Pairs in an Array。

思路比较简单：首先用哈希表统计所有数出现的频率。对于k＝0的情况，我们返回所有出现次数大于1的数的数目，对于k>0的情况，我们只要统计所有n+k也出现的数n的数目。对于k<0的情况，直接返回0。我第一次提交忘记考虑k<0的情况了。

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

今晚是一次丰盛的聚餐：羊肉汤，金鲳鱼，红烧排骨，炒牛肉和炒青菜。

这次比赛我全都做出来了！可惜前三题都WA了一次，而且都是粗心大意的错。

第一题Minimum Absolute Difference in BST，我采取了简单粗暴的方法：首先中序遍历将所有数放在一个数组里，然后返回相邻两个数之间差的最小值。

# 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))

这周六的菜单是牛排骨、金鲳鱼和土豆丝，甜点是蛋糕。

这次比赛有四题，我只做出来了前三道。

第一道是简单的字符串处理。

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:])

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.

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.

最近在练习法语翻译的时候遇到Vigny的两句诗¹：

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年里做出一些成果。

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.

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.

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.\]

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

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.