TITLE: equilibrium solutions question? with initial value and limit question?
QUESTION [1 upvotes]: $y'=y(y-2)(y-3)^2$
if $y(0) = 1$ what is the limits of $y(x)$ as $x \to +/-\infty?$
I have found the solutions of the differential equation and sketched the direction field if thats to any help on this one? $0$=stable $2$=unstable $3$=semi-stable :) any solutions/tips? :D

REPLY [2 votes]: We find three equilibrium points as:
$$y = 0, 2, 3$$
A direction field plot, with the initial condition (green) shows:

We can numerically solve this ODE and here is a plot of those results (note what happens to the limit of $y(t)$ as we approach $\pm~ \infty$). Compare this to the direction field plot and make the connection:

Another approach is to just draw the phase line.


text:
\begin{document} \pagenumbering{arabic} \setcounter{page}{1}
 \author[O.~Olmez]{Oktay Olmez}
\address{Department of Mathematics, Iowa State University,
Ames, Iowa, 50011, U. S. A.} \email[O. ~Olmez]{oolmez@iastate.edu}

\author[S. Y.~Song]{Sung Y. Song}
\address{Department of Mathematics, Iowa State University, Ames, Iowa, 50011, U. S.
A.} \email[S. Y.~Song]{sysong@iastate.edu}

\begin{abstract}

We use finite incident structures to construct new infinite families
of directed strongly regular graphs with parameters
\[(lq^l(q-1),\ lq^{l-1}(q-1),\ q^{l-2}(lq-l+1),\ (l-1)q^{l-2}(q-1),\
q^{l-2}(lq-l+1)),\] for integers $q$ and $l$ ($q, l\ge 2$), and
\[(lq^2(q-1),\ lq(q-1),\ lq-l+1,\ (l-1)(q-1),\ lq-l+1)\] for all prime powers $q$
and $l\in \{1, 2, \dots, q\}$. The new graphs given by these
constructions include those with parameter sets $(36, 12, 5, 2, 5)$,
$(54, 18, 7, 4, 7)$, $(72, 24, 10, 4, 10)$, $(96, 24, 7, 3, 7)$,
$(108, 36, 14, 8, 14)$ and $(108, 36, 15, 6, 15)$ listed as feasible
parameters on ``Parameters of directed strongly regular graphs" by
S. Hobart and A. E. Brouwer at ${http://homepages.cwi.nl/^\sim
aeb/math/dsrg/dsrg.html}$.  We also review these constructions and
show how our methods may be used to construct other infinite
families of directed strongly regular graphs. We then characterize
finite incidence structures from which we can produce directed
strongly regular graphs.
\end{abstract}

\maketitle

\tableofcontents

{\small {\it Keywords:} Affine planes, affine resolvable designs,
group-divisible designs, partial geometries.}

\section{Introduction and preliminaries}\label{sec:intro}

Directed strongly regular graphs were introduced by Duval \cite{Du}
in 1988 as directed versions of strongly regular graphs. There are
numerous sources for these graphs. Some of known constructions of
these graphs use combinatorial block designs \cite{FK}, coherent
algebras \cite{FK, KM}, finite geometries \cite{FK0, FK, GH, KP},
matrices \cite{Du, EH, GH}, and regular tournaments \cite{EH, Jo}.
Some infinite families of these graphs also appear as Cayley graphs
of groups \cite{DI, HS, Jo, Jo2, KM}. {\footnote{For the current
state-of-the-art on known constructions and the existence and
non-existence results of directed strongly regular graphs are found
in the Hobart and Brouwer's web \cite{BH} (also see the Handbook of
Combinatorial Designs \cite[Chap. VII.12]{BH2}.)}}

In this paper, we construct some new infinite families of directed
strongly regular graphs by using certain finite incidence
structures, such as, non-incident point-block pairs of a divisible
design and anti-flags of a partial geometry.

In Section 2, we describe a construction of a directed strongly
regular graph with parameters $(v, k, t, \lambda, \mu)$ given by
\[(lq^l(q-1),\ lq^{l-1}(q-1),\ q^{l-2}(lq-l+1),\ (l-1)q^{l-2}(q-1),\
q^{l-2}(lq-l+1)),\] for integers $l\ge 2$ and $q\ge 2$. The graph is
defined on the set of non-incident point-block pairs of group
divisible design GD$(l, q^{l-2}, q; ql)$. Among the feasible
parameters listed in \cite{BH}, our construction realizes the
feasibility of the parameter sets $(36, 12, 5, 2, 5)$ and $(96, 24,
7, 3, 7)$; and then $(72, 24, 10, 4, 10)$ and $(108, 36, 15, 6, 15)$
by applying for a construction of Duval \cite{Du}.

In section 3, we construct directed strongly regular graphs on the
sets of anti-flags of partial geometries. In particular, if we use
the partial geometry obtained from the affine plane of order $q$ by
considering all $q^2$ points and taking the $ql$ lines from exactly
$l$ pencils (parallel classes) of the plane, we obtain a directed
strongly regular graph with parameters
\[ (lq^2(q-1),\ lq(q-1),\ lq-l+1,\ (l-1)(q-1),\ lq-l+1).\]
Thus, for example, it follows the feasibility of the parameter sets
$(54, 18, 7, 4, 7)$ and $(108, 36, 14, 8, 14)$ among those listed in
\cite{BH}.

In section 4, we construct two families of directed strongly regular
graphs with parameters
\[(ql(l-1),\ q(l-1),\ q,\ 0,\ q)\] and
\[(ql(l-1),\ 2q(l-1)-1,\ ql-1,\ ql-2,\ 2q)\]
for integers $q\ge 2\mbox{ and } l\ge 3$. These graphs are not new.
J{\o}rgensen \cite{Jo2} showed that the graph with parameters
$(ql(l-1),\ q(l-1),\ q,\ 0,\ q)$ is unique for every integers $l\ge
2$ and $q\ge 2$. Godsil, Hobart and Martin constructed the second
family of graphs in \cite[Corollary 6.3]{GH}. Our construction for
the second family is essentially similar to the one in \cite{GH}.
However, both families of the graphs are constructed by using the
almost trivial incidence structure obtained from a partition of a
set of $ql$ elements into $l$ mutually disjoint $q$-element subsets.

In Section 5 and Section 6 we introduce how to construct directed
strongly regular graphs by using the anti-flags over the affine
resolvable designs and arbitrary 2-designs, respectively. In Section
7, we introduce a prolific construction method for directed strongly
regular graphs by using sets of anti-flags over certain tactical
configurations.

While there is a number of families of directed strongly regular
graphs constructed by using flags of finite geometries (cf.
\cite{BH, FK, GH, KM, KP}), there are few results for using
anti-flags or partial geometries. The results presented here adds
some constructions using sets of anti-flags of various finite
incidence structures including partial geometries, combinatorial
designs, and certain tactical configurations. More work is needed to
explore other incidence structures and address the existence and
non-existence problems of directed strongly regular graphs and their
related incidence structures.

\medskip
In the remainder of this section, we recall the definition and some
properties of directed strongly regular graphs.

A loopless directed graph $D$ with $v$ vertices is called
\textit{directed strongly regular graph} with parameters $(v, k, t,
\lambda, \mu)$ if and only if $D$ satisfies the following
conditions:
\begin{itemize}
\item[i)] Every vertex has in-degree and out-degree $k$.
\item[ii)] Every vertex $x$ has $t$ out-neighbors, all of which are
also in-neighbors of $x$.
\item[iii)] The number of directed paths of length two from a vertex
$x$ to another vertex $y$ is $\lambda$ if there is an edge from $x$
to $y$, and is $\mu$ if there is no edge from $x$ to
$y$.\end{itemize}

Another definition of a directed strongly regular graph, in terms of
its adjacency matrix, is often conveniently used. Let $D$ be a
directed graph with $v$ vertices. Let $A$ denote the adjacency
matrix of $D$, and let $I=I_v$ and $J=J_v$ denote the $v\times v$
identity matrix and all-ones matrix, respectively. Then $D$ is a
directed strongly regular graph with parameters $(v, k, t, \lambda,
\mu)$ if and only if (i) $JA=AJ=kJ$ and (ii) $A^2=tI+\lambda A+\mu
(J-I-A)$.

Duval observed that if $t=\mu$ and $A$ satisfies above equations (i)
and (ii), then so does $A\otimes J_m$ for every positive integer
$m$; and so, we have:

\begin{prop}\label{pro1} \cite{Du} If there exists a directed strongly regular
graph with parameters $(v,k,t,\lambda,\mu)$ and $t=\mu$, then for
each positive integer $m$ there exists a directed strongly regular
graph with parameters $(mv,mk,mt,m\lambda,m\mu)$.\end{prop}

\begin{prop} \label{Duval} \cite{Du} A directed strongly
regular graph with parameters $(v,k,t,\lambda,\mu)$ has three
distinct integer eigenvalues \[\theta_0=k,\quad
\theta_1=\frac12(\lambda-\mu+\delta),\quad
\theta_2=\frac12(\lambda-\mu-\delta)\] with multiplicities
\[m_0=1,\quad m_1=-\frac{k+\theta_2(v-1)}{\theta_1-\theta_2},\quad
m_2=\frac{k+\theta_1(v-1)}{\theta_1 - \theta_2},\] respectively,
where $\delta=\sqrt{(\mu-\lambda)^2+4(t-\mu)}$ is a positive
integer.\end{prop}

Throughout the paper, we will write $x\rightarrow y$ if there is an
edge from a vertex $x$ to another vertex $y$, and $x\nrightarrow y$
if there is no edge from $x$ to $y$. We will also write
$x\leftrightarrow y$ if and only if both $x\rightarrow y$ and
$y\rightarrow x$.

\section{Graphs obtained from group
divisible designs}\label{sec:CBG}

The first family of directed strongly regular graphs, which we shall
describe in this section, use non-incident point-block pairs of
group divisible designs GD$(l,q^{l-2}, q; ql)$ for integers $q\ge 2$
and $l\ge 2$.

