TITLE: Inverse of matrix with QR method
QUESTION [0 upvotes]: What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.

REPLY [0 votes]: Calculating the $QR$ decomposition has complexity $O(n^3)$, after which $A = QR$ can be inverted into $R^{-1} Q^T$ also by $O(n^3)$ operations. In many of these algorithms, it is not the complexity that is important, but rather the numerical stability. It is well-known that first decomposing into $QR$ before inverting provides greater stability.


TITLE: Is the forgetful functor $\mathrm{Mod}_R \mathrm{Sp} \rightarrow \mathrm{Sp}$ faithful?
QUESTION [9 upvotes]: $\DeclareMathOperator{\Sp}{\mathrm{Sp}}$I am taking a special case $\Sp$ here, mainly because it has nice categorical properties.
Let $R$ be an $E_\infty$-ring spectrum. In Higher Algebra, Lurie proves we have a forgetful functor (part of monadic adjunction)
$$ U_R:\operatorname{Mod}_R(\Sp) \rightarrow \Sp$$
where $\Sp$ is in the $\infty$-category of spectra.
$U_R$ reflects equivalences. But is $U_R$ faithful in the sense that that the induced map of
$$Map(x,y)\rightarrow Map(U_Rx,U_Ry)$$
mapping spaces is $-1$-truncated in the $\infty$-category of spaces. i.e. the homotopy fibers are $-1$-truncated.

One categorically, $U$ is faithful in many cases, i.e. if we replace $\Sp$ with $\mathrm{Ab}$.
Perhaps the answer is false in $\infty$-categories.
I'd like to understand what goes wrong. Some comments on the following would be helpful:

A counter example where $U_R$ is not faithful. (i.e. is it faithful when $R=H\Bbb Z$? )
A brief/reference explanation for what accounts of this.

REPLY [13 votes]: $U_R$ obviously preserves delooping, so if that were the case, because $\pi_0 map(X,Y) = \pi_1 map(X, \Sigma Y)$, you would also get an isomorphism on $\pi_0$, so an equivalence of mapping spaces.
In other words, $U_R$ is faithful if and only if it is fully faithful. But now for a map of ring spectra $R\to S$, the forgetful $Mod_S \to Mod_R$ is fully faithful if and only if $R\to S$ is an epimorphism of ring spectra (good examples are localizations - be careful that classical examples such as $R\to R/I$ for a usual ring $R$ tend to fail).
This is to say that "being an $S$-module" becomes a property of an $R$-module, rather than additional structure - so of course you can expect that to be very rare.
In your example of $H\mathbb Z$, it doesn't hold at all - you can for instance detect it on the level of the ring of stable cohomology operations of singular cohomology, which is bigger than just $\mathbb Z$ (look at the (co)homology of Eilenberg-MacLane spaces)

REPLY [9 votes]: In general, the functor $U_R$ does not induce isomorphisms on higher homotopy groups of mapping spaces. Let $R=H(\mathbf{Z}/2)$.
Then $\pi_*(map(R,R))$ is the Steenrod algebra $\mathcal{A}^*$ where $map$ denotes the mapping spectrum.
The mapping spectrum $map(R,R)$ therefore has non-zero homotopy groups in negative degrees and differs from the mapping spectrum of $R$-module maps from $R$ to itself, which is just $R$ again, whose homotopy groups consist of $\mathbf{Z}/2$ concentrated in degree zero.
To see this difference directly in terms of mapping spaces as opposed to mapping spectra, we consider maps from $R$ to deloopings of $R$. For example,
$$\pi_1(Map_{R-Mod}(R, R[2])) \cong \pi_0(Map_{R-Mod}(R, \Omega R[2])) \cong \pi_0(Map_{R-Mod}(R, R[1])) \cong \mathrm{Ext}^1_R(R,R) = 0$$
but
$$\pi_1(Map_{Sp}(R,R[2])) \cong \pi_0(Map_{Sp}(R, \Omega R[2])) \cong \pi_0(Map_{Sp}(R,R[1]))  = \mathcal{A}^1 \cong \mathbf{Z}/2$$
so the induced map on $\pi_1$ is not surjective.


TITLE: Prove projection of $v$ onto a subspace is the one with minmum distance to $v$
QUESTION [3 upvotes]: Let $V$ be a vector space over field $F$, and $V$ can be decomposed as a direct sum $V = {V_1} \oplus {V_2}$ of two subspaces $V_1$ and $V_2$, then any vector $\bf v$ can be uniquely written as ${\bf v}={\bf v}_1+{\bf v}_2$ for some ${\bf v}_1\in V_1$, ${\bf v}_2\in V_2$. We define ${\bf v}_1$ as the projection of $\bf v$ into subspace $V_1$, denoted by ${\text{pro}}{{\text{j}}_{{V_1}}}{\mathbf{v}} = {{\mathbf{v}}_1}$.
The projection is unique since the direct sum decomposition of $\bf v$ is unique.
My question is how to prove

${\text{pro}}{{\text{j}}_{{V_1}}}{\mathbf{v}} = {\arg _{\mathbf{u}}}\mathop {\min }\limits_{{\mathbf{u}} \in {V_1}} \left\| {{\mathbf{u}} - {\mathbf{v}}} \right\|$, where $\|\|$ is any norm. In plain words, ${\text{pro}}{{\text{j}}_{{V_1}}}{\mathbf{v}}$ is the vector in $V_1$ that is nearest to $\bf v$ w.r.t. any norm.

I think the proof should not be hard. but an attempt of using triangular inequality does not seem to give me anything,
$\left\| {{\mathbf{u}} - {\mathbf{v}}} \right\| = \left\| {{\mathbf{u}} - {{\mathbf{v}}_1} - {{\mathbf{v}}_2}} \right\| \leqslant \left\| {{\mathbf{u}} - {{\mathbf{v}}_1}} \right\| + \left\| {{{\mathbf{v}}_2}} \right\|$
Thanks!

REPLY [1 votes]: It is not true that if $V = V_1 \oplus V_2$, then ${\operatorname{proj}_{{V_1}}}{\mathbf{v}} = {\arg _{\mathbf{u}}}\mathop {\min }\limits_{{\mathbf{u}} \in {V_1}} \left\| {{\mathbf{u}} - {\mathbf{v}}} \right\|$.  As a counterexample: take $\|\cdot\|$ to be the typical Euclidean norm (i.e. the "$\ell^2$ norm").  We may say that $V = \Bbb R^2$ can be decomposed as $V_1 \oplus V_2$ where $V_1 = \operatorname{span}\{(1,0)\}$ and $V_2 = \operatorname{span}\{(1,1)\}$ (so $V_1$ is the $x$-axis and $V_2$ the line $y = x$).
We find, for instance, that $\operatorname{proj}_{{V_1}}(0,1) = (-1,0)$ since $(0,1) = (-1,0) + (1,1)$.  However, it is clear that $(0,0) \in V_1$ is closer to $(0,1)$ than the so-called "projection".


text:
\begin{document}

\title{Almost symmetric  numerical semigroups with given Frobenius number and type}

