text:
(*****************************************************************************
 * HOL-TestGen --- theorem-prover based test case generation
 *                 http://www.brucker.ch/projects/hol-testgen/
 *
 * UPF
 * This file is part of HOL-TestGen.
 *
 * Copyright (c) 2005-2012 ETH Zurich, Switzerland
 *               2008-2015 Achim D. Brucker, Germany
 *               2009-2017 Université Paris-Sud, France
 *               2015-2017 The University of Sheffield, UK
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *
 *     * Redistributions in binary form must reproduce the above
 *       copyright notice, this list of conditions and the following
 *       disclaimer in the documentation and/or other materials provided
 *       with the distribution.
 *
 *     * Neither the name of the copyright holders nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 ******************************************************************************)

section\<open>Elementary Policies\<close>
theory
  ElementaryPolicies
  imports
    UPFCore
begin
text\<open>
  In this theory, we introduce the elementary policies of UPF that build the basis
  for more complex policies. These complex policies, respectively, embedding of
  well-known access control or security models, are build by composing the elementary
  policies defined in this theory.
\<close>

subsection\<open>The Core Policy Combinators: Allow and Deny Everything\<close>

definition
   deny_pfun    :: "('\<alpha> \<rightharpoonup>'\<beta>) \<Rightarrow> ('\<alpha> \<mapsto> '\<beta>)" ("AllD")
   where
  "deny_pfun pf \<equiv> (\<lambda> x. case pf x of
                          \<lfloor>y\<rfloor> \<Rightarrow> \<lfloor>deny (y)\<rfloor>
                         |\<bottom> \<Rightarrow> \<bottom>)"

definition
   allow_pfun    :: "('\<alpha> \<rightharpoonup>'\<beta>) \<Rightarrow> ('\<alpha> \<mapsto> '\<beta>)" ( "AllA")
   where
  "allow_pfun pf \<equiv> (\<lambda> x. case pf x of
                          \<lfloor>y\<rfloor> \<Rightarrow> \<lfloor>allow (y)\<rfloor>
                         |\<bottom> \<Rightarrow> \<bottom>)"

syntax
  "_allow_pfun"  :: "('\<alpha> \<rightharpoonup>'\<beta>) \<Rightarrow> ('\<alpha> \<mapsto> '\<beta>)" ("A\<^sub>p")
translations
  "A\<^sub>p f" \<rightleftharpoons> "AllA f"

syntax
  "_deny_pfun"  :: "('\<alpha> \<rightharpoonup>'\<beta>) \<Rightarrow> ('\<alpha> \<mapsto> '\<beta>)" ("D\<^sub>p")
translations
  "D\<^sub>p f" \<rightleftharpoons> "AllD f"

notation
   "deny_pfun"  (binder "\<forall>D" 10) and
   "allow_pfun" (binder "\<forall>A" 10)

lemma AllD_norm[simp]: "deny_pfun (id o (\<lambda>x. \<lfloor>x\<rfloor>)) = (\<forall>Dx. \<lfloor>x\<rfloor>)"
  by(simp add:id_def comp_def)

lemma AllD_norm2[simp]: "deny_pfun (Some o id) = (\<forall>Dx. \<lfloor>x\<rfloor>)"
  by(simp add:id_def comp_def)

lemma AllA_norm[simp]: "allow_pfun (id o Some) = (\<forall>Ax. \<lfloor>x\<rfloor>)"
  by(simp add:id_def comp_def)

lemma AllA_norm2[simp]: "allow_pfun (Some o id) = (\<forall>Ax. \<lfloor>x\<rfloor>)"
  by(simp add:id_def comp_def)

lemma AllA_apply[simp]: "(\<forall>Ax. Some (P x)) x = \<lfloor>allow (P x)\<rfloor>"
  by(simp add:allow_pfun_def)

lemma AllD_apply[simp]: "(\<forall>Dx. Some (P x)) x = \<lfloor>deny (P x)\<rfloor>"
  by(simp add:deny_pfun_def)

lemma neq_Allow_Deny: "pf \<noteq> \<emptyset> \<Longrightarrow> (deny_pfun pf) \<noteq> (allow_pfun pf)"
  apply (erule contrapos_nn)
  apply (rule ext)
  subgoal for x
    apply (drule_tac x=x in fun_cong)
    apply (auto simp: deny_pfun_def allow_pfun_def)
    apply (case_tac "pf x =  \<bottom>")
     apply (auto)
    done
  done

subsection\<open>Common Instances\<close>

definition allow_all_fun :: "('\<alpha> \<Rightarrow> '\<beta>) \<Rightarrow> ('\<alpha> \<mapsto> '\<beta>)" ("A\<^sub>f")
  where "allow_all_fun f =  allow_pfun (Some o f)"

definition deny_all_fun :: "('\<alpha> \<Rightarrow> '\<beta>) \<Rightarrow> ('\<alpha> \<mapsto> '\<beta>)" ("D\<^sub>f")
  where "deny_all_fun f \<equiv> deny_pfun (Some o f)"

definition
   deny_all_id   :: "'\<alpha> \<mapsto> '\<alpha>" ("D\<^sub>I") where
  "deny_all_id  \<equiv> deny_pfun (id o Some)"

definition
   allow_all_id    :: "'\<alpha> \<mapsto> '\<alpha>" ("A\<^sub>I") where
  "allow_all_id  \<equiv> allow_pfun (id o Some)"

definition
  allow_all    :: "('\<alpha> \<mapsto> unit)"  ("A\<^sub>U") where
  "allow_all p  = \<lfloor>allow ()\<rfloor>"

definition
  deny_all :: "('\<alpha> \<mapsto> unit)" ("D\<^sub>U") where
  "deny_all p   = \<lfloor>deny ()\<rfloor>"

text\<open>... and resulting properties:\<close>

lemma "A\<^sub>I  \<Oplus> Map.empty  = A\<^sub>I"
  by simp

lemma "A\<^sub>f f  \<Oplus> Map.empty  = A\<^sub>f f"
  by simp

lemma "allow_pfun Map.empty = Map.empty"
  apply (rule ext)
  apply (simp add: allow_pfun_def)
  done

lemma allow_left_cancel :"dom pf = UNIV \<Longrightarrow> (allow_pfun pf) \<Oplus> x = (allow_pfun pf)"
  apply (rule ext)+
  apply (auto simp: allow_pfun_def option.splits)
  done

lemma deny_left_cancel :"dom pf = UNIV \<Longrightarrow> (deny_pfun pf) \<Oplus> x = (deny_pfun pf)"
  apply (rule ext)+
  by (auto simp: deny_pfun_def option.splits)

subsection\<open>Domain, Range, and Restrictions\<close>

text\<open>
  Since policies are essentially maps, we inherit the basic definitions for
  domain and range on  Maps: \\
  \verb+Map.dom_def+ :  @{thm Map.dom_def} \\
  whereas range is just an abrreviation for image:
  \begin{verbatim}
  abbreviation range :: "('a => 'b) => 'b set"
  where -- "of function"  "range f == f ` UNIV"
  \end{verbatim}
  As a consequence, we inherit the following properties on
  policies:
  \begin{itemize}
  \item  \verb+Map.domD+ @{thm Map.domD}
  \item\verb+Map.domI+ @{thm Map.domI}
  \item\verb+Map.domIff+ @{thm Map.domIff}
  \item\verb+Map.dom_const+ @{thm Map.dom_const}
  \item\verb+Map.dom_def+ @{thm Map.dom_def}
  \item\verb+Map.dom_empty+ @{thm Map.dom_empty}
  \item\verb+Map.dom_eq_empty_conv+ @{thm Map.dom_eq_empty_conv}
  \item\verb+Map.dom_eq_singleton_conv+ @{thm Map.dom_eq_singleton_conv}
  \item\verb+Map.dom_fun_upd+ @{thm Map.dom_fun_upd}
  \item\verb+Map.dom_if+ @{thm Map.dom_if}
  \item\verb+Map.dom_map_add+ @{thm Map.dom_map_add}
  \end{itemize}
\<close>

text\<open>
  However, some properties are specific to policy concepts:
\<close>
lemma sub_ran : "ran p  \<subseteq> Allow \<union> Deny"
  apply (auto simp: Allow_def Deny_def ran_def full_SetCompr_eq[symmetric])[1]
  subgoal for x a
    apply (case_tac "x")
     apply (simp_all)
    done
  done

lemma dom_allow_pfun [simp]:"dom(allow_pfun f) = dom f"
  apply (auto simp: allow_pfun_def)
  subgoal for x y
    apply (case_tac "f x", simp_all)
    done
  done

lemma dom_allow_all: "dom(A\<^sub>f f) = UNIV"
  by(auto simp: allow_all_fun_def o_def)

lemma dom_deny_pfun [simp]:"dom(deny_pfun f) = dom f"
  apply (auto simp: deny_pfun_def)[1]
  apply (case_tac "f x")
  apply (simp_all)
  done

lemma dom_deny_all: " dom(D\<^sub>f f) = UNIV"
  by(auto simp: deny_all_fun_def o_def)

lemma ran_allow_pfun [simp]:"ran(allow_pfun f) = allow `(ran f)"
  apply (simp add: allow_pfun_def ran_def)
  apply (rule set_eqI)
  apply (auto)[1]
  subgoal for x a
    apply (case_tac "f a")
     apply (auto simp: image_def)[1]
     apply (auto simp: image_def)[1]
    done
  subgoal for xa a
    apply (rule_tac x=a in exI)
    apply (simp)
    done
  done

lemma ran_allow_all: "ran(A\<^sub>f id) = Allow"
  apply (simp add: allow_all_fun_def Allow_def o_def)
  apply (rule set_eqI)
  apply (auto simp: image_def ran_def)
  done

lemma ran_deny_pfun[simp]: "ran(deny_pfun f) = deny ` (ran f)"
  apply (simp add: deny_pfun_def ran_def)
  apply (rule set_eqI)
  apply (auto)[1]
  subgoal for x a
    apply (case_tac "f a")
     apply (auto simp: image_def)[1]
    apply (auto simp: image_def)[1]
    done
  subgoal for xa a
    apply (rule_tac x=a in exI)
    apply (simp)
    done
  done

lemma ran_deny_all: "ran(D\<^sub>f id) = Deny"
  apply (simp add: deny_all_fun_def Deny_def o_def)
  apply (rule set_eqI)
  apply (auto simp: image_def ran_def)
  done

