text:
\section{Transfinite Recursion/Theorem 1}
Tags: Ordinals

\begin{theorem}
Let $G$ be a [[Definition:Mapping|mapping]].
{{explain|What are the domain and range of $G$?}}
Let $K$ be a [[Definition:Class (Class Theory)|class]] of [[Definition:Mapping|mappings]] $f$ that satisfy:
:the [[Definition:Domain of Mapping|domain]] of $f$ is some [[Definition:Ordinal|ordinal]] $y$
:$\forall x \in y: f \left({x}\right) = G \left({f {\restriction_x} }\right)$
where $f {\restriction_x}$ denotes the [[Definition:Restriction of Mapping|restriction]] of $f$ to $x$.
Let $F = \bigcup K$, the [[Definition:Union of Set of Sets|union]] of $K$.
Then:
:$(1): \quad F$ is a [[Definition:Mapping|mapping]] with [[Definition:Domain of Mapping|domain]] $\operatorname{On}$
:$(2): \quad \forall x \in \operatorname{On}: F \left({x}\right) = G \left({F {\restriction_x} }\right)$
:$(3): \quad F$ is [[Definition:Unique|unique]]. That is, if another mapping $A$ has the above two properties, then $A = F$.
\end{theorem}

\begin{proof}
=== $K$ is a chain ===
First, it is necessary to must show that $K$ is a [[Definition:Chain (Set Theory)|chain]] of [[Definition:Mapping|mappings]] under the [[Definition:Subset|subset]] [[Definition:Relation|relation]].
Take any $f, g \in K$.
Set $B$ equal to the [[Definition:Domain of Mapping|domain]] of $f$ and set $C$ equal to the [[Definition:Domain of Mapping|domain]] of $g$.
From [[Relation between Two Ordinals]]:
:$B \subseteq C \lor C \subseteq B$
From [[Transfinite Recursion/Uniqueness of Transfinite Recursion|Lemma 1]]:
: $\forall x \in B \cap C: f \left({x}\right) = g \left({x}\right)$
So depending on whether $B \subseteq C$ or $C \subseteq B$:
: $f \subseteq g \lor g \subseteq f$
From [[Subset Relation is Ordering]], it follows that $\subseteq$ is a [[Definition:Total Ordering|total ordering]] on $K$.
=== Domain of $F$ is an ordinal ===
$K$ is a chain of [[Definition:Mapping|mappings]].
Since the union of a chain of mappings is a mapping, $F$ is a mapping.
Moreover, $\forall x \in B: f \left({x}\right) = F \left({x}\right)$, because $F$ is an [[Definition:Extension of Mapping|extension]] of the mapping $f$.
The domain of $F$ is a subset of the [[Definition:Ordinal Class|ordinals]] because it is the union of a collection of mappings whose domains are themselves subsets of ordinals.
{{begin-eqn}}
{{eqn | l = a \in \operatorname{Dom} \left({F}\right) \land x \in a
      | o = \implies
      | r = \exists f: \exists \beta \in \operatorname{On}: \left({f: \beta \to \operatorname{Im} \left({f}\right) \land a \in \beta }\right)
      | c = Definition of $F$ (above)
}}
{{eqn | o = \implies
      | r = a \in \operatorname{On} \land x \in \beta
      | c = [[Definition:Transitive Set|Transitivity]] of $\beta$ and $\operatorname{On}$
}}
{{eqn | o = \implies
      | r = x \in \operatorname{Dom} \left({F}\right)
      | c =
}}
{{end-eqn}}
From this it follows that $\operatorname{Dom} \left({F}\right)$ is an ordinal, since it is a transitive subset of $\operatorname{On}$.
=== Domain of $F$ is $\operatorname{On}$ ===
Assume the domain of $F$ is a set.
Since $F$ is a mapping, the range of $F$ is a set and $F$ is a set.
Then $\operatorname{Dom} F = \gamma$ for some ordinal $\gamma$.  Define $C$ as follows:
:$C = F \cup \left\{{\left({\gamma, G \left({F {\restriction_\gamma}}\right)}\right)}\right\}$
Then $C$ is a mapping with domain $\gamma^+$ and satisfies:
: $\forall x < \gamma^+: C \left({x}\right) = G \left({F {\restriction_\gamma} }\right)$
Therefore $C$ is a member of $K$ (note that $F {\restriction_\gamma} = C {\restriction_\gamma}$).
:$\displaystyle C \in K \implies C \subseteq \bigcup K$
So $C \subseteq F$.
But if $F$ is a set, $F \subsetneq C$, a contradiction.
Therefore, $\operatorname{Dom} \left({F}\right)$ cannot be a set and must therefore be the set of all ordinals $\operatorname{On}$.
{{qed|lemma}}
=== Value of $F$ is $G \left({F {\restriction_\alpha} }\right)$ ===
:$\forall x \in \operatorname{On}: \exists f \in K: f \left({x}\right) = F \left({x}\right)$
Since $f \in K$:
: $f \left({x}\right) = G \left({f {\restriction_x} }\right)$
But $\forall y < x: f \left({y}\right) = F \left({y}\right)$, so by [[Equality of Restrictions]]:
: $f {\restriction_x} = F {\restriction_x}$
Therefore,:
:$F \left({\alpha}\right) = G \left({F {\restriction_\alpha} }\right)$
{{qed|lemma}}
=== $F$ is Unique ===
Finally, assume there is another mapping $H$ that satisfies the first two properties.
Then $H$ is equal to $F$ by [[Transfinite Induction/Schema 1|transfinite induction]]:
{{begin-eqn}}
{{eqn | l = \forall x \in y: H \left({x}\right) = F \left({x}\right)
      | o = \implies
      | r = \left({H \restriction y}\right) = \left({F \restriction y}\right)
      | c = [[Equality of Restrictions]]
}}
{{eqn | o = \implies
      | r = G \left({H \restriction y}\right) = G \left({F \restriction y}\right)
      | c = by hypothesis
}}
{{eqn | o = \implies
      | r = H \left({y}\right) = F \left({y}\right)
      | c = by hypothesis
}}
{{end-eqn}}
So for all ordinals:
: $H \left({y}\right) = F \left({y}\right)$
Thus $H = F$.
{{qed}}
\end{proof}

config: wiki


TITLE: Entropy of partitioning for set of all $\binom{n}{k}$ combinations
QUESTION [3 upvotes]: Let $\binom{[n]}{k}$ represent the set of all $k$-combinations of the set $[n]=\{1,\dotsc,n\}$. We will use the notation:
$$\{x_1, \dotsc, x_k\} \in \binom{[n]}{k},$$
where $x_1 < x_2, < \dotsc < x_k$. Let $k$ be odd, and let $t = \left\lfloor \frac{k}{2}\right \rfloor$. One way to partition this set is to say all elements with the same values of $x_{2i}, \;\; i=1,\dotsc, t$ belong to the same part.
There are a total of $\binom{n-t-1}{t}$ parts in this partitioning. To see this, we let $x_{2i} - i = d_i, \;\;i=1,\dotsc,t$. We must have that $x_{2i} \geq x_{2(i-1)}+2$, and $x_{2i} \in \{2, \dotsc, n-1\}$. From these conditions, any set of $d_i$'s must satisfy $0 < d_1, < d_2, \dotsc, < d_t < n-t$. Clearly there are $\binom{n-t+1}{t}$ ways this inequality can be satisfied, which is equal to the number of parts.
For each part in the partition, indexed by $\mathbf{d} = \{d_1, \dotsc, d_t\}$ let the number of elements in that part be $c (\mathbf{d})$. We can show by a simple counting argument that
$$c (\mathbf{d}) = d_1(d_2-d_1)\dotsc,(d_t - d_{t-1})(n-t-d_t),$$
which is the form of a vendermonde determinant. My question is, if we let $p(\mathbf{d}) = \frac{c(\mathbf{d})}{\binom{n}{k}},$
is it possible to analytically calculate the following sum?
$$\sum \limits_{0 < d_1 < \dotsc, < d_t<n-t} p(\mathbf{d})\log\left( p(\mathbf{d}) \right)$$
I've tried myself, but there doesn't seem to be any obvious way to do this. Furthermore, if there is no easy way to analytically compute this sum, is there an easy bound for it in terms of $n,k,t$? Obviously, there is the simple lower bound $-\log \left( \binom{n-t-1}{t}\right)$, but I'm wondering if there is anything better, which makes use of the structure, and not just the number of parts in the partition.
Somewhat loosely related to this question (Minimum number of $k$-partitions of a set of size $n$ to enumerate all $n \choose k$ combinations).

REPLY [0 votes]: $$ \begin{array}{lll}
\displaystyle \sum_{\mathbf{d}} p(\mathbf{d})\ln p(\mathbf{d}) & = &
\displaystyle \sum_{\mathbf{d}}\frac{c(\mathbf{d})}{\binom{n}{k}}\ln\frac{c(\mathbf{d})}{\binom{n}{k}} \\[10pt]
 & = & \displaystyle \binom{n}{k}^{-1} \sum_{\mathbf{d}} \left[ c(\mathbf{d})\ln c(\mathbf{d})-c(\mathbf{d})\ln\binom{n}{k}\right] \\[10pt]
& = & \displaystyle \binom{n}{k}^{-1}\left[-\binom{n}{k}\ln\binom{n}{k}+\sum_{\mathbf{d}}c(\mathbf{d})\ln c(\mathbf{d})\right] \\[10pt]
& = & \displaystyle -\ln\binom{n}{k}+\binom{n}{k}^{-1}\sum_{\mathbf{d}}c(\mathbf{d})\ln c(\mathbf{d})
 \end{array} $$
