奇(ㄐㄧ)怪的小鎮

老樣子，先簡單介紹一下數學問題，再講點這個project的故事，最後再來點深入的數學吧！

組合中的線性代數方法裡，最入門的應用大概就是Eventown跟Oddtown問題了，先來個問題敘述：

Oddtown問題：有個奇怪的小鎮裡面有 $n$ 個人跟一堆俱樂部，其中俱樂部裡可以有重複的成員。假設每個俱樂部都有奇數個人，且兩兩的交集都是偶數個人，請問最多有幾個俱樂部？

既然說是線性代數方法，那我們就把每個俱樂部看作是一個 $0$ – $1$ 向量，第 $i$ 個位置表示第 $i$ 個人在不在這個俱樂部裡面。假設有 $m$ 個俱樂部，我們就會得到 $m$ 個向量 $v_1,\dots,v_m$ 。既然題目是mod $2$ ，那我們就把這些向量看作是 $\mathbb{F}_2^n$ 裡的向量吧。那從題目條件不難發現

$v_i\cdot v_i=1$ ,

$v_i\cdot v_j=0$ , if $i\neq j$

熟悉線代的小夥伴就知道，這保證了這些向量線性獨立，於是必須有 $m\leq n$ 。而這個上界是可以達到的：考慮標準基底(也就是每個俱樂部恰好對應一個人)。

而在我們的文章中，我們關心的是，如果把mod $2$ 換成mod $\ell$ ，也就是以下問題

$\ell$ -Oddtown問題：有個奇怪的小鎮裡面有 $n$ 個人跟一堆俱樂部，其中俱樂部裡可以有重複的成員。假設每個俱樂部裡人數都不是 $\ell$ 的倍數，且兩兩的交集人數都是 $\ell$ 的倍數，請問最多有幾個俱樂部？

這問題在 $\ell$ 是質數的時候，做法跟上面一模一樣，但 $\ell$ 是合數的時候這問題就難了，也是我們paper主要關心的問題。先來個連結，然後開始講這個project的故事XD

Paper連結：https://arxiv.org/abs/2509.00586

———-故事時間———-

今年四月泽宇跑來波士頓玩，然後跟我提了這個問題中，Boris跟他有個線性代數問題不會做，然後跟我敘述了一下。於是我們就在晚餐前在common room想這個問題。

晚餐吃一吃，我越想越不對勁(?)。回想起丘賽學到的技巧：遇事不決，方的矩陣Jordan form，長的矩陣SVD(亂講)。於是發現我只要線性組合把其中一塊變成單位矩陣，然後做點線性變換，就可以化成好做的case了。於是我就在晚餐吃到一半開始跟他講怎麼做XD(對不起了好吃的somenya以及一起吃飯的他的另一個朋友)。

於是我跟Boris就久違的再次開始了一個project，感覺還蠻神奇的。之前在CMU後兩年覺得我們style很不合，所以沒有繼續合作，但實際上再次work就覺得還行，其實就只是匹茲堡這地方太糟糕，我沒有心力做些對我來說是支線任務的數學問題吧XD。感覺離開匹茲堡一切都好起來了。

———-數學時間———-

好啊，上面提到 $\ell$ 是質數的時候，我們知道答案一樣是最多 $n$ 個。實際上，如果 $\ell$ 是質數冪次的話一樣有這個結論，只是需要稍微仔細一點線代技巧，這個我們後面再一起證。

那當 $\ell=p_1^{\alpha_1}\dots p_{\omega}^{\alpha_\omega}$ 的時候怎麼辦呢？有個直接的bound是你考慮令 $\mathcal{A}_i$ 是那些人數mod $p_i^{\alpha_i}$ 不是 $0$ 的俱樂部所成的集合，那我們知道根據質數冪次的結論，會有 $|\mathcal{A}_i|\leq n$ ，所以總共至多有 $\omega n$ 個俱樂部。但so far人類知道的構造都不超過 $n$ 個QQ。

實際上，上界可以做得比 $\omega n$ 稍微再好一點。在我們的paper中，我們證明了

定理 1：若 $\ell$ 有至少兩個質因數，則我們會有上界 $\omega n-2\omega \log_2 n+11$ 。

定理 2：若 $\ell$ 有至少兩個奇質因數，且當 $n$ (相較於 $\ell$ )足夠大時，我們會有上界 $\omega n-(2\omega +\varepsilon)\log_2 n$ 。

我們先暫時不要管定理 1的 $+11$ ，這只是為了讓小數字也會對所加的常數。而定理 2裡面的 $\varepsilon$ 是個跟 $\ell$ 有關的正的量，但重點不是他的大小，而是他引申出來的問題，我們後面會稍微提到。

