TITLE: bounding absolute moments given probability of tails
QUESTION [1 upvotes]: Let $X$ be a random variable such that $P(X < t + c) \ge 1-e^{-t^2/2}$ for $t > 0$ and $c > 0$ is some known constant.
I am interested in deriving upper bounds for $E[|X|^k]$ for $k \in \mathbb{Z}$.
My approach is as follows:
$E[|X|^k]^{1/k} = E[|X-c+c|^k]^{1/k} \le E[|X-c|^k]^{1/k} + c$ by the triangle inequality.
Hence, it only remains to bound $E[|X-c|^k]^{1/k}$.
I'm going to exploit the fact that $E[|X-c|^k]^{1/k} = \int_0^{\infty} P(|X-c|^k \ge u)\,du = \int_0^{\infty} ku^{k-1} P(|X-c| \ge u)\,du$.
However, since $P(|X-c| \ge u) \ge P(X-c\ge u)$, I could not invoke the tail probability that I have for $X$.
Any suggestions on how to proceed? If I have results on $P(d - t < X) \ge 1-e^{-t^2/2}$ for some constant $d$, $t>0$, will that be needed here? Thanks!

REPLY [0 votes]: You can use the following approach
$$
E[|X|^k]=\int_{0}^{\infty} t^{k-1}P(|X|>t)\,dt = \int_{0}^c t^{k-1}P(|X|>t)\,dt + \int_{c}^{\infty} t^{k-1}P(|X|>t)\,dt \\
\leq c^{k-1} + \int_{0}^{\infty} (z+c)^{k-1}P(|X|>z+c)\,dz \leq c^{k-1} + \int_{0}^{\infty} (z+c)^{k-1}e^{-\frac{z^2}{2}}\,dz.
$$
In the last inequality, we have used $P(|X|>z+c) \leq e^{-\frac{z^2}{2}}$.
You will need some assumptions on the lower tail. Otherwise, you can construct a random variable whose upper tail is Gaussian and lower tail is like Cauchy, and therefore you will not be able to prove any meaningful upper bound even for $E|X|$. Let me know if this clarifies your doubts.


TITLE: Cosets and quotient groups. What is the difference?
QUESTION [1 upvotes]: So I'm very new to group theory and I'm trying to understand the difference between a coset and a quotiënt group. To me it seems that a quotient group is always also a coset but not the other way around. But I can't seem to grap the exact difference betweem them.
Can anyone give a simple example or intuitive explanation?

REPLY [7 votes]: So you start with a group $G$ and a subgroup $H$.
Then the (left) coset of $H$ for $g\in G$ is a subset of $G$ of the form $\{gh\ |\ h\in H\}$. Also denoted by $gH$. Let me emphasize this one more time: cosets are certain special subsets of $G$.
The collection of all cosets is denoted by $G/H=\{gH\ |\ g\in G\}$. So elements of $G/H$ are cosets, not elements of $G$.
If $H$ is additionally a normal subgroup then $G/H$ can be naturally turned into a group as well and in this situation we call $G/H$ the quotient group.
Example:
Consider $G=\mathbb{Z}$ integers with addition and $H=5\mathbb{Z}$ i.e. all integers divisible by $5$. So every element of $H$ can be written as $5k$ for some $k\in\mathbb{Z}$. Therefore every coset can be written as
$$x+H=\{x+5k\ |\ k\in\mathbb{Z}\}$$
So how many cosets are there? Since every coset is $x+H$ for some integer $x\in\mathbb{Z}$ then you may think that as many as there are integers, right? Wrong. For example
$$\{1+5k\ |\ k\in\mathbb{Z}\}=\{6+5t\ |\ t\in\mathbb{Z}\}$$
These are equal sets and so these two cosets: $1+H$ and $6+H$ are equal. You can verify that there are only 5 cosets of $H$, namely $H$, $1+H$, $2+H$, $3+H$ and $4+H$. They correspond to remainders to division by $5$. So $G/H$ has exactly $5$ elements even though $G$ is infinite.


text:
\section{Conclusions}

We propose a novel framework of decentralized algorithms for smooth and strongly convex objectives. The framework provides a unified viewpoint of several well-known decentralized algorithms and, when instantiated with AGD,
achieves optimal convergence rates in theory and state-of-the-art performance in practice. We leave further generalization to (non-strongly) convex  and non-smooth objectives to future work.

config: arxiv

file: 2006.06733/[Neurips20] Decentralized Acc-AL algorithm /sections/sec6_conclusion.tex


text:
\begin{document}

\maketitle

\begin{abstract}
	We investigate the relationship between algorithmic fractal dimensions and the classical local fractal dimensions of outer measures in Euclidean spaces. We introduce global and local optimality conditions for lower semicomputable outer measures. We prove that globally optimal outer measures exist. Our main theorem states that the classical local fractal dimensions of any locally optimal outer measure coincide exactly with the algorithmic fractal dimensions. Our proof uses an especially convenient locally optimal outer measure $\bkappa$ defined in terms of Kolmogorov complexity. We discuss implications for point-to-set principles.

\end{abstract}

\section{Introduction}
	Algorithmic fractal dimensions, which quantify the density of algorithmic information in individual points~\cite{Lutz03b,AHLM07,LutMay08}, have recently been used to prove new theorems~\cite{LutStu17,Lutz17b,LutStu18,Lutz19,LuLuMa20} about their classical forerunners, the Hausdorff and packing dimensions of sets. Since algorithmic fractal dimensions are products of the theory of computing, and since the aforementioned new theorems are entirely classical (not involving logic or the theory of computing), these developments call for a more thorough investigation of the relationships between algorithmic and classical fractal dimensions. One significant facet of this investigation, initiated by Orponen~\cite{Orpo20}, is to look for purely classical proofs of these new classical theorems.

	In this paper, taking a different approach, we establish direct connections between algorithmic and classical fractal dimensions. Aside from the presence versus absence of algorithms, the most striking difference between algorithmic fractal dimensions and classical fractal dimensions is that the algorithmic dimensions are usefully defined for individual points in Euclidean space, while the classical Hausdorff and packing dimensions vanish on individual points. To bridge this gap, we examine the classical {\it local dimensions} (also called \emph{pointwise dimensions}) of outer measures at individual points in Euclidean spaces~\cite{Falc14}. These local fractal dimensions have been studied at least since the 1930s and are essential tools in multifractal analysis~\cite{Fros35, Falc97}. Outer measures and the algorithmic and local dimensions are defined precisely in Section~\ref{sec:alfd} below.

	Outer measures, introduced by Carath\'{e}odory~\cite{Cara14} in the ``prehistory'' of Hausdorff dimension~\cite{Haus19} (defining what later became known as the 1-dimensional Hausdorff measure), are now best known for their role in Carath\'{e}odory's program~\cite{Cara18} to generalize Lebesgue measure to a wide variety of settings~\cite{Tao11}. However, it is the role of outer measures in local fractal dimensions that are of interest here.

	The second author observed~\cite{Lutz17} that a particular, very nonclassical outer measure $\bkappa$, defined in terms of Kolmogorov complexity, has the property that the classical local fractal dimensions of $\bkappa$ coincide exactly with the algorithmic fractal dimensions at every point in $\R^n$. This property of $\bkappa$ is analogous to Levin's coding theorem~\cite{jLevi73,jLevi74}, which pertains to a particular, very nonclassical subprobability measure $\bm$ on strings. Levin's theorem says that if we substitute $\bm$ for the probability measure $p$ in the classical Shannon \emph{self-information}~\cite{Shan48} $\log 1/p(x)$, then the resulting quantity $\log 1/\bm(x)$ is essentially the prefix Kolmogorov complexity (i.e., the algorithmic information content) of the string $x$.

	Levin defined $\bm$ as an optimal lower semicomputable subprobability measure, so the above analogy leads us to investigate here the algorithmic optimality properties of $\bkappa$ and other outer measures on Euclidean spaces.

	We first investigate outer measures that are \emph{globally optimal}, a property that is closely analogous to the optimality property of Levin's $\bm$. In Section~\ref{sec:gao} we prove that globally optimal outer measures on $\R^n$ exist.

	As it turns out, the outer measure $\bkappa$ is not globally optimal. In Section~\ref{sec:lao} we prove this fact, and we introduce and investigate the more general and more subtly defined class of \emph{locally optimal} outer measures on $\R^n$. Our main theorem establishes that \emph{every} locally optimal outer measure $\mu$ on a Euclidean space $\R^n$ has the property that the classical local fractal dimensions of $\mu$ coincide exactly with the algorithmic dimensions at every point in $\R^n$.

	In Section~\ref{sec:pspdm} we discuss implications of our results, especially for the point-to-set principles that have enabled the new classical results mentioned in the first paragraph of this introduction.

\section{Algorithmic and Local Fractal Dimensions}\label{sec:alfd}
	This section reviews the algorithmic fractal dimensions and the classical local fractal dimensions.

	Following standard practice~\cite{Nies09,DowHir10,LiVit19}, we fix a universal prefix Turing machine $U$ and define the \emph{(prefix) Kolmogorov complexity} of a string $w\in\{0,1\}^*$ to be
	\[\K(w)=\min\left\{|\pi|\;\big|\;\pi\in\{0,1\}^*\text{ and }U(\pi)=w\right\},\]
	i.e., the minimum number of bits required to cause $U$ to output $w$. By standard binary encodings, we extend this from $\{0,1\}^*$ to other countable domains. In particular, the Kolmogorov complexity $\K(q)$ of a rational point $q\in\Q^n$ is well defined.

	The \emph{Kolmogorov complexity} of a point $x\in \R^n$ at a \emph{precision} $r\in\N$ is
	\[\K_r(x)=\min\left\{\K(q)\mid q\in \Q^n\text{ and }|q-x|< 2^{-r}\right\},\]
	where $|q-x|$ is the Euclidean distance from $q$ to $x$.

	We now define the algorithmic fractal dimensions of points in $\R^n$.
	\begin{definition}[\cite{Lutz03b,Mayo02,AHLM07}] Let $x\in \R^n$.
		\begin{enumerate}
			\item The \emph{algorithmic dimension} of $x$ is
			\begin{equation}\label{eq:dim}
				\dim(x)=\liminf_{r\to\infty}\frac{\K_r(x)}{r}.
			\end{equation}
			\item The \emph{strong algorithmic dimension} of $x$ is
			\begin{equation}\label{eq:Dim}
				\Dim(x)=\limsup_{r\to\infty}\frac{\K_r(x)}{r}.
			\end{equation}
		\end{enumerate}
	\end{definition}
	See~\cite{Reim04,Mayo08,LutLut20} for surveys of these notions.

	The classical local fractal dimensions are local properties of outer measures. An \emph{outer measure} on a set $X$~\cite{Tao11} is a function $\mu:\cP(X)\to[0,\infty]$ (where $\cP(X)$ is the power set of $X$) with the following three properties.
	\begin{enumerate}[(i)]
		\item (vanishes on empty set) $\mu(\emptyset)=0$.
		\item (monotonicity) For all $E,F\subseteq X$,
		\[E\subseteq F\implies \mu(E)\leq \mu(F).\]
		\item (countable subadditivity) For all $E_0,E_1,\ldots\subseteq X$,
		\[\mu\left(\bigcup_{n=0}^\infty E_n\right)\leq \sum_{n=0}^\infty \mu(E_n).\]
	\end{enumerate}
	An outer measure $\mu$ is \emph{finite} if $\mu(\R^n)<\infty$.

	\begin{definition}[\cite{Falc14}]
		If $\mu$ is a finite

		outer measure on $\R^n$, then the \emph{lower} and \emph{upper local} (or \emph{pointwise}) \emph{dimensions} of $\mu$ at a point $x\in \R^n$ are
		\begin{equation}\label{eq:dimloc}
			\dimloc\mu(x)=\liminf_{r\to\infty}\frac{\log\frac{1}{\mu(B(x,2^{-r}))}}{r}
		\end{equation}
		and
		\begin{equation}\label{eq:Dimloc}
			\Dimloc\mu(x)=\limsup_{r\to\infty}\frac{\log\frac{1}{\mu(B(x,2^{-r}))}}{r},
		\end{equation}
		respectively. (The logarithms here are base-2, and $B(x,\varepsilon)$ is the open ball of radius $\varepsilon$ about $x$ in $\R^n$.)
	\end{definition}

	As stated in the introduction, our main objective is to identify a class of outer measures that cause the classical local fractal dimensions~\eqref{eq:dimloc} and~\eqref{eq:Dimloc} to coincide with the algorithmic fractal dimensions~\eqref{eq:dim} and~\eqref{eq:Dim}.

