TITLE: Problem involving conditional probability
QUESTION [1 upvotes]: I am working on a problem that reads as follows:
A new test has been developed to determine whether a given student is
overstressed. This test is 95% accurate if the student is not overstressed, but only 85%
accurate if the student is in fact overstressed.  It is known that 99.5% of all students
are overstressed. Given that a particular student tests negative for stress, what is the
probability that the test results are correct, and that this student is not overstressed?
I understand that the answer I'm looking for is of the form $$P((A \cap S^c)|\text{tested negative for stress}),$$ where $A$ is the event that the test is accurate and $S$ is the event that the student is overstressed.
Furthermore, the remaining probabilities from the question are (I believe) $P(A|S)=0.85$ and $P(A|S^c)=0.95$. Assuming that these are correct, how would I use them to express the second half of the conditional probability above  (tested negative for stress)?
My first thought was that the test could be either accurate or inaccurate, which led me to $P((A\cap S^c)\cup(A^c\cap S))$.

REPLY [1 votes]: Take a look at Bayes' theorem.
Denote $N$ as an event of negative test for student.
So, we are given that the event $N$ occured. We want to find $P(A\vert N)$.
We have
$$P(S^c\vert N) = \dfrac{P(N\vert S^c)P(S^c)}{p(N)}$$
For $P(N)$ we have
$$P(N) = P(N\vert S)P(S)+P(N\vert S^c)P(S^c).$$
And this quantity is computable from your statement.
$$P(S^c\vert N) = \dfrac{P(N\vert S^c)P(S^c)}{P(N\vert S)P(S)+P(N\vert S^c)P(S^c)}$$


TITLE: On $17^7+76271^3=d^2$ and coprime solutions to $x^6+y^3=z^2$?
QUESTION [7 upvotes]: This post got me curious. The Diophantine equation with $x\neq1$,
$$x^n+y^3 = z^2\tag1$$
has infinitely many coprime solutions when $n\leq5$. Are there at least a few co-prime ones when $n>5$?

$n=6:$ $\color{red}{??}$

No solutions with $x<100$ and $0<y<100000$. (I checked.)

$n=7:$

$$2^7+17^3=71^2$$
$$17^7+76271^3=21063928^2$$

$n=8:$

$$43^8+96222^3 = 30042907^2$$

Q: Does $n=6$ in fact have a coprime solution? (It seems strange that $n=7,8$ has but $n=6$ doesn't. A larger search radius might yield a result.)

P.S.: From work by Darmon and Granville, if $1/p+1/q+1/r<1$, then the equation $ax^p+by^q+cz^r=0$ has only finitely many coprime solutions. So $(1)$ has only finitely many for $n\geq7$.

REPLY [4 votes]: Proposition 14.6.1. In the parabolic case $1/p + 1/q + 1/r = 1$, the equation $x^p + y^q = z^r$ has no solutions in nonzero coprime integers, except that the equation $x^3 + y^6 = z^2$ has the solutions $(x, y, z) = (2, ±1, ±3)$, and the equation $x^3 + y^2 = z^6$ has the solutions $(x, y, z) = (−2, ±3, ±1)$.
From Henri Cohen Number Theory Volume II: Analytic and Modern Tools


TITLE: Intersection of a normal subgroup with the centre of a $p$-group
QUESTION [0 upvotes]: For homework, I'm asked to show that a normal subgroup of a $p$-group intersects the centre of the $p$-group nontrivially (Herstein section 2.12 P. 15).
This question is answered here, but to prove it, I actually proved a stronger claim; that $N \cap Z(P) = Z(N)$. I'd like to know if this is right, and if so, if my proof is correct.
First, I show that if a subgroup of an arbitrary group is normal, then it's a union of conjugacy classes, i.e.
$$N = \left(\bigcup_{a \in N} C(a)\right) = Z(N) \sqcup \left(\bigcup_{a \in N\setminus Z(N)} C(a)\right).$$
Choosing representatives $a_1,\dots,a_r$ for each non-central conjugacy class, the class decomposition for $N$ reads
$$N = Z(N) \sqcup \left(\bigsqcup_{i=1}^r  C(a_i)\right).$$
Now let $P$ be a group of order $p^n$ for some $n > 0$, and let $N \trianglelefteq P$. As $P$ is a $p$-group, its centre $Z(P)$ is nontrivial.
Further, as $N \trianglelefteq P$, we write $N = \bigcup_{a\in N} C(a)$; choosing representatives $a_1,\dots,a_r$ for each conjugacy class that is not in the centre of $N$, we have that $$N = Z(N) \sqcup
\left(\bigsqcup_{i=1}^r C(a_i)\right).$$
Writing $P$ as a union of nontrivial disjoint conjugacy classes, together with $Z(P)$, we have that
$$P = Z(P) \sqcup\left(\bigsqcup_{j=1}^s C(b_j)\right),$$
where $b_1,\cdots,b_s$ are representatives of distinct non-central conjugacy classes of $P$.
\ind
For each noncentral conjugacy class $C(a_i) \subset N$, we have that $C(a_i) \in P \setminus Z(P)$, since $P\setminus Z(P)$ is the complete collection of non-central conjugacy classes; since $Z(N) = \bigsqcup_{z \in Z(N)} C(z)$ which is the collection of central (singleton) conjugacy classes in $N$, and since $Z(P)$ is the complete collection of all central conjugacy classes of $P$, it follows that $Z(N)$ must be contained in $Z(P)$. As $Z(N)$ is non-trivial (since $N$ is a $p$-group), we have that
\begin{align*}
Z(P) \cap N &= Z(P) \cap \left(Z(N) \sqcup \left(\bigsqcup_{i=1}^r C(a_i)\right)\right) \\
&= Z(P) \cap Z(N) \cup \left(Z(P) \cap \left(\bigsqcup_{i=1}^r C(a_i)\right)\right) \\
&= Z(N) \cup \varnothing = Z(N).
\end{align*}
Is this reasoning sound?

REPLY [1 votes]: Your claim is false by counterexample; say, the normal subgroup $ C_4 $ of $ D_4 $ is abelian, but the center of $ D_4 $ is isomorphic to $ C_2 $. In your proof, I don't understand how you conclude from $ N - Z(N) \subset P - Z(P) $ that $ Z(N) \subset Z(P) $.


TITLE: Derivation of KVL for AC circuits
QUESTION [0 upvotes]: AC circuits have periodically changing current, due to which there will be a change in the magnetic flux as a consequence of which an electric field will be produced and hence an emf; my question is, whether this induced emf will invalidate the application of KVL for the loop or not? If not then any mathematical proof?

REPLY [1 votes]: KVL is valid for lumped circuits only.
One of the conditions that makes a circuit "lumped" is that the magnetic flux through the loops formed by the circuit wiring is negligible.
This is, of course, only an approximation, and in any real circuit KVL is not strictly correct. The approximation becomes less accurate as the physical extent of the circuit gets larger.
When the circuit size becomes comparable to the wavelength of the signals involved (say $l \gt 0.1 \lambda$) we can't really use the lumped circuit approximation any more and we have to start analyzing wires as transmission lines rather than ideal wires.


TITLE: group actions (left, conjugation, etc...)
QUESTION [0 upvotes]: We mentioned in class three important group actions of any group G. Show carefully that each are indeed group actions.
a- Left group action $G \circlearrowright G$ where $g \cdot h = gh$ for all $g, h \in G$.
b- Conjugation action $G \circlearrowright G$ where $g \cdot h = ghg^{-1}$ for all $g,h \in G$.
c- For a subgroup $H \leq G$, the left action of $G$ on $G/H$ where $g \cdot aH = (ga)H$.
----definition----
If we have a group G ($g,h \in G$), a set X ($x \in X$), we can show that $\alpha$ is an action if
$\alpha:G \times X \to X$
i. $e\cdot x$
ii. $g\cdot (h \cdot x)=(gh)\cdot x$
----My attempt----
a-i. wts $e\cdot x=x$, but that sounds obvious. How would this ever not happen?
a-ii. wts $g\cdot (h \cdot x)=(gh)\cdot x$, but $g\cdot h= gh$ is given. What on earth am I supposed to show?
b-i. wts $e \cdot x = x$, but $e\cdot x=exe^{-1}$, so we are done.
b-ii. wts $g\cdot (h \cdot x)=(gh)\cdot x$, but $g\cdot(h\cdot x)=g\cdot(hxh^{-1})=ghxh^{-1}g^{-1}=(gh)x(gh)^{-1}=(gh)\cdot x$, so we are done.
c-i. wts $e\cdot x=x$, so $(ex)\cdot H=x\cdot H$? Is there not more to this?
c-ii. wts $g\cdot (h \cdot H)=(gh)\cdot H$? Isn't it just $g\cdot (h \cdot H)=g\cdot (hH)=ghH=gh\cdot H$?
I feel like I have to be missing something absolutely critical.

REPLY [1 votes]: a i) It sounds obvious, because it is. You have $e\cdot x=ex=x$.
a ii) You have $g\cdot(h\cdot x)=g\cdot(hx)=g(hx)=(gh)x=(gh)\cdot x$.
b i) You need to finish it by stating $exe^{-1}=x$
b ii) You have an error. The middle equality should read $ghxh^{-1}g^{-1}$.
c i) You want to show $e\cdot xH = xH$. This is straightforward: $e\cdot xH = (ex)H = xH$.
c ii) You want to show $g\cdot(h\cdot xH) = (gh)\cdot xH$ (remember, the $g$ and $h$ are in the group and $xH$ is in the set). We have
$$g\cdot(h\cdot xH)=g\cdot(hx)H=(ghx)H=(gh)xH = (gh)\cdot xH$$

REPLY [0 votes]: a-i: As you mentioned, $e*x=ex=x$ is obvious (indeed, by group axiom called identity).
a-ii: This also follows from the group axiom, associativity. We have $g*(h*x)=g*hx=g(hx)=(gh)x=(gh)*x$.
b-i and b-ii: You are correct.
c-i: What you want to show is $e*x=x$ for all $x\in X$, which means $e*gH=gH$ for all $gH\in G/H$. By identity axiom, we get $e*gH=egH=gH$.
c-ii: Again, what you want to show is $g*(h*aH)=(gh)*aH$ for all $aH\in G/H$. This holds by associativity axiom, $g*(h*aH)=g*haH=g(ha)H=(gh)aH=(gh)*aH$.


TITLE: p norm of matrix
QUESTION [2 upvotes]: I have a matrix $A \in C^{n\times n}$ with $||A||_p ≤ 1/2$  in some p-norm. I am wondering how to show that $$||(I+A)^{-1}-I||_p ≤2||A||_p $$
Thanks, in advance.

REPLY [1 votes]: $$\quad{||AB||_p\leq ||A||_p||B||_p\to ||A^2||_p\leq||A||_p^2\\||A||_p ≤ 1/2\to ||A^2||_p\leq\frac{1}{2^2}\\||A^n||_p\leq ||A||_p^n\leq \frac{1}{2^n}}$$now put $$\quad{(I+A)^{-1}=I-A+A^2-A^3+A^4-...\because\\(I+A)^{-1}(I-A+A^2-A^3+A^4+...+(-1)^nA^n)=I+(-1)^{n+1}A^n\\when \space n\to \infty \implies A^n\to0}$$so
$$\quad{||(I+A)^{-1}-I||_p=\\||I-A+A^2-A^3+A^4-...-I||_p=\\||-A+A^2-A^3+A^4-...||_p\\=||-A(I-A+A^2-A^3+A^4-...)||_p\\\leq ||A||_p||I-A+A^2-A^3+A^4-...||_p\\||A||_p(||I||_p+||A||_p+||A^2||_p+||A^3||_p+... ) \\
||A||_p(1+\frac 12+\frac 14+\frac 18+...)\\\leq ||A||_p\times 2
 }$$


TITLE: $x$ generator of $(\mathbb{Z}/p^2\mathbb{Z})^* \implies$ $x$ generator of $(\mathbb{Z}/p^n\mathbb{Z})^*$
QUESTION [0 upvotes]: As it's indicated in the title, I have to show that

$x$ generator of $(\mathbb{Z}/p^2\mathbb{Z})^* \implies$ $x$ generator of  $(\mathbb{Z}/p^n\mathbb{Z})^*$, $p \neq 2$.

I'm not sure of my proof, it's why I post it here and I hope you will be able to enlighten me if it's okay or not ! :)
My proof :
We know that ($\mathbb{Z}/p^n\mathbb{Z})^*$ is cyclic. Let's $\overline{q}$ be a generator of $(\mathbb{Z}/p^n\mathbb{Z})^*$. So  $\overline{x} = \overline{q}^m$, $m \in \mathbb{Z}$. But $\overline{q}$ is as well generating ($\mathbb{Z}/p^2\mathbb{Z})^*$, and we have : $x = q^m + kp^n$, $k \in \mathbb{Z}$. So, as $n \geq 2$, we have : $x = q'^m [p^2]$ ($\overline{x} = \overline{q}^m$, but this time mod $p^2$).
On the other side, we know that $\mathrm{ord}(\overline{x}) = p(p-1)$ over $(\mathbb{Z}/p^2\mathbb{Z})^*$ and $\overline{q}$ is generating $(\mathbb{Z}/p^2\mathbb{Z})^*$, so we should have $\gcd(m,p(p-1))=1$ (otherwise $x$ is not a generator over $(\mathbb{Z}/p^2\mathbb{Z})^*$).
From here, as $\gcd(p,p-1)=1$, we have $\gcd(m,p)=1, \gcd(m,p-1)=1$, and then $\gcd(m,p^n(p-1))=1$. So, $\mathrm{ord}(\overline{x}) = \mathrm{ord}(\overline{q}) = p^n(p-1)$ over $(\mathbb{Z}/p^n\mathbb{Z})^*$, and we have the result.
Is it right or not ? :)
Thank you very much !

REPLY [2 votes]: The proof looks reasonable, but you should clean up and clarify a few things: what is $q'$ in your first paragraph?  Why exactly does $\gcd(m, p(p-1))\neq 1$ imply that $x$ is not a generatator of $(\mathbb{Z}/p^2\mathbb{Z})^\ast$?
Also, I believe in the last paragraph you use $n$ when you mean $n-1$.


