TITLE: How to calculate the limit of zeta function
QUESTION [5 upvotes]: Suppose $f(x)>0$,$f''(x)\leqslant0$,and $\lim\limits_{x\to+\infty}f(x)=+\infty$ on$[0,+\infty)$.prove that
$$\lim\limits_{s\to0^+}\sum\limits_{n=0}^{\infty}\dfrac{(-1)^n}{f^s(n)}=\frac{1}{2}.$$
I tried to do it ,first of all we have
$$\sum\limits_{n=0}^{\infty} \frac{(-1)^n}{f^s(n)}=\sum\limits_{n=0}^{\infty} \left( \frac{1}{f^s(2n)}-\frac{1}{f^s(2n+1)} \right).$$
Use MVT we have
$$ \frac{1}{f^s(2n)}-\frac{1}{f^s(2n+1)}=-\frac{sf'(\xi_n)}{f^{s+1}(\xi_n)}(\xi_n\in(2n,2n+1)).$$
But next, I don't know how to deal with it. I want to ask that this problem can be solved by the property that the function is concave.

REPLY [4 votes]: We can generalize @zhw's solution from Prove that $\lim\limits_{x\to 0^+}\sum\limits_{n=1}^\infty\frac{(-1)^n}{n^x}=-\frac12$.
Starting with your application of the mean-value theorem (note that you have a sign error),
$$
\frac{1}{f^s(2n)}-\frac{1}{f^s(2n+1)}=\frac{sf'(\xi_n)}{f^{s+1}(\xi_n)}
\le \frac{sf'(2n)}{f^{s+1}(2n)}
$$
since $f$ is increasing and $f'$ is decreasing. It follows that
$$
\sum_{n=0}^{\infty} \frac{(-1)^n}{f^s(n)} \le \sum_{n=0}^{\infty} \frac{sf'(2n)}{f^{s+1}(2n)}  \le \frac{sf'(0)}{f^{s+1}(0)} + s\int_0^\infty \frac{f'(2t)}{f^{s+1}(2t)} \, dt = \frac{sf'(0)}{f^{s+1}(0)} + \frac{1}{2f^s(0)} \, .
$$
Similarly,
$$
\sum_{n=0}^{\infty} \frac{(-1)^n}{f^s(n)} \ge \sum_{n=0}^{\infty} \frac{sf'(2n+1)}{f^{s+1}(2n+1)} \ge  s\int_1^\infty \frac{f'(2t)}{f^{s+1}(2t)} \, dt = \frac{1}{2f^s(1)} \, .
$$
The result now follows by squeezing these estimates for $s \to 0$.


TITLE: Uniform closure vs. dense
QUESTION [0 upvotes]: Let $S_1= \{z\in \mathbb{C} \}$ be the unit circle in the complex plane. Let $A$ be the set of all polynomial functions on $\mathbb{C}$ restricted to $S^1$. That is $A= \{ f: S^1 \rightarrow \mathbb{C}; f(e^{i\theta})= \sum_{k=0}^n c_ke^{ik\theta}, c_k\in \mathbb{C}\}$. Either prove that the uniform closure of $A$ is all of $C(S^1)$, or give an example with justification to show that it is not.
By the complex version of Stone-Weierestrass, we know $A$ is dense in $C(S^1)$. Does this prove that the uniform closure of $A$ is all of $C(S^1)$? In general, do "being dense in" and the "being uniform closure of" mean the same thing?
Thanks!

REPLY [1 votes]: So, do you think the "conjugation"  function $g(e^{i\theta}) = e^{-i\theta}$, which is continuous on $S_1$, is a uniform limit of polynomials as in $A$?
For $f \in A$,
$$
\int_0^{2\pi} e^{i\theta} f(e^{i\theta})\,d\theta =
\int_0^{2\pi}\sum_{k=0}^n c_ke^{i(k+1)\theta}d\theta = 0
\tag1$$
but
$$
\int_0^{2\pi} e^{i\theta} g(e^{i\theta})\,d\theta =
\int_0^{2\pi}1\; d\theta = 2\pi.
\tag2$$
Thus a uniform limit of functions $f$ as in $(1)$ cannot be the function $g$ as in $(2)$.


TITLE: Equivalent conditions for covering space actions
QUESTION [2 upvotes]: I'm trying to reconcile two different sets of conditions on a group action $G$ acting on $X$ to make it a covering space action. Hatcher uses this condition (changed notation for consistency):

Each $x \in X$ has a neighbourhood $U$ such that all the images $g(U)$ for varying $g \in G$ are disjoint. In other words, $g_1(U) \cap g_2(U) \neq \varnothing$ impliles $g_1 = g_2$.

The other comes from Schlag and is similar to Wikipedia's description of a properly discontinuous action:

Let $K \subset \Omega$ be compact. Then the cardinality of $\{g \in G : g(K) \cap K \neq \varnothing\}$ is finite.

Does one of these imply the other?

REPLY [1 votes]: Note that when speaking of the Schlag definition, we require the space be locally compact.
I first note that a Hatcher action is not necessarily a Schlag action. I'm stealing the proof of this another question.
Consider $X = \mathbb{R}^2 \setminus \{(0, 0)\}$ and the action of $\mathbb{Z}$ on this space given by $n \cdot (x, y) = (2^n x, 2^{-n} y)$. It's easy to show that this action is a Hatcher covering space action. For suppose we have $(x, y) \in X$. Then either $x \neq 0$ or $y \neq 0$. In the first case, WLOG suppose $x > 0$ and let $U = (x/\sqrt{2}, \sqrt{2}x) \times \mathbb{R}$; in the second case, WLOG suppose $y > 0$ and let $U = \mathbb{R} \times (y / \sqrt{2}, \sqrt{2} y)$. However, this action fails to meet Schlag's definition. For consider the compact set $K = \{(x, 1) : x \in [0, 1]\} \cup \{(1, y) : y \in [0, 1]\}$. Then for every $n \geq 0$, we have $p_n = (2^{-n}, 1) \in K$. And we have $n \cdot p_n = (1, 2^{-n}) \in K$. Then $n(K) \cap K \neq \emptyset$ for all $n \geq 0$. This clearly contradicts Schlag's condition.
On the other hand, an action meeting Schlag's condition may not meet Hatcher's. In particular, consider the action of $\mathbb{Z}_2$ on $\mathbb{R}$ defined as $x \cdot y = y$. This clearly meets the condition laid out in Schlag, as for every compact $K$, the set $\{g \in \mathbb{Z}_2 : g(K) \cap K \neq \emptyset\}$ is finite. However, it definitely fails to meet Hatcher's condition since for all $U$, $0(U) = 1(U)$.
So these are two completely different conditions.


TITLE: I'm finding difficult to understand deduction theorem with inference rules
QUESTION [1 upvotes]: I'm finding difficult to understand deduction theorem with inference rules. Now i'm stuck with this question because of lack of understanding in that theorem.
The problem

   1. p=>q      Premise
   2. r=>s      Premise
   3. q∨s => t  Premise
   4. ¬t        Premise
   5. p         Assumption
   6. ....       ......
   7. ....       ......
   8. ....       ......
   9. ¬p         From 4 and 8, ¬_I(Reductio ad absurdum)(Contradiction of line
                 8 with line 4)

  10. r           Assumption
  11. ....        .....
  12. ....        .....
  13. ....        .....
  14.  ¬r          From 4 and 13, ¬_I(Reductio ad absurdum)(Contradiction of
                   line 13 with line 4)
  15.  ¬p∧¬r       From 9 and 14, ∧_I

REPLY [0 votes]: The missing steps is that after assuming $p$ you have by $p\Rightarrow q$ that $q$ follows and then $q\lor s$ follows and by $(q\lor s)\Rightarrow t$ follows $t$. Now you have a contradiction because of $\neg t$ so you can conclude $\neg p$ instead.
In similar way you conclude $\neg r$ and $\neg p\land\neg r$ follows.
A problem seem to be is that you're mixing up terminology. The deduction theorem states that you can prove a implication by assuming the premise and proving the consequence and by that is proving that the premise implies the consequence. Or formally:
$$\begin{align}\phi&\vdash \psi\\
&\vdash \phi\Rightarrow \psi\end{align}$$
This is not that central to the problem, instead it's reductio ad absurdum which states that a statement can be proved by assuming it's opposite and proving a contradiction by which you can conclude the statement. Or formally:
$$\begin{align}
\neg\psi&\vdash\phi\\
\neg\psi&\vdash\neg\phi\\
&\vdash\psi
\end{align}$$


TITLE: if $C$ is a vector space over a finite field $\mathbb{F_q}$ where q is prime, and $|C|=q^n, n\in \mathbb{N}$, then $dim(C)=n$?
QUESTION [1 upvotes]: If $C$ is a vector space over a finite field $\mathbb{F_q}$ where q is prime, and the number of different vectors in the vector space is $q^n, n\in \mathbb{N}$, then $dim(C)=n$ ?
It seems to me very simple, since the if $dim(C)>n$ then $|C|>q^n$ which contradicts that $|C|=q^n$, and $dim(C)<n$ then $|C|<q^n$ which again contradicts that $|C|=q^n$. The question is whether it's the right way, and if I need to prove something in addition to what I said?

REPLY [1 votes]: You could reason as follows: any finite dimensional vector space $V$ of dimension $r$ over a field $K$ is necessarily isomorphic to $K^r$, and thus when $K$ is finite, we will have $|V|=|K^r|=|K|^r$.
Therefore if $|C|=q^n$, and $|K|=|\mathbb F_q|=q$, then the dimension of $C$ must be $n$.
Of course, your argument also works (and is probably equivalent), but you need to explain why $\operatorname{dim}C>n$ implies $|C|>n$ and similarly for the other case. It's not so clear how the logic flows, as it currently stands.


TITLE: Every $3 \times 3$ complex matrix is unitarily similar to matrix of certain form
QUESTION [0 upvotes]: For what kinds of three-given-positions is it true that: for any matrix $A \in \mathbb C^{3 \times 3}$, $A$ is unitarily similar to a matrix whose entries at the given positions are $0$?
This problem occurred to me naturally when I was thinking about schur's Triangulization. I think if the given positions aren't in the same row or column, then the proposition stated above should be true.
Thanks in advance.

REPLY [1 votes]: A quick observation: none of these three positions can lie on a diagonal, because positive definite matrices are unitarily similar only to positive definite matrices.
Therefore, up to simultaneous permutations or rows and columns, the three positions must have one of the following three alignments:
$$
X=\pmatrix{\ast&\ast&\ast\\ 0&\ast&\ast\\ 0&0&\ast},
\ Y=\pmatrix{\ast&\ast&\ast\\ \ast&\ast&0\\ 0&0&\ast}
\ \text{ or }\ Z=\pmatrix{\ast&0&\ast\\ \ast&\ast&0\\ 0&\ast&\ast}.
$$
Of course, by Schur triangulation, the first form is always possible. The second form is also possible, as it can be obtained from the first form by applying a further unitary similarity transform $(U\oplus1)X(U^\ast\oplus1)$ for some appropriate unitary $2\times2$ matrix $U$.
So, the only question that remains is whether every complex $3\times3$ matrix is similar to some matrix in the form of $Z$.


TITLE: Existence of a connection $A$ on a holomorphic line bundle $L$, s.t $F(A)=(\deg L)\omega$
QUESTION [4 upvotes]: I'm reading this paper and at page 67, he states that for any line bundle $L$ over a Rieman surface there is a connection $A$ whose curvature is
$$
F(A)=(\deg L)\omega,
$$
where $\omega$ is a positive form. Does anyone know how can I prove it without using algebraic geometry arguments?

REPLY [5 votes]: Let me expand a bit Henri's (hi Henri!) answer, even if this is completely standard. In general, given a compact Kähler manifold $X$ of any dimension, given a holomorphic line bundle $L\to X$, and given any $(1,1)$-form $\eta$ representing $c_1(L)$, there exists a smooth hermitian metric $h_\eta$ on $L$ such that its Chern curvature satisfies
$$
\frac i{2\pi}\Theta(L,h_\eta)=\eta.
$$
The proof goes as Henri was saying, that is: fix any hermitian metric $h$ on $L$, take its Chern curvature form, then $\frac i{2\pi}\Theta(L,h)\in c_1(L)$. But then, $\frac i{2\pi}\Theta(L,h)-\eta$ is an exact form, and the $\partial\bar\partial$-lemma tells us that there exists a real function $f$ on $X$ such that
$$
\frac i{2\pi}\Theta(L,h)-\eta=\frac i{2\pi}\partial\bar\partial f.
$$
Now, make a conformal change of the metric $h$ using $f$ as follows: $h_\eta:=e^fh$. The Chern curvature of this new metric satisfies
$$
\frac i{2\pi}\Theta(L,e^fh)=-\frac i{2\pi}\partial\bar\partial f+\frac i{2\pi}\Theta(L,h)=\eta.
$$
To finish with, if your $X$ is a compact Riemann surface (you didn't mention explicitly compactness in your question, but I guess you just missed it? ) then $H^2(X,\mathbb Z)\simeq\mathbb Z$. Thus (I also also imagine that your Kähler class $[\omega]$ was chosen to be a positive generator of $H^2(X,\mathbb Z)$, otherwise what you say is trivially false...), $c_1(L)=\deg L$ and $\deg L\,\omega$ is in the right cohomology class (namely $c_1(L)$), so that in the preceding argument you can replace $\eta$ by $\deg L\,\omega$.


TITLE: How many roots of complex equation given in an interval
QUESTION [1 upvotes]: Given $z^4-5z+1=0$. Determine how many roots of that equation on $1 \leq |z| \leq 2$.

Do you have any idea to solve this problem? Honestly, I have tried some classic ways but that interval giving me a headache. Does that mean the roots are bounded between $1$ and $2$? Please give me your help

REPLY [0 votes]: You get $|5z|>|z^4+1|$ for $|z|=1$ and $|z^4|>|5z+1|$ for $|z|=2$ which allows you via Rouché to find the number of roots in the disks with radius $1$ and $2$ and per subtraction of the sets the number of roots in the annulus.


TITLE: Show that a locally compact Hausdorff space is regular.
QUESTION [10 upvotes]: Show that a locally compact Hausdorff space $(X,\tau)$ is regular.

I have already shown that a compact Hausdorff space is regular.
My textbook proposes 2 methodes, but I get stuck at both. The first method looks the most elegant, but how can I continue?
Compactification method.
Consider the compactification $(X_\infty, \tau_\infty)$ where $X_\infty = X\sqcup \infty$ and $\tau_\infty = \tau \cup \{ X_\infty \setminus K: K \text{ is a compact subset of } X\}$
Then $(X_\infty, \tau_\infty)$ is regular.
Let $x\in X\setminus F, F\subseteq X$ closed in $\tau$. Then $x\in X_\infty$ and $F\sqcup \{ \infty\}$ is closed in $\tau_\infty$. By regularity:
$$(\exists U_\infty, V_\infty \in \tau_\infty)(x\in U_\infty, (F\sqcup \{ \infty\} ) \subseteq V_\infty, U_\infty\cap V\infty = \varnothing)$$
Since $\infty \in V_\infty$ then $U_\infty \in \tau$.
How can I prove $V_\infty \setminus \{ \infty\} \in \tau?$ Any pointers?
Direct method:
Consider $x\in X\setminus F, F\subseteq X$ closed in $\tau$.
We are on the lookout for $(U, V\in \tau)$ such that $U\cap V = \varnothing, x\in U, F\subseteq V$.
Since $x\in X$ there (exists $K\subseteq X$ compact)($K$ is a neighbourhood of $x$)
Consider the compact subspace $(K, \tau_K)$ of $(X,\tau)$ which is Hausdorff. Then $K\cap F$ is closed in $\tau_K$ which makes $(K,\tau_K)$ regular. And then $(\exists U_K, V_K \in \tau_K)(x\in U_K, (K\cap F)\subseteq V_K, U_K\cap V_K =  \varnothing)$.
But how can I expand this $V_K$, such that $F\subseteq V$?

REPLY [6 votes]: The second approach can be made clearer (for my tastes, which do not have to agree with yours) by using the English language more.
A simple reformulation is that you are looking for a closed neighbourhood of $x$ that does not meet $F$. Now $x$ has a compact neighbourhood $K$ and a closed neighbourhood $W_K$ in $K$ that does not meet $F$. Since $K$ is a neighbourhood of $x$, $W_K$ is also a neighbourhood of $x$ in $X$, and since $K$ is closed, $W_K$ is also closed in $X$.
(The closed neighbourhood $W_K$ can be chosen as the closure of $U_K$ in your formulation of the proof.)


TITLE: Counting tree nodes that end probabilistically
QUESTION [0 upvotes]: Suppose we have $N$ root nodes that can branch into $N$ new nodes every level. There is a maximum of 64 levels. However, on any given step, each node has a chance $P$ of terminating. What is the expected value of $S$, the total number of nodes in the tree?
Is the answer simply
$$S = \sum\limits_{n=0}^{63}(1-P)^n *N^n  $$
or something like that? This is similar to other questions on here such as Expected number of leaf nodes resulting from branching process or expected value tree structure.

REPLY [1 votes]: Each level should be expected to contain $C[N(1-P)]$ nodes, where $C$ is the number of nodes on the previous level. This is because every $C$ that survives, which is $C(1-P)$ on average, multiplies to $N$ more nodes. Thus the expected total, $S$ is indeed
$$S = N\sum\limits_{n=0}^{63} \left[N(1-P)\right]^n$$


text:
{\bf Problem.} Compute \[\dfrac{2^3-1}{2^3+1}\cdot\dfrac{3^3-1}{3^3+1}\cdot\dfrac{4^3-1}{4^3+1}\cdot\dfrac{5^3-1}{5^3+1}\cdot\dfrac{6^3-1}{6^3+1}.\]
{\bf Level.} Level 3
{\bf Type.} Intermediate Algebra
{\bf Solution.} Let $S$ be the value of the given expression. Using sum and difference of cubes to factor, we get \[\begin{aligned} S &= \dfrac{(2-1)(2^2+2+1)}{(2+1)(2^2-2+1)}\cdot\dfrac{(3-1)(3^2+3+1)}{(3+1)(3^2-3+1)} \cdot\dfrac{(4-1)(4^2+4+1)}{(4+1)(4^2-4+1)}\cdot\dfrac{(5-1)(5^2+5+1)}{(5+1)(5^2-5+1)}\cdot\dfrac{(6-1)(6^2+6+1)}{(6+1)(6^2-6+1)} \\ &= \frac{1}{3} \cdot \frac{2}{4} \cdot \frac{3}{5} \cdot \frac{4}{6} \cdot \frac{5}{7} \cdot \frac{2^2+2+1}{2^2-2+1} \cdot \frac{3^2+3+1}{3^2-3+1} \cdot \frac{4^2+4+1}{4^2-4+1} \cdot \frac{5^2+5+1}{5^2-5+1} \cdot \frac{6^2+6+1}{6^2-6+1}.\end{aligned}\]The first product telescopes to $\tfrac{1 \cdot 2}{6 \cdot 7} = \tfrac{1}{21}$. The second product also telescopes due to the identity \[x^2 + x + 1 = (x+1)^2 - (x+1) + 1.\]That is, the terms $2^2+2+1$ and $3^2-3+1$ cancel, as do the terms $3^2+3+1$ and $4^2-4+1$, and so on, leaving just $\tfrac{6^2+6+1}{2^2-2+1} = \tfrac{43}{3}$. Thus, \[S = \frac{1}{21} \cdot \frac{43}{3} = \boxed{\frac{43}{63}}.\]

set_name: MATH


text:
\begin{document}

\title{Dual method for continuous-time Markowitz's Problems with nonlinear wealth equations}
\author{Shaolin Ji \thanks{School of Mathematics \& System Sciences, Shandong
University, Jinan 250100, People's Republic of China. email: jsl@sdu.edu.cn.
This work is supported by the National Basic Research Program of China (973
Program, No. 2007CB814900). This work was submitted to SIAM Journal on Control
and Optimization on August 21, 2007 (manuscript number: 070066).} }
\date{}
\maketitle

\textbf{Abstract. }Continuous-time mean-variance portfolio selection model
with nonlinear wealth equations and bankruptcy prohibition is investigated by
the dual method. A necessary and sufficient condition which the optimal
terminal wealth satisfies is obtained through a terminal perturbation
technique. It is also shown that the optimal wealth and portfolio is the
solution of a forward-backward stochastic differential equation with constraints.

\vskip0.2cm

\textbf{Keywords. }continuous-time mean-variance portfolio selection model,
stochastic optimal control, dual method, stochastic maximum principle,
forward-backward stochastic differential equation (FBSDE)

\vskip0.2cm

\textbf{AMS Subject classification.} 60H30, 60H10

\baselineskip=16pt

\pagestyle{myheadings} \thispagestyle{plain}

\section{Introduction\-}

Mean-variance portfolio selection in discrete time setting has been well
studied. But mean-variance portfolio selection has received little attention
in the context of continuous-time models \cite{st}. Recently several papers
studied various continuous-time Markowitz's models [2, 12-16, 27, 28]. There
are mainly two approaches which are employed to study this problem in
continuous-time case: the forward (primal) method [15, 16, 27] which is
inspired by the indefinite LQ control theory \cite{yo-zh}, and backward (dual)
method which is employed by Bielecki et al. \cite{bi-ji}.

The dual method (also known as martingale method) is first studied by Harrison
and Kreps \cite{ha-kr} and Pliska [23, 24]. A systematic account on this
method and its application to utility optimization problems can be found in
\cite{ka} and the references therein. It mainly includes two steps: the first
step is to compute the optimal terminal wealth, and the second one is to
compute the portfolio strategy replicating the obtained optimal terminal
wealth. It is worth pointing out that the dual method is powerful in solving
stochastic control problem with sample-wise constraint imposed on the state. A
sample-wise constraint requires that the state be in a given set with
probability 1; for example, a nonnegativity constraint on the wealth process,
i.e., bankruptcy prohibition. For a deeper discussion we refer the reader to a
recent paper by Ji and Zhou \cite{ji-zhou}.

In this paper, we study the continuous-time mean-variance portfolio selection
model with nonlinear wealth equation and bankruptcy prohibition. To apply the
dual method, we first give a backward formulation of this problem in which the
terminal wealth is regarded as the \textquotedblleft control variable". Note
that, in this formulation, the initial wealth becomes an additional
constraint. Under convexity assumptions, the backward formulation leads to a
static convex programming problem. Then a terminal perturbation technique is
introduced to derive a stochastic maximum principle which characterizes the
optimal terminal wealth. Due to the convexity assumptions on the coefficients,
we prove that the established stochastic maximum principle is also a
sufficient condition. The terminal perturbation technique is first studied in
El Karoui, Peng and Quenez \cite{el-pe-2001} to solve a recursive utility
optimization problem. Recently, Ji and Peng \cite{ji-peng} use this technique
and Ekeland's variational principle to obtain a necessary condition for the
mean-variance portfolio selection problem with non-convex wealth equations.
Finally, we show that the optimal wealth and portfolio can be solved by a
forward-backward stochastic differential equation (FBSDE) with constraints.

This paper is organized as follows: in section 2, we introduce continuous-time
mean-variance portfolio selection model with nonlinear wealth equation and
bankruptcy prohibition as well as its equivalent backward formulation.
Applying Lagrange multiplier and terminal perturbation technique, we obtain a
necessary and sufficient condition for optimality in section 3. In section 4,
we prove that there exists an optimal solution of the continuous-time
mean-variance portfolio selection problem and it can be obtained by solving a
FBSDE. Finally, section 5 closes the paper with some concluding remarks.

\section{Problem formulation}

Let $W(\cdot)=(W_{1}(\cdot),\ldots,W_{d}(\cdot))^{\prime}$ be a standard
d-dimensional Brownian Motion defined on a complete probability space
$(\Omega,\mathcal{F},P)$. The information structure is given by a filtration
$F=\{\mathcal{F}_{t}\}_{0\leq t\leq T}$, which is the $\sigma-$algebra
generated by the Brownian Motion $W(\cdot)$ and augmented. For any given
Euclidean space $H$, we denote by $M^{2}(0,T;H)$, the space of all
$\mathcal{F}_{t}-$progressively measurable processes $x(\cdot)$\ with values
in $H,$ such that
\[
E\int_{0}^{T}\mid x(t)\mid^{2}dt<\infty.
\]
Denote by $L^{2}(\Omega,\mathcal{F}_{T},P)$, the space of all $\mathcal{F}
_{T}-$measurable random variable $\xi$ with value in $R$, such that $E\mid
\xi\mid^{2}<\infty$.

\subsection{The wealth process}

Consider a complete market where there are one bank account (risk free
instrument) and $d$ stocks (risky instruments), and an investor who can decide
at time $t\in\lbrack0,T]$ the amount $\pi_{i}(t)$ to invest in the $i$th stock
($i=1,\ldots d$) with initial investment $x>0$. The respective prices of the
instruments are $S_{0}(\cdot)$ and $S_{1}(\cdot),\cdots,S_{d}(\cdot)$, and the
portfolio is $\pi(\cdot)=(\pi_{1}(t),\ldots,\pi_{d}(t))^{\prime}.$ We suppose
that the wealth process $X(\cdot)$ is governed by the following stochastic
differential equation
\begin{equation}
\left\{
\begin{array}
[c]{l}
-dX(t)=f(X(t),\sigma(t)^{\prime}\pi(t),t)dt-\pi(t)^{\prime}\sigma(t)dW(t),\\
X(0)=x
\end{array}
\right.  \tag{2.1}
\end{equation}
where the stock-volatility matrix $\sigma(\cdot)=\{\sigma_{ij}(\cdot)\}_{1\leq
i,j\leq d}$ is a predictable and bounded process. $\sigma(\cdot)$ is also
assumed to be invertible and $\sigma^{-1}(\cdot)$ be bounded uniformly in
$(t,\omega)\in\lbrack0,T]\times\Omega$. Set $Z(t)=\sigma(t)^{\prime}\pi(t).$
Then (2.1) can be rewritten as
\begin{equation}
\left\{
\begin{array}
[c]{l}
-dX(t)=f(X(t),Z(t),t)dt-Z(t)^{\prime}dW(t),\\
X(0)=x.
\end{array}
\right.  \tag{2.2}
\end{equation}

We assume

(H1) $f$ is continuous in $R\times R^{d}\times\lbrack0,T]$ for $a.a.\omega$
and has continuous bounded derivatives in $(X,Z)$;

(H2) $f(0,0,\cdot,\cdot)\in M^{2}(0,T;R);$

(H3) $f$ is convex with respect to $(X,Z);$

(H4) $f(0,0,t)\geq0$ a.s.

In the following, we give two specific examples to illustrate the model (2.1).

\begin{example}
The standard linear case.

The prices $S_{0}(\cdot)$ and $S_{1}(\cdot),\cdots,S_{d}(\cdot)$ are governed
by the equations
\[
\begin{array}
[c]{ll}
dS_{0}(t)=S_{0}(t)r(t)dt, & S_{0}(0)=s_{0};\\
dS_{i}(t)=S_{i}(t)[b_{i}(t)dt+\sum\limits_{j=1}^{d}\sigma_{ij}(t)dW(t)], &
S_{i}(0)=s_{i}>0;i=1,\ldots,d.
\end{array}
\]

We assume: the interest rate $r(\cdot)$ is a non-negative, predictable and
uniformly bounded scalar-valued process; the stock-appreciation rates
$b(\cdot)=(b_{1}(\cdot),\ldots b_{d}(\cdot))^{\prime}$ is a predictable and
uniformly bounded process.

Set $B(t):=(b_{1}(t)-r(t),\ldots,b_{m}(t)-r(t))^{\prime}$. Define the risk
premium process $\theta(t)\equiv(\theta_{1}(t),\ldots,\theta_{m}(t))^{\prime
}:=\sigma(t)^{-1}B(t)$. The wealth process $X(\cdot)$ satisfies the following
linear stochastic differential equation
\begin{equation}
\left\{
\begin{array}
[c]{l}
dX(t)=[r(t)X(t)+\pi(t)^{\prime}\sigma(t)\theta(t)]dt+\pi(t)^{\prime}
\sigma(t)dW(t),\\
X(0)=x.
\end{array}
\right.  \tag{2.3}
\end{equation}
Note that for this case,
\[
f(X,\sigma(t)^{\prime}\pi,t)=-r(t)X-\pi^{\prime}\sigma(t)\theta(t).
\]

\end{example}

\begin{example}
A large investor case.

An interesting example of a nonlinear wealth equation is the optimal portfolio
choice problem for a large investor considered in Cuoco and Cvitanic
\cite{cu-cv}. Refer to [3, 5, 7]\ for other models. In \cite{cu-cv},
$S_{0}(\cdot)$ and $S_{1}(\cdot),\cdots,S_{d}(\cdot)$ are described by
equations
\[
\begin{array}
[c]{ll}
dS_{0}(t)=S_{0}(t)[r(t)+l_{0}(X(t),\pi(t))]dt, & S_{0}(0)=s_{0};\\
dS_{i}(t)=S_{i}(t)[(b_{i}(t)+l_{i}(X(t),\pi(t)))dt+\sum\limits_{j=1}^{d}
\sigma_{ij}(t)dW(t)], & S_{i}(0)=s_{i}>0;i=1,\ldots,d
\end{array}
\]
where $l_{i}:R^{+}\times R^{d}\rightarrow R,\,0\leq i\leq d$ are given
functions which describe the effect of the wealth and the strategy. In this
case,
\[
f(X,\sigma(t)^{\prime}\pi,t)=-r(t)X-(X-\pi^{^{\prime}}\mathbf{1)}l_{0}
(X,\pi)-\pi^{^{\prime}}[b(t)-r(t)\mathbf{1}+l(X,\pi)].
\]

\end{example}

\subsection{Backward formulation of the problem}

Before formulating the problem, we point out that we distinguish the concepts
between initial investment and initial wealth. Throughout this paper, we
suppose that the initial investment $x$ of the investor is less than or equal
to his initial wealth $y$, i.e. $x\leq y$.

Usually the continuous-time mean-variance portfolio selection problem with
bankruptcy prohibition is formulated as: the investor chooses his portfolio
and initial investment $x$ so as to
\[
Minimize\qquad Var\,X(T)\equiv EX(T)^{2}-c^{2},
\]
\begin{equation}
subject\,\,to\left\{
\begin{array}
[c]{l}
EX(T)=c,\\
X(t)\geq0\qquad a.s.,\quad t\in\lbrack0,T],\\
\pi(\cdot)\in M^{2}(0,T;R^{m}),\\
(X(\cdot),\pi(\cdot))\,\text{satisfies\thinspace equation }(2.1)\text{ and
}0<x=X(0)\leq y,
\end{array}
\right.  \tag{2.4}
\end{equation}
where $c>0$ is a given expectation level with respect to the investor's
terminal wealth $X(T)$, and $X(t)\geq0$ means that no-bankruptcy is required.

\begin{definition}
A portfolio $\pi(\cdot)$ is said to be admissible if $\pi(\cdot)\in
M_{\mathcal{F}}^{2}(0,T;R^{m}),$ $EX(T)=c$ and the corresponding wealth
processes $X(t)\geq0\,a.s,\forall\,t\in\lbrack0,T].$
\end{definition}

We denote by $\mathcal{A}(x)$ the set of portfolio $\pi(\cdot)$ admissible for
the initial investment $x$. Set
\begin{equation}
V(y)=\underset{0<x\leq y,\pi\in\mathcal{A}(x)}{\min}\{E[X^{x,\pi}
(T)]^{2}-c^{2}\}. \tag{2.5}
\end{equation}

In the following we give an equivalent backward formulation of the above
optimization problem (2.4).

Since $\sigma(\cdot)$ is invertible, $Z(\cdot)$ can be regarded as the
"control variable" instead of $\pi(\cdot)$. Notice that selecting $Z(\cdot
)$\ is equivalent to selecting the terminal wealth $X(T)$ by the backward
stochastic differential equation (BSDE) theory \cite{pa-pe}. Hence the wealth
equation (2.2) can be rewritten as
\begin{equation}
\left\{
\begin{array}
[c]{l}
-dX(t)=f(X(t),Z(t),t)dt-Z(t)^{\prime}dW(t),\\
X(T)=\xi
\end{array}
\right.  \tag{2.6}
\end{equation}
where the terminal wealth $\xi$\ is the "control" to be chosen from the
following set
\[
U=\{\xi\mid\xi\in L^{2}(\Omega,\mathcal{F}_{T},P),\xi\geq0,a.s.\}.
\]
Note that nonnegative terminal wealth, i.e., $\xi=x(T)\geq0$ keeps the wealth
process nonnegative all the time, as implied by Assumption (H4) and the
comparison theorem for BSDEs.

This gives rise to the following optimization problem:
\[
\text{Minimize}\qquad J(\xi)\triangleq(E\xi^{2}-c^{2})
\]
\begin{equation}
subject\,\,to\left\{
\begin{array}
[c]{l}
E\xi=c,\\
X(0)\leq y,\\
\xi\in U.
\end{array}
\right.  \tag{2.7}
\end{equation}

It is clear that the original problem (2.4) is equivalent to (2.7). Hence,
hereafter we focus ourselves on solving (2.7). The advantage of doing this
lies in the fact that the state constraint in (2.4) now becomes a control
constraint in (2.7) since $\xi$ is regarded as the control variable. It is
well known in control theory that a control constraint is easier to deal with
than a state constraint. But there is a cost of doing so: the original initial
condition $X(0)=x$ now becomes a constraint, i.e., $X(0)\leq y$.

It is easy to prove that Assumptions (H1) and (H2) ensure there exists a
unique pair $(X(\cdot),Z(\cdot))\in M^{2}(0,T;R)\times M^{2}(0,T;R^{d})$ of
(2.6) \cite{pa-pe}. From now on, we denote the solution of (2.6) by $(X^{\xi
}(\cdot),Z^{\xi}(\cdot))$, whenever necessary, to show the dependence on $\xi
$. We also denote $X^{\xi}(0)$ by $X_{0}^{\xi}$.

\begin{definition}
$\xi$ is called admissible for given $y>0$ and $c>0$, if $\xi\in U$ and the
solution of (2.6) satisfies $X_{0}^{\xi}\leq y,$ $E\xi=c$. We shall denote by
$\mathcal{N}(y),$ the set of all admissible $\xi^{\prime}$s for any given $y$
and $c$.
\end{definition}

An admissible $\xi^{\ast}$ is called optimal if it attains the minimum of
$J(\xi)$ over $\mathcal{N}(y)$. From above discussions, we know that
$V(y)=J(\xi^{\ast})$. The optimal portfolio for (2.7) is called a variance
minimizing\thinspace\thinspace portfolio.\ After the optimal terminal wealth
$\xi^{\ast}$ is obtained, we can compute the optimal portfolio by solving (2.6).

For the feasibility of above optimization problem (2.4) and (2.7), we assume
the following slater condition:

(H5) For given $y>0$ and $c>0$, there exist an initial investment $x^{o}$
($0<x^{o}<y$) and a portfolio $\pi^{o}$ such that the corresponding terminal
wealth $X^{o}(T)\geq0$ and $EX^{o}(T)=c$.

\textbf{Remark}. In fact, the feasibility of (2.4) and (2.7) can be checked by
solving another optimization problem. For more details, see Appendix A.

Note that if $y\geq X_{0}^{c}$, then $\xi\equiv c$ is admissible. In this
case, it is obvious that $V(y)=0$. Hence, without loss of generality we can assume

(H6) $y<X_{0}^{c}.$

\section{A sufficient and necessary condition for optimality}

In this section, we derive a sufficient and necessary condition which
characterizes the optimal terminal wealth.

It is easy to check that the following $R-$valued functionals on $U$
\begin{align*}
\xi &  \mapsto X_{0}^{\xi}-y,\\
\xi &  \mapsto E\xi^{2}-c^{2},\\
\xi &  \mapsto E\xi-c
\end{align*}
are convex under Assumption (H3). Hence, applying classical results of convex
analysis \cite{lu}, it is easy to obtain the following lemma.

\begin{lemma}
We suppose (H1)-(H6). There exist real numbers $\lambda_{1}\geq0$ and
$\lambda_{2}$ such that
\begin{equation}
V(y)=\underset{\xi\in U}{\min}\{E\xi^{2}-c^{2}+\lambda_{1}(X_{0}^{\xi
}-y)+\lambda_{2}(E\xi-c)\}. \tag{3.1}
\end{equation}
Furthermore, if the minimum is attained in (2.7) by $\xi^{\ast}$, then it is
attained in (3.1) by $\xi^{\ast}$ with $\lambda_{1}(X_{0}^{\xi^{\ast}}-y)=0.$
Conversely, suppose there exist $\lambda_{1}^{o}\geq0$, $\lambda_{2}^{o}\in R$
and $\xi^{o}\in U$ such that the minimum is achieved in
\[
\underset{\xi\in U}{\min}\{E\xi^{2}-c^{2}+\lambda_{1}^{o}(X_{0}^{\xi
}-y)+\lambda_{2}^{o}(E\xi-c)\}
\]
with $\lambda_{1}^{o}(X_{0}^{\xi^{o}}-y)=0$, then the minimum is achieved in
(2.7) by $\xi^{o}$.
\end{lemma}

In the following, we introduce a terminal perturbation technique which is used
in [7, 10].

Let $\xi^{\ast}$ be optimal for (2.7) and $(X^{\ast}(\cdot),Z^{\ast}(\cdot))$
be the corresponding optimal trajectory, i.e., the solution of (2.6) under
$\xi^{\ast}$. Let $\hat{\xi}\in L^{2}(\Omega,\mathcal{F},P)$ such that
$(\xi^{\ast}+\hat{\xi})\in U$. Since $U$ is convex, then for any $0\leq
\rho\leq1$,
\[
\xi^{\rho}\triangleq\xi^{\ast}+\rho\hat{\xi}
\]
is also in $U$. Let $(\delta X(\cdot),\delta Z(\cdot))$ be the solution of the
following first order variational equation
\begin{equation}
\left\{
\begin{array}
[c]{l}
-d\delta X(t)=[f_{X}(X^{\ast}(t),Z^{\ast}(t),t)\delta X(t)+f_{Z}(X^{\ast
}(t),Z^{\ast}(t),t)\delta Z(t)]dt-\delta Z(t)^{\prime}dW(t),\\
\delta X(T)=\hat{\xi}.
\end{array}
\right.  \tag{3.2}
\end{equation}
Note that (3.2) is a linear BSDE and it has a unique pair $(\delta
X(\cdot),\delta Z(\cdot))\in M^{2}(0,T;R)\times M^{2}(0,T;R^{d})$. We denote
by $(X^{\rho}(\cdot),Z^{\rho}(\cdot))$ the solution of (2.6) corresponding to
$X(T)=\xi^{\rho}$. Set
\begin{align*}
\tilde{X}^{\rho}(t)  &  =\rho^{-1}[X^{\rho}(t)-X^{\ast}(t)]-\delta X(t),\\
\tilde{Z}^{\rho}(t)  &  =\rho^{-1}[Z^{\rho}(t)-Z^{\ast}(t)]-\delta Z(t).
\end{align*}
Using the techniques in \cite{peng-1993}, we have the following convergence results.

\begin{lemma}
Assume (H1) and (H2), then
\begin{align*}
\underset{\rho\rightarrow0}{\lim}\underset{0\leq t\leq T}{\sup}E  &
\mid\tilde{X}^{\rho}(t)\mid^{2}=0,\\
\underset{\rho\rightarrow0}{\lim}E\int_{0}^{T}  &  \mid\tilde{Z}^{\rho}
(t)\mid^{2}dt=0.
\end{align*}

\end{lemma}

For the reader's convenience, we sketch the proof of Lemma 3.2 in the Appendix B.

In order to derive the necessary condition, we introduce the adjoint equation
\begin{equation}
\left\{
\begin{array}
[c]{l}
dq(t)=q(t)[f_{X}(X^{\ast}(t),Z^{\ast}(t),t)dt+f_{Z}(X^{\ast}(t),Z^{\ast
}(t),t)^{\prime}dW(t)],\\
q(0)=1
\end{array}
\right.  \tag{3.3}
\end{equation}
where $(X^{\ast}(\cdot),Z^{\ast}(\cdot))$ is the optimal trajectory with
respect to $\xi^{\ast}$. (3.3) is a linear stochastic differential equation
and it has a unique solution in $M^{2}(0,T;R).$

Set
\[
M\triangleq\{\omega\in\Omega\mid\xi^{\ast}(\omega)=0\}.
\]

\begin{theorem}
We assume (H1)-(H6). $\xi^{\ast}$ is optimal to (2.7) if and only if there
exist constants $\lambda_{1}>0$ and $\lambda_{2}\in R$ such that
\begin{equation}
\begin{array}
[c]{l}
2\xi^{\ast}(\omega)+\lambda_{1}q_{T}(\omega)+\lambda_{2}\geq0\text{ a.s.\quad
on }M,\\
2\xi^{\ast}(\omega)+\lambda_{1}q_{T}(\omega)+\lambda_{2}=0\text{ a.s.\quad on
}M^{c}
\end{array}
\tag{3.4}
\end{equation}
with $X_{0}^{\xi^{\ast}}=y,$ where $q(t)$ is the solution of the adjoint
equation (3.3).
\end{theorem}

\textbf{Proof.} (1) Proof of the necessary condition.

By Lemma 3.1, there exist constants $\lambda_{1}\geq0$ and $\lambda_{2}$ such
that
\[
E(\xi^{\rho})^{2}-c^{2}+\lambda_{1}(X_{0}^{\xi^{\rho}}-y)+\lambda_{2}
(E\xi^{\rho}-c)\geq E(\xi^{\ast})^{2}-c^{2}+\lambda_{1}(X_{0}^{\xi^{\ast}
}-y)+\lambda_{2}(E\xi^{\ast}-c).
\]

Dividing the inequality by $\rho$ and sending $\rho$ to $0$, we obtain
\begin{equation}
2E(\xi^{\ast}\hat{\xi})+\lambda_{1}\delta X(0)+\lambda_{2}E\hat{\xi}\geq0
\tag{3.5}
\end{equation}
where $\delta X(0)$ denotes the solution of (3.2) at time $0$.

Applying It\^{o}'s lemma to $\delta X(t)q(t)$ yields
\[
\begin{array}
[c]{ll}
& E[\delta X(T)\cdot q(T)-\delta X_{0}\cdot q(0)]\\
= & E[-\int_{0}^{T}[(f_{X}(X^{\ast}(t),Z^{\ast}(t),t)\delta X(t)+f_{Z}
^{\prime}(X^{\ast}(t),Z^{\ast}(t),t)\delta Z(t))q(t)]dt+\\
& \int_{0}^{T}[(f_{X}(X^{\ast}(t),Z^{\ast}(t),t)\delta X(t)q(t)+<\delta
Z(t),f_{Z}(X^{\ast}(t)(t),Z^{\ast}(t),t)q(t)>)]dt\\
= & 0.
\end{array}
\]

Since $q(0)=1$, it is obvious that
\begin{equation}
\delta X_{0}=E[\hat{\xi}\cdot q(T)]. \tag{3.6}
\end{equation}

Replacing $\delta X_{0}$ with $E[\hat{\xi}\cdot q(T)]$\ in (3.5), we have that
for each $\bar{\xi}\in U$, the following inequality holds
\begin{align}
&  2E(\xi^{\ast}\hat{\xi})+\lambda_{1}E[\hat{\xi}\cdot q(T)]+\lambda_{2}
E\hat{\xi}\tag{3.7}\\
&  =E[(2\xi^{\ast}+\lambda_{1}q(T)+\lambda_{2})\cdot\hat{\xi}]\nonumber\\
&  =E[(2\xi^{\ast}+\lambda_{1}q(T)+\lambda_{2})\cdot(\bar{\xi}-\xi^{\ast
})]\nonumber\\
&  \geq0.\nonumber
\end{align}

Thus, it is easy to check that for each $\varepsilon>0$
\[
P\{\omega\mid\omega\in M,\,2\xi^{\ast}+\lambda_{1}q(T)+\lambda_{2}
<-\varepsilon\}=0.
\]

From the continuity property of probability, we have
\[
2\xi^{\ast}+\lambda_{1}q(T)+\lambda_{2}\geq0\text{ a.s.\quad on }M.
\]

By a similar argument,
\[
2\xi^{\ast}+\lambda_{1}q(T)+\lambda_{2}=0\text{ a.s.\quad on }M^{c}.
\]

Now we show that $\lambda_{1}\neq0.$ If $\lambda_{1}=0$, (3.4) becomes
\begin{equation}
\begin{array}
[c]{l}
\xi^{\ast}(\omega)\geq-\frac{\lambda_{2}}{2}\text{ a.s.\quad on }M,\\
\xi^{\ast}(\omega)=-\frac{\lambda_{2}}{2}\text{ a.s.\quad on }M^{c}.
\end{array}
\tag{3.8}
\end{equation}

There are two cases: one is $M$ is nonempty and the other is $M$ is empty. For
the first case, we deduce that $\xi^{\ast}=0$ which contradicts to the
constraint $E\xi^{\ast}=c>0$. For the second case, we have that $\xi^{\ast}=c$
from (3.8) and the constraint $E\xi^{\ast}=c$. But this contradicts to
Assumption (H6). In summary, we have $\lambda_{1}>0.$

By Lemma 3.1, we know $\lambda_{1}(X_{0}^{\xi^{\ast}}-y)=0$. Since
$\lambda_{1}>0$, it is easy to see $X_{0}^{\xi^{\ast}}=y$ holds.

(2) Proof of the sufficient condition.

Let $\xi\in U$ with $(X(\cdot),Z(\cdot))$ be the corresponding trajectory.
From lemma 3.1 we need only to prove that for any $\xi\in U$
\[
E\xi^{2}-c^{2}+\lambda_{1}(X_{0}^{\xi}-y)+\lambda_{2}(E\xi-c)\geq E(\xi^{\ast
})^{2}-c^{2}+\lambda_{1}(X_{0}^{\xi^{\ast}}-y)+\lambda_{2}(E\xi^{\ast}-c),
\]
i.e., to prove
\[
E\xi^{2}-E(\xi^{\ast})^{2}+\lambda_{1}(X_{0}^{\xi}-X_{0}^{\xi^{\ast}}
)+\lambda_{2}E(\xi-\xi^{\ast})\geq0.
\]

Set
\begin{align*}
\hat{\xi}  &  =\xi-\xi^{\ast},\\
f_{1}(x,z,t)  &  =f(X^{\ast}(t)+x,Z^{\ast}(t)+z,t)-f(X^{\ast}(t),Z^{\ast
}(t),t),\\
f_{2}(x,z,t)  &  =f_{X}(X^{\ast}(t),Z^{\ast}(t),t)x+f_{Z}(X^{\ast}(t),Z^{\ast
}(t),t)z.
\end{align*}

Consider the following equation
\[
\left\{
\begin{array}
[c]{rl}
-d(X(t)-X^{\ast}(t)) & =[f(X(t),Z(t),t)-f(X^{\ast}(t),Z^{\ast}
(t),t)]dt-(Z(t)-Z^{\ast}(t))^{\prime}dW(t),\\
& =[f_{1}(X(t)-X^{\ast}(t),Z(t)-Z^{\ast}(t),t)dt-(Z(t)-Z^{\ast}(t))^{\prime
}dW(t),\\
X(T)-X^{\ast}(T) & =\hat{\xi}.
\end{array}
\right.
\]

By Assumption (H3),
\[
f_{1}(x,z,t)\geq f_{2}(x,z,t)\qquad\forall x,z,\quad dP\otimes dt-a.s.
\]

Hence applying the comparison theorem for BSDEs, we obtain $X(t)-X^{\ast
}(t)\geq\delta X(t),$ $\forall t$ $P-a.s.,$ where $\delta X(\cdot)$ is the
solution of (3.2).

Using the following inequality
\[
(\xi^{\ast})^{2}-\xi^{2}\leq-2\xi^{\ast}(\xi-\xi^{\ast})
\]
and (3.6), we have
\[
\begin{array}
[c]{ll}
& E\xi^{2}-E(\xi^{\ast})^{2}+\lambda_{1}(X_{0}^{\xi}-X_{0}^{\xi^{\ast}
})+\lambda_{2}E(\xi-\xi^{\ast})\\
\geq & 2E[\xi^{\ast}(\xi-\xi^{\ast})]+\lambda_{1}\delta X(0)+\lambda_{2}
E(\xi-\xi^{\ast})\\
\geq & 2E(\xi^{\ast}\hat{\xi})+\lambda_{1}\delta X(0)+\lambda_{2}E\hat{\xi}\\
\geq & E[(2\xi^{\ast}+\lambda_{1}q(T)+\lambda_{2})\hat{\xi}].
\end{array}
\]

Since (3.4) implies
\[
E[(2\xi^{\ast}+\lambda_{1}q(T)+\lambda_{2})\hat{\xi}]\geq0,
\]
we obtain the result. The proof is complete. $\blacksquare$

\section{Existence of the optimal solution}

In this section, we prove that there exists a unique optimal solution for the
optimization problem (2.7). We also show that the optimal solution can be
obtained by solving a FBSDE with constraints.

\begin{theorem}
Suppose that (H1)-(H6) hold. Then there exists a unique $\xi^{\ast}\in
L^{2}(\Omega,\mathcal{F}_{T},P)$ which attains the minimum of the problem (2.7).
\end{theorem}

\textbf{Proof.} The uniqueness is due to the strict convexity of the
functional
\[
\xi\mapsto J(\xi),\quad\xi\in U.
\]

As for the existence, consider the set given by
\[
\mathcal{B}=\{\xi\in\mathcal{N}(y);\quad J(\xi)\leq C\}
\]
where $C>0$ is a constant. It is clear that, for each constant $C$,
$\mathcal{B}$ is bounded, closed and convex. Hence $\mathcal{B}$ is weakly
compact and by classical results of convex analysis \cite{br}, we need only to
show that $J$ is weakly lower-semicontinuous. Since $J$ is convex and strongly
lower-semicontinuous (in fact, it is strongly continuous [6, 7]), it follows
that $J$ is lower-semicontinuous for the weak convergence \cite{br}.

Thus the minimum of the problem (2.7) is attained (refer to Corollary 3.20 in
\cite{br}). The proof is complete. $\blacksquare$

\begin{corollary}
We assume (H1)-(H6). Then there exist constants $\lambda_{1}>0$ and
$\lambda_{2}\in R$ such that the optimal $\xi^{\ast}$ has the form
\begin{equation}
\xi^{\ast}=\frac{1}{2}(-\lambda_{2}-\lambda_{1}q(T))^{+}. \tag{4.1}
\end{equation}

\end{corollary}

This is a direct consequence of Theorem 3.3 and Theorem 4.1. The proof is omitted.

Let $(X^{\ast}(\cdot),Z^{\ast}(\cdot))$ be the optimal wealth process and
portfolio associated with $\xi^{\ast}$ for problem (2.7).

\begin{theorem}
Suppose that (H1)-(H6) hold. Then there exist a positive number $\lambda_{1}$
and $\lambda_{2}\in R$ such that the following FBSDE
\begin{equation}
\left\{
\begin{array}
[c]{l}
dq(t)=q(t)[f_{X}(X(t),Z(t),t)dt+f_{Z}(X(t),Z(t),t)^{\prime}dW(t)],\\
q(0)=1,\\
-dX(t)=f(X(t),Z(t),t)dt-Z(t)^{\prime}dW(t),\\
X(T)=\frac{1}{2}(-\lambda_{2}-\lambda_{1}q(T))^{+}
\end{array}
\right.  \tag{4.2}
\end{equation}
with constraints
\begin{equation}
EX(T)=c\quad\text{and}\quad X(0)=y \tag{4.3}
\end{equation}
has a unique solution $(q(\cdot),X(\cdot),Z(\cdot)).$ Furthermore, we have
$(X(\cdot),Z(\cdot))=(X^{\ast}(\cdot),Z^{\ast}(\cdot))$ and $X(T)=\xi^{\ast}$.
\end{theorem}

\textbf{Proof.} Note that (4.1) is equivalent to (3.4). Then it is easy to
check that the solution of FBSDE (4.2) with (4.3) is just the optimal solution
of problem (2.7) by Theorem 3.3 and Theorem 4.1. The proof is complete.
$\blacksquare$

Finally, we show that the smoothness condition, i.e., Assumption (H1) may not
hold for the following examples:

\begin{example}
Suppose that taxes must be paid on the gains which are made on the risky
securities. The wealth process $X$ is governed by
\begin{equation}
\left\{
\begin{array}
[c]{l}
-dX(t)=-[r(t)X(t)+\pi(t)^{\prime}\sigma(t)\theta(t)-\alpha(\pi(t)^{\prime
}\sigma(t)\theta(t))^{+}]dt-\pi(t)^{\prime}\sigma(t)dW(t),\\
X(0)=x.
\end{array}
\right.  \tag{4.4}
\end{equation}

\end{example}

\begin{example}
Suppose that the borrowing interest rate $R(t)\geq r(t)$. In this case, the
wealth process $X$ satisfies
\begin{equation}
\left\{
\begin{array}
[c]{l}
-dX(t)=-[r(t)X(t)+\pi(t)^{\prime}\sigma(t)\theta(t)-(R(t)-r(t))(X(t)-

{\displaystyle\sum\limits_{i=1}^{d}}

\pi_{i}(t))^{-}]dt-\pi(t)^{\prime}\sigma(t)dW(t),\\
X(0)=x.
\end{array}
\right.  \tag{4.5}
\end{equation}

\end{example}

But in this case, we can still prove that (3.4) is a sufficient condition for
optimality. To this end, we need an additional assumption:

(H1)' $f$ is uniformly Lipschitz with respect to $(X,Z)$.

Let $\xi^{\ast}\in U$ and $(X^{\ast}(\cdot),Z^{\ast}(\cdot))$ be the
corresponding trajectory.

\begin{theorem}
Suppose that (H1)' and (H2)-(H6) hold. If there exist constants $\lambda
_{1}>0$ and $\lambda_{2}\in R$ such that (3.4) with $X_{0}^{\xi^{\ast}}=y$ is
satisfied or equivalently, (4.2) with (4.3) has a solution $(q(\cdot),X^{\ast
}(\cdot),Z^{\ast}(\cdot))$, then $\xi^{\ast}=X^{\ast}(T)$ is an optimal
terminal wealth for problem (2.7).
\end{theorem}

\textbf{Proof.} We should only use subdifferentials instead of differentials
in the second part proof of Theorem 3.3. Note that now $f_{X}$ (resp. $f_{Z}
$)denotes a predictable process belonging $dP\otimes dt$ almost surely to
$\partial f(X^{\ast}(t),Z^{\ast}(t),t)$, where $\partial f$ is the
subdifferential of $f$ with respect to $X$ (resp. $Z$).

The proof is complete. $\blacksquare$

\section{Concluding remarks}

This paper investigates the continuous-time mean-variance portfolio selection
model with nonlinear wealth equation and bankruptcy prohibition. A stochastic
maximum principle is established via the dual method and terminal perturbation
technique. Under the smoothness conditions on the coefficients (Assumption
(H1)), we prove that the established stochastic maximum principle is not only
a necessary but also a sufficient condition for the optimal terminal wealth.
Then the optimal wealth and portfolio strategy, i.e., the solution of the
FBSDE (4.2) can be computed by the PDE approach of Ma, Protter and Yong
\cite{ma1}, the probability method of Hu and Peng \cite{hu} or numerical
methods (see also \cite{ma2} for systematical investigation). If the
smoothness assumption does not hold, we only obtain a sufficient condition,
i.e., Theorem 4.6. In this case, the main difficulty lies in the fact that the
corresponding FBSDE (4.2) may have discontinuous coefficients. We emphasize
that it remains an interesting open problem to solve FBSDEs with discontinuous
coefficients. But as shown in Theorem 4.6, our method in this paper can be
used to derive the existence of solutions for FBSDE (4.2). Another important
point to note here is that the existing results in the utility framework can't
cover the mean-variance model at all since the usual assumptions imposed on
utility functions are different from those on the mean-variance models.

\vskip0.5cm

{\large Appendix A.}

\vskip0.2cm

\textbf{Feasibility analysis.}

For a given initial investment $x>0$ and $c>0$, if there exists a portfolio
$\pi(\cdot)\in\mathcal{A}(x)$, the initial investment $x$ is called
admissible. Our aim is to compute the minimal admissible initial investment
which is denoted by $\bar{x}$. If $\bar{x}\leq y$ (resp. $\bar{x}<y)$, the
optimization problem (2.4) and (2.7) are feasible (resp. the slater condition holds).

Using similar analysis as in section 2, we can obtain $\bar{x}$ by solving the
following optimization problem:
\[
\bar{x}=\underset{\xi\in U}{\inf}X_{0}^{\xi},
\]
\[
\text{subject\thinspace\thinspace to \ }E\xi=c.
\]

For $\lambda\in R$, define
\[
\varphi(\lambda)=\underset{\xi\in U}{\inf}[X_{0}^{\xi}+\lambda E(\xi-c)].
\]

By the classical results of duality theory \cite{lu}, we have
\[
\bar{x}=\underset{\lambda\in R}{\max}\varphi(\lambda).
\]

\vskip0.5cm

{\large Appendix B.}

\vskip0.2cm

\textbf{Proof of Lemma 3.2}. From (2.6) and (3.2), we have
\[
\left\{
\begin{array}
[c]{ll}
-d\tilde{X}^{\rho}(t) & =\rho^{-1}[f(X^{\rho}(t),Z^{\rho}(t),t)-f(X^{\ast
}(t),Z^{\ast}(t),t)-\rho f_{X}(X^{\ast}(t),Z^{\ast}(t),t)\delta X(t)\\
& -f_{Z}^{^{\prime}}(X^{\ast}(t),Z^{\ast}(t),t)\delta Z(t)]dt-\tilde{Z}^{\rho
}(t)^{\prime}dW(t),\\
\tilde{X}^{\rho}(T) & =0.
\end{array}
\right.
\]
Let
\begin{align*}
A^{\rho}(t)  &  =\int_{0}^{1}f_{X}(X^{\ast}(t)+\lambda\rho(\delta
X(t)+\tilde{X}^{\rho}\left(  t\right)  ),Z^{\ast}(t)+\lambda\rho(\delta
Z(t)+\tilde{Z}^{\rho}(t)),t)d\lambda,\\
B^{\rho}(t)  &  =\int_{0}^{1}f_{Z}(X^{\ast}(t)+\lambda\rho(\delta
X(t)+\tilde{X}^{\rho}\left(  t\right)  ),Z^{\ast}(t)+\lambda\rho(\delta
Z(t)+\tilde{Z}^{\rho}(t)),t)d\lambda,\\
C^{\rho}(t)  &  =[A^{\rho}(t)-f_{X}(X^{\ast}(t),Z^{\ast}(t),t)]\delta
X(t)+[B^{\rho}(t)-f_{Z}(X^{\ast}(t),Z^{\ast}(t),t)]\delta Z(t).
\end{align*}
Thus
\[
\left\{
\begin{array}
[c]{l}
-d\tilde{X}^{\rho}\left(  t\right)  =(A^{\rho}(t)\cdot\tilde{X}^{\rho}\left(
t\right)  +B^{\rho}(t)\cdot\tilde{Z}^{\rho}(t)+C^{\rho}(t))dt-\tilde{Z}^{\rho
}(t)^{\prime}dW(t),\\
\tilde{X}^{\rho}(T)=0
\end{array}
\right.
\]
Using It\^{o}'s formula to $\mid\tilde{X}^{\rho}\left(  t\right)  \mid^{2}$ we
get
\begin{align*}
E  &  \mid\tilde{X}^{\rho}\left(  t\right)  \mid^{2}+E\int_{t}^{T}\mid
\tilde{Z}^{\rho}(s)\mid^{2}ds\\
\  &  =2E\int_{t}^{T}\tilde{X}^{\rho}(s)(A^{\rho}(s)\cdot\tilde{X}^{\rho
}(s)+B^{\rho}(s)\cdot\tilde{Z}^{\rho}(s)+C^{\rho}(s))ds\\
\  &  \leq KE\int_{t}^{T}\mid\tilde{X}^{\rho}(s)\mid^{2}ds+\frac{1}{2}
E\int_{t}^{T}\mid\tilde{Z}^{\rho}(s)\mid^{2}ds+E\int_{t}^{T}\mid C^{\rho
}(s)\mid^{2}ds
\end{align*}

where $K$ is a constant. So
\begin{align*}
E  &  \mid\tilde{X}^{\rho}\left(  t\right)  \mid^{2}+\frac{1}{2}E\int_{t}
^{T}\mid\tilde{Z}^{\rho}(s)\mid^{2}ds\\
&  \leq KE\int_{t}^{T}\mid\tilde{X}^{\rho}(s)\mid^{2}ds+E\int_{t}^{T}\mid
C^{\rho}(s)\mid^{2}ds
\end{align*}

By the Lebesgue dominate convergence theorem, we have
\[
\underset{\rho\rightarrow0}{\lim}E\int_{0}^{T}\mid C^{\rho}(t)\mid^{2}dt=0.
\]

Applying Grownwall's inequality, we obtain the result. $\blacksquare$

\vskip0.5cm

\textbf{Acknowledgement. }The author would like to thank Prof. Shige Peng and
Dr. Hanqing Jin for some useful conversations. Especially, Assumptions
(H5)-(H6) are due to helpful discussions with Prof. Xunyu Zhou.

\vskip0.5cm

config: arxiv


TITLE: Why does $\lim_{n\to 0}\frac{x^n-1}{n}$ = ln(x)$?
QUESTION [1 upvotes]: I was watching a 3blue1brown video about exponentials, and in explaining why $e$ is the base where the derivative/integral is the same as the original function, he uses the above fraction. Is there some way of showing it? I tried using l'hopital's rule, but that makes it $$\lim_{n\to 0}\frac{nx^{n-1}}{1}$$ which is 0.

REPLY [2 votes]: If you're watching the video that I think you're watching (https://youtu.be/m2MIpDrF7Es), and if I recall correctly, then there is nothing to prove here. That limit is some number that depends only on $x$, and he chooses to call that number $\ln x$.
Of course, you could then ask how to prove that $\ln$ defined this way is the inverse of the exponential map. That's a different question, and one that, in the light of the answers given here, should be asked more carefully and with greater attention to exactly what you're given and where you want to end up.


text:
\begin{document}

\begin{abstract}
We study the \emph{picture space} $\PSd(G)$ of all embeddings of a finite graph $G$ as point-and-line arrangements in an arbitrary-dimensional projective space, continuing previous work on the planar case.  The picture space admits a natural decomposition into smooth quasiprojective subvarieties called \emph{cellules}, indexed by partitions of the vertex set of $G$, and the irreducible components of $\PSd(G)$ correspond to cellules that are maximal with respect to a partial order on partitions that is in general weaker than refinement.  We study both general properties of this partial order and its characterization for specific graphs.  Our results include complete combinatorial descriptions of the irreducible components of the picture spaces of complete graphs and complete multipartite graphs, for any ambient dimension~$d$.  In addition, we give two graph-theoretic formulas for the minimum ambient dimension in which the directions of edges in an embedding of $G$ are mutually constrained.
\end{abstract}

\maketitle

\section{Introduction}

The motivation for this paper is the geometric problem of determining the constraints on the directions of the lines formed by placing $n$ points in space and joining each pair of points with a line.

Let $G$ be a finite simple graph with vertices $V=V(G)$ and edges $E=E(G)$, let $\Ff$ be a field (typically algebraically closed), and let $\Pp^d=\Pp^d_\Ff$ denote projective $d$-dimensional space over~$\Ff$.  A \emph{picture} of $G$ consists of a point $P(v)$ for each vertex~$v$, and a line $P(e)$ for each edge $e$, all lying in~$\Pp^d$, subject to the conditions $P(v)\in P(e)$ whenever vertex~$v$ is an endpoint of edge~$e$.  The \emph{picture space} $\PS(G)=\PSd(G)$ of all pictures of~$G$ can be regarded naturally as a reduced scheme over~$\Ff$ (specifically, it is an algebraic subset of a product of Grassmannians, with the containment conditions expressible in terms of Pl\"ucker coordinates).

In general, the space $\PS(G)$ is not irreducible.  Its most important irreducible component, the \emph{picture variety} $\PV(G)$, consists of the Zariski closure of the locus of \emph{generic} pictures (i.e., those for which the points $P(v)$ are all different).  A picture in~$\PV(G)$ is called \emph{near-generic}; that is, it is either itself generic or is a limit of generic pictures.  Thus $\PV(G)=\PS(G)$ if and only if every picture is near-generic.  The projection of $\PV(G)$ onto the lines $\{P(e)\st e\in E\}$ (i.e., forgetting the locations of the points $P(v)$) is called the \emph{slope variety} of~$G$.

The picture space, picture variety and slope variety are collectively called \emph{graph varieties}; previous work of the second author on this subject includes \cite{GGV,Picspace,Slopes}.  A goal of this study is to understand the equations defining the picture variety as an irreducible component of the picture space; that is, the set of constraints on the directions of lines in a generic picture of~$G$.  In the case that $G$ is the complete graph on $n$ vertices, this is identical to the motivating problem stated at the start of this paper.

A related problem is to determine the component structure of the picture space.  Roughly speaking, each component other than $\PV(G)$ corresponds to a way in which the points of a picture can collapse, thus releasing some of the constraints on the directions of lines.  In the case of plane pictures (i.e., with ambient space $\Pp^2$), ``direction'' may be replaced with ``slope''.  The second author previously gave combinatorial descriptions of the components of the picture space, and of the generators of the ideal of slope constraints for an arbitrary graph~\cite{GGV}, and more detailed information about the Gr\"obner geometry of the picture space of the complete graph~\cite{Slopes}.  A key tool in these results is the theory of \emph{combinatorial rigidity} (for a good general reference, see \cite{GSS}).

The goal of this paper is to begin extending the theory of graph varieties to ambient dimension greater than~2.  Combinatorial rigidity is much less well understood in high dimension; on the other hand, some of the methods used in \cite{GGV} carry over effectively to the general setting, as we now explain.

The picture space has a natural decomposition into quasiprojective subvarieties called \emph{cellules}.  For each set partition $\pi$ of $V(G)$, the cellule $\PS_\pi(G)=\PSd_\pi(G)$ consists of the pictures for which $P(v)=P(w)$ if and only if $v,w$ belong to the same block of $\pi$.  For instance, the locus of generic pictures is the cellule corresponding to the partition of $V(G)$ into singleton subsets.  Every irreducible component of $\PS(G)$ is in fact the Zariski closure of some cellule (Proposition~\ref{cpt-cellule-closure}), although not every cellule closure is a full component (because some cellules can be contained in the closures of other cellules).  Accordingly, we define the \emph{cellule (partial) order} $\prec_{G,d}$ on set partitions $\pi,\sigma$ by
\begin{equation}
\label{partial-order}
\pi\prec_{G,d}\sigma\iff \PSd_\pi(G)\subseteq\overline{\PSd_\sigma(G)}.
\end{equation}
Therefore, describing the components of $\PSd(G)$ reduces to the combinatorial problem of determining the maximal set partitions with respect to the cellule order.

By way of motivation, consider the case $d=1$.  A one-dimensional picture of~$G$ is just an ordered $n$-tuple of points in $\Pp^1$, where $n=|V|$; the data corresponding to edges of $G$ is trivial.  Thus $\PS^1(G)=(\Pp^1)^n$, and the cellules are just the elements of the intersection lattice of the projectivized braid arrangement (see, e.g.,~\cite[pp.~8--9]{HA}), partially ordered by refinement: $\pi\prec_{G,d}\sigma$ if every block of~$\sigma$ is contained in some block of~$\pi$.  In the case $d=2$, some refinement relations disappear; for the precise statement, which uses rigidity theory, see \cite[Thm.~6.3]{GGV}.  As the ambient dimension~$d$ increases, the cellule order contains fewer and fewer relations.

We start by establishing the following general facts about the cellule order.  First, let $B$ be a set of vertices that induces an acyclic subgraph, and $\pi$ is any set partition containing $B$ as a block.  Then the points $\{P(v)\st v\in B\}$ of $B$ in a picture $P\in\PS_\pi(G)$ can be separated: that is, $P$ can be obtained as a limit of pictures in a cellule indexed by a refinement $\sigma$ of $\pi$.  Therefore, $\pi\prec_{G,d}\sigma$ (Corollary~\ref{acyclic-corollary}).  In particular, if $G$ itself is acyclic, then $\PS(G)$ is irreducible, and in fact smooth~\cite[\S7]{Picspace}.  An immediate application is a description of the  components of the picture space of the cycle $C_n$: if $d<n$ then $\PSd(C_n)$ is irreducible, while if $d\geq n$ then it has two components, namely the picture variety and the indiscrete cellule (the locus of pictures in which all points $P(v)$ coincide).  This component structure corresponds to the following simple geometric fact: in a generic picture of~$C_n$, the lines corresponding to the edges connect $n$ distinct points, so their affine span has dimension at most $n-1$.  If $d<n$ then this constraint is vacuous; on the other hand, if $d\geq n$, then the affine span of the lines in an indiscrete picture can have dimension~$n$, so not every picture is near-generic.

On the other hand, in order to show that breaking up a block $B$ does \emph{not} correspond to a relation in $\prec_{G,d}$, it often suffices to calculate the dimension of the indiscrete cellule in $\PS(G|_B)$ (Proposition~\ref{squash-a-block}).  This suggests a method of determining the component structure for families of graphs that are \emph{hereditary}, i.e., closed under taking induced subgraphs.  As an application, consider the \emph{complete multipartite graph} $G=K_{q_1,\dots,q_n}$, which consists of $q_i$ vertices of color~$i$ for each $i$, $1\leq i\leq n$, with an edge between each pair of vertices of different colors.  The general results described above lead to a explicit, if somewhat technical, combinatorial description of the components of~$\PSd(G)$ (Theorem~\ref{Kmn-components}).  In the important special case of the complete graph~$K_n$ (which can be regarded as a complete multipartite graph with one vertex of each color), the component structure becomes much easier to describe.

\textbf{Theorem~\ref{Kn-components}:} Let $d\geq 3$.  Then the components of the picture space $\PSd(K_n)$ are exactly the closures of cellules corresponding to set partitions with no block of size two.

We find it notable that the result is the same for all ambient dimensions $d\geq 3$, and is much simpler than the $d=2$ case \cite[Thm.~6.4]{GGV}.  A rough combinatorial explanation is that for $d=2$, the minimal obstructions to irreducibility are rigidity circuits, while when $d\geq 3$, the minimal obstructions are cycles of length~$d$ (although this is not quite true; see below) which are combinatorially easier to describe.

As observed above, the cellule order becomes weaker and weaker as $d$ increases.  Accordingly, we define the \emph{minimum constraint dimension} $\mcd(G)$ to be the smallest positive integer~$d$ for which $\PSd(G)$ is not irreducible (or $\infty$ if no such $d$ exists).  Equivalently, $\mcd(G)$ is the smallest ambient dimension in which the directions of the lines in a generic $d$-dimensional picture of $G$ admit some mutual constraint.  For instance, as discussed above, the $n$-cycle $C_n$ has $\mcd(C_n)=n$; more generally, $\mcd(G)\leq\gir(G)$, where $\gir(G)$ denotes the \emph{girth} of $G$, that is, the length of the smallest cycle.  This bound is not sharp; for instance, the graph obtained by identifying two 4-cycles along an edge has girth~4, but minimum constraint dimension~3.  In fact, a result of B.~Servatius~\cite{Ser} implies that the gap between $\gir(G)$ and $\mcd(G)$ can be arbitrarily wide; see Remark~\ref{girth-mcd} below.

Previous work of the second author \cite[Theorem~14]{Picspace} implies that the minimum constraint dimension can be determined from the Tutte polynomial of $G$.  (For general information on the Tutte polynomial, see \cite{BryOx}.)  We give two simpler versions of this formula, respectively in terms of the graphic matroid of $G$ (Proposition~\ref{mcd-formula}) and ear decompositions (Proposition~\ref{ear-formula}).  As a more general class of examples, we calculate the minimum constraint dimension for the ``onion'' graph formed by identifying multiple paths at their endpoints.

\section{Components of the Picture Space} \label{component-section}

Fix an ambient dimension $d\geq 3$ and a graph $G=(V,E)$.  The notation $\pi\partn V$ means that $\pi$ is a partition of $V$ into pairwise disjoint subsets, called \emph{blocks}.  The corresponding equivalence relation will be denoted by $\sim_\pi$; thus $v\sim_\pi w$ if and only if $v,w$ belong to the same block of $\pi$.  The number of blocks of $\pi$ will be denoted $|\pi|$.

The \emph{cellule} corresponding to $\pi$ is defined as
\begin{equation}
\label{define-cellule}
\PSd_\pi(G) = \left\{P\in\PSd(G) ~\Big|~ P(v)=P(w)\iff v\sim_\pi w\right\}.
\end{equation}
Thus the picture space is the disjoint union of the cellules.
Moreover, each cellule is a smooth, quasiprojective subvariety
of $\PSd(G)$ with a natural bundle structure as follows.  Consider the
projection map $\PS_\pi(G)\to(\Pp^d)^{|\pi|}$ that records only the positions of the points (one for each block~$B_i$).  This makes $\PS_\pi(G)$ into a bundle with smooth base
  $$\left\{(p_1,\dots,p_{|\pi|})\in(\Pp^d)^{|\pi|} ~\Big|~ p_i\neq p_j \text{ for all $i\neq j$}\right\}$$
 and smooth fiber $(\Pp^{d-1})^{\delta(\pi,G)}$,
where $\delta(\pi,G)$ is the number of edges with both endpoints in
the same block of~$\pi$.  Therefore,
  \begin{equation}
  \label{dim-cellule}
  \dim \PS_\pi(G) = d|\pi|+(d-1)\delta(\pi,G).
  \end{equation}
Important special cases are the \emph{discrete cellule} $\PSD(G)$ and the \emph{indiscrete cellule} $\PSI(G)$, which correspond respectively to the \emph{discrete partition} of $V$ into singleton blocks, and the \emph{indiscrete partition} with only one block.  Thus the discrete cellule $\PSD(G)$ consists precisely of the generic pictures, and its closure is the picture variety $\PV(G)$, which is the whole picture space if and only if $\PSD(G)$ is the unique cellule of largest dimension~\cite[Thm.~4.5]{GGV}.  Meanwhile, the indiscrete cellule $\PSI(G)$ has a smooth bundle structure, with base $\Pp^d$ and fiber $(\Pp^{d-1})^{|E(G)|}$; it is the only cellule that is Zariski-closed in $\PS(G)$.  Note that
$\dim\PSD(G)=d|V|$ and $\dim\PSI(G)=d+(d-1)|E|$.

\begin{proposition}
\label{cpt-cellule-closure}
For every graph $G$ and ambient dimension $d$,
the components of $\PSd(G)$ are exactly the maximal sets of the form
$\overline{\PS_\pi}$.
\end{proposition}

\begin{proof}
Each cellule is irreducible and smooth (by its description
above as a bundle); therefore, its closure is irreducible
\cite[Example~1.1.4, p.~3]{Har}.  Therefore,
the picture space can be written as the union of finitely many
closed, irreducible subsets, namely the closures of the cellules,
so each irreducible component must appear in this union.
\end{proof}

Accordingly, to understand the component structure of $\PSd(G)$,
it suffices to describe the cellule order $\prec_{G,d}$ combinatorially.
This problem is the subject of the remainder of this section.

\begin{lemma}
Let $\sigma,\pi\partn V(G)$ with $\pi\prec_{G,d}\sigma$.
Then $\sigma$ refines $\pi$.
\end{lemma}

\begin{proof}
If $\sigma$ does not refine $\pi$, then there is some pair of vertices $x,y$ such that $x,y$ are in the same block of $\sigma$, but not in the same block of $\pi$.  The equality $P(x)=P(y)$ is a Zariski-closed condition that holds on $\PS_\sigma(G)$, hence on $\overline{\PS_\sigma(G)}$, but not on $\PS_\pi(G)$.  (In fact, we have shown more: if $\sigma$ does not refine $\pi$, then $\overline{\PS_\sigma(G)}\cap \PS_\pi(G)=\emptyset$.)
\end{proof}

\begin{proposition}
\label{split-doubleton}
Let $\pi,\sigma$ be partitions of $V(G)$ such that $\sigma$ is obtained from $\pi$ by splitting a doubleton block into two singletons, say $\pi=\{B_1,\dots,B_r,\{x,y\}\}$ and $\sigma=\{B_1,\dots,B_r,\{x\},\{y\}\}$.  Then $\PS_\pi(G)\subset\overline{\PS_\sigma(G)}$.  In particular, no partition containing a doubleton block corresponds to a maximal cellule.
\end{proposition}

\begin{proof}
Fix a picture $P_0\in\PS_\pi(G)$.  If $x,y$ are joined by an edge $e$, then let $L=P_0(e)$; otherwise, let~$L$ be any line containing the point~$P_0(x)=P_0(y)$.  Let $Z$ be the locus of all pictures $P$ such that
\begin{itemize}
\item $P(v)=P_0(v)$ for all vertices $v\neq y$;
\item $P(y)\in L$; and
\item $P(f)=P_0(f)$ for all edges $f$ with both endpoints in the same block of $\pi$.
\end{itemize}
Note that if $f$ is an edge with endpoints in different blocks
of $\pi$, then $P_0(f)$ is determined by the foregoing data,
with finitely many exceptions (namely, if $P(y)=P(v)$
for some $v\in V\sm\{x,y\}$).  Therefore, the map $P\mapsto P(y)$
is a birational equivalence of $Z$ with $L$ itself.

In particular, setting $P(y)=P_0(y)$ gives $P=P_0$.  It follows
that $P_0\in \overline{\PS_\sigma(G)}$.  Since $P_0$ was chosen
arbitrarily in $\PS_\pi(G)$, we conclude that
$\PS_\pi(G)\subset\overline{\PS_\sigma(G)}$.
\end{proof}

Note that the proof of Proposition~\ref{split-doubleton} fails for larger blocks.  Pulling apart the vertices in a block of size $r>2$ requires the corresponding $\binom{r}{2}$ lines in $P$ to lie in a common $(r-1)$-dimensional space, which need not be the case for all pictures.  On the other hand, a stronger result using essentially the same argument is as follows:

\begin{proposition}
\label{general-split-doubleton}
Let $G=(V,E)$ be any graph (not necessarily simple),
let $S\subseteq V$ and let $y\in V\sm S$
be a vertex such that no more than one edge incident
to $y$ has its other endpoint in $S$.  Let $S'=S\cup\{y\}$,
let $\pi$ be a partition of $V$ such that $S'$ is a block of
$\pi$, and let $\sigma=\pi\sm\{S'\}\cup\{S,\{y\}\}$.
Then $\PS_\pi(G)\subset\overline{\PS_\sigma(G)}$.
\end{proposition}

\begin{proof}
Let $P_0\in\PS_\pi(G)$.  If $G$ has an edge $e$ between $y$ and a vertex in $S$, then let $L=P_0(e)$, otherwise, let~$L$ be any line through the point $P_0(y)$.  As before, construct a family of pictures $P$ such that $P(x)=P_0(x)$ for $x\in V\sm\{y\}$; $P(y)$ varies along $L$; $P(e)=P_0(e)$ (if applicable), and $P(f)=P_0(f)$ for all edges $f$ with both endpoints in the same block of $\pi$.  Then all but finitely many $P$ lie in $\PS_\sigma(G)$, and setting $P(y)=P_0(y)$ gives $P=P_0$, so $P_0\in\overline{\PS_\pi(G)}$.
\end{proof}

\begin{corollary} \label{acyclic-corollary}
Let $W\subseteq V$ such that the induced subgraph $G|_W$ is acyclic.
Let $\sigma,\pi\partn V$ such that $W$ is a block of $\pi$ and $\sigma$ is
obtained by $\pi$ from subdividing $W$ into smaller blocks.  Then
$\PS_\pi(G)\subseteq\overline{\PS_\sigma(G)}$.
\end{corollary}

An immediate application of Corollary~\ref{acyclic-corollary} is a simple description of the components of the picture space of a cycle.

\begin{corollary} \label{cycle-corollary}
Let $C_n$ be the cycle on $n$ vertices.  If $d<n$, then $\PS^d(C_n)$ is irreducible, while if
$d\geq n$, then $\PS^d(C_n)$ has two components, namely the picture variety $\PVd(C_n)$
and the indiscrete cellule $\PSId(C_n)$.
\end{corollary}

\begin{proof}
By Corollary~\ref{acyclic-corollary}, every cellule other than $\PSId(C_n)$ is contained in the picture variety, so $\PSId(C_n)$ is the only other possible component.  Meanwhile, the cellule-dimension formula~\eqref{dim-cellule} implies that $\dim\PSId(G)\geq\dim\PVd(G)$ if and only if $d\geq n$;
as mentioned above, we have $\PSd(G)=\PVd(G)$ if and only if $\PSD(G)$ is the unique cellule of largest dimension~\cite[Thm.~4.5]{GGV}, implying the result.
\end{proof}

Indeed, when $d\geq n$, the picture space of $C_n$ is not irreducible for the geometric reason discussed in the Introduction --- the lines of a generic picture of $C_n$ must span an affine space of dimension at most $n-1$, while this constraint does not apply to pictures in the indiscrete cellule.
In this way, cycles behave in ambient dimension $\geq 3$ just as rigidity circuits do in ambient dimension~2 (cf.~\cite[Lemma~6.2]{GGV}).

We now turn to the problem of finding sufficient conditions for a cellule to be maximal in the cellule order.

\begin{definition}
Let $d\geq 2$.  A graph $H$ is called \emph{$d$-heavy} if the indiscrete cellule $\PSId(H)$ has maximum dimension (not necessarily uniquely) among all cellules of $\PSd(H)$.
\end{definition}

If $H$ is $d$-heavy, then the indiscrete cellule is maximal in the cellule order, hence is a component.  The following result reduces the geometric statement that a cellule $\PSd_\pi(G)$ is maximal to the combinatorial statement that the induced subgraph $G|_B$ is $d$-heavy for every block $B\in\pi$.

\begin{proposition}\label{squash-a-block}
Let $G$ be a graph and~$d\geq 2$.  Let~$B$ be a set of vertices of~$G$
such that the induced subgraph~$H=G|_B$ is $d$-heavy.
Let $\sigma,\pi$ be partitions of~$V(G)$ such that $\sigma$ refines~$\pi$
and $B\in\pi\sm\sigma$. Then $\PSd_\pi(G)\not\subset\overline{\PS_\sigma^d(G)}$.
\end{proposition}

\begin{proof}
Suppose that $B=B_1\cup\cdots\cup B_r$, where $B_1,\dots,B_r\in\sigma$.
Let $\phi$ be the map that takes a picture of $G$ and forgets all vertices
except those in~$B$, and all edges except those with both endpoints in~$B$.
We have a commutative diagram

\begin{equation}
\xymatrix{
 Z=\PS_\pi(G) \rto\dto^{\phi} & \PS(G) \dto^{\phi} & \PS_\sigma(G)=Y \dto^{\phi}\lto \\
\PSI(H) \rto & \PS(H) & \PS_{\tilde\sigma}(H)\lto
}
\end{equation}
where $\tilde\sigma=\{B_1,\dots,B_r\}$.
Here each vertical map is a surjection, and each horizontal
map is the natural inclusion.
Now, suppose that $\bar Y\supset Z$.  Then
$\overline{\phi(Y)}=\overline{\phi(\overline
Y)}\supset\overline{\phi(Z)}\supset\phi(Z)$.
But this contradicts
the hypothesis that $H$ is $d$-heavy.
\end{proof}

The complete multipartite graph $G=K_{q_1,\dots,q_n}$ has $q_i$ vertices of color~$i$ for each $i\in[n]=\{1,2,\dots,n\}$, with an edge between every pair of vertices of different colors (for short, a \emph{heterochromatic pair}).  For convenience, we assume that $q_1\geq\cdots\geq q_n>0$.  (Note that here $n$ denotes the number of colors, not the number of vertices.)  Proposition~\ref{squash-a-block} can be used as a general tool to characterize the component structures of picture spaces of complete and complete multipartite graphs.  Our methods may apply more generally to \emph{hereditary} familes of $d$-heavy graphs: a family $\G$ is hereditary if every induced subgraph of a member of~$\G$ is also a member of~$\G$.

We assume in what follows that either $n\geq 3$, or if $n=2$ then $q_1,q_2\geq 2$.  (Otherwise, $G$ is acyclic.)  Let $V_i$ be the set of vertices of color $i$ and let $V=V_1\cup\cdots\cup V_n$.  Each set partition
$\pi\partn V$ with $r$ blocks can be written as
$$
\pi ~=~ \{B_1 = B_{11}\cup\cdots\cup B_{1n},\ \ \dots,\ \
B_r = B_{r1}\cup\cdots\cup B_{rn}\}
$$
where $V_j=B_{1j}\dju\cdots\dju B_{rj}$ for each $j\in[n]$.  The dimension of the cellule $\PSd_\pi(G)$ depends only on the numbers $b_{ij}=|B_{ij}|$, so it is convenient to regard $\pi$ as a way of placing colored balls in boxes, with the $i^{th}$ box containing $b_{ij}$ balls of color~$j$ for each~$i,j$, and no box empty.  The cellule dimension formula \eqref{dim-cellule} may be rephrased in terms of balls and boxes:
\begin{equation} \label{ballbox}
\dim\PSd_\pi(G) = d|\{\text{boxes}\}| + (d-1)|\{\text{heterochromatic pairs in the same box}\}|.
\end{equation}

\begin{proposition} \label{complete-multip-degen}
Let $d\geq 3$ and let $G=K_{q_1,\dots,q_n}$ be a complete multipartite graph on $n\geq 2$ colors; if $n=2$, then assume that $q_1\geq 3$ and $q_2\geq 2$.  Then $G$ is $d$-heavy.  In particular, the indiscrete cellule of $\PSd(G)$ is an irreducible component.
\end{proposition}

\begin{proof}
Consider any set partition $\pi\partn V(G)$, corresponding to some way of placing colored balls in boxes as described above.  We will show that it is possible to  merge all the boxes into a single box, step by step, with each step either preserving or increasing the dimension of the corresponding cellule.  It will follow that the indiscrete cellule has dimension greater than or equal to every other cellule.  The following rules list types of mergers with this property.  (These rules are of course invariant with respect to permuting colors; it is more convenient to say, e.g., ``two red balls and one orange ball'' rather than ``two balls of the same color and a third ball of a different color''.)

\begin{enumerate}[label=(\roman{*}), ref=(\roman{*})]
\item\label{RR-O} Merge $B_1$ and $B_2$, where $B_1$ contains two red balls and $B_2$ contains an orange ball;
\item\label{RO-RO} Merge $B_1$ and $B_2$, where $B_1$ and $B_2$ each contain a red ball and a orange ball;
\item\label{RO-G} Merge $B_1$ and $B_2$, where $B_1$ contains a red ball and an orange ball, and $B_2$ contains a green ball.
\item\label{RO-X} Merge $B_1$ and $B_2$, where $B_1$ contains balls of at least three colors, and $B_2$ is arbitrary.
\item\label{R-O-G} Merge $B_1$, $B_2$ and $B_3$, where $B_1$ contains a red ball, $B_2$ contains an orange ball, and $B_3$ contains a green ball;
\item\label{RO-R-O} Merge $B_1$, $B_2$ and $B_3$, where $B_1$ contains a red and an orange ball, $B_2$ contains a red ball, and $B_3$ contains an orange ball.
\item\label{R-R-R-O-O} Merge $B_1,\dots,B_5$, where $B_1,B_2,B_3$ each contain a red ball and $B_4,B_5$ each contains an orange ball.
\end{enumerate}

Checking that the cellule dimension remains the same or increases after any of these mergers is an elementary consequence of \eqref{ballbox}.  For example, each of the mergers~\ref{RR-O}\dots\ref{RO-X} results in one fewer box, but at least two additional heterochromatic pairs in the same box, hence increases dimension by at least $-d+2(d-1)=d-2>0$; merger~\ref{R-R-R-O-O} increases dimension by at least $-4d+6(d-1)=2d-6\geq 0$.

We now show how to use the merging rules to obtain the indiscrete partition from an arbitrary partition~$\pi$.

\begin{itemize}
\item \textbf{Case 1:} $n\geq 3$.

\begin{itemize}
\item \textit{Case 1a:} If some box of $\pi$ contains two or more red balls, then either it contains all the orange balls or, by~\ref{RR-O}, can be merged with a box containing an orange ball.  The resulting box either contains all the green balls, or, by~\ref{RR-O}, can be merged with a box containing a green ball.  The resulting box contains balls of at least three colors, and so can be merged with every other box in turn by repeated applications of~\ref{RO-X}.

\item \textit{Case 1b:} If some box contains both a red ball and an orange ball, then either it contains all the green balls, or, by~\ref{RO-G}, can be merged with a box containing a green ball.  The resulting box contains balls of at least three colors, and so can be merged with every other box.

\item \textit{Case 1c:} The only other possibility is that $\pi$ is the discrete partition.  By~\ref{R-O-G}, we can merge three boxes containing balls of different colors, then proceed as in Case~1a.
\end{itemize}

\item \textbf{Case 2:} $n=2$.  Recall that we have assumed that $q_1\geq 3$ and $q_2\geq 2$.

\begin{itemize}

\item \textit{Case 2a:} If some box of $\pi$ contains two red balls, then by~\ref{RR-O} it can be merged with all boxes containing orange balls, then with all the other boxes.

\item \textit{Case 2b:} If two boxes each contain both a red and an orange ball, then we can first merge them by~\ref{RO-RO}, then proceed as in Case~2a.

\item \textit{Case 2c:} If one box contains two balls, one red and one orange, and all other boxes are singletons, then we can merge the doubleton box with two singleton boxes with different-colored balls by~\ref{RO-R-O}, then proceed as in Case~2a.

\item \textit{Case 2d:} If all boxes contain singletons, then we can first apply~\ref{R-R-R-O-O}, then proceed as in Case~2a.
\end{itemize}
\end{itemize}

In all cases, we can eventually merge all boxes into a single box, while increasing or preserving dimension at every stage of the process.
\end{proof}

It is possible to relax the restrictions on $d$ and $q_1,\dots,q_n$ in the statement of Proposition~\ref{complete-multip-degen}.  We have not done so, because if $d=2$, then the component structure of $\PSd(G)$ is already known~\cite[\S6]{GGV}, while $K_{2,2}$ is just a 4-cycle, so its component structure is given by Corollary~\ref{cycle-corollary}.

\begin{theorem} \label{Kmn-components}
Let $d\geq 3$, and let $G=K_{q_1,\dots,q_n}$ be a complete multipartite graph other than an acyclic graph or $K_{2,2}$.  Then the components of $\PSd(G)$ are exactly the cellule closures $\ol{\PSd_\sigma(G)}$, where $\sigma$ is a set partition of~$[n]$ in which every block either (i) contains only one vertex; (ii) contains at least two red vertices and at least two orange vertices; or
(iii) contains vertices of three or more colors.
\end{theorem}

\begin{proof}
Suppose that $\sigma$ contains a block that is not of any of these forms.  Then the induced subgraph on that block is acyclic, and by Corollary~\ref{acyclic-corollary}, the cellule $\PSd_\sigma(G)$ is not maximal.  On the other hand, if $\sigma$ meets the conditions of the theorem, then $\sigma$ is maximal in cellule order by Proposition~\ref{complete-multip-degen}.  Therefore, by Proposition~\ref{cpt-cellule-closure}, $\overline{\PSd_\sigma(G)}$ is a component of $\PSd(G)$, and these are all the components.
\end{proof}

An important special case is the complete graph $K_n$, which is the complete multipartite graph $K_{1,1,\dots,1}$.  If $n=2$ then $\PSd(K_n)$ is smooth; otherwise, since there is only one vertex of each color, condition~(ii) of Theorem~\ref{Kmn-components} is irrelevant, and conditions (i) and (iii) say that each block must be either a singleton, or else contain at least three vertices.  That is:

\begin{theorem} \label{Kn-components}
Let $d\geq 3$ and $n\geq 2$.  Then the components of $\PSd(K_n)$ are exactly the cellule closures $\ol{\PS_\sigma(K_n)}$, where $\sigma$ ranges over all set partitions of~$[n]$ with no blocks of size two.
\end{theorem}

We close this section with some potential problems for future study.  Proposition~\ref{complete-multip-degen} is far from sharp, in the sense that there are $d$-heavy graphs with many fewer edges than a complete multipartite graph.  This suggests looking for a lower bound on the number of edges that guarantees $d$-heaviness.  Another possibility is to look more closely at the cellule order.  For instance, is it possible to characterize all posets arising as $\prec_{G,d}$ for some $G$ and $d$?  (Every such poset must of course be a weakening of the partition lattice.)  In addition, what can be said about the order ideal generated by the discrete partition, i.e., the set of cellules consisting of quasi-generic pictures?

\section{Minimum constraint dimension as a combinatorial invariant}
\label{mcd-section}
Let $G$ be a connected graph that is not acyclic.  We define the \emph{minimum constraint dimension} $\mcd(G)$ to be the smallest positive integer~$d$ for which $\PSd(G)$ is not irreducible.  Implicit in the results of \cite{Picspace} is that $\mcd(G)$ can be calculated by reading off information about the irreducible components of $\PS(G)$ from the Tutte polynomial of $G$, as we now explain.

The Tutte polynomial has the well-known \emph{corank-nullity formula}
$$T_G(x,y) = \sum_{A\subseteq E} (x-1)^{r(E)-r(A)} (y-1)^{\nul(A)}$$
where $r(A)$ denotes the rank of $A$ (that is, the size of a maximum acyclic subset of~$A$) and $\nul(A)=|A|-r(A)$.  By \cite[Thm.~1]{Picspace}, the homology of $\PSd(G)$ is free abelian and concentrated in even real dimension, and the Poincar\'e polynomial of $\PSd(G)$ --- the generating function for its topological Betti numbers --- is given by the formula
  \begin{equation}\label{poinc}
  \sum_{i\geq0} \ q^{2i} \dim H_i(\PSd(G),\Qq) \ = \
  (\qan{d}-1)^{|V|-1}\qan{d+1}T_G\left(\frac{\qan{2}\qan{d}}{\qan{d}-1},\qan{d}\right)
  \end{equation}
where $\qan{d}=1+q+q^2+\cdots+q^{d-1}=(1-q^d)/(1-q)$.  In particular, $\PSd(G)$ is irreducible if and only if the Poincar\'e polynomial is monic of degree $d|V|$.  Comparing the leading terms of the summands (for details, see \cite[Prop.~3.3]{DMR}) implies that $\PSd(G)$ is irreducible if and only if $d\cdot\nul(A)<|A|$ for all nonempty $A\subseteq E$.  Therefore,
\begin{align}
\label{irred-condition}
\mcd(G) &= \min\{d\in\Nn \st d\cdot\nul(A)\geq|A|\ \text{ for some nonempty } A\subseteq E\}\\
\label{mcd-over-A}
&= \min_{\0\neq A\subseteq E}\left\lceil\frac{|A|}{\nul(A)}\right\rceil.
\end{align}
In particular, the condition \eqref{irred-condition} becomes stricter as $d$ increases, so in fact $\PSd(G)$ is irreducible if and only if $d<\mcd(G)$.

A consequence of \eqref{irred-condition} is the inequality $\mcd(G)\leq\gir(G)$, where $\gir(G)$ denotes the \emph{girth} of $G$, i.e., the size of the smallest cycle in $G$.  Geometrically, the lines corresponding to the edges of an $n$-cycle must all lie in some affine space of dimension $<n$, giving a nontrivial constraint on their directions when $d\geq n$; combinatorially, if $A\subseteq E$ is the edge set of a cycle, then $r(A)=|A|-1$, and so \eqref{irred-condition} fails for $d\geq |A|$.  On the other hand, cycles with common edges can interact to produce a tighter constraint on $\mcd(G)$,
as in the case of ``onion graphs''; see Remark~\ref{girth-mcd} below.  A rough explanation is that contracting the edge set of a cycle can decrease the girth of a graph; this observation suggests interpreting $\mcd(G)$ in terms not only of cycles in~$G$, but also cycles of graphs produced from~$G$ by repeatedly contracting cycles.

We can restrict the edge sets that need to be considered in \eqref{mcd-over-A}.
In what follows, we assume familiarity with basic facts about graphic matroids (see, e.g., \cite{Oxley}, particularly \S4).

\begin{proposition}
\label{mcd-formula}
For every connected, non-acyclic graph $G$, we have
$$\mcd(G) = \min_A\left\lceil\frac{|A|}{\nul(A)}\right\rceil$$
where $A$ ranges over all nonempty flats of the graphic matroid $M=M(G)$ such that $M|_A$ is indecomposable as a direct sum.  (Graph-theoretically, $A$ ranges over all nonempty edge sets of 2-connected induced subgraphs of~$G$.)
\end{proposition}

\begin{proof}
Let $A$ be a nonempty subset of $E$ minimizing $|A|/\nul(A)$.
If $M|_A=M|_{A_1}\oplus M|_{A_2}$, then $|A|=|A_1|+|A_2|$ and $\nul(A)=\nul(A_1)+\nul(A_2)$, so there is some $i$ for which $|A_i|/\nul(A_i)\leq|A|/\nul(A)$.  Therefore, we may assume that $M|_A$ is indecomposable.  Meanwhile, $|A|/\nul(A)=(\nul(A)+\rank(A))/\nul(A)=1+\rank(A)/\nul(A)$.  If $\bar A$ denotes the closure of $A$ in $M$, then $\rank(\bar A)=\rank(A)$ and $\nul(\bar A)\geq\nul(A)$; therefore, $|\bar A|/\nul(\bar A)\leq|A|/\nul(A)$.  Therefore, we may assume that $A=\bar A$, i.e., that $A$ is a flat of $M$.
\end{proof}

The formula can be restated in more explicitly graph-theoretic terms.  A \emph{partial ear decomposition} of $G$ is a sequence $(C_1,\dots,C_k)$ of pairwise disjoint edge sets such that $C_i$ is an induced cycle of $G/C_1/\cdots/C_{i-1}$ for each $i$.

\begin{proposition} \label{ear-formula}
For every connected, non-acyclic graph $G$, we have
\begin{equation}
\mcd(G) = \min_{(C_1,\dots,C_k)}\left\lceil\frac{\sum_{i=1}^k|C_i|}{k}\right\rceil
\end{equation}
the minimum over all partial ear decompositions of $G$.
\end{proposition}

\begin{proof}
Every 2-connected edge set $A$ (in fact, every 2-edge-connected graph) has an ear decomposition~\cite[Prop~2.10]{Frank}, so the result follows from replacing the set $A$ in Proposition~\ref{mcd-formula} with the partial ear decomposition $(C_1,\dots,C_k)$ and observing that $k=\nul(A)$.
\end{proof}

\begin{example}
\label{onion}
Let $a_1\leq\cdots\leq a_k$ be positive integers, and let $O=O(a_1,\dots,a_k)$
be the ```onion'' graph formed by identifying $k$ disjoint paths $P_1,\dots,P_k$
of lengths $a_1,\dots,a_k$ at their endpoints, as shown.
\includefigure{3in}{1.5in}{onion}
The 2-connected edge sets of $O$ are precisely the unions of two or more of
the $P_i$, so
$$\mcd(O) = \left\lceil\min_{2\leq r\leq k}\left(\frac{a_{1}+\cdots+a_{r}}{r-1}\right)\right\rceil.$$
On the other hand, the girth of $O$ is $a_1+a_2$, which can be considerably larger;
for instance, if $k\gg 0$ and $a_1=\cdots=a_k=a$, then $\mcd(O)=a$ and $\gir(O)=2a$.
\end{example}

\begin{remark}
\label{girth-mcd}
The ratio $\gir(G)/\mcd(G)$ can be arbitrarily high, at least when $\mcd(G)=2$.  By a theorem of B.~Servatius \cite{Ser}, there exist 2-rigid graphs of arbitrarily high girth.  For any positive integer~$\ell$, let $G$ be a 2-rigid graph with girth $\geq 2\ell-2$, let $C$ be a minimum-length cycle in~$G$, and let~$x,y$ be vertices of $C$ at maximum distance, so that every path in~$G$ between~$x,y$ has length $\geq \ell-1$.  Then $G+xy$ contains a 2-rigidity circuit~$G'$, which has $\mcd(G')=2$; on the other hand, $\gir(G')\geq\gir(G)\geq\ell$.
\end{remark}

\begin{remark}
\label{edmonds}
The inequality in \eqref{irred-condition} can be rewritten as $|A|\geq(d/(d-1))r(A)$, which closely resembles Edmonds' condition~\cite{Edmonds} for decomposability of a matroid into independent sets; when $d=2$, it is precisely Laman's characterization~\cite{Laman} of 2-rigidity independence.  For more on this connection, see \cite{DMR}.
\end{remark}

\bibliographystyle{amsalpha}
\bibliography{biblio.bib}
\end{document}