\section{Global Algorithmic Optimality}\label{sec:gao}

	The optimality notions that we discuss in this paper concern outer measures with three special properties that we now define.

	\begin{definition}
		An outer measure $\mu$ on $\R^n$ is \emph{finitely supported} on $\Q^n$ if, for every $\varepsilon>0$, there is a finite set $A\subseteq\Q^n$ such that $\mu(\R^n\setminus A)<\varepsilon$.
	\end{definition}

	Note that an outer measure $\mu$ on $\R^n$ that is finitely supported on $\Q^n$ is supported on $\Q^n$ in the usual sense that $\mu(\R^n\setminus\Q^n)=0$. The following example shows that the converse does not hold.

	\begin{example}\label{ex:suppnotfinsupp}
		The function $\mu:\cP(\R^n)\to[0,\infty]$ defined by
		\[
			\mu(E)=
			\begin{cases}
				1-2^{-|E\cap\Q^n|}&\text{if }|E\cap\Q^n|<\infty\\
				2&\text{if }|E\cap\Q^n|=\infty
			\end{cases}
		\]
		is an outer measure on $\R^n$ that is supported, but not finitely supported, on $\Q^n$.
	\end{example}

	\begin{definition}
		An outer measure $\mu$ on $\R^n$ is \emph{strongly finite} if $\mu$ is supported on $\Q^n$ and
		\[\sum_{q\in\Q^n}\mu(\{q\})<\infty.\]
	\end{definition}
	It is clear that every strongly finite outer measure is finite. The outer measure of Example~\ref{ex:suppnotfinsupp} shows that the converse does not hold.

	\begin{definition}
		An outer measure on $\R^n$ is \emph{lower semicomputable} if it is finitely supported on $\Q^n$ and there is a computable function
		\[\hat{\mu}:\cP^{<\omega}(\Q^n) \times\N\to\Q\cap[0,\infty)\]
		(where $\cP^{<\omega}(\Q^n)$ is the \emph{finite power set} of $\Q^n$, i.e, the set of all finite subsets of $\Q^n$) with the following two properties.
		\begin{enumerate}[(i)]
			\item For all $A\in\cP^{<\omega}(\Q^n)$ and $s,t\in\N$,
			\[s\leq t\implies \hat{\mu}(A,s)\leq \hat{\mu}(A,t)\leq \mu(A).\]
			\item For all $A\in \cP^{<\omega}(\Q^n)$,
			\[\lim_{t\to\infty}\hat{\mu}(A,t)=\mu(A).\]
		\end{enumerate}
	\end{definition}

	\begin{lemma}\label{lem:limit}
		Let $\mu$ be a lower semicomputable outer measure on $\R^n$. If $\hat{\mu}$ is a function testifying to the lower semicomputability of $\mu$, then, for all $E\subseteq\R^n$,
		\[\lim\limits_{\substack{A\nearrow E\cap\Q^n\\ t\to\infty}}\hat{\mu}(E,t)=\mu(E),\]
		meaning that, for all $\varepsilon>0$, there exist $A\in\cP^{<\omega}(E\cap\Q^n)$ and $t_0\in\N$ such that, for all $B\in\cP^{<\omega}(E\cap\Q^n)$ and $t\in\N$,
		\[[B\supseteq A\text{ and }t\geq t_0]\implies|\mu(E)-\hat{\mu}(B,t)|<\varepsilon.\]
	\end{lemma}

	\begin{definition}
		An outer measure $\mu$ on $\R^n$ is \emph{globally optimal} if the following conditions hold.
		\begin{enumerate}[(i)]
			\item $\mu$ is strongly finite and lower semicomputable.
			\item For every strongly finite, lower semicomputable outer measure $\nu$ on $\R^n$, there is a constant $\beta\in(0,\infty)$ such that, for all $E\subseteq\R^n$,
			\[\mu(E)\geq\beta\cdot\nu(E).\]
		\end{enumerate}
	\end{definition}

	In proving that globally optimal outer measures exist, we will use a computable enumeration of all strongly finite, lower semicomputable outer measures that take values in $[0,1]$. Our main technical lemma, which we now state, shows that such an enumeration exists.

	\begin{lemma}\label{lem:maintech}
		Let $\Theta$ be the set of all strongly finite, lower semicomputable outer measures $\mu:\cP(\R^n)\to[0,1]$. There is a computable function
		\[\hat{\theta}:\N\times\cP^{<\omega}(\Q^n) \times\N\to\Q\cap[0,1]\]
		such that, if we write
		$\hat{\theta}_k(A,t)=\hat{\theta}(k,A,t)$
		for all $k,t\in\N$ and $A\in \cP^{<\omega}(\Q^n) $, and if we define $\theta_k:\cP (\R^n)\to[0,1]$ by
		\[\theta_k(E)=\lim\limits_{\substack{A\nearrow E\cap \Q^n\\t\to\infty}}\hat{\theta}_k(A,t)\]
		for all $E\subseteq \R^n$, then $\Theta=\{\theta_k\mid k\in\N\}$.
	\end{lemma}
	\begin{proof}
		Let $M_0,M_1,M_2\ldots$ be an enumeration of all prefix Turing machines that take inputs in $\cP^{<\omega}(\Q^n) \times\N$, give outputs in $\Q\cap[0,1]$, and satisfy $M_k(\emptyset,t)=0$ for all $k,t\in\N$. For each $k\in\N$, we define the following functions.

		$\tau_k:\cP^{<\omega}(\Q^n) \times\N\to[0,\infty]$ is given by
		\[\tau_k(A,t)=\min_{B\subseteq A}\max\{s\leq t\mid\text{for all }s'\leq s,\ M_k\text{ halts on input }(B,s')\text{ within $t$ steps}\}.\]

		$\eta_k:\cP^{<\omega}(\Q^n) \times\N\times\N\to\Q\cap[0,1]$ is given by
		\[\eta_k(A,t,T)=\max\limits_{\substack{B\subseteq A\\s\leq t}}\{M_k(B,s)\mid M_k\text{ halts on input $(B,s)$ within $T$ steps}\}.\]

		$\hat{\theta}_k:\cP^{<\omega}(\Q^n) \times\N\to\Q\cap[0,1]$ is given by
		\[\hat{\theta}_k(A,t)=\min\left\{\sum_{i=0}^{\ell-1} \eta_k(A_i,\tau_k(A,t),t)\;\middle|\;A_0,\ldots,A_{\ell-1}\subseteq A\text{ and }A\subseteq \bigcup_{i=0}^{\ell-1} A_i\right\}.\]

		Now fix $k\in\N$. It is immediate from our construction that $\theta_k$ takes values in $[0,1]$ and is finitely supported on $\Q^n$, and that $\hat{\theta}_k$ is computable. To prove that $\theta_k\in\Theta$, then, it remains to show that $\hat{\theta}_k$ satisfies conditions (i) and (ii) from the definition of lower semicomputable outer measures, and that $\theta_k$ is countably subadditive.

		For condition (i), let $A\in\cP^{<\omega}(\Q^n) $ and $s,t\in\N$ with $s\leq t$. Then $\tau_k(A,s)\leq\tau_k(A,t)$, and for all $T\in\N$, $\eta_k(A,s,T)\leq \eta_k(A,t,T)$, so $\hat{\theta}_k(A,s)\leq \hat{\theta}_k(A,t)$.

		For condition (ii), let $A,B\in\cP^{<\omega}(\Q^n) $ with $A\subseteq B$, let $t\in\N$, and let $T\geq t$ be such that $\tau_k(B,T)\geq \tau_k(A,t)$. Then
		\begin{align*}
			\hat{\theta}_k(B,T)&=\min\left\{\sum_{i=0}^{\ell-1} \eta_k(A_i,\tau_k(B,T),T)\;\middle|\;A_0,\ldots,A_{\ell-1}\subseteq B\text{ and }B\subseteq \bigcup_{i=0}^{\ell-1} A_i\right\}\\
			&\geq\min\left\{\sum_{i=0}^{\ell-1} \eta_k(A_i,\tau_k(B,T),T)\;\middle|\;A_0,\ldots,A_{\ell-1}\subseteq A\text{ and }A\subseteq \bigcup_{i=0}^{\ell-1} A_i\right\}\\
			&\geq\min\left\{\sum_{i=0}^{\ell-1} \eta_k(A_i,\tau_k(A,t),t)\;\middle|\;A_0,\ldots,A_{\ell-1}\subseteq A\text{ and }A\subseteq \bigcup_{i=0}^{\ell-1} A_i\right\}\\
			&=\hat{\theta}_k(A,t),
		\end{align*}
		so
		\[\lim_{t\to\infty}\hat{\mu}(A,t)\leq \lim_{t\to\infty}\hat{\mu}(B,t).\]

		To prove that $\theta_k$ is countably subadditive, we first show that, for all $t\in\N$, $\hat{\theta}_k(\cdot,t)$ is finitely subadditive on $\cP^{<\omega}(\Q^n) $. Fix $t\in\N$, let $A\in\cP^{<\omega}(\Q^n) $, and let $A_0,\ldots,A_{\ell-1}\subseteq A$ be such that $A\subseteq\bigcup_{i=0}^{\ell-1}A_i$ and
		\[\hat{\theta}_k(A,t)=\sum_{i=0}^{\ell-1}\eta_k(A_i,\tau_k(A,t),t).\]

		Suppose that, for some $0\leq i<\ell$, we have
		$\eta_k(A_i,\tau_k(A,t))>\hat{\theta}_k(A_i,t)$.
		Then there are sets $A_{i,0},\ldots,A_{i,m-1}\subsetneq A_i$ such that
		\begin{align*}
			\eta_k(A_{i,j},\tau_k(A,t),t)&>\sum_{j=0}^{m-1}\eta_k(A_i,\tau_k(A_i,t),t)\\
			&\geq \sum_{j=0}^{m-1}\eta_k(A_{i,j},\tau_k(A,t),t),
		\end{align*}
		which contradicts the minimality of our choice of $A_0,\ldots,A_{\ell-1}$. Hence, for all $0\leq i<\ell$,
		\[\eta_k(A_i,\tau_k(A,t))\leq \hat{\theta}_k(A_i,t),\]
		so
		\[\hat{\theta}(A,t)=\sum_{i=0}^{\ell-1}\eta_k(A_i,\tau_k(A,t),t)\leq \sum_{i=0}^{\ell-1}\hat{\theta}_k(A_i,t).\]

		Now let $E,E_0,E_1,E_2,\ldots\subseteq \R^n$ be such that $E\subseteq \bigcup_{i=0}^\infty E_i$. Let $\varepsilon>0$, and let $A\in\cP^{<\omega}(E\cap\Q^n)$ and $t\in\N$ be such that
		\[\hat{\theta}_k(A,t)>\theta_k(E)-\varepsilon.\]
		For each $i\in\N$, let $A_i=E_i\cap A$.
		Since $A$ is a finite set, there is some $\ell\in\N$ such that $A\subseteq \bigcup_{i=0}^{\ell-1}A_i$. By Lemma~\ref{lem:limit} and the finite subadditivity of $\hat{\theta}_k(\cdot,t)$,
		\begin{align*}
			\theta_k(E)-\varepsilon&<\hat{\theta}_k(A,t)\\
			&\leq \sum_{i=0}^{\ell-1}\hat{\theta}_k(A_i,t)\\
			&\leq \sum_{i=0}^{\ell-1}\theta_k(E_i).
		\end{align*}
		Letting $\varepsilon\to 0$, we have
		\[\theta_k(E)\leq \sum_{i=0}^\infty\theta_k(E_i),\]
		and we conclude that $\theta_k\in\Theta$, so $\{\theta_k\mid k\in\N\}\subseteq\Theta$.

		For the converse, let $\mu\in\Theta$, and let $\hat{\mu}$ be a witness to the lower semicomputability of $\mu$. Then $\hat{\mu}$ is computable and $\hat{\mu}(\emptyset,t)=0$ for all $t\in\N$, so there is some $k\in\N$ such that, for all $(A,t)\in\cP^{<\omega}(\Q^n) \times\N$, we have $M_k(A,t)=\hat{\mu}(A,t)$.

		We now show that for all $A\in\cP^{<\omega}(\Q^n) $, \[\lim_{t\to\infty}\hat{\theta}_k(A,t)=\lim_{t\to\infty}\hat{\mu}(A,t).\]
		Let $A\in\cP^{<\omega}(\Q^n) $ and $t\in\N$. Then
		\begin{align*}
			\hat{\theta}_k(A,t)&\leq \eta_k(A,\tau_k(A,t),t)\\
			&=\max\limits_{\substack{B\subseteq A\\s\leq \tau_k(A,t)}}\{M_k(B,s)\mid M_k\text{ halts on input $(B,s)$ within $t$ steps}\}\\
			&=\max\limits_{\substack{B\subseteq A\\s\leq \tau_k(A,t)}}M_k(B,s)\\
			&\leq\max\limits_{\substack{B\subseteq A\\s\leq t}}M_k(B,s)\\
			&=M_k(A,t)\\
			&=\hat{\mu}(A,t).
		\end{align*}
		Now let $\varepsilon>0$, let $t\in\N$ be such that, for all $B\subseteq A$,
		\[\hat{\mu}(B,t)\geq\mu(B)-\varepsilon/2^{|A|},\]
		and let $T\in\N$ be such that $\tau_k(A,T)\geq t$. Then for each $B\subseteq A$,
		\begin{align*}
			\eta_k(A,\tau_k(A,T),T)
			&=\max\limits_{\substack{C\subseteq B\\s\leq \tau_k(A,T)}}\{M_k(C,s)\mid M_k\text{ halts on input $(C,s)$ within $T$ steps}\}\\
			&=\max\limits_{\substack{C\subseteq B\\s\leq \tau_k(A,T)}}M_k(C,s)\\
			&= M_k(B,\tau_k(A,T))\\
			&\geq M_k(B,t)\\
			&=\hat{\mu}(B,t).
		\end{align*}
		It follows that
		\begin{align*}
			\hat{\theta}_k(A,T)&=\min\left\{\sum_{i=0}^{\ell-1} \eta_k(A_i,\tau_k(A,T),T)\;\middle|\;A_0,\ldots,A_{\ell-1}\subseteq A\text{ and }A\subseteq \bigcup_{i=0}^{\ell-1} A_i\right\}\\
			&\geq \min\left\{\sum_{i=0}^{\ell-1} \hat{\mu}(A_i,t)\;\middle|\;A_0,\ldots,A_{\ell-1}\subseteq A\text{ and }A\subseteq \bigcup_{i=0}^{\ell-1} A_i\right\}\\
			&\geq \min\left\{\sum_{i=0}^{\ell-1} \left(\mu(A_i)-\frac{\varepsilon}{2^{|A|}}\right)\;\middle|\;A_0,\ldots,A_{\ell-1}\subseteq A\text{ and }A\subseteq \bigcup_{i=0}^{\ell-1} A_i\right\}\\
			&\geq\mu(A)-\varepsilon,
		\end{align*}
		by the countable subadditivity of $\mu$.

		We have shown that for every $A\in\cP^{<\omega}(\Q^n) $, every $\varepsilon>0$, and every sufficiently large $t\in\N$, $\hat{\theta}_k(A,t)\leq\hat{\mu}(A,t)$ and there exists some $T\in\N$ such that $\hat{\theta}_k(A,T)\geq M_k(A,t)-\varepsilon$. This implies that for all $A\in\cP^{<\omega}(\Q^n) $,
		\[\lim_{t\to\infty}\hat{\theta}_k(A,t)=\lim_{t\to\infty}\hat{\mu}(A,t),\]
		and therefore for all $E\subseteq \R^n$,
		\begin{align*}
			\theta_k(E)
			&=\lim\limits_{\substack{A\nearrow E\cap \Q^n\\t\to\infty}}\hat{\theta}_k(A,t)\\
			&=\lim\limits_{\substack{A\nearrow E\cap \Q^n\\t\to\infty}}\hat{\mu}(A,t)\\
			&=\mu(A).
		\end{align*}
		We conclude that $\mu\in\{\theta_k\mid k\in\N\}$, so $\Theta\subseteq \{\theta_k\mid k\in\N\}$.
	\end{proof}

	\begin{theorem}
		Globally optimal outer measures exist.
	\end{theorem}

	\begin{proof}
		Define the strongly finite outer measure $\theta:\cP(\R^n)\to[0,1]$ by
		\[\theta(E)=\sum_{k=0}^\infty\frac{\theta_k(E)}{2^{k+1}},\]
		where $\theta_k$ is defined as in Lemma~\ref{lem:maintech}. This outer measure is supported on $\cP^{<\omega}(\Q^n)$, and the function $\hat{\theta}:\cP^{<\omega}(\Q^n)\times\N\to[0,1]$ given by
		\[\hat{\theta}(A,t)=\sum_{k=0}^t\frac{\hat{\theta}_k(A,t)}{2^{k+1}}\]
		is a witness to the lower semicomputability of $\theta$.

		Let $\mu:\cP(\R^n)\to[0,\infty)$ be any lower semicomputable outer measure that is strongly finite and supported on $\cP^{<\omega}(\Q^n)$, and let \[h=\max_{E\subseteq \R^n}\lceil\mu(E)\rceil.\]
		Then the function $\tilde{\mu}:\cP(\R^n)\to[0,1]$ given by
		\[\tilde{\mu}(E)=\mu(E)/h\]
		belongs to $\Theta$. By Lemma~\ref{lem:maintech}, there is some $k\in\N$ such that, for all $E\subseteq \R^n$,
		\[\theta_k(E)=\tilde{\mu}(E).\]
		We have, for all $E\subseteq\R^n$,
		\[\mu(E)=h\cdot \tilde{\mu}(E)= h\cdot\theta_k(E)\leq h\cdot 2^k\cdot \theta(E),\]
		so $\theta$ is globally optimal.
	\end{proof}

