TITLE: Show If $\int_0^{\infty} f(x) dx$ is convergent, for $a \ge 0$, $\int_0^{\infty} \frac{f(x)}{e^{ax}}$ is convergent.
QUESTION [1 upvotes]: $e^{ax} \ge 1$ so for $f(x) \ge 0$ we have $\frac{f(x)}{e^{ax}} \le f(x)$ and by comparison test it is convergent. But what about negative f(x)?
I also used integration by parts but it was confusing.
If $g(x) = e^{-ax}$ then $g'(x) = -ae^{-ax}$ and if F'(x) = f(x) then $$e^{-ax}F(x) = \int e^{-ax}f(x) + \int -ae^{-ax}F(x)$$ on the other hand $$\int_0^{\infty}f(x) = \lim_{T\to\infty}\int_0^{T}f(x) = \lim_{T\to\infty}F(T) - F(0)$$
But how can I use these informations?

REPLY [0 votes]: Claim: $$\left|\int_0^\infty \frac{f(x)}{e^{ax}}\right| \leq \sup_{b \geq 0} \left|\int_0^b f(x)\right|$$
Lemma: If $a_1, a_2, \cdots$ is a sequence of real numbers and $1 \geq b_1 \geq b_2 \geq \cdots$ is another sequence, then for every $n \geq 1$, $$\left|\sum_{k =1}^n a_kb_k \right| \leq \sup_{i \leq n} \left|\sum_{k = 1}^i a_k \right|$$
proof: Let $i$ be the smallest index such that $\left|\sum_{k =1}^i a_kb_k \right|$ is maximized. WLOG assume $$\sum_{k =1}^i a_kb_k \geq 0$$ We will show by induction that for every $0 \leq j \leq i$, $$\sum_{k = 1}^{j}a_kb_k + b_{j+1}\sum_{k = j+1}^i a_i \geq \sum_{k =1}^i a_kb_k$$ starting with $j = i$ and moving down.
The base case is given and the inductive step follows from inductive hypothesis and the fact that for every $j$, $\sum_{k = j+1}^ia_k \geq 0$ because otherwise we would have $$\sum_{k =1}^{j} a_kb_k > \sum_{k =1}^i a_kb_k$$ contradicting the definition of $i$.
Now, to prove the main claim it suffices to show for every, $C > 0$, $$\left|\int_0^C \frac{f(x)}{e^{ax}}\right| \leq \sup_{0 \leq b \leq C} \left|\int_0^b f(x)\right|$$ But this follows from the lemma and approximating the integral by Riemann Sums.


text:
\vspace{-.5em}
\section{Experiments}\label{sec:experiments}\vspace{-.3em}

We evaluate our approach by learning a range of synthetic LPs and parametric instances of minimum-cost multi-commodity flow.
Use of synthetic instances is common in IO (e.g., \citet{Ahuja01, Keshavarz11, Dong18}) and there are no community-established and readily-available benchmarks, especially for more general formulations.
Our experimental study considers instances not directly addressable by previous IO work, either because we learn all coefficients jointly or because the parametrization results in non-convex NLP.

We compare three versions\footnote{For completeness we also evaluated finite-differences (\SQPdiff) which, unsurprisingly, was not competitive.} of our gradient-based method (\SQPbprop, \SQPimpl, \SQPdir) with two gradient-free methods: random search (RS) and COBYLA. The main observation is that the gradient-based methods perform similarly and become superior to gradient-free methods as the dimension~$K$ of parametrization $\bw$ increases.  We find that including a black-box baseline like COBYLA is important for assessing the practical difficulty of an IO instance (and encourage future papers to do so) because such methods work reasonably well in low-dimensional problems. A second observation is that generalization to testing conditions is difficult because the discontinuous nature of LP decision space creates an underfitting phenomenon. This may explain why many previous works in IO require a surprising amount of training data for so few model parameters (see end of Section~\ref{sec:experiments}). A third observation is that there are instances for which no method succeeds at minimizing training error 100\% of the time. Our method can therefore be viewed as a way to significantly boost the probability of successful training, when combined with simple global optimization strategies such as multi-start.

Experiments used PyTorch~v1.6 nightly build, the COBYLA and SLSQP wrappers from SciPy~v1.4.1, and were run on an Intel Core i7 with 16GB RAM. (We do not use GPUs, though our PyTorch interior point solver inherits GPU acceleration.) We do not regularize $\bw$ nor have any other hyperparameters.

\begin{figure}[t]
\centering
    \begin{subfigure}{\textwidth}
      \centering
          \includegraphics[width=\textwidth]{Figure/fig_exp1a_10d80cons.pdf}\vspace{-.5em}
    \end{subfigure}
