text:
\begin{document}

  \title{Preimage Cardinalities of Continuous Functions}
\author {Seljon Akhmedli}

\maketitle

\address{Sheyenne High School, 11th Grade, West Fargo, ND, USA}

\vspace{1cm}

   \begin{center} June 12th, 2020   \end{center}

   \bigskip

\begin{center} {\Large ABSTRACT:} We find all subsets of $\mathbb{N} $  which occur as the set of possible cardinalities of preimages of a continuous function. We also study and answer this question for various subclasses of continuous functions. \end{center}

   \section{Introduction}

  It is a well-known fact that there exists no continuous function $f:[0,1]\to \mathbb{R} $ such that every point $x\in \mathbb{R}$ has either two or zero preimages. A somewhat less well-known fact is that there exist continuous functions $f:[0,1]\to \mathbb{R} $ where the preimage $f^{-1}(x)$ has an even cardinality for all $x\in \mathbb{R}$, in fact, one can construct such a function where the set of cardinalities of preimages is $\{0,2,4\}$.

  \medskip

 \hspace{4cm}  \includegraphics[width=0.5\textwidth]{waveexamplepic}

  In this paper, we are interested in the question of what other sets may occur as the set of preimage cardinalities for a continuous function. Given a continuous function $f:[a,b]\to \mathbb{R}, a < b$ we let $$\Omega _f = \{n\in \mathbb{N}\cup \{\infty \} \ : \ \exists x\in \mathbb{R} \ s.t. \ |f^{-1}(x)| = n\}.$$ Our question is what subsets of $\mathbb{N}$ may occur as $\Omega _f$ where $f:[a,b]\to \mathbb{R}$ is a continuous function. Notice that by boundedness of a continuous function in the compact interval, it is necessary that $0\in \Omega _f$. We also study the case when $f$ belongs to a sub-class of the class of continuous functions.

   \medskip

  One can also ask what subsets $S$ of $\mathbb{N}\cup \{\infty \} $ occur as $\Omega _f $ but in this question if we let $\infty \in S$ (otherwise, we fall back to the previous question) then it becomes easy: for any non-empty subset $A\subseteq \mathbb{N}$ where $0\in A$, the set $S = A\cup \{\infty \}$ does occur as $\Omega _f$ for some continuous $f:[a,b]\to \mathbb{R}$.

  \medskip

  By re-scaling the domain, we may just consider functions over the interval $[0,1]$ in this question (instead of an arbitrary interval). For an arbitrary interval $[a,b]$, $C[a,b]$ will denote the space of all continuous functions $f:[a,b]\to \mathbb{R}$. In this space, we define a subset  $$\mathcal{F}([a,b]) := \{f\in C[a,b] \ : \ f^{-1}(x) \ \mathrm{is \ finite \ for \ all} \ x\in \mathbb{R}\}.$$ In the case of the interval $[0,1]$, we will just write $\mathcal{F}$ instead of $\mathcal{F}([0,1])$. For functions $f\in \mathcal{F}$, we can also write $$\Omega _f = \{n\in \mathbb{N} \ : \ \exists x\in \mathbb{R} \ s.t. \ |f^{-1}(x)| = n\}.$$ If $\Omega _f = S$, then we also say that $f$ is an $S$-function. Notice that a function $f\in \mathcal{F}$ has finitely many local maximums and local minimums, moreover, the end points 0 and 1 are either a local maximum or a local minimum.

  \medskip

  Given a subset $S\subseteq \mathbb{N}$ with $|S|\geq 2$, we let $$m_1(S)  = \min (S\backslash \{0\}) \  \mathrm{and} \ m_2(S) = \max S.$$ Here, we use a convention that the maximum of an unbounded subset of natural numbers equals $\infty $. Our main theorem is the following

  \medskip

  {\bf Theorem 1.} Let $S\subseteq \mathbb{N}$ such that $0\in S$ and $|S|\geq 2$. Then there exists  $f\in C[0,1]$ with $\Omega _f = S$ if and only if $m_2 \geq 2m_1 - 1$.

  \medskip

  With slight care, one can indeed make all these functions from the class $C^{\infty }$. An important tool in this construction is the use of functions which "wiggles" infinitely many times. Hence this construction would not work for real analytic functions (by our definition, a function $f:[0,1]\to \mathbb{R}$ is real analytic if it can be extended holomorphically to some domain of $\mathbb{C}$ which includes the unit real segment $[0,1]$; in the sequel, instead of "real analytic" we will simply use the term "analytic"). Motivated by this fact, we also study the same question for all analytic functions, in particular, for polynomials. In fact, by far, not every subset of type $\Omega _f$ for a continuous function occurs as $\Omega _p$ where $p$ is a polynomial. First of all, for a polynomial $p(x)$, we necessarily have $\Omega _p$ is finite (same is true for analytic functions $f:[0,1]\to \mathbb{R}$). But even among finite subsets, for example, the set $\{0, 2, 4\}$ already does not occur as $\Omega _p$. By the following theorem, we achieve a complete characterization of the sets $\Omega _p$ as well where $p(x)$ is an analytic function. To state this theorem, we need to introduce some notations. Let $$A_{+} = \{(n, n+k, n+2k)\in \mathbb{N}^3 \ : \ n\geq 0, k > 0\},$$ \ $$A_{-} = \{(n, n-k, n-2k)\in \mathbb{N}^3 \ : \ n\geq 0, 0 < k\leq \frac{n}{2}\},$$ \
  $$B_{+} = \{(n, n+k, n+2k-1)\in \mathbb{N}^3 \ : \ n\geq 0, k \geq 0\},$$ \ $$ B_{-} = \{(n, n-k, n-2k-1)\in \mathbb{N}^3 \ : \ n\geq 0, 0 \leq k\leq \frac{n-1}{2}\},$$ \
  $$C_{+} = \{(n, n+k, n+2k-2)\in \mathbb{N}^3 \ : \ n\geq 0, k \geq 0\},$$ \ $$C_{-} = \{(n, n-k, n-2k-2)\in \mathbb{N}^3 \ : \ n\geq 0, 0 \leq k \leq \frac{n}{2}-1\},$$ \ $$A = A_{+}\cup A_{-}, B = B_{+}\cup B_{-}, C = C_{+}\cup C_{-}. $$

  \bigskip

  {\bf Theorem 2.} Let $S\subseteq \mathbb{N}$ such that $0\in S$. Then there exists an analytic function $f:[0,1]\to \mathbb{R}$ with $\Omega _f = S$ if and only if there exists a finite sequence $(x_0, x_1, x_2, \dots , x_{2m-1}, x_{2m})$ of natural numbers for some $m\geq 1$ such that the following conditions hold:

   i) $x_i\in S$ for all $i\in \{0, \dots, 2m\}$, and for all $z\in S$ there exists $i\in \{0, \dots, 2m\}$ such that $z = x_i$,

   ii) $x_0 = 0$ and $x_{2m} = 0$,

   iii) for all $0\leq i\leq m-1, (x_{2i}, x_{2i+1}, x_{2i+2})\in A\cup B\cup C$,

   iv) either $|\{i \ : \ 0\leq i\leq m-1, (x_{2i}, x_{2i+1}, x_{2i+2})\in B\}| = 2$ or $|\{i \ : \ 0\leq i\leq m-1, (x_{2i}, x_{2i+1}, x_{2i+2})\in C\}| = 1$,

   v) if any triple belongs to $B$, then no triple belongs to $C$.

   \medskip

   {\bf Remark 1.} If $S$ satisfies conditions i)-v), then the analytic function $p$ with $\Omega _p = S$ is constructed by interpolation method, thus in the statement of the theorem, "analytic" can be replaced with "polynomial".

  \section{Proof of Theorem 1}

  In this section we will assume that $S$ is a subset of $\mathbb{N}$ such that $0\in S$ and $|S|\geq 2$. The symbols $I, I_1, I_2, J, J_1, J_2$ will always denote a set $\{1,\dots , n\}$ for some $n\geq 1$ or one of the sets $\mathbb{Z}_{+}, \mathbb{Z}$. Such sets will be called {\em index sets}. We will first consider the special case of Theorem 1 when $1\in S$. In this special case Theorem 1 states the following

  \medskip

  {\bf Proposition 1.} Let $S\subseteq \mathbb{N}$ such that $0, 1\in S$. Then there exists  $f\in C[0,1]$ with $\Omega _f = S$.

  \medskip

   To prove Proposition 1, we introduce some terminology.

   {\bf Definition 1.} Let $n\geq 1$. A function $f\in C([a,b])$ is called an {\em $n$-wave function} if there exists real numbers $m < M$ and a sequence $a = x_0 < x_1 < \dots x_{n-1} < x_n = b$ such that $f$ is strictly increasing in the interval $[x_i, x_{i+1}]$ for all even $i\in \{0, \dots , n-1\}$ and strictly decreasing in the interval $[x_i, x_{i+1}]$ for all odd $i\in \{0, \dots , n-1\}$, moreover, $f(x_i) = m$ for all even $i\in \{1, \dots , n\}$ and $f(x_i) = M$ for all odd $i\in \{0, \dots , n\}$. The restriction $f|_{[x_{i-1}, x_i]}$ is called the $i$-th leaf of $f$; the interval $[x_{i-1}, x_i]$ is called the support of this leaf of $f$.

   \medskip

   Along with $n$-wave functions we will also use the notion of an $n$-stair function.

   \medskip

    {\bf Definition 2.} Let $n\geq 2$ be a positive odd integer. A function $f\in C([a,b])$ is called an {\em $n$-stair function} if there exists a sequence $a = z_0 < z_1 < \dots z_{n-1} < z_n = b$ such that for all $i\in \{0, \dots , n-1\}$ the restriction $f|_{[z_i, z_{i+1}]}$ is a $k_i$-wave function for some positive odd integer $k_i\geq 1$, and for all $0\leq i < j\leq n-1$, $x\in [z_i, z_{i+1}], y\in [z_j, z_{j+1}]$, $f(x) \leq f(y)$. The sequence $(k_1, \dots , k_n)$ will be called {\em the signature of $f$}. The interval $[z_i, z_{i+1}]$ is called the $(i+1)$-st block of $f$.

   \medskip

    \hspace{4cm}  \includegraphics[width=0.5\textwidth]{5-stairfunction.png}

    In the above picture we have 5-stair function with signature $(5,1,3,7,1)$; so this function has 5 blocks, and the restriction to these blocks are 5-wave, 1-wave, 3-wave, 7-wave and 1-wave functions.

 \medskip

    We also need to define infinite stair functions. This is done similarly as follows

    {\bf Definition 3.} A function $f\in C([a,b])$ is called an {\em $\infty $-stair function} if there exists a two-sided sequence $a < \dots < z_{-1} < z_0 < z_1 < \dots  < b$ with $\displaystyle \mathop{\lim }_{n\to \infty }z_{-n} = a$ and $\displaystyle \mathop{\lim }_{n\to \infty }z_n = b$ such that for all $i\in \mathbb{Z}$ the restriction $f|_{[z_i, z_{i+1}]}$ is a $k_i$-wave function for some positive odd integer $k_i\geq 1$, and for all $i < j$, $x\in [z_i, z_{i+1}], y\in [z_j, z_{j+1}]$, $f(x) \leq f(y)$. The sequence $(k_i)_{i\in \mathbb{Z}}$ will be called {\em the signature of $f$}. If $k_i = k$ for all $i\in \mathbb{Z}$ (i.e. if the sequence $(k_i)_{i\in \mathbb{Z}}$ is constant), then we also say that $f$ has a signature $k$. If, for some positive odd $p, q$ and $n_0\in \mathbb{Z}$, $k_i = p$ for all  $i\leq n_0$ and $k_i = q$ for all  $i > n_0$ then we also say that $f$ has a signature $(p,q)$. The intervals $[z_i, z_{i+1}]$ are called {\em the blocks} of $f$.

    \medskip

     \hspace{4cm}  \includegraphics[width=0.5\textwidth]{signature}

     In the above figure an $\infty $-stair function of signature $(3,5)$ is represented.

     \medskip

   {\bf Definition 4.} Let $a\leq c < d\leq b$, $f\in C([a,b]), g\in C([c,d])$ such that $f(c) = g(c)$ and $f(d) = g(d)$. The function $h:[a,b]\to \mathbb{R}$ defined as $$h(x) = \left\{
	\begin{array}{ll}
		f(x)  & \mbox{if } x \in [a,c]\cup [d,b] \\
		g(x) & \mbox{if } x \in [c,d]
	\end{array}
\right.$$ is called {\em the amendment of $f$ by $g$}. More generally, if $g_i:K_i\to \mathbb{R}, i\in I$ is a collection of continuous functions such that the intervals $K_i = [c_i,d_i]$ have mutually disjoint interiors and $g_i(c_i) = f(c_i), g_i(d_i) = f(d_i)$ for all $i\in I$, then {\em the amendment of $f$ by the collection $(g_i)_{i\in I}$} is defined as $$h(x) = \left\{
	\begin{array}{ll}
		f(x)  & \mbox{if } x \in [a,b]\backslash \displaystyle \mathop{\cup }_{i\in I}K_i \\
		g_i(x) & \mbox{if } x \in K_i, i\in I
	\end{array}
\right.$$
   If $[c,d] = [a,b]$ then the amendment is also called {\em a replacement.}

   \medskip

   Notice that the amendment of continuous functions is still continuous. We will be interested in amending $n$-stair functions with $r$-stair functions for various values of $n, r$ (including infinite values) at different sub-intervals.

   \bigskip

   {\bf Proof of Proposition 1.} In the case $S = \{0,1\}$ the claim is obvious so we may assume that $\{0,1\}$ is a proper subset of $S$. Let $r = \min (S\backslash \{0,1\})$, $(S\backslash \{0,1\})\cap 2\mathbb{N} = \{r_i : i\in I_1\}$ and $(S\backslash \{0,1\})\cap (2\mathbb{N}+1) = \{s_i : i\in I_2\}$. We also define the functions $f:[0,1]\to [0,1], h:[0,1]\to [0,1]$ as $f(x) = x, \forall x\in [0,1]$ and $h(x) = \left\{
	\begin{array}{ll}
		2x  & \mbox{if } x \in [0,\frac{1}{2}] \\
		-x+\frac{3}{2} & \mbox{if } x \in [\frac{1}{2},1]
	\end{array}
\right.$  We consider the following cases.

   \medskip

   {\em Case 1.}  $(S\backslash \{0,1\})\cap 2\mathbb{N} = \emptyset $ (i.e. $I_1 = \emptyset $).

   Let $C_i, i\in I_2$ be mutually disjoint open intervals in $(0,1)$ such that $\displaystyle \mathop{\cup }_{i\in I_2}\overline{C_i}=[0,1]$. For all $i\in I_2$, we let $g_i:C_i\to C_i$ be a surjective $\infty $-stair function with signature $s_i$. Then we take the identity function $f:[0,1]\to [0,1]$ and for each $i\in I_2$ we amend $f$ with $g_i$ in the interval $C_i$. The amendment $\overline{f}:[0,1]\to \mathbb{R}$ satisfies the conditions $\mathrm{Range}(\overline{f}) = [0,1]$,  $\overline{f}(0) = 0, \overline{f}(1) = 1$ and $\Omega _{\overline{f}} = S$.

   \medskip

   {\em Case 2.} $2\in S$.

 Let $B_i, i\in I_2$ and $C_i, i\in I_1$ be mutually disjoint open intervals in $(0,1)$ such that $\displaystyle \mathop{\cup }_{i\in I_2}\overline{B_i}=[0,\frac{1}{4}]$ and $\displaystyle \mathop{\cup } _{i\in I_1}\overline{C_i}=[\frac{1}{4}, \frac{1}{2}]$.

  For all $i\in I_2$ we let $g_i:B_i\to 2B_i$ be a surjective $\infty $-stair function with signature $s_i$ and for all $i\in I_1$ we let $g_i:C_i\to 2C_i$ be a surjective $\infty $-stair function with signature $r_i-1$. Then in the intervals $B_i, i\in I_2$ and $C_i, i\in I_1$ we amend $h$ with $g_i$. The amendment $\overline{h}:[0,1]\to \mathbb{R}$ satisfies the conditions  $\mathrm{Range}(\overline{h}) = [0,1]$, $\overline{h}(0) = 0, \overline{h}(\frac{1}{2}) = 1, \overline{h}(1) = \frac{1}{2}, \overline{h}^{-1}(0) = \{0\}, \overline{h}^{-1}(1) = \{\frac{1}{2}\}, \overline{h}^{-1}(\frac{1}{2}) = \{\frac{1}{4}, 1\}$ and $\Omega _{\overline{h}} = S$.

   \medskip

   {\em Case 3.} $r$ is odd, $I_1\neq \emptyset , I_2\neq \emptyset $.

   Let $\phi :[0,\frac{1}{2}]\to [0,1]$ be an $\infty $-stair function with signature $(r,r-2)$ such that every block supporting an $r$-wave function lies in $[0,\frac{1}{4}]$ and every block supporting an $(r-2)$-wave function lies in $[\frac{1}{4}, \frac{1}{2}]$, moreover, $|\phi ^{-1}(\frac{1}{2})| = r-1$. Let $B_i, i\in J_2$ and $C_i, i\in J_1$ be mutually disjoint open blocks of $\phi $ such that $\displaystyle \mathop {\cup }_{i\in J_2}\overline{B_i}=[0,\frac{1}{4}]$ and $\displaystyle \mathop{\cup } _{i\in J_1}\overline{C_i}=[\frac{1}{4}, \frac{1}{2}]$.

   \medskip

   Let $u_i, i\in J_2$ be a leaf of $\phi $ in the block $B_i$, and $v_i, i\in J_1$ be a leaf of $\phi $ in the block $C_i$. Let also $a:J_1\to I_1$ and $b:J_2\to I_2$ be surjective maps (such maps exist because the sets $J_1$ and $J_2$ are both infinite). We replace $u_i, i\in J_2, v_i, i\in J_1$ respectively with $\infty $-stair functions $\overline{u_i}$ of signature $s_{b(i)}-r+1$ and $\overline{v_i}$ of signature $r_{a(i)}-r$. Then we amend $f$ with functions $\overline{u_i}, i\in J_2$ and $\overline{v_i}, i\in J_1$.

   \medskip

   {\em Case 4.} $r$ is even, $r\geq 4$, $I_1\neq \emptyset , I_2\neq \emptyset $.

   This case is very similar to the previous case with the only difference that $\phi :[0,1]\to [0, \frac{1}{2}]$ is assumed to be an $\infty $-stair function with signature $(r+1,r-3)$ such that every block supporting an $(r+1)$-wave function lies in $[0,\frac{1}{4}]$ and every block supporting an $(r-3)$-wave function lies in $[\frac{1}{4}, \frac{1}{2}]$, $|\phi ^{-1}(\frac{1}{2})| = r-1$, and the signatures of $\overline{u_i}, \overline{v_i}$ are $s_{b(i)}-r$ and $r_{a(i)}-r+3$ respectively.

   \medskip

   {\em Case 5.} $(S\backslash \{0,1\})\cap (2\mathbb{N}+1) = \emptyset $ (i.e. $I_2 = \emptyset $).

   \medskip

   Since $S\backslash \{0,1\}$ does not contain an odd element we have that $r$ is even. Let $H:[-\frac{1}{2},1]\to [0,1]$ defined as $h(x) = \left\{
	\begin{array}{ll}
		-x  & \mbox{if } x \in [-\frac{1}{2},0] \\
		h(x) & \mbox{if } x \in [0,1]
	\end{array}
\right.$

  and $\psi :[0,\frac{1}{2}]\to [0,1]$ be an $\infty $-stair function with signature $(r-1,r-3)$ such that $|\psi ^{-1}(\frac{1}{2})| = r-2.$ Let also $D_i, i\in J$ be mutually disjoint open blocks of $\psi $ such that $\displaystyle \mathop{\cup }_{i\in J}\overline{D_i}=[\frac{1}{4},\frac{1}{2}]$. Let $w_i, i\in J$ be a leaf of $\psi $ in the block $D_i$, and $c:J\to I_1$ be a surjective function. We replace $w_i, i\in J$ with $\infty $-stair function $\overline{w_i}$ of signature $r_{c(i)}-r+3$. Then we amend $H$ with functions $\overline{w_i}, i\in J$. The amendment $\overline{H}:[-\frac{1}{2},1]\to \mathbb{R}$ satisfies the conditions $\mathrm{Range}(\overline{H}) = [0,1]$, $\overline{H}(-\frac{1}{2}) = \overline{H}(1) = \frac{1}{2}, \overline{H}(0) = 0, \overline{H}(\frac{1}{2}) = 1$ and $\Omega _{\overline{H}} = S$. By re-scaling the domain of $\overline{H}$ we can obtain a function $F:[0,1]\to \mathbb{R}$ with $\Omega _F = S$.  \ $\square $

  \bigskip

  For the proof of Theorem 1, we need to introduce the following

  {\bf Definition 5.} Let $S\subseteq \mathbb{N}$ and $0\in S$. $S$ is called of type I if for all even $x\in S$ there exists an odd $y\in S$ such that $y > x$. If $S$ is not of type I then we say that $S$ is of type II.

  \medskip

   The above definition implies that if $S$ is finite, then $S$ is of type II if and only if $\max S$ is even.

   \bigskip

   Now we are ready for the proof of the main theorem.

   \medskip

   {\bf Proof of Theorem 1.} First we will prove the "only if part".

   \medskip

     If $(0,1)$ does not contain any local maximum point of $f$ then either $f$ is a strictly monotone function or $f$ has only one local minimum in $(0,1)$ and local maximums at 0 and 1. In the latter case $\Omega _f = \{0,1,2\}$ whereas in the former case $\Omega _f = \{0,1\}$; the inequality  $m_2\geq 2m_1-1$ holds in both cases.

    \medskip

     Thus we may assume that $(0,1)$ does contain a local maximum point. Similarly, we may assume that $(0,1)$ contains a local minimum point. Then, without loss of generality we may also assume that at least one of the ends 0, 1 is not a local maximum. Let $y_1$ be the biggest value of $f$ in $[0,1]$  such that $f^{-1}(y_1)$ contains a local maximum in $(0,1)$. If we have $l$ local maximums in $f^{-1}(y_1)\cap (0,1)$, then $|f^{-1}(y_1)| \leq l+1$, and for a sufficiently small $\epsilon > 0$, $|f^{-1}(y_1-\epsilon )| \geq 2l$; moreover, if $|f^{-1}(y_1)| = l+1$, then $|f^{-1}(y_1-\epsilon )| \geq 2l+1$. Thus $|f^{-1}(y_1-\epsilon )| \geq 2|f^{-1}(y_1)|-1$. Hence we obtain that $m_2\geq 2m_1-1$.

    The "if part" is proved in Proposition 1 when $1\in S$. So we will assume that $1\notin S$.  Let $S\cap 2\mathbb{Z} = \{r_i \ : \ i\in I_1\}$ and $S\cap (2\mathbb{Z}+1) = \{s_i \ : \ i\in I_2\}$. We also let $p = \min (S\backslash \{0\})$. Then $p\geq 2$.

     We will consider the following cases.

    {\em Case 1.} $S$ is of type I.

    We can find an odd $q\in S$ such that $q\geq 2p-1$. Let $C_i, i\in \mathbb{Z}$ be mutually disjoint open intervals such that $\displaystyle \mathop{\cup }_{i\in \mathbb{Z}}\overline{C_i} = [\frac{1}{4}, \frac{3}{4}]$ and $C_i$ is on the left of $C_j$ for all $i<j$ (i.e. for all $x\in C_i, y\in C_j, x < y$).

    We let $f:[\frac{1}{4}, \frac{3}{4}]\to [\frac{1}{4}, \frac{3}{4}]$ be a surjective $\infty $-stair function of signature $(\dots , 1, 2p-1, 1, 2p-1, 1, 2p-1, \dots )$ such that every block supported on $C_i$ for even $i\in \mathbb{Z}$ is a 1-wave function, and every block supported on $C_i$ for odd $i\in \mathbb{Z}$ is a $(2p-1)$-wave function. We also let $f_1:[0, \frac{1}{4}]\to [0, \frac{1}{4}]$ and $f_2:[\frac{3}{4},1]\to [\frac{3}{4},1]$ be surjective $(2p-1)$-wave functions.

    Let $u_j$ be leaf of $f_j, j\in \{1,2\}.$ Let also $v_i$ be a leaf of $f$ supported on the block $C_{2i+1}, i\in \mathbb{Z}$ and $w_i = f|_{C_{2i}}, i\in \mathbb{Z}$. So $w_i$ is a 1-wave function for all $i\in \mathbb{Z}$.
    For all $i\in \mathbb{Z}$, we replace $v_i$ with an $\infty $-stair function $\overline{v_i}$ of signature $(q-2p+2)$; for all $j\in \{1,2\}$ we also replace $u_j$ with an $\infty $-stair function $\overline{u_j}$ of signature $(q-2p+2)$. Furthermore, for all $i\in 2\mathbb{Z}$ we replace $w_i$ with an $\infty $-stair function $\overline{w_i}$ of signature $(r_{a(i)}-1,r_{a(i)}+1)$, and for all $i\in (2\mathbb{Z}+1)$ we replace $w_i$ with an $\infty $-stair function $\overline{w_i}$ of signature $(s_{b(i)})$ where $a:2\mathbb{Z}\to I_1, b:2\mathbb{Z}+1\to I_2$ are surjective maps.
    The blocks of $\overline{w_i}, i\in 2\mathbb{Z}$ are either $(r_{a(i)}-1)$-wave functions or $(r_{a(i)}+1)$-wave functions. For each $i\in 2\mathbb{Z}$, in the former case we replace a leaf of it with $\infty $-stair function of signature $(q-r_{a(i)}+2)$ whereas in the latter case e replace a leaf of it with $\infty $-stair function of signature $(q-r_{a(i)})$. Let $\overline{\overline{w_i}}$ be this amendment of $\overline{w_i}$.

    \hspace{4cm}  \includegraphics[width=0.5\textwidth]{Case1}

    Now we amend $F:[0,1]\to [0,1]$ with functions $\overline{u_j}, j\in \{1,2\}$ and $\overline{v_i}, i\in \mathbb{Z},  \overline{w_i}, i\in 2\mathbb{Z}+1$ and  $\overline {\overline{w_i}}, i\in 2\mathbb{Z}$ where $F$ is defined as $F(x) = \left\{
	\begin{array}{lll}
		f_1(x)  & \mbox{if } x \in [0, \frac{1}{4}] \\
		f(x) & \mbox{if } x \in [\frac{1}{4},\frac{3}{4}] \\
		f_2(x)  & \mbox{if } x \in [\frac{3}{4},1]
	\end{array}
\right.$  (The above picture represents $F$ when $p=3$).

  For the amendment $\overline{F}:[0,1]\to \mathbb{R}$ we have $\Omega _{\overline{F}} = S$.

  \medskip

   {\em Case 2:} $S$ is of type II.

   Let the intervals $C_i, i\in \mathbb{Z}$ be as in Case 1 and $a:2\mathbb{Z}\to I_1, b:2\mathbb{Z}+1\to I_2$ are surjective maps. We can find an even $q\in S$ such that $q-1\geq 2p-1$.

   We let $h:[\frac{1}{4}, \frac{3}{4}]\to [\frac{1}{4}, \frac{3}{4}]$ be a surjective $\infty $-stair function of signature $(\dots , 1, 2p-1, 1, 2p-1, 1, 2p-1, \dots )$ such that every block supported on $C_i$ for even $i\in \mathbb{Z}$ is a 1-wave function, and every block supported on $C_i$ for odd $i\in \mathbb{Z}$ is a $(2p-1)$-wave function. We also let $h_1:[0, \frac{1}{4}]\to [0, \frac{1}{4}]$ be a surjective $(2p-1)$-wave function and $h_2:[\frac{3}{4},\frac{7}{8}]\to [\frac{3}{4},\frac{7}{8}]$ be a surjective $(2p-2)$-wave function with $h_2(\frac{7}{8}) = \frac{3}{4}$.

   Let $u_j$ be the first leaf of $h_j, j\in \{1,2\}$, and $v_i$ be a leaf of $h$ supported on the block $C_{2i+1}, i\in \mathbb{Z}$ and $w_i = h|_{C_{2i}}, i\in \mathbb{Z}$.

   Let the last two leafs of $h_2$ be supported on the interval $D = (d_1, d_2)$. We take a function $\xi : D\to [\frac{3}{4},\frac{7}{8}]$ such that $\xi ^{-1}(\frac{3}{4}) = \{d_1,d_2\}, \xi ^{-1}(\frac{7}{8}) = \{d_3, d_4\}$ for some $d_3, d_4\in D$, (so $|\xi ^{-1}(\frac{3}{4})| = |\xi ^{-1}(\frac{7}{8})| = 2$) and $|\xi ^{-1}(y)| = 4$ for all $y\in (\frac{3}{4},\frac{7}{8})$. Then we amend $h_2$ with $\xi $; let $h_3$ be this amendment.

    For all $i\in \mathbb{Z}$, we replace $v_i$ with an $\infty $-stair function $\overline{v_i}$ of signature $(q-2p+1)$. We also amend $u_1$ with an $\infty $-stair function $\overline{u_1}$ of signature $(q-2p+1)$, and $u_2$ with an $\infty $-stair function $\overline{u_2}$ of signature $(q-2p+1)$. Finally, for all $i\in 2\mathbb{Z}$ we replace $w_i$ with an $\infty $-stair function $\overline{w_i}$ of signature $(s_{a(i)}-2,s_{a(i)})$, and for all $i\in (2\mathbb{Z}+1)$ we replace $w_i$ with an $\infty $-stair function $\overline{w_i}$ of signature $(r_{b(i)}-1)$.

    The blocks of $\overline{w_i}, i\in 2\mathbb{Z}$ are either $(s_{a(i)}-2)$-wave functions or $(s_{a(i)})$-wave functions. For each $i\in 2\mathbb{Z}$, in the former case we replace a leaf of it with $\infty $-stair function of signature $(q-s_{a(i)}+2)$ whereas in the latter case e replace a leaf of it with $\infty $-stair function of signature $(q-s_{a(i)})$. Let $\overline{\overline{w_i}}$ be this amendment of $\overline{w_i}$.

    Now let $H:[0,1]\to [0,1]$ be defined as $H(x) = \left\{
	\begin{array}{llll}
		h_1(x)  & \mbox{if } x \in [0, \frac{1}{4}] \\
		h(x) & \mbox{if } x \in [\frac{1}{4},\frac{3}{4}] \\
		h_3(x)  & \mbox{if } x \in [\frac{3}{4},\frac{7}{8}] \\
		-6x+6 & \mbox{if } x \in [\frac{7}{8},1]
	\end{array}
\right.$

  We amend $H$  with functions $\overline{u_j}, j\in \{1,2\}$ and $\overline{v_i}, \overline{w_i}, i\in 2\mathbb{Z}+1$ and  $\overline {\overline{w_i}}, i\in 2\mathbb{Z}$. For the amendment $\overline{H}:[0,1]\to \mathbb{R}$ we have $\Omega _{\overline{H}} = S$.

  \ $\square $

    \bigskip

    {\bf Remark 2.} In the proof of Proposition 1 and Theorem 1, we use  $\infty $-stair functions $\sigma :[a,b]\to [c,d]$. We can allow "the heights of the waves" to be small enough and fast converging to zero so we can build such a function $\sigma _1:[a,b]\to [c,c+\delta ]$ of class $C^{\infty }$, where $\delta $ is some (possibly small) positive number and $\sigma ^{(n)}(a) = \sigma ^{(n)}(b) = 0$ for all $n\geq 1$. Then we re-scale the range by defining $\sigma _2(x) = \frac{c}{\delta }(\delta + c - d)+\frac{d-c}{\delta }\sigma _1(x)$ thus make $\sigma _2$ of class $C^{\infty }$. This allows to make the function $f$ in the claim of Proposition 1 and Theorem 1 from the $C^{\infty }$ class.

    \bigskip

    \section{Proof of Theorem 2}

    Let us first recall a well-known fact that if an analytic function has infinitely many zeros on a compact interval then it is identically zero. Thus an analytic function $p:[0,1]\to \mathbb{R}$ has finitely many zeros and  finitely many critical points. It also belongs to $\mathcal{F}$. Then there exists a finite sequence $y_1 < y_2 < \dots < y_{m-1}$ such that any local maximum or local minimum point of $p$ belongs to $\displaystyle \mathop{\sqcup }_{1\leq i\leq m-1}p^{-1}(y_i)$, and each of the subsets $p^{-1}(y_i)$ contains at least one local maximum or local minimum. Let $y_0 = -\infty $ and $y_m = \infty $, and let $\phi :\mathbb{R} \to \mathbb{N}$ be defined as $\phi (y) = |p^{-1}(y)|$. Then in any interval $(y_i, y_{i+1}), 0\leq i\leq m-1$, $\phi $ is constant. Let $z_i$ be a point in $(y_i, y_{i+1}), 0\leq i\leq m-1$.

    \medskip

    We let $x_{2i} = |p^{-1}(z_i)|, 0\leq i\leq m$,  and $x_{2i+1} = |p^{-1}(y_i)|, 1\leq i\leq m$. Then for all $0\leq i\leq m-1$,

    if $p^{-1}(y_i)$ does not contain end points, contains $l$ local minimums and $r$ local maximums, and $r < l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in A_{+}$;

    if $p^{-1}(y_i)$ does not contain end points, contains $l$ local minimums and $r$ local maximums, and $r > l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in A_{-}$;

    if $p^{-1}(y_i)$ contains one end point as a local minimum, $l$ local minimums and $r$ local maximums, and $r \leq l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in B_{+}$;

    if $p^{-1}(y_i)$ contains one end point as a local minimum, $l$ local minimums and $r$ local maximums, and $r > l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in B_{-}$;

    if $p^{-1}(y_i)$ contains one end point as a local maximum, $l$ local minimums and $r$ local maximums, and $r \leq l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in B_{+}$;

    if $p^{-1}(y_i)$ contains one end point as a local maximum, $l$ local minimums and $r$ local maximums, and $r > l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in B_{-}$;

      if $p^{-1}(y_i)$ contains two end points of opposite types, $l$ local minimums and $r$ local maximums, and $r \leq l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in C_{+}$;

      if $p^{-1}(y_i)$ contains two end points of opposite types, $l$ local minimums and $r$ local maximums, and $r > l$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in C_{-}$;

      if $p^{-1}(y_i)$ contains two end points both of which are local maximums, $l$ local minimums and $r$ local maximums, and $r > l+2$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in C_{-}$;

      if $p^{-1}(y_i)$ contains two end points both of which are local maximums, $l$ local minimums and $r$ local maximums, and $r \leq l+2$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in C_{+}$;

      if $p^{-1}(y_i)$ contains two end points both of which are local minimums, $l$ local minimums and $r$ local maximums, and $l \geq r+2$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in C_{+}$;

      if $p^{-1}(y_i)$ contains two end points both of which are local minimums, $l$ local minimums and $r$ local maximums, and $l > r+2$, then  $(x_{2i}, x_{2i+1}, x_{2i+2})\in C_{-}$;

      in all other cases $x_{2i} = x_{2i+1} = x_{2i+2}$.

      \medskip

      Thus we proved the "only if part" of the theorem. To prove the "if part", we first observe the following simple fact.

      \medskip

      {\bf Lemma 1.} Let $f\in \mathcal{F}([a,b])$ and $y_1 < y_2 < y_3$ such that for all $y \in [y_1, y_3]\backslash \{y_2\}$, the set $f^{-1}(y)$ does not contain any local maximum or local minimum, and $|f^{-1}(y_1)| = n, |f^{-1}(y_2)| = n+k, |f^{-1}(y_3)| = n+2k$ for some $n\geq 0, k\in \mathbb{Z}\backslash \{0\}$. Let also $r, s\in \mathbb{Z}\backslash \{0\}$ such that $r+s = k$. Then $f$ can be amended in the set $f^{-1}([y_1, y_3])$ such that the amendment $F$ belongs to $\mathcal{F}([a,b])$, moreover, there exists $z_1, z_2 \in (y_1, y_3)$ such that $z_1 < y_2 < z_2$, for all $y \in [y_1, y_3]\backslash \{z_1, z_2, y_2\}$, the set $F^{-1}(y)$ does not contain any local maximum or local minimum, and $|F^{-1}(y_1)| = n, |F^{-1}(z_1)| = n+r, |F^{-1}(y_2)| = n+2r, |F^{-1}(z_2)| = n+2r+s, |F^{-1}(y_3)| = n+2k$.  $\square $

      \medskip

      Now, given any sequence $(x_0, x_1, x_2, \dots , x_{2m-1}, x_{2m})$ satisfying conditions i)-v) we have two cases: 1) None of the triples $(x_{2i}, x_{2i+1}, x_{2i+2}), 0\leq i\leq m-1$ belongs to $C$ or 2) Exactly one of the triples $(x_{2i}, x_{2i+1}, x_{2i+2}), 0\leq i\leq m-1$ belongs to $C$.

      In the former case we have $0\leq p < q\leq m-1$ such that $$(x_{2p}, x_{2p+1}, x_{2p+2}), (x_{2q}, x_{2q+1}, x_{2q+2})\in B$$ and in the latter case we have $0\leq k\leq m-1$ such that $(x_{2k}, x_{2k+1}, x_{2k+2})\in C$.

      We can take a sequence $(0, 1, \dots , m-1)$ and inductively build a piecewise linear function $f:[0,1]\to \mathbb{R}$ (i.e. $f$ is continuous, has finitely many singularity points, and in between these singularities it is defined as a polynomial of degree at most 1, such that

      (i) if $c$ is a local maximum or local minimum, then $f(c)\in \{0, 1, \dots , m-1\}$

      (ii) $f(a) = p, f(b) = q$ in Case 1), and $f(a) = f(b) = k$ in Case 2).

      (iii) For all $i\in \{0, 1, \dots , 2m\}$, $|f^{-1}(i)| = x_i$.

       \medskip

       Here, we carry the induction on the quantity $m$. For $m\leq 4$ we can see by a direct check that the claim holds. If $m\geq 5$ then there exists $i\in \{0, \dots , m-2\}$ such that none of the triples $(x_{2i}, x_{2i+1}, x_{2i+2}), (x_{2i+2}, x_{2i+3}, x_{2i+4})$ belongs to $B\cup C$. Then using Lemma 1 we reduce the question to the case of a sequence of length $2m-2$.

       \medskip

       Now, conditions (i)-(ii) imply that $\Omega _f = S$. But, by interpolation formula [1], for any piecewise linear function one can find a polynomial $p:[0,1]\to \mathbb{R}$ with same range and the same set of local maximums and local minimums. Then $\Omega _p = \Omega _f.$ \ $\square $

    \medskip

    {\bf Acknowledgement:} I thank Azer Akhmedov for his encouragements and for so many helpful comments and suggestions on the original draft.

    \vspace{1cm}

    REFERENCES:

    \bigskip

    [1] \ Whittaker, E. T. and Robinson, G. "Lagrange's Formula of Interpolation." §17 in The Calculus of Observations: A Treatise on Numerical Mathematics, 4th ed. New York: Dover, pp. 28-30, 1967.

    \vspace{1cm}

    E-mail: 147414@west-fargo.k12.nd.us

  \end{document}

config: arxiv


TITLE: Abelianization of characteristic quotients of $F_2$
QUESTION [5 upvotes]: Let $F_2$ be the free group on two generators.
Let $U\le F_2$ be a characteristic subgroup of finite index, and let $f : F_2\rightarrow\mathbb{Z}^2$ be the abelianization map.
It's easy to check that $f(U)$ is characteristic in $\mathbb{Z}^2$, so it must be of the form $N\mathbb{Z}\times N\mathbb{Z}$ for some $N\ge 1$, and hence the induced quotient $\mathbb{Z}^2/f(U)$ must be of the form $(\mathbb{Z}/N\mathbb{Z})^2$.
I apologize if this is a basic question, but my general question is - Is there a way of determining the $N$ from the characteristic subgroup $U$?
Of course this is too vague - I suppose an underlying question was - what are the characteristic subgroups of $F_2$? (There seems to be very little literature on this)
A more precise question might be:
Let $G$ be a finite group, and let $H\lhd F_2$ with $F_2/H \cong G$, and let $\{H_i\}$ be the $Aut(F_2)$-orbit $H$, then $U_H := \bigcap_i H_i$ is characteristic in $F_2$. Then we know that $f(U) = N\mathbb{Z}\times N\mathbb{Z}$. Is there a way of determining $N$ from $H$?
If we let $U_G$ be the intersection of all $G$-defining subgroups of $F_2$, then is there a way of determinine the $N$ associated to $f(U_G)$ from $G$?

REPLY [2 votes]: Note that $N$ is clearly the exponent of $F_2/[F_2,F_2]U$.
For any normal subgroup $U$ of $F_2$, the exponent of $F_2/[F_2,F_2]U$ is the same as the exponent of $K/[K,K]$, where $K=F_2/U$. Thus, $N$ is the exponent of $K/[K,K]$.
Now, $K$ is a subgroup of the Cartesian product $G\times G\times\dots$ such that the projection of $K$ to each factor is surjective. This implies that $K/[K,K]$ is a subgroup of
$G/[G,G]\times G/[G,G]\times\dots$ and the projection of $K/[K,K]$ to each factor is surjective.
Thus, the exponent of $K/[K,K]$ (that is $N$) is equal to the exponent of $G/[G,G]$.
So, Derek is right.


text:
\section{Discussion and Conclusions}
\label{sec:conclusions}

We have presented an approach for learning control policies that provably generalize well to novel environments given a dataset of example environments. Our approach leverages PAC-Bayes theory to obtain upper bounds on the expected cost of (stochastic) policies on novel environments and can be applied to robotic systems with continuous state and action spaces, complicated dynamics, rich sensory inputs, and neural network-based policies. We synthesize policies by explicitly minimizing this upper bound using convex optimization in the case of a finite policy space, and using stochastic gradient descent in the more general case of continuously parameterized policies. We also present an extension of our approach for learning distributionally-robust policies, i.e., settings where test environments are drawn from a different distribution than training environments. We demonstrated our framework by learning (i) depth sensor-based obstacle avoidance policies with guarantees on collision-free navigation in novel environments, and (ii) neural network-based grasping policies with guarantees on generalization to new objects. Our simulation results compared the generalization guarantees provided by our technique with exhaustive numerical evaluations in order to demonstrate that our approach is able to provide strong bounds even with relatively few training environments. Our hardware experiments -- which tested policies learned using our framework on a real-world obstacle avoidance example -- suggest that our technique is effective for developing policies that generalize well to (unseen) real-world environments.

\subsection{Challenges and Future Work}
\label{sec:future work}

There are a number of challenges and exciting opportunities for future work on both the theoretical and practical fronts. We highlight a few such directions here.

{\bf Deterministic policies.} It may be desirable in many cases (e.g., safety-critical settings) to learn deterministic policies instead of stochastic ones. Techniques for converting stochastic hypotheses into deterministic hypotheses have been developed within the PAC-Bayes framework (e.g., using majority voting in the classification setting \citep{Langford03, Lacasse07}); an interesting avenue for future work is to extend such techniques to the policy learning setting we consider here. Another possibility is to use different frameworks for obtaining generalization bounds that are better suited to deterministic policies (e.g., bounds based on algorithmic stability \citep{Bousquet02, Kearns99, Hardt15} and sample compression \citep{Floyd95, Langford05}). An important feature of the reduction-based perspective we presented in Section \ref{sec:pac bayes control} is that it immediately allows us to port over such bounds from the supervised learning setting to our setting.

{\bf Choosing the prior.} While we have demonstrated that our framework allows us to obtain strong bounds on generalization performance, an important direction for future work is to find ways to further improve these bounds. We believe that a particularly promising approach for doing this is to systematically choose the prior $P_0$ over the control policy space. The priors in the examples considered in this paper were chosen in a fairly simplistic manner (e.g., a uniform prior over the finite policy space for the obstacle avoidance example in Section \ref{sec:reactive obstacle avoidance control}, or a prior that attempts to keep the grasp position close to the center of mass in the grasping example in Section \ref{sec:grasping}). One possibility for choosing a prior more carefully is to embed domain knowledge into the prior. For example, one could choose a prior that incorporates a physics model of the system, or one that is derived from an existing state-of-the-art approach for the problem under consideration (e.g., choosing a prior that encourages force-closure grasps). Another promising possibility is to learn the prior from a human expert using imitation learning.

{\bf Extensions to meta-learning.} Another exciting future direction is to combine the techniques presented here with \emph{meta-learning} techniques in order to achieve provably data-efficient control on novel tasks. Specifically, we are currently investigating using a PAC-Bayes bound as part of the objective of a meta-learning algorithm such as MAML \citep{Finn17a} to achieve improved generalization performance and few-shot learning.

\vspace{7pt}

We believe that the approach presented here along with the indicated future directions represent an important step towards learning control policies with provable guarantees for challenging robotic platforms with rich sensory inputs operating in novel environments.


TITLE: second order SDE vs general diffusion stationary distribution
QUESTION [0 upvotes]: A quick follow-on to this question.
Consider the following SDE:
$$
\ddot{x} = f(x) - \gamma g(x)\, \dot{x} + \sigma h(x)\, \xi(t)
\tag{1}
$$
Based on [1], we can represent (1) as a system of two first-order equations:
$$
\begin{cases}
\mathrm{d} X_t = V_t\, \mathrm{d}t \\
\mathrm{d} V_t = -\gamma g(X_t)\, \mathrm{d}t + f(X_t)\, \mathrm{d}t + \sigma h(X_t)\, \mathrm{d}W_t.
\end{cases}
\tag{2}
$$
Why does the noise contribute to the $V_t$ variables, not the $X_t$ variables? Is it something particular about (1)? Can we rewrite (2) equivalently with noise on the $X_t$ variables?

[1] Burrage, Kevin; Lenane, Ian; Lythe, Grant, Numerical methods for second-order stochastic differential equations, SIAM J. Sci. Comput. 29, No. 1, 245-264 (2007). ZBL1144.65004.

REPLY [1 votes]: It really depends on the physics hidden behind, namely on where you think the stochastics finds its role. Let me explain with two examples. In both examples, $X_t$ denotes the position vector, $V_t$ the "velocity", and $W_t$ the Wiener process.
The first example is the Brownian motion. If we consider the standard Brownian motion, its equation of motion is obviously
$$
{\rm d}X_t={\rm d}W_t.
$$
Here we believe, in physics, that the stochastics contributes to the position directly. More precisely, we owe the physically-observed stochastic behavior of tiny particles to some mathematically-defined stochastic processes. In this example, there is no properly defined velocity. In other words, if you want to put
$$
{\rm d}X_t=V_t\,{\rm d}t+{\rm d}W_t,
$$
it is a must that $V_t=0$, meaning that the velocity is zero. This is of course counterintuitive; after all, all Brownian particles are moving, right? So this really depends on how you define velocity for a stochastic process, or an Ito process for special. Mathematically, there are two ways. The first is to identify the drift term as the velocity, i.e., if
$$
{\rm d}X_t=V_t\,{\rm d}t+\sigma_t\,{\rm d}W_t,
$$
$V_t$ is then the velocity. However, this does not apply to the Brownian motion. The second is to identify the quadratic variation as the velocity, i.e.,
following the above SDE,
$$
{\rm d}\left<X\right>_t=\sigma_t^2\,{\rm d}t,
$$
and $\sigma_t$ is then regarded as the velocity. This applies to the Brownian motion, and $\left<X\right>_t$ measures the average kinetic energy.
The second example is your Langevin equation. In this scenario, recall that a Langevin equation models a very large particle whos dynamics is governed by Newton's second law, but with stochastic background forces contributed from tiny Brownian particles. With this understanding, the equation of motion for this very large particle should be
\begin{align}
{\rm d}X_t&=V_t\,{\rm d}t,\\
{\rm d}V_t&=I_{t+{\rm d}t}-I_t={\rm d}I_t,
\end{align}
which is in the form of Newton's second law. Here $I_t$ denotes the impulse of external forces. The only difference is that $I_t$ is no longer deterministic, but yields some stochastic behaviors. Therefore, we put
$$
{\rm d}I_t=F_t\,{\rm d}t+\sigma_t\,{\rm d}W_t,
$$
where $F_t$ stands for the conventional forces, and $\sigma_t$ indicates the strength of stochastic forces. These stochastic forces arise from the Brownian motion of those tiny particles. Combine the last three equations, and you recover the Langevin equation. In this case, the stochastic factors are all put on the forcing term.
Of course, you may consider
\begin{align}
{\rm d}X_t&=V_t\,{\rm d}t+\mu_t\,{\rm d}W_t^1,\\
{\rm d}V_t&=F_t\,{\rm d}t+\sigma_t\,{\rm d}W_t^2,
\end{align}
where $W_t^1$ and $W_t^2$ are two Wiener processes. This model is no longer Langevin, but for some intermediate particle instead. In other words, the dynamics of this particle is partly governed by Newton's second law with stochastic background forces, but itself also observes some Brownian motion. It really depends on how you interpret the physics hidden behind.
That's it. Hope this could be somewhat helpful for you.


TITLE: Proving a sequence is bounded
QUESTION [1 upvotes]: I want to prove that (4n-1)/4n is bounded.

My work:
$$\begin{align}
&\frac{4n-1}{4n}\\
= &\frac{\frac{4n}n - \frac 1n}{\frac {4n}n}\\
=&\frac{4 - 1/n}4\\
=&1 - \frac 1{4n}\\
=&1\;\;\;\;\;\;\;\;\; [\text{ by taking the limit}]
\end{align}$$
.

REPLY [1 votes]: Split the fraction:
$$\frac{4n-1}{4n} = \frac{4n}{4n} - \frac{1}{4n}= 1-\frac{1}{4n} \le 1$$
since $\tfrac{1}{4n}$ is a positive term ($n \in \mathbb{N}$). The terms of the sequence are thus bounded above by 1.


text:
\section{Bootstrapping the Quantiles}\label{sec:bootsrapping the quantiles}
The quantiles of the limit distribution of $\dodstat$ under $H_0$ depend on the unknown distribution $U$ and are therefore in general not accessible. One possible approach, which is quite cumbersome, is to estimate the covariance matrix of the Gaussian limit process $G$ from the data and use this to approximate the quantiles required. Alternatively, we suggest to directly bootstrap the quantiles of the limit distribution of $\dodstat$ under $H_0$. To this end, we define and investigate the bootstrap versions of $U_n$, $U_n^{-1}$ and $\mathbb{U}_n^{-1}\coloneqq \sqrt{n}\left( U_n^{-1}-U^{-1}\right)$.

\noindent Let $\mu_n$ denote the empirical measure based on the sample $X_1,\dots,X_n$. Given the sample values, let ${X}_1^*,\dots,{X}_{n_B}^*$ be an independent identically distributed sample of size $n_B$ from $\mu_n$. Then, the bootstrap estimator of $U_n$ is defined as
\begin{align*}
&{U}_{n_B}^*(t):= \frac{2}{n_B(n_B-1)}\sum_{1\leq i<j\leq n_B}\mathds{1}_{\left\lbrace d_\mathcal{X}({X}_i^*,{X}_j^*)\leq t\right\rbrace},
\end{align*}
the corresponding bootstrap empirical $U$-process is for $t\in\R$ given as ${\mathbb{U}}_{n_B}^*(t)=\sqrt{n_B}\big({U}_{n_B}^*(t)-U_n(t) \big) $ and the corresponding bootstrap quantile process for $t\in(0,1)$ as $\left( {\mathbb{U}}_{n_B}^*\right) ^{-1}(t)=\sqrt{n_B}\Big(\big( {U}_{n_B}^*\big) ^{-1}(t)-U_n^{-1}(t) \Big)$.\\

\noindent One can easily verify along the lines of the proof of \Cref{thm:main2} that for $n\to\infty$ it also holds for $\beta\in(0,1/2)$
\begin{equation}\label{eq:bootstrapideabasis}
\int_{\beta}^{1-\beta}\!\left( \mathbb{U}_n^{-1}(t)\right)^2 \,dt\rightsquigarrow\Xi=\int_{\beta}^{1-\beta}\!\mathbb{G}^2(t) \,dt.
\end{equation}
Hence, this suggests to to approximate the quantiles of $\Xi$ by the quantiles of its bootstrapped version
\begin{equation}
{\Xi}_{n_B}^*\coloneqq\int_{\beta}^{1-\beta}\!\left(\left( {\mathbb{U}}_{n_B}^*\right) ^{-1}(t)\right)^2 \,dt.\label{eq:defofhatXinun}\end{equation}

	Let $\beta\in(0,1/2)$, suppose that \Cref{cond:firstcondition} holds, let $\sqrt{n_B}=o(n)$ and let $\xi_{n_B,\alpha}^{(R)}$ denote the empirical bootstrap quantile of $R$ independent bootstrap realizations ${\Xi}_{n_B}^{*,(1)},\dots,{\Xi}_{n_B}^{*,(R)}$. Under these assumptions, we derive (cf. Section C of the supplement \cite{supplement}) that for any $\alpha\in(0,1)$ it follows
\begin{equation}\label{eq:bootstrapconsitency}\lim_{n,n_B,R\to\infty}\prob\left(\int_{\beta}^{1-\beta}\!\left(\mathbb{U}_n^{-1}(t)\right)^2\,dt \geq \xi_{n_B,\alpha}^{(R)} \right)=\alpha. \end{equation}

Because of \eqref{eq:bootstrapideabasis} the statement \eqref{eq:bootstrapconsitency} guarantees the consistency of $\xi_{n_B,\alpha}^{(R)}$ for $n,n_B,R\to\infty$. Hence, a consistent bootstrap analogue of the test defined by the decision rule \eqref{eq:decision rule} is for $\beta\in(0,1/2)$ given by the \textit{bootstrapped Distribution of Distances (DoD)}-test
\begin{equation}\label{eq:bootstraptest}\Phi_{DoD}^*(\mathcal{X}_n,\mathcal{Y}_m)=\begin{cases}
1, &\text{if}~\frac{nm}{n+m}\dodstat>\xi_{n_B,1-\alpha}^{(R)}\vspace*{5mm}\\
0, &\text{if}~\frac{nm}{n+m}\dodstat\leq \xi_{n_B,1-\alpha}^{(R)}.
\end{cases}\end{equation}


TITLE: Is the graph of the Conway base 13 function connected?
QUESTION [18 upvotes]: IVT Property: If $a<b$ and $y$ is between $f(a)$ and $f(b)$, then there exists $c\in(a,b)$ such that $f(c)=y$.

Theorem. Let $f:\mathbb R \to \mathbb R$ be a function with the IVT Property. If the set of discontinuities of $f$ is first category in $\mathbb R$, then the graph of $f$ is connected.

This is an old Theorem. I assume there must be a counterexample if we leave out the first category assumption, though I don't know of any (help!).
There are functions which are discontinuous everywhere and still have connected graphs. F.B. Jones showed that the graph of a function satisfying $f(x)+f(y)=f(x+y)$ for all $x$ and $y$ can be connected, even if the function is discontinuous everywhere.
So now I come to Conway's example. It has the IVT property in a rather extreme way: it takes every value on every interval. It is discontinuous everywhere. Is the graph connected?

REPLY [13 votes]: Merely knowing that the base-13 function takes every value in every interval does not tell us whether its graph is connected or not. Here is an answer by Eric Wofsey that constructs a function with this property and a connected graph -- on the other hand a comment by Niels J. Diepeveen explains how any such function can be modified to have a disconnected graph without losing the every value-in-every-interval property:

I think a counterexample can be obtained more easily by modifying the function slightly. Let $f$ be Conway's function. Define $g(x)=f(x)+1$ if $f(x)=x$ and $g(x)=f(x)$ otherwise. The fibres of $g$ are still dense in $\mathbb R$ since they differ by only one point each from those of $f$, but $g$ has no fixed points, which gives an easy separation of the graph.

So we need to look closer into Conway's particular definition to resolve the matter.
The graph of the base-13 function is not connected.
In fact it is totally separated (and therefore totally disconnected), since you can carry out variants of the following construction almost everywhere in the plane, enough to separate any two points.
Let $f$ be the Conway function as defined in Wikipedia. I will construct a continuous function $h:\mathbb [0,1]\to[1,2]$ such that $h(x)\ne f(x)$ everywhere. Then
$$\{(x,f(x))\mid 0<x<1 \land f(x)>h(x)\}$$
is a nontrivial relatively clopen subset of the graph of $f$ (since $f(0)=f(1)=0$), so the graph is not connected.
The construction depends on the fact that the intersection of the graph of $f$ with the rectangle $[0,1]\times[1,2]$ is the union of countably many functions $f_i$ such that

$f_i$'s domain is a subset of $[0,1]$
$f_i$ is non-decreasing, and
$f_i$ is surjective onto $[1,2]$.

Namely, each $f_i$ handles the inputs where the encoded decimal point is in a particular position, with a particular sequence of tridecimal digits in front of it. Each of them looks a bit like the Cantor function with the interior of each plateau removed, such that there is a horizontal gap instead.
The properties of$f_i$ noted above means that it can be uniquely extended to a non-decreasing $g_i:[0,1]\to[1,2]$. (At points where $f_i(x)$ is not defined, there can only be one possible value of $g_i(x)$ that won't break monotonicity). We have that $g_i(0)=1$, $g_i(1)=2$ and $g_i$ is continuous.
My $h$ will be strictly decreasing, with its values chosen such that it intersects each $g_i$ at an $x$-coordinate where $f_i$ is not defined. This prevents it from intersecting each of the $f_i$s and therefore from intersecting all of $f$.
We start by setting $h(0)=2$, $h(1)=1$ and now inductively define a sequence of additional points on $h$. In this phase we maintain the invariants that

$h$ is defined at finitely many points in $[0,1]$.
$h(x)$ is (so far) only defined for points where $f(x)=0$.
Whenever $h(a)$ and $h(b)$ are defined for distinct $a$ and $b$, the slope $\frac{h(a)-h(b)}{a-b}$ will be strictly between $-2$ and $0$. (We easily see that it is enough to enforce this between neighboring points).

Now in step $i$ we will chose an $x_i$ and $h(x_i)$ which prevents $h$ from meeting $f_i$. Consider the piecewise linear function we get from interpolating linearly between the known points of $h$. It is strictly decreasing, so it intersects $g_i$ at exactly one point. If this happens to be at an already known point of $h$, we don't need to add any point in this step.
Otherwise the points where near the intersection point where the slope condition above will let us place a new $(x_i,h(x_i))$ form an open parallelogram of $[0,1]\times[1,2]$, which contains the intersection point. The set of $x$ such that $(x,g_i(x))$ is in the parallelogram is open and nonempty, and therefore we can chose an $x_i$ in this set with $f(x_i)=0$. Now set $h(x_i)=g_i(x_i)$.
At the end of $\omega$ many steps, we will have defined $h(x)$ for a dense set of $x$s, because each interval on the $x$ axis contains the entire preimage of the interior of $[1,2]$ under at least one of the $g_i$s.
This means that $x\mapsto h(x)+x$ is Lipschitz with Lipschitz constant $1$ defined on a dense subset of $[0,1]$, and it therefore extends uniquely to a function on all of $[0,1]$ with the same Lipschitz constant. Subtracting $x$ back out gives us a strictly decreasing continuous $h$ that avoids all $f_i$, as desired.


TITLE: Showing that two tuples are equal
QUESTION [0 upvotes]: Suppose we have a function $$g:A\rightarrow\bigcup_{n\in\mathbb{Z}^+}\mathbb{Q}^n.$$ Here, $A$ is the set of sequences $t_k\in\mathbb{Q}$ that are eventually constant. We define $t_k=(x_1,x_2,x_3,...,x_n,x_k,x_k,x_k,...)$, and the function by $f(t_k)=(x_1,x_2,x_3,...,x_n)$. I am trying to show that this is injective.
If we take $t_a,t_b\in A$, then how does $f(t_a)=f(t_b)\implies t_a=t_b$.

REPLY [1 votes]: The $f$ you defined is not one-one (With a counterexample already mentioned in the comments). Rather define $f(x_1,\cdots,x_n,q,q,q,\cdots)=(x_1,\cdots,x_n,q)$. It is easy to see that this $f$ is bijective.
We want to show that $f$ is injective. I.E., if $f(a)=f(b)$ then $a=b$. First of all, if $f(a)=f(b)$, then both must be of equal length (i.e. both must belong to $\mathbb Q^{n+1}$ for a fixed $n\in\mathbb \{0,1,...\}$). Now that we've established both are of equal length, tuple equality means that every element of the tuple is equal. By reconstruction of $a$ and $b$, we see that $a$ and $b$ must be equal


TITLE: Derivable functions
QUESTION [1 upvotes]: If $f: \mathbb{R} \rightarrow \mathbb{R} \in C^{n}$ (class $C^{n}$) and $f^{(i)}(a) = 0, \forall i \in \{0,1,2,\cdots ,n\}$ . Prove that for $k\leq n$ :
$$ f(x)=(x-a)^k g(x)$$
Where $g : \mathbb{R} \rightarrow \mathbb{R} \in C^{n-k}$
My attempt :
By Taylor's theorem: for $x\in \mathbb{R}$ exists $c_{x}$ between $x$ and $a$ such that :
$$f(x)=f(a)+f'(a)(x-a)+\cdot + \dfrac{f^{(k-1)}(a)}{(k-1)!}(x-a)^{k-1}+\dfrac{f^{(k)}(c_x)}{k!}(x-a)^{k} $$
Then :
$$ f(x) = (x-a)^{k} \dfrac{f^{(k)}(c_x)}{k!}$$
My idea is define $g(x)= \dfrac{f^{(k)}(c_x)}{k!}$
I would like to know if that definition is good or not.
The fact that $g$ is $C^{n-k}$ is clear from the fact that $f$ is $C^{n}$

REPLY [0 votes]: You are complicating things by introducing $c_x$. Why not just define $g(x)$ to be $\frac {f(x)} {(x-a)^{k}}$ for $x \neq a$ and $0$ for $x =a$. Repeated application of L'Hopital's Rule show that $g$ is $C^{n-k}$.


TITLE: For the differential equation given by $(x^2-y^2)dx+3xydy=0$ the general solution is $(x^2+2y^2)^3 =cx^2$
QUESTION [1 upvotes]: For the differential equation given by $$(x^2-y^2)dx+3xy \ dy=0$$ the general soultion is $$(x^2+2y^2)^3 =cx^2$$ Check this solution by differentiating and rewriting to get the original function.

I solved for $\frac{dy}{dx}$ and got $$\frac{dy}{dx}=\frac{cx-3x(x^2+2y^2)^2} {6y(x^2+2y^2)^2}$$ I was told to solve for $c$ and multiply by $dx$. but I cannot figure out how to get this to the original equation. My teacher said to use implicit differentiation so I solved for $\frac{dy}{dx}$.

REPLY [0 votes]: Calling
$$
f(x,y) = (x^2 + 2 y^2)^3 -c x^2 = 0
$$
we have
$$
df=f_x dx+f_y dy = 0\to y' = -\frac{f_x}{f_y} = \frac{x \left(c-3 \left(x^2+2 y^2\right)^2\right)}{6 y \left(x^2+2 y^2\right)^2}
$$
now substituting $c = \frac{\left(x^2+2 y^2\right)^3}{x^2}$ and simplifying we obtain
$$
y' = \frac{y}{3 x}-\frac{x}{3 y}
$$
as expected.
NOTE
now making $z = \frac yx \to y' = x z' + z$ we have the transformed DE
$$
x z' = \frac 13\left(z-\frac 1z\right)-z
$$
which is separable and can be easily solved.


TITLE: Group theory and direct product
QUESTION [5 upvotes]: Let $G$ be a finite group such that $x^2=e$ for any $x \in G$ (that is: every element other than identity is of order $2$). Then $G$ is isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_2\times\ldots\times\mathbb{Z}_2$.

REPLY [2 votes]: The fact that $x^2=e$ implies that $G$ is abelian since $(ab)^2=e$ so $abab=e$ hence $ba=a^{-1}b^{-1}=ab$ (because $a,b$ of order 2). Moreover you have that 2 divides the order of $G$. The result follows from Fundamental theorem of finitely generated abelian groups.


TITLE: Subgroup of Finite Index Containing a Given Finitely Generated Subgroup of a Free Group: Problem 12 in 1A in Hatcher.
QUESTION [2 upvotes]: Problem 1A.12 (Hatcher) Let $F$ be a finitely generated free group and $H$ be a finitely generated subgroup of $F$. Let $x\in F-H$.
  Show that there is a finite index subgroup $K$ of $F$ such that $H\subseteq K$ and $x\notin K$.

Here is my attempt.
Let $X$ be the wedge sum of appropriately many circles such that the fundamental group of $X$ can be identified with $F$. Since $H$ is a finitely generated subgroup of $F$, we can find a finite sheeted covering $p:\tilde X\to X$ of $X$ such that $p_*(\pi_1(\tilde X, \tilde x_0))=H$, where $\tilde x_0$ is a point in $\tilde X$. We know that $\tilde X$ is also a graph because any covering space of a graph is also a graph.
Let $\gamma$ be a path in $X$ (based at the only vertex in $X$) which corresponds to $x$. Since $x\notin H$, we know that the lift $\tilde \gamma$ of $\gamma$ starting at $\tilde x_0$ in $\tilde X$ is not a loop.
Now Hatcher has given a hint to use the following fact:

Fact. Let $X$ be a wedge sum of $n$ circles, with natural graph structure, and let $\tilde X\to X$ be a covering space with $Y\subseteq \tilde X$ a finite connected subgraph. Show there is a finite graph $Z\supseteq Y$ having the same vertex set as $Y$, such that the projection $Y\to X$ extends to a covering space $Z\to X$.

Back to our problem, we can think of $\tilde \gamma$ as a subgraph of $\tilde X$. By the "fact" above, we can find a connected graph $\tilde Y$  with the same vertex set as those appearing in $\tilde \gamma$ such that the the projection $p:\tilde \gamma\to X$ can be extended to a covering $\tilde Y\to X$.
I am stuck here.

REPLY [3 votes]: As an algebraist, I prefer to use different language, but I think the solution is essentially the same.
From the generators of $H$, you can construct a (usually incomplete) Schreier graph for $H$ in $F$, in which any reduced word that lies in $H$ will trace out a circuit from the base point. (You can construct this graph very efficiently using the stamndard coset enumeration procedure.)
We know that the word $x$ does not label such a circuit. If it fails to label a path from in the graph from the base point, then add extra vertices to make it do so, and let $V$ be the resulting set of vertices.
Now just complete the graph, by adding extra labelled edges,  in any way you like. It is easy to see that you can do that. For example, you could think of the graph as defining incomplete permutations of $K$, one for each free generator of $F$, and so it is just a matter of tending partial bijections to a complete bijection of $K$.
Now the subgroup defined by the labels of all circuits based at $1$ is the required subgroup $K$. Each vertex of the graph corresponds to a coset of $K$ in $F$, so the index $|F:K|$ is equal to $|V|$. You could also think of the graph as defining a homomorphism $F \to {\rm Sym}(V)$.


TITLE: Is this parametric curve a rotated parabola?
QUESTION [2 upvotes]: I have a parametric curve that is quadratic in both x(a) and y(a).  Specifically,
$$x(a) = -a^2 +150a$$
$$y(a) = -3a^2 + 500a$$
It looks like a rotated parabola.  How can I be sure?
See my Maple worksheet.
Thanks,
Matt

REPLY [1 votes]: Note that for large $a$ the functions are asymptotic to $(x,y)=(-a^2,-3a^2)$; hence the line $y=3x$ must be the axis of symmetry if this is to be a parabola. By comparison, the standard parabola has $x=0$ as axis of symmetry. This suggests the change of coordinates $u=y-3x,\, v=x+3y$, chosen such that $u=0$ is the line $y=3x$ and the $uv$-axes are orthogonal. In these coordinates, we immediately have  $$u=y-3x=50a\implies a=u/50\implies v=1650a-10a^2=31u-\frac{1}{50}u^2$$
which is clearly a parabola.


TITLE: how can I calculate the probability to get triples or better when throwing n 6-sided dice?
QUESTION [2 upvotes]: I've been banging my head on a wall with this question. I'm designing a game and would like to implement a loot system inspired by a game called "Vermintide" where players roll a certain number of dice and gain loot according to the result.
I want my players to get rewards depending on the result of the dice. but I need to evaluate the quality of items, and the number of dice they get to throw based on the probability.
Essentially if they get doubles they get a standard item, if they get triples they get a magic item etc...
I heard of the "birthday problem" and "multinomials" but most of what I could find about it seemed to be very particular cases (I found birthday problem for 2 or more but not for 3 or more, which seems much less trivial).
Is there a smart way to go about this problem which I first thought was going to be trivial, and the more I search the more it seems complicated.

REPLY [0 votes]: The OP is correct in saying that this is a generalization of the Birthday Problem and that it is harder because we are interested in cases where the number of people with the same birthday is greater than two.  One approach is by way of exponential generating functions.
Let's take a concrete example.  Suppose we want to roll $10$ six-sided dice and find the probability that at least one number comes up $5$ or more times.  It seems easier to consider the complementary event, i.e. all numbers come up $4$ or fewer times.  There are $6^{10}$ possible sequences of die rolls, all of which we assume are equally likely.  We would like to count the number of sequences in which no number comes up more than $4$ times.  We generalize the problem a bit and think about a sequence of $n$ die rolls, and let the number of sequences in which no number appears more than $4$ times be $a_n$.
The exponential generating function of $a_n$ is defined to be
$$f(x) = \sum_{n=0}^{\infty} \frac{1}{n!} a_n x^n$$
Since each die has $6$ sides and each number appears no more than $4$ times,
$$f(x) = \left( \sum_{i=0}^4 \frac{1}{i!} x^i \right)^6$$
The number we want in our problem, $a_{10}$, is $10!$ times the coefficient of $x^{10}$ when $f(x)$ is expanded.  I suppose a pencil and paper solution is possible, but I took the easy way out and used a computer algebra system to find that the coefficient of $x^{10}$ is $2177 / 144$.  Therefore the number of sequences of $10$ die rolls in which no number appears more than $4$ times is $$a_{10} = 10! \times \frac{2177}{ 144} = 54,860,400$$
So the probability that no number appears more than $4$ times in $10$ rolls is
$$p = \frac{a_{10}}{6^{10}} = 0.907291$$
and the probability that at least one number appears $5$ times or more is
$$1-p = 0.0927093$$


TITLE: Space of integrands for stochastic processes
QUESTION [1 upvotes]: In Evan's book "An Introduction to Stochastic Differential Equations", the space  $\mathbb{L}^2(0,T)$ denotes the space of progressively measurable stochastic processes $G$ such that:
$E(\int_{0}^TG^2dt)<+\infty$
and later the author introduces a larger class of integrands, $\mathbb{M}^2(0,T)$, the space of progressively measurable stochastic processes $G$ such that:
$\int_{0}^TG^2dt<+\infty$ (a.s).
I do not understand why $\mathbb{M}^2(0,T)$ is larger than $\mathbb{L}^2(0,T)$.
If $|Y|<+\infty$ a.s. then $E(|Y|)<+\infty$ ?

REPLY [2 votes]: $$\left(\operatorname{E}[\vert X \vert] < \infty \implies \vert X \vert \underset{\text{a.s.}}{<} \infty\right) \text{ but } \left(\vert X \vert \underset{\text{a.s.}}{<} \infty \kern.6em\not\kern -.6em \implies \operatorname{E}[\vert X \vert] < \infty\right)$$
To see the latter non-implication, let $X$ be equal to $2^n$ with probability $2^{-n}$, for $n=1,2,3,\ldots$.
$X$ is finite almost surely, but its expectation diverges.


TITLE: Graph with total chromatic number $\chi''(G)=\chi'(G)+\chi(G)$
QUESTION [5 upvotes]: 1)I try to show that the graphs with total chromatic number $\chi''(G)=\chi'(G)+\chi(G)$ are exactly the bipartite graphs.
Definition https://en.wikipedia.org/wiki/Total_coloring
After the answer of Smylic
2)If $\chi''(G)=\chi'(G)+\chi(G)$ holds then the graph should be bipartite

