TITLE: Dependence of decidability on the encoding of Turing machines
QUESTION [3 upvotes]: Let $f : \{0, 1\}^* \to \{0, 1\}^*$ be a computable function. Given any encoding $\left<M\right>$ of Turing machines over binary (i.e., a function from the set of Turing machines to the set of strings over $\{0, 1\}^*$), consider the following language:
$$ L_f = \{\left<M\right> \mid M \mathrm{\ accepts\ } f(\left<M\right>)\} $$
Question: Does there exist a function $f$ for which the decidability/recognizability of this  language depends upon the particular encoding used?

REPLY [4 votes]: For a given computable $f$, the decidability of $L_f$ is independent of the encoding of Turing machines if and only $f$ is eventually injective (i.e., there exists a finite $X\subseteq\def\N{\mathbb N}\N$ such that $f\restriction(\N\smallsetminus X)$ is injective, or equivalently, $\{\def\<#1>{\langle#1\rangle}\<n,m>:n\ne m,f(n)=f(m)\}$ is finite).

If $f$ is computable and eventually injective, then $L_f$ is undecidable for any encoding.

Assume for contradiction that $L_f$ is decidable. Then
$$\{m\in\N:\exists n\in\N\:(f(n)=m\land n\notin L_f)\}$$
is r.e., hence it is accepted by infinitely many Turing machines; in particular, using the assumption, it is accepted by a TM $M$ such that $f(n)\ne f(\<M>)$ for all $n\ne\<M>$. Then
$$\<M>\in L_f\iff M\text{ accepts }f(\<M>)\iff\<M>\notin L_f,$$
a contradiction.

If $f$ is not eventually injective, then the decidability of $L_f$ depends on the encoding.

As shown in Aryeh’s answer, $L_f$ is undecidable under the standard encoding, hence it suffices to exhibit an encoding that makes $L_f$ is decidable. Let $\{M_m:m\in\N\}$ be any enumeration of TMs, and define $X\subseteq\N$ by
$$n\in X\iff|\{m<n:f(n)=f(m)\}|\text{ is even.}$$
We define a new enumeration $\{M'_n:n\in\N\}$ by
$M'_n=M_{m(n)}$, where $m(n)$ is defined by induction on $n$:
$$m(n)=\begin{cases}
  \min\bigl\{m\in\N\smallsetminus\{m(i):i<n\}:M_m\text{ accepts }f(n)\bigr\},&\text{if }n\in X,\\
  \min\bigl\{m\in\N\smallsetminus\{m(i):i<n\}:M_m\text{ does not accept }f(n)\bigr\},&\text{if }n\notin X.
\end{cases}$$
To see that $\{M'_n:n\in\N\}$ indeed enumerates all TMs, assume for contradiction that $m$ is least such that $m\ne m(n)$ for all $n\in\N$. Since $f$ is not eventually injective, there are $n<n'$ such that $f(n)=f(n')$ and $\{0,\dots,m-1\}\subseteq\{m(i):i<n\}$. We may assume $n'>n$ is smallest such that $f(n')=f(n)$, which implies
$$n\in X\iff n'\notin X.$$
Thus, either $n''=n$ or $n''=n'$ satisfies
$$M_m\text{ accepts }f(n'')\iff n''\in X,$$
which implies $m(n'')=m$ by the definition of $m(n'')$, a contradiction.
Thus, we may define an encoding of TM by $\<M'_n>=n$, and then it follows from the definition that
$$L_f=X,$$
which is decidable.

The answer above assumes that an encoding of TM has to be injective; this is not specified in the OP, but I suppose this is just an omission, as I fail to see how something that assigns the same code to two different TM can be considered an “encoding” of TM.
Anyway, if we allow non-injective encodings, the answer is that the decidability of $L_f$ depends on the encoding for every $f$: it is undecidable under the standard encoding by Aryeh’s answer, while it is trivially decidable (because finite) for the constant encoding $\<M>=0$.


TITLE: Proving complex function is constant.
QUESTION [0 upvotes]: , I get that from the restrictions on $a,b$ we get that they can't both be $0$. I tried taking the partial with respect to $x$ of the given constant function but could not translate that into a 0 for the derivative of f or even a 0 for the partial of $Im(f)$ or $Re(f)$. What am I missing?

REPLY [0 votes]: Write $f=u+iv.$ Consider $g(z)= e^{(a-ib)f(z)}.$ Then $|g(z)| = e^{au(z) + bv(z)},$ which from the given hypothesis is constant. By the open mapping theorem, $g$ is constant. That implies $(a-ib)f(z)$ is constant, which implies $f$ is constant.


TITLE: the order of the factor ring $\mathbb{Z}_{15}\left [ x \right ] / \left \langle 3x^{2}+5x \right \rangle$
QUESTION [3 upvotes]: What is the order of the factor ring $\mathbb{Z}_{15}\left [ x \right ] / \left \langle 3x^{2}+5x \right \rangle$ ?
Since $x$ and $3x+5$ are not relatively prime polynomial in $\mathbb{Z}_{15}$, so I can't use the Chinese Remainder Theorem.
Any help please. Thank you.

REPLY [3 votes]: Let $f=3x^{2}+5x$ and $I=\langle f \rangle$.

$I \ni 3f = 9x^2+15x = 9x^2$.
$I \ni 5f = 15x^2+25x = 25x = 10x = -5x$.
$I \ni 5xf - 3f = 10x^2 - 9x^2 = x^2$.

Thus, $I=\langle 5x, x^2 \rangle$.
Therefore, for every $g \in \mathbb{Z}_{15}[x]$ we have $g \equiv ax+b \bmod I$, with $a \in \{0,1,2,3,4\}$.
Thus, $\mathbb{Z}_{15}[x] / I$ has $5 \cdot 15 = 75$ elements.


TITLE: Consistency of a family of probabilities in the construction of a pre-brownian motion
QUESTION [4 upvotes]: I'm trying to understand how to construct the pre-brownian motion and I'm stuck at trying to prove the consistency of a family to be able to apply the Kolmogorov extension theorem.
Definition. Let $S$ be any arbitrary set and $(X,\mathcal{F})$ a events space. Let $\Omega=X^{J}$ and for all $J\subset S$ ($J$ finite) and define $\pi_{J}$ the projection from $\Omega$ to $X_{J}$. Now, suppose that for each $J\subset S$ ($J$ finite) we have a probability measure $P_{J}$ defined over $X^{J}$. We say that $\{P_{J}:J\subset S, J~\text{finite} \}$ is a consistent family if for $J' \subset J$we have that $$P_{J}\Bigl( \pi_{J}\left(\pi_{J'}^{-1}(A) \right) \Bigr)=P_{J'}(A)$$
For $A\in \prod _{i\in J'} \mathcal{F}$.
Now, lets consider the space $\displaystyle\left(\mathbb{R}^{(0,\infty)}, \mathcal{B}(\mathbb{R})^{(0,\infty)} \right)$ and the density function $\displaystyle p(t,x)=\frac1{\sqrt{2\pi t}} e^{\frac{-x^{2}}{2t}}$.
So for $J=\{t_{1},t_{2},...,t_{n}\}$ and for $A_{1},A_{2},...,A_{n} \in \mathcal{B}(\mathbb{R})$ we define the probability measure
$$P_{J}(A_{1} \times \cdots \times A_{n})=\int_{A_{n}}\int_{A_{n-1}} \cdots \int _{A_{1}} p(t_{1},x_{1})\prod p(t_{j+1}-t_{j}, x_{j+1} - x_{j}) dx_{1}dx_{2} \cdots dx_{n}$$
Where $P_{J}$ is defined over $(\mathbb{R}^{J},\mathcal{B}(\mathbb{R})^{J})$
How can I prove that $P_{J}$ is a consistent family of probability measures?
Thanks so much for the help.

REPLY [1 votes]: Say $J = \{t_1,\dots,t_n\}$ and $J' = \{t_{k_1},\dots,t_{k_m}\}$. Fix $A_{k_1},\dots,A_{k_m} \in \mathcal{B}(\mathbb{R})$. Then, $$\pi_J(\pi_{J'}^{-1}(A_{k_1}\times \dots \times A_{k_m})) = \mathbb{R}\times\dots\times\mathbb{R}\times A_{k_1}\times\mathbb{R}\times\dots\times\mathbb{R}\times A_{k_2}\times \mathbb{R}\times\dots.$$ So, with $A := A_{k_1}\times\dots\times A_{k_m}$, we have $$P_J(\pi_J(\pi_{J'}^{-1}(A))) = \int \dots \int p(x_1,t_1)p(x_2-x_1,t_2-t_1)\dots p(x_n-x_{n-1},t_n-t_{n-1})dx_1\dots dx_n.$$ The integrals over $x_1,\dots,x_{k_1-1}$ are over $\mathbb{R}$, as are the integrals over $x_{k_1+1},\dots,x_{k_2-1}$, etc, while the integrals over $x_{k_i}$ are over $A_{k_i}$. So, thinking through the notation for a minute, it suffices to prove the following two general identities: $$ \int_{\mathbb{R}} p(t_1,x_1)p(t_2-t_1,x_2-x_1)dx_1 = p(t_2,x_2)$$ $$\int_{\mathbb{R}} p(t_2-t_1,x_2-x_1)p(t_2-t_2,x_3-x_2)dx_2 = p(t_3-t_1,x_3-x_1).$$ But these are just standard gaussian integrals which can be easily computed via standard formulas.


text:
\section{A Toy Model}

\subsection{The Map}

The work in the previous chapter reduces the proof of Theorem \ref{main}
to the study of the pinwheel map $\Phi: R_1 \to R_1$, where
 $R_1$ is  shown in Figure 5.2.
This first return map turns out to be a polygon exchange map.
In this chapter, we will briefly discuss a simpler but related polygon
exchange map.

Though the simpler map is not the one we will
ultimately study in our proof of Theorem \ref{main}, we think
that it will prepare the reader for the more complicated system
we do study.    First,  the basic shapes that arise in the
simple system here arise in the more complicated system we
study later.  Second, both the system here and the one we
do study have a {\it renormalization scheme\/}.  It is the
renormalization scheme for the first return map
that leads to the self-similar nature
of the arithmetic graphs.

The dynamical system we study here is well known,
and indeed also arises in the study of outer billiards:
It is the first return map to a certain
 invariant domain for a dynamical system generated
by the outer billiards map and the rotational symmetry
group of the regular octagon.
Compare [{\bf T2\/}] and [{\bf BC\/}].
The system is a self map of the kite-shaped region $X$, shown as the
shaded region in Figure 6.1.  The region $X$ is best defined in terms
of a large regular octagon.    The smaller regular octagon, which
is a subset of $X$, is drawn in
for later reference.

\begin{center}
\resizebox{!}{1.6in}{\includegraphics{Pix/model1.eps}}
\newline
{\bf Figure 6.1:\/} The region $X$.
\end{center}

As shown in Figure 6.2, the
 region $X$ can be partitioned in two ways into right angled
isosceles triangles,
\begin{equation}
X=A_1 \cup B_1 = A_2 \cup B_2.
\end{equation}

There is a unique orientation-preserving isometry $\phi_A: A_1 \to A_2$.
The map $\phi_A$ rotates $3 \pi/4$ radians clockwise about the center
of the small octagon in Figure 6.1.  Likewise, there is a unique
orientation preserving isometry $\phi_B: B_1 \to B_2$.  The
map $\phi_B$ rotates $\pi/4$ radians counterclockwise about
the center of the big octagon in Figure 6.1.
  We have a map
$\phi: X \to X$ which restricts to $\phi_A$ on $A_1$ and $\phi_B$
on $B_1$.  The map $\phi$ is defined except on the segment
common to $A_1$ and $B_1$.

\begin{center}
\resizebox{!}{1.5in}{\includegraphics{Pix/model2.eps}}
\newline
{\bf Figure 6.2:\/} Two partitions of $X$.
\end{center}

\subsection{The Renormalization Scheme}

Let $O \subset X$ denote the inner octagon in Figure 6.1.
By construction, the center of $O$ is a fixed point of
$\phi$, and every point of $O$ has period $8$ with
respect to $\phi$.

\begin{center}
\resizebox{!}{2.8in}{\includegraphics{Pix/model3.eps}}
\newline
{\bf Figure 6.3:\/} Renormalization Scheme
\end{center}

Let $X'$ be the shaded component of $X-O$ shown in Figure 6.3.
We have partitioned $X'$ into two pieces, which we call
$A_1'$ and $B_1'$.    The third power $\phi^3$ maps
$X'$ to itself.  Figure 6.2 shows the pieces
$A_2'=\phi(A_1')$ and $A_3'=\phi(A_2')$ and
$B_2'=\phi(B_1')$ and $B_3'=\phi(B_2')$.

We have not drawn $A_4', B_4' \subset X'$, but
we observe that $A_4'$ and $B_4'$ relate to
$A_1'$ and $B_1'$ in the same say that
$A_2$ and $B_2$ relate to $A_1$ and $B_1$.
More precisely, there is an orientation reversing
dilation $\Theta: X' \to X$ such that
\begin{equation}
\label{renorm1}
\Theta^{-1} \circ \phi \circ \Theta=\phi^3
\end{equation}
on $X'$.
The map $\Theta$ is the {\it remormalization map\/}.
Having $\Theta$ by itself is nice, but we have a second
property that really pins things down.  Namely,
\begin{equation}
\label{renorm2}
X-O=X' \cup \phi(X') \cup \phi^2(X').
\end{equation}
In other words, every point of $X-O$ lies in the
orbit of a point in $X'$.

\subsection{The Periodic Points}

Our remormalization scheme allows us to get a complete
understanding of the periodic points of $\phi$.
The octagon $O$ consists of points having period $8$.
(The center is the one point of $O$ that has period $1$.)
For our purposes, it is nicer to think of $O$ as having
period $1$ {\it as a tile\/}.  The set $O$ is
preserved by $\phi$.  We set $O_0=O$.

By equation \ref{renorm1}, the region $X'$ contains a small
octagon
\begin{equation}
O'_0=\Theta^{-1}(O_0)
\end{equation}
that has tile-period $3$.
We set
\begin{equation}
O'_{k+1}=\phi(O'_k).
\end{equation}
The tiles $O'_k$ for $k=0,1,2$ all have tile-period $3$.
They comprise a tile-orbit.

Now we iterate.  By Equation \ref{renorm1}, the three octagons
\begin{equation}
O''_{3k}=\Theta^{-1}(O'_k); \hskip 30 pt k=0,1,2
\end{equation}
all have tile-period $9$.
Setting \begin{equation}
O''_{k+1}=\phi(O''_k),
\end{equation}
we produce $9$ small octagons
$O''_0,...,O''_8$ that all have tile-period $9$.
Next, we produce $27$ small octagons
$O^{(3)}_k$ for $k=0,...,26$, all having
tile-period $27$.   Figure 6.4 shows some of these
octagons.

\begin{center}
\resizebox{!}{3.5in}{\includegraphics{Pix/model4.ps}}
\newline
{\bf Figure 6.4:\/} Cascade of periodic tiles
\end{center}

Thus, we have produced, for each $n=0,1,2,3...$, a periodic
octagonal tile having tile-period $3^n$.   We claim that
every periodic point is contained in one of these octagons.
To see this, we use Equation \ref{renorm2}.
Clearly, the only periodic points of order $1$ lie in $O_0$.
Suppose $N$ is the smallest positive integer for which
we have not proven our result.  Let $y'$ be a periodic
point of period $N$.

Since $N>1$, we have $y' \in X-O$.  By Equation \ref{renorm2}, the point
$y'$ lies in the orbit of some point $x' \in X'$.   Let
$x=\Theta(x')$.  Note that
$\phi(X')$ and $\phi^2(X')$ are disjoint from $X'$.
Since $\phi^N(x')=x'$, we must therefore have $N=3M$ for
some integer $M$.   But then, by Equation \ref{renorm1},
we see that $x$ has period $M$.     By induction, $x$ lies
in one of our octagonal tiles.  But then, by construction,
so does $x'$.   Now we know that $x'$ is one of the
periodic points we have already studied.  So, the
same goes for $y'$, the original point of interest to us.

Using the renormalization scheme, we have been able to
classify all the periodic points of the system.  Incidentally,
we note that the complement of the octagons has dimension
larger than $1$, and the set of points where some iterate of
$\phi$ is undefined has dimension $1$.  Therefore,
$\phi$ has some aperiodic points.  This is the same argument
Tabachnikov [{\bf T2\/}] gives for the regular pentagon.

\newpage

config: arxiv


TITLE: Combinations of integers
QUESTION [0 upvotes]: I still try to get intuitive feeling of permutations and combinations, so far without much success. I am confused by the following exercise.
Exercise. Four integers are chosen at random between 0 and 9, inclusive. Find the probability that (a) they are all different, (b) not more than 2 are the same.
Answers a) $\frac{63}{125}$ b) $\frac{963}{1000}$
Ideas:
a) $\frac{9}{10}\frac{8}{10}\frac{7}{10}=\frac{63}{125}$. Good!
b)P (no more than 2 are the same) = 1 - P(all 4 are the same) - P(any 3 are the same)
P(all 4 are the same) = $\frac{1}{1000}$
P(any 3 are the same) = ?. Here the problem. I assume I should appreciate the probability by counting. Let try to do so
$_{4}P_{10}$ - total number of permutations.
$10$ - variations of the same numbers.
I am hot sure whether it's a right reasoning, if you know how to solve this exercise please share it with us.

