Additive Combinatorics and Theoretical Computer Science (2009)

A Kakeya needle set.

Additive Combinatorics and Theoretical Computer Science Trevisan, SIGACT News 40

接續同篇文章上次的心得

Szemerédi Regularity Lemma 讓你可以用簡單一點的 model 去估計複雜的 graph 上的結果。Goldreich et al(1996)以檢驗任意 graph 是否內含三角形為例,給了一個複雜度為 O_ε(1) 的 property test 演算法。

Gower 在分析 Erdos-Turan 問題的時候提出了 Gower norms,一樣對於 property testing 是個強力的工具。Gower inverse conjecture 在 finite field 已經被證明。

Ergodic theory 的技巧在 Furstenberg 對 Erdos-Turan 問題的分析,以及 finite field Gower inverse conjecture 的證明裡都有出現。它可以讓你把有限的 quantitative(內含很多 ε δ 的)結果推廣到 infinitary 結果。

Finite field 的 sum-product 問題,一部份動機是為了解決分析裡的 Kakeya problem。對一個 group 的子集合 A,當 A+A 夠小的時候,對 A 的結構有所瞭解可以有助於分析 Kakeya problem。換成 finite field 的情況,Wolff(1999)提出了 finite field sum-product conjecture:對 F_p 的任何子集合 A|A+A||A*A| 其中一個至少是 min{p, |A|^{1+ε}}ε>0。Finite field Kakeya problem 被 Dvir(2008)證明。

文章最後列了 3 個 open problem:The cap problm in $F_3$、bounds in the traingle removal lemma、the polynomial Freiman-Rusza conjecture。

One clap, two clap, three clap, forty?

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