text:
\begin{document}

\begin{abstract}
In \cite{sa} the third author of this paper presented two conjectures on the additive decomposability of the sequence of ''smooth'' (or ''friable'') numbers. Elsholtz and Harper \cite{eh} proved (by using sieve methods) the second (less demanding) conjecture. The goal of this paper is to extend and sharpen their result in three directions by using a different approach (based on the theory of $S$-unit equations).
\end{abstract}

\maketitle

\section{Introduction}

$\A,\B,\C,\hdots$ denote (usually infinite) sets of non-negative integers, and their counting functions are denoted by $A(X),B(X),C(X),\hdots$ so that e.g.
$$
A(X)=|\{a:a\leq X,\ a\in\A\}|.
$$
The set of the positive integers is denoted by $\N$, and we write $\N\cup\{0\}=\N_0$. The set of rational numbers is denoted by $\Q$.

We will need
\begin{defi}
\label{defi1}
Let $\G$ be an {\rm additive} semigroup and $\A,\B,\C$ subsets of $\G$ with
\begin{equation}
\label{eq11}
|\B|\geq 2,\ \ \ |\C|\geq 2.
\end{equation}
If
\begin{equation}
\label{eq12}
\A=\B+\C\ (=\{b+c:b\in\B,\ c\in\C\})
\end{equation}
then \eqref{eq12} is called an {\rm additive decomposition} or briefly {\rm a-decomposition} of $\A$, while if a {\rm multiplication} is defined in $\G$ and \eqref{eq11} and
\begin{equation}
\label{eq13}
\A=\B\cdot\C\ (=\{bc:b\in\B,\ c\in\C\})
\end{equation}
hold then \eqref{eq13} is called a {\rm multiplicative decomposition} or briefly {\rm m-decomposition} of $\A$.
\end{defi}

In \cite{ost1} and \cite{ost2} H.-H. Ostmann introduced some definitions concerning additive properties of sequences of non-negative integers and studied some related problems. The most interesting definitions are:

\begin{defi}
\label{defi2}
A finite or infinite set $\A$ of non-negative integers is said to be {\rm a-reducible} if it has an {\rm additive decomposition}
$$
\A=\B+\C\ \ \ \text{with}\ \ \ |\B|\geq 2,\ |\C|\geq 2
$$
(where $\B\subset\N_0$, $\C\subset\N_0$). If there are no sets $\B,\C$ with these properties then $\A$ is said to be {\rm a-primitive} or {\rm a-irreducible}.
\end{defi}

(More precisely, Ostmann used the terminology "reducible", "primitive", "irreducible" without the prefix a-. However, since we will study both additive properties and their multiplicative analogs thus to distinguish between them we will use a prefix a- in the additive case and a prefix m- in the multiplicative case.)

\begin{defi}
\label{defi3}
Two sets $\A,\B$ of non-negative integers are said to be {\rm asymptotically equal} if there is a number $K$ such that $\A\cap[K,+\infty)=\B\cap [K,+\infty)$ and then we write $\A\sim\B$.
\end{defi}

\begin{defi}
\label{defi4}
An infinite set $\A$ of non-negative integers is said to be {\rm totally a-primitive} if every $\A'$ with $\A'\subset \N_0$, $\A'\sim\A$ is {\rm a-primitive}.
\end{defi}

The multiplicative analogs of Definitions \ref{defi2} and \ref{defi4} are:

\begin{defi}
\label{defi5}
If $\A$ is an infinite set of {\rm positive} integers then it is said to be {\rm m-reducible} if it has a {\rm multiplicative decomposition}
$$
\A=\B\cdot\C\ \ \ \text{with}\ \ \ |\B|\geq 2,\ |\C|\geq 2
$$
(where $\B\subset\N$, $\C\subset\N$). If there are no such sets $\B,\C$ then $\A$ is said to be {\rm m-primitive} or {\rm m-irreducible}.
\end{defi}

\begin{defi}
\label{defi6}
An infinite set $\A\subset\N$ is said to be {\rm totally m-primitive} if every $\A'\subset \N$ with $\A'\sim\A$ is {\rm m-primitive}.
\end{defi}

Many papers have been written on the existence or non-existence of a-decompositions and m-decompositions, resp., of certain special sequences; surveys of results of this type are presented in \cite{el, eh, hs1, hs3}. In \cite{sa} the third author of this paper presented two related conjectures (we adjust the original notation and terminology to match better to the ones used by Elsholtz and Harper who have proved related results in \cite{eh} later):

\begin{defi}
\label{defi7}
Denote the greatest prime factor of the positive integer $n$ by $p^+(n)$. Then $n$ is said to be smooth (or friable) if $p^+(n)$ is ''small'' in terms of $n$. More precisely, if $y=y(n)$ is a monotone increasing function on $\N$ assuming positive values and $n\in\N$ is such that $p^+(n)\leq y(n)$, then we say that $n$ is $y$-smooth, and we write $\F_y$ ($\F$ for ''friable'') for the set of all $y$-smooth positive integers.
\end{defi}

We quote \cite{sa} (using a slightly different notation):

\vskip.2cm

\noindent
''{\bf Conjecture A.} {\sl If $0<\varepsilon<1$,
$$
y(n)=n^\varepsilon,
$$
the set $\F_y\subset\N$ is defined by
$$
\F_y=\{n:n\in\N, p^+(n)\leq y(n)=n^\varepsilon\}
$$
and $\F_y'\subset\N$ is a set such that
$$
\F_y'\sim \F_y,
$$
then there are no sets $\A,\B\subset\N$ with $|\A|,|\B|\geq 2$ and
$$
\A+\B=\F_y'.
$$
}

\noindent
(...) this seems to be very difficult, but, perhaps, the ternary version of the problem can be settled:

\vskip.2cm

\noindent
{\bf Conjecture B.} {\sl If $\F_y$ and $\F_y'$ are defined as in Conjecture A, then there are no $\A,\B,\C\in\N$ with $|\A|,|\B|,|\C|\geq 2$ and
$$
\A+\B+\C=\F_y'.''
$$
}

Elsholtz and Harper (see Corollary 2.2 in \cite{eh}) proved Conjecture B for all small $\varepsilon>0$:

\vskip.2cm

\noindent
{\bf Theorem A.} {\sl There exists a large absolute constant $D>0$, and a small absolute constant $\kappa>0$, such that the following is true. Suppose $y(n)$ is an increasing function such that
\begin{equation}
\label{eq14}
(\log n)^D\leq y(n)\leq n^\kappa\ \ \ \text{\sl for large}\ n,
\end{equation}
and such that
$$
y(2n)\leq y(n)(1+(100\log y(n))/\log n).
$$
Then a ternary decomposition
$$
\A+\B+\C\sim\F_y',
$$
where $\A,\B$ and $\C$ contain at least two elements each, does not exist.}

\vskip.2cm

(This proves Conjecture B for $0<\varepsilon\leq\kappa$.)

In \cite{eh} first they proved ''an additive irreducibility theorem for sets that need not be well controlled by the sieve'' and then they deduced Theorem A from this theorem. In this paper our goal is to extend and sharpen their result in three directions: we will consider the decomposability of sets $\F_y'\sim\F_y$ with $y(n)$ smaller than the lower bound in \eqref{eq14}; in this case we will be able to also attack the more difficult problem of binary decomposition considered in Conjecture A; we will also study the multiplicative analog of the problem. While in \cite{eh} mostly sieve methods are used, here we will apply a completely different approach, namely, the crucial tool used by us will be the theory of $S$-unit equations.

Here we will prove the following two theorems:

\begin{theorem}
\label{thm1}
If $y(n)$ is an increasing function with $y(n)\to\infty$ and
\begin{equation}
\label{eq15}
y(n)<2^{-32}\log n\ \ \ \text{for large}\ n,
\end{equation}
then the set $\F_y$ is totally {\rm a-primitive}.
\end{theorem}

(If $y(n)$ is increasing then the set $\F_y$ is m-reducible since $\F_y=\F_y\cdot\F_y$, and we also have $\F_y\sim\F_y\cdot\{1,2\}$, thus if we want to prove an {\sl m-primitivity} theorem involving $\F_y$ then we have to switch from $\F_y$ to the shifted set
\begin{equation}
\label{eq16}
\g_y:=\F_y+\{1\}.
\end{equation}
See also \cite{el}.)

\begin{theorem}
\label{thm2}
If $y(n)$ is defined as in Theorem \ref{thm1}, then the set $\g_y$ is totally {\sl m-primitive}.
\end{theorem}

(While in part II of this paper we will present further closely related results.)

\section{Proof of Theorem \ref{thm1}}

Assume that contrary to the statement of the theorem, the function $y=y(n)$ satisfies the assumptions in Theorem \ref{thm1}, however, the set $\F_y$ is {\sl not} totally a-primitive. Then there are $\F_y'\subset \N_0$, $n_0\in\N$, $A\subset \N_0$, $\B\subset\N_0$ such that
\begin{equation}
\label{eq21}
\F_y'\cap [n_0,+\infty)=\F_y\cap [n_0,+\infty),
\end{equation}
\begin{equation}
\label{eq22}
|\A|\geq 2,\ |\B|\geq 2
\end{equation}
and
\begin{equation}
\label{eq23}
\F_y'=\A+\B.
\end{equation}
Let $N$ denote a positive integer with
\begin{equation}
\label{eq24}
N\to+\infty.
\end{equation}
It follows from \eqref{eq21} and \eqref{eq23} that
$$
\F_y\cap [n_0,N]=\F_y'\cap [n_0,N]=(\A+\B)\cap [n_0,N]\subset(\A\cap [0,N])+(\B\cap [0,N])
$$
whence
\begin{multline}
\label{eq25}
|\F_y\cap [n_0,N]|\leq |(\A\cap [0,N])+(\B\cap [0,N])|\leq\\
\leq |(\A\cap [0,N])|\cdot |(\B\cap [0,N])|=A(N)B(N).
\end{multline}
On the other hand, using the standard notation
$$
\Psi(x,y)=|\{n:n\leq x,\ p^+(n)\leq y\}|,
$$
for $N\to +\infty$ we have
\begin{multline}
\label{eq26}
|\F_y\cap [n_0,N]|=|\F_y\cap (0,N]|-|\F_y\cap (0,n_0)|\geq\\
\geq\Psi(N,y(N))-n_0=(1+o(1))\Psi(N,y(N))
\end{multline}
since clearly
\begin{equation}
\label{eq27}
\Psi(x,y)\to +\infty\ \text{for}\ 2\leq y\leq x,\ x\to +\infty.
\end{equation}
By \eqref{eq25} and \eqref{eq26}, for large enough $N$ we have
$$
\max(A(N),B(N))>{\frac{1}{2}} (\Psi(N,y(N)))^{1/2}.
$$
Thus either
$$
A(N)>{\frac{1}{2}} (\Psi(N,y(N)))^{1/2}
$$
or
\begin{equation}
\label{eq28}
B(N)>{\frac{1}{2}} (\Psi(N,y(N)))^{1/2}
\end{equation}
holds for infinitely many $N$; since $\A$ and $\B$ play symmetric roles thus we may assume that \eqref{eq28} does.

Write $\A=\{a_1,a_2,\dots\}$ with $(0\leq)a_1<a_2<\dots$ and
\begin{equation}
\label{eq29}
\tilde{\B}_N=\{b:b\in\B,\ n_0-a_1\leq b\leq N-a_2\}.
\end{equation}
Then by \eqref{eq27}, for all large enough $N$ satisfying \eqref{eq28} we have
\begin{multline}
\label{eq210}
|\tilde{\B}_N|=|(\B\cap [0,N])\setminus\left((\B\cap [0,n_0-a_1))\cup (\B\cap (N-a_2,N])\right)|\geq\\
\geq |\B\cap [0,N]|-|\B\cap [0,n_0-a_1)|-|\B\cap (N-a_2,N]|\geq\\
\geq B(N)-n_0-a_2>{\frac{1}{3}} (\Psi(N,y(N)))^{1/2}.
\end{multline}

