Challenge Micromass' big August challenge

[fresh_42]

Ok, I did a Google search and found a paper by Abraham Robinson, from which it is clear that generalized limits can be constructed by using nonstandard analys (several of them, thus solving also Advanced Problem 7 a, in the September Challenge, and probably b, c, and d can also be solved by this method). This proof would be really simple, if one is aquainted to nonstandard analysis, that is . Unfortunately, I cannot give the proof here, since that would be cheating.

And the axiom of choice shows up indirectly here too, in the construction of a nonstandard extension.

I still hope to find an elegant way to prove it after the choice of $L$. Otherwise one would have to start with the shifting invariance and deduce the rest. However, it looks so simple ...

 

[Erland]

I finally have a proof of Advanced Problem 4. But in order to decide whether I have followed the challenge rules or not, I need to tell you how I found it:

I googled "generalized limit" and found an article by Abraham Robinson, where he uses nonstandard analysis to construct a particular class of generalized limits. I didn't read all the details, but I realized from this how one can construct generalized limits using nonstandard analysis in some simple special cases of Robinson's class. This gives a short proof of the existence of generalized limits. But I didn't want a nonstandard proof, so I tried to convert this proof into a "standard" proof. This is possible for all nonstandard proofs, but certainly not easy. The proof given here is the result of this "conversion". It is not strictly the converted version of the nonstandard proof, but rather inspired by it.
Although I probably wouldn't have found this proof if I hadn't found Robinson's article, I still don't think it is against the rules to publish my proof here, since it took me considerable effort to construct the standard proof. Besides, we are halfway into September and the August Challenge should be expired, and I don't care if I get the credit for this solution or not, I just want to share it with you.

The proof is based upon ultrafilters. If you are not aquainted to ultrafilters, you may look up this paper I once wrote myself about nonstandard analysis. Chapter 5 (p. 63 ff.) gives the basic properties of filters and ultrafilters. In particular, look up Definitions 5.1, Corollary 5.7, and Theorem 5.8. These will be used in the proof below without referring to them.
Notice that the axiom of choice is used in Theorem 5.8 (about extending a filter to an ultrafilter), so this axiom is essential here too.

Lemma 1.

Assume that:
1. $I$ is a nonempty set.
2. $\mathcal U$ is an ultrafilter on $I$.
3. $(K,d)$ is a compact metric space.
4. $f: I\to K$ is a function.

Then, there is a unique $x\in K$ such that for every $\epsilon >0$, $f^{-1}(B(x,\epsilon))\in \mathcal U$ (where $B(x,\epsilon)=\{y\in K\,|\,d(y,x)<\epsilon\}$).

Proof: Since $K$ is a compact metric space, it is also totally bounded, which implies that to each integer $n>0$ there is a finite subset $\{x_1^n,x_2^n,\dots,x_{m_n}^n\}\subseteq K$ such that $\cup_{k=1}^{m_n} B(x_k^n,1/n)=K$. This gives $\cup_{k=1}^{m_n}f^{-1}(B(x_k^n,1/n))=I$. Since $\mathcal U$ is an ultrafilter, this means that for some $k$ ($1\le k\le m_n$), $f^{-1}(B(x_k^n,1/n))\in \mathcal U$. Put $x_n=x_k^n$ for every $n>0$, so that we obtain a sequence $\{x_n\}_{n=1}^\infty$ in $K$.
Since $K$ is compact, this sequence has a convergent subsequence $\{x_{n_l}\}_{l=1}^\infty$, with a limit $x\in K$.
Now, take $\epsilon>0$. There is an $l>0$ such that both $n_l\ge 2/\epsilon$ and $d(x_{n_l},x)<\epsilon/2$ hold. Then $B(x_{n_l},1/n_l)\subseteq B(x_{n_l},\epsilon/2)\subseteq B(x,\epsilon)$, which implies $f^{-1}(B(x_{n_l},1/n_l))\subseteq f^{-1}(B(x,\epsilon))$. Since $f^{-1}(B(x_{n_l}))\in\mathcal U$, $f^{-1}(B(x,\epsilon))\in\mathcal U$. This holds for all $\epsilon>0$.
It remains to prove that this $x$ is unique: Assume that $y$ also has these properties, with $y\neq x$. Put $\epsilon=d(x,y)/2>0$. Then also $f^{-1}(B(y,\epsilon))\in\mathcal U$.
Then $\varnothing = f^{-1}(B(x,\epsilon))\cap f^{-1}(B(y,\epsilon))\in\mathcal U$, which is impossible, since $\mathcal U$ is an ultrafilter.
Hence, this $x$ is unique, which completes the proof of Lemma 1.

