Loading...
Please wait, while we are loading the content...
On Sums of Generating Sets in ℤ2n
| Content Provider | Scilit |
|---|---|
| Author | Even-Zohar, Chaim |
| Copyright Year | 2012 |
| Description | LetAandBbe two affinely generating sets of ℤ_{2}$^{n}$. As usual, we denote their Minkowski sum byA+B. How small canA+Bbe, given the cardinalities of A andB? We give a tight answer to this question. Our bound is attained when bothAandBare unions of cosets of a certain subgroup of ℤ_{2}$^{n}$. These cosets are arranged as Hamming balls, the smaller of which has radius 1.By similar methods, we re-prove the Freiman–Ruzsa theorem in ℤ_{2}$^{n}$, with an optimal upper bound. Denote byF(K)the maximal spanning constant |〈A〉|/|A| over all subsetsA⊆ ℤ_{2}$^{n}$with doubling constant |A+A|/|A| ≤K. We explicitly calculateF(K), and in particular show that $4^{K}$/4K≤F(K)⋅(1+o(1)) ≤ $4^{K}$/2K. This improves the estimateF(K)= $poly(K)4^{K}$, found recently by Green and Tao [17] and by Konyagin [23]. |
| Related Links | http://arxiv.org/pdf/1108.4902 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/A3DA225ED7928BD6A5DE3D52BB7A7E29/S0963548312000351a.pdf/div-class-title-on-sums-of-generating-sets-in-span-class-sub-2-span-span-class-sup-span-class-italic-n-span-span-div.pdf |
| Ending Page | 941 |
| Page Count | 26 |
| Starting Page | 916 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548312000351 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 6 |
| Volume Number | 21 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2012-08-03 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Minkowski Sum Upper Bound Number Theory |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