REPLY [1 votes]: I’d do the second problem by counting rather than by working directly with probabilities. There are $10^4$ sequences altogether. The ‘bad’ sequences are those in which all $4$ numbers are the same; those with $3$ identical numbers and $1$ different number; and those with two pairs of identical numbers.

There are $10$ sequences in which all $4$ numbers are the same.
There are $10\cdot9=90$ ways to choose a number for the triplet and a different number for the unmatched one. There are then $4$ possible positions in the sequence for the unmatched number, so there are $4\cdot90=360$ sequences of this type.
For the two pairs case there are $10$ ways to choose the number that appears first in the sequence, and $9$ ways to choose the other number. There are $3$ possible positions for the mate to the first number, so there are $10\cdot9\cdot3=270$ sequences of this type.

Altogether we have $10+360+270=640$ ‘bad’ sequences, leaving $10000-640=9360$ ‘good’ sequences. The probability of getting a ‘good’ sequence is therefore $$\frac{9360}{10000}=0.936=\frac{117}{125}\;.$$
It’s actually easier to count the ‘good’ sequences directly. There are $4!\binom{10}4=5040$ sequences with no repeated numbers. A sequence with exactly $2$ identical numbers must contain $3$ distinct numbers, one of them repeated. There are $\binom{10}3=120$ ways to choose the $3$ numbers, there are then $3$ ways to choose which one is to be repeated, there are $\binom42=6$ ways to pick $2$ positions in the sequence for the matched pair, and there are then $2$ ways to distribute the other two numbers to the remaining $2$ positions. Thus, there are $120\cdot3\cdot6\cdot2=4320$ sequences with exactly $2$ identical numbers, and a total of $5040+4320=9360$ ‘good’ sequences. The probability of getting one of them is therefore $\frac{9360}{10000}$, exactly as before.