TITLE: Effect of tensor product on euler characteristic of line bundles
QUESTION [1 upvotes]: Suppose X is a curve.
Under sufficiently nice conditions we have that every line bundle on X corresponds to an equivalence class of divisors modulo principal divisors, with tensor product of bundles corresponding to addition of divisors.
Given a line bundle L on X, I will call the Euler Characteristic of L minus the Euler characteristic of the trivial line bundle the cohomological degree of L.
By the first half of the Riemann Roch theorem, we have that this is equal to the degree of the equivalence class of divisors corresponding to L. Thus cohomological degree is a homomorphism from the Picard group of X to Z.
Is there a more direct proof of the fact that cohomological degree is a homomorphism, that does not go through divisors and the Riemann-Roch theorem? Hopefully this is just a matter of homological algebra.
Is there a similar, cohomological definition of degree that works in higher dimensions?
Thank you.

REPLY [1 votes]: I am not really sure I have understood your question. First of all I guess you suppose your curve $C$ is smooth, compact, connected and over the field of complex numbers, right?
In this case, consider the exponential short exact sequence
$$
0\to \mathbb Z\to\mathcal O_C\to\mathcal O_C^*\to 0.
$$
A piece of derived long exact sequence in cohomology is thus
$$
\operatorname{Pic}(C)\simeq H^1(C,\mathcal O_C^*)\overset{c_1}\to H^2(C,\mathbb Z)\simeq\mathbb Z.
$$
Now, $H^1(C,\mathcal O_C^*)$ is the group of isomorphism classes of line bundles over $C$, that is the Picard group of $C$, and $c_1$ is the connection homomorphism which assigns to an isomorphism class of line bundles its first Chern class in $H^2(C,\mathbb Z)$.
Since the curve is (smooth) compact and connected, the latter group is canonically isomorphic to $\mathbb Z$ (the isomorphism been given by integrating over $C$) and under this identification $c_1(\bullet)$ is nothing else than the degree homomorphism.
Hope this will answer to your question.


TITLE: Branch cut question
QUESTION [6 upvotes]: I have a function $$f(z)=(z-1)^{3/5}(z+1)^{2/5}$$
and I have the branch of this function chosen such that $$-\pi<\arg(z\pm1)\leq\pi$$
How do I show that a branch cut is not required on the section $(-\infty,1)$ of the real axis?
I have defined $(z-1)=r_1e^{i\theta_1}$ and $(z+1)=r_2e^{i\theta_2}$ and thus can get $f(z)$ into the form $$r_1^{3/5}r_2^{2/5}e^{i/5(3\theta_1+2\theta_2)}$$
Now here is where I get confused but I think I need to find $f(x\pm0i)$on the section $(\infty,1)$ of the real axis and determine continuity but I don't know how to do this for this specific example and would appreciate some help. Thank you.

REPLY [5 votes]: You only need to choose a branch cut so that all of the branch points lie on the cut.  Remember that a branch point is a point where the function is discontinuous when traversing an arbitrarily small circuit about the point.  By choosing a branch cut like this you're essentially acknowledging this behavior and choosing specifically where this discontinuity will occur.
The points $z = \pm 1$ are clearly branch points, and they are the only finite branch points.  The point at infinity may also be a branch point.  In this case it isn't (shown below), but if it were then you would need to choose your cut so that it contains all three branch points ($1$, $-1$, and $\infty$).  You could do this by choosing it to be the real interval $(-\infty,1]$, but there are infinitely many other choices you could make too.
To see that the point at infinity is not a branch point, rewrite the function as
$$
f(z) = z\,\left(\frac{1}{z}-1\right)^{3/5}\left(\frac{1}{z}+1\right)^{2/5}.
$$
Let $|z| > 1$.  By doing this, we can ensure that neither of the two quantities $a = \frac{1}{z}-1$ or $b = \frac{1}{z}+1$ will make a circuit about the origin, regardless of what $z$ is doing.  They are both restricted to unit disks centered at $-1$ and $1$, respectively.  Indeed, $|a+1|<1$ and $|b-1|<1$.
Now, with this condition on $|z|$, if $z$ makes a circuit about the origin (equivalently, a circuit about infinity), the change in the argument of $f$ is precisely $2\pi$, and the function remains unchanged.  We have thus continuously traversed an arbitrarily small circuit about infinity, and hence infinity is not a branch point of $f$.
As a result, we only need to choose a branch cut which includes $1$ and $-1$.  The real inverval $[-1,1]$ is the simplest choice.

REPLY [1 votes]: One only needs a branch cut between $-1$ and $1$. We can define
$$
\log\left(\frac{w-1}{w+1}\right)=\frac{\pi i}{2}+\int_i^w\left(\frac1{z-1}-\frac1{z+1}\right)\,\mathrm{d}z
$$
where the path from $i$ to $w$ does not cross the line segment from $-1$ to $1$. This forces the difference of any two paths from $i$ to $w$ to circle both singularities the same number of times. Since their residues are $1$ and $-1$, the total residue would be $0$ and so the function computed using either path would be the same.
Therefore, we can define
$$
(z-1)^{3/5}(z+1)^{2/5}=\left(\frac{z-1}{z+1}\right)^{3/5}(z+1)
$$
using the same branch cut.


TITLE: When does the greedy change-making algorithm work?
QUESTION [4 upvotes]: The change-making problem asks how to make a certain sum of money using the fewest coins. With US coins {1, 5, 10, 25}, the greedy algorithm of selecting the largest coin at each step also uses the fewest coins.
With which currencies (sets of integers including 1) does the 'greedy' algorithm work?

REPLY [11 votes]: That's a different question, Gerry.
Believe it or not, the answers are different if one is asking
(a) given N and a system of denominations D, is the greedy algorithm using D optimal for N?
and
(b) given a system of denominations D, is the greedy algorithm using D optimal for ALL N?
I think the latter problem is the one that Zachary Vance is asking about.
In that case, it is decidable in polynomial time.  See Pearson's article here:
http://dl.acm.org/citation.cfm?id=2309414 .


TITLE: Is $C^{\infty}_c(R^n) $ dense in $C_0(R^n)$?
QUESTION [2 upvotes]: If $C^{\infty}_c(R^n) $ is dense in $L^p(R^n)$ then is it dense in $C_0(R^n)$?

REPLY [4 votes]: To answer the question if $C_c^\infty(\mathbb R^n)$ is dense in $C_0(\mathbb R^n)$. Yes, it is. Either one uses cut-off functions as in the other answer or one can just use the Stone-Weierstrass Theorem (actually the version for $C_0$-spaces):
So notice that $C_c^\infty(\mathbb R^n)$ is clearly a subalgebra of $C_0(\mathbb R^n)$. Moreover, it can be seen easily by considering bump-functions that $C_c^\infty(\mathbb R^n)$ seperates the points, i.e., for all $x, y \in \mathbb R^n$, $x \neq y$ there is $f \in C_c^\infty(\mathbb R^n)$ such that $f(x) \neq f(y)$. Finally, by considering bump-functions one see that $C_c^\infty(\mathbb R^n)$ vanishes nowhere, which means that for each $x \in \mathbb R^n$ there is $f \in C_c^\infty(\mathbb R^n)$ such that $f(x) \neq 0$.
Hence, the Stone-Weierstrass Theorem yields the density of $C_c^\infty(\mathbb R^n)$. I hope that answers your question.


TITLE: Number of possible Prüfer codes
QUESTION [2 upvotes]: I am trying to solve the following problem in my book: (Code stands for Prüfer code)

Consider labelled trivalent rooted trees $T$ with $2n$ vertices, counting the root labeled $2n$. The labels are chosen in such a way that the procedure leading to $P(T)$ has $1,2,\cdots 2n-1$ as first row. How many possible codes $P(T)$ are there?

As I understand the question, it is asking for the number of ways of labeling the tree such that if we run the Prüfer algorithm, first time the vertex labeled $1$ is removed, second time the vertex labeled $2$ is removed and so on, until the vertex labelled $2n-1$ is removed. Is  my understanding of the question correct?
There are going to be $n+1$ monovalent vertices in such trees, which means there are $n+1$ ways to label a vertex as $1$. But how many ways will be there to label a vertex as $2$? As soon as a vertex has been labeled as $1$, and removed in the first iteration there are either $n$ monovalent vertices remaining or $n+1$ monovalent vertices remaining. So there seem to be two possibilities for labeling $2$: either among $n$ or among $n+1$. How do I decide the number of ways of choosing $2$.
An example of such a rooted trivalent tree is:

Thanks.

REPLY [3 votes]: I'm a bit surprised that this exercise appears so early in a combinatorics book without any hints.
Regarding your first question, yes, I understand the question the same way. What I don't understand is how you originally expected us to help you in interpreting the question without linking to your book or explaining what the "first row" was. I'd suggest to always directly link to any book you're referring to if it's available online, and also not to change the spelling if you quote from a book – I searched for the problem before you provided the link and would have found it if you hadn't changed the spelling of "labeled" to "labelled" :-)
Regarding your second question: What you want to count isn't the ways of labelling the vertices of a given graph; you want to count all such graphs with all labellings for all structures; so I don't think this approach will get you very far.
The problem itself doesn't define what exactly a rooted trivalent tree is. In particular, it's not immediately clear whether the root itself can have degree $1$ or $3$ or only one of the two. Unfortunately Google Books doesn't show (at least to me) the page with Figure 14.3 that the problem refers to, which would probably resolve this. However, this page seems to indicate that the root may be required to have degree $1$, which would fit with how this book seems to be use the term, and also with this solution, which apparently makes that assumption.
The given condition is equivalent to the condition that the vertices are labelled in decreasing order as viewed from the root. Thus we're counting the number of labelled full/proper/strictly binary trees with vertex labels increasing from the root.
The recurrence
$$a_n=\frac12\sum_{k=1}^{n-1}\binom{2n-2}{2k-1}a_na_{n-k}$$
derived in the solution linked to yields the initial terms $1,1,4,34,496,\dotsc$, which lead to OEIS sequence A002105.


TITLE: Does the multiplicative group of GF(81) have a subgroup of order 9?
QUESTION [2 upvotes]: $$|GF(81)^*| = |GF(81)\setminus \{0\}| = 81 - 1 = 80.$$
Since $GF(81)^*$ is cyclic, $|GF(81)^*|=n$ : for any divisor $d$ of $n,$ there's exactly one unique subgroup of $G$ of order $d.$
$9$ is not a divisor of $80,$ therefore, there is no subgroups of order $9.$
Would someone please help me with this and tell me whether my argumentation is correct?
Thank you!

REPLY [0 votes]: You are correct.   Actually you don't even need cyclicity.  You can just note $|\operatorname {GF}(81)^*|=80$ and apply Lagrange.


TITLE: Concentration of the $\ell_2$ error of the empirical distribution
QUESTION [6 upvotes]: Let $X$ be a random variable that takes values only in the set $\{1,2, \dots, m\}$ such that $\Pr(X = i) = p_i$ for all $i = 1,2, \dots, m$. Let $S = \{X_1, X_2, \dots, X_n\}$ be a set of $n$ i.i.d. realisations of $X$. We can then construct the empirical distribution  $\{\hat{p}_i\}_{i = 1}^m$ using the samples from $S$, where $\hat{p}_i = \frac{1}{n} |\{ j : X_j = i\}|$.
I am interested in the concentration inequalities for the random variable $Z := Y - \mathbb{E}[Y]$ where $Y = \| \hat{p} - p \|^2_2$, the square of the $\ell_2$ norm of the difference between the true and the empirical distribution. I have found results in the literature on the concentration of the $\| \hat{p} - p\|_1$, $D(\hat{p} \| p)$ and $\sup_{i} |\hat{p}_i - p_i |$, where $D(p\|q)$ is the KL divergence between $p$ and $q$. However, quite surprisingly, I haven't come across any result on the concentration of the $\ell_2$ norm. While it is possible to directly use the results for other norm for my case, it turns out that the resulting bounds are not tight enough for my case.
Any leads or references will be appreciated. Thanks!

REPLY [6 votes]: Note that if $F_n$ denotes the empirical c.d.f. and $F$ the c.d.f., and $i^{\star} = \text{argmax}_{1 \leq i \leq m} |\hat{p}_i - p_i|$, then

