TITLE: Three linearly independent vector fields
QUESTION [2 upvotes]: How can one find three linearly independent vector fields on $S^1\times S^2$? I know that $S^1\times S^2 \cong SO_3( \mathbb{R})$, i.e. the set of orthogonal $3 \times 3$ matrices with determinant $1$, which is a Lie group and thus parallelizable. I am, however, interested in an explicit form for three vector fields.

REPLY [2 votes]: Draw a picture of $S^2 \times [0,1]$ as a thickened sphere in $\mathbb{R}^3$ where we think of the outside sphere as $S^2\times \{1\}$ and the inside as $S^2\times \{0\}$.  We will view $S^2\times S^1$ as a quotient of this space where we identify $(p,0)$ with $(p,1)$.
Now, at each point, just draw the usual $x,y,z$ arrows.  This defines a nonvanishing smooth vector field on $S^2\times [0,1]$.  The identification made on the boundary maps the usual $x,y,z$ arrows to the usual $x,y,z$ arrows, so this descends to a non-vanishing vector field on $S^2\times S^1$.


TITLE: Norm of an ideal
QUESTION [8 upvotes]: Would someone attempt to give me a simple explanation of how to compute the norm of an ideal. I like the definition |$O/a$| but find it difficult to apply. Perhaps the "determinant version" lends itself better to application. In any event, I need some hints for a problem which asks for all ideals of $\mathbb Z[\sqrt{(-5)}]$ which contain the element $6$. The previous post with a similar title really doesn't address this issue clearly.

REPLY [3 votes]: Hint $\ $ This is easy if you write the ideal as a module in "normal" form,  e.g. see section 2.3 in the nice exposition by Franz Lemmermeyer.
These normal forms generalize to higher degree number fields, e.g. see the discussion on Hermite and Smith normal forms in Henri Cohen's A Course in Computational Number Theory.


TITLE: Mixed States, Gibbs States, and Temperature
QUESTION [1 upvotes]: I am trying to help myself clarify some concepts. The purpose of this post is twofold: 1) to get some comments/feedback, and 2) to help me organize my thoughts. I have been approaching these concepts from a more mathematical point of view, but quickly realize that this seems to be not enough.
Assumption: I am considering a closed system.
Here are the definitions that I am using:
Mixed states by definition are operators of the form
\begin{align}
\rho = \sum_{n} p_n|\psi_n\rangle\langle\psi_n|
\end{align}
where $p_n\ge 0$ and $\sum_n p_n = 1$. For convenience, I assume the sequence $\{\psi_n\}$ is an orthonormal family of vectors in some Hilbert space $\mathcal{H}$ (infinite dimensional, say $\mathcal{H}= L^2(\mathbb{R}^n)$). Note that this definition also contains pure states.
A Gibbs State by definition is a mixed state of the form
\begin{align}
\rho_G = \frac{e^{-\beta H}}{Z}= Z^{-1}\sum_n e^{-\beta E_n}|E_n\rangle\langle E_n|
\end{align}
where $H=\sum_n E_n |E_n\rangle\langle E_n|$ and $\{|E_n\rangle\}$ (clearly an abuse of notation) is the family of eigenfunctions of $H$. Let us assume $\beta\ge 0$ and $Z:=\operatorname{Tr}(e^{-\beta H})<\infty$.
Lastly, we define the temperature of $\rho_G$ by $T:= 1/(k\beta)$ where $k$ is some constant (for simplicity, let us take $k=1$). Note that this means that temperature is dependent on the Hamiltonian.
Observations:
It is clear to me that the set of mixed states is clearly larger than the set of Gibbs states. The claim comes from the observation that $\rho = \frac{1}{2}\left(|\psi_1\rangle\langle \psi_1|+|\psi_2\rangle\langle \psi_2|\right)$ cannot be written as a Gibbs state since the spectrum of
\begin{align}
 H= -\Delta+V \ \ \ (1)
\end{align}
is usually countably infinite at the very least (am I wrong?) This means that infinitely many $p_n$ are zero so that $e^{-\beta E_n} = 0$ implies $E_n=0$ or $T = \infty$. However, no one is demanding me to assume $H=-\Delta+V$. In fact, in theory, we could consider $H= E_1|\psi_1\rangle\langle\psi_1|+ E_2|\psi_2\rangle\langle\psi_2|$ (a 2-level system). Then, we have the Gibbs states
\begin{align}
\rho_G(\beta) = Z^{-1}(e^{-\beta E_1}|\psi_1\rangle\langle\psi_1|+e^{-\beta E_2}|\psi_2\rangle\langle\psi_2|).
\end{align}
Questions:

Given a mixed state, can we view it as a Gibbs state of some Hamiltonian? (From a physics perspective, this question doesn't make too much sense.)
Given a mixed state, can we associate a temperature to it intrinsically? (From my first question, it is clear that you can't since, there, the temperature depends on the Hamiltonian.)

In these questions, I have completely ignored the physics and just view the objects mathematically (computationally).

REPLY [1 votes]: Gibbs states are defined by the KMS condition not by the alegbraic expression. In a Hilbert space $ \mathcal{H}_d$ of dimension $d < \infty$, any state $\rho$ with rank $k\leq d$ can be interpreted as a Gibbs state with an arbitrary temperature $\beta$ and Hamiltonian $H$ like, $$ \rho  = \frac{e^{-\beta H}}{ Z_\beta^H}$$
For states with less than full rank, one must define the Hamiltonian $H$ (and the corresponding dynamical flow) appropriately on a subspace. So, the set of all mixed states is identical to the set of Gibbs states.
The answer to your second question (2.) is a bit more delicate, the state $\rho$ does not describe the system but a only a preparation procedure of the thermal ensemble. Therefore, one cannot define a temperature of the system by specifying just a density matrix $\rho$.
Also, please note that the $\beta$ occuring in the expression is the temperature of the canonical bath and is not a feature of the system.
However, given a Hamiltonian of the system, one may infer the temperature by performing projective measurements in the energy eigenbasis. Alternatively, one may also perform tomography on a dynamical sequence of states to infer the temperature using the microcanonical expression, $$ \frac{\partial S}{\partial E} = \beta,$$
where $S$ is the von Neumann entropy and $E$ is the internal energy of the ensemble defined by $$E = \mbox{Tr}[\rho H]$$


TITLE: Why absolute value changes function in limit?
QUESTION [1 upvotes]: If $f(x) = |x-1|$ then test the continuity and differentiability of the function $f(x)$ at the point $x=1$.

$$Rf'(1)=\lim_{h->0_+} \frac{f(1+h)-f(1)}{h}$$
$$=\lim_{h->0_+} \frac{|1+h-1|-0}{h}$$
$$=1$$
$$Lf'(1)= \lim_{h->0_-} \frac{f(1+h)-f(1)}{h}$$
$$=\lim_{h->0_-} \frac{-h-0}{h}$$
$$=-1$$
What is happening to second line? Both limit had used same function although why both of them are writing different "thing"? I am so confused with it.

REPLY [0 votes]: The absolute value in $f$ means that $f$ is defined differently for the two pieces of the domain:
$$f(x) = \vert x -1 \vert  =
\begin{cases}
       x-1, &\quad\text{if }x-1\geq 0\\
       -(x-1), &\quad\text{if }x-1<0\\
\end{cases} \quad = \quad
\begin{cases}
       x-1, &\quad\text{if }x\geq 1\\
       1-x, &\quad\text{if }x<1\\
\end{cases}.$$
Then:
$$\lim_{h\to 1 ^-} \dfrac{f(x+h)-f(x)}{h} = \dfrac{(1-(x+h))-(1-x)}{h} = \dfrac{-h}{h} = -1,$$
$$\lim_{h\to 1 ^+} \dfrac{f(x+h)-f(x)}{h} = \dfrac{(x+h-1)-(x-1)}{h} = \dfrac{h}{h} = 1.$$
(Notice the limits have to be around the point $x=1$, not $x=0$).
It is the same function, but it is defined differently at the left ($x<1$) and the right ($x\geq 1$).
Since the limits do not coincide, $f$ is not differentiable at the point $x=1$.


TITLE: Understanding the logic of expectation $\ge$ the game value
QUESTION [0 upvotes]: I was reading the solution of a $2\times 2$ games with mixed strategies. My book gives answer like this:
The pay-off matrix is \begin{matrix}
&   &C_1 &C_2\\
&R_1 &a_{11} &a_{12}\\
&R_2 &a_{21} &a_{22}
\end{matrix}
with the probability vector $\bar p=(p_1,p_2), \bar q=(q_1,q_2)$ for $R$ and $C$ respt.
When $C$ chooses his move $C_1$, the expected gain of $R$ is $E_1(\bar p)=a_{11}p_1+a_{21}p_2=a_{11}p_1+a_{21}(1-p_1)$
and when $C$ chooses his move $C_2$, the expected gain of $R$ is $E_2(\bar p)=a_{12}p_1+a_{22}p_2=a_{11}p_1+a_{21}(1-p_1)$
Similarly $E_1(\bar q)=a_{11}q_1+a_{12}q_2=a_{11}q_1+a_{12}(1-q_1)$ and $E_2(\bar q)=a_{21}q_1+a_{22}q_2=a_{21}q_1+a_{22}(1-q_1)$
If $v$ be the values of the game, then clearly
$E_1(\bar p)\ge v, E_2(\bar p)\ge v$ and $E_1(\bar q)\le v, E_2(\bar q)\le v$.
This is not clear to me. How do these inequalities hold for $\bar p$ and $\bar q$?

REPLY [0 votes]: Game has value, if lower value equals upper value.
Recall that lower value is
$$
\underline v = \max_{\bar p} \min_{\bar q}r(\bar p, \bar q)
$$
where $r$ stands for revenue function (a convex combination of $a_{ij}$ with coefficient obtained from $\bar p$ and $\bar q$) - your expected income.
Fix strategy for first player $\bar p^*$. We have
$$
\underline v \geq \min_{\bar q}r(\bar p^*, \bar q)
$$
directly from definition. Two of those strategies are deterministic ones: $\bar p^* = (1, 0)$ which correspond to $E_1(\bar q)\leq v$ and $\bar p^* = (0, 1)$ corresponding to $E_2(\bar q) \leq v$.
Similar reasoning can be done with upper value to obtain remaining inequalities.


TITLE: How to efficiently determine a metric manifold's skeleton (and what's it actually called)?
QUESTION [0 upvotes]: For a $n$-dimensional manifold $M$ (that has a metric) with boundary $\partial M$, I refer to the submanifold $S$ with the following property as the "skeleton" of $M$:
$$x\in S \Longleftrightarrow x\in M \wedge \exists R>0\forall r<R:B^n(x,r)\cap\partial M=\varnothing\ \wedge \#(B^n(x,R)\cap\partial M)>1$$
i.e. $S$ consists of all points inside $M$ for which there is no unique closest neighbour on the boundary $\partial M$. To name a few examples, for a square the skeleton consists of the diagonals, for a sphere it is the centre, for an infinite cylinder$\dagger$ it's the symmetry line, for a torus a circle etc. So here are my questions:

What is the actual name of this submanifold? (I'm also tempted to call it "Origami-core" since it relates to the manifold's symmetries)
Is this definition sound for general manifolds that have a metric or did I generalize too much from $\mathbb R^n$? Does the shape of $S$ actually depend on the metric used?
Is the reconstruction of $M$ as $\cup_{x\in S}\cup_{r=0}^{R(x)} B^n(x,R(x))$ correct? (Assuming inner hole boundaries are considered part of $\partial M$)
How can $S$ be determined more efficiently than by expanding spheres around each boundary point and checking whether any point of these surfaces has another nearest neighbour?
Is there maybe a non-constructive formula to determine the dimension of $S$? As the example of a hypersphere shows, $S$ can still be one dimensional for arbitrary large $n$ while I'm pretty sure in the general case it may remain irreducibly $n-1$ dimensional - or could $S$ even be $n$ dimensional as well?

$\dagger$ If you take the (intuitive?) limit

REPLY [1 votes]: At least for regions in $\mathbb R^n$, this is known as the medial axis or the topological skeleton.


TITLE: How would we measure the non-randomness and compactness of this cubic lattice and corresponding graph?
QUESTION [1 upvotes]: The genetic code is decrypted into a 4x4x4 cubic lattice shown here:
https://www.researchgate.net/publication/361073909_Decryption_and_Topology_of_the_Genetic_Code

That cube was used to construct an un-direction graph with 21 nodes and 148 edges in Mathematica - displayed below:

REPLY [0 votes]: Designated Cube 1, the order: g, a, c, u yields a structure with the most closed-loops. The mirror of this cube (u, c, a, g) is a second solution.
(21) (PDF) Graph Analysis of the Genetic Code Using Closed-Loops Shows Isotropic Axes Using the Order GACU Yields Maximum Topological Compactness. Available from: https://www.researchgate.net/publication/361250677_Graph_Analysis_of_the_Genetic_Code_Using_Closed-Loops_Shows_Isotropic_Axes_Using_the_Order_GACU_Yields_Maximum_Topological_Compactness [accessed Jun 14 2022].
Computational proof, but someone should try group theory:


TITLE: An example of Serre on the cohomology of some CM elliptic curves
QUESTION [2 upvotes]: Let $E$ be the elliptic curve over $\mathbf{Q}_3$ with Weierstrass equation $y^2 = x^3-x$.
It has complex multiplication by $\mathbf{Z}[\sqrt{-1}]$, with  $\sqrt{-1}$ acting as $(x,y)\mapsto(-x,iy)$.
Call $R:=\mathbf{Z}_3[\sqrt{-1}] = W(\mathbf{F}_9)$.
Let $\mathcal{E}$ be the Néron model over $\mathbf{Z}_3$, an abelian scheme (e.g. by Néron-Ogg-Shafarevich). Then the endomorphism $[-3] : \mathcal{E}\otimes_{\mathbf{Z}_3}R\to\mathcal{E}\otimes_{\mathbf{Z}_3}R$ is a lift of the $9$-power map on $\mathcal{E}_{\mathbf{F}_9}\to \mathcal{E}_{\mathbf{F}_9}$.
In the example by Serre discussed in the answer to this question, a conjectural $\mathbf{Q}$-linear cohomology theory is discussed for varieties over $p$-adic fields, and it is argued that such theory cannot exist in light of the fact that a Frobenius action $F$ on $H^1(E_{\overline{\mathbf{Q}}_3})$ would satisfy $F^2 = -3=[-3]^*$, $F[\sqrt{-1}]^*=-[\sqrt{-1}]^*F$, and of course $([\sqrt{-1}]^*)^2=-1$, and these equations cannot be solved in $2\times 2$ matrices over $\mathbf{R}$ (at least, this is how I understood the question and answer).
My question only asks for a clarification on the linked question and answer.

question
It seems to me the linked question asks for a cohomology theory for varieties over $p$-adic fields. How does $F$ on $H^1$ arise, then?

I would expect such theory to be functorial only with respect to morphisms of varieties over $p$-adic fields (as it seems to be required in the linked question), and so $H^1(E_{\overline{\mathbf{Q}}_3})$ would not necessarily carry the effect of endomorphisms of $\mathcal{E}_{\overline{\mathbf{F}}_3}$, except those that are liftable.
The $3$-rd power map on $\mathcal{E}_{\mathbf{F}_3}$ is not liftable, I believe. Otherwise I'd expect the example to apply to the rational Betti cohomology of $E(\mathbf{C})$ for any $\sigma :\overline{\mathbf{Q}}_3\simeq\mathbf{C}$.
expectation I expect the linked question asks for a theory that is assumed to carry some such $F$ (probably in the last sentence of the linked question - "taking value in Weil-Deligne representations over $\mathbf{Q}$"), and Serre's example shows $F$ cannot exist on any such $\mathbf{Q}$-linear theory. I'd just like to double-check this understanding is correct, to be sure. I'll leave the question here for other's benefit.

REPLY [2 votes]: Yes. There exists a "nice" cohomology theory for $p$-adic varieties, taking values in vector spaces over $\mathbb Q$, defined by fixing an embedding $\mathbb Q_p \to \mathbb C$, base-changing along this embedding, and taking singular cohomology. Every morphism of varieties over $\mathbb Q_p$ induces a map on cohomology groups in this theory (by the usual property of singular cohomology). So no argument of this type can rule out such a theory.
It is a cohomology theory valued in $\mathbb Q$-rational Weil-Deligne representations, which by assumption admit an action of Frobenius, that this argument rules out.


text:
\begin{document}

\title{The layer number of $\alpha$-evenly distributed point sets}
\author{
	Ilkyoo Choi\thanks{
Supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2018R1D1A1B07043049), and also by the Hankuk University of Foreign Studies Research Fund.
Department of Mathematics, Hankuk University of Foreign Studies, Yongin-si, Gyeonggi-do, Republic of Korea.
\texttt{ilkyoo@hufs.ac.kr}
	}
	\and
	Weonyoung Joo\thanks{
		Department of Industrial and Systems Engineeing, KAIST, Daejeon, Republic of Korea.
		\texttt{es345@kaist.ac.kr}
	}
	\and
	Minki Kim\thanks{
		Partially supported by ISF grant no. 2023464 and BSF grant no. 2006099.
		Department of Mathematics, Technion -- Israel Institute of Technology, Haifa, Israel.
		\texttt{kimminki@technion.ac.il}
	}
}
\date\today
\maketitle

