牛仔骨復仇戰

好久沒發blog了，先來講點數學。這次的問題如下：

Affine subspace statistics問題：給定 $n,d,s$ ，考慮一個集合 $A\subseteq\mathbb{F}_2^n$ ，請問最多有多少比例的 $d$ -flats ( $d$ 維affine subspaces) 恰好包含 $A$ 中的 $s$ 個點？

這問題motivation是Alon, Axenovich, Goldwasser提出了上述的問題，但是只考慮跟軸平行的 $d$ -flats的case，稱為hypercube statistics問題。xzx在去年的時候跟我說了這問題，然後她就去邊suffer各種問題+申請了(?)。然後Affine subspace statistics問題應該是這個問題的簡化版(或是更對稱的版本)。

上學期某一天子超來訪問的時候，我們剛好在吃飯，然後她說她做出了Affine subspace statistics問題的一個蠻好的上界，但跟下界差兩倍。我想說兩倍我熟阿，於是我就邊吃黑椒牛仔骨邊想這問題。首先，有個簡單的bootstraping可以把那個兩倍變成1.5倍。然後，我就在咬牛仔骨的時候，被某塊很貼近牛仔骨的筋崩斷了我的智齒，還好沒傷到神經。當天晚上我做惡夢夢到整晚邊咬牛仔骨邊做這題，於是我就跟它槓上了。然後我跟xzx跟dima就開始搞這問題了。

在這裡塞paper連結應該是個好時機(?)：http://arxiv.org/abs/2607.25920

基本上呢，這問題有兩種構造。假設 $s=j2^k$ ，其中 $j$ 是 $s$ 的奇數部分的話，可以考慮取 $A$ 是 $j$ 個平行的 $n-d+k$ -flats的聯集，這樣的話只要大部分的 $d$ -flats跟那些 $n-d+k$ -flats都交在 $d$ -flat裡的codimension $d-k$ ，所以都交 $2^k$ 個點。由於取了 $j$ 個 $n-d+k$ -flats，總共就有 $s=j2^k$ 個點。而那些不好的 $d$ -flats都來自於跟 $A$ 的方向有太多平行的人，算一下比例會發現好的 $d$ -flats大概有 $1-2^{-k}$ 的比例。而我們的第一個結果證明了如果 $k$ 跟 $d-k$ 都很大的話，這個比例是asymptotically對的。

另一個構造是當 $s=1$ 的時候，取random的 $A$ ，其中每個點被放進 $A$ 的機率是 $2^{-d}$ ，這樣的話好的 $d$ -flats的比例大概是 $1/e$ ，而這個case其實是個Gowers–Cauchy–Schwarz inequality的簡單推論，這部分是chatgpt教會我們的XD

以下是證明的outline，但我太忙(ㄌㄢˇ)，所以讓gpt代勞吧(?)

好啊，那我們先正式講一下結果。令 $\lambda^*(d,s)$ 是當 $n\to\infty$ 時，好的 $d$ -flats比例的最大值。我們證明了以下兩個定理。

定理1：令 $s=j2^k\leq 2^d$ ，其中 $j$ 是奇數且 $k$ 足夠大，則

$\lambda^*(d,s)=1-(1-2^{-(d-k)})2^{-k}+O(2^{-3k/2}).$

所以當 $k,d-k\to\infty$ 時，

$1-\lambda^*(d,j2^k)=(1+o(1))2^{-k}.$

換句話說，前面那個平行flats的construction不只order是對的，連leading coefficient也是對的。

另外，對 $s=1$ ，我們可以完全決定答案。

定理2：對所有 $d\geq 1$ ，

$\lambda^*(d,1)=(1-2^{-d})^{2^d-1}.$

特別地，當 $d\to\infty$ 時，

$\lambda^*(d,1)\to \frac1e.$

也就是說，每個點獨立地以機率 $2^{-d}$ 放進 $A$ 的random construction真的是optimal的。

$s=j2^k$ 的case

先來講比較麻煩的第一個定理。

固定一個 $A\subseteq\mathbb F_2^n$ ，我們稱一個 $d$ -flat $Q$ 是good的，如果

$|Q\cap A|=s,$

否則稱它是bad的。令 $\rho$ 是bad $d$ -flats的比例。我們的目標就是證明

$\rho\geq (1-2^{-(d-k)})2^{-k}-O(2^{-3k/2}).$

首先我們用一個averaging找到一個 $(d+1)$ -flat $W$ ，使得 $W$ 裡面的 $d$ -flats有至多 $\rho$ 比例是bad的。令

$S=A\cap W.$

由於 $W$ 是一個 $(d+1)$ -flat，裡面的 $d$ -flats就是它的affine hyperplanes。每個非零linear functional $\xi$ 都會把 $W$ 分成一對平行的hyperplanes

$H_{\xi,0}={x\in W:\xi(x)=0}$

跟

