text:
\begin{document}
\thanks{The author is partially supported by KU Leuven grant IF C14/17/083.}
\keywords{Mild function, mild parametrization, subanalytic sets}
\subjclass[2020]{14G05, 26E10, 32B20}

\maketitle
\begin{abstract}
We prove that the function $P_\alpha(x) = \exp(1-x^{-\alpha})$ with $\alpha >0$ is $1/\alpha$-mild. We apply this result to obtain a uniform $1/\alpha$-mild parametrization of the family of curves $\{ xy = \epsilon^2 \mid (x,y) \in (0,1)^2 \}$ for $\epsilon \in (0,1)$,  which does not have a uniform $0$-mild parametrization by work of Yomdin. More generally we can parametrize families of power-subanalytic curves. This improves a result of Benjamini and Novikov that gives a $2$-mild parametrization.
\end{abstract}

\section{Introduction}
We study the function
\[
P_\alpha : (0,1) \to (0,1) : x \mapsto \exp(1-x^{-\alpha})
\]
with $\alpha > 0$ in the context of counting rational points. In \cite{countpointsexp}, Pila gave an upper bound on the number of rational points of bounded height on a certain exponential-algebraic surface by parametrizing it using $P_\alpha$. The bound on the derivatives of $P_\alpha$, or more generally of mild functions, are suited to bound the number of rational points on the set that it parametrizes, see \cite[Corollary 3.3]{countpointsexp}. The constant $C$ in the definition of a mild function (see Definition \ref{defmild}) plays an important role in this bound.

We will show that for the map $P_\alpha$, one can take $C = 1/\alpha$. This is sharper than the result of Pila, where he shows $C = 1+1/\alpha$ (\cite[Proposition 2.8.]{countpointsexp}) and has the advantage of being close to zero for $\alpha$ large. The main obstacle in bounding the derivatives is the polynomial in $1/x$ that appears in the computations, which is rather large.

The reason why the map $P_\alpha$ is interesting in this field, is because some functions become mild after composing with it. This has been applied successfully for $\alpha = 1$ in \cite{ccs} to construct $2$-mild parametrizations of families of subanalytic sets. In Section \ref{sec3} we show our main results. We prove such properties for some classes of functions which appear in \cite{unif} in Theorem \ref{abmmild}, from which the result on parametrizations of curves follows in Theorem \ref{curvepara}. In both results we obtain $C = 1/\alpha$ for $\alpha > 0$.

If one considers a fixed subanalytic set,  there are model theoretic results that imply that it has a $0$-mild parametrization (see for instance \cite{mildpara} for subanalytic sets). However, Yomdin has shown in \cite{yomdin2} that any analytic parametrization of the algebraic family of curves in the abstract necessarily has to contain infinitely many charts (see also \cite{ex}). More precisely, the number of charts in a $0$-mild parametrization will depend on $\epsilon$ and tend to infinity as $\epsilon$ tends to zero. We will construct an explicit $1/\alpha$-mild parametrization of this family where the size of the parametrization does not depend on $\epsilon$. Moreover, we can do this for any family of power-subanalytic curves using a pre-parametrization result of \cite{unif} or \cite{para}. Taking the above example in mind, this seems optimal. More on the field of parametrizations can be found in the survey \cite{ex}.

