TITLE: Clarification of definition of category
QUESTION [2 upvotes]: Need the set of objects and the set of non-id morphisms be disjoint? If not, can the morphisms be a subset of the objects?

REPLY [3 votes]: In the most direct (set theoretic) construction of $\mathbf{Set}$, the category of small sets, the objects are small sets, and the morphisms are set-theoretic functions. Because every function between small sets is itself a small set, the morphisms of $\mathbf{Set}$ are indeed a subclass of the objects of $\mathbf{Set}$.
Depending on your precise definition of category, you might instead need the morphisms to be triples $(A,f,B)$ where $A,B$ are sets and $f$ is a function whose domain is $A$ and whose range is a subset of $B$. But the usual set-theoretic definition of triples make these into small sets, so we still get the same result.


TITLE: Eliminate variable in Maple
QUESTION [1 upvotes]: I tried to search, and found some answers that were sort of relevant. However I could not get it to work.
So, I have two equations $x=f(\xi)$ and $z = g(\xi)$, both being affine, thus invertible.
More precisely the equations are
$$
x=\frac{1+\varepsilon}{4(2+\varepsilon)}\left(\xi - 1 - \frac{\varepsilon}{2}\right)t^2 + \frac{1}{2+\varepsilon}\xi (t+1)
$$
and
$$
z=\frac{1+\varepsilon}{2(2+\varepsilon)}\left(\xi - 1 - \frac{\varepsilon}{2}\right)t + \frac{1}{2+\varepsilon}\xi.
$$
Maple:
x = (1+varepsilon)*(xi-1-(1/2)*varepsilon)*t^2/(4*(2+varepsilon))+xi*(t+1)/(2+varepsilon)
z = (1+varepsilon)*(xi-1-(1/2)*varepsilon)*t/(2*(2+varepsilon))+xi/(2+varepsilon).
I would like to eliminate $\xi$ and write $z = h(x)$, where $h$ should be as simplified as possible. This should be possible to do in Maple.

REPLY [0 votes]: There is a Maple command for this kind of thing, called eliminate.
[edited: I did not initially understand which variables were to be eliminated. So below it now eliminates both z and w.]
I'll follow quasi's Answer by using w for xi, etc.
Using eliminate here does not require coming up (on your own) with a set of solving steps (such as solving cleverly for w, subsituting, etc).
restart;
eq1:=x=(1+e)/(4*(2+e))*(w-1-e/2)*t^2+(1/(2+e))*(w*(t+1)):
eq2:=z=(1+e)/(2*(2+e))*(w-1-e/2)*t+(1/(2+e))*w:

raw:=eliminate({eq1,eq2},{z,w}):

sol:=eval(z,raw[1]);

                2                      2
             e t  - 4 e t x + 2 e t + t  - 4 t x + 2 t - 8 x
    sol := - -----------------------------------------------
                           /   2    2          \
                         2 \e t  + t  + 4 t + 4/

That result can be simplified, though you have not been precise about what you mean by it being as simplified as "possible".
z=simplify(sol,size);

                     2
           (-e - 1) t  + ((4 x - 2) e + 4 x - 2) t + 8 x
       z = ---------------------------------------------
                                     2
                      8 + (2 e + 2) t  + 8 t

z=collect(numer(sol),e,factor)
  /collect(denom(sol),e,factor);

           -t (t - 4 x + 2) e - (t + 2) (t - 4 x)
       z = --------------------------------------
                         2            2
                    2 e t  + 2 (t + 2)

The result from the eliminate command also returns restrictions remaining (implied) on the other variables (parameters). In the code above that would be raw[2], and for this example that is the empty set, which means that solve({eq1,eq1},{z,w}) would produce the same answer since the remaining variables are free.


TITLE: Is $Tf=x_0+\int_0^tf(t)(1-f)\,dt$ a Lipschitz function?
QUESTION [1 upvotes]: Consider the Banach space $C[0,1]$ with the uniform norm and the operator given by $(T(f))x=x_0+\int_0^xf(t)(1-f(t))\,dt$ for $x\in[0,1]$ and $x_0\geq0$.
I want to show that there is a number $0<L<1$ sucht that $|(Tf-Tg)(x)|\le L\lVert f-g\rVert_{\infty}$ for $f,g\in C[0,1]$.
I have done the following:
$|(Tf-Tg)(x)|=|\int_0^xf(t)(1-f(t)) - g(t)(1-g(t))\,dt|$,
I am stuck at this point, since I do not know how to find a good estimate for the integrand.
Can someone help?

REPLY [0 votes]: What you want to show is not true.
To see this, note that this would imply (by taking $g \equiv 0$) that $|Tf(x)|$ grows at most linearly in $f$. But since the integrand is quadratic in $f$, it is easy to see that this cannot hold (take $f \equiv c$ for large $c$).


TITLE: Fourier series trigonometric bn/an value
QUESTION [1 upvotes]: So how would do below Fourier?
where $$f(x)=
\begin{cases}
1-x, &x = [0,4]\\
x-3, &x = [4,8]
\end{cases}$$
Should is this way to solve it?
$$b_n = \frac{1}{8}\int_{0}^{4} (1-x) \cdot \cos(\frac{2\cdot \pi\cdot n\cdot x}{4})dx +\frac{1}{8}\int_{4}^{8} (x-3) \cdot \cos(\frac{2\cdot \pi\cdot n\cdot x}{4})dx$$
It possible for mod to add this image for the equation? Link

Thanks

REPLY [0 votes]: It is in fact$$b_n = \frac{2}{8}\int_{0}^{4} (1-x) \cdot \cos(\frac{\pi\cdot n\cdot x}{4})dx +\frac{2}{8}\int_{4}^{8} (x-3) \cdot \cos(\frac{\pi\cdot n\cdot x}{4})dx$$since the period is $T=8$ and $L={T\over 2}=4$.


TITLE: question if these derivative are equal
QUESTION [1 upvotes]: Starting fuction: $y= \sqrt{x^2-2x+1}$
derivative A:
$y^{\prime} = (1/2)(2x-2)(x^2-2x+1)^{-1/2}$
derivative B:  rewrote the starting function as:
$\sqrt{\left(x-1\right)^2} = \vert x -1 \vert$ thus
$y^{\prime} = $ either 1 if $x > 0$ or -1 if $x < 0$
First, are these the same answer? If they are different please tell me where I went wrong, if they are the same, please explain how and why I can have two different answers?

