[HN Gopher] Graduate Student Solves Classic Problem About the Li...
       ___________________________________________________________________
        
       Graduate Student Solves Classic Problem About the Limits of
       Addition
        
       Author : sonabinu
       Score  : 67 points
       Date   : 2025-05-23 11:15 UTC (2 days ago)
        
 (HTM) web link (www.quantamagazine.org)
 (TXT) w3m dump (www.quantamagazine.org)
        
       | VladVladikoff wrote:
       | Why is the lower bound N/3 and not N/2? Doesn't the set of all
       | odd numbers make the lower bound N/2?
        
         | Bootvis wrote:
         | N/3 + log log N holds for any arbitrary set, not just for 1 ...
         | N or something.
        
         | hiddencost wrote:
         | An adversary first gives you any set, and then you have to find
         | a subset.
         | 
         | They could give you only even numbers.
        
           | VladVladikoff wrote:
           | Ohhhh ok thanks!
        
       | svat wrote:
       | So cool. On the one hand, going from n/3 to (n/3 + log log n)
       | seems like such a small improvement, but as the article shows,
       | the history is formidable:
       | 
       | - n/3 (Erdos, 1965)
       | 
       | - (n+1)/3 (Alon and Kleitman, 1990)
       | 
       | - (n+2)/3 (Bourgain, 1997)
       | 
       | - n/3 + O(log log n) (this paper, Benjamin Bedert,
       | https://arxiv.org/abs/2502.08624)
       | 
       | And the upper bound:
       | 
       | - n/3 + o(n) (Eberhard, Green, Manners, 2014).
       | 
       | Ben Green's list of 100 open problems is which this is (was?)
       | Problem 1, is here:
       | https://people.maths.ox.ac.uk/greenbj/papers/open-problems.p...
        
       | nyc111 wrote:
       | Is the main subject here addition or sets?
        
         | abetusk wrote:
         | It concerns the size of the largest sum-free set [0]. Take a
         | (finite) set of integers, A. What is the largest subset of A
         | such that no two entries sum to a third.
         | 
         | The previous results was not much better than |A|/3. The
         | current, just proved, result shows that the largest subset is
         | |A|/3 + c log(log(|A|)).
         | 
         | For example, the set {1,2,3} is not sum-free (1+2 = 3) but the
         | subset {2,3} is sum-free (2+3 \notin {2,3}).
         | 
         | [0] https://en.wikipedia.org/wiki/Sum-free_set
        
           | nyc111 wrote:
           | "It concerns the size of the largest sum-free set [0]. Take a
           | (finite) set of integers, A. What is the largest subset of A
           | such that no two entries sum to a third."
           | 
           | Yes, it seems to me we are focusing mainly about sets, not
           | addition. Addition is secondary. Mainly I'm debating the
           | title. The word "set" ought to be in the title too. I guess
           | not a big deal.
        
             | abetusk wrote:
             | I see. Yes, I agree, the title is bad.
        
       | dooglius wrote:
       | It's weird to spend paragraphs talking about the incremental
       | improvements to (N+1)/3 and (N+2)/3 and then miss that the new
       | bound is N/3 + c*log(log(n)) for some c>0, not N/3+log(log(n))
        
       ___________________________________________________________________
       (page generated 2025-05-25 23:01 UTC)