text:
\section{BIM Semidefinite Programming}
\label{sec: BIM SDP}
OPF is nonconvex due to \eqref{BIM}, and a standard semidefinite programming (SDP) relaxation has been developed to solve it \cite{dall2012distributed}. In this section we propose a different SDP relaxation, called BIM-SDP, that exploits the radial network topology to reduce the computational complexity of the standard SDP.

\subsection{Bus Injection Model Semidefinite Programming}
BIM-SDP is derived by shifting the nonconvexity from \eqref{BIM} to some rank constraints and removing the rank constraints.

Let $|A|$ denote the number of elements in a set $A$, and $\her^{k \times k}$ denote the set of $k\times k$ complex Hermitian matrices.
Let $v_i\in\her^{|\ph_i|\times|\ph_i|}$ for $i\in\hN$ and $W_{ij}\in\mathbb{C}^{|\ph_{ij}|\times|\ph_{ij}|}$ for $i\sim j$. If these matrices satisfy
	\[
        	\begin{bmatrix} v_i^{\ph_{ij}} & W_{ij} \\ W_{ji} & v_j \end{bmatrix}
        	= \begin{bmatrix} \vct{V}_i^{\ph_{ij}} \\ \vct{V}_j \end{bmatrix}
        	\begin{bmatrix} \vct{V}_i^{\ph_{ij}} \\ \vct{V}_j \end{bmatrix}^H,
	\quad i\rightarrow j,
    	\]