\section{Local Algorithmic Optimality}\label{sec:lao}

	This paper's investigation of algorithmic optimality is primarily driven by a specific outer measure $\bkappa$. To define $\bkappa$, we first define the \emph{Kolmogorov complexity of a set} $E\subseteq\R^n$ to be
	\[\K(E)=\min\{\K(q)\mid q\in E\cap\Q^n\}.\]
	That is, $\K(E)$ is the minimum number of bits required to cause the universal prefix Turing machine $U$ to print \emph{some} rational point in $E$. (Shen and Vereschagin~\cite{SheVer02} introduced a similar notion for a different purpose.)

	\begin{definition}[\cite{Lutz17}]
		Define the function $\bkappa:\cP(\R^n)\to[0,1]$ by
		\[\bkappa(E)=2^{-\K(E)}\]
		for all $E\subseteq\R^n$.
	\end{definition}

	\begin{observation}[\cite{Lutz17}]
		$\bkappa$ is an outer measure on $\R^n$.
	\end{observation}

	Our primary interest in $\bkappa$ is the following connection between classical local fractal dimensions and algorithmic fractal dimensions.

	\begin{observation}[\cite{Lutz17}]\label{obs:kappaloc}
		For all $x\in \R^n$,
		\[\dimloc\bkappa(x)=\dim(x)\]
		and
		\[\Dimloc\bkappa(x)=\Dim(x).\]
	\end{observation}
	\begin{proof}
		By \eqref{eq:dim}--\eqref{eq:Dimloc}, it suffices to note that, for all $x\in\R^n$,
		\[\log\frac{1}{\bkappa(B(x,2^{-r}))}=K_r(x).\qedhere\]
	\end{proof}

	We next investigate the algorithmic properties of the outer measure $\bkappa$.
	\begin{observation}\label{obs:kappasflc}
		$\bkappa$ is strongly finite and lower semicomputable.
	\end{observation}
	\begin{proof}
		It suffices to show three things.
		\begin{enumerate}
			\item
				$\bkappa$ is finitely supported on $\Q^n$. For this, let $\varepsilon>0$. Let
				\[A=\left\{q\in\Q^n\;\middle|\; \K(q)\leq \log\frac{1}{\varepsilon}\right\}.\]
				Then $A$ is a finite subset of $\Q^n$, and
				\begin{align*}
					\K(\R^n\setminus A)&=\min\{\K(q)\mid q\in \Q^n\setminus A\}\\
					&>\log\frac{1}{\varepsilon},
				\end{align*}
				so $\bkappa(\R^n\setminus A)<\varepsilon$.
			\item
				$\displaystyle \sum_{q\in\Q^n}\bkappa(\{q\})<\infty$. For this, just note that
				\[\sum_{q\in\Q^n}\bkappa(\{q\})=\sum_{q\in\Q^n}2^{-\K(q)}\leq 1,\]
				by the Kraft inequality for prefix Kolmogorov complexity.
			\item
				$\bkappa$ is lower semicomputable. This follows immediately from the well known upper semicomputability of the Kolmogorov complexity function.
		\end{enumerate}
	\end{proof}

	\begin{lemma}\label{lem:kappanotgo}
		$\bkappa$ is not globally optimal.
	\end{lemma}
	\begin{proof}
		Define the function $\nu:\cP(\R^n)\to[0,\infty]$ by
		\[\nu(E)=\sum_{q\in E\cap\Q^n}2^{-\K(q)}.\]
		We now show that $\nu$ is a strongly finite, lower semicomputable outer measure on $\R^n$. It is clear that $\nu$ is an outer measure on $\R^n$. It thus suffices to prove that $\nu$ has the properties 1, 2, and 3 proven for $\bkappa$ in the proof of Observation~\ref{obs:kappasflc}. For properties 2 and 3, the proofs for $\nu$ are identical to those for $\bkappa$. For property 1, that $\nu$ is finitely supported on $\Q^n$, let $\varepsilon>0$. By the Kraft inequality for prefix Kolmogorov complexity,
		\[\sum_{q\in\Q^n}2^{-\K(q)}\leq 1,\]
		so there is a finite set $A\subseteq\Q^n$ such that
		\[\nu(\R^n\setminus A)=\sum_{q\in\Q^n\setminus A}2^{-\K(q)}<\varepsilon.\]
		Hence, to prove the lemma, it suffices to exhibit a set $E\subseteq\R^n$ such that, for all $\beta\in(0,\infty)$,
		\begin{equation}\label{eq:kappanotgo}
			\bkappa(E)<\beta\nu (E).
		\end{equation}

		Let $\beta\in(0,\infty)$. Let $c$ be a constant such that, for all $m\in\N$,
		\[\K(m,0,\ldots,0)< \log(m)+2\log\log(m)+c\,.\]
		Let $\alpha\in(0,\infty)$ be some parameter, let $\gamma=2+2\log(\alpha+2)+c$,

		and define the set
		\[E=\left\{q\in\Q^n\;\middle|\;\K(q)>\alpha\right\}.\]
		Then $\bkappa(E)< 2^{-\alpha}$, and
		\begin{align*}
			\nu (E)&= \sum_{q\in E\cap\Q^n}2^{-\K(q)}\\
			&\geq\sum\limits_{\substack{q\in\Q^n\\\K(q)\in(\alpha,\alpha+\gamma)}}2^{-\K(q)}\\
			&\geq 2^{-\alpha-\gamma}\cdot|\{q\in\Q^n\mid \K(q)\in(\alpha,\alpha+\gamma)\}|\,.
		\end{align*}
		There are fewer than $2^{\alpha+1}$ rational points $q$ with $\K(q)\leq\alpha$. For all $m\in\N$ such that $m\leq 2^{\alpha+2}$,
		\begin{align*}
			\K(m,0,\ldots,0)

			&< \alpha+2+2\log(\alpha+2)+c\\
			&=\alpha+\gamma\,,
		\end{align*}
		so there are at least $2^{\alpha+1}$ rational points $q$ with $\K(q)\in(\alpha,\alpha+\gamma)$, and we have $\nu (E)> 2^{-\gamma}$.
		Thus,
		\[\bkappa(E)<2^{\gamma-\alpha}\nu (E).\]
		Choosing $\alpha$ such that
		\[\gamma-\alpha=2+2\log(\alpha+2)+c-\alpha<\log\beta\]
		yields~\eqref{eq:kappanotgo}.
	\end{proof}

	Notwithstanding Lemma~\ref{lem:kappanotgo}, $\bkappa$ does have an optimality property, which we next define. For each $m=(m_1,\ldots,m_n)\in\Z^n$, let
	\[Q_m=[m_1,m_1+1)\times\cdots\times[m_n,m_n+1)\]
	be the \emph{unit cube} at $m$. For each such $m$ and each $r\in\N$, let
	\[Q^{(r)}_m=2^{-r}Q_m=\left\{2^{-r}x\;\middle|\; x\in Q_m\right\}\]
	be the \emph{$r$-dyadic cube} with \emph{address} $m$. Note that each $Q^{(r)}_m$ is ``half-closed, half-open'' in such a way that, for each $r\in\N$, the family
	\[\cQ^{(r)}=\left\{Q^{(r)}_m\;\middle|\;m\in\Z^n\right\}\]
	is a partition of $\R^n$.

	\begin{definition}
		Let $\mu$ and $\nu$ be outer measures on $\R^n$, and let $\cA=(\cA^{(r)}\mid r\in\N)$ be a sequence of families $\cA^{(r)}\subseteq\cP(\R^n)$ of subsets of $\R^n$. We say that $\mu$ \emph{dominates} $\nu$ on $\cA$ if there is a function $\beta:\N\to(0,\infty)$ such that $\beta(r)=2^{-o(r)}$ as $r\to\infty$ and, for every $r\in\N$ and every set $E\in\cA^{(r)}$,
		\[\mu(E)\geq\beta(r)\cdot\nu(E).\]

		We say that $\mu$ \emph{dominates $\nu$ on dyadic cubes} if $\mu$ dominates $\nu$ on $\cQ=(\cQ^{(r)}\mid r\in\N)$. We say that $\mu$ \emph{dominates $\nu$ on balls} if $\mu$ dominates $\nu$ on $\cB=(\cB^{(r)}\mid r\in\N)$, where $\cB^{(r)}$ is the set of all open balls of radius $2^{-r}$ in $\R^n$.
	\end{definition}

	\begin{definition}
		An outer measure $\mu$ on $\R^n$ is \emph{locally optimal} if the following two conditions hold.
		\begin{enumerate}[(i)]
			\item $\mu$ is strongly finite and lower semicomputable.
			\item\label{it:locopt2} For every strongly finite, lower semicomputable outer measure $\nu$ on $\R^n$, $\mu$ dominates $\nu$ on dyadic cubes.
		\end{enumerate}
	\end{definition}

	\begin{theorem}
		The outer measure $\bkappa$ is locally optimal.
	\end{theorem}

	\begin{proof}
		We rely on machinery created for a different purpose by Case and the first author~\cite{CasLut15}. Just as we have ``lifted'' Kolmogorov complexity from $\{0,1\}^*$ to $\Q^n$ via routine encoding, we lift Levin's optimal lower semicomputable subprobability measure $\bm$~\cite{jLevi73,jLevi74} from $\{0,1\}^*$ to $\Q^n$ so that, for all $q\in\Q^n$,
		\[\bm(q)=\sum\limits_{\substack{\pi\\U(\pi)=q}}2^{|\pi|}.\]
		We also set
		\[\bm(E)=\sum_{q\in E\cap\Q^n}\bm(q)\]
		for all $E\subseteq\R^n$. The LDS coding theorem of~\cite{CasLut15} is a mild generalization of Levin's coding theorem~\cite{jLevi73,jLevi74} that tells us that there is a constant $c\in\N$ such that, for all $r\in\N$ and $Q\in\cQ^{(r)}$,
		\begin{equation}\label{eq:lds}
			\K(Q)\leq \log\frac{1}{\bm(Q)}+\K(r)+c.
		\end{equation}
		To prove the present theorem, it suffices by Observation~\ref{obs:kappasflc} to prove that $\bkappa$ satisfies condition~\ref{it:locopt2} of the definition of local optimality. For this, let $\nu$ be a strongly finite, lower semicomputable outer measure on $\R^n$. Define $p_\nu:\Q^n\to[0,\infty]$ by $p_\nu(q)=\nu(\{q\})$ for all $q\in\Q^n$. Then $p_\nu$ is lower semicomputable and $\sum_{q\in\Q^n}p_\nu(q)<\infty$, so the optimality property of $\bm$ tells us that there is a constant $\alpha\in(0,\infty)$ such that, for all $q\in\Q^n$,
		\begin{equation}\label{eq:mopt}
			\bm(q)\geq\alpha p_\nu(q).
		\end{equation}

		Define $\beta:\N\to(0,\infty)$ by
		\[\beta(r)=\alpha 2^{-(\K(r)+c)}\]
		for all $r\in\N$. Then
		\[\lim_{r\to\infty}\frac{\log\frac{1}{\beta(r)}}{r}=\lim_{r\to\infty}\frac{\log\frac{1}{\alpha(r)}+\K(r)+c}{r}=0,\]
		so $\beta(r)=2^{-o(r)}$ as $r\to\infty$. Also, for all $r\in\N$ and $Q\in\cQ^{(r)}$,~\eqref{eq:lds},~\eqref{eq:mopt}, and the countable subadditivity of $\nu$ tell us that
		\begin{align*}
			\bkappa(Q)&=2^{-\K(Q)}\\
			&\geq 2^{-(\K(r)+c)}\bm(Q)\\
			&=2^{-(\K(r)+c)}\sum_{q\in Q\cap\Q^n}\bm(q)\\
			&\geq\beta(r)\sum_{q\in Q\cap\Q^n}p_\nu(q)\\
			&=\beta(r)\sum_{q\in Q\cap\Q^n}\nu(\{q\})\\
			&\geq \beta(r)\nu(Q).
		\end{align*}
		This shows that $\bkappa$ dominates $\nu$ on dyadic cubes, confirming that $\bkappa$ is locally optimal.
	\end{proof}

	\begin{corollary}
		A strongly finite, lower semicomputable outer measure on $\R^n$ is locally optimal if and only if it dominates $\bkappa$ on dyadic cubes.
	\end{corollary}

	\begin{lemma}\label{lem:ballcube}
		There is a constant $c\in\N$ such that, for every $r\in\N$, every $r$-dyadic cube $Q\in\cQ^{(r)}$, and every open ball $B\subseteq\R^n$ of radius $2^{-r}$ that intersects $Q$,
		\[|\K(B)-\K(Q)|\leq\K(r)+c.\]
	\end{lemma}
	\begin{proof}
		Lemma 3.5 of~\cite{CasLut15} gives us a constant $c_1\in\N$ such that, for all $r$, $Q$, and $B$ as in the present lemma,
		\[\K(B)\leq\K(Q)+\K(r)+c_1.\]
		Hence it suffices to show that there is a constant $c_2$ such that, for all $r$, $Q$, and $B$ as in the present lemma,
		\[\K(Q)\leq\K(B)+\K(r)+c_2.\]
		Let $M$ be a prefix Turing machine that, on input $\pi_1\pi_2\pi_3$ where $U(\pi_1)=r\in\N$, and $U(\pi_2)=k\in\N$, and $U(\pi_3)=(q_1,\ldots,q_n)\in\Q^n$, outputs the lexicographically $k$\textsuperscript{th} point in the product set
		\[\prod_{i=1}^n\left\{2^{-r}(\lfloor 2^{r}q_i\rfloor-2),2^{-r}(\lfloor 2^{r}q_i\rfloor-1),2^{-r}\lfloor 2^{r}q_i\rfloor,2^{-r}(\lfloor 2^{r}q_i\rfloor+1),2^{-r}(\lfloor 2^{r}q_i\rfloor+2)\right\}.\]

		Let $r$, $Q$, and $B$ be as in the present lemma. Let $q\in B\cap\Q^n$ be such that $\K(q)=\K(B)$. Then there is some point $p=(p_1,\ldots,p_n)\in Q\cap B\cap\Q^n$ such that $|p-q|<2^{1-r}$. Hence $Q$ is the $r$-dyadic cube with address $(\lfloor 2^rp_1\rfloor,\ldots,\lfloor 2^rp_n\rfloor)$, and for each $1\leq i\leq n$,
		\[|\lfloor 2^rq_i\rfloor-\lfloor 2^rp_i\rfloor|\leq 2.\]
		That is, the address of $Q$ belongs to the product set
		\[\prod_{i=1}^n\left\{\lfloor 2^{r}q_i\rfloor-2,\lfloor 2^{r}q_i\rfloor-1,\lfloor 2^{r}q_i\rfloor,\lfloor 2^{r}q_i\rfloor+1,\lfloor 2^{r}q_i\rfloor+2\right\}.\]
		Let $k\leq 5^n$ be the lexicographical index of $Q$'s address within this set, and let $\pi_1$, $\pi_2$, and $\pi_3$ be witnesses to $\K(r)$, $\K(k)$, and $\K(q)$, respectively. Then $M(\pi_1\pi_2\pi_3)\in Q$, so letting $c_M$ be an optimality constant for the machine $M$, we have
		\begin{align*}
			\K(Q)&\leq |\pi_1|+|\pi_2|+|\pi_3|+c_M\\
			&=\K(r)+\K(k)+\K(q)+c_M\\
			&=\K(B)+\K(r)+\K(k)+c_M\,.
		\end{align*}
		Since $k\leq 5^n$, there is some constant $c_3$ such that $\K(k)\leq 2\log(5^n)+c_3$, so the constant
		\[c_2=c_M+2\log(5^n)+c_3\]
		affirms the lemma.
	\end{proof}

	\begin{lemma}
		A strongly finite, lower semicomputable outer measure $\mu$ dominates $\bkappa$ on balls if and only if it dominates $\bkappa$ on dyadic cubes.
	\end{lemma}
	\begin{proof}
		Suppose that $\mu$ dominates $\bkappa$ on balls. Then for every $x\in\R^n$,
		\[\mu(B(x,2^{-r}))=2^{-o(r)}\bkappa(B(x,2^{-r})).\]
		Let $r\in\Z$, and let $Q$ be an $r$-dyadic cube with center $q$, and let $B=B(q,2^{-r-1})$, so that $B\subseteq Q$. Then, applying Lemma~\ref{lem:ballcube},
		\begin{align*}
			\mu(Q)&\geq\mu(B)\\
			&= 2^{-o(r)}\bkappa(B)\\
			&= 2^{-\K(B)-o(r)}\\
			&=2^{-\K(Q)-o(r)}\\
			&=2^{-o(r)}\bkappa(Q),
		\end{align*}
		so $\mu$ dominates $\bkappa$ on dyadic cubes.

		Now suppose that $\mu$ dominates $\bkappa$ on dyadic cubes. Then for every $r$-dyadic cube $Q$,
		\[\mu(Q)=2^{-o(r)}\bkappa(Q).\]
		Let $r\in\Z$, $x\in\R^n$, and $B=B(x,2^{-r})$. Let $Q$ be the $\big(r+\big\lceil\log\sqrt{n}\big\rceil\big)$-dyadic cube containing $x$, so that $Q\subseteq B$.
		Applying Lemma~\ref{lem:ballcube},
		\begin{align*}
			\mu(B)&\geq\mu(Q)\\
			&= 2^{-o(r)}\bkappa(Q)\\
			&= 2^{-\K(Q)-o(r)}\\
			&=2^{-\K(B)-o(r)}\\
			&=2^{-o(r)}\bkappa(B),
		\end{align*}
		so $\mu$ dominates $\bkappa$ on balls.
	\end{proof}

	\begin{corollary}\label{cor:tfaeopt}
		For every strongly finite, lower semicomputable outer measure $\mu$ on $\R^n$, the following three conditions are equivalent.
		\begin{enumerate}[(1)]
			\item $\mu$ is locally optimal.
			\item $\mu$ dominates $\bkappa$ on balls.
			\item For every strongly finite, lower semicomputable outer measure $\nu$ on $\R^n$, $\mu$ dominates $\nu$ on balls.
		\end{enumerate}
	\end{corollary}

	We now have everything we need to prove our main theorem, which is the following generalization of Observation~\ref{obs:kappaloc}.

	\begin{theorem}\label{thm:main}
		If $\mu$ is any locally optimal outer measure on $\R^n$, then for all $x\in \R^n$,
		\begin{equation}\label{eq:dimlocdim}
			\dimloc\mu(x)=\dim(x)
		\end{equation}
		and
		\begin{equation}\label{eq:DimlocDim}
			\Dimloc\mu(x)=\Dim(x).
		\end{equation}
	\end{theorem}

	\begin{proof}
		Let $\mu$ be any locally optimal outer measure on $\R^n$. By Corollary~\ref{cor:tfaeopt}, $\bkappa$ dominates $\mu$ on balls, and $\mu$ dominates $\bkappa$ on balls. That is, there exist two function $\beta_1,\beta_2:\N\to(0,\infty)$ such that $\beta_1(r)=2^{-o(r)}$ and $\beta_2(r)=2^{-o(r)}$ as $r\to\infty$, and, for every $r\in\N$ and $x\in\R^n$,
		\[\bkappa(B(x,2^{-r}))\geq \beta_1(r)\mu(B(x,2^{-r}))\]
		and
		\[\mu(B(x,2^{-r}))\geq \beta_2(r)\bkappa(B(x,2^{-r})).\]
		Letting $\beta(r)=\min\{\beta_1(r),\beta_2(r)\}$, we have $\beta(r)=2^{-o(r)}$ as $r\to\infty$ and, for every $r\in\N$ and $x\in\R^n$,
		\[\left|\log\frac{1}{\mu(B(x,2^{-r}))}-\log\frac{1}{\bkappa(B(x,2^{-r}))}\right|\leq\log\frac{1}{\beta(r)}.\]
		It follows that, for all $x\in\R^n$,
		\[\left|\log\frac{1}{\mu(B(x,2^{-r}))}-K_r(x)\right|=o(r)\]
		as $r\to\infty$, whence~\eqref{eq:dimlocdim} and~\eqref{eq:DimlocDim} follow from~\eqref{eq:dim}--\eqref{eq:Dimloc}.
	\end{proof}

