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. It would make for a good Analysis I exercise. Let $\mathbf{N}$ exclude $0$ for the purpose of this post.

Fekete's lemma: If $f:\mathbf{N}\to\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
\[\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$.

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.

Claim: $f(n)/n$ converges as $n\to\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$.

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: $\sigma=\frac{1}{3}$.

Ben Green, Freddie Manners, and I have just proved this conjecture: see http://arxiv.org/abs/1301.4579.