\begin{abstract}
	For a finite point set in $\mathbb{R}^d$, we consider a peeling process where the vertices of the convex hull are removed at each step.
	The layer number $L(X)$ of a given point set $X$ is defined as the number of steps of the peeling process in order to delete all points in $X$.
	It is known that if $X$ is a set of random points in $\mathbb{R}^d$, then the expectation of $L(X)$ is $\Theta(|X|^{2/(d+1)})$, and recently it was shown that if $X$ is a point set of the square grid on the plane, then $L(X)=\Theta(|X|^{2/3})$.

	In this paper, we investigate the layer number of $\alpha$-evenly distributed point sets for $\alpha>1$; these point sets share the regularity aspect of random point sets but in a more general setting.
The set of lattice points is also an $\alpha$-evenly distributed point set for some $\alpha>1$.
We find an upper bound of $O(|X|^{3/4})$ for the layer number of an $\alpha$-evenly distributed point set $X$ in a unit disk on the plane for some $\alpha>1$, and provide an explicit construction that shows the growth rate of this upper bound cannot be improved.
	In addition, we give an upper bound of $O(|X|^{\frac{d+1}{2d}})$ for the layer number of an $\alpha$-evenly distributed point set $X$ in a unit ball in $\mathbb{R}^d$ for some $\alpha>1$ and $d\geq 3$.
\end{abstract}

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

Let $\Vol(R)$ be the volume function of a region $R$ in $\mathbb{R}^d$.
	For a finite point set $X$ in $\mathbb{R}^d$, let $\conv(X)$ denote the convex hull of $X$ and let $V(X)$ denote the \df{convex layer} of $X$, which is the set of extreme points of $X$.
	We consider a ``peeling process'' of $X$ that removes the convex layer at each step.
Given a point set $X$, the \df{peeling sequence} $\{X_i\}_i$ of $X$ is the sequence of subsets of $X$ such that $X_i$ is the set of remaining vertices at step $i-1$;
	in other words, $X_1 =X$ and  $X_{i+1} = X_i\setminus V(X_i)$ for $i\geq1$.
See Figure~\ref{fig:peeling} for an illustration.

\begin{figure}[h]
    \centerline{\includegraphics[scale=0.9]{peeling.pdf}}
    \caption{One step of the peeling process of $X$.}
    \label{fig:peeling}
\end{figure}

	The \df{layer number} $L(X)$ of $X$ is the number of steps the peeling process takes to remove all points from $X$; namely, $L(X):=\min\{k:X_{k+1}=\emptyset\}$.
	An optimal deterministic algorithm to find $L(X)$ with running time $O(|X| \log (|X|))$ was discovered in~\cite{Cha85}.

Note that $L(X)=1$ if and only if $X$ is a point set in convex position.
It is not hard to see that $1\leq L(X)\leq \lceil|X|/2\rceil$.
The upper bound is sharp, as it comes from points on a single straight line.
See the illustration in Figure~\ref{fig:ex}.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}
\tikzstyle{c}=[circle, draw, solid, fill=black, inner sep=0pt, minimum width=3pt]
\tikzstyle{d}=[diamond, draw, solid, fill=white, inner sep=2pt, minimum width=2pt]
\begin{scope}[thick, every node/.style={sloped,allow upside down}]
	\node[c] at (-3,0){};
	\node[c] at (-2,0){};
	\node[c] at (-1,0){};
	\node[c] at (0,0){};
	\node[c] at (1,0){};
	\node[c] at (2,0){};
	\node[c] at (3,0){};
	\draw[dotted] (-4,0)--(4,0);

	\node at (0,1){}; \node at (0,-1){};
\end{scope}
\end{tikzpicture}
\caption{An example of a point set $X$ where $L(X)=\lceil|X|/2\rceil$.}
\label{fig:ex}
\end{figure}

	Finding an asymptotic bound on the layer number of a class of point sets is an intriguing research problem; in particular, discovering a class of point sets where every point set $X$ in the class satisfies $L(X)\leq o(|X|)$ or even $L(X)\leq O(|X|^{1-\epsilon})$ for some $\epsilon>0$ is noteworthy.

	\begin{prob}\label{problem}
		Let $\mathcal{C}$ be a class of point sets in $\mathbb{R}^d$.
		Find the maximum value of $\epsilon>0$ such that $L(X)\leq O(|X|^{1-\epsilon})$ for every finite point set $X\in\mathcal{C}$.
	\end{prob}
	Recently, Problem~\ref{problem} was solved for random point sets~\cite{Dal04} and the square grid~\cite{HPL13}.

	In \cite{Dal04}, it was shown that for a bounded region $R$ with non-empty interior in $\mathbb{R}^2$, the expected layer number for an $n$-vertex point set $X$ distributed independently and uniformly in $R$ is $\Theta(n^{2/3})$.
Furthermore, the author of \cite{Dal04} proved the bound is $\Theta(n^{2/(d+1)})$ when $X$ is a set of points in $\mathbb{R}^d$.
	The main result in \cite{HPL13} is that the layer number is $\Theta(n^{2/3})$ for a set of points on the $\cceil{ \sqrt{n} } \times \cceil{ \sqrt{n} }$ square grid.
	It would be remarkable to find the layer number of the $\cceil{ n^{1/d} } \times \cdots \times \cceil{ n^{1/d} }$ $d$-dimensional square grid for each $d\geq 3$; this future direction was also mentioned in~\cite{HPL13}.

	Regarding the results in \cite{Dal04} and \cite{HPL13}, it is interesting that the bounds coincide to $\Theta(n^{2/3})$ for the case of an $n$-vertex point set on the plane.
	However, it may not be surprising because the bounds for the number of points in convex position are the same.
	Note that the layer number $L(X)$ of a point set $X$ is bounded below by $|X|$ divided by the maximum number of points in convex position.
	In \cite{Bar89}, it was shown that for an $n$-vertex point set $X$ distributed independently and uniformly in a convex body, the expected value  of $|V(X)|$ is $O(n^{(d-1)/(d+1)})$.
	This result is the core of the proof of the lower bound of $\Omega(n^{2/(d+1)})$ in \cite{Dal04}.
	The expected number of $|V(X)|$ is also $O(n^{(d-1)/(d+1)})$ for grids, as shown in~\cite{Sch88}.
	See \cite{And63, BB91, BL98, Bar08} for an overview and more information on the number of points of the convex layer of sets of lattice points.
Also see \cite{RS63, Sch88, Bar08} for similar results regarding random point sets.

\subsection{Evenly distributed point sets}\label{sec:even}

	Besides sets of random points or sets of lattice points, it is worth considering the layer number of ``evenly distributed'' point sets, that is, point sets that are almost uniformly distributed in a given region.
In particular, an evenly distributed point set is ``locally'' not too dense.

\begin{definition}
	Let $X$ be a finite point set in a unit ball in $\mathbb{R}^d$.
	For a constant $\alpha > 1$, we say $X$ is \df{$\alpha$-evenly distributed} if
	\[ |X\cap D|  \leq  \Big\lceil \alpha|X|\Vol(D) \Big\rceil \]
	holds for every Euclidean ball $D$ with positive volume.
\end{definition}

The above definition, roughly speaking, says that when the volume of $D$ is large, then the number of points of $X$ in $D$ is proportional to the volume of $D$, and when the volume of $D$ is small, then the number of points of $X$ in $D$ is bounded above by a constant.

	In this paper, we investigate Problem~\ref{problem} for $\alpha$-evenly distributed point sets in $\mathbb{R}^d$.
We succeed in determining the maximum value of $\epsilon$ in Problem~\ref{problem} when $d=2$.
It was surprising to discover that the behavior of an evenly distributed point set is quite different from that of the square grid.
We also obtain results for higher dimensions, but unfortunately we could not prove that the growth rate is tight.

	Given a positive integer $d$ and a positive real number $\alpha$, let $\mathcal{C}_d(\alpha)$ be the class of all $\alpha$-evenly distributed point sets in a unit ball in $\mathbb{R}^d$.
	Our main results are the following:
	\begin{theorem}\label{thm1.2}
	For every real number $\alpha > 1$,
	if $X$ is a point set in the class $\mathcal{C}_2(\alpha)$, then $L(X) \leq O(|X|^{3/4})$, and
	the growth rate cannot be improved.
	\end{theorem}

	\begin{theorem}\label{thm1.3}
	For every real number $\alpha > 1$ and every integer $d \geq 3$,
	if $X$ is a point set in the class $\mathcal{C}_d(\alpha)$, then $L(X) \leq O(|X|^{\frac{d+1}{2d}})$.
	\end{theorem}

	In Section~\ref{sec:2dup}, we prove Theorem~\ref{thm1.2} by further developing ideas from \cite{Dal04}.
	In Section~\ref{sec:2dlow}, we give an explicit construction showing that the bound of $O(|X|^{3/4})$ cannot be improved, and hence confirm that $\epsilon=\frac{1}{4}$ is the answer of Problem~\ref{problem} for evenly distributed point sets on the plane.
	In Section~\ref{sec:higher}, we prove an analogue of Theorem~\ref{thm1.2} to higher dimensions, which gives a partial solution of $\epsilon\geq\frac{d-1}{2d}$ to Problem~\ref{problem} for evenly distributed point sets in $\mathbb{R}^d$ where $d\geq 3$.
	We finish the paper with remarks, discussion on future research directions, and open problems in Section~\ref{sec:rmk}.

	\smallskip

\section{Preliminaries}\label{sec:prelim}
We prove some lemmas that will be used in the proofs of the main theorems.
The statement of the following lemma also appeared in \cite{Dal04}; we include a proof here for completeness.

\begin{lemma}\label{lem2.1}
	Assume $X$ is a finite point set in $\mathbb{R}^d$.
	\begin{enumerate}[$(a)$]
		\item If $Y\subseteq X$, then $Y\setminus V(Y)\subseteq X\setminus V(X)$.
		\item If $Y\subseteq X$, then $L(Y)\leq L(X)$.
	\end{enumerate}
\end{lemma}
\begin{proof}
$(a)$
If no point of $Y$ is in $V(X)$, then $Y\setminus V(Y)\subseteq Y\subseteq X\setminus V(X)$.
Thus, we may assume that $V(X)\cap Y\neq\emptyset$, and let $v\in V(X)\cap Y$.
Since $v\in V(X)$, there is a hyperplane $H$ such that $H\cap X=\{v\}$ and $H$ divides $\mathbb{R}^d$ into two closed halfspaces $H^+$ and $H^-$ where $H^+\cap X=\{v\}$ and $H^-\cap X=X$.
See Figure~\ref{fig:lem21} for an illustration.
Since $Y\subseteq X$ and $v\in Y$, it follows that $H^+\cap Y=\{v\}$ and $H^-\cap Y=Y$.
Hence, $v$ is also in $ V(Y)$.
		This shows that $Y\cap V(X)\subseteq V(Y)$.
		Therefore, $Y\setminus V(Y)\subseteq Y\setminus (Y\cap V(X))=Y\setminus V(X) \subseteq X\setminus V(X)$.

\begin{figure}[h]
    \centerline{\includegraphics[scale=0.8]{lem21.pdf}}
    \caption{For Lemma~\ref{lem2.1}~$(a)$. Dots represent points in $X$, and diamonds represent points in $Y$. Note that $Y\subseteq X$.} \label{fig:lem21}
\end{figure}

		$(b)$
Let $\{X_i\}_i$ and $\{Y_i\}_i$ be the peeling sequence of $X$ and $Y$, respectively.
		We will show that $Y_k\subseteq X_k$ for every $k\geq1$ by induction on $k$.
		For $k=1$, it is true since $Y\subseteq X$.
		Assume $k\geq2$ and $Y_{k-1}\subseteq X_{k-1}$ holds.
		By $(a)$, we know $Y_{k-1}\setminus V(Y_{k-1})\subseteq X_{k-1}\setminus V(X_{k-1})$, which is equivalent to $Y_{k}\subseteq X_{k}$.
