text:
\newcommand{\PolicyRegret}{\mathrm{PolicyRegret}}
\newcommand{\ControlReg}{\mathrm{ControlReg}}

\newcommand{\calO}{\mathcal{O}}
\newcommand{\ocom}{\textsc{OcoM}}
\newcommand{\convoco}{\textsf{ConvOCO}}
\newcommand{\convreg}{\mathrm{ConvReg}}
\newcommand{\drcons}{\textsc{Drc-Ons}}
\newcommand{\drcgd}{\textsc{Drc-Gd}}
\nipsminpt
\nipsminpt
\nipsminpt
\section{Introduction}
\nipsminpt
\nipsminpt
\nipsminpt
In control tasks, a learning agent seeks to minimize cumulative loss in a dynamic environment which responds to its actions. While dynamics make control problems immensely expressive, they also pose a significant challenge: the learner's past decisions affect future losses incurred.

This paper focuses on the widely-studied setting of linear control, where the the learner's environment is described by a continuous state, and evolves according to a linear system of equations, perturbed by \emph{process noise}, and guided by inputs chosen by the learner. Many of the first learning-theoretic results for linear control focused on \emph{online LQR} \citep{abbasi2011regret,dean2018regret,cohen2019learning,mania2019certainty}, an online variant of the classical \emph{Linear Quadratic Regulator (LQR)} \citep{kalman1960new}. In online LQR, the agent aims to control an unknown linear dynamical system driven by independent, identically distributed Gaussian process noise.  Performance is measured by regret against the optimal LQR control law on a time horizon $T$, for which the optimal regret rate is $\widetilde{\Theta}(\sqrt{T})$ \citep{cohen2019learning,mania2019certainty,simchowitz2020naive,cassel2020logarithmic}.

\nipstogfalse{

}
Theoretical guarantees for LQR rely heavily on the strong stochastic modeling assumptions for the noise, and may be far-from-optimal if these assumptions break. A complementary line of work considers \emph{non-stochastic control},   replacing stochastic process noise with adversarial disturbances to the dynamics \citep{agarwal2019online,simchowitz2020improper}. Here, performance is measured by \emph{regret}: performance relative to the best (dynamic) linear control policy in hindsight, given full knowledge of the adversarial perturbations.

Though many works have proposed efficient algorithms which attain sublinear regret for non-stochastic control, they either lag behind optimal guarantees for the stochastic LQR problem, or require partial stochasticity assumptions to ensure their regret. And while there is a host of literature demonstrating that, in many online learning problems without dynamics, the worst-case rates of regret for the adversarial and stochastic settings are the same ~\citep{auer2002nonstochastic,zinkevich2003online,hazan2007logarithmic}, whether this is true in control is far from clear. Past decisions affect future losses in control settings, and this may be fundamentally more challenging when perturbations are adversarial and unpredictable.
\nipstogfalse{

}
Despite this challenge, we propose an efficient algorithm that matches the optimal $\sqrt{T}$ regret bound attainable  the stochastic LQR problem, but under arbitrary, non-stochastic disturbance sequences and arbitrary strongly convex costs. Thus, from the perspective of regret with respect to a benchmark of linear controllers, we show that the optimal rate for non-stochastic control matches the stochastic setting.

\paragraph{Our Setting}Generalizing LQR, we consider partially-observed linear dynamics :
\begin{align}
\matx_{t+1} = \Ast \matx_t + \Bst \matu_t + \matw_t, \quad
 \maty_t = \Cst \matx_t + \mate_t \label{eq:LDS_system}
\end{align}
Here, the state $\matx_t$ and process noise $\matw_t$ lie in $\R^{\dimx}$, the observation $\maty_t$ and observation noise $\mate_t$ lie in $\R^{\dimy}$, and the input $\matu_t \in \R^{\dimu}$ is elected by the learner, and  $\Ast,\Bst,\Cst$ are matrices of appropriate dimensions. We call the $(\matw_t,\mate_t)$ the \emph{disturbances}, and let $(\matw,\mate)$ denote the entire disturbance sequence.  Unlike LQR, we assume that the disturbances are selected by an oblivious\footnote{The oblivious assumption is only necessary if the dynamics are unknown to the learner; if the dynamics are known, our guarantees hold against adaptive adversaries as well.} adversary, rather than from a mean zero stochastic process, and the learner observes the outputs $\maty_t$, but not the full state $\matx_t$.  \Cref{ssec:app_classical} describes how our setting strictly generalizes the online LQR problem, and relates to its partially observed analogoue LQG.
\nipstogfalse{

}
A \emph{policy} $\pi$ is a (possibly randomized) sequence of mappings $\matu_t := \pi_t(\maty_{1:t},\matu_{1:t-1})$. We denote by $\maty_t^{\pi}$ and $\matu_t^\pi$ sequence the realized sequence of outputs and inputs produced by policy $\pi$ and the noise sequence $(\matw,\mate)$. At each time $t$,  a convex cost $\cost_t : \R^{\dimy \times \dimu} \to \R$ is revealed, and the learner observes the current $\maty_t$, and  suffers loss $\cost_t(\maty_t,\matu_t)$. The \emph{cost functional} of a policy $\pi$ is

\begin{align*}
	J_T(\pi) := \nipstogtrue{\textstyle}\sum_{t=1}^T \cost_t(\maty^{\pi}_t,\maty^{\pi}_t),