Next, let $\mathcal V$ be the family of all cofinite subsets of $\mathbb Z_+$, i.e. the family of all $A\subseteq \mathbb Z_+$ such that $\mathbb Z_+\setminus A$ is finite. It is easy to verify that $\mathcal V$ is a filter on $\mathbb Z_+$. Then, there is an ultrafilter $\mathcal U$ on $\mathbb Z_+$ such that $\mathcal V\subseteq \mathcal U$.
We fix such a $\mathcal U$.

$\mathcal U$ contains no finite sets: if $A\in \mathcal U$ is finite, then $\mathbb Z_+\setminus A\in \mathcal V\subseteq \mathcal U$, and hence $\varnothing=A\cap \mathbb Z_+\setminus A\in\mathcal U$, which is a contradiction.

Let $\{x_n\}_{n=1}^\infty$ be a bounded a sequence in $\mathbb R$, say that $|x_n|\le M$ for all $n>0$. The closed interval $[-M,M]$ is a compact metric space (with the metric given by $|x-y|$). Also, the sequence can be considered as a function $f:\mathbb Z_+\to [-M,M]$, with $f(n)=x_n$ for all $n>0$.
Now, it follows from Lemma 1 that there exists a unique $x\in [-M,M]$ such that for all $\epsilon >0$ $\{n\in\mathbb Z_+\,|\,|x_n-x|<\epsilon\}\in\mathcal U$.
This $x$ is independent of the bound $M$: if $M'$ is another bound such that $|x_n|\le M'$ for all $n>0$, with $M\le M'$, say, and the we obtain $y$ instead of $x$ if we apply the above to $M'$ instead of $M$, then also $x\in [-M',M']$, so by the uniqueness for the $M'$ case, $x=y$. Likewise if $M'\le M$.
It follows that there is a unique $x\in \mathbb R$ such that such that for all $\epsilon >0$, $\{n\in\mathbb Z_+\,|\,|x_n-x|<\epsilon\}\in\mathcal U$.

Such a unique $x$ exists for every bounded real sequence $\{x_n\}_{n=1}^\infty$, so this defines a functional $F:\mathcal B\to R$, where $\mathcal B$ is the set of all bounded real sequences $\{x_n\}_{n=1}^\infty$: $F(\{x_n\}_{n=1}^\infty)=x$, with this $x$ just described.

We next prove that $F$ is a (real) linear functional (with the obvious addition and multiplication by scalar): Let $a,b\in \mathbb R$ and $\{x_n\}_{n=1}^\infty,\,\{y_n\}_{n=1}^\infty\in\mathcal B$, with $F(\{x_n\}_{n=1}^\infty)=x$ and $F(\{y_n\}_{n=1}^\infty)=y$. Take $\epsilon>0$.
Put $A=\{n\in\mathbb Z_+\,|\,|x_n-x|<\frac\epsilon{2|a|+1}\}$ and $B=\{n\in\mathbb Z_+\,|\,|y_n-y|<\frac\epsilon{2|b|+1}\}$. Then $A,B\in \mathcal U$, and hence $A\cap B\in \mathcal U$. If $n\in A\cap B$, then $|(ax_n+by_n)-(ax+by)|\le |a||x_n-x|+|b||y_n-y|<|a|\frac\epsilon{2|a|+1}+|b|\frac\epsilon{2|b|+1}<\epsilon$. This holds for all $n\in A\cap B$, so $A\cap B\subseteq \{n\in\mathbb Z_+\,|\,|(ax_n +by_n)-(ax+by)|<\epsilon\}$. Therefore, $\{n\in\mathbb Z_+\,|\,|(ax_n +by_n)-(ax+by)|<\epsilon\}\in \mathcal U$. This holds for all $\epsilon>0$. By the uniqueness clause above and the subsequent definition of $F$, this means that $F(a\{x_n\}_{n=1}^\infty+ b\{x_n\}_{n=1}^\infty)=F(\{ax_n+by_n\}_{n=1}^\infty)=ax+by$.