REPLY [2 votes]: Derivative $A$ is $$ y' = \frac 12 (2x-2) (x^2 - 2x + 1)^{-1/2} = \frac{x-1}{\sqrt{x^2 - 2x + 1}} = \frac{x-1}{|x-1|}.$$
Derivative $B$ should be $1$ if $x > 1$ and $-1$ if $x < 1$.
With this correction observe they agree.


TITLE: Proof maximum flow is at most O(v^2/d^2) - the value of min cut
QUESTION [0 upvotes]: Given a simple graph (at most one edge between u-v), with no loops or parallel edges, I have to prove that max (s,t) flow is at most O(v^2 / d^2).
I understand that this is asking to prove max flow <= C* (V^2/d^2) for some positivie c. I asked my TA (teacher assistant) and he said that we'd need to prove this by contradiction
MY PROOF

Assume for a contradiction, there's more than one edge between some vertices x and y. The shortest path is distance 'd'.

I'm stuck after this. In other words, I need to show that the minimum cut cannot be > v^2 / d^2

REPLY [1 votes]: When you prove something by contradiction, you assume the negation of the statement you're proving. You would assume for contradiction that there's more than one edge between some pair of vertices if your goal was to prove that the graph was simple.
But that's not what's happening here. It's one of your assumptions that the graph is simple. In a proof by contradiction, here, you would want to assume that the max flow is not $O(v^2/d^2)$.

In fact, a proof by contradiction isn't necessary here. To prove that the max flow is at most some upper bound $x$, it's equivalent to prove that the min cut is at most some upper bound $x$. To do that, it's enough to find some cut, not necessarily the min cut, with capacity $x$. (Then, the min cut can only be lower than that!)
So, your goal is to prove that if the distance between $s$ and $t$ is $d$, then there is a cut of capacity $O(v^2/d^2)$.
Here's a sketch of an argument. Let $V_1, V_2, \dots, V_{d-1}$ be the sets of vertices at distance $1, 2, \dots, d-1$ from $s$, respectively. Then for every $i$ such that $1 \le i < d-1$, deleting all the edges between $V_i$ and $V_{i+1}$ will disconnect $s$ from $t$, so it corresponds to a cut.
The "average case" is that $V_1, V_2, \dots, V_{d-1}$ all have size about $\frac{v}{d-1}$. The number of edges between $V_i$ and $V_{i+1}$ is at most $|V_i| \cdot |V_{i+1}|$, which would be about $(\frac{v}{d-1})^2$.
You cannot guarantee that you're in the average case, of course. But you should be able to argue that at least one of these cuts is not much worse than average, proving the result you want.


TITLE: What axiom in Math says "similar inputs should yield similar outputs"?
QUESTION [0 upvotes]: It is easy to take for granted the simple idea that similar input $x$ to a function $f(x)$ should yield similar outputs - such that if the difference between $x$ is arbitrary small, then we should also be able to get arbitrary small changes in $f(x)$.
But what is this fundamental property called? Is it just function continuity? But even continuity seems to rely on this fact. What stops me from arguing that only arbitrary far-apart numbers as inputs will yield similar outputs?
It feels like there should exist an even more fundamental axiom upon which all this is based. What is this axiom called?

REPLY [3 votes]: This is not an axiom, it's exactly what the property "continuity" means. And there are functions which aren't continuous: for an extreme example, take Conway's base 13 function $h$, which has the property that for every $x$ and $y$, and for every $\delta>0$, there is some $c\in (x-\delta, x+\delta)$ such that $h(c)=y$. That is, it's completely uncontrollable.

Regarding axioms: There are certain (extremely rare) contexts where it can make sense to work in a system one of whose axioms is "every function is continuous." Separately, one might argue that "every function occuring in nature is continuous," but that is imprecise. In general, though, if you're looking for an axiom that tells you that you can take continuity for granted, there isn't one - because you can't!


TITLE: Proving two inequalities in calculus
QUESTION [2 upvotes]: I'm trying to prove this two statements:
$$1) \quad \forall\,x\geq 1, \quad \left|\arctan(x)-\frac{\pi}{4}-\frac{x-1}{2}\right|\leq \frac{(x-1)^2}{2}; \\
2)\quad\textrm{If}\;e <a<e^{2}\implies a^{\ln a}-e<4e^3(a-e)\qquad\quad ;
$$
For the second inequality, before trying to solve I saw some things in the statement.
If $a>e\implies  \ln(a)>\ln(e)=1\implies a^{\ln a}-e=e^{(\ln a)^{2}}-e>e^{(\ln(e))^{2}}-e=0\implies a^{\ln a}-e>0.$
And... this is all I got. I don't know what to do.
For the first inequality, I've been searching for some similar questions. The answers always comes from a clever function definition and applying the mean value theorem. Is that the way to solve this problem?
I know that I didn't get so close, but any help would be appreciated.

REPLY [0 votes]: For the second inequality, let $a=eb$ with $1\lt b\lt e$. Note that
$$a^{\ln a}=(eb)^{\ln(eb)}=(eb)^{1+\ln b}=e^{1+\ln b}b^{1+\ln b}=ebb^{1+\ln b}=eb^{2+\ln b}$$
so the inequality to prove becomes
$$b^{2+\ln b}-1\lt4e^3(b-1)$$
for $1\lt b\lt e$.  Now $1\lt b\lt e$ implies $b^{\ln b}\lt b^{\ln e}=b$, so
$$b^{2+\ln b}-1\lt b^3-1=(b-1)(b^2+b+1)\lt(b-1)(e^2+e+1)\lt4e^3(b-1)$$
where the final inequality, $e^2+e+1\lt4e^3$, is obvious.


TITLE: Would a phone move upon vibration in a completely uniform situation?
QUESTION [4 upvotes]: I was sitting down yesterday and saw my phone vibrate on a side, and it moved about a centimetre per vibration.
I wondered why it moves, and thought perhaps that the side it was on had a slight slope, because it tended to move in the same direction every time.
So I then though, what if the side was perfectly flat? Well, then I considered the fact that the phone's centre of mass would make it move in a biased direction (is this correct?).
So I then thought, what if the phone's centre of mass was in the exact centre, and the slop was perfectly flat?
Would the phone still move?
And if so, what factor would make it move in a particular direction?

