Somemathhere

Truncated exponential series equation

$\textbf{Problem}.$ For a positive integer $n$ let $x_n$ be the unique positive real root of the equation

$$\sum_{k=0}^n \frac{x^k}{k!}=\frac{e^x}{2}.$$

Prove that $\displaystyle\lim_{n\to\infty}(x_n-n)=\frac{2}{3}.$

$\textbf{Comment.}$ The limit $\displaystyle\lim_{n\to\infty} e^{-n}\sum_{k=0}^n \frac{n^k}{k!}$ is well known to be $\displaystyle\frac{1}{2}$. It could be derived via nice probabilistic structure related to Poisson distribution. This limit hints that the value of the root $x_n$ should be close to $n$.

$\textbf{Sketch of a solution of the problem}$. Defining

$$g(x)=\frac{1}{n!}\int_0^x s^ne^{-s}\ ds-\frac{1}{2}$$

the original equation could be rewritten in the form $g(x)=0.$ One should observe that $g$ is monotonically increasing and the unique root is in the interval $(n,n+1)$. Then one uses one iteration of the Newton method initialized at $n$ to obtain an approximation of the solution $\tilde x_n$. Using the final asymptotic obtained at the end of the this answer and Stirling approximation, one obtains that $\displaystyle\lim_{n\to\infty}(\tilde x_n-n)=\frac{2}{3}.$ It remains to use the estimate of the error in the Newton method (one needs the first and second derivatives of $g$ here, which are easy to write), to see that $\lim_{n\to\infty}(x_n-\tilde x_n)=0$.

Proof of Gelfand-Phillips Theorem

$\textbf{Theorem.}$ Let $X$ be a Banach space and $A\subseteq X$. Prove that $A$ is precompact (in the norm) if and only if for every $w^*$-convergent to $\textbf{0}$ sequence $\{x_n^*\}_{n\ge 1}\subseteq X^*$ it holds that $\{x_n^*\}_{n\ge 1}$ converges uniformly to $\textbf{0}$ on $A.$

$\textbf{Proof.}$ If $A$ is precompact the result follows from Arzela-Ascoli theorem (combined with the fact that $w^*$-convergent sequences are norm bounded).

Now we prove the reverse direction.

First we proof the following characterization of compactness in normed spaces: $A$ is compact if and only if $A$ is bounded and for any $\varepsilon>0$ there exists a finite-dimensional space $F$ such that $A\subseteq F+\varepsilon\mathbf{B}.$

$\textit{Proof}.$

If $A$ is precompact, then for any $\varepsilon>0$ there exists $\{a_i\}_{i=1}^n\subseteq A$ such that $A\subseteq\bigcup_{i=1}^n\mathbf{B}_{\varepsilon}(a_i)$. In particular $A$ is bounded and
\[A\subseteq \text{span}(\{a_i\}_{i=1}^n)+\varepsilon\textbf{B}.\]
For the reverse direction, let $\varepsilon>0$ and $F$ be finite-dimensional space such that $A\subseteq F+\frac{\varepsilon}{3}\mathbf{B}.$ For each $a\in A$ choose $f_a\in F$ with $\|a-f_a\|\le\varepsilon/3$. Since $A$ is bounded and $F$ is finite-dimensional, the set $\{f_a\}_{ a\in A}$ is precompact.
Thus there exists $\{f_{a_i}\}_{i=1}^n\subseteq F$ such that $ \{f_a\}_{a\in A}\subseteq \bigcup_{i=1}^n\textbf{B}_{\varepsilon/3}(f_{a_i})$.
Now let $a\in A$ be arbitrary. Then there exists $i\in \{1,2,\ldots,n\}$ such that $\|f_a-f_{a_i}\|<\varepsilon/3.$ Consequently
\[\|a-a_i\|\le\|a-f_a\|+\|f_a-f_{a_i}\|+\|f_{a_i}-a_i\|<\varepsilon,\]
hence $\{a_i\}_{i=1}^n\subseteq A$ is a finite $\varepsilon$-net for $A.$ $\square$

