TITLE: Problem in understanding the solution of exact differential $M(x,y)dx + N(x,y)dy = du(x,y)$.
QUESTION [3 upvotes]: If $M(x,y)dx + N(x,y)dy = du(x,y)$, then it is an exact differential equation. For that to happen, $$\left(\dfrac{\partial M(x,y)}{\partial y}\right)_x =\left(\dfrac{\partial N(x,y)}{\partial x}\right)_y \tag1.$$
I was following Differential Equations by  Balachandra Rao, S. Staff to see how to find $u(x,y)$. For most of the part but one, I could conceive.
The proof goes using  the first part of $(1)$ after integrating it to get $$u(x,y) = \int M(x,y) dx + \phi (y).$$ In order to satisfy the second condition of $(1)$, there exists a certain $\phi (y)$. So, $$\frac{\partial u(x,y)}{\partial y} = \frac{\partial}{\partial y}\left[\int M(x,y) dx\right]+ \phi'(y)$$ which must be equal to $$N(x,y) = \frac{\partial}{\partial y}\left[\int M(x,y) dx\right]+ \phi'(y) \implies \phi'(y) = N(x,y) - \frac{\partial}{\partial y}\left[\int M(x,y) dx\right] .$$ LHS is independent of $x$; so RHS must also be independent of $x$; in order to verify this, we take the partial derivative of RHS w.r.t. $x$ : $$\frac{\partial}{\partial x} \left[N(x,y) - \frac{\partial}{\partial y}\left[\int M(x,y) dx\right]\right] = \dfrac{\partial N(x,y)}{\partial x} -\dfrac{\partial M(x,y)}{\partial y}= 0.$$ So, RHS is independent of $x$. Then by integrating, we get $$\phi(y) = \int\left[N(x,y) -\frac{\partial}{\partial y}\left[\int M(x,y) dx \right] \right]dy + C .$$ Putting the value of $\phi(y)$, we get $$u(x,y) = \int M(x,y) dx + \int\left[N(x,y) -\frac{\partial}{\partial y}\left[\int M(x,y) dx \right] \right]dy.$$ This is the value of $u(x,y)$ .
But the book presents the working rule as

A "working rule" convenient to apply for solving an exact differential equation is as follows: $$\underset{[y\; \text{const.}]}{\int M dx} + [\color{red}{\text{Terms of} \; N\; \text{not containing} \; x}] dy = c$$

See the red marked statement; $M(x,y)$ is not there, but in the derivation the parenthesis contained $\dfrac{\partial}{\partial y}\left[\int M(x,y) dx \right] $. As if it was excluded in the working rule without specifying any reason. If I break $$\int\left[N(x,y) -\frac{\partial}{\partial y}\left[\int M(x,y) dx \right] \right]dy$$ into $$\int N(x,y) dy - \int \frac{\partial}{\partial y}\left[\int M(x,y) dx \right] dy$$, then I get $$\int N(x,y) dy - \frac{\partial}{\partial y}\left[\int M(x,y) dx \right].$$ The second term $$-\frac{\partial}{\partial y}\left[\int M(x,y) dx \right]$$ is absent in the red-marked statement. What is the reason for its exclusion ? Please help.

REPLY [0 votes]: I think
$$\int N(x,y)dy$$
will still contain $x$ because $N$ is a function of $x$ and $y$. But if it were combined with
$$−\dfrac{∂}{∂y}\left[\int M(x,y)dx\right]$$
the terms containing $x$ would probably cancel so that:
$$\left[ N(x,y) −\dfrac{∂}{∂y}\left[\int M(x,y)dx\right]\right] = f(y)$$ which would be free from $x$; while
$$\left[ M(x,y) −\dfrac{∂}{∂x}\left[\int N(x,y)dy\right]\right] = f(x)$$ would be free from y.
I am new to this topic but I am trying to do my best to understand it..
That's why I came upon this site
It says here:

Formula for general solution of exact equation $M dx + N dy = 0$. The general solution is given by $$\int M ∂x + \int f(y)dy = C$$
where $f(y)$ is composed of all the terms in $N$ which are free from $x$ (i.e. all terms not containing $x$ — terms containing $y$ only or constants) and $\int M ∂x$ denotes integration with respect to $x$, keeping $y$ constant.
Alternate formula: $$\int N ∂y + \int f(x)dx = C$$
where $f(x)$ is composed of all the terms in $M$ which are free from $y$.
The above formulas will give the correct result in the vast majority of cases but they are not infallible and in exceptional cases may give an incorrect result. Consequently the solution should always be checked by substituting it into the original equation.


TITLE: Countable basis and first countable
QUESTION [0 upvotes]: A space $X$ is said to have a countable basis at $x$ is there is a countable collection $B$ of neighbourhoods of $x$ such that each neighbourhood of $x$ contains at least one of the most elements from $B$. What does this mean? We take countable neighbourhoods and again some neighbourhood such that each contains at least one from the countable neighbourhoods. How is the second neighbourhood different from the first? What is the significance?

REPLY [2 votes]: Consider a "really complicated" metric space $(M,d)$. If I pick a point $x\in M$, there are probably lots of open neighborhoods of $x$. However, the metric $d$ provides a canonical family of neighborhoods of $x$ which are particularly nice, namely the open balls $B_\epsilon(x):=\{y: d(x,y)<\epsilon\}$ for $\epsilon>0$.
Regardless of how big $M$ is, there are only as many open balls with center $x$ as there are real numbers. Moreover, if $U\ni x$ is open then $U\supseteq B_\epsilon(x)$ for some $\epsilon>0$. So even the neighborhoods which aren't actually open balls centered on $x$ are still "no sharper than" open balls centered on $x$ (think of an open neighborhood of a point as a guess at that point: intuitively, smaller = better).
And we can do even better by considering only rational radii: since the rationals are dense in the reals, the set $$RatBall(x):=\{B_\epsilon(x):\epsilon\in\mathbb{Q}_{>0}\}$$ of rational-radius open balls centered on $x$ has the same "sharpening" property as the set of all open balls centered on $x$. Since $\mathbb{Q}$ is countable, $RatBall(x)$ (which, remember, is a set of sets) is also countable. This shows that every metric space, no matter how complicated, is first countable.
Note that $RatBall(x)$ depends on $x$ itself: even though there's a sense of uniformity here, we're not getting a countable base for $(M,d)$ itself. First countability is much weaker than second countability (= "there is a countable base for the whole space").