\section{Preliminaries}
In this short section we fix some notation for multidimensional calculus and revisit the formula for arbitrary derivatives of a function in several variables, also known as the Fa\`a di Bruno formula.

Let $f \in C^\infty(U,\R)$ be an infinitely differentiable function on an open $U \subset (0,1)^m$. For $\nu \in \N^m$ we denote $|\nu| = \nu_1+\ldots + \nu_m$ and
\[
f^{(\nu)}(x) = \left(\frac{\partial^{|\nu|}}{\partial x_1^{\nu_1}\cdots \partial x_m^{\nu_m}} f\right)(x).
\]
For $f \in C^\infty(U,\R^n)$ we set $f^{(\nu)} = (f_1^{(\nu)},\ldots,f_n^{(\nu)})$. Finally, for $x \in U$ and $\mu \in \R^m$ we denote:
\[
x^\mu = \prod_{i = 1}^m x_i^{\mu_i}.
\]

\begin{definition}[Mild functions] \label{defmild}
Let $f \in C^\infty(U,\R)$, $A,B \in \R_{>0}$ and $C \in \R_{\geq 0}$. We say that $f$ is $(A,B,C)$-mild if for any $x \in U$ and $\nu \in \N^m$:
\[
|f^{(\nu)}(x)| \leq B A^{|\nu|}(|\nu|!)^{C+1}.
\]
A map $f \in C^\infty(U,\R^n)$ is $(A,B,C)$-mild if all its component functions are. We say that $f$ is $C$-mild if it is $(A,B,C)$-mild for some $A$ and $B$.
\end{definition}

A $0$-mild function is analytic, but the converse is not true. The composition of $C$-mild functions is $C$-mild. A proof can be found in the next section. It relies on the formula for arbitrary order derivatives of a composition, which is also known as the Fa\`a di Bruno formula. In the univariate case, in propositions \ref{comp}, \ref{main} and \ref{weakpower}, we will use a more compact version stated in \cite[p.51]{dio}.

\begin{proposition}[Fa\`a di Bruno, \cite{faa}]\label{chain}
Suppose that $n$ is a positive integer, $V \subset \R^d$ and $U \subset \R^e$ are open, $f: V \to \R$, $g: U \to V$ and that $f$ and $g$ are $C^n$. For any $x \in U$ and $\nu \in \N^e$ with $|\nu| = n$ we have that: $$(f \circ g)^{(\nu)}(x) = \sum_{1 \leq |\lambda| \leq n} f^{(\lambda)}(g(x)) \sum_{s = 1}^n \sum_{p_s(\nu,\lambda)} \nu! \prod_{j = 1}^s \frac{(g^{(l_j)}(x))^{k_j}}{k_j!(l_j!)^{k_j}}$$ where $p_s(\nu,\lambda)$ is the set consisting of all $k_1,\ldots,k_s \in \N^d$ with $|k_i| > 0$ and $l_1,\ldots,l_s \in \N^e$ with $0 \prec l_1 \prec \ldots \prec l_s$ such that: $$ \sum_{i = 1}^sk_i = \lambda$$ and $$\sum_{i = 1}^s |k_i|l_i = \nu.$$ Here $l_i \prec l_{i+1}$ means that $|l_i| < |l_{i+1}|$ or, if $|l_i| = |l_{i+1}|$, then $l_i$ comes lexicographically before $l_{i+1}$.
\end{proposition}

\section{The mildness of $P_\alpha$}
In this section we prove that $P_\alpha$ is $1/\alpha$-mild. Writing $P_\alpha$ as a composition of two functions, we will use the Fa\`a di Bruno formula to bound the derivatives. The proof uses the fact that the composition of $0$-mild functions is $0$-mild. Indeed, this follows from the theory of Gevrey functions \cite{Ge}, and a proof in full generality can be found in \cite{para}. To be self contained, we briefly repeat its proof, but formulated in terms of mild functions.

\begin{proposition} \label{comp}
Suppose that $f$ and $g$ are respectively $(A_f,B_f,C)$-mild and $(A_g,B_g,C)$-mild. Then the composition $f \circ g$ is $C$-mild. Moreover, if $C = 0$ we have:
\[
A = A_g(1+A_fB_g) \quad \text{and} \quad B = \frac{A_fB_fB_g}{1+A_fB_g} < B_f.
\]
\end{proposition}

\begin{proof}
By Proposition \ref{chain}, using the triangle inequality and the mildness of $f$ and $g$, we obtain for any $x \in (0,1)$ a sum of positive terms:
\[
|(f \circ g)^{(n)}(x)| \leq \sum_{k = 1}^n B_fA_f^k (k!)^{C+1} \left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n (B_gA_g^i(i!)^{C+1})^{k_i}\right),
\]
where the sum is over all $n$ and $k$ satisfying the relations stated in the theorem. Since $x \mapsto x^{C+1}$ is convex, taking the $(C+1)$-th rooth of the constants where needed, we are done if we can show that if $C = 0$ the sum can be bounded by $BA^nn!$.

To this end, consider the maps:
\[
\psi(x) = \frac{B_f}{1-A_f(x-B_g)} \quad \text{and} \quad \phi(x) = \frac{B_g}{1 - A_gx}.
\]
One easily verifies that $\psi^{(k)}(B_g) = B_fA_f^kk!$ and $\phi^{(k)}(0) = B_gA_g^kk!$, which are exactly the bounds on the derivatives of $f$ and $g$. Now in this case, one can compute $(\psi \circ \phi)^{(n)}(0)$ directly, without using the chain rule. One checks that:
\[
(\psi \circ \phi)^{(n)}(0) = \frac{A_fB_fB_g}{1+A_fB_g} (A_g(1+A_fB_g))^n n!.
\]
\end{proof}

Clearly, the composition of a $C_1$-mild map and a $C_2$-mild map is $\max(C_1,C_2)$-mild. We need two more elementary lemma's which will be used frequently.

\begin{lemma} \label{umild}
Suppose that $\alpha \geq 1$ and let $u_\alpha$ be the map $(0,1) \to \R$ given by $u_\alpha(x) = 1-x^{-\alpha}$. Then, for any $x \in (0,1)$ and $k > 0 \in \N$, we have:
\[
x^{\alpha+k}|u_\alpha^{(k)}(x)| \leq \alpha^k k!.
\]
\end{lemma}
\begin{proof}
This follows immediately from:
\[
u_\alpha^{(k)}(x) = (-1)^{k+1}x^{-(\alpha+k)}\alpha(\alpha+1)\cdots(\alpha+(k-1))
\]
using that $\alpha \geq 1$ to obtain the desired upper bound.
\end{proof}

Clearly, if $\alpha < 1$, one can find the upper bound $k!$ instead of $\alpha^k k!$ in the lemma.

\begin{lemma} \label{expmild}
For $r,s \in \R_{>0}$ we have:
\[
\max_{x > 0} x^{-r}\exp(-sx^{-\alpha}) = \left(\frac{r}{es\alpha}\right)^{r/\alpha}.
\]
\end{lemma}
\begin{proof}
The maximum is reached in $x = (s\alpha/r)^{1/\alpha}$.
\end{proof}

\begin{proposition} \label{main}
The map $$P_\alpha: (0,1) \to (0,1): x \mapsto \exp(1-x^{-\alpha})$$ is $(A,e,1/\alpha)$-mild, where $A = 6\alpha$ if $\alpha \geq 1$ and $A = 3 (2/\alpha)^{1/\alpha}$ for $0 < \alpha < 1$.
\end{proposition}
\begin{proof}
Defining $u_\alpha(x) = 1-x^{-\alpha}$ as in Lemma \ref{umild}, we will use the Fa\`a di Bruno formula for the map $P_\alpha = \exp \circ \, u_\alpha$. This yields:
\[
P_\alpha^{(n)}(x) = \sum_{k = 1}^n \exp(u_\alpha(x)) \left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n (u_\alpha^{(i)}(x))^{k_i}\right).
\]
The summation over $n,k$ is subject to the conditions of Proposition \ref{chain}: $\sum_{i = 1}^n ik_i = n$ and  $\sum_{i = 1}^n k_i = k$.
Thus, in the product over the derivatives of $u_\alpha$, we obtain a factor:
\[
\prod_{i = 1}^n (x^{-(\alpha+i)})^{k_i} = x^{-\sum_{i = 1}^n (\alpha+i)k_i} = x^{-(k\alpha+n)}.
\]
Therefore, we obtain:
\begin{align*}
P_\alpha^{(n)}(x) &= \sum_{k = 1}^n x^{-(k\alpha+n)}\exp(u_\alpha(x)) \left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n (x^{\alpha+i}u_\alpha^{(i)}(x))^{k_i}\right) \\
&=  x^{-n}e^{1-(1/2)x^{-\alpha}}\sum_{k = 1}^n x^{-k\alpha}e^{-(1/2)x^{-\alpha}} \left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n (x^{\alpha+i}u_\alpha^{(i)}(x))^{k_i}\right).
\end{align*}
We proceed by taking absolute value and using the triangle inequality. Suppose now $\alpha \geq 1$, the other case is similar. By Lemma \ref{umild} we have that:
\[
x^{\alpha+i}|u_\alpha^{(i)}(x)| \leq \alpha^i i!
\]
and by Lemma \ref{expmild} we find that:
\[
x^{-k\alpha}e^{-(1/2)x^{-\alpha}} \leq \left(\frac{2k\alpha}{e\alpha}\right)^k \leq 2^k k!
\]
where we have used the inequality $k ^k \leq e^k k!$. Thus by Proposition \ref{comp} the sum can be bounded by $(3\alpha)^n n!$. Finally, by Lemma \ref{expmild}, we have:
\[
x^{-n}e^{1-(1/2)x^{-\alpha}} \leq e \left(\frac{2n}{e\alpha} \right)^{n/\alpha} \leq e (2/\alpha)^{n/\alpha} (n!)^{1/\alpha},
\]
using that $\alpha \geq 1$ to obtain $(2/\alpha)^{1/\alpha} \leq 2$.
\end{proof}

\section{parametrizations}
In this section we prove some results that indicate that the map $P_\alpha$ can be used to construct mild parametrizations. We start with a classical example that motivates this idea. We generalize this result in Proposition \ref{power}, which yields a parametrization result for definable families of curves. Proposition \ref{weakpower} is more general, but we obtain a $(1/\alpha + 1)$-mild map in that case.

\begin{definition}[Mild parametrization]
Let $X$ be a subset of $\R^n$. A $C$-mild parametrization of $X$ is a finite collection of $C$-mild maps $\{\phi_i: (0,1)^m \to X \mid i = 1,\ldots,N\}$ such that $X$ is covered by the images of these maps. If $X_T$ is a family of subsets of $\R^n$, then a uniform $C$-mild parametrization is a finite collection of families of $C$-mild maps $\{\phi_i: T \times (0,1)^m \to X_T \mid i = 1,\ldots,N\}$. That is: there exist $A$,$B$ and $C$ such that for any $t \in T$ the maps $\phi_{i,t}$ are $(A,B,C)$-mild and $X_t$ is covered by the union of all their images.
\end{definition}

\subsection{Yomdin's example}\label{sec41}
Consider the family of hyperbolas in $(0,1)^2$ given by $xy = \epsilon^2$, with $\epsilon \in (0,1)$. There is no uniform $0$-mild parametrization for this family (see \cite[Section 3.2]{ex}). We will show that it has a $1/\alpha$-mild parametrization consisting of three charts. We will use the map $P_\alpha$ as a power substitution, similarly to the map $x \mapsto x^2$ in \cite[Lemma 4.2]{ex} and more generally $x \to x^r$ in \cite[Proposition 4.1.5]{unif}.

First, consider the family as the graph of the map $f_\epsilon(x) = f(\epsilon,x) = \epsilon^2/x$ on the interval $\epsilon^2 < x < 1$. Now, on this interval, the first order derivative (with respect to $x$) is not uniformly bounded as $x \to \epsilon^2$. To this end we divide the domain in three parts: $\epsilon^2 < x < \epsilon$, $x = \epsilon$ and $\epsilon < x < 1$. Changing variables, the first case becomes the third case and the second case is trivial. Hence we proceed on the interval $\epsilon < x < 1$.

Let $C$ be the set $\{ (\epsilon,x) \in (0,1)^2 \mid \epsilon < x < 1\}$ and let $\tilde{C}$ be the preimage under the map $P:(0,1)^2 \to (0,1)^2: (\epsilon,x) \mapsto (P_\alpha(\epsilon),P_\alpha(x))$. Then for any $\epsilon$ and $x$ in $\tilde{C}$ we have:
\[
e^{1-\epsilon^{-\alpha}} < e^{1-x^{-\alpha}} < 1 \iff \epsilon < x < 1.
\]
We claim that for any $\epsilon$ the map $(f \circ P)_{\epsilon}$ is $1/\alpha$-mild. Moreover, the constants $A$ and $B$ do not depend on $\epsilon$ (uniform mildness). To this end, note that $$(f \circ P)(\epsilon,x) = e^{2(1-\epsilon^{-\alpha})-(1-x^{-\alpha})}.$$ We use the same approach as in the proof of the mildness of $P_\alpha$. The $n$-th derivative with respect to $x$ can be bounded in absolute value by:
\[
|(f \circ P)_{\epsilon}^{(n)}(x)| \leq \sum_{k = 1}^n e^{2(1-\epsilon^{-\alpha})-(1-x^{-\alpha})} \left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n (|u_\alpha^{(i)}(x)|)^{k_i}\right).
\]
Writing the exponent as $2(1-\epsilon^{-\alpha}) - 2(1-x^{-\alpha}) + (1-x^{-\alpha})$ and using that $e^{(1-\epsilon^{-\alpha})} < e^{-(1-x^{-\alpha})}$, bounding the above sum completely reduces to the proof of Proposition \ref{main}. (Here we really used that we bounded the first order derivative.) Finally, one should revert the transformation in $\epsilon$ and map $(0,1)$ onto the domain of the obtained function. More precisely, denote  $\Gamma(f_\epsilon)$ for the graph of $f_\epsilon$, then we get:
\[
\phi: (0,1) \to \Gamma(f_\epsilon) : x \mapsto ( (1-P^{-1}_\alpha(\epsilon))x+P^{-1}_\alpha(\epsilon), \epsilon e^{-(1-x^{-\alpha})}).
\]
Note that we do not need the power substitution in $\epsilon$, as we will show in Theorem \ref{curvepara}.

\subsection{Results on compositions}\label{sec3}
We would like to generalize this example, using the results of \cite{unif}. Their pre-parametrization result (Theorem 4.3.1) leads to a uniform $C^r$-parametrization by using the power substitution $P_r: x \to x^r$. More precisely, given a map $\phi$ obtained by this result, the composition $\phi \circ P_r$ is mild (up to order $r$). Using the map $P_\alpha$, it might be possible to construct a uniform $1/\alpha$-mild parametrization, which would improve bounds on the number of rational points of bounded heights on sets that we can parametrize. We will show that $\phi \circ P_\alpha$ is $1/\alpha$-mild. This yields a uniform $1/\alpha$-mild parametrization for power-subanalytic curves.

We start with a more general class of functions defined in \cite{unif}, which also become mild after composing with $P_\alpha$.

\begin{definition}[Weakly mild functions]
Let $f \in C^\infty(U,\R)$, $A,B \in \R_{>0}$ and $C \in \R_{\geq 0}$. We say that $f$ is weakly $(A,B,C)$-mild if for any $x \in U$ and $\nu \in \N^m$:
\[
|f^{|\nu|}(x)| \leq \frac{B A^{|\nu|}(|\nu|!)^{C+1}}{x^\nu}.
\]
\end{definition}

The next result is similar to \cite[Proposition 4.1.5]{unif}. Intuitively, near $0$, $x \to x^r$ is a vanishing function of order $r$, thus is capable of rendering functions mild up to order $r$. In our case, this will be up to order $+\infty$. In the proof of the next proposition, we use that $\alpha \geq 1$, but clearly, it is also true for $0 < \alpha < 1$.

\begin{proposition}\label{weakpower}
Let $f:U \to \R$, $U \subset (0,1)$ open, be weakly $(A,B,0)$-mild and suppose that $f^{(1)}$ is weakly $(A,B,0)$-mild. Then the map $f \circ P_\alpha: P_\alpha^{-1}(U) \to \R$ is $(1+1/\alpha)$-mild.
\end{proposition}

\begin{proof}
Of course, we will use the Fa\`a di Bruno formula and the triangle inequality again. This leaves us with the task to bound:
\[
|(f \circ P_\alpha)^{(n)}(x)| \leq \sum_{k = 1}^n \frac{BA^kk!}{e^{(k-1)(1-x^{-\alpha})}} \left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n (|P_\alpha^{(i)}(x)|)^{k_i}\right).
\]
Here, we have $k-1$ in the denominator because of the additional assumption on $f^{(1)}$. From the proof of Proposition \ref{main}, we know that:
\begin{align*}
|P_\alpha^{(i)}(x)| &= \left|\sum_{l = 1}^i x^{-(l\alpha+i)}e^{1-x^{-\alpha}} \left( \sum_{i,l} B_i(l_1,\ldots,l_i) \prod_{j = 1}^i (x^{\alpha+j}u_\alpha^{(j)}(x))^{l_j}\right)\right| \\
&\leq x^{-(\alpha+1)i}e^{1-x^{-\alpha}}\sum_{l = 1}^i \left( \sum_{i,l} B_i(l_1,\ldots,l_i) \prod_{j = 1}^i (x^{\alpha+j}|u_\alpha^{(j)}(x)|)^{l_j}\right).
\end{align*}
The sum over $l$ can be considered as the composition of an $(1,1,0)$-mild map and a $(\alpha,1,0)$-mild map, yielding a $(2\alpha,1,0)$-mild map. Using the relations for the sum over $n,k$ and Lemma \ref{expmild} we get:
\begin{align*}
|(f \circ P_\alpha)^{(n)}(x)| &\leq \sum_{k = 1}^n \frac{BA^kk!}{e^{(k-1)(1-x^{-\alpha})}}x^{-(\alpha+1)n}e^{k(1-x^{-\alpha})} \left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n ((2\alpha)^ii!)^{k_i}\right) \\
&=  x^{-(\alpha+1)n}e^{1-x^{-\alpha}}\sum_{k = 1}^n BA^kk!\left( \sum_{n,k} B_n(k_1,\ldots,k_n) \prod_{i = 1}^n ((2\alpha)^ii!)^{k_i}\right) \\
&\leq e\left(\frac{(\alpha+1)n}{e\alpha}\right)^{(\alpha+1)n/\alpha} B(2\alpha(A+1))^nn! \\
&\leq eB\left(\frac{\alpha+1}{\alpha}\right)^{(\alpha+1)n/\alpha}(2\alpha(A+1))^n (n!)^{2+1/\alpha}.
\end{align*}
\end{proof}

Following the strategy of the proof of \cite[Proposition 4.1.5]{unif} for several variables, will also yield this result for weakly mild functions in more variables. Now this result is not very satisfying and it seems that it cannot be improved in general. For $\alpha = 1$ it is equal to the bound in \cite[Lemma 77]{ccs}.

However, if $f$ is of a specific form, we can improve it. The maps we consider are the maps obtained from the pre-parametrization result of \cite{unif}. Our motivating example falls within this scope. The key observation is that these maps have a good interaction with $P_\alpha$. Indeed, the main obstruction to a better result in the proof above is that we completely factor out a power of $x$ in the estimate of $|P^{(i)}_\alpha(x)|$. We will not have to do this below. Let us be more precise about which maps are given by this parametrization result.

\begin{definition}[a-b-m functions]\label{abmdef}
A map $b:U \subset (0,1)^m \to \R$ is bounded-monomial if it is either identically zero, or is of the form $x^\mu$ for some $\mu \in \R^m$ and its image is bounded. A map $b: U \to \R^n$ is bounded-monomial if all of its component functions are. A map $f: U \to \R$ is analytic-bounded-monomial (a-b-m) if $f$ is of the from
\[
f(x) = b_j(x)F(b(x))
\]
where $b$ is a bounded-monomial map, $b_j$ a component function of $b$ and $F$ is a unit on $\im(b)$, that is: it is analytic and non-vanishing on an open neighborhood of the topological closure of $\im(b)$.
\end{definition}

It is shown in \cite[Corollary 4.2.4]{unif} that if all partial derivatives of the associated bounded-monomial map $b$ of $f$ are bounded, then $f$ and all its first order derivatives are weakly $0$-mild. Thus one could apply the previous proposition to this class of functions. In the next proposition, we use that $\alpha \geq 1$ in the proof and the statement, but it is straightforward to deduce an analogue for $0 < \alpha < 1$. One just has to compute the constant $A$.

\begin{proposition} \label{power}
Suppose that $b(x) = x^{\mu}$ is a bounded-monomial map whose first order derivatives are bounded on an open $U \subset (0,1)^m$. Let $P: (0,1)^m \to (0,1)^m$ be given by
\[
P(x_1,\ldots,x_m) = (P_\alpha(x_1),\ldots,P_\alpha(x_m)).
\]
Then $b \circ P: P^{-1}(U) \to \R$ is $(A,B,1/\alpha)$-mild with $A = 2\alpha(2mN+1)$ with $N = \max_{i = 1}^m |\mu_i|$, $B = e^{|\mu|}M^2$ and $M$ a constant that depends on $b$.
\end{proposition}

\begin{proof}
We use the same strategy as in the proof of Proposition \ref{main}: using the multivariate Fa\`a di Bruno formula. We write
\[
(b \circ P)(x) = e^{\sum_{i = 1}^m\mu_i(1-x_i^{-\alpha})} = (E \circ u_\alpha)(x_1,\ldots,x_m)
\]
where $E = \exp(x_1+\ldots+x_m)$ and $u_\alpha = (u^1_\alpha(x_1),\ldots,u^m_\alpha(x_m))$ where $u^i_\alpha(x_i) = \mu_i(1-x_i^{-\alpha})$. We may suppose that all $\mu_i$ are nonzero, otherwise the map does not depend on $x_i$ and any derivative with respect to $x_i$ is trivial. We have that:
\[
(E \circ u_\alpha)^{(\nu)}(x) = \sum_{1 \leq |\lambda| \leq n} E^{(\lambda)}(u_\alpha(x)) \sum_{s = 1}^n \sum_{p_s(\nu,\lambda)} \nu! \prod_{j = 1}^s \frac{(u_\alpha^{(l_j)}(x))^{k_j}}{k_j!(l_j!)^{k_j}}.
\]
As in the proof of Proposition \ref{main}, we rewrite the formula as follows:
\[
(E \circ u_\alpha)^{(\nu)}(x) = \sum_{1 \leq |\lambda| \leq n} \frac{1}{x^{\nu+\alpha\lambda}}E^{(\lambda)}(u_\alpha(x)) \sum_{s = 1}^n \sum_{p_s(\nu,\lambda)} \nu! x^{\nu+\alpha\lambda}\prod_{j = 1}^s \frac{(u_\alpha^{(l_j)}(x))^{k_j}}{k_j!(l_j!)^{k_j}},
\]
which equals
\[
e^{|\mu|}\frac{1}{x^\nu}e^{-(1/2)\sum_{i = 1}^m \mu_ix_i^{-\alpha}}  \sum_{1 \leq |\lambda| \leq n} \frac{1}{x^{\alpha\lambda}}e^{-(1/2)\sum_{i = 1}^m \mu_ix_i^{-\alpha}}  \sum_{s = 1}^n \sum_{p_s(\nu,\lambda)} \nu! x^{\nu+\alpha\lambda}\prod_{j = 1}^s \frac{(u_\alpha^{(l_j)}(x))^{k_j}}{k_j!(l_j!)^{k_j}}.
\]
Taking the extra factor $x^{\nu+\alpha\lambda}$ into account, using the relations on $l_j$ and $k_j$, we can bound everything concerning $u_\alpha$ by the appropriate bounds of an $(\alpha,N,0)$-mild function (see Lemma \ref{umild}). Now let $I$ be such that $x_I = \min_{i = 1}^m x_i$. Let $\mu' \in \R^m$ be given by $\mu'_i = \mu_i$ for $i \neq I$ and $\mu'_I = \mu_I - 1$. Then we have:
\[
\frac{1}{x^{\alpha\lambda}}e^{-(1/2)\sum_{i = 1}^m \mu_ix_i^{-\alpha}} \leq \frac{1}{x_I^{\alpha|\lambda|}}e^{-(1/2)x_I^{-\alpha}}e^{-(1/2)\sum_{i = 1}^m \mu'_ix_i^{-\alpha}} \leq \left(\frac{2|\lambda|}{e}\right)^{|\lambda|} e^{-(1/2)\sum_{i = 1}^m \mu'_ix_i^{-\alpha}}
\]
by Lemma \ref{expmild}. Now denote $K = e^{-(1/2)\sum_{i = 1}^m \mu'_ix_i^{-\alpha}}$, then $e^{|\mu'|}K^2 = ((\partial / \partial x_I)(b)/\mu_I) \circ P$. By our assumption on the partial derivatives of $b$, taking the maximum, this can be bounded independent of $I$. Thus we find that $K < M$ for some $M$ depending on $b$ only.

Similarly we find that
\[
\frac{1}{x^\nu}e^{-(1/2)\sum_{i = 1}^m \mu_ix_i^{-\alpha}} \leq \left(\frac{2|\nu|}{e\alpha}\right)^{|\nu|/\alpha}M.
\]
Using the multivariate version of Proposition \ref{comp} (see \cite[Corollary 2.5.1]{para}) we obtain that for any $x \in U$:
\[
|(b \circ P)^{(\nu)}(x)| \leq e^{|\mu|}M^2 (2/\alpha)^{|\nu|/\alpha}(\alpha(1+m2N))^{|\nu|} (|\nu|!)^{1+1/\alpha}.
\]
\end{proof}

As we have mentioned in the example, the fact that all first order partial derivatives of $b$ are bounded is crucial. Not only for the proof, but the statement can fail if it is not bounded. Indeed, if one does not bound the first order derivative in the example of Section \ref{sec41}, one would obtain the relation $e^{2(1-\epsilon^{-\alpha})} < e^{1-x^{-\alpha}}$, which is not sufficient to bound $e^{-2(1-x^{-\alpha})}$.

\begin{theorem}\label{abmmild}
Suppose that $f: U \to \R$ is a-b-m on an open $U \subset (0,1)^m$ such that the first order derivatives of its associated bounded-monomial map $b$ are bounded. Then $f \circ P: P^{-1}(U) \to \R$ is $1/\alpha$-mild.
\end{theorem}

\begin{proof}
This follows by Proposition \ref{power} and the fact that the unit $F$ is $0$-mild since it is analytic on an open neighborhood of $\overline{\text{Im}(b)}$ \cite[Proposition 2.2.10]{primer}. This concludes the proof by the remark below Proposition \ref{comp} and the fact the the product of $C$-mild functions is $C$-mild.
\end{proof}

Before moving to our final result, let us point out that by the method above, one can show that the parametrization of the exponential-algebraic surface on the last line of \cite[p. 507]{countpointsexp} is $1/g$-mild (improving $1+1/g$). This improves the upper bound on rational points in that paper to $c(\epsilon)(\log T)^{35+\epsilon}$.

We will now use the pre-parametrization result of \cite[Theorem 3.5]{para}, which is a slight modification of \cite[Theorem 4.3.1]{unif}, to obtain a uniform $1/\alpha$-mild parametrization of a family of power-subanalytic curves. This improves the $2$-mild parametrization of subanalytic curves of \cite{ccs}.

\begin{theorem}\label{curvepara}
If $X_T$ is a power-subanalytic family of power-subanalytic curves in $(0,1)^n$, then it has a uniform $1/\alpha$-mild parametrization.
\end{theorem}

\begin{proof}
By \cite[Theorem 3.5]{para} we obtain finitely many $f: C \subset T \times (0,1) \to [-1,1]^{n-1}$, where $C$ is an open cell in $T \times (0,1)$. The map $f$ is of the following form
\[
f(x) = b_j(t,x) F(b(t,x)),
\]
where $b_j$ is a component function of $b$, all component functions of $b$ are of the form $a(t)x^r$ for some definable function $a(t)$, $r \in \R$ and $F$ is a non-vanishing analytic function on an open neighborhood of $\overline{\im(b)}$. Moreover, $(\partial/\partial x)(b)$ is (uniformly) bounded. Consider the map
\[
P: T \times (0,1) \to T \times (0,1) : (t,x) \mapsto (t,P_\alpha(x))
\]
and set $\tilde{C} = P^{-1}(C)$. It follows that for any $t$ the map $(f \circ P)_t$ is $(A,B,1/\alpha)$-mild, where $A$ and $B$ are independent of $t$ (using the same technique as in the proof of Proposition \ref{power}, using the fact that $a(t)x^r$ and its first order derivative are uniformly bounded). Since in the case of curves the walls of the cell bounding the variable $x$ only depend on $t$, for any $t$ they are automatically $(1,1,0)$-mild.
\end{proof}

It would be interesting to know whether the techniques in this paper can be applied to the cellular maps in \cite{ccs} to obtain a uniform $1/\alpha$-mild parametrization of families of subanalytic sets (of arbitrary dimension). For power-subanalytic sets, one does not really require an analogue of \cite[Proposition 4.2.6]{unif}, as mentioned in the introduction of this section. One could argue by induction instead. The obstacle in that case is the fact that $P_\alpha^{-1}(C)$ is not power-subanalytic.

\bibliographystyle{alpha}
\bibliography{Mildlib}{}
\end{document}


TITLE: Prove that the integral $\int_a^b \frac{\sin(x)}{x}dx$ is bounded uniformly.
QUESTION [5 upvotes]: How do I show that exists a constant $M>0$ such that, for all $0\leq a \leq b < \infty$,
$$\left|\int_a^b \frac{\sin(x)}{x}dx\right| \leq M.$$
I just read on Richard Bass book's that is enough to prove the uniformly boundeness of the integral $\int_0^b \frac{\sin(x)}{x}dx$, but I can't see why...

REPLY [0 votes]: The way I will approach it is to prove that $\lim_{x \to \infty}G(x)\le G(\pi)$, where $G(x) is \int_{0}^{x}\frac{sin(y)}y dy $. The reason being if $f(y)=\frac{sin(y)}y$, then $\int_{r \pi}^{(r+2)\pi}f(y)dy\leq0$ for odd $r$
The rest is trivial


TITLE: Finite Ordinals and Natural Numbers
QUESTION [3 upvotes]: I'm studying set theory and I'm focusing on von neumann ordinals. I've built an understanding of the reasoning that brings to the set-theoretic construction of the natural numbers whose soundness I'm questioning. I should stress that I find important point 2 to be the starting point of this construction. I'm going to outline it:

Let's assume that we have already defined ordinals. We know that every successor of an ordinal is still an ordinal.
Starting from $0 = \emptyset$, which is the smallest ordinal, we can construct some ordinals by finding iteratively (but finitely) the successor ordinal of the previous one. That is $$0 = \emptyset\\
1 = \{\emptyset\}\\
2 = \{\emptyset,\{\emptyset\}\}\\
3 = \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}\\\dots\\
n = \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\},\dots\}\\\dots$$
we know that these ordinals exist, right?. What we don't know is if there exist a set containing them.
We define the class of finite ordinals with the following formula: $$FON(x) = ON(x)\wedge\forall y[(y \le x) \wedge (y \neq 0) \Rightarrow \exists z\{y = z \cup \{z\}\}]$$
So finite ordinals are those successor ordinals whose elements are all successor ordinals. We have that each ordinals $n$ we constructed above satisy this formula. Here is the first question: can we say the converse? Can we say that every $x$ such that $FON(x)$ is explicitely definable (with a finite iteration) as for $n$? However our new objective is to identify natural numbers and finite ordinals, and we want to prove that the class finite ordinals is a set $\omega$ (which we will eventually identify with $\mathbb{N}$).
We introduce the axiom of infinity: $$\exists I(\emptyset \in I \wedge \forall x \in I((x \cup \{x\}) \in I))$$
and we'll call $I$ an inductive set. We want to show that every finite ordinal belongs to every inductive set. If the equivalence, conjectured in the previuos point, between finite ordinals and ordinals iteratively constructed from $\emptyset$ were to be true, then this would follow easly. Now, thanks to the axiom scheme of specification, we can extract from $I$ the subset of all the elements of $I$ that are finite ordinals. So we define $$\omega = \{x \in I : FON(x)\}$$
We then have that, since every finite ordinal belongs to every inductive set, $$FON(x) \Rightarrow x \in I \Rightarrow x \in \omega$$
on the other hand we have $$x \in \omega \Rightarrow FON(x)$$
by the definition of $\omega$. So finally we get: $$\omega = \{x : FON(x)\}$$

Is this line of reasoning solid? Can we fill the holes in it?
Thanks

REPLY [1 votes]: We have the following
Proposition: An ordinal $\alpha$ is a natural number if, and only if $\alpha=0$ or is a successor ordinal and for each ordinal $\beta<\alpha$, $\beta=0$ or $\beta$ is a successor ordinal.
Demonstration:
$\Longrightarrow$) By induction over the natural numbers. Let
$$A=\{n\in\omega\;|\;(n=0\text{ or }(n\text{ is a successor ordinal}\text{ and }\text{for each }\beta<n,\;\beta=0\text{ or }\beta\text{ is successor})\}$$

It is evident that $0$ belongs to $A$
Let $n$ be a natural number that belongs to $A$. Then $S(n)$ is a successor ordinal. If $\beta<S(n)$, then $\beta\in n$ or $\beta=n$. In any of those cases $\beta=0$ or $\beta$ is a successor ordinal.

$\Longleftarrow$) Let $\alpha$ be an ordinal which satisfies the property of the statement. By the trichotomy property, exactly one of the following possibilities is given: $\alpha<\omega,\;\alpha=\omega$ or $\omega<\alpha$. If $\alpha=\omega$, then $\alpha$ is not equal to $0$ nor a successor ordinal. If $\omega<\alpha$, then $\omega$ is an ordinal less than $\alpha$ that is not $0$ nor a successor ordinal. The only remaining possibility is for $\alpha$ to be less than $\omega$, that is, $\alpha\in\omega$ so $\alpha$ is a natural number.
So now to you questions. For $3$ I must agree with Max's answer, nothing else should be added.
If you are curious about the actual construction of the set of the natural numbers, please check my answer to this question. After constructing the natural numbers, proving the principle of induction over $\omega$ and the principle of trichotomy of the ordinal numbers, you can immediately give an answer to $4$ via the proposition I just proved before.
Note that I'm also supposing that $\omega$ is not a successor ordinal. Indeed, $\omega$ is different from $0$, and if it were a successor ordinal, then there would exist a natural number $n$ such that $\omega=S(n)$, which cannot be possible, for various reasons: one of them, is that $S(n)$ would be a natural number that is an element of itself. Therefore, $\omega$ is a limit ordinal. But also it is the first limit ordinal, since we have just proved that every element in $\omega$ is $0$ or a successor ordinal.
Hope my answer, although late, is still helpful.


TITLE: How come lenses alter the path of photons?
QUESTION [1 upvotes]: From what I know, photons are theorized particles and believed to be massless (just energy) and travel at the speed of light. How come a lens, which is an object made of atoms, can bend a light path?
I would expect the lens to heat up but not alter the paths of massless particles.  Could someone explain in simple terms?

REPLY [0 votes]: Photons obey the rules of quantum electrodynamics. To explain this I will need to teach you how to use complex numbers.
A quick tutorial on complex numbers
Complex numbers are pairs of numbers $(a,b)$ which add by the obvious rule $(a, b) + (c, d) = (a + b,\; c+d)$ and multiply by the not-at-all-obvious rule $(a, b) \cdot (c, d) = (ac - bd,\; ad + bc),$ chosen so that $(0, 1) \cdot (0, 1) = (-1, 0)$ and therefore there is a "square root of -1." If you really work out how these rules interact you can find out that the algebra is the same as the 2x2 real matrix algebra $$(a, b) \leftrightarrow \begin{bmatrix}a&-b\\b&a\end{bmatrix},$$which has  can think of as a scaled rotation matrix:$$\begin{bmatrix}a&-b\\b&a\end{bmatrix} = \sqrt{a^2 + b^2} \begin{bmatrix}\cos\theta& -\sin\theta\\\sin\theta &\cos\theta\end{bmatrix}  = \sqrt{a^2 + b^2} R(\theta) \text { , for some }\theta.$$ Here $R(\theta)$ is the 2D rotation matrix by an angle of $\theta$ radians; it is a full rotation for $\theta = 2\pi$ for example.
Adding two complex numbers therefore is like the "vector sum" of the two "arrows" that point from the origin to the numbers on the complex plane $(x, y)$, whereas multiplying by a complex number both scales the complex plane out and rotates it. (More specifically, each complex number $(a, b)$ scales-and-rotates the entire plane so that the point $(1,0)$ on the $x$-axis gets mapped to $(a, b)$.)
In many ways, rotations are the simplest "wavey" things, so it's not too surprising that when we want to describe the waviness of the quantum world we turn to some sort of rotation to do it.
Complex numbers as amplitudes
The core rules of quantum electrodynamics are very simple:

Each way that something can happen is represented by a complex number, called its "amplitude."
If something can happen many different ways, you add together the different amplitudes of the different possibilities.
If something needs multiple things to happen, then you multiply together the different amplitudes of these different possibilities.
When you're done, the square of the scale factor of the amplitude $a^2 + b^2$ is the probability that this thing will happen.

Now you need a rule for a particular path, which in the photon's case is really easy: If the photon travels a distance $\ell$ in a time $\tau$ and has frequency $f$ then its amplitude is $\frac1\ell ~ R(2\pi f\tau).$ We will ignore the $1/\ell$ prefactor but it leads (through all of the above) to a $1/r^2$ drop in light's intensity as you go a certain distance, which keeps the flux of energy through successive spheres (which have surface area $4\pi r^2$) constant as a burst of light goes through bigger and bigger spheres. So you can imagine that this has to do with conservation of energy.
Fermat's principle as a special case
Now these rules state that if I have a detector in one medium where light goes slower and an emitter outside where light goes faster, we must consider all straight baths from the emitter to any point on the surface between them, and then from the surface to the detector. We must sum all of these up.
Let's say that the surface is the points $(x, 0)$ on the plane, the detector is at point $(0, -D)$, and the emitter is at point $(A, B)$. Each path will then have the amplitude which goes like $R(2\pi f \sqrt{(A - x)^2 + B^2}/v_\text{out})~R(2\pi f \sqrt{x^2 + D^2} / v_\text{in}),$ where $v_\text{out}$ is the speed of light outside the medium where the detector is, and $v_\text{in}$ is the speed of light inside. Since rotating twice is the same as adding the angles, we can combine these into: $$R\left(2\pi f \left[\frac{\sqrt{(A - x)^2 + B^2}}{v_\text{out}} + \frac{\sqrt{x^2 + D^2}}{v_\text{in}}\right]\right).$$That's better, but still... Yuck! Because we have to add together a lot of these! Well, we have a special trick up our sleeves. ;-)
The trick is that when you're adding up something which is rapidly spinning around in circles like this, most of the little arrows you're adding up point in all the directions of the compass, cancelling out. Therefore the only way that these amplitudes can sum up to anything big (meaning a non-negligible probability when we compute the squared scale factor!) is if the stuff on the inside isn't changing much. This usually happens when the stuff is at an extremum, either a minimum or maximum, because there's "no lower" that it can go.
Combined with our earlier expression $R(2\pi f \tau)$ this leads to a fact called Fermat's principle: light takes the path of shortest time. In fact we've seen that light takes all paths, but we're saying now that any paths which are not near a shortest-time path all cancel each other out anyway, so it doesn't matter much to the final amplitude if you insert a photon-absorber which blocks those paths completely!
To compute an extremum path in physics, we use calculus to take a derivative of the angle above, and set it equal to 0. $$\frac{d\theta}{dx} = - \frac{A - x}{v_\text{out}\sqrt{(A - x)^2 + B^2}} + \frac{x}{v_\text{in} \sqrt{x^2 + D^2}} = 0.$$ This identifies a special point $x$ on the surface. The triangle it makes with the outside of the medium is a right triangle with height $B$ and base $A - x$ and therefore if we measure $\phi_\text{out}$ from the "normal vector" that is perpendicular to the surface we find $(A - x) / \sqrt{(A - x)^2 + B^2} = \sin\phi_\text{out}.$ Likewise we find the other term to be $\sin\phi_\text{in},$ again measuring the angle from the normal vector perpendicular to the surface. We therefore find:$$\frac{\sin\phi_\text{out}}{v_\text{out}} = \frac{\sin\phi_\text{in}}{v_\text{in}}.$$This is also called Snell's law.
In summary
In summary, lenses alter the path of photons because photons take all paths, but since their underlying physics is "wavey" different paths can "interfere." A photon will appear to take only those paths which feature lots of "constructive interference," in the sense that if we block other paths we do not diminish the intensity of light reaching our detector by very much. The paths of constructive interference are the ones where the time taken to travel along "nearby" paths is roughly the same. This leads to light usually taking the "shortest-time-path" and a couple of constructive paths immediately around it.
Because the speeds of light are different in the two different media, the shortest-time-path becomes different in the presence of a lens, and bends. It's the same as if you want to rescue someone who's drowning and is diagonal from you (relative to the shore): you don't run straight into the water and then turn at a right angle to swim along the shore; in fact it's much better to run along the beach parallel to the shore and then turn at a right angle to swim to them, and if you want to be as fast as possible you also don't run in a straight line to them immediately jumping in the water. Ideally you compromise between the latter two: you know that you can run on the beach faster than you can swim, so you ideally run in a bent line, staying on the beach for a little longer to get a little closer, before you jump into the water and start swimming.


TITLE: Can we estimate $P(x)$ using $P(1)$?
QUESTION [0 upvotes]: Given a polynomial $P(x)$, is it possible to estimate/lower bound/upper bound the value of $P(k)$ for some $k \in \mathbb{N}$ if we know $P(1)$?
We can also assume $P(x)$ has only natural coefficients and is only taken over $x \in \mathbb{N}$ if that helps.

REPLY [2 votes]: No if you assume that the coefficients can be in $\mathbb{Z}$, as you can just consider for example the family
$$P_n(x)=(x-1)^n$$
You clearly have no control whatsoever on the growth rate, but all share the same value $$P_n(1)=0$$
In the case of positive integers, you too cannot find any upper bound, as the family of monomials
$$P_n(x)=x^n$$
have similar properties as the one we said above, but for any polynomial $P(x)=\sum_{i=1}^na_ix^i$with positive coefficiens, it holds that
$$P(x)\ge P(1),\quad\forall x\ge 1$$
because $x^i\ge 1 $ if $x\ge 1$ and so
$$\sum_{i=1}^na_ix^i\ge \sum_{i=1}^na_i(1)^i=\sum_{i=1}^na_i=P(1)$$
Where the positivity of the coefficients is needed to pass from $x^i\ge 1$ to $a_ix^i\ge a_i(1)^i$.


TITLE: Daletskii-S.Krein formula proof
QUESTION [2 upvotes]: I've came across to the following equation, known as Daletskii-S.Krein formula. Consider a sufficiently smooth function $h : \mathbb{R} \rightarrow \mathbb{R}$, and let $\mathbf{A}_t = \mathbf{A} + t\mathbf{T}$, where $t = [0,1]$, and both $\mathbf{A}$ and $\mathbf{T}$  are self adjoint operators in a hilbert space $\mathfrak{H}$. Then
$$
h(\mathbf{A}_t)-h(\mathbf{A}) = t\int\limits_{\sigma(\mathbf{A})}\int\limits_{\sigma(\mathbf{A}_t)} \phi(\lambda,\mu) dE^{\mathbf{A}}\mathbf{T}dE^{\mathbf{A}_t}
$$
or when taking $t \rightarrow 0$,
$$
\left. \dfrac{d h(\mathbf{A}_t)}{t}\right|_{t=0} = \int\limits_{\sigma(\mathbf{A})}\int\limits_{\sigma(\mathbf{A})} \phi(\lambda,\mu) dE^{\mathbf{A}}\mathbf{T}dE^{\mathbf{A}}
$$
My question is how to prove the equation above. I found this equation in
scienceDirect paper mentioned without proof. The main reference of this formula (ref 18) is difficult to find right now. Any help will be appreciated.
Cheers.

REPLY [0 votes]: As remarked in user92646's answer, the proof is quite involved, but as usual, everything is a lot easier if $h$ is a polynomial. First note that it suffices to consider $h(\lambda)=\lambda^{n+1}$. In this case, $\phi(\lambda,\mu)=\sum_{j+k=n}\lambda^j \mu^k$.
If the integrand $\phi$ is of the form $\phi(\lambda,\mu)=f(\lambda)g(\mu)$, then the double operator integral is simply
$$
\int_{\sigma(X)}\int_{\sigma(Y)}f(\lambda)g(\mu)\,dE^X(\lambda)TdE^Y(\mu)=f(X)Tg(Y).
$$
For $\phi$ as above, this gives
$$
\int_{\sigma(A)}\int_{\sigma(A_t)}\phi(\lambda,\mu)\,dE^{A}TdE^{A_t}=\sum_{j+k=n}A^jT(A+tT)^k.
$$
On the other hand, one can show by induction that
$$
(A+tT)^{n+1}-A^{n+1}=t\sum_{j+k=n}A^j T(A+tT)^k.
$$
When $h$ is not necessarily a polynomial, one can still approximate it by polynomials and $\phi$ by linear combinations of elementary tensors. the hard work is then to show that everything (especially on the right-hand side) converges nicely so that the equation remains valid.


TITLE: Cardinality of subsets of $\mathbb{N}$ with fixed asymptotic density
QUESTION [5 upvotes]: For a set $S\subset \mathbb{N}$, let
$$a(S)=\lim_{n\rightarrow\infty}\frac{\#\{s\in S\>|\>s\le n\}}{n}$$
be the limiting asymptotic density of $S$ in the natural numbers if the limit exists, and $a(S)=0$ if it does not.
Now take $0<\alpha<1$ and let
$$A_\alpha = \{S\subset \mathbb{N}\>|\>a(S)=\alpha\}$$
be the set of all subsets of $\mathbb{N}$ with asymptotic density $\alpha$.
Is $A_\alpha$ countable?

REPLY [8 votes]: For each $n\in\mathbb N$ choose one element from the set $\{2n-1,2n\}$. Each of the $2^{\aleph_0}$ sets you can get this way has asymptotic density $\frac12$.
P.S. More generally: If $S$ has density $\alpha$ and $T$ has density zero, then the symmetric difference $S\triangle T$ has density $\alpha$. Of course there are continuum many sets of density zero, e.g., the subsets of a given infinite set of density zero. Thus, by fixing $S$ and varying $T$, we get continuum many sets of density $\alpha$.


TITLE: What is the Bruhat decomposition of the affine Grassmannian?
QUESTION [6 upvotes]: We define the affine Grassmannian to be the quotient $Gr = GL_n(\mathbb{C}((t)))/GL_n(\mathbb{C}[[t]])$ where $\mathbb{C}((t))$ is the field of formal Laurent series and $\mathbb{C}[[t]]$ is the ring of formal power series. (The affine Grassmannian can be defined more generally, but here we restrict to a special case.) If we let $B$ be the Borel subgroup of upper triangular matrices in $GL_n(\mathbb{C})$, $T$ a maximal torus, then the Weyl group $W=N(T)/T$ is just $S_n$. Let $\widetilde{W} = \mathbb{Z}^{n-1}  \rtimes W$ denote the affine Weyl group. Then for $i = 1, 2,...,n-1$ the affine permutations in $\widetilde{W}$ correspond to the usual permutation matrices in $GL_n(\mathbb{C})$, namely the identity matrix with columns $i$ and $i+1$ interchanged. The matrix for the affine permutation $s_0$ has ones along the diagonal in rows $2, 3, ..., n-1$, has $t$ in the right hand corner, and $t^{-1}$  in the bottom left corner. Let $I$ denote the Iwahori subgroup, that is, the inverse image of $B$ under the reduction map $GL_n(\mathbb{C}((t))) \rightarrow GL_n(\mathbb{C})$. Then $I$ is the set of upper triangular matrices mod $t$. I read somewhere that $GL_n(\mathbb{C}((t)))$ has a decomposition
$GL_n(\mathbb{C}((t))) = \cup IwGL_n(\mathbb{C}[[t]])$
where $w$ varies across the affine permutation matrices. This decomposition is supposed to induce the Bruhat decomposition of the affine Grassmannian into Schubert cells. Now something here is wrong. Since $I \subset GL_n(\mathbb{C}[[t]])$, and the determinant of any affine permutation matrix is 1 or -1, we have that for any $w \in \widetilde{W}$ the determinant of any matrix in $IwGL_n(\mathbb{C}[[t]])$ has power series determinant, but the matrix
$\left(\begin{array}{cc}
t^{-1} & 0 \\

0   & t^{-1} \\
\end{array}\right)$
is in $GL_n(\mathbb{C}((t)))$ with determinant $t^{-2}$ and inverse
$\left(\begin{array}{cc}
t &  0 \\

0 & t \\
\end{array}\right).$
So, my question is, what is wrong here? What is the correct decomposition and indexing set?

REPLY [3 votes]: Your identification of the Affine Weyl Group  with elements of $ G(\mathbb{C}((t)) $ is wrong.
Any co-character $\lambda:\mathbb{C}^*\to T$ where $T$ is a chosen maximal torus can be regarded as an element of $ G(\mathbb{C}((t))) $. If you choose $P$ to be the abelian group generated by the dominant coroots (which is acted upon by W) the semi-direct product with $W$ is isomorphic to the Affine Weyl Group. Now these elements, for example $t\mapsto (t^n,t^{-n})$, give you the desired Bruhat decomposition.
This is explained in the paper of Iwahori and Matsumoto: on some bruhat decomposition... from page 24 on.


TITLE: Equivalent conditions of prime ideals in Lie algebra
QUESTION [2 upvotes]: I am studding on Lie algebra and prime ideals, but some problems rise up to me.
please look on this and try to help me.
Definition: An ideal $P$ of $L$ is called prime if $[H, K] \subseteq P$ with $H, K$ ideals of $L$ implies $H \subseteq P$ or $K \subseteq P$.
THEOREM : Let $P$ it be an ideal of L. Then the following conditions are equivatent}:
i) $P$ is prime.
ii) If $[a, H]\subseteq P$ for $a \in L$ and an ideal $H$ of $L$, then either $a\in P$ or $H\subseteq P.$
iii) If $[a, <b^{L}>]\subseteq P$ for $a, b\in L$, then either $a\in P$ or $b\in P.$
PROOF.
$\mathrm{i}$)
$\Rightarrow \mathrm{i}\mathrm{i}\mathrm{i}$). For each $a\in L,$
$$
<a^{L}>=\sum_{i=0}^{\infty} V_{i},
$$
where $V_{0}=(a)$ and $V_{i} [(a),\underline{{L],\ldots,}_{i-times}}L]$. If $[a,\ <b^{L}>]\subseteq P$, we assert that
$$
$$
$[V_{i},\ <b^{L}>]\subseteq P$ for all $i\geq 0$. In fact, it is true for $i=0$. Let $i\geq 1$ and assume that the assertion is true for $i-1$. Then
$$
[V_{i},\ <b^{L}>]=[[V_{i-}{}_{1}L],\ <b^{L}>]
$$
$$
\subseteq[[V_{i-1},\ <b^{L}>],\ L]+[V_{i-1},\ [L,\ <b^{L}>]]
$$
$$
\subseteq[P,\ L]+[V_{i-1},\ <b^{L}>]\subseteq P_{:}
$$
Thus we have the assertion.

It follows that
  $$
[<a^{L}>,<b^{L}>]\subseteq P.
$$
  Since $P$ is prime, either $<a^{L}>\subseteq P$ or $<b^{L}>\subseteq P$ and so $a\in P$ or $b\in P.$

$\mathrm{i}\mathrm{i}\mathrm{i})\Rightarrow \mathrm{i}\mathrm{i})$ . Let $a\in L\backslash P$ and let $H$ be an ideal of $L$ such that $[a,\ H]\subseteq P$. For any $b\in H, [a,\ <b^{L}>]\subseteq P$ since the ideal $<b^{L}>$ is contained in  $H$. As $a\not\in P,$ iii) implies $b\in P$. Hence $H\subseteq P.$

$\mathrm{i}\mathrm{i})\Rightarrow \mathrm{i})$ . Let $H, K$ be ideals of $L$ such that $[H,\ K]\subseteq P$ and $H\not\subset P$. Since $[a,\ K]\subseteq P$ for any $a\in H\backslash P$, we have $K\subseteq P$ by ii). Therefore $P$ is prime.

My questions( I need more explanation about this points which have color) :-
1) It follows that $[<a^{L}>,<b^{L}>]\subseteq P.$ (why this true) ??
2) Since $P$ is prime, either $<a^{L}>\subseteq P$ or $<b^{L}>\subseteq P$ and so $a\in P$ or $b\in P.$ (why this true) ??
3) Since $[a,\ K]\subseteq P$ for any $a\in H\backslash P$ (why this true) ??

REPLY [2 votes]: The source is Naoki Kawamoto, On Prime Ideals of Lie Algebras (Hiroshima Math J. 4 (1974), 679--684), Theorem 1.
To quote the paper and to correct your typesetting: $$\langle a^L \rangle = \sum_{i=0}^\infty V_i \qquad \text{where} \qquad V_0 = (a) \qquad \text{and} \qquad V_i = [\ldots[(a),\underbrace{L],\ldots,}_i\ L]. \tag{1}$$
That is, $V_1 = [(a),L], \quad V_2 = [[(a),L],L], \quad V_3=[[[(a),L],L],L],\quad$ etc.
1) To show $[\langle a^L \rangle,\langle b^L \rangle] \subseteq P$ it suffices to show $[V_i, \langle b^L \rangle] \subseteq P$ for each $i \geqslant 0$. This sufficiency follows from $(1)$. Showing $[V_i, \langle b^L \rangle] \subseteq P$ is what is done in the proof. To summarize the argument: the case $i=0$ is true by assumption, and the rest follows by induction and the Jacobi identity.
2) Since $P$ is prime, either $\langle a^L\rangle \subseteq P$ or $\langle b^L \rangle \subseteq P$ (this is the definition of prime). If $\langle a^L \rangle \subseteq P$ then we have $a \in \langle a^L \rangle \subseteq P$, so $a \in P$. In the same way, if $\langle b^L \rangle \subseteq P$ then $b \in P$. So $a \in P$ or $b \in P$.
3) $[a,K] \subseteq P$ for any $a \in H\setminus P$ is true by the first assumption on $H$ and $K$ made in the preceding sentence, that is $[H,K] \subseteq P$. Indeed, for $a \in H\setminus P$ we have $a\in H$ and hence $[a,K] \subseteq [H,K] \subseteq P$.

To answer the questions in the comment:

What is the meaning of $(a)$?

$L$ is a Lie algebra over a field $\Phi$. For any element $a$ of $L$, $\langle a^L \rangle$ is defined to be the smallest ideal of $L$ containing $a$. An ideal $I$ is a $\Phi$-vector subspace of $L$ satisfying $[I,L] \subset L$. So what is $\langle a^L \rangle$ as a $\Phi$-vector space? Of course it must contain $a$, and all its scalar multiples, i.e. the $1$-dimensional $\Phi$-vector subspace $(a) := \Phi a \subset \langle a^L \rangle$. But if it contains $(a)$, then (by definition of ideal) it must also contain $[(a),L]$, and hence $[[(a),L],L]$, etc. Because it is a $\Phi$-vector space it must contain their sum. This leads to $(1)$.

How you use the Jacobi identity in the first one?

It is used to go from line 1 to line 2 in the display equation: $[[V_{i-1},L], \langle b^L \rangle]$ is a set consisting of $[[x,y],z]$ such that $x \in V_{i-1}, y \in L, z \in \langle b^L \rangle$. By the Jacobi identity $(I)$ and antisymmetry $(II)$ we have:
$$\begin{align*}[[x,y],z] &= -[[y,z],x] -[[z,x],y] \tag{I} \\
& = [[x,z],y] + [x,[y,z]] \tag{II} \\ &\in [[V_{i-1},\langle b^L \rangle],L] + [V_{i-1},[L,\langle b^L \rangle]].\end{align*}$$
Hence $[[V_{i-1},L], \langle b^L \rangle] \subseteq [[V_{i-1},\langle b^L \rangle],L] + [V_{i-1},[L,\langle b^L \rangle]]$.

How can we prove that if $\langle b^L \rangle$ is contained in $H$ then $[a,\langle b^L \rangle] \subseteq [a,H]$?

This is by definition, or the meaning of the notation: $[a,\langle b^L \rangle]$ is a set consisting of $[a,y]$ with $y \in \langle b^L \rangle$ and $[a,H]$ is a set consisting of $[a,z]$ with $z \in H$. Since $y \in \langle b^L \rangle \subseteq H$, we have $y \in H$, so $[a,y] \in [a,H]$, hence $[a,\langle b^L \rangle] \subseteq [a,H]$

How can we prove that if $a \in H$ then $[a,K] \subseteq [H,K]$?

Same/similar reason: $[H,K]$ is a set consisting of $[x,y]$ with $x \in H$ and $y \in K$, and $[a,K]$ is a set consisting of $[a,z]$ with $z \in K$. Since $a \in H$, we have $[a,z] \in [H,K]$, so $[a,K] \subseteq [H,K]$.


TITLE: Hyperbolic length of curve that does not enter a collar
QUESTION [2 upvotes]: Let $\Sigma$ be a compact surface of genus at least $1$ with one boundary component, equipped with a hyperbolic metric so that the boundary is geodesic. There is a version of the collar lemma that says there is a collar neighbourhood $C$ of the boundary such that no simple closed geodesic on $\Sigma$ enters $C$.
Given a curve, I am interested in measuring what length of it lies outside $C$. More precisely, I am curious about the following: does there exist a constant $d>0$ such that, if $\gamma$ is an essential simple closed curve (not nullhomotopic and not homotopic to the boundary component), then $$\ell(\gamma|_{\Sigma\backslash C})+d \geq \ell(\tilde{\gamma})$$ Here, $\ell$ is the hyperbolic length, $\tilde{\gamma}$ is the unique simple closed geodesic homotopic to $\gamma$, and, to be clear, $\ell(\gamma|_{\Sigma\backslash C})$ refers to the length of the restriction of $\gamma$ to $\Sigma\backslash C$ (this is a union of disconnected curves). Here $d$ should depend on the hyperbolic metric and the choice of $C$, but not the homotopy class of the curve.
The reason I add the "$+d$" is that one could cook up the following example: take a curve that enters $C$ once, and then replace the region that enters $C$ with a straight line connecting the boundary points at which the curve crosses. We then get a closed curve homotopic to $\tilde{\gamma}$, and the length is at most $\ell(\gamma|_{\Sigma\backslash C})+d$, where $d=\ell(\partial C)$.
It seems true for just about any example I draw, but any proof I attempt to write down becomes terribly buggy and complicated.

REPLY [4 votes]: There is no such constant $d$.  The "reason" is that geodesic laminations exist, and are approximated by simple closed curves.
Thought process (which can be ignored):

Suppose that $\tau$ is a train track in $\Sigma$.  Let $R$ be a
rectangle embedded in $\Sigma - \tau$ with one side running along
$\partial \Sigma$ and one side running along a branch $b$ of $\tau$.
If $\gamma$ is carried by $\tau$ then we can use $R$ to perform a
homotopy of $\gamma$; we take all of the arcs of $\gamma$ running
along $b$ and isotope a subsegment of each, along $R$ into $C$.  We
call the sides of $R$ in $\partial \Sigma$ and in $b$ "horizontal" and
we call the other two sides "vertical".
Let $\gamma'$ be the result of the homotopy. After the homotopy we
have added many copies of the vertical sides (to the length of
$\gamma' - C$) and subtracted the same number of many copies of the
segment along $b$.
So if we can find a surface $\Sigma$ equipped with a track $\tau$
where $R$ has short verticals and long horizontals, we are done.

The resulting proof:
Suppose that $\Sigma'$ is a closed surface with a very short geodesic curve $\alpha$. Let $\beta$ and $\beta'$ be distinct, disjoint, simple geodesic loops that cross $\alpha$ exactly once.  It will be useful to arrange for $\beta$ to be separating, and $\beta'$ to be non-separating.
Let $C_\alpha$ be a collar of $\alpha$ where $\partial C_\alpha$ is much smaller than the "height" of $C_\alpha$. Since $\alpha$ is short, the curves $\beta$ and $\beta'$ fellow travel, very closely, inside of $C_\alpha$.  By Dehn twisting about $\beta'$ we can now produce a family of curves $\gamma_n$ that are (a) disjoint from $\beta$ and (b) cross $\alpha$ exactly $n$ times.  We produce $\Sigma$ by cutting along $\beta$ and throwing away the component that does not contain the $\gamma_n$.
Let $C_\beta$ be the given collar of $\partial \Sigma = \beta$. We now perform a homotopy of $\gamma_n$ (supported in the remains of $C_\alpha$) so that the $n$ long arcs of $\gamma_n \cap C_\alpha$ lie inside of $C_\beta$.  The length of $\gamma_n - C$ is less than that of $\gamma_n$ by (approximately) $n$ times the difference between the height of $C_\alpha$ and the length of $\partial C_\alpha$.


TITLE: Number of Possible Ways to Distribute Apples
QUESTION [0 upvotes]: I had this problem in a local math competition and was wondering how to solve it, even though I know the answer.
Bob has 24 apples. He want to give some apples to two of his friends Jill and Patty. He wants each of the three friends (counting himself) to end up with at least 2 apples each. How many possible ways could he distribute these apples (without breaking any)?
I tried permutations, combinations, and the multiplication rule but to no avail. Help would be greatly appreciated.
Thank you in advance!

REPLY [1 votes]: If each person gets $2$ apples, then there remain $18$ apples to be distributed. Let $X_1, X_2, X_3$ be the number of additional apples that the first, second, and third friends get, respectively.
With these definitions, we wish to find the number of nonnegative integer valued vector solutions $(X_1,X_2,X_3)$ to $X_1 + X_2 + X_3 = 18$, $X_1, X_2, X_3 \geq 0$.
The result is well known and often referred to as the (nonnegative) solution to the "stars and bars" problem: ${18 + 3 - 1} \choose {3-1}$ $=$ $20 \choose 2$ $=190$ ways.


TITLE: Integrating $\int_0^{2\pi} \frac1{a\cos(t)+b\sin(t)+c}dt$ with $\sqrt{a^2+b^2}=1<c$
QUESTION [1 upvotes]: Let $a,b,c\in\mathbb{R}$ such that $\sqrt{a^2+b^2}=1<c$.
Find $I:=\int_{0}^{2\pi} \frac{1}{a\cos(t)+b\sin(t)+c}dt$.
So, I set $z=e^{it}$ and then $dz=ie^{it}dt$ and so $\frac{dz}{iz}=dt$. Therefore,
$\begin{align*} I & =\frac{1}{i}\int_{|z|=1} \frac{dz/z}{a\cdot\frac{z+z^{-1}}{2}+b\cdot\frac{z-z^{-1}}{2i}+c} \newline &=\frac{2}{i}\int_{|z|=1} \frac{dz}{a\cdot(z^2+1)-ib\cdot(z^2-1)+2cz} \newline &=\frac{2}{i}\int_{|z|=1} \frac{dz}{(a-ib)z^2+2cz+a+ib}\newline &= \frac{2}{i}\int_{|z|=1} \frac{dz}{(z-z_+)(z-z_-)}\end{align*}$
Where $z_{\pm}=\frac{-2c\ \pm\ \sqrt{4c^2-4(a+ib)(a-ib)}}{2(a-ib)}=\frac{-c\ \pm\ \sqrt{c^2-(a^2+b^2)}}{(a-ib)}=\frac{-c\ \pm\ \sqrt{c^2-1}}{(a-ib)}$.
Therefore, if we define $f(z)=\frac{1}{z-z_-}$, we get that $f$ is analytic in $\{z:|z|\leq 1\}$ since
$$|z_-|=\Bigg|\frac{-c-\sqrt{c^2-1}}{a-ib}\Bigg|=\bigg|c+\sqrt{c^2-1}\bigg|>|c|>1$$
Finally from Cauchy's Integral Formula:
$$I=\frac{2}{i}\cdot 2\pi i\cdot f(z_+)=4\pi \frac{1}{z_+-z_-}=\frac{2\pi(a-ib)}{\sqrt{c^2-1}}$$
Which is not always real... So my question is what is the problem.
Moreover, sometimes it is correct, e.g. $a=1,b=0,c=2$ gives the correct answer $\frac{2\pi}{\sqrt{3}}$.

REPLY [5 votes]: Note, we have
\begin{align}
\frac{a}{\sqrt{a^2+b^2}}\cos(t)+\frac{b}{\sqrt{a^2+b^2}}\sin(t) = \cos(t-\delta)
\end{align}
where
\begin{align}
\delta=\cos^{-1}\frac{a}{\sqrt{a^2+b^2}}.
\end{align}
Hence it follows
\begin{align}
\int^{2\pi}_0 \frac{dt}{c+a\cos(t)+b\sin(t)} = \int^{2\pi}_0 \frac{dt}{c+\cos(t-\delta)} =\int^{2\pi-\delta}_{-\delta}\frac{dt}{c+\cos(t)}.
\end{align}
However, since $(c+\cos(t))^{-1}$ is $2\pi$ period, then the integral is equivalent to
\begin{align}
\int^{2\pi}_0 \frac{dt}{c+\cos(t)} =\frac{2\pi}{\sqrt{c^2-1}}
\end{align}
where the evaluation is done with contour integral.


text:
\begin{document}

\maketitle

\begin{abstract}
	For a graph $G$, let $\lambda_2(G)$ denote its second smallest Laplacian eigenvalue.
	It was conjectured that $\lambda_2(G) + \lambda_2(\Gb) \ge 1$, where $ \Gb $ is the complement of $G$.
	In this paper, it is shown that $\max\left\{\lambda_2(G), \lambda_2(\Gb)\right\} \ge \frac{2}{5}$.
\end{abstract}

\noindent {\em AMS Classification}: 05C50\\
\noindent{\em Keywords}: Laplacian eigenvalues of graphs, Laplacian spread

\section{Introduction}

All graphs considered in this paper are simple (no loops and no multiple edges).
If $G$ is a graph and $v\in V(G)$, we denote by $ N_{G}(v) $ the set of vertices adjacent to $ v $.

We denote the complementary graph of $ G $ by $ \Gb $.

The adjacency matrix $A(G)$ of $G$ is the matrix whose $(u,v)$-entry is equal to $1$ if $uv\in E(G)$ and $0$ otherwise.
If $D(G)$ denotes the diagonal matrix of vertex degrees, then the Laplacian of the graph $G$ is defined as $L(G) = D(G) - A(G)$. We denote the Laplacian eigenvalues of $G$ by
$$0=\lambda_1(G) \le \lambda_2(G) \le \cdots \le \lambda_n(G).$$
The second smallest eigenvalue $\lambda_2(G)$ is also called the \textit{algebraic connectivity} of $ G $ and is an important indicator related to various properties of the graph.

It is well-known that the eigenvalues of the complementary graph $L(\Gb)$ are
$$0 = \lambda_1(\Gb) \le n - \lambda_n(G) \le n - \lambda_{n - 1}(G) \le \ldots \le n - \lambda_{2}(G).$$

The \textit{Laplacian spread} of a graph $ G $ is defined to be $\lambda_n(G) - \lambda_2(G)$.
Clearly, $\lambda_n(G) - \lambda_2(G) \le n$. It was conjectured \cite{yl,zsh} that this quantity is at most $n-1$.

\begin{conj}
	For any graph $ G $ of order $ n\ge2 $, the following holds:
	$$\lambda_n(G) - \lambda_2(G) \le n-1,$$
	or equivalently $\lambda_2(G) + \lambda_2(\Gb) \ge 1$, with equality if and only if $ G $ or $ \Gb $ is isomorphic to the join of an isolated vertex and a disconnected graph of order $ n-1 $.
\end{conj}

This conjecture holds for trees \cite{fxwl}, unicyclic graphs \cite{btf}, bicyclic graphs \cite{flt,lsl,lw}, tricyclic graphs \cite{cw}, cactus graphs \cite{l}, quasi-tree graphs \cite{xm}, graphs with diameter not equal to $3$ \cite{zsh}, bipartite and $K_3$-free graphs \cite{cd}.

In this paper, we provide a positive constant lower bound for $\lambda_2(G) + \lambda_2(\Gb)$ by proving the following.

\begin{thm}\label{thm:main}
	Let $G$ be a graph of order $n\ge2$. Then
	$$ \max\left\{\lambda_2(G), \lambda_2(\Gb)\right\} \ge \frac{2}{5}.$$
\end{thm}

\section{Routings}

If $P$ is a path in a graph $G$, we denote its length by $\Vert P\Vert$.
Let $\mathcal{P}$ be a set of paths in $G$. For any edge $e\in G$, let $w_{\mathcal{P}}(e)$ be the sum of the lengths of all paths in $\mathcal{P}$ which contain $e$.
We say $\mathcal{P}$ has \emph{weighted congestion} $w$, where $w = \max_{e\in E(G)} {w_{\mathcal{P}}(e)}$.
We denote the weighted congestion of $\mathcal{P}$ by $w(\mathcal{P})$.

A set $\mathcal{P}$ of paths in $G$ is called a \textit{routing} if for any distinct vertices $x,y \in V(G)$, there is \textit{exactly one} path $P_{xy}\in \mathcal{P}$ with endpoints $x$ and $y$. In particular, this means that $P_{xy}=P_{yx}$.

\begin{thm}\label{SystemOfPaths&Lambda}
	Let $G$ be a graph of order $n$. If $G$ has a routing $\mathcal{P}$ of weighted congestion at most $w$, then $\lambda_2(G) \ge \frac{n}{w}$.
\end{thm}

\begin{proof}
	Let $f: V(G) \rightarrow \mathbb{R}$ be an eigenvector of $L(G)$ corresponding to the eigenvalue $\lambda_2(G)$. Then $f$ is orthogonal to the all-one vector $\mathbf{1}$, since $\mathbf{1}$ is an eigenvector corresponding to $\lambda_1(G)$. This means that $\sum_{x\in V(G)}f(x)=0$.

	Note that we have
	\begin{equation}\label{eq:1}
		\Vert f \Vert^2
		= \frac{1}{n} \sum_{ \{x,y\} \subseteq V(G) } (f(x) - f(y))^2 ,
	\end{equation}
	because
	\begin{eqnarray*}
		2 \sum_{ \{x,y\} \subseteq V(G) } (f(x) - f(y))^2
		&=& \sum_{x,y \in V(G)} (f(x) - f(y))^2 \\
		&=& \sum_{x,y \in V(G)} (f(x)^2 + f(y)^2 - 2 f(x) f(y)) \\
		&=& 2n \sum_{x \in V(G)} f(x)^2 - 2 \biggl( \sum_{x \in V(G)} f(x) \biggr)^2 \\[1mm]
		&=& 2n \Vert f \Vert^2 .
	\end{eqnarray*}

	For any distinct vertices $x,y \in V(G)$, let $P_{xy}\in \mathcal{P}$ be the path in $\mathcal{P}$ with end points $x$ and $y$. We may assume that $\Vert f \Vert = 1$. Then,
	\begin{align*}
		\lambda_2(G)
		 & = \sum_{xy \in E(G)} (f(x) - f(y))^2                                                                                \\
		 & = \frac{n \sum_{xy \in E(G)}{(f(x) - f(y))^2}}{ \sum_{\{x,y\} \subseteq V(G) } (f(x) - f(y))^2}                                                            & \text{ (by (\ref{eq:1}))}               \\
		 & \ge \frac{n \sum_{xy \in E(G)}{(f(x) - f(y))^2}}{ \sum_{\{x,y\} \subseteq V(G) }{\left( \Vert P_{xy}\Vert \sum_{uv \in P_{xy}} (f(u) - f(v))^2 \right) } } & \text{ (by Cauchy–-Schwarz inequality)} \\
		 & = \frac{n \sum_{xy \in E(G)}{(f(x) - f(y))^2}}{\sum_{uv \in E(G)} w_{\mathcal{P}}(uv) (f(u) - f(v))^2}                                                                                \\
		 & \ge \frac{n}{w}.
	\end{align*}
	The proof is complete.
\end{proof}

\section{Main Result}

Now, we prove the main result of this paper.

\begin{thm}\label{mainThm}
	Let $G$ be a graph of order $n \ge 2$. At least one of $G$ or $\Gb$ has a routing of weighted congestion at most $5n/2$.
\end{thm}

\begin{proof}
	The proof is by induction on $n$. If $G$ has diameter at most 2, we select for each pair $\{x,y\}$ a path of length 1 or 2 joining $x$ and $y$.
	For any edge $e=xy\in E(G)$, the paths through $e$ are the edge $xy$, some paths from $x$ to $V(G)\setminus (N_G(x)\cup\{x\})$ and some paths from $y$ to $N_G(x)\setminus\{y\}$. Thus the weighted congestion of $e$ is at most $1 + 2(n-1-|N_G(x)|) + 2(|N_G(x)|-1) = 2n-3$.
	Thus, this routing has weighted congestion at most $2n-3$. Hence, we may assume from now on that neither $G$ nor $\Gb$ has diameter less than 3. This implies that both, $G$ and $\Gb$ have diameter exactly 3 and that $n\ge 4$.

	Let $u,v$ be vertices whose distance in $\Gb$ is 3, and let $u',v'$ have distance 3 in $G$. Then
	$uv \in E(G)$, $u'v' \in E(\Gb)$ and $N_G(u) \cup N_G(v) = N_\Gb(u') \cup N_\Gb(v') = V(G)$.
	This implies in particular that in $G$, every vertex is at distance at most 2 from $u$.
	Thus $u\notin \{u',v'\}$. By symmetry, we conclude that $\{u,v\}\cap\{u',v'\} = \emptyset$.
	Let
	\begin{align*}
		X \coloneqq N_G(u) \setminus (N_G(v) \cup \{v\}), \quad
		Y \coloneqq N_G(v) \setminus (N_G(u) \cup \{u\}), \quad
		Z \coloneqq N_G(u) \cap N_G(v), \\
		X' \coloneqq N_\Gb(u') \setminus (N_\Gb(v') \cup \{v'\}), \quad
		Y' \coloneqq N_\Gb(v') \setminus (N_\Gb(u') \cup \{u'\}), \quad
		Z' \coloneqq N_\Gb(u') \cap N_\Gb(v').
	\end{align*}
	Without loss of generality assume that $|X| \le |Y|$ and $|X'| \le |Y'|$.

	Since $u'$ and $v'$ are at distance 3 in $G$, we have
	\begin{equation}\label{eq1}
		|\{u',v'\} \cap X| = |\{u',v'\} \cap Y| = 1.
	\end{equation}
	We may thus assume that $u'\in X$ and $v'\in Y$. Similarly, we may assume that $u\in X'$ and $v\in Y'$.

	Let $H = G -\{v,v'\}$. By induction, at least one of $H$ or $\Hb$ has a routing of weighted congestion at most $5(n-2)/2$.

	Let us first assume that $H$ has such a routing $\mathcal{P}_H$.
	Let $\mathcal{A}$ be the set of following paths taken for every $z\in V(H)$:
	$$ P_{vz} = \begin{cases}
			v z   & \text{if $z \in Y \cup Z \cup \{u\}$}, \\
			v u z & \text{if $z \in X$}.
		\end{cases} $$

	We have
	$$ w_{\mathcal{A}}(e) = \begin{cases}
			1        & \text{if $e = vz$ and $z \in Y \cup Z$}, \\
			2|X| + 1 & \text{if $e = v u$},                     \\
			2        & \text{if $e = u z$ and $z \in X$},       \\
			0        & \text{otherwise}.
		\end{cases} $$

	Let $\mathcal{B}$ be the following set of paths taken for each $z\in V(H)\cup \{v\}$:
	$$ P_{v'z} = \begin{cases}
			v' z     & \text{if $z=v$},                       \\
			v' v z   & \text{if $z \in Y \cup Z \cup \{u\}$}, \\
			v' v u z & \text{if $z \in X$}.
		\end{cases} $$
	We have
	$$ w_{\mathcal{B}}(e) = \begin{cases}
			2n-3+|X| & \text{if $e = v' v$},                                       \\
			2        & \text{if $e = v z$ and $z \in (Y \cup Z)\setminus\{v'\} $}, \\
			3|X| + 2 & \text{if $e = v u$},                                        \\
			3        & \text{if $e = u z$ and $z \in X$},                          \\
			0        & \text{otherwise}.
		\end{cases} $$
	The set of paths $ \mathcal{P} = \mathcal{P}_H \cup \mathcal{A} \cup \mathcal{B} $ is a routing in $G$ with weighted congestion at most $5n/2$ since $|X| \le \frac{n-2}{2}$ and $w(\mathcal{P}_H) \le 5(n-2)/2$. Note that all we needed for this conclusion was that we had a routing in $H$ and that $v'\in Y$ (since we used the fact that $|X|\le |Y|$ to conclude that $|X|\le (n-2)/2$).

	Suppose now that the requested routing exists in $\Hb$. Since $v\in Y'$, the same proof as above shows that we can obtain a routing in $\Gb$ with weighted congestion at most $5n/2$. This completes the proof.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:main}]
	By Theorems~\ref{SystemOfPaths&Lambda} and \ref{mainThm}, every graph $G$ of order $n\ge2$ satisfies:
	\begin{equation*}
		\max\left\{\lambda_2(G), \lambda_2(\Gb)\right\}
		\ge \frac{n}{5n/2} = \frac{2}{5}
	\end{equation*}
	which is what we were to prove.
\end{proof}

At the end, we pose the following question:

\medskip

\noindent
\textbf{Question.} {\it What is the supremum of all real numbers $c$ such that for any graph $G$ of order at least 2,}
$$ \max\left\{\lambda_2(G), \lambda_2(\Gb)\right\} \ge c.$$

\medskip

The path $P_4$ (which is self-complementary) has $\lambda_2(P_4) = 2-\sqrt{2} < 0.5858$. This shows that the supremum will be smaller than $0.5858$.

\bibliographystyle{amsplain}

config: arxiv


TITLE: Find all real numbers $t$ such that the quadratic form $f$ is positive definite.
QUESTION [5 upvotes]: Where $$f(x_1,x_2,x_3)=2x_1^2+x_2^2+3x_3^2+2tx_1x_2+2x_1x_3$$.
This is a problem in my Matrix Analysis homework. Below is my effort.

Let $x=(x_1,x_2,x_3)^T$, then we have $$f=x^*Sx$$, in which $$S=\left(\begin{matrix}2&t&1\\t&1&0\\1&0&3\end{matrix}\right)$$. $f$ is positive definite is equivalent to $S$ is positive definite which is equivalent to all the eigenvalues of $S$ is positive.
The characteristic polynomial of $S$ is: $$\begin{align}|\lambda I-S|&=-\lambda^3+6\lambda^2+(3t^2-10)\lambda+(-3t^2+5)\\&=(-3+3\lambda)t^2+(-\lambda^3+6\lambda^2-10\lambda+5)\end{align}$$.
Now the only problem left is that how do I find all the possible real values of $t$ that makes this polynomial of $\lambda$ only has positive roots?

REPLY [4 votes]: An equivalent condition for a matrix to be positive definite is that the leading principal minors of the matrix are all positive. This condition is easier to check: You just need to check that $2>0$, $2-t^2>0$ and that $-3t^2+5>0$. For more info see characterizations of positive definite matrices

REPLY [0 votes]: Hint: If all roots of $p(X)=-X^3+a X^2+bX+c$ are positive then necessarily $p(0)>0$ because $p(x)\to+\infty$ as $x\to-\infty$.
To rule out the possibility that two roots are complex, you may check that $p'=-3X^2+2aX+b$ has two real roots (i.e. $4a^2+12b>0$) and that $p(x)>0$ where $x$ is the greater of the roots of $p'(x)$.

REPLY [0 votes]: We can solve it writing $x^tSx$ as a sum of squares. We have
\begin{align}
x^tSx&=(x_2+tx_1)^2-t^2x_1^2+2x_1^2+3x_3^2+2x_1x_3\\
&=(x_2+tx_1)^2+3\left(x_3^2+\frac 23x_1x_3\right)+(2-t^2)x_1^2\\
&=(x_2+tx_1)^2+3\left(x_3+\frac{x_1}3\right)^2-3\frac{x_1^2}9+(2-t^2)x_1^2\\
&=(x_2+tx_1)^2+3\left(x_3+\frac{x_1}3\right)^2+\left(\frac 53-t^2\right)x_1^2.
\end{align}


TITLE: Second order differential equation, orthogonality
QUESTION [0 upvotes]: A temperature field T(x, t) is determined by the following governing equation:
$$\frac 1\alpha\frac {dT}{dt} = \frac {d^2T}{dx^2}$$ (Eq 1)
T(x,t) can be expressed as a form of expansion of T(x,t) = (Eq 2)
$$\sum_{n=0}^\infty cos(\lambda_nx)\bar T(\lambda_n,t)$$
where $\lambda_n=n*pi(n=0,1,2...)$ are known.  using the orthogonality property of $cos(\lambda_nx)$ in domain $x \epsilon [a,b]$, one obtains
$$\bar T(\lambda_n,t)=\frac {\int_a^bT(x,t)cos(\lambda_nx)dx} {\int_a^bcos^2(\lambda x)dx}$$
One needs to solve for $\bar T(\lambda_n,t)$ to finally determine the temperature field T(x,t).
Write the expression for
$$\frac {d \bar T(\lambda_n,t)}{dt}$$
from Eq 2, and then replace $\frac {dT}{dt}$ inside this equation with $\alpha \frac {d^2x}{dt^2}$.
You then rearrange using integration by parts twice and you should end up with an ordinary ODE for $\bar T(\lambda_n,t)$.
I just typed the whole problem because I am really not sure where to start.  It looks like I need to differentiate equation 2 but I don't know how because of the integrals in there.  If anyone could even just tell me which topics I should look for in which textbooks, or a general guideline to how to go about solving, I'd really appreciate it.

REPLY [1 votes]: I am not really sure what you require here, but here goes.
$$
\bar{T}\left(\lambda_n,t\right) = \dfrac{\int_a^b T(x,t)\cos\left(\lambda_n x\right)dx}{\int_a^b\cos^2\left(\lambda_n x\right)dx}
$$
$$
\dfrac{\partial}{\partial t}\bar{T}\left(\lambda_n,t\right) = \dfrac{\partial}{\partial t}\dfrac{\int_a^b T(x,t)\cos\left(\lambda_n x\right)dx}{\int_a^b\cos^2\left(\lambda_n x\right)dx}
$$
since $x$ and $t$ are independent we can swap around the integral and differentiation to yield
$$
\dfrac{\partial}{\partial t}\dfrac{\int_a^b T(x,t)\cos\left(\lambda_n x\right)dx}{\int_a^b\cos^2\left(\lambda_n x\right)dx} = \dfrac{\int_a^b \left(\dfrac{\partial }{\partial  t}T(x,t)\right)\cos\left(\lambda_n x\right)dx}{\int_a^b\cos^2\left(\lambda_n x\right)dx}
$$
now you can replace
$$
\dfrac{\partial T}{\partial t} = \alpha\dfrac{\partial^2 T}{\partial x^2}
$$
and then integrate by parts of something..
I do not understand where $\alpha\dfrac{d^2 x}{dt^2}$ comes from? Also think about using partial derivative notation :).
$$
$$


TITLE: The set of natural number functions is uncountable
QUESTION [11 upvotes]: I thought the set of natural number functions would be of the same cardinality as the countably infinite product of $\mathbb{N}$, which is countable.
Each natural number function can be identified with an infinite-tuple of $\mathbb{N}$ by letting the $i$th entry be the image of the number $i$ under the function.

REPLY [0 votes]: Let's consider the following set: $F = \{ f:D \in 2^\mathbb{N} \rightarrow \mathbb{N} \ | \ f(x) = x \}$;
Notice how there is a function $f$ for each possible set of natural numbers residing inside $2^\mathbb{N}$, which will allow us to draw the following conclusion: $|F| = |2^\mathbb{N}|$.
Now, observe how $F$ is a much smaller set than $\mathbb{N}^\mathbb{N}$(because it contains only functions of the form $f(x)=x$), but even so, it's uncountable. Therefore $\mathbb{N}^\mathbb{N}$ is evidently uncountable since it's a superset of $F$.
$F \subseteq \mathbb{N}^\mathbb{N}, |F| = |2^\mathbb{N}| \implies |\mathbb{N}^\mathbb{N}|=|2^\mathbb{N}|  \ \ \ \square $


TITLE: Conceptual problem with general relativity
QUESTION [3 upvotes]: According to Einstein, mass curves spacetime and objects in the nearby field tends to travel in the shortest possible path to reach their heavier counterparts. My question is was not Newton's interpretation better; i.e. considering gravity as a force that acts on $n$ masses and tends to attract? I know that photons don't hold up with this definition, but how can spacetime be visualized (saw those trampoline models) in real life? How to define motions of celestial objects by considering an invisible 'fabric'? Any help will be appreciated.

REPLY [0 votes]: Better theories
You ask if Newton's theory isn't "better". But you have to define "better" first.
There are mostly a few different requirements for good theories:

Accuracy

Conceptual simplicity

Computational efficiency

A theory could be "better" only in a specific way.
General Relativity is the most accurate theory of gravity in an absolute sense, at all scales it is expected to yield more accurate results, and it starts to differ significantly from Newtonian mechanics near massive bodies.
Newtonian gravity may be considered simpler (Euclidean geometry), although one may find the axioms of relativity more parsimonious (simpler axioms) than the Newtonian, which demands assuming the inverse square law (offering no explanation for "why" the law is as such) and gravitational and inertial mass equivalence.
Computationally, certainly Newtonian gravity is simpler (it may be interpreted as an approximation of GR), so it is the best theory for fast calculation of low mass interactions.

Metaphysically, we may equate truth with maximum possible accuracy (by definition), so finding the more accurate theories is the path to discovering the a nature of the universe, or the closest we can get. Truth may be thought to have intrinsic value (apart from the practical utilities discussed before).


TITLE: Is this sequence the Markov chain?
QUESTION [0 upvotes]: Let $\xi_n, n\geq 1$ be a sequence of discrete random variables, $\xi_n \in A=\{1,2,...,K\}, \forall n$. This sequence satisfies the following condition:
$$P(\xi_n=i_1|\xi_m=i_2,\xi_k=i_3)=P(\xi_n=i_1|\xi_m=i_2), \forall n>m>k, i_1,i_2,i_3 \in A.$$
The question: Will this sequence be a Markov chain?
Any suggestion or example are appreciated. Thank you.

REPLY [2 votes]: Assuming $\xi_n$ is adapted to the filtration $F_n$, the Markov Property is given by
\begin{align}
\mathbb{P} \left( \xi_n = i_1 \mid F_{m} \right) = \mathbb{P} \left( \xi_n = i_1 \mid \xi_{m} \right), \quad \forall n>m, i_1 \in A
\end{align}
which intuitively means that the only information that is relevant for future jumps is the
most recent information. In your example, the Markov Property is
\begin{align}
\mathbb{P} \left( \xi_n = i_1 \mid \xi_m = i_2, \xi_{m-1}=i_3, \dots, \xi_1=i_{m+2} \right) = &\mathbb{P} \left( \xi_n = i_1 \mid \xi_{m} =i_2 \right),
\\ \forall n>m, i_1 \dots i_{m+2} \in A.
\end{align}
However, this is not the property that you were given. So the sequence $(\xi_n)_{n \geq 1}$ is not Markov with the information you were given.
 Imagine that information about 3 consecutive values of $\xi$, $\xi_{n},\xi_{n-1},\xi_{n-2}$, would change the jump probabilities for $\xi_{n+1}$ compared to just having the knowledge of $\xi_n$:
\begin{align}
\mathbb{P} \left( \xi_{n+1} = i_1 \mid \xi_n = i_2, \xi_{n-1}=i_3,\xi_{n-2}=i_{4} \right) \neq &\mathbb{P} \left( \xi_{n+1} = i_1 \mid \xi_{n} =i_2 \right),
\\ \forall n, i_1, i_2, i_3, i_{4} \in A.
\end{align}
This example is a sequence that would not have the Markov Property, but could still have the property you were given.
EDIT:
Here is a more concrete example: Let $ \left(X_n \right)_{n \geq 0}$ be a sequence of discrete random variables, $X_n \in A = \{ 1,2,\dots,K  \} \forall n$, where
\begin{align}
\mathbb{P} \left(X_{n+1} =a+1 \mid X_n = a \right) &= \frac{2}{3},\quad \forall n, a \in \{ 1,2,\dots,K-1  \}
\\
\mathbb{P} \left(X_{n+1} =a \mid X_n = a \right) &= \frac{1}{3},\quad \forall n, a \in \{ 1,2,\dots,K  \}
\\
\mathbb{P} \left(X_{n+1} =1 \mid X_n = K \right) &= \frac{2}{3},\quad \forall n
\\
\mathbb{P} \left( X_{n} = a_1 \mid X_{m} =a_2 , X_k = a_3 \right) &= \mathbb{P} \left( X_{n} = a_1 \mid X_{m} =a_2 \right) \forall n, a_1, a_2, a_3 \in A
\end{align}
So far, this looks like a Markov Chain, and if no further information about sequence is given, it would be fair to assume it is a Markov Chain (ie. assuming all unspecified probabilities are $0$). Notably, it has the desried property that is given in your problem. However, if it was futhermore given that
\begin{align}
\mathbb{P} \left( X_{n+1} = 1 \mid X_{n} =a , X_{n-1} = a, X_{n-2} =a \right) &=1 \quad \forall n, a\in A,
\end{align}
the sequence cannot have the Markov Property (and thus cannot be a Markov Chain) despite having the property given in the problem. This is due to
\begin{align}
\mathbb{P} \left( X_{n+1} = 1 \mid X_{n} =a , X_{n-1} = a, X_{n-2} =a \right) \neq \mathbb{P} \left( X_{n+1} = 1 \mid X_{n} =a \right) \quad \forall n, a\in A,
\end{align}
since we would need an equality in the equation above.


TITLE: Statistics: Why do we divide by $\sqrt{n}$ for sample standard deviation
QUESTION [7 upvotes]: Can someone tell me if my explanations/understanding is on the right track?
Suppose we have a set of variances, each of them identical, where $V_{1}(x) + V_{2}(x) + ...+ V_{j}(x) = \sigma^2$. If we wanted to take $\frac{1}{n}$-th ($n \leq j$) of the variances we would have $\frac{\sigma^2}{n}$, taking the square root this becomes $\frac{\sigma}{\sqrt{n}}$
My other idea is to let $V_{1}(x) = V_{2}(x) = ...=V_{j}(x) = \sigma^2$ so summing these all together we would get $j\sigma^2$ so the standard deviation is $\sqrt{j} \sigma$ and taking the average we would get $\frac{\sigma}{\sqrt{j}}$

REPLY [3 votes]: Your second idea is correct if you assume your $V$'s are independent.  Independence is the important property, because variance is then additive, as you show, and then the rest of your reasoning is correct.  If your $V$'s are not independent, then you won't have additivity of variance because there could be covariance between the observations.