$\|v\|_2 \leq \sqrt{m} \|v\|_{\infty}$ for any vector $v\in \mathbb{R}^m$, see for example here: Equivalence of Two Norm and Infinity Norm.
$\|\hat{p}_n - p\|_{\infty} = |\hat{p}_{i^{\star}} - p_{i^{\star}}| \leq 2 \|F_n - F\|_{\infty}$, since the worst case scenario is that $F_n(x_{i^{\star}}^-)$ was at a distance $\|\hat{p}_n - p\|_{\infty}$ above or below $F(x_{i^{\star}}^-)$ and then after taking the mass at $x_{i^{\star}}$ into account, the roles flipped.
$\mathbb{P}(\|F_n - F\|_{\infty} > t) \leq 2 e^{-2 n t^2}$ for all $t > 0$, by the Dvoretsky, Kiefer and Wolfowitz theorem (see e.g. here: https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality#:~:text=In%20the%20theory%20of%20probability,the%20empirical%20samples%20are%20drawn.)

By these three points (in order), we have, for all $t > 0$,
\begin{align*}
\mathbb{P}\Big(\|\hat{p}_n - p\|_2 > t\Big) \leq \mathbb{P}\Big(\|\hat{p}_n - p\|_{\infty} > \frac{t}{\sqrt{m}}\Big) \leq \mathbb{P}\Big(\|F_n - F\|_{\infty} > \frac{t}{2 \sqrt{m}}\Big) \leq 2 e^{- \frac{n t^2}{2 m}}.
\end{align*}
Furthermore, if you want the concentration about the mean, note that $x\mapsto \sqrt{x}$ is concave, so Jensen's inequality yields
\begin{align*}
\mathbb{E}\Big[\|\hat{p}_n - p\|_2\Big]
&\leq \sqrt{\mathbb{E}\Big[\sum_{i=1}^m |\hat{p}_i - p|^2\Big]} \\
&= \sqrt{\sum_{i=1}^m \frac{1}{n^2} \mathbb{E}\Big[|\sum_{j=1}^n \mathrm{1}_{\{X_j = i\}} - n p_i|^2\Big]} \\
&\leq \sqrt{m \cdot \frac{1}{n^2} \cdot n \max_{1 \leq i \leq m} p_i (1 - p_i)} \quad \text{since } \sum_{j=1}^n \mathrm{1}_{\{X_j = i\}}\sim \text{Binomial}(n, p_i) \\
&\leq \sqrt{\frac{m}{4 n}} \quad \text{since } \max_{x\in [0,1]} x(1-x) = 1/4
\end{align*}
and thus, by the previous concentration bound, we have
\begin{align}
\mathbb{P}\bigg(\Big|\|\hat{p}_n - p\|_2 - \mathbb{E}\Big[\|\hat{p}_n - p\|_2\Big]\Big| > t\bigg)
&\leq \mathbb{P}\Big(\|\hat{p}_n - p\|_2 + \mathbb{E}\Big[\|\hat{p}_n - p\|_2\Big] > t\Big) \\
&\leq \mathbb{P}\Big(\|\hat{p}_n - p\|_2 > t - \sqrt{\frac{m}{4 n}}\Big) \\
&\leq 2 \exp\Bigg(- \frac{n \big(t - \sqrt{\frac{m}{4 n}}\big)^2}{2 m}\Bigg) \\
&\leq 2 \exp\Big(-\frac{n t^2}{2m}\Big) \exp\Big(+ \frac{t}{4} \sqrt{\frac{n}{m}}\Big)
\end{align}
In particular, if $\lim_{n\to \infty} \frac{t}{\sqrt{n/m}} = 0$, then for any given $\epsilon > 0$, we have, for $n$ large enough,
\begin{align}
\mathbb{P}\bigg(\Big|\|\hat{p}_n - p\|_2 - \mathbb{E}\Big[\|\hat{p}_n - p\|_2\Big]\Big| > t\bigg)
&\leq 2 \exp\Big(-\frac{n t^2}{(2 + \epsilon) m}\Big).
\end{align}
This whole reasoning is valid even if $m$ is a function of $n$.


TITLE: How to compute $H_1(S^1, S^0) $
QUESTION [1 upvotes]: As in the title, my problem is to compute the relative homology group $H_1(S^1, S^0) $  of these two spheres.
The problem is that te long exact sequence of the couple gives
$0 \rightarrow \mathbb{Z}\rightarrow H_1(S^1, S^0)\rightarrow\mathbb{Z}^2
\rightarrow \mathbb{Z} \rightarrow 0$
And I think this is not so helpfull.
I know there are tricks using the cellular structure of these two spaces but there is a more basic way to see the result?
Thank you!

REPLY [1 votes]: The exact sequence
$0 \rightarrow \mathbb{Z}\rightarrow H_1(S^1, S^0)\rightarrow\mathbb{Z}^2
\rightarrow \mathbb{Z} \rightarrow 0$
ends in $\mathbb Z$. This is free, so the last projection splits, and you have in fact
$0 \rightarrow \mathbb{Z}\rightarrow H_1(S^1, S^0)\rightarrow\mathbb{Z} \rightarrow 0$
This splits again because $\mathbb Z$ is free, so your group is $\mathbb Z^2$.


TITLE: The probability of rain is 40% on Monday and 30% on Tuesday. (...) What is the probability that it will rain at least one of the two days?
QUESTION [0 upvotes]: My problem:
The probability of rain is 40% on Monday and 30% on Tuesday. Assume the two probabilities are independent. What is the probability that it will rain at least one of the two days?
My solution:
Saying that it will rain at least one of the two days is logically the same as saying that it'll rain on monday (event A) or it'll rain on tuesday (event B). Thus,
$$
P(A \lor B) = P(A) + P(B) = 0.4 + 0.3 = 0.7
$$
But...
The complement of "it will rain at least one of the two days" is that "it will not rain either day", so by the rule of complements,
$$
P(\lnot A \land \lnot B) = P(\lnot A) \cdot P(\lnot B) = 0.6 \cdot 0.7 = 0.42
$$
and so the probability that it will rain at least one of the two days is $1-0.42=0.58$
Where have I gone wrong?

REPLY [4 votes]: The formula that $P(A\vee B)= P(A) + P(B)$ is only true if events $A$ and $B$ are disjoint. In this case, simply adding $P(A)$ and $P(B)$ double counts the case where both $A$ and $B$ occur.
The correct formula in this case would be $P(A\vee B)= P(A) + P(B) - P(A\wedge B)$, which should give you the correct answer. Note that if $A$ and $B$ are indeed disjoint, $P(A\wedge B)$ is $0$ by definition, so we can see that the first formula is just a subcase of the more general formula.
EDIT: I respond to your comment to the other answer, which suggests that it is not completely clear to you what the difference between “independent” and “disjoint” is.
Independence, intuitively, means that the outcome of one event does not affect the outcome of the other. Formally, if A and B are independent, $P(A|B)=P(A)$ and $P(B|A)= P(B)$. Notably, this allows us to conclude the familiar multiplication rule for independent events: if A and B are independent, $P(A\wedge B)= P(A)\cdot P(B)$. To give an example, suppose that tommorow may be sunny or rainy. Also, you might win the lottery next week. These events are independent— the outcome of one will not influence the other.
On the other hand, disjoint events are events which cannot occur at the same time. In other words, if A and B are disjoint, then either A is true or B is true, (or maybe neither!), but it is not possible that both are true. Suppose that you are picking a single marble out of a bag with red and blue marbles. You might pick a red marble or you might pick a blue marble, but you can’t pick a blue marble and a red marble at the same time. Hence the events “pick a red marble” and “pick a blue marble” are disjoint.
Therefore, not only are the two ideas very different, but in fact disjoint events are never independent. This is because, for disjoint events, if A is occurs, then we know that B cannot occur. So the outcome of A can allow us to make a conclusion about the outcome of B.

REPLY [2 votes]: Elaborating on Theo C.'s comment: the correct rule for adding probabilities is $$
P(A \cap B) + P(A \cup B) = P(A) + P(B).
$$ Thus, the probability of $A$ or $B$ happening is only $P(A) + P(B)$ if $A$ and $B$ cannot both happen at the same time. This clearly is not the case in your example.


TITLE: Prove that f is injective. (Is my solution correct?)
QUESTION [1 upvotes]: Let $f: R\to R$, and ($f\circ f\circ f)(x) = (f\circ f)(x) + x$, $x$ $\in \mathbb R.$
  Prove that $f$ is injective.

My Solution:
Let $x_1, x_2\in \mathbb R.$ and $f(f(x_1)) = f(f(x_2)) = y$
($f\circ f\circ f)(x) = (f\circ f)(x) + x$
$f((f\circ f)(x)) = f(f(x)) + x$
$f(f(f(x))) = f(f(x)) + x$
$f(f(x)) = f(f(f(x))) - x$
Since $f(f(x_1)) = f(f(x_2))$
$f(f(f(x_1))) - x_1 = f(f(f(x_2))) - x_2$
$f(y) - x_1 = f(y) - x_2$
$-x_1 = -x_2$
$x_1 = x_2$ therefore $f$ is injective.
Is this solution acceptable?

REPLY [2 votes]: You should prove that $f(x_1) = f(x_2)$ implies $x_1 = x_2$. So your solution is not acceptable. You should start with $f(x_1) = f(x_2)$ then say this implies $f(f(x_1)) = f(f(x_2))$ and then complete as you did

REPLY [0 votes]: It looks on the right path if not a bit long: Suppose that $f(x) = f(y)$.  Then $$f(f(x)) = f(f(y))\quad \text{and} \quad  f(f(f(x))) = f(f(f(y))).$$ Subtract the second equation from the third to get $x=y$.


TITLE: Determining the properties of solutions of a first order linear ODE
QUESTION [1 upvotes]: Which of the following is a general solution of a first order linear ODE
$$y(t)=(\frac{10}{t+C})^{10}$$
$$y(t)=(t+C)e^{sin(t)}$$
$$y(t)=\frac{23Ce^{0.1t}}{23+C(e^{0.1t}-1)}$$
What i tried
I know it cannot be the second equation since if i differentiate it there will be a $sint$ hence it cannot be linear. Between the first and the third equation, I believe it is the first one because if i differentiate th first equation somehow it gives me a linear equation. Im not too sure how to see it though. Could anyone please explain.

REPLY [0 votes]: Since a first order linear ODE, $y+p(t)y=q(t)$, has the general solution $y(t)$ given by $$y(t)e^{\int p(t)dt}=\int q(t)e^{\int p(t)dt}dt$$
It follows $y(t)=(t+C)e^{\sin t}$ is the general solution of $$\frac{dy}{dt}-(\cos t)y=e^{\sin t}$$


TITLE: Pairing algorithm for simple speed dating problem
QUESTION [0 upvotes]: I am asking myself whether there is an polynomial algorithm for the following problem:
Given:
- m persons (think of them as "men")
- w persons (think of them as "women")

- t-talking sessions
- a function
     f: (w, m) -> {-1,0,1,2}, which is preference of a specific woman to talk with a specific man: -1 means, that the woman does not want to talk to this man, if possible.
     g: (m, w) -> {-1,0,1,2}, which is preference of a specific man to talk with a specific woman: -1 means, that the man does not want to talk to this woman, if possible.

Target: Accomplish the "best" dating plan, meaning a pairing function for each talking session, which maximizes by summing over all dates using this function: m, w -> max(f(m,w),g(w,m)). During the talking sessions noone should date a person he has met before.
Is there a greedy algorithm for this problem, e.g. by matching the most loved-person with the most preferred person having the least number of talks?

REPLY [1 votes]: This is simply the Stable Marriage Problem, where rankings go from -1 to 2 instead of 1 to n. Thus it's almost a subset of the problem solved by the Gale–Shapley algorithm. Quoting from Wikipedia:

The Gale–Shapley algorithm involves a number of "rounds" (or
  "iterations").
In the first round, first a) each unengaged man proposes to the woman
  he prefers most, and then b) each woman replies "maybe" to her suitor
  she most prefers and "no" to all other suitors. She is then
  provisionally "engaged" to the suitor she most prefers so far, and
  that suitor is likewise provisionally engaged to her.
In each subsequent round, first a) each unengaged man proposes to the
  most-preferred woman to whom he has not yet proposed (regardless of
  whether the woman is already engaged), and then b) each woman replies
  "maybe" to her suitor she most prefers (whether her existing
  provisional partner or someone else) and rejects the rest (again,
  perhaps including her current provisional partner).
The provisional nature of engagements preserves the right of an
  already-engaged woman to "trade up" (and, in the process, to "jilt"
  her until-then partner).
This algorithm guarantees that:
Everyone gets married.
Once a woman becomes engaged, she is always engaged to someone. So, at
  the end, there cannot be a man and a woman both unengaged, as he must
  have proposed to her at some point (since a man will eventually
  propose to everyone, if necessary) and, being unengaged, she would
  have had to have said yes.
The marriages are stable.
Let Alice be a woman and Bob be a man who are both engaged, but not to
  each other. Upon completion of the algorithm, it is not possible for
  both Alice and Bob to prefer each other over their current partners.
  If Bob prefers Alice to his current partner, he must have proposed to
  Alice before he proposed to his current partner. If Alice accepted his
  proposal, yet is not married to him at the end, she must have dumped
  him for someone she likes more, and therefore doesn't like Bob more
  than her current partner. If Alice rejected his proposal, she was
  already with someone she liked more than Bob.

It's not greedy, so I'm not totally answering the question, but it works. It's probably easier if you convert the problem to the marriage problem by changing the -1...2 to 1-n (by picking randomly higher preferences in the case of ties) before processing, I think.
Edit: Nevermind, this doesn't have the least number of talks either I think, but I figured it was still worth bringing up. Really it depends on whether those talking preferences are known beforehand (and we are optimizing the pairings, in which case this algorithm works), or whether those talking preferences aren't known until a talking session begins - in which case this algorithm isn't applicable at all. I mean you could just set everyone up with everyone else, compute these values, then run the algorithm above, but it's certainly not optimal.


TITLE: The "Energy transformation" of a second order differential equation
QUESTION [1 upvotes]: After asking a question regarding the math myself, as well as finding some others, I am still puzzled by the opening sections of Jordan, D. and Smith, P. (2011). Nonlinear ordinary differential equations. We start off with the equation of motion for a simple pendulum, where $x$ denotes the angular displacement of the pendulum:
$$
    \ddot{x} + \omega^2 \sin{x} = 0.
$$
Here, $\ddot{x} = \mathop{\mathrm{d}}^2x/\mathop{\mathrm{d}}t^2$, and similarily, $\dot{x}= \mathop{\mathrm{d}}x / \mathop{\mathrm{d}}{t}$. Then, the first element that confuses me is the statement
$$
    \ddot{x} = \frac{\mathop{\mathrm{d}}}{\mathop{\mathrm{d}}t} \frac{\mathop{\mathrm{d}}x}{\mathop{\mathrm{d}}t} = \frac{\mathop{\mathrm{d}}\dot{x}}{\mathop{\mathrm{d}}t} = \frac{\mathop{\mathrm{d}}\dot{x}}{\mathop{\mathrm{d}}x} \frac{\mathop{\mathrm{d}x}}{\mathop{\mathrm{d}}t} = \frac{\mathrm{d}}{\mathrm{d}x} \left(\frac{1}{2} \dot{x}^2 \right).
$$
According to the authors, this is known as the energy transformation. I haven't been able to find any other literature supporting this, so my first question is this: Is energy transformation a general term for ODEs, or is it a special name for this operation on the pendulum equation?
To continue, I understand the equation given that one may write $\dot{x} = \dot{x}(x)$, but that doesn't seem right to me, as the angular velocity may be both increasing and decreasing at any given $x$, depending upon if the pendulum is currently moving "up" or "down". I wouldn't know how to evaluate $\mathop{\mathrm{d}}\dot{x} / \mathop{\mathrm{d}}x$ by itself. My second question is therefore: Is there a more rigorous way to arrive at the same result?