Hence, when $k=L(X)+1$, it follows that $Y_{L(X)+1}\subseteq X_{L(X)+1}=\emptyset$, which means $L(Y)\leq L(X)$.
	\end{proof}

	Let $K_1$ and $K_2$ be two convex bodies in $\mathbb{R}^d$ such that $K_2 \subset \intr(K_1)$.
	For each point $p$ on the boundary of $K_2$, let $H_p$ be a tangent hyperplane of $K_2$ at the point $p$.
	Note that $H_p$ divides $\mathbb{R}^d$ into two closed halfspaces, say $H^+_p$ and $H^-_p$ such that $\intr(H^+_p) \cap K_2 = \emptyset$.
	The closed region $K_1 \cap H^+_p$ is a called a \df{cap} of $K_1\setminus K_2$.
	See Figure~\ref{fig:cap} for an illustration.
	Note that each cap has a corresponding hyperplane and a corresponding point on the boundary of $K_2$.
	The following lemma shows how the number of points in a cap is related to the layer number of the given point set in $\mathbb{R}^d$.

\begin{figure}[h]
    \centerline{\includegraphics[scale=1]{capp}}
    \caption{A cap $C$ of $K_1 \setminus K_2$ } \label{fig:cap}
\end{figure}

\begin{lemma}\label{lem2.3}
	If $K_1$ and $K_2$ are two convex bodies in $\mathbb{R}^d$ such that $K_2\subseteq \intr(K_1)$ and $X$ is a finite point set in $K_1$, then
	$L(X) \leq \max\{|X\cap C|: C\text{ is a cap of }K_1\setminus K_2\} +L(X\cap K_2)$.
\end{lemma}

\begin{proof}
Let $C$ be a cap of $K_1\setminus K_2$ and let $H$ be the corresponding hyperplane of $C$.
	Recall that $H$ divides $\mathbb{R}^d$ into two closed halfspaces $H^+$ and $H^-$ where $C=K_1\cap H^+$.

Let $\{X_i\}_i$ be the peeling sequence of $X$.
We claim that for $k\geq 1$, either $V(X_k)\cap C$ is non-empty or $X_k\cap C$ is empty.
	Suppose $X_k\cap C$ is non-empty.
	Note that $X_k\cap C = X_k\cap H^+$ since $X\subset K_1$.
	Now, it must be that $\conv(X_k)$ contains some point $p$ in $H^+$ such that $p\in V(X_k)$.
	Since $p$ must also be in $C$, it follows that $V(X_k)\cap C$ is non-empty.

	Now, at every peeling step, at least one point is removed from each non-empty cap.
	Let $C_0$ be a cap of $K_1 \setminus K_2$ that contains the maximum number of points of $X$.
	By repetitively applying Lemma~\ref{lem2.1} $(b)$, we conclude that $L(X) \leq |X\cap C_0|+L(X_{|X\cap C_0|+1}\cap K_2)\leq |X\cap C_0|+L(X\cap K_2)$.
\end{proof}

	Recall that a finite point set $X$ in a unit ball in $\mathbb{R}^d$  is $\alpha$-evenly distributed if there is a constant $\alpha > 1$ such that
	\[ |X\cap D|  \leq  \lceil \alpha|X|\Vol(D) \rceil \]
	holds for every Euclidean ball $D$ with positive volume.
	Let $\delta(X)$ be the minimum distance between two different points in $X$; namely, $\delta(X) = \min \{ \|x-y\| : x,y\in X\text{ and } x \neq y\}$.
	The following lemma gives a sufficient condition on $\delta(X)$ in order for $X$ to be an $\alpha$-evenly distributed point set for some $\alpha>1$.

	\begin{lemma}\label{lem2.4}
	For a positive integer $d$, there exists a continuous bijection $f_d:\mathbb{R}_{>0}\to\mathbb{R}_{>1}$ such that
	if $X$ is a finite point set in a unit ball in $\mathbb{R}^d$ satisfying  $\delta(X) \geq \beta{|X|^{-1/d}}$ for some constant $\beta>0$,
	then $X$ is $f_d(\beta)$-evenly distributed.
\end{lemma}

\begin{proof}
	Let $n=|X|$ and let $\beta>0$ be a constant such that $\delta(X)\geq \beta{n^{-1/d}}$.
	Also, let $B$ be a ball of radius $r>0$ in $\mathbb{R}^d$.
	Note that the $\Vol(B)=C_d r^d$ for some positive constant $C_d$.
	A $d$-dimensional cube with side length $\frac{\delta(X)}{2\sqrt{d}}$ contains at most one point of $X$ since it fits in a ball of diameter less than $\delta(X)$.
	Since $B$ fits in a $d$-dimensional cube with side length $2r$,
	we have the following upper bound on $|X\cap B|$:
	\[|X\cap B|\leq \left(\left\lfloor{\frac{2r}{\delta(X)/\sqrt{4d}}}\right\rfloor + 1\right)^d\leq \left\lceil\left(\frac{4\sqrt{d}r}{\beta} n^{1/d}+1\right)^d\right\rceil.\]
	Let $f_d(\beta) = \left(\frac{4\sqrt{d}}{C_d^{1/d}\beta } + 1\right)^d$ so $f_d$ is a continuous bijection from $\mathbb{R}_{>0}$ to $\mathbb{R}_{>1}$.
	We see that $X$ is $f_d(\beta)$-evenly distributed by definition.
\end{proof}

\section{The layer number of an evenly distributed point set on the plane}\label{sec:planar}

\subsection{The upper bound on the plane}\label{sec:2dup}
	In this section, we give an upper bound of $O(|X|^{3/4})$ on the layer number of a point set $X$ in the class $\mathcal{C}_2(\alpha)$, that is, an $\alpha$-evenly distributed point set in a unit disk in $\mathbb{R}^2$.
	This shows the first part of Theorem~\ref{thm1.2}.

\begin{prop}\label{prop:2dup}
For a real number $\alpha > 1$,
	if $X$ is a point set in the class $\mathcal{C}_2(\alpha)$, then $L(X) \leq O(|X|^{3/4})$.
\end{prop}
\begin{proof}
	Let $X \in \mathcal{C}_2(\alpha)$ with sufficiently many points where $n = |X|$ and let $N = \lfloor \sqrt{n} \rfloor$.
	For each $j\in\{0, \ldots, N\}$, let $D_j$ be the disk in $\mathbb{R}^2$ with radius $1-\frac{j}{\sqrt{n}}$ centered at the origin;
	note that $D_0$ is the unit disk  centered at the origin.
	For each $j\in\{0, \ldots, N-1\}$, let $C_j$ be a cap of $D_j\setminus D_{j+1}$ that contains the maximum number of points of $X$ among all caps of $D_j\setminus D_{j+1}$.
See Figure~\ref{fig:thm311}.

\begin{figure}[h]
    \centerline{\includegraphics[scale=0.8]{thm311.pdf}}
    \caption{Take a cap $C_j$ of $D_j \setminus D_{j+1}$ that contains the maximum number of points of $X$.}
\label{fig:thm311}
\end{figure}

	Since $X$ is $\alpha$-evenly distributed in $D_0$, we have upper bounds
	\[|X \cap B_0| \leq \lceil\alpha\pi\rceil \;\;\;\text{and}\;\;\; |X \cap B_1| \leq \left\lceil\frac{\alpha\pi}{2}\right\rceil,\]
	where $B_0$ and $B_1$ is a disk of radius ${{n^{-1/2}}}$ and $\frac{1}{\sqrt{2}}n^{-1/2}$, respectively.
	We prove the following two lemmas, which provide upper bounds on $|X\cap C_j|$ and
	$|X\cap D_{N}|$.

	\begin{lemma}\label{lem3.1}
	For $j\in\{0, \ldots, N-1\}$, we know $|X\cap C_j|\leq O(n^{1/4}) + O(1)$.
	\end{lemma}

	\begin{proof}
	For each $j\in\left\{0, \ldots, N-1\right\}$, the area of $C_j$ is upper bounded by the area of the smallest rectangle $R_j$ containing $C_j$.
	The length of one side of $R_j$ is $n^{-1/2}$ and the length of the other side of $R_j$ is bounded above by $2\sqrt{2}n^{-1/4}$ since $2\sqrt{2n^{-1/2} - (2j+1)/n}\leq 2\sqrt{2}n^{-1/4}$.
	By partitioning $R_j$ into $\cceil{2\sqrt{2}n^{1/4}}$ squares of side length $n^{-1/2}$, we see that $R_j$ can be covered by $\cceil{2\sqrt{2}n^{1/4}}$ disks of radii $\frac{1}{\sqrt{2}}n^{-1/2}$.
See Figure~\ref{fig:lem312}.

\begin{figure}[h]
    \centerline{\includegraphics[scale=0.75]{lem312.pdf}}
    \caption{A rectangle $R_j$ containing a cap $C_j$ can be covered by disks of radii $\frac{1}{\sqrt{2}}n^{-1/2}$.} \label{fig:lem312}
\end{figure}

	Since each disk of radius $\frac{1}{\sqrt{2}}n^{-1/2}$ contains at most $\cceil{\frac{\alpha\pi}{2}}$ points of $X$,
	it follows that
	\begin{align*}
	|X\cap C_j| \quad &\leq \quad |X\cap R_j|\\
	&\leq \quad \cceil{\frac{\alpha\pi}{2}} \cceil{2\sqrt{2}n^{1/4}}\\
	&\leq\quad  \cceil{\frac{\alpha\pi}{2}} (2\sqrt{2}n^{1/4}+1)\\
	&=\quad  O(n^{1/4})+O(1).
	\end{align*}
	\end{proof}

	\begin{lemma}\label{lem3.2}
		$|X\cap D_N|\leq \lceil \alpha \pi\rceil$.
	\end{lemma}
	\begin{proof}
	This is obvious since $D_N$ is a disk of radius less than $n^{-1/2}$.
	\end{proof}

Now,
\begin{align*}
L(X)	\quad
&\leq \quad |X\cap D_N|+ \sum_{j=0}^{ N-1} |X\cap C_j|\tag{by Lemma~\ref{lem2.3}}\\
	&\leq\quad  \lceil\alpha\pi\rceil+N\times(O(n^{1/4})+O(1)) \tag{by Lemmas~\ref{lem3.1} and~\ref{lem3.2}}\\
	&\leq \quad \lceil\alpha\pi \rceil + n^{1/2}(O(n^{1/4})+O(1))\\
	&\leq \quad O(n^{3/4})
\end{align*}

Hence, $L(X) \leq O(|X|^{3/4})$.
		\end{proof}

\subsection{The lower bound on the plane}\label{sec:2dlow}

In this section, we prove that the upper bound in Theorem~\ref{thm1.2} is best possible.

\begin{prop}\label{thm:2dlow}
	For every real number $\alpha > 1$, there exists an $\alpha$-evenly distributed point set $X$ in a unit disk in $\mathbb{R}^2$ such that $L(X) \geq \Omega(|X|^{3/4})$.
\end{prop}
\begin{proof}
	We give an explicit construction of an $\alpha$-evenly distributed point set $X$ in the unit disk $D$ in $\mathbb{R}^2$ centered at the origin with $|X| \leq O(n)$ and $L(X)\geq\Omega(n^{3/4})$.
	Fix $\alpha > 1$, and let $\beta> 0$ satisfy $f_2(\beta) = \alpha$, where $f_2$ is the function defined in Lemma~\ref{lem2.4}.
	Let $C = \max\{2\beta, 4\pi^2\}$ and $M = \ffloor{ \frac{\sqrt{n}}{C} }$.
	For a sufficiently large positive integer $n$, let $k = \ffloor{ n^{1/4} }$.

	Let $P_1$ be a regular $k$-gon centered at the origin such that the distance between the origin and a vertex of $P_1$ is $\frac{C}{\sqrt{n}}$.
	For each $j\in\{1, \ldots, M\}$, let $P_j$ be the scaled copy of $P_1$, centered at the origin, with scaling factor $j$.
	Let $l_j$ be the length of an edge of $P_j$.
	Since $\frac{2x}{\pi} \leq \sin{x} < x$ and $k > n^{1/4}/2$, we have
	\[\frac{j}{n^{3/4}} \leq l_j = 2 \times \frac{C}{\sqrt{n}}j \times \sin{\frac{\pi}{k}} < \frac{4C\pi j}{n^{3/4}}.\]

	Now, for each $j\in\{1, \ldots, M\}$, define a point set $Q_j$ containing all vertices of $P_j$, and in addition include as many points as possible on the boundary of $P_j$ such that the distance between two (consecutive) points on $Q_j$ is at least $\beta n^{-1/2}$.
	Finally, let \[X = \bigcup_{j=1}^{M} Q_j.\]
	See Figure~\ref{fig:thm321} for an illustration.
\begin{figure}[h]
    \centerline{\includegraphics[scale=0.25]{thm321}}
    \caption{An $\alpha$-evenly distributed point set $X$ in a unit disk in $\mathbb{R}^2$ such that $L(X) = \Omega(|X|^{3/4})$.} \label{fig:thm321}
\end{figure}

	Since $\cos\frac{\pi}{k} \geq \frac{1}{2}$ for sufficiently large $k$, the minimum distance between points on the boundaries of $P_j$ and $P_{j+1}$ is at least
	\[\frac{C}{\sqrt{n}} \times \cos\frac{\pi}{k} \geq \frac{C}{2\sqrt{n}} \geq \beta n^{-1/2}.\]
	Hence $\delta(X)\geq \beta n^{-1/2}$, and by Lemma~\ref{lem2.4}, $X$ is $\alpha$-evenly distributed in $D$.

\begin{claim}\label{claim3.4}
	For $j\in\{2, \ldots, M\}$, if $P'_j$ is  a regular $k$-gon whose vertices are the midpoints of edges of $P_j$, then $P_{j-1} \subset P'_j$.
\end{claim}
\begin{proof}
	Let $O$ be the origin and let $W_1$, $V$, and $W_2$ be three consecutive vertices of $P_k$.
For $i\in\{1, 2\}$, let $M_i$ be the midpoint of the edge ${VW_i}$.
Let $U$ be the vertex of $P_{k-1}$ such that $O,U,V$ are collinear, and let $P$ be the point where $UV$ and $M_1 M_2$ intersect.
	It is sufficient to show that $P$ is strictly between $U$ and $V$.
See Figure~\ref{fig:claim322} for an illustration.

\begin{figure}[h]
    \centerline{\includegraphics[scale=0.25]{claim322}}
    \caption{An illustration of Claim~\ref{claim3.4}. $P$ exists strictly between $U$ and $V$.} \label{fig:claim322}
