數學(xué)中的一些最困難的極值問(wèn)題，精確求解不可能，只能不斷逼近

數學(xué)中有許多問(wèn)題，要求在各種約束之下，使某個(gè)量最大化或最小化，這些問(wèn)題稱(chēng)為極值問(wèn)題。和計數問(wèn)題一樣（數學(xué)不好，你連“簡(jiǎn)單”的計數都不會(huì )，計數問(wèn)題憑什么這么難？），有一些極值問(wèn)題可以實(shí)際地算出精確解來(lái)，而更多的則是，雖然精確解是談不上的，但仍然可以找到有趣的估計。這兩類(lèi)問(wèn)題，下面各有一些例子。

（1）令n為一正整數，而X為一含有n個(gè)元素的集合。問(wèn)可以找出X的多少個(gè)子集合，使得沒(méi)有一個(gè)會(huì )含于另一個(gè)子集合之內。

可以做出的一個(gè)簡(jiǎn)單觀(guān)察是∶如果兩個(gè)不同子集合大小相同，則沒(méi)有一個(gè)會(huì )包含于另一個(gè)之內。所以滿(mǎn)足問(wèn)題的約束的方法之一是選取所有的子集合具有同樣大小 k。X的大小為k的子集合一共有n!/k!（n-k）!個(gè)，這個(gè)數通常記為

而不難證明當k=n/2（若n是偶數）或者k=（n±1）/2（若n是奇數）時(shí)，它取最大值。為簡(jiǎn)單計，我們集中于n為偶數的情況。剛才證明了∶在n元素的集合中，可以做出

個(gè) n/2元素的子集合，其中沒(méi)有一個(gè)會(huì )包含任意另一個(gè)。也就是說(shuō)，

是這個(gè)問(wèn)題的一個(gè)下界。一個(gè)稱(chēng)為 Sperner 定理的結果指出，它也是一個(gè)上界。就是說(shuō)，如果取多于

個(gè)子集合，不論怎樣取，其中必有一個(gè)包含于另一個(gè)之內。

（2）設有一條有重量的鏈子，兩端掛在天花板的兩個(gè)鉤子上，而除此以外鏈子再沒(méi)有其他支撐點(diǎn)。這個(gè)掛著(zhù)的鏈子將是什么形狀？

初看起來(lái)，這并不像是一個(gè)極大極小問(wèn)題，但它很快就是了。這是因為物理學(xué)的一個(gè)一般原理告訴我們，鏈子將會(huì )靜止在一個(gè)使得位能為最小的形狀上。 這樣我們就面臨一個(gè)新問(wèn)題∶令A，B是（位于同一水平高度而）相距的距離為d 的兩點(diǎn)，c為長(cháng)度為l以A，B為兩端的曲線(xiàn)的集合，問(wèn)哪一條曲線(xiàn)C∈c具有最小位能？這里設任意曲線(xiàn)段的質(zhì)量正比于其長(cháng)度。這條曲線(xiàn)的位能是mgh，m是曲線(xiàn)的質(zhì)量，g是引力常數，而h為曲線(xiàn)的重心的高度。因為m和g不會(huì )改變，這個(gè)問(wèn)題就有了一個(gè)新的陳述∶哪一條曲線(xiàn)C∈c具有最小的平均高度？

這個(gè)問(wèn)題可以用一種稱(chēng)為變分法的技術(shù)來(lái)解決。粗略地說(shuō)，它的思想是∶有了一個(gè)集合c，又有了一個(gè)定義在c上的函數h，即平均高度，此函數把每一個(gè)C∈c 映為其平均高度。我們試著(zhù)來(lái)使h最小化，而處理這個(gè)問(wèn)題的一個(gè)自然的途徑是設法定義某種導數，然后再去找一條曲線(xiàn)C∈c，使得這個(gè)導數為0。注意，“導數”一詞在這里并不是沿著(zhù)曲線(xiàn)運動(dòng)時(shí)高度的變率，而是指曲線(xiàn)的平均高度（以線(xiàn)性方式）對于整個(gè)曲線(xiàn)的微小攝動(dòng)的響應。利用這一類(lèi)的導數來(lái)求最小值，比求定義在R上的函數的駐點(diǎn)要復雜一點(diǎn)，因為c是一個(gè)無(wú)限維的集合。然而這個(gè)途徑還是能起作用的，解也是知道的，是一種稱(chēng)為懸鏈線(xiàn)的曲線(xiàn)。這是又一個(gè)能夠準確回答的最小化問(wèn)題。

變分法的典型問(wèn)題都是求一條曲線(xiàn)、一個(gè)曲面或者更一般種類(lèi)的函數，使得某一個(gè)量達到最大或最小值。如果這個(gè)最大或者最小存在（對于一個(gè)無(wú)限維集合，它們絕非自動(dòng)存在的），則使得最大或最小達到的對象，會(huì )滿(mǎn)足一組偏微分方程，稱(chēng)為歐拉-拉格朗日方程。

（3）在1和n之間可以找到多少個(gè)數，使得其中不會(huì )有3個(gè)構成等差數列？如果n=9，答案是5。因為在1，2，4，8，9這五個(gè)數中，找不到3個(gè)成為等差數列。所以，在1到9之間有五個(gè)數，其中沒(méi)有等差數列。那么，在1 到9之間能否找到6個(gè)數使其中不會(huì )有3個(gè)數的等差數列呢?這也不會(huì )。原因如下∶