then \eqref{BIM} is equivalent to
    \[ \vct{s}_i = \sum_{j:\,i\sim j} \diag\left[ (v_i^{\ph_{ij}}-W_{ij})\mtx{y}_{ij}^H\right]^{\ph_i}, \quad i\in\hN. \]

\begin{lemma}
\label{lemma: V <=> W}
Let $v_i\in\her^{|\ph_i|\times|\ph_i|}$ for $i\in\hN$ and $W_{ij}\in\mathbb{C}^{|\ph_{ij}|\times|\ph_{ij}|}$ for $i\sim j$. If
\begin{itemize}
\item $v_0 = \vct{V}_0^\mathrm{ref} [\vct{V}_0^\mathrm{ref}]^H$ for some $\vct{V}_0^\mathrm{ref}\in\mathbb{C}^{|\ph_0|}$;
\item $\diag(v_i)$ is nonzero componentwise for $i\in\hN$;
\item $W_{ji}=W_{ij}^H$ for $i\rightarrow j$;
\item $\begin{bmatrix}
        v_i^{\ph_{ij}} & W_{ij} \\
        W_{ji} & v_j
        \end{bmatrix}$ is rank one for $i\rightarrow j$,
\end{itemize}
then Algorithm \ref{algorithm: recover V} computes the unique $\vct{V}$ that satisfies $\vct{V}_0=\vct{V}_0^\mathrm{ref}$ and
    \begin{subequations}
    \label{def v W}
    \begin{align}
    v_i &= \vct{V}_i \vct{V}_i^H, &\quad i\in\hN; \label{eq: def v}\\
    W_{ij} &= \vct{V}_i^{\ph_{ij}} (\vct{V}_j^{\ph_{ij}})^H, &\quad i\sim j.
    \end{align}
    \end{subequations}