\end{figure}

	Let $l\leq1$ be the length of the line segment $OV$.
	Since $\angle W_i O V = 2\pi/k$ and $W_iOV$ is an isosceles triangle for each $i\in\{1, 2\}$, we know that $\angle M_1 O V = \angle V M_1 M_2 = \pi/k$.
	Since $\sin x < x $ for $x > 0$ and $k > n^{1/4}/2$, the length of the line segment $VP$ is given by
	\[l \times \left(\sin\frac{\pi}{k}\right)^2< 1\times \left(\frac{\pi}{k}\right)^2 = \frac{\pi^2}{k^2} < \frac{4\pi^2}{\sqrt{n}} \leq \frac{C}{\sqrt{n}}.
	\]
	Since the line segment $VP$ has length strictly less than the length of $UV$, which is $Cn^{-1/2}$, it follows that $P$ is strictly between $U$ and $V$.
\end{proof}

\begin{claim}\label{claim3.5}
	For $j\in\{1, \ldots, M\}$, we have $|Q_j| = \Theta(j)$ and $L(Q_j) \geq \frac{j}{4\beta n^{1/4}}$.
\end{claim}

\begin{proof}
	Recall that
	\[\frac{j}{n^{3/4}} \leq l_j < \frac{4C\pi j}{n^{3/4}}.\]
	Since the distance between two consecutive points of $Q_j$ is between $\beta n^{-1/2}$ and $2\beta n^{-1/2}$, we obtain
	\[\frac{1}{2\beta}j \leq \frac{l_j}{2\beta n^{-1/2}}\times n^{1/4} \leq |Q_j| \leq \frac{l_j}{\beta n^{-1/2}}\times n^{1/4} \leq \frac{4C\pi}{\beta}j.\]
	Thus, we conclude that $|Q_j| = \Theta(j)$.

	For the layer number of $Q_j$, observe that every layer of $Q_j$ contains at most two points on each edge of $P_j$.
In fact, the layer number of $Q_j$ is at least half the number of points on an edge.
Therefore,
	\[L(Q_j) \geq \frac{l_j/2}{2 \beta n^{-1/2}} \geq \frac{j/n^{3/4}}{4\beta n^{-1/2}} = \frac{j}{4\beta n^{1/4}}.\]
\end{proof}

\begin{claim}\label{claim3.6}
	$L(X)\geq \Omega(n^{3/4})$ and $|X|= \Theta(n)$.
\end{claim}
\begin{proof}
	Note that
	\[\sum_{j=1}^{M} j = \frac{M(M+1)}{2} = \Theta(n).\]
	Thus $|X| = \sum_{j=1}^{M} |Q_j| = \Theta(n)$.

	On the other hand, Claim~\ref{claim3.4} tells us that all points of $Q_k$ will be removed before removing a point of $Q_{k-1}$ in the peeling process of $X$.
	By Claim~\ref{claim3.5}, we obtain the following lower bound on $L(X)$.
	\[
	L(X) \geq \sum_{j=1}^{M} \frac{j}{4\beta n^{1/4}} = \Omega(n^{3/4}).
	\]
		\end{proof}
	Since $L(X) \geq \Omega(n^{3/4})$ and $|X| =\Theta(n)$, we know that $L(X)\geq\Omega(|X|^{3/4})$.
\end{proof}

\section{Results in higher dimensions}\label{sec:higher}

	In this section, we generalize Proposition~\ref{prop:2dup} in Section~\ref{sec:2dup} to higher dimensions by proving Theorem~\ref{thm1.3}.
	The proof is similar to the planar case, yet, it is not a straightforward generalization.

\begin{proof}[Proof of Theorem~\ref{thm1.3}]

	Fix $d\geq 3$ and let $D_0$ be a unit ball in $\mathbb{R}^d$ centered at the origin.
	Let $X$ be an $\alpha$-evenly distributed finite point set in $D_0$ with sufficiently many points and let $n=|X|$.
		The volume of a $d$-dimensional ball with radius $r>0$ is given by $\dfrac{\pi^{d/2}}{\Gamma\left(\frac{d}{2}+1\right)}r^d = \Theta(r^d)$ for a fixed $d$;
	$\Gamma$ is Euler's gamma function.
	Hence, for a $d$-dimensional ball to have at most a constant number of points of $X$, the ball must have radius $O(n^{-1/d})$.
	Fix $k \geq 0$ and let $B_0$, $B_1$, and $B_2$ be a ball of radius $n^{-k}$, $\frac{\sqrt{d}}{2}n^{-1/d}$, and $\frac{\sqrt{d}}{2}n^{-k}$, respectively.
	Since $X$ is $\alpha$-evenly distributed in $D_0$, there exist constants $c_1, c_2, c_3, c_4 > 0$ depending only on $\alpha, d$, and $k$, but not $n$, such that
	\[|X \cap B_0| \leq \begin{cases} c_1 & \text{ if }k > \frac{1}{d} \\ c_2 n^{1-dk} & \text{ if }0 \leq k \leq \frac{1}{d} \end{cases}, |X \cap B_1| \leq c_3 , \text{ and } |X \cap B_2| \leq c_4 n^{1-dk}.\]

	Let $N = \ffloor{ n^k }$.
	For each $j\in\{0, \ldots, N\}$, let $D_j$ be the ball of radius $1 - \frac{j}{n^k}$ centered at the origin.
	For each $j\in\{0, \ldots, N-1\}$, let $C_j$ be a cap of $D_j\setminus D_{j+1}$ that contains the maximum number of points of $X$ among all caps of $D_j\setminus D_{j+1}$.

	The following lemmas reveal upper bounds on $|X\cap C_j|$ and $|X\cap D_{N}|$.

	\begin{lemma}\label{lem4.1}
	For $j\in\{0, \ldots, N-1\}$, we know
	\[|X\cap C_j|\leq \begin{cases} O(n^{\frac{1}{2}-\frac{1}{2d}}) & \text{ if }k > \frac{1}{d} \\ O(n^{1-\frac{dk}{2}-\frac{k}{2}}) &\text{ if }0 \leq k \leq \frac{1}{d} \end{cases}.\]
	\end{lemma}
	\begin{proof}
	For each $j\in\{0,\ldots, N-1\}$, $C_j$ is bounded by the smallest $d$-dimensional box $R_j$ containing $C_j$.
	Similar to the proof of Lemma~\ref{lem3.1},
	by geometric observations we know that $R_j$ has $d-1$ sides of length $2\sqrt{2n^{-k}-(2j+1)n^{-2k}} \leq 2\sqrt{2}n^{-k/2}$ and one side of length $n^{-k}$.

	If $k \geq 1/d$, then by partitioning $R_j$ into at most $\cceil{ 2\sqrt{2}n^{\frac{1}{d}-\frac{k}{2}} }^{d-1}$ $d$-dimensional boxes of side length $n^{-1/d}$, we see that $R_j$ can be covered by $4^{d-1}n^{\frac{d-1}{2d}}$ balls of radii $\frac{\sqrt{d}}{2}n^{-1/d}$.
	If $0 \leq k \leq 1/d$, then by partitioning $R_j$ into at most $\cceil{ 2\sqrt{2}n^{k/2} }^{d-1}$ $d$-dimensional boxes of side length $n^{-k}$, we see that $R_j$ can be covered by $4^{d-1} n^{(d-1)k/2}$ balls of radii $\frac{\sqrt{d}}{2} n^{-k}$.

	It follows that
	\begin{align*}
	|X\cap C_j| \quad &\leq\quad  |X\cap R_j|\\
	&\leq \begin{cases} c_3 4^{d-1} n^{\frac{d-1}{2d}}  & \text{ if }k \geq \frac{1}{d} \\
	c_4 n^{1-dk} \times 4^{d-1} n^{(d-1)k/2} &\text{ if }0 \leq k \leq \frac{1}{d} \end{cases}\\
	&\leq \begin{cases} O(n^{\frac{1}{2}-\frac{1}{2d}}) & \text{ if }k \geq \frac{1}{d} \\
	O(n^{1-\frac{dk}{2}-\frac{k}{2}}) &\text{ if }0 \leq k \leq \frac{1}{d} \end{cases}.
	\end{align*}
	\end{proof}

	\begin{lemma}\label{lem4.2}
		$|X\cap D_N|\leq \begin{cases} O(1) & \text{ if }k \geq \frac{1}{d} \\ O(n^{1-dk}) &\text{ if }0 \leq k \leq \frac{1}{d} \end{cases}$.
	\end{lemma}
	\begin{proof}
	This is obvious since $D_N$ is a ball of radius less than $n^{-k}$.
	\end{proof}

		Recall that $X$ is an $\alpha$-evenly distributed finite point set in a unit ball in $\mathbb{R}^d$. Now,
	\begin{align*}
		L(X)\quad
	&\leq\quad |X\cap D_N|+ \sum_{j=0}^{N-1} |X\cap C_j|\tag{by Lemma~\ref{lem2.3}}\\
	&\leq\quad  \begin{cases} (\sum_{j=0}^{N-1} O(n^{\frac{1}{2} - \frac{1}{2d}})) + O(1) & \text{ if }k \geq \frac{1}{d} \\ (\sum_{j=0}^{N-1} O(n^{1 - \frac{dk}{2} - \frac{k}{2}})) + O(n^{1-dk}) &\text{ if }0 \leq k \leq \frac{1}{d} \end{cases}\tag{by Lemmas~\ref{lem4.1} and~\ref{lem4.2}}\\
	&\leq\quad  \begin{cases} O(n^{\frac{1}{2} - \frac{1}{2d} + k}) & \text{ if }k \geq \frac{1}{d} \\  O(n^{1 - \frac{dk}{2} + \frac{k}{2}}) &\text{ if }0 \leq k \leq \frac{1}{d} \end{cases}\tag{since $N \leq n^k$}\\
	&\leq\quad  O(n^{\frac{1}{2} + \frac{1}{2d}})\tag{let $k={1/d}$}
	\end{align*}
Hence, $L(X) \leq O(|X|^{\frac{d+1}{2d}})$.
		\end{proof}

\section{Future directions and open problems}\label{sec:rmk}

	In this section, we suggest possible future research directions and open problems.

	In the planar case, we gave a construction to show tightness of the upper bound of Theorem~\ref{thm1.2}.
	For higher dimensions, it is trickier to construct such examples relying only on Euclidean geometry.
	One possible way to find such an example is to consider vector configurations.
	We conjecture that the upper bound we found for higher dimensions is also tight.

\begin{conj}\label{conj1}
	For every real number $\alpha>1$ and $d \geq 3$, there exists an $\alpha$-evenly distributed point set $X$ in $\mathbb{R}^d$ such that $L(X) \geq \Omega(|X|^{\frac{d+1}{2d}})$.
\end{conj}

	In this paper, we focused on upper bounds of the layer number.
	However, one can also ask about lower bounds.

\begin{que}\label{que1}
	For a real number $\alpha>1$ and $d\geq 2$, find a lower bound on $L(X)$ for an $\alpha$-evenly distributed finite point set $X$ in the unit ball in $\mathbb{R}^d$.
\end{que}
	For $d=2$, one can easily construct an example of an $\alpha$-evenly distributed point set $X$ on the plane such that $L(X)\geq\Omega({|X|}^{1/2})$.
	We suspect that $\Omega({|X|}^{1/d})$ is also the best possible lower bound for  $d\geq 2$.

	Finally, recall that in \cite{HPL13}, it was shown that for the $\cceil {n^{1/2} }\times \cceil {n^{1/2}} $ square grid $G_n$ in $\mathbb{R}^2$, $L(G_n) = \Theta(n^{2/3})$.
	However, it is quite challenging to generalize their proof for higher dimensions.
	The authors of \cite{HPL13} also posed the following question.

\begin{que}[\cite{HPL13}]\label{que2}
	If $G_n ^d$ is the $\cceil {n^{1/d}}\times \cdots \times \cceil {n^{1/d} }$ square grid in $\mathbb{R}^d$ for $d \geq 3$, then what can one say about $L(G_n ^d)$?
\end{que}

	Note that the point set $G_n^d$ is an $\alpha$-evenly distributed point set in a unit ball in $\mathbb{R}^d$ for some $\alpha >1$ by applying Lemma~\ref{lem2.4} after rescaling $G_n^d$.
	By Theorem~\ref{thm1.2}, we know $L(G^d_n) \leq O(n^{2/d})$ for $d\geq 3$.
	On the other hand, the lower bound on $L(G^d_n)$ can be obtained as an immediate consequence of the following well-known result (see \cite[Theorem 13.1]{Bar08}, for example).
	\begin{theorem}[\cite{Bar08}]
	If $X \subset \mathbb{Z}^d$, then 	$|V(\conv(X))| << (\Vol(\conv(X)))^{(d-1)/(d+1)}$.
	\end{theorem}
	From the above theorem, we obtain $L(G^d_n) \geq \Omega(n^{2/(d+1)})$ since the number of points deleted in each step of the peeling process of $G^d_n$ is $O(n^{(d-1)/(d+1)})$.

	Indeed, it was shown in \cite{BB91} that the number of lattice points on a ball of radius $r>0$ in $\mathbb{R}^d$ is $\Theta(r^{(d-1)/(d+1)})$.
	Hence, we suspect that $L(G_n^d)=\Theta(n^{2/(d+1)})$, which is same as the expected layer number of a random point set $X$ with $n$ points in a unit ball of $\mathbb{R}^d$~\cite{Dal04}.

\section*{Acknowledgments}
The authors thank Andreas Holmsen for helpful comments and development of this project in the early stages, and also Joseph Briggs for improving the readability of the manuscript.
We thank the referees for pointing out the various mistakes and providing valuable comments, which improved the quality of the manuscript.

config: arxiv


TITLE: Solution by differential equation by Clairaut Form
QUESTION [4 upvotes]: Solve the differential equation:
$$y+x \frac{dy}{dx}=x^4 \bigg(\frac{dy}{dx}\bigg)^2$$
This is given under 'Clairaut form' but I am not able to convert it to Clairaut form of type $y=px+f(p)$ where $p=dy/dx$. The general solution is given as $xy+c=c^2x$ and singular solution is $4x^2y+1=0$. Could someone give me some hint with this?

REPLY [5 votes]: Take the derivative of the equation to obtain
$$2\frac{dy}{dx}+x \frac{d^2y}{dx^2}=4x^3 \bigg(\frac{dy}{dx}\bigg)^2+ 2x^4\frac{dy}{dx}\frac{d^2y}{dx^2}$$
Factorize the right hand of the equation
$$2\frac{dy}{dx}+x \frac{d^2y}{dx^2}=2x^3\frac{dy}{dx} \bigg(2\frac{dy}{dx}+ x\frac{d^2y}{dx^2}\bigg)$$
Now you see that you can rewrite this as
$$\bigg(1 - 2x^3\frac{dy}{dx}\bigg) \bigg(2\frac{dy}{dx}+ x\frac{d^2y}{dx^2}\bigg) = 0$$
So you have two linear ODEs that you can solve, the first giving
$$y=-\frac{1}{4x^2}+C$$
as a solution, the second giving
$$y=-\frac{A}{x}+K$$
However, when you fill them back into your original equation, you'll notice that these only satisfy it provided that
$$C=0 \; \text{ and } \; K=A^2$$
This settles the problem.