Now let $A$ be a set which is not precompact. If it is unbounded, the results follows easily. Assume otherwise. Thus there exists $\varepsilon>0$ such that for any finite-dimensional space $F$, there exists $a\in A$ with $\text{d}(a,F)\ge\varepsilon.$ Choose a sequence $\{x_i\}_{i\ge 1}\subseteq X$ which is dense in $X$. Let $F_n:=\text{span}(\{x_i\}_{i=1}^n).$ Choose $a_n\in A$ with $\text{d}(a_n,F_n)\ge\varepsilon.$ Using Hahn-Banach construct $x_n^*\in X^*$ such that $\langle x_n^*,a_n\rangle\ge\varepsilon$, $\|x_n^*\|=1$ and $F_n\subseteq\text{ker}(x_n^*)$.
Thus for every $n$ \[\sup_{a\in A}|\langle x_n^*,a\rangle|\ge\varepsilon,\]
hence $\{x_n^*\}_{n\ge 1}$ does not converge uniformly to $\mathbf{0}$ on $A$. On the other hand $\bigcup_{n\ge 1}F_n$ is dense in $X$. Fix $x\in X$ and let $\delta>0$ be arbitrary. Then there exists $m$ such that for some $z_m\in F_m$ it holds that $\|z_m-x\|<\delta$. For $n\ge m$ it holds that $\langle x_n^*,z_m\rangle=0$, hence
\[|\langle x_n^*,x\rangle|= |\langle x_n^*,z_m-x\rangle|\le \|x_n^*\|\|z_m-x\|<\delta.\]
Consequently $\{x_n^*\}_{n\ge 1}$ is weak$^*$ convergent to $\mathbf{0}.$

Closed orbits are finite

Let $f:[a,b]\to [a,b]$ be continuous function and $x_0\in [a,b]$. Consider the sequence $X=\{x_n\}_{n\ge 0}$ defined by $x_n=f(x_{n-1})$ for $n\ge 1$. Assume that $X$ is a closed set. Prove that it consists of finitely many elements. (The problem is taken from IMC 2002. The set $X$ is called the orbit of $f$ starting from $x_0$)

$\textbf{Proof.}$ Let us assume that $X$ is infinite. So it has a limit point, which should belong to the set (since it is closed). Let $$n_0:=\min\{n\ | \ x_n \text{ is a limit point of } X \}.$$ Then define $\hat X=\{x_n\}_{n\ge n_0+1}$. Thus $\hat X\cup \{x_{n_0}\}$ is compact and $f:\hat X\cup\{x_{n_0}\}\to \hat X$ is a continuous function. Since the image of compact sets under continuous functions are compact set, we must have that $\hat X$ is compact as well. But it is clearly not closed, since $x_{n_0}$ is a limit point $\hat X$ and does not belong to $\hat X$.

There is no lowest rate of convergence

Let $\{a_n\}_{n\ge 1}$ be a sequence of positive numbers such that

$$\sum_{n=1}^{\infty} a_n$$ is convergent. Then there exists a sequence $\{b_n\}_{n\ge 1}$ with $\displaystyle \lim_{n\to \infty}\frac{b_n}{a_n}=\infty$ and such that

$$\sum_{n=1}^{\infty} b_n$$ is also convergent.

First proof (a la Calculus I, based on ideas of Zhivko Petrov). Consider $$S_n=\sum_{k=n}^{\infty}a_k.$$ Clearly $S_n\to 0$. Define $$b_n=\sqrt{S_n}-\sqrt{S_{n+1}}.$$

Clearly $b_n>0$ for all $n$ and $b_n\to 0$. Moreover

$$\sum_{n=1}^\infty b_n=\sqrt{S_1},$$ hence is convergent.