REPLY [0 votes]: No it won't move. Simple prove is tide. You can consider moon as a motor with asymmetric center of gravity. So it makes water moving back and further, however water doesn't move in any direction constantly.


TITLE: General solution of Transport equation
QUESTION [1 upvotes]: General solution of Transport equation (homogeneous): Method of Characteristics
$$u_t+cu_x=0 (\star)$$
We know that if $f: \mathbb{R} \to \mathbb{R}$ is differentiable  then $u(x,t)=f(x-ct)$ is a solution of $(\star)$.
We will show that each solution of $(\star)$ is of the form $u(x,t)=f(x-ct)$, where $f$ is an arbitrary differentiable function, $f: \mathbb{R} \to \mathbb{R}$.
We consider the lines $\epsilon_a: x-ct=a, a \in \mathbb{R}$.
We define the function $z(s)=u(x(s),t(s))$, where $x(s)=cs+a$, $t(s)=s$.
Then $(x(s), t(s)) \in \epsilon_a \forall s \in \mathbb{R}$.
Let $u$ be a solution of $(\star)$ and for this $u$ I define $z(s)$ as previously.
Then $z'(s)=c u_x+ u_t=0$, i.e. $z(s)=\beta \forall s \in \mathbb{R}$.
$u(x(s),t(s))=z(s)=z(0)=u(a,0)=u(x(s)-ct(s),0) \forall s$
Thus $u(x,t)=u(x-ct,0)=:f(x-ct)$, where $f: \mathbb{R} \to \mathbb{R}$ is differentiable.
I am looking at the following exercise:
Find the general solution of the non-homogeneous  Transport equation $u_t+cu_x=g(x,t)$ where $g$ is "smooth" (how smooth?) and using the above find the general solution of the wave equation.
Hint: We work as previously : $z'(s)=g(x(s),t(s))$.
So in this case do we know that $u(x,t)=f(x-ct)$ is again a solution of the given equation?
Or do we have to consider an other solution and show that all the solutions are of this form?

REPLY [4 votes]: here is one way to do $$u_t + cu_x = g(x, t), u(x,0) = f(x).\tag 1 $$
define the characteristic lines parametrically by $x = a+cs, t = s.$ you can verify that $$\frac{d}{ds}u(a+cs, s)=u_t+cu_x=g(a+cs, s) \tag 2$$
integrating $(2)$ from $0$ to $t,$ gives you $$u(a+ct, t)=f(a)+\int_0^tg(a+cs, s)\, ds $$ which can be rewritten as $$u(x, t) = f(x-ct)+\int_0^t g(x-ct + cs,s)ds$$ is a solution of $(1).$


TITLE: Equivalence for sequentially compact space for Hausdorff spaces.
QUESTION [0 upvotes]: Let $X$ be a Hausdorff space. Show that $X$ is sequentially compact if and only if for every closed set $A$ of $X$ and every continuous function $f:A \to \mathbb{R}$, $f$ has a maximum. I think this should follow from Urysohn's lemma but I don't really see how to approach this problem. I know that since $X$ is Hausdorff, we also get that $X$ is normal. So in particular, $X$ is a compact Hausdorff space, however I don't know if this would get me anywhere...

