1
$\begingroup$

I am working through this post from Terry Tao's blog.

Problem: Prove that if a binary (i.e. consisting of $0$ and $1$, or $\top$ and $\bot$) sequence $x_n$ is such that $\text{p-lim}(x_n) = 1$, then any sequence $y_n$ containing $x_n$ has $\text{p-lim}(y_n) = \text{p-lim}(x_n) = 1$.

My attempt at a proof. We know the following facts regarding $\text{p-lim}$:

  • homomorphic: $\text{p-lim}(1) = 1$, $\text{p-lim}(Cx_n) = C\text{p-lim}(x_n)$ (for some $C \in \{0, 1\}$), $\text{p-lim}(x_n \oplus y_n) = \text{p-lim}(x_n) \oplus \text{p-lim}(y_n)$ (where $\oplus$ is the "or" operator), and $\text{p-lim}(x_n \otimes y_n) = \text{p-lim}(x_n) \otimes \text{p-lim}(y_n)$ (where $\otimes$ is the "and" operator)
  • bounded: $\text{p-inf}(x_n) \leq \text{p-lim}(x_n) \leq \text{p-sup}(x_n)$
  • non-principality: deletion of a finite number of elements from $x_n$ should not change its $\text{p-lim}$.

We do not know anything else about $\text{p-lim}$, so a combination of these facts must be used to prove the required.

Note that $x_n$ will never be finite, since it is an indicator sequence which runs over all the natural numbers, hence $y_n$ will never be finite either. So non-principality is unlikely to be a useful tool. The supremum and infimum of every sequence of binary numbers which is not $1, 1, 1, 1, 1, 1 \dots$ or $0, 0, 0, 0, 0, 0, \dots$ is trivially $0$ and $1$ respectively, so it is unlikely that boundedness can be used as a tool.

Let us try to use the fact that $\text{p-lim}$ is a homomorphism. Note that $y_n \oplus x_n = y_n$, since $x_n \subset y_n$ (in other words, $x_k = 1 \Rightarrow y_k = 1$, while $x_k = 0 \Rightarrow (y_k = 1 \vee y_k = 0)$). Then:

\begin{align*} &\quad\;\; x_n \oplus y_n = y_n \\ &\Rightarrow \text{p-lim}(x_n \oplus y_n) = \text{p-lim}(y_n) \\ &\Rightarrow \text{p-lim}(x_n) \oplus \text{p-lim}(y_n) = \text{p-lim}(y_n) \\ &\Rightarrow 1 \oplus \text{p-lim}(y_n) = \text{p-lim}(y_n) \\ &\{\text{1 is the zero of $\oplus$}\} \\ &\Rightarrow 1 = \text{p-lim}(y_n) \end{align*}


Is this proof correct? The following assumptions, I think, will need confirmation:

  • On the space of binary numbers, is it okay to assume that $\oplus, \otimes$ are the analogues of $+, \times$, for the homomorphism property? I think it should be okay, because: 1) it makes things work out nicely (I think I can use similar logic to show that some of the other ultrafilter properties hold for the $\text{p-lim}$ over the binary numbers), and connects nicely to classical "predicate calculus" stuff; 2) $\oplus, \otimes$ can also be thought of as "addition/multiplication $\mathbb{Z}/2$")
$\endgroup$
3
  • $\begingroup$ What do you mean by $(y_n)$ "containing" $(x_n)$? Sequences are functions, not sets.. It seems you mean $y_n \le x_n$ for all $n$? $\endgroup$ – Henno Brandsma Jan 30 '19 at 5:34
  • $\begingroup$ It seems that you mean by "$x_n \subset y_n$" that $y_k \le x_k$ for all $k$; is that true? In the subset interpretation Tao gives the latter means that the subset of $\omega$ associated with $y$ is a subset of the one asssociated with $x$, so inclusion the other way around.... You seem confused. $\endgroup$ – Henno Brandsma Jan 30 '19 at 23:07
  • $\begingroup$ @HennoBrandsma by $x_n$ being contained in $y_n$, I mean: $x_k = 1 \Rightarrow y_k = 1$ $\endgroup$ – user89 Jan 31 '19 at 18:45
0
$\begingroup$

You can go about it in two ways, which come down to the same thing. If we have a $p$-lim for sequences with values $0$ and $1$ we can identify a sequence $x=(x_n)$ with a subset $A(x) \subseteq \omega$ where $n \in A(x)$ iff $x_n =1$ (using characteristic functions, in other words, or indicator sequences as Tao calls them). As $p$-$\lim(x_n) \in \{0,1\}$ as well, as he also shows, we have that a $p$-lim defines a non-principal ultrafilter $\mathcal{F}$ on the powerset of $\omega$: $A \in \mathcal{F}$ iff the indicator sequence $\chi_A$ has $p$-$\lim(\chi_A)=1$. The monotonicity property you mention follows immediately from Tao's monotonicity principle: if two Boolean sequences $x,y$ obey: $\forall k: x_k =1 \implies y_k=1$, we see that $A(x) \subseteq A(y)$ and as $p$-$\lim(x)=1$ so $A(x) \in \mathcal{F}$ we have $A(y) \in \mathcal{F}$ by monotonicity of ultrafilters, and so $p$-$\lim(y)=1$ as well.

To see the monotonicity of the ultrafilter (which Tao doesn't show) is to use the homomorphism properties. "$x$ is contained in $y$" (or $A(x) \subseteq A(y)$) in your definition is equivalent to the identity $1-x+xy=1$ or $xy-x=x(y-1)=0$ (i.e. this holds for all $k$, as reals). This identity is preserved by $p$-$\lim$ by its homomorphism property:

$$p\text{ -}\lim(x)\left(1-p\text{ -}\lim(y)\right) = 0$$

from which it follows that $p\text{ -}\lim(x)=1$ implies $p\text{-}\lim(y)=1$ which is what we needed.

$\endgroup$
2
  • $\begingroup$ Can you comment on whether my proof approach was okay or not? $\endgroup$ – user89 Feb 1 '19 at 3:47
  • $\begingroup$ @user89 You have to prove separately that $\oplus$ is preserved. I do think it's true, as it can be defined in terms of $+,\cdot$ on the reals, when restricted to Boolean sequences, so do that. And you need to justify too that $x$ contained in $y$ iff $x \oplus y = y$. I think the equivalence is not true. $\endgroup$ – Henno Brandsma Feb 1 '19 at 5:28

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.