TITLE: Prove ${2n\choose n}=\sum\limits_{k=0}^n {n\choose k}^2$
QUESTION [0 upvotes]: Prove ${2n\choose n}=\sum\limits_{k=0}^n {n\choose k}^2$

My Approach: I will be making use of $$\tag 1\quad{m+n\choose r} = {m\choose 0}{n \choose r} + {m\choose 1}{n\choose r- 1} + \cdot\cdot\cdot + {m\choose r}{n \choose 0}$$ and $$\tag 2{a \choose b}={a\choose a-b}$$

By (1) $${2n\choose n} = {n+n\choose n}= {n\choose 0}{n\choose n}+{n\choose 1}{n\choose n-1}+\cdot\cdot\cdot + {n\choose n}{n\choose 0}$$
By (2) $${2n\choose n} = {n\choose 0}^2 + {n\choose 1}^2 + \cdot\cdot\cdot + {n\choose n}^2$$
Then $${2n\choose n}=\sum\limits_{k=0}^n {n\choose k}^2$$

Please have a look at my solution and give me any hints and\or suggestions you may have.

REPLY [1 votes]: Using the fact that $\sum_{k=0}^{l}\binom{n}{k}\binom{m}{l-k}=\binom{n+m}{l}$. Substituting $l,m=n$ and seeing that $\binom{n}{k}=\binom{n}{n-k}$.
Best regards.


TITLE: If $f: \Bbb{N} \to \Bbb{N}$ is strictly increasing and $f(f(n))=3n$, find $f(2001)$.
QUESTION [9 upvotes]: I have this question which seems a little harder than I thought. It has been about an hour for me hitting aimless thoughts on this one. I can really use a hint here if some one knows how to tackle it.

Let $f: \Bbb{N} \to \Bbb{N}$ such that $f$ is strictly increasing and $f(f(n))=3n$ for all $n \in \Bbb{N}$. Find $f(2001)$.

REPLY [13 votes]: Part A: $f(1)=2$.
First $f(1)$ cannot be $1$. Otherwise $3=f(f(1)) = f(1) = 1$.
So $f(1)$ is at least $2$. But $3 = f(f(1)) > f(2)$ because $f$ is increasing and $f(1)>2$.
Then $f(2)$ can only be $2$ or $1$. But $f(1)$ is at least $2$ and $f(1)<f(2)$.
This is a contradiction. So $f(1)$ must be $2$.

Part B
Since $2 = f(1)$, then $f(2) = f(f(1)) = 3\cdot1 = 3$. Similarly $f(3) = f(f(2)) = 6$ and
$f(6) = f(f(3)) = 9$.
Since f is strictly increasing, then $f(4)$ and $f(5)$ has to be $7$ and $8$.

Part C
Claim: $f(3^n) = 2\cdot 3^n $
Why? Let $f(n) = x$. Then $f(f(n)) = f(x)$.
So $3n = f(x)$. And $f(3n) = f(f(x)) = 3x = 3f(n)$. So iteration follows:
$$f(3^n) = 3f(3^{n-1}) = \ldots = 3^n\cdot f(1) = 2\cdot3^n$$
From this result,
$$f(2\cdot3^n) = f(f(3^n)) = 3\cdot3^n$$
Now for $x\in[3^n, 2\cdot3^n]$, $f(x)\in[2\cdot3^n, 3\cdot3^n]$. Both $x$ and
$f(x)$ have exactly $3^n$ values. Note that $f(x)$ has to be positive integers
and strictly increasing. Thus if $x$ increases by $1$, $f(x)$ has to increase by
 $1$ too. So
$$ f(3^n + m) = 2\cdot3^n + m ; m \in [0,3^n]$$

Part D
Claim:$ f(2\cdot3^n + m) = 3(3^n + m) ; m \in [0,3^n]$.
Why? From Part C, $f(2\cdot3^n) = 3\cdot3^n$ and $f(3\cdot3^n) = 2\cdot3^{n+1}$
For any $x\in[2\cdot3^n, 3\cdot3^n]$, based on result of C, there exists a z such that $x = f(z) = 2\cdot 3^n + m$ where $z = 3^n + m$, and $m\in[0,3^n]$. Hence, $f(x) = f(f(z)) = 3z$, i.e.
$$ f(2\cdot 3^n + m) = 3\cdot(3^n + m) ; m \in [0,3^n]$$

Part E
$f(2001) = f(2\cdot3^6 + 543) = 3(3^6 + 543) = 3\cdot(729+543) = 3816$.


TITLE: Central extensions versus semidirect products
QUESTION [9 upvotes]: Consider an extension $E$ of a group $G$ by an abelian group $A$.
$$1 \to A \overset{\iota}{\to} E \overset{\pi}{\to} G \to 1$$
Two special kinds of extensions are:

Central Extensions:  $A$ is contained in the centre of $E$.
Semidirect products: $\pi$ has a section, i.e. a homomorphism $s : G \to E$ with $\pi \circ s = \mathrm{id}_G$.

It perhaps reasonable to think of these two types of extensions as "orthogonal" since an extension is both central and a semidirect product if and only if it is split, i.e. there is an isomorphism $E \cong A \times G$ through which $
\iota$ and $\pi$ become identified with the standard inclusion and projection.
These two types of extensions are nice in the sense that we can construct all of them in terms of certain external data, namely 2-cocycles and actions.

Given $\psi:G \times G \to A$ satisfying $\psi(g_1,g_2)  \psi(g_1 g_2,g_3) = \psi(g_1,g_2 g_3)\psi(g_2,g_3),$ we can devise an extension $E_\psi = A\times G$ with product $(a_1,g_1)(a_2,g_2)=(a_1a_2\psi(g_1,g_2),g_1g_2),$ and $\iota,\pi$ given by the standard inclusion and projection.
Given a homomorphism $\theta:G \to \mathrm{Aut}(A)$, define $E=A \rtimes_\theta G$ to be $A \times G$ with product $(a_1,g_1)(a_2,g_2) = (a_1 \theta_{g_1}(a_2),g_1g_2)$.

Since the cases of central extensions and semi-direct product are somehow "orthogonal", I am tempted to ask the following ill-defined question:

Main Question: Can we think of all extensions $E$ of a group $G$ by an abelian group $A$ as being somehow built out of these two orthogonal cases of central extensions and semidirect products?

and maybe

Followup Question 1: Can arbitrary extensions be constructed out of external data in the same way as central extensions and semidirect products? The data would need to be something which mixes the notions of a 2-cocycle and an action.

One further question, a bit frivolous, just popped into mind.

Followup question 2: If we want to study extensions $A \to E \to G$ where $A$ is nonabelian, we can still talk about the extensions which are semidirect products. However, the notion of a central extension no long makes any sense. Is there a property $(P)$ which is an appropriate analogue of central extension in this context? Can $(P)$ be chosen so that the trivial split extension is the only extensions which satisfies $(P)$ and is also a semidirect product?

REPLY [3 votes]: Actually this might be pretty straightforward. Let $1 \to A \overset{\iota}{\to} E \overset{\pi}{\to} G \to 1$ be any extension of $G$ by an abelian group $A$. Since $A$ is normal in $E$, any $e \in E$ determines an automorphism $a \mapsto eae^{-1}$. Moreover, since $A$ is abelian, replacing $e$ by $ea_1$ for some $a_1 \in A$ does not change this automorphism, i.e. the action of $e$ on $A$ only depends on the coset $eA$. Thus, we do in fact have a well-defined action
\begin{align*}
\theta:G \to \mathrm{Aut}(A) && && \theta_g(a) = eae^{-1} \text{ for any } e\in \pi^{-1}(g),
\end{align*}
(it is easy to check $g \mapsto \theta_g$ is still a homomorphism)
Next we need something like a 2-cocycle. For every $g \in G$, choose arbitrarily an $e(g)$ in the coset $\pi^{-1}(g)$. Since $e(g_1) e(g_2)$ and $e(g_1g_2)$ are equal under $\pi$, we get a map
\begin{align*}
\psi : G \times G \to A && \text{ defined by } &&e(g_1)e(g_2) = \psi(g_1,g_2) e(g_1g_2)
\end{align*}
To see what happens with the 2-cocycle identity, we should compute $e(g_1)e(g_2)e(g_3)$ in two different ways. Because $A$ is not necessarily central in $E$, things come out slightly differently.
\begin{align*}e(g_1)e(g_2)e(g_3) &=\psi(g_1,g_2)e(g_1g_2)e(g_3) \\
&= \psi(g_1,g_2)\psi(g_1g_2,g_3) e(g_1g_2g_3)
\end{align*}
\begin{align*}e(g_1)e(g_2)e(g_3) &=e(g_1)\psi(g_2,g_3)e(g_2g_3) \\
&= e(g_1)\psi(g_2,g_3)e(g_1)^{-1} e(g_1)e(g_2g_3) \\
&= \theta_{g_1}(\psi(g_2,g_3)) \psi(g_1,g_2g_3) e(g_1,g_2g_3)
\end{align*}
so we find that $\psi$ satisfies the identity
$$\psi(g_1,g_2) \psi(g_1g_2,g_3) =\psi(g_1,g_2g_3) \theta_{g_1}(\psi(g_2,g_3))$$
a rather mild variation on the 2-cocycle identity. For convenience, we had may as well require that $e(1)=1$ and that $e(g^{-1}) =e(g)^{-1}$, since this is easy to enforce. This leads to the additional identities
$$\psi(g,g^{-1})=\psi(g,1)=\psi(1,g)=1$$
Now we just need to turn all this around:

Let $G$ be a group, $A$ an abelian group. suppose that we have the following data:

A homomorphism $\theta : G \to \mathrm{Aut}(A)$
a map $\psi : G \times G \to A$ satisfying $\psi(g_1,g_2) \psi(g_1g_2,g_3) =\psi(g_1,g_2g_3) \theta_{g_1}(\psi(g_2,g_3))$ and $\psi(g,g^{-1})=\psi(g,1)=\psi(1,g)=1$ (this second requirement can most likely be dispensed with, at the cost of complicating the formulas).

Define $E$ to be $A \times G$ as a set with product given by
  $$(a_1,g_1)(a_2,g_2) = (a_1 \theta_{g_1}(a_2) \psi(g_1,g_2),g_1g_2).$$
  (This group law is invented by thinking of $(a,g)$ as $ae(g)$ for $g \mapsto e(g)$ some set-theoretic section of $\pi$ defining $\psi$, and multiplying accordingly). There are some routine algebraic checks to show that this defines a group product:

$(1,1)(a,g)=(1 \theta_1(a) \psi(1,g),1g)=(a,g)$
$(a,g)(1,1) = (a \theta_g(1) \psi(g,1),g1)=(a,g)$
$(\theta_g^{-1}(a^{-1}), g^{-1})(a,g)=(\theta_g^{-1}(a^{-1})\theta_g^{-1}(a)\psi(g^{-1},g), g^{-1}g)=(1,1)$
$(a,g)(\theta_g^{-1}(a^{-1}), g^{-1})=(a \theta_g \theta_g^{-1}(a^{-1}) \psi(g,g^{-1}), gg^{-1}) =(1,1)$

and, finally,
  \begin{align*}
[(a_1,g_1)(a_2,g_2)](a_3,g_3) &= (a_1 \theta_{g_1}(a_2)\psi(g_1,g_2),g_1g_2)(a_3,g_3) \\
&=(a_1 \theta_{g_1}(a_2) \psi(g_1,g_2)\theta_{g_1g_2} (a_3)\psi(g_1g_2,g_3), g_1g_2g_3) \\
&=(a_1 \theta_{g_1}(a_2)\theta_{g_1} \theta_{g_2}(a_3) \psi(g_1,g_2)\psi(g_1g_2,g_3), g_1g_2g_3) \\
&=(a_1 \theta_{g_1}(a_2)\theta_{g_1} \theta_{g_2}(a_3) \psi(g_1,g_2g_3) \theta_{g_1}(\psi(g_2,g_3)), g_1g_2g_3) \\
&=(a_1\theta_{g_1}(a_2\theta_{g_2}(a_3)\psi(g_2,g_3))\psi(g_1,g_2g_3),g_1g_2g_3) \\
&=(a_1,g_1)(a_2 \theta_{g_2}(a_3)\psi(g_2,g_3),g_2g_3)\\
&=(a_1,g_1)[(a_2,g_2)(a_3,g_3)]
\end{align*}
It is quite obvious that $(a,g) \mapsto g$ is a surjective homomorphism whose kernel $\{(a,1) : a \in A\}$ is a isomorphic to $A$.

Strictly speaking, I did not prove that every extension of a group $G$ by an abelian group $A$ comes from the above construction, but this will surely be the case since, as discussed above, every extension $E$ determines such data $\theta$ and $\psi$ once one chooses a section $g \mapsto e(g) : G \to E$. So, one just needs to check the extension constructed out of that data is isomorphic to the original one.


