TITLE: Comparing two condition
QUESTION [1 upvotes]: Let $\rho:(0,\infty)\to (0,\infty)$ be a measurable function.
The condition 1 for the function $\rho$ is: There exist constants $C_1>0$ and $0<2k_1<k_2<\infty$ such that
$$
\sup_{r/2<s\le r}\rho(s)\leq C_1 \int_{k_1 r}^{k_2 r}\frac{\rho(s)}{s}ds,\qquad r>0.
$$
The condition 2 for the function $\rho$ is: There exist constant $C_2>0$ such that
$$
\frac{1}{C_2}\le \frac{\rho(r)}{\rho(s)}\le C_2
$$
whenever $r$ and $s$ satisfy
$$
r,s>0 \text{   and   }\frac{1}{2}\le \frac{r}{s}\le 2.
$$
The claim is "conditon 1 is weaker than condition 2, i.e., condition 2 implies condition 1."
I can not prove this claim. Can anybody help me to prove this claim?

REPLY [1 votes]: Condition 2 implies that
$$\rho(s) \leqslant C_2 \rho(r)$$
for $\frac{r}{2} \leqslant s \leqslant r$, from which
$$\sup_{\frac{r}{2} \leqslant s \leqslant r} \rho(s) \leqslant C_2 \rho(r)$$
follows immediately. On the other hand, choosing $k_2 = 1$ and $0 < k_1 < \frac{1}{2}$ yields
\begin{align}
\int_{k_1r}^{k_2r} \frac{\rho(s)}{s}\,ds
&> \int_{r/2}^r \frac{\rho(s)}{s}\,ds \\
&\geqslant \frac{\rho(r)}{C_2}\int_{r/2}^r \frac{ds}{s} \\
&= \frac{\log 2}{C_2}\rho(r)
\end{align}
using the inequality
$$\rho(s) \geqslant \frac{\rho(r)}{C_2}$$
for $\frac{r}{2} \leqslant s \leqslant r$ implied by condition 2. Putting both pieces together, we have
$$\sup_{\frac{r}{2} \leqslant s \leqslant r} \rho(s) \leqslant C_1 \int_{k_1r}^{k_2r} \frac{\rho(s)}{s}\,ds$$
with
$$C_1 = \frac{C_2^2}{\log 2}$$
and $0 < 2k_1 < k_2 = 1 < \infty$, that is, we have condition 1.


TITLE: Given a plane, find a plane perpendicular to it, containing a given line
QUESTION [1 upvotes]: Ok so this is basically for my upcoming test. The essence of question is that I have a plane $$E_1: \; 18x-y-10z=1$$ and a line $$g(x)=(1,-3,-2)+x(1,-2,0)$$
What I need to do next is find a plane $E_2$ which is perpendicular to $E_1$ and containing the line described by $g(x)$
Since this is a part of a bigger problem the plane $E_1$ already contains the line $g(x)$
I have tried to do following. Since the line is given I can find any two points which it contains. So I choose $x=0$ and $x=1$ and plug them into function to obtain two points contained by the line. These points are:
$$P_0(1,-3,-2)$$
$$P_1(2,-5,-2)$$
Now since I have two points,I can find a vector between them $$P_0P_1 (1,-2,0)$$
Also I can determine the normal vector of plane $E_1$ which will be denoted $n_1$ and is equal to $$n_1=(18,-1,-10)$$
Now let $n_2$ be the perpendicular vector of plane $E_2$.Since these two planes are perpendicular to each other,then their normal vectors must be perpendicular to each other, and dot product of the normal vectors of two planes must be zero. When I take scalar product I get the first equation on my way:
$$18x-y-10z=0$$
Next equation I obtain is by taking in consideration that $n_2$ is normal to plane $E_2$ thus normal to contained vector $P_0P_1$ which gives the second equation:
$$x-2y=0$$
From here on I am so to say, stuck. I cant obtain a second equation, nor can I find a third non-collinear point to finish the system. How do I determine the plane?

REPLY [2 votes]: You have two vectors parallel to $E_2$: $v=(1,-2,0)$ and $n_1=(18,-1,-10)$, so you can write immediately the parametric equations for $E_2$:
$$
(x,y,z)=P_0+sv+tn_1=(1+s+18t,-3-2s-t,2-10t).
$$
The cartesian equation can be readily found from these: express $t$ and $s$ using the equations for $z$ and $y$, then substitute into the equation for $x$.


TITLE: How to show that $\pi_1(\mathbb{RP}^2) = \mathbb{Z}_2$?
QUESTION [1 upvotes]: How to show that $\pi_1(\mathbb{RP}^2) = \mathbb{Z}_2$?
In general is well known that $\pi_1(\mathbb{RP}^n) = \mathbb{Z}_2, ~ n \ge 2.$
But how to show this assertion?
I have a few knowledge about covering spaces...

REPLY [1 votes]: For a "sufficiently nice" action of a group $G$ on a simply-connected, based space $X$, we can lift a loop $\gamma:[0, 1] \to G/X$ to a loop $\tilde \gamma$ in $G$. The map $\gamma \to \tilde \gamma(1)$ then induces a well-defined isomorphism $\pi_1(G/X) \to G$. In this particular case, "sufficiently nice" means "free and properly discontinuous," but you should really study covering spaces before computing $\pi_1(\mathbb{RP^2}) = \pi_1(S^2/\{\pm 1\})$; the proof of the statement above involves some technical lifting properties that are only a small step away from covering spaces anyway.


text:
\section{Precedence Proper Thinness for a Given Partition}\label{chpt:ppthinness}

In this section, we discuss precedence proper thinness for a given partition. First, we prove that this problem is \NP-complete for an arbitrary number of parts. Then, we propose a polynomial time algorithm for a fixed number of parts based on the one presented in Section~\ref{chpt:pthinness}.
Formally, we will prove that the following problem is \NP-complete.

\begin{flushleft}
\begin{tabular}{ l l }
 \hline
 \textbf{\textsc{Problem}:} & \textsc{Partitioned \fpp{k}} (Recognition of \fpp{k}  graphs for a given\\ & partition)\\
 \textbf{\textsc{Input}:} & A natural $k$, a graph $G$ and a partition $(V_1,\ldots,V_k)$ of $V(G)$.\\
 \textbf{\textsc{Question}:} & Is there a strongly consistent ordering $s$ of $V(G)$ such that  the\\& vertices of $V_i$ are consecutive in  $s$, for all $1 \leq i \leq k$?\\
 \hline