We will need the notion of $S$-unit equations and a result on the number of solutions of them. For their formulation, we introduce some notation. Let $(0<)p_1<p_2<\dots<p_s$ be prime numbers, write $\s=\{p_1,p_2,\dots,p_s\}$ and let
$$
\Z_\s=\left\{\frac{a}{b}:a,b\in\Z,\ b\neq 0,\ (a,b)=1,\ p\mid b\implies p\in\s\right\}
$$
be the set of {\sl $\s$-integers}. Then the units of the ring $\Z_\s$, that is the set of {\sl $\s$-units} is given by
\begin{equation}
\label{eq211}
\Z_\s^*=\left\{\frac{a}{b}:a,b\in\Z,\ ab\neq 0,\ (a,b)=1,\ p\mid ab\implies p\in\s\right\}.
\end{equation}

\begin{lemma}
\label{lem1}
If $U\in\Q$, $V\in\Q$ and $UV\neq 0$ then the {\rm $S$-unit equation}
\begin{equation}
\label{eq212}
UX+VY=1,\ X,Y\in\Z_\s^*
\end{equation}
has at most $2^{8(2s+2)}$ solutions.
\end{lemma}

\begin{proof} This assertion is a consequence of a theorem of Beukers and Schlickewei \cite{bs}; see Corollary 6.1.5 of Evertse and Gy\H{o}ry \cite{eg}, p.133.
\end{proof}

We will apply this lemma later with
\begin{equation}
\label{eq213}
\s=\{p:p\ \text{prime},\ p\leq y\}=\{p_1,p_2,\dots,p_{\pi(y)}\}
\end{equation}
(where $p_1<p_2<\dots<p_{\pi(y)}$ are the first $\pi(y)$ primes) so that now
\begin{equation}
\label{eq214}
s=|\s|=\pi(y)=\pi(y(N)).
\end{equation}
Consider now any
\begin{equation}
\label{eq215}
b\in \tilde{\B}_N,
\end{equation}
and write
\begin{equation}
\label{eq216}
X_b=a_2+b,\ Y_b=a_1+b.
\end{equation}
Then we have
$$
X_b-Y_b=a_2-a_1
$$
whence
\begin{equation}
\label{eq217}
\frac{1}{a_2-a_1}X_b-\frac{1}{a_2-a_1}Y_b=1.
\end{equation}
By \eqref{eq215} and \eqref{eq216} for all $b\in\tilde{\B}_N$ we have
\begin{multline}
\label{eq218}
n_0=a_1+(n-a_1)\leq a_1+b=Y_b<\\
<a_2+b=X_b\leq a_2+(N-a_2)=N,
\end{multline}
and by \eqref{eq23} we also have
\begin{equation}
\label{eq219}
a_1+b=Y_b\in\F_y'\ \text{and}\ a_2+b=X_b\in\F_y'.
\end{equation}
It follows from \eqref{eq21}, \eqref{eq218} and \eqref{eq219} that
$$
X_b,Y_b\in [n_0,N]\cap\F_y'=[n_0,N]\cap\F_y,
$$
thus $X_b,Y_b$ are composed from the primes not exceeding $y=y(N)$, i.e. from the set $\s$ defined in \eqref{eq213}, so that
\begin{equation}
\label{eq220}
X_b,Y_b\in\Z_\s^*
\end{equation}
(for the $\Z_\s^*$ defined in \eqref{eq211}). Writing $U=\frac{1}{a_2-a_1}$, $V=-\frac{1}{a_2-a_1}$, we have $U,V\in\Q$, thus
\begin{equation}
\label{eq221}
UX+VY=1,\ X,Y\in\Z_\s^*
\end{equation}
is an $S$-unit equation, and by \eqref{eq217} and \eqref{eq220} for every $b$ satisfying \eqref{eq215}, $X=X_b$, $Y=Y_b$ is a solution of this equation. It follows by \eqref{eq210} that the number $M$ of solutions of this equation satisfies
\begin{equation}
\label{eq222}
M\geq |\tilde{\B}_N|> \frac{1}{3} (\Psi(N,y(N)))^{1/2}.
\end{equation}

On the other hand, by Lemma \ref{lem1} and \eqref{eq214} we have
\begin{equation}
\label{eq223}
M\leq 2^{8(2s+2)}=2^{8(2\pi(y)+2)}.
\end{equation}
By \eqref{eq222} and \eqref{eq223} we have
\begin{equation}
\label{eq224}
\frac{1}{3} (\Psi(N,y(N)))^{1/2}<2^{8(2\pi(y)+2)}.
\end{equation}

Now we have to distinguish two cases.

CASE 1. Assume first that
\begin{equation}
\label{eq225}
2\leq y=y(N)\leq \log\log N.
\end{equation}
Then clearly we have
\begin{multline*}
\Psi(N,y(N))\geq \Psi(N,2)=|\{k\in\N_0,\ 2^k\leq N\}|=\\
=\left[\frac{\log N}{\log 2}\right]+1>\frac{\log N}{\log 2}>\log N
\end{multline*}
whence
\begin{equation}
\label{eq226}
\frac{1}{3} (\Psi(N,y(N)))^{1/2}>\frac{1}{3} (\log N)^{1/2}.
\end{equation}
On the other hand, by \eqref{eq225} we have
\begin{equation}
\label{eq227}
2^{8(2\pi(y)+2)}\leq 2^{8(2\pi(\log\log N)+2)}=2^{o(\log\log N)}=(\log N)^{o(1)}.
\end{equation}
\eqref{eq226} and \eqref{eq227} contradict \eqref{eq224}.

CASE 2. Assume now that
\begin{equation}
\label{eq228}
\log\log N<y(N)<2^{-32}\log N.
\end{equation}
We will need the following lemma:

\begin{lemma}
\label{lem2}
Write
$$
Z=\frac{\log x}{\log y}\log\left(1+\frac{y}{\log x}\right)+\frac{y}{\log y}\log\left(1+\frac{\log x}{y}\right).
$$
Then we have, uniformly for $x\geq y\geq 2$,
$$
\log\Psi(x,y)=Z\left(1+O\left(\frac{1}{\log y}+\frac{1}{\log\log 2x}\right)\right).
$$
\end{lemma}

\begin{proof}
This is de Bruijn's theorem \cite{br} (see also \cite{te} for the proof, background, and analysis of this formula).
\end{proof}

By \eqref{eq228} and Lemma \ref{lem2}, for $N$ large enough we have
\begin{multline}
\label{eq229}
\log\Psi(N,y(N))=Z\left(1+O\left(\frac{1}{\log y(N)}\right)\right)=\\
\left(\frac{\log N}{\log y(N)}\log\left(1+\frac{y(N)}{\log N}\right)+\frac{y(N)}{\log y(N)}\log\left(1+\frac{\log N}{y(N)}\right)\right)(1+o(1))>\\
>(1+o(1))\left(\frac{y(N)}{\log y(N)}\log(1+2^{32})\right).
\end{multline}

On the other hand, by \eqref{eq224}, \eqref{eq228} and the prime number theorem, for $N\to +\infty$ we have
\begin{multline*}
\log\Psi(N,y(N))<2\left(\log 3+\log 2^{8(2\pi(y)+2)}\right)=\\
=\log 9+2(2\pi(y)+2)\log 2^8=(1+o(1))\log 2^{32}\frac{y(N)}{\log y(N)}.
\end{multline*}
For $N$ large enough this contradicts \eqref{eq229} which completes the proof of Theorem \ref{thm1}.

\section{Proof of Theorem \ref{thm2}}
There are some similarities between the proofs of Theorems \ref{thm1} and \ref{thm2}, thus we will omit some details.

Assume that the conditions of Theorem \ref{thm2} hold, however, contrary to the statement of the theorem there are $\g_y'\subset\N$, $n_0\in\N$, $\A\subset\N$, $\B\subset\N$ such that
\begin{equation}
\label{eq31}
\g_y'\cap [n_0,+\infty)=\g_y\cap [n_0,+\infty),
\end{equation}
\eqref{eq22} holds, and
\begin{equation}
\label{eq32}
\g_y'=\A\cdot\B.
\end{equation}
Assume that $N\in\N$ satisfies \eqref{eq24}. Then it follows from \eqref{eq31} and \eqref{eq32} that
$$
\g_y\cap [n_0,N]=\g_y'\cap [n_0,N]\subset (\A\cap [0,N])\cdot (\B\cap [0,N])
$$
whence, by \eqref{eq16},
\begin{equation}
\label{eq33}
|\F_y\cap [n_0-1,N-1]|=|\g_y\cap [n_0,N]|\leq A(N)B(N).
\end{equation}
On the other hand, as in \eqref{eq26}, for $N\to +\infty$ we have
\begin{equation}
\label{eq34}
|\F_y\cap [n_0-1,N-1]|=(1+o(1))\F_y(0,N)=(1+o(1))\Psi(N,y(N)).
\end{equation}
By \eqref{eq33} and \eqref{eq34}, for every $N$ large enough we have
\begin{equation}
\label{eq35}
A(N)B(N)> \frac{1}{2} \Psi(N,y(N)).
\end{equation}

Now write $\A=\{a_1,a_2,\dots\}$ with $(0<)a_1<a_2<\dots$ and $\B=\{b_1,b_2,\dots\}$ with $(0<)b_1<b_2<\dots$, and define $m$ by $m=\max(a_2,b_2)$ (so that $m\geq 1$). We will show that there are infinitely many positive integers $D$ such that
\begin{equation}
\label{eq36}
A(mD)B(mD)< (m^2+1) A(D)B(D).
\end{equation}
Indeed, assume that contrary to this assertion there are only finitely many positive integers $D$ with this property. Then there exists a positive integer $D_0$ with
\begin{equation}
\label{eq37}
A(D_0)B(D_0)>0
\end{equation}
such that for $D\in\N$, $D\geq D_0$ we have
$$
A(mD)B(mD)\geq (m^2+1) A(D)B(D).
$$
It follows from this by induction on $k$ that
\begin{equation}
\label{eq38}
A(m^kD_0)B(m^kD_0)\geq (m^2+1)^k A(D_0)B(D_0)\ \ \ \text{for}\ k=0,1,2,\dots .
\end{equation}
Clearly, we have
\begin{equation}
\label{eq39}
A(m^kD_0)B(m^kD_0)\leq m^kD_0\cdot m^k D_0=m^{2k}D_0^2 .
\end{equation}
We obtain from \eqref{eq38} and \eqref{eq39} that
$$
(m^2+1)^k A(D_0)B(D_0)\leq m^{2k}D_0^2
$$
whence
$$
\left(1+\frac{1}{m^2}\right)^k A(D_0)B(D_0)\leq D_0^2\ \ \ (\text{for}\ k=0,1,2,\dots).
$$
However, by \eqref{eq37}, this inequality cannot hold for $k$ large enough, and this contradiction proves the existence of infinitely many $D\in\N$ satisfying \eqref{eq36}.

Let $D$ be a positive integer satisfying \eqref{eq36} and large enough, and write $N=mD$. So far the sets $\A$ and $\B$ play symmetric roles thus we may assume that
\begin{equation}
\label{eq310}
B(D)\geq A(D).
\end{equation}
It follows from \eqref{eq35},\eqref{eq36} and \eqref{eq310} that
\begin{multline*}
\frac{1}{2} \Psi(N,y(N))<A(N)B(N)=A(mD)B(mD)<\\
<(m^2+1) A(D)B(D)\leq (m^2+1)(B(D))^2
\end{multline*}
whence, by $m\geq 1$,
\begin{equation}
\label{eq311}
B(D)\geq (2(m^2+1))^{-1/2} \left(\Psi(N,y(N))\right)^{1/2}\geq \frac{1}{2m}\left(\Psi(N,y(N))\right)^{1/2}.
\end{equation}
Now write
\begin{equation}
\label{eq312}
\tilde{\B}_N=\{b:b\in\B,\ n_0/a_1<b\leq N/a_2\}
\end{equation}
(note that $a_1\geq 1$ by $\A\subset\N$). Then by $\A\subset\N$, $N=mD$, the definition of $m$, and \eqref{eq311}, we have
\begin{multline}
\label{eq313}
|\tilde{\B}_N|=|\{b:b\in\B,\ n_0/a_1<b\leq N/a_2\}|=\\
=|\{b:b\in\B,\ b\leq N/a_2\}|-|\{b:b\in\B,\ b\leq n_0/a_1\}|\geq\\
\geq |\{b:b\in\B,\ b\leq N/m\}|-|\{b:b\in\B,\ b\leq n_0\}|=\\
=B(D)-B(n_0)\geq \frac{1}{2m} \left(\Psi(N,y(N))\right)^{1/2}-n_0 > \frac{1}{3m} \left(\Psi(N,y(N))\right)^{1/2}
\end{multline}
for $N$ large enough.

