TITLE: MPC trajectory optimization intuition
QUESTION [2 upvotes]: Introduction
I’ve been a struggling to create some intuition around trajectory optimization for MPC. I'd really, really like some help in creating that intuition, whether it be some pointers, some literature recommendations, some videos, anything. Something to help me build an understanding as to how these problems are actually optimized.
Context
I am a dumb dual electrical engineer/applied math recent graduate, so if possible I'd really appreciate some tangible intuition into how the optimization process works for trajectory optimization.
I've done some courses on numerical linear algebra and optimization during my studies, so I'm familiar with how 2nd order methods like L-BFGS are defined and implemented (and even know some tricks like implicit formulation of the hessian to save memory).
However I am having trouble understanding the intuition behind open loop optimisation methods like trajectory optimization.
Every tutorial on the internet I've looked, when they get to the step of optimizing their NLP problem, uses CasADi, which often just wacks an NLP formatted problem into its magic solve() function and hey presto you've got your optimal trajectory.
I understand that the tools in CasADi are really popular and powerful, and the people who came up with the algorithms that can solve these problems are amazing. In a production environment, I'd probably use CasADi as a solver as well, since its well researched and robust.
However, I'd really like to understand the intuition as to how these problems are solved fundamentally before I go taking advanced tools like CasADi for granted.
Toy problem
I'll elaborate with a toy problem I came up with.
I'll be opting for a Direct transcription method as its easier to solve (or so I've heard).

Here I've shown a classic system used to introduce chaotic motion to undergrads doing math degrees.
It's a polar system that is inherently stable.
Given some point ($r$,$\theta$), I want to determine the optimal trajectory to the stable ring ($r^2 = \lambda$).
We denote the position of the point (or state) as $x_k$
Since $\dot{r}$ is dependent on $\lambda$, as our point moves colser to the stable ring, each step size will become smaller (as the change in $r$ will become smaller and smaller as we move closer to $\lambda$).
This might not be optimal, as I may have a time constraint for when the point should be within some small margin around the stable ring.
We could control the system using MPC, denoting the control state at time $k$ as $u_k$, and giving it the ability to change the value of $\lambda$ at each timestep.
This way the point could be moved to the original position of $\lambda$ much faster.

Here I've fleshed out the control problem in a bit more detail to show my understanding.
$x^r$ and $u^r$ are the target state and resting control state respectively.
In order to achieve an optimal trajectory, we need to minimize some cost function.
Here I’ve denoted the cost function, $J_N(x,u)$ as the sum of all the running costs $l(x_k,u_k)$.
This cost function allows for balancing of the state error with control error (i.e. we want a snappy response, but we might want to limit how harsh the changes in controller input can be).
Where the issue arises
I'm aware of two methods to solve this problem

Shooting methods
(based on simulation, better for problems with simple control and no path constraints)
Collocation methods
(based on function approximation, better for problems with complicated controls and/or path constraints)

I had a go at formulating an implementation for the single shooting method as I heard it was the easiest.

Here $U^T$ denotes the control vector, and $X^T$ the state vector.
Question now is, what do I do from here?
$X^T$ is based on the prior states of $x_k$, hence the problem has an infinite number of solutions.
Trajectory optimization, according to what I've read, provides an open loop solution to the problem, meaning a global picture of the system is not required in order to achieve some minimum.
But implementing this on a computer is not straight forward.
Do I "guess" what the path should be?
When I put said path into the cost function, how do I determine how the path should change in order to be less wrong (as changing one segment would require re-computing the other segments)?
I have no idea how collocation works, and most of the tutorials online aren't super clear about how the idea works.
Please I'd really appreciate some pointers, advice, literature recommendations, anything. Something to help me see how this wonderful idea works.
Kind regards,
Despicable_B
EDIT 1:
After some more research, I think I now understand the difference between shooting and (direct) collocation methods.
Shooting Methods:
Shooting methods optimize over the set of control states, and the state trajectory is implicitly determined from those control states.

The upside is that shooting methods tend not to violate the dynamics of the problem, as the dynamics are an implicit constraint (in the context of the toy problem, this means that the point will obey the motions of the vector field in a sequential manner).

The downside is, shooting methods will have extreme difficulty converging for non-linear, chaotic systems (as a small change in input will lead to a disproportional change in output, and follow a chaotic path).

(Direct) Collocation method:
Rather than optimize over the control states, the collocation method optimizes over the evaluation states, and from that optimal path, determining the controls implicitly.

The upside is this means that each point is only dependent on a limited number of previous states (making it easier to optimise)

The downside is, the dynamics of the system are an explicit constraint, and if not properly configured, can lead to solutions that violate the dynamics of the system (for a robot, this might mean the robot thinks it can walk through walls).

Interestingly, this lecture from Berkeley asserts that second order methods are much better suited to this kind of problem, as they're better at solving with multiple constraints simultaneously.
The lecturer gives some examples and specifically mentions the Gauss-Newton method. I'll continue studying the problem for now, will be back with more updates.
EDIT 2:
Sorry for the delay, I managed to figure out a how to implement the shooting method and solve my problem though. The results speak for themselves:

