凸體覆蓋泛函的估計與關(guān)于凸體覆蓋的Hadwiger猜想

吳森林, 呂亞方, 張珂珂

(中北大學(xué) 數(shù)學(xué)學(xué)院, 山西 太原 030051)

1 關(guān)于凸體覆蓋的Hadwiger猜想

凸體覆蓋泛函的估值是凸和離散幾何中的一個自然、基本且有難度的研究問題，得到了廣泛關(guān)注[1-31]。對任意整數(shù)m>1,令[m]={1,2,…,m}。Rn的一個內(nèi)部非空的緊凸子集K稱為一個n維凸體,所有n維凸體構(gòu)成的集合記作Kn。對任意凸體K,?c∈Rn和?γ∈(0,1),集合

γK+c={γx+c|x∈K}

稱為K的一個小位似體,γ稱為該小位似體的位似系數(shù)。對任意正整數(shù)m,令

Γm(K)=inf{γ>0|?{ci|i∈[m]}

并稱Γm(K)為K的m-覆蓋泛函。容易驗證, 上述定義中的下確界可達。若C={ci|i∈[m]}滿足

K?Γm(K)K+C,

則稱C是K的一個m-最優(yōu)構(gòu)圖。

當K?R2是歐氏平面的單位圓盤時,Γm(K)的估值問題便是經(jīng)典的圓覆蓋問題(disk covering problem),該問題自1916年來得到了諸多數(shù)學(xué)家的深入研究(參見文獻[1]及其參考文獻)。2005年以前關(guān)于凸體覆蓋泛函估值的大部分結(jié)果可在文獻[2]中找到。除了它本身的研究價值和理論意義外, 凸體覆蓋泛函的估計問題還在關(guān)于凸體覆蓋的Hadwiger猜想研究中扮演著重要角色。

猜想1(關(guān)于凸體覆蓋的Hadwiger猜想, 簡稱為(H)猜想) 對任意n維凸體K,覆蓋K所需的K內(nèi)部平移的最小個數(shù)c(K)(稱為凸體K的覆蓋數(shù))滿足

n+1≤c(K)≤2n。

右側(cè)等式成立當且僅當K是一個仿立方體([0,1]n在某個非奇異仿射變換下的像)。

該問題被多部專著[2-4]和多篇綜述文章[5-8]反復(fù)提及, 近年來得到不少學(xué)者的研究[9-18]。但它在3維的情形仍是一個非常困難的公開問題，很大程度上是因為c(K)關(guān)于Hausdorff距離dH不連續(xù)，僅具有上半連續(xù)性，即當凸體L充分接近給定凸體K時,c(L)≤c(K)總成立。因此,即使驗證了c(L)≤2n對在(Kn,dH)中稠密的凸體類均成立也無法判斷c(K)≤2n,?K∈Kn。事實上,對Kn中光滑的凸體K,c(K)=n+1總成立。

2 宗傳明基于凸體覆蓋泛函的估計方案

文獻[19]給出了用于攻克(H)猜想的方案, 利用覆蓋泛函Γm(·)關(guān)于Banach-Mazur距離dBM的連續(xù)性,克服了c(K)不連續(xù)性帶來的困難。如文獻[6]所述,該方案是針對(H)猜想的首個基于計算機算法和程序的解決方案。

一方面,c(K)是一個仿射不變量。因此,在研究(H)猜想時, 利用Banach-Mazur距離dBM來度量凸體之間的差異更為自然。?K1,K2∈Kn，

T(K2)?γK1+x},

其中An是Rn到自身的非奇異仿射變換的全體構(gòu)成的集合。顯然,dBM(K1,K2)=0當且僅當K1和K2仿射等價。令～表示仿射等價關(guān)系,[K]表示K∈Kn所在的仿射等價類。對任意一對凸體K1和K2,令

dBM([K1],[K2])=dBM(K1,K2)。

不難驗證(Kn/～,dBM)是一個緊度量空間。在不引起混淆的條件下,我們不區(qū)分(Kn/～,dBM)和(Kn,dBM)。

另一方面,c(K)等于覆蓋K所需小位似體的最小個數(shù)[4],此處小位似體的位似系數(shù)不一定相等。因此,c(K)≤m當且僅當Γm(K)<1。于是, 驗證

c(K)≤2n,?K∈Kn

(1)

(稱為(H)-猜想的不等式部分)可以轉(zhuǎn)化為驗證

Γ2n(K)<1,?K∈Kn。

(2)

最后,覆蓋泛函關(guān)于dBM有較好的連續(xù)性。令Γm([K])=Γm(K),?K∈Kn。文獻[19]指出Γm(·)在(Kn/～,dBM)上一致連續(xù),文獻[6]進一步證明Γm(·)是Lipschitz連續(xù)的。上述結(jié)果表明(1)式成立的充要條件為

因此,若(1)式成立,則?ε>0使得

dBM(K,L)≤ε?|Γ2n(K)-Γ2n(L)|≤

令N?Kn為(Kn/～,dBM)的一個ε-網(wǎng)。亦即,?K∈Kn,?L∈N使得dBM(K,L)≤ε。那么

基于這些觀察,宗傳明提出了如下用以攻克(H)猜想的方案[30]:

2)適當?shù)剡x取ε>0并構(gòu)造Kn的ε-網(wǎng)N。

3 凸體覆蓋泛函的現(xiàn)有估計

a(y)x6-b(y)x5+c(y)x4-d(y)x3+

e(y)x2-f(y)x+g(y)=0，

圖1 用5個小圓盤覆蓋單位圓

表1列出了一些常見凸體覆蓋泛函的精確值。

表1 已知Γm(·)的精確值