\caption{A comparison on synthetic PLP instances. Shown is the probability of achieving zero AOE training loss over time (curves), along with final training and testing loss (box plots). Each mark denotes one of 100 trials (different instances) with  20 training and testing points ($D\!=\!10, M_1\!=\!80$). The AOE testing loss is always evaluated with the `true' cost $\bc$, never the imputed cost. For insight into why the mean testing error is larger than median testing error, see discussion (end of Section~\ref{sec:experiments}).
\label{fig:exp_1a}\vspace{-.5em}}
\end{figure}

{\bf Learning linear programs \;}  We used the LP generator of~\citet{tan2019dio}, modifying it to create a more challenging variety of feasible regions; their code did not perform competitively in terms of runtime or success rate on these harder instances, and cannot be applied to AOE loss.
Fig.~\ref{fig:exp_1a} shows the task of learning ($\bc$, $\bA$, $\bb$) with a $K\!=\!6$ dimensional parametrization $\bw$, a $D\!=\!10$ dimensional decision space $\bx$, and 20 training observations. RS fails; COBYLA `succeeds' on ~25\% of instances; SQP succeeds on 60-75\%, which is substantially better. The success curve of \SQPbprop slightly lags those of \SQPimpl and \SQPdir due to the overhead of backpropagating through the steps of the interior point solver. See Appendix for five additional problem sizes, where overall the conclusions are the same.
Surprisingly, $\SQPimpl$ works slightly better than $\SQPbprop$ and $\SQPdir$ in problems with higher $D$. We observe similar performance on instances with equality constraints, where $\bG$ and $\bh$ also need to be learned (see Appendix). Note that each RS trial returns the best of (typically) thousands of $\bw$ settings evaluated during the time budget, all sampled uniformly from the same $\cW$ from which the `true' synthetic PLP was sampled. Most random (and thus initial) points do not satisfy~\eqref{eqn:IOP_outer}.

Learning $(\bc, \bA, \bb)$ directly, so that $\bw$ comprises all LP coefficients, results in a high-dimensional NLP problem (which is why, to date, the IO literature has focused on special cases of this problem, either with a single $\xt$ \citep{Chan18,Chan19} or fewer coefficients to learn \citep{Ghobadi20}). For example, an instance with $D\!=\!10, M_1\!=\!80$ has $890$ adjustable parameters. \SQPbprop, \SQPimpl and \SQPdir consistently achieve zero AOE training loss,  while RS and COBYLA consistently fail to make learning progress given the same time budget (see Appendix).

\begin{figure}[b]
\includegraphics[width=\textwidth]{Figure/fig_nguyen.pdf}\vspace{-.5em}
\caption{A visualization of minimum-cost paths (for simplicity) and minimum-cost multi-commodity flows (our experiment) on the Nguyen-Dupuis network. Sources $\{s_1, s_2, s_3, s_4\}$ and destinations $\{d_1, d_2, d_3, d_4\}$ are shown. At left are two example sets of training paths $\{(t_1, \xt_1), (t_2, \xt_2)\}$ alongside an example of a correctly predicted set of optimal paths under different conditions (different~$t$). At right is a visualization of a correctly predicted optimal flow, where color intensity indicates proportion of flow along arcs.  \label{fig:nguyen}}
\end{figure}

\begin{figure}[t]
\centering
    \begin{subfigure}{\textwidth}
      \centering
          \includegraphics[width=\linewidth]{Figure/fig_MCF_result_1e-05.pdf}
    \end{subfigure} \vspace{-.4em}
\caption{A comparison on minimum-cost multi-commodity flow instances, similar to Fig.~\ref{fig:exp_1a}. \label{fig:multicommodityResults}}
\end{figure}

{\bf Learning minimum-cost multi-commodity flow problems \;}
Fig.~\ref{fig:nguyen} shows a visualization of our experiment on the Nguyen-Dupuis graph \citep{Nguyen84}.
We learn a periodic arc cost $c_j(t, l_j, p_j) = l_j +  w_1 p_j + w_2l_j(\sin(2\pi(w_3+w_4t+w_5l_j))+1)$ and an affine arc capacity $b_j(l_j) = 1+ w_6 + w_7l_j$, based on global feature $t$ (time of day) and arc-specific features $l_j$ (length) and $p_j$ (toll price). To avoid trivial solutions, we set $\cW = \{\bw \ge \mathbf{0}, w_3+w_4+w_5 = 1\}$.
Results on 100 instances are shown in Fig.~\ref{fig:multicommodityResults}.
The SQP methods outperform RS and COBYLA in training and testing loss. From an IO perspective the fact that we are jointly learning costs and capacities  in a non-convex NLP formulation is already quite general. Again, for higher-dimensional parametrizations, we can expect the advantage of gradient-based methods to get stronger.

We report both the mean and median loss over the testing points in each trial. The difference in mean and median testing error is due to the presence of a few `outliers' among the test set errors. Fig.~\ref{fig:decisionsurface} shows the nature of this failure to generalize: the decision map $\bu \mapsto \xp$ of a PLP has discontinuities, so the training data can easily under-specify the set of learned models that can achieve zero training loss, similar to the scenario that motivates max-margin learning in SVMs. It is not clear what forms of regularization $r(\bw)$ will reliably improve generalization in IO. Fig.~\ref{fig:decisionsurface} also suggests that training points which closely straddle discontinuities are much more `valuable' from a learning perspective.
\begin{figure}
\hspace{-.5em}\includegraphics[width=1\textwidth]{Figure/fig_decision_surface.pdf}\\[-2em]
\small \phantom{~~~~~~~~~} (a) \hspace{1.33in} (b) \hspace{1.4in} (c)\vspace{.25em}
\caption{A failure to generalize in a learned PLP. Shown are the optimal decision map $\bu \mapsto \bx^*$ for a ground-truth PLP (a) and learned PLP (b) with the value of components $(\textcolor[rgb]{0.85,0,0}{x_1^*}, \textcolor[rgb]{0,0.7,0}{x_2^*})$ represented by red and green intensity respectively, along with that of a PLP trained on $\{\bu_1, \bu_2\}$. The learned PLP has no training error ($\text{SOE}\!=\!0, \text{AOE}\!=\!0$) but large test error ($\text{SOE}\!=\!.89, \text{AOE}\!=\!.22$) as depicted in~(c). (See Appendix for the specific PLP used in this example.) \label{fig:decisionsurface}\vspace{-1em}}
\end{figure}

config: arxiv


TITLE: Evaluate the flux of $F=\langle\sin(xyz), x^2y, z^2e^{x/5}\rangle$ through surface $S$ ... $4y^2+z^2=4, \space x\in [-2,2]$
QUESTION [1 upvotes]: I am trying to find the flux of  $\vec F=\langle\sin(xyz), x^2y, z^2e^{x/5}\rangle$ through the surface $S$ where $S$ consists of the elliptical cylinder defined by
$S$ ... $4y^2+z^2=4, \space x\in [-2,2]$
My first instinct is to parametarize the surface to get $\vec F \cdot \vec n$,
where
$$\vec r = \left\langle x,y,\pm \sqrt{1-y^2} \right\rangle$$
I get $$\vec n = \left\langle 0, \pm \frac{2y}{\sqrt{1-y^2}},1\right\rangle$$
so $$\vec F \cdot \vec n = \pm \frac{2x^2y^2}{\sqrt{1-y^2}} + 4(1-y^2)e^{x/5}.$$
I know that $x \in [-2,2]$ and $y \in \left[-\sqrt{1-\left(\frac{z}{2}\right)^2}, \sqrt{1-\left(\frac{z}{2}\right)^2} \right]$, and using a calculator I would be able to evaluate it, but with certain techniques the answer simplifies to
$$\frac{16\pi + 160 \sinh(2/5)}{3}.$$
I am not as familiar with integration involving hyperbolic functions and that is probably the reason why I am not seeing this.
Is there anyone that can confirm this fact?

REPLY [1 votes]: While you can apply divergence theorem, this one is quite straightforward for direct surface integral as well. Given it is a cylinder, it is easier to set up the integral in cylindrical coordinates. An elliptic cylinder with form $\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$ can be parametrized as $x = a \cos\theta, y = b \sin \theta, z$. Following the same parametrization but adjusting for the fact that axis of our cylinder is along $x-$axis instead of $z$.
We choose $r(t) = (x, \cos\theta, 2 \sin\theta)$, so you can find that $r'(t) = (0, 2\cos\theta, \sin\theta)$
So, $\vec{F} \cdot \vec{n} = (2x^2\cos^2\theta + 4\sin^3\theta)$. The integral becomes,
$\displaystyle \int_0^{2\pi} \int_{-2}^{2} (2x^2 \cos^2\theta + 4 \sin^3\theta e^{x/5}) \ dx \ d\theta$.
Please note that $\sin^3\theta$ is an odd function and over $(0,2\pi)$, its integral is zero. So all you are left with is to integrate $\displaystyle \int_0^{2\pi} \int_{-2}^{2} 2 x^2 \cos^2\theta \ dx \ d\theta$ which is a straightforward integral and the answer comes to $\frac{32\pi}{3}$.
Now coming to your working,
You should avoid parametrizing surface where you have $\pm$ sign and have to split the integral into two as we work with oriented surface and one will have to be very careful with orientation for both integral.
As far as the integral you have set up is not a hyperbolic integral. I am taking the plus sign part for example.
$\vec F \cdot \vec n = \frac{2x^2y^2}{\sqrt{1-y^2}} + 4(1-y^2)e^{x/5}$.
$x \in \mathbb{(-2,2)}$ is correct but $y \in \left[-\sqrt{1-\left(\frac{z}{2}\right)^2}, \sqrt{1-\left(\frac{z}{2}\right)^2} \right]$ is not correct as you have parametrized your surface in terms of $(x, y)$. So you have to just take limits of $y$ which is $y \in \mathbb{(-1,1)}$.
When we integrate wrt $x$, integral of $e^{x/5}$ is simply $5 e^{x/5}$ and between $-2, 2$, the integral comes to $5(e^{2/5} - e^{-2/5})$. Note that $\sinh({\frac{2}{5}}) = \frac{e^{2/5} - e^{-2/5}}{2}$ and hence the integral result can be written that way too.
$\int_{-1}^{1} \int_{-2}^{2} \frac{2x^2y^2}{\sqrt{1-y^2}} + 4(1-y^2)e^{x/5} \ dx \ dy = \frac{16\pi}{3} + \frac{160}{3} \sinh(\frac{2}{5})$
Similarly for $\vec{F} \cdot \vec{n} = - \frac{2x^2y^2}{\sqrt{1-y^2}} + 4(1-y^2)e^{x/5}$, you get the integral of $\frac{16\pi}{3} - \frac{160}{3} \sinh(\frac{2}{5})$
Adding both, you get $\frac{32\pi}{3}$.


TITLE: If null(AB) is a subset of null(A), does they have the same rank?
QUESTION [0 upvotes]: Let $A$ and $B$ be a square matrices.
If every solution to $AB_x=0$ is also a solution to $A_x=0$
then $rank(AB)$ = $rank(A)$.
I'm not sure if the logic is good here :
$AB_x=0 \;\;and\;\;A_x=0\; \Leftrightarrow$ $AB_x-A_x=0\Leftrightarrow (AB-A)_x=0\Leftrightarrow$ $null(AB)=null(A)$
$\Leftrightarrow$ $rank(AB)=rank(a)$
I'm not sure if $(AB-A)_x=0\Leftrightarrow$ $null(AB)=null(A)$

REPLY [2 votes]: First observe that for every pair of matrices $A, B$ we have
$$rank (AB) \leq rank (A).$$
In fact
$$rank (AB)=\dim(Im AB)=\dim (Im A_{|_{Im B}})\leq \dim (Im A)=rank (A).$$
On the other hand you have by hypothesis that
$$\ker (AB)\subseteq \ker(A).$$
In terms of dimensions it means
$$\dim (\ker AB)\leq \dim(\ker A),$$
and using the rank-nullity theorem you obtain
$$rank (AB)\geq rank (A),$$
hence the equality.


TITLE: How to find the angles in a bisected golden rectangle?
QUESTION [1 upvotes]: If you split a golden rectangle along the diagonal, you get a right triangle with sides of 1 and phi.  I’ve been trying to figure out what the angles in such a triangle would be.  Obviously, I can plug phi or 1/phi into the arctan function, but I’ve been trying to figure out if there is some clean multiple of pi that expresses those angles.
Any one have thoughts or suggestions on how to solve this?

REPLY [2 votes]: This is a comment that is too long to be fit in a comment.
This reddit thread: https://www.reddit.com/r/math/comments/9std3s/arctangent_of_two_and_the_golden_ratio/ contains a beautiful Proof Without Words of the result:
$$\arctan\left(\frac1\phi\right)=\frac {\arctan 2}2$$
By the result in [Is] ArcTan(2) a rational multiple of $\pi$? (where the answers actually extends the results and determine exactly when the arctan of a rational number is a rational multiple of $\pi$), we see that $\arctan 2$ is indeed NOT a rational multiple of $\pi$. Hence it follows that neither $\arctan (\phi)$ nor $\arctan (\phi^{-1})$ could be rational multiples of $\pi$. The may not be a full answer though, since "clean multiple" is subjective.


TITLE: Derangements: Probability that exactly $r$ players get their own name.
QUESTION [1 upvotes]: Suppose $n$ competitors in a tournament organize a sweep stake on the result of the tournament. Their names are placed in an urn, and each player pays a dollar to withdraw one name from the urn. The player holding the name that wins the tournament is awarded the pot of $n$.

(a) Show that the probability that exactly $r$ players draw their own name is $$\frac{1}{r!}\bigg\{ \frac{1}{2!} - \frac{1}{3!} + ... + \frac{(-1)^{n-r}}{(n-r)!}\bigg\}$$

This I understand and I can derive it.

(b) Given that exactly $r$ such matches occur, what is the probability that Fred draws his own name?

This I am struggling to answer. Fred is either part of the $r$ matches or he is not. This gives us an idea. I can condition on on Fred being part of the $r$: Let $F$ be the event that Fred draws his own name, $R$ be the event that exactly $r$ matches occur and $Q$ be the event that Fred is part of the group of matches.
$$P(F|R) = P(F|R,Q)P(Q) + P(F|R,Q^c)P(Q^c) = P(F|R,Q)P(Q)$$
I am a bit stumped here. As I have not achieved anything.

REPLY [0 votes]: @user2661923 gave a simple approach.  Here is an alternative approach that applies Bayes' Theorem and the result from part (a):
$$\mathbb{P}(F | R) = \frac{\mathbb{P}(R | F)\mathbb{P}(F)}{\mathbb{P}(R)}
= \frac{\frac{1}{(r-1)!}\left(\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^{(n-1)-(r-1)}}{((n-1)-(r-1))!}\right) \frac{1}{n}}{\frac{1}{r!}\left(\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^{n-r}}{(n-r)!}\right)} = \frac{r}{n}$$


TITLE: Hoffman Problem. Section 5, Problem 13.
QUESTION [3 upvotes]: Let  $\mathbb{R}$ be the field  of real  numbers,  and  let  D  be  a function  on  2x2  matrices over  $\mathbb{R}$,  with  values  in  $\mathbb{R}$,  such  that  $D(AB) = D(A)D(B)$  for  all  $A, B$.  Suppose also  that
$$D\begin{pmatrix} 0     & 1\\ 1 & 0 \end{pmatrix} \neq D\begin{pmatrix}
  1 & 0\\ 0 & 1 \end{pmatrix}$$
If we already know that:
$1.D(0)=0$
$2.D(A)=0$ if $A^2=0.$
$3.D(A)=-D(B)$ if $B$ is obtained  by interchanging  the  rows  (or  columns)
of  $A$.
Prove that:
(a) $D(A)=0$  if  one  row  (or  one  column)  of  $A$  is  $0$.
(b) $D(A)  =  0$  whenever $A$  is singular.

REPLY [5 votes]: Consider
$$D\left(\begin{bmatrix}
x&y\\
0&0
\end{bmatrix} \right) = D\left(\begin{bmatrix}
1&0\\
0&0
\end{bmatrix} \begin{bmatrix} x&y\\x&y\end{bmatrix}\right) = D\left(\begin{bmatrix}
1&0\\
0&0
\end{bmatrix}\right)D\left(\begin{bmatrix} x&y\\x&y\end{bmatrix}\right)$$
and use the fact that property (3) implies
$$D\left(\begin{bmatrix} x&y\\x&y\end{bmatrix}\right) = 0.$$
It should be easy to fill in the remaininig details from there.


TITLE: Indefinite integral $\int{3x^2\over (x^3+2)^4}dx$
QUESTION [2 upvotes]: Question:

How to solve this indefinite interal $$\int{3x^2\over (x^3+2)^4}dx$$

Attempt:
$3\int x^2{1\over (x^3+2)^4}dx$
Let $u=x^2$ then $du={1\over (x^3+2)^4}dx$.
Am I on the right track or going about it the wrong way?
ok so I make $du=3x^2dx$ but what do I do with this? Does it just disappear?

REPLY [2 votes]: The substitution $u = x^3 +2$ and $\mathrm{d}u = 3x^2 \, \mathrm{d}x$ giving $$\int \frac{1}{u^4} \, \mathrm{d}u = -\frac{1}{3u^3} = \bbox[10px, border: solid blue 1px]{-\frac{1}{3(x^3+2)^3} + \mathrm{C}}$$
is much more elegant and tractable than the substitution you proposed.


text:
\begin{document}

\begin{abstract}
It is known that the Kadison-Singer Problem (KS) and the Paving Conjecture
(PC) are equivalent to the Bourgain-Tzafriri Conjecture (BT).
Also, it is known that (PC) fails for $2$-paving projections with constant
diagonal $1/2$.  But the proofs of this fact are existence proofs.  We will use
variations of the discrete Fourier Transform matrices to construct
concrete examples of these projections and projections with constant diagonal
$1/r$ which are not $r$-pavable in a very strong sense.

In 1989, Bourgain and
Tzafriri showed that the class of
zero diagonal matrices with small entries (on the order
of $\le 1/log^{1+\epsilon}n$, for an $n$-dimensional Hilbert space) are
 {\em pavable}.  It has always been assumed that this result also
holds for the BT-Conjecture - although no one formally checked it.  We will
show that this is not the case.  We will show that if the BT-Conjecture is
true for vectors with small coefficients (on the order of $\le C/\sqrt{n}$)
then the BT-Conjecture is true and hence KS and PC are true.
 \\

\noindent {\sc Keywords.}  Kadison-Singer Problem, Anderson Paving Problem
Discrete Fourier Transform.\\
\noindent {\sc AMS MSC (2000).} 42C15, 46C05, 46C07.

\end{abstract}

\maketitle

\section{Introduction}

It is now known that the 1959 Kadison-Singer Problem is equivalent to fundamental
unsolved problems in a dozen areas of research in pure mathematics, applied
mathematics and engineering \cite{CT,CT1}.  In 1979, Anderson \cite{A} showed
that the Kadison-Singer Problem is equivalent to the {\em Paving Conjecture}.

