# 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”

1. Jacek Cichoń says:

A great use of the lemma. Congratulations

Like