數學中的幾個概率啟發式「證明」

01-27

在數學研究過程中，當人們對一個猜想（多數是數論里的）正面強攻無效時常常從概率的角度對該猜想正確與否進行定性分析或者推測其核心公式的形式及反例的分布，這樣的想法被UCLA的數學家陶哲軒（Terrence Tao）稱為對該猜想的「概率啟發式理由」（Probabilistic heuristic justification）。這種定性分析往往不構成對猜想的證明，但是可以提高該猜想的可信度或為正式的證明指明方向，下面是幾個這樣的例子：

（以下不區分 $approx$ 、 $sim$ 以及 $=$ ，都是在近似的意義下作的）

1.素數定理：記 $pi (x)$ 為不大於 $x$ 的素數個數，則 $pi (n)sim int_{2}^{n} frac{mathrm{d}x}{mathrm{log}x}$

分析：首先假設描述素數分布的規律是存在的，即有這樣一個描述素數密度的函數 $P(n)$ 使得對充分大的正整數 $n$ ， $pi (n)sim int_{2}^{n}P(x)mathrm{d}x$ .

下面給出兩個引理（證明留作習題）：

引理1.1：對充分大的 $n$ ， $mathrm{log}n!sim nmathrm{log}n$

引理1.2：（Lagrange）記 $[n]_{p} =k$ ，當且僅當 $p^{k} ||n$ ，即 $k$ 是 $n$ 中 $p$ 的冪次，則 $left[ n! right]_{p} = sum_{k=1}^{infty }{[frac{n}{p^{k} }] }$ .

由引理2得： $[n!]_{p}approx sum_{k=1}^{infty }{frac{n}{p^{k} } }=frac{n}{p-1}$ （這當然是個近似的式子）

$n$ 很大時，對所有小於 $n$ 的素數 $p$ 對上式求和有： $mathrm{log}n!sim sum_{p<n}^{}{frac{n}{p-1}mathrm{log}p}$ .

再由引理1： $nmathrm{log}nsim sum_{p<n}^{}{frac{n}{p-1}mathrm{log}p}$ ，即 $mathrm{log}nsim sum_{p<n}^{}{frac{mathrm{log}p}{p-1} }$ $(1)$

在前面我們假設素數的密度分布符合 $P(x)$ ，選取點 $2=xi _{1},xi _{2} ,cdot cdot cdot , xi _{r},xi _{r+1}=n$ ，則第 $j$ 個區間 $[xi _{j},xi _{j+1} ]$ 中的素數個數大約為 $P(xi_{j})(xi_{j+1}-xi_{j})= P(xi_{j})Delta xi _{j}$ ，因此 $(1)$ 式右端近似等於 $sum_{j=1}^{r+1}{frac{mathrm{log}xi _{j} }{xi _{j}-1 }P( xi _{j})Deltaxi _{j} }$ ，我們用它所逼近的積分來代替這個和並用 $x$ 代替 $n$ ：

$mathrm{log}xsim int_{2}^{x}frac{mathrm{log}xi }{xi -1}P(xi )mathrm{d}xi$ . 兩邊微分得： $frac{1}{x}approx frac{mathrm{log}x}{x-1}P(x)$ .

於是我們得到： $P(x)approx frac{x-1}{xmathrm{log}x} approx frac{1}{mathrm{log}x}$ ，故 $pi (n)sim int_{2}^{n}frac{mathrm{d}x}{mathrm{log}x}$ .

（嚴格來講並沒有用到太多概率的想法……）

我們還有另外一個概率味道比較濃的推理，回顧一下歷史：Gauss通過「大數據」歸納出到 $x$ 的素數密度大致為 $frac{1}{mathrm{log}x}$ ，由此Gauss推測應當 $pi(x)sim lim_{varepsilon rightarrow 0}({ int_{0}^{1-varepsilon } +int_{1+varepsilon }^{x})frac{mathrm{d}t}{mathrm{log}t} }$ .上個世紀30年代，概率論大師H.Cramer給出了Gauss猜想的概率解釋，這個概率模型現在被稱作Gauss-Cramer隨機素數模型：

定義如下數列 $left{ X_n right}_{ngeq 3 }$ ： $X_n=1$ ，當且僅當 $n$ 是素數；否則 $X_n=0$ .

$left{ X_n right}$ 寫下來就是（從 $3$ 開始）： $1,0,1,0,1,0,0,0,1,0,cdot cdot cdot$

Cramer假設這個序列有典型的 $01$ 序列的性質，根據高斯的觀察，Cramer假設：對充分大的 $n$ ， $X_n$ 有 $frac{1}{mathrm{log}n}$ 的概率取 $1$ ，有 $1-frac{1}{mathrm{log}n}$ 的概率取 $0$ ；並定義一個關於此序列分布的命題為真，當且僅當它以概率 $1$ 為真.

