TITLE: a limit property at infinity
QUESTION [2 upvotes]: Let $k\in(0,1)$ is fixed and $L$ is a finite value. Is it possible to say if
$\lim_{x\to\infty}f(x)=L$ then $\lim_{x\to\infty}f(kx)=L.$

REPLY [2 votes]: By definition we have $\lim\limits_{x\to\infty}f(x)=L$ means
$$\forall \epsilon>0,\; \exists A>0,\; x>A\implies |f(x)-L|<\epsilon$$
so for the selected $\epsilon>0$, and for $B=kA$ we have $(kx>B\iff x>\frac Bk)\implies |f(kx)-L|<\epsilon$ hence we get $$\lim\limits_{x\to\infty}f(kx)=L$$


TITLE: Find $\frac{dz}{dt}$ if $z(x,y) = x^2y + xy^2$; $x(t) = 2 + t^4$; $y(t) = 1 - t^3$.
QUESTION [2 upvotes]: Find $\frac{dz}{dt}$ if $z(x,y) = x^2y + xy^2$; $x(t) = 2 + t^4$; $y(t) = 1 - t^3$.
I used the Chain Rule: $\frac{dz}{dt} = \frac{\partial z}{\partial x}\frac{dx}{dt} + \frac{\partial z}{\partial y}\frac{dy}{dt}$:
$$\frac{dz}{dt} = (2xy + y^2)(4t^3) + (x^2 + 2xy)(-3t^2)$$
I then substituted for the $x$'s and $y$'s to get the whole expression in terms of $t$'s and simplified to get
$$\frac{dz}{dt} = 8 -12t^2+ 6t^4 +12t^5- 14t^6 - 2t^7+t^8 + 10t^9  $$
Assuming this answer is correct, should my final answer be in terms of $t$ like this?

REPLY [0 votes]: Yes, I would say a polynomial of $t$ is an acceptable answer. I think there is a small error in your calculations but other than that the method is correct. Real answer should be$$
\frac{dz}{dt}=t^2(-24+20t+12t^3-42t^4+8t^5+10t^7-11t^8).
$$


TITLE: evaluating the limit $\lim_{x\to 0^+} \tan (2x + \pi/2)$.
QUESTION [0 upvotes]: Find :
$\lim_{x\to 0^+} \tan (2x + \pi/2)$
By looking at the graph of the function :
$f$ goes to $-\infty$  if x approaches 0 from right
and $f$ goes to $+\infty$  if x approaches 0 from left

But I am interested in finding the limit algebraically, without using its graph
If we substitute $0$ in the function, we get :
 $\lim_{x\to 0^+} \sin 0/\cos0 $ =$\lim_{x\to 0^+} 1/0 = \infty$ which is not correct
So, How to figure out that the limit goes to $-\infty$ as x approaches zero from right?

REPLY [1 votes]: You should get $$\lim_{x\to 0^+} \tan{\left( 2x + \tfrac\pi 2 \right)} = \lim_{x\to 0^+} \frac{\sin{\left( 2x + \tfrac\pi 2 \right)}}{\cos{\left( 2x + \tfrac\pi 2 \right)}} = \frac{1}{0^-} = -\infty$$
because we approach $\cos \frac \pi 2$ from angles greater than $\frac \pi 2$ where $\cos$ is negative.


TITLE: Prove that $\frac {a}{b+c} + \frac {b}{a+c}+ \frac {c} {a+b}=1$
QUESTION [0 upvotes]: Given $$\frac {a^2}{b+c} + \frac {b^2}{a+c}+ \frac {c^2} {a+b}=0,$$  prove that $$\frac {a}{b+c} + \frac {b}{a+c}+ \frac {c} {a+b}=1.$$

I tried but getting $\frac {a}{b+c} + \frac {b}{a+c}+ \frac {c} {a+b}=0$. How to do this?

REPLY [2 votes]: $$\sum\frac{a^2}{b+c}=0\iff\sum\left(\frac{a^2}{b+c}+a\right)=a+b+c$$
$$(a+b+c)\sum\frac a{b+c}=a+b+c$$
$$\iff(a+b+c)\left[-1+\sum\frac a{b+c}\right]=0$$


TITLE: Does an Elliptic Curve has to have a rational point by definition?
QUESTION [2 upvotes]: This is how an Elliptic Curve is defined by my professor, which also appears in Silverman and Tate's book Rational Points on Elliptic Curves. The set of solutions to the equation (over a field) $y^2 = x^3 + ax^2 + bx +c$ is an Elliptic curve.
Are there any curves of this form which don't have ANY rational points? Because if so, then the set of all rational points will be empty and since the set of rational points forms a group, and an empty set is not a group, there is a contradiction here.
Moreover, the way in which group law is defined in this book, it assumes that the curve has a rational point because it defines that very point to be the identity element.
So am I missing something in the definition because at some places online I see that it is required for the curve to have a $k-$ rational point? And if the definition that I am using is not wrong then how is the contradiction above resolved?

REPLY [3 votes]: You are right that an elliptic curve must always have a rational point, since at the very least you'll want to have a point that acts as the identity element.
Any elliptic curve can be put into Weiestrass form; with respect to this form, you always have the point at infinity, which is taken to be the identity element. Can you see how that is indeed a rational point?
In general, there are genus-1 curves without rational points, and a fortiori these cannot be put into Weierstrass form.


TITLE: Problem related to Fatou's Lemma (Measure theory)
QUESTION [1 upvotes]: Statement of the problem: Show that if $\{f_n\}_{n=1}^{\infty}$ is a sequence of non-negative measurable functions on $\mathbb{R}^d$, then for any $t>0$ we have:
$$m\left(\left\{x\in \mathbb{R}^d:\enspace \liminf_{n\to\infty}f_n(x)>t\right\} \right)
\leq  \liminf_{n\to\infty}m\left(\left\{x\in \mathbb{R}^d:\enspace f_n(x)>t\right\} \right).$$
Attempt/Discussion
When I first looked at the statement  I immediately thought of Fatou's Lemma which in this case would tell us that (directly following the statement of the Lemma):
$$\int_{\mathbb{R}^d}\liminf_{n\to\infty} f_n  dm\leq \liminf_{n\to\infty}\int_{\mathbb{R}^d}f_n dm.$$
We then have the relations (which can be proved from Fubini's Theorem):
$$ \int_{\mathbb{R}^d}\liminf_{n\to\infty} f_n  dm=\int_0^\infty m\left(\left\{x\in \mathbb{R}^d:\enspace \liminf_{n\to\infty}f_n(x)>t\right\} \right)dt$$
and
$$\int_{\mathbb{R}^d}f_n dm=\int_0^\infty m\left(\left\{x\in \mathbb{R}^d:\enspace f_n(x)>t\right\} \right)dt $$
This then implies
$$\int_0^\infty m\left(\left\{x\in \mathbb{R}^d:\enspace \liminf_{n\to\infty}f_n(x)>t\right\} \right)dt \leq \liminf_{n\to\infty}\int_0^\infty m\left(\left\{x\in \mathbb{R}^d:\enspace f_n(x)>t\right\} \right)dt.$$
Although this statement looks close, it is not the result of the statement. It seems that the statement in the problem Implies Fatou's lemma but not necessarily the other way around (I'm not sure yet). If anyone has any thoughts or ideas they would be appreciated!

