TITLE: Name for categories in which isomorphic implies equal?
QUESTION [2 upvotes]: A quick terminology question: Is there any particular name for a category in which each object is uniquely determined by its isomorphism class?

REPLY [0 votes]: A "gaunt" category is similar, but does not allow any nontrivial automorphisms, which are allowed in a skeletal category. http://ncatlab.org/nlab/show/gaunt+category


TITLE: "Choose next word" as an alternative to phrase-structure grammar
QUESTION [1 upvotes]: Notation: For the sake of this question, let $\sigma_X(x)$ denote the symbol immediately following $x$ in the sentence $X$. Let $a\in A$ indicate that the symbol $a$ occurs in the sentence $A$ if $A$ is a sentence and ordinary set membership, otherwise.

I was thinking about possible alternatives to phrase-structure grammar and I was inspired by text prediction software.
In principle, it should be possible to specify the grammar of a language using only a vocabulary $V$, a set $I\subseteq V$ of valid starting words (the set of symbols which may be used to begin a sentence), and a 'select next from' function $S:V\to\mathcal{P}(V)$; where, for each $v\in V$, $S(v)$ is the set of symbols in $V$ which may succeed $v$. That is, if $X$ is a valid sentence then $\forall x\in X.\sigma_X(x)\in S(x)$.
The one possible advantage this might have over phrase-structure grammar is that it allows for arbitrarily long sentences (it may also place fewer restrictions on the the structure of valid sentences) - but this might come at the cost of more complex production rules (in the form of the 'select next from' function).
Is this a valid means of specifying the grammar of a language, and if so, what would be the most expedient means of specifying $S$ (particularly when the predecessors of a symbol affect the possible successors)?

Edit: As pointed out by Q the Platypus, the grammar I am describing is similar, though not identical, to a Greibach normal form. The production rules of a grammar in Greibach normal form take the form of $A\to aA_1A_2\ldots A_n$, where $a$ is terminal and the sequence of $A_i$ are nonterminal.
The key difference between what I am attempting to describe and Greibach normal form is that there is no limit to length of a sentence. This might be put in Greibach normal form if the production rules could be specified by an expression like...
$$A\to a\bigsqcup_{i=1}^\beta A_i$$
...(using $\sqcup$ for concatenation) for every ordinal $\beta$.
The idea behind the 'select next' function was to provide a means of constructing arbitrarily long sentences and assessing whether an infinitely long sentence is valid (this could be done analogously to induction).
It also occurs to me that such sentences could, in principle, be without start or endpoint. Since each symbol depends only on the one(s) before it, you could have a 'select previous from' function that takes a symbol and determines which symbols might precede it and use that to create a sentence order-isomorphic to the integers.
Edit: It might be possible to express the aforementioned 'select next' and 'select previous' in terms of right and left recursion, respectively, with $A\to aA$ for right recursion and $A\to Aa$ for left recursion. In both cases, we must also have $A\to\varepsilon$, with $\varepsilon$ the empty string, as a production rule.

REPLY [1 votes]: I'm not sure if this is precisely what you're describing but, sentences can be generated via transitions such as: $P(x_t|x_{t-1},\cdots,x_1)$, where a sentence is comprised of words $x_1x_2\cdots x_n$. The probability function here simply counts the estimated frequency of the word $x_t$ given the past, and will be exactly 0 for disallowed word sequences (assuming your corpus of sentences has no grammatical errors). By the rules of probability this can be reduced to:
$$P(x_1\cdots x_n)=P(x_n|x_{n-1}\cdots x_1)P(x_{n-1}|x_{n-2}\cdots x_1)\cdots P(x_1).$$
By selecting $x_t$ with high probability, this effectively replicates current state-of-the-art techniques used for generating sentences in machine learning. This is generally referred to as Beam Search.
See for example:
https://hackernoon.com/beam-search-a-search-strategy-5d92fb7817f


text:
\newpage
\subsection{The main part of the proof of Theorem \ref{th:mainresult}}
This section is the main part of the proof of Theorem \ref{th:mainresult}.
The argument is inductive, that is, we shall use the result of $v_{1}$ and $v_{2}$ for the proof of higher degrees $v_{3.1},v_{3.2},v_{4.1},v_{4.2},v_{4.3},v_{4.4}$.
\subsubsection{$v_{1}$}
\noindent{\bf Proof of} (\ref{eqn:main result12}) {\bf in Theorem \ref{th:mainresult}.}
We expand (\ref{eq:v12}) according to (\ref{eqn:logtheta}) and obtain:
\begin{eqnarray*}
  v_{1}(A^b(\{K_1,K_2\}))=\hidarii A^b(\{K_1,K_2\}),\marucb\migii
  +\hidarii A^b(\{K_1,K_2\}),\marudo\migii.
\end{eqnarray*}
The second term in the right side of this equation identically vanishis, since
\linebreak[4]
$v_{1}(A^b(\{K_1,K_2\}))$ and the first term in the right side of this equation are real valued and the second term is pure imaginary. Inserting (\ref{eqn:crossingnumber0}) into the first term yields (\ref{eqn:main result12}).
$\square$
\newline

From this proof, we obtain the following lemma.
\begin{lemma}\hspace{-5pt}{\bf.}\hspace{5pt}~~\label{lemma:v12}
$\displaystyle
  \hidarii A^b(\{K_1,K_2\}),\marudo\migii=0.~~\square
$
\end{lemma}
Later we shall use this lemma in the proof of higher degrees.

\subsubsection{$v_2$}
\noindent{\bf Proof of} (\ref{eqn:main result2}) {\bf in Theorem \ref{th:mainresult}.}
For sufficiently small $b$, inserting $(\ref{eqn:decomposition1})$ into
(\ref{eq:v2}) and using $(\ref{eqn:crossingnumber1})$, we have
\begin{eqnarray}\label{eqn:v2-1}
  &&\hspace{-1.5cm}
  v_2(A^b(K))=\hidarii G(K),\marubb\migii_\chi\nonumber\\
  &&\hspace{1cm}
  +\frac{1}{2}\hidarii G^e(K),\marube\migii_{\chi^e}
  +\hidarii A^b(K),\marubd\migii-\frac{1}{6}m(K)+O(b),
\end{eqnarray}
where we have dropped the imaginary part, since $v_2(A^b(K))$ is real valued.
We replace $K$ by $\alpha(K)$ in (\ref{eqn:v2-1}) and obtain
\begin{eqnarray}\label{eqn:v2-2}
  &&\hspace{-1.5cm}
  v_2(A^b(\alpha(K)))=\hidarii G(\alpha(K)),\marubb\migii_\chi\nonumber\\
  &&\hspace{1cm}
  +\frac{1}{2}\hidarii G^e(K),\marube\migii_{\chi^e}
  +\hidarii A^b(K),\marubd\migii-\frac{1}{6}m(K)+O(b).
\end{eqnarray}
The second, third and fourth terms on the right hand side of (\ref{eqn:v2-1}) and (\ref{eqn:v2-2}) take the same value for $K$ and $\alpha(K)$, since they are independent on the signatures.
Since $v_2$ is a knot invariant, $v_2(A^b(\alpha(K)))$ is equal to
$v_2(U)$, where $U$ denotes a trivial knot. Subtracting (\ref{eqn:v2-2}) from
(\ref{eqn:v2-1}) yields the Gauss diagram formula (\ref{eqn:main result2}) in Theorem \ref{th:mainresult}:
\begin{eqnarray}\label{eqn:v2-3}
  v_2(A^b(K))=v_2(U)+\hidarii \bar{G}(K),\marubb\migii_{\chi},
\end{eqnarray}
where $\bar{G}(K)=G(K)-G(\alpha(K))$, $v_2(U)=-\frac{1}{6}$ and we have dropped $b$-dependent term $O(b)$ since $v_2(A^b(K))$ does not depend on $b$.
$\square$
\newline

From (\ref{eqn:v2-1}) and (\ref{eqn:v2-3}), we obtain the following lemma.
\begin{lemma}\hspace{-5pt}{\bf.}\hspace{5pt}~~\label{lemma:v2-4}
\begin{eqnarray*}
   &&\hspace{-1cm}
   \hidarii A^b(K),\marubd\migii=-\hidarii G(\alpha(K)),\marubb\migii_\chi
  -\frac{1}{2}\hidarii G^e(K),\marube\migii_{\chi^e}\\
  &&\hspace{6cm}
  -\frac{1}{6}(1-m(K))+O(b).
  ~~\square
\end{eqnarray*}
\end{lemma}
Later we shall use this lemma for the proof of higher degrees. Notice that we have obtained the Gauss diagram formula for the difficult integral $\hidarii A^b(K),\marubd\migii$.

\subsubsection{$v_{3.1}$}
To prepare for the proof of (\ref{eqn:main result31}) in Theorem \ref{th:mainresult},
we shall first prove Lemma \ref{lemma:v31-1} and Lemma \ref{lemma:v31-2}.
\begin{lemma}\hspace{-5pt}{\bf.}\hspace{5pt}\label{lemma:v31-1}~~
\begin{eqnarray*}
  \hh\{A^b(K):a\},\maruia+\marudk\mm=\hidarii A^b(K),\marubd\migii-\sum_{s=\pm}
  \hidarii A^b(K^{[1]}_s),\marubd\migii+O(b).
\end{eqnarray*}
\end{lemma}
{\bf Proof.}~~Use the identities:
\begin{eqnarray*}
  &&\hidarii A^b(K),\marubd\migii
  =\hh\{A^b(K):a\},\maruib+\maruia+\marudk\mm,\nonumber\\
  &&\sum_{s=\pm}\hidarii A^b(K^{[1]}_s),\marubd\migii
  =\hh\{A^b(K):a\},\maruib\mm+O(b),
\end{eqnarray*}
where $K^{[1]}_s$ are given in Definition \ref{def:NewKnotDiagram}. $\square$

\begin{lemma}\hspace{-5pt}{\bf.}\hspace{5pt}\label{lemma:v31-2}~~
$\displaystyle
  \hh\{A^b(K):a\},\marudi+\marudk\mm=O(b).
$
\end{lemma}
{\bf Proof.}
\begin{eqnarray*}
  \hh\{A^b(K):a\},\marudi+\marudk\mm&
  =&\frac{1}{2}\hh\{A^b(K):a\},\maruic\mm^2\nonumber\\
  &=&\frac{1}{2}\hidarii A^b\bigl(\{K^{[1]}_+,K^{[1]}_-\}\bigr),\marudo\migii^2
  +O(b)\nonumber\\[0.1cm]
  &=&O(b)
\end{eqnarray*}
The last step follows from Lemma \ref{lemma:v12}. $\square$
\newline

\noindent{\bf Proof of} (\ref{eqn:main result31}) {\bf in Theorem \ref{th:mainresult}.}~~
Inserting (\ref{eqn:decomposition2}),(\ref{eqn:decomposition3}) into
(\ref{eq:v31}) and using (\ref{eqn:spilit1}), (\ref{eqn:spilit2}),(\ref{eqn:spilit3}) yields:
\begin{eqnarray*}
  \lefteqn{v_{3.1}(A^b(K))}\\
  &&=\hidarii A^b(K),\marudd+2\marude\migii\nonumber\\
  &&+\sum_{a}
  \hidarii P(\{K:a\}),\marua\migii_\chi \hh\{A^b(K):a\},
  \marudi+\maruia+2\marudk\mm+O(b)
  \nonumber\\
  &&=\hidarii A^b(K),\marudd+2\marude\migii\nonumber\\
  &&\hspace{-0.5cm}
  +\sum_{a}
  \hidarii P(\{K:a\}),\marua\migii_\chi \biggl\{\hidarii A^b(K),\marubd\migii-
  \sum_{s=\pm}\hidarii A^b(K^{[1]}_s),\marubd\migii\biggr\}+O(b).\\
\end{eqnarray*}
The last step follows from Lemma \ref{lemma:v31-1} and Lemma \ref{lemma:v31-2}.
We insert Lemma \ref{lemma:v2-4} and (\ref{eqn:crossingnumber311}) (\ref{eqn:crossingnumber312}) into this and use
\begin{eqnarray*}
  &&\bullet~~
  \sum_{a}\hidarii P(\{K:a\}),\marua\migii_\chi \hidarii G^e(K)-
  \sum_{s=\pm}G(K^{[1]}_s),\marube\migii_{\chi^e}\nonumber\\
  &&\hspace{6cm}
  =\hidarii G^e(K),\marudm~+\marudn\migii_{\chi^e},
  \nonumber\\
  &&\bullet~~
  \sum_{a}\hidarii P(\{K:a\}),\marua\migii_\chi
  \Bigl\{ \bigl(1-m(K)\bigr)
  -\sum_{s=\pm}\bigl(1-m(K^{[1]}_s)\bigr)\Bigr\}\nonumber\\
  &&\hspace{6cm}
  =-\hidarii G^e(K),\marudn\migii_{\chi^e}.
\end{eqnarray*}
Then we have
\begin{eqnarray*}
  &&\hspace{-0.8cm}
  v_{3.1}(A^b(K))=
  \hidarii G(K),~~2\marude+\marudd+\frac{1}{2}\marudp\migii_{\chi}
  \nonumber\\
  &&\hspace{1.2cm}
  -\sum_{a}\hidarii P(\{K:a\}),\marua\migii_\chi
  \hidarii G(\alpha(K))-\sum_{s=\pm}G(\alpha(K_s^{[1]})),
  \marubb\migii_{\chi},
\end{eqnarray*}
where we have dropped $b$-dependent term $O(b)$ since $v_{3.1}(A^b(K))$ does not depend on $b$. We can easily see that this equation is the same as the Gauss diagram formula (\ref{eqn:main result31}) in Theorem \ref{th:mainresult}.
$\square$

\subsubsection{$v_{3.2}$}
To prepare for the proof of (\ref{eqn:main result32}) in Theorem \ref{th:mainresult},
we shall prove Lemma \ref{lemma:v32-1} and Lemma \ref{lemma:v32-2}.
\newpage

\begin{lemma}\hspace{-5pt}{\bf.}\hspace{5pt}\label{lemma:v32-1}~~
If $P_0(\{K_1,K_2:a\})=\marucb$, then
\begin{eqnarray*}
  &&\hspace{-0.8cm}
  \hh\bigl\{A^b(\{K_1,K_2\}):a\bigr\},\maruid+\maruie\mm
   \nonumber\\
  &&\hspace{3cm}
  =\hidarii A^b(K^{[2]})
  ,\marubd\migii
  -\sum_{i=1}^2\hidarii A^b(K_i),\marubd\migii+O(b).
