# subadditivity for sets and monotonic function

Let $f : \Sigma \rightarrow \mathbb{R}^+$ be a function, where $\Sigma$ is the space of finite subsets of $\mathbb{Z}^d$. Assume that, if $A_1, A_2 \subset \mathbb{Z}^d$ are two disjoint finite sets, then $$f(A_1 \cup A_2) \leq f(A_1) + f(A_2).$$

Assume also that, if $A_1 \subset A_2$, then $f(A_1) \leq f(A_2)$. How to prove that there exists a value $f_0 \in [0, \infty]$ such that $$\lim\limits_{n \rightarrow \infty} \frac{f(A_n)}{|A_n|} = f_0,$$ independently on the specific sequence $A_n \uparrow \mathbb{Z}^d$ satisfying $A_n \subset A_{n+1}$ (EDITED ASSUMPTION), where $|A|$ is the number of elements in $A$?

It's not true. Say $\mathbb Z^d=S_1\cup S_2$, where $S_j$ is infinite and $S_1\cap S_2=\emptyset$. Define $\phi(x)=j$ for $x\in S_j$. Define $$f(A)=\sum_{x\in A}\phi(x).$$Then your limit can equal any number between $1$ and $2$ for some sequence $A_n$ (and for "most" sequences $A_n$ the limit does not exist).

EDIT 1:

Adding the hypothesis that $A_n\subset A_{n+1}$ does not change this. Start with $A_1\subset S_1$. Choose $A_2$ so that $A_1\subset A_2$ but most of the elements of $A_2$ lie in $S_2$. Then choose $A_3$ with elements mostly in $S_1$. Etc.

To be specific, if $n$ is odd and we've chosen $A_n$ we can choose $A_{n+1}$ so that $$\frac{|A_{n+1}\cap S_2|}{|A_{n+1}|}\ge1-\frac1n.$$Similarly for $n$ even, with $S_1$ in place of $S_2$. Then the limit does not exist.

EDIT 2:

So now comes the question of what assumptions are needed to ensure that the limit does exist. I don't know exactly. But if we assume that $f$ is additive instead of just subadditive it's easy to see that the limit cannot exist except under the obvious condition:

Say $f$ is additive. Then there exists $\phi:\mathbb Z^d\to\mathbb R^+$ so that $$f(A)=\sum_{x\in A}\phi(x).$$(Let $\phi(x)=f(\{x\})$.)

I'm not sure whether we're allowing $\infty$ as the limit. Assuming yes:

It follows that the limit exists if and only if there exists $f_o\in[0,\infty]$ such that $$\lim_{x\to\infty}\phi(x)=f_0.$$The sufficiency of this condition is clear. For the necessity: Suppose not. Then there exist $L$ and $\epsilon>0$ such that the sets $S_1$ and $S_2$ are both infinite, where $$S_1=\{x\,:\,\phi(x)>L+\epsilon\},\quad S_2=\{x\,:\,\phi(x)<L-\epsilon\}.$$And now the argument at the top shows the limit does not exist.

EDIT 3:

Next question: What if we assume $f$ is translation-invariant?

If $f$ is additive and translation-invariant then the function $\phi$ above is constant, so the limit exists and is independent of the sequence $A_n$.

If $f$ is just subadditive then no in general. Take $d=1$. Let $S_1$ be the set of even integers and let $S_2$ be the set of odd integers. Define $$f(A)=\max(|A\cap S_1|,|A\cap S_2|).$$ Then $f$ is subadditive and translation-invariant. But if $A_n$ increases to $\mathbb Z$ and $A_n$ consists mostly of even numbers (maybe $A_n$ consists of the even integers beyween $-n^2$ and $n^2$ and the odd integers between $-n$ and $n$) then the limit is $1$, while if $A_n$ is the set of integers between $-n$ and $n$ the limit is $1/2$.

• I added an edit that modifies a bit the question. – QuantumLogarithm Jul 16 '15 at 17:47
• Doesn't change anything - see edit. – David C. Ullrich Jul 16 '15 at 17:54
• I understand, thanks. What additional assumption should $f$ satisfy in order the limit to exist? – QuantumLogarithm Jul 16 '15 at 18:06
• See second edit – David C. Ullrich Jul 16 '15 at 18:22
• Ok, see third edit... – David C. Ullrich Jul 17 '15 at 16:29