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 条
  • [31] On solution-free sets of integers
    Hancock, Robert
    Treglown, Andrew
    EUROPEAN JOURNAL OF COMBINATORICS, 2017, 66 : 110 - 128
  • [32] ON THE MAXIMUM SIZE OF A (k, l)-SUM-FREE SUBSET OF AN ABELIAN GROUP
    Bajnok, Bela
    INTERNATIONAL JOURNAL OF NUMBER THEORY, 2009, 5 (06) : 953 - 971
  • [33] On solution-free sets of integers II
    Hancock, Robert
    Treglown, Andrew
    ACTA ARITHMETICA, 2017, 180 (01) : 15 - 33
  • [34] ON SETS WITH SMALL SUMSET AND m-SUM-FREE SETS IN Z/pZ
    Candela, Pablo
    Gonzalez-Sanchez, Diego
    Grynkiewicz, David J.
    BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE, 2021, 149 (01): : 155 - 177
  • [35] Δ-Optimum Forbidden Subgraphs and Exclusive Sum Labellings of Graphs
    Wei, Jianxin
    Fan, Baoqiang
    ARS COMBINATORIA, 2013, 108 : 387 - 402
  • [36] When Sets Are Not Sum-Dominant
    Hung Viet Chu
    JOURNAL OF INTEGER SEQUENCES, 2019, 22 (03)
  • [37] On the complexity of finding and counting solution-free sets of integers
    Meeks, Kitty
    Treglown, Andrew
    DISCRETE APPLIED MATHEMATICS, 2018, 243 : 219 - 238
  • [38] A Turan-Kubilius type inequality on sum sets
    Rivat, Joel
    Sarkozy, Andras
    ACTA ARITHMETICA, 2010, 142 (04) : 311 - 329
  • [39] INTEGERS REPRESENTED AS THE SUM OF ONE PRIME, TWO SQUARES OF PRIMES AND POWERS OF 2
    Lue, Guangshi
    Sun, Haiwei
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2009, 137 (04) : 1185 - 1191
  • [40] HITTING-SETS FOR ROABP AND SUM OF SET-MULTILINEAR CIRCUITS
    Agrawal, Manindra
    Gurjar, Rohit
    Korwar, Arpita
    Saxena, Nitin
    SIAM JOURNAL ON COMPUTING, 2015, 44 (03) : 669 - 697