{"entities":{"Q6056560":{"pageid":13190715,"ns":120,"title":"Item:Q6056560","lastrevid":55490353,"modified":"2026-02-17T17:34:23Z","type":"item","id":"Q6056560","labels":{"en":{"language":"en","value":"On the restricted sumsets containing powers of an integer"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7745027"}},"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":"Q6056560$1594119D-A1A4-455D-9578-F821BBC919E3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"97595d6bfe9806cf67901e4d6a4bcca1d9dd5f84","datavalue":{"value":{"text":"On the restricted sumsets containing powers of an integer","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6056560$58453117-3C1F-4B8F-A82E-2A57D6ADA120","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"795d39c019d77f3c9e27ce07e9abe48675bede13","datavalue":{"value":{"entity-type":"item","numeric-id":2162812,"id":"Q2162812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$8B2261BF-927E-4A85-B76F-4021F88547F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29faf7751cc3b3046253a216a3fb05d50299e3e5","datavalue":{"value":{"entity-type":"item","numeric-id":249586,"id":"Q249586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$736DAB50-D390-46DC-B2B0-1B038A017B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f635262fbfb883d44d913cfcd26089994e34ac55","datavalue":{"value":{"entity-type":"item","numeric-id":776304,"id":"Q776304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$CBBBD2B5-C069-4EA5-B5C1-DE3D5631DE37","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$3C3DE4F0-6F64-4126-B074-FB51E59911F8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e68dcb3ce5566cf2b4bd7c1def923cc7a3f373d5","datavalue":{"value":{"time":"+2023-10-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6056560$67F40CA4-1375-4012-B5C1-DBEEC0D77361","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"94540875fa80d27a16b9cc90a619039c044da989","datavalue":{"value":"Let $\\mathbb N$ be the set of positive integers, $[a,b] = \\{n \\in \\mathbb Z; a \\le n \\le b\\}$, and $\\gcd A$ be the greatest common factor of the elements of $A$. For $h \\ge 1$, define the $h$-fold sumset and the $h$-fold restricted sumset  \\[ hA = \\{a_1+\\dots+a_h; a_1, \\dots, a_h \\in A\\}, \\text{ and } h\\wedge A = \\{a_1+\\dots+a_h; a_1, \\dots, a_h \\in A, a_i \\neq a_j \\text{ if } i \\neq j\\}, \\] respectively. Let $A(n) = \\sum_{\\substack{1 \\le a \\le n\\\\a \\in A}} 1$. For $c \\in \\mathbb Z$, let $c-A = \\{c-a; a \\in A\\}$.  \\textit{P. Erd\u0151s} [in: Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9--20, 1986. New York: New York Academy of Sciences. 132--145 (1989; Zbl 0790.11015)] conjectured that if $n \\in \\mathbb N$ and $A \\subset [1,3n]$ with $|A| \\ge n+1$, then there is a power of $2$ that can be represented as the sum of distinct elements of $A$. Then \\textit{P. Erd\u0151s} and \\textit{G. Freiman} [J. Number Theory 34, No. 1, 1--12 (1990; Zbl 0697.10047)] proved that this conjecture holds for sufficiently large $n$, and they showed that there are at most $c \\log n$ pairwise distinct elements of $A$ the sum of which is a power of $2$, where $c > 0$ is absolute. At the same time, \\textit{M. B. Nathanson} and \\textit{A. S\u00e1rk\u00f6zy} [Acta Arith. 54, No. 2, 147--154 (1989; Zbl 0693.10040)] proved that at most $30,961$ distinct elements are needed.  After some improvements on such results (see [\\textit{M. B. Nathanson} and \\textit{A. S\u00e1rk\u00f6zy}, Acta Arith. 54, No. 2, 147--154 (1989; Zbl 0693.10040); \\textit{G. A. Freiman}, in: Sets, graphs and numbers. A birthday salute to Vera T. S\u00f3s and Andr\u00e1s Hajnal. Amsterdam: North-Holland Publishing Company. 279--286 (1992; Zbl 0796.11005); \\textit{V. F. Lev}, Combinatorica 16, No. 3, 413--416 (1996; Zbl 0862.11008); \\textit{V. F. Lev}, Acta Arith. 132, No. 3, 197--204 (2008; Zbl 1143.11010)]), \\textit{H. Pan} [J. Number Theory 117, No. 1, 216--221 (2006; Zbl 1101.11045)] showed that for any $\\varepsilon>0$ and any sufficiently large $n \\in \\mathbb N$, if $A \\subset [1,n]$ with $\\gcd A = 1$ and $|A| > \\varepsilon n$, then there are integers $x \\ge 0$ and $k = k(\\varepsilon) \\ge 1$ such that $2^x \\in kA$. The following question is naturally to be considered.  Problem 1.1. How dense can $A$ be if no power of $2$ can be represented as the sum of distinct elements of $A$?  The paper answer this question. For $r \\in \\mathbb N$, $r \\ge 2$, let  \\[ m(r) = \\min\\{w \\in \\mathbb N; rad(w) \\mid r \\text{ and }r\\text{ is not a primitive root of }w\\}, \\] where $rad(1)=1$ and $rad(w)$ is the product of all the distinct prime factors of $w$. It is easy to see that $m(r) \\ge 3$. For $r \\in \\mathbb N$, $r \\ge 2$, let $p$ be the least prime with $p \\nmid r$ and let  \\[ M(r) = \\{s \\in \\mathbb N; 1 < s < m(r) \\text{ and }r\\text{ is a primitive root of }s\\}. \\] Let  \\[ h(r) = \\begin{cases} r(m(r)-1) &\\text{ if }r\\text{ is not a primitive root of }p, \\\\ \\max\\{ 2\\lceil r(m(r)-1)/2 \\rceil, \\max_{s \\in M(r)} f_r(s)\\} &\\text{ if }r\\text{ is a primitive root of }p, \\end{cases} \\] where $f_r(s) = \\frac{1}{s}(r^{\\varphi(s)} - 1)m(r) + (r^{\\varphi(s)} + 1)\\lceil s^{-1}m(r) - 1 \\rceil + 1$, and $\\varphi(s)$ is the Euler's totient function.  For $A \\subset \\mathbb N$, if there is a power of $r$ that can be represented as the sum of distinct elements of $A$, then $rad(\\gcd A) \\mid r$. Let $A_1 \\subset A$ be the set of all elements which are the middle terms of at least $h(r)$ three-term arithmetic progressions in $A$. Let $|A| \\ge 2(h(r)-1)$. The main results of this paper are the following.  Theorem 1.2. Let $r \\in \\mathbb N$, $r \\ge 2$. For $n \\in \\mathbb N$ sufficiently large, if $A \\subset [1,n]$ with $rad(\\gcd A) \\mid r$ and $|A| > \\frac{n}{m(r)}$, $|A_1| \\ge \\frac{n}{m(r)\\gcd A}+1$, then there is a power of $r$ that can be represented as the sum of at most $h(r)$ distinct elements of $A$.  Theorem 1.3. Let $r \\in \\mathbb N$, $r \\ge 2$, and let $\\varepsilon > 0$ be real. For $n \\in \\mathbb N$ sufficiently large, if $A \\subset [1,n]$ with $rad(\\gcd A) \\mid r$ and $|A| > \\left( \\frac{1}{m(r)} + \\varepsilon \\right)n$, then there is a power of $r$ that can be represented as the sum of at most $h(r)$ distinct elements of $A$.  Theorem 1.4. Let $r \\in \\mathbb N$, $r \\ge 2$. Then for infinitely many positive integers $n$, there exists $B \\subset [1,n]$ with $\\gcd B = 1$ and $|B| > \\frac{n}{m(r)}$ such that no power of $r$ can be represented as the sum of distinct elements of $B$.  For an infinite set of positive integers, the authors obtained similar results (see Corollary 1.5).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6056560$F51CEEAE-D7D7-44F5-BBAE-86BCB7D60B1B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c7e53f9088504d44a25210cfb3a791cde0c1634c","datavalue":{"value":{"entity-type":"item","numeric-id":1686015,"id":"Q1686015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$0160B999-8BB2-4128-B2D1-501487EC3B78","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f966b0d08eaa36f862948c36979cac20cef1e7f7","datavalue":{"value":"11B13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6056560$D0101244-E946-475E-BBA9-423AEA74CC9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e468619e2b41b60fc13e0c6dbb8477811d53d177","datavalue":{"value":"7745027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6056560$8E79C54B-E373-4CAF-8EC7-FA0D3481A5C2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b66ce6c04fd76a681fb2cee846484d2f65dcb35","datavalue":{"value":"restricted sumsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q6056560$2E1F8EEA-0C86-4723-8947-DEF3971149E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ca9f3705eb956469debf81d65cae855b27b2ca5","datavalue":{"value":"powers of an integer","type":"string"},"datatype":"string"},"type":"statement","id":"Q6056560$A8D730F4-DB25-4864-A65F-4D4FD95134B0","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":"Q6056560$C44E4BD7-E3E0-4737-80D6-B65E490DCA18","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80daa448afbbce624e460ba1c98a9fd5a9489c95","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2023.103795","type":"string"},"datatype":"url"},"type":"statement","id":"Q6056560$5366157E-303A-4327-99B9-C3BC72649FC0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cffafc2bdf8bb40425be2bb59a4f82ce5e607e3f","datavalue":{"value":"W4386491306","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6056560$13920CCE-BF32-4620-B428-ED90994BC190","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a709aacde50765b66d9f60f8ee1fef0daa5c4f84","datavalue":{"value":{"entity-type":"item","numeric-id":4294585,"id":"Q4294585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$DD94F3EC-3AC6-4FC7-9157-66152F5FF925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27531504e42ecde1af84ca28d2124857871e1e0a","datavalue":{"value":{"entity-type":"item","numeric-id":911638,"id":"Q911638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$1418F376-7DF8-4616-BF60-E6C0887AC7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0305f86d26022b04cd981e8e5dfb3eebfb9d3d43","datavalue":{"value":{"entity-type":"item","numeric-id":3035395,"id":"Q3035395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$0DF4FC9D-F934-49A2-BAFA-4B40EDF023D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c03d3a103e4d9f03f42c656aeae4af893b82c16","datavalue":{"value":{"entity-type":"item","numeric-id":3137186,"id":"Q3137186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$CB1F638F-DA68-4E31-A541-415416145C68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a35708f2b9631c870bf768a45adb49946e79d41","datavalue":{"value":{"entity-type":"item","numeric-id":2563516,"id":"Q2563516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$ED31C6D7-6C4E-4800-94ED-4700983378BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f05df8c8e5d59696aa980473f01c344e57ca2d3d","datavalue":{"value":{"entity-type":"item","numeric-id":5387113,"id":"Q5387113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$0F55C057-1DA4-476B-B075-84996367A025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"438232bb6ae1abec04a87fbe1819f0e71b47616d","datavalue":{"value":{"entity-type":"item","numeric-id":1882138,"id":"Q1882138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$9BE7086B-94E7-4080-9C11-0C71DFCFF171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0966b2e468cc7cc5ca3efa26d64c23aff5cabe63","datavalue":{"value":{"entity-type":"item","numeric-id":1090706,"id":"Q1090706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$7197A03C-2A4C-4361-B20C-9F9E195C61C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a35ff6e1a64706c0f17c5e640aa49a14f457a4a1","datavalue":{"value":{"entity-type":"item","numeric-id":1914029,"id":"Q1914029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$8E0B5253-25AF-4A1F-8D10-D73E7538436C","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":"Q6056560$44352232-5317-467D-B8A4-EE2BF275AB7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aee538616b58d3e7664c0fb09b07a75109b7bfde","datavalue":{"value":{"entity-type":"item","numeric-id":3115768,"id":"Q3115768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$9D8FCEBA-4A69-4FFA-ADB8-DFE9ED0751BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d0b177b76a183baab9cc408c1e7a12bfef7a252","datavalue":{"value":{"entity-type":"item","numeric-id":4898759,"id":"Q4898759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$B455467B-6D79-4983-B52E-3E0B772CBB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cde4d0ae7d34f080a141a46b46ccbb41793a256","datavalue":{"value":{"entity-type":"item","numeric-id":2490155,"id":"Q2490155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$DEB17C3D-5DEE-4623-9963-BB300E11EF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac65b5b6de72f53d0401da135ceb018e3c6b3689","datavalue":{"value":{"entity-type":"item","numeric-id":3261450,"id":"Q3261450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6056560$A3E91146-B068-40A5-996D-90C6C93EC464","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a8482d5b3fb5bdbf4a2e8349b5e06449c8e42a4","datavalue":{"value":"10.1016/J.EJC.2023.103795","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6056560$1DA43546-272E-4FE7-9AE2-EE24EAA23B74","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf8d6f06074dce0e6336b1d87abbe007a9571cb4","datavalue":{"value":{"entity-type":"item","numeric-id":3137186,"id":"Q3137186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffff4ab420c720a1355d289d5928c29518b9fc5e","datavalue":{"value":{"amount":"+0.8671830892562866","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":"Q6056560$E061CDAD-4E44-4A27-8790-DC71DE81DEBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"572785b6d42798017ff96504d1fb5a93b3705160","datavalue":{"value":{"entity-type":"item","numeric-id":685699,"id":"Q685699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4605303502fd25321088ba17204689b2e154e5f","datavalue":{"value":{"amount":"+0.8597946166992188","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":"Q6056560$D238F326-3F4C-41DE-BC9B-2F9E95F5C3A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8df54515249279e6e79f2ccc5be0300649bf4056","datavalue":{"value":{"entity-type":"item","numeric-id":3032340,"id":"Q3032340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ec3265b2aa87e387583c191eccc2e1aa01a9c23","datavalue":{"value":{"amount":"+0.8565547466278076","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":"Q6056560$C1C69092-A6AC-4537-951A-5EC7EF616F93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d5ca9d9c59a014a4a2293a95572357cca950639","datavalue":{"value":{"entity-type":"item","numeric-id":2490155,"id":"Q2490155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb98d83df1b43f73861ea512590e8bc537267054","datavalue":{"value":{"amount":"+0.8412700891494751","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":"Q6056560$7EB5BD61-FA66-477A-B4F1-51727744DD52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93c8c2cf3a79d63d4c9d8aaa34af752f1b1dec23","datavalue":{"value":{"entity-type":"item","numeric-id":2569594,"id":"Q2569594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b253b1ea6b34bb7fd146e81818d25114cf29840","datavalue":{"value":{"amount":"+0.8170093297958374","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":"Q6056560$C8191C00-9B3B-49C8-B452-AC30E7F27103","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6056560","badges":[]}}}}}