Consider now any
\begin{equation}
\label{eq314}
b\in\tilde{\B}_N
\end{equation}
and write
\begin{equation}
\label{eq315}
X_b=a_1b-1,\ \ \ Y_b=a_2b-1.
\end{equation}
Then we have
$$
a_2X_b-a_1Y_b=a_2(a_1b-1)-a_1(a_2b-1)=a_1-a_2,
$$
so that $X=X_b$, $Y=Y_b$ is a solution of the equation
\begin{equation}
\label{eq316}
\frac{a_2}{a_1-a_2} X-\frac{a_1}{a_1-a_2} Y=1.
\end{equation}
Moreover, by \eqref{eq312}, \eqref{eq314} and \eqref{eq315} we have
\begin{equation}
\label{eq317}
n_0\leq X_b=a_1b-1<Y_b=a_2b-1\leq N-1.
\end{equation}
It follows from \eqref{eq31} that
$$
a_1b\in\g_y'\ \ \ \text{and}\ \ \ a_2b\in\g_y',
$$
thus by \eqref{eq32} and \eqref{eq317} we also have
$$
a_1b\in\g_y\ \ \ \text{and}\ \ \ a_2b\in\g_y,
$$
so that by \eqref{eq16},
$$
X_b=a_1b-1\in\F_y\ \ \ \text{and}\ \ \ Y_b=a_2b-1\in\F_y.
$$
Thus $X_b$ and $Y_b$ satisfy \eqref{eq220} for the sets $\s$ and $\Z_\s^*$ defined by \eqref{eq213} and \eqref{eq211}, respectively. Then for every $b$ satisfying \eqref{eq314}, $X=X_b$, $Y=Y_b$ is a solution of the $S$-unit equation formed by \eqref{eq316} and $X,Y\in\Z_\s^*$ with this $\s,\Z_\s^*$, and clearly, if we start out from different $b$ values satisfying \eqref{eq314}, then we get different solutions $X=X_b$, $Y=Y_b$ of this equation. Thus by \eqref{eq313} the number $M$ of the solutions of this $S$-unit equation satisfies
\begin{equation}
\label{eq318}
M\geq |\tilde{\B}_N|> \frac{1}{3m} \left(\Psi(N,y(N))\right)^{1/2}.
\end{equation}
On the other hand, by Lemma \ref{lem1} the number of solutions must satisfy
\begin{equation}
\label{eq319}
M\leq 2^{8(2s+2)}=2^{8(2\pi(y)+2)}.
\end{equation}
It follows from \eqref{eq318} and \eqref{eq319} that
$$
\frac{1}{3m} \left(\Psi(N,y(N))\right)^{1/2}<2^{8(2\pi(y)+2)}.
$$
This is almost identical with inequality \eqref{eq224}, the only difference is that the constant factor $\frac{1}{3}$ on the left hand side of \eqref{eq224} is replaced here by $\frac{1}{3m}$ which is also independent of $N$, and thus it is easy to see that it leads to a contradiction in the same way as \eqref{eq224} did in Section 2.


TITLE: What is a non binary adjacency Matrix?
QUESTION [5 upvotes]: I am going through the implementation of a graph convolutional neural network. I came across a non-binary adjacency matrix in the case of a directed graph.
The particular issue is discussed here in the following
https://github.com/tkipf/pygcn/issues/3
Can someone explain what a non-binary adjacency matrix looks like? How can an adjacency matrix have something other than 0 or 1?

REPLY [3 votes]: In some uses, the value of the adjacency matrix is the number of parallel edges connecting the nodes.


TITLE: probability of divisibility
QUESTION [1 upvotes]: Let S be the sum of k randomly selected integers between 1 and n.
What is the probability of S being divisible q?
Can this be expressed in a closed form?
This is the generalization of one of the problems from this year's hungarian high school final exam - advanced mathematics.

REPLY [2 votes]: One can use discrete Fourier transform, starting with $z=\mathrm e^{2\mathrm i\pi/q}$ a $q$th root of unity and using the identity
$$
\sum_{u=1}^qz^{un}=q\,\mathbf 1_{q\ \text{divides}\ n}.
$$
Thus,
$$
P[q\ \text{divides}\ S]=\frac1q\sum_{u=1}^qE[z^{uS}].
$$
Now, for every $x$, $E[x^S]=E[x^X]^k$ where $X$ is uniform on $\{1,2,\ldots,n\}$, and, for every $x\ne1$,
$$
E[x^X]=\frac1n\sum_{u=1}^nx^u=\frac{x}n\frac{1-x^n}{1-x},
$$
and whether the formula for $P[q\ \text{divides}\ S]$ all this, when put together, yields, is a "closed form" or not is... well, debatable.


TITLE: A weaker characterization of convergence in distribution
QUESTION [1 upvotes]: $X_n$ and $X$ are real-valued random variables. If $X_n \to X$ in distribution, then we know that
$$P\{X_n \leq a\} \to P\{X \leq a\}$$
for every $a$ at which $x\mapsto P\{X \leq x\}$ is continuous. For a certain problem I have at hand this condition is too strong to check. Instead, I only have the following.
$$P\{X_n \leq a\} \to P\{X \leq a\}$$
for every $a \in D$ where $D = \{d_1,d_2,\ldots\}$ is a countable dense set in $\mathbb{R}$ such that $x\mapsto P\{X \leq x\}$, $x\mapsto P\{X_1 \leq x\}$, $x\mapsto P\{X_2 \leq x\},\ldots$ are continuous at $d_i$ for every $i = 1,2,\ldots$. I would like to show that this condition is sufficient for convergence in distribution.
I fix an arbitrary $d \notin D$ such that $x\mapsto P\{X \leq x\}$ is continuous at $d$. By denseness of $D$ I can find a sequence $(d_k)_k$ such that $d_k \downarrow d$. By right-continuity and monotonicity of the distribution functions
$$P\{X_n \leq d_k\} \to P\{X_n \leq d\} \quad \text{and} \quad P\{X \leq d_k\} \to P\{X \leq d\}$$
for every $n$ as $k \to \infty$. Furthermore, by definition of the set $D$
$$P\{X_n \leq d_k\} \to P\{X \leq d_k\}$$
for every $k$ as $n\to\infty$.
How do I conclude rigorously from these that
$$P\{X_n \leq d\} \to P\{X \leq d\}$$

REPLY [1 votes]: If a sequence $(d_k)$ from $D$ decreases to $x$, then $F_n(x)\le F_n(d_k)$, so $\limsup_nF_n(x)\le F(d_k)$ for all $k$, so $\limsup_nF_n(x)\le F(x)$. If $(d_k)\subset D$ increases to $x$, and $x$ is a continuity point of $F$, then in like fashion $\liminf_nF_n(x)\ge F(x)$.


TITLE: Probability of not appearing a side of a dice
QUESTION [0 upvotes]: We flip over a dice infinite times. What is the probability that a specific side will never show up?
I think that the probability is zero. Am I wrong ?

REPLY [1 votes]: A direct corollary of the law of large numbers is that if there is a non-zero probability of event E occurring in a trial, and the number of trials goes to infinity, then E must happen. This, there is zero probability that E won't happen.


TITLE: Double and triple integral in spherical polar coordinates, $\iint\sqrt{4-x^2-y^2}\mathrm{d}A$
QUESTION [0 upvotes]: Consider the double integral
$$
I=\iint\limits_{\mathcal D} \sqrt{4-x^2-y^2}\mathrm{d}A
$$
where $\mathcal D=\{(x,Y): x^2 + y^2 \leq 4\}$ is the disc on the $xy$ plane
(source)
A.) Use polar coordinates to evaluate the double integral $I$
B.) Give an interpretation of the integral $I$ as the volume of a region $\mathcal R$ in ($x$, $y$, $z$)-space.
Hence write $I$ as a triple integral over $\mathcal R$ in cylindrical polar coordinates.
For A, I changed the integral to
$$
\int_0^{2\pi}\int_0^2 r\sqrt{4-r^2}\mathrm{d}r\mathrm{d}\theta
$$
This eventually led me to get $\displaystyle{\int_0^{2\pi}\frac83 \mathrm{d}\theta}=\frac{16\pi}{3}$. I'm not completely sure about the integral limits I used.
For B, I rewrote the equation as $x^2 + y^2 + z^2 = a^2 = 4$ ($a=2$), and then solved normally using spherical polar coordinates. I got an answer of $\displaystyle{\frac{32\pi}{3}}$. But since the original equation only included the positive area of the sphere, should the volume be $\displaystyle{\frac{16\pi}{3}}$ instead?

REPLY [0 votes]: Technically the question asked you to do (b) using cylindrical coordinates, not spherical coordinates. This is basically the same as doing it with polar coordinates and a height function, since you just have $\int_0^{2\pi} \int_0^2 \left ( \int_0^{\sqrt{4-r^2}} 1 dz \right ) r dr d\theta$, where I use parentheses just for emphasis.
But yes, since this is a hemisphere, whichever coordinate system you use, you will end up with $2 \pi 2^3/3$ instead of $4 \pi 2^3/3$.


TITLE: Prove that $OM=ON$
QUESTION [1 upvotes]: Consider $\Delta ABC$ has $AB=AC\text{ and } \angle BAC=90^o$. Let $O$ with radius $\dfrac{AB}2$. The secant $DE$ such that $CE$ always goes through $OB$.  $CO \cap BD=M;CO \cap BE= N$. Prove that $OM=ON$

To prove $OM=ON$ we need prove $MANB$ is parallelogram $(OA=OB)$
We need to prove $\angle MAB=\angle ABN\rightarrow \angle MAC=\angle BAE=\angle BDE=\angle CDM$
I dont know how to prove this. I tried to prove some similar triangles but failed.

REPLY [1 votes]: hint: if you can approve TE pass O , then the problem is solved.


TITLE: how to find the maximum height perpendicular to arc without knowing radius of the arc
QUESTION [1 upvotes]: I am doing the curvature correction of the object boundary, I need to calcluate the maximum height perpendicular to the arc shown in the figure.
I know the chord length and arc length, But i don't know the radius of the arc.
I would like to know how to find out the maximum height perpendicular to the the arc if we have only two parameters like W and A.
Please help me to solve this problem.
Thanks in advance.

REPLY [0 votes]: Here's the simple solution you're looking for, but it's only an approximation, plus or minus 2 or 3%.
s=sagitta (or height), a=arc length, c=chord length
s = 0.42 * √( a^2 - c^2 )
c = √( a^2 - (s/0.42)^2 )
a = √( c^2 + (s/0.42)^2 )
If the arc is more like a full semi-circle (where radius=sagitta), then the constant will be a little closer to 0.4127. If the arc is more flat (very large radius), then the constant will be closer to 0.43. But these are minor differences for an approximation.


text:
\section{Applications}\label{c:prz}
In this section we use Theorem \ref{t:main} to find triangulations of some topological spaces, that give, as nerves, right-angled Coxeter groups with Menger curve boundary.

\begin{remark}
In further text, we consider the boundary
$\partial\sigma$ of a simplicial complex $\sigma$.
In such case $\sigma$ is a triangulation of a manifold $M_{\sigma}$ and by $\partial\sigma$ we mean the subcomplex of $\sigma$ that corresponds to the boundary $\partial M_{\sigma}$ of the manifold $M_{\sigma}$.
In particular, if $\sigma$ is a subcomplex of some $\tau$, we do not mean the topological boundary of $\sigma$ in the space $\tau$.

