TITLE: Is gravitational acceleration truly independent of mass?
QUESTION [0 upvotes]: I am doing Newtonian Physics.
Correct me if I am wrong:
So two objects always exert equal forces on each other(Newtons Third).
So for example the same gravitational force that the earth exerts on a tennis ball, a tennis ball exerts on the earth.
We also know that the acceleration of gravity is irrespective of mass and on earth, it is 9.8 ms. Shouldn't the earth also accelerate to objects at 9.8 ms?
So my question is: Isn't the Earth constantly accelerating to all objects on it at the fast rate of 9.8ms? Should we notice the earth moving around like that?

REPLY [0 votes]: No. Newton's second law tells us that the acceleration profile obtained by application of a force $F$ to an object should be given by
$$a = \frac{F}{m}$$
where $m$ is the object's mass. This means it is inversely proportional to mass. Moreover, it is Newton's third law which tells us that there must be something opposite happening to the Earth from the ball, but it is not that the ball produces an equal and opposite acceleration, but rather an equal and opposite force. If the ball has a mass of, say, 100 g, or 0.1 kg, but the Earth has a mass of 6000 Yg, or $6 \times 10^{24}$ kg, then that means that, thanks to the inverse proportionality, while the ball will accelerate at 9.8 $\mathrm{m/s^2}$, the Earth will accelerate about $6 \times 10^{25}$ times less strongly. That equates to about 0.16 $\mathrm{ym/s^2}$, or yoctometres per second squared. Equivalently, that is $0.16\  \mathrm{(m/s)/Ys}$, or 0.16 metres per second per yottasecond, meaning it will take an entire yottasecond - about two million times the age of the Universe - for the Earth to be accelerated by this force to even 0.16 m/s of speed. Of course, the ball has already contacted the Earth's surface long, long before that point and so the mutual acceleration of the two has ceased.


TITLE: residue class rings - value calculations with modulo
QUESTION [0 upvotes]: computer science studies - residue class rings.
I have to calculate the following expression in $ \mathbb{Z_9}$

and the other one in $ \mathbb{Z_{16}}$

my question is how one should handle $-1, 23, 10$ in the "powers"?
are they really powers or do they have another meaning perhaps?
Thank you for your help

REPLY [1 votes]: Here we show the OP some techniques (tricks?) for finding the inverse elements in   $\mathbb{Z_{16}}$.
Since $15 \equiv -1 \pmod{16}$ we can factor $15$ and write
$\quad 3\cdot 5 \equiv -1 \pmod{16} \; \text{ iff } \; (-3) \cdot 5 \equiv 1 \pmod{16} \; \text{ iff } \; 5 \cdot 13 \equiv 1 \pmod{16}$
and
$\quad 3\cdot 5 \equiv -1 \pmod{16} \; \text{ iff } \; 3 \cdot (-5) \equiv 1 \pmod{16} \; \text{ iff } \; 3 \cdot 11 \equiv 1 \pmod{16}$
A good start - we've found the inverse of four residue primes. By working with our 'material', we'll find $[7]^{-1}$ by multiplying $[7]$ with known quantities and see if we transform it to $[1]$.
$\quad 7 \cdot 3 \equiv 21 \pmod{16}$
$\quad 7 \cdot 3 \equiv 5 \pmod{16}$
$\quad 7 \cdot 3 \cdot 13 \equiv 5 \cdot 13 \pmod{16}$
$\quad 7 \cdot (39) \equiv 1 \pmod{16}$
$\quad 7 \cdot 7 \equiv 1 \pmod{16}$
So $[7]^{-1} = 7$.
Here are the remaining invertible elements,
$\quad \large [9]^{-1} = \bigr([3]^{2}\bigr)^{-1}  = \bigr([3]^{-1}\bigr)^2 = [11^2] = [121] = [9]$
$\quad \large [15]^{-1} = [3\cdot5]^{-1} = [3^{-1} \cdot 5^{-1}] = [11 \cdot 13] = [15]$
(there is an easier way to find $[15]^{-1}$)
$\quad \large [1]^{-1} = [1]$
So $\mathbb{Z_{16}}$ has $8 = \phi(16)$ invertible elements.


