TITLE: Can Electric field line form a right angle?
QUESTION [1 upvotes]: Can Electric field line form a right angle ? something that look like the letter L..
please be as rigorous as possible.
Thanks in advance.

REPLY [1 votes]: In order for this to happen, the electric field at the point where the field line is forming the right angle would have to be undefined. This can only happen if there is a divergent density of charge at the point. Thus, strictly speaking, the electric field line doesn't have a well-defined existence at such a point. However,  if one must, one can arrange many such situations where there are multiple field lines in the neighborhood of such a point which would be perpendicular. A cute example is provided by @probablysomeone.


TITLE: $\perp \Rightarrow p$ Syntactic Proof
QUESTION [2 upvotes]: Given the following axioms
$$\begin{aligned}&1. p\Rightarrow (q\Rightarrow p)\\&2. [p\Rightarrow (q\Rightarrow r )] \Rightarrow [(p\Rightarrow q)\Rightarrow (p\Rightarrow r)]\\&3. \neg\neg p \Rightarrow p
 \end{aligned}$$
and the deduction rule of modus ponens, I want to prove that $$\perp \Rightarrow p.$$
Can somebody give me a hint how to do that?

REPLY [2 votes]: Proof :
1) $\bot \rightarrow ((p \rightarrow \bot) \rightarrow \bot)$ --- from Ax.1
2) $\bot \vdash (p \rightarrow \bot) \rightarrow \bot$ --- from 1) and modus ponens
3) $((p \rightarrow \bot) \rightarrow \bot) \rightarrow p$ --- from Ax.3, with the abbreviation : $\lnot p := p \rightarrow \bot$
4) $\bot \vdash p$ --- from 2) and 3), by modus ponens

5) $\vdash \bot \rightarrow p$ --- from 4) by Deduction Theorem.

Note : see Alonzo Church, Introduction to Mathematical Logic (1956), page 90.


TITLE: An example of a matrix in $\mathrm{SL}(4, \mathbb{Z})$ with the following properties
QUESTION [4 upvotes]: I am looking for a matrix $M\in \mathrm{SL}(4, \mathbb{Z})$, with all eigenvalues equal to $1$, and with the following properties:
Write $M=\begin{bmatrix}
A_1&A_2\\
A_3&A_4
\end{bmatrix},
$ where the $A_i$ are $2$ by $2$ sumbatrix of $M$.
Let $d_i$ be the dot product of two rows of $A_i$, i.e. if $A_i = \begin{bmatrix}
a&b\\
c&d
\end{bmatrix}$, then $d_i = ac +bd$.
Let $a_i = \mathrm{det}(A_i) - d_i$.
For example if  $A_1 =\begin{bmatrix}
1&2\\
3&4
\end{bmatrix}$,  then  $d_1 = 11$ and $a_1 = - 2 - 11 = -13$.
Consider the matrix $A =  \begin{bmatrix}
a_1&a_2\\
a_3&a_4
\end{bmatrix}$,  I would like to find $M$ such that $A$ is in $\mathrm{GL}(2, \mathbb{Z})$, and has one eigenvalue with absolute value not equal to $1$.
The matrices I have tried so far: since $M$ needs to have eigenvalues all equal to $1$, I tried the matrices consisting of just Jordan blocks, unfortunately, they didn't work. I also tried the matrix in the form $M=\begin{bmatrix}
A_1&A_2\\
0&A_4
\end{bmatrix},
$ where $A_1$ and $A_4$ have all eigenvalues all equal to $1$, but in this case $A$ will have all eigenvalues with absolute values $1$. I am a bit stuck as I can't think of other $4$ by $4$ matrices that have all eigenvalues equal to $1$.
Any idea to construct such matrices will be really appreciated.

REPLY [3 votes]: More of a long comment over a full answer.
If this question does not have a solution in $\mathbb{C}$, then it cannot have a solution in $\mathbb{Z}$.  Therefore, I wrote the following Macaulay2 code to study the problem over $\mathbb{C}$:
R = QQ[r_0..r_3,s_0..s_3,t_0..t_3,u_0..u_3]
S = R[lambda]

M = matrix{{r_0,r_1,s_0,s_1},
           {r_2,r_3,s_2,s_3},
           {t_0,t_1,u_0,u_1},
           {t_2,t_3,u_2,u_3}}
L = lambda*id_(S^4)

D = det (M-L)
C = coefficients D

-- dot products of the matrices
d1 = r_0*r_2+r_1*r_3
d2 = s_0*s_2+s_1*s_3
d3 = t_0*t_2+t_1*t_3
d4 = u_0*u_2+u_1*u_3

-- determinants of the matrices
e1 = r_0*r_3-r_1*r_2
e2 = s_0*s_3-s_1*s_2
e3 = t_0*t_3-t_1*t_2
e4 = u_0*u_3-u_1*u_2

-- values of a's
a1 = e1 - d1
a2 = e2 - d2
a3 = e3 - d3
a4 = e4 - d4

T = QQ[first entries vars R|{w},MonomialOrder=>Eliminate 16]

-- Conditions to be eigenvalues 1.
f1 = sub((C_1)_(1,0)-(-1)^1*binomial(4,1),T)
f2 = sub((C_1)_(2,0)-(-1)^2*binomial(4,2),T)
f3 = sub((C_1)_(3,0)-(-1)^3*binomial(4,3),T)
f4 = sub((C_1)_(4,0)-(-1)^4*binomial(4,4),T)

-- w is value of trace of A

I = ideal(f1,f2,f3,f4,w-sub(a1+a3,T),1-sub(a1*a4-a2*a3,T))
G = gb I
selectInSubring(1,G)

J = ideal(f1,f2,f3,f4,w-sub(a1+a3,T),1+sub(a1*a4-a2*a3,T))
H = gb J
selectInSubring(1,H)

The code first computes the coefficients of the characteristic polynomial for M and the polynomials $f1,\dots,f4$ force those coefficients to be the coefficients of $(\lambda-1)^4$.  The $d1,\dots,d4$ are the dot products and the $e1,\dots,e4$ are the determinants of the $A_i$'s.  Then, the $a$'s are calculated as you described.
Finally, we make a new ring where $w$ is the value of the trace of $A$.  We make an ideal whose elements restrict the coefficients of the characteristic polynomial of $M$ to be correct, the determinant of $A$ to be $1$, and set $w$ to be the trace of $A$.  If we eliminate all variables except for $w$, then we get the possible values for the trace.
If the trace has only finitely many values, then one can hope that these cases can be studied individually.


TITLE: Scale values between -1 and 1 with a sum of 0
QUESTION [0 upvotes]: I need a function that scales array of values (from -inf to inf) between -1 and 1 with a sum of 0. The closest thing that comes to mind is the softmax function. But I don't know how to convert it to the form I need.

REPLY [0 votes]: Matti P.'s comment shows that there is no function  which always meets this condition.
If you have the data $x_1,x_2,\ldots,x_n$ with minimum $a$, mean $b$ and maximum $c$ with $a <b< c$ then $$f(x_i) = \dfrac{x_i - b}{\max(c-b,b-a)}$$ will transform the data linearly so it has mean of $0$, a maximum of $1$ or less and a minimum of $-1$ or more, and at least one of $1$ and $-1$ being achieved


