{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:13:04Z","timestamp":1772518384287,"version":"3.50.1"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2009,5]]},"abstract":"Using various results from extremal set theory (interpreted in the language of additive combinatorics), we prove an asymptotically sharp version of Freiman's theorem in $\\F_2^n$<\/jats:alt-text><\/jats:inline-graphic>: if $A \\subseteq \\F_2^n$<\/jats:alt-text><\/jats:inline-graphic> is a set for which |A<\/jats:italic> + A<\/jats:italic>| \u2264 K<\/jats:italic>|A<\/jats:italic>| then A<\/jats:italic> is contained in a subspace of size $2^{2K + O(\\sqrt{K}\\log K)}|A|$<\/jats:alt-text><\/jats:inline-graphic>; except for the $O(\\sqrt{K} \\log K)$<\/jats:alt-text><\/jats:inline-graphic> error, this is best possible. If in addition we assume that A<\/jats:italic> is a downset, then we can also cover A<\/jats:italic> by O<\/jats:italic>(K<\/jats:italic>46<\/jats:sup>) translates of a coordinate subspace of size at most |A<\/jats:italic>|, thereby verifying the so-called polynomial Freiman\u2013Ruzsa conjecture in this case. A common theme in the arguments is the use of compression techniques. These have long been familiar in extremal set theory, but have been used only rarely in the additive combinatorics literature.<\/jats:p>","DOI":"10.1017\/s0963548309009821","type":"journal-article","created":{"date-parts":[[2009,3,30]],"date-time":"2009-03-30T18:31:21Z","timestamp":1238437881000},"page":"335-355","source":"Crossref","is-referenced-by-count":21,"title":["Freiman's Theorem in Finite Fields via Extremal Set Theory"],"prefix":"10.1017","volume":"18","author":[{"given":"BEN","family":"GREEN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TERENCE","family":"TAO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,5,1]]},"reference":[{"key":"S0963548309009821_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755149"},{"key":"S0963548309009821_ref13","first-page":"323","article-title":"An analog of Freiman's theorem in groups","volume":"258","author":"Ruzsa","year":"1999","journal-title":"Structure Theory of Set Addition, Ast\u00e9risque"},{"key":"S0963548309009821_ref10","unstructured":"[10] Green B. J. and Tao T. C. A note on the Freiman and Balog\u2013Szemer\u00e9di\u2013Gowers theorems in finite fields. Submitted; available at: http:\/\/www.arxiv.org\/abs\/math.CO\/0701585. To appear in J. Austral. Math. Soc."},{"key":"S0963548309009821_ref4","first-page":"81","volume-title":"London Mathematical Society Lecture Notes","author":"Frankl","year":"1987"},{"key":"S0963548309009821_ref16","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1307\/mmj\/1029002504","article-title":"Orthogonal pairings of Euclidean spaces","volume":"28","author":"Yuzvinsky","year":"1981","journal-title":"Michigan Math. J."},{"key":"S0963548309009821_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01876039"},{"key":"S0963548309009821_ref8","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609305018102"},{"key":"S0963548309009821_ref9","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdl021"},{"key":"S0963548309009821_ref1","first-page":"185","article-title":"Sur quelques propri\u00e9t\u00e9s arithm\u00e9tiques des presque-p\u00e9riodes","volume":"4","author":"Bogolyubov","year":"1939","journal-title":"Ann. Chaire Math. Phys. Kiev"},{"key":"S0963548309009821_ref11","first-page":"109","article-title":"Additive number theory sheds extra light on the Hopf\u2013Stiefel ^ function (English summary)","volume":"49","author":"Plagne","year":"2003","journal-title":"Enseign. Math."},{"key":"S0963548309009821_ref5","volume-title":"Foundations of a Structural Theory of Set Addition","author":"Freiman","year":"1973"},{"key":"S0963548309009821_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00303-2"},{"key":"S0963548309009821_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008644"},{"key":"S0963548309009821_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0004-0"},{"key":"S0963548309009821_ref7","first-page":"1","volume-title":"Surveys in Combinatorics","author":"Green","year":"2005"},{"key":"S0963548309009821_ref6","first-page":"1","article-title":"Structure theory of set addition","volume":"258","author":"Freiman","year":"1999","journal-title":"Ast\u00e9risque"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309009821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,6]],"date-time":"2019-04-06T19:36:57Z","timestamp":1554579417000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309009821\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["S0963548309009821"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309009821","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5]]}}}