怀念Galois

  我的第一篇谈到具体学科的博客,还是献给我最钟爱的数学。

  个人比较喜欢离散数学,并非因为曲高和寡,而是因为数学分析、概率论、拓扑学、泛函之类的高手实在太多。而离散数学更为抽象,抽象到抽象代数直接以抽象二字命名,愿意去学习的人自然就少了,那么个人闲聊的时候忽悠的空间就会比较大,夸张夸张也没多少人看出自己其实是不学无术的。也正因为如此,喜欢离散数学,离散数学中最喜欢的就算是抽象代数了。

  数学是什么

  从人类原始社会起,人类与地斗,与天斗,物质资源极端匮乏,长期以往,人类对自己所控制的物质资源有了个量化的概念,再精确下去,就产生了计数。后来随着私有制的产生,加法、减法、乘法、除法也就慢慢产生了。农耕民族更容易更早产生面积的概念,从而产生几何学。Newton对于经典力学的奠基同时促进了数学的发展,尽管Newton所建立的微积分并未建立在无穷小分析基础之上,从而存在缺陷,这后来是Cauthy最终解决的,但无论如何,Newton是高等数学的祖师爷。之后源源不断的数学问题,解决过程中伴随着反复的抽象过程,从而不断建立新的数学学科,乃至完善。在数理逻辑完善前,人们认为数学是冥冥中注定的,它的底层是哲学保证的;然而在数理逻辑完善后,人们才意识到数学原来是自圆其说。

  再回到之前的这个问题,数学是什么,佛感觉一个无形的手在数学后面推着,数学是什么可能真的是一个见仁见智的问题。而我却总是意淫式的觉得数学是和我们物理的宇宙不一样的一个虚拟宇宙,是一切推理的抽象。

  尺规作图

  尺规作图是古老的几何问题,它模拟了一个无限长的直尺以及一个可以任意半径的圆规,其规则如下:

  1.过任意两个不同的已知点可以作过两点的一条直线。

  2.任意两条直线,其交点为已知点。

  3.任意两个圆,其交点为已知点。

  4.以已知点为圆心,以任意两个已知点之间的距离为半径,作圆。

  5.作图只能在以上4条的有限步骤之内完成。

  初始的时候,至少要有两个已知点。

  从古希腊开始,人们就被三大尺规作图问题困扰:

  1.立方倍积:已知线段a,做图得到体积为2*a3的正方体的边长。

  2.画圆为方:已知道线段a,作图得到面积为π*a2的正方形的边长。

  3.三等分角:已知道角度a,作图得到角度a/3。

  一元五次方程求解

  早在古希腊的时候,人们就知道一元二次方程如何根式求解。

  十六世纪之前,人们一直认为一元三次方程如同三大尺规作图一样,基本无法得到根式解的。十六世纪的时候,意大利数学家Ferro解出了形如x3+m*x+n=0这样的一元三次方程的根式解,Tartaglia彻底解决了一元三次方程的根式求解,直到Ferrari搞定一元四次方程根式求解问题。至此,一元三次方程、一元四次方程都有了根式求解,且都是被意大利数学家解决的。

  以后的连绵两三个世纪,人们在探索着一元五次方程的根式解,可是却一直没法解决。

  冥冥中注定了,此问题最终成就了数学史上的大事。

  Galois

  现在轮到我们的主角出场了。

  Galois 1811年10月25日出生,父亲是一个市长,当时的法国处于革命的热潮之中,他的父亲也是一个革命的支持者。受其父亲的影响,Galois短暂的一生与法国革命有着重要的关系,作为一位革命者,有着革命志士的情怀与浪漫。

  Galois从小就表现出很高的天分,但自从学习了数学之后对其他的科目再无兴趣。最终又因为糟糕的表达能力,最终无法被其向往的综合工科大学录取。在他第二次报考该大学的时候,他父亲在选举中又被人恶意中伤而自杀,这对他打击很大,从而第二次报考依然无法被录取。名落孙山的他最终来到了一个师范大学。

  自从学习了数学之后,Galois想与前人一样,来攻占一元五次方程的数学堡垒。最终证明了其实一元n次方程(n≥5)是不存在通用的根式求解的。