可以看出,即使是對n維單純形這樣“簡單”的凸體,覆蓋泛函的精確值計算已非常不易。

當n≥3時,對Γm(K)估值的難度從如下結(jié)果[26]可見一斑:

一方面,上式中下標24遠大于8=23; 另一方面,0.991 6…太過靠近1。即便如此, 我們?nèi)钥梢匀〉媚承┨厥馔贵w類覆蓋泛函值的較好估計。例如,宗傳明[19]證明,若K∈K3是一個以平面凸體為底的凸錐,則

并且

文獻[27]證明，若K∈Kn,

C1=conv(K×{0}∪{p}),

C2=conv(K×{0}∪{p,q}),

其中p,q∈Rn+1/Rn×{0}滿足[p,q]∩(K×{0})≠?,則

(3)

上述估計在很多情形下可以得到C1和C2的覆蓋泛函的較好估計, 甚至得到它們的精確取值。

文獻[27]還考慮了凸體K與線段L的Minkowski和K+L的覆蓋泛函的取值問題。通過適當?shù)姆律渥儞Q,不妨設(shè)平行于H=Rn-1×{0}的超平面在en和-en處支撐凸體K。令Kλ=K+λ[-u,u],其中u=en,Πu(K)為Rn至H上的正交投影。文獻[28]給出了Γm(Kλ)的如下估計:

|Γm(Kλ)-Γm(K)|≤λ,?λ≥0,

當λ>1時，可以利用Γm(Πu(K)+[-u,u])的覆蓋泛函的值估計Γm(Kλ):

其中,Πu(K)+[-u,u]的覆蓋泛函的取值與Γm(Πu(K))的取值密切相關(guān)。特別地,當m=c(Πu(K))時, 有

Γ2m(Πu(K)+[-u,u])=Γm(Πu(K))。

文獻[28]還考慮了兩個凸體直和的覆蓋泛函的取值問題。設(shè)Rn是兩個線性子空間L1和L2的直和,K1和K2分別為L1和L2中的凸體,并且它們均含原點。那么,?m1，m2,有

Γm1×m2(K1⊕K2)≤max{Γm1(K1),Γm2(K2)}。

特別地,當m1=c(K1)且m2=c(K2)時,有

Γm1×m2(K1⊕K2)=max{Γm1(K1),Γm2(K2)}。

若K∈Kn關(guān)于原點O中心對稱,則(Rn,‖·‖K)是一個以K為單位球的Banach空間,其中

‖·‖K=inf{λ>0|x∈λK},?x∈Rn，

是K的Minkowski泛函。利用方向凸性模等Banach空間幾何理論中的概念和結(jié)論,文獻[29]給出了中心對稱凸體覆蓋泛函的一般估計。當K是一個中心對稱的平面凸體且m=4時,給出的估計是最優(yōu)的。

由于所有凸多面體構(gòu)成的集族在Kn中是稠密的,其覆蓋泛函的估值有重要意義。文獻[9]在2016年證明:若P∈Cn是一個有m個頂點的中心對稱的n維多面體,則

λ(x,P)=sup{λ∈[0,1]|?ν∈V和y∈P

s.t.x=λν+(1-λ)y}。

記

λ(P)=inf{λ(x,P)|x∈P},

γ(C,P)=min{γ≥0|?c∈Rn

s.t.C?c+γP},?C?V。

文獻[15]證明,若P∈Kn且C1,C2,…,Cm?V是V的一個覆蓋,則

Γm(P)≤1+λ(P)max{γ(Ci,P)|i∈[m]}-

λ(P)。

(4)

?m∈Z+。

(5)

如前所述, 對很多凸體, 即使是像歐氏平面單位圓盤這樣我們非常熟悉的平面凸體,當m不夠特殊時,得到Γm(K)的精確值非常困難。因此, 利用計算機算法和程序來給出凸體覆蓋泛函的近似值是非常必要的。早在1962年, Zahn在IBM 704用FORTRAN語言編寫的程序以±0.002的精度給出了用m=2,3,…,10個等大的小圓覆蓋單位圓所需的最小半徑[24]。需要注意的是,Zahn的算法只能給出對應(yīng)目標函數(shù)的局部最小值。

為了取得精度較高的覆蓋泛函的估計, 采用類似于文獻[30-31]中論述的幾何分支定界法更為恰當。據(jù)我們所知, 目前尚無用于覆蓋泛函估計的確定性全局優(yōu)化算法。在嘗試設(shè)計這種算法時，會面臨兩個問題:其一,隨著n的增加, 估計n維凸體覆蓋泛函Γ2n(K)值的算法復(fù)雜度增加很快;其二,對很多具有一定對稱性的凸體K和給定的m值,K的m-最優(yōu)構(gòu)圖并不唯一存在。只有對覆蓋泛函估值有一個更全面更深刻的認識才能夠最大限度地克服這些不利因素。

4 總結(jié)與展望

凸體覆蓋泛函的估值是來自于凸和離散幾何的一個難題, 除去自身的研究價值外, 它還在關(guān)于凸體覆蓋的Hadwiger猜想的研究當中扮演著重要角色。學(xué)者們在特殊凸體覆蓋泛函的精確值的計算、凸體類覆蓋泛函值上界的估計等方向進行了不少研究。然而, 目前僅有極少數(shù)特殊凸體覆蓋泛函的精確值已知, 只有若干性質(zhì)比較簡單的凸體類覆蓋泛函的上界有較好估計, 尚沒有用于計算凸體覆蓋泛函值的確定性全局優(yōu)化算法，且相應(yīng)算法的設(shè)計過程面臨著亟待解決的關(guān)鍵理論問題。