TITLE: How to find the eigen values
QUESTION [0 upvotes]: How to find the eigen values of the graph having vertex set as $\{1,2,.......n\}$ and edge set as $\{(l,l+1)\}$ $ \cup (1,n)$ ?
 where $1\le l \le n$.
Here I am considering the Laplacian matrix of the graph.
Please give some hints . I am totally clueless.

REPLY [1 votes]: This is a cycle graph. I expect here the edges are undirected type. Hence your Laplacian matrix is $$L=\begin{bmatrix}2 & -1 & 0 & \cdots & 0 & -1\\ -1 & 2 & -1 & \cdots & 0 & 0\\0 & -1 & 2 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 2 & -1\\ -1 & 0 & 0 & \cdots & -1 & 2\end{bmatrix}.$$ This is a circulant matrix and for a circulant matrix the eigenvalues are already obtained. Using that you can get its eigenvalues.  Otherwise, observe that $L=2I_n-\mathcal{P}_n-\mathcal{P}_n^T,$ where $\mathcal{P}_n$ is the full-cycle permutation matrix. As ${\rm det}(\mathcal{P}_n-\lambda I_n)=(-1)^n(\lambda^n-1)$, the eigenvalues of $\mathcal{P}_n$ are the primitive $n$th roots of unity ($1, \omega, \ldots, \omega^{n-1}$ where $\omega=e^{\frac{2\pi\mathtt{i}}{n}}$). Further $\mathcal{P}_n^T=\mathcal{P}_n^{n-1}$. So the eigenvalues of $L$ are given by \begin{align*}2-\omega^k+\omega^{n-k}&=2-\omega^k-\omega^{-k}\\&=2-2\cos\frac{2\pi k}{n}\\&=4\sin^2\frac{\pi k}{n}, ~~~~\text{ for }k=1, \ldots, n.\end{align*}


TITLE: Physical motivation for tight/overtwisted dichotomy
QUESTION [9 upvotes]: I'm learning about tight vs. overtwisted contact structures in contact geometry. I understand that we care about the existence/nonexistence of overtwisted disks in a contact structure in part because the distinction has proved useful (e.g., in classification).
But since contact geometry has a lot of applications to physics, I'm curious: Are there any big physical reasons for why we care about this distinction?
(reposted from math.SE)

REPLY [4 votes]: In the physics of fluids, a reason for caring about tightness of the contact structure is the idea/conjecture that overtwisted discs raise the energy of the fluid.
The velocity field of an inviscid, incompressible fluid flow on a Riemannian manifold corresponds to a contact 1-form in dimension three.$^\ast$ In this context one can investigate how the topological tight/overtwisted dichotomy for contact structures relates to the physical properties of the fluid like its energy. Is the energy minimizing flow necessarily a tight contact structure? Ghrist and Komendarczyk, in Overtwisted energy-minimizing curl eigenfields, show that the answer is "no" in general, but "yes" under additional symmetry conditions.
$^\ast$ For an introduction and overview of this correspondence, see On the contact topology and geometry of ideal fluids.


TITLE: Accessible topics with a background of linear Algebra and Calculus
QUESTION [0 upvotes]: I have a background of a one year course in linear algebra (covering most of K&H) and two years of calculus (the first year was a one real variable course at the level of Spivak's Calculus book and then one year of multivariable calculus starting from topology of $\mathbb{R}^n$ and up to Stokes' theorem).
I am looking for some interesting and not-so popular topics which I can understand and help me develop my understanding of the topics I already know.

REPLY [4 votes]: I suggest at least looking over the following book. There's a 2nd edition available, but the 2nd edition is less theoretical and omits some of the linear algebra in the 1st edition. This book was very popular for those with approximately your background when I was an undergraduate (late 1970s), but I don't seem to hear about it much anymore (hence, it might fit your desire for something "not-so popular"). This book ties together and uses much of the calculus and linear algebra background that you have, and it also introduces/previews a few topics that come up in later math courses (e.g. some baby operator theory via exponentiation of matrices). Finally, at least in the U.S., you can find this book in most any college or university library (usually cataloged at QA3.P8).
Morris W. Hirsch and Stephen Smale, Differential Equations, Dynamical Systems, and Linear Algebra, Pure and Applied Mathematics #60, Academic Press, 1974, 358 pages.
http://www.amazon.com/dp/0123495504


TITLE: Joy of Cats Corollary 10.50
QUESTION [5 upvotes]: I have been studying category theory from Joy of Cats. I am stuck at proving Corollary 10.50 from Proposition 10.49. Which says that,

Embeddings of concretely reflective subcategories preserve initial sources.

Since I was trying to apply Proposition 10.49 I was thinking about somehow showing that the concrete reflector (say $R$) and the embedding (say $E$) forms a Galois correspondence. Then by Proposition 10.49 we could conclude that $E$ preserves initial sources. But that's precisely where I am stuck. Can anyone help?

For the sake of completeness here are the relevant definitions,

Definition 1. Let $\mathbf{X}$ be a category. A concrete category over $\mathbf{X}$ is a pair $(\mathbf{A},U)$, where $\mathbf{A}$ is a category and $U : \mathbf{A} \to \mathbf{X}$ is a faithful functor.
Definition 2. If $(\mathbf{A},U)$ and $(\mathbf{B}, V)$ are concrete categories over $\mathbf{X}$ , then a concrete functor from
$(\mathbf{A},U)$ to $(\mathbf{B}, V)$ is a functor $F : \mathbf{A}\to \mathbf{B}$ with $U = V \circ F$. We denote such a functor
by $F : (\mathbf{A},U)\to (\mathbf{B},V)$.
Definition 3. Let $(\mathbf{A},U)$ and $(\mathbf{B}, V)$ are concrete categories over $\mathbf{X}$ and $R:(\mathbf{B},V)\to (\mathbf{A}, U)$ is a concrete functor. Then we call $F$ to be a concrete reflector if the following holds:

