Sep 032013
 

\[(x^2+xy+y^2)(z^2+zw+w^2)=(xz-yw)^2+(xz-yw)[wx+y(z+w)]+[wx+y(z+w)]^2\]

因此, 形如 \(x^2+xy+y^2\) 的数相乘, 所得的积仍为同样的形式.

这恒等式是如何想出来的? 秘密在于行列式, 把 \(x^2+xy+y^2\) 看成行列式

\begin{vmatrix}
x& y\cr
-y & x+y
\end{vmatrix}

Let \(f(x_1,x_2,\dotsc,x_n)\) be a homogeneous polynomial. Let

\[S=\{f(a_1,a_2,\dotsc,a_n)\mid a_1,a_2,\dotsc,a_n \in\Bbb Z\}.\]

If \(S\) satisfies the following condition: for all \(m,n\in S\), we have \(mn\in S\). Can we determine all the homogeneous polynomials \(f\)?

For example, \(x^n(n\in\Bbb N),x^2+n y^2(n\in\Bbb Z), x^2+xy+y^2,x^3+y^3+z^3-3xyz\), and \(x^2+y^2+z^2+w^2\) are all appropriate examples.

 Posted by at 10:09 am
Aug 192013
 

Richard Taylor(就是协助 Andrew Wiles 完成了Fermat’s Last Theorem 的证明的那位) 写了一篇很有趣的文章 Modular Arithmetic: Driven by Inherent Beauty and Human Curiosity(The Institute Letter, 2012, Summer, 6-8). 这文章指出: Euclid 在他的几何原本 已经得到方程

\begin{equation}x^2+y^2=z^2\end{equation}

的全部整数解. Taylor 进一步指出, 只要

\begin{equation}x^2+y^2=2z^2\end{equation}

有一个非零整数解, 那么 Euclid 的办法依然有效, 可以用来找出  \(x^2+y^2=2z^2\) 的全部解, 并且 Taylor 也写出了全部的解. 然后, 对于  \(x^2+y^2=3z^2\), 很遗憾, 没有非平凡的解.

对方程

\begin{equation}x^2+y^2=nz^2,\end{equation}

Taylor 就说了这么多. 那么, 我们来尝试找出这方程的所有有理解, 以及所有整数解.

根据 Fermat 的平方和定理, 方程 (3) 有(有理解, 整数解)解, 当且仅当 \(n\) 能表成两个整数的平方和 \(n=a^2+b^2\). 因此, 我们考察下面的方程就行了:

\begin{equation}x^2+y^2=(a^2+b^2)z^2,\end{equation}

这里 \(a,b\in\Bbb Z\).

Jul 112013
 

不存在无穷质数等差数列. 下面是几种证明:

设等差数列的首项为 \(a\), 公差为 \(d\).

证明 1

分两种情况:

  • a=1. 此时 \(1+(d+2)d=(d+1)^2\) 是合数;
  • \(a\geqslant2\). 此时 \(a+ad=a(d+1)\) 是合数.

证明 2

连续合数可以任意长, 这是熟知的. 不曾想,  一个副产品居然就是我们的目标.

\((m+1)!+2,(m+1)!+3,\dotsc,(m+1)!+m+1\) 是 \(m\) 个连续合数.

证明 3

稍强一点的结果 采用完全剩余系

取一个与公差 \(d\) 互质的正整数 \(m\),

\[a, a+d, a+2d, \dotsc, a+(m-1)d\]

将跑遍 \(\bmod  m\) 的完全剩余系, 于是必有一项 \(\equiv0\pmod m\).

证明 4

这个结论也是熟知的: 不存在多项式

\[f(x)=\sum\limits_{i=0}^ma_ix^i,\]

使得对于任意 \(n∈\Bbb N, f(n)\) 都是质数.

证明 5

这个高级一点点: 采用自然密率 (natural density 或 asymptotic density), 而不是更常见的 Schnirelmann 密率 (Schnirelmann density).

由质数组成的集合的 asymptotic density 是 \(0\), 而等差数列形成的集合的 asymptotic density 为正.

证明 6

使用中国剩余定理证明”连续合数可以任意长”的加强版. 这个证明来自 matrix67 在2015年5月30日的日志, 但这里一些改进.