REPLY [3 votes]: $$y=-x \frac{dy}{dx}+x^4 \bigg(\frac{dy}{dx}\bigg)^2$$
Let $\quad x=\frac1t\quad\to\quad dx=-\frac{dt}{t^2}\quad\to\quad \frac{dy}{dx}=\frac{dy}{dt}\frac{dt}{dx}= -t^2\frac{dy}{dt}$
$y=-\frac1t \bigg(-t^2\frac{dy}{dt}\bigg)+\bigg(\frac1t\bigg)^4 \bigg(-t^2\frac{dy}{dt}\bigg)^2$
$$y=t\frac{dy}{dt}+\bigg(\frac{dy}{dt}\bigg)^2 $$
$\frac{dy}{dt}=\frac{dy}{dt}+t\frac{d^2y}{dt^2}+2\frac{dy}{dt}\frac{d^2y}{dt^2}$
$$\bigg(t+2\frac{dy}{dt}\bigg)\frac{d^2y}{dt^2}=0$$
General solution :
$\frac{d^2y}{dt^2}=0\quad\to\quad y=at+b=\frac{a}{x}+b=-x(\frac{-a}{x^2})+x^4(\frac{-a}{x^2})^2=\frac{a}{x}+a^2\quad\to\quad b=a^2$
$$y=\frac{a}{x}+a^2$$
and particular solution :
$t+2\frac{dy}{dt}=0 \quad\to\quad y=-\frac{t^2}{4}+c=-\frac{1}{4x^2}+c=-x(\frac{1}{2x^3})+x^4(\frac{1}{2x^3})^2=-\frac{1}{4x^2}\quad\to\quad c=0$
$$y=-\frac{1}{4x^2}$$