REPLY [2 votes]: Note that $\liminf f_n(x) > t$ if and only if $f_n(x) > t$ for all but at most finitely many indices $n$. Thus $$\left\{x :  \liminf f_n(x) > t \right\} = \bigcup_{n=1}^\infty \bigcap_{k \ge n} \{x : f_k(x) > t\}.$$ Use continuity from below: $$m \left( \bigcup_{n=1}^\infty \bigcap_{k \ge n} \{x : f_k(x) > t\} \right) = \lim_{n \to \infty} m \left( \bigcap _{k \ge n} \{x : f_k(x) > t\} \right).$$ Since $$\bigcap_{k \ge n} \{f_k(x) > t\} \subset \{f_n(x) > t\}$$ you obtain
$$ \lim_{n \to \infty} m \left( \bigcap _{k \ge n} \{x : f_k(x) > t\} \right) = \liminf_{n \to \infty} m \left( \bigcap _{k \ge n} \{x : f_k(x) > t\} \right) \le \liminf_{n \to \infty} m(\{x : f_n(x) > t\}).$$


text:
\section{Overview}\label{sec:overview}

\subsection{Treedepth, elimination forests, and cores}\label{secov:cores}
In this subsection we give an overview of the material presented in Sections~\ref{sec:cores} and~\ref{sec:obstructions}.
Our first goal is to obtain a fine combinatorial understanding of elimination forests of optimum height, so that we will be able to efficiently recompute them upon edge insertions and deletions.

Recall that an {\em{elimination forest}} (or equivalently treedepth decomposition) of a graph $G$ is a rooted forest on the same vertex set as $G$ satisfying the following property: for every edge $uv$ of $G$, either $u$ is an ancestor of $v$ in $F$, or vice versa. Note that edges of $F$ do not need to be present in $G$. Elimination forests are graph decompositions underlying the parameter {\em{treedepth}}, defined as the minimum possible height of an elimination forest.
Note that an elimination forest of a connected graph is necessarily a tree.

 We will work with elimination forests that are in some sense also ``locally optimal'', as explained in the following definition. Here, for a forest $F$ and vertex $u\in V(F)$, by $F_u$ we denote the subtree of $F$ induced by $u$ and all its descendants. Also, $\desc_F(u)$ denotes the set of descendants of $u$ in $F$, including $u$ itself.

\begin{definition}
 An elimination forest $F$ of a graph $G$ is {\em{recursively optimal}} if for every vertex $u$, the graph $G[\desc_F(u)]$ is connected and has treedepth equal to the height of $F_u$.
\end{definition}

In other words, in a recursively optimal elimination forest $F$, each subtree $F_u$ is an optimum-height elimination tree of $G[\desc_F(u)]$. Thus, the height of a recursively optimal elimination forest $F$ always matches the treedepth of the graph, as $F$ needs to optimally decompose each connected component in a separate tree. It is easy to see that every graph has a recursively optimal elimination forest, and, up to technical details, such a forest can be computed in time $2^{\Oh(d^2)}\cdot n^{\Oh(1)}$ using the algorithm of Reidl et al.~\cite{ReidlRVS14}.

\medskip

From now on, let us fix a graph $G$ and assume, for simplicity, that $G$ is connected. Let $T$ be a recursively optimal elimination tree of $G$, say of height $d$. For a vertex $u$, we define the {\em{strong reachability set}} $\SReach(u)$ as the set $N_G(\desc_T(u))$, that is, $\SReach(u)$ consists of all (strict) ancestors of $u$ that have neighbors among $\desc_T(u)$. The intuition is that $\SReach(u)$ is the set to which the subtree $T_u$ is ``attached'' in $T$. In other words, if we temporarily removed $T_u$ from $T$ and wanted to attach it back, then the optimal way would be to find the deepest vertex $m$ of $\SReach(u)$ and attach $T_u$ by making $u$ a child of $m$. In this way, the conditions in the definition of an elimination forest are satisfied, while $T_u$ is attached as high as~possible.

A {\em{prefix}} of $T$ is an ancestor-closed subset of vertices of $T$. For a non-empty prefix $K$ of $T$, an {\em{appendix}} of $K$ is a vertex that does not belong to $K$, but whose parent already belongs to $K$. The set of appendices of $K$ will be denoted by $\App(K)$. The following definition is the cornerstone of our analysis.

\begin{definition}
 Let $q\in \N$. A non-empty prefix $K$ of $T$ is a {\em{$q$-core}} (of $(G,T)$) if the following property holds: for every appendix $a\in \App(K)$ and subset $X\subseteq \SReach(a)$ of size at most $2$, $a$ has at least $q$ distinct siblings $w$ in $T$ such that $w\in K$, $X\subseteq \SReach(w)$, and $\height(T_w)\geq \height(T_a)$.
\end{definition}

Before we continue, let us verify that we can always find very small cores.

\begin{lemma}\label{lemov:small-core}
 For each $q\geq 2$, there is a $q$-core of size at most $(qd)^{\Oh(d)}$.
\end{lemma}
\begin{proof}[Sketch]
 Consider the following recursive marking procedure that can be applied to a vertex $u\in V(G)$. For each set $X$ consisting of at most $2$ ancestors of $u$ (including $u$), consider all the children $w$ of $u$ satisfying $X\subseteq \SReach(u)$, and mark $q$ of them with the largest values of $\height(T_w)$, or all of them if their number is smaller than $q$. Then apply the procedure recursively on each marked child of $u$. It is straightforward to see that if $K$ comprises of all vertices that got marked after applying the procedure to the root of $T$, then $K$ is a $q$-core. Since for a marked vertex $u$ we also mark at most $q\cdot (1+d+\binom{d}{2})=\Oh(qd^2)$ children of $u$, and $T$ has height at most $d$, it follows that $|K|\leq (qd)^{\Oh(d)}$.
\end{proof}

Let us now explain the idea behind the definition of a core. Suppose $K$ is a $q$-core, $a\in \App(K)$, and $w$ is a sibling of $a$ satisfying the property from the definition for some $X=\{x,y\}\subseteq \SReach(a)$. Since $T$ is recursively optimal, $G[\desc_T(w)]$ is connected. As $x,y\in \SReach(w)=N_G(\desc_T(w))$, we conclude that in $G$ there is a path $P^{x,y}_w$ such that $P^{x,y}_w$ has endpoints $x$ and $y$, and all the internal vertices of $P^{x,y}_w$ belong to $\desc_T(w)$. As we have $q$ such siblings $w$, we can find $q$ such paths $P^{x,y}_w$, and they will be pairwise internally vertex-disjoint. It can now easily be seen that, provided $q\geq d$, such a set of $q$ paths forces that in {\em{every}} elimination tree of $G$ of depth at most $d$, $x$ and $y$ have to be in the ancestor-descendant relation. Since none of the paths $P^{x,y}_w$ intersects $\desc_T(a)$, this conclusion can be drawn even if we removed all the vertices of $\desc_T(a)$ from $G$. This reasoning can be applied for every pair $\{x,y\}\subseteq \SReach(a)$. After fixing technical details, this amounts to the following statement.