\begin{paving conjecture}[PC]
For $\epsilon >0$, there is a natural number $r$ so
that for every
 natural number $n$ and
every linear operator
  $T$ on $l_2^n$
whose matrix has zero diagonal,
  we can find a partition (i.e. a {\it paving})
$\{{A}_j\}_{j=1}^r$
  of $\{1, \ldots, n\}$, such that
  $$
  \|Q_{{A}_j} T Q_{{A}_j}\|  \le  \epsilon \|T\|
  \ \ \ \text{for all $j=1,2,\ldots ,r$,}
  $$
  where $Q_{A_j}$ is the natural projection onto the $A_j$ coordinates of a vector.
\end{paving conjecture}

Operators satisfying the Paving Conjecture are called {\bf pavable operators}.
A projection $P$ on $\cH_n$ is {\bf $(\epsilon,r)$-pavable} if there
is a partition $\{A_j\}_{j=1}^r$ of $\{1,2,\ldots,n\}$ satisfying
\[ \|Q_{A_j}PQ_{A_j}\| \le \epsilon,\ \ \mbox{for all $j=1,2,\ldots,r$}.\]

It was shown in \cite{CE} that  projections with
constant diagonal $1/r$ are not $(r,\epsilon)$-pavable for any $\epsilon >0$.
But the argument in \cite{CE} is an existence proof and the actual matrices failing
paving were not known.  In this note we will construct concrete examples of
these projections.  As a consequence, we will obtain a stronger result than that
of \cite{CE}.  The main question now is whether this construction can be
generalized to produce a counter-example to KS.

\begin{notation}
Throughout this paper, if $\cH_n$ is an n-dimensional Hilbert space, then
$\{e_i\}_{i=1}^n$ denotes a fixed orthonormal basis for $\cH$.
\end{notation}

It was shown \cite{CT} that BT is equivalent to PC.
Our construction of non-2-pavable projections starts with
a construction of non-2-Riesable sequences (See Section \ref{section2}
for the definitions).     The vectors we will produce have very small coefficients,
on the order of $1/\sqrt{n}$ for an $n$-dimensional Hilbert space.  However,
conventional wisdom indicates that we cannot construct a counter-example
to PC out of vectors with small coefficients.  So next, we will show that
conventional-wisdon has been wrong for the last 20 years and a counter-example
to BT exists in general if and only if it exists for matrices with coefficients on the
order of $1/\sqrt{n}$.  Conventional wisdom came from a result of Bourgain and
Tzafriri \cite{BT,BT1} where they showed that the Paving Conjecture has a positive solution
for the class of zero diagonal matrix operators $A = (a_{ij})_{i,j=1}^n$
on $\mathbb H_n$ with small coefficients.  In particular, a matrix is
pavable if the coefficients satisfy for some
$\epsilon >0$,
\[ |a_{ij}|\le \frac{C}{log^{1+\epsilon}n}.\]

It has always been assumed that the corresponding result holds for BT if
\[ |Te_i(j)|\le \frac{C}{log^{1+\epsilon}n},\ \ \mbox{for all $i,j=1,2,\ldots,n$}.\]

We will show that this is not the case.
This is the second main theorem of this paper (See Section \ref{section2} for
the definitions).

\begin{theorem}\label{J1}
The following are equivalent:

(1)  The Bourgain-Tzafriri Conjecture is true.

(2)  There are constants $\delta$ and $r\in \NN$ so that for every $C>0$ there is an
$N_0$ so that for every $N\ge N_0$ if $\{f_i\}_{i=1}^{2N}$ is a unit norm 2-tight frame
for $\cH_N$ satisfying
\[ |f_i(j)|\le \frac{C}{\sqrt{2N}},\]
then $\{f_i\}_{i=1}^{2N}$ is $(\delta,r)$-Rieszable.
\end{theorem}

\section{Preliminaries}\label{section2}

We will actually work with an equivalent form of the Paving Conjecture for
projections with constant diagonal.
In 1989, Bourgain and Tzafriri proved one of the most celebrated theorems in analysis:
The {\em Bourgain-Tzafriri Restricted Invertibility Theorem} \cite{BT}.  This gave rise to
a major open problem in analysis.

\begin{bourgain-tzafriri}[BT]\label{CBST1}
There is a universal constant $A>0$ so that
for every $B>1$ there is a natural number $r=r(B)$
satisfying:
For any natural number $n$,
if $T:{\ell}_2^n \rightarrow {\ell}_2^n$ is a linear operator
with $\|T\|\le B$ and $\|Te_{i}\|=1$ for all $i=1,2,\ldots , n$,
 then there is a partition
$\{A_{j}\}_{j=1}^{r}$ of $\{1,2,\ldots , n\}$ so that
for all $j=1,2,\ldots ,r$ and
 all choices of scalars $\{a_{i}\}_{i\in A_{j}}$ we have:
$$
\|\sum_{i\in A_{j}}a_{i}Te_{i}\|^{2}\ge A \sum_{i\in A_{j}}|a_{i}|^{2}.
$$
\end{bourgain-tzafriri}

It was shown in \cite{CT} that BT is equivalent to the Paving Conjecture.

\begin{definition}
A family of vectors $\{f_i\}_{i=1}^M$ for an $n$-dimensional Hilbert space $\cH_n$ is
$(\delta,r)$-{\bf Rieszable} if there is a partition $\{A_j\}_{j=1}^r$ of
$\{1,2,\ldots,M\}$ so that for all $j=1,2,\ldots,r$ and all scalars $\{a_i\}_{i\in A_j}$
we have
\[ \|\sum_{i\in A_j}a_if_i\|^2 \ge \delta \sum_{i\in A_j}|a_i|^2.\]
A projection $P$ on $\cH_n$ is $(\delta,r)$-{\bf Rieszable} if $\{Pe_i\}_{i=1}^n$
is $(\delta,r)$-Rieszable.
\end{definition}

Recall that a family of vectors $\{f_i\}_{i\in I}$ is a {\bf frame} for a Hilbert space
$\cH$ if there are constants $0<A,B < \infty$, called the {\bf lower  (upper)
frame bounds)} respectively satisfying for all $f\in \cH$:
\[ A \|f\|^2 \le \sum_{i\in I}|\langle f,f_i\rangle |^2 \le B\|f\|^2.\]
If $\|f_i\|=\|f_j\|$ for all $i,j$, we call this an {\bf equal norm} frame and if
$\|f_i\|=1$ for all $i$, it is a {\bf unit norm frame}.
If $A=B$ this is an {\bf $A$-tight frame} and if $A=B=1$, it is a {\bf Parseval frame}.
It is known \cite{C,CK,Ch} that $\{f_i\}_{i\in I}$ is an $A$-tight frame if and only if
the matrix with the $f_i's$ as rows has orthogonal columns and the
square sums of the column coefficients equal $A$.  It is also known
\cite{C,Ch} that $\{f_i\}_{i=1}^M$ is a Parseval frame for $\cH_n$ if and only if there is an
othogonal projection $P:\ell_2^M \rightarrow \cH_n$ with
\[ Pe_i = f_i,\ \ \mbox{for all $i=1,2,\ldots,M$},\]
where $\{e_i\}_{i=1}^M$ is the unit vector basis of $\ell_2^M$.

The following result  can be found in \cite{CE,T}.

\begin{proposition}\label{prop1}
Fix a natural number $r\in \NN$.  The following are equivalent:

(1)  The class of projections with constant diagonal $1/r$ are pavable.

(2)  The class of projections with constant diagonal $1/r$ are Rieszable.

(3)  The class of unit norm $r$-tight frames $\{f_m\}_{m=1}^{nr}$ for $\cH_n$ are
Rieszable.
\vskip12PT
Moreover, the Paving Conjecture is equivalent to (1)-(3) holding for some
$r\in \NN$.
\end{proposition}

We will construct concrete counterexamples for (4) of Proposition \ref{prop1}
for the case $r=2$.  These will give
concrete counterexamples to 1-3 in the proposition by the following result which
can be found in \cite{CE}.  The point here is that the proof of this proposition gives
an explicit representation of each of the equivalences in the proposition in terms
of all the others.

\begin{proposition}
Let $P$ be an orthogonal projection on $\cH_n$ with matrix $B = (a_{ij})_{i,j=1}^n$.
The following are equivalent:

(1)  The vectors $\{Pe_i\}_{i=1}^n$ is $(\delta,r)$-Rieszable.

(2)  There is a partition $\{A_j\}_{j=1}^r$ of $\{1,2,\ldots,n\}$ so that
for all $j=1,2,\ldots,r$ and all scalars $\{a_i\}_{i\in A_j}$ we have
\[ \|\sum_{i\in A_j}a_i(I-P)e_i\|^2 \le (1-\delta)\sum_{i\in I}|a_i|^2.\]

(3)  The matrix of $I-P$ is $(\delta,r)$-pavable.
\end{proposition}

As a fundamental tool in our work, we will work with the $n\times n$
discrete Fourier transform matrices which we will just call DFT matrices
or $DFT_{n\times n}$.   For these, we fix $n\in \NN$ and let $\omega$ be a
primative $n^{th}$ root of unity and define
\[ DFT_{n\times n} = \left ( \frac{1}{\sqrt{n}}\omega^{ij}\right )_{i,j=1}^n.\]

The main point of these $DFT_{n\times n}$
matrices is that they are unitary matrices for which the modulus of all of
the entries of the matrix are equal to 1.  We will use on the following simple observation.

\begin{proposition}\label{prop5}
If $A=(a_{ij}\}_{i,j=1}^n$ is a matrix with $|a_{ij}|^2=a$ for all $i,j$ and
orthogonal columns and we multiply the
$j^{th}$-column of $A$ by a constant $C_j$ to get a new matrix $B$, then

(1)  The columns of $B$ are orthogonal.

(2)  The square sums of the coefficients of any row of $B$ all equal
\[a \sum_{j=1}^n C_j^2.\]

(3)  The square sum of the coefficients of the $j^{th}$ column of $B$ equal
$aC_j^2$.
\end{proposition}

\section{The Bourgain-Tzafriri Conjecture for $r$=2}

Let us first outline our construction.
For any natural number $n$, we will alter two $2n \times 2n$ DFT matrices
along the lines of Proposition \ref{prop5} and then stack them on top
of one another to get a $4n\times 2n$ matrix with the following
properties:

(1)   Each altered DFT has the square sums of the
coefficients of any row equal to 1.

(2)  The top altered DFT will have the square sums of the coefficients of each
column $j$ with $1\le j\le n-1$ equal to 2, and the square sums of the
coefficients of the remaining columns will all equal $2/(n+1)$.

(3)  The combined matrix will have the square sums of the coefficients of each
column equal to 2.

(4)  The columns of the combined matrix are orthogonal.

It follows that this is the matrix of a unit norm $2$-tight frame and hence multiplying the matrix by
$1/\sqrt{2}$ will turn it into an equal norm Parseval frame, creating the matrix of a
rank $2n$ projection
on ${\mathcal C}^{4n}$ with constant diagonal $1/2$.  We will then show that the rows
of this class of matrices are not uniformly $2$-Rieszable to complete the example.

So we start with a $2n\times 2n$ DFT and multiply the first $n-1$ columns
by $\sqrt{2}$ and the remaining columns by $\sqrt{\frac{2}{n+1}}$
to get a new matrix $B_1$.
Now, we take the second $2n\times 2n$ DFT matrix and multiply the first
$n-1$ columns by $0$ and the remaining columns by $\sqrt{\frac{2n}{n+1}}$ to get a
matrix $B_2$.  We form the matrix $B$ by stacking the matrices $B_1$ and $B_2$
on top of one another to get the matrix $B$ given below.