TITLE: Convergence of stochastic process
QUESTION [1 upvotes]: As we know, to prove the convergence of stochastic process, we could either show the convergence of finite dimensional distribution and tightness of the process, or use techniques of martingale problems. What about the following Markov process:
$L=\frac{1}{2}p(1-p)\frac{d^{2}}{dp^{2}}-\frac{\theta}{2}p\frac{d}{dp}+\log(\theta) p(1-p)(2p-1)\frac{d}{dp},  p\in[0,1]$
We can see that the generator explodes when $\theta\rightarrow0$. How can we find the limit of this process as $\theta\rightarrow0$. Apparently, the techniques of martingale problems are not applicable here!

REPLY [3 votes]: This drifted Wright--Fisher diffusion seems to converge to the rather degenerate process $X_0 = p$, $X_t = 1/2$ for $t>0$, which is why I would do it by hand: Show that for every $t>0$ and every $p\in(0,1)$, the process started from $p$ is with high probably near $1/2$ at time $t$, uniformly for $p\in[\epsilon,1-\epsilon]$, say (you can use standard arguments from diffusion theory for that, i.e. speed measure, Green function...). This yields convergence in finite-dimensional distributions. Convergence in Skorokhod topology will not hold, since continuous functions are closed in this topology, hence a continuous process cannot converge to a process with a jump.


text:
\begin{document}
\maketitle
\begin{abstract}
We study a variant of Erd\H os' unit distance problem, concerning dot products between successive pairs of points chosen from a large finite point set. Specifically, given a large finite set of $n$ points $E$, and a sequence of nonzero dot products $(\alpha_1,\ldots,\alpha_k)$, we give upper and lower bounds on the maximum possible number of tuples of distinct points $(A_1,\dots, A_{k+1})\in E^{k+1}$ satisfying $A_j \cdot A_{j+1}=\alpha_j$ for every $1\leq j \leq k$.
\end{abstract}

\section{Introduction}
In \cite{Erd46}, Erd\H os introduced two popular problems in discrete geometry, the single distance problem and the distinct distances problem. Given a finite point set in the plane, the single distance problem asks how often a single distance can occur between pairs of points, while the distinct distances problem asks how many distinct distances must be determined by pairs of points. In the decades since these problems were first posed, they have been studied by many people, with varying degrees of success. See \cite{BMP, GIS} for surveys of these and related problems. The distinct distances problem was resolved in 2010 by Guth and Katz in \cite{GK}. One popular variant of this family of problems involves replacing the distance between two points by the dot product of two points, \cite{GIS, Steinerberger}.

In addition to studying the dot products determined by pairs of points chosen from a set, there has been much interest in studying dot products determined by larger subsets of points. See \cite{Bahls, Fickus, IS, TV12} for some examples and applications. In this note, we concern ourselves with chains, which are sequences of points restricted by the dot products between successive pairs. We borrow notation from related problems on distances in \cite{BIT, PSS}. Specifically, if we fix a $k$-tuple of real numbers, $(\alpha_1, \alpha_2, \dots, \alpha_k)$, then a {\it $k$-chain} of that type is a $(k+1)$-tuple of points, $(R_1, R_2, \dots, R_{k+1}),$ such that for all $j=1,\dots, k,$ we have $R_j\cdot R_{j+1}=\alpha_j.$ For example, if we fix a triple of real numbers, $(\alpha, \beta, \gamma)$, a 3-chain of that type will be a set of four points, where the dot product of the first two points is $\alpha$, the dot product of the middle two points is $\beta$, and the dot product of the last two points is $\gamma.$ We follow convention and refer to 2-chains as hinges.

We will assume a given $k$-tuple $(\alpha_1, \alpha_2, \dots, \alpha_k)$ consists of nonzero real numbers, unless explicitly stated otherwise. Also, if two quantities, $X(n)$ and $Y(n)$, vary with respect to some natural number parameter, $n$, then we write $X(n) \lesssim Y(n)$ if there exist constants, $C$ and $N$, both independent of $n$, such that for all $n> N$, we have $X(n)\leq CY(n)$. If $X(n) \lesssim Y(n)$ and $Y(n) \lesssim X(n)$, we write $X(n) \approx Y(n).$

\subsection{Main results}

In \cite{BS}, Dan Barker and the third listed author gave the following bound on the number of hinges (2-chains) in a large finite point set in the plane. They go on to show that this bound is tight.

\begin{theorem}\label{hinges}
Given a large, finite set $E$ of $n$ points in $\mathbb R^2$, and a pair of nonzero real numbers $(\alpha_1, \alpha_2)$, the maximum number of triples of points, $(R_1, R_2, R_3)\in E^3$ such that $R_1\cdot R_2 = \alpha_1$ and $R_2\cdot R_3 = \alpha_2$ is no more than $\lesssim n^2.$
\end{theorem}

In this note, we continue the work in \cite{BS} by offering upper bounds on the number of times that a $k$-chain of a given type can occur in any large finite point set. In what follows, we will always assume that $k,$ the length of the chain, is constant with respect to $n,$ the total number of points in a given large, finite point set. We denote this by $k\lesssim 1.$

\begin{theorem}\label{2chainzgeneral}
Given a large, finite set $E$ of $n$ points in $\mathbb R^2$ and a natural number $k\lesssim 1$, the maximum number of $k$-chains of the type $(\alpha_1,\dots, \alpha_k)$ that can exist in $E$, is $\lesssim n^\frac{2(k+1)}{3}.$
\end{theorem}

The next result gives a lower bound for how many $k$-chains of a given type we can construct in $\mathbb R^2.$

\begin{proposition}\label{sharpChains}
There exists a set $E$ of $n$ points in $\mathbb{R}^2$ and a $k$-tuple of nonzero real numbers $(\alpha_1,\dots, \alpha_k)$, for which which there are at least $n^{\ceil{(k+1)/2}}$ instances of $k$-chains of the type $(\alpha_1,\dots, \alpha_k),$ for any $k\lesssim 1.$
\end{proposition}

This result is surprising because the corresponding estimates for chains of distances appeared to be the same from previous investigations of 1- and 2-chains, but for higher values of $k$, their behaviors are very different. In particular, the best known upper bound on the number of times a single distance (1-chain) can occur is $n^\frac{4}{3}.$ The upper bound on the number of times a particular distance hinge (2-chain) can occur is $n^2,$ which is sharp. For dot products, we have the same upper bounds on 1- and 2-chains. Moreover, both bounds are known to be sharp.

However, the similarities end there. Both upper and lower bounds on the number of $k$-chains are different for larger values of $k.$ This is addressed in further detail in Subsection \ref{starlikeProof}. For example, Proposition \ref{sharpChains} tells us that we can construct a large finite set of $n$ points for which there are $\gtrsim n^4$ occurrences of a particular dot product 6-chain, but the main result in \cite{PSS} (Theorem 1.1 in that paper), implies that there can be no more than $\lesssim n^\frac{1079}{300}\lesssim n^{3.6}$ occurrences of any distance 6-chain.

Note, we have only considered nonzero dot products here, because of point sets like the one in the following construction.
\begin{remark}\label{2Lenz}
For any $k\lesssim 1$, there are infinitely many $n$ for which we can get $\gtrsim n^{k+1}$ occurrences of $k$-chains of the type $(0, \dots,0)$ by putting $n/2$ points on the $x$-axis and $n/2$ points on the $y$-axis.
\end{remark}

\subsection{Special cases}

One key feature of the construction in the proof of Proposition \ref{sharpChains} is the fact that dot products can repeat in ways that distances cannot. However, with a restriction on the types of point sets under consideration, so that this overlap of dot products is forbidden, we can get much better results by slightly modifying the proof of the main two-dimensional result in \cite{FK} (Theorem 2 in that paper). We discuss this further below.
\newpage

\begin{corollary} \label{starlike}
Given a large, finite set $E$ of $n$ points in $\mathbb R^2,$ with the property that no two points of $E$ lie on the same line as the origin, any $\epsilon >0,$ and a natural number $k\lesssim 1$, the maximum number of $k$-chains of the type $(\alpha_1,\dots, \alpha_k)$ that can exist in $E$ is no more than
$$\lesssim
\begin{cases}
n^\frac{k+3}{3} \qquad & \text{ if } k \equiv 0 \Mod{3}, \\
n^{\frac{k+3}{3}+\epsilon} & \text{ if } k \equiv 1 \Mod{3}, \\
n^\frac{k+4}{3} & \text{ if } k \equiv 2 \Mod{3}.
\end{cases}$$
\end{corollary}

Next, we follow \cite{BS} in offering $k$-chain bounds for sets of points where no line has many points.

\begin{corollary}\label{lightLines}
Given a large, finite set $E$ of $n$ points in $\mathbb R^2$, with no more than $t$ points on any line and a natural number $k\lesssim 1$, the maximum number of $k$-chains of the type $(\alpha_1,\dots, \alpha_k)$ that can exist in $E$, is
$$\lesssim \begin{cases}
\left(\log_2 n \right)^\frac{2k-6}{3} t^\frac{k-3}{3}n^{\frac{4k+12}{9}} \qquad& \text{ if } k \equiv 0 \Mod 3,\\
\left(\log_2 n \right)^\frac{2k-2}{3} t^\frac{k-1}{3}n^{\frac{4k+8}{9}} & \text{ if } k \equiv 1 \Mod 3,\\
\left(\log_2 n \right)^\frac{2k+2}{3} t^\frac{k+1}{3}n^{\frac{4k+4}{9}} & \text{ if } k\equiv 2 \Mod 3.
\end{cases}$$
\end{corollary}

We now introduce {\it $s$-adaptability}, which is used to quantify how well-distributed a set of points is. This property has been used to study many types of geometric point configuration problems. Using $s$-adaptability, results about discrete point sets can be partially translated to apply to sets with positive Hausdorff dimension. These latter results have consequences in geometric measure theory. See \cite{BIT, IJL, IMS, IRU, IS2}, for example.
A large, finite point set $E \subset [0,1]^2$, is said to be {\it $s$-adaptable} if the following two conditions hold:
\begin{align*}
\text{(energy)} \qquad &\frac{1}{{n \choose 2}}\sum_{\substack{P, Q \in E\\P\neq Q}} |P-Q|^{-s} \lesssim 1,\\
\text{(separation)} \qquad &\min\{|P-Q| : P,Q\in E,~ P\neq Q \}\geq n^{-\frac{1}{s}}.\\
\end{align*}
The separation condition from the definition of $s$-adaptability guarantees that there will be no more than $\lesssim n^{\frac{1}{s}}$ points on a line, so we can appeal to Corollary \ref{lightLines} and get the next result as a corollary.
\begin{corollary}\label{sAdapt}
Let $E \subset [0,1]^2$ be a set of $n$ points that is $s$-adaptable. For $s\leq 2$ and a natural number $k\lesssim 1$, the maximum number of $k$-chains of the type $(\alpha_1,\dots, \alpha_k)$ that can exist, is $$\lesssim \begin{cases}
\left(\log_2 n \right)^\frac{2k-6}{3} n^{\frac{4k+12}{9}+\frac{k-3}{3s}} \qquad& \text{ if } k \equiv 0 \Mod 3,\\
\left(\log_2 n \right)^\frac{2k-2}{3} n^{\frac{4k+8}{9}+\frac{k-1}{3s}} & \text{ if } k \equiv 1 \Mod 3,\\
\left(\log_2 n \right)^\frac{2k+2}{3} n^{\frac{4k+4}{9}+\frac{k+1}{3s}} & \text{ if } k\equiv 2 \Mod 3.
\end{cases}$$
\end{corollary}

We pause to note that no large, finite set of $n$ points in $[0,1]^2$ can be $s$-adaptable for $s>2,$ without violating the separation condition. To see this, partition the unit square into a $\sqrt n \times \sqrt n$ grid of squares of side-length $n^{-\frac{1}{2}}.$ Notice that there are $n$ such squares, and if points are to be separated by a distance much greater than $n^{-\frac{1}{2}}$, many of the small squares must be empty, but then there cannot be $n$ points in total. Moreover, when a set is not $s$-adaptable for any $s\geq \frac{3}{2},$ Corollary \ref{sAdapt} is outperformed by Theorem \ref{2chainzgeneral}. So the effective range for Corollary \ref{sAdapt} is $\frac{3}{2}\leq s \leq 2.$

\subsection{Higher dimensions}

Thus far, we have only considered point sets in the plane. Much like in Remark \ref{2Lenz}, there are point sets in higher dimensions that have many dot product chains of a given type. The difference here is that in higher dimensions, we can construct arbitrarily long dot product $k$-chains with $n^{k+1}$ points that have nonzero dot products, as opposed to in two dimensions, where we could only do that for zero dot products.

\begin{remark}\label{3Lenz}
Given a natural number $k \lesssim 1$ and any type of dot product $k$-chain, $(\alpha_1,\dots, \alpha_k),$ we can arrange about $n/(k+1)$ points along each of the following lines:
$$\{(x,y,z): x=1, y=0\},$$
$$\{(x,y,z): x=\alpha_1, z=0\},$$
$$\{(x,y,z): x=\alpha_2/\alpha_1, y=0\},$$
$$\{(x,y,z): x=\alpha_1\alpha_3/\alpha_2, z=0\}, \dots$$
and so on, so that the dot product of a point from the $j$th line and a point from the $(j+1)$th line is $\alpha_j,$ and alternating the free variable between $y$ and $z$ each time. This gives us a set of $n$ points with a total of about $n^{k+1}$ dot product $k$-chains of the specified type.
\end{remark}