\begin{lemma}\label{lemov:straight}
 Suppose $K$ is a $d$-core and $T^K$ is any elimination tree of the graph $G[K]$ of height at most $d$. Then for each $a\in \App(K)$, the set $\SReach(a)$ is {\em{straight}} in $T^K$, that is, all the vertices of $\SReach(a)$ lie on one root-to-leaf path in $T^K$.
\end{lemma}

\begin{figure}
  \centering
  \includegraphics[width=0.6\textwidth]{figures/overview_0-eps-converted-to.pdf}
  \caption{Treedepth cores and their replaceable elimination trees.}\label{fig:choinka}
\end{figure}

Supposing that $K$ is a $d$-core, let $R=T-K$ be the rooted forest obtained by removing all the vertices of $K$ from $T$; see Figure~\ref{fig:choinka}. Note that $R$ is an elimination forest of the graph $G-K$. Then the conclusion of Lemma~\ref{lemov:straight} means for {\em{every}} elimination tree $T^K$ of $G[K]$ of height at most $d$ (possibly very different from $T[K]$),  $R$ is {\em{attachable}} to $T^K$ in the following sense: for each tree $S$ of $R$, the set $N_G(V(S))$ is straight in $T^K$. Recalling our previous intuition, this suggests that we can compute a new elimination forest $\wh{T}$ of $G$ by attaching $R$ ``below'' $T^K$ as follows (note that $\App(K)$ coincides with the set of roots of $R$). For each $a\in \App(K)$, we let $m$ be the deepest vertex of $\SReach(a)$ in $T^K$, and we attach the tree $R_a=T_a$ by making $a$ a child of $m$. It is straightforward to see that if $R$ is attachable to $T^K$, then the tree $\wh{T}$ obtained in this manner is indeed an elimination tree of $T$; we shall call it the {\em{extension}} of $T^K$ via $R$.

We see that $\wh{T}$ constructed as above is indeed an elimination forest of $G$, but so far we cannot say much about its height. Fortunately, from the definition of a core we can also derive useful properties in this respect. In particular, this is why in this definition we insisted that for each of the distinguished siblings $w$ of $a$, the height of $F_w$ is not smaller than the height of $F_a$.

The intuition is as follows. Suppose $K$ is a $(d+1)$-core and $T^K$ is a recursively optimal elimination forest of $G[K]$ of height at most $d$. Consider any $a\in \App(K)$. By Lemma~\ref{lemov:straight}, the set $\SReach(a)$ is straight in $T^K$. Let then $m$ be the vertex of $\SReach(a)$ that is the deepest in $T^K$. Then, by the definition of the core we can find a set $W\subseteq K$ consisting of $d+1$ siblings $w$ of $a$ such that
$$m\in \SReach(w)\qquad\textrm{and}\qquad\td(G[\desc_T(w)])=\height(T_w)\geq \height(T_a)=\td(G[\desc_T(a)]).$$
Here, the first and the last equality follows from the recursive optimality of $T$. Through a fairly complicated inductive scheme, we can show for one of the trees $T_w$ for $w\in W$, the graph $G[K\cap \desc_T(w)]$ has same treedepth as $G[\desc_T(w)]$ and its vertex set is fully contained in a subtree $T^K_x$ for some $x$ that is a child of $m$ in $T^K$. This witnesses that $\height(T^K_x)\geq \height(T_w)\geq \height(T_a)$. We infer that attaching $T_a$ below $m$ in the construction of $\wh{T}$ --- the extension of $T^K$ via $R=T-K$ --- {\em{cannot}} increase the height of $\wh{T}$ above $\height(T^K)$. This is because after the attachment, there anyway is a subtree rooted at a sibling of $a$ whose height is not smaller than the height of $T_a$. We may conclude the following.

\begin{lemma}\label{lemov:extend}
 Let $K$ be a $(d+1)$-core and let $T^K$ be any elimination tree of $G[K]$ of height at most $d$. Let $R=T-K$ and let $\wh{T}$ be the extension of $T^K$ via $R$ (which is well-defined by Lemma~\ref{lemov:straight}). Then $\wh{T}$ is a recursively optimal elimination tree of $G$ and the height of $\wh{T}$ is equal to the height of $T^K$.
\end{lemma}

Recall that in the first place, we were interested in recomputing a recursively optimal elimination forest of a graph under edge insertions and edge deletions. Let then $H$ be a graph obtained from $G$ by either inserting an edge $uv$, or deleting an edge $uv$. By following the same reasoning that led us to Lemmas~\ref{lemov:straight} and~\ref{lemov:extend}, but additionally keeping track of the modified edge $uv$, we can prove the following.

\begin{lemma}\label{lemov:extend-update}
 Let $K$ be a $(d+2)$-core of $(G,T)$ that includes both $u$ and $v$, and let $T^K$ be any elimination tree of $H[K]$ of height at most $d$. Let $R=T-K$. Then $R$ is attachable to $T^K$. Moreover, if $\wh{T}$ is the extension of $T^K$ via $R$, then $\wh{T}$ is a recursively optimal elimination forest of $H$ whose height is equal to the height of $T^K$.
\end{lemma}

Note that in Lemma~\ref{lemov:extend-update} we require that $K$ is a $(d+2)$-core, while Lemma~\ref{lemov:extend} only assumed that $K$ is a $(d+1)$-core. This is because some of the witnessing structures, for instance paths $P^{x,y}_w$ considered in the reasoning leading to Lemma~\ref{lemov:straight}, might be affected by the removal of the edge $uv$. However, as this is just a single edge, adding $1$ to the requirement on the core suffices for the argument to go through.

Lemma~\ref{lemov:extend-update} suggests the following strategy for recomputing a recursively optimal elimination tree upon inserting or deleting an edge $uv$. Here, $H$ is the updated graph.
\begin{itemize}[nosep]
 \item Using the procedure described in the proof of Lemma~\ref{lemov:small-core}, compute a $(d+2)$-core $K$ of $T$ of size $d^{\Oh(d)}$. By modifying this procedure slightly, we may make sure that $u,v\in K$.
 \item Using the static algorithm of Reidl et al.~\cite{ReidlRVS14}, compute a recursively optimal elimination forest $T^K$ of $H[K]$. Since the treedepth of $H[K]$ does not exceed the treedepth of $H$, which in turn does not exceed $d+1$, this takes time $2^{\Oh(d^2)}$. Observe that if the treedepth of $H[K]$ turns out to be larger than $d$, then the same can be concluded about $H$.
 \item Letting $R=T-K$, compute $\wh{T}$: the extension of $T^K$ via $R$.
\end{itemize}
Then Lemma~\ref{lemov:extend-update} asserts that $\wh{T}$ is a recursively optimal elimination forests of $H$.

Note that this procedure readily can be implemented as a static algorithm, but the idea seems useful in the dynamic setting as well. This is because the forest $R$ --- which constitutes a vast majority of the graph, provided $d\ll n$ --- first gets detached from $T$ and then gets attached below $T^K$ while keeping its structure intact. In the next section, our goal will be to implement this detachment and attachment so that the internal data about $R$ does not need to be updated at all.

\medskip