Introduce the change of variables $c(\mathbf{d})=b_1\cdots b_tb_{t+1}$ (and later $\mathbf{b}'=(b_1,\cdots,b_t)$) so
$$ \begin{array}{lll}
\displaystyle \sum_{\mathbf{d}}c(\mathbf{d})\ln c(\mathbf{d}) & = &
\displaystyle \sum_{\mathbf{b}}b_1\cdots b_{t+1} \ln(b_1\cdots b_{t+1}) \\[10pt]
& = & \displaystyle \sum_i \sum_{\mathbf{b}} b_1\cdots b_{t+1}\ln b_i \\[10pt]
& = & \displaystyle (t+1)\sum_{\mathbf{b}} b_1\cdots b_{t+1}\ln b_{t+1} \\[10pt]
& = & \displaystyle (t+1)\sum_{b_{t+1}=1}^{n-t} \left(\sum_{\mathbf{b}'}b_1\cdots b_t\right)b_{t+1}\ln b_{t+1}
\end{array} $$
Evaluate the inner sum generatingfunctionologically (set $k=b_{t+1}$):
$$ \begin{array}{lll}
\displaystyle \sum_{\mathbf{b}'}b_1\cdots b_t & = &
\displaystyle [x^{n-t-k}]\left(\sum_{b_1\ge1} b_1x^{b_1}\right)\cdots\left(\sum_{b_t\ge1}b_tx^{b_t}\right) \\[10pt]
& = & \displaystyle [x^{n-t-k}](1x+2x^2+\cdots)^t \\[1pt]
& = & \displaystyle [x^{n-t-k}]\left(\frac{x}{(1-x)^2}\right)^t \\[10pt]
& = & \displaystyle [x^{n-2t-k}](1-x)^{-2t} \\[10pt]
& = & \displaystyle \binom{-2t}{n-2t-k}(-1)^{n-k}
\end{array} $$
Therefore
$$ \sum_{\mathbf{d}} p(\mathbf{d})\ln p(\mathbf{d})=-\ln\binom{n}{k}+\frac{t+1}{\binom{n}{k}}\sum_{k=1}^{n-t} \binom{-2t}{n-2t-k}(-1)^{n-k} k\ln k $$
I'm not sure what else can be done besides express it as a rational combination of $\ln$s.
I'm not sure this is useful for getting an estimate either.


text:
\section{Integer Power Function is Bijective iff Index is Odd}
Tags: Real Functions, Powers, Bijections

\begin{theorem}
Let $n \in \Z_{\ge 0}$ be a [[Definition:Positive Integer|positive integer]].
Let $f_n: \R \to \R$ be the [[Definition:Real Function|real function]] defined as:
:$\map {f_n} x = x^n$
Then $f_n$ is a [[Definition:Bijection|bijection]] {{iff}} $n$ is [[Definition:Odd Integer|odd]].
\end{theorem}

\begin{proof}
=== Even Index ===
Suppose $n$ is [[Definition:Even Integer|even]].
Let $x \ne 0$.
Then $1^n = \paren {-1}^n$ by [[Power of Ring Negative]], so $f_n$ is not [[Definition:Injection|injective]].
Also, by [[Even Power is Non-Negative]], $f_n$ is not [[Definition:Surjective|surjective]].
By definition, a [[Definition:Bijection|bijection]] is both [[Definition:Injection|injective]] and [[Definition:Surjective|surjective]].
It follows that for [[Definition:Even Integer|even]] $n$, $f_n$ is not [[Definition:Bijection|bijective]].
{{qed|lemma}}
=== Odd Index ===
Now suppose $n$ is [[Definition:Odd Integer|odd]].
From [[Odd Power Function is Strictly Increasing]], $f_n$ is [[Definition:Injection|injective]].
From [[Odd Power Function is Surjective]], $f^n$ is [[Definition:Surjective|surjective]].
So when $n$ is [[Definition:Odd Integer|odd]], $f_n$ is both [[Definition:Injection|injective]] and [[Definition:Surjection|surjective]], and so by definition [[Definition:Bijection|bijective]].
Hence the result.
{{qed}}
\end{proof}


TITLE: Prob. 2, Sec. 20, in Munkres' TOPOLOGY, 2nd ed: The dictionary order topology on $\mathbb{R} \times \mathbb{R}$ is metrizable.
QUESTION [9 upvotes]: Here's Prob. 2, Sec. 20 in the book Topology by James R. Munkres, 2nd edition:

Show that $\mathbb{R}\times \mathbb{R}$ in the dictionary order topology is metrizable.

The dictionary order on the set $\mathbb{R} \times \mathbb{R}$ is defined as follows:

For any two points $x_1\times y_1$, $x_2 \times y_2$ $\in \mathbb{R} \times \mathbb{R}$, we define $$x_1 \times y_1 \prec x_2 \times y_2$$
  if and only if either $x_1 < x_2$, or if $x_1 = x_2$ and $y_1 < y_2$.

Now the dictionary order topology on $\mathbb{R} \times \mathbb{R}$ is the one having as a basis all sets of the fomm
$$\left( a \times b, a \times c \right) \colon= \left\{ \ x \times y \in \mathbb{R} \times \mathbb{R} \ \colon \ a \times b \prec x \times y \prec a \times c \ \right\},$$
where $a, b, c \in \mathbb{R}$ such that $b < c$.
Now if we define the funtion $d \colon \left(\mathbb{R} \times \mathbb{R} \right) \times \left( \mathbb{R} \times \mathbb{R} \right) \to \mathbb{R}$ as
$$d\left( x_1 \times y_1, x_2 \times y_2 \right) \colon = \begin{cases} 1 \ \mbox{ if } \ x_1 \neq x_2; \\ \min \left(\  \vert y_1 - y_2 \vert, \ 1 \ \right) \ \mbox{ otherwise }, \end{cases} $$
then is this function $d$ a metric? How to verify the triangle inequality?
Does this function give the dictionary order topology on $\mathbb{R} \times \mathbb{R}$?
If $x_1 = x_2 = x_3$, then we have
$$
\begin{align}
& \ d\left(x_1 \times y_1, x_3 \times y_3 \right) \\
&= \min\left( \vert y_1 - y_3 \vert, \ 1 \right) \\
&\leq \min\left( \vert y_1 - y_2 \vert, \ 1 \right)  + \min\left( \vert y_2 - y_3 \vert, \ 1 \right) \\
& \ \ \mbox{ [using the fact that this minimum is the same as the standard bounded metric on $\mathbb{R}$]} \\
&= d\left(x_1 \times y_1, x_2 \times y_2 \right) + d\left(x_2 \times y_2, x_3 \times y_3 \right).
\end{align}
$$
If $x_1 \neq x_2$ and $x_2 \neq x_3$, then we have
$$
\begin{align}
d\left(x_1 \times y_1, x_3 \times y_3 \right) &\leq 1 < 1 + 1 =  d\left(x_1 \times y_1, x_2 \times y_2 \right) + d\left(x_2 \times y_2, x_3 \times y_3 \right).
\end{align}
$$
If $x_1 = x_2$ and $x_2 \neq x_3$, then $x_1 \neq x_3$ either, and so
$$
\begin{align}
d\left(x_1 \times y_1, x_3 \times y_3 \right) &= 1 \\
&\leq d\left(x_1 \times y_1, x_2 \times y_2 \right) + 1 \\
&= d\left(x_1 \times y_1, x_2 \times y_2 \right) + d\left(x_2 \times y_2, x_3 \times y_3 \right). \end{align}$$
And, similarly for the case when $x_1 \neq x_2$ and $x_2 = x_3$.
Is this demonstration of the triangle inequality complete and correct?
PS:
Assuming that the above $d$ is a metric, here is my attempt at showing that the dictionary order topology on $\mathbb{R} \times \mathbb{R}$ is indeed the one induced by the metric $d$ above.

Let
  $$B \colon= \{ a \} \times (b, c)  = \{ \ a \times t \in \mathbb{R} \times \mathbb{R} \ \colon \ b < t < c \ \} = ( a \times b, a \times c) $$
  be a basis element for the dictionary order topology on $\mathbb{R} \times \mathbb{R}$, and let $x \times y \in B$. Then of course $x = a$ and $b < y < c$. Let us put
  $$ \epsilon \colon= \min \{ \ y-b, c-y, 1 \}.  $$
  Then if $s \times t \in B_d ( x \times y, \epsilon)$, then $s \times t \in \mathbb{R} \times \mathbb{R}$, and
  $$ d( s \times t, x \times y ) < \epsilon. \tag{1}$$
  and, as $\epsilon \leq 1$, so
  $$ d( s \times t, x \times y ) < 1, $$
  which implies that $s = x$, that is, $s = a$, and also from (0) we can conclude that
  $$ d( s \times t, x \times y ) = \min \{ \  \lvert t-y \rvert, 1 \ \}. $$
  Then (1) implies that
  $$
d( s \times t, x \times y ) = \min \{ \  \lvert t-y \rvert, 1 \ \} < \epsilon = \min \{\  y - b, c - y , 1 \ \}. $$
  So
  $$ d( s \times t, x \times y ) = \lvert t-y \rvert < \min \{ \ y-a, b-y \} , $$
  The last relation implies that $b < t < c$. So $s \times t \in B$.
Thus for any basis set $B$ for the dictionary order topology and for any element $x \times y \in B$, we have a basis element $B_d ( x \times y, \epsilon)$ for the $d$-metric topology such that
  $$ x \times y \in B_d ( x \times y, \epsilon ) \subset B. $$
  So the $d$-metric topology is finer than the dictionary order topology on $\mathbb{R} \times \mathbb{R}$.
Now let us consider an open ball $B_d( a \times b, \epsilon )$, where $a \times b \in \mathbb{R} \times \mathbb{R}$ and $\epsilon > 0$ are arbitrary. Let $x \times y \in B_d ( a \times b, \epsilon )$. Then if we choose a real number $\delta$ such that
  $$ 0 < \delta < \min \{ \ \epsilon - d( a \times b, x \times y), \ 1 \ \}, $$
  then we note that $\delta < 1$ and also that
  $$ B_d ( x \times y, \delta ) \subset B_d ( a \times b, \epsilon ). \tag{2} $$
Now let us put
  $$ B \colon= \{ \ x \ \} \times ( y-\delta, y + \delta) = \big( \ x \times (y-\delta), \ x \times (y+ \delta) \ \big). $$
  Then this $B$ is a basis element for the dictionary order topology on $\mathbb{R} \times \mathbb{R}$ such that $x \times y \in B$.
Moreover, if $s \times t \in B$, then
  $s = x$ and $y-\delta < t < y+\delta$ and hence $\lvert t-y \rvert < \delta$. But $\delta < 1$.
  So
  $$ d( s \times t, x \times y ) = \min \{ \lvert t-y \rvert, 1 \} = \lvert t-y \rvert < \delta,  $$
  which implies that $ s \times t \in B_d( x \times y, \delta )$ and hence also that $s \times t \in B_d( a \times b, \epsilon)$ by virtue of (2) above. Therefore $B \subset B_d( a \times b, \epsilon)$.
Thus we have shown that for any basis element $B_d( a \times b, \epsilon)$ for the $d$-metric topology and for any element $x \times y \in B_d( a \times b, \epsilon)$, there is a basis element $B$ for the dictionary order topology on $\mathbb{R} \times \mathbb{R}$ such that
  $$ x \times y \in B \subset B_d( a \times b, \epsilon). $$
  Thus the dictionary order topology is finer than the $d$-metric topology.
The preceding few paragraphs show that the $d$- metric topology is the same as the dictionary order topology on $\mathbb{R} \times \mathbb{R}$.

Is this proof correct? Is each and every step of it correct in its logic and presentation? If not, then where lies the problem?

REPLY [8 votes]: Here's an outline:
It might be enlightening to convince yourself that the dictionary order topology on $\mathbb{R}\times\mathbb{R}$ is the homeomorphic to the disjoint union of continuum many copies of $\mathbb{R}$.
One may check, and my recollection is that Munkres does this, that if $d$ is a metric, then $d' = \min(d,1)$ is a metric inducing the same topology. Thus, as far as the topology of metric spaces is concerned, it is entirely sufficient to consider metrics which are $\leq 1$.
Now, suppose that $(X_\alpha)_{\alpha \in I}$ are metric spaces and that the corresponding metrics $d_\alpha$ all have $d_\alpha \leq 1$. Form the disjoint union $X = \bigsqcup_{\alpha \in I} X_\alpha$ and give it its natural topology (open sets in $X$ are disjoint unions $\bigsqcup_{\alpha \in I} U_\alpha$ where $U_\alpha$ is open in $X_\alpha$). You may find it less distracting to check in this setting that $d$ defined by $d(x,y) = \begin{cases} d_\alpha(x,y) & \text{ if } x,y \in X_\alpha \\ 1 & \text{ otherwise} \end{cases}$ is a metric on $X$ and induces the aforementioned topology.
To put it in a slogan: "the disjoint union of metrizeable spaces is metrizeable".


TITLE: Calculate 2d rotation of a wall in a picture given 4 edge points
QUESTION [1 upvotes]: I want to compute the rotation (angle alpha) between the wall and the camera. (see Figure 1) The camera takes a photo as pictured in "camera view", and I get the 4 edge points of the wall (in 2d (x,y) coodinates).
How can I compute alpha if I know that the wall has to be a 16:9 rectangle if not distorted?

REPLY [0 votes]: You can see below a top view of your wall, with $B$ and $C$ the midpoints of the vertical walls, projected onto the plane of view at $B'$ and $C'$. I'm assuming that line $VA$, joining the camera to the center of the wall, is perpendicular to $B'C'$.
Let $VA=d$ and $VA'=s$. You have $BM=AB\sin\alpha$ and $AM=AB\cos\alpha$. By similarity we then obtain:
$A'B':MB=(VA-AM):VA'$, whence:
$$
A'B'={s\sin\alpha\over d-AB\cos\alpha}AB
\quad\hbox{and, analogously:}\quad
A'C'={s\sin\alpha\over d+AC\cos\alpha}AC.
$$
Summing up these equalities we thus get:
$$
\tag{1}
B'C'={sd\sin\alpha\over d^2-a^2\cos^2\alpha}BC,
$$
where I set $a=AB=AC$.

If $DE$ (with midpoint $B$) and $FG$ (with midpoint $C$) are the vertical sides of the wall (see picture below), their projections on the plane of view can be computed in a similar way because we have for instance $DE:D'E'=VB:VB'=VM:VA'$, which gives:
$$
D'E'={s\over d-a\cos\alpha}DE
\quad\hbox{and, in a similar way:}\quad
F'G'={s\over d+a\cos\alpha}FG,
$$
so that
$$
\tag{2}
D'E'+F'G'={sd\over d^2-a^2\cos^2\alpha}(DE+FG).
$$

Dividing $(1)$ by $(2)$ we finally get:
$$
{B'C'\over D'E'+F'G'}=\sin\alpha{BC\over DE+FG}.
$$
As $DE/BC=FG/BC=9/16$, from the above relation we easily obtain
$$
\sin\alpha={9\over 8}{B'C'\over D'E'+F'G'}.
$$


TITLE: Clinical trials with $0$ sensitivity
QUESTION [1 upvotes]: A probability problem which seems interesting (and I'm not sure about the answer):
Two companies A and B are developing a test for a disease (affects $1\%$ of population). Company A's test has specificity sensitivity $0.95$.
Company B does a trick, every patient is diagnosed as not having the disease.
My questions:
a). For the test developed by B, sensitivity is equal to 0 (specificity $=1$)?
b). How do we define overall success mathematically (a random person is correctly diagnosed)?
c). Is the overall success higher for test B vs test A?
For a) I want to be sure that it is so. For b) I am inclined to say that overall success is given by the $P(T,D)+P(T^c,D^c)$, where $T=\text{test is positive}$ and $D=\text{has the disease}$ and I'm not sure (I think this is case for Simpson's paradox if we take into account only the success rate).
Sensitivity is defined as:
$P(T|D)=0.95$.
Specificity is defined as:
$P(T^C|D^C)=0.95$

REPLY [1 votes]: a) I don't know what specificity and sensitivity mean exactly. Most online sources give fractions. Some give that
$$\text{sensitivity} = P(+|D)$$
where let $+$ mean a positive result, and $D$ is the event that a patient has the disease. If this is the case, then if I tell you that a particular patient has the disease, then test B will always say negative, hence
$$P(+|D) = 0$$
Similarly, I found
$$\text{specificity} = P(-|\bar D)$$
where $-$ is the event that the test says negative, and $\bar D$ that the patient does not have it. If I tell you that a particular person does not have the disease, then test B will always say negative, hence
$$P(-|D) = 1$$
So I agree.
b) I'm not sure either, but I would venture to say that we must compare the probability of accuracy for either test. For example, if I let $\mathscr A$ be the event that test A was accurate,  $T$ the test was positive, $\bar T$ the test was negative, then the probability that test A was accurate is
$$P(\mathscr A) = P(TD)+P(\bar T\bar D) = P(T|D)P(D)+P(\bar T|\bar D)P(\bar D) = .95(.01)+.95(.99)=.95 $$
where the second equality is due to the law of total probability, and in the second equality I invoked the product rule. Also, I assume you meant that sensitivity = specificity = .95
Similarly, we have
$$P(\mathscr B) = P(TD)+P(\bar T\bar D) = P(T|D)P(D)+P(\bar T|\bar D)P(\bar D) = 0(.01)+1(.99) = .99$$
c) What do you think? Why is this not surprising? What happens if instead the the disease affects $10\%$ of the population?
(Rhetorical.)


TITLE: $\sum_{n=1 }^{+\infty }a_{n}$ and $\sum_{n=m }^{+\infty }a_{n}$ or converge together or diverge together
QUESTION [1 upvotes]: Prove that series $$\sum_{n=1 }^{+\infty }a_{n}$$ and $$\sum_{n=m }^{+\infty }a_{n}$$ or converge together or diverge together. When they converge, find $\alpha$ to we have $$\sum_{n=1}^{+\infty }a_{n}=\alpha + \sum_{n=m}^{+\infty }a_{n}$$