\end{tabular}
\end{flushleft}

The \NP-hardness of the previous problem is accomplished by a reduction from the problem  \textsc{Not all equal 3-SAT}, which is \NP-complete~\cite{Schaefer1978b}. The details are described in Theorem~\ref{theo:npc:ppthinness}.

\begin{flushleft}
    \begin{tabular}{ l l }
        \hline
        \textbf{\textsc{Problem}:} & \textsc{Not all equal 3-SAT}\\
        \textbf{\textsc{Input}:} & A formula $\varphi$ on variables $x_1,\dots, x_r$ in conjunctive normal form,\\&  with clauses  $\mC_1, \dots, \mC_s$, where each clause has exactly three lite-\\&rals.\\
        \textbf{\textsc{Question}:} & Is there a truth assignment for $x_1,\dots, x_r$ such that each clause \\&$\mC_i$,  $i = 1, \dots, s$, has at least one true literal and at least one fal-\\&se literal?
        \\
        \hline
    \end{tabular}
\end{flushleft}

\begin{theorem}\label{theo:npc:ppthinness}
Recognition of \fpp{k} graphs for a given partition is
\NP-complete, even if the size of
each part is at most 2.
\end{theorem}

\begin{proof}
A given precedence strongly consistent ordering for the partition of $V(G)$ can be easily verified in polynomial time. Therefore, this problem is in \NP.

Given an instance $\varphi$ of \textsc{Not all equal 3-SAT}, we
define a graph $G$ and a partition of $V(G)$ in which each part has size at most two. The graph $G$ is defined in such a way that $\varphi$ is satisfiable if, and only if, there is a precedence strongly consistent ordering of  $V(G)$ for the partition. The graph $G$ is constructed as follows.

For each variable $x_i$ appearing in the clause $\mC_j$, create
the  part $$X_{ij} = \{x_{ij}^T,x_{ij}^F\}$$

For each variable $x_i$, create the  parts $$X_{i}^T =
\{x_{i}^T\} \mbox{ and } X_{i}^F = \{x_{i}^F\}$$

The edges of the graph between these parts are $(x_i^T, x_{ij}^T)$
and $(x_i^F, x_{ij}^F)$ for every $i,j$ such that variable $x_i$
appears in clause $\mC_j$.

Notice that in any strongly consistent ordering, part $X_{ij}$ must be between parts $X_i^F$ and $X_i^T$. Moreover, if $x_i^F < x_i^T$,
then $x_{ij}^F < x_{ij}^T$, and conversely. In particular, in any valid vertex order, for each $i \in \{1, \dots, r\}$, either
$x_{ij}^F < x_{ij}^T$ for every $j \in \{1, \dots, s\}$ or
$x_{ij}^T < x_{ij}^F$ for every $j \in \{1, \dots, s\}$.

The \textsc{Partitioned \fpp{k}} instance will be such that if there is a precedence strongly consistent ordering for the vertices with respect to the given parts, then the assignment $x_i = (x_i^F < x_i^T)$ (that is, $x_i$ is true if $x_i^F$ precedes $x_i^T$ in such an ordering and $x_i$ is false otherwise) satisfies $\varphi$ in the context of \textsc{Not all equal 3-SAT} and, conversely, if there is a truth assignment satisfying $\varphi$ in that context, then there exists a strongly consistent ordering for the \textsc{Partitioned \fpp{k}} instance in which $x_i^F < x_i^T$ if $x_i$ is true and $x_i^T < x_i^F$ otherwise.

In what follows, if the $k$-th literal $\ell_{ij}$ of $\mC_j$ is the
variable $x_i$ (resp. $\neg x_i$), we denote by $O_{ij}$ the
ordered part $\{x_{ij}^F,x_{ij}^T\}$ (resp.
$\{x_{ij}^T,x_{ij}^F\}$).

Given a 2-vertex ordered part $C$, we denote by $C^1$ and $C^2$
the first and second elements of $C$. By $\pm C$, we denote
``either $C$ or $\bar C$''.

For each clause $\mC_j = \ell_{1j} \vee \ell_{2j} \vee \ell_{3j}$, we add
the 2-vertex ordered parts $Y_{1j}$, $Y_{2j}$, and $Y_{3j}$, and
the edges $(O_{1j}^2,Y_{1j}^1)$, $(O_{1j}^1,Y_{2j}^1)$,
$(O_{1j}^2,Y_{2j}^1)$, $(O_{2j}^1,Y_{1j}^2)$,
$(O_{2j}^1,Y_{1j}^1)$, $(O_{2j}^2,Y_{2j}^1)$,
$(O_{2j}^2,Y_{2j}^2)$, $(O_{2j}^1,Y_{3j}^1)$,
$(O_{2j}^1,Y_{3j}^2)$, $(O_{3j}^1,Y_{1j}^2)$,
$(O_{3j}^2,Y_{1j}^2)$, $(O_{3j}^1,Y_{2j}^2)$,
$(O_{3j}^2,Y_{2j}^2)$, $(O_{3j}^2,Y_{3j}^1)$,
$(O_{3j}^2,Y_{3j}^2)$. These edges ensure the following properties
in every strongly consistent ordering of the graph with respect to the defined partition.

\begin{enumerate}

\item\label{it:1} Since $(O_{1j}^2,Y_{1j}^1)$ is the only edge
between $O_{1j}$ and $Y_{1j}$, their only possible relative
positions are  $O_{1j}<Y_{1j}$ and its reverse $\bar Y_{1j}<\bar O_{1j}$.

\item\label{it:2} Since $(O_{1j}^1,Y_{2j}^1)$ and
$(O_{1j}^2,Y_{2j}^1)$ are the edges between $O_{1j}$ and $Y_{2j}$,
their possible relative positions are $\pm O_{1j}<Y_{2j}$ and
$\bar Y_{2j}<\pm O_{1j}$.