for all $\mathbf{B}$-object $C$ there exists a $\mathbf{B}$-morphism $r_C:C\to R(C)$ such that $V(r_C)=id_{V(C)}$.
for all $\mathbf{B}$-objects $B,B'$ and a $\mathbf{B}$-morphsim $f:B\to B'$, $R(f)$ is the unique $\mathbf{A}$-morphism making the following diagram, $$\require{AMScd}
\begin{CD}
B @>{r_B}>> R(B);\\
@V{f}VV @VV{R(f)}V \\
B' @>>{r_{B'}}> R(B');
\end{CD}$$commute.

Definition 4. Let $(\mathbf{A},U)$ and $(\mathbf{B}, V)$ are concrete categories over $\mathbf{X}$ and $F,G:(\mathbf{A},U)\to (\mathbf{B}, V)$ be two concrete functors. Then we write $F\le G$ iff for all $\mathbf{A}$-object $A$ there exists a $\mathbf{B}$-morphism $f:F(A)\to G(A)$ such that $V(f)$ is a $\mathbf{X}$-identity.
Definition 5. Let $(\mathbf{A},U)$ and $(\mathbf{B}, V)$ are concrete categories over $\mathbf{X}$ and $F:(\mathbf{B},V)\to (\mathbf{A}, U)$ and $G:(\mathbf{A},U)\to (\mathbf{B},V)$ be two concrete functors. Then we say that $(F,G)$ is a Galois correspondence if $F\circ G\le id_{\mathbf{A}}$ and $id_{\mathbf{B}}\le G\circ F$.
Definition 6. Let $(\mathbf{A},U)$ be a concrete category A family of $\mathbf{A}$-morphisms $(A\overset{f_i}{\longrightarrow}A_i)_{i\in I}$ is said to be an initial source if for any family of $\mathbf{A}$-morphisms $(B\overset{k_i}{\longrightarrow}A_i)_{i\in I}$ and for any $\mathbf{X}$-morphism $U(B)\overset{h}{\longrightarrow}U(A)$, $$U(B\overset{g}{\longrightarrow}A)=U(B)\overset{h}{\longrightarrow}U(A)$$whenever $U(k_i)=U(f_i)\circ h$ for all $i\in I$.

REPLY [1 votes]: Let me first say that when it says embeddings of concretely reflective subcategories preserve initial sources, it means that if $A$ is a concrete subcategory of $B$ over $X$, and $E$ is the embedding $A\newcommand\into\hookrightarrow\into B$, and moreover $A$ admits a concrete reflection $R$, then $E$ preserves initial sources.
If you could prove that any embedding of $A$ into any other category preserved initial sources, just because it was a concretely reflective subcategory of some particular category $B$, then in particular, we can always realize $A$ as a concretely reflective subcategory of itself, so this would imply that all embeddings preserve initial sources. This is false, and I'm pretty sure you can come up with nice finite categories to give a counterexample.
With that said, then it should suffice to prove 6.26, and you've asked about it, so I'll give an explanation here.

Example 6.26 (2) We want to show that if $E : A\to B$ is a concrete embedding, and
$R:B\to A$ is a concrete reflector, then $(R,E)$ is a Galois correspondence.

Proof.
Let's be careful about the definition of concrete reflector. In particular, saying that we have a $B$-morphism $r_b:b\to Rb$ is actually slightly abusive of notation. $Rb$ belongs to $A$, so when we say $r_b:b\to Rb$, we actually mean $r_b:b\to ERb$. Also the requirement that $|r_b| = 1_{|b|}$ tells us that $\mathrm{id}_B\le ER$. Thus we just need to show that $RE\le \mathrm{id}_A$.
To show this, we need to use one more piece of information, that the arrows $r_b$ are $A$-reflection arrows (see definition 4.16). This implies in particular, that for all $A$-objects $a$, there is a unique $A$-morphism $s_a : REa\to a$ such that the following diagram commutes (taking great care to use the embedding $E$ explicitly):
$$
\require{AMScd}
\begin{CD}
Ea @>r_{Ea}>> EREa\\
@| @VVE s_aV
\\
Ea @>1_{Ea}>> Ea \\
\end{CD}
$$
Now when we take the underlying $X$-objects of this diagram, we get
$$
\begin{CD}
|a| @>1_{|a|}>> |a|\\
@| @VV |s_a|V
\\
|a| @>1_{|a|}>> |a|, \\
\end{CD}
$$
so $|s_a| = 1_{|a|}$. Thus the morphisms $s$ show $RE\le \textrm{id}_A$, as desired.


TITLE: Graph Theory: Simple Planar graph problem.
QUESTION [1 upvotes]: The complement of $G$ is the graph with the same vertices as $G$, but whose
edges are precisely the non-edges of $G$. (That is, $u$ is adjacent to $v$ in the complement
of $G$ if and only $u$ is not adjacent to $v$ in $G$.) Therefore, if $G^c$
is the complement of $G$,
then $E(K_{|V (G)|}
)$ is the disjoint union of $E(G)$ and $E(G^c
)$.
Show that if $G$ is a simple planar graph with at least eleven vertices, then the complement of $G$ is not planar.

REPLY [0 votes]: Hint: Remember Euler's criterion: if $G$ is a planar graph, then $\epsilon\le 3\nu-6$.


TITLE: If $\alpha$ and $\beta$ are distinct roots of the equation $p \cos(\theta) + q \sin(\theta) = r,$ then show that $\tan ((\alpha+\beta)/2) = q/p.$
QUESTION [0 upvotes]: I tried dividing both sides by $\cos$ and then squaring them. Then I converted $\sec^2(x)$ to $\tan^2(x)$ but still no luck even after substituting values.

REPLY [0 votes]: $$p(\cos\beta-\cos\alpha)=q(\sin\alpha-\sin\beta)$$
Now apply this


text:
\section{Hierarchical Matrices}
\label{sec:hmat}

As discussed in \secref{sec:IGABEM_collocation}, the system matrices are fully populated and hence, the required storage scales $\order(n^2)$ with the number of degrees of freedom $n$. The same holds for the effort of the involved matrix-vector operations in order to solve the system of equations. In this work, the concept of \hmatrices{} is applied to the isogeometric BEM formulation previously described.

\hmatrices{} have been introduced by \citet{hackbusch1999} as a general matrix format and applied to the BEM in \cite{boerm2003}. It allows the storage of fully populated matrices with
\revdel{almost linear complexity}{}
\revadd{an asymptotic complexity of}{}
 $\order( n \log n )$. Moreover, no further information on the underlying problem is needed after construction of a \hmatrix{}. If the matrix is based on adaptive cross approximation (ACA) introduced by \citet{bebendorf2000}, the underlying physics is also not important for the construction. ACA is a black-box algorithm and hence, has become very popular. Its applicability covers many different problems.
In the context of the presented formulation, the extension to the elasto-static \cite{bebendorf2006} and elasto-plastic BEM~\cite{zechner2013} is of particular interest.

\subsection{Matrix Approximation }

The reduced complexity of the \hmatrix{} format stems from the low rank approximation of separate blocks $\mat{M}$. It is well known, that the singular values of $\mat{M}$ which is constructed by evaluation of \emph{asymptotically smooth} functions ${\Phi(\pt{x}-\pt{y})}$ decay exponentially if the variables $\pt{x}$ and $\pt{y}$ are well separated. Hence, a degenerated function may be used instead of the original one. To a certain degree of accuracy, the resulting matrix block has numerically low rank \cite{hackbusch2009}. The same holds if matrix entries consist of boundary integrals such as \eqref{eq:BIEdisEntries}. If applicable, $\mat{M}$ may be represented as low rank matrix ($\rk$-matrix) in factorised form
\begin{equation}
\label{eq:low-rank-representation}
\begin{aligned}
  \mat{M}\approx\mat{R}_k = \mat{A} \mat{B}^\trans
\end{aligned}
\end{equation}
with $\mat{M}\in\R^{m\times n}$, $\mat{A}\in\R^{m\times k}$ and $\mat{B}\in\R^{n\times k}$. If ${k\ll \min(m,n)}$ the storage requirement of $\mat{R}_k$ is considerably reduced compared to the full matrix $\mat{M}$. The number of floating point operations when performing for example matrix-vector multiplication is also reduced.

In this work, ACA is used for the construction of $\rk$-matrices, which is one of the most efficient rank-revealing algorithms available. The construction of $\mat{A}$ and $\mat{B}$ is performed by evaluating chosen rows $\vek{a}_i$ and columns $\vek{b}_j$ of the original matrix block $\mat{M}$. This is the basis for the black-box characteristics of the algorithm.
Which row- or column-indices are used is controlled by the evaluation of pivot points, typically
the argument of maximum for the coefficients of a row or column.

\Figref{fig:aca} depicts the construction of a low rank representation by means of the ACA algorithm and shows the reduction of storage of the $\rk$-matrix. Ideally, the number of evaluated rows and columns of the original matrix $\mat{M}$ should be small. How many evaluations are necessary, is controlled by a user-defined approximation quality $\err_{\h}$. As a consequence, the rank $k$ of the approximation is adaptively determined using the criterion

\begin{align}
  \label{eq:aca_stop}
  \| \vek{a}_{k+1} \|_F \cdot \| \vek{b}_{k+1} \|_F \leq
  \err_{\h} \| \vek{R}_k \|_F && \text{with} &&
  \vek{R}_k = \sum_{\nu=1}^k \vek{a}_\nu \vek{b}_\nu^T
\end{align}

which uses measures in the Frobenius norm $\| \bullet \|_F$.
The reader is referred to \cite{bebendorf2000} for details of the standard algorithm. The improved ACA+ algorithm used in this work is explained in \cite{grasedyck2005}.

\tikzfig{tikz/aca}{1.0}{Construction of a low rank matrix $\mat{R}_k$ by ACA}{aca}{figure06}

For problems described by the Lam\'{e}-Navier equation, the fundamental solution is a tensor and therefore vector-valued in each direction. In the context of smoothness, a straight forward assembly of vector valued entries into $\mat{M}$ violates this requirement. Nevertheless, ACA will not fail since the algorithm still reveals the rank of the block, or at least the full rank. But the singular values might not decay exponentially, and thus the rank and the calculation time increase. To overcome this remedy, Cauchy data are decomposed by means of their spatial direction \cite{bebendorf2006,zechner2013} resulting in
\begin{equation}
  \begin{aligned}
    \label{eq:resorting-vectors}
    \tilde{\vek{u}} := &
    \begin{pmatrix}
      \left[ \tilde{\utens}_{1,n} \right]_{n=1}^{N_u} & \dots & \left[ \tilde{\utens}_{d,n} \right]_{n=1}^{N_u}
    \end{pmatrix}^\trans
    \und \\
    \tilde{\vek{t}} := &
    \begin{pmatrix}
      \left[ \tilde{\ttens}_{1,n} \right]_{n=1}^{N_t} & \dots & \left[ \tilde{\ttens}_{d,n} \right]_{n=1}^{N_t}
    \end{pmatrix}^\trans
  \end{aligned}
\end{equation}
for a number of points $N_u$ and $N_t$ in consideration. Consequently, this leads to a block-wise representation
\begin{align}
  \label{eq:block-representation}
  \mat{V} =
  \begin{pmatrix}
    \mat{V}_{11} & \dots & \mat{V}_{1d} \\
    \vdots & \ddots & \vdots \\
    \mat{V}_{d1} & \dots & \mat{V}_{dd}
  \end{pmatrix}\beistrich &&
  \mat{K} =
  \begin{pmatrix}
    \mat{K}_{11} & \dots & \mat{K}_{1d} \\
    \vdots & \ddots & \vdots \\
    \mat{K}_{d1} & \dots & \mat{K}_{dd}
  \end{pmatrix} &&
\end{align}
for the discrete single and double layer operator in $d$ dimensions. Each sub-matrix now contains scalar values based on smooth kernels and ACA can be applied efficiently.

\subsection{Geometrical Bisection}

As mentioned in the previous section, matrix approximation is based on the fact that for asymptotically smooth integral kernels, matrix blocks related to well separated variables $\pt{x}$ and $\pt{y}$ have low rank. A partition of the system matrices with respect to the geometry is thus needed. This means that indices of matrix rows $i\in I$ and columns $j\in J$ are resorted in such a way that their offset corresponds somehow to their geometric distance. The splitting is done block-wise and matrix blocks assigned to be \emph{near field} or \emph{far field}. For the latter type the variables are far away enough from each other and hence, the matrix block is a candidate for approximation.

In the context of \hmatrices{}, this procedure is termed clustering. The geometric properties of row and column indices are defined in two binary cluster trees $\ct$. The procedure is carried out in the following way: first, each index $i$ and $j$ is labelled with a characteristic point. In this formulation this is the collocation point $\pt{x}_i$  or the anchor $\pt{y}_j$ of the NURBS basis function, i.e. $\varphi_j$ as used in \eqref{eq:ansatzDispl}. Second, an axis parallel bounding box $Q$, which includes the support of the corresponding index is generated. For row indices, the box degenerates to a point $Q_i=x_i$, for column indices $Q_j=\supp\{\varphi_j\}$. \revmod{Based upon different strategies, the geometrical bisection which defines the structure of the cluster trees is performed \protect\cite{hackbusch2009,bebendorf2008}}{location of references has been changed}. In the following explanation, the creation of a \emph{geometrically balanced} cluster tree for the row indices $i\in I$ is demonstrated.

Covering all local boxes $Q_i$, a bounding box $B_0^0$ aligned to the initial axis is constructed. In the next step, $B_0^0$ is halved by a cutting plane defined with respect to the direction of its largest extension. The result is now two boxes $B_0^1$ and $B_1^1$, which are then minimised with respect to all $Q_i$ contained within. In the corresponding cluster tree $\ct$, this defines the clusters $t_0^1$ and $t_1^1$ as sons of the root cluster $t_0^0$. The superscript denotes the level $\ell$ in the tree $\ct$ and the subscript is an unique number which relates $B$ and $t$ of the same level. The bisection is continued recursively until
\begin{equation}
  \label{eq:min_leafsize}
  \mathrm{size}( t ) = \# t \leq n_{min}
\end{equation}
is fulfilled, which is characterised by the minimum leaf size $n_{min}$ related to the desired minimal amount of indices in a cluster $t$. The whole procedure is depicted in \figref{fig:clustering} for the minimum leaf size $n_{min}=2$. It can be seen that the diameters of boxes $B$ shrink quickly with increasing level.

\tikzfig{tikz/clustering}{0.95}{Geometrically balanced clustering for collocation points on a circular geometry and a minimum leaf size $n_{min}=2$.}{clustering}{figure07}

The same operations are performed for the column cluster tree~$s$, except for the fact that $Q_j$ are now influenced by the support of the assigned NURBS basis function. To provide a reliable bounding box, B\'{e}zier segments are constructed  and the \emph{convex hull} of the resulting control grid is taken. As an example the process is described for a cubic NURBS curve.

The geometry and its control grid is outlined on top of \figref{fig:hull}. The knot vector for the geometry description is defined by $\varXi_\theta=\{ 0,0,0,0,2,4,4,4,4 \}$. Adapted from $\varXi_\theta$, the knot vectors for traction $\varXi_\psi=\{ 0,0,0,0,1,2,3,4,4,4,4 \}$ and displacement field $\varXi_\varphi=\{ 0,0,0,0,0,2,2,4,4,4,4,4 \}$ are defined. Knot vector $\varXi_\psi$ has been subject to knot insertion and $\varXi_\varphi$ to order elevation. The entries of all knot vectors are now accumulated to $\varXi_h$.
Since geometrical information only is sought, the order of $\varXi_h$ is equal to the order of the geometry description. The B\'{e}zier segments are constructed by means of knot insertions as described in \secref{sec:IGABEM}.
As a result $\varXi_h = \{ 0,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,4 \}$.
The corresponding B\'{e}zier segments are depicted on the bottom of \figref{fig:hull}. The resulting control points represent a convex hull of the NURBS curve. Hence,
a bounding box is generated easily by taking the control points of B\'{e}zier segments related to the support of the considered basis function. For instance, the dashed box in \figref{fig:hull} depicts $Q_1$ for the first basis function $\psi=R_{0,3}$ of the traction description. Whereas $Q_2$ is the bounding box for the support of $\varphi=R_{6,4}$ for the description of displacements.

\tikzfig{tikz/convexhull}{0.9}{Cubic NURBS curve with its control grid (top) and B\'{e}zier segments (bottom)
  determined by the knot vector for the convex hull $\varXi_h$. The
  dashed boxes $Q_1$ and $Q_2$ denote the bounding box for the support of selected NURBS basis functions describing tractions (red) or displacements (green) respectively.}{hull}{figure08}

The structure of a \hmatrix{} is then defined by the block cluster tree $\bct$ and its nodes ${b = t \times s}$. These nodes contain row- and column-indices taken from the corresponding clusters in the same level $\ell$. The level-wise treatment is not mandatory but reduces the numerical effort. The block cluster tree for off-diagonal matrices in the block system~\eqref{eq:BIEdis} is in fact constructed inhomogeneously by checking admissibility in different levels of the row and column cluster trees. This is because the number of total row or column indices may be relatively unbalanced. An inhomogeneous clustering equilibrates the size of matrix blocks in the \hmatrix{} and thus improves the approximation with ACA.

Efficiency for the evaluation of distances and diameters is the reason for taking axis-aligned bounding boxes for $Q$ and $B$.
The block cluster tree is a quad tree and forms the basis for the structure of a \hmatrix{}.
An example for the level-wise definition of the matrix structure is depicted in \figref{fig:blockcluster}.
Starting from $\ell=0$, for each node $b$ an admissibility condition
\begin{equation}
  \label{eq:admissibility-condition}
  \min ( diam(B_t), diam(B_s) ) \leq \eta dist(B_t,B_s)
\end{equation}
is checked \cite{boerm2003}. The variable $\eta$ is called admissibility factor and ranges from $0 < \eta \leq 1$. In effect, the admissibility factor controls the number of $\rk$-matrices: the higher $\eta$ the more admissible blocks are obtained. In \figref{fig:blockcluster} these blocks are coloured green and therefore denote the far field. For red matrix blocks the level in $\bct$ is increased as long as either the row or column cluster is a leaf. Finally, the remaining red blocks not fulfilling \eqref{eq:admissibility-condition} are full matrices and define the near field. These matrix blocks are evaluated with standard BEM techniques whereas far field matrix blocks are $\rk$-matrices to be constructed with ACA.

\tikzfig{tikz/blockcluster}{1.0}{Matrix partition into blocks defined
  by the block cluster tree $\bct$ up to level $\ell=3$}{blockcluster}{figure09}

\subsection{Matrix Operations and Solver}

Compared to other fast methods, \hmatrices{} allow many more matrix operations than merely the matrix-vector multiplication. For example, $LU$ and $QR$ factorization and even inversion are carried out with
\revdel{almost linear complexity, too}{}
\revadd{linear complexity up to a logarithmic factor}{} \cite{grasedyck2003}. Of course the accuracy of results is determined by the accuracy of the matrix approximation $\err_{\h}$ itself. For a detailed complexity analysis of operations on and with \hmatrices{}, the reader is referred to \cite{hackbusch2009}.

The complexity of operations is also determined by depth of the underlying block cluster tree. It has been shown by \citet{grasedyck2005}, that after construction the structure of the \hmatrix{} can be coarsened. This is due to the fact that the admissibility parameter $\eta$ could be larger than chosen and that condition \eqref{eq:admissibility-condition} might be sufficient but not necessary. Coarsening yields reduced complexity for matrix operations and less storage requirements as well. In addition, the described approach makes use of the fact that $\rk$-matrices may be re-compressed with only slight additional effort. While a singular value decomposition (SVD) on full matrix blocks is inefficient, it is affordable for the outer product format of $\rk$ matrices. With the help of a truncated SVD, the rank and thus the storage requirement can be reduced further.

The coefficient matrices in \eqref{eq:BIEdis} are ill-conditioned if the number of unknowns becomes very large.
Thus, special care has to be taken in the solution procedure carried out by \hmatrices{} for large scale computations. As mentioned before, computing the inverse or a $LU$ factorization leads to
\revdel{almost linear computational complexity}{}
\revadd{linear complexity up to a logarithmic factor}{}. Hence they can be computed in reasonable time, especially when the approximation error for the particular factorisation is set to a relatively high value, i.e. $\err_\h=10^{-1}$.
\revdel{For that reason these factorisations can be used as a spectrally equivalent preconditioner for the purpose of solving {\eqref{eq:BIEdis}} iterative with a suitable Krylov subspace method such as GMRES \protect{\citep[see][]{zechner2012b}}.}{}
\revadd{In the presented implementation, the system of equations is left-preconditioned by such a data-sparse, spectrally equivalent $LU$ factorisation and then solved iteratively with GMRES. For further details on the solution strategy implemented in the described formulation the reader is referred to \protect\cite{zechner2012b}.}{Remark to describe the solution strategy and refer to another paper}

config: arxiv


TITLE: Given $\mathbb E(5X+2)=12$ and $\mathbb E(X|Y)=Y^3$ compute $\mathbb E(Y^3)$
QUESTION [4 upvotes]: Given $\mathbb E(5X+2)=12$ and $\mathbb E(X|Y)=Y^3$ compute $\mathbb E(Y^3)$.
I've been trying this a million different ways and can't seem to reach a final answer, I would love any suggestions!

REPLY [2 votes]: $E[X] = 2$.
Since $E[ X|Y] = Y^3$, then $E[Y^3] = E[ E[X|Y]] = E[X] = 2$.


TITLE: Find the eigenvalues and eigenfunctions of the Sturm-Liouville problem $x^4 y'' + k^2 y = 0$
QUESTION [0 upvotes]: Find the eigenvalues and eigenfunctions of the Sturm-Liouville problem
$x^4 y'' + k^2 y = 0$
$y(\alpha) = y(\beta) = 0$, $\hspace{0.4cm}0 < \alpha < \beta$
For this problem I need to find the eigenvalues and the eigenfunctions. Originally the problem has variable coefficients, so I think I can transform the problem to the form $v'' + k^2 v = 0$. I think this is possible by doing a change of variable, which one? I'm familiar with problems that have the form $y'' + \lambda y = 0$. In these cases, to find the eigenvalues and eigenfunctions is simply to consider the cases where $\lambda <0$ or $\lambda = 0$ or $\lambda> 0$. However, I have had difficulty finding the eigenvalues and eigenfunctions for this problem posed here. How can I do this? I appreciate any help

REPLY [3 votes]: $$x^4 y'' + k^2 y = 0$$
$$x^2 y'' + \dfrac {k^2}{x^2} y = 0$$
Z Ahmed's answer is correct substitute $w=\dfrac 1x$:
$$y'=-w^2\dfrac {dy}{dw}$$
$$y''=2w^3 \dfrac {dy}{dw}+w^4 \dfrac {d^2y}{dw^2}$$
The DE becomes:
$$wy''+2y'+k^2wy=0$$
$$(wy)''+k^2wy=0$$
Which is the form  you wanted:
$$v''+k^2v=0$$
Where $v=wy=\dfrac yx$.


TITLE: What does a topology tell you about the relationship between its elements?
QUESTION [2 upvotes]: I'm new to topology, and I'm having some trouble. I understand that a donut and a mug have the same topology. In my intuition, that is because one of them can be stretched into the other, and all the points will still be connected to each other the same way as they were before(don't know if "connected" is the right term). What I don't seem to get my head around, is how a topology is giving you this info, about how the elements in a set are related/connected (if you can use that term). If I have the set $X = \{a, b, c, d\}$ with the topology $t = \{\{\}, \{a, b\}, \{a, b, c\}, \{a, b, c, d\}\}$, how do you interpret $(X, t)$ to know which elements are related/connected? I can't seem to find any information about how you really interpret a topology. Like what does a topology really tell you about the relationship of the elements in its sets? Is this a valid question, or am I missing something fundamental?

REPLY [2 votes]: I meant for this to be a comment, but it got a little bit long so I'm leaving it here. If anyone wants to add a more comprehensive answer, or expand on this one, they should feel free to.

Topology tells you what elements are "close to" each other, while avoiding a notion of "distance". It does this by providing a notion of open set, where if $x \in U \subseteq V$, we can think of elements in $U$ being "closer to $x$" than elements of $V \setminus U$. The intuition you want to have here is related to the open balls of a metric space. If we forget about the actual distance on $\mathbb{R}$, we can still remember that points in $(-1,1)$ are closer to $0$ than points in $(-2,2)$.
Closed sets too, provide "closeness" information. If $x \in \overline{A}$, that is, the closure of $A$, then $x$ is "almost in $A$". The picture to have in mind here is $A = \{ (x,y) ~|~ x^2 + y^2 < 1 \}$. The point $(2,2)$ is somehow "less in $A$" than the point $(1,0)$, even though both aren't in $A$. With naked sets, we cannot make this intuition precise, but with a topology, we can. The point $(1,0)$ may not be in $A$, but it is in $\overline{A}$. No matter how close to $(1,0)$ we want to get (as measured by open sets), we can always find a point that is close enough and also in $A$.
As an aside, we can dualize this argument. If we work with $B = \{(x,y) ~|~ x^2 + y^2 \leq 1\}$, then
the point $(1,0)$ is somehow "less in $B$" than the point $(0,0)$. This is topologically expressed by $(0,0)$ being in the interior of $B$. We know $(0,0)$ is REALLY in $B$ because we can find a set of points close to $(0,0)$ (again, measured by an open set) where every point which is close enough is also in $B$.
As a test of understanding, you should take the standard definitions of interior and closure and show they align with the intuition I've given above.
"But", I hear you asking, "what about rubber-sheet geometry?" A circle and a square are homeomorphic (i.e., topologically the same) because you can find a bijection which respects "closeness" in each direction. By stretching the square into a circle, points which start close together stay close together, though the concrete distance between points changes. However, a circle and a filled in circle (i.e. a disk) are not homeomorphic because either you must tear the disk (and so points that started close together end far apart) or you must glue the circle to itself (so that the inverse function involves tearing).
Finally, to address the four point space you brought up, I have this (perhaps controversial) opinion: Finite topological spaces are interesting in their own right, but they aren't very good for building intuition. They CERTAINLY aren't good for working with intuition you may have about rubber-sheet geometry. It is somewhat unfortunate that a first course in topology is typically obsessed with pathologies and problematic spaces. There is good reason to do this! Knowing about pathologies is useful for understanding what can go wrong, and tempering the intuition that working with metrizable spaces for too long will give you. Topology is also incredibly useful outside of geometry, and the material of a point set topology class is extremely relevant to analysis.
This focus, however, obscures the connection between geometry and topology that many of us were promised by pop-math articles. Once you take a course in Algebraic Topology, you will see the connections you are hoping for (provided you have a good professor, of course).
If you want a jump-start on this material, I cannot recommend the book "A combinatorial introduction to topology" by Michael Henle highly enough. It is accessible without much background, and explains algebraic topology in a very polite way, while still managing to hit some fairly advanced material.

I hope this helps ^_^


TITLE: What’s going on when I restrict a homomorphism to a smaller quotient group?
QUESTION [1 upvotes]: I have $N\lhd G$, $K\lhd G$ and $N\le K$. Let $f:G\rightarrow H$ be a homomorphism with kernel $K$. I want to write $f$ as a composition $h\circ\pi$ where $\pi:G\rightarrow G/N$ is the projection and $h:G/N\rightarrow H$ is a homomorphism.
To get $h$, I can just map $gN$ to $f(g)$ because if $gN=rN$ then $f(g)=f(r)$. What’s actually happening in the last sentence abstractly in terms of the homomorphisms/projections involved?
We needed to use that $N\le K$ to say this.

REPLY [0 votes]: What you wrote in your sentence "To get $h$" is an exactly correct abstract description of the homomorphism. If what you wanted was to break up the (exactly correct) implication "if $gN=rN$ then $f(g)=f(r)$" into a few more steps of set theoretic logic then you could write something like this:

If $gN=rN$ then $gN=rN = gN \cap rN \subset gK \cap rK$. It follows that $gK \cap rK \ne \emptyset$, and therefore $gK=rK$, so $f(g)=f(r)$.


TITLE: Existence of a smooth compactly supported function
QUESTION [4 upvotes]: Let $U$ be a bounded domain in $\mathbb R^n$. Does there exist a smooth function $f$ with compact support in $U$ such that:
$$ \| f\|_{W^{k,\infty}(U)} \leq (k!)^{2-\epsilon},$$
for some $\epsilon>0$?
Thanks,

REPLY [15 votes]: The answer is yes if $\epsilon<1$, and no when $\epsilon\geq 1$.
This follows from Carleman's quasianalyticity criterion, see for example, Hormander, Analysis of linear partial differential operators, Vol. I, Chap I, Section 1, Theorem 1.3.8.
(Carleman's original proof used Complex Analysis, and it was reproduced in the books on the subject. Hormander has an elementary proof, not using Complex Analysis. As far as I know, this proof was first published in the book I refer to).


TITLE: Definition of the ring of differentiable maps $C^\infty(M)$, where $M$ is a differentiable manifold
QUESTION [1 upvotes]: Let $M$ be a differentiable manifold. We define the set $C^{\infty}(M) := \{f : M \to \mathbb{R} \text{ differentiable}\}$.
We can endow this set with a ring structure considering the common sum of functions:
$$(f+g)(p) := f(p)+g(p)$$
and the product (instead of the composition):
$$(fg)(p) := f(p)g(p)$$
So, the neutral element for $+$ is the constant map zero, and the neutral element for the product is the constant map $1$ or the identity map? (then is a domain?)
Or we consider $(C^{\infty}(M),+,\circ)$ with $\circ$ the composition of differentiable maps?
Thanks.

REPLY [1 votes]: $M$ is an arbitrary differentiable manifold, so the "identity map" does not make sense unless $M$ itself is $\mathbb{R}$. So, the multiplicative identity is the constant map $1$.
Again, since $M$ is an arbitrary differentiable manifold, composition does not necessarily make sense. It only makes sense if $M = \mathbb{R}$. So, composition cannot in general define a multiplication on $C^\infty(M)$.
The question

(then is a domain?)

does not make sense to me. Are you perhaps asking if $C^\infty(M)$ is an integral domain? If so, the answer is no, and it is a good exercise to find two nonzero smooth functions on $M$ whose product is the zero function.


TITLE: What is the significance of Einsteins postulate on speed of light?
QUESTION [0 upvotes]: Einstein postulated that the speed of light in free space
is the same for all observers, regardless of their motion
relative to the light source, where we may think of an
observer as an imaginary entity with a sophisticated set
of measurement devices, at rest with respect to itself,
that perfectly records the positions and times of all
events in space and time.
It is really exciting to understand Einsteins thoughts. I have a doubt with respect Einsteins above postulate,

Is there any significance in saying an observer as an imaginary entity? I thought light could be called as some thing imaginary, rather than calling observer as an imaginary entity.
What does it mean one being at rest with respect to one self? I think it mean that, observer is not under motion due to its own virtue, but the observer may be under motion, if considered inside a moving frame of reference. I don't know whether I am right with respect to this, if I have misunderstood, please explain.
Why is speed of light considered same for all observers (imaginary entity which is at rest with respect to itself) regardless of their motion relative to the light source? I thought, if we consider observer inside a moving frame of reference, speed of light should be different for the observer, due to relative motion with respect to light.

REPLY [3 votes]: Is there any significance in saying an observer as an imaginary
  entity?

Yes.  From Wikipedia:

Physicists use the term "observer" as shorthand for a specific
  reference frame from which a set of objects or events is being
  measured. Speaking of an observer in special relativity is not
  specifically hypothesizing an individual person who is experiencing
  events, but rather it is a particular mathematical context which
  objects and events are to be evaluated from. The effects of special
  relativity occur whether or not there is a sentient being within the
  inertial reference frame to witness them.

Thus, we must be careful to understand that what is observed, as the term is used in the context of special relativity, is not to be confused with what is seen by a localized being.

What does it mean one being at rest with respect to one self?

It means that one is not moving relative to one's reference frame.  This is a tautology.

speed of light should be different for the observer, due to relative
  motion with respect to light.

Empirically, the two-way speed of light is the same for all observers.  It turns out that the one-way speed of light is not physically meaningful.  This is because two spatially separated synchronized clocks must be used in one-way measurement.
Einstein's invariance of light speed postulate is, operationally, the selection of an synchronization convention.  Again, from Wikipedia:

It is only possible to verify experimentally that the two-way speed of
  light (for example, from a source to a mirror and back again) is
  frame-independent, because it is impossible to measure the one-way
  speed of light (for example, from a source to a distant detector)
  without some convention as to how clocks at the source and at the
  detector should be synchronized. However, by adopting Einstein
  synchronization for the clocks, the one-way speed of light becomes
  equal to the two-way speed of light by definition.[14][16] The special
  theory of relativity explores the consequences of this invariance of c
  with the assumption that the laws of physics are the same in all
  inertial frames of reference.[17][18] One consequence is that c is the
  speed at which all massless particles and waves, including light, must
  travel in vacuum.


TITLE: Use Rodrigues' formula to derive the following property for legendre polynomial
QUESTION [0 upvotes]: The Rodrigues' formula says: $\phi_{0}(x)=1$, $\phi_n(x)=\frac{((x^2-1)^n)^{(n)}}{2^nn!}$ $\forall n\geq 1 $
where $\phi_n$ is the $n^{th}$
Legendre Polynomial
and I have already derived:  $\phi'_n(x)=x\phi'_{n-1}(x)+n\phi_{n-1}(x)$
How do I show:
$$\phi_n(x)=x\phi_{n-1}(x)+\frac{x^2-1}{n}\phi'_{n-1}(x)$$

REPLY [0 votes]: See my other post dated yesterday: [Differentiate $((x^{2}-1)f_{n-1}(x))^{(n)}$. ]
Note that there I used two other well-known properties of Legendre polynomials:
\begin{equation}
(n+1)P_{n+1} = (2n+1)xP_n-nP_{n-1}
\end{equation}
and
\begin{equation}
P_{n+1}'-P_{n-1}' = (2n+1)P_n
\end{equation}
Also note that the derived formula is slightly different than what you mentioned:
$$\frac{x^2-1}{n}P_n' = xP_n - P_{n-1}$$
But you can easily derive the formula you are looking for as follows:
$$(x^2-1)P_n' = nxP_n - nP_{n-1} = (n+1)P_{n+1} - (n+1)xP_n$$
hence
$$\frac{x^2-1}{n+1}P_{n}' = P_{n+1} - xP_n$$
replacing $n$ by $n-1$ then gives:
$$\frac{x^2-1}{n}P_{n-1}' = P_{n} - xP_{n-1}$$
As required.


TITLE: LSZ reduction derivation Srednicki
QUESTION [2 upvotes]: In the derivation of the LSZ reduction formula equation (5.21) Srednicki claims that in case of an interaction term in the Lagrangian density $a^{\dagger}(\textbf{k})$ will no longer be time dependent. Now does that mean that the only modification to the formula of $\varphi(x)$ will be a time dependence of $a$'s and $a^{\dagger}$'s? So is that like an ansatz we use for $\varphi(x)$? Now even if we do assume this form of $\varphi(x)$, in line two of the derivation he makes the substitution $$a^{\dagger}(\textbf{k},t)= -i \int\:d^3x \:[e^{ikx} \partial_0\varphi(x) - e^{ikx} ik_0 \varphi(x)]\tag{5.2}.$$ Now in the derivation of this formula if we remember we explicitly had to use the time independence of the $a$'s. So what am I missing in this derivation that justifies the substitution in the case the $a$'s are time dependent?

REPLY [0 votes]: That expression is time independent. Try taking the time derivative, being sure to use the equation of motion for $\varphi(x)$, also notice that the plane wave $e^{ik\cdot x}$ satisfies the same equation of motion.


TITLE: Let $A$ be a non-zero linear transformation on a real vector space $V$ of dimension $n$.
QUESTION [1 upvotes]: Let $A$ be a non-zero linear transformation on a real vector space $V$ of dimension $n$. Let the subspace $V_0 \subset V$ be the image of $V$ under $A$. Let $k = \dim (V_0) \lt n$ and suppose that for some $\lambda \in \mathbb{R}$, $A^2 = \lambda A$. Then which of the following are true?

$\lambda = 1$
$\det(A) = |\lambda|^{1/n}$
$\lambda$ is the only eigenvalue of $A$
There is a nontrivial subspace $V_1 \subset V$ such that $Ax = 0$ for all $x \in V_1$

I am able to say that 4 is true as $\operatorname{rank}(A) < n$. 2 is false by using the determinant function on both sides. Using the argument used for 4, 0 is also an eigenvalue. So 3 is also false.
But I want to know what we can say about $\lambda$. Is is an eigenvalue? Is it equal to 1?

REPLY [0 votes]: Let $A$ be a matrix of order $2 \times 2$ with all entries equal to $1$. Then $A^2 = 2A$ and the eigenvalues of A are $0$ and $2$. Using this example, options $1$, $2$ and $3$ can be discarded.


TITLE: Proving an integral of products of a function is equal to a regular integral.
QUESTION [0 upvotes]: Given $f \in C([a,b])$, we also define $V= \{x\in \mathbb{R}^n | a\leq x_1 \leq x_2 \leq \cdots \ x_n \leq b \} .$
Now, I want to solve the following equation:
$$ \int_V \prod_{1\leq j \leq n} f(x_j) dx= \frac{1}{n!}\left( \int_a^b f(t)dt)\right). $$
I have shown this to be true for $n=1$ and $n=2$, and so I thought that perhaps I should use induction to prove the whole equation to be true. However, I wasn't able to figure out how to apply the inductive step to this integral. Any help in solving this would be greatly appreciated.

REPLY [2 votes]: If I understand your notation, it is not a true identity, for $n=2$, $f(x)=x$, $a=0$, $b=1$
$$
\int_0^1 \int_0^x xy\,dy   \,dx=\frac1{2!}\int_0^1 x^3\,dx=\frac1{2!4}\neq \frac 1{2!2} = \frac 1{2!}\int_0^1 x\,dx.
$$

REPLY [1 votes]: I'm afraid its just not true. Pick $f=1$ and $b=1$ and $a=-1$, then
$$\int_a^bf(t)\, dt= 2 \mbox{ and } \int_V1dx=(b-a)^n=2^n.$$
Hence
$$2^n=\frac{2}{n!},$$
which is not true. What you may want to look into is Fubini's Theorem. It yields
$$\int_V\Pi_{j}f(x_j)dx=\Pi_j\int_a^b f(t)\, dt= (\int_a^bf(t)\, dt)^n$$


text:
{\bf Problem.} The distribution of populations in a group of counties is shown in this pie chart. What percent of the counties have fewer than 100,000 residents?

[asy]
draw(Circle((0,0),25),linewidth(1));
draw((-24,-7)--(0,0)--(24,-7),linewidth(1));
draw((0,0)--(7,-24),linewidth(1));
label("59\%",(0,12));
label("25\%",(-10,-10));
label("16\%",(10,-10));
label("\textbf{Distribution of County Populations}",(0,25),N);
label("\tiny{10,000 to 99,999}",(30,15),N);
label("\tiny{less than 10,000}",(-30,-15),S);
label("\tiny{100,000 or more}",(30,-15),S);
label("\tiny{residents}",(30,13),N);
label("\tiny{residents}",(-30,-17),S);
label("\tiny{residents}",(30,-17),S);
[/asy]
{\bf Level.} Level 2
{\bf Type.} Prealgebra
{\bf Solution.} This is the percent that has either fewer than 10,000 or 10,000 to 99,999 residents, so we add those two percentages, giving $25\%+59\%=\boxed{84\%}$.

set_name: MATH


TITLE: Law of total expectation well-defined?
QUESTION [1 upvotes]: Wikipedia states that this is a special case of the law of total expectation click me.
Given a partition $A_1,...,A_n$ of the outcome space, we have for a random variable $X$ that
$E(X)=\sum_{i=1}^{n} E(X|A_i)P(A_i).$
Now, I know how $E(X|\mathcal{G})$ is defined for a sigma-algebra, but I don't know what the definition of $E(X|A_i)$ is or more precisely, whether we can view it as a special case of $E(X|\mathcal{G})?$

REPLY [1 votes]: $\Bbb E[X|A_i]$ means $\Bbb E[X1_{A_i}]/\Bbb P[A_i]$--the "elementary" conditional expectation. This notion is linked to $\Bbb E[X|\mathcal G]$ when $\mathcal G=\sigma(A_1,A_2,\ldots,A_n)$. In this case
the random variable $\Bbb E[X|\mathcal G]$ is equal to
$$
\sum_{i=1}^n 1_{A_i}\Bbb E[X|A_i],
$$
and your Law of Total Expectation is related to the Law of Iterated Expectations : $\Bbb E[\Bbb E[X|\mathcal G]]=\Bbb E[X]$.


TITLE: How can I prove that the perimeter is at most 60?
QUESTION [2 upvotes]: Problem: Let $\Delta$ be a triangle in the plane. Let $P$ be the perimeter of the triangle and $A$ be the area. Let $a,b,c$ be the length of the sides and suppose they are positive integers. Suppose finally that $A=P$. How can I prove that $P \leq 60$?
My attempt: I tried using Erone's formula getting:
$$a+b+c = \sqrt{\frac P 2 \left(\frac{P}{2}-a\right)\left(\frac P 2-b\right)\left(\frac P 2 - c\right)}$$
from which I obtained:
$$4P=-P^3 + 4 (a^2b+a^2c+ab^2+b^2c+ac^2+bc^2+abc)$$
and I noticed that $abc \leq \left(\frac{P}{2}\right)^2$ but I am not able to continue. Any help will be appreciated.
Remark: as suggested in the comments, defining $u=a+b-c$, $v=a+c-b$ and $w=b+c-a$ we get $16(u+v+w)=uvw$.
Noticing that $uvw$ should be even and that none of $u,v,w$ can be odd we can write $u=2k$, $v=2h$, $w=2n$ in such a way we deduce $4(k+h+n)=khn$.

REPLY [1 votes]: $$hnk=4(h+n+k), h,n,k\in\mathbb{N}$$
$$(hk-4)n=4(h+k)$$
WLOG $h\geq n \geq k > 0$. Then
$$(hk-4)k \leq 4(h+k) \Rightarrow hk^2-8k \leq 4h \Rightarrow hk^2-8h\leq 4h\Rightarrow hk^2\leq12h\Rightarrow k\leq 3$$
$$n=\frac{4(h+k)}{hk-4}$$
At $k=1$:
$$n=\frac{4h+4}{h-4}=4+\frac{20}{h-4}$$
$$h+n+k=h+5+\frac{20}{h-4}=9+(h-4)+\frac{20}{h-4}$$
$$(h-4)|20 \Rightarrow (h-4)+\frac{20}{h-4}\leq 21 \Rightarrow h+n+k\leq 30$$
At $k=2$:
$$n=\frac{4h+8}{2h-4}=2+\frac{8}{h-2}$$
$$h+n+k=h+4+\frac{8}{h-2}=6+(h-2)+\frac{8}{h-2}$$
$$(h-2)|8 \Rightarrow (h-2)+\frac{8}{h-2}\leq 9 \Rightarrow h+n+k\leq 15$$
At $k=3$:
$$n=\frac{4h+12}{3h-4}=1+\frac{h+16}{3h-4}$$
$$n\geq k=3 \Rightarrow \frac{h+16}{3h-4}\geq 2\Rightarrow h+16\geq 6h-8 \Rightarrow h\leq \frac{24}{5}<5$$
$$h\leq 4\Rightarrow h+n+k\leq 4+4+3=11$$
Then $h+n+k\leq 30$ in all possible cases.
Perimeter of triangle $$P=a+b+c=u+v+w=2(h+k+n)\leq 60$$


text:
\begin{document}
\Large
\title{Transcendental ending laminations}
\author{Ian Agol}
\address{Department of Mathematics, University of Illinois at
Chicago, 322 SEO m/c 249, 851 S. Morgan Street, Chicago, IL
60607-7045}

\keywords{Kleinian group, transcendental}

\email{agol@math.uic.edu}
\thanks{Partially supported by NSF grant DMS 0204142 and the Sloan
Foundation}

\begin{abstract}
Yair Minsky showed that punctured torus groups are classified by a
pair of ending laminations $(\nu_-,\nu_+)$. In this note, we show
that there are ending laminations $\nu_+$ such that for any choice
of $\nu_-$, the punctured torus group is transcendental as a
subgroup of $\PSL_2\CC$.
\end{abstract}

\maketitle

\section{Introduction}
We investigate in this note the algebraic properties of Kleinian
groups, that is finitely generated, discrete subgroups of
$\PSL_2\CC$. Let $\AA\subset \CC$ be the algebraic numbers. A
subgroup $G<\PSL_2\CC$ is {\it algebraic} if it can be conjugated
into $\PSL_2\AA$. Otherwise, it is {\it transcendental}. By Mostow
rigidity, all finite covolume Kleinian groups are algebraic. In
fact, it follows from the proof of Thurston's hyperbolization
theorem for Haken manifolds that any Kleinian group has {\it some}
faithful representation into $\PSL_2\CC$ whose image is algebraic.
This is proven by embedding the abstract Kleinian group into the
fundamental group of a finite volume hyperbolic 3-orbifold. The
induced hyperbolic structure on the subgroup from Thurston's
construction is geometrically finite \cite{Mo}. It seems possible
that there are algebraic Kleinian groups which are geometrically
finite, but which are not the subgroup of any finite volume
Kleinian group. However, it follows from the geometric tameness
theorem \cite{Ag04, CG04} and the covering theorem \cite{Ca} that
if a non-geometrically finite Kleinian group $\G$ is a subgroup of
a finite volume Kleinian group $\G'$, then $\G$ is a surface group
containing a  fiber subgroup $\G_0$ of a virtual fibration of
$\HH^3/\G'$ of index at most 2 in $\G$. Each end of a Kleinian
group is either geometrically finite, or simply degenerate
\cite{Ca93}. Thus, in this case $\G_0$ has two simply degenerate
ends, and there is an infinite order isometry $\psi\in \G'-\G_0$
which normalizes $\G_0$, and acts by a translation on
$\HH^3/\G_0$. It does not appear to be known whether there are
degenerate algebraic Kleinian groups which are not of this type. A
similar argument to the covering theorem shows that a singly
degenerate hyperbolic 3-manifold cannot immerse totally
geodesically in a higher dimensional geometrically finite
hyperbolic manifold. Any algebraic Kleinian group $\G$ embeds in a
natural way into a higher rank S-arithmetic lattice. But the
embedding does not induce a quasi-isometric embedding on the
convex core of $\HH^3/\G$ into the corresponding cover of the
symmetric space, otherwise the techniques of the covering theorem
would carry over. One may construct simplicial ruled surfaces in
higher rank symmetric spaces, but the bounded diameter lemma and
local finiteness fail.

It would be interesting to know if there can be singly degenerate
algebraic surface Kleinian groups. We demonstrate in this note
that there are families of degenerate punctured torus Kleinian
groups satisfying certain geometric restrictions which must be
transcendental. The families of groups we consider are
uncountable, and therefore all but countably many groups in a
family will be transcendental; the point of the result is that
{\it all} of the groups in the family are transcendental.

One motivation for studying this question is to understand whether
there is an algorithm to tell that a collection of matrices in
$\SL_2\AA$ generates a discrete subgroup of $\SL_2\CC$. If every
non-geometrically finite Kleinian group were the subgroup of a
finite volume Kleinian group, then an algorithm would exist. So
the discovery of a singly degenerate algebraic Kleinian group
would demonstrate the difficulty of this question.

{\bf Acknowledgment} We thank Caltech and Nathan Dunfield for
their hospitality during a visit in which this work was carried
out.
\section{Ending lamination theorem}
In this section, we review the classification of punctured torus
Kleinian groups from \cite{Minsky}.
 Let $\S$ be a punctured torus.  A punctured torus group
$G$ is a 2 generator free discrete subgroup of $\PSL_2\CC$, such
that there exist two generators of $G$ whose commutator is
parabolic. $G$ is naturally identified as the image of a discrete
faithful representation $\rho:\pi_1(\S)\to \PSL_2\CC$ such that
the monodromy of the puncture is parabolic. Then $N=\HH^3/G$ is a
punctured torus manifold. Bonahon showed that $N\cong \S\times
\RR$ \cite{Bon}.

Let $\HH^2$ denote the upper half plane model for hyperbolic
space, with boundary $\RR$. The Farey triangulation is a graph in
$\overline{\HH^2}=\HH^2\cup \RR \cup \infty$ with vertices at
$\hat{\QQ}=\QQ\cup \infty$, and two rational numbers $\frac{p}{q},
\frac{r}{s}$ are connected by a hyperbolic geodesic if $|ps-qr|=1$
(where we let $\infty =\frac10$). The irrational numbers in $\RR$
represent the ending laminations. See figure \ref{Farey} for a
partial picture of the Farey triangulation in the disk model of
hyperbolic space.
\begin{figure}[htbp]
    \begin{center}
    \epsfbox{figures.ps}
    \caption{\label{Farey} The Farey graph in the unit disk,
    with some of the vertices labelled}
    \end{center}
\end{figure}
The curve complex $\MC(\S)$ of the punctured torus has vertices
consisting of isotopy classes of simple closed curves. The edges
of $\MC(\S)$ join pairs of curves which intersect exactly once.
There is a natural bijection of $\MC(\S)^{(1)}$ with the Farey
triangulation, for example by considering projective homology
classes in $H_1(\S)\cong\ZZ^2$. Given a basis $\{\a,\b\}$ for
$H_1(\S)$, any oriented simple closed curve represents a homology
class $p\a+q\b$, with $\gcd(p,q)=1$. Then we get an element
$-\frac{p}{q}\in \hat{\QQ}$, which gives a bijection with
unoriented simple closed curves. The number $|pr-qs|$ represents
the geometric intersection number between two simple closed curves
$p/q, r/s$.

If we lift a punctured torus group representation $\rho:\pi_1\S\to
\PSL_2\CC$ to $\tilde{\rho}:\pi_1\S\to \SL_2\CC$, then the
function $\tr(\tilde{\rho}(\a))$ is well-defined on conjugacy
classes of elements in $\pi_1\S$. This function takes values in
$\AA$ if $\rho$ is algebraic. The lift $\tilde{\rho}$ is
well-defined up to multiplying generators by $-I$. Given three
adjacent curves $\a,\b,\g\in \MC(\S)$, with traces
$x=\tr(\tilde{\rho}(\a)), y=\tr(\tilde{\rho}(\b)),
z=\tr(\tilde{\rho}(\g))$, they satisfy the Markoff equation
\begin{equation}x^2+y^2+z^2=xyz.\end{equation} Moreover, if $\delta\in \MC(\S)$ is
adjacent to $\a,\b$ with trace $w=\tr(\tilde{\rho}(\delta))$, then
these satisfy the equation \begin{equation}w+z=xy.
\label{recursion}\end{equation} These formulae follow from trace
identities in $\SL_2\CC$, see \cite{Bowditch98} for details.

Let $\DD=\overline{\HH^2}$. Bonahon showed the existence of end
invariants $(\nu_-,\nu_+)\subset (\DD\times \DD)\backslash
\Delta$, where $\Delta$ is the diagonal of $\d\DD\times\d\DD$
\cite{Bon}. Teichm\"{u}ller space for the once punctured torus is
identified with $\Int \DD=\HH^2$. Minsky proved that the end
invariants of $G$ determine $G$ uniquely up to conjugacy in
$\PSL_2\CC$ (Theorem A, \cite{Minsky}). We may thus call $\nu_+$ a
{\it transcendental ending lamination} if the punctured torus
group associated to $(\nu_-,\nu_+)$ is transcendental for all
$\nu_-\in \DD-\{\nu_+\}$.

Let $N$ be a punctured torus manifold. If one removes the interior
of the Margulis tube associated to the parabolic commutator to get
$\hat{N}$, then $\hat{N}$ has two ends, $e_{\pm}$. The ends are
either geometrically finite, or simply degenerate. To each end,
associate an end invariant $\nu_{\pm}\in\DD$. If $e_s$ ($s\in
\{+,-\}$) is geometrically finite, then $\nu_s\in \Int \DD$ is the
point in Teichm\"{u}ller space of the conformal structure of the
domain of discontinuity corresponding to $e_s$, or if there is an
accidental parabolic, it is the curve $\nu_s\in \hat{\QQ}=\MC(\S)$
represented by the accidental parabolic in $e_s$. If $e_s$ is
simply degenerate, then there is a unique ending lamination
$\nu_s\in \RR-\QQ$ which is a limit point of simple curves in
$\MC(\S)$ whose geodesic representatives in $N$ have bounded
length and exit the end $e_s$.

To each end invariant $\nu_s$, we associate an element $\a_s$ of
$\hat{\RR}$, $s=\pm$. If the end $e_s$ is simply degenerate or has
an accidental parabolic, then $\a_s=\nu_s$. If $e_s$ is
geometrically finite, then $\a_s$ is a systole in the hyperbolic
structure on $\S$ corresponding to the Teichm\"uller point
$\nu_s$, which is defined up to finite ambiguity. We will assume
from now on that $e_+$ is simply degenerate, so that $\nu_+\in
\RR-\QQ$. Define $E=E(\a_-,\a_+)$ to be the set of edges of the
Farey graph which separate $\a_-$ from $\a_+$ in $\DD$. Let
$P_0\in \hat{\QQ}$ be the set of vertices of $\MC(\S)$ belonging
to at least two edges of $E$. The edges of $E$ admit a natural
order where $e<f$ if $e$ separates the interior of $f$ from
$\a_-$, and this induces an order on $P_0$ (see figure
\ref{pivot}). So we can arrange $P_0$ as a sequence
$\{\a_n\}_{n=\i}^{\infty}$, where $\i=-\infty$ if $\nu_-\in
\RR\backslash \QQ$, and $\i=0$ otherwise. We note that the
vertices of $E$ which are not elements of $P_0$ also are ordered,
and we will denote these by $\{\b_i\}_{i=\iota}^{\infty}$, with
the convention that $\b_1$ is adjacent to $\a_0$ in $\MC(\S)$ and
$\a_0<\b_1$ (meaning that any edge of $E$ incident with $\a_0$ is
$<$ the unique edge of $E$ incident with $\b_1$). The {\it width}
of $\a_i$ is $1+$ the number of vertices in $E\backslash P_0$
which are adjacent to $\a_i$ in $\MC(\S)$ and which are $>
\a_{i-1}$ and $< \a_{i+1}$ (in the example in figure \ref{pivot},
$w(0)=3, w(1)=4, w(2)=2, w(3)=1, w(4)=3$).

\begin{figure}[htbp]
    \begin{center}
    \epsfbox{figures2.ps}
    \caption{\label{pivot} The pivot
sequence }
    \end{center}
\end{figure}

The pivot sequence $\{\a_n\}_{n=0}^{\infty}$ determines $\nu_+$
uniquely. In fact, given adjacent $\a_0,\a_1\in \MC(\S)$, and the
width sequence $\{w(n)\}_{n\in \NN}$, the pivot sequence
$\{\a_n\}$ and $\nu_+$ are uniquely determined. Assuming a fixed
lift of a punctured torus group $\tilde{\rho}:\pi_1\S\to
\SL_2\CC$, let us denote $a_i=\tr(\tilde{\rho}(\a_i)),
b_j=\tr(\tilde{\rho}(\b_j))$. From the trace relation equation
\ref{recursion}, we can compute $a_i$ or $b_j$ recursively as a
polynomial function of the traces of $\a_0,\a_1,\b_1$. In the
example in figure \ref{pivot}, $b_2=b_1a_1-a_0$,
$b_3=b_2a_1-b_1=(b_1a_1-a_0)a_1-b_1$.  We let $\l(\g)=l+i\th$ be
the complex translation length of an element (or conjugacy class)
$\g\in\PSL_2\CC$, normalized so that $l\geq 0, \th\in (-\pi,\pi]$.
It is determined by the identity $\tr^2\g=4\cosh^2(\l/2)$. Given
$\rho:\pi_1(\S)\to \PSL_2\CC$, we get a function on $\MC(\S)$
denoted $\l(\a)\equiv\l(\rho(\a))$.

\section{Construction of transcendental ending laminations}
 We will describe the construction of
width sequences $\{w(n)\}_{n=1}^{\infty}$ with associated ending
lamination $\nu_+$ such that for any choice of ending lamination
$\nu_-\in \DD-\{\nu_+\}$, the punctured torus group $G$ associated
to $(\nu_-,\nu_+)$ is transcendental. The construction is akin to
Cantor diagonalization and to Liouville's construction of
transcendental numbers. The non-trivial input which we take is a
result of Minsky.

\begin{theorem} (4.4,4.5 \cite{Minsky})
There exist constants $c_2, c_3, c_4$ such that
$$\frac{c_2}{w(n)^2}\leq l(\a_n)\leq \frac{c_3}{w(n)^2},$$
$$|w(n)-\frac{2\pi}{\th(\a_n)}|\leq c_4.$$
\end{theorem}

From this theorem, we clearly have $l(\a_n)=O(w(n)^{-2})$,
$\th(\a_n)=O(w(n)^{-1})$, so $\l(\a_n)=O(w(n)^{-1})$. It follows
that
\begin{equation}|a_n^2-4| =
|4\cosh^2(\l(\a_n)/2)-4|= O(w(n)^{-2}).\label{bound}\end{equation}

{\bf Construction:} Choose an exhaustion of $\AA$ by finite
subsets $\AA=\cup_{i=0}^{\infty} A_i$, $|A_i|<\infty$, which is
possible since $\AA$ is countable. Also, choose a sequence
$\{n_i\}\subset \NN$.  Assume by induction that
$\{w(1),...,w(n_i-1)\}$ have been defined. We may choose a triple
of generators $\a_0,\a_1,\b_1$ with traces $a_0,a_1,b_1$. Assume
that $a_0,a_1,b_1\subset A_i$. There is a polynomial
$P_i(x,y,z)\in \ZZ[x,y,z]$ such that $a_{n_i}=P_i(a_0,a_1,b_1)\neq
\pm 2$ (following from theorem 2.1, $\l(\a_n)\neq 0$ since any
parabolic element is conjugate to either the peripheral curve or
to an accidental parabolic corresponding to an end invariant by
theorem 4.1 \cite{Minsky}). Let
\begin{equation} m_i=\min\{ |P_i(x,y,z)^2-4|\ \ni\ x,y,z\in A_i, P_i(x,y,z)\neq
\pm 2\}.\end{equation}
 Choose $w(n_i)$ large enough that
$|a_{n_i}^2-4|< m_i,$ for any pivot  $\a_{n_i}$ with width
$w(n_i)$, which we may choose by equation \ref{bound}. We may
choose the widths $\{w(n_i+1),...,w(n_{i+1}-1)\}$ arbitrarily.
This describes the recursive construction of the sequence
$\{w(n)\}_{n=1}^{\infty}$.

\begin{theorem}
If $\nu_+$ is associated to the width sequence $\{w(1),w(2),...\}$
coming from the construction, then for any ending lamination
$\nu_-$, the punctured torus group $G$ associated to
$(\nu_-,\nu_+)$ is transcendental.
\end{theorem}

\begin{proof}
Suppose we had a punctured torus group $G < \PSL_2\AA$, with
associated ending pair $(\nu_-,\nu_+)$, where $\nu_+$ has the
width sequence $\{w(n)\}$ given in the construction above. Then
$\{a_0,a_1,b_1\}\subset A_i$, for some $i$. Thus, we have for the
pivot $\a_{n_i}$, $$0\neq |a_{n_i}^2-2| \geq m_i >
|a_{n_i}^2-4|,$$ a contradiction.
\end{proof}

\section{Conclusion}
Most likely, the numbers $\nu_+\in \RR-\QQ$ coming from the
construction are transcendental, since the continued fraction
coefficients of $\nu_+$ are given by $w(n)$ (up to ambiguity of a
finite initial sequence), and the numbers $w(n)$ should grow fast
enough to satisfy Liouville's criterion for being transcendental.
One could get explicit sequences $\{w(n)\}$ which are defined
recursively and satisfy the requirements of the construction by
using the generalized Liouville theorem, which bounds the length
of $P_i(a_0,a_1,b_1)$ in terms of the length of $P_i$ and the
lengths of $a_0,a_1,b_1$. The length of a polynomial is the sum of
the absolute values of its coefficients, and the length of an
algebraic number is the length of its minimal polynomial. Then the
set $A_i\subset \AA$ would be all algebraic numbers with length
and degree $\leq i$, which is a finite set, and one could estimate
the growth of the bound on $P_i(a_0,a_1,b_1)$ using equation
\ref{recursion} recursively. It might be interesting to compute
the asymptotics of $\{w(n)\}$ using this method.

The same technique produces transcendental ending laminations for
4 punctured sphere groups and 2 parabolic generator groups. It
would be interesting to try to use the techniques of the general
ending lamination theorem  to find transcendental ending
laminations for arbitrary Kleinian surface groups \cite{Minsky03,
BCM}.

\def\cprime{$'$} \def\cprime{$'$}


TITLE: photon absorption by atoms causes heat?
QUESTION [1 upvotes]: I have came up with a weird doubt: photon absorption by atoms causes heat? I mean, I was always told that if the photon's frequency is the magic one, the atoms absorbs the photon and goes to an excited state. So I have to suppose that heating (increasing in kinetic energy) happens when the frequency is outside the set of permitted transitions. Is it correct?

REPLY [1 votes]: This is true. If for example you subject Hydrogen gas to a perfectly monochromatic 121.57 nm laser, then all that will happen is that the gas will scatter the light in all directions, glowing without increasing the temperature.
Otherwise there are many different phenomena that are involved in the heat transfer of energy by radiation. For example in solids, photons are absorbed and turn into phonons which are waves that when they are numerous lead to thermalization, and for molecules you have photon absorption that leads to molecular vibration which again increases the root mean square speed, etc...


TITLE: Intuition behind picking group actions and Sylow
QUESTION [11 upvotes]: A common strategy in group theory for proving results/solving problems is to find a clever group action. You take the group you are interested in (or perhaps a subgroup), and find some special set that your group can act on, usually by left multiplication or conjugation. Somehow studying this action makes the result you want clearer to see.
The most obvious example of this is with proving the Sylow theorems.

To prove the First Sylow theorem (that a $p$-subgroup exists) you can let $G$ act by left multiplication on all subsets of $G$ that have size $p^n$.
To prove the Second Sylow theorem (that Sylow $p$-subgroups are conjugate) you let $Q$ be any $p$-subgroup, $P$ a Sylow $p$-subgroup, and let $Q$ act on $G/P$ by left multiplication.
To prove the Third Sylow theorem (that the number of Sylow $p$-subgroups is $1\pmod p$ and divides $|G|$) you can consider both $G$ and some Sylow $p$-subgroup $P$ acting on $\operatorname{Syl}_p(G)$ by conjugation.

My question: is there any intuitive or natural way to come up with these group actions? To me, all three proofs seem magical -- if someone had told me which group action to consider, I could probably have completed the proofs myself, but I would never have come up with the appropriate action myself.
More generally, are there any ways to "see" which group action might help for solving a specific problem?

REPLY [4 votes]: Well, there's only a few group actions to consider. The ones that worked made it into the proofs. That said, there are a priori reasons to check these actions used in the proofs first.
In investigating these actions, having a fundamental understanding of orbit-stabilizer is critical.
For Sylow I, we don't know from the get-go there is any subgroup of order $p^n$. But of course there are subsets of size $p^n$, and the subgroups are distinguished among these in that they are closed under multiplication. This closure property can be rephrased in terms of stabilization and fixed points. Indeed, if a subset has stabilizer $S$ (under left multiplication), then it is a union of right cosets of $S$, so in particular stabilizers must be $p$-subgroups. By orbit-stabilizer, a subset has full Sylow stabilizer iff its orbit size is not divisible by $p$. Which suggests a possible way to prove Sylows exist by contradiction by considering the sum of orbit sizes mod $p$!
For Sylow II, recall some basic facts about group actions a la (again) orbit-stabilizer. Every $G$-set is a disjoint union of orbits, all orbits are eqiuvalent to $G/H$ for stabilizers $H$. But these coset spaces are only inequivalent up to conjugacy class of subgroup, because $\mathrm{Stab}(g\omega)=g\mathrm{Stab}(\omega)g^{-1}$. This can be rephrased as follows: $H,K\le G$ are conjugate iff $K$ has a fixed point acting on $G/H$ (by left-multiplication).
For Sylow III, after we already know Sylow subgroups are conjugate we automatically know they carry a conjugation action from the group. Orbit-stabilizer gets you $G/N_G(P)$. A trick we used for Sylow I to get a numerical result is to mod by $p$, so we can do that here to investigate the size of this index, which means we want to consider the action of a $p$-group for modding out to yield results. Might as well a Sylow subgroup, and further might as well $P$ so we have a guaranteed fixed point.


TITLE: Geometry question
QUESTION [1 upvotes]: In the given figure , AP, BQ and CR are perpendicular to line AC. And AP=$x$ , BQ=$y$, CR=$z$ then find the value of $\frac{1}{x} + \frac{1}{z}$ in terms of $y$.
I have no idea how to solve it. But the limitation is this is to do with the use of similarity concepts. Don't use trigonometry.

REPLY [2 votes]: y/z = AB / (AB+BC)
y/x = BC / (AB+BC)
y/z + y/x = AB/(AB+BC) + BC/(AB+BC) = 1
1/z + 1/x = 1/y


TITLE: Riesz Representation Thereom for Polynomials with real coefficients problem
QUESTION [1 upvotes]: Find a polynomial q(x) $\in$ P$_2$($\Bbb R$) Such that $ p ( 1/4 ) = $$\int_0^1 p(x)q(x) \,dx$$ $.
I'm sorry to ask this question, but I've been working on it for some time. The inner product on P$_2$($\Bbb R$) is given by$ <f,g>= $$\int_0^1 fg \,dx$$.  $ I have aimed to utilize the Reisz Representation Thereom to solve this problem. To save time, an orthonomal basis for this space is given by
$\beta$ = { $1$, $\sqrt 12$ ($x-1/2$), $\sqrt180$( $ $$x^2$- x + 1/6 $ $ }. Call these vectors $s_1$, $s_2$, $s_3$. Now, should I use the formula q(x) = $\sum S_i  S_i$(1/4), where the sum runs from i=0 to 3
? Is this complelety rong? Any Hints? Thanks for your time as always, and don't waste your time with it too long, thanks.

REPLY [1 votes]: Doesn't your question boil down to solving $d,f,g$ in terms of $a,b,c$ in the following equation?
$$\int_0^1p(x)q(x) \, dx =p(\frac{1}{4}) \\\int_0^1(ax^2+bx+c)(dx^2+ex+f) \, dx =a(\frac{1}{4})^2+b(\frac{1}{4})+c \\\
cf+ \frac{(ce+bf)}{2}+\frac{cd+be+af}{3}+\frac{bd+ae}{4}+\frac{ad}{5}\, =\frac{a}{16}+\frac{b}{4}+c$$
Note that $p(x)=ax^2+bx+c$ and $q(x)=dx^2+ex+f$
This is just a linear equation in 3 unknowns.


TITLE: Proof $\left|1-\binom{n}{k} \frac{k!}{n^k}\right| \leq \frac{k(k-1)}{n}$
QUESTION [2 upvotes]: For all $n \in \mathbb{N}, 0 \leq k \leq n$ it holds that
$$\left|1-\binom{n}{k} \frac{k!}{n^k}\right| \leq \frac{k(k-1)}{n}$$
How can one prove that?
Base case:
$$ \left|1-\frac{1!}{k!\cdot(1-k)!} \frac{k!}{1^k}\right| = \left|1-\frac{1!}{(1-k)!} \frac{1}{1^k}\right| $$
If $k=0$, then
$$\left|1-\frac{1!}{(1-1)!} \frac{0}{1^0}\right| = 1 - 1 * 0 = 0 = \frac{0(0-1)}{1} = 0$$
If $k=1$, then
$$1-\frac{1!}{(1-1)!}\frac{1}{1^1} = 0 = \frac{1(1-1)}{1} = 0$$
Induction step:
$$ 1- \binom{n+1}{k}\frac{k!}{(n+1)^k} = 1 - \frac{(n+1)!}{k! \cdot (n+1-k)!} \frac{k!}{(n+1)^k} = \frac{(n+1)!}{(n+1-k)! (n+1)^k} = ?$$

REPLY [2 votes]: The proposed inequality rhymes well with the following general inequality which can be proved by induction

Let $I$ be a finite set (of indices) and $a \in [0,1]^I$ a family of numbers. It then holds that:
  $$\prod_{i \in I}(1-a_i) \geqslant 1- \sum_{i \in I} a_i$$

(needless to say, the induction is carried out with respect to the cardinal of $I$).
In your particular case you have
$$\left|1-{n\choose k}\left( \frac{k!}{n^k} \right)\right|=\left|1-\prod_{h=0}^{k-1}\left(1-\frac{h}{n} \right) \right|=1-\prod_{h=0}^{k-1}\left(1-\frac{h}{n} \right)$$
for $n \in \mathbb{N}^*, k \leqslant n$ and since $1-\frac{h}{n} \in [0,1]$ for any $h$ satisfying $0 \leqslant h \leqslant k-1$ an application of the mentioned inequality yields
$$1-\prod_{h=0}^{k-1}\left(1-\frac{h}{n} \right) \leqslant \sum_{h=0}^{k-1} \frac{h}{n}=\frac{k(k-1)}{2n}$$


TITLE: Looking for the functions $\alpha_n(x)$ that satisfy $\sum_{n=0}^{\infty} e^{i \alpha_n(x)}\frac{H_n(x)}{\sqrt{2^n n!}}=0$
QUESTION [1 upvotes]: I am looking for the functions $\alpha_n(x)$ that satisfy $\sum_{n=0}^{\infty} e^{i \alpha_n(x)}\phi_n(x)=0 \text{ or } \delta(x)$ where $\phi_n(x)=\frac{H_n(x)}{\sqrt{2^n n!}}$ and $H_n(x)$ is the $n^{\small\mbox{th}}$ Hermite Polynomial (physicist's convention). Do these functions exist or is there a method to find them numerically?

REPLY [2 votes]: You mentioned that you would be interested in seeing complex $\alpha_{n}(x)$ solutions; I believe I have the answer in the $\delta(x)$ case. We will use the fact that:
$$
\int_{-\infty}^{\infty}H_{n}(x)H_{m}(x)e^{-x^2}\,\text{d}x = \sqrt{\pi}2^n n! \delta_{n m} \tag{1}
$$
We wish to find $\alpha_{n}(x)$ such that:
$$
\sum_{n=0}^{\infty}\frac{e^{i\alpha_{n}(x)}}{\sqrt{2^n n!}}H_{n}(x)=\delta(x) \tag{2}
$$
Begin by multiplying both sides by $H_{m}(x)$ and integrating over the real line:
$$
\sum_{n=0}^{\infty}\frac{1}{\sqrt{2^n n!}}\int_{-\infty}^{\infty}H_{n}(x)H_{m}(x)e^{ i\alpha_{n}(x)}\,\text{d}x =\int_{-\infty}^{\infty}H_{m}(x)\delta(x)\,\text{d}x
$$
Motivated by $(1)$, let us assume that the $\alpha_{n}(x) = i(x^2 - C_{n})$ for some constant $C_{n}$. Then, $e^{i\alpha_{n}(x)}=e^{-x^2 + C_{n}}=B_{n}e^{-x^2}$, so:
$$
\sum_{n=0}^{\infty}\frac{B_{n}}{\sqrt{2^n n!}}\int_{-\infty}^{\infty}H_{n}(x)H_{m}(x)e^{-x^2}\,\text{d}x =\int_{-\infty}^{\infty}H_{m}(x)\delta(x)\,\text{d}x
$$
Now use $(1)$ and the fact that $\int f(x) \delta(x)\,\text{d} x = f(0)$:
$$
\sum_{n=0}^{\infty}\frac{B_{n}}{\sqrt{2^n n!}}\cdot \sqrt{\pi}2^n n! \delta_{n m} = B_{m} \sqrt{\pi 2^m m!} =H_{m}(0)\implies B_{m} = \frac{H_{m}(0)}{\sqrt{\pi 2^m m!}}
$$
Therefore, we have $\alpha_{n}(x) = i\left(x^2 - \ln(\frac{H_{n}(0)}{\sqrt{\pi 2^n n!}})\right)$ And therefore:
$$
\sum_{n=0}^{\infty}\frac{H_{n}(0)}{\sqrt{\pi} 2^n n!}H_{n}(x)e^{-x^2}=\delta(x) \\
\sum_{n=0}^{\infty}\frac{H_{2n}(0)}{\sqrt{\pi} 4^n (2n)!}H_{2n}(x)e^{-x^2}=\delta(x) \\
$$
Since $H_{2n+1}(0)=0$. Note that this trick won't work for the $0$ case since the $B_{n}$ would all be $0$.


text:
\begin{definition}[Definition:Zermelo-Fraenkel Universe]
A '''Zermelo-Fraenkel universe''' is a [[Definition:Basic Universe|basic universe]] which also satisfies the [[Axiom:Axiom of Infinity|axiom of infinity]] and the [[Axiom:Axiom of Substitution|axiom of substitution]]:
{{:Definition:Basic Universe Axioms}}
=== [[Axiom:Axiom of Infinity/Class Theory|$\text A 7$: Axiom of Infinity]] ===
{{:Axiom:Axiom of Infinity/Class Theory}}
=== [[Axiom:Axiom of Substitution|$\text A 8$: Axiom of Substitution]] ===
{{:Axiom:Axiom of Substitution}}
\end{definition}

config: wiki


TITLE: Is there a *simple* example showing that uncorrelated random variables need not be independent?
QUESTION [30 upvotes]: Is there a simple example showing that given $X,Y$ uncorrelated
  (covariance is zero), $X,Y$ are not independent?

I have looked up two references, however, I am dissatisfied with both.

In Reference $1$, $X,Y$ are assumed to be independent uniform RVs
from $(0,1)$, construct $Z = X+Y, W = X - Y$, then the claim is that
$Z,W$ is uncorrelated but not independent. Unfortunately, finding the
PDF of $Z,W$ is not trivial.
In Reference $2$, $\phi$ is assumed to be uniform RV from $(0,
   2\pi)$, and construct $X = \cos(\phi)$, $Y = \sin(\phi)$. Then the claim is that $X,Y$ are uncorrelated but not independent. Unfortunately, the PDFs of $X,Y$ takes on the form of rarely mentioned arcsine distribution.

I just wish to have an example at hand where I can whip out to show that uncorrelated does not necessarily implies independent. Is this do-able?

REPLY [2 votes]: Another easy to explain on the run:
for $\theta$ Uniform [0 , 2$\pi$] set X = sin($\theta$), Y = cos($\theta$).
Then $X^2 + Y^2 = 1$ - clearly X and Y are not independent.
However as correlation is a linear relationship it is unable to produce anything but zero for the correlation between X and Y


TITLE: Linear independence of a set of vectors in $\mathbb{R}^n$
QUESTION [2 upvotes]: There is a theorem that states: $$Let \space S=\{v_1,v_2,...v_r\}\space be \space a \space set \space of\space vectors \space in\space \mathbb{R}^n. \space If\space r>n,\space then\space S\space is\space linearly\space dependent.$$ My question is, does the 'other' case apply as well? By other case, I mean if $r<n$, does this mean the set $S$ is linearly independent or linearly dependent? No proofs please, just some intuition behind the answer if possible!
Thanks in advance!

REPLY [1 votes]: There's nothing to be said (without further information) about a set with less elements than the dimension of the space, except when the size of the set is exactly one (in which case it's trivially linearly independent iff it's not the zero subspace). Consider, for example, $v \in \mathbb{R}^k \setminus\{0\}$ with $k \geq 3$ and the set
$$
\{v,2v,3v,...,(k-1)v\}
$$
which is clearly linearly dependent, but has less than $k$ elements. The intuition here is that you could easily choose vectors that belong to the subspace generated by the previously chosen, and if you choose more vectors than the dimension of the space, this property is guaranteed.

REPLY [1 votes]: Just from $r<n$, you cannot say whether the set S is linearly independent or linearly dependent. E.g., in $R^3$, two parallel vectors are linearly dependent, while two non-parallel vectors are linearly independent.


TITLE: Condition for Banach space that the distance function can always reach its minimum at a unique point
QUESTION [4 upvotes]: Let $(X,\|\cdot\|)$ be a Banach space and $B\subset X$ be a bounded subset. Now define a function $f_B:X\to [0,\infty)$ by $f_B(x)=\sup_{b\in B}\|b-x\|$.
My question is in which kind of Banach space, $f_B$ can always reach its minimum at a unique point of $X$ for any given bounded subset $B$.
I find that the norm does matter: if $X=\mathbb{R}^2$ equipped with $l^2$ norm, it is true. However, if $X=\mathbb{R}^2$ equipped with $l^\infty$ norm, it is not true when $B=\{0,1\}\times[0,1]$.

REPLY [4 votes]: I think the condition you need is the uniformly convexity:
For any fixed $M>0$, $\forall \epsilon>0$, $\exists \delta>0$ such that
$$\|x\|\le M,\|y\|\le M,\|x-y\|\ge \epsilon\Rightarrow\left\|\frac{x+y}{2}\right\|\le M-\delta.$$
Since $B$ is bounded, suppose $B\subset B_M=\{x\in X:\|x\|\le M\}$ for some $M>0$. It is clear that we only need to focus on the value of $f(x)$ in $B_{3M}$, because for $\|x\|>3M$, $\|x-b\|\ge\|x\|-\|b\|> 2M$. However, since $B\subset B_M$, the minimum value of $f$ should be $\le 2M$.
Let $m=\inf_{x\in X}f(x)=\inf_{x\in B_{3M}}f(x)$. Then for any fixed $\epsilon>0$, there exists $\delta>0$ such that $$\|x\|\le m,\|y\|\le m,\|x-y\|\ge \epsilon\Rightarrow\left\|\frac{x+y}{2}\right\|\le m-\delta.$$
Denote $T=\max\{\|x\|,\|y\|\}$ hence $\|x\|,\|y\|\le T$. If $m\le T\le 4M$. Denote $x'=\frac{mx}{T}, y'=\frac{my}{T}$, so $\|x'\|,\|y'\|\le m$. If $\|x-y\|\ge \frac{4M}{m}\epsilon$, i.e., $\|x'-y'\|\ge \frac{4M}{T}\epsilon\ge \epsilon$, then
\begin{align*}
\left\|\frac{x+y}{2}\right\|= \frac{T}{m}\left\|\frac{x'+y'}{2}\right\| \le\frac{T}{m}(m-\delta) = T-\frac{T}{m}\delta \le T-\delta =\max\{\|x\|,\|y\|\}-\delta
\end{align*}
To sum up, for any $\epsilon>0$, there exists $\delta>0$ for any $x,y\in B_M$ with $m\le\max\{\|x\|,\|y\|\}\le 4M$ and $\|x-y\|\ge \epsilon$, such that
$$\left\|\frac{x+y}{2}\right\|\le \max\{\|x\|,\|y\|\}-\delta.$$
Given $\epsilon>0$, for fixed $x,y\in B_{3M}$, $\|x-y\|\ge\epsilon$, let $S=\{b\in B: \|x-b\|\ge m\text{ or }\|y-b\|\ge m\}$. Then for all $b\not\in S$,
$$\left\|\frac{x+y}{2}-b\right\|=\left\|\frac{x-b}{2}+\frac{y-b}{2}\right\|\le \frac{\|x-b\|+\|y-b\|}{2}<m,$$
so we do not need to focus on the value on $B\setminus S$.
For $b\in S$, since $\|x-b\|\le \|x\|+\|b\|\le 4M$, $\|y-b\|\le 4M$, hence $m\le\max\{\|x-b\|,\|y-b\|\}\le 4M$ and $\|(x-b)-(y-b)\|=\|x-y\|\ge\epsilon$, by above inequality, we have
\begin{align*}
\left\|\frac{x+y}{2}-b\right\|&\le \max\{\|x-b\|,\|y-b\|\}-\delta\\
&\le \max\{\sup_{b\in S}\|x-b\|,\sup_{b\in S}\|y-b\|\}-\delta\\
& = \max\{\sup_{b\in B}\|x-b\|,\sup_{b\in B}\|y-b\|\}-\delta\\
& = \max\{f(x),f(y)\}-\delta.
\end{align*}
Thus
\begin{align*}
f\left(\frac{x+y}{2}\right)=\sup_{b\in B}\left\|\frac{x+y}{2}-b\right\|&=\sup_{b\in S}\left\|\frac{x+y}{2}-b\right\|\le  \max\{f(x),f(y)\}-\delta.
\end{align*}
Uniqueness: If $x,y\in X$ such that $f(x)=f(y)=m$, then $\exists \delta>0$ such that
$$f\left(\frac{x+y}{2}\right)\le \max\{f(x),f(y)\}-\delta=m-\delta<m,$$
which is a contradiction.
Existence: Suppose $(x_n)$ is a sequence in $B_M$ such that $f(x_n)\to m$. We shall prove that $(x_n)$ is a Cauchy sequence. If not, there exists $\epsilon>0$ and a subsequence $(x_{n_k})$ such that $\|x_{n_{k+1}}-x_{n_k}\|\ge\epsilon$. Thus
$$f\left(\frac{x_{n_{k}}+x_{n_{k+1}}}{2}\right)\le \max\{f(x_{n_{k}}),f(x_{n_{k+1}})\}-\delta.$$
Since $f(x_n)\to m$, there exists $N>0$ such that $\forall n>N$, $f(x_n)<m+\frac{\delta}{2}$, which follows that for $n_k>N$
$$m\le f\left(\frac{x_{n_{k}}+x_{n_{k+1}}}{2}\right)\le m+\frac{\delta}{2}-\delta<m,$$
which is a contradiction.
Thus $(x_n)$ is a Cauchy sequence. Since $X$ is a Banach space hence complete, $(x_n)$ converges to a unique element $x_0\in X$ and $f(x_0)=\inf_n f(x_n)=m$.


TITLE: Decision theory - Example
QUESTION [2 upvotes]: Your wealth is $€14400$. If you have no accident, your wealth remains unchanged, but if you do, you need to pay $€4400$ to cover medical costs. If you have an accident, the insurance reimburses the medical costs but you need to pay a premium $p=€2300$ whether you have an accident or not. Your utility over wealth is $U(w) = {\sqrt w}$, the probability of an accident is $q$.
(1) Suppose that you believe there is a probability $q=0.1$ of having an accident. What is the highest premium $p$ you would be willing to pay for the insurance?
In this case the expected utility without insurance would be:
$E [U(N)]=q*U(14400-4400)+(1-q)*U(14400)$
$E [U(N)]=q*U(10000)+(1-q)*U(14400)$
$E [U(N)]=q*{\sqrt 10000}+(1-q)*{\sqrt 14400}$
$E [U(N)]=q*100+(1-q)*120$
$E [U(N)]=0.1*100+0.9*120$
$E [U(N)]=118$
In order to buy the insurance, expected utility with insurance (minus premium price) must be grater or equal the expected utility without insurance.
$E [U(I-premium)] ≥ E [U(N)]$.
So, $E [U(I-premium)] ≥ 118]$
Is it correct?
But I have also seen this this rule:

$E [U(I)]=q*U(14400-premium)+(1-q)*U(14400-premium)≥0$
$E [U(I)]=0.1*U(14400-premium)+0.9*U(14400-premium)≥0$
And when I calculate it, I obtain that, with a probability of accident of $q=0.1$, the risk highest risk premium that a person would be willing to pay is exactly $€14400$, which is her/his entire wealth. This is a nonsense.
How can I calculate the highest premium that a person would be willing to pay for the insurance?
Any help is appreciated.
(2) Suppose that you still believe $q=0.1$, but that your utility over wealth is now $U(w) = w$. What is the highest premium $p$ you would be willing to pay for the insurance? Explain intuitively how this premium compares with the one you found in the previous point.
Here is the difference that this person is risk neutral, because of utility function $U(w) = w$, and in the first case we know that the person is risk averse, because of $U(w) = {\sqrt w}$ is a concave function. But how does the premium change? How can I calculate it?
Any help is appreciated.
Thanks in advance.

REPLY [1 votes]: Suppose the insurance premium is $p$, and your wealth is $I$. You’ve found that your expected utility with insurance is just $U(I-p) = \sqrt{I-p}$.
You prefer to purchase insurance whenever the above quantity is higher than your expected utility without insurance, which you’ve found to be $118$. Thus, you are looking for the largest $p$ such that $$ \sqrt{14400 -p} \ge 118.$$
You can follow similar steps when $U(w)=w$.