任取 \(n\) 个两两互质的正整数 \(m_1\), \(m_2\), \(\dotsc\), \(m_n\). 存在正整数 \(a\), 使得

\[m_i|\left(a+i\right),  i=1, 2, \dotsc, n.\]

[证明 6 更新于 北京时间 2015 年 6 月 24 日]

Jul 052013
 

单墫的数论书 “趣味数论” 是一本不错的数论入门书. 这是我看过的第一本完全的数论书籍.

阅读本书不需要多少准备知识, 初中毕业生基本没有什么困难. 当然, 一个爱思考的大脑, 对数学的热爱, 一支铅笔一张纸肯定是不能缺少的!

对数学竞赛来说, 需要的数论知识点, 这书都有, 除了不是必须的二次剩余. 这书有不少堆垒数论的问题. 除此之外, 第七章是丢番图逼近的简单介绍, 第九章, 第十章可以看作解析数论, 代数数论的最简单入门. 这些数论分支, 继续深入, 都有很多好的文献.

单墫的的书, 有一些共同的特征: 问题多, 定理少! 这在本书也得到完整的体现.

本书最早由中国青年出版社出版, 是绿色封皮. 最新的第二版, 是华东师大出版社推出. 新版, 相较前版, 仅仅只有最后一节, 修订交待了 Wiles 证明了Fermat 大定理.

下面是对本书的一些补充材料:

1.21 唯一因式分解定理的证明

本书给出的是最流行的办法.  Hardy 的名作 [2] 用最小数原理给出了另外一个证明.

2.5  五边形与五角数

一般, 第 \(k\) 个 \(m+2(m\geqslant1)\) 角数记为
\[p_m(k)=\dfrac{mk(k-1)}2+k.\]

2.8  一个不平凡的结论

这个结论是 Euler 的.  可在 [3] 的最后一章找到一个证明.

2.9 什么数恰好有 \(60\) 个因数?

最后给出的答案, 遗漏了一种情况: \(p^{59}\).

\(kn = x^2+y^2+1\)

\(n\) is a odd number, then there exists positive integer \(k\gt0\) such that \(kn = x^2+y^2+1\) for some integers \(x,y\).

with use of the Chinese remainder theorem we have to solve this problem only for power of primes:

suppose that \( n=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}\), then we know that for each \(i\), there exist \( x_i, y_i\) such that \( p_i^{a_i}\) divides  \( x_i^2+y_i^2+1\). Now consider these equations:

\[ X\equiv x_i\pmod {p_i^{a_i}}, i= 1,2,\dotsc,k.\]

these equations have solution because of  Chinese remainder theorem.

similarly these equation have solution:

\[  Y\equiv y_i\pmod {p_i^{a_i}}, i= 1,2,\dotsc,k.\]

now \(n\) divides  \( X^2+Y^2+1.\)

then we can apply hansel’s lemma. Actually we want to show that if for some \( \alpha \), there exist \(x,y\) such that \( p^\alpha\) divides  \( x^2+y^2+1\), then for  \( \alpha +1\) such \(x\)  and \(y\) exist. For this because in case \( \alpha \), \( p\) cannot divide both \(x\)  and \(y\), then we can use hansel for improve \( \alpha \) to \( \alpha+1.\)

References

  1. 华罗庚, 数论导引.
  2. Hardy, An introducton to the theory of numbers. 有中文本
  3. Tom M. Apostol, Introduction to analytic number therory. 有中文本
Oct 032012
 

Number theory will be understood, not as a collection of tricks and isolated results, but as a coherent and interconnected theory.

算术基本定理最早的准确表述与证明, 应该是出自 Gauss 的名著算术研究. 但是, 在这之前很久, 人们似乎就已经知道这个定理的具体内容, 并且已经广泛使用.

很明显, 这个结果是重要的! \(\sqrt2\) 是无理数的经典证法也依仗它! 当然, 定理也是漂亮的!

Green(与 Tao 合作 Green–Tao theorem 的那位)的(博士)导师 Gowers, 写了两篇关于此定理的文章: Why isn’t the fundamental theorem of arithmetic obvious?  和 Proving the fundamental theorem of arithmetic.