METHOD 1:
I will prove that $\sum_{n=1 }^{+\infty }a_{n}$ converges $\Leftrightarrow$ $\sum_{n=m }^{+\infty }a_{n}$ converges.
We have the nth partial sums of seri $\sum_{n=1 }^{+\infty }a_{n}$ is $s_{n}=\sum_{k=1 }^{n }a_{k}$ and the nth partial sums of seri $\sum_{n=m }^{+\infty }a_{n}$ is $t_{n+m-1}=\sum_{k=m }^{n+m-1 }a_{k}$ (or  the nth partial sums of seri $\sum_{n=m }^{+\infty }a_{n}$ is$t_{n}=\sum_{k=m }^{n}a_{k}$ ? I think I have problem with this)
We prove that the sequence $(s_{n})$  converges $\Leftrightarrow$ sequence $(t_{n+m-1})$ converges
First, suppose we have the sequence $(s_{n})$  converges and $\lim_{n\rightarrow \infty }s_{n}=b$. We have $\forall \epsilon >0,\exists  n_{0}\in \mathbb{N}, \forall n\geq n_{0}:|s_{n}-b|<\epsilon$. Cause $n+m-1\geq n \geq n_{0}$ so $|s_{n+m-1}-b|< \epsilon \Rightarrow |t_{n+m-1}+ \sum_{k=1 }^{m-1 }a_{k}-b|< \epsilon$.
Therefore $\forall \epsilon >0,\exists  n_{0}\in \mathbb{N}, \forall n\geq n_{0}:|t_{n+m-1}-( b-\sum_{k=1 }^{m-1 }a_{k})|<\epsilon$. So $(t_{n+m-1})$ converges and $\lim_{n\rightarrow \infty }t_{n+m-1}=b-\sum_{k=1 }^{m-1 }a_{k} $
Second, suppose we have the sequence $(t_{n})$  converges and $\lim_{n\rightarrow \infty }t_{n}=b$. I'm stuck at this.
Please tell me where I was wrong. Thank you very much.

METHOD 2:
We have $$\sum_{n=1 }^{\infty}a_{n}=\sum_{n=1 }^{m-1 }a_{n}+\sum_{n=m }^{\infty}a_{n}$$
Because $\sum_{n=1 }^{m-1 }a_{n}$ is a finite sum (constant) so $\sum_{n=1 }^{\infty}a_{n}$ converges $\Leftrightarrow$ $\sum_{n=m }^{\infty}a_{n}$ converges.
It is right?

REPLY [1 votes]: We fix a $m \in \mathbb{N}$. Then:
$$\sum_{n=1}^{N} a_n=  \sum_{n=1}^{m-1}a_n+ \sum_{n=m}^{N} a_n $$
Note that $\sum_{n=1}^{m-1}a_n$ is a finite sum.
So what can we say?


text:
\begin{document}

\maketitle
\begin{abstract}
Using McCann's transportation map, we establish a transport inequality on  compact manifolds with positive Ricci curvature. This inequality contains the sharp  spectral comparison estimates.
\end{abstract}

\section{Introduction}

Extending the mass transportation approach to sharp Sobolev type inequalities from Euclidean space to curved geometries remains a challenging problem. In the present note, we propose a new twist in the classical transportation technique that allows for a transport inequality which contains sharp Poincar\'e inequalities.

The method applies to a (compact) Riemannian manifold  of dimension $n\ge 2$ having a lower bound on the Ricci curvature of the form $\ric \ge (n-1)k^2 {\rm g}$ with $k>0$ and ${\rm g}$ the Riemannian metric. By scaling the distances, we can always assume that $k=1$.

So, in the rest of the paper $M=(M, {\rm g})$ will stand for an $n$-dimensional  Riemannian manifold satisfying
\be\label{riccibound}
\ric \ge (n-1)\, {\rm g}.
\ee
The  main example is the usual sphere $S^n\subset \R^{n+1}$. The interest, perhaps,   in stating a result under the condition~\eqref{riccibound}, even if one aims at the sphere only, is that it makes it clear that we will not use any of the algebraic properties of the sphere. Our computations are modeled on the sphere case;  the extension to the   situation given by~\eqref{riccibound} relies on Bishop comparison's estimates only.
We will denote by  $d\sigma = d\vol / \vol(M) $ the Riemannian volume measure normalized to be a probability measure. The distance will be denoted $d$; recall that $M$ has diameter smaller than $\pi$.

A simple but important result is that, on such manifold $M$, the  spectral gap for the Laplacian satisfies $\lambda_1 \ge n$. Equivalently, one has the following  Wirtinger-Poincar\'e inequality: for every Lipschitz function $g$ on $M$,
\be\label{poinc}
\Var_{\sigma} (g) := \int \Big(g -\int g\, d\sigma\Big)^2 \, d\sigma \le \frac{1}{n} \int |\nabla g|^2 \, d\sigma.
\ee

The $L^2$ proof of this inequality as done by Lichnerovicz using Bochner's formula  is rather short and elementary. In the particular case of the sphere, one can also use the expansion of $g$ in the spherical harmonics basis; moreover, in this case, equality holds for linear functions, which are eigenfunctions for the spherical Laplacian.

It is well known that Poincar\'e inequalities are not well suited to mass transport techniques. However, in the Euclidean case and under appropriate curvature assumptions, one can prove very easily using mass transport (Brenier map) \emph{stronger} inequalities such as \emph{transport inequalities} or \emph{logarithmic Sobolev inequalities} (see~\cite{C02}).

So it is quite annoying that no mass transport proof of the sharp log-Sobolev inequality (see~\cite{Le}), say, is available on $M$. Indeed, the straightforward adaptation of the techniques from Euclidean space leads to a log-Sobolev inequality with a constant $(n-1)$ in place of the expected constant $n$. Similarly,  the  transport inequality (definitions are recalled below) that one gets by standard techniques is as follows:  for every $f\ge 0$ on $M$ with $\int f\, d\sigma = 1$,
\begin{equation}\label{badtransport}
\mathcal W_{c}(f\, d\sigma, \sigma) \le \int f \log f \, d\sigma
\end{equation}
for the cost $c(d):=(n-1)d^2/2$ . Linearization of this inequality gives only a weak form of~\eqref{poinc} with $1/(n-1)$ in place  of the correct $1/n$. Let us note that by an abstract result of Otto and Villani~\cite{OV}, the  log-Sobolev inequality mentioned above  with the sharp constant $n$ implies that the transport inequality~\eqref{badtransport} holds with the cost $c(d):=n\, d^2/2$. As for the log-Sobolev inequality, it is not known how to reach this inequality using mass transport.

The difficulty is to properly quantify the interplay between dimension and non-zero curvature in the mass transportation techniques.

This was partly overcome in the work of Lott and Villani~\cite{LV07} (see also Chapters~20 and~21 of~\cite{V09}). There, the authors manage to prove some Sobolev-like inequalities under the so called "curvature-dimension condition $CD(K,n)$" that imply, after linearization,  sharp spectral bounds. To be precise, their assumption is that the metric measured space $(M,d,\sigma)$ satisfies a curvature-dimension lower bound which is defined in terms of uniform convexity  along optimal transport of a class of entropy functionals. From this assumption, they deduce a (not very natural)  Sobolev-like inequality. This inequality has no reason to be sharp when the curvature is nonzero, but after linearization it gives the correct Poincar\'e inequality~\eqref{poinc} (so in a sense it is sharp at first order).  Of course, it is known, by the properties of optimal transport  on manifolds (McCann's map), that a Riemannian manifold with condition~\eqref{riccibound} satisfies the curvature-dimension criterion.  So putting all together, we see that Lott and Villani's work is already an answer to the question on how to use  mass transport to derive some sharp dimensional inequalities. But of course, it is rather indirect, and no standard inequality that one could prove using optimal transport on a manifold is easy to extract from it. Actually, this is somehow the content of the "Open Problem 21.11" in Villani's book~\cite{V09}.

Our original motivation was to provide, in the particular case of a manifold, a different,  more  direct, approach  based on the geometric properties of  McCann's transport map. The aim was to find an inequality that contained the sharp bound~\eqref{poinc}. Eventually, we managed to establish a new, suitable, transport inequality, that is an inequality between an entropy functional and a transportation cost functional (we recommend the survey~\cite{GL} for background on transport inequalities).  The question of obtaining the sharp log-Sobolev inequality using mass transport remains.

Let us introduce the following classical dimensional entropy: given a probability density $f$ on $M$, meaning a Borel nonnegative function on $M$ with $\int f \, d\sigma = 1$, we put
$$H_{n, \sigma}(f):= n \int \big( f- f^{1-1/n}\big)\, d\sigma = n - n\int f^{1-1/n} \, d\sigma.$$
Note that $H_{n, \sigma}$ is a nonnegative convex functional of $f$.

We will consider transportation costs given by  functions of the distance $d$ on $M$. Given a function $c:\R\to \R^+$ (or rather $c:[0,\pi]\to \R^+$ in our case),   the associated Kantorovich transportation cost between two Borel probability measures $\mu$ and $\nu$ on $M$ is defined by
$$\mathcal W_c(\mu, \nu):= \inf_\pi \iint  c\big(d(x,y)\big)\, d\pi(x,y)$$
where the infimum is taken over all probability measures $\pi$ on $M\times M$ projecting on $\mu$ and $\nu$, respectively.

In the proof of the Theorem below, will use McCann's map, which arises from an optimizer in the functional $\mathcal W_c$ when $c$ is the quadratic cost, $c(d)=d^2/2$; we shall recall McCann's result in detail later. However, let us emphasize that, although we will use this quadratic-optimal map, the cost in our transport inequality will be a different function of the distance.

\def\S{{\rm S}}

Our cost function is defined for $d\in [0,\pi)$ by
$${c}_n(d):= n- \frac{\sin^{n-1}(d)}{\S_n(d)^{n-1}}- (n-1)\frac{\S_n(d)}{\tan(d)}$$
and at the limit by $c_n(\pi)=+\infty$, where $\S_n$ is the familiar function defined for $d\in [0, \pi]$ by
$$ {\rm S}_n(d):=  \Big( n\int_0^d\sin^{n-1}(s)  \, ds\, \Big)^{1/n}.$$

We have, as expected,  $c_n(0)=0$ (since $\S_n(t)\sim t$ at $0$) and $c_n(d)>0$ for $d>0$.

We can now state the transport inequality satisfied by the uniform measure $\sigma$ on  $M$.

\begin{theo*}
Let $M$ be an $n$-dimensional Riemannian manifold with positive Ricci curvature satisfying~\eqref{riccibound} and let  $\sigma$ be  its normalized Riemannian volume.
Then, for every probability density $f$ on $M$ we have
$$\mathcal W_{c_n}(f\, d\sigma, \sigma) \le H_{n, \sigma} (f).$$
\end{theo*}
\medskip

We will see  that for small distances the cost $c_n(d(x,y))$ behaves  like $(n-1) d(x,y)^2/2$, so it may seem that we are back to the bad situation~\eqref{badtransport} where we were stuck with the constant $(n-1)$. However, the entropy $H_{n, \sigma}$ is~\emph{better}, i.e. smaller, than the usual entropy $\int f\log f\, d\sigma$ (note that $H_{n, \sigma}(f)\nearrow \int f\log(f) \, d\sigma$ as $n\to +\infty$) , and as a matter of fact we will reproduce the sharp Poincar\'e inequality. So there is an interesting trade-off between the cost and the entropy.
Incidentally, both sides of our inequality are zero when $n=1$ (which is a good sign), meaning that we don't derive any result on the torus $S^1$, although it might be possible,  by looking at first orders when $n\to 1$ and analyzing the proof below,  to guess what one should get in this case.

The next section contains the proof of the Theorem. In the last section we  give some properties of the cost $c_n$ and we explain how to derive the sharp spectral gap inequality~\eqref{poinc} from the Theorem.

\section{Proof of the Theorem}

We start by recalling the result of McCann~\cite{M99}. Given two (compactly supported) probability densities $f$ and $g$ on a manifold $M$ with respect to $d\vol$, the Riemannian volume, there exists a Lipschitz function $\theta:M\to \R$ such that $-\theta$ is \emph{$c$-concave} and the map
$$T(x)=\exp_x(\nabla\theta(x))$$
pushes forward $f\, d\vol$ to $g\, d\vol$. The latter means that for every (bounded or nonnegative) Borel function $u$ on $M$,
$$\int u(y)\, g(y)\, d\vol(y) = \int u(T(x)) f(x)\, d\vol(x) .$$
The $c$-concavity of $-\theta$ is defined by the property that there exists a Lipschitz function $\psi$ such that $-\te(x) = \inf_y \{\psi(y) + d(x,y)^2/2\}$.  This implies (and is formally equivalent to) that at every point $x$ where $\theta$ is differentiable, and thus $y:=T(x)$ is uniquely defined, the function $v\to  \theta(v) + \frac12 d(v,y)^2 -\frac12 d(x,y)^2 $ achieves its minimum at $v=x$.

Following a classical approach, the map $T$ is constructed by establishing that $\pi=(\id \times T) f\, d\vol$ is the optimizer for $\mathcal W_c(f\, d\vol, g\, d\vol)$ when $c$ is the quadratic cost. We will not use this  property, though.

As explained in~\cite{CMS01, CMS06}, it is possible to do, in a weak sense,  the change of variable $y=T(x)$ and to establish a pointwise Jacobian change of variable equation. To be precise, let us set, whenever it makes sense,
$$dT_x := Y (H+\Hess_x \theta)$$
where, for fixed $x\in M$, the linear operators $Y:T_xM\to T_{T(x)}M$ and $H:T_xM\to T_xM$ are defined by
$$Y := Y_x=:d(\exp_x )_{\nabla\te(x)} \AND  H := H_x:= \Hess_x d^2 _{T(x)} /2,$$
 with the notation $d_y(\cdot)=d(y,\cdot)$ for fixed $y\in M$. Then, one has
$$f(x)= g(T(x))\, \det dT_x  \qquad f\, d\vol-a.e.$$
The set of points where this equation holds is contained in the set of $x\in M$  where $\te$ is differentiable at $x$ with  $\gamma(t):=\exp_x(t\nabla \te(x))$ being the unique minimizing geodesic between $x=\gamma(0)$ and $T(x)=\gamma(1)\notin {\rm cut}(x)$, and such that $\Hess_x \theta$ exists, in the sense of Aleksandrov for the Lipschitz (and locally semi-convex) function $\te$; later we shall use  that $\tr \Hess \theta=:\Delta \te \le \Delta_{\mathcal D} \theta$  where $\Delta_{\mathcal D} \theta $ is the distributional Laplacian of the Lipschitz function $\theta$.
The $c$-concavity of $-\theta$ then implies the following, crucial monotonicity property of $T$, which holds  $f\, d\vol-a.e.$:
\begin{equation}\label{monotony}
H+\Hess \theta \ge 0
\end{equation}
In Euclidean space, $H=\id$ and we recover that $T(x)=x+\nabla \theta$ is the gradient of the convex function $|x|^2/2+\theta(x)$ (the Brenier map).