REPLY [3 votes]: This is not true, because $\chi''(C_6) = 3 \ne 4 = 2 + 2 = \chi'(C_6) + \chi(C_6)$.


TITLE: How to show results for schemes when the affine case is easy?
QUESTION [1 upvotes]: For example, I have to show every scheme admits a morphism $X\to \operatorname{Spec} \mathbb{Z}$
or that $\operatorname{Hom}_S(T,\mathbb{A}_S^1)\cong \mathcal{O}_T(T)$ for every $S$-scheme T, where $S$ is affine
If I assume that $X$ and $T$ are spec of ring that's easy. How shall I prove those for schemes? I don't know how to glue together these results

REPLY [1 votes]: Recall that there is a natural isomorphism $$\operatorname{Hom}_{\mathbf{Sch}}(X, \operatorname{Spec}{A}) \cong \operatorname{Hom}_{\mathbf{Ring}}(A, \Gamma(X, \mathcal{O}_X)).$$ Gluing cannot be completely avoided, as the proof of this result requires some work via gluing. You can find it in every introduction on scheme theory.


TITLE: Certainty Affairs
QUESTION [1 upvotes]: I have a 3000 telephone number list. A computer software has found (automatically) that all the numbers are out of service. My boss mistrusts of that software, so he has asked me to pick a sample list in order to do the calls manually. That sample list must be created in a random way. What should be minimum size of the sample list necessary to justify the software? I'm not a mathematician but i heard something about the Chi-squared distribution.
Thanks in advance.
PD: It seems homework, but it is not!!! This is a real life problem ToT.