定理不是显然的. 流行的证明, 大家都知道, 是利用 Bézout 恒等式还有归纳法. 罕见的一个证明来自英国大数学家 Hardy 的数论导引, 如今名为哈代数论, 的第二章的最后: 利用最小数原理.

陈省身说, 好的数学就是可以引导出很多后来发展的数学! 所以, 题外话是: 竞赛数学不是好的数学!

对于算术基本定理来说, 很遗憾, 在一般的数域中, 在更广泛的范围, 并不成立. 20世纪最伟大的数学家 Hilbert 曾经举个一个例子: 唯一分解在

\[H=\{1,5,9,13,17,\dotsc\}\]

中不成立. 众所周知的一个事情是: 如果唯一分解总是成立的的话, 著名的 Fermat 大定理就太 easy 了.

算术基本定理诱导了如唯一分解整环, Euclid 整环等等概念. Gauss 为了描述唯一分解成立的程度, 引进了类数的概念. 大致上, 类数越大, 一个数被分解成质数的分法个数就越多. 虚二次域 \(Q( \sqrt D)\) 的 Gauss 猜想已经解决, 但实二次域的情形, 现在还是木有证明的事情.

关于理想 ideal, 倒是有一个相应的唯一分解定理: \(O_k\) 的任意非零真理想可以唯一写成质理想的积, 不考虑顺序的话.

 Posted by at 11:44 am
Aug 232012
 

间接或者直接使用中国剩余定理(the Chinese remainder theorem)可以证明二次互反律. 间接使用, 意思是互反律的证明使用了某个定理, 但是这个定理的关键却在 CRT; 直接使用容易理解. Sey Y.Kim 在 The American Mathematical Monthly, Vol.111, Jan., \(2004\),\(48\)-\(50\) 有一个比较简洁的初等证明, 使用了 Euler的判别条件(Euler’s criterion)和由中国剩余定理导出的同余方程的一个结论, 可算间接证明的代表; 而 G.Rousseau, Tim Kunisty, Klaus Hoechsmann 的证明, 都是直接使用了 CRT 的一个特例, 即群论中的一个同构 \(\Bbb Z_{pq}^*\cong\Bbb Z_p^*\times\Bbb Z_q^*\).

Sey Y.Kim 的证明也收录在 Biscuits of Number Theory 一书.

Aug 212012
 

If \(p,q\) are distinct odd primes,  then

\[\left( \frac pq\right) \left( \frac qp\right) = (-1)^{\frac{(p-1)(q-1)}4},\]

where \(\left( \frac{}{}\right)\) is the Legendre symbol. 这就是被 Gauss 称为”数论酵母” 的二次互反律.

自 Legendre 的那个没有完成的证明以来, 据 Reciprocity Laws: From Euler to Eisenstein 的作者 Franz Lemmermeyer 统计, 发表的证明是 \(240\) 个. 可以预见的到, 这个数字还会不断增加. 这些证明的作者, 发表年份,使用的方法以及文献的详细列表可在 Lemmermeyer 的个人主页找到. 其中, \(1889\) 这一年就有 \(6\) 个证明公布, \(1893,1951,1961\) 年也各有 \(5\) 个证明发表在不同的期刊上. 仅看从 \(1950\) 年到今天的这 \(60\) 多年, 只有 \(1956,1959,1968,1970,1975,1977,1982,1986,1988,1996,2002\) 这 \(11\) 年没有证明发表.不过, Lemmermeyer 的统计好像有小错误, 例如 Wouter Castryck 在 \(2008\) 年发表了一篇文章, 办法类似于 V. A. Lebesgue 在 \(1838\) 年的论证, 但 Lemmermeyer 的统计认为 Castryck 的证明在 \(2007\) 年给出.

这么多的证明, 想要全部分门别类, 整理好写出来, 肯定是困难的. 文献多, 不容易都找到. 即便都找齐了, 也因为是不同的语言, 也不能都看懂. 这些方法各有繁简. 哪个证明才是最简单的呢? 显然, Proofs from THE BOOK 给出的两个途径, 是比较繁琐的; Jean-Pierre Serre 在他的 A Couse in Arithmetic 第一章给出的都依靠 Gauss 引理的两个证明, 也不算太简单. 那么, 到底哪个才是最简单的呢? 各人的看法可能有不同. 但, 美妙的, 能给人以深刻印象, 令人荡气回肠的证明, 应该有一些共同的特征, 或者说一个证明要能成为好的证明, 美丽的证明, 应该有一定的门槛, 满足一定的条件. 我们试着列出这些条件:

  • 简单是首要条件. 基于简单的想法, 能揭示问题的本质, 加深对事物的理解.
  • 美. 构思巧妙, 论证精妙方能展现出深刻. 当然, 简单其实也是一种美.
  • 自然. 方法能用在更广泛的地方, 解决更多的问题.