\end{eqnarray*}
holds.
\end{lemma}
{\bf Proof.}~~The proof is similar to Lemma \ref{lemma:v31-1}~~.
\begin{eqnarray*}
  &&
  \hh\bigl\{A^b(\{K_1,K_2\}):a\bigr\},\maruid+\maruie\mm\\
  &&\hspace{3cm}
  =\hh\{A^b(K^{[2]}):a\},\maruia+\marudk\mm+O(b)\nonumber\\
  &&\hspace{3cm}
  =\hidarii A^b(K^{[2]}),\marubd\migii
  -\sum_{i=1}^2\hidarii A^b(K_i),\marubd\migii+O(b).~~\square\nonumber
\end{eqnarray*}

\begin{lemma}\hspace{-5pt}{\bf.}\hspace{5pt}\label{lemma:v32-2}~~
$\displaystyle
  \hh\{A^b(\{K_1,K_2\}):a\},\marueg\mm=O(b).
$
\end{lemma}
{\bf Proof.}
\begin{eqnarray*}
  \lefteqn{\hh\{A^b(\{K_1,K_2\}):a\},\marueg\mm} \nonumber\\
  &&=\hidarii A^b(\{K^{[17]}_+,K^{[17]}_0\}),\marudo\migii
  \hidarii A^b(\{K^{[17]}_-,K^{[17]}_0\}),\marudo\migii+O(b)
  \nonumber\\
  &&=O(b).
\end{eqnarray*}
The last step follows from Lemma \ref{lemma:v12}. $\square$
\newline

\noindent{\bf Proof of} (\ref{eqn:main result32}) {\bf in Theorem \ref{th:mainresult}.}~~
After inserting (\ref{eqn:decomposition4})
,(\ref{eqn:decomposition5}) into (\ref{eq:v32}), we use (\ref{eqn:spilit4}),(\ref{eqn:spilit5}),(\ref{eqn:spilit6}). Then we obtain
\begin{eqnarray*}
  \lefteqn{v_{3.2}(A^b(\{K_1,K_2\}))}\nonumber\\
  &&=\hidarii A^b(\{K_1,K_2\}),\marueb+2\marued\migii\nonumber\\
  &&~~+\sum_{a}
  \hidarii P({K_1,K_2:a}),\marucb\migii_{\chi}\\
  &&\hspace{3cm}\times
  \hh \{A^b(\{K_1,K_2\}):a\},\maruid+\maruie\mm\nonumber\\
  &&~~+\sum_{a}
  \hidarii P({K_1,K_2:a}),\marua\maru\migii_{\chi}\\
  &&\hspace{3cm}\times
  \hh \{A^b(\{K_1,K_2\}):a\},\marueg\mm+O(b)
  \nonumber\\
  &&=\hidarii A^b(\{K_1,K_2\}),\marueb+2\marued\migii\nonumber\\
  &&~~+\sum_{a}
  \hidarii P({K_1,K_2:a}),\marucb\migii_{\chi}\\
  &&\hspace{3cm}\times
  \biggl\{\hidarii A^b(K^{[2]}),\marubd\migii
  -\sum_{i=1}^2\hidarii A^b(K_i),\marubd\migii\biggr\}+O(b).
\end{eqnarray*}
The last step follows from Lemma \ref{lemma:v32-1} and \ref{lemma:v32-2}.
We insert Lemma \ref{lemma:v2-4} and (\ref{eqn:crossingnumber321}) (\ref{eqn:crossingnumber322}) into this and use
\begin{eqnarray*}
  &&\bullet~~
  \sum_{a}\hidarii P({K_1,K_2:a}),\marucb\migii_{\chi}
  \hidarii G^e(K^{[2]})-\sum_{i=1,2}G^e(K_i),\marube\migii_{\chi^e}\nonumber\\
  &&\hspace{3cm}=\hidarii G^e(K_1,K_2),\maruej\migii_{\chi^e},
  \nonumber\\
  &&\bullet~~
  \sum_{a}\hidarii P({K_1,K_2:a}),\marucb\migii_{\chi}
  \Bigl\{ \bigl(1-m(K^{[2]})\bigr)
  -\sum_{i=1,2}\bigl(1-m(K_i)\bigr)\Bigr\}\nonumber\\
  &&\hspace{3cm}=-\hidarii G^e(\{K_1,K_2\}),\marucb+\maruel\migii_{\chi^e}.
\end{eqnarray*}
Then we have
\begin{eqnarray*}
  \lefteqn{v_{3.2}(A^b(\{K_1,K_2\}))}\\
  &&=\hidarii G(K_1,K_2),~~\marueb
  +\marued+\frac{1}{3}\marucb\migii_{\chi}\nonumber\\
  &&-\sum_{a}\hidarii P({K_1,K_2:a}),\marucb\migii_{\chi}
  \hidarii G(\alpha(K^{[2]}))
  -\sum_{i=1,2}G(\alpha(K_i)),\marubb\migii_{\chi}.\nonumber
\end{eqnarray*}
This is the same as the Gauss diagram formula (\ref{eqn:main result32}) in Theorem \ref{th:mainresult}.
$\square$

\subsubsection{$v_{4.1}, v_{4.2}, v_{4.3}, v_{4.4}$}
The computaion of degree four $v_{4.1},v_{4.2},v_{4.3},v_{4.4}$ are long but straightforward. We use the same argument as degree two and three.
\newline

\noindent{\bf Proof of} (\ref{eqn:main result41}) {\bf in Theorem \ref{th:mainresult}.}
We calculate $v_{4.1}$ in the same way as the lower degree, and obtain:
\begin{eqnarray*}
  \lefteqn{v_{4.1}(A^b(K))}\\
  &&=\hidarii A^b(K),~~\maruga+\marugb+2\marugc+4\marugd
  +5\maruge+7\marugf\migii \nonumber\\
  &&+\sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\marubb\migii_{\chi}
  \nonumber\\
  &&\hspace{-0.5cm}\times
  \biggl\{3\hidarii A^b(K),\marubd\migii
  -2\sum_{n=3,4}\sum_{s=\pm}\hidarii A^b(K^{[n]}_s),\marubd\migii
  +\sum_{s=\pm}\hidarii A^b(K^{[5]}_s),\marubd\migii\biggr\}
  \nonumber\\
  &&+\sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\maruba\migii_{\chi}
  \nonumber\\
  &&\hspace{-0.3cm}\times
  \biggl\{\hidarii A^b(K),\marubd\migii
  -\sum_{n=6,7}\sum_{s=\pm}\hidarii A^b(K^{[n]}_s),\marubd\migii
  +\sum_{s=\pm,0}\hidarii A^b(K^{[8]}_s),\marubd\migii
  \biggr\}\nonumber\\
  &&+(\mbox{signature independent terms})+O(b),
\end{eqnarray*}
where we have used Lemma \ref{lemma:v12}. In the above equation,
"(signature independent terms)" means the terms which take the same value for $K$ and $\alpha(K)$.
After inserting Lemma \ref{lemma:v2-4} into this, we use
\begin{eqnarray*}
  &&\bullet~~
  \sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\marubb\migii_{\chi}\nonumber\\
  &&\hspace{2cm}\times
  \hidarii 3~G(K)-2\sum_{n=3,4}\sum_{s=\pm}G(K^{[n]}_s)
  +\sum_{s=\pm}G(K^{[5]}_s),\marube\migii_{\chi} \nonumber\\
  &&\hspace{4cm}=\hidarii G(K),3\marujd+\maruja~+2\marujc+\marugi\migii_{\chi},
  \nonumber\\
  &&\bullet~~
  \sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\marubb\migii_{\chi}\nonumber\\
  &&\hspace{1.5cm}\times
  \Bigl\{ 3\bigl(1-m(K)\bigr)
  -2\sum_{n=3,4}\sum_{s=\pm}\bigl(1-m(K^{[n]}_s)\bigr)
  +\sum_{s=\pm}\bigl(1-m(K^{[5]}_s)\bigr)\Bigr\} \nonumber\\
  &&\hspace{4cm}=\hidarii G(K),\marubb-3\marujd\migii_{\chi},
\end{eqnarray*}
and
\begin{eqnarray*}
  &&\bullet~~
  \sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\maruba\migii_{\chi}\nonumber\\
  &&\hspace{2cm}\times
  \hidarii G(K)-\sum_{n=6,7}\sum_{s=\pm}G(K^{[n]}_s)
  +\sum_{s=\pm,0}G(K^{[8]}_s),\marube\migii_{\chi}
  \nonumber\\
  &&\hspace{6cm}
  =\hidarii G(K),\marujb\migii_{\chi},\nonumber\\
  &&\bullet~~
  \Bigl\{ \bigl(1-m(K)\bigr)
  -\sum_{n=6,7}\sum_{s=\pm}\bigl(1-m(K^{[n]}_s)\bigr)
  +\sum_{s=\pm,0}\bigl(1-m(K^{[8]}_s)\bigr)\Bigr\}=0.
\end{eqnarray*}
Lastly we cancel the signature independent terms by using $\alpha(K)$ in the same argument as in the proof of $v_2$. Then we have
\begin{eqnarray*}
  \lefteqn{v_{4.1}(A^b(K))}\\
  &&=\frac{1}{360}+\hidarii \bar{G}(K),~\maruga+\marugb+2\marugc+4\marugd
  +5\maruge+7\marugf\migii_{\chi} \nonumber\\
  &&\hspace{3cm}+\hidarii \bar{G}(K),~
  \frac{1}{6}\marubb+\frac{1}{2}\marugg+2\marugh+2\marugi\migii_{\chi}
  \nonumber\\
  &&-\sum_{(a_1,a_2)}\hidarii \bar{P}(\{K:a_1,a_2\}),\marubb\migii_{\chi}
  \nonumber\\
  &&\hspace{1cm}\times
  \hidarii 3~G(\alpha(K))-2\sum_{n=3,4}\sum_{s=\pm}G(\alpha(K^{[n]}_s))
  +\sum_{s=\pm}G(\alpha(K^{[5]}_s)),\marubb\migii_{\chi}
  \nonumber\\
  &&-\sum_{(a_1,a_2)}\hidarii \bar{P}(\{K:a_1,a_2\}),\maruba\migii_{\chi}
  \nonumber\\
  &&\hspace{1cm}\times
  \hidarii G(\alpha(K))-\sum_{n=6,7}\sum_{s=\pm}G(\alpha(K^{[n]}_s))
  +\sum_{s=\pm,0}G(\alpha(K^{[8]}_s)),\marubb\migii_{\chi}.
  \nonumber\\
\end{eqnarray*}
This is the same as the Gauss diagram formula (\ref{eqn:main result41}) in Theorem \ref{th:mainresult}.  $\square$
\newline

\noindent{\bf Proof of} (\ref{eqn:main result42}) {\bf in Theorem \ref{th:mainresult}.} We calculate $v_{4.2}$ in the same way as the lower degree and obtain:
\begin{eqnarray*}
  \lefteqn{v_{4.2}(A^b(K))}\\
  &&=
  \hidarii A^b(K),~~\marugd+\maruge+\marugf\migii \nonumber\\
  &&+\sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\marubb\migii_{\chi}
  \nonumber\\
  &&\hspace{0cm}\times
  \biggl\{\hidarii A^b(K),\marubd\migii
  -\sum_{n=3,4}\sum_{s=\pm}\hidarii A^b(K^{[n]}_s),\marubd\migii
  +\sum_{s=\pm}\hidarii A^b(K^{[5]}_s),\marubd\migii\biggr\}
  \nonumber\\
  &&+(\mbox{signature independent term})+O(b),
\end{eqnarray*}
where we have used Lemma \ref{lemma:v12}. After inserting Lemma \ref{lemma:v2-4} into this, we use
\begin{eqnarray*}
  &&\bullet~~
  \sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\marubb\migii_{\chi}
  \nonumber\\
  &&\hspace{2cm}\times
  \hidarii G(K)-\sum_{n=3,4}\sum_{s=\pm}G(K^{[n]}_s)
  +\sum_{s=\pm}G(K^{[5]}_s),\marube\migii_{\chi} \nonumber\\
  &&\hspace{4cm}=\hidarii G(K),\marugi+\marujd \migii_{\chi},\nonumber\\
  &&\bullet~~
  \sum_{(a_1,a_2)}\hidarii P({K:a_1,a_2}),\marubb\migii_{\chi}
  \nonumber\\
  &&\hspace{1.5cm}\times
  \Bigl\{ \bigl(1-m(K)\bigr)
  -\sum_{n=3,4}\sum_{s=\pm}\bigl(1-m(K^{[n]}_s)\bigr)
  +\sum_{s=\pm}\bigl(1-m(K^{[5]}_s)\bigr)\Bigr\} \nonumber\\
  &&\hspace{4cm}=\hidarii G(K),-\marubb+\maruje-\marujd\migii_{\chi}.
\end{eqnarray*}
Lastly we cancel the signature independent terms by using $\alpha(K)$ in the same argument as in the proof of $v_2$. Then we have
\begin{eqnarray*}
  \lefteqn{v_{4.2}(A^b(K))}\\
  &&=-\frac{1}{360}+\hidarii \bar{G}(K),~~\marugd+\maruge+\marugf
  +\frac{1}{2}\marugh-\frac{1}{6}\marubb\migii_{\chi}
  \nonumber\\
  &&~~-\sum_{(a_1,a_2)}\hidarii \bar{P}(\{K:a_1,a_2\}),\marubb\migii_{\chi}
  \nonumber\\
  &&\hspace{1.5cm}\times
  \hidarii G(\alpha(K))-\sum_{n=3,4}\sum_{s=\pm}G(\alpha(K^{[n]}_s))
  +\sum_{s=\pm}G(\alpha(K^{[5]}_s)),\marubb\migii_{\chi}.
  \nonumber\\
\end{eqnarray*}
This is the same as the Gauss diagram formula (\ref{eqn:main result42}) in Theorem \ref{th:mainresult}.  $\square$
\newline

\noindent
{\bf Proof of} (\ref{eqn:main result43}) {\bf in Theorem \ref{th:mainresult}.}
We calculate $v_{4.3}$ in the same way as the lower degree, and we obtain
\begin{eqnarray*}
  \lefteqn{v_{4.3}(A^b(\{K_1,K_2\}))}\\
  &&=\hidarii A^b(\{K_1,K_2\}),\maruha+\maruhb
  +2\maruhc \nonumber\\
  &&\hspace{4cm}+\maruhd+\maruhe+\maruhf\migii\nonumber\\
  &&+\sum_{(a_1,a_2)}\hidarii P({K_1,K_2:a_1,a_2}),\maruca\migii_{\chi}
   \nonumber\\
  &&\hspace{1.5cm}\times
  \biggl\{\sum_{i=1,2}\hidarii A^b(K_i),\marubd\migii
  -\sum_{s=\pm}\hidarii A^b(K^{[9]}_s),\marubd\migii\biggr\}\nonumber\\
  &&+\sum_{(a_1,a_2)}\hidarii P({K_1,K_2:a_1,a_2}),\marucc\migii_{\chi}
  \nonumber\\
  &&
  \times\biggl\{\hidarii A^b(K^{[10]}),\marubd\migii
  -\sum_{n=11,12}\sum_{s=\pm}\hidarii A^b(K^{[n]}_s),\marubd\migii
  \nonumber\\
  &&\hspace{6cm}
  +\sum_{s=\pm,0}\hidarii A^b(K^{[13]}_s),\marubd\migii\biggr\},\nonumber\\