Of course it doesn't look like much, this system is very stable by itself and thus there really isn't much that can be done to optimize it.
But I did learn a bunch about what is required to make this work, and more broadly why we're seeing things like self driving cars, boston dynamic's amazing robots, and space X's self landing rockets pop up in recent years.
You'll recall that I mentioned solvers like CasADi were a bit of an oddity to me, as I didn't quite understand what black magic made their methods work.
Low and behold, the answer was in the title all along, Automatic Differentiation.
After reading through the implementation of the collocation method by fedja, I noticed the use of the finite differences method, which got me thinking, "What does machine learning use to determine the descent direction for the millions of parameters in modern neural networks?".
Ari Seff does an absolutely magnificent job explaining how the technology works, (those who're curious about understanding Backpropagation in ML from a more general perspective should definitely give it a watch).
Essentially, the "primatives" of your loss function (i.e. the dot product, various for loops, euclidean norms, etc) all can be broken down into a "tree" which can be traversed (either backwards or forwards) to get the derviative with respect to any of your inputs.
The loss function can even be MIMO (multi-input, multi-output), and you can even compute individual rows or columns of the jacobian or hessian, allowing for memory constraints to be factored into your optimisation algorithm.
This lead me to the JAX python package (a research project funded by Google I believe), that allows python code to be accelerated on either GPUs or TPUs using a JIT (just in time) compiler. This compiler will perform the automatic differentiation for us, allowing us to use whatever methods we like in order to optimise it (I used stochastic gradient descent for this one because it's the easiest to understand).
Hence, even a complicated loss function like the one shown above can be optimized using Auto-div (and even accelerated on modern GPU / TPU hardware).
EDIT 3:
Here is the collocation method results as well.

It was computed using the optimisation method as the shooting method, and with the same Q and R weights.
I'll put together a github project with the python code used to generate the graphs (as well as a readme to explain the intuition behind the methods, their pros and cons, and where to go from here if you want to do more with this tech). It should be out soon.
EDIT 4:
Github link as promised.
Closing comments
After completing this problem, I can see how the ML lead tech-boom, Space-X's self landing rockets and self-driving cars came into existence.
The capability gained from having a computer systematically process any complex function (i.e. compute code) and generate its gradient, jacobian and hessian is a critical point in the history of the development of the applied math / computer science fields and should be appreciated in all of its glory.
Acknowledgements
I could not have figured this out without the support of fedja, thank you so much for your insight, help and patience, you're truly a marvel to behold.

REPLY [3 votes]: I'll start with what I understood to be the main ideas of lecture 8. The stuff that is most relevant to what you are asking was near the end and the 15 minute camera blackout there certainly was quite a nuisance, but I still believe I understood the idea.
Suppose we have a discrete time dynamical system $x_{t+1}=F(t,x_t,u_t)$ ($t$ is time, $x$'s are states and $u$'s are controls) that is initially in the state $x_0$. We assume that there is a certain cost $c(t,x,u)\ge 0$ associated with being at the state $x$ and applying control $u$ at the moment $t$. Then the total cost of running this dynamical system over times from $0$ to $T$ is $C(x,u)=\sum_{t=0}^{T} c(t,x_t,u_t)$ .
Now we have no choice about $x_0$, but we can control all other states by $u$'s. Thus we want to minimize $C(x,u)$ viewed as a function of $2T+1$ free variables $x_1,\dots,x_T; u_0,\dots,u_T$ subject to the $T$ constraints $x_{t+1}-F(t,x_t,u_t)=0$.
The first key idea of the "collocation method" and of lecture 8 in general is that one can convert constraints to penalty, so instead of the rigid problem, we will consider a more flexible one
$$
C_\mu(x,u)=C(x,u)+\mu\sum_{t=0}^{T-1}|x_{t+1}-F(t,x_t,u_t)|^p\to \min
$$
where $p\ge 1$ is some power (the lecture advertises $p=1$ but when playing on the computer, I got rather strong preference for $p=2$, at least as far as the control of differential equations with weighted integral penalty is concerned)
with totally independent free variables $x_t,u_t$.
Note that the solution of the stiff problem turns the $\mu$-penalty part to $0$, so the minimum $m_{\mu}$ of the relaxed problem is never larger than the minimum $m$ of the initial stiff one. On the other hand, if $\bar x, \bar u$ is the minimizer of the relaxed problem, then we certainly have
$$
\mu\sum_{t=0}^{T-1}|\bar x_{t+1}-F(t,\bar x_t,\bar u_t)|^p\le m_\mu\le m
$$
so we can say at the very least that for all $t$, we have
$$
|\bar x_{t+1}-F(t,\bar x_t,\bar u_t)|\le (m/\mu)^{\frac 1p}
$$
(we don't know $m$, of course, but we can bound it above by just guessing some control, running it, and computing the cost).
Now we just use $\bar u$ and find the actual trajectory $x$ associated with it. The hope is that the system has some decent stability property, so $x$ will be close to $\bar x$ all the way and, therefore, we'll have $C(x,\bar u)\approx C(\bar x,\bar u)\le m_\mu\le m$, so we will have an approximate minimizer (the rigorous statement is that the value of $C(x,\bar u)$ is at most the computable quantity $C(x,\bar u)-C(\bar x,\bar u)$ above the (unknown) minimum $m$, provided, of course, that we are sure that $(\bar x,\bar u)$ is the true minimizer, which in practice is a separate issue).
The splitting property of the cost and the fact that the dynamical system constraints entangle only adjacent variables make the relaxed problem with every fixed $\mu$ much easier to handle than the original one. The second idea is, of course, the standard calculus one: the linearization.
Suppose that we have some candidate $x,u$ (I'll omit the bars from now on) for the optimizer and want to see if it can be improved by a small perturbation. Then we consider
$$
C_\mu(x+dx, u+du)
\\
=
\sum_t c(t,x_t+dx_t,u_t+du_t)+\mu\sum_t|x_{t+1}+dx_{t+1}-F(t,x_t+dx_t,u_t+du_t)|^p
\\
\approx \sum_t [c(t,x_t,u_t)+\partial_x c(t,x_t,u_t)dx_t
+ \partial_u c(t,x_t,u_t)du_t]
\\
+
\mu\sum_t|[x_{t+1}-F(t,x_t,u_t)]+[dx_{t+1}-\partial_x F(t,x_t,u_t)dx_t-\partial_uF(t,x_t,u_t)du_t]|^p\,.
$$
The $x$'s and $u$'s may be vectors, in which case we have the corresponding partial gradients rather than partial derivatives, but the key point is that all expressions in brackets are linear (or, rather, affine) functions of $dx, du$ and the $p$-th power of an absolute value of a linear function is a convex one. Thus, assuming that $c()$ and $F()$ are reasonably smooth, we can at least locally approximate the optimization problem for $C_\mu(x+dx,u+du)$ by a convex optimization problem with variables $dx,du$ subject to the additional constraint that $|dx|$ and $|du|$ are in a sufficiently small ball around the origin so that our linear approximation isn't way off in that ball.
The next part of the lecture (actually the previous one) is the general mantra that "We do have readily available good convex problem solvers that can quickly find the minimum of any convex function in a ball". I only partially agree: they certainly exist and some people have access to them. I don't know if you are one of those people, but I'm not. Fortunately there are some nice freely available books like, say, this one by S. Bubeck, but in two days I managed to implement only the ellipsoid method for general functions (which works great in dimensions 15 and lower but is almost hopelessly slow beyond that; it is however convenient because we literally do want to find a minimum in the ball a fewtimes, so the domain constraint is just semi-automatic here) and some versions of gradient descent, so I can comfortably speak only about those. Fortunately, for the model problems like your toy one, they seem to be enough for the beginning. The ellipsoid method does not care about smoothness in any way, so I used it with $p=1$, but any version of gradient descent suffers dramatically from the lack of smoothness, so my several amateur attempts to use the gradient descent techniques with $p=1$ were a total disaster though $p=2$ often works like a charm with them.
Now let us turn to differential equations. I'll consider
the problem of controlling the equation $\frac {dx}{dt}x=-x^2-u$ on $[0,1]$ with $x(0)=1$ with the cost
$$
C(x,u)=\int_0^1[Qx^2+Wu^2]\,dt
$$
with some positive reasonably nice weights $Q,W$ depending on $t$. The zero control solution is just $x(t)=\frac 1{t+1}$, so the control will be used to push it down but the non-zero control itself carries some cost.
One model case is when $W(t)=(1-t)^2$ and $Q(t)=2[3-(1-t)^3-(1-t)^6]$, in which case the minimizing pair is
$x(t)=(1-t)^2$ and $u(t)=2(1-t)-(1-t)^4$. I like this example because it is something smooth, non-linear, and the control is not monotone on the interval. It is a good simple test (IMHO) for any method you want to try to implement and it took me some time to make it work. First, we need to discretize. We split $[0,1]$ into $n$ equal intervals of length $h=\frac 1n$ and assume that $u=u_k$ on the $k$-th interval ($k=0,\dots,n-1$). The differential equation then becomes exactly solvable using the tangent-arctangent function, but I do not want to go this way because it is too special, so I'll use the first order Runge-Kutta approximation instead, which is
$$
y_k=x_k-\frac h2(x_k^2+u_k), \quad x_{k+1}=x_k-h(y_k^2+u_k)\,.
$$
So my single penalty term is programmed as $|x_{k+1}-f(x_k,u_k)|^p$ where
double f(double x, double u)
{
double y=x-h/2.0*(x*x+u)*(x*x+u);
return x-h*(y*y+u)*(y*y+u);
}

I also need the partials $fx$ and $fu$ in $x$ and $u$ respectively. By the chain rule, we get
double fx(double x, double u)
    {
    double y=x-h/2.0*(x*x+u)*(x*x+u);
    double yx=1-h*(x*x+u)*x;
    return 1-2*h*(y*y+u)*y*yx);
    }
double fu(double x, double u)
    {
    double y=x-h/2.0*(x*x+u)*(x*x+u);
    return -h*(1-y*h);
    }

The integrals are natural to approximate by the midpoint sum for $u$ and by the trapezoid sum for $x$, so dropping the irrelevant factor of $h$ and the fixed value $x(0)$, we get for our $u_k$ and $x_{k}=x(kh/n)$
$$
\int_0^1 Qx^2\,dt\asymp \sum_{k=0}^{n-1} q_{k+1}x_{k+1}^2
$$
where $q_{k}=Q(k*h)$ for $k<n$ and $q_n=\frac 12Q(1)$ and
$$
\int_0^1 Wu^2\,dt\asymp \sum_{k=0}^{n-1} w_{k}u_{k}^2
$$
where $w_k=W((k+0.5)*h)$;
That gives us the cost $C_\mu(x,u)$ as a sum of exactly the type discussed above.
Now we need to optimize. I will use the gradient descent so I'll work with the quadratic penalty $(p=2)$. We want to start with some initial guess, which in this case (and in any other case as well, unless you have a brighter idea) will be just $0$ control and the corresponding computed discrete trajectory. Eventually we want $\mu$ to become very large, but if we start with large $\mu$ immediately, the gradient will immediately throw us to some random place on the constraint surface but won't let us move along it because it is curved and we want to go by lines, so even if we choose a tangent direction and go a step $dx,du$, we will leave the surface by the amount about $|dx|^2+|dy|^2$ and will be immediately penalized for this deviation in the $\mu$-term, which will allow us only very small steps resulting in a large running time.
So now comes the fourth idea of lecture 8: start with small $\mu$ (say, $\mu=1$) and gradually move it up. How gradually? After experimenting I would say that there are two major constraints: first, you do not want to increase the cost $C_mu$ much beyond the original estimate along the uncontrolled trajectory, so you want to stay low. This gives you one bound for $\mu$ at every time. Also, you do not want to change it fast at any particular step because you want the minimum at each step to be within one iteration from the minimum at the previous step. This means that if you want to end up with ultimate $\mu $in the allotted number of iterations $I$, you'd better multiply it every time by $\mu^{1/|I|}$ or so. So my rules are these: Let $C_0$ be the cost of the original guess. Then every next $\mu$ should (a) produce the penalty term of cost at most $C0$ and (b) exceed the previous value at most $\mu^{2/|I|}$ times (so I want to be able to reach the final value in half the time allotted because the other half may be restricted by rule (a)). Thus I change the functional in line with changing the point. The lectures say something like "find the minimum with fixed $\mu$ almost precisely and then increase $\mu$ fixed number of times and start again with the old minimizer as an initial guess. I failed to achieve any reasonable time this way, so I ended up with gradual changes.
The next question about gradient decent is "how far to go". The upshot seems to be that it depends on the smoothness of the function but in this case you have a variable smoothness that changes with $\mu$. Also, if I understood that Bubeck's book correctly, the point that becomes close to the position of the minimum with guarantee is not as much the running point as a certain average of the running points. But averaging with too old points makes no sense because that time it was a wrong function. So I finally chose the following scheme (more knowledgeable people will promptly criticize it, perhaps, but it worked in my toy example).
I have already told you how I upgrade $\mu$. Now how to upgrade the running point $P=(x,u)$ and the "averaging point" $Q=(xx,uu)$ in $\mathbb R^{2n}$. Suppose that the gradient of $C_\mu(Q)$ (no misprint here!) tells you to go in the direction $V$. Then just consider the ray $P+tV$ and do a one-dimensional convex minimization on it. Then update $P$ to the (approximate, you do not need to be super-precise here, so you'd better do something fast) point of minimum $P'$ and change $Q$ to $(1-\alpha)Q+\alpha P'$ with some $\alpha\in(0,1)$ (I use $\alpha=1/n$). If this fails to produce new $P'$ (after all you take the gradient at a wrong point), just make $P$ and $Q$ the same by choosing the one that gives the smaller value at the moment and continue from there. I'm pretty sure that more competent people will offer something better, but this simple idea on this simple example produced the following picture (controls are in blue and the trajectories are in red and magenta, though they are too close to distinguish). As usual, ask as many questions as you like (though, perhaps, we'll need to switch to chat). I plan to continue when I have more to say. I guess that with what I posted, you can try to write a program for this test case yourself, but, if not yet, I'll be more than happy to provide more details.
$n=40$" />
Edit: how to choose $h$ and $\mu$ (IMHO)
I'll make an attempt to describe what I learned/figured out. I have no doubt that it is well known but so what? It doesn't seem like the experts are in hurry to join this thread :lol:  I'll try to present most things reasonably rigorously but I'll reserve the right to do a bit of handwaving.
Part 1: The problem setup.
I will consider the general first order ODE on
$$
\frac{dx}{dt}=F(t,x,u),\quad x(0)=x_0
$$
on the interval $[0,1]$ with the quadratic cost $C(x,u)=\int_0^1 [Qx^2+Wx^2]\,dt$. I shall assume that the differential equation itself is smooth and of size $1$ (so $F$ and all its partial derivatives up to the third order are bounded by $1$, the weights are squeezed between two constants (say, $1/2$ and $2$)  and the optimal trajectory and control are also bounded by $1$ functions. In this case all implicit constants in the phrases "this quantity is of order blahblahblah" will be absolute. More general situation can be, probably, considered as well, but, since we both are just learning, it makes more sense to put the emphasis on the ideas then on various explicit error formulas.
Our task will be to design the piecewise constant control discretization, so we will split $[0,1]$ into $n$ equal intervals of length $h=\frac 1n$ and assume that our control $u$ is constant on each interval. We will also denote by $x_k$ the values of the trajectory at the interval endpoints. So the meaning is that $x_k=x(k*h)$ for $k=0,\dots, n$ with $x_0$ given to us and $u(t)\equiv u_k$ on the interval $I_k=[kh,(k+1)h]$. Then we have a totally discrete setup, which is that $x_k$, $x_{k+1}$ and $u_k$ are precisely related by some condition $\Phi(x_k,x_{k+1},u_k)=0$ coming from the differential equation. These $3$ values together are more than enough to find the whole function $x(t)$ on $I_k$, thus making the integral $\int_{I_k}q(t)x(t)^2\,dt$ some complicated cost function $hJ_k(x_k,u_k,x_{k+1})$ of three variables. The integral $\int_{I_k}w(t)u(t)^2$ is just $hw_ku_k^2$ where $w_k$ is the average of the weight $w$ over $I_k$, so this part of the cost presents no problem. Thus we have a formal discrete problem
$$
h\sum_{k=0}^{n-1} w_ku_k^2+h\sum_{k=0}^{n-1} J_k(x_k,u_k)\to\min \text{ subject to } \Phi_k(x_k,x_{k+1},u_k)=0,\,k=0,\dots,n-1\,.
$$
In the collocation method we turn it into the problem of unconstrained minimization of the functional $\Xi(x,u)$ given by
$$
h^{-1}\Xi(x,u)=\sum_{k=0}^{n-1} w_ku_k^2+\sum_{k=0}^{n-1} J_k(x_k,u_k)+\mu \sum_{k=0}^{n-1} \Phi_k(x_k,x_{k+1},u_k)^2
$$
with some large parameter $\mu>0$ (I normalized everything so that the factor of $h$ can be carried out).
Part 2: Comparison to the continuous optimal control
Assuming that we can solve this discrete problem exactly (yeah, what an assumption!), we have two main parameters: step size  $h=1/n$ and the penalty strength $\mu$ to choose.
We also have the true continuous optimal control $u(t)$ and the trajectory $x(t)$, so the question becomes how close the solution of the discrete problem is to that of the continuous one depending on the choice of $h$ and $\mu$, i.e., how much precision have we lost by the very idea of restricting to the class of piecewise constant controls.
Let's start with an easy example to figure out what the answer can possibly be. I will cheat a little bit because doing it properly on a finite interval would be rather messy (though the ultimate conclusion is exactly the same), but all solutions will exhibit exponential decay, so we may sort of think of them as having finite support for all practical purposes. Consider the differential equation $\frac{dx}{dt}=-u, \ x(0)=1$ on $[0,+\infty)$ subject to the cost $\int_0^\infty[x^2+u^2]\,dt$. Here the continuous minimizer is unique and given by $x(t)=u(t)=e^{-t}$. To see it, just write any function $x(t)$ as $e^{-t}+y(t)$ with $y(0)=y(+\infty)=0$. Then, by the differential equation, $u(t)=e_{-t}-y'(t)$ and we can write
$$
\int_0^\infty[x(t)^2+u(t)^2]\,dt=2\int_{0}^\infty e^{-2t}\,dt+\int_{0}^\infty [y(t)^2+y'(t)^2]+
2\int_{0}^\infty  e^{-t}[y(t)+y'(t)]\,dt
$$
but
$$
e^{-t}[y(t)-y'(t)]=-\frac{d}{dt}[e^{-t}y(t)]
$$
is a full differential of a function with $0$ boundary values, so its integral vaniches and the rest has a clear minimum at $y\equiv 0$.
Now take the discretization. The relations $\Phi_k$ are easy here: they are just
$$
\Phi_k(x_k,x_{k+1},u_k)=x_{k+1}-x_k+hu_k=0\,.
$$
Note that normally I try to write equations normalized so that they have "size 1" in each variable, but here we don't have that option, so I chose the normalization of size 1 in $x$ and size $h$ in $u$. The exact solution is also easy to find: it is given by a piecewise linear function $x(t)$ with slope $-u_k$ on $[kh,(k+1)h]$. Then
$$
J_k(x_k,,x_{k+1},u_k)=\frac 12(x_k^2+x_{k+1}^2-\frac{h^2}6 u_k^2)\,.
$$
I leave the derivation of this formula for you. Note for now that it gives the right result for both the rectangle and the triangle and scales correctly, so it passes the trivial sanity check.
Thus we just need to minimize
$$
C(x,u)=\sum_{k=0}^{\infty}(1-\tfrac{h^2}{6})u_k^2+\sum_{k=0}^\infty x_k^2
$$
subject to
$$
x_{k+1}-x_k+hu_k=0\,.
$$
Eliminating $u_k$ and renormalizing a little bit,, we get the unconstrained minimization problem
$$
C (x)=\sum_{k=0}^{\infty}(1-\tfrac{h^2}{6})^2(x_{k+1}-x_k)^2+h^2\sum_{k=0}^\infty x_k^2\to\min\,.
$$
Now differentiating this expression with respect to $x_k$, we get the linear recursion
$$
x_{k+1}-(2+B)x_k+x_{k-1}=0
$$
where $B=B(h)=h^2(1-\frac{h^2}6)^{-1}= h^2+\frac{h^4}6+\dots$.
Its characteristic polynomial is $r^2-(2+B)r+1$. The product of the roots is $1$, so they are $e^{-H}$ and $e^H$ for some $H>0$. The Vieta equation for the sum yields
$$
e^{-H}+e^H=2+H^2+H^4/12+\dots=2+h^2+\frac{h^4}{6}+\dots\,.
$$
This means that  $H\approx h$ and
$$
H-h=\frac 1{h+H}(H^2-h^2)=\frac 1{h+H}(\tfrac 1{6}h^4-\tfrac 1{12}H^2+\dots)\approx \frac{h^3}{24}+\dots\,.
$$
Thus the points $x(kh)$ of our optimal trajectory $x(t)$ in the piecewise constant control setting lie on the curve $t\mapsto e^{-(H/h)t}\approx e^{-(1+\frac{h^2}{24})t}$, which deviates down from the true solution by about $\frac{h^2}{24}$ once we reach $t=1$.
so wewhich, after $n=\frac 1h$ steps will produce the error of order $h^2$ at the point $1$.
Now, if we relax the exact constraints to the penalty, then the problem will become that of an unconstrained minimization of
$$
C_\mu(x,u)=\sum_{k=0}^{\infty}(1-\tfrac{h^2}{6})u_k^2+\sum_{k=0}^\infty x_k^2
+\mu )=\sum_{k=0}^{\infty}(x_{k+1}-x_k+hu_k)^2\,,
$$
in which case the minimization over $u_k$ gives an equation
$$
(1-\tfrac {h^2}6)u_k+\mu h{x_{k+1}-x_k}+h^2\mu u_k=0\,,
$$
so
$$
u_k=\frac{h\mu}{1-\frac{h^2}6+\mu h^2}(x_k-x_{k+1})\,.
$$
Differentiating with respect to $x_k$, we get the equation
$$
x_k+\mu [(x_k-x_{k+1}-hu_k)+(x_k-x_{k-1}-hu_{k-1})=0
$$
so, plugging in the values of $u$, we obtain the recurrence relation
$$
x_k+\mu\frac{1-\frac{h^2}6}{{1-\frac{h^2}6+\mu h^2}}(2x_k-x_{k-1}-x_{k+1})=0\,,
$$
which can be rewritten in the same way as before but now with $B=\frac  1\mu+\frac{h^2}{1-\frac{h^2}6}$. As before, we write the roots of the corresponding characteristic equation $r^2-(2+B)r+1$ as $e^{\pm H}$ and now we get for $H$
$$
H^2+\frac{H^4}{12}+\dots=\frac 1\mu+h^2+\frac{h^4}{6}+\dots
$$
If we still want $H\approx h$ (otherwise the deviation is of order $1$), we must have $\frac 1\mu\ll h^2$ and then
$$
H-h\approx \frac{1/mu+\frac{h^4}6}{2h}\,.
$$
To make it of order $h^3$ as before, it is necessary and sufficient to take $\mu\approx h^{-4}$. Going lower would not yield the precision that the choice of $h$ can guarantee in principle, so what was the point of choosing such small $h$ then, and going higher will not improve the precision any more.
What I'll try to do later is to prove that this choice $\mu=h^{-4}$ is enough in the general situation, provided that the cost is sufficiently convex around the minimizer, more precisely, if the deviation from the optimal control by $du$ will increase the cost by about $\int_0^1 (du)^2\,dt$ for small $du$ (note that $\int_0^1(dx)^2 dt$ is always dominated by $int_0^1 (du)^2\,dt$  since $x$ is a Lipschitz function of $u$). This is definitely true  if $F$ and its derivatives are small enough but not only. Actually, the degenerate case in this problem seems rather an exception than the rule, though one can construct such examples.
Part 3. Discretization and approximation
We shall now try to figure out how to discretize the continuous problem properly. The issue is that we cannot afford to exactly solve the differential equation every time (otherwise the program will never finish) so we need to do some approximation. However, once we approximate, we technically minimize a different functional. So the question is "How much different can it be if we want its minimizer to differ from the minimizer of the original one by at most $h^2$?". I claim that in the non-degenerate situation we can afford the deviation of $h^2$ provided that it is a smooth systematic deviation, i.e., that it is given by $h^2\Psi(x,u)$ where $\Psi$ is a Lipschitz functional of $x,u$. Indeed, let $(x,u)$ be the minimizer of the true cost $C(x,u)$ and $(x+dx,u+du)$ be the minimizer of $C(x,u)+h^2\Psi(x,u)$. Then we have the inequality
$$
C(x+dx,u+du)+h^2\Psi(x+dx,u+du)\le C(x,u)+h^2\Psi(x,u)
$$
and therefore
$$
\|dx\|^2+\|du\|^2\le C(x+dx,u+du)-C(x,u)\le h^2(\Psi(x,u)-\Psi(x+dx,u+du))\le h^2(\|dx\|+\|du\|)\,,
$$
so we, indeed, can conclude that $\|dx\|,\|du\|\le h^2$ (I ignore various constants here).
This observation allows us to approximate the square of the true solution of the differential equation $x'=F(t,x,u)$ on the interval $I_k$ by just the linear function joining the endpoint values, i.e., to replace $J_k(x_k,x_{k+1},u_k)$ by $\left[x_k^2(\int_0^1 Q(kh+th)(1-t)\,dt)+x_{k+1}^2(\int_0^1 Q(kh+th)t\,dt)\right]$. Note that I don't assume that $Q$ is smooth here though for smooth weights the integrals can also be approximated using any decent quadrature formula. Thus, we shall get a simple expression of the kind $\sum_k q_kx_k^2$ instead of the hard to compute $\sum_k J_k(x_k,x_{k+1},u_k)$.
For the same reason, we want our differential equation approximation to be accurate to the order $h^3$ or better at each step, so that the systematic error in the solution will be of order $h^2$. The first order Runge-Kutta is fine, as well as the implicit Euler, but not the usual explicit Euler. I'll use the latter one here, so we'll end up with the expression of the kind
$$
C_\mu(x,u)=\sum_{k=0}^{n-1}w_k u_k^2+\sum_{k=1}^{n}q_k x_k^2
\\
+
\mu \sum_{k=0}^{n-1}[x_{k+1}-x_k-\frac h2(F(kh,x_k,u_k)+F((k+1)h,x_{k+1},u_k)]^2
$$
to minimize with the goal to reach the value $\mu=h^{-4}$ eventually.


TITLE: problems to calculate $\int_\gamma \frac{e^{iz}}{z^2}dz$
QUESTION [1 upvotes]: Some ideas to may begin to calculate $\int_\gamma \frac{e^{iz}}{z^2}dz$?(where $\gamma:[0,2\pi]\to\mathbb{C}$ def by $\gamma(t)=e^{it}$). Trying by definition I obtain an expression like $e^{ie^{it}}$ which is weird.

REPLY [2 votes]: Note that the function $$f(z) = \frac{e^{iz}}{z^2}$$ is analytic on all $\mathbb{C}/{0}$. The function has a pole of order two in $0$. The contour you're integrating on contains the pole of the function so you can use the residue theorem to evaluate your integral: $$\int_{\gamma}\frac{e^{iz}}{z^2} = 2\pi i\operatorname{Res}(f(z),0)\tag1$$
Now it's just a matter to evaluate your resiude. Being $0$ a pole of order $2$ we can evaluate it in the following manner $$\operatorname{Res}(f(z),0) = \lim_{z\rightarrow 0}\frac{d}{dz}\left(z^2\frac{e^{iz}}{z^2}\right) = \lim_{z\rightarrow 0}\frac{d}{dz}\left(e^{iz}\right) = \lim_{z\rightarrow 0}(ie^{iz}) = i$$
Or we could evaluate it by the Laurent series around $0$ of the function, which can be easily found by the Taylor series of $e^{iz}$ $$e^{iz} = \sum_{n=0}^\infty \frac{(iz)^n}{n!} = 1+iz-\frac{z^2}{2}-\frac{iz^3}{6}+O(z^4)$$ dividing it by $z^2$ we get the Laurent series of $f(z)$ $$\frac{e^{iz}}{z^2} = \sum_{n=0}^\infty i^n\frac{z^{n-2}}{n!} = \frac{1}{z^2}+\color{red}{i}\frac{1}{z}-{1\over 2}-\cdots$$
the $\color{red}{\text{red}}$ coloured coefficient is the residue at $z=0$
In both cases we found out that the residue evaluates to $i$ so plugging it back into $(1)$ we get the value of the integral $$\int_{\gamma}\frac{e^{iz}}{z^2} = 2\pi i\operatorname{Res}(f(z),0) =  2\pi i\color{red}{i} = -2\pi$$


TITLE: Is joint variation a plane?
QUESTION [1 upvotes]: This is probably a foolish question, but I am going over some old math problems and started thinking about joint variation. My question is:
Can joint variation $y = kxz$ be graphed as plane in $3D$ space? Such that if $k$ remains constant, and $x$ and $z$ vary, will $(x, y, z)$ make a plane? It seems intuitively like it will... but I was never made to graph direct relationships that way.
Aside: Is there any application to this you have encountered? I googled and didn't get any straight answers but did see some snippets about virtual reality...

REPLY [1 votes]: I randomized some $(x,z)$ pairs, calculated $y = xz$ for each pair and then made a plot, but it is too big for a comment.

We should not be able to rotate a plane to have it look like this so it must be twisted.
In fact, $y=kxz$ or $kxz-y=0$ is example of one of the lowest degrees of an algebraic variety: a set of equations of multivariate polynomials. In our case we have just 1 equation and the degree is only 2, since the highest sum of exponent for any term is 2 ($kx^1z^1$ and $1+1=2$).
These algebraic varieties are often non-linear differentiable manifolds of some dimensionality and have lots of applications in science and engineering.
Both the fields of algebraic geometry and differential geometry deals with these things.


TITLE: Concrete Mathematics - 2.5 Method 5 Summation of $k^2$
QUESTION [1 upvotes]: $$\sum_{k=1}^n k^2  =  \sum_{j=1}^n \sum_{k=j}^n k$$

This equation was given in book Concrete Mathematics : A Foundation for Computer Science Page 46 under Method 5: Expand and contract.
In book author jumped from single sum to double sum but how he derived the double sum(using summation properties) I am unable to get it.
Explain in detail please.

REPLY [1 votes]: One way to look at it is like this: note that $k=1+1+\cdots+1$  ($k$ times),
so $\displaystyle k=\sum_{j=1}^k 1$, and then
$\displaystyle \sum_{k=1}^n k^2 = \sum_{k=1}^n kk=\sum_{k=1}^n\sum_{j=1}^k k
=\sum_{j=1}^n\sum_{k=j}^n k$
where the last step is the standard switching of the order of summation.


TITLE: Efficient algorithm for SDP relaxation of max-cut
QUESTION [0 upvotes]: Given a symmetric $n\times n$ matrix $A$, I'm interested in the class of SDP problems that can be written canonically as:
$$
\begin{align}
\text{minimize} \quad &-\text{tr}(AX) \\
\text{subject to} \quad &\forall i, \, X_{ii} = 1 \\
 & X \succeq 0.
\end{align}
$$
I understand that this is a convex problem so an efficeint algorithm exists, but I want to write my own code to solve this problem for pedagogical sake, and also to better interface with the current code I have.
Therefore, I'm wondering what is the best known algorithm for solving this class of SDP problem, and is there a documentation containing some form of pseudocode that I can refer to.

REPLY [1 votes]: Primal-dual interior point methods can solve this formulation efficiently and there are multiple open source codes available to do so.  CSDP can solve it well and is documented here.  If you use that paper, I'd ignore the operator $B$ to make things simpler.  Alternatively, SDPT3 is also an excellent code and is documented here.  That said, from a pedagogical point of view, these papers are a terrible place to start.  In my opinion, a much better path is to start from Wright's book Primal-Dual Interior-Point Methods, which covers the algorithm for linear, not semidefinite, cones.  Really, most of the algorithm is the same, but the primal and dual variables are no longer vectors, but matrices.  In Wright's book, this means that $X$ and $S$ are matrices and no longer $Diag(x)$ and $Diag(s)$ respectively.  This also adds the complication of symmetrization because the optimization steps will in general not be symmetric, but the CSDP and SDPT3 papers will cover what to do in this situation.
To be sure, I am aware that there is continued research on SDP max-cut relaxations and most likely algorithms, so it's possible that there is better than what I've suggested above.  That said, those algorithms are really good and are a reasonable place to start.


text:
\begin{document}
\maketitle

\begin{abstract}  We discuss the role of weakly normal formulas in the theory of thorn forking, as part of a commentary on the paper \cite{Ealy-Onshuus}.  We also give a  counterexample to Corollary 4.2 from that paper, and in the process discuss ``theories of selectors".
\end{abstract}

\section{Introduction}

This work comes out of our reading of the paper \cite{Ealy-Onshuus}. A superficial look  at \cite{Ealy-Onshuus} may give the impression (as it gave to the authors) that the results in that paper shed some light on the stable forking conjecture.
We point out that it is a stronger version of stability, {\em weak normality}, which is relevant, more or less by definition, although there is still no real connection with the stable forking conjecture. We also point out a counterexample to Corollary 4.2 of  \cite{Ealy-Onshuus} which claims that strong dividing of $\phi(x,c)$ can be witnessed by parameters from $dcl(c)$.

We will work as usual in a saturated model ${\bar M} = {\bar M}^{eq}$ of a complete first order theory $T$ in language $L$. Our basic model-theoretic notation  is as in \cite{Pillay-book}.   Definability means with parameters. Remember that a definable set $X$  is said to be ``almost over $A$" iff $X$ has finitely many images under $Aut({\bar M}/A)$  iff the canonical parameter of $X$ is in $acl(A)$.  We typically identify a set $A$ of parameters with its definable closure.

We will be assuming a basic knowledge of notions from stability such as forking, dividing, and canonical bases of stationary types. In addition to \cite{Pillay-book} one could refer to \cite{Casanovas} for example.

Thorn forking was introduced by Onshuus \cite{Onshuus} as an account of a most general theory of independence, which subsumes nonforking in stable theories, and also in simple theories assuming elimination of hyperimaginaries, but also includes ``dimension-independence" in $o$-minimal theories.  A very nice account and explanation of thorn forking appears in \cite{Adler}. The stable forking conjecture says that stable formulas are responsible for forking in simple theories.  Here by a stable formula we mean an $L$-formula $\phi(x,y)$ where the free variables of $\phi$ are partitioned into $x,y$ and $\phi(x,y)$ does not have the order property.  And to say that stable formulas are responsible for forking means that whenever $p(x)\in S(B)$ forks over $C\subseteq B$,  then there is  stable $L$-formula $\phi(x,y)$ and an instance $\phi(x,b)$ of $\phi(x,y)$ which is in $p(x)$ and such that $\phi(x,b)$ forks over $C$.

In both ordinary forking and thorn forking one starts with a notion of (thorn) dividing, and then say that $tp(a/B)$ does not (thorn) fork over $C$ if $tp(a/B)$ has an extension $p'(x)$ over a saturated model say, such that no formula in $p(x)$ (thorn) divides over $C$.   Dividing is well-known.  But thorn dividing involves some additional parameters: $\phi(x,b)$ is said to thorn divide over $C$, if there is some set $C'$ of parameters which contains $C$ such that $\phi(x,b)$ ``strongly divides" over $C'$ meaning that the family of $C'$-conjugates of $\phi(x,b)$ is $k$-inconsistent for some $k$, and $\phi(x,b)$ is not almost over $C'$.
Ealy and Onshuus introduce a notion of ``stably dividing with parameters", and  say that we can choose $\phi(x,y)$ to be stable in the language obtained by adding constants for the additional parameters in $C'$ and they call this $\phi(x,b)$ stably dividing, with parameters, over $C$ (even though $C$ has disappeared from the picture).  So the set-up is a bit confusing. Our aim is to try to unravel what is going on,  and in so far as stability is involved, to point out that it is so-called weakly normal formulas which are responsible.

\section{Weak normality}
As in Chapter 4 of \cite{Pillay-book} we call a definable (with parameters) set $X$ {\em weakly normal} if $X$ is nonempty, and  for any $a\in X$ there are only finitely many $Aut({\bar M})$ conjugates of $X$ which contain $a$.   When $X$ is already defined over $acl(\emptyset)$ this condition trivially holds.
If $e$ is the (or a) canonical parameter for $X$ then weak normality  of $X$ means that for all $a\in X$, $e\in acl(a)$. The condition that $X$ is not over $acl(\emptyset)$ means that $e\notin acl(\emptyset)$.

We can relativise weak normality to any (small) set $A$ of parameters:  $X$ is {\em weakly normal relative to $A$} if $X$ is weakly normal in the expansion of ${\bar M}$ by adding constants for elements of $A$, namely $e\in acl(A,a)$ for any $a\in X$. And the ``nontriviality condition", over $A$, means that $e\notin acl(A)$. By compactness we obtain the following characterization of weak normality related to the notion of $k$-dividing.

\begin{Remark}\label{remark:k.many.weakly.normal}
Assume that $X$ is a definable set.
The definable set  $X$ is weakly normal relative to a set $C$ if and only if
the number of distinct $C$-conjugates of $X$ is finite or
there exists a natural number $k>0$ such that
for every $k$-many distinct $C$-conjugates of $X$, the intersection of these $C$-conjugates is empty.
\end{Remark}

\begin{Remark}\label{remark:old.2.1}
Let $X$ be a definable set which is weakly normal relative to a set $C$. Then $X$ divides over $C$ iff $X$ forks over $C$ iff $X$ is not almost over $C$.
\end{Remark}
\begin{proof} Clearly dividing over $C$ implies forking over $C$ implies not being almost over $C$  (for any definable set $X$, weakly normal relative to   $C$ or not).  Conversely suppose that $X$ is weakly normal relative to $X$ and that $X$ is not almost over $C$.
Then by Remark \ref{remark:k.many.weakly.normal}, the set $X$ $k$-divides over $C$ for some $k$.

\end{proof}

\begin{Remark}\label{remark:old.2.2}
 Suppose we are given tuple $a$ and sets $C\subseteq B$. Then the following are equivalent:
\newline
(i) there is $b$ in $B$ which is in $acl(a,C)\setminus acl(C)$.
\newline
(ii) For some weakly normal relative to $C$, definable set $X$ in $tp(a/B)$, $X$ is not almost over $C$.
\end{Remark}
\begin{proof} Let $b\in B$ be as in (i).  We can then  find an $L$-formula  $\phi(x,y,z)$, and $c$ in $C$ such that  $\models\phi(a,b,c)$ and $\phi(x,y,z)$ implies $(\exists^{=n}y')\,\phi(x,y',z)$ for some $n>0$.

Let $X$ be the set defined by $\phi(x,b,c)$.  So $X$ is in $tp(a/B)$.
\newline
It is immediate from the properties of $\phi(x,y,z)$ that $X$ is weakly normal relative to $C$. We have to check that $X$ is not almost over $C$.
Suppose for a contradiction that $X$ is almost over $C$.
As $b\not\in acl(C)$, choose an infinite sequence $f_i\in\aut(\bar{M}/C)$, $i<\omega$, such that all $f_i(b)$'s are distinct.
Without loss of generality, we have $f_i(X)=f_1(X)\ni f_1(a)$ for infinitely many $i<\omega$ and
so $\models\phi(f_1(a),f_i(b),c)$ for infinitely many $i<\omega$ which contradicts the choice of $\phi$.

\end{proof}

Finally recall that if $X$ is a definable set which is weakly normal relative to a set $C$, and $X$ is defined by $\phi(x,e)$ where $e$ is the canonical paramer of $X$, and $\phi(x,z)$ is an $L$-formula, then the formula $\phi(x,z)$ is stable in the expansion of $T$ by adding constants for elements of $C$.  A weakly normal definable set is also a special case of an instance of an equation, in the sense of Srour \cite{Srour}.

\section{Thorn forking}
We point out the following which refines Theorems 3.3 and 4.1 in \cite{Ealy-Onshuus}:
\begin{Proposition} \label{proposition:thorn.weakly.normal}
Given tuple $a$ and sets $C\subseteq B$, $tp(a/B)$ does not thorn fork over $C$ iff there is some extension of $tp(a/B)$ to a complete type $p(x)$  over some $|C|^{+}$-saturated model $M$, such that whenever $X$ is a definable set in $p(x)$ and $C\subseteq C'\subseteq M$ and $X$ is weakly normal relative to $C'$ then $X$ is almost over $C'$ (equivalently $X$ does not divide/fork over $C'$).
\end{Proposition}

We recall the notion of thorn forking appearing in Onshuus' paper \cite{Onshuus}:  $tp(a/B)$ does not thorn fork over $C\subseteq B$ if for any ${\hat B}\supseteq B$, $tp(a/B)$ has an extension to some $tp(a'/{\hat B})$ which does not thorn divide over $C$, namely no formula $\phi(x,b)\in tp(a'/{\hat B})$ thorn divides over $C$.  And $\phi(x,b)$ thorn divides over $C$ if there is some tuple $d$ of parameters such that $b\notin acl(C,d)$, and the set of all $(C,d)$-conjugates of $\phi(x,b)$ is  $k$- inconsistent for some $k$ (i.e. $\phi(x,b)$ strongly divides over $C,d$ in the language of \cite{Onshuus}).

It is easy to first replace the arbitrary ${\hat B}\supseteq B$, by some fixed $|C|^{+}$-saturated model $M\supseteq B$, and, using the saturation of $M$, allowing $d$ to be chosen from $M$,  Namely we obtain: $tp(a/B)$ does not thorn fork over $C$, if it has an extension $p(x)$ over some $|C|^{+}$-saturated model $M\supseteq B$, such that there do not exist a formula $\phi(x,b)\in p(x)$ and some $C\subseteq C'\subseteq M$ such that $b\notin acl(C')$ and the set of $C'$-conjugates of $\phi(x,b)$ is $k$-inconsistent for some $k$.  Modulo Remarks \ref{remark:old.2.1} and \ref{remark:old.2.2} this is precisely the statement of Proposition \ref{proposition:thorn.weakly.normal}.   Our ``proof" above of \ref{proposition:thorn.weakly.normal} is roughly the content of Proposition 4.7 in \cite{Adler}.

\vspace{5mm}
\noindent
Let us comment on why Proposition \ref{proposition:thorn.weakly.normal} includes Theorem 4.1 of \cite{Ealy-Onshuus}.  The latter theorem of Ealy-Onshuus says that if one redefines thorn forking by redefining a formula $\phi(x,b)$ to thorn divide over $C$ if $\phi(x,b)$ strongly divides over $(C,d)$ for some $d\in dcl(A,b)$, then this new notion of thorn forking agrees with the original
notion.   This is precisely the preceding paragraph, which says that $tp(a/B)$ does not thorn fork in the original sense, iff
$tp(a/B)$ has an extension $p(x)$ over the saturated model $M$ , such that no formula in $p(x)$ thorn divides over $C$ in the new sense (as we can add to the formula any dummy parameters from $M$ that one wishes).

\vspace{10mm}
\noindent
Finally we discuss Corollary 4.2 of \cite{Ealy-Onshuus}.  This states that if $\phi(x,b)$ thorn divides over $C$, then a tuple $d$ such that $\phi(x,b)$ strongly divides over $C,d$ can be found in $dcl(C,b)$.

This is supposed to follow from  Theorem 4.1 of \cite{Ealy-Onshuus} (which was discussed earlier).   In fact the role of $C$ is also problematic.  Remember that $\phi(x,b)$ is defined to thorn divide over $C$ if there is $C'\supseteq C$ such that $\phi(x,b)$ strongly divides over $C'$  ($b\notin acl(C')$ and the set of $C'$-conjugates of $\phi(x,b)$ is $k$-inconsistent for some $k$.  But then, if $\phi(x,b)$ thorn divides over $C$, it also thorn divides over $\emptyset$, and so Corollary 4.2 of \cite{Ealy-Onshuus} would yield that we can find $d\in dcl(b)$ such that $\phi(x,b)$ strongly divides over $d$.

Translating into the weakly normal language we obtain:
\begin{Question} Let $X$ be a definable set with canonical parameter $e$. Suppose that for some set of parameters $C$, $X$ is weakly normal, relative to $C$, and $e\notin acl(C)$. Can one find such a set of parameters $C\subseteq dcl(e)$?
\end{Question}

We give a couple of examples, related to  Question 3.2, and its context.
We start with an example giving basically a positive answer for strongly minimal theories.  We will work with Morley rank which corresponds to algebraic independence dimension for tuples in  strongly minimal sets.

\begin{Lemma} Suppose $T$ is a $1$-sorted strongly minimal theory with elimination of imaginaries. Let $p({\bar x})$ be a stationary complete type over a tuple ${\bar e}$ where ${\bar e}$ is the canonical base of $p$. Then there is a formula (definable set) $X$ in $p$ with canonical parameter $\bar{e}$ and some ${\bar c}\in dcl({\bar e})$ such that ${\bar e}\notin acl({\bar c})$ and $X$ is weakly normal relative to ${\bar c}$.
\end{Lemma}
\begin{proof} Let ${\bar a}$ realize $p$, and suppose that $RM(p) = n$ and $RM(tp({\bar a}/\emptyset)) = n+k$ where $k\geq 0$.
\newline
{\em Claim.}  $RM(tp({\bar e}/\emptyset)) \geq k$.
\newline
{\em Proof.}  Otherwise, by subadditivity, $RM(tp({\bar a},{\bar e}/\emptyset) < n+k$, a contradiction.

\vspace{2mm}
\noindent
Now by elimination of imaginaries (or our notation) ${\bar e}$ is a tuple from the strongly minimal home sort, with $dim({\bar e}) = r\geq k$  (some $r$).
Hence for some subtuple ${\bar c}$ of ${\bar e}$, $dim({\bar c}) = r-k$ whereby $dim({\bar e}/{\bar c}) = k$, namely $RM(tp({\bar e}/{\bar c})) = k$.
Now, by subadditivity again we get that $RM(tp({\bar a},{\bar e}/{\bar c})) = n+k$, hence equals $RM(tp({\bar a}/{\bar c}))$, so by subadditivity again ${\bar e}\in acl({\bar a}, {\bar c})$.  As ${\bar c}$ is a subtuple of ${\bar e}$, we can (by compactness) find a formula $\phi({\bar x})$ in $p = tp({\bar a}/{\bar e})$, such that for any ${\bar a}'$ realizing $\phi({\bar x})$, ${\bar e}\in acl({\bar a}', {\bar c})$.
\end{proof}

The next example is where both the hypothesis and conclusion of Question 3.2 fail, but the hypothesis``almost" holds.

We will take as $T$ the theory of the free pseudoplane.  See  Example 6.1 in Chapter 4 of \cite{Pillay-book} as well as Section 2 of \cite{Baudisch-Pillay} for some more details.  This is also called the infinite forest in \cite{Adler}.  The language consists of a single binary relation $I$, and the axioms for $T$ say that $I$ is symmetric, irreflexive, for each $a$ there are infinitely $b$ such that $I(a,b)$, and there are no ``loops", namely for each $n\geq 3$ there do not exist $a_{0}, a_{1},...., a_{n}$ such that $I(a_{i},a_{i+1})$ (for all $i=0,..,n-1$), the $a_{i}$ for $i\leq n-1$ are distinct, and $a_{0} = a_{n}$.
$T$ is complete, and $\omega$-stable, where the Morley rank of the home sort is $\omega$.  A saturated model of $T$ consists of infinitely many connected components. In \cite{Baudisch-Pillay} it is pointed out that $T$ has weak elimination of imaginaries.

Fix a (saturated) model ${\bar M}$, let $a\in {\bar M}$, then the formula $I(x,a)$ isolates a complete type $p_{a}(x)$ over $a$.  $a$ is the canonical base of $p_{a}$ as well as the canonical parameter of the formula $I(x,a)$.

\begin{Lemma} (i) $I(x,a)$ is not weakly normal (i.e. relative to $\emptyset$).
\newline
(ii) There is no $c\in {\bar M^{eq}}$ such that $a\notin acl(c)$ and $I(x,a)$ is weakly normal relative to $c$.
\end{Lemma}
\begin{proof} (i) Fixing $b$ such that $I(a,b)$, $I(b,y)$ is infinite and isolates a complete type over $b$ (as mentioned above).  So $a\notin acl(b)$.
\newline
(ii)  Choose $c\in {\bar M}^{eq}$ such that $a\notin acl(c)$ and we want to show that $I(x,a)$ is not weakly normal relative to $c$.  By the weak elimination of imaginaries we may assume that $c$ is a real tuple.  The assumption that $a\notin acl(c)$ implies that there are no two elements $c_{1}, c_{2}$ from the tuple $c$ such that the unique shortest path from $c_{1}$ to $c_{2}$ goes via $a$. It follows that there is (unique) $b$ such that $I(a,b)$ and such that all elements of $c$ are on (shortest) paths from $a$ which go through $b$ (or in different components of the model).
Now choosing this unique $b$ realizing $I(x,a)$, we see that $a\notin acl(b,c)$, because there are infinitely many $a'$ such that $I(b,a')$ and $a'$ is not on a path from $b$ to any element of $c$, and all such $a'$ have the same type over $b,c$.
\end{proof}

\begin{Lemma}\label{lemma:pseudoplane2} Let $I(b,a)$. Let $\phi(x)$ be the formula $I(x,a)\wedge x\neq b$. Then for any $b'$ realizing $\phi(x)$ we have that $a\in acl(b,b')$.
\end{Lemma}
\begin{proof} $a$ is in the unique shortest path between $b$ and $b'$.
\end{proof}

However note that the canonical parameter of the formula $\phi(x)$ from Lemma \ref{lemma:pseudoplane2} is $(a,b)$ and the lemma says that $\phi(x)$ is weakly normal with respect to $b$.

\section{Theories with selectors}
In this section we give a family of  negative answers to Question 3.2 (so counterexamples to 4.2 of \cite{Ealy-Onshuus}).
It is a simple construction (maybe known?) which for any theory $T$, produces a ``mild expansion" (in the sense of also adding a new sort) $T^{S}$, which for any infinite definable set $X$ in $T$ with canonical parameter $e$, yields some $d$ not in $dcl(e)$ such that $X$ is not almost over $d$ and $X$ is weakly normal relative to $d$ in $T^{S}$.  The construction is related to but distinct from  the {\em generic variations} of  \cite{Baudisch}.

We fix a complete theory $T$ in a language $L$, which we assume, for simplicity, to be relational.  There is no harm in assuming $T$ to be $1$-sorted.
We will define a language $L^{+}$ and complete $L^{+}$-theory $T^{+}$, and a language $L^{S}$ and complete $L^{S}$ theory $T^{S}$, all depending on $T$, and with $L^{+}\subseteq L^{S}$.

Roughly speaking $T^{+}$ is theory of a set equipped with an equivalence relation $E$ with infinitely many classes, such that each $E$-class  has structure making it a model of $T$, this is uniform across the $E$-classes, and moreover any interaction (on the level of language $L$) between distinct $E$-classes is forbidden.
Model-theoreticaly $T^{+}$ is quite transparent, but one should give a definite formalism, which we do now.

We discuss the language $L^{+}$ and theory $T^{+}$ simultaneously, sometimes mixing up syntax and semantics.  There will be two sorts in $L^{+}$, a sort $P$ equipped with an equivalence relation $E$, and the second sort is just $P/E$, and we have the canonical function $f_{E}:P \to P/E$, in the language $L^{+}$.

For $a$ of sort $P$, $a/E$ denotes the equivalence class of $a$ as an element of the sort $P/E$. And $[a]_{E}$ denotes the equivalence class of $a$ as a subset of the sort $P$.

For each $n$-ary relation symbol $R$ of the language $L$, we will have an $n+1$-ary relation symbol
$R^{+}(z,x_{1},..,x_{n})$ where $z$ is a variable of sort $P/E$ and $x_{1},..,x_{n}$ variables of sort $P$.  In addition to the equality symbols on the two sorts, this is the language $L^{+}$. The axioms of $T^{+}$ say that $f_{E}$ is what it should be, that for any $z\in P/E$, $R^{+}(z, x_{1},..,x_{n})$ implies that the $x_{i}$ are in the equivalence class determined by $z$, and that each $E$-class $C$ is a model of $T$. Where the $E$-class $[a]_{E}$ is viewed as an $L$-structure by defining $R(b_{1},..,b_{n})$ to hold in $C$ iff  $R^{+}(a/E,b_{1},..,b_{n})$ holds in the ambient $L^{+}$-structure.

To summarise $L^{+}$ is the language with sorts $P$ and $P/E$, and symbols $E$, $f_{E}$ and the  $R^{+}$ for $R\in L$.
\begin{Lemma} (i) $T^{+}$ is complete,
\newline
(ii)  Assuming that $T$ has quantifier elimination (i.e. is Morleyized), then $T^{+}$ has quantifier elimination too.
\newline
(iii) $P/E$ is an indiscernible set in $T^{+}$.
\end{Lemma}
\begin{proof} (i) is clear as a model of $T^{+}$ is just a family of models of $T$ indexed by $P/E$, and any two saturated models will be isomorphic.
\newline
(ii) follows by doing back-and-forth between $\omega$-saturated models.

\end{proof}

Of course we can assume that $T$ has QE, so we obtain complete understanding of definability in models of $T^{+}$.
Note that if $M$ is a saturated model of $T$  (say $\kappa$-saturated and strongly $\kappa$-homogeneous), then  the model $M^{+}$ of $T^{+}$ where $E$ has $\kappa$-many classes and each class is isomorphic (as an $L$-structure) to $M$, is also saturated.  We write $P(M^{+})$ and $(P/E)(M^{+})$ for the corresponding sorts in  $M^{+}$.

One immediate observation which will be useful for us later is:

\begin{Lemma} Let $X\subset P(M^{+})$ be definable in $M^{+}$ over $a$ from $P(M^{+})$. Let $C$ be the $E$-class (as a subset of $P(M^{+})$ of $a$. Then $X = X_{1}\cup X_{2}$ where $X_{1}$ is a subset of $C$ definable over $a$ in $L$, and $X_{2}$ is the union of a  family of uniformly $\emptyset$-definable (in $L$) subsets (maybe empty) of the classes other than $C$. Moreover if $a$ is the canonical parameter of $X_{1}$ in $C$ (as a model of $T$), then $a$ is the canonical parameter of $X$ in $T^{+}$.
\end{Lemma}

We now introduce the language $L^{S}$ and theory $T^{S}$.  $L^{S}$ is $L^{+}$ together with a new sort $Q$ and function symbol $\pi: P/E \times Q \to P$.
$T^{S}$ can be described in two equivalent ways. First take any model $M$ of $T$ and expand $M^{+}$ to an $L^{S}$ structure $M^{S}$ by letting the sort $Q(M^{S})$ consists of all ``selectors"  from the equivalence classes, and $\pi(M^{S})$ the obvious thing.  Namely, $Q(M^{S})$ is the collection of all choice functions or sections $s$ corresponding to the map $f_{E}:P\to P/E$ and $\pi(z,s) = s(z)$.

Alternatively $T^{S}$ is the $L^{S}$ expanding $T^{+}$ which says: for $y_{1}, y_{2}\in Q$, $y_{1} = y_{2}$ iff  $\pi(z,y_{1}) = \pi(z,y_{2})$ for all $z$, together with the axiom which says that for all $d\in Q$, $z\in P/E$ and $a\in P$ in the class named by $z$, there is $d'\in Q$ such that $\pi(z,d') = a$ and $\pi(z',d') = \pi(z',d)$ for all $z' \neq z$.

Iterating the last axiom, it implies that for any $d$ in $Q$ and finitely many $E$-classes we can find $d'\in Q$ such that the value of $\pi(-,d')$ on these finitely many classes is anything one wants, but for the other classes is the same as the value of $\pi(-,d)$.  (And in a $\kappa$-saturated model we can do it for $<\kappa$ many equivalence classes instead of only finitely many.)

\begin{Lemma}  Let $N$ be a model of $T^{+}$ and ${\bar a}$, ${\bar b}$ tuples of the same length (and in appropriate sorts) from $N$ such that $tp_{N}({\bar a}) = tp_{N}({\bar b})$.  Let $N'$ be an expansion of $N$ to a model of $T^{S}$. Then $tp_{N'}({\bar a}) = tp_{N'}({\bar b})$.
\end{Lemma}
\begin{proof} We will prove the special case where ${\bar a}$ (and ${\bar b}$) are singletons from $P$.  The general case is similar.
We may assume that everybody is saturated.
First suppose that $a$ and $b$ are in the same $E$-class $C$ say. So viewing $C$ as a model of $T$, there is an automorphism $f$ of $C$ taking $a$ to $b$.  Then $f$ extends to an automorphism of $N$ by fixing $P/E$ pointwise and fixing pointwise every $E$-class $C'\subseteq P$ other than $C$.
We will call this automorphism $f$ too. We now want to extend $f$ to an automorphism $f'$ of $N'$ by defining the action on $Q$.   For each $d\in Q$, let $f'(d)$ be the unique element $d'\in Q$ such that $\pi(a/E,d') = f(\pi(a/E),d)$ (where $d'$ is given to us by the axiom above).  It is then easy to see that $f'$ is a bijection of $Q$ with itself and is an automorphism of  $N'$. So $a$ and $b$ have the same type in $N'$.

Now suppose that $a$ and $b$ are in different $E$ classes. The quantifier elimination result earlier (for $T^{+}$ implies that not only do $a$ and $b$ have the same types in $N$ but $(a,b)$ and $(b,a)$ have the same types in $N$. So there is
an automorphism $f$  of $N$ taking $(a,b)$ to $(b,a)$  (so also switching $a/E$ and $b/E$) and fixing pointwise all other elements of $P/E$ and all $E$-classes $C$' other than $[a]_{E}$ and $[b]_{E}$.  As in the the first paragraph, $f$ extends to an automorphism $f'$ of $N'$. So in this case $(a,b)$ and $(b,a)$ have the same type in $N'$.
\end{proof}

It follows that:
\begin{Corollary} The (relativised) reduct $T^{+}$ of $T$ is ``weakly stable embedded" in the sense that for subsets of Cartesian products of the $P/E$ and $P$, \\$\emptyset$-definability in $T^{+}$ coincides with $\emptyset$-definability in $T^{S}$.   In particular the sort $P/E$ is an indiscernible set in the theory $T^{S}$.
\end{Corollary}

On the other hand $T^{+}$ is not ``stably embedded" in $T^{S}$, as  there will be sets in the $T^{+}$-sorts which are definable with parameters in the $Q$ sorts but not in the $T^{+}$ sorts.  In fact:

\begin{Proposition} $T^{S}$ has both the strict order property and the independence property, all witnessed on the $P/E$ sort (which remember is an indiscernible set in $T^{+}$).
\end{Proposition}
\begin{proof}  Let $N$ be any model of $T^{S}$  (saturated if one wishes), and fix $d\in Q(N)$ which gives a section $\pi(-,d)$ from $(P/E)(N)$ to $P(N)$.  For any finite subset $S$ of $P/E$, we can (by the axioms for example) find an element $d_{S}\in Q(N)$ such that  $\pi(z,d) = \pi(z,d_{S})$ precisely for those $z\notin S$.  Namely finite subsets of $S$ are uniformly definable, giving both the strict order property and the independence property.
\end{proof}

We now point out a general result which will be useful in our (counter) examples. Note that by 4.4 there is a unique $1$-type of an element of $P/E$ in $T^{S}$.

\begin{Proposition} Suppose that there is a unique $1$-type (over $\emptyset$) in $T$.  Then (working in a saturated model of $T^{S}$), for every $a\in P$, there is $d\in Q$ such that $\pi(a/E, d) = a$, $a\notin acl(d)$ and $d\notin acl(a)$.
\end{Proposition}
\begin{proof} It is enough to work in a model $M^{S}$ as described above where $M$ is a $\kappa$-saturated, strongly $\kappa$-homogeneous model of $T$, $M^{+}$ is the model of $T^{+}$ consistig of $\kappa$ many ``copies" of $M$, and $M^{S}$ is the expansion of $M^{+}$ to a model of $T^{S}$ by adding all selectors (or sections) as $Q(M^{S})$.
First, as there are infinitely many $d\in Q(M^{S})$ such that $\pi(a/E, d) = a$ we may choose such $d\notin acl(a)$.
Let $e = a/E$. Let $e'\neq e$ in $(P/E)(M^{S})$. And let  $b = \pi(e',d)$.  Viewing $[a]_{E}$ and $[b]_{E}$ as models of $T
$ there is an isomorphism $f$ between them taking $a$ to $b$ (by our assumptions).  Then $f\cup f^{-1}$ extends to an automorphism of $M^{+}$ fixing all $E$-classes pointwise, other than $[a]_{E}$ and $[b]_{E}$.  This induces a bijection from $Q(M^{S})$ to itself which fixes $d$, hence an automorphism $f'$ of $M^{S}$. Hence $a$ and $b$ have the same type over $d$ in $M^{S}$. As $e'\neq e$ was arbitrary this shows that $a\notin acl(d)$ in $M^{S}$.
\end{proof}

The results of this section yield many negative answers to Question 3.2. We will mention two of them.
Let us begin with $T = DLO$ the theory of dense linear orderings without endpoints in the language $\{<\}$. The theory $T$ is complete with quantifier elimination and a unique $1$-type over $\emptyset$. $T$ also has elimination of imaginaries. Let $M$ be a (saturated) model of $T$ and $a\in M$ and consider the formula $x>a$ and the set $X$ it defines in $M$. Then $X$ is not weakly normal. Moreover, the only element in $dcl(a)$ is $a$, hence $X$ is not weakly normal relative to any set $C$ such that $X$ is not almost over $C$.

Now let $M^{S}$ be the model of $T^{S}$ built from $M$ as above. Fix an $E$-class $C\subset P(M^{S})$ which we identify with $M$, and let $X$ be as above, now considered as a definable set in $M^{S}$.

\begin{Proposition}  Working in $M^{S}\models T^{S}$, and $X$ as above:
\newline
The canonical parameter of $X$ is $a$. For no $e\in dcl^{eq}(a)$ do we have that $X$ is weakly normal relative to $e$ and $a\notin  acl(e)$. But there is $d\in M^{S}$ such that $X$ is weakly normal relative to $d$ and $a\notin acl(d)$.
\end{Proposition}
\begin{proof} First, by Proposition 4.6 we find $d\in Q$ such that $\pi(a/E,d) = a$ and $a\notin acl(d)$ and $d\notin acl(a)$. In particular for any $b\in X$, $a\in dcl(b,d)$. Hence $X$ is weakly normal relative to $d$, and $a\notin acl(d)$. (All in the sense of $T^{S}$.)
Now we want to check that $a$ is the canonical parameter of $X$ in the sense of $T^{S}$.  This follows quickly from the fact that $T^{+}$ is weakly stably embedded in $T^{S}$ and that $a$ is the canonical paramete of $X$ in $T$.

Now, we want to check that: for no $e\in dcl^{eq}(a)$ do we have that $X$ is weakly normal relative to $e$ and $a\notin  acl(e)$.  So suppose $e\in dcl^{eq}(a)$ in $M^{S}$, so $h(a) = e$ for some $\emptyset$-definable function $h$ in $(M^{S})^{eq}$. But then $h(x) = h(y)$ is an $L^{S}$-formula $\phi(x,y)$ on the sort $P$. And clearly the canonical parameter of the formula $\phi(x,a)$ is interdefinable with $e$.  We will now use Corollary 4.4 and Lemma 4.2. First by Corollary 4.4, $\phi(x,a)$ is defined in $M^{+}$ over $a$ by a formula which we still call $\phi(x,a)$, and moreover the canonical parameter of $\phi(x,a)$ corresponds to its canonical parameter in $T^{S}$.  Let $C$ be the $E$-class of $a$.
By 4.2 the canonical parameter of $\phi(x,a)$in $T^{+}$ is the same as the canonical parameter of $\phi(x,a)\cap C$ in the model $C$ of $T = DLO$ (where $\phi(x,a)\cap C$ is definable in $C\models DLO$ by a quantifier-free formula with parameter $a$. Clearly the canonical parameter in $DLO$ of this definable set is $a$ or $\emptyset$.
So we have shown that  $e$ is interdefinable with either $a$ or $\emptyset$ in $T^{S}$.
In the first case of course $a\in acl(e)$.  In the second case, as $X$ is not weakly normal in  $T$ it is not weakly nornal in $T^{+}$, hence (by 4.4) not wealy nornal in $T^{S}$  (i.e. all relative to $\emptyset$).

\end{proof}

Bearing in mind, our discussion of the theory $T$ of the free pseudoplane at the end of Section 3,  and choosing now $X$ to be defined by $I(x,a)$ in a saturated model $M$ of $T$, an identical proof to that of Proposition 4.7 above yields a definable set $X$ in $M^{S}$ giving also a negative answer to Question 3.2 (and a counterexample to 4.2 of \cite{Ealy-Onshuus}).

config: arxiv


TITLE: Show that the set is a partition of $A$
QUESTION [1 upvotes]: Let $A\neq \emptyset\neq B$ be sets, $C\subseteq A$, $D\subseteq B$ subsets and $f:A\rightarrow B$ a map.
I want to show that the set $\{f^{-1}(\{x\})\mid x\in\text{im} f\}$ is a partition of $A$.
$$$$
For that do we have to show that the union of all such sets is equal to $A$ and the intersection of them is the empty set?
Could you give me a hint how we could do that?

REPLY [1 votes]: For "the union of all such sets is equal to A" you need to use the definition of the Domain of a function f. Try starting with $ a \in A$ and find a set of the form $ f^{-1}(\{x\}) $ that contains a.
For "the intersection of them is the empty set", assume that for $ x_1 \ne x_2 $ you have $ a \in f^{-1}(\{x_1\})$ and $ a \in f^{-1}(\{x_2\})$. Is this consistent with f being a function?
As a side note, although it is not wrong, you are using x to refer to the images of f. I think $ f^{-1}(\{y\}) $ would be clearer.


TITLE: How many 7-digit phone numbers are possible, assuming that the first digit can’t be a 0 or a 1
QUESTION [2 upvotes]: I use the multiplication rule.
For the first digit I have 8 choices. For the last 6 digits I have 10 choices for each. So answer is $8 \cdot 10 ^6$.
Is there any other way to solve this problems. I usually gain a lot of insight from solving the problems in different ways. Please write which theorems etc. you have used.

REPLY [1 votes]: number of 7 digit numbers ( including leading 0):  10,000,000
number of 7 digit numbers including lead 0 or 1 :  - 2,000,000
number of 7 digit numbers not lead by 0 or 1 :          8,000,000
This more just taking a complement of a set. ( so an interior form of inclusion-exclusion)
You could realize all 7 have at least 8, get $8^7$ then realize each of 6 have 2 more with the seventh having $8=2^3$, for $2^9$ and have fun adding up all $64=2^6$ combinations all together. More a property of a powerset which relates to combinations, as the total number of combinations of all sizes, is the number of distinguishable states which in includes all subsets, (Also tedious)


TITLE: Meaning of euclidean distance matrix's rank
QUESTION [1 upvotes]: It is well known that in dimension $m$, an Euclidean distance matrix has rank less than or equal to m+2. Wiki also knows about it
Also another known fact is added there:

If the points $x_{1},x_{2},\ldots ,x_{n}$ are in general position, the
  rank is exactly $min(n, m + 2)$.

But wherever I read about it, the opposite statement is never mentioned, seemingly being wrong. So, let's say I've got a $n \times n$ Euclidean distance matrix and it really has got the rank equal to $m+2$.
What would it mean? Are there any other definite opportunities for that matrix other than to contain points in general position? The reverse statement has not been proven or there are more options (possibly undiscovered yet)?
So, briefly speaking, what conclusions can be made from the fact that the Euclidean distance matrix has it's rank equal to $space \ dimension + 2$?

REPLY [0 votes]: Well, had to search on the topic for a while. Something concrete had been found in an old, but frequently cited alticle.
Theorem 6 there states:

All the null vectors of $D$ are also null vectors of $F$, and they
  satisfy $e^Tx_i = 0$. $F$ always has $s$ as a further null vector. If
  $rank(D) = r$ then the dimensionulity of $D$ is:
$(i)$ $r-1$ iff $e^TD^-e\neq0$, in which case the generating points
  lie on the surface of a hypersphere, or
$(ii)$ $r-2$ iff $e^TD^-e=0$, in which case the generating points
  cannot lie on the surface of a hypersphere and $D^-e$ is a further
  independent null vector of $F$.

...where $D$  is a EDM (Euclidean distance matrix) – real symmetric $n \times n$
matrix with elements $-\frac{1}{2}d_{ij}^2$ and with zero diagonal; the dimensionality of $D$ is the dimension of the space containing the
points that generate $D$; further details can be found in the original article.
(Gower, J. C., Properties of Euclidean and non-Euclidean distance matrices, Linear Algebra Appl. 67, 81-97 (1985). ZBL0569.15016.)
So, seemingly Wikipedia was not precise enough – general position in the case means "general" in terms of hypersphere. In other words, $rank(D) = r + 1$, if and only if the points generating $D$ lie on the relative boundary of an $r$-dimensional hypersphere.


TITLE: If $f$ is analytic, prove that $\overline{f(\overline{z})}$ is also analytic
QUESTION [3 upvotes]: Let $f$ be an analytic function in an open set $U \subseteq \mathbb{C}$. Let $V=\{z\in\mathbb C:\overline z\in U\}$. Define $g$ on $V$ by $g(z)=\overline{f(\overline{z})}$. Show that $g$ is analytic on $V$. Note: It is not sufficient to show that $g$ is holomorphic because we haven't yet proved that holomorphic implies analytic.

Here is my attempted proof:
First, we will simply state what it means that $f$ is analytic on $U$. Applying the definition, we know that since $f$ is analytic on $U$, we know that for every $z_0 \in U$, there exists $r>0$ and a sequence of complex numbers $\left(a_n\right)_{n=0}^\infty$ such that $f(z)=\sum_{n=0}^\infty a_n\left(z-z_0\right)^n$ on the disc $D(z_0,r)$.
Next, note by definition of $V$ that for all $v \in V$, we have $\overline{v} \in U$. Therefore since $f$ is analytic on $U$, then for all $v \in V$ there exists $r>0$ and a sequence of complex numbers $\left(a_n\right)_{n=0}^\infty$ such that $f(u)=\sum_{n=0}^\infty a_n\left(u-\overline{v}\right)^n$ for all $u \in D(\overline{v},r)$.
Edit (Following Daniel Fischer's suggestion) Now if we realize that if $u \in D(\overline{v},r)$, then we see $u=\overline{w}$ for some $w \in D(v,r) \subseteq V$.
Therefore, putting everything together, we have that for all $v \in V$, there exists $r>0$ and a sequence of complex numbers $\left(a_n\right)_{n=0}^\infty$ such that $f(w)=\sum_{n=0}^\infty \overline{a_n}\left(w-v\right)^n$ for all $w \in D(v,r)\subseteq V$ (is this last part correct?).
I feel like I am getting close; I just need to obtain $g$ from this somehow. But I am losing direction here... Am I on the right track? Thanks!

REPLY [0 votes]: Splitting into real and imaginary parts probably isn't all that helpful - use the fact that $\overline{p(z)}=p(\bar{z})$ for every polynomial $p$ and the continuity of $z\mapsto\bar{z}$. Let $z_0\in U$. There exists $r>0$ and a sequence $(a_n)$ in $\mathbb{C}$ such that
$$f(z)=\sum_{k=0}^\infty a_k(z-z_0)^k$$
for all $z\in\overline{D(z_0,r)}$. Define
$$f_n(z):=\sum_{k=0}^na_k(z-z_0)^k$$
for each $n\in\mathbb{N}$. Then $f_n\to f$ uniformly on $\overline{D(z_0,r)}$. We also define
$$g_n(z):=\overline{f_n(\bar{z})}=\sum_{k=0}^n\bar{a}_k(z-\bar{z}_0)^k$$
We have that $\liminf_{n\to\infty}|\bar{a}_n|^{-1/n}=\liminf_{n\to\infty}|a_n|^{-1/n}>r>0$ so the series
$$\sum_{k=0}^\infty\bar{a}_k(z-\bar{z}_0)^k$$
has radius of converge $\rho>r>0$. In particular, this implies that the above series defines an analytic function $g(z)$ on $D(\bar{z}_0,\rho)$ and $g_n\to g$ uniformly on $\overline{D(\bar{z}_0,r)}$. It follows from the continuity of $z\mapsto\bar{z}$ that $g(z)=\overline{f(\bar{z})}$ on $\overline{D(\bar{z_0},r)}$. This completes the proof since $z_0\mapsto\bar{z}_0$ is a bijection $U\rightarrow V$.


text:
\chapter{Filtering and the VIX}

\section{Stochastic Volatility}
\label{sec:intoSVM}
Consider an equity model with stochastic volatility,
\[dS_t = \mu S_tdt+f(X_t)S_tdW_t\]
where $S_t$ is the price of a stock, the function $f(x)$ is known and $X_t$ is a hidden Markov process. For instance, the Heston model, where $f(x) = \sqrt{X}$ and
\[dX_t = \kappa(m-X_t)dt+\gamma\sqrt{X_t}dB_t\]
where we model the volatility leverage effect by saying that $\frac{1}{t}\mathbb EB_tW_t=\rho $ with $\rho\in[-1,0)$.

In general, if we observe a continuum of prices, then $f(X_t)$ is measurable with respect to the filtration generated by $\{S_\tau:\tau\leq t\}$. Let $Y_t=\log S_t$, and notice that
\[dY_t = \left(\mu-\frac{1}{2}f^2(X_t)\right)dt+f(X_t)dW_t.\]
For a fixed $t>0$, let $(t_k)_k$ be a partition of $[0,t]$, then the quadratic variation of $Y$ is the cumulative variance
\[[Y]_t = \lim_{\|P\|\searrow0}\sum_k(\Delta Y_{t_k})^2=\int_0^tf^2(X_\tau)d\tau\qquad\hbox{in probability}\]
where $\|P\|=\sup_k(t_{k+1}-t_k)$. Clearly, then $\int_0^tf^2(X_\tau)d\tau$ is $\mathcal F_t^Y$-measurable, and if $f(X_t)$ is a continuous process we have
\[\frac{d}{dt}[Y]_t = f^2(X_t)\]
is also $\mathcal F_t^Y$-measurable. So at the very least (e.g. for $f(X_t)$ a continuous process) volatility is observable for almost everywhere $t$, and $X_t$ is observable if $f^{-1}$ exists.

Nonetheless, it is still beneficial to have a Markov structure for $X_t$ so that we can price derivatives on $S_t$. For instance, in the example by Elliot \cite{elliot2007}, the Black-Scholes price of a European call option in the presence of Markovian volatility, when $\rho = 0$ is
\[C(t,S_t,X_t;T,K)=\mathbb E^*[C_{BS}(t, S_t;T,K,Z_{[t,T]})|X_t,S_t] =\mathbb E^*[C_{BS}(t, S_t;T,K,Z_{[t,T]})|\mathcal F_t^Y]\]
where $Z_{[t,T]} = \frac{1}{T-t}\int_t^Tf^2(X_s)ds$, and $\mathbb E^*[~\cdot~]$ is the market's pricing measure. Given $X_t$ and the parameters of $X$'s dynamics under the market measure, we can compute the expected return of the call option either explicitly or through Monte Carlo.

If $X_t$ is not known (i.e. observations are discrete) then we could take a filtering expectation,
\[C(t,S_t;T,K)\stackrel{?}{=}\int C(t,S_t;T,K,x)\pi_t(dx)\]
but such a price would be significantly biased if the market placed any premium on volatility. This option pricing formula exemplifies the challenge of interpreting the filter in financial math.

\section{The VIX}
Filtering can be used to extract the risk-premium placed on volatility by the market. Let $S_t$ be the S\&P500 index. For any time $t$ and some time-window $T>0$, the VIX index is the square root of the market's prediction of average variance during $[t,t+T]$,
\[V_t= \mathbb E^*\left[\frac{1}{T}\int_t^{t+T}f^2(X_s)ds\Big|\mathcal F_t^m\right]\]
where $\mathbb E^*[~\cdot~]$ is the market's pricing measure, and $\mathcal F_t^m$ is the filtration generated by \textit{all} the information in the market (i.e. $\mathcal F_t^Y\subset\mathcal F_t^m$). The process $V_t$ is the `fair' price of a variance swap whose floating leg is the realized variance,
\[RV_{[t,t+T]} =\lim_{\|P\|\searrow 0}\frac{1}{T}\sum_{k}(\Delta Y_{t_k})^2=_p\frac{1}{T}\int_t^{t+T}f^2(X_s)ds\]
where $(t_k)_k$ is a partition of $[t,t+T]$ (i.e. $t=t_0<t_1<\dots t_N=t+T$, with $\|P\|=\sup_k(t_{k+1}-t_k)$ going to zero as $N$ gets large). For a pre-specified notional amount, the payoff of a variance swap is
\[\hbox{notional}\times\left(RV_{[t,t+T]} - V_t\right).\]

\subsection{The VIX Formula}
For diffusion models without jumps, it was shown by Demeterfi et al \cite{derman} that a portfolio of out-of-the-money call and put contracts along with a short position in a futures contract replicates the VIX. It was shown by Carr et al \cite{carr2002,carr2005} that models with jumps can be approximated by the same setup. The following lemma derives the strategy for diffusions:

\begin{lemma} Let $T$ denote the life of the contract, let $F_{t,T}$ denote the future price on $S_{t+T}$ at time $t\geq 0$, and let $r$ be the rate so that $F_{t,T}=S_te^{rT}$. If $S_t$ is purely a diffusion process (i.e. has no jump terms in its differential), then the market's expectation of future realized variance is

\begin{equation}
\label{eq:VIX}
V_t=\frac{2e^{rT}}{T}\left(\int_{K\leq F_{t,T}}P_t(K,T)\frac{dK}{K^2}+\int_{K\geq F_{t,T}}C_t(K,T)\frac{dK}{K^2}     \right)
\end{equation}
where $P_t(K,T)$ and $C_t(K,T)$ denote the price of a put and a call option at time $t$ with strike $K$ and time to maturity $T$, respectively.
\end{lemma}

\begin{proof} Under the market measure, there is a Wiener process $dW_t^*$ such that the returns on the stock satisfy
\[\frac{dS_t}{S_t} = rdt+f(X_t)dW_t^*\]
and the log-price satisfies
\[d\log(S_t) = dY_t = \left(r-\frac{1}{2}f^2(X_t)\right)dt+f(X_t)dW_t^*.\]
Integrating the returns and the log-price separately and then subtracting, we can eliminate all randomness to get the cumulative variance,
\[\int_t^{t+T}\frac{dS_\tau}{S_\tau} -\int_t^{t+T}dY_\tau = \frac{1}{2}\int_t^{t+T}f^2(X_\tau)d\tau\]
which shows us that the realized variance satisfies the following:
\[RV_{[t,t+T]}=\frac{2}{T}\left(\int_t^{t+T}\frac{dS_\tau}{S_\tau}-\log(S_{t+T}/S_t)\right)\]

\[=\frac{2}{T}\left(\int_t^{t+T}\frac{dS_\tau}{S_\tau}-\log(S_{t+T}/F_{t,T})-\log(F_{t,T}/S_t))\right).\qquad\qquad(*)\]
Then, through some simple calculus, we see that
\[-\log(S_{t+T}/F_{t,T}) \]

\[= -\frac{S_{t+T}-F_{t,T}}{F_{t,T}}+\int_{K\leq F_{t,T}}(K-S_{t+T})^+\frac{dK}{K^2}+\int_{K\geq F_{t,T}}(S_{t+T}-K)^+\frac{dK}{K^2}.\]
Plugging this expression for $-\log(S_{t+T}/F_{t,T})$ into $(*)$ we see that the realized variance can be written as the payoffs of several contracts and a continuum of puts and calls that were out-of-the money at time $t$:
\[RV_{[t,t+T]}=\frac{2}{T}\Bigg(\int_t^{t+T}\frac{dS_\tau}{S_\tau} -\frac{S_{t+T}-F_{t,T}}{F_{t,T}}-\log(F_{t,T}/S_t)\]

\[+\int_{K\leq F_{t,T}}(K-S_{t+T})^+\frac{dK}{K^2}+\int_{K\geq F_{t,T}}(S_{t+T}-K)^+\frac{dK}{K^2}\Bigg).\]
Taking expectation of both with respect to the market measure, the noise in $\int\frac{dS}{S}$ vanishes, and since both $\log(F_{t,T}/S_t)=rT$ and $\mathbb E^*S_{t+T}=F_{t,T}$, we have

\[V_t = \mathbb E^*[RV_{t,T}|\mathcal F_t^m]\]

\[=\frac{2}{T}\Big(\int_{K\leq F_{t,T}}\mathbb E^*[(K-S_{t+T})^+|\mathcal F_t^m]\frac{dK}{K^2}+\int_{K\geq F_{t,T}}\mathbb E^*[(S_{t+T}-K)^+|\mathcal F_t^m]\frac{dK}{K^2}\Big)\]
and if we multiply and divide the RHS by $e^{-rT}$ we get the result.
\end{proof}

\subsubsection{Risk Premium}
Under the market measure, the expected returns on a variance swap are zero. However, statistically speaking, variance swaps exhibit a slight bias against the holder of the contract. In other words, the person who receives $\hbox{\textit{notional}}\times(RV_{[t,t+T]}-V_t)$ at time $t+T$ will have an average return that is slightly negative. But because of the volatility leverage effect, the variance swap has the potential to provide relief in the form of a positive cash flow when volatility is high and equities are losing. When quoted in the market, the VIX is quoted as the square-root of $V_t$ in percentage points, and is a mean-reverting process that drifts between 15\% and 50\%. The VIX has the nickname `the investor fear gauge', as it should because it is composed primarily of out-of-the-money options which means that there is an increase in crash-a-phobia whenever the VIX increases.

To get a more precise understanding of investors' fears, it would be nice to remove any actual increases in volatility and merely examine the bias in the market measure's prediction of variance. In other-words, we would like to predict variance in the physical measure, and then compare it with the VIX's prediction to gain a sense of how much of a premium is being placed on risk, or how much fear there is out there.

If we can identify an HMM whose observable component generates $\mathcal F_t^m$, then the market's price of volatility risk (aka the risk-premium) is
\[\mathcal {RP}_t = V_t -  \mathbb E\left[\frac{1}{T}\int_t^{t+T}f^2(X_s)ds\Big|\mathcal F_t^m\right].\]

\begin{remark}
Carr and Wu \cite{carr2006} point out that if we define the martingale change of measure with the Radon-Nykodym derivative $M_t$, then
\[V_t = \mathbb E_t^*[RV_{t,t+T}] = \frac{ \mathbb E_t[M_{t+T}RV_{t,t+T}] }{ \mathbb E_t[M_{t+T}]}=\mathbb E_t[RV_{t,t+T}]+cov_t\left(\frac{M_{t+T}}{\mathbb E_t[M_{t+T}]},RV_{t,t+T}\right)\]
where $\mathbb E_t[~\cdot~]= \mathbb E[~\cdot~|\mathcal F_t^m]$ and $\mathbb E_t^*[~\cdot~]= \mathbb E^*[~\cdot~|\mathcal F_t^m]$, which leads to an expression for the risk-premium, and is $\mathcal F_t^m$-measurable provided that $M_{t+T}$ is known.

\end{remark}

\subsubsection{More on the VIX}
Historically, indices like the S\&P500 exhibit contrary motion with volatility. In particular, periods of high volatility often coincide with bearish markets. Whaley \cite{whaley} describes how tradable volatility assets, such as the VIX, provided market makers with new ways to hedge the options they had written. For instance, a market maker who was short a portfolio of options has always been able to go long in some other types of contracts to reduce the portfolio's Delta to almost zero, meaning that the portfolio would not be hugely affected by small changes in the value of the underlying. When VIX was introduced, it allowed the same market maker the opportunity to also hedge the Vega of his/her short position in options. Prior to volatility hedging instruments, a market maker might be exposed to the rising options prices that occur as volatility increases. However, instruments such VIX futures and calls on VIX futures changed all that, as a short position in options could then have its Vega reduced to almost nothing with the appropriate number of VIX contracts.

Traders use VIX futures and options to hedge in times of uncertain volatility in the SPX or the SPY.\footnote{SPX is the S\&P500; SPY is the tracking stock for the S\&P 500.} When volatility traders notice a spread between the VIX and VIX futures, they realize that a correction is probable. Therefore, if VIX is trading higher than the VIX futures price, then buying calls in both SPY and VIX will make money because either a) VIX goes down and the SPY goes up which places the SPY call in-the-money, or b) the VIX stays up and the VIX futures close the gap which places the VIX call in-the-money. A similar strategy with puts on SPY and VIX can be devised when the VIX is significantly lower than the VIX futures price. The rule of thumb is: provided that the spread between VIX and VIX futures is wide enough, the correction in VIX will create enough change in the market that one of these straddles can cover its initial cost and provide some profit to the investor. The operative word in the strategy mentioned in this paragraph is \textit{spread}, which is precisely what we are looking for as we filter for the risk-premium.


TITLE: Intersection of conics
QUESTION [1 upvotes]: By conic we understand a conic on the projective plane $\mathbb{P}_2=\mathbb{P}(V)$, where $V$ is $3$-dimensional. I'd like to ask how to find the number of points in the intersection of two given smooth conics $Q_1$ and $Q_2$ (given by $q_1,q_2\in S^2V^*$ respectively). So, we are to find the set of all $(x_0,x_1,x_2)\in V$ such that $q_1(x_0,x_1,x_2)=q_2(x_0,x_1,x_2)=0$. First, is this number necessarily finite? And second, how to describe such intersection of quadrics (i.e. 'conics' in $\mathbb{P}^n$) in higher dimensions?
I'm sorry for the lack of my 'research', I'm really stuck on this problem.

REPLY [1 votes]: First, is this number necessarily finite?

No: a degenerate conic factors into two lines. Two such degenerate conics might have a line in common. This line would be a continuum of intersections. Barring such a common component, the number of intersections is limited to four.

And second, how to describe such intersection of quadrics (i.e. 'conics' in $\mathbb P^n$) in higher dimensions?

If you want to count them, then Bézout's Theorem, as mentioned in a comment, is indeed the way to go. Wikipedia includes a generalization to higher dimensoons. Applied to quadrics, you get the result that barring shared components, $n$ quadrics intersect in up to $2^n$ points. In exactly $2^n$ if you include complex points of intersection and take multiplicities into account.


TITLE: Radius of Convergence of $\sum_{k=0}^{\infty}\binom{a}{k}(z)^k$
QUESTION [1 upvotes]: How would I find the radius of convergence for this for complex $z$?
$$(1+z)^a = \sum_{k=0}^{\infty}\binom{a}{k}z^k$$ around $z=0$
I am guessing that it is 1 but not sure how to prove yes or no.
Also, is there a difference between LHS / RHS? Would the RHS follow only if certain criteria are met for the LHS?

REPLY [2 votes]: If we use the ratio test then $$\lim_{k \to \infty} \left\vert\frac{\binom{a}{k+1}z^{k+1}}{\binom{a}{k}z^k}\right\vert = |z|\lim_{k\to \infty} \left\vert \frac{(a-k)!k!}{(a-k-1)!(k+1)!}\right \vert = |z|\lim_{k\to \infty} \left\vert \frac{a-k}{k+1}\right \vert =|z|\lim_{k\to \infty} \left\vert \frac{a}{k+1} - \frac{k}{k+1}\right \vert = |z|$$ so the series converges if $|z| < 1$. Hence the radius of convergence is $1$.


TITLE: Lipshitz Integral for $a=0$
QUESTION [5 upvotes]: I knew that this, $$\displaystyle{\int_0^\infty e^{-ax}J_0(bx)dx=\frac{1}{\sqrt{a^2+b^2}}},$$ holds for $a>0$ but, in an exercise from Arfken, it said that this holds for $a\geq0$.
How can I prove that?

REPLY [2 votes]: Another way. We know that:
$$ J_0(x) = \frac{1}{2\pi}\int_{-\pi}^{\pi}\exp\left(i x \sin(t)\right)\,dt \tag{1}$$
hence by assuming $a>0$ we may apply Fubini's theorem to get:
$$ \begin{eqnarray*}\int_{0}^{+\infty}e^{-ax}J_0(x)\,dx &=& \frac{1}{2\pi}\int_{-\pi}^{\pi}\int_{0}^{+\infty}\exp\left(i x \sin(t)-ax\right)\,dx\,dt\\&=&\frac{1}{2\pi}\int_{-\pi}^{\pi}\frac{dt}{a-i\sin(t)}\\&=&\frac{1}{\pi}\int_{0}^{\pi}\frac{a\,dt}{a^2+\sin^2(t)}\\&=&\frac{2a}{\pi}\int_{0}^{\pi/2}\frac{dt}{a^2+\sin^2(t)}\\&=&\frac{2a}{\pi}\int_{0}^{+\infty}\frac{du}{a^2(1+u^2)+u^2}\\&=&\color{red}{\frac{1}{\sqrt{1+a^2}}}\tag{2}\end{eqnarray*}$$
through the substitution $t=\arctan(u)$. Now $J_0(x)$ is not a Lebesgue-integrable function over $\mathbb{R}^+$, since $|J_0(x)|$ decays like $\frac{1}{\sqrt{x}}$, but it is improperly Riemann-integrable over $\mathbb{R}^+$. So assuming that the given identity is stated "in the Riemann way", $(2)$ holds also for $a=0$. The two-parameters identity of yours can be deduced from $(2)$ through a simple change of variable.


TITLE: adjoint functor
QUESTION [0 upvotes]: I'm currently reading about adjoint functor (page 22 of these notes: http://www.math.jussieu.fr/~schapira/lectnotes/AlTo.pdf).
In particular, it says that two functors $F: C\rightarrow C'$ and $G: C' \rightarrow C$ are adjoint if there exists an isomorphism of bifunctors:
$Hom_{C'}(F(\circ),\circ) \cong Hom_C(\circ,G(\circ))$
By plugging in $F(\circ)$, we have:
$Hom_{C'}(F(\circ),F(\circ)) \cong Hom_C(\circ,G(F(\circ)))$ as two functors from $C \rightarrow Set$.
It then says that we have morphisms $X \rightarrow GF(X)$, functorial in X. I don't understand why it's functorial.
So for each $X \in C$, we have $id_{F(X)} \in Hom_{C'}(F(X),F(X))$, which gives us a morphism $\varphi_X: X \rightarrow GF(X).$ If we have $f: X\rightarrow X'$, why the diagram commutes, in particular, why $GF(f) \circ \varphi_X = \varphi_{X'}\circ f ?$ Can anyone help me please.

REPLY [2 votes]: Let's name $\psi \colon \text{Hom}_{C'}(F(\bullet),F(\bullet))\cong\text{Hom}_C(\bullet,G\circ F(\bullet))$ functorial isomorphism.
In you notation so $\varphi_X = \psi(1_{F(X)})$.
Now the following equation holds
$$\varphi_{X'} \circ f = \hom(f,G \circ F(X'))(\varphi_{X'})=\hom(f,G \circ F(X'))\circ \psi(1_{F(X)})$$
and this is also equal to
$$\psi \circ \hom(F(f),F(X'))(1_{F(X')})=\psi(F(f))$$
in similar way we have that
$$G\circ F(f) \circ \varphi_X = \hom(X,G\circ F(f))\circ \psi(1_{F(X)})$$
which is also equal to
$$\psi \circ \hom(F(X),F(f))(1_{F(X)})=\psi(F(f))$$
From this it follows the equation you were looking for.


TITLE: What is easiest way to prove that $\sqrt 8/2$ is equal to $\sqrt 2$.
QUESTION [0 upvotes]: What is the most easy way I can prove $\sqrt 8/2$ is equal to $\sqrt 2$
I have done $(\sqrt 8/2)^2$ but at the end it gives me $\pm \sqrt 2$ and not positive $\sqrt 2$ So how?

REPLY [0 votes]: $\sqrt{8}=2\sqrt{2}\iff\sqrt{8}=\sqrt{2^2\cdot2}$


TITLE: homotopy limits of dg categories
QUESTION [4 upvotes]: The question is related to the following MO question
(Co-)Limits and fibrations of DG-Categories?
My question is,

how to define the homotopy limit (and colimit) of a system of dg-categories (let's fix a universe and a base ring $k$, and work only with small things...), and
is there an explicit description of the homotopy category of the homotopy limit of dg categories
$$
Ho(holim_{i\in I}\mathscr C_i)=?
$$
Recall that the homotopy category $Ho(\mathscr C)$ of a dg category $\mathscr C$ is the category with the same objects as $\mathscr C$ and the hom group is the cohomology at degree 0 of the hom complex in $\mathscr C:$
$$
Hom_{Ho(\mathscr C)}(X,Y)=H^0(Hom_{\mathscr C}(X,Y)).
$$
One can ask similar questions to "categories" enriched in simplicial sets, which is a slightly more general setting.

I understand (sort of) that there is a model category structure (due to Tabuada) on the category $dg-Cat$ of dg categories such that weak equivalences are what one expects (to be a bit precise, a functor $F:\mathscr C\to\mathscr D$ is a w.e. if
$$
Hom_{\mathscr C}(X,Y)\to Hom_{\mathscr D}(FX,FY)
$$
is a quasi-isomorphism of complexes, and $Ho(F):Ho(\mathscr C)\to Ho(\mathscr D)$ is essentially surjective). But I don't know how to use this model structure to define homotopy limits.
Maybe one uses cofibrant replacement and the naive $\otimes$-structure on $dg-Cat$ to define a $\otimes^{\mathbb L}$-structure (following Toen) and shows that it is closed, so that one has internal hom $R\mathscr Hom$ on $dg-Cat,$ with which one defines homotopy limits (and colimits) of dg-categories by universal properties. I'm not sure. Both references and direct explanations are appreciated.

REPLY [2 votes]: I'm sorry this answer is not on time. Actually for cosimplicial diagrams of dg-categories, which is mostly common in algebraic geometry, the homotopy limit is given by the dg-category of twisted complexes, under some conditions on the diagram. See this paper for details. (sorry for the self-citation.)


TITLE: How to calculate the limit of a sequence having a factorial $ \lim_{n\to \infty}\frac{\ln \left ( n \right )}{\left ( n! \right )^{\frac{1}{n}}} $
QUESTION [1 upvotes]: The limit of

$$ \lim_{n\to \infty}\frac{\ln \left ( n \right )}{\left ( n! \right )^{\frac{1}{n}}} $$

Since the sequence is positive , can we find a sequence bigger having as a limit 0 ?

REPLY [1 votes]: Yes, you can.  First, take the log of the factorial:
$$\ln(n!)=\ln(1\times2\times\dots\times n)=\sum_{k=1}^n\ln(k)$$
Which is derived from log rules.  Then note that
$$\sum_{k=1}^n\ln(k)>\int_1^n\ln(x)\ dx=n\ln(n)-n+1>n\ln(n)-n$$
Thus,
$$\log(n!)>n\ln(n)-n$$
$$n!>\left(\frac ne\right)^n$$
$$(n!)^{1/n}>\frac ne$$
Which reduces your limit to the following:
$$0<\frac{\ln(n)}{(n!)^{1/n}}<e\frac{\ln(n)}{n}$$
which can be proven to go to zero in one application of L'Hospital's rule.


TITLE: How prove this inequality $\sum\limits_{k=1}^{n}\frac{|\sin{k}|}{k}>\frac{2}{\pi}\ln{n}$
QUESTION [4 upvotes]: Question:

show that
  $$\sum_{k=1}^{n}\dfrac{|\sin{k}|}{k}>\dfrac{2}{\pi}\ln{n}$$

I know this
$$\sum_{k=1}^{\infty}\dfrac{\sin{k}}{k}=\dfrac{\pi-1}{2}$$
But for this inequality,I can't.Thank you

REPLY [2 votes]: For large $n$ this is true because as @Winther said, $|\sin k|$ averages to $2/\pi$, and since the integers are incommensurate with $\pi$, they'll be ergodic in $[0,2\pi)$ so
$$[1]\qquad\qquad\qquad \lim_{m \rightarrow \infty}\sum_{k=m}^n\frac{|\sin k|}{k}=\frac{2}{\pi}\sum_{k=m}^n\frac{1}{k}=\frac{2}{\pi}(H_n-H_{m-1})$$where $H_n$ is the $n$th harmonic sum.
Also $H_n = \log n + \gamma +\mathcal{O}(\frac{1}{n})$ so we have
$$[2]\qquad \sum_{k=1}^n\frac{|\sin k|}{k}=\frac{2}{\pi}H_n+\left(\sum_{k=1}^n\frac{|\sin k|-(2/\pi)}{k}\right)= \frac{2}{\pi}\log n+\frac{2}{\pi}\gamma+\mathcal{E}_n$$ where $\gamma$ is the Euler–Mascheroni constant, and the error terms (from averaging $|\sin|$ and summing the harmonic sequence) are grouped into $\mathcal{E}_n$. From $[1]$ above, we have shown that the differences in successive error terms go to zero, so the only thing left to check is if they are always greater than $-2 \gamma/\pi$ for every $n$. In fact for every $n$ we have $$ 0 < \mathcal{E}_n $$ Since the error terms are always positive, we easily have:
$$\sum_{k=1}^n\frac{|\sin k|}{k}=\frac{2}{\pi}\log n+\frac{2}{\pi}\gamma+\mathcal{E}_n>\frac{2}{\pi}\log n+\frac{2}{\pi}\gamma>\frac{2}{\pi}\log n$$


TITLE: Converting between polar and Cartesian coordinates
QUESTION [2 upvotes]: The polar coordinates $r$ and $\varphi$ can be converted to the Cartesian coordinates x and y
by using the [[trigonometric function]]s sine and cosine:
$$x = r \cos \varphi \,$$
$$y = r \sin \varphi \,$$
The Cartesian coordinates ''$x$'' and ''y'' can be converted to polar coordinates ''r'' and ''$\varphi$'' with ''r'' ≥ 0 and ''$\varphi$'' in the interval $[0, 2\pi)$.
$r = \sqrt{x^2 + y^2} \quad$ (as in the (Pythagorean theorem) or the (Euclidean norm),
$$\varphi=\begin{cases}
\arctan(\frac{y}{x}) & \mbox{if } x > 0 \mbox{and } y \geq 0\\
\arctan(\frac{y}{x}) + 2\pi & \mbox{if } x > 0 \mbox{ and } y < 0\\
\arctan(\frac{y}{x}) + \pi & \mbox{if } x < 0 \\
\frac{\pi}{2} & \mbox{if } x = 0 \mbox{ and } y > 0\\
-\frac{3\pi}{2} & \mbox{if } x = 0 \mbox{ and } y < 0\\
\text{undefined} & \mbox{if } x = 0 \mbox{ and } y = 0
\end{cases}$$
my question is $\varphi$ could be  written in one equation by using Congruences modulo n as follows :
$$\varphi=\arctan(\frac{y}{x}) [2\pi]$$ which means there exists some integer ”k” such that $$\varphi=\arctan(\frac{y}{x})+2\cdot k\cdot \pi $$
Can we speak of congruence modulo 2pi (for example) for angles?
Are there any serious references (if wikipedia would answer my question but I am suspicious ...) which I can support myself.
I think there is discontinuity somewhere, because when we do continuously around the origin in the direct sense, $\varphi$ angle increases by $2\pi$ and therefore can not be equal to the initial value that chose. Am i right ??

REPLY [1 votes]: Can the angles be defined up to $2k\pi$? Yes.
Can we write $\phi = \arctan(y/x)+ 2k\pi$?
Almost, but not exactly. The problem in the use of the $\arctan$ function is not (only) that the angle is defined up to multiples of $2\pi$ (which you said correctly), but also that it gives values only between $-\pi/2$ and $+\pi/2$.
For example, consider the point at $(-1,0)$ in Cartesian coordinates. That is, $r=1, \phi = \pi$ in polar coordinates. If we used the "function" you define, $\phi = \arctan(y/x)+ 2k\pi$, we would get:
$$
\phi = \arctan(\frac{0}{-1}) + 2k\pi = 0 + 2k\pi \ne \pi.
$$
The problem of the $\arctan$ function is precisely its codomain. Congruences can help, and are a very nice way to look at the concept of "angle", but don't solve this problem.
In a way, the definition with "multiple cases", that you wrote, is unavoidable (and it is linked to the fact that no continuous function can map the real line into the "circle" of the angles).
In the applications (for example, in CS), the problem is solved by the "atan2" function. (The article, if you want, also answers partly to your question.)

REPLY [1 votes]: Speaking of congruence mod $2\pi$ makes perfectly good sense for real numbers (define an equivalence relation on $\mathbf{R}$ by $x \sim y$ if and only if $y - x = 2\pi k$ for some integer $k$). However, you cannot use congruence mod $2\pi$ to define the polar angle by a single formula: $\arctan(y/x) = k$ along the line $y = kx$ (with the origin removed), but the polar angle $\theta$ differs by $\pi$ on the two rays.
Incidentally, with your piecewise definition of $\varphi$ it's not easy to see $\varphi$ is a smooth function on the plane with a closed ray removed. Instead, you can use
$$
\varphi = \begin{cases}
\operatorname{arccot}(x/y) - \pi & \text{if $y < 0$,} \\
\arctan(y/x) & \text{if $x > 0$,} \\
\operatorname{arccot}(x/y) & \text{if $y > 0$,} \\
\end{cases}
$$
and then show that the first two formulas agree in the open fourth quadrant, while the last two agree in the open first quadrant. (This defines $\varphi$ as a smooth function from the slit plane with the non-positive $x$-axis removed to the interval $(-\pi, \pi)$.)