那我們就先來證定理 1吧！首先觀察到， $|\mathcal{A}_i|\leq n$ 這個界其實有點鬆，原因如下。令 $\mathcal{B}_i$ 為所有不在 $\mathcal{A}_i$ 裡的俱樂部所成的集合。那如果 $|\mathcal{A}_i|= n$ 的話，你會發現你沒辦法有任何俱樂部在 $\mathcal{B}_i$ 裡，所以 $\mathcal{A}_i$ 跟 $\mathcal{B}_i$ 的大小會有個trade-off。事實上呢，我們會有以下引理。

引理 1：令 $u_1,\dots,u_k,w_1,\dots,w_m$ 是一些 $\mathbb{Z}^n$ 中的向量，並令 $d$ 是 $w_1,\dots,w_m$ over $\mathbb{F}_p$ 的維度。假設

$u_i\cdot u_i\not\equiv 0\pmod{p^\alpha}$

$u_i\cdot u_j\equiv 0\pmod{p^\alpha}$ , if $i\neq j$

$w_i\cdot w_i\equiv 0\pmod{p^\alpha}$

$w_i\cdot w_j\equiv 0\pmod{p^\alpha}$ , if $i\neq j$

$u_i\cdot w_j\equiv 0\pmod{p^\alpha}$

則 $k+2d\leq n$ 。

先來直觀解釋一下這東西為什麼該對。我們先想像一下 $\alpha=1$ ，那 $u_1,\dots,u_k,w_1,\dots,w_m$ 跟 $w_1,\dots,w_m$ 互相垂直。前者維度是 $k+d$ ，後者想成線性條件有 $d$ 維，所以解應該是 $n-d$ 維。也就是說 $k+d\leq n-d$ 。

那我們實際上來證明吧！我們從 $w_1,\dots,w_m$ 裡選 $d$ 個over $\mathbb{F}_p$ 線性獨立的向量，不失一般性假設是 $w_1,\dots,w_d$ 。我們不失一般性假設 $w_1,\dots,w_d$ 投影到前 $d$ 個entries是線性獨立的，也就是說如果你把 $w_1,\dots,w_d$ 作為行向量排成一個矩陣，那前 $d$ 列是full rank的。

這樣的話在 $\mathbb{F}_p$ 中有一個線性變換把 $w_1,\dots,w_d$ 變成 $w'_1,\dots,w'_d$ 使得 $w'_1,\dots,w'_d$ 的前 $d$ 列是單位矩陣。我們可以把這些線性變換的係數以及 $w'_1,\dots,w'_d$ 視作整數以及整數向量，則 $w'_1,\dots,w'_d$ 的前 $d$ 列是個對角矩陣，且對角線上的值都不被 $p$ 整除。我們再把 $w'_1,\dots,w'_d$ 乘上個係數得到 $w^*_1,\dots,w^*_d$ ，使得這個對角上都mod $p^\alpha$ 餘 $1$ 。注意到把 $w_1,\dots,w_d$ 換成 $w^*_1,\dots,w^*_d$ 並不會改變引理中的那些性質。

再來我們clean up $u_1,\dots,u_k$ 。注意到我可以把 $u_i$ 換成 $u_i+cw^*_j$ 都不會改變引理中的性質，所以我們可以透過加上一些 $w^*_j$ 使得 $u_i$ 的前 $d$ 個entries都是 $0$ ，假設得到的是 $u^*_i$ 。

現在我們知道了 $u^*_1,\dots,u^*_k,w^*_1,\dots,w^*_d$ 的前 $d$ 個entries長怎樣了。令 $u^-_1,\dots,u^-_k,w^-_1,\dots,w^-_d$ 是扔掉了前 $d$ 個entries後的向量，則我們會有

$u^-_i\cdot u^-_i\not\equiv 0\pmod{p^\alpha}$

$u^-_i\cdot u^-_j\equiv 0\pmod{p^\alpha}$ , if $i\neq j$

$w^-_i\cdot w^-_i\equiv -1\pmod{p^\alpha}$

$w^-_i\cdot w^-_j\equiv 0\pmod{p^\alpha}$ , if $i\neq j$

$u^-_i\cdot w^-_j\equiv 0\pmod{p^\alpha}$

既然 $u^-_1,\dots,u^-_k,w^-_1,\dots,w^-_d$ 是 $n-d$ 維的整數向量，如果 $k+d>n-d$ 的話，則 $u^-_1,\dots,u^-_k,w^-_1,\dots,w^-_d$ 是over $\mathbb{Q}$ 線性相依的，也就是說有

$a_1u^-_1+\dots+a_ku^-_k=b_1w^-_1+\dots+b_dw^-_d$

且我們可以不失一般性假設 $a_1,\dots,a_k,b_1,\dots,b_d$ 都是整數且最大公因數是 $1$ 。把上式跟 $w^-_i$ 內積可以得到 $-b_i\equiv 0\pmod{p^\alpha}$ 。所以有