So, $F$ is linear.

Given $\{x_n\}_{n=1}^\infty\in \mathcal B$, we have $F(\{x_n\}_{n=1}^\infty)\le \overline \lim x_n$: If $x>\overline\lim x_n$, put $\epsilon=|x-\overline \lim x_n|/2$. Then $\{n\in\mathbb Z_+\,|\,|x_n-x|<\epsilon\}$ is a finite set, and then it does not lie in $\mathcal U$, so $F(\{x_n\}_{n=1}^\infty)\neq x$.
Applying this and linearity, we obtain $F(\{x_n\}_{n=1}^\infty)=-F(-\{x_n\}_{n=1}^\infty)=-F(\{-x_n\}_{n=1}^\infty)\ge -\overline \lim (-x_n)=\underline\lim x_n$.
Thus, $\underline \lim x_n \le F(\{x_n\}_{n=1}^\infty)\le \overline\lim x_n$.

Now, we can prove the following:

Lemma 2.

Let $G:\mathcal B\to\mathcal B$ be linear operator such that
1) $\underline\lim x_n\le \underline\lim y_n\le \overline\lim y_n\le\overline\lim x_n$, and
2) $\lim_{n\to\infty}(z_n-y_n)=0$,
where $\{y_n\}_{n=1}^\infty=G(\{x_n\}_{n=1}\infty)$, $\{z_n\}_{n=1}^\infty =G(\{u_n\}_{n=1}^\infty)$, and $u_n=x_{n+1}$ for all $n\in\mathbb Z_+$, for
$\{x_n\}_{n=1}^\infty)\in\mathcal B$.

Then $L=F\circ G:\mathcal B\to \mathbb R$ is a generalized limit.

Proof: Since $F$ and $G$ are linear, so is $L=F\circ G$. With $\{x_n\}_{n=1}^\infty$, $\{y_n\}_{n=1}^\infty$, $\{u_n\}_{n=1}^\infty$, and $\{z_n\}_{n=1}^\infty$ related as above, we have $\underline \lim y_n \le F(\{y_n\}_{n=1}^\infty)\le \overline\lim y_n$. Since $L(\{x_n\}_{n=1}^\infty)=F(\{y_n\}_{n=1}^\infty)$, 1) gives $\underline \lim x_n \le L(\{x_n\}_{n=1}^\infty)\le \overline\lim x_n$.

Now, put $F(\{y_n\}_{n=1}^\infty)=y$. Let $\epsilon>0$. Put $A=\{n\in\mathbb Z_+\,|\,|y_n-y|<\epsilon/2\}$. Then $A\in\mathcal U$. By 2), there is an $N\in\mathbb Z_+$ such that $|z_n-y_n|<\epsilon/2$ for all $n\ge N$. Put $B=\{n\in \mathbb Z_+\,|\,n\ge N\}$. Then $B\in\mathcal U$, since $B$ is cofinite. Now, if $n\in A\cap B$, $|z_n-y|\le|z_n-y_n|+|y_n-y|<\epsilon/2 + \epsilon/2=\epsilon$. This means that $A\cap B\subseteq \{n\in \mathbb Z_+\,|\,|z_n-y|<\epsilon\}$, so $\{n\in \mathbb Z_+\,|\,|z_n-y|<\epsilon\}\in\mathcal U$. This holds for all $\epsilon >0$, which means that $F(\{z_n\}_{n=1}^\infty)=F(\{y_n\}_{n=1}^\infty)$, or $L(\{u_n\}_{n=1}^\infty)= L(\{x_n\}_{n=1}^\infty)$.
This holds for all $\{x_n\}_{n=1}^\infty\in \mathcal B$ and $\{u_n\}_{n=1}^\infty$, such that $u_n=x_{n+1}$ for all $n\in\mathbb Z_+$.