Both Remark \ref{2Lenz} and Remark \ref{3Lenz} were inspired by the celebrated Lenz construction in $\mathbb R^4$ of $n/2$ points on a unit circle in the first two dimensions and $n/2$ points on a circle in the next two dimensions, which will give about $n^2$ point pairs (one point from each circle) separated by a distance of $\sqrt 2.$ These constructions make it clear that the study of chains in higher dimensions is trivial unless there are extra restrictions put on the point sets under consideration. For this reason, we offer the next results on point sets where we have some extra conditions on how many points can be on hyperplanes.

\begin{corollary}\label{hiDim}
Given any natural number $k \lesssim 1,$ and any large, finite set $E$ of $n$ points in $\mathbb R^d$, with no more than $r$ points on any $(d-1)$-hyperplane, and no more than $t$ points on any $(d-2)$-hyperplane, and any $\epsilon>0,$ the number of occurrences of a dot product $k$-chain of type $(\alpha_1,\dots, \alpha_k)$ is bounded above by
$$\lesssim \begin{cases}
n^\frac{k+3}{3}r^\frac{k-3}{3}t^2+n^{\frac{(4d-3)(k-1)+18d-8}{6d-3}+\epsilon}r^\frac{k-3}{3}t^\frac{2d-2}{2d-1} \qquad& \text{ if } k \equiv 0 \Mod 3,\\
 n^\frac{k+2}{3}r^\frac{k-1}{3}t+n^{\frac{(4d-3)(k-1)+9d-6}{6d-3}+\epsilon}r^\frac{k-1}{3}t^\frac{d-1}{2d-1} & \text{ if } k \equiv 1 \Mod 3,\\
n^\frac{k+1}{3}t^\frac{2k+2}{3}+n^{\frac{(4d-3)(k+1)}{6d-3}+\epsilon}t^{\frac{(2d-2)(k+1)}{6d-3}+\epsilon}+n^\frac{k+1}{3}r^\frac{k+1}{3} & \text{ if } k\equiv 2 \Mod 3.
\end{cases}$$
\end{corollary}

\subsection{Organization of this paper}
We will begin by recalling some of the elementary notions used herein in Section \ref{prelim}. Section \ref{proofs} follows, beginning with the most simple arguments. Since many of the arguments have the same basic structure, we omit details in the later proofs.

\section{Preliminaries}\label{prelim}

To keep track of dot products, we introduce some geometric tools.

\subsection{The $\alpha$-line for A}

Let $A$ be a point in $\arr^{2}$ with coordinates $(a_1,a_2)$, and let $\alpha \neq 0$ be a real number. A point $B$ in $\arr^{2}$ satisfies $A \cdot B = \alpha$, if and only if it lies on the line having the equation
$$a_{1}{x}+ a_{2}y=\alpha.$$
This line is called \textit{the $\alpha$-line for A,} denoted $\ell_\alpha(A).$ Note that $B$ is on the $\alpha$-line of $A$, if and only if $A$ is on the $\alpha$-line of $B$. We also call the unique line through a point $A$ and the origin the {\it radial line} of $A,$ and note that it is perpendicular to $\ell_\alpha(A)$ for any $\alpha.$\\

\begin{minipage}{5in}

\includegraphics[scale=1]{dpChainsFig1.pdf}\label{dpChainsFig1}\\
{\bf Figure 1:} Here we have the points $A$ and $B$, neither of which are the origin, and two positive numbers $\alpha$ and $\beta.$ The dashed lines are the radial lines of $A$ and $B$, and their $\alpha$-lines are perpendicular to their respective radial lines. The points $A$ and $B$ have a dot product of $\alpha,$ so $A$ is on $\ell_\alpha(B),$ and $B$ is on $\ell_\alpha(A).$ Notice that for $\beta \neq \alpha$, the points that have dot product $\beta$ with the point $A$ are on another line, $\ell_\beta(A)$ that is parallel to $\ell_\alpha(A).$\\\\
\end{minipage}

\subsection{Basic tools}

The following lemma appears in \cite{BS} and will be fundamental to our results. We include the short proof as it shows the flavor of the arguments to come.

\begin{lemma}\label{singlePoint}
If $A$ and $C$ are two points in $\mathbb{R}^2$ that do not lie on the same radial line, and $\alpha, \beta \in \mathbb{R}\setminus\{0\},$ then there exists exactly one point $B \in\mathbb{R}^2$ such that
$$B \cdot A = \alpha \text{  and  } B \cdot C = \beta $$
\end{lemma}

\begin{proof} Let $\ell_\alpha(A)$ be the alpha line for $A$ and let $\ell_\beta(C)$ be the beta line for $C.$ Since $A$ and $C$ do not lie on the same radial line and $\ell_\alpha(A)$ and $\ell_\beta(C)$ are perpendicular to the radial lines of $A$ and $C$, respectively, they are not parallel to each other and hence intersect in exactly one point. Therefore, there exists exactly one point $B \in \mathbb R^2$ such that $B \cdot A= \alpha \text { and }  B \cdot C=\beta.$
\end{proof}

The celebrated Szemer\'edi-Trotter Theorem from \cite{ST83} will also come into play in what follows.

\begin{theorem}\label{ST}
Given $n$ points and $m$ lines in the plane, the number of point-line pairs, such that the point lies on the line is
$$\lesssim\left(n^{\frac{2}{3}}m^{\frac{2}{3}}+n+m\right).$$
\end{theorem}

\section{Proofs}\label{proofs}

We begin with the following simple lemma, using Szemer\'edi-Trotter to bound how often a particular dot product can occur in a set of points in the plane.
\begin{lemma}\label{singleDP}
Given a large, finite set $E$ of $n$ points in the plane, no $\alpha\neq 0$ can be a dot product determined by pairs of points from $E$ more than $n^\frac{4}{3}$ times.
\end{lemma}
\begin{proof}
We can ignore the origin, as it has dot product zero with every point, so in what follows, we will assume that the origin is not in $E$. For each point $R\in E,$ draw the corresponding $\alpha$-line, $\ell_\alpha(R).$ So for each $R=(r_1,r_2)\in E,$ we have that $\ell_\alpha(R)$ can be written in the form $r_1x+r_2y=\alpha.$ We now show that these are unique.
\newpage

Consider any two distinct points $A, C\in E$. In the case that $A$ and $C$ do not lie on the same radial line, Lemma \ref{singlePoint} shows that there exists exactly one point, $B$, such that $A\cdot B = \alpha = B \cdot C.$ This means that $\ell_\alpha(A)\cap\ell_\alpha(C)$ is a single point, so they must be distinct lines.

Now suppose that $A=(a_1,a_2)$ and $C=(c_1,c_2)$ lie on the same radial line, and that it is not the $y$-axis. Then $a_1$ and $c_1$ are both nonzero, and there exists a nonzero $\lambda \in \mathbb R$ such that
$$c_1=\lambda a_1, \text{ and } c_2 = \lambda a_2.$$
By way of contradiction, suppose that $\ell_\alpha(A)=\ell_\alpha(C).$ Then we would have
$$a_1x+a_2y=\alpha=c_1x+c_2y=\lambda a_1x+\lambda a_2y,$$
for all $x\in \mathbb R.$ This implies that $a_1=\lambda a_1,$ which in turn tells us that $\lambda=1.$ But this means that $A$ and $C$ somehow share the same first coordinate and lie on the same radial line. The only radial line on which distinct points share the first coordinate is the $y$-axis, but we have assumed that $A$ and $C$ do not lie on the $y$-axis, so in this case $\ell_\alpha(A)$ cannot completely coincide with $\ell_\alpha(C)$.

In the case that $A$ and $C$ both lie on the $y$-axis, we would have that $a_1=c_1=0$, and the definition of $\ell_\alpha(A)$ would tell us $0\cdot x + a_2y=\alpha$, or that we can write $\ell_\alpha(A)$ as $y=(\alpha/a_2).$ Arguing similarly for $C$, we would see that $\ell_\alpha(C)$ could be written as $y=(\alpha/c_2)$. Putting these together yields
$$\frac{\alpha}{a_2} = y = \frac{\alpha}{c_2}.$$
But this means that $c_2 = a_2.$ This means that both points have coordinates $(0,a_2),$ meaning that they are the same point, which contradicts the fact that they are distinct. So again, $\ell_\alpha(A)$ cannot completely coincide with $\ell_\alpha(C)$.

Finally, we apply Szemer\'edi-Trotter. Since each of the $n$ points is associated to a unique line, we have a set of $n$ lines. Notice that by definition, if a point $P$ lies on a line $\ell_\alpha(Q),$ for some point $Q$, then $P\cdot Q=\alpha.$ That is to say, the number of point pairs for $E$ that determine the dot product $\alpha$ is precisely the number of incidences of points from $E$ and lines of the form $\ell_\alpha(Q),$ for some $Q\in E.$ Since there are $n$ points and $n$ lines, Theorem \ref{ST} tells us that the number of point-line incidences, and therefore occurrences of the dot product $\alpha$, is $\lesssim (n\cdot n)^\frac{2}{3}+n+n \approx n^\frac{4}{3},$ as claimed.
\end{proof}
\subsection{Proof of Theorem \ref{2chainzgeneral}}

\begin{proof} Let $E \subset \mathbb R^2$ be any set of $n$ points, and consider a given $k$-chain type $(\alpha_1, \dots, \alpha_k)$. Our aim is to bound the number of $(k+1)$-tuples of points in $E$ that determine these dot products pairwise, suppressing dependence on the $k$-tuples $(\alpha_1, \dots, \alpha_k)$, that is, the size of $\mathcal C_k(E), $ where
$$\mathcal C_k(E):= \{(R_1, \dots, R_{k+1})\in E^{k+1}:R_i\cdot R_{i+1}=\alpha_i, i=1,\dots, k\}.$$
We break into cases depending on the congruence class of $k$ modulo 3. From there, each case is broken up into component pieces which we estimate with repeated applications of Theorem \ref{hinges} and Lemma \ref{singleDP}.

\subsubsection{Case 1: $k\equiv 2 \Mod 3$} First off, if $k=2$, then we have the desired bound by direct appeal to Theorem \ref{hinges}. If $k>2$, then we just apply it repeatedly. Specifically, there exists a nonnegative integer $j$ such that $k=3(j-1)+2.$ Since $k+1=(3(j-1)+2)+1=3j,$ we are dealing with $(3j)$-tuples of points. We will break each $(3j)$-tuple down into $j$ consecutive triples. Start with $(R_1, R_2, R_3).$ By Theorem \ref{hinges}, we know that there can be no more than $n^2$ triples of the form $(R_1, R_2, R_3)$ with $R_1\cdot R_2 = \alpha_1$ and $R_2\cdot R_3 =\alpha_2.$ We will ignore any possible relationship between $R_3$ and $R_4$. Appealing to Theorem \ref{hinges} again, there can be no more than $n^2$ triples of the form $(R_4, R_5, R_6)$ with $R_4\cdot R_5 = \alpha_4$ and $R_5\cdot R_6 =\alpha_5.$ We continue in this fashion to bound the number of triples of each subsequent type. In so doing, we get a bound on the set
$$\mathcal C_{k,2}(E)=\{(R_1, \dots, R_{k+1})\in E^{k+1}:R_i\cdot R_{i+1}=\alpha_i, i=1,2,4,5, \dots, k,~ 3\hskip-1ex\not| i \}.$$
Namely, we can see that $|\mathcal C_{k,2}(E)|\lesssim (n^2)^{j},$ because for each of the $j$ triples, we get a bound of $n^2.$ Notice that $\mathcal C_k(E)\subset \mathcal C_{k,2}(E)$, so we get $|\mathcal C_k(E)|\leq |\mathcal C_{k,2}(E)|\lesssim (n^2)^{j}=n^\frac{2(k+1)}{3}.$

\subsubsection{Case 2: $k\equiv 1 \Mod 3$} In this case, there exists a nonnegative integer $j$ such that $k= 3j+1.$ So we can write $k+1 = 3j + 2.$ This means that we are looking at $j$ triples of points, followed by a pair of points. We can handle the $j$ triples by Case 1, and the final pair of points separately. That is to say, since $k-2\equiv 2 \Mod 3,$ the number of $(k-2)$-chains will be bounded above by
$$|\mathcal C_{k-2}(E)|\lesssim \left(n^2\right)^j=n^\frac{2(k-1)}{3}.$$
Now, we will ignore the relationship between $R_{k-1}$ and $R_k,$ and use Lemma \ref{singleDP} to bound the number of point pairs $(R_k, R_{k+1})$ such that $R_k\cdot R_{k+1}=\alpha_k$ by $n^\frac{4}{3}.$ That is to say,
$$|\mathcal C_1(E)|\lesssim n^\frac{4}{3}.$$
Putting these together, we get
$$|\mathcal C_k(E)|\leq |\mathcal C_{k-2}(E)|\cdot|\mathcal C_1(E)|\lesssim n^\frac{2(k-1)}{3}\cdot n^\frac{4}{3} = n^\frac{2(k+1)}{3}.$$