We refer the interested (or worried) reader to~\cite{CMS01, CMS06} where these facts are carefully stated and proved.

So, under the assumptions  of the Theorem, let $T(x) = \exp_x (\nabla \theta)$ be the McCann map  pushing $\sigma$ forward to $f\, d\sigma$. Denote the displacement distance by
$$\alpha(x) := d(x, T(x))= |\nabla \theta(x)|\in [0, \pi ].$$
The Jacobian equation satisfied almost everywhere is then
\begin{equation}\label{jacobian}f(T(x))^{-1}=\det\big[Y (H+\Hess_x \theta)\big]
\end{equation}
with $Y := Y_x=:d(\exp_x )_{\nabla\te(x)}$ and $H := H_x:= \Hess_x d^2 _{T(x)} /2$.

For $x\in M$ a point where equation~\eqref{jacobian} holds,  let $E_1 := \nabla\theta /|\nabla\theta|$ be the direction of transport, completed by $E_2, \ldots , E_n$ in order to have an orthonormal frame.

In this basis, the symmetric operator $H$ takes the form
$$ \begin{pmatrix}
  1  &   0  \\
 \smallskip
 0 &   K
 \end{pmatrix} $$
 and the classical Bishop comparison estimates (see e.g.~\cite{Petersen}) ensure that under~\eqref{riccibound} we have
$$\det Y \le \left( \frac{\sin ( \alpha)}{\alpha} \right)^{n-1}=:v_n(\alpha)^n\, \AND \quad
\mbox{tr}\, K \le (n-1) \frac{ \alpha }{ \tan( \alpha)}=: w_n(\alpha)     .$$
Of course, these inequalities are equalities when $M=S^n$, a case where $Y$ and $K$ can be computed explicitly (see~\cite{CE99}).

If we write $\Hess_x \theta=  \begin{pmatrix}
  a  &   b^t  \\
 \smallskip
 b &   M
 \end{pmatrix} $, where $M$ is a symmetric $(n-1)\times (n-1)$ matrix and $a:= \Hess_x \theta (E_1)\cdot E_1$ (all the quantities depend on $x$, of course), then we have

\begin{eqnarray*}
f(T(x))^{-1} &=&\det\Big[ Y\begin{pmatrix}
  1+a  &   b^t  \\
 \smallskip
 b &   K+M
 \end{pmatrix} \Big]
 \le v_n(\alpha)^n  \det\begin{pmatrix}
  1+a  &   b^t  \\
 \smallskip
 b &   K+M
 \end{pmatrix}
 \\
 & \le &  v_n(\alpha)^n \det\begin{pmatrix}
  1+a  &   0  \\
 \smallskip
 0 &   K+M
 \end{pmatrix}
 \\
 & = &  v_n(\alpha)^n \det\begin{pmatrix}
  (1+a)\mu(\alpha)^{-(n-1)} &   0  \\
 \smallskip
 0 &   \mu(\alpha)K+\mu(\alpha)M
 \end{pmatrix}
 \end{eqnarray*}

where $\mu$ is a numerical $C^1$ positive function defined on $[0, \pi]$ that will be fixed later. Note that $1+a\ge 0$ and $K+M\ge 0$ by~\eqref{monotony}.
Using  the arithmetic-geometric inequality, namely ${\det }^{1/n} \le$tr$/n$ on nonnegative matrices,  we then get that
$$n \, f(T(x))^{-1/n}
\le v_n(\alpha) \Big[ (1+a)\mu(\alpha)^{-(n-1)}+ \mu(\alpha)w_n(\alpha) + \mu(\alpha)(\Delta\te-a)\Big] $$
We integrate this inequality with respect to $\sigma$. Integration by parts gives
$$\int v_n(\alpha) \mu(\alpha) \Delta \theta \, d\sigma \le - \int (v_n \mu)'(\alpha) \nabla \alpha \cdot \nabla \te \, d\sigma.$$
When $\te$ is smooth, the previous equation is an equality; but as we explained above, the Laplacian we used is smaller than the distributional Laplacian, in general.