We have now proved that $L$ satisfies conditions 1, 2, 3, and 5 in the definition of a generalized limit.
4 follows from 3, since $\underline \lim x_n\ge 0$ if $x_n\ge 0$ for all $n \in\mathbb Z_+$.
6 also follows from 3, for if $\lim_{n\to \infty} x_n$ exists, then $\lim_{n\to \infty} x_n=\underline \lim x_n\le L(\{x_n\}_{n=1}^\infty)\le\overline\lim x_n = \lim_{n\to \infty} x_n$.
Thus, $L(\{x_n\}_{n=1}^\infty)=\lim_{n\to \infty} x_n$, that is, 6 holds.

Thus $L$ is a generalized limit, so Lemma 2 is proved.

It remains to prove that there exists an operator $G$ which satisfies the conditions in Lemma 2. Indeed, if we could find $G$ and $G'$ both satisfying these conditions, such that $L=F\circ G\neq F\circ G´=L'$, then we have found two different generalized limits, thus solving Advanced Problem 7a in the September Challenge.

I leave the latter problem for the moment, and confine myself to find just one $G$:

Define $G:\mathcal B\to\mathcal B$ by $G(\{x_n\}_{n=1}^\infty)=\{y_n\}_{n=1}^\infty$, for $\{x_n\}_{n=1}^\infty\in\mathcal B$, where $y_n=\frac1n\sum_{k=1}^n x_k$, for all $n\in\mathbb Z_+$.
It is clear that $\sup_n |y_n|\le\sup_n |x_n|$, so $\{y_n\}_{n=1}^\infty\in\mathcal B$.
It is also clear that $G$ is linear. We must prove that $G$ satisfies 1) and 2) of Lemma 2.

Given $\{x_n\}_{n=1}^\infty\in\mathcal B$, let $\{y_n\}_{n=1}^\infty$ be as above and $\{u_n\}_{n=1}^\infty$ and $\{z_n\}_{n=1}^\infty$ as in Lemma 2, related to these$\{x_n\}_{n=1}^\infty$ and $\{y_n\}_{n=1}^\infty$.
Put $s=\overline \lim x_n$.
Take $\epsilon>0$. Put $M=\max(\epsilon/4,\sup_n |x_n|)$. There is an $N_1\in\mathbb Z_+$ such that $x_n<s+\epsilon/4$ for all $n\ge N_1$.
Choose $N\in \mathbb Z_+$ such that $N\ge 4MN_1/\epsilon\ge N_1$.
Then, for $n\ge N$: $y_n=\frac1n\sum_{k=1}^n x_k=\frac1n\sum_{k=1}^{N_1} x_k +\frac1n\sum_{k=N_1+1}^n x_k \le$
$\le MN_1/n +(s+\epsilon/4) (n-N_1)/n\le MN_1/N+(s+\epsilon/4)n/n+MN_1/N+(\epsilon/4)N_1/n<$
$<\epsilon/4+(s+\epsilon/4)+\epsilon/4+\epsilon/4=s+\epsilon$.
Thus, $y_n < s+\epsilon$.

There is such an $N$ to each $\epsilon>0$, which means that $\overline \lim y_n\le s=\overline\lim x_n$.
Applying this to $-\{x_n\}_{n=1}^\infty$ and using linearity, we obtain $\underline\lim y_n=-\overline \lim (-y_n)\ge -\overline \lim (-x_n)=\underline\lim x_n$.

It follows that $\underline \lim x_n\le\underline\lim y_n\le\overline\lim y_n\le\overline\lim x_n$. This holds for all $\{x_n\}_{n=1}^\infty$ and $\{y_n\}_{n=1}^\infty$ related as above, that is, 1) in Lemma 2 holds.

Next, let $\{x_n\}_{n=1}^\infty$ and $\{y_n\}_{n=1}^\infty$ be as above, and $\{u_n\}_{n=1}^\infty$ and $\{z_n\}_{n=1}^\infty$ as in Lemma 2, related to these$\{x_n\}_{n=1}^\infty$ and $\{y_n\}_{n=1}^\infty$.
Then, for $n\in \mathbb Z_+$, and with $M$ as above, $|z_n-y_n|=|\frac1n\sum_{k=1}^n u_n -\frac1n\sum_{k=1}^n x_n|=\frac1n|\sum_{k=2}^{n+1} x_k -\sum_{k=1}^n x_k|= |x_{n+1}-x_1|/n\le 2M/n\to 0$ as $n\to\infty$.