\end{lemma}

	\begin{algorithm}[h!]
	\caption{Recover $V$ from $(v,W)$.}
	\label{algorithm: recover V}
	\begin{algorithmic}[1]

	\REQUIRE $(v,W)$ that satisfies the conditions in Lemma \ref{lemma: V <=> W}.
	\ENSURE $V$.

	\STATE $V_0 \leftarrow V_0^\mathrm{ref}$;
	\STATE $\hN_\text{visit} \leftarrow\{0\}$;

	\WHILE{$\hN_\text{visit} \neq \hN$}
		\STATE find $i\rightarrow j$ such that $i\in\hN_\text{visit}$ and $j\notin\hN_\text{visit}$;
		\STATE compute
		\begin{align*}
		V_j &\leftarrow \frac{1}{\trace\left(v_i^{\ph_{ij}}\right)} W_{ji}V_i^{\ph_{ij}}; \\
		\hN_\text{visit} &\leftarrow\hN_\text{visit}\cup\{j\};
		\end{align*}
	\ENDWHILE

	\end{algorithmic}
	\end{algorithm}

	Lemma \ref{lemma: V <=> W} is proved in Appendix \ref{app: V <=> W}. It implies that OPF can be equivalently formulated as BIM-OPF. Let $A\succeq0$ denote a hermitian matrix $A$ being positive semidefinte.

    	\begin{subequations}
    	\label{BIM OPF}
    	\textbf{BIM-OPF: }
    	\begin{align}
    	\min~~ & \sum_{i\in \hN} C_i(\vct{s}_i) \nonumber\\
	\mathrm{over}~~ & \vct{s}_i\in\mathbb{C}^{|\ph_i|} \text{ and } v_i\in\her^{|\ph_i|\times|\ph_i|} \text{ for }i\in\hN; \nonumber\\
    	& W_{ij}\in\mathbb{C}^{|\ph_{ij}|\times|\ph_{ij}|} \text{ for }i\sim j, \nonumber\\
	\mathrm{s.t.}~~ &
	\vct{s}_i = \sum_{j:\,i\sim j} \diag\left[ (v_i^{\ph_{ij}}-W_{ij})\mtx{y}_{ij}^H\right]^{\ph_i},
	\quad i\in\hN; \label{BIM s} \\
	& \vct{s}_i \in \hS_i, \quad i\in \hN^+;  \label{BIM constraint s}\\
    	& v_0 = \vct{V}_0^\text{ref} (\vct{V}_0^\text{ref})^H; \label{BIM constraint v0}\\
	& \underline{\vct{v}}_i \leq \diag(v_i) \leq \overline{\vct{v}}_i, ~\quad i\in \hN^+;  \label{BIM constraint v} \\
    	& W_{ij} = W_{ji}^H, \quad i\rightarrow j; \label{BIM hermitian}\\
	& \begin{bmatrix}
        v_i^{\ph_{ij}} & W_{ij} \\
        W_{ji} & v_j
        \end{bmatrix} \succeq 0, \quad i\rightarrow j; \label{BIM relax}\\
	& \rank\begin{bmatrix}
        v_i^{\ph_{ij}} & W_{ij} \\
        W_{ji} & v_j
        \end{bmatrix}=1, \quad i\rightarrow j \label{BIM rank}
    \end{align}
    \end{subequations}
