TITLE: Find positive fractions so that $k_1+k_2+...+k_n+k_{n+1} \leq 1/2^n$?
QUESTION [0 upvotes]: I'm working on a proof in topology and the only thing left to do is some combinatorics (number theory?), which I've never had any exposure to.  I would appreciate any help I can get.
I'm attempting to choose positive fractions $k_1,k_2,...,k_n,k_{n+1}$ so that, $k_1 < 1/2^2, k_2 < 1/2^2, k_3 < 1/2^3, k_4 < 1/2^4,...,k_n < 1/2^n, k_{n+1} < 1/2^{n+1}$ and so that,
$k_1+k_2+...+k_n+k_{n+1}  \leq 1/2^n$.
P.S. Help with tagging if this isn't a number theory question.
EDIT: I need to define the sequence $k_1,k_2,...$ first.  I wish to define it so that each $k_i$ is small enough to ensure two properties;
(1) $k_1 < 1/2^2, k_2 < 1/2^2, k_3 < 1/2^3, k_4 < 1/2^4,...,k_n < 1/2^n, k_{n+1} < 1/2^{n+1}$
and
(2) For any $n \in \mathbb N$, $k_1+k_2+...+k_n+k_{n+1}  \leq 1/2^n$.

REPLY [1 votes]: This is impossible. Assume that such a sequence exists, and look at the series
$$ \sum_{j=1}^\infty k_j. $$
By assumption, the partial sum $0 \le \sum_{j=1}^n k_j \le 2^{-n}$. Let $n \to \infty$ to conclude that
$$ \sum_{j=1}^\infty k_j = 0, $$
which implies that $k_j = 0$ for all $j$.


TITLE: where do exponential and logarithmic functions intersect?
QUESTION [8 upvotes]: If $0<a<1$, then the graphs of $y=a^x$ and $y=\log_a(x)$ intersect at some point $(t(a),t(a))$. Does this function $t(a)$ have any nice expression? How much do we know about this function, except that it is obviously increasing and stays between $0$ and $1$? It is a very natural question, so I guess people thought about it before.
EDIT: why do I think it is a natural question? When we teach students calculus, one way to introduce the $\log_a(x)$ function is as the inverse of $a^x=e^{x \ln a}$. And drawing the graphs of $a^x$ and $\log_a(x)$ for $0<a<1$ in one coordinate system pulls attention to their intersection point right away.
EDIT 2: Thanks to lhf and Wolfram Alpha, the graph of $a^x=\log_a(x)$ for $x,a$ between $0$ and $1$ can be seen here.
It shows that for $a<t(e^{-1})=e^{-e}\approx 0.065988$, we have THREE points of intersection of graphs $a^x$ and $\log_ax$ (see example of $a=0.03$ here). At $a=e^{-e}$, the two graphs are tangent to each other (see here).
However, one of the points of intersection can be seen as the "principal branch", which I denoted $t(a)$ above. It looks like it has an inflection point at $a=e^{-1}\approx 0.367879$.
EDIT 3: Interestingly, the graphs of $a^x$ and $\log_a(x)$ do intersect for some values of $a>1$, namely, if $1<a<e^{1/e}\approx 1.44467$: example for $a=1.3$.

REPLY [2 votes]: Okay, this turned out to be an easy one. Since $a^x$ and $\log_a(x)$ are inverse to each other, their point of intersection (if unique) lies on the line $y=x$, so in particular, that value of $x=t(a)$ will satisfy $x=a^x$. Therefore, $a=x^{1/x}$, and $t(a)$ is the inverse for this function on $[0,1]$. The function $y=x^{1/x}$ (see graph here) has maximum value $e^{1/e}$ at $x=e$, it approaches $1$ from above as $x\to\infty$. Thus the functions $a^x$ and $\log_a(x)$ have two intersection points when $1<a<e^{1/e}$, they touch each other at $x=a$ if $a=e^{1/e}$, and have no intersection points if $a>e^{1/e}$.
A "closed form formula" for $t(a)$ may be obtained through Lambert $W$ function:
Since $x=a^x$, one has: $$1=x/a^x=x\cdot e^{-x \ln a},$$ and $$-\ln a= -x \ln a \cdot e^{-x \ln a},$$which means that $$W(-\ln a)=-x\ln a,$$ so that $$x=\dfrac{W(-\ln a)}{-\ln a}.$$
A graph of this function shows that it does indeed look like the inverse to $a=x^{1/x}$ on $[0,1]$ (see the graph in the EDIT 2 part).
Another question remains: what is the formula for the two "non-principal" intersection points when $0<a<e^{-e}$?


TITLE: how to convert right group action to left group action?
QUESTION [1 upvotes]: In Wikipedia it says one can convert right group action to left group action, because of the formula $(gh)^{−1} = h^{−1}g^{−1}$.
Can you explain how this works?

REPLY [5 votes]: If you have a left action you want to make into a right action, say $G$ acts on $X$, then just define $x \cdot g := g^{-1} \cdot x$ for $g \in G$ and $x \in X$.  The formula you've quoted above is then exactly what you need to prove that this gives a group action.  (If you did this without the inverse in there, then you wouldn't get a group action -- check this!)


TITLE: Can quantum measurements be the origin of thermodynamic arrow of time?
QUESTION [2 upvotes]: We can practically consider that the microscopic interactions are symmetric with respect to time(as we can neglect weak force for many cases which is the only interaction that can violate $T$ symmetry). So I thought that the asymmetry might be due to the irreversibility of quantum measurements. But this is only applicable for interpretations where wave function collapses like Copenhagen etc. What is the answer to this question in Many-worlds interpretation, Consistent histories, etc? Also in this page, they gave that the initial conditions of the universe are the reason for $T$ asymmetry in the 2nd law of thermodynamics. But I am not sure what they mean. Do they mean that the universe had a very low entropy at the beginning?

REPLY [2 votes]: Entropy is Macroscopic
As RogerJBarlow mentions in a comment, there is no need to invoke QM to explain the "arrow of time".  To use the exact analogy, consider an "ideal billiard table" with the standard collection of 15 balls.  Now, the macro state in which all balls are arranged in the starting triangle is very improbable, because there are only a few "micro-states" (permutations and rotations of the balls) which correspond to this macro state.  Further, with typical energy inputs to the table, there are many ways to move from this macro state to other macro states, but not very many ways to move from other macro states to this one.  That makes it a "high entropy" state.
On the other hand, if we consider the macro state "every pocket has at least 2 balls closer to it than any other pocket", we see that there are very many micro states in this macro state.  There are also many transitions which lead into this state, and the sheer number of micro states means that many transitions will cause you to never leave this macro state.  Thus, this is a "low entropy" state, and one of the more likely outcomes in a typical game of pool.
There is no entanglement, superposition, tunnelling, wave function collapse or any other QM phenomenon required to analyze the entropic behavior of this system, or to guess between a sequence of snapshots which direction indicates the arrow of time.  Replace the billiard balls with gas molecules, and you start to look much like thermodynamics.


TITLE: In a Banach Space $V$, proof that $A_V = B_V$
QUESTION [2 upvotes]: Let V be a Banach Space. Define $$\delta_V (t) = \inf \left\{ 1 - \frac{\|x+y\|}{2}: \|x\| = \|y\| = 1, \|x-y\| = t \right\}, \ \ \ \ t \in [0,2].$$ Consider
$$ A_V = \inf \left \{ \frac{4 - \|x+y\|^2}{\|x-y\|^2} : \|x\| = \|y\| = 1, x \neq y \right\} $$ and
$$ B_V = \inf \left\{ 4 \frac{1 - (1-\delta_V(t))^2}{t^2} : 0 < t \leq 2 \right\}.$$
Then $A_V = B_V$.
Proof.  Let $x,y \in V$ s.t. $\|x\| = \|y\| = 1$ and $\|x-y\| = t$, as, by definition, $\delta_V(t) \leq 1 - \frac{\|x+y\|}{2} $, we have
$$ (1 - \delta_V(t))^2 \geq   \frac{\|x+y\|^2}{4} \Rightarrow 4 (1 - (1 - \delta_V(t))^2 ) \leq 4 - \|x+y\|^2$$
As $t^2 = \|x-y\|^2$, we have
$$ \frac{4(1-(1 - \delta_V(t))^2)}{t^2} \leq \frac{4 - \|x+y\|^2}{\|x-y\|^2} \Rightarrow B_V \leq A_V $$
By the other side, given $0 < t \leq 2$ and $\epsilon > 0$, we can find $x,y \in V$ st $\|x\| = \|y\| = 1$ and $\|x-y\| = t$ satisfying:
$$ 1 - \frac{\|x+y\|}{2} \leq \delta_V(t) + \epsilon t^2 \Rightarrow 2 - \|x+y\| \leq 2 \delta_V(t) + 2 \epsilon t^2 $$
The next step in the proof would be showing the following inequality:
$$ 4 - \|x+y\|^2 \leq 4(\delta_V(t) + \epsilon t^2 (2 - \delta_V(t))) $$
However, I can't see why it's true. I would appreciate a hint.
Thank you.

REPLY [2 votes]: I cannot follow why you want that last inequality. But here is something that works.
By definition of $\delta_V(t)$, you have
$$
\delta_V(t)\leq\frac{2-\|x+y\|}2,
$$
that is $$\|x+y\|\leq 2-2\delta_V(t).$$ Also, $$2+\|x+y\|\leq2+\|x\|+\|y\|=4.$$
Then
\begin{align}
4-\|x+y\|^2&=(2+\|x+y\|)(2-\|x+y\|)
\leq(2+\|x+y\|)(2\delta_V(t)+2\epsilon t^2)\\ \ \\
&\leq(2+\|x+y\|)2\delta_V(t)+8\epsilon t^2\\ \ \\
&\leq(2+2-2\delta_V(t))2\delta_V(t)+8\epsilon t^2\\ \ \\
&=8\delta_V(t)-4\delta_V(t)^2+8\epsilon t^2\\ \ \\
&=4(1-(1-\delta_V(t))^2)+8\epsilon t^2,
\end{align}
which implies
$$
\frac{4-\|x+y\|^2}{\|x-y\|^2}\leq\frac{4(1-(1-\delta_V(t))^2)}{t^2}+8\epsilon.
$$


TITLE: probability that we stop flipping after exactly ten flips in a biased coin flipping?
QUESTION [3 upvotes]: We have a biased coin such that $P(head) = 0.25$ and $P(Tails) = 0.75$, suppose we flip coin until we observe third heads. What is the probability that we stop flipping after exactly ten flips?.
I thought that let us fix  of getting a third head at last that is at 10th flip, so that we would stop there, and the remaining - getting two heads can be accommodated in the 9 trials. so there are $9$ choose 2 ways of getting  two heads so the probability that we stop flipping after exactly ten flips is $^9C_{2}$ . $\frac{1}{4}^3$.$\frac{3}{4}^7$. Is this correct?
EDIT -
Now the probability of getting exactly 3 heads? I got it to be $^{10} C_{3} \frac{1}{4}^3 \frac{3}{4}^7$. Should we get the same as the previous one? any reason why they should/should not be same?

REPLY [1 votes]: $$\sum\limits_{k=3}^{10} {10 \choose k} \left( {1 \over 4} \right)^k \left( {3 \over 4} \right)^{10-k} = 0.474$$


text:
\section{Sparse Separable NMF}
\label{sec:ssnmf}

We explained in the previous section why separable NMF does not allow for the identification of ``interior vertices'', as they are nonnegative linear  combinations of other vertices.
However, if we assume a certain column-wise sparsity on the coefficient matrix $H$, they may become identifiable.
For instance, the vertex~$W_4$ of \cref{fig:intvertex} can be expressed as a combination of the three exterior vertices ($W_1$, $W_2$, and $W_3$), but not as a combination of any two of these vertices.
Moreover, some data points cannot be explained using only pairs of exterior vertices, while they can be if we also select the interior vertex~$W_4$.

\subsection{Problem Statement and Complexity}
\label{subsec:pbm}

Let us denote $\|x\|_0$ the number of non-zero entries of the vector $x$.

\begin{definition}\label{def:sparsesep}
A matrix $M$ is $k$-sparse $r$-separable if there exists a subset of $r$ columns of $M$, indexed by $\mathcal{J}$, and a nonnegative matrix $H \geq 0$ with $\|H(:,j)\|_0 \leq k$ for all $j$ such that $M = M(:,\mathcal{J}) H$.
\end{definition}
\Cref{def:sparsesep} corresponds to \cref{def:separability} with the additional constraint that $H$ has $k$-sparse columns, that is, columns with at most $k$ non-zero entries.

A natural assumption to ensure that we can identify $W$ (that is, find the set $\mathcal{J}$), is that the columns of $W$ are not $k$-sparse combinations of any other columns of $W$; see \cref{sec:analysis} for the details.

\begin{problem}[SSNMF]
Given a $k$-sparse $r$-separable matrix $M$, find $W = M(:,\mathcal{J})$ with $|\mathcal{J}| = r$ and a column-wise $k$-sparse matrix $H \geq 0$  such that $M = W H$.
\end{problem}

As opposed to separable NMF, given $\mathcal{J}$, computing $H$ is not straightforward. It requires to solve the following $\ell_0$-constrained optimization problem
\begin{equation}\label{eq:sparseproj}
    H^* = \argmin_{H \geq 0} f(M - M(:,\mathcal{J}) H) \text{ such that }  \|H(:,j)\|_0 \leq k \text{ for all } j.
\end{equation}
Because of the combinatorial nature of the $\ell_0$-``norm'', this $k$-sparse projection is a difficult subproblem with $\binom{r}{k}$ possible solutions, which is known to be NP-hard~\cite{natarajan1995sparse}.