REPLY [2 votes]: Simply multiply the equation with $\dot x$ and integrate for the time to get
$$
\int (\dot x\ddot x+ω^2\sin(x)\dot x)dt=\frac12\dot x^2 + ω^2(1-\cos x) = E(x,\dot x)=const.
$$
The second part can be substituted as $\int \sin x\,dx$. Forcing the same substitution on the first term instead of integrating directly as product $\int v\dot v\,dt$ gives rise to the cited contortion of the formalism.
Note that in the Lagrange formalism you get in this context
$$
\ddot x =\frac{d}{dt}\frac{\partial(\frac12\dot x^2)}{\partial \dot x}.
$$
as part of the Euler-Lagrange equations
$$
0=\frac{d}{dt}\frac{∂L}{∂\dot x}-\frac{∂L}{∂x}.
$$


text:
\RequirePackage{luatex85}

\documentclass[11pt,notitlepage,a4paper]{report}
\usepackage[T1]{fontenc}
\usepackage{isabelle,isabellesym,eufrak}
\usepackage[english]{babel}

% For graphics files
\usepackage{graphicx}

% this should be the last package used
\usepackage{pdfsetup}

% urls in roman style, theory text in math-similar italics
\urlstyle{rm}
\isabellestyle{it}

% XYPic package, for drawing commutative diagrams.
\input{xy}
\xyoption{curve}
\xyoption{arrow}
\xyoption{matrix}
\xyoption{2cell}
\xyoption{line}
\UseAllTwocells

% Even though I stayed within the default boundary in the JEdit buffer,
% some proof lines wrap around in the PDF document.  To minimize this,
% increase the text width a bit from the default.
\addtolength\textwidth{60pt}
\addtolength\oddsidemargin{-30pt}
\addtolength\evensidemargin{-30pt}

\begin{document}

\title{Bicategories}
\author{Eugene W. Stark\\[\medskipamount]
        Department of Computer Science\\
        Stony Brook University\\
        Stony Brook, New York 11794 USA}
\maketitle

\begin{abstract}
Taking as a starting point the author's previous work
(\cite{Category3-AFP} \cite{MonoidalCategory-AFP})
on developing aspects of category theory in Isabelle/HOL, this article gives a
compatible formalization of the notion of ``bicategory'' and develops a
framework within which formal proofs of facts about bicategories can be given.
The framework includes a number of basic results, including the
Coherence Theorem, the Strictness Theorem, pseudofunctors and biequivalence,
and facts about internal equivalences and adjunctions in a bicategory.
As a driving application and demonstration of the utility of the framework,
it is used to give a formal proof of a theorem, due to Carboni, Kasangian,
and Street \cite{carboni-et-al}, that characterizes up to biequivalence
the bicategories of spans in a category with pullbacks.
The formalization effort necessitated the filling-in of many details
that were not evident from the brief presentation in the original paper,
as well as identifying a few minor corrections along the way.

Revisions made subsequent to the first version of this article added additional
material on pseudofunctors, pseudonatural transformations, modifications, and equivalence
of bicategories; the main thrust being to give a proof that a pseudofunctor is
a biequivalence if and only if it can be extended to an equivalence of bicategories.
\end{abstract}

\tableofcontents

\phantomsection
\addcontentsline{toc}{chapter}{Introduction}
\chapter*{Introduction}

Bicategories, introduced by B\'{e}nabou \cite{benabou}, are a generalization of categories
in which the sets of arrows between pairs of objects (\emph{i.e.}~the ``hom-sets'')
themselves have the structure of categories.  In a typical formulation, the definition of
bicategories involves three separate kinds of entities: \emph{objects} (or \emph{$0$-cells}),
\emph{arrows} (or \emph{$1$-cells}), and morphisms between arrows (or \emph{$2$-cells}).
There are two kinds of composition: \emph{vertical} composition, which composes $2$-cells
within a single hom-category, and \emph{horizontal} composition, which composes $2$-cells in
``adjacent'' hom-categories ${\rm hom}(A, B)$ and ${\rm hom}(B, C)$.
Horizontal composition is required to be functorial with respect to vertical composition;
the identification of a $1$-cell with the corresponding identity $2$-cell then leads to the
ability to horizontally compose $1$-cells with $2$-cells (\emph{i.e.}~``whiskering'')
and to horizontally compose $1$-cells with each other.
Each hom-category ${\rm hom}(A, A)$ is further equipped with an \emph{identity} $1$-cell
${\rm id}_A$, which serves as a unit for horizontal composition.
In a \emph{strict} bicategory, also known as a \emph{$2$-category}, the usual unit and
associativity laws for horizontal composition are required to hold exactly,
or (as it is said) ``on the nose''.
In a general bicategory, these laws are only required to hold ``weakly'';
that is, up to a collection of (vertical) isomorphisms that satisfy certain
\emph{coherence conditions}.
A bicategory, all of whose hom-categories are discrete, is essentially an ordinary category.
A bicategory with just one object amounts to a monoidal category whose tensor is given by
horizontal composition.
Alternatively, we may think of bicategories as a generalization of monoidal categories in
which the tensor is permitted to be a partial operation, in analogy to the way in which
ordinary categories can be considered as a generalization of monoids.

A standard example of a bicategory is \textbf{Cat}, the bicategory whose $0$-cells are
categories, whose $1$-cells are functors, and whose $2$-cells are natural transformations.
This is in fact a $2$-category; however, as two categories that are related by an equivalence
of categories have the same ``categorical'' properties, it is often more sensible to
consider constructions on categories as given up to equivalence, rather than up to
isomorphism, and this leads to considering \textbf{Cat} as a bicategory and using
bicategorical constructions rather than as a $2$-category and using $2$-categorical ones.
This is one reason for the importance of bicategories: as Street \cite{street-fibrations-ii} remarks,
``In recent years it has become even more obvious that, although the fundamental constructions
of set theory are categorical, the fundamental constructions of category theory are bicategorical.''

An alternative reason for studying bicategories, which is more aligned with my own
personal interests and forms a major reason why I chose to pursue the present project,
is that they provide an elegant framework for theories of generalized relations,
as has been shown by Carboni, Walters, Street, and others \cite{carboni-et-al}
\cite{cartesian-bicategories-i} \cite{cartesian-bicategories-ii} \cite{carboni-partial-maps}.
Indeed, the category of sets and relations becomes a bicategory by taking the inclusions
between relations as $2$-cells and thereby becomes an exemplar of the notion
bicategory of relations which itself is a specialization of the notion of
cartesian bicategory \cite{cartesian-bicategories-i} \cite{cartesian-bicategories-ii}.
In the study of the semantics of programming languages containing nondeterministic or
concurrent constructs, it is natural to consider the meaning of a program in such a language
as some kind of relation between inputs and outputs.  Ordinary relations can be used for
this purpose in simple situations, but they fail to be adequate for the study of higher-order
nondeterministic programs or for concurrent programs that engage in interaction with their environment,
so some sort of notion of generalized relation is needed.  One is therefore led to try to identify
some kind of bicategories of generalized relations as framework suitable for defining the
semantics of such programs.  One expects these to be instances of cartesian bicategories.

I attempted for a long time to try to develop a semantic framework for a certain class of
interactive concurrent programs along the lines outlined above, but ultimately failed to obtain
the kind of comprehensive understanding that I was seeking.  The basic idea was to try to
regard a program as denoting a kind of generalized machine, expressed as some sort of
bimodule or two-sided fibration ({\em cf.}~\cite{street-fibrations-i} \cite{street-fibrations-ii}),
to be represented as a certain kind of span in an underlying category of ``maps'',
which would correspond to the meanings of deterministic programs.
A difficulty with trying to formulate any kind of theory like this is that there quickly gets
to be a lot of data and a lot of properties to keep track of, and it was certainly more than
I could handle.
For example, bicategories have objects, $1$-cells, and $2$-cells, as well as domains, codomains,
composition and identities for both the horizontal and vertical structure.
In addition, there are unit and associativity isomorphisms for the weak horizontal composition,
as well as their associated coherence conditions.
Cartesian bicategories are symmetric monoidal bicategories, which means that there is an additional
tensor product, which comes with another set of canonical isomorphisms and coherence conditions.
Still more canonical morphisms and coherence conditions are associated with the cartesian structure.
Even worse, in order to give a proper account of the computational ideas I was hoping to capture,
the underlying category of maps would at least have to be regarded as an ordered category,
if not a more general $2$-category or bicategory, so the situation starts to become truly daunting.

With so much data and so many properties, it is unusual in the literature to find proofs written
out in anything approaching complete detail.
To the extent that proofs are given, they often involve additional assumptions made purely for
convenience and presentational clarity, such as assuming that the bicategories under consideration
are strict when actually they are not, and then discharging these assumptions by appeals to informal
arguments such as ``the result holds in the general case because we can always replace a non-strict
bicategory by an equivalent strict one.''
This is perhaps fine if you happen to have finely honed insight, but in my case I am always left
wondering if something important hasn't been missed or glossed over, and I don't trust very much
my own ability to avoid gross errors if I were to work at the same level of detail as the proofs
that I see in the literature.
So my real motivation for the present project was to try to see whether a proof assistant
would actually be useful in carrying out fully formalized, machine-checkable proofs of some kind
of interesting facts about bicategories.  I also hoped in the process to develop a better
understanding of some concepts that I knew that I hadn't understood very well.

The project described in the present article is divided into two main parts.
The first part, which comprises Chapter 1, seeks to develop a formalization of the notion of
bicategory using Isabelle/HOL and to prove various facts about bicategories that are required
for a subsequent application.  Additional goals here are:
(1) to be able to make as much use as possible of the formalizations previously created for
categories \cite{Category3-AFP} and monoidal categories \cite{MonoidalCategory-AFP};
(2) to create a plausibly useful framework for future extension; and
(3) to better understand some subtleties involved in the definition of bicategory.
In this chapter, we give an HOL formalization of bicategories that makes use of and extends the
formalization of categories given in \cite{Category3-AFP}.  In that previous work, categories
were formalized in an ``object-free'' style in terms of a suitably defined associative partial
binary operation of composition on a single type.  Elements of the type that behave as units
for the composition were called ``identities'' and the ``arrows'' were identified as
the elements of the type that are composable both on the left and on the right with identities.
The identities composable in this way with an arrow were then shown to be uniquely determined,
which permitted domain and codomain functions to be defined.
This formalization of categories is economical in terms of basic data (only a single partial
binary operation is required), but perhaps more importantly, functors and natural transformations
need not be defined as structured objects, but instead can be taken to be ordinary functions
between types that suitably preserve arrows and composition.

In order to carry forward unchanged the framework developed for categories, for the
formalization of bicategories we take as a jumping-off point the somewhat offbeat view of
a bicategory as a single global category under vertical composition (the arrows are
the $2$-cells), which is then equipped with an additional partial binary operation of
horizontal composition.  This point of view corresponds to thinking of bicategories as
generalizations of monoidal categories in which the tensor is allowed to be a partial
operation.  In a direct generalization of the approach taken for categories,
we then show that certain \emph{weak units} with respect to the horizontal composition play
the role of $0$-cells (the identities with respect to vertical composition play the role
of $1$-cells) and that we can define the \emph{sources} and \emph{targets} of an arrow
as the sets of weak units horizontally composable on the right and on the left with it.
We then define a notion of weak associativity for the horizontal composition and arrive
at the definition of a \emph{prebicategory}, which consists of a (vertical) category equipped
with an associative weak (horizontal) composition, subject to the additional assumption
that every vertical arrow has a nonempty set of sources and targets with respect to
the horizontal composition.
We then show that, to obtain from a prebicategory a structure that satisfies a more
traditional-looking definition of a bicategory, all that is necessary is to choose
arbitrarily a particular representative source and target for each arrow.
Moreover, every bicategory determines a prebicategory by simply forgetting the chosen
sources and targets.
This development clarifies that an \emph{a priori} assignment of source and target objects
for each $2$-cell is merely a convenience, rather than an element essential to the notion
of bicategory.

Additional highlights of Chapter 1 are as follows:
\begin{itemize}
\item  As a result of having formalized bicategories essentially as ``monoidal categories with
  partial tensor'', we are able to generalize to bicategories, in a mostly straightforward way,
  the proof of the Coherence Theorem we previously gave for monoidal categories in
  \cite{MonoidalCategory-AFP}.
  We then develop some machinery that enables us to apply the Coherence Theorem to shortcut
  certain kinds of reasoning involving canonical isomorphisms.
%
\item  Using the syntactic setup developed for the proof of the Coherence Theorem, we also
  give a proof of the Strictness Theorem, which states that every bicategory is biequivalent
  to a $2$-category, its so-called ``strictification''.
%
\item  We define the notions of internal equivalence and internal adjunction in a bicategory
  and prove a number of basic facts about these notions, including composition of equivalences
  and adjunctions, and that every equivalence can be refined to an adjoint equivalence.
%
\item  We formalize the notion of a pseudofunctor between bicategories, generalizing the
  notion of a monoidal functor between monoidal categories and we show that pseudofunctors
  preserve internal equivalences and adjunctions.
%
\item  We define a sub-class of pseudofunctors which we call \emph{equivalence pseudofunctors}.
  Equivalence pseudofunctors are intended to coincide with those pseudofunctors that can
  be extended to an equivalence of bicategories, but we do not attempt to give an independent
  definition equivalence of bicategories in the present development.  Instead, we establish various
  properties of equivalence pseudofunctors to provide some confidence that the notion has been
  formalized correctly.  Besides establishing various preservation results, we prove that,
  given an equivalence pseudofunctor, we may obtain one in the converse direction.
  For the rest of this article we use the property of two bicategories being connected by an
  equivalence pseudofunctor as a surrogate for the property of biequivalence,
  leaving for future work a more proper formulation of equivalence of bicategories and a
  full verification of the relationship of this notion with equivalence pseudofunctors.
\end{itemize}

The second part of the project, presented in Chapter 2, is to demonstrate the utility of
the framework by giving a formalized proof of a nontrivial theorem about bicategories.
For this part, I chose to tackle a theorem of Carboni, Kasangian, and Street
(\cite{carboni-et-al}, ``CKS'' for short)
which gives axioms that characterize up to equivalence those bicategories whose $1$-cells are
spans of arrows in an underlying category with pullbacks and whose $2$-cells are arrows
of spans.  The original paper is very short (nine pages in total) and the result I planned to
formalize (Theorem 4) was given on the sixth page.  I thought I had basically understood this result
and that the formalization would not take very long to accomplish, but I definitely
underestimated both my prior understanding of the result and the amount of auxiliary material
that it would be necessary to formalize before I could complete the main proof.
Eventually I did complete the formalization, and in the process filled in what seemed to me
to be significant omissions in Carboni, Kasangian, and Street's presentation, as well as
correcting some errors of a minor nature.