REPLY [1 votes]: This is false: $\{0,1\}^{[0,1]}$ is compact Hausdorff (so every real-valued continuous function assumes a max) but not sequentially compact. $\beta \Bbb N$ (the Čech–Stone compactification of $\Bbb N$ is another such example.
In first countable Hausdorff spaces the equivalence (pseudocompactness and sequential compactness) does hold.


TITLE: Are topological manifolds homotopy equivalent to smooth manifolds?
QUESTION [23 upvotes]: There exist topological manifolds which don't admit a smooth structure in dimensions > 3, but I haven't seen much discussion on homotopy type.  It seems much more reasonable that we can find a smooth manifold (of the same dimension) homotopy equivalent to a given topological manifold.  Is this true, or is there a counterexample?

REPLY [23 votes]: For every $n\ge 4$ there exists a closed aspherical  topological $n$-manifold $N$ which is not homotopy-equivalent to a PL manifold. Furthermore, $\pi_1(N)$ is a CAT(0) group. This is a theorem of Davis and Januszkiewicz, see theorems 5a1, 5b1 in their "Hyperbolziation of polyhedra" paper http://intlpress.com/JDG/archive/1991/34-2-347.pdf The construction relies heavily on Freedman's result about E8-manifold. As Vitali said, this is an old post, but it is good to have an answer that works in all dimensions since dimension 4 is exceptional in many ways.


TITLE: Evaluation map in the category of $\omega$CPO's is $\omega$-continuous
QUESTION [4 upvotes]: I'm struggling with a claim in Example 6.2 from Steve Awodey's Category Theory (2nd Ed.). The context is the following: $P$ and $Q$ are $\omega$CPO's, $Q^P = \{ f: P \to Q \mid \text{ $f$ is monotone and $\omega$-continuous}\}$, and $\epsilon: Q^P \times P \to Q$ is defined by $\epsilon(f,p) = f(p)$. I want to prove that $\epsilon$ is $\omega$-continuous, meaning that $\epsilon$ preserves all $\omega$-colimits, i.e., $\epsilon\left(\varinjlim (d_n,e_n)\right) = \varinjlim \epsilon(d_n, e_n)$. Below is the part I was able to do.

Given an $\omega$-chain $DE: (d_0, e_0) \leq (d_1, e_1) \leq (d_2, e_2) \leq \dots$ in $Q^P \times P$, with colimit $L = (L_1, L_2)$, we want to prove that the colimit of the $\omega$-chain $\epsilon(DE): \epsilon(d_0, e_0) \leq \epsilon(d_1, e_1) \leq \epsilon(d_2, e_2) \leq \dots$ is $\epsilon(L)$. From the fact that $L$ is a colimit of $DE$, we have, immediately, that:
(i) $L$ is an upper bound for $DE$. That is, for all $n \in \mathbb{N}$, $(d_n, e_n) \leq (L_1, L_2)$, i.e., $d_n \leq L_1$ and $e_n \leq L_2$.
(ii) If $L' = (L_1', L_2') \in Q^P \times P$ is an upper bound for $DE$, then $L \leq L'$, i.e., $L_1 \leq L_1'$ and $L_2 \leq L_2'$, i.e., $L_2 \leq L_2'$ and, for all $p \in P$, $L_1(p) \leq L_1'(p)$.
Observe that

$\epsilon(L)$ is an upper bound for $\epsilon(DE)$. That is, for all $n \in \mathbb{N}$, $d_n(e_n) = \epsilon(d_n, e_n) \leq \epsilon(L) = L_1(L_2)$. In fact, given $n \in \mathbb{N}$, we have, by (i), $e_n \leq L_2$. Since $d_n$ is monotone, it follows that $d_n(e_n) \leq d_n(L_2)$. But, by (i), $d_n \leq L_1$. So, $d_n(p) \leq L_1(p)$, for all $p \in P$. In particular, for $p = L_2$, we have $d_n(L_2) \leq L_1(L_2)$. Now, from $d_n(e_n) \leq d_n(L_2)$ and $d_n(L_2) \leq L_1(L_2)$, we obtain $d_n(e_n) \leq L_1(L_2)$, as intended.
If $q \in Q$ is an upper bound for $\epsilon(DE)$, then $\epsilon(L) \leq q$. In fact, given $q \in Q$, with $d_n(e_n) \leq q$ for all $n \in \mathbb{N}$, ...

REPLY [4 votes]: I just found an answer: Propositions 1.2.11-1.2.13 of Barendregt's The Lambda Calculus, Its Syntax and Semantics. Below is my version of the proof.

Proposition 1: $Q^P$ is an $\omega$CPO.
Proof:  Given any $\omega$-chain $D: d_0 \leq d_1 \leq d_2 \leq \dots$ in $Q^P$, we need to prove that it has a colimit $d_{\omega}$. Observe that, for all $p \in P$, we have a $\omega$-chain $D(p): d_0(p) \leq d_1(p) \leq d_2(p) \leq \dots$, in $Q$, which has a colimit $d_{\omega}(p)$. The map $p \mapsto d_{\omega}(p) = \varinjlim_{n \in \mathbb{N}} d_n(p)$ defines an element $d_{\omega} \in Q^P$ such that

$d_{\omega}$ is an upper bound for $D$. That is, for all $n \in \mathbb{N}$, $d_n \leq d_{\omega}$. In fact, given $n \in \mathbb{N}$, we have that, for all $p \in P$, $d_n(p) \leq d_{\omega}(p)$, since $d_{\omega}(p)$ is an upper bound for $D(p)$.
If $f \in Q^P$ is an upper bound for $D$, then $d_{\omega} \leq f$. In fact, suppose $f$ is an upper bound for $D$. Then, for all $n \in \mathbb{N}$ and $p \in P$, $d_n(p) \leq f(p)$. That is, for any $p \in P$, we have $d_n(p) \leq f(p)$, for all $n \in \mathbb{N}$. Hence, for all $p \in P$, $f(p)$ is an upper bound for $D(p)$. So, for all $p \in P$, we have $d_{\omega}(p) \leq f(p)$, by minimality of $d_{\omega}(p)$ as an upper bound for $D(p)$. Therefore, $d_{\omega} \leq f$.

Thus, $d_{\omega}$ is the least upper bound for $D$. Since $D$ is an arbitrary $\omega$-chain in $Q^P$, we conclude that $Q^P$ is an $\omega$CPO. $\square$
Proposition 2: The evaluation map $\epsilon: Q^P \times P \to Q$ is $\omega$-continuous.
Proof: Given an $\omega$-chain $DE: (d_0, e_0) \leq (d_1, e_1) \leq (d_2, e_2) \leq \dots$ in $Q^P \times P$, with colimit $L = (L_1, L_2)$, we want to prove that the colimit of the $\omega$-chain $\epsilon(DE): \epsilon(d_0, e_0) \leq \epsilon(d_1, e_1) \leq \epsilon(d_2, e_2) \leq \dots$ is $\epsilon(L)$. From the fact that $L$ is a colimit of $DE$, we have, immediately, that:
(i) $L$ is an upper bound for $DE$. That is, for all $n \in \mathbb{N}$, $(d_n, e_n) \leq (L_1, L_2)$, i.e., $d_n \leq L_1$ and $e_n \leq L_2$.
(ii) If $L' = (L_1', L_2') \in Q^P \times P$ is an upper bound for $DE$, then $L \leq L'$, i.e., $L_1 \leq L_1'$ and $L_2 \leq L_2'$, i.e., $L_2 \leq L_2'$ and, for all $p \in P$, $L_1(p) \leq L_1'(p)$.
Furthermore,
(iii) $L_1 = \varinjlim_{n \in \mathbb{N}} d_n$. Proof: By (i), we have that $d_n \leq L_1$, for all $n \in \mathbb{N}$. Moreover, if $L_1'$ is an upper bound for $D$, then $(L_1', L_2)$ is an upper bound for $DE$, which implies, by (ii), that $L_1 \leq L_1'$.
(iv) $L_2 = \varinjlim_{n \in \mathbb{N}} e_n$. Proof: By (i), we have that $e_n \leq L_2$, for all $n \in \mathbb{N}$. Moreover, if $L_2'$ is an upper bound for $E$, then $(L_1, L_2')$ is an upper bound for $DE$, which implies, by (ii), that $L_2 \leq L_2'$.
Finally, observe that

$\epsilon(L)$ is an upper bound for $\epsilon(DE)$. That is, for all $n \in \mathbb{N}$, $\epsilon(d_n, e_n) \leq \epsilon(L)$. Equivalently, for all $n \in \mathbb{N}$, $d_n(e_n) \leq L_1(L_2)$. In fact, given $n \in \mathbb{N}$, we have, by (i), $e_n \leq L_2$. Since $d_n$ is monotone, it follows that $d_n(e_n) \leq d_n(L_2)$. But, by (i), $d_n \leq L_1$. So, $d_n(p) \leq L_1(p)$, for all $p \in P$. In particular, for $p = L_2$, we have $d_n(L_2) \leq L_1(L_2)$. Now, from $d_n(e_n) \leq d_n(L_2)$ and $d_n(L_2) \leq L_1(L_2)$, we obtain $d_n(e_n) \leq L_1(L_2)$, as intended.