TITLE: Probability Distribution on a 1D space with curvature
QUESTION [0 upvotes]: Can one consider that a general probability distribution for some random variable X over a Euclidean space is actually the probability distribution of a uniform random variable over a curved 1D-space ?
(I was thinking about a map of the type $\frac{1}{\sqrt{1+f'^2}}$ between the two distributions)

REPLY [1 votes]: If $X$ has a cumulative distribution function $F(x)$ and $F$ is invertible, and if $U$ is a random variable with a uniform distribution on $(0,1)$, then you can generate $X$ using $F^{-1}(U)$.
Now all you have to do is translate $F^{-1}$ into whatever you mean by a curved 1D-space.


TITLE: If three vector such $|a|^2=a\cdot b=b\cdot c=1,a\cdot c=2$,show that $|a+b+c|\ge 4$
QUESTION [2 upvotes]: Let three vector $\vec{a},\vec{b},\vec{c}$ such
$$|\vec{a}|^2=\vec{a}\cdot\vec{b}=\vec{b}\cdot \vec{c}=1,\vec{a}\cdot \vec{c}=2$$
show that
$$|\vec{a}+\vec{b}+\vec{c}|\ge 4$$
since
$$|a+b+c|^2=|a|^2+2(a\cdot b+\vec{b}\cdot \vec{c}+\vec{a}\cdot \vec{c})+|b|^2+|c|^2=9+|b|^2+|c|^2$$
it suffice to prove
$$|b|^2+|c|^2\ge 7$$
or
$$|b+c|\ge 3$$I just do it now
Thanks in advance!

REPLY [0 votes]: The span $V$ of the three vectors is at most three-dimensional. We may chose an orthonormal basis of $V$ such that $a=(1,0,0)$ and $b=(1,p,0)$. The condition $a\cdot c=2$  enforces $c=(2,y,z)$, and from $b\cdot c=1$ it then follows that $2+py=1$. This can be done with any $p\ne0$ and $y=-{1\over p}$. Altogether we now have
$$a+b+c=\left(4,p-{1\over p}, z\right)\ .$$
It is obvious that this vector has length $\geq4$.


TITLE: Proof of CDF of nakagami-m distribution?
QUESTION [0 upvotes]: I want to derive the CDF of Nakagami-m distribution. Here is what i had tried:
My approach: We know that to find CDF, we have to integrate the PDF. Hence, first writing the PDF of nakagami random variable (X) as $f_X(x)=\frac{2}{\Gamma(m)}\left(\frac{m}{\Omega}\right)^mx^{(2m-1)}e^{-\left(\frac{m}{\Omega}x^2\right)}$-------(1).
Next, i assume $\alpha = m$ and $\beta = \frac{m}{\Omega}$.
Thus (1) becomes: $f_X(x)=\frac{2}{\Gamma(\alpha)}\left(\beta\right)^{\alpha}x^{(2\alpha-1)}e^{-\beta x^2}$-------(2).
Integrating (2) we get CDF as $F_{X}(x) = $ $\int_0^u\frac{2}{\Gamma(\alpha)}\left(\beta\right)^{\alpha}x^{(2\alpha-1)}e^{-\beta x^2}\text{dx}$
Thus, $F_{X}(x) = \frac{2\beta^{\alpha}}{\Gamma(\alpha)}\int_0^ux^{(2\alpha-1)}e^{-\beta x^2}\text{dx} $------(3)
I am not getting how to further solve Eq. (3).
Any help in this regard is highly appreciated.

REPLY [1 votes]: $$F_X(u)=\int_{0}^{u} f_X(x)dx=\int_{0}^{u} \frac{2}{\Gamma(m)}\left(\frac{m}{\Omega}\right)^mx^{(2m-1)}e^{-\left(\frac{m}{\Omega}x^2\right)}dx$$
Now, substitute $t=\frac{m x^2}{\Omega}$, $dt=\frac{2 m x}{\Omega}$ to derive
$$F_X(u)
=\int_{0}^{u} \frac{2}{\Gamma(m)}\left(\frac{m}{\Omega}\right)x \left(\frac{m x^2}{\Omega}\right)^{(m-1)}e^{-\left(\frac{m x^2}{\Omega}\right)}dx
=\frac{1}{\Gamma(m)}\int_{0}^{\frac{2u^2}{\Omega}}  t^{(m-1)}e^{-t}dt=\frac{\gamma(m,\frac{2u^2}{\Omega})}{\Gamma(m)}=P(m,\frac{2u^2}{\Omega})$$
$\gamma$ is the lower incomplete gamma function and $P$ is the regularized Gamma function


TITLE: Using the transition matrix for computing probability.
QUESTION [1 upvotes]: Ruth has a red coin, and Ben has a blue coin. The red coin has a probability of $p$ for heads, and the blue coin has a probability of $q$ for heads. They play a game: they both toss their coins, and if both coins show "Heads" they switch the coins. Otherwise, they keep them. Let $A_n$ denote the event in which Ben has the blue coin after $n$ rounds. Find $P(A_2),P(A_3)$.
There are two situations: Ruth=red, Ben=blue with probability of $pq$ to change it and a probability of $1-pq=p(q-1)+q(p-1)$ to keep it that way. The same goes for the other situation. I get: $P=\begin{pmatrix}1-pq&pq\\pq&1-pq\\ \end{pmatrix}$. But how do I use it to compute actual probabilities? I guess I am to use matrix multiplication but I will have to understand how I turn a matrix into a number. I could really use your help.

REPLY [2 votes]: Let $v_0=\left( \array{ 1 \\ 0 }\right)$. This first entry is the probability that Ben has the blue coin at time 0, while the 2nd entry is that Ben has the red coin at time 0.
Now, convince yourself that
$v_1=\left( \array{ 1-pq & pq \\ pq & 1-pq}\right)\left( \array{ 1 \\ 0 }\right)$
Is the probability distribution of Ben having the blue coin after 1st toss
Prove by induction that $v_{n}:=A^nv_0$ is the distribution of ben having the blue/red coin after $n$ tosses. That is:
$v_n=\left(\array{P(A_n)\\ 1-P(A_n)}\right).$
To find the limit distribution in the comments i provide a hint: Try any combination of $p,q\in (0,1)$ and diagonalize the matrix.


TITLE: Number of functions from n-element set to {1, 2, …, m}
QUESTION [1 upvotes]: I've gotten stuck at the following exercise;

There are m functions from a one-element set to the set {1, 2, …, m}.
  How many functions are there from a two-element set to {1, 2, …, m}?
  From a three-element set? Give a recurrence for the number of T(n) of
  functions from an n-element set to {1, 2, …, m}. Solve the recurrence.

I'm not sure how to begin solving it?

REPLY [2 votes]: sha has ably explained how to find an explicit formula for the number of functions from a set with $n$ elements to a set with $m$ elements.  I will address the recurrence relation.
Without loss of generality, we will take the $n$ element set to be the set $[n] = \{1, 2, 3, \ldots, n\}$.
The number of functions from $f: \{1\} \to [m]$ is $m$ because there are $m$ possible choices for $f(1)$.  Hence, $T(1) = m$.
The number of functions from $f: \{1, 2\} \to [m]$ is $m^2$ since for each of the $m$ ways $f(1)$ can be assigned, there are $m$ ways to assign $f(2)$, yielding $m \cdot m = m^2$ possible functions.  Hence, $T(2) = m^2$.
Let $n \geq 2$.  Suppose that the number of functions $f: [n - 1] \to [m]$ is $T(n - 1)$.  Then the number of functions $f: [n] \to [m]$ is $mT(n - 1)$ since for each of the $T(n - 1)$ ways of assigning the values of $f(1), f(2), \ldots, f(n - 1)$, we can assign $f(n)$ in $m$ ways.
Therefore, we have the recurrence relation
\begin{align*}
T(1) & = m\\
T(n) & = mT(n - 1), n \geq 2
\end{align*}
Evaluating the recurrence for the first few values of $n$ yields
\begin{align*}
T(1) & = m\\
T(2) & = mT(1) = m \cdot m = m^2\\
T(3) & = mT(2) = m \cdot m^2 = m^3
\end{align*}
which suggests that the explicit formula for $T(n) = m^n$, which can be proved by induction.


TITLE: Simplifying complex radicals that includes prime numbers
QUESTION [0 upvotes]: In my mathematics class we learned radicals and how to simplify them. However some of the questions involved prime numbers that were in the radical, and we had to simplify them.
For example:

How on earth can we simplify radicals that have prime numbers in them?

REPLY [1 votes]: $$11-6 \sqrt{2}=9+2-6 \sqrt{2}=\left(3-\sqrt{2}\right)^2\to \sqrt{11-6 \sqrt{2}}=3-\sqrt 2$$
$$11+4\sqrt6=8+3+4\sqrt{2\cdot 3}=\left(2\sqrt 2+\sqrt 3\right)^2\to \sqrt{11+4\sqrt6}=2\sqrt 2+\sqrt 3$$


TITLE: Proof of limits, Spivak
QUESTION [2 upvotes]: So when proving that the function $f(x) = \frac 1x$ approaches $\frac 13$ as $x \to 3$ , Spivak does something like:
$$|\frac 1x - \frac 13| < \epsilon$$
he simplifies it to
$$\frac 13 \cdot \frac1{|x|} \cdot |x - 3| $$
so basically he is trying to show that $(x-3)$ is small hence $\epsilon$ is bigger, so $x$ in $x-3$ lies between $2$ and $4$ i.e. $2<x<4 $ and $\frac 1x $ lies between $\frac 14 $ and $\frac 12$ ie. $\frac14 <\frac 1x<\frac 12$
I understand all the way till there however,
he then puts an inequality:
$$\frac 13 \cdot \frac 1{|x|} \cdot |x-3| < \frac 16 |x - 3|$$
I was just wondering if anyone can inform me on where the $\frac 16$ came from?

REPLY [1 votes]: We're letting $x\to 3$. Since $x$ is close to $3$, we can assume that $|x-3|<1$. Since $||x|-|3||<|x-3|$ we get that $||x|-3|<1$ i.e. $-1<|x|-3<1$. Adding three gives $2<|x|<4$. Inverting gives $$\frac{1}{|x|}<\frac 1 2$$


TITLE: Riemann integrability of a certain function
QUESTION [0 upvotes]: Let $ f $ defined at $ [0,1] $ by
$$f(x)=\frac{1}{p+q}\; \;\text{if }x=\frac pq \; \text{with }\; \gcd(p,q)=1$$
and
$$f(x)=0 \; \;\text{if }\; x=0\; \text{or} \;x\notin \Bbb Q$$
I want to prove that $ f$ is Riemann integrable at $ [0,1]  \;$ and  compute $$\int_0^1f(x)dx$$
They told me to consider the set
$$E_n=\left\{x\in \Bbb Q\cap [0,1]\;\;:\;f(x)\ge \frac 1n\right\} $$ and the function $ \psi $ defined by
$$\psi(x)=\epsilon \; \text{if} \;x\notin E_n$$
and
$$\psi(x)=f(x)\; \text{if} \; x\in E_n.$$
I tried  to construct two step functions to satisfy the definition of Riemann integrability but i don't see how to use the help given.
Thanks in advance.

REPLY [1 votes]: I claim two things:
(i) $f$ is continuous at every irrational point in $[0,1]$ ;
(ii) $\int_0^1 f = 0$.
Notice that claim (i) tell us that $f$ is indeed (Riemann) integrable on $[0,1]$ by the Lebesgue Criterion for Riemann Integrability, beacuse $\mathbb{Q}\cap [0,1]$ has measure zero.
Try proving these claims, by first looking at Thomae's Function, which is very similarly defined. (Claims (i) and (ii) also hold for Thomae's function. Can you modify the proofs to work for your function?)


TITLE: Constructing the incenter of a triangle in only six steps
QUESTION [18 upvotes]: Lately I have become hooked on the game Euclidea. One of the problems gives a triangle and asks you to construct the incenter, or as it is put, "the intersection of angle bisectors."
It is stated that it should only take six steps. Steps are in the mode of the straightedge and collapsible compass constructions at the beginning of Baby Hartshorne: use of the ruler to construct a line or line segment and use of the compass to construct a circle are counted. Extending lines or constructing points at previously constructed intersections are not.
The obvious solution

has sadly been my best effort: bisect two of the triangle's angles (3 circles and 1 line each) and mark the intersection of the two lines.
Any help is appreciated.

REPLY [17 votes]: Your construction is fine, but you can spare two circles if you use the points that are already there, see diagram below.


TITLE: Subtle Twist on the Monty Hall Problem---Does It Make a Difference?
QUESTION [9 upvotes]: In the Monty Hall problem, when the host picks a door and reveals an goat, does it make any difference if he did not know which door the real car was behind, and he just happened to pick a door with a goat?

REPLY [0 votes]: This has been said in various ways in other answers/comments, but I think this is a clearer way to explain it that requires very little theory.
The most obvious difference is that sometimes when the host opened that door, the car would be there and the game would be over. This would happen 1/3 of the time. Also 1/3 of the time the car would be behind the door the player picked initially, and the other 1/3 of the time the car would be behind the door the player had the option of switching to.
If the question is "What is the probability of winning if you switch doors?" well it depends on whether you are including the instances where the contestant does not have that opportunity (on account of Monty opening the winning door by accident). If so the answer is 1/3. If, on the other hand, you are only looking at when Monty doesn't show the car prematurely (maybe the contestant gets to go again?) well then 1/3 out of 2/3 is 1/2.


TITLE: Calculating height of an object in the background based on the height of an object in the foreground
QUESTION [0 upvotes]: I've been googling around all day and I can't really find an answer to this issue. I'm trying to create an image composed to multiple images. I have a person in the foreground who's height gives the viewer perspective for a painting hanging on the wall in the background.
bad rendering to give an example:
poor rendering
I have a couple constants in this poor drawing. A is the height of the person, B is the distance between the person and the wall, and C is the actual height of the painting. Edit: Lets also say I have D which is the distance from the wall to the camera.
If anyone could point me in the right direction on how to solve this I'd be  super greatful. Thanks.
Is there a specific formula I should be looking for or is there some reading that might help me with this?

REPLY [0 votes]: You need one more thing: you need to know the distance from the camera (or painter) to the person (or the wall).
Why?
A six foot person standing in front of a six-foot mural -- say 6 feet away from it --- viewed from a point in the ground another 6 feet away will appear twice as tall as the mural.
That same person, viewed through top-notch binoculars from a mile away will appear almost exactly the same height as the mural. (The binoculars are just there to let you see anything at all!)
It's also helpful to know the "height of eye" -- how high off the ground the camera or viewing eye happens to be.
With those basic facts...you can read any book on computer graphics to show you how to make a nice rendering.
By the way, what's not clear from your "question" is just what you're asking. What is it that you actually want to know?


text:
\begin{definition}[Definition:Finer Filter on Set/Strictly Finer]
Let $\FF \subset \FF'$, that is, $\FF \subseteq \FF'$ but $\FF \ne \FF'$.
Then $\FF'$ is '''strictly finer''' than $\FF$.
\end{definition}

config: wiki


TITLE: How to prove that the reflection is an orthogonal tranformation
QUESTION [1 upvotes]: From Humphreys: A reflection is a linear operator $s$ on $V$ which sends some nonzero vector $\alpha$ to its negative while fixing pointwise the hyperplane $H_{\alpha}$ orthogonal to $\alpha.$ We may write $s=s_{\alpha}.$ The formula for the reflection is
$s_{\alpha}\lambda=\lambda-\frac{(\lambda,\alpha)}{(\alpha,\alpha)}\alpha.$
How to explicitly show that $s_{\alpha}$ is an orthogonal transformation, i.e. $(s_{\alpha}\lambda, s_{\alpha}\mu)=(\lambda, \mu)$ for all $\lambda, \mu \in V$?
Thanks!
Edit: Sorry for the wrong formula given above, it should be
$s_{\alpha}\lambda=\lambda-2\frac{(\lambda,\alpha)}{(\alpha,\alpha)}\alpha.$
Here is my attempt.
$(s_{\alpha}\lambda, s_{\alpha}\mu)=(\lambda - 2\frac{(\lambda,\alpha)}{(\alpha,\alpha)}\alpha , \mu - 2\frac{(\mu,\alpha)}{(\alpha,\alpha)}\alpha )=(\lambda, \mu)+(\lambda, - 2\frac{(\mu,\alpha)}{(\alpha,\alpha)}\alpha)+ (- 2\frac{(\lambda,\alpha)}{(\alpha,\alpha)}\alpha, \mu)+ (- 2\frac{(\lambda,\alpha)}{(\alpha,\alpha)}\alpha, - 2\frac{(\mu,\alpha)}{(\alpha,\alpha)}\alpha)$
and I don't know if it's correct.

REPLY [0 votes]: Choosing an orthonormal basis of $H_\alpha$, and completing with $\frac\alpha{\|\alpha\|}$, one has an orthonormal basis of the whole space. On this basis the matrix of the reflection is diagonal with diagonal entries $1$ except the last which is $-1$. That is clearly an orthogonal matrix. This suffices, as on any orthonormal basis, the orthogonal transformations are precisely those whose matrix is an orthogonal matrix.


TITLE: Newton's third law (action and reaction) and work done with a wheel
QUESTION [1 upvotes]: I'm aware of the common misunderstanding about action and reaction canceling each other; they don't because they don't act on the same object. This is about a more subtle issue: exactly where is the work being done? Consider a bicycle wheel:

The bike wheel pushes the earth backwards (action force $F_A$) and the reaction force $F_R$ is in the opposite direction on the bike wheel (ignoring gravity). But the point of the wheel that touches the ground is not moving relative to the ground; therefore, neither the reaction force nor the action force does any work; therefore, this force cannot be what causes the bike to accerelate from a standstill. (If you account for the displacement of the earth, there would be on the order of $10^{-20}$ W of work, which is small enough to ignore.)
The chain of the bike definitely does work on the sprocket on the back axle (teeth and chain are moving with a force). Presumably, the axle does work on the bike frame; the frame and rider are pushed from the axle. Something tricky happens between the axle and the tire.
The question is: what is a clean way to describe the forces (especially those acting on the wheel) so that this is all consistent? Is it possible to draw the relevant force vectors in a free body diagram?
Edit: to make the problem more well-defined: the bike is accelerating, ignore air resistance, and ignore gravity (you can pretend that it's a rack and pinion construction that works without vertical force.
Here is a diagram with the forces around the sprocket/chain and the forces around the road contact point (arrows not on scale). How do you describe acceleration?

REPLY [2 votes]: But the point of the wheel that touches the ground is not moving
relative to the ground; therefore, neither the reaction force nor the
action force does any work; therefore, this force cannot be what
causes the bike to accelerate from a standstill.

That is not correct. If the wheel is not slipping on the ground, then the static friction force will cause the bicycle, as well as the earth, to accelerate, though the latter would be imperceptible.
Per Newton's third law $F_R$= $F_A$=$F$.
Per Newton's second law the friction force $F$ that the earth exerts on the bicycle causes the bicycle to accelerate
$$a_{b}=\frac{F}{m_b}$$
where $a_b$ is the acceleration of the bicycle and $m_b$ is the mass of the bicycle
The force $F$ that the bicycle exerts on the earth causes the earth to accelerate
$$a_{E}=\frac{F}{M_E}$$
where $a_E$ is the acceleration of the earth and $M_E$ is the mass of the earth.
Clearly since $M_{E}>>>>m_b$, then $a_{E}<<<<a_b$ . The acceleration of the earth would be too small to measure, but it would theoretically exist nonetheless.

The chain of the bike definitely does work on the sprocket on the back
axle (teeth and chain are moving with a force). Presumably, the axle
does work on the bike frame; the frame and rider are pushed from the
axle. Something tricky happens between the axle and the tire.

Ultimately the energy that causes work to be done on the bicycle comes from the conversion of chemical potential energy of the body to mechanical energy doing work pushing on the pedals. If we can ignore any dissipative forces in the chain of events from the force on the bike pedal to the torque applied to the wheel, then all of these forces can be considered internal to the bike/cyclist system. If we can exclude all external dissipative forces (air resistance, tire rolling resistance, etc.), then the only external force acting on the bike/cyclist system is the static friction force exerted by the earth, which is then responsible for the acceleration of the bike.
Hope this helps.


TITLE: Real-valued functions whose level sets are hyperplanes?
QUESTION [0 upvotes]: Does the class of functions $f:\mathbb{R}^n\to\mathbb{R}$ such that all of their level sets $\{x\in\mathbb{R}^n: f(x)=c\}$ are hyperplanes have a special name?
In either case, could someone direct me to a characterization result?
Many thanks!

REPLY [1 votes]: I don't know that they have a special name, but they are all composites of some linear function $\Bbb R^n\to \Bbb R$ with some injective function $\Bbb R\to \Bbb R$.
Proof: Take a function $f:\Bbb R^n\to \Bbb R$ with hyperplanes as level sets. These planes must all be parallel as they are not intersecting, so they all have some normal vector $v$ in common. Define the linear function $f_0:\Bbb R^n\to \Bbb R$ by scalar product with $v$.
Define $f_1:\Bbb R\to \Bbb R$ by
$$
f_1(x) = f(f_0^{-1}(x))
$$
This is well-defined as each level set of $f_0$ is also a level set of $f$, and therefore $f$ only takes one value on all of $f_0^{-1}(x)$.
This gives $f = f_1\circ f_0$.


TITLE: about the Atiyah-Segal axioms on topological quantum field theory
QUESTION [17 upvotes]: Trying to go through the page on Topological quantum field theory - The original Atiyah-Segal axioms - "Let $\Lambda$ be a commutative ring with 1,  Atiyah originally proposed the axioms of a topological quantum field theory (TQFT) in dimension d defined over a ground ring $\Lambda$ as following":
$(1):$ A finitely generated $\Lambda$-module $Z(\Sigma)$ associated to each oriented closed smooth d-dimensional manifold $\Sigma$ (corresponding to the homotopy axiom).
$(2):$ An element $$Z(M) \in Z(\partial M)$$ associated to each oriented smooth (d+1)-dimensional manifold (with boundary) $M$ (corresponding to an additive axiom).
Pardon my question is really stupid, if not just naive:
Questions:
$\bullet (i)$ How do I see this axiom $(2)$: $Z(M) \in Z(\partial M)$ is correct? Instead of $Z(M) \ni Z(\partial M)$? It seems $M$ is one higher dimension than its boundary $\partial M$, so why not more intuitively $Z(M) \ni Z(\partial M)$? Or is that a misleading typo in Wiki, instead we have $$Z(\Sigma) \in Z(\partial M)$$ with $M=M^{d+1}$ being one higher dimensional than $\Sigma=\Sigma^{d}$?
$\bullet (ii)$ How do I physically intuitively digest (1) as a homotopy axiom and (2) as an additive axiom?
ps. I suppose we shall view $Z(\Sigma)$ as a TQFT partition function on the manifold $\Sigma$.

REPLY [14 votes]: The Atiyah-Segal axioms and generally the axioms of FQFT formalize the Schrödinger picture of quantum physics:

to a codimension-1 slice $M_{d-1}$ of space one assigns a vector space $Z(M_{d-1})$ -- the (Hilbert) space of quantum states over $M_{d-1}$;
to a spacetime manifold $M$ with boundaries $\partial M$ one assigns the quantum propagator which is the linear map $Z(M) : Z(\partial_{in} M) \to Z(\partial_{out} M)$ that takes incoming states to outgoing states via propagation along the spacetime/worldvolume $M$. This $Z(M)$ is alternatively known as the  the scattering amplitude or the S-matrix for propagation from $\partial_{in}M$ to $\partial_{out}M$ along a process of shape $M$.

Now for genuine topological field theories all spaces of quantum states are finite dimensional and hence we can equivalently consider the linear dual spaces (using that finite dimensional vector spaces form a compact closed category). Doing so the propagator map
$$
  Z(M) : Z(\partial_{in}M) \to Z(\partial_{out}M)
$$
equivalently becomes a linear map of the form
$$
  \mathbb{C} \to Z(\partial_{out}M) \otimes Z(\partial_{in}M)^\ast = Z(\partial M)
  \,.
$$
Notice that such a linear map from the canonical 1-dimensional complex vector space $\mathbb{C}$ to some other vector space is equivalently just a choice of element in that vector space. It is in this sense that $Z(M)$ is a vector in $Z(\partial_{out}M) \otimes Z(\partial_{in}M)^\ast = Z(\partial M)$.
In this form in physics the propagator is usually called the correlator .
Segal's axioms were originally explicitly about the propagators/S-matrices, while Atiyah formulated it in terms of the correlators this way. Both perspectives go over into each other under duality as above.
Notice that this kind of discussion is not restricted to topological field theory. For instance already plain quantum mechanics is usefully formulated this way, that's the point of finite quantum mechanics in terms of dagger-compact categories. There this is being used to great effect in quantum information theory and quantum computing.


TITLE: What notation to use for stacking a series of matrices?
QUESTION [1 upvotes]: I have a series of matrices that I need to stack on top of each other, and use the resulting tall matrix - in fact, several such matrices, each stacking different components - in a formula. I would like a compact symbol for it, something along the lines of $\sum_i A_i$ for sum or $\prod_i A_i$ for product. I know the regular way is $\left[\substack{A_1\\ \vdots \\ A_n}\right]$, but it's way too bulky for my purposes.

REPLY [0 votes]: There is no single widely used notation for this. One common notation is $\mathrm{col}(A_1,\dots,A_n)$. Another common solution is to use "Matlab notation" and write $[A_1; \cdots; A_n]$. Another solution you might consider (though I don't know how common it is) is to write $[A_i]_{i=1}^n$. More commonly, the latter solution is used for block matrices, as in
$$
[A_{ij}]_{i=1,j=1}^{m,\quad n} =  \pmatrix{A_{11} & \cdots & A_{1n}\\ \vdots & \ddots & \vdots\\ A_{m1} & \cdots & A_{mn}}.
$$


TITLE: Finding a vertex of a triangle knowing the other two and its area
QUESTION [2 upvotes]: I have vertix A, vertix B and the area of a triangle, and I need to find the coordinates of vertex C, knowing that it's on the bisector between the first and the third sector of the Cartesian plane.
Until now I found out the length of the segment AB using the following formula:
$\sqrt{(x_b - x_a)^2 + (y_b - y_a)^2}$
Then I found out the mid-point of A e B and calculated the height of the triangle.
I now need to finally find the coordinates of the last vertex. How do I do this?

REPLY [2 votes]: The condition on vertex  $C$ is that it lies on the line $y=x$.
The area is known, and the length of the base $AB$ is known.  So the height $h$ with respect to this base is known.
Find the equation of the line $AB$. I am sure that you know how to do this. Suppose that this equation turns out to be $ax+by+c=0$.
Since our point $C$ lies on the line $y=x$, we can suppose that its coordinates are $(t,t)$.  We will use the formula for the perpendicular distance from a point $(u,v)$ to the line $ax+by+c=0$. It is a standard fact that this distance is equal to
$$\frac{|au+bv+c|}{\sqrt{a^2+b^2}}.$$
We know $a$, $b$, $c$, and the distance $h$.
So we need to solve the following equation for $t$:
$$\frac{|at+bt+c|}{\sqrt{a^2+b^2}}=h.$$
Or, removing absolute value signs, we need to solve the two linear equations
$$(a+b)t+c=h\sqrt{a^2+b^2}\quad\text{and}\quad (a+b)t+c=-h\sqrt{a^2+b^2}.$$
Remark: The idea is easily extended to solving similar problems, where $C$ lies on any line with given equation, like $2x+3y+4=0$ instead of $y=x$.


text:
\section{Orthogonal Random Forest}
\label{sec:plr}
Now we describe our main algorithm \emph{orthogonal random forest}
(ORF) for the two stage estimation estimation. At a high level, ORF
can be viewed as an orthogonalized version of GRF that is more robust
to the nuisance estimation error. We will defer the details of the
first-stage nuisance estimation to \Cref{sec:kernel-lasso} and focus
on the second stage target estimation here. Similar to GRF, the
algorithm runs a tree learner over $B$ random subsamples $S_b$
(without replacement) to build $B$ trees such that each tree indexed
by $b$ provides a tree-based weight $a_{ib}$ for each observation
$Z_i$ in the input sample. Then we compute ORF weights over the
examples by averaging over the tree-weights, and solve for the ORF
estimator given by \Cref{weighted_moment}.

The tree learner starts with a root node that contains the entire
$\cX$ and recursively grow the tree to split $\cX$ into a set of
leaves until the number of observations in each leaf is not too small.
The set of neighboods defined by the leaves naturally gives a
simlarity measure between each observation and the target $x$.
Following the same approach of \cite{GRF,WA}, we maintain the
following tree properties in the process of building a tree.
\begin{specification}[Forest Regularity]\label{forest_spec}
The tree construction process satisfies
\begin{itemize}
\item \textit{Honesty}: we randomly partition the input sample $S$
  into two subsets $S^1$, $S^2$, then uses $S^1$ to place splits in
  the tree, and uses $S^2$ for estimation.
\item $\omega$-\emph{balanced}: each split leaves at least a fraction
  $\omega$ of the observations in $S^2$ on each side of the split for
  some parameter of $\omega\leq 0.2$.
\item \textit{Minimum leaf size $r$}: there are between $r$ and
  $2r - 1$ observations from $S^2$ in each leaf of the tree.
\item $\pi$-\emph{random-split}: at every step, marginalizing over the
  internal randomness of the learner, the probability that the next
  split occurs along the $j$-th feature is bounded below by $\pi/d$
  for some $0 < \pi \leq 1$, for all $j = 1, ..., d$ (e.g., this can
  be achieved by uniformly randomizing the splitting variable with
  probability $\pi$).
\end{itemize}
\end{specification}

The key modification to GRF's tree learner is our incorporation of
double ML in the splitting criterion. In order to accurately capture
the heterogeneity in the target parameter $\theta$ in the presence of
high-dimensional nuisance, we also perform a two-stage estimation at
each internal node to decide the next split. While the splitting
criterion does not factor into our theoretical analysis (similar to
\cite{GRF}), we find it to be an effective practical heuristic.

\paragraph{Splitting criterion with orthogonalization.}
At each internal node $P$ we perform a two-stage estimation over
$(P\cap S^1)$, i.e.~the set of examples in $S^1$ that reach node $P$:
1) first compute a nuisance estimate $\hat h_P$ given by the parameter
$\hat \nu_P$ that minimizes $\sum_{i\in (P\cap S^1)} \ell(Z_i; \nu)$,
and then 2) form estimate $\hat \theta_P$ using $\hat h_P$:
\[
  \hat \theta_P \in\argmin_{\theta\in \Theta} \left\|\sum_{i\in (P\cap
      S^1)} \psi(Z_i; \theta, \hat h_P(W_i)) \right\|
\]
Given the estimates $(\hat \theta_P, \hat h_P)$, we would like to find
an axis-aligned split of some node into two children $C_1$ and $C_2$
such that if we perform the same two-stage estimation separately at
each child, the new estimates $\hat \theta_{C_1}$ and
$\hat \theta_{C_2}$ take on very different values, so that the
heterogeneity of the two children nodes is maximized. However,
performing the two-stage estimation of $\hat \theta_{C_1}$ and
$\hat \theta_{C_2}$ for all possible splits is too computationally
expensive. Instead, we will approximate these estimates by taking a
Newton step from the parent node estimate $\hat \theta_P$: for any
child node $C$ given by a candidate split, our proxy estimate is then
given by
\[
  \tilde \theta_{C} = \hat \theta_P - \frac{1}{|C\cap S^1|}\sum_{i\in
    C} A_P^{-1} \psi(Z_i; \hat \theta_P, \hat h_P(W_i))
\]
where
$A_P = \frac{1}{|P\cap S^1|} \sum_{i\in P\cap S_b^1} \nabla_\theta
\psi(Z_i; \hat \theta_P, \hat h_P(W_i))$.

Given the estimates $\tilde \theta_{C}$, we select the candidate split
that maximizes the following proxy heterogeneity score for the:
\begin{equation}\label{splitting}
  \tilde \Delta(C_1, C_2) = \sum_{j=1}^2 \frac{1}{|C_j\cap S^1|} \left(\tilde
    \theta_{C_j} -\hat \theta_P \right)^2
\end{equation}

\paragraph{ORF weights and estimator.}
For each tree indexed $b\in [B]$ based on subsample $S_b$, let
$L_b(x)\subseteq \cX$ be its leaf containing the target feature $x$,
and we assign \emph{tree weigh} and ORF weight to each observation
$i$:
\begin{align*}
  a_{ib} = \frac{\mathbf{1}[(x_i\in L_b(x)) \wedge (Z_i\in S_b^2)]}{|L_b(x) \cap S_b^2|}, \quad a_i = \frac{1}{B}\sum_{b=1}^B a_{ib}
\end{align*}
The ORF estimator $\hat \theta$ is then computed by solving the
weighted moment condition in \Cref{weighted_moment}.

\citet{WA} show that under the structural specification of the trees,
the tree weights are non-zero only around a small neighborhood of $x$.

\begin{theorem}[Kernel shrinkage \cite{WA}]\label{kernel-bound}
  Let $s$ be the subsample size. Suppose the minimum leaf size
  parameter $r = O(1)$ and tree is $\omega$-balanced and
  $\pi$-random-split. Further, assume that each feature $x_i$ is drawn
  independently from the uniform distribution over $[0, 1]^d$. Then
  the tree weights satisfies
  $\Ex{}{\sup\{\|x- x_i\|\colon a_{ib} > 0 \}} =
  O(s^{-\frac{1}{2\alpha d}})$, with
  $\alpha = \frac{\log(\omega^{-1})}{\pi\log((1 - \omega)^{-1}) }$.
\end{theorem}

\iffalse
\begin{algorithm}[h]
\begin{algorithmic}[1]
  \STATE{\textbf{Input}: a dataset $D$ of size $n$, target point $x$,
    kernel base learner $\cL_k$, parameter $B$: number of kernels,
    parameter $s$ subsample size}

  \STATE{Randomly split the data set $D$ into two data sets of equal
    size $D_1$ and $D_2$}
  \STATE{\textbf{First stage: nuisance estimation.}}
  \STATE{Compute nuisance estimate $\hat h$ by performing a kernel
    nuisance estimation using dataset $D_1$}

    \STATE{\textbf{Second stage: moment estimation with $\hat h$}.}

    \STATE{For each $Z_i\in D_2$, set weight $a_{ib} = 0$ for all
      $b\in[B]$}

    \STATE{\textbf{For} $b = 1 ,\ldots , B$: }

    \INDSTATE{Let $S_{b}$ be a set of $s$ observations randomly
      subsampled without replacement from $D_2$}

    \INDSTATE{Run tree learner on $S_b$ and compute tree weight on
      each observation $i\in D_2$.}
    \STATE{\textbf{For} each $Z_i\in D_2$, let $a_i = \frac{1}{B}\sum_{b=1}^B a_{ib}$}
  \STATE{Compute $\hat \theta$ by solving the weighted moment
    condition in \Cref{weighted_moment}.
    }
    \caption{Orthogonal Random Forest}
  \label{alg:mainalg}
\end{algorithmic}
\end{algorithm}
\fi

We will leverage this kernel shrinkage result in our analysis.

\section{Convergence and Asymptotic Analysis}\label{sec:conv-rate}
\iffalse
\paragraph{Base kernel learner.} The learner $\cL_k$ takes a set $S$
of observations as input, and outputs a kernel weighting function
$K\colon \cX\times \cX \times \cZ^m \rightarrow [0,1]$. In particular,
given any target feature $x$ and a set of observations $S$, the weight
of each observation $Z_i$ in $S$ with feature vector $x_i$ is
$K(x_i, x, S)$. For the convenience of our analysis, we will assume
that the weights among the observations in $S$ are non-negative and
normalized such that $\sum_{Z_i \in S} K(x_i, x, S) = 1$.

Following the approach of generalized random forest (GRF) by
\citet{ATW17}, we run the base kernel learner on $B$ random subsamples
and take the average over the kernel weights to obtain the similarity
weights $a_i$. This allows us to analyze the weighted score as a
$U$-statistic, which is important for establishing convergence rate
and asymptotic normality.

The formal description of estimation procedure in \Cref{alg:mainalg}.
To analyze our estimator, we rely on several assumptions on the moment
condition and the kernel learner.
\fi

To provide theoretical guarantees for ORF, we reluy on the following
assumption on the local moment conditions.
\begin{assumpt}\label{tech-conditions}
  The moment condition and the score function satisfy the following:
\begin{enumerate}
\item \textbf{Local Orthogonality.} The moment condition satisfies
  local orthogonality.
\item \textbf{Identifiability.}  The moments $m(x; \theta, h_0)=0$ has
  a unique solution $\theta_0(x)$.

\item \textbf{Curvature.} The Jacobian
  $\nabla_\theta m(x; \theta_0(x), h_0)$ has minimum eigenvalue
  bounded away from zero.
\item \textbf{Smoothness of moments.} For every $j\in [p]$ and for all
  $\theta$ and $h$, the eigenvalues of the expected Hessian
  $\Ex{}{\nabla^2_{(\theta, h)} \psi_j(Z; \theta, h(W))\mid x, W}$ \vscomment{I think we also need to condition on $W$ for the proof, which I added. We might as well assume it point-wise for simplicity.} are
  bounded above by a constant $O(1)$.  For any $Z$, the score
  $\psi(Z; \hat \theta, \hat \nu)$ is $O(1)$-Lipschitz in
  $\hat \theta$ for any $\hat \nu$ and $O(1)$-Lipschitz in $\hat \nu$
  for any $\hat \theta$.

\item \textbf{Boundedness.} The parameter set $\Theta$ has constant
  diameter.  There exists a bound $\psimax$ such that for any
  observation $Z$, the first-stage nuisance estimate $\hat h$
  satisfies {$\|\psi(Z; \theta, \hat h)\|_{\infty}\leq \psimax$} for
  any $\theta\in \Theta$.

\end{enumerate}
\end{assumpt}

Note that except for the local orthogality condition, all of the
assumptions are imposing standard boundedness and regularity
conditions of the moments.

\iffalse
Next, we will turn to our assumptions on the kernel learner.
\begin{assumpt}[Assumption Kernel Learner]\label{shrinkage}
  The learner takes as input a set $S$ consisting of $s$
  i.i.d. observations drawn from $\cD$ and satisfies the following:
\begin{enumerate}
\item \textit{Kernel Shrikage.} The kernel weights satisfy
\begin{equation*}
  \Ex{}{\sup \left\{\|x - x_i\|_2: K(x_i, x, S) > 0 \right\}} = O\left(s^{-\tau}\right)
\end{equation*}
\item \textit{Honesty.} For any observation $i$, the weight
  $K(x_i, x, S)$ is independent of $Z_i$, conditioned on realized
  feature being $x_i$.
\end{enumerate}
\end{assumpt}

The first assumption asserts that the weights are \emph{localized}
around the target $x$. The second assumption ensures that the
high-dimensional nuisance of the observation does not influence the
weight calculatino. We will establish both of these conditions for our
variant of generalized random forest.\swcomment{pls check}
\fi

\iffalse
In the second stage, we use techniques from orthogonal machine
learning to compute the estimate $\hat \theta$ by solving the weighted
moment condition. The formal procedure is described in
\Cref{alg:stage-two}.

\begin{algorithm}[htpb]
  \label{alg:stage-two}
\begin{algorithmic}
  \STATE{\textbf{Input}: data set $S$, target point $x$, Kernel
    function $\hat{K}(x, x_i, S)$ using an auxiliary sample $S'$, such
    that $\sum_{i=1}^n \hat{K}(x, x_i, S)=1$. }

 \STATE Using a samples $S''$
  estimate nuisance function $\hat{h}$ \STATE For each data target
  $x$, estimate $\theta(x)$ by solving the local empirical moment:
\begin{equation}
\sum_{i\in S} \hat{K}(x, x_i, S_{-i})\cdot \psi(Z_i; \theta, \hat{h})=0
\end{equation}
\end{algorithmic}
\caption{Stage 2: estimation via orthogonal machine learning}
\label{alg:general}
\end{algorithm}

We make the following assumptions on the estimated kernels:
\begin{assumpt}[Kernel Averaging and Honesty] The estimated Kernel is
  an average over $B$ Kernels created based on sub-sampled data sets:
\begin{equation}
K(x_i, x, S_{-i}) = \frac{1}{B} \sum_{b=1}^B K_b(x_i, x, S_{-i})
\end{equation}
and $K_b(\cdot, \cdot, \cdot)$ is estimated on a sub-sample without replacement of size
$s$ of an auxiliary independent dataset $S'$ of size $n$.
\end{assumpt}
\fi

\vsedit{Now we state the convergence guarantee of
  $\|\hat \theta - \theta_0(x)\|$.}

\begin{theorem}\label{thm:converge}
  Suppose that the marginal each feature vectors $x_i$ are
  independently and uniformly distributed over $[0, 1]^d$ and that the
  moment conditions satisfy \Cref{tech-conditions}. {If the first stage
  estimates are consistent at a sufficiently fast rate:
\begin{align*}
  &\Ex{}{\|\hat h(W) - h_0(W)\|^2\mid x}\\ \leq &{o}_p\left(\left( s^{-\tau} +
    \psimax\sqrt{\frac{s \, p\, \ln(p\, n/ s)}{n}} \right) \right)
  \end{align*}
and the second stage estimate is consistent, i.e. $\Ex{}{ \|\hat{\theta} - \theta_0(x)\|} = o_p(1)$,
then the first stage estimation error can asymptotically be ignored and the final stage estimate $\hat{\theta}$ converges at an oracle rate of:
\begin{align*}
&\Ex{}{ \|\hat
    \theta - \theta_0(x) \|} \\\leq &{O}\left( \sqrt{p} \left(s^{-\tau} +
    \psimax\sqrt{\frac{s \, p\, \ln(p\, n/ s)}{n}} \right) \right)
\end{align*}}
\end{theorem}

\swcomment{add a remark here.}

In this section, we will assume consistency of the overall estimation
process, i.e. that $\|\hat \theta - \theta_0(x)\| = o_p(1)$, and prove
a rate of convergence conditional on consistency. In the next section
we will also argue consistency under some extra set of convexity
conditions. In essence, consistency allows us to restrict the estimate
$\hat{\theta}$ in a cone around the true parameter, such that
$\|\hat{\theta}-\theta_0(x)\|^2 < \kappa_n
\|\hat{\theta}-\theta_0(x)\|$, for some $\kappa_n = o_p(1)$. Within
this cone, we prove an explicit convergence rate of the estimation
error.  We have a stronger consistency rate when the score is a
gradient of loss.

\iffull First, we will bound the estimation error as a sum of
$m(x; \theta, \hat h)$ and second order terms. The proof follows from
the Taylor expansion of the moment function and mean-value theorem
(see appendix).

\begin{lemma}\label{lem:taylor}
  Under \Cref{tech-conditions}, for any nuisance estimate $\hat h$ and
  parameter $\theta$,
  \begin{align*}
   & \|\theta - \theta_0(x)\| \leq \mathcal{O} \left( \left\|m(x; \theta, \hat h)\right\| \right)\\ + &\sqrt{p}\, \mathcal{O}\left(\Ex{}{\|\hat h(W) - h_0(W)\|^2\mid x}
      +\|{\theta}-\theta_0(x)\|^2\right).
  \end{align*}
\end{lemma}

Next, we will fix the nuisance estimate $\hat h$ and define the
following functions of $\theta$:
\begin{align*}
  \Psi(\theta) &= \sum_{i: Z_i \in D_2} a_{i} \, \psi(z_i;
                 \theta, \hat h(W_i)), \\
  \Lambda_n(\theta) &=   m(x; {\theta}, \hat{h}) - \Psi(\theta)

\end{align*}

Recall that our estimate $\hat{\theta}$ at the target point $x$ is the
solution to the equation: $\Psi(\hat{\theta}, \hat{h}) =
0$. Equivalently, we can also view $\hat \theta$ as the solution for
$m(x; \hat\theta , \hat h)= \Lambda_n(\hat \theta)$.  This means we
can decompose the error as
\begin{align*}
&  \|\hat \theta - \theta_0(x)\| = O\left(\left\|\Lambda_n(\hat \theta )
    \right\| \right)\\ +  &O\left(\sqrt{p}\, \left(\Ex{}{\|\hat h(W) -
      h_0(W)\|^2\mid x} +\|\hat{\theta}-\theta_0(x)\|^2\right) \right)
\end{align*}

Note that under our assumption on the first stage estimation error
rate and condition that the second stage estimator is consistent, both
of the second-order terms $\Ex{}{\|\hat h(W) - h_0(W)\|^2\mid x}$ and
$\|\hat{\theta}-\theta_0(x)\|^2$ will be in smaller order than
$\|\hat \theta - \theta_0(x)\|$. We will defer the proof of
consistency to the appendix and focus on bounding the scale of
${\Lambda_n(\theta)}$ for any $\theta\in \Theta$.

\vsedit{\begin{lemma}[Uniformly Bounding
    $\Lambda_n(\theta)$]\label{lem:lambda-n} For any $x$:
\begin{equation}
\Ex{}{\sup_{\theta \in \Theta} \|\Lambda_n(\theta)\|_{\infty}} = {O}\left( s^{-\tau} +
    \psimax\sqrt{\frac{s\ln(n)}{n}}\right)
\end{equation}
\end{lemma}}

\begin{proof}[Proof sketch of \Cref{lem:lambda-n}]
  We will rewrite the expression of $\Lambda_n(\theta)$ by adding and
  subtracting the term $\mu(\theta) = \Ex{}{\Psi(\theta)}$, where the
  expectation is taken over both the random draws of the observations
  and the internal randomness of the algorithm. By leveraging the
  honesty property of the kernel weights, we can rewrite $\mu(\theta)$
  as the following.
\begin{lemma}\label{exp-proof}
  For any $\theta$,
  $$\mu(\theta) = \Ex{}{\sum_{i: Z_i \in D_2} a_{i}\,
    m(x_i; \theta,\hat h)}.$$
\end{lemma}

Then we can decompose $\Lambda_n(\theta)$ as a sum of two error terms
such that the first one is \emph{kernel error} due to the kernel
averaging around a neighborhood of $x$, and the second one is
\emph{sampling error} due to the sampling error of the moment:
\begin{align*}
  &\Lambda_n(\theta)  =~  m(x; {\theta}, \hat{h}) - \mu({\theta}) +  \mu({\theta}) - \Psi(\theta)\\
  &  = \underbrace{\Ex{}{\sum_{i: Z_i \in D_2} a_{i}\cdot \left(m(x; {\theta}, \hat{h}) - m(x_i; {\theta}, \hat{h})\right)}}_{\Gamma(\theta)=\text{kernel error}}
    \\ & + \underbrace{\mu(\theta) - \frac{1}{B} \sum_{b=1}^B \sum_{i:Z_i \in D_2} a_{ib} \cdot \psi(Z_i; {\theta}, \hat{h})}_{\Delta(\theta)=\text{sampling error}}
\end{align*}

By the assumption of kernel shrinkage and the Lipschitzness of the $m$
in the first input $x$, we can bound the kernel error by
$O(s^{-\tau})$. To bound the sampling error, first observe that
$\sum_{i: Z_i\in D_2} a_{ib}\cdot \psi_j(Z_i; {\theta}, \hat{h})$ is
computed based on a random sub-sample of $D_2$ (without replacement),
and thus each coordinate $\Psi_j(\theta)$ can be viewed as a Monte
Carlo approximation to a $U$-statistic, centered at
$\mu_j(\theta)$. Hence, we can bound the sampling error with high
probability using concentration inequality. Finally, to uniformly
bound the sampling error for all $\theta$, we will apply union bound
over an $\eps$-cover over the set $\Theta$, for sufficiently small
value of $\eps$.
\end{proof}

\begin{proof}[proof of \Cref{thm:converge}]
  By \Cref{lem:lambda-n}, we have
  $\Lambda_n(\hat \theta) \leq \sqrt{p} \, {O}\left( s^{-\tau} +
    \psimax\sqrt{\frac{s \, p\, \ln(p\, n/ s)}{n}}\right) \equiv E$.
  Since $\hat \theta$ is consistent (proof deferred in the appendix),
  the second term $\|\hat\theta - \theta_0(x)\|^2$ is at most
  $\frac{1}{2}\|\hat{\theta} - \theta_0(x)\|$. Further, since the
  nuisance estimation error term is in smaller order than
  $E/\sqrt{p}$, we can bound $\|\hat{\theta} - \theta_0(x)\| \leq E$,
  as desired.
\end{proof}


TITLE: Differentiability of $f$. Given $0 < \beta < 1$ and $|f(x)|\geq |x|^ \beta $ and $f(0)=0$. Show that $f$ is not differentiable at $0$
QUESTION [0 upvotes]: This is what I have so far. I think it is the absolute value signs that are throwing me off. By the definition of derivatives,
$$
f'(0) =  \lim_{h \to 0} \frac {f(0 +h) - f(0)} {h}= \lim_{h \to 0} \frac {f(h)} {h}\\
$$
But now what? Since $f(0)=0$ and as $h$ tends to $0$, doesn't the the derivative read $0/0$?
I know that I should be getting the left and the right hand limit to be different at zero. I am just failing to carry the rest of the proof through. Will appreciate any help.

REPLY [0 votes]: The result is wrong if $\beta=1$ (try $f(x)=x$). If $\beta\lt1$, this follows from
$$
\left|\frac{f(h)}h\right|\geqslant\frac1{|h|^{1-\beta}}\to\infty.
$$

REPLY [0 votes]: $$
\left|\frac{f(h)}{h}\right|\geq |h|^{\beta-1}.
$$
If $0\leq\beta< 1$, we have that $\beta-1$ is negative. Hence $|h|^{\beta-1}$ diverges as $h$ tends to zero and the limit $\lim_{h\to 0}f(h)/h$ does not exist.


TITLE: Is there a $t$ such that this function is positive?
QUESTION [2 upvotes]: Let $b>0$ and $p (x,y) := \frac{1}{\sqrt{2\pi}}\exp (- \frac{(x-y)^2}{2})$ denote the Gaussian kernel. Set $1- \alpha := \int_{-b}^{b} p(0,y) \text d y$.
Define the function $\psi : [0,b]\times[0, b] \to \Bbb R$ by
$$\psi (t , c):= \int_{c}^\infty p(0,y)\text d y - \frac{1}{1-\alpha} \int_{-b}^{b} p(0,y) \int_{t+c}^{\infty} p(y,x)\text d x \text dy
$$
Let $Y, X \sim \mathcal{N} (0,1)$ standardnormal and independent. We can rewrite $\psi$ as follows.
$$\psi (t,c) = \Bbb P (Y \geq c) - \Bbb P (X+Y \geq t+c | \vert X\vert \leq b)$$
If we fix $c$ we observe that $t\mapsto \psi (t,c)$ is strictly increasing and one can compute (this comes from black boxes) that $\psi(0,c)\leq 0$ and $\psi (b,c)\geq 0$. Due to continuity there must be an unique $t_c \in [0,b]$ with $\psi (t_c ,c ) = 0$.
Additionally, from the same black box I know that $t_{b} < b$.
What I want to know is whether it is true that
$$\sup_{c\in [0,b]} t_c = t_b$$
or equivalently
$$\psi(t_b ,c ) \geq 0 \quad \forall c\in [0,b]$$
1) My first attempt: Observing that $\psi (t_b , 0) = \frac 1 2 - \Bbb P (X+Y \geq t_b| \vert X\vert \leq b) \geq 0$ gave me the idea to try whether
$$c\mapsto \psi (t_b ,c ) \text{ or more generally } c\mapsto \psi (t,c)$$
is decreasing, but could not figure it out.
A computation in python suggests that this is true for $t_b$ on $c\in[0,b]$ (but not for all $c$) and not true for some $t< t_b$.
2) Second idea: By intuition I guessed that $\Bbb P (X+Y \geq t+c | \vert X\vert \leq b) \leq \Bbb P (X+Y \geq t+c) $. This is indeed true and so one could try to show that
$$\Bbb P (Y \geq c) - \Bbb P (X+Y \geq t_b+c) \geq 0 \quad\forall c\in[0,b]$$
but I think that this is just not the case.

REPLY [0 votes]: I think I have found a way to solve this by ansatz 1. The property $c\mapsto \psi (t_b , c)$ decreasing is equivalent to
$$0 \geq \frac{\partial}{\partial c} \psi (t_b , c) = f(t_b + c) - g(c)\quad \forall c\in[0,b]$$
where $f(x) := \frac{1}{1-\alpha} \int_{-b}^{b} p(0,y)p(y,x) \text d y$ and $g(x) := p(0,x)$. Note that both $f$ and $g$ are symmetric densities with $f(0) < g(0)$. Since both integrate to $1$ they must have at least one intersection point on the positive real line (and thus the same on the negatives). Let $x_0$ denote the intersection point in $(-\infty , 0)$.
Let $b\ge t>0$ and define $f_t (x) := f(x+t)$. Since both $f$ and $g$ are radially decreasing we have that $f_t (0) <f(0)<g(0)$. Furthermore, we have that $f_t(x_0 - t)=f(x_0) =g(x_0) > g(x_0 -t)$. Due to continuity there has to be a intersection point of $f_t$ and $g$ in $(-\infty , 0)$.
Claim: $f_t$ and $g$ have at most two intersection points.
Given the claim we can proceed as follows: Suppose the remaining intersection point is contained in $[0,b]$. The claim yields that then $f_t (x) > g(x)$ for all $x> b$. By definition of $t_b$ we have that
$$0 = \psi (t_b , b) =\int_b^\infty ( g(x) -f_{t_b}(x) ) \text d x < 0$$
which is a contradiction. Therefore an intersection point in $[0,\infty)$ can only occur in $[b, \infty)$. By continuity and the fact that $f_{t_b} (0) < g(0)$ this means that $f(t_b + c) \le g(c)$ for all $c\in [0,b]$, which yields the statement.
Proof of the claim:
$x$ is an intersection point if and only if $\phi (x) := \log ( \frac{f_t (x)}{g(x)} ) = 0$. Now consider
$$ \phi ' (x) =  \frac{f '(x +t) }{f (x+t)} - \frac{g'(x)}{g(x)} = \frac{\int_{-b}^{b} p(0,y) (y - (x+t))p(y,x+t) \text d y}{\int_{-b}^{b} p(0,y) p(y,x+t) \text d y} +x  = \frac{\int_{-b}^{b}(y - t) p(0,y) p(y,x+t) \text d y}{\int_{-b}^{b} p(0,y) p(y,x+t) \text d y}$$
For every $x$ this can only be equal to $0$ if
$$0 = \int_{-b}^{b}(y - t) p(0,y) p(y,x+t) \text d y = \int_0^{b-t} z p(z+t,0)p(z,x)\text d z - \int_0^{b+t} z p(z-t,0) p(-z,x) \text d z$$
which can only be the case if
$$\varphi (x) := \frac{\int_0^{b-t} z p(z+t,0)p(z,x)\text d z}{\int_0^{b+t} z p(z-t,0) p(-z,x) \text d z} = 1$$
Claim: $\varphi$ is strictly increasing
For this note that it suffices to show that for all $z_0 \in (0,b-t), z_1 \in (0,b+t)$ we have that
$$x \mapsto \frac{z_0 p (0,t+z_0)p(z_0,x)}{z_1 p(0,z_1-t)p(-z_1,x)}$$
is strictly increasing. Transforming this yields that this mapping is
$$x\mapsto \frac{z_0 p (0,t+z_0)}{z_1 p(0,z_1-t)} e^{-\frac{1}{2} (z_0^2 -z_1^2)} e^{(z_0+z_1)x}$$
which is indeed strictly increasing in $x$. Looking back this means that
$\phi ' (x) = 0$ occurs for at most one $x$. This means that $\phi $ has at most one local extremum and cannot be constant anywhere. In view of the mean value theorem this means that $\phi$ can have at most two roots.