Observe that from Lemma~\ref{lemov:extend} we may immediately derive the following conclusion: the subgraph induced by a $d$-core inherits the treedepth of the original graph.

\begin{lemma}\label{lemov:td-opt}
 Let $K$ be a $(d+1)$-core. Then the treedepth of $G[K]$ is equal to the treedepth of $G$.
\end{lemma}
\begin{proof}
 Let $T^K$ be an elimination forest of $G[K]$ of minimum height. By Lemma~\ref{lemov:extend}, there exists an elimination forest of $G$ of height equal to the height of $T^K$. This means that the treedepth of $G$ is not larger than the treedepth of $G[K]$. As the reverse inequality is obvious, the lemma follows.
\end{proof}

We note that in reality, we prove (the formal analogs of) Lemmas~\ref{lemov:extend} and Lemmas~\ref{lemov:td-opt} in the reverse order, as (a generalization of) Lemma~\ref{lemov:td-opt} is needed in the inductive scheme used in the proof of Lemma~\ref{lemov:extend}.

From Lemmas~\ref{lemov:small-core} and~\ref{lemov:td-opt} we may now immediately derive the improved bounds on minimal obstructions for bounded treedepth. Recall here that a graph $G$ is a minimal obstruction for treedepth $d$ if the treedepth of $G$ is larger than $d$, but every proper induced subgraph of $G$ has treedepth at most $d$.

\begin{theorem}\label{thmov:obstructions}
 Every minimal obstruction for treedepth $d$ has at most $d^{\Oh(d)}$ vertices.
\end{theorem}
\begin{proof}
 Let $G$ be a minimal obstruction for treedepth $d$. Clearly, $G$ is connected. As removing one vertex decreases the treedepth by at most $1$, the treedepth of $G$ is equal to $d+1$. Let $T$ be a recursively optimal elimination tree of $G$; then $T$ has height $d+1$. By Lemma~\ref{lemov:small-core}, we may find a $(d+1)$-core $K$ of $(G,T)$ of size~$d^{\Oh(d)}$. By Lemma~\ref{lemov:td-opt}, the treedepth of $G[K]$ is $d+1$. Since $G$ is a minimal obstruction, we necessarily have $K=V(G)$. So $G$ has $d^{\Oh(d)}$ vertices.
\end{proof}

\subsection{Dynamic treedepth data structure}\label{secov:data}

In this subsection we give an overview of the material presented in Sections~\ref{sec:data-structure} and~\ref{sec:dp}, in particular we explain the proof of Theorem~\ref{thm:td-data}. The idea is to design the dynamic treedepth data structure so that the detachment/attachment strategy described in the previous subsection can be implemented efficiently. We note that the internal organization of information in our data structure roughly follows the general strategy of Dvo\v{r}\'ak et al.~\cite{DvorakKT14}, but the approach we use to implement the update methods, which is based on the analysis of cores that we developed in the previous section, is completely new and different from~\cite{DvorakKT14}. This is the part of the reasoning that leads to the improvement.

Suppose that $G$ is the considered graph, say connected for simplicity, and $T$ is an elimination tree of $G$ of depth at most $d$. Suppose further that $G$ is updated by inserting or deleting an edge $uv$, and $H$ is the updated graph. As outlined in the previous subsection, we should compute a $(d+2)$-core $K$ of $(G,T)$ of size $d^{\Oh(d)}$, recompute a recursively optimal elimination forest $T^K$ of $H[K]$ using a static algorithm, and reattach $R\coloneqq T-K$ below $T^K$. Consider any appendix $a\in \App(K)$ and recall that reattaching $R_a=T_a$ boils down to making $a$ a child of the vertex of $\SReach(a)$ that is the deepest in $T^K$. Now comes the main observation: for any other appendix $a'\in \App(K)$ satisfying $\SReach(a')=\SReach(a)$, the tree $R_{a'}=T_{a'}$ will be attached at exactly the same place as $R_a$. Therefore, we can treat all trees $R_a$ with the same $\SReach(a)$ as one ``batch'', which will be detached from $T$ and reattached to $\wh{T}$ concurrently. Here, it is not hard to see that all the trees of this batch have the same parent in $T$, which obviously belongs to $K$.

We now implement this idea algorithmically. The tree $T$ is stored as follows. For every vertex $u$, we remember the parent of $u$ in $T$, $\SReach(u)$, and $\Up(u)\coloneqq \SReach(u)\cap N_G(u)$; the last set is used to represent the edge set of $G$. Further, $u$ remembers all its children, but these children are partitioned into {\em{buckets}} as follows: for each $X\subseteq \SReach(u)\cup \{u\}$ and $i\leq d$, we store the bucket
$$\bucket[u,X,i]\coloneqq \{\,v\in \mathsf{children}(u)\ \colon\ \SReach(v)=X\textrm{ and }\height(T_v)=i\,\}.$$
Thus, buckets $\bucket[u,\cdot,\cdot]$ form a partition of the children of $u$ and there are at most $2^d\cdot d$ buckets associated with $u$. Buckets are represented using doubly-linked lists.

Inserting or deleting the edge $uv$ can now be implemented as follows:
\begin{itemize}[nosep]
 \item Construct a $(d+2)$-core $K$ of size $d^{\Oh(d)}$ that includes $u$ and $v$. Having access to buckets, this can be done by simulating the marking procedure presented in Lemma~\ref{lemov:small-core} in time $d^{\Oh(d)}$.
 \item Apply the static algorithm of Reidl et al.~\cite{ReidlRVS14} to compute a recursively optimal elimination tree $T^K$ of~$H[K]$. This step takes time $2^{\Oh(d^2)}\cdot |K|^{\Oh(1)}=2^{\Oh(d^2)}$ and is the only bottleneck: all the other steps take time $d^{\Oh(d)}$. Also, if it turns out that $\height(T^K)>d$, then the treedepth of $H$ exceeds $d$ and the update should be rejected.
 \item Remove all vertices of $K$ from all the buckets. This can be done in time $\Oh(|K|)$ by remembering, for each vertex, a pointer to a list element representing it in the bucket to which it belongs.
 \item For each $u\in K$, $X\subseteq \SReach(u)\cup \{u\}$, and $i\leq d$, rename the bucket $\bucket[u,X,i]$ to $\bucket[m,X,i]$, where $m$ is the vertex of $\SReach(u)$ that is the deepest in $T^K$. Note that there are at most $|K|\cdot 2^d\cdot d=d^{\Oh(d)}$ buckets that need to be renamed in this way.
 \item Recompute the information for the vertices of $K$ and place them in appropriate buckets. This can be done in time $2^{\Oh(d)}\cdot |K|^{\Oh(1)}=d^{\Oh(d)}$  by a bottom-up traversal of $T^K$.
\end{itemize}
The key observation is that in such an implementation, the following assertion holds: for each renamed bucket $\bucket[u,X,i]$, all the values stored for vertices of trees $R_a$ for $a\in \bucket[u,X,i]$ do not need to be updated at all. The only exception are the parent pointers for vertices $a\in \bucket[u,X,i]$, which after renaming should all point to the new parent $m$. This can be easily remedied by storing one parent pointer per bucket, and changing it in a single operation. This concludes the proof of Theorem~\ref{thm:td-data}.