\begin{center}
\begin{tabular}{|c|c|}
\hline (n-1)-Colmns & (n+1)-Colmns.\\
\hline $\sqrt{2}$ & $\sqrt{\frac{2}{n+1}}$  \\
\hline 0 & $\sqrt{\frac{2n}{n+1}}$  \\
\hline
\end{tabular}
\end{center}
\vskip12pt

Now we can prove:

\begin{proposition}
The matrix $B$ satisfies:

(1)  The columns are orthogonal and the square sum of the coefficients of
every column equals 2.

(2)  The square sum of the coefficients of every row equals 1.

The row vectors of the matrix $B$ are not $(\delta,2)$-Rieszable, for any
$\delta$ independent of $n$.
\end{proposition}

\begin{proof}
Clearly the columns of $B$ are orthogonal.  To check the square sums of the
column coefficients, recall that for columns $1\le \ell \le n-1$ the modulus
of all the coefficients of $B_1$ are $\frac{1}{\sqrt{n}}$, the the coefficients of $B_2$
are 0.  So the square sum of the coefficients in column $\ell$ are:
\[ \frac{1}{n}\cdot 2n + 0 = 2.\]
For the columns $n\le \ell \le 2n$, the modulus of the coefficients of $B_1$ are
$\frac{1}{\sqrt{n(n+1)}}$ and the coefficients of $B_2$ are $\frac{1}{\sqrt{n+1}}$.
So the square sum of the coefficients of $B$ in column $\ell$ are:
\[ 2n \cdot \frac{1}{n(n+1)} + 2n \cdot \frac{1}{n+1} = \frac{2}{n+1} + \frac{2n}{n+1} = 2.\]

Now we check the row sums.  For any row of $B_1$, the first $n-1$ column coefficients
have modulus $\frac{1}{\sqrt{n}}$, and the modulus of the coefficients of the last
$n+1$ columns of $B_1$ have modulus $\frac{1}{\sqrt{n(n+1)}}$.  So the square sum of the
coefficients of any row of $B_1$ are:
\[ (n-1)\frac{1}{n} + (n+1)\frac{1}{n(n+1)} =1.\]
For any row of $B_2$, the first $n-1$ column coefficients are equal to 0 and the
remaining $n+1$ column coefficients have modulus $\frac{1}{\sqrt{n+1}}$.  So the
square sum of the row coefficients of $B_2$ are
\[ (n+1)\frac{1}{n+1} + 0 = 1. \]

We will now show that the row vectors of $B$ are not two Rieszable.
So let $\{A_1,A_2\}$ be a partition of $\{1,2,\ldots,4n\}$.  Without loss of generality,
we may assume that $|A_1 \cap \{1,2,\ldots,2n\}| \ge n$.    Let the row vectors of the matrix $B$
be $\{f_i\}_{i=1}^{4n}$ as elements of ${\mathcal C}^{2n}$.  Let $P_{n-1}$ be
the orthogonal projection of ${\mathcal C}^{2n}$ onto the first $n-1$ coordinates.
Since $|A_1|\ge n$, there are scalars $\{a_i\}_{i\in A_1}$
so that $\sum_{i\in A_1}|a_i|^2 = 1$ and
\[ P_{n-1}\left ( \sum_{i\in A_1}a_if_i \right ) = 0.\]  Also, let $\{g_j\}_{j=1}^{2n}$ be
the orthonormal basis consisting of the original rows of the $DFT_{2n\times 2n}$.
We now have:
\begin{eqnarray*}
\| \sum_{i\in A_1}a_if_i\|^2 &=&\|(I-P_{n-1})\left ( \sum_{i\in A_1}a_if_i \right )\|^2\\
&=& \frac{2}{n+1}\|(I-P_{n-1})\left ( \sum_{i\in A_1}a_ig_i\right ) \|^2\\
&\le& \frac{2}{n+1}\|\sum_{i\in A_1}a_ig_i\|^2\\
&=& \frac{2}{n+1}\sum_{i\in A_1}|a_i|^2\\
&=& \frac{2}{n+1}.
\end{eqnarray*}
Letting $n\rightarrow \infty$, we have that this class of matrices is not $(\delta,2)$-pavable
for any $\delta >0$.
\end{proof}

\section{The Bourgain-Tzafriri Conjecture for general $r$}

In this section we will extend our construction to projections with constant diagonal
$1/r$ and actually prove a stronger result.

\begin{proposition}\label{prop10}
For every natural number $r\ge 2$, there is a $r^2n \times rn$ projection matrix with constant
diagonal $1/r$ so that whenever we partition $\{1,2,\ldots,r^2n\}$ into sets $\{A_j\}_{j=1}^r$,
and for all $k=1,2,\ldots,r$, if $D_k = \{(k-1)rn+1,(k-1)rn+2,\ldots, krn\}$,
then for every $k=1,2,\ldots,r-1$, there is a $j$ so that the vectors $\{f_i\}_{i\in A_j \cap D_k}$
are not uniformly $2$-Rieszable.
\end{proposition}

This time, we will take $r$ DFT matrices of size $rn \times rn$ and alter their columns
by certain amounts so that when we stack them on top of one another
to get a matrix $B$ of size $r^2n \times rn$ satifying:
\vskip10pt
1.  The columns of $B$ are orthogonal and the sums of the
squares of the coefficients of each row of $B$ equals 1.
\vskip10pt
2.  The sums of the squares of the coefficients of each column of $B$ equals $r$.
\vskip10pt
3.  $B$ satisfies the requirements of the proposition.
\vskip10pt
For the first matrix $B_1$ we take the $rn\times rn$ DFT and multiply the first
$n-1$ columns by $\sqrt{r}$
and the remaining columns by $\sqrt{\delta_1}$ (to be chosen later).
For $B_2$ we take the $rn\times rn$ DFT and multiply the first $n-1$ columns
by 0, multiply the columns $n-1+j$, $j=1,2,\ldots,n-1$ by $\sqrt{r - \delta_1}$,
and multiply the remaining columns by $\sqrt{\delta_2}$ (to be chosen later).
And for $k=3,\ldots, r-1$ we construct the matrix $B_k$ by
taking the $rn \times rn$ DFT and multiplying  the first
$(k-1)(n-1)$ columns by 0, multiply the columns $(k-1)(n-1)+j$ for $j=1,2,\ldots,n-1$ by
\[ \sqrt{r - \sum_{i=1}^{k-1}\delta_{k-1}},\]
 and multiplying the remaining columns by $\sqrt{\delta_k}$ (to be chosen later).
 Finally, for $B_r$ we take the $rn\times rn$ DFT and multiplying the first
 $(r-1)(n-1)$ columns by 0 and the remaining columns by $\sqrt{\delta_r}$
 (to be chosen later).

We then stack these $r$, $rn\times rn$ matrices $\{B_k\}_{k=1}^r$ on top of each other
to produce the matrix $B$ for which the moduli
of the coefficients of $B$ are given in figure 2 below.  Now we must show that the matrix
$B$ has all of the properties of Proposition \ref{prop10}.

It is clear that the columns of $B$ are orthogonal.
To show that the square sums of the row coefficients of the matrix $B$ are all equal to 1,
we need a lemma.

\begin{lemma}\label{lem1}
To get the rows of the matrix $B$ to square sum to 1,
we need
\begin{equation}\label{E3}
 \delta_k = \frac{r^2n}{[(r-k+1)n+k-1][(r-k)n+k]}.
 \end{equation}
\end{lemma}

\begin{proof}
We will proceed by induction on $k$ to show Equation \ref{E3} for
all $k=1,2,\ldots, r$.  For $k=1$, we observe that the coefficients
of the first $n-1$ columns of $B_1$ have modulus equal to $1/n$,
while the coefficients of the remaining $rn-(n-1)$ columns of $B_1$ have modulus
$\sqrt{\frac{\delta_1}{rn}}$.  So the sum of the squares of the coefficients of any
row of $B_1$ equals
\[ \frac{1}{rn}\left [ r(n-1)+\delta_1(rn-(n-1)) \right ] = 1.\]
Hence,
\[ \delta_1(rn-(n-1)) = rn -r(n-1) = r.\]
So,
\[ \delta_1 = \frac{r}{(r-1)n+1}= \frac{r^2n}{[(r-1+1)n+1-1][(r-1)n+1]|}.\]
For $k=2$, our matrix $B_2$ has coefficients of the first $n-1$ columns equal to 0,
coefficients of the columns $(n-1)+j$, $j=1,2,\ldots,n-1$ have modulus equal to
\[ \sqrt{\frac{r-\delta_1}{rn}}.\]
 and the remaining $rn-2(n-1)$ columns have modulus equal to $\sqrt {\frac{\delta_2}{rn}}$.
So the square sums of the coefficients of any row of $B_2$ equals
\[ \frac{1}{rn}\left [ (n-1)(r-\delta_1)+ (rn-2(n-1))\delta_2\right ] = 1.\]
Since
\[ r-\delta_1 = r-\frac{r}{(r-1)(n+1)} = \frac{r(r-1)n}{(r-1)n+1},\]
we can solve the equation to get
\[ \delta_2 = \frac{r^2n}{[(r-1)n+1][(r-2)n+2]}.\]

Now assume our formula holds for any $k\le r-1$ and we check it for $k+1$.
The matrix $B_{k+1}$ has coefficients of the first $k(n-1)$ columns equal to 0,
coefficients of the columns $k(n-1)+j$, $j=1,2,\ldots,n-1$ of modulus
\[ \left ( \frac{r- \sum_{j=1}^k \delta_k }{rn}\right )^{1/2},\]
and the coefficients of the remaining columns have modulus $\sqrt{\frac{\delta_{k+1}}{rn}}$.
It follows that the square sums of the row coefficients of the matrix $B_{k+1}$ must
satisfy
\begin{equation}\label{E2} \left ( r-\sum_{j=1}^k \delta_j \right )(n-1) + \delta_{k+1} [ rn-(k+1)(n-1)] = rn.
\end{equation}
Hence, letting $a = rn/(n-1)$ we have
\begin{eqnarray*}
\sum_{j=1}^{k}\delta_j &=& r^2n\sum_{j=1}^k \frac{1}{[r-j+1)n + j-1][(r-j)n+j]}\\
&=& \frac{r^2n}{(n-1)^2} \sum_{j=1}^k \frac{1}{(a+1-j)(a-j)}\\
&=& \frac{r^2n}{(n-1)^2} \sum_{j=1}^k \left ( \frac{1}{a-j}-\frac{1}{a-(j-1)} \right )\\
&=& \frac{r^2n}{(n-1)^2} \frac{1}{a-k}-\frac{1}{a-0}\\
&=& \frac{r^2n}{(n-1)^2}\frac{k}{a(a-k)}\\
&=& \frac{r^2kn}{rn(rn-k(n-1))}\\
&=& \frac{rk}{(r-k)n+k}.
\end{eqnarray*}
Combining this with Equation \ref{E2} we have
\begin{eqnarray*}
\delta_{k+1} &=& \frac{r+(n-1)\sum_{j=1}^k \delta_j}{rn-(k+1)(n-1)}\\
&=& \frac{r+(n-1) \left ( \frac{rk}{(r-k)n+k}\right ) }{(r-k+1)n+k-1}\\
&=& \frac{r[(r-k)n+k] + (n-1)rk}{[(r-k+1)n+k-1][(r-k)n+k]}\\
&=& \frac{r^2n-rkn+rk+rnk-kr}{[(r-k+1)n+k-1][(r-k)n+k]}\\
&=& \frac{r^2n}{[(r-k+1)n+k-1][(r-k)n+k]}.
\end{eqnarray*}
\end{proof}