\author{M.B. Branco}
\address{Universidade de \'Evora\newline
\indent Departamento de Matem\'atica\newline
\indent 7000 \'Evora, Portugal}
\email{mbb@uevora.pt}

\author{I. Ojeda}
\address{Universidad de Extremadura\newline
\indent Departamento de Matem\'aticas\newline
\indent E-06071 Badajoz, Spain}
\email{ojedamc@unex.es}

\author{J.C. Rosales}
\address{Universidad de Granada\newline
\indent Departamento de \'Algebra\newline
\indent E-18071 Granada, Spain}
\email{jrosales@ugr.es}

\thanks{The first author is supported by the project FCT PTDC/MAT/73544/2006). The second author was partially supported by the research groups FQM-024 (Junta de Extremadura/FEDER funds) and by the project MTM2015-65764-C3-1-P (MINECO/FEDER, UE).
The third author was partially supported by the research groups FQM-343 FQM-5849 (Junta de Andalucia/Feder) and by the project  MTM2014-55367-P (MINECO/FEDER, UE. 2010 Mathematics Subject Classification: 20M14, 11D07.}

\date{\today}
\subjclass[2010]{20M14, 20M25.}
\keywords{\em Almost symmetric numerical semigroup, irreducible numerical semigroup, genus, Frobenius number, type.}

\begin{abstract}
We give two algorithmic procedures to compute the whole set of almost symmetric numerical semigroups with fixed Frobenius number and type, and the whole set of almost symmetric numerical semigroups with fixed Frobenius number. Our algorithms allow to compute the whole set of almost symmetric numerical semigroups with fixed Frobenius number with similar or even higher efficiency that the known ones. They have been implemented in the GAP (\cite{GAP}) package \texttt{NumericalSgps} (\cite{numericalsgps}).
\end{abstract}

\maketitle
\pagestyle{myheadings}
\markboth{{M. B.} Branco \and I. Ojeda \and {J. C.} Rosales}{Almost symmetric numerical semigroups}

\section{Introduction}

Let $\mathbb{Z}$ and $\mathbb{N}$ denote the set of integers and nonnegative integers, respectively. A \textbf{numerical semigroup} is a subset $S$ of $\mathbb{N}$ that is closed under addition, contains the zero element and has finite complement in $\mathbb{N}$, that is, $\mathbb{N} \setminus S$ is a finite set.

Given a nonempty subset $A$ of $\mathbb{N}$, we write $\langle A \rangle$ for the submonoid of $\mathbb{N}$ generated by $A$, that is, \[\langle A \rangle := \Big\{ \sum_{finite} n a \mid n \in \mathbb{N}, a \in A\Big\}\]

It is well known that $\left\langle A\right\rangle$ is a numerical semigroup if and only if $\gcd\left(A\right)=1$ (see \cite[Lemma 2.1]{libro}) .  If $S$ is a numerical semigroup and $S=\left\langle A\right\rangle$ then  we say that $A$ is a \textbf{system of generators} of $S$.  Furthermore if $S\neq \left\langle A'\right\rangle$ for every $A' \varsubsetneq A$, then we say that $A$ is a \textbf{minimal system of generators} of $S$. It is also known that every numerical semigroup admits a unique finite minimal system of generators (\cite[Lemma 2.7]{libro}). Hence, if $S$ is a numerical semigroup, we write $\mathrm{msg}(S)$ for the  minimal system of generators of $S$.

Here and in the following $S$ will denote a numerical semigroup.

The \textbf{Frobenius number} of $S$ is the largest integer not belonging to $S$ and it is denoted by $\mathrm{F}(S)$. A numerical semigroup is irreducible if it cannot be expressed as the intersection of two numerical semigroups properly containing it. A numerical semigroup is said to be \textbf{symmetric} (\textbf{pseudo-symmetric}, resp.) if it is irreducible and its Frobenius number is odd (even, resp).

An integer $x\in \mathbb{Z}\setminus S$ is called a \textbf{pseudo-Frobenius number} if $x+S\setminus\{0\}\subseteq S$ (see \cite{JPAA}). The set of pseudo-Frobenius number of $S$ is denoted by $\mathrm{PF}(S)$. The type of the semigroup, denoted by $\mathrm{t}(S)$, is the cardinality of $\mathrm{PF}(S)$ and it was introduced in  \cite{froberg}.

As a consequence of \cite[Corollary 4.11 and 4.16 ]{libro}, we have the following result.

\begin{lemma}\label{2}
If $S$ is a numerical semigroup, then:
\begin{enumerate}[ (a)]
  \item $S$ is symmetric if and only if $\mathrm{PF}(S)=\big\{\mathrm{F}(S)\big\}$.
  \item  $S$ is pseudo symmetric if only if $\mathrm{PF}(S)=\big\{\mathrm{F}(S),\frac{\mathrm{F}(S)}{2}\big\}$.
\end{enumerate}
\end{lemma}

Observe that if $S$ is an irreducible numerical semigroups then $\mathrm{t}(S)\in\{1,2\}$ and we have that $\mathrm{t}(S)=1$ if and only if $\mathrm{F}(S)$ is odd, equivalently if $S$ is symmetric.

The elements in $\mathbb{N}\setminus S$ are called the \textbf{gaps} of $S$ and the cardinality of the set of gaps of $S$, $\mathrm{g}(S)$, is known as the \textbf{genus} of $S$. Following the terminology of \cite{jager} (see also \cite{barucci-froberg}) the elements in $$\mathrm{N}(S) := \{x \in \mathbb{N} \setminus S \mid \mathrm{F}(S)-x\in S\}$$ are called \textbf{gaps of the first type} and the remaining gaps are called \textbf{gaps of the second type}. Set of gaps of the second type is denoted $\mathrm{L}(S)$. By \cite[Proposition 3.4]{libro}, one has that if $S$ is symmetric (pseudo-symmetric, resp.) then $\mathrm{L}(S) = \varnothing$ ($\mathrm{L}(S) = \{\mathrm{F}(S)/2 \}$, resp.).

\begin{definition}
A numerical semigroup $S$ is \textbf{almost symmetric} (AS-symme\-tric, for short) when $\mathrm{L}(S) \subseteq \mathrm{PF}(S)$.
\end{definition}

Notice that symmetric and pseudo-symmetric semigroups are almost symmetric.

The concept of AS-semigroup was introduced in \cite {barucci-froberg} where the next is proven.

\begin{proposition}\label{1}
Let $S$ be a numerical semigroup. The following conditions are equivalent:
\begin{enumerate}[ (a)]
  \item $S$ is AS-semigroup;
  \item $\mathrm{PF}(S)=\mathrm{L}(S)\cup\{\mathrm{F}(S)\}$;
  \item $\mathrm{g}(S)=\frac{\mathrm{F}(S)+\mathrm{t}(S)}{2}$.
\end{enumerate}
\end{proposition}

It is well known (see \cite[Proposition 2.2]{nari}) that if $S$ is a numerical semigroup then \begin{equation}\label{ecu3} \mathrm{g}(S) \geq \frac{\mathrm{F}(S)+\mathrm{t}(S)}{2}.\end{equation} Therefore, we deduce that AS-semigroups are those numerical semigroups with the least possible genus in the set of numerical semigroups with fixed Frobenius number and type (observe that AS-semigroups are maximal in this set).

The main aim of this paper is to give algorithmic methods to compute the whole set of AS-semigroups with fixed Frobenius number and given type. Thus, by Proposition \ref{1}, we will solve the optimization of problem of the computation of all numerical semigroups with fixed Frobenius number and type, and minimal genus.

An interesting application our computations is related to the theory of $S-$graded minimal free resolutions (see Remark \ref{Remark final}).

For our main purpose, we will give two algorithms. The first one will start from the almost symmetric numerical semigroups with Frobenius number $F$ and smallest possible type (that is, type equals to $1$) and the second will start from the almost symmetric numerical semigroup with Frobenius number $F$ and biggest possible type  (that is, type equals to $F$). For that reasons, we have called them the ascending and the descending algorithms, respectively.

As an inmediate consequence, our algorithms  allow to compute set of AS-semigroups with fixed Frobenius number. The asceding algorithm has a running time similar to the algorithm given in \cite{CA}. Its main virtue is that it enables to perform the computation with separate processes for each feasible type or even truncate the computation in a range of types. The descending algorithm wins without forgiveness for the previous ones for high Frobenius numbers . A discussion table of timing is included in Section \ref{sect time}.

\section{Irreducible numerical semigroups and AS-semigroups}\label{S2}

Throughout this section, $F$ and $t$ are integers and $S$ denotes a numerical semigroup. Our goal now is to describe the conditions that $F$ and $t$ must fulfill for $S$ to be an AS-semigroup with  Frobenius number $F$ and type $t$. First we need to recall some useful results.

\begin{proposition}\cite[Theorem 3]{CA}.\label{3}
$S$ is AS-semigroup if and only if there exists an irreducible numerical $S'$ and $A \subseteq \mathrm{msg}(S')$ such that
\begin{enumerate}[ (a)]
\item $S = S' \setminus A$.
\item $\mathrm{F}(S')/2 < x < F(S')$, for every $x \in A$.
\item $x+y-\mathrm{F}(S') \not\in S$, for every $x,y \in A$.
\end{enumerate}
In this case, $\mathrm{F}(S) = \mathrm{F}(S')$ and $\mathrm{t}(S)=2 \#A + \mathrm{t}(S')$, where $\#$ means cardinality.
\end{proposition}

Notice that if $A \neq \varnothing$, then $S' \setminus A$ is neither symmetric nor pseudo-symmetric.

Let us denote by $C(F)$ the following numerical semigroup:
\begin{itemize}
\item $\{0, \frac{F+1}2, \frac{F+1}2+1, \frac{F+1}2+2, \ldots \} \setminus \{F\} $ if $F$ is odd;
\item $\{0, \frac{F}2+1, \frac{F}2+2, \ldots \} \setminus \{F\} $ if $F$ is even.
\end{itemize}
Clearly, $C(F)$ has Frobenius number equal to $F$. Moreover, by Lemma \ref{2}, $C(F)$ is irreducible.

\begin{proposition}\cite[Proposition 2.7]{forum}\label{5}
The semigroup $C(F)$ is the unique irreducible numerical semigroup
with Frobenius number $F$ and such that all its minimal generators are larger than $\frac{F}2$.
\end{proposition}

In the following result we present a necessary and sufficient condition for the existence of an AS-semigroup with given Frobenius number and type.

\begin{proposition}\label{6}
There exists an almost symmetric semigroup $S$ with $F(S) = F$
and $t(S) = t$ if if and only if $\mathrm{F}(S)+\mathrm{t}(S)$ is an even number less than or equal to $2\,  \mathrm{F}(S)$.
\end{proposition}

\begin{proof}
Set $F = \mathrm{F}(S)$ and $t = \mathrm{t}(S)$. If $S$ is an AS-semigroup, by Proposition \ref{1}, $F+t = 2 \mathrm{g}(S)$ is even. Besides, since  $g \leq F$, it follows that $F+t \leq 2 F$. Conversely, we distinguish to cases:
\begin{itemize}
\item[] if $F$ is odd, we set $A=\left\{\frac{F+1}{2},\frac{F+1}{2}+1,\ldots,\frac{F+1}{2}+\frac{t-3}{2}\right\}$;
\item[] if $F$ is even, we set $A=\left\{\frac{F}{2}+1,\ldots,\frac{F}{2}+\frac{t-2}{2}\right\}$.
\end{itemize}
Now, if $S' = C(F)$, then, by applying Proposition \ref{3}, we conclude  that $S' \setminus A$ is an AS-semigroup with Frobenius number $F$ and type $t$.
\end{proof}

Observe that, if we choose $ F $ and $ t $ as in Proposition \ref{6}, then we can use Proposition \ref{3} to produce an AS-semigroup with Frobenius number $ F $ and type $ t $, from $ C (S) $. Let us see a couple of examples.

\begin{example}\label{7a}
Set $F=11$ and $t = 5$. By Proposition \ref{6}, there exists at least one AS-semigroup with Frobenius $11$ and type $5$. In this case, the semigroup $C(11)$ is $\{0,6,7,8,9,10,12,13, \ldots \}$. So, by taking $A = \{6,7\}$, Proposition \ref{3} ensures that \[S = C(11) \setminus A = \{0,8,9,10,12,13, \ldots \}\] is an AS-semigroup with $\mathrm{F}(S)=11$ and $\mathrm{t}(S)=5$.
\end{example}

\begin{example}\label{7b}
Set $F=10$ and $t = 6$. By Proposition \ref{6}, there exists at least one AS-semigroup with Frobenius $10$ and type $6$. In this case, the semigroup $C(10)$ is  $\{0,6,7,8,9,11,12,13, \ldots \}$. So, by taking $A = \{6,7\}$, Proposition \ref{3} ensures that \[S = C(10) \setminus A = \{0,8,9,11,12,13, \ldots \}\] is an AS-semigroup with $\mathrm{F}(S)=10$ and $\mathrm{t}(S)=6$.
\end{example}

\section{The asceding algorithm}\label{S3}

Let $F$ and $t$ be positive integers such that $F+t$ is an even number lesser than or equal to $2\, F$. The objective in this section is to describe an algorithmic procedure to compute the set \[\mathscr A(F,t):=\left\{S \mid S \text{ is an AS-semigroup with } \mathrm{F}(S)= F \text{ and } \mathrm{t}(S)=t \right\}.\]
In order to reach the almost symmetric numerical semigroups with Frobenius number $F$ and type $t$, our algorithm will depart from the almost symmetric numerical semigroups with Frobenius number $F$ and type $1$, that is to say, from the irreducible numerical semigroups with Frobenius number $F$.

Before presenting the result that supports our algorithm, we need to recall one of the main results in  \cite{forum} which allows to compute the set $\mathscr I(F)$ of all irreducible numerical semigroups with Frobenius number $F$.

\begin{proposition}\cite[Proposition 2.9]{forum}\label{9}
If $S\in \mathscr I(F)$, then \[\big( S \setminus \{x\} \big) \cup \{F- x \} \in
\mathscr I(F),\] for every $x \in\mathrm{msg}(S)$ such that
$ \frac{F}{2} < x < F,\ 2 x- F \not\in S,\  3 x \neq 2\, F,\ 4 x\neq 3\, F$ and $F-x< \min\big(\mathrm{msg}(S)\big)$.
\end{proposition}

Let $\prec$ be the following binary relation on $\mathscr I(F)$: $S \prec S'$ if and only if there exists $S = S_0, S_1, \ldots, S_p = S'$ such that $S_{i+1}$ is obtained from $S_i$ by applying Proposition \ref{9}. In \cite{forum} it is shown that $\prec$ is an order relation (reflexive, transitive and antisymmetric) on $\mathscr  I(F)$ with first element equal to $C(F)$. In other words, the set $\mathscr  I(F)$  forms a rooted tree with root $C(F )$.

Therefore, one can compute all the irreducible numerical semigroup with Frobenius number $F$ starting from $C(F)$.

\begin{example}\label{10}
Let us compute $\mathscr I(11)$. Using Proposition \ref{9}, we compute the elements in $\mathscr I(11)$ that are immediately bigger than $$C(11)=\{0, 6,7,8,9,10,12,13 \ldots \} = \langle 6,7,8,9,10 \rangle,$$ namely $\langle 3,7 \rangle, \langle 4,6,9 \rangle$ and $\langle 5,7,8,9 \rangle$. By repeating the same construction with these three semigroups, we obtain that the first is maximal and the other two produce $\langle 2, 13 \rangle$ and $\langle 4, 5 \rangle$, respectively. As these two last are maximal, we are done.

The following figure summarizes the construction flow:
\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=.75cm,y=.75cm]

\clip(2,-1) rectangle (9,6);
\draw [->] (5,5) -- (3,3);
\draw [->] (5,5) -- (5,3);
\draw [->] (5,5) -- (7,3);
\draw [->] (5,2) -- (5,0);
\draw [->] (7,2) -- (7,0);
\draw (3.6,5.75) node[anchor=north west] {$\langle 6,7,8,9,10\rangle$};
\draw (2.25,3) node[anchor=north west] {$ \langle 3,7 \rangle$};
\draw (4.1,3) node[anchor=north west] {$\langle 4,6,9\rangle$};
\draw (6.25,3) node[anchor=north west] {$\langle 5,7,8,9\rangle$};
\draw (4.25,0) node[anchor=north west] {$\langle 2,13\rangle$};
\draw (6.35,0) node[anchor=north west] {$\langle 4,5\rangle$};
\draw (3.5,4.5) node[anchor=north west] {$8$};
\draw (5,4.5) node[anchor=north west] {$7$};
\draw (6,4.5) node[anchor=north west] {$6$};
\draw (5,1.5) node[anchor=north west] {$9$};
\draw (7,1.5) node[anchor=north west] {$7$};
\end{tikzpicture}
\end{center}
where each edge was marked with the corresponding $x$.
\end{example}

Now, let us write $b(S)$ for the cardinality of the set \[\left\{ x\in\mathrm{msg}(S) \mid\frac{\mathrm{F}(S)}{2}<x<\mathrm{F}(S) \right\}\] and define  $\mathscr B(F,t) :=\left\{S' \in \mathscr I(F) \mid b(S')\geq  \lceil \frac{t}{2}\rceil-1 \right\}$, being $\lceil - \rceil$ the ceiling operator. Observe that
$\mathscr B(F,t) \neq \varnothing$, because $C(F) \in \mathscr B(F,t)$.

\begin{theorem}\label{Th main}
With the notation above, $S$ is an almost symmetric semigroup with Frobenius number $F$ and type $t$ if and only if there exist $S' \in  \mathscr B(F,t)$ and a subset $A$ of $\mathrm{msg}(S')$ with cardinality $\lceil \frac{t}{2}\rceil-1$ such that $S = S' \setminus A,\ \mathrm{F}(S')/2 < x < F(S')$ and $x+y-\mathrm{F}(S') \not\in S'\setminus A$, for every $x,y \in A$.
\end{theorem}

\begin{proof}
Let $S$ be an AS-semigroup  with Frobenius number $F$ and type $t$. By Proposition \ref{3}, there exist $S' \in \mathscr I(F)$ and $A \subseteq \mathrm{msg}(S')$ such that $S = S' \setminus A, \mathrm{F}(S')/2 < x < F(S')$ and $x+y-\mathrm{F}(S') \not\in S'\setminus A$, for every $x,y \in A$. Moreover, since $t = \mathrm{t}(S) = 2 \# A + \mathrm{t}(S')$, we obtain that $\# A = \frac{t+\delta}2-1$ where $\delta$ is $0$ or $1$ depending on whether $F$ is even or odd. Now, $F+t$ is an even number, we conclude that $\# A =  \lceil \frac{t}{2}\rceil-1$. The converse follows directly from  Proposition \ref{3}.
\end{proof}

The following algorithm computes all AS-semigroups with Frobenius number $F$ and type $t$.