So, $\lim_{n\to\infty}|z_n-y_n|=0$. This holds for all $\{x_n\}_{n=1}^\infty\in\mathcal B$, that is, 2) in Lemma 2 holds.

We have proved that all the conditions of Lemma 2 are satisfied for our $G$. Thus, by Lemma 2, $L=F\circ G$ is a generalized limit.

Thus, there exists a generalized limit, Q.E.D.

 

[micromass]

Very nice! Here is a proof using Hahn-Banach instead:

Consider the set of all bounded sequences $\ell^\infty$. Let $S((x_n)) = x_{n+1}$. Consider
W = \{Sx - x~\vert~x\in \ell^\infty\}
We clam that for any $y\in W$ and $c\in \mathbb{R}$ we have
\|y + c1\|_\infty \geq |c|
Indeed, if $z = Sx - x + c1$, then $z_n = x_{n+1} -x_n +c$ and
\|z\|_\infty\geq \frac{1}{N}\sum |z_n| \geq \frac{1}{n}\left|\sum z_n\right| = \left|\frac{1}{N}(x_{N+1} - x_1) + c)\right|
This converges to $|c|$ as $N\rightarrow +\infty$ because $|x_{N+1} - x_1|\leq 2\|x\|_\infty$ is bounded.

In particular, it follows that the set of constant sequences $C$ has trivial intersection with $W$. Define on $W\oplus C$
\Phi_0(y + c1) = c
We have just established that $\Phi_0(z)\leq \|z\|_\infty$ for every $z\in W\oplus C$.

Using the Hahn-Banach theorem, there exists a linear functional $\Phi$ on $\ell^\infty$ extending $\Phi_0$ such that
|\Phi(x)|\leq \|x\|_\infty
This $\Phi$ satisfies (1) and (2) by construction.

We have
\Phi(Sx) - \Phi(x) = \Phi(Sx - x) = \Phi_0(Sx - x) = 0
This $(5)$ is satisfied.

For $x\geq 0$, we write $x = \|x\|_\infty y$ where $y_n\in [0,1]$ for all $n$. Then
\|1 - y\|_\infty \leq 1
Hence
1 - \Phi(y) = \Phi(1-y)\leq \|1-y\|_\infty\leq 1
Implying
\Phi(y)\geq 0
And thus
\Phi(x) = \|x\|_\infty\Phi(y) \geq 0
Thus (4) is satisfied.

Given $x\in \ell^\infty$ and any $\alpha,\beta$ with
\alpha&lt;\liminf x_n,~\limsup x_n&lt;\beta
there is an $N$ such that $\alpha<x_n<\beta$ for all $n>N$. This means that
y = S^N x - \alpha 1,~z = \beta.1 - S^Nx
are positive bounded sequences. Hence
0\leq \Phi(y) = \Phi(S^N x) - \alpha = \Phi(x) -\alpha
Implying $\alpha<\Phi(x)$, and
0\leq \Phi(z) = \beta - \Phi(S^n x) = \beta - \Phi(x)
Implying $\Phi(x)<\beta$.
Since $\alpha,\beta$ are chosen arbitrarily, property (3) follows. Property (6) is a direct consequence from (3).

 

[micromass]

Erland, are you acquainted with convergence of (ultra)filters? I think it would make your proof a lot more cleaner if you could use that instead.

 

[Erland]

Erland, are you acquainted with convergence of (ultra)filters? I think it would make your proof a lot more cleaner if you could use that instead.

I did read about it many years ago, so I had to look it up. Perhaps that could work, but how? Recall that my ultrafilter is not on $\mathbb R$, but on $\mathbb Z_+$, which has no obviuos suitable topology.

Btw, nice Hahn-Banach proof, much simpler than mine!

 

[Erland]

Let me also give the nonstandard analysis proof I mentioned. To follow it, the reader needs some knowledge about nonstandard analysis, for which I refer to the literature.