By Lemma \ref{lem1}, we know that the rows of the matrix $B$ square sum to 1.
Now we need to check the column sums.  Most of this is true by our definitions.
We check two cases:
\vskip12pt
\noindent {\bf Case 1}:
For a column $\ell = k(n-1)+j$, $k=1,2,\ldots,r-1$,  the column coefficients
for $1\le j \le k-1$ and $i = jrn+m$, $m=1,2,\ldots,rn$, have
modulus $\sqrt{\frac{\delta_j}{rn}}$, and for $i=krn+m$, $m=1,2,\ldots,rm$ the modulus
of the coefficients are $\sqrt{\frac{r-\sum_{j=1}^{k-1}\delta_j}{rn}}$, and all other
coefficients are 0.  Hence, the square sum of the column coefficients is
\[ rn \sum_{j=1}^{k-1}\frac{\delta_j}{rn} + rn \left ( \frac{r-\sum_{j=1}^{k-1}\delta_j}{rn} \right )
= r.\]
\vskip12pt

\noindent {\bf Case 2}:  For a column $\ell = (r-1)(n-1)+j$, with $j=1,2,\ldots rn-(r-1)(n-1) =
r+n-1$, the square sum of the coefficients of column $\ell$ are (using our formula for the
sum of the $\delta_k$ above):
\[ \sum_{k=1}^r \delta_k = \frac{r^2}{(r-r)n+r} = r.
\]
\vskip12pt
Finally, we need to show that our matrix $B$ is not pavable (with paving
constants independent of $n$) in the strong sense given
in the proposition.  This follows similarly to the $DFT_{2n\times 2n}$ case.  Let $\{f_i\}_{i=1}^{r^2n}$
be the rows of the matrix $B$ and let $\{g_i\}_{i=1}^{rn}$ be the rows of the DFT
matrix.  Also, let $P_k$ be the orthogonal projection of ${\mathcal C}_2^{rn}$ onto
the first $k(n-1)$ coordinates.
Now let $\{A_j\}_{j=1}^r$ be a partition of $\{1,2,\ldots,r^2n\}$ and
fix $1\le k \le r-1$.  Then there is a $j$ so that $|A_j \cap D_k|\ge n$.  Since
the vectors $\{f_i\}_{i\in A_j\cap D_k}$ have zero coordinates for all
$j=1,2,\ldots,(k-1)(n-1)$, and there are scalars $\{a_i\}_{i\in A_j\cap D_k}$ satisfying

1.  $\sum_{i\in A_j\cap D_k}|a_i|^2 =1$.

2.  We have
\[ P_{k}\left ( \sum_{i\in A_j\cap D_k}a_if_i \right ) =0.\]

It follows from our construction that
\begin{eqnarray*}
\|\sum_{i\in A_j\cap D_k}a_if_i\|^2 &=& \|(I-P_k)\left (\sum_{i\in A_j\cap D_k}a_if_i\right )\|^2\\
&=& \delta_k \|(I-P_k)\left ( \sum_{i\in A_j\cap D_k}a_ig_i\right )\|^2\\
&\le& \delta_k \|\sum_{i\in A_j \cap D_k}a_jg_j\|^2\\
&=& \delta_k \sum_{i\in A_j\cap D_k}|a_i|^2\\
&=& \delta_k
\end{eqnarray*}
Since $\lim_{n\rightarrow \infty}\delta_k =0$, it follows that our family of matrices are
not $2$-Rieszable in the strong sense of the Proposition.  This argument looks pictorially
as:
\vskip12pt

Each square is a $rn \times (n-1)$ submatrix
\vskip12pt
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline $\sqrt{\frac{r}{rn}}$ & $\sqrt{\frac{\delta_1}{rn}}$ & $\sqrt{\frac{\delta_1}{rn}}$ & $\cdots$ & $\sqrt{\frac{\delta_1}{rn}}$ \\
\hline 0 & $\sqrt{\frac{r}{rn}}$ & $\sqrt{\frac{\delta_2}{rn}}$ & $\cdots$ & $\sqrt{\frac{\delta_2}{rn}}$ \\
\hline 0 & 0 & $\sqrt{\frac{r}{rn}}$ & $\cdots$ & $\sqrt{\frac{\delta_3}{rn}}$ \\
\hline $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ \\
\hline 0 & 0 & 0 & $\cdots$ & $\sqrt{\frac{\delta_r}{rn}}$ \\
\hline
\end{tabular}
\end{center}

\vskip12pt
The main question is whether it is possible to take the concrete constructions in this
paper and generalize them to give a complete counterexample to the Paving Conjecture.

\section{The Proof of Theorem \ref{J1}}

\begin{proof}
$(1)\Rightarrow (2)$:  This is from Proposition \ref{prop1}.

$(2)\Rightarrow (1)$:  Let $P$ be a projection with constant diagonal $1/2$ on
${\mathcal H}_{2N}$.  So $\{\sqrt{2}Pe_i\}_{i=1}^{2N}$ is a unit norm 2-tight frame
for ${\mathcal H}_{2N}$.  Let $A$ be the $N\times N$ matrix with row vectors
$\{\sqrt{2}Pe_i\}_{i=1}^{2N}$.  Define recursively,

\[ A_1 =  \frac{1}{\sqrt{2}}\begin{bmatrix} A & A\\
A & -A
\end{bmatrix}\]
and
\[
A_{K+1} = \frac{1}{\sqrt{2}}\begin{bmatrix}
A_K & A_K\\
A_K & -A_K
\end{bmatrix} \]

\noindent {\bf Note}:  Each $A_K$ (their rows) is a unit norm 2-tight frame for
${\mathcal H}_{2^K N}$.  Since the columns of $A_K$ are orthogonal, this implies that
the columns of $A_{K+1}$ are orthogonal.  Also, clearly the sums of the
squares of the row elements are still one
and the sums of the squares of the column elements are still one.
\vskip12pt

Also, the entries $(a_{i,j})$ of $A_K$ satisfy
\begin{equation}\label{eqn1}
|a_{i, j}|\le \frac{1}{\sqrt{2^K}} = \frac{\sqrt{N}}{\sqrt{2^K N}}.
\end{equation}
Letting $C = \sqrt{N}$ in $(2)$ of the theorem, there is some $N_0$ such that
for every $L\ge N_0$, if $\{f_i\}_{i=1}^{2L}$ is a unit norm 2-tight frame for
${\mathcal H}_{L}$ with
\[ |f_{i,j}|\le \frac{C}{\sqrt{2L}},\]
then $\{f_i\}_{i=1}^{2L}$ is $(\delta,r)$-Rieszable.  Hence, for $K$ large enough,
Equation \ref{eqn1} has this inequality.  So, $A_K$ is $(\delta,r)$-Rieszable.
That is, there is a partition $\{A_j\}_{j=1}^r$ of $\{1,2,\ldots,2^K N\}$ so that
for every $j=1,2,\ldots,r$ and all scalars $\{a_i\}_{i\in A_j}$ we have
\[ \|\sum_{i\in A_j}a_if_i\|^2 \ge \delta \sum_{i\in A_j}|a_i|^2,\]
where $\{f_i\}$ are the row vectors of $A_K$.  Let
\[ B_j = A_j \cap \{1,2,\ldots,N\}.\]
Then $\{B_j\}_{j=1}^r$ is a partition of $\{1,2,\ldots,N\}$.  Now we compute,
\begin{eqnarray*}
\delta &\le& \|\sum_{i\in B_j}a_if_i\|^2\\
&=&\frac{1}{2^K}\sum_{\ell =1}^{2^K}\|\sum_{i\in B_j}a_i \sum_{j=1}^N f_{i,\ell+j}\|^2\\
&=& \frac{1}{2^K}\cdot 2^K \|\sum_{i\in B_j}a_i\sqrt{2}Pe_i\|^2\\
&=&  \|\sum_{i\in B_j}a_i\sqrt{2}Pe_i\|^2.
\end{eqnarray*}
Hence, $A$ is $(\delta,r)$-Rieszable and hence KS holds by Proposition \ref{prop1}.
\end{proof}

\begin{remark}  The above points out that there really is a major difference
between ``paving" and ``Rieszing".  Recall that if $\{f_i\}_{i=1}^M$
is a set of vectors, the {\em Grammian} of this family is the
$M\times M$ matrix $(\langle f_i,f_j\rangle )$.  In the above construction, if $G_A$ is the
Grammian of the row vectors $A$ then the Grammian of of the row vectors of $A_K$ is
\[
\begin{bmatrix}
G_A & 0 & 0 & \cdots\\
0 & G_A & 0 & \cdots\\
0 & 0 & G_A & \cdots\\
\vdots & \vdots & \vdots & \ddots
\end{bmatrix}\]
That is, the coefficients of the Grammian do not get smaller in this construction while
the coefficients of the matrix do get smaller.
\end{remark}

\begin{remark}
This result also says that passing results on paving from the Grammian
back to the matrix and the other way do not hold in general.
\end{remark}

\vskip12pt
\noindent {\bf Acknowledgments}
\vskip10pt
Casazza and Tremain were supported by NSF DMS 0704216 and 1008183, Fickus was supported by AFOSR F1ATA09125G003.  The views expressed in this article are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the U.S. Government.


TITLE: I have a problem with reaching the required result using Taylor Expansions.
QUESTION [1 upvotes]: I do not know how to get the result in the rhs. I know a few things about Taylor Expansions but I do not know how to get the extra term. I would really appreciate if someone could show me a step-by-step method on how to get to the result in the RHS.
Thank you!

REPLY [1 votes]: The variable is $u=\sqrt{\Delta t}$, and the expression can be re-written as
$$\mathrm e^{\bigl(r-\tfrac{\sigma^2}2\bigr)u^2+\sigma u}.$$
Taylor's expansion at order $2$ of $\mathrm e^x$ is $\;1+x+\dfrac{x^2}2+o(x^2)$, so we substitute $\bigl(r-\tfrac{\sigma^2}2\bigr)u^2+\sigma u$ to $x$ in this formula
$$\Bigl[\Bigl(r-\frac{\sigma^2}2\Bigr)u^2+\sigma u\Bigr]^2=\Bigl(r-\frac{\sigma^2}2\Bigr)^{\!2}u^4+2\sigma\Bigl(r-\frac{\sigma^2}2\Bigr)u^3+\sigma^2 u^2=\sigma^2 u^2+o(u^2).$$
So we obtain
$$1+\Bigl(r-\frac{\sigma^2}2\Bigr)u^2+\sigma u+\frac12\sigma^2 u^2+o(u^2)=1+\sigma u+ru^2+o(u^2).$$


TITLE: Is restriction a closed map?
QUESTION [6 upvotes]: Originally asked on MSE.
Let $X$ be a normal (or even metrizable) topological space and let $Y$ be a closed subset of $X$. Let $C(X)$ be the linear space of all continuous scalar functions on $X$ endowed with the compact-open topology. Consider a map $R:C(X)\to C(Y)$ defined by $Rf=f|_Y$. This map is obviously linear, and it is easy to see that it is continuous. By Tietze theorem it is also surjective. It seems that this is in fact a quotient map. However, what interests me is the following question:

Let $B$ be a closed convex balanced subset of $C(X)$. Is $RB$ closed in $C(Y)$?

Under additional assumption that $B$ is weakly compact, this is true, since then $B$ is compact in the pointwise topology, and so $RB$ is pointwise compact, and so pointwise closed, and so closed in $C(Y)$. I can also show that this is wrong if we don't require $Y$ to be closed in $X$.

REPLY [7 votes]: The answer to the main question is negative:
Consider the compact subset $X=[0,1]\cup \{2\}$ of the real line and let $Y=\{2\}$ be a singleton in $X$. In the function space $C(X)$ consider the closed convex balanced subset
$$B:=\{f\in C(X):\sup_{x\in [0,1]}|f(x)|\le 1,\;f(0)=0,\;f(2)=\int_0^1 f(t)dt\}.$$ It is easy to see that for the restriction operator $R:C(X)\to C(Y)$, the image  $R(B)=\{f\in C(Y):|f(2)|<1\}$ is not closed in $C(Y)$.


TITLE: Is there a way to save electricity from lightning?
QUESTION [1 upvotes]: Possible Duplicate:
Can the lightning be captured and used as power source?