\subsubsection{Case 3: $k\equiv 0 \Mod 3$} In this case, there exists a nonnegative integer $j$ such that $k= 3j.$ Therefore we can write $k+1 = 3(j-1) + 2+2.$ So we have $(j-1)$ triples, followed by two pairs. So, similar to the previous case, we will deal with the $(j-1)$ triples using Theorem \ref{hinges}, then apply Lemma \ref{singleDP} twice to get
$$|\mathcal C_k(E)|\leq |\mathcal C_{k-4}(E)|\cdot|\mathcal C_1(E)|\cdot|\mathcal C_1(E)|\lesssim n^\frac{2(k-3)}{3}\cdot n^\frac{4}{3}\cdot n^\frac{4}{3} = n^\frac{2(k+1)}{3}.$$
\end{proof}

It is worth pointing out that in Case 1, if $k$ is also congruent to 5 modulo 6, we can get the same bounds by breaking up every sextuple into three pairs and using Lemma \ref{singleDP}, instead of breaking them into two triples and using Theorem \ref{hinges}.

\subsection{Proof of Proposition \ref{sharpChains}}
We will work inductively using a process similar to the proof of Theorem 2 of \cite{BS}. Given a natural number $k\geq 2,$ we will select a $k$-tuple of dot products $(\alpha_1, \dots, \alpha_k)$ and construct a set of points that exhibits many $k$-chains of that type. We note that for this construction, we will have the restriction that $\alpha_{2j}=\alpha_{2j-1}$ for all $j=1,\dots, \lfloor k/2\rfloor.$
\begin{proof}
Select a point $(1,1)$ and call it $R_2.$ Now choose some nonzero $\alpha_1\in\mathbb R.$ Place $n-k$ points on the $\alpha_1$-line $\ell_{\alpha_1}(R_2)$. We now set $\alpha_2=\alpha_1.$ Now we have $\approx n$ choices for each of the points $R_1$ and $R_3$ so that $R_1\cdot R_2 = \alpha_1$ and $R_2\cdot R_3 = \alpha_2=\alpha_1.$ Thus, the bound holds for $k = 2$.

Now select the point $(2,2)$, and call it $R_4.$ Let $\alpha_3$ be the unique nonzero dot product so that $\ell_{\alpha_1}(R_2)$ and $\ell_{\alpha_3}(R_4)$ are coincident. As before, we now have $\approx n$ choices for $R_5$ so that $R_3 \cdot R_4=\alpha_3$ and $R_4 \cdot R_5=\alpha_4=\alpha_3.$

Next, if necessary, we select the point $(3,3)$ and call it $R_6.$ Let $\alpha_5$ be the unique nonzero dot product so that $\ell_{\alpha_3}(R_4)$ and $\ell_{\alpha_5}(R_6)$ are coincident. Let $m=\lceil k/2 \rceil.$ We continue to repeat this process until we have selected the point $(m, m)$ to be $R_k$, if $k$ is even, or $R_{k+1}$, if $k$ is odd. Now, each of the even indexed points $R_j$ are fixed, but the odd indexed points each have $\approx n$ choices. Since there are $m$ odd indices, we have a total of $\approx n^m$ occurrences of the $k$-chain of type $(\alpha_1, \alpha_1, \alpha_2, \alpha_2, \dots, \alpha_m),$ as claimed.
\end{proof}

The idea behind this construction is actually a bit more flexible than written in the proof. The basic idea is to put $\lceil k/2\rceil$ points on the same radial line, and to evenly distribute the rest of them on a family of about $\lfloor k/2\rfloor$ lines perpendicular to the original line. In the construction given above, we put this family of lines all on one line, which restricts the possible values of dot products, $\alpha_j$, slightly more than is necessary.

\subsection{Proof of Corollary \ref{starlike}}\label{starlikeProof}

Given distinct points $P$ and $Q$, the circle of radius $\alpha$ centered at $P$ can intersect the circle of radius $\beta$ centered at $Q$ in at most two points. So the number of points that are of distance $\alpha$ to $P$ and distance $\beta$ to $Q$ is at most two. However, the corresponding property does not necessarily hold for dot products. Namely, there exist distinct points $P$ and $Q$ with infinitely many points that are of dot product $\alpha$ to $P$ and $\beta$ to $Q,$ even with $\alpha, \beta \neq 0.$ This happens when $P$ and $Q$ lie on the same radial line, as the next lemma shows.

\begin{lemma}\label{sameRadial}
If two points, $P$ and $Q$ have $\ell_\alpha(P)=\ell_\beta(Q),$ then $P$ and $Q$ lie on the same radial line.
\end{lemma}
\begin{proof}
Notice that if $P=(p_1,p_2)$ and $Q=(q_1,q_2)$ are the same point, the conclusion is trivially true. So we now assume that $P\neq Q.$ Let $\ell_\alpha(P)$ have the equation $y=mx+b.$ For any $x\in \mathbb R,$ we must have that $p_1x+p_2y=\alpha.$ Solving this for $y$ yields that
$$y=-\frac{p_1}{p_2}x+\frac{\alpha}{p_2}.$$
So we can see that $m=-\frac{p_1}{p_2}$ and $b=\frac{\alpha}{p_2}.$ But  $\ell_\beta(Q)$ is the same line, with the same equation, so we can similarly argue that $m=-\frac{q_1}{q_2}$ and $b=\frac{\beta}{q_2}.$ Comparing the two expressions for $m$ gives us
$$-\frac{p_1}{p_2} = m = -\frac{q_1}{q_2},$$
which implies that
\begin{equation}\label{sameM}
\frac{p_2}{p_1} = \frac{q_2}{q_1}.
\end{equation}
Notice that $P$ lies on a line through the origin with slope $\frac{p_2}{p_1},$ and $Q$ lies on a line through the origin with slope $\frac{q_2}{q_1}.$ But \eqref{sameM} says that these are the same line through the origin.
\end{proof}

We now state the main two-dimensional estimate in \cite{FK}, by Frankl and Kupavskii, which is Theorem 2 in that paper (an improvement on similar estimates from \cite{PSS}). We refer to a {\it distance $k$-chain} as a $k$-chain defined by distances instead of dot products. Since distances between distinct points are strictly positive, we only concern ourselves with $\alpha_j>0$ when dealing with distances. Let $u_2(n)$ denote the maximum number of pairs of points separated by exactly a unit distance in any set of $n$ points in the plane.

\begin{theorem}\label{FKthm}[Theorem 2 in \cite{FK}]
Given a large, finite set $E$ of $n$ points in $\mathbb R^2,$ any $\epsilon >0,$ and a natural number $k\lesssim 1$, the maximum number of distance $k$-chains of the type $(\alpha_1,\dots, \alpha_k)$ that can exist in $E$ is no more than
$$\lesssim
\begin{cases}
n^\frac{k+3}{3} \qquad & \text{ if } k \equiv 0 \Mod{3}, \\
n^{\frac{k-1}{3}+\epsilon}u_2(n) & \text{ if } k \equiv 1 \Mod{3}, \\
n^\frac{k+4}{3} & \text{ if } k \equiv 2 \Mod{3}.
\end{cases}$$
\end{theorem}

The key to the proof of Theorem \ref{FKthm} is a bound on incidences between points and circles, and it heavily relies on the fact that circles of the form $\mathcal C_\alpha(P)$ and $\mathcal C_\beta(Q)$ can intersect in at most two points. In order to follow the proof through for dot product $k$-chains, we would need to replace the circles that come from distances with lines that come from dot products. Now, in general, we would not have the guarantee that $\ell_\alpha(P)$ and $\ell_\beta(Q)$ intersect in a small number of points. However, with the additional hypothesis that no two points lie on the same radial line, we are guaranteed by Lemma \ref{sameRadial} that $\ell_\alpha(P)$ and $\ell_\beta(Q)$ intersect in at most one point, and we can follow the proof through in the cases that $k\equiv 0,2 \Mod{3},$ replacing circles with lines. To handle the case that $k\equiv 1 \Mod{3},$ we notice that by applying Lemma \ref{singleDP} for the maximum number of occurrences of a single dot product, we can replace $u_2(n)$ with $n^\frac{4}{3}.$

\subsection{Proof of Corollary \ref{lightLines}}

The following result is a rephrasing of what is proved in \cite{BS} (Theorem 2 and Remark 3 in that paper). It says that if we have some bounds on the number of points on a line, we can get better hinge bounds than the general case, as in Lemma \ref{hinges}.

\begin{theorem}\label{BSep}[Barker and Senger]
Given a large, finite set $E$ of $n$ points in $\mathbb R^2$, with no more than $t$ points on any line, the maximum number of hinges of the type $(\alpha_1, \alpha_2)$ that can exist in $E$, is $\lesssim \left(\log_2 n \right)^2 tn^{\frac{4}{3}}.$
\end{theorem}

To prove Corollary \ref{lightLines}, we repeat the proof of Theorem \ref{2chainzgeneral}, but use Theorem \ref{BSep} in place of Lemma \ref{hinges}. As before, we separate into three cases, depending on the congruence classes of $k$ modulo 3. Here we merely note the necessary modifications of each case of the proof of Theorem \ref{2chainzgeneral}.

\subsubsection{Case 1: $k \equiv 2 \Mod 3$} Find $j$ so that $k+1=3j$, and apply Theorem \ref{BSep} $j$ times to get an upper bound of
$$\lesssim \left(\left(\log_2 n \right)^2 tn^{\frac{4}{3}}\right)^j \approx \left(\log_2 n \right)^\frac{2k+2}{3} t^\frac{k+1}{3}n^{\frac{4k+4}{9}}.$$

\subsubsection{Case 2: $k\equiv 1 \Mod 3$} Set $j$ so that $k+1=3j+2$. We apply Theorem \ref{BSep} $j$ times and Lemma \ref{singleDP} once to get an upper bound of
$$\lesssim \left(\left(\log_2 n \right)^2 tn^{\frac{4}{3}}\right)^j\cdot n^\frac{4}{3} \approx \left(\log_2 n \right)^\frac{2k-2}{3} t^\frac{k-1}{3}n^{\frac{4k+8}{9}}.$$

\subsubsection{Case 3: $k\equiv 0 \Mod 3$} Fix $j$ so that $k+1=3(j-1)+2+2$. We apply Theorem \ref{BSep} $(j-1)$ times and Lemma \ref{singleDP} twice to get an upper bound of
$$\lesssim \left(\left(\log_2 n \right)^2 tn^{\frac{4}{3}}\right)^{(j-1)}\cdot n^\frac{4}{3}\cdot n^\frac{4}{3} \approx \left(\log_2 n \right)^\frac{2k-6}{3} t^\frac{k-3}{3}n^{\frac{4k+12}{9}}.$$

\subsection{Proof of Corollary \ref{hiDim}}

In order to prove Corollary \ref{hiDim}, we mimic the proof of Corollary \ref{lightLines}, but appeal to higher dimensional incidence theorems. As the construction in Remark \ref{3Lenz} shows, we have no hope to prove nontrivial estimates in higher dimensions in general, so we restrict ourselves to the case of sets where we have some control on the distribution of points. To this end, we introduce two estimates. The first is due to Ben Lund, in \cite{Lund}.

\begin{theorem}\label{lundHinges}[Lund, in \cite{Lund}]
Given a large, finite set $E$ of $n$ points in $\mathbb R^d$, with no more than $r$ points on any $(d-1)$-hyperplane, and no more than $t$ points on any $(d-2)$-hyperplane, a pair of nonzero real numbers $(\alpha_1, \alpha_2)$, and any $\epsilon>0,$ the maximum number of triples of points, $(R_1, R_2, R_3)\in E^3$ such that $R_1\cdot R_2 = \alpha_1$ and $R_2\cdot R_3 = \alpha_2$ is no more than
$$\lesssim nt^2+n^{\frac{4d-3}{2d-1}+\epsilon}t^{\frac{2d-2}{2d-1}+\epsilon}+nr.$$
\end{theorem}

This bound is an application of the following result, due to Lund, Sheffer, and de Zeeuw, from \cite{LSdZ}, but is based on the work of Fox, Pach, Suk, Sheffer, and Zahl, from \cite{FPSSZ}.

\begin{theorem}\label{dUDP}[Lund, Sheffer, and de Zeeuw, from \cite{LSdZ}]
Given a large, finite set $E$ of $n$ points and $m$ $(d-1)$-hyperplanes in $\mathbb R^d$, with no more than $t$ points on any pair of hyperplanes, and any $\epsilon>0,$ the maximum number of incidences of points and hyperplanes is no more than
$$\lesssim mt+m^{\frac{2(d-1)}{2d-1}+\epsilon}n^\frac{d}{2d-1}t^{\frac{d-1}{2d-1}}+n.$$
\end{theorem}

Though they are defined slightly differently in the last two results, for our purposes, both references to the quantity $t$ will coincide. Now we are ready to proceed. As before, we separate into three cases, depending on the congruence classes of $k$ modulo 3. Again, we merely note the necessary modifications of each case of the proof of Theorem \ref{2chainzgeneral}.

