On sumsets in \Bbb F₂ⁿ

2012/05/26 by Chaohua Jia, Jia, Chaohua
Computer Science · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT) #math.CO #math.NT

paper · pdf · doi:10.48550/arxiv.1205.5912

arxiv created 2012/05/26 · openalex publication_date 2012/05/26 · arxiv updated 2012/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let \Bbb F₂ be the finite field of two elements, \Bbb F₂ⁿ be the vector space of dimension n over \Bbb F₂. For sets A, B⊆\Bbb F₂ⁿ, their sumset is defined as the set of all pairwise sums a+b with a∈ A, b∈ B. Ben Green and Terence Tao proved that, let K≥ 1, ifA, B⊆\Bbb F₂ⁿ and |A+B|≤ K|A|^{1\over 2}|B|^{1\over 2}, then there exists a subspace H⊆\Bbb F₂ⁿ with |H|≫exp(-O(√(K)log K))|A| and x, y∈\Bbb F₂ⁿ such that |A∩(x+H)|^{1\over 2}|B∩(y+H)|^{1\over 2}≥1\over 2K|H|. In this note, we shall use the method of Green and Tao with some modification to prove that if |H|≫exp(-O(√(K)))|A|, then the above conclusion still holds true.

Related

• Sumsets in the Hypercube
• Properties of two dimensional sets with small sumset
• Ubiquity of simplices in subsets of vector spaces over finite fields
• A Second Wave of Expanders over Finite Fields
• On restricted sumsets over a field