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?
hiddencost · 31d ago
An adversary first gives you any set, and then you have to find a subset.
They could give you only even numbers.
VladVladikoff · 31d ago
Ohhhh ok thanks!
Bootvis · 31d ago
N/3 + log log N holds for any arbitrary set, not just for 1 … N or something.
dooglius · 31d 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 · 31d ago
Is the main subject here addition or sets?
abetusk · 31d 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.
svat · 30d ago
Although as students we learn addition before we learn about sets, from the viewpoint of mathematics, sets are everywhere / everything can be expressed in terms of sets, so there's no point talking about sets in any given problem (unless it involves matters deep in set theory, which this does not). This is evident even colloquially, where we can talk about problems without explicitly using the word “set” — for example, “given some numbers, how many can you pick such that no two of them add up to another?” — while it's hard to avoid using “add” or “addition”.
So this problem is really more about addition than about sets, as the mathematicians who worked on it will say: the amount of set theory it involves is very little/almost nonexistent, while the properties of addition it involves are fairly deep.
(But sure, no harm if sets were mentioned in the title, I guess!)
- 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.
So this problem is really more about addition than about sets, as the mathematicians who worked on it will say: the amount of set theory it involves is very little/almost nonexistent, while the properties of addition it involves are fairly deep.
(But sure, no harm if sets were mentioned in the title, I guess!)