\begin{algorithm}\label{12}\mbox{}\par
\textsc{Input}: $F$ and $t$ two positive integers.\par
\textsc{Output}: $\mathscr A(F,t)$.
\begin{enumerate}[ 1)]
\item Set $\mathscr A(F,t) = \varnothing$.
\item If $t > F$ or $F+t$ is odd  then return $\mathscr A(F,t)$.
\item Compute the set $\mathscr I(F)$.
\item Compute  the set $\mathscr B(F,t) =\left\{S' \in \mathscr I(F) \mid b(S')\geq  \lceil\frac{t}{2}\rceil-1 \right\}$.
\item For each $S' \in \mathscr B(F,t)$ compute
\begin{enumerate}[ 4.1)]
\item $\mathcal A(S')=\Big\{A \subseteq \mathrm{msg}(S') \mid \#A=\lceil \frac{t}{2}\rceil-1,\ \frac{F}{2}<x<F$ and $x+y-F\not\in S' \setminus A$, for every $x,y \in A\Big\}$
\item Set $\mathscr D(S')=\left\{ S' \setminus A \mid A\in \mathcal A(S')\right\} $
\item Append $\mathscr D(S')$ to $\mathscr A(F,t)$.
\end{enumerate}
\item  Return $\mathscr A(F,t)$.
\end{enumerate}
\end{algorithm}

The correctness of this algorithm relies on Theorem \ref{Th main}.
The algorithm ends because the sets $\mathscr B(F,t)$ and $\mathcal A(S'),\ S' \in \mathscr B(F,t)$, are empty or finite.

\begin{example}
Let us compute the set $\mathscr A(11,7)$. By Example \ref{10} we have that $\mathscr B(11,7)=\left\{\langle 6,7,8,9,10\rangle,
\langle 5,7,8,9\rangle\right\}$.
\begin{itemize}
\item If $S'=\langle 6,7,8,9,10\rangle$, then the subsets $A$ of $\left\{6,7,8,9,10\right\}$ with cardinality $3$ such that  $x+y-11\not\in S'\setminus A$, for every $x,y \in A$ are $\{6,7,8\}$ and $\{6,7,9\}$
\item If $S'=\langle 5,7,8,9\rangle$, then there exists no $A$ possible.
\end{itemize}
Hence, by applying Proposition \ref{3},
\begin{align*}
\mathscr A(11,7) & =\left\{ \langle 6,7,8,9,10\rangle\setminus \{6,7,8\}, \langle 6,7,8,9,10\rangle\setminus \{6,7,9\}\right\}\\ & =  \left\{\langle 9,10,12,13,14,15,16,17\rangle,\langle 8,10,12,13,14,15,17,19\rangle\right\}
\end{align*}
We can verify this computation by using the \texttt{NumericalSgps} package (see \cite{numericalsgps}). It suffices to change the first line in the code provided in \cite[Example 5]{CA} by
\texttt{almostnsfromirreducibleAlt := function(s,t)} and set the variable \texttt{pow} as \texttt{Combinations(msg,CeilingOfRational(t/2)-1)}.

\medskip
The following piece of code will do the rest:
\begin{verbatim}
   assemigroupswithfrobeniusnumberandtype:=function(f,t)
      return Union(Set(
      IrreducibleNumericalSemigroupsWithFrobeniusNumber(f),
      s->almostnsfromirreducible(s,t)
      ));
   end;
\end{verbatim}
Indeed, the command \texttt{assemigroupswithfrobeniusnumberandtype(11,7)} will give us all the almost symmetric semigroups of Frobenius number 11 and type 7.
\end{example}

\begin{remark}
Let $g$ be a positive integer. By Proposition \ref{1}, the set of all AS-semigroups with genus $g$ and type $t$ and the set of all AS-semigroups with Frobenius number $F$ and genus $g$ are $\mathscr A(2g-t,t)$ and $\mathscr A(F,2g-F)$, respectively.
Notice that,  by Proposition \ref{6}, there exists at least one AS-semigroup with genus $g$ and type $t$ for every pair $(g,t)$ of positive integers such that $t \leq g$. Analogously, there exists at least one AS-semigroup with Frobenius number $F$ and genus $g$ for every pair $(F,g)$ of positive integers  such that $g \leq F$.
\end{remark}

We, finally, observe that since $t \leq F$ we can compute the set of all AS-semigroup with fixed Frobenius number $F$, $\mathscr A(F)$,  that is nothing but the union of the sets $\mathscr A(F,2i-F)$ for every $i = \lceil \frac{F+1}2 \rceil, \ldots, F$.

\begin{verbatim}
assemigroupswithfrobeniusnumber := function(F)
    local irr, irrt, c;

    irr:=IrreducibleNumericalSemigroupsWithFrobeniusNumber(F);
    if IsOddInt(F) then
      c:=1;
    else
      c:=2;
    fi;
    irrt:=Cartesian(irr,[c..Int(F/2)]);
    return Concatenation(irr,Concatenation(List(irrt,
     st->almostnsfromirreducibleAlt(st[1],2*st[2]+
     RemInt(F,2)))));
end;
\end{verbatim}

\section{The desceding algorithm}\label{S4}

Let $F$ be a positive integer and define $M(F)$ to be the numerical semigroup $\{0, F+1, F+2, \ldots \}$. Clearly, this semigroup has Frobenius number and type equal to $F$. Moreover, since $\mathbb{N} \setminus M(F) = \mathrm{PF}(M(F))= \{1, \ldots, F\}$, we have that $g = \frac{F+F}2$. So, by Proposition \ref{1}, $M(F)$ is a almost symmetric.

\begin{lemma}
The unique numerical semigroup with both Frobenius number and type equal to $F$ is $M(F)$.
\end{lemma}

\begin{proof}
Let $S$ be a numerical semigroup such that $F(S)=t(S)=F$. Since $g(S) \leq F$ and, by \eqref{ecu3}, $g(S) \geq \frac{F(S)+t(s)}2=F$. We conclude that $\mathbb N \setminus S = \{1, \ldots, F\}$, that is to say, $S = M(F)$.
\end{proof}

In this section, we will depart from $M(F)$, i.e. the almost symmetric semigroup with Frobenius number and type equal to $F$, in order to ``descend'' to the set of almost symmetric semigroup with Frobenius number $F$ and type $t \leq F$.

We recall that the least positive integer in a numerical semigroup $S$ is called the \textbf{multiplicity} of $S$ and it is denoted $m(S)$. The following result relates the multiplicity and type of a numerical semigroup.

\begin{proposition}\label{15}\cite[Corollary 2.23]{libro}.
Let $S$ be a numerical semigroup. Then \[m(S) \geq t(S)+1\]
\end{proposition}

\begin{theorem}\label{16}
Let $F \geq 5$ and $t \leq F$ be a positive integer greater than $2$ such that $F+t$ is even. Then $S$ is an almost symmetric numerical semigroup with Frobenius number $F$ and type $t-2$ if and only if there exist an almost symmetric numerical semigroup $S'$ with Frobenius number $F$ and type $t$, $x \in [t-1,m(S')-1]$ such that
\begin{enumerate}[ (a)]
\item $S = \{x\} \cup S'$.
\item $-x + \mathbb{N} \setminus S \subseteq \mathbb{Z} \setminus S$.
\item $\big(x + (\mathrm{PF}(S') \setminus \{x,F-x\}) \big) \subseteq S$.
\end{enumerate}
In this case, $\mathrm{PF}(S') = \mathrm{PF}(S) \cup \{x,F-x\}.$
\end{theorem}

\begin{proof}
Suppose that $S$ is almost symmetric with Frobenius number $F$ and type $t-2$. Set $x = m(S)$ and define $S'$ to be the numerical semigroup generated by $S \setminus \{x\}$. Notice that the conditions (a)-(c) are trivially satisfied by construction.

Let us prove that $S'$ is almost symmetric with Frobenius number $F$ and type $t$.

Clearly, $F(S')$ is either $x$ or $F$. If $F(S') = x$, then $S = M(F)$ has type $F > t-2$ that is not possible by hypothesis. So $F(S') = F$.

Now, we prove that the type of $S'$ is $t$. By definition, $g(S')=g(S)+1$. Thus, since \begin{equation}\label{ecu1} \frac{F+t(S')}2 \leq g(S') = g(S)+1=\frac{F+t-2}2+1 = \frac{F+t}2,\end{equation} we obtain that $t(S') \leq t$. Furthermore, $F-x \not\in S'$, otherwise $F=(F-x)+x \in S$, and $x=F-(F-x) \not\in S'$. Thus, $\{x,F-x\} \subseteq PF(S')$. Now, since $y + S \setminus \{0\} \subseteq S$, for every $y \in PF(S)$, we have that $y+S' \setminus \{0\} \subseteq S$, for every $y \in PF(S)$. If $y+s' = x$, for some $s' \in S' \setminus \{0\},$ then $s' = x-y \leq x = m(S) < m(S') \leq s'$, a contradiction.  Therefore $PF(S) \subseteq PF(S') \setminus \{x,F-x\},$ in particular, $t-2 = t(S) \leq t(S')-2,$ that is to say, $t \leq t(S')$. Thus, $t(S') = t$.

From \eqref{ecu1} it follows that $g(S') = \frac{F(S')+t(S')}2$; so, by Proposition \ref{1}, we conclude that $S'$ is almost symmetric.

Conversely, suppose that there exist an almost symmetric numerical semigroup $S'$ with Frobenius number $F$ and type $t$, and $x \in [t-1,m(S')-1]$ satisfying (a)-(c). Let $S = \{x\} \cup S'$. Given $y \in S$, then $x+y \in S$; otherwise, by condition (b), $y = -x+(x+y) \in \mathbb{Z} \setminus S$. Therefore, $S$ is a semigroup that is numerical because $\mathbb{N} \setminus S \subset \mathbb{N} \setminus S'$. Moreover, since $x \leq m(S') - 1 < F$, we have that $F(S) = F$.

Let us see now that $t(S) = t-2$. On the one hand we have that $g(S) = g(S')-1$. Thus, \begin{equation}\label{ecu2} \frac{F+t(S)}2 \leq g(S) = g(S')-1=\frac{F+t}2-1 = \frac{F+t-2}2,\end{equation} and consequently, $t(S) \leq t-2$. On the other hand, if $y \in \mathrm{PF}(S') \setminus \{x,F-x\}$, then $y + z \in S' \subset S$, for every $z \in S'$ and, by condition (b), $x+y \in S.$ Thus, $\mathrm{PF}(S') \setminus \{x,F-x\} \subseteq \mathrm{PF}(S)$ and, consequently, $t(S')-2 = t-2 \leq t(S)$. Thus, $t(S) = t-2$.

From \eqref{ecu2} it follows that $g(S) = \frac{F(S)+t(S)}2$; so, by Proposition \ref{1}, we obtain that $S$ is almost symmetric.

Notice that in both implications we have obtained that $\mathrm{PF}(S') = \mathrm{PF}(S) \cup \{x,F-x\},$ as immediate consequence.
\end{proof}

Observe that the set, $\cup_{i=t}^F \mathscr{A}(F,i)$, of almost symmetric numerical semigroups with Frobenius number $F \geq 1$ and type greater than or equal to $t \leq F$ forms a rooted tree with root $M(F)$. Thus, using Theorem \ref{16}, we can formulate an iterative algorithm for computing the whole set $\cup_{i=t}^F \mathscr{A}(F,i)$, where the cases $1 \leq F \leq 4$ can be obtained by direct computation.

Obviously if $t = 1$, our algorithm will compute the whole set $\mathscr{A}(F)$ of almost symmetric numerical semigroups with Frobenius number $F$.

\begin{algorithm}\label{17}
The following GAP (\cite{GAP}) functions compute the whole set \[\bigcup_{i=t}^F \mathscr{A}(F,i)\] for $1 \leq t \leq F,\ F+t$ even and $F \geq 3$. The first function is nothing but the recursive step, while the second one is the core function that follows from Theorem \ref{16}. The function \texttt{NumericalSemigroupByGaps} from the
\texttt{NumericalSgps} package (\cite{numericalsgps}) is required.

\medskip
\begin{verbatim}
assemigroupswithfrobeniusnumberuptotype := function(F,t)
  local L,sg,PF,Ga,N;
  L:=[[[F+1 .. 2*F+1],[1 .. F],[1 .. F]]];
  sg:=Union([F-1],[F+1 .. 2*F+1]);
  PF:=Difference([1 .. F],[F-1,1]);
  Ga:=Difference([1 .. F],[F-1]);
  Append(L,[[sg,PF,Ga]]);

  N:=[[sg,PF,Ga]];
  repeat
    N:=Concatenation(List(N, t->CallFuncList(auxiliar,t)));
    Append(L,N);
  until Length(N[1][2]) < t+2;
  return List(L, t->NumericalSemigroupByGaps(t[3]));
end;

auxiliar := function(sg,PF,Ga)
    local L,m,t,i,sg1,PF1,Ga1;
    L := []; m:=sg[1]; t:=Length(PF); F:=PF[t];
    for i in [t-1 .. m-1] do
      sg1:=Union([i],sg);
      PF1:=Difference(PF,[i,F-i]);
      Ga1:=Difference(Ga,[i]);
      if  IsSubset(Ga1,Filtered(Ga1-i,j->(j>0)))
       and
         (Intersection(PF1+i, Ga1) = [ ]) then
       Append(L,[[sg1,PF1,Ga1]]);
      fi;
    od;
    return L;
end;
\end{verbatim}

A much more refined implementation of our algorithm can be found at the development version site of the \texttt{NumericalSgps}  package (\cite{numericalsgps}): \url{https://github.com/gap-packages/numericalsgps}.
\end{algorithm}

Notice that algorithm computes also the set of pseudo-Frobenius numbers of every almost symmetric numerical semigroup of Frobenius number $F$ and type up to a fixed $t \geq 1$. Indeed, the key fact of Theorem \ref{16} is that controls the set of pseudo-Frobenius numbers.

\begin{remark}\label{Remark final}
The semigroup algebra $\mathbb{Q}[S] := \bigoplus_{s \in S} \mathbb{Q}\, \chi^s,$ a $S-$graded resolution has the form $$0 \to \bigoplus_{j=1}^{l_{k-1}} A^{r_{k-1\, j}}(-b_{k-1\, j}) \longrightarrow \ldots \longrightarrow \bigoplus_{j=1}^{l_1} A^{r_{1\, j}}(-b_{1\, j}) \longrightarrow A \stackrel{\varphi_0}{\longrightarrow} \mathbb{Q}[S] \to 0,$$ where integer $\beta_i := \sum_{j=1}^{l_j} r_{ij}$ is the rank of the $i-$th syzygy module of $\mathbb{Q}[S]$ and $b_{ij} \neq b_{ij'},\ j \neq j'.$

It is well known that $PF(S) = \big\{ b - \sum_{i=1}^k a_i \mid b \in \{b_{k-1\, 1}, \ldots,  b_{k-1\, l_{k-1}} \} \big\}$ (see \cite{MOT}).

On the other hand, in \cite{OjVi} an algorithm for the computation of the $S-$gra\-ded minimal free resolution of $\mathbb{Q}[S]$ is given. One of the main contribution in that paper is that the resolution can be computed from left to right, that is, starting from the pseudo-Frobenius number of $S$.

Therefore, our algorithms produce families of numerical semigroups for which $t = \beta_{k-1}$ is a priori known, and furthermore, for which the $S-$gra\-ded minimal free resolution of $\mathbb{Q}[S]$ can be computed starting from left to right.
\end{remark}

\section{Calculation time comparisons}\label{sect time}

In this section, a table with some computational results is presented. We have obtained it running GAP 4.8.6 (\cite{GAP}) in a Intel(R) Core(TM) i5-2450M CPU \@ 2.50GHz. The used implementations of our algorithms are the given above. The function
\begin{center}
 \texttt{AlmostSymmetricNumericalSemigroupsWithFrobeniusNumber}
\end{center}
is the one included in the version 1.1.8 of the \texttt{NumericalSgps} package (\cite{numericalsgps}).

For simplicity, we write
\begin{enumerate}[ (A)]
\item for \texttt{AlmostSymmetricNumericalSemigroupsWithFrobeniusNumber},
\item for \texttt{assemigroupswithfrobeniusnumber},
\item for \texttt{assemigroupswithfrobeniusnumberuptotype}
\end{enumerate}
The computation time below is expressed in seconds.

\medskip
\begin{center}
\begin{tabular}{||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Frobenius(S) & 13 & 14 & 15 &  20 & 25 & 30 & 40 \\
\hline\hline
(A)  & 0.004 & 0.004 & 0.012 & 0.032 & 0.196 & 0.764 & 39.292 \\
\hline
(B)  & 0 & 0.008 & 0.008 & 0.04 & 0.172 & 0.764 & 38.924 \\
\hline
(C)  & 0 & 0 & 0.004 & 0.008 & 0.028 & 0.076 & 0.692  \\
\hline
\end{tabular}
\end{center}

\medskip
It is important to mention that the algorithm given in Section \ref{S3} is better than (C) if one just wants to compute the set $\mathscr{A}(F,t)$ for small $t$. For example, the function \texttt{assemigroupswithfrobeniusnumberandtype} took $0.884$ seconds to compute $\mathscr{A}(50,4)$, whereas a truncated version of (C) took $6.632$ seconds. The reason is clear, the procedure (C) needs to compute first $\mathscr{A}(50,t)$ for every $t$ from $F$ to $4$.

\medskip
\noindent\textbf{Acknowledgement.}
We thank the anonymous referees for their detailed suggestions and comments, which have greatly improved this article. We also thank Pedro A. Garc\'{\i}a-S\'anchez for his invaluable help to refine and improve the implementation of our algorithms.

config: arxiv


TITLE: Regarding a basis which generates K-topology
QUESTION [0 upvotes]: We know that $\{(a,b):a,b\in \mathbb{R}\}\cup\{(a,b)\setminus K: a,b\in \mathbb{R}\}$ is a basis for a topology called $K$-topology on $\mathbb{R}$, where $K=\{\dfrac{1}{n}:n\in \mathbb{N}\}$. I am searching for a member of $K$-topology, which is not there in lower limit topology on $\mathbb{R}$.
Please give a hint.

REPLY [1 votes]: HINT: The only point at which the $K$-topology really differs from the Euclidean topology is $0$, so you should look for something involving $0$. It should also be one of the non-Euclidean open sets involving $K$. What about $[0,1)\setminus K$?


TITLE: Prove that 2003 is prime.
QUESTION [0 upvotes]: How do I prove that 2003 is a prime number? It's not very impressive going through factors and searching the internet only gives answers to smaller numbers. Can anyone help?

REPLY [4 votes]: It's not foolproof, but you can do $2^{2002} \equiv 1 \pmod{2003}$ (this is Fermat's little theorem), but $2003$ could be a pseudoprime. So then you could see that $2002! \equiv 2002 \pmod{2003}$. This is Wilson's theorem, since it's an if-and-only-if theorem, you're done.
The use of congruences helps keep these numbers reasonably small, you don't actually have to compute the full value of $2^{2002}$ or $2002!$.


text:
\section{Dynamic dynamic programming}\label{sec:dp}

In this section we show how the data structure presented in Section~\ref{sec:data-structure} can be enriched so that together with an elimination forest, it also maintains a run of an auxiliary dynamic program on this forest.
For this, we need to understand dynamic programming on elimination forests in an abstract way, which we do using a formalism of {\em{configuration schemes}}.
This formalism is based on the classic algebraic approach to graph decompositions, and in particular on the idea of recognizing finite-state properties of graphs of bounded treewidth through homomorphisms into finite algebras.
This direction has been intensively developed in the 90s, see the book of Courcelle and Engelfriet~\cite{CourcelleE12} for a broad introduction.
The definitional layer that we use is closest to the one used in the work of Bodlaender et al.~\cite{BodlaenderFLPST16}.

\paragraph*{Boundaried graphs.}
We shall assume that all vertices in all the considered graphs come from some countable reservoir of vertices $\Omega$, say $\Omega=\N$.
A {\em{boundaried graph}} is a graph $G$ together with a subset of vertices $X\subseteq V(G)$, called the {\em{boundary}}.
On boundaried graphs we can introduce two basic operators:
\begin{itemize}[nosep]
 \item For a boundaried graph $(G,X)$ and $x\in X$, the operator $\forget$ yields
       $$\forget((G,X),x)\coloneqq (G,X\setminus \{x\}).$$
 \item For two boundaried graphs $(G_1,X_1)$ and $(G_2,X_2)$ such that $V(G_1)\cap V(G_2)=X_1\cap X_2$, the {\em{union}} operator $\oplus$ yields
       $$(G_1,X_1)\oplus (G_2,X_2)\coloneqq ((V(G_1)\cup V(G_2),E(G_1)\cup E(G_2)),X_1\cup X_2).$$
       In other words, we take the disjoint union of $G_1$ and $G_2$ and, for each $x\in X_1\cap X_2$, we fuse the copy of $x$
       from $G_1$ with the copy of $x$ from $G_2$. The boundary of the output graph is $X_1\cup X_2$.
\end{itemize}
Note that the operator $\forget((G,X),x)$ is defined only if $x\in X$, while the operator $(G_1,X_1)\oplus (G_2,X_2)$ is defined only if $V(G_1)\cap V(G_2)=X_1\cap X_2$.
It is useful to think of this as of an abstract algebra on boundaried graphs, endowed with operations $\forget$ and $\oplus$.

\paragraph*{Configuration schemes.}
We now introduce the language of {\em{configuration schemes}}, which intuitively is a way of assigning each boundaried graph $(G,X)$ a set of {\em{configurations}} $\conf(G,X)$
which contains all the essential information about the behaviour of $(G,X)$ with respect to some computational problem.

A {\em{configuration scheme}} is a pair of mappings $(\Conf,\conf)$ such that
with any set of vertices $X\subseteq\Omega$ we may associate a set of {\em{configurations}} $\Conf(X)$,
and with every boundaried graph $(G,X)$ we may associate a subset of configurations $\conf(G,X)\subseteq \Conf(X)$ {\em{realized}} by $(G,X)$. For an example what this might be, see the first paragraph of the proof of Lemma~\ref{lem:schem-kpath}.
We will need several properties of configuration schemes, the first of which is composability.

We will say that such a configuration scheme $(\Conf,\conf)$ is {\em{composable}} if the following conditions hold.
\begin{itemize}[nosep]
 \item For a boundaried graph $(G,X)$ and $x\in X$, $\conf(\forget((G,X),x))$ is uniquely determined by $\conf(G,X)$ and $x$.
 \item For boundaried graphs $(G_1,X_1)$ and $(G_2,X_2)$ whose union is defined, $\conf((G_1,X_1)\oplus (G_2,X_2))$ is uniquely determined by $\conf(G_1,X_1)$ and $\conf(G_2,X_2)$.
\end{itemize}
Letting $\Xi\coloneqq \biguplus_{X\subseteq \Omega} 2^{\Conf(X)}$, the above conditions are equivalent to saying that there exist operators
$$\forget\colon \Xi \times \Omega \to \Xi \qquad\textrm{and}\qquad\oplus\colon \Xi \times \Xi \to \Xi$$
such that the following assertions hold:
\begin{itemize}[nosep]
 \item Operator $\forget(\cdot,\cdot)$ is defined only on pairs of the form $(C,x)$ such that $C\in 2^{\Conf(X)}$ and $x\in X$ for some $X\subseteq \Omega$; then $\forget(C,x) \in 2^{\Conf(X \setminus \{ x \} )}$.
 \item For every boundaried graph $(G,X)$ and $x\in X$, we have $$\conf(\forget((G,X),x))=\forget(\conf(G,X),x).$$
 \item If $C_1 \in 2^{\Conf(X_1)}$ and $C_2 \in 2^{\Conf(X_2)}$ for some $X_1,X_2\subseteq \Omega$, then $C_1 \oplus C_2 \in 2^{\Conf(X_1 \cup X_2)}$.
 \item For all boundaried graphs $(G_1,X_1)$ and $(G_2,X_2)$ whose union is defined, we have $$\conf((G_1,X_1)\oplus (G_2,X_2))=\conf(G_1,X_1)\oplus \conf(G_2,X_2).$$
\end{itemize}
In other words, $\conf$ is a homomorphism from the algebra of boundaried graphs endowed with operations $\forget$ and $\oplus$ to the algebra on $\Xi$ with the same operations.
Note that $\oplus$ is commutative and associative on boundaried graphs, hence it should also have these properties on sets of configurations.

We will say that $(\Conf,\conf)$ is {\em{efficiently composable}} if there is a non-decreasing computable function $\zeta\colon \N\to \N$ such that
\begin{itemize}[nosep]
 \item For every $X\subseteq \Omega$ we have $|\Conf(X)|\leq \zeta(|X|)$ and given $X$, one can compute $\Conf(X)$ in time $\zeta(|X|)^{\Oh(1)}$.
 \item Given a boundaried graph $(G,X)$ with $|V(G)| \leq 2$ and $X = V(G)$, one can compute $\conf(G,X)$ in constant time.
 \item Given $X\subseteq \Omega$, $x\in X$, and $C\subseteq \Conf(X)$, one can compute $\forget(C,x)$ in time~$\zeta(|X|)^{\Oh(1)}$.
 \item Given $X_1,X_2\subseteq \Omega$, $C_1\subseteq \Conf(X_1)$, and $C_2\subseteq \Conf(X_2)$, one can compute  $C_1\oplus C_2$ in time $\zeta(|X|)^{\Oh(1)}$.
\end{itemize}
Finally, we will say that $(\Conf,\conf)$ is {\em{idempotent}} if there is a non-decreasing computable function $\tau\colon \N\to \N$ such that the following condition holds:
\begin{itemize}[nosep]
 \item Consider any $X\subseteq \Omega$ and a multiset $\Mm$ whose elements are subsets of $\Conf(X)$.
       Suppose in $\Mm$ there is $C\subseteq \Conf(X)$ such that for each $c\in C$, there are at least $\tau(|X|)$ elements $D\in \Mm\setminus \{C\}$ such that $c\in D$.
       Then $$\bigoplus_{D\in \Mm\setminus \{C\}} D\ =\ \bigoplus_{D\in \Mm} D.$$
\end{itemize}
A configuration scheme $(\Conf,\conf)$ that is both efficiently composable and idempotent shall be called {\em{tractable}}.
The corresponding functions $\zeta$ and $\tau$ shall be called the {\em{witnesses}} of tractability of $(\Conf,\conf)$.

\paragraph*{Recognizing properties.}
A {\em{graph property}} is simply a set $\Pi$ consisting of graphs, interpreted as graphs that admit $\Pi$.
A graph property $\Pi$ is {\em{recognized}} by a configuration scheme $(\Conf,\conf)$ if there exists a subset of {\em{final}} configurations $F\subseteq \Conf(\emptyset)$ such that for every graph $G$, we have
$$G\in \Pi\qquad \textrm{if and only if}\qquad \conf(G,\emptyset)\cap F\neq \emptyset.$$

As mentioned before, the formalism introduced above should be standard for a reader familiar with the work on graph algebras and recognition of $\MSO$-definable languages of graphs.
Recall here that $\MSO_2$ is a logic on graphs that extends the standard first order logic $\FO$ by allowing quantification over subsets of vertices and over subsets of edges.
A graph property $\Pi$ is {\em{$\MSO_2$-definable}} if there exists a sentence $\varphi$ of $\MSO_2$ such that for every graph $G$, $\varphi$ holds in $G$ if and only if $G\in \Pi$.
Then the classic connection between graph algebras and $\MSO_2$ yields the following statement.
As this is not the main focus of our work, we only give a sketch of the proof, but both the statement and the tools are standard.

\begin{lemma}\label{lem:mso-tractable}
 Every $\MSO_2$-definable graph property is tractable.
\end{lemma}
\begin{proof}[Sketch]
 Let us first recall some basic definitions and facts from logic.
 The {\em{quantifier rank}} of a formula is the maximum number of nested quantifiers in it.
 For $X\subseteq \Omega$, let $\MSO_2[X]$ be the standard $\MSO_2$ logic on graphs where in the signature, apart from the standard relations for encoding graphs, we also have each $x\in X$ introduced as a constant.
 It is known that for every $q\in \N$ and $X$, there is only a finite number of pairwise non-equivalent $\MSO_2[X]$-statements of quantifier rank at most $q$.
 Moreover, given $q$ and $X$, one can compute a set $\Types^q(X)$ consisting of one $\MSO_2[X]$-statement of quantifier rank at most $q$ per each class of equivalence. Thus, $|\Types^q(X)|$ is bounded by a computable function of $q$ and $X$.
 Then, with every boundaried graph $(G,X)$ we can associate its {\em{$q$-type}} $\type^q(G,X)\subseteq \Types^q(X)$, which just comprises all those statements $\psi\in \Types^q(X)$ that are satisfied in $(G,X)$.

 We move to the sketch of the proof.
 Let $\Pi$ be the property in question, and let $\varphi$ be the $\MSO_2$-statement defining $\Pi$. Let $q$ be the quantifier rank of $\varphi$.
 We define the following configuration scheme $(\Conf,\conf)$:
 \begin{itemize}[nosep]
  \item for $X\subseteq \Omega$, we let $\Conf(X)\coloneqq \Types^q(X)$; and
  \item for a boundaried graph $(G,X)$, we let $\conf(G,X)\coloneqq \type^q(G,X)$.
 \end{itemize}
 The fact that this configuration scheme is efficiently composable and idempotent is a standard fact about $\MSO_2$ logic, which can be proved e.g. using Ehrenfeucht-Fra\"isse games.
 By taking the set of final configurations to be $F\coloneqq \{\varphi\}$, we see that this configuration scheme recognizes $\Pi$.
\end{proof}

Lemma~\ref{lem:mso-tractable} gives tractability of any $\MSO_2$-definable graph property, however the witnesses $\zeta,\tau$ of this tractability are non-elementary functions.
We now give an explicit configuration scheme for the property of our interest: containing a $k$-path.

\begin{lemma}\label{lem:schem-kpath}
 For $k\in \N$, let $\Pi_k$ be the graph property comprising all graphs that contain a simple path on $k$ vertices.
 Then $\Pi_k$ is recognized by a tractable configuration scheme with witnesses $\zeta(x)=(k+1)\cdot 2^{x+1}\cdot x!$ and $\tau(x)=x+2$.
\end{lemma}
\begin{proof}
 We first define the configuration scheme.
 Let $s,t$ be two new special vertices, not belonging to $\Omega$; intuitively, in our scheme these will be markers representing the beginning and the end of the constructed path.
 Recall that a {\em{linear forest}} is an acyclic undirected graph whose every component is a path.
 For $X\subseteq \Omega$, we define the set of configurations $\Conf(X)$ as follows: $\Conf(X)$ consists of all pairs $(H,i)$ such that:
 \begin{itemize}[nosep]
  \item $H$ is a linear forest with vertex set $X\cup \{s,t\}$, where the degrees of $s$ and $t$ are at most $1$; and
  \item $i\in \{0,1,\ldots,k-1,\infty\}$.
 \end{itemize}
 Moreover, we require that if $E(H)=\emptyset$, then $i=0$.

It is straightforward to see that the number of different linear forests with vertex set of size $p$ is at most $2^{p-1}\cdot p!$: a linear forest can be chosen by
selecting a permutation $\pi=(u_1,\ldots,u_p)$ of the vertex set ($p!$~choices), and then deciding, for each $i\in \{1,\ldots,p-1\}$, whether $u_i$ and $u_{i+1}$ are adjacent ($2^{p-1}$ choices).
Therefore, we have $|\Conf(X)|\leq (k+1)\cdot 2^{|X|+1}\cdot |X|!=\zeta(|X|)$, as required.

Now, for a boundaried graph $(G,X)$ and a configuration $(H,i)\in \Conf(X)$, we shall say that $(H,i)$ is {\em{realized}} in $(G,X)$ if there exists a family of paths $\{P_e\colon e\in E(H)\}$ in $G$
satisfying the following conditions:
\begin{itemize}[nosep]
 \item For each $xy\in E(H)$, $P_e$ is a path whose one endpoint is $x$, provided $x\in X$, and the second endpoint is $y$, provided $y\in X$. If $x$ or $y$ (or both) belongs to $\{s,t\}$, then the corresponding endpoint of $P_e$ can be any vertex of $V(G)$. Moreover, $V(P_e)\cap X=\{x,y\}\cap X$.
 \item For all $e,e'\in E(H)$, the paths $P_e$ and $P_{e'}$ are vertex-disjoint, apart from possibly sharing an endpoint in case $e$ and $e'$ share an endpoint.
 \item The total number of edges on paths $P_e$ is equal to $i$ if $i<\infty$, or is at least $k$ if $i=\infty$.
\end{itemize}
For a boundaried graph $(G,X)$, let $\conf(G,X)\subseteq \Conf(X)$ be the set of configurations realized in $(G,X)$.

Observe that a graph $G$ contains a simple path on $k$ vertices if and only if $\conf(G,\emptyset)$ contains configuration $(H_0,k-1)$, where $H_0$ is the graph on vertex set $\{s,t\}$ with the edge $st$ present.
Thus, by setting $F\coloneqq \{(H_0,k-1)\}$ we see that the scheme $(\Conf,\conf)$ recognizes $\Pi_k$. It remains to show that $(\Conf,\conf)$ is suitably efficiently composable and idempotent.

\begin{claim}\label{cl:composable}
 The configuration scheme $(\Conf,\conf)$ is efficiently composable with witness $\zeta(x)=(k+1)\cdot 2^{x+1}\cdot x!$.
\end{claim}
\begin{clproof}
 The bound $|\Conf(X)|\leq\zeta(|X|)$ has already been shown.
 Also, for every boundaried graph $(G, X)$ such that $|V(G)|\leq 2$ and $X = V(G)$, the value of $\conf(G, X)$ can be computed in constant time trivially by the definition.
 Thus, to prove the claim, it remains to define suitable operators $\forget$ and $\oplus$, and to show that they are computable in time $\zeta(|X|)^{\Oh(1)}$.

 We start with defining the $\forget(\cdot,\cdot)$ operator.
 For any boundaried graph $(G, X)$ and $x \in X$ consider a configuration $(H, i) \in \conf(\forget((G,X),x))$ and a corresponding family of paths $\{P_e\colon e\in E(H)\}$ in $G$, as described in the definition of $\conf(\cdot)$.
 There are three possibilities of how $x$ can interact with this family of paths:
 \begin{itemize}[nosep]
  \item $x$ is an internal vertex of exactly one path $P_e$. This means that $(H', i) \in \conf(G, X)$, where $e = yz$ and $H'=(V(H) \cup \{x\}, E(H) \cup \{xy, xz\} \setminus \{yz\})$.
  \item $x$ is an endpoint of some path $P_e$. From the definition this is possible if and only if the corresponding endpoint of $e$ belongs to $\{s, t\}$; say $e=ys$, the other case being analogous.
        Again, this means that $(H', i) \in \conf(G, X)$, where $H'=(V(H) \cup \{x\}, E(H)\cup \{xy, xs\} \setminus \{ys\})$.
  \item $x$ does not belong to any of these paths. This means that $((V(H) \cup \{x\}, E(H)), i) \in \conf(G, X)$.
 \end{itemize}

 These observations show a way of defining $\forget(\cdot,\cdot)$. For a linear forest $H$ and $x \in V(H)$ such that $x$ has degree $2$ in $H$,
 let $\join(H, x)$ be the graph obtained from $H$ by adding an edge connecting the neighbors of $x$ and removing $x$ itself. Then for $C\subseteq \Conf(X)$ we can write the definition of $\forget$ as follows:
 \begin{eqnarray*}
   \forget(C, x) & \coloneqq & \forget_0(C, x) \cup \forget_2(C, x);\\
   \forget_0(C, x) & \coloneqq & \{\, (H-x, i)\ \colon\ (H, i) \in C, x \in V(H), \degree_H(x) = 0\,\};\\
   \forget_2(C, x) & \coloneqq & \{\, (\join(H, x), i)\ \colon\ (H, i) \in C, x \in V(H), \degree_H(x) = 2\,\}.
 \end{eqnarray*}
 Based on the previous observations, it is easy to see that this operator satisfies the desired property: $\conf(\forget((G,X),x))=\forget(\conf(G,X),x)$ for every boundaried graph $(G, X)$ and $x \in X$.
 Moreover, $\forget(C, x)$ can be computed in time $\zeta(|X|)^{\Oh(1)}$ by inspecting every element of $C$ and applying the formula above; recall here that $|C|\leq \zeta(|X|)$.

 We now move to the discussion of the $\oplus$ operator.
 Consider any pair of boundaried graphs $(G_1, X_1)$ and $(G_2, X_2)$ whose union is defined, and let $(G, X) \coloneqq (G_1,X_1)\oplus (G_2,X_2)$.
 Consider a configuration $(H, i) \in \conf(G, X)$ and a corresponding family of paths $\{P_e\colon e\in E(H)\}$ in $G$.
 Note that each path $P_e$ is either a single edge, in which case it can be present both in $G_1$ and $G_2$, or it has some internal vertices.
 In the latter case all internal vertices and edges of $P_e$ must belong either to $G_1$ or to $G_2$. They cannot belong to both, as $P_e$ is internally disjoint with $X$, and in $G$ there is no edge between $V(G_1)\setminus X_1$
 and $V(G_2)\setminus X_2$.
 In particular, this means that each path from the family $\{P_e\colon e\in E(H)\}$ is either entirely contained in $G_1$ or entirely contained in $G_2$. Based on this observation, we can define $\oplus$ as follows.

 Two configurations $(H_1,i_1)\in \Conf(X_1)$ and $(H_2,i_2)\in \Conf(X_2)$ are {\em{mergeable}} if $E(H_1)\cap E(H_2)=\emptyset$ and
 the graph $H_1\oplus H_2\coloneqq (V(H_1)\cup V(H_2),E(H_1)\cup E(H_2))$ is a linear forest with $s$ and $t$ having degrees at most $1$.
 Then for $C_1\subseteq \Conf(X_1)$ and $C_2\subseteq \Conf(X_2)$, we define operator $\oplus$ as follows
 $$C_1\oplus C_2\coloneqq C_1 \cup C_2 \cup \{\,(H_1\oplus H_2,i_1+i_2)\ \colon\ (H_1,i_1)\in C_1, (H_2,i_2)\in C_2,\textrm{ and they are mergeable}\},$$
 where the value $i_1+i_2$ is replaced with $\infty$ in case it exceeds $k-1$.

 Based on the previous observation, it is easy to see that this operator satisfies the desired property:
 $\conf((G_1,X_1)\oplus (G_2,X_2))=\conf(G_1,X_1)\oplus \conf(G_2,X_2)$ for all boundaried graphs $(G_1,X_1)$ and $(G_2,X_2)$
 whose union is defined. That the operator $\oplus$ defined above is commutative and associative is obvious.
 Finally, the value of $C_1\oplus C_2$ can be computed in time $\zeta(|X|)^{\Oh(1)}$ by inspecting all pairs $((H_1,i_1),(H_2,i_2))\in C_1 \times C_2$,
 whose number is bounded by $\zeta(|X_1|)\zeta(|X_2|) \leq \zeta(|X|)^2$, and applying the formula above.
\end{clproof}

\begin{claim}\label{cl:idempotent}
 The configuration scheme $(\Conf,\conf)$ is idempotent with witness $\tau(x)=x+2$.
\end{claim}
\begin{clproof}
 Consider any $X\subseteq \Omega$ and a multiset $\Mm$ whose elements are subsets of $\Conf(X)$. Suppose that there is $C \in \Mm$ such that for each $c\in C$,
 there are at least $|X|+2$ elements $D\in \Mm\setminus\{C\}$ such that $c\in D$. Let $S\coloneqq \bigoplus (\Mm\setminus \{C\})$.
 We need to prove that $S = S \oplus C$.

 That $S \subseteq S \oplus C$ is directly implied by the definition of operator $\oplus$. To prove that $S \oplus C \subseteq S$, let us consider any configuration $(H, i) \in S \oplus C$; we need to argue that in fact $(H,i)\in S$.

 From the definition of $\oplus$ there exists a multiset of configurations $M = \{(H_1, i_1), (H_2, i_2), \ldots, (H_m, i_m)\}$ for some  $m \leq |\Mm|$,
 with each configuration in $M$ chosen from some distinct element of multiset $\Mm$, such that $H = \bigoplus_{j=1}^m H_j$ and either $i = \sum_{j=1}^m i_j$ in case $i<\infty$, or $\sum_{j=1}^m i_j\geq k$ in case $i=\infty$.
 In particular, graphs $H_j$ for $j\in \{1,\ldots,m\}$ are pairwise mergeable.
 Note that $H=\bigoplus_{j=1}^m H_j$ is a linear forest on a vertex set of size $|X|+2$, hence it has at most $|X|+1$ edges. As graphs $H_j$ have pairwise disjoint edge sets due to being mergeable, we conclude that all but at most $|X|+1$ graphs $H_j$ have empty edge sets. Since in the definition of a configuration we required that emptiness of the edge set entails that the second coordinate is $0$, for those graphs $H_j$ for which $E(H_j)=\emptyset$ we also have $i_j=0$.
 Now observe that configurations $(H_j,i_j)$ with $E(H_j)=\emptyset$ and $i_j=0$ can be safely removed from $M$ without changing the union of configurations in $M$. Thus, by restricting $M$ if necessary, we may assume that $|M|\leq |X|+1$.

 Now, if none of the configurations from $M$ were selected from $C$, then $(H, i) \in S$ and we are done.
 On the other hand, if some configuration $(H_j, i_j)$ was selected from $C$, then by the assumptions on $C$ and the fact that $|M|\leq |X|+1$, there is at least one other element $D \in \Mm\setminus \{C\}$,
 such that no other configuration in $M$ was selected from $D$ and $(H_j, i_j) \in D$. Therefore, we can select $(H_j, i_j)$ from $D$ instead of $C$, which again implies that $(H, i) \in S$.
\end{clproof}

Claims~\ref{cl:composable} and~\ref{cl:idempotent} verify that the scheme $(\Conf,\conf)$ has all the required properties. This concludes the proof of Lemma~\ref{lem:schem-kpath}.
\end{proof}

\newcommand{\Gb}{\mathbf{G}}
\newcommand{\Hb}{\mathbf{H}}

\paragraph*{Maintaining a scheme.}
We next show that whenever a graph property admits a tractable configuration scheme, it can be efficiently maintained in a dynamic graph of bounded treedepth. Let $\Pi$ be a graph property that is recognized by a tractable configuration scheme $(\Conf,\conf)$ with polynomial-time computable witnesses~$\zeta(\cdot)$ and $\tau(\cdot)$. Let $G$ be a graph and $F$ be a recursively connected elimination forest of $G$. We enrich the data structure $\Dt[F,G]$ presented in Section~\ref{sec:data-structure} to the data structure $\Dt^\Pi[F,G]$ as follows.

 For each $w\in V(G)$, define the graph
 $$G_w\coloneqq \left(\,\desc_F(w)\cup \SReach_{F,G}(w),\ \{\,e\in E(G)\ \colon\ e\cap \desc_F(w)\neq \emptyset\,\}\,\right).$$
 In other words, the vertex set of $G_w$ consists of the descendants of $w$ plus $\SReach_{F,G}(w)$, while in the edge set we include only those edges of $G$ that are incident on vertices of $\desc_F(w)$.
 Thus, $\SReach_{F,G}(w)$ is an independent set in $G_w$. Further, we define the boundaried graph
 $$\Gb_w\coloneqq \left(\,G_w,\ \SReach_{F,G}(w)\,\right).$$

 In addition to all the data stored in $\Dt[F,G]$, in $\Dt^\Pi[F,G]$ we include the following. For each vertex~$u$, subset $X\subseteq \SReach_{F,G}(u)\cup \{u\}$, $i\in \{1,\ldots,d\}$, and configuration $c\in \Conf(X)$,
 we store the {\em{mug}} $\bucket[u,X,i,c]$ defined as follows:
 $$\bucket[u,X,i,c]\coloneqq \{\,w\in \bucket[u,X,i]\ \colon\ c\in \conf(\Gb_w)\,\}.$$
 In other words, the mug $\bucket[u,X,i,c]$ comprises all vertices $w$ from the bucket $\bucket[u,X,i]$ for which $c$ is realized in $\Gb_w$.
 Note that the mugs are not necessarily disjoint, in particular one vertex may be stored in up to $|\Conf(X)|\leq \zeta(d)$ mugs. Some vertices may even not belong to any mug. Similarly as for $\Dt[F,G]$ structure, we only store nonempty mugs, so the storage space used for the mugs is bounded by $\Oh(n \cdot \zeta(d))$.

 Similarly as for the buckets, the mugs are represented as doubly linked lists. In the lists corresponding to mugs we only store indices of the required vertices, representing their copies, while the actual objects corresponding to vertices are stored in the buckets as before. Each vertex object $w$ in bucket $\bucket[u,X,i]$, besides storing pointers to the next and the previous element in $\bucket[u,X,i]$, also stores $ \zeta(d)$ additional pointers: for each $c\in \Conf(X)$, we store the pointer to the position of an element in $\bucket[u,X,i,c]$ containing index of $w$, or null pointer if the $w$ does not belong to $\bucket[u,X,i,c]$.
 Thus, whenever we remove a vertex $w$ from its bucket, we may also remove it from all the mugs to which it belongs in time $\Oh(\zeta)$. These pointers occupy space $\Oh(n \cdot \zeta(d))$. So the total space for $\Dt^\Pi[F,G]$ is $\Oh(n \cdot (d+ \zeta(d)))$.

 \newcommand{\mmb}{\mathsf{member}}

 Finally, $\Dt^\Pi[F,G]$ also stores a boolean flag $\mmb$, which is set to true if and only if $G\in \Pi$. Note that this flag can be computed by checking whether $\conf(G,\emptyset)=\oplus_{r\in \roots_F} \conf(\Gb_r)$ contains a final configuration.
 It is again clear that $\Dt^{\Pi}[F,G]$ can be initialized for an edgeless graph $G$ in $\Oh(n)$ time, because there are additionally $\Oh(n)$ empty mugs to initialize.

 We now explain how the mugs are maintained upon updates of $\Dt^\Pi[F,G]$. For this, it will be again convenient to speak about partial data structures $\Dt^{\Pi}[R,G/K]$, where $K$ is a subset of vertices of $G$ and $R$ is an elimination forest of $G-K$. We define them in the same way as in Section~\ref{sec:data-structure}, with the exception that each bucket $\bucket[u,X,i]$ is enriched with mugs $\bucket[u,X,i,c]$ for $c\in \Conf(X)$ as in the definition of $\Dt^{\Pi}[\cdot,\cdot]$. We now argue that suitable analogs of Lemmas~\ref{lem:trim-implement},~\ref{lem:extend-implement}, and~\ref{lem:update-conf} hold. Note that in the following statements, the configuration scheme $(\Conf,\conf)$ is considered fixed.

 \begin{lemma}\label{lem:trim-implement-scheme}
 Suppose $G$ is a graph, $F$ is a recursively connected elimination forest of $G$ of height at most $d$, and $K$ is a prefix of $F$. Then given on input the data structure $\Dt^\Pi[F,G]$, one can in time $\Oh(2^d\cdot d\cdot |K|\cdot \zeta(d))$ modify $\Dt^\Pi[F,G]$ to obtain the partial data structure $\Dt^\Pi[F-K,G/K]$. Moreover, in the obtained structure $\Dt^\Pi[F-K,G/K]$, the list $\appendices$ has length at most $1+2^d\cdot |K|$.
\end{lemma}
\begin{proof}
 Perform exactly the same modifications as described in the proof of Lemma~\ref{lem:trim-implement}, and additionally do the following:
 \begin{itemize}[nosep]
  \item For each $u\in K$, remove $u$ also from all the mugs in which it is contained. Note that this boils down to removing the single list element corresponding to $u$ not just from one list representing the bucket containing $u$,
 but also from at most $\zeta(d)$ lists representing the mugs containing $u$.
  \item When renaming bucket $\bucket[u,X,i]$ to $\bucket[\bot,X,i]$, rename also all the mugs of the form $\bucket[u,X,i,c]$ to $\bucket[\bot,X,i,c]$. Note that there are at most $\zeta(d)$ such mugs.
 \end{itemize}
 It is straightforward to see that these modifications turn $\Dt^\Pi[F,G]$ into $\Dt^\Pi[F-K,G/K]$. The bound on the length of $\appendices$ can be argued as in the proof of Lemma~\ref{lem:trim-implement}.
\end{proof}

\begin{lemma}\label{lem:extend-implement-scheme}
 Suppose $H$ is a graph, $K$ is a subset of vertices of $H$, and $F^K$ is an elimination forest of $H[K]$ of height at most~$d$. Suppose further that $R$ is a recursively connected elimination forest of $H-K$ of height at most $d$ that is attachable to $(H,F^K)$. Let $\wh{F}$ be the extension of $F^K$ via $R$. Then given on input $H[K]$, $F^K$, and the partial data structure $\Dt^\Pi[R,H/K]$, one can in time $2^{\Oh(d)}\cdot |K|^{\Oh(1)}\cdot \tau(d)\zeta(d)^{\Oh(1)}$ modify $\Dt^\Pi[R,H/K]$ to obtain the data structure $\Dt^\Pi[\wh{F},H]$.
\end{lemma}
\begin{proof}
We augment the procedure that modifies $\Dt[R,H/K]$ to $\Dt[\wh{F},H]$ that was described in the proof of Lemma~\ref{lem:extend-implement}. We denote $\tau\coloneqq \tau(d)$ and $\zeta\coloneqq \zeta(d)$; recall that these can be computed in time $d^{\Oh(1)}$.

Recall that the first step of the procedure of Lemma~\ref{lem:extend-implement} was to rename the buckets from the list $\appendices$ so as to model attaching trees $R_r$ for $r\in \roots_R$ in the construction  of $\wh{F}$. We apply the same renaming scheme: whenever a bucket $\bucket[\bot,X,i]$ is renamed to $\bucket[m,X,i]$, this renaming applies also to all the mugs $\bucket[\bot,X,i,c]$ that are sub-lists of $\bucket[\bot,X,i]$. Note that there are at most $\zeta$ such mugs per bucket.
 Recall that the key observation in the proof of Lemma~\ref{lem:extend-implement} was that after the renaming, all the data stored for vertices $w\notin K$ did not require further updating, and even the buckets $\bucket[u,\cdot,\cdot]$ for
 $u\in K$ were as they should be in $\Dt[\wh{F},H]$, except they were lacking vertices of $K$.
 Observe that now, the same also applies to the mugs: mugs $\bucket[w,\cdot,\cdot,\cdot]$ for $w\notin K$ do not require updating, while mugs $\bucket[u,\cdot,\cdot,\cdot]$ for $u\in K\cup \{\bot\}$
 are as they should be in $\Dt^\Pi[\wh{F},H]$,
 except they lack vertices of $K$.

 Next, we may compute the values $\SReach(w)$, $\Up(w)$, $\height(w)$ for $w\in K$ and appropriately fill up the buckets $\bucket[w,\cdot,\cdot]$ for $w\in K\cup \{\bot\}$ exactly as in the proof of Lemma~\ref{lem:extend-implement}.
 Hence, it remains to fill up the mugs $\bucket[w,\cdot,\cdot,\cdot]$ for $w\in K\cup \{\bot\}$ by inserting the lacking vertices of~$K$.
 Similarly as in the proof of Lemma~\ref{lem:update}, for this it suffices to add each $u\in K$ to the mug
 \begin{equation}\label{eq:hamster}
 \bucket[\pnt_{F^K}(u),\SReach(u),\height(u),c]\qquad\textrm{for each }c\in \conf(\Hb_u).
 \end{equation}
 Here, $\Hb_u$ is a suitable boundaried graph defined as in the description of $\Dt^\Pi[\cdot,\cdot]$, but with respect to the graph $H$ and its elimination forest $\wh{F}$.
 Note that this can be easily done in time $\Oh(\zeta)$ provided we have computed the set $\conf(\Hb_u)$.

 We now present a procedure that updates the mugs $\bucket[w,\cdot,\cdot,\cdot]$ for all $w\in K\cup \{\bot\}$ by processing vertices $u\in K$ in a bottom-up manner over the forest $F^K$.
 When processing $u$ we assume that all $v\in \chld_{F^K}(u)$ have already been inserted in appropriate mugs as prescribed in~\eqref{eq:hamster}, that is, all the mugs $\bucket[u,\cdot,\cdot,\cdot]$ are already
 correctly constructed. Based on this we compute $\conf(\Hb_u)$, so that $u$ itself can be inserted to appropriate mugs as prescribed in~\eqref{eq:hamster}.

 First, we construct a set~$W$ of vertices with $W\subseteq \chld_{F'}(u)$ as follows:
 for each $X\subseteq \SReach(u)\cup \{u\}$, $i\in \{1,\ldots,d\}$, and $c\in \Conf(X)$, include in $W$ the first $\tau$ elements of the mug $\bucket[u,X,i,c]$, or all of them in case their number is at most $\tau$.
 Note that this can be done in time $\Oh(\tau)$ per considered mug, so in total time $\Oh(2^d\cdot d \tau\zeta)$ per vertex $u$. Also, we have $|W|\leq 2^d\cdot d \tau\zeta$.
 Next, we construct the multiset
 $$\Mm\coloneqq \{\{\,\conf(\Hb_v)\ \colon\ v\in W\,\}\}.$$
 This can be done in time $\Oh(|W|\cdot \zeta)$ as follows: for each $v\in W$, we deduce $\conf(\Hb_v)$ by inspecting the list element of $v$ and checking in which mugs it is contained.

 Let $\mathbf{I}_{uu'}$ be the boundaried graph $((\{u,u'\},\{uu'\}),\{u,u'\})$; that is, it consists only of two boundary vertices $u,u'$ and the edge $uu'$.
 We finally compute $\conf(\Hb_u)$ using the following formula:
 \begin{equation}\label{eq:walrus}
   \conf(\Hb_u) = \forget\left(\quad \bigoplus_{u'\in \Up(u)} \conf(\mathbf{I}_{uu'})\ \oplus\ \bigoplus_{D\in \Mm} D,\quad u\quad \right).
 \end{equation}
 Note that formula~\eqref{eq:walrus} can be computed in time $$(d+|\Mm|)\cdot \zeta^{\Oh(1)}=2^d\cdot d \tau\zeta^{\Oh(1)} ,$$
 because it involves $\Oh(d+|\Mm|)$ operations $\oplus$ and $\forget$, plus $\Oh(d)$ operations $\conf(\cdot,\cdot)$ applied to a two-vertex graph: each of these operations can be carried out in time $\zeta^{\Oh(1)}$
 due to the efficient composability of $(\Conf,\conf)$. Once $\conf(\Hb_u)$ is computed, the vertex $u$ can be added to appropriate mugs as described in~\eqref{eq:hamster} in time $\Oh(\zeta)$.

 It remains to argue that formula~\eqref{eq:walrus} is correct. First, observe that
 $$
   \Hb_u = \forget\left(\quad \bigoplus_{u'\in \Up(u)} \mathbf{I}_{uu'}\ \oplus\ \bigoplus_{v\in \chld_{F'}(u)} \Hb_v,\quad u\quad \right).
 $$
 Hence, by the composability of $(\Conf,\conf)$ we have
 \begin{equation}\label{eq:seal}
   \conf(\Hb_u) = \forget\left(\quad \bigoplus_{u'\in \Up(u)} \conf(\mathbf{I}_{uu'})\ \oplus\  \bigoplus_{v\in \chld_{F'}(u)} \conf(\Hb_v),\quad u\quad \right).
 \end{equation}
 However, the construction of $W$ and the idempotence of $(\Conf,\conf)$ implies that
 \begin{equation}\label{eq:penguin}
   \bigoplus_{D\in \Mm} D = \bigoplus_{v\in W} \conf(\Hb_v) = \bigoplus_{v\in \chld_{F'}(u)} \conf(\Hb_v).
 \end{equation}
 Now~\eqref{eq:seal} and~\eqref{eq:penguin} imply the correctness of~\eqref{eq:walrus}.

 \medskip

 This concludes the description of updating the mugs.
 To see that the time complexity of the update is as promised, note that the time spent on processing a single $u\in K$ as above is bounded by $2^d\cdot d \tau\zeta^{\Oh(1)}$.
 Hence, the total time complexity of $2^{\Oh(d)}\cdot |K|^{\Oh(1)}\cdot \tau\zeta^{\Oh(1)}$ follows.

 We are left with recomputing the $\mmb$ flag.
 In the paragraphs above, we have described the computation of $\conf(\Hb_u)$ for any vertex $u$ based on the access to correctly updated mugs $\bucket[u,\cdot,\cdot,\cdot]$,
 in time $2^d\cdot d \tau\zeta^{\Oh(1)}$.
 We can apply the same reasoning for $u=\bot$, and thus compute within the same running time the value $\conf(\Hb_\bot)=\conf(H,\emptyset)$.
 To verify whether $H\in \Pi$, which is the new value of $\mmb$, it suffices to check whether whether $\conf(H,\emptyset)$ contains one of final configurations of $(\Conf,\conf)$.
\end{proof}

 \begin{comment}
\begin{lemma}\label{lem:extension-implementation-conf}
 Let $G$ and $H$ be graphs on the same vertex set $V$ and $K\subseteq V$ be a vertex subset such that $E(G)\setminus \binom{K}{2}=E(H)\setminus \binom{K}{2}$. Let $F$ be a recursively connected elimination forest of $G$ such that the height of $F$ is at most $d$ and $K$ is a prefix of $F$. Further, let $F^K$ be an elimination forest of $H[K]$ of height at most $d$. Suppose that $R\coloneqq F-K$ is an elimination forest of $H-K$ that is attachable to $(H,F^K)$, and let $\wh{F}$ be the extension of $F^K$ via $R$. Then given on input $H[K]$, $F^K$, and the data structure $\Dt^\Pi[F,G]$, one can in time $2^{\Oh(d)}\cdot |K|^{\Oh(1)}\cdot \tau(d)\zeta(d)^{\Oh(1)}$ modify $\Dt^\Pi[F,G]$ to obtain the data structure $\Dt^\Pi[\wh{F},H]$.
\end{lemma}
\begin{proof}
 We apply all the operations needed for updating $\Dt[F,G]$ to $\Dt[\wh{F},H]$ in the same manner as in the proof of Lemma~\ref{lem:extension-implementation}.
 It remains to update the mugs and the $\mmb$ flag. We write $\tau\coloneqq \tau(d)$ and $\zeta\coloneqq \zeta(d)$; note that these can be computed in time $d^{\Oh(1)}$.

 The first step in updating $\Dt[F,G]$ to $\Dt[\wh{F},H]$ was to remove each $u\in K$ from the bucket in which it resides.
 When performing this operation we also remove $u$ from all the mugs to which $u$ belongs.
 Note that this boils down to removing the single list element corresponding to $u$ not just from one list representing the bucket containing $u$,
 but also from at most $\zeta$ lists representing the mugs containing $u$.

 The next step in updating $\Dt[F,G]$ to $\Dt[\wh{F},H]$ was to rename the buckets $\bucket[u,\cdot,\cdot]$ for $u\in K$ so as to model re-attaching trees $F_a$ for $a\in \App_F(K)$ in the construction
 of $\wh{F}$. We apply the same renaming scheme: whenever a bucket $\bucket[u,X,i]$ is renamed to $\bucket[m,X,i]$, this renaming applies also to all the mugs $\bucket[u,X,i,\cdot]$ that are sub-lists of $\bucket[u,X,i]$.
 Recall that the key observation in the proof of Lemma~\ref{lem:update} was that after the renaming, all the data stored for vertices $w\notin K$ did not require updating, and even the buckets $\bucket[u,\cdot,\cdot]$ for
 $u\in K$ were as they should be in $\Dt[\wh{F},H]$, except they were lacking vertices of $K$.
 Observe that now, the same also applies to the mugs: mugs $\bucket[w,\cdot,\cdot,\cdot]$ for $w\notin K$ do not require updating, while mugs $\bucket[u,\cdot,\cdot,\cdot]$ for $u\in K\cup \{\bot\}$
 are as they should be in $\Dt^\Pi[\wh{F},H]$,
 except they lack vertices of $K$. This is because for $w\notin K$ we have $\Hb_w=\Gb_w$, where
 $\Hb_w$ is the boundaried graph defined analogously to $\Gb_w$, but with respect to the graph $H$ and its elimination forest $\wh{F}$.

 Hence, it remains to update the mugs $\bucket[w,\cdot,\cdot,\cdot]$ for $w\in K\cup \{\bot\}$ by inserting the lacking vertices of~$K$.
 Similarly as in the proof of Lemma~\ref{lem:update}, for this it suffices to add each $u\in K$ to the mug
 \begin{equation}\label{eq:hamster}
 \bucket[\pnt_{F^K}(u),\SReach(u),\height(u),c]\qquad\textrm{for each }c\in \conf(\Hb_u).
 \end{equation}
 Note that this can be easily done in time $\Oh(\zeta)$ provided we have computed the set $\conf(\Hb_u)$.

 We now present a procedure that updates the mugs $\bucket[w,\cdot,\cdot,\cdot]$ for all $w\in K\cup \{\bot\}$ by processing vertices $u\in K$ in a bottom-up manner over the forest $F^K$.
 When processing $u$ we assume that all $v\in \chld_{F^K}(u)$ have already been inserted in appropriate mugs as prescribed in~\eqref{eq:hamster}, that is, all the mugs $\bucket[u,\cdot,\cdot,\cdot]$ are already
 correctly constructed. Based on this we compute $\conf(\Hb_u)$, so that $u$ itself can be inserted to appropriate mugs as prescribed in~\eqref{eq:hamster}.

 First, we construct a set~$W$ of vertices with $W\subseteq \chld_{F'}(u)$ as follows:
 for each $X\subseteq \SReach(u)\cup \{u\}$, $i\in \{1,\ldots,d\}$, and $c\in \Conf(X)$, include in $W$ the first $\tau$ elements of the mug $\bucket[u,X,i,c]$, or all of them in case their number is at most $\tau$.
 Note that this can be done in time $\Oh(\tau)$ per considered mug, so in total time $\Oh(2^d\cdot d \tau\zeta)$ per vertex $u$. Also, we have $|W|\leq 2^d\cdot d \tau\zeta$.
 Next, we construct the multiset
 $$\Mm\coloneqq \{\{\,\conf(\Hb_v)\ \colon\ v\in W\,\}\}.$$
 This can be done in time $\Oh(|W|\cdot \zeta)$ as follows: for each $v\in W$, we deduce $\conf(\Hb_v)$ by inspecting the list element of $v$ and checking in which mugs it is contained.

 Let $\mathbf{I}_{uu'}$ is the boundaried graph $((\{u,u'\},\{uu'\}),\{u,u'\})$; that is, it consists only of two boundary vertices $u,u'$ and the edge $uu'$.
 We finally compute $\conf(\Hb_u)$ using the following formula:
 \begin{equation}\label{eq:walrus}
   \conf(\Hb_u) = \forget\left(\quad \bigoplus_{u'\in \Up(u)} \conf(\mathbf{I}_{uu'})\ \oplus\ \bigoplus_{D\in \Mm} D,\quad u\quad \right).
 \end{equation}
 Note that formula~\eqref{eq:walrus} can be computed in time $$(d+|\Mm|)\cdot \zeta^{\Oh(1)}=2^d\cdot d \tau\zeta^{\Oh(1)} ,$$
 because it involves $\Oh(d+|\Mm|)$ operations $\oplus$ and $\forget$, plus $\Oh(d)$ operations $\conf(\cdot,\cdot)$ applied to a two-vertex graph: each of these operations can be carried out in time $\zeta^{\Oh(1)}$
 due to the efficient composability of $(\Conf,\conf)$. Once $\conf(\Hb_u)$ is computed, the vertex $u$ can be added to appropriate mugs as described in~\eqref{eq:hamster} in time $\Oh(\zeta)$.

 It remains to argue that formula~\eqref{eq:walrus} is correct. First, observe that
 $$
   \Hb_u = \forget\left(\quad \bigoplus_{u'\in \Up(u)} \mathbf{I}_{uu'}\ \oplus\ \bigoplus_{v\in \chld_{F'}(u)} \Hb_v,\quad u\quad \right).
 $$
 Hence, by the composability of $(\Conf,\conf)$ we have
 \begin{equation}\label{eq:seal}
   \conf(\Hb_u) = \forget\left(\quad \bigoplus_{u'\in \Up(u)} \conf(\mathbf{I}_{uu'})\ \oplus\  \bigoplus_{v\in \chld_{F'}(u)} \conf(\Hb_v),\quad u\quad \right).
 \end{equation}
 However, the construction of $W$ and the idempotence of $(\Conf,\conf)$ implies that
 \begin{equation}\label{eq:penguin}
   \bigoplus_{D\in \Mm} D = \bigoplus_{v\in W} \conf(\Hb_v) = \bigoplus_{v\in \chld_{F'}(u)} \conf(\Hb_v).
 \end{equation}
 Now~\eqref{eq:seal} and~\eqref{eq:penguin} imply the correctness of~\eqref{eq:walrus}.

 \medskip

 This concludes the description of updating the mugs.
 To see that the time complexity of the update is as promised, note that the time spent on processing a single $u\in K$ as above is bounded by $2^d\cdot d \tau\zeta^{\Oh(1)}$.
 Hence, the total time complexity of $2^{\Oh(d)}\cdot |K|^{\Oh(1)}\cdot \tau\zeta^{\Oh(1)}$ follows.

 We are left with updating the $\mmb$ flag.
 In the paragraphs above, we have described the computation of $\conf(\Hb_u)$ for any vertex $u$ based on the access to correctly updated mugs $\bucket[u,\cdot,\cdot,\cdot]$,
 in time $2^d\cdot d \tau\zeta^{\Oh(1)}$.
 We can apply the same reasoning for $u=\bot$, and thus compute within the same running time the value $\conf(\Hb_\bot)=\conf(H,\emptyset)$.
 To verify whether $H\in \Pi$, which is the new value of $\mmb$, it suffices to check whether whether $\conf(H,\emptyset)$ contains one of final configurations of $(\Conf,\conf)$.
\end{proof}
\end{comment}

\begin{lemma}\label{lem:update-conf}
  Suppose that we have access to the data structure $\Dt^\Pi[F,G]$, where $G$ is a graph and $F$ is a recursively optimal elimination forest $G$ of height at most $d$.
 Let $H$ be a graph obtained from $G$ by inserting or removing a single edge, given as input.
 Then one can in $2^{\Oh(d^2)}\cdot \tau(d)\zeta(d)^{\Oh(1)}$ time either conclude that $\td(H)>d$, or modify $\Dt^\Pi[F,G]$ to obtain the data structure $\Dt^\Pi[\wh{F},H]$ where $\wh{F}$ is some recursively optimal elimination forest of $H$ of height at most $d$.
\end{lemma}
\begin{proof}
 We apply the same reasoning as in Lemma~\ref{lem:update}, except that we use of Lemmas~\ref{lem:trim-implement-scheme} and~\ref{lem:extend-implement-scheme} instead of Lemmas~\ref{lem:trim-implement} and~\ref{lem:extend-implement}, respectively.
\end{proof}

From Lemma~\ref{lem:update-conf} we immediately obtain the following conclusion.

\begin{lemma}\label{lem:scheme-maintain}
 Let $\Pi$ be a graph property that is recognized by a tractable configuration scheme with polynomial-time computable witnesses~$\zeta(\cdot)$ and $\tau(\cdot)$.
 Then there exists a data structure that maintains a dynamic graph $G$ of treedepth at most $d$ under edge insertions and deletions with update time $2^{\Oh(d^2)}\cdot \tau(d)\zeta(d)^{\Oh(1)}$
 while offering a query on whether $G\in \Pi$ in time $\Oh(1)$.
 Upon inserting an edge that breaks the invariant $\td(G)\leq d$, the data structure detects this and refuses to carry out the operation. The data structure uses $\Oh(n (d+\zeta(d)))$ memory.
 The initialization of the data structure for an edgeless $n$-vertex graph takes time $\Oh(n)$.
\end{lemma}

Finally, by combining Lemmas~\ref{lem:schem-kpath} and~\ref{lem:scheme-maintain} we immediately obtain the following.

\begin{lemma}\label{lem:kpath-bnd-td}
 There exists a data structure that maintains a dynamic graph $G$ of treedepth smaller than $k$ under edge insertions and deletions with update time $2^{\Oh(k^2)}$
 while offering a query on whether $G$ contains a simple path on $k$ vertices in time $\Oh(1)$.
 Upon inserting an edge that breaks the invariant $\td(G)<k$, the data structure detects this and refuses to carry out the operation. The data structure uses $\Oh(n \cdot 2^{\Oh(k \log k)})$ memory.
 The initialization of the data structure for an edgeless $n$-vertex graph takes $\Oh(n)$ time.
\end{lemma}

Let us remark that by combining Lemma~\ref{lem:scheme-maintain} with Lemma~\ref{lem:mso-tractable} in the same manner, we may recover the result of Dvo\v{r}\'ak et al.~\cite{DvorakKT14}:
for every fixed $\MSO_2$-definable property $\Pi$, there is a data structure that for a dynamic graph of treedepth at most $d$ maintains the information about $\Pi$-membership with update time $f(d)$, for some function $f$.

\begin{comment}
\section{Automata}\label{sec:automata}

We will work with labeled graphs and labeled forests. For a finite alphabet $\Sigma$, a $\Sigma$-labelled graph is a pair $(G,\lambda)$, where $G$ is a graph and $\lambda\colon V(G)\to \Sigma$
is a labeling of the vertices of $G$ with elements of $\Sigma$. Similarly for labeled forests.

We now define automata suitable for our needs, which are {\em{nondeterministic threshold automata}}. The following notation will be convenient.
For $\tau\in \N$, let $[\tau^+]\coloneqq \{0,1,\ldots,\tau,\infty\}$. Then for $m\in \N$, we define
$$\dw{m}{\tau}\coloneqq \begin{cases}m & \textrm{if }m\leq \tau \\ \infty & \textrm{otherwise} \end{cases}$$
For a function $f\colon X\to \N$, we define $\dw{f}{\tau}$ as the composition of $f$ and the $\dw{m}{\tau}$ operator.
Also, $(X\to Y)$ denotes the set of functions from $X$ to $Y$.

\begin{definition}
 Fix a finite alphabet $\Sigma$. A {\em{nondeterministic threshold automaton}} over $\Sigma$ is a tuple $\Aa=(Q,\tau,\zeta,\zeta)$, where
 \begin{itemize}[nosep]
  \item $Q$ is a finite set of states;
  \item $\tau\in \N$ is the {\em{threshold}};
  \item $\zeta \subseteq (Q\to [\tau^+])\times \Sigma\times Q$ is the {\em{transition relation}}; and
  \item $\zeta\subseteq (Q\to [\tau^+])$ is the {\em{accepting relation}}.
 \end{itemize}
 The {\em{size}} of automaton $\Aa$ is $|Q|+\tau$.

 A {\em{run}} of automaton $\Aa$ on a $\Sigma$-labeled forest $F$ is a function $\rho\colon V(F)\to Q$ satisfying the following property:
 for each $u\in V(F)$, if $f_u\colon Q\to \N$ is such that $f_u(q)=|\{v\in \chld(u)\colon \rho(v)=q\}|$ for all $q\in Q$, and $a$ is the label of $u$, then
 $(\dw{f_u}{\tau},a,\rho(u))\in \zeta$.
 A run $\rho$ is {\em{accepting}} if the following property holds: if $g\colon Q\to \N$ is such that $g(q)=|\{v\in \roots\colon \rho(v)=q\}|$ for all $q\in Q$, then
 $\dw{g}{\tau}\in \zeta$.
 The language {\em{recognized}} by $\Aa$ comprises of all $\Sigma$-labelled forests $F$ such that there is an accepting run of $\Aa$ on $F$.
\end{definition}

Now suppose that $G$ is a $\Sigma$-labeled graph and $F$ is an elimination forest of $G$ of depth at most $k$.
Let
$$\Sigma[k] = \Sigma\times \left(\{1,\ldots,k-1\}\to \{0,1\}\right).$$
We now obtain a $\Sigma[k]$-labeled forest $F[k]$ from $F$ by setting labels of vertices as follows:
for every vertex $u\in V(G)$, the label $u$ in $F[k]$ is the pair $(a,f)$, where $a$ is the label of $u$ in $G$ and $f$ is a function from $\{1,\ldots,k-1\}$ to $\{0,1\}$
such that $f(i)=1$ if and only if $\depth(u)>i$ and $u$ is adjacent in $G$ to its ancestor at depth $i$. Note that thus, $F[k]$ contains all the information about edges of $G$, and hence it can be understood as a concise
representation of $G$ in the form of a labeled tree.

Given this description, we can define recognizability of graphs of bounded treedepth by finite automata.

\begin{definition}
Let $\Pi$ be a graph property, that is, a set of graphs. For $k\in \N$, we shall say that $\Pi$ is {\em{$k$-$\td$-recognized}} by a nondeterministic threshold automaton $\Aa_k$ over $\Sigma[k]$ if the following holds:
for every graph $G$ and elimination forest $F$ of $G$ of depth at most $k$, $\Aa$ accepts $F[k]$ if and only if $G\in \Pi$.
Property $\Pi$ is {\em{$k$-$\td$-recognizable}} if there exists a nondeterministic threshold automaton $\Aa_k$ that recognizes $\Pi$ as above, and simply {\em{$\td$-recognizable}} if it is $k$-$\td$-recognizable for every $k\in \N$.
\end{definition}

It is well known that $\MSO_2$-definable properties are $\td$-recognizable in the sense above.

\begin{lemma}
 Every $\MSO_2$-expressible graph property $\Pi$ is $\td$-recognizable.
 Moreover, given $k\in \N$ and an $\MSO_2$ sentence $\varphi$ defining $\Pi$, a nondeterministic threshold automaton $\Aa_k$ that $k$-$\td$-recognizes $\Pi$ can be computed.
\end{lemma}

\todo[inline]{We probably need to prove the lemma above, as there is no place where this is stated explicitly. But this will be a combination of a few known things.}

The next lemma shows that membership in $\td$-recognizable properties can be efficiently maintained in the dynamic setting. The proof relies on a modification of the data structure provided in Section~\ref{sec:data-structure}.

\begin{lemma}
 Let $k\in \N$ and $\Pi$ be a graph property that is $k$-recognized by an nondeterministic threshold automaton $\Aa_k=(Q,\tau,\zeta,\zeta)$.
 Then membership in $\Pi$ for a dynamic graph $G$ of treedepth at most $k$ can be maintained with update time $2^{\Oh(k^2)}\cdot (|Q|k)^{|Q|k}$.
\end{lemma}
\begin{proof}
 TODO
\end{proof}
\end{comment}


TITLE: $1+4^n+7^n$ is divisible by $3$ for all $n \in \mathbb{N}$
QUESTION [4 upvotes]: Prove that $1+4^n+7^n$ is divisible by $3$ for all $n \in \mathbb{N}$.

I have to do it with induction.
So I got my start, for $n=0$: We have $1+4^0+7^0 = 1+1+1 = 3$ and that's clearly divisible by $3$.
Then I have to do the induction, so I assume that $1+4^k+7^k$ is divisible by 3, and then look at $1+4^{k+1}+7^{k+1}$. Though I'm stuck here, I have to be able to write it like $1+4^k+7^k + \text{(something)}$ or $(1+4^k+7^k)*\text{(something)}$, I guess, but can't figure out what.

REPLY [0 votes]: Other people have answered, but since you are asking for tips about induction and how to find the inspiration to solve it... This is how I'd try to solve it if I had no idea where it was heading.
I have $1 +4^{k+1} + 7^{k+1}$ and I want to express it in terms of $1+4^{k} + 7^k$.  Well, the only thing I see at first is $4^{k+1} = 4^k*4$ and the same for 7.  So I try it and see where it goes.
$1 + 4^k*4 + 7^k*7$.
Okay, that's close but the pesky extra terms are in the way.  That $4^k*4$ is too big with that extra 4.  I want to reduce to multiples of 3.  Can I break this down in terms of multiples of 3 while keeping the $4^k$ but mucking around with the four to get it in terms of 3?
Well, 4 = 3+1, so $1 + 4^k*4 = 1 + 4^k(3 + 1) = 1 + 4^k*3 + 4^k$. Good. I've got the $4^k$ isolated!  I've added an extra $3*4^k$ but that's okay as it's a multiple of 3.
Let's do the same thing with the $7^k*7$.  7 = 2*3 + 1.  So
$1+4^k*4 + 7^k*7 = 1 + 4^k(3 + 1) + 7^k(2*3 + 1) = 1 + 3*4^k + 4^k + 2*3*7^k + 7^k = 1 + 4^k + 7^k + 3*4^k + 2*3*7^k$.
Now that extra mess is just a bunch of multiples of 3s.
$1+4^k*4 + 7^k*7 =1 + 4^k + 7^k + 3*4^k + 2*3*7^k = (1 + 4^k + 7^k) + 3*(4^k + 2*7^k)$.
And that's it.


TITLE: "Discrete" Statistical Mechanics vs QM
QUESTION [0 upvotes]: Is there a categorical difference between "discretized" statistical mechanics and quantum mechanics from a theory perspective?
For example, we can count possible configurations of a system using the binomial formula when position and time are discretized. I showed in this post that this state counting leads us to the familiar result for an $NVE$ ensemble in statistical mechanics when Stirling's approximation is applied.
Or, stated another way, is discretizing the methods in statistical mechanics satisfactory in reproducing the main results of QM?

REPLY [2 votes]: Since neither space nor time are generically discrete in quantum theories, it's not clear to me to which results you are referring.
Furthermore, the fundamental distinction between classical and quantum theories is the presence of incompatible observables in the latter (represented in the standard formulation of QM by non-commuting linear operators). The discretization (or lack therof) of e.g. the spatial degrees of freedom for a system would not affect this distinction.


TITLE: Can these rules be used to solve this logarithm?
QUESTION [2 upvotes]: I saw a video on logarithms saying if there is a limit where $x$ approaches $\pm\infty$ of some fraction, then we can solve by using these rules:

If the largest power on the top and bottom are the same, then the limit is the division of the leading coefficients;
If the largest power is on the bottom, then the limit is $0$;
if the largest power is on the top then there is no horizontal asymptote.

For example, $\lim_{x\to\infty}\frac{4x+2}{2x+8}$ is $\frac{4}{2}$ or $2$ because the powers of $x$ are the same and we divide the leading coefficients.
Another one: $\lim_{x\to-\infty}\frac{x+11}{x^3+16}$ is $0$ because the largest power is on the bottom.
My question: How do I compute the limit $\lim_{x\to\infty}\frac{\log x}{x^{1/k}}$? This is particularly difficult for me because of the arbitrary variable $k$, and the fact that the largest power on top ($1$) is only greater than $\frac{1}{k}$ for all $k > 1$.
So there's a case where they can both be the same (where $k=1$ in which case we divide the leading coefficients which is 1), or the case where the largest power is on top ($k>1$), in which case there is no horizontal asymptote.

REPLY [1 votes]: Hint: Use L'Hopital's Rule.${}$
I.e.
$$\lim_{x \to \infty}\frac{\log x}{x^{1/k}}=\lim_{x \to\infty}\frac{\frac{d}{dx}(\log x)}{\frac{d}{dx}(x^{1/k})}.$$


TITLE: How do I express $y = 1 - e^{-ax^b}$ as a linear function in terms of $y$, $x$, $a$, and $b$?
QUESTION [0 upvotes]: I tried using the log rules and eventually got to $\ln(\ln(1-y)) = \ln(-a) + b\ln(x)$, but $\ln(-a)$ is obviously not defined across all $a$. This assumes that $x\ge 0$ and that $y<1$.

REPLY [0 votes]: You are done up to $\ln (1-y)=-ax^b$ but from now, different cases are considerable. If $a=0$ then $y=1$ which is the trivial case. Otherwise, we multiply the sides of the equation by $-\text{sgn}(a)$ to obtain$$-\text{sgn}(a)\ln(1-y)=|a|\cdot x^b$$since both sides are always non-negative we can take $\ln$ from the sides and write $$\ln\Big(-\text{sgn}(a)\ln(1-y)\Big)=\ln|a|+b\cdot\ln x$$


TITLE: How to get the bound of a summation changed from $e^x$?
QUESTION [0 upvotes]: I meet a problem with calculating
$$
\frac{e^{-|\alpha|^2}}{\sum A_k^2}\left|\sum_{k=0}^{\infty} A_k \frac{(-\alpha)^k}{\sqrt{k!}}\right|^2\,.
$$
Only I know is the constrain that $\sum_{k=0}^{\infty} A_k \frac{\alpha^k}{\sqrt{k!}}=0$.
How to get the result, or the upper and lower bound?
(so sorry that I missed the square roof of $k!$)

REPLY [0 votes]: I believe the purpose of that constraint is to just prove that the series converges, as if that sequence converges, that alternating sequence does too.
Using @Dmitry's hint, you can get a decent upper bound with Cauchy-Schwartz:
$|U*V|^2 \le U^2 * V^2 $, which with $\sum U_k * V_k \le \sum U_k \sum V_k$ implies that $\sum |U * V|^2 = |\sum U_k|^2|\sum V_k|^2$
$$
\frac{e^{-|\alpha|^2}}{\sum A_k^2}\left|\sum_{k=0}^{\infty} A_k \frac{(-\alpha)^k}{k!}\right|^2 \le \frac{e^{-|\alpha|^2}}{\sum A_k^2}\left|\sum_{k=0}^{\infty} A_k \right|^2 \left| \sum_{k=0}^{\infty}\frac{(-\alpha)^k}{k!}\right|^2
$$
$$
\le \frac{e^{-|\alpha|^2}}{\sum A_k^2}(\sum_{k=0}^{\infty} A_k^2) \left| \sum_{k=0}^{\infty}\frac{(-\alpha)^k}{k!}\right|^2
$$
$$
= e^{-|\alpha|^2} \left|\sum_{k=0}^{\infty}\frac{(-\alpha)^k}{k!}\right|^2
$$
$$
= e^{-|\alpha|^2} (e^{-\alpha})^2
$$
$$
= e^{-|\alpha|^2 - 2\alpha}
$$
The simplest lower bound would be zero. This could occur for $\alpha = 0$ or specific $A$'s, whether it makes $lim_{n->\infty} \sum A_k^2 = \infty$ or the alternating sequence sum is pushed to zero somehow.


TITLE: Why does the universal enveloping algebra not have zero-divisors?
QUESTION [9 upvotes]: Let $\mathfrak{g}$ be a finite-dimensional Lie algebra, and denote by $U(\mathfrak{g})$ its universal enveloping algebra. It appears to be a consequence of the Poincaré-Birkhoff-Witt Theorem that $U(\mathfrak{g})$ has no zero-divisors. All sources I look at consider this to be either obvious or an easy exercise. But to be honest I'm baffled by this problem.
Attempt 1: Take a basis $e_1,\ldots,e_n$ of $\mathfrak{g}$, so that $U(\mathfrak{g})$ is generated by all terms of the form $e_1^{k_1} \cdots e_n^{k_n}$. Take two elements $x$ and $y$ in $U(\mathfrak{g})$, and suppose $x y = 0$. Our goal is to show that $x$ or $y$ is trivial. Thanks to Poincaré-Birkhoff-Witt, $x$ and $y$ are a finitely sum of the form
$$x = \sum_{k_1,\ldots,k_n} a_{k_1\cdots k_n} e_1^{k_1} \cdots e_n^{k_n}$$
and
$$y = \sum_{k_1,\ldots,k_n} b_{k_1 \cdots k_n} e_1^{k_1} \cdots e_n^{k_n}$$
We can then expand the product $xy$, and for each product of the form
$$e_1^{k_1} \cdots e_n^{k_n} e_1^{k'_1} \cdots e_n^{k'_n}$$
we can use the rule $e_i e_j + e_j e_i = [e_i,e_j]$ finitely many times to find an expression of it with respect to the basis that PBW gives us. Working all this out, the expression for $xy$ entirely gets out of hand, and it is not at all clear that it won't vanish for non-trivial $x$ and $y$.
Attempt 2: It is often hinted that you should use the associated graded ring of $U(\mathfrak{g})$ in some way. Many times it is stated that, as a consequence of PBW, this graded ring is a polynomial ring, and that therefore there aren't zero divisors. Both logical steps elude me, and I have no idea how to proceed in this direction.

REPLY [7 votes]: The trick is that you can look at just the highest-degree terms.
 Note that $$e_1^{k_1}\dots e_n^{k_n}\cdot e_1^{j_1}\dots e_n^{j_n}=e^{k_1+j_1}\dots e_n^{k_n+j_n}+\text{lower degree terms}$$ since all the other terms come from replacing two of the factors by their bracket and thus have lower degree.  So the highest degree part of $x\cdot y$ is just obtained by multiplying the highest degree parts of $x$ and $y$ as if the $e_i$ all commuted (i.e., treating them as variables in an ordinary polynomial ring).  Since a polynomial ring in $n$ variables has no zero divisors, the highest degree part of $x\cdot y$ is nonzero (assuming $x$ and $y$ are nonzero) and thus $x\cdot y$ is nonzero.
Or, without picking a basis, if $x$ has degree $d$ and $y$ has degree $e$, we look at the image $x'$ of $x$ in $A_d$ and the image $y'$ of $y$ in $A_e$ where $A$ is the associated graded algebra of $U(\mathfrak{g})$.  By definition of the ring structure on $A$, $x'\cdot y'$ is the image of $xy$ in $A_{d+e}$.  If $A$ has no zero divisors and $x$ and $y$ are nonzero, then $x'$ and $y'$ are nonzero and thus $x'y'$ is nonzero, so $xy$ must be nonzero.  (This argument shows more generally that if the associated graded ring of a filtered ring has no zero divisors, then neither does the original ring.)