TITLE: Does this gradient descent with asymptotically vanishing stepsize converge?
QUESTION [1 upvotes]: Suppose $f: \mathbb R^n \to \mathbb R$ is a $C^1$ convex function with gradient being Lipschitz continuous, i.e., $\|\nabla f(x) - \nabla f(y)\|_2 \le L\|x-y\|_2$. Consider the gradient update scheme
$$x_{k+1} = x_k - \alpha_k \nabla f(x_k),$$
where $\alpha_k = \alpha_k(\nabla f(x_k))$ means $\alpha_k$ is a function of $\nabla f(x_k)$ and $\alpha_k \in o(\nabla f(x_k)))$, i.e., $\alpha_k \to 0$ if $\nabla f(x_k) \to 0$. It might make no sense to consider vanishing stepsize but think this as a thought experiment.
I am wondering whether the sequence $\{f(x_k)\}$ will converge to $f(x_*)$. At first, I thought this was obvious, but then it occurred to me the reduction $f(x_k) - f(x_{k-1})$ could be arbitrarily small. It becomes less obvious for me.

REPLY [1 votes]: As a start, consider that at each iteration, we have the following inequality:
$$
\begin{align}
\|x^{(k+1)} - x^*\|_2^2 &= \|x^{(k)} - \alpha_k \nabla f(x^{(x)}) - x^*\|_2^2 \\
&= \|x^{(k)} - x^*\|_2^2 + \alpha_k^2 \|\nabla f(x^{(x)})\|_2^2 - 2\alpha_k \nabla f(x^{(x)})^T (x^{(k)} - x^*) \\
&\leq \|x^{(k)} - x^*\|_2^2 + \alpha_k^2 \|\nabla f(x^{(x)})\|_2^2 - 2\alpha_k (f(x^{(k)}) - f(x^*))
\end{align}
$$
We can rearrange and build this up inductively for $k = 1,\ldots, K$ so that
$$
2\sum_{k=0}^{K-1} \alpha_k (f(x^{(k)}  - f(x^*)) \leq \|x^{(0)} - x^*\|_2^2 + \sum_{k=0}^{K-1} \alpha_k^2 \|\nabla f(x^{(k)}\|_2^2
$$
and
$$
f(x^{(\hat{k})}) - f(x^*) \leq \frac{\|x^{(0)} - x^*\|_2^2}{2\sum_{k=0}^{K-1} \alpha_k} + \frac{L^2 \sum_{k=0}^{K-1} \alpha_k^2}{2\sum_{k=0}^{K-1} \alpha_k}
$$
where $x^{(\hat{k})}$ is the argminimizer of $f$ over all the iterates up through iteration $K$. So one thought would be that we need $\sum_{k=0}^{K-1} \alpha_k = \infty$ and also that $\sum_{k=0}^{K-1} \alpha_k^2 < \infty$.


TITLE: Exponential and power functions through two points
QUESTION [1 upvotes]: I have a problem where I'm asked to determine the constants of exponential and power functions that go through both points (5, 50) and (10, 1600). I have tried to solve them below, but would appreciate it if someone could check. Would also appreciate feedback on how I could optimize my notation, if anyone has any thoughts on that.

Exponential, i.e. $f(x) = c \cdot a^x$
$50 = c \cdot a^5 \\
1600 = c \cdot a^{10}
$
$
ln(50) = ln( c ) + 5ln(a) \\
ln(1600) = ln( c ) + 10ln(a)
$
$
ln(50)-ln(1600) = 5ln(a) - 10ln(a)
\Rightarrow ln(\frac{50}{1600}) = -5ln(a)
\Rightarrow ln(\frac{1}{32}) = -5ln(a)
\Rightarrow -ln(32) = -5ln(a)
\Rightarrow \frac{-ln(32)}{-5} = ln(a)
\Rightarrow e^{ln(a)} = e^{\frac{ln(32)}{5}}
= 2
$
$
f(x) = c \cdot 2^{x}
\Rightarrow 50 = c \cdot 2^{5}, 1600 = c \cdot 2^{10}
$
$
50 = 32c
\Rightarrow c = \frac{50}{32} = \frac{25}{16}
$
$
1600 = 1024c
\Rightarrow c = \frac{1600}{1024} = \frac{25}{16}
$
$
f(x) = \frac{25}{16}2^{x}
$

Power, i.e. $f(x) = c \cdot x^r$
$
50 = c \cdot 5^r \\
1600 = c \cdot 10^r
$
$
ln(50) = ln( c ) + rln(5) \\
ln(1600) = ln( c ) + rln(10)
$
$
ln(50) - ln(1600) = r(ln(5) - ln(10))
$
$
\frac{ln(50) - ln(1600)}{ln(5) - ln(10)} = r
\Rightarrow r = 5
$
$
50 = c \cdot 5^5
\Rightarrow c = \frac{2}{125}
$
$
1600 = c \cdot 10^5
\Rightarrow c = \frac{2}{125}
$
$
f(x) = \frac{2}{125}x^{5}
$

REPLY [1 votes]: The steps seem to be good. In both cases, you could divide your first equation by the second one (or vice versa) and then take ln on both sides. It would save you some time.


TITLE: Doesn't Young's modulus depends on length?
QUESTION [1 upvotes]: Similar questions have been already asked here and here, but I'm still confused. I think of a wire of a material, say aluminum, as formed by stacking layers of atoms. Suppose that the distance between layers at equilibrium is $r_0$, and that $\Delta r := r-r_0$ is the displacement from equilibrium. I suppose that the restoring force between two consecutive layers is $F = -K'\Delta r$; I neglect the interaction between distant layers.
I assume that $K'$ depends on the area $A$ of the layers as $K' = KA$. Hence, the force needed to stretch the wire is $F_t = KAN\Delta r$, where $N$ is the number of layers. We have that the initial length of the wire is $L_0 = Nr_0$ and the extension is $\Delta L = N\Delta r$. Therefore, Young's modulus $E$ should be $E = (F_t/A)/(\Delta L/L_0) = L_0K$.
In my derivation $K$ is the fundamental quantity, so $E$ should depend on the length of the sample, but I know that $E$ is the intrinsic property of the metal. What am I missing? It's hard to imagine that $K \propto \frac{1}{L_0}$.
Think of two wires of aluminum, the transversal area of both 1 mm$^2$, the length of the sample A 10 cm, and the length of the sample B 1 m. Suppose we stretch both by 1 cm, so $\Delta L/L_0 = $ 0.1 (A) and 0.01 (B). Since $E$ is constant, I have to apply more pressure to stretch (A); however, if $K$ were the fundamental quantity the force should be equal in both cases. The reason for the latter is that, even though the strain is different, in (A) the number of layers opposing to the force is fewer but $\Delta r/r_0 = \Delta L/L_0$ is larger, and in (B) the number of layers opposing to the force is larger but $\Delta r/r_0 = \Delta L/L_0$ is smaller; both effects offset, and the force is the same.
I'd appreciate any clarification.

REPLY [1 votes]: The forces in the layers do not add up. Essentially, you have a chain of springs - if you stretch the chain on both ends, the force in each spring is the same. Otherwise, the point between the first and the second spring would be puled towards the centre, since the force in that direction would be $N-1$ times the one pulling towards the end.
Forces do add up when the springs are in parallel -- you have correcty taken that into account by assumeing the force is proportional to the area.


text:
\begin{document}

\maketitle

\begin{abstract}
Motivated by surprisingly good generalization properties of learned deep neural networks in overparameterized scenarios and by the related double descent phenomenon, this paper analyzes the relation between smoothness and low generalization error in an overparameterized linear learning problem. We study a random Fourier series model, where the task is to estimate the unknown Fourier coefficients from equidistant samples. We derive exact expressions for the generalization error of both plain and weighted least squares estimators. We show precisely how a bias towards smooth interpolants, in the form of weighted trigonometric interpolation, can lead to smaller generalization error in the overparameterized regime compared to the underparameterized regime. This provides insight into the power of overparameterization, which is common in modern machine learning.
\end{abstract}

\begin{keywords}
 overparameterization, generalization error, weighted optimization, smoothness
\end{keywords}

\begin{AMS}
42A15, 65T40
\end{AMS}

\section{Introduction}
\input{sections/introduction}

\subsection{Main Contribution and Outline}
\input{sections/outline}
\subsection{Previous work on generalization and overparameterization}\label{sec:previous}
\input{sections/related_work}

\section{Formulation}\label{sec:formulation}
\input{sections/setup}

\section{Risk Analysis for Decaying Fourier Series Model in the Overparameterized Setting}\label{sec:overpara}
\input{sections/fourier}
\subsection{Asymptotic Rate of Weighted Min-norm Risk}
\input{sections/asymp}
\subsection{Concentration of Error}
\input{sections/highp}

\section{Risk Analysis in the Underparameterized Setting and Benefits of Overparameterization}\label{sec:underpara}
\input{sections/under}

\section{Experiments}\label{sec:exp}
\input{sections/exp_section}

\section{Discussion on Necessity of Randomness}\label{sec:diss}
\input{sections/discussion}

\section{Conclusion and Outlook}\label{sec:sum}
\input{sections/summary}

\section*{Acknowledgments}
\input{sections/acknowledge}

\appendix
\input{appendix/proof_of_lemmas}
\input{appendix/proof_of_theorems}
\input{appendix/exp_others}

\bibliographystyle{siamplain}
\bibliography{references}

\end{document}

config: arxiv


text:
\paragraph{Models}

\input{image/schematic_view}

Figure \ref{fig:schematic-view} shows a schematic view of the model considered in this study.
It consists of two types of components: \textit{aggregation} functions $g^{(t)}: \mathcal{X}^N\to \mathcal{X}^N$ that mix the representations of sample points and \textit{transformation} functions $b^{(t)}:\mathcal{X}^N \to \widehat{\mathcal{Y}}^N$ that make predictions from representations.
We specify a model by defining the set of aggregation and transformation functions at each iteration $t$, denoted by $\mathcal{G}^{(t)}$ and $\mathcal{B}^{(t)}$, respectively. If we use the same function classes $\mathcal{G}^{(t)}$ and $\mathcal{B}^{(t)}$ for all $t$, we shall omit the superscript $(t)$.
Typically, a transformation function $b\in \mathcal{B}^{(t)}$ is a broadcast of the same function, i.e., $b$ is of the form $b = (b_0, \ldots, b_0)$ for some $b_0:\mathcal{X}\to \widehat{\mathcal{Y}}$.
However, we do not assume this until necessary.
We define the hypothesis space $\mathcal{F}^{(t)}$ at the $t$-th iteration by
    $\mathcal{F}^{(t)} := \{b^{(t)}\circ g^{(t)} \circ \cdots \circ g^{(1)} \mid b^{(t)} \in \mathcal{B}^{(t)}, g^{(s)}\in \mathcal{G}^{(s)} (s \in [t])\}.$
Given $g^{(s)}\in \mathcal{G}^{(s)}$ selected at the $s=1, \ldots, t-1$ iterations, we choose $g^{(t)}\in \mathcal{G}^{(t)}$ and $b^{(t)}\in\mathcal{B}^{(t)}$ to construct a weak learner $f^{(t)}(X) := b^{(t)}(g^{(t)}(X^{(t-1)}))$ and update the representation $X^{(t)}:=g^{(t)}(X^{(t-1)})$. When $t=1$, we define $f^{(1)}(X) := b^{(1)}(X)$ and $X^{(1)} := X$. We do not select $g^{(1)}$, nor do we update the representation.
Algorithm \ref{alg:train} shows the overall training algorithm.


TITLE: the deformation of a fibration V.S. the deformation of the generic fiber
QUESTION [2 upvotes]: Let $X \to C$ be a flat family over a curve. A deformation of the fibration gives a deformation of the generic fiber $X_\eta$. Now my questions are the following.

If we have a deformation of the generic fiber, is there any way to ``lift" the deformation to the fibration?
A slightly weaker version: if we have a deformation of the generic fiber, is it possible to choose one model of $X \to C$ such that the deformation is induced by this fiberation.

Based on the answer given, let me add that a general fiber is rationally connected or even fano. And if you wish, the base is a rational curve. Also the total space should be smooth.

REPLY [3 votes]: The answer is no.
The following example is typical. Take a surface of general type $X$ which is obtained as
$X:=(C_1 \times C_2) /G$ where

$C_1$, $C_2$ are smooth curves
$G$ is a finite group acting faithfully on both $C_1$ and $C_2$ and freely on their product (the action is the diagonal one).
$C_i/G \cong \mathbb{P}^1$ and $f_i \colon C_i \to C_i/G$ is branched in three points.

(F. Catanese called these surfaces Beauville surfaces, there are many of them).
Then there are two natural isotrivial fibrations
$g_i \colon X \to C_i/G \cong \mathbb{P}^1$.
On the other hand, one proves that $X$ is a rigid scheme, so it has no abstract deformations at all. In particular no non-trivial deformation of the general fibre of $g_i$ can lift to a deformation of the fibration.


TITLE: $\sigma(Y)$-measurability in conditional expectation computation formulas
QUESTION [2 upvotes]: Let $X$ and $Y$ be $1$ dimensional random variables such that $(X,Y)$ has density $g_{(X,Y)}$. Let $h(x):\mathbf{R}\to \mathbf{R}$ be a borel function such that $h(X)$ is integrable. Then the conditional expectation $E(X \mid Y)$ can be written as a function $\eta(Y)$, where $$\eta:y \mapsto \int\limits_{\mathbf{R}} h(x) g_{X \mid Y}(x, y)\ dx,$$ where $$g_{X \mid Y}(x, y) = \begin{cases}
\dfrac{g_{(X, Y)}(x, y)}{g_Y(x)} &\text{ if } g_Y(x) > 0,\\
0 &\text{ otherwise}
\end{cases}$$ Why is $\eta(Y)$ $\sigma(Y)$-measurable? Why does $\int\limits_{\mathbf{R}} h(x) g_{X \mid Y}(x, y)\ dx$ even exist? Does it exist for every $y$ or just almost everywhere?
I'v read that $\sigma(Y)$-measurability follows from Fubini's theorem. I suppose it means that we use Fubini to a function $\phi:(x,y) \mapsto h(x) g_{X \mid Y}(x, y)$ and conclude that $\eta(y)$ is a borel function. But to use Fubini we need to know that $\phi$ is both borel and integrable (since $h(x)$ doesn't have to be positive). I see why it is borel, but not why it is integrable.
I'v got similar problem with the case of $X$,$Y$ being discrete. Denote $S_X$ set of atoms of $X$ and $P_X(x)=P(X=x)$. Why is $\sum_{x\in S_X} \frac{P_{(X,Y)}(x,Y)}{P_Y(Y)}$ (I guess we put $0$ when $P(Y=y)=0$)  $\sigma(Y)$-measurable?
Any help would be appreciated. I'm just starting with conditional expectation.

REPLY [1 votes]: First off there's a typo in your definition of the $g_{X \mid Y}(x, y)$. It should be $$g_{X \mid Y}(x, y) = \begin{cases}
\dfrac{g_{(X, Y)}(x, y)}{g_Y(y)} &\text{ if } g_Y(y) > 0,\\
0 &\text{ otherwise}
\end{cases}$$
Let $g_X$ denote the marginal density of $X$: $g(x)=\int g(x,y) dy$.
Since
$$\int \int |h(x) g(x,y)| dx dy = \int |h(x)| \int g(x,y) dy dx = \int |h(x)|g_X(x) dx =E(|h(X)|)<\infty $$
the function $(x,y)\mapsto h(x) g(x,y)$ is integrable.


text:
\section{Self-Parametrization}
\label{sec:selfparam}

In this section, we introduce our novel algorithm for adaptive parameter tuning.

\subsection{Overview of \Paramsheading{}}
\label{ssec:paramoverview}

The reachability algorithm from \sectref{ssec:ra_linsys}
depends on different \params{},
which we divide into:
\begin{itemize}
	\item \textbf{Time Step Size:}
		The propagation in~\eqref{eq:HRPR_start} can be applied to any series
		of $\Delta t_i$ adding up to $T$.
		Large $\Delta t$ speed up the computation, while small $\Delta t$ increase the precision.
	\item \textbf{\AppModPtextheading{}:}
		The tightness of the computed reachable sets
		also depends on parameters approximating the dynamics $\AppModP{}$,
		e.g., determining the precision of computing $e^{At}$.
		We introduce the operator $\incrOp{\AppModP{}}$
		which increments the parameters $\AppModP{}$ towards values
		which result in a tighter reachable set,
		as well as the operator $\resetOp{\AppModP{}}$
		which resets~$\AppModP{}$ to the coarsest setting.
	\item \textbf{Set Representation:}
		We denote the number of scalar values needed to describe a set by~$\SetReprP{}$.
		Let us introduce the operator $\decrOp{\SetReprP{}}$ which decreases $\SetReprP{}$.
		If $\SetReprP{}$ has reached its minimum, it returns $\decrOp{\SetReprP{}} = \SetReprP{}$.
		We denote the over-approximation of a set $\Sarb{}$
		by reducing its number of parameters
		to a desired value $\SetReprP{}$ by the operator $\redOp{\Sarb{}}{\SetReprP{}}$.
\end{itemize}

\subsection{Error measures}
\label{ssec:errors}

As we can only compute over-approximations,
we are interested in measuring the over-approximation error.
Let the reachable set $\HRset{}$ consist of summands, e.g.,
$\HRset{} = \HRset{}^{(1)} \oplus ... \oplus \HRset{}^{(\nu)}$,
as shown for a concrete implementation in \sectref{ssec:setprop}.
This assumption is valid for almost all approaches, see e.g.
\cite{Althoff2010a,Girard2005,Girard2008b,FreLeG2011,BFFPSV2018}.
We sum over all indices $\mathcal{E}$ representing exactly-computed terms
to obtain $\HReqset{} = \bigoplus_{i \in \mathcal{E}}^{\nu} \HRset{}^{(i)}$
and the remaining terms are summed to $\HRplusset{} = \bigoplus_{i \notin \mathcal{E}}^{\nu} \HRset{}^{(i)}$.
The same is done for $\PRset{}$, so that we obtain

\begin{align}
	\HRti{[0,\Delta t]} &= \HReqti{[0,\Delta t]} \oplus \HRplusti{[0,\Delta t]} \; ,
		\label{eq:HRtieqplus} \\
	\PRti{[0,\Delta t]} &= \PReqti{[0,\Delta t]} \oplus \PRplusti{[0,\Delta t]} \; .
		\label{eq:PRtieqplus}
\end{align}

We use this separation to realize a computationally efficient over-approximation
of the Hausdorff distance

\begin{align*}

	d_H (\Sarb{}_1, \Sarb{}_2)
		= \max &\Big\{ \sup_{x_1 \in \Sarb{}_1}
				\big( \, \inf_{x_2 \in \Sarb{}_2} \, \norm{x_1 - x_2} \,
			\big), \\
		&\quad \sup_{x_2 \in \Sarb{}_2}
			\big( \, \inf_{x_1 \in \Sarb{}_1} \norm{x_1 - x_2} \,
			\big) \Big\} \; .

\end{align*}

\begin{proposition} \label{prop:bloat}
Let $\Seq{} \subset \R{n}$ and $\Splus{} \subset \R{n}$
with ${0 \in \Splus{}}$ be non-empty compact, convex sets.
The Hausdorff distance between $\Seq{}$ and $\Stot{} := \Seq{} \oplus \Splus{}$

can be over-approximated by
\begin{equation} \label{eq:bloat}
	d_H(\Seq{},\Stot{}) \leq \errOp{\Splus{}}
		:= r \big( \boxOp{\Splus{}} \big) \; ,

\end{equation}
where $\boxOp{\Splus{}}$ is the box enclosure of $\Splus{}$
and $r(\cdot)$ returns the radius of the smallest hypersphere
centered at the origin enclosing its argument.

\end{proposition}

\begin{proof}
Since $\Stot{}$ encloses $\Seq{}$, we have

\begin{equation} \label{eq:dH_r}
	d_H(\Seq{},\Stot{})
		= \sup_{y \in \Stot{}} \big( \, \inf_{x \in \Seq{}} \, \norm{x - y} \big) \; .
\end{equation}

We also know that the difference between $\Stot{}$ and $\Seq{}$ is given by $\Splus{}$,
so that \eqref{eq:dH_r} can be equivalently written as
\begin{equation*}
	\sup_{y \in \Stot{}} \big( \, \inf_{x \in \Seq{}} \norm{x - y} \, \big)
		\overset{0 \in \Splus{}}{=} \sup_{x \in \Splus{}} \norm{x} = r ( \Splus{} ) \; .
\end{equation*}
Obviously, $r(\Splus{}) \leq r\big(\boxOp{\Splus{}}\big)$
and therefore $d_H(\Seq{},\Stot{}) \leq \errOp{\Splus{}}$.
\end{proof}

Let us introduce user-defined upper bounds for errors:
$\bloatHRmax{}$ for the error of the homogeneous solution $\HRset{}$ and
$\bloatPRmax{}$ for the error of the inhomogeneous solution $\PRset{}$.
Our approach ensures that these errors are not exceeded.

We now compute the errors of the $i$-th time step.
For the error $\bloatHRti{[t_i,t_{i+1}]}$ and $\bloatPRti{[t_i,t_{i+1}]}$
we use the split in~\eqref{eq:HRtieqplus} and apply the error measure from \propref{prop:bloat}:

\begin{align}
	\bloatHRti{[t_i,t_{i+1}]} &:= \errOp{\HRplusti{[t_i,t_{i+1}]}} \label{eq:bloatHRti} \\
		&\geq d_H \big( \HReqti{[t_i,t_{i+1}]},\HRti{[t_i,t_{i+1}]} \big) \; , \nonumber \\
	\bloatPRti{[t_i,t_{i+1}]} &:= \errOp{\PRplusti{[t_i,t_{i+1}]}} \label{eq:bloatPRti} \\
		&\geq d_H \big( \PReqti{[t_i,t_{i+1}]},\PRti{[t_i,t_{i+1}]} \big) \; . \nonumber
\end{align}

From \eqref{eq:HRPR_start}, we see that the computation of $\bloatHR{}$ does not depend on previous time intervals.
Contrary, the inhomogeneous solution $\PRti{[0,t_i]}$
accumulates over time, see \eqref{eq:HRPR_start},
and with it the error $\bloatPR{}$:

\begin{equation}
	\bloatPRti{[0,t_{i+1}]} = \bloatPRti{[0,t_i]} + \bloatPRti{[t_i,t_{i+1}]} \; ,
		\label{eq:bloatPRti_acc}
\end{equation}

where $\bloatPRti{[0,0]} = 0$.
Let us introduce a mild assumption for the errors $\bloatHR{}$ and $\bloatPR{}$,
which will be justified in \sectref{ssec:verass}.

\begin{assumption} \label{ass:bloatHRPR} (Convergence of $\bloatHR{}$ and $\bloatPR{}$)
We neglect floating-point errors so that $\bloatHRti{[t_i,t_{i+1}]} \rightarrow 0$
and $\bloatPRti{[t_i,t_{i+1}]} \rightarrow 0$ for $\Delta t_i \rightarrow 0$. \hfill $\square$
\end{assumption}

\assref{ass:bloatHRPR} is mild, since it practically holds
for all other current approaches, see e.g. \cite{Althoff2015a, FreLeG2011, BogFor2019}.
For further derivations we need the following definition.

\begin{definition} \label{def:superlinear} (Superlinear decrease)
	The set-based evaluation $f(\Sarb{}(t)) = \{ f(x) \, | \, x \in \Sarb{}(t) \}$
	is a continuous function $f: \R{n} \rightarrow \R{}$
	decreases superlinearly if
	\begin{equation*}
		\hspace{8pt} \forall \varphi \in (0,1):
			f\big(\Sarb{}\big([t,t + \varphi \Delta t]\big)\big)
				\subseteq \varphi \, f\big(\Sarb{}\big([t,t + \Delta t]\big)\big) \; .
		\hspace{5pt} \square
	\end{equation*}
\end{definition}
The following proposition addresses satisfying $\bloatPRmax{}$.

\begin{proposition} \label{prop:bloatPRtiadm}
Let the error $\bloatPRti{[t_i,t_{i+1}]}$
decrease superlinearly according to \defref{def:superlinear}.
For any given $\bloatPRmax{} > 0$, there exists a sequence of
time intervals $[t_i,t_{i+1}]$ so that
\begin{equation*}
	\sum_i \bloatPRti{[t_i,t_{i+1}]} \leq \bloatPRmax{} \; .
\end{equation*}
\end{proposition}

\noindent \textit{Proof.}
We define an admissible error $\bloatPRtiadm{i}$ for each step:
\begin{equation} \label{eq:bloatPRtiadm}

	\bloatPRti{[t_i,t_{i+1}]} \leq
	\bloatPRtiadm{i} := \frac{\bloatPRmax{} - \bloatPRti{[0,t_i]}}{T - t_i} \, \Delta t_i .
\end{equation}

For $\Delta t_i \rightarrow 0$, $\bloatPRtiadm{i}$ converges to 0,
as does $\bloatPRti{[t_i,t_{i+1}]}$ by \assref{ass:bloatHRPR}.
Moreover, $\bloatPRtiadm{i}$ decreases linearly in~$\Delta t_i$,
whereas $\bloatPRti{[t_i,t_{i+1}]}$ decreases superlinearly by assumption.
Hence, we can always obtain a $\Delta t_i$ so that the inequality in \eqref{eq:bloatPRtiadm} holds.
We sum each side in \eqref{eq:bloatPRtiadm} to
\begin{equation} \label{eq:bloatPRsumti}
	\bloatPRti{[0,t_i]} \leq \sum_{j=0}^{i-1} \bloatPRtiadm{j}
\end{equation}
which is subsequently used to bound $\bloatPRtiadm{i}$ and $\bloatPRmax{}$:
\begin{align*}
	\hspace{26pt}
	\bloatPRtiadm{i}
		&\overset{\eqref{eq:bloatPRtiadm}}{=} \big( \bloatPRmax{} - \bloatPRti{[0,t_i]} \big) \frac{\Delta t_i}{T - t_i} \\
		&\overset{\eqref{eq:bloatPRsumti}}{\leq} \big( \bloatPRmax{} - \sum_{j=0}^{i-1} \bloatPRtiadm{j} \big) \frac{\Delta t_i}{T - t_i} \\
	\Rightarrow \bloatPRmax{}
		&\geq \sum_{j=0}^{i-1} \bloatPRtiadm{j} + \underbrace{\frac{T - t_i}{\Delta t_i}}_{\geq 1} \bloatPRtiadm{i} \\
		&\geq \sum_{j=0}^{i} \bloatPRtiadm{j} \geq \sum_{i} \bloatPRti{[t_i, t_{i+1}]} \; .
	\hspace{26pt}
	\square
\end{align*}

The Minkowski sum in~\eqref{eq:HRPR_start} typically increases the representation size of the resulting set.
To counteract this growth, we enclose~$\PRset{}$ in~\eqref{eq:HRPR_start}
by a set specified by less parameters which over-approximates the original set
by the error $\bloatSet{}$ accumulating
as the error $\bloatPR{}$ of $\PRset{}$:

\begin{align}
	&\bloatSetti{[0,t_{i+1}]} = \bloatSetti{[0,t_i]} + \bloatSetti{[t_i,t_{i+1}]} \; ,
		\label{eq:bloatSetti_prop} \\
	&\text{with} \quad \bloatSetti{[0,0]} = 0 \; . \nonumber
\end{align}
Similarly to \propref{prop:bloatPRtiadm},
we define an admissible error $\bloatSettiadm{i}$:
\begin{equation} \label{eq:bloatSettiadm}
	\bloatSetti{[t_i,t_{i+1}]} \leq \bloatSettiadm{i} := \frac{\bloatSetmax{} - \bloatSetti{[0,t_i]}}{T - t_i} \, \Delta t_i \; .
\end{equation}

If we do not over-approximate the set representation
in the $i$-th time step, we have $\bloatSetti{[t_i,t_{i+1}]} = 0$.

\subsection{Adaptive Parameter Tuning}
\label{ssec:tuning}

We now present our generic framework for adaptive parameter tuning
in \algref{alg:full}.
The two subroutines, \algref{alg:postTSTT} and \algref{alg:propInhom},
will be presented thereafter.
First, we initialize $\Delta t$ and the scaling factor $\mu$ (\lineref{alg:full:inits}),
as well as the accumulating errors $\bloatPR{}$ and $\bloatSet{}$
(\lineref{alg:full:initbloat})
for the first iteration of the main loop
(\linerangeref{alg:full:mainloop_start}{alg:full:mainloop_end}).
In every iteration, we first obtain the parameters
$\Delta t_i$ and $\AppModPidx{i}$ (\lineref{alg:full:postTSTT})
from \algref{alg:postTSTT}.
Then, we calculate the reachable sets
$\HRti{[0,\Delta t_i]}$ and $\PRti{[0,\Delta t_i]}$ (\lineref{alg:full:HRPR0Deltati}),
which are subsequently used to obtain $\HRti{[t_i,t_{i+1}]}$
and $\PRti{[0,t_{i+1}]}$ (\lineref{alg:full:HRPR_prop}).
In \algref{alg:propInhom}, we obtain the parameters $\SetReprPidx{i}$,
which are used to recalculate $\PRti{[0,t_{i+1}]}$ (\lineref{alg:full:propInhom}).
At the end of each step, we add the homogeneous and inhomogeneous solution
to obtain the reachable set $\Rti{[t_i, t_{i+1}]}$ (\lineref{alg:full:Rti}).
Finally, after the calculation of the reachable set for each time interval,
the reachable set of the whole time horizon $\Rti{[0,T]}$
is obtained by unifying partial sets (\lineref{alg:full:R0T}).

\begin{theorem} \label{thm:alg:full}
\algref{alg:full} terminates and the overall error
stays below a user-defined error bound $\bloatmax{} \in \R{+}$,
assuming the reduction of the set representation in each step is optional.
\end{theorem}

\FloatBarrier

\begin{algorithm}[h!tb]
	\caption{Fully automated parameter tuning} \label{alg:full}
	\textbf{Input:} $\bloatHRmax{}, \bloatPRmax{}, \bloatSetmax{}, T$

	\textbf{Output:} $\Rti{[0,T]}$
	\begin{algorithmic}[1]
		\State $t \gets 0, i \gets 0$
		\State $\factor{} \gets 0.9, \Delta t_{-1} \gets T \, \factor{}$
			\label{alg:full:inits}
		\State $\bloatPRti{[0,0]} \gets 0$, $\bloatSetti{[0,0]} \gets 0$
			\label{alg:full:initbloat}
		\While{$t < T$}
			\label{alg:full:mainloop_start}
			\State $\Delta t_i, \AppModPidx{i}, \bloatPRti{[0,t_{i+1}]} \gets$ \algref{alg:postTSTT}
				\label{alg:full:postTSTT}
			\State calc. $\HRti{[0,\Delta t_i]}, \PRti{[0,\Delta t_i]}$ using $\Delta t_i$, $\AppModPidx{i}$
				\label{alg:full:HRPR0Deltati}
			\State calc. $\HRti{[t_i,t_{i+1}]}, \PRti{[0,t_{i+1}]}$ acc. to \eqref{eq:HRPR_start}
				\label{alg:full:HRPR_prop}
			\State $\PRti{[0,t_{i+1}]}, \bloatSetti{[0,t_{i+1}]} \gets$ \algref{alg:propInhom}
				\label{alg:full:propInhom}
			\State $\Rti{[t_i, t_{i+1}]} = \HRti{[t_i,t_{i+1}]} \oplus \PRti{[0,t_{i+1}]}$
				\label{alg:full:Rti}
			\State $t \gets t + \Delta t_i$, $i \gets i+1$
				\label{alg:full:increaset}
		\EndWhile \label{alg:full:mainloop_end}
		\State $\Rti{[0,T]} \gets \bigcup_{j=0}^{i-1} \Rti{[t_j, t_{j+1}]}$
			\label{alg:full:R0T}
	\end{algorithmic}
\end{algorithm}

\begin{proof}
We first show that the algorithm terminates.
The while-loop in \algref{alg:postTSTT} always terminates if
\begin{equation*}
	\forall i: \bloatPRti{[t_i, t_{i+1}]} \leq \bloatPRtiadm{i}
	\; , \; \bloatHRti{[t_i, t_{i+1}]} \leq \bloatHRmax{}	\; .
\end{equation*}
The first inequality can be satisfied as shown in the proof of \propref{prop:bloatPRtiadm}.
From \lineref{alg:postTSTT:decreaseDeltat} in \algref{alg:postTSTT}
and under \assref{ass:bloatHRPR}, we have
$\forall i: \Delta t_i \rightarrow 0 \Rightarrow \bloatHRti{[t_i,t_{i+1}]} \rightarrow 0$.
Thus, every bound $\bloatHRmax{}$ is satisfiable.
The while-loop in \algref{alg:propInhom} terminates as we will
either exceed the admissible error bound $\bloatSettiadm{i}$
during the continuous reduction or exit the loop
if the set parameters $\SetReprP{}$ have been reduced as much as possible.
Finally, the main loop (\linerangeref{alg:full:mainloop_start}{alg:full:mainloop_end})
terminates as the time~$t$ monotonically increases (\lineref{alg:full:increaset}),
eventually reaching~$T$.

To prove that the error stays below a user-defined bound,
we split the error $\bloatmax{}$
in $\bloatmax{} = \bloatHRmax{} + \bloatPRmax{} + \bloatSetmax{}$.
All individual bounds
are satisfiable:
We have already shown the satisfiability of any $\bloatHRmax{}$
in the beginning of this proof.
\propref{prop:bloatPRtiadm} shows that any limit $\bloatPRmax{}$ is satisfiable.
Lastly, any bound~$\bloatSetmax{}$ can be satisfied since
we can choose to not over-approximate the set representation.
\end{proof}

\noindent We now present two algorithms performing the adaptive parameter tuning:
As an overview, \algref{alg:postTSTT} adapts
the parameters $\Delta t_i$ and $\AppModPidx{i}$,
while \algref{alg:propInhom} adapts the parameters $\SetReprPidx{i}$
concurrently to the propagation of $\PRset{}$.

We first present \algref{alg:postTSTT}:
As the main idea, every $\AppModP{}$ is checked for an iteratively decreasing $\Delta t_i$
until the error bounds $\bloatHRmax{}$ and $\bloatPRtiadm{i}$ are satisfied.
Initially, we increase the time step size by division with the factor $\factor{}$
(\lineref{alg:postTSTT:startDeltat}).
Furthermore, we reset~$\AppModPidx{i}$ to its coarsest setting (\lineref{alg:postTSTT:startDeltat})
and calculate the admissible error $\bloatPRtiadm{i}$ (\lineref{alg:postTSTT:bloatPRtiadm}).
In the loop (\linerangeref{alg:postTSTT:loop_start}{alg:postTSTT:loop_end}),
we increment $\AppModPidx{i}$ (\lineref{alg:postTSTT:incrAppModP})
and calculate the errors $\bloatHRti{[t_i,t_{i+1}]}$ and $\bloatPRti{[t_i,t_{i+1}]}$
based on the error sets $\HRplusti{[t_i,t_{i+1}]}$ and $\PRplusti{[t_i,t_{i+1}]}$
(\linerangeref{alg:postTSTT:errors_start}{alg:postTSTT:errors_end}).
These errors are then compared to their respective error bounds
(\lineref{alg:postTSTT:loop_end}).
If $\AppModPidx{i}$ reaches $\AppModPmax{}$ (\lineref{alg:postTSTT:AppModPmax}),
we decrease $\Delta t_i$, reset $\AppModPidx{i}$ (\lineref{alg:postTSTT:decreaseDeltat}),
and recalculate the admissible bound $\bloatPRtiadm{i}$
(\lineref{alg:postTSTT:updatebloatPRtiadm})
before restarting the loop (\lineref{alg:postTSTT:continue}).
After the loop is finished, the accumulated error $\bloatPRti{[0,t_{i+1}]}$
is computed (\lineref{alg:postTSTT:bloatPRti_acc}).

\FloatBarrier

\begin{algorithm}[h!tb]
	\caption{Adapt values for $\Delta t, \AppModP{}$} \label{alg:postTSTT}
	\textbf{Input:} $\bloatHRmax{}, \bloatPRmax{}, \bloatPRti{[0,t_i]}, \Delta t_{i-1}, \factor{}, T$

	\textbf{Output:} $\Delta t_i, \AppModPidx{i}, \bloatPRti{[0,t_{i+1}]}$
	\begin{algorithmic}[1]
		\State $\Delta t_i \gets \frac{\Delta t_{i-1}}{\factor{}}$, $\resetOp{\AppModPidx{i}}$
			\label{alg:postTSTT:startDeltat}
		\State calc. $\bloatPRtiadm{i}$ acc. to \eqref{eq:bloatPRtiadm}
			\label{alg:postTSTT:bloatPRtiadm}
		\State \textbf{do}
			\label{alg:postTSTT:loop_start}
			\State $\quad$ $\incrOp{\AppModPidx{i}}$
				\label{alg:postTSTT:incrAppModP}
			\State $\quad$ \textbf{if} $\AppModP{} \geq \AppModPmax{}$
				\label{alg:postTSTT:AppModPmax}
				\State $\qquad$ $\Delta t_i \gets \Delta t_i \factor{}$, $\resetOp{\AppModPidx{i}}$
					\label{alg:postTSTT:decreaseDeltat}
				\State $\qquad$ calc. $\bloatPRtiadm{i}$ acc. to \eqref{eq:bloatPRtiadm}
					\label{alg:postTSTT:updatebloatPRtiadm}
				\State $\qquad$ \textbf{continue}
					\label{alg:postTSTT:continue}
			\State $\quad$ \textbf{end if}
			\State $\quad$ calc. $\HRplusti{[t_i,t_{i+1}]}, \bloatHRti{[t_i, t_{i+1}]}$
				\label{alg:postTSTT:errors_start}
			\State $\quad$ calc. $\PRplusti{[t_i,t_{i+1}]}, \bloatPRti{[t_i, t_{i+1}]}$
				\label{alg:postTSTT:errors_end}
		\State \textbf{while} $\bloatHRti{[t_i, t_{i+1}]} > \bloatHRmax{}
			\wedge \bloatPRti{[t_i, t_{i+1}]} > \bloatPRtiadm{i}$
				\label{alg:postTSTT:loop_end}
		\State calc. $\bloatPRti{[0,t_{i+1}]}$ acc. to \eqref{eq:bloatPRti_acc}
			\label{alg:postTSTT:bloatPRti_acc}
	\end{algorithmic}
\end{algorithm}

\FloatBarrier

The adaptation of~$\SetReprP{}$ is shown in \algref{alg:propInhom}:
In order to decrease the computation time, the number of parameters
describing $\PRset{}$ is iteratively reduced from a high-precision representation
towards lower precision.
First, we calculate the admissible error~$\bloatSettiadm{i}$
(\lineref{alg:propInhom:bloatSettiadm}) for the given~$\Delta t_i$.
The operator $\paramOp{\SetReprP{}}$ extracts
the number of stored parameters~$\SetReprPidx{i}$
from $\PRti{[0,t_{i+1}]}$ (\lineref{alg:propInhom:readSetReprP}).
Inside the loop (\linerangeref{alg:propInhom:loop_start}{alg:propInhom:loop_end}),
we iteratively decrease $\SetReprPidx{i}$ (\lineref{alg:propInhom:decrSetReprP})
and over-approximate $\PRti{[0,t_{i+1}]}$
by reducing the number of stored parameters to $\SetReprPidx{i}$
(\lineref{alg:propInhom:reduce}).
From the difference between the original set and the set over-approximated by reduction,
we calculate the induced error~$\bloatSetti{[t_i,t_{i+1}]}$ (\lineref{alg:propInhom:bloatSetti})
and compare it to the admissible error (\lineref{alg:propInhom:loop_end}).
After the loop,
the accumulated error for the set representation $\bloatSetti{[0,t_{i+1}]}$
is computed (\lineref{alg:propInhom:bloatSetti_prop}).

\FloatBarrier

\begin{algorithm}[h!tb]
	\caption{Adapt values for $\SetReprP{}$} \label{alg:propInhom}
	\textbf{Input:} $\bloatSetmax{}, \bloatSetti{[0,t_i]}, \PRti{[0,t_{i+1}]}, \Delta t_i, T$

	\textbf{Output:} $\PRti{[0,t_{i+1}]}, \bloatSetti{[0,t_{i+1}]}$
	\begin{algorithmic}[1]
		\State calc. $\bloatSettiadm{i}$ acc. to \eqref{eq:bloatSettiadm}
			\label{alg:propInhom:bloatSettiadm}
		\State $\SetReprPidx{i} \gets \paramOp{\PRti{[0,t_{i+1}]}}$
			\label{alg:propInhom:readSetReprP}
		\State \textbf{do}
			\label{alg:propInhom:loop_start}
			\State $\quad$ $\decrOp{\SetReprPidx{i}}$
				\label{alg:propInhom:decrSetReprP}
			\State $\quad$ $\redOp{\PRti{[0,t_{i+1}]}}{\SetReprPidx{i}}$
				\label{alg:propInhom:reduce}
			\State $\quad$ calc. $\bloatSetti{[t_i,t_{i+1}]}$
				\label{alg:propInhom:bloatSetti}
		\State \textbf{while} $\bloatSetti{[t_i,t_{i+1}]} < \bloatSettiadm{i}
			\vee \decrOp{\SetReprP{}} = \SetReprP{}$
			\label{alg:propInhom:loop_end}
		\State calc. $\bloatSetti{[0,t_{i+1}]}$ acc. to \eqref{eq:bloatSetti_prop}
			\label{alg:propInhom:bloatSetti_prop}
	\end{algorithmic}
\end{algorithm}

\FloatBarrier

The presented framework for adaptive parameter tuning
can be applied to any reachability algorithm.
In the next section, we will provide an example implementation
and prove the assumptions underlying \thmref{thm:alg:full}.


TITLE: What is larger? Graham's number or Googolplexian?
QUESTION [2 upvotes]: See YouTube or wikipedia for the defination of Graham's number.
A Googol is defined as $10^{100}$.
A Googolplex is defined as $10^{\text{Googol}}$.
A Googolplexian is defined as $10^{\text{Googolplex}}$.
Intuitively, it seems to me that Graham's number is larger (maybe because of it's complex definition).
Can anybody prove this?

REPLY [11 votes]: Googolplex can be bounded from above like a tower of exponents, so $$10^{10^{100}} < (3^3)^{10^{100}} = 3^{3\times 10^{100}} <3^{10^{101}} < 3^{(3^3)^{101}} = 3^{3^{303}} < 3^{3^{3^{3^3}}}$$ In the last step, we have used the fact that $303$ is much,much smaller than $3^{27}$. Now, take the Googolplexian.We can thus, easily check that,  $$10^{10^{10^{100}}} < (3^3)^{10^{10^{100}}} < 3^{3^{3^{3^{3^3}}}}$$ So, Googolplexian is much smaller than a tower of exponents of $3$'s of length $6$, or in other words Googolplexian is less than $3\uparrow \uparrow6$.(using Knuth's up-arrow notation.)

Now, compare this with just the first layer of Graham's number,i.e., $3\uparrow \uparrow \uparrow \uparrow 3$. Hope it helps.


TITLE: Show that $1 \le \sum_{n=1}^\infty\frac{1}{n!} \le 2$
QUESTION [2 upvotes]: How can I prove that $\sum_{n=1}^\infty\frac{1}{n!}$ is limited this way $1 \le \sum_{n=1}^\infty\frac{1}{n!} \le 2$. I know that the lower bound is obvious because the sequence of the partial sums is monotone in a crescent way and the first term is $\frac{1}{1!}=1$, for the upper bound I think that maybe $\lim s_n = 2$ with $(s_n)$ being the sequence of partial sums of $\sum_{n=1}^\infty\frac{1}{n!}$, since this sequence is convergent by the Ratio Test, but how can I prove this?

REPLY [4 votes]: Note that for $n\geq1$ we have that
$$2^{n-1}\leq n!$$
so
$$\frac{1}{2^{n-1}}\geq\frac{1}{n!}$$
and then
$$\sum_{n=0}^\infty\frac{1}{2^n}\geq\sum_{n=1}^\infty\frac{1}{n!}.$$


TITLE: Basic theorem of multivariable calculus
QUESTION [5 upvotes]: Consider the following theorem:

It appears in many different places but always with both conditions stated:
One: $g_i(0,...,0) = {\partial f\over \partial x_i}(0,...,0)$
Two: $f(x_1,...,x_n) = \sum_i x_i g_i$
But as far as I can tell the first one follows from the second one. Consider the case in two dimensions: Assume $f(x,y) = xg(x,y) + yh(x,y)$ where $f,g,h$ are smooth. Then
$$ {\partial f \over \partial x } (x,y) = g(x,y) + x {\partial g \over \partial x } (x,y) + y {\partial h \over \partial x } (x,y)$$
and then
$${\partial f \over \partial x } (0,0) = g(0,0)$$
The same argument works for $n$ dimensions. What am I missing here? (Surely if one really did follow from two then only two would be stated?)
If "two" then of course the $g_i$ are already shown to exist.

REPLY [2 votes]: HINT: This is also called Hadamard's lemma. One of the most simple proofs involves connecting the origin and $x$ with a straight line and representing the
restriction of $f$ on that line via fundamental theorem of calculus (just because restriction is a function on the segment in $\mathbb{R}$)


TITLE: Let $X$ be the class of all classical Laver tables. Is $HS(X)=S(X)$?
QUESTION [6 upvotes]: Let $A_{n}=(\{1,\ldots,2^{n}\},*_{n})$ be the algebra defined by
$x*_{n}1=x+1\mod 2^{n}$ and $x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$ for all $x,y,z\in\{1,\ldots,2^{n}\}$. Suppose that $X$ is a subalgebra of some $A_{n}$ and $\simeq$ is a congruence on $X$. Then does there necessarily exist some $m$ along with some embedding $i:(X/\simeq)\rightarrow A_{m}$?
If so, then for all $n$, let $t_{n}$ be the least natural number $m$ such that whenever $X$ is a subalgebra of $A_{n}$ and $\simeq$ is a congruence on $X$, then there is some embedding $i:X/\simeq\rightarrow A_{m}$. Then what are some bounds on $t_{n}$? Or what is the exact value of $t_{n}$?

REPLY [3 votes]: It is known that if $X$ is a cyclic subalgebra of $A_n$ and $\simeq$ is a congruence on $X$, then $X/\simeq$ is isomorphic to $A_m$ for some $m\leq n$. See Propositions 1.6 and 1.21 of Chapter X of Braids and Self-Distributivity by Dehornoy for the proof.
I don't think it is known whether the result is true for arbitrary subalgebras $X\leq A_n$. I experimented with $A_3$ and $A_4$ using UACALC, and could not find any counterexamples.


TITLE: How would I find the solution of explicit MPC with piecewise u?
QUESTION [0 upvotes]: If I want to use this kind of system model
x(k+1)=$A$x(k)+$\overbrace{[\Phi_1\ \Phi_2]}^{B}\begin{bmatrix}
u(k)\\
u(k+1)\\
\end{bmatrix}$
(Assume that the input is linearly interpolated between sample times) to solve the cost function
$J(k) = \min_u \sum_{j=1}^{N_p-1} \|x(k+j|k)\|_{Q_i}^2  +  \sum_{j=0}^{N_c-1} \|u(k+j)\|_{P_i}^2$
by using explicit MPC.
\begin{equation}
\begin{aligned}
\begin{bmatrix}
x(k+1|k)\\
x(k+2|k) \\
\vdots \\
\vdots \\
\vdots \\
x(k+N_p-1|k)\\
x(k+N_P|k) \\
\end{bmatrix} &= \overbrace{\begin{bmatrix}
 A\\
 A^2\\
 A^3\\
 \vdots \\
 A^{N_p}
 \end{bmatrix}}^{M_x}x(k)+\overbrace{\begin{bmatrix}
 B &0    &\cdots   & 0\\
 AB & B  & \cdots & 0\\
 \vdots & \vdots & \ddots &\vdots \\
 A^{N_{p}-1}B & A^{N_{p}-2}B & \cdots  & A^{N_{p}-N_{c}}B\end{bmatrix}}^{M_u}\begin{bmatrix}
u(k|k)\\
u(k+1|k) \\
u(k+1|k) \\
u(k+2|k) \\
\vdots \\
\vdots \\
u(k+N_c-1|k)\\
u(k+N_c-1|k)\\
u(k+N_c|k) \\
\end{bmatrix}\\
\end{aligned}
\end{equation}
\begin{equation}
\begin{aligned}
\label{Kostenfunktion}
\mathbf{H}&=\mathbf{M}_{u}^{T}\mathbf{Q}\mathbf{M}_{u}+\mathbf{P}\\
\mathbf{f}^T&=-\mathbf{M}_{u}^{T}\mathbf{Q}(-\mathbf{M}_{x}x_{k})\\
\mathbf{u}&=-inv(\mathbf{H})*\mathbf{f}\\
\end{aligned}
\end{equation}
should I still choose the first $u=[1\ 0\ 0\ 0... 0]^T\mathbf{u}$ as optimal input other  $u=[1\ 1\ 0\ 0... 0]^T\mathbf{u}$ during the optimization?

REPLY [1 votes]: You could do a coordinate transformation such that it could be written into a more standard form. For your original system I use the following notation
$$
x[k+1] = A\,x[k] + B_1\,u[k] + B_2\,u[k+1] \tag{1}
$$
and the new coordinates are defined as
$$
z[k] = x[k] - B_2\,u[k]. \tag{2}
$$
Increasing the index in $(2)$ and substituting in $(1)$ gives
$$
z[k+1] = A\,x[k] + B_1\,u[k]. \tag{3}
$$
Solving $(2)$ for $x[k]$ and substituting that into $(3)$ gives the following standard form state space model
\begin{align}
z[k+1] &= A\,(z[k] + B_2\,u[k]) + B_1\,u[k], \tag{4a} \\
 &= A\,z[k] + (\underbrace{A\,B_2 + B_1}_{B})\,u[k]. \tag{4b}
\end{align}
The cost function now has to be written in terms of $z[k]$ instead of $x[k]$
$$
J(k) = \min_u \sum_{j=1}^{N_p-1} \|z[k+j|k] + B_2\,u[k+j]\|_{Q_i}^2  +  \sum_{j=0}^{N_c-1} \|u[k+j]\|_{P_i}^2, \tag{5}
$$
where the terms in the first summation can also be written as
\begin{align}
\|z[k+j|k] + B_2\,u[k+j]\|_{Q_i}^2 &= (z[k+j|k] + B_2\,u[k+j])^\top Q_i\,(z[k+j|k] + B_2\,u[k+j]), \\
 &= z[k+j|k]^\top Q\,z[k+j|k] + 2\,z[k+j|k]^\top N\,u[k+j] + u[k+j]^\top R\,u[k+j],
\end{align}
with $Q = Q_i$, $N = Q_i\,B_2$ and $R = B_2^\top Q_i\,B_2$.