\subsubsection{Case 1: $k \equiv 2 \Mod 3$} Find $j$ so that $k+1=3j$, and apply Theorem \ref{lundHinges} $j$ times, setting $\epsilon' = \epsilon^\frac{3}{k+1}$. This yields an upper bound of
$$\lesssim \left(nt^2+n^{\frac{4d-3}{2d-1}+\epsilon'}t^{\frac{2d-2}{2d-1}+\epsilon'}+nr\right)^j$$
$$\approx n^\frac{k+1}{3}t^\frac{2k+2}{3}+n^{\frac{(4d-3)(k+1)}{6d-3}+\epsilon}t^{\frac{(2d-2)(k+1)}{6d-3}+\epsilon}+n^\frac{k+1}{3}r^\frac{k+1}{3}.$$

\subsubsection{Case 2: $k\equiv 1 \Mod 3$} Set $j$ so that $k+1=3j+2$. We apply Theorem \ref{lundHinges} $j$ times, each time with $\epsilon' = \epsilon^\frac{3}{k-1}$. We also apply Lemma \ref{dUDP}, with $m = n$ and $\epsilon''=\epsilon-\epsilon',$ since each point generates a unique hyperplane, akin to the $\alpha$-lines before. Notice that by definition, $t \leq r.$ This yields an upper bound of
$$\lesssim \left(nt^2+n^{\frac{4d-3}{2d-1}+\epsilon'}t^{\frac{2d-2}{2d-1}+\epsilon'}+nr\right)^j\cdot \left(nt+n^{\frac{2(d-1)}{2d-1}+\epsilon''}n^\frac{d}{2d-1}t^{\frac{d-1}{2d-1}}+n \right)$$
$$\approx n^\frac{k+2}{3}r^\frac{k-1}{3}t+n^{\frac{(4d-3)(k-1)+9d-6}{6d-3}+\epsilon}r^\frac{k-1}{3}t^\frac{d-1}{2d-1},$$
where we have omitted some cross terms, as they will always be dominated by terms present in the final expression given.

\subsubsection{Case 3: $k\equiv 0 \Mod 3$} Fix $j$ so that $k+1=3(j-1)+2+2$. Similarly to the previous case, we apply Theorem \ref{lundHinges} $(j-1)$ times and Lemma \ref{dUDP} twice, as in the previous case, with appropriate values of $\epsilon', \epsilon'', m, r,$ and $t$, to get an upper bound of
$$\lesssim \left(nt^2+n^{\frac{4d-3}{2d-1}+\epsilon'}t^{\frac{2d-2}{2d-1}+\epsilon'}+nr\right)^{j-1}\cdot \left(nt+n^{\frac{2(d-1)}{2d-1}+\epsilon''}n^\frac{d}{2d-1}t^{\frac{d-1}{2d-1}}+n \right)^2$$
$$\approx n^\frac{k+3}{3}r^\frac{k-3}{3}t^2+n^{\frac{(4d-3)(k-1)+18d-8}{6d-3}+\epsilon}r^\frac{k-3}{3}t^\frac{2d-2}{2d-1},$$
where we have again omitted some cross terms.

config: arxiv


TITLE: how to solve $min\{x \in \mathbb N_0 \quad |x \cdot 714\quad mod \quad 1972 \quad = \quad 1292 \quad mod \quad 1972 \} $ (modulo equation)
QUESTION [1 upvotes]: Question: How can I solve: $min\{x \in \mathbb N_0 \quad |x \cdot 714 \equiv 1292 \mod 1972 \} $ ?
I only know about:
$x \cdot a \equiv _m b \Rightarrow m|x \cdot a - b$
different way of notation:
$min\{x \in \mathbb N_0 \quad | x \cdot 714 \equiv_{1972} 1292\}$
How to go on?
I appreciate every hint.

REPLY [1 votes]: As $714=34\cdot21$, $1292=34\cdot 38$, $1972=34\cdot 58$, this is equivalent to solving $21 x\equiv 38\mod 58$.
We have to find the inverse of $21$ modulo $58$. The tool for this is the Extended Euclidean algorithm:
$$\begin{array}{rrrl}
\hline
r_i&u_i&v_i&q_i\\
\hline
58&0&1\\
21&1&0&2\\
\hline
16&-2&1&1\\
5&3&-1&3\\1&-11&4\\
\hline
\end{array}$$
Thus the inverse of $21$ mod $58$ is $-11\equiv47$. The solution is
$$x\equiv47\cdot 38\equiv (-11)(-20)\equiv 46\mod 58. $$


TITLE: Question regarding shifting of origin
QUESTION [0 upvotes]: At what point the origin be shifted, if the coordinates of a point $(-1,8)$ becomes $(-7,3)$.
Let origin be shifted by $(h,k)$. so we have
$-1=-7+h$
$8=3+k$
solving i get $(h,k)=(6,5)$. But textbook states answer to be $(-6,-5)$. i am thoroughly confused

REPLY [1 votes]: Let $(x,y) = (-1,8)$ be the original point, and $(x',y') = (-7,3)$ the shifted point.
Shift:
$P(x,y)$ $ \rightarrow $ $P'(x',y')$, where
$1) x $$ \rightarrow$ $x' = x + a$;
$2) y $$ \rightarrow$ $ y' = y + b$.
As row vectors:
$(x',y') =  (x,y) + (a,b)$.
Now calculate $a$ and $b$:
$1) - 7 = - 1 + a$,
$ a = - 6$;
$2) 3   = 8 + b$,
$b= - 5$.
Shift of origin $O$ $\rightarrow$ $O'$ :
$(x',y') = (0,0) + (-6,-5) = (-6,-5)$.


