科学空间|Scientific Spaces

集合上的一个等价关系决定了几何的一个划分，反之亦然，这直观上是不难理解的。但是，如果我要问一个有$n$个元素的有限集合，共有多少种不同的划分呢？以前感觉这也是一个很简单的问题，就没去细想，但前天抽象代数老师提到这是一个有相当难度的题目，于是研究了一下，发现里面大有文章。这里把我的研究过程简单分享一下，读者可以从中看到如何“从零到有”的过程。

以下假设有$n$个元素的有限集合为$\{1,2,\dots,n\}$，记它的划分数为$B(n)$。

前期：暴力计算

$n=3$的情况不难列出：
$$\begin{aligned}&\{\{1,2,3\}\},\{\{1,2\},\{3\}\},\{\{1,3\},\{2\}\},\\
&\{\{2,3\},\{1\}\},\{\{1\},\{2\},\{3\}\}\end{aligned}$$

点击阅读全文...

原则上来讲，同样的算法，如果分别在Python和C++上实现，那么Python的速度肯定比不上C++的。但是Python还被称为“胶水语言”，它允许我们把主要计算的部分用C或C++等高效的语言编写好，然后它作为“粘合剂”把两者粘合在一起。正因为如此，Python才有了各种各样的扩展库，这些库中有不少是用C语言编写的。因此，我们在编写Python程序的时候，如果可以用这些现成的库，速度会快很多。本文就是用Numpy来改进之前的《两百万前素数之和与前两百万素数之和》的计算。

算法本身是没有变的，只是用了Numpy来处理数组计算，代码如下：

点击阅读全文...

圆上的有理点

我们在这个系列的文章之中，探索了一些有关环和域的基本知识，并用整环以及唯一分解性定理证明了费马大定理在n=3和n=4时的情形。使用高斯整数环或者艾森斯坦整数环的相关知识，相对而言是属于近代的比较“高端”的代数内容（高斯生于1777年，艾森斯坦生于1823年，然而艾森斯坦英年早逝，只活到了1852年，高斯还活到了1855年。）。如果“顺利”的话，我们可以用这些“高端”的工具证明解的不存在性，或者求出通解（如果有解的话）。

然而，对于初等数论来讲，复数环和域的知识的门槛还是有点高了。其次，环和域是一个比较“强”的工具。这里的“强”有点“强势”的意味，是指这样的意思：如果它成功的话，它能够“一举破城”，把通解都求出来（或者证明解的不存在）；如果它不成功的话，那么往往就连一点非平凡的解都求不出来。可是，有些问题是求出一部分解都已经很困难了，更不用说求出通解了（我们以后在研究$x^4+y^4 = z^4 + w^4 $的整数解的时候，就能深刻体会这点。）。因此，对于这些问题，单纯用环域的思想，很难给予我们（至少一部分）解。（当然，问题是如何才算是“单纯”，这也很难界定。这里的评论是比较粗糙的。）

点击阅读全文...

两年前，笔者曾写过《算子与线性常微分方程》两篇，简单介绍了把线形常微分方程算符化，然后通过对算符求逆的方法求得常微分方程的通解。而在这篇文章中，笔者打算介绍关于算符类似的内容：差分算符、微分算符以及与之相关的伯努利数（Bernoulli数）。

我们记$D=\frac{d}{dx}$，那么$Df=\frac{df}{dx}$，同时定义$\Delta_t f(x)=f(x+t)-f(x)$，并且记$\Delta \equiv \Delta_1 =f(x+1)-f(x)$，这里我们研究的$f(x)$，都是具有良好性态的。我们知道，$f(x+t)$在$t=0$附近的泰勒展式为
$$\begin{aligned}f(x+t)&=f(x) + \frac{df(x)}{dx}t + \frac{1}{2!}\frac{d^2 f(x)}{dx^2}t^2 + \frac{1}{3!}\frac{d^3 f(x)}{dx^3}t^3 + \dots\\
&=\left(1+t\frac{d}{dx}+\frac{1}{2!}t^2\frac{d^2}{dx^2}+\dots\right)f(x)\\
&=\left(1+tD+\frac{1}{2!}t^2 D^2+\dots\right)f(x)\end{aligned}$$