\section{Point-to-Set Principles and Dimensions of Measures}\label{sec:pspdm}

		Local dimensions of measures give rise to global dimensions of measures, which we now briefly comment on. In classical fractal geometry, the global dimensions of Borel measures play a substantial role in studying the interplay between local and global properties of fractal sets and measures. The material in this section is from~\cite{Lutz17}.

	\begin{definition}[\cite{Falc97}]
		For any locally finite Borel measure $\mu$ on $\R^n$, the \emph{lower} and \emph{upper Hausdorff and packing dimension} of $\mu$ are
		\begin{align*}
		\dimH(\mu)&=\sup\big\{\alpha \;\big|\; \mu(\{x \mid \dim_\mu(x) < \alpha\}) = 0\big\}
		\\\DimH(\mu)&=\inf\big\{\alpha \;\big|\; \mu(\{x \mid \dim_\mu(x) > \alpha\}) = 0\big\}
		\\\dimP(\mu)&=\sup\big\{\alpha \;\big|\; \mu(\{x \mid \Dim_\mu(x) < \alpha\}) = 0\big\}
		\\\DimP(\mu)&=\inf\big\{\alpha \;\big|\; \mu(\{x \mid \Dim_\mu(x) > \alpha\}) = 0\big\},
		\end{align*}
		respectively.
	\end{definition}
	Extending these definitions to outer measures, we may consider global dimensions of the outer measure $\bkappa$. Since $\bkappa$ is supported on $\cP^{<\omega}(\Q^n)$ and $\dim(x)=0$ for all $x\in\cP^{<\omega}(\Q^n)$,
	\begin{equation}\label{eq:globaldim}
		\dimH(\bkappa)=\DimH(\bkappa)=\dimP(\bkappa)=\DimP(\bkappa)=0.
	\end{equation}

	The \emph{point-to-set principle}~\cite{LutLut18} expresses classical Hausdorff and packing dimensions in terms of \emph{relativized} algorithmic dimensions. That is, algorithmic dimensions in which the underlying universal Turing machine $U$ is an oracle machine with access to some oracle $A\subseteq\N$. We write $\dim^A(x)$ and $\Dim^A(x)$ to denote the algorithmic dimension and strong algorithmic dimension of a point $x\in \R^n$ relative to $A$.
	\begin{theorem}[\cite{LutLut18}]\label{thm:p2s}
		For every $E\subseteq \R^n$,
		\[\dimH(E)=\adjustlimits\min_{A\subseteq\N}\sup_{{x}\in E}\,\dim^A({x})\]
		and
		\[\dimP(E)=\adjustlimits\min_{A\subseteq\N}\sup_{{x}\in E}\,\Dim^A({x}).\]
	\end{theorem}
	In light of Theorem~\ref{thm:main}, this principle may be considered a member of the family of results, such as Billingsley's lemma~\cite{Bill61} and Frostman's lemma~\cite{Fros35}, that relate the local decay of measures to global properties of measure and dimension. Useful references on such results include~\cite{BisPer17,Hoch14,Matt95}.

	Among classical results, this principle is most directly comparable to
	the \emph{weak duality principle} of Cutler~\cite{Cutl94} (see also~\cite{Falc97}),
	which expresses Hausdorff and packing dimensions in terms of lower and upper pointwise dimensions of measures. For nonempty $E\subseteq\R^n$, let $\Delta(E)$ be the collection of Borel probability measures on $\R^n$ such that the $E$ is measurable and has measure 1, and let $\overline{E}$ be the closure of $E$.
	\begin{theorem}[\cite{Cutl94}] For every nonempty $E\subseteq\R^n$,
		\[\dimH(E)=\adjustlimits\inf_{\mu\in\Delta(\overline{E})}\sup_{{x}\in E}\,\dimloc\mu(x)\]
		and
		\[\dimP(E)=\adjustlimits\inf_{\mu\in\Delta(\overline{E})}\sup_{{x}\in E}\,\Dimloc\mu(x).\]
	\end{theorem}
	By letting $\mathcal{A}=\{\bkappa^A\mid A\subseteq\N\}$ and invoking Observation~\ref{obs:kappaloc}, Theorem~\ref{thm:p2s} can be restated even more similarly as
	\[\dimH(E)=\adjustlimits\inf_{\mu\in\mathcal{A}}\sup_{x\in E}\dimloc\mu(x)\]
	and
	\[\dimP(E)=\adjustlimits\inf_{\mu\in\mathcal{A}}\sup_{x\in E}\Dimloc\mu(x).\]
	Notice, however, that the collections over which the infima are taken in these two results, $\mathcal{A}$ and $\Delta(\overline{E})$, are disjoint and qualitatively very different. In particular, $\mathcal{A}$ does not depend on $E$. Whereas the global dimensions of the measures in $\Delta(\overline{E})$ are closely tied to the dimensions of $E$~\cite{Falc97},~\eqref{eq:globaldim} shows that the outer measures in $\mathcal{A}$ all have trivial global dimensions.

\section*{Acknowledgments}
	This research was supported in part by National Science Foundation Grants 1445755, 1545028, and 1900716. Some of this work was conducted while the second author was at Rutgers University, DIMACS, and the University of Pennsylvania.
\bibliography{oom}
\end{document}


TITLE: Standard conjectures on positive characteristic
QUESTION [3 upvotes]: In this MO answer of M. Bondarko, he says:

"the Hodge conjecture implies all the Grothendieck's standard conjectures over base fields of characteristic 0..."

and in Remarks on Grothendieck's standard conjectures A. Beilinson says:

"We show that Grothendieck’s standard conjectures (over a field of characteristic zero) follow from either of two other motivic conjectures, namely, that of existence of the motivic t-structure and (a weak version of) Suslin’s Lawson homology conjecture".

My question is: What about with standard conjectures in positive characteristic?

REPLY [7 votes]: Over finite fields, the Tate conjecture by itself doesn't imply the standard conjectures, but together with the Hodge conjecture for CM abelian varieties it does (Milne 2002, 2009).
In a little more detail: Milne showed that the Hodge conjecture for CM abelian varieties implies the Tate conjecture for all abelian varieties over the algebraically closure k of a finite field in a 1999 paper (Compositio), and that it implies the Hodge standard conjecture for AVs/k in a 2002 Annals paper. If you assume the Tate conjecture, then the category of motives over k is generated by abelian varieties (mentioned in Milne 1994, Seattle I). In terms of motives, the Hodge standard conjecture says that the pairings defined by ample line bundles are positive for a polarization on the Tannakian category of motives.


TITLE: Structure of the module of derivations on the space of Holomorphic functions
QUESTION [8 upvotes]: Maybe this is well-known, maybe not.
Let
$\Omega\subset \mathbb{C}$ be connected open and non-empty.
It can be shown that if
$d\in\mathfrak{Der}(\mathcal{H}(\Omega))$
(i.e. $d$ is a derivation of the algebra
$\mathcal{H}(\Omega)$) and is continuous
for the topology of compact convergence
then $d$ is of the form
$d=\varphi(z)\frac{d}{dz}$.
My questions are the following

 Can the continuity be withdrawn ?
 If yes, for which $\Omega$ ?
 Can $\Omega$ be replaced by a one
dimensional complex manifold ? (in
particular, for these manifolds, is
there a principal derivation
like $\frac{d}{dz}$ ?)

In particular the third question is trivial
in the case of a compact connected manifold
(because $\mathcal{H}(\Omega)=\mathbb{C}1_{\Omega}$
by maximum principle.).

REPLY [7 votes]: If you have a smooth manifold $M$, then you have a linear map $\mathfrak{X}(M) \to \text{Der}(C^{\infty}(M))$ from the space of smooth global vector fields to the space of derivations of the algebra of smooth global functions. It sends a vector field $X$ to the operator of differentiation of functions along $X$. It is a standard fact from the smooth manifold theory that this map is an isomorphism.
Now, let $M$ be a complex manifold. You still have a similar map $\mathfrak{X}^{hol}(M) \to \text{Der}(\mathcal{O}(M))$ from global holomorphic vector fields to derivations of the algebra of global holomorphic functions. As I understand, your question is about the surjectivity of this map. First of all, as you mentioned, if $M$ is compact, then there are no nonzero derivations of the algebra of holomorphic functions, but there maybe plenty nonzero holomorphic vector fields, so the map is surjective but not injective in this case. Now, we need the following fact:

If $M$ is Stein, then this map is an isomorphism.

Here is a proof of a similar result for real-analytic manifolds (real-analytic vector fields are exactly derivations of the algebra of real-analytic functions) by David Speyer. He uses the fact that every real-analytic manifold can be properly embedded into a Euclidean space, but the same is true for Stein manifolds (see the Wikipedia article on Stein manifolds; in fact Stein manifolds are exactly those complex manifolds that admit a proper holomorphic embedding into $\mathbb{C}^n$ for $n$ sufficiently large). After that, as far as I see, the proof goes without any changes.
Now, it is known that every non-compact connected Riemannian surface is Stein (see the same Wikipedia article for references). In particular, every domain in $\mathbb{C}$ is Stein. So the answers to your questions are:

Yes.
For any $\Omega$.
For any Riemannian surface $X$, every derivation of $\mathcal{O}(X)$ comes from some holomorphic vector field. It comes from a unique vector field if and only if $X$ has no compact components.