where the vectors $\underline{v}_i$ and $\overline{v}_i$ in \eqref{BIM constraint v} are defined as
	\[ \underline{\vct{v}}_i := [ (\underline{V}_i^\phi)^2 ]_{\phi\in\ph_i}, ~
	\overline{\vct{v}}_i := [ (\overline{V}_i^\phi)^2 ]_{\phi\in\ph_i}, \quad
	i\in\hN^+. \]

If $C_i$ (in the objective) and $\hS_i$ [in \eqref{BIM rank}] are convex, then BIM-OPF is convex except for \eqref{BIM rank},
and an SDP relaxation can be obtained by removing \eqref{BIM rank} from BIM-OPF.
    	\begin{align*}
    	\textbf{BIM-SDP: }\min~~ & \sum_{i\in \hN} C_i(\vct{s}_i) \\%\label{SDP}\\
	\mathrm{over}~~ & \vct{s}, v, W \nonumber\\
	\mathrm{s.t.}~~ & \eqref{BIM s}-\eqref{BIM relax}.  \nonumber
	\end{align*}
Note that BIM-SDP may be nonconvex due to $C_i$ and $\hS_i$.

If an optimal BIM-SDP solution $(\vct{s},v,W)$ satisfies \eqref{BIM rank}, then $(\vct{s},v,W)$ also solves BIM-OPF. Furthermore, a global optimum $(\vct{s},\vct{V})$ of OPF can be recovered via Algorithm \ref{algorithm: recover V}.

\begin{theorem}
\label{thm: BIM recover}
Given an optimal solution $(\vct{s}, v,W)$ of BIM-SDP that satisfies \eqref{BIM rank}, Algorithm 1 computes a $V$ such that $(s, V)$ solves OPF.
\end{theorem}

Theorem \ref{thm: BIM recover} follows directly from Lemma \ref{lemma: V <=> W}.
	\begin{definition}
	\label{def: BIM exact}
	BIM-SDP is \emph{exact} if every optimal solution of BIM-SDP satisfies \eqref{BIM rank}.
	\end{definition}

If BIM-SDP is exact, then a global optimum of OPF can be obtained by solving BIM-SDP according to Theorem \ref{thm: BIM recover}.

\subsection{Comparison with a Standard SDP}
A standard SDP relaxation of OPF has been proposed in the literature \cite{dall2012distributed}. It is derived by introducing
	\[ \tilde{W} = \begin{bmatrix}
	\vct{V}_0 \\ \vdots \\ \vct{V}_n
	\end{bmatrix}
	\begin{bmatrix}
	\vct{V}_1^H & \cdots & \vct{V}_n^H
	\end{bmatrix} \]
to shift the nonconvexity from \eqref{BIM} in BIM-OPF to
	$\rank \tilde{W} = 1,$
and removing the rank constraint. We call this relaxation standard-SDP for ease of reference.

BIM-SDP is computationally more efficient than standard-SDP since it has fewer variables. It is straightforward to verify that there are $O(n)$ variables in BIM-SDP and $O(n^2)$ variables in standard-SDP.

Standard-SDP does not exploit the radial network topology. In $\tilde{W}$,  only blocks corresponding to lines $i\sim j$ appear in other constraints than $\tilde{W}\succeq0$, i.e., if bus $i$ and bus $j$ are not connected, then block $(i,j)$ in $\tilde{W}$ only appears in $\tilde{W}\succeq0$. Since the network is radial, $n^2$ out of the $(n+1)^2$ blocks in $\tilde{W}$ only appear in $\tilde{W}\succeq0$, leaving significant potential for exploring sparsity.

