3
$\begingroup$

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$?

$\endgroup$
3
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.