{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:29:07Z","timestamp":1759336147082},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T00:00:00Z","timestamp":1708473600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,7]]},"abstract":"Abstract<\/jats:title>For a subset \n$A$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of an abelian group \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, given its size \n$|A|$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, its doubling \n$\\kappa =|A+A|\/|A|$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and a parameter \n$s$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> which is small compared to \n$|A|$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we study the size of the largest sumset \n$A+A'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> that can be guaranteed for a subset \n$A'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of \n$A$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of size at most \n$s$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We show that a subset \n$A'\\subseteq A$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of size at most \n$s$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> can be found so that \n$|A+A'| = \\Omega (\\!\\min\\! (\\kappa ^{1\/3},s)|A|)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Thus, a sumset significantly larger than the Cauchy\u2013Davenport bound can be guaranteed by a bounded size subset assuming that the doubling \n$\\kappa$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is large. Building up on the same ideas, we resolve a conjecture of Bollob\u00e1s, Leader and Tiba that for subsets \n$A,B$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of \n$\\mathbb{F}_p$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of size at most \n$\\alpha p$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for an appropriate constant \n$\\alpha \\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, one only needs three elements \n$b_1,b_2,b_3\\in B$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to guarantee \n$|A+\\{b_1,b_2,b_3\\}|\\ge |A|+|B|-1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Allowing the use of larger subsets \n$A'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we show that for sets \n$A$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of bounded doubling, one only needs a subset \n$A'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with \n$o(|A|)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> elements to guarantee that \n$A+A'=A+A$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also address another conjecture and a question raised by Bollob\u00e1s, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.<\/jats:p>","DOI":"10.1017\/s0963548324000014","type":"journal-article","created":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T08:13:03Z","timestamp":1708503183000},"page":"411-431","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Small subsets with large sumset: Beyond the Cauchy\u2013Davenport bound"],"prefix":"10.1017","volume":"33","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[]},{"given":"Sammy","family":"Luo","sequence":"additional","affiliation":[]},{"given":"Huy Tuan","family":"Pham","sequence":"additional","affiliation":[]},{"given":"Yunkun","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,2,21]]},"reference":[{"key":"S0963548324000014_ref3","first-page":"77","article-title":"Structure of sets with small sumset","volume":"258","author":"Bilu","year":"1999","journal-title":"Ast\u00e9risque"},{"key":"S0963548324000014_ref18","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/978-0-387-68361-4_9","volume-title":"Additive Number Theory: Festschrift in Honor of the Sixtieth Birthday of Melvyn B. Nathanson","author":"Green","year":"2010"},{"key":"S0963548324000014_ref7","unstructured":"[7] Cauchy, A. Recherches sur les nombres, J. \u00c9cole Polytechnique 9 (1813), 99-116. Also de Cauchy, A.L., Recherches sur les nombres, \u0152uvres (2nd series, Paris, 1882), Vol. 1, pp. 39\u201363."},{"key":"S0963548324000014_ref17","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1093\/qmath\/hal009","article-title":"Compressions, convex geometry and the Freiman\u2013Bilu theorem","volume":"57","author":"Green","year":"2006","journal-title":"Q. J. Math"},{"key":"S0963548324000014_ref1","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01212974","article-title":"A statistical theorem of set addition","volume":"14","author":"Balog","year":"1994","journal-title":"Combinatorica"},{"key":"S0963548324000014_ref28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511755149","volume-title":"Additive combinatorics. Cambridge Stud. Adv. Math. 105","author":"Tao","year":"2006"},{"key":"S0963548324000014_ref5","unstructured":"[5] Bollob\u00e1s, B. , Leader, I. and Tiba, M. Large sumsets from small subsets, preprint, arXiv: 2204.07559."},{"key":"S0963548324000014_ref24","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3845-2","volume-title":"Additive Number Theory: Inverse problems and the geometry of sumsets","author":"Nathanson","year":"1996"},{"key":"S0963548324000014_ref12","doi-asserted-by":"crossref","first-page":"561","DOI":"10.4007\/annals.2011.174.1.17","article-title":"A new proof of the graph removal lemma","volume":"174","author":"Fox","year":"2011","journal-title":"Ann. Math."},{"key":"S0963548324000014_ref20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-00416-7","volume-title":"Structural additive theory","author":"Grynkiewicz","year":"2013"},{"key":"S0963548324000014_ref26","doi-asserted-by":"crossref","DOI":"10.19086\/da.3733","article-title":"Proof of a conjecture of Kleinberg-Sawin-Speyer","author":"Pebody","year":"2018","journal-title":"Discrete Anal."},{"key":"S0963548324000014_ref23","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.jcta.2008.12.003","article-title":"A combinatorial proof of the removal lemma for groups","volume":"116","author":"Kr\u00e1l\u2019","year":"2009","journal-title":"J. Combin. Theory, Ser. A"},{"key":"S0963548324000014_ref27","first-page":"97","article-title":"An application of graph theory to additive number theory","volume":"3","author":"Ruzsa","year":"1989","journal-title":"Scientia, Ser. A"},{"key":"S0963548324000014_ref16","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1112\/jlms\/jdl021","article-title":"Freiman\u2019s theorem in an arbitrary abelian group","volume":"75","author":"Green","year":"2007","journal-title":"J. Lond. Math. Soc."},{"key":"S0963548324000014_ref29","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1112\/jlms\/s1-31.2.200","article-title":"The critical pairs of subsets of a group of prime order","volume":"31","author":"Vosper","year":"1956","journal-title":"J. Lond. Math. Soc."},{"key":"S0963548324000014_ref22","doi-asserted-by":"crossref","DOI":"10.19086\/da.3734","article-title":"The growth rate of tri-colored sum-free sets","author":"Kleinberg","year":"2018","journal-title":"Discrete Anal."},{"key":"S0963548324000014_ref14","unstructured":"[14] Freiman, G. A. Foundations of a structural theory of set addition (in Russian), Kazan, 1959; English Translation: Translation of Mathematical Monographs 37, Amer. Math. Soc., Providence, 1973."},{"key":"S0963548324000014_ref8","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1112\/jlms\/s1-10.37.30","article-title":"On the addition of residue classes","volume":"10","author":"Davenport","year":"1935","journal-title":"J. Lond. Math. Soc."},{"key":"S0963548324000014_ref6","unstructured":"[6] Bollob\u00e1s, B. , Leader, I. and Tiba, M. Large sumsets from medium-sized subsets, preprint, arXiv: 2206.09366."},{"key":"S0963548324000014_ref4","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/PL00009351","article-title":"Rectification principles in additive number theory","volume":"19","author":"Bilu","year":"1998","journal-title":"Discrete Comput. Geom."},{"key":"S0963548324000014_ref15","first-page":"109","volume-title":"Number Theory, New York 1984\u20131985, Lecture Notes in Math. 1240","author":"Freiman","year":"1987"},{"key":"S0963548324000014_ref19","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/s00039-001-0332-9","article-title":"A new proof of Szemer\u00e9di\u2019s theorem","volume":"11","author":"Gowers","year":"2001","journal-title":"Geom. Funct. Anal."},{"key":"S0963548324000014_ref10","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s11856-011-0061-1","article-title":"An improved construction of progression-free sets","volume":"184","author":"Elkin","year":"2011","journal-title":"Israel J. Math."},{"key":"S0963548324000014_ref25","doi-asserted-by":"crossref","first-page":"e46","DOI":"10.1017\/fms.2019.47","article-title":"A distribution on triples with maximum entropy marginal","volume":"7","author":"Norin","year":"2019","journal-title":"Forum Math. Sigma"},{"key":"S0963548324000014_ref2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1073\/pnas.32.12.331","article-title":"On sets of integers which contain no three terms in arithmetical progression","volume":"32","author":"Behrend","year":"1946","journal-title":"Proc. Natl. Acad. Sci. U. S. A."},{"key":"S0963548324000014_ref9","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1112\/jlms\/s1-22.2.100","article-title":"A historical note","volume":"22","author":"Davenport","year":"1947","journal-title":"J. Lond. Math. Soc."},{"key":"S0963548324000014_ref21","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0021-9800(66)80059-5","article-title":"Optimal numberings and isoperimetric problems on graphs","volume":"1","author":"Harper","year":"1966","journal-title":"J. Comb. Theory"},{"key":"S0963548324000014_ref11","article-title":"Sumsets as unions of sumsets of subsets","author":"Ellenberg","year":"2017","journal-title":"Discrete Anal."},{"key":"S0963548324000014_ref13","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/j.aim.2017.09.037","article-title":"A tight bound for Green\u2019s arithmetic triangle removal lemma in vector spaces","volume":"321","author":"Fox","year":"2017","journal-title":"Adv. Math."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T16:08:27Z","timestamp":1728403707000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000014\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,21]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["S0963548324000014"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000014","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,2,21]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}