Each lightning contains several kilo volts of electricity.
Saving them could be a boon to soaring need of it.
Is there a way?

REPLY [3 votes]: Tesla investigated the possibility of using the potential built up in the atmosphere. It's not clear how far he got with this. In principle it's possible, but in practice it doesn't seem likely anyone could make it economically viable.
You would need to build a large capacitor with one side grounded and the other positioned up in the clouds where atmospheric electricity can change it. Assuming you could manage this you can certainly generate power by discharging the capacitor. However the engineering challenges are, shall we say, formidable!


TITLE: Form of solutions of Diophantine equation
QUESTION [0 upvotes]: Consider the following Diophantine equation $$zx^2  +xy^2 +yz^2  =xyzt .$$
Is that true that all solutions of this equation are of the form $(x,y,z,t) =(a^2 b ,b^2 c ,c^2 a ,t)$ for some $a,b,c\in\mathbb{N}$?

REPLY [0 votes]: This need not be true. We have the solution $(x,y,z,t)=(7,7,7,3)$, and $7=a^2b=b^2c=c^2a$ gives first $a=1$ and $b=7$ from $a^2b=7$, but also $c=1$ and $a=7$ from $c^2a=7$, a contradiction.


TITLE: page $102$ from Ahlfors.
QUESTION [0 upvotes]: He talks about a function $f(a)$ for which all the derivatives vanish. He shows inside a circle within our domain $\Omega$, for any circle $C$ we take, there $f$ is identicaly zero.
Then he shows that $f$ is identically zero in $\Omega$. Let $E_1$ be the set where $f$ and all its derivatives vanish, and $E_2$ be the set on which the function or one of the derivatives is nonzero. Then $E_1$ is open because for any $x\in E_1$, we can just get a circle within which the function vanish. Now $E_2$ is also open, and the reason he gives is because the function and all derivatives are continuous. Im not sure why $E_2$ is open.  $f$ is analytic hence continuous, so around any point $x\in E_2$, we have a smaller ball within which $f$ is continuous?

REPLY [2 votes]: Let $x_0\in E_2$,say $f^{(n)}(x_0)\ne 0$. As $f^{(n)}$ is continuous, the set $\{\,x\in \Omega \mid f^{(n)}(x)\ne 0\,\}$ is open (and contains $x_0$).


text:
\section{Summary}

The goal of this investigation was two-fold: first, to develop and extend models of motion to study the third-body perturbation. Second, to verify how these can contribute to on-going research into low-energy trajectories, periodic orbits and their application in innovative concepts, such as asteroid capture missions.

The accurate modelling of the space environment is essential for every space mission. The utilisation of simplified models of motion, like the two-body problem, may be detrimental to particular mission designs. Additional disturbing accelerations can be greatly felt by the spacecraft in the form of third-body effects, which must be accounted for even when well outside the sphere of influence of a body. These effects can yet be exploited in order to obtain lower-cost trajectories.

However, the use of higher-order models to accurately convey the third-body effect and other disturbing accelerations can be quite expensive and time-consuming, especially when characterising the orbit in terms of rotating reference frames. For preliminary mission design, when a very large number of trajectories is computed and considered, lower-fidelity models can be used wisely, provided they are constrained by certain accuracy standards.

This document highlights existing low-fidelity models for the computation of the third-body effect and proposes four other novel ones. All of these are based on perturbation methods where the third-body effect is either described using accelerations or a disturbing function. The necessity of creating many methodologies comes from the possible application scenarios, which range from real-time computations to long-term propagations and mapping. The accuracy of these models is \textcolor{Internal}{generally} shown to be very similar to the CR3BP in the depicted mission design studies; in contrast, the computational cost was established to be much lower.

After developing the models of motion for the third-body perturbation, the related targetting methods were developed, together with tools to obtain low-energy and low-thrust trajectories. These allowed the exploration of the third-body effect for specific mission design cases. In particular, the perturbation of the Earth is used to reduce the capture trajectory costs in so-called Earth-resonant trajectories. This was achieved by concluding that the phasing of the spacecraft with the Earth is the main factor that determines the disturbing effect on the motion. Therefore, by moving the spacecraft accordingly, its relative phasing can be controlled and exploited. These findings were applied to asteroid capture missions, where several bodies were identified as adequate candidates for retrieval. Namely, six NEAs (targets 2016 RD34, 2012 TF79, 2011 MD, 2017 FJ3, 2017 BN93 and 2010 VQ98) yielded a very large increase in retrievable mass with respect to the state of the art. Thus, these trajectories may become valuable options for asteroid capture mission design: either for making larger targets accessible, or for lowering the fuel cost when retrieving smaller bodies.

\section{Recommendations}

By extending the analysis completed in this investigation, additional insights may be obtained into some of the covered topics. Recommendations for continuing this investigation include:

\begin{description}
	\item[On the Keplerian third-body potential and its applications:] this disturbing function and the related models of motion, both for conservative and non-conservative forces, have shown great promise in the depiction of the third-body perturbation. The computational \textcolor{External}{speed} of all the derived models can be improved by coding them in a lower-level language or improving the orbital propagation equations. Furthermore, since these models are based on the Lagrange planetary equations and Gauss' variational equations, the singularities related to the use of orbital elements can be resolved for an overall better model.

	\textcolor{Internal}{The Hamiltonian used to derive the K3BP is written as a Taylor expansion with $\mathpzc{O}(\mu^2)$. The equation can be developed such that higher-order terms are included. Some preliminary studies were made on this part, but no interesting increases in accuracy were achieved. However, this idea may be especially valuable for systems of greater gravitational parameter than the Sun-Earth one.}

	In terms of application scenarios, the provided computation of the third-body perturbation can be useful in several different mission designs. The case of Jovian and Saturnian moon tours, in which a spacecraft is subject to varied gravitational perturbations simultaneously, is one of them. Another would be the disposal of spacecraft at the end of life, by doing long-term propagation to guarantee that the object always remains at a minimum distance from the Earth.

	\item[On Earth-resonant capture missions:] the option to perform Earth encounters to decrease the capture $\Delta v$ opens a wide range of possibilities for mission design. One of them is to increase the number of Earth encounters: it is predicted that, when this value increases, the $\Delta v$ can be even further minimised. This would, however, increase the time taken by the trajectory immensely. A strategy to make the mission shorter could be to investigate the application of the $\Delta v_M$ manoeuvre when the spacecraft is closer to the asteroid, and not so many orbital periods before they meet.

	Regarding the trajectory computation, the estimation using the filter can be further improved by using alternative ways to compute the manoeuvre, such as analytical Lambert arcs. This would possibly remove outliers, in order to obtain a more consistent list of target bodies.

	The presented multi-fidelity framework for nearly-resonant encounters has similar potential applications to the previous point: from moon exploration missions to planetary protection analysis, amongst others.

	\item[On the computation of periodic orbits:] given that this is a preliminary study on the subject, many topics are left to explore. The main one is the definition of \textit{Figure of Merit} and the conditions for a periodic orbit to exist in a mapping model. \textcolor{Both}{One metric that could better validate the usage of the LCLM and provide a nice tuning for the $FM$ would be the comparison with a list of known periodic orbits in the CR3BP. These orbits would be characterised by their semi-major axis and eccentricity, and could therefore be plotted on the LCLM to understand if their existence matches the high-likelihood regions of the latter.}

	The LCLM can be expanded so the initial states for the grid search include more orbital values and are extended to the spatial case ($i \neq 0$) or the asymmetrical case ($\nu \neq 0$). Furthermore, a differential correction process and a continuation method can both be implemented to further build the orbital families found in the PAP-KM. Although unlikely, other orbital types that are not represented in the Hill's problem may be found. Finally, the achieved corrected orbits can be used for mission design and exploration, or to compute low-energy trajectories connecting periodic orbits of the Solar System.
\end{description}


text:
\begin{document}
\title[Centralizer]
{Trivial centralizers for codimension-one attractors}
\author{Todd Fisher}
\address{Department of Mathematics, Brigham Young University, Provo, UT 84602}
\email{tfisher@math.byu.edu}
\thanks{}

\subjclass[2000]{37C05, 37C20, 37C29, 37D05, 37D20}
\date{November 2, 2007}
\keywords{Commuting diffeomorphisms, hyperbolic set, attractors}
\commby{}

\begin{abstract}
 We show that if $\Lambda$ is a codimension-one hyperbolic attractor for a $C^r$ diffeomorphism $f$, where $2\leq r\leq \infty$, and $f$ is not Anosov, then there is a neighborhood $\mathcal{U}$ of $f$ in $\mathrm{Diff}^r(M)$ and an open and dense set $\mathcal{V}$ of $\mathcal{U}$ such that any $g\in\mathcal{V}$ has a trivial centralizer on the basin of attraction for $\Lambda$.    \end{abstract}

\maketitle

\section{Introduction}

Let $f\in\mathrm{Diff}^r(M)$ be a $C^r$ diffeomorphism where $M$ is a connected compact manifold  without boundary.  The {\it centralizer} of $f$, denoted $Z(f)$, is the set of all diffeomorphisms that commute with $f$:
 $$Z(f)=\{g\in\mathrm{Diff}^r(M)\,|\, fg=gf\}.$$ Note that the set $Z(f)$ contains  all powers of $f$.
 The set $Z(f)$ forms a group under composition.   We say $f$ has {\it trivial centralizer} if  $Z(f)=\{f^n\, |\, n\in\mathbb{Z}\}$.   A diffeomorphism with trivial centralizer has no smooth symmetries.  Smale~\cite{Sma2, Sma} asked the following question concerning the frequency of diffeomorphisms with trivial centralizer.

\begin{que}\label{q.smale}
Let $1\leq r\leq \infty$, $M$ be a smooth, connected, compact, boundaryless manifold, and $T$ be the set of all $f\in\mathrm{Diff}^r(M)$ such that $f$ has trivial centralizer.
\begin{enumerate}
\item  Is $T$ dense in $\mathrm{Diff}^r(M)$?
\item Is $T$ residual in $\mathrm{Diff}^r(M)$?
\item Does $T$ contain an open and dense subset of $\mathrm{Diff}^r(M)$?
\end{enumerate}
\end{que}

There are a number of partial results to the above question.  A few of the results are the following:
\begin{itemize}
\item   Kopell~\cite{Kop1} shows that $T$ contains an open and dense set if  $M=S^1$ and $r=\infty$.  \item Palis and Yoccoz~\cite{PY1} show there is an open and dense set of $C^{\infty}$ Axiom A diffeomorphisms with the strong transversality property and a periodic sink that have a trivial centralizer.
\item In~\cite{Fis2} it is shown that there is a residual set of $C^\infty$ Axiom A diffeomorphisms with the no cycles property with trivial centralizer.  Additionally, for a surface and $2\leq r\leq\infty$  it is shown that there exists an open and dense set of $C^r$ Axiom A diffeomorphisms with the no cycles property whose elements have trivial centralizer.
\item Burslem~\cite{Bur} shows that for certain classes of $C^{\infty}$ partially hyperbolic diffeomorphisms there is a residual set with trivial centralizer.
\item Bonatti, Crovisier, and Wilkinson~\cite{BCW1} have shown that $C^1$ diffeomorphisms contain a residual set with trivial centralizer.
\item Bonatti, Crovisier, Vago, and Wilkinson~\cite{BCW} are able to show that on any manifold there is a open set in $\mathrm{Diff}^1(M)$ containing a dense set whose elements do not have a trivial centralizer.
\end{itemize}

One approach to Question~\ref{q.smale} is to examine the centralizer of a diffeomorphism restricted to the basin of attraction for an attractor.  This is the approach used in~\cite{PY1} and ~\cite{Fis2}.  The next theorem addresses this approach in the case of codimension-one attractors.