\end{remark}

\subsection{Triangulations of 2-dimensional simplicial complexes}

\begin{definition}
	An edge of a 2-dimensional simplicial complex $X$ that is not contained in any face of $X$ is a  \emph{lonely edge}.
\end{definition}

\begin{theorem}\label{t:kompleksy}
	Let $X$ be a

	2-dimensional simplicial complex without lonely edges.

	TFAE:

	\begin{enumerate}[(i)]
		\item $X$ admits a triangulation $N$ such that $N$ is flag and the boundary $\bd{W_N}$ is the Menger curve,

		\label{t:kompleksy1}

		\item $X$ admits infinitely many triangulations as in \ref{t:kompleksy1},
		\label{t:kompleksy2}

		\item $X$ is connected, non-planar, has no separating pair of points and $H^2X=0$.
		\label{t:kompleksy3}
	\end{enumerate}
\end{theorem}

\begin{remark}
\begin{enumerate}[(i)]
\item Having no lonely edges implies that a point $x\in X$ is a local cut-point

if and only if it is a vertex of $X$ whose link is not connected.
Therefore the the set of local cut-points in $X$ is discrete, so any triangulation $N$ of $X$ has no lonely edges, thus each separating point of $X$ is a vertex of $N$.
\item If $X$ has no separating pair, then it has no separating point.
\end{enumerate}
\end{remark}

\begin{corollary}\label{c:powierzchnie}
Let $M$ be a compact surface (it may have a boundary). Then $M$ admits a triangulation (equivalently, infinitely many triangulations) that is a nerve of a right-angled Coxeter group with Menger curve boundary if and only if the boundary $\partial M$ is non-empty and $M$ is non-planar.
\end{corollary}
\begin{proof}{\sc (of Corollary \ref{c:powierzchnie})}
We can triangulate $M$. Such a triangulation has no local cut-points and no lonely edges. In view of Theorem \ref{t:kompleksy}, it suffices to check that $\partial M\neq\emptyset$ if and only if $H^2M=0$, but it follows from classical theorems on surfaces and manifolds.
\end{proof}

\begin{proof}{\sc (of Theorem \ref{t:kompleksy})}
\emph{\ref{t:kompleksy2}$\Rightarrow$\ref{t:kompleksy1}.} Clear.

\medskip
\emph{\ref{t:kompleksy1}$\Rightarrow$\ref{t:kompleksy3}.} Non-planarity of $X$ follows by Remark \ref{u:mainkonieczne}\ref{u:mainkonieczne4}.
The condition $H^2X=0$ follows by Remark \ref{u:mainkonieczne}\ref{u:mainkonieczne1}.
Connectedness of $X$ and lack of separating pair of points in $X$ are necessary conditions for the existence of a non-separable triangulation of $X$, which by Remark \ref{u:mainkonieczne}\ref{u:mainkonieczne2} finishes the proof of this implication.

\medskip
\emph{\ref{t:kompleksy3}$\Rightarrow$\ref{t:kompleksy2}.}
In the proof, first we find a non-planar graph that is embedded in $X$, next we make it a part of some triangulation, out of which we produce infinitely many ones that satisfy the assumptions of Theorem \ref{t:main}.

\smallskip
\emph{Finding the graph.}
The space $X$ is compact, metrisable,
connected, locally connected, non-planar and has no cut-points, therefore by \cite[end of Section 3]{KaKl98} some non-planar graph embeds in $X$. By Kuratowski's Theorem we may assume it is either $\katt$ or $\kapi$. (Notice that we do not need to use such general theorems in case when $X$ is a less general space, e.g. a surface).
We may assume that $X$ admits a triangulation $K$, that has a 1-dimensional subcomplex $\Gamma$, which is an edge subdivision of either $\katt$ or $\kapi$.

\begin{figure}
\iflight
	\centerline{\input{figpodrozbiciedra.tex}}
\else
	\includegraphics[width=0.9\textwidth]{20190717641}
\fi
\centering
\caption{The simplex $\Delta$ with its subdivisions $\Delta^{\dra}$ and $\Delta^{\dra\dra}$.}
\label{fig:podrozbiciedra}
\end{figure}

\smallskip
\emph{Final triangulation.} We want to modify $K$ in such a way that it becomes in particular  flag {no-$\square$}.

We use a method of subdividing 2-dimensional complexes that was introduced in \cite{Dra99}. It consists in subdividing each edge into two edges and subdividing each face as in Figure \ref{fig:podrozbiciedra}. We denote by $L^{\dra}$ the result of such subdivision applied to a simplicial complex $L$. It has the following properties.

\begin{lemma}\label{l:podrozbiciedra}
Let $L$ be a 2-dimensional simplicial complex. Then:
\begin{enumerate}[(i)]
\item $L^{\dra}$ is flag no-$\square$,
\label{l:podrozbiciedra1}

\item if $\Gamma$ is a 1-dimensional subcomplex of $L$, then the subcomplex $\Gamma^{\dra}$ of $L^{\dra}$
is full,
\label{l:podrozbiciedra2}

\item if $L$ is connected, has no lonely edges an no separating pair of vertices, then the complex $L^{\dra\dra}$ is inseparable.

\label{l:podrozbiciedra3}
\end{enumerate}
\end{lemma}

We omit the proof of Lemma \ref{l:podrozbiciedra} since it is a combination of well known properties and some routine combinatorial reasonings.
As the required infinitely many triangulations, we take $n$-fold subdivisions $K^{n\times\dra}$ for $n\geq2$ --
by Lemma \ref{l:podrozbiciedra} each of these triangulations satisfies all the assumptions of Theorem \ref{t:main} besides the cohomology condition (for \sg-non-planarity, recall Remark \ref{u:tnieplan}). The latter can be shown by the following standard reasoning using the Mayer-Vietoris sequence.

Let $\Delta$ be any simplex of $K^{n\times\dra}$.
By the properties of simplicial complexes, there exists a neighbourhood $U$ of $\Delta$ such that the boundary $\partial U$ is homeomorphic to a 1-dimensional simplicial complex, $\Delta$ is a deformation retract of $U$ and $U\setminus\Delta$ is homotopy equivalent to $\partial U$.

Then, considering the following part of the the Mayer-Vietoris sequence: $H^2(K^{n\times\dra})\to H^2(K^{n\times\dra}\setminus\Delta)\oplus H^2(U)\to H^2(U\cap(K^{n\times\dra}\setminus\Delta))$ whose left term is 0 by assumption and the right term is 0 by the choice of $U$, we have that $H^2(K^{n\times\dra}\setminus\Delta)=0$.
\end{proof}

\subsection{Triangulations of disks $D^n$}

In this section we prove the following theorem.

\begin{theorem}\label{t:dysk}
	The disk $D^n$ admits a triangulation that is a nerve of a right-angled Coxeter group with Menger curve boundary if and only if $n\geq3$.
\end{theorem}

Note that, by the cohomology condition in Theorem \ref{t:main}, we have that the desired triangulation should have all its $(n-3)$-simplicies contained in the boundary $\partial D^n$.

\begin{proof}
The crux of the proof is the case $n=3$. To cover this case we construct a triangulation of $D^3$ that satisfies the conditions of Theorem \ref{t:main}. When $n<3$, the disk $D^n$ is planar, so its any flag triangulation (viewed as a nerve) yields a right angled Coxeter group with planar
boundary, \cite[Lemma 2.4]{Swiat16}.
On the other hand, if $N$ is a flag no-$\square$ complex, then the simplicial cone $\Cone{N}$ over $N$ also is and we have $W_{\Cone{N}}\cong W_N\oplus\Z_2$.
By properties of the Gromov boundary, this implies that $\bd{W_N}\cong\bd{W_{\Cone{N}}}$. Since $\Cone{D^n}\cong D^{n+1}$, in order to obtain an appropriate triangulation of $D^n$ for $n>3$ it suffices to take $n-3$ times the simplicial cone over the triangulation for $D^3$. From now on we concentrate on the case of $n=3$.

\begin{figure}
\centering
\iflight
	\centerline{\input{figkonstrukcja.tex}}
\else
	\includegraphics[width=0.45\textwidth]{20190716636}
	\includegraphics[width=0.45\textwidth]{20190716637}
\fi
\caption{\emph{Left:} 1-skeleton after stages \eone--\ethree. \emph{Right:} Final 1-skeleton. We removed the \tone{axis} from the picture and cut complex along a \tone{meridian}, removing some edges and vertices around this cutting.}
\label{fig:konstrukcja}
\end{figure}

\smallskip
\emph{Construction.} The construction is divided into 6 stages \eone--\esix.

To each stage we associate a colour, which

will be used in the pictures. The simplices created in the stage (s$i$) will be coloured in the colour associated to this stage and will be called (s$i$)-simplices (such convention is extended to other objects).
Note that not all the edges of a (s$i$)-simplex are necessarily (s$i$)-edges, only those that do not belong to any (s$j$)-simplex for some $j<i$.
The construction can be subdivided into a sequence of steps, each consisting in gluing some 3-simplex to a 3-dimensional complex $\triang$ along one or two neighbouring faces contained in the boundary $\partial\triang$. Thus, at each step $\triang$ is a triangulation of the disk $D^3$ having all of its vertices on the boundary $\partial D^3$.
We call a subcomplex $\sigma$ \emph{external} if it is contained in the boundary $\partial\triang$,  \emph{internal} otherwise.

See Figure \ref{fig:konstrukcja}. The schematic view of the complex that is present there will be used throughout the whole proof.

\begin{enumerate}
\item[\eone]
Take a \tone{simplicial join of a 8-cycle $C_8$

with an edge $E$}. We call fragments of its 1-skeleton in a natural way, namely the edge $E$ is called the \tone{axis}, the cycle $C_8$ is the \tone{equator}, the endpoints of the axis are the north and south pole. The remaining part consists of 8 2-paths

with endpoints in the poles, we call them meridians.

\item[\etwo]

Glue to each external \eone-face a \ttwo{3-simplex} (by one of its faces).

\item[\ethree]

For each pair of \etwo-3-simplices that share an edge of a \tone{meridian}, glue a \tthree{3-simplex} between them, i.e. in a way that one of its faces is glued to the \ttwo{right face of one of these \etwo-3-simplices} and the other to the \ttwo{left face of the other of the \etwo-3-simplices}.

\item[\efour]
For each pair of \etwo-3-simplices $\ttwo{\Delta_1},\ttwo{\Delta_2}$ that share an edge of the \tone{equator}, with $\ttwo{\Delta_1}$ ($\ttwo{\Delta_2}$) above (below) the equator, glue a \tfour{simplicial suspension of a 2-simplex} so that some of its full subcomplexes being a suspension of an edge has one of its faces glued to the lower face of the \etwo-3-simplex $\ttwo{\Delta_1}$ and the other face glued to the upper face of \etwo-3-simplex $\ttwo{\Delta_2}$.

\item[\efive]
We glue \tfive{3-simplices} to some of the external faces of \ethree-3-simplices, that intersect the \tone{equator}, in the following way.
Denote $\tthree{N_1},\ldots,\tthree{N_8}$ ($\tthree{S_1},\ldots,\tthree{S_8}$) the faces described above that are above (below) the \tone{equator} (in a cyclical order) in such a way that the face $\tthree{N_i}$ shares an edge with the face $\tthree{S_i}$. We glue a \tfive{3-simplex} to each of the faces $\tthree{N_1},\tthree{N_2},\tthree{S_3},\tthree{S_4},\tthree{N_5},\tthree{N_6},\tthree{S_7},\tthree{S_8}$.

\item[\esix]

For each pair of 3-simplices \tfour{$\Delta_4$}, \tfive{$\Delta_5$} such that $\Delta_i$ is a (s$i$)-simplex, if \tfour{$\Delta_4$} and \tfive{$\Delta_5$} share a \etwo-edge $e$, we glue a \tsix{3-simplex} in such a way that one of its faces is glued to the external face of the \efour-simplex \tfour{$\Delta_4$} that contains the \etwo-edge \ttwo{$e$} and some other face is glued to the external face of the \efive-simplex \tfive{$\Delta_5$} that contains the \etwo-edge \ttwo{$e$}.
Note that out of the newly added edges we get a pattern \tsix{$\mathsf{{}_W\!{}^M\!{}_W\!{}^M}$}.