\item\label{it:3} Since $(O_{2j}^1,Y_{1j}^1)$ and
$(O_{2j}^1,Y_{1j}^2)$ are the edges between $O_{2j}$ and $Y_{1j}$,
their possible relative positions are $\bar O_{2j}<\pm Y_{1j}$
and $\pm Y_{1j}<O_{2j}$.

\item\label{it:4} Since $(O_{2j}^2,Y_{2j}^1)$ and
$(O_{2j}^2,Y_{2j}^2)$ are the edges between $O_{2j}$ and $Y_{2j}$,
their possible relative positions are $O_{2j}<\pm Y_{2j}$ and
$\pm Y_{2j}<\bar O_{2j}$.

\item\label{it:5} Since $(O_{2j}^1,Y_{3j}^1)$ and
$(O_{2j}^1,Y_{3j}^2)$ are the edges between $O_{2j}$ and $Y_{3j}$,
their possible relative positions are $\bar O_{2j}<\pm Y_{3j}$
and $\pm Y_{3j}<O_{2j}$.

\item\label{it:6} Since $(O_{3j}^1,Y_{1j}^2)$ and
$(O_{3j}^2,Y_{1j}^2)$ are the edges between $O_{3j}$ and $Y_{1j}$,
their possible relative positions are $\pm O_{3j}<\bar Y_{1j}$
and $Y_{1j}<\pm O_{3j}$.

\item\label{it:7} Since $(O_{3j}^1,Y_{2j}^2)$ and
$(O_{3j}^2,Y_{2j}^2)$ are the edges between $O_{3j}$ and $Y_{2j}$,
their possible relative positions are $\pm O_{3j}<\bar Y_{2j}$
and $Y_{2j}<\pm O_{3j}$.

\item\label{it:8} Since $(O_{3j}^2,Y_{3j}^1)$ and
$(O_{3j}^2,Y_{3j}^2)$ are the edges between $O_{3j}$ and $Y_{3j}$,
their possible relative positions are $O_{3j}<\pm Y_{3j}$ and
$\pm Y_{3j}<\bar O_{3j}$.
\end{enumerate}

Notice that, by items \ref{it:1} and \ref{it:6} (resp. \ref{it:2}
and \ref{it:7}), the vertices of $Y_{1j}$  (resp. $Y_{2j}$) are
forced to lie between those of $O_{1j}$ and those of $O_{3j}$. More
precisely, the possible valid orders are $O_{1j}<Y_{1j},Y_{2j}<\pm O_{3j}$ and their reverses $\pm
O_{3j}<\bar Y_{2j} , \bar Y_{1j}<\bar O_{1j}$.

By items \ref{it:3} and \ref{it:4}, the vertices of $O_{2j}$ are
forced to be between those of $Y_{1j}$ and those of $Y_{2j}$. More
precisely, the possible valid orders are $\pm Y_{1j}<O_{2j}<\pm Y_{2j}$ and their reverses $\pm Y_{2j}<\bar O_{2j}<\pm
Y_{1j}$.

By items \ref{it:3} and \ref{it:5}, the vertices of $Y_{1j}$ and
$Y_{3j}$ are forced to be on the same side with respect to the
vertices of $O_{2j}$, either $\bar O_{2j}<\pm Y_{1j},\pm Y_{3j}$ or $\pm Y_{1j}, \pm Y_{3j}<O_{2j}$.

Hence, taking also into account item \ref{it:8}, the possible
valid orders are
\begin{itemize}
\item $O_{1j}<Y_{1j}, \pm Y_{3j} < O_{2j}<Y_{2j}<\bar O_{3j}$

\item $O_{1j}<Y_{2j}<\bar O_{2j}<Y_{1j} , \pm
Y_{3j}<\bar O_{3j}$

\item $O_{1j}<Y_{2j}<\bar O_{2j}<Y_{1j}<O_{3j}<\pm
Y_{3j}$
\end{itemize}
and their reverses,

\begin{itemize}
\item $O_{3j}<\bar Y_{2j}<\bar O_{2j}<\bar Y_{1j}
, \pm Y_{3j}<\bar O_{1j}$

\item $O_{3j}<\bar Y_{1j} , \pm Y_{3j}<O_{2j}<\bar Y_{2j}<\bar O_{1j}$

\item $\pm Y_{3j}<\bar O_{3j}<\bar Y_{1j}<O_{2j}<\bar
Y_{2j}<\bar O_{1j}$
\end{itemize}
and will correspond to truth assignments that make true, respectively,

\begin{enumerate}[a)]
\item $\ell_{1j} \wedge \ell_{j2} \wedge \neg \ell_{3j}$

\item $\ell_{1j} \wedge \neg \ell_{2j} \wedge \neg \ell_{3j}$

\item $\ell_{1j} \wedge \neg \ell_{2j} \wedge \ell_{3j}$

\item $\neg \ell_{1j} \wedge \neg \ell_{2j} \wedge \ell_{3j}$

\item $\neg \ell_{1j} \wedge \ell_{2j} \wedge \ell_{3j}$

\item $\neg \ell_{1j} \wedge \ell_{2j} \wedge \neg \ell_{3j}$

\end{enumerate}

Suppose first that there is a precedence strongly consistent ordering of $V(G)$ with respect to its vertex partition. Define a truth assignment for variables $x_1, \dots, x_r$ as $x_i = (x_i^F < x_i^T)$, for $i \in \{1, \dots, r\}$.