\end{align*}
measuring the cumulative losses evaluated on the outputs and inputs induced by the realization of the disturbances $(\matw,\mate)$. The learner's policy $\Alg$, is chosen to attain low \emph{control regret} with respect to a pre-specified benchmark class $\Pi$ of reference policies,
\begin{align}
\ControlReg_T(\Alg;\Pi) := J_T(\Alg) - \inf_{\pi \in \Pi} J_T(\pi), \label{eq:reg_def}
\end{align}
which measures the performance of $\Alg$ (on the realized losses/disturbances) compared to the best policy $\pi \in \Pi$ in hindsight (chosen with knowledge of losses and disturbances). We consider a restricted a benchmark class $\Pi$ consisting of linear, dynamic controllers, formalized in \Cref{defn:benchmark}. While this class encompasses optimal control laws for many classical settings \citep{simchowitz2020improper}, in general it \emph{does not} include the optimal control law for a given realization of noise. This \nipstogfalse{restriction} is unavoidable: even in \iftoggle{nips}{the simplest settings,}{simple, noiseless settings with adversarial costs,} it is impossible to attain sublinear regret with respect to the optimal control law \citep{li2019online}.
\nipstogfalse{

}
We assume that the losses $\ell_t(\cdot)$ are $\alpha$-strongly convex, and grow at most quadratically:
\begin{assumption}\label{asm:loss_reg} We suppose that all $\cost_t:\R^{\dimy + \dimu} \to \R$ are \emph{$L$-subquadratic:} $0 \le \cost(v) \le L\max\{1,\|v\|_2^2\}$, and $\|\nabla \cost(v)\|_2 \le L\max\{1,\|v\|\}$.  We also assume that $\cost_t$ are twice-continuously differentiable, and $\alpha$-strong convex ($\nablatwo \cost_t \succeq \alpha I$).  For simplicity, we assume $L \ge \max\{1,\alpha\}$.
\end{assumption}
This assumption is motivated by classical LQR/LQG, where the loss is a strongly convex quadratic of the form $\ell(y,u) = y^\top R y + u^\top Q u$ for $R,Q \succ 0$. The central technical challenge of this work is that, unlike  standard online learning settings, \emph{the strong convexity of the losses does not directly yield fast rates}~\citep{agarwal2019logarithmic,foster2020logarithmic}.

\subsection{Our Contributions}
For the above setting, we propose \emph{Disturbance Reponse Control via Online Newton Step}, or \drcons{} - an adaptive control policy which attains fast rates previously only known for settings with stochastic or semi-stochastic noise \citep{mania2019certainty,simchowitz2020improper,cohen2019learning,agarwal2019logarithmic}. Our algorithm combines the \drc{} controller parametrization \citep{simchowitz2020improper} with \semions{}, a novel second-order online learning algorithm tailored to our setting.  We show that \drcons{} achieves logarithmic regret when the learner knows the dynamical matrices:

\begin{informaltheorem}[thm:known_control]
When the agent knows the dynamics \eqref{eq:LDS_system} (but does not have foreknowledge of disturbances nor the costs $\ell_t$),  \drcons{} has $\ControlReg_T = \bigohst{\frac{L^2}{\alpha} \cdot \poly(\log T )}$.
\end{informaltheorem}

This is the first bound to guarantee logarithmic regret with general strongly convex losses and non-stochastic noise. Past work required stochastic or semi-stochastic noise \citep{agarwal2019logarithmic,simchowitz2020improper}, or was limited to fixed quadratic costs \citep{foster2020logarithmic}. For unknown dynamics, we find:

\begin{informaltheorem}[thm:unknown_control]
When the dyamics are unknown, \drcons{} with an initial estimation phase attains $\ControlReg_T = \widetilde{\mathcal{O}}(\frac{L^2}{\alpha}\sqrt{T})$.
\end{informaltheorem}

This bound matches the optimal $\sqrt{T}$-scaling for \emph{stochastic} online LQR \citep{simchowitz2020naive}. Thus, from the perspective of regret minimization with respect to the benchmark $\Pi$, non-stochastic control is \emph{almost} as easy as stochastic. This is not without many caveats, which are left to the discussion in \Cref{app:comparison_discussion}.

\paragraph{Technical Contributions} While our main results are control theoretic, our major technical insights pertain to online convex optimization (\oco). Our control algorithm  leverages a known reduction \citep{agarwal2019online} to the online convex optimization with memory (\ocom) framework \citep{anava2015online}, which modifies \oco{} by allowing losses to depend on past iterates. Past \ocom{} analyses required bounds on both the standard \oco{} regret and  total Euclidean variation of the iterates produced (\Cref{sec:semions_sketch}).
\nipstogfalse{

}
But for the the losses that arise in our setting, \Cref{thm:Regmu_lb} shows that there is a significant tradeoff between the two, obviating sharp upper bounds.
\nipstogfalse{
Specifically, with non-stochastic noise, the loss functions induced by this reduction are no longer strongly convex. They do satisfy a weaker property called exp-concavity, an assumption which suffices for fast rates in standard \oco{}. However, we show that this condition is not sufficient to naively extend the standard \ocom{} approach:
	\begin{informaltheorem}[thm:Regmu_lb] For exp-conave (but not necessarily strongly convex) losses, \ocom{} analyses based on  Euclidean movement cannot guarantee better than $\Omega(T^{1/3})$ regret, which translates into $\Omega(T^{1/3})$ regret for the setting of controlling an \emph{known} system. This lower bound is matched by the Online Newton Step algorithm \citep{hazan2007logarithmic} with an appropriately selected regularization parameter.

\end{informaltheorem}
In addition, \Cref{thm:Regmu_lb} characterizes the tradeoff between \oco-regret and Euclidean movement cost for exp-concave losses; for example, it shows any algorithm which attain logarithmic regret in the (without memory) \oco-setting suffers Euclidean movement cost $\tilde{\Omega}(\sqrt{T})$.

}
To overcome this \nipstogfalse{ lower bound}, we show that online control enjoys additional structure  we call \emph{\oco{} with affine memory}, or \ocoam{}.
We propose a novel second order method, \semions{},  based on online Newton step (\ons,~\cite{hazan2007logarithmic}), tailored to this structure.
Under a key technical condition satisfied by online control, we establish logarithmic regret.

