Math sunday

I had a chill day thinking about math today without any pressure whatsoever. First I figured out, calculating inductively, that the order of GL_n(\mathbb{F}_p) is (p^n - 1)(p^n - p)(p^n - p^2)\cdots (p^n - p^{n-1}). You calculate the number of k-tuples of column vectors linear independent and from there derive p^k as the number of vectors that cannot be appended if linear independence is to be preserved. A Sylow p-group of that is the group of upper triangular matrices with ones on the diagonal, which has the order p^{n(n-1)/2} that we want.

I also find the proof of the first Sylow theorem much easier to understand now, the inspiration of it. I had always remembered that the Sylow p-group we are looking for can be the stabilizer subgroup of some set of p^k elements of the group where p^k divides the order of the group. By the pigeonhole principle, there can be no more than p^k elements in it. The part to prove that kept boggling my mind was the reverse inequality via orbits. It turns out that that can be viewed in a way that makes its logic feel much more natural than it did before, when like many a proof not understood, seems to spring out of the blue.

We wish to show that the number of times, letting p^r be the largest pth power dividing n, that the order of some orbit is divided by p is no more than r-k. To do that it suffices to show that the sum of the orders of the orbits, \binom{n}{p^k} is divided by p no more than that many times. To show that is very mechanical. Write out as m\displaystyle\prod_{j = 1}^{p^k-1} \frac{p^k m - j}{p^k - j} and divide out each element of the product on both the numerator and denominator by p to the number of times j divides it. With this, the denominator of the product is not a multiple of p, which means the number of times p divides the sum of the orders of the orbits is the number of times it divides m, which is r-k.

Following this, Brian Bi told me about this problem, starred in Artin, which means it was considered by the author to be difficult, that he was stuck on. To my great surprise, I managed to solve it under half an hour. The problem is:

Let H be a proper subgroup of a finite group G. Prove that the conjugate subgroups of H don’t cover G.

For this, I remembered the relation |G| = |N(H)||Cl(H)|, where Cl(H) denotes the number of conjugate subgroups of H, which is a special case of the orbit-stabilizer theorem, as conjugation is a group action after all. With this, given that |N(H)| \geq |H| and that conjugate subgroups share the identity, the union of them has less than |G| elements.

I remember Jonah Sinick’s once saying that finite group theory is one of the most g-loaded parts of math. I’m not sure what his rationale is for that exactly. I’ll say that I have a taste for finite group theory though I can’t say I’m a freak at it, unlike Aschbacher, but I guess I’m not bad at it either. Sure, it requires some form of pattern recognition and abstraction visualization that is not so loaded on the prior knowledge front. Brian Bi keeps telling me about how hard finite group theory is, relative to the continuous version of group theory, the Lie groups, which I know next to nothing about at present.

Oleg Olegovich, who told me today that he had proved “some generalization of something to semi-simple groups,” but needs a bit more to earn the label of Permanent Head Damage, suggested upon my asking him what he considers as good mathematics that I look into Arnold’s classic on classical mechanics, which was first to come to mind on his response of “stuff that is geometric and springs out of classical mechanics.” I found a PDF of it online and browsed through it but did not feel it was that tasteful, perhaps because I’m been a bit immersed lately in the number theoretic and abstract algebraic side of math that intersects not with physics, though I had before an inclination towards more physicsy math. I thought of possibly learning PDEs and some physics as a byproduct of it, but I’m also worried about lack of focus. Maybe eventually I can do that casually without having to try too hard as I have done lately for number theory. At least, I have not the right combination of brainpower and interest sufficient for that in my current state of mind.