同时满足这些要求的证明不容易找到, Castryck 的证明大概可以满足前两条. 下面是他的详细论证:

For any odd \(n \in\Bbb N\), denote by \(N_n\) the number of solutions in \(\left( \Bbb Z / (q)\right)^n\) to the equation

\[x_1^2-x_2^2+x_3^2-\dotsb + x_n^2 = 1.\]

If we substitute \(x_1 \gets x_1+x_2\), then we get

\[x_1^2+x_3^2-\dotsb + x_n^2-1 = -2x_1x_2.\]

For any non-zero \(x_1\)-value and any values of \(x_3,\dotsc,x_n\), there is a unique corresponding \(x_2\)-value. If \(x_1=0\), there are no solutions, except if \(x_3^2-\dotsb + x_n^2 = 1\) (which happens in \(N_{n-2}\) cases): then all possible values of \(x_2\) do the job. We find that

\[N_n = q^{n-2}(q-1)+qN_{n-2}.\]

and hence \(N_n = q^{n-1}+q^{\frac{n-1}{2}}(N_1-1) = q^{n-1}+q^{\frac{n-1}{2}}.\) In particular,

\begin{equation}N_p\equiv1+\left(\frac qp\right) \pmod p.\end{equation}

Next, \(N_p\) can be classically determined as

\[\sum_{t_1+\dotsb + t_p = 1}N(x_1^2 = t_1)N(x_2^2 = -t_2)N(x_3^2=t_3)\dotsm N (x_p^2=t_p),\]

where the \(t_i\) are in \(\Bbb Z/(q)\) and \(N(\cdots)\) denotes the number of solutions to the corresponding univariate equation. This can be rewritten as

\[\sum_{t_1+\dotsb+t_p=1}\left(1+\left(\frac{t_1}q\right)\right)\left( 1+\left( \frac{-t_2}q\right)\right)\left( 1+\left( \frac{t_3}q\right)\right)\dotsm \left( 1+\left( \frac{t_p}q\right)\right),\]

When expanding out the product, only the terms \(1\cdot 1 \cdot 1 \cdots 1\) and \(\left(\frac{t_1}q\right)\cdot\left(\frac{-t_2}q\right)\cdot\left( \frac{t_3}q\right)\cdots\left( \frac{t_p}q\right)\) should be taken into consideration; the other terms disappear because Legendre symbols sum up to zero: \(\sum\limits_{t\in\Bbb Z/(q)}\left(\frac tq\right) = 0.\) Therefore, the above expression simplifies to

\[q^{p-1}+\left( \frac{(-1)^{\frac{p-1}2}}q\right)\sum_{t_1+\dotsb+t_p = 1}\left(\frac{t_1t_2t_3\dotsm t_p}q\right).\]

Modulo \(p\), the latter sum almost completely vanishes, since the tuples \((t_1,\dotsc,t_p)\) satisfying \(t_1+\dotsb + t_p = 1\) with not all \(t_i\) equal to \(p^{-1}\) can be collected in groups of size \(p\) by cyclic permutation. Note that \(p\) is indeed a multiplicative unit in \(\Bbb Z/(q)\). We thus obtain

\begin{equation}N_p\equiv1+\left( \frac{(-1)^{\frac{p-1}2}}q\right) \left( \frac{p^{-p}}q\right) \equiv1+(-1)^{\frac{p-1}2\frac{q-1}2}\left( \frac pq\right) \pmod p.\end{equation}

The last congruence follows from Euler’s criterion \(\left(\frac aq\right) \equiv a^{\frac{q-1}2} \pmod q\) and the observation that \(p^{-p}\) is a square in \(\Bbb Z/(q)\) if and only if \(p\) is a square in \(\Bbb Z/(q)\).