TITLE: Let Z=E(X|Y). Show that Var(X) = Var(Z) + E(Var(X|Y)). So that in particular, we have Var(Z) $\le$ Var(X)
QUESTION [0 upvotes]: I am having trouble proving this:
Let Z=E(X|Y). Show that Var(X) = Var(Z) + E(Var(X|Y)). So that in particular, we have Var(Z) $\le$ Var(X)
This is what I have so far:
$Var(Z) = E(Z^2)-(EZ)^2$
$Var(Z) = E((E(X|Y)^2)-[E(E(X|Y))]^2$
$Var(Z) = E((E(X|Y)^2)-(EX)^2$
Then I am not sure where to go from here. Any help would be appreciated. Thank you very much.

REPLY [1 votes]: You're almost there. Use that $Var(X)  + (EX)^2 = E(X^2)$ (you can verify this using the definition of variance). Combine that with your work on the previous lines to obtain the desired identity.


TITLE: Find a simpler description of the ring
QUESTION [3 upvotes]: Find a simpler description of $\mathbb Q[x]/(x^3 + x)$.

Since $x^3 = -x$ in the quotient space, I know all the polynomials can be reduced to the form $a + bx + cx^2$ where $a,b,c\in\mathbb Q$.
I also know that since $x^3 + x = x(x^2 + 1)$ is reducible, the ideal is not prime or maximal, so the quotient space is not a domain.
Is this as simple as it gets, or is there some other simpler description of this ring?

REPLY [5 votes]: You're on the right track, but a little more can be said: using the Chinese remainder theorem,
$$ \mathbb{Q}[x]/(x^3+x)\simeq \mathbb{Q}[x]/(x)\times\mathbb{Q}[x]/(x^2+1)\simeq\mathbb{Q}\times\mathbb{Q}[i]$$
where $i^2=-1$.


TITLE: Fourier coefficients of $f^2$ for $f\in L_4([0,1])$
QUESTION [1 upvotes]: I'm trying to do the following problem:

For a function $f\in L_1([0,1]) $ recall that $$ \hat{f}(k)=\int_0^1
 e^{-2\pi i kx} f(x) dx.$$
Show that for $f\in L_4([0,1])$ the sequence  $$ c_n =\Sigma_{k+j=n}
 \hat{f}(k)\hat{f}(j)$$ converges to $0$ for $n\to \pm \infty$.

I'm thinking of relating $c_n$ with the Fourier coefficient of $f^2$ by usingFourier transform of convolution: $$\int _{0}^{1} f^2(x) e^{-2\pi ikx}= \frac{1}{2\pi} \int_0^1 \hat{f}(x) \hat{f} (2\pi k-x)dx$$ which converges to $0$ as $k\to \infty$. But I don't know if one can compare this coefficient with $c_n$. Can anyone give me some hints on how to solve this problem?

REPLY [0 votes]: HINT: what do you know about the convergence of $\sum \hat{f}(k)e^{2\pi i k x}$ to $f$?
HINT2: For $g \in L^a[0,1]$, with $1\leq b < a \leq \infty$ we have $g\in L^b[0,1]$ as a consequence of Jensen inequality or Holder inequality.


TITLE: how to rotate a Gaussian?
QUESTION [5 upvotes]: Lets suppose that we have a 2D Gaussian with zero mean and one covariance and the equation looks as follows
$$f(x,y) = e^{-(x^2+y^2)}$$
If we want to rotate in by an angle $\theta$, does it mean that we rotate the values $x$ and $y$ and then see how the Gaussian is rotated or do we actually rotate the graph of the function.
How this rotation actually be computed analytically and how the graph would look like. Is there any intuitive way of understanding.
How do we explain rotating a general function analytically and geometrically?
Thanks a lot

REPLY [7 votes]: If the covariance is the $2\times2$ identity matrix, then the density is
$$e^{−(x^2+y^2)/2}$$
multiplied by a suitable normalizing constant.  If $\begin{bmatrix} X \\ Y \end{bmatrix}$ is a random vector with this distribution, then you rotate that random vector by multiplying on the left by a typical $2\times 2$ orthogonal matrix:
$$
G \begin{bmatrix} X \\ Y \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \\  \sin\theta & \cos\theta \end{bmatrix}\begin{bmatrix} X \\ Y \end{bmatrix}.
$$
If the question is how to "rotate" the probability distribution, then asnwer is that it's invariant under rotations about the origin since it depends on $x$ and $y$ only through the distance $\sqrt{x^2+y^2}$ from the origin to $(x,y)$.
If you multiply on the left by a $k\times2$ matrix $G$, you have
$$
\mathbb{E}\left(G\begin{bmatrix} X \\ Y \end{bmatrix}\right) = G\mathbb{E}\begin{bmatrix} X \\ Y \end{bmatrix}
$$
and
$$
\operatorname{var}\left( G \begin{bmatrix} X \\ Y \end{bmatrix} \right) = G\left(\operatorname{var}\begin{bmatrix} X \\ Y \end{bmatrix}\right)G^T,
$$
a $k\times k$ matrix.  If the variance in the middle is the $2\times2$ identity matrix and $G$ is the $2\times 2$ orthogonal matrix given above, then it's easy to see that the variance is
$$
GG^T
$$
and that is just the $2\times 2$ identity matrix.  The only fact you need after that is that if you multiply a multivariate normal random vector by a matrix, what you get is still multivariate normal.  I'll leave the proof of that as an exercise.


TITLE: Solve the ODE $y''+4y'+3y = 4.5\sin(2t)$
QUESTION [0 upvotes]: Find the steady-state motion of the mass spring system modelled by the ODE $y''+4y'+3y = 4.5sin(2t)$
What I have tried:
Finding the general solution $$y^2+4y+3=0 \\
(y+1)(y+3) = 0 \\
\implies y_h = c_1e^{-x}+c_2e^{-3x}$$
To find $y_p$ we use $$y_p(t) = a\cos(\omega t) + b\sin(\omega t) \\ y'_p(t) = -a \omega \sin(\omega t) + b \omega \cos(\omega t) \\ y''_p(t) = -a \omega^2 \cos(\omega t) - b \omega^2 \sin(\omega t)$$
Plugging these into the equation:
$$-\omega^2(a\cos(\omega t) + b\sin(\omega t))+4\omega(-a\sin(\omega t) + b\cos(\omega t)) + 3(a\cos(\omega t) + b\sin(\omega t))=4.5\sin(2t)$$
$\omega=2$
$$-2^2(a\cos(2 t) + b\sin(2t))+8(-a\sin(2t) + b\cos(2t)) + 3(a\cos(2t) + b\sin(2t))=4.5\sin(2t)$$
Simplifying I get $$-a\cos(2t)-3b\sin(2t)-8a\sin(2t)+8b\cos(2t)=4.5\sin(2t)$$
However, I'm not sure on how to proceed from here. I thought I'd need to use the calculations for $a$ and $b$ for the undetermined coefficients, however I $a = -\frac{1}{65}, b = \frac{4}{65}$ when plugged in I do not get the answer which is $y_p(t) = -36/65 \cos(2t)-9/130 \sin(2t)$

REPLY [2 votes]: After your simplification you should end up with
$$-a\cos(2t)-b\sin(2t)-8a\sin(2t)+8b\cos(2t)=4.5\sin(2t)$$
careful because you had $-3b\sin\left(2t\right)$ and that was a little mistake. Now regrouping terms depending on $a$ and $b$ you get
$$
\left(-a+8b\right)\cos\left(2t\right)+\left(-8a-b\right)\sin\left(2t\right) = \frac{9}{2}\sin\left(2t\right)
$$
You can then identify giving you
$$
-a+8b = 0 \text{ and } -8a-b = \frac{9}{2}
$$
I let you find the value of $a$ and $b$ which correspond to your reference answer


text:
\begin{document}

\author{Peter Letavaj}
\thanks{The first author was supported by Young Researchers' Support Program of Slovak University of Technology in Bratislava.}
\author{Ladislav Mi\v{s}\'\i{k}}
\thanks{The second author was supported by the project P201/12/2351 of GA\v CR.}
\author{Martin Sleziak}
\thanks{The third author was supported by grant VEGA 1/0608/13.}
\keywords{asymptotic density, density measure, finitely additive measure, Ces\`{a}ro mean}
\subjclass[2010]{Primary: 11B05; Secondary: 28A12}

\email{\tt peterletavaj@googlemail.com, ladislav.misik@osu.cz, sleziak@fmph.uniba.sk}

\title{Extreme points of the set of density measures}

\date{\today}
\maketitle

\begin{abstract}
We study finitely additive measures on the set $\mathbb N$ which extend the asymptotic density (density measures). We show that there is a one-to-one correspondence between density measures and positive functionals in $\ell_\infty^*$, which extend Ces\`{a}ro mean. Then we study maximal possible value attained by a density measure for a given set $A$ and the corresponding question for the positive functionals extending Ces\`{a}ro mean.
Using the obtained results, we can find a set of functionals such that their closed convex hull in $\ell_\infty^*$ with weak${}^*$ topology is precisely the set of all positive functionals extending Ces\`{a}ro mean.
This also describes a set of density measures, from which all density measures can be obtained as the closed convex hull.
\end{abstract}

\section{Introduction}

Asymptotic density is a very natural way to measure size of subsets of $\NN$. One of the drawbacks of this concept is that there are sets that do not have asymptotic density. This problem leads us to studying finitely additive measures which extend the asymptotic density and are defined for all subsets of $\NN$. Such measures are called \emph{density measures} and they were studied by several authors, for example \cite{BFPR,MAHARAM,SALTIJD,VANDOUWEN}. Density measures (and other types of densities on $\NN$) have applications, for example, in theory of social choice \cite{FEYMAY,LAUWERS,SUREKHABHARAO}.

If $\mu$ is a density measure and a set $A\subseteq\NN$ has asymptotic density, then clearly $\mu(A)=d(A)$. But for sets not having asymptotic density, it might be interesting to find the maximal and minimal possible values of $\mu(A)$. This problem was posed in \cite{FEYPROBLEM}. Some questions concerning the possible values of density measures were also stated in \cite{VANDOUWEN}. Several expressions of extreme values of density measures are known, see \cite{SLEZZIMDENSRANGE}. In this paper we continue in the study of these extremal values and we find new possibilities how to express them.

Every finitely additive measure on $\NN$ induces a positive continuous linear functional on $\ell_\infty$ and by restricting such functional to characteristic sequences $\chi_A$ we obtain a finitely additive measure. This correspondence between measures and functionals is described in more detail in Section \ref{SECTMEASFUNCT}. Often it is easier to study the corresponding functionals instead of measures. We show that the functionals corresponding to density measures are precisely the positive functionals extending Ces\`{a}ro mean. Thus we are also interested in the extremal values of these functionals.

Another natural question pertaining to the density measures (and the corresponding functionals) is whether we can obtain them in some way from some set of simpler measures (simpler functionals). One possibility how to do this was proposed in \cite{LAUWERS}. Unfortunately, as shown in \cite{SLEZZIMDENSLEVY}, the expression given in \cite[p.49]{LAUWERS} does not entail all density measures.

Using the fact that we know the range of possible values of density measures together with results of \cite{JERISONCONVEX} we obtain some sets of positive functionals which give the set of positive functionals extending Ces\`{a}ro mean as their closed convex hulls in $\ell_\infty^*$ with weak${}^*$-topology. (In the other words, we find a set of functionals such that taking all pointwise limits of their convex combinations yields the set of all positive functionals extending Ces\`{a}ro mean.) This also gives a corresponding results for density measures.

The paper is organized as follows:

Section \ref{SECTPRELIM} contains a version of Krein-Milman theorem which will be needed later.
In Section \ref{SECTMEASFUNCT} we briefly describe the correspondence between the finitely additive measures and the positive functionals from $\ell_\infty^*$. We show that in this way  density measures can be viewed as the positive functionals extending Ces\`{a}ro mean.

In Section \ref{SECTDENSMEAS} we give  four different expressions of the range of density measures. We start by stating the result that these four values are equal to each other, recapitulating which of the equalities are already known. Then we show the remaining equality.

Section \ref{SECTFUNCTIONALS}  deals with analogous problem for functionals. Here we only give two different expressions of maximal possible value of a functional extending Ces\`{a}ro mean. The purpose of this section is to prepare results needed in the last section, where we use them to derive some facts about extreme points of the set of density measures and corresponding functionals.

In Section \ref{SECTEXTPOINTS} we describe a set of functionals such that the closed convex hull of this set is the set of all positive functionals extending the Ces\`{a}ro mean. We give consequences of this fact for the density measures.
To get such set of functionals we can use the expressions of the extreme values obtained in Section \ref{SECTFUNCTIONALS}. It suffices to find some functionals, which attain these values. In this way it is relatively easy to find a set generating all functionals with this property (see Remark \ref{REMFORFREE}). But we then show that the description of the density measures and the corresponding functionals can be further simplified and we show that there is a smaller set of functionals, which have simpler form, and they still generate all positive functionals extending Ces\`{a}ro mean.
From this result we get in Corollary \ref{CORCONVHULL} an analogous result for density measures. This can be considered as the main result of this paper, here we finally get a results about extreme points of the sets of all density measures.

\section{Preliminaries}\label{SECTPRELIM}

By $\NN$ we denote the set $\NN=\{1,2,3,\dots\}$ of all positive integers.

\subsection{Extreme points of subsets of $X^*$}

We will need the following result, which is a special case of \cite[Theorem 1]{JERISONCONVEX} applied to the space $X^*$ with the weak${}^*$ topology. The result from \cite{JERISONCONVEX} can be considered as a version of Krein-Milman theorem.
\begin{PROP}\label{PROPJERISON}
Let $X$ be a linear normed space and $C$ be a subset of $X^*$ which is convex and compact in the weak${}^*$-topology. Let $S\subseteq C$. The following conditions are equivalent:
\begin{enumerate}
\enu
  \item
  \begin{equation*}\label{EQJERISON}
    \sup_{\vp\in S} \vp(x) = \sup_{\vp\in C}\vp(x)
  \end{equation*}
    holds for each $x\in X$;
  \item $C=\cco(S)$, i.e., $C$ is the closed convex hull of $S$;
  \item the closure $\ol S$ of the set $S$ contains all extreme points of $C$.
\end{enumerate}
\end{PROP}

\section{Finitely additive measures and $\ell_\infty^*$}\label{SECTMEASFUNCT}

We say that a function $\Zobr\mu{\powerset{\NN}}{\RR}$ is a \emph{finitely additive measure on $\NN$} if $\mu(A\cup B)=\mu(A)+\mu(B)$ for any disjoint sets $A,B\subseteq\NN$. (Notice that, at this point, we allow the values of $\mu$ to be negative.)

There is a very natural correspondence between the finitely additive measures and linear continuous functionals $\Zobr f{\ell_\infty}{\RR}$. For  $f\in\ell_\infty^*$ we can obtain a measure by putting
$$\mu(A)=f(\chi_A).$$
The process of obtaining a functional from a given measure is similar to definition of Riemann integral. It uses the fact that any bounded sequence can be uniformly approximated by step sequences. (By a \emph{step sequence} we mean a sequence of the form $\sum_{i=1}^n c_i\chi_{A_i}$ for some $\Ldots c1n \in\RR$ and $\Ldots A1n\subseteq\NN$, i.e., a finite linear combination of characteristic sequences.)

More details about this construction can be found, for example, in \cite[Theorem 16.7]{CAROTHERS}, \cite[p.50, Example 1.19]{MORRISON}, \cite[Section 3]{VANDOUWEN}. Many texts in functional analysis provide also a more general version of this result dealing with dual of $\mc L_\infty(X,\mu)$.

It is relatively easy to see that positive functionals correspond to positive finitely additive measures and positive functionals such that $\norm f=1$ correspond to positive finitely additive probability measures.

From now on we will say briefly \emph{measure} instead of finitely additive positive probability measure.

We will study the measures which extend asymptotic density.
\begin{DEF}
For a set $A\subseteq\NN$ the \emph{upper} and \emph{lower asymptotic density} is defined by
$$\ol d(A)=\limsup_{n\to\infty} \frac{A(n)}n \qquad \text{and} \qquad \ul d(A)=\liminf_{n\to\infty} \frac{A(n)}n,$$
where $A(n)=\abs{A\cap\{1,2,\dots,n\}}$.

If $\ul d(A)=\ol d(A)$ then this common value is denoted by $d(A)$ and it is called the \emph{asymptotic density} of the set $A$.

We will denote the class of all subsets of $\NN$ possessing asymptotic density by $\DD$.

A finitely additive measure $\Zobr\mu{\powerset{\NN}}{[0,1]}$ is called a \emph{density measure} if
$$\mu(A)=d(A)$$
for every $A\in\DD$.

The set of all density measures will be denoted by $\DM$.
\end{DEF}

In the other words, density measures are precisely the measures which extend asymptotic density.
Density measures have been studied, for example, in \cite{BFPR,MAHARAM,SALTIJD,VANDOUWEN,SLEZZIMDENSLEVY,SLEZZIMDENSRANGE}.

Sometimes it is easier to work with the corresponding functionals instead of measures. Since we work with density measures, we need to know what class of functionals corresponds to such measures. We will show in Theorem \ref{THMDENSCES} that they are precisely the positive functionals which extend Ces\`{a}ro mean.

\begin{DEF}
Let $x\in\ell_\infty$. If the limit
$$C(x)=\limti n \frac{x_1+\dots+x_n}n$$
exists, then it is called the \emph{Ces\`{a}ro  mean} of the sequence $x$. We will denote the set of all bounded sequences that have Ces\`{a}ro mean by $\Ces$.

The set of all positive
functionals
$f\in\ell_\infty^*$ which \emph{extend Ces\`{a}ro mean,} i.e., which fulfill
$$f|_{\Ces}=C$$
will be denoted by $\Cesex$.
\end{DEF}

In the following proof we will need the notion of L\'evy group $\mc G$. The L\'evy group $\mc G$ consists of all permutations $\Zobr\pi{\NN}{\NN}$ such that
$$\limti n \frac{\abs{\{k; k \le n < \pi(k)\}}}n=0.$$
Several equivalent characterizations and some other facts about $\mc G$ can be found in \cite{BLUMLINGER}, \cite{BLUMOBA} or \cite{SLEZZIMDENSLEVY}.

\begin{THM}\label{THMDENSCES}
Let $\mu$ be a measure and $f\in\ell_\infty^*$ be the corresponding functional. The measure $\mu$  is a density measure if and only if $f$ extends Ces\`{a}ro mean.
\end{THM}

\begin{proof}
It is obvious that if $f$ extends Ces\`{a}ro mean then $\mu$ is a density measure, since we have $d(A)=C(\chi_A)$ whenever $A\in\DD$.

To prove the opposite direction we need
a characterization of $\DM$ and $\Cesex$
using invariance under
permutations from $\mc G$.

It is shown in \cite[Theorem 2.6]{SLEZZIMDENSLEVY} that density measures are precisely the $\mc G$-invariant measures.
By \cite[Theorem 2]{BLUMOBA} a positive functional with $\norm f=1$ extends Ces\`{a}ro mean if and only if it is $\mc G$-invariant.

So if $\mu$ is a density measure, then the corresponding functional is positive and $\norm f=1$. Since $\mu$ is $\mc G$-invariant, we also get that $f$ is $\mc G$-invariant for step sequences, simply because $$f(\pi(\chi_A))=f(\chi_{\inv\pi(A)})=\mu(\inv\pi(A))=\mu(A)=f(\chi_A)$$
and the same is true for any finite linear combination $\sum\limits_{i=1}^n \chi_{A_i}$ by linearity.

Using the fact that step sequences are dense in $\ell_\infty$ we can extend the $\mc G$-invariance to all sequences.
It suffices to notice that if we have step sequences $s_n=\sum\limits_{i\in F_n} \chi_{A_i}$ (where each $F_n$ is finite) and $s_n\to x$, then we have, for any $\pi\in\mc G$,
$$f(\pi(s_n))=f(s_n)$$
which implies $f(\pi(x))=f(x)$.
\end{proof}

\section{Extremal values of density measures}\label{SECTDENSMEAS}

For a given subset $A\subseteq\NN$, we are interested in the values
$$\lld(A)=\inf\{\mu(A); \mu\in\DM\} \qquad\text{and}\qquad \uud(A)=\sup\{\mu(A); \mu\in\DM\}.$$
In this section we will mention several equivalent expressions of $\uud(A)$ and $\lld(A)$.

For any $A\subseteq\NN$ and $\alpha\in\RR$ we define
$$A_\alpha(n)=\sum_{\substack{k\in A\\k\le n}}k^\alpha.$$
Notice that $A_0(n)=A(n)$.

It is relatively easy to see that $\NN_\alpha(n)\sim\frac{n^{\alpha+1}}{\alpha+1}$ for $\alpha>-1$. This observation is often useful when working with functions similar to $\udi(A)$, $\ldi(A)$ defined below.

In addition to $\uud(A)$ and $\lld(A)$ we will also use the following quantities.
\begin{align*}

\du(A)&=\inf\{d(B); B\supseteq A; B\in\DD\}\\
\udi(A)&=\limti\alpha \limsup_{n\to\infty} \frac{A_\alpha(n)}{\NN_\alpha(n)}\\
\udp(A)&=\lim_{\theta\to1^-} \limsup_{n\to\infty}  \frac{A(n)-A(\theta n)}{n-\theta n}
\end{align*}

We should show that the limits in the definitions of $\udi(A)$ and $\udp(A)$ really exist.
The existence of the limit appearing in the definition of $\udp(A)$ is shown in \cite{POLYA}.
For the existence of the limit used in the definition of $\udi(A)$, see Remark \ref{REMUDIEXISTS}.

We also define the lower versions of the last three densities $\dl(A)=\sup\{d(B); B\subseteq A; B\in\DD\}$, $\ldi(A)=\limti\alpha \liminf\limits_{n\to\infty} \frac{A_\alpha(n)}{\NN_\alpha(n)}$ and $\ldp(A)=\lim\limits_{\theta\to1^-} \liminf\limits_{n\to\infty}  \frac{A(n)-A(\theta n)}{n-\theta n}$.

There is an obvious correspondence between the lower and upper densities, $\uud(\NN\sm A)=1-\lld(A)$ and the analogous equalities are true for
$\du(A)$, $\udi(A)$ and $\udp(A)$.

The values $\udp(A)$ and $\ldp(A)$ were studied in a slightly more general setting in \cite{POLYA}. They are sometimes called (upper and lower) P\'olya density, see e.g. \cite{GREDENSSURV}.

The densities $\udi(A)$ and $\ldi(A)$ are related to $\alpha$-densities, which were studied
in \cite{FUCHSGA,GAGM}. The upper $\alpha$-density is defined as
$$\uda{\alpha} (A) = \limsup_{n\to\infty} \frac{A_\alpha(n)}{\NN_\alpha(n)},$$
the definition of $\lda{\alpha}(A)$ is analogous.

We will need the following facts, which follow from \cite[Theorem 3, Corollary 1]{RAJAGOPAL}.
\begin{THM}\label{THMRAJNEW}
Let
\begin{enumerate}
\enu
  \item If $-1\le\alpha\le\beta$ and then
    $$\lda{\beta}(A) \leq \lda{\alpha}(A) \leq \uda{\alpha}(A) \leq \uda{\beta}(A)$$
  \item If $\alpha>0$ and $A\in \DD$, then
    $$\uda{\alpha}(A) = d(A).$$
\end{enumerate}
\end{THM}

\begin{REM}\label{REMUDIEXISTS}
Note that from Theorem \ref{THMRAJNEW} we immediately get that the limit
$$\udi(A)=\limti\alpha \uda\alpha(A)$$
exists.
\end{REM}

Now we can formulate the main result of this section, in which we obtain several expressions for the extremal values of density measures.
\begin{THM}\label{THM4DENS}
For any $A\subseteq\NN$ we have
$$\uud (A)= \du(A)=\udi(A)=\udp(A)$$
and $\lld(A)=\dl(A)=\ldi(A)=\ldp(A).$
\end{THM}

Of course, it suffices to show this only for the upper densities or only for lower densities, because of the aforementioned correspondence.

In fact, with the exception of the part about $\udi(A)$ and $\ldi(A)$ the above theorem is only a summarization of known results.
The equality $\uud(A)=\du(A)$ was shown in \cite[Theorem 3]{SLEZZIMDENSRANGE}.  The equality $\uud(A)=\udp(A)$ can be obtained from (more general) result \cite[Satz VIII]{POLYA}.

The missing equality between $\udi(A)$ and the remaining expressions will be shown in Lemma \ref{LMDODATOK}. This answers \cite[Problem 1]{SLEZZIMDENSRANGE}.

Let us start by summarizing some results on $\udi(A)$ and $\uud(A)$ which will be needed in the proof.

\begin{LM}\label{LMSLEZZIM}
Let $A,B\subseteq\NN$.
\begin{enumerate}
\enu
  \item
        $$0 \le \lld(A) \leq \ldi(A) \leq \udi(A) \leq \uud(A)\le1$$
  \item For any $B$ there exists $A\subseteq B$ such that $A\in\DD$ and $d(A)=\lld(B)$.
  \item If $A\cap B=\emps$ and $A\in\DD$, then $$\lld(A\cup B)=d(A)+\lld(B).$$
  \item If $A\cap B=\emps$ and $A\in\DD$ then $$\ldi(A\cup B)=d(A)+\ldi(B).$$
\end{enumerate}
\end{LM}

\begin{proof}
The part (i) is shown in \cite[Corollary 6]{SLEZZIMDENSRANGE}. The second part is \cite[Proposition 2]{SLEZZIMDENSRANGE} and the third part is
\cite[Proposition 1]{SLEZZIMDENSRANGE}.

(iv) From the existence of the limit $d(A)=\limti n\frac{A(n)}{n}=\limti n \frac{\sum_{i=1}^n \chi_A(n)}n$ we get, for any $\alpha>0$,
$d_\alpha(A)=\limti n \frac{A_\alpha(n)}{\NN_\alpha(n)} =d(A)$ from Theorem \ref{THMRAJNEW}. Therefore
$$\lda{\alpha} (A\cup B) = \liminf_{n\to\infty} \frac{A_\alpha(n)+B_\alpha(n)}{\NN_\alpha(n)} =
\limti n \frac{A_\alpha(n)}{\NN_\alpha(n)} + \liminf_{n\to\infty} \frac{B_\alpha(n)}{\NN_\alpha(n)} = d(A) + \lda{\alpha}(B).$$
Taking limits $\alpha\to\infty$ on both sides gives $\ldi(A\cup B)=d(A)+\ldi(B)$.
\end{proof}

\begin{LM}\label{LMDODATOK}
For any set $A\subseteq\NN$ we have
$$\lld(A)=\ld_\infty(A).$$
\end{LM}

\begin{proof}
We already know $0 \le \lld(A) \leq \ldi(A) $ from Lemma \ref{LMSLEZZIM}, so it suffices to show the inequality $\ldi(A)\le\lld(A)$ for all $A\subseteq\NN$.

First let us assume that $\lld(A)=0$. We want to show that $\lda\infty(A)=0$.

We have
$$\lim_{\theta \to 1^-} \liminf_{n \to \infty} \frac{A(n) - A(\theta n)}{n - \theta n}=0.$$
Fix $\ve>0$. Then there exists $\theta_0<1$ such that
$$\liminf_{n \to \infty} \frac{A(n) - A(\theta n)}{n - \theta n}<\ve$$
whenever $\theta_0<\theta<1$. This implies that
\begin{equation}\label{EQTHETA}
  \frac{A(n) - A(\theta n)}{n - \theta n} < 2\ve
\end{equation}
for infinitely many $n$'s.

If $n$ fulfills (\ref{EQTHETA}) then
\begin{gather*}
A_\alpha(n) \leq A_\alpha(\theta n) + n^\alpha (A(n) - A(\theta n)) < A_\alpha(\theta n) +
n^{\alpha+1}(1-\theta) 2 \ve\\
\frac{A_\alpha(n)}{n^{\alpha+1}} \leq \frac{A_\alpha(\theta n)}{(\theta
n)^{\alpha+1}}\cdot\theta^{\alpha+1} +
(1-\theta)2\ve\\
\frac{A_\alpha(n)}{n^{\alpha+1}} \leq \frac{\NN_\alpha(\theta n)(\alpha+1)}{(\theta n)^{\alpha+1}} \cdot \frac{\theta^{\alpha+1}}{\alpha+1} + (1-\theta)2\ve
\end{gather*}

Since the above inequality holds for infinitely many $n$'s we get
\begin{equation}\label{INEQTHETA}
\lda{\alpha}(A) = \liminf_{n\to\infty} \frac{A_\alpha(n)(\alpha+1)}{n^{\alpha+1}} \leq \theta^{\alpha+1} +
(1-\theta)2\ve(\alpha+1)
\end{equation}
for any $\theta\in(\theta_0,1)$ and any $\alpha>0$.

Let us assume that, moreover,
\begin{equation}\label{EQTHETAALPHA}
    (1-\theta)(\alpha+1)=\frac1{\sqrt{\ve}}.
\end{equation}

Using \eqref{EQTHETAALPHA} we get from \eqref{INEQTHETA}
\begin{equation}\label{EQALPEPS}
    \lda{\alpha}(A) \leq \left(1-\frac1{(\alpha+1)\sqrt\ve}\right)^{\alpha+1} + 2\sqrt\ve.
\end{equation}
This inequality is valid for any $\alpha$ and
$\theta\in(\theta_0,1)$ that fulfill \eqref{EQTHETAALPHA}.

Now, if $\alpha\to\infty$ (note that this means $\theta\to1^-$,
hence we can always find $\theta\in(\theta_0,1)$ such that
\eqref{EQTHETAALPHA} holds), we get
\begin{equation}\label{EQINFEPS}
    \lda{\infty}(A) \leq e^{-\frac1{\sqrt\ve}} + 2\sqrt\ve.
\end{equation}
As the RHS tends to $0$ for $\ve\to0^+$ and $\ve>0$ can be
chosen arbitrarily, we finally get
$$\lda{\infty}(A)=0.$$

If we combine the above with the inequality $0 \le \lld(A) \leq \ldi(A)$, we have so far proved $\lld(A)=\ld_\infty(A)$ for the case that some of these values is zero.

By Lemma \ref{LMSLEZZIM}(ii) we know that
$\lld(A)=d(B)$
for some $B\subseteq A$, $B\in\DD$. For this set we have $\lld(A\sm B)=0$. Using other parts of Lemma \ref{LMSLEZZIM} we get that
$$\lld(A)=\lld(B\cup A\sm B) = d(B)+\lld(A\sm B)= d(B)+\ldi(A\sm B)=\ldi(A).$$
\end{proof}

From Theorem \ref{THM4DENS} and Theorem \ref{THMRAJNEW} we immediately have $$\lld(A) \le \ul d(A) \le \ol d(A) \le \uud(A).$$
Let us mention that these inequalities may be strict, as shown, for example, in  \cite[Exaple 3.4]{SLEZZIMDENSLEVY}, \cite[Sectoin 2]{SLEZZIMDENSRANGE}.

\section{Extremal values of positive functionals extending Ces\`{a}ro mean}\label{SECTFUNCTIONALS}

Next we turn to study the set $\Cesex$ of all positive functionals extending Ces\`{a}ro mean. From Theorem \ref{THMDENSCES} we already know that they correspond to density measures. Sometimes working with functionals instead of measures can be more convenient.

Again we want to find out the maximal and minimal possible value of such functionals for a given bounded sequence $x$.
We will study two functions which naturally correspond to $\uud$ and $\udp$. (It would be possible to define also analogous of the remaining densities from Theorem \ref{THM4DENS}.)

These results will be used in the following section to prove Corollary \ref{CORCONVHULL} describing a set containing all extreme points of the set of all density measures.

We will use the following sublinear functions defined on $\ell_\infty$
\begin{align*}
f_C(x)&=\sup\{f(x); f\in\Cesex\}\\
t(x)&=\lim_{\theta\to1^-} \limsup_{n\to\infty} \frac{\sum x_i\chi_{(\theta n,n]}(i)}{n(1-\theta)}
\end{align*}

The existence of the limit used in the definition of $t(x)$ is shown in Remark \ref{REMTEXISTS}.

\begin{REM}\label{REMDENSFUN}
Note that for $A\subseteq\NN$ we have $f_C(\chi_A)=\uud(A)$, $t(\chi_A)=\udp(A)$.
\end{REM}

We will introduce some notation which will be useful when proving some facts about the function $t(x)$.

Let us denote
\begin{align*}
\Te_{\theta,n}(x)&=\frac{\sum x_i\chi_{(\theta n,n]}(i)}{n(1-\theta)}\\
\Te_\theta(x)&=\limsup_{n\to\infty} \Te_{\theta,n}(x)
\end{align*}
When the sequence $x$ will be clear from the context, we will just write $\Te_{\theta,n}$ and $\Te_\theta$ instead.

This means that $t(x)=\lim\limits_{\theta\to1^-} \Te_\theta(x)$.

Now we can formulate and prove the following lemma, which will be useful in the proof of Proposition \ref{PROPTX}.

\begin{LM}\label{LMSLAVO2}
Let $x\in\intrv01^{\NN}$. Then there exists $\tilde x\in\{0,1\}^{\NN}$ such that $\tilde x-x\in\Ces$ and
\begin{gather*}
C(\tilde x-x)=0\\
f_C(x)=f_C(\tilde x)\\
\Te_{\theta}(x)=\Te_{\theta}(\tilde x) \text{ and } t(x)=t(\tilde x)
\end{gather*}
\end{LM}

\begin{proof}
Define $\tilde x_n$ by
$$\Pdots{\tilde x}1n = \dcc{\Pdots x1n}.$$
Then we have
$$\Pdots{\tilde x}1n \le \Pdots x1n \le \Pdots{\tilde x}1n+1,$$
which implies $C(\tilde x-x)=0$. From this we immediately get $f_C(x)=f_C(\tilde x)$.

We also have
$$\sum x_i\chi_{(\theta n,n]}(i) = \sum_{i=1}^n x_i - \sum_{i=1}^{\dcc{\theta n}} x_i,$$
which implies $\abs{\sum x_i\chi_{(\theta n,n]}(i) - \sum \tilde x_i\chi_{(\theta n,n]}(i)}\le 2$ and, consequently,
$\Te_{\theta}(x)=\Te_{\theta}(\tilde x)$ and $t(x)=t(\tilde x)$.
\end{proof}

\subsection{Basic properties of $f_C(x)$}

Let us mention some basic properties of the function $f_C(X)$. Proofs of these facts are easy, so they will be omitted.

\begin{LM}\label{LMFC}
\begin{align*}
(\forall x,y\in\ell_\infty)\,\,& f_C(x+y)\le f_C(x)+f_C(y)\\
(\forall x\in\ell_\infty)(\forall c>0)\,\,& f_C(cx)=cf_C(x)\\
(\forall x\in\ell_\infty)(\forall y\in\Ces)\,\,& f_C(x+y)=f_C(x)+C(y)\\
(\forall x\in\Ces)\,\,& f_C(x)=C(x)\\
(\forall x,y\in\ell_\infty)\,\,& x-y\in\Ces \land C(x-y)=0 \Ra f_C(x)=f_C(y)\\
(\forall x,y)\,\,& x\le y \Ra f_C(x)\le f_C(y)
\end{align*}
\end{LM}

\subsection{Function $t(x)$}

\begin{REM}\label{REMTEXISTS}
From \cite{POLYA} we know that the limit in the definition of $t(x)$ exists for sequences from $\{0,1\}^{\NN}$.
Using Lemma \ref{LMSLAVO2} we get the existence of this limit for any sequences in $\intrv01^{\NN}$.

It is relatively easy to show that $\Te_\theta(cx)=c\Te_\theta(x)$ for $c>0$ and $\Te_\theta(x+\ol c)=c+\Te_\theta(x)$ for any constant $c$. Once we know this, we get the existence of this limit for all bounded sequences.

In fact, the proof from \cite{POLYA} could be modified so that it works for any bounded sequence.
\end{REM}

Now we can prove the main result of this section.

\begin{PROP}\label{PROPTX}
For any $x\in\ell_\infty$ we have
$$t(x)=f_C(x).$$
\end{PROP}

\begin{proof}
We know from Theorem \ref{THM4DENS} that $t(\chi_A)=f_C(\chi_A)$ for any $A\subseteq\NN$. This yields $t(\tilde x)=f_C(\tilde x)$ for any $\tilde x\in\{0,1\}^{\NN}$ (see Remark \ref{REMDENSFUN}).

Now from Lemma \ref{LMSLAVO2} we have for any $x\in\intrv01^{\NN}$ that there is a sequence $\tilde x \in\{0,1\}^{\NN}$ such that
$$t(x)=t(\tilde x)=f_C(\tilde x)=f_C(x).$$
This proves the claim for any $x\in\intrv01^{\NN}$.

We can extend the validity of the above equality from $x\in\intrv01^{\NN}$ to $x\in\ell_\infty$ using the facts that $\Te_\theta(cx)=c\Te_\theta(x)$ for $c>0$ and $\Te_\theta(x+\ol c)=c+\Te_\theta(x)$ for any constant $c$, together with analogous claims for $f_C(x)$ (see Lemma \ref{LMFC}).
\end{proof}

\section{Extreme points}\label{SECTEXTPOINTS}

We have found the maximal value of $f(x)$ for functionals $f\in\Cesex$.
We will use Proposition \ref{PROPJERISON} to obtain some sets of functionals such that their closed convex hull is $\Cesex$.
This gives, in a sense, a description of the whole space $\Cesex$ using some simpler functionals. Namely we can obtain all functionals by taking the convex hull of this set and then the closure in the weak${}^*$-topology. (Closure in the weak${}^*$-topology means taking all limits of nets of functionals from this set, which converge pointwise.)

We could obtain some similar sets of functionals with this property from the results we have already shown so far, see Remark \ref{REMFORFREE}. The main purpose of this section is to obtain a smaller and simpler set which generates all functionals extending Ces\`{a}ro mean.
Using the correspondence between measures and functionals this yields a set of density measures, which generate all density measures, see Corollary \ref{CORCONVHULL}.

In the proof of Theorem \ref{THMSLAVOSUPFG}, which is one of the main results of this section, we will be working with some fixed sequence $x=\seq xn \in \intrv01^{\NN}$. It suffices to show this result for sequences with values in the interval $\intrv01$, since the result can be easily extended to all bounded sequences by scaling and adding constant sequence.

We can use $\Te_{\theta,n}$ from the definition of the function $t(x)$ not only for integers, but for positive real numbers, too.
For any real number $r>0$ and $\theta\in(0,1)$ we define:
\begin{align*}
\Sui{\theta}r(x)&=\sum_{i\in\NN} x_i\chi_{\intrvr{\theta r}r}(i)\\
\Te_{\theta,r}(x)&=\frac{\Sui{\theta}r(x)}{r(1-\theta)}\\
\Te_\theta(x)&=\limsup_{r\to\infty} \Te_{\theta,r}(x)\\
t(x)&=\lim\limits_{\theta\to1^-}\Te_\theta(x)
\end{align*}
We will often write just $\Sui{\theta}r$, $\Te_{\theta,r}$ and $\Te_\theta$ instead.

The resulting function $t(x)$ will be the same in both cases, whether we use integers or real numbers. (We will need to use both possibilities.)
To see that this is indeed the case, notice that if $\abs{r-r'}<1$ (e.g., if $r'=\dcc r$ or $r'=\hcc r$) then also $\abs{\theta r-\theta r'}<1$ and consequently
$$\abs{\Sui{\theta}r-\Sui{\theta}{r'}}\le 2.$$
Hence $$\limti r \left(\frac{\Sui{\theta}r}r-\frac{\Sui{\theta}{r'}}{r'}\right)=0$$
holds for any $\theta\in(0,1)$.

We will use the notion of the limit of a real sequence along an ultrafilter.
\begin{DEF}
If $\seq xn$ is a bounded real sequence and $\FF$ is an ultrafilter on $\NN$, then there exists a unique real number $L$ such that
$$\{n\in\NN; \abs{x_n-L}<\ve\}\in\FF$$
for each $\ve>0$. The number $L$ is called the $\FF$-limit of the sequence $\seq xn$ and it is denoted by $L=\Flim x_n$.
\end{DEF}
The most important property of $\FF$-limit is that it exists for every bounded sequence. For some other useful facts about $\FF$-limits we refer the reader to
\cite{ALEKSGLEBGORD}, \cite[8.23--8.26]{BALSTE}, \cite[Sections 2.3 and 4.5]{DIXMIERGT}, \cite[Section 11.2]{HRJECH}, \cite[Problem 17.19]{KOMJTOT}, \cite{KMSS}.

The symbols $\beta\NN$ and $\beta\NN^*$ denote the set of all ultrafilters and the set of all free ultrafilters on $\NN$, respectively.

\begin{THM}\label{THMSLAVOSUPFG}
For any sequence $\theta_k\in(0,1)$ such that $\theta_k\to1^-$, any $x\in\ell_\infty$ and any free ultrafilter $\FF$ we have
$$t(x)=\sup_{\GG\in\beta\NN^*} \Flim_k \Glim_n \Te_{\theta_k,n}(x).$$
\end{THM}

\begin{proof}
Fix a sequence $x=(x_k)\in \intrv01^{\NN}$.

Choose any $L<H<t(x)$.

By the definition of $t(x)$ there exists an $\thenul\in(0,1)$ such that
$$\Te_\theta=\limsupti r \Te_{\theta,r}>H$$
for each $\theta\ge\thenul.$

This implies that the set $$\{n\in\NN; \Te_{\thenul,n} \ge H\}$$
is infinite.

Inductively we can choose an infinite subset $A=\{n_1<n_2<\dots\}$ such that $\frac{n_k}{n_{k+1}}<\thenul$.
We have
$$n\in A \qquad \Ra \qquad \Te_{\thenul,n}\ge H.$$

Using this set we can define a function $\Zobr\vp{\intrvl{\thenul}1}{\intrv01}$ by
$$\vp(\theta)=\liminf_{n\in A} \Te_{\theta,n}$$

This function is continuous. (The proof is postponed to Lemma \ref{LMVPCONT}.)

\underline{Case 1.} First we suppose that $(\forall \theta\in\intrvl{\thenul}1) (\vp(\theta)\ge H)$.
This means that
$$\liminf_{n\in A} \Te_{\theta,n}\ge H.$$ For every such $\theta$ and for any free ultrafilter $\GG$ containing the infinite set $A$ we get $$\Glim_n \Te_{\theta,n}\ge H\ge L.$$

\underline{Case 2.} If $\vp$ does not fulfill the above property, then there exists $\theo>\thenul$ such that $L<\vp(\theo)<H$. Let us denote $M=\vp(\theo)$ and
$$\thed=\inf\{\theta\in\intrvl{\thenul}1; \vp(\theta)\le M\}.$$
We have
$$\vp(\thed)=M$$
(by the continuity of $\vp$) and the definition of $M$ implies
$$\vp(\theta)>M$$
whenever $\thenul\le\theta<\thed$. (See Figure \ref{FIGFUNKCIA}.)

\begin{figure}
\begin{center}
\includegraphics{funkcia}
\end{center}
\caption{Illustration of $\theo$ and $\thed$ from the proof of Theorem \ref{THMSLAVOSUPFG}}\label{FIGFUNKCIA}
\end{figure}

Since $$M=\vp(\thed)=\liminf_{n\in A}\Te_{\thed,n},$$
there exists an infinite set $A'\subseteq A$ such that
\begin{gather*}
\lim_{n\in A'} \Te_{\thed,n} =\lim_{n\in A'}\frac{\Sui{\thed}n}{n(1-\thed)}=M\\
\intertext{or equivalently}
\lim_{n\in A'}\frac{\Sui{\thed}n}{n}=M(1-\thed)
\end{gather*}

For every $n\in A'$ and $\theta$ such that $\frac{\thenul}{\thed}\le\theta<1$
we get
\begin{gather}
\notag \Sui{\theta\thed}n=\Sui{\theta}{\thed{n}}+\Sui{\thed}n,\\
\frac{\Sui{\theta\thed}n}n=\frac{\Sui{\theta}{\thed{n}}}n+\frac{\Sui{\thed}n}n, \label{EQZLOM}
\end{gather}
(since $\intrvl{\theta\thed n}n = \intrvl{\theta\thed n}{\thed n} \cup \intrvl{\thed n}n$; see Figure \ref{FIGINTERVALY}.)

\begin{figure}
\begin{center}
\includegraphics{intervaly}
\end{center}
\caption{Division of the interval $\intrvr{\theta\thed n}n$}\label{FIGINTERVALY}
\end{figure}

The condition $\thenul \le \theta\thed < \thed$ implies $\vp(\theta\thed)\ge M$, i.e.,
\begin{align*}
\liminf_{n\in A'} \Te_{\theta\thed,n}  &\ge \liminf_{n\in A} \Te_{\theta\thed,n} \ge M\\
\liminf_{n\in A'} \frac{\Sui{\theta\thed}n}{n} &\ge M(1-\theta\thed)
\end{align*}

From \eqref{EQZLOM}
we get $\frac{\Sui{\theta}{\thed{n}}}n = \frac{\Sui{\theta\thed}n}n-\frac{\Sui{\thed}n}n$ and thus
\begin{gather*}
\liminf_{n\in A'} \frac{\Sui{\theta}{\thed{n}}}n = \liminf_{n\in A'} \frac{\Sui{\theta\thed}n}n-\lim_{n\in A'} \frac{\Sui{\thed}n}n \ge
M(1-\theta\thed)-M(1-\thed)=M\thed(1-\theta)\\
\liminf_{n\in A'} \frac{\Sui{\theta}{\thed{n}}}{\thed n(1-\theta)} \ge M
\end{gather*}

Now denote $$B=\{\thed a; a\in A'\}.$$ (Note that $B\subseteq\RR$.)

Since $B$ is precisely the set of all real numbers of the form $r=\thed n$ for $n\in A'$, this is equivalent to
\begin{align*}
\liminf_{r\in B} \frac{\Sui{\theta}r}{r(1-\theta)} &\ge M,\\
\liminf_{r\in B} \Te_{\theta,r} &\ge M.
\end{align*}

Now put $$\dcc B=\{\dcc b; b\in B\}.$$ For this set we have
$$\liminf_{n\in \dcc B} \Te_{\theta,n} \ge M.$$
(We have chosen the set $A$ in such way that for any two elements $m_1<m_2$ in $A$ we have $\frac{m_1}{m_2}<\thenul$. This implies that $\thed m_1 < m_1 < \thenul m_2 <\thed m_2$. Hence for any two different elements $m_1, m_2\in A'$, the corresponding elements $\dcc{\thed m_1}$ and $\dcc{\thed m_2}$ of $B$ will be different.)

This implies that for every free ultrafilter $\GG\ni\dcc{B}$ the inequalities
$$\Glim \Te_{\theta,n} \ge M \ge L$$
hold for each $\theta\in\intrvl{\frac{\thenul}{\thed}}1$.

\underline{Conclusion.} In both cases we have shown that there exists a free ultrafilter $\GG$ such that
$$\Glim \Te_{\theta,n} \ge L$$
for each $\theta$ close enough to $1$. Thus for any choice of $\seq\theta{k}$ such that $\theta_k\to1^-$ and any free ultrafilter $\FF$
$$\Flim_k \Glim_n \Te_{\theta_k,n} \ge L.$$
Since $L$ can be chosen arbitrarily close to $t(x)$, we get
$$\Flim_k \Glim_n \Te_{\theta_k,n} \ge t(x).$$
\end{proof}

\begin{LM}\label{LMVPCONT}
The function $\vp(\theta)=\liminf\limits_{n\in A} \Te_{\theta,n}$ is continuous for any infinite set $A\subseteq\NN$.
\end{LM}

\begin{proof}
Note that we have for any $\theta\in(0,1)$, $r>0$ and $0<\delta<1-\theta$.
\begin{gather*}
\Sui{\theta}r=\sum x_i \chi_{\intrvr{(\theta+\delta)r}r} +\sum x_i \chi_{\intrvr{\theta r}{(\theta+\delta)r}}\\
\Sui{\theta}r=\Sui{(\theta+\delta)}r+\sum x_i \chi_{\intrvr{\theta r}{(\theta+\delta)r}}\\
\Te_{\theta,r}=\frac{\Sui{\theta}r}{r(1-\theta)}=\frac{\Sui{(\theta+\delta)}r}{r(1-\theta)}+\frac{\sum x_i \chi_{\intrvr{\theta r}{(\theta+\delta)r}}}{r(1-\theta)}\\
\Te_{\theta,r}=\Te_{\theta+\delta,r}\frac{1-(\theta+\delta)}{1-\theta}+\frac{\sum x_i \chi_{\intrvr{\theta r}{(\theta+\delta)r}}}{r(1-\theta)}\\
\Te_{\theta,r}=\Te_{\theta+\delta,r}-\frac{\delta}{1-\theta}\Te_{(\theta+\delta),r}+\frac{\sum x_i \chi_{\intrvr{\theta r}{(\theta+\delta)r}}}{r(1-\theta)}\\
\absl{\Te_{\theta,r}-\Te_{\theta+\delta,r}}\le \frac{\delta}{1-\theta} \norm{x} + \frac{\delta}{(1-\theta)} \norm{x}
\end{gather*}

From this we get
$$\absl{\liminf_{n\in A}\Te_{\theta+\delta,n}-\liminf_{n\in A}\Te_{\theta,n}}\le \frac{2\delta}{1-\theta} \norm{x},$$
which implies the continuity of $\varphi$.
\end{proof}

\begin{LM}\label{LMFGINCESEX}
Let $\FF,\GG\in\beta\NN^*$, and $\theta_k\to1^-$. Let us define $\Zobr f{\ell_\infty}{\RR}$ by
$$f(x)=\Flim_k \Glim_n \Te_{\theta_k,n}(x).$$
Then $f\in\Cesex$, i.e., $f$ is a positive linear functional on $\ell_\infty$ which extends Ces\`{a}ro mean.
\end{LM}

\begin{proof}
It is clear
that $f(x)$ defined above is a positive linear functional on $\ell_\infty$.

Now let $x\in\Ces$. Then we have $t(x)=\lim\limits_{\theta\to1^-} \limsup\limits_{n\to\infty} \Te_{\theta,n}(x)=C(x)$ and also
$C(x)=-C(-x)=-t(-x)=\lim\limits_{\theta\to1^-} \liminf\limits_{n\to\infty} \Te_{\theta,n}(x)$. For each $k$ we get
$$\liminf\limits_{n\to\infty} \Te_{\theta_k,n}(x) \le \Glim_n \Te_{\theta_k,n}(x) \le \limsup\limits_{n\to\infty} \Te_{\theta_k,n}(x)$$
which yields
$$C(x)\le \Flim_k \Glim_n \Te_{\theta_k,n}(x) \le C(x).$$
So we have $f(x)=C(x)$.
\end{proof}

\begin{THM}\label{THMCONVHULL}
Let $\theta_k\in(0,1)$ be a sequence such that $\theta_k\to1^-$ and $\FF$ be any free ultrafilter $\FF$. Let us define
$$S=\{f_{\GG}; \GG\in\beta\NN^*\}$$
where $\Zobr {f_{\GG}}{\ell_\infty}{\RR}$ is defined by
$$f_{\GG}(x)=\Flim_k \Glim_n \Te_{\theta_k,n}(x).$$
We consider $S$ as a subset of the space $\ell_\infty^*$ endowed with the weak${}^*$ topology.

Then $$\ccohull{S}=\Cesex,$$
i.e., the closed convex hull of $S$ is the set of all positive functionals on $\ell_\infty$ extending Ces\`{a}ro mean.
Or, equivalently, $\ol{S}$ contains all extreme points of $\Cesex$.
\end{THM}

\begin{proof}
The set $\Cesex$ is a subset of the unit ball of $\ell^*$. It is closed in the weak${}^*$ topology. Thus by Banach-Alaoglu theorem it is compact.

Lemma \ref{LMFGINCESEX} implies that each $\vp\in S$ is indeed an element of $\Cesex$ and by Theorem \ref{THMSLAVOSUPFG} we have
$$\sup_{\vp\in S} \vp(x)=\sup_{\vp\in\Cesex} \vp(x).$$
So from Proposition \ref{PROPJERISON} we get that $\ccohull{S}=\Cesex$ and $\ol S$ contains all extreme points of $\Cesex$.
\end{proof}

Of course, we can work with finitely additive measures instead of the corresponding functionals. The weak${}^*$ topology is then determined by the condition that a net $\mu_\sigma$ of measures converges to $\mu$ if and only if $\mu_\sigma(A)$ converges to $\mu(A)$ for each $A\subseteq\NN$.
\begin{COR}\label{CORCONVHULL}
Let $\theta_k\in(0,1)$ be a sequence such that $\theta_k\to1^-$ and $\FF$ be any free ultrafilter $\FF$. Let us define
$$S=\{\mu_{\GG}; \GG\in\beta\NN^*\}$$
where $\mu_{\GG}$ is defined by
$$\mu_{\GG}(A)=\Flim_k \Glim_n \Te_{\theta_k,n}(\chi_A).$$

Then $$\ccohull{S}=\DM,$$
i.e., the closed convex hull of $S$ is the set of all density measures.
Or, equivalently, $\ol{S}$ contains all extreme points of $\DM$.
\end{COR}

\begin{REM}\label{REMFORFREE}
It is easy to show that any functional of the form
$$f(x)=\Flim_k \Gklim_n \Te_{\theta_k,n}(x)$$
for $\FF,\GG_k\in\beta\NN^*$ is also a positive functional extending Ces\`{a}ro mean.

For any given $x$ and $(\theta_k)$ there exists a sequence $\GG_k$ of free ultrafilters such that $\limsup\limits_{n\to\infty} \Te_{\theta_k,n}=\Gklim_n \Te_{\theta_k,n}$.

From this we can immediately see that the set of all functionals of this form has the same properties as the set $S$ from Theorem \ref{THMCONVHULL}. But Theorem \ref{THMCONVHULL} is a stronger result than this, we do not need a sequence of ultrafilters, we have the same ultrafilter $\GG$ for each $k$.
\end{REM}

\bibliographystyle{plain}

\bibliography{martin}

\end{document}

config: arxiv


TITLE: What is an irreducible element in $\Bbb{Z}_6[x]$?
QUESTION [3 upvotes]: What is an irreducible element in $\Bbb{Z}_6[x]$?

This was a problem on our final and no one knew how to solve it. Does anyone have a method for solving this?

REPLY [5 votes]: Claim. Assume that $\Bbb Z_m=\Bbb Z/m\Bbb Z$.  The polynomial $f(x)\in\Bbb Z_6[x]$ is irreducible if and only if exactly one of these is true:
$(a)$ $f(x)$ is irreducible over $\Bbb Z_2$ and $f(x)\equiv \pm1\pmod{3}$ or
$(b)$ $f(x)$ is irreducible over $\Bbb Z_3$ and $f(x)\equiv 1\pmod{2}$.

Suppose that $f(x)\in \Bbb Z_6[x]$ is irreducible.  Then, $f(x)$ is either irreducible or invertible over $\Bbb{Z}_2$, and over $\Bbb{Z}_3$.  If $f(x)$ is invertible in both $\Bbb Z_2$ and $\Bbb Z_3$, then $f(x)$ is one of the constant polynomials $\pm1$, which are invertible (and not irreducible).  This is a contradiction, so $f(x)$ must either be irreducible over $\Bbb Z_2$ or over $\Bbb Z_3$.
If $f(x)$ is invertible in neither $\Bbb Z_2$ nor $\Bbb Z_3$, then we can solve for $$u(x)\equiv 1\pmod{2}\ \ \  \wedge\ \ \  u(x)\equiv f(x)\pmod 3$$
and
$$v(x)\equiv f(x)\pmod{2}\ \ \ \wedge \ \ \ v(x)\equiv 1\pmod{3}$$
for $u(x),v(x)\in\Bbb{Z}_6[x]$.  These $u(x)$ and $v(x)$ are non-invertible over $\Bbb Z_6$ (since $u(x)$ is non-invertible modulo $3$, and $v(x)$ is non-invertible modulo $2$).  However, $f(x)=u(x)\cdot v(x)$ in $\Bbb Z_6[x]$, which is a contradiction.  Therefore, either $(a)$ or $(b)$ holds, but not both.
Conversely, suppose that $(a)$ holds.  If $f(x)=p(x)\cdot q(x)$ for some $p(x),q(x)\in \Bbb Z_6[x]$, then reduce $p(x)$ and $q(x)$ modulo $2$ and $3$ respectively.  As $f(x)$ is irreducible mod $2$, $(p,q)=(f,1)$ or $(p,q)=(1,f)$ modulo $2$.  Wlog, $p=f$ and $q=1$.   As $f(x)\equiv \pm 1\pmod{3}$, $p(x)$ and $q(x)$ modulo $3$ are constants $\pm 1$.  Thus, $q(x)\equiv 1\pmod{2}$ and $q(x)\equiv -1\pmod{3}$. Therefore, $q(x)= \pm 1$ in $\Bbb Z_6[x]$.  That is, $q(x)$ is constant, and so $f(x)$ is irreducible.
Finally, suppose that $(b)$ holds.  If $f(x)=p(x)\cdot q(x)$ for some $p(x),q(x)\in \Bbb Z_6[x]$, then reduce $p(x)$ and $q(x)$ modulo $2$ and $3$ respectively.  As $f(x)$ is irreducible mod $3$, $(p,q)=(f,1)$ or $(p,q)=(1,f)$ modulo $3$, up to sign swapping.  Wlog, $p=f$ and $q=1$.   As $f(x)\equiv 1\pmod{2}$, $p(x)$ and $q(x)$ modulo $2$ equal the constant $1$.  Thus, $q(x)\equiv 1\pmod{2}$. Therefore, $q(x)= 1$ in $\Bbb Z_6[x]$.  That is, $q(x)$ is constant, and so $f(x)$ is irreducible.
Examples.  The polynomial $f(x)=3x+1$ fits $(a)$, so it is irreducible in $\Bbb{Z}_6[x]$.   The polynomial $f(x)=2x+1$ fits $(b)$, so it is irreducible in $\Bbb{Z}_6[x]$.


TITLE: topology basis, euclidean topology
QUESTION [1 upvotes]: Let $k$ be a natural number ($k\in\{0,1,2,...\}$). Let $\mathcal{B}_k$ be the family of subsets of $\mathbb{R}$ consisting of $\mathbb{R}$ and all the open intervals $(a,b)$ which contain at most $k$ integers (when $k=0$, that means: intervals $(a,b)$ that contain no integers). Show that
a. $\mathcal{B}_k$ is a topology basis on $\mathbb{R}$.
b. for $k\geq 1$, the topology induced by $\mathcal{B}_k$ on $\mathbb{R}$ is the euclidean topology.
Can somebody help me? Thank you very much!

REPLY [0 votes]: Let $\tau$ be the Euclidean topology and $\tau'$ be the topology induced by $\mathcal{B}_k$. The collection of all open intervals in $\mathbb{R}$ is a basis for $\tau$. To show $\tau=\tau'$ it suffices to show

For every $x \in \mathbb{R}$ and $B \in \mathcal{B}_k$ containing $x$, there is an open interval $I \subseteq \mathbb{R}$ such that $x \in I \subseteq B$.
For every $x \in \mathbb{R}$ and $I \subseteq \mathbb{R}$ containing $x$, there is a $B \in \mathcal{B}_k$ such that $x \in \mathcal{B}_k \subseteq I$.

The first bullet point should be immediate. For the second, notice that if $I$ contains $0$ or $1$ integers the result is immediate. Otherwise you need to show that there is a subinterval of $I$ containing $x$ which contains $0$ or $1$ integers. As suggested in the other answer, consider whether $x$ is an integer or not, and in both cases show that there are arbitrarily small intervals centered at $x$ which contain $0$ or $1$ integers. Since these intervals can be made arbitrarily small, you can certainly find one contained in $I$.


text:
\section{Convergence theory}\label{sec:convergence}

Using the viewpoint of \SNR in Sec.~\ref{sec:SGD}, we adapt proof techniques of \SGD to establish the global convergence of \SNR.

\subsection{Smoothness property}

In our upcoming proof, we rely on the following type of smoothness property thanks to our \SGD reformulation~\eqref{eq:sgdreform}.

\begin{lemma}\label{lem:smooth}
For every $x\in\R^p$ and any realization $\mS \sim \cD_x$ associated with any distribution $\cD_x$,

\begin{align}\label{eq:1smooth}
\frac{1}{2}\|\nabla f_{\mS, x}(x)\|^2 =  f_{\mS, x}(x).
\end{align}
\end{lemma}

\begin{proof}
Turning to the definition of $f_{\mS,x}$ in~\eqref{eq:fk}, we have that

\begin{align*}
\norm{\nabla f_{\mS,x}(x)}^2 &\overset{\eqref{eq:SGDgrad}}{=} \norm{DF(x)\mH_{\mS}(x)F(x)}^2
= F(x)^\top \mH_{\mS}(x)^\top DF(x)^\top DF(x)\mH_{\mS}(x) F(x) \\
&= F(x)^\top\mH_{\mS}(x)F(x) = 2f_{\mS,x}(x),
\end{align*}
where we used the property
 $ \mM^\dagger \mM\mM^\dagger = \mM^\dagger$ with $\mM = \mS^\top DF(x)^\top DF(x) \mS$ to establish that

$\mH_{\mS}(x)^\top DF(x)^\top DF(x)\mH_{\mS}(x) \overset{\eqref{eq:Hk}}{=} \mH_{\mS}(x).$

\end{proof}

This is not a standard smoothness property.
Indeed, since  $\nabla f_{\mS,x}(x^*) =0 $ and $ f_x(x^*) =0$,
we have that~\eqref{eq:1smooth} implies that

\begin{eqnarray*}
\norm{\nabla f_{\mS,x}(x) -\nabla f_{\mS,x}(x^*) }^2 \leq 2 (f_{\mS, x}(x) -f_{\mS,x}(x^*)),
\end{eqnarray*}
which is usually a consequence of assuming that $f_{\mS, x}(x) $ is convex and $1$--smooth (see Theorem 2.1.5 and Equation 2.1.7 in~\cite{NesterovBook}).

Yet in our case, eq.~\eqref{eq:1smooth} is a direct consequence of the definition of $f_{\mS,x}$ as opposed to being an extra assumption. This gratuitous property will be key in establishing a global convergence result.

\subsection{Convergence for star-convex}

We use the shorthand $f_{k}(x) \eqdef f_{x^k}(x)$, $f_{\mS_k,k} \eqdef f_{\mS_k,x^k}$ and $\EE{k}{ \cdot } \eqdef \E{ \cdot  \mid x^k}$.
Here we establish the global convergence of \SNR by supposing that $f_k$ is \emph{star-convex} which is a large class of nonconvex functions that includes convexity as a special case~\cite{Nesterov2006cubic,LeeV16,zhou2018sgd,hinder2020nearoptimal}.

\begin{assumption}[Star-Convexity]

\label{ass:convex}
Let $x^*$ satisfy Asm.~\ref{ass:zero}, i.e.\ let $x^*$ be a solution to~\eqref{eq:main}. For every $x^k$ given by Alg.~\ref{algo:SkeNeR} with $k \in \N$, we have that

\begin{eqnarray}\label{eq:cvx}
f_k(x^*) &\geq& f_k(x^k) + \dotprod{\nabla f_k(x^k), x^* - x^k}.
\end{eqnarray}
\end{assumption}

We now state our main theorem.
\begin{theorem} \label{theo:convex}
Let $x^*$ satisfy Asm.~\ref{ass:convex}. If $0 < \gamma < 1$,
then

\begin{align}
\E{\min_{t=0, \ldots, k-1} f_t(x^t)}
\leq \frac{1}{k}\sum_{t=0}^{k-1}\E{f_t(x^t)}
\leq \frac{1}{k}\frac{\norm{x^0-x^*}^2}{2\gamma\left(1 - \gamma\right)}. \label{eq:convminEf}
\end{align}
Written in terms of $F$ and for $\gamma =1/2$ the above gives

\[\E{\min_{t=0, \ldots, k-1}\norm{F(x^t)}_{\E{\mH_{\mS}(x^t)}}^2} \quad \leq \quad \frac{4\norm{x^0-x^*}^2}{k}.\]

Besides, if the stochastic function $f_{\mS,x}(x)$ is star-convex along the iterates $x^k$

, i.e.\

\begin{eqnarray}\label{eq:cvx-S-star}
 f_{\mS_k,x^k}(x^*) &\geq& f_{\mS_k,x^k}(x^k) + \dotprod{\nabla f_{\mS_k,x^k}(x^k), x^* - x^k}
\end{eqnarray}
for all $\mS_k \sim\cD_{x^k}$, then the iterates $x^k$ of \SNR~\eqref{eq:update} are bounded with

\begin{eqnarray}\label{eq:bounded-det}
\norm{x^k - x^*} &\leq& \norm{x^0 - x^*}.
\end{eqnarray}
\end{theorem}

\begin{proof}
Let $t \in  \{0, \ldots,  k - 1 \}$ and $\delta_t \eqdef x^t-x^* $.

We have that

\begin{eqnarray}
\EE{t}{\norm{\delta_{t+1}}^2} &\overset{\eqref{eq:SGD}}{ =}& \EE{t}{\norm{x^t - \gamma \nabla f_{\mS_t,t}(x^t) - x^*}^2} \nonumber\\
&=& \norm{\delta_{t}}^2 - 2\gamma \dotprod{\delta_{t}, \nabla f_t(x^t)} + \gamma^2\EE{t}{\norm{\nabla f_{\mS_t,t}(x^t)}^2} \nonumber\\
&\overset{\eqref{eq:cvx}}{\leq}& \norm{\delta_{t}}^2 - 2\gamma (f_t(x^t) - f_t(x^*))+ \gamma^2\EE{t}{\norm{\nabla f_{\mS_t,t}(x^t)}^2} \nonumber \\
&\overset{ \eqref{eq:1smooth}}{ = }& \norm{\delta_{t}}^2 - 2\gamma\left(1 - \gamma\right)(f_t(x^t) -f_t(x^*))  \nonumber\\
&\overset{f_t(x^*) = 0}{=}& \norm{\delta_{t}}^2 - 2\gamma\left(1 - \gamma\right)f_t(x^t). \label{EEt}
\end{eqnarray}
Taking total expectation  for all $t \in \{0, \ldots,  k - 1 \}$, we have that

\begin{eqnarray}
\E{\norm{\delta_{t+1}}^2} &\leq& \E{\norm{\delta_{t}}^2} - 2\gamma\left(1 - \gamma\right)\E{f_t(x^t)}. \label{eq:Etotal}
\end{eqnarray}

Summing both sides of~\eqref{eq:Etotal} from $0$ to $k-1$ gives

\begin{eqnarray*}
\E{\norm{x^k-x^*}^2} + 2\gamma\left(1 - \gamma\right)\sum_{t=0}^{k-1}\E{f_t(x^t)} &\leq& \norm{x^0-x^*}^2.
\end{eqnarray*}
Dividing through by $2\gamma\left(1 - \gamma\right) >0$ and by $k$, we have that

\[\E{\min_{t=0, \ldots, k-1}f_t(x^t)}  \leq  \min_{t=0, \ldots, k-1} \E{f_t(x^t)}  \leq  \frac{1}{k}\sum_{t=0}^{k-1}\E{f_t(x^t)}  \leq  \frac{1}{k}\frac{\norm{x^0-x^*}^2}{2\gamma\left(1 - \gamma\right)},\]
where in the most left inequality we used Jensen's inequality.

Finally, if~\eqref{eq:cvx-S-star} holds, then we can repeat the steps leading up to~\eqref{EEt} without the conditional expectation, so that

\begin{eqnarray*}
\norm{\delta_{t+1}}^2 &\overset{\eqref{eq:SGD}+\eqref{eq:cvx-S-star}+\eqref{eq:1smooth}}{\leq}&\norm{\delta_{t}}^2 - 2\gamma\left(1 - \gamma\right)f_{\mS_t,t}(x^t).
\end{eqnarray*}
Since $f_{S_t,t}(x^t) \geq 0$, we have $\norm{\delta_{t+1}}^2 \leq \norm{\delta_{t}}^2$, i.e.\ \eqref{eq:bounded-det} holds.
\end{proof}

Thm.~\ref{theo:convex} is an unusual result for \SGD methods. Currently, to get a $\cO(1/k)$ convergence rate for \SGD, one has to assume smoothness and strong convexity~\cite{Gower19} or convexity, smoothness and interpolation~\cite{VaswaniBS19}.

Here we get a $\cO(1/k)$ rate by \emph{only} assuming star-convexity. This is because we have smoothness and interpolation properties as a by-product due to our  reformulation~\eqref{eq:sgdreform}.

\ruiline{However, the star-convexity assumption of $f_k(\cdot)$ for all $k \in \N$ is hard to interpret in terms of assumptions on $F$ in general. But, we are able to interpret it in many important extremes.  That is, for the full \NR method, we show that it suffices for the Newton direction to be $2$--co-coercive (see~\eqref{eq:nxcvx} in Sec.~\ref{sec:globalNR}). For the other extreme where the sketching matrix samples a single row, then the star-convexity assumption is even easier to check, and is guaranteed to hold so long as $F_i(x)^2$ is convex for all $i=1, \cdots, m$ (see Sec.~\ref{sec:Kaczmarz}).

}

\ruiline{

Next, we will show

the convergence of $F(x^k)$ instead of $f_k(x^k)$ via Thm.~\ref{theo:convex}.}

\subsubsection{Sublinear convergence of the Euclidean norm \texorpdfstring{$\norm{F}$}{|F|}}
\label{sec:EuclideanF}
If $\E{\mH_{\mS}(x)}$ is invertible for all $x \in \R^p$, we can use Thm.~\ref{theo:convex} with the bound~\eqref{eq:bounded-det} to guarantee that $\norm{F}$ converges sublinearly.
Indeed, \ruiline{when $\E{\mH_{\mS}(x)}$ is invertible, $\E{\mH_{\mS}(x)}$ is symmetric positive definite.}

Thus there exists $\lambda>0$ that bounds the smallest eigenvalue away from zero in any closed bounded set
\ruiline{(e.g.\ $\{x \in \R^p \mid \norm{x-x^*} \leq \norm{x^0 - x^*} \}$\footnote{\ruiline{We can re-write the set as the closure of the ball $\{x \in \R^p \mid x \in \overline{\cB(x^*, \norm{x^0 - x^*})}\}$. }})}:

\begin{equation} \label{eq:smalleigbnd}
\min_{x \in \{x \mid \norm{x-x^*} \leq \norm{x^0 - x^*}\}} \lambda_{\min} \left(\E{\mH_{\mS}(x)}\right)  =  \lambda  >  0,
\end{equation}
where  $\lambda_{\min}(\cdot)$ is the smallest eigenvalue operator.

Consequently, under the assumption of Thm.~\ref{theo:convex}
with the condition~\eqref{eq:cvx-S-star}, from~\eqref{eq:bounded-det} and~\eqref{eq:smalleigbnd},
we have
\begin{equation}
\lambda  \E{\min_{t=0, \ldots, k-1}\norm{F(x^t)}^2}   \leq  \E{\min_{t=0, \ldots, k-1}\norm{F(x^t)}^2_{\E{\mH_{\mS}(x^t)}}}  \overset{\eqref{eq:convminEf}}{\leq}  \frac{1}{k}\frac{\norm{x^0-x^*}^2}{\gamma\left(1 - \gamma\right)}.  \label{eq:FEHsk}
\end{equation}

It turns out that using the smallest eigenvalue of $\E{\mH_{\mS}(x)}$ in the above bound  is overly pessimistic.
\ruiline{
To improve it, first note that we do \emph{not need} that $\E{\mH_{\mS}(x)}$ is invertible. Instead, we only need that

 $F(x) \in {\bf Im}(DF(x)^\top) \subset {\bf Im}(\E{\mH_{\mS}(x)})$, as we show in Cor.~\ref{lem:EuclidieanF}.} But first, we need the following lemma.
\begin{lemma}[Lemma 10 in~\cite{RSN_nips}] \label{lem:ker}
For any matrix $\mW$ and symmetric positive semi-definite matrix $\mG$ s.t.\
${\bf Ker}(\mG)  \subset  {\bf Ker}(\mW),$
we have
${\bf Ker}(\mW^\top)  =  {\bf Ker}(\mW\mG\mW^\top).$
\end{lemma}

\ruilinex{Note $L \eqdef \sup_{x \in \{x \mid \norm{x-x^*} \leq \norm{x^0 - x^*}\}} \|DF(x)\| > 0$.

Such $L$ exists because $x$ is in a closed bounded convex set and because we have assumed that $DF(\cdot)$ is continuous. A continuous mapping over a closed bounded convex set is bounded.
Now we can state the sublinear convergence results for $\norm{F}$.}
\begin{corollary} \label{lem:EuclidieanF}
Let

\begin{align}
 \rho(x)  &\eqdef  \min_{v \in {\bf Im}\left(DF(x)\right) / \{0\}}\frac{v^\top DF(x)\E{\mH_{\mS}(x)}DF(x)^\top v}{\norm{v}^2}, \label{eq:defrho} \\
 \rho  &\eqdef  \min_{x \in \{x \mid \norm{x-x^*} \leq \norm{x^0 - x^*}\}} \rho(x). \label{eq:defrho2}
\end{align}
It follows that $0\leq \rho(x)\leq 1$.

\ruilinex{If
\begin{equation}\label{eq:DFTinEmHass}
 F(x) \; \in \; {\bf Im}(DF(x)^\top) \; \subset \; {\bf Im}(\E{\mH_{\mS}(x)}) \quad \mbox{for all } x \in \R^p,
\end{equation}
then

$\quad \quad \rho(x) = \lambda^+_{\min}\left(DF(x)\E{\mH_{\mS}(x)}DF(x)^\top\right) > 0 \quad \forall x \in \R^p, \quad \mbox{and} \quad \rho >0,$

where $\lambda^+_{\min}$ is the smallest \emph{non-zero} eigenvalue.
Furthermore, if the star-convexity for each sketching matrix~\eqref{eq:cvx-S-star} holds

, then

\begin{eqnarray} \label{eq:EuclidieanF}
\E{\min_{t=0,\ldots,k-1}\norm{F(x^t)}^2} &\leq& \frac{1}{k}\cdot\frac{L^2\norm{x^0-x^*}^2}{\rho\gamma\left(1 - \gamma\right)}.
\end{eqnarray}}
\end{corollary}

\begin{proof}
First recall that
\begin{eqnarray*}
DF(x)\mH_{\mS}(x)DF(x)^\top DF(x)\mH_{\mS}(x)DF(x)^\top = DF(x)\mH_{\mS}(x)DF(x)^\top \quad \mbox{for all } x \in \R^p,
\end{eqnarray*}
which is shown in the proof of Lemma~\ref{lem:smooth}.
Thus $DF(x)\mH_{\mS}(x)DF(x)^\top$ is a projection. By Jensen's inequality, the eigenvalues of an expected projection are between $0$ and $1$. Thus by the definition of $\rho(x)$, we have $0\leq\rho(x)\leq 1$.
\ruiline{Next,
by~\eqref{eq:DFTinEmHass}, we have
${\bf Ker}\left(\E{\mH_{\mS}(x)}\right) \subset {\bf Ker}\left(DF(x)\right)$. Thus, by Lemma~\ref{lem:ker} we have that}

\begin{equation} \label{eq:imDFequalkerperp}
{\bf Im}\left(DF(x)\right)  =  \left({\bf Ker}\left(DF(x)^\top\right)\right)^\perp  =  \left({\bf Ker}\left(DF(x)\E{\mH_{\mS}(x)}DF(x)^\top\right)\right)^\perp,
\end{equation}
where the second equality is obtained by Lemma~\ref{lem:ker}. Now from the definition of $\rho(x)$ in~\eqref{eq:defrho}, we have

\begin{eqnarray}
\rho(x) &\overset{\eqref{eq:imDFequalkerperp}}{=}&\min_{v \in \left({\bf Ker}\left(DF(x)\E{\mH_{\mS}(x)}DF(x)^\top\right)\right)^\perp / \{0\}}\frac{v^\top DF(x)\E{\mH_{\mS}(x)}DF(x)^\top v}{\norm{v}^2} \nonumber \\
&=& \lambda^+_{\min}\left(DF(x)\E{\mH_{\mS}(x)}DF(x)^\top\right)  >  0. \nonumber
\end{eqnarray}
It now follows that $\rho >0$, since the definition of $\rho$ in~\eqref{eq:defrho2} is given by minimizing $\rho(x)$ over the closed bounded set $\{x \mid \norm{x-x^*} \leq \norm{x^0 - x^*}\}.$
Next, \ruiline{given $x \in \{x \mid \norm{x-x^*} \leq \norm{x^0 - x^*}\}$, since $F(x) \in {\bf Im}(DF(x)^\top)$ by $\eqref{eq:DFTinEmHass}$ and notice that ${\bf Im}(DF(x)^\top) = {\bf Im}(DF(x)^\top DF(x))$, there exists $v \in \R^m$ s.t.\ $F(x) = DF(x)^\top DF(x)v$.

\xline{If $F(x) \neq 0$, then $DF(x)v \in {\bf Im}\left(DF(x)\right) / \{0\}$, we have}

\begin{eqnarray}
\norm{F(x)}^2_{\E{\mH_{\mS}(x)}} &=& v^\top DF(x)^\top DF(x)\E{\mH_{\mS}(x)}DF(x)^\top DF(x)v \nonumber \\
&\overset{\eqref{eq:defrho}}{\geq} & \rho(x)v^\top DF(x)^\top DF(x)v.\label{eq:zsnlo8jh8o}
\end{eqnarray}
Since $F(x) = DF(x)^\top DF(x)v$ and ${\bf Im}(DF(x)^\top) \oplus {\bf Ker}(DF(x)) = \R^m$,\footnote{\ruiline{The operator $\oplus$ denotes the direct sum of two vector spaces.}} we have that

\[\exists! \ y \in {\bf Ker}(DF(x)) \subset \R^m \mbox{ s.t.\ } v =  (DF(x)^\top DF(x))^{\dagger} F(x) + y.\]
Thus

\[DF(x) v = DF(x) (DF(x)^\top DF(x))^{\dagger} F(x) = (DF(x)^\top)^{\dagger} F(x).\]

Substituting this in~\eqref{eq:zsnlo8jh8o},} we have that

\begin{eqnarray}
\norm{F(x)}^2_{\E{\mH_{\mS}(x)}} \geq \rho(x)\norm{F(x)}^2_{\left(DF(x)^\top DF(x)\right)^{\dagger}}
\geq \frac{\rho}{L^2}\norm{F(x)}^2, \label{eq:FEHs}
\end{eqnarray}
where

on the last inequality, we use that $\sup_{x \in \{x \mid \norm{x-x^*} \leq \norm{x^0 - x^*}\}} \|DF(x)\| \leq L$ and $\rho(x) \geq \rho$ by the definition of $\rho$ in~\eqref{eq:defrho2}

.

\xline{If $F(x) = 0$,~\eqref{eq:FEHs} still holds. Thus, for all $x \in \{x \mid \norm{x-x^*} \leq \norm{x^0 - x^*}\}$,~\eqref{eq:FEHs} holds.}
Consequently by Thm.~\ref{theo:convex} and~\eqref{eq:bounded-det} under the star-convexity condition~\eqref{eq:cvx-S-star} with $\norm{x^t - x^*} \leq \norm{x^0 - x^*}$ for all $t \in \{0, \cdots, k-1\}$, we have that
\[ \frac{\rho}{L^2} \E{\min_{t=0,\ldots,k-1}\norm{F(x^t)}^2}  \overset{\eqref{eq:FEHs}}{\leq}  \E{\min_{t=0,\ldots,k-1} \norm{F(x^t)}^2_{\E{\mH_{\mS}(x^t)}}}  \overset{\eqref{eq:convminEf}}{\leq} \frac{1}{k} \frac{\norm{x^0-x^*}^2}{\gamma\left(1 - \gamma\right)},\]

which after multiplying through by $\left. L^2 \right/\rho >0$ concludes the proof.
\end{proof}

\ruiline{
Thus with Cor.~\ref{lem:EuclidieanF}, we show that $F(x^t)$ converges to zero. This lemma relies on the inclusion~\eqref{eq:DFTinEmHass}, which in turn imposes some restrictions on the sketching matrix and $F(x)$. In our forthcoming examples in Sec.~\ref{sec:globalNR} and~\ref{sec:Kaczmarz}, we can directly verify the inclusion of~\eqref{eq:DFTinEmHass}. For other examples in Sec.~\ref{sec:SNM} and~\ref{sec:GLM}, we provide the following Lemma~\ref{lem:reformulationnew} where we give sufficient conditions for~\eqref{eq:DFTinEmHass} to hold.

\begin{lemma}\label{lem:reformulationnew}
Let $F(x) \in {\bf Im}(DF(x)^\top)$. Furthermore, we suppose that  $\mS \sim \cD_x$ is \emph{adapted} to $DF(x)$
by which we mean
\begin{align}
{\bf Ker} \left(\E{\mS\mS^\top}\right)  \; \subset \; {\bf Ker}(DF(x)) &  \subset \; {\bf Ker}\left(\mS^\top\right) , \quad \mbox{for all } \mS \sim \cD_x. \label{eq:adaptedsketch}

\end{align}
Then it follows that~\eqref{eq:DFTinEmHass} holds for all $x \in \R^p$.

\end{lemma}
\begin{proof}

Since  ${\bf Ker}(DF(x)^\top DF(x)) = {\bf Ker}(DF(x)) \overset{\eqref{eq:adaptedsketch}}{\subset} {\bf Ker}(\mS^\top)$,

we have
\begin{align}
{\bf Ker}\left(\left(\mS^\top DF(x)^\top DF(x)\mS\right)^\dagger\right)  &=  {\bf Ker}\left(\mS^\top DF(x)^\top DF(x)\mS\right)  =  {\bf Ker}(\mS), \label{eq:ker2new}
\end{align}
where

the last equality is obtained by Lemma~\ref{lem:ker} with ${\bf Ker}(DF(x)^\top DF(x)) \subset {\bf Ker}(\mS^\top)$.
Thus, using Lemma~\ref{lem:ker} again with $\mG = \left(\mS^\top DF(x)^\top DF(x)\mS\right)^\dagger$, $\mW = \mS$ and ${\bf Ker}(\mG) \subset {\bf Ker}(\mW)$ given by~\eqref{eq:ker2new}, we have that
\begin{equation}\label{eq:ker3new}
{\bf Ker}(\mH_{\mS}(x)) \overset{\eqref{eq:Hk}}{=} {\bf Ker}(\mS\left(\mS^\top DF(x)^\top DF(x)\mS\right)^\dagger\mS^\top)  =  {\bf Ker}(\mS^\top)  =  {\bf Ker}(\mS\mS^\top).
\end{equation}
\noindent \ruiline{As $\mH_{\mS}(x)$ is symmetric positive semi-definite $\forall \ \mS\sim\cD_x$, we have that

\begin{align*}
&v \in {\bf Ker}\left(\E{\mH_{\mS}(x)}\right)
 \Longleftrightarrow  \E{\mH_{\mS}(x)} v = 0
 \Longleftrightarrow  \norm{v}_{\E{\mH_{\mS}(x)}}^2 = 0 \ \ \left(\mbox{as } \E{\mH_{\mS}(x)} \succeq 0\right) \\
 &\Longleftrightarrow  \E{\norm{v}_{\mH_{\mS}(x)}^2} = 0 \Longleftrightarrow \int_{\mS} \norm{v}_{\mH_{\mS}(x)}^2 d\mathbb{P}_{\cD_x}(\mS) = 0 \\
 &\Longleftrightarrow  \norm{v}_{\mH_{\mS}(x)}^2 = 0 \; \forall \; \mS \sim \cD_x
 \ \ \left(\mbox{as } \norm{v}_{\mH_{\mS}(x)}^2  \geq 0  \; \forall \; \mS\right) \\
 &\overset{\mH_{\mS}(x) \succeq 0}{\Longleftrightarrow} v \in {\bf Ker}\left(\mH_{\mS}(x)\right) \; \forall \; \mS \sim \cD_x

 \Longleftrightarrow v \in \bigcap_{\mS\sim\cD_x} {\bf Ker}\left(\mH_{\mS}(x)\right),
\end{align*}
where we use $\bigcap_{\mS\sim\cD_x} {\bf Ker}\left(\mH_{\mS}(x)\right)$ to note the intersection of the random subsets ${\bf Ker}\left(\mH_{\mS}(x)\right)$ for all $\mS \sim \cD_x$.
}
Similarly, we have ${\bf Ker}\left(\E{\mS\mS^\top}\right) = \bigcap_{\mS\sim\cD_x} {\bf Ker}\left(\mS\mS^\top\right)$ because $\mS\mS^\top$ is also symmetric, positive semi-definite for all $\mS \sim \cD_x$.
Thus we have
\begin{eqnarray*}
{\bf Ker}(\E{\mH_{\mS}(x)}) &=& \bigcap_{\mS\sim\cD_x} {\bf Ker}(\mH_{\mS}(x)) \\
&\overset{\eqref{eq:ker3new}}{=}& \bigcap_{\mS\sim\cD_x}{\bf Ker}(\mS\mS^\top)
\; = \; {\bf Ker}(\E{\mS\mS^\top})
\; \overset{\eqref{eq:adaptedsketch}}{\subset} \; {\bf Ker}(DF(x)).
\end{eqnarray*}

Consequently, by considering the complement of the above, we arrive at~\eqref{eq:DFTinEmHass}.

\end{proof}}

\ruilinex{We refer to a sketching matrix $\mS \sim \cD_x$ that satisfies~\eqref{eq:adaptedsketch} as a sketch that is \emph{adapted to} $DF(x)$. One easy way to design such adapted sketches is
the following.
\begin{lemma} \label{lem:adaptedsketch}

Let $\hat{\mS} \in \R^{p \times \tau} $ s.t.\ $\hat{\mS} \sim \cD$ a fixed distribution independent to $x$ and ${\bf Ker} (\mathbb{E}[\hat{\mS} \hat{\mS}^\top] ) \subset {\bf Ker}(DF(x)^\top)$. Thus, $\mS = DF(x)^\top \hat{\mS} \in \R^{m \times \tau}$ is adapted to $DF(x)$.

\end{lemma}
\begin{proof}
First, $ {\bf Ker}(DF(x)) \subset {\bf Ker}(\hat{\mS}^\top DF(x)) =  {\bf Ker}(\mS^\top).$ Furthermore, from Lemma~\ref{lem:ker} with  ${\bf Ker} (\mathbb{E}[\hat{\mS} \hat{\mS}^\top] ) \subset {\bf Ker}(DF(x)^\top)$, we conclude the proof with
\[ {\bf Ker} \left(\E{\mS\mS^\top}\right) \; =\;  {\bf Ker} (DF(x)^\top\mathbb{E}[\hat{\mS} \hat{\mS}^\top]DF(x)) \; \subset   {\bf Ker}(DF(x)). \]
\end{proof}}

\ruilinex{
The condition ${\bf Ker} (\mathbb{E}[\hat{\mS} \hat{\mS}^\top] ) \subset {\bf Ker}(DF(x)^\top)$ in Lemma~\ref{lem:adaptedsketch}
holds for many standard sketches including Gaussian and subsampling sketches presented as follows.

\begin{lemma}\label{lem:SSTinv}
For Gaussian and uniform subsampling sketches defined in Sec.~\ref{sec:sketch}, we have that $\E{\mS\mS^\top} = c \mI_m $ with $c>0$ a fixed constant depending on the sketch.
\end{lemma}

\begin{proof}
For Gaussian sketches with $\mS_{ij} \sim \cN(0,\frac{1}{\tau})$, we have that $c=1$. Indeed, since the mean is zero, off-diagonal elements of  $\E{\mS\mS^\top}$ are all zero. We note $\mS_{i:}$ the $i$th row of $\mS$, then the $i$th diagonal element of the matrix $\E{\mS\mS^\top}$  is given by

\[
\E{\mS_{i:}\mS_{i:}^\top} =\sum_{j=1}^{\tau} \E{\mS_{ij}^2} = \sum_{j=1}^{\tau} \frac{1}{\tau} =1.
\]
For the uniform subsampling sketch~\eqref{eq:subsample}, we have again that off-diagonal elements are zero since the rows of $\mS$ are orthogonal. The diagonal elements are constant with
 \begin{align*}
\E{\mS_{i:}\mS_{i:}^\top}

=\frac{1}{\binom{m}{\tau}}\sum_{\substack{C \subset \{1,\ldots, m\}, |C|=\tau, i\in C}} 1  = \frac{\binom{m-1}{\tau-1}}{\binom{m}{\tau}} = \frac{\tau}{m}, \quad \mbox{for all } i = 1, \cdots, m.
\end{align*}
\end{proof}}

\ruilinex{
From Lemma~\ref{lem:SSTinv}, we know that $\mathbb{E}[\hat{\mS} \hat{\mS}^\top] = c\mI_p$ invertible with $c>0$. Thus ${\bf Ker} (\mathbb{E}[\hat{\mS} \hat{\mS}^\top] ) = \{0\} \subset {\bf Ker}(DF(x)^\top)$ holds for \emph{any} sketch size $\tau$.}

\subsection{Convergence for strongly convex}

Here we establish a global linear convergence of \SNR when assuming that $f_y$ is strongly quasi-convex.

\begin{assumption}[$\mu$-Strongly Quasi-Convexity]\label{ass:strconv}
Let $x^*$ satisfy Asm.~\ref{ass:zero}

and
\begin{equation}\label{eq:strconv}
\exists \ \mu > 0 \mbox{ s.t.\ } \ f_y(x^*) \geq f_y(x) + \dotprod{\nabla f_y(x), x^*-x} + \frac{\mu}{2} \norm{x^*-x}^2 \ \ \forall \ x, y \in \R^p.
\end{equation}

\end{assumption}

This Asm.~\ref{ass:strconv} is strong, so much so, we have the following lemma.

\begin{lemma}\label{lem:assstrconvimplyasskerr}
Asm.~\ref{ass:strconv} implies~\eqref{ass:ker} and that the solution to~\eqref{eq:main} is unique.
\end{lemma}

\begin{proof}
Let $y \in \R^p$ and let $u \in F(\R^p) \cap {\bf Ker}\left(\E{\mH_{\mS}(y)}\right)$. $u \in F(\R^p)$ implies that $\exists x \in \R^p$ s.t.\ $F(x) = u$. Besides, $u \in {\bf Ker}\left(\E{\mH_{\mS}(y)}\right)$ implies that $\E{\mH_{\mS}(y)}F(x) = 0$. Now we apply \eqref{eq:strconv} at point $x$ knowing that $f_y(x^*) = 0$:
\begin{align*}
&\quad \quad 0 \geq f_y(x) + \dotprod{\nabla f_y(x), x^*-x} + \frac{\mu}{2} \norm{x^*-x}^2 \\
&\Longrightarrow 0 \geq 0 + \dotprod{0, x^*-x} + \frac{\mu}{2} \norm{x^*-x}^2 \ \ \left(\mbox{as } \E{\mH_{\mS}(y)}F(x) = 0\right)
\Longleftrightarrow x = x^*.
\end{align*}
Thus $F(x) = u = 0$. We conclude $F(\R^p) \cap {\bf Ker}\left(\E{\mH_{\mS}(y)}\right) = \{0\}$, i.e.~\eqref{ass:ker} holds.

Besides, let $x'$ be a global minimizer of $f_y(\cdot)$. Then $f_y(x') = f_y(x^*) = 0$ and $\nabla f_y(x') = 0$. Similarly, by applying \eqref{eq:strconv} at point $x'$, we obtain $x' = x^*$. Consequently, $x^*$ is the unique minimizer of $f_y(\cdot)$ for all $y$, thus the unique solution to \eqref{eq:main}, according to~\eqref{ass:ker} and Lemma~\ref{lem:equiv}.
\end{proof}

Under
Asm.~\ref{ass:strconv}
, choosing $\gamma = 1$ guarantees a fast global linear convergence.

\begin{theorem}\label{theo:strconv}
If $x^*$ satisfies Asm.~\ref{ass:strconv} and $\gamma \leq 1$, then \SNR converges linearly:
\begin{eqnarray}
\E{\norm{x^{k+1}-x^*}^2} &\leq& (1-\gamma \mu)^{k+1} \norm{x^{0}-x^*}^2 \quad \quad \mbox{with } \ \mu \leq 1.
\end{eqnarray}
\end{theorem}

\begin{proof}
Let $\delta_k \eqdef x^{k} -x^*.$
By expanding the squares, similarly we have that
\begin{eqnarray}
\EE{k}{\norm{\delta_{k+1}}^2} &=& \norm{\delta_k }^2 - 2\gamma \dotprod{\delta_k , \nabla f_k(x^k)} + \gamma^2\EE{k}{\norm{\nabla f_{\mS_k,k}(x^k)}^2} \nonumber \\
&\overset{\eqref{eq:strconv}}{\leq}& (1-\gamma \mu) \norm{\delta_k }^2 - 2\gamma (f_k(x^k) - f_k(x^*))+ \gamma^2\EE{k}{\norm{\nabla f_{\mS_k,k}(x^k)}^2} \nonumber \\
&\overset{\eqref{eq:1smooth}}{\leq }& (1-\gamma \mu) \norm{\delta_k }^2 - 2\gamma\left(1 - \gamma\right)(f_k(x^k) -f_k(x^*)) \nonumber \\
&\leq& (1-\gamma \mu) \norm{\delta_k }^2. \nonumber \quad \quad \left(\mbox{since } \gamma\left(1 - \gamma\right)(f_k(x^k) -f_k(x^*)) \geq 0\right)
\end{eqnarray}
Now by taking total expectation, we have that
\[\E{\norm{x^{k+1}-x^*}^2} \ \leq \ (1-\gamma \mu) \E{\norm{x^k-x^*}^2} \ \leq \ (1-\gamma \mu)^{k+1}\norm{x^0-x^*}^2.\]

Next, we show that  $\mu \leq 1$. In fact, when we imply \eqref{eq:strconv} at the point $x^k$, it shows
\begin{eqnarray}\label{eq:mu}
\eqref{eq:strconv} &\overset{\eqref{eq:1smooth} }{\Longrightarrow}& f_k(x^*) \geq \frac{1}{2}\EE{k}{\norm{\nabla f_{\mS_k,k}(x^k)}^2} + \dotprod{x^*-x^k, \nabla f_{k}(x^k)} + \frac{\mu}{2}\|x^*-x^k\|^2 \nonumber \\
&\Longleftrightarrow& f_k(x^*) \geq \frac{1}{2}\EE{k}{\norm{x^* - \left(x^k - \nabla f_{\mS_k,k}(x^k)\right)}^2} - \frac{1-\mu}{2}\|x^*-x^k\|^2 \nonumber \\
&\overset{f_k(x^*) = 0}{\Longrightarrow}& (1-\mu)\|x^*-x^k\|^2 \geq \EE{k}{\norm{x^* - \left(x^k - \nabla f_{\mS_k,k}(x^k)\right)}^2} \geq 0. \nonumber
\end{eqnarray}
Thus $\mu \leq 1$.
\end{proof}


TITLE: How to relate BCS's particle number uncertainty with the quotient between the gap and Fermi energy
QUESTION [1 upvotes]: I'm trying to prove that the uncertainty in the particle number of the BCS Theory is related to the quotient between the energy gap and Fermi energy:
$$\left \langle \left ( N - \overline{N} \right )^{2} \right \rangle \simeq N\frac{\Delta }{\varepsilon _{F}}\ll N$$
I'm using Tinkham's Introduction To Superconductivity 2nd Edition chapter 3 as reference. I've already proved that
$$\left \langle \left ( N - \overline{N} \right )^{2} \right \rangle = 4\sum_{k}u_{k}^{2}v_{k}^{2}$$
And also
$$\overline{N} = \sum_{k}2\left | v_{k}^{2} \right |$$
In page 51, Tinkham says, referring to my second equation: "This is nonzero unless the occupancy cuts off discontinuously. In fact, it will turn out that $v_{k}$ goes from 1 to 0, and $u_{k}$ goes from 0 to 1 in an energy range of $\sim kT_{c}$, so that the sum is $\sim (T_{c}/T_{F})\bar{N}$."
Then at page 59 there is a graph showing $1-v_{k}^{2}$ for $T=0$:

$$$$
From this graph I don't understand the statement I just quoted. Wouldn't the energy range to make those changes in $v_{k}$ and $u_{k}$ be $\sim 2kT_{c}$?
Going back to my initial problem, I guess I have to integrate my second equation over $\xi _{k}$ from $-kT_{c}$ to $kT_{c}$ to get to the approximation I want to prove. However, I don't seem to find a way to get there. I'm using $v_{k}$ and $u_{k}$ in their forms where they depend on the gap and on $\xi _{k}$ but I don't get anywhere near what I want (of course I have to introduce or take away Boltzmann's constant at some point but I don't think my problem is there).
Any suggestions? Thanks in advance.

REPLY [0 votes]: Let's suppose that $u^2= (1+\tanh (\epsilon-\mu)/ 2kT_c)/2$ and $v^2=(1-\tanh (\epsilon-\mu)/2kT_c)/2$ (a resonable assumption given the curves in the figure and one that make s $|u^2|+|v|^2=1$) so that
$$
4u^2v^2= 1-\tanh^2 (\epsilon-\mu)/2kT_c= {\rm sech}^2\{(\epsilon-\mu)/ 2kT_c\}$$
and
$$
4\sum_k u^2v^2 = \int_{-\infty}^\infty N(0)\, {\rm sech}^2\{(\epsilon-\mu)/ 2kT_c\} d\epsilon = 4 N(0)kT_c\approx 4N(0)\Delta(T=0)
$$
Does this help?
Note $N(0)={\rm const.} \sqrt{\epsilon_f}$, $N = (2/3) (\hbox{ same const.})  \epsilon_f^{3/2}$ so $(N/\epsilon_f) \sim   N(0)$ making the integral  $N(\Delta/\epsilon_f)$ up to numerical constants.


TITLE: Measurability condition $\{x \in X: g(\{n \in \mathbf{N}: f_n(x)>a\})>b\} \in \mathscr{F}$
QUESTION [2 upvotes]: Let $(X,\mathscr{F})$ be a measurable space, and $f_n: X\to \mathbf{R}$ a sequence of measurable functions, with $n\ge 1$. Let also $g$ be a real-valued function defined on the power set of the positive integers $\mathbf{N}$.
What assumptions on $g$ are sufficient so that
$$
\{x \in X: g(\{n \in \mathbf{N}: f_n(x)>a\})>b\} \in \mathscr{F}
$$
for every real $a,b$?

REPLY [1 votes]: Let us identify the power set of $\Bbb {N} $ with the set $P := \{0,1\}^\Bbb {N} $ of $0-1$ valued sequences.
Then, by measurability of the $f_n $, the map
$$
\Phi_a : X \to P, x \mapsto (1_{f_n (x)>a})_n
$$
is measurable when $P $ is equipped with the product sigma algebra.
Now, your set in question is equal to
$$
\{x \mid \Phi_a (x) \in g^{-1}((b,\infty))\},
$$
which is measurable if $g^{-1}((b,\infty)) $ is. This holds, if $g : P \to \Bbb {R} $ is measurable (with respect to the product sigma algebra on $P $).
I am very certain that this condition is even necessary,  if you want your condition to hold for all choices of $f_n $.


TITLE: Brezis Exercise 4.1: Find conditions for a function to be in Lp
QUESTION [0 upvotes]: I am stuck on showing the following exercise on Brezis, I am aware of this answer (Under what conditions does $f$ belong to $L^p(\mathbb{R}^N)$?), but I would like to see a more detailed explanation. In particular, I am not sure how to make the notion "$\sim$" rigorous:

Let $\alpha > 0$ and $\beta > 0$. Set
$$
f(x) = \frac{1}{1 +|x|^\alpha} \frac{1}{1 + |\log|x||^\beta}, x \in \mathbb{R}^N.
$$
Under what conditions does $f$ belong to $L^p(\mathbb{R}^N)$.

Here is my attempt so far: We wish to find conditions such that
$$
\int_{\mathbb{R}^N} \frac{1}{(1 + |x|^\alpha)^p}\ \frac{1}{(1 + |\log|x||^\beta)^p} \,dx < \infty.
$$
We have by changing to spherical coordinate that
\begin{align*}
\int_{\mathbb{R}^N} \frac{1}{(1 + |x|^\alpha)^p}\ \frac{1}{(1 + |\log|x||^\beta)^p} \,dx < \infty \iff \int_{0} ^\infty \frac{1}{(1 + r^\alpha)^p} \frac{1}{(1 + |\log r|^\beta)^p} r^{N - 1} \,dr < \infty
\end{align*}
Now noticing that when $r$ is small, we have the integrand to be extremly small, so we can wrote the integral as
\begin{align*}
\int_{0} ^\infty \frac{1}{(1 + r^\alpha)^p} \frac{1}{(1 + |\log r|^\beta)^p} r^{N - 1} \,dr &= \int_0 ^1 \frac{r^{N - 1}}{(1 + r^\alpha)^p} \frac{1}{(1 + |\log r|^\beta)^p} \,dr + \int_1 ^\infty \frac{r^{N - 1}}{(1 + r^\alpha)^p} \frac{1}{(1 + |\log r|^\beta)^p} \,dr
\end{align*}
For the first integral, we have
\begin{align*}
\int_0 ^1 \frac{r^{N - 1}}{(1 + r^\alpha)^p} \frac{1}{(1 + |\log r|^\beta)^p} \,dr \leq \int_0 ^1 \frac{r^{N - 1}}{(1 + r^\alpha)^p} \,dr \leq \int_0 ^1 \frac{r^{N - 1}}{r^{\alpha p}} \,dr = \int_0 ^1 r^{N - 1 - \alpha p} \,dr = \frac{r^{N - \alpha p}}{N - \alpha p}
\end{align*}
Now the quantity is finite as long as $N - \alpha p > 0$. I wish to do a similar thing for the second integral, but getting rid of $\frac{1}{(1 + r^\alpha)^p}$. However, this will make the integral to blow up. I am stuck at this point. Especially I have not found a way to get a condition relating to $\beta$.

REPLY [0 votes]: We want to know if the first integral $\int_{\mathbb{R}^N} \frac{1}{(1 + |x|^\alpha)^p}\ \frac{1}{(1 + |\log|x||^\beta)^p} \,dx$ converge or not.
This is when:

if $\alpha > \frac N p$ then for all $\beta$
if $\alpha > \frac N p$ then for $\beta = \frac 1 p$

First remark: in your integral there are not problems in $0$ because $1+|x|^{\alpha}$ goes to $1$ and $1+|\log |x||^\beta$ goes to $+\infty$ as $x \to 0$.
Now you have to deal with the following:
$$\int_{2} ^\infty \frac{1}{(1 + r^\alpha)^p} \frac{1}{(1 + |\log r|^\beta)^p} r^{N - 1} \,dr < \infty$$
To understand the behavior of the function you might write:
$$\int_{2} ^\infty \frac{1}{(1 + r^\alpha)^p} \frac{1}{(1 + |\log r|^\beta)^p} r^{N - 1} \,dr = \int_{2} ^\infty \frac{1}{r^{\alpha p}(1 + r^{-\alpha})^p} \frac{1}{|\log r|^{\beta p}(1 + |\log r|^{-\beta})^p} r^{N - 1} \,dr = \int_{2} ^\infty \frac{1}{r^{\alpha p - N + 1} |\log r|^{\beta p}} \frac{1}{(1 + |\log r|^{-\beta})^p(1 + r^{-\alpha})^p} \,dr$$
Finally you notice that for $r \geq 2$ one has $1 \leq (1 + |\log r|^{-\beta})^p(1 + r^{-\alpha})^p \leq (1 + |\log 2|^{-\beta})^p(1 + 2^{-\alpha})^p<+\infty$
where the last term is a finite constant.
Using this $2$ inequalities you can understand the "only if" in your question.


TITLE: Derivation of the Euler Lagrange Equation
QUESTION [3 upvotes]: I'm self studying a little bit of physics at the moment and for that I needed the derivation of the Euler Lagrange Equation. I understand everything but for a little step in the proof, maybe someone can help me. That's were I am:
$$
 \frac{dJ(\varepsilon=0 )}{d\varepsilon } = \int_{a}^{b}\eta(x)\frac{\partial F}{\partial y}+\eta'(x)\frac{\partial F}{\partial y'}dx = 0
$$
Then the second term is integrated by parts:
$$
\frac{dJ(\varepsilon =0)}{d\varepsilon } = \int_{a}^{b}\eta(x)\frac{\partial F}{\partial y}dx + \left [ \frac{\partial F}{\partial y'}\eta(x) \right ]_a^b-\int_{a}^{b}\frac{d}{dx}(\frac{\partial F}{\partial y'})\eta(x) = 0
$$
And the equation is simplified to:
$$
\frac{dJ(\varepsilon =0)}{d\varepsilon } = \int_{a}^{b}\frac{\partial F}{\partial y}-\frac{d}{dx}(\frac{\partial F}{\partial y'})\eta(x)dx = 0
$$
What I don't understand is why you just can omit the
$$
\left [ \frac{\partial F}{\partial y'}\eta(x) \right ]_a^b
$$
Why does that equal zero, but the integral following it which also goes from a to b isn't left out?
I think it's pretty obvious, but I'm just to stupid to see it. I'd appreciate if someone could help me!

REPLY [0 votes]: In the Euler-Lagrange equation, the function $\eta$ has by hypothesis the following properties:

$\eta$ is continuously differentiable (for the derivation to be rigorous)
$\eta$ satisfies the boundary conditions $\eta(a) = \eta(b) = 0$.

In addition, $F$ should have continuous partial derivatives.
This is why $\left [ \frac{\partial F}{\partial y'}\color{red}{\eta(x)} \right ]_a^b$ simplifies to $0$.


TITLE: Difference between uncertainty relations
QUESTION [0 upvotes]: I have come across two different uncertainty relations for position and momentum, namely
$$\Delta x\Delta p\geq\frac{\hbar}{2}$$ and $$\Delta x\Delta p\geq h.$$ These two are clearly different and yield different results when calculated with. Why are there two of them?

REPLY [2 votes]: The correct expression  is
$$\Delta x\Delta p\geq \frac{\hbar}{2}$$
Though most of the time one only interested in the order of magnitudes so the numerical factors don't matter.


text:
\begin{document}

\maketitle

\begin{abstract}

The Chow-Mumford (CM) line bundle is a functorial line bundle on the base of any family of polarized varieties, in particular on the base of families of klt Fano varieties (also called sometimes $\bQ$-Fano varieties). It is conjectured that it yields a polarization on the conjectured moduli space of K-semi-stable klt Fano varieties. This boils down to showing semi-positivity/positivity statements about the CM-line bundle for families with  $K$-semi-stable/$K$-polystable fibers. We prove the necessary semi-positivity statements in the $K$-semi-stable situation,
and the necessary positivity statements in the uniform $K$-stable situation, including in both cases variants  assuming $K$-stability  only for very general fibers. Our statements work in the most general singular situation (klt singularities), and the proofs are algebraic, except the computation of the limit of a sequence of real numbers via the central limit theorem of probability theory.
We also  present an application to the classification of Fano varieties. Furthermore, in the semi-positivity case we may allow log-Fano pairs.

\end{abstract}

\section{Introduction}

\input{introduction.tex}

\subsection{Outline of the proof}
\label{sec:outline}

\input{outline_proof.tex}

\subsection{Organization of the paper}

\input{organization.tex}

\subsection{Acknowledgements}

\input{acknowledgement.tex}

\section{Notation}
\label{sec:notation}

\input{notation.tex}

\section{The definition of the CM line bundle}
\label{sec:CM_definition}

\input{CM_definition.tex}

\section{The delta invariant and $K$-stability}
\label{sec:delta}

\input{delta_plus.tex}

\section{Growth of sections of vector bundles over curves}
\label{sec:growth}

\input{growth.tex}

\section{Ancillary statements}

\input{ancillary.tex}

\section{Semi-positivity  }
\label{sec:semi_positivity}

\input{proof.tex}

\section{Bounding the nef threshold}
\label{sec:nefness_threshold}

\input{nef_threshold.tex}

\section{Positivity}
\label{sec:positivity}

\input{ positivity.tex}

\section{Applications}
\label{sec:applications}

\input{applications.tex}

\section{Examples}
\label{sec:examples}

\input{example.tex}

\appendix

\section{Computations concerning the definition of the CM line bundle}
\label{sec:appendix}

\input{appendix.tex}

\bibliographystyle{skalpha}
\bibliography{includeNice}

\end{document}


TITLE: Given $A_{m\times n}$ and $B_{n \times m} (m<n)$. prove that AB is not singular and BA is singular
QUESTION [3 upvotes]: I have the following question which I can't seem to wrap my head around. I don't see how we can determine the desired just from the given info.

Given $A_{m\times n}$ and $B_{n \times m}$ $(m<n)$. prove that AB is not singular (for every A) and BA is singular

Thanks for the help.
EDIT: Question in another form (closer to original text):

Given $A_{m\times n}$ and $B_{n \times m} (m<n)$.
1) Is AB Singular?
2) Is BA Singular?

My answers say that 1 is false and 2 is true.

REPLY [3 votes]: If $A$ is $ m \times n $ for $ m < n $, then the columns of $A$ are vectors in $\mathbb{R}^m$ (or whatever the field is). Since there are more than $ m $ of them, they must be linearly dependent and so there are nontrivial solutions to $A\mathbf{x} = \mathbf{0}$.
Multiplying by $B$ on the left of both sides of this equation gives $BA \mathbf{x} = B\mathbf{0}$ so $BA \mathbf{x} = \mathbf{0}$ (albeit a different zero vector). Since $A\mathbf{x} = \mathbf{0}$ had a nontrivial solution, so must $(BA)\mathbf{x} = \mathbf{0}$ and hence $BA$ is singular.
It is possible that $AB$ is singular or non-singular. For example, if $A$ is a zero matrix then $AB$ is also a zero matrix (of a different size) and so must be singular. However, for example, if $A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$ and $B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0\end{pmatrix}$ then $AB = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ and $AB$ is nonsingular.
In general, if the columns of $B$ define combinations of the columns of $A$ that are independent, then $AB$ will be nonsingular.


TITLE: convergence of geometric mean
QUESTION [0 upvotes]: Let $\{w_n\}_{n=0}^{\infty}$ be a bounded sequence of positive real numbers such that $w=\text{sup}\{w_n\}$. Suppose the subsequence $\{w_{n_{i}}\}_{i=0}^{\infty}$ of the sequence $\{w_n\}$ convergence to zero then does this implies that the geometric mean $(w_0w_1\cdots w_n)^{1/n}$ converges to zero?
I am not sure how to partition the set $(w_0w_1\cdots w_n)^{1/n}$ to check the convergence. Thanks in advance.

REPLY [2 votes]: As the question is currently phrased, it doesn't imply that the geometric mean goes to $0$. Consider the following sequence
$$1/2, 2, 1/4, 2, 2, 1/8, 2,2,2, 1/16, 2,2,2,2, \ldots$$
The sequence is the sequence $1/2^k$ with $k$ $2$s in between $1/2^k$ and $1/2^{k+1}$.
This sequence is bounded, and has a subsequence that goes to $0$. Namely, $1/2, 1/4, 1/8, 1/16, \ldots$.
However, if we group $1/2^k$ with the $k$ $2$s that follow it, then these multiply out to $1$. Hence, every so often, the geometric mean of the sequence will be equal to $1$.

However, let us consider the case, when $w_i$ converges to $0$ instead of only having a subsequence that converges to $0$. Then by the AM-GM inequality, we have that the geometric mean is bounded by the arithmetic mean.
Let $\epsilon > 0$. Then there exists a $N$ such that for all $i > N$ we have that $w_i < \epsilon$. Thus, we have that for all $n > N$.
$$ \sum_{i = 1}^n\frac{w_i}{n} \le \frac{1}{n} \sum_{i=1}^N (w_i) + \epsilon. $$
Taking the limit of $n$ to infinity, we see that the arithmetic mean is at most $\epsilon$. Since this is true for arbitrary positive $\epsilon$, we that arithmetic mean (and hence the geometric mean) goes to $0$.


TITLE: The domain of fractional exponents
QUESTION [2 upvotes]: Take the following:
$$f(x) = x^{6/4}$$
The domain of this function is all real numbers. This function can be simplified to:
$$f(x) = x^{3/2}$$
The domain of this function is all real numbers greater than or equal to 0. Why is this true? Why does simplifying the function change its domain?

REPLY [0 votes]: The problem is that
$$
x^{(m/n)} = (x^m)^{1/n}
$$
is only valid if $x$ is positive.  So in other words, while of course it is true that
$x^{(6/4)} = x^{(3/2)}$,
you seem to be interpreting this to mean $(x^6)^{1/4} = (x^3)^{1/2}$, which doesn't follow.


TITLE: Why an electron does not get stuck to nucleus?
QUESTION [1 upvotes]: An electron remains in its orbit because of electrostatic and centrifugal force. But when a reaction takes place some electrons are gained or removed. Then how they still are stable?

REPLY [1 votes]: An electron is removed or added in outer orbitals. There is slight variation in Z_eff. but overall the total energy of electron - proton system remains negative which makes the electron bounded around the nucleus.


TITLE: Are $\frac{\pi}{e}$ or $\frac{e}{\pi}$ irrational?
QUESTION [7 upvotes]: Is it clear whether $\displaystyle \frac{\pi}{e}$ or $\displaystyle \frac{e}{\pi}$ are irrational or not?
If not, then there would exist $q,p\in \mathbb{Z}$ such that $$p\cdot \pi = q\cdot e$$

REPLY [5 votes]: A QUITE SIMPLE REMARK  $$\begin{cases}\frac{e}{\pi}=t\\e+\pi=s\end{cases}\qquad (*)$$ would imply $$\pi=\frac{s}{t+1}\\e=\frac{st}{t+1}$$ Consequently and least one of $t$ and $s$ in (*) must be trascendental.


TITLE: Given $ab+c$, $bc+a$, $ca+b$, find $(a - b)(b - c)(c - a)(a - 1)(b - 1)(c - 1)$
QUESTION [0 upvotes]: Three numbers $a$, $b$ and $c$ satisfy $ab + c = 10$, $bc + a = 11$, $ca + b = 14$. Find the value of $(a - b)(b - c)(c - a)(a - 1)(b - 1)(c - 1)$.
How do I solve this problem? I have tried numerous algebraic equalities, but they don't seem to work out.

REPLY [0 votes]: Equation 1 is $ab+c=10$, equation 2 is $bc+a=11$, and equation 3 is $ca+b=14.$
Subtract eq. 3 from eq. 2 and factor to obtain $(a-b)(c-1)=3.$
Subtract eq. 3 from eq. 1 and factor to obtain $(b-c)(a-1)=-4.$
Subtract eq. 2 from eq. 1 and factor to obtain $(c-a)(b-1)=-1.$
Multiply the 3 numbers above and you get 12.


TITLE: If $X$ and $Y$ are finite etale covers of each other, are they isomorphic?
QUESTION [4 upvotes]: This is a somewhat strange question perhaps, but I was wondering the following:
Suppose $X$ and $Y$ are schemes (lets say Noetherian, and integral as well if you'd like). Suppose that there are maps $f: Y \rightarrow X, g: X \rightarrow Y$ which realize $Y$ as a finite etale cover of $X$, and vice versa. Does it follow that $X$ and $Y$ have to be isomorphic?
I would be happy with any result along these lines. That is, if it's not always true, are there nice situations where it is? Knowing about the case where $X, Y$ are assumed affine would be just fine too.

REPLY [4 votes]: This is just a comment, but I don't have enough reputation yet.
It's true for compact hyperbolic curves (=smooth projective curves of genus at least two) for trivial reasons. In fact, if $X\to Y$ is a finite etale morphism of compact hyperbolic curves of degree $d$ and $Y\to X$ is a finite etale morphism of degree $e$ we obtain that $$2g_X -2 = (2g_Y-2)d = (2g_X-2)dd^\prime.$$ This implies that $dd^\prime =1$ and thus $d=d^\prime = 1$.
More generally, the above approach shows the following. Suppose that $f:X\to Y$ is finite etale and $g:Y\to X$ is finite etale, where $X$ and $Y$ are smooth projective varieties. Then, the "Riemann-Hurwitz formula" implies that $$K_X = f^\ast K_Y = f^\ast g^\ast K_X = (gf)^\ast K_X.$$ Maybe this implies that $K_X$ is torsion, but I'm not sure. Of course, I'm assuming $\deg g, \deg f>1$.
It might be more natural to just consider the isomorphism $(gf)^\ast \Omega^1_X \to \Omega^1_X$. You can compute the Euler characteristic of $X$ and $Y$ by taking the $n$-th Chern class ($n=\dim X=\dim Y$), and then you see that the Euler characteristic of $X$ (and $Y$) is zero (if the above surjective map is an isomorphism).


TITLE: Direct sum of module and isomorphism
QUESTION [1 upvotes]: Would you please help me to prove the following result?
If $A$ is an abelian group and $n\in \mathbb Z$ then we define
$$A[n]=\left\{a\in A| na=0\right\}$$
$$T(A)=\cup_{n\ge 1} A[n]$$
and if $p$ is a prime number $$T_p(A)=\cup_{k\ge 1} A[p^k]$$

Show that the map $x\mapsto (x_p)$ where $x_p$ is the $p-$th part of $x$ is an isomorphism from $T(A)$ to $\oplus_{p} T_p(A)$

( $x=x_px_{p′}$ where $x_p$ is the $p−$th part (has order a power of $p$)
Thanks

REPLY [1 votes]: The existence of a $p$-th part (in some way) already assumes the correctness of the statement you are asking for, at least for finitely generated abelian groups. Let me try to give a more natural discussion of the underlying question.
There is a natural morphism (for example via definition of the direct sum) $$\bigoplus_p T_p(A) \rightarrow A$$ and one readily checks (for example by direct computation) that this factorizes as $$\bigoplus_p T_p(A) \stackrel{f}\rightarrow T(A) \hookrightarrow A.$$
I claim that $f$ is an isomorphism and we will actually use this isomorphism to define the $p$-th part of an element in $T(A)$ and it will then be clear that it's inverse is the morphism in question.
One can certainly formulate the following argument more elegantly; I will try to keep the notation as elementary as possible though.
Injectivity follows from the definition ($f$ is a direct sum of inclusions). So we need to show surjectivity. Let $x \in T(A)$ with $s \cdot x = 0$. If $s$ is of the form $p^n$, then $x \in T_p(A)$ and we are done. Now we do induction over the number of different primes appearing in the prime decomposition of $s$. Assume $s= p_1^{n_1} \cdots p_m^{n_m}$ and the statement holds true for upto $m-1$ factors for elements $x$ in arbitry abelian groups. By induction, we find $y' \in f^{-1}(<x>)$ such that $f(y')=p_1^{n_1}x$. On the other hand, again by induction, we find $y'' \in f^{-1}(<x>/<p_1^{n_1}x>)$ such that $f(y'')= x + c \cdot p_1^{n_1} x$ for some $c \in \mathbb{Z}$. Now $y'' - cy'$ yields the desired preimage.