記事件 $A$ ： $left{ X_n right} _{ngeq 3}$ 的前 $x$ 項有 $int_{2}^{x}frac{mathrm{d}t}{mathrm{log}t}$ 個 $1$ ，利用中心極限定理，Cramer得到 $lim_{n rightarrow infty }{P(A)}=1$ .因此，我們有充分的理由猜測 $pi (x)sim int_{2}^{x}frac{mathrm{d}t}{mathrm{log}t}$ .

2.費馬大定理：方程 $x^{n}+y^{n}=z^{n}$ 對 $ngeq 3$ 無正整數解.

分析：這個是徹頭徹尾的概率計算，來自物理學家R.Feynman.

設 $N$ 是充分大的整數，則 $sqrt[n]{N}$ 與 $sqrt[n]{N+1}$ 的間距 $d=sqrt[n]{N+1}-sqrt[n]{N} =sqrt[n]{N}(sqrt[n]{1+frac{1}{N} }-1)$ .

因為 $frac{1}{N}$ 足夠小，故 $dsim sqrt[n]{N}(1+frac{1}{nN}-1)=frac{sqrt[n]{N} }{nN}$

則在區間 $[sqrt[n]{N},sqrt[n]{N+1}]$ 中至少有一個整數的概率為 $frac{d}{1}sim frac{sqrt[n]{N} }{nN }$ .

對費馬大定理 $x^{n}+y^{n}=z^{n}$ 而言，令 $N=x^{n}+y^{n}$ ，則 $N$ 為完全 $n$ 次方的概率為 $frac{sqrt[n]{x^{n}+y^{n}} }{n(x^{n}+y^{n})}$

當然，這個概率是對於給定的 $x,y$ 而言的，若要對任意的 $x,y>2$ 計算概率則應對其求和，跟前面一樣我們用積分來代替求和得到概率： $p_{n} =int_{2}^{infty } int_{2}^{infty }frac{1}{n}(x^{n}+y^{n})^{frac{1}{n}-1}mathrm{d}xmathrm{d}y$ .

令 $a_{n}=int_{0}^{infty } int_{0}^{infty }(x^{n}+y^{n})^{frac{1}{n}-1 } mathrm{d}xmathrm{d}y$ ，則 $p=frac{1}{n2^{n-3}}a_{n}$ .

再令 $u=frac{x}{2}$ ， $v=frac{y}{2}$ ，則 $a_{n} =int_{1}^{infty } int_{1}^{infty }frac{1}{n2^{n-1}} (u^{n}+v^{n})^{frac{1}{n}-1 }left| frac{partial (x,y)}{partial(u,v)} right| mathrm{d}umathrm{d}v$

這裡 $left| frac{partial(x,y)}{partial(u,v)} right| =frac{partial x}{partial u} frac{partial y}{partial v} -frac{partial x}{partial v} frac{partial y}{partial u} =4$ 是Jacobi行列式.

故 $a_{n} =int_{1}^{infty } int_{1}^{infty }frac{1}{n2^{n-3}} (u^{n}+v^{n})^{frac{1}{n}-1 } mathrm{d}umathrm{d}v$

注意到對充分大的 $n$ ， $a_{n} sim frac{2mathrm{log}2}{n^{2} }$ （留作習題……嘻嘻）

所以對給定的 $n$ ， $p_{n}sim frac{2mathrm{log}2}{n^{3}2^{n-3} }$ . 從這裡看出： $n$ 越大，Fermat方程有解的概率越小.這是符合直覺的.

故對所有的 $n>n_{0}$ ，Fermat方程有解的概率： $p=int_{n_0}^{infty } frac{2mathrm{log}2}{n^32^{n-3}}mathrm{d}n$ .

在Feynman時代，人們已經知道當 $nleq 100$ 時，Fermat方程無解.所以令 $n_0=100$ ，Feynman給出的概率 $p= int_{100}^{infty }frac{2mathrm{log}2}{n^{3}2^{n-3} } mathrm{d}n=1.2104923times 10^{-35}$ .可以看到這個概率是極其小的，於是Feynman斷言：「依我看，費馬大定理是成立的。」當然，這是很不正式，但說服物理學家足夠了。（捂臉）

另外，不同於Feynman的推理，Erdos和Ulam於1971年給出了一個更具說服力的概率啟發式推理。他們實際上是對一個更強的命題的推測：對 $u,v,wgeq 4$ ，方程 $x^{u}+y^{v}=z^{w}$ 至多有有限對互素解 $(x,y,z)$ . 容易看到這其實是費馬大定理某種形式上的推廣（這個命題跟著名的Fermat-Catalan猜想不無淵源），Erdos和Ulam給出的推導也是極具啟發性的.