REPLY [0 votes]: See if you can get information from some of the phone companies about how many numbers go in and out of service at a time and their current portion of active numbers over inactive numbers. If they're similar (statistically), you can pretend they're all from an imaginary typical company.
Imagine the process of dropping or gaining your phone number as a state machine. Initially, there's a portion $a=\text{active/numbers}$ of the numbers which are in service, and a portion $i=\text{inactive/numbers}=1-a$ whose are not. This would form the first branch of the probability tree, with an edge $\text{Start}\rightarrow \text{Active}$ labelled $a$ and likewise to Inactive by $i$. However, in a stochastic matrix model, you would use these as the coordinates of a vector $[a,i]$, called the initial state vector $S_0$.
Next, you have the change of state. The first pair of numbers to look at are the portion of numbers that go out of service $a'_1$ over some time period and the portion of numbers that remain in service $a'_2$ out of $a$. As a ratio of the numbers in service before they lost or kept numbers, it won't matter if the figures are out of date, and hence not matched to a portion of $a$. These form the 2nd branch of the probability tree extending from the node for active numbers. Likewise, $i_1, i_2$ are the portions of numbers that remain inactive or become reassigned, and complete the 2nd level of the probability tree.
Form a $2 \times 2$ matrix whose columns describe activity/inactivity probabilities for a state change, and rows the different starting states those probabilities are relevant to:
$P=\begin{pmatrix}a_1 & a_2 \\ i_1 & i_2\end{pmatrix}$
At this time you want to find the stationary probability vector for $S_0, P$, which is the eigenvector of $P$ which $S_0$ tends to as $P$ is applied repeatedly to it. In particular, it should give us a pair of probabilities, a stable version of $S_0$ whose coordinates have the same meaning, but for asymptotic likelihood of activity or inactivity, and hence something that better describes the long-term relevance of an outdated document from an imaginary company.
We'll call this vector $S'=[c_a,c_i]$, and define it to be the vector such that $S'P=S', c_a+c_i=1$. Hence,
$[c_a a_1+c_i i_1, c_a a_2 + c_i i_2]=[c_a, c_i],$ or
$\begin{cases}
c_a (a_1-1)+c_i i_1 = 0, \\
c_a a_2 + c_i (i_2-1) = 0, \\
c_a+c_i = 1
\end{cases}$