text\<open>
  Reasoning over \verb+dom+ is most crucial since it paves the way for simplification and
  reordering of policies composed by override (i.e. by the normal left-to-right rule composition
  method.
  \begin{itemize}
    \item \verb+Map.dom_map_add+ @{thm Map.dom_map_add}
    \item \verb+Map.inj_on_map_add_dom+ @{thm Map.inj_on_map_add_dom}
    \item \verb+Map.map_add_comm+ @{thm Map.map_add_comm}
    \item \verb+Map.map_add_dom_app_simps(1)+ @{thm Map.map_add_dom_app_simps(1)}
    \item \verb+Map.map_add_dom_app_simps(2)+ @{thm Map.map_add_dom_app_simps(2)}
    \item \verb+Map.map_add_dom_app_simps(3)+ @{thm Map.map_add_dom_app_simps(3)}
    \item \verb+Map.map_add_upd_left+ @{thm Map.map_add_upd_left}
  \end{itemize}
  The latter rule also applies to allow- and deny-override.
\<close>

definition dom_restrict :: "['\<alpha> set, '\<alpha>\<mapsto>'\<beta>] \<Rightarrow> '\<alpha>\<mapsto>'\<beta>" (infixr "\<triangleleft>" 55)
where     "S \<triangleleft> p \<equiv> (\<lambda>x. if x \<in> S then p x else \<bottom>)"

lemma dom_dom_restrict[simp] : "dom(S \<triangleleft> p) = S \<inter> dom p"
  apply (auto simp: dom_restrict_def)
  subgoal for x y
    apply (case_tac "x \<in> S")
     apply (simp_all)
    done
  subgoal for x y
    apply (case_tac "x \<in> S")
     apply (simp_all)
    done
  done

lemma dom_restrict_idem[simp] : "(dom p) \<triangleleft> p = p"
  apply (rule ext)
  apply (auto simp: dom_restrict_def
      dest: neq_commute[THEN iffD1,THEN not_None_eq [THEN iffD1]])
  done

lemma dom_restrict_inter[simp] : "T \<triangleleft> S \<triangleleft> p = T \<inter> S \<triangleleft> p"
  apply (rule ext)
  apply (auto simp: dom_restrict_def
      dest: neq_commute[THEN iffD1,THEN not_None_eq [THEN iffD1]])
  done

definition ran_restrict :: "['\<alpha>\<mapsto>'\<beta>,'\<beta> decision set] \<Rightarrow> '\<alpha> \<mapsto>'\<beta>" (infixr "\<triangleright>" 55)
where     "p \<triangleright> S \<equiv> (\<lambda>x. if p x \<in> (Some`S) then p x else \<bottom>)"

definition ran_restrict2 :: "['\<alpha>\<mapsto>'\<beta>,'\<beta> decision set] \<Rightarrow> '\<alpha> \<mapsto>'\<beta>" (infixr "\<triangleright>2" 55)
where     "p \<triangleright>2 S \<equiv> (\<lambda>x. if (the (p x)) \<in> (S) then p x else \<bottom>)"

lemma "ran_restrict = ran_restrict2"
  apply (rule ext)+
  apply (simp add: ran_restrict_def ran_restrict2_def)
  subgoal for x xa xb
    apply (case_tac "x xb")
     apply simp_all
    apply (metis inj_Some inj_image_mem_iff)
    done
  done

lemma ran_ran_restrict[simp] : "ran(p \<triangleright> S) = S \<inter> ran p"
  by(auto simp: ran_restrict_def image_def ran_def)

lemma ran_restrict_idem[simp] : "p \<triangleright> (ran p) = p"
  apply (rule ext)
  apply (auto simp: ran_restrict_def image_def Ball_def ran_def)
  apply (erule contrapos_pp)
  apply (auto dest!: neq_commute[THEN iffD1,THEN not_None_eq [THEN iffD1]])
  done

lemma ran_restrict_inter[simp] : "(p \<triangleright> S) \<triangleright> T = p \<triangleright> T \<inter> S"
  apply (rule ext)
  apply (auto simp: ran_restrict_def
      dest: neq_commute[THEN iffD1,THEN not_None_eq [THEN iffD1]])
  done

lemma ran_gen_A[simp] : "(\<forall>Ax. \<lfloor>P x\<rfloor>) \<triangleright> Allow = (\<forall>Ax. \<lfloor>P x\<rfloor>)"
  apply (rule ext)
  apply (auto simp: Allow_def ran_restrict_def)
  done

lemma ran_gen_D[simp] : "(\<forall>Dx. \<lfloor>P x\<rfloor>) \<triangleright> Deny = (\<forall>Dx. \<lfloor>P x\<rfloor>)"
  apply (rule ext)
  apply (auto simp: Deny_def ran_restrict_def)
  done

lemmas ElementaryPoliciesDefs = deny_pfun_def allow_pfun_def allow_all_fun_def deny_all_fun_def
                                allow_all_id_def deny_all_id_def allow_all_def deny_all_def
                                dom_restrict_def ran_restrict_def

end

subset_name: curated


TITLE: finding the partial bell polynomial of $e^x$
QUESTION [4 upvotes]: $$
\left(e^{x+z} - e^x\right) = \sum_{n=1}^\infty \frac{z^n}{n!} \frac{d^n}{dx^n}[e^x]
$$
$$
\left(e^{x+z}-e^x\right)^k = \sum_{n \geq k} Y^{\Delta}_{e^x}(n,k,x)z^n
$$
Where:
$$
Y^{\Delta}(n,k,x) = \frac{k!}{n!}B_{n,k}^{e^x}(x)
$$
$$
[z^n]\left(e^{x+z}-e^x\right)^k = e^{kx}[z^n]\left(e^z-1\right)^k = e^{kx} \sum_{j=0}^k {k \choose j} [z^n]e^{zj} (-1)^{k-j}
$$
$$
e^{zj} = \sum_{n=0}^\infty \frac{(zj)^n}{n!}
$$
therefore:
$$
[z^n]e^{zj} = \frac{j^n}{n!}
$$
$$
B_{n,k}^{e^x}(x) = \frac{e^{kx}}{k!} \sum_{j=0}^k {k \choose j} j^n (-1)^{k-j}
$$
Can someone please check my work, im a bit wary about this...

REPLY [1 votes]: I think your calculation is correct.

Observe that
\begin{align*}
B_{n,k}^{e^x}(0)=\frac{1}{k!}\sum_{j=0}^k\binom{k}{j}j^n(-1)^{k-j}=\left\{n \atop k\right\}
\end{align*}
yield the Stirling Numbers of the second kind.


TITLE: Uniform convergence of real function
QUESTION [0 upvotes]: Let $f:[a,b] \to  \mathbb{C}$ where $0 < a < b < 2 \pi$ be defined by $f(x) = \sum_{k=1}^{\infty} \frac{exp(ikx)}{k}$. Show that $f$ converges uniformly in $[a,b]$.

The problem is that I do not know for what function is $f$ converging to. I think that maybe complex Fourier series might help here, but I'm not completely confortable with that tool.
Any help?

REPLY [0 votes]: HINT: In order to establish whether the series converges or not, you do not need to actually  know  its limit. You are only asked to establish the existence of the limit, so you can simply apply one of the Convergence Tests, e.g.  Dirichlet test.
PS Before applying these tests, it might be convenient to recall the Euler's Formula and split you series into two:
$$
e^{ix} = \cos x + i\sin x \implies f(x) = \sum_{k=1}^{\infty} \frac{e^{ikx} }{k}=
\sum_{k=1}^{\infty} \frac{\cos (kx)}{k} +i\sum_{k=1}^{\infty} \frac{\sin (kx)}{k},
$$
and then establish uniform convergence of each of the series individually.


TITLE: Convergence of series $\sum_{n=1}^{\infty}\frac{1}{2^{n-1}+3}$
QUESTION [2 upvotes]: Where does this series converges?
Using Ratio Test, I have checked that this series converges. Now I want to find the limit of this series.
$$\sum_{n=1}^{\infty}\frac{1}{2^{n-1}+3}$$
I would like to have some hint.

REPLY [4 votes]: There is no simple closed form for the summation but there is one
$$S=\sum_{n=1}^{\infty}\frac{1}{2^{n-1}+3}=\frac{2 \psi _2^{(0)}\left(-\frac{\log (3)+i \pi}{\log (2)}\right)+2 i \pi +\log
   (18)}{\log (64)}$$ where appears the digamma function.
Numerically $S=0.79528027349537094149502809561786001318781240072533$
You could have a quite good approximation making
$$S=\sum_{n=1}^{\infty}\frac{1}{2^{n-1}+3}=\sum_{n=1}^{k}\frac{1}{2^{n-1}+3}+\sum_{n=k+1}^{\infty}\frac{1}{2^{n-1}+3}\approx \sum_{n=1}^{k}\frac{1}{2^{n-1}+3}+\sum_{n=k+1}^{\infty}\frac{1}{2^{n-1}}$$
$$S\approx 2^{1-k}+\sum_{n=1}^{k}\frac{1}{2^{n-1}+3}$$ Using $k=10$ would give
$\frac{99630343269857}{125276421276160}\approx 0.795284 $ which is not too bad.
Edit
Making the problem more general,
$$S=\sum_{n=1}^{\infty}\frac{1}{2^{n-1}+a}=\frac{2 \psi _2^{(0)}\left(-\frac{\log (-a)}{\log (2)}\right)+2 \log (-a)+\log
   (2)}{a \log (4)}$$


TITLE: Law of large numbers: second moment tends to 0, but $S_n/n$ doesn't converge a.e.
QUESTION [3 upvotes]: What is an example of a sequence of random variables $\{X_n\}$ on a probability space $(\Omega, \mathscr{F}, P)$ such that $E\left(X_n^2\right) \to 0$ but it is not the case that
$$
\frac{S_n - E(S_n)}{n} \to 0
$$
almost everywhere. There is no assumption of independence of $\{X_n\}$.
See Chung's A Course in Probability Theory, problem 5.1.1, for reference.

Attempts

Take $P$ to be Lebesgue measure on the Borel sets $(0,1]$. Let $X_1 = 1$ on $(0,1]$, $X_2 = 1$ on $(0,0.5]$, $X_3 = 1$ on $(0.5,1]$, $X_4 = 1$ on $(0,1/3]$, and so on. This is an example to show convergence in probability does not imply convergence almost everywhere. This fails.
Take $X_n = 1$ on $(0,1/n]$. This fails.

REPLY [1 votes]: Some observations. Suppose that $\mathbb E\left[X_n^2\right]\to 0$.

We have $$\frac 1n\left\lvert  \mathbb E\left[S_n\right] \right\rvert\leqslant\frac 1n\sum_{i=1}^n\left\lVert X_i\right\rVert  _1\leqslant \frac 1n\sum_{i=1}^n\left\lVert X_i\right\rVert  _2\to 0                          .$$
Moreover, $\left\lVert\frac 1n\sum_{i=1}^n X_i\right\rVert  _2\to 0  $, so we have the convergence in probability to zero.

Consider your favorite sequence $\left(Y_i\right)_{i\geqslant 1}$ of non-negative random variables which converges to zero in $\mathbb L^2$ but not almost everywhere. For $2^N\leqslant n\leqslant 2^{N+1}-1$, define $X_n=Y_N$. Then
$$\frac 1{2^{N+1}}S_{2^{N+1}} \geqslant\frac 1{2^{N+1}}\sum_{i=2^N}^{2^{N+1}-1}X_i=\frac 12 Y_N.                      $$


TITLE: A trouble about the topology of pointwise convergence $({\mathbb{R}}^M,\tau)$
QUESTION [0 upvotes]: Let $(M,d)$ be a separable metric space and $F=\{f_{\lambda}:M\longrightarrow\mathbb{R}:\lambda\in L \}\subset \mathbb{R}^M $ be an equicontinuous family of uniformly bounded functions on $M$.
How can we prove that:
$\boxed{1}\;\; \overline{F}^{\tau}\subset ({\mathbb{R}}^M,\tau)$ is an equicontinuous and uniformly bounded family
$\boxed{2}\;$ $(\overline{F}^{\tau},\tau) \subset ({\mathbb{R}}^M,\tau)$ is metrizable
$L:$ set of indices
$\tau :$ topology of pointwise convergence $({\mathbb{R}}^M,\tau)$
The proof of this fact is analogous to Proposition $3.22$ ?
Any hints would be appreciated.

REPLY [1 votes]: You asked for hints, so I'm being "hintish..."
Definition of Uniformly Bounded is that $f_\lambda < N$ for some real number $N$ correct?  If so, all limits of sequences in $F$ are bounded by $N$, since every element in the sequence is bounded by $N$.
A similar argument holds for equicontinuous.
I don't immediately see how to metrize it, although my first gut is to hack out a supremum norm.  That would definitely work for M compact....  Ah, I bet you can metrize it by something like, $d(f_1,f_2) = \sum_{i=1}^\infty |f_1(s_i) - f_2(s_i) | / 2^i$ where the $s_i$ form a separable subset of $M$.
I'm not using the fact that $M$ is a metric space.... so I am probably missing something...


TITLE: For $(1+x+x^2)^n = A_0 + A_1x + ... + A_{2n}x^{2n}$, prove that $(n-r)A_r + (2n -r+1)A_{r-1} = (r+1)A_{r+1}$
QUESTION [0 upvotes]: My try:
One way to do this:

Differentiate the original expression
Divide the resultant expression with the original expression
Compare coefficients of $A_r$ on both sides

This will give the result.
Is there any other way(a more elegant one perhaps) to derive this result?

REPLY [0 votes]: Hint. By induction: compute $$(n+1-r)A^{n+1}_r+(2n+2-r+1)A^{n+1}_{r-1}$$ and write it as $(r+1)A^{n+1}_{r+1}$ using the relation $A^{n+1}_r=A^n_r+A^n_{r-1}+A^n_{r-2}$. If you group the terms smartly, this takes only a few lines...


text:
\begin{document}
\title[Pseudo-stopping times]{A definition and some characteristic properties of pseudo-stopping times}
\author{Ashkan Nikeghbali}
\address{Laboratoire de Probabilit\'{e}s et Mod\`{e}les Al\'{e}atoires\\
Universit\'{e} Pierre et Marie Curie, et CNRS UMR 7599\\
175, rue du Chevaleret F-75013 Paris, France \\
and C.R.E.S.T\\
( Centre de Recherche en Economie et Statistique Th\'{e}orique)}
\email{nikeghba@ccr.jussieu.fr}
\author{Marc Yor}
\address{Laboratoire de Probabilit\'{e}s et Mod\`{e}les Al\'{e}atoires\\
Universit\'{e} Pierre et Marie Curie, et CNRS UMR 7599\\
175, rue du Chevaleret F-75013 Paris, France}
\date{November 19, 2004}
\subjclass{60G07, 60G40, 60G44.} \keywords{Random times, Progressive
enlargement of filtrations, Optional stopping theorem, Martingales,
General theory of processes.}
\begin{abstract}
Recently, D. Williams \cite{williams} gave an explicit example of a random
time $\rho$ associated with Brownian motion such that $\rho$\ is not a
stopping time but $\mathbb{E}M_{\rho}=\mathbb{E}M_{0}$ for every bounded
martingale $M$. The aim of this paper is to give some characterizations for
such random times, which we call pseudo-stopping times, and to construct
further examples, using techniques of progressive enlargements of filtrations.

\end{abstract}
\maketitle

\section{Introduction}

Let $\left(  \Omega,\mathcal{F},\left(  \mathcal{F}_{t}\right)  _{t\geq
0},\mathbb{P}\right)  $ be a filtered probability space, and $\rho:$ $\left(
\Omega,\mathcal{F}\right)  \rightarrow\left(  \mathbb{R}_{+},\mathcal{B}
\left(  \mathbb{R}_{+}\right)  \right)  $ be a random time. We recall that the
space $\mathcal{H}^{1}$ is the Banach space of (c\`{a}dl\`{a}g) $\left(
\mathcal{F}_{t}\right)  $-martingales $\left(  M_{t}\right)  $ such that
\[
\left\Vert M\right\Vert _{\mathcal{H}^{1}}=\mathbb{E}\left[  \sup_{t\geq
0}\left\vert M_{t}\right\vert \right]  <\infty.
\]

\begin{definition}
We say that $\rho$ is a $\left(  \mathcal{F}_{t}\right)  $ pseudo-stopping
time if for every$\ \left(  \mathcal{F}_{t}\right)  $-martingale $\left(
M_{t}\right)  $ in $\mathcal{H}^{1}$, we have
\begin{equation}
\mathbb{E}M_{\rho}=\mathbb{E}M_{0}.\label{pta}
\end{equation}
\end{definition}

\begin{remark}
It is equivalent to assume that (\ref{pta}) holds for bounded martingales,
since these are dense in $\mathcal{H}^{1}$.
\end{remark}

\bigskip

We indicate immediately that a class of pseudo-stopping times with respect to
a filtration $\left(  \mathcal{F}_{t}\right)  $\ which are not in general
$\left(  \mathcal{F}_{t}\right)  $\ stopping times may be obtained by
considering stopping times with respect to a larger filtration $\left(
\mathcal{G}_{t}\right)  $\ such that $\left(  \mathcal{F}_{t}\right)  $ is
immersed in $\left(  \mathcal{G}_{t}\right)  $, i.e: every $\left(
\mathcal{F}_{t}\right)  $\ martingale is a $\left(  \mathcal{G}_{t}\right)
$\ martingale. This situation is described in (\cite{bremaudyor}) and refered
to there as the $\left(  H\right)  $\ hypothesis. We shall discuss this
situation in more details in Section 3. For now, we give an example. Let
$B_{t}=\left(  B_{t}^{1},\ldots,B_{t}^{d}\right)  $\ be a $d$-dimensional
Brownian motion, and $R_{t}=\left\vert B_{t}\right\vert $, $t\geq0,$ its
radial part; it is well known that
\[
\left(  \mathcal{R}_{t}\equiv\sigma\left\{  R_{s},\text{ }s\leq t\right\}
,\text{ }t\geq0\right)  ,
\]
the natural filtration of $R$,\ is immersed in $\left(  \mathcal{B}_{t}
\equiv\sigma\left\{  B_{s},\text{ }s\leq t\right\}  ,\text{ }t\geq0\right)  $,
the natural filtration of $B$. Thus an example of $\left(  \mathcal{R}
_{t}\right)  $\ pseudo-stopping time is:
\[
T_{a}^{\left(  1\right)  }=\inf\left\{  t,\text{ }B_{t}^{1}>a\right\}  .
\]

Recently, D. Williams \cite{williams} showed that with respect to the
filtration $\left(  \mathcal{F}_{t}\right)  $\ generated by a one dimensional
Brownian motion $\left(  B_{t}\right)  _{t\geq0}$, there exist pseudo-stopping
times $\rho$\ which are not $\left(  \mathcal{F}_{t}\right)  $\ stopping
times. D. Williams' example is the following: let
\[
T_{1}=\inf\left\{  t:\text{ }B_{t}=1\right\}  ,\text{ }\sigma=\sup\left\{
t<T_{1}:\text{ }B_{t}=0\right\}  ;
\]
then
\[
\rho=\sup\left\{  s<\sigma:\text{ }B_{s}=S_{s}\right\}  ,\text{ where }
S_{s}=\sup_{u\leq s}B_{u}
\]
is a $\left(  \mathcal{F}_{t}\right)  $\ pseudo-stopping time. This paper has
two main aims:

\begin{itemize}
\item to understand better the nature of pseudo-stopping times;

\item to construct further examples of pseudo-stopping times;\bigskip
\end{itemize}

In Section 2, with the help of the theory of progressive enlargements of
filtrations, we give some equivalent properties for $\rho$\ to be a
pseudo-stopping time. We also comment there on the difference between
(\ref{pta}) and the property
\begin{equation}
\mathbb{E}\left[  M_{\infty}\mid\mathcal{F}_{\rho}\right]  =M_{\rho
}\label{knimais}
\end{equation}
for every uniformly integrable $\left(  \mathcal{F}_{t}\right)  $-martingale
$\left(  M_{t}\right)  $, which was shown by Knight and Maisonneuve
\cite{Knight-Maisonneuve} to be equivalent to $\rho$\ being a $\left(
\mathcal{F}_{t}\right)  $-stopping time.\bigskip

In Section 3, we give some other examples of pseudo-stopping times. We
associate with the end $L$\ of a given $\left(  \mathcal{F}_{t}\right)
$\ predictable set $\Gamma$, i.e
\[
L=\sup\left\{  t:\left(  t,\omega\right)  \in\Gamma\right\}  ,
\]
a pseudo-stopping time $\rho<L$ in a manner which generalizes D. Williams'
example. We also link the pseudo-stopping times with randomized stopping times.\bigskip

In Section 4, we give a discrete time analogue of the Williams random time
$\rho$. This approach is based on the analogue of Williams' path decomposition
obtained by Le Gall for the standard random walk \cite{Le Gall}.

\section{Some characteristic properties of pseudo-stopping times}

\subsection{Basic facts about progressive enlargements}

We recall here some basic results about the progressive enlargement of a
filtration $\left(  \mathcal{F}_{t}\right)  $\ by a random time $\rho$. All
these results may be found in \cite{jeulinyor}, \cite{jeulin}, \cite{zurich},
\cite{delmaismey} or \cite{protter}.\bigskip

We enlarge the initial filtration $\left(  \mathcal{F}_{t}\right)  $\ with the
process $\left(  \rho\wedge t\right)  _{t\geq0}$, so that the new enlarged
filtration $\left(  \mathcal{F}_{t}^{\rho}\right)  _{t\geq0}$\ is the smallest
filtration containing $\left(  \mathcal{F}_{t}\right)  $\ and making $\rho$\ a
stopping time. A few processes play a crucial role in our discussion:

\begin{itemize}
\item the $\left(  \mathcal{F}_{t}\right)  $-supermartingale
\begin{equation}
Z_{t}^{\rho}=\mathbb{P}\left[  \rho>t\mid\mathcal{F}_{t}\right]
\label{surmart}
\end{equation}
chosen to be c\`{a}dl\`{a}g, associated to $\rho$\ by Az\'{e}ma (see
\cite{jeulin} for detailed references);

\item the $\left(  \mathcal{F}_{t}\right)  $-dual optional and predictable
projections of the process $1_{\left\{  \rho\leq t\right\}  }$, denoted
respectively by $A_{t}^{\rho}$ and $a_{t}^{\rho}$;

\item the c\`{a}dl\`{a}g martingale
\[
\mu_{t}^{\rho}=\mathbb{E}\left[  A_{\infty}^{\rho}\mid\mathcal{F}_{t}\right]
=A_{t}^{\rho}+Z_{t}^{\rho}
\]
which is in BMO($\mathcal{F}_{t}$) (see \cite{delmaismey} or \cite{zurich}).
We recall that the space of BMO martingales (see \cite{dellachmeyer} for more
details and references) is the Banach space of (c\`{a}dl\`{a}g) square
integrable $\left(  \mathcal{F}_{t}\right)  $-martingales $\left(
Y_{t}\right)  $ which satisfy
\[
\left\Vert Y\right\Vert _{BMO}^{2}=\mbox{essup} _{T}\mathbb{E}\left[  \left(
Y_{\infty}-Y_{T-}\right)  ^{2}\mid\mathcal{F}_{T}\right]  <\infty
\]
where $T$\ ranges over all $\left(  \mathcal{F}_{t}\right)  $-stopping times.
\end{itemize}

We also consider the Doob-Meyer decomposition of (\ref{surmart}):
\[
Z_{t}^{\rho}=m_{t}^{\rho}-a_{t}^{\rho}
\]
If $\rho$\ avoids any $\left(  \mathcal{F}_{t}\right)  $-stopping time, that
is to say $P\left[  \rho=T>0\right]  =0$ for any stopping time $T$, then
$A_{t}^{\rho}=a_{t}^{\rho}$ is continuous.\bigskip

Finally, we recall that every $\left(  \mathcal{F}_{t}\right)  $-local
martingale $\left(  M_{t}\right)  $, stopped at $\rho$, is a $\left(
\mathcal{F}_{t}^{\rho}\right)  $\ semimartingale, with canonical
decomposition:
\begin{equation}
M_{t\wedge\rho}=\widetilde{M}_{t}+\int_{0}^{t\wedge\rho}\frac{d<M,\mu^{\rho
}>_{s}}{Z_{s-}^{\rho}}\label{decocanonique}
\end{equation}
where $\left(  \widetilde{M}_{t}\right)  $\ is an $\left(  \mathcal{F}
_{t}^{\rho}\right)  $-local martingale.

\begin{remark}
We also recall that in a filtration $\left(  \mathcal{F}_{t}\right)  $\ where
all martingales are continuous, $A_{t}^{\rho}=a_{t}^{\rho}$ since optional
processes are predictable (see \cite{revuzyor}, chapter IV).
\end{remark}

\subsection{A characterization of pseudo-stopping times}

We now discuss some characteristic properties of pseudo-stopping times. We
assume throughout that $\mathbb{P}\left[  \rho=\infty\right]  =0$.\

\begin{theorem}
\label{mainthm}The following four properties are equivalent:

\begin{enumerate}
\item $\rho$\ is a $\left(  \mathcal{F}_{t}\right)  $\ pseudo-stopping time,
i.e (\ref{pta}) is satisfied;

\item $\mu_{t}^{\rho}\equiv1$, $a.s$

\item $A_{\infty}^{\rho}\equiv1$, $a.s$

\item every $\left(  \mathcal{F}_{t}\right)  $\ local martingale $\left(
M_{t}\right)  $ satisfies
\[
\left(  M_{t\wedge\rho}\right)  _{t\geq0}\text{ }is\text{ }a\text{
}local\text{ }\left(  \mathcal{F}_{t}^{\rho}\right)  \text{ }martingale.
\]

If, furthermore, all $\left(  \mathcal{F}_{t}\right)  $ martingales are
continuous, then each of the preceding properties is equivalent to

\item
\[
\left(  Z_{t}^{\rho}\right)  _{t\geq0}\text{ is a decreasing }\left(
\mathcal{F}_{t}\right)  \ \text{predictable process}
\]
\end{enumerate}
\end{theorem}

\begin{proof}
$\left(  1\right)  \Longrightarrow\left(  2\right)  $ For every square
integrable $\left(  \mathcal{F}_{t}\right)  $\ martingale $\left(
M_{t}\right)  $, we have
\[
\mathbb{E}\left[  M_{\rho}\right]  =\mathbb{E}\left[  \int_{0}^{\infty}
M_{s}dA_{s}^{\rho}\right]  =\mathbb{E}\left[  M_{\infty}A_{\infty}^{\rho
}\right]  =\mathbb{E}\left[  M_{\infty}\mu_{\infty}^{\rho}\right]  .
\]
Since $\mathbb{E}M_{\rho}=\mathbb{E}M_{0}=\mathbb{E}M_{\infty}$, we have
\[
\mathbb{E}\left[  M_{\infty}\right]  =\mathbb{E}\left[  M_{\infty}A_{\infty
}^{\rho}\right]  =\mathbb{E}\left[  M_{\infty}\mu_{\infty}^{\rho}\right]  .
\]
Consequently, $\mu_{\infty}^{\rho}\equiv1$, $a.s$,$\ $hence $\mu_{t}^{\rho
}\equiv1$, $a.s$ which is equivalent to: $A_{\infty}^{\rho}\equiv1$, $a.s$.
Hence, $2.$ and $3.$ are equivalent.

$\left(  2\right)  \Longrightarrow\left(  4\right)  .$ This is a consequence
of the decomposition formula (\ref{decocanonique}).

$\left(  4\right)  \Longrightarrow\left(  1\right)  .$ It suffices
to consider any $\mathcal{H}^{1}$-martingale $\left(  M_{t}\right)
$, which, assuming $4.$, satisfies: $\left(  M_{t\wedge\rho}\right)
_{t\geq0}$ is a martingale in the enlarged filtration, for which
$\rho$\ is a stopping time. Then as a consequence of the optional
stopping theorem applied in $\left(
\mathcal{F}_{t}^{\rho}\right)  $ at time $\rho$, we get
\[
\mathbb{E}\left[  M_{\rho}\right]  =\mathbb{E}\left[  M_{0}\right]  ,
\]
hence $\rho\ $is a pseudo-stopping time.

Finally, in the case where all $\left(  \mathcal{F}_{t}\right)  $\ martingales
are continuous, we show:

$\left.  a\right)  $ $\left(  2\right)  \Rightarrow\left(  5\right)  $ If
$\rho$\ is a pseudo-stopping time, then $Z_{t}^{\rho}$ decomposes as
\[
Z_{t}^{\rho}=1-A_{t}^{\rho}.
\]
As all $\left(  \mathcal{F}_{t}\right)  $\ martingales are continuous,
optional processes are in fact predictable, and so $\left(  Z_{t}^{\rho
}\right)  $\ is a predictable decreasing process.

$\left.  b\right)  $ $\left(  5\right)  \Rightarrow\left(  2\right)  $
Conversely, if $\left(  Z_{t}^{\rho}\right)  $\ is a predictable decreasing
process, then from the unicity in the Doob-Meyer decomposition, the martingale
part $\mu_{t}^{\rho}$ is constant, i.e. $\mu_{t}^{\rho}\equiv1$, $a.s$. Thus,
$\left(  2\right)  $ is satisfied.
\end{proof}

In the next proposition, we deal with uniformly integrable martingales
$\left(  M_{t}\right)  $ instead of martingales in $\mathcal{H}^{1}$ (or
$\mathcal{H}^{2},\ldots$).

\begin{proposition}
The following properties are equivalent:

\begin{enumerate}
\item $\rho$\ is a $\left(  \mathcal{F}_{t}\right)  $\ pseudo-stopping time;

\item for every uniformly integrable martingale
\[
\mathbb{E}\left[  \left\vert M_{\rho}\right\vert \right]  \leq\mathbb{E}
\left[  \left\vert M_{\infty}\right\vert \right]  .
\]
\end{enumerate}
\end{proposition}

\begin{remark}
In fact, we shall further show in the next proof, that for $\rho$\ a
pseudo-stopping time and for $\left(  M_{t}\right)  $\ a uniformly integrable
martingale:
\[
\mathbb{E}\left[  \left\vert M_{\rho}\right\vert \right]  <\infty,\text{ and
}\mathbb{E}\left[  M_{\rho}\right]  =\mathbb{E}\left[  M_{\infty}\right]  .
\]
\end{remark}

\begin{proof}
$\left(  1\right)  \Rightarrow\left(  2\right)  $ If $\left(  M_{t}\right)  $
is uniformly integrable, it may be decomposed as:
\begin{equation}
M_{t}=M_{t}^{\left(  +\right)  }-M_{t}^{\left(  -\right)  }\label{posnegpart}
\end{equation}
where
\[
M_{t}^{\left(  +\right)  }=\mathbb{E}\left[  M_{\infty}^{+}\mid\mathcal{F}
_{t}\right]  \text{ and }M_{t}^{\left(  -\right)  }=\mathbb{E}\left[
M_{\infty}^{-}\mid\mathcal{F}_{t}\right]  .
\]
(Note that $M_{\infty}^{\pm}$\ indicates the positive and negative parts of
$M_{\infty}$, whereas $\left(  M_{t}^{\left(  \pm\right)  }\right)  $\ are the
martingales with terminal values $M_{\infty}^{\pm}$). Thus to prove $\left(
2\right)  $ it suffices to prove
\[
\mathbb{E}\left[  M_{\rho}\right]  =\mathbb{E}\left[  M_{\infty}\right]  ,
\]
under the further assumption that $M\geq0$. In this latter case, we have
$M_{t}=\mathbb{E}\left[  M_{\infty}\mid\mathcal{F}_{t}\right]  $, with
$M_{\infty}\geq0$. Now let
\[
M_{t}^{\left(  n\right)  }=\mathbb{E}\left[  \left(  M_{\infty}\wedge
n\right)  \mid\mathcal{F}_{t}\right]  .
\]
$\left(  M_{t}^{\left(  n\right)  }\right)  $ is a bounded martingale, hence
we have
\[
\mathbb{E}\left[  M_{\infty}^{\left(  n\right)  }\right]  =\mathbb{E}\left[
M_{\rho}^{\left(  n\right)  }\right]  .
\]
We also have
\[
\mathbb{P}\left[  \sup_{t\geq0}\left(  M_{t}-M_{t}^{\left(  n\right)
}\right)  >\varepsilon\right]  \leq\frac{1}{\varepsilon}\mathbb{E}\left[
M_{\infty}-M_{\infty}^{\left(  n\right)  }\right]  ,
\]
so that $\left(  M_{\rho}^{\left(  n\right)  }\right)  $ converges to $\left(
M_{\rho}\right)  $ in probability; but the sequence $\left(  M_{\rho}^{\left(
n\right)  }\right)  $\ is increasing, so it in fact converges almost surely.
Hence the monotone convergence theorem yields
\[
\mathbb{E}\left[  M_{\infty}\right]  =\mathbb{E}\left[  M_{\rho}\right]  .
\]
Finally, going back to (\ref{posnegpart}) in the general case, we obtain:
\begin{align*}
\mathbb{E}\left[  \left\vert M_{\rho}\right\vert \right]   & \leq
\mathbb{E}\left[  M_{\rho}^{\left(  +\right)  }+M_{\rho}^{\left(  -\right)
}\right] \\
& =\mathbb{E}\left[  M_{\infty}^{+}+M_{\infty}^{-}\right] \\
& =\mathbb{E}\left[  \left\vert M_{\infty}\right\vert \right]  .
\end{align*}
Hence $\left(  2\right)  $ holds. Further, we may now write:
\begin{align*}
\mathbb{E}\left[  M_{\rho}\right]   & =\mathbb{E}\left[  M_{\rho}^{\left(
+\right)  }-M_{\rho}^{\left(  -\right)  }\right] \\
& =\mathbb{E}\left[  M_{\infty}^{+}-M_{\infty}^{-}\right] \\
& =\mathbb{E}\left[  M_{\infty}\right]  .
\end{align*}

$\left(  2\right)  \Rightarrow\left(  1\right)  $ We need only apply
property $\left(  2\right)  $ to any martingale $\left(
M_{t}\right)  $ taking values
in $\left[  0,1\right]  $. Thus:
\begin{align*}
\mathbb{E}\left[  M_{\rho}\right]   & \leq\mathbb{E}\left[  M_{\infty}\right]
\\
\mathbb{E}\left[  1-M_{\rho}\right]   & \leq\mathbb{E}\left[  1-M_{\infty
}\right]  .
\end{align*}
But, since the sums on both sides add up to $1$, we must have:
\[
\mathbb{E}\left[  M_{\rho}\right]  =\mathbb{E}\left[  M_{\infty}\right]
\]
Hence, $\rho$ is a $\left(  \mathcal{F}_{t}\right)  $\ pseudo-stopping time.
\end{proof}

As an application of the theorem, we can check that in D. Williams' example,
his time $\rho$ associated with a Brownian motion is a pseudo-stopping time.
Indeed, the dual predictable (=optional) projection $A_{t}^{\rho}$\ of
$1_{\left\{  \rho\leq t\right\}  }$ is max$_{s\leq t\wedge T_{1}}B_{s}$
(\cite{williams}, \cite{rogerswilliams}) and $A_{\infty}^{\rho}\equiv1$.

\subsection{Around the result of Knight and Maisonneuve}

We now comment on the statement of the fourth property in Theorem
\ref{mainthm}.

For the properties of the different sigma fields $\mathcal{F}_{\rho}$,
$\mathcal{F}_{\rho+}$, $\mathcal{F}_{\rho-}$, associated with a general random
time $\rho$, the reader can consult \cite{rogerswilliams} or \cite{zurich}.
Here, we just recall the definitions:

\begin{definition}
Three classical $\sigma$-fields associated with a filtration $\left(
\mathcal{F}_{t}\right)  \ $and any random time $\rho$ are:
\[
\left\{
\begin{array}
[c]{lcl}
\mathcal{F}_{\rho+} & = & \sigma\left\{  z_{\rho},\text{ }\left(
z_{t}\right)  \text{ any }\left(  \mathcal{F}_{t}\right)
\ \text{progressively measurable process}\right\}  ;\\
\mathcal{F}_{\rho} & = & \sigma\left\{  z_{\rho},\text{ }\left(  z_{t}\right)
\text{ any }\left(  \mathcal{F}_{t}\right)  \ \text{optional process}\right\}
;\\
\mathcal{F}_{\rho-} & = & \sigma\left\{  z_{\rho},\text{ }\left(
z_{t}\right)  \text{ any }\left(  \mathcal{F}_{t}\right)  \ \text{predictable
process}\right\}  ;
\end{array}
\right.
\]
\end{definition}

The result of Knight and Maisonneuve which was recalled in the introduction
may be stated as follows:

\begin{theorem}
If for all uniformly integrable $\left(  \mathcal{F}_{t}\right)  $-martingales
$\left(  M_{t}\right)  $, one has
\[
\mathbb{E}\left[  M_{\infty}\mid\mathcal{F}_{\rho}\right]  =M_{\rho},\qquad
on\text{ }\left\{  \rho<\infty\right\}  ,
\]
then $\rho$ is a $\left(  \mathcal{F}_{t}\right)  $-stopping time (the
converse is Doob's optional stopping theorem).
\end{theorem}

Refining slightly the argument in \cite{Knight-Maisonneuve}, we obtain the following:

\begin{theorem}
If for all bounded $\left(  \mathcal{F}_{t}\right)  $-martingales $\left(
M_{t}\right)  $, one has
\[
\mathbb{E}\left[  M_{\infty}\mid\mathcal{\sigma}\left\{  M_{\rho}
,\rho\right\}  \right]  =M_{\rho},\qquad on\text{ }\left\{  \rho
<\infty\right\}  ,
\]
then $\rho$ is a $\left(  \mathcal{F}_{t}\right)  $-stopping time.
\end{theorem}

\begin{proof}
For $t\geq0$\ we have
\[
\mathbb{E}\left[  M_{\infty}\mathbf{1}_{\left(  \rho\leq t\right)  }\right]
=\mathbb{E}\left[  M_{\rho}1_{\left(  \rho\leq t\right)  }\right]
=\mathbb{E}\left[  \int_{0}^{t}M_{s}dA_{s}^{\rho}\right]  =\mathbb{E}\left[
M_{\infty}A_{t}^{\rho}\right]  .
\]
Comparing the two extreme terms, we get
\[
\mathbf{1}_{\left(  \rho\leq t\right)  }=A_{t}^{\rho},
\]
i.e $\rho$\ is a $\left(  \mathcal{F}_{t}\right)  $-stopping time.\bigskip
\end{proof}

An interesting open question in view of what has been proved for
pseudo-stopping times is whether $\mathbb{E}\left[  M_{\infty}\mid M_{\rho
}\right]  =M_{\rho},$ $on$ $\left\{  \rho<\infty\right\}  $\ is equivalent to
$\rho$\ being a stopping time.\bigskip

To illustrate the result of Knight and Maisonneuve, we show explicitly how, in
the framework of D. Williams' example, $M_{\rho}$\ and $\mathbb{E}\left[
M_{\infty}\mid\mathcal{F}_{\rho}\right]  $\ differ, for
\[
M_{t}=\exp\left(  \lambda B_{t\wedge T_{1}}-\frac{\lambda^{2}}{2}\left(
t\wedge T_{1}\right)  \right)  ,\qquad\lambda>0.
\]
We write
\begin{align*}
M_{\infty}  & =\exp\left(  \lambda-\frac{\lambda^{2}}{2}T_{1}\right) \\
& =\exp\left(  \lambda\right)  \exp\left(  -\frac{\lambda^{2}}{2}\left(
\rho+\left(  \sigma-\rho\right)  +\left(  T_{1}-\sigma\right)  \right)
\right)
\end{align*}
and we compute:
\begin{align}
\mathbb{E}\left[  M_{\infty}\mid\mathcal{F}_{\rho}\right]   & =\label{trois}\\
& \exp\left(  \lambda-\frac{\lambda^{2}}{2}\rho\right)  \mathbb{E}\left[
\exp\left(  -\frac{\lambda^{2}}{2}\left(  \sigma-\rho\right)  \right)
\mid\mathcal{F}_{\rho}\right]  \mathbb{E}\left[  \exp\left(  -\frac{\lambda
^{2}}{2}\left(  T_{1}-\sigma\right)  \right)  \right]  ,
\end{align}
since $\left(  T_{1}-\sigma\right)  $ is independent from $\mathcal{F}
_{\sigma}$, (and consequently from $\mathcal{F}_{\rho}$, since $\mathcal{F}
_{\rho}\subset\mathcal{F}_{\sigma}$).

We now recall D. Williams' path decomposition results for $\left(
B_{u}\right)  _{u\leq T_{1}}$ on the intervals $\left(  0,\rho\right)  $,
$\left(  \rho,\sigma\right)  $, $\left(  \sigma,T_{1}\right)  $:

\begin{itemize}
\item $\left(  B_{\sigma+u}\right)  _{u\leq T_{1}-\sigma}$ is a BES$\left(
3\right)  $ process, independent of $\mathcal{F}_{\sigma}$; hence we have
\[
\mathbb{E}\left[  \exp\left(  -\frac{\lambda^{2}}{2}\left(  T_{1}
-\sigma\right)  \right)  \right]  =\frac{\lambda}{\sinh\left(  \lambda\right)
}.
\]

\item $S_{\rho}$, where $S_{s}=\sup_{u\leq s}B_{u}$, is uniformly distributed
on $\left(  0,1\right)  $;

\item Conditionally on $S_{\rho}=h$, the processes $\left(  B_{u}\right)
_{u\leq\rho}$ and $\left(  B_{\sigma-u}\right)  _{u\leq\sigma-\rho}$ are two
independent Brownian motions considered up to their first hitting time of $h$.
Consequently, we have:
\[
\mathbb{E}\left[  \exp\left(  -\frac{\lambda^{2}}{2}\left(  \sigma
-\rho\right)  \right)  \mid\mathcal{F}_{\rho}\right]  =\exp\left(  -\lambda
S_{\rho}\right)  .
\]
Plugging these informations in (\ref{trois}), we obtain:
\[
\mathbb{E}\left[  M_{\infty}\mid\mathcal{F}_{\rho}\right]  =\exp\left(
\lambda\left(  1-B_{\rho}\right)  -\frac{\lambda^{2}}{2}\rho\right)  \left(
\frac{\lambda}{\sinh\left(  \lambda\right)  }\right)  ,
\]
whilst
\begin{equation}
M_{\rho}=\exp\left(  \lambda B_{\rho}-\frac{\lambda^{2}}{2}\rho\right)
\end{equation}
and these two quantities are obviously different.
\end{itemize}

\subsection{Further properties of pseudo-stopping times}

Besides the assumption that $\rho$\ is a $\left(  \mathcal{F}_{t}\right)  $
pseudo-stopping time, we also make the hypothesis that $\rho$ avoids all
$\left(  \mathcal{F}_{t}\right)  $-stopping times. We saw that in this case
\[
a_{t}^{\rho}=A_{t}^{\rho}=1-Z_{t}^{\rho}
\]
is continuous.

For simplicity, we shall write $\left(  Z_{u}\right)  $\ instead of $\left(
Z_{u}^{\rho}\right)  $.

\begin{proposition}
\label{terminaval}Under the previous hypotheses, for all uniformly integrable
$\left(  \mathcal{F}_{t}\right)  $\ martingales $\left(  M_{t}\right)  $, and
all bounded Borel measurable functions $f$, one has:
\[
\mathbb{E}\left[  M_{\rho}f\left(  Z_{\rho}\right)  \right]  =\mathbb{E}
\left[  M_{0}\right]  \int_{0}^{1}f\left(  x\right)  dx=\mathbb{E}\left[
M_{\rho}\right]  \int_{0}^{1}f\left(  x\right)  dx.
\]
\end{proposition}

\begin{remark}
On the other hand it is not true that
\begin{equation}
\mathbb{E}\left[  M_{\infty}f\left(  Z_{\rho}\right)  \right]  =\mathbb{E}
\left[  M_{\rho}f\left(  Z_{\rho}\right)  \right]  ,\label{rhs}
\end{equation}
for every bounded Borel function $f$. Indeed, from Proposition
\ref{terminaval}, the right hand side of (\ref{rhs}) is equal to:
\[
\mathbb{E}\left[  M_{\infty}\int_{0}^{1}f\left(  x\right)  dx\right]  .
\]
Thus, our hypothesis (\ref{rhs}) would imply the absurd equality between
$f\left(  Z_{\rho}\right)  $\ and $\int_{0}^{1}f\left(  x\right)  dx$.
\end{remark}

\begin{proof}
(of Proposition \ref{terminaval}) Under our assumptions, we have
\begin{align*}
\mathbb{E}\left[  M_{\rho}f\left(  Z_{\rho}\right)  \right]   & =\mathbb{E}
\left[  \int_{0}^{\infty}M_{u}f\left(  Z_{u}\right)  dA_{u}^{\rho}\right] \\
& =\mathbb{E}\left[  \int_{0}^{\infty}M_{u}f\left(  1-A_{u}^{\rho}\right)
dA_{u}^{\rho}\right] \\
& =\mathbb{E}\left[  M_{\infty}\int_{0}^{\infty}f\left(  1-A_{u}^{\rho
}\right)  dA_{u}^{\rho}\right] \\
& =\mathbb{E}\left[  M_{\infty}\int_{0}^{1}f\left(  1-x\right)  dx\right] \\
& =\mathbb{E}\left[  M_{\infty}\int_{0}^{1}f\left(  x\right)  dx\right]  .
\end{align*}
\end{proof}

Taking $M_{t}\equiv1$, we find that $\left(  Z_{\rho}\right)  $\ is uniformly
distributed on $\left(  0,1\right)  $, which is already known
(\cite{jeulinyor}, \cite{zurich}) since (recalling that $Z_{u}$\ is
decreasing)
\[
Z_{\rho}=\inf_{u\leq\rho}Z_{u}.
\]
In fact we have a stronger result: under all changes of probability on
$\mathcal{F}_{\rho}$, of the form
\[
d\mathbb{Q}=M_{\rho}d\mathbb{P}
\]
where $\left(  M_{t}\right)  $\ is a positive uniformly integrable $\left(
\mathcal{F}_{t}\right)  $-martingale such that $\mathbb{E}\left[
M_{0}\right]  =1$, the law of $Z_{\rho}$\ (is unchanged and) is uniform.

\begin{corollary}
Under the assumptions of Proposition \ref{terminaval}, we have
\[
\mathbb{E}\left[  M_{\rho}\mid Z_{\rho}\right]  =\mathbb{E}\left[  M_{\rho
}\right]  =\mathbb{E}\left[  M_{0}\right]
\]
On the other hand, the quantity $\mathbb{E}\left[  M_{\infty}\mid Z_{\rho
}\right]  $\ is not easy to evaluate, as is seen with D. Williams' example,
and is different from $\mathbb{E}\left[  M_{\rho}\mid Z_{\rho}\right]  $.
Indeed, in this framework and with the already used notations:
\[
\mathbb{E}\left[  M_{\infty}\mid Z_{\rho}\right]  =\exp\left(  \lambda\right)
\mathbb{E}\left[  \exp\left(  -\frac{\lambda^{2}}{2}T_{1}\right)  \mid
B_{\rho}\right]  .
\]
Decomposing again $T_{1}$ as $T_{1}=\rho+\left(  \sigma-\rho\right)  +\left(
T_{1}-\sigma\right)  $, and using D. Williams\textquotedblright\ path
decomposition, we obtain:
\begin{align*}
\mathbb{E}\left[  M_{\infty}\mid Z_{\rho}\right]   & =\exp\left(
\lambda\right)  \left(  \frac{\lambda}{\sinh\left(  \lambda\right)  }\right)
\exp\left(  -\lambda B_{\rho}\right)  \mathbb{E}\left[  \exp\left(
-\frac{\lambda^{2}}{2}\rho\right)  \mid B_{\rho}\right] \\
& =\left(  \frac{2\lambda}{1-\exp\left(  -2\lambda\right)  }\right)
\exp\left(  -2\lambda B_{\rho}\right)  .
\end{align*}
\end{corollary}

\begin{corollary}
The family $\left\{  M_{\rho};\text{ }M\text{ uniformly integrable }\left(
\mathcal{F}_{t}\right)  \text{-martingale}\right\}  $ is not dense in
$L^{1}\left(  \mathcal{F}_{\rho}\right)  $.
\end{corollary}

\begin{proof}
From Proposition 2, the variable $\left(  f\left(  Z_{\rho}\right)  -\int
_{0}^{1}f\left(  x\right)  dx\right)  $ is orthogonal to $M_{\rho}$.
\end{proof}

This negative result led us to look for some representation of the generic
element of $L^{1}\left(  \mathcal{F}_{\rho}\right)  $\ in terms of $\left(
\mathcal{F}_{t}\right)  $-martingales taken at time $\rho$\ on one hand, and
the variable $Z_{\rho}$, on the other hand.

\begin{proposition}
$\left(  i\right)  .$ Let $K:$ $\left[  0,1\right]  \times\mathbb{R}_{+}
\times\Omega\rightarrow\mathbb{R}_{+}$, be a $\mathcal{B}_{\left[  0,1\right]
}\otimes\mathcal{P}\left(  \mathcal{F}_{\bullet}\right)  $ measurable process,
where $\mathcal{P}\left(  \mathcal{F}_{\bullet}\right)  $ denotes the $\left(
\mathcal{F}_{t}\right)  $ predictable $\sigma$-field on $\mathbb{R}_{+}
\times\Omega$. \ Then:
\begin{equation}
\mathbb{E}\left[  K\left(  1-Z_{\rho},\rho\right)  \right]  =\mathbb{E}\left[
\int_{0}^{1}dyK\left(  y,\alpha_{y}\right)  \right] \label{masterformula}
\end{equation}
where
\[
\alpha_{y}=\inf\left\{  u:\text{ }A_{u}^{\rho}>y\right\}  .
\]
$\qquad\qquad\qquad\qquad\quad\left(  ii\right)  .$ Let $\left(  H_{u}
,u\geq0\right)  $ be a bounded predictable process. Define a measurable family
$\left(  M_{t}^{y}\right)  _{t\geq0}$ of martingales through their terminal
values:
\[
M_{\infty}^{y}=H_{\alpha_{y}}.
\]
Then
\[
H_{\rho}=M_{\rho}^{1-Z_{\rho}},\text{ }a.s.
\]
\end{proposition}

\begin{proof}
$\left(  i\right)  .$ This follows from the monotone class theorem, once we
have shown:
\begin{equation}
\mathbb{E}\left[  f\left(  1-Z_{\rho}\right)  H_{\rho}\right]  =\mathbb{E}
\left[  \int_{0}^{1}dyf\left(  y\right)  H_{\alpha_{y}}\right]
\label{formulerandom}
\end{equation}
for every bounded predictable process $H$ and every Borel bounded function $f
$. But, this identity follows from the fact that: $1-Z_{\rho}=A_{\rho}$; and
so:
\begin{align*}
\mathbb{E}\left[  f\left(  A_{\rho}\right)  H_{\rho}\right]   & =\mathbb{E}
\left[  \int_{0}^{\infty}dA_{u}f\left(  A_{u}\right)  H_{u}\right] \\
& =\mathbb{E}\left[  \int_{0}^{1}dyf\left(  y\right)  H_{\alpha_{y}}\right]  .
\end{align*}
We shall prove the second statement by showing that for every bounded $\left(
k_{u}\right)  $ predictable process
\[
\mathbb{E}\left[  k_{\rho}H_{\rho}\right]  =\mathbb{E}\left[  k_{\rho}M_{\rho
}^{1-Z_{\rho}}\right]  .
\]
From (\ref{masterformula}), we deduce:
\begin{align*}
\mathbb{E}\left[  k_{\rho}M_{\rho}^{1-Z_{\rho}}\right]   & =\mathbb{E}\left[
\int_{0}^{1}dyM_{\alpha_{y}}^{y}k_{\alpha_{y}}\right] \\
& \overset{\left(  a\right)  }{=}\int_{0}^{1}dy\mathbb{E}\left[  M_{\infty
}^{y}k_{\alpha_{y}}\right] \\
& \overset{\left(  b\right)  }{=}\int_{0}^{1}dy\mathbb{E}\left[  H_{\alpha
_{y}}k_{\alpha_{y}}\right] \\
& \overset{\left(  c\right)  }{=}\mathbb{E}\left[  k_{\rho}H_{\rho}\right]  .
\end{align*}
((a) follows from the optional stopping theorem for $\left(  M_{t}^{y}\right)
$; (b) follows from the definition of $M_{\infty}^{y}$; (c) is another
consequence of (\ref{masterformula})). Comparing the extreme terms in the
above, we get
\[
H_{\rho}=M_{\rho}^{1-Z_{\rho}}.
\]
\end{proof}

\section{Some systematic constructions and some examples of pseudo-stopping times}

\subsection{First constructions}

Here we discuss some combinations of several pseudo-stopping times which yield
a pseudo-stopping time. Here is a first easy result:

\begin{proposition}
\label{construc}Let $\rho$\ be a $\left(  \mathcal{F}_{t}\right)
$-pseudo-stopping time and let $\tau$ be a $\left(  \mathcal{F}_{t}^{\rho
}\right)  $-stopping time. Then $\rho\wedge\tau$ is a $\left(  \mathcal{F}
_{t}\right)  $ pseudo-stopping time.
\end{proposition}

\begin{proof}
Let $M$\ be any uniformly integrable $\left(  \mathcal{F}_{t}\right)
$-martingale. We know that $M_{t\wedge\rho}$ is a uniformly integrable
martingale in the enlarged filtration $\left(  \mathcal{F}_{t}^{\rho}\right)
$ and $\rho$\ is a stopping time in this filtration. If $\tau$\ is also a
$\left(  \mathcal{F}_{t}^{\rho}\right)  $-stopping time, then so is
$\rho\wedge\tau$. Hence $\mathbb{E}M_{\rho\wedge\tau}=\mathbb{E}M_{0}$.
\end{proof}

\begin{example}
Let $\rho$\ be as in D. Williams' example. Let $0<a<1$, and$\ T_{a}
=\inf\left\{  t>0:\quad B_{t}=a\right\}  $. Then
\[
\rho_{a}=\rho\wedge T_{a},\qquad0<a<1,
\]
is an increasing family of pseudo-stopping times.
\end{example}

\begin{remark}
From the previous proposition, it is easy to see that for any uniformly
integrable $\left(  \mathcal{F}_{t}\right)  $-martingale, we have
\[
\mathbb{E}\left[  M_{T\wedge\rho}\right]  =\mathbb{E}\left[  M_{0}\right]
\]
for any $\left(  \mathcal{F}_{t}\right)  $\ stopping time $T$.
\end{remark}

\begin{remark}
As a further comment about Proposition \ref{construc}, we remark that
pseudo-stopping times do not inherit all the "nice" properties of stopping
times. As an example, a pseudo-stopping time of a given filtration does not
remain in general a pseudo-stopping time in a larger filtration, whereas a
stopping time does. Indeed, let us keep the same notation as in section 2.3
and look at the pseudo-stopping time $\rho$\ in the larger filtration $\left(
\mathcal{F}_{t}^{\sigma}\right)  $. Using the computations we have already
done in section 2.3 and the projections formula (see \cite{delmaismey} p.186),
we get:
\[
\mathbb{P}\left[  \rho>t\mid\mathcal{F}_{t}^{\sigma}\right]  =\frac{1-\max
_{s\leq t\wedge T_{1}}B_{s}}{1-B_{t\wedge T_{1}}^{+}}\mathbf{1}_{\left\{
\sigma>t\right\}  },
\]
which is not decreasing. In fact, any end of predictable set that avoids
stopping times is not a pseudo-stopping time, as we shall see in the next subsection.
\end{remark}

\subsection{A generalization of D. Williams' example}

To keep the discussion as simple as possible, we assume that we are working
with an original filtration $\left(  \mathcal{F}_{t}\right)  $\ such that:

\begin{itemize}
\item all $\left(  \mathcal{F}_{t}\right)  $-martingales are continuous (e.g:
$\left(  \mathcal{F}_{t}\right)  $ is the Brownian filtration).

\item Moreover, we consider $L$, the end of a $\left(  \mathcal{F}_{t}\right)
$\ predictable set, such that for every $\left(  \mathcal{F}_{t}\right)
$\ stopping time $T$, $\mathbb{P}\left[  L=T\right]  =0$.
\end{itemize}

Under these two conditions, the supermartingale $Z_{t}=P\left[  L>t\mid
\mathcal{F}_{t}\right]  $ associated with $L$\ is a.s. continuous, and
satisfies $Z_{L}=1$. Then we let,
\[
\rho=\sup\left\{  t<L:\quad Z_{t}=\inf_{u\leq L}Z_{u}\right\}  .
\]
The following holds:

\begin{proposition}
$\left(  i\right)  $ $I_{L}=\inf_{u\leq L}Z_{u}$ is uniformly distributed on
$\left[  0,1\right]  $; (see \cite{zurich})\newline

$\left(  ii\right)  $ The supermartingale $Z_{t}^{\rho}=P\left[  \rho
>t\mid\mathcal{F}_{t}\right]  $ associated with $\rho$\ is given by
\[
Z_{t}^{\rho}=\inf_{u\leq t}Z_{u}.
\]
As a consequence, $\rho$ is a $\left(  \mathcal{F}_{t}\right)  $
pseudo-stopping time.
\end{proposition}

\begin{proof}
$\left(  i\right)  $ Let
\[
T_{b}=\inf\left\{  t,\quad Z_{t}\leq b\right\}  ,\qquad0<b<1,
\]
then
\[
\mathbb{P}\left[  I_{L}\leq b\right]  =\mathbb{P}\left[  T_{b}<L\right]
=\mathbb{E}\left[  Z_{T_{b}}\right]  =b.
\]
$\left(  ii\right)  $ Note that for every $\left(  \mathcal{F}_{t}\right)  $
stopping time $T$, we have
\[
\left\{  T<\rho\right\}  =\left\{  T^{^{\prime}}<L\right\}
\]
where
\[
T^{^{\prime}}=\inf\left\{  t>T,\quad Z_{t}\leq\inf_{s\leq T}Z_{s}\right\}  .
\]
Consequently, we have
\[
\mathbb{E}\left[  Z_{T}^{\rho}\right]  =\mathbb{P}\left[  T<\rho\right]
=\mathbb{P}\left[  T^{^{\prime}}<L\right]  =\mathbb{E}\left[  Z_{T^{^{\prime}
}}\right]  =\mathbb{E}\left[  \inf_{u\leq T}Z_{u}\right]  .
\]
We deduce the desired result from the equality between the two extreme terms
for every $\left(  \mathcal{F}_{t}\right)  $-stopping time $T$, and the
optional section theorem.
\end{proof}

\bigskip

In the literature about enlargements of filtrations (\cite{jeulin},
\cite{jeulinyor}, \cite{zurich}, etc.), a number of explicit computations of
supermartingales associated to various $L^{\prime}s$ have been given. We shall
use some of these computations to produce some examples of pseudo-stopping
times, with the help of the proposition.

\begin{enumerate}
\item First let us check again that we recover the example of D. Williams from
the Proposition 5. With the notations of the introduction $\left(
L=\sigma\right)  $, it is not hard to see that (see \cite{rogerswilliams})
\[
Z_{t}=1-B_{t\wedge T_{1}}^{+}.
\]
Hence
\[
\rho=\sup\left\{  s<\sigma:\text{ }B_{s}=S_{s}\right\}  .
\]

\item Consider $\left(  R_{t}\right)  _{t\geq0}$ a three dimensional Bessel
process, starting from zero, its filtration $\left(  \mathcal{F}_{t}\right)
$, and
\[
L=L_{1}=\sup\left\{  t:\quad R_{t}=1\right\}  .
\]
Then
\begin{equation}
\rho=\sup\left\{  t<L:\quad R_{t}=\sup_{u\leq L}R_{u}\right\}  ,\label{eight}
\end{equation}
is a $\left(  \mathcal{F}_{t}\right)  $ pseudo-stopping time. This follows
from the fact that
\[
Z_{t}^{L}=1\wedge\frac{1}{R_{t}},
\]
hence (\ref{eight}) is equivalent to:
\[
\rho=\sup\left\{  t<L:\qquad Z_{t}^{L}=\inf_{u\leq L}Z_{u}^{L}\right\}  ,
\]
and from the above proposition:
\[
Z_{t}^{\rho}=1\wedge\left(  \frac{1}{\underset{u\leq t}{\sup}R_{u}}\right)  .
\]
We can generalize further this example by noticing that for $n>2$, we have for
$\left(  R_{t}\right)  _{t\geq0}$ a BES$\left(  n\right)  $, $Z_{t}
^{L}=1\wedge\left(  \frac{1}{R_{t}}\right)  ^{n-2}$.

\item Consider $\left(  B_{u}\right)  _{u\geq0}$\ a one dimensional Brownian
motion, $\left(  \mathcal{F}_{t}\right)  $\ its filtration, and
\[
g_{t}=\sup\left\{  s<t:\quad B_{s}=0\right\}  ,
\]
then
\begin{equation}
\rho_{t}=\sup\left\{  s<g_{t}:\quad\frac{\left\vert B_{s}\right\vert }
{\sqrt{t-s}}=\sup_{u<g_{t}}\frac{\left\vert B_{u}\right\vert }{\sqrt{t-u}
}\right\} \label{nine}
\end{equation}
is a $\mathcal{F}_{t}$\ pseudo-stopping time. Again, this follows from the
fact that $\rho_{t}$\ is in fact defined from $g_{t}\left(  =L\right)  $ as in
the framework preceding the proposition, since:
\[
Z_{u}^{g_{t}}\equiv\Phi\left(  \frac{\left\vert B_{u}\right\vert }{\sqrt{t-u}
}\right)  ,
\]
with $\Phi\left(  x\right)  =\mathbb{P}\left(  \left\vert N\right\vert \geq
x\right)  $, where $N$\ is a standard Gaussian.

\item We can reinterpret the previous example via a deterministic time-change.
We remark that we can write:
\[
\frac{B_{u}}{\sqrt{1-u}}=Y_{\log\frac{1}{1-u}},
\]
where $\left(  Y_{s}\right)  _{s\geq0}$, is an Ornstein-Uhlenbeck process
satisfying
\[
Y_{s}=\beta_{s}+\frac{1}{2}\int_{0}^{s}duY_{u}.
\]
We then deduce from example 3 that
\[
\rho^{^{\prime}}=\sup\left\{  s<L_{0}^{^{\prime}}:\text{\qquad}\left\vert
Y_{s}\right\vert =\sup_{u\leq L_{0}^{^{\prime}}}\left\vert Y_{u}\right\vert
\right\}
\]
is a $\left(  \mathcal{F}_{t}^{^{\prime}}\right)  $ pseudo-stopping time,
where
\[
L_{0}^{^{\prime}}\equiv\log\left(  \frac{1}{1-g_{1}}\right)  =\sup\left\{
s>0,\qquad Y_{s}=0\right\}
\]
and $\left(  \mathcal{F}_{t}^{^{\prime}}\right)  $\ is the natural filtration
of $\left(  Y_{t}\right)  $.

\item Let us consider the case of a transient diffusion $X_{t}$. Let $s$\ be a
scale function such that $s\left(  -\infty\right)  =0$ and $s\left(  x\right)
>0$. Let
\[
L_{a}=\sup\left\{  t;\quad X_{t}=a\right\}  ,
\]
the last passage at the level $a$. We have (see \cite{pitmanyor}):
\[
Z_{t}^{L_{a}}=1\wedge\frac{s\left(  X_{t}\right)  }{s\left(  a\right)  }.
\]
Thus
\[
\rho_{a}=\sup\left\{  t<L_{a}:\quad s\left(  X_{t}\right)  =\inf_{u\leq L_{a}
}s\left(  X_{u}\right)  \right\}
\]
is a pseudo-stopping time in the filtration of $\left(  X_{t}\right)  $. For
example, let us consider the case of a brownian motion with a negative drift:
\[
X_{t}\equiv x+\mu t+\sigma B_{t},\quad\mu<0.
\]
In this case, the scale function is
\[
s\left(  x\right)  =\exp\left(  -\frac{2\mu x}{\sigma^{2}}\right)  .
\]
Hence
\[
\rho_{a}=\sup\left\{  t<L_{a}:\quad\mu t+\sigma B_{t}=\inf_{u\leq L_{a}
}\left(  \mu u+\sigma B_{u}\right)  \right\}
\]
is a pseudo-stopping time in the filtration of $\left(  B_{t}\right)  $.\bigskip
\end{enumerate}

As for D. Williams' example, none of these pseudo-stopping times remains a
pseudo-stopping time in the larger filtration $\left(  \mathcal{F}_{t}
^{L}\right)  $.This is a consequence of a result of Az\'{e}ma (\cite{azema}).

\begin{proposition}
Let $L$\ be the end of a predictable set such that $\mathbb{P}\left[
L=T\right]  =0$. Then $L$\ is not a pseudo-stopping time.
\end{proposition}

\begin{proof}
From a result of Az\'{e}ma (\cite{azema}), as $A_{t}^{L}=a_{t}^{L}$ is
continuous, the law of $A_{\infty}^{L}$\ is the exponential law of parameter
$1$, whilst for pseudo-stopping times, the law of $A_{\infty}^{L}$\ is
$\delta_{1}$, the Dirac mass at one. Hence $L$\ cannot be a pseudo-stopping time.
\end{proof}

\subsection{Another generalization}

We now give a generalization of the previous construction. We make the same
assumptions about the filtration $\left(  \mathcal{F}_{t}\right)  $\ and the
time $L$, with the extra assumption that $\mathbb{P}\left[  L=\infty\right]
=0$. Let $\left(  \Delta_{t}\right)  $\ be a nonincreasing, continuous and
adapted process such that
\begin{align}
\Delta_{0}  & =1\label{ncond}\\
\Delta_{\infty}  & =0.
\end{align}
Let us define $\rho$\ by
\[
\rho\equiv\sup\left\{  t<L;\quad Z_{t}=\Delta_{t}\right\}  .
\]
Again, for every $\left(  \mathcal{F}_{t}\right)  $ stopping time $T$, we have
\[
\left\{  T<\rho\right\}  =\left\{  T^{^{\prime}}<L\right\}
\]
where
\[
T^{^{\prime}}=\inf\left\{  t>T,\quad Z_{t}\leq\Delta_{T}\right\}
\]
Thus
\[
\mathbb{E}\left[  Z_{T}^{\rho}\right]  =\mathbb{P}\left[  T<\rho\right]
=\mathbb{P}\left[  T^{^{\prime}}<L\right]  =\mathbb{E}\left[  Z_{T^{^{\prime}
}}\right]  =\mathbb{E}\left[  \Delta_{T}\right]  ,
\]
and with the optional section theorem we can conclude that
\[
Z_{t}^{\rho}=\Delta_{t},\qquad t\geq0.
\]
It follows from Theorem \ref{mainthm} that $\rho$\ is a pseudo-stopping time.
Hence we have proved the following:

\begin{proposition}
Let $\left(  \Delta_{t}\right)  $\ be a nonincreasing, continuous and adapted
process such that:
\begin{align*}
\Delta_{0}  & =1\\
\Delta_{\infty}  & =0.
\end{align*}
Then, under the assumptions made above, there always exists a pseudo-stopping
time $\rho$\ such that $Z_{t}^{\rho}=\Delta_{t}$, for $t\geq0$.
\end{proposition}

So we can associate a pseudo-stopping time to any continuous, nonincreasing
adapted process $\left(  \Delta_{t}\right)  $\ which satisfies (\ref{ncond}).
But there is not uniqueness since we can use different $Z^{\prime}s$
associated to different $L^{\prime}s$ to construct $\rho$. In other words,
every continuous, nonincreasing adapted process $\left(  \Delta_{t}\right)  $
satisfying (\ref{ncond}) is the dual predictable projection of some
$1_{\left\{  \rho\leq t\right\}  }$, where $\rho$\ is a pseudo-stopping time.

As an example, we can take
\[
\Delta_{t}=\exp\left(  -S_{t}\right)
\]
with the already used\ notations. Then,
\[
\rho=\sup\left\{  t<\sigma;\quad1-B_{t}^{+}=\exp\left(  -S_{t}\right)
\right\}
\]
is a pseudo-stopping time in the filtration of the Brownian motion $\left(
B_{t}\right)  $. We could as well take
\[
\Delta_{t}=\exp\left(  -L_{t}\right)  ,
\]
where $L_{t}$\ is the Brownian local time at level zero. In that case,
\[
\rho=\sup\left\{  t<\sigma;\quad1-B_{t}^{+}=\exp\left(  -L_{t}\right)
\right\}
\]
is a pseudo-stopping time.

We can also notice that if we take some deterministic $\Delta$, this
construction allows us to construct a pseudo-stopping time with a given
distribution. For example,
\[
\rho=\sup\left\{  t<\sigma;\quad1-B_{t}^{+}=\exp\left(  -\lambda t\right)
\right\}  ,
\]
where $\lambda>0$. Then $\rho$\ follows an exponential law of parameter
$\lambda$.

In the following section, we will see that we can drop the continuity
assumption but we will have to enlarge the initial probability space.

\subsection{Further examples}

In this section, we shall link pseudo-stopping times with other random times
that appear in the literature. In particular, we will see that the random
times allowing the $\left(  \mathbf{H}\right)  $\ hypothesis (see
\cite{elliotjeanbyor}) to hold are special cases of pseudo-stopping times.

\subsubsection{The hypothesis $\left(  \mathbf{H}\right)  $}

First, we give the following obvious result:

\begin{proposition}
If $\rho$\ is a random time that is independent from $\mathcal{F}_{\infty}$,
then it is a pseudo-stopping time.
\end{proposition}

\begin{example}
If $\rho$\ is an exponential time of parameter $\lambda$\ that is independent
from $\mathcal{F}_{\infty}$, then it is a pseudo-stopping time.
\end{example}

\begin{example}
Another example is given by what D. Williams (\cite{williams}) calls a "silly"
time:
\[
\rho=\frac{1}{1+\left\vert B_{2}-B_{1}\right\vert },
\]
which is independent from $\mathcal{F}_{1}$.\bigskip
\end{example}

Now suppose that our probability space supports a uniform random variable
$\Theta$\ on $\left(  0,1\right)  $ that is independent of the sigma field
$\mathcal{F}_{\infty}$. Assume we are given an $\left(  \mathcal{F}
_{t}\right)  $-adapted increasing and continuous process satisfying $A_{0}=0$
and $A_{\infty}=1$\ . Let us consider the random time defined by:
\[
\rho=\inf\left\{  t;\quad A_{t}>\Theta\right\}  .
\]
It is not difficult to check that
\begin{equation}
\mathbb{P}\left[  \rho>t\mid\mathcal{F}_{t}\right]  =1-A_{t}
.\label{indeppseudo}
\end{equation}
We have thus constructed a pseudo-stopping time associated with a given
continuous process $\left(  A_{t}\right)  $. This construction is well known,
see \cite{jenbrutk1} for more details and references. But this construction is
not always possible (for example when $\mathcal{F}_{\infty}=\mathcal{F}$),
which explains why our construction in the previous section is more general.

But the pseudo-stopping times that are constructed in the way of
(\ref{indeppseudo}) enjoy the following noticeable property (\cite{jenbrutk1},
\cite{delmeyfil}):
\begin{equation}
\mathbb{P}\left[  \rho>t\mid\mathcal{F}_{t}\right]  =\mathbb{P}\left[
\rho>t\mid\mathcal{F}_{\infty}\right]  .\label{H}
\end{equation}
Random times with this property are often used in the literature on default
modelling (see \cite{jenbrutk1}, \cite{elliotjeanbyor}) and were studied in
\cite{delmeyfil}, \cite{bremaudyor}. There are several equivalent formulations
for (\ref{H}). Before we mention them, let us notice that any random time
satisfying (\ref{H}) is a pseudo-stopping time. In fact, we have a stronger
result: every $\left(  \mathcal{F}_{t}\right)  $ martingale is an $\left(
\mathcal{F}_{t}^{\rho}\right)  $ martingale (see \cite{delmeyfil}). Thus the
fourth statement in Theorem \ref{mainthm} is satisfied.\bigskip

Now let us consider the $\left(  \mathbf{H}\right)  $ hypothesis in our
framework of progressive enlargement with a random time $\rho$: every $\left(
\mathcal{F}_{t}\right)  $-square integrable martingale is an $\left(
\mathcal{F}_{t}^{\rho}\right)  $-square integrable martingale. This hypothesis
was studied by Dellacherie and Meyer \cite{delmeyfil}, Br\'{e}maud and Yor
\cite{bremaudyor}. It is equivalent to one of the following hypothesis (see
\cite{elliotjeanbyor} for more references):

\begin{enumerate}
\item $\forall t$, the $\sigma$-algebras $\mathcal{F}_{\infty}$\ and
$\mathcal{F}_{t}^{\rho}$\ are conditionally independent given $\mathcal{F}
_{t}$.

\item For all bounded $\mathcal{F}_{\infty}$-measurable random variables
$\mathbf{F}$\ and all bounded $\mathcal{F}_{t}^{\rho}$-measurable random
variables $\mathbf{G}_{t}$, we have
\[
\mathbb{E}\left[  \mathbf{FG}_{t}\mid\mathcal{F}_{t}\right]  =\mathbb{E}
\left[  \mathbf{F}\mid\mathcal{F}_{t}\right]  \mathbb{E}\left[  \mathbf{G}
_{t}\mid\mathcal{F}_{t}\right]  .
\]

\item For all bounded $\mathcal{F}_{t}^{\rho}$-measurable random variables
$\mathbf{G}_{t}$:
\[
\mathbb{E}\left[  \mathbf{G}_{t}\mid\mathcal{F}_{\infty}\right]
=\mathbb{E}\left[  \mathbf{G}_{t}\mid\mathcal{F}_{t}\right]  .
\]

\item For all bounded $\mathcal{F}_{\infty}$-measurable random variables
$\mathbf{F}$,
\[
\mathbb{E}\left[  \mathbf{F}\mid\mathcal{F}_{t}^{\rho}\right]  =\mathbb{E}
\left[  \mathbf{F}\mid\mathcal{F}_{t}\right]  .
\]

\item For all $s\leq t$,
\[
\mathbb{P}\left[  \rho\leq s\mid\mathcal{F}_{t}\right]  =\mathbb{P}\left[
\rho\leq s\mid\mathcal{F}_{\infty}\right]  .
\]
\end{enumerate}

Thus, pseudo-stopping times may be considered as a generalized or a weakened
form of the $\left(  \mathbf{H}\right)  $ hypothesis since then local
martingales in the initial filtration remain local martingales in the enlarged
one up to time $\rho$. Moreover, for most of the examples we have considered,
such as D. Williams', (\ref{H}) is not satisfied.

\subsubsection{Randomized stopping times and F\"{o}llmer measures}

Now we give a relation between pseudo-stopping times and randomized stopping
times as presented in \cite{meyflou}. First we give some definitions. We
always consider a given probability space $\left(  \Omega,\mathcal{F},\left(
\mathcal{F}_{t}\right)  _{t\geq0},\mathbb{P}\right)  $.

\begin{definition}
A randomized random variable on $\left(  \Omega,\mathcal{F},\mathbb{P}\right)
$ is a probability measure $\mu$\ on $\left(  \left[  0,\infty\right]
\times\Omega,\mathcal{B}\left(  \left[  0,\infty\right]  \right)
\otimes\mathcal{F}\right)  $ such that its projection on $\Omega$\ is equal to
$\mathbb{P}$.
\end{definition}

For example, let $\rho$\ be a random time; then $\mu_{\rho}$ defined by
\[
\mu_{\rho}\left(  X\right)  =\mathbb{E}\left[  X_{\rho}\right]  ,
\]
for all bounded measurable processes $\left(  X_{t}\right)  $ is a randomized
random variable. \bigskip

We know from a result of F\"{o}llmer (see \cite{dellachmeyer}) that there
exists an increasing c\`{a}dl\`{a}g process $\left(  A_{t}\right)  $ such that
$A_{0}=0$ and
\[
\mu\left(  X\right)  =\mathbb{E}\left[  \int_{0}^{\infty}X_{s}dA_{s}\right]  ,
\]
for all nonnegative process $\left(  X_{t}\right)  $. The fact that the
projection on $\Omega$\ is equal to $\mathbb{P}$ means that $A_{\infty}=1,$
$a.s$.

\begin{definition}
If the process $\left(  A_{t}\right)  $ associated with $\mu$\ on $\left(
\left[  0,\infty\right]  \times\Omega,\mathcal{B}\left(  \left[
0,\infty\right]  \right)  \otimes\mathcal{F}\right)  $ is adapted, then we say
that $\mu$\ is a randomized stopping time.
\end{definition}

By considering the new space $\overline{\Omega}=\left[  0,1\right]
\times\Omega$ endowed with the $\sigma$-fields $\overline{\mathcal{F}}
$=$\mathcal{B}\left(  \left[  0,1\right]  \right)  \otimes\mathcal{F}$,
$\overline{\mathcal{F}}_{t}$=$\mathcal{B}\left(  \left[  0,1\right]  \right)
\otimes\mathcal{F}_{t}$ (augmented in the usual way) and the probability
measure $\overline{\mathbb{P}}=\lambda\otimes\mathbb{P}$, it is possible to
show that for every randomized stopping time $\mu$, there exists a stopping
time $\rho$\ in this new filtered space such that
\[
\mu\left(  X\right)  =\overline{\mathbb{E}}\left[  X_{\rho}\right]  ,
\]
for all bounded measurable process $\left(  X_{t}\right)  $ on $\left(
\left[  0,\infty\right]  \times\Omega,\mathcal{B}\left(  \left[
0,\infty\right]  \right)  \otimes\mathcal{F}\right)  $. We take the convention
that a random variable $H$\ on $\Omega$ can be considered as the random
variable on $\overline{\Omega}$: $\left(  u,\omega\right)  \rightarrow
H\left(  \omega\right)  $. Conversely to every stopping time of $\overline
{\mathcal{F}}_{t}$ corresponds a randomized stopping time. \bigskip

This construction is always carried on the enlarged space $\overline{\Omega}
$. The third statement in Theorem \ref{mainthm} allows us to use
pseudo-stopping times to construct randomized stopping times without enlarging
the initial space.

\begin{proposition}
Let $\rho$\ be a pseudo-stopping time and $A_{t}^{\rho}$\ the $\left(
\mathcal{F}_{t}\right)  $\ dual optional projection of the process
$1_{\left\{  \rho\leq t\right\}  }$. Then the F\"{o}ellmer measure $\mu
$\ associated with $A_{t}^{\rho}$ is a randomized stopping time. Moreover, for
every bounded or nonnegative $\left(  \mathcal{F}_{t}\right)  $\ optional
process $\left(  X_{t}\right)  $:
\[
\mu\left(  X\right)  =\mathbb{E}\left[  X_{\rho}\right]  .
\]
\end{proposition}

\subsubsection{Randomized stopping times and families of stopping times}

\begin{proposition}
Let $\left(  T_{u}\right)  _{u\geq0}$ be a family of $\left(  \mathcal{F}
_{t}\right)  $\ stopping times and $S$ a positive random variable, independent
of the family $\left(  \mathcal{F}_{\infty}\right)  $. Then
\[
\rho=T_{S}
\]
is a $\left(  \mathcal{F}_{t}\right)  $\ pseudo-stopping time.
\end{proposition}

\begin{proof}
Let $\left(  M_{t}\right)  $ be a bounded $\left(  \mathcal{F}_{t}\right)
$\ martingale;
\begin{align*}
\mathbb{E}\left[  M_{T_{S}}\right]   & =\mathbb{E}\left[  \mathbb{E}\left[
M_{T_{s}}\mid S=s\right]  \right] \\
& =\mathbb{E}\left[  \mathbb{E}\left[  M_{0}\right]  \mid S=s\right] \\
& =\mathbb{E}\left[  M_{0}\right]  .
\end{align*}
\end{proof}

The previous proposition shows that any independently time changed family of
stopping times is a pseudo-stopping time. In fact, this proposition admits a
converse: every pseudo-stopping time is, in law, a time changed family of
stopping times. More precisely:

\begin{proposition}
Let $\rho$\ be a $\left(  \mathcal{F}_{t}\right)  $\ pseudo-stopping time,
which avoids all $\left(  \mathcal{F}_{t}\right)  $-stopping times, and
$Z_{t}=\mathbb{P}\left[  \rho>t\mid\mathcal{F}_{t}\right]  $ its associated
supermartingale. Set
\[
\alpha_{u}\equiv\inf\left\{  t\geq0,\quad\left(  1-Z_{t}\right)  >u,\quad0\leq
u\leq1\right\}  ,
\]
the right-continuous generalized inverse of the increasing continuous process
$\left(  1-Z_{t}\right)  $. Then $\left(  \alpha_{u}\right)  _{0\leq u\leq1}
$\ is a family of $\left(  \mathcal{F}_{t}\right)  $\ stopping times and
\[
\rho\overset{law}{=}\alpha_{U},
\]
where $U$\ is a random variable with uniform law, independent of $\left(
\mathcal{F}_{\infty}\right)  $.
\end{proposition}

\begin{proof}
The fact $\alpha_{u}$ is a stopping time, for all $u$, follows from
\[
\left\{  \alpha_{u}\leq t\right\}  =\left\{  u\leq\left(  1-Z_{t}\right)
\right\}  ,\quad\forall t\geq0.
\]
From (\ref{formulerandom}), we also have
\[
\mathbb{E}\left[  g\left(  \rho\right)  \right]  =\mathbb{E}\left[  \int
_{0}^{1}g\left(  \alpha_{u}\right)  du\right]  ,
\]
for all bounded Borel function $g$. This establishes $\left(  \rho
\overset{law}{=}\alpha_{U}\right)  $.
\end{proof}

\section{A discrete analogue: the coin-tossing case}

Let $\left(  X_{n}\right)  _{n\geq1}$ be the standard random walk with
Bernoulli increments. In his paper \cite{Le Gall}, Le Gall proved an analogue
of Williams' path decomposition for $\left(  X_{n}\right)  $. To fix ideas, we
shall consider the canonical space $\Omega=\mathbb{Z}^{N}$ endowed with the
product $\sigma$-field. $\left(  X_{n}\right)  $ will be the coordinate
process and $\left(  \mathbb{P}_{x}\right)  _{x\in\mathbb{Z}}$\ the family of
probability laws which make $\left(  X_{n}\right)  $\ the standard random walk
with Bernoulli increments. We also denote by $\left(  \mathbb{Q}_{x}\right)
_{x\in N}$\ the unique family of probability measures such that $\left(
X_{n},\mathbb{Q}_{x}\right)  $\ is a Markov chain with transition
probabilities:
\begin{align*}
\mathbb{Q}_{0}\left[  X_{1}=1\right]   & =1\\
if\text{ }x  & \geq1,\quad\mathbb{Q}_{x}\left[  X_{1}=x+1\right]  =\frac{1}
{2}\left(  1+\frac{1}{x}\right)  ;\quad\mathbb{Q}_{x}\left[  X_{1}=x-1\right]
=\frac{1}{2}\left(  1-\frac{1}{x}\right)  .
\end{align*}
Now let $p\geq1$ and define:
\begin{align*}
\sigma_{p}  & =\inf\left\{  k;\quad X_{k}=p\right\}  ,\\
\eta & =\sup\left\{  k\leq\sigma_{p}:\quad X_{k}=0\right\}  ,\\
m  & =\sup\left\{  X_{k},\quad k\leq\eta\right\}  ,\\
\gamma & =\inf\left\{  k\geq0;\quad X_{k}=m\right\}  .
\end{align*}
Then, Le Gall's statement is that under $\mathbb{P}_{0}$:

\begin{enumerate}
\item The processes $\left(  X_{k}\right)  _{0\leq k\leq\eta}$ and $\left(
X_{\eta+k}\right)  _{0\leq k\leq\sigma_{p}-\eta}$ are independent, with the
second being distributed as $\left(  X_{k}\right)  _{0\leq k\leq\sigma_{p}}$
under $\mathbb{Q}_{0}$;

\item $m$ is uniformly distributed on $\left\{  0,1,\ldots,p-1\right\}  $;

\item Conditionally on $\left\{  m=j\right\}  $, the processes $\left(
X_{k}\right)  _{0\leq k\leq\gamma}$ and $\left(  X_{\eta-k}\right)  _{0\leq
k\leq\eta-\gamma}$ are independent, the first being distributed as $\left(
X_{k}\right)  _{0\leq k\leq\sigma_{j}}$ under $\mathbb{P}_{0}$, and the second
as $\left(  X_{k}\right)  _{0\leq k\leq\sigma_{j+1}-1}$ under $\mathbb{Q}_{0}$.
\end{enumerate}

\begin{proposition}
If $\left(  M_{n}\right)  _{n\in\mathbb{N}}$ is a bounded martingale, then
\[
\mathbb{E}_{0}\left[  M_{\gamma}\right]  =\mathbb{E}_{0}\left[  M_{0}\right]
.
\]
Thus $\gamma$\ is a pseudo-stopping time.
\end{proposition}

\begin{proof}
The discrete time setup allows us to give an elementary argument, based in
part on the fact that $M_{n}$, as every $\mathcal{F}_{n}$ measurable variable,
may be written as:
\[
M_{n}=f_{n}\left(  X_{1},X_{2},\ldots,X_{n}\right)  ,
\]
where $f_{n}$ is a bounded function depending on $n$\ variables.

Now, for any bounded function $g$:
\[
\mathbb{E}_{0}\left[  M_{\gamma}g\left(  m\right)  \right]  =\mathbb{E}
_{0}\left[  \mathbb{E}_{0}\left[  M_{\gamma}\mid m\right]  g\left(  m\right)
\right]  .
\]
But, from $\left(  3\right)  $\ in Le Gall's satatement:
\begin{align*}
\mathbb{E}_{0}\left[  M_{\gamma}\mid m=j\right]   & =\mathbb{E}_{0}\left[
f_{\sigma_{j}}\left(  X_{1},X_{2},\ldots,X_{\sigma_{j}}\right)  \right] \\
& =\mathbb{E}_{0}\left[  M_{\sigma_{j}}\right]  =\mathbb{E}_{0}\left[
M_{0}\right]  .
\end{align*}
Thus, we have obtained:
\begin{align*}
\mathbb{E}_{0}\left[  M_{\gamma}g\left(  m\right)  \right]   & =\mathbb{E}
_{0}\left[  M_{\gamma}\right]  \mathbb{E}_{0}\left[  g\left(  m\right)
\right] \\
& =\mathbb{E}_{0}\left[  M_{\infty}\right]  \mathbb{E}_{0}\left[  g\left(
m\right)  \right]  ,
\end{align*}
which is the discrete analogue of Proposition 2, and shows a fortiori that
$\gamma$\ is a pseudo-stopping time.
\end{proof}

\newpage

config: arxiv


TITLE: Number of solutions to $x^k ≡ n (mod\ p)$
QUESTION [0 upvotes]: I am asked to show:
If $(n,p)=1$ show that the equation $x^k\equiv{n}\mod p$ has either no solutions or exactly k solutions.
How do I approach this problem?
I've begun by defining the obvious congruence, i.e.: this means $p | x^k-n$ but wasn't sure how to proceed

REPLY [1 votes]: Part a) is not true. You have infinitely many solutions, unless you restrict to $x<p$. And in this last case, for instance, $x^3\equiv 1\pmod 3$ has one solution, since $1^3=1$ but $2^3\equiv 2\pmod 3$. For a more dramatic example, $x^5\equiv 1\pmod 7$ has only $1$ as solution.
And the case $n=1$ shows that b) is not true either.


TITLE: Cantor&Zasenhaus - Polynomial factoring
QUESTION [1 upvotes]: I'm having problems factoring the following polynomial in $\mathbb{F}_5\left [ x \right ]$, someone could guide me please :'(
$x^5+2x^4+3x^3+x^2+2x+4 \in \mathbb{F}_5\left [ x  \right ]$.
Here is my attempt at what I have been able to understand: The idea is to use the algorithm of Cantor & Zasenhauss.
Let $f(x) := x^5+2x^4+3x^3+x^2+2x+4 \in \mathbb{F}_5\left [ x  \right ] \Rightarrow f'(x) = 3x^3+4x^2+2x+2 \in \mathbb{F}_5\left [ x  \right ]$. Then, we check that $f(x)$ is free of squares, ie that $gcd(f(x),f'(x))=1$, which is not verified, since $gcd(f(x),f'(x))=x+2$, therefore, we do $g(x) := \dfrac{f(x)}{gcd(f(x),f'(x))}=x^4+3x^2+2 \Rightarrow g'(x)=4x^3+x$ and so we get that $gcd(g(x),g'(x))=1$, ie $g(x)$ is free of squares.
From here I begin to complicate: (For the next steps I am guiding myself from here http://planetmath.org/cantorzassenhaussplit]http://planetmath.org/cantorzassenhaussplit
I will use the same notations on the attached page:
$B_1 = A, \ B_{k+1} := \displaystyle\frac{A}{gcd(B_k, x^{5^k}-x)} $
So, we have:
$B_1 := x^4+3x^2+2 $
$B_2 := \displaystyle\frac{x^4+3x^2+2}{gcd(B_k, x^5-x)}=x^3+2x^2+2x+4$
$B_3 := \displaystyle\frac{x^4+3x^2+2}{gcd(B_k, x^{25}-x)}=x^2+1$
And then how do I proceed? Can someone help me please?
First of all, Thanks.
Best regards.

REPLY [1 votes]: I would start by looking for factors of degree $1$: it is not hard to find $x+3$ and $x+2$ (the latter with multiplicity $2$).  After dividing out those, you're left with $x^2+2$ which is easily seen to be irreducible.


TITLE: How does ${n \choose k}$ relate to $2^n$ in asymptotic notation?
QUESTION [0 upvotes]: What would be an asymptotic (big-O) notation for ${n \choose k}$ which puts it into perspective with $2^n$?
EDIT: for $k$ constant, this post states ${n \choose k} = \Theta(n^k)$. I'm searching for a more general asymptotic notation, not limited to $k$ constant.
EDIT 2: and for $k = \frac{n}{2}$, this post obtains ${n \choose k} = \Theta(\frac{2^n}{\sqrt{n}})$.

REPLY [1 votes]: Two bounds from information theory might be helpful. If you let the function $H(p) = -p\log_2 p-(1-p)\log_2(1-p)$ denote the binary entropy function for $0\leq p\leq 1$, then you have
$$\frac{1}{n+1}2^{n H(k/n)}\leq \binom{n}{k}\leq 2^{n H(k/n)}.$$
It can be further tightened, but the connection with $2^n$ is already there.


TITLE: Curvature waves, harmonic curvature, and curvature flow
QUESTION [1 upvotes]: Let me first say I'm better at physics than math and have big gaps in my understanding of Riemannian geometry.  I do a lot better with intuitive explanations than identities and so forth.
I've been contemplating the idea of a Lorentzian manifold whose curvature is inherently wave-like; it could be described by the d'Alambert equation of the Riemann or Ricci tensor:
$$\Box R_{\mu\nu\sigma\rho} = 0$$
because the d'Alambertian is the wave operator, as we can see when we write it in an inertial frame:
$$\left(-\frac{1}{c^2}\frac{\partial^2}{\partial t^2} + \frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial z^2} + \frac{\partial^2}{\partial z^2}\right)R_{\mu\nu\sigma\rho} = 0.$$
Since the d'Alambertian is the generalization of the Laplacian, I would think that would also describe "harmonic curvature".  But apparently harmonic curvature is given by the divergence, not the Laplacian:
$$\nabla^iR_{ijkl} = 0$$
Why is this so?
And the other thing is, when people describe flow of curvature, instead of the wave equation they  use Ricci flow, which says the curvature determines how the metric changes:
$$\frac{\partial g_t}{\partial t} = -2\operatorname{Ric}_{g_t}$$
Now this apparently has soliton solutions, so I guess it's somehow a wave equation, but as I understand it was introduced more in the spirit of a diffusion equation, and I don't see why it should be preferable to the wave equation for the curvature tensor.  Nor can I follow DeTurck's paper that supposedly generalizes Ricci flow to more than 3 dimensions, and even then is it really covariant?
Sorry if that's two questions in one post but it really boils down to: why is the Laplace equation of the curvature tensor apparently not studied, and these other equations are studied instead?  Any insight would be appreciated!

REPLY [1 votes]: The Ricci Flow (RF) equation
$$
\frac{\partial g(t)}{\partial t}= -2 Ric(g(t))
$$
is a 2nd order PDE on the metric tensor $g(t)$. In contrast, your proposed d'Alambert equation  equation is a 4-th order PDE (since the Riemann tensor itself is a 2nd order nonlinear differential operator). As a rule of thumb, differential equations of higher order are harder to analyze, which might be one answer to your question: Your proposed equation is simply harder than RF which itself is hard enough. (I have no idea if anybody looked at your equation since the differential geometry literature is so vast.)

More importantly, RF was introduced by Richard Hamilton in early 1980s as a potential tool for proving Thurston's Geometrization Conjecture (TGC). It is clear from the equations defining the RF that Ricci-flat metrics are stationary points of the flow. Moreover, whenever $g$ is an Einstein metric it is a critical point of the normalized Ricci flow (NRF), which is a modification of the RF. Since in dimension 3 a Riemannian metric is Einstein if and only if it has constant sectional curvature, Hamilton thought that RF might be useful in proving TGC (by establishing its convergence to a stationary point of the flow). This was quite a leap of faith, but, eventually, Perelman proved that Hamilton was right. Later on, RF was used to prove other conjectures of topological and geometrical flavor.

This explains popularity of the RF: (1) it has relatively low  order (namely 2) and it is useful in proving something interesting.
I have no idea if the equation you propose can be used for proving some interesting geometric/topological results, but it is definitely more complex than the RF. I suggest you ask on MO if anybody (e.g. Robert Bryant, the one who introduced the Bryant Soliton in the context of the RF) saw any work in the literature on your equation.

About solitons. The notion of solitons in the context of RF (which, I think, is due to Hamilton himself), or of a more general geometric flow, an equation of the form, say,
$$
\frac{\partial g(t)}{\partial t}= D(g(t)),
$$
where $D$ is a differential operator, has only loose relation to classical solitons. One can define a geometric soliton as a family of Riemannian metrics $g(t)$ on a manifold $M$ such that there exists a family of diffeomorphisms $f_t: M\to M$ satisfying
$$
f_t^*(g(t))=g(0),
$$
i.e. we have a family of isometric metrics. More generally, one can allow metrics $g(t)$ such that
$$
f_t^*(g(t))= a(t) g(0),
$$
i.e. we have a family of metrics which are isometric up to a scalar. Depending on $a<1$ or $a>1$, one talks about shrinking or expanding solitons. Informally, "the shape of a metric does not change as the metric evolves." In this sense it is similar to a soliton/solitary wave: A solitary wave moves in space (this corresponds to having diffeomorphisms $f_t$ above) but preserves its shape.
This terminological flexibility is useful since people consider both RF and its normalized version (NRF): A family of metrics which evolves by isometry under the NRF will evolve by isometry up to scaling under the RF.


TITLE: Evaluate the limit $\lim_{x \to 0} \left(\frac{1}{x^{2}}-\frac{1}{\tan^{2}x}\right)$
QUESTION [4 upvotes]: Evaluate the limit $$\lim_{x \to 0}\left( \frac{1}{x^{2}}-\frac{1}{\tan^{2}x}\right)$$

My attempt
So we have $$\frac{1}{x^{2}}-\frac{\cos^{2}x}{\sin^{2}x}$$
$$=\frac{\sin^2 x-x^2\cos^2 x}{x^2\sin^2 x}$$
$$=\frac{x^2}{\sin^2 x}\cdot\frac{\sin x+x\cos x}{x}\cdot\frac{\sin x-x\cos x}{x^3}$$
Then I have $3$ limits to evaluate
$$\lim_{x \to 0}\frac{x^2}{\sin^2 x}=\left(\lim_{x \to o}\frac{x}{\sin x}\right)^2=1^2=1$$
$$\lim_{x \to 0}\frac{\sin x+x\cos x}{x}=\lim_{x \to 0}\left(\frac{\sin x}{x} + \cos x\right)=1+1=2$$
Now I'm having trouble with the last one which is
$$\lim_{x \to 0}\frac{\sin x-x\cos x}{x^3}=?$$
Thanks for any help.

REPLY [1 votes]: I think this limit would be considerably easier using Taylor Series instead of LHR.
$ \frac{\sin^2(x)-x^2\cos^2(x)}{x^2\sin^2(x)} \approx \frac{(x-\frac{x^3}{6})^2-x^2(1-\frac{x^2}{2})^2}{x^2(x)^2}=\frac{\frac{2x^4}{3}+O(x^5)}{x^4} \rightarrow \frac{2}{3} $


TITLE: Module $M$ over valuation Ring $A$ is flat $\iff$ it is torsion free
QUESTION [2 upvotes]: Given a valuation ring $A$ and an $A$-module $M$, I want to prove that $M$ is flat $\iff$ M is torsion free.
I already proved the implication '$\implies$' and I also know that $A$ is a local ring with maximal ideal $\mathfrak{m} = \{0\} \cup \{a \in A\setminus{\{0\}}\; :\; a^{-1} \notin A\}$. I was given a hint that it suffices to show that every finitely generated, torsion free $A$-module is free (and thus flat); that is, every minimal generating set is linearly independent. However, I don't quite understand why it suffices to consider finitely generated modules. Could someone explain this please?
Proving the claim for a finitely generated module $M$, let $<x_1,\dots , x_r>_A$ be a minimal generating set of $M$ and $\sum_{i=1}^r a_ix_i = 0$. Since $A$ is local, by Nakayama's Lemma we have that $<\bar{x_1},\dots ,\bar{x_r}>_{A/\mathfrak{m}}$ is a generating set of the $A/\mathfrak{m}$-vector space $M/\mathfrak{m}M$. Since $r$ is minimal, the set is also linearly independent and thus $\sum_{i=1} \bar{a_i}\bar{x_i} = 0 \implies \bar{a_i} = \bar{0}$ for all $i = 1, \dots , r$. That means $a_i \in \mathfrak{m}$. Now it remains to show that $a_i$ is invertible, but how exactly can we do this?

REPLY [1 votes]: However, I don't quite understand why it suffices to consider finitely generated modules.

That's simple: every module is the direct limit of its finitely generated submodules, and a direct limit of flat modules is flat.

REPLY [1 votes]: Any module is the filtered colimit of its finitely generated submodules. Also, submodules of torsionfree modules are torsionfree, and filtered colimits of flat modules are flat. This is why it suffices to prove that finitely generated torsionfree modules are flat, or even free.
So let $M$ be a finitely generated $A$-module, where $ A$ is a valuation ring. Choose $m_1,\dotsc,m_n \in M$ such that $[m_1],\dotsc,[m_n]$ is a $A/\mathfrak{m}$-basis of $M/\mathfrak{m}M$. By Nakayama's Lemma, $m_1,\dotsc,m_n$ is a generating set of $M$. We show that it is linearly independent. Assume $\sum_{i=1}^{n} a_i m_i = 0$ for some $a_1,\dotsc,a_n \in A$. Since $A$ is a valuation ring, some coefficient $ a_j$ divides all others. If $a_j=0$, we are done. Otherwise, the relation becomes $a_j \sum_{i=1}^{n} a_i/a_j \cdot m_i=0$, and since $M$ is torsionfree this implies $ \sum_{i=1}^{n} a_i/a_j \cdot m_i=0$. But since  the $[m_1],\dotsc,[m_n]$ are linearly independent over $A/\mathfrak{m}$, we have $a_i/a_j \in \mathfrak{m}$ for all $i$, which fails for $i=j$.
A different proof, using the equational criterion of flatness, can be found in Stacks, Tag 0539.


TITLE: Coprime polynomials.
QUESTION [0 upvotes]: Let f(x) be a nonzero polynomial. Show that there exists a polynomial g(x) with f(x) g(x) ≡ 1 (mod p(x)) if and only if gcd (f(x), p(x)) = 1.

What is this math question asking us to prove?
Is the problem asking to show that there exists a polynomial g(x) or does it want us the prove f(x) g(x) ≡ 1 (mod p(x)) if and only if gcd (f(x), p(x)) = 1. If it is asking us to prove "f(x) g(x) ≡ 1 (mod p(x)) if and only if gcd (f(x), p(x)) = 1" I can do the forward direction. I am not sure how to prove "if f(x) g(x) ≡ 1 (mod p(x)), then (f(x), p(x)) = 1".

REPLY [0 votes]: You're given two polynomials: $f(x)$ and $p(x)$. This question asks you to prove the equivalence of the following two statements:

$f(x) g(x) \equiv 1$ mod $p$ for some polynomial $g(x)$, and
$\gcd(f(x), p(x)) = 1$

Note that you're not given a polynomial $g$ to begin with. You have to show that such a $g$ exists given the second statement is true.


TITLE: polynomial conjugate
QUESTION [0 upvotes]: It is well known that any quadratic polynomial is conjugated to a polynomial of the form $z^2+c$. How about polynomials with higher degree, such as $z^n+a_1z^{n-1}+\cdots+a_{n-1}$, is it also conjugated to a polynomial of the form $z^n+c$.

REPLY [1 votes]: No. I assume you mean affinely conjugated, ie conjugated by means of affine map $h(z)=az+b$. Then you can see that you only have 2 parameters ($a$ and $b$) to simplify the form of the polynomial; there is no reason to expect that just 2 parameters will enable you to kill all but 1 coefficient.
What is true is that any polynomial $a_n z^n+ a_{n-1} z^{n-1}+\ldots$ is affinely conjugated to a monic centered polynomial, ie of the form
$z^{n} + a_{n-2} z^{n-2} + \ldots$.