\end{eqnarray*}
where we have used Lemma \ref{lemma:v12}. After inserting Lemma \ref{lemma:v2-4} into this, we use
\begin{eqnarray*}
  &&\hspace{-1cm}\bullet~
  \sum_{(a_1,a_2)}\hidarii P({K_1,K_2:a_1,a_2}),\maruca\migii_{\chi}
  \hidarii \sum_{i=1,2}G(K_i)
  -\sum_{s=\pm}G(K^{[9]}_s),\marube\migii_{\chi} \nonumber\\
  &&\hspace{3cm}=\hidarii G(\{K_1,K_2\}),\marujf-\marujg\migii_{\chi},
  \nonumber\\
  &&\hspace{-1cm}\bullet~
  \sum_{(a_1,a_2)}\hidarii P({K_1,K_2:a_1,a_2}),\maruca\migii_{\chi}
  \nonumber\\
  &&\hspace{2cm}\times
  \Bigl\{\sum_{i=1,2}\bigl(1-m(K_i)\bigr)
  -\sum_{s=\pm}\bigl(1-m(K^{[9]}_s)\bigr)\Bigr\} \nonumber\\
  &&\hspace{4cm}=\hidarii G(\{K_1,K_2\}),\marujh\migii_{\chi},
\end{eqnarray*}
and
\begin{eqnarray*}
  &&\bullet~
  \sum_{(a_1,a_2)}\hidarii P({K_1,K_2:a_1,a_2}),\marucc\migii_{\chi}
  \nonumber\\
  &&\hspace{1.5cm}\times
  \hidarii G(K^{[10]})-\sum_{n=11,12}\sum_{s=\pm}G(K^{[n]}_s)
  +\sum_{s=\pm,0}G(K^{[13]}_s),\marube\migii_{\chi}\nonumber\\
  &&\hspace{5cm}=\hidarii G(\{K_1,K_2\}),\maruji\migii_{\chi},\nonumber\\
  &&\bullet~
  \bigl(1-m(K^{[10]})\bigr)
  -\sum_{n=11,12}\sum_{s=\pm}\bigl(1-m(K^{[n]}_s)\bigr)
  +\sum_{s=\pm,0}\bigl(1-m(K^{[13]}_s)\bigr)=0.
\end{eqnarray*}
Lastly we cancel the signature independent terms by using $\alpha(K)$ in the same argument as in the proof of $v_2$. Then we have
\begin{eqnarray*}
  \lefteqn{v_{4.3}(A^b(\{K_1,K_2\}))}\\
  &&=\hidarii \bar{G}(\{K_1,K_2\}),
  ~\maruha+\maruhb+2\maruhc+\maruhd\migii_{\chi}
  \nonumber\\
  &&\hspace{-0.1cm}
  +\hidarii \bar{G}(\{K_1,K_2\}),
  \maruhe+\maruhf+\frac{1}{2}\maruhg+\frac{1}{2}\maruhh\migii_{\chi}
  \nonumber\\
  &&-\sum_{(a_1,a_2)}\hidarii \bar{P}(\{K_1,K_2:a_1,a_2\}),\maruca\migii_{\chi}
  \nonumber\\
  &&\hspace{4cm}\times
  \hidarii \sum_{i=1,2}G(\alpha(K_i))
  -\sum_{s=\pm}G(\alpha(K^{[9]}_s)),\marubb\migii_{\chi}
  \nonumber\\
  &&-\sum_{(a_1,a_2)}\hidarii \bar{P}(\{K_1,K_2:a_1,a_2\}),\maruhi\migii_{\chi}
  \nonumber\\
  &&\hspace{0cm}\times
  \hidarii G(\alpha(K^{[10]}))-\sum_{n=11,12}\sum_{s=\pm}G(\alpha(K^{[n]}_s))
  +\sum_{s=\pm,0}G(\alpha(K^{[13]}_s)),\marubb\migii_{\chi}
  \nonumber\\
\end{eqnarray*}
This is the same as the Gauss diagram formula (\ref{eqn:main result43}) in Theorem \ref{th:mainresult}.  $\square$
\newline

\noindent
{\bf Proof of} (\ref{eqn:main result44}) {\bf in Theorem \ref{th:mainresult}.}
We calculate $v_{4.4}$ in the same way as the lower degree, and we obtain
\begin{eqnarray*}
  \lefteqn{v_{4.4}(A^b(\{K_1,K_2,K_3\}))}\\
  &&=\hidarii A^b(\{K_1,K_2,K_3\}),
  ~~\maruhj+\maruhk+\maruhl\migii\nonumber\\[0.2cm]
  &&\hspace{0cm}
  +\sum_{(a_1,a_2)}\hidarii P({K_1,K_2,K_3:a_1,a_2}),\maruhm\migii_{\chi}
  \nonumber\\
  &&\hspace{1cm}\times\biggl\{\hidarii A^b(K^{[14]}),\marubd\migii
  -\sum_{n=15,16}\sum_{s=\pm}\hidarii A^b(K^{[n]}_s),\marubd\migii
  \nonumber\\
  &&\hspace{6cm}
  +\sum_{i=1,2,3}\hidarii A^b(K_i),\marubd\migii\biggr\},\nonumber\\
\end{eqnarray*}
where we have used Lemma \ref{lemma:v12}. After inserting Lemma \ref{lemma:v2-4} into this, we use
\begin{eqnarray*}
  &&\bullet~~
  \sum_{(a_1,a_2)}\hidarii P({K_1,K_2,K_3:a_1,a_2}),\maruhm\migii_{\chi}
  \nonumber\\
  &&\hspace{1cm}\times
  \hidarii G(K^{[14]})-\sum_{n=15,16}\sum_{s=\pm}G(K^{[n]}_s)
  +\sum_{i=1,2,3}G(K_i),\marube\migii_{\chi}\nonumber\\
  &&\hspace{3cm}=\hidarii G(\{K_1,K_2,K_3\}),\marujj\migii_{\chi},
  \nonumber\\[0.5cm]
  &&\bullet~~\bigl(1-m(K^{[14]})\bigr)
  -\sum_{n=15,16}\sum_{s=\pm}\bigl(1-m(K^{[n]}_s)\bigr)
  +\sum_{i=1,2,3}\bigl(1-m(K_i)\bigr)=0.
\end{eqnarray*}
Lastly we cancel the signature independent terms by using $\alpha(K)$ in the same argument as in the proof of $v_2$. Then we have
\begin{eqnarray*}
  \lefteqn{v_{4.4}(A^b(\{K_1,K_2,K_3\}))}\\
  &&=\hidarii \bar{G}(\{K_1,K_2,K_3\}),~~\maruhj+\maruhk+\maruhl\migii_{\chi}
  \nonumber\\[0.2cm]
  &&-\sum_{(a_1,a_2)}\hidarii \bar{P}(\{K_1,K_2,K_3:a_1,a_2\})
  ,\maruhm\migii_{\chi}
  \nonumber\\
  &&\hspace{1cm}\times
  \hidarii G(\alpha(K^{[14]}))
  -\sum_{n=15,16}\sum_{s=\pm}G(\alpha(K^{[n]}_s))
  +\sum_{i=1}^3G(\alpha(K_i)),\marubb\migii_{\chi}.
  \nonumber\\
\end{eqnarray*}
This is the same as the Gauss diagram formula (\ref{eqn:main result44}) in Theorem \ref{th:mainresult}.  $\square$
\newline

\noindent{\it Remark.}
Notice the concept of direction "s", "d" disappear in the final Gauss diagram formula, as we have expected.

config: arxiv


TITLE: Converting "% faster" to "X times speedup"
QUESTION [0 upvotes]: I'm confusing myself over a rather pedantic math question. I'm comparing two simulation's runtimes (measured in seconds). I want to know how many times faster is simulation A compared to simulation B.
Normally, I report the result as a percentage, e.g., simulation A is 50% faster than simulation B. To get this percentage, I can simply divide $$t_A / t_B$$. 50% faster is equivalent to "1 times speedup". I'm wondering what is the equation to get this speedup number on less nice numbers?

REPLY [0 votes]: To say a value $x$ is $p\%$ greater than a value $y$ means that $\dfrac {x-y}y \times 100\% = p\%$. That fraction can also be expressed as $\left(\dfrac xy - 1\right)$. In this case, you are comparing the speeds to accomplish the task, which will be $x = \dfrac 1{t_A}$ and $y = \dfrac 1{t_b}$, so $$\dfrac xy = \dfrac{\dfrac 1{t_A}}{\dfrac 1{t_B}} = \frac {t_B}{t_A}$$ and the answer to your question is

Simulation A is $\left(\dfrac {t_B}{t_A} - 1\right)\times 100\%$ faster than Simulation B.

In particular A will be $50\%$ faster than B if $t_B = (1.5)t_A$


TITLE: If the partial sums $s_n $of $\sum a_n $ are bounded, show that the series $\sum \frac{a_n}{n} $ converges to $\sum \frac{s_n}{n (n+1)} $
QUESTION [2 upvotes]: My try:   $\left(\frac{1}{n}\right)_{n=1}^\infty $is decreasing and $\lim_{n\to\infty} \frac{1}{n}=0$ with $\sum a_n $is bounded so by Dirichlet's Test $\sum \frac{a_n}{n}$ is convergent.
To prove the given statement I am trying to show $|\sum \frac{a_n}{n}-\sum \frac{s_n}{n(n+1)}|$ tends to $0$.
\begin{align}
|\sum \frac{a_n}{n}-\sum \frac{s_n}{n(n+1)}|
&=\left|a_1 +\frac{a_2}{2} +\frac{a_3}{3} +\cdots-\frac{a_1}{1\cdot2} -\frac{a_1+a_2}{2\cdot3}-\frac{a_1+a_2+a_3}{3\cdot4} -\cdots\right|\\
&=|a_1-\frac{a_1}{1\cdot2} + \frac{a_2}{2} -\frac{a_1+a_2}{2\cdot3} +\frac{a_3}{3} -\frac{a_1+a_2+a_3}{3\cdot4} +\cdots|\\
&\leq\left|a_1-\frac{a_1}{1\cdot2}\right| + \left|\frac{a_2}{2} -\frac{a_1+a_2}{2\cdot3}\right| +\left|\frac{a_3}{3} -\frac{a_1+a_2+a_3}{3\cdot4}\right| + \cdots & (1)
\end{align}
Now From the $n$th term
$$\left|\frac{na_n-a_1-a_2-...-a_{n-1}}{n (n-1)}\right|\geq\left|\frac{na_n-M}{n(n-1)}\right|$$
($M$ is an upper bound of $\sum a_n$)
Also $\left|\frac{na_n+M}{n(n-1)}\right|$ is greater than the nth term. Taking $n$ tends to infinity we see that the $n$th term goes to $0$. Using this in $(1)$ we note that tail of both the series coincide and then $1$st series converges to $2$nd series. Am I correct?

REPLY [3 votes]: Try the usual summation by parts as suggested in the comments.
Another approach:
$$\begin{align}\sum_{n=1}^N \frac{s_n}{n(n+1)} &= \sum_{n=1}^N \sum_{k=1}^n\frac{a_k}{n(n+1)} \\&= \sum_{n=1}^N \sum_{k=1}^N\frac{a_k\, 1_{k \leqslant n}}{n(n+1)} \\&= \sum_{k=1}^N \sum_{n=1}^N\frac{a_k\, 1_{k \leqslant n}}{n(n+1)} \\ &=  \sum_{k=1}^N a_k\sum_{n=k}^N\frac{1 }{n(n+1)}  \\ &= \sum_{k=1}^N a_k \left(\frac{1}{k} - \frac{1}{N+1} \right)\\ &= \sum_{k=1}^N \frac{a_k}{k} - \frac{s_N}{N+1} \end{align}$$
Now take limits as $N \to \infty$ using the fact that $s_N$ is bounded.


TITLE: Contradicting example concerning the definition of homotopic paths?
QUESTION [0 upvotes]: From Rotman's algebraic topology:  In the picture below in example $7.16$, how is the underlined statement in red true given the definition above it?  The elementary move of $(0,1)(1,2) \rightarrow (0,2)$ should still apply but the book is saying they can't be homotopic?
Additional definitions:  Edge path $\alpha$ is a sequence of finite edges $\alpha = e_1e_2\dots e_n$.
Edge $e=(p,q)$ in a simplicial complex is an ordered pair of vertexes lying in a simplex of $K$.

REPLY [3 votes]: Hint: The definition says "where $\{p,q,r\}$ lie in a simplex of $K$" - which simplex of the skeleton do $\{p_0,p_1,p_2\}$ lie in?


TITLE: complex analysis conjugate problem
QUESTION [0 upvotes]: Is it equal? Or is it not equal? Also I tried two way. Logarithmic and polar representation. But I failed. Sorry for my English.
I couldn't show this.
$$\overline{(z^{z})} \neq \bar{z}^{\bar{z}}$$
$$\overline{(z^{z})} = \bar{z}^{\bar{z}}$$

REPLY [2 votes]: Take the case $z=i$.  Then $$z^z=i^i=e^{i\log{i}}=e^{i(i2n\pi+i\pi/2)}=e^{-2n\pi-\pi/2}$$ Since this is real, for all integer values of $n$, we have $\overline{z^z}=z^z$ in this case.  On the other hand,
$$\overline{z}^{\overline{z}}=(-i)^{-i}=e^{-i(i2k\pi-i\pi/2)}=e^{-2k\pi+\pi/2}$$  There are no integer values of $k$ and $n$ such that $-2n\pi-\pi/2=-2k\pi+\pi/2$, so in the case $z=i$, there is no value of the left-hand side equal to any value of the right-hand side.
Therefore, as a general rule, $\overline{z^z}\neq\overline{z}^{\overline{z}}$.  Of course, they're equal when $z$ is real.


TITLE: 2 Cards are drawn from a deck of cards.
QUESTION [1 upvotes]: I use this site for learning mathematics. I have come across this question. and the explanations are very much clear. Suppose the question is

2 Cards are drawn from a deck of cards. What
is the probability that one of them is a black card and one of them is ace?

Can anybody help me to get the intuition for this problem,

REPLY [0 votes]: Here is a picture:

