In what follows, we will prove that every Hilbert-Schmidt integral operator is compact.
Formally, let $k\in L_2([0,1]\times[0,1])$ and $T:L_2[0,1]\to L_2[0,1]$ be defined by
$$Tf(x):=\int_0^1k(x,y)f(y)dy.$$
Then $T$ is compact operator.
Although the proof may seem a bit long at first sight, it is proceeds naturally, utilizing approximation of $k$ with continuous functions.
$\textbf{Proof}$. We approximate $k$ with a sequence of continuous functions, then prove that each of the corresponding operators has image contained in $C[0,1]$, then show that each of these operators is compact when $C[0,1]$ is equipped with the $\sup$ norm. This will be done via the Arzela-Ascoli theorem. Finally show that these converge uniformly (in the operator norm) to the original operator, and since they are compact, the original must be as well.
The Cauchy-Bunyakovsky-Schwartz inequality is used throughout the proof.
Thus we start by choosing a sequence $(k_n)_{n\ge 1}$ of continuous functions converging to $k$ in the sense of $L_2$ norm, i.e.
$$\lim_{n\to\infty}\int_0^1(k_n(x)-k(x))^2\text{d}x=0.$$
Such a sequence could be constructed using the Fourier decomposition of $k$ into sines for example.
Then for any $n\ge 1$ define $$T_nf(x):=\int_0^1k_n(x,y)f(y)dy.$$
Fix $m\ge 1$ and for brevity denote $S=T_m$.
First we show that $\text{Im} S\subseteq C[0,1]$. Let $f\in L_2[0,1]$. We aim to show that $Sf$ is a continuous function. Indeed, let $x\in [0,1]$ and $(x_n)_{n\ge 1}$ be a sequence in $[0,1]$ converging to $x$. Then, if we denote $g_n(y)=k_m(x_n,y)$, we have
$$\lim_{n\to\infty}g_n(y)=k_m(x,y)$$
Moreover, if $\displaystyle C:=\sup_{x\in[0,1]}|k_m(x,y)|$ (finite, since $k_m$ is continuous), then $|g_n(y)|=|k_m(x_n,y)|\le C$. Thus Dominated convergence theorem is applicable, hence
$$\lim_{n\to\infty}Sf(x_n)=\lim_{n\to\infty}\int_0^1g_n(y)f(y)\text{d}y=\int_0^1k_m(x,y)f(y)\text{d}y=Sf(x).$$
So $S:L_2[0,1]\to C[0,1]$.
Next, equip $C[0,1]$ with the $\sup$ norm. We will prove $S$ is compact. To this end, we take a sequence $(f_n)_{n\ge 1}\subset L_2[0,1]$, such that $\|f_n\|_2\le 1$ for all $n$, and we are going to prove that $(Sf_n)_{n\ge 1}$ has a convergent subsequence in $C[0,1]$. The criterion telling us whether this is true is the Arzela-Ascoli theorem.
From the Cauchy-Bunyakovsky-Schwartz inequality we obtain $$|Sf_n(x)|=\left|\int_0^1 k_m(x,y)f_n(y)\text{d}y\right|\le \sqrt{\int_0^1k_m(x,y)^2\text{d}y\int_0^1f_n(y)^2\text{d}y}\le C$$
(for $\displaystyle C:=\sup_{x\in[0,1]}|k_m(x,y)|$) and thus the sequence $(Sf_n)_{n\ge 1}$ is uniformly bounded.
Moreover, let $\varepsilon>0$. Then there is some $\delta>0$ such that whenever $|x_1-x_2|< \delta$, then $|k_m(x_1,y)-k_m(x_2,y)|<\varepsilon$ for all $y\in[0,1]$ (uniform continuity of continuous functions).Thus for any $n$ and any $x_1,x_2$, such that $|x_1-x_2|<\delta$ we have
$$|Sf_n(x_1)-Sf_n(x_2)|=\left|\int_0^1(k_m(x_1,y)-k_m(x_2,y))f_n(y)\text{d}y\right|$$
$$\le \sqrt{\int_0^1(k_m(x_1,y)-k_m(x_2,y))^2\text{d}y \int_0^1 f_n(y)^2\text{d}y}\le \varepsilon$$
This shows that the sequence $(Sf_n)_{n\ge 1}$ is equicontinuous. Thus it contains convergent subsequence.
This concludes the proof that $(T_m)_{m\ge 1}$ is a sequence of compact operators (acting from $L_2[0,1]$ to $C[0,1]$). Moreover, for any $f\in C[0,1]$, $\|f\|_{\infty}\ge \|f\|_2$, which means that the $L_2$ topology on $C[0,1]$ is weaker than the uniform topology. Hence the operators $T_m$, $m\ge 1$, are compact, even if we consider them from $L_2[0,1]$ to $L_2[0,1]$.
It remains to observe that $T_m$ converges to $T$ in the operator norm.
Let $f\in L_2[0,1]$. Then
$$\|T_mf-Tf\|_2^2=\int_0^1\left(\int_0^1(k(x,y)-k_m(x,y))f(y)\text{d}y\right)^2\text{d}x\le$$
$$\int_0^1\int_0^1(k(x,y)-k_m(x,y))^2\text{d}y\int_0^1f(y)^2\text{d}y\text{d}x=\int_0^1\int_0^1(k(x,y)-k_m(x,y))^2\text{d}y\text{d}x\int_0^1f(y)^2\text{d}y=$$
$$\|k_m-k\|_2^2\|f\|_2^2.$$
This shows that
$$\|T_m-T\|\le \|k_m-k\|_2,$$
and since $(k_m)_{m\ge 1}$ was taken to converge to $k$ in $L_2$, then $T_m$ converges to $T$.
The proof is finished, by saying, that the space of compact operators is closed, and as $T_m$ are compact, so is $T$.
Absolutely convergent series over all functionals
Let $X$ be a normed vector space. Let $(x_n)_{n\ge 1}$ be a sequence in $X$, such that for any $f\in X^*$
$$\sum_{n=1}^{\infty}|f(x_n)|<\infty.$$
Then there exists a constant $C$ such that
$$\sum_{n=1}^{\infty}|f(x_n)|\le C\|f\|, \ \forall f\in X^*$$.
$\textbf{Proof}.$ Consider the operator $T:X^*\to l_1$, defined by
$$T(f)=(f(x_1),f(x_2),\ldots).$$
Clearly $T$ is well-defined linear operator. Moreover $T$ is bounded. We shall check that using the Closed-graph theorem ($X^*$ is Banach, even if $X$ is not). For this purpose take a sequence $(f_k)_{k\ge 1}\subset X^*$ converging to some $f$, and let $Tf_n\rightarrow p$ for some $p\in l_1$. Our aim is to show that $Tf=p$.
Since $Tf_k\rightarrow p$ (in $l_1$), we have that
$$\sum_{n=1}^{\infty}|f_k(x_n)-p_n|\rightarrow 0$$
as $k$ goes to $\infty$.
This means that for any $n\in\mathbb{N}$ we have
$$\lim_{k\to\infty}f_k(x_n)=p_n.$$
On the other hand, as $f_k\rightarrow f$, we have that
$$\lim_{k\to\infty}f_k(x_n)=f(x_n).$$
This means that $f(x_n)=p_n$, which implies that $Tf=p$, which is what we needed.
Now, the boundedness of $T$ implies that there is a constant $C$ such that
$$\|Tf\|_{l_1}\le C\|f\|$$
which was to be proved.
$\textbf{Comment}.$ We are tempted to say that the series
$$\sum_{n=1}^{\infty}x_n$$
are absolutely convergent, and afterwards, that there is some $x\in X$ which equals this sum (in which case the problem's constraint will be fulfilled). This however, needs not to be true (and the obstacle is not only that $X$ is not required to be Banach space).
Here is a (counter)example. Let $X=c_0$ and $x_n=e_n$ - the basis unit vectors. Then $(c_0)^*=l_1$ and for any $f\in l_1$ we have
$$\sum_{n=1}^{\infty}|f(e_n)|=\|f\|_{l_1}$$
so that the problem's constraint is satisfied. However, the series
$$\sum_{n=1}^{\infty}e_n$$
are not convergent.
Nevertheless, the problem's conclusion is correct, and the constant is $1$.
$$\sum_{n=1}^{\infty}|f(x_n)|<\infty.$$
Then there exists a constant $C$ such that
$$\sum_{n=1}^{\infty}|f(x_n)|\le C\|f\|, \ \forall f\in X^*$$.
$\textbf{Proof}.$ Consider the operator $T:X^*\to l_1$, defined by
$$T(f)=(f(x_1),f(x_2),\ldots).$$
Clearly $T$ is well-defined linear operator. Moreover $T$ is bounded. We shall check that using the Closed-graph theorem ($X^*$ is Banach, even if $X$ is not). For this purpose take a sequence $(f_k)_{k\ge 1}\subset X^*$ converging to some $f$, and let $Tf_n\rightarrow p$ for some $p\in l_1$. Our aim is to show that $Tf=p$.
Since $Tf_k\rightarrow p$ (in $l_1$), we have that
$$\sum_{n=1}^{\infty}|f_k(x_n)-p_n|\rightarrow 0$$
as $k$ goes to $\infty$.
This means that for any $n\in\mathbb{N}$ we have
$$\lim_{k\to\infty}f_k(x_n)=p_n.$$
On the other hand, as $f_k\rightarrow f$, we have that
$$\lim_{k\to\infty}f_k(x_n)=f(x_n).$$
This means that $f(x_n)=p_n$, which implies that $Tf=p$, which is what we needed.
Now, the boundedness of $T$ implies that there is a constant $C$ such that
$$\|Tf\|_{l_1}\le C\|f\|$$
which was to be proved.
$\textbf{Comment}.$ We are tempted to say that the series
$$\sum_{n=1}^{\infty}x_n$$
are absolutely convergent, and afterwards, that there is some $x\in X$ which equals this sum (in which case the problem's constraint will be fulfilled). This however, needs not to be true (and the obstacle is not only that $X$ is not required to be Banach space).
Here is a (counter)example. Let $X=c_0$ and $x_n=e_n$ - the basis unit vectors. Then $(c_0)^*=l_1$ and for any $f\in l_1$ we have
$$\sum_{n=1}^{\infty}|f(e_n)|=\|f\|_{l_1}$$
so that the problem's constraint is satisfied. However, the series
$$\sum_{n=1}^{\infty}e_n$$
are not convergent.
Nevertheless, the problem's conclusion is correct, and the constant is $1$.
Continuity of inf function
Let $X,Y$ be topological spaces, $Y$ is compact and $f:X\times Y\to \mathbb{R}$ be a continuous function. Define $$g(x)=\inf_{y\in Y}f(x,y)$$
Then $g$ is continuous.
$\textbf{Proof}$. It is enough to check that for all real $a$ the sets $g^{-1}((-\infty,a))$ and $g^{-1}((a,\infty))$ are both open in $X$.
First rewrite $$g^{-1}((-\infty,a))=\{x\in X\ | \ \inf_{y\in Y}f(x,y)<a\}=\{x\in X\ | \ \exists y\in Y, f(x,y)<a\}.$$
Observe that
$$\{x\in X\ | \ \exists y\in Y, f(x,y)<a\}=\bigcup_{y_0\in Y}\{x\in X\ | \ f(x,y_0)<a\}.$$ Since $f$ is continuous, the function $h_{y_0}(x)=f(x,y_0)$ is continuous as well. This means that the set $\{x\in X\ | \ f(x,y_0)<a\}$ is open (being preimage of the open interval $(-\infty,a)$ under the continuous function $h_{y_0}$). Hence $\{x\in X\ | \ \exists y\in Y, f(x,y)<a\}$ is a union of open sets - thus it is open.
Now $$g^{-1}((a,\infty))=\{x\in X\ | \ \inf_{y\in Y}f(x,y)>a\}.$$
Denote $$V_n=\left\{x\in X\ | \ \forall y\in Y,\ f(x,y)> a+\frac{1}{n}\right\}$$ so that $\displaystyle\bigcup_n V_n=\{x\in X\ | \ \inf_{y\in Y}f(x,y)>a\}$. Thus it suffices to prove that all of the $V_n$ are open. Fix $n$ and for brevity $V=V_n$ and $\displaystyle b=a+\frac{1}{n}$. We write
$$V=\{x\in X\ | \ \forall y\in Y,\ f(x,y)> b\}.$$
Assume $V$ is nonempty and let $\hat{x}\in V$. Since $f$ is continuous, for any $\bar{y}\in Y$ there are open neighbourhoods $U_\bar{y}$ of $\hat{x}$ and $W_\bar{y}$ of $\bar{y}$ such that for any $(x,y)\in U_\bar{y}\times W_\bar{y}$, $f(x,y)>b$. The sets $W_\bar{y}$ form an open cover of $Y$ and so we may choose $y_1,\ldots,y_n\in Y$ such that the sets $W_{y_i}$ also cover $Y$. Let $\displaystyle U=\bigcap_i U_{y_i}$. Thus $U$ is nonempty ($\hat{x}\in U$) open set. Let $x\in U$ and $y\in Y$. Thus $y\in W_{y_i}$ for some $i$, and so $(x,y)\in U_{y_i}\times W_{y_i}$ hence $f(x,y)>b$. Hence $x\in V$. This means that $U$ is an open neighbourhood of $\hat{x}$ which is contained in $V$. Thus $V$ is open.
Then $g$ is continuous.
$\textbf{Proof}$. It is enough to check that for all real $a$ the sets $g^{-1}((-\infty,a))$ and $g^{-1}((a,\infty))$ are both open in $X$.
First rewrite $$g^{-1}((-\infty,a))=\{x\in X\ | \ \inf_{y\in Y}f(x,y)<a\}=\{x\in X\ | \ \exists y\in Y, f(x,y)<a\}.$$
Observe that
$$\{x\in X\ | \ \exists y\in Y, f(x,y)<a\}=\bigcup_{y_0\in Y}\{x\in X\ | \ f(x,y_0)<a\}.$$ Since $f$ is continuous, the function $h_{y_0}(x)=f(x,y_0)$ is continuous as well. This means that the set $\{x\in X\ | \ f(x,y_0)<a\}$ is open (being preimage of the open interval $(-\infty,a)$ under the continuous function $h_{y_0}$). Hence $\{x\in X\ | \ \exists y\in Y, f(x,y)<a\}$ is a union of open sets - thus it is open.
Now $$g^{-1}((a,\infty))=\{x\in X\ | \ \inf_{y\in Y}f(x,y)>a\}.$$
Denote $$V_n=\left\{x\in X\ | \ \forall y\in Y,\ f(x,y)> a+\frac{1}{n}\right\}$$ so that $\displaystyle\bigcup_n V_n=\{x\in X\ | \ \inf_{y\in Y}f(x,y)>a\}$. Thus it suffices to prove that all of the $V_n$ are open. Fix $n$ and for brevity $V=V_n$ and $\displaystyle b=a+\frac{1}{n}$. We write
$$V=\{x\in X\ | \ \forall y\in Y,\ f(x,y)> b\}.$$
Assume $V$ is nonempty and let $\hat{x}\in V$. Since $f$ is continuous, for any $\bar{y}\in Y$ there are open neighbourhoods $U_\bar{y}$ of $\hat{x}$ and $W_\bar{y}$ of $\bar{y}$ such that for any $(x,y)\in U_\bar{y}\times W_\bar{y}$, $f(x,y)>b$. The sets $W_\bar{y}$ form an open cover of $Y$ and so we may choose $y_1,\ldots,y_n\in Y$ such that the sets $W_{y_i}$ also cover $Y$. Let $\displaystyle U=\bigcap_i U_{y_i}$. Thus $U$ is nonempty ($\hat{x}\in U$) open set. Let $x\in U$ and $y\in Y$. Thus $y\in W_{y_i}$ for some $i$, and so $(x,y)\in U_{y_i}\times W_{y_i}$ hence $f(x,y)>b$. Hence $x\in V$. This means that $U$ is an open neighbourhood of $\hat{x}$ which is contained in $V$. Thus $V$ is open.
Some integrals
Evaluate $$\int_{0}^{\pi/2}(\tan x)^a\text{d}x$$
$$\int_{0}^{\pi/2}\int_{0}^{\pi/2}\left(\frac{\sin x}{\sin y}\right)^a\text{d}x\text{d}y$$
(in particular for $a=1/2$, the answes is $\pi$.)
Solution. Use the Beta function trigonometric definition.
$$\int_{0}^{\pi/2}\int_{0}^{\pi/2}\left(\frac{\sin x}{\sin y}\right)^a\text{d}x\text{d}y$$
(in particular for $a=1/2$, the answes is $\pi$.)
Solution. Use the Beta function trigonometric definition.
Determinant of arithmetic functions
Let $$f(a,b)=\sum_{d|a, \ d|b}d.$$ Let $M=(a_{i,j})_{i,j=1}^{n}$. Evaluate $\det M$.
Solution. The idea is utilization of Lower-upper triangular decomposition. Using a software (like Mathematica) one observes that for small $n$ the matrices $L$ and $U$ coulde be intepreted as - $L=(l_{i,j})_{i,j=1}^{n}$, where $$l_{i,j}=\begin{cases} 1, & \text{j divides i}\\
0, & \text{otherwise} \end{cases}$$ and $U=(u_{i,j})_{i,j=1}^{n}$ where $$u_{i,j}=\begin{cases} i, & \text{i divides j}\\
0, & \text{otherwise} \end{cases}$$
It is directly verified that this holds in general (all $n$).
Obviously $\det L=1$, while $\det U=n!$ (the diagonal elements are $1,2,\ldots,n$). Thus $\det M=n!$.
The same idea could be employed for similar looking determinants, for example the one having $\gcd(i,j)$ at place $(i,j)$.
Solution. The idea is utilization of Lower-upper triangular decomposition. Using a software (like Mathematica) one observes that for small $n$ the matrices $L$ and $U$ coulde be intepreted as - $L=(l_{i,j})_{i,j=1}^{n}$, where $$l_{i,j}=\begin{cases} 1, & \text{j divides i}\\
0, & \text{otherwise} \end{cases}$$ and $U=(u_{i,j})_{i,j=1}^{n}$ where $$u_{i,j}=\begin{cases} i, & \text{i divides j}\\
0, & \text{otherwise} \end{cases}$$
It is directly verified that this holds in general (all $n$).
Obviously $\det L=1$, while $\det U=n!$ (the diagonal elements are $1,2,\ldots,n$). Thus $\det M=n!$.
The same idea could be employed for similar looking determinants, for example the one having $\gcd(i,j)$ at place $(i,j)$.
Prime divides element with index that prime
Let $s$ be a positive integer. Let $\{a_n\}_{n=1}^{\infty}$ be a
sequence given by $$a_1=0, \ a_2=2s, \ a_3=3, \ a_{n+3}=s a_{n+1}+a_n \ \
\ \text{for} \ n\ge 1.$$
Prove that for any prime number $p$, the number $a_p$ is divisible by $p$.
Solution. Let the roots of the equation $x^3-sx-1=0$ be $x_1, x_2$ and $x_3=-x_1-x_2$ (Vieta's formulas), they are algebraic integers (by definition). One directly observes (using the initial conditions) that $a_n=x_1^n+x_2^n+(-x_1-x_2)^n$. Assume $p>2$ (the other is obvious). We have
$$a_p=x_1^p+x_2^p+(-x_1-x_2)^p=-\sum_{k=1}^{p-1}{p\choose k}x_1^kx_2^{p-k}$$
${p\choose k}$ is divisible by $p$ for $1\le k \le p-1$, so we obtain that $a_p=p A$ where $A$ is an algebraic integer, since algebraic integers form a ring. However, from here we see that $A$ is also rational, hence $A$ is integer. Thus $p$ divides $a_p$.
I would like to thank Mr. Bozhilov for finding a mistake in the original proof, and his fruitful discussion, which led to a resolution.
The problem appeared at AKHIMO 2018.
Prove that for any prime number $p$, the number $a_p$ is divisible by $p$.
Solution. Let the roots of the equation $x^3-sx-1=0$ be $x_1, x_2$ and $x_3=-x_1-x_2$ (Vieta's formulas), they are algebraic integers (by definition). One directly observes (using the initial conditions) that $a_n=x_1^n+x_2^n+(-x_1-x_2)^n$. Assume $p>2$ (the other is obvious). We have
$$a_p=x_1^p+x_2^p+(-x_1-x_2)^p=-\sum_{k=1}^{p-1}{p\choose k}x_1^kx_2^{p-k}$$
${p\choose k}$ is divisible by $p$ for $1\le k \le p-1$, so we obtain that $a_p=p A$ where $A$ is an algebraic integer, since algebraic integers form a ring. However, from here we see that $A$ is also rational, hence $A$ is integer. Thus $p$ divides $a_p$.
I would like to thank Mr. Bozhilov for finding a mistake in the original proof, and his fruitful discussion, which led to a resolution.
The problem appeared at AKHIMO 2018.
Simple one (Lucas theorem)
Consider the integers $${n \choose k}$$
for $k=0,1,\ldots,n$. It turns out that the number of those which are odd is always a power of $2$.
Proof. Direct application of Lucas theorem. $ \displaystyle {n \choose k}$ is odd exactly when the $1's$ in the binary represenation of $k$ correspond only to $1's$ in the binary representation of $n$. If $n$ has exactly $d$ $1's$ then the number of such $k$ is $2^d$.
for $k=0,1,\ldots,n$. It turns out that the number of those which are odd is always a power of $2$.
Proof. Direct application of Lucas theorem. $ \displaystyle {n \choose k}$ is odd exactly when the $1's$ in the binary represenation of $k$ correspond only to $1's$ in the binary representation of $n$. If $n$ has exactly $d$ $1's$ then the number of such $k$ is $2^d$.
Subscribe to:
Comments (Atom)