点击阅读全文...

之前笔者曾写过《初试在Python中使用PARI/GP》，简单介绍了一下在Python中调用PARI/GP的方法。PARI/GP是一个比较强大的数论库，“针对数论中的快速计算（大数分解，代数数论，椭圆曲线...）而设计”，它既可以被C/C++或Python之类的编程语言调用，而且它本身又是一种自成一体的脚本语言。而如果仅仅需要高精度的大数运算功能，那么GMP似乎更满足我们的需求。

了解C/C++的读者都会知道GMP（全称是GNU Multiple Precision Arithmetic Library，即GNU高精度算术运算库），它是一个开源的高精度运算库，其中不但有普通的整数、实数、浮点数的高精度运算，还有随机数生成，尤其是提供了非常完备的数论中的运算接口，比如Miller-Rabin素数测试算法、大素数生成、欧几里德算法、求域中元素的逆、Jacobi符号、legendre符号等^[来源]。虽然在C/C++中调用GMP并不算复杂，但是如果能在以高开发效率著称的Python中使用GMP，那么无疑是一件快事。这正是本文要说的gmpy2。

点击阅读全文...

今天上近世代数课，老师谈到除环，举了一个非交换的除环的粒子，也就是四元数环，然后谈到“实数域上有限维可除代数只有4种”，也就是实数本身、复数、四元数和八元数（这里的可除代数就是除环）。这句话我听起来有点熟悉，又好像不大对劲。我记得在某本书上看过，定义为实数上的超复数系，如果满足模的积性，那么就只有以上四种。但是老师的那句话表明即使去掉模的积性，也只有四种。我自然以为老师记错了，跟老师辩论了一翻，然后回到宿舍又找资料，最终确定：实数域上有限维可除代数真的只有四种！下面简单谈谈我对这个问题的认识。

当然，这里不可能给出这个命题的证明，因为这个证明相当不简单，笔者目前也没有弄懂，但是粗略感觉一下为什么，还是有可能的。看到这个命题，我们一下子的感觉可能是：怎么会这么少！我们这里通过例子简单说明一下，确实不会多！

我们已经对复数系很熟悉了，也就是定义在实数上的向量空间，基为$\{1,i\}$，并且给定乘法为
$$1\times i=i \times 1=i,\quad 1^2=1,\quad i^2=-1$$

点击阅读全文...

特殊的通项公式

对数学或编程感兴趣的读者，相信都已经很熟悉斐波那契数列了

0, 1, 1, 2, 3, 5, 8, 13, ...

它是由
$$a_{n+2}=a_{n+1}+a_n,\quad a_0=0,a_1=1$$
递推所得。读者或许已经见过它的通项公式
$$a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]$$
这里假设我们没有如此高的智商可以求出这个复杂的表达式出来，但是我们通过研究数列发现，这个数列越来越大时，相邻两项趋于一个常数，这个常数也就是（假设我们只发现了后面的数值，并没有前面的根式）
$$\beta=\frac{1 + \sqrt{5}}{2}=1.61803398\dots$$

点击阅读全文...

伽马函数
$$\Gamma(x)=\int_0^{+\infty}t^{x-1}e^{-t}dt$$
作为阶乘的推广，会让很多初学者感到困惑，对于笔者来说也不例外。一个最自然的问题就是：这般复杂的推广公式是如何得到的？

在cos.name的文章《神奇的伽马函数》中，有比较详细地对伽马函数的历史介绍，笔者细读之后也获益匪浅。但美中不足的是，笔者还是没能从中找到引出伽马函数的一种“自然”的办法。所谓“自然”，并不是说最简单的，而是根据一些基本的性质和定义，直接把伽马函数的表达式反解出来。它的过程和运算也许并不简单，但是思想应当是直接而简洁的。当然，我们不能苛求历史上伽马函数以这种方式诞生，但是作为事后探索是有益的，有助于我们了解伽马函数的特性。于是笔者尝试了以下途径，得到了一些结果，可是也得到了一些困惑。

点击阅读全文...