Just a quick post to help popularise a useful lemma which seems to be well known to researchers but not to undergraduates, known variously as Fekete’s lemma or the subadditive lemma. It would make for a good Analysis I exercise. Let exclude for the purpose of this post.

Lemma 1 (Fekete’s lemma) If satisfies for all then .

Proof: The inequality is immediate from the definition of , so it suffices to prove for each . Fix such a and set . Set . Now for a given choose so that . Then

so .

Here is an example. For let denote the largest such that every set of nonzero real numbers contains a subset of size containing no solutions to . We call such a subset sum-free.

Proposition 2 converges as .

Proof: Let be a set of size containing no sum-free subset of size larger than , and a set of size containing no sum-free subset of size larger than . Then for large enough , the set is a set of size containing no sum-free subset of size larger than , so . Thus by Fekete’s lemma converges to .

The value of not easy to compute, but certainly . A famously simple argument of Erdos shows : Fix a set , and for simplicity assume . For consider those such that the fractional part of lies between and . This set is sum-free, and if is chosen uniformly at random then has size on average.

The example , due to Malouf, shows . The current record is due to Lewko, who showed by example . Since these examples are somewhat ad hoc, while Erdos’s argument is beautiful, one is naturally led to the following conjecture (indeed many people have made this conjecture):

Conjecture 3 .

Ben Green, Freddie Manners, and I have just proved this conjecture! See our preprint.

A great use of the lemma. Congratulations

LikeLike