Remark. It is unknown to me if there are any examples of complex manifolds where our map is not surjective. If there is one (connected, WLOG), it must be of dimension greater than 1, non-Stein, and noncompact. Besides, I am interested if there are non-Stein complex manifolds with this map still bijective.
By the way, one can prove that every open subset of $\mathbb{C}$ is Stein without using the deep theorem that noncompact connected Riemannian surfaces are Stein. If you want, you may look for a proof in this wonderful survey into the Levi problem by Harry J. Slatyer.


TITLE: Corollary of Bolzano's theorem (i.e. IVT)
QUESTION [1 upvotes]: Let $f:(a,b)\to\mathbb{R}$ be a continuous function, such that $\lim_{x\to a^+}f(x)=-\infty$ and $\lim_{x\to b^-}f(x)=\infty$. Then there exists $c\in (a,b)$ such that $f(c)=0$.
Proof: Due to one-sided limits, there exists $\delta_1>0$ such that $f(x)<-1$ for all $x\in (a,a+\delta_1)$, and there exists $\delta_2>0$ such that $f(x)>1$ for all $x\in (b-\delta_2,b)$. Is there a way to choose $a'\in (a,a+\delta_1)$ and $b'\in (b-\delta_2,b)$ such that $a'<b'$? If I draw a line with these numbers, I expect it should look like
$-|--|-------|--------|------|-----|--$
$\;$ $a$$\hspace{0.8cm}$ $a'$ $\hspace{2cm}$ $a+\delta_1$$\hspace{2.5cm}$ $b-\delta_2$$\hspace{2cm}$$b'$$\hspace{2.2cm}$$b$
However, to make it happen, I need $\delta_1,\delta_2$ to satisfy $a+\delta_1<b-\delta_2$. I imagined, I should take an $\delta$ in terms of $\delta_1$ and $\delta_2$ (perhaps, the smallest of them?), so that we would get $a+\delta<b-\delta$, or that $a'<b'$, but do not know if it still would be true. Why do I care? So that I could conclude that $f$ is continuous in $[a',b']$ and $f(a')f(b')<0$, then the existence of root of $f$ will follow by Bolzano's theorem.

REPLY [0 votes]: $$\Delta \,:=\, \min\left(\delta_1,\,\delta_2,\,\frac{b-a}3\right).$$
Now pick any $a' \,\in\, (a,a+\Delta),$ and pick any $b' \,\in\, (b-\Delta,b)$.
Confirmation that $a'<b':$
$$a' \,<\, a+\Delta \,<\, a+\frac{b-a}{2} \,=\, b-\frac{b-a}{2} \,<\, b-\Delta \,<\, b'.$$
Checking that $\Delta < (b-a)/2,$ using that $b-a$ is greater than zero:
$$\Delta \,=\, \min\left(\delta_1,\,\delta_2,\,\frac{b-a}3\right)\,\leqslant\, \frac{1}3\cdot (b-a)\,<\, \frac{1}2\cdot (b-a).$$


text:
\section{Proofs of the Main Results} \label{sec:main_result}

Now, we are ready to put all results together to prove the main theorem. It states that a partial
representation $\calR'$ of $G$ is extendible if and only if $G$ and $\calR'$ contain none of the
obstructions described in Section~\ref{sec:definition_of_obstructions}.

\begin{proof}[Theorem~\ref{thm:repext_obstructions}]
If $G$ and $\calR'$ contain one of the obstructions, they are non-extendible by
Lemma~\ref{lem:correctness_all}. It remains to prove the converse. If $G$ is not an interval graph,
it contains an LB obstruction~\cite{lb_graphs}. Otherwise, $G$ is an interval graph and there exists
an MPQ-tree $T$ for it. By Lemma~\ref{lem:repext_char}, we know that a partial representation
$\calR'$ is extendible if and only if $T$ can be reordered according to $\wlt$. If it cannot be
reordered, then the reordering algorithm fails in some node of $T$. If this reordering fails in a
leaf, we get a $1$-BI obstruction by Lemma~\ref{lem:leaf}. If it fails in a P-node, we get an SE,
$1$-BI, or $1$-FAT obstruction by Lemma~\ref{lem:p_node}. And if it fails in a Q-node, we get one of
the obstructions of Section~\ref{sec:definition_of_obstructions} by
Lemmas~\ref{lem:q_node_three_cliques}, \ref{lem:q_node_two}, and \ref{lem:q_node_three}.\qed
\end{proof}

Next, we show that a partial representation $\calR'$ is extendible if and only if every quadruple of
pre-drawn intervals is extendible by itself.

\begin{proof}[Corollary~\ref{cor:helly_obstructions}]
The result follows from the fact that all the obstructions of Theorem~\ref{thm:repext_obstructions}
contain at most four pre-drawn intervals.\qed
\end{proof}

Concerning the certifying algorithm, we first show that $k$-FAT obstructions can be found in linear
time:

\begin{lemma} \label{lem:computing_k_fat}
Suppose that the assumptions of $k$-FAT Lemma~\ref{lem:k_fat} are satisfied. Then we can find a
$k$-FAT obstruction in time $\O(n+m)$.
\end{lemma}

\begin{proof}
Since the proof of $k$-FAT Lemma~\ref{lem:k_fat} is constructive, the algorithm follows it.  Let $Q$
be the Q-node.  We search the graph $G[Q] \setminus N[y_k]$ from $x_k$ to compute $C(x_k)$, and test
whether $z_k$ belongs to it. If it does, the algorithm stops and outputs $1$-FAT. Otherwise, we compute
$W_k$, choose $t_k$, and store it together with $P_k$.
We choose $x_{k-1}$ as in the the proof; if $s_i(Q) = s_{t_k}^\rt(Q)$, then either
$s_{x_{k-1}}^\lft(Q) = s_{i+1}(Q)$, or $x_{k-1}$ belongs to sections of $T_{i+1}$.
Then we apply the rest of the algorithm recursively.  It is important that then we can remove
$C(x_k)$ and $W_k$ from the graph because they are not used in the remainder of the obstruction.

Since the algorithm searches each vertex and edge of $G[Q] \setminus N[y_k]$ at most once when
computing $C(x_j)$, we obtain that the algorithm runs in time $\O(n+m)$.\qed
\end{proof}

Similarly, a $(k,\ell)$-CE obstruction can be obtained from $(k,\ell)$-CE Lemma~\ref{lem:kl_ce} in
time $\O(n+m)$.  Since obstructions are built constructively, we get a linear-time certifying
algorithm for the partial representation extension problem:

\begin{proof}[Corollary~\ref{cor:certifying_algorithm}]
We can assume that $G$ is an interval graph; otherwise we can find an LB obstruction in time
$\O(n+m)$ using~\cite{finding_lb_graphs}.  Each interval graph has $\O(n)$ maximal cliques of total
size $\O(n+m)$, and that they can be found in linear time~\cite{recog_chordal_graphs}.  We compute
the MPQ-tree $T$ in time $\O(n+m)$ using~\cite{korte_mohring}. Next, we use the partial
representation extension algorithm of~\cite{kkosv} in time $\O(n+m)$, which either finds an
extending representation, or finds an obstructed node which cannot be reordered according to $\wlt$.
We distinguish three cases according to the distinct types of obstructed nodes.

\emph{Case 1: A leaf cannot be reordered.}
We output a $1$-BI obstruction in time $\O(n)$, by searching the partial representation.

\emph{Case 2: A P-node $P$ cannot be reordered.}
From the partial representation extension algorithm, we get directly a two-cycle, ensured by
Lemma~\ref{lem:p_node_two_cycle}, and four maximal cliques $a$, $b$, $c$, and $d$ defining it. By
Lemma~\ref{lem:p_node_three_cliques}, one of these maximal cliques can be omitted, and
it can be clearly found in constant time. It remains to output an SE, $1$-BI, or $1$-FAT
obstruction in time $\O(n+m)$, by following Lemma~\ref{lem:p_node}. For $1$-BI and $1$-FAT
obstructions, we find a shortest path in $G[P] \setminus N[y_k]$ by searching the graph.

\emph{Case 3: A Q-node $Q$ cannot be reordered.}
From the partial representation extension algorithm, we get four maximal cliques defining the
obstruction and, by following Lemma~\ref{lem:q_node_three_cliques}, we can reduce it to at most three
maximal cliques. An SE obstruction can be computed in time $\O(n+m)$. If three maximal
cliques are contained in two subtrees, we follow Lemma~\ref{lem:q_node_two} and output one of the
obstructions in time $\O(n+m)$.

If three maximal cliques belong to three different subtrees, we follow the structure of the proof of
Lemma~\ref{lem:q_node_three}. In all cases, we derive some vertices somehow placed in the Q-node and
some pre-drawn intervals, which can be easily done in time $\O(n+m)$. Next, we either apply $k$-FAT
Lemma, or $(k,\ell)$-CE Lemma to construct the obstruction, which can be done in time $\O(n+m)$ by
Lemma~\ref{lem:computing_k_fat}.\qed
\end{proof}


TITLE: Is the classical world an illusion?
QUESTION [1 upvotes]: In the paper

Zeh, H. D. The Wave Function: It or Bit? In Science and Ultimate Reality, eds. J.D. Barrow, P.C.W. Davies, and C.L. Harper Jr. (Cambridge University Press, 2004), pp. 103-120.    arXiv:quant-ph/0204088

does Zeh state the classical world is an illusion or that our sense of locality in the classical world is an illusion? Is he correct?

REPLY [0 votes]: There's a misleading urban myth spreading around virulantly these days. It says decoherence shows how the classical world can emerge and solve the measurement problem.
Decoherence doesn't do anything of this sort! Note careful thinkers always use the word quasiclassicality instead of classical in this context. Interference may be exponentially suppressed after coarse graining, but the superposition still remains! Exponentially small off diagonal terms are still there, and there's still the problem of definite outcomes!
The classical world is an illusion! Quasiclassicality is the best we can do! We're all Wigner's friend!


TITLE: f(x,y) is continuous if the partial derivatives of f(x,y) exist and one of them is bounded below?
QUESTION [1 upvotes]: I had a test and I couldn't solve this problem:
f is continuous if the partial derivatives of f(x,y) exist and one of them is bounded below.
I know that if f is differentiable then f must be continuous. But this isn't a necessary condition. How do you do that?

REPLY [0 votes]: Suppose that $f$ is not continuous at the origin and $f(0,0)=0,f_{x}$ is bounded below.Then there is an $\varepsilon_{0}>0,P_{n}=(x_{n},y_{n})\rightarrow0$ as $n\rightarrow\infty$ so that $|f(P_{n})|\geq\varepsilon_{0}.$
If $\{P_{n}\}$ is in the first quadrant and suppose that $f(P_{n})\geq0$, according to the existence of $f_{x}$, we know that there is a $\delta_{1}>0$ so that when $x\in(0,\delta_{1}),|f(x,0)|<\frac{\varepsilon_{0}}{4}.$
Similarly, $\exists\delta_{2}>0$ so that when $y\in(0,\delta_{2}),|f(x,y)-f(x,0)|<\frac{\varepsilon_{0}}{4}$ where $x\in(0,\delta_{1}).$
Hence $$\begin{aligned}
|f(x,y)|&=|f(x,y)-f(x,0)+f(x,0)|\\
&\leq|f(x,y)-f(x,0)|+|f(x,0)|\\
&<\dfrac{\varepsilon_{0}}{2}.
\end{aligned}$$
Since $P_{n}=(x_{n},y_{n})\rightarrow0$ as $n\rightarrow\infty$,when $n$ large enough,there is $|P_{n}|<\min\{\delta,\delta_{2}\}.$ Thus we have $|f(x,y_{n})|<\frac{\varepsilon_{0}}{2}.$
Using the Lagrange mean value theorem,we know there exists $\xi_{n}$ between $x$ and $x_{n}$ so that $$f_{x}(\xi_{n},y_{n})=\dfrac{f(x,y_{n})-f(x_{n},y_{n})}{x-x_{n}}<-\dfrac{\varepsilon_{0}}{2x}.$$
Let $x\rightarrow0$ we can get $f_{x}(\xi_{n},y_{n})\rightarrow-\infty$ which is contradict to $f_{x}$ is bounded below.
When $\{P_{n}\}$ is in other quadrant we can discuss similarly to conclude the contradiction,and in general,we can just take a subsequence $\{P_{n_{k}}\}$ which in some quadrant into consideration.
Above all,$f$ is continuous.


TITLE: Which interaction is the responsible for long-range magnetism?
QUESTION [0 upvotes]: I am taking a course on solid state physics. The class is mostly based on Ashcroft-Mermin's "Solid State Physics". Yesterday I sat for an exam and there was a question I couldn't answer:
"Which interaction is the responsible for long-range magnetism?"
After the exam, we were discussing about it with the the rest of the classmates. Some said it was spin-spin interaction, but that doesn't make any sense to me, I don't even know what that would mean. Some others said it was wrong to say dipole-dipole... but no one was certain.

REPLY [1 votes]: Exchange interaction, which is a fancy way of saying spin-spin interaction. However, conditions have to be right (below Curie temperature) otherwise entropy washes the order out.
Two electrons have a total wavefunction $\psi(x_1,x_2, s_1, s_2)$ that is antisymmetric (changes sign) when we interchange $x_1,x_2$ and $s_1, s_2$ (Pauli exclusion principle). You can generalize to any number of identical fermions).
The Coulomb repulsion between two electrons is lower when they are in a spin-aligned state, because by the Pauli exclusion principle, they can't be in the same position, so their combined wavefunction $\psi(x_1,x_2)$ goes to zero when $x_1 \approx x_2$. In other words, they have less probability to be in a position where the electrical potential energy is highest. This state has lower energy. (Convince yourself that $\psi(x_1, x_2, \uparrow, \uparrow) = 0$ if $x_1 = x_2$)
Of course, if their spins are anti-aligned, then they can be close together, so that wavefunction has has a greater probability for them to be in a position where the electrical potential energy is highest. This state has higher energy.


TITLE: How to Solve a "Sum Inverse"
QUESTION [0 upvotes]: Before I start, I want to say that the kinds of problems like (solve for $x$: $1=\sum_{n=1}^x(\ln(n))$) is not what I'm talking about. I'm talking about if you have a certain function like $\ln(x)$ and want to find what sums to that function. In other words, it's the opposite of finding a partial sum (for $\ln(x)$, it's $\ln(\frac{x}{x-1})$.
If you just want the answer straightforward, here it is: the inverse sum of a certain function $f(x)$ is $f(x)-f(x-1)$.
EDIT: I removed the proof because it was too confusing. Please look at J.G.'s answer for the proof.

REPLY [1 votes]: Or if you want a shorter proof, if $\sum_{k=1}^n a_k=b_n$ then $a_n=\sum_{k=1}^n a_k-\sum_{k=1}^{n-1}a_k=b_n-b_{n-1}$.


TITLE: Ordinal exponentiation of limit ordinal
QUESTION [2 upvotes]: Prove that If $a$ is a limit ordinal and $p$ and $q$ are finite ordinals, then $(ap)^q$ = $a^q$$p^q$.
In my book, the right side of the equality is written as $a^qp$, but i think its typo since equality does not hold for the case $q=0$ and $p\ge1$.