On the other hand $$\lim_{n\to\infty}\frac{b_n}{a_n}=\lim_{n\to\infty}\frac{1}{\sqrt{S_n}+\sqrt{S_{n+1}}}=\infty.$$

Second proof. (Based on Folland's book) Assume on the contrary that there is lowest decaying sequence, i.e.

for some sequence $a=\{a_n\}_{n\ge 1}$ with convergent series, holds that for any sequence of positive numbers $\{b_n\}_{n\ge 1}$, the series $$\sum_{n=1}^\infty a_nb_n$$ is convergent if and only if $\{b_n\}_{n\ge 1}$ is bounded (the if part holds for any sequence $\{a_n\}_{n\ge 1}$ with convergent series).

This implies that the linear operator $T:\ell_{\infty}\to\ell_1$ defined by

$$T(c_1,c_2,\ldots)=(a_1c_1,a_2c_2,\ldots)$$

is not only well defined but also surjective ( due to the "only if" part above). Moreover the map is injective, since $a$ has only nonzero terms. The map is clearly bounded (by the norm of $a$), so the bounded inverse mapping theorem implies that the inverse $T^{-1}:\ell_1\to\ell_\infty$ is also bounded, hence continuous operator. Now it remains to observe that the image of $c_{00}$ under $T^{-1}$ is again $c_{00}$. However, $c_{00}$ is dense in $\ell_1$ and its image under continuous map should be dense in $\ell_\infty$, but the image (which is again $c_{00}$) is clearly not dense in $\ell_\infty$

Two functional inequalities

$\textbf{Problem 1.}$ Find all functions $f:\mathbb{R}\to\mathbb{R}$ such that for all $x$ and $y$ holds

$$f(x)f(x+y)\ge f(x)^2+xy.$$

$\textbf{Problem 2.}$ Find all differentiable functions $f:\mathbb{R}\to\mathbb{R}$ with $f(0)=0,\ f(1)=1$ and such that for all $x$ and $y$ holds

$$f(x+y)\ge 2022^xf(x)+f(y).$$

Haudorff dimension and Liouville numbers

In this post we present a proof of the fact the the set of Liouville numbers contained in $[0,1]$ has Hausdorff dimension $0$.

Why is this result interesting, apart from finding explicitly the Hausdorff dimension of a particular set? Regarding Lebesgue measure, it is not obvious whether there exists an uncountable set with measure zero. Lioville numbers serve as such example. However, Liouville numbers even serve as an example of an uncountable set with Hausdorff dimension zero, and this is much stronger. That is because every set of dimension zero has measure zero, whereas for example, another common reference of an uncountable set with measure $0$, the Cantor set, has positive Hausdorff dimension ($\ln 2/\ln 3$). Thus the set of Lioville numbers, is in a sense, way smaller than the Cantor set. One could also say that Liouville numbers are example of the smallest possible uncountable sets among the sets with measure zero. You can look here, for another construction of uncountable sets with dimension zero. Another interesting aspect of Liouville numbers is that they are $G_\delta$-dense in $[0,1]$ (which is a property stronger than uncountability). Hence Liouville numbers are big in sense of cardinality and topology, yet among the smallest with respect to measure and dimension.

Preliminary notions. We recall the definition of Hausdorff dimension.
For a subset $U$ of a metric space (e.g. real line), define $\operatorname{diam}(U)$ to be the diameter of $U$, i.e. the supremum of distances between any two elements of $U$. If $U$ would be an interval, that is just its length. Now for a set $X$, for $d\ge 0$ (which would take the role of a dimension) and $\delta>0$ define
$$H_\delta^d(X)=\inf\left \{\sum_{i=1}^\infty (\operatorname{diam} U_i)^d: X\subseteq\bigcup_{i=1}^\infty U_i,\ \operatorname{diam} U_i<\delta\right \}.$$
One observes that this is nonincreasing as a function of $\delta$ (smaller $\delta$ - less covers $\{U_n\}_{n\ge 1}$). Thus we define $$\displaystyle\mathcal{H}^d(X)=\sup_{\delta>0}H_\delta^d(X)=\lim_{\delta\to 0}H_\delta^d(X).$$ This turns out to be a measure (defined at least on the Borel $\sigma$-algebra (the one containing all open sets)); it is called $d$-dimensional Hausdorff measure. One may observe that $\mathcal{H}^d(X)$ is nonincreasing as a function of $s$ with values in $[0,\infty]$, and may obtain at most one finite nonzero value (consider for example subset of $[0,1]$).
Define the Hausdorff dimension as the $d$ for which we switch from measure $\infty$ to measure $0$, i.e.
$$\dim_{\operatorname{H}}{(X)}=\inf\{d\ge 0: \mathcal{H}^d(X)=0\}.$$

To the problem. We want to show that the set of Liouville numbers in $[0,1]$ has dimension $0$. Denote this set by $L$. Recall that by definition $x\in L $ iff for each positive integer $n$ there exist infinitely many positive integers $p,q$, such that $$\left|x-\frac{p}{q}\right|<\frac{1}{q^n}.$$
Pay attention, the usual definition requires existence of at least one such pair $p,q$; it is easy to observe that if there exists at least one pair for each $n$, then there exist infinitely many pairs for each $n$.

So let us unpack what it means for a set to have dimension $0$. Going back to the above definitions (in reverse order) we see that it suffices to show that for any $s>0$ holds $\mathcal{H}^d(X)=0$. This in turn reduces to showing that for $\delta>0$ holds $H_\delta^d(X)=0$. This means that
$$\inf\left \{\sum_{i=1}^\infty (\operatorname{diam} U_i)^d: X\subseteq\bigcup_{i=1}^\infty U_i,\ \operatorname{diam} U_i<\delta\right \}=0$$
Finally, unwrapping the infimum we may summarise the task to be done as follows:

For any $d>0$, $\delta>0$ and $\varepsilon>0$ there exists a countable collection $\{U_i\}_{i\ge 1}$ such that: $\displaystyle X\subset \bigcup_{i\ge 1}U_i$, $\operatorname{diam}U_i<\delta$ for all $i$ and
$$ \sum_{i=1}^\infty (\operatorname{diam} U_i)^d<\varepsilon.$$ So fix $d>0$, $\delta>0$ and $\varepsilon>0$. We may assume $d<1$. Fix $\displaystyle n>\frac{3}{d},\ q_0>\max\left\{\frac{2}{\delta},\frac{2}{\varepsilon}\right\}$ and consider
$$I_{p,q}:=\left(\frac{p}{q}-\frac{1}{q^n},\frac{p}{q}+\frac{1}{q^n}\right).$$ One observes that (recalling the modified, still equivalent defintion, we stated) $$L\subset \bigcup_{q>q_0}\bigcup_{p=1}^{q-1}I_{p,q}$$ Moreover $\displaystyle\operatorname{diam}I_{p,q}=\frac{2}{q^n}<\frac{2}{q_0}<\delta.$ Finally
$$\sum_{q>q_0}\sum_{p=1}^{q-1}(\operatorname{diam}I_{p,q})^d\le\sum_{q>q_0}\frac{2^d}{q^{nd}}q\le 2\sum_{q>q_0}\frac{1}{q^{nd-1}}\le 2\sum_{q>q_0}\frac{1}{q^{2}}\le \frac{2}{q_0}<\varepsilon.$$ In the above we used the inequality $$\sum_{k>n}\frac{1}{k^2}\le \frac{1}{n}$$ which could be proven, for example, by estimating the sum from above by $\displaystyle \int_n^\infty\frac{1}{x^2}dx$.

Thus the proof is finished.

You can also check the wikipedia articles for further information on Hausdorff dimension and Liouville numbers.

Problem proposed by prof. Gadjev

$\textbf{Problem.}$

Let $f:[0,1]\to\mathbb{R}$ be a continuous function.

Find the limit

$$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n f\left(\frac{\ln k}{\ln n }\right).$$

$\textbf{Solution.}$

Fix $\varepsilon>0$. We aim to show that for large enough $n$

$$\left|\frac{1}{n}\sum_{k=1}^n f\left(\frac{\ln k}{\ln n }\right)-f(1)\right|<3\varepsilon$$

which would mean that the limit is $f(1).$

Let $M$ be an upper bound for $|f|$ on $[0,1]$, i.e. $|f(x)|\le M$ for all $x\in [0,1].$

For all $n\ge 1$ define $$k(n)=\left\lfloor\frac{n}{n^{1/\sqrt{\ln n}}}\right\rfloor.$$

The number is chosen in such a way that $$\lim_{n\to\infty}\frac{k(n)}{n}=0 \ \ \& \ \ \lim_{n\to\infty}\frac{\ln(k(n))}{\ln n}=1.$$

Split the sum in two:

$$\left|\frac{1}{n}\sum_{k=1}^n f\left(\frac{\ln k}{\ln n }\right)-f(1)\right|\le \left|\frac{1}{n}\sum_{k=1}^{k(n)} f\left(\frac{\ln k}{\ln n }\right)\right|+\left|\frac{1}{n}\sum_{k=k(n)+1}^{n} f\left(\frac{\ln k}{\ln n }\right)-f(1)\right| \ \ \ (*)$$

Take $n_1$ such that for $n>n_1$ holds $\displaystyle \frac{k(n)}{n}<\frac{\varepsilon}{M}$. For the first summand on the right, using the triangle inequality, we obtain

$$\left|\frac{1}{n}\sum_{k=1}^{k(n)} f\left(\frac{\ln k}{\ln n }\right)\right|\le \frac{1}{n}\sum_{k=1}^{k(n)} \left|f\left(\frac{\ln k}{\ln n }\right)\right|\le \frac{Mk(n)}{n}<\varepsilon$$

when $n>n_1$.

Now take $\delta>0$ such that when $|x-1|<\delta$ holds $|f(x)-f(1)|<\varepsilon$. Take $n_2$ such that for $n>n_2$ holds $\displaystyle \left|\frac{\ln(k(n))}{\ln n}-1\right|<\delta.$ Now for $n>\max\{n_1,n_2\}$ we obtain

$$\left|\frac{1}{n}\sum_{k=k(n)+1}^{n} f\left(\frac{\ln k}{\ln n }\right)-f(1)\right|\le \sum_{k=k(n)+1}^{n} \frac{1}{n}\left|f\left(\frac{\ln k}{\ln n }\right)-f(1)\right|+\left|\frac{k(n)}{n}f(1)\right|<\frac{n-k(n)}{n}\varepsilon+\varepsilon\le 2\varepsilon$$

Thus for $n>\max\{n_1,n_2\}$ from $(*)$ we obtain

$\textbf{Remark.}$ We only used that the function $f$ is bounded and continuous at $1$. The proof heavily relied on the existence of the function (sequence) $k$. Functions, for which such function $k$ exists (like $\ln$) are called super slowly varying. They arise in Probability theory. The same proof could be carried for any such function.

The proof proposed from Prof. Gadjev relies on the following equivalences

$$\sum_{k=1}^n f\left(\frac{\ln k}{\ln n }\right)\equiv\int_1^n f\left(\frac{\ln x}{\ln n }\right)dx\underbrace{=}_{x=n^y}\int_0^1 f\left(y\right)\ln(n)n^ydy$$

and consequently $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n f\left(\frac{\ln k}{\ln n }\right)=\lim_{n\to\infty}\int_0^1 \frac{\ln n}{n}n^y f\left(y\right)dy.$$

This reasoning could be made rigorous. After that, what remains is to observe that the sequence

$ \displaystyle\frac{\ln n}{n-1}n^y$ tends to the Dirac Delta function at $1$.