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

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

這問題motivation是Alon, Axenovich, Goldwasser提出了上述的問題，但是只考慮跟軸平行的dd-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=j2ks=j2^k，其中jj是ss的奇數部分的話，可以考慮取AA是jj個平行的n−d+kn-d+k-flats的聯集，這樣的話只要大部分的dd-flats跟那些n−d+kn-d+k-flats都交在dd-flat裡的codimension d−kd-k，所以都交2k2^k個點。由於取了jj個n−d+kn-d+k-flats，總共就有s=j2ks=j2^k個點。而那些不好的dd-flats都來自於跟AA的方向有太多平行的人，算一下比例會發現好的dd-flats大概有1−2−k1-2^{-k}的比例。而我們的第一個結果證明了如果kk跟d−kd-k都很大的話，這個比例是asymptotically對的。

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

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

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

定理1： 令s=j2k≤2ds=j2^k\leq 2^d，其中jj是奇數且kk足夠大，則

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

所以當k,d−k→∞k,d-k\to\infty時，

1−λ∗(d,j2k)=(1+o(1))2−k.1-\lambda^*(d,j2^k)=(1+o(1))2^{-k}.

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

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

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

λ∗(d,1)=(1−2−d)2d−1.\lambda^*(d,1)=(1-2^{-d})^{2^d-1}.

特別地，當d→∞d\to\infty時，

λ∗(d,1)→1e.\lambda^*(d,1)\to \frac1e.

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

s=j2ks=j2^k的case

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

固定一個A⊆F2nA\subseteq\mathbb F_2^n，我們稱一個dd-flat QQ是good的，如果

∣Q∩A∣=s,|Q\cap A|=s,

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

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

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

S=A∩W.S=A\cap W.

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

Hξ,0=x∈W:ξ(x)=0H_{\xi,0}={x\in W:\xi(x)=0}

跟

Hξ,1=x∈W:ξ(x)=1.H_{\xi,1}={x\in W:\xi(x)=1}.

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

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

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

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

f^(ξ)=∣S∩Hξ,0∣−∣S∩Hξ,1∣.\widehat f(\xi)=|S\cap H_{\xi,0}|-|S\cap H_{\xi,1}|.

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

f^(ξ)≠0\widehat f(\xi)\neq 0

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

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

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

這邊我們需要以下引理。

引理： 令HH是mm維的F2\mathbb F_2-vector space，S⊆HS\subseteq H非空，並令

r=ν2(∣S∣),r=\nu_2(|S|),

則

∣supp(1S^)∣≥2m−r.|\textup{supp}(\widehat{1_S})|\geq 2^{m-r}.

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

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

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

回到我們的問題，因為

∣S∣=j2k+1|S|=j2^{k+1}

且jj是奇數，所以

ν2(∣S∣)=k+1.\nu_2(|S|)=k+1.

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

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

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

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

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

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

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

Nice subspaces

令

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

我們考慮frequency space裡的aa維subspaces，並稱LL是nice的，如果它跟TT恰好交在

L∩T=0,γL\cap T={0,\gamma}

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

令

U=L⊥⊆W.U=L^\perp\subseteq W.

因為LL裡只有00跟γ\gamma在Fourier support中，Fourier inversion會告訴我們，對所有x∈Wx\in W，

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

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

∣A∩(x+U)∣≠∣A∩(x+w+U)∣.|A\cap(x+U)|\neq |A\cap(x+w+U)|.

也就是說，兩個相差ww的平行UU-cosets中，AA的點數不一樣。

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

考慮所有滿足

Q∩W=x+UQ\cap W=x+U

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

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

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

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

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

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

2a2−a+12^{a^2-a+1}

個dd-flats是bad的。

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

先從T∖0T\setminus{0}裡選γ\gamma，大概有2d−k2^{d-k}個選擇。然後依序選v2,…,vav_2,\ldots,v_a，但在第ii步要避開

T+span(γ,v2,…,vi),T+\textup{span}(\gamma,v_2,\ldots,v_i),

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

∣T∣≤2d+1−k,|T|\leq 2^{d+1-k},

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

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

計算完會得到

ρ≥2−k(1−2−(d−k))(1−2−a)∏i=1a−1(1−2i−k).\rho\geq 2^{-k}(1-2^{-(d-k)})(1-2^{-a})\prod_{i=1}^{a-1}(1-2^{i-k}).

最後選

a=⌊k/2⌋.a=\lfloor k/2\rfloor.

此時後面的修正項滿足

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

因此

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

就證完定理1了！

簡單總結一下這個證明：

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

s=1s=1的case

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

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

x,v1,…,vd∈F2n,x,v_1,\ldots,v_d\in\mathbb F_2^n,

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

x+∑i∈Svi,S⊆[d].x+\sum_{i\in S}v_i,\qquad S\subseteq[d].

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

令這個機率為pp，並令

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

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

p2d=Λd(1A,f,…,f),\frac{p}{2^d}=\Lambda_d(1_A,f,\ldots,f),

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

因為

1A=1−f,1_A=1-f,

所以由multilinearity，

p2d=Λd(1,f,…,f)−Λd(f,…,f).\frac{p}{2^d}=\Lambda_d(1,f,\ldots,f)-\Lambda_d(f,\ldots,f).

Gowers–Cauchy–Schwarz inequality告訴我們

Λd(1,f,…,f)≤Λd(f,…,f)(2d−1)/2d.\Lambda_d(1,f,\ldots,f)\leq\Lambda_d(f,\ldots,f)^{(2^d-1)/2^d}.

令

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

那我們就得到

p2d≤u2d−1(1−u).\frac{p}{2^d}\leq u^{2^d-1}(1-u).

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

u=1−2−du=1-2^{-d}

的時候最大，所以

p2d≤2−d(1−2−d)2d−1,\frac{p}{2^d}\leq 2^{-d}(1-2^{-d})^{2^d-1},

也就是

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

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

λ∗(d,1)=(1−2−d)2d−1.\lambda^*(d,1)=(1-2^{-d})^{2^d-1}.

證完了OAO。

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

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

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