In particular, a brute-force approach could tackle this problem by solving $\mathcal{O}(r^k)$ NNLS problems.
However, this combinatorial subproblem can be solved exactly and at a reasonable cost by dedicated branch-and-bound algorithms, such as  \arbo{}~\cite{nadisicexact}, given that $r$ is sufficiently small, which is typically the case in practice.
Even when $k$ is fixed, the following result shows that no provably correct algorithm exists for solving SSNMF in polynomial time (unless P=NP):
\begin{theorem} \label{th:nphardssnmf}
SSNMF is NP-complete for any fixed $k \geq 2$.
\end{theorem}

\begin{proof}
The proof is given in Appendix~\ref{sec:nphard}.
Note that the case $k = 1$ is trivial since each data point is a multiple of a column of $W$.
\end{proof}

However, in Section \ref{sec:analysis}, we show that under a reasonable assumption, SSNMF can be solved in polynomial time when $k$ is fixed.

\subsection{Related Work} \label{sec:relwork}

To the best of our knowledge, the only work presenting an approach to tackle SSNMF is the one by Sun and Xin (2011)~\cite{sun2011underdetermined} --- and it does so only partially.
It studies the blind source separation of nonnegative data in the underdetermined case.
The problem tackled is equivalent to NMF in the case $m < r$.
The
assumptions
used in this work are similar to ours, that is, separability and sparsity.

However, the setup considered is less general than SSNMF because the sparsity assumption (on each column of $H$) is limited to $k = m - 1$, while the only case considered theoretically is the case $r = m+1$ with only one interior vertex.

The proposed algorithm first extracts the exterior vertices using the method LP-BSS from~\cite{naanaa2005blind}, and then identifies the interior vertex using a brute-force geometric method.
More precisely,
they select an interior point, and check whether at least two of the $m-1$ hyperplanes generated by this vertex with $m-2$ of the extracted exterior vertices contain other data points.

If it is the case, then they conclude that the selected point is an interior vertex, otherwise they select another interior point.
For example, when $m = 3$,  this method consists in constructing the  segments between the selected interior point and all the exterior vertices.  If two of these segments contain at least one data point, then the method stops and the selected interior point is chosen as the interior vertex. Looking at Figure~\ref{fig:intvertex}, the only interior point for which two segments joining this point and an exterior vertex   contain data points is $W_4$.
Note that, to be guaranteed to work,
this method requires at least two hyperplanes containing the interior vertex and $m-2$ exterior vertices to contain data points. This will not be a requirement in our method.

config: arxiv


TITLE: Components of the metric tensor and its inverse
QUESTION [2 upvotes]: Let $g$ denote a metric tensor. Then Wald writes (in his book on general relativity): "The inverse of $g_{ab}$...is a tensor of type $(2,0)$ and could be denoted as $(g^{-1})^{ab}$. It is convenient, however, to drop the inverse sign and denote it simply as $g^{ab}$. No confusion arises from this since the upper position of the indices distinguishes the inverse metric from the metric. Thus, by definition, $g^{ab}g_{bc} = \delta^{a}_c$ (viewed as a map from $V_p$ into $V_p$)".
I understand all of this fine. My only problem is with the notation. If we view g as a map from the tangent space into the cotangent space, then $g^{-1}$ is map from the cotangent space into the tangent space, and hence $g^{-1} \circ g$ is the identity map from the tangent space to the tangent space. Makes perfect sense. But, I don't see how the general component of $g^{-1} \circ g = \delta$ (the identity map on the tangent space) is given by $g^{ab}g_{bc}$.

REPLY [1 votes]: One can use the matrix for $g$ within the construction of the reciprocal basis
$$\partial^k=\sum_sg^{ks}\partial_s,$$
or simply $\partial^k=g^{ks}\partial_s$.
It happens that  $\partial_k\mapsto\partial^k$ is a change of basis in the tangent space.


TITLE: Is series $\ln\frac{n+1}{n-1}$ converging?
QUESTION [0 upvotes]: We already know that
$$ \lim_{x\to \infty} x \ln \frac{x+1}{x-1} = 2$$
(this could be easily proved using L’Hospital’s rule.)
Then, how could we conclude (based on the limit provided) that the series
$$\sum_{n=2}^\infty \ln\frac{n+1}{n-1} $$
converges or not?

REPLY [4 votes]: $\sum_\limits{n=2}^N \ln \frac {n+1}{n-1}\\
\sum_\limits{n=2}^N \ln  (n+1) - \ln (n-1)\\
\ln N + \ln (N+1) - \ln 2$
As $N$ approaches infinity $\ln N + \ln (N+1) - \ln 2$ also goes toward infinity.


TITLE: How do I show this is a basis?
QUESTION [1 upvotes]: Suppose $\beta$ is a basis for $\mathbb R$ over $\mathbb Q$ and let $a \in \mathbb R$, $a \neq 1$.
Show that $a \beta= ${$ay\ |\ y \in \beta$} is a basis for $\mathbb R$ over $\mathbb Q$ for all $a \neq 0$.
Okay, isn't the dimension of $\mathbb R$ over $\mathbb Q$ uncountably infinite? How can I show it's a basis using the original method (linear independence and spanning), if the dimension is uncountable. Or should I approach it by contradiction?

REPLY [1 votes]: Let
$$x\in\Bbb R\implies \exists\;\text{finite}\;S\subset\beta \;\;s.t.\;\; x=\sum_{s\in S}a_ss\;,\;\;a_s\in\Bbb Q\;,\;s\in S\implies$$
$$x=\sum_{x\in S}\frac{a_s}a(as)\;,\;\;s\in S$$
and thus we can see any real is a rational linear combination of elements in $\;a\beta\;$ ...
The above works only for $\;a\in\Bbb Q\;$ . For $\;a\in\Bbb R\setminus \Bbb Q\;$ I can't see the way...


TITLE: Matrix x vector
QUESTION [0 upvotes]: matrix x vector multiplication
Are these correct? When I calculated them I got -2,1,3 for the first and 1,0,-2 for the second. if I am incorrect, what have I done wrong?

REPLY [0 votes]: The results you have shown in the linked image and the question text do not match. The correct values are
a) $$ \left| \matrix{ 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1} \right|
\pmatrix{1 \\ 2 \\ 3} = \pmatrix{(-1)(2) \\ (1)(1) \\ (1)(3)} = \pmatrix{-2 \\ 1 \\ 3} \;\;\checkmark$$
b) $$ \left| \matrix{ 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1} \right|
\pmatrix{0 \\ -1 \\ -2} = \pmatrix{(-1)(-1) \\ (1)(0) \\ (1)(-2)} = \pmatrix{1 \\ 0 \\ -2} \;\;\checkmark$$


TITLE: Pendulum with oscillating Fulcrum | Equations of Motion
QUESTION [0 upvotes]: A pendulum with a horizontally oscillating fulcrum can be described using the Lagrange formalism (related to a setting, as it is shown e.g. here) by the following system of nonlinear ordinary differential equations (ODE):
$$\begin{cases}
m\ddot x+kx+ml\left(\ddot \theta \cos \left(\theta\right)-\dot \theta^2 \sin \left(\theta\right)\right) & \text{= 0} \\
\cos \left(\theta\right) \ddot x+g\sin \left(\theta\right)+l \ddot \theta & \text{= 0}
\end{cases},$$
with $m$ being the pendulum's point mass, $l$ being the length of the pendulum's massless, inextensible and always taut cord, $k$ being the spring constant, $g \approx 9.81 \frac{m}{s^2}$ being Earth's average gravitational acceleration, $x$ being the horizontal deflection of the spring, and $\theta$ being the angle of rotation of the pendulum.
After I had comprehended the derivation, I asked myself how the equations of motion would look like in concrete terms. Of course, it's hardly possible to find analytical solutions for these equations.
But what is the easiest way to generate numerical approximations? Is it possible online, with appropriate programs (e.g. Scilab; if so, what would be the code?) or at all? Does the system have to be somehow manipulated, linearized, simplified ... before (if so, how?)? Which and how many boundary conditions are necessary?
Thank you and all the best!