REPLY [2 votes]: The book is correct, except in the case that $q=0$ and $p\neq 1$. One result you might want to prove is that for any limit ordinal $\lambda$ and any non-$0$ finite ordinal $p$, we have $p\cdot\lambda=\lambda$. From that, associativity of multiplication, and the fact that $0\cdot\alpha=0=\alpha\cdot 0$ for all $\alpha$, the book's equality follows readily by induction for non-$0$ finite $q$.


text:
\begin{document}
\maketitle
\begin{abstract}
We prove a uniqueness result for limit cycles of the second order ODE $\ddot x + \dot x \phi(x,\dot x) + g(x) = 0$. Under mild additional conditions, we show that such a limit cycle attracts every non-constant solution. As a special case, we prove limit cycle's uniqueness for an ODE studied in \cite{ETA} as a model of pedestrians' walk.
This paper is an extension to equations with a non-linear $g(x)$ of the results presented in \cite{S}.

{\bf Keywords}: Uniqueness, limit cycle, second order ODE's, star-shaped function, Conti-Filippov transformation.
\end{abstract}

\section{Introduction}

The simplest non-linear continuous dynamical systems originate from the study of planar differential systems,
\begin{equation}\label{sysPQ}
\dot x = P(x,y), \qquad \dot y = Q(x,y), \qquad P, Q \in C^1(\R^2,\R^2).
\end{equation}
Special cases of such systems are Lotka-Volterra ones, and systems equivalent to Li\'enard equations,
\begin{equation}\label{syslie}
\dot x = y - F(x)   , \qquad \dot y = - g(x),
\end{equation}
or to Rayleigh equations
\begin{equation}\label{sysray}
\dot x = y , \qquad \dot y = - g(x) - f(y).
\end{equation}
All of them arise as mathematical models of biological, physical, engineering systems \cite{LC}. The study of the dynamics of (\ref{sysPQ}) strongly depends on the existence and stability properties of special solutions such as equilibrium points and non-constant isolated periodic solutions. In particular, if an attracting non-constant periodic solution exists, then it dominates the dynamics of (\ref{sysPQ})  in an open, connected subset of the plane, its region of attraction. Studying the number and location of isolated periodic solutions, usually called limit cycles, is by no means a trivial question, as shown by the resistance of Hilbert XVI problem (see \cite{Sm}, problem 13). In some cases such a region of attraction can even extend to cover the whole plane, with the unique exception of an equilibrium point. In such a case the limit cycle is unique and dominates the system's dynamics, as in \cite{DO}.
Uniqueness theorems for limit cycles have been  extensively studied (see \cite{CRV}, \cite{XZ1}, \cite{XZ2},  for recent results and extensive bibliographies). Limit cycle's uniqueness is a relevant feature even in discrete time systems, which are often related to continuous time systems \cite{Sun}. Sometimes, suitable symmetry conditions have been used, in order to simplify the study of such systems. In particular $Z_2$ symmetry, that is orbital symmetry with respect to one axis, has proved to be useful in approaching similar problems \cite{YH}.   \\
\indent Most of the results obtained for continuous time dynamical systems in the plane are concerned with the classical Li\'enard system (\ref{syslie})  and its generalizations, such as
\begin{equation}\label{sysGG}
\dot x = \xi(x)\bigg[ \varphi(y) - F(x)  \bigg], \qquad \dot y = -\zeta(y)g(x).
\end{equation}
Such a class of systems also contain Lotka-Volterra systems and systems equivalent to Rayleigh equation (\ref{sysray}) as special cases.

Even if the systems (\ref{sysGG}) reach a high level of generality, compared to Van der Pol system,
 \\
\indent Even if the systems (\ref{sysGG}) reach a high level of generality, compared to Van der Pol system,
$$
\dot x = y - \epsilon \left(\frac{x^3}3-x \right)   , \qquad \dot y = - x .
$$
the first one to be  investigated  in relation to existence and uniqueness of limit cycles, an evident limitation is given by the fact that the variables $x$ and $y$ appear separately, so that mixed terms are products of single-variable functions. Since models displaying a different combination of variables do exist, different methods are desirable, in particular in absence of symmetry conditions.  \\
\indent  A recent result \cite{CRV} is concerned with systems equivalent to
\begin{equation}\label{equaCRV}
\ddot x +  \sum_{k=0}^{N}f_{2k+1}(x){\dot x}^{2k+1} + x = 0,
\end{equation}
with $f_{2k+1}(x)$ increasing  for $x > 0$, decreasing for $x < 0$, $k=0, \dots, N$.
On the other hand, there exist classes of second order models which are not covered by previous results. This is the case of a model developed in \cite{ETA} to describe the pedestrian's walk, which leads to the equation
\begin{equation}\label{ETA}
\ddot x + \epsilon \dot x (x^2 + x \dot x + {\dot x}^2 -1) + x = 0, \qquad \epsilon >0.
\end{equation}
Such an equation can be considered as a special case of a more general class of equations,
\begin{equation}\label{equaphi}
\ddot x + \dot x \phi(x,\dot x) + g(x) = 0.
\end{equation}
In this paper we study the class (\ref{equaphi}), assuming $ \phi(x,\dot x)$ to have strictly star-shaped level sets and $xg(x) > 0$ for $x \neq 0$. We prove a uniqueness result for limit cycles, and, under suitable additional assumptions, we show that a limit cycle exists and attracts every non-constant solution. Since $ \epsilon \dot x (x^2 + x \dot x + {\dot x}^2 -1)$ has strictly star-shaped level sets, the model introduced in \cite{ETA} has a unique limit cycle, attracting every non-constant solution. \\
\indent The result we present here is as well applicable to several equations of Li\'eanrd and Rayleigh type, in particular when they have a non-linear $g(x)$. \\
\indent This paper is organized as follows. In section 1 we study the equation (\ref{equaphi}), assuming $g(x)$ to be linear. We first prove the uniqueness theorem. The main tools applied here  is a uniqueness result proved in \cite{GS}. Then we introduce some mild additional hypotheses on the sign of $\phi(x,\dot x)$, under which the unique limit cycle attracts every non-constant solution. Then, in section 2, we assume $g(x)$ to be non-linear. We reduce the study of such a case to that of the linear $g(x)$, by  means of Conti-Filippov transformation \cite{SC}. The structure of section 2 is very similar to that of section 1, the main difference being the derivation of the condition on $ \phi(x,\dot x)$ which implies the strict star-shapedness property for the transformed system.

\section{Linear $g(x)$}

Let $\Omega \subset \R^2$ be a star-shaped set. We denote partial derivatives by subscripts, i. e. $\phi_x$ is the derivative of $\phi$ w. r. to $x$, etc..
We say that a function $\phi \in C^1( \Omega, \R) $ is  {\it star-shaped} if $(x,y) \cdot \nabla \phi = x \phi_x + y \phi_y$ does not change sign. We say that $\phi$ is
{\it strictly star-shaped} if  $(x,y) \cdot \nabla \phi \neq 0$, except at the origin $O=(0,0)$.  We say that $\gamma(t)$ is {\it positively bounded} if the semi-orbit $\gamma^+ = \{\gamma(t), \quad t \geq 0\}$ is contained in a bounded set. Similarly for the negative boundedness. We say that an orbit is an {\it open unbounded orbit} if it is both positively and negatively unbounded.    We say that a set $X$ is {\it invariant} if every orbit starting at a point of $X$ is entirely contained in $X$. For other definitions related to dynamical systems, we refere to \cite{BS} We call {\it ray} a half-line having origin at the point $(0,0)$.

In this section we are concerned with the equation
\begin{equation}\label{equaphix}
\ddot x + \dot x \phi(x,\dot x) + k x = 0, \qquad k \in \R, \qquad k > 0.
\end{equation}
Without loss of generality, possibly performing a time rescaling, we may restrict to the case $k=1$.
Let us consider a system equivalent to the equation (\ref{equaphix}), for $k=1$,
\begin{equation}\label{sysphi}
\dot x = y \qquad \dot y = -x - y \phi(x,y).
\end{equation}
We denote by $\gamma(t,x^*,y^*)$ the unique  solution of the system (\ref{sysphi}) such that $\gamma(0,x^*,y^*) = (x^*,y^*)$. We first consider a sufficient condition for limit cycles' uniqueness. We set
$$
A(x,y) = y \dot x - x \dot y = y^2 + x^ 2 +xy \phi(x,y).
$$
The sign of $A(x,y)$ is opposite to that of the angular speed of the solutions of (\ref{sysphi}).  Our uniqueness result comes from theorem 2 of \cite{GS}, in the form of corollary 6.