Highlights of Chapter 2 are the following:
\begin{itemize}
\item  A formalization of the notion of a category with chosen pullbacks, a proof that
  this formalization is in agreement with the general definition of limits we gave
  previously in \cite{Category3-AFP}, and the development of some basic properties
  of a category with pullbacks.
%
\item  A construction, given a category $C$ with chosen pullbacks, of the ``span bicategory''
  ${\rm Span}(C)$, whose objects are those of the given category, whose $1$-cells are spans
  of arrows of $C$, and whose $2$-cells are arrows of spans.
  We characterize the maps (the \emph{i.e.}~left adjoints) in ${\rm Span}(C)$ as
  exactly those spans whose ``input leg'' is invertible.
%
\item  A formalization of the notion of \emph{tabulation} of a $1$-cell in a bicategory
  and a development of some of its properties.  Tabulations are a kind of bicategorical
  limit introduced by CKS, which can be used to define a kind of biuniversal way of factoring
  a $1$-cell up to isomorphism as the horizontal composition of a map and the adjoint of
  a map.
%
\item  A formalization of \emph{bicategories of spans}, which are bicategories that satisfy
  three axioms introduced in CKS.  We give a formal proof of CKS Theorem 4,
  which characterizes the bicategories of spans as those bicategories that are biequivalent
  to a bicategory ${\rm Span}(C)$ for some category $C$ with pullbacks.
  One direction of the proof shows that if $C$ is a category with pullbacks,
  then ${\rm Span}(C)$ satisfies the axioms for a bicategory of spans.
  Moreover, we show that the notion ``bicategory of spans'' is preserved under equivalence
  of bicategories, so that in fact any bicategory biequivalent to one of the form ${\rm Span}(C)$
  is a bicategory of spans.
  Conversely, we show that if $B$ is a bicategory of spans, then $B$ is biequivalent
  to ${\rm Span}({\rm Maps}(B))$, where ${\rm Maps}(B)$ is the so-called \emph{classifying category}
  of the maps in $B$, which has as objects those of $B$ and as arrows the isomorphism classes
  of maps in $B$.

  In order to formalize the proof of this result, it was necessary to develop a number of
  details not mentioned by CKS, including ways of composing tabulations vertically and
  horizontally, and spelling out a way to choose pullbacks in ${\rm Maps}(B)$ so that
  the tupling of arrows of ${\rm Maps}(B)$ obtained using the chosen pullbacks agrees
  with that obtained through horizontal composition of tabulations.
  These details were required in order to give the definition of the compositor for an equivalence
  pseudofunctor ${\rm SPN}$ from $B$ to ${\rm Span}({\rm Maps}(B))$ and establish the
  necessary coherence conditions.
\end{itemize}

In the end, I think it can be concluded that Isabelle/HOL can be used with benefit to formalize
proofs about bicategories.  It is certainly very helpful for keeping track of the data
involved and the proof obligations required.  For example, in the formalization given here,
a total of 99 separate subgoals are involved in proving that a given set of data constitutes
a bicategory (only 7 subgoals are required for an ordinary category)
and another 29 subgoals must be proved in order to establish a pseudofunctor between two
bicategories (only 5 additional subgoals are required for an ordinary functor),
but the proof assistant assumes the burden of keeping track of these proof obligations and
presenting them to the human user in a structured, understandable fashion.
On the other hand, some of the results proved here still required some lengthy equational
``diagram chases'' for which the proof assistant (at least so far) didn't provide that much help
(aside from checking their correctness).
An exception to this was in the case of equational reasoning about expressions constructed
purely of canonical isomorphisms, which our formulation of the Coherence Theorem permitted
to be carried out automatically by the simplifier.
It seems likely, though, that there is still room for more general procedures to be developed
in order to allow other currently lengthy chains of equational reasoning to be carried out
automatically.

\medskip\par\noindent
{\bf Revision Notes}

The original version of this article dates from January, 2020.
The current version of this article incorporates revisions made throughout 2020.
A number of the changes made in early to mid-2020 consisted of minor improvements
and speedups.  A more major change made in this period was that the theory
``category with pullbacks'' was moved to \cite{Category3-AFP}, where it more
logically belongs.

In late 2020 additional material was added relating to pseudofunctors,
pseudonatural transformations, and equivalence of bicategories.
The main result shown was that a pseudofunctor is a biequivalence if and only
if it can be extended to an equivalence of bicategories.
This important result was sidestepped in the original version of this article,
but the author felt that it was a glaring omission that should be corrected.
Unfortunately, to formalize these results required some rather lengthy calculations
in order to establish coherence conditions.  These calculations added significantly
to the line count of this article, as well as the time and memory required to
validate the proofs.

In July, 2021, a ``concrete bicategory'' construction analogous to the ``concrete category''
construction in \cite{Category3-AFP} was added.  This construction was used to give
a construction of the bicategory of categories, functors, and natural transformations,
which was then shown to be strict.

\phantomsection
\addcontentsline{toc}{chapter}{Preliminaries}
\chapter*{Preliminaries}

\input{IsomorphismClass.tex}

\chapter{Bicategories}

\input{Prebicategory.tex}
\input{Bicategory.tex}
\input{ConcreteBicategory.tex}
\input{Coherence.tex}
\input{CanonicalIsos.tex}
\input{Subbicategory.tex}
\input{InternalEquivalence.tex}
\input{Pseudofunctor.tex}
\input{Strictness.tex}
\input{CatBicat.tex}
\input{InternalAdjunction.tex}
\input{PseudonaturalTransformation.tex}
\input{Modification.tex}
\input{EquivalenceOfBicategories.tex}

\chapter{Bicategories of Spans}

\input{SpanBicategory.tex}
\input{Tabulation.tex}
\input{BicategoryOfSpans.tex}

\phantomsection
\addcontentsline{toc}{chapter}{Bibliography}

\bibliographystyle{abbrv}
\bibliography{root}

\end{document}

subset_name: curated


TITLE: Asymptotic differential equation for large $t$. Can I just drop fast decaying terms?
QUESTION [0 upvotes]: I am looking at the differential equation
$x'(t)=x(t) (1+s(t))$.
and I want to make a statement about the behaviour of its solution $x(t)$ for large $t$, knowing that for large $t$
$s(t)=\frac{1}{2}-\frac{1}{2t}+\text{terms decaying like }t^{-2}\text{ or faster}.$
Naively I would simply drop the higher order terms, since I know that for large enough $t$ those should be negligible. Setting $s(t)\approx\frac{1}{2}-\frac{1}{2t}$ and solve the resulting differential equation, yields
$x(t)\propto e^{3t/2}/\sqrt t$.
Is this way of approximating the differential equation and its solution for large $t$ legal? If not, why not, and what else could I say about the solution $x(t)$ for large $t$, given the asymptotic behaviour of $s(t)$?

REPLY [3 votes]: If $x > 0$, you can write your differential equation as
$$ \dfrac{d}{dt} \log(x(t)) = 1 + s(t)$$
so
$$ \log(x(t)) = c + \int (1+s(t))\; dt = c + \frac{3}{2} t - \frac{1}{2} \log t + O(t^{-1})$$
That is, there exist $T$ and $\epsilon$ such that for all $t > T$,
$$ c + \frac{3}{2} t - \frac{1}{2}\log t - \frac{\epsilon}{t} < \log(x(t))
<  c + \frac{3}{2} t - \frac{1}{2}\log t +   \frac{\epsilon}{t}$$
Now take the exponential...


TITLE: What is the purpose of the metal strip??
QUESTION [1 upvotes]: Context:

Two large, flat metal plates are held parallel to each other and
  separated by a distance $d$. They are connected together at their edge
  by a metal strip. A thin plastic sheet carrying a surface charge
  $\sigma$ per unit area is placed between the plates @ a distance
  $\frac{1}{3}d$ from the upper plate.
Call $\vec{E}_{1} $ and $\vec{E}_{2} $ the electric field near the
  upper and lower plates respectively. What are  $\vec{E}_{1} $ and
  $\vec{E}_{2} $?

What's the purpose of that metal strip? Would it affect the outcome? If so, how come? If not, why would it be mentioned in the question, any ideas?

REPLY [1 votes]: If the two plates were not connected together by a conducting material, like the metal strip, then this would not work as a capacitor.
My guess is that the metal strip symbolizes the conducting wires / lanes in a curcuit. They are simply trying to make the question sound more non-curcuit-like by calling it "two plates connected by a metal strip".


TITLE: How to calculаte $\int_{\ln\sqrt{8}} ^{\ln\sqrt{24}}\sqrt{1+e^{2x}} \, dx$
QUESTION [2 upvotes]: I need help with calculating this integral:
$$\int_{\ln\sqrt{8}} ^{\ln\sqrt{24}}\sqrt{1+e^{2x}} \, dx$$
I got the answer using five replacements and I think my long solution is not optimal. Please give me advice what methods and how should I use.

REPLY [1 votes]: $$\int_{\ln\sqrt{8}} ^{\ln\sqrt{24}}\sqrt{1+e^{2x}} \, dx$$
$$1+e^{2x}=t \Rightarrow e^{2x}=t-1 \Rightarrow 2x=\ln(t-1) \Rightarrow x={{\ln(t-1)}\over 2}=\ln{\sqrt{t-1}} $$ $$dx={1\over 2} \cdot {dt\over {t-1}}$$
$$x=\ln(\sqrt8) \Rightarrow t=9;\ x=\ln(\sqrt24) \Rightarrow t=25$$
$$\int_{9} ^{25}{\sqrt{t}dt\over 2({t-1})}=\int_{9} ^{25}{\sqrt{t}dt\over 2({\sqrt t-1})({\sqrt t+1})}=\int_{9} ^{25}{(\sqrt{t}+1-1)dt\over 2({\sqrt t-1})({\sqrt t+1})}=$$
$$=\int_{9} ^{25}{dt\over 2({\sqrt t-1})}-\int_{9} ^{25}{dt\over 2({t-1})}$$
$$integral_1=\int_{9} ^{25}{dt\over 2({\sqrt t-1})}=\int_{9} ^{25}{\sqrt tdt\over 2\sqrt t({\sqrt t-1})}=\int_{9} ^{25}{\sqrt td(\sqrt t)\over {\sqrt t-1}}=\int_{9} ^{25}{(\sqrt t-1+1)d(\sqrt t)\over {\sqrt t-1}}=$$
$$=\int_{9} ^{25}{d(\sqrt t)}+\int_{9} ^{25}{d(\sqrt t)\over {\sqrt t-1}}=\sqrt t \biggr |_9^{25}+\ln(\sqrt t - 1)\biggr |_9^{25}=5-3+\ln4-\ln2=2+\ln2$$
$$integral_2=-\int_{9} ^{25}{dt\over 2({t-1})}={1\over 2}\ln(t-1)\biggr |_9^{25}=-0.5\ln24+0.5\ln8=0.5\ln({1\over 3})$$
Result is

$$2+\ln2+0.5\ln({1\over 3})\approx 2.14$$


TITLE: Minimum number of bits required to encode a subset of sequences of length 200
QUESTION [0 upvotes]: The typical set $S$ is given as consisting of all sequences $x$ with at most three 1s.
Here $x \in ${0,1}$ ^{200} $ and $P(0) = 0.99$
We can use $\log_{2}|S|$ to encode such sequences. And that is the best one can do in case of equal length codewords I think.
But how to get the minimum expected no. of bits required for encoding the sequences in $S$ ?
Should I think in terms of the ceil of the entropy of the least probable one of these sequences times the number of such sequences?