我来换句话来说明Galois到底证明了什么,用程序员听的懂的语言。先建立这么5个复数上的函数:

  (1)    复数加法

  (2)    复数减法

  (3)    复数乘法

  (4)    复数除法

  (5)    正整数次根

  严格的说,正整数次根不能算一个函数,因为一个不为0的复数会有n个n次根。但这n个不同的根的辅角是不一样的。于是可以把这个根式补充一下,从而成为一个函数:

      先定义复数的辅角在区间[0,2π)中取。函数sqrt(c, n, d),其中c是复数,n是正整数,d为小于等于n的正整数,代表复数c的n个n次根中辅角第d大的这个值。

      于是5个函数都有了。Galois证明的是,存在整系数的一元五次方程没有一个根可以通过任意整数有限次使用以上5个函数构造出来。

      再看看这个描述,是否觉得和之前的尺规作图看起来很像?是的,Galois也通过一样的模型证明了三大尺规作图问题是不可能完成的。

      Galois把他的研究成果写成论文,投给法国科学院,审稿人是Cauthy,一说是Gauss,反正是这两大牛中的一个。结果据说还是由于Galois糟糕的表达能力,最终被这位审稿的大牛传为笑柄,连稿子都找不到了。Galois就这么被埋没了……

      Galois作为革命者曾经两度入狱,第二次入狱的中认识了狱医的女儿。疯狂的人有着疯狂的爱情,疯狂的爱情催生疯狂的举动,终于,Galois和他的情敌——另外一个有着贵族身份的革命者,相约决斗。决斗前夕,可能因为Galois的情敌是位神枪手,他已经预见了自己的结局,连夜赶出61页的稿子,并交给了他的朋友,这是1832年5月28日夜。5月30日清晨时分,一位农民在巴黎的葛拉塞尔湖附近看到了重伤的他,送到医院。第二天,1832年5月31日早上,也就是185年前的今天,Galois不治身亡,死前,对他身边哭泣的弟弟说:“不要哭,我需要足够的勇气在20岁的年纪死去”。死后,尸体在公墓边随便葬了,至今难寻踪迹。

   抽象代数

      Gailos死后几十年,手稿到了一个三流数学家手中。这位数学家耐心的看完手稿,并细心研究他的成果,惊为天人。

      Galois为群论奠基,并梳理了域论的一些东西,正是以此为工具,Galois解决了一元n次方程根式求解、三大作图问题,以及所有可以用尺规作图作出的正n边形的n满足的条件。牛的不是后面的结果,而是这个工具,那是一个让人激动的学科,有的人说,牛顿的微积分再晚些时候也会有人创造出来,而这种看待数学的思维却非得这种不世出的天才不可。相比来说,Gauss对于数学的贡献,光从境界上看,就比Galois低了一个级别,而Galois是从本质上去看待数学这种学科。那完全是从另外一个角度来看待数学这个东西,那是一个从所有数学中提纯出来的东西,研究对象为前所未有的一个叫代数系统的东西,从而我们学过的所有数学归根结底上都成了抽象代数的一个数学建模(其实即便是底层如数理逻辑者也是受了抽象代数的启发)。大师已经指明了探索的方向,于是在接着的百年时间里,人们陆续完善了群论、环论、域论、格论、模论这些抽象代数的分支。

      一个月前,一同事研究加密解密的时候不理解Galois域(有限域的另一个名字,一般计算机里使用特征2域)的计算,来问我。他是一个打破沙锅问到底的家伙,我实在不忍心直接告诉他Galois域怎么计算加减乘除,当然即便我草草作答他也绝不会放过我。于是,我花了一个多小时从头到尾帮他了解了群、环、域,甚至于一些定理的证明,当然,他听的半懂半不懂倒也是真,不过倒是听的很有兴趣,那我也算是没白讲了。最后,一条vim galois_field.c命令准备用C语言现写Galois域的计算方法,不过由于他编程能力也很强,于是还没开写就打住了。我告诉他,其实作为工程师最多只要知道Galois域怎么算的,而至于我之前说的那么一大通数学理论,不明白倒也关系不大,而加密之所以一般采用Galois域,其原因之一也就是有限的存储之内可以让加减乘除都封闭。

      本文不打算解释Galois是怎么搞定这些问题的,这些在短短的章节恕我学艺不精实在没有那个水平写的通俗易懂,只是大致解释一下群论里相关的代数系统。

  n元运算:对于集合A上的一个n元运算,指的是A的n阶笛卡尔积An -> A的一个映射。以我匮乏的数学知识,实在不知道人类目前有没有研究超过二元运算的代数系统的一般理论。

      二元运算:对于集合A上一个二元运算,指AXA –> A的一个映射。

      半群:如果对于集合A上的一个二元运算,为了方便,用我们常用的数学符号来计,就叫a*b,如果对于A上的任何元素a、b、c,一定满足a*b*c = a*(b*c),也就是满足结合律,那么我们叫A在这个二元运算上构成一个半群。举个栗子,所有的偶数在数值乘法就合成一半群。其实,在群论里,我们一般都把这个运算叫乘法,当然此乘法非彼乘法。再举个极端的例子,对于所有实数,构造二元运算f(a,b),使得无论是什么实数a,b,f(a.b)都等于0,那么实数集在此f上也构成一个半群。

      带e元的半群:假如一个半群中,存在一个特别的元素b,使得集合中任意的a,都有a*b = e*b = a,那么我们就把这个b叫作e元,把这个半群叫作带e元的半群。这里还是举个例子,所有整数在数值乘法上就构成这样的一个带e元的半群,1就是这个e元。

      群:假如一个带e元的半群,对于集合中任何一个元素a,都可以找到集合中的一个b,使得a*b=b*a=e,那么我们就叫这个半群为群了,这里的a、b互为逆元。举个例子:所有非0实数在数值乘法上构成一个群,1是e元。注意,所有的实数在乘法上并无法构成一个群,因为0没有逆元。

      交换群:又叫Abel群,也就是乘法满足交换律的群,也就是对于集合上任意a,b,满足a*b=b*a。What?乘法居然不满足交换律?淡定,难道忘了矩阵的乘法是不可交换的吗?要知道,实数的n阶非奇异方阵在矩阵乘法上也是构成一个群的。另外,交换群除了Abel群之外,还有一个名字,叫加法群。

      子群:对于一个群,如果其子集在相同运算上依然合成一个群,那么这个新群叫这个群的子群。一个多于一个元素的群至少有两个子群,{e}和自身,这叫平凡子群。举个非平凡子群,实数集在加法上合成一个群,其子集有理数集在加法上也合成一群。

      到现在为止,还没介绍过有限的群。其实Galois域在加法上就是一个有限群,但这个例子不够好,因为我不打算介绍环、域了。如下构造一个n阶加法群(也就是群里有n个元素),取集合{0,1,2…n-1},也就是从0开始的连续n个整数构成的集合,定义乘法a*b为a+b除以n的余数,0是这个群的e元,任意一个元素a的逆元是n-a除以n的余数(也就是0的逆元是0,其他不为0的元素a的逆元是n-a)。此群有个名字,叫n阶循环群。再举个咱码农更容易理解的有限群例子:{真,假}在异或运算上是一个群,"假"是该群的e元,这个群同构于2阶循环群。

      群论就是研究群这样的代数系统的性质的学科,同理环论、域论、格论、模论。

      今天是Galois的忌日,延续了几天的文字还是在今天发到网上。偶尔,我还是会拿出抽象代数翻看翻看,看看那些极度抽象的运算、代数系统,也算是一种对大师的敬意。正是Galois,让我们的数学不是拓展了广度,而是翻了维度。虽然Galois生前被埋没,死了之后其数学理论却可泽及万世,大师也能安息了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