The first card appears left-right, the second card top-bottom in lighter colors.
The colored squares represent picking either an ace or black card, or both. The yellow squares are no-goes.
I count $2100$ colored (not yellow) squares, and  there are $2652$ available squares in total (the grid is $52\times52$), so the probability is $\dfrac{175}{221}$.


TITLE: Confirmation about how to formally state a function rule that satisfies a specific property
QUESTION [0 upvotes]: I am having a little trouble deciding that I have properly worded the rule for a function. The only background knowledge required is as follows:

Let $G$ be any subset of $X \times Y$ with the property that for each $x \in X$, the set $\{y \in Y: (x,y) \in G\}$ has exactly one element.

Now, the function that I am trying to make can be worded as:
"$f$ maps each element of $X$ to its ordered pair 'partner component' found in $G$."
Here is how I have tried to word this:
$f: X \to Y$
$f: \forall x \in X, f(x) = y \text{ such that } (x,y) \in G$
Because of how $G$ is defined, I think this is satisfactory. But I am uncertain about whether or not my formal language has correctly encoded the idea of mapping each first component of the ordered pair to its   partner second component.
Confirmation would be greatly appreciated!

REPLY [1 votes]: Yes, this is indeed how it works. Because it is unique we call the unique $y$ with $(x,y) \in G$ the image $f(x)$ of $x$.
Or $y=f(x)=\pi_2[G \cap (\{x\}\times Y)]$, where $\pi_2$ is the projection from $X \times Y$ onto $Y$.


TITLE: If $G$ is a group, $x,y, \in G$ and $xy =yx$ then prove that $|xy| = \operatorname{lcm}\{|x|,|y|\}$ given that $|x|$ and $|y|$ are coprime
QUESTION [0 upvotes]: Well I know that since $|x|,|y|$ are both positive integers then we have that  $$|x||y| = \gcd(|x|,|y|)\operatorname{lcm}(|x|,|y|)$$
And since we are given that $|x|,|y|$ are coprime then we have $gcd(|x|,|y|)=1$ and so $$|x||y| = \operatorname{lcm}(|x|,|y|)$$
Now all I need to show is that $|x||y| = |xy|$.
Now let $|x| =n,|y| = m$ and also let $|xy|=k$ and consider $(xy)^{mn}$.
$(xy)^{mn} = (x)^{mn}(y)^{mn} = (x^n)^m(y^m)^n = e^me^n = ee= e$. However, since we have $|xy|=k$ then we know that $$k\leq mn.$$ Now I need to show that $mn \leq k$ to conclude that $k=mn$ and so $|x||y| = |xy|$. But I am stuck in here. I know for sure that I need to use the fact that $xy=yx$. But I dunno how

REPLY [0 votes]: If $k$ is a common multiple of $m$ and $n$, then $k=ma=nb$ for some $a,b\in\Bbb N^+$. So
$$(xy)^k=x^ky^k=(x^n)^b(y^m)^a=e$$.
Therefore, $(xy)^k=e$ for every common multiple of $m$ and $n$.
Now suppose that $(xy)^k=e$, then $x^k=y^{-k}=y^{m-k}$. $|x^k|=n/d$ where $d=(n,k)$ and $|y^{m-k}|=n/d$ as well.
But $|y^{m-k}|=m/d'$ with $d'=(m-k,m)$.
So,
$$\frac nd= \frac md'\implies nd'=md.$$
Since $(m,n)=1$, $m|d'$ and $n|d$. So
$n=d$ and $m=d'$, and so $x^k=e=y^k$.


TITLE: What is a bispectrum analysis?
QUESTION [2 upvotes]: I am in the atmospheric sciences and when I read papers on non linear interactions I came up with this term - bispectrum. It is not very clear what a 2nd order cumulant is .
So assuming I have wind speed magnitude across a latitude circle as a function of longitude and time I know that I can take a Fourier expansion of the wind speed across the entire globe. So then I can check for wavenumber from that Fourier expansion. I can also check for the temporal frequency of a wave. Then I am lost. Why would I want to take the bispectrum analysis ?
So the paper I am reading talks of a cross spectrum analysis. I am not sure what that means but I am presuming if a particular time series has different temporal frequencies and assuming if the energies associated with these temporal frequencies interact with each other will that show up in a bispectrum analysis as explained in the introduction of this article - Introduction to bispectrum?
Here is a paper(not from my field) but from plasma physics that talks of the cross bispectrum.
By taking simple use cases can somebody explain what is a bispectrum and from that a cross bispectrum ?

REPLY [1 votes]: I know my response is a bit late but I hope it can help someone who got stuck on the bispectrum just as I have in the last few days. Since I've just learnt about it today, you should proof check everything in this comment. Anyway, my goal is mostly to give you an overall and intuitive view of what it is. You should also refer to : Digital Bispectral Analysis and Its Applications to
Nonlinear Wave Interactions by Young C. Kim (1979).
Here's my match plan :

Introduce moment-generating function (MGF) and cumulant generating function (CGF).
Introduce the formula for the bispectrum
Try to interpret what it means

1)  The first order MGF $M_X(t)$ can be thought of as the expected value of a function $f(x)$ of a random variable and is written
$$ M_X(t)= E[f(x)] = \int_{-\infty}^\infty e^{tx} f(x) dx $$
where E denote the expected value. An higher order only means we deal with more than 1 function. Knowing probability density function, we do the convolution $*$ of our sequence of function $$ M_{X_1...X_N}(t)= E[f_1(x)...f_N(x)] = \int_{-\infty}^\infty e^{tx} f_1(x)*...*f_N(x) dx $$
The CGF is more complex but as long as we assume stationary wave (which is usually assumed and means $x(t)=\sum_k X_k e^{-i\omega_kt}$ where $X_k$ doesn't depend on $t$, we can write $C_X(t)=M_X(t)$ for second and third order.
2) From Wikipedia : The bispectrum is the third-order cumulant-generating function.
What does it means ? First, we need 3 functions since it is third order : $f_1$, $f_2$ and $f_{1+2}$. The bispectra is defined
$$B(k,l) = F\{C_3(f_1, f_2, f_1+f_2)\} = F\{ E[f_1 \cdot f_2 \cdot f^C(f_1 + f_2)]\} $$ where F is the Fourier transform, $C$ means complex conjugate and we are doing regular multiplication (instead of convolution). To be honest, I'm not really familiar with the cumulant spectra but it seems close to a quantum mechanical wavefunction. Using the convolution theorem, we get
$$ B(f_1,f_2) = \int_{-\infty}^\infty e^{tx} f_1*f_2*(f_1+f_2) dx = F[f_1] \cdot F[f_2] \cdot F^C[f_1 + f_2]$$
3) What is it actually. The bispectrum is the Fourier-transformed counterpart of the three-point correlation function. The three-point correlation function is a function which if given two values at two points, gives us the expected value for a third point. i.e. If we have the density at two points $\rho(r_1), \rho(r_2)$ of a nebulae, it will gives us the correlation at a third point (We assume the value we want to find as a circular distribution which doesn't depend on the angle). A correlation function measure the order of a system as how the spin or the density at different positions are related. So if I understand correctly, and as I said, take this with a grain of salt as I'm no expert, instead of getting the value at two points, we get the value at two frequencies. To continue the example, we would get the density $\rho(f_1), \rho(f_2)$ and determine the correlation with a third frequency.
Normally, we will study correlation function knowing only one position or one frequency and try to determine it at another value. The power of the bispectra is that, since it depends on two values, it can captures higher order effect.


TITLE: Integrating functions in real analysis
QUESTION [1 upvotes]: The following is a True/False problem from an exam I got back:
If $f'(x)=1$ for each $x\in\mathbb{R}$ and $f(2)=7$ then $f(-2)=-7$.
I said false for this problem, but it was marked wrong. My reasoning for this was to treat this as an initial value problem. First, integrate $f'(x)$ so that $f(x)=\int f'(x)dx=x+c$. Next solve for $c$ from $f(2)=7$. Thus $2+c=7\implies c=5$. So our function is $f(x)=x+5$ where $f'(x)=1\forall x\in\mathbb{R}$ and $f(2)=7$. Both of the statements in the AND statement in the hypothesis are true, therefore the hypothesis is true. Next, checking $f(-2)=3\neq-7$ therefore the conclusion of the implication is false. Here we have True imply false, therefore the implication is false.
Is there an error in my rationale?

REPLY [6 votes]: Your argument is correct. Besides, note that$$\frac{f(2)-f(-2)}{2-(-2)}=\frac{14}4=\frac72.$$But, by the mean value theorem, that quotient should be $1$.


TITLE: Probability that one random graph is contained in another
QUESTION [3 upvotes]: Let $G_{n,p}, n\in \mathbb{N}, p\in(0,1)$ be the binomial random graph, i.e. a graph on $n$ vertices where an edge is in $G_{n,p}$ with probability $p$.
For some $q\in(0,1)$, what is the probability that $G_{n,p}\subset G_{n,q}$?

REPLY [3 votes]: Assuming that the two graphs are independent of each other, we could do the following, where $N:=\binom{n}{2}$:$\newcommand{\order}[1]{\lvert #1\rvert}$
Start by partition the set of all graphs on $[n]$ based on the number of edges they contain; let $\mathcal{G}_{n,k}$ be the set of such graphs on $[n]$ with $k$ edges. Then we get
$$
\begin{align*}
P(G_{n,p}\subseteq G_{n,q})=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}P(G_{n,p}=G,\ G_{n,p}\subseteq G_{n,q})=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}P(G_{n,p}=G,\ G\subseteq G_{n,q}).
\end{align*}
$$
Now, of course these events are independent, and so we can break up the probability. Further, if $G$ contains $k$ edges, then $P(G_{n,p}=G)=p^k(1-p)^{N-k}$ and $P(G\subseteq G_{n,q})=q^k$. Hence
$$
\begin{align*}
P(G_{n,p}\subseteq G_{n,q})&=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}P(G_{n,p}=G)P(G\subseteq G_{n,q})\\
&=\sum_{k=0}^{N}\sum_{G\in \mathcal{G}_{n,k}}p^k(1-p)^{N-k}q^k\\
&=\sum_{k=0}^{N}\binom{N}{k}(pq)^k(1-p)^{N-k}\\
&=(1-p+pq)^N.
\end{align*}
$$
Note that this is definitely in $[0,1]$: writing the base as $1-(p-pq)=1-p(1-q)$ shows this.

Another way to come to this:
The event that $G_{n,p}\subseteq G_{n,q}$ is precisely the event that each edge is either not contained in $G_{n,p}$ or is contained in both $G_{n,p}$ and $G_{n,q}$. These are disjoint events, and the events that this holds for each edge are independent of each other.
For a given edge $e$, the probability of this is
$$
P(e\notin G_{n,p}\text{ or }e\in G_{n,p}\text{ and }G_{n,q})=(1-p) + pq.
$$
Noting that there are $N$ such edges, we again get
$$
P(G_{n,p}\subseteq G_{n,q})=(1-p+pq)^N.
$$


text:
\begin{document}

\maketitle

\begin{abstract}
We give an estimate for sums appearing in the Nyman-Beurling criterion for the Riemann
Hypothesis. These sums contain the M\"obius function and are related to the imaginary part
of the Estermann zeta function. The estimate is remarkably sharp in comparison to other sums containing the M\"obius function. The bound is smaller than the trivial bound - essentially the number of terms - by a fixed power of that number. The exponent is made explicit. The methods intensively use tools from the theory of continued fractions and from the theory of
Fourier series.

\textbf{Key words:} Riemann Hypothesis, Riemann zeta function, Nyman-Beurling-B\'aez-Duarte criterion.\\
\textbf{2000 Mathematics Subject Classification:} 30C15, 11M26, 42A16, 42A20

\newline

\end{abstract}

\section{Introduction}

According to the approach of Nyman-Beurling-B\'aez-Duarte (see \cite{baez1}, \cite{BEC}) to the Riemann Hypothesis, the Riemann Hypothesis is true if and only if
$$\lim_{N\rightarrow \infty} d_N^2=0\:,$$
where
\[
d_N^2:=\inf_{D_N}\frac{1}{2\pi}\int_{-\infty}^\infty\left|1-\zeta D_N\left(\frac{1}{2}+it\right)\right|^2\frac{dt}{\frac{1}{4}+t^2}\tag{1.1}
\]
and the infimum is over all Dirichlet polynomials
$$D_N(s):=\sum_{n=1}^{N}\frac{a_n}{n^s}\:,\ a_n\in\mathbb{C}\:,$$
of length $N$ (see \cite{bcf}).\\
Various authors (cf. \cite{baez1}, \cite{baez2}, \cite{burnol}) have investigated the question, which
asymptotics hold for $d_N$ if the Riemann Hypothesis is true.\\