\end{enumerate}

Henceforth we will denote the constructed triangulation by $\triang$ and use the notions of internal and external with respect to $\triang$.

In particular all \eone-edges are internal, all \ethree-, \efour-, \efive- and \esix-edges are external and there are both internal and external \etwo-edges.

\smallskip
\emph{Non-planarity.}
The complex $\triang$ contains a subcomplex being an edge subdivision $\Gamma$ of $\katt$: take all \esix-edges (i.e. \tsix{$\mathsf{{}_W\!{}^M\!{}_W\!{}^M}$}), the \tone{axis}, the two external 2-paths

that join the south pole with the middle \efour-vertices of the fragments \tsix{$\mathsf{M}$} and the two external 2-paths

that join the north pole with the middle \efour-vertices of the fragments \tsix{$\mathsf{W}$}.
One can check that $\Gamma$ is a full subcomplex of $\triang$ and it is an edge subdivision of the graph $\katt$ such that to each edge of $\katt$ there corresponds a path of length at least 2 in $\Gamma$ with an exception of the edge corresponding to the \tone{axis}.
Therefore, in view of Remark \ref{u:tnieplan}, the complex $\triang$ is \sg-non-planar.

\begin{figure}
\iflight
	\centerline{\input{fighiperbolicznosc.tex}}
\else
	\includegraphics[width=0.80\textwidth]{20190719645}
\fi
\centering
\caption{The four remaining cases of checking the no-$\triangle$ and no-$\square$ conditions for $\triang$. Symbols \wiea{} and \wieb{} denote the endpoints of an edge potentially belonging to some $\triangle$ or $\square$, symbols \sasa{} and \sasb{} denote the neighbours of \wiea{} and \wieb{} respectively. It suffices to check that each vertex denoted by both \sasa{} and \sasb{} spans a 2-simplex together with \wiea{} and \wieb{} and there is no edge with one endpoint marked only with \sasa{} and the other endpoint marked only with \sasb.}
\label{fig:hiperbolicznosc}
\end{figure}

\smallskip
\emph{No-$\triangle$ and no-$\square$.} The no empty triangle condition (shortly, \emph{no-$\triangle$}) is a part of checking flagness of the complex $\triang$. In means that there is no 3-cycle

in $\triang$ that does not span a 2-simplex.

We inductively check that after each stage \eone--\esix{} of the construction both no-$\triangle$ and no-$\square$ conditions are satisfied.
Stage \eone{} may be viewed as applying twice simplicial cone to a 8-cycle.

The cycle has no $\triangle$ and no $\square$, the operation of taking a cone preserves these properties. The stages \etwo, \efive{} cannot introduce neither a $\triangle$ nor a $\square$, since they consist in gluing 3-simplices along single faces.
Stage \efour{} may be viewed as a sequence of gluings of 8 \efour-simplices above the equator, each along one face, and next gluing 8 \efour-simplices below the equator, each along two faces, therefore a potential new $\triangle$ or $\square$ contains some \efour-edge having an end in some of \etwo-vertices.

Similarly, stages \ethree{} and \esix, give 3 types of edges (up to symmetry), that potentially may introduce a new

$\triangle$ or $\square$.
Figure \ref{fig:hiperbolicznosc}

contains all the already not considered cases and its description finishes the proof of this part.

\begin{figure}
\iflight
	\centerline{\input{figniesep.tex}}
\else
	\includegraphics[width=0.80\textwidth]{20190717640}
\fi
\centering
\caption{\emph{Left:} situation in the proof of 1-dimensionality, for simplicity drawn in dimension 2. \emph{Middle, right:} the complex $\rys{e}$ in the remaining 2 cases from the proof of inseparability with 2-complexes. On the left $e$ is a \eone-edge, on the right $e$ is a \etwo-edge. The bold lines mark the edge $e$, dashed lines mark the edges of the graph $\gra{e}$, the line
\raisebox{0.15em}{\protect\tikz{\protect\draw (0,0) -- (0.8,0);\protect\draw[decorate,decoration={snake,segment length=1mm,amplitude=0.3mm}] (0,0) -- (0.8,0)}}	(\raisebox{0.15em}{\protect\tikz{\protect\draw (0,0) -- (0.8,0);\protect\draw[decorate,decoration={crosses}] (0,0) -- (0.8,0)}})
marks the edges of the 2-paths that are surely external (internal).}
\label{fig:niesep}
\end{figure}

\smallskip
\emph{1-dimensional.}
In the remaining part of the proof we consider $\triang$ more often as a topological space than as a simplicial complex.

Let $\Delta$ be a simplex of $\triang$.
Embed $\triang$ as a 3-disk contained in the interior of a bigger 3-disk $D$ in a standard way with respect to the piecewise linear topology.

Let $U$ be a standard open normal neighbourhood of $\Delta$ in $D$.
See Figure \ref{fig:niesep}.
Then $U$ is homeomorphic with the interior of the 3-disk and $\triang\setminus U$ is
a deformation retract
of

$\triang\setminus\Delta$.

The Mayer-Vietoris sequence for the sets $\triang\setminus U$ and $(D\setminus\intr\triang)\setminus U$ yields an exact sequence $H^k(D\setminus U)\to H^k(\triang\setminus U)\oplus H^k((D\setminus\intr\triang)\setminus U)\to H^k(\partial\triang\setminus U)$.
Since $U$ is contractible and contained in the interior $\intr D$, the space $D\setminus U$ is a deformation retract of a 3-disk with one point removed, therefore the space $D\setminus U$ is homotopically equivalent to the boundary $\partial D\cong S^2$.
The space $(D\setminus\intr\triang)\setminus U$ is a deformation retract of $D\setminus\intr\triang$, which is homotopically equivalent to $S^2$.

Since $U\cap\partial\triang\neq\emptyset$, the space $\partial T\setminus U$ is a 2-manifold, whose each connected component has a non-empty boundary, so it is homotopically equivalent to some 1-complex.
Putting $k=2$ we get an exact sequence $\Z\to H^2(\triang\setminus U)\oplus\Z\to0$, so $H^2(\triang\setminus U)=0$.
For $k>2$ we have zeros on both sides, therefore $H^k(\triang\setminus U)=0$.

\smallskip
\emph{Inseparability.}
It is clear that $\triang$ is inseparable by a vertex or a pair of non-adjacent vertices.
The remaining part of the proof of inseparability relies on the following observation.

\begin{observation}\label{f:niesep}
Let $\sigma$ be a full subcomplex of $\,\triang$ of dimension at least 1 that is either a simplex or a suspension of a simplex.

Then, if $\sigma$ separates $\triang$, then it also separates its boundary $\partial\triang$.

\end{observation}

\begin{proof}

Equivalently one may remove

a standard open normal neighbourhood
$U$ of the complex $\sigma$.

It is sufficient to show that each point $x$ in $\triang\setminus U$ has a point from the set $\partial\triang\setminus U$ in its path component in $\triang\setminus U$. Take a path $\gamma$ that connects (in $\triang$) $x$ with a point in $\partial\triang$. If it crosses the boundary $\partial U$, then,
since $U$ is an open 3-disk whose boundary intersects the boundary

$\partial\triang$, we can get to the boundary $\partial\triang$ by a path contained in the boundary $\partial U$.

\end{proof}

The proof of inseparability consists in checking whether the intersections of appropriate complexes with the boundary $\partial\triang$ make it disconnected.
One can immediately prove inseparability by 1-simplices and suspensions of 0-simplices.

\smallskip
\emph{Inseparability by 2-complexes, no empty $\kacz$ and no $\kapi$.}

The no empty $\kacz$ and no $\kapi$ conditions are a part of checking flagness of $\triang$.
No empty $\kacz$ means that there is no $\kacz$ subgraph in the 1-skeleton $\triang^{(1)}$ that does not span a 3-simplex in $\triang$. No $\kapi$ means that there is no $\kapi$ subgraph in the 1-skeleton $\triang^{(1)}$.

The proof of inseparability by 2-complexes uses the following observation.

\begin{observation}\label{f:niesep2}
\begin{enumerate}[(i)]
\item A 2-simplex $\Delta$ disconnects the boundary $\partial\triang$ if and only if $\Delta\cap\partial\triang=\partial\Delta$.

\item If the suspension $\sigma$ of some 1-simplex disconnects the boundary $\partial\triang$, then either some 2-simplex of the complex $\sigma$ disconnects $\partial\triang$ or $\sigma\cap\partial\triang=\partial\sigma$.

\end{enumerate}
\end{observation}

If a 2-simplex $\Delta$ disconnects $\partial\triang$, then by the above observation its intersection with the boundary $\partial\triang$ consists of all of its edges.
We mark the one that appeared in the earliest of the stages \eone--\esix{} out (in case of having several such edges, mark an arbitrary one out).

Otherwise, if some suspension $\sigma$ of a 1-simplex $e$ disconnects $\triang$, but none of its 2-simplices does, then mark the edge $e$ out.

The proof method is as follows. We consider each 1-simplex $e$ of the complex $\triang$ and check that it was not marked out in the above procedure.
More precisely, if $e$ is internal, then we check the condition (\en1): there are no 2 2-paths

contained in the boundary $\partial\triang$ with endpoints in the vertices of $e$ such that their middle vertices do not span an edge (recall fullness in the definition of inseparability). If $e$ is external, we check the condition (\en2): there is no 2-path $\gamma$

with endpoints in the vertices of $e$ that is built of edges from stages not earlier than the one where $e$ was put and $\gamma\cup e$ does not span an external face.

Consider a $\kacz$ or $\kapi$ subgraph of $\triang^{(1)}$. Mark one of its edges $e$ that was put in the earliest of the stages \eone--\esix. Note that in the case of $\kapi$ we have in $\triang$ the 1-skeleton of a join of the edge $e$ with a 3-cycle.

Now we define for each edge $e$ the complex $\rys{e}$, that will contain all the content needed to check whether it has been marked out due to one of the four above reasons.

If $e$ is an internal edge, then we define $\rys{e}$ to be the full subcomplex of $\triang$ spanned on all 2-paths

that connect the endpoints of the edge $e$.

If $e$ is external, then $\rys{e}$ is the full subcomplex of $\triang$ spanned on all 2-paths

that connect the endpoints of the edge $e$ and are built of edges that were created in the stages that are not earlier than the stage when the edge $e$ was created.

For each edge $e$ we define the graph $\gra{e}$ as the induced subgraph of the 1-skeleton $\rys{e}^{(1)}$ spanned on the vertices that are not the endpoints of the edge $e$ (i.e. the middle points of the appropriate 2-paths).

In order to check that there are no empty $\kacz$, we check the condition (\ky1): for each edge $e'$ of the graph $\gra{e}$ the complex $\rys{e}$ has the simplicial join of $e$ with $e'$ as one of its 3-simplices.

In order to check that there is no $\kapi$, we check the condition (\ky2): there is no 3-cycle

in the graph $\gra{e}$.

Below we execute the mentioned proof strategy. We split it in cases depending on for which $i$ the edge $e$ is a (s$i$)-edge.

Our goal is to describe $\rys{e}$ and $\gra{e}$ accurately enough, so that one can easily check the conditions (\ky1), (\ky2) and the appropriate one of (\en1), (\en2).

\begin{enumerate}
\item[\eone]
3 cases.

If \tone{$e$} is the \tone{axis}, the complex $\rys{e}$ is the complex created in the stage \eone.
If \tone{$e$} is an \tone{edge of a meridian}, the complex $\rys{e}$ consists of 2 \etwo-paths with their middle vertices spanning a \ethree-edge, and 3 \eone-paths (which are internal). The graph $\gra{e}$ is a 5-cycle.

The case of \tone{$e$} being an \tone{edge of the equator} is on Figure \ref{fig:niesep}. The path consisting of 2 \efour-edges is external and at most one of the paths consisting of \etwo-edges is external, but the middle vertices of both of these paths are neighbours of the middle vertex of the path consisting of \efour-edges.