If $q \in Q$ is an upper bound for $\epsilon(DE)$, then $\epsilon(L) \leq q$. In fact, given $q \in Q$, with $d_n(e_n) \leq q$ for all $n\in \mathbb{N}$, we have that, for all $i,j\in \mathbb{N}$, there is a $p = \max\{i,j\}$ such that $d_i(e_j) \leq d_i(e_p) \leq d_p(e_p) \leq q$. Thus, for all $i \in \mathbb{N}$, $q$ is an upper bound of the $\omega$-chain $D_iE: d_i(e_0) \leq d_i(e_1) \leq d_i(e_2) \leq \dots$. But, since $L_2 = \varinjlim_{j \in \mathbb{N}} e_j$ and each $d_i$, with $i \in \mathbb{N}$, is continuous, we have that, for all $i \in \mathbb{N}$, $d_i(L_2) = \varinjlim_{j \in \mathbb{N}} d_i(e_j)$ is the least upper bound for $D_iE$. Hence, $d_i(L_2) \leq q$, for all $i \in \mathbb{N}$. So, $q$ is an upper bound for the $\omega$-chain $D(L_2): d_0(L_2) \leq d_1(L_2) \leq d_2(L_2) \leq \dots $. Now, recall that $L_1 = \varinjlim_{i \in \mathbb{N}} d_i$ and, by Proposition 1, the colimit of any $\omega$-chain $d_0 \leq d_1 \leq d_2 \leq \dots$ in $Q^P$ is the function $d_\omega$ given by $d_{\omega}(p) = \varinjlim_{i \in \mathbb{N}} d_i(p)$, for all $p \in P$. Thus, $L_1(L_2) = d_\omega(L_2) = \varinjlim_{i \in \mathbb{N}} d_i(L_2)$. So, $L_1(L_2)$ is the least upper bound of the $\omega$-chain $D(L_2): d_0(L_2) \leq d_1(L_2) \leq d_2(L_2) \leq \dots$. On the other hand, we have seen that $q$ is an upper bound for $D(L_2)$. Therefore, $\epsilon(L) = L_1(L_2) \leq q$, as intended. $\square$


TITLE: Need help with the following lemma about transpositions
QUESTION [3 upvotes]: If $1 \leq k <l \leq n$ and $\sigma=(k,l)$ then the number of inversions of $\sigma$ is $2(l-k)-1$. Thus every transposition is an odd transposition.
I don't understand why the number of inversions would be such expression. The transposition $\sigma$ is just a 2 cycle, so I don't see how it can have more than 1 inversion.

REPLY [3 votes]: A way to define the number of inversions is, the total number of pairs $i<j$ with $\sigma(i)>\sigma(j)$. So when you switch $k$ and $l$, $k$ gets moved past every number between $k$ and $l$ and so does $l$. Thus the inversions are: the pair $k,l$; and the pairs $k,i$ and $i,l$ for every $i$ strictly between $k$ and $l$. There are $l-k-1$ numbers $i$ between $k$ and $l$, and each contributes $2$ inversions ($k,i$ and $i,l$); and $k,l$ is also an inversion. So the total is $2\times (k-l-1) + 1$, which is equivalent to the formula in the OP.


TITLE: Doubt regarding square root
QUESTION [0 upvotes]: During a lecture my professor said that the co domain of function $$f(x)=\sqrt{x}$$ must be $[0,\infty)$.
But I asked " can the co-domain be the whole R?"
He answered "it can't".
My doubt is that eventhough the range is [0,$\infty$),can the co domain be R or it  must be [0,$\infty$).
Please help me to clarify my doubt.Thanks .

REPLY [1 votes]: The point is, unless we are being very strict  about things, the only condition on the co-domain is that it must contain the range.
The definition of codomain says : "a set that contains all the possible values of a function".
Both the sets $\mathbb{R}$ and $[0,\infty)$ contain the range of your function, which happens  to be $[0,\infty)$. Hence, both qualify as co domains of the function.
However, if you were to say that $[0,\infty)$ is the domain of the function, then you would get  a stronger statement about the function, namely that it is one-one and onto. Therefore, it would be recommended for you to work with  $[0,\infty)$ as the co domain.  It would not be mandatory to do so.

REPLY [1 votes]: For a function $f\colon A\to B$ we call $A$ the domain and $B$ the co-domain of $f$. This expresses that $f(x)$ is defined and is an element of $B$ for all $x\in A$.
The range of the function, $$f[A]=\{\,f(x)\mid x\in A\,\}=\{\,y\in B\mid \exists x\in A\colon y=f(x)\,\},$$ is a subset of the co-domain, and may be a proper subset.
Thus we can consider the square-root function as a function $[0,\infty)\to[0,\infty)$, but just as well as a function $[0,\infty)\to \Bbb R$ (but certainly not as a function $[0,\infty)\to[1,\infty)$ and of course not $\Bbb R\to\Bbb R$)


TITLE: What does fundamental (homotopy) groups measure?
QUESTION [8 upvotes]: As I read an algebraic topology book, I felt I knew exactly what the fundamental group is geometrically! I thought it counts the number of independent cycles. (my definition of dependence cycles (that may be incorrect): $\alpha,\beta$ are two dependent cycles if $\exists m,n\in\Bbb Z$ s.t. $\alpha^n=\beta^m$.)
And according to this explanation it was always a serious question for me that why almost all authors compute the fundamental group of circle in very long way, some of them in a separate chapter and after proving many theorems instead of observing that there is only one independent cycle in circle! After these doubts, I read that $\pi_1(\Bbb RP^2)=\Bbb Z_2$. And here was the end of my dream. Since in term of my interpretation, the fundamental group is always free product of some $\Bbb Z$ but $\pi_1(\Bbb RP^2)=\Bbb Z_2$ is not in that form! So I want to know that

What does fundamental (homotopy) groups measure?

Isn't it true that if the space does not have a trivial loop, then it must contain at least one generator?