TITLE: complex polynomial has zeroes only in the upper half plane
QUESTION [7 upvotes]: Let $f(z)=z^{n}+a_{1}z^{n-1}+...+a_{n}$ be a polynomial with complex coefficients and suppose it has $n$ zeros in the upper half plane, that is $\operatorname{Im} z>0$, and let $\alpha_ {k}$ be the real part of $a_{k}$. Show that $\alpha(x)=x^{n}+\alpha_{1}x^{n-1}+...+\alpha_{n}$ has $n$ real distinct roots.

REPLY [2 votes]: the distinct comes from the following :
Since $$\alpha(x)=\prod_{k=1}^{n}(x-\alpha_k)$$
$$\alpha'(x)=\alpha(x)\sum_{k=1}^{n}\frac{1}{x-\alpha_k}$$


TITLE: Fibrations are thought of as epimorphisms
QUESTION [0 upvotes]: In the book More concise algebraic topology on the page 213 they write

We think of fibrations as analogous to epimorphisms.

BUT Hovey on the page 51 says
$f$ is a fibration if it is in $J-inj$.
My question is simple: how epimorphisms (rather than monomorphisms) are all of $J-inj$ ? I.e. how can $J-inj$ be thought of as epis?

REPLY [2 votes]: If you read definition 2.1.7 of Hovey you see that $J$-inj is the maps with the RLP with respect to the maps in $J$. These should remind with $J$ being the inclusions $D^n\to D^n\times I$. One example of such maps are covering maps, these we would definitely want to be surjective.