TITLE: Symmetry transformations on a quantum system; Definitions
QUESTION [10 upvotes]: We define a symmetry transformation of a system to be any transformation that, when performed, does not change the outcome of a measurement. Wigner's symmetry theorem says that any symmetry of a quantum system is represented by a linear and unitary operator which acts on the Hilbert space of physical states $\mathscr{H}$. So for any symmetry $\mathscr{E}$ there corresponds a unitary transformation $\mathcal{U}(\mathscr{E})$  acting on $\mathscr{H}$.
Suppose $\hat{A}$ is the Hermitian operator corresponding to some observable $A$ which has eigenvalue $\lambda\in\mathbb{R}$ with eigenvector $|\Phi\rangle$. Then, if the system is in a state $|\Psi\rangle$, the probability of measuring the value $\lambda$ of the observable $A$ is given by the Born rule;
\begin{align}
\text{Prob}(\lambda,\hat{A},\Psi)=\frac{|\langle\Phi|\Psi\rangle|^2}{\langle\Psi|\Psi\rangle\langle\Phi|\Phi\rangle}~.
\end{align}
We define a symmetry of a quantum system to be one that preserves the above probabilities. However, any unitary operator $\tilde{\mathcal{U}}$  acting on $\mathscr{H}$ will preserve these probabilities;
\begin{align}
\text{Prob}(\lambda,\hat{A'},\Psi')=\frac{|\langle\tilde{\mathcal{U}}\Phi|\tilde{\mathcal{U}}\Psi\rangle|^2}{\langle\tilde{\mathcal{U}}\Psi|\tilde{\mathcal{U}}\Psi\rangle\langle\tilde{\mathcal{U}}\Phi|\tilde{\mathcal{U}}\Phi\rangle}=
\frac{|\langle\Phi|\tilde{\mathcal{U}}^{\dagger}\tilde{\mathcal{U}}\Psi\rangle|^2}{\langle\Psi|\tilde{\mathcal{U}}^{\dagger}\tilde{\mathcal{U}}\Psi\rangle\langle\Phi|\tilde{\mathcal{U}}^{\dagger}\tilde{\mathcal{U}}\Phi\rangle}=\text{Prob}(\lambda,\hat{A},\Psi).
\end{align}
This would imply that any unitary transformation acting on $\mathscr{H}$ corresponds to a symmetry transformation of the system. I doubt this is true, so where did I go wrong in my definitions and how do I rectify it?

REPLY [10 votes]: There are many definitions of symmetry in Quantum Theory.
However your idea is not correct: symmetries, acting on states, do change outcomes of measurements, at least for one observable. Otherwise we are not speaking of a symmetry but of a gauge transformation.
In the Hilbert space formulation, and I will stick to this case here, and in the absence of superselection rules, a symmetry is a bijective operation that preserves some structure of the space of the states or of the space of observables. As far as I know there are four notions and they are those listed below.

Wigner symmetry: a bijective map from the space of rays (unit vectors up to phases) to the space of rays that preserves the probability transitions.
Kadison symmetry: a bijective map from the space of states (positive trace-class operators with unit trace) that preserves the convex linear combinations of states, i.e. it preserves the weights of the mixtures of pure states.
Kadison symmetry in dual formulation: a bijective map from the lattice of elementary observables (orthogonal projectors in the Hilbert space) into itself preserving the orthocomplemented $\sigma$-complete lattice structure. I.e. it preserves the logical structure of quantum theory.
Segal symmetry: a bijective map from the set of bounded everywhere defined self-adjoint operators into the same set that preserves the structure of Jordan algebra of that set, i.e. it preserves the structure of the set of observables.

Each of these definitions can be physically motivated. All definitions lead to the same characterization theorem (for 3 and 4 the Hilbert space must be separable with dimension $\neq 2$ to take advantage of Gleason's theorem).
Theorem [Wigner-Kadison-Segal]. A symmetry of type 1-4 is described by a unitary or antiunitary (depending on the symmetry if the Hilbert space has dimension $>1$ otherwise both possibilities are allowed).  Every unitary or anti unitary operator defines a symmetry of type 1-4 simultaneously.
A fundamental symmetry depending on time and continuous with respect to the natural topology (depending on the type 1-4), is the temporal evolution.
A symmetry of type 1-4 (also depending on time) is said to be a dynamical symmetry if it commutes with the temporal evolution.
(At this point, as more or less everybody knows, a theorem similar to Noether's one arises as a consequence of the Stone's theorem provided, as I supposed, the Hilbert space is complex).
When superselection rules enter the game (namely, the center of the von Neumann algebra of observables is non-trivial), the picture becomes more delicate and, for instance, Wigner's notion ceases to be a good notion because the same notion of transition probability becomes ambiguous (pure states and rays are not one-to-one). The same problem arises when the von Neumann algebra of observables admits a non Abelian commutant, as in chromodynamics (even if the center is trivial).


TITLE: Find the limit of convergence sequence
QUESTION [0 upvotes]: Let $x_1=1$ and $x_{n+1}=\sqrt{1+2/x_n}$, for $n\in\mathbb{N}$. Show that $\lim\limits_{n\rightarrow\infty} x_n$ exists and find the limit.
I have conjectured that odd-term sequence of $x_n$ is increasing and even-term sequence of $x_n$ is decreasing, but I am struggling to prove that $x_{2n+1}-x_{2n-1}>0$ and $x_{2n}-x_{2n-2}<0$, for all $n$.

REPLY [1 votes]: You can also see it as a fixpoint problem for $f(x) = \sqrt{1+\frac{2}{x}}$ on $[1,2]$ because
$$f:[1,2]\rightarrow [1,2] \mbox{ and } |f´(x)| = \left|-\frac{1}{x^2\sqrt{1+\frac{2}{x}}} \right| <= \frac{1}{\sqrt{3}}<1 \mbox{ on } [1,2]$$
So, the limit exists and is the only real solution to $x^3-x-2=0$.


TITLE: If $x\not\leq y$, then is $x>y$, or $x\geq y$?
QUESTION [3 upvotes]: I'm currently reading about surreal numbers from here.
At multiple points in this paper, the author has stated that if $x\not\leq y$, then $x\geq y$.
Shoudn't the relation be "if $x\not\leq y$, then $x>y$"?
Hasn't the possibility of $x=y$ already been negated when we said $x\not\leq y$?
Thanks in advance.

REPLY [3 votes]: In the paper linked to, there appears to be only a single primitive relation, written $x\leq y$, of which $y\geq x$ is just a notational variant. The equals part of the symbol is present because $x\leq x$ holds for all $x$ (theorem$~1.2$) but this is just a mnemonic device without formal implications. The negation of the relation $x\leq y$ is $x\not\leq y$, and it is written like that to remind the reader that it only affirms the absence of the relation $x\leq y$, not the presence of the relation $x\geq y$. In fact $x\not\leq y$ does imply $x\geq y$, but that is only shown in theorem$~1.4$.
Equality is not an explicitly mentioned relation (at least it seems so scanning rapidly), and so there is no reason to introduce $x>y$ as as shorthand for $x\geq y\land x\neq y$; for this reason theorem$~1.4$ is formulated the ways it is. But of course the hypothesis $y\not\leq x$ does exclude the possibility that $y$ actually is $x$; indeed the notation $x>y$ is introduced just after that theorem. However I do not agree with the given motivation "Theorem 1.4 means that the the surreal numbers are totally ordered", because they are not even partially ordered, merely preordered. In view of theorem 1.2 it is what I would call a total preorder (not sure the term is in use), a relation in which every pair is comparable at least one way, possibly both ways.
This is the next point; the paper states that $x\leq y\land x\geq y$ is not only possible when $x=y$. It introduces the relation $x\equiv y$ for $x\leq y\land x\geq y$, and given transitivity, this is an equivalence relation. What is really totally ordered is the set of equivalence classes for this equivalence relation.


TITLE: Is average over sphere lower bound on average over optimal great circle?
QUESTION [0 upvotes]: Say $f(r,\theta, \phi)$ is a function defined on the unit sphere, with $f \in [0, 1]$ for every point in the sphere. The average of this function over the unit sphere, $\overline{f}$, can be written as:
$$\overline{f} = \int_{0}^{2\pi}\int_{0}^{\pi}\int_{0}^{1} f(r,\theta, \phi) r^2 \sin{\theta}dr d\theta d\phi.$$
The average of the same function over the great circle whose parallel vector establishes an angle of $\theta$ with the $z$ axis, $\overline{f}_{\text{circ}_{\theta}}$, can be written as:
$$\overline{f}_{\text{circ}_{\theta}} = \int_{0}^{2\pi}\int_{0}^{1} f(r,\theta, \phi) rdr  d\phi.$$
My question is: does the following hold?
$$\max_{\theta \in [0,\pi]} \overline{f}_{\text{circ}_{\theta}} \geq \overline{f}.$$
Or, in words: is the average of the function over the great circle which maximizes it lower-bounded by the average over the whole sphere?
It seems intuitive to me that this should hold, by an argument of the type: the average of the function over the sphere is something like the average of the averages over the different circles that make up the sphere, so the average over the best circle should not be smaller than the overall average. However, I really don't know how to go about formalizing this. Some googling hasn't given me an answer, either because I'm not using the right words or because this isn't a particularly interesting problem.

REPLY [1 votes]: I don't think it's true. Let $$f(r,\theta,\phi)=\frac{r}{2\pi}$$
Then $$\bar f=2\int_0^1r^3dr=\frac12$$
and $$\bar f_{circ_\theta}=\int_0^1r^2dr=\frac13$$


TITLE: Using any input number to come up with an output number between 1 and X
QUESTION [0 upvotes]: I'm working on a way to load-balance a few different servers, but need help coming up with the math to do so. Lets say I have these random input numbers:
2353242
-4346323
43
64323
7544423

And just from an input number, I want to somehow get an output number between 1 and X.
So lets say if I were to run this function over a 1,000,000 random numbers, and that I want the output numbers to be between 1 and 5. Ideally, the numbers would roughly come close to:
200,000 input numbers would output 1
200,000 input numbers would output 2
200,000 input numbers would output 3
200,000 input numbers would output 4
200,000 input numbers would output 5

I'm not looking for just a random function to find between 1 and X, but a way to ALWAYS get the same output number with the same input number. The size of the input number is unknown, but the output number is always between 1 and X, X being the highest output number possible.
Thanks

REPLY [1 votes]: The simplest would to use $(X \% 5)+1$, the remainder on division by $5$ (plus $1$ to get the range $1-5$ instead of $0-4$). If you don't like the regularity because one remainder is more likely than another, you could hash $X$ before taking the remainder.


TITLE: Particle moving through a potential
QUESTION [0 upvotes]: Lets consider the potential:
$$V(x) = \begin{cases} V_0&x>0 \\ 0 & x< 0 \end{cases}$$
and $E > V_0$ and at $x = 0$ the wave gets dispersed/scattered.
My deductions:
The solution to the schrödinger equation are should have the form: $\psi(x) = Ce^{kx}$, with $k_{1,2} =\sqrt{\frac{2m(E-V_0)}{\hbar^2}}, \sqrt{\frac{2mE}{\hbar^2}}$.
The boundary condition should look like this: $\psi_1(x) = \psi_2(x), \psi_1'(x) = \psi_2'(x)$ where $\psi_1(x)$ is the wavefunction for $x>0$ and $\psi_2(x)$ is the wavefunction for $x<0$.
Questions:
Does the direction of the particle matter?
How do we decide which solution has a positive and a negative part or just one of the two?
How do we decide whether the solution should me made into a complex one (so which one "swings") ?

REPLY [0 votes]: The square roots for the $k_{1,2}$ are $+$ or $-$. Therefore you have to take both waves (incoming and reflected) into account on the side of the incoming particle (usually from $x=-\infty$) and one transmitted wave on the other side. For $x \gt0$ when $E$ is larger than $V_0$ you can also have an incoming oscillatory wave from $x=+\infty$ with reflection and transmission.


TITLE: 100 lbs of drag? Really? Chain running physics
QUESTION [1 upvotes]: Recently came across this video of an endurance technique involving the strapping of a 100lb chain to one's back and running along the grass dragging it behind. What is the true force experienced by the runner?

REPLY [1 votes]: The chain looks pretty long, only a meter or so is actually in the air. The gravitational force on the runner by the chain is not that big. The runner is bulled back/down in the angle that the chain attaches to the back. The chain cannot convey any torque or transversal force. So there are only a few kilograms of weight directly pulling on the runner.
A lot of force is probably the acceleration of the chain. The runner cannot keep his back at a steady velocity, it will move back and forward. Therefore there is a certain tug on the chain. The chain will be tugged forward, which is acceleration. Then it will quickly come to a rest again in the grass.
Do a thought experiment: If you are on ice skates gliding forward and the chain gliding on the ice, it would not be much work to pull the chain around. The friction on the grass is the problem. It is hard to quantify the force needed.
So although I am a to-be theoretician, I would suggest to just do a measurement with a force meter. It would probably be best to have a good resolution in time such that you can get the time dependent $F(t)$ and can then properly average over it.


TITLE: Function taxonomy based on contour topology
QUESTION [0 upvotes]: I only have a basic knowledge of topology so please correct any false assumptions. It seems that certrain functions have some similar (homotopic) contour curves, eg the gaussian and $-x^2$ have some homotopic contours around the global max. Has there been any research regarding such a taxonomy of n-ary functions? Is it even interesting?

REPLY [2 votes]: Nothing terribly sophisticated. Any $C^2$ function near a nondegenerate critical point will be locally like a quadric. See Second partial derivative test. In the degenerate case, add higher order terms.


text:
\section{Algorithms for Nonconvex Relaxations/Variants of RPCA}

In this section, we discuss nonconvex relaxations and variants of RPCA given in~\eqref{rpca-rank-L0} and algorithms for solving them. \sa{Some researchers} aim to (approximately) solve RPCA in~\eqref{rpca-rank-L0} directly without convexifying the rank function \sa{and/or} the $\ell_0$ norm. In~\cite{GoDec-icml-2011}, Zhou and Tao considered
\sa{a} variant of \eqref{rpca-rank-L0}:
\BE\label{zhou-tao}
\min \ \|L+S-M\|_F^2\ \st\ \rank(L)\leq \tau_r, \|S\|_0\leq \tau_s,
\EE
where $\tau_r$ and $\tau_s$ are given parameters to control the \sa{rank} of $L$ and sparsity of $S$. The authors proposed the GoDec algorithm which alternatingly minimizes the objective function \sa{in one variable while fixing the other, which is a special case of alternating projection method analyzed in~\cite{Lewis-Malick-alt-proj-manifold}.}
\sa{In particular,} a naive version of GoDec algorithm {iterates} as follows:
\BE\label{GoDec}
\BA{ll}
L^{k+1} & := \argmin_L \|L+S^k-M\|_F^2\ \ \st\ \ \rank(L)\leq \tau_r, \\
S^{k+1} & := \argmin_S \|L^{k+1}+S-M\|_F^2\ \ \st\ \ \|S\|_0\leq \tau_s.
\EA
\EE
The two subproblems correspond to two projections. Although the projection for $S$ is easy, the projection for $L$ requires \sa{computing a partial SVD}, which may be time consuming when the matrix size is large.
The authors proposed to use \sa{a low-rank approximation based on  bilateral random projections} to approximate this projection \sa{operation} which can significantly speed up the computation. The authors showed that \sa{the iterate sequence}
converges to a local minimum provided that the initial point is close to some point in the intersection of the two manifolds $\{L\mid\rank(L)\leq \tau_r\}$ and $\{S\mid \|S\|_0\leq \tau_s\}$. \sa{The convergence of GoDec
follows from the results in~\cite{Lewis-Malick-alt-proj-manifold}.}

\sa{In~\cite{hintermuller2015robust}, Hinterm\"{u}ller and Wu considered a regularized version of \eqref{zhou-tao}:
\begin{align}
\label{eq:ams-model}
&\min_{L,S\in\reals^{m\times n}} \norm{L+S-M}_F^2+\frac{\rho}{2}\norm{L}_F^2\\
&\quad \hbox{ s.t. }\quad \rank(L)\leq \tau_{r},\quad \|S\|_0\leq\tau_{s},\nonumber
\end{align}
where $\tau_{r},\tau_{s}>0$ are given model parameters as in \eqref{zhou-tao}, and $0\leq\rho\ll 1$ is a given regularization parameter. An \emph{inexact alternating minimization method} (
\emph{R2PCP}) on matrix manifolds is proposed to solve \eqref{eq:ams-model}. The iterates $L_{k+1}$ and $S_{k+1}$ are computed as ``inexact" solutions to subproblems $\min_L\{\norm{L+S_k-M}_F^2+\rho\norm{L}_F^2:\ \rank(L)\leq\tau_{r}\}$ and $\min_S\{\norm{L_{k+1}+S-M}_F^2:\ \|S\|_0\leq\tau_{s}\}$, respectively. Provided that a limit point of the iterate sequence exists, under some further restrictive technical assumptions, it is shown that first-order necessary optimality conditions are satisfied.}

Note that \sa{the convex relaxation in~\eqref{rpca-nuclear-L1} involves the nuclear norm $\|\cdot\|_*$ in the objective}. Algorithms dealing with nuclear norm (like the ones discussed in \sa{Section~\ref{sec:convex}}) usually require to compute its proximal mapping, which then require an SVD. This can be very time consuming when the problem size is large, \sa{even when $\min\{m,~n\}$ is in the order of thousands.} This has motivated \sa{researchers} to consider nonconvex relaxations of RPCA that avoid SVD calculations. One way to achieve \sa{SVD-free methods} is to factorize the low rank matrix $L\in\mR^{m\times n}$ as \sa{a} product of \sa{two low-rank matrices,}
i.e., factorize $L= UV^\top$, where $U\in\mR^{m\times r}$, $V\in\mR^{n\times r}$ and $r\ll \min\{m,n\}$ \sa{such that $r$ is an upper bound on $\rank(L^o)$.} This leads to many different nonconvex relaxations of RPCA.

{In~\cite{pmlr-v31-zhou13b}, Zhou and Tao considered a regularized version of \eqref{zhou-tao}:
\begin{align}
\label{eq:biliteral-model}
\min_{U,V,S} \rho_1\norm{S}_1 + \norm{UV^\top+S-M}_F^2\\
\quad \hbox{ s.t. }\quad \rank(U) = \rank(V) \leq \tau_{r},\nonumber
\end{align}
where $\rho_1>0$ and $\tau_{r}\in\integers_+$ such that $\tau_{r}\geq\rank(L^o)$. The authors propose a three-block alternating minimization algorithm, GreBsmo, for solving \eqref{eq:biliteral-model}. The proposed algorithm lacks theoretical convergence guarantees; but, on the other hand, according to numerical results reported in~\cite{pmlr-v31-zhou13b}, GreBsmo performs considerably better than both GoDec~\cite{GoDec-icml-2011} and inexact ALM method~\cite{Lin-Chen-Wu-Ma-iadm-2009} (around 30-100 times faster than both) when applied to foreground extraction problems.}

A nonconvex model of RPCA, {similar to one in~\cite{pmlr-v31-zhou13b},} is studied in \cite{Yi-Park-Chen-Caramanis-gradient} and a gradient descent (GD) method with proper initialization is proposed to solve it. The algorithm proposed in \cite{Yi-Park-Chen-Caramanis-gradient} has two phases and in both phases the objective is to reduce the function $Q(U,V,S):=\|UV^\top+S-M\|_F^2$. In the first phase, a sorting-based sparse estimator is used to generate a rough \sa{initial} estimate $S_0$ \sa{to the unknown sparse target matrix $S^o$}, and then $U_0$ and $V_0$ are generated via an SVD of $M-S_0$ such that $U_0V_0^\top$ \sa{forms a rough initial} estimate \sa{to the unknown low-rank target matrix $L^o$}. In the second phase, the algorithm alternatingly performs two operations: taking gradient steps for $U$ and $V$, and \sa{computing} a sparse estimator to adjust $S$. The sparse estimator is to guarantee that \sa{the fraction of nonzero entries in each column and row of $S$ is bounded above so that the nonzero entries are spread out in $S$}. The authors showed that the proposed two-phase algorithm \sa{recovers the target decomposition} and \sa{linear convergence is achieved} with proper initialization and step size, under the incoherence assumptions similar to \eqref{incoherence-conditions}.

For more detailed description of the assumptions and the results, see \cite{Yi-Park-Chen-Caramanis-gradient}.

In \cite{Gu-Wang-Liu-AISTATS-2016}, \sa{assuming that the data matrix $M$ is observed indirectly through compressive measurements}, Gu, Wang and Liu considered the following variant of RPCA:
\BE\label{gu-wang-liu}
\min \ H(U,V,S):=\|A(UV^\top+S)-M\|_F^2\ \ \st\ \ \|S\|_0\leq \tau_s,
\EE
where $A$ is a sensing matrix. The alternating minimization algorithm proposed in \cite{Gu-Wang-Liu-AISTATS-2016} iterates as follows:
\BEA\label{gu-wang-liu-alt-min}
\BA{ll}
U^{k+1} := \argmin_U \ H(U,V^k,S^k) \\
V^{k+1} := \argmin_V \ H(U^{k+1},V,S^k) \\
S^{k+1} := \argmin_S \ H(U^{k+1},V^{k+1},S)\ \ \st\ \ \|S\|_0\leq \tau_s.
\EA
\EEA
It is noted that the $U$ and $V$ subproblems in \eqref{gu-wang-liu-alt-min} correspond to solving linear systems and the $S$-subproblem admits an easily computable closed-form solution. The authors showed that \sa{under incoherence assumption on $L^o$ and $A$ satisfying restricted isometry property~(RIP),} \eqref{gu-wang-liu-alt-min} converges globally. However, note that $A=I$ does not satisfy the RIP condition, and therefore the convergence is not guaranteed for RPCA problem \sa{in \eqref{rpca-rank-L0}} for which $A=I$.
Similar idea was also \sa{investigated} in~\cite{sparcs-2011}, assuming the RIP condition on the sensing matrix $A$, and thus does not \sa{apply to the} RPCA problem either.

In \cite{Xu-OR-PCA-2013}, the authors considered \sa{the scenario such that the columns of the data matrix $M$ are observed} in an online fashion. This is suitable for many real applications, \sa{e.g.,
in surveillance video background separation.}

To handle this problem, the authors proposed a stochastic algorithm, which solves a nonconvex variant of RPCA:
\BE\label{OR-PCA}
\min_{U,V,S} \half\|UV^\top+S-M\|_F^2 + \frac{\rho_1}{2}(\|U\|_F^2 + \|V\|_F^2) + \rho_2\|S\|_1,
\EE
where $\rho_1$ and $\rho_2$ are \sa{some weight} parameters. \sa{The formulation in~\eqref{OR-PCA} exploits the representation of
the nuclear norm established in~\cite{recht2010guaranteed}. In particular, for any given $L\in\reals^{m\times n}$ such that $\rank(L)\leq r$, $\norm{L}_*$ can be computed as follows:
\BE\label{equiv-nuc-nonconvex}\|L\|_*:=\inf_{U\in\mR^{m\times r},V\in\mR^{n\times r}}\big\{\half\|U\|_F^2+\half\|V\|_F^2: UV^\top=L\big\}.\EE}
Form \eqref{equiv-nuc-nonconvex} we know that \eqref{rpca-nuclear-L1-noise-reform-unconstrained} is equivalent to
\BE\label{OR-PCA-constrained}
\min_{U,V,S} \frac{\mu}{2}\|UV^\top+S-M\|_F^2 + \half(\|U\|_F^2 + \|V\|_F^2) + \rho\|S\|_1.
\EE
As a result, \eqref{OR-PCA} is a nonconvex reformulation of the penalized variant of RPCA in~\eqref{rpca-nuclear-L1-noise-reform-unconstrained}. For given matrix $M=[M_1,\ldots,M_n]\in\mR^{m\times n}$, solving \eqref{OR-PCA} is the same as the following empirical risk minimization problem:
\BE\label{OR-PCA-ERM}
\min_{U} \frac{1}{n}\sum_{i=1}^n \ell(M_i,U) + \rho_1\|U\|_F^2,
\EE
where $\ell(M_i,U)$ is defined as
\BE\label{ERM-component-func}\BA{ll}\ell(M_i,U):= & \min_{V_i\in\mR^r,S_i\in\mR^m} \half\|UV_i+S_i-M_i\|_2^2 \\ & + \frac{\rho_1}{2}\|V_i\|_2^2 + \rho_2\|S_i\|_1.\EA\EE
The empirical risk minimization \eqref{OR-PCA-ERM} favors stochastic gradient descent algorithm. Of course every time to compute the gradient of $\ell(M_i,U)$, another minimization problem in \eqref{ERM-component-func} needs to be solved. Therefore, the algorithm proposed in \cite{Xu-OR-PCA-2013} is an alternating minimization method with subproblem for $U$ being solved using stochastic gradient descent. The authors showed that the proposed method converges to the correct low-dimensional subspace asymptotically under certain assumptions.

The following nonconvex variant of RPCA was proposed by Shen, Wen and Zhang in \cite{Shen-Wen-Zhang-Lmafit}:
\BE\label{Lmafit-problem}
\min_{U,V} \ \|UV^\top -M\|_1.
\EE
This simple reformulation can be viewed as a nonconvex reformulation of \eqref{rpca-nuclear-L1} but without any regularization terms on $U$ and $V$. In particular, \eqref{Lmafit-problem} can be rewritten as
\sa{
\BE\label{Lmafit-problem-rewrite}
\min \ \|S\|_1\ \ \st\ \ S + UV^\top = M.
\EE}
The authors in \cite{Shen-Wen-Zhang-Lmafit} proposed an ADMM algorithm (named LMafit) for solving \eqref{Lmafit-problem-rewrite}.
By associating a Lagrange multiplier $\Lambda$ to the constraint, the augmented Lagrangian function for \eqref{Lmafit-problem-rewrite} can be written as
\begin{align*}
\cL_\beta(U,V,S;\Lambda):= & \|S\|_1-\langle \Lambda,UV^\top + S-M \rangle \\ & +\frac{\beta}{2}\|UV^\top + S-M\|_F^2,
\end{align*}
where $\beta>0$ is a penalty parameter.
The nonconvex ADMM for solving \eqref{Lmafit-problem-rewrite} {iterates the updates} as follows:
\BEA\label{Lmafit-admm}
\BA{ll}
U^{k+1} & := \argmin_U \ \cL_\beta(U,V^k,S^k;\Lambda^k) \\
V^{k+1} & := \argmin_V \ \cL_\beta(U^{k+1},V,S^k;\Lambda^k) \\
S^{k+1} & := \argmin_S \ \cL_\beta(U^{k+1},V^{k+1},S;\Lambda^k) \\
\Lambda^{k+1} & := \Lambda^k - \beta(U^{k+1}{V^{k+1}}^\top + S^{k+1}-M).
\EA
\EEA
Note that \sa{all} three subproblems in \eqref{Lmafit-admm} are easy to solve. In particular, the $U$ and $V$-subproblems correspond to solving linear systems, and the \sa{$S$-subproblem} corresponds to the soft-shrinkage operation of the $\ell_1$ norm \eqref{vec-shrink}. However, this nonconvex ADMM lacks convergence guarantees.

In \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016}, the authors studied some variants of \sa{the conditional gradient method and ADMM for} solving nonconvex and nonsmooth optimization problems. \sa{Consider a general nonconvex optimization problem:}
\BE\label{cg-general-problem}\min_x \ f(x) + r(x)\ \ \st\ \ x\in\cX,\EE
where $f$ is smooth and possibly nonconvex, $r(x)$ is convex and nonsmooth, $\cX$ is a convex compact set. Moreover, $f$ satisfies the so-called H\"{o}lder condition:
\[f(y) \leq f(x) + \nabla f(x)^\top(y-x) + \frac{\sa{\gamma}}{2}\|y-x\|_p^p, \forall x,y\in\cX,\]
where $p>1$ and $\sa{\gamma}>0$. The definition of $\epsilon$-stationary solution given in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} is as follows.
\begin{defn}\label{def:eps-unconstrained}
$x\in\cX$ is called an $\epsilon$-stationary solution ($\epsilon\geq 0$) for \eqref{cg-general-problem} if the following holds:
\[\Psi_\cX(x):=\inf_{y\in\cX}\{\nabla f(x)^\top(y-x) + r(y)-r(x)\}\geq-\epsilon.\]
\end{defn}
The authors commented that this definition is stronger than the one used by Ghadimi \etal in \cite{glz13}.

Now we briefly discuss how to apply the algorithms analyzed in~\cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} to solve nonconvex RPCA variants.

