彩虹??等差數列

02-17

我們考慮對abelian group $G$ 進行染色。所謂對一個群 $G$ 進行 $r$ 染色是指存在 $G$ 到 $[r]$ 的一個滿射 $c$ 。稱一個長度為 $k$ 的等差數列 $A$ 是rainbow的，當且僅當 $c$ 在 $A$ 上是單射。這裡 $[r]$ 代表集合 ${1,2,dots,r}$ .

我們考慮anti-van der Waerden number $mathsf{aw}(S,k)$ ，指的是對 $G$ 的子集 $S$ 最小染色數，使得 $S$ 一定存在長度為 $k$ 的等差數列。首先考慮 $mathsf{aw}([n],3)$ .

題圖是對 $[27]$ 的四染色，其不包含長度為3的rainbow等差數列，也就是說 $mathsf{aw}([27],3)ge5$ .實際上我們可以推廣這個染色方法：對 $n=3^m$ ，定義 $c:[n] o[m+1]$ ，對 $[n]$ 中任意元素 $x$ ， $c(x)=m+1-mathcal{O}_3(x)$ ，其中 $mathcal{O}_3(x)$ 是 $x$ 中因子 $3$ 的個數。因此我們可以猜測 $mathsf{aw}([n],3)geqlog_3n+2$ 。實際上對於 $n$ 不是 $3$ 的冪的情形，我們可以通過類似的方法構造 $log_3n+1$ 的反例。

對於 $mathsf{aw}([n],3)$ 的上界我們目前只有平凡上界：對於 $i<mathsf{aw}([n],3)$ ，考慮 $b_i$ 是最大的 $x$ 使得 $[x]$ 恰好被 $i$ 染色。顯然， $b_{i+1}ge2b_i$ ，否則 $2b_i-b_{i+1}+1,b_i+1,b_{i+1}+1$ 是rainbow等差數列。於是當n比較大時， $mathsf{aw}([n],3)lelog_2n+1$ 。

至於 $mathsf{aw}(mathbb{Z}_n,3)$ ，容易看出其被 $n$ 的因子 $p$ 的 $mathsf{aw}(mathbb{Z}_p,3)$ 確定。2003年，當時還是高中生的J. Fox的第一篇paper里證明， $mathsf{aw}(mathbb{Z}_{2^m},3)=3$ 對所有 $m$ 都成立。（寫到這裡感覺有點恐怖啊，15年前還是高中生，15年後他的PhD學生都當了教授...）

Emmmmm...本來還想花篇幅寫一下 $mathsf{aw}(mathbb{Z}_n,3)$ 的性質，突然懶了，因為比較複雜。。這個問題也是我最近才開始思考的一個問題。在過去的幾十年中，數學家們比較關注的是「同色等差數列」（Roth定理，van der Waerden定理，Szemeredi定理，Green-Tao定理），Rainbow等差數列屬於比較新的方向。不過在Graph Theory中，很多時候Rainbow版本的定理要比monochromatic的情況複雜。比如我們高中都學過的Turan定理，他的Rainbow版本目前還是open的。

下面寫幾個我最近思考的問題，從易到難（我估計的。。）如下。最近比較無聊的朋友可以想想。。

通過對染色的粗略估計，我們對 $mathsf{aw}([n],3)$ 有 $log_2n$ 的上界，但是目前所有的例子和構造都是 $log_3n$ 的。是不是 $log_3n$ 已經足夠了？

Conjecture 1：存在常數 $C$ 使得 $mathsf{aw}([n],3)=log_3n+C$

題圖給出了對 $n=3^m$ 情形時， $m+1$ 種染色不足以得到長度為3的rainbow等差數列的構造。那麼 $m+2$ 種顏色是否足夠了？

Conjecture 2： $mathsf{aw}([3^m],3)=m+2$

可以發現 $mathsf{aw}([n],3)$ 對 $n$ 不單調。那麼它在某個 $n$ 時會不會有比較大的drop？

Conjecture 3： $mathsf{aw}([n+1],3)gemathsf{aw}([n],3)-1$

考慮對 $mathbb{Z}_p$ 的染色。容易看出如果Artins Conjecture成立，（存在無窮多p使得2是 $mathbb{Z}_p^ imes$ 生成元）那麼 $mathsf{aw}(mathbb{Z}_p,3)=3$ .

Conjecture 4：存在無窮多素數 $p$ 使得 $mathsf{aw}(mathbb{Z}_p,3)=3$

通過對 $mathsf{aw}(S,k)$ 的定義可以「感覺」到，如果讓很多顏色染色的數量盡量少（比如就一兩個），可以「避免」出現rainbow等差數列。所以一個更困難的問題是，如果我們考慮每種顏色染色的數量相同呢？對於任意 $kge3$ 定義 $T_k$ 是最小正整數 $r$ ，使得對 $[rn]$ 的 $r$ 染色，（其中每種顏色各染了 $n$ 個數字）一定存在長為 $k$ 的rainbow等差數列。

Conjecture 5： $T_k=Theta(k^2)$