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):