As observed above, if the value of $x_i$ is true (resp. false), then
for every $j \in \{1, \dots, s\}$, the part $X_{ij}$ is ordered
$x_{ij}^F$ $x_{ij}^T$ (resp. $x_{ij}^T$ $x_{ij}^F$). So, for each
clause ${\mathcal C}_j$, the part corresponding to its $k$-th
literal will be ordered as $O_{kj}$ if the literal is assigned true
and as $\bar O_{kj}$ if the literal is assigned false. Since for
each valid order of the vertices there exist $k, k' \in \{1,2,3\}$
such that the part corresponding to the $k$-th literal is ordered
$O_{kj}$ and the part corresponding to the $k'$-th literal is
ordered $\bar O_{k'j}$, the truth assignment satisfies the instance
$\varphi$ of \textsc{Not all equal 3-SAT}.

Suppose now that there is a truth assignment for variables $x_1,
\dots, x_r$ that satisfies the instance $\varphi$ of \textsc{Not
all equal 3-SAT}. Define the order of the vertices in the
following way. The first $r$ vertices are $\{x_i^F : x_i \mbox{ is
true}\} \cup \{x_i^T : x_i \mbox{ is false}\}$, and the last $r$
vertices are $\{x_i^T : x_i \mbox{ is true}\} \cup \{x_i^F : x_i
\mbox{ is false}\}$.
Between these first and last $r$ vertices,
place all the parts $X_{ij}$, $Y_{1j}$,$Y_{2j}$ and $Y_{3j}$ associated with each clause $\mathcal{C}_j$,
$j=1,\dots,s$.

In particular, the parts $X_{ij}$, $Y_{1j}$, $Y_{2j}$ and $Y_{3j}$ are ordered accordingly to which of the conditions
(a)--(f) is satisfied.
By the analysis above, this is a precedence strongly consistent ordering of the vertices of $G$, with respect to the defined parts.
As an example, Figure~\ref{fig:ppthinnes:npc:instance} depicts the instance of the \textsc{Partitioned \fpp{k}} problem built from the instance $\varphi = \{(x_1\wedge x_2 \wedge x_3)\}$ of \textsc{Not all equal 3-SAT} problem.
\end{proof}

\begin{figure}[htbp]
\centering
\includegraphics[width=80mm]{figures/ppthinness/qualiNPcInstance.pdf}
\caption{ Instance of the \textsc{Partitioned \fpp{k}} problem built from the instance $\varphi = \{(x_1\wedge x_2 \wedge x_3)\}$ of \textsc{Not all equal 3-SAT} problem.}
\label{fig:ppthinnes:npc:instance}
\end{figure}

The remaining of this section is dedicated to discuss a polynomial time solution to a variation of the \textsc{Partitioned \fpp{k}} problem. This variation consists in considering a fixed number of parts for $V(G)$, that is, $k$ is removed from the input and  taken as a constant for the problem. The strategy that will be adopted is the same used for \textsc{Partitioned \fp{k}} problem. It is not difficult to see that Property~\ref{prop:thinness} is not sufficient to describe the requirements that must be imposed in the ordering of vertices in a precedence strongly consistent ordering.  This is so because, unlike what occurs in a precedence consistent ordering, in a precedence strongly consistent ordering the vertices of each part $V_i$ may impose an ordering to vertices that belong to parts that precede and succeed $V_i$. Given this fact, we observe the following property to describe such relation.

\begin{property}\label{prop:pthinness}
Let  $(V_1,V_2, \ldots, V_k)$ be a partition of $V(G)$, $s$ a precedence strongly consistent ordering and  $1 \leq i , j \leq k$. If $V_i$ precedes $V_j$ in $s$, then for all  $u,v \in V_i$ and $w \in V_j$, if $(u,w) \not\in E(G)$ and $(v,w) \in E(G)$, then  $u$ precedes $v$ in $s$. Moreover, for all  $u \in V_i$ and $w,x \in V_j$, if $(u,w) \not\in E(G)$ and $(u,x) \in E(G)$, then  $x$ precedes $w$ in $s$
\end{property}

\begin{figure}[htbp]
\centering
\includegraphics[width=80mm]{figures/ppthinness/qualiPropPThin.pdf}
\caption{Precedence relations among the vertices in a precedence strongly consistent ordering.}
\label{fig:propthinness}
\end{figure}

Notice that the greedy strategy used in Section~\ref{chpt:pthinness} does not work in the problem being considered. This is so because, according to Property~\ref{prop:pthinness} and visually depicted in Figure~\ref{fig:propthinness}, the ordering of vertices of $V_i$ in a precedence strongly consistent ordering $s$ is influenced by both the parts that precede and succeed $V_i$ in $s$. Despite this, the  method described in the Section~\ref{chpt:pthinness} to validate whether a part can precede a set of parts  is also useful to present a solution to this problem.

Let $G$ be a graph, $\mathcal{V} =(V_1,V_2, \ldots, V_k)$ a partition of $V(G)$ and $s$ a precedence strongly consistent ordering of $V(G)$ for the given partition.
Clearly, for all $1 \leq 1 \leq k$,  $G[V_i]$ must be a proper interval graph for $s$ to be a precedence strongly consistent ordering. Verifying whether $G[V_i]$ is a proper interval graph can be accomplished in linear time. If one of the parts does not induce a proper interval graph, then the answer is \textsc{NO}. Otherwise, each part has a $PQ$ tree associated to it.

For a  given sequence $s_\mathcal{V}$ of parts of $\mathcal{V}$, suppose that $V_j<V_i<V_z$ in $s_\mathcal{V}$,  for $1 \leq j,i,z \leq k$. Let $T_i$ be a $PQ$ tree of $G[V_i]$.
Notice that, considering the Property~\ref{prop:pthinness},  if we apply Theorem~\ref{theo:thinness} to get the ordering constraints imposed by $V_j$ and $V_z$ to $T_i$, and add the directed edges  to $T_i$ in the same way that has been done in Section~\ref{chpt:pthinness} and $T_i$ can meet the constraints, then $T_i$ is compatible to being at that position. That is, the vertices of $V_i$ can precede the vertices of $V_z$ and succeed the vertices of $V_j$ in any precedence strongly consistent ordering. We show that for any $s_\mathcal{V}$, it is possible to verify whether there is a precedence strongly consistent ordering $s$ in which the ordering of the parts in $s$ is precisely $s_\mathcal{V}$.

To solve the problem, we will test all $k!$ possible permutations $s_\mathcal{V}= V'_1,V'_2,\ldots\allowbreak , V'_k$ among the parts of $\mathcal{V}$ and validate, using a digraph and $PQ$ trees, if each part $V'_i$ can precede  $V'_z$ and succeed $V'_j$, for all $1\leq j <i< z \leq k$. This validation is done exactly as described in Section~\ref{chpt:pthinness}, except for using Property~\ref{prop:pthinness} instead of Property~\ref{prop:thinness}. If there is some $s$ that satisfies this condition, then there is a precedence strongly consistent ordering with respect to $s$ and $G$ is a \fpp{k} graph concerning $\mathcal{V}$. Otherwise, $G$ is not a \fpp{k} graph with respect to $\mathcal{V}$.  Algorithm~\ref{alg:kfpp} formalizes the procedure.

\begin{algorithm}[htbp]
\textbf{Input}: $G$: a graph;
        $\mathcal{V}$: a $k$-partition $(V_1, V_2, \ldots, V_k)$ of $V(G)$ for some fixed $k$  \\
\vspace{0.20cm}
\KpptF{

    \For{\Each  $V_i \in \mathcal{V}$ }{
         \If{\textsf{\upshape $G[V_i]$ is not a proper interval graph}}{
            \Return (\textsc{NO}, $\emptyset$)
         }
    }

    \For{\Each \textsf{\upshape  permutation $s_\mathcal{V}$ of  $\mathcal{V}$ }}{
        $s \leftarrow \emptyset$\\
        $foundValidPermutation \leftarrow$ \TRUE\\
        \For{\Each $V_i \in s_\mathcal{V}$}{
            Create a digraph $D = (V_i, \emptyset)$\\
            Build a $PQ$ tree $T_i$ of $G[V_i]$\\
            \For{\Each \textsf{\upshape $V_j \in s_\mathcal{V}$ such that $V_j \neq V_i$}}{
                Let $S$ be the set of precedence relations among the vertices of $V_i$ concerning $V_j$ (Property~\ref{prop:pthinness})\\
                \For{\Each $(u<v) \in S$}{
                   $E(D) \leftarrow  E(D) \cup \{(u,v)\}$ \\
                    \For{\textsf{\upshape \Each node $X$ of $T_i$}}{
                        Add the direct edges, deriving from $(u<v)$, among the children of $X$ (Theorem~\ref{theo:thinness})  \\
                    }
                }
                \For{\textsf{\upshape \Each node $X$ of $T_i$}}{
                    Let $D = (V', E')$ be the digraph where $V'$ is the set of the children of $X$ and  $E'$ are the directed edges added among them\\
                     \If{\textsf{\upshape there is a topological ordering $s$ of $D$}}{
                         Arrange the children of $X$ according to $s$ \\
                    }
                    \Else{
                        $foundValidPermutation \leftarrow$ \FALSE \\
                    }
                }
            }
            \If{ foundValidPermutation}{
                \AddEdgesFromPQTree{$G[V_i]$, $D$, $T_i$}\\
                \If{\textsf{\upshape there is a topological ordering $s_i$ of $D$}}{
                    $s \leftarrow ss_i$\\
                }
                \Else{$foundValidPermutation \leftarrow$ \FALSE \\
                \Break}
            }
        }
        \If{ foundValidPermutation}{
            \Return (\textsc{YES}, $s$)
         }
    }
    \Return (\textsc{NO}, $\emptyset$)
}
\caption{\textsc{Partitioned \fpp{k}}}
\label{alg:kfpp}
\end{algorithm}

Concerning the time complexity of the algorithm, first note that to create in $T_i$ the directed edges derived from Property~\ref{prop:pthinness} related to $V'_j$ (resp. $V'_z$) can be done in $O(n^5)$ time. Also, for each $V_i$ we apply this property considering all the other parts, that is, $O(k)$ times, and therefore $O(k^2)$ times overall considering each $V_i$. As this operation must be executed for all $k!$ possible permutations, and considering the analysis of this same method in Section~\ref{chpt:pthinness}, the given strategy yields a worst case time complexity of $O(k!k^2n^5) = O(n^5)$ as $k$ is fixed.