S. Bettin, J. B. Conrey and D. W. Farmer \cite{bcf} show the following:\\
If the Riemann Hypothesis is true and if
$$\sum_{|Im(\rho)|\leq T}\frac{1}{|\zeta'(\rho)|^2}\ll T^{\frac{3}{2}-\delta}$$
for some $\delta>0$, then
$$\frac{1}{2\pi}\int_{-\infty}^{\infty}\left|1-\zeta V_N\left(\frac{1}{2}+it\right)\right|^2\frac{dt}{\frac{1}{4}+t^2}\sim\frac{2+\gamma-\log4\pi}{\log N}$$
for
\[
V_N(s):=\sum_{n=1}^N\left(1-\frac{\log n}{\log N}\right)\frac{\mu(n)}{n^s}\:.\tag{1.2}
\]
Moreover, it follows from \cite{bcf} that under certain assumptions among all Dirichlet polynomials $D_N(s)$ the infimum in (1.1) is assumed for $D_N(s)=V_N(s)$. It thus is of interest to obtain an unconditional estimate for the integral in (1.1).\\
If we expand the square in (1.1) we obtain
\begin{align*}
d_N^2&=\inf_{D_N}\Bigg(\int_{-\infty}^\infty\left(1-\zeta\left(\frac{1}{2}+it\right)D_N\left(\frac{1}{2}+it\right)-\zeta\left(\frac{1}{2}-it\right)\overline{D}_N\left(\frac{1}{2}+it\right)\right)\frac{dt}{\frac{1}{4}+t^2}\\
&\ \ \ +\int_{-\infty}^\infty\left|\zeta\left(\frac{1}{2}+it\right)\right|^2\left|D_N\left(\frac{1}{2}+it\right)\right|^2\frac{dt}{\frac{1}{4}+t^2}\Bigg)\:.
\end{align*}
The last integral evaluates as
$$\sum_{1\leq h,k\leq N} a_h\bar{a_k} h^{-1/2}k^{-1/2} \int_{-\infty}^\infty\left|\zeta\left(\frac{1}{2}+it\right)\right|^2\left(\frac{h}{k}\right)^{it}\frac{dt}{\frac{1}{4}+t^2}\:.$$
We have
\begin{align*}
b_{h,k}&:=\frac{1}{2\pi\sqrt{hk}}\int_{-\infty}^\infty\left|\zeta\left(\frac{1}{2}+it\right)\right|^2\left(\frac{h}{k}\right)^{it}\frac{dt}{\frac{1}{4}+t^2}\\
&=\frac{\log2\pi-\gamma}{2}\left(\frac{1}{h}+\frac{1}{k}\right)+\frac{k-h}{2hk}\log\frac{h}{k}-\frac{\pi}{2hk}\left(V\left(\frac{h}{k}\right)+V\left(\frac{k}{h}\right)\right)\:,\tag{1.3}
\end{align*}
where
$$V\left(\frac{h}{k}\right):=\sum_{m=1}^{k-1}\left\{\frac{mh}{k}\right\}\cot\left(\frac{\pi m h}{k}\right)$$
is Vasyunin's sum (see \cite{VAS}).\\
It can be shown that
\[
V\left(\frac{h}{k}\right)=-c_0\left(\frac{\bar{h}}{k}\right),\tag{1.4}
\]
where $h\bar{h}\equiv 1(\bmod k)$, with the cotangent sum
$$c_0\left(\frac{h}{k}\right):=\sum_{l=1}^{k-1}\frac{l}{k}\cot\left(\frac{\pi h l}{k}\right)\:,$$
where $h,k\in\mathbb{N}$, $k\geq 2$, $1\leq h\leq k$, $(h,k)=1$ (see \cite{BEC}, \cite{mr}).

Ishibashi \cite{ISH} observed that $c_0$ is related to the value at $s=0$ or $s=1$
of the Estermann zeta function by the functional equation of the \textit{imaginary part}. Namely
$$c_0\left(\frac{a}{q}\right)=\frac{1}{2}D_{sin}\left(0,\frac{a}{q}\right)=2q\pi^{-2}D_{\sin}\left(1,\frac{\bar{a}}{q}\right)\:,$$
where for $x\in\mathbb{R}$, $Re(s)>1$, we have:
$$D_{\sin}(s,x):=\sum_{n=1}^\infty\frac{d(n)\sin(2\pi nx)}{n^s}$$
and $a\bar{a}\equiv 1(\bmod q)$.\\
If $x\in\mathbb{R}\setminus\mathbb{Q}$, then Wilton \cite{wilton} showed that the convergence of the above series at $s=1$ is equivalent to the convergence of
$$\sum_{n\geq 1}(-1)^n\frac{\log v_{n+1}}{v_n}\:,$$
where $u_n/v_n$ denotes the $n$-th partial quotient of $x$.\\
The irrational numbers for which this sum converges are called \textbf{Wilton numbers}.

A basic ingredient in the papers \cite{mr2}, \cite{mr5} have been the representations of
Balazard, Martin in their papers \cite{balaz1}, \cite{balaz2}, of the function
$$g(x):=\sum_{l\geq 1}\frac{1-2\{lx\}}{l}\:,$$
involving the Gauss transform from the theory of continued fractions as well as from the paper \cite{Marmi}, by Marmi, Moussa and Yoccoz.\\
One can show (\cite{bre}) that $g(x)$ can also be written in the form
$$-\sum_{n\geq 1}\frac{d(n)}{\pi n}\:\sin(2\pi n x)=-\frac{1}{\pi}\: D_{sin}(1, x)\:.$$
These concepts and results also play an important role in the present paper. We shall represent them in the next section.\\

\textit{Remark.} There is another, simpler, approach to our result. By \cite{bettin} (see 1st
display of page 5) $V(h/k)$ is approximately
$$\sum_{n\leq k^2}\frac{d(n)}{n}\:\sin\left(2\pi n \:\frac{h}{k}\right)\:.$$
One then may use well-known estimates for exponential sums containing the M\"obius function
(cf. \cite{IKW}, formula (13.49)).

\section{Statement of result}

We prove the following theorem:
\begin{theorem}\label{main}
Let $D\geq 2$. Let $C$ be the number which is uniquely determined by
$$C\geq \frac{\sqrt{5}+1}{2},\ 2C-\log C - 1- 2\log 2=\frac{1}{2}\log 2\:.$$
Let $v_0$ be determined by
$$v_0\left(1-\left(1+2\log 2\left(C+\frac{\log 2}{2}\right)^{-1}\right)^{-1}+2+\frac{4}{\log 2} C\right)=2\:.$$
Let $z_0:=2-\left(2+\frac{4}{\log 2} C\right) v_0$. Then for all $\epsilon >0$ we have
$$\sum_{k^D\leq n< 2k^D} \mu(n)g\left(\frac{n}{k}\right)\ll_{\epsilon} k^{D-z_0+\epsilon}\:.$$
\end{theorem}

\section{Continued Fractions}
In this section we provide some basic facts related to the theory of continued fractions. We also recall facts and results from the papers \cite{balaz2}.
\begin{definition}\label{def21}
Let $X:=[0,1]\setminus\mathbb{Q}$. For $x\in(0,1)$ we set $\alpha(x):=\{1/x\}$. For $x\in X$ we define recursively
$$\alpha_0(x):=x,\ \alpha_l(x):=\alpha(\alpha_{l-1}(x)),\ \ \text{for $l\in\mathbb{N}$}\:.$$
This definition is also valid for $x\in\mathbb{Q}$ and $l\in\mathbb{N}$, whenever $\alpha_{l-1}(x)\neq 0$. We set
$$a_l(x):=\left[\frac{1}{\alpha_{l-1}(x)}\right]\:.$$
\end{definition}
We have:
\begin{lemma}\label{lem22}
For $x\in X$, let
$$x=[0;a_1(x),\ldots, a_l(x),\ldots]$$
be the continued fraction expansion of $x$.\\
For $x\in(0,1)\cap \mathbb{Q}$ we have
$$x=[0;a_1(x),\ldots, a_L(x)]\:,$$
where $L$ is the last $l$, for which $\alpha_{l-1}\neq 0$.\\
We define the partial quotient of $p_l(x), q_l(x)$ by
$$\frac{p_l(x)}{q_l(x)}:=[0;a_1(x),\ldots, a_l(x)],\ where\ (p_l(x), q_l(x))=1\:.$$
We have
$$p_{l+1}=a_{l+1}p_l+p_{l-1}$$
$$q_{l+1}=a_{l+1}q_l+q_{l-1}\:.$$
\end{lemma}
\begin{proof}
(cf. \cite{hens}, p. 7.)
\end{proof}

\begin{definition}\label{def23}
For $r\in(0,1)\cap\mathbb{Q}$ let
$$r=[0;a_1(r),\ldots, a_L(r)]\:.$$
Then we call $L$ the \textbf{depth} of $r$.
\end{definition}

\begin{definition}\label{def24}
Let $x\in X$. Then for $l\in\mathbb{N}_0:=\mathbb{N}\cup\{0\}$, we set:
$$\beta_l(x):=\alpha_0(x)\alpha_1(x)\cdots \alpha_l(x)$$
(by convention $\beta_{-1}=1$) and
$$\gamma_l(x):=\beta_{l-1}(x)\log\frac{1}{\alpha_l(x)},\ \text{where}\ l\geq 0,$$
so that $\gamma_0(x)=\log(1/x).$\\
Let $r\in(0,1)\cap\mathbb{Q}$ be a rational number of depth $L$. Then we set:
$$\beta_l(r):=\alpha_0(r)\alpha_1(r)\ldots \alpha_l(r)\:,\ \ \text{for $0\leq l\leq L$ }$$
and
$$\gamma_l(r):=\beta_{l-1}(r)\log\frac{1}{\alpha_l(r)}\:,\ \ \text{for $0\leq l\leq L$.}$$
For $x\in X$ we define Wilton's function $\mathcal{W}(x)$ by
$$\mathcal{W}(x):=\sum_{l\geq 0}(-1)^l\gamma_l(x)\:,\ \ \text{for all $x\in X$,}$$
for which the series is convergent.
\end{definition}

\begin{definition}\label{def25}(definitions from Sec. 4.1 of \cite{balaz2})$ $\\
For $\lambda\geq 0$ let
$$A(\lambda):=\int_0^\infty\{t\}\{\lambda t\}\frac{dt}{t^2}\:.$$
For $x>0$ let
$$Q(x):=\frac{x+1}{2}A(1)-A(x)-\frac{x}{2}\log x\:.$$
For $x\in X$ let
$$G(x):=\sum_{j\geq 0}(-1)^j\beta_{j-1}Q(\alpha_j(x))\:.$$
For a rational number $r$ of depth $L$ let
$$G(r):=\sum_{j\leq L}(-1)^j \beta_{j-1}(r)Q(\alpha_j(r))\:.$$
\end{definition}

\begin{lemma}\label{lem26}
We have
$$\sup_{\lambda\geq 1}|A(\lambda+h)-A(\lambda)|\leq \frac{1}{2}h\log\left(\frac{1}{h}\right)+O(h)\:,\ \ (0<h< 1)\:.$$
\end{lemma}
\begin{proof}
This is Proposition 28 of \cite{balaz2}.
\end{proof}

\begin{definition}\label{def27}
Let
\begin{eqnarray}
\delta(x):=\left\{
  \begin{array}{l l}
   0\: & \quad \text{, if $x\in X$}\vspace{2mm}\\
    \frac{(-1)^{L+1}A(1)}{2q}\: & \quad \text{, if $x=p/q\in[0,1]$, $(p,q)=1$, $x$ of depth $L$}\:.\\
  \end{array} \right.
\nonumber
\end{eqnarray}
\end{definition}

\begin{lemma}\label{lem27}
The series $g(x)$ and $\mathcal{W}(x)$ converge for the same values $x\in[0,1]$ and we have
$$g(x)=\mathcal{W}(x)-2G(x)-2\delta(x)$$
in each point of convergence.
\end{lemma}
\begin{proof}
This is Proposition 28 of \cite{balaz2}.
\end{proof}

\begin{definition}\label{def28}
For $s\in\mathbb{N}$, $x\in X$ or $x$ a rational number with depth $\geq s$,
we define
$$\mathcal{L}(x, s):=\sum_{\nu=0}^s(-1)^\nu(T^\nu l)(x)\:,$$
where $l(x):=\log(1/x)$ and the operator $T\::\: L^p\rightarrow L^p$ is defined
by $$Tf(x):=xf(\alpha(x))\:.$$
We write
$$g(x)=:g_{sm}(x, s)+g_{sing}(x,s)\:,$$
where
$$g_{sm}(x, s)=\mathcal{L}(x, s)\:.$$
We call $g_{sm}$ the ``smooth part" and $g_{sing}$ the ``singular part" of $g$.
\end{definition}

\begin{lemma}\label{lem29}
Let $x\in X$ be a Wilton number or a rational number. Then we have:
$$\mathcal{W}(x)=l(x)-x\mathcal{W}(\alpha(x))\:.$$
\end{lemma}
\begin{proof}
This follows directly from the definition of Wilton's function $\mathcal{W}(x)$.
\end{proof}

\begin{lemma}\label{lem210}
For $s\in\mathbb{N}$, $x\in X$ or $x$ a rational number with depth
$\geq s+1$ we have
$$\mathcal{L}(x,s)=\mathcal{W}(x)-(-1)^{s+1}T^{s+1}\mathcal{W}(x)\:.$$
\end{lemma}
\begin{proof}
This follows from Lemma \ref{lem29} by the same computation as in the
proof of Lemma 2.10 in \cite{mr5}, which is valid also for $x$ a rational number with depth $\geq s+1$.
\end{proof}

\begin{lemma}\label{lem211}
For $s\in\mathbb{N}_0$, $x\in X$ or $x$ a rational number of depth $\geq s+1$ we have
$$\alpha_s(x)\alpha_{s+1}(x)\leq \frac{1}{2}\:.$$
\end{lemma}
\begin{proof}
This is Lemma 2.11 of \cite{mr5}, whose proof is also valid for rational $x$ of depth $\geq s+1$.
\end{proof}

\begin{definition}\label{def212}
Let $\mathcal{E}$ be a measurable subset of $(0,1)$. The measure $m$
is defined by
$$m(\mathcal{E}):=\frac{1}{\log 2}\int_{\mathcal{E}}\frac{dx}{1+x}\:.$$
\end{definition}

\begin{lemma}\label{lem213}
The measure $m$ is invariant with respect to the map $\alpha$, i.e.
$$m(\alpha(\mathcal{E}))=m(\mathcal{E})$$
for all measurable subsets $\mathcal{E}\subseteq (0,1)$.
\end{lemma}
\begin{proof}
This result is well-known.
\end{proof}

\begin{lemma}\label{lem213}
Let $s\in \mathbb{N}$, $p>1$. For $f\in L^p$, we have
$$\int_0^1|T^s f(x)|^p dm(x)\leq g^{(s-1)p}\int_0^1|f(x)|^pdm(x)\:,$$
where
$$g:=\frac{\sqrt{5}-1}{2}<1\:.$$
\end{lemma}
\begin{proof}
For the proof of this result, due to Marmi, Moussa and Yoccoz \cite{Marmi}, see \cite{mr5} Lemma 2.8, (ii).
\end{proof}

\begin{definition}\label{def215}
Let $s\in\mathbb{N}$, $b_0=0$ and $b_1,\ldots, b_s\in\mathbb{N}$. The \textbf{cell} of depth $s$, $\mathcal{C}(b_1,\ldots, b_s)$ is the interval with the endpoints $[0;b_1,\ldots, b_s]$ and \mbox{$[0;b_1,\ldots, b_{s-1},b_s+1]$.}
\end{definition}

\begin{lemma}\label{lem216}
In the interior of the cell $\mathcal{C}(b_1,\ldots, b_s)$ of depth $s$, the
functions $a_j, p_j, q_j$ are constants for $j\leq s$,
$$a_j(x)=b_j,\ \frac{p_j(x)}{q_j(x)}=[0; b_1,\ldots, b_j],\ (x\in\mathcal{C}(b_1,\ldots, b_j))\:.$$
The endpoints of $\mathcal{C}(b_1,\ldots, b_s)$ are
\[
\frac{p_s}{q_s}\ \ \text{and}\ \ \frac{p_s+p_{s-1}}{q_s+q_{s-1}}\:.\tag{3.1}
\]
For $x\in X$ and $s\in\mathbb{N}$ there is a unique cell of depth $s$
that contains $x$.\\
Within a cell of depth $s$ we have the derivatives
$$\alpha_s'=(-1)^s(q_s+\alpha_sq_{s-1})^2\:,$$
$$\gamma_s'=(-1)^sq_{s-1}\log\left(\frac{1}{\alpha_s}\right)+(-1)^{s-1}/\beta_s\:.$$
We also have
$$\beta_s(x)=\frac{1}{q_{s+1}(x)+\alpha_{s+1}(x)q_s(x)}\ \ (x\in X)\:.$$
\end{lemma}
\begin{proof}
See \cite{balaz2}, sections 2.2, 2.3 and 2.4.
\end{proof}

\begin{lemma}\label{lem216b}
Let $\mathcal{C}=\mathcal{C}(b_1,\ldots, b_s)$ a cell of depth $s$, $x_1, x_2\in\mathcal{C}$, $d=|x_2-x_2|$. Then we have:
$$|g(x_1)-g(x_2)|\ll d^{2}q_{s+1}\log s+2^{-s/2}\log k\:.$$
\end{lemma}
\begin{proof}
Let without loss of generality $x_1<x_2$. From Definition \ref{def28} and the
formula for $\gamma'_s$ in Lemma \ref{lem216} it follows by integration over the
interval $[x_1, x_2]$ that
\[
|g_{sm}(x_1)-g_{sm}(x_2)|\ll d^2 q_{s+1}\log s\:.\tag{3.2}
\]
From Lemma \ref{lem211} we obtain
\[
|g_{sing}(x_i)|\leq 2^{-s/2}\log k\ \ (i=1, 2).\tag{3.3}
\]
The result follows from (3.2) and (3.3).
\end{proof}

\begin{lemma}\label{lem217}
Let $\mathcal{C}(b_1,\ldots, b_s)$ be as in Definition \ref{def215}. Then we have
$$\log\text{meas}(\mathcal{C}(b_1,\ldots, b_s))\leq -2\sum_{j=1}^s \log b_j\:.$$
\end{lemma}
\begin{proof}
The cell $\mathcal{C}(b_1,\ldots, b_s)$ has the length
\[
\frac{1}{q_s(q_s+q_{s-1})}\:.\tag{3.4}
\]
From $q_j=b_{j+1}q_j+q_{j-1}$ it follows by induction that
\[
q_j\geq \prod_{i\leq j} b_i\:.  \tag{3.5}
\]
From (3.4) and (3.5) it follows that
$$\text{meas}(\mathcal{C}(b_1,\ldots, b_s))\leq  \prod_{j\leq s}  b_j^{-2}\:, $$
which concludes the proof of Lemma \ref{lem217}.
\end{proof}

\begin{lemma}\label{lem218}
We have $$\log q_s\leq 2\sum_{1\leq j\leq s}\log b_j+s\log 2\:.$$
\end{lemma}
\begin{proof}
This follows from
$$q_{j+1}=b_{j+1}q_j+q_{j-1}\leq 2b_{j+1}q_j\:.$$
\end{proof}

\begin{lemma}\label{lem219}
Let $\epsilon>0$, $C_1\geq\frac{\sqrt{5}+1}{2}$, $C_2=\frac{1}{2}C_1-\log C_1-1+\log 2$. Then we have for $s\geq s(\epsilon)$ sufficiently large:
$$meas\{x\in(0,1)\::\: q_s(x)\geq \exp(C_1s)\}\leq \exp(-(C_2-\epsilon)s)\:.$$
\end{lemma}
\begin{proof}
The smallest sequence $(q_s)$ is obtained for $b_j=1$ for all $j\leq s$, which
gives $q_s=F_s$, $F_s$ being the $s$-th Fibonacci number. This shows that
the assumption $C_1\geq\frac{\sqrt{5}+1}{2}$ does not imply any loss of generality.\\
By partition into cells of depth $s$ we obtain from Lemmas \ref{lem217} and \ref{lem218}
the following:
\begin{align*}
&meas\{x\in(0,1)\::\: q_s(x)\geq \exp(C_1s)\}\leq\sum_{\substack{\vec{b}=(b_1,\ldots,b_s)\in\mathbb{N}^s\::\\\sum_{1\leq j\leq s}\log b_j\geq \frac{1}{2}C_1s}}meas(\mathcal{C}(b_1,\ldots, b_{s}))\\

&\ \ \ \ \ \ \ \leq \sum_{\substack{\vec{b}\in\mathbb{N}^s\::\\ \sum_{1\leq j\leq s}\log b_j\geq \frac{1}{2}C_1s}}\left(\int_{b_1}^{b_1+1}[u_1]^{-2}\:du_1  \right)\cdots \left(\int_{b_s}^{b_s+1}[u_s]^{-2}\:du_s  \right)\\
&\ \ \ \ \ \ \ \leq 2^s \int\displaylimits_{\substack{[1,\infty)^s\::\\ \sum_{1\leq j\leq s}\log u_j\geq \frac{1}{2}C_1s}} (u_1\cdots u_s)^{-2}\: du_1\cdots du_s\\
&\ \ \ \ \ \ \ =2^s \int\displaylimits_{{\mathbb{R}_+^s\::\:v_1+\cdots+v_s\geq \frac{1}{2}C_1s}} \exp(-v_1-\cdots -v_s)\: dv_1\cdots dv_s\:. \tag{3.6}
\end{align*}
The integral in (3.6) is
$$Prob\left(X_1+\cdots+X_s\geq\frac{1}{2}C_1s\right)\:,$$
where $X_1,\ldots, X_s$ are i.i.d. exponentially distributed random variables with rate 1. The distribution of the sum $X_1+\cdots+X_s$ is the Gamma
distribution with density
\[
f(x,s,1)=\frac{x^{s-1}e^{-x}}{(s-1)!}\tag{3.7}
\]
Lemma \ref{lem219} now follows from (3.6), (3.7) and Stirling's formula.
\end{proof}

\vspace{7mm}

\section{Vaughan's identity}

We now express the M\"obius function by Vaughan's identity.
\begin{lemma}\label{lem31}
Let $w>1$. For $n\in\mathbb{N}$ we have:
$$\mu(n)=c_1(n)+c_2(n)+c_3(n)\:,$$
where
$$c_1(n):=\sum_{\substack{\alpha\beta\gamma=n\\\alpha\geq w,\: \beta\geq w}}\mu(\gamma)c_4(\alpha)c_4(\beta)\:,$$
for
$$c_4(\alpha):=-\sum_{\substack{(d_1,d_2)\::\: d_1d_2=\alpha\\ d_1\leq w}}\mu(d_1)\:.$$
\begin{eqnarray}
c_2(n):=\left\{
  \begin{array}{l l}
   2\mu(n)\: & \quad \text{, if $n\leq w$}\vspace{2mm}\\
    0\: & \quad \text{, if $n>w$}\\
  \end{array} \right.
\nonumber
\end{eqnarray}
and
$$c_3(n):=-\sum_{\substack{\alpha\beta\gamma=n\\\alpha\leq w,\: \beta\leq w}}\mu(\alpha)\mu(\beta)\:.$$
\end{lemma}
\begin{proof}
We introduce the generating Dirichlet series
$$\sum_{n=1}^{+\infty}c_1(n)n^{-s}=\frac{1}{\zeta(s)}E(s)^2$$
$$\sum_{n=1}^{+\infty}c_2(n)n^{-s}=2M_w(s)$$
$$\sum_{n=1}^{+\infty}c_3(n)n^{-s}=-M_w(s)^2\zeta(s)$$
where
$$M_w(s):=\sum_{n\leq w}\mu(n)n^{-s}\:,$$
and
$$E(s):=\zeta(s)M_w(s)-1\:.$$
The proof follows by comparison of the coefficients of these Dirichlet series.
\end{proof}

We now obtain
$$\sum_{k^D\leq n<2k^D}\mu(n)g\left(\frac{n}{k}\right)={\textstyle\sum}_{1}+{\textstyle\sum}_{2}+{\textstyle\sum}_{3}\:,$$
where
\[
{\textstyle\sum}_{i}:=\sum_{k^D\leq n<2k^D}c_i(n)g\left(\frac{n}{k}\right)\:.\tag{4.1}
\]
From the definitions for $c_1$ and $c_4$ in Lemma \ref{lem31} we obtain:
$${\textstyle\sum}_{1}=\sum_{\substack{s\geq w,\: t\geq w \\ k^D\leq st\gamma<2k^D}}\mu(\gamma)\sum(s,t)\:,$$
where
$$\sum(s,t) := \sum_{\substack{d_1d_2=s \\ d_1\leq w}}\mu(d_1)\sum_{\substack{e_1e_2=t \\ e_1\leq w}}\mu(e_1)g\left(\frac{d_1d_2e_1e_2\gamma}{k}\right)\:.$$
We now choose
$$w=k^{2\delta_0},\ \text{for}\ \delta_0>0\ \text{fixed}\:,$$
to be determined later. We also fix $v_0>0$ to be determined later as well.\\
We partition the sum ${\textstyle\sum}_{1}$ as follows:
\[
{\textstyle\sum}_{1}={\textstyle\sum}_{1,1}+{\textstyle\sum}_{1,2}\tag{4.2}
\]
with
\[
{\textstyle\sum}_{1,1}:=\sum_{\substack{s\geq w,\: t\geq w \\ k^D\leq st\gamma<2k^D\\st\geq k^{4\delta_0+4v_0}}}\mu(\gamma)\sum(s,t)\tag{4.3}
\]
and
\[
{\textstyle\sum}_{1,2}:=\sum_{\substack{s\geq w,\: t\geq w\\ k^D\leq st\gamma<2k^D\\st< k^{4\delta_0+4v_0}}}\mu(\gamma)\sum(s,t)\:.\tag{4.4}
\]

\vspace{7mm}

\section{The sum ${\textstyle\sum}_{1,1}$}

We further partition the sum ${\textstyle\sum}_{1,1}$. The condition
$$d_1e_1d_2e_2\geq k^{4\delta_0+4v_0}$$
implies that $d_2e_2\geq k^{4v_0}$ and therefore at least one of the following
two cases must hold:\\
1) $d_2\geq k^{2v_0}$\\
2) $e_2\geq k^{2v_0}\:.$

\noindent By symmetry we may restrict ourselves to the case $e_2\geq k^{2v_0}$.\\
For $v\geq v_0$ we define the partial sum ${\textstyle\sum}_{1,1}^{(v)}$ of
${\textstyle\sum}_{1}$ by
\[
{\textstyle\sum}_{1,1}^{(v)}:=\sum_{\substack{s\geq w,\: t\geq w\\ k^D\leq st\gamma<2k^D\\k^{2v}\leq e_2<2k^{2v} }}\mu(\gamma)\sum_{\substack{d_1d_2=s\\ d_1\leq w}}\mu(d_1)\sum_{\substack{e_1e_2=t\\ e_1\leq w}}\mu(e_1)g\left(\frac{d_1d_2e_1e_2\gamma}{k} \right)  \tag{5.1}
\]
We then partition the sum ${\textstyle\sum}_{1,1}$ into $O(\log k)$ partial sums of
the form ${\textstyle\sum}_{1,1}^{(v)}$.
\[
{\textstyle\sum}_{1,1}:={\textstyle\sum}_{1,1}^{(v_0)}+{\textstyle\sum}_{1,1}^{(v_1)} +\cdots+{\textstyle\sum}_{1,1}^{(v_z)}\:, \tag{5.2}
\]
where $v_0<v_1<\cdots< v_z$. In the sequel we assume $v\geq v_0$ fixed and
estimate the sum ${\textstyle\sum}_{1,1}^{(v)}$.\\
We fix $\delta_1=\delta_1(v)>0$, $\delta_2=\delta_2(v)>0$
to be determined later. We construct an appropriate Diophantine approximation
of $l/k$.  By the Theorem of Dirichlet there are positive integers $a$, $q=q(l)$,
$(a, q)=1$, $q\leq k^{\delta_2}$, such that
\[
\left|  \frac{l}{k}-\frac{a}{q} \right|\leq (qk^{\delta_2})^{-1}\:.\tag{5.3}
\]

\begin{definition}\label{defn4141}
For $\vec{d}=(d_1, d_2, e_1, \gamma)$ let $l(\vec{d})$ be the uniquely defined
integer $l$ with $0<l\leq k$, $l\equiv \Pi(\vec{d}\:)\: \bmod k$, where $\Pi(\vec{d}\:)=d_1d_2e_1\gamma$. We define the exceptional set
$$\mathcal{E}(v, \delta_1, \delta_2, k):=\{\vec{d}=(d_1, d_2, e_1, \gamma)\::\:\exists e_2\in [k^{2v}, 2k^{2v}),\ k^D\leq \Pi(\vec{d}\:)e_2<2k^D\}\:.$$
\end{definition}

\begin{lemma}\label{lem4141}
We have
$$|\mathcal{E}(v, \delta_1, \delta_2, k)|=O_\epsilon(k^{D-2v+\delta_1-\delta_2+\epsilon})$$
for all $\epsilon >0$.
\end{lemma}
\begin{proof}
Let $\vec{d}\in \mathcal{E}(v, \delta_1, \delta_2, k)$, $l= l(\vec{d})$ and $q(l)<k^{\delta_1}$. Then there is an interval
$$N(a, q)=\left(\frac{a}{q}-\left(qk^{\delta_1}\right)^{-1},\ \frac{a}{q}+\left(qk^{\delta_1}\right)^{-1}\right) $$
of length $2(qk^{\delta_1})^{-1}$ with $l/k\in N(a, q)$.\\
$N(a, q)$ contains $\ll k^{1-\delta_1}q^{-1}$ numbers $l/k$. The set
$$\mathcal{F}:=\{l(\vec{d})k^{-1}\::\: \vec{d}\in \mathcal{E}(v, \delta_1, \delta_2, k)\}$$
is contained in the union
$$\bigcup_{(a, q)\::\: q\leq k^{\delta_1}}N(a, q)\:.$$
There are $O(k^{2\delta_1})$ pairs $(a, q)$. Thus
$$|\mathcal{F}|=O(k^{1+\delta_1-\delta_2})\:.$$
The interval $[\frac{1}{2}k^{D-2v},\ 2k^{D-2v})$ can be partitioned into
$O(k^{D-1-2v})$ abetting subintervals of length $\leq k$. \\
The result now follows from well known estimates for the divisor function $d_4$.
\end{proof}

\begin{lemma}\label{lem4242}
For all $\epsilon>0$ we have
$$\sum_{\vec{d}\in\mathcal{E}(v, \delta_1, \delta_2, k)}\left| \sum_{\substack{e_2\::\: k^{2v}\leq e_2< 2k^{2v}\\ k^D\leq \Pi(\vec{d}\:)e_2<2k^D}}g\left(\frac{\Pi(\vec{d}\:)e_2}{k}  \right) \right| =O_\epsilon\left( k^{D+\delta_1-\delta_2+\epsilon} \right)\:.  $$
\end{lemma}
\begin{proof}
This follows from Lemma \ref{lem4141} and from the bound $g(h/k)=O(\log k)$.
\end{proof}
We fix $s_1=s_1(v)>0$, $C_4>0$ to be determined later and set
\[
C_5:=\frac{1}{2}\:C_4-\log C_4-1+\log 2\:.\tag{5.4}
\]
By Lemma \ref{lem219} all but $O(k\exp(-(C_5-\epsilon)s_1))$ values of $l/k$ belong to
cells  $\mathcal{C}$ of depth $s_1$ with denominator
$$q_{s_1}(l):=q_{s_1}(\mathcal{C})\leq \exp(C_4s_1)\:.$$

\begin{definition}\label{def4242}
We call the cell $\mathcal{C}$ of depth $s_1$ \textbf{exceptional}, if
$q_{s_1}(\mathcal{C})>\exp(C_4s_1)$, otherwise non-exceptional.
\end{definition}
\begin{definition}\label{def4343}
For $k^{\delta_1}\leq q< k^{\delta_2}$ let
\[
\mathcal{A}(q):=\left\{\vec{d}\::\: \exists \: r\in \mathbb{Z},\ \left|\frac{l(\vec{d}\:)}{k}-\frac{r}{q}\right|<\frac{1}{q^2}\right\}\:.  \tag{5.5}
\]
\end{definition}

We now use the Diophantine approximation property for $\vec{d}\in\mathcal{A}(q)$
to estimate the sum
$$\sum_{\substack{e_2\::\: k^{2v}\leq e_2< 2k^{2v}\\ k^D\leq \Pi(\vec{d}\:)e_2<2k^D}}g\left(\frac{\Pi(\vec{d}\:)e_2}{k}  \right) \:.$$

\begin{definition}\label{def4444}
Let
$$\mathcal{J}:=\left[\max(k^{2v}, k^D\Pi(\vec{d}\:)^{-1},\ \min(2k^{2v}, 2k^D\Pi(\vec{d}\:)^{-1})\right)\:.$$
\end{definition}
We partition $\mathcal{J}$ into $j_0-1=O(k^{2v}q^{-1})$ abetting subintervals
$I_j=[e_{2,j},\ e_{2, j}+q)$ of length $q$ and an additional interval $I_{j_0}=[e_{2,j_0},\ e_{2, j_0}+\tilde{q})$ of length $\tilde{q}<q$:
$$\mathcal{J}=\bigcup_{j=0}^{j_0} I_j,\ e_{2, j+1}=e_{2, j}+q\ \ \text{for $0\leq j\leq j_0-2$.}$$
For each $j$ with $0\leq j\leq j_0-1$ we construct a function $\Phi_j$ as follows:\\
The elements of the sequence $(r(e_{2,j}+g))_{g=0}^{q-1}$ form a complete residue system $\bmod\: q$. Thus there is a $g_0\in \mathbb{N}_0$, such that
$$ \left| \left\{ \frac{\Pi(\vec{d}\:)}{k}\:e_{2,j} \right\}-\left\{ \frac{r(e_{2, j}+g_0)}{q} \right\} \right| \leq \frac{1}{2q}\:. $$
From the inequality (4.4) we then obtain:
\[
 \left| \left\{ \frac{\Pi(\vec{d}\:)(e_{2,j}+g)}{k} \right\}-\left\{ \frac{r(e_{2, j}+g_0+g)}{q} \right\} \right| \leq \frac{2}{q}\:. \tag{5.6}
 \]
 We then define
 $$\Phi_j(\vec{d}, e_{2, j}+g)=\left\{ \frac{r}{q}(e_{2,j}+g_0+g) \right\}\:.$$

 \begin{lemma}\label{lem4343}
 Let $\vec{d}\in \mathcal{A}(q)$, $I_j$ $(j\leq j_0-1)$ as described above. Then
 the sequence $(q\Phi_j(\vec{d}\:, e_{2,j}+g))$ forms a complete residue system
 $\bmod\: q$.
 \end{lemma}
\begin{proof}
This is contained in the observations above.
\end{proof}

\begin{definition}\label{defn4545}
Let $\vec{d}\:\in\mathcal{A}(q)$, $e_2\in I_j$. We call the pair $(\vec{d}\:, e_2)$
\textbf{separated}, if exactly one of the two numbers
$$\left\{ \frac{\Pi(\vec{d}\:)e_2}{k} \right\}\:,\ \ \Phi_j(\vec{d\:}, e_2)  $$
lies in a non-exceptional cell of depth $s_1$ or if they lie in two distinct non-exceptional cells of depth $s_1$. We call the pair $(\vec{d}\:, e_2)$
\textbf{exceptional}, if $\{\Pi(\vec{d}\:)e_2k^{-1}\}$ lies in an exceptional cell of depth $s_1$. Let $N_1(q)$ denote the number of separated pairs $(\vec{d}\:, e_2)$
with $\vec{d\:}\in \mathcal{A}(q)$ and
$N_2$ be the number of exceptional pairs $(\vec{d\:}, e_2)$.
\end{definition}

\begin{lemma}\label{lem4444}
For all $\epsilon>0$ we have\\
(i) $N_1(q)\ll_\epsilon k^{D-1+\epsilon}q^{-1}\exp(2C_4s_1)$ \\
(ii) $N_2\ll_\epsilon k^{D+\epsilon}\exp(-(C_5-\epsilon)s_1)$.
\end{lemma}
\begin{proof}
 We first consider the number $N(q, j, \vec{d}\:)$ for a fixed $\vec{d}\:$ and
 $e_2\in I_j$.\\
 By (2.1) the length of a non-exceptional cell of depth $s_1$ is $\leq \exp(-2C_4s_1)$. Thus the number of cells of depth $s_1$ is $\ll \exp(2C_4s_1)$.\\
 Let $(\vec{d}\:, e_2)$, $e_2\in I_j$ be separated. Then
 $$\left\{ \frac{\Pi(\vec{d}\:)e_2}{q} \right\}\:\ \ \text{or}\ \ \left\{ \frac{\Pi(\vec{d}\:)(e_2-1)}{q} \right\}  $$
is the smallest or the largest number of the form $r/q$ of a cell of depth $s_1$.\\
Thus for fixed $\vec{d}$ and $j$  there are
\[
\ll \exp(2C_4s_1)\tag{5.7}
\]
separated tuplets $(\vec{d}\:, e_2)$ with $e_2\in I_j$. The number of intervals
$I_j\subset [k^{2v}, 2k^{2v})$ is
\[
\ll k^{2v} q^{-1} \tag{5.8}
\]
The number of $\vec{d}$ with $\Pi(\vec{d}\:)\equiv l\bmod\: k$ is
\[
\ll k^{D-1-2v+\epsilon}\:.\tag{5.9}
\]
The result (i) follows from (5.7), (5.8), (5.9), and the result (ii) from Lemma \ref{lem219} and the formula (5.9).
\end{proof}

\begin{definition}\label{def4545}
Let
$$\mathcal{T}=\{ (\vec{d\:}, e_2)\::\: \vec{d}\in\mathcal{E}(v, \delta_1, \delta_2, k)\ \text{or}\ (\vec{d}\:, e_2)\ \text{separated or}\ (\vec{d}\:, e_2)\ \text{exceptional} \:\}$$
\end{definition}

\begin{lemma}\label{lem4545}
For all $\epsilon>0$ we have
$$\sum_{(\vec{d}\:, e_2)\in\mathcal{T}}\left| g\left(\frac{\Pi(\vec{d}\:)e_2}{k} \right) \right|\ll_\epsilon k^{D-1+\epsilon} \exp(2C_4s_1)+k^{D+\delta_1-\delta_2+\epsilon}+k^{D+\epsilon}\exp(-(C_5-\epsilon)s_1)\:.$$
\end{lemma}
\begin{proof}
This follows from Lemma \ref{lem4242}, the bound $q(l/k)=O(\log k)$, from Lemma \ref{lem4444} (i) by summing over $q$ and from Lemma
\ref{lem4444} (ii).
\end{proof}

For non-separated, non-exceptional pairs $(\vec{d}\:, e_2)$ we now replace the
terms $g(\Pi(\vec{d}\:)e_2k^{-1})$ by $g(\Phi_j(\vec{d\:}, e_2))$.

\begin{lemma}\label{lem4646}
Let $\vec{d}\in\mathcal{A}(q)$, $(\vec{d}\:, e_2)\not\in\mathcal{T}$. Then we have
$$\left| g\left( \frac{\Pi(\vec{d}\:)e_2}{k}  \right)-g(\Phi_j(\vec{d}\:, e_2)\right|\ll
q^{-2}\exp(C_4s_1)+q2^{-s_1/2}\log k\:.$$
\end{lemma}
\begin{proof}
This follows from (5.8) and Lemma \ref{lem216b}.
\end{proof}
We now determine the total contribution of the tuplets $\vec{d}$ with appropriate
Diophantine approximation to the sum ${\textstyle\sum}_{1,1}^{(v)}$.

\begin{lemma}\label{lem4747}
For all $\epsilon>0$ we have:
\begin{align*}
\sum_{k^{\delta_1}\leq q< k^{\delta_2}}\sum_{\vec{d\:}\in \mathcal{A}(q)}\left|\sum_{\substack{e_2\::\: k^{2v}\leq e_2< 2k^{2v}\\ k^D\leq \Pi(\vec{d}\:)e_2<2k^D}}g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)  \right| &\ll_\epsilon k^{D-2\delta_1+\epsilon}\exp(C_4s_1)+k^{D-2v+\delta_2+\epsilon }\\
&+k^{D+\epsilon}2^{-s_1/2}+k^{D-1+\epsilon}\exp(2C_4s_1)\\
&+k^{D+\delta_1-\delta_2+\epsilon}
+k^{D+\epsilon}\exp(-(C_5-\epsilon)s_1)\:.
\end{align*}
\end{lemma}
\begin{proof}
For $\vec{d\:}\in\mathcal{A}(q)$ we use the partition $\mathcal{J}=\bigcup_{j=0}^{j_0} I_j$ from Definition \ref{def4545} and the function $\Phi_j$. We have
\begin{align*}
 \tag{5.10}  \sum_{e_2\in I_j} g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)&=\sum_{e_2\in I_j, e_2\not\in \mathcal{T}}\left( g\left( \Phi_j(\vec{d\:} ,e_2)+\left| g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)-g(\Phi_j(\vec{d\:}, e_2))\right| \right) \right)\\
&+\sum_{e_2\in I_j, e_2\in \mathcal{T}}g(\Phi_j(\vec{d\:}, e_2))+O\left(\sum_{e_2\in I_j, e_2\in \mathcal{T}}|g(\Phi_j(\vec{d\:}, e_2))| \right)\\
&+O\left( \sum_{e_2\in I_j, e_2\in \mathcal{T}}  \left|g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)\right|\right)\:.
\end{align*}
By Lemma \ref{lem4646} we have
\[
\sum_{e_2\in I_j, e_2\not\in \mathcal{T}}\left| g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)-
 g( \Phi_j(\vec{d\:} ,e_2))\right| \ll q^{-1}\exp(C_4s_1)\log k\:.  \tag{5.11}
