Counting Sumsets and Applications

on YouTube ↗49m

" summary

Count of A ⊂ [N] with |A| = k and |A+A| ≤ Kk is log‑asymptotically given by the product (Kk/2 choose k) · N^K, with the progression construction dominating when k ≳ log N and the N^K embeddings dominating when k = o(log N). Tools include the Ruzsa model lemma embedding into Z/qZ, a regularity on Z/qZ with double‑exponential bounds, Cauchy–Davenport to bound block count. Applications: random Cayley sum graphs have clique number (2+o(1)) log_2 N while F2^n gives ≈ log N · log log N, and P(A+A misses K) = 2^{-K/2+o(1)} for random A ⊂ N.

AI-written summary · about

" chapters (11)

1. 0:00The problem of counting sets
2. 1:34Range of sumset sizes
3. 3:00Constructions for small sumsets
4. 8:51The main theorem on counting sets
5. 11:49Application: Ramsey graphs
6. 15:48Clique number theorems
7. 18:54Quadratic residue graphs
8. 24:19Connecting sumsets to graphs
9. 28:56Application: Random subsets
10. 30:52Methods for counting sets
11. 44:00Questions and discussion