Comparing \((1)\) and \((2)\), the reciprocitylaw follows. \(\Box\)

接下来的论证, 是 Aurelien Bessard (2010) 改编自 V. A. Lebesgue 和 Eisenstein的一个证明:

Let \(p = 2m+1\) and \(q\) be distinct odd primes and let \(N\) denote the number of solutions of the equation

\[ x_1^2 + \ldots + x_p^2 = 1 \]

in the finite field \(\Bbb F_q\).

The group \(\Bbb Z/p\Bbb Z\) acts on the solution space \(X\) by shifting indices: if \((x_1, \ldots, x_p) \in X\), then so is \((x_a,x_{a+1}, \dotsc)\) for each \(a \in {\mathbb Z}/p{\mathbb Z}\), where the indices have to be read modulo \(p\). Each orbit has exactly \(p\) elements except if there is an \(x\) with \((x,x,\ldots,x) \in X\): the orbit of this element has \(1\) element. Now \((x,x,\ldots,x) \in X\) if and only if \(px^2 = 1\) is solvable in \(\Bbb F_q\), hence

\begin{equation} N \equiv \Big( \frac pq \Big) + 1 \pmod p.\end{equation}

We make a change of variables to transform the diagonal equation into an equation where counting the number of solutions is easier. To this end, consider the matrix

\[ A = \left( \begin{matrix} 0 & 1 & & & & & & \\ 1 & 0 & & & & & & \\ & & 0 & 1 & & & & \\ & & 1 & 0 & & & & \\ & & & & \ddots & & & \\ & & & & & 0 & 1 & \\& & & & & 1 & 0 & \\& & & & & & & a\end{matrix} \right) \]

with \(a = (-1)^{\frac{p-1}2}\). Since \(\det A = 1\), this matrix is congruent to the unit matrix, hence \(X\) and the solution spaces \(X^\prime\) of the equation \(x^T A x = 1\),i.e.,recall that \(p=2m+1\), of

\[2(y_1z_1+\dotsb+y_mz_m)+ax_p^2=1\]

are isomorphic.

For counting the number of solutions of \(X^\prime\), observe that if \((y_1, \dotsc, y_m) = 0\), we have \(q^m(1+a^{\frac{q-1}2})\) possibilities for choosing \(z_1, \dotsc, z_m\) and \(x_p\).

If \(y = (y_1, \dotsc, y_m) \ne 0\), on the other hand, then for each choice of \(y\) and \(x_p\) we have to count the number of points on a hyperplane of dimension \(m\); there are \(q^{m-1}\) points on such a hyperplane, and the number of overall possibilities in this case is \((q^m-1) \cdot q \cdot q^{m-1} = q^m(q^m-1)\).

Thus we find

\begin{equation}\begin{split} N & = q^m (1+a^{\frac{q-1}2})+q^m(q^m-1) \\&=q^m(q^m+(-1)^{\frac{p-1}2\frac{q-1}2})\\ & \equiv\Big(\frac qp\Big)\bigg(\Big(\frac qp\Big)+(-1)^{\frac{p-1}2\frac{q-1}2}\bigg)\\&\equiv1+(-1)^{\frac{p-1}2\frac{q-1}2}\Big(\frac qp\Big)\pmod p.\end{split}\end{equation}

Comparing \((3)\) and \((4)\), gives the quadratic reciprocity law. \(\Box\)

Aug 202012
 

卢昌海谈 Riemann 猜想(Riemann hypothesis)的系列文章, 刚刚由清华大学出版社结集出版, 书名”黎曼猜想漫谈”.

the Riemann hypothesis

book on the Riemann hypothesis

从卢昌海动笔写第一篇谈Riemann 猜想的小文章, 到现在出版成书, 过去了八年仅仅差三个月. 在正式出版之前, 其内容已经在网络广为流传, 被很多人转载, 也被数学杂志连载刊登过, 影响巨大. 现在作为数学科普出版, 相信会促进科学的传播, 有助于大家了解这个数学中最重要的难题.

书名: 黎曼猜想漫谈
ISBN: 978-7-302-29324-8
出版社: 清华大学出版社
作者: 卢昌海
出版日期: 2012年08月
定价: 25 人民币元