\]
Since the numbers $q\Phi_j(\vec{d\:}, e_2)$ form a complete residue system $\bmod\: q$ and because of the antisymmetry of $g$ we have
\[
\sum_{e_2\in I_j}g(\Phi_j(\vec{d\:}, e_2))=0\:.\tag{5.12}
\]
From (5.11) and (5.12) we obtain for $0\leq j\leq j_0-1$:
\[
\sum_{e_2\in I_j, e_2\not\in \mathcal{T}}  g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right) \ll q^{-1}\exp(C_4s_1)\log k+\sum_{e_2\in I_j, (\vec{d\:}, e_2)\in \mathcal{T}}\left| g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right) \right|\:.  \tag{5.13}
\]
For $j=j_0$ we obtain:
\[
\sum_{e_2\in I_j} g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)\ll q\log k\:. \tag{5.14}
\]
Summing over all $O(k^{2v_0 }q^{-1})$  intervals $I_0, \ldots, I_{j_0-1}$ we
obtain from (5.13) and (5.14):
\begin{align*}
\sum_{e_2\in \mathcal{J}, e_2\not\in \mathcal{T}}  g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)& \ll k^{2v+\epsilon }q^{-2}\exp(C_4s_1)+q\log k\\
&+\sum_{e_2\in \mathcal{J}\::\: (\vec{d\:}, e_2)\in \mathcal{T}} \left| g\left( \frac{\Pi(\vec{d}\:)e_2}{k}\right)\right|
\end{align*}
Summing over all $O(k^{D-2v+\epsilon})$ tuplets $\vec{d\:}$ we obtain the result
by application of Lemma \ref{lem4545}.
\end{proof}