REPLY [1 votes]: You should have specified you were interested in minimizing the expected codeword length. Lets look at arbitrary $n,$ and consider $\{0,1\}^n.$
In that case you can assign a 1 bit codeword, say $0$, to the all zero sequence which has probability ($p=P(0)$)
$$
p^n,
$$
In general, you can specify all weight $w$ codewords with
$$
W_w = \left\lceil \log_2 \binom{n}{w}\right\rceil
$$
bits for $w=1,2,3.$
You have 4 classes of typical sequences $W_0,W_1,W_2,W_3$ and you can specify which class you have with a prefix of 2 bits [note for $p=0.99$ there may be a slightly more efficient use of the prefix but I don't think so since $.99^{200}$ is already a small number]. For the all zero codeword just use the prefix 00 and no extra bits are necessary.
So there exists a good code with small expected codeword length
$$
\overline{L}=2+\sum_{w=1}^3 W_w \binom{n}{w} p^{(n-w)}(1-p)^w.
$$
Using $\log_2 |S|$ I get 20.347 bits are needed so 21 bits are needed.
The expectation above is approximately 9.64 bits so you can get an expected codeword length of 10+2=12 bits, if I have calculated correctly (please check).


TITLE: References for "second order" random walk on graphs (used in "node2vec" paper)?
QUESTION [1 upvotes]: The "word2vec" family of methods provided a great breakthrough in natural language processing.
The methods assign to each word a vector in $R^{n}$, such that the "similar" words are assigned vectors close to one another in the space.
Later on the concept has been generalized to graph research in machine-learning,
where "nearby in some sense" nodes of a graph are assigned "nearby" vectors in $R^{n}$.
"Deepwalk" and "node2vec" are the most popular ones, both of them  define "nearby nodes" as nodes co-occuring in some random walks many times.
The "node2vec" considers unusual type of random walk - they call it "biased second order random walk"
(the comments are given below).
Question: Have this (or similar) random walks been considered in mathematical literature ?
What is known/unknown about them ?
"Biased second order random walk".
That random walk is defined with the help of two parameters p,q  - positive real numbers.
Random walk is "second order" that means it remembers the previous node (denoted s1).
Now assume the current node is "w" .
We split nearby nodes in THREE categories:

s1 - just the previous node

the nodes which are neigbours of BOTH - current node w and previous node s1

the other neigbours of  current node w, not falling in categories above.

Now we give weights 1/p, 1, 1/q for these categories, so first we sample category according to these weight, and latter choose node uniformly in category.
http://web.stanford.edu/class/cs224w/slides/07-noderepr.pdf

REPLY [1 votes]: This is nothing but an ordinary Markov chain whose state space is the set of oriented edges of the graph with the transition probabilities determined by the configuration of two adjacent oriented edges (more precisely, whether the distance between the endpoints is 0, 1, or 2). What do you want to know about this chain?


text:
\begin{document}
\title[Sum Rules and Divergent Lieb-Thirring Sums]{Sum Rules for Jacobi Matrices and Divergent Lieb-Thirring Sums}
\author[Andrej Zlato\v{s}]{Andrej Zlato\v{s}}

\address{ Department of Mathematics \\ University of
Wisconsin \\ Madison, WI 53706, USA \\ {\it E-mail address}: \tt
andrej@math.wisc.edu}

\thanks{2000 {\it Mathematics Subject Classification}. Primary: 47B36; Secondary: 34L15}
\thanks{Keywords: Jacobi matrix, sum rules, Lieb-Thirring sums}

\begin{abstract} Let $E_j$ be the
eigenvalues outside $[-2,2]$ of a Jacobi matrix with
$a_n-1\in\ell^2$ and $b_n\to 0$, and $\mu'$ the density of the
a.c.~part of the spectral measure for the vector $\delta_1$. We
show that if $b_n\notin\ell^4$, $b_{n+1}-b_{n}\in\ell^2$, then
\[
\sum_j(|E_j|-2)^{5/2} = \infty,
\]
and if $b_n\in\ell^4$, $b_{n+1}-b_{n}\notin\ell^2$, then
\[
\int_{-2}^2 \ln(\mu'(x)) (4-x^2)^{3/2}\, dx = -\infty.
\]
We also show that if $a_n-1,b_n\in\ell^3$, then the above integral
is finite if and only if $a_{n+1}-a_{n}, b_{n+1}-b_{n}\in\ell^2$.
We prove these and other results by deriving sum rules in which
the a.c.~part of the spectral measure and the eigenvalues appear
on opposite sides of the equation.
\end{abstract}

\maketitle

\section{Introduction} \lb{s1}

In the present paper we consider Jacobi matrices
\begin{equation*}
J\equiv \begin{pmatrix}
b_1 & a_1 & 0 & \dots \\
a_1 & b_2 & a_2 & \dots \\
0 & a_2 & b_3 & \dots \\
\dots & \dots & \dots & \dots \\
\end{pmatrix}
\end{equation*}
with $a_n>0$, $b_n\in\bbR$, and $a_n\to 1$, $b_n\to 0$. These are
compact perturbations of the {\it free matrix} $J_0$ with
$a_n\equiv 1$ and $b_n\equiv 0$. If only $a_n\equiv 1$, then $J$
is the discrete half-line Schr\" odinger operator with the
decaying potential $b_n$.

$J$ is a self-adjoint operator acting on $\ell^2(\{1,2,\dots\})$.
We denote by $\mu$ the spectral measure of the (cyclic for $J$)
vector $\delta_1$ and by $\mu'$ the density of its a.c.~part. For
$J_0$, the measure $\mu_0$ is absolutely continuous with $\mu_0'
(x)=(2\pi)^{-1} \sqrt{4-x^2} \chi_{[-2,2]}(x)$, and so by Weyl's
theorem, $\sigma_{\rm ess}(J)=\sigma_{\rm ess}(J_0)=[-2,2]$.
Hence, outside $[-2,2]$ spectrum of $J$ consists only of
eigenvalues (of multiplicity 1), with $\pm 2$ the only possible
accumulation points. We will denote the negative ones
$E_1,E_3,\dots$ and the positive ones $E_2,E_4,\dots$, with the
convention that $E_{2j-1}\equiv -2$ ($E_{2j}\equiv 2$) if $J$ has
fewer than $j$ eigenvalues below $-2$ (above $2$).

We let $\partial a_n\equiv a_{n+1}-a_{n}$, $\partial b_n\equiv
b_{n+1}-b_{n}$, and define
\[
r_n\equiv b_n^4-2(\partial b_n)^2 -8(\partial a_n)^2+
4(a_n^2-1)(b_n^2+b_nb_{n+1}+b_{n+1}^2).
\]
The following are our main results.

\begin{theorem} \lb{T.1}
Assume $a_n-1\in\ell^3$ and $b_n\to 0$.
\begin{SL}
\item[{\rm{(i)}}] If $\sum_{n=1}^\infty r_n=\infty$ or does not
exist, then $\sum_{j=1}^\infty (|E_j|-2)^{5/2} = \infty$.
\item[{\rm{(ii)}}] If $\sum_{n=1}^\infty r_n=-\infty$ or does not
exist, then $\int_{-2}^2 \ln(\mu'(x)) (4-x^2)^{3/2}\, dx =
-\infty$.
\end{SL}
\end{theorem}

{\it Remark.} One can actually dispense with the assumption
$a_n-1\in\ell^3$, but the corresponding $r_n$ is less transparent
(it is the diagonal element of the matrix $P_w(J)$ from the proof
of Theorem \ref{T.1}).

\begin{corollary} \lb{C.1a}
Assume $a_n-1\in\ell^2$ and $b_n\to 0$.
\begin{SL}
\item[{\rm{(i)}}] If $b_n\notin\ell^4$ and $\partial
b_n\in\ell^2$, then $\sum_{j=1}^\infty (|E_j|-2)^{5/2} = \infty$.
\item[{\rm{(ii)}}] If $b_n\in\ell^4$ and $\partial
b_n\notin\ell^2$, then $\int_{-2}^2 \ln(\mu'(x)) (4-x^2)^{3/2}\,
dx = -\infty$.
\end{SL}
\end{corollary}

\begin{proof}
Since $a_n-1\in\ell^2$, we have $\partial a_n\in\ell^2$. Also,
\[
|4(a_n^2-1)(b_n^2+b_nb_{n+1}+b_{n+1}^2)|\le 72 (a_n^2-1)^2 +
\tfrac 14(b_n^4+b_{n+1}^4)
\]
and $a_n^2-1\in\ell^2$, so the result follows from Theorem
\ref{T.1}.
\end{proof}

The sum in (i) is a Lieb-Thirring sum and most results go in the
direction opposite to (i), bounding sums of eigenvalue moments
from above in terms of the matrix elements. See \cite{HS}, where
it is proved that
\begin{equation} \lb{1.0a}
\sum_j(|E_j|-2)^{p} \le c_p \Big( \sum_n|a_n-1|^{p+1/2} +
\sum_n|b_n|^{p+1/2} \Big)
\end{equation}
for any $p\ge \tfrac 12$ and some $c_p>0$, and references therein.

The integral in (ii) is one from a family of Szeg\H o-type
integrals recently studied, among others, in
\cite{DHS,KS,Kupin2,Kupin,LNS,NPVY,SZ,Zla}. The actual Szeg\H o
integral has the weight $(4-x^2)^{-1/2}$ instead of
$(4-x^2)^{3/2}$ and is an important object in the theory of
orthogonal polynomials.

We also single out the following of our results (cf. Corollary
\ref{C.7}).

\begin{theorem} \lb{T.1b}
Assume $a_n-1,b_n\in\ell^3$. Then $\partial a_n,\partial
b_n\in\ell^2$ if and only if $\int_{-2}^2 \ln(\mu'(x))
(4-x^2)^{3/2}\, dx >-\infty$.
\end{theorem}

{\it Remarks.} 1. The ``only if'' part was proved in
\cite{Kupin2}.
\smallskip

2. Note that $a_n-1,b_n\in\ell^3$ and \eqref{1.0a} imply
$\sum_{j=1}^\infty (|E_j|-2)^{5/2} < \infty$.
\smallskip

We briefly review here related results. In \cite{KS}, which
started recent development in the area of sum rules, it is proved
that $a_n-1,b_n\in\ell^2$ if and only if $\sum_j(|E_j|-2)^{3/2} <
\infty$ and $\int_{-2}^2 \ln(\mu'(x)) (4-x^2)^{1/2}\, dx >
-\infty$. Using a higher sum rule \cite{Kupin} shows that
$a_n-1,b_n\in\ell^4$ and $\partial^2a_n,\partial^2b_n\in\ell^2$ if
and only if $\sum_j(|E_j|-2)^{7/2} < \infty$ and $\int_{-2}^2
\ln(\mu'(x)) (4-x^2)^{5/2}\, dx > -\infty$. Finally, \cite{LNS}
shows that $a_n-1,b_n\in\ell^4$ and
$a_{n+1}+a_n,b_{n+1}+b_n\in\ell^2$ if and only if
$\sum_j(|E_j|-2)^{3/2} < \infty$ and $\int_{-2}^2 \ln(\mu'(x))
x^2(4-x^2)^{1/2}\, dx > -\infty$. Closely related to our work is
also a general ``existence'' result in \cite{NPVY}.

From most such results one can conclude that a Lieb-Thirring sum
or a Szeg\H o-type integral is infinite for certain $a_n,b_n$, but
is not able to say which one of these happens. We achieve this by
obtaining sum rules in which these two quantities appear on
opposite sides of the equation (Theorem \ref{T.5}(i)). This is in
the spirit of Theorem 4.1 in \cite{SZ}, which shows that
$\limsup_n\sum_{j=1}^n\ln(a_n)=\infty$ implies
$\sum_j(|E_j|-2)^{1/2} = \infty$ and
$\liminf_n\sum_{j=1}^n\ln(a_n)=-\infty$ implies $\int_{-2}^2
\ln(\mu'(x))(4-x^2)^{-1/2}\, dx = -\infty$ (see also Theorem
\ref{T.8} below).

The paper is organized as follows. In Section \ref{s2} we
introduce the necessary tools, {\it Case sum rules for Jacobi
matrices} (see \cite{Case,KS,SZ,Zla}), and then extend these to a
form we will need here (Theorem \ref{T.5}). In Section \ref{s3} we
use them to prove Theorems \ref{T.1} and \ref{T.1b} and related
results. The author would like to thank Barry Simon for useful
communication.

\section{Sum Rules for Jacobi Matrices} \lb{s2}

In this section we use the notation of and extend results from
\cite{SZ}. If for some $\{c_\ell\}_{\ell=0}^k$ we have
$w(\tht)\equiv \sum_{\ell=0}^k c_\ell\cos(\ell\tht)\ge 0$, we
define
\begin{align}
Z_w (J) &\equiv -\f{1}{2\pi} \, \int_0^{\pi} \ln \biggl(
\f{\pi\mu'(2\cos\tht)}{\sin\tht}\biggr)\, w(\tht) \, d\theta
\notag
\\ &= -\f{1}{2\pi} \int_{-2}^2 \ln \biggl( \f{\mu'(x)}{\mu_0'(x)}\biggr)
 \sum_{\ell=0}^k c_\ell T_\ell \Big(\frac x2 \Big)
\f{dx}{\sqrt{4-x^2}}, \lb{2.1}
\end{align}
where $T_\ell(\cos\tht)\equiv \cos\ell\tht$ is the $\ell^{\rm th}$
Chebyshev polynomial (of degree $\ell$), and the second equality
follows from the substitution $x=2\cos\tht$. Since
$\ln(\mu'(x))\le \mu'(x)\sqrt{4-x^2}-\ln(\sqrt{4-x^2})$,
$\mu(\bbR)=1$, and $w(\tht)\ge 0$, the positive part of the
integral is bounded, that is,
\begin{equation} \lb{2.2}
Z_w(J)\ge C_w
\end{equation}
with $C_w>-\infty$ (but $Z_w(J)=\infty$ is possible). Note that
$Z_w(J_0)=0$.

We also let $|\beta_j|\ge 1$ be such that
$E_j=\beta_j+\beta_j^{-1}$. Hence
\begin{equation*}
|\beta_j|-1=(|E_j|-2)^{1/2} + O(|E_j|-2).
\end{equation*}

We define
\begin{equation*}
J^{(n)}= \begin{pmatrix}
b_{n+1} & a_{n+1} & 0 & \dots \\
a_{n+1} & b_{n+2} & a_{n+2} & \dots \\
0 & a_{n+2} & b_{n+3} & \dots \\
\dots & \dots & \dots & \dots \\
\end{pmatrix}
\end{equation*}
that is, $J^{(n)}$ is the matrix we obtain from $J$ by removing
the first $n$ rows and columns. We let $E_j^{(n)}\equiv
E_j(J^{(n)})$ and $\beta_j^{(n)}\equiv \beta_j(J^{(n)})$. We also
let $J_n$ be the matrix one obtains from $J$ by replacing $a_j$ by
1 and $b_{j+1}$ by 0 for $j\ge n$. Notice that $(J_n)^{(n)}=J_0$.

We denote (with $\ell\ge 1$)
\begin{align*}
X_0^{(n)}(J) &\equiv \sum_{j=1}^\infty  \Big[
\ln(|\beta_j|)-\ln(|\beta_j^{(n)}|) \Big],
\\ X_\ell^{(n)}(J) &\equiv \frac 1{2\ell} \sum_{j=1}^\infty  \Big[
\big( \beta_j^\ell-\beta_j^{-\ell} \big)- \big(
(\beta_j^{(n)})^\ell-(\beta_j^{(n)})^{-\ell} \big)  \Big].
\end{align*}
These sums are always convergent because
$X_\ell^{(n)}(J)=\sum_{j=0}^{n-1} X_\ell^{(1)}(J^{(j)})$ (where
$J^{(0)}\equiv J$), and the finiteness of $X_\ell^{(1)}(J)$
follows from the fact that positive (resp. negative) eigenvalues
of $J$ and $J^{(1)}$ interlace \cite{SZ}.

Finally, if $B$ is a semi-infinite matrix, we let $B(n)$ be the
matrix we obtain from $B$ by adding to it, from the top and left,
$n$ rows and columns containing only zeros. For instance,
$J^{(n)}(n)$ is the matrix one obtains from $J$ by replacing
$a_j,b_j$ for $j\le n$ by zeros. We then define
\begin{align*}
\xi_0^{(n)}(J) &\equiv -\sum_{j=1}^n \ln(a_j)
\\ \xi_\ell^{(n)}(J) &\equiv -\frac 1{\ell} \Tr \Big( T_\ell \big(\tfrac 12 J \big) - T_\ell \big(\tfrac 12 J^{(n)} \big)(n) \Big)
\end{align*}
for $\ell\ge 1$. These are well defined because the diagonal of
the matrix $T_\ell(\tfrac 12 J) - T_\ell(\tfrac 12 J^{(n)})(n)$
eventually vanishes (starting from $(n+\ell)^{\rm th}$ diagonal
element), although the matrix need not be trace class.

With this notation one has the following {\it step-by-step sum
rule}:

\begin{lemma} \lb{L.2}
If $w(\tht)=\sum_{\ell=0}^k c_\ell\cos(\ell\tht)\ge 0$, then
\begin{equation} \lb{2.3}
Z_w(J)=\sum_{\ell=0}^k c_\ell\xi_\ell^{(n)}(J) + \sum_{\ell=0}^k
c_\ell X_\ell^{(n)}(J) + Z_w(J^{(n)}).
\end{equation}
\end{lemma}

Remark. Here both sides can be $+\infty$. In particular,
$Z_w(J)=\infty$ if and only if $Z_w(J^{(n)})=\infty$.

\begin{proof}
One proves the statement for $n=1$ and then iterates the obtained
formula $n$ times. The proof is identical to that of Theorems
3.1--3.3 in \cite{SZ} (using their Remark 1 before Theorem 2.1),
where $w(\tht)\equiv 1$, $w(\tht)\equiv 1\pm\cos\tht$, and
$w(\tht)\equiv 1-\cos 2\tht$ (the proofs, with more detail, also
appear in \cite{Zla}).
\end{proof}

A natural question here is what happens when we take $n\to\infty$.
To do this we need to determine the convergence of the terms on
the right hand side of \eqref{2.3}. Following \cite{SZ}, one can
use two approximations --- $J$ by $J_n$, and $J_0$ by $J^{(n)}$
--- to treat the second and third term. We define
\begin{equation} \lb{2.4}
 f_w(\beta)\equiv c_0\ln(|\beta|)+\sum_{\ell=1}^k
\frac{c_\ell}{2\ell} \big( \beta^\ell-\beta^{-\ell} \big)
\end{equation}
so that
\[
\sum_{\ell=0}^k c_\ell X_\ell^{(n)}(J) = \sum_{j=1}^\infty \Big[
f_w(\beta_j)-f_w(\beta_j^{(n)}) \Big].
\]
We also let $X_{\ell,+}^{(n)}(J)$ be defined as $X_\ell^{(n)}(J)$
but with the sum taken only over positive eigenvalues. Similarly
we define $X_{\ell,-}^{(n)}(J)$, with only negative eigenvalues.
We then have
$X_\ell^{(n)}(J)=X_{\ell,+}^{(n)}(J)+X_{\ell,-}^{(n)}(J)$ and
\begin{align*}
\sum_{\ell=0}^k c_\ell X_{\ell,+}^{(n)}(J) & = \sum_{E_j\ge 2}
\Big[ f_w(\beta_j)-f_w(\beta_j^{(n)}) \Big],
\\ \sum_{\ell=0}^k c_\ell X_{\ell,-}^{(n)}(J) & = \sum_{E_j\le -2} \Big[
f_w(\beta_j)-f_w(\beta_j^{(n)}) \Big].
\end{align*}

\begin{lemma} \lb{L.3}
If $a_n\to 1$, $b_n\to 0$, and $w(\tht)=\sum_{\ell=0}^k
c_\ell\cos(\ell\tht)\ge 0$, then
\begin{align}
\liminf_{n\to\infty} Z_w(J^{(n)}) & \ge Z_w(J_0)=0, \lb{2.5}
\\ \liminf_{n\to\infty} Z_w(J_n) & \ge Z_w(J). \lb{2.6}
\end{align}
Also,
\begin{align}
\lim_{n\to\infty}\sum_{\ell=0}^k c_\ell X_{\ell,\pm}^{(n)}(J)  &
=\sum_{\pm E_j\ge 2} f_w(\beta_j),  \lb{2.7}
\\ \lim_{n\to\infty}\sum_{\ell=0}^k c_\ell X_{\ell,\pm}^{(n)}(J_n)
 & =\sum_{\pm E_j\ge 2} f_w(\beta_j). \lb{2.8}
\end{align}

\end{lemma}

{\it Remarks.} 1. Eqs. \eqref{2.7}, \eqref{2.8} are intended as
two statements each --- one with the plus signs and one with the
minus signs. This will be the case in Theorems \ref{T.5}(ii) and
\ref{T.8} as well.

2. The sums on the left hand sides of \eqref{2.7}, \eqref{2.8}
both exist but could be $\pm\infty$. We separate the sums over
positive and negative eigenvalues from each other because one
could be $\infty$ and the other $-\infty$.

\begin{proof}
Eqs. \eqref{2.4}, \eqref{2.5} follow directly from Corollary 5.3
in \cite{KS}.

Let us prove \eqref{2.7}, \eqref{2.8} with the plus signs (the
second case is identical). Notice that $f_w$ is continuous on
$[1,\infty)$ with $f_w(1)=0$. Since also $f_w\in C^\infty$ and not
all its derivatives at $1$ vanish (unless $f_w\equiv 0$), it is
monotone on some interval $[1,1+\eps]$, $\eps>0$ (and so the sums
in \eqref{2.7}, \eqref{2.8} exist). For such functions \eqref{2.7}
holds by Lemma 4.6 in \cite{SZ}. Similarly, \eqref{2.8} holds by
Theorem 6.2 in \cite{KS}, using that $(J_n)^{(n)}=J_0$ has no
eigenvalues (and so the left hand side is just $\lim_{n\to\infty}
\sum_{E_j\ge 2} f_w(\beta_j(J_n))$).
\end{proof}

To treat the first sum in \eqref{2.3} we define
\begin{equation} \lb{2.9}
P_w(J)\equiv S-c_0 A-\sum_{\ell=1}^k \frac {c_\ell}\ell
T_\ell(\tfrac 12 J)
\end{equation}
where $A$ is the matrix with $\ln(a_j)$ on the diagonal, and $S$
is the matrix with $S_{1,1}=-\sum_{\ell=1}^k
\tfrac{1}{4\ell}(1+(-1)^\ell)c_\ell$ and all other elements zero.

\begin{lemma} \lb{L.4} If $n>k$, then with $o(1)=o(n^0)$,
\begin{equation} \lb{2.10}
\sum_{\ell=0}^k c_\ell\xi_\ell^{(n)}(J) = \sum_{j=1}^{n} \big(
P_w(J) \big)_{j,j} +  o(1).
\end{equation}
\end{lemma}

\begin{proof}
As already mentioned, diagonal elements of $T_\ell(\tfrac 12 J) -
T_\ell(\tfrac 12 J^{(n)})(n)$ vanish starting from $(n+k)^{\rm
th}$. The first $n$ of them are equal to those of $T_\ell(\tfrac
12 J)$, so we are left with proving that the sum of the remaining
$k-1$ is $\tfrac 14(1+(-1)^\ell) + o(1)$.

The $(n+1)^{\rm st}$ through $(n+k-1)^{\rm st}$ diagonal elements
of $T_\ell(\tfrac 12 J)$ differ by $o(1)$ from those of
$T_\ell(\tfrac 12 J_0)$ (since $a_n\to 1$, $b_n\to 0$), and these
are $0$ when $n>k$ \cite[Lemma 3.29]{Zla}. The $(n+1)^{\rm st}$
through $(n+k-1)^{\rm st}$ diagonal elements of $T_\ell(\tfrac 12
J^{(n)})(n)$ differ by $o(1)$ from the $1^{\rm st}$ through
$(k-1)^{\rm st}$ of $T_\ell(\tfrac 12 J_0)$, which sum up to
$-\tfrac 14(1+(-1)^\ell)$ \cite[Lemma 3.29]{Zla}. The proof is
finished.
\end{proof}

With this preparation we can obtain the final form of the sum
rules.

\begin{theorem} \lb{T.5}
Let $a_n\to 1$, $b_n\to 0$, and $w(\tht)=\sum_{\ell=0}^k
c_\ell\cos(\ell\tht)\ge 0$.
\begin{SL}
\item[{\rm{(i)}}] If $f_w\ge 0$ on $[1,1+\eps]\cup[-1-\eps,-1]$
for some $\eps>0$, and either $Z_w(J)<\infty$ or
$\sum_{j=1}^\infty f_w(\beta_j)<\infty$, then $\Tr(P_w(J))$ exists
and
\[
Z_w(J)=\Tr(P_w(J)) + \sum_{j=1}^\infty f_w(\beta_j).
\]
\item[{\rm{(ii)}}] If $\pm f_w\ge 0$ on $[1,1+\eps]$ and $\pm
f_w\le 0$ on $[-1-\eps,-1]$ for some $\eps>0$, and either
$Z_w(J)<\infty$ and $\sum_{\pm E_j\le - 2}f_w(\beta_j)>-\infty$ or
$\sum_{\pm E_j\ge 2}f_w(\beta_j)<\infty$, then $\Tr(P_w(J))$
exists and
\[
Z_w(J) - \sum_{\pm E_j\le -2}f_w(\beta_j) = \Tr(P_w(J)) +
\sum_{\pm E_j\ge 2}f_w(\beta_j).
\]

\item[{\rm{(iii)}}] If $f_w\le 0$ on $[1,1+\eps]\cup[-1-\eps,-1]$
for some $\eps>0$, then $\Tr(P_w(J))$ exists and
\[
Z_w(J)- \sum_{j=1}^\infty f_w(\beta_j) = \Tr(P_w(J)).
\]
\end{SL}
\end{theorem}

{\it Remarks.} 1. The matrix $P_w(J)$ need not be trace-class, but

its trace, given by the sum of its diagonal elements, exists in
(i)--(iii).
\smallskip

2. We use here the convention that $\pm\infty+a=\pm\infty$ for
$a\in\bbR$ and $\infty-\infty$ can be anything. For example, if in
(i) $Z_w(J)<\infty$ and $\sum_{j}f_w(\beta_j)=\infty$, then
$\Tr(P_w(J))$ must be $-\infty$. Notice that in the above sum
rules, $\Tr(P_w(J))$ is the only term that can be $-\infty$.
\smallskip

3. Theorem \ref{T.5}(iii) is just the main result of \cite{NPVY}
in a different guise. It provides a characterization of the
$a_n$'s and $b_n$'s which correspond to matrices with spectral
measures for which a certain Szeg\H o-type integral involving
$\mu'$ and a certain Lieb-Thirring sum are both finite.
\smallskip

4. In the proofs of Theorems \ref{T.1} and \ref{T.1b} we will use
Theorem \ref{T.5}(i) with
\begin{equation} \lb{2.11}
w(\tht)\equiv 3-4\cos 2\tht + \cos 4\tht = 2 (1-\cos 2\tht)^2.
\end{equation}
The previously mentioned results from \cite{KS,Kupin} can be
obtained from Theorem \ref{T.5}(iii) by taking $w(\tht)\equiv
(1-\cos2\tht)^k$ for $k=1,3$, respectively.

\begin{proof}
(i) We take $n\to\infty$ in \eqref{2.3}. Using \eqref{2.5},
\eqref{2.7}, and \eqref{2.10} we obtain
\[
Z_w(J)\ge \limsup_{n\to\infty} \sum_{j=1}^n(P_w(J))_{j,j} +
\sum_{j=1}^\infty f_w(\beta_j).
\]
Similarly, writing \eqref{2.3} for $J_n$ in place of $J$ (with
$(J_n)^{(n)}=J_0$) and taking $n\to\infty$, from \eqref{2.5},
\eqref{2.8}, and \eqref{2.10} we obtain
\[
Z_w(J)\le \liminf_{n\to\infty} \sum_{j=1}^n(P_w(J))_{j,j} +
\sum_{j=1}^\infty f_w(\beta_j).
\]
Here we used the fact that the first $n-k$ diagonal elements of
$P_w(J)$ and $P_w(J_n)$ are the same, whereas the next $k$ differ
by $o(1)$. Unless both $Z_w(J)=\infty$ and $\sum_{j}
f_w(\beta_j)=\infty$, these inequalities can both be satisfied
only if the $\limsup=\liminf$.

The proofs of (ii) and (iii) are analogous.
\end{proof}

\section{Spectral Consequences} \lb{s3}

\begin{proof}[Proof of Theorem \ref{T.1}] First we note that
\begin{equation*}
T_0(x)=1,\quad T_2(x)=2x^2-1,\quad T_4(x)=8x^4-8x^2+1,
\end{equation*}
and so with $w$ as in \eqref{2.11} we have $\sum_{\ell=0}^k c_\ell
T_\ell(\tfrac x2)=\tfrac 12(4-x^2)^2$. Hence by \eqref{2.1},
$\int_{-2}^2 \ln(\mu'(x)) (4-x^2)^{3/2}\, dx = -\infty$ if and
only if $Z_w(J)=\infty$.

Next, we have
\[
f_w(\beta)\equiv 3\ln(|\beta|)-(\beta^2-\beta^{-2})+\tfrac
1{8}(\beta^4-\beta^{-4}) = \tfrac 8{5}(|\beta|-1)^5 +
O((|\beta|-1)^6).
\]
In particular, $\sum_j(|E_j|-2)^{5/2} = \infty$ if and only if
$\sum_j f_w(\beta_j) = \infty$.

Finally, with $S_{i,j}=\tfrac 78 \delta_{1,i}\delta_{1,j}$, we
have
\[
P_w(J) = S - 3A + 2 T_2(\tfrac 12 J) - \tfrac 1{4}T_4(\tfrac 12 J)
= S - 3A - \tfrac 1{8}(J^4-12J^2+18).
\]
If all $a_j=1$, then for $j\ge 4$ the $j^{\rm th}$ diagonal
element of $P_w(J)$ is
\begin{equation*}
- \tfrac 1{8}   \big[
(b_j^4+6b_j^2+b_{j-1}^2+b_{j+1}^2+2b_j(b_{j+1}+b_{j-1})+6)-12(b_j^2+2)+18
\big].
\end{equation*}

Since $b_j\to 0$, we get that the limit $\Tr(P_w(J))$ exists if
and only if $\sum_{j=1}^\infty [ b_j^4-2(\partial b_j)^2]$ exists,
and
\begin{equation*}
\Tr(P_w(J)) = - \frac 1{8}\sum_{j=1}^\infty \big[ b_j^4-2(\partial
b_j)^2 \big] + O\big(1+\|b_j\|_\infty\big).
\end{equation*}

For general $d_j\equiv a_j-1$ we get with $O(\|J\|_\infty)=
O(\|a_j\|_\infty+\|b_j|\|_\infty)$,

\begin{align}
-8\Tr(P_w(J)) =   \sum_{j=1}^\infty & \big[ b_j^4-2(\partial
b_j)^2-8(\partial d_j)^2  \notag
\\ +& 8d_j(2d_j^2+d_jd_{j+1}+d_{j+1}^2+b_j^2+b_jb_{j+1}+b_{j+1}^2) \notag
\\ +& 4d_j^2(-d_j^2+d_{j+1}^2+b_j^2+b_jb_{j+1}+b_{j+1}^2) +
O(d_j^5)\big] \notag
\\ +& O \big(\|J\|_\infty \big). \lb{2.12}
\end{align}
If $a_j-1\in\ell^3$, then this is $\sum_{j} r_j + O(\|d_j\|_3^3 +
\|J\|_\infty)$.

(i) From the hypothesis and \eqref{2.12}, we have
$\Tr(P_w(J))=-\infty$ or does not exist. Thus $\sum_j
f_w(\beta_j)=\infty$ by Theorem \ref{T.5}(i) and \eqref{2.2}.

(ii) Now $\Tr(P_w(J))=\infty$ or does not exist, and we use
Theorem \ref{T.5}(i) and $\sum_j f_w(\beta_j)>-\infty$ to get
$Z_w(J)=\infty$.
\end{proof}

By a careful examination of \eqref{2.12}, one can prove the
following variation on Theorem \ref{T.1}, allowing
$a_n-1\notin\ell^3$. We let $a_\pm\equiv\max\{\pm a,0\}$.

\begin{corollary} \lb{C.6}
\begin{SL}
\item[{\rm{(i)}}] If $(a_n-1)_-\in\ell^2$, $\partial a_n,\partial
b_n\in\ell^2$, and either $a_n-1\notin\ell^3$ or
$b_n\notin\ell^4$, then $\sum_j(|E_j|-2)^{5/2} = \infty$.

\item[{\rm{(ii)}}] If $(a_n-1)_+\in\ell^2$, $b_n\in\ell^4$ and
either $a_n-1\notin\ell^3$ or $\partial a_n\notin\ell^2$ or
$\partial b_n\notin\ell^2$, then $\int_{-2}^2 \ln(\mu'(x))
(4-x^2)^{3/2}\, dx = -\infty$.

\end{SL}
\end{corollary}

\begin{proof}
(i) Note that once $d_j$ is small enough, then for $d_j\le 0$ the
sum of the second and third lines in \eqref{2.12} is bounded below
by $-Cd_j^2-\eps(|d_{j+1}|^3+b_j^4+b_{j+1}^4)$ (for any $\eps>0$
and $C=C(\eps)<\infty$), and for $d_j\ge 0$ it is bounded below by
$8d_j^3$. So the whole sum is bounded below by $\sum_j
[(1-2\eps)b_j^4+(8-\eps) d_j^3-q_j]$ for some summable $q_j$,
proving $\Tr(P_w(J))=-\infty$. The result follows as in the proof
of Theorem \ref{T.1}(i).

(ii) One shows that $\Tr(P_w(J))=\infty$ in a similar way as in
(i), this time bounding the sum of the second and third lines of
\eqref{2.12} above by $Cd_j^2+\eps(|d_{j+1}|^3+b_j^4+b_{j+1}^4)$
for $d_j\ge 0$ and by $8d_j^3$ for $d_j\le 0$.
\end{proof}

\begin{proof}[Proof of Theorem \ref{T.1b}]
The hypothesis and \eqref{1.0a} give $\sum_j (|E_j|-2)^{5/2} <
\infty$. Hence, by Theorem \ref{T.5}(i) with $w$ given by
\eqref{2.11}, $\Tr(P_w(J))$ exists. And it is finite if and only
if $Z_w(J)<\infty$. But by the assumptions and \eqref{2.12}, the
former happens precisely when $\partial a_n,\partial
b_n\in\ell^2$. As in Theorem \ref{T.1}, the latter happens if and
only if $\int_{-2}^2 \ln(\mu'(x)) (4-x^2)^{3/2}\, dx > -\infty$.
\end{proof}

Here is an application of Theorem \ref{T.5}(i) to {\it
oscillatory} Jacobi matrices:

\begin{corollary} \lb{C.7}
If $\limsup_n \sum_{j=1}^n (|\partial a_j|^2+|\partial b_j|^2) /
\sum_{j=1}^n (|a_j-1|^3+|b_j|^3) =\infty$, then $\int_{-2}^2
\ln(\mu'(x)) (4-x^2)^{3/2}\, dx = -\infty$.
\end{corollary}

{\it Remark.} This applies, for example, in the case
$a_n=1+\alpha_1\cos(\mu n)/n^{\gamma_1}$ and $b_n=\alpha_2\cos(\mu
n)/n^{\gamma_2}$ when $\mu\notin 2\pi\bbZ$ and $\alpha_j\neq 0$,
$\gamma_j\le\tfrac 12$ for either $j=1$ or $j=2$. In \cite{DHS} it
was proved that in this case, with $\alpha_1=0$, $\int_{-2}^2
\ln(\mu'(x)) (4-x^2)^{-1/2}\, dx = -\infty$.

\begin{proof}
For $w$ as in the proof of Theorem \ref{T.1} we get
$\Tr(P_w(J))=\infty$ (from \eqref{2.12}). Then we continue as in
(ii) of that proof.
\end{proof}

Finally, here are two results illustrating the use of Theorem
\ref{T.5}(ii). The first has been proved in \cite{SZ} for the case
$a_n-1,b_n\in\ell^2$. The second is related to results in
\cite{DHKS,DK}.

\begin{theorem} \lb{T.8}
If $a_n\to 1$, $b_n\to 0$, and $\limsup_n \sum_{j=1}^n
[\ln(a_j)\pm \tfrac 12 b_j] =\infty$, then
\[
\sum_{\pm E_j\ge 2} (|E_j|-2)^{1/2} = \infty.
\]
\end{theorem}

\begin{proof}
Let $w(\tht)\equiv 1\pm\cos\tht$ so that
$f_w(\beta)=2(|\beta|-1)+O((|\beta|-1)^2)$ for $\pm\beta\downarrow
1$ and $f_w(\beta)=-\tfrac 16(|\beta|-1)^3+O((|\beta|-1)^4)$ for
$\pm\beta\uparrow -1$. Then $P_w(J)=-A\mp\tfrac 12 J$, and so its
$j^{\rm th}$ diagonal element is $-[\ln(a_j)\pm \tfrac 12 b_j]$.
Theorem \ref{T.5}(ii) finishes the proof.
\end{proof}

\begin{theorem} \lb{T.9}
If $a_n\to 1$, $b_n\to 0$, and one of $\sum_{n=1}^\infty
[\ln(a_n)\pm \tfrac 12 b_n]$ is larger than $\tfrac 12$ or does
not exist, then $J$ has at least one eigenvalue outside $[-2,2]$.
\end{theorem}

{\it Remark.} The bound $\tfrac 12$ is optimal as can be seen by
taking $a_n\equiv 1$ and $|b_n|\le\delta_{1,n}$. The corresponding
Jacobi matrix has no eigenvalues.

\begin{proof}
Take again $w(\tht)\equiv 1\pm\cos\tht$ in Theorem \ref{T.5}(ii).
By (2.45) in \cite{Zla},
\begin{align*}
Z_w(J) & \ge \int_0^\pi
(1-\cos\tht)\ln(2+2\cos\tht)\,\frac{d\tht}{2\pi}
\\ & = \frac 12 \int_0^{2\pi}
(1-\cos\tht)\ln\big|1+2e^{i\tht}+e^{2i\tht}\big|\,\frac{d\tht}{2\pi}.

\end{align*}
Jensen's formulae for the function $\ln|1+2z+z^2|=\Re(2z+O(z^2))$
show that the last integral equals $-1$.

If $J$ had no eigenvalues, we would have $-\tfrac
12\le Z_w(J)=\Tr(P_w(J))=-\sum_{n=1}^\infty [\ln(a_n)\pm \tfrac 12
b_n]$, a contradiction.
\end{proof}

config: arxiv


TITLE: Euclidean Operator Norm Identity
QUESTION [1 upvotes]: I'm trying to prove that $||A||=\sqrt{||AA^T||}$ where $||A||$ is the euclidean operator norm. I'm thinking something along the lines of inner products and making use of Cauchy-Schwarz.

REPLY [1 votes]: You have, using Cauchy-Schwarz, that $$\tag1\langle Ax,Ax\rangle=\langle A^*Ax,x\rangle\leq\|A^*A\|\,\|x\|^2=\|A^*A\|.$$ Then
$$\tag2
\|A\|^2=\sup\{\|Ax\|^2:\ \|x\|=1\}
=\sup\{\langle Ax,Ax\rangle:\ \|x\|=1\}\leq\|A^*A\|.
$$
Conversely,
$$\tag3
\|A^*A\|\leq\|A\|\,\|A^*\|.
$$
Combining $(2)$ and $(3)$, you get
$$
\|A\|^2\leq\|A\|\,\|A^*\|,
$$
implying $\|A\|\leq\|A\|^*$. If we repeat the above for $A^*$ we get $\|A^*\|\leq\|A^{**}\|=\|A\|$, so $\|A^*\|=\|A\|$.
Now we go back to $(3)$ to get
$$\tag4
\|A^*A\|\leq\|A\|^2,
$$
and $(2)$ and $(4)$ give
$\|A^*A\|=\|A\|^2$.


text:
{\bf Problem.} Consider a string of $n$ $7$'s, $7777\cdots77,$ into which $+$ signs are inserted to produce an arithmetic expression. For example, $7+77+777+7+7=875$ could be obtained from eight $7$'s in this way. For how many values of $n$ is it possible to insert $+$ signs so that the resulting expression has value $7000$?

{\bf Level.} Level 5
{\bf Type.} Number Theory
{\bf Solution.} Suppose we require $a$ $7$s, $b$ $77$s, and $c$ $777$s to sum up to $7000$ ($a,b,c \ge 0$). Then $7a + 77b + 777c = 7000$, or dividing by $7$, $a + 11b + 111c = 1000$. Then the question is asking for the number of values of $n = a + 2b + 3c$.
Manipulating our equation, we have $a + 2b + 3c = n = 1000 - 9(b + 12c) \Longrightarrow 0 \le 9(b+12c) < 1000$. Thus the number of potential values of $n$ is the number of multiples of $9$ from $0$ to $1000$, or $112$.
However, we forgot to consider the condition that $a \ge 0$. For a solution set $(b,c): n=1000-9(b+12c)$, it is possible that $a = n-2b-3c < 0$ (for example, suppose we counted the solution set $(b,c) = (1,9) \Longrightarrow n = 19$, but substituting into our original equation we find that $a = -10$, so it is invalid). In particular, this invalidates the values of $n$ for which their only expressions in terms of $(b,c)$ fall into the inequality $9b + 108c < 1000 < 11b + 111c$.
For $1000 - n = 9k \le 9(7 \cdot 12 + 11) = 855$, we can express $k$ in terms of $(b,c): n \equiv b \pmod{12}, 0 \le b \le 11$ and $c = \frac{n-b}{12} \le 7$ (in other words, we take the greatest possible value of $c$, and then "fill in" the remainder by incrementing $b$). Then $11b + 111c \le 855 + 2b + 3c \le 855 + 2(11) + 3(7) = 898 < 1000$, so these values work.
Similarily, for $855 \le 9k \le 9(8 \cdot 12 + 10) = 954$, we can let $(b,c) = (k-8 \cdot 12,8)$, and the inequality $11b + 111c \le 954 + 2b + 3c \le 954 + 2(10) + 3(8) = 998 < 1000$. However, for $9k \ge 963 \Longrightarrow n \le 37$, we can no longer apply this approach.
So we now have to examine the numbers on an individual basis. For $9k = 972$, $(b,c) = (0,9)$ works. For $9k = 963, 981, 990, 999 \Longrightarrow n = 37, 19, 10, 1$, we find (using that respectively, $b = 11,9,10,11 + 12p$ for integers $p$) that their is no way to satisfy the inequality $11b + 111c < 1000$.
Thus, the answer is $112 - 4 = \boxed{108}$.

set_name: MATH


TITLE: What does electroweak vacuum lifetime refer to?
QUESTION [2 upvotes]: I just read an article about the correlation between the Higgs boson mass and the stability (or metastability) of vacuum, so I want to ask to someone this:
When someone is talking about the electroweak vacuum lifetime, does it refer to a certain region of space, the time needed for quantum tunnelling to occur once in the whole vacuum, the lifetime of the entire vacuum or something else?

REPLY [1 votes]: I believe that no one has established a definition that is accurate up to order-one prefactors – that the lifetime is only being calculated as an order-of-magnitude estimate. This order-of-magnitude estimate is meant to be relevant for the real Universe.
In the real Universe, the volume where a dangerous decay may start is proportional to $c^3\tau^3$ where $\tau$ is the lifetime. So if the probability of the nucleation of a "bubble of the new vacuum" is
$$\gamma=\frac{dP}{d\Omega} = \frac{dP}{dt\cdot dV}$$
per unit spacetime four-volume, I believe that by the lifetime, people just mean
$$\tau =\left({\gamma}{c^3}\right)^{-1/4} $$
up to number-one prefactors that are not specified and it's somewhat likely that the normalization is exactly as I wrote it. Note that $\gamma$ has units of ${\rm m}^{-3}{\rm s}^{-1}$ which gets converted to ${\rm s}^{-4}$ with the multiplication by $c^3$.