2007/10/16 by David J. Grynkiewicz, Grynkiewicz, David J., Oriol Serra +1
Computer Science · Mathematics · #11P70 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT) #math.CO #math.NT #msc:11P70
paper · pdf · doi:10.48550/arxiv.0710.3127
arxiv created 2007/10/16 · openalex publication_date 2007/10/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let A, B⊆ ℝ2 be finite, nonempty subsets, let s≥ 2 be an integer, and let h1(A,B) denote the minimal number t such that there exist 2t (not necessarily distinct) parallel lines, ℓ1,...,ℓt,ℓ'1,...,ℓ't, with A⊆ \bigcupi=1tℓi and B⊆\bigcupi=1tℓ'i. Suppose h1(A,B)≥ s. Then we show that: (a) if ||A|-|B||≤ s and |A|+|B|≥ 4s2-6s+3, then |A+B|≥ (2-\frac 1 s)(|A|+|B|)-2s+1; (b) if |A|≥ |B|+s and |B|≥ 2s2-7/2s+3/2, then |A+B|≥ |A|+(3-\frac 2 s)|B|-s; (c) if |A|≥ 1/2s(s-1)|B|+s and either |A|> 1/8(2s-1)2|B|-1/4(2s-1)+((s-1)2)/(2(|B|-2)) or |B|≥ (2s+4)/(3), then |A+B|≥ |A|+s(|B|-1). This extends the 2-dimensional case of the Freiman 2d--Theorem to distinct sets A and B, and, in the symmetric case A=B, improves the best prior known bound for |A|+|B| (due to Stanchescu, and which was cubic in s) to an exact value. As part of the proof, we give general lower bounds for two dimensional subsets that improve the 2-dimensional case of estimates of Green and Tao and of Gardner and Gronchi, and that generalize the 2-dimensional case of the Brunn-Minkowski Theorem.