TITLE: Limitation to "manually" constructing simply connected region in $\mathbb{R}^2$?
QUESTION [1 upvotes]: Restricting the cases to $\mathbb{R}^2$. When studying conservative field, I was under the impression that a vector field can be considered conservative as long as it is continuously differentiable on some region $D$ that is simply connected.
In situations where the region $D$ is not simply connected (such as a donut with a "hole" in the middle) we can then construct such region into a simply connected one by linking to the boundary of the "hole" two lines with opposite orientations such that they are infinity close to each other, and then extend those two lines to the boundary of the region $D$. Thus transforming $D$ into a simply connected region.
It follows that I am unsure if there is limitation to this method. Would it be true to state that at least in $\mathbb{R}^2$ any non-simply connected region can be transformed into a simply connected one using the aforementioned method? Would this be true if $D=\mathbb{R}^2$ with a whole in the middle?
As an example, for vector field such as $F=(1/(x^2+y^2), 1/(x^2+y^2)$ which is clearly not defined at the point $(0,0)$. Can I then artificially "remove" the point $(0,0)$ from the whole space $\mathbb{R}^2$ and claim this new region to be simply connected? And thus $F$ is conservative on this region?
Thanks!
P.S. I just made up the vector field $F$, please imagine that it satisfies the requirement to be a conservative field at all points except for $(0,0)$.
Edit: Sorry to the responders as I do not know a word in topology. My main problem is in fact to justify a problem I saw in my problem set. Here goes:
Let D be the whole region that does not include the point (0,0)
Consider the vector field $f(x,y)=(x/(x^2+y^2), y/(x^2+y^2))$
Find a potential for $f$.
Question: Does $f$ even have a potential? Is it even a conservative field? D is clearly not simply connected. I'm sorry if it is really trivial what I fail to see.
Further edit: I think I see where my mistake is. Thanks everyone!

REPLY [2 votes]: Let me treat the specific question at the end of your post. You are given the vector field
$$ F(x,y) = \left( \frac{x}{x^2+y^2},\frac{y}{x^2+y^2} \right) = (F_1(x,y),F_2(x,y)) $$
on the domain $\Omega = \mathbb{R}^2 \setminus \{ (0,0) \}$. For $F$ to be a conservative vector field, it must have a potential function. A necessary condition for $F$ to be a conservative vector field is $\frac{\partial F_1}{\partial y} = \frac{\partial F_2}{\partial x}$ and this is also sufficient if the domain $\Omega$ is simply connected. In our case,
$$ \frac{\partial F_1}{\partial y} = -\frac{2xy}{(x^2 + y^2)^2} = \frac{\partial F_2}{\partial x} $$
so the condition is satisfied but since $\Omega$ is not simply connected, we can't deduce that $F$ is conservative. However, we can just try and find a potential function $\phi$ for $F$:
$$ \frac{\partial \phi}{\partial x} = \frac{x}{x^2 + y^2} \implies \phi(x,y) = \int \frac{x}{x^2 + y^2} \, dx + g(y) = \frac{1}{2} \ln (x^2 + y^2) + g(y)$$
where $g$ is some function of $y$. Then
$$ \frac{\partial \phi}{\partial y} = \frac{y}{x^2+y^2} + g'(y) = \frac{y}{x^2 + y^2} \implies g'(y) \equiv 0 $$
so
$$ \phi(x,y) = \frac{1}{2} \ln(x^2 + y^2) + C $$
is a potential for $F$ (where $C \in \mathbb{R}$ is arbitrary). Note that this is well-defined on $\Omega$ (but blows up at the origin).


text:
/-
Copyright (c) 2018 Simon Hudon. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Simon Hudon, Patrick Massot
-/
import algebra.module.basic
import algebra.regular.smul
import algebra.ring.pi
import group_theory.group_action.pi

/-!
# Pi instances for modules

This file defines instances for module and related structures on Pi Types
-/

universes u v w
variable {I : Type u}     -- The indexing type
variable {f : I → Type v} -- The family of types already equipped with instances
variables (x y : Π i, f i) (i : I)

namespace pi

lemma _root_.is_smul_regular.pi {α : Type*} [Π i, has_smul α $ f i] {k : α}
  (hk : Π i, is_smul_regular (f i) k) : is_smul_regular (Π i, f i) k :=
λ _ _ h, funext $ λ i, hk i (congr_fun h i : _)

instance smul_with_zero (α) [has_zero α]
  [Π i, has_zero (f i)] [Π i, smul_with_zero α (f i)] :
  smul_with_zero α (Π i, f i) :=
{ smul_zero := λ _, funext $ λ _, smul_zero' (f _) _,
  zero_smul := λ _, funext $ λ _, zero_smul _ _,
  ..pi.has_smul }

instance smul_with_zero' {g : I → Type*} [Π i, has_zero (g i)]
  [Π i, has_zero (f i)] [Π i, smul_with_zero (g i) (f i)] :
  smul_with_zero (Π i, g i) (Π i, f i) :=
{ smul_zero := λ _, funext $ λ _, smul_zero' (f _) _,
  zero_smul := λ _, funext $ λ _, zero_smul _ _,
  ..pi.has_smul' }

instance mul_action_with_zero (α) [monoid_with_zero α]
  [Π i, has_zero (f i)] [Π i, mul_action_with_zero α (f i)] :
  mul_action_with_zero α (Π i, f i) :=
{ ..pi.mul_action _,
  ..pi.smul_with_zero _ }

instance mul_action_with_zero' {g : I → Type*} [Π i, monoid_with_zero (g i)]
  [Π i, has_zero (f i)] [Π i, mul_action_with_zero (g i) (f i)] :
  mul_action_with_zero (Π i, g i) (Π i, f i) :=
{ ..pi.mul_action',
  ..pi.smul_with_zero' }

variables (I f)

instance module (α) {r : semiring α} {m : ∀ i, add_comm_monoid $ f i}
  [∀ i, module α $ f i] :
  @module α (Π i : I, f i) r (@pi.add_comm_monoid I f m) :=
{ add_smul := λ c f g, funext $ λ i, add_smul _ _ _,
  zero_smul := λ f, funext $ λ i, zero_smul α _,
  ..pi.distrib_mul_action _ }

/- Extra instance to short-circuit type class resolution.
For unknown reasons, this is necessary for certain inference problems. E.g., for this to succeed:
```lean
example (β X : Type*) [normed_add_comm_group β] [normed_space ℝ β] : module ℝ (X → β) :=
infer_instance
```
See: https://leanprover.zulipchat.com/#narrow/stream/113488-general/topic/Typeclass.20resolution.20under.20binders/near/281296989
-/
/-- A special case of `pi.module` for non-dependent types. Lean struggles to elaborate
definitions elsewhere in the library without this. -/
instance _root_.function.module (α β : Type*) [semiring α] [add_comm_monoid β] [module α β] :
  module α (I → β) :=
pi.module _ _ _

variables {I f}

instance module' {g : I → Type*} {r : Π i, semiring (f i)} {m : Π i, add_comm_monoid (g i)}
  [Π i, module (f i) (g i)] :
  module (Π i, f i) (Π i, g i) :=
{ add_smul := by { intros, ext1, apply add_smul },
  zero_smul := by { intros, ext1, apply zero_smul } }

instance (α) {r : semiring α} {m : Π i, add_comm_monoid $ f i}
  [Π i, module α $ f i] [∀ i, no_zero_smul_divisors α $ f i] :
  no_zero_smul_divisors α (Π i : I, f i) :=
⟨λ c x h, or_iff_not_imp_left.mpr (λ hc, funext
  (λ i, (smul_eq_zero.mp (congr_fun h i)).resolve_left hc))⟩

end pi

subset_name: curated


TITLE: Associativity test for a Magma
QUESTION [10 upvotes]: Say I have the operation table for a magma. I want to know whether or not the operation is associative. However, associativity is defined for an operation on 3 elements, and the operation table deals only with two. So it is not clear to me how to determine whether operation is associative by looking only at the table. Is it possible, or does one just need to try every combination of three elements by brute force?

REPLY [1 votes]: What follows was extracted from a personal manuscript of mine written in July 2004. I’ve changed the reference citation numbers to be consecutive beginning with 1, and I’ve included internet links when I could find them. None of the references are very recent (even in 2004) because they were mostly collected (as photocopies I made from library journal volumes) in the 1980s and 1990s when I came across them while browsing these journals in college/university libraries for various topics of interest to me. Also, nearly all are from expository/elementary journals and thus would likely be of interest to teachers (and some students) of beginning abstract algebra courses. I have not attempted to search for more recent references that would fit with those I've given below—I'll leave that to others who might be interested.
Associativity can sometimes be difficult to verify when the operation is not based on known associative operations in certain ways, such as subgroup or direct product group settings. The following give tips on some efficient ways to prove associativity in finite groups: Abdali [1], Aczel [2], Budden [5] (pp. 36−42, 96), Burn [6], Di Paola [7], Dobyns [8], Ferrero/Ferrero [9], Hammel [10], Parker [11], Rosenberg [12], Siu [13], Spielman [14], Watson [15], and Zassenhaus [16].
Borenson [3] gives a short proof that at most $n^3 – n$ verifications are needed to prove associativity for an arbitrary binary operation defined on a set of $n$ elements. Bruckheimer/Scott [4], by assuming that an identity and inverses exist for the binary operation, manage to slightly improve on this last result. They show that $n^3 – 3n^2 +2n$ verifications are needed to prove associativity. Bruckheimer/Scott’s result winds up being about $27\%$ less than $n^3 – n$ when $n=10$ and about $3\%$ less when $n = 100.$
[1] S. Kamal Abdali, Verification of associativity of a binary operation, Mathematical Gazette 54 #390 (December 1970), pp. 372−374.
[2] János Aczél, Conditions for a loop to be a group and for a groupoid to be a semigroup, American Mathematical Monthly 76 #5 (May 1969), pp. 547−549.
[3] Henry Borenson, Verifying associativity (Solution to Problem 6238), American Mathematical Monthly 87 #5 (May 1980), pp. 409−410
[4] Maxim Bruckheimer and Jean V. Scott, Testing for associativity, Mathematics Teaching 45 (Winter 1968), pp. 44−46.
[5] Francis James Budden, The Fascination of Groups, Cambridge University Press, 1972, xviii + 596 pages.
[6] Robert Pemberton Burn, Cayley tables and associativity, Mathematical Gazette 62 #422 (December 1978), pp. 278−281.
[7] Jane W. Di Paola, When is a totally symmetric loop a group?, American Mathematical Monthly 76 #3 (March 1969), pp. 249−252.
[8]  Roy Dobyns, A condition equivalent to associativity for finite groups, Two-Year College Mathematics Journal [after 1983: College Mathematics Journal] 3 #1 (Spring 1972), pp. 10−13.
[9] Giovanni Ferrero and Celestina Cotti Ferrero, Verifying the associative property, Bollettino della Unione Matematica Italiana (4) 11 (1975), pp. 322−329.
[10] Arnold Dean Hammel, Verifying the associative property for finite groups, Mathematics Teacher 61 #2 (February 1968), pp. 136−139.
[11] Francis D. Parker, When is a loop a group?, American Mathematical Monthly 72 #7 (August−September 1965), pp. 765−766.
[12] Edwin A. Rosenberg, A question of associativity, or many are the uses of commutativity, School Science and Mathematics 84 #7 (November 1984), pp. 566−572.
[13] Man-Keung Siu, Which Latin squares are Cayley tables?, American Mathematical Monthly 98 #7 (August−September 1991), pp. 625−627.
[14] Bryan Spielman, A test for associativity, Mathematical Gazette 55 #391 (February 1971), p. 59.
[15] Donald Ross Watson, Condition for a loop to be a group, American Mathematical Monthly 74 #7 (August−September 1967), pp. 843−844.
[16] Hans Zassenhaus, What makes a loop a group?, American Mathematical Monthly 75 #2 (February 1968), pp. 139−142.


text:
\section{Line-search and Polyak step-sizes}
\label{app:line-search}
We now give the main guarantees on the step-sizes returned by the line-search. In practice, we use a backtracking line-search to find a step-size that satisfies the constraints, described in \cref{alg:conservative-sls} (\cref{app:exp-details}).
For simplicity of presentation, here we assume the line-search returns the largest step-size that satisfies the constraints.

When interpolation is not exactly satisfied, the procedures
need to be equipped with an additional safety mechanism;
either by capping the maximum step-size by some $\eta_{\max}$
or by ensuring non-increasing step-sizes, $\etak \leq \etakm$. In this case, $\eta_{\max}$ ensures that a bad iteration of the line-search procedure does not result in divergence. When interpolation is satisfied, those conditions can be dropped (e.g., setting $\eta_{\max} \to \infty$) and the rate does not depend on $\eta_{\max}$. The line-searches depend on a parameter $c \in (0,1)$ that controls
how much decrease is necessary to accept a step (larger $c$ means more decrease is demanded).

Assuming the Lipschitz and Armijo line-searches select the largest $\eta$ such that
\aligns{
    \fj(\x - \eta \nabla \fj(\x))
    &\leq \fj(\x) - c \eta \norm{\nabla \fj(\x)}^2,
    &&
    \eta \leq \eta_{\max},
    \tag{Lipschitz line-search}
    \label{eq:app-lipschitz-ls}
    \\
    \fj(\x - \eta A^{-1} \nabla \fj(\x))
    &\leq \fj(\x) - c \eta \norm{\nabla \fj(\x)}^2_{A^{-1}},
    &&
    \eta \leq \eta_{\max},
    \tag{Armijo line-search}
    \label{eq:app-armijo-ls}
}
the following lemma holds.
\begin{thmbox}
\begin{lemma}[Line-search]
\label{lem:lipschitz-line-search}
\label{lem:armijo-line-search}
If $f_i$ is $L_i$-smooth,
the Lipschitz and Armijo lines-searches ensure
\aligns{
    \eta \norm{\nabla f_i(w)}^2 \leq \frac{1}{c}(f_i(w) - f_i^*),
    &&\text{and}&&
    \min\left\{
        \eta_{\max},
        \frac{2 \, (1-c)}{L_{i}}
    \right\}
    \leq \eta \leq \eta_{\max},
    \\
    \eta \norm{\nabla f_i(w)}^2_{A^{-1}} \leq \frac{1}{c}(f_i(w) - f_i^*),
    &&\text{and}&&
    \min\left\{\eta_{\max}, \frac{2 \, \lambda_{\min}(A) \,  (1-c)}{L_{i}}\right\}
    \leq
    \eta \leq \eta_{\max}.
}
\end{lemma}
\end{thmbox}
We do not include the backtracking line-search parameters in the analysis for simplicity,
as the same bounds hold, up to some constant.
With a backtracking line-search,
we start with a large enough candidate step-size and multiply it
by some constant $\gamma < 1$ until the Lipschitz or Armijo line-search condition is satisfied.
If $\eta'$ was a proposal step-size that did not satisfy the constraint, but $\gamma \eta'$ does, the maximum step-size $\eta$ that satisfies the constraint must be in the range $\gamma \eta' \leq \eta < \eta'$.

\begin{proof}[Proof of \cref{lem:lipschitz-line-search,lem:armijo-line-search}]
Recall that if $f_i$ is $L_i$-smooth,
then for an arbitrary direction $d$,
\aligns{
    f_i(w - d) \leq f_i(w) - \lin{\nabla f_i(w), d} + \frac{L_i}{2} \norm{d}^2.
}
For the Lipschitz line-search, $d=\eta\nabla f_i(w)$.
The smoothness and the line-search condition are then

\aligns{
    \text{Smoothness:}
    &&
    f_i(w - \eta \nabla f_i(w)) - f_i(w)
    &\leq \, \textstyle \paren{\frac{L_i}{2}\eta^2-\eta}\norm{\nabla f_i(w)}^2,
    \\
    \text{Line-search:}
    &&
    f_i(w - \eta \nabla f_i(w)) - f_i(w) &\leq -c \eta \norm{\nabla f_i(w)}^2.
}
\vskip .5em
\begin{minipage}[t]{.48\textwidth}
As illustrated in \cref{fig:line-search-illustration},
the line-search condition is looser than smoothness if
\aligns{
    \textstyle
    \paren{\frac{L_i}{2}\eta^2-\eta}\norm{\nabla f_i(w)}^2
    &\leq
    -c \eta \norm{\nabla f_i(w)}^2.
}
The inequality is satisfied for any $\eta \in [a, b]$,
where $a, b$ are values of $\eta$ that satisfy
the equation with equality,
$a = 0, b = \nicefrac{2(1-c)}{L_i}$,
and the line-search condition holds for $\eta \leq \nicefrac{2(1-c)}{L_i}$.
\end{minipage}\hfill
\begin{minipage}[t]{.48\textwidth}
\vskip-1.8em
\begin{figure}[H]
\centering
\makebox[\textwidth][c]{
    \adjustbox{trim={.0\width} {.0\height} {.0\width} {.1\height},clip}{
        \scalebox{0.8}{{\input{figs/line-search.tikz}}}
    }
}
\vskip-1.00em
\caption{Sketch of the line-search inequalities.}
\label{fig:line-search-illustration}
\end{figure}
\end{minipage}
\vskip .5em

As the line-search selects the largest feasible step-size,
$\eta \geq \nicefrac{2(1-c)}{L_i}$.
If the step-size is capped at $\eta_{\max}$, we have
$\eta \geq \min\{\eta_{\max}, \nicefrac{2(1-c)}{L_i}\}$,
and the proof for the Lipschitz line-search is complete.
The proof for the Armijo line-search is identical except for the smoothness property,
which is modified to use the $\norm{\cdot}_{A}$-norm for the direction
 $d=\eta A^{-1}\nabla f_i(w)$;
\aligns{
    f_i(w - \eta A^{-1} \nabla f_i(w))
    &\leq
    f_i(w)
    - \eta \lin{\nabla f_i(w), A^{-1} \nabla f_i(w)}
    + \frac{L_i}{2}\eta^2 \norm{A^{-1} \nabla f_i(w)}^2,
    \\
    &\leq
    f_i(w)
    - \eta \norm{\nabla f_i(w)}_{A^{-1}}^2
    + \frac{L_i}{2 \lambda_{\min}(A)} \eta^2 \norm{\nabla f_i(w)}^2_{A^{-1}},
    \\
    &=
    f_i(w)
    + \paren{\frac{L_i}{2 \lambda_{\min}(A)}\eta^2 - \eta}\norm{\nabla f_i(w)}_{A^{-1}}^2,

}
where the second inequality comes from $\|A^{-1} \nabla f_i(w)\|{}^2 \leq \frac{1}{\lambda_{\min}(A)} \norm{\nabla f_i(w)}^2_{A^{-1}}$.
\end{proof}

Similarly, the stochastic Polyak step-sizes (SPS) for $f_i$ at $\x$ are defined as
\aligns{
    \text{SPS:}
    &&
    \eta
    =
    \min\left\{
        \frac{f_i(\x) - f_i^*}{c \normsq{\nabla f_i(\x)}},
        \eta_{\max}
    \right\},
    &&
    \text{Armijo SPS:}
    &&
    \eta
    =
    \min\left\{
        \frac{f_i(\x) - f_i^*}{c \normsq{\nabla f_i(\x)}_{A^{-1}}},
        \eta_{\max}
    \right\},
}
where the parameter $c > 0$ controls the scaling of the step
(larger $c$ means smaller steps).
\begin{thmbox}
\begin{lemma}[SPS guarantees]
\label{lem:sps-bounds}
If $f_i$ is $L_i$-smooth, SPS and Armijo SPS ensure that
\aligns{
    \text{SPS:}
    &&
    \textstyle
    \eta \normsq{\gradi{w}} \leq \frac{1}{c} (f_i(w) - f_i^*),
    &&
    \textstyle
    \min\left\{\eta_{\max}, \frac{1}{2 c L_{i}}\right\} \leq \eta &\leq \eta_{\max},
    \\
    \text{Armijo SPS:}
    &&
    \textstyle
    \eta \normsq{\gradi{w}}_{A^{-1}} \leq \frac{1}{c} (f_i(w) - f_i^*),
    &&
    \textstyle \min\left\{\eta_{\max}, \frac{\lambda_{\min}(A)}{2 c L_{i}}\right\} \leq \eta &\leq \eta_{\max}
}
\end{lemma}
\end{thmbox}
\begin{proof}[Proof of \cref{lem:sps-bounds}]
The first guarantee follows directly from the definition of the step-size.
For SPS,
\aligns{
    \eta \norm{\nabla f_i(\x)}^2
    &=
    \min\left\{
        \frac{f_i(\x) - f_i^*}{c \normsq{\nabla f_i(\x)}},
        \eta_{\max}
    \right\}
    \norm{\nabla f_i(\x)}^2,
    \\
    &=
    \min\left\{
        \frac{f_i(\x) - f_i^*}{c},
        \eta_{\max}  \norm{\nabla f_i(\x)}^2
    \right\}
    \leq
    \frac{1}{c}(f_i(\x) - f_i^\star).
}
The same inequalities hold for Armijo SPS with $\norm{\nabla f_i(\x)}^2_{A^{-1}}$.
To lower-bound the step-size, we use the $L_i$-smoothness of $f_i$, which implies $f_i(w) - f_i^* \geq \frac{1}{2 L_i} \norm{\gradi{w}}\!{}^2$.
For SPS,
\aligns{
\frac{f_i(w) - f_i^*}{c \normsq{\gradi{w}}}
\geq \frac{\frac{1}{2 L_i} \normsq{\gradi{w}}}{c \normsq{\gradi{w}}}
= \frac{1}{2 c L_i}.
}
For Armijo SPS, we additionally use $\norm{\nabla f_i(\x)}^2_{A^{-1}} \leq \frac{1}{\lambda_{\min}(A)}\norm{\nabla f_i(\x)}^2$,
\aligns{
\frac{f_i(w) - f_i^*}{c \norm{\gradi{w}}^2_{A^{-1}}}
\geq \frac{\frac{1}{2 L_i} \normsq{\gradi{w}}}{c \frac{1}{\lambda_{\min}(A)} \norm{\gradi{w}}^2}
= \frac{\lambda_{\min}(A)}{2 c L_i}.
\tag*{\qedhere}
}
\end{proof}

config: arxiv


TITLE: Proof for: GCD and divisibility
QUESTION [0 upvotes]: I need some hints how to proof something like the following:
Let $a,b \in \mathbb{Z}$ with $a,b \not= 0$ and let $\gcd(a,b)=d$.
(1) For any $m,n\in \mathbb{Z}$ we have $d \mid ma+nb$.
(2) There exist $t,r \in \mathbb{Z}$ so that $d = ta + rb$.
Thank you very much for any help ;)

REPLY [1 votes]: $(1)\,$ follows by basic divisibility laws: for any $\,d\in\Bbb Z\!:\ d\mid a,b\,\Rightarrow\, d\mid\,\color{#0a0}ma,\color{#0a0}nb\,\Rightarrow\,d\mid ma\color{#c00}+nb.\,$ Said equivalently, the set of multiples of $d$ are closed under integer $\rm\color{#0a0}{scalings}$, and under $\color{#c00}{\rm addition}$ (the same holds true for the set of common multiples of any set of integers).  Or, for a direct proof: $\, a = \bar a d,\, b = \bar b d\, $ so $\, ma + nb = m\bar a d + n\bar b d = (m\bar a + n\bar b) d\,$ is a multiple of $d$.
This linear structure of a set of (common) multiples of an integer lies at the heart of many divisibility results. This innate linear structure is brought to the fore when one studies ideals in rings, as well as modules - a generalization of a vector space with scalarsfrom rings (vs. fields).
$(2)\,$ can be proved by (complete) induction, using the basic descent step of the Euclidean algorithm for the gcd, that the gcd remains the same if we subtract the smaller argument from the larger one, i.e $\ \gcd(a,b) = \gcd(a,b\!-\!a).\,$ If $\,0 < a < b\,$ then $\,a+(b\!-\!a) < a+b,\,$  so, by complete induction on the height $\,:= a+b\,$ of $\,\gcd(a,b),\,$ we conclude that $\,d = m a + n(b-a)\,$ for some $\,m,n\in\Bbb Z,\,$ But, rearranging, $\,d  = (m-n)a + nb\,$ is also a linear combination of $\,a,b.\,$ QED $ $ That's a sketch of the inductive proof of the Bezout Identity for the gcd. You need to fill in the details, e.g. base case(s).
Remark $\ $ Interpreted constructively, the above yields an extended Euclidean algorithm that computes the linear Bezout representation of the gcd. For efficiency one replaces the above subtractive descent by its iteration to modular form $\,\gcd(a,b) = \gcd(a,b\!-\!qa) = \gcd(b,\, b\ {\rm mod}\ a).$ If one annotates the remainder sequence with equations expressing each remainder as a linear rep of $\,a,b\,$ then one obtains a very simple extended gcd algorithm, which is conveniently expressed in terms of row operations (as in linear algebra). This is both easier and far less error-prone than the alternative method of back-substitution. See this post for complete details.


TITLE: Is there a general product formula for $\sum\limits_{k=1}^{n} k^p$
QUESTION [2 upvotes]: I'm familiar with Faulhaber's formula to express this sum as a much simpler one, but it appears that for any $p$ there's a product formula in $n$ for the sum e.g.:
$$\begin{align}
& \sum\limits_{k=1}^{n} k^1=\frac{n(n+1)}{2} \\
& \sum\limits_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6} \\
& \sum\limits_{k=1}^{n} k^3=\frac{n^2(n+1)^2}{4}
\end{align}$$
...and so forth. Is there a general product formula in $p$ and $n$ for this sum?

REPLY [3 votes]: This question was answered in a comment:

Yes: http://en.wikipedia.org/wiki/Faulhaber%27s_formula. –  Martín-Blas Pérez Pinilla Feb 1 at 22:31


TITLE: Examples of connections between bounded cohomology and geometric properties of groups
QUESTION [4 upvotes]: I think that the question is self explanatory. The only example that comes to my mind is the characterization of hyperbolic groups given by Mineyev ("Straightening and bounded cohomology"). There is also a characterization of amenability of groups using bounded cohomology. However, amenability doesn't seems to me a geometric property.

REPLY [3 votes]: There is a long strand of literature relating hyperbolicity of groups and of group actions to second bounded cohomology of groups.
The first result in this theory is Brooks' proof that free groups of positive rank have second bounded cohomology of uncountably infinite dimension. After further progress eventually Epstein and Fujiwara proved the same conclusion for all word hyperbolic groups.
Then Fujiwara wrote a series of papers studying non-properly discontinuous group actions on hyperbolic spaces, giving conditions on such actions under which the second bounded cohomology is of uncountable dimension.
After further progress, Bestvina and Fujiwara proved that every subgroup of a surface mapping class group is either virtually abelian or has second bounded cohomology of uncountable dimension. One of their main tools was the theorem of Masur and Minsky on Gromov hyperbolicity of the curve complex of a surface, and they used and deeloped related results about the geometry and dynamics of actions of subgroups of mapping class groups on curve complexes.
A further interesting feature of this story is that the machinery developed by Bestvina and Fujiwara, for purposes of computing second bounded cohomology of subgroups of mapping class groups, played back into the general study of group actions on hyperbolic spaces, leading to the theory of "acylindrical group actions" developed first by Bowditch and more recently by Osin, and the very recent theory of "hierarchically hyperbolic groups" developed by Behrstock, Hagen, and Sisto.


TITLE: Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$
QUESTION [10 upvotes]: Let $a,b,c$ be positive integers.  Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$.
Attempt
Diophantine $ax + by = c$ has integer solution $x_0, y_0$ implies $GCD(a,b)|c$. Factoring out $ GCD(a,b)$ from each side gives $$\frac{1}{GCD(a,b)}(ax + by) = \frac{1}{GCD(a,b)}c$$ which must still have an integer solution as $GCD(a,b)$ obviously divides both $a$ and $b$.  If $GCD(a,b)$ does not divide $c$ there is no integer solution.
That $GCD(a,b)|c$ implies that $ax + by = c$ has integer solution $x_0, y_0$. Let $c = GCD(a,b)d$, where $d$ is integer.
$ax + by = GCD(a,b)d$;  divide both sides by $GCD(a,b)$:
Obtain $mx + ny = d$ with $GCD(m,n) = 1$.  If $d$ is an integer and $GCD(m,n) = 1$ then $x,y$ must be integers as $mx + ny$ cannot be further divided evenly.
or
$ax + by = c$ has no solution implies $GCD(a,b)$ does not divide c.
$c = GCD(a,b)(\frac{ax}{GCD(a,b)} + \frac{by}{GCD(a,b)}) + r$
with $GCD(a,b) > 0, 0<r<GCD(a,b)$, r integer
$\frac{c}{GCD(a,b)} = \frac{ax + by}{GCD(a,b)} + \frac{r}{GCD(a,b)}$

REPLY [1 votes]: Let a,b,c be positive integers. Verify that Diophantine equation ax+by=c has integer solution x0,y0 if and only if GCD(a,b)|c.
=>: (how do you write the arrows?):
This was pretty much correct in my first attempt.  More clearly:
If $ax + by = c$ has integer solution $x_0,y_0$(they exist - how do i draw that?) then $ax_0 + by_0 = c$.  Divide both sides by $gcd(a,b)$.  (See first attempt.)  Then $gcd(a,b)|a, gcd(a,b)|b$ => $gcd(a,b)|(ax_0 + by_0)$ => $gcd(a,b)|c$.
<=:
This was pretty much wrong in my first attempt.
Let $gcd(a,b)|c$
Then exist e such that $c = gcd(a,b)*e$ and exist $x_1,y_1$ with $gcd(a,b) = ax_1 + by_1$
Multiply both sides by $e$: $gcd(a,b)*e = ax_1e + by_1e$
$a(x_1e) + b(y_1e) = c$, $(x_1e,y_1e)$ solution.

Attempt to prove both ways at once:
$ax + by = c$ has integer solution $ax_0 + by_0 = c$
Let $d = gcd(a,b)$; then $a = md,b = nd$:
$c = (md)x_0 + (nd)y_0 = d(mx_0 + ny_0)$
So $d$ divides $c$.
If either $ax_0 + by_0 <>($does not equal$) c$ or $gcd(a,b) $ does not divide $ c$
$c = (md)x_0 + (nd)y_0 = d(mx_0 + ny_0)$ would not be valid.  kind of a stretch there.


TITLE: Find the number of zeros of $f(z)={1\over3}e^z-z$ in the unit disc
QUESTION [0 upvotes]: Find the number of zeros of $f(z)={1\over3}e^z-z$ in the unit disc.

The book's solution is that because $|z|>{1\over3}e^z$ then by Roche's theorem $\mathbb{Z}(f)=1$, but I think it's a mistake since, for example, for $z=1$, $1>{e\over3}$ but for $z=0, 0\ngtr{1\over3}$. I'm not sure how to solve it, thanks.

REPLY [2 votes]: @Jacobian in his comment above has already solved the problem. First read Rouche’s theorem carefully: Let $D$ be a bounded domain with piecewise smooth boundary $\partial D$. Let $f(z),h(z)$ be analytic in $D\cup \partial D$. If $|h(z)|<|f(z)|$ for all $z\in \partial D$, then $f$ and $f+g$ have the same number of zeros inside $D$.
Note than the image of your curve $\gamma$ equals $\partial D$ for some domain $D$, so inside $\gamma$ means for $z\in \partial D$ as in the theorem.


text:
\begin{document}
\title{\textbf{Reflected Solutions of Backward Doubly Stochastic \\Differential Equations\footnote{Supported by National Natural Science Foundation of China Grant 10771122,
Natural Science Foundation of Shandong Province of China Grant
Y2006A08 and National Basic Research Program of China (973 Program,
No. 2007CB814900)}}\\}
\author{Yufeng SHI \thanks{
Corresponding author. E-mail: yfshi@sdu.edu.cn},\quad Yanling GU\\
School of Mathematics \\
Shandong University\\
Jinan, 250100, P. R. China}
\date{}
\maketitle
\begin{abstract}
We study reflected solutions of one-dimensional backward doubly
stochastic differential equations (BDSDEs in short). The
``reflected'' keeps the solution above a given stochastic process.
We get the uniqueness and existence by penalization. For the
existence of backward stochastic integral, our proof is different
from [KKPPQ] slightly. We also obtain a comparison theorem for
reflected BDSDEs. At last we gave a simulation for the reflected
solutions of BDSDEs.
\end{abstract}

\textbf{Key words.} Reflected Backward doubly stochastic
differential equations, comparison theorem, backward stochastic
integral.

\textbf{AMS 1991 subject classifications. 60H10, 60H30, 35K85,
90A09.}
\section{ Introduction}
\section{Preliminaries: the existence and uniqueness to BDSDEs}
\textbf{Notations.} The Euclidean norm of a vector
$x\in{\mathbf{R}}^k$ will be denoted by $|x|$, and for a
$d\times k$ matrix $A$, we define $\|A\|=\sqrt{TrAA^*}$.\\
Let $(\Omega,\cal{F},P)$ be a probability space, and $T>0$ be an
arbitrarily fixed constant throughout this paper. Let $\{W_t;0\leq
t\leq T\}$ and $\{B_t;0\leq t\leq T\}$ be two mutually independent
standard Brownian Motion processes, with values respectively in
$R^d$ and $R^l$, defined on $(\Omega,\cal{F},P)$. Let $\cal{N}$
denote the class of $P-$null sets of $\cal{F}$. For each $t\in
[0,T]$, we define
$${\cal{F}}_t : ={\cal{F}}_t^W\vee {\cal{F}}_{t,T}^B$$
where for any process $\{\eta_t\}$,
${\cal{F}}_{s,t}^{\eta}=\sigma\{\eta_r-\eta_s;s\leq r\leq t\}\vee
{\cal{N}}$, ${\cal{F}}_t^{\eta}={\cal{F}}_{0,t}^{\eta}$.

Note that the collection $\{{\cal{F}}_t;t\in [0,T]\}$ is neither
increasing nor decreasing, so it does not constitute a
filtration.\\
Let us introduce some spaces.

${\mathbf{L}}^2=\{\xi$ is an ${\cal{F}}_T$ -measurable random
variable s.t. $E(|\xi|^2)<\infty \}$.

${\mathbf{M}}^n=\{\{\phi_t,0\leq t\leq T\}$ is a jointly
measurable (classes of $dP\times dt$ a.e. equal) stochastic
processes s.t. $E\int_0^T|\varphi_t|^ndt<\infty$, and $\phi_t$ is
${\cal{F}}_t$ measurable for a.e. $t\in [0,T]\}$. ($n\in
{\mathbf{N}}$)

${\mathbf{S}}^2=\{\{\phi_t,0\leq t\leq T\}$ is a continuous
stochastic processes, s.t. $E(\sup_{0\leq t\leq
T}|\phi_t|^2)<\infty$, and
$\phi_t$ is ${\cal{F}}_t$ measurable for a.e. $t\in [0,T]\}$.\\
We are given four objects: the first one is a terminal value
$\xi$, s.t.

(i) $\xi \in {\mathbf{L}^2}$.\\
The second is two ``coefficients'' $f$ and $g$, which are maps
\begin{eqnarray*}
f:\Omega\times [0,T]\times R\times R^d\rightarrow R, \quad \quad
g:\Omega\times [0,T]\times R\times R^d\rightarrow R^l.
\end{eqnarray*}
 be jointly measurable and such that

(ii) $\forall (y,z)\in R\times R^d$, $f(\cdot,y,z)\in
{\mathbf{M}}^2$, $g(\cdot,y,z)\in {\mathbf{M}}^2$.

(iii) there exist two constants $K>0$ and $0<\alpha<1$, $\forall
y$, $y'\in R$, $z$, $z'\in R^d$, a.s.,a.e.
$$
\left\{
\begin{array}{lcl}
|f(t,y,z)-f(t,y',z')|^2 &\leq & C(|y-y'|^2+|z-z'|^2)\\
|g(t,y,z)-g(t,y',z')|^2 &\leq &C|y-y'|^2+\alpha
|z-z'|^2\\
\end{array}
\right. \eqno{\mbox{(H1)}}
$$
And the last one is an ``obstacle'' $\{S_t,0\leq t\leq T\}$, which
is a continuous progressively measurable real-valued process,
$S_t$ is ${\cal{F}}_t$ measurable, satisfying

(iv) $E\{\sup_{0\leq t\leq T}(S^+_t)\}<\infty$.\\
We always assume that $S_T\leq \xi$, a.s.\\
Now, let us introduce our reflected backward doubly stochastic
differential equations (BDSDE in short). The solution of our
reflected BDSDE is triple $(Y,Z,K)$ of ${\cal{F}}_t$ measurable
processes taking valued in $\bf{R}$, $\bf{R}^d$ and $\bf{R}_+$,
respectively, and satisfying

(v) $Z\in {\mathbf{M}}^2$;

(v') $Y\in {\mathbf{S}}^2$, and $K_T\in {\mathbf{L}}^2$;

(vi)
$Y_t=\xi+\int_t^Tf(s,Y_s,Z_s)ds+K_t-K_t+\int_t^Tg(s,Y_s,Z_s)dB_s-\int_t^TZ_s,dW_s$,
$0\leq t\leq T$;

(vii) $Y_t\geq S_t$, \quad\quad $0\leq t\leq T$;

(viii) $\{K_t\}$ is continuous and increasing, $K_0=0$ and
$\int_0^T(Y_t-S_t)dK_t=0$.

\textbf{Lemma 2.1.} Under the above conditions (i), (ii) and
(iii), the following backward doubly stochastic differential
equation (BDSDE in short) (1)
\begin{eqnarray}
Y_t=\xi+\int_t^Tf(s,Y_s,Z_s)ds+\int_t^Tg(s,Y_s,Z_s)dB_s-\int_t^TZ_sdW_s,\quad
0\leq t\leq T.
\end{eqnarray}
has a unique solution $(Y,Z)\in {\mathbf{S}}^2\times {\mathbf{M}}^2.$\\
This lemma was derived from Pardoux and Peng [PP3].

\textbf{Lemma 2.2.} let $(\xi,f,g)$ and $(\xi',f',g)$ be two
parameters of BDSDEs, each one satisfies all the assumptions (i),
(ii) and (iii) [with the exception that the Lipschitz condition
(iii) could be satisfied by either $f$ or $f'$ only], and suppose
in addition the following
$$\xi\leq \xi', a.s., \quad \quad f(t,y,z)\leq f'(t,y,z), a.s.a.e \quad \forall (y,z)\in R\times R^d .$$
Let $(Y,Z)$ be a solution of the BDSDE with parameter $(\xi,f,g)$
and $(Y',Z')$ a solution of the BDSDE with parameter
$(\xi',f',g)$. Then
$$Y_t\leq Y'_t, \quad a.e. \quad \quad \forall  0\leq t\leq T$$
This lemma was derived from Y. Gu and Y. Shi [GS].
\section{A priori estimate.}
In the following, $c$ will denote a constant whose value can vary
from line to line. \\
{\bf Proposition 3.1.} let $(Y,Z,K)$ be a solution of the
following reflected BDSDE(2)
\begin{eqnarray}
Y_t=\xi+\int_t^Tf(s,Y_s,Z_s)ds+\int_t^Tg(s,Y_s,Z_s)dB_s+K_t-K_t-\int_t^TZ_sdW_s,\quad
0\leq t\leq T.
\end{eqnarray}
Then there exists a constant $C$ such that
\begin{eqnarray}\nonumber
& & E(\sup_{0\leq t\leq T}Y_t^2+\int_0^T|Z_t|^2dt+K_T^2)\\
&\leq& CE(\xi^2+\int_0^ Tf(t,0,0)^2dt+\int_0^
Tg(t,0,0)^2dt+\sup_{0\leq t\leq T}(S_t^+)^2).
\end{eqnarray}
{\bf Proof.} Applying It$\hat{o}$'s to the process $Y_t$ and the
function $y\rightarrow y^2$ yields,
\begin{eqnarray*}
Y_t^2+\int_t^T|Z_s|^2ds&=&\xi^2+2\int_t^TY_sf(s,Y_s,Z_s)ds+\int_t^Tg^2(s,Y_s,Z_s)ds\\
& &
+2\int_t^TS_sdK_s+2\int_t^TY_sg(s,Y_s,Z_s)dB_s-2\int_t^TY_sZ_sdW_s
\end{eqnarray*}
where we have used the identity $\int_0^T(Y_t-S_t)dK_t=0$.\\
Using the Lipschitz property of $f$ and $g$, we have
\begin{eqnarray*}
EY_t^2+E\int_t^T|Z_t|^2 dt&=&
E\xi^2+2E\int_t^T|Y_s|\cdot[K(|Y_s|+|Z_s|)+f(s,0,0)]ds+2E\int_t^TS_sdK_s\\
& &
+E\int_t^Tc(\alpha')(|Y_s|^2+|g(s,0,0)|^2)ds+\alpha'E\int_t^T|Z_s|^2ds\\
&\leq&
E\xi^2+(2K+1+K^2\frac{2}{1-\alpha'}+c(\alpha'))E\int_t^T|Y_s|^2ds+E\int_t^Tf^2(s,0,0)ds\\
& &
+c(\alpha')E\int_t^Tg^2(s,0,0)ds+2\int_t^TS_sdK_s+\frac{1+\alpha'}{2}E\int_t^T|Z_s|^2ds
\end{eqnarray*}
where we have used (iii), for any $\alpha<\alpha'<1$, $\exists
c(\alpha')$, such that
\begin{eqnarray} |g(t,y,z)|^2\leq
c(\alpha')(|y|^2+|g(t,0,0)|^2)+\alpha'|z|^2, \quad a.s.\quad
\forall (y,z)\in R\times R^d
\end{eqnarray}
from Gronwall's lemma applied to $Y$, we get
\begin{eqnarray}
EY_t^2\leq
cE[\xi^2+\int_t^Tf(s,0,0)^2ds+\int_t^T|g(s,0,0)|^2ds+2\int_t^TS_sdK_s]
\end{eqnarray}
It follows that
\begin{eqnarray}
E\int_0^T|Z_s|^2ds\leq
cE[\xi^2+\int_0^Tf(s,0,0)^2ds+\int_0^T|g(s,0,0)|^2ds+2\int_0^TS_sdK_s]
\end{eqnarray}
We now give an estimate of $E[K_T^2]$, from Eq(2)
\begin{eqnarray*}
K_T=Y_0-\xi-\int_0^Tf(t,Y_t,Z_t)dt-\int_0^Tg(t,Y_t,Z_t)dB_t+\int_0^TZ_tdW_t
\end{eqnarray*}
and the estimates (5) and (6), we show the following inequalities,
\begin{eqnarray*}
E[K_T^2]&\leq&
cE[\xi^2+\int_0^Tf^2(s,0,0)^2ds+\int_0^Tg^2(s,0,0)ds+2\int_0^TS_sdK_s]\\
&\leq
&cE[\xi^2+\int_0^Tf^2(s,0,0)ds+\int_0^Tg^2(s,0,0)ds]+2c^2E(\sup_{0\leq
t\leq T}(S_t^+)^2)+\frac12E(K_T^2)\\
&\leq &
cE[\xi^2+\int_0^Tf^2(s,0,0)ds+\int_0^Tg^2(s,0,0)ds]+E(\sup_{0\leq
s\leq T}(S_s^+)^2)
\end{eqnarray*}
It follows easily that for each $t\in [0,T]$,
\begin{eqnarray*}
E(Y_t^2+\int_0^T|Z_t|^2dt+K_T^2)\leq
CE[\xi^2+\int_0^Tf^2(s,0,0)ds+\int_0^Tg^2(s,0,0)ds+(\sup_{0\leq
s\leq T}(S_s^+)^2)]
\end{eqnarray*}
The result then follows easily from Burkholder-Davis-Gundy
inequality.\quad\quad $\Box$\\

{\bf Proposition 3.2.} Let $(\xi,f,g,S)$ and $(\xi',f',g,S')$ be
two parameters satisfying the assumptions (i)-(iv). Suppose
$(Y,Z,K)$ is a solution of the reflected BDSDE $(\xi,f,g,S)$ and
$(Y',Z',K')$ is a solution of the reflected BDSDE
$(\xi',f',g,S')$. Define
$$\triangle \xi=\xi'-\xi,\quad \triangle f=f-f',\quad \triangle S=S-S',\quad \triangle Y=Y-Y',\quad \triangle Z=Z-Z',\quad \triangle K=K-K'$$
Then there exists a constant $C$ such that,
\begin{eqnarray}\nonumber
& & E(\sup_{0\leq t\leq T}|\triangle Y_t|^2+\int_0^T|\triangle
Z_t|^2dt+|\triangle K_T|^2) \\
& \leq & CE[|\triangle\xi|^2+\int_0^T|\triangle f(t,Y_t,Z_t)|^2dt
+cE[\sup_{0\leq t\leq T}({\triangle {S_t^+})^2}]^{\frac
12}\Psi_T^{\frac12}
\end{eqnarray}
where
$$\Psi_T=E[\xi^2+\int_0^Tf^2(t,0,0)dt+\sup_{0\leq t\leq T}(S_T^+)^2+{\xi'}^2+\int_0^T{f'}^2(t,0,0)dt+\sup_{0\leq t\leq T}({S'}^+_T)^2]$$
{\bf Proof.} The computation are similar to those in the previous
proof, so we'll only sketch the argument. Since
$\int_t^T(\triangle Y_s-\triangle S_s)d(\triangle K_s)\leq 0$,
\begin{eqnarray*}
E|\triangle Y_t|^2+E\int_t^T|\triangle Z_s|^2ds&\leq &
E|\triangle\xi|^2+2E\int_t^T\triangle f(s,Y_s,Z_s)\triangle Y_sds\\
& & +2E\int_t^T(f(s,Y_s,Z_s)-f(s,Y'_s,Z'_s))\triangle
Y_sds\\
& &
+E\int_t^T(g(s,Y_s,Z_s)-f(g,Y'_s,Z'_s))^2ds+2E\int_t^T\triangle
S_sd(\triangle K_s)
\end{eqnarray*}
Arguments already used in the previous proof lead to
\begin{eqnarray*}
E|\triangle Y_t|^2+\frac{1-\alpha}{2}E\int_t^T|\triangle
Z_s|^2ds&\leq & c[E|\triangle\xi|^2+\int_t^T|\triangle
f(s,Y_s,Z_s)|^2ds+\int_t^T|\triangle
Y_s|^2ds\\
& & +(\sup_{0\leq t\leq T}|\triangle S_t|)(K_T+K'_T)]
\end{eqnarray*}
Using Gronwall's lemma, Proposition 3.1 and the
Burkholder-Davis-Gundy inequality, we obtain inequality
(7).\quad\quad $\Box$\\

From the Proposition 3.2, We deduce immediately the following
uniqueness result  when $\xi=\xi',\quad f'=f,\quad S=S'$.

{\bf Theorem 3.3.} Under the assumption (i)-(iv), there exists at
most one measurable triple $(Y,Z,K)$, which satisfies (v)-(viii).
\section{Existence of a solution of reflected BDSDE: approximation via penalization.}
In this section, we'll give the result of existence via
penalization which is slightly different from [KKPPQ].

For each $n\in$ {\bf N}, let $(Y^n,Z^n)$ denote the unique pair of
${\cal{F}}_t$ measurable processes with valued in $R\times R^d$,
satisfying
$$E\int _0^T|Z_t^n|^2dt<\infty$$
and
\begin{eqnarray}
Y_t^n=\xi+\int_t^Tf(s,Y_s^n,Z_s^n)ds+n\int_t^T(Y^n_s-S_s)^-ds+\int_t^Tg(s,Y_s^n,Z_s^n)dB_s-\int_t^TZ^n_sdW_s
\end{eqnarray}
where $\xi$, $f$ and $g$ satisfy the  assumptions stated in
Section 2. We define
$$K^n_t=n\int_0^t(Y^n_s-S_s)^-ds, \quad \quad 0\leq t\leq T$$
From [PP3], we get
$$E(\sup_{0\leq t\leq T}|Y^n_t|^2)< \infty .$$
We now establish a priori estimate, uniformly in $n$, on the
sequence $(Y^n,Z^n,K^n)$.
\begin{eqnarray}\nonumber
& & E|Y^n_t|^2+E\int_t^T|Z^n_s|^2ds\\
\nonumber &=&
E|\xi|^2+2E\int_t^Tf(s,Y^n_s,Z^n_s)Y^n_sds+E\int_t^Tg^2(s,Y^n_s,Z^n_s)ds+2E\int_t^TY^n_sdK^n_s\\
\nonumber
\end{eqnarray}
from (4), we obtain
\begin{eqnarray}\nonumber
E|Y^n_t|^2+E\int_t^T|Z^n_s|^2ds &\leq &
E|\xi|^2+2E\int_t^T(f(s,0,0)+K|Y^n_s|+|Z_s^n|)|Y^n_s|ds\\
\nonumber & &
+E\int_t^T[c(\alpha')(|Y^n_s|^2+g^2(s,0,0))+\alpha'|Z_s^n|^2]ds+2E\int_t^TS_sdK_s^n\\
\nonumber &\leq &
E|\xi|^2+E\int_0^Tf^2(s,0,0)ds+E\int_0^Tg^2(s,0,0)ds\\
\nonumber & & +(2K+c(\alpha')+K^2\beta)E\int_t^T|Y^n_s|^2ds +
(\alpha'+\frac{1}{\beta})E\int_t^T|Z_s^n|^2ds \\
\nonumber & &
+\beta E[\sup_{0\leq t\leq
T}(S_t^+)^2]+\frac{1}{\beta}E[(K_T^n-K_t^n)^2]
\end{eqnarray}
where $\beta$ is positive. But
\begin{eqnarray*}
K^n_T-K^n_t=Y^n_t-\xi-\int_t^Tf(s,Y^n_s,Z^n_s)ds-\int_t^Tg(s,Y^n_s,Z^n_s)dB_s+\int_t^TZ_s^ndW_s,
\end{eqnarray*}
hence
\begin{eqnarray*}
E[(K^n_T-K^n_t)^2]\leq
c[E(|Y^n_t|^2)+E|\xi|^2+1+E\int_t^T(|Y^n_s|^2+|Z^n_s|^2)ds]
\end{eqnarray*}
choosing $\beta$ enough large, such that
$\alpha'+\frac{1+c}{\beta}\leq \bar{\alpha}<1$, then
\begin{eqnarray*}
E(|Y^n_t|^2)+(1-\bar{\alpha})E\int_t^T|Z^n_s|^2ds\leq
c(1+E\int_t^T|Y^n_s|^2ds)
\end{eqnarray*}
it then follows from Gronwall's lemma that
\begin{eqnarray*}
E(|Y^n_t|^2)+E\int_t^T|Z^n_s|^2ds+E[(K_T^n)^2]\leq c,\quad \quad
n\in {\bf N}
\end{eqnarray*}
furthermore, from Burkholder-Davis-Gundy inequality, we deduce
that
\begin{eqnarray}
E(\sup_{0\leq t\leq T
}|Y^n_t|^2)+E\int_t^T|Z^n_s|^2ds+E[(K_T^n)^2]\leq c,\quad \quad
n\in {\bf N}
\end{eqnarray}
note that if we define
\begin{eqnarray*}
f_n(t,y,z)&=& f(t,y,z)+n(y-S_t)^-,\\
f_n(t,y,z)&\leq&  f_{n+1}(t,y,z),
\end{eqnarray*}
it follows from lemma 2.2 that $Y^n_t\leq Y^{n+1}_t$, $0\leq t\leq
T$, a.e. Hence
$$Y^n_t\uparrow Y_t,\quad \quad 0\leq t\leq T,\quad a.e.$$
and from (9) and Fatou's lemma,
$$E(\sup_{0\leq t\leq T}Y^2_t)\leq c.$$
It then follows by dominated convergence that
\begin{eqnarray}
E\int_0^T(Y_t-Y^n_t)^2dt\rightarrow 0,\quad as \quad n\rightarrow
\infty
\end{eqnarray}
Next, we'll prove $Z_t^n\rightarrow Z_n$ in ${\mathbf{M}}^2$.\\
Applying It$\hat{o}$'s formula to $(Y^n-Y^p)$ and the function
$y\rightarrow y^2$ ,
\begin{eqnarray*}
& & E(|Y^n_t-Y^p_t|^2)+E\int_t^T|Z^n_s-Z^p_s|^2ds \\&=&
2E\int_t^T[f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s)](Y^n_s-Y^p_s)ds\\
& &
+E\int_t^T|g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s)|^2ds+2E\int_t^T(Y^n_s-Y^p_s)d(K^n_s-K^p_s)\\
&\leq & 2KE\int_t^T(|Y^n_s-Y^p_s|^2+|Y^n_s-Y^p_s|\cdot
|Z^n_s-Z^p_s|)ds+KE\int_t^T|Y^n_s-Y^p_s|^2ds\\
 & &+\alpha E\int_t^T|Z^n_s-Z^p_s|^2ds
+2E\int_t^T(Y^n_s-S_s)^-dK^p_s+2E\int_t^T(Y^p_s-S_s)^-dK^n_s
\end{eqnarray*}
from $2ab\leq \frac{2}{1-\alpha}a^2+\frac{1-\alpha}{2}b^2$, then
\begin{eqnarray*}
& & E(|Y^n_t-Y^p_t|^2)+E\int_t^T|Z^n_s-Z^p_s|^2ds \\
&=&
(3K+K^2\frac{2}{1-\alpha})E\int_t^T|Y^n_s-Y^p_s|^2ds+\frac{1+\alpha}{2}E\int_t^T|Z^n_s-Z^p_s|^2ds\\
& & +2E\int_t^T(Y^n_s-S_s)^-dK_s^p+2E\int_t^T(Y^p_s-S_s)^-dK_s^n
\end{eqnarray*}
\begin{eqnarray*}
\frac{1-\alpha}{2}E\int_t^T|Z_s^n-Z_s^p|^2ds&\leq&
cE\int_t^T|Y^n_s-Y^p_s|^2ds+(E(\sup_{0\leq t\leq
T}|(Y^n_t-S_t)^-|^2)\cdot E(K^p_T)^2)^{\frac12}\\
& & +(E(\sup_{0\leq t\leq T}|(Y^p_t-S_t)^-|^2)\cdot
E(K^n_T)^2)^{\frac12}
\end{eqnarray*}
so
\begin{eqnarray}\nonumber
E\int_t^T|Z_s^n-Z_s^p|^2ds&\leq&
c[E\int_t^T|Y^n_s-Y^p_s|^2ds+(E(\sup_{0\leq t\leq
T}|(Y^n_t-S_t)^-|^2)\cdot E(K^p_T)^2))^{\frac12}\\
 & & +(E(\sup_{0\leq t\leq T}|(Y^p_t-S_t)^-|^2)\cdot
E(K^n_T)^2]))^{\frac12}
\end{eqnarray}
now, we give the proof that
\begin{eqnarray}
E(\sup_{0\leq t\leq T}|(Y^n_t-S_t)^-|^2)\rightarrow 0,\quad \quad
as \quad n\rightarrow \infty
\end{eqnarray}
Since $Y^n_t\geq Y^0_t$, we can w.l.o.g. replace $S_t$ by $S_t\vee
Y^0_t$;so assume that $E(\sup_{t\leq T}S^2_t)<\infty$. We first
want to compare a.s. $Y_t$ and $S_t$ for all $t\in [0,T]$, while
we do not know yet that $Y$ is a.s. continuous. From the
comparison theorem for BDSDE's, we have that a.s. $Y^n_t\geq
\tilde{Y}^n_t$, $0\leq t\leq T$, $n\in \mathbf{N}$, where
$\{\tilde{Y}^n_t,\tilde{Z}^n_t;0\leq t\leq T\}$ is the unique
solution of the BDSDE:
\begin{eqnarray*}
\tilde{Y}^n_t=\xi+\int_t^Tf(s,Y^n_s,Z^n_s)ds+n\int_t^T(S_t-\tilde{Y}^n_s)ds+\int_t^Tg(s,Y^n_s,Z^n_s)dB_s-\int_t^T\tilde{Z}_s^ndW_s
\end{eqnarray*}
Let $\nu$ be a stopping time such that $0\leq \nu\leq T$. Then
\begin{eqnarray*}
\tilde{Y}^n_t&=&E^{{\cal{F}}_{\nu}}[e^{-n(T-\nu)}\xi+\int_{\nu}^Te^{-n(s-\nu)}f(s,Y^n_s,Z^n_s)ds+n\int_{\nu}^Te^{-n(s-\nu)}S_sds]\\
             & &+\int_{\nu}^Te^{-n(s-\nu)}g(s,Y^n_s,Z^n_s)dB_s
\end{eqnarray*}
It is easily seen that
$$e^{-n(T-\nu)}\xi+n\int_{\nu}^Te^{-n(s-\nu)}S_sds\rightarrow \xi{\mathbf{1}}_{\nu=T}+S_{\nu}{\mathbf{1}}_{\nu<T}$$
a.s. and in ${\mathbf{L}}^2$, and the conditional expectation
converges also in ${\mathbf{L}}^2$. Moreover,
$$|\int_{\nu}^Te^{-n(s-\nu)}f(s,Y^n_s,Z^n_s)ds|\leq \frac{1}{\sqrt{2n}}(\int_0^Tf^2(s,Y^n_s,Z^n_s)ds)^{\frac12}$$
hence
$E^{{\cal{F}}_{\nu}}\int_{\nu}^Te^{-n(s-\nu)}f(s,Y^n_s,Z^n_s)ds\rightarrow
0$ in ${\mathbf{L}}^2$, as $n\rightarrow \infty$. \\
and
\begin{eqnarray*}
E(\int_{\nu}^Tg(s,Y^n_s,Z^n_s)dB_s)^2&\leq& cE\int_0^Te^{-2n(s-\nu)}g^2(s,Y^n_s,Z^n_s)ds\\
&\leq & \frac{c}{4n}E\int_0^Tg^4(s,Y^n_s,Z^n_s)ds\rightarrow 0
\end{eqnarray*}
Consequently, $\tilde{Y}^n_s\rightarrow
\xi{\mathbf{1}}_{\nu=T}+S_{\nu}{\mathbf{1}}_{\nu<T}$ in mean
square, and $Y_{\nu\geq S_{\nu}}$ a.s. From this and the section
theorem in Dellacherie and Meyer [DM], it follows that a.s.
$$Y^n_t\geq S_t,\quad 0\leq t\leq T$$
Hence $(Y^n_t-S_t)^-\searrow 0$, $0\leq t\leq T$, a.s., and from
Dini's theorem the convergence is uniform in $t$. The result
finally follows by dominated convergence, since $(Y^n_t-S_t)^-\leq
(S_t-Y^0_t)^+\leq |S_t|+|Y^0_t|$.\\
From above property, (11) and
(10), hence
$$E\int_0^T|Z^n_s-Z^p_s|^2ds\rightarrow 0,\quad E\int_0^T|Y^n_s-Y^p_s|^2ds\rightarrow 0,\quad as \quad n,p \rightarrow \infty$$
Now, we want to prove the process $Y$ is continuous. Similar to
above proof,
\begin{eqnarray*}
& & |Y^n_t-Y^p_t|^2+\int_t^T|Z^n_s-Z^p_s|^2ds \\&=&
2\int_t^T[f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s)](Y^n_s-Y^p_s)ds+\int_t^T|g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s)|^2ds\\
& &
+2\int_t^T[g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s)](Y^n_s-Y^p_s)dB_s-2\int_t^T(Y^n_s-Y^p_s)(Z^n_s-Z^p_s)dW_s\\
& & +2\int_t^T(Y^n_s-Y^p_s)d(K^n_s-K^p_s)\\
\end{eqnarray*}
and
\begin{eqnarray*}
\sup_{0\leq t\leq T}|Y^n_t-Y^p_t|^2 &\leq &
2\int_0^T|f(s,Y^n,Z^n_s)-f(s,Y^p,Z^p_s)|\cdot|Y^n_s-Y^p_s|ds+2\int_0^T(Y^p_s-S_s)^-dK^n_s\\
& &
+\int_0^T|g(s,Y^n,Z^n_s)-g(s,Y^p,Z^p_s)|^2ds+2\int_0^T(Y^n_s-S_s)^-dK^p_s\\
& & +2\sup_{0\leq t\leq
T}|\int_t^Tg(s,Y^n,Z^n_s)-g(s,Y^p,Z^p_s)(Y^n_s-Y^p_s)dB_s|\\
& & +2\sup_{0\leq t\leq T}|\int_t^T(Y^n_s-Y^p_s)(Z^n_s-Z^p_s)dW_s|
\end{eqnarray*}
and from Burkholder-Davis-Gundy inequality and $2ab\leq \beta
a^2+\frac{1}{\beta}b^2$, we have
\begin{eqnarray*}
E\sup_{0\leq t\leq T}|Y^n_t-Y^p_t|^2 &\leq &
\frac12 E\sup_{0\leq t\leq T}|Y^n_t-Y^p_t|^2+cE\int_0^T(|Y^n_s-Y^p_s|^2+|Z^n_s-Z^p_s|^2)ds\\
& & +(E[\sup_{0\leq t\leq T}|(Y^n_t-S_t)^-|^2]\cdot
E|K_T^p|^2)^{\frac12}\\
& &+(E[\sup_{0\leq t\leq T}|(Y^p_t-S_t)^-|^2]\cdot
E|K_T^n|^2)^{\frac12}
\end{eqnarray*}
hence, $E(\sup_{0\leq t\leq T}|Y^n_t-Y^p_t|^2)\rightarrow 0$, as
$n,p\rightarrow \infty$.\\
from which we get $Y^n$ convergence uniformly in $t$ to $Y$, a.s.
and $Y$ is a continuous process.\\

Denote $K^n_t=n\int_0^t(Y^n_s-S_s)^-ds$, since $K^n_{\cdot}
\nearrow$ as $n\nearrow $, and from $E((K^n_T)^2)\leq C$, $\forall
n\in N$ we have $K^n_T\nearrow K_T$ and $E(K_T)^2\leq C$, that is
$K_T<
\infty$, a.s.\\
Since
\begin{eqnarray*}
|K_t^n-K_t^p|&\leq&
|Y_t^n-Y_t^p|+|Y_0^n-Y_0^p|+|\int_0^t(f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s))ds|\\
& &
+|\int_0^t(g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s))dB_s|+|\int_0^t(Z_s^n-Z_s^p)dW_s|
\end{eqnarray*}
\begin{eqnarray*}
E(\sup_{0\leq t \leq T}|K_t^n-K_t^p|^2)& \leq& c\{E\sup_{0\leq
t\leq T
}|Y^n_s-Y^p_s|^2+E|Y^n_0-Y^p_0|^2\\
& & +E\int_0^T(f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s))^2ds\\
& & +E(\sup_{0\leq t\leq
T}|\int_0^tg(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s))dB_s|)\\
& & +E(\sup_{0\leq t\leq T}|\int_0^t(Z^n_s-Z^p_s)dW_s|\}
\end{eqnarray*}
We use the fact that $f$ and $g$ are Lipschitz functions, and the
Burkholder-Davis-Gundy inequality for the last terms, he obtain
$$E(\sup_{0\leq t\leq T}|K_t^n-K_t^p|^2)\rightarrow 0, \quad as \quad n,p \rightarrow \infty$$
consequently, there exists a pair $(Z,K)$ of measurable processes
which valued in $R^d\times R$, satisfying
$$E(\int_0^T(Z^n_t-Z^p_t)^2dt+\sup_{0\leq t\leq T}|K_t-K_t^n|^2)\rightarrow 0, \quad \quad as \quad n\rightarrow \infty$$
and (v), (vi) satisfied by the triple $(Y,Z,K)$ (obtained by
taking limit as $n\rightarrow \infty$), (vii) from (12). It
remains to
check that $\int_0^T(Y_t-S_t)dK_t=0$.\\
Clearly, $\{K_t\}$ is increasing. Moreover, we have just seen that
$(Y^n,K^n)$ tends to $(Y,K)$ uniformly in $t$ in probability. Then
the measure $dK^n$ tends to $dK$ weakly in probability,
$$\int_0^T(Y^n_t-S_t)dK_t^n\rightarrow \int_0^T(Y_t-S_t)dK_t,$$
in probability, as $n\rightarrow \infty$.\\
We deduce from the same argument and (12) that
$$\int_0^T(Y_t-S_t)dK_t\geq 0.$$
on the other hand, $$\int_0^T(Y^n_t-S_t)dK_t^n\leq 0,\quad \quad
n\in {\bf N}$$ hence,
$$\int_0^T(Y_t-S_t)dK_t= 0, \quad \quad a.s.$$
and we have proved that $(Y,Z,K)$ solves the reflected
BDSDE(2).\quad\quad $\Box$
\section{Comparison Theorem for reflectd BDSDE.}
We next give a comparison theorem, similar to that of [KKPPQ] and
[HLM] for reflected BSDEs.

{\bf Theorem 5.1.} Let $(\xi,f,g,S)$ and $(\xi',f',g,S')$ be two
sets of data, each one satisfying all the assumptions of (i)-(iv)
[with the exception that the Lipschtiz condition (H1) could be
satisfied by either $f$ or $f'$ only]. And suppose in addition the
following:

(1) $\xi\leq \xi'$, a.s.,

(2) $f(t,y,z)\leq f'(t,y,z)$, \quad $dP\bigotimes dt$, a.e.
$\forall (y,z)\in R\times R^d $,

(3) $S_t\leq S'_t$, $0\leq t\leq T$, a.s.\\
Let $(Y,Z,K)$ be a solution of the reflected BDSDE with data
$(\xi,f,g,S)$ and $(Y',Z',K')$ a solution of the reflected BDSDE
with data $(\xi',f',g,S')$. Then
$$Y_t\leq Y'_t,\quad 0\leq t\leq T, \quad a.s.$$
If $f$ and $f'$ all satisfy Lipschitz condition (iii), and $S=S'$,
then we also have $dK\geq dK'$, $P\_a.s.$

{\bf Proof.} Applying It$\hat{o}$'s formula to $|(Y_t-Y'_t)^+|^2$,
and taking expectation, we get
\begin{eqnarray*}
E|(Y_t-Y'_t)^+|^2+E\int_t^T{\mathbf{1}}_{\{Y_s>
Y'_s\}}|Z_s-Z'_s|^2ds\leq
2E\int_t^T(Y_s-Y'_s)^+[f(s,Y_s,Z_s)-f'(s,Y'_s,Z'_s))]ds\\
+E\int_t^T{\mathbf{1}}_{\{Y_s>
Y'_s\}}[g(s,Y_s,Z_s)-g(s,Y'_s,Z'_s)]^2ds+2E\int_t^T(Y_s-Y'_s)^+(dK_s-dK'_s)
\end{eqnarray*}
since on $\{Y_t>Y'_t\}$, $Y_t>S_t'>S_t$, then $dK_t=0$, so we have
$$\int_t^T(Y_s-Y'_s)^+(dK_s-dK'_s)=-\int_t^T(Y_s-Y'_s)^+dK'_s\leq 0$$
Assume now that the Lipschitz condition in the statement applied
to $f$, then
\begin{eqnarray*}
& & E|(Y_t-Y'_t)^+|^2+E\int_t^T{\mathbf{1}}_{\{Y_s>
Y'_s\}}|Z_s-Z'_s|^2ds\\
&\leq & 2E\int_t^T(Y_s-Y'_s)^+[f(s,Y_s,Z_s)-f'(s,Y'_s,Z'_s))]ds\\
& & +E\int_t^T{\mathbf{1}}_{\{Y_s>
Y'_s\}}[g(s,Y_s,Z_s)-g(s,Y'_s,Z'_s)]^2ds\\
&\leq &
2K\int_t^T(Y_s-Y'_s)^+[|Y_s-Y'_s|+|Z_s-Z'_s|]ds+E\int_t^T{\mathbf{1}}_{\{Y_s>
Y'_s\}}[K|Y_s-Y'_s|^2+|Z_s-Z'_s|^2]ds\\
&\leq &
(3K+K^2\frac{2}{1-\alpha})E\int_t^T|(Y_s-Y'_s)^+|^2ds+\frac{1+\alpha}{2}\int_t^T{\mathbf{1}}_{\{Y_s>
Y'_s\}}|Z_s-Z'_s|^2ds
\end{eqnarray*}
hence
$$E|(Y_t-Y'_t)^+|^2\leq \bar{K}E\int_t^T|(Y_s-Y'_s)^+|^2ds,$$
and from Gronwall's lemma, $(Y_t-Y'_t)^+=0$, $0\leq t\leq T$,
a.s.\\
If $f$ and $f'$ are all Lipschitz functions and $S=S'$, we
consider the following two BDSDEs:
\begin{eqnarray*}
Y^n_t&=&\xi+\int_t^Tf(s,Y_s^n,Z^n_s)ds+n\int_t^T(Y^n_s-S_s)^-ds+\int_t^Tg(s,Y^n_s,Z^n_s)dB_s-\int_t^TZ^n_sdW_s,\\
{Y'}^n_t&=&\xi'+\int_t^T{f'}(s,{Y'}_s^n,{Z'}^n_s)ds+n\int_t^T({Y'}^n_s-S_s)^-ds+\int_t^Tg(s,{Y'}^n_s,{Z'}^n_s)dB_s-\int_t^T{Z'}^n_sdW_s,
\end{eqnarray*}
from the comparison theorem of BDSDE [GS], we get $\forall n\geq
0$, $P\_a.s.$ $Y^n\leq {Y'}^n$. On the other hand, from the proof
of existence in section 4, we know that, $\forall t\in [0,T]$,
$P\_a.s.$,

(i) $Y^n_t\rightarrow Y_t$ (resp. ${Y'}^n_t\rightarrow Y'_t$), as
$n\rightarrow\infty$,

(ii) $K_t=\lim_{n\rightarrow \infty}n\int_0^t(Y_s^n-S_s)^-ds$, and
$K'_t=\lim_{n\rightarrow \infty}n\int_0^t({Y'}_s^n-S_s)^-ds$.\\
for $Y^n\leq {Y'}^n$, it follows that, $\forall s,r\in [0,T]$,
$K_s-K_r\geq K'_s-K'_r$ and $dK\geq dK'$, $P\_a.s$.\quad \quad
$\Box$
\section{Other results}
{\bf Lemma 6.1.} let $(Y,Z,K)$ be a solution of the above
reflected BDSDE, satisfying condition (vi) to (viii). Then for
each $t\in [0,T]$,
$$K_T-K_t=\sup_{t\leq u\leq T}(\xi+\int_u^Tf(s,Y_s,Z_s)ds+\int_u^Tg(s,Y_s,Z_s)dB_s-\int_u^TZ_sdW_s-S_u)^-$$
{\bf Proof.} The proof is similar to [KKPPQ]. Where
$((Y_{T-t}(\omega)-S_{T-t}(\omega)),
(K_T(\omega)-K_{T-t}(\omega)), 0\leq t\leq T)$ is the solution of
a Skorohod problem. Applying the Skorohod lemma with
$$x_t=(\xi+\int_{T-t}^Tf(s,Y_s,Z_s)ds+\int_{T-t}^Tg(s,Y_s,Z_s)dB_s-\int_{T-t}^TZ_sdW_s-S_{T-t})(\omega),$$
$k_t=(K_t-K_{T-t})(\omega)$,
$y_t=(Y_{T-t}-S_{T-t})(\omega)$.\quad\quad $\Box$

{\bf lemma 6.2.} Let $(Y,Z,K)'$ be a solution of the above
reflected BDSDE (2), satisfying (v)-(viii). Then for each $t\in
[0,T]$,
\begin{eqnarray}
Y_t=ess\sup_{\nu\in
\Gamma_t}\{E^{{\cal{F}}_t}[\int^{\nu}_tf(s,Y_s,Z_s)ds+S_{\nu}{\mathbf{1}}_{\{\nu<
T \}}+\xi{\mathbf{1}}_{\{\nu= T\}}+\int_t^{\nu}g(s,Y_s,Z_s)dB_s\}]
\end{eqnarray}
where $\Gamma$ is the set of all stopping times dominated by $T$,
and $\Gamma_t=\{\nu\in\Gamma;t\leq \nu\leq T\}$.

{\bf Proof.} Let $\nu\in\Gamma_t$,
\begin{eqnarray*}
Y_t&=&\xi+\int_t^{\nu}f(s,Y_s,Z_s)ds+K_{\nu}-K_t+\int_t^{\nu}g(s,Y_s,Z_s)dB_s-\int_t^{\nu}Z_sdW_s\\
   &=&E[\xi+\int_t^{\nu}f(s,Y_s,Z_s)ds+K_{\nu}-K_t|{\cal{F}}_t]+\int_t^{\nu}g(s,Y_s,Z_s)dB_s\\
   &\geq & E[\int_t^{\nu}f(s,Y_s,Z_s)ds+S_{\nu}{\mathbf{1}}_{\{\nu<T\}}
   +\xi{\mathbf{1}}_{\{\nu=T\}}|{\cal{F}}_t]+\int_t^{\nu}g(s,Y_s,Z_s)dB_s
\end{eqnarray*}
Now er choose an optimal element of $\Gamma_t$ in order to get the
reversed inequality. Let
$$D_t=\inf\{t\leq u\leq T;Y_u=S_u\}\wedge T$$
Now the condition $\int_0^T(Y_t-S_t)dK_t=0$ and the continuity of
$K$ imply that
$$K_{D_t}-K_t=0,$$
it follows that
$$Y_t=E[\int_t^{D_t}f(s,Y_s,Z_s)ds+S_{D_t}{\mathbf{1}}_{\{D_t<T\}}
   +\xi{\mathbf{1}}_{\{D_t=T\}}|{\cal{F}}_t]+\int_t^{D_t}g(s,Y_s,Z_s)dB_s$$
from above result, we get (13).\quad\quad $\Box$
\section{Two reflected BDSDE}
Assume

(i) $\xi\in \mathbf{L}^2$;\\
let the mappings $f:[0,T]\times\Omega\times R\times R^d$,
$g:[0,T]\times\Omega\times R\times R^d$ be jointly measurably and
such that

(ii) $\forall (y,z)\in R\times R^d$, $f(\cdot,y,z)\in
\mathbf{M}^2$, $g(\cdot,y,z)\in \mathbf{M}^4$;

(iii) there exist two constants $K>0$ and $0<\alpha<1$, $\forall
(y,z), (y'z')\in R\times R^d$,
$$
\left\{
\begin{array}{lcl}
|f(t,y,z)-f(t,y',z')|^2 &\leq & C(|y-y'|^2+|z-z'|^2)\\
|g(t,y,z)-g(t,y',z')|^2 &\leq &C|y-y'|^2+\alpha
|z-z'|^2\\
\end{array}
\right. \eqno{\mbox{(H1)}}
$$
and two obstacles $\{L_t\}$ and $\{U_t\}$, such that

(iv) $E(\sup_{t\leq T}(L_t^+)^2)\leq \infty$, $E(\sup_{t\leq
T}(U_t^-)^2)< \infty$, and $L_t\leq \xi\leq
 U_t$, $P\_a.s.$,
$L_t<U_t$ for all $0\leq t<T$, $P\_a.s.$\\
A solution of two reflected BDSDE is a measurable processes
$(Y,Z,K^+,K^-)$, valued in $R\times R^d\times R_+\times R_+$, such
that for $0\leq t \leq T$

(v) $Z\in \mathbf{M^2}$;

(v') $Y\in \mathbf{S}^2$, $K^+$, $K^-\in \mathbf{L}^2$;

(vi) $ Y_t=\xi+\int_t^Tf(s,Y_s,Z_s)ds+(K^+_T-K^+_t)-(K^-_T-K^-_t)
 +\int_t^Tg(s,Y_s,Z_s)dB_s-\int_t^TZ_sdW_s$

(vii) $L_t\leq Y_t\leq U_t$, $P\_a.s.$, for all $0\leq t\leq T$;

(viii) $\{K_t^+\}$, $\{K_t^-\}$ are continuous and increasing,
$K_0^+=K_0^-=0$, and
$$\int_0^T(Y_t-L_t)dK^+_t=\int_0^T(U_t-Y_t)dK^-_t=0,\quad P\_a.s.$$
We also need the following additional assumption (H2):\\
there exists a process
$$X_t=X_0-\int_0^tJ_sdW-s-V_t^++V_t^-,\quad \quad X_T=\xi$$
with $J\in\mathbf{M}^2$, $V^+$, $V^-$ are continuous and
increasing, s.t.
$$L_t\leq X_t\leq U_t,\quad P\_a.s.  \forall t\in[0, T], \quad L<U,\quad P\_a.s. \forall t\in [0,T) $$
\vskip 0.5cm We now divide several steps to prove the existence
and uniqueness of two reflected BDSDE.

Consider the following BDSDE, for any $n$, $m\geq 1$,
\begin{eqnarray}\nonumber
Y^{n,m}_t&=&\xi+\int_t^Tf(s, Y^{n,m}_s,Z^{n,m}_s)ds+m\int_t^T(L_s-
Y^{n,m}_s)^+ds-n\int_t^T( Y^{n,m}_s-U_s)^+ds\\
 & & +\int_t^Tg(s,
Y^{n,m}_s,Z^{n,m}_s)dB_s-\int_t^TZ^{n,m}_sdW_s
\end{eqnarray}
since $f(s,y,z)+m(L_t-y)^+-n(y-U_t)^+$ is Lipschitz in $(y,z)$
uniformly in $(t,\omega)$, Eq(14) has a unique solution, denoted
$(Y^{n,m},Z^{n,m})$. Then we have the follow priori estimates.

{\bf lemma 7.1.} There exists a constant $C$ independent of $n$,
$m$, s.t.
\begin{eqnarray*}
\sup_{t\leq
T}E(Y^{n,m}_t)^2+E(\int_0^T|Z^{n,m}_s|^2ds)+m^2E(\int_0^T(L_s-Y^{n,m}_s)^+ds)^2
+n^2E(\int_0^T(Y^{n,m}_s-U_s)^+ds)^2\leq C
\end{eqnarray*}

{\bf proof.} (1) Applying It$\hat{o}$'s formula to $Y^{n,m}$ and
$y\rightarrow y^2$, we get
\begin{eqnarray*}
E(Y^{n,m}_t)^2+E(\int_t^T|Z^{n,m}_s|^2ds)&=&
E(\xi)^2+2E\int_t^TY^{n,m}_sf(s,Y^{n,m}_s,Z^{n,m}_s)ds\\
& &+E\int_t^Tg^2(s,Y^{n,m}_s,Z^{n,m}_s)ds
+2mE\int_t^TY^{n,m}_s(L_s-Y^{n,m}_s)^+ds\\
& & -2nE\int_t^TY^{n,m}_s(Y^{n,m}_s-U_s)^+ds
\end{eqnarray*}
from $2ab\leq \beta a^2+\frac{1}{\beta}b^2$, we have
\begin{eqnarray}\nonumber
E(Y^{n,m}_t)^2+E(\int_t^T|Z^{n,m}_s|^2ds)&=&
E(\xi)^2+c(\alpha')E\int_t^Tg^2(s,0,0)ds+E\int_t^Tf^2(s,0,0)ds\\\nonumber
&
&+(2K+c(\alpha')+K^2\frac{2}{1-\alpha'})E\int_t^T|Y^{n,m}_s|^2ds+\frac{1+\alpha'}{2}E\int_t^T|Z^{n,m}_s|^2ds\\\nonumber
& & +\beta E(\sup_{s\leq
T}(L_s^+)^2)+\frac{1}{\beta}m^2E(\int_t^T(L_s-Y^{n,m}_s)^+ds)^2\\
& & +\beta E(\sup_{s\leq
T}(U_s^-)^2)+\frac{1}{\beta}n^2E(\int_t^T(Y^{n,m}_s-U_s)^+ds)^2
\end{eqnarray}
we use the fact that
$$(Y^{n,m}_s-L_s)(L_s-Y^{n,m}_s)^+\leq 0,\quad (Y^{n,m}_s-U_s)(Y^{n,m}_s-U_s)^+\geq 0$$
(2) We now prove there exists a constant $\bar{c}$ independent of
$n$, $m$, such that, for all $0\leq t\leq T$,
\begin{eqnarray}\nonumber
& &m^2E(\int_0^T(L_s-Y^{n,m}_s)^+ds)^2
+n^2E(\int_0^T(Y^{n,m}_s-U_s)^+ds)^2 \\&\leq &
\bar{c}(1+E\int_t^T|Y^{n,m}_s|^2ds+E\int_t^T|Z^{n,m}_s|^2ds)
\end{eqnarray}
for $0\leq t\leq T$, define
\begin{eqnarray*}
T_1=\inf(t\leq r\leq T, Y^{n,m}_r=U_r)\wedge T;\\
S_1=\inf(T_1< r\leq T, Y^{n,m_r=L_r})\wedge T;\\
T_2=\inf(S_1\leq r\leq T, Y^{n,m}_r=U_r)\wedge T;\quad \cdots
\mbox{and
so on.}\\
\end{eqnarray*}
Then $T_k\nearrow T$, $S_k\nearrow T$ as $k\rightarrow \infty$.\\
Since $L<U$ on $[0,T)$, we have $Y^{n,m}\geq L$ between $T_k$ and
$S_k$, so
\begin{eqnarray*}
Y^{n,m}_{T_k}&=&Y^{n,m}_{S_k}+\int_{T_k}^{S_k}f_n(s,Y^{n,m}_s,Z^{n,m}_s)ds-n\int_{T_k}^{S_k}(Y^{n,m}_s-U_s)^+ds\\
& &
+\int_{S_k}^{T_k}g(s,Y^{n,m}_s,Z^{n,m}_s)dB_s-\int_{T_k}^{S_k}Z_s^{n,m}dW_s
\end{eqnarray*}
on the other hand,
\begin{eqnarray*}
U_{T_k}=Y^{n,m}_{T_k}\geq X_{T_k} \quad\mbox{if}\quad T_k<T,\quad
Y^{n,m}_{T_k}=X_{T_k}=\xi \quad\mbox{if}\quad T_k=T
\end{eqnarray*}
\begin{eqnarray*}
Y^{n,m}_{S_k}=L_{S_k}\leq X_{S_k}\quad\mbox{if}\quad S_k<T, \quad
Y^{n,m}_{S_k}=X_{S_k}=\xi\quad\mbox{if}\quad S_k=T
\end{eqnarray*}
from above property, we get for all $k$,
\begin{eqnarray*}
n\int_{T_k}^{S_k}(Y^{n,m}_s-U_s)^+ds &\leq &
X_{S_k}-X_{T_k}+\int_{T_k}^{S_k}f(s,Y_s^{n,m},Z_s^{n,m})ds\\
& &
+\int_{T_k}^{S_k}f(s,Y_s^{n,m},Z_s^{n,m})dB_s-\int_{T_k}^{S_k}Z_s^{n,m}dW_s\\
&\leq &
\int_{T_k}^{S_k}|f(s,Y_s^{n,m},Z_s^{n,m})|ds+V^+_{S_k}-V^+_{T_k}+V^-_{S_k}-V^-_{T_k}\\
& &
+\int_{S_k}^{T_k}g(s,Y_s^{n,m},Z_s^{n,m})dB_s-\int_{T_k}^{S_k}(J_s+Z_s^{n,m})dW_s
\end{eqnarray*}
since between $S_k$ and $T_{k+1}$, $Y^{n,m}_s\leq U_s$, summing up
in $k$, we obtain
\begin{eqnarray*}
n\int_T^t(Y^{n,m}_s-U_s)^+ds &\leq &
\int_t^T|f(s,Y^{n,m}_s,Z^{n,m}_s)|ds+V^+_T-V_t^++V_T^--V_t^-\\
& &
+\int_t^Tg(s,Y^{n,m}_s,Z^{n,m}_s)(\sum_k{\mathbf{1}}_{[T_k,S_k)}(s))dB_s\\
& &
-\int_t^T(J_s+Z_s^{n,m})(\sum_k{\mathbf{1}}_{[T_k,S_k)}(s))dW_s
\end{eqnarray*}
Taking square and expectation, we get
\begin{eqnarray}\nonumber
& & n^2E(\int_T^t(Y^{n,m}_s-U_s)^+ds)^2+E(\int_t^T(J_s+Z_s^{n,m})(\sum_k{\mathbf{1}}_{[T_k,S_k)}(s))ds)^2\\
&\leq
&\frac12\bar{c}(1+E\int_t^T|Z_s^{n,m}|^2ds+E\int_t^T|Y_s^{n,m}|^2ds)
\end{eqnarray}
In the same way, we obtain
\begin{eqnarray}
m^2E(\int_T^t(L_s-Y^{n,m}_s)^+ds)^2\leq\frac12\bar{c}(1+E\int_t^T|Z_s^{n,m}|^2ds+E\int_t^T|Y_s^{n,m}|^2ds)
\end{eqnarray}
from (15) and (16), choosing $\beta=\frac{2\bar{c}}{\alpha'}$, we
get
$$E(Y^{n,m}_t)^2+\frac{1-\alpha'}{2}E(\int_t^T|Z^{n,m}_s|^2ds)\leq \bar{K}(1+E\int_t^T(Y^{n,m}_s)^2ds)$$
then from Gronwall's lemma,
$$\sup_{t\leq T}E(Y^{n,m}_t)^2\leq c,\quad E\int_t^T|Z_s^{n,m}|^2\leq c$$
so
$$m^2E(\int^T_t(L_s-Y^{n,m}_s)^+ds)^2\leq c,\quad n^2E(\int^T_t(Y^{n,m}_s-U_s)^+ds)^2\leq c\quad \quad \Box$$

we now introduce the follow one reflected BDSDE $(\xi,f,g,L)$ for
all integer.
\begin{eqnarray}\nonumber
Y^n_t &=& \xi+\int_t^Tf(s,Y^n_s,Z^n_s)ds+K_T^{n,+}-K^{n,+}_t-n\int_t^T(Y^n_s-U_s)^+ds\\
& & +\int_t^Tg(s,Y_s^n,Z_s^n)dB_s-\int_t^TZ^n_sdW_s
\end{eqnarray}
from Burkholder-Davis-Gundy inequality,
$$E(\sup_{0\leq t\leq T}(Y^{n,m}_t)^2)\leq c$$
As $m\rightarrow\infty$, $Y^{n,m}\nearrow Y^n$,
$m\int_0^T(L_s-Y^{n,m}_s)^+ds\nearrow K_T^{n,+}$,
$Z^{n,m}\rightarrow Z^n$ in $M^2$.[KKPPQ]\\
 where $(Y^n,Z^n,K^{n,+})$ is
the unique solution of Eq$(\xi,f,g,L)$. Then

{\bf Lemma 7.2.}
\begin{eqnarray}
E(\sup_{t\leq
T}(Y^n_t)^2)+E\int_0^T|Z^n_s|^2ds+E(K_T^{n,+})^2+n^2E\int_0^T(Y^n_s-U_s)^+ds)^2\leq
c
\end{eqnarray}
where the constant $c$ is independent of $n$.\\
For Eq$(\xi,f,g,L)$, we know $Y^n\geq L$, a.s. and from the
comparison theorem [GS] that $Y^n\searrow$, we conclude that there
exists a process $Y$ such that $Y^n\searrow Y$, and from Fatou's
Lemma,
$$E(\sup_{t\leq T}Y^2_t)\leq c$$
then follows by the dominated convergence theotem that,
$$E(\int_0^T(Y_t-Y^n_t)^2dt)\longrightarrow 0,\quad \mbox{as}\quad n\rightarrow \infty$$
Now if $n\geq p$, $Y^n\leq Y^p$, $dK^{n,+}\geq dK^{p,+}$ by the
comparison theorem [GS]. Then we want to prove that
$Z^n\rightarrow Z$ in $M^2$, as $n\rightarrow\infty$.

{\bf Lemmma 7.3.} $Z^n\rightarrow Z$ in $M^2$ as $n\rightarrow
\infty$.

{\bf proof.} we define
$\widetilde{K}_t^T=n\int_0^t(Y^n_s-U_s)^+ds$, $n>p$.\\
Applying It$\hat{o}$'s formula to $Y^n-Y^p$ and $y\rightarrow
y^2$,
\begin{eqnarray*}
E(Y^n_t-Y^p_t)^2+E\int_t^T|Z^n_s-Z^p_s|^2ds &=& 2E\int_t^T(Y^n_s-Y^p_s)(f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s))ds\\
& &
+2E\int_t^T(Y^n_s-Y^p_s)(dK_s^{n,+}-dK^{p,+}_s)\\
& & -2E\int_t^T(Y^n_s-Y^p_s)(d\widetilde{K}_s^{n,+}-d\widetilde{K}^{p,+}_s)\\
& &+E\int_t^T(g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s))^2ds \\
&\leq
&2E\int_t^T(Y^n_s-Y^p_s)(f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s))ds\\
& &  -2E\int_t^T(Y^n_s-Y^p_s)(d\widetilde{K}_s^{n,+}-d\widetilde{K}^{p,+}_s)\\
& & +E\int_t^T(g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s))^2ds \\
\end{eqnarray*}
where we have use
$$(Y^n_s-Y^p_s)(d\widetilde{K}_s^{n,+}-d\widetilde{K}^{p,+}_s)=[(Y^n_s-U_s)+(U_s-Y^p_s)](d\widetilde{K}_s^{n,+}-d\widetilde{K}^{p,+}_s)$$
and $(Y^n_s-U_s)d\widetilde{K}_s^{n,+}\geq 0$,
$(U_s-Y^p_s)d\widetilde{K}^{p,+}_s\leq 0$, we obtain
\begin{eqnarray*}
E(Y^n_t-Y^p_t)^2+\frac{1-\alpha}{2}E\int_t^T|Z^n_s-Z^p_s|^2ds &=&
cE\int_t^T(Y^n_s-Y^p_s)^2ds\\
& & +2E(\sup_{t\leq T}((Y^n_s-U_s)^+)^2)\cdot
E(p\int_t^T(Y^p_s-U_s)^+ds)^2\\
& &+2E(\sup_{t\leq T}((Y^p_s-U_s)^+)^2)\cdot
E(n\int_t^T(Y^n_s-U_s)^+ds)^2
\end{eqnarray*}
Now, we prove $E(\sup_{t\leq T}((Y^n_s-U_s)^+)^2)\rightarrow 0$,
as $n\rightarrow \infty$. \\
We consider the following Eq$(\xi,f(s,Y^n_s,Z^n_s)-n(y-U_s),g,L)$,
\begin{eqnarray*}
\hat{Y}^n_t &=& \xi+\int_t^Tf(s,Y^n_s,Z^n_s)ds+\widetilde{K}_T^{n,+}-\widetilde{K}^{n,+}_t-n\int_t^T(\hat{Y}^n_s-U_s)ds\\
& & +\int_t^Tg(s,Y_s^n,Z_s^n)dB_s-\int_t^T\hat{Z}^n_sdW_s
\end{eqnarray*}
which has a unique solution, denoted
$(\hat{Y}^n,\hat{Z}^n,\widetilde{K}^n)$. From the comparison
theorem [GS], $Y^n_t\leq \hat{Y}^n_t$, a.s. for all $0\leq t\leq
T$.\\
Then we have the following reflected BDSDE:
\begin{eqnarray*}
e^{-nt}\hat{Y}^n_t &=& e^{-nT}\xi+\int_t^Te^{-ns}f(s,Y^n_s,Z^n_s)ds+\int_t^Te^{-ns}d\widetilde{K}_t^{n,+}+n\int_t^Te^{-ns}U_sds\\
& &
+\int_t^Te^{-ns}g(s,Y_s^n,Z_s^n)dB_s-\int_t^Te^{-ns}\hat{Z}^n_sdW_s
\end{eqnarray*}
This process $\{e^{-nt}Y^n_t\}$ is the solution of the BDSDE with
the obstacle $\{e^{-nt}L_t\}$ with terminal value $e^{-nt}\xi$ and
coefficients $e^{-nt}f(t,Y^n_t,Z^n_t)+ne^{-nt}U_t$ and
$g(t,Y^n_t,Z^n_t)$.\\
Let $\nu$ be a stopping time such that $0\leq \nu \leq T$, then
\begin{eqnarray*}
\hat{Y}^n_{\nu}&=&ess\sup_{\tau\geq \nu}\{E(\xi
e^{-n(\tau-\nu)}{\mathbf{1}}_{\{\tau
=T\}}+L_{\tau}e^{-n(\tau-\nu)}{\mathbf{1}}_{\{\tau
<T\}}+n\int_{\nu}^{\tau}e^{-n(s-\nu)}U_sds)\\
& &
+\int_{\nu}^{\tau}e^{-n(s-\nu)}f(s,Y^n_s,z^n_s)ds|{\cal{F}}_{\nu})+\int_{\nu}^{\tau}e^{-n(s-\nu)}f(s,Y^n_s,z^n_s)dB_s\}\\
&\leq &
E(n\int_{\nu}^{\tau}e^{-n(s-\nu)}(U_s-X_s)ds|{\cal{F}}_{\nu})+E(\int_{\nu}^{\tau}e^{-n(s-\nu)}|f(s,Y^n_s,z^n_s)|ds|{\cal{F}}_{\nu})\\
& & +ess\sup_{\tau\geq\nu}E(n\int_{\nu}^{\tau}X_se^{-n(s-\nu)}ds+
e^{-n(\tau-\nu)}X_{\tau}{\mathbf{1}}_{\{\tau
<T\}}+e^{-n(\tau-\nu)}\xi{\mathbf{1}}_{\{\tau=T\}}|{\cal{F}}_{\nu})\\
&
&+ess\sup_{\tau\geq\nu}\int_{\nu}^{\tau}e^{-n(s-\nu)}g(s,Y^n_s,z^n_s)dB_s
\end{eqnarray*}
where we have use $L_t\leq X_t\leq U_t$, a.s. $t\in [0,T]$.\\
It is easily seen that
$$n\int_{\nu}^{\tau}e^{-n(s-\nu)}(U_s-X_s)ds\rightarrow (U_t-X_t){\mathbf{1}}_{\{\tau
<T\}},\quad n\rightarrow \infty$$ a.s. and in $\mathbf{L}^2$, and
the conditional expectation convergence also in $\mathbf{L}^2$.
and
$$\int_{\nu}^{\tau}e^{-n(s-\nu)}|f(s,Y^n_s,z^n_s)|ds\leq \frac{1}{\sqrt{2n}}(\int_0^Tf^2(s,Y^n_s,z^n_s)ds)^{\frac12}$$
hence,
$$E(\int_{\nu}^{\tau}e^{-n(s-\nu)}|f(s,Y^n_s,z^n_s)|ds|{\cal{F}}_{\nu})\rightarrow 0 $$
in $\mathbf{L}^2$ as $n\rightarrow\infty$. \\
moreover,
\begin{eqnarray*}
E(ess\sup_{\tau\geq\nu}(\int_{\nu}^{\tau}e^{-n(s-\nu)}g(s,Y^n_s,z^n_s)dB_s)^2)&\leq&
cE\int_0^Te^{-2n(s-\nu)}g^2(s,Y^n_s,z^n_s)ds\\
&\leq & cE(e^{-4n(s-\nu)}ds\cdot
\int_0^Tg^4(s,Y^n_s,z^n_s))^{\frac12}\\
&\leq &
\frac{c}{4n}E(\int_0^Tg^4(s,Y^n_s,z^n_s))^{\frac12}\rightarrow 0
\end{eqnarray*}
in $\mathbf{L}^2$, as $n\rightarrow \infty$. \\
Now consider the second term at the right of the above inequality,
since
$$e^{-n(\tau-\nu)}X_{\tau}+n\int_{\nu}^{\tau}e^{-n(s-\nu)}X_sds=X_{\nu}\int_{\nu}^{\tau}e^{-n(s-\nu)}dX_s$$
we have
\begin{eqnarray*}
& & ess\sup_{\tau\geq\nu}E(n\int_{\nu}^{\tau}X_se^{-n(s-\nu)}ds+
e^{-n(\tau-\nu)}X_{\tau}{\mathbf{1}}_{\{\tau
<T\}}+e^{-n(\tau-\nu)}\xi{\mathbf{1}}_{\{\tau=T\}}|{\cal{F}}_{\nu})\\
&=&ess\sup_{\tau\geq\nu}E(X_{\nu}+\int_{\nu}^{\tau}e^{-n(s-\nu)}dX_s|{\cal{F}}_{\nu})\\
&\leq &X_{\nu}{\mathbf{1}}_{\{\nu <T\}}+\xi {\mathbf{1}}_{\{\nu
=T\}}+E(\int_{\nu}^{\tau}e^{-n(s-\nu)}d(V^++V^-)_s|{\cal{F}}_{\nu})
\end{eqnarray*}
since
$E(\int_{\nu}^{\tau}e^{-n(s-\nu)}d(V^++V^-)_s|{\cal{F}}_{\nu})\rightarrow
0 $ in $\mathbf{L}^2$, as $n\rightarrow \infty$. We obtain finally
$$Y_{\nu}\leq \hat{Y}_{\nu}\leq U_{\nu}{\mathbf{1}}_{\{\nu
<T\}}+\xi {\mathbf{1}}_{\{\nu =T\}}\leq U_{\nu},\quad a.s.$$ From
above and the section theorem of Dellacherie and Meyer [DM], it
follows that, $Y_t\leq U_t$, $0\leq t\leq T$, a.s. \\
Hence $(Y^n_t-U_t)^+\searrow 0$, $0\leq t\leq T$, a.s., and from
Dini's theorem the convergence in uniformly in $t$. Then, the
result finally follows by the dominated convergence theorem, since
$(Y^n_t-U_t)^+\leq (Y^0_t-U_t)^+\leq |Y^0_t|+|U_t|$.\quad\quad
$\Box$

{\bf Lemma 7.4.} The process $Y$ is a continuous process.

{\bf Proof.} Let $n>p$. Using It$\hat{o}$'s formula to $Y^n-Y^p$
and $y\rightarrow y^2$,
\begin{eqnarray*}
(Y^n_t-Y^p_t)^2+\int_t^T|Z^n_s-Z^p_s|^2ds &=& 2\int_t^T(Y^n_s-Y^p_s)(f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s))ds\\
& & -2\int_t^T(Y^n_s-Y^p_s)(d\widetilde{K}_s^{n,+}-d\widetilde{K}^{p,+}_s)\\
& &+\int_t^T(g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s))^2ds \\
& &
+\int_t^T(Y^n_s-Y^p_s)(g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s))dB_s\\
& & -\int_t^T(Y^n_s-Y^p_s)(Z^n_s-Z^p_s)dW_s\\
\end{eqnarray*}
then
\begin{eqnarray*}
E(\sup_{t\leq T}(Y^n_t-Y^p_t)^2)+E\int_t^T|Z^n_s-Z^p_s|^2ds &\leq & E\int_t^T|Y^n_s-Y^p_s|\cdot|f(s,Y^n_s,Z^n_s)-f(s,Y^p_s,Z^p_s)|ds\\
& &+\int_t^T|g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s)|^2ds\\
& & +2E(\sup_{t\leq T}(Y^n_t-U_t)^+\cdot p\int_0^T(Y^p_s-U_s)^+ds\\
& & +2E(\sup_{t\leq T}(Y^p_t-U_t)^+\cdot n\int_0^T(Y^n_s-U_s)^+ds\\
& &+E(\sup_{t\leq T}\int_t^T|(Y^n_s-Y^p_s)(g(s,Y^n_s,Z^n_s)-g(s,Y^p_s,Z^p_s))dB_s|)\\
& &+E(\sup_{t\leq T}\int_t^T|(Y^n_s-Y^p_s)(Z^n_s-Z^p_s)dW_s|\\
\end{eqnarray*}
Using B-D-G inequality and $f$ and $g$ is uniformly Lipschitz in
$(y,z)$, we deduce,
$$E(\sup_{t\leq T}(Y^n_t-Y^p_t)^2)\rightarrow 0,\quad \mbox{as}\quad n,p\rightarrow \infty $$
from which we get that $Y^n$ convergence uniformly in $t$ to $y$,
$P\_a.s.$ and that $Y$ is continuous process.\quad\quad$\Box$


TITLE: Construction of the petit Zariski topos out of the gros topos of a scheme
QUESTION [17 upvotes]: Let S be a scheme. Let (Sch/S) be a small category of schemes over S (including essentially all finitely presented schemes affine over S). Let E = (Sch/S)zar denote the gros Zariski topos with its local ring object A1.
Is there a nice way to construct the petit Zariski topos X = Szar out of the locally ringed topos E? (By nice I mean, for example, that there is a universal property that the locally ringed topos X possesses with respect to E.)
There are variations of this question in which I am also interested: For example, one can replace E by the gros étale (or fppf or fpqc) topos (Sch/S)ét and ask for the construction  of Szar out of (Sch/S)ét. Or one can replace X by the petit étale (or fppf or fpqc) topos Sét and ask for the construction of it out of E = (Sch/S)zar.

REPLY [5 votes]: Many of these toposes admit descriptions as internal classifying toposes, hence indeed enjoy useful universal properties. Here is a selection of such descriptions:
Constructing the big Zariski topos from the little Zariski topos. The big Zariski topos of a scheme $S$ is the externalization of the result of constructing, internally to the little Zariski topos of $S$, the classifying topos of local $\mathcal{O}_S$-algebras which are local over $\mathcal{O}_S$.
(One might hope that it would simply be the internal big Zariski topos of $\mathcal{O}_S$, that is the classifying topos of local $\mathcal{O}_S$-algebras where the structure morphism needn't be local. This alternative description is true if $S$ is of dimension $0$.)
Constructing the little Zariski topos from the big Zariski topos. Additionally to $\mathbf{A}^1$, which is the functor $T \mapsto \Gamma(T,\mathcal{O}_T)$, the big Zariski topos contains an additional local ring object: The functor $\flat \mathbf{A}^1$, which maps an $S$-scheme $(f : T \to S)$ to $\Gamma(T,f^{-1}\mathcal{O}_S)$. There is a local ring homomorphism $\flat \mathbf{A}^1 \to \mathbf{A}^1$, and the little Zariski topos can be characterized as the largest subtopos of the big Zariski topos where this morphism is an isomorphism. (This fits with the comments as follows. If $S = \operatorname{Spec}(A)$ is affine, we have the string of ring homomorphisms $\underline{A} \to \flat \mathbf{A}^1 \to \mathbf{A}^1$ starting in the constant sheaf $\underline{A}$. The map $\underline{A} \to \flat \mathbf{A}^1$ is always a localization, and the composition is iff $\flat \mathbf{A}^1 \to \mathbf{A}^1$ is an isomorphism.)
Constructing the big étale topos from the big Zariski topos. The big étale topos of a scheme $S$ is the largest subtopos of the big Zariski topos of $S$ where $\mathbf{A}^1$ is separably closed. This fact is essentially a restatement of Gavin Wraith's theorem on what the big étale topos classifies.
Constructing the big infinitesimal topos from the little Zariski topos. A back-of-the-envelope computation indicates that the recent result of Matthias Hutzler on what the infinitesimal topos of an affine scheme classifies can be relativized to the non-affine case as follows. The big infinitesimal topos of a scheme $S$ is the externalization of constructing, internally to the little Zariski topos of $S$, the classifying topos of local and local-over-$\mathcal{O}_S$ $\mathcal{O}_S$-algebras equipped with a nilpotent ideal.
Some details can be found in Sections 12 and 21 of these notes.
A word of warning: When I say "the largest subtopos where foo", I refer to the largest element in the poset of subtoposes which validate foo from their internal language. (By general abstract nonsense (more or less the existence of classifying toposes), such a largest element always exists in case foo is a set-indexed conjunction of geometric implications.) In particular, I'm not referring to "the subtopos of those objects $Y$ of $E$ such that $\mathbf{A}^1$ restricted to $Y$ enjoys foo" (as in the comments). Indeed, this category is in general not a subtopos (typically it doesn't contain the terminal object). Maybe I interpreted that phrase too literally.


TITLE: Determinant of matrices with independent indeterminates entries
QUESTION [0 upvotes]: Let $R$ be a unique factorization domain, let $X=(x_{ij})_{1\leq i\leq n,1\leq j\leq n}$, be a family of independent indeterminates, and let $R_{nn}$ be the polynomial ring $R[x_{11},x_{12},...,x_{21},x_{22},...,x_{nn}]$. Let $D_{n}\in R_{nn}$ be the determinant of the $n\times n $ matrix $X$, and let $D_{n-1}\in R_{nn}$ be the cofactor of $x_{nn}$, i.e. the determinant of the matrix obtained from the above one by deleting the $n$th row and column.

The question is:
  (1) if $n>1$, then in $R_{nn}$, $D_{n-1}$ doesn't divide $D_{n}$;
  (2) $D_{n}$ generates a prime ideal in $R_{nn}$.

REPLY [2 votes]: Both statements are immediate consequences of the fact that the determinant $D_n$ is an irreducible polynomial, as is proved in this question.


text:
\section{Analysis}
\label{sec.analysis}

In this section we analyze the performance of AMB in terms of expected regret. As the performance is sensitive to the specific distribution of the processing times of the computing platform used, we first present a generic  analysis in terms of the number of epochs processed and the size of the minibatches processed by each node in each epoch. Then in Sec. \ref{sec.shiftExpDist}, in order to illustrate the advantages of AMB, we assert a probabilistic model on the processing time and analyze the performance in terms of the elapsed ``wall time'' .

\subsection{Preliminaries}
We assume that the feasible space $W \in \mathbb R^d$ of the primal optimization variable $w$ is a closed and bounded convex set where $D = \max_{w,u \in W} \|w-u\|$. Let $\|\cdot\|$ denote the $\ell_2$ norm. We assume the objective function $f(w,x)$ is convex and differentiable in $w \in W$ for all $x \in X$. We further assume that $f(w,x)$ is Lipschitz continuous with constant $L$, i.e.
\begin{align}\label{eqn:function.lipchitz}
	|f(w,x)- f(\tilde w,x)| \leq L\|w-\tilde w\|, \;\;\; \forall \, x
        \in X, {\rm and} \ \forall \, w,\tilde w \in W.
\end{align}
Let $\nabla f(w,x)$ be the gradient of $f(w,x)$ with respect to
$w$. We assume the gradient of $f(w,x)$ is Lipschitz continuous with constant $K$, i.e.,
\begin{align}\label{eqn:gradient.lipchitz}
	\|\nabla f(w,x)-\nabla f(\tilde w,x)\| \leq K\|w-\tilde w\|, \;\;\; \forall \, x \in X,  {\rm and} \,\forall \, w,\tilde w \in W.
\end{align}
As mentioned in Sec.~\ref{sec.algOutline},
\begin{align}
	\label{eqn:unbiased}
	F(w)=\mathbb E[f(w,x)],
\end{align}
where the expectation is taken with respect to the (unknown) data
distribution $Q$, and thus $\nabla F(w)=\mathbb E[\nabla f(w,x)]$.  We
also assume that there exists a constant $\sigma$ that bounds the second
moment of the norm of the gradient so that
\begin{align}
	\mathbb E[\| \nabla f(w,x) - \nabla F(w) \|^2] \leq \sigma^2,
        \forall \, x \in X, {\rm and} \, \forall \, w \in W.
\end{align}
Let the global minimum be denoted $w^* :=\arg \min_{w \in W} F(w)$.

\subsection{Sample path analysis}
First we bound the consensus errors.
Let $z(t)$ be the exact dual variable without any consensus errors at each node
\begin{align}\label{exact.dual}
z(t)=\bar{z}(t-1)+g(t-1).
\end{align}
The following Lemma bounds the consensus errors, which is obtained using \cite[Theorem 2]{tsianos2016efficient}
{\Lemma  Let $z_i^{(r)}(t)$ be the output after $r$ rounds consensus. Let $\lambda_2(P)$ be the second eigenvalue of the matrix $P$ and let  $\epsilon\geq 0$, then
	\begin{equation}
	\|z_i^{(r)}(t)-z(t)\| \leq \epsilon, \;\; \forall i \in [n], t \in [\tau],
	\end{equation}
	if the number of consensus rounds satisfies
	\begin{align}
	r_i(t) \geq \left\lceil\frac{\log\left(2\sqrt{n}(1+2L/\epsilon)\right)}{1-\lambda_2(P)}\right\rceil, \;\; \forall i \in [n], t \in [\tau].
	\end{align}
	\label{Lemma.consensus.error}
}
We characterize the regret after $\tau$ epochs, averaging over the data distribution but keeping a fixed ``sample path'' of per-node minibatch sizes $b_i(t)$. We observe that due to the time spent in communicating with other nodes via consensus, each node has computation cycles that could have been used to compute more gradients had the consensus phase been shorter (or nonexistent). To model this, let $a_i(t)$ denote the number of {\em additional} gradients that node $i$ {\em could have} computed had there been no consensus phase. This undone work does not impact the system performance, but does enter into our characterization of the regret. Let $c_i(t)=b_i(t)+a_i(t)$ be the total number of gradients that node $i$ had the potential to compute during the $t$-th epoch. Therefore, the total potential data samples processed in the $t$-th epoch is $c(t)=\sum_{i=1}^{n}c_i(t)$. After $\tau$ epochs the total number of data
points that could have been processed by all nodes in the absence of communication delays is
\begin{align}

	m = \sum_{t=1}^{\tau} c(t). \label{eq.totalData}
\end{align}

\iffalse
An important quantity is the ratio of total {\em potential} computations in each epoch to that actually completed. Define the maximum such minibatch ``skewness'' as
\begin{align}
\label{eq.batchSkewness}
	\gamma = \max_{t \in [\tau-1]} \frac{c(t+1)}{b(t)}.
\end{align}
It turns out that it is important to compute this skewness across epochs (i.e., $c(t+1)$ versus $b(t)$) in order to bound the regret via a telescoping sum. [Details can be found in the supplementary material.]
\fi

In practice, $a_i(t)$ and $b_i(t)$ (and therefore $c_i(t)$) depend on latent effects, e.g., how many other virtual machines are co-hosted on node $i$, and therefore we model them as random variables. We bound the expected regret for a fixed sample path of $a_i(t)$ and $b_i(t)$. The sample paths
of importance are $c_{\rm tot}(\tau) = \{c_i(t)\}_{i \in V, t \in
  [\tau]}$ and $b_{\rm tot}(\tau) = \{b_i(t)\}_{i \in V, t \in
  [\tau]}$, where we introduce $c_{\rm tot}$ and $b_{\rm tot}$ for notational
compactness.

Define the average regret after $\tau$ epochs as
\begin{equation}
	\label{eqn:first.regret}
	R(\tau) = \mathbb E\big[R|b_{\rm tot}(\tau), c_{\rm tot}(\tau) \big]= \mathbb E\left[\sum_{t=1}^{\tau} \sum_{i=1}^{n} \sum_{s=1}^{c_i(t)} \Big[f\big(w_i(t), x_i(t,s)\big)-F(w^*)\Big]\right],
\end{equation}
where the expectation is taken with respect the the i.i.d.~sampling from the distribution $Q$. Then, we have the following bound on $R(\tau)$.
\begin{theorem}
\label{thm.samplePath}

Suppose workers collectively processed $m$ samples after $\tau$ epochs, cf.~(\ref{eq.totalData}), and let $c_{\max} = \max _{t \in [\tau]} c(t)$, and $\mu = (1/\tau)\sum_{t=1}^{\tau} c(t)$ be the maximum, and the average across $c(t)$, respectively. Further, suppose the averaging consensus has additive accuracy $\epsilon$, cf.~Lemma \ref{Lemma.consensus.error}. Then, the expected regret is

\iffalse
Suppose workers collectively processed $m$ samples after $\tau$ epochs, cf.~(\ref{eq.totalData}), minibatch skewness parameter $\gamma$, cf.~(\ref{eq.batchSkewness}), and let $c_{\max} = \max _{t \in [\tau]} c(t)$, $c_{\rm avg} = (1/\tau)\sum_{t=1}^{\tau} c(t)$ and $\delta=\max_{\{t,t'\} \in \{1,\tau-1\}} |c(t)-c(t')|$ be the maximum, average, and variation across $c(t)$. Further, suppose the averaging consensus has additive accuracy $\epsilon$, cf.~Lemma \ref{Lemma.consensus.error}. Then, the expected regret is
\fi

	\begin{multline}
	R(\tau)\leq  c_{\max} [F(w(1))-F(w^*) +\beta(\tau)h(w^*)] +\frac{3K^2\epsilon^2c_{\max} \mu ^{3/2}}{4} \\ + \left(2K D \epsilon +\frac{ \sigma^2 }{2}   + 2L\epsilon \right)c_{\max}\sqrt{m}. \label{eqn:thm1}
	\end{multline}
\end{theorem}
Theorem~\ref{thm.samplePath} is proved in App.~\ref{app.pfThmSampPath} of the supplementary material.

We now make a few comments about this result. First, recall that the expectation is taken with respect to the data distribution, but holds for any sample path of minibatch sizes. Further, the regret bound depends only on the summary statistics $c_{\max}$ and $\mu$. Further, the impact of consensus error, which depends on the communication speed relative to the processing speed of each node, is summarized in the assumption of uniform accuracy $\epsilon$ on the distributed averaging mechanism. Thus, Theorem \ref{thm.samplePath} is a sample path result that depends only coarsely on the distribution of the speed of data processing.

Next, observe that the dominant term is the final one, which scales in the aggregate number of samples $m$. The first term is approximately constant, only scaling
with the monotonically increasing $\beta$ and $c_{\max}$ parameters.
The terms containing $\epsilon$ characterizes the effect of imperfect
consensus, which can be reduced by increasing the number of rounds of
consensus. If perfect consensus were achieved ($\epsilon = 0$) then
all components of the final term that scales in $\sqrt{m}$ would
disappear except for the term $c_{\max}\sigma^2/2$.

\iffalse
We now make a few comments about this result. First, recall that the expectation is taken with respect to the data distribution, but holds for any sample path of minibatch sizes. Further, the regret bound depends only on the summary statistics $c_{\max}$, $c_{\rm avg}$, $\delta$, and $\gamma$. These parameters capture the distribution of the processing speed at each node. Further, the impact of consensus error, which depends on the communication speed relative to the processing speed of each node, is summarized in the assumption of uniform accuracy $\epsilon$ on the distributed averaging mechanism. Thus, Theorem \ref{thm.samplePath} is a sample path result that depends only coarsely on the distribution of the speed of data processing.

Next, observe that the dominant term is the final one, which scales in the aggregate number of samples $m$. The first term is approximately constant, only scaling
with the monotonically increasing $\beta$ and $c_{\max}$ parameters.
The terms containing $\epsilon$ characterizes the effect of imperfect
consensus, which can be reduced by increasing the number of rounds of
consensus. The effect of variability across $c(t)$ is reflected in
the terms containing the $c_{\max}$, $c_{\rm avg}$ and $\delta$
parameters. If perfect consensus were achieved ($\epsilon = 0$) then
all components of the final term that scales in $\sqrt{m}$ would
disappear except for the term that contains the minibatch skewness
parameter $\gamma$. It is through this term that the amount of useful
computation performed in each epoch ($b_i(t) \leq c_i(t)$) enters the
result.
\fi

In the special case of constant minibatch size $c(t) = c$ for all $t \in [\tau]$; hence $c_{\rm max}=\mu=c$, we have the following corollary.
\begin{corollary}
\label{cor.samplePath}
If $c(t)=c$ for all $t \in [\tau]$ and the consensus error $\epsilon$ is bounded,
then the expected regret is
\begin{align}
	R(\tau) = \mathcal O (\sqrt{m}).
\end{align}
\end{corollary}

\iffalse
\begin{corollary}
\label{cor.samplePath}
If $c(t)=c$ for all $t \in [\tau]$ and the consensus error $\epsilon
\leq 1/c$, then the expected regret is
\begin{align}
	R(\tau) = \mathcal O (c+\sqrt{m}).
\end{align}
Furthermore, if $c=m^\rho$ for a constant $\rho \in (0,1/2]$, then $R(\tau)  = \mathcal O (\sqrt{m})$.
\end{corollary}
\fi

\subsection{Expected regret analysis}

\iffalse
We can translate Theorem~\ref{thm.samplePath} and Cor.~\ref{cor.samplePath} to a regret bound averaged over the sample path. Since the summary statistics $c_{\max}$, $c_{\rm avg}$, $\delta$, and $\gamma$ are sufficient to bound the regret, we assert a joint distribution $p$ over these terms rather than over the sample path $b_{\rm tot}(\tau), c_{\rm tot}(\tau)$. For the following result, we need only specify several moments of the distribution. In Sec.~\ref{sec.shiftExpDist} we will take the further step of choosing a specific distribution $p$.
\fi

\iffalse
\begin{theorem}
\label{thm.expWork}
Let $\bar c = \mathbb E_p [c(t)]$ so that $\bar m = \tau \bar c$
  is the expected total work that can be completed in $\tau$ epochs.
  Also, let $1/\hat b = \mathbb E_p[1/b(t)]$.  If averaging consensus has additive accuracy $\epsilon$, then the
  expected regret is bounded by
\begin{align}
\mathbb E_p[R(\tau)] &\leq  \bar c\big[F(w(1))-F(w^*)  +\bar \beta(\tau)h(w^*)\big] +\frac{3 K^2\epsilon^2\bar c^{5/2}}{4}   \nonumber  + \left(2K D \epsilon +\frac{ \bar c\sigma^2 }{2\hat b}+ 2 L\epsilon \bar c \right) \sqrt{\bar m } .
\end{align}
\end{theorem}
\fi

We can translate Theorem~\ref{thm.samplePath} and Cor.~\ref{cor.samplePath} to a regret bound averaged over the sample path by asserting a joint distribution $p$ over the sample path $b_{\rm tot}(\tau), c_{\rm tot}(\tau)$. For the following result, we need only specify several moments of the distribution. In Sec.~\ref{sec.shiftExpDist} we will take the further step of choosing a specific distribution $p$.

\begin{theorem}
\label{thm.expWork}
Let $\bar c = \mathbb E_p [c(t)]$ so that $\bar m = \tau \bar c$
  is the expected total work that can be completed in $\tau$ epochs.
  Also, let $\hat c = \mathbb E_p[c_i(t)]$ so that $\bar c = n \hat c$ and let $1/\hat b = \mathbb E_p[1/b(t)]$ .  If averaging consensus has additive accuracy $\epsilon$, then the
  expected regret is bounded by
\begin{align}
\mathbb E_p[R(\tau)] &\leq  \bar c\big[F(w(1))-F(w^*)  +\bar \beta(\tau)h(w^*)\big] +\frac{3 K^2\epsilon^2\bar c^{5/2}}{4}   \nonumber  + \left(2K D \epsilon +\frac{ \bar c\sigma^2 }{2\hat b}+ 2 L\epsilon \bar c \right) \sqrt{\bar m }.
\end{align}
\end{theorem}

Theorem \ref{thm.expWork} is proved in App.~\ref{app.pfThmExp} of the supplementary material. Note that this expected regret is over both the i.i.d.~choice of data samples and the i.i.d.~choice of $(b(t), c(t))$ pairs.

\begin{corollary}
\label{cor.expWork}
If $\epsilon \leq 1/\bar c$, the expected regret is
	\begin{align}
	\mathbb E_p[R(\tau)]   \leq \mathcal O (\bar c+\sqrt{\bar m}).
	\end{align}
	Further, if $\bar c=\bar m^\rho$ for a constant $\rho \in (0,1/2)$, then $\mathbb E[R]   \leq \mathcal O (\sqrt{\bar m})$.
\end{corollary}

{\remark Note that by letting $\epsilon=0$, we can immediately find the results for master-worker setup.}


TITLE: Why is the kinetic energy a fixpoint of the Legendre transformation?
QUESTION [4 upvotes]: Question: Why is (from an intuitive standpoint) the kinetic energy $T$ a fixpoint of the Legendre transformation, i.e. $\frac{\partial T}{\partial \dot q}\dot q-T = T$ for any general coordinate $q$? Can I derive this without Lagrangian or Hamiltonian mechanics?
Background: I noticed that I can derive $\frac{\partial T}{\partial \dot q}\dot q-T = T$ from Lagrangian / Hamiltonian mechanics via ($q$ is any general coordinate):
$$\begin{align}
H & = \frac{\partial L}{\partial \dot q} \dot q - L \\
\implies\ T+V &= \frac{\partial (T-V)}{\partial \dot q} \dot q - (T-V) \\
\implies\ T+V &= \frac{\partial T}{\partial \dot q} \dot q - T + V \\
\implies\ T &= \frac{\partial T}{\partial \dot q} \dot q - T
\end{align}$$
Now I asked myself why it makes intuitively sense that the kinetic energy is a fixpoint of the Legendre transformation. It doesn't seem to be a coincidence...

REPLY [1 votes]: Let the Lagrangian have the traditional form
$$ \mathcal{L}(q,\dot{q};t) = \frac{\dot{q}^2}{2} - V(q) \, ,$$
where $V(q)$ represents the potential energy. We see that the condition
$$ \frac{\partial \mathcal{L}(q,\dot{q};t)}{\partial q} = - \frac{\partial V(q)}{\partial q} = 0 $$
describes extrema of the Hamiltonian
$$H(p,q) = p \dot{q} - \mathcal{L}(q,\dot{q};t) = \frac{p^2}{2} + V(q) \, , \quad \text{where}
 \qquad p = \frac{\partial \mathcal{L}(q,\dot{q};t)}{\partial \dot{q}} \, .$$
Since the Legendre transformation is defined as a sup, i.e for each evaluation point $p$ we have
$$ f^*(p) = \sup_{\dot{q}} \left(  p \dot{q} - \mathcal{L}(q,\dot{q};t)\right) \, ,$$
the fact that the Legendre transform maps the kinetic energy to itself is equivalent to saying that the point where the potential energy vanishes, which is an extremum of the Lagrangian, will also be an extremum of the Hamiltonian. This is fundamental, since fixed points must have the same stability properties in either Lagrangian or Hamiltonian formulations: An unstable equilibrium in the Lagrangian description must be mapped to an unstable equilibrium in the Hamiltonian description, etc. The definition of the Legendre transform as a suppremum guarantees that the graph of $f^*(p)$ will be convex, being bounded above/below  by the points where $V(q)=0$, i.e. by the kinetic energy.
All of the above can be generalized to non-convex functions using convex duals, but I don't know enough to elaborate.
Regarding your interest in Legendre transformations outside of coordinate-free formulations of mechanics (not talking about thermodynamics here), I would say they're simply not useful. Legendre transforms have no meaning in Newtonian mechanics apart from their abstract mapping of points into lines, which is quite useless unless your formulation takes place on a cotangent bundle.


TITLE: Why don't absorption and emission lines cancel out in our Sun?
QUESTION [14 upvotes]: I was looking at this answer on why absorption lines and emission lines don't cancel out:

An experiment shining light on the material and looking at the
  reflected spectrum will see absorption lines at those frequencies,
  because the relaxation of the excited electrons will emit back
  radiation all around randomly, whereas the reflected spectrum is at a
  specific angle.

However it is not totally convincing to me. The photons that get emitted towards the center of the Sun (by the electrons in higher energy states that absorbed a photon earlier) would get absorbed again when they hit a different electron (and then re-emitted) and would eventually make it out. So why don't absorption and emission lines cancel out in our Sun?

REPLY [10 votes]: The key point missing from most efforts to answer this question are that the Sun has a temperature gradient with depth. If it were (somehow) isothermal, then indeed the absorption and emission processes would cancel and the Sun's spectrum would be a smooth blackbody.
The photons we see from the Sun, were those that were able to escape from its photosphere - an outer layer only a few hundred km in thickness.
The interior of the Sun is hotter than layers further out and the radiation field approximates to a blackbody, with a radiation flux that is strongly temperature dependent. The strong temperature dependence, combined with the negative temperature gradient means that the solar spectrum is produced by the hottest layers we can see.
Why the emphasis? Well, the depth we can see into the Sun is wavelength dependent. Where there are strong radiative transition probabilities, the light coming from the interior is absorbed. The re-emitted light (it has to be re-emitted if the material is in thermal equilibrium) is emitted in a random direction and a negligible fraction comes towards us.
I think there are two key points. One is the random direction of the re-emission of absorbed energy, but the other is the temperature gradient which means there is a clear outward directionality to the net radiative flux which means you can treat the Sun as a succession of cooler "slabs" as one moves outward.
The net effects are absorption lines. A good way to think about the solar spectrum is that at each wavelength you are seeing a (roughly) blackbody spectrum emitted at the temperature of the layer from which photons at that wavelength can escape. Thus the bottom of an absorption line is emitted at cooler temperatures, closer to the "surface", whilst continuum comes from hotter, deeper layers, but at wavelengths where the opacity is lower so that the photons are still able to make it out.

REPLY [8 votes]: I think that this is a very good question.
In my answer I will only mention the formation of one of the absorption lines, the 589 nm of sodium, and I will call the photon associated with that wavelength a "sodium photon".
What I will try to explain with reference to that particular wavelength of light will be true for all the other wavelengths for which absorption occurs.
The schematic layout of a standard demonstration of absorption and emission lines is shown below.

At position $A$ one would see an absorption spectrum and at position $B$ an emission spectrum and the "re-radiated in all directions" explanation works very well.
The difference with the Sun is that the "sodium flame" envelopes the Sun and the rate of "sodium photons" emerging from the Sun is less than the rate of emergence of photons with comparable wavelengths.
I think that the OP is asking "Where do the re-radiated sodium photons go?"
The fact is that the rate at which sodium photons escape from the "sodium flame blanket" around the Sun (the Sun's outer layers) is smaller than the rate at which photons close in wavelength escape.
So in effect that outer layer of the Sun is fairly opaque to sodium photons.
As the sodium photons which are being produced in the internal layers of the Sun progress through the outer layers of the Sun they get absorbed and re-radiated so the net rate in the forward (away from the Sun) direction decreases and there is a flux of sodium photons heading back towards the Sun.
Here they interact with the hotter "inner" layers of the Sun and do not necessarily emerge again as sodium photons, their wavelength is changed.
They are thermalised (I cannot think of a better wording).
Those sodium photons enter regions within the Sun where they they are in excess of what might expect for the distribution of wavelength for the temperature of those inner layers.
Interactions within those layers reduce that excess number of sodium photons, so they cease to be sodium photons.
So the net effect is that the "sodium flame blanket" around the Sun sends back towards the Sun sodium photons which are then transformed into photons of other wavelengths.


text:
Now we present our main results.

\paragraph{Main Result for Episodic MDP}
The following theorem characterizes the performance of Algorithm~\ref{algo:ucb-q} for episodic MDP.
To our knowledge, this is the first theoretical result showing a model-free algorithm can achieve logarithmic regret of tabular RL.
\begin{theorem}[Logarithmic Regret Bound of $Q$-learning for Episodic MDP]
	\label{thm:episodic}
	The expected regret of Algorithm~\ref{algo:ucb-q} for episodic tabular MDP is upper bounded by

	 $\expect{\regret(K)}\le\cO\left(\frac{H^6SA}{\gapmin}
	\log\left({SAT}\right)\right)$.

\end{theorem}

An interesting advantage of our theorem is adaptivity.
Note the algorithm we analyze is exactly the same algorithm studied in \cite{jin2019provably}, which has been shown to achieve the worst-case $\sqrt{T}$-type regret bound.
Theorem~\ref{thm:episodic} suggests that one does not need to modify the algorithm to exploit the strictly positive minimum sub-optimality gap structure, Algorithm~\ref{algo:ucb-q} \emph{automatically adapts} to this benign structure.
Importantly, Algorithm~\ref{algo:ucb-q} does not need to know $\gapmin$.

Proposition 2.2 in \cite{max2019nonasymptotic} suggested that any algorithm with sub-linear regret in the worst case, suffer an $\Omega\left(\sum_{(x,a), \gap_1(x,a) > 0}\frac{H^2}{\gap_1\left(x,a\right)} \log T\right)$ expected regret.
Therefore, the dependencies on $S$, $A$ and $T$ are nearly tight in Theorem~\ref{thm:episodic}.

One may wonder whether it is possible to obtain a regret bound that only depends the sum of positive gaps, e.g., $O\left(\sum_{(x,a), \gap_1(x,a) > 0}\frac{H^2}{\gap_1\left(x,a\right)} \log T\right)$, unlike ours, which is a multiple of $1/\gapmin$.
Unfortunately, \citet{max2019nonasymptotic} showed, all existing algorithms, including Algorithm~\ref{algo:ucb-q} and their algorithm, suffer an $\Omega\left(\frac{S}{\gapmin}\right)$ regret, and new algorithmic ideas are needed in order to circumvent this lower bound.

We compare Theorem~\ref{thm:episodic} with the regret bound for model-based algorithm in \cite{max2019nonasymptotic} (in big-$\cO$ form):\begin{align*}
\Bigg(\!&\!\sum_{\substack{(x,a): \\\exists h \in [H], \gap_{h}\!(x,a) >0 }}\!\frac{H^3}{\min_h \gap_h\left(x,a\right)} + \frac{SH^3}{\gap_{\min}} \\
&+ H^4SA\max\left(S,H\right) \log\!\left(\!\frac{SAH}{\gapmin}\!\right)\Bigg)\log\left(SAHT\right)
\end{align*}

First recall our bound is for a model-free algorithm which is more space-efficient and time-efficient than the model-based algorithm in \cite{max2019nonasymptotic}.
In terms of the regret bound, Theorem~\ref{thm:episodic}'s dependency on $H$ is worse than that in their bound.
We remark that simple model-free algorithms may have a worse dependency on $H$ compared to model-based algorithms (e.g., see \cite{jin2018qlearning}).

Now let us consider an environment where there are $\sim SA$ state-action pairs whose gap is $\gapmin$.
Then the bound in \cite{max2019nonasymptotic} becomes \[
\left(\!\frac{H^3SA}{\gapmin} \!+\! H^4SA \max\!\left\{S,\!H\right\}\!\log\!\left(\!\frac{SAH}{\gapmin}\!\right)\!\right)\! \log\!\left(\!SAHT\!\right).
\]
In this regime, both Theorem~\ref{thm:episodic} and their bound have an $\frac{SA}{\gapmin}$ term.
Their bound also has an additional $H^4 SA\max\left(H,S\right) \log\left(\frac{SAH}{\gapmin}\right)$ burn-in term which our bound does not have.
When $S$ is large compared to $H$ and $\gap_{\min}$, this term scales $S^2$ and can dominate other terms, so our bound is better.
The technical reason behind this phenomenon is that Algorithm~\ref{algo:ucb-q} uses the Hoeffding bound for constructing bonus on $Q$-value, which does not need burn-in.

\paragraph{Main Result for Infinite-horizon Discounted MDP}
Algorithm~\ref{algo:ucb-q} can be easily generalized to the discounted MDP.
See Algorithm~\ref{algo:infinite ucb-q} in the appendix.
We also obtain a logarithmic regret bound for infinite-horizon discounted MDP.

\begin{theorem}[Logarithmic Regret Bound of $Q$-learning for Infinite-horizon Discounted MDP]
	\label{thm:discounted}

	The expected regret of Algorithm~\ref{algo:infinite ucb-q} for infinite-horizon discounted MDP is upper bounded by
	$\expect{\regret(T)}\le\cO\left(\frac{SA}{\gapmin\discount^6}
	\log\frac{SAT}{\gapmin\left(1-\gamma\right)}\right)$.
\end{theorem}
Theorem~\ref{thm:discounted} suggests that model-free algorithms can achieve logarithmic regret even in the infinite-horizon discounted MDP setting.
The main difference from Theorem~\ref{thm:episodic} is that $H$ is replaced by $\frac{1}{1-\gamma}$.
By analogy, we believe the dependencies on $S,A,T$ and $\gapmin$ are nearly tight and the dependency $\frac{1}{1-\gamma}$ can be improved.
The proof of Theorem~\ref{thm:discounted} is deferred to Appendix.


TITLE: Prove a function is constant over an interval
QUESTION [2 upvotes]: Suppose $f$ is a function of $\mathbb{R}$ and satisfies $$\forall \ x_0 \in \mathbb{R},\ \exists \  \delta > 0,\ f(x_0) \geq f(x),\ \forall x \in (x_0 - \delta, x_0 + \delta).$$
Prove that there exists a nondegenerate interval $I$, $f$ is constant over $I$.
There are no conditions on the continuity of $f$, so I don't know where to start. I tried the principle of nested intervals but failed.
Any kind of help is appreciated and thank you very much in advance!

REPLY [1 votes]: From the answer linked in comments, we know $f$ attains at most countably many values.  Thus by formulation BCT3 of the Baire category theorem, we know there exists some $y\in \mathbb{R}$ such that $f^{-1}(y)$ is not nowhere dense. That is there exists a closed interval $I$, such that $f^{-1}(y)$ is dense on $I$.
Thus the minimum value of $f$ on $I$ is $y$, as no smaller value can be a local maximum.  Pick $x\in {\rm int}(I)$ with $f(x)=y$.  We have some closed interval $x\in J\subseteq I$ with the maximum value of $f$ on $J$ being $y$.
We already know the minimum value of $f$ on $J$ is $y$.  Thus $f$ is constant on $J$.