We work in a nonstandard extension of some superstructure over $\mathbb R$. Every number, set, function etc. $x$ in this superstructure has a $*$-transform $^*x$ in the extended superstructure.
Let $\{x_n\}_{n\in \mathbb Z_+}$ be a bounded sequence in $\mathbb R$. Its $*$-transform $^*\{x_n\}_{n\in \mathbb Z_+}$is a bounded hypersequence $\{x_n\}_{n\in \,^*\mathbb Z_+}$ in $^*\mathbb R$.

Pick an infinite positive hyperinteger $H\in\, ^*\mathbb Z_+\setminus\mathbb Z_+$.
For each bounded real sequence $\{x_n\}_{n\in \mathbb Z_+}$, put $F(\{x_n\}_{n\in \mathbb Z_+})=st(x_H)$, i.e. the standard part of $x_H$ (in the corresponding hypersequence). It is easy to verify that $F$ is a real linear functional on the space $\mathcal B$ of all bounded real sequences.
It is also so that $\overline\lim x_n=\max_{K\in\, ^*\mathbb Z_+-\mathbb Z_+}st(x_K)$ and $\underline\lim x_n=\min_{K\in \,^*\mathbb Z_+-\mathbb Z_+}st(x_K)$, so $\underline\lim x_n\le F(\{x_n\}_{n\in \mathbb Z_+})\le \overline\lim x_n$.

Now, define $G: \mathcal B\to\mathcal B$ by $G(\{x_n\}_{n\in \mathbb Z_+}=\{y_n\}_{n\in \mathbb Z_+}$, where $y_n=\frac1n\sum_{k=1}^n x_n$ for all $n\in \mathbb Z_+$. Let $H_1=\,^*\lfloor \,^*\sqrt{H}\rfloor$. Then $H_1$ is an infinite positive hyperinteger such that $H_1/H$ is infinitesimal.

There is a real $M$ such that $|x_n|\le M$ for all $n\in \mathbb Z_+$, and the same holds for all $n\in ^*\mathbb Z_+$, with the same $M$. It follows that $\frac1H\,^*\sum_{k=1}^{H_1}x_k$ is infinitesimal and that $y_H=\frac1H\,^*\sum_{k=1}^{H}x_k$ is finite, and $F(\{x_n\}_{n\in \mathbb Z_+})=st(y_H)=st(\frac1H\,^*\sum_{k=H_1+1}^{H}x_k)$. By the characterizations of $\overline\lim x_n$ and $\underline\lim x_n$ above, this implies that $\underline\lim x_n\le F(\{y_n\}_{n\in \mathbb Z_+})\le \overline \lim x_n$.

With these $\{x_n\}_{n\in \mathbb Z_+}$ and $\{y_n\}_{n\in \mathbb Z_+}$, define $\{u_n\}_{n\in \mathbb Z_+}$ by $u_n=x_{n+1}$, for all $n\in \mathbb Z_+$, and put $\{z_n\}_{n\in \mathbb Z_+}=G(\{u_n\}_{n\in \mathbb Z_+})$. Then $F(\{z_n\}_{n\in \mathbb Z_+})-F(\{y_n\}_{n\in \mathbb Z_+})=st((x_{H+1}-x_1)/H)=0$.

So, if we put $L=G\circ F:\mathcal B\to\mathbb R$, then $L$ is linear, $\underline\lim x_n\le L(\{x_n\}_{n\in \mathbb Z_+})\le \overline \lim x_n$,
since $G(\{x_n\}_{n\in \mathbb Z_+})=\{y_n\}_{n\in \mathbb Z_+}$, and $L(\{u_n\}_{n\in \mathbb Z_+})=L(\{x_n\}_{n\in \mathbb Z_+})$, since $F(\{z_n\}_{n\in \mathbb Z_+})=F(\{y_n\}_{n\in \mathbb Z_+})$.

This means that $L$ satisfies 1, 2, 3, and 5, and hence 4 and 6, in the definition of generalized limit, so $L$ is a generalized limit.

If one tries to convert this proof to a "standard" proof, the result is something like my previous proof. So we see that nonstandard proofs are often considerably shorter!