REPLY [0 votes]: Considering a fulcrum mass $M$, the Lagrangian modeling is straightforward
Kinetic energy
$$
T = \frac{1}{2} \left(m \left(l^2 \theta'^2 \sin ^2(\theta)+\left(l \theta' \cos (\theta)+x_1'\right)^2\right)+M x_1'^2\right)
$$
Potential energy
$$
V = g l m (1-\cos (\theta))+\frac{1}{2} k x_1^2
$$
with the lagrangian
$$
L = T-V
$$
giving the movement equations
$$
\left\{
\begin{array}{rcl}
 x_1''&=&\frac{2 m \sin (\theta) \left(l \theta'^2+g \cos (\theta)\right)-2 k x_1}{m+2 M-\cos (2 \theta) m} \\
 \theta ''&=&\frac{\sec (\theta) \left(k x_1-\tan (\theta) \left(l m \cos (\theta) \theta'^2+g (m+M)\right)\right)}{l \left((m+M)
   \tan^2(\theta)+M\right)} \\
\end{array}
\right.
$$
as can be observed, if $M=0$ the denominators for $x_1''$ and $\theta''$ become $0$ as $\theta\to 0$. Considering $M<<m$ we can simulate the beautiful patterns appearing for $x_p = x_1+l\sin(\theta), y_p = -l\cos(\theta)$ executing the following MATHEMATICA script.
xp[t] = x1[t] + l Sin[theta[t]];
yp[t] = -l Cos[theta[t]];
T = 1/2 (M D[x1[t], t]^2 + m (D[xp[t], t]^2 + D[yp[t], t]^2));
V = 1/2 k x1[t]^2 + l (1 - Cos[theta[t]]) m g;
L = T - V;
vars = {x1[t], theta[t]};
equs = Grad[L, vars] - D[Grad[L, D[vars, t]], t];
sols = Solve[equs == 0, D[vars, {t, 2}]][[1]] // FullSimplify;
equs = Thread[D[vars, {t, 2}] == (D[vars, {t, 2}] /. sols)];
parms = {l -> 1, m -> 1, M -> 1/10, k -> 100, g -> 10};
tmax = 10;
equs0 = equs /. parms;
cinits = {x1[0] == 0, x1'[0] == -4, theta[0] == 0, theta'[0] == 0};
solx = NDSolve[Join[equs0, cinits], {x1, theta}, {t, 0, tmax}];
ParametricPlot[Evaluate[{xp[t], yp[t]} /. parms /. solx], {t, 0, tmax},  PlotRange -> All]


TITLE: If $\forall a,b \in G, \exists x \in G: a * x = b$ and $\forall a,b \in G, \exists x \in G: x * a = b$ then $G$ is a group
QUESTION [3 upvotes]: I'm having some trouble with the following exercise:

Let $G$ be a non-empty set and let $*:G\times G \to G$ such that:

$*$ is associative
$\forall a,b \in G, \exists x \in G: a * x = b$
$\forall a,b \in G, \exists x \in G: x * a  = b$

Prove that $(G,*)$ is a group

We already know that $*$ is associative but I'm having some trouble proving that there exists an identity element. My plan is the following:

For any $a \in G$, show that if $a * x = a$ and $x'*a = a$, then $x = x'$
for any $a,b \in G$, if $a * x_a = a$ and $b * x_b = b$, then $x_a = x_b$

But I'm not being able to prove 1. How can this be done?

REPLY [3 votes]: Let $g$ be any element of $G$ and take $a = b = g$ in assumption 2.
It follows that there exists $e \in G$ such that $g * e = g$.
It follows that $h*g*e = h*g$ for any $h\in G$.
By assumption 3, any element of $G$ can be written as $h*g$ for some $h \in G$.
Thus we have $x*e = x$ for any $x \in G$.
This shows that there exists a right identity $e$ of $G$.
The same proof, with left and right switched, shows that there exists a left identity $e'$ of $G$.
We then have $e' = e'e = e$, which means that $e$ is an identity of $G$.
It remains to show that every element has an inverse.
For any $g \in G$, assumptions 2 and 3 say that there exist $h$ and $h'$ such that $g*h = e = h'*g$.
As $h' = h'*e = h'*g*h = e*h = h$, we see that $h$ is an inverse of $g$.


text:
\begin{document}

\begin{abstract}
We construct a finitely generated 2-dimensional group that acts properly on a locally finite CAT(0) cube complex
but does not act properly on a finite dimensional CAT(0) cube complex.
\end{abstract}

\maketitle

Among its  extraordinary properties,
Thompson's group $F$  acts freely and metrically properly on a CAT(0) cube complex \cite{Farley2003},
but $F$ does not act properly on a finite dimensional CAT(0) cube complex,
 since $F$ contains a copy of $\integers^\infty$. The purpose of this note is to produce a f.g.\ group $G$ with
the same property, but with $\cd(G)<\infty$.
We remark that there are tubular groups (e.g.\ Gersten's group)
that act freely on infinite dimensional cube complexes,
but cannot act metrically properly \cite{WiseGerstenRevisited}, since Gersten's result applies in a cubical case \cite{Gersten94, HaglundSemiSimple, WoodhouseAxis}.
Also, the wreath product $H\wr F_2$ with $H\neq 1$ finite,
acts metrically properly on an infinite dimensional CAT(0) cube complex,
but does not act metrically properly on any finite dimensional CAT(0) cube complex \cite{CornulierStadlerValette12}.

\begin{thm}\label{thm:main}
There exists a f.g.\ group of cohomological dimension $2$ that acts freely (and thus metrically properly)  on a locally-finite CAT(0) cube complex but does not act
freely on a finite dimensional CAT(0) cube complex.
\end{thm}

\begin{proof}
For each $n\geq 1$ let $A_n$ be the $2$-complex of a $2$-generator $C'(\frac16)$ group that does not act properly on any $n$-dimensional CAT(0) cube complex. Such groups were constructed in \cite{JankiewiczCubicalDimension}. Moreover, we can choose $A_n$ so that its $2$-cells have boundary cycles of length $>12$.

Let $X_n = A_n\vee B_n$ where $B_n$ is a bouquet of two circles. Let $X$ be the union of a ray $r =[0,\infty]$ and $\displaystyle \sqcup_{n\geq 0} X_n$ where the basepoint of $X_n$ is identified with the vertex $n\in r$. Let $t_n$ denote the oriented edge $[n-1,n]$ of $r$. Let the basepoint of $X$ be the vertex $0 \in r$. We have $\pi_1 X = *_{n=0}^{\infty}\pi_1 X_n$.
 Let $x_{n1},x_{n2}$ be closed paths in $X_n$ representing generators of $\pi_1 A_n$, and let $x_{n3},x_{n4}$ be closed paths representing generators of $\pi_1B_n$.

Consider the $2$-complex $Y$ obtained from $X$ by adding $2$-cells as follows:
for each $n\geq 1$ and  $i\in\{1,2,3,4\}$ add a $2$-cell $C_{ni}$ with boundary path
\[
t_nx_{ni}t_n^{-1}\gamma_{ni}
\]
where $\gamma_{ni}$ is a closed path in $X_{n-1}$ of the form
\[
\gamma_{ni} =
\beta_{ni}^1\alpha_{ni}\beta_{ni}^2\cdots\alpha_{ni}\beta_{ni}^m
\]
 where $m\geq 12$, and where
 \begin{itemize}
 \item $\alpha_{ni} = x_{(n-1)i}$ for $i=1,2$, and $\alpha_{ni} = (x_{(n-1)(i-2)})^2$ for $i=3,4$;\\ (note that $\alpha_{ni}\in A_{n-1}$),
 \item $\{\beta_{ni}^j : 1\leq i\leq 4,\, 1\leq j\leq m\}$
is a collection of distinct closed paths of the same length in $B_{n-1}$.
 \end{itemize}

\begin{claim}The complex $Y$ is a $C'(\frac16)$-complex without periodic 2-cell attaching maps. Consequently, $\cd(\pi_1 Y)=2$.\end{claim}
As $X$ is a $C'(\frac16)$-complex, it suffices to verify the $C'(\frac16)$ condition for:
\begin{itemize}
\item a $2$-cell $C_{ni}$ and a $2$-cell $C$ of $X$,
\item a $2$-cell $C_{ni}$ and a $2$-cell $C_{n'i'}$.
\end{itemize}

If there is nontrivial piece between $C_{ni}$ and $C$, then $C$ lies in $A_n$ or $A_{n-1}$ and the piece is the first or second power of one of $\{x_{n1}, x_{n2}, x_{(n-1)1},x_{(n-1)2}\}$.

The cells $C_{ni}$ and $C_{n'i'}$ can only overlap if $|n-n'|\leq 1$.
If $n' = n+1$, then
the only piece between $C_{ni}$ and $C_{n'i'}$ is of the form $x_{ni}$.
In all the cases considered so far, pieces have length at most $2$, so the $C'(\frac16)$ condition is satisfied.

If  $n=n'$ and  $i - i'$ is odd, then any nontrivial piece is either $t_n$ or is contained in some $\beta_{ni}^j$. Suppose $n=n'$ and $i-i'$ is even. Since $\{\beta_{ni}^j\}$ are distinct, the maximal pieces are strictly contained in $\beta_{ni}^{j}\alpha_{ni}\beta_{ni}^{j+1}$, $t_n^{-1}\beta_{ni}^1$, or $\beta_{ni}^m t_n$. In these cases $C'(\frac16)$ condition holds
as $m\geq 12$.

Any $C'(\frac16)$-complex without periodic 2-cell attaching maps is aspherical (see e.g.\ \cite{LS77} and \cite{ChiswellCollinsHuebschmann81})
so $\cd (\pi_1Y) =2$.

\begin{claim} The group $\pi_1 Y$ is f.g.
\end{claim}
$\pi_1 Y$ is a quotient of $\pi_1 X$, so $\pi_1Y$ is generated by images of generators of $\pi_1 X$, i.e.\ the elements represented by $\bigcup_{n=0}^{\infty}\{t_1\cdots t_{n}x_{ni}t_{n}^{-1}\cdots t_{1}^{-1}\}_{i=1}^{4}$. By construction, $t_1\cdots t_{n}x_{ni}t_{n}^{-1}\cdots t_{1}^{-1}$ is homotopic in $Y$ to a closed path contained in a finite subcomplex $X_{[0,n-1]} = [0,n-1]\cup \bigcup_{i=0}^{n-1} X_i$ of $X$.  Specifically,
\[[t_1\cdots t_{n}x_{ni}t_{n}^{-1}\cdots t_{1}^{-1}] = [t_1\cdots t_{n-1}\gamma_{ni}^{-1}t_{n-1}^{-1}\cdots t_{1}^{-1}] \,\,\text{ in }\pi_1Y.\]
 Consequently, $\pi_1 Y$ is generated by $[x_{01}], [x_{02}], [x_{03}],[x_{04}]$.

\begin{claim}The complex $Y$ is locally finite.\end{claim}

Indeed, each $X_n$ is compact and intersects finitely many additional cells:\\ $\{t_{m}, C_{mi}: m\in\{n, n+1\}, i\in\{1,2,3,4\}\}$.

\begin{claim} The group $\pi_1 Y$ acts freely on a locally finite CAT(0) cube complex.
\end{claim}
As $Y$ is locally finite, its dual cube complex is locally finite~\cite[Thm~10.5]{WiseSmallCanCube04}.
Since $Y$ is aspherical, $\pi_1Y$ is torsion-free.
Hence the action of $\pi_1 Y$ on the dual cube complex is free~\cite[Cor~10.7]{WiseSmallCanCube04}.

\begin{claim}The groups $\pi_1 A_n$ embed in $\pi_1 Y$. Consequently, $\pi_1 Y$ does not act properly on any finite dimensional CAT(0) cube complex.\end{claim}
$\pi_1A_n\hookrightarrow \pi_1 Y$ since $A_n\hookrightarrow Y$ has  \emph{no missing shells} \cite[Thm~13.3]{WiseCBMS2012}. As $\pi_1A_n$ does not act properly on an $n$-dimensional CAT(0) cube complex, $\pi_1Y$ does not.
\end{proof}

Groups with finite $C'(\frac 16)$ presentations are hyperbolic. However, the complex $Y$ in Theorem~\ref{thm:main} has infinitely many $2$-cells. We close with the following problem, which is open, even under the assumption that $G$ acts freely on a finite dimensional CAT(0) cube complex.
\begin{prob}
Let $G$ be a hyperbolic group.
Suppose $G$ acts freely on a CAT(0) cube complex.
Does $G$ act freely and cocompactly on a CAT(0) cube complex?
\end{prob}

\subsection*{Acknowledgements} We are grateful to the referee for helpful comments and corrections.

\bibliographystyle{alpha}

\bibliography{wise}

\end{document}


TITLE: There is a primitive $m^{th}$ root of unity in $\mathbb{Q}_p$ $\Leftrightarrow m \mid (p-1)$
QUESTION [4 upvotes]: After Hensel's Lemma there is the following proposition in my notes:

If $p$ is a prime and $m \in \mathbb{N}$ then there is a primitive $m^{th}$ root of unity in $\mathbb{Q}_p$ $\Leftrightarrow m \mid (p-1)$.

To prove this proposition we begin as follows:
$(\Rightarrow) $ Let $a$ be a primitive $m^{th}$ root of unity in $\mathbb{Q}_p$. That means that $m$ is the smallest natural number such that $$a^m \equiv 1 \pmod p$$ (correct?)
Can we suppose that $m$ and $p$ are coprime, and use Fermat's little theorem we have that $a^{p-1} \equiv 1 \pmod p$?
Can we conclude from this that $m \mid (p-1)$?
How do we prove the other direction? Perhaps using Hensel's Lemma?

REPLY [3 votes]: The easiest way to prove this is as follows:
You want to ask if the polynomial
$$x^m-1$$
has a root in $\Bbb Q_p$. We know if you pick one such primitive root, $\zeta$ then we can get all of the others by examining $1,\zeta,\zeta^2,\ldots, \zeta^{m-1}$.
Now, reducing this polynomial modulo $p$ we see that we want to know if there are $m^{th}$ roots of $1$ in $\Bbb F_p$, however we know by the classification of finite fields that the elements of $\Bbb F_p$ are exactly those that satisfy $x^p-x=0$. Now, since roots of unity are not $0$, we see all non-zero elements of $\Bbb F_p$ satisfy $x^{p-1}-1$. More completely we have the result from the structure of finite fields

If $F$ is a finite field of order $q$, then $F^\times$ is a cyclic group of order $q-1$.

From this we see that for each divisor $d|(q-1)$, we may take a multiplicative generator of $F^\times$, say we call it $g$, and note that $g^{(q-1)/d}$ is an element of order $d$ in the group, i.e. it is a $d^{th}$ root of $1$. And if $\zeta\in F$ is an $m^{th}$ root of one, then the multiplicative group $\langle \zeta\rangle\le F^\times$ must have order dividing the order of the group, i.e. $m|(q-1)$. So it is necessary and sufficient that $m|(q-1)$ for a finite field, $F$, of order $q$ to possess the $m^{th}$ roots of $1$.
Now, in our case the residue field is just $\Bbb F_p$, so we see it has all $m^{th}$ roots of $1$ for $m|(p-1)$ and no others. This implies immediately that if $m\not\mid (q-1)$, then $\Bbb Q_p$ does not possess $m^{th}$ roots of $1$, since if we had them in the bigger field, quotienting to the residue field would still keep them.
To see the other direction, we note that if $m|(p-1)$, in particular $m$ is coprime to $p$, hence since
$${d\over dx}(x^m-1)=mx^{m-1}$$
and $|m|_p=1$ so we satisfy the hypotheses of Hensel's lemma, and get a lifting back up to $\Bbb Q_p$. This completes the proof.


text:
\begin{document}

\title{Some New Examples of Non-K\"ahler Ricci Solitons}
\author{Andrew S. Dancer}
\address{Jesus College, Oxford University, OX1 3DW, United Kingdom}
\email{dancer@maths.ox.ac.uk}
\author{McKenzie Y. Wang}
\address{Department of Mathematics and Statistics, McMaster
University, Hamilton, Ontario, L8S 4K1, Canada}
\email{wang@mcmaster.ca}
\thanks{partially supported by NSERC Grant No. OPG0009421}

\date{revised \today}

\begin{abstract}
We produce non-K\"ahler complete steady gradient Ricci solitons
generalising those constructed by Bryant and Ivey.
\end{abstract}

\maketitle

\noindent{{\it Mathematics Subject Classification} (2000):
53C25, 53C44}

\bigskip
\setcounter{section}{-1}

\section{\bf Introduction}

In this article we continue our investigation of reductions of the Ricci soliton
equations to ordinary differential equations. Recall that a Ricci soliton consists of
a complete Riemannian metric $g$ and a complete vector field $X$ on a manifold
satisfying the equation:
\begin{equation} \label{LieRS}
{\ric}(g) + \frac{1}{2} \,{\sf L}_{X} g + \frac{\epsilon}{2} \, g = 0
\end{equation}
where $\epsilon$ is a real constant and $\sf L$ denotes the Lie derivative.

This equation is a generalisation of the Einstein equation, and it is
natural to look for solutions by methods that have been fruitful in the Einstein
case. In \cite{DW} we set up the formalism for cohomogeneity one Ricci solitons
and wrote down the resulting ODE system. We found families of explicit K\"ahler
solutions generalising those of \cite{Ko}, \cite{Ca}, \cite{ChV},
\cite{G}, \cite{PTV}, \cite{FIK}, \cite{PS} and \cite{ACGT}.

Most of the known examples of Ricci solitons are indeed K\"ahler. The
exceptions of which we are aware are the homogeneous solitons on nilpotent
Lie groups \cite{La}, the rotationally symmetric Bryant
solitons \cite{Bry} on $\R^n \, (n > 2),$   Ivey's generalization of these
solutions \cite{Iv}, as well as the expanding counterparts described in \cite{Cetc}
and \cite{GK}. (Note that if $n=2$ the Bryant soliton is Hamilton's
famous cigar soliton \cite{Ha1}, which {\em is}  K\"ahler.) The Bryant solutions
are warped products on a single factor, while those of Ivey involve two factors.

In this paper we shall focus on steady gradient Ricci solitons and
generalise the Bryant-Ivey examples to produce complete steady  solitons
on warped products over an arbitrary number of positive Einstein factors
(see Theorem \ref{mainthm}). An important tool in our analysis is the
observation that the {\em general} cohomogeneity one {\em steady} soliton equations
always admit a Lyapunov function. This generalises the Lyapunov function in
the Bryant-Ivey systems.

Recall that Hamilton has proved that steady gradient Ricci solitons occur as
type II singularity models for the Ricci flow when the curvature operator is
non-negative and the Ricci is positive (\cite{Ha2} or Theorem 4.3.6 in \cite{CaZ}).
Our new steady solitons have non-negative Ricci curvature (Theorem \ref{ricci})
and always some negative sectional curvatures. They have asymptotically
paraboloid geometry (Theorem \ref{asymptotics}) and hence zero asymptotic
volume ratio. The asymptotic scalar curvature ratio is infinite
(cf Remark \ref{sectcurv}). Whether these steady solitons can be realised
as blow-up limits of non-trivial Ricci flows seems to be an interesting
question.

Finally, we would like to thank the referee for several helpful comments.

\section{\bf Lyapunov functions}

We recall the set-up from \cite{DW}. We consider a manifold $M$
with an open dense set foliated by diffeomorphic hypersurfaces $P_t$ of
real dimension $n$.
Assume the metric can be written as $g=dt^2 + g_t$ where $g_t$ is a metric
on $P_t$. We can view $t$ as arclength along a geodesic orthogonal to the
hypersurfaces. Let $r_t$ denote the Ricci tensor of $g_t$, viewed as an
endomorphism via $g_t$, and let $L_t$ denote the shape operator of the
hypersurfaces (so $\dot{g_t} = 2 g_t L_t$). Assume that the scalar curvature
$R_t=\tr(r_t)$ and the mean curvature $\tr(L_t)$ are constant on each
hypersurface. Furthermore, assume that the codifferentials $\delta^{\nabla^{t}} L_t$
vanish, where $L_t$ is viewed as a $TP_t$-valued $1$-form on $P_t$.

The above assumptions are satisfied, for example, if $M$ is
of cohomogeneity one with respect to an isometric group action, with
no repeated summands in the isotropy representation of the principal orbits $P_t$.
They are satisfied also when $M$ is a multiple warped product over an
interval, which will be the setting of this paper.

We consider solitons of {\em gradient type}, i.e., where $X = {\rm grad} \; u$
for a function $u$. Equation (\ref{LieRS}) then becomes
\begin{equation} \label{gradRS}
{\ric}(g) + {\rm Hess}(u) + \frac{\epsilon}{2} \, g = 0.
\end{equation}
We will further suppose that $u$ is a function of $t$ only. In this setting,
the above equation become the system (cf \S 1 of \cite{DW})
\begin{eqnarray}
  -{\rm tr} (\dot{L}) - {\rm tr} (L^2) + \ddot{u} + \frac{\epsilon}{2} &=& 0,  \label{TT} \\
    r_t - ({\rm tr}\, L)L - \dot{L} + \dot{u} L + \frac{\epsilon}{2} \, \I &=& 0 \label{SS}.
\end{eqnarray}

We have a conservation law
\[
\ddot{u} + ({\rm tr}\, L) \dot{u} - (\dot{u})^2 -\epsilon u = C
\]
for some constant $C$.
Using the equations this may be rewritten as
\begin{equation}
{\rm tr} (r_t) + {\rm tr} (L^2) - (\dot{u} - {\rm tr}\, L )^2 - \epsilon u +
\frac{1}{2}(n-1) \epsilon = C.
\end{equation}

We now specialise to the case of {\em steady solitons}, that is, $\epsilon =0$.
The conservation law is now
\begin{equation} \label{cons1}
{\rm tr} (r_t) + {\rm tr} (L^2) - (\dot{u} - {\rm tr}\,  L)^2 = C.
\end{equation}

\begin{prop}
The function $(\dot{u} - {\rm tr}\, L)^{-2}$
is a Lyapunov function, that is, it is monotonic on each interval on which it is defined.
\end{prop}

\begin{proof}
\begin{eqnarray*}
\frac{d}{dt} \left( \frac{1}{(\dot{u} - {\rm tr}\, L)^2} \right) &=&
-\frac{2 ( \ddot{u} - {\rm tr}\, \dot{L} )}{(\dot{u} - {\rm tr}\, L)^3} \\
&=& - \frac{2 {\rm tr} (L^2) }{(\dot{u} - {\rm tr}\, L)^3}
\end{eqnarray*}
\end{proof}

\begin{rmk}
The conservation law (\ref{cons1}) shows that our Lyapunov function is a constant multiple
of
\[
\frac{{\rm tr}(r_t) + {\rm tr} (L^2)}{(\dot{u} - {\rm tr}\; L)^2}  -1.
\]
\end{rmk}

\begin{rmk} Recall that the above conservation law was derived in \cite{DW}
from the consequence $\Delta du = du \circ \ric$ of the Ricci soliton
equation upon application of the contracted second Bianchi identity.
In fact, we can also derive this conservation law from Perelman's
$\mathcal F$-functional (steady case) and $\mathcal W$-functional
(expanding and contracting cases). From this point of view, the conservation
law asserts that the trajectories representing smooth gradient Ricci
solitons must lie in the zero-energy hypersurface of the Hamiltonians
corresponding to Perelman's functionals. Details of the Hamiltonian
formulation will be discussed elsewhere.
\end{rmk}

\section{\bf Multiple warped products}
We now specialise to the class of examples, multiple warped products,
that will generalise the examples of Bryant and Ivey.

We look for metrics of the form
\begin{equation} \label{metric}
dt^2 + \sum_{i=1}^{r} g_i^2(t)\,  h_i
\end{equation}
on $I \times M_1 \times ... \times M_r$\, where
$I$ is an interval in $\mathbb R$ and $(M_i, h_i)$ are Einstein manifolds
with positive Einstein constants $\lambda_i$. We let $d_i$ denote the (real)
dimension of $M_i$.

Recall that the soliton potential $u$ is taken to be a function of $t$ alone.
The resulting equations are equivalent to those coming from a cohomogeneity one
ansatz, though of course the $M_i$ could be inhomogeneous.

The shape operator and Ricci endomorphism are now given by
\begin{eqnarray*}
L_t &=& {\rm diag} \left( \frac{\dot{g_1}}{g_1} \,\I_{d_1}, \cdots,\frac{\dot{g_r}}{g_r} \,\I_{d_r}\right)  \\
r_t &=& {\rm diag} \left( \frac{\lambda_1}{g_1^2} \, \I_{d_1}, \cdots,\frac{\lambda_r}{g_r^2}\, \I_{d_r}\right)
\end{eqnarray*}
where $\I_m$ denotes the identity matrix of size $m$. (We shall henceforth
drop the subscript $t$ of $L$ for ease of notation.)
Motivated by Ivey's work, we introduce new variables
\begin{eqnarray}
X_i &=& \frac{\sqrt{d_i}}{( -\dot{u} + {\tr} L)} \frac{\dot{g_i}}{g_i} \label{def-Xi}\\
Y_i &=& \frac{\sqrt{d_i \lambda_i}}{g_i} \frac{1}{(-\dot{u} + \tr{L})} \label{def-Yi}
\end{eqnarray}
for $i=1, \ldots, r$.

Notice that
\[
\sum_{j=1}^{r} \, X_j^2  = \frac{{\rm tr} (L^2)}{(\dot{u} - {\rm tr} L)^2} \;\; : \;\;
\sum_{j=1}^{r} \, Y_j^2 = \frac{ {\rm tr} (r_t)}{(\dot{u} - {\rm tr} L)^2}.
\]
We can take our Lyapunov function, therefore, to be
\begin{equation} \label{Lyap}
{\mathcal L} := \frac{C}{(\dot{u}- {\rm tr} L)^2} = \sum_{i=1}^{r} \, (X_i^2 + Y_i^2)  - 1
\end{equation}
where $C$ is a nonzero constant to be specified later. Note further that
\begin{equation} \label{cons2}
{\mathcal L} = \tilde{C}_{i} g_i^2 Y_i^2 \;\; : \;\; i=1, \ldots, r
\end{equation}
for nonzero constants $\tilde{C}_{i} = \frac{C}{d_i \lambda_i}$.

It is convenient to introduce a new independent variable $s$ defined by
\begin{equation} \label{st}
\frac{d}{ds} := \frac{1}{(-\dot{u} + {\rm tr} L)} \frac{d}{dt} =
\sqrt{\frac{\mathcal L}{C}} \frac{d}{dt}
=\frac{g_i Y_i}{\sqrt{\lambda_i d_i}}\, \frac{d}{dt},
\end{equation}
in which the final expression is independent of $i$ by (\ref{cons2}).
We use a prime ${ }^{\prime}$ to denote differentiation with respect to $s$.

We obtain from the Ricci soliton system the following equations in our new variables:
\begin{eqnarray}
X_{i}^{\prime} &=& X_i \left( \sum_{j=1}^{r} X_j^2 -1 \right) +
\frac{Y_i^2}{\sqrt{d_i}} \, , \label{eqnX} \\
Y_{i}^{\prime} &=&  Y_i \left( \sum_{j=1}^{r} X_j^2 -\frac{X_i}{\sqrt{d_i}}
\right) \label{eqnY}
\end{eqnarray}
for $i=1, \ldots, r$.   Note that these imply the equation
\begin{equation} \label{eqnLyap}
{\mathcal L}^{\prime} = 2 {\mathcal L} \left( \sum_{i=1}^{r} X_i^2 \right).
\end{equation}

Conversely, if we have a solution of the above system, we may recover $t$ and the $g_i$
from
\begin{equation} \label{def-tgi}
dt = \sqrt{\frac{\mathcal L}{C}}\,\, ds, \ \ \ \ \
{g}_i = \sqrt{\frac{\mathcal L}{C}} \, \frac{\sqrt{d_i \lambda_i}}{Y_i}\, ,
\end{equation}
which are equivalent to (\ref{st}) and (\ref{def-Yi}) respectively. The soliton potential
is recovered from integrating
\begin{equation} \label{def-u}
 \dot{u} = \tr(L) - \sqrt{\frac{C}{\mathcal L}},
\end{equation}
where $\tr(L)$ is calculated using
\begin{equation} \label{logdiff-gi}
 \frac{\dot{g_i}}{g_i} = \sqrt{\frac{C}{\mathcal L}} \frac{X_i}{\sqrt{d_i}}\, .
\end{equation}
Differentiating the above, which is equivalent to (\ref{def-Xi}), one gets
\begin{equation} \label{gidotdot}
     \frac{\ddot{g}_i}{g_i} = \frac{C}{\mathcal L} \left(\frac{X_i^2 + Y_i^2 -\sqrt{d_i} X_i}{d_i}\right).
\end{equation}
Putting (\ref{def-u})-(\ref{gidotdot}) together one obtains (\ref{SS}). Finally,
differentiating (\ref{def-u}) gives (\ref{TT}). We then obtain a smooth solution of the
Ricci soliton equation provided that appropriate smoothness conditions
at the endpoints (formulated in the next section) are satisfied.

\begin{rmk} \label{einstein}
In (\ref{def-u}) if we take the derivative with respect to $s$ instead, we have
$$ u^{\prime} = \frac{\tr L}{\sqrt{C/{\mathcal L}} } - 1 = \sum_{i=1}^{r} \sqrt{d_i} X_i - 1,$$
where we have used (\ref{logdiff-gi}). Observe that $u^{\prime} \equiv 0$ iff
the soliton is trivial (Ricci-flat in the steady case). This motivates the
definition of the quantity $\mathcal{H} := \sum_{i=1}^{r} \sqrt{d_i} X_i$,
so that the Ricci-flat trajectories lie in the subspace ${\mathcal H} = 1$.
For these trajectories the conservation law (\ref{cons1})
becomes $\mathcal{L} = 0$.
\end{rmk}

\section{\bf Trajectories of the equations}

Recall that by applying the maximum principle to consequences of
the Ricci soliton equation one can show that on a closed manifold
a steady Ricci soliton is Ricci-flat (see e.g. Proposition 1.66 in \cite{Cetc}).
Hence we are interested in constructing complete non-compact steady
soliton metrics where there is a smooth collapse at one end, corresponding to $t=0$
without any loss of generality, onto a lower-dimensional submanifold. This can
be achieved if we take one factor, say $M_1$, to be a sphere $S^{d_1}$.
The submanifold would then be $M_2 \times \cdots \times M_r$. With
the normalization $\lambda_1 = d_1 -1$, the boundary conditions for the soliton
solution to be $C^2$ are the existence of the following limits:
\begin{equation} \label{bdy0}
g_1(0)=0   \;\; : \;\; g_i(0) = l_i \neq 0 \; (i > 1),
\end{equation}

\begin{equation} \label{bdy1}
\dot{g_1}(0)=1 \;\; : \;\; \dot{g_i}(0) = 0 \; (i > 1),
\end{equation}

\begin{equation} \label{bdy2}
\ddot{g}_{1}(0) =0 \;\; : \;\; \ddot{g_i}(0) \;\, {\rm  finite} \;
(i > 1),
\end{equation}

\begin{equation} \label{bdyu}
u(0) \, \,  {\rm finite}: \, \, \dot{u}(0)=0 \, \, : \ddot{u}(0) \, \, {\rm \, finite}.
\end{equation}

In order to get a smooth solution, it suffices to show further that the third
derivatives of $g_i$  tend to finite limits at $t=0$. Once this is done,
we can write the trace of the soliton equation (\ref{gradRS}) as
$$ \Delta u =  R + \frac{n \epsilon}{2}.$$
The right-hand side of this elliptic equation for $u$ lies in $C^{0, \alpha}$.
Since $u$ is in $C^2$, it follows from Lemma 6.16 in \cite{GT} that $u$
is in $C^{2, \alpha}$. Using the contracted second Bianchi identity and the
weak form of Bochner's formula for the Laplacian of a one-form (verified for
example by smooth approximation in $W^{1, 2}$) we can then show that the $1$-form
$\omega:=du$ is a weak solution of $\Delta \omega = 2 \omega \circ r$
(Eq. (2.1) in \cite{DW}). The argument in the proof of Lemma 2.2
there shows that $\omega$ is actually in $C^{2, \alpha}$. The smoothness
(in fact real analyticity) of the solution then follows from Morrey's theorem.

With the above remarks in mind, we consider trajectories emanating from the
critical point of (\ref{eqnX}) and (\ref{eqnY}) given by
\[
X_i = \beta, \;\; Y_1 = \hat{\beta}, \;\; X_i =Y_i=0  \,\, (i > 1)
\]
where $\beta = \frac{1}{\sqrt{d_1}} $ and $\hat{\beta} = +\sqrt{1- \beta^2}$.
This critical point lies on the unit sphere in $XY$-space, i.e., on the
level set  ${\mathcal L}=0$.

Linearising about this critical point gives a system whose matrix
has a $2 \times 2$ block
\[
\left( \begin{array}{cc}
3 \beta^2 -1 & 2 \beta \hat{\beta} \\
\beta \hat{\beta} & 0
\end{array} \right)
\]
corresponding to $X_1, Y_1$ : the remaining entries are diagonal, with
$\beta^2$ and $\beta^2 -1$ each occurring $r-1$ times.
The eigenvalues are therefore
$\beta^2$ ($r-1$ times),  $\beta^2 -1$ ($r$ times), and $2 \beta^2$.

\medskip

We shall assume from now on that $d_1 > 1$. The above critical point
is then {\em hyperbolic}.

\medskip

We will parametrise trajectories emanating from this critical point
so that the critical point corresponds to $s=-\infty$. Note that there is
some $\delta > 0$  such that for $i>1$, the differential inequality
$$  \frac{d}{ds} Y_i^2 \leq 2(\beta^2 + \delta) Y_i^2$$
holds near $s=-\infty$ for any such trajectory. A comparison argument then
shows that if $Y_i(s_*) > 0$ for all $i>1$, then on $(-\infty, s_*]$ we have
$Y_i > 0$. Since $\lim_{s \rightarrow -\infty} Y_1 = \hat{\beta} > 0$ we may
assume that $Y_1 > 0$ on $(-\infty, s_*]$ as well.

Now by standard facts in dynamical systems (cf \cite{CL}, proofs of
Theorems 4.1, 4.3 and 4.5) and the fact that the system
(\ref{eqnX})-(\ref{eqnY}) is invariant under the symmetries
$Y_i \mapsto -Y_i$, there is an $(r-1)$-parameter family of trajectories
lying in the unstable manifold of this critical point having the above
positivity properties and flowing into the open unit ball ${\mathcal L} < 0$.

\begin{rmk} \label{Bohm}
In \cite{Bo} an $r-2$ parameter family of complete Ricci-flat
metrics was constructed on the manifolds under consideration here.
These correspond to trajectories emanating from the above critical point and
lying {\em in} the sphere ${\mathcal L} = 0$. In fact, the unstable manifold
intersects this sphere transversely, and this accounts for the parameters
in the Ricci-flat metrics.
\end{rmk}

We now work with one of the trajectories going into ${\mathcal L} < 0$.

 Eq. (\ref{eqnLyap}) shows
that the trajectory {\em stays} in the region ${\mathcal L} < 0$. Hence all
the variables are bounded by $1$ and the flow exists for all $s \in \mathbb R$.
Moreover, $\mathcal L$ decreases monotonically to some negative constant $\kappa$.
Note that as a result of the above choices, the constant $C$ in (\ref{Lyap})
is fixed and is {\em negative}.

Now  Eq. (\ref{eqnY}) and $X_i \leq 1$ imply that $Y_i^2$ satisfies
the differential inequality
$$ \frac{d}{ds} Y_i^2 \geq -\frac{2}{\sqrt{d_i}} \, Y_i^2. $$
By a standard comparison argument it follows from $Y_i(s_*) > 0$ that
$Y_i > 0$ on $[s_*, +\infty)$. Hence for all finite $s$, $g_i$ can be defined
by (\ref{def-tgi}) (so is nonzero) and (\ref{cons2}) holds.

\begin{lemma}
The metric corresponding to our trajectory is complete at $s = +\infty$.
\end{lemma}

\begin{proof}
From (\ref{def-tgi}) it follows that as $s$ tends to infinity the arclength
$t$ does also. The definition of $g_i$ shows that $g_i$ remain nonzero
on $s > s_*$.
\end{proof}

We can refine our analysis to study the asymptotics of the metric as
$s$ tends to $+\infty$.

\begin{prop} \label{omegalimit}
The trajectory converges to the origin as $s$ tends to $+\infty$.
\end{prop}

\begin{proof}
Recall that the $\omega$-limit set of the trajectory is the set
\[
\Omega = \{ (X^*,Y^*) : \exists \, s_n \rightarrow +\infty \; {\rm  with} \;
(X(s_n),Y(s_n)) \rightarrow (X^*,Y^*) \}.
\]
As our trajectory ultimately lies in a compact set, we know from standard theory
(\cite{Pk} \S 3.2) that $\Omega$ is a compact, connected, non-empty set that is
invariant under the flow of our equations. Moreover, $\Omega$ is contained in
the sphere ${\mathcal L}= \kappa$.

Now if $\Omega$ contains a point $(X^*, Y^*)$ with $X^* \neq 0$, we see
from (\ref{eqnLyap}) that ${\mathcal L}^{\prime}$
at this point is nonzero, contradicting the flow-invariance of $\Omega$.
Hence $\Omega$ is contained in the set $X_i=0 \; (i=1, \ldots, r)$.
 Furthermore, if
$\Omega$ contains a point $(0, Y^*)$ with $Y^* \neq 0$, we see from (\ref{eqnX}) that
some $X_i^{\prime}$ is nonzero, again contradicting flow-invariance.

Hence $\Omega = (0,0)$, and the limiting value $\kappa$ of $\mathcal L$ is
$-1$, showing that the trajectory does indeed converge to the origin.
\end{proof}

\begin{lemma}
We have $\lim_{s \rightarrow \infty} \frac{X_i}{Y_i^2} = \frac{1}{\sqrt{d_i}}$.
\end{lemma}

\begin{proof}
Observe that $X_i/Y_i^2$ satisfies the differential equation
\begin{equation} \label{eqnXY2}
\left( \frac{X_i}{Y_i^2} \right)^{\prime} =  \left(-1 -\sum_{j=1}^{r} X_j^2
+ \frac{2 X_i}{\sqrt{d_i}} \right) \frac{X_i}{Y_i^2} + \frac{1}{\sqrt{d_i}}\, .
\end{equation}
By Prop \ref{omegalimit}, the coefficient of $\frac{X_i}{Y_i^2}$ tends
to $-1$ as $s \rightarrow +\infty$. In particular, if $\frac{X_i}{Y_i^2}$
tends to a limit $a,$ then its derivative tends to
$-a + \frac{1}{\sqrt{d_i}},$ so $a$ must equal $\frac{1}{\sqrt{d_i}}$.

Let $0 < \delta < 1$, and pick $s^*(\delta)$ so that
the absolute value of $-\sum_{j=1}^{r} X_j^2 +
\frac{2X_i}{\sqrt{d_i}}$ is less than $\delta$ for $s > s^*(\delta)$.
It follows that
if $\frac{X_i}{Y_i^2} (s_0) \geq \frac{1}{\sqrt{d_i}(1 - \delta)}$
for some $s_0 > s^*(\delta),$
then $\left(\frac{X_i}{Y_i^2} \right)^{\prime} <0$ at $s_0$.
Similarly, if $\frac{X_i}{Y_i^2}(s_0) \leq \frac{1}{\sqrt{d_i}(1+\delta)}$,
 then $\left(\frac{X_i}{Y_i^2} \right)^{\prime} >0$ at $s_0$.

So if $\frac{X_i}{Y_i^2}$ enters the horizontal strip
$\frac{1}{\sqrt{d_i}(1+\delta)} < y < \frac{1}{\sqrt{d_i}(1-\delta)}$
at some $s > s^*(\delta)$ it is trapped there.
Hence one of the following must hold:

(i) $\frac{X_i}{Y_i^2} (s) \geq \frac{1}{\sqrt{d_i}(1-\delta)}$ for all $s > s^*(\delta),$

(ii) $\frac{X_i}{Y_i^2} (s) \leq \frac{1}{\sqrt{d_i}(1+\delta)}$ for all $s > s^*(\delta),$
or

(iii)
 $ \frac{1}{\sqrt{d_i}(1+\delta)}< \frac{X_i}{Y_i^2} < \frac{1}{\sqrt{d_i}(1-\delta)}$
 for $s$ sufficiently large.

In Case (i), $\frac{X_i}{Y_i^2}$ is monotonic decreasing and bounded below
by $\frac{1}{\sqrt{d_i}(1-\delta)},$ so it tends to a finite limit which
must be at least $\frac{1}{\sqrt{d_i}(1-\delta)}> \frac{1}{\sqrt{d_i}}$,
contradicting the discussion above. Case (ii) is eliminated similarly.

The remaining possibility is that (iii) holds for all $\delta$;
hence $\frac{X_i}{Y_i^2} \rightarrow \frac{1}{\sqrt{d_i}}$ as claimed.
\end{proof}

We deduce that $g_i \dot{g_i}$ asymptotically approaches the constant
$\lambda_i/\sqrt{-C}$, and obtain the following theorem.

\begin{thm} \label{asymptotics}
The metric corresponding to our trajectory is, to leading order in $t$
as $t \rightarrow +\infty$,
\[
dt^2 + t \; {\sf h}_{\infty}
\]
where the homothety class of  ${\sf h}_{\infty}$ is that of the product
Einstein metric on $M_1 \times \cdots \times M_r$.
So our metric has an asymptotically paraboloid geometry.
\end{thm}

\begin{rmk}
The Bryant solitons on $\mathbb R^n$ (for $n>2$) also have
asymptotically paraboloid geometry.  On the other hand the complete
steady K\"ahler solitons considered in \cite{DW} are asymptotically circle
bundles of constant radius over paraboloids.

These two kinds of asymptotics may be viewed as the Ricci soliton
analogues of the Asymptotically Conical (AC) and Asymptotically Locally
Conical (ALC) conditions satisfied by many of the known complete
non-compact Ricci-flat metrics (see \cite{CGLP} for example).
\end{rmk}

\section{\bf Analysing the flow}

To check smoothness at the collapsing submanifold, we must now analyse
the trajectory as $s$ tends to $-\infty$. Recall that
$X_1 \rightarrow \beta = \frac{1}{\sqrt{d_i}},
Y_1 \rightarrow +\sqrt{1- \beta^2}$ and the remaining
variables tend to 0.

\begin{rmk} \label{asympLyap}
Observe from (\ref{eqnLyap}) that $\mathcal L$ (and hence $g_i^2 Y_i^2$)
tend to zero exponentially fast as $s$ tends to $-\infty$.
\end{rmk}

The following lemma is often useful.

\begin{lemma} \label{FHKlemma}
Suppose a function $F$ satisfies a differential equation
\begin{equation} \label{eqnFHK}
F^{\prime} = H F + K
\end{equation}
where $H, K$ are functions tending respectively to finite limits
$h,  k $ as $s$ tends to $-\infty$, where $h<0$ and $k \neq 0$.

Then either $\lim_{s \rightarrow -\infty} F(s) = -\frac{k}{h}$
or $F$ tends to $\infty$ or $-\infty$ as $s$ tends to $-\infty$. Moreover
in the case of infinite limit $F$ is monotonic for sufficiently large
negative $s$.
\end{lemma}

\begin{proof}
We give the proof for the case $k > 0$ below; obvious modifications
yield the proof for the case $k < 0$.

Let $0 < \delta < {\rm min} (-h, k)$, and choose $s^*(\delta)$ so that
for all $s \leq s^*(\delta)$ we have
\[
h - \delta < H(s) < h + \delta <0 \;\; : \;\;
0< k - \delta < K(s) < k + \delta.
\]

If $F(s_0) \leq \frac{k -\delta}{-h + \delta}$ for some $s_0 \leq s^*(\delta)$,
then $F^{\prime}(s_0) >0$. Hence these inequalities for $F,F^{\prime}$
actually hold for all $s \leq s_0$. So as $s$ tends to $-\infty$, either $F$
tends to $-\infty$ (monotonically on $(-\infty, s_0]$) or to a finite limit
$\xi <  \frac{k -\delta}{-h + \delta} < -\frac{k}{h}$. But in the latter
case $F^{\prime}$ tends to a nonzero limit, which is impossible.

If $F(s_0) \geq \frac{k + \delta}{-h - \delta},$ then we similarly see that
$F$ tends monotonically to $+\infty$ as $s$ tends to $-\infty$.

So if $F$ does not tend monotonically to $\pm \infty$, we see that
for all such $\delta$ we have $\frac{k -\delta}{-h + \delta}
< F(s) < \frac{k + \delta}{-h - \delta}$ on $(-\infty, s^*(\delta)]$.
Hence $F$ tends to $-\frac{k}{h}$ as $s$ tends to $-\infty$.
\end{proof}

\begin{lemma} \label{XYbounded}
The function $X_i / Y_i^2$ is positive, and remains bounded as $s$ tends to
$-\infty$.
\end{lemma}

\begin{proof} {   }

(i) {\bf Positivity}. Note that  $(\sum_{j=1}^{r} X_j^2) -1$ is bounded
above by $\mathcal L$ so it is negative. Now since $Y_i > 0$ for all $s$,
if $X_i \leq 0$ at some $s_0$, we see that $X_i^{\prime}$ is positive at $s_0$.
Hence $X_i$ is negative and $X_i^{\prime}$ positive on $(-\infty, s_0)$, which
contradicts the fact that $\lim_{s \rightarrow -\infty} X_i =0$ (if $i>1)$,
or $\beta = \frac{1}{\sqrt{d_1}}>0$ if $i=1$. We deduce that $X_i$ is positive
for all finite $s$.

(ii) {\bf Boundedness}. This is trivial if $i=1$, so in what follows we take
$i>1$. We know that $(\sum_{i=1}^{r} X_j^2) -1$ tends to $\beta^2 -1$
and $(\sum_{j=1}^{r} X_j^2) - \frac{X_i}{\sqrt{d_i}}$ tends to $\beta^2$ as $s$
tends to $-\infty$. Pick $s^*$ so that
$(\sum_{j=1}^{r} X_j^2) - 1 < \frac{1}{2} (\beta^2 -1)<0$ and
$(\sum_{j=1}^{r} X_j^2) - \frac{X_i}{\sqrt{d_i}} > \frac{1}{2} \beta^2 > 0$
for $s \leq s^*.$ Note that this implies that $Y_i^{\prime}$ is positive on
$(-\infty, s^*]$, since, as discussed in \S 3, we can take the $Y_i$ to be positive.

Suppose that $\frac{X_i}{Y_i^2} > \frac{2}{\sqrt{d_i}(1- \beta^2)}$ at some
$s_0 \leq s^*$. It follows from our choice of $s^*$ that $X_i^{\prime}$ is
negative at $s_0$. As remarked above, $Y_i$ and $Y_i^{\prime}$ are positive
on $(-\infty, s^*]$. It follows that these inequalities for $X_i/Y_i^2$ and
the derivatives of $X_i, Y_i$ actually hold on $(-\infty, s_0]$. But this
contradicts the fact that $X_i$ tends to zero as $s$ tends to
$-\infty$. So we have the desired bound on $X_i / Y_i^2$.
\end{proof}

\begin{prop} \label{XYlimit}
For $i > 1$, we have
\[
\lim_{s \rightarrow -\infty} \frac{X_i}{Y_i^2} = \frac{1}{\sqrt{d_i}(1 + \beta^2)}.
\]
\end{prop}

\begin{proof}
  The differential equation (\ref{eqnXY2}) is of the form
  (\ref{eqnFHK}), with $h = -(1 + \beta^2)$ and $k =
  \frac{1}{\sqrt{d_i}}$.  The desired result now follows from Lemma
  \ref{FHKlemma} and Lemma \ref{XYbounded}.
\end{proof}

\begin{cor}
As $s$ tends to $-\infty$, the arclength $t$ can be chosen to tend to
zero. Moreover, we have the following limiting values for $g_i(t)$ as
$t$ tends to $0$.
\[
g_1 (0) =0 \;\; : \;\; \dot{g}_{1}(0) = 1 \;\; :  \;\; \dot{g}_{i}(0) =0  \; (i>1).
\]
\end{cor}

\begin{proof}
The first statement follows from Remark \ref{asympLyap} and equation
(\ref{st}). The statement about $g_1$ comes from (\ref{def-tgi}) using
this Remark and the fact that $Y_1$ tends to a nonzero value as $s$ tends
to $-\infty$.

Since $\dot{g_i} = \sqrt{\lambda_i} (X_i/Y_i),$ the remaining limits
follow from Prop \ref{XYbounded}, the known limits of $X_i, Y_i$,
and the fact that $\lambda_1 = d_1 -1$.
\end{proof}

\begin{prop} \label{gi}
For $i > 1$, $g_i(0)$ is finite and nonzero.
\end{prop}

\begin{proof}
Observe that $\frac{d}{ds} (g_i^2) = 2g_i^2 X_i/\sqrt{d_i},$ which is positive
for all  $s$. So $g_i^2$ tends to a finite, nonnegative limit at $s=-\infty$.

To get positivity, we consider
\[
\frac{g_i^{\prime}}{g_i} =  \frac{X_i}{\sqrt{d_i}}
=\frac{1}{2 \sqrt{d_i}} \frac{X_i}{Y_i^2}
\frac{ (Y_i^2)^{\prime}}{(\sum_{j=1}^{r} X_j^2) - \frac{X_i}{\sqrt{d_i}}}.
\]
Integrating, using Prop. \ref{XYlimit}, and observing that the
denominator in the last factor tends to $\beta^2$,  we get
a bound
\[
\frac{g_i(s^*)}{g_i(s)} \leq \exp \left(\frac{Y_i^2(s^*)- Y_i^2(s)}
{2d_i (\beta^2 -\delta)(1 + \beta^2 - \delta)} \right)
\]
(for some positive $\delta$),
giving the desired positive lower bound on $g_i(s)$.
\end{proof}

\medskip

We shall next obtain some estimates that will be useful for
studying the second derivatives of $g_i$ and $u$.

\begin{lemma} \label{X1upper}
We have $X_1 < \beta$ for all finite $s$.
\end{lemma}

\begin{proof}
We can rewrite the equation (\ref{eqnX}) for $X_1$ as
\[
X_1^{\prime} = (X_1 - \beta) \left( {\mathcal L} - \sum_{j=1}^{r} Y_j^2 \right)
+ \beta \left({\mathcal L} - \sum_{j=2}^{r} Y_j^2 \right).
\]
The terms in the second and third brackets are negative for finite
$s$, since $\mathcal L$ is. Hence if $X_1 \geq \beta$ at some $s_0$ we
see $X_1^{\prime}$ is negative at $s_0$, and hence these inequalities
hold on $(-\infty, s_0]$. It follows that $X_1$ cannot tend to $\beta$
as $s$ tends to $-\infty$, a contradiction.
\end{proof}

Recalling that $\mathcal L$ is negative on our trajectory, this shows that
$\frac{X_1 - \beta}{\mathcal L}$ is positive.

\smallskip

We note next that $(X_1 - \beta)/{\mathcal L}$ satisfies the differential
equation
\[
\left(\frac{X_1 - \beta}{\mathcal L} \right)^{\prime} = \left(\frac{X_1 - \beta}{\mathcal L}
\right) \left( -1 - \sum_{j=1}^{r} X_j^2 \right) + \beta \left(
\frac{ \sum_{j=1}^{r} X_j^2 + Y_1^2 -1 }{\mathcal L} \right).
\]
Observe also that
\[
\rho := \lim_{s \rightarrow -\infty} \frac{ \sum_{j=1}^{r} X_j^2 + Y_1^2 -1}{\mathcal L}
\]
exists and is a finite number greater than $1$, because the
numerator is ${\mathcal L} - \sum_{j=2}^{r} Y_j^2$, and we know for
$j>1$ that $Y_j^2 / {\mathcal L}$ tends to a finite negative limit as
$s$ tends to $-\infty$ (as this is a negative constant times $g_j^{-2}$).

Now Lemma \ref{FHKlemma} shows that as $s$ tends to
$-\infty$, $\frac{X_1 - \beta}{\mathcal L}$ either tends to infinity
or tends to the positive limit $\frac{\beta \rho}{1  + \beta^2}$.
Moreover, because it cannot tend to $-\infty$, Lemma \ref{FHKlemma}
gives a positive lower bound on $\frac{X_1 - \beta}{\mathcal L}$.

\begin{rmk} \label{asymp} We can make some statements about the decay
  rates of our variables as $s$ tends to $-\infty$.  From (\ref{eqnY})
  we see that for $i > 1$ we have $Y_i \sim e^{\beta^2 s}$, hence, by
 Prop. \ref{XYlimit}, we also have $X_i \sim e^{2 \beta^2 s}$.
It follows from (\ref{eqnLyap}) that ${\mathcal L}
  \sim e^{2 \beta^2 s}$. Now the remarks in the previous paragraph show
  that $X_1 - \beta$ decays more slowly than $e^{(2 \beta^2 +
    \delta)s}$, for any positive $\delta$.
\end{rmk}

\begin{lemma} \label{XbLfin}
The quantity $\frac{X_1 - \beta}{\mathcal L}$ cannot tend to $\infty$ as $s$ tends
 to $-\infty$.
\end{lemma}

\begin{proof}
Observe that
\begin{equation} \label{Ybhat}
\frac{(Y_1 - \hat{\beta})^{\prime}}{{\mathcal L}^{\prime}} = \frac{Y_1}{2 \sum_{j=1}^{r} X_j^2}
\left( \frac{\sum_{j=2}^{r} X_j^2}{\mathcal L} + \frac{X_1 (X_1 - \beta)}{\mathcal L} \right).
\end{equation}
Now the term outside the bracket tends to a nonzero finite limit,
and the first term in the bracket tends to zero. So if
$\frac{X_1 - \beta}{\mathcal L}$ tends to $+\infty$, so does
$\frac{(Y_1 - \hat{\beta})^{\prime}}{{\mathcal L}^{\prime}}$, and hence,
by L'H\^{o}pital's rule, so does $\frac{Y_1 - \hat{\beta}}{\mathcal L}$.
But
\[
\frac{\sum_{j=1}^{r} X_j^2 + Y_1^2 - 1}{\mathcal L} =
\frac{ 2 \beta (X_1 - \beta) + 2 \hat{\beta} (Y_1 - \hat{\beta}) +
(X_1 - \beta)^2 + (Y_1 - \hat{\beta})^2  + \sum_{j=2}^{r} X_j^2}{\mathcal L}
\]
The discussion in Remark \ref{asymp} shows
 the first two terms are the dominant ones, so we deduce the expression
on the left-hand-side tends to $+\infty$, which we saw above is false.
\end{proof}

We now have
\begin{prop} \label{XbLlimit}
\[
\lim_{s \rightarrow -\infty} \left( \frac{X_1 - \beta}{\mathcal L} \right) =
\frac{\beta \rho}{1 + \beta^2}.
\]
\end{prop}

\begin{prop} \label{Lasymp}
As $s$ tends to $-\infty$, $e^{-2 \beta^2 s} {\mathcal L}$ tends to a finite
negative limit.
\end{prop}

\begin{proof}
Letting $F = e^{-2 \beta^2 s} {\mathcal L}$, (so that $F$ is negative),
 we see that
\[
F^{\prime} = 2F ( (\sum_{j=1}^{r} X_j^2) - \beta^2 ).
\]
As in the proof of Lemma \ref{XbLfin}, we see that the  dominant term in
the bracket is $2 \beta (X_1 - \beta),$ which is negative by Lemma \ref{X1upper}.
So $F$ is monotonic increasing for large negative $s$.

The proposition is proved if we can show that $F$ is bounded below near
$s=-\infty$. This follows by estimating the integral of the right-hand side
of the above equation over an interval $(-\infty, s^*]$ on which we have
bounds of the form
$$ |X_1 - \beta| \leq A\exp(2(\beta^2 -\delta)s), \ \ \ \ \ \  |X_j(s)| \leq C_j \exp(2(\beta^2 -\delta)s)$$
$$ |X_1 + \beta| \leq 2\beta + \delta, \ \ \ \ \ \
      |{\mathcal L}| \leq B \exp(2(\beta^2 - \delta)s)$$
where $\delta, A, B, C_j, 2 \leq j \leq r$ are appropriate positive constants
(cf Remark \ref{asymp}).
\end{proof}

We can now check the second derivatives of $g_i$ at $t=0$. Recall that
from (\ref{gidotdot}) we have
\[
\ddot{g}_i = \frac{\lambda_i}{g_i Y_i^2} (X_i^2 + Y_i^2 - \sqrt{d_i} X_i).
\]
It is now clear from Prop \ref{XYlimit}
and Prop \ref{gi} that for $i >1$, $\ddot{g_i}$ tends
to a finite limit as $t$ tends to zero.

If $i=1$, we rewrite this expression, using (\ref{def-Yi})-(\ref{cons2}), as
\[
\ddot{g_1} = \frac{\lambda_1}{Y_1} \left(\frac{1 - \sqrt{d_1}X_1}{g_1 Y_1}\right)
+ g_1 \left( \frac{C}{d_1} - \sum_{j=2}^{r}
\frac{d_j \lambda_j}{d_1} \frac{1}{g_j^2} \left(\frac{X_j^2}{Y_j^2} + 1\right) \right).
\]
The quantities in the bracket after $g_1$ tend to finite limits, so
$g_1$ times that bracket tends to zero.
As $Y_1$ tends to $\hat{\beta} \neq 0$, we see from
Prop \ref{XbLlimit} and (\ref{cons2}) that the first term also tends to zero.

We have therefore shown the metric is $C^2$.

Similarly we can study the potential $u$. From the relation (\ref{def-u})
we obtain
\begin{equation} \label{u1}
\dot{u} = \sqrt{\frac{C}{\mathcal L}} \left(\left(\sum_{j=1}^{r} \sqrt{d_j} X_j\right) -1 \right)
= \sqrt{d_1}\left(\frac{ (X_1 - \beta)}{\sqrt{{\mathcal L}/C}}\right)
+ \sum_{i=2}^{r} \sqrt{d_i}\left(\frac{X_i}{Y_i^2}\right) \left(\frac{Y_i^2}{\sqrt{{\mathcal L}/C}}\right).
\end{equation}
By Prop \ref{XYlimit}, Remark \ref{asymp}, and Prop \ref{XbLlimit}, it follows
that $\dot{u}$ tends to zero as $t$ tends to $0$. Next, by integrating (\ref{def-u})
we get
\begin{equation} \label{u0}
e^{u(0)} = ({\rm positive \; constant })
\prod_{i=2}^{r} \, g_i(0)^{d_i} \left(\lim_{s \rightarrow
-\infty} e^{-2 \beta^2 s} \frac{\mathcal L}{C}\right)^{\frac{d_1}{2}},
\end{equation}
which is finite by Prop \ref{Lasymp}. If we differentiate (\ref{def-u}) and
use (\ref{eqnLyap}) we get
\begin{equation} \label{u2}
\ddot{u} = \sum_{i=1}^{r} \, d_i \frac{\ddot{g_i}}{g_i}
= \sum_{i=1}^{r} \frac{\lambda_i d_i}{g_i^2 Y_i^2} \left(X_i^2 + Y_i^2 -\sqrt{d_i}X_i \right).
\end{equation}
The right-hand side tends to a finite limit (as $t$ tends to $0$) by
Props \ref{gi}, \ref{XbLlimit}, the relation (\ref{cons2}) and the discussion
after Prop \ref{Lasymp}.

For the third derivatives, we calculate
\[
\frac{d^3 g_i}{dt^3} = \sqrt{\frac{C}{{\mathcal L}}} \frac{\lambda_i}{g_i}
\left( \frac{X_i}{Y_i^2} \left(
 -3X_i + \frac{X_i^2}{\sqrt{d_i}} + \sqrt{d_i} + \sqrt{d_i}
\sum_{j=1}^{r} X_j^2 \right)
+ \frac{X_i}{\sqrt{d_i}} -1 \right).
\]
If $i > 1$, we know that the terms in $\frac{X_i}{\sqrt{\mathcal L}},
\frac{X_i^2}{Y_i^2 \sqrt{\mathcal L}},
\frac{X_i^3}{Y_i^2 \sqrt{\mathcal L}}$ tend to zero (cf Remark \ref{asymp}).
Our task thus reduces to showing that
\[
\frac{1}{\sqrt{\mathcal L}} \left(\frac{X_i}{Y_i^2} (1 + \sum_{j=1}^{r} X_j^2 )
 -\frac{1}{\sqrt{d_i}} \right)
\]
tends to zero.

Now, $1 + \sum_{j=1}^{r} X_j^2 = 1 + \beta^2$ modulo terms approaching
zero at least as fast as $\mathcal L$, so we just have to check that
\[
\lim_{s \rightarrow -\infty}
  \frac{1}{\sqrt{\mathcal L}} \left(\frac{X_i}{Y_i^2} -
  \frac{1}{\sqrt{d_i}(1 + \beta^2)}\right) =0.
\]
In fact we shall show the stronger statement that
\[
Q_i := \frac{1}{\mathcal L} \left( \frac{X_i}{Y_i^2}
- \frac{1}{\sqrt{d_i}(1 + \beta^2)}\right)
\]
tends to a finite limit.
We find that $Q_i$ satisfies the equation
$$ Q_i^{\prime} = -\left(1+ 3 \sum_{j=1}^r X_j^2 \right) Q_i
  + \frac{1}{(\sqrt{d_i}(1+ \beta^2))\mathcal L} \left(2(1+\beta^2) \frac{X_i^2}{Y_i^2}
    + \beta^2 - \sum_{j=1}^r X_j^2 \right). $$
By arguments similar to those above, one sees that the second term on
the right-hand side tends to a finite negative limit
as $s \rightarrow -\infty$ since $X_1 < \beta$ and ${\mathcal L} < 0.$
So the hypotheses of Lemma \ref{FHKlemma} are satisfied, and $Q_i$ either
tends to a finite limit or to $+\infty$ or $-\infty$.  But
\[
\frac{\left(\frac{X_i}{Y_i^2} - \frac{1}{\sqrt{d_i}(1 + \beta^2)}\right)^{\prime}}
{{\mathcal L}^{\prime}}
=
\frac{\left(\frac{X_i}{Y_i^2} - \frac{1}{\sqrt{d_i}(1 + \beta^2)}\right)}
{\mathcal L} \left( \frac{-(1 + \beta^2)}{2 \sum_{j=1}^{r} X_j^2} \right)
+ R_i
\]
where $R_i$ tends to a finite limit. So
if the limit of $Q_i$ is infinite, L'H\^{o}pital's rule gives a
contradiction, as the term in the final bracket is negative.

For $i=1$, by (\ref{def-tgi}) and $Y_1(0)=\hat{\beta},$ it is enough to check that
\[
\frac{ -3 (\frac{X_1}{Y_1})^2 + \beta \frac{X_1^3}{Y_1^2} + \beta X_1 -1
+  \frac{X_1}{\beta Y_1^2} (1 + \sum_{j=1}^{r} X_j^2)  }
{\mathcal L}
\]
has a finite limit.
Recall that $1 + \sum_{j=1}^{r} X_j^2 =1 + \beta^2$ modulo terms
which have a finite limit when divided by $\mathcal L$. Similarly
$X_1^k = \beta^k$ modulo such terms. So we are left with checking
that the limit of $\frac{Y_1^2 - \hat{\beta}^2}{\mathcal L}$ is finite, which follows
on applying L'H\^{o}pital's rule, equation (\ref{Ybhat}) and Prop. \ref{XbLlimit}.

\medskip

We have shown that the metric is $C^3$ and so by the discussion on regularity
near the beginning of \S 3, the soliton is smooth.

\begin{thm} \label{mainthm}
Let $M_2, \ldots, M_r$ be compact Einstein manifolds with positive scalar
curvature. For $d_1 > 1$ there is an $r-1$ parameter family of complete smooth
steady Ricci solitons on the trivial  rank $d_1 + 1$ vector bundle
over $M_2 \times \ldots \times M_r$.  \qed
\end{thm}

The examples of Ivey and Bryant have nonnegative Ricci curvature. This is
also true for our more general examples.

\begin{prop} \label{ricci}
The soliton metrics have nonnegative Ricci curvature.
\end{prop}

\begin{proof}
It is enough to show that the Ricci curvature is positive on the complement
of the submanifold at $t=0$, i.e., on the finite part of the trajectory.
The Hessian of $u$ is given by $\ddot{u}$ evaluated on directions normal
to the hypersurface and by $\frac{\dot{u} \dot{g_i}}{g_i}$ evaluated on
directions tangent to $M_i$. From the soliton equation (\ref{gradRS})
(with $\epsilon = 0$), the formulae (\ref{u0}), (\ref{u1}), (\ref{u2}),
(\ref{cons2}) above for $\dot{u}, \ddot{u}$ and the fact, proved in Prop (\ref{gi}),
that $\frac{\dot{g}_{i}}{g_i}$ is positive, it is enough to check that
\[
{\mathcal H}= \sum_{i=1}^{r} \sqrt{d_i} X_i,
\]
introduced in Remark \ref{einstein}, satisfies ${\mathcal H} < 1$ and
${\mathcal L} + 1 - {\mathcal H} < 0$ for all $s$.

Now it is easy to check that we have equations
\[
({\mathcal H}-1)^{\prime} = ({\mathcal H}-1) ( \sum_{j=1}^{r} X_j^2  -1 )
 + \mathcal L
\]
and
\[
({\mathcal L} + 1 - {\mathcal H})^{\prime} =
({\mathcal L} + 1 - {\mathcal H}) (\sum_{j=1}^{r}
X_j^2 -1 ) + {\mathcal L} (\sum_{j=1}^{r} X_j^2).
 \]
 Moreover $\sum_{j=1} X_j^2 - 1$ and $\mathcal L$ are negative.  So if
 ${\mathcal H} \geq 1$ at $s_0$ then ${\mathcal H}^{\prime} <0$ and
 ${\mathcal H} > 1$ on $(-\infty, s_0)$, contradicting the fact that
 $\mathcal H$ tends to $1$ as $s$ tends to $-\infty$. Similarly if
 ${\mathcal L} +1 -{\mathcal H}$ is non-negative at $s_0$, then we see it
 is positive with negative derivative on $(-\infty, s_0)$,  contradicting
 the fact that ${\mathcal L} + 1-{\mathcal H}$ tends to zero.
\end{proof}

\begin{rmk} \label{sectcurv}
For a multiply-warped product $I \times M_1 \times \cdots \times M_r$ with
metric of the form (\ref{metric}) it is easy to compute the sectional curvatures,
e.g., by considering it as a Riemannian submersion over $I$. If $U, V$ are
respectively tangent to  $M_i$ and $M_j$, one has
\begin{eqnarray*}
 K(U \wedge \frac{\partial}{\partial t}) & = & -\frac{\ddot{g}_i}{g_i}  \\
 K(U \wedge V) &=& -\frac{\dot{g}_i \dot{g}_j}{g_i g_j}, \, \, \, \, i \neq j, \\
 K(U \wedge V) &=& \frac{1}{g_i^2} \left(K_{h_i}(U \wedge V) - \dot{g_i}^2  \right), \, \, i=j,
\end{eqnarray*}
where $K_{h_i}$ denotes the sectional curvature of $(M_i, h_i)$.

It now follows from the asymptotics described in Theorem \ref{asymptotics}
that if $r > 1$ there are always $2$-planes with negative sectional curvature.
If $r=1$, we are in the case of the Bryant solitons, which are known to have positive
curvature ([Bry] or [Cetc Lemma 1.37]). The above formulas also show
that the sectional curvatures decay like $t^{-1}$ as $t$ tends
to $+\infty$. Recall that the {\em asymptotic scalar curvature ratio} of a
complete, non-compact Riemannian manifold is defined as
$\limsup_{d \rightarrow +\infty}  R d^2$, where $R$ is the scalar curvature
and $d$ is the distance from a fixed origin in the manifold. Since $t$ is the
geodesic distance in our examples, it follows that their asymptotic scalar
curvature ratios are all $+\infty$.
\end{rmk}


text:
\section*{Broader Impact}
The central concern of this investigation is Bayesian optimization of an expensive-to-evaluate objective function. As is standard in this body of literature, our proposed algorithms make minimal assumptions about the objective, effectively treating it as a ``black box.'' This abstraction is mathematically convenient but ignores ethical issues related to the chosen objective.  Traditionally, Bayesian optimization has been used for a variety of applications, including materials design and drug discovery \citep{frazier2018tutorial}, and could have future applications to algorithmic fairness. We anticipate that our methods will be utilized in these reasonable applications, but there is nothing inherent to this work, and Bayesian optimization as a field more broadly, that preclude the possibility of optimizing a nefarious or at least ethically complicated objective.


TITLE: Is $f(x)=\frac{\sin(x)}{\cos(2x)}+\sin(x)-\cos(x)$ strictly positive?
QUESTION [0 upvotes]: I would like to have an advice for this exercise.

Let $x\in[0,\pi]$ For which values of $x$ this function $$f(x)=\frac{\sin(x)}{\cos(2x)}+\sin(x)-\cos(x)$$ is strictly positive ?

I tried to compute the derivative, i get so far $$f'(x)=\frac{\cos(x)\cos(2x)+2\sin(x)\sin(2x)}{\cos(2x)^2}+\cos(x)-\sin(x).$$
Using the fact that $\cos(2x)=1-2\sin(x)^2$ we have $$f'(x)=\frac{\cos(x)}{\cos(2x)^2}+\cos(x)-\sin(x)=\cos(x)\bigl(\frac{1}{\cos(2x)^2}+1-\frac{\sin(x)}{\cos(x)}\bigr).$$  I'm not sure I simplify my problem. Any ideas ?

REPLY [1 votes]: Hint: write $$f(x) = \dfrac{\ldots}{\cos(2x)}$$ and simplify the numerator.  Then look at the intervals between points where the numerator or denominator is $0$.
EDIT:
$$ f(x) = \dfrac{\cos(x) \left(2 \sin(x) \cos(x) - 2 \cos(x)^2 + 1\right)}{\cos(2x)} = \dfrac{\cos(x) \left(\sin(2x) - \cos(2x)\right)}{\cos(2x)}$$


TITLE: Sequences of Coefficients in $a p^i + b q^j = 1$
QUESTION [0 upvotes]: Let $p$ and $q$ be different primes. Then for all positive integers $i$ and $j$ there exists integers $a_{ij}$ and $b_{ij}$ with
$$ a_{ij} p^i + b_{ij} q^j = 1.$$
What is known about the sequence $\left((a_{ij},b_{ij})\right)_{i,j}$ of coefficients? Is there an explicit formula for calculating them? If no, is there a subsequence $i_k$, $j_k$  of indices, for which the sequence of coefficients $a_{i_kj_k}$ and $b_{i_kj_k}$ are known?

REPLY [1 votes]: At least some things can be said. Say we are looking at $a_{ij}p^i-b_{ij}q^j=1$ with $0\lt a_{ij}\lt q^j$ and $0\lt b_{ij}\lt p^i$. Then for fixed $j$ there are at most $q^j-q^{j-1}$ possible values for  $a_{ij}.$ These values cycle periodically with each completely determined by the previous. (the period is likely to be too large to be practical though) and knowing any $a_{ij}$ yields the corresponding $b_{ij}$ Furthermore, $a_{0j}=1$ and $b_{0j}=0$. Similar remarks holds for fixed $i$ with $j$ allowed to grow. None of this is very useful computationally.
To partially avoid subscripts for the moment, let $a_{ij}p^i-b_{ij}q^j=1$ and also $up^{i+1}-vq^j=1$. Since  $(up)p^i-vq^j=1$ we know that $up=a_{ij}+mq^j$ and $v=b_{i,j}-mp^i$ where $0 \le m \le p-1$ is the unique value making $\frac{a_{ij}+mq^j}{p}$ an integer. For example, in the simplest case of $p=2$ , we either have $a_{i+1,j}=a_{ij}/2$ and $b_{i+1,j}=b_{i,j}$ or else $a_{i+1,j}=(a_{ij}+q^j)/2$ and $b_{i+1,j}=b_{i,j}-2^i$ according as $a_{ij}$ is even or odd.
Also, we only need that $p$ and $q$ are relatively prime.


TITLE: Inversion inequalities
QUESTION [2 upvotes]: Do there exist $n$ permutations $(\pi_i; 1 \le i \le n)$ of $[k]$ such that for any transposition $\sigma = (j, l)$, $1 \le j, l \le k$,
\begin{equation}
\label{1}
(*) \quad \sum_{i = 1}^n inv(\pi_i \circ \sigma) > \sum_{i = 1}^n inv(\pi_i),
\end{equation}
where $inv(\pi_i)$ is the number of inversions of $\pi_i$,
but
\begin{equation}
(**) \quad \sum_{i = 1}^n inv(\pi_i \circ \pi) \le \sum_{i = 1}^n inv(\pi_i) \quad \mbox{for some permutation } \pi \neq id ?
\end{equation}
The answer is no for n = 1 and 2, since $inv(\pi_i \circ \sigma) = inv(\pi) \pm 1$ for any adjacent transposition $\sigma$. In these cases, $(*)$ implies that $\pi_i = id$ and $(**)$ is automatically true. The answer also seems to be negative for $\pi$ a permutation of adjacent three elements, e.g. $(2,3,1)$.
I want to know if any positive or negative result holds in general.

REPLY [2 votes]: The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by
$$\big\{\  [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$
$$ [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3]\ \big\}$$
and $\pi = [2, 3, 4, 1]$ do the job. In fact, the total number of inversions in this set is decreased by 5 when the elements are multiplied by $\pi$, while multiplying them by any transposition increases the total number of inversions by at least 1.

ADDED. A smaller set example for the same $\pi = [2, 3, 4, 1]$:
$$\{ [1, 2, 3, 4], [3, 4, 1, 2], [4, 1, 2, 3] \}.$$


TITLE: What happens to this theorem when we enlarge (or shorten) the set of elementary functions?
QUESTION [2 upvotes]: I'm having lectures on complex analysis, there is this theorem:

I got a bit curious about the following: Having an antiderivative depends also on our choice of elementary functions, I am aware that we can enlarge (or shorten) this set (at least this is what was told to me in elementary calculus lectures, the professor gave a demonstration that$f(x) =\frac{1}{x}$ does not have an antiderivative if the set of elementary functions is the set of polynomial functions. This seemed to imply that the choice of this set is arbitrary).
So what happens to this theorem when we enlarge (or shorten) the set of elementary functions? Does it only work for the the standard set of elementary functions?

REPLY [6 votes]: This statement is wrong: ”Having an antiderivative depends also on our choice of elementary functions”.
A function $f$ may or may not have an antiderivative. If it have an antiderivative $F$, that's independent of what kind of functions you are willing to accept as elementary.
We say, for example, that $f(x) = e^{x^2}$ doesn't have an elementary antiderivative not because it doesn't have an antiderivative, but because its antiderivative is not elementary.


TITLE: For what exactly we need that the submartingale is a finite sequence in theorem 6.7.3 of Ash's book?
QUESTION [1 upvotes]: I want to check if my understanding of the following proof is correct. The following is a slight rephrasing of a theorem of Ash's probability book:

6.7.3 Theorem. Let $\{X_n:n=1,\ldots ,m\}$ a submartingale and let $T_1,T_2,\ldots $ an increasing sequence of stopping times for the $\mathscr{F}_n$ (that is, $\{\omega :T_n(\omega )\leqslant j\}\in \mathscr{F}_j$ for each $n$, and each $T_n$ take values in $\{1,\ldots ,m\}$). Now let $$\mathscr{F}_{T_i}:=\{A\in \mathscr{F}: A\cap \{\omega :T_i(\omega )\leqslant k\}\in \mathscr{F}_k\}$$ Then the $X_{T_n}$ form a submartingale respect to the $\mathscr{F}_{T_n}$.

There we defines $X_{T}(\omega ):=X_n(\omega )$ whenever $T(\omega )=n$. Now the proof:

Set $Y_n:=X_{T_n}$ and note that $$\int_{\Omega }|X_{T_n}|\mathop{}\!d P=\sum_{k=1}^m\int_{\{\omega : T_n(\omega )=k\}}|X_k|\mathop{}\!d P\leqslant \sum_{k=1}^m\mathrm{E}[|X_k|]<\infty\tag1 $$ As the $T_n$ increases with $n$ so does $\mathscr{F}_{T_n}$. Now if $A\in \mathscr{F}_{T_n}$ then we must show that $\int_{A}Y_{n+1}\mathop{}\!d P\geqslant \int_{A}Y_n\mathop{}\!d P$. Since $A=\bigcup_{j}A\cap \{T_n=j\}$ it suffices to replace $A$ in the integral by $D_j:=A\cap \{T_n=j\}$, wich belong to $\mathscr{F}$.
Now note that if $k>j$ then $T_n=j$ implies $T_{n+1}\geqslant j$, hence $$\int_{D_j}Y_{n+1}\mathop{}\!d P=\sum_{i=j}^k\int_{D_j\cap \{T_{n+1}=i\}}Y_{n+1}\mathop{}\!d P+\int_{D_j\cap \{T_{n+1}>k\}}Y_{n+1}\mathop{}\!d P\tag2$$ so
$$\int_{D_j}Y_{n+1}\mathop{}\!d P=\sum_{i=j}^k\int_{D_j\cap \{T_{n+1}=i\}}X_i\mathop{}\!d P+\int_{D_j\cap \{T_{n+1}>k\}}X_k\mathop{}\!d P-\int_{D_j\cap \{T_{n+1}>k\}}(X_k-Y_{n+1})\mathop{}\!d P\tag3$$ and from the definitions its easy to see that $$\int_{D_j\cap \{T_{n+1}\geqslant k\}}X_k\mathop{}\!d P\geqslant \int_{D_j\cap \{T_{n+1}\geqslant k\}}X_{k-1}\mathop{}\!d P\tag4$$ Then by a finite recursion we find that $$\int_{D_j}Y_{n+1}\mathop{}\!d P\geqslant \int_{D_j\cap \{T_{n+1}\geqslant j\}}X_j\mathop{}\!d P-\int_{D_j\cap \{T_{n+1}>k\}}(X_k-Y_{n+1})\mathop{}\!d P\tag5$$
Now $\{T_{n+1}>k\}$ is empty for $k\geqslant m$. Finally, $D_j\cap \{T_{n+1}\geqslant j\}=D_j$ since $D_j\subset \{T_{n}=j\}$, and $X_j=Y_n$ in $D_j$. Thus $$\int_{D_j}Y_{n+1}\mathop{}\!d P\geqslant \int_{D_j}Y_n\mathop{}\!d P\tag6$$

This means that $-\int_{D_j\cap \{T_{n+1}>k\}}(X_k-Y_{n+1})\mathop{}\!d P>0$, what is a consequence of $\{X_n\}$ being a submartingale, ok. But this is my question: for what exactly was used that $\{X_n\}$ was a finite sequence? Just to prove that the $Y_j\in L^1(P)$? It seems that it is used for a different step, as Ash says just after the end of this proof

Theorem 6.7.3 extends immediately to the case of an infinite sequence if
each $T_n$ is bounded, that is, for each $n$ there is a positive constant $K_n$ such that $T_n \le K_n$ a.e. The same proof may be used; the key point is that $\{T_{n+1} > k\}$ is still empty for sufficiently large $k$.

This seems to imply that the finiteness of the sequence $\{X_k\}$ is used in the conclusion (6) from (5), that is, that the RHS of (5) is finite or so. It is not so clear. Can someone clarify it?

REPLY [0 votes]: Lots of typos in the question---just to point out a couple:

"...$\{\omega :T_n(\omega )\leqslant j\}\in \mathscr{F}_n...$" should be "...$\{\omega :T_n(\omega )\leqslant j\}\in \mathscr{F}_j$...".

"...$X_{T}(\omega ):=T(\omega )$..." should be "...$X_{T}(\omega ):=X_{T(\omega )}(\omega)$...".

Now to answer your question:

...where exactly was the assumption that $m < \infty$ (in $\{X_n:n=1,\ldots ,m\}$) used in the
argument?

The answer is nowhere, really. Note that the argument only involves two adjacent elements $Y_{n+1} = X_{T_{n+1}}$ and $Y_{n} = X_{T_{n}}$. This would remain the same regardless whether $m$ is finite or infinite.
Rather, the key to the argument is the assumption that the sequence of stopping times $\{ T_n \}$ is bounded. For example, the assumption you mention that $T_n < K_n\;\; a.s.$ would suffice (where the sequence $K_n$ may diverge to $\infty$).
Under the assumption that $T_n < K_n\;\; a.s.$, the same argument goes through verbatim for a submartingale $\{  X_n \}_{n \geq 1}$:
Proof:
Integrability of $Y_n$ holds exactly the same as before:
$$
\int |Y_n| dP = \sum_{j = 1}^{K_n} \int_{\{T_n = j\}} |X_{j}| dP < \infty.
$$
Let $A \in \mathscr{F}_{T_n}$, then $A\stackrel{(1)}{=}\bigsqcup\limits_{j=1}^{K_n } A\cap \{T_n=j\}$. Therefore it suffices to consider
$$
D_j = A \cap \{T_n=j\}
$$
for some $1 \leq j \leq K_n$. So $Y_n \cdot 1_{D_j} = X_{T_j} \cdot 1_{D_j}$.
On the other hand,
$$
\int_{ D_j } Y_{n+1} dP \stackrel{(2)}{=}
\sum_{i = j }^{K_{n+1}} \int_{ D_j  \cap \{ T_{n+1} = i \} } Y_{n+1} dP
= \sum_{i = j }^{K_{n+1}} \int_{ D_j  \cap \{ T_{n+1} = i \} } X_i dP
\geq  \int_{ D_j } X_j dP = \int_{ D_j } Y_{n} dP.
$$
End of Proof.
With the additional assumption that $\{  X_n \}_{n \geq 1}$ is, say, dominated by an $Z \in L^1_+$, i.e. $|X_n| \leq Z \; a.s.$, each element of the stopping time sequence $\{ T_n \}$ can be allowed to be unbounded:

$\int |Y_n| dP = \sum\limits_{j = 1}^{\infty} \int_{\{T_n = j\}} |X_j| dP \leq \int Z dP < \infty$.

"$\stackrel{(1)}{=}$" becomes $A = \bigsqcup\limits_{j=1}^{\infty } A\cap \{T_n=j\}$. Therefore it still suffices to consider
$$
D_j = A \cap \{T_n=j\}.
$$

"$\stackrel{(2)}{=} $" becomes $\int\limits_{ D_j } Y_{n+1} dP =
\sum\limits_{i = j }^{\infty} \int\limits_{ D_j  \cap \{ T_{n+1} = i \} } Y_{n+1} dP$. Now, for each finite $m$,
$$
\sum\limits_{i = j }^{m} \int\limits_{ D_j  \cap \{ T_{n+1} = i \} } Y_{n+1} dP
\geq \sum\limits_{i = j }^{m} \int\limits_{ D_j  \cap \{ T_{n+1} = i \} } Y_{n} dP.
$$
So the submartingale property follows from the Dominated Convergence Theorem.

One can probably construct counterexamples where the $L^1$-dominated condition does not hold, each $T_n$ is unbounded, and $\{ X_{T_n} \}$ is no longer a submartingale.


TITLE: Cantor ternary set problem
QUESTION [1 upvotes]: Let C be a cantor ternary set
If $x,y \in C,$ then obviously $x-y \in [-1,1]$
Conversely I want to prove that
if $w \in [-1,1],$ then there exists $x,y \in C$ such that $x-y=w$
How to prove this problem?

REPLY [3 votes]: Let $w$ in $[-1,1]$, then $w=-1+2u$ with $u$ in $[0,1]$. Like every number in $[0,1]$, $u$ can be written in base $3$, that is, as a series of negative powers of $3$, namely,
$$
u=\sum\limits_{k\geqslant1}\frac{u_k}{3^k},\qquad u_k\in\{0,1,2\}.
$$
Let $w_k=2u_k-2$, hence $w_k$ is in $\{-2,0,2\}$. Then
$$
w=-1+\sum\limits_{k\geqslant1}\frac{w_k+2}{3^k}=\sum\limits_{k\geqslant1}\frac{w_k}{3^k}.
$$
For every $k\geqslant1$, define

$x_k=0$ and $y_k=2$ if $w_k=-2$,
$x_k=y_k=0$ if $w_k=0$,
and $x_k=2$ and $y_k=0$ if $w_k=2$.

Then $w_k=x_k-y_k$ for every $k$ hence $w=x-y$ with
$$
x=\sum\limits_{k\geqslant1}\frac{x_k}{3^k},\qquad
y=\sum\limits_{k\geqslant1}\frac{y_k}{3^k}.
$$
Since $x_k$ and $y_k$ are in $\{0,2\}$ for every $k$, both $x$ and $y$ are in $C$.


TITLE: Confused about exponents and imaginary/real answers
QUESTION [5 upvotes]: I am confused about some exponent behavior.
$$(-2)^{7.6} = (-2)^{\frac{76}{10}} = ((-2)^{76})^{\frac{1}{10}} = ((-2)^{\frac{1}{10}})^{76}$$
Is there something wrong in this logic?  When I plug the different versions into Mathematica, I get complex number for the first two versions, and real numbers for the last two.  And, the last two are opposite in sign.  What am I missing?

REPLY [7 votes]: $x^y$ is multi-valued unless either $y$ is an integer or $x$ is real and positive.
In the general case one has to define $x^y = e^{y\log x}$, which inherits the ambiguity of the complex logarithm.
Even for $x>0$, $y\not\in\mathbb Z$, this general definition in principle leads to multiple complex values, but then it makes sense to adopt a convention that real logarithm of $x$ is used. In other cases there is no such common convention -- it isn't possible to fix one convention such that the exponentiation rules always hold anyway.


TITLE: If we have $A = AB$, what can we conclude about $B$?
QUESTION [4 upvotes]: If we have matrices $A$ and $B$ ($A$ not necessarily square), and $A = AB$, what can we conclude about $B$? I know that the rank of $B$ needs to be at least the rank of $A$, but I bet more could be said.
As a related question, I'm also curious what are some conditions for $A = AB \Rightarrow B = I$ to be true.

REPLY [3 votes]: The rank of $B$ is at least equal to the rank of $A$, because
$$
\operatorname{rank}(A)=\operatorname{rank}(AB)\le\operatorname{rank}(B)
$$
Now, in order to analyze further the problem, you can assume $A$ is in reduced row echelon form, because if $E$ is an invertible matrix such that $EA$ is in RREF, then $EAB=EA$.
Now consider a permutation matrix $P$ such that $AP$ has the block form
$$
AP=\left[\begin{array}{c|c} I_r & C \\ \hline 0 & 0 \end{array}\right]
$$
(permute the columns in such a way that the pivot columns are at the beginning in the right order to form the block $I_r$, where $r$ is the rank of $A$). Then you have
$$
AP=APP^{-1}BP
$$
and if we decompose $P^{-1}BP$ in compatible blocks
$$
P^{-1}BP=\left[\begin{array}{c|c} B_1 & B_2 \\ \hline B_3 & B_4 \end{array}\right]
$$
we have
$$
\left[\begin{array}{c|c} I_r & C \\ \hline 0 & 0 \end{array}\right]=
\left[\begin{array}{c|c} B_1+CB_3 & B_2+CB_4 \\ \hline 0 & 0 \end{array}\right]
$$
and so we need $B_1+CB_3=I_r$ and $B_2+CB_4=C$.
Note: the block $C$ does not exist if $A$ has full column rank; in this case $A$ has a left inverse and $AB=A$ implies $B$ is the identity.
The condition $AB=A$ can also be expressed as $A(B-I)=0$; if $A$ hasn't full column rank then its null space is nonzero; take $v\ne0$ such that $Av=0$ and build the matrix
$$
B=[v\ v\ \dots \ v]+I
$$
Then $AB=A$ and $B\ne I$.