Let $P$ be a $ql$-element set with a partition $\mc{P}$ of $P$ into
$l$ parts (`\textit{groups}') of size $q$. Let $\mc{P}=\{S_1, S_2,
\dots, S_l\}$. Let
$$\mc{B}=\{B\subset P:\ |B\cap S_i|=1 \mbox{ for all } i=1,2, \dots,
l\}.$$ Then $\mc{B}$ consists of $q^l$ subsets of size $l$ called
\textit{blocks}. The elements of $P$ will be called \textit{points}
of the incidence structure $(P, \mc{B})$ with the natural
point-block incidence relation $\in$. This structure has property
that any two points from the same group never occur together in a
block while any two points from different groups occur together in
$q^{l-2}$ blocks. It is known as a group-divisible design
GD$(l,q^{l-2}, q; ql)$.

\begin{defn} \label{D1} Let $(P, \mc{B})$ be the incidence structure
defined as above. Let $D=D(P, \mc{B})$ be the directed graph with
its vertex set
\[V(D)=\{(p, B)\in P\times \mc{B}:\ p\notin B\},\]
and directed edges given by $(p, B)\rightarrow (p', B')$ if and only
if $p\in B'$.\end{defn}

\begin{thm} \label{dsrg1} Let $D$ be the graph $D(P,\mc{B})$ defined in
Definition \ref{D1}. Then $D$ is a directed strongly regular graph
with parameters
\[\begin{array}{l} v=lq^l(q-1),\\
k= lq^{l-1}(q-1),\\ t=\mu=q^{l-2}(lq-l+1),\\
\lambda=q^{l-2} (l-1)(q-1).\\ \end{array}\]
\end{thm}

\begin{pf} It is easy to verify the values of $v$ and $k$.
 To find the value of $t$, let
$(p, B)\in V(D)$ with $B=\{b_1, b_2, \dots, b_l\}$, and let
$N^+((p,B))$ and $N^-((p,B))$ denote the set of out-neighbors and
that of in-neighbors of $(p,B)$, respectively. Then for $t$ we need
to count the elements of
\[ N^+((p,B))\cap N^-((p,B))
\ = \ \{(p^*, B^*)\in V(D):\ p\in B^* ,\ p^*\in B\}.\] Without loss
of generality, suppose that $p\in S_1$. Then condition $p\in B^*$
requires that $b_1^*$ must be $p$. The second condition $p^*\in B$
requires that $p^*=b_i$ for some $i$. With the choice of $p^*=b_1$,
there are $q^{l-1}$ blocks $B^*=\{b_1^*, b_2^*, \dots, b_l^*\}$ with
$b_1^*=p$ can be paired with $p^*=b_1$. On the other hand, with
$p^*=b_j$ for $j\neq 1$, we have $(q-1)q^{l-2}$ choices for $B^*$
with $b_1^*=p$, $b_j^*\in S_j\setminus\{b_j\}$ and $b_i^*\in S_i$
for all $i\in \{2, 3, \dots, l\}\setminus \{j\}$. Hence $t =
q^{l-1}+(l-1)(q-1)q^{l-2}$.

We now claim that the number of directed paths of length two from a
vertex $(p, B)$ to another vertex $(p', B')$ depends only on whether
there is an edge from $(p,B)$ to $(p',B')$.

Suppose that $(p, B)\rightarrow (p', B')$; that is, $p\in B'$. Then,
without loss of generality, we may assume that $p=b_1'$, and have
\[\begin{array}{ll} \lambda &=\ |N^+((p,B))\cap N^-((p',B'))|\\
& = |\{(p^*, B^*)\in V(D):\ p=b_1'\in B^*,\ p^*\in B'\}|\\
&= |\{(p^*, \{p, b_2^*,\dots, b_l^*\}): \ p^*\in
B'\setminus\{b_1'\},\ b_i^*\in S_i\setminus\{p^*\}\mbox{ for } i=2,
3, \dots, l\}|\\
& =(l-1)(q-1)q^{l-2}.\end{array} \]

For $\mu$, suppose $(p, B)\nrightarrow (p', B')$. Then
$\mu=|\{(p^*,B^*): p\in B^*,\ p^*\in B'\}|$ with $p\notin B'$.
Without loss of generality, we assume that $p\in S_1$, and have
\[\begin{array}{ll} \mu &
=\ |\{(b_1',\{p, b_2^*, \dots, b_l^*\}):\ b_i^*\in S_i \mbox{ for
}i=2, 3,\dots, l\}|\\
&\ +\ \sum\limits_{i=2}^l |\{(b_i', \{p, b_2^*,\dots, b_l^*\}):
b_i^*\in S_i\setminus\{b_i'\},\ b_j^*\in S_j\mbox{ for } j\in\{2,
3,\dots,
l\}\setminus\{i\} \}|\\
& =\ q^{l-1}+(l-1)(q-1)q^{l-2}.\end{array}\] This completes the
proof.
\end{pf}

\begin{rem} By Proposition \ref{pro1}, there are directed strongly
regular graphs with parameters
\[(mlq^l(q-1),\ mlq^{l-1}(q-1),\ mq^{l-2}(lq-l+1),\ mq^{l-2}(l-1)(q-1),\
mq^{l-2}(lq-l+1))\] for all positive integers $m$. These graphs can
be constructed directly by replacing all edges by multiple edges
with multiplicity $m$ in the above construction.
\end{rem}
\begin{rem} In the case of $l=2$ ($m=1$) in the above construction, we
obtain the graphs with parameters
$$(2q^2(q-1), \ 2q(q-1),\ 2q-1,\ q-1,\ 2q-1).$$ These graphs are
constructed on the sets of non-incident vertex-edge pairs of
complete bipartite graphs $K_{q,q}$. If we use complete bipartite
multigraph with multiplicity $m$ for each edge as in the above
remark, we obtain directed strongly regular graphs with parameters,
$$(2mq^2(q-1), \ 2mq(q-1),\ m(2q-1),\ m(q-1),\ m(2q-1)).$$ With
several combinations of small $m$ and $q$, we obtain new directed
strongly regular graphs with parameter sets $(36, 12, 5, 2, 5)$,
$(96, 24, 7, 3, 7)$, $(72, 24, 10, 4, 10)$ and $(108, 36, 15, 6,
15)$. So the feasibility of these parameter sets which are listed in
\cite{BH} has been realized.
\end{rem}

By Proposition \ref{Duval}, we can easily compute the eigenvalues
for $D(P,\mc{B})$.
\begin{lem}\label{cor1} If a directed strongly
regular graph with parameters $(v,k,t,\lambda,\mu)$ satisfies
$t=\mu=\lambda +q^{l-1}$ for positive integers $q$ and $l\ge 2$,
then its eigenvalues are $\theta_0=k,\ \theta_1=0,\
\theta_2=-q^{l-1}$ with multiplicities $m_0=1,\
m_1=v-1-\frac{k}{q^{l-1}},\ m_2=\frac{k}{q^{l-1}},$ respectively.
\end{lem}

\begin{exa} (Parameter sets for small DSRGs (orders up to 110)
constructed.)
\[\begin{array}{ll}
(v, k, t, \lambda, \mu) & l, q, m\\
\hline
(8, 4, 3, 1, 3) & l=q=2\\
(16, 8, 6, 2, 6) &  l=q=2;\ m=2\\
(24, 12, 9, 3, 9) &  l=q=2;\ m=3\\
(24, 12, 8, 4, 8) & l=3, q=2\\
(32, 16, 12, 4, 12) &  l=q=2;\ m=4\\
(36, 12, 5, 2, 5) & l=2, q=3 \\
(40, 20, 15, 5, 15)&  l=q=2;\ m=5\\
(48, 24, 16, 8, 16) &  l=3, q=2;\ m=2\\
(48, 24, 18, 6, 18) & l=q=2;\ m=6\\
(56, 28, 21, 7, 21) & l=q=2;\ m=7\\
(64, 32, 20, 4, 20) & l=4, q=2\\
(64, 32, 24, 8, 24) & l=q=2;\ m=8\\
(72, 24, 10, 4, 10) &  l=2, q=3;\ m=2\\
(72, 36, 24, 12, 24) & l=3, q=2; \ m=2\\
(72, 36, 27, 9, 27) &  l=q=2; \ m=9\\
(80, 40, 30, 10, 30) &  l=q=2;\ m=10\\
(88, 44, 33, 11, 33) & l=q=2;\ m=11\\
(96, 24, 7, 3, 7)& l=2, q=4\\
(96, 48, 32, 16, 32) &  l=3, q=2;\ m=4\\
(96, 48, 36, 12, 36) &  l=q=2;\ m=12\\
(104, 52, 39, 13, 39) & l=q=2;\ m=13\\
(108, 36, 15, 6, 15) &  l=2, q=3;\ m=3\\ \end{array}\]
\end{exa}

\section{Graphs obtained from partial geometries}\label{sec:AP}

In this section, we use partial geometries to construct a family of
directed strongly regular graphs. The concept of a partial geometry
was introduced by R. C. Bose in connection with his study of large
cliques of more general strongly regular graphs in \cite{Bo}.

A partial geometry $\ts{pg}(\kappa, \rho, \tau)$ is a set of points
$P$, a set of lines $\mc{L}$, and an incidence relation between $P$
and $\mc{L}$ with the following properties:
\begin{enumerate}
\item Every line is incident with $\kappa$ points ($\kappa\ge 2$),
and every point is incident with $\rho$ lines ($\rho\ge 2$).
\item Any two points are incident with at most one line.
\item If a point $p$ and a line $L$ are not incident, then
there exists exactly $\tau$ ($\tau\ge 1$) lines that are incident
with $p$ and incident with $L$.\end{enumerate} Here we use
parameters $(\kappa, \rho, \tau)$ instead of more traditional
notations, $(K, R, T)$ or $(1+t, 1+s, \alpha)$ used in \cite{Bo, BC}
or \cite{Th}. In what follows, we often identify a line $L$ as the
set of $\kappa$ points that are incident with $L$; so, when $p$ and
$L$ are incident, we write ``$p\in L$," as well as ``$p$ is on $L$,"
and ``$L$ passes through $p$".

\begin{defn}\label{dpg} Let $D=D(\ts{pg}(\kappa, \rho, \tau))$ be the directed
graph with its vertex set
\[V(D)=\{(p, L)\in P\times \mc{L}:\ p\notin L\},\]
and directed edges given by $(p, L)\rightarrow (p', L')$ if and only
if $p\in L'$.
\end{defn}

\begin{thm}\label{pg} Let $D$ be the graph $D(\ts{pg}(\kappa, \rho,\tau))$
defined as above. Then $D$ is a directed strongly regular graph with
parameters
\[\begin{array}{l} v=\frac{\kappa\rho(\kappa-1)(\rho-1)}{\tau}
\left(1+\frac{(\kappa-1)(\rho-1)}{\tau}\right),\\
k=\frac{\kappa\rho(\kappa-1)(\rho-1)}{\tau},\\
t=\mu= \kappa\rho-\tau,\\
\lambda= (\kappa-1)(\rho-1).\\ \end{array}\]
\end{thm}

\begin{pf} The value $v$ is clear as it counts the number of anti-flags
of $\ts{pg}(\kappa,\rho,\tau)$ which has
$\kappa\left(1+\frac{(\kappa-1)(\rho-1)}{\tau}\right)$ points and
$\rho\left(1+\frac{(\kappa-1)(\rho-1)}{\tau}\right)$ lines. Also it
is clear that \[k=|\{(p',L'): p\in
L'\}|=\rho(v-\kappa)=\kappa\rho(\kappa-1)(\rho-1)/\tau.\]

For $t$, given a vertex $(p, L)\in V(D)$, we count the cardinality
of
\[
N^+((p,L))\ \cap\ N^-((p,L))=\{(p', L')\in V(D):\ p\in L' ,\ p'\in
L\}.
\] Among the $\rho$ lines passing through $p$, $\rho-\tau$ lines
are parallel to $L$. If $L'$ is parallel to $L$, then all $\kappa$
points on $L$ can make legitimate non-incident point-line pairs
$(p', L')$ with given $L'$. In the case when $L'$ is not parallel to
$L$, all points on $L$ except for the common incident point of $L$
and $L'$, can form desired pairs. Hence we have
\[t=(\rho-\tau)\kappa + \tau (\kappa-1)= \kappa\rho-\tau.\]

For $\lambda$, suppose $(p, L)\rightarrow (p',L')$. It is clear that
 \[\lambda=|\{(p^*,L^*): p\in L^*,\ p^*\in L'\}|=(\rho-1)(\kappa-1),\]
 because each of $\rho-1$ lines passing through $p$ (excluding $L'$)
 can be paired with any of $\kappa-1$ points on $L'\setminus\{p\}$.

For given $(p, L)$ and $(p',L')$ with $p\notin L'$,
 \[\mu=|\{(p^*,L^*): p\in L^*,\ p^*\in L'\}|=(\rho-\tau)\kappa
 +\tau(\kappa-1)=\kappa\rho-\tau,\]
since among the $\rho$ lines passing through $p$, the ones that are
parallel to $L'$ can form desired pairs with any of $\kappa$ points
on $L'$, while each of the remaining $\tau$ lines can be paired with
$\kappa-1$ points on $L'$.
\end{pf}

Partial geometries are ubiquitous. For example, partial geometries
with $\tau =1$ are generalized quadrangles, those with $\tau=\kappa
-1$ are transversal designs, and those with $\tau=\rho-1$ are known
as nets. In order to have some concrete examples of new directed
strongly regular graphs of small order, we consider a special class
of partial geometries that are obtained from finite affine planes.

Let $AP(q)$ denote the affine plane of order $q$. Let $\ol{AP}^l(q)$
denote the partial geometry obtained from $AP(q)$ by considering all
$q^2$ points and taking the lines of $l$ parallel classes of the
plane. Then $\ol{AP}^l(q)$ inherits the following properties from
$AP(q)$: (i) every point is incident with $l$ lines, and every line
is incident with $q$ points, (ii) any two points are incident with
at most one line, (iii) if $p$ and $L$ are non-incident point-line
pair, there are exactly $l-1$ lines containing $p$ which meet $L$.
That is, $\ol{AP}^l(q)=\ts{pg}(q,l,l-1)$.

\begin{cor} \label{AP} Let $D=D(\ol{AP}^l(q))$ be the directed graph
$D(\ts{pg}(q, l, l-1))$ defined as in Definition \ref{dpg}. Then $D$
is a directed strongly regular graph with parameters
\[(v,k, t, \lambda, \mu)=(lq^2(q-1),\ lq(q-1),\ lq-l+1,\ (l-1)(q-1),\
lq-l+1).\] \end{cor}

\begin{pf} It immediately follows from Theorem \ref{pg}. \end{pf}

In particular, if $l=q$, $\ol{AP}^q(q)=\ts{pg}(q,q,q-1)$ is a
transversal design TD$(q,q)=(P, \mathcal{G}, \mathcal{L})$ of order
$q$, block size $q$, and index 1 in the following sense.
\begin{enumerate}
\item  $P$ is the set of $q^2$ points of $\ol{AP}^q(q)$;
\item  $\mc{G}$ is the partition of $P$ into $q$ classes (groups) such that
each class consists of $q$ points that were collinear in $AP(q)$ but
not in $\ol{AP}^q(q)$;
\item  $\mc{L}$ is the set of $q^2$ lines (blocks);
\item every unordered pair of points in $P$ is contained in either
exactly one group or in exactly one block, but not both.
\end{enumerate}

\begin{cor} Let $D$ be the graph $D(\ol{AP}^q(q))$ defined as above.
Then $D$ is a directed strongly regular graph with parameters
\[(v,k, t, \lambda, \mu)=(q^3(q-1),\ q^2(q-1),\ q^2-q+1,\ (q-1)^2,\
q^2-q+1).\] The eigenvalues of this graph are $q^2(q-1),\ 0,\ -q$
with multiplicities $1,\ q^4-q^3-q^2+q-1,\ q(q-1),$ respectively.
\end{cor}

\begin{exa} This method produces the DSRGs with the following
parameter sets (with order up to $110$ and $m=1$ only):
\[\begin{array}{ll}
(v, k, t, \lambda, \mu) & l, q, m\\
\hline (8, 4, 3, 1, 3) & l=q=2\\
(12, 6, 4, 2, 4) & l=3, q=2\\
(16, 8, 5, 3, 5) & l=4, q=2\\
(20, 10, 7, 4, 7) & l=5, q=2\\
(24, 12, 7, 5, 7) & l=6, q=2\\

(28, 14, 8, 6, 8) & l=7, q=2\\
(32, 16, 9, 7, 9) & l=8, q=2\\

(36, 12, 5, 2, 5) & l=2, q=3 \\

(54, 18, 7, 4, 7) & l=q=3\\
(72, 24, 9, 6, 9) & l=4, q=3\\

(96, 24, 7, 3, 7) & l=2, q=4\\

\end{array}\]
Among these, the parameter sets $(54, 18, 7, 4, 7)$; and so $(108,
36, 14, 8, 14),$ $(162, 54, 21, 12, 21) \cdots $ confirm the
feasibility of the putative parameter sets listed in \cite{BH}.
These graphs share the same automorphism group which is isomorphic
to $(((Z_3\times Z_3)\rtimes Z_3)\rtimes Z_2)\rtimes Z_2$.
\end{exa}

\begin{rem} When $l=2$, we obtain the directed strongly regular graph
with parameters $(4q^2, 4q, 2q-1, q-1, 2q-1)$ in both Section 2 and
Section 3. The two graphs are shown to be isomorphic although the
construction methods are different. We demonstrate the isomorphism
through an example; namely, for the case when $q=3$, the directed
strongly regular graph with parameters $(36, 12, 5, 2, 5)$. The one,
denoted by $D_1$, is coming from non-incident vertex-edge pairs of
the complete bipartite graph $K_{3,3}$ with partite sets $\{1, 2,
3\}$ and $\{4, 5, 6\}$. The other, denoted by $D_2$, comes as
$D_2=D(\overline{AP})^2(3)$, with point set $P=\{1, 2, \dots, 9\}$
and line set $\mc{L}=\{123, 456, 789, 147, 258, 369\}$ of
$\overline{AP}^2(3)$.

The following map between the vertices (anti-flags of the underlying
incident structures,) establishes the isomorphism between the graphs
$D_1$ and $D_2$, where the adjacency of vertices in $D_1$ is defined
by
$$(h, ij)\rightarrow (h', i'j')\mbox{ iff } h\in i'j'$$ while that
of $D_2$ is defined by
$$(hij,l)\rightarrow (h'i'j',l')\mbox{ iff } l'\in \{hij\}.$$

\[\begin{array}{|lcl|lcl|lcl|}\hline
1,24 &\leftrightarrow & 123,4 & 2,14 &\leftrightarrow & 456, 1 & 3,14 &\leftrightarrow & 789, 1\\
1,25 &\leftrightarrow & 123,5 & 2,15 &\leftrightarrow & 456, 2 & 3,15 &\leftrightarrow & 789, 2\\
1,26 &\leftrightarrow & 123,6 & 2,16 &\leftrightarrow & 456, 3 & 3,16 &\leftrightarrow & 789, 3\\
1,34 &\leftrightarrow & 123,7 & 2,34 &\leftrightarrow & 456, 7 & 3,24 &\leftrightarrow & 789, 4\\
1,35 &\leftrightarrow & 123,8 & 2,35 &\leftrightarrow & 456, 8 & 3,25 &\leftrightarrow & 789, 5\\
1,36 &\leftrightarrow & 123,9 & 2,36 &\leftrightarrow & 456, 9 & 3,26 &\leftrightarrow & 789, 6\\
4,15 &\leftrightarrow & 147,2 & 5,14 &\leftrightarrow & 258, 1 & 6,14 &\leftrightarrow & 369, 1\\
4,16 &\leftrightarrow & 147,3 & 5,16 &\leftrightarrow & 258, 3 & 6,15 &\leftrightarrow & 369, 2\\
4,25 &\leftrightarrow & 147,5 & 5,24 &\leftrightarrow & 258, 4 & 6,24 &\leftrightarrow & 369, 4\\
4,26 &\leftrightarrow & 147,6 & 5,26 &\leftrightarrow & 258, 6 & 6,25 &\leftrightarrow & 369, 5\\
4,35 &\leftrightarrow & 147,8 & 5,34 &\leftrightarrow & 258, 7 & 6,34 &\leftrightarrow & 369, 7\\
4,36 &\leftrightarrow & 147,9 & 5,36 &\leftrightarrow & 258, 9 & 6,35 &\leftrightarrow & 369, 8\\
\hline
\end{array}\]

\end{rem}

\section{Graphs obtained from partitioned sets}\label{sec:DSGN}

In this section we construct directed strongly regular graphs for
two parameter sets,
\[(ql(l-1),\ q(l-1),\ q,\ 0,\ q)\] and \[(ql(l-1),\ 2q(l-1)-1,\
ql-1,\ ql-2,\ 2q)\] for all positive integers $q\ge 1$ and $l\ge 3$.
The incidence structure which will be used here may be viewed as a
degenerate case of those used in earlier sections. The graphs
produced by this construction are not new. The latter family of
graphs have been constructed by Godsil, Hobart and Martin in
\cite[Corollary 6.3]{GH}. Nevertheless, we introduce our
construction to illustrate a variation of constructions which may be
applied to produce new families of directed strongly regular graphs.

Let $P$ be a set of $ql$ elements (`points'), and let $S_1, S_2,
\dots, S_l$ be $l$ mutually disjoint $q$-element subsets of $P$
(`blocks'). We denote the family of blocks by $\mc{S}=\{S_1, S_2,
\dots, S_l\}$. We will say that point $x\in P$ and block $S\in
\mc{S}$ is a non-incident point-block pair if and only if $x\notin
S$.

For the directed strongly regular graph with the first parameter
set, let $D=D(P,\mc{S})$ be the directed graph with its vertex set
\[V(D)=\{(x, S)\in P\times \mc{S}:\ x\notin
S \},\] and directed edges defined by $(x,S)\rightarrow (x',S')$ if
and only if $x\in S'$.

\begin{thm} Let $P$, $\mc{S}$ and $D(P,\mc{S})$ be as the above.
Then $D(P,\mc{S})$ is a directed strongly regular graph with
parameters
\[(ql(l-1),\ q(l-1),\ q,\ 0,\ q).\]
\end{thm}
\begin{pf}
Easy counting arguments give the values for parameters.
\end{pf}

\begin{rem} J{\o}rgensen \cite{Jo2} showed that the directed strongly regular
graph with parameters $(ql(l-1),\ q(l-1),\ q,\ 0,\ q)$ is unique for
all positive integers $l$ and $q$.
\end{rem}

For the directed strongly regular graph with the second parameter
set, let $G=G(P,\mc{S})$ be the directed graph with its vertex set
\[V(G)=\{(x, S)\in P\times \mc{S}:\ x\notin S \},\] where $P$ and
$\mc{S}$ are as the above, and let edges on $V(G)$ be defined by:
$(x,S)\rightarrow (x',S')$ if and only if
\[ \left \{\begin{array}{l} (1)\ x\in S' ; \mbox{ or} \\
(2)\ S=S'\mbox{ and } x\neq x'.\\ \end{array}\right . \]

\begin{thm} Let $G$ be the graph $G(P,\mc{S})$ defined as above.
Then $G$ is a directed
strongly regular graph with parameters \[(ql(l-1),\ 2q(l-1)-1,\
ql-1,\ ql-2,\ 2q).\]\end{thm}
\begin{pf} Clearly $v=ql(l-1)$ as $|V(G)|=|V|\cdot (|\mc{S}|-1)$.

Given a vertex $(x,S)$, let \[\begin{array}{l}
N_1((x, S)):=\{(x', S'): x\in S' \mbox{ and } x'\in S\}\\
N_2((x, S)):=\{(x', S'): S=S' \mbox{ and }
x\neq x'\}\\
N_3((x, S)):=\{(x', S'): x\in S'\mbox{ and } x'\notin S\}\\
\end{array}\]
Then by simple counting, we have
\[\begin{array}{l} |N_1((x, S))|=q\\ |N_2((x, S))|= q(l-2)+q-1\\
|N_3((x, S)|=q(l-2). \\ \end{array}\] Hence, $t=|N_1((x, S))|+
|N_2((x, S))|= ql-1$, and $k=t+|N_3((x,S))|=2ql-2q-1$.

Finally, we count the number of vertices $(x^*, S^*)$ that belongs
to $N^+((x,S))\cap N^-((x',S'))$ for $\lambda$ and $\mu$.

For $\lambda$, given an edge $(x,S)\rightarrow (x',S')$, we shall
need to consider the following two cases separately: (Case 1) when
$x\in S'$, and (Case 2) when $S=S'$ and $x\neq x'$.\\ Case (1).
Suppose $x\in S'$. Then unless $S^*=S$, $S^*$ must contain $x$ which
forces $S^*=S'$. With $S^*=S'$, all points that are not belong to
$S'\cup \{x'\}$ can be chosen to be $x^*$; and so, there are
$q(l-1)-1$ choices for $x^*$. With $S^*=S$, the $q-1$ points of the
set $S'\setminus\{x\}$ are possible for $x^*$. Together there are
$ql-2$
vertices $(x^*, S^*)$ belonging to $N^+((x,S))\cap N^-((x',S'))$.\\
Case (2). Let $S=S'$. Then with the choice of $S^*=S=S'$, $x^*$ can
be chosen from $P\setminus (S\cup \{x, x'\})$; and so, there are
$q(l-1)-2$ choices for $x^*$. Also with the choice of $S^*$ being
the block containing $x$, any point in $S$ can be chosen as $x^*$;
and so, there are $q$ possible choices for $x^*$. Together we have
$ql-2$ choices for $(x^*, S^*)$ as well. Hence we have
$\lambda=ql-2$.

For $\mu$, suppose $S\neq S'$ and $x\notin S'$. Then it is clear
that
\[\mu=|\{(x^*, S^*): x\in S^*, x^*\in S'\}\cup \{(x^*, S^*): S^*=S,
x\in S'\}|=q+q.\] This completes the proof.
\end{pf}
\section{Graphs obtained from affine resolvable designs}
Let $\vb, \kb$ and $\lb$ be positive integers such that
$\vb>\kb>\lb$. Let $\mc{D}=(P, \mc{B})$ be a $2-(\vb,\kb,\lb)$
design such that $|P|=\vb$, each block consists of $\kb$ points, and
each pair of distinct points occurs in exactly $\lb$ blocks. Every
point belongs to $\rb=\frac{\lb(\vb-1)}{\kb-1}$ blocks, and the
block set $\mc{B}$ consists of $\bb=\frac{\lb\vb(\vb -1)}{\kb(\kb
-1)}$ blocks. A parallel class is a set of pairwise disjoint blocks
that is a partition of $P$. Obviously a parallel class can exist
only if $\vb$ is divisible by $\kb$ or equivalently, $\bb$ is
divisible by $\rb$.

A $2-(\vb,\kb,\lb)$ design is resolvable if the block set $\mc{B}$
can be partitioned into $\rb$ disjoint parallel classes. A
resolvable design $\mc{D}=(P, \mc{B})$ is called affine (or affine
resolvable) if there exists a positive integer $m$ such that any two
non-parallel blocks intersect in exactly $m$ point(s). All
parameters of an affine design may be expressed in terms of $m$ and
another parameter $s$ where $s=({\vb}/{\kb})=({\bb}/{\rb})$, the
number of blocks in a parallel class, as follows (cf. \cite{Bose}):

\[\vb=m s^2,\ \bb=\frac{s(m s^2-1)}{s-1},\ \rb=\frac{m s^2 -1}{s
-1},\ \kb=m s,\ \lb=\frac{m s -1}{s-1}.\]

Let $(P, \mc{B})$ be an affine resolvable $2-(\vb, \bb, \kb, \rb,
\lb)$ design with $m={\kb^2}/{\vb}$ and $s={\vb}/{\kb}$. We denote
this design by $AP_{m}(s)$. Let $\ol{AP}^l_{m}(s)$ denote the
incidence structure obtained from $AP_{m}(s)$ by considering all
$\vb$ points in $P$ and taking the blocks of any $l$ parallel
classes of the design $(P, \mc{B})$ for $1<l< \rb$. Let
$\bar{\mc{B}}$ denote the set of blocks in the $l$ parallel classes.
Then $\ol{AP}^l_{m}(s)=(P, \bar{\mc{B}})$ inherits the following
properties from $AP_{m}(s)$: (i) every point is incident with $l$
blocks, and every block is incident with $\kb$ points, (ii) any two
points are incident with at most $\lb$ blocks, (iii) if $p$ and $B$
are non-incident point-block pair, there are exactly $l-1$ blocks
containing $p$ which intersect with $B$ in $m$ point(s).

\begin{thm} \label{dsrg-ARD} For $m\ge 1, s\ge 2$ and $l\ge 2$,
let $\ol{AP}^l_{m}(s)$ be the tactical configuration defined as
above. Let $D=D(AP^l_{m}(s))$ be the directed graph with its vertex
set
\[V(D)=\{(p, B)\in P\times \bar{\mc{B}}:\ p\notin B\},\]
and directed edges defined by $$(p, B)\rightarrow (p', B') \mbox{ if
and only if } p\in B'.$$ Then $D$ is a directed strongly regular
graph with parameters
\[v=m ls^2(s-1),\ k=m ls(s-1),\ t=\mu=m(ls-l+1),\ \lambda= m(l-1)(s-1).\]
\end{thm}
\begin{pf} By straightforward counting, we find
\[v=ls(\vb -\kb),\ k=l(\vb -\kb),\ t=(l-1)(\kb -m)+\kb,\
\lambda= (l-1)(\kb -m),\ \mu=(l-1)(\kb -m)+\kb.\] If we write these
parameters in terms of $l, m$ and $s$, we get the desired
expression.
\end{pf}

\begin{rem}
This is a generalization of the construction of the directed
strongly regular graphs obtained from the degenerated affine plane
described in Corollary \ref{AP}. In fact, the graphs obtained for
$m=1$ in Theorem \ref{dsrg-ARD} are the ones obtained in Corollary
\ref{AP}. From the graphs with $m=1$, we can obtain graphs with
$m\ge 2$ by the `$m$-multiple construction method' introduced by
Duval \cite{Du}.
\end{rem}

\begin{rem}
In regard to the source of affine resolvable designs, we would like
to recall the concept of orthogonal arrays. An orthogonal array
$A[n, q, \mu]$ of strength 2, $q$ constraints and index $\mu$ is a
$q\times \mu n^2$ matrix with entries from an $n$-set with the
property that any two of its rows contain each of the $n^2$ ordered
pairs of symbols exactly $\mu$ times. The parameters of an
orthogonal array satisfy the inequality $q\le \frac{\mu
n^2-1}{n-1}$. An orthogonal array is called complete if if satisfy
the equality $q= \frac{\mu n^2-1}{n-1}$. The existence of an affine
resolvable $2-(\vb,\bb, \kb, \rb, \Lambda)$ is equivalent to the
existence of a complete orthogonal array with $n=\frac{\vb}{\kb}$,
$q=\rb$, $\mu=\frac{\kb^2}{\vb}$ \cite{Sh}. Many concrete examples
may be obtained from the study of orthogonal arrays. \end{rem}

Here are the parameters of the graphs (with small orders) that are
constructed by our method described above. -- This table may be
deleted.

\[\begin{array} {|rrrrr|l||rrrrr|l|}\hline
v &  k & t& \lambda & \mu & (\vb, \kb, \lb; s, m, l) & v &  k & t&
\lambda & \mu & (\vb, \kb, \lb; s, m, l)\\
\hline \hline 12 & 6& 4& 2 & 4 &  (4, 2,6; 2, 1, 3)
&132& 66& 36& 30& 36& (12,6,22;2,3,11) \\
\hline 8 & 4& 3& 1& 3& (4,2,6; 2, 1, 2)
&120& 60& 33& 27& 33& (12,6,22;2,3,10)\\
\hline 56& 28& 16& 12& 16& (8,4,14;2, 2, 7)&
108& 54& 30& 24& 30& (12,6,22;2,3,9)\\
\hline 48 & 24& 14& 10& 14& (8,4,14;2, 2, 6)
&96& 48& 27& 21& 27& (12,6,22;2,3,8)\\
\hline 40 & 20& 12& 8& 12& (8,4,14; 2, 2,5)
&84& 42& 24& 18& 24& (12,6,22;2,3,7)\\
\hline 32 & 16& 10& 6& 10& (8,4,14;2,2,4)
&72& 36& 21& 15& 21& (12,6,22;2,3,6)\\
\hline 24 & 12& 8& 4& 8& (8,4,14;2,2,3)
&60& 30& 18& 12& 18& (12,6,22;2,3,5)\\
\hline 16 & 8& 6& 2& 6& (8,4,14;2, 2, 2)
&48& 24& 15& 9& 15& (12,6,22;2,3,4)\\
\hline 72 & 24& 9& 6& 9& (9,3,12;3,1,4)
&36& 18& 12& 6& 12& (12,6,22;2,3,3)\\
\hline *54& 18& 7& 4& 7& (9,3,12;3,1,3)
&24& 12& 9& 3& 9& (12,6,22;2,3,2)\\
\hline *36& 12& 5& 3& 5& (9,3,12;3,1,2) & & & & & &\\
 \hline \end{array}\]

\bigskip

\section{Graphs obtained from $2-(\vb, \kb, \lb)$ designs}

The balanced incomplete block designs have been used to produce
directed strongly regular graphs (cf. \cite{BH}). In this section,
we will see that we can also construct many directed strongly
regular graphs on the sets of anti-flags of every $2-(\vb, \bb, \kb,
\rb, \lb)$ design (with $\bb+\lb>2\rb$) in the following two
different ways.

\begin{thm} \label{dsrg-2-D1}
Let $\mc{D}=(P, \mc{B})$ be a $2-(\vb, \bb, \kb, \rb, \lb)$ design
with $\bb+\lb>2\rb$.
 Let $D=D(P,\mc{B})$ be the directed graph with its vertex set
\[V(D)=\{(p, B)\in P\times {\mc{B}}:\ p\notin B\},\]
and directed edges defined by $(p, B)\rightarrow (p', B')$ if and
only if $p'\in B$.

Then $D$ is a directed strongly regular graph with parameters
\[v=\vb (\bb - \rb)=\frac{\lb \vb (\vb -1)(\vb - \kb)}
{\kb (\kb -1)},\quad k=\kb (\bb -\rb)=\frac{\lb (\vb -1)(\vb -
\kb)}{\kb (\kb -1)},\]
\[t=\mu=\kb (\rb -\lb)=\frac{\lb \kb (\vb - \kb)}{\kb -1},\quad
\lambda= (\kb -1)(\rb -\lb)=\lb(\vb - \kb).\]
\end{thm}

\begin{pf} It is easy to verify the values of the parameters.
\end{pf}

\begin{rem} This is another way to construct the graphs that may be
constructed by the method of [T8] in Brouwer and Hobart's home page.
The construction [T8] uses the complementary designs of 2-designs
instead of 2-designs themselves.
\end{rem}

The second method of obtaining directed strongly regular graphs from
the anti-flags of 2-designs uses a different rule for the adjacency.
\begin{thm} \label{dsrg-2-D2}
Let $\mc{D}=(P, \mc{B})$ be a $2-(\vb, \bb, \kb, \rb, \lb)$ design
with $\bb+\lb>2\rb$.
 Let $D=D(P,\mc{B})$ be the directed graph with its vertex set
\[V(D)=\{(p, B)\in P\times {\mc{B}}:\ p\notin B\},\]
and directed edges given by $(p, B)\rightarrow (p', B')$ if and only
if either $p'\in B$ or $p=p'$ and $B\neq B'$. Then $D$ is a directed
strongly regular graph with parameters
\[\begin{array}{l} v=\vb (\bb - \rb),\\
k=\kb (\bb -\rb)+(\bb -\rb -1),\\ t=\kb (\rb -\lb)+ (\bb -\rb -1),\\
\lambda= \kb (\rb -\lb) + (\bb -\rb -2), \\ \mu=(\kb +1) (\rb -\lb).\\
\end{array}\]
\end{thm}

\begin{pf} The values of the parameters can be verified by the similar
counting argument.
\end{pf}

config: arxiv


TITLE: Solving modular arithmetic equation $7x\equiv5 \pmod {256}$
QUESTION [0 upvotes]: I'm trying to solve the following equation: $7x\equiv5 \pmod {256}$
My attempt:
$7x\equiv5 \pmod {256}$
$7x-5=256y$
$7x-256y=5$
Next, find the $gcd(7,256)$
$256=36*7+4$
$7=1*4+3$
$4=1*3+1$
$3=1*3 \Longrightarrow gcd(7,256)=1$
Then, find $x$ and $y$ in $7x-256y=5$
$1=4-3$
$1=256-36*7-(7-4)$
$1=256-36*7-7+(256-36*7)$
$1=256-37*7+256-36*7$
$1=7*(-73)+256*2$
$5=7*(-365)+256*10 \Longrightarrow x_0=-365, y_0=10$
Therefore, the solution to the Diophantine equation is
$\begin{equation}
  \begin{cases}
    x=-365+n*\frac{-256}{1}=-256n-365\\
    y=10-n*\frac{7}{1}=10-7n
  \end{cases}
\end{equation}$
Which in turn means that the solution to $7x\equiv5 \pmod {256}$ is
$-256n-365, n\in \mathbb{Z}$. But my answer sheet and WolframAlpha give the solution $x=256n+147$. What am I missing?

REPLY [1 votes]: we have to solve $$7x\equiv 5 \mod 256$$ this is equivalent to
$$x\equiv \frac{5}{7}\mod 256$$ and then we have $$x\equiv \frac{5+256+256+256+256}{7}=\frac{1029}{7}=147 \mod 256$$ thus we have $$x=147+256k$$ with $$\ k\in \mathbb{Z}$$


TITLE: Probability and genetics - Bayes' theorem
QUESTION [8 upvotes]: Britney can be homozygous $HH$ or heterozygous $Hh$ with equal probability.
Hemophilia is a mostly inherited genetic disorder. A test to detect a dominant allele $h$, responsible for the disorder, is carried out.
The test has $85\%$ reliability in heterozygous women (with $Hh$ genotype), that is, it successfully detects the presence of the allele $h$ in $85\%$ of the cases, while in homozygous women (with $HH$ genotype) it fails to detect $h$ in $1\%$ of the cases.
We want to calculate the following probabilities:
$P (\text{Britney}\,Hh | \text{test was positive})$
and
$P(\text{Britney}\,HH | \text{test was negative})$
I am not sure for the correct interpretation of the question, as I had to translate some terms I am not familiar with.
With the little knowledge I have on statistics, I will make an attempt:

Prior probability Britney is homozygous or heterozygous $P(ΗΗ)= P(Hh) = 0.5$

$$P(E|Hh)= \text{Probability of a Positive Test Result given Britney is Heterozygous} = 0.85\\
\text{So, we have}\\
P(E|HH)= \text{Probability of a Positive Test Result given Britney is Homozygous} = 0.15$$
We want $$P(HH|E) = \text{Probability of Britney being Heterozygous given the test yields a Positive Result}$$
We also want $$P(Hh|E^c) = \text{Probability of Britney being Homozygous given the test yields a Negative Result}$$
So for a)
$$P(HH|E) = {P(E|HH) P(HH) \over P(E)} = {P(E|HH) P(HH) \over P(E|HH)P(HH) + P(E|{Hh}) P({Hh})}$$
and similarly for the second. Are these correct?
EDIT: Can you tell me if this is correct?
"$P(E|HH)= \text{Probability of a Positive Test Result given Britney is Homozygous} = 0.15$"
or is it
"$P(E|HH)= \text{Probability of a Negative Test Result given Britney is Heterozygous} = 0.15$"?

REPLY [0 votes]: By the law of total probability, $$P(Positive)=P(Positive|HH)P(HH)+P(Positive|Hh)P(Hh)=0.5\cdot0.99+0.5\cdot0.85=0.5(0.99+0.85)=0.5\cdot1.84=0.92$$ and so P(Negative)=0.08 (can also be calculated from the law of total probability).
(a)By Bayes Theorem, $$P(Hh|Positive)=\frac{P(Hh\cap Positive)}{P(Positive)}$$
$$=\frac{0.85\cdot 0.5}{0.92}=\frac{85}{184}≈0.4619=46.19\% $$
 Similarly, (b) By Bayes Theorem, $$P(HH|Negative)=\frac{P(HH\cap Negative)}{P(Negative)}$$
$$=\frac{0.01\cdot 0.5}{0.08}=\frac{1}{16}=0.0625=6.25\%$$


TITLE: For $y = 2f\left(0.5x+4\right)-3$, derive the equation of: $ f(x)=2x^2-3x+4. $
QUESTION [1 upvotes]: For $y = 2f\left(0.5x+4\right)-3$,
derive the equation of:
$$
f(x)=2x^2-3x+4.
$$
I don't really understand what this question is asking for. Any input would be greatly appreciated.

REPLY [2 votes]: I think that the (admittedly poorly worded) problem is asking for you to express $y$ in terms of $x$ given that $\displaystyle y=2\ f\left(\frac x 2 + 4\right)-3$ and $f(x)=2x^2-3x+4$.
In that case:
\begin{align}
y&=2\ f\left(\frac x 2 + 4\right) - 3\\
&=2\left(2\left(\frac x 2 + 4\right)^2 - 3 \left(\frac x 2 + 4\right)+4\right)-3\\
&=\dots
\end{align}


TITLE: Show that if $(\sigma^r)^i$ is an $n$-cycle, then $\sigma^r$ is an $n$-cycle
QUESTION [0 upvotes]: I'm trying to show that if the power of $\sigma$ is an $n$-cycle, then $\sigma$ itself is an $n$-cycle. This seems to be something that is privy to a proof by contradiction but I can't seem to see how.

REPLY [3 votes]: Let $\sigma = (123)(45)$. Then $\sigma^2 = (132)$ is a $3$-cycle but $\sigma$ is not a $3$-cycle.


TITLE: How to solve system of differential equations?
QUESTION [1 upvotes]: I would like to solve a system of differential equations
\begin{align*}
&x''(t) = -a_0(a_1 - bz'(t))\cos(wt), &&x(t_o)= 0,  &&x'(t_o)=0\\
&z''(t)= -a_0 bx'(t)\cos(wt), &&z(t_o) =0,  &&z'(t_o)= 0
\end{align*}
It reduces to a third order equation
$z'''(t) = a(1-cz'(t))\cos^2(wt)-\tan(wt) dz''(t), z(t_o)=0,z'(t_o)= 0$
I tried mathematica and matlab but they do not want to return analytical solution.
This is free electron in electromagnetic field.
If the field is complex mathematica find some solution. But the answer is also complex. Is it possible to get real Z for cos(wt) field out of it.
eqns = {z'''[t] == a*Exp[I*t*2*w]*(1 - z'[t]*c) + z''[t]*(I*w),
   z[t0] == 0, z'[t0] == 0};

soln = Real[DSolve[eqns, z, t][[1]]]

REPLY [2 votes]: $$x''(t) = -a_0(a_1 - bz'(t))\cos(wt),\ \ \ \  x(t_o)= 0,\ \ \ \ \  x'(t_o)=0$$
let $x'(t)=y(t) ,z'(t)=\beta(t)$
than we get
$$y'(t)=-a_0(a_1 - b\beta(t))\cos(wt)$$
the second equation converts to $$\beta'(t)= -a_0b y(t)\cos(wt) $$
i think it can be solved now
on solving and referring results from work of @okrzysik Solution of a system of linear odes
$$\beta(t) = A \cos\left(\frac{c \sin(\omega t)}{\omega}\right) + B \sin\left(\frac{c \sin(\omega t)}{\omega}\right) + \frac{d}{c^2} $$
and
$$y'(t)=(-a_0a_1\cos(wt)+a_0b A \cos\left(\frac{c \sin(\omega t)}{\omega}\right) \cos(wt)+ a_0Bb \sin\left(\frac{c \sin(\omega t)}{\omega}\right)\cos(wt) +a_0 \frac{bd}{c^2}\cos(wt))$$
on integrating

$$y(t)=\frac{1}{w}(a_0 \frac{bd}{c^2}-a_0a_1)\sin(wt)+a_0bA\frac{w^2}{c}\sin(\frac{c\sin(wt)}{w})-a_0Bb\frac{w^2}{c}\cos(\frac{c\sin(wt)}{w})+K$$

now $z(t),x(t)$ could be calculated from $\beta(t),y(t)$

$$z(t) = A \int \cos\left(\frac{c \sin(\omega t)}{\omega}\right) dt+ B \int\sin\left(\frac{c \sin(\omega t)}{\omega}\right)dt +\int \frac{d}{c^2} dt$$


TITLE: Calculating limits of areas of circle
QUESTION [1 upvotes]: If $r$ is the radius of circle then I calculated $f(t)$ and $g(t)$ to be
$$f(t)=\frac{1}{2}r^2t-\frac{1}{2}r^2\sin t=\frac{1}{2}r^2(t-\sin t)$$
$$AB^2=4r^2\sin^2 \frac{t}{2}= 2AC^2+2AC^2\cos(\pi-t)$$
$$g(t)=\frac{1}{2}AC^2\sin (\pi-t)-\frac{1}{2}r^2(t-\sin t )= \frac{r^2\sin^2 \frac{t}{2}}{1-\cos t}-\frac{1}{2}r^2(t-\sin t)$$
$$\frac{f(t)}{g(t)} = \frac{1}{\frac{2\sin^2 \frac{t}{2}\sin t}{(1-\cos t)(t-\sin t)}-1}$$
Thus $$\ \lim_{x\rightarrow 0 } \frac{f(t)}{g(t)} = 0$$
Is this working correct? Intuitively we can see that as $t$ approaches $0$, line segment $AB$ becomes smaller and thus $f(t)$ approaches $0$ and $g(t)$ approaches the area $ABC$  giving a limit of $0$ which is my answer.

REPLY [2 votes]: Alternatively:
$$\begin{align}
f(t)=&\frac{1}{2}r^2t-\frac{1}{2}r^2\sin{t}=\frac{1}{2}r^2(t-\sin t). \\
AC=&r\tan{\frac{t}{2}}. \\
S_{ABC}=&\frac{1}{2}AC^2\sin{(\pi-t)}=\frac{1}{2}r^2\tan^2{\frac{t}{2}}\sin{t}=\frac{1}{2}r^2\frac{1-\cos t}{1+\cos t}\sin t. \\
g(t)=&S_{ABC}-f(t)=\frac{1}{2}r^2(\frac{1-\cos t}{1+\cos t}\sin t-t+\sin t)= \\
=&\frac{1}{2}r^2\frac{2\sin t-t(1+\cos t)}{1+\cos t}\\
\lim_\limits{t\to 0} \frac{f(t)}{g(t)}=&\lim_\limits{t\to 0} \frac{(t-\sin{t})(1+\cos t)}{2\sin t-t(1+\cos t)}=2.\end{align}$$


TITLE: Unlimited balls to $t$ cells with conditions
QUESTION [2 upvotes]: Assuming an unlimited number of balls to be put into $t$ cells, such that each cell doesn't contain more than 2 balls - an empty cell will contain to balls, and a full cell will contain 2 balls. In how many ways can we put the balls in the cells such that the number of full cells will be even and the numer of empty cells will be odd ?

Attempt -
I thought about doing a double sigma, but i am not sure how to approach the problem and if my counting is even right -
$$\sum_{k=0}^t \sum_{n=0}^t \binom{t}{2k+1}\binom{t}{2n}$$
I know that this is not true, What do you think ?

REPLY [1 votes]: The simplest form of the answer I could come up with is:

$$\tfrac{1}{4}(3^t-(-1)^t)\tag{Answer}$$

assuming the cells are distinct but the balls are not.
Which I arrive at through the exponential generating function
$$e^x\sinh(x)\cosh(x)\tag{1}$$
We see that
$$\sinh(x)=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots$$
has even powers of $x$ and so coefficients of $x^k/k!$ represent the possible number of ways of having even full cells.
Then
$$\cosh(x)=\frac{x^1}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots$$
has odd powers of $x$ and so represents the number of ways of having odd empty cells.
Finally
$$e^x=1+\frac{x^1}{1!}+\frac{x^2}{2!}+\cdots$$
represents the possible numbers of ways of having any number of cells with a single ball.
The coefficient of $x^t/t!$ in $e^x\sinh(x)\cosh(x)$ therefore gives the required count.
Well, since $\sinh(x)=(e^x-e^{-x})/2$ and $\cosh(x)=(e^x+e^{-x})/2$ our exponential generating function $(1)$ becomes:
$$\begin{align}e^x\sinh(x)\cosh(x)&=\tfrac{1}{4}e^x(e^x-e^{-x})(e^x+e^{-x})
\\ &=\tfrac{1}{4}(e^{3x}-e^{-x})\end{align}$$
taking the $x^t/t!$ coefficient:
$$\begin{align}[x^t/t!]e^x\sinh(x)\cosh(x)&=[x^t/t!]\tfrac{1}{4}(e^{3x}-e^{-x})\\&=\tfrac{1}{4}(3^t-(-1)^t)\end{align}$$
which is our result at the top.


TITLE: Closed but not rational points of a cubic
QUESTION [6 upvotes]: In Mumford's Red Book of Varieties and Schemes, page 102, he gave the example of the closed but not rational points of the cubic $y^2=x^3-x$ on the real field : I have some difficulty to recover by elementary methods the figure he traced. Especially, he seems to imply that these closed points (where their residue field is the complex field) formed a set homeomorphic to the region $y^2>x^3-x$ in the real plane (that is why he depicted a cylinder in the projective plane). Can somebody give me a simple explanation ? (I suppose the maximal ideals of the spectrum of the algebra defined by the cubic have to be parametrized the right way ?)

REPLY [0 votes]: The question has been answered on MathOverflow. The right way to parametrize the maximal ideals was just to consider those containing $(ax+by-1)$ and impose that the intersection of this line with the cubic has only one point (so that a discriminant involving parameters $(a,b)$ is negative). Then one finds a cubic region looking like the cylinder I was looking for in the projective. The flaw of my approach was that I was parametrizing by projecting on the wrong real plane $(p,q)$ instead of $(a,b)$ because I found the equations easier being of degree 2. But then I could not grasp the right picture (because I crushed the component corresponding to the second coordinate $y$ therefore seeing only a disk in the projective) ! Silly me ...


text:
\section{Global landscape analysis under deterministic conditions}

As mentioned, the proof of Theorem \ref{thm:main_rand} and Proposition \ref{prop:rand_localmin}, will be based on deterministic conditions on
the weights of the network and the noise matrix.
In particular we will consider the minimization problem \eqref{eq:minM} with: \[M = G(\xstar)G(\xstar)^\T + H,\] for an unknown symmetric matrix $H \in \R^{n \times n}$ and nonzero $\xstar \in \R^k$.

Recall the definition \ref{def:WDC} of the WDC.
Below we will say that a $d$-layer generative network $G$ of the form \eqref{eq:Gx}, satisfies the WDC with constant $\eps>0$ if every weight matrix $W_i$ has the WDC with constant
$\eps$ for all $i = 1, \dots d$.

We can now describe the landscape of the minimization problem \eqref{eq:minM} in a deterministic settings.
\begin{thm}\label{thm:dir_deriv}

	Consider a generative network $G: \R^k \to \R^n$ as in \eqref{eq:Gx} and
	the minimization problem \eqref{eq:minM} with unknown nonzero $\xstar$ and symmetric $H$.
	Fix $\eps > 0$ such that $K_1 d^{16} \sqrt{\eps} \leq 1$ and let $d \geq 2$.
	Suppose that $G$ satisfies the WDC with constant $\eps$ and assume that:
	\begin{equation}\label{eq:noise}
	\|\Lambda_x^\T H \Lambda_x \|_2 \leq \frac{\omega}{2^d}  \qquad \text{for all}\; x \in \R^k,
	\end{equation}
	with $2^d d^{12} w \leq K_2 \| \xstar \|^2$ and $K_2 < 1$.

	Then for all $x \in \R^k$:
	\begin{itemize}
		\item if $x \notin \mathcal{B}(\xstar, r_+)~\cup~\mathcal{B}(-\rho_d \xstar, r_-)~\cup~\{0\}$ and \\$v_x \in \pa f(x)$:
		\[
		D_{-v_x} f(x) < 0
		\]
		where
		\[
		r_+ = K_3 (d^4 {\eps^{1/2}} + 2^d \omega  \|\xstar\|_2^{-2}) d^{10} \|\xstar\|_2,
		\]
		and
		\[
		r_- =  K_4 (d^2 {\eps}^{1/4} + 2^{d/2} \omega^{1/2} \|\xstar\|_2^{-1}) d^{10}  \|\xstar\|
		\]
		\item if $x \in \mathcal{B}(0,  \|\xstar\|_2/16 \pi) \backslash \{0\}$  and $v_x \in \pa f(x)$ then
		\[\langle x, v_x\rangle < 0\]
		while if $x = 0$ and $v \in \mathcal{S}^{k-1}$ then
		\[D_{-v} f(0) = 0\]
	\end{itemize}
	Here $\rho_d$ is a positive number that converges to 1 as $d \to \infty$ and $K_1, \dots, K_4$ are universal constants.
\end{thm}

Similarly, below we give the deterministic version of Proposition \ref{prop:rand_localmin}.
\begin{prop}\label{prop:local_min}
	Under the assumptions of Theorem \ref{thm:dir_deriv}, for any $\phi_d \in [\rho_d, 1]$, it holds that:
	\begin{equation}\label{eq:localmin}
	f(x) < f(y)
	\end{equation}
	for all $x \in \mathcal{B}(\phi_d \xstar, \varrho \|\xstar\| d^{-12})$ and $y \in \mathcal{B}(- \phi_d \xstar, \varrho  \|\xstar\| d^{-12})$ where $\varrho<1$ is a universal constant.
\end{prop}

The rest of the paper is organized as follows.
After summarizing the notation used throughout the paper in
Section \ref{sec:Notation} and deriving concentration results for the subgradients from the WDC in Section \ref{subsec:prelim}, we give the proof of Theorem \ref{thm:dir_deriv} in Section \ref{sec:proof_det}. In Section
\ref{sec:proof_loc_min} we prove Proposition \ref{prop:local_min}, while Section
\ref{sec:supp_proof} contains the proofs of supplementary lemmas needed in the main results.
Finally in Section \ref{sec:rand_proofs}, we derive the main Theorem \ref{thm:main_rand} and Proposition \ref{prop:local_min} from the corresponding deterministic ones by
controlling the noise terms and recalling a result of \cite{hand2017global} which shows that the WDC holds with high probability.

\subsection{Notation}\label{sec:Notation}

We now collect the notation that is used throughout the paper.  For any real number $a$, let $\relu(a) = \max(a, 0)$ and for any vector $v \in \R^n$, denote the entrywise application of $\relu$ as $\relu(v)$ . Let $\diag(W x > 0)$ be the diagonal matrix with $i$-th diagonal element equal to 1 if $(Wx)_i > 0$ and 0 otherwise.
For any vector $x$ we denote with $\|x\|$ its Euclidean norm
and for any matrix  $A$ we denote with $\|A\|$ its spectral norm and with $\|A\|_F$ its Frobenius norm. The euclidean inner product between two vectors $a$ and $b$ is $\langle a,b \rangle$, while for
two matrices $A$ and $B$ their Frobenius inner product will be denoted by $\langle A, B\rangle_F$.
For any nonzero vector $x \in \R^n$, let $\hat{x} = x/\|x\|$.  For a set $S$ we will write $|S|$ for its cardinality and $S^c$ for its complement.
Let $\mathcal{B}(x,r)$ be the Euclidean ball of radius $r$ centered at $x$, and $\mathcal{S}^{k-1}$ be the unit sphere in $\R^k$.
With $D_v f(x)$ we denote the (normalized) one-sided directional derivative of $f$ in direction $v$: $D_{v} f(x) = \lim_{t \to 0} \frac{f(x + t v) - f(x)}{t \|v\|_2}$.
We will write $\gamma = \Omega(\delta)$ to mean that
there exists a positive constant $C$ such that $\gamma \geq C \delta$ and similarly $\gamma = \bigO(\delta)$ if $\gamma \leq C \delta$. Additionally we will use $a = b + O_1(\delta)$ when
$\|a - b\| \leq \delta$, where the norm is understood to be the absolute value for scalars, the Euclidean norm for vectors and the spectral norm for matrices.

\subsection{Preliminaries}\label{subsec:prelim}

At a differentiable point, the gradient of $f$ is given by \eqref{eq:gradx} and will be denoted by $\vtilde_x$ and .
By the WDC, $\vtilde_x$ concentrates up to the
noise level around the direction $h_x \in \R^k$:
\begin{equation} \label{eq:h_def}
h_x := \big[ \frac{1}{2^{2d}} x x^\T - \htilde_{x,\xstar} \htilde_{x,\xstar}^\T \big] x,
\end{equation}
where $\htilde_{x,\xstar}$ is defined below and
is a continuous function of $x$ and $\xstar$. The vector field  $\htilde_{x,\xstar}$ depends on a function that controls how the
angles are contracted by the deep network, and defined as:
\begin{equation}\label{eq:def_g}
g(\theta) := \cos^{-1}\big( \frac{(\pi - \theta) \cos \theta + \sin \theta}{\pi} \big)
\end{equation}
With this definition we let $\htilde_{x,\xstar}$ be:
\[
\htilde_{x,\xstar} := \frac{1}{2^d} \big[ \big(\prod_{i=0}^{d-1} \frac{\pi - \bar{\theta}_i}{\pi} \big) \xstar + \sum_{i=1}^{d-1} \frac{\sin \bar{\theta}_i }{\pi}   \big(\prod_{j=i+1}^{d-1} \frac{\pi - \bar{\theta}_j}{\pi}\big) {\|\xstar\|} \hat{x} \big]
\]
where $\theta_i := g(\bar{\theta}_{i-1})$ for $g$ given by \eqref{eq:def_g} and $\theta_0 = \angle(x,y)$. For brevity of notation below we will use $\htilde_x = \htilde_{x,\xstar}$. For later convenience we also  define the following vectors:
\begin{equation*}
\begin{aligned}
p_x &:= \Lambda_x^\T \Lambda_x x; \\
q_x &:= \Lambda_x^\T \Lambda_\xstar  \xstar; \\
\vbar_x &:=  [p_x p_x^\T - q_x q_x^\T] \,x; \\
\eta_x &:= \Lambda_x^\T H \Lambda_x \, x.
\end{aligned}
\end{equation*}
and note that when $f$ is differentiable at $x$, then $\vtilde_x:= \nabla f(x) = \vbar_x - \eta_x$, in particular for zero noise $\vtilde_x = \vbar_x$.

We now observe the following facts.
\begin{lemma}[Lemma 8 in \cite{HV17}]\label{lemma:conctrWDC}
	Suppose that $d\geq 2$ and the WDC holds with $\eps < 1/(16 \pi d^2)^2$, then for all nonzero $x, \xstar \in \R^k$,
	\begin{align}
	\langle\Lambda_x x, \Lambda_\xstar \xstar \rangle &\geq \frac{1}{4 \pi} \frac{1}{2^d} \|x\|_2 \|\xstar\|, \label{eq:LxLy}\\
	\| \Lambda_x^\T \Lambda_\xstar \xstar - \htilde_{x,\xstar} \| &\leq 24 \frac{d^3 \sqrt{\eps}}{2^d} \|\xstar\|,  \; \text{and} \label{eq:htilde_conctr} \\
	\|\Lambda_x\|^2 \leq \frac{1}{2^d} (1 + 2 \eps)^d\leq \frac{1+ 4 \eps d}{2^d}  &\leq \frac{13}{12} \frac{1}{2^d} \label{eq:Lx_bound}.
	\end{align}
\end{lemma}
\begin{proof}
	The first two bounds can be found in \citep[Lemma 8]{HV17}. The third bound follows noticing that the WDC implies:
	\[
	\|\Lambda_x \|^2 \leq \Pi_{i=d}^1 \| W_{i,+,x} \|^2 \leq \frac{1}{2^d} (1 + 2 \eps)^d \leq \frac{1 + 4 \eps d}{2^d} \leq \frac{13}{12}\frac{1}{2^d}
	\]
	where we used $\log(1+z) \leq z$ and $e^{z}\leq (1 + 2 z)$ for all $0\leq z \leq 1$.
\end{proof}

The next lemma shows that the noiseless gradient $\vbar_x$, concentrates around $h_x$.
\begin{lemma}\label{lemma:conctr_grad1}
	Suppose $d\geq 2$ and the WDC holds with $\eps < 1/(16 \pi d^2)^2$, then for all nonzero $x, \xstar \in \R^k$:
	\[
	\|\vbar_x - h_x \| \leq 86 \frac{ d^4 \sqrt{\eps}}{2^{2d}} \max(\|\xstar\|^2, \| x\|^2) \|x\|
	\]
\end{lemma}

We now use the characterization of the Clarke subdifferential given in \eqref{eq:subdiff}, to derive a bound on the concentration of $v_x \in \pa f(x)$ around $h_x$ up to the noise level.
\begin{lemma}\label{lemma:conctr_grad2}
	Under the assumption of Lemma \ref{lemma:conctr_grad1}, and with $H$ satisfying \eqref{eq:noise}, for any $v_x \in \pa f(x)$:
	\[
	\|v_x - h_x \| \leq 86 \frac{ d^4 \sqrt{\eps}}{2^{2d}} \max(\|\xstar\|^2, \| x\|^2) \|x\| +   \frac{\omega}{2^{d}} \,  \| x\|
	\]
\end{lemma}


TITLE: How to find $r$ in an equation like this: $r^3= xr+y$
QUESTION [1 upvotes]: Can anyone give me an an idea how to solve this and find $r$, where $r^3= xr+y$ and $x$ and $y$ are known numbers?

REPLY [2 votes]: I'm sure there are more elegant methods, but one simple approach is to turn it into a polynomial in $r$ as such:
$$r^3 -xr - y = 0$$
and then apply the cubic formula (it's not so bad since there is no $r^2$ term) to obtain
$$r =
\sqrt[3]{\frac{y}{2} + \sqrt{\left(\frac{y}{2}\right)^2 + \left(-\frac{x}{3}\right)^3}} +
\sqrt[3]{\frac{y}{2} - \sqrt{\left(\frac{y}{2}\right)^2 + \left(-\frac{x}{3}\right)^3}}$$


TITLE: Why does bitshifting to the right work as division?
QUESTION [1 upvotes]: So I'm trying to understand why bitshifting integers to the right works as division.
Take the number 4200. If I shift it to the right by 1, it divides by 2.
If I shift it to the right by 2, it divides by 4.
If I shift it to the right by 3, it divides by 8.
Why is bitshifting by 1 the equivalent of dividing by 2?  And bitshifting by 2 is the equivalent of dividing by 4 etc.
I understand that it has something to do with the power of 2 and the binary system and the way I look at it is like so
Multiply 2 with the index at the power of 2 table
8 4 2 1

Let's say I wanted to bitshift by 3, I would then take what's on the 3rd index of the table which is the value 4, going from right to left, and multiply it by 2. hence why bitshifting to the right by 3 is the same as dividing by 8.
I don't understand why though, and I don't feel like that would be a good answer if I were to face this on a test. Where the question is.. "Why does it multiply by 8 if you bitshift the value to the right by 3"

REPLY [2 votes]: Let some number $x$ be given and assume it has binary representation:
$$
x=\cdots b_8b_4b_2b_1
$$
where $b_1,b_2,...\in\{0,1\}$ are the binary digits. Then $x$ can be translated into base 10 by multiplying the rows in the following table:
$$
\begin{array}{c|c}
\cdots & b_8 & b_4 & b_2 & b_1 \\
\hline
\cdots & 8 & 4 & 2 & 1
\end{array}
\longrightarrow x=\cdots + 8b_8+4b_4+2b_2+1b_1
$$
and bitshifting by $3$ would leave us with:
$$
\begin{array}{c|c}
\cdots & b_{64} & b_{32} & b_{16} & b_8 \\
\hline
\cdots & 8 & 4 & 2 & 1
\end{array}
\longrightarrow x=\cdots + 8b_{64}+4b_{32}+2b_{16}+1b_{8}
$$
More generally one can say that x>>3 replaces each term by mapping:
$$
2^n b_n\mapsto 2^{n-3}b_n = \frac{2^n b_n}{2^3} = \frac{2^n b_n}{8}
$$
and even more generally, the operation x>>k maps the terms as:
$$
2^n b_n\mapsto\frac{2^n b_n}{2^k}
$$

In any base, say $q$, we would have:
$$
x=\cdots d_{[q^3]}d_{[q^2]}d_{[q]}d_{[1]}
$$
where $d_i\in\{0,1,...,q-1\}$ and the table would be:
$$
\begin{array}{c|c}
\cdots & d_{[q^3]} & d_{[q^2]} & d_{[q]} & d_{[1]} \\
\hline
\cdots & q^3 & q^2 & q & 1
\end{array}
\longrightarrow x=\cdots + q^3 d_{[q^3]}+q^2 d_{[q^2]}+q d_{[q]}+1 d_{[1]}
$$
and digit shifting by $k$ places to the right would result in division by $q^k$ (and a floor operation since the rightmost digits drop off).


TITLE: Maximum of a function with parameter
QUESTION [0 upvotes]: can someone please tell me if I'm going in the right direction?

Find $\max_{x\in[-3, 3]} \{bx^2 - 3x + b^2\} $ where $b$ is a real parameter.

Here is how I reasoned: $[-3, 3]$ is a closed and bounded set, hence it's compact. By Weierstrass Theorem, being $f(x)$ a polynomial hence continuous in the whole real line and particularly in $[-3, 3]$, the existence of an absolute max / min in $[-3, 3]$ is guaranteed.
So now $f'(x) = 2bx - 3 = 0$ and its zeroes are given by $x_c = \frac{3}{2b}$
Now I thought I have to find $b$ such that $x_c \in [-3, 3]$ and I found that I need $b\in [-1/2, 1/2]$
That being said, I wanted to compare $f$ in the extrema of the interval and $f(x_c)$:
$$f(-3) = 9b + 6 + b^2$$
$$f(3) = 9b - 6 + b^2$$
$$f(x_c) = \frac{4b^3-9}{4b}$$
Reasoning Update
I thought to compare the images of the three points. I mean I did:
$$f(3) > f(-3)$$
This turned out to be never true hence $f(-3) > f(3)$ for all $x$ and for all $b$
In the same way I did
$$f(x_c) < f(-3)$$
And I found out that this is true for all $x$ and $b$.
Hence I thought the function starts from $-3$ in a high point, decreasing down to $x_c$ which then is a minimum, and increasing up to $3$.
Hence $-3$ and $+3$ are the max, but the absolute is at $-3$.
Am I right?

REPLY [0 votes]: Just one note: either typo $f(x) = bx^2 -3x + b$, or derivative is $f'(x) = 2bx = 0$.


TITLE: Gradient flows: convex potential vs. contractive flow?
QUESTION [1 upvotes]: Take a $\mathcal C^2$ potential $V:\mathbb R^d\to \mathbb R$, and assume that it is bounded from below (say $\min V=0$ for simplicity, so that $V\geq 0$).
Consider the autonomous gradient-flow
$$
\dot X_t=-\nabla V(X_t)
$$
and let $\Phi(t,X_0)$ be the corresponding flow.
It is well-known that if $V$ is $\lambda$-convex (i-e the Hessian $D^2V\geq \lambda Id$ in the sense of symmetric matrices) then the flow is exponentially $\lambda$-contractant,
$$
|\Phi(t,X_0)-\Phi(t,X_0')|\leq e^{-\lambda t}|X_0-X_0'|,
\qquad
\forall \, X_0,X_0'\in \mathbb R^d.
$$
In particular for $\lambda=0$ (convex potential) the flow is just nonexpanding.

Question: is this an equivalence? I-e is it true that if $V$ is smooth and $\Phi(t,.)$ is $1$-Lipschitz for all times then necessarily $V$ must be convex? I am also interested in the corresponding statement for $\lambda>0$, i-e if $\Phi(t,.)$ is $e^{-\lambda t}$-Lipschitz for all $t>0$ is it true that $D^2V\geq \lambda$?

Let me just add a few comments:

The implication "$D^2V\geq \lambda$ $\Rightarrow$ $\Phi(t,.)$ is $e^{-\lambda t}$-contractant" is classical and easy to prove. As should be clear from my question above, I am only interested in the converse implication.
I stated the problem in $\mathbb R^d$ and smooth potentials for simplicity, but in reality I'm interested in this kind of problems in infinite dimension, and in fact in the context of abstract gradient-flows in metric spaces. The point is that I want to prove that some potential $V$ is geodesically convex, assuming only that the generated flow is contractant. But I want to check that this is not a complete equivalence. For example sometimes it is easy to see that the flow map is well-behaved by pure "1st-order calculus" PDE arguments (I mean, taking just one derivative in time along solutions), but characterizing the convexity requires 2nd order calculus and is therefore more delicate to justify rigorously in infinite dimensions so the mutual implications between both concepts may not be totally clear
This is related to my previous posts:

Heat flow, decay of the Fisher information, and $\lambda$-displacement convexity
Universal decay rate of the Fisher information along the heat flow
improved regularization for $\lambda$-convex gradient flows

REPLY [2 votes]: It should be noticed that already on $R^d$ equipped with a non-Euclidean norm $\|.\|$ the answer to your question is no. Ohta-Sturm [1] proved the following: let $\lambda\in R$ and consider the classes of $\lambda$-convex functions on $R^d$ on one side and the class of functions whose gradient flows are $\lambda$-contractive (they call these functions skew-convex). Then these classes coincide if and only if the norm $\|.\|$ (which is relevant for the notion of gradient flow) comes from a scalar product.
This shows that "convexity" and "contractivity" are really related only on Riemannian-like world, whereas on Finsler-like ones they are different concepts.
In particular, the answer in general metric spaces is no.
However, you may have better luck in spaces which are Hilbert-behaved on small scales (whatever this means). Judging by the other questions that you linked it seems that you are particularly interested in the Wasserstein space built over a Riemannian manifold. In this case, the paper by Otto-Westdickenberg [2] might be the reference you are looking for. They basically make the same argument Willie Wong gave above in $R^d$ but in $(P_2(M),W_2)$.
Inspired by [2], Daneri-Savare' [3] proved that if you interpret gradient flows in the $EVI_\lambda$ sense (a condition that implies $\lambda$-contractivity but that in practical situation one is often able to obtain if s/he is able to get contractivity - but beware of the results in [1]), then if a functional admits gradient flows in such sense, it must be $\lambda$-convex. This holds in arbitrary metric spaces.
[1] https://arxiv.org/abs/1009.2312
[2] http://www.instmath.rwth-aachen.de/~mwest/files/OttoWest.pdf
[3] https://arxiv.org/abs/0801.2455

EDIT
oh, small world indeed :) Let me add some comments:

one of the greatest intuitions in optimal transport is Otto’s interpretation of $(P_2(M),W_2)$ (here $M$ is a Riemannian manifold) as a sort of "infinite dimensional Riemannian manifold" (this answers your question). Quotation marks are needed because this is not really a Riemannian manifold in any reasonable sense (not even a Hilbert manifold), but still it resembles it a lot. This intuition drove the research on optimal transport (and in particular on gradient flows over the Wasserstein space) in the last 20 years, thus my advice is that if you are not familiar with this, try to build some intuition for it.

Yes, EVI is stronger than contractivity (as said above, it implies both contractivity and convexity). Now, the question "how the EVI formalism means Riemannian on small scale" is of course tricky as nobody knows what "Riemannian on small scale" means. Still, let me mention some results pointing in this direction:

[4] shows that if we have many EVIs in a Banach space then the space is Hilbert
[5] shows that gradient flows of convex functionals on CAT(k) spaces satisfy the EVI. Thus it goes the other way around by showing how to derive the EVI from some geometric property of the space, but it is interesting to see what is the key property used. They call it "commutativity of the distance" and it is a nice exercise to check that a Banach space is "commutative" in this sense if and only if it is Hilbert.
[4] https://www.sciencedirect.com/science/article/pii/S0022247X11006391
[5] https://www.researchgate.net/publication/267983274_Gradient_flows_and_a_Trotter--Kato_formula_of_semi-convex_functions_on_CAT1-spaces


TITLE: Finding the longest path between two nodes in a bidirectional unweighted graph
QUESTION [5 upvotes]: I'm looking for an algorithm to find the longest path between two nodes in a bidirectional, unweighted, cyclic graph.
The path must not have repeated vertices (otherwise the path would be infinite of course).
Would someone point me a to a good one (site or explain)?
The graph will be sparse.
Thanks for any help!

REPLY [5 votes]: You can solve your problem in $O(n^2 2^n)$ on a graph with $n$ vertices by dynamic programming. Let $G=(V,E)$ be an undirected graph with edge weights $d_{uv}$. Let $L(v,S)$ be the length of the longest path from some fixed vertex $s$ to vertex $v$, which visits no vertex in $S$. $L$ satisfies
$$L(v,S)=\begin{cases}
\max_{w\in N(v)\setminus S} d_{vw}+L(w,S\cup\{w\}) & v\neq s\\
0 & \text{otherwise}
\end{cases}\mathrm{,}$$
where $N(v)$ is the set of $v$'s neighbors. (Define the empty $\max$ to be $-\infty$.) Then the longest path between $s$ and $v$ has length $L(v,\{v\})$.


TITLE: What are the dynamics of an atom and photon, as the atom absorbs the photon in the quantum mechanical picture?
QUESTION [2 upvotes]: Atoms can absorb photons, and when they do, an electron "orbiting" that atom moves up an energy level. I was wondering what the dynamics of this interaction was? Precisely how is the photon absorbed, from a wave function perspective?
My mental picture is that the wave function for the photon would have to go to zero at the end of the interaction (since it has been absorbed by the atom), and the wavefunction for the atom (lets say hydrogen for simplicity) would have to change to the wavefunction for excited hydrogen.
This is just a vague picture though, and I was wondering if anyone had done the mathematics of this interaction, and whether anyone had made a physically correct animation of it. What does the dynamics of an atom absorbing a photon look like?

REPLY [1 votes]: Let's start by looking at the behavior of an atom irradiated by a resonant electromagnetic wave of constant amplitude and frequency $\omega$. For simplicity, let's use hydrogen.
Classical electric field
The electric field polarizes the atom by moving the electron along the axis of polarization. To appropriately account for the discrete energy eigenstates of the electron ($|1s\rangle$, $|2s\rangle$, $|2p\rangle$, etc.) we need to treat it quantum mechanically. So instead of a point particle we need to describe it by its wavefunction. In the ground state it occupies a $1s$ orbital.
If you, for example, excite it at the frequency resonant with the $1s \to 2p_x$ transistion, the wavefunction describing the electron is displaced by the electic field along the $x$ axis. It can then be described by a superposition of the wavefunctions associated with the $1s$ and $2p_x$ orbitals.
$$\left| \Psi(t) \right\rangle = \alpha(t) \left| 1s \right\rangle + \beta(t) e^{-i \omega t} \left| 2p_x \right\rangle$$
After some time the electron will be fully in the $\left| 2p_x \right\rangle$ state. Driving it further at the same frequency $\omega$ will not inrease its energy (as expected from a harmonic oscillator), but transition it back to the ground state. This is in line with how Einstein described stimulated emission in his famous 1917 paper Zur Quantentheorie der Strahlung, Phys. Z. 18 121-128 (1917). In §2b) he wrote:
If a Planck resonator [the atom] is in a radiation field, the energy of the resonator can be changed by the transfer of energy from the electromagnetic field to the resonator; this energy can be positive or negative depending on the phases of the resonator and of the oscillating field.
Better than any wordy description is a visualization of the wavefunctions, like this applet. I got a pretty good intuition for this process by just watching the electron undergoing many Rabi cycles.
The movement of the electron creates an electric field by itself, which interferes with the incident beam. On the transmission side this interference is destructive, so that a weak, strongly focused beam can be completely blocked.
Single photon
Since a single photon holds only a finite amount of energy you need to care about its spatial extend. Typically, single photons are created by other atoms, which in free space emit in all directions. For simplicity, let's not care about this and assume that we managed to transform its emission pattern into a Gaussian beam focused on our observed atom.
The temporal envelope of a photon created by spontaneous emission is a decaying exponential, but the excitation probability is highest, when it's a rising exponential. In fact, if the photon temporally and spatially matches a time-reversed spontaneously emitted photon it would be absorbed with a probability of $100\,\%$. In that case the photon is completely gone at the moment the absorption is finished.
$$\left| 1s \right\rangle_{\text{electron}} \left| 1 \right\rangle_{\text{photon}} \rightarrow \left| 2p_x \right\rangle_{\text{electron}} \left| 0 \right\rangle_{\text{photon}}$$
The more realistic case is that the photon does not fulfill the previous conditions and therefore is only partially absorbed, so that the final state is a superposition of the photon being absorbed and having passed the atom:
$$\alpha \, \left| 1s \right\rangle_{\text{electron}} \left| 1 \right\rangle_{\text{photon}} + \beta \, \left| 2p_x \right\rangle_{\text{electron}} \left| 0 \right\rangle_{\text{photon}}$$
One can increase the interaction efficiency $\beta$ for non-ideal photon shapes by embedding the atom in a suitable environment, for example in a cavity.
The latter superposition can be collapsed by a measurement. For example if you place a detector after the atom and you detect a photon you know that it must have passed the atom. Since atom and photon are entangled it also affects the state of the atom. It will be completely in the $| 1s \rangle$ state then. Else, if you detected no photon (and unrealistically made sure that you would inevitably detect one if it was there) the atom would end up completely in the excited state $| 2p_x \rangle$.