如果這6個(gè)數中已經(jīng)包含了5，那么必須舍去4或6。否則，4，5，6就是3個(gè)數的等差數列。類(lèi)似地，必須舍去3與7之一，2與8之一，1與9之一?？傊崛?個(gè)數，而只剩下5個(gè)，與題設的6個(gè)數發(fā)生矛盾?？傊?，這6個(gè)數中不能有5在。

我們又必須舍去1，2，3中的一個(gè)數，如果一個(gè)都不舍，則又出現了等差數列1，2，3，同理也必須舍去7，8，9中的一個(gè)。但是，我們已經(jīng)不允許取5，所以4和6都必須保留。但是那樣一來(lái)，就不能保留2或8。也必須舍去1，4，7之一，總之必須舍去至少4個(gè)數，而不可能留下6個(gè)數。

當n=9時(shí)，這種笨拙的逐個(gè)情況逐一論證的辦法還算行得通，n 稍微大一點(diǎn)，就無(wú)法逐一考慮了。對于這個(gè)問(wèn)題，似乎沒(méi)有一個(gè)干凈利落的答案準確地告訴我們，在1到n之間最大的不包含長(cháng)度為3的等差數列的集合是什么，所以我們代之以尋求這個(gè)集合的大小的上下界。為了證明一個(gè)下界，必須找到一個(gè)好的構造、一個(gè)不包含任意等差數列大集合的方法；而為了證明一個(gè)上界，就必須證明∶任意的有一定大小的集合，必定含有一個(gè)等差數列。

至今為止，離最佳的界還很遠呢。1947年，Behrend找到了一個(gè)大小為

其中沒(méi)有等差數列，而在1999年Jean Bourgain又證明了每一個(gè)大小為

都含有一個(gè)等差數列。當n=10^100 時(shí)，

（4）理論計算機科學(xué)是許多最小化問(wèn)題的來(lái)源∶當人們編制一個(gè)計算機程序以完成一項任務(wù)時(shí)，他就會(huì )希望在盡可能短的時(shí)間里完成它。下面是一個(gè)聽(tīng)起來(lái)很初等的例子∶如果想把兩個(gè)n位數相乘，需要多少步？

即使對于什么叫做一“步”并不太清楚，也能看到通常的乘法，即長(cháng)乘法，至少需要n^2步。這是因為在計算過(guò)程中，第一個(gè)數的每一位都會(huì )被第二位數的每一位去乘。 人們可能心想，這是必不可少的，但是事實(shí)上，有聰明的方法把問(wèn)題變換一下，就能極大地減少計算機完成這類(lèi)乘法所需的時(shí)間。最快的方法是用快速傅里葉變換來(lái)把計算的步數從n^2減少到

因為一個(gè)數的對數遠小于這個(gè)數本身。

另一個(gè)實(shí)質(zhì)上類(lèi)似的問(wèn)題是∶矩陣乘法有沒(méi)有快速算法？要想用經(jīng)典的方法把兩個(gè)n×n矩陣乘起來(lái)，需要對矩陣里面的數作n^3次單個(gè)的乘法。這個(gè)問(wèn)題上的突破主要來(lái)自 Strassen，他的思想是把這兩個(gè) n × n 矩陣的每一個(gè)都“平分”成 4 個(gè)

初看起來(lái)只不過(guò)是把原來(lái)矩陣的乘法化為8對小矩陣的乘法，但是這些乘法實(shí)際上是互有關(guān)聯(lián)的，Strassen做了7個(gè)乘法，而8個(gè)乘法就可以由此導出了。然后就可以利用遞歸，就是把同樣的思想用于加速這7個(gè)小矩陣的乘法，并仿此以往。

Strassen 的算法把矩陣乘法的步數的數量級從 n^3 降為

所以這已經(jīng)是顯著(zhù)的改進(jìn)，不過(guò)要當n很大時(shí)才是。他的基本的分而治之的策略后來(lái)又得到改進(jìn)，最近又有了新的突破（最近，人工智能推進(jìn)了數學(xué)研究的進(jìn)程，揭示了矩陣乘法的新可能性）。

關(guān)于更多的這一類(lèi)問(wèn)題，可見(jiàn)計算復雜性和算法設計的數學(xué)還有一類(lèi)更加微妙的最大化和最小化問(wèn)題。例如，假設我們想要理解相繼的素數之差的性質(zhì)。這種差最小為1（2和3之差），不難證明差沒(méi)有最大的，所以關(guān)于這些差似乎不會(huì )有有趣的最大化和最小化問(wèn)題。

然而事實(shí)是，如果先作適當的規范化，就可以提出很吸引人的問(wèn)題。素數定理指出，接近于n的素數，密度是大約1/logn，所以n附近的兩個(gè)素數間平均的空隙長(cháng)約為logn。如果p，q是兩個(gè)相繼的素數，就可以定義它們的規范化的空隙長(cháng)為（q一p）/logp。這個(gè)規范化空隙長(cháng)的平均值為1，但是會(huì )不會(huì )有時(shí)小得多，有時(shí)又大得多？

Westzynthius 在1931年就指出，甚至規范化空隙長(cháng)也可能任意長(cháng)，廣泛的信念則是它也可以任意接近于0（由著(zhù)名的孿生素數猜想立刻可以推出這件事），然而一直到2005年，才由Goldston，Pintz和Yildirim 證明了這一點(diǎn)。