\begin{thm}\label{t.codimone}
If $\Lambda$ is a codimension-one hyperbolic attractor for a $C^r$
diffeomorphism $f$ where $2\leq r\leq \infty$ and $f$ is not Anosov, then there exists a neighborhood $\mathcal{U}$ of $f$ in
$\mathrm{Diff}^r(M)$ and an open and dense set $\mathcal{V}$ of $\mathcal{U}$ such that for all $g\in \mathcal{V}$ and $h\in Z(g)$
the map $h|_{W^s(\Lambda(g))}=g^n|_{W^s(\Lambda(g))}$ where $\Lambda(g)$ is the
continuation of $g$.
\end{thm}

We note that the novelty of the above theorem is that $r$ can be taken less than infinity and the the fact that $\mathcal{V}$ is open.  The above result will also hold for codimension-one hyperbolic repellers.

Two cases where we can apply the above result to the entire manifold are for certain structurally stable diffeomorphisms and quasi-Anosov diffeomorphisms of $3$-manifolds.

A function $f$ is {\it structurally stable} if there exists a neighborhood $\mathcal{U}$ of $f$ such that for each $g\in \mathcal{U}$ there exists a topological conjugacy from $f$ to $g$.  From the work of Grines and Zhuzhoma~\cite{GZ} on non-Anosov structurally stable diffeomorphisms with a codimension-one attractor we know in this case that the basin of attraction of the hyperbolic attractor is dense in the manifold.  We then have the following corollary.

\begin{cor} If $f$ is a structurally stable, non-Anosov, $C^r$ diffeomorphism where $2\le r\leq \infty$, and contains a codimension-one attractor, then there exists a neighborhood $\mathcal{U}$ of $f$ in $\mathrm{Diff}^r(M)$ and an open and dense set $\mathcal{V}$ of $\mathcal{U}$ whose elements have a trivial centralizer.
\end{cor}

A diffeomorphism $f$  is {\it expansive} if there exists a constant $c>0$  such that for any two distinct points $x$ and $y$ there exists an integer $n$ where $d(f^n (x),f^n(y))\geq c$.  The definition is independent of the metric, although the constant $c$ in general depends on the metric.
A diffeomorphism $f$ is {\it quasi-Anosov} if there exists a neighborhood $\mathcal{U}$ of $f$ such that each $g\in \mathcal{U}$ is expansive.
For quasi-Anosov diffeomorphisms we will show the next corollary follows from results in~\cite{FRH} and Theorem~\ref{t.codimone}.

\begin{cor} \label{c.2} If $\mathrm{dim}(M)=3$, then there is a $C^r$ open and dense set of $C^r$ non-Anosov quasi-Anosov diffeomorphisms of $M$ where $2\leq r\leq \infty$ whose elements have a trivial centralizer.
\end{cor}

From the above results the next question is a natural weakening of   Question~\ref{q.smale} part (3).
\begin{que}
If $2\leq r\leq \infty$, then does $T$ contain an open and dense subset of $\mathrm{Diff}^r(M)$?
\end{que}

\section{Background}

We now review some basic definitions and facts about hyperbolic attractors and commuting diffeomorphisms.
We assume that all of our maps are diffeomorphisms of a manifold to itself.

A compact set $\Lambda$ invariant under the action of $f$ is {\it
hyperbolic} if there exists a splitting of the  tangent space
$T_{\Lambda}f=\mathbb{E}^u\oplus \mathbb{E}^s$ and positive
constants $C$ and $\lambda<1$ such that, for any point
$x\in\Lambda$ and any $n\in\mathbb{N}$,
$$
\begin{array}{llll}
\| Df_{x}^{n}v\|\leq C \lambda^{n}\| v\|,\textrm{ for }v\in
E^{s}_x \textrm{, and}\\
\| Df_{x}^{-n}v\|\leq C \lambda^{n}\| v\|,\textrm{ for }v\in
E^{u}_x. \end{array}
$$

For $\epsilon>0$ sufficiently small and $x\in \Lambda$ the
\textit{local stable and unstable manifolds} are respectively:
$$
\begin{array}{llll}
W_{\epsilon}^{s}(x,f)=\{ y\in M\, |\textrm{ for all }
n\in\mathbb{N}, d(f^{n}(x), f^{n}(y))\leq\epsilon\},\textrm{
and}\\
W_{\epsilon}^{u}(x,f)=\{ y\in M\, |\textrm{ for all }
n\in\mathbb{N}, d(f^{-n}(x), f^{-n}(y))\leq\epsilon\}.
\end{array}$$
The \textit{stable and unstable manifolds} are respectively:
$$
\begin{array}{llll}
W^s(x,f)=\bigcup_{n\geq 0}f^{-n}\left(
W_{\epsilon}^s(f^n(x),f)\right) ,\textrm{ and}\\
W^u(x,f)=\bigcup_{n\geq
0}f^{n}\left(W_{\epsilon}^u(f^{-n}(x),f)\right). \end{array}
$$
For a $C^r$ diffeomorphism the stable and unstable manifolds of a hyperbolic set are $C^r$
injectively immersed submanifolds.

A useful property is the following standard result.

\begin{thm}(Structural stability of hyperbolic sets) Let $f\in \mathrm{Diff}(M)$ and $\Lambda$ be a hyperbolic set for $f$.  Then for any neighborhood $V$ of $\Lambda$ and every $\delta>0$ there exists a neighborhood $\mathcal{U}$ of $f$ in $\mathrm{Diff}(M)$ such that for any $g\in \mathcal{U}$ there is a hyperbolic set $\Lambda_g\subset V$ and a homeomorphism $h:\Lambda_g\rightarrow \Lambda$ with $d_{C^0}(\mathrm{id},h) + d_{C^0}(\mathrm{id},h^{-1})<\delta$ and $h\circ g|_{\Lambda_g}=f|_{\Lambda}\circ h$.  Moreover, $h$ is unique when $\delta$ is sufficiently small.
\end{thm}

Many of the results in this paper will follow from looking at the basins of attractors and repellers.  We now give some basic properties of these sets.

A set $X\subset M$ has an {\it attracting neighborhood} if there
exists a neighborhood $V$ of $X$ such that
$X=\bigcap_{n\in\mathbb{N}}f^n(V)$.
If $X$ is a compact
set of a smooth manifold $M$ and $f$ is a continuous map from $M$
to itself, then $f|_X$ is {\it transitive} if for any open
sets $U$ and $V$ of $X$ there exists some $n\in\mathbb{N}$ such
that $f^n(U)\cap V\neq\emptyset$.
A set $\Lambda\subset M$
is called a {\it hyperbolic attractor}
if $\Lambda$ is a transitive hyperbolic set for a diffeomorphism
$f$ with an attracting neighborhood.  The {\it basin of attraction} for a hyperbolic attractor $\Lambda$ is the set
$$W^s(\Lambda)=\{x\in M\, |\, d(f^n(x), \Lambda)\rightarrow 0\textrm{ as }n\rightarrow\infty\}.$$
A standard result is that if $p$ is a periodic point contained in a hyperbolic attractor $\Lambda$, then
$$W^s(\Lambda)\subset \overline{W^s(\mathcal{O}(p))}.$$

We now review some basic properties of commuting diffeomorphisms.
Let $f$ and $g$ be commuting diffeomorphisms.  Let
$\mathrm{Per}^n(f)$ be the periodic points of period $n$ for $f$
and $\mathrm{Per}^n_h(f)$ denote the hyperbolic periodic points in
$\mathrm{Per}^n(f)$.  If $p\in\mathrm{Per}^n(f)$, then
$g(p)\in\mathrm{Per}^n(f)$ so $g$ permutes the points of
$\mathrm{Per}^n(f)$.  Furthermore, if
$p\in\mathrm{Per}^n(f)$, then
$$T_{g(p)}f^nT_pg=T_pgT_pf^n.$$
Hence, the linear maps $T_{g(p)}f^n$ and $T_pf^n$ are similar.
Since $\#(\mathrm{Per}^n_h(f))<\infty$ it
follows that if $p\in\mathrm{Per}^n_h(f)$, then $g(p)\in\mathrm{Per}(g)$.  If $p\in\mathrm{Per}^n_h(f)$, then
$$g(W^u(p,f))=W^u(g(p),f)\textrm{ and }g(W^s(p,f))=W^s(g(p),f).$$

\section{Trivial centralizer for codimension-one attractors}

Let $p$ denote a periodic point in a codimension-one attractor.  The proof of Theorem~\ref{t.codimone} will depend on a linearization of $W^s(p)$ to the reals.  Since $f$ is in $\mathrm{Diff}^r(M)$ where $2\leq r\leq\infty$ we know there exists a $C^2$ immersion $\phi$ of $W^s(p)$ such that $F=\phi f\phi^{-1}\in \mathrm{Diff}^r(\mathbb{R})$ fixing the origin.  The following result due to Sternberg will then help $C^1$ linearize the map $F$.

\begin{thm}~\cite{Ste} Let $f$ be a $C^r$ monotone increasing function defined in a neighborhood of the origin in $\mathbb{R}$ where $2\leq r\leq\infty$ and $|f'(0)|=a\neq 0,1$.  Then there exists a function $g$ that is a $C^{r-1}$ monotone increasing function with $C^{r-1}$ inverse defined in a neighborhood of the origin in $\mathbb{R}$ such that $g^{-1} f g(x)=ax$ for all sufficiently small $x$ in $\mathbb{R}$.
\end{thm}

As the function $F$ above is defined on all of $\mathbb{R}$ and globally contracting we will want the following corollary to the result of Sternberg.

\begin{cor}\label{c.linear} Let $f\in\mathrm{Diff}^r(\mathbb{R})$ be a contraction mapping fixing the origin where $2\leq r\leq\infty$ and $|f'(0)|=a\neq 0,1$.  Then there exists a function $g$ in $\mathrm{Diff}^{r-1}(\mathbb{R})$ such that $g^{-1} f g(x)=ax$ for all  $x$ in $\mathbb{R}$.
\end{cor}

For the proof of the corollary one simply takes the $C^{r-1}$ linearizing function defined in a neighborhood of the origin given by Sternberg and extends to all of the reals through iteration.  Since
the map is a contraction mapping this can be extended to all of the reals.\\

\noindent{\bf Proof of Theorem~\ref{t.codimone}.}
Let $f$ be a diffeomorphism and $\Lambda$ a codimension-one hyperbolic attractor.  By the structural  stability of hyperbolic sets there exists an open set $\mathcal{U}$ of $f$ in $\mathrm{Diff}^r(M)$ such that for all $g\in \mathcal{U}$ there is a continuation $\Lambda(g)$ of $\Lambda$.  Since $\Lambda$ is a transitive locally maximal hyperbolic set the periodic points are dense, see~\cite[p. 574]{KH1}.

From~\cite{GZ} there exists a periodic point $p\in\Lambda$, called a periodic boundary point such that $W^s(p)\cap\Lambda$ is a Cantor set in one of the separtrices and the empty set in the other.   Furthermore, the map $f|_{W^s(p)\cap \Lambda}$ is invariant so $f|_{W^s(p)}$ is orientation preserving.

For simplicity we assume that $p$ is a fixed point, we leave the details of $p$ a periodic point to the reader.
We let $\mathcal{V}$ be an open and dense set  in $\mathcal{U}$ such that if $g\in\mathcal{V}$ and $q$ and $q'$ are hyperbolic fixed points of $g$, then $T_{q}g$ is not similar to $T_{q'}g$.  Hence, if $g\in \mathcal{V}$ and $h\in Z(g)$, then $h(p(g))=p(g)$.