\item[\etwo] 3 cases.

If \ttwo{$e$} contains a \tone{pole} or is an external edge containing some vertex of the \tone{equator}, then $\rys{e}$ consists of two neighbouring \ethree-2-simplices or a \ethree-2-simplex and a \efour-2-simplex respectively.

If \ttwo{$e$} contains a vertex of the \tone{equator} and is internal, see Figure \ref{fig:niesep}.

\item[\ethree] 2 cases. The complex $\rys{e}$

is either empty

or consists of a \efive-2-simplex containing the edge \tthree{$e$}.

\item[\efour] If \tfour{$e$} is a \efour-edge with the endpoints outside the \tone{equator},

we have 3 cases, the complex $\rys{e}$

is either empty
or consists of a single \esix-2-simplex
or two \esix-2-simplices.
If \tfour{$e$} is a \efour-edge with one endpoint on the \tone{equator}, we have 2 cases, in each of them the complex $\rys{e}$ consists of a single \esix-2-simplex.

\item[\efive] All \efive-edges are external and there is no 2-simplex, whose edges are only \efive- or

\esix-edges, therefore the complex $\rys{e}$

is empty.

\item[\esix] As above, the complex $\rys{e}$ is empty.

\end{enumerate}

\smallskip
\emph{Inseparability by 3-complexes.}
The proof of this part uses the following observation that enables us to reduce the problem to the already considered case of inseparability by 2-complexes.

\begin{observation}\label{f:niesep3}
Let $\Delta$ be a 2-face of a 3-simplex $\sigma$ of $\triang$.
Define (a subspace) $\tra{\sigma}{\Delta}:=(\sigma\cap\partial\triang)\setminus\Delta$.
Assume that the closure $\overline{\tra{\sigma}{\Delta}}\cap\Delta$ is either empty or is a path.
Then:

\begin{enumerate}[(i)]
	\item if a 3-simplex $\sigma$ disconnects the boundary $\partial\triang$, then the 2-simplex $\Delta$ disconnects the boundary $\partial\triang$,

	\label{f:niesep31}

	\item if $\sigma'$ is a 3-simplex such that the complex $\sigma\cup\sigma'$ is a full subcomplex of $\triang$ that is a suspension of the face $\Delta$

	and
	the complex $\sigma\cup\sigma'$ disconnects the boundary $\partial\triang$, then the 3-simplex $\sigma'$ disconnects the boundary $\partial\triang$.

	\label{f:niesep32}

\end{enumerate}
\end{observation}

\begin{proof}

The complex $\overline{\tra{\sigma}{\Delta}}$ is a cone over $\overline{\tra{\sigma}{\Delta}}\cap\Delta$.
If the latter is empty, then the former is a single vertex and the observation follows.
Otherwise $\overline{\tra{\sigma}{\Delta}}$ is a deformation retract of $\overline{\tra{\sigma}{\Delta}}\cap\Delta$, which gives a
homotopical equivalence between
$\partial\triang\setminus\Delta$
and $\partial\triang\setminus\sigma$ and, in case of \ref{f:niesep32},
a homotopical equivalence between $\partial\triang\setminus\sigma$ and $\partial\triang\setminus(\sigma\cup\sigma')$.

\end{proof}

The proof consists in assigning to each 3-simplex some of its 2-faces $\Delta_{\sigma}$ and then assigning to each internal 2-simplex $\Delta$ a 3-simplex $\sigma_{\Delta}$ in such a way that the pairs $(\sigma,\Delta_{\sigma})$ and $(\sigma_{\Delta},\Delta)$ satisfy the assumptions of the Observation \ref{f:niesep3}.

Then the inseparability by 3-complexes follows in such a way. If $\sigma$ is a 3-simplex of $\triang$ that disconnects the boundary $\partial\triang$, then by Observation \ref{f:niesep3}\ref{f:niesep31} we have that its 2-dimensional face $\Delta_{\sigma}$ disconnects the boundary $\partial\triang$. We have excluded that in the previous part of the proof.

If a suspension  $\tau$ of a 2-simplex $\Delta$ is a subcomplex of $\triang$ disconnecting its boundary $\partial\triang$, then the 3-simplex $\sigma_{\Delta}$ is one of simplices of $\tau$ and, denoting by $\sigma'$ the other one, we have that by Observation \ref{f:niesep3}\ref{f:niesep32} the 3-simplex $\sigma'$ disconnects the boundary $\partial\triang$. We have just excluded it above.

Below we show some pairs $(\sigma,\Delta)$ and the spaces $\tra{\sigma}{\Delta}$. These pairs will we the pairs described in the beginning of this paragraph.

We do this in the order given by the stage in which the complex $\sigma$ was constructed.

We leave checking that the described pairs satisfy the assumptions of Observation \ref{f:niesep3} and verifying that each internal face has been paired with some 3-simplex to the reader.

\begin{enumerate}
\item[\eone] The intersection of any \eone-3-simplex \tone{$\sigma$} with the boundary $\partial\triang$ consists of 4 points, in particular $\tra{\mone{\sigma}}{\mone{\Delta}}$ is a 1 point for any \eone-face \tone{$\Delta$} of the \eone-simplex \tone{$\sigma$}.

\item[\etwo] For any \etwo-3-simplex \ttwo{$\sigma$} and \efour-3-simplex that share a \etwo-face \ttwo{$\Delta$} we have, that $\tra{\ttwo{\sigma}}{\ttwo{\Delta}}$ is a single edge.

\item[\ethree] Consider a \ethree-3-simplex \tthree{$\sigma$}. Its \ethree-face \tthree{$\Delta$} that touches the \tone{equator} has the property that $\tra{\tthree{\sigma}}{\tthree{\Delta}}$ is a single face. Consider any \etwo-face \ttwo{$\Delta'$}, which is shared by the \ethree-3-simplex \tthree{$\sigma$} and a \etwo-3-simplex. If \tthree{$\sigma$} has 2 external faces, then $\tra{\tthree{\sigma}}{\ttwo{\Delta'}}$ consists of a suspension of an edge. If \tthree{$\sigma$} has one external face, $\tra{\tthree{\sigma}}{\ttwo{\Delta'}}$ it is single face.

\item[\efour] Let \tfour{$\Delta$} be a \efour-face of a \efour-3-simplex \tfour{$\sigma$}, which \tfour{$\Delta$} shares with a \efour-3-simplex. The simplex \tfour{$\sigma$} can lie in $\triang$ in 3 ways, we have that $\tra{\tfour{\sigma}}{\tfour{\Delta}}$ is either a  single edge or a single face or a suspension of an edge.

\item[\efive] Let \tfive{$\sigma$} be a  \efive-3-simplex and \tthree{$\Delta$} its \ethree-face. Then $\tra{\tfive{\sigma}}{\tthree{\Delta}}$ is a single face.

\item[\esix] For each \esix-3-simplex \tsix{$\sigma$} and its face $\Delta$, that is internal, we have that $\tra{\tsix{\sigma}}{\Delta}$ is a suspension of an edge.
\end{enumerate}

\smallskip
\emph{Flag.} Consider a $n$-clique subgraph of 1-skeleton $\triang^{(1)}$, that does not span a simplex. We have proved that $n\geq 5$. Therefore the 1-skeleton $\triang^{(1)}$ contains a $\kapi$ subgraph, which has also been excluded.
\end{proof}

\begin{remark}
	A slight modification of the triangulation $\triang$ gives infinitely many triangulations of the disk $D^3$ that give a Menger curve boundary.
	Fix $n\geq2$. In stage \eone{} take a join of a $4n$-cycle

	with an edge, leave the stages \etwo--\efour{} unchanged, and execute the stages \efive{} and \esix{} so that the pattern \tsix{$\mathsf{{}_W\!{}^M}$}, that exists around the equator, repeats $n$ times (note that for $n=2$ we get $\triang$).
	The proof that such triangulation satisfies the desired properties is almost the same as for $\triang$.
	For example the proof of inseparability uses that fact that the equator is of length greater than 4 and considers the shape of some small fragments of the considered triangulation, that do not depend on $n$.

\end{remark}

config: arxiv


TITLE: Statistics & Probability -Distribution problem
QUESTION [0 upvotes]: 10% of the chocolate bars that are produced in a factory have unacceptable shape. In a sample of 1000 chocolate bars find the probability that the number of unacceptable shapes is
(A) less than 80
(B) between 90 and 115
(C) 120 or more.

REPLY [1 votes]: The number of unacceptable chocolate bars in a sample of $1000$ is a random variable $X$ which has the binomial distribution with parameters $n=1000$ and $p=0.10$, in symbols $$X \sim \mathrm{Bin}(n=1000,\,p=0.10)$$
To calculate the required probabilities we will use the normal approximation to the binomial distribution, that is $$X \sim \mathrm{N}\left(\mu=np, σ^2=np(1-p)\right)$$ approximately. Here $μ=np=1000\cdot0.1=100$ and $σ^2=np(1-p)=100\cdot0.9=90$. Applying also the continuity correction we have that

For A) $$\begin{align*}P(X<80)&=P(X\le79) \approx P\left(\frac{X-μ}{σ}\le\frac{79+1/2-100}{\sqrt{90}}\right)=P(Z\le -2.16)=\\ \\&=Φ(-2.16)=1-Φ(2.16)=0.015\end{align*}$$ using the normal distribution tables.
For B) $$\begin{align*}P(90<X<115)&=P(X\le114)-P(X\le90)\approx \\& \approx P\left(\frac{X-μ}{σ}\le\frac{114+1/2-100}{\sqrt{90}}\right)-P\left(\frac{X-μ}{σ}\le\frac{90+1/2-100}{\sqrt{90}}\right)\\&=\ldots \end{align*}$$
For C) $$\begin{align*}P(X\ge120)&=1-P(X<120)=1-P(X\le119)\approx\\ \\&\approx1-P\left(\frac{X-μ}{σ}\le\frac{119+1/2-100}{\sqrt{90}}\right)=\ldots \end{align*}$$


text:
\begin{document}

\maketitle

\section*{ABSTRACT}

In this paper, five different approaches for reduced-order modeling of brittle fracture in geomaterials, specifically concrete, are presented and compared.
Four of the five methods rely on machine learning (ML) algorithms to approximate important aspects of the brittle fracture problem.
In addition to the ML algorithms, each method incorporates different physics-based assumptions in order to reduce the computational complexity while maintaining the physics as much as possible.
This work specifically focuses on using the ML approaches to model a 2D concrete sample under low strain rate pure tensile loading conditions with 20 preexisting cracks present.
A high-fidelity finite element-discrete element model is used to both produce a training dataset of 150 simulations and an additional 35 simulations for validation.
Results from the ML approaches are directly compared against the results from the high-fidelity model.
Strengths and weaknesses of each approach are discussed and the most important conclusion is that a combination of physics-informed and data-driven features are necessary for emulating the physics of crack propagation, interaction and coalescence.
All of the models presented here have runtimes that are orders of magnitude faster than the original high-fidelity model and pave the path for developing accurate reduced order models that could be used to inform larger length-scale models with important sub-scale physics that often cannot be accounted for due to computational cost.

\newline
\newline
\textbf{Keywords:}~Brittle fracture, machine learning, crack interaction, artificial neural networks.

\input{Sections/S1_Intro}

\input{Sections/S2_HOSS}

\input{Sections/S3_ML}

\input{Sections/S4_Results}

\input{Sections/S5_Discussion}

\input{Sections/S6_Summary}

\section*{ACKNOWLEDGMENTS}
The authors would like to acknowledge support from the Los Alamos National Laboratory Directed Research and Development (LDRD) Program through the Directed Research Project \# 20170103DR.
MKM and SK authors also thank the support of the LANL LDRD Early Career Award 20150693ECR.
MKM gratefully acknowledges the support of LANL Chick-Keller Postdoctoral Fellowship through Center for Space and Earth Sciences (CSES).
Authors thank the LANL Institutional Computing program for their support in generating data used in this work.

\bibliographystyle{unsrt}
\bibliography{Master_References/paper_bib}

\end{document}