對 $ngeq 4$ ，定義集合 $S_n$ 為所有 $n$ 次冪的集合，令 $mathbb{S}=S_4cup S_5 cup cdot cdot cdot$ .我們要計算的概率是如果 $a,bin mathbb{S}$ ，那麼 $a+b$ 也在 $mathbb{S}$ 中的可能性.我們用一個隨機過程來生成 $mathbb{S}$ ：假設每個正整數 $n$ 都是獨立的，因為 $[1,n]$ 中大約有 $n^{frac{1}{4}}$ 數量級個 $4$ 次冪或更高次冪數，所以隨機抽取數 $n$ ，它在 $mathbb{S}$ 中的概率與 $n^{-frac{3}{4}}$ 成正比.

因此數 $n=a+b$ ，其中 $a,bin mathbb{S}$ 的概率應該正比於 $sum_{1leq a<frac{n}{2} }^{}{a^{-frac{3}{4}} } {(n-a)^{-frac{3}{4}} }$ .然後我們對其進行小小的放縮： $sum_{1leq a<frac{n}{2} }^{}{a^{-frac{3}{4}} } {(n-a)^{-frac{3}{4}} }<n^{-frac{3}{4}} sum_{1leq a<frac{n}{2} }^{}{a^{-frac{3}{4}} }$

對於充分大的 $n$ ，容易證明上式左邊是正比於 $frac{1}{sqrt{n} }$ .現在考慮到 $n$ 本身也在 $mathbb{S}$ 中，所以總的概率應該正比於 $frac{1}{sqrt{n} }times n^{-frac{3}{4}}=n^{-frac{5}{4}}$ .於是這種情況最多能發生的次數是正比於 $sum_{n}{n^{-frac{5}{4} }}$ 的，顯然這是個收斂的級數，因此我們對 $x^{u}+y^{v}=z^{w}$ 能發生的次數的期望也是有限的，故推測 $x^{u}+y^{v}=z^{w}$ 只有有限組互素解是合理的.

3.強孿生素數猜想：記 $pi _{2}(x)$ 為不小於 $x$ 的孿生素數個數，則 $pi _{2}(x) sim 2C_{2}int_{2}^{x} frac{mathrm{d}t}{mathrm{log}^{2}t }$ .這裡 $C_{2}=prod_{pgeq 3}frac{p(p-2)}{(p-1)^2}=0.660161181584cdot cdot cdot$ .

分析：隨機抽取數對 $(m,n)$ ，則 $m,n$ 不被素數 $p$ 整除的概率顯然為 $frac{(p-1)^2}{p^2}$ ，而對隨機選取的正整數 $n$ ， $n$ 與 $n+2$ 同時不被素數 $p>2$ 整除的概率為 $frac{p-2}{p}$ （對 $p=2$ ，概率為 $frac{1}{2}$ ）

因此 $n,n+2$ 模 $p>2$ 不為 $0$ 的概率與隨機數對 $(m,n)$ 的相差了因子 $frac{p-2}{p} frac{p^2}{(p-1)^2} =frac{p(p-2)}{(p-1)^2}$ .將所有這樣的因子乘起來，我們就得到了 $n$ 與 $n+2$ 同時是素數的概率的調整因子

$C_{2}=prod_{pgeq 3}frac{p(p-2)}{(p-1)^2}=0.660161181584cdot cdot cdot$ .

由素數定理我們知道，對充分大的 $x$ ， $x$ 附近的素數密度大約為 $frac{1}{mathrm{log}x}$ .因此兩個素數分布在寬為 $2$ 的區間里的概率大致為 $frac{2}{mathrm{log}^2x}$ ，這幾乎就是強孿生素數猜想的被積函數.於是大致我們得到：存在常數 $C$ ，使 $pi _{2}(x) sim 2Cint_{2}^{x} frac{mathrm{d}t}{mathrm{log}^{2}t }$ .容易發現 $C$ （如果有的話）就是前面的調整因子 $C_2$ ，故應該有 $pi _{2}(x) sim 2C_{2}int_{2}^{x} frac{mathrm{d}t}{mathrm{log}^{2}t }$ .這便是強孿生素數猜想了.

下面是重頭戲，在此之前先把一個重要的概念說了以防後面拖泥帶水的：

對整數 $n=p_{1}^{alpha _1} p_{2}^{alpha _2} cdot cdot cdot p_{k}^{alpha _k}$ ，其中 $p_{i}$ 都是素數.定義其根基（radical)為 $mathrm{rad}(n)=p_{1}p_{2} cdot cdot cdot p_k$ ，即 $n$ 的非平方部分.

好啦，解釋完了……

