text:
\begin{document}
\thispagestyle{empty}
\date{}
\maketitle

\vskip .25 in
\textbf{\textit{Abstract}:} Let \(p \geq 2\) be a large prime, and let $N \gg (\log p)^{1+\varepsilon} $. This note proves the existence of primitive roots in the short interval $[M,M+N]$, where $M \geq 2$ is a fixed number, and $ \varepsilon>0$ is a small number. In particular, the least primitive root $g(p)= O\left (  (\log p)^{1+\varepsilon} \right )$, and the least prime primitive root $g^*(p)= O\left (  ( \log p)^{1+\varepsilon} \right )$ unconditionally.  \let\thefootnote\relax\footnote{\today \date{} \\
\textit{Mathematics Subject Classifications}: Primary 11A07, Secondary 11N37. \\
\textit{Keywords}: Least primitive root; Least prime primitive root; Primitive root in short interval.}

\vskip .25 in
\tableofcontents

\section{Introduction}
Given a large prime $p \geq 2$, and a number $N \leq p$. The standard analytic methods demonstrate the existence of primitive roots in any short interval
\begin{equation} \label{eq175.03}
\left [M, M+N \right ]
\end{equation}
for any number $N \gg p^{1/2+\varepsilon} $, where $M \geq 2$ is a fixed number, and $ \varepsilon>0$ is a small number, see \cite{ES57}, \cite{DH37}, \cite{CL53}, \cite{PS90}. More elaborate exponential sums methods can reduce the size of the interval to $N \gg p^{1/4+\varepsilon}$, see \cite{BD67}. Further, the explicit upper bound claims that the least primitive root $g(p) \geq 2$ satisfies the inequality
\begin{equation} \label{eq175.13}
g(p) <\sqrt{p}-2
\end{equation}
for all primes $p >409$, see \cite{CT15}, and \cite{MT15}. Assuming the GRH, it was proved that $g(p) =O\left ( \log ^6 p\right )$, and the average value is $\overline{g(p)} =O\left ( (\log \log p)^2 \right )$, see \cite{SV92} and \cite{BE93} respectively. \\

Almost all these results are based on the standard indicator function in Lemma \ref{lem333.2}. This note introduces a new technique based on the indicator function in Lemma \ref{lem333.3} to improve the results for primitive roots in short intervals.

\begin{thm} \label{thm1.1} Given a small number $ \varepsilon>0$, and a sufficiently large prime \(p \geq 2\), let $N \gg (\log p)^{1+\varepsilon}$. Then, the short interval
\begin{equation} \label{el03}
\left [ M, M+  N\right ]
\end{equation}
contains a primitive root for any fixed $M \geq 2$. In particular, the least primitive root $g(p) =O\left (  (\log p)^{1+\varepsilon} \right )$ unconditionally.
\end{thm}

As the probability of a primitive root modulo $p$ is $O(1/\log \log p)$, this result is nearly optimal, see Section \ref{s222} for a discussion.\\

The existence of prime primitive roots in short interval $[M,M+N]$ requires information about primes in short intervals such that $N < p^{1/2}$, and $M \geq 2$ is any fixed number, which is not available in the literature. But, for the long interval $[2, x]$, it is feasible. Recently, it was proved that the least prime primitive root $ g^*(p)= O\left (  p^{\varepsilon} \right )$, unconditionally, see \cite{CN17}. Moreover, assuming standard conjectures, the least prime primitive root is expected to be $g^{*}(p) =O\left ( (\log p) (\log \log p)^2 \right )$, see \cite{BE97}. A very close upper bound is provided here.

\begin{thm} \label{thm1.2} If \(p \geq 2\) is a sufficiently large prime, then, the least prime primitive root satisfies
\begin{equation} \label{el05}
g^{*}(p) =O\left (  (\log p)^{1+\varepsilon} \right )
\end{equation}
for any small number $ \varepsilon>0$, unconditionally.
\end{thm}

\begin{thm} \label{thm1.3} Let \(p \geq 2\) be a sufficiently large prime, and let $N \gg p^{.525}$. Then, the short interval
\begin{equation} \label{el07}
\left [ M, M+  N\right ]
\end{equation}
contains a prime primitive root for any fixed $M \geq 2$ unconditionally.
\end{thm}

The fundamental background materials are discussed in the earlier sections. Section \ref{s887} presents a proof of Theorem \ref{thm1.1}, the penultimate section presents a proofs of Theorem \ref{thm1.2}, and the last section presents a proof of Theorem \ref{thm1.3}. \\

\section{Primitive Roots Test} \label{969}
For a prime $p \geq 2$, the multiplicative group of the finite fields $\mathbb{F}_p$ is a cyclic group for all primes.

\begin{dfn} { \normalfont The order $\min \{k \in \mathbb{N}: u^k \equiv 1 \bmod p \}$ of an element $u \in \mathbb{F}_p$ is denoted by $\ord_p(u)$. An element is a \textit{primitive root} if and only if $\ord_p(u)=p-1$. }
\end{dfn}
The Euler totient function counts the number of relatively prime integers \(\varphi (n)=\#\{ k:\gcd (k,n)=1 \}\). This counting function is compactly expressed by the analytic formula \(\varphi (n)=n\prod_{p \mid n}(1-1/p),n\in \mathbb{N} .\)
\begin{lem} {\normalfont (Fermat-Euler)} \label{lem2.1}If \(a\in \mathbb{Z}\) is an integer such that \(\gcd (a,n)=1,\) then \(a^{\varphi (n)}\equiv
	1 \bmod n\).
\end{lem}
\begin{lem} \label{lem969.05}  {\normalfont (Primitive root test)} An integer $u \in \Z$ is a primitive root modulo an integer $n \in \N$ if and only if
\begin{equation*}\label{eq969.52}
u^{\varphi (n)/p} -1\not \equiv 0 \mod  n
\end{equation*}
for all prime divisors $p \mid \varphi (n)$.
\end{lem}
The primitive root test is a special case of the Lucas primality test, introduced in \cite[p.\ 302]{ LE78}. A more recent version appears in \cite[Theorem 4.1.1]{CP05}, and similar sources.

\begin{lem} \label{lem969.21}  {\normalfont (Complexity of primitive root test)} Given a prime $p \geq 2$, and the squarefree part $p_1 p_2 \cdots p_v \mid p-1$, a primitive root modulo $p$ can be determined in deterministic polynomial time $O(\log ^c p)$, some constant $c >1$.
\end{lem}
\begin{proof} The mechanics of the deterministic polynomial time algorithm are specified in \cite[Chapter 11]{SV08}. By Theorem \ref{thm1.2}, the algorithm is repeated at most $O\left (  (\log p)^{1+\varepsilon} \right )$ times for each $u=O\left (  (\log p)^{1+\varepsilon} \right )$. These prove the claim.
\end{proof}

\section{Representations of the Characteristic Functions} \label{s333}
The characteristic function \(\Psi :G\longrightarrow \{ 0, 1 \}\) of primitive elements is one of the standard analytic tools employed to investigate the various properties of primitive roots in cyclic groups \(G\). Many equivalent representations of the characteristic function $\Psi $ of primitive elements are possible. Several of these representations are studied in this section.

\subsection{Divisors Dependent Characteristic Function}
A representation of the characteristic function dependent on the orders of the cyclic groups is given below. This representation is sensitive to the primes decompositions $q=p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t}$, with $p_i$ prime and $e_i\geq1$, of the orders of the cyclic groups $q=\# G$. \\