For a given $v$ we now choose the parameters $\delta_1, \delta_2, s_1$ and
the constants $C_4, C_5$ optimally. Writing $s_1=v_1\log k$ all the terms appearing in Lemmas \ref{lem4242} and \ref{lem4747} become powers of $k$, whose exponents are functions of these parameters, linear in each variable and thus monotonic.\\
By equating expressions with opposite monotonicity we obtain:
\begin{lemma}\label{lem4848}
Let $C_4$ be determined by
$$C_4\geq \frac{\sqrt{5}+1}{2}\ \text{and}\ \frac{1}{4}\:C_4-\log C_4-1+\log 2=\frac{1}{2}\:\log 2\:.$$
Let
$$E(v)=v\left(1-\left(1+2\log 2\left(C_4+\frac{\log 2}{2}\right)^{-1}\right)^{-1}\right)\:.$$
Then for all $\epsilon>0$ we have:
$${\textstyle\sum}_{1,1}^{(v)}\ll_\epsilon k^{D-E(v)+\epsilon}\:.$$
\end{lemma}

\vspace{7mm}

\section{The sum ${\textstyle\sum}_{1,2}$}

By (4.4) we have
\[
{\textstyle\sum}_{1,2}=\sum_{\substack{s\geq w, t\geq w\\ k^D\leq st\gamma< 2k^D \\ st<k^{4\delta_0+4v_0}}}\mu(\gamma)\sum(s, t)\:,   \tag{6.1}
\]
where
$$\sum(s, t)=\sum_{k^D\leq u\gamma<2k^D}\mu(\gamma)F(u)g\left(\frac{u\gamma}{k}\right)$$
with
$$F(u):=\sum_{\substack{(s,t)\in\mathbb{N}^2\\ st=u}}\sum_{\substack{d_1d_2=s\\ d_1\leq w}}\mu(d_1)\sum_{\substack{e_1e_2=t\\ e_1\leq w}}\mu(e_1)\:.$$
We observe that
$$|F(u)|\leq d_4(u)\ll_\epsilon u^\epsilon\:,\ \ \text{for all $\epsilon>0$}\:,$$
where $d_4$ denotes the divisor function of order 4.\\
Let $u^*>0$ be a constant to be determined later.\\
Let
\[
\mathcal{R}=\{ (U, V)\::\: U\geq 0,\ V\geq 0,\ D\log k\leq U+V< D\log k+\log 2, U\leq u^*\log k  \}\tag{6.2}
\]
We recursively define the sequence $(R_l)$ of regions that exhaust $\mathcal{R}$.\\
Let $\mathcal{R}_0$ be the union of squares with sides parallel to the coordinates axes, the coordinates of whose vertices are integer multiples of $2^{-v}=1$ and
side lengths $2^{-v}=1$, that are completely contained in $\mathcal{R}$.\\
The recursion $l\rightarrow l+1$: Assume that $R_l$ has been defined. We let
$S_l$ be the union of squares of sides parallel to the coordinate axes of side
lengths $2^{-(l+1)}$, the coordinates of their vertices are integer multiples of $2^{-(l+1)}$, whose interiors are contained in the set $\mathcal{R}\setminus R_l$. We set
$$\mathcal{R}_{l+1}:=\mathcal{R}_l\cup S_l\:.$$
For a square $Q$ of $\mathcal{R}_l$ we define
\[
\text{Exp}(Q):=\{ (u, \gamma)\::\: (\log u, \log\gamma)\in Q \}\:.\tag{6.3}
\]
We define $\Delta_u:=\Delta_u(Q)$, $\Delta_\gamma:=\Delta_\gamma(Q)$ by
\[
\text{Exp}(Q)=:[u_0, u_0(1+\Delta_u))\times[\gamma_0, \gamma_0(1+\Delta_\gamma))\:.\tag{6.4}
\]
We now define
\[
l_0:=\max\{l\in\mathbb{N}\::\: \gamma_0\Delta_\gamma\geq k\ \text{for all squares $Q$ of $\mathcal{R}_l$}  \}\:.\tag{6.5}
\]
We consider the partial sum
\[
\sum(Q):=\sum_{\substack{u_0\leq u<u_0(1+\Delta_u)\\ \gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)}}\mu(\gamma)F(u)g\left( \frac{u\gamma}{k} \right).\tag{6.6}
\]
We have
\begin{align*}
\left| {\textstyle\sum}_{1,2} (Q)\right|&\leq \left(\sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)}\mu(\gamma)^2 \right)^{1/2}\\
&\times\left( \sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)} \left(\sum_{u_0\leq u<u_0(1+\Delta_u)}F(u)g\left(\frac{u\gamma}{k}\right)\right)^2  \right)^\frac{1}{2}
\end{align*}
and
\begin{align*}
&  \sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)} \left(\sum_{u_0\leq u<u_0(1+\Delta_u)}F(u)g\left(\frac{u\gamma}{k}\right)\right)^2   \\
=&\sum_{u_0\leq u_1, u_2 \leq u_0(1+\Delta_u)}F(u_1)F(u_2) {\textstyle\sum}_{g}(Q, u_1, u_2)\:,
\end{align*}
where
$$ {\textstyle\sum}_{g}(Q, u_1, u_2):= \sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)} g\left( \frac{u_1\gamma}{k} \right) g\left( \frac{u_2\gamma}{k} \right)\:.$$
We now fix $s_2\in\mathbb{N}$, $C_6\in\mathbb{R}$, to be determined later. We set
\[
 \mathscr{C}_{1, s_2}:=\{ x\in (0,1)\::\: q_{s_2}(x)\leq \exp(C_6s_2)  \} \tag{6.7}
\]
\[
 \mathscr{C}_{2, s_2}:=(0,1)\setminus  \mathscr{C}_{1, s_2}\tag{6.8}
\]
and define
\[
 {\textstyle\sum}_{g}^{(1)}(Q, u_1, u_2):=\sum_{\substack{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)\\\left\{ \frac{u_i\gamma}{k} \right\}\in  \mathscr{C}_{1, s_2},\ i=1,2 }} g\left( \frac{u_1\gamma}{k} \right) g\left( \frac{u_2\gamma}{k} \right)   \tag{6.9}