Call these $n^2$ blocks that only appear in $\tilde{W}\succeq0$ the $\tilde{W}$-only blocks and the other $2n+1$ blocks the key-blocks. The role of having $\tilde{W}$-only blocks in the optimization is to make sure that the partial matrix specified by key-blocks can be completed to a positive semidefinite full matrix.

There is a standard way of positive semidefinite matrix completion---looking at the \emph{chordal} extension of a partial matrix \cite{fukuda2001exploiting}. Essentially, BIM-SDP applies this technique to exploit the radial network topology.


TITLE: Solving differential equation and obtain expressions for unknowns?
QUESTION [1 upvotes]: I have the following differential equation
$my'' + \beta y' + mg = 0$ , with condition $y(0)=0$.
I need to solve the equation and obtain expressions for the unknowns.
I have attempted to use the try method of substituting in $y=e^{\lambda t}$ but do not know how to proceed beyond that.
The differential equation is meant to represent free-fall of an object with air resistance that is proportional to it's speed.

REPLY [1 votes]: Construct $q(t)=y(t)+\frac{mg}{\beta}t$
By substitution
$$ mq''+\beta q'=0 $$
The solutions of above ODE are
$$ q(t)=c$$
Or
$$ q(t)=c_1e^{-\frac{\beta}{m}t}+c_2$$
$c,c_1,c_2$ are all constants
Therefore, with initial condition $y(0)=0$,the solutions of original ODE are
$$ y(t) =-\frac{mg}{\beta}t$$
Or
$$y(t) = c(e^{-\frac{\beta}{m}t}-1)-\frac{mg}{\beta}t$$


TITLE: Infinite multiplication of the fractions of square roots
QUESTION [1 upvotes]: I would like to show
$$\frac{\sqrt{2}}{2}\cdot\frac{\sqrt{2+\sqrt{2}}}{2}\cdot\frac{\sqrt{2+\sqrt{2+\sqrt{2}}}}{2}\cdots=\frac{2}{\pi}
$$
I have no clue on this. I am very appreciated if someone can help me.

REPLY [4 votes]: Write $\sqrt{2}=2\cos\frac{\pi}{4}$, using the formular $1+\cos 2\theta=2\cos^2
\theta $ and $\sin 2\theta=2\sin\theta\cos \theta$
The left side is exactly the limit of
$$\frac{1}{2^n\sin\frac{\pi}{2^{n+1}}}.$$