4.ABC猜想： 對互素的兩正整數 $a,b$ 及 $c=a+b$ ，對任意的 $epsilon >0$ 存在 $C_{epsilon }$ 使 $c<C_{varepsilon }mathrm{rad}^{1+varepsilon }(abc)$ .

分析：這可以說是當世最重要的猜想之一，其重要性除了Riemann猜想堪與比肩外，任何其他猜想恐怕都得退居其後。

By the way，ABC猜想還有一個等價的說法就是，滿足 $cgeqmathrm{rad}^{1+varepsilon }(abc)$ 的解只有有限多組.（這從根本上說明ABC猜想即使不對也壓根不能用數值檢驗的方法來否證）這裡我們用的是另一個等價的說法：對於滿足 $alpha +beta +gamma <1$ 的正實數 $alpha ,beta ,gamma$ 和充分大的整數 $N$ ，不存在使得 $a+b=c$ $(Nleq cleq 2N)$ 且 $mathrm{rad}(a)leq N^alpha$ ， $mathrm{rad}(b)leq N^beta$ ， $mathrm{rad}(c)leq N^gamma$ 的互素整數組 $(a,b,c)$ .

我們採取以下步驟來尋找ABC猜想的反例.（來自陶哲軒大神）

Step1 找一個很大很大的整數 $N$ （比如某個 $2$ 的冪）；

Step2 找三個互素的且均無平方因子的整數 $xleq N^alpha$ ， $yleq N^beta$ ， $zleq N^gamma$ ；

Step3 找 $a,b,c=O(N)$ 且 $mathrm{rad}(a)=x$ , $mathrm{rad}(b)=y$ , $mathrm{rad}(c)=z$ ， $c$ 要跟 $N$ 差不多大；

Step4 驗證一下是否 $a+b=c$ .

Step1，2，4比較容易做到，Step3基於以下引理：

引理4.1：設 $xleq N$ 是一無平方因子數，則至多有 $O(N^{o(1)})$ 個小於 $N$ 的整數 $n$ 使得 $mathrm{rad}(n)=x$ .

簡單給一個證明：若 $x=p_1p_2cdot cdot cdot p_k$ ，定義 $A$ 為小於 $N$ 且根基是 $x$ 的整數的個數.我們期望 $A=O(N^{o(1)})$ ，令 $S=left{ p_{1}^{alpha _1} p_{2}^{alpha _2} cdot cdot cdot p_{k}^{alpha _k} |alpha _1,alpha _2,cdot cdot cdot ,alpha _kgeq 1 right}$ .對於 $varepsilon >0$ ，考慮級數 $sum_{nin S}^{}{} frac{1}{n^varepsilon }$ .

一方面，這個級數的和至少是 $N^{-varepsilon }A$ ；另一方面， $sum_{nin S}^{}{} frac{1}{n^varepsilon } =prod_{j=1}^{k}(frac{1}{p_{j}^{varepsilon } }+ frac{1}{p_{j}^{2varepsilon } }+cdot cdot cdot )$ .取滿足對 $1leq jleq k$ 均有 $frac{1}{p_{j}^{varepsilon } }+ frac{1}{p_{j}^{2varepsilon } }+cdot cdot cdotleq C_varepsilon$ 的一實數 $C_varepsilon$ ，則 $sum_{nin S}^{}{} frac{1}{n^varepsilon } =prod_{j=1}^{k}(frac{1}{p_{j}^{varepsilon } }+ frac{1}{p_{j}^{2varepsilon } }+cdot cdot cdot ) leq C_{varepsilon }^{k}$ .

於是 $Aleq N^varepsilon C_{varepsilon }^{k}$ ，而我們有 $sum_{j=1}^{k}{mathrm{log}p_j}=mathrm{log}xleq mathrm{log}N$ .根據素數定理我們可以得到 $k=o(mathrm{log}N)$ ，於是 $Aleq N^{varepsilon+o(1)}$ ，此即所證.

現在，考慮Step1選出的大整數 $N$ 和Step2選出的滿足 $O(N^{alpha +beta +gamma })$ 的 $x,y,z$ .對於每一個 $x,y,z$ ，能選擇的 $O(N)$ 量級的 $a,b,c$ 至多有 $O(N^{o(1)})$ 組.假設 $c,a+b$ 是相互獨立的，它們隨機分布在一組大小是 $O(N)$ 的數里，則 $c=a+b$ 的概率的階差不多是 $frac{1}{N}$ .所以對所有充分大的 $N$ 求和得到所有概率的和為 $sum_{N}{O(N^{alpha +beta +gamma -1+o(1)})}$ .

因為 $alpha +beta +gamma <1$ ，故上面這個和是收斂的，從而最多期望有有限個反例，這是支持ABC猜想的.