{"entities":{"Q944315":{"pageid":946163,"ns":120,"title":"Item:Q944315","lastrevid":65566887,"modified":"2026-04-12T03:29:29Z","type":"item","id":"Q944315","labels":{"en":{"language":"en","value":"John-type theorems for generalized arithmetic progressions and iterated sumsets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5344305"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$3CFD2071-D75B-437F-9F9F-E5EB8D3E6E0A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8c5b91fe69cff8d27cf538e7e53b417f45e6f4be","datavalue":{"value":{"text":"John-type theorems for generalized arithmetic progressions and iterated sumsets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q944315$7F7C50CA-79AE-42D1-AAA5-601A8B391355","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e80601c89ba0f438297a4fa684bec8fd83142889","datavalue":{"value":"1165.11016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944315$EFC7D539-A797-49BC-9F0B-3A0CE5A5A42F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa0a0fd6d39713c055b1389b556244194d49e99e","datavalue":{"value":{"entity-type":"item","numeric-id":934227,"id":"Q934227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$65D21D44-79A4-4A08-B4B6-30E5E00C9FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ac20003147c5e8ffc37ced247b8446bd4defdc1","datavalue":{"value":{"entity-type":"item","numeric-id":178484,"id":"Q178484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$4443EF85-C452-47E1-8D76-8FD70FC88C71","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"87fedd43d9515b94c7651de65777aba7be17422f","datavalue":{"value":{"entity-type":"item","numeric-id":165833,"id":"Q165833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$3DC1FED3-BCF7-4432-995F-D7A8377F1C8D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae960b13deac5afb5a738e4b316ea7d581125be5","datavalue":{"value":{"time":"+2008-09-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q944315$30FAD35C-86EB-4C1A-A936-8E48D169512C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d762a3b2568ef45d1d05451bdefda7ef9704e619","datavalue":{"value":"https://arxiv.org/abs/math/0701005","type":"string"},"datatype":"url"},"type":"statement","id":"Q944315$53B3925A-F0F2-4EBB-A320-8719264DB0DB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3b96067d74efc34fe8922d51b035efc864744297","datavalue":{"value":"A classical theorem of [\\textit{F. John}, Extremum problems with inequalities as subsidiary conditions, Studies Essays, pres. to R. Courant, 187--204 (1948; Zbl 0034.10503)] states that for any symmetric convex body \\(B\\) in \\(\\mathbb{R}^d\\), there exists an ellipsoid \\(E\\) centered at the origin such that \\(E \\subseteq B \\subseteq \\sqrt{d} \\cdot E\\). This rather technical yet elementary paper establishes various discrete analogues of John's theorem. It constitutes a valuable resource for anyone in need of precise quantitative statements about containment properties of generalized arithmetic progressions.  The first fundamental result is a John-type theorem for lattices, a proof of which can also be found in [\\textit{T. Tao} and \\textit{V. Vu}, Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105. Cambridge: Cambridge University Press (2006; Zbl 1127.11002)]. For the convenience of the reader we shall state it (and the remaining results of this paper) in a simplified form.  Let \\(B\\) be a convex symmetric body and \\(\\Gamma\\) be a lattice in \\(\\mathbb{R}^d\\). Then there exists a symmetric infinitely proper generalized arithmetic progression (GAP) \\(P\\) of rank at most \\(d\\) in \\(\\Gamma\\), with the property that  \\[ (O(d)^{-3d/2} \\cdot B) \\cap \\Gamma \\subseteq \\text{Im}(P) \\subseteq B \\cap \\Gamma \\subseteq \\text{Im}(P_{O(d)^{3d/2}}), \\]  where Im stands for the image of the GAP and \\(P_t\\) for the \\(t\\)-dilate of \\(P\\). A GAP is called \\(t\\)-proper if its dilate \\(P_t\\) is proper (that is, all its elements are distinct), and infinitely proper if it is \\(t\\)-proper for all \\(t\\).  As a corollary the authors obtain in the torsion-free case a John-type theorem for GAPs, which states that given a symmetric GAP of rank \\(d\\) in a torsion-free group \\(G\\), there exists a \\(t\\)-proper symmetric GAP \\(Q\\) of rank at most \\(d\\) such that  \\[ \\text{Im}(Q) \\subseteq \\text{Im}(P) \\subseteq \\text{Im}(Q_{O(d)^{3d/2}t}). \\]  Essentially the same result is obtained in the torsion case with GAPs replaced by so-called coset progressions, a concept that originated in the work of [\\textit{B. J. Green} and \\textit{I. Ruzsa}, J. Lond. Math. Soc. 75, No. 1, 163--175 (2007; Zbl 1133.11058)].  The above proof techniques are then combined with Freiman-type results by Green and Ruzsa to strengthen a recent result by \\textit{E. Szemer\u00e9di} and \\textit{V. Vu} [J. Am. Math. Soc. 19, No. 1, 119--169 (2006; Zbl 1088.11012)], which can be interpreted as a John-type theorem for iterated sumsets:  Let \\(A \\subseteq G\\) be a finite subset such that \\(|lA| \\leq c(d) l^d|A|\\) for some explicitly specified constant \\(c(d)\\) depending on \\(d\\). Then there exists a proper symmetric coset progression \\(Q\\) of rank \\(d'\\leq d-1\\) and size at least \\(c(d)l^{d'}|A|\\) together with \\(x,y \\in G\\) such that  \\[ x+\\text{Im}(Q) \\subseteq lA \\subseteq y+c(d)^{-1} \\text{Im}(Q). \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q944315$0839248E-06D2-4CAA-A3E0-15E6950CB1CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0db3c4a650faecc1fde3c6831e7a4c85caf06f6e","datavalue":{"value":{"entity-type":"item","numeric-id":607843,"id":"Q607843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$06C2E48F-9E33-4355-B5D1-B0DEDE7C0955","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"59ff1173f55ceccb7042119df1cda673726c7815","datavalue":{"value":"11B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944315$05165813-8434-4EC6-B1B0-C5F50CF33A14","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2bc31ade4d308d32ee245c149f3eef9f0f9052e3","datavalue":{"value":"5344305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944315$3A2CEAD9-43F4-4437-A5E2-19257096590F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1a286173921c785e5a1491fd3cdf4e3ceb551de","datavalue":{"value":"John theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q944315$33AEBD11-6095-4ACE-9301-6C59E7C3876B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76dd9197ddbd5acf06a96230194b74b9b5ab276d","datavalue":{"value":"sumsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q944315$7908AF36-A85B-4548-AAD7-66A8C468B17B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eabc875f2c47bf76e76caa841b51c7eb04a365f9","datavalue":{"value":"generalized arithmetic progressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q944315$0038E369-89A2-4D28-A485-12DBB519B5A4","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$70D1C481-53E3-4243-BB3D-F2EDE9F2C65D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1c9f285dc81280d44dd1f0dbd8791cfc1f42b0b4","datavalue":{"value":"W2011552750","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944315$861D6E93-6EB1-4B50-A500-9C71AD60796E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fcfb5268ea01c31e62ef508f1080fc0d6a7be51","datavalue":{"value":{"entity-type":"item","numeric-id":2366288,"id":"Q2366288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$0AFAB17A-DE3E-445C-BA0F-033254770DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c01e524c0be693f15311834bdb0f294fbf4b2bb3","datavalue":{"value":{"entity-type":"item","numeric-id":4256473,"id":"Q4256473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$A8317AEF-9EF6-45A6-8169-76E65B77575D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"486d8cef7f0092197d1f83b5042b5aa56754f4ee","datavalue":{"value":{"entity-type":"item","numeric-id":3202166,"id":"Q3202166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$1A2B11EC-9439-4B89-AEA7-A492F78EA372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8bd2486fd63df7fa2abc5d75cb72f78c1ffba06","datavalue":{"value":{"entity-type":"item","numeric-id":1847934,"id":"Q1847934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$E099829D-5C55-4C9D-BF60-5D4A282504C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7593f33a91663bad5cb64893ce72a6ac97f2dcca","datavalue":{"value":{"entity-type":"item","numeric-id":685677,"id":"Q685677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$BC014C0F-DCCE-4110-9AE7-EEC17CA2A507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08780ebfeffb5808b58f5d09ecc9528afc1291f8","datavalue":{"value":{"entity-type":"item","numeric-id":4024922,"id":"Q4024922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$E947F495-0318-4FA1-BA52-2E966CA13160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e073502687e61e37f42cb5d7deb96331d66bdcbb","datavalue":{"value":{"entity-type":"item","numeric-id":1847946,"id":"Q1847946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$A4F217AF-A2F9-43A6-AD7E-173735C2BF9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e08649f2d12a42a44ee291eb7ebcae8b26b225c","datavalue":{"value":{"entity-type":"item","numeric-id":5297567,"id":"Q5297567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$C9A6CA22-6389-4BB4-BD31-C7496630E007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ff02751caf2c1d49caa12d60a48ee3988c586ea","datavalue":{"value":{"entity-type":"item","numeric-id":5791470,"id":"Q5791470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$B1EB2FE7-30A1-4138-86CD-46F708EE6F01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57fda35771501bcf36a6f0fffdb384b7fa832e6d","datavalue":{"value":{"entity-type":"item","numeric-id":676285,"id":"Q676285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$C69FA276-AA5B-4475-8FB7-EEB0EDD570CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdb82bd83dbe1b3f4595d2d1faff685b06dfc3e9","datavalue":{"value":{"entity-type":"item","numeric-id":1576306,"id":"Q1576306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$4A461C14-1EEC-481A-B373-37395CCC3D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3382f67afdedc3d633959c11188ace835374c430","datavalue":{"value":{"entity-type":"item","numeric-id":558129,"id":"Q558129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$E8765DAA-03CB-405D-9C04-7B64BC605C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad0af965834672b7a4457e733039f937e00d0d64","datavalue":{"value":{"entity-type":"item","numeric-id":4871768,"id":"Q4871768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$6D07788A-C2C5-437C-8C04-CA7F131D8A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07f38df6ee5e2fb0928432d25ead6e7174008f54","datavalue":{"value":{"entity-type":"item","numeric-id":1121319,"id":"Q1121319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$519A99A2-BC10-4B8A-AAAC-9E4010808488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d55419bd1c094cce650aa748417d4640b65fa32","datavalue":{"value":{"entity-type":"item","numeric-id":5695776,"id":"Q5695776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$B25B11FC-74BE-4169-A4DD-DDF059E14D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c451ebd49df7a4cce39c10d200808e69ab4811a8","datavalue":{"value":{"entity-type":"item","numeric-id":5393666,"id":"Q5393666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944315$ECF46119-5F59-4917-80CB-3C6907164C4A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5779be2f1d82962beddfe46dcfc6fa6af4fd8de5","datavalue":{"value":"10.1016/J.AIM.2008.05.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944315$2785934C-B7D4-419E-82CB-EF9F57896326","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50da96d9346e05d846de26be99081c47ad1e1933","datavalue":{"value":{"entity-type":"item","numeric-id":2332797,"id":"Q2332797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"556b385695ece1185d8783a604dbc4816eb00b77","datavalue":{"value":{"amount":"+0.8291661739349365","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944315$6720B3D2-5186-4692-AB6B-55E4848E13AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8896b60917e89144f216b9d79f699921b2e0f80","datavalue":{"value":{"entity-type":"item","numeric-id":1333044,"id":"Q1333044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30b609822868f04dc5bff096e77fbfc6710509cf","datavalue":{"value":{"amount":"+0.7654806971549988","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944315$E59ED6B4-F5C8-4808-A684-8252EB75DB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"240d599996fcde06fb9a073ef8ddb9934b47b9a7","datavalue":{"value":{"entity-type":"item","numeric-id":4021762,"id":"Q4021762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51de11066fe02e9b29f43af51a2ddd85d2edc3c5","datavalue":{"value":{"amount":"+0.7623218297958374","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944315$EFAEF541-B072-4F7C-895C-5FB3DAFA53E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62498d59c6f55c1a2221832dc052f6b258f2ecde","datavalue":{"value":{"entity-type":"item","numeric-id":5297567,"id":"Q5297567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa455a0b116e2e9d4a04b10ed441c3600fe23e79","datavalue":{"value":{"amount":"+0.7181116342544556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944315$71469A6E-F6C9-4E29-A58B-2FD3366EC410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a0230c4a9c7f80709b524ea1e68408e707f5d36","datavalue":{"value":{"entity-type":"item","numeric-id":541154,"id":"Q541154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"934bac8118c66b5e4fa8153ebacd7a66fb1e13bc","datavalue":{"value":{"amount":"+0.7177845239639282","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944315$3DA635A1-1903-468B-8669-40E21C4229E5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"John-type theorems for generalized arithmetic progressions and iterated sumsets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/John-type_theorems_for_generalized_arithmetic_progressions_and_iterated_sumsets"}}}}}