$a_1u^-_1+\dots+a_ku^-_k\equiv 0\pmod{p^\alpha}$

由於假設了最大公因數是 $1$ ，我們知道有某個 $a_i$ 跟 $p$ 互質。考慮把上式跟 $u^-_i$ 內積，得到 $a_iu^-_i\cdot u^-_i\equiv 0\pmod{p^\alpha}$ ，這跟 $u^-_i\cdot u^-_i\not\equiv 0\pmod{p^\alpha}$ 矛盾！

注意到，這個引理同時給出了上面提及的 $|\mathcal{A}_i|\leq n$ ：考慮令 $u^*_1,\dots,u^*_k$ 是 $\mathcal{A}_i$ 裡面俱樂部對應到的向量們，然後 $w$ 的部分就只取一個零向量。

有了這個引理之後，下個問題就是：我假設知道 $w_1,\dots,w_m$ 都是 $0$ – $1$ 向量，那 $d$ 可以多大。如果你考慮取 $d$ 個entries然後令 $w_1,\dots,w_m$ 是所有在這以外都是 $0$ ，在這 $d$ 個entries可以是 $0$ 或 $1$ 的向量，這樣 $d=\log_2 m$ 。而實際上這是我們可以做得最好的。

引理 2：令 $V\subseteq \mathbb{F}^n$ 是一個 $d$ 維的子空間，則 $|V\cap\{0,1\}^n|\leq 2^d$ 。

這個相對好證，你可以不失一般性假設 $V$ 投影到前 $d$ 個entries是full rank的，那 $V$ 裡面的向量 $d$ 個entries決定，所以至多 $2^d$ 個。

有了這兩個引理，我們就能來證定理 1了。為了省略一些technical details我會忽略計算。首先，我們知道總共俱樂部數量至多是 $|\mathcal{A}_i|+|\mathcal{B}_i|$ ，所以如果有一個 $i$ 使得 $|\mathcal{B}_i|\leq n$ 我們就做完了(除了 $\omega=2$ 的時候要把 $n$ 換成 $n/2$ 之類的，但我們先忽略這個小細節XD)，因為我們還知道 $|\mathcal{A}_i|<=n$ ，也就是總共至多 $2n$ 。

那當 $|\mathcal{B}_i|>n$ 的時候，由引理 1我們知道，假設 $d$ 是 $\mathcal{B}_i$ 對應的向量們over $\mathbb{F}_p$ 的rank，那 $|\mathcal{A}_i|+2d\leq n$ 。由引理 2我們還知道 $|\mathcal{B}_i|\leq 2^d$ 。所以有

$|\mathcal{A}_i|+2\log_2 |\mathcal{B}_i|\leq n$

配上 $|\mathcal{B}_i|>n$ ，我們知道 $|\mathcal{A}_i|\leq n-2\log_2 n$ 。由於總共的俱樂部數量也可以用 $\sum_i|\mathcal{A}_i|$ upper bound，所以至多有 $\omega n-2\omega\log_2 n$ 個。(常數的那個 $+11$ 來自一些上面忽略的edge case)

好啊，那我們要怎麼從 $2\omega\log_2 n$ 再多擠一點到 $(2\omega+\varepsilon)\log_2 n$ 呢？雖然引理2是緊的，但我們可以在那附近多擠出一點。首先，引理二有個等價敘述：

引理 2’：令 $M$ 是一個行向量不重複的 $0$ – $1$ 矩陣，假設 $d=\text{rank}_{\mathbb{F}}(M)$ ，則 $M$ 至多有 $2^d$ 列。

而在我們的問題中，我們(忽略一些technical details後，大約)可以得到一個 $|\mathcal{B}_i|$ by $n$ 的 $0$ – $1$ 矩陣 $M$ ，其中 $M$ 的行向量不重複，列向量也不重複。而問題是 $d=\text{rank}_{\mathbb{F}}(M)$ 能有多小，其中 $\mathbb{F}=\mathbb{F}_{p_i}$ 。

假設 $M$ 有 $r$ 列 $c$ 行的話，我們會有如下表格：

其中construction代表存在構造，trivial bound就是上述的引理 2’，這告訴我們說那以外的都不可能。而我們透過一些基礎的傅立葉變換加上一些組合引理可以得到斜線那塊也不可能，而這也幫我們從 $2\omega\log_2 n$ 多擠一點到 $(2\omega+\varepsilon)\log_2 n$ 。細節請參考paper XD

趙庭偉的blog

奇(ㄐㄧ)怪的小鎮

發表留言取消回覆

奇(ㄐㄧ)怪的小鎮

分享此文：

發表留言 取消回覆

發表留言取消回覆