TITLE: If $ a, b \in \mathbb{C}$ with $|a|^2 - |b|^2 = 1$, then the zeros of $az^{n+1}+bz^n - \overline{b}z - \overline{a} $ lie on the unit circle.
QUESTION [0 upvotes]: I've got absolutely no idea how to approach this problem. I know that if the zeros of a polynomial $p(z)$ lie on the unit circle then $\max |p{'}(z)| = \frac{n}{2} \max|p(z)|$, where $n = deg(p)$. I am not sure the converse is true. Could someone please give a  hint on how to start the solution? My hunch is an easy way to solve it will involve Schwarz's lemma. Thanks in advance!

REPLY [2 votes]: $$
az^{n+1}+bz^n - \overline{b}z - \overline{a} = 0
$$
is equivalent to
$$
 z^n = \frac{\overline{b}z + \overline{a}}{az+b} \, .
$$
Now show that $|z| < 1$ implies $\left|\frac{\overline{b}z + \overline{a}}{az+b} \right| > 1$, and $|z| > 1$ implies $\left|\frac{\overline{b}z + \overline{a}}{az+b} \right| < 1$.
It follows that $|z|=1$ is the only possibility.
In order to show the above implications it is helpful to expand
$$
 |az+b| ^2 - |\overline{b}z + \overline{a}|^2 \, .
