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$.
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$.
Yet another solution of an old problem
Consider a problem we already solved (in a weaker setting) in a previous post.
Let $x_1,\ldots, x_n$ be complex numbers, such that $$x_1^k+\cdots +x_n^k=0$$ for all $k\in\{1,\ldots,n\}$. Prove that all of the numbers are zeros.
Here we would investigate another approach. The idea is simple. First we construct a matrix $A$ whose characteristic polynomial has as roots $x_1,\ldots, x_n$. Then we use the fact that $\text{Tr}(A^k)=x_1^k+\cdots+x_n^k$ to successively eliminate all the coefficients, hence showing that $x_1,\ldots,x_n$ are roots of $x^n=0$.
Assume $x^n-a_1 x^{n-1}-\cdots-a_{n-1}x-a_n$ is a polynomial whose roots are precisely $x_1,\ldots,x_n$. Then the matrix
$$ A= \begin{pmatrix}
a_1 & a_2 & a_3 & \dots & a_{n-1} & a_n \\
1 & 0 & 0 & \dots &0 & 0 \\
0 & 1 & 0 & \dots &0 & 0 \\
\vdots &\vdots & \vdots &\vdots &\ddots &\vdots\\
0 & 0 & 0 & \dots &1 & 0
\end{pmatrix}
$$ has this polynomial as characteristic.
Since $\text{Tr}(A)=0$ we have $a_1=0$. Now assume we have deduced that $a_1=\cdots=a_k=0$ for some $k\le n-1$. It is easy to see by induction that $$A^{k+1}=\begin{pmatrix}
a_{k+1} & a_{k+2} & a_{k+3} & \dots & \dots & a_{n} & 0 & \dots & 0\\
0 & a_{k+1} & a_{k+2} & \dots & \dots & a_{n-1} & a_n &\dots & 0\\
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots\\
0 & 0 & 0 & \dots &a_{k+1} & \dots & \dots & \dots & a_n \\
1 & 0 & 0 & \dots &\dots &\dots &\dots &\dots &0 \\
0 & 1 & 0 & \dots &\dots &\dots &\dots &\dots &0\\
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots&\vdots&\vdots\\
0 & 0 & \dots & 1 & 0 & \dots & \dots &\dots & 0
\end{pmatrix}$$
(the matrix may not be perfectly written, but you got the feeling)
From here is evident that $\text {Tr}(A^{k+1})=(k+1) a_{k+1}$. Hence $(k+1)a_{k+1}=0$ thus $a_{k+1}$ is zero. Thus we obtain that all the coefficients are zero. Hence the roots.
Comment. Does this solution generalizes the problem into a more abstract setting?
Let $x_1,\ldots, x_n$ be complex numbers, such that $$x_1^k+\cdots +x_n^k=0$$ for all $k\in\{1,\ldots,n\}$. Prove that all of the numbers are zeros.
Here we would investigate another approach. The idea is simple. First we construct a matrix $A$ whose characteristic polynomial has as roots $x_1,\ldots, x_n$. Then we use the fact that $\text{Tr}(A^k)=x_1^k+\cdots+x_n^k$ to successively eliminate all the coefficients, hence showing that $x_1,\ldots,x_n$ are roots of $x^n=0$.
Assume $x^n-a_1 x^{n-1}-\cdots-a_{n-1}x-a_n$ is a polynomial whose roots are precisely $x_1,\ldots,x_n$. Then the matrix
$$ A= \begin{pmatrix}
a_1 & a_2 & a_3 & \dots & a_{n-1} & a_n \\
1 & 0 & 0 & \dots &0 & 0 \\
0 & 1 & 0 & \dots &0 & 0 \\
\vdots &\vdots & \vdots &\vdots &\ddots &\vdots\\
0 & 0 & 0 & \dots &1 & 0
\end{pmatrix}
$$ has this polynomial as characteristic.
Since $\text{Tr}(A)=0$ we have $a_1=0$. Now assume we have deduced that $a_1=\cdots=a_k=0$ for some $k\le n-1$. It is easy to see by induction that $$A^{k+1}=\begin{pmatrix}
a_{k+1} & a_{k+2} & a_{k+3} & \dots & \dots & a_{n} & 0 & \dots & 0\\
0 & a_{k+1} & a_{k+2} & \dots & \dots & a_{n-1} & a_n &\dots & 0\\
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots\\
0 & 0 & 0 & \dots &a_{k+1} & \dots & \dots & \dots & a_n \\
1 & 0 & 0 & \dots &\dots &\dots &\dots &\dots &0 \\
0 & 1 & 0 & \dots &\dots &\dots &\dots &\dots &0\\
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots&\vdots&\vdots\\
0 & 0 & \dots & 1 & 0 & \dots & \dots &\dots & 0
\end{pmatrix}$$
(the matrix may not be perfectly written, but you got the feeling)
From here is evident that $\text {Tr}(A^{k+1})=(k+1) a_{k+1}$. Hence $(k+1)a_{k+1}=0$ thus $a_{k+1}$ is zero. Thus we obtain that all the coefficients are zero. Hence the roots.
Comment. Does this solution generalizes the problem into a more abstract setting?
Subscribe to:
Posts (Atom)