TITLE: What is the probability of measuring $p$ in the momentum space?
QUESTION [1 upvotes]: I have a wave function $\Psi (x,t)$. According to the Max Born postulate, $\lvert\Psi (x,t)\rvert ^2$ is the probability density. This quantity specifies the probability, per length of the $x$ axis, of finding the particle near the coordinate $x$ at time $t$.
If at $t=0$ I make a Fourier transform for the momentum space, $$\phi(p)=\frac{1}{\sqrt{2 \pi \hbar}} \int _{-\infty} ^{+\infty} \psi(x)e^{-ipx/\hbar} dx$$ does $\vert\phi(p)\rvert ^2$ specifies the probability of finding the particle near the momentum $p$ at time $t=0 \hspace{1mm}$?
In this sense, given $\Psi(x,t)$, how could I write $\phi(p)$ at any time $t$, i.e. $\Phi(p,t)\hspace{1mm}$?

REPLY [3 votes]: You’re exactly right: $|\phi(p)|^2$ gives the probability of measuring momentum $p$ at time $t=0$. An analogous relation holds for the time-dependent case:
$$\Phi(p,t)=\frac{1}{\sqrt{2\pi\hbar}}\int_{-\infty}^{\infty}dx e^{-i px/\hbar}\Psi(x,t)$$
This is simply due to the fact that one independently transforms between position and momentum space and between time and frequency space.
For a “proof” that this is the case, consider:
$$\Phi(p,t)=\langle p|\Psi(t)\rangle=\int _{-\infty}^{\infty}dx \langle p|x\rangle\langle x|\Psi(t)\rangle= \int _{-\infty}^{\infty}dx \langle p|x\rangle \Psi(x,t)$$
Now, note that a free particle momentum eigenstate in the position basis is a plane wave $\langle x|p\rangle= \frac{1}{\sqrt{2\pi\hbar}} e^{i px/\hbar} $, so $\langle p|x\rangle=\langle x|p\rangle^*= \frac{1}{\sqrt{2\pi\hbar}} e^{-i px/\hbar}$. Finally then, we arrive at:
$$ \boxed{ \Phi(p,t)= \frac{1}{\sqrt{2\pi\hbar}} \int _{-\infty}^{\infty}dx  e^{-i px/\hbar} \Psi(x,t)}$$


TITLE: Biggest Lynch-Bell number
QUESTION [6 upvotes]: A number $n$ is called a Lynch-Bell number if its digits are all distinct and  $n$ is divisible by each digit (the sequence is presented HERE). It can be found in many places that the biggest Lynch-Bell number is 9867312 and it can be proved with computer easily.
Bet let's do the same by doing some elementary math. Obviously, digit 0 must be excluded. And digits 2 and 5 cannot be both included in $n$ because such $n$ would end in zero. And then... what?

REPLY [9 votes]: Introduction
A fitting reply to people using the computer on this one.
No nine or ten digit Lynch Bell Numbers
To start with, we claim that there is no eight,nine or ten digit Lynch Bell number. Anything with $11$  or more digits must have two digits as the same by the pigeonhole principle.
Any ten digit Lynch Bell number contains zero as a digit, contradiction.
Consider a nine digit Lynch Bell number. It certaily must avoid zero, and therefore has the digits $123456789$ in some order. This contradicts the fact that $2 \times 5   = 10$ is a multiple of the number.
No eight digit Lynch Bell Numbers
Consider an eight digit Lynch bell number. If it has a zero, we have a contradiction. On the other hand, if it has a five, then it has at least one of $2$ or $4$ , since we can exclude only two digits, and $0$ is already out. But then it is a multiple of $10$ either way. In short, such a number must not contain zero or five. Therefore, its digits  are precisely $12346789$.
Which is an issue, since the sum of the digits of this number is $40$, so by our usual divisibility  test , it is not a multiple of $3$ (or $9$).
Hence, no eight digit Lynch bell number exists!
Seven digit Lynch Bell - What to Exclude?
Coming to seven digit Lynch Bell numbers, we know they have seven different digits. By our previous logic, $0$ must be excluded. Now, note that if $5$ is in the number, then at least one of $2,4$ or $6$ is in the number, since all these cannot be excluded. However, each of these gives that our number is a multiple of $10$ so we have a contradiction.
Hence, $0$ and $5$ are out. The question is of the third digit to be excluded.
At this stage, all we need to do is note that the divisibility test comes to our rescue again. Indeed, we have to exclude some number from $12346789$, whose sum of digits is $40$. Excluding $9$ gives rise to a number whose sum of digits is $31$ and which is not divisible by $3$, a contradiction. Hence, $9$ cannot be excluded.
But then, the number must be a multiple of $9$, since $9$ is one of the digits of the number! Hence, the sum of digits must be a multiple of $9$. Indeed, one sees that $40-\color{blue}{4} = 36$ and hence $4$ must be the excluded one, since if anything else(bar $9$) is excluded we won't get a multiple of $9$.
Where are we, and what now?
In conclusion, any seven digit Lynch Bell number must consist precisely of the digits $1236789$. Fantastic. Now, life is actually quite simple.
A logical point would be to start from the largest possible candidate for a Lynch Bell number, namely $9876321$.
Why the very large ones don't work
We now eliminate all numbers of the form $987....$ from being a Lynch Bell number.
Recall the criteria of divisibility by eight. Indeed, a number is divisible by $8$ if and only if its last three digits are. Therefore, what combinations of $1236$ give numbers divisible by $8$? Indeed, only $136,216,312,632$ give a positive result.
At this stage, we note that $987....$ is divisible by $7$ if and only if $....$ in that order is divisible by $7$. Therefore, all we need to do is check whether any of $2136,3216,6312,1632$ are divisible by $7$. Indeed, none of them are, and you don't even need to do the actual division in some cases. For example , $2136$ is not divisible by $7$ because $36$ is not, and $21$ is.
Therefore, it follows that $987....$ is not a Lynch Bell number for any combination of $....$
Conclusion
The numbers which come next in the descending order is $9867...$ Indeed, note that $...$ must end with $2$, since we have a multiple of $2$. We now see that $9867312$ is a Lynch Bell number, by seeing that it has distinct digits and is divisible by each of them.
We have already shown that all numbers larger than $9867312$ are not Lynch Bell numbers. This allows us to conclude that $9867312$ is the largest Lynch Bell number, with a handful of divisions by hand and no computer.


text:
\section{Entropy-Regularized Optimal Transport between Gaussians}

Solving \eqref{eq:kantorovich} can be quite challenging, even in a discrete setting~\citep{Peyre2019computational}. Adding an entropic regularization term to \eqref{eq:kantorovich} results in a problem which can be solved efficiently using Sinkhorn's algorithm~\citep{cuturi2013sinkhorn}. Let $\sigma > 0$. This corresponds to solving the following problem:

\begin{align}\label{eq:ent_ot}
\OT_\sigma(\alpha, \beta) \defeq \min_{\pi \in \Pi(\alpha, \beta)} \int_{\RR^d\times\RR^d} \| x - y \|^2 \dd\pi(x, y) + 2\sigma^2 \KL(\pi \| \alpha\otimes\beta),
\end{align}

where $\KL(\pi \| \alpha\otimes\beta) \defeq \int_{\RR^d} \log\left(\tfrac{\dd\pi}{\dd\alpha\dd\beta}\right)\dd\pi$ is the Kullback-Leibler divergence (or relative entropy).
As in the original case \eqref{eq:kantorovich}, $\OT_\sigma$ can be studied with centered measures (i.e zero mean) with no loss of generality:

\begin{lemma}
\label{lemma:centering}
Let $\alpha, \beta \in \Pcal$ and  $\bar{\alpha}, \bar{\beta}$ their respective centered transformations. It holds that
\begin{equation}
    \label{eq:centering}
    \OT_\sigma(\alpha, \beta) = \OT_\sigma(\bar{\alpha}, \bar{\beta}) +  \| \ba - \bb \|^2.
\end{equation}
\end{lemma}