$$


TITLE: prove that $G$ is complete graph.
QUESTION [1 upvotes]: suppose that $G$ is connected graph and for every eigenvalue of its adjacency matrix we have $\lambda \geq -1$. prove that $G$ is complete graph.
I think that the easiest way is to show that we have just two distinct eigenvalues,it forces the graph to have diameter 1!so it is complete!
I don't know how to show it.any hint or Idea or theorem that make it possible will be great .thanks a lot.

REPLY [2 votes]: You probably mean adjacency matrix.
For $|G| = 2$, $G$ is connected iff $G$ is complete so it is true.
For $|G| = 3$, the only case needed to check is the one where the graph is a path, but this has an eigenvalue $-\sqrt{2}$.
Now, suppose it is true for $|G| < n$ ($n \ge 4$).
Now, we prove for $|G| = n \ge 4$. Let $A$ be the adjacency matrix of $G$.
$A$ has every eigenvalue $\lambda \ge -1$ iff $A + I$ is positive semidefinite.
By Sylvester's Criterion, this means that $B + I$ is also positive semidefinite, where $B$ is the matrix obtained by deleting the first row and first column of $A$, i.e. $B$ also has every eigenvalue $\ge -1$. By induction, if the graph corresponding to $B$ is connected the it is complete.
So, we've proven that if the subgraph induced by some $n-1$ vertices of $G$ is connected then it is complete. Now, there exists one vertex which does'nt disconnnect the graph (consider a leaf of the spanning tree), so we know there exists a $(n-1)$-clique. Let $V = \{v_1,\cdots,v_n\}$, with $\{v_2,\cdots, v_n\}$ spanning a regular graph, and assume $(v_1,v_2) \in E$. We only need to show that the $1$st vertex is connected to all of them.
Now, the graph induced by deleting $v_3$ is connected, so it must be complete, hence $v_1$ is connected to $v_4,\cdots, v_n$. In particular, this implies that the graph induced by deleting $v_2$ is connected, so it must also be complete, hence $v_1$ is connected to $v_3$, completing the proof.