\begin{informaltheorem}[thm:semions_memory]

 Under the aforementioned assumption (\Cref{defn:input_recov}), the \semions{} algorithm attains $\BigOh{\frac{1}{\alpha}\log T}$ regret in the \ocoam{} setting.

\end{informaltheorem}

The above bound directly translates to logarithmic control regret for known systems, via the control-to-\ocoam{} reduction spelled out in \Cref{sec:prelim}. For control of unknown systems, the undergirding \ocoam{} bound is quadratic sensitivity to $\epsilon$-approximate losses:
\begin{informaltheorem}[thm:semions_unknown]

 Consider the \ocoam{} setting with $\epsilon$-approximate losses (in the sense of \Cref{asm:approx_ocoam}). Then, \nipstogfalse{under appropriate assumptions,}  \semions{} has regret $\BigOh{\frac{1}{\alpha}\log T \cdot T \epsilon^2}$.
 \end{informaltheorem}

Quadratic sensitivity to errors in the gradients  was previously demonstrated for strongly convex stochastic optimization \citep{devolder2014first},  and subsequently for strongly convex \oco{} \citep{simchowitz2020improper}. Extending this guarantee to \semions{}  is the most intricate technical undertaking of this paper.
\nipstogfalse{The full full formulation of \ocoam{}, description of the \semions{} algorithm, and rigorous statements of the above two bounds are given in \Cref{sec:ocoam_setting,sec:semions_alg,sec:semions_bounds}, respectively. \Cref{sec:semions_sketch} motivates  the novelty of our proof strategy and algorithm, and \Cref{sec:lb} formalizes the limitations of past approaches via a regret-movem{}ent tradeoff (\Cref{thm:Regmu_lb}).}

\subsection{Prior Work\label{ssec:prior_work}}
In the interest of brevity, we restrict our attention to previous works regarding online control with a regret benchmark; for a survey of the decades old field of adaptive control, see e.g. \cite{stengel1994optimal}.
Much work has focused on obtaining low regret in online LQR with unknown dynamics \citep{abbasi2011regret,dean2018regret,mania2019certainty,cohen2019learning}, a setting we formally detail in \Cref{ssec:app_lqr}.  Recent algorithms \citep{mania2019certainty,cohen2019learning} attain $\sqrt{T}$ regret for this setting, with polynomial runtime and polynomial regret dependence on relevant problem parameters.  This was recently demonstrated to be optimal \citep{simchowitz2020naive,cassel2020logarithmic}, with \citet{cassel2020logarithmic}  showing that logarithmic regret is possible the partial system knowledge. In the related LQG setting (partial-observation, stochastic process and observation noise, \Cref{ssec:app_lqg}), \citet{mania2019certainty} present perturbation bounds which suggest $T^{2/3}$ regret, improve to $\sqrt{T}$ by \citet{lale2020regret}, matching the optimal rate for LQG. For LQG with both non-denegerate process and observation noise,  \citet{lale2020logarithmic} attain $\poly(\log T)$ regret, demonstrating that in the presence of observation, LQG is in fact \emph{easier} than LQR (with no observation noise) in terms of regret; see \Cref{app:comparison_discussion} for further discussion.

