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:
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 · 6h ago
N/3 + log log N holds for any arbitrary set, not just for 1 … N or something.
hiddencost · 5h ago
An adversary first gives you any set, and then you have to find a subset.
They could give you only even numbers.
VladVladikoff · 5h ago
Ohhhh ok thanks!
dooglius · 1h ago
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))
nyc111 · 2h ago
Is the main subject here addition or sets?
abetusk · 59m ago
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}).
"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.
- n/3 (Erdős, 1965)
- (n+1)/3 (Alon and Kleitman, 1990)
- (n+2)/3 (Bourgain, 1997)
- n/3 + Ω(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...
They could give you only even numbers.
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
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.