The proof of Theorem~\ref{t.codimone} will follow from examining $W^s(p)$ since this is dense in $W^s(\Lambda)$.
The set $W^s(p)$ is a $C^2$ immersed copy of $\mathbb{R}$ where the map $\psi:W^s(p)\rightarrow\mathbb{R}$ is the immersion with $\psi(p)=0$.  Then the map $G=\psi g\psi^{-1}$ is a $C^2$ contracting diffeomorphism of the reals fixing the origin and $G'(0)=a\in(0,1)$ (since $G$ is orientation an orientation preserving contraction).
From Corollary~\ref{c.linear} there exists a map $\phi\in\mathrm{Diff}^1(M)$ such that $(\phi G\phi^{-1})(x)=ax$.

The next lemma will show $h|_{W^s(p)}$  is also $C^1$ linearized by $\Phi=\phi\psi$.

\begin{lem}\label{l.commutereals}~\cite[p. 61]{KH1}  Any $C^1$ map defined on a neighborhood of the origin on the real line and commuting with a linear contraction is linear.
\end{lem}

Let $L=\Phi g\Phi^{-1}$ and $H=\Phi h\Phi^{-1}$.  We now show that $LH=HL$ for  all $x$.
$$
\xymatrix{
\mathbb{R}\ar[d]_{\Phi^{-1}}\ar[r]^{L} &  \mathbb{R}\ar[d]^{\Phi^{-1}}\\
W^s(p(g))\ar[d]_{h}\ar[r]^{g} & W^s(p(g))\ar[d]^{h}\\
W^s (p(g))\ar[d]_{\Phi}\ar[r]^{g} & W^s (p(g))\ar[d]^{\Phi}\\
\mathbb{R}\ar[r]_{L} & \mathbb{R}}
$$
Since $L$ is linear and $H$ is $C^1$ we know from the previous lemma that $H$ is linear.

To complete the proof of Theorem~\ref{t.codimone} we show there exists an open and dense set $\mathcal{V}'$ in $\mathcal{V}$ such that for each $g\in \mathcal{V}'$ and $h\in Z(g)$ we have $h|_{W^s(p(g))}=g^n|_{W^s(p(g))}$ for some $n$.
Since $W^s(p(g))$ is dense in $W^s(\Lambda)$ we see that $h|_{W^s(\Lambda)}=g^n|_{W^s(\Lambda)}$.  To construct the set $\mathcal{V}'$  we perturb the Cantor sets on one separatrix of $W^s(p(g))$ so that the only linear maps that commute with $L$ are powers of $L$.

Define $C=\Phi(W^s(p)\cap\Lambda)$.  So $C$ is a Cantor set in the reals.  We may assume that $C\subset[0,\infty)$.   A {\it gap} of $C$ is a connected component of $\mathbb{R}-C$.  A bounded gap is a bounded component.

\begin{figure}[htb]
\begin{center}
\psfrag{x}{$x$}
\psfrag{y}{$y$}
\psfrag{l}{$L(U)$}
\psfrag{z}{$L(x)$}
\psfrag{w}{$L(y)$}
\psfrag{1}{$U_1$}
\psfrag{2}{$U_2$}
\psfrag{n}{$U_n$}
\psfrag{u}{$U$}

\includegraphics{gaps2.eps}
\caption{Gaps between $U$ and $L(U)$}\label{f.gaps1}
\end{center}
\end{figure}

Let $U$ be a bounded gap in $C$ with boundary points $0<x<y<\infty$.    Let $U_1,...U_n$ be the gaps of size at least size
$L(U)$ contained in the interval $[L(y),x]$ and $x_i<y_i$ be the boundary points of gap $U_i$ for $1\leq
i\leq n$ where $x_i<x_{i+1}$ for all $1\leq i<n$.  We know there exists some $k\in\mathbb{Z}$ such that $L^kH(x)\in [L(x), x)$.  Furthermore, we know that $C$ is $H$ invariant so $L^kH(x)\in C$ and $L^kH(U)$ is a gap of $C$ contained in $[L(x), x)$.  Since $L^kH$ is a linear map we know the size of $L^kH(U)$  by the image of $x$ under $L^kH$.  Additionally, $L^kH(U)$ is  contained in $[L(x), x)$ and the linearization implies that the size of $L^kH(U)$ is at least that of $L(U)$.  Hence, $L^kH(U)$ is either $L(U)$ or one of the set $U_1,...,U_n$.

If $L^kH(U)=U_i$, then $x_i/x=y_i/y$ is the contraction constant of $L^kH$.  By an arbitrarily small perturbation of $g$ we can ensure that $x_i/x\neq y_i/y$ for all $1\leq i\leq n$.
Indeed, let $W=\Phi^{-1}([0, y])\subset W^s(p(g))$ and $V$ be a neighborhood of $W$ and $\epsilon>0$ such that $$V\cap \bigcup_{i=1}^nB_{\epsilon}(g^{-1}\Phi^{-1}(y_i))=\emptyset.$$  Then there exists an arbitrarily small perturbation of $g$ with support in $\bigcup_{i=1}^nB_{\epsilon}(g^{-1}\Phi^{-1}(y_i))$ that does not change the linearization of $W$ and ensures that $x_i/x\neq y_i/y$ for all $1\leq i\leq n$.

Furthermore, this will be an open condition since $L$ varies continuously with $g$.
Hence, $L^kH(U)=L(U)$ and $H$ is a power of $L$ showing that $h|_{W^s(\Lambda)}=g^{1-k}|_{W^s(\Lambda)}$.
$\Box$\\

\noindent{\bf Proof of Corollary~\ref{c.2}.}  From~\cite{FRH} we know that for every quasi-Anosov diffeomorphism of a 3-manifold there is an open and dense set of points in the manifold contained in the basin of a codimension-one attractor or repeller.

Let $QA^r(M)$ be the set of quasi-Anosov diffeomorphisms on a manifold $M$ that are non-Anosov.
Since each quasi-Anosov diffeomorphism is Axiom A with no cycles~\cite{Man1} we know from Proposition 3.2 in~\cite{Fis2} that there is an open and dense set $\mathcal{U}$ in $QA^r(M)$ such that for each  $f\in\mathcal{U}$ and $\Lambda$ and $\Lambda'$ are attractors for $f$ where $$\overline{W^s(\Lambda)}\cap \overline{W^s(\Lambda')}\neq\emptyset,$$ then there exists a hyperbolic repeller $\Lambda_r$ such that $$W^s(\Lambda)\cap W^u(\Lambda_r)\neq\emptyset\textrm{ and }W^s(\Lambda')\cap W^u(\Lambda_r)\neq\emptyset.$$

From Theorem~\ref{t.codimone} there exists an open and dense set $\mathcal{V}\subset \mathcal{U}$ such that if $f\in\mathcal{V}$, $\Lambda$ a codimension-one hyperbolic attractor or repeller of $f$, and $g\in Z(f)$, then $g|_{W^s(\Lambda)}=f^n|_{W^s(\Lambda)}$ if $\Lambda$ is an attractor or $g|_{W^u(\Lambda)}=f^n|_{W^u(\Lambda)}$ if $\Lambda$ is a repeller where $n\in\mathbb{Z}$.

Let $f\in\mathcal{V}$, $\Lambda_a$ be a codimension-one hyperbolic attractor for $f$, $\Lambda_r$ be a codimension-one repeller for $f$, $W^s(\Lambda_a)\cap W^u(\Lambda_r)\neq \emptyset$, and $g\in Z(f)$.  Let $$g|_{W^s(\Lambda_a)}=f^n|_{W^s(\Lambda_a)}\textrm{ and  }g|_{W^u(\Lambda_r)}=f^m|_{W^u(\Lambda_r)}.$$  Suppose that  $m\neq n$.  Then
$$g'=f^{-n}g\in Z(f)\textrm{ and }g'|_{W^s(\Lambda_a)}=\mathrm{id}|_{W^s(\Lambda_a)}.$$
Let $x\in W^s(\Lambda_a)\cap W^u(\Lambda_r)$.  Then
$$g'(x)=x=f^{m-n}(x).$$  Hence, $x$ is periodic for $f$, a contradiction.  Therefore, we know for each $f\in \mathcal{V}$ there is an open and dense set $U\subset M$ such that if $g\in Z(f)$, then $g|_U=f^n|_U$.  This follows from Proposition 3.2 in~\cite{Fis2}.  Hence, for each $f\in\mathcal{V}$ and $g\in Z(f)$ we have $g=f^n$. $\Box$

\bibliographystyle{plain}
\bibliography{commute012808}

\end{document}


TITLE: equivalence of implications
QUESTION [2 upvotes]: I've got a little trouble with logic.
I'm reading a book about mathematics, and as an example for implication there is:
$$  x > 3 \implies x>0$$
So, if $x$ is bigger than $3$, it implies that it is bigger than zero, okay.
But in general, we say:
$$a \implies b = \overline b \implies \overline a $$
and
$$ \overline{x > 3} = x \underline < 3$$
so if $x$ is not bigger than $3$, it is equals to or less than $3$. all fine here. But this means also that:
$$ x > 3 \implies x>0 = x \underline < 0 \implies x \underline < 3$$
Okay, but I read it as: if $x$ is smaller or equals to $0$, it is smaller or equals to $3$. But if it is already smaller than $3$, how can it be equals $3?$
Seems not very logic to me :)

REPLY [4 votes]: $x \leq 0 \implies x \leq 3$ is a true statement.
$x\leq 3$ means $x\lt3$ or $x=3$. So, as long as $x<3$ remains true, $x\leq 3$ also remains true. In the same way, $1\leq1$ or $2\leq 3$ are also true statements.
In general, $P\implies P \vee Q$ is a tautology.


TITLE: How does standard random variable have variance of 1?
QUESTION [1 upvotes]: Let X be a discrete random variable and define $Z = \cfrac{X - \mu_x}{\sigma_x}=\cfrac{1}{\sigma_x} \cdot X - \cfrac{\mu_x}{\sigma_x}$ which is a linear transformation of $X$.
How do you get a variance of 1 assuming this?  I tried working it out but couldn't get it.  I am stuck on the last step:
$\mu_z=E[Z] = \cfrac{\mu_x}{\sigma_x} - \cfrac{\mu_x}{\sigma_x} =0$
$Z^2 = \left(\cfrac{X-\mu_x}{\sigma_x}\right)^2= \cfrac{X^2}{\sigma_x^2} - \cfrac{-2 X \mu_x}{\sigma_x^2} + \cfrac{\mu_x^2}{\sigma_x^2} $
$E[Z^2] = \cfrac{1}{\sigma_x^2}(E[X^2] - 2 E[X] \mu_x + \mu_x^2)$
$E[Z^2] = \cfrac{1}{\sigma_x^2}(E[X^2] -E[X]^2)$
By defn:
$\sigma_z^2 = E[Z^2] - E[Z]^2=E[Z^2]=\cfrac{1}{\sigma_x^2}(E[X^2] -E[X]^2)$
I see $E[X]^2 = \sigma_x^2$ but how do you simplify $E[X^2]$?  Thank you in advance.

REPLY [1 votes]: As $\sigma_x^2 = E[X^2] - E[X]^2$ by definition of $\sigma_x$, you have in your computation of $E[Z^2]$, that
$$ E[Z^2] = \frac 1{\sigma_x^2} \bigl(E[X^2] - E[X]^2\bigr) = 1 $$
So $\sigma_z^2 = E[Z^2] - E[Z]^2 = 1 - 0^2 = 1$.

REPLY [0 votes]: When dealing with variances, as we know that for a random variable X
$$ \operatorname{Var} (X + c) = \operatorname{Var}(X) $$
for any constant $c \in \Bbb R$, we see that without loss of generality we may assume that $\mu_x = 0$ and hence
$$ \operatorname{Var}(Z) = \operatorname{Var} \left( \frac{X}{\sigma_x}\right)= \frac{1}{\sigma_x^2} \operatorname{Var}(X) = \frac{\sigma_x^2}{\sigma_x^2} = 1$$
While I'm aware this doesn't address your method directly, I would think that this is a much easier way of going about it - you don't have to find the variance directly from the distribution of $Z$, and instead you can just use the properties of the variance.