\sa{Consider the nonconvex RPCA variant given in \eqref{OR-PCA},
the generalized conditional gradient method proposed in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} can be customized} to solve~\eqref{OR-PCA}.
\sa{Since} the generalized conditional gradient method requires a compact constraint set,
\sa{one can equivalently reformulate \eqref{OR-PCA} in the following form:}

\BE\label{nonconvex-rpca-cg-constrained}
\BA{ll}
\min_{U,V,S} & f(U,V,S) + \rho_2\|S\|_1, \\[1mm]
\st         & \sa{\max\{\|U\|_F,~\|V\|_F\}} \leq \tfrac{1}{\sqrt{\rho_1}}\|M\|_F, \\[1mm]

             & \|S\|_1 \leq \tfrac{1}{2\rho_2}\|M\|_F^2,
\EA
\EE
where $f(U,V,S):=\half\|UV^\top+S-M\|_F^2 + \frac{\rho_1}{2}(\|U\|_F^2 + \|V\|_F^2)$ denotes the smooth part of the objective function. It is easy to see that $\nabla f$ is Lipschitz continuous \sa{-- let $\gamma>0$
denote the Lipschitz constant.}

\sa{At the $k$-th iteration of the generalized conditional gradient method~\cite{Jiang-Lin-Ma-Zhang-nonconvex-2016}, implemented on \eqref{nonconvex-rpca-cg-constrained},

one needs to solve the following subproblem:}
\BE\label{nonconvex-rpca-cg-constrained-sub}
\BA{ll}
\min_{U,V,S} & \langle \nabla_U f(U^k,V^k,S^k),U \rangle + \langle \nabla_V f(U^k,V^k,S^k),V \rangle \\
             & +\langle \nabla_S f(U^k,V^k,S^k),S \rangle  + \rho_2\|S\|_1, \\[1mm]
\st          & \max\{\|U\|_F,~\|V\|_F\} \leq \tfrac{1}{\sqrt{\rho_1}}\|M\|_F, \\[1mm]

             & \|S\|_1 \leq \tfrac{1}{2\rho_2}\|M\|_F^2.
\EA
\EE
Suppose $(\bar{U}^k,\bar{V}^k,\bar{S}^k)$ denotes the solution of \eqref{nonconvex-rpca-cg-constrained-sub}, a typical iteration of the generalized conditional gradient method {is given} as follows:
\BE\label{nonconvex-rpca-cg-alg}\left\{
\BA{ll}
\mbox{Solve } & \eqref{nonconvex-rpca-cg-constrained-sub} \mbox{ to obtain } (\bar{U}^k,\bar{V}^k,\bar{S}^k) \\
\Delta U^k & := \bar{U}^k - U^k \\
\Delta V^k & := \bar{V}^k - V^k \\
\Delta S^k & := \bar{S}^k - S^k \\
\Delta^k  &:= \sa{[\Delta U^k,\Delta V^k,\Delta S^k]} \\
\alpha_k & := \argmin_{\alpha\in[0,1]} \alpha (\langle \nabla f(U^k,V^k,S^k),\Delta^k \rangle \\ & + \frac{\alpha^2\sa{\gamma}}{2}\|\Delta^k\|_F^2 + (1-\alpha)\rho_2\|[U^k,V^k,S^k]\|_1 \\ & + \alpha\rho_2\|[\bar{U}^k,\bar{V}^k,\bar{S}^k]\|_1 \\
U^{k+1} & := (1-\alpha_k) U^k + \alpha_k \bar{U}^k \\
V^{k+1} & := (1-\alpha_k) V^k + \alpha_k \bar{V}^k \\
S^{k+1} & := (1-\alpha_k) S^k + \alpha_k \bar{S}^k.
\EA\right.
\EE
Note that the generalized conditional gradient method in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} involves a line search step for computing $\alpha_k$ as shown in~\eqref{nonconvex-rpca-cg-alg}, \sa{which can be efficiently computed.}
It is shown in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} that the generalized conditional gradient method in~\eqref{nonconvex-rpca-cg-alg} \sa{can compute} an $\epsilon$-stationary solution of \eqref{nonconvex-rpca-cg-constrained} in $O(1/\epsilon^2)$ iterations.