\paragraph*{Configuration schemes.} As mentioned in Section~\ref{sec:introduction}, the dynamic treedepth data structure can be conveniently augmented to maintain a run of a dynamic programming procedure on the stored elimination forest. This applies to a wide range of dynamic programming procedures, in particular those obtained for $\MSO_2$-expressible problems through the classic connection with tree automata. In Section~\ref{sec:dp} we present a general formalism of {\em{configuration schemes}} that can be used to formulate such dynamic programming procedures. To keep the overview simple, we now explain how this idea applies to \LPath.

Suppose $T$ is the maintained elimination tree and consider any $u\in V(G)$. Let $X=\SReach(u)$ and let $G_u$ be the subgraph of $G$ such that the vertex set of $G_u$ is $X\cup \desc_T(u)$, while the edge set of $G_u$ comprises of all the edges of $G$ that have an endpoint in $\desc_T(u)$. Note that, thus, $X$ forms an independent set in $G_u$. We now define a set $\Conf(X)$ of {\em{configurations}} on $X$: a configuration $c$ is a pair $(F,j)$, where $F$ is a {\em{linear forest}} (i.e. a forest of paths) on vertex set $X\cup \{s,t\}$, where $s,t$ are special vertices, and $j$ is an integer not larger than $k$ (the requested vertex count of the path). Note that $|\Conf(X)|\leq |X|^{\Oh(|X|)}\cdot (k+1)\leq d^{\Oh(d)}\cdot k$. Configuration $c=(F,j)$ is {\em{realizable}} in $G_u$ if in $G_u$ there is a family of paths $\{P_e\colon e\in E(F)\}$ of total length $j$ such that the paths $P_e$ are disjoint apart from endpoints in $X$, and the endpoints of $P_e$ match the endpoints of $e$. Here, the special vertices $s,t$ can be replaced with any vertices in $G_u$. Then with each $u\in V(G)$, we can associate the set $\conf(G_u)\subseteq \Conf(X)$ comprising configurations realizable in $G_u$. Whether $G$ contains a $k$-path can be determined by checking whether $\conf(G_r)$, where $r$ is the root of $T$, contains configuration $(F_{st},k-1)$, where $F_{st}$ has only one edge: $st$.

This configuration scheme has two important properties:
\begin{itemize}[nosep]
 \item {\em{Compositionality}}: $\conf(G_u)$ can be computed from the multiset $\{\{\conf(G_v)\colon v\in \chld(u)\}\}$.
 \item {\em{Idempotence}}: There is a threshold $\tau$ (equal to $d+2$) such that for the computation above, it is immaterial whether a configuration is realized in $\tau$ or more children of $u$ (see Section~\ref{sec:dp} for a formal~definition).
\end{itemize}
We show that these two basic properties alone are sufficient for augmenting the dynamic treedepth data structure so that with each $u\in V(G)$, we also implicitly store $\conf(G_u)$. This of course introduces factors depending on the configuration scheme to the update time, but in case \LPath and assuming $k\leq d$, these factors are dominated by the $2^{\Oh(d^2)}$ update time of the data structure.

The augmentation is done as follows. For every bucket $\bucket[u,X,i]$ stored in the data structure, we additionally store a {\em{mug}} $\bucket[u,X,i,c]$ for each configuration $c\in \Conf(X)$. This mug comprises all $v\in \bucket[u,X,i]$ for which $c\in \conf(G_v)$, and is organized as a doubly-linked list (a sublist of $\bucket[u,X,i]$). Note that each $v\in \bucket[u,X,i]$ can appear in multiple mugs, but the number of mugs is bounded by $|\Conf(X)|$, which depends only on $d$ and the configuration scheme in question. The set $\conf(G_v)$ corresponds to the set of mugs to which $v$ belongs. It is now not hard to maintain the mugs during updates using the assumptions of compositionality and idempotence, similarly as we do for buckets.

\subsection{Postponing insertions}

Using all the tools prepared so far for $d=k-1$,
we can implement a fully dynamic data structure that for a graph $G$, promised to be always of treedepth smaller than $k$, maintains an elimination forest of $G$ of height smaller than $k$ together with the answer to the query whether $G$ contains a $k$-path. Upon receiving an invariant-breaking edge insertion, the data structure rejects the update and reports this. We now use the technique of Eppstein et al.~\cite{EppsteinGIS96} to turn this into a data structure working without the promise.

We maintain the dynamic treedepth data structure $\Dt$ described above, which stores a subgraph $G'$ of $G$. Additionally, we have a queue $Q$ of edges whose insertions are postponed. We maintain the invariants: $G$ consists of $G'$ and all the edges stored in $Q$; $G'$ has treedepth smaller than $k$; and if $Q$ is non-empty, then $G'+e$ has treedepth at least $k$, where $e$ is the edge at the front of $Q$. Thus, if $Q$ is empty then $G'=G$. The query about a $k$-path can be implemented as follows: if $Q$ is empty then we can simply query $\Dt$, and otherwise the answer is $\true$, because $G$ has treedepth at least $k$. When inserting an edge, we either try to insert it into $\Dt$ in case $Q$ is empty, or we push it at the back of $Q$ otherwise. The former case may result in rejecting the insertion and pushing the edge into $Q$. Finally, when deleting an edge we either delete it from $\Dt$ or from $Q$, depending where it is currently stored. We may now need to perform a clean-up: iteratively pop an edge from the front of $Q$ and insert it into $\Dt$. This can take large worst-case time, but it is not hard to see that the amortized time remains constant. We use the dictionary to quickly locate edges within $Q$.

\subsection{Detecting cycles}

\CycleNoteSub

Finally, we show how the whole machinery can be put into motion to handle also the \LCycle problem. That is, we give an overview of the material presented in Sections~\ref{sec:splitting-merging},~\ref{sec:scheme-ms}, and~\ref{sec:cyc_det_ds}.

Recall that a biconnected graph of treedepth at least $k^2$ necessarily contains a simple cycle on at least $k$ vertices~\cite[Proposition~6.2]{NesetrilM12}. Hence, if $G$ does not contain a simple cycle on at least $k$ vertices --- and using the technique of Eppstein et al.~\cite{EppsteinGIS96} we can focus on this case --- then every biconnected component of $G$ has treedepth smaller than $k^2$. Therefore, in our data structure we maintain the partition $\Prt$ of $G$ into biconnected components and, for each $H\in \Prt$, the dynamic treedepth data structure $\Dt[H]$ for $d=k^2$, which stores $H$ together with some recursively optimal elimination tree $T_H$ of height at most $d$.

To efficiently handle the partition $\Prt$ upon updates, we maintain a spanning forest $\Upsilon$ of $G$ using the top tree data structure of Alstrup et al.~\cite{AlstrupIP,AlstrupJ}. This data structure supports adding and removing edges from $\Upsilon$ in time $\Oh(\log n)$, as well as the following two queries about a pair of vertices $u,v$:
\begin{itemize}[nosep]
 \item What is the distance between $u$ and $v$ in $\Upsilon$?
 \item If $u,v$ are in the same connected component of $\Upsilon$, return the path in $\Upsilon$ between $u$ and $v$.