AI 路上,第一步这么走下去...

算法是描述解决一个问题的步骤,外界给它所指定的数据,然后经过一系列步骤输出一个结果。为了更快更轻量级地解决问题,我们会选择高效精简的结构去实现,这种结构称为数据...

13360
来自专栏后端技术探索

算法之经典背包问题分析与实例

我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,...

11510
来自专栏C语言及其他语言

[每日一题]老王赛马

题目描述 赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到...

28790
来自专栏ACM算法日常

5行位运算,map靠边站——位操作进阶

Given an array of integers, every element appears three times except for one. F...

13310
来自专栏机器之心

机器学习时代的哈希算法,将如何更高效地索引数据

27250
来自专栏marsggbo

什么是P问题、NP问题和NPC问题

    这或许是众多OIer最大的误区之一。     你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你...

14520
来自专栏PPV课数据科学社区

如何向小白介绍何谓机器学习和数据挖掘?买回芒果他就懂了

  买芒果   嘴馋的你想吃芒果了,于是你走到水果摊,挑了几个让老板过过秤,然后你再根据芒果的斤两付钱走人。   显然,买芒果你当然是挑着最甜、最熟的来买(因为...

36870
来自专栏hadoop学习笔记

Hanlp自然语言处理工具的使用演练

Hanlp是由一系列模型与算法组成的工具包,目标是普及自然语言处理在生产环境中的应用。Hanlp具备功能完善、性能高效、架构清洗、语料时新、可自定义的特点;提供...

20820
来自专栏WOLFRAM

偶述 Wolfram 中文分词算法

从 2000 年开始学习和使用 Mathematica,《Mathematica 演示项目笔记》作者,发表Wolfram Demonstrations Proj...

18320
来自专栏Java面试通关手册

六道面试中常见的智力题 来看看你会做几道?

下面的题目来自滴滴出行2017秋招题。这些题目是我自己觉得比较难或者比较容易出错的题目。

29540

扫码关注云+社区

领取腾讯云代金券