Jiang~\etal \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} also proposed \sa{some ADMM variants that can solve various nonconvex RPCA formulations, and the authors provided a convergence rate analysis to compute an $\epsilon$-stationary solution -- the definition of $\epsilon$-stationarity employed to analyze the ADMM algorithm is given in Definition~\ref{def:eps-constrained}.} We here discuss the ADMM-g algorithm in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} which can solve the following RPCA variant:
\BE\label{nonconvex-rpca-admm}
\BA{ll}
\min & \half\|L-UV^\top\|_F^2 + \frac{\rho_1}{2}(\|U\|_F^2 + \|V\|_F^2) \\[1mm] & + \rho_2\|S\|_1 + \rho_3\|N\|_F^2 \\[1mm]
\st  & L + S + N = M.
\EA
\EE
This is a nonsmooth and nonconvex problem with five block variables $L$, $S$, $N$, $U$ and $V$, and it can be viewed as a variant of \eqref{OR-PCA} with linear constraints. Treating $N$ as the last block variable, a typical iteration of ADMM-g for solving \eqref{nonconvex-rpca-admm} {iterates} as follows:
\BE\label{ADMM-g}
\BA{ll}
L^{k+1} &:= \argmin_L \ \tilde{\cL}_{L^k}(L,U^{k},V^{k},S^{k},N^{k};\Lambda^k) \\
U^{k+1} &:= \argmin_U \ \tilde{\cL}_{U^k}(L^{k+1},U,V^{k},S^{k},N^{k};\Lambda^k) \\
V^{k+1} &:= \argmin_V \ \tilde{\cL}_{V^k}(L^{k+1},U^{k+1},V,S^{k},N^{k};\Lambda^k) \\
S^{k+1} &:= \argmin_S \ \tilde{\cL}_{S^k}(L^{k+1},U^{k+1},V^{k+1},S,N^{k};\Lambda^k) \\
N^{k+1} &:= N^k - \sa{\eta}\nabla_N\cL(L^{k+1},U^{k+1},V^{k+1},S^{k+1},N;\Lambda^k) \\
\Lambda^{k+1} &:= \Lambda^k - \beta(L^{k+1}+S^{k+1}+N^{k+1}-M),
\EA
\EE
where $\sa{\eta}>0$ is a step size, the augmented Lagrangian function $\cL$ is defined as
\begin{eqnarray*}
\lefteqn{\cL(L,U,V,S,N;\Lambda)  := }\\
& & \half\|L-UV^\top\|_F^2 + \frac{\rho_1}{2}(\|U\|_F^2 + \|V\|_F^2) + \rho_2\|S\|_1 \\
& & + \rho_3\|N\|_F^2  -\langle\Lambda,L + S + N - M \rangle \\
& & + \frac{\beta}{2}\|L + S + N - M\|_F^2,
\end{eqnarray*}
and $\tilde{\cL}$ denotes $\cL$ plus a proximal term. For example, $\tilde{\cL}_{L^k}$ is defined as
\begin{eqnarray*}
\lefteqn{\tilde{\cL}_{L^k}(L,U^{k},V^{k},S^{k},N^{k};\Lambda^k) :=}\\
& & \cL(L,U^{k},V^{k},S^{k},N^{k};\Lambda^k) + \half\|L-L^k\|_H^2,
\end{eqnarray*}
where $H$ denotes a pre-specified positive definite matrix which needs to satisfy certain conditions to guarantee the convergence of \sa{the method as stated in~\eqref{ADMM-g}.}
It is noted that the last block variable $N$ is treated specially. It is not updated by minimizing the augmented Lagrangian function, but by taking a gradient step on it.
The results in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} indicate that ADMM-g \eqref{ADMM-g} finds an $\epsilon$-stationary solution for \eqref{nonconvex-rpca-admm} in no more than $O(1/\epsilon^2)$ iterations. Since \eqref{nonconvex-rpca-admm} is a constrained problem, the definition of its $\epsilon$-stationary solution is different from the one in Definition \ref{def:eps-unconstrained}. Here we briefly discuss how it is defined for constrained problems in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016}. We consider the following constrained nonsmooth and nonconvex problem:
\BE\label{admm-general-problem}\BA{ll}
\min & f(x_1,\ldots,x_p) + \sum_{i=1}^{p-1}r_i(x_i) \\
\st  & \sum_{i=1}^{p-1} A_ix_i + x_p = b, \\
     & x_i\in\cX_i, i=1,\ldots,p-1,
\EA\EE
where $x_i\in\mR^{n_i}$, $f$ is differentiable and possibly nonconvex, each $r_i$ is possibly nonsmooth and nonconvex, and each $\cX_i$ is a convex set. Note again that the last block variable $x_p$ is treated differently, which is needed in the analysis of convergence rate. The $\epsilon$-stationary solution to \eqref{admm-general-problem} is defined as follows.
\begin{defn}\label{def:eps-constrained}
$(x_1^*,\ldots,x_p^*)\in\cX_1\times\cdots\times\cX_{p-1}\times\mR^{n_p}$ is called an $\epsilon$-stationary solution to \eqref{admm-general-problem}, if there exists $\lambda^*$ such that the following holds for any $(x_1,\ldots,x_p)\in\cX_1\times\cdots\times\cX_{p-1}\times\mR^{n_p}$:
\[\BA{r}
(x_i-{x}^*_i)^\top({g}^*_i + \nabla_i f(x_1^*,\cdots, x^*_p)  - A_i^\top {\lambda}^*) \geq -\epsilon, \\
 i=1,\ldots,p-1, \\
\| \nabla_p f(x_1^*,\ldots, x_{p-1}^*, x_p^*) - \lambda^*\| \leq  \epsilon, \\
\| \sum_{i=1}^{p-1} A_i x_i^* + x_p^* - b\| \leq \epsilon,
\EA\]
where ${g}^*_i$ is a general subgradient of $r_i$ at point $x_i^*$. This set of inequalities can be viewed as a perturbed KKT system.
\end{defn}

It is also interesting to note that \eqref{nonconvex-rpca-admm} is equivalent to the following unconstrained problem, and thus can be solved by block coordinate descent method (BCD).
\BE\label{nonconvex-rpca-bcd}
\BA{ll}
\min & \half\|M-S-N-UV^\top\|_F^2 + \frac{\rho_1}{2}(\|U\|_F^2 + \|V\|_F^2) \\ & + \rho_2\|S\|_1 + \rho_3\|N\|_F^2.
\EA
\EE
Most existing BCD type algorithms for solving nonconvex problems lack convergence rate analysis. In \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016}, the authors proposed a proximal BCD method that can find an $\epsilon$-stationary solution in $O(1/\epsilon^2)$ iterations. Denoting the objective function in \eqref{nonconvex-rpca-bcd} as $F(U,V,S,N)$, the proximal BCD given in \cite{Jiang-Lin-Ma-Zhang-nonconvex-2016} for solving \eqref{nonconvex-rpca-bcd} {updates the variables} as follows:
\BE\label{prox-bcd}\BA{l}
U^{k+1} := \argmin_U F(U,V^k,S^k,N^k)+\half\|U-U^k\|_H^2 \\
V^{k+1} := \argmin_V F(U^{k+1},V,S^k,N^k)+\half\|V-V^k\|_H^2 \\
S^{k+1} := \argmin_S F(U^{k+1},V^{k+1},S,N^k)+\half\|S-S^k\|_H^2 \\
N^{k+1} := \argmin_N F(U^{k+1},V^{k+1},S^{k+1},N)+\half\|N-N^k\|_H^2,
\EA\EE
where $H$ denotes a pre-specified positive definite matrix.


TITLE: Given $3$ children and $3$ different rooms, what's the probability that two children are placed in one room and the third is placed in another?
QUESTION [1 upvotes]: Given 3 different children and 3 different rooms, what's the probability of randomly putting 2 children in one room, 1 in the second one, and 0 in the third one, provided that each room can contain 0 to 3 children? According to my calculation, the sample space is 324; the required probability would, therefore, be 18/324. Thanks

REPLY [1 votes]: The randomly means the probabilities are equally likely.
Without loss of generality we may assume the first child $(C1)$ is in the first room $(R1)$.
The success cases:
$$P(\color{blue}{C2R1}\cap C3R2|\color{blue}{C1R1})+P(\color{blue}{C2R1}\cap C3R3|\color{blue}{C1R1})+$$
$$P(C2R2\cap \color{red}{C3R1}|\color{red}{C1R1})+P(\color{red}{C2R2}\cap \color{red}{C3R2}|C1R1)+$$
$$P(C2R3\cap \color{green}{C3R1}|\color{green}{C1R1})+P(\color{green}{C2R3}\cap \color{green}{C3R3}|C1R1)=6\cdot \frac19=\frac23.$$


TITLE: How do I prove this trigonometric integral inequality?
QUESTION [2 upvotes]: If f is integrable and monotone on [a,b] then
$\left |\int^b_a f(x)\cos x\,dx\right | \le 2(|f(a)-f(b)|+|f(b)|).$
I've tried integration by parts and using the integral inequality property but I'm not sure how to piece everything together. I figure that I need to somehow use the fact that $|\sin x|\, \le 1$ but I'm not sure how. Any help would be appreaciated. Thanks.

REPLY [1 votes]: We have
\begin{align}\left|\int_a^b f(x) \cos x\, dx \right|&= \left|\int_a^b [f(x) - f(b)]\cos x\, dx + \int_a^b f(b)\cos x\, dx\right|\\
&\le \left|\int_a^b [f(x) - f(b)]\cos x\, dx\right| + \left|\int_a^b f(b)\cos x\, dx\right|\\
&= |f(c) - f(b)|\left|\int_a^b \cos x\, dx\right| + |f(b)|\left|\int_a^b \cos x\, dx\right|\quad (\text{some $c\in (a,b)$})\\
&= (|f(c) - f(b)| + |f(b)|)\left|\int_a^b \cos x\, dx\right|\\
&= (|f(c) - f(b)| + |f(b)|)|\sin b - \sin a|\\
&\le 2(|f(a) - f(b)| + |f(b)|) \quad (\text{by montonicity of $f$}).
\end{align}


TITLE: Proof of the Cauchy–Hadamard theorem
QUESTION [0 upvotes]: I'm looking at the proof of Cauchy–Hadamard theorem.
Let $\sum_{n=1}^\infty a_nz^n$ be a power series where $a_n\in\mathbb{R}, z\in\mathbb{C}$. Let t = $\limsup|a_n|^{1/n}$, and let R = the radius of convergence of this series. Then,
(i) $t \in\left(0,\infty\right)  \Longrightarrow 1/R = t$
(ii) $t = 0 \Longrightarrow R=\infty$
(iii) $t = \infty \Longrightarrow R = 0$
I'm struggling to prove the case (iii) which says that if the sequence $\{|a_n|^{1/n}\}$ is unbounded, then the series $\sum_{n=1}^\infty a_nz^n$ converges absolutely only for $z = 0$.  Similar question have already been asked in here. But there is no proof for the case (iii). I tried to prove that if the series $\sum_{n=1}^\infty a_nz^n$ converges absolutely for some $z \neq 0$, then this leads to a contradiction. But this approach didn't work.
Thank you for your help.

REPLY [1 votes]: This follows directly from the root test for absolute convergence. If $t = \infty$ then $$\limsup_n \sqrt[n]{|a_nz^n|} = \limsup_n |z|\sqrt[n]{|a_n|} = \infty > 1$$
as long as $z\neq 0$, which implies divergence. [This trivially follows from the divergence $\sum q^n$ for $q>1$.]


TITLE: Algebraically closed ring extension
QUESTION [5 upvotes]: Suppose that $B \rightarrow A$ is an extension of rings where $A$ and $B$ are integral $k$-algebras ($\mathrm{char}\,k = 0$) finitely generated over $k$.
It is well known that if $B \rightarrow A$ is an integral extension, then the induced morphism $\mathrm{Spec}\,A \rightarrow \mathrm{Spec}\,B$ is finite and surjective.
I am interested in the opposite case. Suppose that $B \rightarrow A$ is an extension of rings which is algebraically closed. That is, if $a \in A$ and there exists a polynomial $p(t) \in B[t]$ such that $p(a) = 0$, then $a \in B$. Does this look in any way like a fibration? In particular, is it surjective and does it have connected fibres?
An example of an algebraically closed extension is $k[x] \rightarrow k[x,y]$, which is a fibration.
In this case, it is easy to show that if $B \rightarrow A$ is generically finite, then it is an isomorphism. It is equally easy to show that, if the image of $\mathrm{Spec}\,A$ in $\mathrm{Spec}\,B$ is affine, then it is surjective. To conclude, one would need a "Stein factorisation" result for affine varieties.
Any ideas or counterexamples?

REPLY [1 votes]: Let $B \to A$ be an injective map of finite type $k$-algebra domains with the property that for any $a \in A$ satisfying a polynomial relation $p(a) = 0$ for $p \in B[X]$ we have $a \in B$.
(1) the fibers of $\mathrm{Spec}(A) \to \mathrm{Spec}(B)$ need not be connected. For example,
$$ \mathrm{Spec}(k[t][x,y,z]/(xy - t, x(x - y) - 1)) \to \mathrm{Spec}(k[t])$$
This is a family of hyperbolas over $\mathbb{A}^1$ degnerating at $t = 0$ with the plane $x = y$ removed and thus the fiber over $t = 0$ is the coordinate axes minus the origin which is disconnected.
(2) the map $\mathrm{Spec}(A) \to \mathrm{Spec}(B)$ need not be surjective. Take the equation for a in $\mathbb{A}^3$ which both contain the line $x = y = 0$. For example, $f = zx + zy + xy + y$. Let $B = k[x,y]$ and $A = k[x,y,z]_{f}$. Consider,
$$ \mathrm{Spec}(k[x,y,z]_{fg}) \to \mathrm{Spec}(k[x,y]) $$
The fiber over $x = y = 0$ is empty.
In both cases, the fraction field is a purely transcendental extension giving counterexamples.