\]
\[
 {\textstyle\sum}_{g}^{(2)}(Q, u_1, u_2):=\sum_{\substack{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)\\\left\{ \frac{u_i\gamma}{k} \right\}\in  \mathscr{C}_{2, s_2},\ \text{$i=1$ or $2$} }} g\left( \frac{u_1\gamma}{k} \right) g\left( \frac{u_2\gamma}{k} \right)   \tag{6.10}
\]
For $\left\{ \frac{u_i\gamma}{k} \right\}\in  \mathscr{C}_{2, s_2}$ we use the trivial
estimate
$$g\left( \frac{u_i\gamma}{k} \right) <\log k\:.$$
The congruence
$$u_i\gamma \equiv l\bmod k$$
has $O(\gamma_0\Delta\gamma k^{-1})$ solutions, $\gamma\in [\gamma_0, \gamma_0(1+\Delta_\gamma))\:.$\\
Therefore we obtain:
\[
{\textstyle\sum}_{g_1}^{(2)}(Q) \ll\gamma_0\Delta_\gamma\exp(-(C_7-\epsilon)s_2)(\log k)^2\:, \tag{6.11}
\]
where $C_7=\frac{1}{2}\:C_6-  \log C_6-1+\log 2$.\\
We now apply Definition \ref{def28} to break up ${\textstyle\sum}_{g}^{(1)}(Q)$. We have
$${\textstyle\sum}_{g}^{(1)}(Q)={\textstyle\sum}_{g, 1}(Q)+{\textstyle\sum}_{g,2}(Q)\:,$$
where
$${\textstyle\sum}_{g, 1}(Q):= \sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)} g_{sm}\left( \frac{u_1\gamma}{k}, s_2 \right) g_{sm}\left( \frac{u_2\gamma}{k}, s_2 \right)$$
and
$${\textstyle\sum}_{g, 2}(Q):={\textstyle\sum}_{g, 2}^{(1)}(Q)+{\textstyle\sum}_{g, 2}^{(2)}(Q)+{\textstyle\sum}_{g, 2}^{(3)}(Q)$$
with
$${\textstyle\sum}_{g, 2}^{(1)}(Q)= \sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)} g_{sm}\left( \frac{u_1\gamma}{k}, s_2 \right) g_{sing}\left( \frac{u_2\gamma}{k}, s_2 \right)$$
$${\textstyle\sum}_{g, 2}^{(2)}(Q)= \sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)} g_{sing}\left( \frac{u_1\gamma}{k}, s_2 \right) g_{sm}\left( \frac{u_2\gamma}{k}, s_2 \right)$$
$${\textstyle\sum}_{g, 2}^{(3)}(Q)= \sum_{\gamma_0\leq \gamma<\gamma_0(1+\Delta_\gamma)} g_{sing}\left( \frac{u_1\gamma}{k}, s_2 \right) g_{sing}\left( \frac{u_2\gamma}{k}, s_2 \right)$$
By Lemma \ref{lem211} we have:
$$g_{sing}\left( \frac{u_i\gamma}{k}, s_2 \right)=O(2^{-s_2/2}\log k)\:.$$
We obtain
\[
{\textstyle\sum}_{g, 2}^{(i)}(Q)=O(\gamma_0\Delta\gamma\:2^{-s_2/2}\log k)\ \ (i=1, 2, 3) \tag{6.12}
\]
For the estimate of ${\textstyle\sum}_{g, 2}^{(1)}(Q)$ we replace the terms
$$g_{sm}\left( \frac{u_1\gamma}{k} \right) g_{sm}\left( \frac{u_2\gamma}{k} \right)$$
by their mean-values
\[
M^{(1)}(u_1, u_2, \gamma):=k\int_{\frac{\gamma}{k}-\frac{1}{2k}}^{\frac{\gamma}{k}+\frac{1}{2k}} g_{sm}(u_1x)g_{sm}(u_2x)dx\:. \tag{6.13}
\]
From the definition of $ \mathscr{C}_{1, s_2}$ we see that $\left\{\frac{u_1\gamma}{k}\right\}$ resp. $\left\{\frac{u_2\gamma}{k}\right\}$ are placed in cells $\mathcal{C}_1$ resp. $\mathcal{C}_2$ of depth $s_2$ with
$$q_2(\mathcal{C}_i)\leq \exp(C_6s_2)\:.$$
By Lemma \ref{lem216b} we have
\begin{align*}
  \tag{6.14} &k \int_{\frac{\gamma}{k}-\frac{1}{2k}}^{\frac{\gamma}{k}+\frac{1}{2k}} \left|g_{sm}\left( \frac{u_1\gamma}{k}, s_2 \right) g_{sm}\left( \frac{u_2\gamma}{k}, s_2 \right)
-g_{sm}(u_1x, s_2) g_{sm}(u_2x, s_2)\right|dx \\
&\ \ \ll_\epsilon u_0\exp(C_6s_1) k^{-1}\:.
\end{align*}
We now compare the mean-values $M^{(1)}(u_1, u_2, \gamma)$ and
$$M^{(2)}(u_1, u_2, \gamma):=k \int_{\frac{\gamma}{k}-\frac{1}{2k}}^{\frac{\gamma}{k}+\frac{1}{2k}}  g(u_1x)g(u_2x)dx\:.$$
We have
\begin{align*}
\tag{6.15} &\sum_{\gamma\in[\gamma_0, \gamma_0(1+\Delta_\gamma))}\int_{\frac{\gamma}{k}-\frac{1}{2k}}^{\frac{\gamma}{k}+\frac{1}{2k}}(  g_{sm}(u_1x, s_2)g_{sm}(u_2x, s_2)-g(u_1x)g(u_2x)dx\\
&\ll \sum_{\gamma\in[\gamma_0, \gamma_0(1+\Delta_\gamma))}\int_{\frac{\gamma}{k}-\frac{1}{2k}}^{\frac{\gamma}{k}+\frac{1}{2k}}| g_{sing}(u_1x)|\:|g_{sm}(u_2x)|\\
&\ \ \ \ \ \ \ \ \ \ \ \ \  +|g_{sm}(u_1x)|\:|g_{sing}(u_2x)|+|g_{sing}(u_1x)|\:|g_{sing}(u_2x)|\:dx\\
&\leq \left( \int_{\frac{\gamma_0}{k}}^{\frac{\gamma_0}{k}(1+\Delta_\gamma)}|g_{sing}(u_1x, s_2)|^2dx\right)^{1/2}\left( \int_{\frac{\gamma_0}{k}}^{\frac{\gamma_0}{k}(1+\Delta_\gamma)}|g(u_2x)|^2dx\right)^{1/2}\\
&+\left( \int_{\frac{\gamma_0}{k}}^{\frac{\gamma_0}{k}(1+\Delta_\gamma)}|g(u_1x)|^2dx\right)^{1/2}\left( \int_{\frac{\gamma_0}{k}}^{\frac{\gamma_0}{k}(1+\Delta_\gamma)}|g_{sing}(u_2x, s_2)|^2dx\right)^{1/2}\\
&+\left( \int_{\frac{\gamma_0}{k}}^{\frac{\gamma_0}{k}(1+\Delta_\gamma)}|g_{sing}(u_1x)|^2dx\right)^{1/2}\left( \int_{\frac{\gamma_0}{k}}^{\frac{\gamma_0}{k}(1+\Delta_\gamma)}|g_{sing}(u_2x)|^2dx\right)^{1/2}\\
&\ll_{\epsilon} \gamma_0\Delta_\gamma k^{-1+\epsilon} g^{s_2}
\end{align*}
by Lemma \ref{lem213}.\\
We finally obtain from (6.11), (6.12), (6.14) and (6.15).
\[
{\textstyle\sum}_{g}^{(1)}(Q) \ll_{\epsilon}  k^{\epsilon} u_0\gamma_0\Delta_u\Delta_\gamma\left(\exp\left(-\frac{C_7}{2}s_2\right)+k^{-1/2}\exp\left(\frac{C_6s_2}{2} \right)u_0^{1/2} + g^{s_2/2}\right)\:.  \tag{6.16}
\]

\begin{lemma}\label{lem5151}
Let $z=(u_1, u_2)$. Then
$$\int_0^1 g(u_1x)g(u_2x)dx\ll \frac{z^2}{u_1^2u_2^2}\:.$$
\end{lemma}
\begin{proof}
By Parseval's equation we have:
$$\int_0^1g(u_1x)g(u_2x)dx=\sum_{(n_1, n_2)\::\: n_1u_1=n_2u_2}\frac{d(n_1n_2)^2}{n_1^3 n_2^3}\:.$$
\end{proof}
We conclude the estimate of ${\textstyle\sum}_{1,2}$ by:
\begin{lemma}\label{lem5252}
\begin{align*}
&{\textstyle\sum}_{1,2}\ll_\epsilon k^{D+\epsilon} \Bigg(k^{-1/2} u_0^{1/2}\exp\left(\frac{C_6s_2}{2}\right)+\exp\left(-\frac{C_7}{2}\: s_2\right)\\
&\ \ +2^{-s_2/4}+g^{s_2/2}+u_0^{-1/2} \Bigg) \:.
\end{align*}
\end{lemma}
\begin{proof}
This is obtained by summing the estimates (6.16) and from Lemma \ref{lem5151}
over all squares $Q$ of $\mathcal{R}_{l_0}$ and by estimating the contribution from the pairs $(u, \gamma)\not\in \mathcal{R}_{l_0}$ trivially.\\
\end{proof}
We now again choose the variables $C_6$ and $s_2$ optimally which leads to
the following lemma (with $C_6=C_4$, $C_7=C_5=\frac{\log 2}{2}$):
\begin{lemma}\label{lem5353}
$${\textstyle\sum}_{1,2}\ll_\epsilon k^{D-H(u^*)+\epsilon}\:, $$
where
$$H(u^*):=\frac{1}{2}-\left(\frac{1}{2}+\frac{C_4}{\log 2}\right) u^*\:.$$
\end{lemma}

\vspace{7mm}

\section{Conclusion of the proof}

\begin{lemma}\label{lem6161}
$${\textstyle\sum}_{2}\ll_\epsilon k^{D-1+4\delta_0+\epsilon}  $$
and
$${\textstyle\sum}_{3}\ll_\epsilon k^{D-1+4\delta_0+\epsilon}  $$
\end{lemma}
\begin{proof}
This follows from the estimate
$$g\left(\frac{l}{k}\right)\ll \log k\:.$$
\end{proof}
We now set $u^*:=4v_0+4\delta_0$ and choose $\delta_0$ arbitrarily small.\\
We then determine $v_0$ by the equation
$$E(v_0)=H(u^*)\:.$$
Our Theorem then follows from Lemma \ref{lem4848}, Lemma \ref{lem5353},
and Lemma \ref{lem6161}.

\vspace{10mm}