\begin{theorem}\label{teorema} Let $\phi\in( \R^2, \R^2)$ be a \sss function. Then (\ref{sysphi}) has at most one limit cycle.
\end{theorem}
{\it Proof.}
Without loss of generality, one may assume that, for $(x,y) \neq (0,0)$,
$x \phi_x + y  \phi_y > 0$.
The proof can be performed analogously for the opposite inequality.  \\
\indent We claim that $\nabla A(x,y)$ does not vanish on the set $A_0 = \{ (x,y) : A(x,y) =0  \} \setminus \{  (0,0) \}$. In fact,
$\nabla A$ and $A$ vanish simultaneously at $(x,y)$ if and only if
\begin{equation} \label{nabla}
\left\{
\begin{array}{cc}
2x + y\phi +xy \phi_x & = 0 \\
2y + x\phi + xy \phi_y & = 0 \\
x^ 2 + y^2 +xy \phi & = 0
\end{array} \right. .
\end{equation}
Multiplying the first equation by $y$, the second one by $x$ and re-ordering terms yields
$$
\left\{
\begin{array}{cc}
xy\phi & = - x^2 (2 + y\phi_x) \\
xy\phi & = - y^2 (2 + x\phi_y) \\
xy \phi & = - x^ 2 - y^2
\end{array} \right. .
$$
Multiplying the third equation by 2 and summing with  the first two equations yields
$$
xy ( x \phi_x + y \phi_y ) = 0.
$$
Since, by hypothesis,  $x \phi_x + y \phi_y \neq 0$ except at $O$, one has $xy = 0$. If $x=0$, then by the third equation in (\ref{nabla}) one has $y=0$.
Similarly, if  $y=0$.  \\
\indent This shows that, at every point, $A_0$ is locally a graph. Additionally, every ray $\{ (t\cos \theta, t\sin \theta), t > 0\}$, meets $A_0$ at most at a point. In fact, for $xy \neq 0$, one has,
$$
A(t\cos \theta, t\sin \theta) = 0 \iff   \phi(t\cos \theta, t\sin \theta) = \frac{1}{ \cos \theta\sin \theta}.
$$
The condition $x \phi_x + y  \phi_y > 0$ implies that $\phi$ is an increasing function of $t$ on every ray. Hence on every ray not contained in an axis there exists at most one $t$ such that $\phi(t\cos \theta, t\sin \theta) = \frac{1}{ \cos \theta\sin \theta}$.  As for $xy = 0$, $A$ vanishes only at $O$.

Moreover, working as above, one can show that $A_0$ has at a single point in common with the axes, $O$. \\
\indent  The radial derivative $A_r$ of $A$ is given by
\begin{equation} \label{radder}
A_r = \frac {x A_x + y A_y}r  = \frac 1r\bigg(2 A + xy (x \phi_x + y\phi_y) \bigg) .
\end{equation}
Let $(x^*,y^*)$ be a point of the first orthant, i. e.  $x^*>0, y^* > 0$. If $A(x^*,y^*) \geq 0$, then $A_r >0$ at $(x^*,y^*)$ and at every point $(rx^*,ry^*)$ with $r > 1$, hence $A$ is strictly increasing on the half-line $\{ (rx^*,ry^*) : r > 1\}$. Now, let $(x^*,y^*)$ be a point of the second orthant, i. e.   $x^*>0, y^* < 0$. If $A(x^*,y^*) <0$, then $A_r <0$ at $(x^*,y^*)$ and at every point $(rx^*,ry^*)$ with $r > 1$, hence $A$ is strictly decreasing on the half-line $\{ (rx^*,ry^*) : r > 1\}$. The same argument allows to prove that in the third orthant $A$ behaves as in the first one, and in the fourth orthant $A$ behaves as in the second one.  \\
\indent Assume, by absurd, two distinct limit cycles to exist. The system (\ref{sysphi}) has a unique critical point, hence they are concentric. Let $\mu_1$ be the inner one, $\mu_2$ be the external one. Let $D$ be the annular region bounded by $\mu_1$ and $\mu_2$. We claim that $A(x,y) > 0$ in $D$. We prove it by proving that, for every orbit $\gamma$ contained in $D$, $A(\gamma(t)) > 0$. Let us observe that every orbit in $D$ has to meet every semi-axis, otherwise its positive limit set would  contain a critical point different from $O$. On every semi-axis one has $A(x,y) > 0$.
Assume first, by absurd, $A(\gamma(t))$ to change sign. Then there exist $t_1 < t_2$ such that $A(\gamma(t_1)) > 0$, $A(\gamma(t_2)) < 0$, and and $\gamma(t_i)$, $i = 1,2$ are on the same ray. Assume $\gamma(t_i)$, $i = 1,2$ to be in the first orthant. Two cases can occur: either  $|\gamma(t_1)| < |\gamma(t_2)|$ or  $|\gamma(t_1)| > |\gamma(t_2)|$. The former, $|\gamma(t_1)| < |\gamma(t_2)|$, contradicts the fact that $A$ is radially increasing in the first orthant, hence one has $|\gamma(t_1)| > |\gamma(t_2)|$. The orbit $\gamma(t_1)$ crosses the segment $\Sigma = \{r \gamma(t_1), 0 < r <1\}$, going towards the positive $y$-semi-axis. Let $G$ be the region bounded by the positive $y$-semi-axis, the ray $\{r \gamma(t_1), r > 0\}$ and the portions of $\mu_1$, $\mu_2$ meeting the $y$-axis and such a ray.  The orbit $\gamma$ cannot remain in $G$, since in that case $G$ would contain a critical point different from $O$. Also, $\gamma$ cannot leave $G$ crossing the positive $y$-semi-axis, because $A(x,y) > 0$ on such an axis. Hence $\gamma$ leaves $G$ passing again through the segment $\Sigma$. That implies the existence of $t_3 > t_2$, such that $\gamma(t_3)$ lies on the ray  $\{ r \gamma(t_1), 0 < r \}$. Again, one cannot have $|\gamma(t_3)| < |\gamma(t_2)|$, since $A(\gamma(t_3)) > 0$ implies $A$ increasing on the half-line $r \gamma(t_3)), r > 1$, hence one has $|\gamma(t_3)| > |\gamma(t_2)|$. Also, one cannot have $|\gamma(t_3)| < |\gamma(t_1)|$, otherwise $\gamma$ would enter a positively invariant region, bounded by the curve $\gamma(t)$, for $t_1 \leq t \leq t_3$,  and by  the segment with extrema $\gamma(t_1)$, $\gamma(t_3)$, hence there would exist a critical point different from $O$. As a consequence, one has $|\gamma(t_3)| > |\gamma(t_1)|$.
Since $A(x,y) >0$ on the segment joining $\gamma(t_1)$ and $\gamma(t_3)$, such a segment, with the portion of orbit joining $\gamma(t_1)$ and $\gamma(t_3)$ bounds a region which is negatively invariant for (\ref{sysphi}), hence contains a critical point different from $O$, contradiction.  \\
  This argument may be adapted to treat also the case of a ray in the second orthant, replacing the positive $y$-semi-axis with the positive $x$-semi-axis, and reversing the relative positions of the points $\gamma(t_1)$, $\gamma(t_2)$, $\gamma(t_3)$. In the other orthants one repeats the arguments of the first and second orthants, respectively.  \\
\indent Finally, assume that $A(\gamma(t)) = 0$ at some point $(x^*,y^*)$. If $(x^*,y^*)$ is interior to $D$, then on the ray  $\{ (rx^*,ry^*), r >0 \}$, there exist points interior to $D$ with $A(rx^*,ry^*) < 0$. Then we can apply  the above argument to the orbits starting at such points. If $(x^*,y^*)$ belongs to the boundary of $D$, then it is on $\mu_1$ or on $\mu_2$. Assume $(x^*,y^*) = \mu_1(t^*)$, for some $t^*$ (the argument works similarly on $\mu_2$). Since $A(\mu_1(t^*)) = 0$, $\mu_1$ is tangent to the ray $\{ (rx^*,ry^*), r > 0 \}$. On the other hand, $\displaystyle A_r =  \frac {xy (x \phi_x + y\phi_y) } r
\neq 0$ at $(x^*,y^*) $, hence $A_0$ is neither tangent to the ray $\{ (rx^*,ry^*), r > 0\}$, nor to $\mu_1$ at $\mu_1(t^*)$. This implies that $A_0$ and $\mu_1$ are transversal at $(x^*,y^*)$, so that a portion of $A_0$ enters $D$. Since $A_0$ separates points where $A >0$ from points where $A < 0$, also in this case there exist points interior to $D$ with $A < 0$.  \\
\indent  Now we can restrict to the annular region $D$ and divide the vector field of (\ref{sysphi}) by $A(x,y)$, as in  corollary 6 in \cite{GS}. In order to appy such a corollary, one has to  compute the expression
$$
\nu = P\left( xQ_x + yQ_y \right) - Q \left( xP_x + yP_y\right) ,
$$
where $P$ and $Q$ are the components of the considered vector field. For system (\ref{sysphi}), one has
$$
\nu =
y \left(-x - xy \phi_x - y\phi - y ^2 \phi_y \right) - \left(  -x - y \phi \right) y  =
$$
$$
-y^2 \left( x \phi_x + y  \phi_y \right) \leq 0.
$$
The function $\nu$ vanishes only for $y=0$.   For both cycles one has:
$$
\int_{0}^{T_i} \nu(\mu_i(t) )dt < 0, \qquad i=1,2,
$$
where $T_i$ is the period of $\mu_i$, $i=1,2$. Hence both cycles, by theorem 1 in \cite{GS}, are attractive. Let $A_1$ be the region of attraction of $\mu_1$.  $A_1$ is bounded, because it is enclosed by $\mu_2$, which is not attracted to $\mu_1$. The external component of   $A_1$'s boundary is itself a cycle $\mu_3$, because (\ref{sysphi}) has just one critical point at $O$. Again,
$$
\int_0^{T_3} \nu(\mu_3(t) )dt < 0,
$$
hence $\mu_3$ is attractive, too. This contradicts the fact that the solutions of (\ref{sysphi}) starting from its inner side are attracted to $\mu_1$. Hence the system  (\ref{sysphi}) can have at most a single limit cycle.
\hfill $\clubsuit$

The angular velocity of the solutions need not be negative at every point of the plane. In fact, even a simple sysytem as that one studied in (\ref{ETA}) has negative angular velocity only in a proper subset of the plane. In Figure 1 we have plotted some orbits of the equation \ref{ETA}  tending at the limit cycle, together with the two components of the curve $A_0$. The orbits cross $A_0$ at the points where their angular velocity changes sign.

\begin{figure}[h!]
  \caption{$\ddot x + \dot x (x^2 + x \dot x + {\dot x}^2 -1) + x = 0$   }
  \centering
    \includegraphics[width=0.5\textwidth]{erlarg-A_0.pdf}
\end{figure}

In the example of Figure 1 we have chosen $\epsilon  = 1$. In general, the system studied in \cite{ETA} has just one limit cycle, for $\epsilon  > 0$. In fact, in this case one has
$$
\nu = x \phi_x + y  \phi_y = 2 \epsilon y^2 (x^2 + xy + y^2) > 0  \quad {\rm for } \quad  y \neq 0.
$$
It should be noted that even if the proof is essentially based on a stability argument, the divergence cannot be used in order to replace the function $\nu$. In fact, the divergence of system (\ref{sysphi}) is
$$
{\rm div } \bigg(y , -x - y \phi(x,y) \bigg)= - \phi -  y  \phi_y,
$$
which does not have constant sign, under our assumptions. Moreover, the divergence cannot have constant sign in presence of a repelling critical point and an attracting cycle.

\indent Now we care about the existence of limit cycles.  Let us denote by $D_r$ the disk $ \{ (x,y) : x^2 + y^2 \leq r^2 \} $, and by $\partial D_r$ its boundary $\{ (x,y) : x^2 + y^2 = r^2 \} $.  Let us consider the function $V(x,y) =   \frac 12 \left( x^2 + y^2 \right)$. Its derivative along the solutions of (\ref{sysphi}) is
$$
\dot V(x,y) = -y^2 \phi(x,y).
$$

\begin{lemma}\label{lemma} Let $U$ be a bounded set, with $\sigma := \sup \{  \sqrt{x^2 + y^2}, (x,y) \in U \}$.
If $\phi(x,y) \geq 0$ out of $U$, and $\phi(x,y)$ does not vanish identically on any $\partial D_r$, for $r > \sigma$, then every $\gamma(t)$ definitely enters the disk $D_\sigma$ and does not leave it.
\end{lemma}
{\it Proof.}
The level curves of $V(x,y)$ are circumferences. For every $r \geq \sigma$, the disk $D_r $ contains $U$.  Since $\dot V(x,y) = - y^2 \phi(x,y) \leq 0$ on its boundary, such a disk is positively invariant.
Let $\gamma$ be an orbit with a point $\gamma(t^*)$ such that $d^* = {\rm dist} (\gamma(t^*),O) > \sigma$. Then $\gamma$ does not leave the disk $D_{d^*}$, hence it is positively bounded.
Moreover $\gamma(t)$ cannot be definitely contained in $\partial D_r$, for any $r > \sigma$, since $\dot V(x,y)$ does not vanish identically on any $\partial D_r$, for $r > \sigma$. Now, assume by absurd that $\gamma(t)$ does not intersect  $B_\sigma$. Then its positive limit set is a cycle $\overline{\gamma}(t)$, having no points in $D_\sigma$. The cycle $\overline{\gamma}(t)$ cannot cross outwards any $\partial D_r$, hence it has to be contained in $\partial D_r$, for some $r > \sigma$, contradicting the fact that $\dot V(x,y)$ does not vanish identically on any $\partial D_r$, for $r > \sigma$. Hence there exists  $t^+ > t^*$ such that $\gamma(t^+) \in D_\sigma$. Then, for every  $t > t^+$, one has $\gamma(t) \in D_\sigma$, because $\dot V(x,y) \leq 0$ on $B_\sigma$.
\hfill$\clubsuit$

Collecting the results of the above statements, we may state a theorem of existence and uniqueness for limit cycles of a class of second order equations. We say that an equilibrium point $O$ is {\it negatively asymptotically stable} if it is asymptotically stable for the system obtained by reversing the time direction.

\begin{theorem}\label{teorema2} If the hypotheses of theorem \ref{teorema} and lemma \ref{lemma} hold, and $\phi(0,0) < 0$, then the system (\ref{sysphi}) has exactly one limit cycle, which attracts every non-constant solution.
\end{theorem}
{\it Proof.} By the above lemma, all the solutions are definitely contained in $D_\sigma$. The condition $\phi(0,0) < 0$  implies by continuity $\phi(x,y) < 0$ in a neighbourhood $N_O$ of $O$. This gives  the negative asymptotic stability of $O$ by Lasalle's invariance principle \cite{V}, since $\dot V(x,y) \geq 0$ in $N_O$, and the set $\{\dot V(x,y) = 0\} \cap N_O = \{y = 0\}   \cap N_O$ does not contain any positive semi-orbit. The system has just one critical point at $O$, hence by Poincar\'e-Bendixson theorem there exist a limit cycle. By  theorem \ref{teorema}, such a limit cycle is unique.
\hfill$\clubsuit$

This proves that every non-constant solution to the equation (\ref{ETA}) studied in  \cite{ETA} is attracted to the unique limit cycle.

We can produce more complex systems with such a property. Let us set
$$
\phi(x,y) = -M +\sum_{k=1}^n H_{2k}(x,y),
$$
with $ H_{2k}(x,y)$ is a homogeneous function of degree $2k$, positive except at $O$, $M$ is a positive constant. Then, by Euler's identity,  one has
$$
\nu = \sum_{k=1}^n \left( x\hkx + y\hky \right) = \sum_{k=0}^n 2kH_{2k}(x,y) > 0  \quad {\rm for } \quad  (x,y) \neq (0,0).
$$
If $\phi(x,y)$ does not vanish identically on any $\partial D_r$, for instance if $H_{2k}(x,y) = (x^2 +xy + y^2)^k$, then the corresponding system (\ref{sysphi}) has a unique limit cycle.
In general, it is not necessary to assume the positiveness of all of the homogeneous functions $H_{2k}(x,y)$, as the following example shows. Let us set $Q(x,y) = x^2+xy+y^2$. Then take
$$
\phi(x,y) =  -1 + Q  - Q^2 + Q^3 .
$$
One has
$$
\nu = x \phi_x + y  \phi_y = 2Q - 4Q^2 +6Q^3 = Q(2  - 4Q  +6Q^2)  .
$$
The discriminant of the quadratic polynomial $2  - 4Q  +6Q^2$ is $ -32 < 0$ hence $\nu >0$ everywhere but at $O$. Moreover, $\phi(x,y)$ does not vanish identically on any circumference, hence  the corresponding system (\ref{sysphi}) has a unique limit cycle.

\section{Non-linear $g(x)$ }

Even if the equation we consider in this section are of a more general type, we actually derive our result from that of the previous section, so that we can consider what follows a corollary of the previous result. Let us consider the equation
\begin{equation}\label{equaphig}
\ddot x + \dot x \Phi(x,\dot x) + g(x) = 0 .
\end{equation}
We assume that  $ xg(x) > 0 {\rm\ for \ } x \neq 0$, $g \in C^1(\R,\R)$, $g'(0) \neq 0$,
We could consider equations defined in smaller subset of the plane, without essential changes. The main tools is the so-called Conti-Filippov transformation, which acts on the equivalent system
\begin{equation}\label{sysphig}
\dot x = y, \qquad  \dot y = - g(x) - y \Phi(x,y),
\end{equation}
in such a way to take the conservative part of the vector field into a linear one. Let us set $G(x) = \int_0^x g(s) ds$, and denote by $\sigma(x)$ the sign function, whose value is $-1$ for $x < 0$, $0$ at $0$, $1$ for $x > 0$.  Let us define the function $\alpha : \R \rightarrow \R$ as follows:
$$
 \alpha(x) =  \sigma(x) \sqrt{2G(x)}.
$$
Then Conti-Filippov transformation is the following one,
\begin{equation}\label{transf}
(u,v) = \Lambda(x,y) = (\alpha(x),y).
 \end{equation}
Since we assume that $g \in C^1(\R,\R)$, one has $\alpha  \in C^1(\R,\R)$ . The function $u = \alpha (x)$ is invertible, due to the condition $xg(x) > 0$. Let us call $x =\beta(u)$ its inverse. The condition $g'(0) > 0$ guarantees the differentiability of $\beta(u)$ at $O$. For $x \neq 0$, that is for $u \neq 0$, one has,
\begin{equation}\label{derivate}
\alpha'(x) =  \frac{\sigma(x) g(x)}{\sqrt{2G(x)}}, \qquad \beta'(u) =  \frac{1}{\alpha'(\beta(u))} =  \frac{\sigma(x)\sqrt{2G(x)}}{g(x)} = 	\frac{u}{g(\beta(u))}.
 \end{equation}
 For $x=u=0$ one has,
 $$
 \alpha'(0) = \sqrt{g'(0)}, \qquad  \beta'(0) =  \sqrt{\frac{1}{g'(0)}} .
 $$