\end{itemize}
These queries take time $\Oh(\log n)$ and $\Oh(\ell \log n)$, respectively, where $\ell$ is the length of the reported path.

Consider now the operation of inserting an edge $uv$. First, we check what is the distance between $u$ and $v$ in $\Upsilon$. If $u$ and $v$ are in different connected components of $\Upsilon$, and therefore also of $G$, then we add $uv$ to $\Upsilon$ and we add a new biconnected component consisting only of $uv$. If $u$ and $v$ are in the same connected component of $\Upsilon$, but the distance between them in $\Upsilon$ is at least $k-1$, then the insertion should be rejected: $uv$ would close a simple cycle of length at least $k$. Otherwise, in time $\Oh(k \log n)$ we can retrieve a path $P\subseteq \Upsilon$ with endpoints $u$ and $v$, and this path has length smaller than $k-1$.

It may happen that the edges of $P$ belong to different biconnected components of $G$. It is easy to see that then, the following should happen to the partition $\Prt$ after the insertion of $uv$: all the biconnected components containing edges of $P$ get merged into one biconnected component. To carry this out, we iterate through the (at most $k-2$) edges on $P$ and if two consecutive edges $xy$ and $yz$ belong to different biconnected components $H_1$ and $H_2$, then we merge $H_1$ and $H_2$. This requires merging the data structures $\Dt[H_1]$ and $\Dt[H_2]$, and in particular computing a recursively optimal elimination forest of the union of $H_1$ and $H_2$. We show that this can be done using the toolbox of cores as follows. Let $T_1$ and $T_2$ be the elimination trees of $H_1$ and $H_2$ stored in $\Dt[H_1]$ and $\Dt[H_2]$, respectively.
\begin{itemize}[nosep]
 \item First, we compute $(d+1)$-cores $K_1$ and $K_2$ of $(H_1,T_1)$ and $(H_2,T_2)$, respectively, each of size $d^{\Oh(d)}=k^{\Oh(k^2)}$. We make sure that $\{x,y\}\subseteq K_1$ and $\{y,z\}\subseteq K_2$.
 \item Letting $K\coloneqq K_1\cup K_2$, we compute a recursively optimal elimination forest $T^K$ of $G[K]$ using the static algorithm of Reidl et al.~\cite{ReidlRVS14}. This takes time $2^{\Oh(d^2)}=2^{\Oh(k^4)}$.
 \item We construct an elimination forest $\wh{T}$ of $H_1\cup H_2$ by attaching both the forests $T_1-K_1$ and $T_2-K_2$ below $T^K$, as in the extension operation.
\end{itemize}
It can be argued that $\wh{T}$ constructed in this manner is a recursively optimal elimination forest of $H_1\cup H_2$. Moreover, all of this can be done in time $2^{\Oh(d^2)}=2^{\Oh(k^4)}$ using our representation of the dynamic treedepth data structure. Note that since the length of $P$ is smaller than $k-1$, we perform at most $k-3$ such merges.

The operation of edge deletion is essentially symmetric: we need to split biconnected components instead of merging them, which can be done analogously. However, there is one issue: the deleted edge $uv$ may belong to $\Upsilon$, in which case it is pointless to query $\Upsilon$ for a $u$-to-$v$ path $P$ along which the splits should be performed. Fortunately, we show that in this case, we can retrieve a suitable path $P$ from the data structure $\Dt[H]$, where $H$ is the biconnected component that contains $uv$. Note that $P$ has length smaller than $k$, for otherwise together with $uv$ it would constitute a simple cycle of length at least $k$. Another caveat is that in order to maintain the invariant that $\Upsilon$ is spanning, after deleting $uv$ from $\Upsilon$ we may need to find a replacement edge and insert it into $\Upsilon$. Again fortunately, the retrieved path $P$ provides at most $k-2$ candidates for such a replacement edge.

config: arxiv


TITLE: Prove that $\sqrt{2}+\sqrt{3}+\sqrt{5}$ is irrational. Generalise this.
QUESTION [11 upvotes]: I'm reading R. Courant & H. Robbins' "What is Mathematics: An Elementary Approach to Ideas and Methods" for fun. I'm on page $60$ and $61$ of the second edition. There are three exercises on proving numbers irrational spanning these pages, the last is as follows.

Exercise $3$: Prove that $\phi=\sqrt{2}+\sqrt{3}+\sqrt{5}$ is irrational. Try to make up similar and more general examples.

My Attempt:

Lemma: The number $\sqrt{2}+\sqrt{3}$ is irrational. (This is part of Exercise 2.)

Proof: Suppose $\sqrt{2}+\sqrt{3}=r$ is rational. Then
$$\begin{align}
2&=(r-\sqrt{3})^2 \\
&=r^2-2r\sqrt{3}+3
\end{align}$$ is rational, so that
$$\sqrt{3}=\frac{r^2+1}{2r}$$ is rational, a contradiction. $\square$
Let $\psi=\sqrt{2}+\sqrt{3}$. Then, considering $\phi$,
$$\begin{align}
5&=(\phi-\psi)^2 \\
&=\phi^2-2\psi\phi+5+2\sqrt{6}.
\end{align}$$
I don't know what else to do from here.
My plan is/was to use the Lemma above as the focus for a contradiction, showing $\psi$ is rational somehow.
Please help :)
Thoughts:
The "try to make up similar and more general examples" bit is a little vague.

The question is not answered here as far as I can tell.

REPLY [1 votes]: Using the straightforward fact that the sum of two (or more) algebraic integers is an algebraic integer (see here), one has the following very short argument: since $\sqrt{2},\sqrt{3},\sqrt{5}$ are algebraic integers, their sum $A=\sqrt{2}+\sqrt{3}+\sqrt{5}$ must be also. Hence if $A$ is rational, it must be an integer. However, as a rudimentary estimate of the three square roots shows, we have $5 < A < 6$: contradiction.


