Fekete’s lemma and sum-free sets

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 {\mathbf{N}} exclude {0} for the purpose of this post.

Lemma 1 (Fekete’s lemma) If {f:\mathbf{N}\rightarrow\mathbf{R}} satisfies {f(m+n)\leq f(m)+f(n)} for all {m,n\in\mathbf{N}} then {f(n)/n\longrightarrow\inf_n f(n)/n}.

Proof: The inequality {\liminf f(n)/n \geq \inf_d f(d)/d} is immediate from the definition of {\liminf}, so it suffices to prove {\limsup f(n)\leq f(d)/d} for each {d\in\mathbf{N}}. Fix such a {d} and set {M=\max\{0,f(1),f(2),\ldots,f(d-1)\}}. Set {f(0)=0}. Now for a given {n} choose {k} so that {0 \leq n-kd < d}. Then

\displaystyle  \frac{f(n)}{n} \leq \frac{f(n-kd)}{n} + \frac{f(kd)}{n} \leq \frac{M}{n} + \frac{kf(d)}{kd} \longrightarrow \frac{f(d)}{d},

so {\limsup f(n)/n \leq f(d)/d}. \Box

Here is an example. For {n\in\mathbf{N}} let {f(n)} denote the largest {k\in\mathbf{N}} such that every set of {n} nonzero real numbers contains a subset of size {k} containing no solutions to {x+y=z}. We call such a subset sum-free.

Proposition 2 {f(n)/n} converges as {n\rightarrow\infty}.

Proof: Let {A} be a set of size {m} containing no sum-free subset of size larger than {f(m)}, and {B} a set of size {n} containing no sum-free subset of size larger than {f(n)}. Then for large enough {M\in\mathbf{N}}, the set {A\cup MB} is a set of size {m+n} containing no sum-free subset of size larger than {f(m)+f(n)}, so {f(m+n)\leq f(m)+f(n)}. Thus by Fekete’s lemma {f(n)/n} converges to {\inf f(n)/n}. \Box

The value of {\sigma = \lim f(n)/n} not easy to compute, but certainly {0\leq\sigma\leq\frac{1}{2}}. A famously simple argument of Erdos shows {\sigma\geq\frac{1}{3}}: Fix a set {A}, and for simplicity assume {A\subset\mathbf{N}}. For {\theta\in[0,1]} consider those {n\in A} such that the fractional part of {\theta n} lies between {\frac{1}{3}} and {\frac{2}{3}}. This set {A_\theta} is sum-free, and if {\theta} is chosen uniformly at random then {A_\theta} has size {|A|/3} on average.

The example {A=\{1,2,3,4,5,6,8,9,10,18\}}, due to Malouf, shows {\sigma\leq\frac{2}{5}}. The current record is due to Lewko, who showed by example {\sigma\leq\frac{11}{28}}. 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 {\sigma=\frac{1}{3}}.

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

One thought on “Fekete’s lemma and sum-free sets

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s