By construction,  $\nabla\alpha \cdot \nabla\te =\alpha  \Hess \te (E_1) \cdot E_1 = \alpha a$ (the fact that this property should be used to improve mass transportation techniques on manifold was suggested to us some years ago by Michael Schmuckenschl\"ager~\cite{Mi}).  So we find
\begin{eqnarray*}
n \int f^{1-1/n}\, d\sigma
&\le  &\int  \Big[v_n(\alpha) \mu(\alpha)^{-(n-1)} - \mu(\alpha) v_n(\alpha) -\alpha\cdot (v_n \mu)'(\alpha) \Big]\, a \,  d\sigma\\
& & \quad  + \int \big( \mu(\alpha)^{-(n-1)} + \mu(\alpha) w_n(\alpha)\big) v_n(\alpha)\, d\sigma.
\end{eqnarray*}
We now want to choose the numerical function  $ \mu$ such that for all $t\in [0, \pi)$,
\begin{equation}\label{ODEcond}
v_n(t) \mu(t)^{-(n-1)} - \mu(t) v_n(t) -t\, (v_n \mu)'(t) =0.
\end{equation}
Setting $h(t):= t \mu(t) v_n(t)$, the previous equation rewrites as
$$h'(t) = v_n(t) (h(t)/tv_n(t))^{-(n-1)}= v_n(t)^{n} t^{n-1} h(t)^{-(n-1)},$$
or equivalently
$$\frac1n (h^n)'(t) = \sin^{n-1}(t),$$
which suggests the choice $h=\S_n$.
So the function \emph{defined} by $\mu(t):= {\rm S}_n(t) /tv_n(t)$ satisfies~\eqref{ODEcond}, and consequently we have the desired inequality:
$$n \int f^{1-1/n}\, d\sigma
\le   \int \Big[ \frac{\sin^{n-1}(\alpha(x))}{\S_n(\alpha(x))^{n-1}}+ (n-1)\frac{\S_n(\alpha(x))}{\tan(\alpha(x))}\Big]\, d\sigma(x) .$$

\section{Further remarks}

We start with some properties of the function $c_n(\alpha)= n- \frac{\sin^{n-1}(\alpha)}{\S_n(\alpha)^{n-1}}- (n-1)\frac{\S_n(\alpha)}{\tan(\alpha)}$, $\alpha \in [0, \pi)$.

First, observe that for $\alpha\in [0,\pi]$,
$\int_0^\alpha  \sin(s)^{n-1} \cos(s)\, ds \le \int_0^\alpha  \sin(s)^{n-1} \, ds \le \int_0^\alpha  s^{n-1}  \, ds$ so that
$$\sin(\alpha) \le \S_n(\alpha) \le \alpha.$$
This implies that $c_n\ge 0$. It also gives that $0\le \frac{\alpha - \S_n(\alpha)}{\alpha^2} \le \frac{\alpha - \sin(\alpha)}{\alpha^2}$ and consequently, for $\alpha\to 0$,
$$\S_n(\alpha) = \alpha +o(\alpha^2).$$
In turn, this gives the behavior of $c_n(\alpha)$ when $\alpha \to 0$:
\be\label{equic}
c_n(\alpha) \sim (n-1) \alpha^2/2.
\ee
To perform this series expansion of $c_n$,  write $\S_n(\alpha) = \alpha + a \alpha^3 + o(\alpha^3)$; the coefficient $a$ indeed disappears in the second order.
We believe (from numerical examples) that the function $c_n$ is convex on $[0,\pi]$. But since we don't need this property (which seems a bit more technical), we leave this question  for another time.

It is well known that the property~\eqref{equic}  of the cost is sufficient to derive by linearization,  from the corresponding transport inequality, a Poincar\'e type inequality. The standard procedure is to first state an infimal convolution inequality (for the Hamilton-Jacobi semi-group), obtained by dualizing the transportation cost and the entropy, and then to linearize  (see~\cite{GL}). Actually, it is enough to dualize only the transportation cost (we don't want to dualize the entropy, since eventually we will linearize it).

Recall the classical Kantorovich duality:  for two probability measures $\mu$ and $\nu$ on $M$ and for a cost $c$,
$$ \mathcal W_c(\mu,\nu)= \sup_\varphi \Big\{ \int Q_c(\varphi) d\mu - \int \varphi \, d\nu \Big\}$$
where the supremum is taken over all (Lipschitz) functions $\varphi:M\to \R$, and
$$\forall x \in M, \quad Q_c(\varphi)(x) := \inf_{y\in M} \big\{ \varphi(y) + c(d(x,y))\big\}.$$
Note that $Q_c(\varphi)\le \varphi$ (provided $c\ge 0$ and $c(0)=0$) and that the bigger the cost is in terms of $d(x,y)$, the closer $Q_c(\varphi)$ is to $\varphi$.

Let $g$ be a smooth function on $M$ with $\int g \, d\sigma = 0$, and $\eps>0$ small. Applying our transport inequality to the probability density $f=1+\eps \lambda g$ where $\lambda>0$ is a constant to be fixed later, and using the above-mentioned duality with the test function $\varphi= \eps g$ we get
\be\label{dualdel}
\int Q_{c_n} (\eps g) (1+\eps \lambda g) d\sigma - \int (\eps g) \, d\sigma \le H_{n,\sigma}(1+\eps \lambda g).
\ee
On one hand we have, for the entropy term,  uniformly on $M$,
$$  n\big[ (1+\eps \lambda g) - (1+\eps \lambda g)^{1-1/n}\big]= \eps \lambda g + \eps^2 \frac{n-1}{2n}(\lambda g)^2 + o(\eps^2).$$
On the other hand, because of~\eqref{equic} we have
$$Q_{c_n} (\eps g)  = \eps\big[ g - \eps\frac{1}{2(n-1)} |\nabla g |^2+ o(\eps)\big].$$
Putting these two expansions in~\eqref{dualdel}, we see that the orders $0$ and $1$ vanish (they have to, since the constant function $\mathbf 1$ is an equality case in the transport inequality), and the inequality between  the second orders reads as
$$\Big(\lambda - \frac{n-1}{2n} \lambda^2 \Big) \int g^2 \, d\sigma\le\frac{1}{2(n-1)} \int |\nabla g |^2\, d\sigma.$$
Picking $\lambda = \frac{n}{n-1}$ we get the sharp Poincar\'e inequality
$ \int g^2 \, d\sigma\le \frac{1}{n}\int |\nabla g |^2\, d\sigma$.

config: arxiv


TITLE: Algorithm for polynomial multiplication (discrete math)
QUESTION [0 upvotes]: I have an algorithm in the course I'm currently studying, which is used to (modulo) multiply two polynomials. I've been trying to work out how it works for half an hour, but can't seem to get it right. The powerpoint doesn't give a name nor a description of how it works.
Does anyone recognize it, and could tell me how it should be used?

REPLY [0 votes]: I think it works as follows. The black rows in the screenshot are the coefficients of the red polynomial mutliplied with one monomial from the blue polynomial and shifted to the left according to the power of $x$ in the monomial from the blue polynomial. In more detail: the first black row consists of the coefficients of $76$ times the red polynomial ($76x^0$ is the monomial of degree $0$ in the blue polynomial), this row is not shifted to the left. The second black row consists of the coefficients of $4x$ times the red polynomial ($4x^1$ is the monomial of degree 1 in the blue polynomial). This row is shifted one time to the left. And so on for the other black rows. The black rows are shifted to the left so that the coefficients of the same power of $x$ are aligned in vertical columns. So far, there's no reduction modulo $251$. We get the green row at the bottom by adding up the black columns (since one column contains all the coefficients of monomials with like powes of $x$) and reducing modulo $251$. That's indeed the desired polynomial. The theoretical reason why this works is that
$$
\begin{align}
\varphi:\ & \mathbb Z[x] \rightarrow (\mathbb Z\ mod\ 251)[x] \\
& a_nx^n+\cdots+a_0x^n \mapsto (a_n\ mod\ 251)x^n + \cdots (a_0\ mod\ 251)x^0
\end{align}
$$
is a ring homomorphism, in other words multiplication and addition of integer polynomials and reduction of the coefficients modulo 251 are interchangeable.
To me, the algorithm looks pretty straightforward, and I don't know of a special name for it.


TITLE: Can a relation be reflexive on the empty set
QUESTION [0 upvotes]: I have the following binary relation that is asymmetric:
$$
\{\langle A,B\rangle , \langle B, C\rangle\}
$$
I have the definition

A binary relation $R$ is reflexive on a set $S$ iff for all elements $d\in S$ the pair $\langle d, d\rangle$ is an element of $R$

Does this mean that the binary relation is reflexive on $S$?

REPLY [1 votes]: Usually when we say that $R$ is a relation on a set $S$, we implicitly require that $R\subseteq S\times S$. So when we say that $R$ is a reflexive relation on $\varnothing$, we also require that $R\subseteq\varnothing\times\varnothing=\varnothing$, which implies that $R=\varnothing$.
Of course, $\varnothing$ is reflexive as a relation on $\varnothing$, since if $x\in\varnothing$, then $\langle x,x\rangle\in\varnothing$, is true vacuously.
But it is not true that $\{\langle A,B\rangle,\langle B,C\rangle\}$ is reflexive on $\varnothing$ because it is not a relation on $\varnothing$.


text:
\begin{document}

\maketitle

\begin{abstract}
The aim of this paper is to give an explicit formula of the invariant distribution of a quasi-birth-and-death process in terms of the block entries of the transition probability matrix using a matrix-valued orthogonal polynomials approach. We will show that the invariant distribution can be computed using the squared norms of the corresponding matrix-valued orthogonal polynomials, no matter if they are or not diagonal matrices. We will give an example where the squared norms are not diagonal matrices, but nevertheless we can compute its invariant distribution.
\end{abstract}

\section{Introduction}\label{INTRO}

The connection between random walks/birth-and-death processes and orthogonal polynomials is very well known. In both cases the state space is the set of nonnegative integers, i.e. $\mathcal{S}=\{0,1,\ldots\}$, while the parameter set is $\mathcal{T}=\{0,1,\ldots\}$ for random walks (i.e. discrete time) and $\mathcal{T}=[0,\infty)$ for birth-and-death processes (i.e. continuous time). In a series of papers, Karlin and McGregor (see \cite{KMc1, KMc2, KMc3}) found an appropriate tool to study these processes connecting the tridiagonal one-step transition probability matrix $P$ (or the infinitesimal generator $\mathcal{A}$ in the continuous time case) with a measure supported in the real line. In particular, they obtained an integral representation for the $n$-step transition probability matrix $P^n$ (or the transition probability matrix $P(t)$ in the continuous case) in terms of the spectral measure and the corresponding orthogonal polynomials, as well as the explicit expression of the invariant distribution, i.e. a row vector $\mbox{\boldmath$\pi$}$ with nonnegative components such that $\mbox{\boldmath$\pi$}P=\mbox{\boldmath$\pi$}$.

Quasi-birth-and-death processes are a natural extension where now the state space is two dimensional, i.e. $\mathcal{S}=\{(i,j) : i\geq0, 1\leq j\leq N\}$. The first component of the pair is usually called the \emph{level} and the second one the \emph{phase}. Now the one-step transition probability matrix $P$ is block tridiagonal. The link with matrix-valued orthogonal polynomials was initially raised independently by \cite{DRSZ} and \cite{G2} in discrete time (for continuous time see \cite{DR}), although the first example may be traced back to the last section of \cite{KMc3}, where the authors deal with the case of a random walk with state space the set of all integers, replacing the spectral measure by a $2 \times 2$ non-negative matrix. In \cite{DRSZ} and \cite{G2} one can find an integral representation for the $n$-step transition probability matrix $P^n$, along with other probabilistic useful results. For a much more detailed presentation of this field, as well as its connections with queueing problems in network theory and the general field of communication systems the reader should consult \cite{LR1, N, O}.

Nevertheless computing the invariant distribution of a quasi-birth-and-death process, i.e. a row vector $\mbox{\boldmath$\pi$}$ with nonnegative components such that $\mbox{\boldmath$\pi$}P=\mbox{\boldmath$\pi$}$, is a much harder problem, compared with the 1-dimensional situation. It is possible to derive nicer looking expressions for the invariant distribution for some special cases, like level-independent quasi-birth-and-death processes (see \cite{LPT}). Also in some papers (see \cite{G3, G4, G5, GdI2}) the invariant distribution was given in terms of the entries of the \emph{diagonal} norms of the corresponding matrix-valued orthogonal polynomials, giving a natural candidate. Here we will show that it is possible to derive an explicit expression of the invariant distribution in terms of the block entries of the transition probability matrix or equivalently, in terms of the squared norms of the corresponding matrix-valued orthogonal polynomials, no matter if they are or not diagonal. In fact, we will give an example of a quasi-birth-and-death process where the squared norms of the corresponding matrix-valued orthogonal polynomials are \emph{not} diagonal, but nevertheless we can compute its invariant distribution.

In Section \ref{QBDP} we will define the matrix version of the so-called potential coefficients and connect them with the squared norms of matrix-valued orthogonal polynomials. In Section \ref{IDs} we will give the explicit expression of an invariant distribution in terms of these matrix-valued potential coefficients and finally, in Section \ref{EX}, we will give the example mentioned in the paragraph above.

\section{Matrix-valued potential coefficients}\label{QBDP}

The content in this section is already known in the literature, but we will point out some properties that these matrix-valued potential coefficients have in order to prove the main result in the next section. For simplicity, we will focus on the case of discrete time quasi-birth-and-death processes. The continuous time case only suffers cosmetic changes.

Consider a nonhomogeneous discrete time quasi-birth-and-death process, i.e. a discrete time Markov process on the countable two dimensional state space $\mathcal{S}=\{(i,j) : i\geq0, 1\leq j\leq N\}$ with block tridiagonal transition probability matrix
\begin{equation}\label{PQdb}
P=\begin{pmatrix}
  B_0 & A_0   \\
  C_1 & B_1 & A_1 &  \\
  & C_2 & B_2 & A_2  \\
   &  & \ddots & \ddots & \ddots
\end{pmatrix}.
\end{equation}

The first component of the pair is usually called the level and the second one the phase. $P$ is \emph{stochastic}, i.e. all entries are nonnegative and all rows sum up to one, that is $(B_0+A_0)\textbf{e}_N=\textbf{e}_N$ and $(C_n+B_n+A_n)\textbf{e}_N=\textbf{e}_N$, $n\geq1$, where $\textbf{e}_N$ is the column vector of 1's of dimension $N$. We will assume that our process is irreducible and that the coefficients $A_n$ and $C_n$ are nonsingular matrices.  Clearly in the case when the number of phases $N$ is one we are back to the case of an ordinary birth-and-death process.

In order to link these processes with matrix-valued orthogonal polynomials the matrix $P$ needs to be transformed into a symmetric matrix. This is possible if there exists a nonsingular block diagonal matrix
$$
R=\begin{pmatrix}
  R_0 &    \\
   & R_1 &    \\
     &  &\ddots
\end{pmatrix}
$$
such that $RPR^{-1}$ is symmetric (see for instance Theorem 2.1 of \cite{DRSZ}). The matrices $R_n$ are subject to the following restrictions
\begin{equation}\label{RnR}
R_nB_nR_n^{-1}=(R_nB_nR_n^{-1})^T,\quad\mbox{and}\quad R_nA_nR_{n+1}^{-1}=(R_{n+1}C_{n+1}R_n^{-1})^T,\quad n\geq0,
\end{equation}
where $M^T$ denotes the transpose of the matrix $M$.

Let us call
\begin{equation}\label{Pin}
\Pi_n=R_n^TR_n,\quad n\geq0,
\end{equation}
which are obviously symmetric. From \eqref{RnR} we have that $\Pi_n$, $n\geq0$, satisfy
\begin{equation}\label{Con1}
\Pi_nB_n=B_n^T\Pi_n,\quad n\geq0,
\end{equation}
and
\begin{equation}\label{Con2}
\Pi_nA_n=C_{n+1}^T\Pi_{n+1},\quad n\geq0.
\end{equation}

Condition \eqref{Con2} gives an explicit formula for $\Pi_n$, $n\geq1$, given $A_n$, $C_n$ and $\Pi_0$:
\begin{equation}\label{MVPC}
\Pi_n=(C_1^TC_2^T\cdots C_{n}^{T})^{-1}\Pi_{0}(A_0A_1\cdots A_{n-1}),\quad n\geq1,
\end{equation}
This formula is similar to the scalar potential coefficients for birth-and-death processes (see \cite{KMc2}), so we will call them \emph{matrix-valued potential coefficients}.

Under these assumptions, there always exists a weight matrix $W$ such that the matrix-valued polynomials defined by the three-term recurrence relation
\begin{equation}\label{ttrrst}
xQ_n(x)=A_{n}Q_{n+1}(x)+B_nQ_n(x)+C_{n}Q_{n-1}(x),\quad n\geq0,
\end{equation}
where $Q_{-1}(x)=0$ and $Q_0(x)=I$, are orthogonal, i.e.
$$
\int Q_n(x)W(x)Q_m^T(x)dx=\|Q_n\|^2_W\delta_{nm}.
$$
In particular, as it is remarked in page 121 of \cite{DRSZ}, $\Pi_0$ can be given in terms of the 0-th moment $S_0=\int W(x)dx$. For an orthonormal family $(\widetilde{Q}_n)_n$ we have that
$$
I=\int \widetilde{Q}_0(x)W(x)\widetilde{Q}_0^T(x)dx=R_0S_0R_0^{T}
$$
Therefore
\begin{equation*}\label{Pn0}
\Pi_0=S_0^{-1}=(\|Q_0\|_W^2)^{-1}.
\end{equation*}
That means that for every weight matrix $W$ associated with the Jacobi matrix \eqref{PQdb}, the matrix-valued potential coefficients are defined recursively using \eqref{MVPC} in a unique way.

\begin{nota}
 Observe that the sequence $(R_n)_n$ is not unique in the sense that we can always consider any other sequence $(U_nR_n)_n$, where $(U_n)_n$ is any sequence of orthogonal matrices and we will get another family of orthonormal polynomials. Nevertheless, the matrix-valued potential coefficients $\Pi_n$ are always unique (see \eqref{Pin}).
\end{nota}

Finally we will show that the matrix-valued potential coefficients can be given in terms of the squared norms of the matrix-valued orthogonal polynomials. From the three-term recurrence relation \eqref{ttrrst} we can multiply on the right by $WQ_n$, $WQ_{n+1}$ and $WQ_{n-1}$, respectively, and integrate in such a way that the sequence of squared norms $\|Q_n\|_W^2$ satisfies the following relations
$$
B_n\|Q_n\|_W^2=\|Q_n\|_W^2B_n^T,\quad \|Q_n\|_W^2C_{n+1}^T=A_n\|Q_{n+1}\|_W^2,\quad n\geq0.
$$
But these are just the relations \eqref{Con1} and \eqref{Con2}. Since $\Pi_0=(\|Q_0\|_W^2)^{-1}$, we have that
\begin{equation}\label{Pn0N}
\Pi_n=(\|Q_n\|_W^2)^{-1},\quad n\geq0.
\end{equation}

In particular we have that the matrix-valued potential coefficients $\Pi_n$ are positive semi-definite matrices.

\section{The invariant distribution}\label{IDs}
With all the information from the last section we are able to give a very natural candidate for the invariant distribution of the process $P$ using the matrix-valued potential coefficients $\Pi_n$.

\begin{teor}\label{Teo}
Let $P$ be the transition probability matrix given by \eqref{PQdb}. Define the sequence of matrices $\Pi_n$, $n\geq1$, as in \eqref{MVPC} with $\Pi_0=(\int W(x)dx)^{-1}$ or, equivalently, as in \eqref{Pn0N}. Consider the following row vector
\begin{equation}\label{ID}
\mbox{\boldmath$\pi$}=
((\Pi_0\textbf{e}_N)^T;(\Pi_1\textbf{e}_N)^T;(\Pi_2\textbf{e}_N)^T;\cdots),
\end{equation}
where $\textbf{e}_N$ is the column vector of 1's of dimension $N$.  Then $\mbox{\boldmath$\pi$}$ is an invariant distribution for the process $P$, i.e. all components of $\mbox{\boldmath$\pi$}$ are nonnegative and
\begin{equation}\label{IDprop}
\mbox{\boldmath$\pi$}P=\mbox{\boldmath$\pi$}.
\end{equation}
\end{teor}
\proof
All components of $\mbox{\boldmath$\pi$}$ are nonnegative since $\Pi_n$ are positive semi-definite matrices (see \eqref{Pn0N}).

To prove \eqref{IDprop}, we have to check that
$$
(\Pi_0\textbf{e}_N)^TB_0+(\Pi_1\textbf{e}_N)^TC_1=(\Pi_0\textbf{e}_N)^T
$$
and
$$
(\Pi_{n-1}\textbf{e}_N)^TA_{n-1}+(\Pi_{n}\textbf{e}_N)^TB_n+(\Pi_{n+1}\textbf{e}_N)^TC_{n+1}=(\Pi_n\textbf{e}_N)^T,\quad n\geq1.
$$
The first equality holds using properties \eqref{Con1}, \eqref{Con2} and the fact that $P$ is stochastic, since
$$
\textbf{e}_N^T(\Pi_0B_0+\Pi_1C_1)=\textbf{e}_N^T(B_0^T\Pi_0+A_0^T\Pi_0)=[(B_0+A_0)\textbf{e}_N]^T\Pi_0=(\Pi_0\textbf{e}_N)^T,
$$
Similarly, for $n\geq1$
$$
\textbf{e}_N^T(\Pi_{n-1}A_{n-1}+\Pi_{n}B_n+\Pi_{n+1}C_{n+1})=[(A_n+B_n+C_n)\textbf{e}_N]^T\Pi_n=(\Pi_n\textbf{e}_N)^T.
$$
\hfill \endproof

\begin{nota}
The same result holds in the continuous time case. In this case, the transition probability matrix $P$ is replaced by an infinitesimal generator $\mathcal{A}$, block tridiagonal as in \eqref{PQdb}, but with $(B_0+A_0)\textbf{e}_N=0$ and $(C_n+B_n+A_n)\textbf{e}_N=0$, $n\geq1$ (see \cite{DR} for more details). Therefore the row vector $\mbox{\boldmath$\pi$}$ defined by \eqref{ID} is an invariant distribution for the process, i.e. all components are nonnegative and
$$
\mbox{\boldmath$\pi$}\mathcal{A}=0.
$$
\end{nota}

\bigskip

Let us make a few comments about the unicity of this invariant distribution. If the process is recurrent then there exists a unique invariant distribution given by \eqref{ID} (see Theorem 5.4 of \cite{S}). But if the process is transient there are no results about unicity. In fact, the case of a random walk on the integers
treated in \cite{KMc3} gives (for $p\neq q$) an example of a transient process where the invariant distribution is not unique.

In Section \ref{QBDP} we saw that the matrix-valued potential coefficients $\Pi_n$ are defined in terms of the corresponding weight matrix $W$ and the block entries of $P$. These quantities are constructed in a unique way, so the question of the unicity of the invariant distribution is the same as the question of the unicity of the weight matrix $W$ corresponding to the equivalent class  of block tridiagonal Jacobi matrices $P$ by unitary transformations. So if we can guarantee that the corresponding weight matrix is unique, then the invariant distribution will be also unique. Nevertheless there are not general results to determine if the weight matrix associated with a block tridiagonal Jacobi matrix is unique.

\bigskip

Observe that Theorem \ref{Teo} gives a way to compute an invariant distribution even if the squared norms of the corresponding matrix-valued orthogonal polynomials are not diagonal. Until now, all the examples introduced in the literature had the special lucky property that these norms were diagonal matrices. In the following section we will give an example of a quasi-birth-and-death process where the squared norms of the corresponding matrix-valued orthogonal polynomials are \emph{not} diagonal, but nevertheless, using \eqref{ID}, we can compute its invariant distribution. This example, as far as the author knows, may be the first quasi-birth-and-death process with this property in the literature.

\section{The example}\label{EX}

Consider the following $2\times2$ weight matrix
\begin{equation*}\label{W}
 W(x)=x^{\alpha}(1-x)^{\beta}\begin{pmatrix}
                                   kx^2+\beta-k+1 & (\beta-k+1)(1-x)\\
                                   (\beta-k+1)(1-x) & (\beta-k+1)(1-x)^2
                                   \end{pmatrix},\quad x\in[0,1],
\end{equation*}
where $\alpha,\beta>-1$ and $0<k<\beta+1$. This weight matrix was introduced in \cite{DdI2} in a different context, that of searching second-order differential operators having several families of matrix-valued orthogonal polynomials as eigenfunctions. Let us call $(\widehat{P}_n)_n$ the unique monic family of matrix-valued orthogonal polynomials associated with $W$.

Let $\Delta_0$ be the nonsingular matrix
\begin{equation*}\label{TT}
\Delta_0=\begin{pmatrix}
                                   1 & -\frac{\alpha+\beta-k+3}{\alpha+2\beta-2k+4}\\
                                   1 & -\frac{\alpha+2\beta-2k+4}{\beta-k+1}
                                   \end{pmatrix},
\end{equation*}
and let us consider the equivalent weight matrix
\begin{equation*}\label{Ww}
\widetilde{W}=\Delta_0W\Delta_0^T.
\end{equation*}
Now we consider a special family of matrix-valued orthogonal polynomials with respect to $\widetilde{W}$ of the following form
\begin{equation*}\label{Qn}
Q_n(x)=\Delta_n\widehat{P}_n(x)\Delta_0^{-1},
\end{equation*}
where
\begin{equation*}\label{Deln}
\Delta_n=\begin{pmatrix}
                             {\footnotesize \mbox{$-\dfrac{a_n(n^2+n(\alpha+\beta+3)+k(\alpha+2\beta-2k+4))}{k(\alpha+\beta-k+n+3)}$}} &a_n\\
                                  b_n  &{\footnotesize \mbox{$-\dfrac{b_n(n^2+n(\alpha+\beta+3)+k(\alpha+2\beta-2k+4))}{(k+n)(\beta-k+1)}$}}
                                   \end{pmatrix},
\end{equation*}
with
\begin{equation*}
a_n= {\Large \mbox{$-\frac{(\alpha+\beta+n+3)_n(\alpha+\beta-k+n+3)(n(\alpha+\beta+n+2)+k(\alpha+1))}{(\beta+2)_n(n(\alpha+\beta)^2+n(2n+5)(\alpha+\beta)+n(n+2)(n+3)+k(2\alpha\beta+2\beta-k(n+2)+\alpha^2+5\alpha-2k\alpha-n^2+4))}$}},
\end{equation*}
$$
b_n=\frac{(\alpha+\beta+n+3)_n(k+n)(n(\alpha+\beta+n+2)+k(\alpha+1))}{(\beta+2)_n((n^2+2nk)(\alpha+\beta)+n(n+5)k+k^2(\alpha-n+1)+n^2(n+3))},
$$
and $(z)_n$ will denote the Pochhammer symbol defined by
$(z)_{n}=z(z+1)\cdots(z+n-1)$ for $n>0$, $(z)_{0}=1$. Observe that $Q_0=I$. The choice of the leading coefficient $\Delta_n\Delta_0^{-1}$ of the family of polynomials $(Q_n)_n$ is motivated by the remarkable fact that
\begin{equation}\label{qn1}
    Q_n(1)\textbf{e}_2=\textbf{e}_2,
\end{equation}
where $\textbf{e}_2$ is the $2$-dimensional column vector with all
entries equal to 1. In other words, the sum of the elements in each
row of $Q_n(1)$ gives the value 1.

The family of matrix-valued orthogonal polynomials introduced above satisfies a
three-term recursion relation
\begin{equation}\label{ttrrst2}
xQ_n(x)=A_{n}Q_{n+1}(x)+B_nQ_n(x)+C_{n}Q_{n-1}(x),\quad n\geq0,
\end{equation}
where $Q_{-1}(x)=0$ and $Q_0(x)=I$ and $A_n, B_n, n\geq0$, $C_n, n\geq1$ are $2\times2$ full matrices with nonnegative entries. The corresponding Jacobi matrix
\begin{equation}\label{PP}
P=\begin{pmatrix}
  B_0 & A_0   \\
  C_1 & B_1 & A_1   \\
   & C_2 & B_2 & A_2   \\
   &  & \ddots & \ddots & \ddots
\end{pmatrix}
\end{equation}
is stochastic. This is a consequence of choosing the family $(Q_n)_n$ with the property \eqref{qn1}. Indeed, applying
both sides of the identity \eqref{ttrrst2} to the vector $\textbf{e}_2$, setting $x=1$ and using \eqref{qn1} we obtain that $(B_0+A_0)\textbf{e}_2=\textbf{e}_2$ and $(C_n+B_n+A_n)\textbf{e}_2=\textbf{e}_2$, $n\geq1$, i.e. the sum of the entries in each row of $P$ equals one. Therefore, it gives a quasi-birth-and-death process with two phases ($N=2$) and depending on three parameters, $\alpha, \beta$ and $k$.

The state space and the corresponding one-step transitions look as follows (see \cite{G2, G3, GdI2} for an explanation of the labeling and ordering of the states)

\bigskip

\bigskip

\bigskip

$$\begin{psmatrix}[rowsep=2.5cm,colsep=3cm]
  \cnode{.55}{0}& \cnode{.55}{2} & \cnode{.55}{4} & \cnode{.55}{6} & \pnode{8} \\
  \cnode{.55}{1} & \cnode{.55}{3} & \cnode{.55}{5} & \cnode{.55}{7} & \pnode{9} \\
\psset{nodesep=3pt,arcangle=15,labelsep=2ex,linewidth=0.3mm,arrows=->,arrowsize=1mm
3} \nccurve[angleA=130,angleB=170,ncurv=4]{0}{0}
\nccurve[angleA=190,angleB=230,ncurv=4]{1}{1}
\nccurve[angleA=70,angleB=110,ncurv=4]{2}{2}
\nccurve[angleA=70,angleB=110,ncurv=4]{4}{4}
\nccurve[angleA=70,angleB=110,ncurv=4]{6}{6}
\nccurve[angleA=250,angleB=290,ncurv=4]{3}{3}
\nccurve[angleA=250,angleB=290,ncurv=4]{5}{5}
\nccurve[angleA=250,angleB=290,ncurv=4]{7}{7} \ncarc{0}{2}
\ncarc{2}{0} \ncarc{2}{4} \ncarc{4}{2} \ncarc{4}{6} \ncarc{6}{4}
\ncarc{6}{8} \ncarc{8}{6} \ncarc{0}{1} \ncarc{1}{0} \ncarc{2}{1}
\ncarc{1}{2} \ncarc{1}{3} \ncarc{3}{1} \ncarc{2}{3} \ncarc{3}{2}
\ncarc{4}{3} \ncarc{3}{4}\ncarc{3}{5} \ncarc{5}{3}\ncarc{5}{4}
\ncarc{4}{5}\ncarc{5}{6} \ncarc{6}{5}\ncarc{5}{7}
\ncarc{7}{5}\ncarc{6}{7} \ncarc{7}{6}\ncarc{7}{8}
\ncarc{8}{7}\ncarc{7}{9} \ncarc{9}{7} \ncarc{0}{3}\ncarc{3}{0}
\ncarc{2}{5}\ncarc{5}{2}\ncarc{4}{7}\ncarc{7}{4}\ncarc{6}{9}\ncarc{9}{6}
\psset{labelsep=-4.25ex}\nput{90}{0}{1}
\psset{labelsep=-4.25ex}\nput{90}{2}{3}
\psset{labelsep=-4.25ex}\nput{90}{4}{5}
\psset{labelsep=-4.25ex}\nput{90}{6}{7}
\psset{labelsep=-4.25ex}\nput{90}{1}{2}
\psset{labelsep=-4.25ex}\nput{90}{3}{4}
\psset{labelsep=-4.25ex}\nput{90}{5}{6}
\psset{labelsep=-4.25ex}\nput{90}{7}{8}
\end{psmatrix}
$$

\vspace{-1cm}

Finally the squared norms $\|Q_n\|_{\widetilde{W}}^2$ are $2\times2$ full matrices (not diagonal). Therefore, using Theorem \ref{Teo}, we get that an invariant distribution for this process is given by
\begin{equation}\label{ID2}
\mbox{\boldmath$\pi$}=
((\Pi_0\textbf{e}_2)^T;(\Pi_1\textbf{e}_2)^T;(\Pi_2\textbf{e}_2)^T;\cdots),
\end{equation}
where
\begin{equation}\label{Pn0N2}
\Pi_n=(\|Q_n\|_{\widetilde{W}}^2)^{-1},\quad n\geq0.
\end{equation}
We can use Theorem 8.1 of \cite{GdI2} to study the recurrence of the process, since our weight matrix has similar properties to that introduced in \cite{GdI2}. The Markov process that results from $P$ is never positive recurrent. If $-1<\beta\leq0$ then the process is null recurrent. If $\beta>0$ then the process is transient. For $-1<\beta\leq0$ the invariant distribution will be unique, as we mentioned at the end of Section \ref{IDs}.

The explicit expressions of $A_n$, $B_n$, $C_n$ and $\|Q_n\|_{\widetilde{W}}^2$ are too long to be displayed here. Instead, we will give all these data for the special case of $\alpha=\beta=0$ and $k=\frac{1}{2}$.  Similar expressions can be derived for other values of the parameters $\alpha, \beta$ and $k$. The coefficients of the three-term recurrence relation \eqref{ttrrst2} are, for $n\geq0$
\begin{align*}
A_n=&\left(\begin{array}{cc}
                                          \dfrac{(n+3)^2(2n^2+4n+1)(4n^2+18n+17)(16n^4+128n^3+348n^2+368n+117)}{2(n+2)(2n+3)(2n^2+8n+7)(4n^2+10n+3)(16n^4+160n^3+572n^2+860n+463)} & * \\
                                         \dfrac{2(n+3)^2(2n^2+4n+1)^2(4n^2+18n+17)}{(2n+3)(2n^2+8n+7)(4n^3+14n^2+9n+1)(16n^4+160n^3+572n^2+860n+463)}   & * \\
                                        \end{array}\right.\\
& \left.\begin{array}{cc}
                                          * & \dfrac{2(n+3)(2n^2+4n+1)(2n^2+12n+17)(4n^3+26n^2+49n+28)}{(n+2)(2n+3)(2n^2+8n+7)(4n^2+10n+3)(16n^4+160n^3+572n^2+860n+463)} \\
                                          * & \dfrac{(n+3)(2n^2+4n+1)(4n^3+26n^2+49n+28)(16n^4+128n^3+348n^2+368n+125)}{2(2n+3)(2n^2+8n+7)(4n^3+14n^2+9n+1)(16n^4+160n^3+572n^2+860n+463)} \\
                                        \end{array}\right),
\end{align*}
\begin{align*}
B_n=&\left(\begin{array}{cc}
                                         \dfrac{32n^8+384n^7+1928n^6+5256n^5+8450n^4+8148n^3+4577n^2+1365n+163}{(2n^2+4n+1)(2n^2+8n+7)(16n^4+96n^3+188n^2+132n+31)}  & * \\
                                         \dfrac{(n+2)(4n^2+10n+3)(32n^6+256n^5+760n^4+1040n^3+674n^2+186n+13)}{2(2n^2+4n+1)(2n^2+8n+7)(4n^3+14n^2+9n+1)(16n^4+96n^3+188n^2+132n+31)} & * \\
                                        \end{array}\right.\\
& \left.\begin{array}{cc}
                                          * & \dfrac{(4n^3+14n^2+9n+1)(32n^6+320n^5+1240n^4+2320n^3+2114n^2+834n+121)}{2(n+2)(2n^2+4n+1)(2n^2+8n+7)(4n^2+10n+3)(16n^4+96n^3+188n^2+132n+31)} \\
                                          * & \dfrac{(2n^2+6n+3)(4n^3+18n^2+21n+6)(4n^3+18n^2+21n+3)}{(2n^2+4n+1)(2n^2+8n+7)(16n^4+96n^3+188n^2+132n+31)} \\
                                        \end{array}\right),
\end{align*}
and for $n\geq1$
\begin{align*}
C_n=&\left(\begin{array}{cc}
                                         \dfrac{n(n+1)(4n^2+2n-3)(32n^6+192n^5+328n^4+32n^3-226n^2-4n+33)}{2(n+2)(2n+3)(2n^2-1)(4n^2+10n+3)(16n^4+32n^3-4n^2-20n+7)}  & * \\
                                         \dfrac{n(n+1)(4n^2+2n-3)(8n^4+32n^3+36n^2+8n-5)}{(2n+3)(2n^2-1)(4n^3+14n^2+9n+1)(16n^4+32n^3-4n^2-20n+7)} & * \\
                                        \end{array}\right.\\
 & \left.\begin{array}{cc}
                                          * &  \dfrac{n(4n^3+2n^2-7n+2)(8n^4+32n^3+36n^2+8n-5)}{(n+2)(2n+3)(2n^2-1)(4n^2+10n+3)(16n^4+32n^3-4n^2-20n+7)}\\
                                          * & \dfrac{n(4n^3+2n^2-7n+2)(32n^6+192n^5+392n^4+288n^3-34n^2-132n-43)}{2(2n+3)(2n^2-1)(4n^3+14n^2+9n+1)(16n^4+32n^3-4n^2-20n+7)} \\
                                        \end{array}\right).
\end{align*}
We see that all entries of the transition probability matrix \eqref{PP} are nonnegative rational functions in $n$, and it is very remarkable that the sum of the entries in each row of $P$ equals one.

The corresponding squared norms are the $2\times2$ non-diagonal matrices
\begin{align*}
\|Q_n\|_{\widetilde{W}}^2=&\left(\begin{array}{cc}
                                          \dfrac{(2n^2+4n+1)(16n^6+160n^5+628n^4+1212n^3+1173n^2+514n+79)}{(n+1)(2n+3)(4n^2+10n+3)^2(n+2)^3} & * \\
                                          -\dfrac{(2n+1)(2n+5)(2n^2+4n+1)}{2(n+1)(n+2)^2(4n^2+10n+3)(4n^3+14n^2+9n+1)}& * \\
                                        \end{array}\right.\\
 & \left.\begin{array}{cc}
                                          * & -\dfrac{(2n+1)(2n+5)(2n^2+4n+1)}{2(n+1)(n+2)^2(4n^2+10n+3)(4n^3+14n^2+9n+1)}\\
                                          * & \dfrac{(2n^2+4n+1)(16n^6+128n^5+388n^4+564n^3+417n^2+152n+22)}{(n+1)(n+2)(2n+3)(4n^3+14n^2+9n+1)^2} \\
                                        \end{array}\right).
\end{align*}

The unique (the process is null recurrent in this case) invariant distribution is given by \eqref{ID2} where $\Pi_n\textbf{e}_2$ can be calculated using \eqref{Pn0N2}
\begin{equation*}
\Pi_n\textbf{e}_2=\begin{pmatrix}
  \dfrac{2(n+1)^2(n+2)^2(2n+3)(4n^2+10n+3)(4n^2+14n+9)}{(2n^2+4n+1)(2n^2+8n+7)(16n^4+96n^3+188n^2+132n+31)} \\
 \dfrac{2(n+1)(n+2)(2n+3)(4n^3+14n^2+9n+1)(4n^3+22n^2+33n+8)}{(2n^2+4n+1)(2n^2+8n+7)(16n^4+96n^3+188n^2+132n+31)}\\
\end{pmatrix},\quad n\geq0.
\end{equation*}

If we denote by $\mbox{\boldmath$\pi$}^n_1$ and $\mbox{\boldmath$\pi$}^n_2$ the two components of $\Pi_n\textbf{e}_2$, we can study the behavior of the invariant distribution in Figure 4.1, a luxury we can afford since we have an analytic expression.

\bigskip

\bigskip

\begin{figure}[h]
\begin{center}\begin{minipage}{6cm}
\includegraphics[35,0][235,143]{graph.eps}
\caption{$\alpha=0, \beta=0, k=0.5$}
\end{minipage}\end{center}
\end{figure}


TITLE: Why is the sum $\sum_{n=0}^{N-1}\left(e^{\frac{\pi i j n}{N}}\right)^2=0$?
QUESTION [0 upvotes]: The background to this question is it's the proof that $\|\cos\left(\frac{jn\pi}{N}\right)\|=\sqrt{\frac{N}{2}}$ and  $\|\sin\left(\frac{jn\pi}{N}\right)\|=\sqrt{\frac{N}{2}}$ asked by question 7 here. My question is why is RED 1 =0 and why are RED 2a and 2b both separately equal to zero? It's not obvious to me from the proof. I recognize that it's true from the orthogonality of the Cos/Sin series These are the Discrete sin/cos pair so $\cos\left(\frac{jn\pi}{N}\right)=\cos\left(\frac{n\pi x_h}{l}\right)$ when converting back to the continuous fourier series which are orthogonal after integrating, but as stated in the proof, this conclusion is what is asked to be proven, so I'm not seeing in the proof how it was proven. Also this question is from Gockenbach Partial differential equations ch. 12.1 or 9.1 depending on the edition.

REPLY [1 votes]: Using $$\sum^{N-1}_{n=0} x^n = \frac{1 - x^N}{1-x}$$ when $x\neq 1$, we see $$\sum^{N-1}_{n=0} e^{2 \pi i j n/N} = \frac{1 - e^{2\pi i j n}}{1 - e^{2 \pi i j/N}} = 0$$ since $e^{2\pi i jn} = 1$ and $e^{2\pi i j/N} \neq 1$.


TITLE: standard zero free region of automorphic L-function on GL(N)
QUESTION [9 upvotes]: Let $L(s,\pi)$ be the standard(Godement-Jacquet) $L$-function of $\pi$, where $\pi$ is a cuspidal automorphic represetation of $GL(m,A_Q)$.
What's the standard zero-free region for $L(s,\pi)$? any reference?
ANy progress beyond standard one?

REPLY [11 votes]: Let $Q=Q(\pi,it)$ be the analytic conductor of $\pi\otimes|\det|^{it}$. For $\pi$ not self-dual, the method of de la Vallée-Poussin yields the zero-free region $\sigma>1-c/\log Q$ for some effective constant $c>0$ depending on $m$. For $\pi$ self-dual, this is still valid up to a possible exceptional zero $\sigma_0$ that might exist on the real axis within this region. Still, we can bound $\sigma_0<1-cQ^{-C}$ with some effective constants $c,C>0$ depending on $m$.
For more details and some additional conditions under which the exceptional zero does not exist, see Hoffstein-Ramakrishnan: Siegel zeros and cusp forms. See especially Theorem A and Corollary 3.2.
Another very relevant paper is Brumley: Effective multiplicity one on $\mathrm{GL}_N$ and narrow zero-free regions for Rankin-Selberg L-functions. See especially Theorem 5 and Corollary 6 there.


TITLE: Why if $H$ be non abelian group , then $ \frac {H}{Z(G) \cap H} $ is non abelian
QUESTION [1 upvotes]: let $G$ be a group and $H$ be a subgroup of $G$.
Why if $H$ be non abelian group , then $ \frac {H}{Z(G) \cap  H} $ is non abelian?

REPLY [2 votes]: I don't think this is true. You should try with a "small" non abelian group $G$ and $H:=G$.

Take $G:=\mathbb{D}_4$ the dihedral group with $8$ elements and $H:=G$. Then $Z(G)\cap H=Z(G)$ is of order $2$ whence $\frac{H}{Z(G)\cap H}=\frac{G}{Z(G)}$ is of order $4$ and whence is abelian. But $G=H$ is not abelian.

Edit : about the remark of Geoff Robinson, $\frac{H}{H\cap Z(G)}$ cannot be cyclic when $H$ is non abelian.
The idea is to use the fact that $H\cap Z(G)\leq Z(H)$.

 When $H$ is non abelian, one can show (classical exercise) that $H/Z(H)$ is not cyclic (if it were cyclic then any element of $H$ would be written $\gamma^kz$ with $z\in Z(H)$ and $\gamma$ a fixed element of $H$). Now, since $H\cap Z(G)\leq Z(H)$ we get $H/Z(H)\leq H/(H\cap Z(G))$ since $H/Z(H)$ is not cyclic $H/(H\cap Z(G))$ cannot be cyclic either (all subgroups of cyclic groups are cyclic groups).


TITLE: Pulling six christmas crackers from a pool of six people
QUESTION [1 upvotes]: A family of six has six Christmas crackers to pull. Each person will pull two crackers, each with a different person. In how many different ways can this be done?
So far I have found $20$ possibilities, because the six members can be separated into two groups of $3$. Each group of 3 has one distinct way of pulling crackers, and there are ${6 \choose 3}$ ways of selecting two groups of 3, giving $20$ ways of cracking crackers. However I'm stuck on how to find more from here onwards. The desired answer is $70$.

REPLY [1 votes]: You've got the right idea. However, the number of ways dividing $6$ people into two groups of three is not 20. It is 10. You may want to read more about it here.
The other case you're missing is when the six people form a cycle of their own - i.e. if you place the family members on a round table, each person forms a pair with their neighbour. The number of ways in which this is done is $\frac{5!}{2} = 60.$
Thus, the answer is $$10 + 60 = 70$$


text:
\section{Introduction}
Deep neural networks (DNNs) have empirically succeeded in achieving high performances in various machine-learning tasks \citep{LeCun2015DeepLearning, Goodfellow2016DeepLearning}.
Nevertheless, their theoretical understanding has been limited, and their success depends much on the heuristic search setting, such as architectures and hyper-parameters.
In order to understand and improve the training of DNNs, researchers have developed some theories to investigate, for instance, vanishing/exploding gradient problems \citep{Schoenholz2016DeepPropagation},  the shape of the loss landscape \citep{Pennington2018spectrum, Karakida2019universal}, the global convergence of training and the generalization \citep{Jacot2018NeuralNetworks}.

The Fisher information matrix (FIM) has been a fundamental quantity for such theoretical understandings.  The FIM describes the local metric of the loss surface concerning the KL-divergence function \citep{Amari2016}.
In particular, the eigenvalue spectrum describes the efficiency of optimization methods.
For instance, the maximum eigenvalue determines an appropriate size of the learning rate of the first-order gradient method for convergence \citep{Cun1991eigenvalues, Karakida2019universal, wu2019how}.
In spite of its importance, the spectrum of FIMs in neural networks is not revealed enough from a theoretical perspective.
The reason is that it has been limited to random matrix theory for shallow networks \citep{Pennington2018spectrum} or mean-field theory for eigenvalue bounds, which may be loose in general \citep{Karakida2019normalization}.
Thus, we need an alternative approach applicable to DNNs.

It is well known that it is difficult to reduce the training error in very deep models without careful prevention of the vanishing/exploding of the gradient.
Naive settings (i.e., activation function and initialization) cause  vanishing/exploding gradients, as long as the network is relatively deep.
The dynamical isometry \citep{Saxe2014exact,Pennington2018emergence} was proposed to solve this problem. The dynamic isometry can facilitate training by setting the input-output Jacobian's singular values to be one, where the input-output Jacobian is the Jacobian matrix of the DNN at a given input.
Experiments have shown that with initial values and models satisfying dynamical isometry, very deep models can be trained without gradient vanishing/exploding;
\citep{Pennington2018emergence,xiao2018dynamical,sokol2018information} have found that DNNs achieve approximately dynamical isometry over random orthogonal weights, but they do not do so over random Gaussian weights.

We investigate the asymptotic spectrum of the FIM of multi-layer perceptrons satisfying dynamical isometry in the present work.
In order to handle the mathematical difficulty to treat the spectrum of the full FIM, we focus on the \emph{conditional FIM} given a single sample.

While analyzing the spectrum of DNN, we often face mathematical difficulties caused by the non-linearity of the activation function, the depth of the network, and random matrices.
To handle such difficulty,  we use the free probability theory (FPT).
The FPT, which is invented by Voiculescu for understanding von Neuman algebras \citep{Voiculescu1985symmetries},  provides algebraic tools of random matrix theory \citep{voiculescu1991limit}.

Since DNN's FIM is a random matrix polynomial of the Jacobian, the FPT provides tools for understanding FIM's spectral distribution.  We use these tools to obtain the propagation of spectral distributions through the layers and then obtain the critical recursive equation of the spectral distributions.

Our findings are the following.

The main finding is that the dynamical isometry makes the spectrum of the conditional FIM concentrates on the maximum spectrum, which value grows linearly as the depth increases (\cref{thm:maximum}).
An interesting phenomenon is that the FIM spectrum depends on the depth, unlike the spectrum of the input-output Jacobian, which is independent of the depth.
It follows from this that as the depth increases, the parameter space's local geometry linearly depends on the depth and the first-order optimization also suffers from it.
Now, our approach for the spectral analysis of DNNs consists of three steps.
In the first step, we consider the dual of the conditional FIM in order to focus on the non-trivial non-zero eigenvalues.
In the second step, the dual's eigenvalue distribution is decomposed to a free multiplicative convolution of two distributions. Subsequently, we introduce the recursive equations \eqref{align:reccurence_spec} of the dual's spectral distribution throughout the layers.
In the last step, the induction on depth shows simultaneously that the maximal value of the limit spectrum of the dual is an atom with a large weight, and we get the recursive equation of the maximum \eqref{align:recursive_max}.
We emphasize that in our setting, the atom helps us simplify the analysis of the maximum.
n
Secondly,  we discover a solvable case on the spectrum distribution of the dual conditional FIM of a non-trivial DNN.
In more detail, we explicitly show the asymptotic spectrum of the dual conditional FIM of a two-hidden-layer (a total of three layers) DNN (\cref{thm:two-hidden-layer}).
As long as we know, this is the first solvable case ever for the FIM's spectrum of the deep architecture and clarifies the connection to the universal law of random matrices in FPT.

Thirdly, we empirically confirm in \cref{sssec:expected_vs_conditional}  that the spectrum of the FIM at a small number of samples has the same property as the single-sample version.
\cref{sec:block-diagonal} describes the rationale for a part of the experiment.

Lastly, in \cref{ssec:dynamics}, experimental results confirm that the FIM's dependence on depth determines the appropriate magnitude of the learning rate for the convergence of the first-order optimization at the initial phase of the online training of DNNs.

Our analysis is the first step towards a theoretical understanding of the FIM of DNN achieving dynamical isometry.
By extending our framework, we expect to see the spectrum of other FIMs in more varied settings.

\subsection{Related Works}
\paragraph{Dynamical Isometry and Edge of Chaos}
\com{ A DNN is said to be on the edge of chaos if it preserves the norm of the gradient and the mean squared singular value of the Jacobian throughout layers.
However, vanishing or exploding of gradients in specific directions still occurs in the worst case.
To prevent them, we need both orthogonal initialization and weight scale depending on activation functions, and that is the finding of the theory of dynamical isometry \citep{Pennington2017Resurrecting,Pennington2018emergence}.}
The theory of dynamical isometry has been extended to various architectures \citep{burkholz2019initialization, gilboa2019dynamical,tarnowski2019dynamical},  and experiments on CNN showed that the dynamical isometry reduced the training error of 10,000 layers of models \citep{xiao2018dynamical}.
In contrast, even if the backpropagation signal is isotropic, our study shows that the parameter space's curvature essentially depends on the number of layers. In particular, our study shows that many eigenvalues concentrate on the number of the point of the depth.
For example, it suggests that the learning rate, which has been implicitly set, needs to be set to a smaller and more appropriate value depending on the number of layers.

\paragraph{Fisher Information Matrix of DNN}
Several works have provided the spectral analysis of FIM in limited cases. \citep{Pennington2018spectrum} has analyzed the spectrum of FIM via random matrix theory but limited to shallow networks and random Gaussian weight matrices.
\citep{Karakida2019normalization, Karakida2019universal} obtained some bounds for the FIM's eigenvalues in DNNs, but their bounds are loose in general and also limited to Gaussian weights.
\cite{Saxe2014exact} treats the loss's Hessian eigenvalues, but the work is restricted to a linear activation.
On the contrary, we investigate the FIM spectrum of deep non-linear networks on random orthogonal weights, which satisfy the dynamical isometry.

\paragraph{Neural Tangent Kernel}
Additionally, let us remark that \citep{Jacot2018NeuralNetworks} uses a version of the dual FIM $\Theta$ with Gaussian initialization as the kernel matrix and call it the neural tangent kernel (NTK). The FIM's eigenvalues also determine convergence characteristics of gradient descent in wide neural networks through the NTK.
\com{
Settings of the last layer of DNNs are different between the theory of NTK and the theory of dynamical isometry.
In the theory of NTK,
 the dimension of the final layer of the DNN is set to be lower-order than that of hidden layers. However, in the theory of dynamical isometry, the final layer's dimension is set to be of the same order as the hidden layers.
}

\com{ \cite{huang2020neural} treats the NTK regime of orthogonal initialization but does not analyze the case of dynamical isometry.}


TITLE: How can I get from one factored form to another?
QUESTION [3 upvotes]: This came from trying to factor $x^6 + 1$. We know that
$x^4 - x^2 + 1 =  (x^4 +2 x^2 + 1) -3x^2 = (x^2+1)^2 - 3x^2 = (x^2 - \sqrt 3 x + 1)(x^2 + \sqrt 3 x + 1)$
I expected that if I factored the $x^4 - x^2 + 1$ completely into $4$ factors and then regrouped them $2$ by $2$, I could arrive at $(x^2 - \sqrt 3 x + 1)(x^2 + \sqrt 3 x + 1)$
$$\left(x+ \sqrt {\dfrac {1 + \sqrt 3 i}{2}}\right) \left(x+ \sqrt {\dfrac {1 - \sqrt 3 i}{2}}\right) \left(x- \sqrt {\dfrac {1 + \sqrt 3 i}{2}}\right) \left(x- \sqrt {\dfrac {1 - \sqrt 3 i}{2}}\right)$$
But that didn't happen. No matter how I group them into quadratics, I always end up with a complex coefficient. How can I get $(x^2 - \sqrt 3 x + 1)(x^2 + \sqrt 3 x + 1)$ from the $4$ factors?

REPLY [1 votes]: $$\left(\frac{\sqrt{3}\pm i}{2}\right)^2 = \frac{3-1\pm 2\sqrt{3}i}{4} = \frac{1\pm\sqrt{3}i}{2} \implies \underbrace{\sqrt{\frac{1\pm \sqrt{3}i}{2}} = \frac{\sqrt{3}\pm i}{2}}_{\text{assume taking principal branch of } \sqrt{\;}}
\\
{\Huge\Downarrow}
\\
\left(x \pm \sqrt{\frac{1 + \sqrt{3}i}{2}}\right)
\left(x \pm \sqrt{\frac{1 - \sqrt{3}i}{2}}\right)\\
\| \\
x^2 \pm \left(\frac{\sqrt{3} + i}{2} + \frac{\sqrt{3} - i}{2}\right) +
\left(\frac{\sqrt{3} + i}{2}\right)\left(\frac{\sqrt{3} - i}{2}\right)\\
\| \\
x^2 \pm \sqrt{3}x + 1
$$


TITLE: Moduli spaces according to Weil's algebraic geometry
QUESTION [3 upvotes]: There's the following footnote on the first page of Deligne-Mumford:

The idea of enlarging the category of varieties for the study of
  moduli spaces is due originally, we believe, to A. Weil.

So, what could supposedly have been the definition of a moduli space according to older-style algebraic geometry? This is in contrast to the modern definition of a fine moduli space being a representable functor, and the similar but slightly more involved definition for coarse moduli space.

REPLY [9 votes]: Deligne and Mumford are referring to Weil's original construction of the Jacobian of a curve (which is the moduli space of degree zero invertible sheaves, or (equivalently) of degree zero divisors up to linear equivalence).  Weil's construction proceeded by first building an open subset of the Jacobian (by applying Riemann--Roch to generically chosen divisors), and then using the group law to move this open set around to cover the whole Jacobian.  The Jacobian itself was then obtained by gluing together these open subsets.
Because the construction was via gluing, Weil didn't know whether or not the Jacobian was a projective variety (although he knew it was complete), and so he enlarged the category of varieties from (quasi-)projective varieties to varieties that were simply required to be locally affine.
(Of course, it was understood in fairly short time that Riemann's theory of line bundles on Jacobians and projective embeddings could be extended from the complex case to the general case, and hence that Jacobians are indeed projective varieties.)

As for your more general question, a "moduli space" simply means a space in algebraic geometry parameterizing a certain collection of objects up to some appropriately chosen equivalence.  The precise categorical definition you are thinking of is due to Grothendieck, but obviously the general idea doesn't need to be formulated categorically.  Martin Brandenburg's answer gives one easy example.  And it the whole point of the Jacobian of a curve (which goes back to Abel, Jacobi, and Riemann) is that its points are in a natural bijection with degree zero divisors mod linear equivalence.


TITLE: groups with prescribed conjugacy class sizes
QUESTION [0 upvotes]: Given a list of conjugacy class sizes, $1=n_1\leq n_2\leq...\leq n_k$, does there exist a group with exactly $k$ conjugacy classes with sizes $n_k$?  The same question for an infinite list, specifically, $n_k=k$.

REPLY [0 votes]: Note that one restriction is that the size of a conjugacy class must divide the order of the group. But even with that restriction...let's look at an example. The number of ways to get $8$ by adding $1$s, $2$s, $4$s, and $8$s is $10$ (8; 44; 422; 4211; 41111; 2222; 22211; 221111; 2111111; 11111111), while the number of groups of order $8$ is only $5$ (and three of those groups are abelian, so they fall into the 11111111 category). There just aren't enough groups to go around.


TITLE: I'm having trouble evaluating this contour integral.
QUESTION [0 upvotes]: I'm having trouble evaluating this contour integral.
More specifically evaluating the residue at z=0.
Thank you in advance!
$$ \oint_{|z|=3} \frac{1}{2-z} e^{\frac{1}{z}} \,dz $$

REPLY [2 votes]: Notice that since $|z|=3,$ you will have that $$\frac1{2-z}e^{\frac1{z}}=\frac1{\frac2{z}-1}\frac{e^{\frac1{z}}}{z}=-\frac1{1-\frac2{z}}\frac{e^{\frac1{z}}}{z}=-\frac{e^{\frac1{z}}}{z}\sum_{m=0}^{\infty}\frac{2^m}{z^m}=-e^{\frac1{z}}\sum_{m=0}^{\infty}\frac{2^m}{z^{m+1}}=-\sum_{m=0}^{\infty}2^m\frac{e^{\frac1{z}}}{z^{m+1}}=-\sum_{m=0}^{\infty}2^m\frac1{z^{m+1}}\sum_{n=0}^{\infty}\frac1{n!z^n}=-\sum_{m=0}^{\infty}\sum_{n=0}^{\infty}\frac{2^m}{n!}\frac1{z^{m+n+1}}.$$ Since $m+n+1=0$ if and only if $m=0$ and $n=0,$ we have that $$-\sum_{m=0}^{\infty}\sum_{n=0}^{\infty}\frac{2^m}{n!}\frac1{z^{m+n+1}}=-\sum_{n=0}^{\infty}\frac1{n!}\frac1{z^{n+1}}-\sum_{m=1}^{\infty}\sum_{n=0}^{\infty}\frac{2^m}{n!}\frac1{z^{m+n+1}}=-\frac1{z}-\sum_{n=1}^{\infty}\frac1{n!}\frac1{z^{n+1}}-\sum_{m=1}^{\infty}\sum_{n=0}^{\infty}\frac{2^m}{n!}\frac1{z^{m+n+1}}.$$ Therefore, the residue of the integrand is $-1.$


text:
\section{Faces Induced by Intersections of Halfspaces: Proof of \propref{faces_teach}}\label{appendix: faces teaching}
In this section, we provide the proof of \propref{faces_teach} for the number of faces induced by the hyperplane arrangement $\cA(\Hnd)$.
\newline
\begin{proof}[Proof of \propref{faces_teach}]
To count the number of faces induced by the arrangement $\cA\parenb{\Hnd}$ on the hyperplanes, one way it can be ascertained is by counting the number of regions/faces induced on any hyperplane. If we fix any hyperplane $h^* \in \Hnd$ and look at the intersections of $h^*$ with $\Hnd\setminus \{h^*\}$, we can count the number of regions formed on $h^*$.

If $d' = 1$, then $\ff\parenb{\cA(\Hnd)} = n$ since all the hyperplanes are parallel to each other. Thus, we  assume that $d' > 1$ for further discussion.

Since $h^*$ can be interpreted as a \tt{flat}, we can write $h^* \equiv v^* + W^*$ for some vector $v^* \in \mathbb{R}^d$ and ($d-1$)-dimensional subspace $W^*$ of $\Rd$. By \defref{defn relaxed general position}, $\parenb{h^* \cap h}$ is a ($d-2$)-dimensional flat $\forall h \in \Hnd\setminus\{h^*\}$. Thus, we define by $\boldsymbol{\mathcal{H}'}_{n-1,d-1}  \triangleq  \condcurlybracket{\parenb{h^*\cap \ell}}{\ell \in \Hnd\setminus \{h^*\}}$ the induced set of $n-1$ flats (intersections) on $h^*$ (which is a $(d-1)$-dimensional flat). We note that for any $1 \le k \le d'-1$, if $\mathrm{T}_k \subset \boldsymbol{\mathcal{H}'}_{n-1,d-1}$ then
\[\dim\paren{\bigcap_{\ell \in \mathrm{T}_k}\ell} = (d-1)-k \]
It holds because if $\dim\bigparen{\bigcap_{\ell \in \mathrm{T}_k}\ell} \neq (d-1)-k$ then $\dim\bigparen{\bigparen{\bigcap_{\ell \in \mathrm{T}_k}\ell} \bigcap h^*} \neq d-(k+1)$ since $\bigparen{\bigcap_{\ell \in \mathrm{T}_k}\ell} \subset h^*$. This violates $d'$-relaxed general position arrangement of $\Hnd$. Thus, $\boldsymbol{\mathcal{H}'}_{n-1,d-1}$ is in $(d'-1)$-relaxed general position arrangement. Since counting the number of regions induced on $h^*$ by $\boldsymbol{\mathcal{H}'}_{n-1,d-1}$ is the same as ascertaining $\fr\parenb{\cA(\Hndo)}$ \tt{i.e.} $(n-1)$ hyperplanes in $\mathbb{R}^{d-1}$ in $(d'-1)$-relaxed general position, using \thmref{thm:d'-general} we get:
\[\fr\parenb{\cA(\boldsymbol{\mathcal{H}'}_{n-1,d-1})} = \fr\parenb{\cA(\Hndo)} = \sum_{i=0}^{d'-1} \binom{n-1}{i} \]
Since, there are $n$ hyperplanes thus the proposition follows,
\[\ff\parenb{\cA(\Hnd)}  = n\cdot \sum_{i=0}^{d'-1}\binom{n-1}{i}\]
which completes the proof.
\end{proof}

\clearpage


TITLE: How high above sea level do your eyes have to be to see a point that is 4.1 miles away "as the crow flies"?
QUESTION [1 upvotes]: There's a fireworks show going on tonight at a little town that's 4.1 miles away from my house, and I want to watch it from a hill near my house. So I thought I'd set up a simple geometry problem to figure out how high up my eyes need to be, assuming no obstacles & negligible atmospheric reflection. The town in question is 7 ft above sea level, so we don't need to worry about its elevation.
Here are my formulae:
$$\theta = \arccos{ \dfrac{r}{r+h} }$$
$$\text{Distance} = \theta \times 2\pi \times r$$
where h = height above sea level and
r = radius of Earth
After I plugged in an r of $3967.5467$ miles, I deduced that h should be approximately 3.409 inches. However, I think I made a mistake, because even without obstacles, the h I got seems too small.

REPLY [3 votes]: Let $F$ be the location of the fireworks, $O$ the centre of the Earth, and $H$ the top of the hill. For all practical purposes $HT=4.1$. If $h$ is the required height, then by the Pythagorean Theorem we have $(HT)^2 +(OF)^2=(OT)^2$, and therefore $(r+h)^2=(4.1)^2+r^2=(r+h)^2$.
Expand. We get $r^2+2rh+h^2=r^2+(4.1)^2$. The number $h^2$ is negligibly small compared to $2rh$, so we want $2rh\approx (4.1)^2$.
Remark: In principle, you don't need much of a hill! However, unless the town is across the bay from you, there is the practical problem of obstructions, such as trees. Avoiding visual obstructions is here  the main practical reason for seeking to be reasonably high up.
Let us change the problem a little. There are two ships at sea, at distance $d$ miles from each other. The top $T_1$ of the mast of Ship 1 is $h_1$ miles above sea level. What should be the height $h_2$ of the top $T_2$ of the mast of Ship 2  so that $T_1$ is (barely) visible from $T_2$?
The line $T_1T_2$ is now tangent to the Earth. A calculation much like the one above shows that $2r(h_1+h_2)\approx d^2$.


TITLE: Are galaxies moving away from each other at a constant speed?
QUESTION [1 upvotes]: Im trying to understand what Hubble's law
$$v = H_0  d$$
means. The thing is I keep getting two different explanations.

Galaxies are moving at a constant speed, the ones further away are so because they move faster.
Galaxies move faster away the further they are from each other, because there is more matter between them that expands.

Which of these two is correct?

REPLY [1 votes]: I find it helpful to separate the observations from the model and interpretation.  The observation was that there was a curious linear trend between distance from Earth and velocity.  This was simply an observation made on galaxies that we could see.  Such a trend would not be expected in random data.  Indeed, it would suggest that we might actually be the center of the universe, as everyone expands out from us.
Of course, that is not the popular interpretation.  We don't like to assume we are that special.  Instead, it was identified that modern relativistic theories permitted space to expand.  If space itself was expanding, then a linear relationship like we see from Earth would be seen from everywhere.  This is the preferred interpretation: $v=H_0d$ is seen as evidence that space itself is expanding (and taking matter along for a ride).