$H_{\xi,1}={x\in W:\xi(x)=1}.$

如果 $|S|\neq 2s$ ，那每一對平行hyperplanes中至少有一個不是good的，所以 $W$ 裡至少一半的hyperplanes是bad的。這樣我們早就得到比需要更強的不等式了。因此，真正需要處理的情況一定滿足

$|S|=2s=j2^{k+1}.$

接下來Fourier analysis就很自然地冒出來了。

令 $f=1_S$ 。對非零頻率 $\xi$ ，我們有

$\widehat f(\xi)=|S\cap H_{\xi,0}|-|S\cap H_{\xi,1}|.$

由於兩邊的總點數是 $2s$ ，這兩個hyperplanes要嘛都包含剛好 $s$ 個 $S$ 中的點，要嘛兩個都不是good的。因此

$\widehat f(\xi)\neq 0$

恰好代表這一對hyperplanes都是bad的。

所以問題就變成：一個大小是 $j2^{k+1}$ 的集合，它的Fourier support最少可以多小？

奇數部分如何逼出一大堆Fourier coefficients

這邊我們需要以下引理。

引理：令 $H$ 是 $m$ 維的 $\mathbb F_2$ -vector space， $S\subseteq H$ 非空，並令

$r=\nu_2(|S|),$

則

$|\textup{supp}(\widehat{1_S})|\geq 2^{m-r}.$

這邊的 $\nu_2(|S|)$ 就是 $|S|$ 裡面有幾個factor $2$ 。

先來直觀解釋一下。如果Fourier support避開了某個 $(r+1)$ 維的frequency subspace，那麼Fourier inversion會告訴你，某個codimension $r+1$ 的subspace的每個coset裡都有一樣多個 $S$ 中的點。這樣的話， $|S|$ 就必須被 $2^{r+1}$ 整除。但根據 $r$ 的定義，它只被 $2^r$ 整除，所以不可能。

實際上，這個argument告訴我們，非零的Fourier support必須跟每個 $(r+1)$ 維的frequency subspace相交。用finite geometry的語言，這就是一個blocking set。接著套用Bose–Burton theorem，就得到上面的 $2^{m-r}$ 。

回到我們的問題，因為

$|S|=j2^{k+1}$

且 $j$ 是奇數，所以

$\nu_2(|S|)=k+1.$

又因為 $\dim W=d+1$ ，我們得到

$|\textup{supp}(\widehat f)|\geq 2^{d-k}.$

另一方面，Fourier support裡的每一個非零frequency都對應到兩個bad hyperplanes，而我們選的 $W$ 裡沒有太多bad hyperplanes，所以

$|\textup{supp}(\widehat f)|\leq 2^{d+1-k}.$

因此這個Fourier support的大小大概就是 $2^{d-k}$ 。

但到這邊還不夠。這只是在 $W$ 裡找到很多bad $d$ -flats，直接數只會得到之前差一個constant的bound。我們需要把 $W$ 裡的Fourier information拿出去，在整個 $\mathbb F_2^n$ 裡製造更多bad flats。

這也是證明中比較主要的idea。

Nice subspaces

令

$T=\textup{supp}(\widehat f).$

我們考慮frequency space裡的 $a$ 維subspaces，並稱 $L$ 是nice的，如果它跟 $T$ 恰好交在

$L\cap T={0,\gamma}$

其中 $\gamma\neq 0$ 。也就是說， $L$ 裡面恰好有一個非零的Fourier coefficient。

令

$U=L^\perp\subseteq W.$

因為 $L$ 裡只有 $0$ 跟 $\gamma$ 在Fourier support中，Fourier inversion會告訴我們，對所有 $x\in W$ ，

$|A\cap(x+U)|=2^{-a}\left(\widehat f(0)+\widehat f(\gamma)(-1)^{\gamma(x)}\right).$

現在選一個 $w\in W$ 使得 $\gamma(w)=1$ 。因為 $\widehat f(\gamma)\neq 0$ ，我們有

$|A\cap(x+U)|\neq |A\cap(x+w+U)|.$

也就是說，兩個相差 $w$ 的平行 $U$ -cosets中， $A$ 的點數不一樣。

好啊，那這件事跟bad $d$ -flats有什麼關係呢？

考慮所有滿足

$Q\cap W=x+U$

的 $d$ -flats $Q$ 。把 $Q$ 跟 $Q+w$ 配成一對，並考慮它們的聯集

$Q^+=Q\cup(Q+w),$

這會是一個 $(d+1)$ -flat。

如果 $|Q^+\cap A|\neq 2s$ ，那麼每一對 $Q,Q+w$ 裡面至少有一個是bad的。

如果 $|Q^+\cap A|=2s$ ，那 $Q$ 是bad的若且唯若 $Q+w$ 也是bad的。另一方面，因為 $Q\cap W$ 與 $(Q+w)\cap W$ 包含不同數量的 $A$ 中的點，一個簡單的double counting會告訴我們，不可能所有相關的 $Q$ 都是good的。所以這個case也至少會出現兩個bad flats。