We end this section by mentioning an even more restricted case of the problem. Namely, the recognition of \fpp{k} graphs for a fixed number of parts such that each part induces a connected graph. Note that, as each part induces a connected graph, the proper interval graph induced by each part has an unique proper canonical ordering but reversion or mutual true twins permutation. This fact implies that the $PQ$ tree related to each one of these proper interval graphs is formed by one node of type $Q$, which is the root, that has all the maximal cliques as its children. That is, there are only two possible configurations for each one of these $PQ$ trees. As the number of possible configurations is a constant, this property leads to a more efficient algorithm. Instead of using Theorem~\ref{theo:thinness} to map restrictions to the $PQ$ tree in order to obtain a compatible tree, the algorithm can check both configurations of the $PQ$ tree independently. As the step which uses Theorem~\ref{theo:thinness} is no longer required, this approach leads to an  algorithm that yields a worst case time complexity of $O(k!k^22^kn^3)=O(n^3)$. This strategy is presented in Algorithm~\ref{alg:kfppc}.

\begin{algorithm}[htbp]

\textbf{Input}: $G$: a graph;
        $\mathcal{V}$: a $k$-partition $(V_1, V_2, \ldots, V_k)$ of $V(G)$, for some fixed $k$, such that $G[V_i]$ is connected for all $1 \leq i \leq k$  \\