\begin{lem} \label{lem333.2}
Let \(G\) be a finite cyclic group of order \(p-1=\# G\), and let \(0\neq u\in G\) be an invertible element of the group. Then
\begin{equation} \label{eq333.02}
\Psi (u)=\frac{\varphi (p-1)}{p-1}\sum _{d \mid p-1} \frac{\mu (d)}{\varphi (d)}\sum _{\ord(\chi ) = d} \chi (u)=
\left \{\begin{array}{ll}
1 & \text{ if } \ord_p (u)=p-1,  \\
0 & \text{ if } \ord_p (u)\neq p-1. \\
\end{array} \right .
\end{equation}
\end{lem}

\begin{proof} Assume that $u=\tau^{qm}$ is a $q$th power residue modulo $p$, where $q\mid p-1$ and $\gcd(m,p-1)=1$. Then, the inner sum
\begin{equation}
\sum _{ \ord(\chi) = q} \chi (u)= \sum _{ \ord(\chi) = q} \chi (\tau^{qm})=\sum _{ \ord(\chi) = q} \chi (\tau^{m})^q=\varphi(q)=q-1,
\end{equation}
 where $\chi(v)^q=1$. Replacing this information into the product
\begin{eqnarray}
\frac{\phi(p-1)}{p-1} \sum_{d \mid p-1}\frac{\mu(d)}{\varphi(d)} \sum_{\ord(\chi)=d}\chi(u)
&=&\frac{\phi(p-1)}{p-1} \prod_{q \mid p-1} \left (1- \frac{\sum_{\ord(\chi)=q}\chi(u)}{q-1} \right )  \nonumber \\
&=&\frac{\phi(p-1)}{p-1} \prod_{q \mid p-1} \left (1- \frac{q-1}{q-1} \right )=0 .
\end{eqnarray}
shows that both sides of the equation vanish if the element $u \in G$ has order $\ord_p(u) =q \mid p-1$ and $q < p-1$. Now, assume that $u=\tau^{m}$ is not $q$th power residue modulo $p$ for any $q \mid p-1$, where $\gcd(m,p-1)=1$. Then, the inner sum
\begin{equation}
\sum _{ \ord(\psi) = q} \chi (u)= \sum _{ \ord(\psi) = q} \chi (\tau^{m})=-1.
\end{equation}
Replacing this information into the product
\begin{eqnarray}
\frac{\phi(p-1)}{p-1} \sum_{d \mid p-1}\frac{\mu(d)}{\varphi(d)} \sum_{\ord(\chi)=d}\chi(u)
&=&\frac{\phi(p-1)}{p-1} \prod_{q \mid p-1} \left (1- \frac{\sum_{\ord(\chi)=q}\chi(u)}{q-1} \right )  \nonumber \\
&=&\frac{\phi(p-1)}{p-1} \prod_{q \mid p-1} \left (1- \frac{-1}{q-1} \right )=1 .
\end{eqnarray}
These verify that both sides of the equation vanishes if and only if the element $u \in G$ has order $\ord_p(u) =q \mid p-1$ and $q < p-1$.
\end{proof}

The precise source of formula \eqref{eq333.02} is not clear. The authors in \cite{DH37}, and \cite{WR01} attributed this formula to Vinogradov, and other authors have attributed it to Landau. The proof and other details on the characteristic function are given in \cite[p. 863]{ES57}, \cite[p.\ 258]{LN97}, \cite[p.\ 18]{MP07}. The characteristic function for multiple primitive roots is used in \cite[p.\ 146]{CZ98} to study consecutive primitive roots. In \cite{DS12} it is used to study the gap between primitive roots with respect to the Hamming metric. And in \cite{WR01} it is used to prove the existence of primitive roots in certain small subsets \(A\subset \mathbb{F}_p\). In \cite{DH37} it is used to prove that some finite fields do not have primitive roots of the form $a\tau+b$, with $\tau$ primitive and $a,b \in \mathbb{F}_p$ constants. In addition, the Artin primitive root conjecture for polynomials over finite fields was proved in \cite{PS95} using this formula.

\subsection{Divisors Free Characteristic Function}
It often difficult to derive any meaningful result using the usual divisors dependent characteristic function of primitive elements given in Lemma \ref{lem333.2}. This difficulty is due to the large number of terms that can be generated by the divisors, for example, \(d\mid p-1\), involved in the calculations, see \cite{ES57}, \cite{DS12} for typical applications and \cite[p.\ 19]{MP04} for a discussion. \\

A new \textit{divisors-free} representation of the characteristic function of primitive element is developed here. This representation can overcomes some of the limitations of its counterpart in certain applications. The \textit{divisors dependent representation} of the characteristic function of primitive roots, Lemma \ref{lem333.2}, detects the order \(\ord_p (u)\) of the element \(u\in \mathbb{F}_p\) by means of the divisors of the totient \(p-1\). In contrast, the \textit{divisors-free representation} of the characteristic function, Lemma \ref{lem333.3}, detects the order \(\text{ord}_p(u) \geq 1\) of the element \(u\in \mathbb{F}_p\) by means of the solutions of the equation \(\tau ^n-u=0\) in \(\mathbb{F}_p\), where \(u,\tau\) are constants, and \(1\leq n<p-1, \gcd (n,p-1)=1,\) is a variable.

\begin{lem} \label{lem333.3}
Let \(p\geq 2\) be a prime, and let \(\tau\) be a primitive root mod \(p\). If \(u\in\mathbb{F}_p\) is a nonzero element, and \(\psi \neq 1\) is a nonprincipal additive character of order \(\ord \psi =p\), then
\begin{equation}
\Psi (u)=\sum _{\gcd (n,p-1)=1} \frac{1}{p}\sum _{0\leq m\leq p-1} \psi \left ((\tau ^n-u)m\right)=\left \{
\begin{array}{ll}
1 & \text{ if } \ord_p(u)=p-1,  \\
0 & \text{ if } \ord_p(u)\neq p-1. \\
\end{array} \right .
\end{equation}
\end{lem}

\begin{proof} As the index \(n\geq 1\) ranges over the integers relatively prime to \(p-1\), the element \(\tau ^n\in \mathbb{F}_p\) ranges over the primitive roots \(\text{mod } p\). Ergo, the equation
\begin{equation}\label{eq33.30}
\tau ^n- u=0
\end{equation}
has a solution if and only if the fixed element \(u\in \mathbb{F}_p\) is a primitive root. Next, replace \(\psi (z)=e^{i 2\pi  z/p }\) to obtain
\begin{equation}
\Psi(u)=\sum_{\gcd (n,p-1)=1} \frac{1}{p}\sum_{0\leq m\leq p-1} e^{i 2\pi  (\tau ^n-u)m/p }=\left \{
\begin{array}{ll}
1 & \text{ if } \ord_p (u)=p-1,  \\
0 & \text{ if } \ord_p (u)\neq p-1. \\
\end{array} \right.
\end{equation}
This follows from the geometric series identity $\sum_{0\leq m\leq N-1} w^{ m }=(w^N-1)/(w-1)$ with $w \ne 1$, applied to the inner sum.
\end{proof}

\section{Primes Numbers Results} \label{s533}
Some prime numbers results focusing on the local minima of the ratio
\begin{equation}\label{eq533.30}
\frac{\varphi(n)}{n}=\prod_{p \mid n}\left( 1- \frac{1}{p} \right)> \frac{1}{e^{\gamma} \log \log n+5/(2 \log \log n)}
\end{equation}
are recorded in this section. The conditional results are studied in \cite{NJ12}, and the
unconditional results are proved by various authors as \cite[Theorem 7 and Theorem 15]{RS62}, and \cite[Theorem 2.9]{MV07}.

\begin{lem} \label{lem533.01}
Let \(n\geq 1\) be a large integer, and let $\omega(n)$ be the number of prime divisors $p \mid n$. Then
\begin{enumerate}[font=\normalfont, label=(\roman*)]
\item $\displaystyle\omega(n) \ll \log \log n,$ \tabto{8cm}the average number of prime divisors.

 \item $\displaystyle \omega(n) \ll \log n/ \log \log n,$\tabto{8cm}the maximal number of prime divisors.
 \end{enumerate}

\end{lem}
\begin{proof} These are standard results in analytic number theory, see \cite[Theorem 2.6]{MV07}.
\end{proof}

\begin{lem} \label{lem533.21}
Let \(x\geq 2\) be a large number, then
\begin{enumerate}[font=\normalfont, label=(\roman*)]
\item $\displaystyle \prod_{p \leq x}\left( 1- \frac{1}{p} \right)
=\frac{1}{e^{\gamma} \log x}+ O\left (e^{-c_0 \sqrt{ \log x}}\right ),$ \tabto{8cm} unconditionally.

 \item $\displaystyle \prod_{p \leq x}\left( 1- \frac{1}{p} \right)
=\frac{1}{e^{\gamma} \log x}+\Omega_{\pm} \left (\frac{\log \log \log x}{x^{1/2}} \right ),$\tabto{8cm}unconditional oscillation.

 \item $\displaystyle \prod_{p \leq x}\left( 1- \frac{1}{p} \right)
=\frac{1}{e^{\gamma} \log x}+ O\left (\frac{\log x}{ x^{1/2}} \right ),$\tabto{8cm}conditional on the RH.
 \end{enumerate}
The symbol $\gamma$ is the Euler constant, and $c_0>0$ is an absolute constant.
\end{lem}
The explicit estimates are given in \cite[Theorem 7]{RS62}, and the results for products over arithmetic progression are proved in \cite{LZ07}, et alii. The nonquantitative unconditional oscillations of the error of the product of primes is implied by the work of Phragmen,
refer to equation (\ref{eq533.8}), and \cite[p.\ 182]{NW00}. Since then, various authors have developed quantitative versions, see \cite{RS62}, \cite{DP09}, et alii.

\section{Basic Statistic For Primitive Roots} \label{s222}
\subsection{Probability Of Primitive Roots}
The probability of primitive roots in a finite field $\F_p$ has the closed form $\varphi(p-1)/(p-1) \leq 1/2$. The maximal probability $\varphi(p-1)/(p-1) = 1/2$ occurs on the subset of Fermat primes
\begin{equation}
\mathcal{F}=\{p=2^{2^n}+1: n \geq 0\}=\{3,5,17,257, 65537, \ldots \}.
\end{equation}
This is followed by the subset of Germain primes
\begin{equation}
\mathcal{S}=\{p=2^aq+1: q \geq  2 \text{ is prime, and } a \geq 1 \}=\{5,7,11, 13, 23, 29, \ldots \},
\end{equation}
which has $\varphi(p-1)/p =(1/2)(1-1/q)$, et cetera. Some basic questions such as the sizes of these subsets of primes are open problems. In contrast, the minimal probabilities occur on the various subsets of primes with highly composite totients $p-1$. For example, the subset
\begin{equation}
\mathcal{R}=\{p \geq 2: p-1=2^{v_2}\cdot 3^{v_3}\cdot 5^{v_5}\cdots q^{v_q}, \text{ and } v_i \geq 1\}=\{3,7,31, 191, \ldots \}.
\end{equation}
In these cases, the probability function can have a complicated expression such as
\begin{equation} \label{eq222.8}
\frac{\varphi(p-1)}{p-1}\asymp\prod_{q \ll \log p}\left( 1- \frac{1}{q} \right)
=\frac{1}{e^{\gamma} \log \log p}+\Omega_{\pm} \left (\frac{\log \log \log \log p}{(\log p)^{1/2}} \right ).
\end{equation}
This is derived from the standard results in Lemma \ref{lem533.01}, and in Lemma \ref{lem533.21}. Further, the average probability over all the primes $p \leq x$ is a well known constant
\begin{equation} \label{eq222.21}
a_0=\frac{1}{\pi(x)} \sum_{p \leq x}\frac{\varphi(p-1)}{p-1}=\prod_{p >2}\left( 1- \frac{1}{p(p-1)} \right) +o(1)= 0.3739558136 \ldots.
\end{equation}
The analysis of the average appears in \cite{GM68}, \cite{SP69}, and an early numerical calculations is given in \cite{WJ61}. The distribution of primitive root for highly composite totients $p-1$ is approximately a Poisson distribution with parameter $\lambda>0$. For $k \geq 0$, and $1 \leq t \leq \delta \log \log p$, with $\delta >0$, the probability function has the asymptotic formula
\begin{equation} \label{eq222.33}
P_k(t) \sim e^{-\lambda} \frac{\lambda^k}{k!},
\end{equation}
confer \cite[Theorem 2]{CZ98} for the finer details.

\subsection{Average Gap Between Primitive Roots}
Let $p\geq2 $ be a prime, and let $g_1, g_2, \ldots, g_t$ be the sequence of primitive roots in increasing order, with $t=\varphi(p-1)$. Given a fixed prime $p\geq 2$, the average gap between a pair of consecutive primitive roots is defined by
\begin{equation} \label{eq222.33}
d_n=g_{n+1}-g_n=\frac{p-1}{\varphi(p-1)} \ll \log \log p.
\end{equation}

 \begin{lem} \label{lem222.41} Let \(x\geq 1\) be a large number, then the average gap between consecutive primitive roots over all the primes $p \leq x$ is bounded by a constant. In particular, for any constant $c>2$,
\begin{equation} \label{eq222.33}
\overline{d_n}=\prod_{p \geq 2}\left( 1- \frac{1}{(p-1)^2} \right) \li(x)+  O\left (\frac{x}{\log^{c-1} x}\right ).
\end{equation}
\end{lem}

\begin{proof} The identity $n/\varphi(n)=\sum_{d\mid n}\mu^2(d)/\varphi(d)$ is used here to compute the average over all the primes $p \leq x$:
\begin{eqnarray} \label{eq222.74}
\sum_{p \leq x}\frac{p-1}{\varphi(p-1)} &=&\sum_{p \leq x} \sum_{d\mid p-1}\frac{\mu^2(d)}{\varphi(d)} \\
&=& \sum_{d\leq x}\frac{\mu^2(d)}{\varphi(d)}\sum_{\substack{p \leq x\\ p \equiv 1 \bmod d}}  1\nonumber.
\end{eqnarray}
To apply the prime number theorem to the inner sum, use a dyadic partition

\begin{equation} \label{eq222.76}
 \sum_{d\leq x}\frac{\mu^2(d)}{\varphi(d)}\sum_{\substack{p \leq x\\ p \equiv 1 \bmod d}}  1= \sum_{d\leq \log^c x}\frac{\mu^2(d)}{\varphi(d)}\sum_{\substack{p \leq x\\ p \equiv 1 \bmod d}}  1+ \sum_{d\geq \log^cx}\frac{\mu^2(d)}{\varphi(d)}\sum_{\substack{p \leq x\\ p \equiv 1 \bmod d}}  1,
\end{equation}
where $c>0$ is an arbitrary constant. The first sum has the asymptotic expression
\begin{eqnarray} \label{eq222.78}
 \sum_{d\leq \log^C x}\frac{\mu^2(d)}{\varphi(d)}\sum_{\substack{p \leq x\\ p \equiv 1 \bmod d}}  1
&=& \sum_{d\leq \log^C x}\frac{\mu^2(d)}{\varphi(d)}        \left(  \frac{\li(x)}{\varphi(d)}+ O\left (\frac{x}{\log^b x}\right )   \right )  \\
&=&\li(x) \sum_{d\geq 2}\frac{\mu^2(d)}{\varphi(d)^2}+ O\left (\frac{x}{\log^b x}\right )  \nonumber,
\end{eqnarray}
where $b>c+1$. The second sum has the asymptotic expression
\begin{equation} \label{eq222.80}
  \sum_{d\geq \log^Cx}\frac{\mu^2(d)}{\varphi(d)}\sum_{\substack{p \leq x\\ p \equiv 1 \bmod d}}  1\ll \frac{x}{\log^c x} \sum_{d\geq \log^cx}\frac{1}{\varphi(d)}= O\left (\frac{x}{\log^{c-1} x}\right ) ,
\end{equation}
Combining the last two expressions (\ref{eq222.78}) and (\ref{eq222.80}) completes the proof.

\end{proof}
The average gap between consecutive primitive roots is precise the value of the constant
\begin{equation} \label{eq222.82}
\prod_{p \geq 2}\left( 1- \frac{1}{(p-1)^2} \right) =2.82638409425598556075406 \ldots .
\end{equation}

\begin{lem} \label{lem222.47} Let \(p\geq 1\) be a large prime, and let $t\leq\varphi(p-1)$ be a large number. Then, the  $g_1, g_2, \ldots, g_t$ be the sequence of primitive roots in increasing order are uniformly distributed over the interval $[2, p-2]$.
\end{lem}
\begin{proof} Apply Theorem \ref{thm3.4} to the Bohl-Weil criterion
\begin{equation}
\frac{1}{p} \sum_{1\leq n \leq t} e^{i2\pi  g_n/p} =o(1) ,
\end{equation}
where $p^{1/2}< t\leq \varphi(p-1)$.
\end{proof}

\section{Estimates Of Exponential Sums} \label{s4}
This section provides simple estimates for the exponential sums of interest in this analysis. There are two objectives: To  determine an upper bound, proved in Theorem \ref{thm3.4}, and to show that
\begin{equation} \label{eq3.201}
\sum_{\gcd(n,p-1)=1} e^{i2\pi b \tau^n/p} =\sum_{\gcd(n,p-1)=1} e^{i2\pi \tau^n/p}+E(p),
\end{equation}
where $E(p)$ is an error term, this is proved in Lemma \ref{lem333.22}. The proofs of these results are entirely based on established results and elementary techniques.

\subsection{Incomplete And Complete Exponential Sums}
Let $f: \C \longrightarrow \C$ be a function, and let $q \in \N$ be a large integer. The finite Fourier transform
\begin{equation} \label{eq3.370}
\hat{f}(t)=\frac{1}{q} \sum_{0 \leq s\leq q-1} e^{i \pi st/q}
\end{equation}
and its inverse are used here to derive a summation kernel function, which is almost identical to the Dirichlet kernel.

\begin{dfn} \label{dfn3.23} {\normalfont Let $ p$ and $ q $ be primes, and let $\omega=e^{i 2 \pi/q}$, and $\zeta=e^{i 2 \pi/p}$ be roots of unity. The \textit{finite summation kernel} is defined by the finite Fourier transform identity
\begin{equation} \label{eq3.373}
\mathcal{K}(f(n))=\frac{1}{q} \sum_{0 \leq t\leq q-1,}  \sum_{0 \leq s\leq p-1} \omega^{t(n-s)}f(s)=f(n).\end{equation}
}
\end{dfn}
This simple identity is very effective in computing upper bounds of some exponential sums
\begin{equation}
 \sum_{ n \leq x}  f(n)= \sum_{ n \leq x}  \mathcal{K}(f(n)),
\end{equation}
where $x  \leq p < q$. Two applications are illustrated here.

\begin{thm}  \label{thm3.2} {\normalfont (\cite{SR73},  \cite{ML72}) }  Let \(p\geq 2\) be a large prime, and let \(\tau \in \mathbb{F}_p\) be an element of large multiplicative order $\ord_p(\tau) \mid p-1$. Then, for any $b \in [1, p-1]$,  and $x\leq p-1$,
\begin{equation}
 \sum_{ n \leq x}  e^{i2\pi b \tau^{n}/p} \ll p^{1/2}  \log p.
\end{equation}

\end{thm}

\begin{proof} Let $q=p+o(p)>p$ be a large prime, and let $f(n)=e^{i 2 \pi b\tau^{n} /p}$, where $\tau$ is a primitive root modulo $p$. Applying the finite summation kernel in Definition \ref{dfn3.23}, yields
\begin{equation} \label{eq3.372}
\sum_{ n \leq x}  e^{i2\pi b \tau^{n}/p}= \sum_{ n \leq x}\frac{1}{q} \sum_{0 \leq t\leq q-1,}  \sum_{1 \leq s\leq p-1} \omega^{t(n-s)}e^{i2\pi b \tau^{s}/p} .
\end{equation}
The term $t=0$ contributes $-x/q$, and rearranging it yield
\begin{eqnarray} \label{eq3.374}
\sum_{ n \leq x}  e^{i2\pi b \tau^{n}/p}
&=&\frac{1}{q} \sum_{ n \leq x,} \sum_{1 \leq t\leq q-1,}  \sum_{1 \leq s\leq p-1} \omega^{t(n-s)}e^{i2\pi b \tau^{s}/p}-\frac{x}{q} \\
&=&\frac{1}{q}  \sum_{1 \leq t\leq q-1}  \left (\sum_{1 \leq s\leq p-1} \omega^{-ts}e^{i2\pi b \tau^{s}/p} \right ) \left (\sum_{ n \leq x}\omega^{tn} \right )-\frac{x}{q}\nonumber.
\end{eqnarray}
Taking absolute value, and applying Lemma \ref{lem333.20}, and Lemma \ref{lem333.27}, yield
\begin{eqnarray} \label{eq3.376}
\left | \sum_{ n \leq x}  e^{i2\pi b \tau^{n}/p} \right |
&\leq&\frac{1}{q}  \sum_{1 \leq t\leq q-1} \left | \sum_{0 \leq s\leq p-1} \omega^{-ts}e^{i2\pi b \tau^{s}/p} \right | \cdot  \left | \sum_{ n \leq x}\omega^{tn} \right |+ \frac{x}{q}\nonumber \\
&\ll&\frac{1}{q}  \sum_{1 \leq t\leq q-1} \left ( 2q^{1/2} \log q \right ) \cdot  \left ( \frac{2q}{\pi t} \right )+\frac{x}{q}\\
&\ll& p^{1/2} \log^2 p\nonumber .
\end{eqnarray}
The last summation in (\ref{eq3.376}) uses the estimate \begin{equation} \label{eq3.392} \sum_{1 \leq t\leq q-1}\frac{1}{t}\ll \log q\ll \log p
\end{equation}
since $q=p+o(p)>p$, and $x/q\leq 1$.
\end{proof}
This appears to be the best possible upper bound. The above proof generalizes the sum of resolvents method used in \cite{ML72}. Here, it is reformulated as a finite Fourier transform method, which is applicable to a wide range of functions. A similar upper bound for composite moduli $p=m$ is also proved, [op. cit., equation (2.29)].

\begin{thm}  \label{thm3.4}  Let \(p\geq 2\) be a large prime, and let $\tau $ be a primitive root modulo $p$. Then,
\begin{equation}
	 \sum_{\gcd(n,p-1)=1} e^{i2\pi b \tau^n/p} \ll  p^{1-\varepsilon}
\end{equation}
for any $b \in [1, p-1]$, and any arbitrary small number $\varepsilon \in
(0, 1/2)$.
\end{thm}

\begin{proof} Let $q=p+o(p)>p$ be a large prime, and let $f(n)=e^{i 2 \pi b\tau^{n} /p}$, where $\tau$ is a primitive root modulo $p$. Start with the representation
\begin{equation} \label{eq3.392}
\sum_{ \gcd(n,p-1)=1}  e^{\frac{i2\pi b \tau^n}{p}}= \sum_{ \gcd(n,p-1)=1}\frac{1}{q} \sum_{0 \leq t\leq q-1,}  \sum_{1 \leq s\leq p-1} \omega^{t(n-s)}e^{\frac{i2\pi b \tau^s}{p}} ,
\end{equation}
see Definition \ref{dfn3.23}. Use the inclusion exclusion principle to rewrite the exponential sum as
\begin{equation}\label{eq3.346}
\sum_{\gcd(n,p-1)=1} e^{ \frac{i2\pi b \tau^n}{p}}
= \sum_{ n \leq p-1}\frac{1}{q} \sum_{0 \leq t\leq q-1,}  \sum_{1 \leq s\leq p-1} \omega^{t(n-s)}e^{\frac{i2\pi b \tau^s}{p}} \sum_{\substack{d \mid p-1 \\ d \mid n}}\mu(d)   .
\end{equation}
The term $t=0$ contributes $-\varphi(p)/q$, and rearranging it yield
\begin{eqnarray}\label{eq3.348}
&&\sum_{\gcd(n,p-1)=1} e^{ \frac{i2\pi b \tau^n}{p}} \\
&=& \sum_{ n \leq p-1}\frac{1}{q} \sum_{1 \leq t\leq q-1,}  \sum_{1 \leq s\leq p-1} \omega^{t(n-s)}e^{\frac{i2\pi b \tau^s}{p}} \sum_{\substack{d \mid p-1 \\ d \mid n}}\mu(d) -\frac{\varphi(p)}{q} \nonumber \\
&=&\frac{1}{q} \sum_{1 \leq t\leq q-1} \left ( \sum_{1 \leq s\leq p-1} \omega^{-ts}e^{\frac{i2\pi b \tau^s}{p}}\right )\left (\sum_{d \mid p-1} \mu(d) \sum_{\substack{n \leq p-1, \\ d \mid n}}   \omega^{tn} \right ) -\frac{\varphi(p)}{q} \nonumber.
\end{eqnarray}
Taking absolute value, and applying Lemma \ref{lem333.24}, and Lemma \ref{lem333.27}, yield
\begin{eqnarray} \label{eq3.379}
&& \left | \sum_{ \gcd(n, p-1)=1} e^{\frac{i2\pi b \tau^n}{p}} \right | \\
&\leq&\frac{1}{q}  \sum_{1 \leq t\leq q-1} \left | \sum_{1 \leq s\leq p-1} \omega^{-ts}e^{i2\pi b \tau^{s}/p} \right | \cdot  \left |\sum_{d \mid p-1} \mu(d) \sum_{\substack{n \leq p-1, \\ d \mid n}}   \omega^{tn} \right | +\frac{\varphi(p)}{q}\nonumber \\
&\ll&\frac{1}{q}  \sum_{1 \leq t\leq q-1} \left ( 2q^{1/2} \log q \right ) \cdot  \left ( \frac{4q \log \log p}{\pi t} \right )+\frac{\varphi(p)}{q}\nonumber\\
&\ll& p^{1/2} \log^3 p \nonumber.
\end{eqnarray}
The last summation in (\ref{eq3.379}) uses the estimate
\begin{equation} \label{eq3.392} \sum_{1 \leq t\leq q-1}\frac{1}{t}\ll \log q\ll \log p
\end{equation} since $q=p+o(p)>p$, and $\varphi(p)/q \leq 1$. This is restated in the simpler notation $p^{1/2}\log ^3 p  \leq p^{1-\varepsilon}$ for any arbitrary small number $\varepsilon \in (0,1/2)$.
\end{proof}

The upper bound given in Theorem \ref{thm3.4} seems to be optimum. A different proof, which has a weaker upper bound, appears in \cite[Theorem 6]{FS00}, and related results are given in \cite{CC09}, \cite{FS01}, \cite{GZ05}, and \cite[Theorem 1]{GK05}.

\subsection{Equivalent Exponential Sums}
For any fixed $ 0 \ne b \in \mathbb{F}_p$, the map $ \tau^n \longrightarrow b \tau^n$ is one-to-one in $\mathbb{F}_p$. Consequently, the subsets
\begin{equation} \label{eq3.220}
 \{ \tau^n: \gcd(n,p-1)=1 \}\quad \text { and } \quad  \{ b\tau^n: \gcd(n,p-1)=1 \} \subset \mathbb{F}_p
\end{equation} have the same cardinalities. As a direct consequence the exponential sums
\begin{equation} \label{3.330}
\sum_{\gcd(n,p-1)=1} e^{i2\pi b \tau^n/p} \quad \text{ and } \quad \sum_{\gcd(n,p-1)=1} e^{i2\pi \tau^n/p},
\end{equation}
have the same upper bound up to an error term. An asymptotic relation for the exponential sums (\ref{3.330}) is provided in Lemma \ref{lem333.22}. This result expresses the first exponential sum in (\ref{3.330}) as a sum of simpler exponential sum and an error term.

\begin{lem}   \label{lem333.22}  Let \(p\geq 2\) be a large primes. If $\tau $ be a primitive root modulo $p$, then,
\begin{equation} \sum_{\gcd(n,p-1)=1} e^{i2\pi b \tau^n/p} = \sum_{\gcd(n,p-1)=1} e^{i2\pi  \tau^n/p} + O(p^{1/2} \log^3 p),
\end{equation}
for any $ b \in [1, p-1]$.
\end{lem}
\begin{proof} For $b\ne 1$, the exponential sum has the representation
\begin{eqnarray} \label{eq3.320}
&& 	\sum_{\gcd(n,p-1)=1} e^{\frac{i2\pi b \tau^n}{p}} \\
&=&\frac{1}{q} \sum_{1 \leq t\leq q-1} \left ( \sum_{1 \leq s\leq p-1} \omega^{-ts}e^{\frac{i2\pi b \tau^s}{p}}\right )\left (\sum_{d \mid p-1} \mu(d) \sum_{\substack{n \leq p-1, \\ d \mid n}}   \omega^{tn} \right ) -\frac{\varphi(p)}{q}\nonumber,
\end{eqnarray}
confer equation (\ref{eq3.348}) for details. And, for $b=1$,
\begin{eqnarray} \label{eq3.321}
&& 	\sum_{\gcd(n,p-1)=1} e^{\frac{i2\pi  \tau^n}{p}} \\
&=& \frac{1}{q} \sum_{1 \leq t\leq q-1} \left ( \sum_{1 \leq s\leq p-1} \omega^{-ts}e^{\frac{i2\pi  \tau^s}{p}}\right )\left (\sum_{d \mid p-1} \mu(d) \sum_{\substack{n \leq p-1, \\ d \mid n}}   \omega^{tn} \right ) -\frac{\varphi(p)}{q}\nonumber,
\end{eqnarray}
respectively, see (\ref{eq3.348}). Differencing (\ref{eq3.320}) and (\ref{eq3.321}) produces
\begin{eqnarray} \label{eq3.90}
& &	\sum_{\gcd(n,p-1)=1} e^{i2\pi b \tau^n/p} -\sum_{\gcd(n,p-1)=1} e^{i2\pi  \tau^n/p} \\
&=&     \frac{1}{q} \sum_{0 \leq t\leq q-1} \left ( \sum_{1 \leq s\leq p-1} \omega^{-ts}e^{\frac{i2\pi b \tau^s}{p}}-\sum_{1 \leq s\leq p-1} \omega^{-ts}e^{\frac{i2\pi  \tau^s}{p}}\right ) \nonumber \\
&& \times \left (\sum_{d \mid p-1} \mu(d) \sum_{\substack{n \leq p-1, \\ d \mid n}}   \omega^{tn} \right ) \nonumber.
\end{eqnarray}
By  Lemma \ref{lem333.24}, the relatively prime summation kernel is bounded by
\begin{eqnarray} \label{eq3.93}
 \left |\sum_{d \mid p-1} \mu(d) \sum_{\substack{n \leq p-1, \\ d \mid n}}   \omega^{tn} \right |
&=& \left | \sum_{\gcd(n, p-1)=1}\omega^{tn} \right | \nonumber \\
&\leq &  \frac{4 q \log \log p} {\pi t},
\end{eqnarray}
 and by Lemma \ref{lem333.27}, the difference of two Gauss sums is bounded by
\begin{eqnarray} \label{eq3.95}
&&  \left | \sum_{1 \leq s\leq p-1} \omega^{-ts}e^{\frac{i2\pi b \tau^s}{p}}-\sum_{1 \leq s\leq p-1} \omega^{-ts}e^{\frac{i2\pi  \tau^s}{p}}\right  |  \nonumber \\
&=& \left |  \sum_{1 \leq s\leq p-1} \chi(s) \psi_b(s) - \sum_{1 \leq s\leq p-1} \chi(s) \psi_1(s) \right | \nonumber \\
&\leq & 4 p^{1/2} \log p,
\end{eqnarray}
where  $\chi(s)=e^{i \pi s t/p}$, and $ \psi_b(s)=e^{i2\pi b \tau^s/p}$. Taking absolute value in (\ref{eq3.90}) and replacing (\ref{eq3.93}), and  (\ref{eq3.95}), return
\begin{eqnarray} \label{388}
&& \left|  	\sum_{\gcd(n,p-1)=1} e^{i2\pi b \tau^n/p} -\sum_{\gcd(n,p-1)=1} e^{i2\pi  \tau^n/p} \right|  \nonumber\\
& \leq &      \frac{1}{q} \sum_{0 \leq t\leq q-1} \left ( 4q^{1/2} \log q \right ) \cdot \left ( \frac{4 q \log \log p} {t} \right ) \\
&\leq & 16q^{1/2} (\log q)(\log q)( \log \log p )\nonumber\\
&\leq & 16p^{1/2} \log^3 p \nonumber,
\end{eqnarray}
where $q=p+o(p)$.
\end{proof}
The same proof works for many other subsets of elements $\mathcal{A} \subset \mathbb{F}_p$. For example,
\begin{equation}
\sum_{n \in \mathcal{A}} e^{i2\pi b \tau^n/p} = \sum_{n \in \mathcal{A}} e^{i2\pi  \tau^n/p} + O(p^{1/2} \log^c p),
\end{equation}
for some constant $c>0$.

\subsection{Finite Summation Kernels And Gaussian Sums}
\begin{lem}   \label{lem333.20}  Let \(p\geq 2\) and $q=p+o(p)>p$ be large primes. Let $\omega=e^{i2 \pi/q} $ be a $q$th root of unity, and let $t \in [1, p-1]$. Then,
\begin{enumerate}[font=\normalfont, label=(\roman*)]
\item $\displaystyle\sum_{n \leq p-1} \omega^{tn} = \frac{\omega^{t}-\omega^{tp}}{1-\omega^{t}},$

 \item $\displaystyle \left |  \sum_{n \leq p-1} \omega^{tn}  \right |\leq \frac{2q }{\pi t}.$
 \end{enumerate}

\end{lem}

\begin{proof} (i) Use the geometric series to compute this simple exponential sum as
	\begin{eqnarray} \label{eq3.340}
	 \sum_{n \leq p-1} \omega^{tn}
	&=& \frac{\omega^{t}-\omega^{tp}}{1-\omega^{t}} \nonumber.
	\end{eqnarray}
(ii) Observe that the parameters $q=p+o(p)>p$ is prime, $\omega=e^{i2 \pi/q}$, the integers $t \in [1, p-1]$, and $d \leq p-1<q-1$. This data implies that $\pi t/q\ne k \pi $ with $k \in \mathbb{Z}$, so the sine function $\sin(\pi t/q)\ne 0$ is well defined. Using standard manipulations, and $z/2 \leq \sin(z) <z$ for $0<|z|<\pi/2$, the last expression becomes
	\begin{equation}
	\left |\frac{\omega^{t}-\omega^{tp}}{1-\omega^{t}} \right |\leq 	\left | \frac{2}{\sin( \pi t/ q)} \right |
	\leq \frac{2q}{\pi t}.
	\end{equation}

\end{proof}

\begin{lem}   \label{lem333.24}  Let \(p\geq 2\) and $q=p+o(p)>p$ be large primes, and let $\omega=e^{i2 \pi/q} $ be a $q$th root of unity. Then,
\begin{enumerate}[font=\normalfont, label=(\roman*)]
\item $\displaystyle\sum_{\gcd(n,p-1)=1} \omega^{tn} = \sum_{d \mid p-1} \mu(d) \frac{\omega^{dt}-\omega^{dt((p-1)/d+1)}}{1-\omega^{dt}},$

 \item $\displaystyle \left | \sum_{\gcd(n,p-1)=1} \omega^{tn}  \right |\leq \frac{4q \log \log p}{\pi t},$
 \end{enumerate}
where $\mu(k)$ is the Mobius function, for any fixed pair $d \mid p-1$ and $t \in [1, p-1]$.
\end{lem}

\begin{proof} (i) Use the inclusion exclusion principle to rewrite the exponential sum as
	\begin{eqnarray} \label{eq360}
	\sum_{\gcd(n,p-1)=1} \omega^{tn}&=& \sum_{n \leq p-1} \omega^{tn}  \sum_{\substack{d \mid p-1 \\ d \mid n}}\mu(d)  \nonumber \\
	&=& \sum_{d \mid p-1} \mu(d) \sum_{\substack{n \leq p-1 \\ d \mid n}} \omega^{tn}\nonumber \\
	& =&\sum_{d\mid p-1} \mu(d) \sum_{m \leq (p-1)/ d} \omega^{dtm} \\
	&=& \sum_{d \mid p-1} \mu(d) \frac{\omega^{dt}-\omega^{dt((p-1)/d+1)}}{1-\omega^{dt}} \nonumber.
	\end{eqnarray}
(ii) Observe that the parameters $q=p+o(p)>p$ is prime, $\omega=e^{i2 \pi/q}$, the integers $t \in [1, p-1]$, and $d \leq p-1<q-1$. This data implies that $\pi dt/q\ne k \pi $ with $k \in \mathbb{Z}$, so the sine function $\sin(\pi dt/q)\ne 0$ is well defined. Using standard manipulations, and $z/2 \leq \sin(z) <z$ for $0<|z|<\pi/2$, the last expression becomes
	\begin{equation}
	\left |\frac{\omega^{dt}-\omega^{dtp}}{1-\omega^{dt}} \right |\leq 	\left | \frac{2}{\sin( \pi dt/ q)} \right |
	\leq \frac{2q}{\pi dt}
	\end{equation}
	for $1 \leq d \leq p-1$. Finally, the upper bound is
	\begin{eqnarray}
	\left|   \sum_{d \mid p-1} \mu(d) \frac{\omega^{dt}-\omega^{dt((p-1)/d+1)}}{1-\omega^{dt}} \right|
	&\leq&\frac{2q}{\pi t} \sum_{d \mid p-1} \frac{1}{d} \\
	&\leq& \frac{4q \log \log p}{\pi t} \nonumber.
	\end{eqnarray}
The last inequality uses the elementary estimate $ \sum_{d \mid n} d^{-1} \leq 2 \log \log n$.
\end{proof}

\begin{lem}   {\normalfont (Gauss sums)} \label{lem333.27}  Let \(p\geq 2\) and $q$ be large primes. Let $\chi(t)=e^{i2 \pi t/q} $ and  $\psi(t)=e^{i2\pi  \tau^t/p}$ be a pair of characters. Then, the Gaussian sum has the upper bound
	\begin{equation} \label{eq3-355}
	\left |\sum_{1 \leq t \leq q-1}    \chi(t) \psi(t) \right | \leq 2 q^{1/2} \log q.
	\end{equation}

\end{lem}

\section{Maximal Error Term}  \label{s899}
The upper bounds for exponential sums over subsets of elements in finite fields $\mathbb{F}_p$ studied in Section \ref{s4} are used to estimate the error terms $E(x,y)$ and $E(x,\Lambda)$ in the proofs of Theorem \ref{thm1.1} and Theorem \ref{thm1.2} respectively.

\subsection{Short Intervals}
\begin{lem} \label{lem899.06}  Let \(p\geq 2\) be a large prime, let \(\psi \neq 1\) be an additive character, and let \(\tau\) be a primitive root mod \(p\). If the element \(u\ne 0\) is not a primitive root, then,
	\begin{equation} \label{el899.00}
	\frac{1}{p}\sum_{x \leq u\leq y,}
	\sum_{\gcd(n,p-1)=1,} \sum_{ 0<m \leq p-1} \psi \left((\tau ^n-u)m\right)\ll \frac{y-x }{p^{\varepsilon}}
	\end{equation}
	for all sufficiently large numbers $1 \leq x< y\leq p$, and an arbitrarily small number \(\varepsilon >0\).
\end{lem}

\begin{proof}  By hypothesis $\tau ^n-u\ne 0$, so $\sum_{ 0<m\leq p-1} \psi \left((\tau ^n-u)m\right)= -1$. Since $ \varphi(p-1)/p\leq 1/2$, a nontrivial error term
\begin{equation}
\left | E(x,y) \right | < \left |-\frac{\varphi(p-1)}{p}(y-x)\right | \leq \frac{y-x}{2}
\end{equation}
can be computed. Toward this end let $\psi(z)=e^{i 2 \pi z/p}$, and rearrange the triple finite sum in the form
\begin{eqnarray} \label{eq899.05}
E(x,y)&=&\frac{1}{p}\sum_{x \leq u \leq y,} \sum_{ 0<m\leq p-1,}  \sum_{\gcd(n,p-1)=1} \psi ((\tau ^n-u)m) \\
&= & \frac{1}{p}\sum_{x \leq u \leq y} \left (\sum_{ 0<m\leq p-1,} e^{-i 2 \pi um/p} \right ) \left ( \sum_{\gcd(n,p-1)=1} e^{i 2 \pi m\tau ^n/p} \right )\nonumber \\
 &= & \frac{1}{p}\sum_{x \leq u \leq y} \left (\sum_{ 0<m\leq p-1,} e^{-i 2 \pi um/p} \right ) \left ( \sum_{\gcd(n, p-1)=1} e^{i2\pi  \tau^{n}/p} + O(p^{1/2} \log^3 p) \right )\nonumber \\
 &= & \frac{1}{p}\sum_{x \leq u \leq y} U_p \cdot V_p \nonumber.
\end{eqnarray}
The third line in equation (\ref{eq899.05}) follows from Lemma \ref{lem333.22}. The first exponential sum $U_p$ has the exact evaluation
\begin{equation}\label{eq899.13}
| U_p| = \left |\sum_{ 0<m\leq p-1} e^{-i 2 \pi um/p} \right |=1,
\end{equation}
where $\sum_{ 0<m\leq p-1} e^{i 2 \pi um/p}=-1$ for any $u \in [x,y]$, with $1\leq x < y<p$. The second exponential sum $V_p$ has the upper bound
\begin{eqnarray} \label{eq899.15}
|V_p|&=& \left |\sum_{\gcd(n,p-1)=1} e^{i2 \pi \tau ^n/p}+ O\left (p^{1/2} \log^3 p \right ) \right |\nonumber \\
&\ll &\left |\sum_{\gcd(n,p-1)=1} e^{i2 \pi \tau ^n/p} \right |+p^{1/2} \log^3 p  \\
&\ll&  p^{1-\varepsilon} \nonumber,
\end{eqnarray}
where \(\varepsilon <1/2 \) is an arbitrarily small number, see Theorem \ref{thm3.4}. \\

Taking absolute value in (\ref{eq899.05}), and replacing the estimates (\ref{eq899.13}) and (\ref{eq899.15}) return
\begin{eqnarray} \label{el89991}
\frac{1}{p}\sum_{x \leq u \leq y}
\left | U_p \cdot V_p \right |
&\leq &
\frac{1}{p} \sum_{x \leq u \leq y} \left | U_p \right | \cdot  |V_p| \nonumber \\
&\ll &\frac{1}{p} \sum_{x \leq u \leq y} (1) \cdot    p^{1-\varepsilon } \\
&\ll &  \frac{ 1}{p^{\varepsilon }}\sum_{x \leq u \leq y}  1 \nonumber \\
&\ll & \frac{y-x} {p^{\varepsilon}}\nonumber,
\end{eqnarray}
These complete the verification.
\end{proof}

\subsection{Long Intervals}
The results available in the literature for primes in small intervals of the forms $[x, x+y]$ with $y < x^{1/2}$ are not uniform. In light of this fact, only the error term for
the simpler intervals $[2,x]$ can be computed effectively.

\begin{lem} \label{lem899.16}  Let \(p\geq 2\) be a large prime, let \(\psi \neq 1\) be an additive character, and let \(\tau\) be a primitive root mod \(p\). If the element \(u\ne 0\) is not a primitive root, then,
	\begin{equation} \label{el899.00}
	\frac{1}{p}\sum_{ u\leq x,}
	\sum_{\gcd(n,p-1)=1,} \sum_{ 0<m\leq p-1} \psi \left((\tau ^n-u)m\right) \Lambda(u) \ll \frac{x }{p^{\varepsilon}}
	\end{equation}
	for all sufficiently large numbers $x \geq 1$, and an arbitrarily small number \(\varepsilon >0\).
\end{lem}

\begin{proof} Same as the previous one.
\end{proof}

\section{Asymtotics For The Main Terms} \label{s999}
The notation $f(x)\asymp g(x)$ is defined by $af(x)<g(x)<bf(x)$ for some constants $a,b >0$.

\subsection{Short Intervals For Primitive Root}
\begin{lem} \label{lem999.76}  Let \(p\geq 2\) be a large prime, and let $1 \leq x <y<p$ be a pair of numbers. Then,
\begin{equation} \label{el999.38}
 \sum _{x \leq u\leq y} \frac{1}{p}\sum_{\gcd(n,p-1)=1}1\gg \frac{y-x}{\log \log p}\left (1+O\left((\log \log p) e^{-c_0 \sqrt{ \log \log p}} \right ) \right )  .
	\end{equation}

\end{lem}

\begin{proof} The maximal number $\omega(p-1)$ of prime divisors of highly composite totients $p-1$ satisfies $\omega(p-1) \gg \log p/ \log \log p$. This implies that $z \asymp \log p$. An application of Lemma \ref{lem533.21} to the ratio returns
\begin{eqnarray}
\frac{\varphi(p-1)}{p}&=&\frac{p-1}{p} \frac{1}{p-1}\prod_{q \mid p-1}\left( 1- \frac{1}{q} \right)\nonumber\\
&\geq& \prod_{q \leq z}\left( 1- \frac{1}{q} \right)\nonumber\\
&=&\frac{1}{e^{\gamma} \log z}+ O\left (e^{-c_0 \sqrt{ \log z}}\right )\\
&\gg&\frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\nonumber.
\end{eqnarray}
Substituting this, the main term reduces to

\begin{eqnarray} \label{el999.53}
M(x,y)&=&\sum _{x \leq u\leq y} \frac{1}{p}\sum_{\gcd(n,p-1)=1}1 \nonumber\\
&=& \frac{\varphi(p-1)}{p}\left ( y-x \right ) \\
&\gg& \left ( \frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\right )\left ( y-x\right )   \nonumber .
\end{eqnarray}
The proves the claim.
\end{proof}

\subsection{Long Intervals For Prime Primitive Root}

\begin{lem} \label{lem999.86}  Let \(p\geq 2\) be a large prime, and let \(x < p \) be a number. Then,
\begin{equation} \label{el999.48}
 \sum _{u\leq x} \frac{1}{p}\sum_{\gcd(n,p-1)=1}\Lambda(u)\gg \frac{x}{\log \log p}\left (1+ O\left ( \frac{e^{\gamma} \log \log p}{e^{c_0 \sqrt{ \log \log p}}}\right )\right )
	\end{equation}
for some constant $c_0>0$.
\end{lem}

\begin{proof} The maximal number $\omega(p-1)$ of prime divisors of highly composite totients $p-1$ satisfies $\omega(p-1) \gg \log p/ \log \log p$. This implies that $z \asymp \log p$. An application of Lemma \ref{lem533.21} to the ratio returns
\begin{eqnarray}
\frac{\varphi(p-1)}{p}&=&\frac{p-1}{p} \frac{1}{p-1}\prod_{q \mid p-1}\left( 1- \frac{1}{q} \right)\nonumber\\
&\geq& \prod_{q \leq z}\left( 1- \frac{1}{q} \right)\nonumber\\
&=&\frac{1}{e^{\gamma} \log z}+ O\left (e^{-c_0 \sqrt{ \log z}}\right )\\
&\gg&\frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\nonumber.
\end{eqnarray}
In addition, using the prime number theorem in the form $\sum_{n \leq x}\Lambda(n)=x +O\left (xe^{-c_0 \sqrt{ \log x}}\right )$, the main term reduces to

\begin{eqnarray} \label{el999.66}
M(x,\Lambda)&=&\sum _{u\leq x} \frac{1}{p}\sum_{\gcd(n,p-1)=1}\Lambda(u) \nonumber\\
&=& \frac{\varphi(p-1)}{p}\sum _{u\leq x}\Lambda(u) \nonumber\\
&=& \frac{\varphi(p-1)}{p}\left ( x+ O\left (xe^{-c_0 \sqrt{ \log x}}\right )\right ) \\
&\gg& \left ( \frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\right )\left ( x+ O\left (xe^{-c_0 \sqrt{ \log x}}\right )\right )   \nonumber \\
&\gg& \frac{x}{\log \log p}\left (1+O\left((\log \log p) e^{-c_0 \sqrt{ \log \log p}} \right ) \right ) \left ( 1+ O\left (e^{-c_0 \sqrt{ \log x}}\right )\right ) \nonumber\\
&\gg& \frac{x}{\log \log p}\left (1+ O\left ( \frac{e^{\gamma} \log \log p}{e^{c_0 \sqrt{ \log \log p}}}\right )\right )   \nonumber.
\end{eqnarray}
This proves the claim.
\end{proof}

\subsection{Short Intervals For Prime Primitive Root}
\begin{lem} \label{lem999.96}  Let \(p\geq 2\) be a large prime, and let $1 \leq p^{.525} <N<p$ be a pair of numbers. Then,for any number $M <p$,
\begin{equation} \label{el999.39}
 \sum _{M \leq u\leq M+N} \frac{1}{p}\sum_{\gcd(n,p-1)=1}\Lambda(u)\gg \frac{N}{e^{\gamma} \log \log p} \left (1+ O\left ( \frac{e^{\gamma} \log \log p}{e^{c_0 \sqrt{ \log \log p}}}\right )\right ) .
	\end{equation}

\end{lem}

\begin{proof} The maximal number $\omega(p-1)$ of prime divisors of highly composite totients $p-1$ satisfies $\omega(p-1) \gg \log p/ \log \log p$. This implies that $z \asymp \log p$. An application of Lemma \ref{lem533.21} to the ratio returns
\begin{eqnarray}
\frac{\varphi(p-1)}{p}&=&\frac{p-1}{p} \frac{1}{p-1}\prod_{q \mid p-1}\left( 1- \frac{1}{q} \right)\nonumber\\
&\geq& \prod_{q \leq z}\left( 1- \frac{1}{q} \right)\nonumber\\
&=&\frac{1}{e^{\gamma} \log z}+ O\left (e^{-c_0 \sqrt{ \log z}}\right )\\
&\gg&\frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\nonumber.
\end{eqnarray}
Let $x=M$, and $y=M+N$. Substituting this, the main term reduces to

\begin{eqnarray} \label{el999.51}
M(x,y,\Lambda)&=&\sum _{x \leq u\leq y} \frac{1}{p}\sum_{\gcd(n,p-1)=1}\Lambda(u) \nonumber\\
&=& \frac{\varphi(p-1)}{p}\sum _{x \leq u\leq y} \Lambda(u)\\
&\gg& \left ( \frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\right )\sum _{x \leq u\leq y} \Lambda(u)   \nonumber  .
\end{eqnarray}
Applying the prime number theorem in short intervals $\sum _{x \leq n\leq y} \Lambda(n) \gg y-x=N$, see \cite{BP01}, to the last inequality yields
\begin{eqnarray} \label{el999.51}
M(x,y,\Lambda)&\gg& \left ( \frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\right )\left ( y-x\right )   \\
&\gg& \frac{N}{e^{\gamma} \log \log p} \left (1+ O\left ( \frac{e^{\gamma} \log \log p}{e^{c_0 \sqrt{ \log \log p}}}\right )\right ) \nonumber .
\end{eqnarray}
The proves the claim.
\end{proof}

\section{Primitive Roots In Short Intervals} \label{s887}
The previous sections provide sufficient background materials to assemble the proof of the existence of primitive roots in a short interval $\left [M, M+N \right ]$ for any sufficiently
large prime $p \geq 2$, a number $N \gg (\log p)^{1+\varepsilon} $, and
the fixed parameters $ M \geq 2$ and $\varepsilon >0$. \\

The analysis below indicates that the local minima of the ratio $\varphi(p-1)/p$ at the highly composite totients $p-1$ are the primary factor determining the size of the short interval.

\begin{proof} (Theorem \ref{thm1.1}) Suppose that the short interval $\left [M, M+N \right ]=[x,y]$, with $1 \leq x <y<p$, does not contain a primitive root modulo a large primes \(p\geq 2\), and consider the sum of the characteristic function over the short interval, that is,
\begin{equation} \label{el887.40}
0=\sum _{x \leq u\leq y} \Psi (u).
\end{equation}
Replacing the characteristic function, Lemma \ref{lem333.3}, and expanding the nonexistence equation (\ref{el887.40}) yield
\begin{eqnarray} \label{el887.50}
0&=&\sum _{x \leq u\leq y} \Psi (u) \nonumber \\
&=&\sum _{x \leq u\leq y}  \left (\frac{1}{p}\sum_{\gcd(n,p-1)=1,} \sum_{ 0\leq m\leq p-1} \psi \left((\tau ^n-u)m\right) \right ) \\
&=& \frac{c_p}{p} \sum _{x \leq u\leq y,}  \sum_{\gcd(n,p-1)=1} 1+\frac{1}{p}\sum _{x \leq u\leq y,}
\sum_{\gcd(n,p-1)=1,} \sum_{ 0<m\leq p-1} \psi \left((\tau ^n-u)m\right)\nonumber\\
&=&M(x,y) + E(x,y)\nonumber,
\end{eqnarray}
where $c_p \geq 0$ is a local correction constant depending on the fixed prime $p\geq 2$. The main term $M(x,y)$ is determined by a finite sum over the trivial additive character \(\psi =1\), and the error term $E(x,y)$ is determined by a finite sum over the nontrivial additive characters \(\psi(t) =e^{i 2\pi t  /p}\neq 1\).\\

An application of Lemma \ref{lem999.76} to the main term, and an an application of Lemma \ref{lem899.06} to the error term yield
\begin{eqnarray} \label{el887.60}
\sum _{x \leq u\leq y} \Psi (u)
&=&M(x,y) + E(x,y) \nonumber\\
&\gg& \left ( \frac{1}{e^{\gamma} \log \log p}+ O\left (e^{-c_0 \sqrt{ \log \log p}}\right )\right ) (y-x)+O\left(\frac{y-x}{p^{\varepsilon}} \right ) \nonumber \\
&\gg& \frac{y-x}{\log \log p}\left (1+ O\left ( \frac{e^{\gamma} \log \log p}{e^{c_0 \sqrt{ \log \log p}}}\right )\right )   \nonumber \\
&>&0 \nonumber,
\end{eqnarray}
where the implied constant $d_p=e^{-\gamma}a_pc_p \geq 0$ depends on local information and the fixed prime $p\geq 2$. However, a short interval $[x,y]$ of length $y-x=N \gg (\log p)^{1+\varepsilon} > 0$ contradicts the hypothesis  (\ref{el887.40})
for all sufficiently large primes $p \geq 2$. Ergo, the short interval $\left [M, M+N \right ]$ contains a primitive root for any sufficiently large prime $p \geq 2$ and the fixed parameters $ M \geq 2$ and $\varepsilon >0$.
\end{proof}

\section{Least Prime Primitive Roots} \label{s888}
A modified version of the previous result demonstrate the existence of prime primitive roots in an interval $\left [2,x \right ]$ for any sufficiently large prime $p \geq 2$.
The analysis below indicates that the local minima of the ratio $\varphi(p-1)/p$ at the highly composite totients $p-1$, and the number of primes $\sum_{p \leq x}\Lambda(n)$
are the primary factors determining the size of the interval $\left [2,x \right ]$.

\begin{proof} (Theorem \ref{thm1.2}) Suppose that the interval $[2,x]$, with $1 \leq x <p$, does not contain a prime primitive root modulo a large primes \(p\geq 2\), and consider the sum of the weighted characteristic function over the integers $u \leq x$, that is,
\begin{equation} \label{el887.80}
0=\sum _{ u\leq x} \Psi (u) \Lambda(u).
\end{equation}\\
Replacing the characteristic function, Lemma \ref{lem333.3}, and expanding the nonexistence equation (\ref{el887.40}) yield
\begin{eqnarray} \label{el887.55}
0&=&\sum _{ u\leq x} \Psi (u) \Lambda(u)\nonumber \\
&=&\sum _{u\leq x}  \left (\frac{1}{p}\sum_{\gcd(n,p-1)=1,} \sum_{ 0\leq m\leq p-1} \psi \left((\tau ^n-u)m\right) \right ) \Lambda(u)\\
&=& \frac{c_p}{p} \sum _{ u\leq x} \Lambda(u) \sum_{\gcd(n,p-1)=1} 1+\frac{1}{p}\sum _{ u\leq x} \Lambda(u)
\sum_{\gcd(n,p-1)=1,} \sum_{ 0<m\leq p-1} \psi \left((\tau ^n-u)m\right)\nonumber\\
&=&M(x,\Lambda) + E(x,\Lambda)\nonumber,
\end{eqnarray}
where $c_p \geq 0$ is a local correction constant depending on the fixed prime $p\geq 2$. The main term $M(x,\Lambda)$ is determined by a finite sum over the trivial additive character \(\psi =1\), and the error term $E(x,\Lambda)$ is determined by a finite sum over the nontrivial additive characters \(\psi(t) =e^{i 2\pi t  /p}\neq 1\).\\

An application of Lemma \ref{lem999.86} to the main term, and an application of Lemma \ref{lem899.16} to the error term yield
\begin{eqnarray} \label{el887.65}
\sum _{ u\leq y} \Psi (u)\Lambda(u)
&=&M(x,\Lambda) + E(x,\Lambda) \nonumber\\
&\gg&  \frac{x}{\log \log p}\left (1+O\left((\log \log p) e^{-c_0 \sqrt{ \log \log p}} \right ) \right )  +O\left(\frac{x}{p^{\varepsilon}} \right ) \nonumber \\
&\gg&  \frac{x}{\log \log p}\left (1+ O\left ( \frac{e^{\gamma} \log \log p}{e^{c_0 \sqrt{ \log \log p}}}\right )\right )   \nonumber \\
&>&0 \nonumber,
\end{eqnarray}
where the implied constant $d_p=e^{-\gamma}a_pc_p \geq 0$ depends on local information and the fixed prime $p\geq 2$. But, an interval $[2,x]$ of length $x-2 \gg (\log p)^{1+\varepsilon} > 0$ contradicts the hypothesis  (\ref{el887.80})
for all sufficiently large primes $p \geq 2$. Ergo, the short interval $\left [2,x \right ]$ contains a prime primitive root for any sufficiently large prime $p \geq 2$ and a fixed parameter $\varepsilon >0$.
\end{proof}

\section{Prime Primitive Roots In Short Intervals} \label{s1088}
The prime number theorem in short intervals $\sum _{M \leq n\leq M+N} \Lambda(n) \gg N$, see \cite{BP01}. A modified version of the previous result will prove the existence of prime primitive roots in short interval $\left [M,M+N \right ]$ for any sufficiently large prime $p \geq 2$, $N \gg p^{.525}$ and any $M<p$. The analysis below indicates that the number of primes $\sum_{M\leq p \leq M+N}\Lambda(n)$ in a short interval $\left [M,M+N \right ]$ is the primary factor determining the size of the interval $N$. The local minima of the ratio $\varphi(p-1)/p$ at the highly composite totients $p-1$ have a minor impact on the analysis.

\begin{proof} (Theorem \ref{thm1.3}) Suppose that the interval $[2,x]$, with $1 \leq x <p$, does not contain a prime primitive root modulo a large primes \(p\geq 2\), and consider the sum of the weighted characteristic function over the integers $u \leq x$, that is,
\begin{equation} \label{el1088.80}
0=\sum _{ M\leq u\leq M+N} \Psi (u) \Lambda(u).
\end{equation}\\
Replacing the characteristic function, Lemma \ref{lem333.3}, and expanding the nonexistence equation (\ref{el887.40}) yield\\
\begin{eqnarray} \label{el1088.55}
0&=&\sum _{ M\leq u\leq M+N} \Psi (u) \Lambda(u)\nonumber \\
&=&\sum _{ M\leq u\leq M+N}  \left (\frac{1}{p}\sum_{\gcd(n,p-1)=1,} \sum_{ 0\leq m\leq p-1} \psi \left((\tau ^n-u)m\right) \right ) \Lambda(u)\\
&=&\frac{c_p}{p} \sum _{ M\leq u\leq M+N}\Lambda(u) \sum_{\gcd(n,p-1)=1} 1+\frac{1}{p}\sum _{ M\leq u\leq M+N} \Lambda(u)
\sum_{\gcd(n,p-1)=1,} \sum_{ 0<m\leq p-1} \psi \left((\tau ^n-u)m\right)\nonumber\\
&=&M(N,\Lambda) + E(N,\Lambda)\nonumber,
\end{eqnarray}
where $c_p \geq 0$ is a local correction constant depending on the fixed prime $p\geq 2$. The main term $M(N,\Lambda)$ is determined by a finite sum over the trivial additive character \(\psi =1\), and the error term $E(N,\Lambda)$ is determined by a finite sum over the nontrivial additive characters \(\psi(t) =e^{i 2\pi t  /p}\neq 1\).\\

An application of Lemma \ref{lem999.96} to the main term, and an application of Lemma \ref{lem899.16} to the error term yield
\begin{eqnarray} \label{el1088.65}
\sum _{ M\leq u\leq M+N} \Psi (u)\Lambda(u)
&=&M(N,\Lambda) + E(N,\Lambda) \nonumber\\
&\gg&  \frac{N}{\log \log p}\left (1+O\left((\log \log p) e^{-c_0 \sqrt{ \log \log p}} \right ) \right )  +O\left(\frac{x}{p^{\varepsilon}} \right ) \nonumber \\
&\gg&  \frac{N}{\log \log p}\left (1+ O\left ( \frac{e^{\gamma} \log \log p}{e^{c_0 \sqrt{ \log \log p}}}\right )\right )   \nonumber \\
&>&0 \nonumber,
\end{eqnarray}
where the implied constant $d_p=e^{-\gamma}a_pc_p \geq 0$ depends on local information and the fixed prime $p\geq 2$. But, an interval $[M,M+N]$ of length $N \gg p^{.525} > 0$ contradicts the hypothesis (\ref{el1088.80})
for all sufficiently large primes $p \geq 2$. Ergo, the short interval $\left [M,M+N \right ]$ contains a prime primitive root for any sufficiently large prime $p \geq 2$ and a fixed parameter $M\geq 0$.
\end{proof}

\section{Problems}
\begin{exe} { \normalfont
Determine an explicit interval $\left [M, M+N \right ]$, where $N \geq c_0(\log \log p)^{1+\varepsilon}$, $c_0>0$ is a constant, and $\varepsilon \leq 2$, such the the interval contains a primitive root for any prime $p\geq p_0$, and $ M \geq 2$.}
\end{exe}

\begin{exe} { \normalfont Let $a_0=\prod_{p >2}\left( 1- 1/p(p-1) \right) = 0.3739558136 \ldots$ be the average probability of a primitive root modulo a prime $p \geq 2$. Determine the length
$N \geq2$ of the average short interval $\left [M, M+N \right ]$ that contains $N\cdot (0.3739\ldots )^k  (1-0.3739\ldots )^{N-k}\geq k$ primitive roots, where $N \geq (\log \log p)^{1+\varepsilon}\geq k$, $k\geq 1$, and $\varepsilon=1$.}
\end{exe}

\begin{exe} { \normalfont Show that the distribution of primitive root modulo a large Germain prime $p=2^aq+1$ with $q \geq 2$ prime, and $a \geq 1$, has a normal approximation with
mean $\mu\approx 2^{a-1}q(1-1/q)$ and standard deviation $\sigma \approx \sqrt{2^{a-2}q(1-1/q^2)}$.}
\end{exe}

 \begin{exe} { \normalfont Estimate the number of highly composite totients $p-1$ in a short interval, that is, $$\sum_{\substack{x \leq p \leq x+y\\
\omega(p-1)\gg \log p/\log \log p}}1, $$ where $x \geq 1$ is a large number, and $1 <y<x$.
}
\end{exe}


TITLE: Hurwitz Polynomial - Why does continued fraction expansion work?
QUESTION [1 upvotes]: While checking whether the given polynomial is Hurwitz or not, we perform continued fraction expansion.  We were taught how to perform this check(i.e) look at the sign of the coefficients of the quotients after performing the normal expansion steps.
I can understand why this method would work for a normal fraction like for example $\frac{158}{18}$. But, why separating a single polynomial into odd and even terms and dividing them(and invert and continue) yields all positive terms in the quotients for a Hurwitz polynomial?

REPLY [0 votes]: The subject is beyond my knowledge. However, I came across the following proofs, I hope you find any value in either of them.
1-Paper-Elementary proof of the Routh-Hurwitz test by Gjerrit Meinsma
2-paper -A NETWORK PROOF OF A THEOREM ON HURWITZ POLYNOMIALS
AND ITS GENERALIZATION - By T. R. BASHKOW and C. A. DESOER
3-Chapter 4 - Page 75 of:
Google Books:A Mathematical Introduction to Control Theory by Shlomo Engelberg


TITLE: Probability coding confusion?
QUESTION [0 upvotes]: Consider n coding machines M1, M2, . . . Mn producing binary codes 0 and 1. The machine
M1 produces codes 0 and 1 with respective probabilities 1/
4
and 3/
4
. The code produced by machine Mk is
fed into machine Mk+1 which may either leave the received code unchanged or may change it. Suppose
that each of the subsequent machines change the code with probability 3/
4
.
Given that final produced code is 1. What is the probability that the machine M1 produced code 0.
I have little confusion, that can we neglect all machines from M1 to Mn-2 , and consider only following four cases:
M0 start with 0,then Mn-1 receive number as 1 or 0
M0 start with 1, then Mn-1 receives number as 1 or 0
to compute the probability of machine Mn to output 1?

REPLY [3 votes]: As lulu's subsequent comment indicates, I made a bad error in my answer, which I have now corrected.  Normally, I would consider leaving the erroneous analysis for contrast.  In this case however, I think that it would simply add confusion.

Assume that code starts at 0, before it is encoded by machine M1.
Let A denote the event that M1 kept the code at 0.
Let B denote the event that M1 changed the code to 1.
Let C denote the event that machines M2 through Mn had an even number of changes.
Let D denote the event that machines M2 through Mn had an
odd number of changes.
There are two mutually exclusive ways that an odd number of changes occurred.  Either events A and D both occurred, or events B and C both occurred.
Let $p = 3/4$ and let $q = (1-p).$
Then the desired probability is
$\displaystyle \frac{q \times P(D)}{[p \times P(C)] + [q \times P(D)]}.$
Let $m = (n-1)$.
For machines M2 through Mn:
Chance of $k$ changes is $f(k) = \binom{m}{k}p^kq^{(m-k)}.$
Then $P(C) = \sum_{k ~\text{even}} ~f(k)~$ and
$P(D) = 1 - P(C).$
Addendum
One of lulu's subsequent comment focused on unwinding the even/odd probabilities.
Coincidentally, the following mathSE query, which occurred in the last 24 hours, generated an answer that seems relevant here.
Prove monotonicity of combinatorial sum


TITLE: Closed convex cone - equivalence of definition via closure and via infinite sums
QUESTION [1 upvotes]: I have a set $P$ of points in a Banach space. Consider the following two cones:

The closure of the set of all (finite) nonnegative linear combinations of $P$. (I.e., the topological closure of $\{\sum_{i=1}^n a_ip_i: a_i\geq0, p_i\in P\}$.)
The set of all infinite nonnegative linear combinations of $P$. (I.e., $\{\sum_i a_ip_i: a_i\geq0, p_i\in P\}$ where $i$ can range over infinite sets, and we only consider sums that converge absolutely.)

Are those sets equal?

REPLY [4 votes]: The answer to your question is "No" (but the first set, obviously, always contains the second).
Example showing that the second set can be strictly smaller: Denote by $\{e_n\}$ the unit vector basis in $\ell_1$ and consider the following set $P:=\{e_1+\frac1ne_n\}_{n=2}^\infty$ in $\ell_1$. It is clear that $e_1$ is in the first set, but not in the second.


text:
\begin{document}
\maketitle

\begin{abstract}
{We prove that a Banach lattice $X$ which does not contain the
$l^n_{\infty}$-uniformly has an equivalent norm which is uniformly
Kadec-Klee for a natural topology $\tau$ on $X$.   In case
the Banach lattice is purely atomic, the topology $\tau$ is
the coordinatewise convergence topology.}
\end{abstract}
\vspace*{3in}

\noindent {\bf 1980 Mathematics Subject Classification}: Primary
46B03, 46B42.\\
\noindent {\bf Key words and phrases}: Renorming, Banach lattices,
Uniform Kadec-Klee.
\newpage

\baselineskip=24pt
\font\tfont= cmbx10 scaled \magstep3
\font\afont= cmcsc10 scaled \magstep2
\centerline{\tfont Uniform Kadec-Klee Property in Banach lattices}
\bigskip
\centerline{\afont F. Chaatit and  M. A. Khamsi }

\bigskip
\begin{abstract}
{We prove that a Banach lattice $X$ which does not contain the
$l^n_{\infty}$-uniformly has an equivalent norm which is uniformly
Kadec-Klee for a natural topology $\tau$ on $X$.   In case
the Banach lattice is purely atomic, the topology $\tau$ is
the coordinatewise convergence topology.}
\end{abstract}

\newtheorem{thm}{Theorem }[chapter]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{ex}{Exercise}
\newenvironment{proof}{\medskip \par \noindent {\bf Proof:}\ }{\hfill $\Box$
                       \medskip \par}

\setcounter{section}{0}

\setcounter{thm}{0}
\setcounter{ex}{0}
\setcounter{page}{1}

\newcommand{\bdfn}{\noindent{\bf Definition:\,} \begin{em}}
\newcommand{\edfn}{\end{em}}
\newcommand{\ntn}{\noindent{\bf Notations:\,\,}}

\newcommand{\rmk}{\noindent{\bf Remark\,\,}}

\newcommand{\del}{\mbox{$\delta$}}
\newcommand{\lftyn}{\mbox{${l_{\infty}^{n}}$}}
\newcommand{\norm}[1]{\mbox{$\|#1\|$}}
\newcommand{\som}{\mbox{$\displaystyle\sum_{n=0}^{\infty}$}}
\newcommand{\son}{\mbox{$\displaystyle\sum_{n=1}^{\infty}$}}
\newcommand{\reals}{\mbox{\bf R}}
\newcommand{\complexes}{\mbox{\bf C}}
\newcommand{\integers}{\mbox{\bf N}}
\newcommand{\smint}{\mbox{\scriptsize {\bf N}}}
\newcommand{\complex}{\mbox{\bf C}}
\newcommand{\ep}{\mbox{$\varepsilon$}}
\newcommand{\B}{\mbox{${\cal B}_1(K)$}}
\newcommand{\pf}{\noindent{\bf Proof:\,\ }}
\newcommand{\ra}{\mbox{$\longrightarrow$}}
\def\qed{~\hfill~\blackbox\medskip}
\def\blackbox{\hbox{\vrule width6pt height7pt depth1pt}}

\newcommand{\osm}{\mbox{$(\Omega,\Sigma,\mu)$}}
\newcommand{\om}{\mbox{$\omega$}}

\section{Introduction}

The uniform Kadec-Klee (in
short UKK) property was introduced by R. Huff in \cite{bib:H}.  Banach spaces with
Schur property, as well as uniformly convex spaces, enjoy the UKK
property. P. Enflo characterized Banach spaces which have an equivalent
 uniformly convex  norm as those which are super-reflexive.  Similarly
R. Huff raised the following question :\\
{\em Under what conditions does a Banach space possess an equivalent
norm which is UKK ?}\\
Spaces with such a property are called UKK-able.  Known examples of
UKK-able spaces are the Hardy space $H_1$ of analytic functions on the
ball or on the polydisc \cite{bib:B.D.D.L}, the Lorentz spaces
$L_{p.1}(\mu)$
\cite{bib:C.D.L.T},
the trace class $C_1$ \cite{bib:L}, Gower's space which does not contain
$c_0, \,\, l_1,$ or any reflexive subspace \cite{bib:G}.
  Using  Prus ideas \cite{bib:Pr},
UKK-ability was intensively  studied in \cite{bib:D.G.K} for Banach spaces with a basis.\\

R. Huff associated an index to UKK-ability and proved that UKK-ability
implies that the index is finite.  He asked whether the converse is
true.  To our knowledge, it is still unknown in the general case.
G. Lancien \cite{bib:La} proved that the converse is true for the space of Bochner
integrable functions $L^p(X)$. More recently,  H. Knaust and E. Odell
proved that the converse is true for reflexive  Banach spaces
with  a finite dimensional decomposition  \cite{bib:K.O}.\\

In \cite{bib:K.T} a natural topology $\tau$ was introduced in Banach lattices.
This topology reduces to the topology of coordinatewise convergence in the case of
Banach spaces with basis, and to  the topology of convergence in measure in
usual spaces of measurable functions with order continuous norm.  In
this work, we define and investigate the UKK-ability for the topology
$\tau$. We first establish a generalization of a result of
Kutzarova and Zachariades \cite{bib:K.Z} to the setting of
Banach lattices using well known
techniques of Pisier \cite{bib:Pi}. If $X$ is a Banach lattice
that satisfies a lower 1-estimate for any two disjoint
elements with a constant less than two, then $X$ must satisfy a lower
p-estimate for some $1\leq p <\infty.$ This will be Theorem 3.
 Our main result -Theorem 4- is that Banach lattices with a lower
p-estimate for $1 \leq p < \infty$ are $\tau$-UKK-able.
 In particular, given that the $/tau$ topology and the topology of
convergence in measure are the same in $L_1$, we get the following
result
of \cite{bib:L2} that    $L_1$ is UKK  for the convergence in measure
  eventhough it fails
to be UKK-able for the weak-topology \cite{bib:D.G.K}.
 Let us also mention that $c_0$ is not $\tau$ UKK-able since it has an unconditional basis and it is known that it is not UKK-able
 for the weak topology, its Huff index being infinite.

We also investigate the relationship between super-reflexivity
and super-UKK-ability and prove that these notions are equivalent in the
lattice case.

\section{Basic Definitions and Properties.}

A sequence $(x_n)$ in a
Banach space $X$ is said to be $\varepsilon$-separated (with
$\varepsilon > 0$) if $$\inf \{ ||x_n - x_m|| ; \; n \not= m \} \geq
\varepsilon \ .$$ Let $\theta$ be any linear topology on $X$.  We say
that $X$ has the $\theta$-uniform Kadec-Klee (in short $\theta$-UKK)
property if for each $\varepsilon > 0$ there exists $\delta > 0$ such
that for  every $\varepsilon$-separated sequence $(x_n)$ in the unit ball
of $X$ which is $\theta$-convergent to $x$, we have that $||x|| \leq 1 -
\delta$.\\

 Let $X$ be a Banach lattice.  Let $u$ and $x$ be elements of $X$.
define $$ S_u(x) = x^+ \wedge |u| - x^- \wedge |u| $$ where $x^+$ and
$x^-$ are respectively the positive and negative parts of $x$ under
the lattice structure of $X$.\\

\bdfn
Let $X$ be a Banach lattice. The topology $\tau$ on $X$ is the coarsest linear
topology  for which the maps $x \rightarrow |||x|\wedge|u|||$
are continuous at $0$ for every $u \in X$.\\
\edfn

Thus a basis of neighborhoods of a point $x \in X$ is formed
 by the sets: $\{y \in X s.t. \| |y-x| \wedge u\| \leq \ep\}$
where $u \in X^+$ and $\ep > 0.$
The topology $\tau$ was introduced by M.A. Khamsi and Ph. Turpin in \cite{bib:K.T}
  to generalize a
fixed point theorem of P.K. Lin \cite{bib:Li} to the setting
of Banach lattices.   It
was then observed that in the  spaces of measurable functions with order
continuous norm, $\tau$ is the topology of convergence in measure on
every set with finite measure.  On the other hand, for Banach spaces
with an unconditional basis, $\tau$ is the topology of coordinatewise
convergence. Among the nice properties of this topology is that it is
a Hausdorff, linear topology, coarser than  the norm; and if $K$
is $\tau$-compact then every sequence $(x_n)$ of points of $K$ has
a $\tau$-convergent subsequence \cite{bib:K.T}.  \\

\begin{prop}
Let $X$ be a Banach lattice. For any $x$ and $y$ in $X$,
$x - S_y(x)$ and $y - S_x(y)$ are disjoints.
\end{prop}

\pf
  We have
$$y - S_x(y) = y^+ - y^- - \Big[ y^+ \wedge |x| - y^- \wedge |x| \Big]
\ .$$
Therefore, we get
$$(1)\;\;\;\; \left\{ \begin{array}{lcl}
y - S_x(y) &=& (y^+ -  y^+ \wedge |x|) - (y^- - y^- \wedge |x|) \\
x - S_y(x) &=& (x^+ -  x^+ \wedge |y|) - (x^- - x^- \wedge |y|)
\end{array} \right.$$

Note that $y^+ -  y^+ \wedge |x|\geq 0$ and $ y^- - y^- \wedge |x|
\geq 0$.  The same is true if we exchange $x$ with $y$.  Since $$y^+
\geq y^+ - y^+ \wedge |x| \;\;\;\mbox{and}\;\;\; y^- \geq y^- - y^-
\wedge |x| \ ,$$
we have
$$0 = y^+ \wedge y^- \geq \Big(y^+ - y^+ \wedge |x|\Big) \wedge \Big(
 y^- - y^- \wedge |x|\Big) \ .$$
The same is true if we exchange $y$ with $x$.  Thus the decomposition
in $(1)$ is a disjoint one in both equations.  In order to complete
the proof, we need to show that
$$(i)\;\;\; \Big(y^+ - y^+ \wedge |x|\Big) \wedge \Big(
 x^+ - x^+ \wedge |y|\Big) = 0$$
 and
$$(ii)\;\;\; \Big(y^+ - y^+ \wedge |x|\Big) \wedge \Big(
 x^- - x^- \wedge |y|\Big) = 0 \ .$$
Put $a = \Big(y^+ - y^+ \wedge |x|\Big) \wedge \Big(
 x^+ - x^+ \wedge |y|\Big)$.  It is clear that
$0 \leq a \leq y^+ - y^+ \wedge |x|$; therefore,
$$a + y^+ \wedge x^+ \leq a + y^+ \wedge |x| \leq y^+$$
and
$$a + y^+ \wedge x^+ \leq a + |y| \wedge x^+ \leq x^+ \ .$$
Thus, $a + y^+ \wedge x^+ \leq y^+ \wedge x^+,$ which
implies that  $a \leq 0$.  This shows that we must have $a = 0$.  The proof of $(ii)$ is
done similarly.
\qed

\begin{prop}
 Let $(x_n)$ be a
sequence $\tau$-convergent to $x$.  Then we have
$$\lim_{n \rightarrow \infty} ||S_u(x_n - x)|| = 0 \;\;\;\mbox{and}\;\;\;
\lim_{n \rightarrow \infty} ||S_{x_n - x}(u)|| = 0$$
for every $u$ in $X$.
\end{prop}

\pf
 By the triangle inequality we  have  $$||S_u(x_n - x)|| \leq
||(x_n - x)^+ \wedge |u| || + ||(x_n - x)^- \wedge |u| || \ .$$ Since
$X$ is a lattice, there exists $K >0$ such that $|x| \leq |y|$ implies
$||x|| \leq K ||y||$ for every $x$ and $y$ in $X$.  We then get
$$||S_u(x_n - x)|| \leq 2 K |||x_n - x| \wedge |u| ||$$ which implies that
$$\lim_{n \rightarrow \infty} ||S_u(x_n - x)|| = 0 \ .$$ On the other
hand, since $$||S_{x_n - x}(u)|| = |||x_n - x| \wedge u^+  -
|x_n - x| \wedge u^- || \leq |||x_n - x| \wedge u^+ || + ||
|x_n - x| \wedge u^- ||  $$
which clearly implies that
$$\lim_{n \rightarrow \infty} ||S_{x_n - x}(u)|| = 0 \ .$$
\qed

We now recall the definition of a lower p-estimate

\bdfn
 Let $1 \leq p < \infty$.  A
Banach lattice $X$ is said to satisfy a lower $p$-estimate (for
disjoint elements) if there exists a constant $C<\infty$ such that,
for every choice of pairwise disjoint elements $(x_i)_{1 \leq i \leq
n}$ in $X$, we have
$$\Bigg(\sum_{i} ||x_i||^p \Bigg)^{1/p} \leq C ||\sum_{i} x_i || \ .$$
\edfn

\rmk {\bf 1:}
Let $X$ be a Banach space with an unconditional basis.
If $X$ is $\tau$-UKK-able then $X$ is UKK-able.

Indeed, as observed in \cite{bib:K.T}, in such a situation the $\tau$
topology
and the coordinatwise topology are the same. Given that a weakly
convergent sequence $(x_n)$ to an element $x \in X$ is coordinatwise
convergent to $x,$ the $\tau$ UKK-ability is clearly seen to be stronger
than the UKK-ability.

\rmk {\bf 2:}
 Let $X$ be a Banach
lattice.
Then $X$ admits an
equivalent norm $||.||_0$ which satisfies
$$(*)\;\;\;||x||_0 + ||y||_0 \leq 2 ||x+y||_0$$
for any disjoint $x,y \in X$.

 Indeed, set
$$||x||_0 = \max\{||x^+||, ||x^-||\} \;\;\;\forall x \in X \ .$$
Then we have for any disjoint elements $x$, $y$ in $X$,
$$||x||_0 \leq ||x + y||_0 \;\;\;\mbox{and}\;\; ||y||_0 \leq ||x +
y||_0$$
which implies  $||x||_0 + ||y||_0 \leq 2 ||x + y||_0$.\\
We easily  check that $\| . \|_0 $ is an equivalent norm, since
 $\|x\| = \|x^+ + x^-\| \leq \|x^+ \| + \|x^-\| \leq 2 \|x\|_0$
and $\|x\|_0 \leq ||x^+|| + ||x^-|| \leq  2 ||x||.$ \\

Note that every Banach lattice has an equivalent norm which satisfies a lower 1-estimate for any two disjoint elements with a constant $c \geq 2$.
 We don't have to consider the case $c=2$ since $c_0$
satisfies such an estimate with $c=2$ but is not UKK-able, and
therefore is not $\tau$-UKK-able by our first remark.
But for the case $c < 2,$ we do have a positive answer
to the UKK-ability problem.
This will be our next theorem.

We now  want to establish a generalization of a theorem by
Kutzarova and Zachariades \cite{bib:K.Z} and we will use techniques
of Pisier \cite{bib:Pi}.
In the case of Banach spaces with basis this version was used by S.
Dilworth,
M. Girardi and D. Kutzarova in \cite{bib:D.G.K} as
a criterion to show that Gower's space, that does not contain $c_0,
\,\, l_1$ or any reflexive subspace, is UKK-able. The proof is classical and we include it here for the sake of completeness.

\begin{thm}
Let $X$ be a Banach lattice. Suppose that there exists a constant $c,$
with $0<c<2,$ such that
$$\,\,(***)\,\,\,\, c \,
 \|x + y \| \geq (\|x\| + \|y\|)$$
for all disjoint $x$ and $y$ in $X.$
Then $X$ satisfies a lower p-estimate for some $1 \leq p <\infty.$
\end{thm}

\pf
Suppose that there exists such a constant such that (***) is satisfied
for any disjoint $x_1$ and $x_2$ in $X.$
Then $\inf \Bigg(||x_1||, ||x_2||\Bigg) \leq (c/2) ||x_1 + x_2||.$\\
Similarly,
$\inf \Bigg( ||x_1||, ||x_2||, ||x_3||, ||x_4|| \Bigg) \leq (c/2)^2
||\sum_{i=1}^{4} x_i||$
for all $(x_i)_{1 \leq i \leq 4}$ that are disjoint.

So $$\inf_{1 \leq i \leq 2^n} \Bigg( ||x_i|| \Bigg) \leq (c/2)^n
||\sum_{i=1}^{2^n} x_i ||$$ for all $(x_i)_{1 \leq i \leq 2^n}$ that
are disjoint.

Now for a general $m,$ there exists a $k$ such that $2^k \leq m \leq
2^{k+1}.$
Then
\begin{eqnarray*}
||\sum_{i=1}^{m} x_i || & = & || \sum_{i=1}^{2^k} x_i + \sum_{i=2^{k}
+1}^{m} x_i|| \\
                        & \geq & 1/c \Bigg(|| \sum_{i=1}^{2^k} x_i|| +|| \sum_{i=2^{k}
+1}^{m} x_i|| \Bigg) \\
                        & \geq & 1/c \,\,|| \sum_{i=1}^{2^k} x_i|| \\
                        & \geq & 1/c \,\,(2/c)^k \inf_{1 \leq i \leq 2^k}
			||x_i|| \\
                        & \geq & 1/c \,\,(2/c)^k \inf_{1 \leq i \leq m}
			||x_i|| \\
\end{eqnarray*}

Thus $$\inf_{1 \leq i \leq m} ||x_i|| \leq \frac{c^{k+1}}{2^k} ||
\sum_{i=1}^{m} x_i||$$ for all finite disjoint sequences in $X.$

\noindent{\bf Claim 1:}{\em There exists a constant $c$ and a real
number $p< \infty$ such that
$$\inf_{1 \leq i \leq m} ||x_i|| \leq \frac{c}{m^{1/p}}
||\sum_{i=1}^{m}x_i||$$
for all $m$ and disjoint $(x_i)_{1\leq i \leq m}$ in $X.$}
\\

\noindent{\bf Proof of Claim 1:}
It suffices then to prove that $(c/2)^k \leq
\frac{1}{m^{1/p}},$
which reduces to find a real number $p$ such that
$\frac{\log m}{k \log (2/c)} \leq p.$
But $2^k \leq m < 2^{k+1},$ so $2 \log 2 \geq (\frac{k+1}{k})\log 2
\geq \frac{\log m}{k}.$ Therefore $p = 2\frac{\log 2}{\log(2/c)}$
works, and the proof of Claim 1 is complete.
\\

\noindent{\bf Claim 2:}{\em For all reals $r > p,$ there exists a constant
$K_r$ so that for all $(x_i)$ that are disjoint in $X,$ we have
$$\Big(\sum_{i=1}^{n} ||x_i||^r \Big)^{1/r} \leq K_r
|| \sum_{i=1}^{n}x_i||.$$}
\\

\noindent{\bf Proof of Claim 2:}
Suppose that $||x_1|| \leq ||x_2|| \leq ....\leq ||x_n||.$\\
Then $||x_1|| \leq \frac{c}{n^{1/p}} ||\sum_{i=1}^{n}x_i||,$ by Claim
1.

\noindent{Similarly,}
 $||x_2|| \leq \frac{c}{(n-1)^{1/p}} ||\sum_{i=2}^{n} x_i|| \leq c
\cdot  \frac{c}{(n-1)^{1/p}} ||\sum_{i=1}^{n} x_i||.$

\noindent{So} $||x_3|| \leq \frac{c}{(n-2)^{1/p}} ||\sum_{i=3}^{n} x_i|| \leq c
\cdot  \frac{c}{(n-2)^{1/p}} ||\sum_{i=1}^{n} x_i||,$

\noindent{and} $||x_n|| \leq \frac{c}{(n-(n-1))^{1/p}} ||x_{n}|| \leq c
\cdot  \frac{c}{(n-2)^{1/p}} ||\sum_{i=1}^{n} x_i||.$

\noindent{Combining all inequalities together we get:}
$$\sum_{i=1}^{n}||x_i||^r \leq
\Big(\sum_{i=1}^{n}\frac{c^{2r}}{i^{r/p}}\Big)||\sum_{i=1}^{n}x_i||^r.$$
So it suffices to let $K_r = \Big(\sum_{i=1}^{\infty}
\frac{c^{2r}}{i^{r/p}}\Big)^{1/r}.$
The proof of Claim 2 is complete, and the theorem is proved.
\qed

\section{Main result.}

As in \cite{bib:H}, assume that $X$ is a Banach lattice satisfying a lower
$p$-estimate ($1 \leq p < \infty$), and  set
\begin{equation}
||x||_0 = \sup\Bigg(\sum_{n} ||x_n||^p \Bigg)^{1/p} \;,
\label{norm0}
\end{equation}
 where the supremum is
taken over all pairwise disjoint elements $(x_i)$ such that $x =
\sum_{i} x_i$.  It is easy to see that $||.||_0$ is a
norm on $X$ for which $||.|| \leq ||.||_0 \leq C ||.||$, i.e. the
norm $||.||_0$ is equivalent to $||.||$.  Moreover we have
$$\;\;\;\; ||x||_0^p + ||y||_0^p \leq ||x + y||_0^p $$
for any disjoint elements $x$ and $y$ in $X$.\\

\begin{thm}
   Let $X$ be a Banach
lattice with a $p$-lower estimate for $ 1 \leq p < \infty$.  Then the
norm $||.||_0$ (defined by (1)) is $\tau$-UKK.
\end{thm}

\pf
  Let $\varepsilon > 0$ and $(x_n)$ be
$\varepsilon$-separated elements in the unit ball of $X$  such that
$\tau-\lim x_n = x$.  Since for every integers $n \not= m$ we have
$$\varepsilon \leq ||x_n - x_m ||_0 \leq ||x_n - x||_0 + ||x_m - x||_0$$
we get
$$\frac{\varepsilon}{2} \leq \liminf_{n \rightarrow \infty} ||x_n -
x||_0 \ .$$
Since $x_n - x - S_{|x|}(x_n - x)$ and $x - S_{|x_n-x|}(x)$ are
disjoints (by Proposition 1), then we have
$$||x_n - x - S_{|x|}(x_n - x)||_0^p + ||x - S_{|x_n-x|}(x)||_0^p \leq
||x_n - x - S_{|x|}(x_n - x) + x - S_{|x_n-x|}(x)||_0^p \ .$$
But $x_n - x - S_{|x|}(x_n - x) + x - S_{|x_n-x|}(x) =
x_n  - S_{|x|}(x_n - x)  - S_{|x_n-x|}(x)$, and since
$$\lim_{n \rightarrow \infty}||S_{|x|}(x_n - x)||_0 = 0 =
\lim_{n \rightarrow \infty} || S_{|x_n-x|}(x)||_0,$$
then we have
\begin{eqnarray*}
\liminf_{n \rightarrow \infty}||x_n-x||^p_0 + ||x||_0^p & = &
\liminf_{n \rightarrow \infty} ||x_n - x - S_{|x|}(x_n - x)||_0^p +
\liminf_{n \rightarrow \infty}||x - S_{|x_n-x|}(x)||_0^p \\
                 &  \leq &
\liminf_{n \rightarrow \infty}||x_n||^p_0 \leq 1.
\end{eqnarray*}
Therefore, we obtain
$$||x||^p_0 \leq 1 - \liminf_{n \rightarrow \infty}||x_n-x||^p_0 \leq
1 - \left(\frac{\varepsilon}{2}\right)^p $$
which implies that $||x||_0 \leq 1-\delta$, with
$$\delta = 1 -\left(1 -
\left(\frac{\varepsilon}{2}\right)^p\right)^{1/p} \ .$$
This completes the proof of Theorem 2.\\

We then get the following

\begin{cor}
 Let $X$ be a Banach
lattice that does not contain $l_{\infty}^{n}$ uniformly for every
$n.$
  Then $X$
is $\tau$-UKK-able.
\end{cor}

\pf
Let $X$ be a Banach lattice which does not contain $\l_{\infty}^{n}$
uniformly for all $n.$ By the result of \cite{bib:J} and \cite{bib:Sh}
$X$ has a lower p-estimate for some $1 \leq p < \infty.$
We then use the previous result.
\qed

\section{Super-UKK-ability in Banach lattices}
In \cite{bib:D.G.K} the following question is raised:
Is
super-reflexivity and super-UKK-ability equivalent in any Banach
space? In the next proposition, we give a positive answer in  the case
of Banach lattices. To our knowledge the general question is still open.

\begin{prop}
Let $X$ be a Banach lattice. $X$ is super-reflexive if and only if
$X$ is super-UKK-able.
\end{prop}

\pf
If $X$ is super-reflexive then $X$ is clearly super-UKK-able.
Suppose now that $X$ is super-UKK-able.
Take any ultrapower $\Pi X/{\cal U}.$
This is still a Banach lattice.
So it either contain $c_0,$
or $l_1,$ or is reflexive.
It can't contain $c_0$ since $\Pi X/{\cal U}$ is UKK-able.
If $\Pi X/{\cal U}$ contains $l_1$ then its ultrapower
$\Pi\Bigg(\Pi X/{\cal U}\Bigg)$ would contain $L_1$
which is not UKK-able.
Therefore $\Pi X/{\cal U}$ is reflexive, i.e. $X$ is super-reflexive.
\qed

\rmk

As it was pointed out to us by D. Leung, the proof of the previous
proposition
actually shows that if $X$ is a super-UKK-able Banach space,
then $X$ cannot contain $l_{\infty}^n$ or $l_1^n$ uniformly in $n.$
However, it is well known that in
a general Banach space, the latter condition is not sufficient
for super-reflexivity. In fact G. Pisier and Q. Xu constructed for
every $q>2$ a non-reflexive space of type 2 and cotype $q.$

config: arxiv


TITLE: Splitting up the nodes of a Graph such that all nodes in these graphs have even degree.
QUESTION [1 upvotes]: $G$ is a simple undirected graph. Show that
2 disjunctive sets $A$ and $B$ exist such that $A \cup B = V(G)$ and all nodes in $G[A]$ and $G[B]$ have even degree.
I have already proven that this is true for trees and cycles.
Sadly I have to idea generalize that.
It would be really great if someone could give me a hint.

REPLY [0 votes]: Can be proved by induction on number of vertices:
Base case: if $G$ is a graph on less than 3 vertices, then the claim is true. for example, if the graph is $k_3$ then $A=V(G),B=\{\}$ is a desired partition.
Suppose the claim is true for all graph on $n$ vertices and we are given a graph $G$ on $n+1$ vertices, then  if all vertices of $G$ is even then done, as we can take $A=V(G)$ and $B=\{\}$. So suppose there is a vertex $v\in V(G)$ of odd degree, then construct a new graph $G'$ from $G$ by removing the vertex $v$ and change the induced subgraph of the resulting graph induced by the vertices $N(v)$ by its complement graph. Then by induction hypotheses, there is a partition $(A,B)$ of $G'$ such that the vertices of the induced graph on A and B all have even degree. Now one of $A \cap N(v)$ or $B \cap N(v)$ is even as $|N(v)|$ is odd. So Suppose W.L.O.G, that $|A \cap N(v)|$ is even, then consider partition $A'=A\cup \{u\}, B'=B$ of $G$. We have that vertices $u \neq N(v) \cup{v} $ have even degree in induced subgraph on $A'$ or $B' $. $v$ has even degree in the induced subgraph on $A$ by construction of $A$. The parity of degree of a vertex $u\in N(v) \cap A$ is flipped twice going from a vertex in induced graph on $A$to $A'$ once when we added $v$ to $A$, once we change the the subgraph spanned by $N(v)$ to its complement. The parity of degree of a vertex in $B \cap N(S)$ is unchanged as there are odd number of vertices in $B \cap N(S)$ and so a vertex  there has at most  even number of neighbour(Think about this,  I have hard time explaining) so when you look at complement graph of line graph induced by $B\cap N(S)$, the parity of a vertex stays the same.  So  that' s it.


TITLE: first-order differential equation problem
QUESTION [0 upvotes]: Given that $y=\sin(x)$ is an expicit function of the first-order differential equation $\frac{dy}{dx}=\sqrt{1-y^2}$. Find an interval I of definition, the solution interval.
So I got to the point that $\cos(x)={\cos(x)}$, what do I do next?

REPLY [0 votes]: $\sqrt{1-\sin ^2 x}\geq 0$. Hence $\cos x \geq 0$ which requires $0\leq x\leq \pm \pi/2$.


TITLE: Why do we do a linear regression to find the minimum wavelength in a X-Ray diffraction spectrum?
QUESTION [1 upvotes]: As part of a an experiment, I was to determine the minimum wavelength emitted by an x-ray source through analysing the detected count rate (detected by a GM counter) of a diffracted x-ray source, via a crystal; NaCl.
From the experimental data, we are able to plot a graph of count rate against x-ray wavelength.
What I do not understand is that the lab manual had asked us to determine the minimum wavelength via linear regression of the points close to the end of the spectrum. The plots and linear regressions are shown below:

Is there any scientifc reason behind the linear regression? Or is it just a experimental approximation due to the lack of resolution in wavelength?
Why can't we take minimum wavelength to be the point where the count rate meets the background count rate?

REPLY [1 votes]: I believe its due to thermalisation & defects states which may mean that you have a spread of minimum values of X-ray emission.
The density of states should be roughly linear near the band gap (i.e. conduction and valence bands), which means that a linear regression is normally taken until this intersects with the background/zero level.
This is also common practise in photoelectron spectroscopy.


TITLE: Two and One sided limits
QUESTION [0 upvotes]: I understand the difference and how to get each but when do you use one or the other?
Does it depend on the problem? When would you want to take the right and left limits vs when you would just take the limit as it approaches whatever?

REPLY [1 votes]: This is a rather general question but here are some things.
A two sided limit exists iff both limits go to the same value.
We often use one sided limits for evaluating what a function does near discontinuities or end points.  Think about a function that is only defined on (a,b).  The two sided limit not defined for x=a or x=b.  However there is a one sided limit at both ends.
In general two sided limits are what are used most commonly because the one sided limits both tend to equal each other if there is a jump discontinuity.
One sided limits basically only matter when there is a at weird spots in a function.  Discontinuities, end points or infinities.


TITLE: Travel time and combinations.
QUESTION [0 upvotes]: Four people must evacuate from an island to the mainland. The only link is a narrow bridge which allows passage of two people at a time. Moreover, the bridge must be illuminated, and the four people have only one lantern among them. After each passage to the mainland, if there are still people on the island, someone must bring the lantern back. Crossing the bridge individually, the four people take 2, 4, 8 and 16 minutes respectively. Crossing the bridge in pairs, the slower speed is used. What is the minimum time for the whole evacuation?
I took various combinations of 2,4,8 and 16 and added the various combinations. This is a very long method of calculation. First 2m,4m -> 4m ...   Then 2m will return so 4+2=6m ...   Then 2m,8m -> 8m ...   So 6+8=14m ...   Then 2m will return so 14+2=16m ...   Then 2m,16m -> 16m ...   So 16+16=32m
So, I get the answer as 32minutes. Is this correct?

REPLY [1 votes]: I presented a shorter solution with 30 minutes length in the comment above:
2 and 4 go -> takes 4 mins, 2 goes back, then 8 and 16 go -> takes 16 mins, then 4 goes back, then 2 and 4 go again, all in all 4+2+16+4+4=30 minutes.
And I thought a bit if you can prove that it's the shortest one. I think you can as follows:
One obviously needs (at least) 3 rounds to bring all four to the other end of the bridge. Every passage of the bridge away from the island lasts at least 4 minutes, since the best you can do is send the 2 minute and the 4 minute guy. One passage will have to feature the 16 minute guy, so the times for the three crossings away from the island will be at least $4+4+16=24$ minutes.
The fastest combination for the two crossings back is $2 \cdot 2=4$, but this is only possible if the 2-minute-guy is always at the end of the bridge, which means that he has to move all the time, leading to the solution proposed by the OP above which lasts 32 minutes. The second best option leads to $2+4$ minutes and gives my solution.
This shows, admittedly with a lot of words, that my suggested solution is indeed the shortest possible one.


text:
\section{A frequency function}
\label{Sec_Frequency}

In view of \autoref{Prop_PsiW22Bound} the following result is the key to proving \autoref{Thm_A}.

\begin{prop}
  \label{Prop_NormPsiControlsRho}
  There exists a constant $\omega > 0$ such that for each solution $(A,\Psi,\alpha) \in \sA(\sL) \times \Gamma\(\Hom(E,\slS\otimes \sL)\) \times (0,\pi/2)$ of \eqref{Eq_nSW} we have
  \begin{equation*}
    \rho(x) \gtrsim \min\set{1,|\Psi|^{1/\omega}(x)}.
  \end{equation*}
\end{prop}

The proof of this proposition will be given in \autoref{Sec_NormPsiControlsRho}.
In this section we lay the groundwork by introducing the following tool:

\begin{definition}
  \label{Def_Frequency}
  The \emph{frequency function} $\scN_x\co (0,r_0] \to [0,\infty)$ of $(A,\Psi,\alpha) \in \sA(\sL) \times \Gamma\(\Hom(E,\slS\otimes \sL)\) \times (0,\pi/2)$ at $x \in M$ is defined by
  \begin{equation*}
    \scN_x(r) := \frac{rH_x(r)}{h_x(r)}
  \end{equation*}
  with
  \begin{equation*}
    \begin{split}
      H_x(r)
      &:= \int_{B_r(x)} |\nabla_{A\otimes B} \Psi|^2 + \tan(\alpha)^{-2}|\mu(\Psi)|^2
      \\ \andq
      h_x(r)
      &:= \int_{\del B_r(x)} |\Psi|^2.
    \end{split}
  \end{equation*}
  If the base-point $x$ is obvious from the context and confusion is unlikely to arise, we will often drop $x$ from the notation and just write $\scN$, $H$ and $h$.
\end{definition}

\begin{remark}
  The notion of frequency function, introduced by Almgren \cite{Almgren1979}, is important in the study of singular/critical sets of elliptic partial differential equations, see, e.g., \cites{Han1998,Naber2014}.
  Our frequency function is an adaptation of the one used by Taubes in \cite{Taubes2012}.
\end{remark}

Throughout the rest of this section we will assume that $(A,\Psi,\alpha) \in \sA(\sL) \times \Gamma\(\Hom(E,\slS\otimes \sL)\) \times (0,\pi/2)$ satisfies \eqref{Eq_nSW} and fix a point $x \in M$.
We establish various important properties of the frequency function.
In particular, we show that:
\begin{itemize}
\item
  $\scN$ is almost monotone increasing in $r$.
\item
  $\scN$ controls the growth of $h$.
\item
  If $|\Psi|(x) > 0$, then $\scN(r)$ goes to zero as $r$ goes to zero.
\end{itemize}
Moreover, we study the base-point dependence of $\scN$.

\subsection{Almost monotonocity of \texorpdfstring{$\scN$}{N}}
\label{Sec_AlmostMonotonicityOfFrequency}

\begin{prop}
  \label{Prop_NDerivativeLowerBound}
  The derivative of the frequency is bounded below as follows
  \begin{equation}
    \label{Eq_NDerivativeLowerBound}
      \scN'(r) \geq O(r)(1+\scN(r)).
  \end{equation}
\end{prop}

Before we embark on the proof, which occupies the remainder of this subsection, let us note the following consequence:

\begin{prop}
  \label{Prop_NMaxGrowth}
  If $0 < s \leq r$, then
  \begin{equation}
    \label{Eq_NMaxGrowth}
    \scN(s) \leq e^{O\(r^2-s^2\)}\scN(r) + O\(r^2-s^2\).
  \end{equation}
\end{prop}

\begin{proof}
  From \eqref{Eq_NDerivativeLowerBound} it follows that
  \begin{equation*}
    \del_r \log(\scN(r)+1) \geq -2cr.
  \end{equation*}
  This integrates to
  \begin{equation*}
    \log(\scN(r)+1) - \log(\scN(s)+1) \geq -c(r^2 - s^2),
  \end{equation*}
  i.e.,
  \begin{equation*}
    \scN(s)+1 \leq e^{c(r^2-s^2)}(\scN(r)+1),
  \end{equation*}
  which directly implies \eqref{Eq_NMaxGrowth}.
\end{proof}

The derivative of the frequency is
\begin{equation}
  \label{Eq_NDerivative}
  \scN'(r) = \frac{H(r)}{h(r)} + \frac{rH'(r)}{h(r)} - \frac{rh'(r)H(r)}{h(r)^2};
\end{equation}
hence, to prove \autoref{Prop_NDerivativeLowerBound} we need to better understand $h'$ and $H'$.
This is what is achieved in the following.

\begin{prop}
  \label{Prop_hDerivative}
  The derivative of $h$ satisfies
  \begin{equation}
    \label{Eq_hDerivative}
    h'(r) = 2h(r)/r + \int_{\del B_r(x)} \del_r|\Psi|^2 + O(r)h(r)
  \end{equation}
  and
  \begin{equation}
    \label{Eq_hDerivative2}
    h'(r) = \(2+2\scN(r)+O(r^2)\)h(r)/r.
  \end{equation}
  Moreover,
  \begin{equation}
    \label{Eq_ErrorBound}
    \int_{B_r(x)} |\Psi|^2 \lesssim rh(r).
  \end{equation}
\end{prop}

\begin{proof}
  We proceed in four steps.

  \setcounter{step}{0}
  \begin{step}
    The identity \eqref{Eq_hDerivative} is clear if the metric is flat near $x$;
    the term $O(r)h(r)$ compensates for the metric possibly being non-flat.
  \end{step}

  \begin{step}\label{Step_ErrorBound0}
    $\int_{B_r(x)} |\Psi|^2 \lesssim (1+\scN(r))rh(r).$
  \end{step}

  Apply the following general fact
  \begin{equation*}
    \int_{B_r(x)} \rd(x,\cdot)^{-2}f^2 \lesssim r^{-1} \int_{\del B_r(x)} f^2 + \int_{B_r(x)} |\rd f|^2,
  \end{equation*}
  which can be proved using integration by parts and Cauchy--Schwarz, to $f=|\Psi|$ and use Kato's inequality.

  \begin{step}
    \label{Step_h'>0}
    $h'(r)>0$.
  \end{step}

  Use \autoref{Prop_IntegrationByParts} with $U=B_r(x)$ and $f=1$ to write
  \begin{equation}
    \label{Eq_HAsBoundaryIntegral}
    \int_{\del B_r(x)} \del_r|\Psi|^2 = 2H(r) + O(1)\int_{B_r(x)} |\Psi|^2.
  \end{equation}
  The estimate from \autoref{Step_ErrorBound0} implies
  \begin{equation*}
    h'(r) = \(1+O(r^2)\)(2+2\scN(r))h(r)/r
  \end{equation*}
  which is non-negative because $r \leq r_0$.

  \begin{step}
    Proof of \eqref{Eq_hDerivative2} and \eqref{Eq_ErrorBound}.
  \end{step}

  The bound \eqref{Eq_ErrorBound} follows directly from $h'(r)>0$.
  Using \eqref{Eq_ErrorBound} in \autoref{Step_h'>0} instead of the estimate from \autoref{Step_ErrorBound0} immediately implies \eqref{Eq_hDerivative2}.
\end{proof}

\begin{prop}
  \label{Prop_HDerivative}
  The derivative of $H$ satisfies
  \begin{multline}
    \label{Eq_HDerivative}
    H'(r)
    = \frac{1}{r} H(r) + \int_{\del B_r(x)} 2|\nabla^{A\otimes B}_r\Psi|^2 + \tan(\alpha)^{-2}|i(\del_r)\mu(\Psi)|^2 \\
    + O\bigl((1+\scN(r))h(r)\bigr).
  \end{multline}
  Here we think of $\mu(\Psi)$ as a $2$--form via \eqref{Eq_Lambda=su}.
\end{prop}

\begin{proof}
  The punctured ball $\dot B_{r_0}(x) := B_{r_0}(x)\setminus \set{x}$ is foliated by the surfaces $\del B_r(x)$ with normal vector field $\del_r$.
  According to \cite{Baer2005}*{Section 3} the restriction of the spin bundle on $\dot B_{r_0}(x)$ to $\del B_r(x)$ can be identified with the spin bundle on $\del B_r(x)$ and if $\tilde\gamma$, $\tilde\nabla$ and $\tilde\slD$ denote the Clifford multiplication, spin connection and Dirac operator on $\del B_r(x)$ respectively, then for $v \in T\del B_r(x)$:
  \begin{align*}
    \gamma(v)
    &= -\gamma(\del_r)\tilde\gamma(v), \\
    \nabla_v
    &= \tilde\nabla_v + \frac{e^{O(r^2)}}{2r}\tilde\gamma(v) \qand \\
    \slD
    &= \gamma(\del_r) (\nabla_r + \frac{e^{O(r^2)}}{r} - \tilde\slD).
  \end{align*}
  (If the metric on $B_{r_0}(x)$ is flat, then the mean curvature of $\del B_r(x)$ is $-\frac{1}{r}$.
  In general, there is a correction term; hence, the term $e^{O(r^2)}$.)
  In particular, $\slD \Psi = 0$ is equivalent to
  \begin{equation*}
    \tilde\slD \Psi = \nabla_r\Psi + \frac{e^{O(r^2)}}{r}\Psi.
  \end{equation*}

  For $\Psi$ a harmonic spinor on $B_r(x)$ we compute:
  \begin{align*}
    \int_{\del B_r(x)} |\nabla\Psi|^2 - |\nabla_r\Psi|^2
    &= \int_{\del B_r(x)} |\tilde\nabla\Psi + \frac{e^{O(r^2)}}{2r} \tilde\gamma(\cdot)\Psi|^2 \\
    &= \int_{\del B_r(x)} |\tilde\nabla\Psi|^2 - \frac{e^{O(r^2)}}{r} \langle\tilde\slD\Psi,\Psi\rangle + \frac{e^{O(r^2)}}{2r^2} |\Psi|^2 \\
    &= \int_{\del B_r(x)} |\tilde\nabla\Psi|^2 - \frac{e^{O(r^2)}}{r}\<\nabla_r\Psi,\Psi\> - \frac{e^{O(r^2)}}{2r^2} |\Psi|^2.
  \end{align*}
  Using the Weitzenböck formula~\eqref{Eq_Weitzenbock} the first term can be written as
  \begin{align*}
    \int_{\del B_r(x)} |\tilde\nabla\Psi|^2
    &= \int_{\del B_r(x)} \langle\tilde\nabla^*\tilde\nabla\Psi,\Psi\rangle \\
    &= \int_{\del B_r(x)} |\tilde\slD \Psi|^2 - \frac{e^{O(r^2)}}{2r^2} |\Psi|^2 \\
    &= \int_{\del B_r(x)} |\nabla_r\Psi|^2 + \frac{2e^{O(r^2)}}{r} \<\nabla_r\Psi,\Psi\> + \frac{e^{O(r^2)}}{2r^2}|\Psi|^2.
  \end{align*}
  This combined with \eqref{Eq_HAsBoundaryIntegral} and \eqref{Eq_ErrorBound} proves the asserted identity if $A$ and $B$ are product connections.

  If $A$ and $B$ are not the product connection, the computation is identical up to changes in notation \emph{and} in the Weitzenböck formula two additional terms appear.
  The first is
  \begin{equation*}
    -\int_{\del B_r(x)} \<F_A|_{\del B_r(x)},\mu(\Psi)\>
  \end{equation*}
  and the second can be estimated by $O(1)h(r)$.
  If $(e_1,e_2)$ is a local positive orthonormal frame of $T\del B_r(x)$, then the integrand in the above expression is
  \begin{equation*}
    \frac12\<F_A(e_1,e_2)[\tilde\gamma(e_1),\tilde\gamma(e_2)],\mu(\Psi)\>
    = \<F_A(e_1,e_2)\gamma(\del_r),\mu(\Psi)\>.
  \end{equation*}
  To better understand this term, observe that if $\{\cdot,\cdot\}$ denotes the anti-commutator, then
  \begin{equation*}
    \mu(\Psi) = \sum_{m} \frac12\{\mu(\Psi),\gamma_m\}\gamma_m
  \end{equation*}
  and $\<\gamma_m,\gamma_n\> = 2\delta_{mn}$.
  Using $F_A = \tan(\alpha)^{-2}\mu(\Psi)$ we can write the integrand as $\tan(\alpha)^{-2}$ times
  \begin{equation*}
    \frac12 |\{\mu(\Psi),\gamma(\del_r)\}|^2
    = |\mu(\Psi)|^2 - |i(\del_r)\mu(\Psi)|^2.
  \end{equation*}
  This proves \eqref{Eq_HDerivative} in general.
\end{proof}

\begin{proof}[Proof of \autoref{Prop_NDerivativeLowerBound}]
  Plug \eqref{Eq_hDerivative2} and \eqref{Eq_HDerivative} into \eqref{Eq_NDerivative} and use \eqref{Eq_HAsBoundaryIntegral} and \eqref{Eq_ErrorBound} to obtain
  \begin{align*}
    \scN(r)'
    &= \frac{2r}{h(r)} \int_{\del B_r(x)} |\nabla^{A\otimes B}_r \Psi|^2 + \tan(\alpha)^{-2} |i(\del_r)\mu(\Psi)|^2 \\
    &\quad - \frac{2r}{h(r)^2}\(\int_{\del B_r(x)} \<\nabla^{A\otimes B}_r\Psi,\Psi\>\)^2 \\
    &\quad + O(r)\(1+\scN(r)\).
  \end{align*}
  By Cauchy--Schwarz the sum of the first and the third term is positive.
  This completes the proof.
\end{proof}

\subsection{\texorpdfstring{$\scN$}{N} controls the growth of \texorpdfstring{$h$}{h}}
\label{Sec_NControlsGrotwthOfh}

\begin{prop}
  \label{Prop_hIntegralFormula}
  If $0 < s < r$, then
  \begin{equation}
    \label{Eq_hIntegralFormula}
    h(r) = e^{O(r^2)}\(r/s\)^2\exp\(2\int_s^r \scN(t)/t \, \rd t\) h(s).
  \end{equation}
\end{prop}

\begin{proof}
  \autoref{Eq_hDerivative2} can be written as
  \begin{equation*}
    (\log h(r))' = (2+2\scN(r))/r + O(r).
  \end{equation*}
  Integrating this yields \eqref{Eq_hIntegralFormula}.
\end{proof}

\begin{cor}
  \label{Cor_hGrowth}
  If $0 < s < r$, then
  \begin{equation*}
    h(s) \lesssim (s/r)^2 h(r).
  \end{equation*}
  In particular, if $h(s)$ is positive, then so is $h(r)$;
  moreover,
  $|\Psi|^2(x) \lesssim h(r)/r^2$.
\end{cor}

\begin{prop}
  \label{Prop_NControlsGrowthOfh}
  If $0 < s < r$, then
  \begin{equation*}
    e^{O(r^2)}(s/r)^{e^{O(r^2)}(2+2\scN(r))}h(r)
    \leq h(s)
    \leq e^{O(r^2)}(s/r)^{e^{O(r^2)}(2+2\scN(s))}h(r).
  \end{equation*}
\end{prop}

\begin{proof}
  Combine
  \begin{equation*}
      h(s) = e^{O(r^2)}\(s/r\)^2 \exp\(-2\int_s^r \scN(t)/t \, \rd t\) h(r)
  \end{equation*}
  with
  \begin{align*}
    \int_s^r \scN(t)/t \, \rd t
    &\leq \int_s^r \frac{1}{t}\(e^{O(r^2-t^2)}\scN(r)+O(r^2-t^2)\) \, \rd t \\
    &\leq -\(e^{O(r^2)}\scN(r)+O(r^2)\)\log(s/r)
  \end{align*} and
  \begin{equation*}
    -\(e^{O(r^2)}\scN(s)+O(r^2)\)\log(s/r) \leq \int_s^r \scN(t)/t \, \rd t.
  \end{equation*}
  The last two inequalities are consequences of \autoref{Prop_NMaxGrowth}.
\end{proof}

\subsection{\texorpdfstring{$|\Psi|(x)$}{|Psi|(x)} controls \texorpdfstring{$\scN$}{N}}

\begin{prop}
  \label{Prop_PsiXControlsN}
  If $0 < \omega \ll 1$ and
  \begin{equation*}
    s \lesssim_\omega \min\{1,|\Psi|^{1/\omega}(x)\},
  \end{equation*}
  then $\scN(s) \lesssim \omega$.
\end{prop}

\begin{proof}
  By \autoref{Prop_APrioriBounds}, $h(r) \lesssim r^2$ and, by \autoref{Cor_hGrowth}, $h_x(s)\gtrsim s^2 |\Psi|^2(x)$.
  From \autoref{Prop_NControlsGrowthOfh} it follows that for $s < r$
  \begin{align*}
    (r/s)^{e^{O(r^2)}2\scN(s)+O(r^2)} \leq c^2|\Psi|^{-2}(x);
  \end{align*}
  hence,
  \begin{equation*}
    \scN(s) \lesssim \frac{\log(c|\Psi|^{-1}(x))}{\log(r/s)} + O(r^2).
  \end{equation*}
  If $\sigma := c|\Psi|^{-1}(x) \leq 1$, then the first term is non-positive and setting $r=2\omega$ and $s = \omega$ yields the asserted bound.
  If $\sigma > 1$, set $r = \omega$ and $s = \omega c^{-1/\omega} |\Psi|^{1/\omega}(x) = \omega \sigma^{-1/\omega}$ to obtain
  \begin{equation*}
    \scN(s)
    \lesssim \omega + O(r^2)
    \lesssim \omega.
    \qedhere
  \end{equation*}
\end{proof}

\subsection{Dependence of \texorpdfstring{$\scN$}{N} on the base-point}

\begin{prop}
  \label{Prop_hDependenceOnBasePoint}
  For $x,y \in M$ and $r > 0$
  \begin{equation*}
    h_x(r) \lesssim \frac{2r+d(x,y)}{r} h_y\bigl(2r+d(x,y)\bigr).
  \end{equation*}
\end{prop}

\begin{proof}
  By \autoref{Cor_hGrowth} and \eqref{Eq_ErrorBound}
  \begin{equation*}
    rh_x(r)
    \lesssim  \int_{B_{2r}(x)} |\Psi|^2
    \leq \int_{B_{2r+d(x,y)}(y)} |\Psi|^2
    \lesssim \bigl(2r+d(x,y)\bigr) h_y\bigl(2r+d(x,y)\bigr).
    \qedhere
  \end{equation*}
\end{proof}

\begin{prop}
  \label{Prop_FrequencyCannotJumpToMuch}
  Suppose $x \in M$ and $r > 0$ are such that $\scN_x(10r) \leq 1$.
  If $y \in B_{r}(x)$, then $\scN_y(5r) \lesssim \scN_x(10r)$.
\end{prop}

\begin{proof}
  Since
  \begin{equation*}
    \scN_y(5r) = \frac{5r H_y(5r)}{h_y(5r)}
    \lesssim \scN_x(10r) \frac{h_x(10r)}{h_y(5r)},
  \end{equation*}
  it is key to control the latter quotient.
  Using \autoref{Prop_NControlsGrowthOfh} with $\scN_x(10r)\leq 1$ as well as \autoref{Prop_hDependenceOnBasePoint}
  \begin{equation*}
    h_x(10r) \lesssim h_x(r) \lesssim h_y(5r).
    \qedhere
  \end{equation*}
\end{proof}


text:
\section{Acknowledgments}
We would like to thank Reza Babanezhad, Aaron Mishkin, Nicolas Loizou and Nicolas Le Roux for helpful discussions. This research was partially supported by the Canada CIFAR AI Chair Program, a Google Focused Research award, an IVADO postdoctoral scholarship, and by the NSERC Discovery Grants RGPIN-2017-06936 and 2015-06068. Simon Lacoste-Julien is a CIFAR Associate Fellow in the Learning in Machines \& Brains program.