TITLE: Group congruences: If the operation is preserved, do we get $a\sim b$ $\Rightarrow$ $a^{-1}\sim b^{-1}$?
QUESTION [5 upvotes]: Let $(G,*)$ be a group. Let $\sim$ be an equivalence relation such that
$$(\forall a,a',b,b'\in G)a\sim a', b\sim b' \Rightarrow a*b\sim a'*b'. \tag{*}$$
I.e., the equivalence relation $\sim$ respects the group operation.
Question. Does the condition $(*)$ necessarily imply that
$$(\forall a,b\in G) a\sim b \Rightarrow a^{-1}\sim b^{-1}, \tag{**}$$
i.e., the relation $\sim$ behaves well w.r.t. the inverses?
(If yes, how can we prove this? If it is not true, what are some counterexamples?)
This can be expressed also using the corresponding partition. The condition $(*)$ means that
$$[a]=[a'], [b]=[b'] \Rightarrow [a*b]=[a'*b'].$$
In the other words, we get a well-defined binary operation on the corresponding partition $G/\sim$. It is easy to see that in this way we get a monoid.
The condition $(**)$ says that the assignment $[a]\mapsto [a^{-1}]$ is also well-defined (=does not depend on the choice of the representative). So if $(**)$ is true, we have also inverses in $G/\sim$ and we get a group.
In several places I have seen mentioned in passing that if an equivalence relation fulfills $(*)$, the condition $(**)$ is true as well. For example, this is mentioned in the Wikipedia article Congruence relation (current revision). The definition there includes this condition, but the article mentions that "this can actually be proven from the other four, so is strictly redundant".
Similarly, if I checked Hungerford's Algebra (proof of Theorem 1.5 on page 27) or Jacobson's Basic Algebra I (Definition 1.4 on page 54 and the comments following this definition), they both define congruence only using $(*)$, but in the proof that we get a group they implicitly use that inverse is well-defined. (To make the question self-contained, I have copied the relevant parts from Jacobson's book below.)

This is how this is presented in Jacobson's book:

Definition 1.4. Let $(M,\cdot,1)$ be a monoid. A congruence (or congruence relation) $\equiv$ in $M$ is an equivalence relation in $M$ such that for any $a$, $a'$, $b$, $b'$ such that $a\equiv a'$ and $b\equiv b'$ on has $ab\equiv a'b'$. (In other words, congruences are equivalence relations which can be multiplied.)

After this definition, there is the definition of quotient monoid and an explanation why it actually is a monoid. For groups, the author mentions:

We can say a good deal more if $M=G$ is a group and $\equiv$ is a congruence on $G$. In the first place, in this case the quotient monoid $(\overline G,\cdot,\overline 1)$ is a group, since $\overline a\overline{a^{-1}}=\overline 1=\overline{a^{-1}}\overline a$. Hence every $\overline a$ is invertible and its inverse is $\overline{a^{-1}}$.

After this, the author proceeds to explain relationship between group congruences and normal subgroups.

REPLY [0 votes]: By definition, $\sim$ is a semigroup congruence on $G$. Thus $S = G/{\sim}$ is a semigroup and the map sending an element of $G$ to its $\sim$-class is a surjective semigroup morphism $f:G \to S$. Let us show that $S$ is actually a group and that $f$ is a group morphism. Let $s \in S$. Then $s = f(g)$ for some $g \in G$.

First, $f(1)$ is an identity of $S$: indeed $f(1)s = f(1)f(g) = f(1g) = f(g) = s$ and similarly $sf(1) = s$. Thus $S$ is a monoid.
Next, $sf(g^{-1}) = f(g)f(g^{-1}) = f(gg^{-1}) = f(1)$ and similarly $f(g^{-1})s = f(g^{-1})f(g) =f(1)$. This shows that $f(g^{-1})$ is the inverse of $s$. It follows that $S$ is a group. Moreover, since $f(g^{-1}) = (f(g))^{-1}$, $f$ is a group morphism.

To answer the initial question it suffices now to observe that $a \sim b$ if and only if $f(a) = f(b)$. Since $f$ is a group morphism, this latter condition yields $f(a^{-1}) =f(a)^{-1} = f(b)^{-1} = f(b^{-1})$ and thus $a^{-1} \sim b^{-1}$.


TITLE: Proof of $A \subset B \iff A\cap B=A \iff A \cup B = B$
QUESTION [1 upvotes]: I want to know if this proof is correct or if something needs to change.
I want to prove $A \subset B \iff A\cap B=A \iff A \cup B = B$
If $A \subset B$, then for every $a \in A$, we have $a \in B$ by definition of "$\subset$", thus $a \in A \cap B$. This shows that $A \subset A \cap B$. Now if $a \in A \cap B$ then $a \in A$ by definition of "$\cap$" and thus $A \cap B \subset A$. It follows that $A = A \cap B$.
If $A \cap B = A$, then for every $a \in A$,  we have $a \in A \cap B$ by definition of "$=$" and thus $a \in B$ by definition of "$\cap$". This shows that $A \subset B$.
If $A \cup B = B$ then
$\forall a :: a \in A \cup B \;\equiv\; a \in B $
$\equiv \forall a :: a \in A \lor a \in B \;\equiv\; a \in B $
$\equiv \forall a :: a \in A \;\Rightarrow\; a \in B$
$\equiv A \subset B$

REPLY [0 votes]: It suffices to show three implications:

$A \subseteq B$ implies $A \cap B = A$: suppose $A$ is a subset of $B$, then note that always $A \cap B \subseteq A$ by definition and $A \subseteq A \cap B$ because $x \in A$ implies $x \in B$ (by $A \subseteq B$) and so $x \in A \cap B$. So both inclusions hold and $A \cap B= A$ is shown.
$A \cap B = A$ implies $A \cup B = B$: so we assume the first equality holds, and we'll show the second: $B \subseteq A \cup B$ is trivial. And if $x \in A \cup B$, either $x \in B$ and we're done, or $x \in A = A \cap B$ (assumption) and so $x \in B$ also follows, hence $A \cup B \subseteq B$ and two inclusions give $B = A \cup B$, as required.
$A \cup B = B$ implies $A \subseteq B$: assume the equality holds and let $x \in A$. Then also $x \in A \cup B$ so by the assumption $x \in B$: we conclude $A \subseteq B$. That concludes the proof of the final implication.

This shows the three-way equivalence in the usual way.


TITLE: Finding the set of equations orthogonal to parabolas
QUESTION [0 upvotes]: The problem is to find the set of equations $\mathcal{G}$ where every equation in $\mathcal{G}$ is perpendicular to every equation in $\mathcal{F}$, where $\mathcal{F}$ consists of equations of the form $y = Ax$.
By plotting, I guessed that $\mathcal{G}$ will be the set of circles around the origin:
Plot: https://www.desmos.com/calculator/zazva0jlzo
How can I express the slope of this series at $(x,y)$? I tried using $A = y^2/x$, but this gives me $\mathcal{G} = \frac{x^3}3$.
From there I know to take the negative reciprical of the slope and solve the differential equation.

REPLY [1 votes]: It is not clear what exactly you want.
Instead of downvoting I would give a lead as a take off point for OT of parabolas $ y= A x^2$
If you carefully see desmos graph you made.. the extreme parabola cuts at around $70^0$, but not at $90^0.$
Now for parabola OT:
$$ y = A x^2 $$
$$ y^{'}= 2 A x $$
Eliminate $A$
$$\frac{2y}{x^2} =  \frac{y^{'}}{x} $$
$$\frac{2y}{x} =  \frac{y^{'}}{1} $$
negative reciprocal for OT's differential equation
$$\frac{2y}{x} =  \frac{{-1}}{y^{'}} $$
integrate and simplify
$$ -2 y dy = x dx$$
$$ x^2/2 + y^2 = c^2 $$
They are all ellipses of eccentricity $\dfrac{1}{\sqrt2}$. The other  $y = - A x^2$ below $x-$ axis not sketched.
Basically you addressed the problem, but going in different directions.. as it appears to me.
This way, now if you ask questions in the comments we will go somewhere..hopefully.


TITLE: Complex valued integral inequality
QUESTION [0 upvotes]: I am looking at the following post: Absolute Value of Complex Integral. I am wondering the following: if $f$ is continuous and $f(t) = r(t)e^{i\theta(t)}$ and we have strict equality:
\begin{equation}
|\int_a^bf(t)dt| = \int_a^b|f(t)|dt
\end{equation}
Is it true that$ |\int_a^b e^{i\theta(t)}dt| = \int_a^b|e^{i\theta(t)}|dt = b- a$?

REPLY [1 votes]: This is true if $f(t) \neq 0$ for all $t$. For a counter-example note that if $f=0$ then $r(t)=0$ and $\theta (t)$ is arbitrary. Take $\theta (t)=t$, $a=0$ and $b =2\pi$ then $\int_a^{b} e^{i\theta (t)} d\theta =0 \neq b-a$.
Proof when $f(t) \neq 0$ for all $t$: Let $s=|\int_a^{b} f(t)dt|$. Then $\int_a^{b} f(t)dt=se^{ic}$ for some real number $c$. We get $\int_a^{b} r(t)dt =s$ from the hypothesis. Hence $\int_a^{b} e^{-ic}f(t)dt =\int_a^{b} r(t)dt$. Taking real parts we get $\int_a^{b} (r(t)-\Re (e^{-ic}f(t)))dt=0$. The integrand is non-negative and continuous. Hence $r(t)= r(t) \Re (e^{-ic}e^{i\theta (t)})$ for all $t$. Since $r(t) \neq 0$ this gives $ \Re (e^{-ic}e^{i\theta (t)})=1$ for all $t$ which implies $e^{i\theta(t)}=e^{ic}$ for all $t$. The conclusion is now obvious.


TITLE: A problem on four kissing circles (Descartes Theorem)
QUESTION [0 upvotes]: Two circles $C_1$ and $C_2$ with radius $r_1$ and $r_2$ touching each other externally and both touching circle $C_3$ with radius $r_1+r_2$ internally. If another circle with radius $r_3$ touches all three circles such that $r_1, r_2, r_3$ are in $A.P.$ and $r_1\gt r_2 \gt r_3$ find $$\frac{r_1}{r_2}$$
I tried applying the Descartes' theorem but the equation so formed seemed to be nearly unsolvable. Any new method or improvement in the method of Descartes theorem is appreciated.

REPLY [1 votes]: Say $r_1 = k r_2$, so $r_3 = (2-k) r_2$. Observe first that the centres of $C_1$, $C_2$ and $C_3$ lie on a straight line, by considering the radii of each, so our diagram looks like this, where $D$ is the centre of $C_3$

From here, notice that $AD = r_1 + r_2 - r_3 = (2k-1)r_2$, and $CD= r_1 + r_2 - r_1 = r_2$. In particular, we know every length inside the triangle in terms of $r_2 $and $k$. Apply Stewart's Theorem and cancel $r_2^3$ to give $(k+1)k + (2k-1)^2 (k+1) = 4k + (3-k)^2$, which simplifies to $k^3 = 2$, so $k = \sqrt[3]{2} = \frac{r_1}{r_2}$.


TITLE: Is there a method to determine a prime number containing the first n digits?
QUESTION [2 upvotes]: For example, the number $10243$ is prime and contains the digits '0,' '1,' '2,' '3,' and '4.'  Similarly, the number $20143$ is prime.  Is there a method to determine whether a prime number exists that contains the first, say, $8$ digits?  Or whether a number exists that contains an arbitrary number of digits in order starting from an arbitrary number (say, $3, 4, 5, 6, 7$)?

REPLY [0 votes]: Based on your examples, its not clear if the prime number is allowed to contain digits other than those specified, or if each of the digits specified can be used more than once. Assuming the answer to both of those is "no":
The number $10235647$ is prime, and contains each of the digits $0$ through $7$ exactly once.
For any number with the digits $3,4,5,6,7$ arranged in some order, the sum of its digits will be $3+4+5+6+7 = 15$, and so, that number will be divisible by $3$, and thus, will not be prime.


TITLE: Time and Work: pipe and cistern related problem
QUESTION [2 upvotes]: Two pipes A and B fill up a half tank in $1.2$ hours. The tank was initially empty. Pipe B was kept open for half the time required by pipe A to fill the tank by itself . Then pipe A was kept open for as much time as was required by the pipe B to fill up $1/3$ of the tank by itself. It was found that the tank was $5/6$ full. The least time in which any of the pipes can the fill the tank fully is ?
Spoiler: The answer is $4$ hours.

REPLY [7 votes]: Let pipe $A$ fill the fraction $a$ of the tank per hour, and let pipe $B$ fill the fraction $b$ of the tank per hour. Then $A$ alone fills the tank in ${1\over a}$ hours and $B$ alone in ${1\over b}$ hours.
From the text we learn that $$1.2(a+b)={1\over2}\ .\tag{1}$$
Furthermore we are told that
$${1\over 2a} b+{1\over 3b} a={5\over6}\ ,$$
or
$$3b^2+2a^2=5ab\ .\tag{2}$$
From $(1$) we deduce $a={5\over12}-b$, and substituting this into $(2)$ leads to the quadratic equation
$$144 b^2-54b+5=0$$
with the solutions $$b_1={5\over24},\quad b_2={1\over6}\ .$$ The corresponding values for $a$ then come out to $$a_1={5\over12}-b_1={5\over24},\quad a_2={5\over12}-b_2={1\over4}\ .$$ It turns out that
$$\max\{a_1,a_2,b_1,b_2\}={1\over4}\ ,$$
which implies that the shortest time compatible with the text, in which any of the two pipes can the fill the tank, is $4$ hours.


TITLE: A $3 \times 3 \times 3$ cube has no Hamiltonian path starting at the corner.
QUESTION [1 upvotes]: We have a $3\times3\times 3$ cube which has $27$ cubes each $1\times1\times1$ stuck together as usual. $2$ cubes are neighbours if they have a common face. The corner cubes are the $8$ cubes at the corners of the big cube. Can the worm start from a corner cube and eat its neighbour cube, continuing until at the end the last cube eaten is the one in the center of the big cube which has 6 neighbour cubes?

REPLY [0 votes]: This appears as a question in Graph Theory in the sections discussing Hamiltonian graphs. A Hamiltonian graph is a graph containing a closed path which spans all the vertices of the graph. We can intuitively relate the vertices to be the cheese blocks. Hence if the graph constructed by assuming the cheese blocks to be vertices had a Hamiltonian path, the worm could traverse through it. Note I have mentioned a Hamiltonian path not a cycle. In the context of the proof, we need a Hamiltonian cycle hence we need to add a hypothetical edge between his first cheese block and the last cheese block(the vertex at the centre).
Any undergraduate level text in graph theory will have a theorem more or less like:
A non-Hamiltonian graph is  degree majorised by some $\mathbb C_{mn}$ $ \forall$ $m \in(0, {\frac n2}) $.
Where the $\mathbb C_{mn}$ graph is defined as $\mathbb K_m\land(\mathbb K_m^c + \mathbb k_{n-2m})$. Where $\mathbb K_m$ is a complete graph on m vertices.
It is easily seen that for some $m \in (0, 13)$  {e.g. m=5}$ $ there exists a $\mathbb C_{m27}$ that degree majorises our graph. Hence we conclude our graph is non-Hamiltonian, and there exists no way in which the worm can burrow his way through the cheese cube in the desired manner. For proof and better understanding of the theorem look up Graph Theory and Applications Chapter 4.