一说起偏微分方程,想到此行有不少杰出的浙江裔学者,最典型的可以说是谷超豪。想起,华盛顿大学一位做非交换代数几何的教授,浙江裔也,的儿子,曾经说起他们回国时谷超豪,复旦的,如他父亲一样,逝世了,又半开玩笑言:“据说谷超豪被选为院士,是因为他曾经当过地下党。”记得看到杨振宁对谷超豪有极高的评价,大大出于谷超豪在杨七十年代访问复旦的促动下解决了一系列有关于杨-米尔斯理论的数学问题。之外,还有林芳华,陈贵强,都是非常有名气的这套数学的教授,也都是浙江人。我们都知道浙江人是中国的犹太人,昨天Brian Bi还在说”there are four times more Zhejiangnese than Jews.” 可惜我不是浙江人,所以成为数学家可能希望不大了。:(

Composition series

My friend after some time in industry is back in school, currently taking graduate algebra. I was today looking at one of his homework and in particular, I thought about and worked out one of the problems, which is to prove the uniqueness part of the Jordan-Hölder theorem. Formally, if G is a finite group and

1 = N_0 \trianglelefteq N_1 \trianglelefteq \cdots \trianglelefteq N_r = G and 1 = N_0' \trianglelefteq N_1' \trianglelefteq \cdots \trianglelefteq N_s' = G

are composition series of G, then r = s and there exists \sigma \in S_r and isomorphisms N_{i+1} / N_i \cong N_{\sigma(i)+1} / N_{\sigma(i)}.

Suppose WLOG that s \geq r and as a base case s = 2. Then clearly, s = r and if N_1 \neq N_1', N_1 \cap N_1' = 1. N_1 N_1' = G must hold as it is normal in G. Now, remember there is a theorem which states that if H, K are normal subgroups of G = HK with H \cap K = 1, then G \cong H \times K. (This follows from (hkh^{-1})k^{-1} = h(kh^{-1}k^{-1}), which shows the commutator to be the identity). Thus there are no other normal proper subgroups other than H and K.

For the inductive step, take H = N_{r-1} \cap N_{s-1}'. By the second isomorphism theorem, N_{r-1} / H \cong G / N_{s-1}'. Take any composition series for H to construct another for G via N_{r-1}. This shows on application of the inductive hypothesis that r = s. One can do the same for N_{s-1}'. With both our composition series linked to two intermediary ones that differ only between G and the common H with factors swapped in between those two, our induction proof completes.

Automorphisms of quaternion group

I learned this morning from Brian Bi that the automorphism group of the quaternion group is in fact S_4. Why? The quaternion group is generated by any two of i,j,k all of which have order 4. \pm i, \pm j, \pm k correspond to the six faces of a cube. Remember that the symmetries orientation preserving of cube form S_4 with the objects permuted the space diagonals. Now what do the space diagonals correspond to? Triplet bases (i,j,k), (-i,j,-k), (j,i,-k), (-j,i,k), which correspond to four different corners of the cube, no two of which are joined by a space diagonal. We send both our generators i,j to two of \pm i, \pm j, \pm k; there are 6\cdot 4 = 24 choices. There are by the same logic 24 triplets (x,y,z) of quaternions such that xy = z. We define an equivalence relation with (x,y,z) \sim (-x,-y,z) and (x,y,z) \sim (y,z,x) \sim (z,x,y) that is such that if two elements are in the same equivalence class, then results of the application of any automorphism on those two elements will be as well. Furthermore, no two classes are mapped to the same class. Combined, this shows that every automorphism is a bijection on the equivalence classes.


上周底,又跑湾区一趟,为了面试,也为了玩。这次受益匪浅,拿到了比较好的工作,同时也再次得到学习数学的启发。我的一位不善学,疯疯癫癫的,苏犹半朋友,却建议我跟一位正在MIT学数学的美国IMO金牌得主聊天。此人我已被介绍过,通过一位“知名的高才生中间人”,可与此人未说任意有含量的话,从而想这牛人太忙,与我这庸人无话可说。出乎意料,介绍者却说他与牛人沟通频繁,并且将我加入他们俩人的脸书群,后来又加了一位不相信智商,反徐道辉的,女生物博士生,犹裔也。面试之前的晚上,我住在旧金山的宾馆,附近有一家“现代犹太博物馆”,好奇去看了看,楼上关门,楼下没啥好看的。我们在群里所讨论的好多与种族,文化,智商,和学科相关,还记得我曾经对数学尖子开玩笑,美国IMO选手,非亚裔,比犹裔,而他似乎未感到我的玩笑口气,回说他那界有一两位非犹太白人。他还强调自己很美国人,不是那种在以色列待过的。高中时,他选了中文为他的外语,以童话为他爱听的一首中文歌。学术上,给的感觉是专注,单一的纯数学本科生,非常肯定他会走学术道路。他的具体数学兴趣及倾向为组合数学和理论计算机和解析数论。那天晚上,问他知道那几个二次互反律(law of quadratic reciprocity)的证明,他回答一个引用Zolotarev’s lemma的,并且发了个链接。当时,我只知道高斯和(Gauss sum)的那个,而细节已经记不清楚了。我花了一小时细读那个证明,领悟后感觉漂亮无比,引用的工具极其简单。从来没有想到可以将这数论皇后的定理视为,表达为置换的奇偶的积,毕竟Legendre symbol给的是1或-1,与sgn一样,好妙啊。回顾透明Legendre symbol给的基本是在给循环阿贝尔群(\mathbb{Z}/{p\mathbb{Z}})^{\times}的元素奇偶,二次剩余和偶置换在他们对应母群都是指数为2的子群。这又让我想到高斯对于正十七边形可作图的证明也是引用指数2的子群,其由Galois theory对应于度数为2的域扩张。过两天,我又学到了Gauss lemma,就是\left(\frac{a}{p}\right) = (-1)^n, n\{a, 2a, \ldots, \frac{p-1}{2}a\}大于p/2的元素的数量。证明思路很直接,将\{a, 2a, \ldots, \frac{p-1}{2}a\}的大于p/2的元素负掉,可和其他元素从新凑成\{1, 2, \ldots, \frac{p-1}{2}\}. Eisenstein对该定理的证明,我以前知道其存在但没看懂的,引用类似于Gauss lemma的引理,思路及证明策略抓住,这次却清晰了然。二次互反律的美妙我之前无法欣赏,记得对此定理有过一种稀奇古怪,难以思议之感,是没有抓住并且悟觉它的美妙的对称结构。想起在Eisenstein的证明中,画了一个pq的格子,将-1的次数示为格子的下左象限所有的点数,此为(p-1)(q-1)/4的来源。

数论是纯数学比较活的分支,与现在被我看为形式化繁琐枯燥的测度论相反。回想起,我学测度论习题做不出来开始大大怀疑自己数学的能力并且对数学稍失去了兴趣。而数论从某种角度而言有相反的作用。昨天,我从新过了Bertrand’s postulate的源于Erdos的证,对此同样有新的见解,至少感觉是这样。这次很明确它是以好紧限的有易与素数次数相连的\binom{2n}{n}在假设n2n范围无素数情况下,导致未成立的不等式。证明里的关键观察是2n/3n之间的素数不整除,此有大大减小上限的作用。


Galois group of x^10+x^5+1

This was a problem from an old qualifying exam, that I solved today, with a few pointers. First of all, is it reducible? It actually is. Note that x^{15} - 1 = (x^5-1)(x^{10}+x^5+1) = (x^3-1)(x^{12} + x^9 + x^6 + x^3 + 1). 1 + x + x^2, as a prime element of \mathbb{Q}[x] that divides not x^5-1 must divide the polynomial, the Galois group of which we are looking for. The other factor of it corresponds to the multiplicative group of \mathbb{F}_{15}, which has 8 elements. Seeing that it has 3 elements of order 2 and 4 elements of order 4 and is abelian, it must be C_2 \times C_4. Thus, the answer is C_2 \times C_2 \times C_4.

More math

Last night, I learned, once more, the definition of absolute continuity. Formally, a function f : X \to Y‘s being absolutely continuous is its for any \epsilon > 0, having a \delta > 0 such that for any finite number of pairs of points (x_k, y_k) with \sum |x_k - y_k| < \delta implies \sum |f(x_k) - f(y_k)| < \epsilon. It is stronger than uniform continuity, a special case of it. I saw that it implied almost everywhere differentiability and is intimately related to the Radon-Nikodym derivative. A canonical example of a function not absolute continuous but uniformly continuous, to my learning last night afterwards, is the Cantor function, this wacky function still to be understood by myself.

I have no textbook on this or on anything measure theoretic, and though I could learn it from reading online, I thought I might as well buy a hard copy of Rudin that I can scribble over to assist my learning of this core material, as I do with the math textbooks I own. Then, it occurred to me to consult my math PhD student friend Oleg Olegovich on this, which I did through Skype this morning.

He explained very articulately absolute continuity as a statement on bounded variation. It’s like you take any set of measure less than \delta and the total variation of that function on that set is no more than \epsilon. It is a guarantee of a stronger degree of tightness of the function than uniform continuity, which is violated by functions such as x^2 on reals, the continuity requirements of which increases indefinitely as one goes to infinity and is thereby not uniformly continuous.

Our conversation then drifted to some lighter topics, lasting in aggregate almost 2 hours. We talked jokingly about IQ and cultures and politics and national and ethnic stereotypes. In the end, he told me that введите общение meant “input message”, in the imperative, and gave me a helping hand with the plural genitive conjugation, specifically for “советские коммунистические песни”. Earlier this week, he asked me how to go about learning Chinese, for which I gave no good answer. I did, on this occasion, tell him that with all the assistance he’s provided me with my Russian learning, I could do reciprocally for Chinese, and then the two of us would become like Москва-Пекин, the lullaby of which I sang to him for laughs.

Back to math, he gave me the problem of proving that for any group G, a subgroup H of index p, the smallest prime divisor of |G|, is normal. The proof is quite tricky. Note that the action of G on G / H induces a map \rho : G \to S_p, the kernel of which we call N. The image’s order, as a subgroup of S_p must divide p!, and as an isomorphism of a quotient group of G must divide n. Here is where the smallest prime divisor hypothesis is used. The greatest common divisor of n and p! cannot not p or not 1. It can’t be 1 because not everything in G is a self map on H. N \leq H as everything in N must take H to itself, which only holds for elements of H. By that, [G:N] \geq [G:H] = p which means N = H. The desired result thus follows from NgH = gH for all g \in G.

Later on, I looked at some random linear algebra problems, such as proving that an invertible matrix A is normal iff A^*A^{-1} is unitary, and that the spectrum of A^* is the complex conjugate of the spectrum of A, which can be shown via examination of A^* - \lambda I. Following that, I stumbled across some text involving minors of matrices, which reminded me of the definition of determinant, the most formal one of which is \sum_{\sigma \in S_n}\mathrm{sgn}(\sigma)\prod_{i=1}^{n}a_{i,\sigma_{i}}. In school though we learn its computation via minors with alternating signs as one goes along. Well, why not relate the two formulas.

In this computation, we are partitioning based on the element that 1 or any specific element of [n] = \{1, 2, \ldots, n\}, with a corresponding row in the matrix, maps to. How is the sign determined for each? Why does it alternate. Well, with the mapping for 1 already determined in each case, it remains to determine the mapping for the remainder, 2 through n. There are (n-1)! of them, from \{2, 3, \ldots, n\} to [n] \setminus \sigma_1. If we were to treat 1 through i-1 as shifted up by one so as to make it a self map on \{2, 3, \ldots, n\} then each entry in the sum of the determinant of the minor would have its sign as the sign of the number of two cycles between consecutive elements (which generate the symmetric group). Following that, we’d need to shift back down \{2, 3, \ldots, i\}, the presentation of which, in generator decomposition, would be (i\ i+1)(i-1\ i) \ldots (1\ 2), which has sign equal to the sign of i, which is one minus the column we’re at, thereby explaining why we alternate, starting with positive.