Recent work first departed from online LQR by considered adversarially chosen costs under known stochastic or noiseless dynamics \citep{abbasi2014tracking,cohen2018online}. \citet{agarwal2019logarithmic} obtain logarithmic regret for fully observed systems, stochastic noise and adversarially chosen, strongly convex costs.  The non-stochastic control setting we consider in this paper was established in
\citet{agarwal2019online}, who obtain $\sqrt{T}$-regret for convex, Lipschitz (not strongly convex) cost functions and known dynamics. \citet{hazan2019nonstochastic} attains $T^{2/3}$ regret for the same setting with unknown dynamics. \citet{simchowitz2020improper} generalizes both guarantees to partial observation, and generalize the optimal rate of logarithmic and $\sqrt{T}$ for known and unknown systems, respectively to  strongly convex losses and a `semi-stochastic'' noise model. This assumption requires the noise to have a well-conditioned, stochastic component; in contrast, our methods allow \emph{truly adversarial} noise sequences. Lastly, for the known system setting, \citet{foster2020logarithmic} propose a different paradigm \nipstogfalse{- online learning with advantages - }which yields logarithmic regret with truly adversarial noise, but fixed quadratic cost functions and with full observation. In contrast, our algorithm accomodates both partial observation and arbitrary, changing costs, and its analysis and presentation are considerably simpler. Our work also pertains to the broader literature of online optimization with policy regret and loss functions with memory \citep{arora2012online,anava2015online}, and our lower bound (\Cref{thm:Regmu_lb}) draws on the learning-with-switching-costs literature \citep{altschuler2018online,chen2019minimax,dekel2014bandits}.

\subsection{Organization and Notation}
\Cref{sec:ocoam} formulates the general \ocoam{} setting, describes our \semions{} algorithm, and states its guarantees (\Cref{thm:semions_memory,thm:semions_unknown}), and the regret-movement tradeoff that hindered past approaches (\Cref{thm:Regmu_lb}). \Cref{sec:prelim} turns to the control setting, describing the reduction to \ocoam{}, the \drcons{} algorithm, and stating our main results (\Cref{thm:known_control,thm:unknown_control}).
\iftoggle{nips}{
Discussion of our results is deferred to \Cref{app:comparison_discussion}. All proofs are deferred to our appendix, whose  organization of the appendix is detailed in \Cref{app:organization}.
}
{\Cref{sec:known} proves \Cref{thm:semions_memory}, and \Cref{sec:unknown} proves \Cref{thm:semions_unknown} and an important refinements (\Cref{thm:semions_unknown_clam}) required  for the control setting. Finally, \Cref{app:comparison_discussion} discusses the consequence of our results.
The organization of the appendix is detailed in \Cref{app:organization}.
}
\nipstogfalse{

}
Throughout, let $a \lesssim b$ denote that $a \le C b$, where $C$ is a universal constant independent of problem parameters. We use  $\bigomst{\cdot},\bigohst{\cdot}$ as informal asymptotic notation.
	 We let  $a \vee b$ denote $\max\{a,b\}$, and $a \wedge b$ to denote $\min\{a,b\}$. For vectors $x$ and $\Lambda \succeq 0$,  we denote $\|x\|_{\Lambda}:= \sqrt{x^\top \Lambda x}$, and use $\|x\|$ and $\|x\|_2$ interchangeably for Euclidean norm. We let $\|A\|_{\op}$ denote the operator norm, and given a sequence of matrices $G = (G^{[i]})_{i \ge 0}$, we define $\|G\|_{\loneop} := \sum_{i \ge 0}\|G^{[i]}\|_{\op}$. We use $[(\cdot);(\cdot)]$  to denote vertical concatenation of vectors and matrices. Finally, non-bold arguments (e.g. $z$) denote function arguments, and bold (e.g. $\matz_t$) denote online iterates.


TITLE: Binomial sum and 2F1
QUESTION [0 upvotes]: In the solution to the Newton-Pepys problem here, there's an identity applied on the third line to relate a binomial sum to the hypergeometric function 2F1. What is the general statement of the identity?

REPLY [2 votes]: $$P_n = \sum _{x=n}^{6n} \binom{6n}{x}\left(\frac{1}{6}\right)^{x}\left(\frac{5}{6}\right)^{6n-x}\\ =\frac{5^{5n}}{6^{6n}}\binom{6n}{n}\sum_{x=n}^{6n}\frac{(5n)!n!}{x!(6n-x)!}5^{n-x}\\
=\frac{5^{5n}}{6^{6n}}\binom{6n}{n}\sum_{k=0}^{5n}\frac{(5n)!n!}{(k+n)!(5n-k)!}\frac{1}{5^k}\\
=\frac{5^{5n}}{6^{6n}}\binom{6n}{n}\sum_{k=0}^{5n}\frac{(5n-k+1)\cdots(5n)}{(n+1)\cdots(n+k)}\frac{1}{5^k}\\
=\frac{5^{5n}}{6^{6n}}\binom{6n}{n}\sum_{k=0}^{5n}\frac{(-5n)_k}{(n+1)_k}\left(-\frac{1}{5}\right)^k\frac{k!}{k!}\\
=\frac{5^{5n}}{6^{6n}}\binom{6n}{n}\sum_{k=0}^{5n}\frac{(-5n)_k(1)_k}{(n+1)_k}\left(-\frac{1}{5}\right)^k\frac{1}{k!}\\
=\frac{5^{5n}}{6^{6n}}\binom{6n}{n}{_2F_1}(1;-5n;n+1;-\frac{1}{5}).$$
I used this symbol as in Wikipedia's definition of hypergeometric series.


TITLE: Integral of Stochastic Integral $ x(t) = \int_0^te^{as}dW_s $
QUESTION [1 upvotes]: I'm working through an exercise where I have got the following object:
$$ x(t) = \int_0^te^{as}dW_s $$
for some constant $a$. Now, I need to find the distribution of $\int_0^t x(s) ds$. I'm struggling to do this and I don't know where to look for help.
So, I want to find the distribution of:
$$ \int_0^t \int_0^s e^{au} dW_uds $$
How do I go about solving this problem? In particular I need to find it's mean and variance. I assume that the order of integration can't be swapped, but I don't know for certain. Can anyone enlighten me?

REPLY [2 votes]: Integrate by parts
\begin{align}
\int_0^t x(s) ds&= tx(t) -\int_0^t sdx(s) \\
& =t\int_0^te^{as}dW_s-\int_0^t se^{as}dW_s \\
&= \int_0^t(t-s)e^{as}dW_s
\end{align}
which is a normal distribution of zero-mean and variance
$$var=\int_0^t(t-s)e^{2as}ds=\frac{e^{2at}-2at-1}{4a^2}$$


TITLE: Sum of average reciprocal of which random variable converges to a Cauchy distribution?
QUESTION [6 upvotes]: If $(X_n)_{n\in\mathbb{N}}$ are independent identically distributed random variables with density $f$ even, continuous in $0$ and such that $f(0)>0$, then $$\frac{1}{n}\left(\frac{1}{X_1}+\dots + \frac{1}{X_n}\right)\xrightarrow{d}Z$$ With $Z$ a r.v. with Cauchy distribution.

REPLY [1 votes]: By Lévy's continuity theorem it's enough to prove that $\left(\varphi_{1/X_1}(t/n)\right)^n \rightarrow e^{-a|t|}$, with $\varphi_X(t):=\mathbb E^X\left[e^{itX}\right]$.
It is a well-known fact that if $(c_n)_{n\in \mathbb{N}}$ is a complex succession with limit $c$ then:
$$
\lim_{n\rightarrow +\infty}\left(1+c_n/n\right)^n=e^c.
$$
In this case $c_n=n\left(\varphi_{1/X_1}(t/n)-1\right)=n \mathbb  E^{1/X_1}[e^{(it)/(nX_1)}-1]$. Because $f$ is even:
$$
c_n=n\mathbb E^{1/X_1}[\cos(t/(nX_1))-1].
$$
Then:
\begin{align}
\lim_{n\to +\infty}c_n&=\lim_{n\to +\infty} \int_{-\infty}^{+\infty}n\frac{\cos(tx/n)-1}{x^2}f(1/x) \ dx\\
&=\lim_{n\to \infty} \int_{-\infty}^{+\infty}-n|t|(1-\cos(1/(ny)))f(ty) \ dy
\end{align}
with $y:=1/(tx)$.
If $\rho (y)=1-cos(1/y)$ and $\rho_n(y)=n\rho(ny)$ then $\int \rho=\int \rho_n =\pi$ and $\rho_n$ have masses that concentrate in $0$. So  $\lim_{n\to +\infty}c_n=-\pi f(0)|t|$ and we have the thesis.


TITLE: On the product over primes $\prod_{p \leq N} \frac{p-1}{p-2}$
QUESTION [2 upvotes]: First of all, sorry for my ignorance. I'm just a common guy interested in maths.
I have read a lot about the product
$$\prod^{N} \frac{1}{1-\frac{1}{p}}=\prod^{N} \frac{p}{p-1}$$
(Where $p$ is a prime number); including its behaviour and its relationship with Zeta function and the Harmonic series when $N \to \infty$.
But what's about this other product?
$$\prod^{N} \frac{p-1}{p-2}$$
Is it any lower or upper bound known for it? What is its asymptotic behaviour? Where could I find information about it?
Thank you!

REPLY [4 votes]: I assume that, for this product, you don't want to include $2$ as one of your primes, so I'll consider
$$\prod_{2<p\leq N} \frac{p-1}{p-2}$$
Note that
$$\frac{n}{n-1}$$
is a strictly decreasing function of $n$, so we have that
$$\frac{p_{n-1}}{p_{n-1}-1} \geq \frac{p_n-1}{p_n-2} > \frac{p_n}{p_n-1}$$
where $p_n$ is the $n$th prime ($p_1=2,p_2=3,\cdots$)
So, the product can be bounded by
$$\prod_{n=2}^{\pi(N)} \frac{p_{n-1}}{p_{n-1}-1} \geq \prod_{n=2}^{\pi(N)} \frac{p_n-1}{p_n-2} > \prod_{n=2}^{\pi(N)} \frac{p_n}{p_n-1} $$
Denote $X_k = \prod_{n=1}^{k} p_k$ as the $k$th primorial, and let $\phi(n)$ represent the Euler totient function. We can now bound our product by
$$\frac{X_{\pi(N)-1}}{\phi\left(X_{\pi(N)-1}\right)} \geq \prod_{2<p\leq N} \frac{p_n-1}{p_n-2} > \frac{X_{\pi(N)}}{2\phi\left(X_{\pi(N)}\right)}$$
We can use Mertens' third theorem to give that
$$\frac{X_{\pi(N)}}{\phi\left(X_{\pi(N)}\right)}\sim e^{\gamma} \log N$$
So, the product is asymptotically between $\frac{e^{\gamma}}{2}\log N$ and $e^{\gamma}\log N$, so it is asymptotically logarithmic.
Getting a very precise upper bound is extremely difficult, but we can do it assuming the Riemann Hypothesis using "RH Equivalence 3.25" here.


TITLE: Homology of bar complex vs homology of indecomposables
QUESTION [5 upvotes]: $\require{AMScd}$
Background: This question is about the bar and cobar constructions, and their relationship with the indecomposables of a dg-algebra. A brief summary of the bar and cobar constructions on ncatlab can be found at [1]. I will also mention the more general case of $A_\infty$ algebras; this case is discussed in this survey [2] or in Proute's thesis [3]. I posted a related question a few months ago in the mathoverflow post [4]. There I called the dg-module of indecomposables the ``linearized chain complex.'' It seems that the former is more standard terminology so I've switched for the time being.
Setup: Let $(A,\partial,\epsilon)$ be an augmented dg-algebra over a field $k$, i.e. a dg-algebra $(A,\partial)$ along with dg-algebra map $\epsilon:A \to k$. Here $k$ is a dga with trivial grading and differential.
The module of indecomposables $(IA,\partial)$ of $(A,\partial,\epsilon)$ is a dg-module whose underlying graded $k$ vector-space is $IA = \ker(\epsilon)/\ker(\epsilon)^2$. The differential $\partial$ on $A$ descends to a differential $\partial$ on $IA$. Furthermore, the correspondence $(A,\partial,\epsilon) \mapsto (IA,\partial)$ is functorial. That is, given a map: $$f:(A,\partial,\delta) \to (B,\partial,\epsilon)$$ of augmented dg-algebras, i.e. a dg-algebra map with $\epsilon \circ f = \delta$, we get a map of dg-modules:
$$If:(IA,\partial) \to (IB,\partial)$$
The bar complex $BA$ of $(A,\partial,\epsilon)$ to a dg-coalgebra whose underlying graded vector-space is:
$$
BA := k \oplus BA^+ \qquad BA^+ := \bigoplus_{i=1}^\infty \ker(\epsilon)[1]^{\otimes i}
$$
The differential combines multiplication and differentiation from $(A,\partial)$ (see [1] for an actual definition) and the coaugmentation $\iota:k \to BA$ is just the inclusion. Similarly, the cobar complex $\Omega C$ of an augmented dg-coalgebra $C$ is an augmented dg-algebra admitting an analogous description to that of $BA$, as a certain tensor algebra. Both constructions are functorial, and there are generalizations of to $A_\infty$ algebras and coalgebras (see [2] or [3]).
The functors $B$ and $\Omega$ form an adjoint pair ($B$ is right adjoint to $\Omega$) and we have natural adjoint maps $\Omega B A \to A$ and $C \to B \Omega C$, which are quasi-isomorphisms of augmented dg-algebras and coaugmented dg-coalgebras, respectively. There is a reference for this in the post [5]. In particular, we get a natural map of dg-modules between the indecomposables:
$$
I\Omega B A \to IA
$$
I believe that it is true that $I\Omega C \simeq \text{coker}(\kappa)$ for any coaugmented dg-coalgebra $(C,\partial,\kappa)$ (an actual isomorphism of chain groups, not just a quasi-isomorphism) so that the above map yields a canonical map of dg-modules and a corresponding map on homology:
$$
BA^+ \to IA \qquad H(BA^+) \to H(IA)
$$

Question: Under what circumstances is the natural map $I\Omega B A \to IA$ an isomorphism on homology? When is it surjective on homology? I'm particularly interested in the case where the underlying graded algebra of $(A,\partial,\epsilon)$ is the free graded commutative algebra over some generators. Any partial answers are much appreciated.

Examples: In some cases this map is simple to understand. For instance, when $A$ is an algebra with the trivial differential and grading, then $H(IA) = IA$ and I believe that the map on homology $H(BA^+) \to H(IA)$ is just projection onto $H^1(BA^+) \simeq IA$.
Another context where something similar happens is when $A = \Omega C$ where $(C,\partial,\kappa)$ is a coaugmented dg-coalgebra (or even an $A_\infty$ coalgebra). Then the map:
$$\text{coker}(\iota) \simeq BA^+ \to IA \simeq \text{coker}(\kappa)$$
is just the $A_\infty$ quasi-isomorphism on the cokernels of the coaugmentations induced by the quasi-isomorphism of $A_\infty$ coalgebras of $B\Omega C \to C$, itself induced by the adjunction map $\Omega B \Omega C \to \Omega C$. Since $A_\infty$ quasi-isomorphisms descend to isomorphisms on homology, we know in particular $H(BA^+) \simeq H(IA)$ under the map of interest.

REPLY [4 votes]: The functor of indecomposables is the left adjoint of a Quillen adjunction between dg-algebras and dg-modules. (For a general reference, see Section 12.1.3 of the book Algebraic Operads by Loday and Vallette, though this was certainly known before the book – I just happen to have it on my desk.) As such it preserves quasi-isomorphisms between cofibrant algebras. The bar-cobar construction on $A$ is always cofibrant, so a sufficient condition for your claim is that $A$ should be cofibrant.
Since you are interested in the case of free symmetric algebra, if $A$ is free symmetric on some space of generators $V$ equipped with a filtration $$0 = F_0 V \subset F_1 V \subset \dots \subset V = \bigcup_{i \ge 0} F_i V$$
such that $\partial(F_i V) \subset S(F_{i-1}(V))$ (i.e. the differential of an element in $F_i V$ is a product of elements in lower filtration), then $A$ is cofibrant. In fact you can assume that the filtration is indexed by an ordinal, not just integers, if you need.
The homology of $I \Omega B A$ is the Hochschild homology of $A$ with constant coefficients $HH_*(A;\Bbbk)$. (Again, see the book of Loday and Vallette.) I wouldn't expect your map to be a quasi-isomorphism if $A$ is not cofibrant – it certainly can happen, but it's basically a coincidence. As for surjective on cohomology... I have no idea.


TITLE: Help with the proof of the Witch of Agnesi curve
QUESTION [2 upvotes]: $a=1$ (The radius is 1).
How do I prove that if we talking about $P=(x,y)$, then:  $$y=\frac{8}{x^2+4}$$
I'd like to get any help!
Thank you!

REPLY [1 votes]: The line through $O$ and $A$ has equation $x=\frac{x_A}{2}y$, the circle has equation $x^2+(y-1)^2=1$. Substituting $x$ from the first into the second you find the coordinates $(x_B,y_B)$ of $B$. You get $(\frac{x_A}{2}y_B)^2+(y_B-1)^2=1$ whence $((4+x_A^2)y_B-8)y_B=0$. Noting that $y_P=y_B$ and $x_P=x_A$ you finally get $((4+x_P^2)y_B-8)y_P=0$.


TITLE: For any matrix norm, is it true $||A|| \le \max|a_{ij}|\cdot ||(1)||$?
QUESTION [4 upvotes]: Let $|| \cdot ||$ be a matrix norm on $m \times n$ matrices, which is not assumed to be submultiplicative. Is it true that $||A|| \le \max|a_{ij}|\cdot ||(1)||$ where $(1)$ denotes the matrix with all entries equal to 1? I tried to use triangle inequality but I don't know how to prove it.

REPLY [3 votes]: It is incorrect when $mn>1$. A simple counter-example: for $A=(a_{ij})$, let
$$\|A\|=|a_{11}|+\sum_{ij}|a_{ij}-a_{11}|.$$
Remark: When $m=n>1$, even if $\|\cdot\|$ is submultiplicative, the conclusion is still incorrect . To provide a counter-example, you may choose $\|\cdot\|$  as defined in $(4)$ here with $P=\lambda\cdot(1)$, where $\lambda>1$ is a large constant determined by the norm $\|\cdot\|'$ in $(4)$.


TITLE: Invertible matrix for moving between bilinear forms?
QUESTION [1 upvotes]: Let $V$ be a finite dimensional vector space over $\mathbb C$. Suppose $f,g$ are symmetric bilinear forms on $V$. Prove there's an invertible $T:V\to V$ such that $f(Tx,Ty)=g(x,y)$ iff $f,g$ have equal rank. Is the claim true over $\mathbb R$ as well?
I thought the answer over both $\mathbb R$ and $\mathbb C$ is yes, by taking $T:b_i\to c_i$ for $(b_i),(c_i)$ respectively orthonormal bases for $f,g$. However, I don't even know how to prove my claim, and suspect I'm missing something important over $\mathbb R$...

REPLY [2 votes]: For the first part:  you can always diagonalize a complex bilinear form to have just ones and zeros down the diagonal. The rank will be equal to the number of $1$s. If two forms diagonalize to the same matrix, there is a change of basis between the two.
For real forms, you can diagonalize down to $0$ and $\pm 1$. Now two forms whose Gram matrices have equal rank can still have different signatures. For example, the bilinear form $f(x,y)=xy$ can't be changed to the bilinear form $g(x,y)=-xy$.


TITLE: Function doesn't satisfy the local condition of Lipschitz at intervals that contain $0$
QUESTION [1 upvotes]: The local Lipschitz criterion is the following:
Let $c>0$ and $f \in C([a,b] \times [y_0-c, y_0+c])$.
If $f$ satisfies in $[a,b] \times [y_0-c,y_0+c]$ the Lipschitz criterion as for $y$, uniformly as for $t$,
$$\exists L \geq 0: \forall t \in [a,b] \  \forall y_1, y_2 \in [y_0-c,y_0+c]:$$
$$|f(t,y_1)-f(t,y_2)| \leq L|y_1-y_2|$$
then the ODE $(1) \left\{\begin{matrix}
y'(t)=f(t,y(t))\\
y(a)=y_0
\end{matrix}\right.$ is solved uniquely, at least at the interval $[a,b']$
where $A=\max_{a \leq t \leq b ,  y_0-c \leq y \leq y_0+c} |f(t,y)| \ $ and
$b'=\min \{ b, a+ \frac{c}{A}\}$.
Remark: The continuity of $f, f \in C([a,b] \times \mathbb{R})$ suffices to ensure the existence of a solution of the ODE $(1)$ at an interval $[a,c], c>a$. But, it doesn't ensure us the uniqueness.
For example, $f(y)=\sqrt{|y|}$ doesn't satisfy the local criterion of Lipschitz as for $y$ at none interval that contains $0$.
I tried to show the latter as follows:
$$\frac{|f(t,y_1)-f(t,y_2)|}{|y_1-y_2|}=\frac{|\sqrt{|y_1|}-\sqrt{|y_2|}|}{|y_1-y_2|}=\frac{|\sqrt{|y_1|}-\sqrt{|y_2|}|}{|\sqrt{|y_1|}-\sqrt{|y_2|}||\sqrt{|y_1|}+\sqrt{|y_2|}|}=\frac{1}{|\sqrt{|y_1|}+\sqrt{|y_2|}|}=\frac{1}{\sqrt{|y_1|}+\sqrt{|y_2|}}$$
Is it right so far? And how do we justify that $f$ doesn't satisfy the local condition of Lipschitz as for $y$ at none of the intervals that contains $0$.
Does it hold because of the fact that it can be that $y_1=y_2=0$?
Also how can we find the intervals at which the local Lipschitz condition is satified?

REPLY [1 votes]: First question
Since $y_1$ and $y_2$ are as close to $0$ as you want, it is impossible to have $1/(\sqrt{|y_1|}+\sqrt{|y_2|})$ bounded by a constant.
Second question
Most of the times, the easiest way to show that $f(x,y)$ satisfies a Lipschitz condition is to show that $\partial f/\partial y$ is bounded. In this case (for $y>0$) $f'(y)=1/(2\,\sqrt{y})$, which is not bounded as $y\to0$.


TITLE: Area between common region between two intersecting circles
QUESTION [0 upvotes]: Two circled with radius $2R$ and $\sqrt{2}R$ intersect each other at points $A$ and $B$. The centres of both the circles are on the same side of $AB$. $O$ is the centre of the bigger circle and $\angle{AOB}$ is $60^\circ$. Find the area of the common region between two cirlces.
I solved this problem two times and every time I came to the same solution of $R^2(2\pi-\frac{\sqrt{3}}{2})$. However the answer provided is $R^2(\frac{13\pi}{6}+1-\sqrt{3})$ and unable to get to the same. Can someone please help with a solution for this? Please help !

PS : I am sorry as I am not able to put my solution approach here as I can not put up a figure to show my calculations.

REPLY [0 votes]: Simplify the process with $R=1$
$AO'=\sqrt 2,AE=1,EO'=1", $ $\triangle AEO'$ is a $45^\circ-90^\circ-45^\circ$ triangle.
\begin{align}S_{ADE}=S_{ADO}-S_{AEO}=\frac{\pi}{3}-\frac{\sqrt 3}{2}\end{align}
\begin{align}S_{ACD}=S_{AO'C}-S_{ADE}-S_{AEO'}=\frac{\pi}{4}-(\frac{\pi}{3}-\frac{\sqrt 3}{2})-\frac{1}{2}=\sqrt3-\frac{\pi}{12}-\frac{1}{2}\end{align}
\begin{align}S=2\pi-\sqrt 3+\frac{\pi}{6}+1=\frac{13\pi}{6}-\sqrt 3+1\end{align}
Scale back R:  \begin{align}S=R^2(\frac{13\pi}{6}-\sqrt 3+1)\end{align}


TITLE: $\varphi$ monotone,continuous on $[0,1]$. Show $\varphi$ is AC, iff for any borel $f_n\to f$ in $L^1$,$\{\varphi(f_n)\}$ converges in measure.
QUESTION [6 upvotes]: Let $\varphi$ be monotonic and continuous on $[0,1]$. Show it is AC, iff for any borel sequence $f_n$ that converges in $L^1$ the sequences $\varphi(f_n)$ converges in measure.
The forward direction follows from the fact that $f_n \to f$ in $L^1$ implies convergence in measure and continuity preserves convergence in measure on finite measures. The backwards direction is the one that is giving me a little more trouble.
Since $\varphi$ is monotonic (WLOG its increasing) all we have to show is that  $\nexists x$ s. t. $\int_{0}^{x}\varphi'\lt\varphi(x)-\varphi(0)$. However I do not really know how to do that.
Any hints would be highly appreciated.

REPLY [2 votes]: What you showed is that the claim is always true, even without assuming that $\varphi$ is AC. Therefore, the converse direction is not true (take your favourite non AC monotonic continuous function, e.g. the devil's staircase).

A correct characterization (at least for the case that $\varphi$ is strictly increasing) is as follows:
Assume that $\varphi : [0,1] \to [a,b]$ is strictly increasing,
so that $\varphi^{-1} : [a,b] \to [0,1]$ is well-defined.
Then $\varphi$ is AC if and only if whenever $f_n \to f$ in $L^1$,
then $f_n \circ \varphi^{-1} \to f \circ \varphi^{-1}$ in measure.
Indeed, if $f_n \to f$ in measure, then it is not too hard to see
(with $\lambda$ denoting the Lebesgue measure) that
\begin{align*}
  \lambda \bigl(\{ x : |f_n \circ \varphi^{-1}(x) - f \circ \varphi^{-1} (x)| > \epsilon \}\bigr)
  & = \lambda\bigl( \varphi ( \{ y : |f_n (y) - f (y)| > \epsilon \} ) \bigr) \\
  & = \int_0^1
      \varphi'(t) \cdot 1_{|f_n(t) - f(t)| > \epsilon}
    \, d t
  & \xrightarrow[n\to\infty]{} 0
\end{align*}
for arbitrary $\epsilon > 0$ by the dominated convergence theorem,
since the indicator function converges to zero in measure.
Conversely, suppose towards a contradiction that $\varphi$ is not absolutely continuous.
By definition, this means that there is some $\epsilon > 0$ such that for each $n \in \Bbb{N}$
there is a pairwise disjoint family of intervals $(a_i^{(n)}, b_i^{(n)}) \subset [0,1]$
($i = 1,\dots,m_n$) such that $\sum_{i=1}^{m_n} (b_i^{(n)} - a_i^{(n)}) < \frac{1}{n}$,
but $\sum_{i=1}^{m_n} \bigl(\varphi(b_i^{(n)}) - \varphi(a_i^{(n)})\bigr) \geq \epsilon$.
This means if we define $f_n := \sum_{i=1}^{m_n} 1_{(a_i^{(n)}, b_i^{(n)})}$, then $f_n \to 0$
in $L^1$, but $f_n \circ \varphi^{-1} = \sum_{i=1}^{m_n} 1_{\bigl(\varphi(a_i^{(n)}), \varphi(b_i^{(n)})\bigr)}$
does not converge to zero in measure.