REPLY [1 votes]: Imagine the metric space with underlying set $\mathbb{R}^2$, with metric the usual one. As every metric space, it can be seen as a topological space. Now, given a point $(x,y)$ in $\mathbb{R}^2$, the neighborhoods of $(x,y)$ are the unions of open balls that contain $(x,y)$. This is a very "large" collection of open neighborhoods
of the point; compare this with the collection of open balls with rational radius centered at the point.
This is also a collection of neighborhoods of the point, but, as the rational numbers, is a numerable set.
Can you see why this numerable family of neighborhoods (let's denote it by $ \mathcal{F}=\{V_{n}: n \in \mathbb{N}\}$) is something we prefer to work with, compared with the first one? We can "list" their element (more properly, there exists a bijection between the natural numbers and this family of neighborhoods), and in some sense they are "enough neighborhoods of $(x, y)$", since
any other neighborhood $U$ of $(x,y)$ contains at least one of the elements $V_{n}$ of this family (this is because $(x,y)$ would be an interior point of $U$, thus we can find $r>0$ such that
$B_{r}((x,y))$ is contained in $U$, and since the rationals are dense on the reals, nothing stops us from taking $r$ rational), we can avoid working with $U$, and to take $V_{n}$ instead.

REPLY [0 votes]: You take a particular point $x\in X$ and consider all neighbourhoods of $x$. Then a countable collection $\{N_{i}\}$ is a neighbourhood base if for any neighbourhood $N$ of $x$ there exists $i\in\mathbb{N}$ such that $N_{i}\subset N$.


text:
\section{Introduction}
This paper will describe an application of my work on the foundations of quantum field theory (much of it joint with Owen Gwilliam) to topology.  I will show how to construct the Witten genus of a complex manifold $X$ from a rigorous analysis of a quantum field theory of maps from an elliptic curve to $X$.

Usually the Witten genus is defined by its $q$-expansion.   From this point of view, modularity of the Witten genus is not obvious.      In the construction presented here, however, we find \emph{directly} a function on the moduli space of (suitable decorated) elliptic curves.  It is only after careful calculation that we can compute the $q$-expansion of this function and identify it with the Witten class.

Hopefully, this construction will give some hints about the mysterious geometric origins of elliptic cohomology.

I am very grateful to Dennis Gaitsgory, Owen Gwilliam, Mike Hopkins, David Kazhdan, Jacob Lurie, Josh Shadlen, Yuan Shen, Stefan Stolz and Peter Teichner for many helpful conversations about the material in this paper.

\section{Hochschild homology and the Todd class}
Before turning to elliptic cohomology and the Witten class, I will describe the analog of my construction for the Todd class.

The most familiar way in which the Todd class occurs is, of course, in the Grothendieck-Riemann-Roch theorem.   Let me recall the statement.    Let $X$ be a smooth projective variety, and let $E$ be an algebraic vector bundle on $X$.   Then, the Grothendieck-Riemann-Roch theorem states that
$$
\sum (-1)^i \op{dim} H^i(X,E) = \int_X \op{Td}(T X) \op{ch}(E).
$$

Another (and closely related) way in which the Todd class appears is in the study of deformation quantization.  There is a rich literature on algebraic and non-commutative analogs of the index theorem: see \cite{Fed96,BreNesTsy99}.   Much of this literature concerns index-type statements on quantizations of general symplectic manifolds.    For the purposes of this paper, we are only interested in the relatively simple case when we are quantizing the cotangent bundle of a complex manifold $X$.

Let $\Diff_X$ denote the algebra of differential operators on $X$.  Let $\Diff^\hbar_X$ denote the sheaf of algebras on $X$ over the ring $\C[\hbar]$ obtained by forming the Rees algebra of the filtered algebra $\Diff_X$.  Explicitly,
$$
\Diff^\hbar_X \subset \Diff_X \otimes \C[\hbar]
$$
is the subalgebra consisting of those finite sums
$$
\sum \hbar^i D_i
$$
where $D_i$ is a differential operator of order at most $i$. Thus, $\Diff^\hbar_X$ is a $\C[\hbar]$ algebra whose specialization to $\hbar = 0$ is the commutative algebra $\Oo_{T^\ast X}$ of functions on the cotangent bundle of $X$.  When specialized to a non-zero value of $\hbar$,  $\Diff^\hbar_X$ is just $\Diff_X$.

\numberedparagraph
The theorem we are interested in states that the Todd class of $X$ appears when one compute the Hochschild homology of the algebra $\Diff^\hbar_X$.    The index theorem concerns, ultimately, traces of differential operators.   Since $HH(  \Diff^\hbar_X)$ is the universal recipient of a trace on the algebra $\Diff^\hbar_X$, it is perhaps not so surprising that the Todd class should appear in this context.

\numberedparagraph
Recall that the Hochschild-Kostant-Rosenberg theorem gives a quasi-isomorphism
$$
\mc{I}_{HKR} : HH ( \Oo_X) \iso \Omega^{-\ast}(X).
$$
Here $HH ( \Oo_X)$ refers to the sheaf of Hochschild chains of $\Oo_X$, and $\Omega^{-\ast}(X)$ refers to the algebra of forms of $X$, with reversed grading.   Applied to the cotangent bundle of $X$, the Hochschild-Kostant-Rosenberg theorem gives an isomorphism
$$
\mc{I}_{HKR} : HH( \Oo_{T^\ast X} ) \iso \Omega^{-\ast} ( T ^\ast X).
$$
The algebra $\Diff^\hbar_X$ is a deformation quantization of $\Oo_{T^\ast X}$.  We will see that the Todd genus appears when we study how $HH( \Oo_{T^\ast X})$ changes when we replace $\Oo_{T^\ast X}$ by $\Diff^\hbar_X$.

\numberedparagraph
Before we state the theorem, we need some notation.  Let $\pi \in  \Gamma ( T^\ast X, \wedge^2 T  ( T^\ast X) )$ denote the canonical Poisson tensor on $T^\ast X$.  Let
$$
L_\pi : \Omega^i ( T^\ast X) \to \Omega^{i-1} (T^\ast X)
$$
denote the operator of Lie derivative with respect to $\pi$.  Thus, if $i_\pi$ is contraction by $\pi$,
$$
L_\pi = [ i_\pi, \d_{dR} ].
$$
Note that $L_\pi^2 = 0$, so that $\Omega^{-\ast}(T^\ast X)$ becomes a cochain complex when endowed with differential $L_\pi$.  The cohomology of this complex is called Poisson homology.

Let
$$
\op{Td}(X) \in H^0( X, \Omega^{-\ast}(X)) = \oplus H^i(X, \Omega^i )
$$
be the Todd class of $X$.  Note that the reversal of grading in the de Rham complex means that $\op{Td}(X)$ is an element of cohomological degree $0$.

The first statement of the theorem is as follows.
\begin{theorem}[Fedosov \cite{Fed96}, Bressler-Nest-Tsyan \cite{BreNesTsy99}]
There is a natural quasi-isomorphism of cochain complexes
$$
HH  ( \Diff^{\hbar}_X ) \simeq \left(  \Omega^{-\ast}  ( T ^\ast X ) [\hbar],  \hbar L_{\pi}  \right )
$$
sending $1 \in HH ( \Diff^{\hbar}_X)$ to
$$\op{Td}(X) \in \R \Gamma(X, \Omega^{-\ast} (X) ).$$
\end{theorem}

\numberedparagraph
This is a rather weak formulation of the theorem, because both sides in the quasi-isomorphism are simply cochain complexes.  There is a refined version which identifies a certain algebraic structure present on both sides.    It will take a certain amount of preparation to state this refined version.

The operator $L_\pi$ is an order two differential operator with respect to the natural product on $\Omega^{-\ast}(T^\ast X)$. We will let $\{-,-\}_{\pi}$ denote the Poisson bracket on $\Omega^{-\ast}( T^\ast X)$ of cohomological degree $1$ defined by the standard formula
$$
\{a,b\}_{\pi} = L_\pi (a b ) - (L_\pi a ) b - (-1)^{\abs{a}} a L_\pi b.
$$
The bracket $\{-,-\}_{\pi}$ is of cohomological degree $1$, and satisfies the standard Leibniz rule. Further, $L_\pi$ is a derivation for the bracket $\{-,-\}_{\pi}$.

\begin{theorem}
There is a quasi-isomorphism of cochain complexes
$$
HH( \Diff^\hbar_X ) \simeq \left(  \Omega^{-\ast}  ( T ^\ast X ) [\hbar],  \hbar L_{\pi}  +  \hbar \{\log \op{Td}(X) , -  \}_\pi \right ).
$$
\end{theorem}
The isomorphism in this theorem is related to that of the previous formulation by conjugating by $\op{Td}(X)$.

\numberedparagraph
The isomorphism appearing in this second formulation is the one that is compatible with an additional algebraic structure.  The structure is that of an algebra over a certain operad, introduced by Beilinson and Drinfeld \cite{BeiDri04}.
\begin{definition}
A \emph{Beilinson-Drinfeld algebra} (or BD algebra) is a flat graded $\C[\hbar]$ module $A$ endowed with the following structures.
\begin{enumerate}
\item A commutative unital product.
\item A Poisson bracket $\{-,-\}$ of cohomological degree $1$.
\item A differential $D: A \to A$ of cohomological degree $1$, satisfying $D^2 = 0$ and $D 1 = 0$, such that
$$
D ( a b ) = (D  a ) b + (-1)^{\abs{a}} a (D b) + \hbar \{a,b\}.
$$
\end{enumerate}

A \emph{filtered} Beilinson-Drinfeld algebra is a BD algebra $A$ with a $\C^\times$ action, such that the operator of multiplication by $\hbar$ is of $\C^\times$ weight $1$, the differential and the product on $A$ are of weight $0$, and the Poisson bracket $\{-,-\}$ is of weight $-1$.
\end{definition}
\begin{remark}
The term \emph{filtered} is used because of the well-known isomorphism between filtered vector spaces and $\C^\times$ equivariant vector bundles on $\C$; or equivalently, $\C^\times$-equivariant flat modules over the ring $\C[\hbar]$, where $\hbar$ is given weight $1$.
\end{remark}
The complex $HH ( \Diff^\hbar_X )$ is endowed with the structure of filtered BD algebra in a natural way.

The complex $\Omega^{-\ast}( T^\ast X ) [\hbar]$ also has the structure of filtered BD algebra.  The product on $\Omega^{-\ast}( T^\ast X ) [\hbar]$ is the ordinary wedge product of forms. The $\C^\times$ action on $\Omega^{-\ast}(T^\ast X)$ arises from rescaling the fibres of the cotangent bundle $T^\ast X$.      The bracket on $\Omega^{-\ast}(T^\ast X)$ is $\{-,-\}_\pi$, and the differential $\hbar L_\pi +  \hbar \{\log \op{Td}(X) , -  \} $.
\begin{proposition}
The quasi-isomorphism
$$
HH( \Diff^\hbar_X ) \simeq \left(  \Omega^{-\ast}  ( T ^\ast X ) [\hbar],  \hbar L_{\pi}  +  \hbar \{\log \op{Td}(X) , -  \} \right ).
$$
is a quasi-isomorphism of (sheaves of) filtered BD algebras.
\end{proposition}
This refined statement is enough to fix the Todd class uniquely, as the following lemma shows.
\begin{lemma}
Let
$$\alpha, \alpha' \in H^0( X, \oplus_{i \ge 1} \Omega^{i} X[i]) = \oplus_{i \ge 1} H^i(X, \Omega^i X) $$ be forms on $X$, with no zero-form component,  and suppose that we have a quasi-isomoprhism sheaves of filtered $BD$ algebras
$$
\left( \Omega^{-\ast}(T^\ast X) [\hbar], \hbar L_\pi + \hbar \{\alpha, - \} \right) \simeq
\left( \Omega^{-\ast}(T^\ast X) [\hbar], \hbar L_\pi + \hbar \{\alpha', - \} \right).
$$
Then
$$
[\alpha] = [\alpha'] \in \oplus_{i > 0} H^i(X, \Omega^i(X)) .
$$
\end{lemma}

\numberedparagraph

In this paper I will state a generalization of this characterization of the Todd class, in which the Witten class appears in place of the Todd class.

config: arxiv


text:
\begin{document}

\def\spacingset#1{\renewcommand{\baselinestretch}
{#1}\small\normalsize} \spacingset{1}

\if0\blind
{
  \title{\bf Recovering Trees with Convex Clustering}
  \author{Eric C. Chi\thanks{
    Department of Statistics, North Carolina State University, Raleigh, NC 27695-8203 (E-mail: eric$\_$chi@ncsu.edu)} \,
    and

    Stefan Steinerberger\thanks{Department of Mathematics, Yale University, New Haven, CT,  06520-8283 (E-mail: stefan.steinerberger@yale.edu).}    \\}
    \date{}
  \maketitle
} \fi

\if1\blind
{
  \bigskip
  \bigskip
  \bigskip
  \begin{center}
    {\LARGE\bf Title}
\end{center}
  \medskip
} \fi

\bigskip

\begin{abstract}
Convex clustering refers, for given $\left\{x_1, \dots, x_n\right\} \subset \Real^p$, to the minimization of
\begin{eqnarray*}
u(\gamma) & = & \underset{u_1, \dots, u_n }{\arg\min}\;\sum_{i=1}^{n}{\lVert x_i - u_i \rVert^2} + \gamma \sum_{i,j=1}^{n}{w_{ij} \lVert u_i - u_j\rVert},\\
\end{eqnarray*}
where $w_{ij} \geq 0$ is an affinity that quantifies the similarity between $x_i$ and $x_j$. We prove that if the affinities $w_{ij}$ reflect a tree structure in the $\left\{x_1, \dots, x_n\right\}$, then the convex clustering solution path reconstructs the tree exactly. The main technical ingredient implies the following combinatorial byproduct:  for every set $\left\{x_1, \dots, x_n \right\} \subset \Real^p$ of $n \geq 2$ distinct points,
there exist at least $n/6$ points with the property that for any of these points $x$ there is a unit vector $v \in \Real^p$ such that, when viewed from $x$, `most' points lie in the direction $v$
\begin{eqnarray*}
\frac{1}{n-1}\sum_{i=1 \atop x_i \neq x}^{n}{ \left\langle \frac{x_i - x}{\lVert x_i - x \rVert}, v \right\rangle} & \geq & \frac{1}{4}.
\end{eqnarray*}
\end{abstract}

\noindent
{\it Keywords:}  Convex optimization, Hierarchical clustering, Penalized regression
\vfill

\newpage
\spacingset{1.45}

\section{Introduction}
Hierarchical clustering is a fundamental unsupervised learning task, whose aim is to organize a collection of points into a tree of nested clusters. To reinforce the idea that we seek a collection of nested clusters, we will often also refer to clusters as folders in this paper.

As an illustration,
\Fig{scatter} shows a collection of points in $\Real^2$, labeled 1 to 18,  that we seek to organize.
\begin{figure}[t]
\centering

\includegraphics[scale = 0.4]{scatter.pdf}
\caption{Eighteen points in $\Real^2$ to organize. \label{fig:scatter}}
\end{figure}
Based on the Euclidean distances between the points, an intuitive organization is the following hierarchy of nested clusters. At the finest and first level of clustering, we partition the set $\{1, \ldots, 18\}$ into five subsets or folders:
\begin{eqnarray*}
F_{1,1} \amp = \amp \{1, 2, 3, 4, 5\},\; F_{1,2} & = & \{6, 7, 8\},\; F_{1,3} \amp = \amp \{9, 10, 11, 12, 13\},\\
F_{1,4} \amp = \amp \{14, 15, 16\}, &\text{and}& F_{1,5} \amp = \amp \{17, 18\}.
\end{eqnarray*}
At the second level of clustering, we merge the folders from the first level into a partition of two folders: $F_{2,1} = F_{1,1} \cup F_{1,2}$ and $F_{2,2} = F_{1,3} \cup F_{1,4} \cup F_{1,5}.$

Finally, at the third level of clustering, we merge the folders from the second level into a single folder: $F_{3,1} = F_{2,1} \cup F_{2,2}.$ \Fig{partition_tree} illustrates the described tree organization. Since each level of the tree consists of a partition of the data points, we refer to such hierarchical organizations as ``partition trees."

\begin{figure}[h]
\centering

\includegraphics[scale = 0.343]{tree_partition.pdf}
	\caption{Partition Tree.\label{fig:partition_tree}}
\end{figure}

There are many existing algorithms for automatically constructing partition trees, but perhaps the most often used algorithms in practice are collectively known as agglomerative hierarchical clustering methods \citep{War1963, Joh1967, LanWil1967, GowRos1969, Mur1983}.  Given a collection of points in $\Real^p$, agglomerative hierarchical clustering methods recursively merge the points which are closest together until all points are joined.
Different choices in the definition of closeness lead to the different variants. \Fig{hclust_average} shows two trees computed by two variants of the agglomerative hierarchical clustering.
For each tree, the eighteen points reside in the ``leaves" which are organized into a hierarchy of nested clusters that captures an increasingly coarser grouping structure as one progresses from the leaves to the root of the tree. The branch lengths in the tree quantify the similarity between pairs of points, or clusters at higher levels. We see that both trees recover binary partition trees that are similar to the ideal partition tree shown in \Fig{partition_tree}.

\begin{figure}[t]
    \centering
	\begin{tabular}{cc}

	     \subfloat[Single-linkage tree]{\includegraphics[scale = 0.45]{hclust_single.pdf}
		\label{fig:hclust_single}}

	    & \subfloat[Average-linkage tree]{\includegraphics[scale = 0.45]{hclust_average.pdf}
		\label{fig:hclust_average}} \\
	\end{tabular}
	\caption{Hierarchical clustering of data in \Fig{scatter} under two different agglomeration methods.\label{fig:single_linkage}}
\end{figure}

\subsection{Convex Hierarchical Clustering?}

Although agglomerative hierarchical methods are widely used in practice, the greedy manner in which trees are constructed often results in an unstable mapping between input data and output tree. Indeed, agglomerative hierarchical clustering methods have been shown to be highly sensitive to perturbations in the input data, namely the resulting output trees can vary drastically with the addition of a little Gaussian noise to the data \citep{Chi2017}.

One promising alternative strategy for constructing trees stably relies on formulating the clustering problem as a continuous optimization problem. Recently, several works have shown that solving a sequence of convex optimization problems can recover tree organizations \citep{PelDeSuy2005, LinOhlLju2011, HocVerBac2011, CheChiRan2015, Chi2015}.
Given $n$ points $x_1,\ldots, x_n$ in $\Real^p$,
we seek cluster centers (centroids) $u_i$ in $\Real^p$ attached to point $x_i$ that minimize the convex criterion
\begin{eqnarray}
\label{eq:objective_function}
E_{\gamma}(u) & = & \frac{1}{2}\sum_{i=1}^n \lVert x_i-u_i\rVert^2 + \gamma \sum_{i<j}w_{ij} \lVert u_i-u_j \rVert,
\end{eqnarray}
where $\gamma$ is a nonnegative tuning parameter, $w_{ij}$ is a nonnegative affinity that quantifies the similarity between $x_i$ and $x_j$, and $u$ is the vector in $\Real^{np}$ obtained by stacking the vectors $u_1, \ldots, u_n$ on top of each other. For now, we assume all norms are Euclidean norms; we will later consider arbitrary norms. The sum of squares data-fidelity term in \Eqn{objective_function} quantifies how well the centroids $u_i$ approximate the data $x_i$, while the sum of norms regularization term penalizes the differences between pairs of centroids $u_i$ and $u_j$. To expand on the latter, the regularization term is a composition of the group lasso \citep{YuanYi2006} and the fused lasso \citep{TibSauRos2005} and incentivizes sparsity in the pairwise differences of centroid pairs. Overall, $E_{\gamma}(u)$ can be interpreted as the energy of a configuration of centroids $u$ for a given relative weighting $\gamma$ between data-fidelity and model complexity as quantified by the regularization term. We next elaborate how $u(\gamma)$ varies as the tuning parameter $\gamma$ varies.

Because the objective function $E_{\gamma}(u)$ in \Eqn{objective_function} is strongly convex, for each value of $\gamma$ it possesses a unique minimizer $u(\gamma)$, whose $n$ subvectors in $\Real^p$ we denote by $u_i(\gamma)$. The tuning parameter $\gamma$ trades off the relative emphasis between data fit and differences between pairs of centroids. When $\gamma=0$, the minimum is attained when $u_i=x_i$, namely when each point occupies a unique cluster. As $\gamma$ increases, the regularization term encourages cluster centers to fuse together. Two points $x_i$ and $x_j$ with $u_i=u_j$ are said to belong to the same cluster. For sufficiently large $\gamma$, the $u_i$ fuse into a single cluster, namely $u_i = \overline{x}$, where $\overline{x}$ is the average of the data $x_i$ \citep{Chi2015, Tan2015}. Moreover, the unique global minimizer $u(\gamma)$ is a continuous function of the tuning parameter $\gamma$ \citep{Chi2017}; we refer to the continuous paths $u_i(\gamma)$ ,traced out from each $x_i$ to $\overline{x}$ as $\gamma$ varies, collectively as the solution path. Thus, by computing $u_i(\gamma)$ for a sequence of $\gamma$ over an appropriately sampled range of values, we hope to recover a partition tree.

\Fig{convex_cluster_paths} plots the $u_i$ as a function of $\gamma$ for two different sets of affinities $w_{ij}$.
We will discuss the differences in the recovered trees shortly, but for now we point out that computing $u(\gamma)$ for a range of $\gamma$ indeed appears to recover trees that bear similarity to the desired partition tree in \Fig{partition_tree}. Moreover, the $u_i(\gamma)$ are 1-Lipschitz functions of the data $x_i$ \citep{Chi2018}. Consequently, small perturbations to the input data $x_i$, are guaranteed to {\em not} result in disproportionately large variations in the output $u_i(\gamma)$.

\begin{figure}[t]
    \centering
	\begin{tabular}{cc}

	    \subfloat[Gaussian Kernel Affinities]{\includegraphics[scale = 0.4]{cvx_gk_tree.pdf}
		\label{fig:cvxclust_gk}}

	    & \subfloat[Unit Affinities]{\includegraphics[scale = 0.4]{cvx_sgk_tree_unit_weights.pdf}
		\label{fig:cvxclust_unit}} \\
	\end{tabular}
	\caption{Solution paths of convex clustering using different affinities $w_{ij}$. \label{fig:convex_cluster_paths}}
\end{figure}

At this point, the solution path of convex clustering appears to stably recover partition trees as desired. Nonetheless, questions remain as to whether convex clustering is a form of convex hierarchical clustering. Specifically, (i) when is the solution path guaranteed to produce a tree, and (ii) how do the affinities modulate the branch formation in the recovered tree?

\cite{HocVerBac2011} provide a partial answer to the first question. They prove that if unit affinities are used, namely $w_{ij} = 1$ for all $i$ and $j$, and if 1-norms are used in the regularization term in \Eqn{objective_function}, then the solution path must be a tree. On the other hand, in the same paper, they also provide an example, using the Euclidean norm in the regularization term, where the solution path can fail to be a tree. Specifically, as the tuning parameter $\gamma$ increases, it is possible for centroids to initially fuse and then ``unfuse" before eventually fusing again.

The differences in the two recovered trees shown in \Fig{convex_cluster_paths} motivate the second question. \Fig{cvxclust_gk} shows the solution path when using Gaussian kernel affinities, namely for all $i$ and $j$
\begin{eqnarray*}
w_{ij} & = & \exp\left ( -\frac{\lVert x_i - x_j \rVert_2^2}{\sigma}\right),
\end{eqnarray*}
where $\sigma$ is a positive scale parameter. Gaussian kernel affinities have been empirically shown to provide more aggressive fusion of folders closer to the leaves, and consequently more informative, hierarchical clustering results \citep{HocVerBac2011, Chi2015, Chi2017}. \Fig{cvxclust_unit} shows the solution path when using unit affinities. We see that Gaussian kernel affinities can generate a solution path that recovers the partition tree in \Fig{partition_tree}, while unit affinities can generate a solution path that recovers a less ``nested" approximation to the partition tree in \Fig{partition_tree}. The same sets of points and folders are getting shrunk together in \Fig{cvxclust_gk} and \Fig{cvxclust_unit}, but less aggressively in the latter as $\gamma$ increases.

\subsection{Contributions}

In this paper, we answer the open questions of (i) why the solution path of convex clustering can recover a tree and (ii) how affinities can be chosen to guarantee recovery of a given partition tree on the data. We first answer these questions in the case when Euclidean norms are employed in \Eqn{objective_function} and then later describe how our results can be extended to more general data-fidelity terms and arbitrary norms in the regularization term.

We clarify how the theoretical contributions in this paper differ from existing theoretical results in the convex clustering literature. \cite{Radchenko2017} present a population model for the convex clustering procedure and provide an analysis of the asymptotic properties of the sample convex clustering procedure. We note that their analysis is specific to using 1-norms in the regularization term, while we consider first the Euclidean norm before generalizing to arbitrary ones. \cite{Zhu2014} provide conditions under which two true underlying clusters can be identified by solving the convex clustering problem with appropriately chosen affinities. Similarly, \cite{She2010} and \cite{Sharpnack2012} present results when the convex clustering solution can consistently recover groupings. \cite{Tan2015} and \cite{WanZhaSun2018} present finite sample prediction error bounds for recovery of a latent set of clusters.

Our contributions differ from these prior works in two ways. First, we provide conditions on the affinities that ensure that the solution path reconstructs an {\em entire} hierarchical partition tree and clarify how these affinities can be explicitly tuned to recover a specific target tree.  With the exception of the work by \cite{Radchenko2017}, all of the other works present theoretical guarantees for recovering a {\em single} partition level rather than a nested hierarchy of partitions.
Second, in contrast to all of the previous work, we do not make any distributional assumptions on the data. Instead, we focus in this paper on understanding the behavior of the solution path as a function of the affinities used in the regularization term. By understanding this dependency, we gain insight into why a commonly used data-driven affinities choice, namely the Gaussian kernel, works so well in practice.

\subsection{Outline}

The rest of this paper proceeds as follows. In \Sec{prelim}, we define structures needed to construct affinities that will enable us to recover a desired partition tree and once equipped with the necessary building blocks, give an overview of our main result. In \Sec{geometric_lemma}, we introduce a geometric lemma that is key to proving our main result. In \Sec{proofs}, we give proofs of the geometric lemma and our main theorem.
In \Sec{extension}, we show how our main result can be generalized to other data-fidelity terms and regularization term norms.
In \Sec{discussion}, we conclude with a discussion on our results within the broader context of penalized regression methods for clustering.

\section{Setup and Overview of Main Result}
\label{sec:prelim}
Our main result shows that if the affinities $w_{ij}$ arise from an underlying partition tree, then that tree can be reconstructed from the solution path of the convex clustering problem. To proceed, we will need a formal definition of a partition tree and then a judicious assignment of weights to the edges in the tree graph corresponding to the partition tree.

\subsection{Partition Tree}
Let $\Omega = \left\{x_1, \dots, x_n\right\} \subset \Real^p$ be an arbitrary collection of points and let $[n]$ denote the set of indices $\{1, \ldots, n\}$. Following the notation and language employed in \citet{Ankenman2014} and \citet{Mishne2016, Mishne2017}, we say that $\mathcal{T}$ is a partition tree on the collection of points $\Omega$ consisting of $\mathcal{P}_0, \ldots, \mathcal{P}_{L}$ partitions of $\Omega$ if it has the following properties:

\begin{itemize}
\item[1.] The partition $\mathcal{P}_l = \{F_{l,1}, \ldots, F_{l,n_l}\}$ at level $l$ consists of $n_l$ disjoint non-empty subsets of indices in $\{1, \ldots, n\}$, termed folders and denoted by $F_{l,i}, i \in [n_l]$.
\item[2.] The finest partition $\mathcal{P}_0$ contains $n_0 = n$ singleton ``leaf" folders, namely $F_{0,i} = \{i\}$.
\item[3.] The coarsest partition $\mathcal{P}_{L}$ contains a single ``root" folder, namely $F_{L,1} = [n]$.
\item[4.] Partitions are nested; if $F \in \mathcal{P}_l$, then $F \subset F'$ for some $F' \in \mathcal{P}_{l+1}$, namely each folder at level $l-1$ is a subset of a folder from level $l$.
\end{itemize}
A partition tree $\mathcal{T}$ on $\Omega$ can be seen as the collection of all folders at all levels, namely $\mathcal{T} = \{F_{l,i} : 0 \leq l \leq L, i \in [n_l]\}$.

\subsection{Weighted Tree Graph}
\label{sec:weighted_tree_graph}

We next assign every folder $F_{l,i} \in \mathcal{T}$ to a node and draw an edge between nested folders in adjacent levels. Thus, if $F \in \mathcal{P}_{l}, F' \in \mathcal{P}_{l+1}$, and $F \subset F'$, then we draw an edge $(F,F')$ between $F$ and $F'$. If we let $\mathcal{E}$ denote the set of all edges between nested folders in adjacent levels, then the resulting graph $\mathcal{G} = (\mathcal{E}, \mathcal{T})$ is a tree.

We next assign weights on the edges in $\mathcal{E}$ as follows. Let $\varepsilon > 0$ be a fixed parameter, whose  value we will elaborate on shortly. Edges between level 0 folders and level 1 folders receive a weight of 1. Edges between level 1 folders and level 2 folders receive a weight of $\varepsilon$. Edges between level 2 folders and level 3 folders receive a weight of $\varepsilon^2$ and so on. Thus, edges between level $l$ folders and level $l+1$ folders receive a weight of $\varepsilon^l$. \Fig{tree_null} shows the weighted tree graph $\mathcal{G}$ derived from the partition tree given in \Fig{partition_tree}.

\begin{figure}[th]
    \centering
	\begin{tabular}{cccc}

		\subfloat[Weighted Tree Graph]{\includegraphics[scale = 0.265]{tree_null.pdf}
		\label{fig:tree_null}}

	    & \subfloat[The path $p_{15}$ from 1 to 5 produces $w_{15} = 1$.]{\includegraphics[scale = 0.265]{tree_level1.pdf}
		\label{fig:tree_level1}} \\

	    \subfloat[The path $p_{17}$ from 1 to 7 produces $w_{17} = \varepsilon$.]{\includegraphics[scale = 0.265]{tree_level2.pdf}
		\label{fig:tree_level2}}

	    & \subfloat[The path $p_{19}$ from 1 to 9 produces $w_{19} = \varepsilon^2$.]{\includegraphics[scale = 0.265]{tree_level3.pdf}
		\label{fig:tree_level3}} \\
	\end{tabular}
	\caption{Weighted Tree: Edges that are solid lines have weight $1$. Edges that are dashed lines have weight $\varepsilon$. Edges that are dotted lines have weight $\varepsilon^2$. \label{fig:convex_cluster_tree}}
\end{figure}

We are finally ready to construct $w_{ij}$ from the weighted tree graph. Let $F_{0,i}$ and $F_{0,j}$ be leaf nodes in the graph $\mathcal{G}$ and let $p_{ij}$ be the sequence of edges in $\mathcal{E}$ that form the path between
$F_{0,i}$ and $F_{0,j}$. Then we set $w_{ij}$ to be the smallest weight of edges contained in $p_{ij}$. In other words, $w_{ij}$ is the smallest edge weight one sees in traveling from $i$ to $j$. \Fig{tree_level1} shows that the path $p_{15}$ from 1 to 5 in the weighted graph $\mathcal{G}$ leads to the affinity assignment $w_{15} = 1$. \Fig{tree_level2} and \Fig{tree_level3} show additional examples of how affinities are derived from the edge weights in $\mathcal{G}$.

\subsection{Main Result}
We now state our main result.

\begin{theorem}
\label{thm:main}
There exists $\varepsilon_0 > 0$, depending on the data and the tree structure (which we assume defines the $w_{ij}$ as outlined above in \Sec{weighted_tree_graph}), so that for all $\varepsilon \in (0, \varepsilon_0)$ the
solution path
\begin{eqnarray*}
u(\gamma) & = & \underset{u_1, \dots, u_n}{\arg\min}\; \sum_{i=1}^{n}{\lVert x_i - u_i \rVert^2} + \gamma \sum_{i,j=1}^{n}{w_{ij} \lVert u_i - u_j\rVert},
\end{eqnarray*}
as parametrized by $\gamma \in (0, \gamma_0)$ traces out exactly the partition tree structure underlying the affinities $w_{ij}$ before collapsing into a point for some large, but finite, $\gamma_0$.
\end{theorem}

Informally speaking, this means that as $\gamma$ increases, elements from the same folder collapse into a single point, these folders (now single points) move themselves (or rather, the
fused points move in a coordinated manner) and then
collapse again in a way predicted by the tree (i.e.\@ folders sharing a parent folder collapse). This evolution continues on until all points have collapsed into a single point (which
happens for a finite value $\gamma_0$). We have no precise bound on the
times $\gamma$ at which these collapses happen but by making $\varepsilon_0$ sufficiently small, there is an arbitrary long time between stages of collapsing. The proof of \Thm{main} also gives a bound
on $\gamma_0$ as a byproduct.\\

\textbf{Remarks} Several additional remarks are in order.
\begin{enumerate}
\item The affinities do not need to have exactly the structure described in \Sec{weighted_tree_graph}. A more precise statement would be that there exists an $\varepsilon_0$ such that whenever we associate weight $\varepsilon_1 \in (0,\varepsilon_0)$ to the first level, then there exists an $\varepsilon$ (depending on everything and $\varepsilon_0, \varepsilon_1$) such that if we associate weight $\varepsilon_2 \in (0, \varepsilon)$ to the second level there exists an $\varepsilon_3$ (depending on everything and $\varepsilon_0, \varepsilon_1, \varepsilon_2$ etc.\@). Simply put, it suffices to have a sufficiently clear separation of scales encoded in the affinities.

Indeed, \Fig{w1k} shows the Gaussian kernel affinities $w_{1j}$ between $x_1$ and the remaining $x_j$ for $j = 2, \ldots, 18$ from the example in \Fig{scatter}. We observe clear separation of scales encoded in the Gaussian kernel affinities that align with the partition tree and corresponding weighted graph $\mathcal{G}$ in \Fig{tree_null}. Similar plots of the set of affinities associated with each data point reveal alignment with the partition tree and corresponding weighted graph $\mathcal{G}$. The key quality of the Gaussian kernel should be readily apparent, namely the Gaussian kernel naturally encodes the geometric decay in weights needed to reconstruct a partition tree embedded in Euclidean space.

\begin{figure}[t]
\centering

\includegraphics[scale = 0.4]{w1k.pdf}
	\caption{Gaussian kernel affinities $w_{1j}$ between $x_1$ and the other $x_j$ from the example in \Fig{scatter}.\label{fig:w1k}}
\end{figure}

\item The result is completely independent of where the $\left\{x_1, \dots, x_n\right\} \in \Real^p$ are located in space. Their location, however, affects the critical scale $\varepsilon_0$.
\item The statement guarantees that points $u_i$ fuse together with respect to the folder structure before moving to fuse with other points and their respective folder structure, however, we do not have clear control over whether they intersect in between or not. Generically, this will not happen but, for a non-generic set of $x_i$, it is possible to arrange for the $u_i$ to intersect before they fuse.
This is a consequence of our lack of conditions on the position of the points $x_i$. If the $x_i$ are located in space in a way that actually reflects the tree structure, then they will fuse upon intersecting for the first time.
\end{enumerate}

\section{A Geometric Lemma}
\label{sec:geometric_lemma}
We establish a geometric Lemma that is of intrinsic interest: it states that for any set of distinct points $\left\{u_1, \dots, u_n\right\} \in \Real^p$, one of these points $u$ (indeed, one on the boundary of the convex hull of all the points) has the property that for a suitable ``viewing direction" $v \in \Real^p$  most points are clearly visible when standing in the point $u$ and looking towards the viewing direction (in the sense of having a large inner product). We now phrase this more precisely below. Recall that the convex hull of a set $S$, denoted by $\conv S$ is the smallest convex set containing the set $S$.

\begin{lemma}
\label{lem:geom}
For every set $S = \left\{u_1, \dots, u_n \right\} \subset \Real^p$ of $n \geq 3$ distinct points,
there exists
$$ u \in S \cap \partial \conv S \quad \mbox{and} \quad v \in \Real^p\quad\mbox{satisfying}~\lVert v\rVert = 1$$
such that
\begin{eqnarray}
\label{eq:property}
\frac{1}{n}\sum_{i=1 \atop u_i \neq u}^{n}{ \left\langle \frac{u_i - u}{\lVert u_i - u\rVert}, v \right\rangle} & \geq & \frac{1}{2}.
\end{eqnarray}
\end{lemma}

The statement can be summarized as follows: for a suitable point $u \in S \cap \partial \conv S$, if we map the direction to all other points onto the unit sphere $\mathbb{S}^p$, then convexity implies that there is a great circle on $\mathbb{S}^p$ such that all these directions are on one side of the great circle or on it. This can be interpreted as the dualization of the fact that there is supporting hyperplane touching the boundary of the convex hull in such a way that all of $ \conv S$ is on one side. The statement claims the existence of a boundary point $u$ such that the average projection point is bounded away from that great circle by a universal constant.

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=1.2]
\filldraw (0,0) circle (0.05cm);
\filldraw (1,0) circle (0.05cm);
\filldraw (0,1) circle (0.05cm);
\filldraw (1.2,1.2) circle (0.05cm);
\filldraw (2,-1) circle (0.05cm);
\filldraw (2,2) circle (0.05cm);
\filldraw (-1,0) circle (0.05cm);
\filldraw (-0.2,0.4) circle (0.05cm);
\filldraw (0.4,-0.5) circle (0.05cm);
\filldraw (-0.2,-0.2) circle (0.05cm);
\filldraw (-0.3,0.5) circle (0.05cm);
\filldraw (0.4,0.3) circle (0.05cm);
\filldraw (0,0) circle (0.05cm);
\draw [thick] (-1,0) -- (0,1) -- (2,2) -- (2,-1) -- (0.4,-0.5) -- (-1,0);
\draw [->, thick] (2,-1) -- (1.5, -0.5);
\node at (2.3, -1) {$u$};
\node at (1.6, -0.4) {$v$};
\end{tikzpicture}
\caption{A set of points in $\Real^2$: there exists a point $u$ on the boundary of the convex hull and a direction $v$ such that the average inner product of $(u_i - u)/\lVert u_i - u\rVert$ and $v$ is bounded away from 0 by a universal constant.}
\end{figure}

We will use \Lem{geom} to study the regularization term in \Eqn{objective_function}, namely the functional
\begin{eqnarray*}
J(u) & = & \sum_{i,j =1}^{m}{ \lVert u_i - u_j \rVert } \qquad \mbox{for a given set of distinct points}~\left\{u_1, u_2, \dots, u_m\right\} \subset \Real^p.
\end{eqnarray*}
The functional $J$ is clearly minimized for any collection of $u_i$ that are all identical. Consequently, any collection of distinct $u_i$ represents a suboptimal configuration of centroids and therefore admits a descent direction that leads to a decrease in energy. The power of \Lem{geom} is that it identifies a direction that guarantees a large amount of decrease in $J$. To see this, we write down the directional derivative of $J$ explicitly.

The directional derivative of moving $u_j$ in direction $v \in \Real^p$, normalized to $\lVert v\rVert = 1$ is computed as
\begin{equation}
\label{eq:directional_derivative}
\begin{split}
 \left\langle \frac{\partial J}{\partial u_j}, v \right\rangle & \amp = \amp \lim_{t \rightarrow 0} \frac{1}{t} \sum_{i \neq j}{\lVert u_i - (u_j + t v)\rVert - \lVert u_i - u_j\rVert} \\
& \amp = \amp  \lim_{t \rightarrow 0} \frac{1}{t} \sum_{i \neq j}{  \sqrt{  \big\langle u_i - (u_j + t v), u_i - (u_j + t v) \big\rangle} - \lVert u_i - u_j \rVert}  \\
& \amp = \amp  \sum_{i \neq j}{\lim_{t \rightarrow 0} \frac{1}{t} \left( \sqrt{\lVert u_i - u_j \rVert^2 - 2t  \left\langle u_i - u_j , v \right\rangle + t^2}  - \lVert u_j - u_i \rVert \right)}\\
& \amp = \amp  -\sum_{i \neq j}{\left\langle  \frac{ u_i - u_j  }{ \lVert u_i - u_j \rVert }, v \right\rangle }.
\end{split}
\end{equation}
The expression for the directional derivative given in (\ref{eq:directional_derivative}), in conjunction with \Lem{geom}, shows that it is always possible to find one point such that moving it $\varepsilon$ in a certain direction decreases the entire functional by at least $(n/3)\varepsilon$. This may be understood as a non-degeneracy condition on the functional $J$. The existence of a direction of guaranteed minimum decrease in $J$ will be essential in proving \Thm{main}. \\

Before proceeding to proofs of \Lem{geom} and \Thm{main}, we also note the following consequence, whose proof is in the Appendix.
\begin{corollary}
\label{cor:more_geometry} Let $S = \left\{u_1, \dots, u_n \right\} \subset \Real^p$ be a set of distinct points. Then there exist at least $n/6$ points $u \in S$ having the property that for some $\lVert v \rVert= 1$
\begin{eqnarray*}
\frac{1}{n}\sum_{i=1 \atop u_i \neq u}^{n}{ \left\langle \frac{u_i - u}{\lVert u_i - u \rVert}, v \right\rangle} & \geq & \frac{1}{4}.
\end{eqnarray*}
\end{corollary}

This simple statement has non-trivial implications: the geometric Lemma may seem like these vantage points from which to observe the entirety of the set without having too many small inner products are rare.  To the contrary, \Cor{more_geometry} declares that the property is surprisingly common and enjoyed by a universal fraction of all points. We believe this result to be of substantial independent interest since it can be interpreted as a basic statement (with universal constants) in a general Hilbert space. It could be of interest to further pursue this line of investigation.

\section{Proofs}
\label{sec:proofs}
We now prove \Lem{geom} and \Thm{main}.

\subsection{Geometric Lemma}

\begin{proof}
Let $S = \left\{u_1, u_2, \dots, u_n\right\}$. Select an arbitrary $u \in \partial S \cap \conv S$, and let $y \in S$ be a point in the set furthest from $u$ (there may be more than one such point), formally
\begin{eqnarray}
\label{eq:distance}
\| u - y \| & = &  \max_{1 \leq i \leq n}{\| u - u_i\|}
\end{eqnarray}
It is easy to see that $y$ resides on the boundary of the convex hull; $y$ is in fact an extreme point. We now show that $u$, equipped with
the viewing direction vector $v_1 = (y-u)/\lVert y-u \rVert$, or $y$, equipped with the viewing direction vector $v_2 = -v$, has the desired property. We first show that for every  $u_i \notin \left\{u, y\right\}$

\begin{eqnarray}
\label{eq:inequality}
\left\langle \frac{u_i - u}{\lVert u_i - u\rVert}, v_1 \right\rangle +  \left\langle \frac{u_i - y}{\lVert u_i - y\rVert}, v_2 \right\rangle & \geq & 1.
\end{eqnarray}
Since we are only dealing with three points $u, y,$ and $u_i$, all angles are determined by the corresponding triangle, which we can assume without loss of generality to reside in $\Real^2$. Moreover, the invariance under dilation, translation and rotation enables us to assume that $u = (0,0)$ and $y=(1,0)$. If
we write $u_i = (a,b)$, then the expression on the left hand side of (\ref{eq:inequality}) simplifies to
\begin{eqnarray}
\label{eq:equality}
\left\langle \frac{u_i - u}{\lVert u_i - u \rVert}, v_1 \right\rangle +  \left\langle \frac{u_i - y}{\lVert u_i - y \rVert}, v_2 \right\rangle & = & \frac{a}{\sqrt{a^2+b^2}} + \frac{1-a}{\sqrt{(1-a)^2 + b^2}},
\end{eqnarray}
and the condition on the distances $\lVert u - u_i \rVert$ and $\lVert y - u_i \rVert$ required by (\ref{eq:distance}) implies that
\begin{eqnarray}
\label{eq:constraint}
\max\left\{ a^2 + b^2, (1-a)^2 + b^2\right\} & \leq & 1.
\end{eqnarray}
Minimizing the expression in (\ref{eq:equality}) subject to the constraint in (\ref{eq:constraint}) gives us the desired inequality in (\ref{eq:inequality}); almost equality is attained for $u_i$ very close to either $u$ or $y$ (and as orthogonal as possible to $v$) and equality is attained for $(a,b)=(1/2, \sqrt{3}/2)$. We then sum the left and right hand sides of (\ref{eq:inequality}) over $i = 1, \ldots, n$ to arrive at the inequality
\begin{eqnarray}
\label{eq:inequality2}
\sum_{i=1 \atop u_i \neq u}^{n}{\left\langle \frac{u_i - u}{\lVert u_i - u \rVert}, v_1 \right\rangle} + \sum_{i=1 \atop u_i \neq y}^{n}{ \left\langle \frac{u_i - y}{\lVert u_i - y \rVert}, v_2 \right\rangle } & \geq & n,
\end{eqnarray}
which follows from realizing that each of the sums contains one term that is equal to 1 and that the remaining sum runs over all $u_i \notin \left\{u, y\right\}$ yielding at least a total of $n-2$.
Thus at least one of the two terms is size $n/2$ and we obtain the desired result.
\end{proof}

\subsection{Main Theorem}
\textbf{Outline}
The proof is based on the self-similarity of the statement. We essentially show that points at the lowest level fuse in the right way with points in the same leaves (those
who have mutual affinity 1). Once they are fused, we show that they stay fused for all subsequent values of $\gamma$. The newly emerging problem turns out to be exactly of the
same type as the original one: we re-interpret fused points as single points with a mutual interaction now at scale $\sim \varepsilon$ (which becomes the dominant scale since points
with $w_{ij} = 1$ are already fused). At every step, the arguments will go through provided $\varepsilon$ is sufficiently small (but positive) and since the tree is of finite height, the result
follows. To be more precise, the argument will proceed as follows.

\begin{enumerate}
\item We assume that the $x_i$ are fixed and that the $u_i$ are solutions of the minimization problem
$$\inf_{u_1, \dots, u_n} \left[ \sum_{i=1}^{n}{\lVert x_i - u_i \rVert^2} + \gamma \sum_{i,j=1}^{n}{w_{ij} \lVert u_i - u_j \rVert} \right].$$
Plugging in an example shows that the minimal energy is uniformly bounded in $\gamma$. This has some basic
implications: the $u_i$ cannot be too far away from the $x_i$ and not too far away from each other.
\item We then study a subset of points $\left\{x_1, \dots, x_n\right\}$ contained in a leaf of the tree. This means that
their mutual affinity satisfies $w_{ij} = 1$ and the affinity between any of these points to any other point not in the leaf of the partition is at most $\varepsilon$.
\item We then focus exclusively on these point sets and prove that for $\gamma$ sufficiently large, these sets are necessarily fused in a point. This is where \Lem{geom} will be applied.
\item This contradiction proves that for $\gamma$ sufficiently large, the point sets in the leaf are fused into exactly one point as desired. Once this has been shown,
the full statement essentially follows by induction since these fused points interact exactly as individual points used to do; having common parents in the tree
becomes the next-level analogue of being associated to the same leaf. The result then follows.
\end{enumerate}

\begin{proof}
We introduce the energy of the minimal energy configuration for $\gamma > 0$ as
\begin{eqnarray*}
E(\gamma) & = & \underset{u}{\inf}\; E_\gamma(u) =\underset{u}{\inf} \left[ \sum_{i=1}^{n}{\lVert x_i - u_i \rVert^2} + \gamma \sum_{i < j}{w_{ij} \lVert u_i - u_j \rVert} \right].
\end{eqnarray*}
By setting $u_1 = u_2 = \dots = u_n$ and putting these points in the center of mass of $\left\{x_1, \dots, x_n\right\}$, we observe that this energy is uniformly bounded for all $\gamma$
\begin{eqnarray*}
E & = & \sup_{\gamma>0}~ E(\gamma) \amp \leq \amp \sum_{i=1}^{n}{ \left \lVert x_i - \frac{1}{n} \sum_{i=1}^{n}{x_i} \right\rVert^2} \amp < \amp \infty.
\end{eqnarray*}
We decompose the energy functional $E(\gamma)$ as
\begin{eqnarray}
\label{eq:decomposition}
E(\gamma) & = & E_1(\gamma) + E_2(\gamma),
\end{eqnarray}
where
\begin{eqnarray*}
E_1(\gamma) & = & \sum_{i=1}^{n}{\lVert x_i - u_i \rVert^2} + \gamma \sum_{(i,j) \in \mathcal{E}_1} \lVert u_i - u_j\rVert,
\end{eqnarray*}
where $\mathcal{E}_1 = \{ (i,j) : w_{ij} = 1\}$ and
\begin{eqnarray*}
E_2(\gamma) & = & \gamma \sum_{(i,j) \in \mathcal{E}_2} w_{ij} \lVert u_i - u_j \rVert,
\end{eqnarray*}
where $\mathcal{E}_2 = \{ (i,j) : w_{ij} \leq \varepsilon < 1\}$. The decomposition (\ref{eq:decomposition}) makes explicit that, for $\varepsilon$ sufficiently small, the functional $E_2(\gamma)$ can be interpreted as an error term, while the dominant dynamics are determined by $E_1(\gamma)$.
We now claim that for $\gamma$ sufficiently large (where sufficiently large depends on everything except the parameter $\varepsilon$) any subset of the points $u_i$ whose mutual affinities are 1 (i.e.\@ all the members of one of the leaves in the tree) are fused in a point. The argument can be made quantitative and
\begin{eqnarray*}
\gamma & > & \frac{8\sqrt{E}}{n}
\end{eqnarray*}
will turn out to be sufficient.

We will invoke \Lem{geom} shortly, but in order to do so we need to ensure that all points are distinct. It is easy to see that the energy $E$ is a continuous functional, this means that we can move any potentially clumped points apart by accepting an arbitrarily small increase of energy; the remainder of the argument works as follows: if points happen to be clumped together -- but not in exactly one point but in several -- then we may move all of them an arbitrarily small bit. We can accept an arbitrarily small increase of energy as long as we are able to then deduce a definite decrease in energy afterwards (that will depend on the diameter of the $u_i$); this contradiction shows that the clumping has to occur in exactly one point.
The next step in the argument is dynamical: we compute the effect of moving one of the points an infinitesimal amount (this is already using the assumption that all $u_i$ are distinct).
Reusing the computation in \Eqn{directional_derivative}, we see that
\begin{eqnarray}
\label{eq:perturb}
\left \langle \frac{\partial E }{\partial  u_j}, v \right \rangle & = & 2\left \langle u_j - x_j , v \right \rangle - \gamma \sum_{i =1 \atop i \neq j}^{n}{\left\langle  \frac{ u_i - u_j  }{ \lVert u_i - u_j \rVert }, v \right\rangle } + \left \langle \frac{\partial  }{\partial  u_j}   \gamma \sum_{(i,j) \in \mathcal{E}_2} w_{ij} \lVert u_i - u_j \rVert, v \right \rangle.\qquad
\end{eqnarray}
The first term on the right hand side of (\ref{eq:perturb}) is bounded above by
\begin{eqnarray}
\label{eq:bound4}
 2 \left \lvert \left \langle u_j - x_j , v \right \rangle \right \rvert & \leq & 2\lVert x_j - u_j\rVert \amp \leq \amp 2 \sqrt{E},
\end{eqnarray}
and the third term on the right hand side of (\ref{eq:perturb}) is bounded above by
\begin{eqnarray}
\label{eq:bound5}
\left\lVert \frac{\partial  }{\partial  u_j}   \gamma \sum_{(i,j) \in \mathcal{E}_2} w_{ij} \lVert u_i - u_j \rVert \right\rVert & = &
\gamma \left \lVert \sum_{i: (i,j) \in \mathcal{E}_2} w_{ij} \frac{u_i - u_j}{\lVert u_i - u_j \rVert} \right \rVert
\amp \leq \amp
\gamma \varepsilon  n.
\end{eqnarray}

\Lem{geom} guarantees that there exists $u_j$ for which the second term on the right hand side of (\ref{eq:perturb}) is smaller than $-\gamma n/2$. The proof of \Lem{geom} is even stronger and guarantees that if $\lVert u_i - u_j\rVert = \diam\left\{u_1, \dots, u_n\right\}$, then either $u_i$ or $u_j$ has the desired property and can be moved in a suitable direction $v$. Plugging the $u_j$ and $v$ from \Lem{geom} into both sides of (\ref{eq:perturb}) and applying inequalities (\ref{eq:bound4}) and (\ref{eq:bound5}), we arrive at the following inequality.
\begin{eqnarray}
\label{eq:guaranteed_decay}
\left \langle \frac{\partial E }{\partial  u_j}, v \right \rangle & \leq & D(\gamma) \amp = \amp 2 \sqrt{E} - \gamma n\left( \frac{1}{2} - \varepsilon \right).
\end{eqnarray}

The inequality in (\ref{eq:guaranteed_decay}) guarantees that for $\gamma$ sufficiently large (depending on $E, \varepsilon$, and $n$), there exists a descent direction $v$ with a decrease rate of at least $D(\gamma)$. We now move the point $u_j$ with the desired property in the descent direction $v$ or a direction very close to it if we are in danger of colliding with another point (this is allowed because of the continuity of all functionals involved and the fact that we do not work with sharp constants). We do this until the moved point does not have the desired property anymore. Then another point will have the desired property, and we can repeat the procedure. It is easily seen that the total decrease in $E$ obtained this way is at least  $D(\gamma) \cdot \diam P$, where $P$ is the set of $u_j$ belonging to a leaf folder.

This, however, implies that as soon as we can guarantee the existence of a strict decent direction, we are not dealing with a minimizer unless the diameter is 0 and all points are fused.
This argument can be made quantitative and assuming $\varepsilon \leq 1/4$, we see that $D(\gamma)$ is negative for all
\begin{eqnarray*}
\gamma & \geq & \frac{8 \sqrt{E}}{n}.
\end{eqnarray*}
This shows that all the points in the leaf have to have fused into a single point for some $\gamma$ less than $8 \sqrt{E}/n$ and will stay in this configuration for all subsequently larger $\gamma$.
A careful inspection of the proof shows that we do not require $w_{ij} =1$ for points in the same partition: it suffices if $1 \leq w_{ij} \leq c$ for some constant $c$
if subsequent parameter choices of $\gamma$ are allowed to depend on that. The full
statement now follows by induction: points in leaves become a single point, their parent structure determines the next collection of leaves and the product of their affinities determines the new affinities.
\end{proof}

\section{Extensions of the Main Theorem}
\label{sec:extension} The proof of \Thm{main} relies on rather elementary analysis and consequently is quite flexible. Indeed, the proof can be immediately extended to more general notions of energy of the type
\begin{eqnarray*}
E_{\gamma}(u) & = &  \phi(x_1, \dots, x_n, u_1, \dots, u_n) + \gamma \sum_{i < j}{w_{ij} \left\lVert  u_i - u_j \right\rVert_{X}},
\end{eqnarray*}
where $X$ is an arbitrary norm on $\Real^p$ and $\phi$ is assumed to satisfy the following properties:
\begin{enumerate}
\item The function $\phi: \Real^{p \times n} \rightarrow \Real_{\geq 0}$ enforces some degree of data-fidelity and compactness.
\item For all $u$ for which
\begin{eqnarray*}
\phi(x_1, \dots, x_n, u_1, \dots, u_n) + \gamma \sum_{i,j=1}^{n}{w_{ij} \left\lVert  u_i - u_j \right\rVert_{X}} & \leq &  \inf_{x \in \Real^p} \phi(x_1, \dots, x_n, x, \dots, x),
\end{eqnarray*}
we have
\begin{eqnarray*}
\left\lVert  \frac{\partial}{\partial u_i} \phi(x_1, \dots, x_n, u_1, \dots, u_n) \right\rVert & \leq & c
\end{eqnarray*}
where $c$ only depends on $\gamma$ and $\left\{x_1. \dots, x_n\right\}$.
\end{enumerate}

The argument proceeds in exactly the same way and makes crucial use of the fact that any two norms in a finite-dimensional Euclidean space are equivalent up to constants, namely
\begin{eqnarray*}
c_5 \lVert x\rVert_{\ell^2} & \leq & \lVert x \rVert_{\scaleto{X}{4.5pt}} \amp \leq \amp c_6 \lVert x\rVert_{\ell^2}.
\end{eqnarray*}
Since constants can always be absorbed in $\gamma$, this reduces to our case, namely $X = \ell^2$. \\

\begin{proof}(Sketch of the argument)
Setting all $u_i = x$ and minimizing over $x$ implies that the energy is uniformly bounded in $\gamma$ (with a bound depending only on $\left\{x_1, \dots, x_n \right\}$). Since the norm $X$ is comparable to the Euclidean norm, this implies that any minimizing configuration $\left\{u_1, \dots, u_n\right\}$ has to have a bounded diameter (with a bound depending only on $\left\{x_1, \dots, x_n \right\}$). Then, for $\gamma$ sufficiently large (depending on $c$), \Lem{geom} implies a direction of decay and thus points are eventually fused. We leave the precise details to the interested reader.
\end{proof}

We close this section by noting that the generality of our result opens the door to intriguing applications. For example, one potential application of our extension is to construct partition trees of regression coefficients in clustered regression \citep{Bondell2008, She2010, Witten2014, KeFanWu2015}. We leave these investigations as future work.

\section{Discussion}
\label{sec:discussion}

In this paper, we answered the question of when the convex clustering solution path recovers a tree. The key to ensuring the recovery of a well nested partition tree is the use of affinities that encourage the fusions within a folder before fusions with higher level folders and so on as the tuning parameter $\gamma$ increases. By choosing the edge weight parameter $\varepsilon$ sufficiently small, different folders have very little incentive to interact, and the optimization problem is essentially decoupled. As $\gamma$ increases, the same procedure repeats itself.

We end with a discussion on the relationship between convex and non-convex formulations of penalized regression based clustering. Although we focus in this paper on the ability of convex clustering to recover a potentially deep hierarchy of nested folders, our result also sheds light on a gap in theory and practice that convex clustering's performance can be significantly improved when using non-uniform data-driven affinities when seeking a shallow or single level of nested folders. In practice, Gaussian kernel affinities have been observed to work well, but these affinity choices have until now lacked formal justification.

Indeed, non-uniform affinities provide the link between convex clustering and other penalized regression-based clustering methods that use folded concave penalties. It is well known that 1-norm penalties lead to biased parameter estimates. Bias is the price for simultaneously performing variable selection and estimation. In the context of convex clustering, the centroid estimates $u_i$ are biased towards the grand mean $\overline{x}$. Consequently, others have proposed employing a folded concave penalty instead of a norm in the regularization terms  \citep{PanShenLiu2013,Marchetti2014,Wu2016}.  Folded concave penalties suffer far less bias in exchange for giving up convexity in the optimization problem, which means that iterative algorithms can typically at best converge only to a KKT point.

Suppose we were to employ a folded concave penalty, such as the smoothly clipped absolute deviation \citep{FanLi2001} or minimax concave penalty \citep{Zhang2010}, and seek to minimize the following alternative objective to \Eqn{objective_function}
\begin{eqnarray}
\label{eq:folded_concave_objective}
\tilde{E}_\gamma(u) & = & \frac{1}{2} \sum_{i=1}^n \lVert x_i - u_i \rVert^2 + \gamma \sum_{i < j}\varphi \left(\lVert u_i - u_j\rVert\right),
\end{eqnarray}
where each $\varphi : [0,\infty) \mapsto [0, \infty )$ has the following properties: (i) $\varphi$ is concave and differentiable on $(0, \infty)$, (ii) $\varphi$ vanishes at the origin, and (iii) the directional derivative of $\varphi$ exists and is positive at the origin.

Since $\varphi$ is concave and differentiable, for all positive $z$ and $\tilde{z}$
\begin{eqnarray*}
	\varphi(z) & \leq & \varphi(\tilde{z}) + \varphi'(\tilde{z})(z - \tilde{z}).
\end{eqnarray*}
In other words, the first order Taylor expansion of a differentiable concave function $\varphi$ provides a tight global upper bound at the expansion point $\tilde{z}$. Thus, we can construct a function that is a tight upper bound of the function $\tilde{E}_\gamma(u)$
\begin{eqnarray}
\label{eq:majorization}
g_\gamma(u \mid \tilde{u}) & = &
\frac{1}{2} \sum_{i=1}^n \lVert x_i - u_i \rVert^2 + \gamma \sum_{i < j}w_{ij} \lVert u_i - u_j\rVert+ c_7,
\end{eqnarray}
where $c_7$ is a constant that does not depend on $u$, and $w_{ij}$ are affinities that depend on $\tilde{u}$, namely
\begin{eqnarray*}
w_{ij} & = & \varphi'\left(\lVert \tilde{u}_i - \tilde{u}_j \rVert \right).
\end{eqnarray*}
Note that if we take $\tilde{u}_i$ to be the data $x_i$, and $\varphi(z)$ to be  the following variation on the error function
\begin{eqnarray*}
\varphi(z) & = & \int_{0}^z e^{-\frac{\alpha^2}{\sigma} }d\alpha,
\end{eqnarray*}
then the bounding function given in \Eqn{majorization} coincides, up to an irrelevant shift and scaling, with the convex clustering objective using Gaussian kernel affinities.

The function $g_\gamma(u \mid \tilde{u})$ is said to majorize the function $\tilde{E}_\gamma(u)$ at the point $\tilde{u}$  \citep{LanHunYan2000} and minimizing it corresponds to performing one step of the local linear-approximation algorithm \citep{Zou2008, Schifano2010}, which is a special case of the majorization-minimization (MM) algorithm \citep{LanHunYan2000}.  Thus, we can see that employing Gaussian kernel affinities corresponds to taking one step of a local linear-approximation algorithm applied to a penalized regression based clustering with an appropriately chosen folded concave penalty.

In practice,
variants that employ folded concave penalties take multiple steps of the local linear approximation. So at the $k$th step,
\begin{eqnarray*}
u^{(k)} & = & \underset{u}{\arg\min}\; \frac{1}{2} \sum_{i=1}^n \lVert x_i - u_i \rVert^2 + \gamma \sum_{i < j}
\varphi'\left(\lVert u^{(k-1)}_i - u^{(k-1)}_j \rVert \right)
 \lVert u_i - u_j\rVert.
\end{eqnarray*}
As affinities represent a data-driven way to approximate the partition tree, one can see that employing folded concave penalties corresponds to implicitly recomputing the affinities, which corresponds to refining our estimate of the partition tree based on the data.

In light of this current work, this last observation raises two interesting questions: (i) what partition tree is being recovered by a solution path of a penalized regression-based clustering method that uses a folded concave penalty and (ii) when is the recovered partition tree substantially different than the tree corresponding to a one-step local linear approximation? We leave these questions to future work.

\begin{center}
{\large\bf ACKNOWLEDGMENTS}
\end{center}
We thank Raphy Coifman for pointing out \Cor{more_geometry}.

\appendix

\section{Proof of \Cor{more_geometry}}
\label{sec:more_geometry}

\begin{proof} \Lem{geom} guarantees the existence of a point $u$, call it $\tilde{u}_{1}$, and viewing direction vector $v_1$ that satisfies inequality (\ref{eq:property}). Remove $\tilde{u}_1$ from the set $S = \{u_1, \ldots, u_n \}$ and apply \Lem{geom} to the new set $S \backslash S_1$, where $S_1 = \{\tilde{u}_1\}$. Repeat this procedure $k$ times and let $S_k$ denote the set of $k$ points, $\{\tilde{u}_1, \ldots, \tilde{u}_k\}$, that satisfy inequality (\ref{eq:property}) for the sets $S, S \backslash S_1, \ldots, S \backslash S_{k-1}$ respectively. \Lem{geom} guarantees the existence of a point $u \in S \backslash S_k$ and viewing direction vector $v$ such that
\begin{eqnarray}
\label{eq:bound1}
\frac{1}{n-k}\sum_{u_i \in S \backslash S_{k} \atop u_i \neq u}^{}{ \left\langle \frac{u_i - u}{\lVert u_i - u \rVert}, v \right\rangle} & \geq & \frac{1}{2}.
\end{eqnarray}
The Cauchy-Bunyakovsky-Schwarz inequality tells us that
\begin{eqnarray}
\label{eq:bound2}
\left\langle \frac{u_i - u}{\lVert u_i - u \rVert}, v \right\rangle & \geq & -1,
\end{eqnarray}
for all $u_i \in S_k$. Inequalities (\ref{eq:bound1}) and (\ref{eq:bound2}) together imply that
\begin{eqnarray}
\label{eq:bound3}
\sum_{i=1 \atop u_i \neq u}^{n}{ \left\langle \frac{u_i - u}{\lVert u_i - u \rVert}, v \right\rangle} \amp \geq \amp \frac{n-k}{2} - k
\end{eqnarray}
Finally, for $k \leq n/6$, we see that the right hand side of (\ref{eq:bound3}) is bounded below by $n/4$ which implies the desired result.
\end{proof}

\bibliographystyle{asa}
\bibliography{ref}

\end{document}


TITLE: Two questions about weakly convergent series related to $\sin(n^2)$ and Weyl's inequality
QUESTION [53 upvotes]: By using partial summation and Weyl's inequality, it is not hard to show that the series $\sum_{n\geq 1}\frac{\sin(n^2)}{n}$ is convergent.

Is is true that $$\frac{1}{2}=\inf\left\{\alpha\in\mathbb{R}^+:\sum_{n\geq 1}\frac{\sin(n^2)}{n^\alpha}\mbox{ is convergent}\right\}?$$
In the case of a positive answer to the previous question, what is $$\inf\left\{\beta\in\mathbb{R}^+:\sum_{n\geq 1}\frac{\sin(n^2)}{\sqrt{n}(\log n)^\beta}\mbox{ is convergent}\right\}?$$

REPLY [3 votes]: I recall a generalization of partial summation formula:
Suppose that $\lambda_1,\lambda_2,\ldots$ is a nondecreasing sequence of real numbers with limit infinity, that $c_1,c_2,\ldots$ is an arbitrary sequence of real or complex numbers, and that $f(x)$ has a continuous derivative for $x\geq \lambda_1$. Put
$$
C(x)=\sum_{\lambda_n\leq x}c_n,
$$
where the summation is over all $n$ for which $\lambda_n\leq x$. Then for $x\geq\lambda_1$,
$$
\sum_{\lambda_n\leq x}c_nf(\lambda_n)=C(x)f(x)-\int^{x}_{\lambda_1}C(t)f'(t)dt.\tag 1
$$
Now we can write if $y=x^2$ and $\lambda_n=n^2$ and $C(t)=[\sqrt{t}]$ (integer part of $\sqrt{t}$):
$$
S=\sum_{1\leq n\leq x}\frac{\sin(n^2)}{n^a}=\sum_{\lambda_n\leq y}\frac{\sin(\lambda_n)}{\lambda_n^{a/2}}=
$$
$$
=[\sqrt{y}]\frac{\sin(y)}{y^{a/2}}-\int^{y}_{1}[\sqrt{t}]\frac{d}{dt}\left(\frac{\sin(t)}{t^{a/2}}\right)dt.
$$
But it is $[\sqrt{t}]=\sqrt{t}-\{\sqrt{t}\}$, where $\{\sqrt{t}\}$ is the fractional part of $\sqrt{t}$. Hence
$$
S=-\frac{1}{2}Re\left[iy^{1/2-a/2}E\left(\frac{1+a}{2},iy\right)\right]+\frac{1}{2}Re\left[iE\left(\frac{1+a}{2},i\right)\right]+\sin(1)-\{\sqrt{y}\}\frac{\sin(y)}{y^{a/2}}+
$$
$$
+\int^{y}_{1}\{\sqrt{t}\}\frac{d}{dt}\left(\frac{\sin(t)}{t^{a/2}}\right)dt,
$$
where
$$
E(a,z)=\int^{\infty}_{1}\frac{e^{-tz}}{t^a}dt
$$
But when $a>0$ and $y\rightarrow+\infty$ we have
$$
\lim_{y\rightarrow+\infty}\left\{-\frac{1}{2}Re\left[iy^{1/2-a/2}E\left(\frac{1+a}{2},iy\right)\right]+\frac{1}{2}Re\left[iE\left(\frac{1+a}{2},i\right)\right]\right\}+\sin(1)=
$$
$$
=\frac{1}{2}Re\left[iE\left(\frac{1+a}{2},i\right)\right]+\sin(1)
$$
Also $x$ is positive integer and $\{\sqrt{y}\}=0$.
Hence when $a>0$, then
$$
\lim_{x\rightarrow\infty}\sum^{x}_{n=1}\frac{\sin(n^2)}{n^a}=\frac{1}{2}Re\left[iE\left(\frac{1+a}{2},i\right)\right]+\sin(1)+\lim_{y\rightarrow\infty}\int^{y}_{1}\{\sqrt{t}\}\frac{d}{dt}\left(\frac{\sin(t)}{t^{a/2}}\right)dt
$$
But
$$
\int^{y}_{1}\{\sqrt{t}\}\frac{d}{dt}\left(\frac{\sin(t)}{t^{a/2}}\right)dt=\int^{y}_{1}\{\sqrt{t}\}\frac{\cos(t)t^{a/2}-a/2\sin(t)t^{a/2-1}}{t^a}dt=
$$
$$
\int^{y}_{1}\{\sqrt{t}\}\left(\cos(t)t^{-a/2}-a/2\sin(t)t^{-a/2-1}\right)dt=\int^{y}_{1}\{\sqrt{t}\}\frac{\cos(t)}{t^{a/2}}dt-\frac{a}{2}\int^{y}_{1}\frac{\sin(t)}{t^{a/2+1}}\{\sqrt{t}\}dt.
$$
Clearly when $a$ is positive and constant
$$
\lim_{y\rightarrow+\infty}\int^{y}_{1}\frac{\sin(t)}{t^{a/2+1}}\{\sqrt{t}\}dt=2\lim_{x\rightarrow\infty}\int^{x}_{1}\frac{\sin(t^2)}{t^{a+1}}\{t\}dt<\infty,
$$
since $0\leq\{t\}<1$ and $-1\leq\sin(t^2)\leq 1$, for all $t>0$.
Hence it remains to find under what condition on $a>0$ we have
$$
\int^{\infty}_{1}\{\sqrt{t}\}\frac{\cos(t)}{t^{a/2}}dt=2\int^{\infty}_{1}\cos(t^2)t^{1-a}\{t\}dt<\infty,
$$
knowinig already that for all $0<a\leq 1$ we have
$$
\int^{\infty}_{1}\cos(t^2)t^{1-a}dt<\infty.
$$
However it is
$$
F(x)=\int^{x}_{1}\cos(t)\{\sqrt{t}\}dt=\frac{\sqrt{2\pi}}{2}\textrm{Fs}\left(\sqrt{\frac{2}{\pi}}\right)-\frac{\sqrt{2\pi}}{2}\textrm{Fs}\left(\sqrt{\frac{2x}{\pi}}\right)+
$$
$$
+\sum_{2\leq k<\sqrt{x}}\sin(k^2)+\{\sqrt{x}\}\sin(x)=O\left(\sum_{2\leq k<\sqrt{x}}\sin(k^2)\right).\tag 2
$$
The function $\textrm{Fs}(x)$ is the FresnelS function
$$
\textrm{Fs}(z):=\int^{z}_{0}\sin\left(\pi t^2/2\right)dt
$$
and it is known that
$$
\lim_{x\rightarrow+\infty}\textrm{Fs}(x)=\frac{1}{2}.
$$
Hence if we set
$$
S(x):=\sum_{2\leq k<x}\sin(k^2)
$$
and assume that $a=1/2-\epsilon$, $\epsilon>0$, then
$$
I(x)=\int^{x}_{1}\frac{1}{t^{a/2}}\cos(t)\{\sqrt{t}\}dt=\int^{x}_{1}\frac{F'(t)}{t^{a/2}}dt=\frac{F(x)}{x^{a/2}}+\frac{a}{2}\int^{x}_{1}\frac{F(t)}{t^{a/2+1}}dt=S_1+S_2,\tag 3
$$
where
$$
S_1=\frac{1}{x^{a/2}}S(\sqrt{x})+\frac{\{\sqrt{x}\}\sin x}{x^{a/2}}+\frac{\sqrt{\pi/2}}{x^{a/2}}\left(\textrm{Fs}\left(\sqrt{\frac{2}{\pi}}\right)-\textrm{Fs}\left(\sqrt{\frac{2x}{\pi}}\right)\right)
$$
and
$$
S_2=\frac{a}{2}\int^{x}_{1}\frac{1}{t^{1/4-\epsilon/2+1}}\{\frac{\sqrt{2\pi}}{2}\textrm{Fs}\left(\sqrt{\frac{2}{\pi}}\right)-\frac{\sqrt{2\pi}}{2}\textrm{Fs}\left(\sqrt{\frac{2t}{\pi}}\right)+
$$
$$
+\{\sqrt{t}\}\sin(t)
+\sum_{2\leq k\leq \sqrt{t}}\sin(k^2)\}dt.
$$
But it is known that there exists constant $C$ such that for infinite values of $x\in\textbf{N}$ holds
$$
\sum_{2\leq k\leq x}\sin(k^2)>Cx^{1/2}.\tag 4
$$
Hence for infinite values of $x$ we will have (easily)
$$
S_1>C_1x^{\epsilon/2}.\tag 5
$$
Moreover if we assume that
$$
\left|\sum_{2\leq k\leq x}\sin(k^2)\right|=O\left(x^{c+\delta}\right)\textrm{, }\forall \delta>0\textrm{ and }x\rightarrow+\infty,\tag 6
$$
then in view of (4) it must be $c\geq 1/2$. Also
$$
S_2=C_{\epsilon}(x)+\int^{x}_{1}t^{-1/4+\epsilon/2-1}\left(\sum_{2\leq k\leq \sqrt{t}}\sin(k^2)\right)dt.
$$
Hence
$$
\left|S_2\right|=\left|C_{\epsilon}(x)+\int^{x}_{1}t^{-1/4+\epsilon/2-1}\left(\sum_{2\leq k\leq \sqrt{t}}\sin(k^2)\right)dt\right|\leq
$$
$$
\leq \left|\left|C_{\epsilon}(x)\right|+\left|\int^{x}_{1}t^{-1/4+\epsilon/2-1}\left(\sum_{2\leq k\leq \sqrt{t}}\sin(k^2)\right)dt\right|\right|\leq
$$
$$
|C_{\epsilon}(x)|+\int^{x}_{1}\left|t^{-1/4+\epsilon/2-1}\left(\sum_{2\leq k\leq \sqrt{t}}\sin(k^2)\right)\right|dt=
$$
$$
=\left|C_{\epsilon}(x)\right|+C_2\int^{x}_{1}t^{-1/4+\epsilon/2-1}\left|\sum_{2\leq k\leq \sqrt{t}}\sin(k^2)\right|dt\leq
$$
$$ \leq\left|C_{\epsilon}(x)\right|+C_2\int^{x}_1t^{-1-1/4+\epsilon/2}t^{1/4+\delta/2}dt=
$$
$$
=\left|C_{\epsilon}(x)\right|+C_2\int^{x}_{1}t^{-1+\epsilon/2+\delta/2}dt=\left|C_{\epsilon}(x)\right|+\frac{2}{\delta+\epsilon}\left(x^{(\delta+\epsilon)/2}-1\right)<
$$
$$
<|C_{0}|+\log x+C_3d\log^2 x,\tag 7
$$
where $\epsilon>0$ and $\delta>0$ so small as we please and $d=\frac{\epsilon+\delta}{2}>0$, $C_3>0$ constant. It is also easy to see someone that $\left|C_{\epsilon}(x)\right|$ are bounded by a constant $C_0>0$.
Hence from $(3)$ and $(5),(7)$ we have if $a=1/2-\epsilon$, that
$$
\left|\int^{x}_{1}\frac{\cos (t)\{\sqrt{t}\}}{t^{a/2}}dt\right|=|S_1+S_2|\geq |S_1|-|S_2|>C_1x^{\epsilon/2}-|C_0|-\log x-C_3d\log^2 x,
$$
For infinite values of $x\in\textbf{N}$.
Hence
$$
\lim_{x\rightarrow+\infty}\int^{x}_{1}\frac{\cos(t)\{\sqrt{t}\}}{t^{a/2}}dt=+\infty
$$
and we conclude that if (6) holds, then $\textrm{inf}\geq1/2$.
I will argue now about the the case $a=\frac{1}{2}+2\epsilon$, $\epsilon>0$ i.e
 the case when $a$ is not $1/2$ but rather a limiting case and doesnot cover the case $a=1/2$. Both results $\textrm{inf}\geq1/2$ and $\textrm{inf}=1/2+2\epsilon$, clearly show us that for $1/2<a\leq1$ the sum $\sum^{\infty}_{n=1}\frac{\sin(n^2)}{n^a}$ converges and diverges for $0<a<1/2$, under the hypothesis $(6)$. For $a=1/2$, we dont know.
For $a=1/2+2\epsilon$, $\epsilon>0$ and for $x>>1$, we chose $\delta>0$ such that
$$
S\left(\sqrt{x}\right)\leq C_1x^{1/4+\delta},
$$
we get
$$
\left|I(x)\right|=|S_1+S_2|\leq  \left|C_1\frac{S\left(\sqrt{x}\right)}{x^{a/2}}+C_2\frac{a}{2}\int^{x}_{1}\frac{S\left(\sqrt{t}\right)}{t^{a/2+1}}dt\right|\leq
$$
$$
\leq\left|C_1'\frac{x^{1/4+\delta}}{x^{1/4+\epsilon}}+C_2'\left(\frac{1}{4}+\epsilon\right)\int^{x}_{1}\frac{t^{1/4+\delta}}{t^{1+1/4+\epsilon}}dt\right|=
$$
$$
=\left|C_1'x^{-(\epsilon-\delta)}+C_2'\left(\frac{1}{4}+\epsilon\right)\int^{x}_{1}\frac{dt}{t^{1+\epsilon-\delta}}\right|.
$$
For $\delta=\epsilon/2$ we get
$$
|I(x)|\leq \left|C_1'x^{-\epsilon/2}-\frac{2C_2'}{\epsilon}\left(\frac{1}{4}+\epsilon\right)\left(x^{-\epsilon/2}-1\right)\right|=
$$
$$
=\left|C_1'x^{-\epsilon/2}+\frac{C_2'}{2\epsilon}\left(1-x^{-\epsilon/2}\right)+2C_2'\left(1-x^{-\epsilon/2}\right)+H-H\right|\leq
$$
$$
\leq\left|C_1'x^{-\epsilon/2}+\frac{C_2'}{2\epsilon}\left(1-x^{-\epsilon/2}\right)+2C_2'\left(1-x^{-\epsilon/2}\right)+H\right|+\left|H\right|.\tag 8
$$
Now we set
$$
X=C_1'x^{-\epsilon/2}+\frac{C_2'}{2\epsilon}\left(1-x^{-\epsilon/2}\right)>0
$$
and
$$
Y=2C_2'\left(1-x^{-\epsilon/2}\right)+H>0
$$
and I use the inequality
$$
\left|X+Y\right|\leq \left|X-\frac{Y}{4\epsilon}\right|,\tag 9
$$
which is is true for small $\epsilon$ and $x>1$ since we can write equivalent
$$
\left|X+Y\right|^2\leq \left|X-\frac{Y}{4\epsilon }\right|^2\Leftrightarrow X^2+Y^2+2XY\leq X^2+\frac{Y^2}{16\epsilon^2}-\frac{XY}{2\epsilon }\Leftrightarrow
$$
$$
Y^2+2XY\leq\frac{Y^2}{16\epsilon^2}-\frac{XY}{2\epsilon}\Leftrightarrow Y+2X\leq \frac{Y}{16\epsilon^2}-\frac{X}{2\epsilon}\Leftrightarrow
$$
$$
\left(\frac{1}{16\epsilon^2}-1\right)Y\geq X\left(2+\frac{1}{2\epsilon}\right)
$$
This last inequality holds for all small $\epsilon>0$ and $x>>1$ since it can be writen equivalently as
$$
(1-16\epsilon^2)Y-X(32\epsilon^2+8\epsilon)\geq0\Leftrightarrow
$$
$$
2\epsilon(1+2\epsilon)\left(C_2'-4\epsilon C_1'+4C_2'\epsilon\right)x^{-\epsilon/2}\geq 0,
$$
where we have used the value
$$
H=\frac{2(C_2'+4C_2\epsilon)}{1-4\epsilon}
$$
Hence (9) is true and we can extract from relation (8) the conclusion
$$
\left|I(x)\right|\leq \left|C_1'x^{-\epsilon/2}+\frac{C_2'}{2\epsilon}\left(1-x^{-\epsilon/2}\right)+2C_2'\left(1-x^{-\epsilon/2}\right)+H\right|+\left|H\right|=
$$
$$
=\left|X+Y\right|+\left|H\right|\leq
$$
$$
\leq\left|C_1'x^{-\epsilon/2}+\frac{C_2'}{2\epsilon}\left(1-x^{-\epsilon/2}\right)-\frac{C_2'}{2\epsilon}\left(1-x^{-\epsilon/2}\right)-\frac{H}{4\epsilon}\right|+|H|=
$$
$$
=\left|C_1'x^{-\epsilon/2}-\frac{H}{4\epsilon}\right|+|H|.
$$
Hence
$$
\epsilon |I(x)|\leq C_1'x^{-\epsilon/2}\epsilon+H/4+|H|\epsilon.
$$
Hence we conclude that
$$
\epsilon \left|I(x)\right|=O(1)
$$
is bounded. Hence for $\epsilon>0$ small but constant the $I(x)$ are bounded.


TITLE: Show the graph is regular
QUESTION [4 upvotes]: If $G$ is a connected finite graph which has no triangles, and $G$ has the property that if two vertices have a common neighbour then they have exactly two common neighbours, does $G$ have to be strongly regular?

Note: I showed it is regular, but how to prove/disprove it's strongly regular?

REPLY [1 votes]: The answer is "no". A counterexample is provided by the hypercube graph $Q_n$ for any $n\gt2$, in particular by the nearest-neighbour graph of the corners of a cube. The conditions are fulfilled, but some non-adjacent vertices have $2$ common neighbours while others have $0$.


TITLE: Cohomology of a constant etale sheaf
QUESTION [8 upvotes]: Let $X$ be a smooth proper algebraic variety over $\mathbb{C}$.
I know that in the analytic world, there is an isomorphism between the de Rham cohomology and the cohomology of the constant sheaf $\underline{\mathbb{C}}$:
$$ H^i_{dR}(X^{an}/\mathbb{C}) \cong H^i(X^{an}, \underline{\mathbb{C}}). $$
The proof of this relies on the fact that the sequence of sheaves on $X^{an}$
$$ 0 \to \underline{\mathbb{C}} \to \Omega^0_{X^{an}} \to \Omega^1_{X^{an}} \to \Omega^2_{X^{an}} \to \cdots $$
is exact.
There is also an isomorphism between $H^i_{dR}(X^{an}/\mathbb{C})$ and $H^i_{dR}(X^{Zar}/\mathbb{C})$.
I assume that this also works for $H^i_{dR}(X^{et}/\mathbb{C})$.
However $H^i(X^{Zar}, \underline{\mathbb{C}}) = 0$ because a constant Zariski sheaf is flabby.

What is $H^i(X^{et}, \underline{\mathbb{C}})$?

So far as I can see, neither of the above arguments to calculate this work: a constant étale sheaf is not flabby, because étale open sets need not be connected (actually I am not sure if the definition of flabby sheaves in the Zariski topology makes sense for the étale site).
And the sequence
$$ 0 \to \underline{\mathbb{C}} \to \Omega^0_{X^{et}} \to \Omega^1_{X^{et}} \to \Omega^2_{X^{et}} \to \cdots $$
is not exact because, if $X=\mathbb{P}^1$, its stalks at the origin are
$$ 0 \to \mathbb{C} \to R \to R \, dX \to 0 $$
where $R$ is the strict Henselization of $\mathbb{C}[X]_{(X)}$.
$R$ is algebraic over $\mathbb{C}[X]$ so does not contain $\log(1+X)$ and hence the 1-form $dX/(1+X)$ is not exact.

REPLY [11 votes]: The etale cohomology groups $H^i(X_{et},V)$ vanish for $i > 0$ if $X$ is a quasi-compact, quasi-separated, normal scheme, and $V$ is a $\mathbb{Q}$-vector space. (In fact, one may replace "normal" with "geometrically unibranch.") To see this, recall the following presumably classical fact.
Lemma: If $X$ is a normal integral scheme with generic point $j:\eta \to X$, then $\underline{\mathbb{Q}} \simeq R j_* \underline{\mathbb{Q}}$ in $D(X_{et})$.
Proof: We can check this on stalks, so we may assume $X = \mathrm{Spec}(R)$ for a strictly henselian normal local ring $R$. Then $R\Gamma(X_{et},\mathbb{Q}) \simeq \mathbb{Q}$ as $\Gamma(X_{et},-)$ is exact with $X$ connected, so it is enough to show $R\Gamma(\eta_{et},\mathbb{Q}) \simeq \mathbb{Q}$. As etale and Galois cohomology are identified for fields, it is enough to show that $R\Gamma_{cont}(G,\mathbb{Q}) \simeq \mathbb{Q}$ for the absolute Galois group $G$ of $\eta$, which is a standard fact in (profinite) group cohomology.
The lemma implies the claim in the first sentence of this answer for $V = \mathbb{Q}$ after applying the global sections functor $R\Gamma$ (and using the corresponding result for fields). In general, one writes $V$ as a direct sum of copies of $\mathbb{Q}$, and uses that that etale cohomology commutes with arbitrary direct sums (as $X$ is quasi-compact and quasi-separated) to reduce to the previous case.


TITLE: Formalized attempt of proof that well ordered-ness ( of subsets of $\mathbb{Z}$ that are bounded below) implies induction seems to have issue?
QUESTION [0 upvotes]: I want to prove that well-orderedness on the integers implies induction. The proof is the classical "assume a contradiction" and see what happens.
So begin with an intended contradiction:
\begin{align*}
 &\quad A\subset\mathbb{Z} \;\wedge\; 0\in A \;\wedge\; (n\in A \implies (n+1)\in A) \;\;\implies\;\; \neg \mathbb{N}\subset A \\
 &\quad\text{...unpacking definition of $\neg\mathbb{N}\subset A$...} \\
 &= A\subset\mathbb{Z} \;\wedge\; 0\in A \;\wedge\; (n\in A \implies (n+1)\in A) \;\;\implies\;\; \exists n\in \mathbb{N} \;s.t. \neg n\in A \\
 &\quad\text{...definition of bunches...} \\
 &= A\subset\mathbb{Z} \;\wedge\; 0\in A \;\wedge\; (n\in A \implies (n+1)\in A) \;\;\implies\;\; \exists B\subset \mathbb{N} \;s.t. |B| > 0 \;\wedge\; &&B\cap A = \emptyset
\end{align*}
Working within the context of what has been proven so far, we let $c$ be the minimal element of the non-empty set $B$:
\begin{align*}
 &\quad (c = \min B)  \\
 &\quad\text{...$0\in A \wedge B\cap A = \emptyset$...}\\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; c > 0 \\
 &\quad\text{...algebra...}\\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; c - 1 > -1 \\
 &\quad\text{...properties of $>$ and $\geq$...}\\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\;  c - 1 \geq 0 \\
 &\quad\text{...definition of $\geq$...} \\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; (c - 1 = 0 \vee c > 0) \\
 &\quad \text{...$0\in A$...} \\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; [(c - 1 = 0 \implies c - 1\in A) \vee c > 0] \\
 &\quad\text{...$n-1\in A \implies n\in A$...} \\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; [(c - 1 = 0 \implies c - 1\in A \implies c\in A) \vee c > 0] \\
 &\quad\text{...transitivity of $\implies$...}\\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; [(c - 1 = 0 \implies c\in A) \vee c > 0]\\
 &\quad\text{...distributivity of $\wedge$ over $\vee$...}\\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \wedge (c - 1 = 0 \implies c\in A) \vee \neg (c\in A) \wedge c > 0 \\
 &\quad\text{...contrapositive law...}\\
 &= c = \min B \;\;\implies\;\; \neg (c\in A) \wedge (\neg(c\in A) \implies \neg(c - 1 = 0)) \vee \neg (c\in A) \wedge c > 0 \\
 &\quad\text{...law of discharge...} \\
 &= c = \min B \;\;\implies\;\; \neg(c\in A) \wedge \neg(c - 1 = 0) \vee \neg (c\in A) \wedge c > 0 \\
 &\quad\text{...De Morgan's Law...} \\
 &= c = \min B \;\;\implies\;\; \neg(c \in A \vee c - 1 = 0) \;\vee\; \neg (c \in A) \wedge c > 0 \\
 &\quad\text{...De Morgan's Law...} \\
 &= c = \min B \;\;\implies\;\; \neg(c \in A \vee c - 1 = 0) \;\vee\; \neg ((c \in A) \vee c \leq 0) \\
 &\quad\text{...De Morgan's Law...} \\
 &= c = \min B \;\;\implies\;\; \neg[(c \in A \vee c - 1 = 0) \wedge (c \in A \vee c \leq 0)] \\
 &\quad\text{...factoring out $c:A$...} \\
 &= c = \min B \;\;\implies\;\; \neg[c \in A \vee (c - 1 = 0 \wedge c \leq 0)] \\
 &\quad\text{...algebra...} \\
 &= c = \min B \;\;\implies\;\; \neg[c \in A \vee (c = 1 \wedge c \leq 0)] \\
 &\quad\text{...integer properties...} \\
 &= c = \min B \;\;\implies\;\; \neg[c \in A \vee \bot] \\
 &\quad\text{...definition of $\vee$...} \\
 &= c = \min B \;\;\implies\;\; \neg(c \in A)
\end{align*}
I am supposed to get a simpler contradiction, which is that $c = \min B \wedge c \in A$. Formally, I do not get this. What is my error?

REPLY [1 votes]: It seems that you're trying to prove that $$\forall A,\Bigl[(A\subseteq\Bbb Z)\wedge(0\in A)\wedge\bigl((n\in A)\implies (n+1\in A)\bigr)\Bigr]\implies \Bbb N\subseteq A.$$
Sadly, if this is indeed what you're trying to show, you got off to a bad start.
Recall that for statements $p,q,$ we have that $p\implies q$ is equivalent to $q\vee\neg p.$ On the one hand, then, $p\implies\neg q$ is equivalent to $\neg q\vee\neg p,$ or $\neg(p\wedge q).$ On the other hand, $\neg(p\implies q)$ is equivalent to $\neg(q\vee\neg p),$ or $p\wedge\neg q.$ But $p\wedge\neg q$ is a strictly stronger statement than $\neg(p\wedge q)$--that is, $p\wedge\neg q$ implies $\neg(p\wedge q),$ but the converse implication doesn't hold--so you've erred in your negation in the first step. Instead, you should start with the assumption $$\exists A:\Bigl[(A\subseteq\Bbb Z)\wedge(0\in A)\wedge\bigl((n\in A)\implies (n+1\in A)\bigr)\Bigr]\wedge\neg(\Bbb N\subseteq A).$$
Can you take it from there?


TITLE: Explicit chain homotopy for the Alexander-Whitney, Eilenberg-Zilber pair
QUESTION [7 upvotes]: Let $A$ and $B$ be simplicial abelian groups, and let $N_\ast(-)$ denote the normalized chain complex functor.  Let
$$AW_{A,B}\colon N_\ast(A\otimes B)
\longrightarrow N_\ast(A)\otimes N_\ast(B)$$
and
$$ EZ_{A,B}\colon N_\ast(A)\otimes N_\ast(B)
\longrightarrow N_\ast(A\otimes B)$$
denote the Alexander-Whitney map
and the Eilenberg-Zilber map respectively.
Does anyone know of an explicit chain homotopy realizing
$$EZ_{A,B}\circ AW_{A,B}\sim Id_{N_\ast(A\otimes B)}.$$
Motivation for its existence can be found in the comments of this question.

REPLY [8 votes]: You have it in page 7 of this paper.


TITLE: Is the Laplace operator w.r.t. all coordinates or not?
QUESTION [2 upvotes]: I have the equation
\begin{align}
\begin{cases}
    u_t(\boldsymbol{x},t)-\nabla^2u(\boldsymbol{x},t) = 0, &\boldsymbol{x}\in D, & t>0, \\
    u(\boldsymbol{x},t)=0, & \boldsymbol{x}\in\partial D, & t>0, \\
    u(\boldsymbol{x},0)=u_0(\boldsymbol{x}), &\boldsymbol{x}\in D,
\end{cases}
\end{align}
where $\boldsymbol{x}=(x_1,x_2,x_3)$.
Does the Laplace operator acts on the vector $\boldsymbol{x}$ AND $t$? I.e.
\begin{align}
\nabla^2 u(\boldsymbol{x},t)=\frac{\partial^2 u}{\partial x_1^2}+\frac{\partial^2 u}{\partial x_2^2}+ \frac{\partial^2 u}{\partial x_3^2}+\frac{\partial^2 u}{\partial t^2}
\end{align}
or just
\begin{align}
\nabla^2 u(\boldsymbol{x},t)=\frac{\partial^2 u}{\partial x_1^2}+\frac{\partial^2 u}{\partial x_2^2}+ \frac{\partial^2 u}{\partial x_3^2}
\end{align}
If the second one is correct, why is it so?

REPLY [1 votes]: In this context (heat equation) the Laplacian is taken in the space variables only -- because this is what the heat equation is.
When considering a PDE where the role of Laplacian is not clear, the author will either state the interpretation of Laplacian in text, or use indices to clarify it:
$$\nabla_x^2 u(x,t) \quad \text{vs.}\quad \nabla_{x,t}^2 u(x,t)$$
or
$$\Delta_x u(x,t) \quad \text{vs.}\quad \Delta_{x,t} u(x,t)$$


TITLE: What is the mathematical foundation of Control Theory?
QUESTION [43 upvotes]: There is a question which I'm wondering again and again in recent months. I have taken courses on elementary differential equations, signals and systems, linear control systems, general theory of circuits and networks but I still do not know how can a simple linear integral transformation (Laplace transform) be so much helpful in analyzing and designing linear systems. For example, I think I somewhat know what "time domain" is, but how about the "frequency domain"?
Consider a block diagram in the frequency domain. Conceptually, what do the blocks represent? What is traveling(?) on the connections between blocks? First, I have thought that instead of taking care of the statement "when does some phenomenon happens" we consider "how many times does a phenomenon oscillate", but how can this approach be more helpful? Is it the best (optimal) way of treating such problems?
I think control systems and even systems have a more general meaning in mathematics. I even think that the very problem of "controlling a system" does have multiple "paradigms" — A.I., neural networks, state space approach, fuzzy logic, robust control, adaptive control, etc.
What I'm looking for is a book (preferred) or paper discussing the very beginning notions of system, control system, its history, and more importantly, what is the field or language in mathematics to study systems rigorously? Dynamical systems? Game theory? Differential equations? Linear algebra? A.I?
Any help is appreciated. Thanks.

P.S.: I've already studied these books:

Alan Oppenheim's Signals and Systems (I think it is the best in the field)

Ogata's Modern Control Engineering

Desore's Basic Circuits Theory

Charles A - Kuh and Ernest S's A rather brief book on the history of control systems ($H_\infty$ methods and so on, but I didn't get much; at least, this book induced some information on me that nobody actually knows what "feedback" is, why is it so helpful and why we should take samples of the output! It wasn't a precise book, I admit)

26 May 2013:
As I said, I am looking for a book or article discussing the origins of Control Theory and Systems. Seven days are passed since I started the bounty, yet I didn't find an answer. I'll get to the bottom of this issue as soon as I get some free time. Thanks.

REPLY [4 votes]: To the asker's desire

"for a book or article discussing the origins of Control Theory and
  Systems"

I can recommend the 2014 article Control: A Perspective by Astrom and Kumar.
Control Theory is a branch of applied mathematics, and as such doesn't really have a predefined "Mathematical Foundation". Techniques from complex variable theory, differential equations, linear algebra, optimization and calculus of variations, functional analysis, differential geometry, graph theory, Lie groups, etc. all make appearances in different places throughout the vast literature on systems and control.
One of the answers mentions automata theory, which puzzled me, since I've rarely seen this used outside of applications that deal with information systems. It's certainly not central to control theory in the way a control theorist would think of it.


TITLE: How to show this sequence converges to 1?
QUESTION [0 upvotes]: Let $x\:>\:1$ and consider $a_n$ a sequence of positive numbers and $\lim _{n\to \infty }\left(a_n\right)\:=\:0$
prove that: $$\lim _{n\to \infty }\left(x^{a_n}\right)\:=\:1$$
I thought about the squeeze theorem because its easy to bound from below, but from above i really can't find something. tnx!
edited: NOT using logarithm rules or functions stuff.

REPLY [4 votes]: Since $\displaystyle \lim_{n\to \infty} a_n = 0$, there exists a positive integer $N$ such that $0 < a_n < \frac{1}{2}$ for all $n \ge N$. If $b_n := x^{a_n} - 1$, then $b_n > 0$ for all $n$ and
$$x = (1 + b_n)^{1/a_n} \ge (1 + b_n)^{\lfloor\frac{1}{a_n}\rfloor} \ge 1 + \left\lfloor\frac{1}{a_n}\right\rfloor b_n > 1 + \left(\frac{1}{a_n} - 1\right)b_n > 1 + \frac{b_n}{2a_n}$$
for all $n \ge N$. Therefore, $0 < b_n < 2a_n(x - 1)$ for all $n \ge N$. Now it follows from the squeeze theorem that $\displaystyle \lim_{n\to \infty} b_n = 0$, i.e., $\displaystyle \lim_{n\to \infty} x^{a_n} = 1$.

REPLY [2 votes]: For a fixed $a>1$ the function $f(x) = a^x$ is continuous. Hence if $x_n$ is a convergent sequence of real numbers:
$\lim_{x\to \infty}(a^{x_n}) = a^{\lim_{x\to\infty}x_n}$.
Thus the limit in question is $x^0 = 1$.

REPLY [0 votes]: If you are allowed to use continuity of the function $a \mapsto x^a$, then,
$$\lim_{n \to \infty} x^{a_n} = x^{\lim_{n \to \infty} a_n} = x^0=1.$$

If you're not allowed to use that, note that the sequence $(x^{a_n})$ is strictly decreasing (this is actually unnecessary). I assume you've shown that $1 \le x^{a_n}$ for all $n$. For any $\epsilon>0$, choose $N$ large enough so that $x^{a_n}<1+\epsilon$ for all $n \ge N$. This is possible by choosing $N$ large enough so that $a_n \le \frac{\log(1+\epsilon)}{\log x}$ for all $n \ge N$, since $a_n \to 0$.

REPLY [0 votes]: let m be a natural number ,now suppose $$a_{n}=\frac{m}{n}\\\lim_{n\rightarrow \infty }a_{n}=\lim_{n\rightarrow \infty }\frac{m}{n}=0$$
$$x>1\\x^{a_{n}}=x^{\frac{m}{n}}=\sqrt[n]{x^m}\\$$if  we name $$x^m=X$$
$$\lim_{n\rightarrow \infty }\sqrt[n]{x^m}=\lim_{n\rightarrow \infty }\sqrt[n]{X}=\lim_{n\rightarrow \infty }X^\frac{1}{n}\rightarrow 1$$

REPLY [0 votes]: Since $a_n$ is positive and converges to $0$, for any $k\in \Bbb N$, there is an $N\in \Bbb N$ such that $a_n<\frac1k$. That means that there is a strictly increasing sequence $n_i$ of natural numbers such that $a_{n}<\frac1i$ as long as $n>n_i$.
So you can compare $x^{a_{n_i}}$ and $\sqrt[i]{x}$, where the last one converges to $1$ as $i$ goes to $\infty$.


TITLE: Unitary dual of $\{0\}$ and $\mathbb R$
QUESTION [0 upvotes]: How to prove that, the unitary dual of $\{0\}$ and $\mathbb R$ are the trivial identity representation $id$ and the representation $\chi_x (y) = e^{i x y}; y\in \mathbb R$,  respectively.
Thank you in advance

REPLY [0 votes]: For a finite group $G$, the number of inequivalent irreducible unitary
representations equals the number of conjugacy classes of $G$. The trivial group only has one conjugacy class.
The second question on $\mathbb{R}$ has been answered at this MSE question.


TITLE: How to find gauge pressure in pipe
QUESTION [0 upvotes]: If I have a pipe for which I know the height and velocity of the fluid at the left and right end, and I am asked to find the gauge pressure at the right end, how would I go about doing this if the internal pressure at both ends is unknown to me? I am aware that finding the difference in pressures will give me the correct answer, though I dont necessarily understand why this is the same thing as P(g) = P(abs) - P(atm). It just doesn't intuitively make sense to me. Any explanation would be much appreciated. Thanks!!

REPLY [0 votes]: If the right end is open to the atmosphere, then the gauge pressure is zero, and the absolute pressure at the right ends is equal to atmospheric pressure.


TITLE: Question about valuation and blow up (a lemma in GIT book)
QUESTION [4 upvotes]: I'm reading Mumford's book Geometric Invariant Theory and confused about the proof of a lemma on Page 91&92:

Lemma:
Let $V_0$ be a smooth surface over an algebraically closed field $k$
with char$k=0$, and let $P$ be a closed point on $V_0$. Let $x,y$ be uniformizing parameters at $P$ on $V_0$ and $I:=(x^{r_0}\cdot y^{s_0},...,x^{r_n}\cdot y^{s_n})$ where $r_i,s_i$ are integers. For all positive rational number $a=p/q$ where $(p,q)=1$, define a valuation associate to $a$ such that discrete, rank 1 and centered at $P$:
$v_a(\sum a_{i j} x^iy^j)=\min_{a_{i j}\neq 0}\{ip+jq\}$.
Let $V$ be the normalization of blow up $Bl_{I} V_0$. Then the prime exceptional divisors on $V$ are exactly those prime divisors $E_a$ corresponding to valuations $v_a$, where the least integer in the sequence of integers $r_ip+s_iq, 0\leq i\leq n$ occurs at least twice.

Q1: In the proof of Lemma, he first claimed if $v$ is a valuation of $K(V)=K(V_0)$ centered at $P$ , then  the center of $v$ has positive dimensional center if and only if $v$ has positive dimensional center on one of the following surfaces:
$Spec(\mathcal{O}_{P, V_0}[\frac{x^{r_0}\cdot y^{s_0}}{x^{r_i}\cdot y^{s_i}},...,\frac{x^{r_n}\cdot y^{s_n}}{x^{r_i}\cdot y^{s_i}}]), 0\leq i\leq n$
How to prove this claim?
Q2: To show every discrete valuation on $V$ is of form $v_a$ for some positive rational number $a$, he pass to the completion $Spec(\widehat{\mathcal{O}_{P, V_0}})$, and claimed that since $I$ is invariant under automorphisms $(x,y)\mapsto (\alpha x, \beta y)$, $v_a$ should also invariant under these automorphism, and he said it's easy to check only discrete valutions with required properties are $v_a$'s. But how to check this?
For Q1, I know the center of $v_a$ on $V$ is irreducible, hence to show center has positive dimension, we only need to show $v_a$ centered at two distince closed points. But I don't know how to continue.
Thanks for any help.

REPLY [1 votes]: do you know how we cunstruct a blow up? for your first question blow up of affine $A$ at the ideal $I$ is covered by $$Spec(A[\frac{x^{r_0}\cdot y^{s_0}}{x^{r_i}\cdot y^{s_i}},...,\frac{x^{r_n}\cdot y^{s_n}}{x^{r_i}\cdot y^{s_i}}]),0\le i\le n$$, now let $Q$ be a prime ideal defining a point with positive dimension at center of $v$ over $$Spec(\mathcal{O}_{P, V_0}[\frac{x^{r_0}\cdot y^{s_0}}{x^{r_i}\cdot y^{s_i}},...,\frac{x^{r_n}\cdot y^{s_n}}{x^{r_i}\cdot y^{s_i}}])$$ and because you have finitely many dominator it define a point with positive dimension of one $Spec(A[\frac{x^{r_0}\cdot y^{s_0}}{x^{r_i}\cdot y^{s_i}},...,\frac{x^{r_n}\cdot y^{s_n}}{x^{r_i}\cdot y^{s_i}}])$ where $U= Spec A$ is a neighborhood of $P$.
For your second question, I don't completely understand your statement but the idea should be something like this: let's $v(x)=p,v(y)=q$ because the valuation is discrete, after a rescaling we can assume $(p,q)=1$. now we know that
$$v(\sum a_{i j} x^iy^j)\ge\min_{a_{i j}\neq 0}\{ip+jq\}$$
by third property of valuations,in fact from the third property we get that if $$v(a)\not =v(b),v(a+b)=min(v(a),v(b))$$, so we only have to handle the case that $\forall i,j,ip+jq$ is a constant. so we can assume that in $$t=\Sigma a_{ij}x^iy^j$$ powers of $x$ are strictly increasing. we prove by induction on the number of terms of $t$ that $$v(\sum a_{i j} x^iy^j)=ip+jq$$.assume that $$v(\sum a_{i j} x^iy^j)>ip+jq$$ then by invariance you mentioned $$v(\sum a_{i j} x^iy^j)=v(\sum a_{i j} (\alpha x)^iy^j)$$ lets $n$ be the biggest power of $x$ appearing in $t$ and take $\alpha^n=-1$ (base is algebraicly closed so such an $\alpha$ exist) now $$\sum a_{i j} x^iy^j+\sum a_{i j} (\alpha x)^iy^j$$ has less terms than $t$ and it's valuation is bigger than $v(t)>ip+jq$ which is a contradiction by induction hypothesis.