I think my interpretation is partially true but it ignores some information of the space. Or perhaps the missed point of my interpretation is that I don't consider the base point to be fixed.
The above interpretation also can be applied for $\pi_2$ (and $\pi_n$). i.e. $\pi_2$ counts the number of independent topological spheres (But in this case I don't know what is the independent topological  spheres!!).

REPLY [3 votes]: Maybe instead of general ideas, look at simple examples where the fundamental group is not a free product. Let's look at a torus, represented as a square with opposite sides identified. Each of the sides $a$ and $b$ represent incontractible loops, but if you go around the square, then the loop $aba^{-1} b^{-1}$ can be contracted (shrinking the boundary of the square into a mid-point).
Following picture illustrates a homotopy between $ab$ and $ba$ in a torus.

With $\Bbb{RP}^2$, represent it as a ball with lower half-circle $a$ identified with upper half-circle $a$. Then there is no way to contract $a$ but of course, $aa$ goes around the circle and can be contracted.

Nullhomotopy of $aa$:

Let's try to nullhomotop just $a$.. intuitively, you can probably see you don't succeed

To illustrate that fundamental group of $\mathbf{SO}(3)$ is $\Bbb Z_2$ is even more intuitive. Take a glass of beer, hold it in your right arm. Rotate it by 360 degrees, with your shoulder being "fixed" (and don't pour anything out). Your hand is "twisted" and represent a loop in $\mathbf{SO}(3)$. Move your hand up and continue twisting in the same rotation; after another 360 degrees, your hand is untwisted again. Great video.
If you want to think in terms of "independence" -- think of generators and relations and note that $\Bbb Z=\langle \alpha| \varnothing\rangle$ (empty relation) and $\Bbb Z_2=\langle \alpha| \alpha^2=1\rangle$. For $\pi_1$, you can restrict yourself to the 2-skeleton. Homotopy group of $1$-skeleton is indeed a free group of generating cycles. Every two-cell adds one relation.


TITLE: Sharp Dirichlet heat kernel estimates in exterior domains?
QUESTION [2 upvotes]: I am right now working on some linear parabolic problems studying the behaviour of its solutions for large initial data. To do this, I have needed to use some estimates of the Dirichlet and Neumann heat kernels (for the Laplacian operator) in exterior domains (i.e. $\Omega=\mathbb{R}^N\backslash K$ where $K$ is a regular compact set).
I have found multiple results from Saloff-Coste, Grigor'yan, Davies, Q. S. Zhang... (See the references below). Most of them concern the problem in complete Riemann manifolds. Some of them study the problem in exterior domains (or in more general (if $K$ is regular enough) inner uniform domains) [2,4,5]. A good general text about this is this one from Saloff-Coste: [1].
However, most of the results I have found are bounds like the following:
$$
\phi(x,y,t)\frac{ e^{-c_1\frac{d(x,y)^2}{4t}}}{(4\pi t)^{N/2}}\leq k(x,y,t)\leq \Phi(x,y,t)\frac{ e^{-c_2\frac{d(x,y)^2}{4t}}}{(4\pi t)^{N/2}}
$$
where $d(x,y)$ is the geodesic distance in $\Omega$ between $x$ and $y$ and $\phi,\Phi$ are known functions. See for example [2] Th 1.1. and [4] Th 1.3.1, 1.3.3.
I would like to know if there are some sharp results in which $c_1=1$ and/or $c_2=1$, like the heat kernel in the whole space. I have not found almost any result in this way. One I found is [6]  Cor 3.1, Th 4.1 in which they get $c_1=1+\varepsilon$ and $c_2=1-\varepsilon$ with $\varepsilon$ as small as one would like (but then $\phi$ and $\Phi$ change obviously) but it is for complete manifolds.
Any comment, suggestion or reference related to this would be really helpful. In particular my main questions are:

Are there any sharp result of that type? It is useful for me even if it is not the case of exterior domain, but other settings.
Are there any result in which I can make $c_1$ and $c_2$ as close to $1$ as we want, although not $1$?
If you don't know about the first two questions, do you think it is a plausible result to obtain that type of bounds for the Dirichlet Heat Kernel in exterior domains?

I am also interested in Neumann heat kernel, so any results for it are also welcomed.

References:
[1] The heat kernel and its estimates. L. Saloff Coste.
[2] The global behavior of heat kernels in exterior domains. Q. S. Zhang.
[3] Heat Kernels and Spectral Theory. E. B. Davies.
[4] Heat kernel estimates for inner uniform subsets of Harnack-type Dirichlet space. P. Gyrya.
[5] Dirichlet heat kernel in the exterior of a compact set Grigor'yan, Saloff-Coste.
[6] On the parabolic kernel of the Schrödinger operator P. Li, S. T. Yau
PS: This is my first question here, do not hesitate to correct me if the question is not well formulated.

REPLY [1 votes]: The upper bound with $c_2=1$ and a polynomial $\Phi$ should be in "Coulhon-Sikora: Gaussian upper bounds via Phragmen-Lindelof principle", Proceedings London Math. Soc. 96 (2008), 507-544. The setting is quite general and should cover exterior domains, too.


text:
\section{Convergence of Projected Gradient Descent} \label{sec: conver prelims}
\iffalse
\paragraph{Measuring of progress using smoothness.} Recall that $\x^* = \argmin_{\x \in P}f (\x)$ denotes the constrained optimal solution. Consider an iterative descent scheme of the form $\x_{t+1} = \x_{t} + \gamma_t\bd_t$. First, to obtain a measure of progress, consider the smoothness inequality given in Section \ref{sec: prelims} applied with $\y \leftarrow \x_{t+1}$ and $\x \leftarrow \x_t$:
\begin{align}
        f(\x_{t+1}) &\leq f(\x_t) + \innerprod{\nabla f(\mathbf{x}_t)}{\x_{t+1} - \x_t} + \frac{L}{2} \|\x_{t+1} - \x_t\|^2 \label{smoothness 1}\\
    &= f(\x_t) + \gamma_t \innerprod{\nabla f(\mathbf{x}_t)}{\bd_t} + \frac{L\gamma_t^2}{2} \|\bd_t\|^2 \label{descent lemma}
\end{align}
Let $\gamma_t^{\max} = \max \{\delta \mid \mathbf{x} + \delta \bd_t \in P\}$. Now consider the step-size $\gamma_{\bd_t} := \frac{\innerprod{-\nabla f(\mathbf{x}_t)}{\bd_t}} {L \|\mathbf{d}_{\mathbf{x}_t}\|^2}$ minimizing the RHS of the inequality above and suppose for now that $\gamma_{\bd_t} \leq \gamma_t^{\max}$. Then, plugging in $\gamma_{\bd_t}$ in \eqref{descent lemma} and rearranging we have
\begin{equation} \label{progress from smoothness}
    h(\x_t) - h(\x_{t+1}) = f(\x_t) - f(\x_{t+1}) \geq \frac{\innerprod{-\nabla f(\mathbf{x}_t)}{\bd_t}^2} {2L \|\bd_t\|^2}.
\end{equation}
It is important to note that $\gamma_{\bd_t}$ is not the step-size we obtain from line-search. It is just used as means to lower bound the progress obtained from the line-search step.

\paragraph{Measuring primal gaps using (strong) convexity.} To prove convergence results for our algorithms, we also need a dual gap bound on $h(\mathbf{x}_t) := f(\mathbf{x}_t) -f(\mathbf{x}^*)$ using $\mathbf{d}_{\mathbf{x}_t}^\Pi$. To do this, consider the strong convexity inequality given in Section \ref{sec: prelims} applied with $\y \leftarrow \x_t + \gamma (\x^*-\x_t)$ and $\x \leftarrow \x_t$:
\begin{equation*}
    f(\x_t + \gamma(\x^*-\x_t)) - f(\x_t) \geq \gamma \innerprod {\nabla f(\x_{t})}{\x^*-\x_t}  + \frac{\mu\gamma^2 \|\x^*-\x_t\|^2 }{2}.
\end{equation*}
The RHS is convex in $\gamma$ and is minimized when $\gamma^* = \frac{\innerprod {-\nabla f(\x_{t})}{\x^*-\x_t}}{\mu \|\x^*-\x_t\|^2}$. Plugging $\gamma^*$ in the above expression and re-arranging we obtain
\begin{equation*}
    f(\x_t + \gamma (\x^*-\x_t)) - f(\x^*) \leq \frac{\innerprod {-\nabla f(\x_{t})}{\x^*-\x_t}^2} {2\mu \|\x^*-\x_t\|^2}.
\end{equation*}
As the LHS is independent of $\gamma$, we can set $\gamma = 1$, which gives
\begin{equation} \label{primal gap}
    h(\x_t) := f(\x_t) - f(\x^*) \leq \frac{\innerprod {-\nabla f(\x_{t})}{\x^*-\x_t}^2} {2\mu \|\x^*-\x_t\|^2}.
\end{equation}

Now using Lemma \ref{best local direction} with $\mathbf{x}^* - \mathbf{x}_t$ substituted for $\y$ in \eqref{best local direction equation} we obtain
\textbf{\begin{equation} \label{deriv performance1}
     \|\mathbf{d}_{\mathbf{x}_t}^\Pi\|^2 =\innerprod{-\nabla f(\mathbf{x}_t)}{\frac{\mathbf{d}_{\mathbf{x}_t}^\Pi}{\|\mathbf{d}_{\mathbf{x}_t}^\Pi\|}}^2  \geq \innerprod {-\nabla f(\mathbf{x}_t)}{\frac{\mathbf{x}^* - \mathbf{x}_t}{ \|\mathbf{x}^* - \mathbf{x}_t\|}}^2 \geq 2\mu h(\mathbf{x}_t),
\end{equation}}
where the last inequality follows from \eqref{primal gap}.

\paragraph{Convergence of projected gradient descent.}
\fi
We will invoke the following theorem in the global linear convergence proof of Theorem \ref{alg converg1} and Theorem \ref{alg converg2}:

\begin{theorem}[Theorem 5 in \cite{Karimi_2016}]\label{PGD progress}
Consider the problem $\min_{x \in \mathcal{X}} f(\x)$, where $\mathcal{X} \subseteq \mathbb{R}^n$ is a convex and compact domain, and $f : \mathcal{X} \rightarrow \mathbb{R}$ is $L$-smooth and $\mu$-strongly convex over $\mathcal{X}$. Further, consider the projected gradient descent (PGD) algorithm with a step-size of $1/L$: $
    \x_{t+1} := \Pi_\mathcal{X}(\x_t - \nabla f(\x_t) / L).$
Then the primal gap $h(\mathbf{x}_t): = f(\mathbf{x}_t) - f(\mathbf{x}^*)$ of the PGD algorithm decreases geometrically:
\begin{equation} \label{PGD decrease}
    h(\mathbf{x}_{t+1}) \leq \left(1- \frac{\mu}{ L}\right)h(\mathbf{x}_t),
\end{equation}
with each iteration of the PGD algorithm.
\end{theorem}

We present a proof of this result for completeness. First, we need the following technical lemma for the proof:

\begin{lemma}[Lemma 1 in \cite{Karimi_2016}]\label{proximal PL}
Let $\mathcal{X} \subseteq \mathbb{R}^n$ be a convex and compact domain and suppose that $f : \mathcal{X} \rightarrow \mathbb{R}$ is $L$-smooth and $\mu$-strongly convex over $\mathcal{X}$. For any $\x \in \mathcal{X}$ and $c \in \mathbb{R}$, define
\begin{equation*}
    D(\x, c) := - 2c \min_{\y \in  \mathcal{X}} \left\{\innerprod{\nabla f(\mathbf{x})}{\y - \x} + \frac{c}{2} \| \y - \x\|^2\right\}.
\end{equation*}
Then, we have  $D(\x, L) \geq D(\x, \mu)$ for all $\x \in \mathcal{X}$.
\end{lemma}

\begin{proof}
Fix any $\x \in \mathcal{X}$. Therefore, by completing the square we have
\begin{align*}
     D(\x, c) &= - \min_{\y \in \mathcal{X}} \left\{2c\innerprod{\nabla f(\mathbf{x})}{\y - \x} + {c^2} \| \y - \x\|^2\right\}\\
     &= \min_{\y \in \mathcal{X}} \left\{ \|\nabla f(\mathbf{x})\|^2 -  \|\nabla f(\mathbf{x})\|^2 - 2c\innerprod{\nabla f(\mathbf{x})}{\y - \x} - {c^2} \| \y - \x\|^2\right\}\\
     & = \|\nabla f(\mathbf{x})\|^2 - \min_{\y \in \mathcal{X}} \| c(\y - \x) + \nabla f(\mathbf{x})\|^2\\
     &= \|\nabla f(\mathbf{x})\|^2 - \min_{\bar{\y} \in c(\mathcal{X} - \x )} \| \bar{\y} + \nabla f(\mathbf{x})\|^2,
\end{align*}
where in the last equality we used the change of variables $\bar{\y} = c (\y - \x)$.

We now claim that, since by definition $\mu \leq L$, we have $\mu (\mathcal{X}- \x) \subseteq L (\mathcal{X}- \x)$. Let $\mathbf{z} \in \mu (\mathcal{X}- \x)$ and we will show that $\mathbf{z} \in L (\mathcal{X}- \x)$. Since $\mathbf{z} \in \mu (\mathcal{X}- \x)$, we could write $\mathbf{z} = \mu (\y - \x) = L( \frac{\mu}{L}(\y - \x))$ for some $\y \in \mathcal{X}$. To prove the claim we now show that $\frac{\mu}{L}(\y - \x) \in \mathcal{X} - \x$. Since $\y - \x \in \mathcal{X} - \x$ and $\mathbf{0} = \x - \x \in \mathcal{X} - \x$, it follows that $\frac{\mu}{L}(\y - \x) = \frac{\mu}{L}(\y - \x) + (1 - \frac{\mu}{L}) \mathbf{0} \in \mathcal{X} - \x$ by the convexity of $\mathcal{X} - \x$ and the fact that $\mu \leq L$. Thus, we have $\mathbf{z} \in L (\mathcal{X}- \x)$ and the claim follows.

Now using this claim we have
\begin{align*}
     D(\x, L) &= \|\nabla f(\mathbf{x})\|^2 - \min_{\bar{\y} \in L(\mathcal{X}- \x)} \| \bar{\y} + \nabla f(\mathbf{x})\|^2 \\
     &\geq \|\nabla f(\mathbf{x})\|^2 - \min_{\bar{\y} \in \mu(\mathcal{X}- \x)} \| \bar{\y} + \nabla f(\mathbf{x})\|^2 && (\text{using $\mu (\mathcal{X}- \x) \subseteq L (\mathcal{X}- \x)$})\\
     &= D(\x, \mu)
\end{align*}
as desired.
\end{proof}

\paragraph{Proof of Theorem \ref{PGD progress}.}
Let $g(\lambda) = \Pi_P(\mathbf{x} - \lambda \nabla f(\mathbf{x}))$ be the curve parameterized by the step-size $\lambda$. Recall that by the proximal definition of the projection (see e.g., \cite{bertsekas1997}) we have
        \begin{equation} \label{prox def}
            g(1/L) = \Pi_\mathcal{X}( \x_t - \nabla f(\x_t)/L) =  \argmin_{\mathbf{y} \in \mathcal{X}} \left \{ \innerprod{\nabla f(\mathbf{x}_t)}{ \mathbf{y} - \mathbf{x}_t} + \frac{L}{2}{\| \y - \mathbf{x}_t \|^2} \right\}.
        \end{equation}
        We can now show the $(1 - \frac{\mu} {L})$ rate of decrease as follows:
        \begin{align}
           h(\x_t) - h(\x_{t+1}) &= f(\x_t) - f(\x_{t+1})\\
           & = f(\x_t) - f(g(1/L)) \label{thm 8 - eq 1}\\
            &  \geq  -  \left(\innerprod{\nabla f(\x_t)}{ g(1/L) - \mathbf{x}_t} + \frac{L}{2}{\|g(1/L) -  \mathbf{x}_t\|^2} \right)\label{thm 8 - eq 2}\\
            &= - \min_{\y \in \mathcal{X}} \left \{\innerprod{\nabla f(\x_t)}{ \mathbf{y} - \x_t} + \frac{L}{2}{\| \y - \x_t \|^2} \right\} \label{thm 8 - eq 3}\\
            &= \frac{1}{2L} \left( -2L\min_{\y \in \mathcal{X}} \left \{\innerprod{\nabla f(\x_t)}{ \mathbf{y} - \x_t} + \frac{L}{2}{\| \y - \x_t \|^2} \right\} \right)\label{thm 8 - eq 4}\\
           & \geq \frac{\mu}{L} \left(-\min_{\y \in \mathcal{X}} \left \{\innerprod{\nabla f(\x_t)}{ \mathbf{y} - \x_t} + \frac{\mu}{2}{\| \y - \x_t \|^2} \right\} \right)\label{thm 8 - eq 5}\\
          & = \frac{\mu}{L} \left(\max_{\y \in \mathcal{X}} \left \{\innerprod{-\nabla f(\x_t)}{ \mathbf{y} - \x_t} - \frac{\mu}{2}{\| \y - \x_t \|^2} \right\} \right)\label{thm 8 - eq 9}\\
           & \geq \frac{\mu}{L} \left(\innerprod{-\nabla f(\x_t)}{\x^* - \x_t} - \frac{\mu}{2}{\| \x^* - \x_t \|^2} \right)\label{thm 8 - eq 6}\\
            & \geq \frac{\mu}{L} h(\x_t) \label{thm 8 - eq 7},
        \end{align}
where \eqref{thm 8 - eq 2} follows from the smoothness inequality given in Section \ref{sec: prelims} applied with $\y \leftarrow g(1/L)$ and $\x \leftarrow \x_t$, \eqref{thm 8 - eq 3} follows from the definition of $g(1/L)$ given in \eqref{prox def}, \eqref{thm 8 - eq 5} follows from Lemma \ref{proximal PL}, \eqref{thm 8 - eq 6} follows from the fact that $\x^* \in \mathcal{X}$, and finally \eqref{thm 8 - eq 7} follows from the strong convexity inequality given in Section \ref{sec: prelims} applied with $\y \leftarrow \x^*$ and $\x \leftarrow \x_t$. \qed

\vspace{-0.3cm}

config: arxiv