TITLE: Optimizing the ratio between two differential equations
QUESTION [2 upvotes]: I have two second-order differential equations describing two systems, both with the same form but different coefficients:
$$ x_v(t) = A_v \frac{d^2u(t)}{dt^2} + B_v \frac{du(t)}{dt} + C_v u(t) - D_v \frac{dx_v(t)}{dt} - \frac{d^2 x_v(t)}{dt^2} $$
$$ x_h(t) = A_h \frac{d^2u(t)}{dt^2} + B_h \frac{du(t)}{dt} + C_h u(t) - D_h \frac{dx_h(t)}{dt} - \frac{d^2 x_h(t)}{dt^2} $$
And I'm trying to select the control function $u(t)$ to maximize one system while minimizing the other; maximize $\int{x_v\ dt}$ (or alternatively the energy integral) while making $x_h$ as close to 0 as possible.
I've tried various optimal control and MPC techniques like iLQR (just makes a step function), pseudospectral optimizers like PSOPT (produces some sensible result with an extremely fine node resolution, but extremely computationally demanding and I can do better by guessing), but I feel like there must be something I'm missing - something about the ratio or the DE that would simplify the problem...
If one system is simply set to a reasonable output and the other to 0, an overdetermined system is obtained, which does not seem super useful.
This problem seems to be similar to a class called "simultaneous stabilization" or "underactuated systems", but the methods don't seem to be particularly applicable.
If anyone has any examples of an equivalent problem or a solution technique, I would be grateful! Thanks!
Ed. per questions:
All coefficients can be assumed to be positive. Both sets of coefficients are similar (whatever that's worth). The time horizon of interest is positive and finite.
The physical context of the problem is called cellular electroporation: this is the paper with transfer functions I'm working off of.

REPLY [1 votes]: As
$$
\cases{
X_v(s) = \frac{A_v s^2+B_v s+ C_v}{s^2+sD_v + 1}U(s) + \frac{\dot x_v(0)+ s x_v(0)}{s^2+sD_v + 1}\\
X_h(s) = \frac{A_h s^2+B_h s+ C_h}{s^2+sD_h + 1}U(s) + \frac{\dot x_h(0)+ s x_h(0)}{s^2+sD_h + 1}
}
$$
we have
$$
\cases{
x_v(t) = \int \Phi_v(\tau)u(t-\tau)d\tau+\mathcal{L}^{-1}\left[\frac{\dot x_v(0)+ s x_v(0)}{s^2+sD_v + 1}\right]\\
x_h(t) = \int \Phi_h(\tau)u(t-\tau)d\tau+\mathcal{L}^{-1}\left[\frac{\dot x_h(0)+ s x_h(0)}{s^2+sD_h + 1}\right]\\
}
$$
Here $\Phi_v(\tau), \Phi_h(\tau), \mathcal{L}^{-1}\left[\frac{\dot x_v(0)+ s x_v(0)}{s^2+sD_v + 1}\right], \mathcal{L}^{-1}\left[\frac{\dot x_h(0)+ s x_h(0)}{s^2+sD_h + 1}\right]$ can be obtained in closed form. The calculations for $\int \Phi_v(\tau)u(t-\tau)d\tau, \int \Phi_h(\tau)u(t-\tau)d\tau$ can also be obtained in closed form with the help of a symbolic processor, after proposing $u(t)$ as a cubic spline over a grid $\{t_0, t_1,\cdots, t_n\}$ of base points, being then $u(t)= u(u_0, u_1,\cdots, u_n,t)$.
Finally we can solve the maximization problem
$$
\max_{u_0,u_1,\cdots,u_n}\int_T (x_v^2(t,u_0,u_1,\cdots,u_n)-\rho^2 x_h^2(t,u_0,u_1,\cdots,u_n)) dt\ \ \text{s. t.}\ \ \|u\| \le u_{max}
$$
Follows a simplified MATHEMATICA script assuming $A_v=3,B_v=1,A_h=0.1,B_h =1,C_v=1,C_h=1,D_v=1,D_h=2, x_v(0) = \dot x_v(0)=x_h(0) = \dot x_h(0)=1$ and $u$ as a linear spline.
ClearAll["Global`*"]
parms = Thread[{Dv, Dh, Av, Ah, Bv, Bh, Cv, Ch, uv0, uh0, duv0,
 duh0} -> {1, 2, 1/2, 3, 1/10, 1, 1, 1, 1, 1, 1, 1}];
tmin = 0;
tmax = 3;
n = 5;
tau0 = 100;
dt = (tmax - tmin)/n;
For[k = 1, k <= n + 1, k++, t0[k] = tmin + dt (k - 1)];
nt = n + 1;
U0 = Table[u0[k], {k, 1, nt}];
ut[u1_, u2_, t1_, t2_, t_] := u1 + (u2 - u1)/(t2 - t1) (t - t1)
uf[t_] := Piecewise[
Table[{ut[u0[k], u0[k + 1], t0[k], t0[k + 1], t], t0[k] <= t < t0[k + 1]}, {k, 1, n}]];
passivationfilter = tau0/(tau0 s + 1);
Phivt[t_] := InverseLaplaceTransform[
  passivationfilter (Av s^2 + Bv s + Cv)/(s^2 + Dv s + 1) /. parms, s, t];
Phiht[t_] := InverseLaplaceTransform[
  passivationfilter (Ah s^2 + Bh s + Ch)/(s^2 + Dh s + 1) /. parms, s, t];

Xvtau = Assuming[Join[{tau, t}, U0] \[Element] Reals,
Integrate[Phivt[tau - t]*uf[t], {t, 0, tau}]] + InverseLaplaceTransform[(s uv0 + duv0)/(s^2 + Dv s + 1) /. parms, s, tau];
Xhtau = Assuming[Join[{tau, t}, U0] \[Element] Reals,
Integrate[Phiht[tau - t]*uf[t], {t, 0, tau}]] + InverseLaplaceTransform[(s uh0 + duh0)/(s^2 + Dh s + 1) /. parms, s, tau];

TXvtau = Table[Abs[Xvtau /. {tau -> tmin + dt/2 (k - 1)}], {k, 1, 2 n + 1}] // ComplexExpand;
TXhtau = Table[Abs[Xhtau /. {tau -> tmin + dt/2 (k - 1)}], {k, 1, 2 n + 1}] // ComplexExpand;

rho = 10;
Umax = 1;
sol = NMaximize[{TXvtau.TXvtau - rho^2 TXhtau.TXhtau, U0.U0 <= Umax}, U0, Method -> "DifferentialEvolution"]

Xvtau0 = Re[Xvtau /. sol[[2]]];
Xhtau0 = Re[Xhtau /. sol[[2]]];
Plot[{Xvtau0, Xhtau0}, {tau, tmin, tmax}, PlotStyle -> {{Blue, Thick}, {Red, Thick}}, PlotRange -> All]
U0t = Table[{tmin + dt (k - 1), u0[k]} /. sol[[2]], {k, 1, nt}];
ListLinePlot[U0t, PlotStyle -> Black, PlotRange -> All]

Follow two plots: in the first in blue $x_v$ and red $x_h$ and for the second, in black $u$.