\vspace{0.20cm}
\KpptFC{

    \For{\Each  $V_i \in \mathcal{V}$ }{
         \If{\textsf{\upshape $G[V_i]$ is not a proper interval graph}}{
            \Return (\textsc{NO}, $\emptyset$)
         }
    }

    \For{\Each  \textsf{\upshape permutation $s_\mathcal{V}$ of  $\mathcal{V}$ }}{
        $s \leftarrow \emptyset$\\
        $foundValidPermutation \leftarrow$ \TRUE\\
        \For{\Each $V_i \in s_\mathcal{V}$}{
            $foundValidTree \leftarrow$ \FALSE\\
            Build a $PQ$ tree $T_i$ of $G[V_i]$\\
            Let $T_i'$ be the $PQ$ tree obtained from $T_i$ by reversing the order of the children of the root\\
            \For{\Each $T \in \{T_i,T_i'\}$}{
                Create a digraph $D = (V_i, \emptyset)$\\
                \For{\Each $V_j \in s_\mathcal{V}$ such that $V_j \neq V_i$}{
                    Let $S$ be the set of precedence relations among the vertices of $V_i$ concerning $V_j$ (Property~\ref{prop:pthinness})\\
                    \For{\Each $(u<v) \in S$}{
                       $E(D) \leftarrow  E(D) \cup \{(u,v)\}$ \\
                    }
                }
                \AddEdgesFromPQTree{$G[V_i]$, $D$, $T$}\\
                \If{\textsf{\upshape there is a topological ordering $s_i$ of $D$}}{
                    $s \leftarrow ss_i$\\
                    $foundValidTree \leftarrow$ \TRUE\\
                    \Break
                }
            }
            \If{\Not foundValidTree}{
                $foundValidPermutation \leftarrow$ \FALSE\\
                \Break
            }

        }
        \If{ foundValidPermutation}{
            \Return (\textsc{YES}, $s$)
         }
    }
    \Return (\textsc{NO}, $\emptyset$)
}
\caption{\textsc{Partitioned \fpp{k}}}
\label{alg:kfppc}
\end{algorithm}

config: arxiv


TITLE: Show that there exists a regular function that is not a quotient of polynomials
QUESTION [2 upvotes]: Let $k$ be an algebraically closed field. Consider the Zariski-closed subset $Y=Z(xw-yz)\subset k^n$. On $U=Y\setminus Z(y,w)$ we consider the function
$$
f\colon U\to k, P=(a,b,c,d)\mapsto
\begin{cases}
a/b &\text{if $P\in U\setminus Z(y)$,}\\
c/d & \text{if $P\in U\setminus Z(w).$}
\end{cases}
$$
My lectures notes claim that this is an example of a function that cannot be written as $f=g/h$ for $f,g\in k[x,y,z,w]$. I haven't been able to actually prove this. What I checked was that $xw-yz$ is an irreducible polynomial, and hence $Z(xw-yz)$ is irreducible. This would mean that if there were $g,h\in k[x,y,z,w]$, then $x/y=f/g$ on $U\setminus Z(y)$, and hence $xg=yf$ (since $U$ is also irreducible). Likewise $z/w=f/g$ yields $zg=wf$ on $U$. I can't find a contraction using this, which I need. Could someone help me out?
This question has been asked before (e.g. here: An example of a regular function over an open set), but the accepted answer talks about Cartier divisors, which I haven't seen before, so I'm actually hoping there is a more elementary argument.

REPLY [1 votes]: You can't find a contradiction from what you wrote because there isn't one.
In the function field $k[Y] = \mathrm{Frac}(A)$ where $A = k[x,y,z,w]/(xw-yz)$ we do indeed have $\frac{f}{g} = \frac{x}{y} = \frac{z}{w}$ exactly because $xw - yz = 0$ and in the function field every nonzero element becomes invertible.
However, you are not asking about rational functions (the functions that live in the function field) but about regular functions meaning that you must have $\frac{f}{g} = \frac{x}{y} = \frac{z}{w}$ in the function field and additionally $g$ vanish nowhere on $U$ so that this fraction produces a well-defined regular function.
Let's see why we must have $g$ vanish somewhere on $U$. We are going to turn this into a pure algebra question. If $g$ did not vanish on $U$ then $Z(g) \subset Z(y,w)$ since $Z(y,w)$ is the complement of $U$. Therefore, $I = (y,w) \subset \sqrt{(g)}$ because these are radical ideals. By Krull's prinicpal ideal theorem $\sqrt{(g)}$ has height $1$ and $I$ is a nonzero prime ideal inside $\sqrt{(g)}$ so $I = \sqrt{(g)}$. Thus $g \in I$ and $I^n = (g)$ for some power $n$.
Let $\mathfrak{m} = (x,y,z,w)$ be the maximal ideal corresponding to the cone point. Now compute that $\dim_{\kappa} I^n_{\mathfrak{m}} / \mathfrak{m} I^n_{\mathfrak{m}} \ge 2$ (think about if $y^n - w^n$ can be in $\mathfrak{m} I^n_{\mathfrak{m}}$) for all $n$ to show that it is impossible for $I^n$ to be principal.


TITLE: Prove f is holomorphic using morera's theorem
QUESTION [0 upvotes]: What kind of subdivisions must I use on an arbitrary triangle in D

I dont understand how the base is extended to coincide with L using continuity in the top 2 diagrams.

REPLY [0 votes]: Say $T$ is a triangle in $D$. If $D\cap L=\emptyset$ then $$\int_{\partial T}f=0.$$
If $T\cap L\ne\emptyset$ you can use $L$ to divide $T$ into two polygons $P_1$ and $P_2$, in such a way that $$\int_{\partial T}f=\int_{P_1}f+\int_{P_2}f=0+0=0.$$


TITLE: Limit of quotients by $p^n$-th powers in $p$-adic fields
QUESTION [2 upvotes]: Let $K/\mathbb{Q}_p$ be a finite extension with normalized valuation $v_K$, let $\mathcal O_K$ be its ring of integers, and let $\mathfrak m_K$ be the maximal ideal of $\mathcal O_K$. Denote $U^N=1+\mathfrak m^N$. I want to prove that the natural map $$U^1\to\varprojlim U^1/(U^1)^{p^n}$$ is an isomorphism.
The map is injective if I show that for each $N$ there exists $n$ such that $(U^1)^{p^n}\subset U^N$. I fix some $N$. The valuations of the non trivial terms of $(1+m)^{p^n}$ are $v_K(p)\cdot n-v_K(k)+k\cdot v_K(m)$ with $1\leq k\leq p^{n}$. The smallest of these valuations is when $k=p^d$ and $v_K(m)=1$, so I assume that. I need to find $n$ such that $v_K(p)\cdot n-v_K(p)\cdot d+p^d\geq N$ for all $1\leq d\leq n$. The minimum of the function $d\mapsto -v_K(p)\cdot d+p^d$ is independent of $n$, so an $n$ large enough will satisfy the needed condition.
For surjectivity, I observe that the image is dense and that the profinite group $U^1$ is compact.
Can someone please verify that the above is correct?

REPLY [2 votes]: I think this looks correct.
Another way to proceed could be to show the following:
Lemma: if $x\in\mathcal{O}_K$ is such that $x-1\in\mathfrak{m}$, then
$$x^{p^n}-1\in\mathfrak{m}^{n+1}$$
for all $n\ge 1$.
You can proceed by induction on $n$, after noticing that $p\in\mathfrak{m}$.
This shows that $(U^1)^{p^n}\subset U^{n+1}$ and $\cap_{n\ge 1}(U^1)^{p^n}=\{1\}$.
Edit: this lemma can be found as "Lemma 1" one Serre's "Corps locaux" (French version, page 35)
For the surjectivity, I think one can also proceed directly: let $(x_n)_n$ be an element of $\varprojlim_{n\ge 1}U^1/(U^1)^{p^n}$. We can find a family $(\tilde{x}_n)_n$ of elements of $U^1$ such that $\tilde{x}_n\mod (U^1)^{p^n}=x_n$. This means that
$\tilde{x}_{n+1}\equiv \tilde{x}_n\mod (U^1)^{p^n},$ i.e. $\tilde{x}_{n+1}\tilde{x}_n^{-1}\in (U^1)^{p^n}\subset U^{n+1}$,
i.e. $\tilde{x}_{n+1}-\tilde{x}_n\in\mathfrak{m}^{n+1}$,
which shows that the sequence $(\tilde{x}_n)$ converges to some $\tilde{x}\in\mathcal{O}_K$.
As $v_K(\tilde{x}_{n}-1)\ge 1$ for all $n$, we get $v_K(\tilde{x}-1)\ge 1$,
i.e. $\tilde{x}\in U^1$.
As we had $\tilde{x}_{n+1}\tilde{x}_n\in(U^1)^{p^n}$ for each $n$, we have
$\tilde{x}_k\tilde{x}_n^{-1}\in (U^1)^{p^n}$ for all $k\ge n$,
then $\tilde{x}\tilde{x}_n^{-1}\in (U^1)^{p^n}$, which means that
$\tilde{x}\mod (U^1)^{p^n}=x_n$, which terminates the surjectivity.
What do you think Lukas ?


TITLE: Norms on C[0, 1] inducing the same topology as the sup norm
QUESTION [29 upvotes]: This is an old homework problem of mine that I was never able to solve.  The solution may or may not involve the Baire category theorem, which I am terrible at applying.
Let $C[0, 1]$ denote the space of continuous functions $[0, 1] \to \mathbb{R}$.  Suppose $|| \cdot ||$ is a norm on $C[0, 1]$ with respect to which the evaluation functions $f \mapsto f(x), x \in [0, 1]$ are continuous.  Show that the topology induced by $|| \cdot ||$ is the same as the usual topology induced by the sup norm.
It is straightforward to show that any sequence converging uniformly converges with respect to $|| \cdot ||$.  I am stuck on proving the converse; I cannot seem to figure out how to use the assumption that $|| \cdot ||$ is a norm.
Edit:  Zhen Lin informs me that $|| \cdot ||$ is supposed to be complete.  That should make the problem statement true now!

REPLY [26 votes]: Here's $\DeclareMathOperator{\ev}{ev}$ the answer if $(C[0,1], \|\cdot\|)$ is assumed to be complete. Consider the family $\mathcal{F} = \{\ev_{x}\}_{x \in [0,1]}$ of continuous linear functionals on $(C[0,1],\|\cdot\|)$. For each $f \in C[0,1]$ we have $\sup_{x \in [0,1]} |\ev_{x}(f)| \leq \|f\|_{\infty}$, so the family $\mathcal{F}$ is pointwise bounded. By the uniform boundedness principle the family is uniformly bounded, that is to say $\sup_{x \in [0,1]} \|\ev_{x}\| \leq M$ for some constant $M$. On the other hand $|f(x)| = |\ev_{x}(f)| \leq \|ev_{x}\|\|f\| \leq M \|f\|$ gives $\|f\|_{\infty} = \sup_{x \in [0,1]} |f(x)| \leq M\|f\|$, so the identity $(C[0,1], \|\cdot\|) \to (C[0,1],\|\cdot\|_{\infty})$ has norm at most $M$. Since both spaces are complete, we may apply the open mapping theorem in order to conclude that its inverse is also continuous. In other words, the norms $\|\cdot\|$ and $\|\cdot\|_{\infty}$ are equivalent.

Edit. Here's an example that shows that completeness of the norm is necessary:
Choose a discontinuous linear functional $\varphi: (C[0,1],\|\cdot\|_{\infty}) \to \mathbb{R}$ and define a norm on $C[0,1]$ by
\[
\|f\| = \|f\|_{\infty} + |\varphi(f)|.
\]
Since $\|f\|_{\infty} \leq \|f\|$, we have that the identity $(C[0,1],\|\cdot\|) \to (C[0,1],\|\cdot\|_{\infty})$ is continuous. Since the evaluation functionals are continuous with respect to the sup-norm, they are also continuous with respect to the norm $\|\cdot\|$. But as $\varphi$ is discontinuous, there is a sequence $f_{n}$ with $\|f_{n}\|_{\infty} = 1$ and $|\varphi(f_{n})| \to \infty$, hence the norms cannot be equivalent. Of course, $\|\cdot\|$ cannot be complete because the last sentence would be in contradiction to the open mapping theorem.

Edit 2.
I forgot to argue why the topologies in the above counterexample are not the same. This is obvious: The functional $\varphi$ is continuous with respect to $\|\cdot\|$ but it isn't continuous with respect to $\|\cdot\|_{\infty}$.


TITLE: Evaluating the integral $\int_0^{\infty} \frac{\sin(x)}{\sinh(x)}\,dx$
QUESTION [8 upvotes]: I was trying to evaluate the following integral,
 $$I=\int_\limits {-\infty}^{\infty} \dfrac{\sin(x)}{\sinh(x)}\,dx$$  but had no success. I first expanded the the hyperbolic sine:
$$I=2\int_\limits {-\infty}^{\infty} \dfrac{\sin(x)}{e^{x}-e^{-x}}\,dx=2\Im \int_\limits {-\infty}^{\infty} \dfrac{e^{ix}}{e^{x}-e^{-x}}\,dx$$
I then substituted $u=e^x$,
$$I=2\Im\int_\limits {0}^{\infty} \dfrac{u^i}{u^2-1}\,du$$
Now, I'm not really sure what to do. Also, after exchanging the $\Im$ with the integral seemed to create a non-integrable singularity at $u=1$. When can you not do that?

REPLY [1 votes]: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\bbox[10px,#ffd]{%
2\int_{0}^{\infty}{\sin\pars{x} \over \sinh\pars{x}}\,\dd x} =
2\,\Im\int_{0}^{\infty}{\expo{\ic x} - 1 \over \pars{\expo{x} - \expo{-x}}/2}\,\dd x
\\[5mm] = &\
4\,\Im\int_{0}^{\infty}{\expo{-\pars{1 - \ic}x} - \expo{-x} \over 1 - \expo{-2x}}\,\dd x
\,\,\,\stackrel{\large\expo{-2x}\ =\ t}{\large =}\,\,\,
4\,\Im\int_{1}^{0}{t^{1/2 - \ic/2} - t^{1/2} \over 1 - t}\,
\pars{-\,{\dd t \over 2t}}
\\[5mm] = &\
2\,\Im\bracks{\int_{0}^{1}{1 - t^{-1/2} \over 1 - t}\,\dd t -
\int_{0}^{1}{1 - t^{-1/2 - \ic/2} \over 1 - t}\,\dd t}
\\[5mm] = &\
2\,\Im\bracks{\Psi\pars{1 \over 2} - \Psi\pars{{1 \over 2} - {\ic \over 2}}} =
-2\,\Im\Psi\pars{{1 \over 2} - {\ic \over 2}}
\\[5mm] = &\
-2\,{\Psi\pars{1/2 - \ic/2} - \Psi\pars{1/2 + \ic/2} \over 2\ic}
=
\ic\braces{\pi\cot\pars{\pi\bracks{{1 \over 2} + {\ic \over 2}}}}
\\[5mm] = &\
-\ic\pi\tan\pars{\pi\ic \over 2} =
\bbx{\pi\tanh\pars{\pi \over 2}}
\end{align}


TITLE: solve equation with sum $\ln x-\ln(\sqrt[2]{ x})+\ln(\sqrt[4]{ x})-\ln(\sqrt[8]{x})+...=2$
QUESTION [2 upvotes]: How to solve this? Any advice?
$$\ln x-\ln(\sqrt[2]{ x})+\ln(\sqrt[4]{ x})-\ln(\sqrt[8]{x})+...=2$$
Next step I do this
$\sum\limits_{n=0}^\mathbb{\infty}(-1)^n\ln(x^{\frac{1}{2^n}}) = 2$
But I don't know next step. Thanks.

REPLY [0 votes]: $$\begin{align}
2&=\ln x-\ln(\sqrt[2]{ x})+\ln(\sqrt[4]{ x})-\ln(\sqrt[8]{x})+\cdots\\
&=\ln x-\ln x^{\frac 12}+\ln x^{\frac 14}-\ln x^{\frac 18}+\cdots \\
&=\ln\left(\frac{x\cdot x^{\frac 14}\cdot x^{\frac 1{16}}\cdots}{\;\;x^\frac 12\cdot x^\frac 18\cdot x^{\frac 1{32}}\cdots
}\right)\\
&=\ln \left(x^{\frac 12}\cdot x^{\frac 18}\cdot x^{\frac 1{32}}\cdots\right)\\
&=\ln \left(x^{\frac 12+\frac 18+\frac 1{32}+\cdots}\right)\\
&=\left(\frac 12+\frac 18+\frac 1{32}+\cdots\right)\ln x\\
&=\frac {\frac 12}{1-\frac 14}\ln x\\
&=\frac 23 \ln x\\
3&=\ln x\\
x&=e^3\quad\blacksquare
\end{align}$$


TITLE: Why is it the case that $\rm\langle Socrates\rangle = Socrates$, while $\rm\{Socrates\}\neq Socrates$?
QUESTION [2 upvotes]: In Nolt's book called Logics (part III, chapter 7, § 7.1 Sets and $n$-tuples) one can read:

Ordered one-tuples, unlike unit sets, are the same things as the object they contain. Thus , for example, the one-tuple $\rm (Socrates) = Socrates$; and more generally, for any object $x$, $(x)  = x$.

Could you please explain Nolt's (too) short explanation (at least for me)?
Is this explanation a way of saying that a "$1$-tuple" is not a well defined object?
Is there a way to derive the formula $(x) = x$ from the set theoretic definition of an $n$-tuple?

REPLY [0 votes]: The most important thing to understand is a set or a list or a collection of an object is not the same thing as the object that is in the set or list or collection.  That is $\{Socrates\}$ is a set containing Socrates whereas Socrates is a guy of flesh and blood who drank hemlock millenia ago.
Now consider an ordered pair.  If I write:  $(3,2)$ that represents a point in 2-dimensional space where the 1st coordinate is $3$ and the 2nd coordinate is $2$.  Now when I write it out as "$(3,2)$" it looks like I am writing a list containing $3$ and $2$.  But it isn't a list.  It's a single point.  The thing is the only way to represent the point is to list out its components.  But it is understood that by so listing we are representing the point and not the list itself.
Same thing if we do a $1$-tuple, a point in $1$ dimensional space.  But a $1$-tuple with only one coordinate is just that... it's coordinate.  The one-tuple with a coordinate of $3$ is... the number $3$.
So whereas $\{3,2\}$ is a set of $3$ and $2$; and "$(3,2)$" is a listing of $3$ and $2$ inside parenthesis.  What the list "$(3,2)$" represents is the $2$-tuple $(3,2)$.
Likewise $\{3\}$ is a set of $3$; and "$(3)$" is a listing of $3$ inside parenthesis.  What the list "$(3)$" represents is the $1$-tuple $3$ or $(3)$ which is simply the value $3$-- a one-dimensional value with a coordinate value of $3$.


TITLE: Is the modulus of i^n 1 for all n?
QUESTION [3 upvotes]: As the tile says, is $\left | i^{n} \right | = 1$ for all real values of n?

REPLY [5 votes]: Since $|i^n|=|i|^n$, and $|i|=1$, then for all $n\in\mathbb R$ $|i^n|=|i|^n=1$ for the simple reason that $1$ raised to any real exponent is still $1$.