\paragraph{Dual problem and Sinkhorn's algorithm.}

Compared to \eqref{eq:kantorovich}, \eqref{eq:ent_ot} enjoys additional properties, such as the uniqueness of the solution $\pi^*$. Moreover, problem \eqref{eq:ent_ot} has the following dual formulation:

\begin{align}
\label{eq:dual-ent-ot}
\OT_{\sigma}(\alpha, \beta) = &\max_{\substack{f \in \Lcal_1(\alpha), \\ g \in \Lcal_1(\beta)}} \Esp_\alpha(f) + \Esp_\beta(g) - 2\sigma^2\left( \int_{{\RR^d} \times {\RR^d}}\hspace{-2em} e^{\tfrac{f(x) + g(y) - \|x-y\|^2}{2\sigma^2}}\dd\alpha(x)\dd\beta(y) -1\right).
\end{align}

If $\alpha$ and $\beta$ have finite second order moments, a pair of dual potentials $(f, g)$ is optimal if and only they verify the following optimality conditions $\beta$-a.s and $\alpha$-a.s respectively~\cite{mena19}:

\begin{align}
    \label{eq:optimality-potentials}
    \begin{split}
    e^{\tfrac{f(x)}{2\sigma^2}} \left(\int_{\RR^d} e^{\tfrac{-\|x-y\|^2 + g(y)}{2\sigma^2}}  \dd\beta(y)\right) = 1, \quad
    e^{\tfrac{g(x)}{2\sigma^2}} \left(\int_{\RR^d} e^{\tfrac{-\|x-y\|^2 + f(y)}{2\sigma^2}}  \dd\alpha(y)\right) = 1.
    \end{split}
\end{align}

Moreover, given a pair of optimal dual potentials $(f, g)$, the optimal transportation plan is given by

\begin{equation}
    \label{eq:transportion_plan}
    \frac{\dd \pi^\star}{\dd \alpha \dd \beta}(x, y) = e^{\frac{f(x) + g(y) - \|x-y\|^2}{2\sigma^2}}.
\end{equation}

Starting from a pair of potentials $(f_0, g_0)$, the optimality conditions \eqref{eq:optimality-potentials} lead to an alternating dual ascent algorithm, which is equivalent to Sinkhorn's algorithm in log-domain:

\begin{align}
\label{eq:alg_sinkhorn}
    \begin{split}
    g_{n+1} &= \left(y \in {\RR^d} \rightarrow -2\sigma^2 \log\int_{\RR^d} e^{\tfrac{-\|x- y\|^2 + f_n(x)}{2\sigma^2}} \dd\alpha(x)\right),\\
    f_{n+1} &= \left(x \in {\RR^d} \rightarrow -2\sigma^2 \log\int_{\RR^d} e^{\tfrac{-\|x-y\|^2 + g_{n + 1}(y)}{2\sigma^2}}  \dd\beta(y)\right).
    \end{split}
\end{align}

\citet{sejourne19} showed that when the support of the measures is compact, Sinkhorn's algorithm converges to a pair of dual potentials. Here in particular, we study Sinkhorn's algorithm when $\alpha$ and $\beta$ are Gaussian measures.

\paragraph{Closed form expression for Gaussian measures.}\label{subsec:ent_ot_gaussians}

\begin{theorem}\label{thm:otclosedform}
Let $\bA, \bB \in \PD$ and $\alpha \sim \Ncal(\ba, \bA)$ and $\beta \sim \Ncal(\bb, \bB)$. Define $\bD_\sigma = (4\bA^{\frac{1}{2}} \bB \bA^{\frac{1}{2}} +\sigma^4 \Id )^{\frac{1}{2}}$. Then,
\begin{equation}\label{eq:means_plus_bures_sk}
    \OT_{\sigma}(\alpha, \beta) = \|\ba - \bb\|^2 + \Bcal^2_{\sigma}(\bA, \bB), \text{ where }
\end{equation}

\begin{align}
\label{eq:otclosedform}
\begin{split}
\Bcal^2_{\sigma}(\bA, \bB) &= \tr(\bA) + \tr(\bB) - \tr(\bD_\sigma) + d\sigma^2(1 - \log(2\sigma^2)) + \sigma^2\log\det\left(\bD_\sigma + \sigma^2 \Id\right).
\end{split}
\end{align}
Moreover, with $\bC_{\sigma} = \frac{1}{2}\bA\rt \bD_\sigma\bA\mrt -\frac{\sigma^2}{2} \Id$, the Sinkhorn optimal transportation plan is also a Gaussian measure over $\RR^d\times \RR^d$ given by
\begin{equation}\label{eq:sinkorn_plan}
    \pi^\star \sim
    \Ncal\left(\left(
            \begin{smallmatrix}
            \ba \\
            \bb
            \end{smallmatrix}\right),
         \left(\begin{smallmatrix}
         \bA & \bC_\sigma \\ \bC_\sigma^\top & \bB
         \end{smallmatrix}\right)
        \right).
\end{equation}
\end{theorem}

\begin{remark}
While for our proof it is necessary to assume that $\bA$ and $\bB$ are positive definite in order for them to have a Lebesgue density, notice that the closed form formula given by \Cref{thm:otclosedform} remains well-defined for positive semi-definite matrices. Moreover, unlike the Bures-Wasserstein metric, $\OT_{\sigma}$ is differentiable even when $\bA$ or $\bB$ are singular.
\end{remark}

The proof of \ref{thm:otclosedform} is broken down into smaller results, \Cref{prop:sinkhorn-transform,prop:bures_sinkhorn_convergence,prop:closed_form_matrix,lemma:optim-loss}. Using \Cref{lemma:centering}, we can focus in the rest of this section on centered Gaussians without loss of generality.

\paragraph{Sinkhorn's algorithm and quadratic potentials.}

We obtain a closed form solution of $\OT_\sigma$ by considering quadratic solutions of \eqref{eq:optimality-potentials}. The following key proposition characterizes the obtained potential after a pair of Sinkhorn iterations with quadratic forms.
\begin{proposition}
\label{prop:sinkhorn-transform}
Let $\alpha \sim \Ncal(0, \bA)$ and $\beta \sim \Ncal(0, \bB)$ and the Sinkhorn transform $T_\alpha: \RR^{\RR^d} \to \RR^{\RR^d}$:
\begin{equation}
    T_\alpha(h)(x) \defeq - \log\int_{\RR^d} e^{\tfrac{-\|x- y\|^2}{2\sigma^2} + h(y)} \dd\alpha(y).
\end{equation}
Let $\bX \in \Scal_d$.
If $h = m + \Qcal(\bX)$ i.e  $h(x) = m - \frac{1}{2} x^\top \bX x$ for some $m \in \RR$, then $T_\alpha(h)$ is well-defined if and only if  $\bX' \defeq \sigma^2\bX + \sigma^2\bA^{-1} + \Id \succ 0$. In that case,
\begin{enumerate}[(i)]
    \item $T_\alpha(h)= \Qcal(\bY) + m'$ where $\bY = \frac{1}{\sigma^2}(\bX'^{-1} - \Id)$ and $m' \in \RR$ is an additive constant,
    \item $T_\beta(T_\alpha(h))$ is well-defined and is also a quadratic form up to an additive constant, since $\bY' \defeq \sigma^2\bY + \sigma^2\bB^{-1} + \Id = \bX'^{-1} + \sigma^2 \bB^{-1} \succ 0$ and (i) applies.
\end{enumerate}
\end{proposition}

Consider the null inialization $f_0 = 0 = \Qcal(0)$.
Since $\sigma^2 \bA^{-1} + \Id \succ0$, \Cref{prop:sinkhorn-transform} applies with $\bX = 0$ and a simple induction shows that $(f_n, g_n)$ remain quadratic forms for all $n$. Sinkhorn's algorithm can thus be written as an algorithm on positive definite matrices.
\begin{proposition}
\label{prop:bures_sinkhorn_convergence}
Starting with null potentials, Sinkhorn's algorithm is equivalent to the iterations:
\begin{align}

    \label{eq:sinkhorn-fg}
    \bF_{n+1} = \sigma^2 \bA^{-1} + \bG^{-1}_n, \hspace{3em}
    \bG_{n+1} =\sigma^2 \bB^{-1} + \bF^{-1}_{n+1},

\end{align}
 with $\bF_0 = \sigma^2 \bA^{-1} + \Id$ and $\bG_0 = \sigma^2 \bB^{-1} + \Id$.
\end{proposition}
Moreover, the sequence $(\bF_n, \bG_n)$ is contractive (in the matrix operator norm) and converges towards a pair of positive definite matrices $(\bF, \bG)$.
At optimality, the dual potentials are determined up to additive constants $f_0$ and $g_0$: $\frac{f}{2\sigma^2} = \Qcal(\bU) + f_0$ and $\frac{g}{2\sigma^2} = \Qcal(\bV) + g_0$ where $\bU$ and $\bV$ are given by

\begin{align}
\label{eq:changeofvariable}

    \bF = \sigma^2 \bU + \sigma^2 \bA^{-1} + \Id, \hspace{4em}
    \bG = \sigma^2 \bV + \sigma^2 \bB^{-1} + \Id.

\end{align}

\paragraph{Closed form solution.}

Taking the limit of Sinkhorn's equations \eqref{eq:sinkhorn-fg} along with the change of variable \eqref{eq:changeofvariable},
there exists a pair of optimal potentials determined up to an additive constant:

\begin{align}
\label{eq:optim-dual}

    \frac{f}{2\sigma^2} = \Qcal(\bU) = \Qcal\left(\frac{1}{\sigma^2}(\bG^{-1} - \Id)\right), \hspace{2em}
    \frac{g}{2\sigma^2} = \Qcal(\bV) = \Qcal\left(\frac{1}{\sigma^2}(\bF^{-1} - \Id)\right),

\end{align}

where $(\bF, \bG)$ is the solution of the fixed point equations

\begin{align}
    \label{eq:optim-fg}
    \bF = \sigma^2 \bA^{-1} + \bG^{-1}, \hspace{4em}
    \bG =\sigma^2 \bB^{-1} + \bF^{-1}.
\end{align}

Let $\bC \defeq \bA\bG^{-1}$. Combining both equations of \eqref{eq:optim-fg} in one leads to $\bG = \sigma^2 \bB^{-1} + (\bG^{-1} + \sigma^2 \bA^{-1})^{-1}$, which can be shown to be equivalent to

\begin{equation}\label{eq:fixedpoint-C}
\bC^2 + \sigma^2\bC - \bA\bB = 0.
\end{equation}

Notice that since $\bA$ and $\bG^{-1}$ are positive definite, their product $\bC = \bA\bG^{-1}$ is similar to $\bA\rt\bG^{-1}\bA\rt$. Thus it has positive eigenvalues. \Cref{prop:closed_form_matrix} provides the only feasible solution of \eqref{eq:fixedpoint-C}.

\begin{proposition}
\label{prop:closed_form_matrix}
Let $\sigma^2 \geq 0$ and $\bC$ satisfying \Cref{eq:fixedpoint-C}. Then,
 \begin{align}
 \bC = \left(\bA\bB + \frac{\sigma^4}{4} \Id\right)\rt -\tfrac{\sigma^2}{2} \Id
     = \bA\rt(\bA\rt\bB\bA\rt + \tfrac{\sigma^4}{4} \Id)\rt\bA\mrt -\tfrac{\sigma^2}{2} \Id
\label{eq:closed-form-C}.
\end{align}
\end{proposition}
\begin{corollary}
\label{cor:closedform-potentials}
The optimal dual potentials of \eqref{eq:optim-dual} can be given in closed form by:
\begin{equation}
    \begin{split}
    \bU =  \frac{\bB}{\sigma^2}(\bC +
    \sigma^2\Id)^{-1} - \frac{\Id}{\sigma^2}
    ,
    \hspace{2em}
    \bV =  (\bC +
    \sigma^2\Id)^{-1}\frac{\bA}{\sigma^2} - \frac{\Id}{\sigma^2}.
    \end{split}
\end{equation}
Moreover, $\bU$ and $\bV$ remain well-defined even for singular matrices $\bA$ and $\bB$.
\end{corollary}

\paragraph{Optimal transportation plan and $\OT_\sigma$.}
Using \Cref{cor:closedform-potentials} and \eqref{eq:optim-dual}, \Cref{eq:transportion_plan} leads to a closed form expression of $\pi$. To conclude the proof of \Cref{thm:otclosedform}, we introduce lemma \ref{lemma:optim-loss} that computes the $\OT_\sigma$ loss at optimality. Detailed technical proofs are provided in the appendix.

\begin{lemma}
\label{lemma:optim-loss}
Let $\bA, \bB, \bC$ be invertible matrices such that
$\bH = \left(\begin{smallmatrix}
       \bA & \bC \\
         \bC^\top  & \bB\\
    \end{smallmatrix}\right) \succ 0$.
Let $\alpha = \Ncal(0, \bA), \beta = \Ncal(0, \bB)$, and $\pi = \Ncal(0, \bH)$. Then,
\begin{align}
    &\int_{\RR^d\times\RR^d} \|x - y\|^2 \d \pi(x, y) = \tr(\bA) + \tr(\bB) - 2\tr(\bC), \label{eq:optim-transport}\\
   &\KL\left(\pi\|\alpha\otimes\beta\right) = \tfrac{1}{2}\left( \log\det \bA + \log\det \bB - \log\det \left(\begin{smallmatrix} \bA & \bC \\ \bC^T & \bB \end{smallmatrix}\right) \right).
   \label{eq:optim-ent}
\end{align}
\end{lemma}


TITLE: Inequality with cardinal numbers
QUESTION [0 upvotes]: I want to check if the following statement holds:
If $a, b, c $ are cardinal numbers and $a<b$ then $a^c<b^c$.
If the statement would hold, given that there is a bijective funcion $f: a \to b$ there will also be a bijective function $g: a^c \to b^c$.
Since $f$ is bijective, we have that $f(a)=b$.
So there will be a $y$ such that $f(a^c)=y$.
Is this right so far? If so, how can we continue?

REPLY [4 votes]: Your statement is false. For example, $\mathbb{N}^\mathbb{N}$ and $2^\mathbb{N}$ have the same cardinality - put another way, $$(\aleph_0)^{\aleph_0}=2^{\aleph_0}.$$
We can see this by invoking basic cardinal arithmetic rules, as $$2^{\aleph_0}\le (\aleph_0)^{\aleph_0}\le (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\times\aleph_0}=2^{\aleph_0},$$ with the first inequality being trivial, the second following from the weak monotonicity of exponentiation (which is also pretty trivial), and the third and fourth following from the definitions of cardinal multiplication and exponentiation (together with a bit of Currying).
However, we can also see this directly via Cantor-Bernstein (which, as a reminder, does not require Choice). Namely, fix your favorite pairing function $\langle\cdot,\cdot\rangle:\mathbb{N}^2\rightarrow\mathbb{N}$, and given $f:\mathbb{N}\rightarrow\mathbb{N}$ let $\hat{f}:\mathbb{N}\rightarrow 2$ be defined by $$\hat{f}(\langle a,b\rangle)=1\quad\iff\quad f(a)=b$$ (and $\hat{f}(\langle a,b\rangle)=0$ otherwise). It's easy to check that the map $$f\mapsto\hat{f}$$ is an injection from $\mathbb{N}^\mathbb{N}$ to $2^\mathbb{N}$. Since the identity provides an injection the other way, Cantor-Bernstein gives a bijection.
(Incidentally, your "proof" also gets cardinal inequality wrong: "$a<b$" means that there is an injection from $a$ to $b$ but there is not an injection from $b$ to $a$.)

It's worth pointing out that increasing the exponent doesn't necessarily increase the whole power either: letting $\kappa=2^{\aleph_1}$, we have $$\kappa^{\aleph_0}=2^{\aleph_1\times\aleph_0}=2^{\aleph_1}\quad\mbox{and}\quad \kappa^{\aleph_1}=2^{\aleph_1\times\aleph_1}=2^{\aleph_1}.$$ This is indeed the usual situation:

Operations on cardinals (including addition, multiplication, and exponentiation) are very often weakly monotonic in each of their arguments but not strongly monotonic in any of them.