SUM-FREE SETS OF INTEGERS WITH A FORBIDDEN SUM

被引:0
作者
Haviv, Ishay [1 ]
机构
[1] Acad Coll Tel Aviv Yaffo, Sch Comp Sci, IL-61083 Tel Aviv, Israel
关键词
additive combinatorics; sum-free sets; forbidden sum; INDEPENDENT SETS; NUMBER; LEMMA;
D O I
10.1137/17M1157532
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A set of integers is sum-free if it contains no solution to the equation x + y = z. We study sum-free subsets of the set of integers [n] = {1,...n} for which the integer 2n + 1 cannot be represented as a sum of their elements. We prove a bound of O(2(n/3)) on the number of these sets, which matches, up to a multiplicative constant, the lower bound obtained by considering all subsets of B-n = {inverted right perperndicular2/3 (n + 1)inverted left perpendicular,..., n}. A main ingredient in the proof is a stability theorem saying that if a subset of [n] of size close to vertical bar B-n vertical bar contains only a few subsets that contradict the sum-freeness or the forbidden sum, then it is almost contained in B-n. Our results are motivated by the question of counting symmetric complete sum-free subsets of cyclic groups of prime order. The proofs involve Freiman's 3k - 4 theorem, Green's arithmetic removal lemma, and structural results on independent sets in hypergraphs.
引用
收藏
页码:402 / 424
页数:23
相关论文
共 50 条
  • [41] The structure of maximal zero-sum free sequences
    Bhowmik, Gautami
    Halupczok, Immanuel
    Schlage-Puchta, Jan-Christoph
    ACTA ARITHMETICA, 2010, 143 (01) : 21 - 50
  • [42] On strong infinite Sidon and Bh sets and random sets of integers
    Fabian, David
    Rue, Juanjo
    Spiegel, Christoph
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2021, 182
  • [43] Sumset problem on dilated sets of integers Sumset problem on dilated sets of integers
    Singh, Sandeep
    Kaur, Ramandeep
    Verma, Mamta
    JOURNAL OF NUMBER THEORY, 2025, 269 : 429 - 439
  • [44] An application of the sum-product phenomenon to sets avoiding several linear equations
    Shkredov, I. D.
    SBORNIK MATHEMATICS, 2018, 209 (04) : 580 - 603
  • [45] On the range of size of sum graphs & integral sum graphs of a given order
    Tiwari, Apurv
    Tripathi, Amitabha
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) : 2653 - 2661
  • [46] On the Davenport constant and on the structure of extremal zero-sum free sequences
    Geroldinger, Alfred
    Liebmann, Manfred
    Philipp, Andreas
    PERIODICA MATHEMATICA HUNGARICA, 2012, 64 (02) : 213 - 225
  • [47] INDEPENDENT SETS IN HYPERGRAPHS AND RAMSEY PROPERTIES OF GRAPHS AND THE INTEGERS
    Hancock, Robert
    Staden, Katherine
    Treglown, Andrew
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (01) : 153 - 188
  • [48] On the sum of dilations of a set
    Balog, Antal
    Shakan, George
    ACTA ARITHMETICA, 2014, 164 (02) : 153 - 162
  • [49] Reciprocal Sum of Palindromes
    Phunphayap, Phakhinkon
    Pongsriiam, Prapanpong
    JOURNAL OF INTEGER SEQUENCES, 2019, 22 (08)
  • [50] On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
    Bourgain, L.
    Garaev, M. Z.
    MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 2009, 146 : 1 - 21