認真把數量算完後，每個nice $L$ 會強迫至少

$2^{a^2-a+1}$

個 $d$ -flats是bad的。

接著我們只需要數nice subspaces有幾個。

先從 $T\setminus{0}$ 裡選 $\gamma$ ，大概有 $2^{d-k}$ 個選擇。然後依序選 $v_2,\ldots,v_a$ ，但在第 $i$ 步要避開

$T+\textup{span}(\gamma,v_2,\ldots,v_i),$

確保最後的span不會再碰到其他 $T$ 中的點。因為

$|T|\leq 2^{d+1-k},$

只要 $a$ 沒有太大，每一步都還有很多選擇。

而且不同的nice $L$ 所產生的 $d$ -flats不會重複，因為從 $Q\cap W$ 的方向可以把 $L$ 找回來。因此我們可以把所有nice subspaces製造的bad flats直接加起來。

計算完會得到

$\rho\geq 2^{-k}(1-2^{-(d-k)})(1-2^{-a})\prod_{i=1}^{a-1}(1-2^{i-k}).$

最後選

$a=\lfloor k/2\rfloor.$

此時後面的修正項滿足

$(1-2^{-a})\prod_{i=1}^{a-1}(1-2^{i-k})=1-O(2^{-k/2}),$

因此

$\rho\geq (1-2^{-(d-k)})2^{-k}-O(2^{-3k/2}),$

就證完定理1了！

簡單總結一下這個證明：

$|S|$ 的奇數部分告訴我們它的Fourier support不能太小；很多Fourier coefficients讓我們找到很多nice subspaces；每個nice subspace又會透過兩個大小不同的平行cosets製造很多bad flats。數完之後就剛好得到平行flats construction的leading coefficient。

$s=1$ 的case

接下來講一個短很多的證明。

固定 $A\subseteq\mathbb F_2^n$ ，獨立均勻地選

$x,v_1,\ldots,v_d\in\mathbb F_2^n,$

並考慮 $2^d$ 個帶label的點

$x+\sum_{i\in S}v_i,\qquad S\subseteq[d].$

當 $v_1,\ldots,v_d$ 線性獨立時，這些點就是一個均勻隨機的 $d$ -flat。當 $n\to\infty$ 且 $d$ 固定時，它們線性相依的機率是 $o(1)$ ，所以我們只需要估計這 $2^d$ 個點中恰好一個落在 $A$ 裡的機率。

令這個機率為 $p$ ，並令

$f=1_{A^c}.$

由對稱性，我們可以指定其中一個點落在 $A$ 中，再乘上 $2^d$ 。因此

$\frac{p}{2^d}=\Lambda_d(1_A,f,\ldots,f),$

其中 $\Lambda_d$ 是標準的Gowers cube average。

因為

$1_A=1-f,$

所以由multilinearity，

$\frac{p}{2^d}=\Lambda_d(1,f,\ldots,f)-\Lambda_d(f,\ldots,f).$

Gowers–Cauchy–Schwarz inequality告訴我們

$\Lambda_d(1,f,\ldots,f)\leq\Lambda_d(f,\ldots,f)^{(2^d-1)/2^d}.$

令

$u=\Lambda_d(f,\ldots,f)^{1/2^d}\in[0,1].$

那我們就得到

$\frac{p}{2^d}\leq u^{2^d-1}(1-u).$

到這邊additive combinatorics已經下班了，只剩下一個高中微積分問題。右邊在

$u=1-2^{-d}$

的時候最大，所以

$\frac{p}{2^d}\leq 2^{-d}(1-2^{-d})^{2^d-1},$

也就是

$p\leq(1-2^{-d})^{2^d-1}.$

這剛好就是random construction給出的值。因此

$\lambda^*(d,1)=(1-2^{-d})^{2^d-1}.$

證完了OAO。

值得一提的是，在原本的hypercube statistics問題中， $s=1$ 時random construction是不是optimal目前仍然是open的。Affine flats因為可以直接寫成一個完整的Gowers cube，所以一次Gowers–Cauchy–Schwarz就可以結束；只考慮跟軸平行的subcubes反而沒有這麼完整的symmetry。

Fun fact： $s=1$ 這個證明是我們看到 $d=2$ 的argument後，叫ChatGPT試著generalize找到的。第一個定理的證明則是純人類生成。

結論是AI可以幫忙做一發Gowers–Cauchy–Schwarz，但咬斷智齒跟數nice subspaces這種苦工目前還是人類的工作(?)

牛仔骨復仇戰

的case

奇數部分如何逼出一大堆Fourier coefficients

Nice subspaces

的case

分享此文：

發表留言 取消回覆

$s=j2^k$ 的case

$s=1$ 的case

發表留言取消回覆