Finally,
$$
\lim_{u \rightarrow 0} \frac{g(\beta(u))}{u} =  \sqrt{g'(0)} > 0.
$$
\begin{theorem}\label{teorema-n} Assume $g \in C^1(\R,\R)$, with $g'(x) > 0$ and $xg(x) > 0$ for $x\neq 0$. Let $\Phi \in C^1(\R^2, \R^2) $ satisfy
$$
 \frac {\sigma(x) \sqrt{2G(x)} }{g(x)} \left[ 2G(x) \frac{ \Phi_x(x,y)g(x) - \Phi(x,y)g'(x) }{g(x)^2} +  \Phi(x,y)  \right]
+ y \Phi_y(x,y) \neq 0.
$$
Then (\ref{sysphig}) has at most one limit cycle.
\end{theorem}
{\it Proof.}
For $u \neq 0$, the transformed system has the form
\begin{equation}\label{sysu}
\dot u = v \frac{g(\beta(u))}{u}, \qquad \dot v = - g(\beta(u)) - v \Phi(\beta(u),v).
\end{equation}
For $u = 0$, the above form is extended by continuity. In the following we consider only the case $u\neq 0 $, that is $x \neq 0$, since the case $u = 0 = x$ is obtained by continuity. We may multiply the system (\ref{sysu}) by $ \frac{u}{g(\beta(u))}$, obtaining a new system having the same orbits as (\ref{sysu}),
 \begin{equation}\label{sysurep}
\dot u = v, \qquad \dot v = - u - v  \frac{u\Phi(\beta(u),v)}{g(\beta(u))}.
\end{equation}
Such a system is of the type (\ref{sysphi}), so that we may apply theorem \ref{teorema} to get uniqueness of solutions. This reduces to require the strict star-shapedness of the function
$$
 \frac{u\Phi(\beta(u),v)}{g(\beta(u))},
$$
that is,
$$
u\left[  \frac{u\Phi(\beta(u),v)}{g(\beta(u))}  \right]_u+ v \Phi_v(\beta(u),v) > 0.
$$
Since $\beta(u) = x$, $v = y$, the second term in the above sum is just $y \Phi_y(x,y)$. As for the the first one, one has
$$
\left[  \frac{u\Phi(\beta(u),v)}{g(\beta(u))} \right]_u = $$ $$
 \frac{\bigg( u\Phi_u(\beta(u),v)\beta'(u) +  \Phi(\beta(u),v) \bigg)g(\beta(u)) - u\Phi(\beta(u),v)g'(\beta(u)) \beta'(u)}{g(\beta(u))^2}.
$$
Replacing $\beta(u)$ with $x$ and applying the formulae (\ref{derivate}) one has
$$
\left[  \frac{u\Phi(\beta(u),v)}{g(\beta(u))} \right]_u = $$ $$
 \frac{\sigma(x)\sqrt{2G(x)}}{g(x)}.
 \frac{\bigg( \sigma(x) \sqrt{2G(x)}\Phi_x(x,y) \bigg)g(x) - \sigma(x) \sqrt{2G(x)}\Phi(x,y)g'(x) }{g(x)^2} +
 \frac{\Phi(x,y) }{g(x)}.
$$
Since $\sigma(x)^2 = 1$ eveywhere but at $0$, the above formula reduces to
$$
\left[  \frac{u\Phi(\beta(u),v)}{g(\beta(u))} \right]_u =
 \frac{2G(x)}{g(x)}   \frac{ \Phi_x(x,y)g(x) - \Phi(x,y)g'(x) }{g(x)^2} +   \frac{\Phi(x,y) }{g(x)} .
$$
Concluding, one has
$$
u\left[  \frac{u\Phi(\beta(u),v)}{g(\beta(u))}  \right]_u =
 \frac {\sigma(x) \sqrt{2G(x)} }{g(x)} \left[ 2G(x) \frac{ \Phi_x(x,y)g(x) - \Phi(x,y)g'(x) }{g(x)^2} +  \Phi(x,y)  \right].
$$
Hence, the star-shapedness conditions reduces to
$$
 \frac {\sigma(x) \sqrt{2G(x)} }{g(x)} \left[ 2G(x) \frac{ \Phi_x(x,y)g(x) - \Phi(x,y)g'(x) }{g(x)^2} +  \Phi(x,y)  \right]
+ y \Phi_y(x,y) \neq 0.
$$
\hfill$\clubsuit$

If $g(x) = x$, then $\displaystyle{ G(x) =  \frac{x^2}{2} }$ and $\displaystyle{  \frac {\sigma(x) \sqrt{2G(x)} }{g(x)} = 1 }$, for $x \neq 0$. In this case the star-shapedness condition just reduces to what considered in the previous section, since
$$
 2G(x)  \frac{ \Phi_x(x,y)g(x) - \Phi(x,y)g'(x) }{g(x)^2} +  \Phi(x,y)  =   x \Phi_x(x,y) .
$$

Now we prove the non-linear analogous of lemma \ref{lemma}. Let us set
$$
E(x,y) = G(x) + \frac {y^2}{2}
$$
For $r > 0$, we set $\Delta_r = \{ (x,y) : 2 E(x,y) < r^2 \}$ and $\partial \Delta_r = \{ (x,y) : 2 E(x,y)  = r^2 \}$

\begin{lemma}\label{lemma-n} Let $U$ be a bounded set, with $\sigma := \sup \{   \sqrt{ 2 E(x,y) }, (x,y) \in U \}$.
If $\Phi(x,y) \geq 0$ out of $U$, and $\Phi(x,y)$ does not vanish identically on any $\partial \Delta_r$, for $r > \sigma$, then every $\gamma(t)$ definitely enters the set $\Delta_\sigma$ and does not leave it.
\end{lemma}
{\it Proof.} Performing Conti-Filippov transformation, the sets $ \Delta_r$ are taken into the sets $D_r$, as well as the boundaries $\partial \Delta_r$ are taken into the boundaries $\partial D_r$. The function $\Phi(x,y)$ does not vanish identically on any $\partial \Delta_r$ if and only if the function $\phi(u,v) = \Phi(\beta(u),v)$ does not vanish identically on any $\partial D_r$.
Then one can apply lemma  \ref{lemma} to the system (\ref{sysurep}). In fact, the derivative of the Liapunov function $V(u,v) = \frac 12 (u^2+v^2)$ along the solutions of  (\ref{sysurep}) is just
$$
\dot V (u,v) =  - v^2  \frac{u\Phi(\beta(u),v)} {g(\beta(u))} .
$$
The function $ \frac{u} {g(\beta(u))}$ is positive for $u \neq 0$, hence the hypotheses of lemma \ref{lemma} are satisfied by the system (\ref{sysurep}). As a consequence, the conclusions of lemma  \ref{lemma} hold for the system (\ref{sysurep}), and applyng the inverse transformation $\Lambda^{-1}$ one obtains the thesis.
\hfill$\clubsuit$

Now we can conclude proving the analogue of theorem \ref{teorema2} for the equation with a non-linear  $g(x)$.

\begin{theorem}\label{teorema2-n}  If the hypotheses of theorem \ref{teorema-n} and lemma \ref{lemma-n} hold, and $\phi(0,0) < 0$, then the system (\ref{sysphig}) has exactly one limit cycle, which attracts every non-constant solution.
\end{theorem}
{\it Proof.} As the proof of theorem \ref{teorema2}, replacing the Liapunov function $V(x,y)$ with the Liapunov function $E(x,y)$.
\hfill$\clubsuit$

\bigskip

{\bf  \large Acknowledgements}

The author would like to thank dr. S. Erlicher for raising the problem, and proff. T. Carletti and G. Villari for reading a previous version of this paper.

This paper has been partially supported by the GNAMPA 2009 project \lq\lq Studio delle traiettorie di equazioni differenziali ordinarie\rq\rq.


TITLE: Where am I going wrong in evaluating this limit?
QUESTION [1 upvotes]: $$\lim_{x \to y} \frac{\sin^2x-\sin^2y}{x^2-y^2}.$$ This is an indeterminate form, and $\sin^2y$ and $y^2$ are simply constants. Applying L'hospital's rule gives $\sin y/y$ which is incorrect. Where did I go wrong?

REPLY [1 votes]: Using Prove $ \sin(A+B)\sin(A-B)=\sin^2A-\sin^2B $,
$$\lim_{x\to y}\dfrac{\sin^2x-\sin^2y}{x^2-y^2}=\lim_{x\to y}\dfrac{\sin(x-y)}{x-y}\cdot\lim_{x\to y}\dfrac{\sin(x+y)}{x+y}$$


TITLE: How many different even 4-digit numbers can be created if digits 0-6 can be used and the first digit is nonzero. Repetition is not allowed.
QUESTION [0 upvotes]: I know that the first digit will be between 1-6 because 0 cannot be chosen but I do not know how to proceed further. How do you solve this?

REPLY [1 votes]: Case 1: The first digit is even (2, 4, or 6)
In this case, the last digit must be some other even digit, while the middle two digits must be different from each other and from the first and last digits. This gives $3 \cdot 5 \cdot 4 \cdot 3=180$ 4-digit even numbers with distinct digits less than 7 where the first digit is even.
Case 2: The first digit is odd (1, 3, or 5)
In this case, the last digit can be any even digit, while the middle two digits must still be different from each other and from the first and last digits. This gives $3 \cdot 5 \cdot 4 \cdot 4=240$ 4-digit even numbers with distinct digits less than 7 where the first digit is odd.
Adding both cases together, the total number of 4-digit even numbers with distinct digits less than 7 is $180+240=420$.


TITLE: Can matter have 100% reflection?
QUESTION [4 upvotes]: Is it possible to have matter that reflects all the light and does not absorb light at all? If thats possible then we can store light inside it right? I think we can trap light inside that matter in shape of box for example and also we can release it by making very small dot in that box.
Im not saying that this is useful or not (I think its useless though because we can already emit light in other ways). Im just curios about this. Im noob in physics so sorry for my noob question. Thanks in advance.
Edit: If it does not make sense for matter to have reflection then what about shapes to reflect all light?

REPLY [5 votes]: Source http://www.researchgate.net/post/Can_the_100_reflection_be_achieved
1) The highest reflectivity conventional mirrors made for reflecting a laser beam have a reflectivity of about 99.999%. These mirrors are made for the advanced LIGO experiment which is an attempt to detect gravitational waves using a power recycled Michelson interferometer. The loss of these dielectric mirrors is primarily because of transmission loss. Absorption is less than 1 part per million. 2) Superconductors are not superconductive above a cut off frequency which is typically in the radio frequency range. However, even if the bulk material exhibits superconductive properties at the frequency being reflected, the superconductive mirrors would still exhibit some loss because of surface defects such as surface contamination, roughness and imperfect super conductive properties of the surface. 3) Total internal reflection (TIR) is virtually 100% reflection, but this answer is probably unsatisfactory. TIR requires an incidence angle less than a critical angle which for air/glass interface is about 42 degrees. Fiber optics utilize TIR and fiber optics can transmit laser beams over many kilometers with low loss. The loss that exists is primarily due to absorption and scatter in the bulk material, not reflection loss.
Therefore, there are no conventional mirrors which produce 100% reflection.


TITLE: how to obtain this differential EQ?
QUESTION [0 upvotes]: Consider the initial value problem
$$
\frac{dy}{dt}  = \frac{ty (4-y)}{3}, \quad y(0) = y_0.
$$
Determine how the behavior of the solution as $t$ increases depends on the initial value $y_0$.

I use this eq is separable, so
$$
\begin{split}
\left(\frac1y - \frac1{4-y}\right)dy &= \frac43 t dt \\
\ln |y| - \ln |4-y| &= \frac23 t^2 +c
\end{split}
$$
and since $y(0)=y_0$, we have $c=\ln\left|\frac{y_0}{4-y_0}\right|$.
Book solution said $y_0=0 \implies y=0$, why is it?
$y_0=0 \implies c=0$, so as $t \to \infty$, $\ln\left| \frac{y}{4-y}\right| \to \infty$, so $y \to 4$ isn't it?
but book said $y_0>0 \implies y \to 4, y_0<0 \implies y\to -\infty$, i don't understand this sol, how to prove this questions and how to obtain this dif-EQ?

REPLY [1 votes]: $${dy\over dt}={ty(4-y)\over3} \implies \ln\left({y\over 4-y}\right)={2\over3}t^2+C$$
Which yields;
$$ {y\over4-y}=Ae^{{2\over3}t^2} \implies y(t)={4Ae^{{2\over3}t^2}\over(1+Ae^{{2\over3}t^2})}$$
Using the initial condition, $y(0)=y_0$, Allows us to solve for A;
$$y(0)={4A\over1+A}=y_0 \implies A={y_0\over4-y_0}$$
So our final solution is;
$$y(t)={4y_0e^{{2\over3}t^2}\over\left(4-y_0(1-e^{{2\over3}t^2})\right)}$$
So, if $y_0=0$ then we do, indeed, have $y(t)=0$, as required.


TITLE: What happens when you put (pour) water on water with the same density? (Archimedes)
QUESTION [1 upvotes]: Suppose you have a glass of water, and you pour on it a volume V of water of the same density; if we consider the archimedes principle, what happens to the water that is poured? Does it float, sink, not move?

REPLY [1 votes]: Archimedes law expresses relates the difference between actual weight (ideally weight in vacuum) to apparent immersed weight (weight in the medium) to density. This is through the following formulations:
Apparent immersed weight = Weight of object - weight of displaced fluid ...(1)
Weight of object/ weight of displayed fluid = Density of object/ density of fluid ...(2)
Since the object here is water with the same density, the above equations show that there is no apparent immersed weight. This means that the buoyant force (on the added water) is exactly equal to the weight of the (added) water, thus the added water will remain suspended wherever you add it.
Now, where you add it is a bit complex since it necessarily involves fluid dynamics, not just statics. Some water will sink due to momentum, as mentioned in the previous answer. Some will splash. Depending on the height of the splash, it could sink or remain at the surface. Once all these dynamic situations cease, each drop/unit of water will remain where it is.


TITLE: Catching fish in a pond
QUESTION [2 upvotes]: Suppose the amount of fish in a pond follows a Poisson distribution. A fisherman catches each fish (independently) with probability $\frac{1}{2}$. If $N$ is the  total number of fish he catches, what is $\mathbb{P}(N=n)?$ Suppose now that he  has caught $N=M$ fish, what is $\mathbb{P}(K=k)$ where $K$ is the number of fish  he has not caught?

Say there are $x$ fish in the pond. $\mathbb{P}(N=n)=\frac{1}{2^n}$
$$\mathbb{P}(K=k\,|\,N=M)=\frac{\mathbb{P}(K=k\cap N=M)}{\mathbb{P}(N=M)}=\frac{\mathbb{P}( N=x-k)}{\mathbb{P}(N=M)}=\left(\frac{1}{2}\right)^{x-k-M}$$
This must be wrong because I haven't taken into account the Poisson distribution. How can I incorporate $\mathbb{P}(X=x)=\lambda^x\frac{1}{x!}e^{-\lambda}$ into this ($X$ is the number of fish in the pond)? Help would be appreciated.

REPLY [2 votes]: See this answer. Have fun with this...


TITLE: Can't create equations to solve linear algebra problem
QUESTION [0 upvotes]: Problem
Suppose that vectors $x_1, x_2, \dots, x_n$ have the following property: for each $i$ the sum of all vectors except $x_i$ is parallel to $x_i$. If at least two of the vectors $x_1, x_2, \dots, x_n$ are not parallel, what is the value of the sum $x_1 + x_2 + \dots + x_n=?$
Attempted solution
I tried to start from the simplest case: 2 vectors: $x_1, x_2$. The condition: for each $i$ the sum of all vectors except $x_i$ is parallel to $x_i$ means, that $x_1 \parallel x_2$. But it contradicts to condition: "at least two of the vectors are $\not\parallel$". So, for 2 vectors such set doesn't exist.
For 3 vectors we get the following:
$$
\begin{pmatrix}
x_1 = a_1 \cdot (x_2 + x_3)\\
x_2 = a_2 \cdot (x_1 + x_3)\\
x_3 = a_3 \cdot (x_1 + x_2)\\
\end{pmatrix}
$$
After we add up all these equations, we get:
$x_1 + x_2 + x_3 = a_1 \cdot (x_2 + x_3) + a_2 \cdot (x_1 + x_3) + a_3 \cdot (x_1 + x_2)$
Difficulty
I have no idea, what to do next. And how to use the condition: "at least two of the vectors are not parallel". This condition means, they are linearly independent: $a_1 \cdot x_1 + a_2 \cdot x_2 = 0 \leftrightarrow a_1 = 0\; \& \;a_2 = 0$. But I don't have any equations with zero here. And I don't understand, how to use it.

REPLY [3 votes]: HINT: A vector is parallel to $x_i$ if and only if it’s a multiple of $x_i$. For each $i$ let $y_i$ be the sum of the vectors other than $x_i$. Then for all $i$ we have
$$x_1+\ldots+x_n=x_i+y_i=\alpha_i x_i$$
for some scalar $\alpha_i$. Now suppose that $x_i$ and $x_j$ are not parallel. What can you infer from $\alpha_ix_i=\alpha_jx_j$?