Sumset and Inverse Sumset Theory for Shannon Entropy (2009)

Sumset and Inverse Sumset Theory for Shannon Entropy Tao, Comb. Prob. Comb. 2010.

Shannon entropy of a coin flip.

如果 (G, +) 是交換群,sumset theory 考慮的是在 G 裡取兩個有限子集合 AB,問 A+BA-BkA 這些集合有多大。反過來說 inverse sumset theory 考慮的是如果要求 A+A 不能太大,那麼對於 A 會有什麼要求。這篇論文討論的不是 G 的有限子集合,而是離散隨機變數 X 但取值在 G,對應於集合大小 |A| 則是 Shannon entropy H(X),考慮與 sumset theory 相對應的結果。

G 是交換群,XYZ 是取值在 G 的隨機變數。對應於 Sumset theory 的主要結果如下:

* dist_R(X,Z)≤dist_R(X,Y) + dist_R(Y,Z)
* dist_R(X,-Y)≤3dist_R(X,Y)
* H(X1 + … + Xn-X1' -… -Xm’) ≤H(X)+O((n+m)log σ[X])

對應於 inverse sumset theory 的結果:

  1. σ[X]=1 若且唯若 X 是取值在 G 的某個有限子群的 translation 上的 uniform distribution。
  2. 如果 σ[X]≤K,那會存在 coset progression H+P,rand O_K(1),讓 dist_{tr}(X, U)<< 1,其中 UH+P 上的 uniform distribution。
  3. 如果 dist_R(X, Y)≤K,那 dist_{tr}(X, Y)<<_K 1 而且 σ[X]≤K⁴

如果 G 是 torsion-free,那麼 σ[A]≥1 這個下界可以取的更好,變成 |A+A|≥2|A|-1σ[A]≥2–1/|A|。如果 A={1,2,…,n-1} 就會剛好碰到這個下界。這個結果不大能對應到 entropy 上。論文有討論一下反例。

以下都是 sumset theory 與上述主要結果相對應的定義與結果。定義 A+B={a+b: a in A, b in B}A-B={a-b: a in A, b in B}2A=A+A3A=A+A+A,依此類推。|A|A 的 cardinality。最基本的上下界是 |A|, |B|≤|A+B|≤|A||B|。定義 doubling constant σ[A]|A+A|/|A|σ[A$ 至少是 1。當然如果 A 剛好是個子群那就 σ[A]=1。事實上只要 A 是某個子群的 translation 就會有 σ[A]=1。那麼是不是只要 σ[A] 是有限的,A 就差不多像是有限子群的 translation 一樣?得到這樣的結果是 sumset theory 的主要目標。我們還想知道那些 σ[A] 夠小的A 是什麼樣子(classification problem),而這是 inverse sumset theory 的目標。這方面的基本結果有:

  1. Ruzsa triangle inequality,當 ABC 不是空集合,而且有限的時候,|A-C|≤(|A-B||B-C|)/|B|
  2. |A+B|≤(|A-B|³)/|A||B|
  3. 如果 σ[A]≤K,會有 |nA-mA|≤K^{n+m}|A|

還有 Balog-Szemerédi-Gowers lemma。如果 EA * B 的子集合,那麼定義 partially sumset A +^E B={a+b: (a, b) in E}。Lemma 是說,如果有 K≥1|E|≥|A||B|/K 而且 |A +^E B|≤K|A|^{1/2}|B|^{1/2},那麼可以取得 A’ in AB’ in B|A’|>>|A|/K|B’|>>|B|/K,讓 |A’+B’|<<K⁷|A’|^{1/2}|B’|^{1/2}

Inverse sumset theory。Coset progression 是指任何長得像 H+P 的子集合,其中 HG 的有限子群,P={x+n1r1+…+ndrd: 0≤n1<N1, …, 0≤nd<Nd}x 與所有 riG 的元素,Ni 是正整數(P 稱為 generalised arithmetic progression)。d 稱為這個 progression 的 rank。

Green-Ruzsa Freiman 定理。如果 A 是有限子群,σ[A]≤KK≥1,那麼 A 會包含在某個 coset progression H+P 之中,其 rank 為 O(K),而且 |H+P|≤exp(O(K^{O(1)}))|A|

考慮 Shannon entropy H(X)X 是取值在 G 的離散隨機變數的時候,一樣有 H(A), H(B)≤H(X+Y)H(X+Y)≤H(X)+H(Y)(這個要 XY 獨立才行)。

X 定義 doubling constant σ[X]=exp(H(X1+X2)-H(X)),一樣 X1X2X 的兩個獨立 copy。Partial sumset A +^E B 在這裡對應到 XY 不是獨立變數的情況。這裡有幾種方式可以定義 XY 的「距離」:total variation distance、Rusza distance、transport distance。這部份還沒看完。

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.