问:
Why is "for all $x\in\varnothing$, $P(x)$" true, but "there exists $x\in\varnothing$ such that $P(x)$" false?
There exists an $X\in A$ such that $P(X)$. When $A$ is the empty set then this statement is false because there is nothing in $A$ that when plugged in for $X$, makes $P(X)$ come out True.

However, when the quantifier is the universal one, meaning "For all $X\in A$" (which is the empty set), then the statement is true !!

How is that ? .. Because by the reasoning in the first statement, there are not any values of $X$ that makes $P(X)$ come out True.

I'm missing something !!

(I'm studying Electrical Engineering and self studying velleman's how to prove it and the quantifiers are already kicking my butt so simplify the answers for me if possible :))

答:
You are not alone who is puzzled with that. Lewis Carroll (who was a logician by trade) also objected to "vacuous truth". The choice that the modern logic makes is due more to the convenience of drawing implications without worrying if some sets are empty or not at each step, than to the intuition. You want to be able to combine the sentences "Everybody who is not too short can pick an apple on this tree" and "Everybody who is not too tall will be able to enter the vault" into "Everybody who is neither too short, nor too tall will be able to pick the apple and go to the vault with it" without heavy thinking of how the threshold heights in those cases are related to each other. This forces you to assign the "true" value to the last statement even if you need to be at least 6 feet tall to reach the apple and no more than 5 feet tall to enter the vault.

In general, such vacuous usage of "for every" is not uncommon in the real life. When the sheriff in a small town proclaims publicly that "Every criminal will be caught and punished!", the streets are patrolled day and night, and there are no crimes in the town, you don't call him a liar and the police department a worthless waste of taxpayer money, quite the opposite: you suspect that he is so right that even the to-be-criminals believe this statement of his and abstain from misdeeds.


问:
Total variation distance of two random vectors whose components are independent
Let $X^n=\left(X_1,\ldots,X_n \right)$ and $Y^n=\left(Y_1,\ldots,Y_n \right)$ be such that all $X_i$'s are independent and all $Y_i$'s are independent. I am trying to prove the following:
$$
d_{TV} \left(\mathbb{P}_{X^n},\mathbb{P}_{Y^n} \right) \leq \sum_{i=1}^n d_{TV} \left( \mathbb{P}_{X_i},\mathbb{P}_{Y_i} \right).
$$

Can anyone help me how to start ? Or provide a useful hint to proceed in the right direction ?

答:
For each $i\in\{1,\dots,n\}$ we consider the maximal coupling of the random variables $X_i$ and $Y_i$ (for the reference see Section 2.5 in Frank den Hollander, "Probability Theory: The Coupling Method", be advised that the total variation distance in this reference has additional factor $2$); in this way we have random variables $X_i'$ and $Y_i'$ which are defined on the same probability space $\Omega_i$, such that $X_i \overset{d}{=} X_i'$, and $Y_i \overset{d}{=} Y_i'$, and $d_{TV}(X_i,Y_i)= \mathbb{P}( X_i' \neq Y_i' )$.

The random variables $X_1',\dots,X_n',Y_1',\dots,Y_n'$ can be considered now as random variables on the product probability space $\Omega_1\times \cdots \times \Omega_n$. In this way $X_1',\dots,X_n'$ are independent and thus the random vector
$X'=(X_1',\dots,X_n')$ filfills $X \overset{d}{=} X'$; analogously $Y\overset{d}{=} Y'$. To summarize: $X'$ and $Y'$ is a coupling of the random vectors $X$ and $Y$.

The coupling inequality implies that
$$ d_{TV}(X,Y) \leq \mathbb{P}(X' \neq Y').$$
The probability on the right-hand side can be treated in two ways.

The first approach is to use the union bound; it follows that
\begin{align*} d_{TV}(X,Y) &\leq  \mathbb{P}(X' \neq Y') \\ & = \mathbb{P}( X_1' \neq Y_1' \text{ or } \dots \text{ or } X_n'\neq Y_n') \\ & \leq  \sum_i \mathbb{P}(X_i'\neq Y_i') \\ & = \sum_i d_{TV}(X_i,Y_i)
\end{align*}
which answers the original question.

The second approach is to calculate this probability exactly; we use the independence of the coordinates and get a better estimate
\begin{align*} d_{TV}(X,Y) & \leq 1- \mathbb{P}(X'=Y') \\ & = 1- \prod_i \mathbb{P}(X'_i=Y'_i) \\   & =  1  -  \prod_i [1-\mathbb{P}(X'_i \neq Y'_i)] \\ & =
1  -  \prod_i \left[1-  d_{TV}(X_i,Y_i) \right]
.
\end{align*}

ContentLicense: CC BY-SA 3.0

ContentLicense: CC BY-SA 4.0


问:
Proof that $\sum_{k=1}^n \frac{k}{2^k} < 2 $ for all $n \geq 1$
I recently completed a variation of a problem I found from a mathematical olympiad which is as follows:

Prove that, for all $n \in \mathbb{Z}^+$, $n \geq 1$, $$\sum_{k=1}^n \frac{k}{2^k} < 2 $$

I would like to hear comments on my method of proving the inequality above as well as ways of improving it or making it more rigorous. Thank you!

Proof: We begin by noticing that the series above is a Riemann sum (or approximation by areas of rectangles) for the integral $$ \int_1^n \frac{x}{2^x} dx$$ where the right endpoints are taken, hence $$\sum_{k=1}^n \frac{k}{2^k} < \int_1^n \frac{x}{2^x} dx$$ for all $n$.

By evaluating the original integral, it can be shown that $$ \int_1^n \frac{x}{2^x} dx = \frac{n \ln 2 + 1}{2^n (\ln 2)^2} + \frac{\ln 2 + 1}{2 (\ln 2)^2}$$

As $n$ approaches infinity, the integral approaches the value $\frac{\ln 2 + 1}{2 (\ln 2)^2}$, which is less than $2$. Hence, it can be deduced that $$ \int_1^n \frac{x}{2^x} dx < 2$$ for a large enough $n$.

By inspection and calculation, it is obvious that $$ \int_1^n \frac{x}{2^x} dx < 2$$ when $n > 5, n \in \mathbb{Z}^+$. Hence, when $1 \leq n \leq 5$, the integral has a value that is greater than $2$.

However, it can be verified by calculation that for $1 \leq n \leq 5$, $$\sum_{k=1}^n \frac{k}{2^k} < 2 $$ Since the statement holds true for $1 \leq n \leq 5$ as well as for $n > 5$, where $n \in Z^+$, the statement must be true for all $n \geq 1$. Hence, the proof is complete.

Hope to hear your thoughts on this!

答:
As commented by Albus, the values can be found.

In fact, let $p \in (0,1)$, then

$$\sum_{k=1}^{n}kp^k\le \sum_{k=1}^{\infty}kp^k=p\sum_{k=1}^{\infty}kp^{k-1}=p\frac{d}{dp}\left(\sum_{k=1}^{\infty}p^k\right)=p\frac{d}{dp}\frac{p}{1-p}=\frac{p}{(1-p)^2}.$$

Therefore, when $p=1/2$, the R.H.S. of the above is $2$, which proves your inequality.

In general, you can use integration to estimate the partial sum, as you did in your post.


答:
There are some major issues.  First, when $n = 1$, the integral is trivially $0$, so you cannot make the claim that $$S(n) = \sum_{k=1}^n \frac{k}{2^k} < \int_{x=1}^n \frac{x}{2^x} \, dx$$ for all $n$.  In fact, this inequality is never true.  I suspect you intended
$$S(n) < \int_{x=0}^n \frac{x}{2^x} \, dx = I(n)$$ but once again this is not true unless $n \ge 5$, and more worrisome is that as $n \to \infty$, $I(\infty) > 2$, so the bound is simply too loose to show that $S(n) < 2$, even if you attempt to patch the reasoning for small cases of $n$.

When we use an integral to bound a sum, the behavior of the summand that is converted to an integrand must be monotone, otherwise you cannot make the argument.  If you study the graph of $y = 2^{-x} x$ on $[0, \infty)$, we see that it is increasing from $x = 0$ to $x = (\log 2)^{-1}$, then decreasing afterward.  This makes your approach fundamentally problematic.

Instead, what I would recommend is either the direct evaluation of $S$, for which there are numerous methods.  This can be accomplished by differentiation of geometric series, e.g. consider $$f(z) = \sum_{k=0}^\infty z^k = \frac{1}{1-z}, \quad |z| < 1,$$ hence $$z f'(z) = \sum_{k=1}^\infty kz^k = \frac{z}{(1-z)^2}.$$  Then $$S(n) < S(\infty) = \left[z f'(z) \right]_{z=1/2} = \frac{1/2}{(1-1/2)^2} = 2$$ with the first inequality a direct consequence of the fact that all terms in $S$ are positive.

Title: Proof that $\sum_{k=1}^n \frac{k}{2^k} < 2 $ for all $n \geq 1$

Body:
I recently completed a variation of a problem I found from a mathematical olympiad which is as follows:

Prove that, for all $n \in \mathbb{Z}^+$, $n \geq 1$, $$\sum_{k=1}^n \frac{k}{2^k} < 2 $$

I would like to hear comments on my method of proving the inequality above as well as ways of improving it or making it more rigorous. Thank you!

Proof: We begin by noticing that the series above is a Riemann sum (or approximation by areas of rectangles) for the integral $$ \int_1^n \frac{x}{2^x} dx$$ where the right endpoints are taken, hence $$\sum_{k=1}^n \frac{k}{2^k} < \int_1^n \frac{x}{2^x} dx$$ for all $n$.

By evaluating the original integral, it can be shown that $$ \int_1^n \frac{x}{2^x} dx = \frac{n \ln 2 + 1}{2^n (\ln 2)^2} + \frac{\ln 2 + 1}{2 (\ln 2)^2}$$

As $n$ approaches infinity, the integral approaches the value $\frac{\ln 2 + 1}{2 (\ln 2)^2}$, which is less than $2$. Hence, it can be deduced that $$ \int_1^n \frac{x}{2^x} dx < 2$$ for a large enough $n$.

By inspection and calculation, it is obvious that $$ \int_1^n \frac{x}{2^x} dx < 2$$ when $n > 5, n \in \mathbb{Z}^+$. Hence, when $1 \leq n \leq 5$, the integral has a value that is greater than $2$.

However, it can be verified by calculation that for $1 \leq n \leq 5$, $$\sum_{k=1}^n \frac{k}{2^k} < 2 $$ Since the statement holds true for $1 \leq n \leq 5$ as well as for $n > 5$, where $n \in Z^+$, the statement must be true for all $n \geq 1$. Hence, the proof is complete.

Hope to hear your thoughts on this!


问:
Does the following necessarily converge to a normal random variable in distribution?
Suppose $X_1, \dots, X_n$ are i.i.d. random variables with $E(X_1) = 0$ and $\operatorname{Var}(X_1) = 1$. Let
$$
S_n = \frac{1}{n}\sum_{i=1}^n\sqrt{i}X_i.
$$
Does $S_n$ converge to a normal random variable?

Originally, I attempted to use Lindeberg CLT to prove this. However, I ran into a wall because I can't figure out a way to check the Lindeberg condition that for $\forall \varepsilon > 0$
$$
\sum_{i=1}^nE(|Y_i|^2\mathbf{1}(|Y_i| > \varepsilon)) \to 0
$$
where $Y_i = \sqrt{i}X_i/s_n$ and $s_n^2 = \sum_{i=1}^ni\operatorname{Var}(X_i) = \frac{n(n+1)}{2}$. If I can prove this, then I can use Slutsky, then we are done. But I have no idea what $X_i$ actually is so I don't know how to verify the condition.

Then I tried using characteristic functions and try to do expansion and approximation. However, I also hit a wall due to the changing index of $i$.

I also tried finding counterexample, but nothing came up.

Can anyone provide some hint? Thank you!

答:
As per answer by @StubbornAtom, I found the original proof of the Hajek-Sidak's CLT which is by deducing the Lindeberg condition. It turns out one can also use characteristic function to prove the claim which is almost in the same spirit as proving the Lindeberg CLT. I will provide the proof for both approaches below:

Proof using Lindeberg CLT:

Let $s_n^2 = \sum_{i=1}^niVar(X_i) = n(n+1)/2$, we will prove this by deducing the Lindeberg condtion. Let $\epsilon > 0$, we want to show that
$$
\frac{1}{s_n^2}\sum_{i=1}^n\int_{|x| > \epsilon s_n}x^2dP(\sqrt{i}X_i \leq x) \to 0.
$$
Now for each $i$,
$$
\int_{|x| > \epsilon s_n}x^2dP(\sqrt{i}X_i \leq x) = i\int_{|\sqrt{i}y|>\epsilon s_n}y^2dP(X_i \leq y) \leq i\int_{|y| > \epsilon v_n}y^2dP(X_i \leq y),
$$
where
$$
v_n^2 = \frac{n+1}{2}.
$$
Then
$$
\frac{1}{s_n^2}\sum_{i=1}^n\int_{|x| > \epsilon s_n}x^2dP(\sqrt{i}X_i \leq x) \leq \int_{|y| > \epsilon v_n}y^2dP(X_i \leq y).
$$
Since $E(X_i^2) < \infty$, we have that the RHS of above goes to zero as $n \to \infty$ by DCT. Therefore, the Lindeberg condition holds. Hence, after some simple calculation and application of Slutsky's theorem, we will have that
$$
S_n \to N(0, 1/2).
$$

Proof using characteristic functions:

Let $\phi(t)$ be the c.f. of $X_1$, and $z_{k,n}(t) = \phi(\frac{\sqrt{k}t}{n})$. Then the c.f. of $S_n$ is then
$$
\prod_{k=1}^nz_{k,n}(t).
$$
Moreover, let $w_{k,n}(t) = 1 - \frac{kt^2}{2n^2}$. Note that for any $t \in \mathbb{R}$,
$$
\sup_{k}|w_{k,n}(t)| \leq 1
$$
for sufficiently large $n$. Now since $E(X_1^2) = 1 < \infty$, we can consider the standard inequality regarding taylor expansion of complex exponential, and we have
$$
|z_{k,n}(t) - w_{k,n}(t)| \leq \frac{kt^2}{n^2}E\left[\min\left(\frac{\sqrt{k}|t|}{n}|X_1|^3, X_1^2\right)\right].
$$
Now since $|z_{k,n}(t)| \leq 1$ and $\sup_{k}|w_{k,n}(t)| \leq 1$, by a standard inequality of complex numbers, we have
\begin{align*}
\bigg|\prod_{k=1}^nz_{k,n}(t) - \prod_{k=1}^nw_{k,n}(t)\bigg| &\leq \sum_{k=1}^n|z_{k,n}(t) - w_{k,n}(t)| \\
&\leq \sum_{k=1}^n\frac{kt^2}{n^2}E\left[\min\left(\frac{\sqrt{k}|t|}{n}|X_1|^3, X_1^2\right)\right] \\
&\leq \frac{t^2(n+1)}{2n}E\left[\min\left(\frac{|t|}{\sqrt{n}}|X_1|^3, X_1^2\right)\right].
\end{align*}
Now the last term of the above converge to $0$ by DCT. Hence, we have that
$$
\lim_{n\to \infty}\prod_{k=1}^nz_{k,n}(t) = \lim_{n\to \infty}\prod_{k=1}^nw_{k,n}(t).
$$
Now
\begin{align*}
\lim_{n\to \infty}\prod_{k=1}^nw_{k,n}(t) &= \lim_{n\to \infty}\prod_{k=1}^n\left(1 - \frac{kt^2}{2n^2}\right)\\
 &= \lim_{n\to \infty}\exp\left(\sum_{k=1}^n\log\left(1 - \frac{kt^2}{2n^2}\right)\right) \\
&= \exp\left(\lim_{n\to \infty}\sum_{k=1}^n\log\left(1 - \frac{kt^2}{2n^2}\right)\right)\\
&= \exp\left(\lim_{n\to\infty}\sum_{k=1}^n- \frac{kt^2}{2n^2} + o\left(\frac{kt^2}{2n^2}\right)\right) \\
&= \exp\left(-\frac{t^2}{4}\right).
\end{align*}
The above is the c.f. of $N(0,1/2)$. Therefore,
$$
S_n \to N(0,1/2).
$$


答:
Note that no calculus is needed:

$$\begin{align*}
\sum_{k=1}^n\frac{k}{2^k}&=\sum_{k=1}^n\sum_{\ell=1}^k\frac1{2^k}\\
&=\sum_{\ell=1}^n\sum_{k=\ell}^n\frac1{2^k}\\
&=\sum_{\ell=1}^n\frac{\frac1{2^{\ell}}-\frac1{2^{n+1}}}{1-\frac12}\\
&=\sum_{\ell=1}^n\left(\frac1{2^{\ell-1}}-\frac1{2^n}\right)\\
&=\sum_{\ell=0}^{n-1}\frac1{2^\ell}-\frac{n}{2^n}\\
&=\frac{1-\frac1{2^n}}{1-\frac12}-\frac{n}{2^n}\\
&=2\left(1-\frac1{2^n}\right)-\frac{n}{2^n}\\
&=2-\frac{n+2}{2^n}\\
&<2\,.
\end{align*}$$

For the visually oriented this has a nice schematic representation:

$$\begin{array}{cccccc|c}
\frac12&\frac14&\frac18&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac12-\frac1{2^{n+1}}\right)=1-\frac1{2^n}\\
&\frac14&\frac18&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac14-\frac1{2^{n+1}}\right)=\frac12-\frac1{2^n}\\
&&\frac18&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac18-\frac1{2^{n+1}}\right)=\frac14-\frac1{2^n}\\
&&&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac1{16}-\frac1{2^{n+1}}\right)=\frac18-\frac1{2^n}\\
&&&&\ddots&\vdots&\vdots\\
&&&&&\frac1{2^n}&2\left(\frac1{2^n}-\frac1{2^{n+1}}\right)=\frac1{2^{n-1}}-\frac1{2^n}\\\hline
\frac12&\frac2{2^2}&\frac3{2^3}&\frac4{2^4}&\cdots&\frac{n}{2^n}&2\left(1-\frac1{2^n}\right)-\frac{n}{2^n}=2-\frac{n+2}{2^n}
\end{array}$$

Instead of summing the columns to the left of the vertical line to get the terms of the summation and then adding, I’ve summed the rows of the triangular matrix, each of which is a geometric progression, to get the totals in the righthand column above the horizontal line, and then summed those row sums to get the desired total.


问:
Definition of a primitive polynomial
I understand there are already some questions (A, B) on primitive polynomials.  But none of these clears my confusion.

In page 84 of Handbook of Applied Cryptography, primitive polynomial has been defined as,

Now, if I try to understand the definition by dissecting the parts,

This is an irreducible polynomial, that means, it cannot be factored into the product of two or more non-trivial polynomials.

The polynomial $f(x) \in \mathbb{Z}_p[x]$. So, the polynomial belongs to the  polynomial ring $\mathbb{Z}_p [x]$, where, $\mathbb{Z}_p [x]$  is the ring formed by the set of all polynomials in the indeterminate $x$ having coefficients from $\mathbb{Z}_p$. Here $\mathbb{Z}_p$, will be the integers modulo $p$,  set of (equivalence classes of) integers
$\{0, 1, 2, . . . , p − 1\}$.

$x$ is a generator of $\mathbb{F}^*_{p^m}$: I am coming to this part regarding $x$ later on. $\mathbb{F}^*_{p^m}$,  is the multiplicative group of $\mathbb{F}_{p^m}$ such that $ \{a \in \mathbb{F}_{p^m} | \gcd(a, p) = 1\}$.

$\mathbb{F}_{p^m} = \mathbb{Z}_p[x]/(f(x))$, denotes the set of (equivalence classes of) polynomials in $\mathbb{Z}_p[x]$
of degree less than $n = \deg f (x)$. Addition and multiplication are performed modulo $f (x)$.

Now, coming back to the point of $x$, I began to realize that I must have some
serious flaw in my understanding above. So far, I have seen that generators have always been numbers.
Here the generator is $x$, which is an indeterminate.

Could you please point out the where I have gone off the track?

Perhaps the best way to salvage me will be to simply rewrite my points 1-4. Adding an example will make things perfect.

答:
The notation in the book is not one I would have chosen. All the $m$ roots of the irreducible polynomial $f(x) \in \mathbb F[x]$ are generators of the multiplicative group of $\mathbb F_{p^m}$; this group is a cyclic group. In particular, if $\alpha$ is a root of $f(x)$, then $$\mathbb F_{p^m}^{\star} = \{1, \alpha, \alpha^2, \ldots, \alpha^{p^m-2}; \times\,\}.$$ The other roots of $f(x)$ are $\alpha^p, \alpha^{p^2},\cdots,\alpha^{p^{m-1}}$ which are also called conjugates of $\alpha$.  An alternative representation of $\mathbb F_{p^m}$ is
the collection of polynomials of degree less than $m$ in $\mathbb F_p[x]$. The two representations are connected via the following table:
$$\begin{matrix}1&=&1\\
\alpha&=& & \alpha\\
\alpha^2&= &&&\alpha^2\\
\vdots& \vdots&\ddots\\
\alpha^{m-1}&= &&&&&\alpha^{m-1}\\
\alpha^{m}&= &-f_0&-f_1\alpha&-f_2\alpha^2&\cdots&-f_{m-1}\alpha^{m-1}\\
\vdots&\vdots&\ddots
\end{matrix}$$
where we assume that $f(x)$ is monic, and use the fact that
$$f(\alpha) = 0 =
f_0 + f_1\alpha + f_2\alpha^2 + \cdots + f_{m-1}\alpha^{m-1} + \alpha^m \tag{1}$$
in writing $\alpha^m$ as a polynomial in $\alpha$ of degree smaller than $m$. To find
the next line in the above table, we use
$$\begin{align}
\alpha^{m+1} &= \alpha^m\cdot\alpha\\
&= (-f_0-f_1\alpha-f_2\alpha^2\cdots -f_{m-1}\alpha^{m-1})\alpha\\
&= 0-f_0\alpha -f_1\alpha^2-f_2\alpha^3\cdots - f_{m-2}\alpha^{m-1}-f_{m-1}\alpha^{m}
\end{align}$$
and replace $f_{m-1}\alpha^m$ by $f_{m-1}(-f_0-f_1\alpha-f_2\alpha^2\cdots -f_{m-1}\alpha^{m-1})$ to once again get a polynomial of degree less than $m$ in $\alpha$.
Repeating this process creates the entire table which is often referred to as
a logarithm table but in fact is an antilogarithm table.  For each $i$, the
table gives the
representation of $\alpha^i$ as a polynomial in $\alpha$ -- very convenient for
addition -- while multiplication of two polynomials in $\alpha$ and subsequent
reduction using $(1)$ repeatedly is harder than computing
$\alpha^i\times\alpha^j = \alpha^{i+j \bmod p^m-1}$, that is, by adding
the logarithms.

Finally, all this works exactly the same way and gives the same results
 if we replace $\alpha$ by $x$
and say that $\mathbb F_{p^m} = \mathbb F_p[x]/f(x)$ etc., but this always
creates confusion amongst beginners.

Title: Definition of a primitive polynomial


问:
How do you prove for all $k$ in the integers, $2-5k$ can never be a perfect square?
Proving this for $k > 0$ is easy and intuitive, but I'm unsure how to proceed with the negative values for $k$. Should I use modular congruence somehow? Or can I prove this more simply? My gut said since it is for all integers, I should try proof by induction, but I have no idea where to go with that.

答: Note than any number $n$ ends with the ones digits $0,1,2,3,4,5,6,7,8,9$. If we square $n$, we multiply the one digits, and do some carrying to get $0,1,4,5,6,9$ as the one digits of $n^2$. Now let's examine the ones digits of $2-5k$ for various values of $k$. For $k=0$, ones digit is $2$, however a square doesn't end in $2$ as we have shown before. For $k=-1$ we have $2+5 =7$, but a square can't end in $7$. For $k=-2$ we have $2+10 = 12$, which ends in $2$, but we can't have it end in $2$. Notice that every time we increase $k$ by $1$, the ones digit switches from $2$ to $7$ or $7$ to $2$. This is because you are only adding $5$ each time, thus if you add it to $2$ it becomes $7$, and if you add it to $7$ you get $12$ which has units digit $2$. Since we have shown that a series will switch between $2,7$ as the ones digits if it adds $5$ each time and we have shown that the base cases have $2,7$ as units digits, we have proven that $2-5k$ will always end in $2,7$ (assuming it is positive). However, a square cannot end in $2,7$, thus $2-5k$ can never be a square.


答: For every integer $x$ we have $x\equiv 0,\pm1, \pm2 \pmod 5$ but then we have $x^2\equiv 0,1,-1\pmod 5$. So if $2-5k = x^2$ for some integers $x$ and $k$, we would have $$x^2 \equiv 2\pmod 5$$ A contradiction.

Title: How do you prove for all $k$ in the integers, $2-5k$ can never be a perfect square?

Body: Proving this for $k > 0$ is easy and intuitive, but I'm unsure how to proceed with the negative values for $k$. Should I use modular congruence somehow? Or can I prove this more simply? My gut said since it is for all integers, I should try proof by induction, but I have no idea where to go with that.


问:
Modular Arithmetic Inverse Proof
Let $m, x$ be positive integers such that $\gcd(m, x) = 1$. Then $x$ has a multiplicative inverse modulo $m$, and it is unique (modulo $m$).

Proof: Consider the sequence of $m$ numbers $0, x, 2x, \dots, (m−1)x$. We claim that these are all distinct modulo $m$. Since there are only $m$ distinct values modulo $m$, it must then be the case that $ax \equiv 1 \pmod m$ for exactly one $a$ (modulo $m$). This $a$ is the unique multiplicative inverse of $x$.

To verify the above claim, suppose for contradiction that $ax \equiv bx \pmod m$ for two distinct values $a,b$ in the range $0 \leq b \leq a \leq m−1$. Then we would have $(a−b)x \equiv 0 \pmod m$, or equivalently, $(a−b)x = km$ for some integer $k$ (possibly zero or negative).
However, $x$ and $m$ are relatively prime, so $x$ cannot share any factors with $m$. This implies that $a−b$ must be an integer multiple of $m$. This is not possible, since $a−b$ ranges between $1$ and $m−1$.

I understand the contradiction and how this proves that the sequence of $m$ numbers are all unique mod $m$; however, I am unsure how if this is the case, then it implies that $ax \equiv 1 \pmod m$ for exactly one $a \pmod m$.

答:
If we let $S$ denote the set of residue classes modulo $m$, then the map $a\mapsto ax\pmod m$ is a function from $S$ to itself. The claim shows that this function is injective. This injectivity already shows that $ax\equiv1\pmod m$ for at most one residue class $a\pmod m$.

But since $S$ is finite, any injective function from $S$ to itself is automatically surjective (this is basically the pigeonhole principle). And surjectivity implies that $ax\equiv1\pmod m$ for at least one residue class $a\pmod m$.

Title: Modular Arithmetic Inverse Proof


答: Simply check that, mod $5$, $0^2, 1^2, 2^2, 3^2$, and $4^2$ are respectively $0,1,4,4$, and $1$. Meanwhile $2-5k\equiv 2$.


答:
''however, I am unsure how if this is the case, then it implies that ax≡1 (mod m) for exactly one a (mod m)''

Its in the proof. It shows that there exists an $a$ with $ax\equiv 1\mod m$ and since the values $0,x,2x,\ldots,(m-1)x$ are all distinct, there is exactly one $a$.

Title: Modular Arithmetic Inverse Proof

Body:
Let $m, x$ be positive integers such that $\gcd(m, x) = 1$. Then $x$ has a multiplicative inverse modulo $m$, and it is unique (modulo $m$).

Proof: Consider the sequence of $m$ numbers $0, x, 2x, \dots, (m−1)x$. We claim that these are all distinct modulo $m$. Since there are only $m$ distinct values modulo $m$, it must then be the case that $ax \equiv 1 \pmod m$ for exactly one $a$ (modulo $m$). This $a$ is the unique multiplicative inverse of $x$.

To verify the above claim, suppose for contradiction that $ax \equiv bx \pmod m$ for two distinct values $a,b$ in the range $0 \leq b \leq a \leq m−1$. Then we would have $(a−b)x \equiv 0 \pmod m$, or equivalently, $(a−b)x = km$ for some integer $k$ (possibly zero or negative).
However, $x$ and $m$ are relatively prime, so $x$ cannot share any factors with $m$. This implies that $a−b$ must be an integer multiple of $m$. This is not possible, since $a−b$ ranges between $1$ and $m−1$.

I understand the contradiction and how this proves that the sequence of $m$ numbers are all unique mod $m$; however, I am unsure how if this is the case, then it implies that $ax \equiv 1 \pmod m$ for exactly one $a \pmod m$.


答: I think I'm getting it. How about the conditional form of this though. For all X(If x belongs to the empty set, then P(X)). This is only false when the hypothesis is True and the conclusion is False. But since the hypothesis is always False since there are not any members of the empty set, therefore the conditional is always True. Great . Now when we change the quantifier into the existential one. Why is it wrong ?! The hypothesis is still wrong because since there aren't any elements in the empty set, then there are not even some elements , Therefore shouldn't it be True as well</p>

Title: Why is "for all $x\in\varnothing$, $P(x)$" true, but "there exists $x\in\varnothing$ such that $P(x)$" false?

Body:
There exists an $X\in A$ such that $P(X)$. When $A$ is the empty set then this statement is false because there is nothing in $A$ that when plugged in for $X$, makes $P(X)$ come out True.

However, when the quantifier is the universal one, meaning "For all $X\in A$" (which is the empty set), then the statement is true !!

How is that ? .. Because by the reasoning in the first statement, there are not any values of $X$ that makes $P(X)$ come out True.

I'm missing something !!

(I'm studying Electrical Engineering and self studying velleman's how to prove it and the quantifiers are already kicking my butt so simplify the answers for me if possible :))


问:
Essential requirements for the definition of a function.
The book I'm working on states that a function f: A -> B is defined under the following conditions:

Every x element of A associated with some y in B, i.e., a function is defined only when the domain is entirely "used up". The set B may not be entirely "used up".

The function may associate more than one x to the same y.

No element A should have more than one image in B

Now, I have three question listed as follows:

What do they mean by a function being "defined"? Is there "undefined" functions?

Is there a reason why the set A has to be entirely "used up" and not B, or is it because that's how mathematicians define it?

If we have a function that relates two sets, for example A and B, the domain is A and the codomain B, but because the the set B may not be entirely "used up", then there will be a subset of the codomain, let's say, C that will represent the range of the function. Right? If so, does this mean that when we restrict a function codomain, the nonerestricted part of the codomaim will become the range?

答:
Q1: What do they mean by a function being defined? They just mean that is satisfies the definition of a function. i.e., Every element of the domain must be mapped somewhere, and no single element of the domain can be mapped to two different elements.

Let $A$ be the set $\{a,b\}$, and let $B$ be the set $\{1,2,3\}$. Consider the following
$$f:A→ B$$
which satisfies $f(a)=1, f(b)=2$. Every element of $A$ is "used up" (we told $f$ where to send $a$ and where to send $b$), and there is no single element of $A$ that is sent to two different places. So, $f$ is a function, i.e., it is defined. In order for something to be a function, it doesn't matter how many elements of $B$ are "hit" by elements of $A$ after applying the function. In this case, $3$ is not hit by any element of $A$ after applying the function, but that's okay, because every element of $A$ is mapped somewhere.

Now, with $A$ and $B$ the same as above, if we now consider
$$g:A→ B$$
given by $g(a)=1,g(a)=2,g(b)=3$, note that the element $a$ is mapped to two different elements of $B$; a is mapped to 1, and to 2. This is not a function, because one single element of $A$ is mapped to two different elements of the codomain. This doesn't mean it's not useful to consider maps such as this, but we just don't call them functions. So, this 'function' (not really a function) is not defined.

Q2: Is there a reason $A$ has to be entirely used up? I think the silly answer is, yes, that's just the way it's defined. If a function $f:A→ B$ only used up some subset $A'⊂ A$, then we can just toss out the extra elements of A that aren't used up, and consider the same function $f:A'→ B$.

Q3 Your statement is correct, that in general, since $B$ is not "used up" by the function, there is some subset of $B$ which will be the range of the function. When we "restrict" (when in reference to the codomain, we say 'constrict' or 'co-restrict') the codomain we are removing elements of the codomain that are not used up by the function. So, yes, the "unrestricted" part, aka the part that we didn't touch, will become the range only when we remove all elements that are not used up by the function. Usually we constrict a function fully, so that the new codomain is exactly the range.


问:
Is this answer to the proof equivalent to the one I wrote
I am doing a mathematical proof in which the answer from the solution is different from what I wrote. Is the one that I wrote also valid or is it wrong?

That was the answer from the solution. Now my answer:

$x^2+5x-1 = (2k)^2+5(2k)-1=4k^2+10k-1=2(2k^2+5k)-1 $

Thank you

答:
Yes, your solution is correct. If you wanted to make it a little bit cleaner, you could do something similar to the following:

Let $y = x^2+5x-1,x\in\mathbb{Z}$

$y$ is odd$\rightarrow y= $$ (2u+1) \lor (2u-1), u\in\mathbb{Z}$

$x$ is even $\rightarrow$ $x = 2k,\;k\in\mathbb{Z}$

$y=x^2+5x-1=(2k)^2+5(2k)-1=4k^2+10k-1=2(2k^2+5k)-1$

Let $u=2k^2+5k$

$k\in\mathbb{Z}$ so $u\in\mathbb{Z}$

$y=2u-1$

$\therefore y$ is odd


Body:
$$2S_n-S_n=\sum_{k=1}^nk2^{1-k}-\sum_{k=1}^nk2^{-k}=\sum_{k=0}^{n-1}(k+1)2^{-k}-\sum_{k=1}^nk2^{-k}
\\=1-n2^{-n}+\sum_{k=0}^{n-1}2^{-k}<1+1.$$


问:
Product of signs of two juxtaposition of two disjoint permutations
Edited: Suppose we are given two disjoint permutations $(a_1,\dots,a_m)$ and $(b_1,\dots,b_n)$. I want to prove that (if it is correct)

$$\text{sgn}(a_1,\dots,a_m, b_1,\dots,b_n)\times \text{sgn}(b_1,\dots,b_n, a_1,\dots,a_m)=(-1)^{\sum_{i=1}^m (a_i-1)+\sum_{i=1}^n (b_i-1)}.$$

Where $\text{sgn}$ denotes the sign of permutation which is $+1$ or $-1$ depending on whether the permutation is even or
odd.
<s> I know that parity of a $k$-cycle is $k-1$. I think $(a_1,\dots,a_m, b_1,\dots,b_n)$ is same as $(a_1,\dots,a_m)(b_1,\dots,b_n)$ because they are disjoint cycles, so $\text{sgn}(a_1,\dots,a_m, b_1,\dots,b_n)=\text{sgn}(a_1,\dots,a_m)\cdot\text{sgn}(b_1,\dots,b_n)$. Right? And $\text{sgn}(a_1,\dots,a_m)=(-1)^{m-1}$ and $\text{sgn}(b_1,\dots,b_n)=(-1)^{n-1}$ But these seems do not imply the above claim.</s>

Any suggestion?

答:
Firstly I think from looking
at the page of the book you reference
in a comment to the answer by Henno Brandsma (which answers the question you originally posed) that what is meant here by $\text{sgn}(c_1,c_2,\dots, c_N)$ is the sign of the permutation $i\mapsto c_i$.

What you are looking at is the case where $N=m+n$, and the first $m$ $c_i$ are  $c_i=a_i$ and the last $n$ $c_i$ are $c_{i-m}=b_i$.

When you look at
$$
\text{sgn}(a_1,\dots,a_m, b_1,\dots,b_n)\times \text{sgn}(b_1,\dots,b_n, a_1,\dots,a_m)
$$
you might as well ask for
$$
\text{sgn}(a_1,\dots,a_m, b_1,\dots,b_n)^{-1}\times \text{sgn}(b_1,\dots,b_n, a_1,\dots,a_m)
$$
since for every permutation $\pi$ we know that $\pi^1$ and $\pi$ have the same sign.

We also know that for any pair of permutations $\pi_1,\pi_2$ the sign of $\pi_1\pi_2$ is just the product of the signs of $\pi_1$ and $\pi_2$. So what you really want to calculate is
$$
\text{sgn}(a_1,\dots,a_m, b_1,\dots,b_n)^{-1}
(b_1,\dots,b_n, a_1,\dots,a_m).
$$

But what is this permutation? It is the permutation taking $a_1$ to $1$ to $b_1$, $a_2$ to $2$ to $b_2$, ..., $b_n$ to $n$ to $a_m$.  [To avoid confusion I read my permutations left to right.]

So how many swaps does it take to move the $a_i$ behind the $b_i$? Well each of the $m$ $a_i$ must slip past $n$ of the $b_j$, so that there are $mn$ swaps.

Hence the sign of the permutation is $(-1)^{mn}$ or if you prefer $(-1)^{m(N-m)}$; the latter is the form given in "Solution (2)" of your book.

Edit: Further question in the comments below.

You are asking (I think) where one of the intermediate formulas in Solution(2) of the book comes from. At this stage we are trying to compute the sign of the permutation $(a_1,a_2,\dots, a_m,b_1,\dots, b_n)$ where this notation still means the permutation taking $1\dots (m+n)$ to these values.

I believe that in the book we have this added information: $a_1<a_2<\dots<a_m$ and $b_1<b_2<\dots<b_n$. To calculate the sign of this permutation note that we have to first swap the first $(a_1-1)$ elements $b_j$ past the $m$ elements $a_i$. Next we have to swap the next $(a_2-a_1-1)$ elements $b_j$ past  $(m-1)$ elements $a_i$. Next we have to swap the next $(a_3-a_2-1)$ elements $b_j$ past  $(m-2)$ elements $a_i$. And so on. When I calculate this sum and simplify it I get -f I have made no mistake-  $\sum_{i=1}^{m} a_i - {m\choose 2}$ which is what is required in the book.


问:
Show that $V\otimes V\simeq L(V^*,V^*,\mathbb{R})$
I am trying to understand tensor products and I would like to show that $V\otimes V\simeq L(V^*,V^*,\mathbb{R})$. In Lee's book about smooth manifolds is the following proof for the case $V^*\otimes V^*\simeq L(V,V,\mathbb{R})$:

According to the book it follows directly from $V\simeq V^{**}$, since everything is assumed to have finite dimension. I am fine with that. Nevertheless  I was wondering if it couldn't be done as it is done in the above proof.

For $(v,w)\in V\times V$ and $\omega,\eta\in V^*$ I would define $\Phi :V\times V\to L(V^*,V^*,\mathbb{R}),\Phi(v,w)[\omega,\eta]:=\omega(v)\cdot\eta(w)$. I suppose it is a bilinear map. If it is, then it decents to a linear map

$\tilde{\Phi} :V\otimes V\to L(V^*,V^*,\mathbb{R}),  \tilde{\Phi}(v\otimes w)[\omega,\eta]:=\omega(v)\cdot\eta(w)$. Now I am stuck. I am not sure what the basis vectors for $L(V^*,V^*,\mathbb{R})$ are or how to show that it is a bijection. I am also not sure if the apprach is okay or complete nonsense.

Thank you very much in advance!

答:
Notation: In order to distinguish the abstract tensor product "$\otimes$" from the tensor product of covectors defined in example $12.2$, if $Z$ is a real vector space, and $f_1,f_2 \in Z^*$, let's denote by $f_1 \,\widetilde{\otimes}\, f_2$ to the bilinear map in $\mathrm L(Z,Z;\mathbb R)$ given by $(f_1 \,\widetilde{\otimes}\, f_2)(z_1,z_2) := f_1(z_1)f_2(z_2)$. Also, if $z \in Z$, let $\operatorname{ev}_z \in Z^{**}$ be "evaluation at $z$", that is, $\operatorname{ev}_z(f) = f(z)$ for every $f \in Z^*$.

Now, let $I := \{1,\dots,\dim V\}$, and suppose that $\{e_i : i \in I\}$ is a basis for $V$. Then proposition $12.8$ tells us that $\{e_\alpha \otimes e_\beta : (\alpha,\beta) \in I \times I\}$ is a basis for $V \otimes V$, and if $\{e^i : i \in I\}$ is the dual basis of $\{e_i : i \in I\}$, proposition $12.4$ tells us that $\{\operatorname{ev}_{e_\alpha} \!\widetilde{\otimes} \operatorname{ev}_{e_\beta}\! : (\alpha,\beta) \in I \times I\}$ is a basis for $\mathrm L(V^*,V^*;\mathbb R)$, simply because $\{\operatorname{ev}_{e_i}\! : i \in I\}$ is the dual basis of $\{e^i : i \in I\}$.

Finally, note that your map $\widetilde{\Phi} : V \otimes V \to \mathrm L(V^*,V^*;\mathbb R)$ sends $e_\alpha \otimes e_\beta \in V \otimes V$ to the bilinear map $\widetilde{\Phi}(e_\alpha \otimes e_\beta) \in \mathrm L(V^*,V^*;\mathbb R)$ such that $$\widetilde{\Phi}(e_\alpha \otimes e_\beta)(f_1,f_2) = f_1(e_\alpha)f_2(e_\beta) = \operatorname{ev}_{e_\alpha}(f_1) \operatorname{ev}_{e_\beta}(f_2)$$ for every $f_1$ and $f_2$ in $V^*$, in other words, $\widetilde{\Phi}(e_\alpha \otimes e_\beta) = \operatorname{ev}_{e_\alpha} \!\widetilde{\otimes} \operatorname{ev}_{e_\beta}\!$. Thus $\widetilde{\Phi}$ take basis elements in $V \otimes V$ to basis elements in $\mathrm L(V^*,V^*;\mathbb R)$, and this proves that $\widetilde{\Phi}$ is an isomorphism.


问:
Induction Argument to prove that the union of a finite number of finite sets is a finite set.
Give an induction argument to prove that the union of a finite number of finite sets is a finite set. Assume the base case is true as indicated in part(2) of Theorem 1.22

Theorem 1.22: The following results on finite and infinite set are valid.

A subset of a finite set is finite.

The union of two finite sets is a finite set.

A set that contains an infinite subset is infinite.

A set that contain an uncountable subset is uncountable.

I have seen some other proofs that solve this without using induction. However, I do not know how to go about proving this using induction.

For the proof am I supposed to let A_k be a finite number of finite sets?

答: After the base case, you would then assume that you have a collection of finite sets $A_1,A_2,\ldots,A_k$ such that $A_1\cup A_2\cup\cdots\cup A_k$ is finite. This is now your assumption and you get to use this as a fact. Then, the induction step would be to suppose that you have another finite set, $A_{k+1}$, and use the previous assumption to show that $A_1\cup\cdots\cup A_k\cup A_{k+1}$ is finite.


问:
Confusion on a proof from Terence Tao's Analysis 1
I recently started learning mathematical induction and I saw this question on here about the proof of backwards induction.

where $m{+\!+}$ is the successor function

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m{+\!+})$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m\leq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

I've seen quite a few answers on this yet its still confusing me mainly because I don't quite grasp the assumption about whenever $P(m{+\!+})$ is true, then $P(m)$ is true i know that for induction you must first prove the base case showing that from what you assume is true actually leads to a truth then you carry out the induction however assuming that that $\mathbb{N}=\{1,2,3,\dots\}$ for the base case $n=1$ how can I show that the assumption $P(m{+\!+})$ $\implies$ $P(m)$ is true as if what exactly is $P(m)$  I saw on other posts that we just say that only $1\leq 1$ and by assumption $P(1)$ was true but doing this we didn't show that $P(m{+\!+}) \implies P(m)$ is true. I'm not quite sure exactly how to deal with the base case here to show that all the assumptions are true this has confused the other users on s.e. too some help would be greatly appreciated.

Thanks in advance.

答:
The base case is straightforward (and it does not change if we "start from" $1$ instead of $0$. According to Tao, page 15, natural numbers start from $0$).

If $P(1)$ holds, then $P(k)$ holds for every $k \le 1$ (there is only $1$).

The fact $P(m++) \to P(m)$ is not used here; as you can see, it is not necessary. Also, $1$ (the "first" number) is not a successor of any number: thus, you cannot find an $m$ such that $1=m++$.

If instead we admit also $0$, from $P(1)$ and $P(m++) \to P(m)$, we have immediately that $P(0)$ also holds.

In both cases: $P(k)$ holds for every $k \le 1$.

Assume now the Induction Hypothesis, i.e. that:

if $P(n)$ holds, then $P(k)$ holds for every $k \le n$.

We want to prove the same for $n++$.

Assume that $P(n++)$ holds. Using the fact that $P(m++) \to P(m)$ holds, for every $m$, we have that (Modus Ponens) also $P(n)$ holds.

Thus, using IH, we have that $P(k)$ holds for every $k \le n$. But we have assumed that $P(n++)$ holds.

Thus: $P(k)$ holds for every $k \le n++$.


问:
Finding $A$, $B$, $C$ such that $(2x-A)(2x+4)-Bx+25=(x-C)^2-Cx^2$ for all $x$

Find $A$, $B$, $C$ such that
$$(2x-A)(2x+4)-Bx+25=(x-C)^2-Cx^2$$
for all $x$.

This is what I've got so far.

$$\begin{align}
\text{L.H.S.}
&= (2x-A)(2x+4)-Bx+25 \tag1\\
&= 4x^2-2Ax+8x-4A-Bx+25 \tag2\\
&= 4x^2-(2A+8)x-4A-Bx+25 \tag3 \\ \\
\text{R.H.S.}
&= (x-C)^2-Cx^2 \tag4\\
&= x^2-2Cx+C^2+Cx^2 \tag5
\end{align}$$

I have no idea how I should find the constants by calculation. Please help.

答:
Since it is true for all $x$, this is an identity and hence all you need to do is compare coefficients as mentioned in comments. So, we have $$\begin{aligned} 4 &=1-C \\ 2A+B-8&=2C \\ -4A+25&=C^2\end{aligned}$$

Which gives you $C=-3,A=4,B=-6$.

Note that you have done some mistakes in sign.


问:
How to prove that $n \equiv 1 \mod (m-1)$ implies $a^n \equiv a \mod m$ for all $n, m, a \in \mathbb{Z}$?
Consider $n=561 = 3\times 11 \times 17$. We note that
$$561 \equiv 1 \mod (3-1), (11-1), (17-1).$$ It's then said that this implies that $$
 a^{561} \equiv a \mod 3, 11, 17 \quad \text{for all}\;a
 $$

I wanted to know how to see that this is always true?

EDIT: Does the result only hold when $m$ is one of the prime factors of $n$?

答:
To elaborate on using FLT when $m$ is prime: if $(a,m)\neq1$ then $m|a$, so the result is trivially true.

Hence we may assume $(m,a)=1$. By FLT, $a^{m-1}\equiv1\pmod m$. Write $n=k(m-1)+1$, then $a^n=a(a^{m-1})^k\equiv a\cdot1^k=a\pmod m$.

More generally, as Stinking Bishop mentioned in the comments, the argument still works when $m$ is a Carmichael number.


答: We wish to prove by induction that $\varphi(n)$ for all $n\ge0$, where $\varphi(n)$ means$$P(n)\to\forall m\le n(P(m)),$$so $\varphi(0)$ is vacuously true. If $\varphi(k)$ then $P(k++)\to P(k)$ and $P(k)\to\forall m\le k(P(m))$, and so$$P(k+1)\to\forall m\le k++(P(m)),$$which is just $\varphi(k++)$.

Title: Confusion on a proof from Terence Tao's Analysis 1

Body:
I recently started learning mathematical induction and I saw this question on here about the proof of backwards induction.

where $m{+\!+}$ is the successor function

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m{+\!+})$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m\leq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

I've seen quite a few answers on this yet its still confusing me mainly because I don't quite grasp the assumption about whenever $P(m{+\!+})$ is true, then $P(m)$ is true i know that for induction you must first prove the base case showing that from what you assume is true actually leads to a truth then you carry out the induction however assuming that that $\mathbb{N}=\{1,2,3,\dots\}$ for the base case $n=1$ how can I show that the assumption $P(m{+\!+})$ $\implies$ $P(m)$ is true as if what exactly is $P(m)$  I saw on other posts that we just say that only $1\leq 1$ and by assumption $P(1)$ was true but doing this we didn't show that $P(m{+\!+}) \implies P(m)$ is true. I'm not quite sure exactly how to deal with the base case here to show that all the assumptions are true this has confused the other users on s.e. too some help would be greatly appreciated.

Thanks in advance.


问:
Making out a proof that manifolds are paracompact
I'm trying to prove any manifold is paracompact, and I'm stuck in the statement marked in red ink. Could anyone tell me how to arrive at this observation? Thank you.

If we add the hypothesis of second-countability to a locally compact Hausdorff space, we can prove even more. A sequence $(K_i)_{i=1}^\infty$ of compact subsets of a topological space $X$ is called an exhaustion of $\boldsymbol{X}$ by compact sets if $X=\bigcup_iU_i$ and $K_i\subseteq\mathrm{Int}\,K_{i+1}$ for each $i$.

Proposition A.60. A second-countable, locally compact Hausdorff space admits an exhaustion by compact sets.

Theorem 1.15 (Manifolds Are Paracompact). Every topological manifold is paracompact. In fact, given a topological manifold $M$, an open cover $\mathscr{X}$ of $M$, and any basis $\mathscr{B}$ for the topology of $M$, there exists a countable, locally finite open refinement of $\mathscr{X}$ consisting of elements of $\mathscr{B}$.

Proof. Given $M$, $\mathscr{X}$, and $\mathscr{B}$ as in the hypothesis of the theorem, let $(K_j)_{j=1}^\infty$ be an exhaustion of $M$ by compact sets (Proposition A.60). For each $j$, let $V_j=K_{j+1}\setminus\mathrm{Int}\,K_j$ and $W_j=\mathrm{Int}\,K_{j+2}\setminus K_{j-1}$ (where we interpret $K_j$ as $\varnothing$ if $j<1$). Then $V_j$ is a compact set contained in the open subset $W_j$. For each $x\in V_j$, there is some $X_x\in\mathscr{X}$ containing $x$, and because $\mathscr{B}$ is a basis, there exists $B_x\in\mathscr{B}$ such that $x\in B_x\subseteq X_x\cap W_j$. The collection of all such sets $B_x$, as $x$ ranges over $V_j$ is an open cover of $V_j$, and thus has a finite subcover. The union of all such finite subcovers as $j$ ranges over the positive integers is a countable open $\color{red}{\text{cover of }M}$ that refines $\mathscr{X}$. Because the finite subcover of $V_j$ consists of sets contained in $W_j$, and $W_j\cap W_{j'}=\varnothing$ except when $j-2\leq j'\leq j+2$, the resulting cover is locally finite. $\qquad\square$

答:
To see it is a cover, let $x \in M$, and let $j(x) \in \{1,2,3,\ldots\}$ the first $j$ such that $x \in K_j$ (the $K_i$ form a (n increasing) cover of $X$, so this is well-defined).
It is then clear that $x \in V_{j(x)-1}$ (note this set is indeed compact as a closed subset of $K_{j(x)}$), by this minimality, so it is going to be in the finite subcover of $B_x$ that are constructed at stage $i=j(x)-1$.


问:
Let $f:R^k \to R, k \geq 2$ Partial function, continuous in punctured neighborhood of $a \in R^k$ Prove $f$ Is not one-to-one
$k \geq 1, f:R^k \to R$ Partial function that is continuous in punctured neighborhood of $a \in R^k$, prove $f$ is not one-to-one.

I dont understand why $f$ Can’t be one to one, if lets say $k=2$, and $(x,y) \in R^2$ I can take a function like $(x,y) \to x*10+y$ And it seems one to one.

Can someone give me a direction?

答:
Sadly, your function $f$ is not one-to-one, because it is not injective. I assume you choose $a=0$ so for an abiatary small open neighborhood $U$ of $a$ we can still find $(x_1,y_1),(x_2,y_2)\in U$ with $(x_1,y_1)=(\tfrac{\delta}{10},0)$ and $(x_2,y_2)=(0,\delta)$ for $delta>0$ small enough. So our function $f$ givs us now $\delta=f(x_1,y_1)=f(x_2,y_2)$. So it is not injective.

Now in generell. Let $p_1,p_2\in U\subset \mathbb R^2$ with $U$ open und $f:U\to \mathbb R$ continuous. We can find some $b,c\in\mathbb R$ with $f(p_1)=b$ and $f(p_2)=c$. Now you could think about that we have for every $V\subset U$ with $p_1,p_2\in V$:
$$[f(p_1),f(p_2)]=[b,c]\subset f(V)$$
If we now take two different cruves $C_1,C_2\subset U$ with $C_1\cap C_2=\{p_1,p_2\}$ (and since $U$ is open there are such curves), we have:
$$[b,c]\subset f(C_1)\cap f(C_2)$$
It follows now that:
$$f(C_1\cap C_2)=\{b,c\}\not=f(C_1)\cap f(C_2)$$
So f can't be injectiv. (Because the last equation would be hold for every injective function).


问:
Simple Transport $u_t+cu_x=0$, why is the substance transported to the right at a fixed speed c?
In Partial Differential Equations by Walter Strauss, Ch 1.3, Example 1, they present the transport equation $u_t+cu_x=0$ whose solution is $u(x,t)=f(x-ct)$. They claim that this solution means the substance is transported to the right at a fixed speed c, why does this conclusion follow from the solution?

They also state that each particle moves in the $xt$ plane along a characteristic line. Why is this so?

答:
The transport equation models the concentration of a substance flowing at a constant rate.
Formally, for a parameter $v\in \mathbb{R}$, the transport equation on $\mathbb{R}\times \mathbb{R}^{+}$ is given by $$\frac{\partial u}{\partial t}(x,t)+v\frac{\partial u}{\partial x}(x,t)=0 \quad [1],$$
where $v$ is the velocity of the fluid. Now, the general solution by $[1]$ is given by $$u(x,t)=\phi(x-vt),$$where $\phi$ is an arbitrary function. But, if you have the initial value problem for the transfport equation given by $$(\operatorname{IVP}):\begin{cases}u_{t}+vu_{x}=0, \quad x\in \mathbb{R},t\in \mathbb{R}^{+}\\\left.u\right|_{t=0}=f(x), \quad x\in \mathbb{R}.\end{cases} \quad [2]$$
Then, the particular solution to $[2]$ is given by $$u(x,t)=f(x-vt).$$

They claim that this solution means the substance is transported to the right at a fixed speed $c$, why does this conclusion follow from the solution?

They also state that each particle moves in the $x-t$ plane along a characteristic line. Why is this so?

First, note that here I'm using $c=v$. Using the gradient operator $$\nabla:= \left( \frac{\partial }{\partial t}, \frac{\partial}{\partial x}\right),$$we can re-write $[1]$ as $$\nabla_{\vec{c}}u:=\vec{c}\cdot \nabla u=\begin{pmatrix} 1\\ v \end{pmatrix}\cdot \nabla u(x,t)=0. \quad [3]$$
Note that if there's not gradient, so there's not transport. Now, note that $[3]$ says that the directional derivative in the $\begin{pmatrix} 1\\ v \end{pmatrix}$ in the $x-t$ plane is zero. So, the solution of $[1]$ it's to say $u(x,t)$ must be constant in this direction. In the plane $x-t$, the $\begin{pmatrix} 1 \\ v \end{pmatrix}-$direction is along lines parralel $x=vt$ (characteristics of $[1]$).

I think this answers both questions. A tip if you are interested in the physical interpretation of the solution is to solve problems that involve the transport equation and you can observe some basic models.

Here, you can read a JJacquelin's answer about the "Understanding the solution to the transport equation $u_{t}+au_{x}=0$". Maybe it will be useful for you.


答:
The intuitive idea:
$$\forall m: P(m++)\implies P(m)$$
means than all the implication chains
$$P(n)\implies\cdots\implies P(2)\implies P(1)$$
are true.
Now, what happens if (for some $n$) $P(n)$ is true?


问:
$\|T(e_i+e_j)\| = \|e_i+e_j\|$ implies isometry
If V is a finite dimensional real inner product space with an orthonormal basis $e_1,...,e_n$, and there exists a linear operator $T$ such that $\|T(e_i+e_j)\| = \|e_i+e_j\|$ then $T$ is an isometry.

My attempts so far have been to write $v=\langle v,e_1\rangle e_1+...$ from which it follows $Tv=\langle v,e_1\rangle T e_1+...$ and thus $\|T(v)\|^2=\|\langle v,e_1\rangle T e_1+...\|^2$ but I cannot break this down further since we don't know if the $Te_i$'s aren't orthonormal. I also attempt to use the fact given that $\|T(e_i+e_j)\| = \|e_i+e_j\|$ but cannot find a way to incorporate that into the expansion.

Body: Hint: For $i \neq j$ we get $\|Te_i+Te_j\|^{2}=\|e_i+e_j||^{2}=2$. So $\|Te_i\|^{2}+\|Te_j\|^{2}+2 \langle Te_i, Te_j \rangle=2$. But $\|Te_i\|^{2}=\|Te_j\|^{2}=1$ so we get $ \langle Te_i, Te_j \rangle=0$.


问:
surface area illustration in Calculus Early Transcendentals
In Calculus Early Transcendentals, edition 6, the author uses a circular cone for a surface area problem on page 533.

The cone has a base radius $r$, slanted height $l$. A slice is made laterally, so that now there's a new cone (two cones, actually) with an upper radius $r_1$ and the same lower/base radius $r_2$. The top cone has a slanted height $l_1$, and bottom cone has a slanted height $l$.

The author says the area of the band was found by subtracting the area of the cones, $$A=\pi r_2(l_1+l)-\pi r_1 l_1=\pi[(r_2-r_1)l_1+r_2l]$$

These areas I don't understand. Shouldn't radius be squared?

Then they use similar triangles to find the area $A$. The only thing confusing me here is that $A=\pi(r_1 l+r_2 l)$ and thus $A=2\pi r l$. This suggests that $2rl=(r_1 l + r_2 l)$ which isn't clear to me.

答:
I think there is a problem that the author seamlessly switches from Fig. 2 (and the corresponding labels/symbols) to Fig. 3 - and so $l$ suddenly means a different thing. (On Fig. 2 it is the slant height of the full cone, on Fig. 3 it is the slant height of the frustum.)

Concentrating on Fig. 3, I will try to answer your questions:

Shouldn't radius be squared?

No. The area of the lateral surface of the cone is $\pi rl$, where $r$ is the radius of the base and $l$ is the slant height (using symbols from Fig 2 here). This was proven on the top of the page and on the bottom of the previous page. You can also see from "dimensionality analysis": both $r$ and $l$ are lengths (e.g. in inches), and so $\pi rl$ has the dimension of area (e.g. inches squared). If $r^2$ featured in the formula, the result would have the dimension of length cubed (i.e. of volume).

Apply that to Fig. 3, where the corresponding radii are $r_1,r_2$ and the slant heights are $l_1, l_1+l$, respectively.

This suggests that $2rl=(r_1l+r_2l)$ which isn't clear to me.

You need to again forget the symbol $r$ that was used on Fig. 2. The author reintroduces this symbol as $r=\frac{1}{2}(r_1+r_2)$ (the "average radius"), and then it is obviously $2r=r_1+r_2$, i.e. $2rl=(r_1l+r_2l)$.


问:
Entire function $f$ such that $|f(z)| ≤ K |z|^3$ for $|z|\ge1$ and $f(z) = f(iz)$ for every $z∈C$
Let $f(z)$ be an entire function such that for some constant $K$ , $|f(z)| ≤ K$ $|z|^3<$ for $|z|\ge1$ and $f(z) = f(iz)$ $∀z∈C$ , then which of the following are correct ?

(A)$ f(z) = Kz^3$ $∀ z∈\Bbb{C}$

(B) $f(z)$ is a constant function

(C) $f(z)$ is quadratic function

(D) No such $f$ exists

My attempt : I can deduce that since $f(z) = f(iz)$ and since $i^4=1 \implies f$ must involve only fourth powers of $z$ . Hence $f(z)=a_1z^4+b_1z^8+c_1z^{16}+ \cdots $-------(1)

Also for $|z| \ge 1 $: let C.

Then $|g(z)| = |f(z)|/|z^3| \le k$

=> By the Cauchy estimate theorem we can prove that :
$f(z)/z^3$ is a constant function $= c $

$\implies f(z)=cz^3$ for $|z| > 1$     ...........(2)

From (1) and (2) ; we get  there does not exist a function like this ?

My textbook answer says it's a constant function ?

答:
We cannot immediately use Cauchy's estimates because the theorem requires a bound on $D(0, R)$ and our bound is on $|z| \ge 1$. But we can fix that. Since $f$ is entire (in particular, continuous) and the closed unit disk is compact, there exists $M > 0$ so that $f(z) \le M$ for all $|z| \le 1$. Putting both bounds together, we have:
$$
\left|f(z)\right| \le K|z|^3 + M \quad \forall z \in \Bbb C
$$

Now we can apply Cauchy's estimates as in this answer and conclude that $f$ is a polynomial of degree $3$ at most.

We also have the fact that $f(z) = f(i z)$ for all $z \in \Bbb C$. This forces $f$ to be of the form:
$$
f(z) = \sum_{n=0}^\infty a_n z^{4n}
$$

Notice that the series may contain a constant term.

Putting both results together, we conclude that $f$ must be constant.


问:
Find the minimum p: for q > p cubic $ x^3 -7x^2 + qx + 16 =0 $ has only one real root using algebraic arguements only
Hi this question can be easily solve with turning point arguement used in differential calculus, I'm curious how to solve it in an algebraic way i.e. using only algebraic arguments in the proof and avoid calculus and or powerful theorems relying on analysis.

So far I used Vieta's relation and some plug n' chug to arrive at:

$ q > \frac{49}{4}$

The correct answer is p = 8 i.e. $q > 8$

答:
If $q=8$ then $(x-4)^2(x+1)=0$ has three roots so $p\ge 8$. Now consider $q>8$ and suppose there is more than 1 real root. Then all three (counting multiplicity) roots are real and, by Vieta, their product is $-16$.

However the equation can be written as $$(x-4)^2(x+1)=(8-q)x.$$

The cubic $y=(x-4)^2(x+1)$ has no points in the fourth quadrant and only has points in the second quadrant for $-1\le x\le0$. However, $y=(8-q)x$ only has points in the second and fourth quadrants.

Therefore all three roots satisfy  $-1\le x\le0$ and so the product of the roots has magnitude at most $1$, a contradiction.

Therefore $p=8$.


问:
Line Drawing Using Bresenham Algorithm
Indicate which raster locations would be chosen by Bersenham’s algorithm when scan converting a line from screen co-ordinates (1,1) to (8,5).

First the straight values (initial values) must be found

```<code>                          dx=x2-x1                      8-1=  7
                          dy= y2-y1                     5-1=  4
</code>```

Therefore                     d=2dy-dx                       2*4-7=   1    initial values

The answers are found to be.

Now the question is how did we got the "d" values. With step by step explanation.

答:
Here's my implementation of Bersenham’s Algorithm in Python.

```<code># bresenham's line drawing algorithm

x0, y0 = map(int, input("Enter the start points: ").split())
x1, y1 = map(int, input("Enter the final points: ").split())

dx = x1 - x0
dy = y1 - y0

x = x0
y = y0

m = dy / dx

print(f"\nSlope = {m}\n")
print("x\t\ty\t\td")
print("-\t\t-\t\t-")
print(f"{x}\t\t{y}\t\t{dd}")

if 0 < m < 1:

    dd = 2*dy - dx

    for x in range(x0+1, x1+1):
        if dd >= 0:
            y += 1
            dd += 2 * (dy - dx)
        else:
            dd += 2 * dy
        print(f"{x}\t\t{y}\t\t{dd}")

elif m > 1:

    dd = 2*dx - dy

    for y in range(y0+1, y1+1):
        if dd >= 0:
            x += 1
            dd += 2 * (dx - dy)
        else:
            dd += 2 * dx
        print(f"{x}\t\t{y}\t\t{dd}")

</code>```

If you unroll the loop you'll see exactly how dd or decision parameter gets updated at each step.

Title: Line Drawing Using Bresenham Algorithm

Body:
Here's my implementation of Bersenham’s Algorithm in Python.

# bresenham's line drawing algorithm

x0, y0 = map(int, input("Enter the start points: ").split())
x1, y1 = map(int, input("Enter the final points: ").split())

dx = x1 - x0
dy = y1 - y0

x = x0
y = y0

m = dy / dx

print(f"\nSlope = {m}\n")
print("x\t\ty\t\td")
print("-\t\t-\t\t-")
print(f"{x}\t\t{y}\t\t{dd}")

if 0 < m < 1:

    dd = 2*dy - dx

    for x in range(x0+1, x1+1):
        if dd >= 0:
            y += 1
            dd += 2 * (dy - dx)
        else:
            dd += 2 * dy
        print(f"{x}\t\t{y}\t\t{dd}")

elif m > 1:

    dd = 2*dx - dy

    for y in range(y0+1, y1+1):
        if dd >= 0:
            x += 1
            dd += 2 * (dx - dy)
        else:
            dd += 2 * dx
        print(f"{x}\t\t{y}\t\t{dd}")

If you unroll the loop you'll see exactly how dd or decision parameter gets updated at each step.


问:
Find the critical point of the function
Consider the following function.

$g(x, y)=e^{−8x^2−6y^2+24y}$

(a) Find the critical point of g.

(b) Using your critical point in (a), find the value of D(a, b) from the Second Partials test that is used to classify the critical point.

(c) Use the Second Partials test to classify the critical point from (a).

For C, the options are either

Saddle Point, Relative Minimum, Relative Maximum, or Inconclusive

I could really used some help finding the critical point. I separated them into $f_x$ and $f_y$ and set them equal to 0 and got (24,0). I'm not sure if this answer is right and what I am supposed to do to find b.

答:
If we write this function as

$$ g(x,y) \ \ = \ \ e^{−8x^2−6y^2+24y} \ \ = \ \ e^{−(8x^2+6y^2-24y)} \ \ = \ \ e^{−[8x^2 \ + \ 6(y-2)^2 \ + 24]} \ \  = \ \ e^{−8x^2}  ·  e^{−6(y-2)^2}  ·  e^{24} \ \ , $$

one thing we can see is that the level curves are ellipses  $ \ 8x^2 \ + \ 6(y-2)^2 \ = \ C \ \ , \ \ C \ \ge \ 0 \ $ centered on $ \ (0,2) \ \ , $ using "completing the square" as Fred shows.  Since we can express $ \ g \ $ as an "exponentially-decaying" function, we would expect there to be a maximum value for the function $ \ g(0,2) \ = \ e^{24} \ . $  [The graph is only worth plotting with extreme vertical scale compression, since $   \ e^{24} \ = \ (e^3)^8 \ \approx \ 20^8 \ \approx \ 2.6 · 10^{10} \ .  $ ]

You didn't show what you found for the first partial derivatives, so it isn't possible to see why you found the result you did.  We work out the relevant partial derivatives here to see up the Hessian matrix:

$$ f_x \ \ = \ \  e^{24} \ · \ (-16x) · e^{−8x^2} \ · \ e^{−6(y-2)^2} \ \ , \ \  f_y \ \ = \ \  e^{24} \ · \  e^{−8x^2} \ · \ [-6·2·(y-2)]·e^{−6(y-2)^2} \ \ ; $$

[the second partial derivatives require the application of the Product Rule]

$$ f_{xx} \ \ = \ \  e^{24} \ · \ \left[ \ (-16) · e^{−8x^2} \ + \ (-16x) · (-16x) · e^{−8x^2} \ \right] \ · \ e^{−6(y-2)^2} \ \ , $$

$$ f_{yy} \ \ = \ \  e^{24} \ · \ (-16) · e^{−8x^2}   \ · \ \left[ \ (-12) · e^{−6(y-2)^2} \ + \ [-6·2·(y-2)]^2·e^{−6(y-2)^2} \right]\ \ , $$

$$ f_{xy} \ \ = \ \  e^{24} \ · \  (-16) · e^{−8x^2}  \ · \ [-12·(y-2)]·e^{−6(y-2)^2} \ . $$

Simplifying the expressions, the Hessian matrix is then

$$ \mathcal{H} \ \ = \ \ \left| \begin{array}{cc} -16·(1-16x^2) & 16·12·(y-2) \\
16·12·(y-2) & 12^2·(y-2)^2 \ - \ 12 \end{array}  \right| \ · \ e^{−8x^2}  ·  e^{−6(y-2)^2}  ·  e^{24}  $$

[there is no compelling need to "pretty up" the entries, as it is easier to see what the evaluation will be in this form] .

At the critical point,

$$ \mathcal{H} \ |_{(0,2)} \ \ = \ \ \left| \begin{array}{cc} -16·(1-0) & 16·12·(2-2) \\
16·12·(2-2) & 12^2·(2-2)^2 \ - \ 12 \end{array}  \right| \ · \ e^0  ·  e^0  ·  e^{24}  $$
$$  = \ \ \left| \begin{array}{cc} -16 & 0 \\
0 &  -12 \end{array}  \right|  · \  e^{24} \ \ > \ \ 0 \ \ .  $$

This shows that the critical point is a local extremum.  Since

$$ f_{xx} \ |_{(0,2)} \ \ = \ \  e^{24} \ · \ \left[ \ (-16) · e^0 \ + \ 0 · 0 · e^0 \ \right] \ · \ e^0 \ \ = \ \  (-16) · e^{24} \ \ < \ \ 0 , $$

it is a local maximum, as we anticipated.

Title: Find the critical point of the function


问:
How to find the pmf of the number of students who get their passport back?
$4$ passports are returned randomly to $4$ students. Let the random variable $X$ be the number of students who get their passport back. Determine the pmf of $X$.

Answer:

$$p(0) = \frac{9}{24}, p(1) = \frac{1}{3}, p(2) = \frac{1}{4}, p(3) = 0, p(4) = \frac{1}{24}$$

I understand that $p(3) = 0$ because if $3$ people get the correct passport back then that implies the remaining person got the wrong passport which is not possible since the remaining passport must be the correct passport. I think my answer makes more sense even though it is incorrect. My question is how is the answer above obtained and why is my answer incorrect?

My answer:

Let $e=${at least one person gets their passport back}$=${$e_1$,$e_2$,$e_3$,$e_4$} where $e_i$ is the subevent that $i$th person gets back their passport.

So the pmf $P(X=e)=p(e)$ is

$$p(0) = p(\bar e)=1-p(e)=1-[p(1)+p(2)+p(3)+p(4)]$$
$$p(1) = \frac{\binom{4}{1}}{4!}, p(2) = \frac{\binom{4}{2}}{4!}, p(3) = \frac{\binom{4}{3}}{4!}, p(4) = \frac{\binom{4}{4}}{4!}$$

which simplifies to

$$p(0) =\frac{9}{24}, p(1) = \frac{4}{24}, p(2) = \frac{6}{24}, p(3) = \frac{4}{24}, p(4) = \frac{1}{24}$$

Only $p(1)$ and $p(3)$ are incorrect. Although the correct answer for $p(3)=0$, I think $p(3)=\frac{4}{24}$ because technically $4$ people are getting back their passports if $3$ people get back the correct passport. Can someone explain why my answer is wrong? Also my probabilities still add up to $1$ although it is incorrect.

答:
Let me show you a very simple way to solve the problem. You have to calculate 5 probabilities

$P(0)$

$P(1)$

$P(2)$

$P(3)$

$P(4)$

$P(3)=0$, trivial because, as you noted, if 3 passports are correct it is not possible to have the fourth wrong.

$P(0)=\frac{9}{24}$ as there are

$!4=4!\left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\right)=9$ favourable ways to have permutations of elements all wrong on 24 possible ways

$P(4)$, conversely, there
is only 1  favourable permutation on the 24 possible

with similar reasoning as $P(0)$

$$P(1)=\frac{ !3}{6}=\frac{1}{3}$$

$P(2)$ can be derived as complement probability to 1


问:
Cauchy criterion problem
Suppose that $\{x_m\}$ is a sequence of positive, non-zero numbers such that $\sum_{n=1}^{\infty} {x_n}$ diverges, and let $S_n = x_1 + x_2 + ... + x_n$. Moreover, suppose that for all $m \geq 1$ and $n \geq 1$, $\sum_{j=1}^{n} \frac{x_{m + j}}{S_{m + j}} \geq 1 - \frac{S_m}{S_{m + n}}$. Use the Cauchy criterion to show that $\sum_{n=1}^{\infty} \frac{x_n}{S_n}$ diverges.

I'm not very sure how to tackle this problem. I somewhat understand how to approach it but I'm unsure how the formal proof would look like. Any hints or assistance is much appreciated.

答:
Assume that $\sum_{n=1}^\infty \frac{x_n}{S_n}$ is convergent. Let's write out the Cauchy criterion: Let $\varepsilon>0$ be any number less than $1$ (if you want you can fix e.g. $\varepsilon=\frac{1}{2}$). Then there is some natural number $N$ such that for all $m\geq N,k\geq 1$ we have $$\sum_{j=m+1}^{k+m}\frac{x_j}{S_j}<\varepsilon$$
By shifting indices we get: $$1-\frac{S_m}{S_{m+k}}\leq\sum_{j=1}^{k}\frac{x_{j+m}}{S_{j+m}}<\varepsilon$$
Now what happens if we let $k\to\infty$?

Title: Cauchy criterion problem


问:
Is this operator T compact on $L^2([0,1])$?
Consider $L^2([0,1])$ and the operator $$Tu(t) = tu(t)$$for a.e. $t \in [0,1]$

How can I prove or disprove that T is compact?
Thanks!

答: On the infinite dimensional invariant subspace $\{f\in L_2([0,1]): f_{[0,1/2]}=0\}$ the operator is invertible.


答:
Your formula is $\frac{combinations}{permutations}$. As you know
$combinations=\frac{permutations}{redundancies}$, so each probability
that you calculated is $\frac{combinations}{permutations}=\frac 1
   {redundancies}$ and doesn't have much meaning. For example, for
$\frac{4\choose 2}{4!}=\frac{1}{2!2!}$ is the probability of picking
a unique sequence when you've got two groups of two things, e.g. if
we were to put A, B where the underscores are and C, D in the
exclamation marks, _ ! ! _, you have calculated the probability of
getting one unique sequence such as ACDB. The immediate relation to
the problem is not clear.

Instead, you should reason as follows. For p(1), there is 1/4 chance
that the correct letter goes to student-1. Then the remaining letters
have a 2/3 * 1/2 * 1 chance of going to an incorrect student. Now
this can also happen to students, 2, 3, and 4, so multiply this
probability by 4 to get $\frac 1 4\left(\frac 2 3 *\frac 1 2*
   1\right)*4=\frac 1 3$. For p(3), it is not possible to get exactly 3
right matches because of exactly what you said. p(4) is a separate
case than p(3). p(4) is when all 4 people get their passports back,
but it so happens that it is not p(3) because p(3) is when 3 people
get their passports back and 1 does not - there is an important
distinction.

Title: How to find the pmf of the number of students who get their passport back?

Body:
$4$ passports are returned randomly to $4$ students. Let the random variable $X$ be the number of students who get their passport back. Determine the pmf of $X$.

Answer:

$$p(0) = \frac{9}{24}, p(1) = \frac{1}{3}, p(2) = \frac{1}{4}, p(3) = 0, p(4) = \frac{1}{24}$$

I understand that $p(3) = 0$ because if $3$ people get the correct passport back then that implies the remaining person got the wrong passport which is not possible since the remaining passport must be the correct passport. I think my answer makes more sense even though it is incorrect. My question is how is the answer above obtained and why is my answer incorrect?

My answer:

Let $e=${at least one person gets their passport back}$=${$e_1$,$e_2$,$e_3$,$e_4$} where $e_i$ is the subevent that $i$th person gets back their passport.

So the pmf $P(X=e)=p(e)$ is

$$p(0) = p(\bar e)=1-p(e)=1-[p(1)+p(2)+p(3)+p(4)]$$
$$p(1) = \frac{\binom{4}{1}}{4!}, p(2) = \frac{\binom{4}{2}}{4!}, p(3) = \frac{\binom{4}{3}}{4!}, p(4) = \frac{\binom{4}{4}}{4!}$$

which simplifies to

$$p(0) =\frac{9}{24}, p(1) = \frac{4}{24}, p(2) = \frac{6}{24}, p(3) = \frac{4}{24}, p(4) = \frac{1}{24}$$

Only $p(1)$ and $p(3)$ are incorrect. Although the correct answer for $p(3)=0$, I think $p(3)=\frac{4}{24}$ because technically $4$ people are getting back their passports if $3$ people get back the correct passport. Can someone explain why my answer is wrong? Also my probabilities still add up to $1$ although it is incorrect.


问:
Hessian of $f(x) = e^{u^Tx}$ for some $u\in \mathbb{R^d}$
I'm seeing the hessian is $uu^Te^{u^Tx}$. From my understanding since this is a single variable function, we can basically treat $u^T$ as a constant and the hessian is equivalent to the second derivative of f(x) with respect to x. My question is why is the solution $uu^Te^{u^Tx}$ and not $u^Tu^Te^{u^Tx}$.  Is this because the vector dimensions for $u^Tu^T$ don't work for multiplication? - If that's the case, why can we just swap $u^Tu^T$ with $uu^T$?

答:
Let $x=(x_1,....,x_d)$ and $u=(u_1,...,u_d).$ Then:

$$f(x)=\prod_{j=1}^d e^{x_ju_j}.$$

This gives

$$f_{x_k}=u_kf(x).$$

and

$$f_{x_ix_k}=u_iu_kf(x).$$

Thus the Hessian is given by

$$uu^Tf(x)=uu^Te^{u^Tx}.$$


问:
Geometrically seeing the linking of the fibres in the Hopf fibration?
I'm working through the following document: https://arxiv.org/pdf/0908.1205.pdf

I can understand the construction of the Hopf map using the Riemann sphere but I struggle to understand the geometric argument in section 4.3, 'the fiber circles are linked'.

The author mentions an equitorial sphere in $S^3$, $E$,  which is of course obtained by setting $x_4 = 0$. Now we consider the fiber $F$ that lies along the equator of the equitorial sphere where $x^4 = 0$.

Now we want to show that any other fibre of the Hopf map can connect any other point in $S^3$ to antipodal points along $E$. If the point on $S^3$ is $(z_1, z_2$) I can use a complex number $\lambda$ in order to 'rotate' the fiber into the plane of  $x^4 = 0$.

I really then struggle to understand how this shows that the fibers are linked by following this geometric argument. I would appreciate it if someone could clarify the steps/logic/etc.

答:
Consider the stereographic projection of this situation. Imagine a $2$-sphere in $\mathbb{R}^3$ with a blue equator, and there is another orange circle intersecting opposite hemispheres (at red points). I think it should be relatively evident these two are linked!

For more details, you should be able to slide the red circle to be as far away from the blue one as possible: namely, the line that the blue circle is wrapped symmetrically around (this corresponds to a circle in $S^3$ through the pole we project from - in this case the two circles are in orthogonal planes). Throughout the whole sliding process (using the action of $S^3$ on itself), the red circle never intersects the blue circle, so whether or not they're linked doesn't change. Then the complement of the blue circle retracts onto the red circle (within $S^3$, or $\mathbb{R}^3$ with a point at infinity). Thus, the red circle repreents a nontrivial element of the complements' fundamental group, which isn't possible if it isn't linked.


答:
For guessing the answer $q=8$: just try to find the borderline case, i.e. one simple root and a repeated root. Say $a$ is the simple root and $u$ is the repeated one.

Using Vieta, it boils down to $a+2u=7, au^2=-16$. Hence $2u^3-7u^2-16=0$. Test roots using rational root theorem, and we find $(u-4)(2u^2+u+4)=0$. The only solution is $u=4$, giving $q=8$.

Title: Find the minimum p: for q > p cubic $ x^3 -7x^2 + qx + 16 =0 $ has only one real root using algebraic arguements only

Body:
Hi this question can be easily solve with turning point arguement used in differential calculus, I'm curious how to solve it in an algebraic way i.e. using only algebraic arguments in the proof and avoid calculus and or powerful theorems relying on analysis.

So far I used Vieta's relation and some plug n' chug to arrive at:

$ q > \frac{49}{4}$

The correct answer is p = 8 i.e. $q > 8$


问:
Find a formula that defines the union A ∪ B in terms of the operations of intersection and complement
The formula A\B = A∩B' defines the difference operation in terms of the operations of intersection and complement.
Find a formula that defines the union A ∪ B in terms of the operations of intersection and complement.
I have an idea for what the expression will be but if I just wrote it out and then proved it, would that be valid?</p>

答:
What about
$$A \cup B = (A^c \cap B^c)^c \quad ?$$


问:
Show gl dim$R=\sup\{pd_RI\}$, where I runs through all right ideals of $R$, where $R$ is not Wedderburn
Question: Show gl dim$R=\sup\{pd_RI\}+1$, where I runs through all right ideals of $R$, where $R$ is not Wedderburn.

Thoughts: I know that gl dim$R=1$ iff $R$ is a hereditary ring, but not Wedderburn.  So, I am seeing where the question is "coming from", but I am not quite seeing a way to, sort of, break up $R$ in the question. Do we just break it up into its hereditary part and its non-hereditary part? Or, could we maybe play around with short exact sequences..?  Any thoughts, ideas, or help is greatly appreciated!

答:
This result was probably first stated in a On the Dimension of Modules and Algebras (III): Global Dimension by Maurice Auslander (as is often the case for theorems on homological dimensions).

The proof relies on two crucial results from homological algebra. Let me state everything for left ideals, you may recover your result for right ideals by just passing to the dual ring.

Theorem 1 (Auslander). Let $R$ be a ring, then $$\operatorname{gl.dim}(R) = \sup \{\operatorname{pd}_R(M) \mid M \text{ cyclic } R \text{-module} \} = \sup \{\operatorname{pd}_R(R/I) \mid I \subseteq R \text{ left ideal} \}.$$

This is a non-trivial result and relies on the Well-Ordering Theorem.

Lemma 2. Let $0 \to U \to P \to M \to 0$ be a short exact sequence with $P$ projective and $U$ non-projective. Then, $\operatorname{pd}(M) = \operatorname{pd}(U) + 1 $.

You can find references for these two results in the paper by Auslander. Both only use basic homological results.

Moreover, from Theorem 1, it follows that $R$ is semisimple if and only if $R/I$ is projective for every left ideal $I \subseteq R$. So if $R$ is not semisimple, there exists an ideal $I \subseteq R$ such that $R/I$ is not projective and therefore $\operatorname{pd}_R(R/I) = \operatorname{pd}_R(I) + 1$ for such $I$. Applying Theorem 1 yields your desired result $$\operatorname{gl.dim}(R) = \sup_I\{\operatorname{pd}_R(I) \} + 1.$$


问:
Prove that the number of vectors in sphere of radius r centered at vector u S-r(u) is $\sum_{i=0}^r \binom{i}{n} (q-1)^i$
I am having a problem understanding this.  I would totally appreciate for any help.

Prove that the number of vectors in sphere of radius $r$ centered at vector $u \in \mathbb{F}_q^n$ $S_r(u)$ is $\sum_{i=0}^r \binom{i}{n} (q-1)^i$, where

$S_r(u) = \{v \in \mathbb{F}_q^n \lvert d(u,v) \leq r\} $ and $d(u, v)$ is the hamming distance of the vectors $u$ and $v$ in $\mathbb{F}_q^n$.

My analysis is this,

If I take an element $u \in \mathbb{F}_q^n$, then the remaining vectors left in $\mathbb{F}_q^n$ is $q-1$.  Taking the distance starting from the center to $r$ it takes that there are $r$ processes.  I don't know know the existence of combinations existence in the formula.

please help me with this.

答:
The correct formula is $\sum_{i=0}^r {n\choose i} (q-1)^i$.

To see this, note that $n\choose i$ is the number of $i$-element subsets of the set $\{1,\ldots,n\}$.

Thus the partial sum ${n\choose i} (q-1)^i$ describes the number of ways to fill $i$ positions of the $n$ coordinate positions with nonzero elements of $GF(q)$.

The outer summation ranges from $0$ (zero vector) to the radius $r$.


问:
Finding the x coordinate of A
The curve C has this equation:

$2x^{2}y+2x+4y-\cos(\pi y) = 17$

The point $\mathbf{P}$ with coordinates $(3, \frac{1}{2})$ lies on C.

The normal C at P meets the x-axis at the point A.

a. Find the x coordinate of A, giving your answer in the form $\frac{a\pi + b}{c\pi + d}$

Where do I begin? I thought of replacing the X and Y values with the coordinates, however, that's not the result I'm expecting.

答:
Hint: you need the slope of the curve at the given point, and for this you can (or have ) to differentiate implicitly:

$$2x^{2}y+2x+4y-cos(\pi y) = 17\implies4xy+2x^2y'+2+4y'+\pi\sin\pi y\,y'=0\implies$$

$$(2x^2+4+\pi\sin\pi y)y'=-4xy-2\implies y'=-\frac{4xy+2}{2x^2+4+\pi\sin\pi y}$$

and now imput the coordinates of $\;P\;$ in the above and you have the slope of the tangent to the curve at $\;P\;$ (or the slope of the curve at $\;P\;$, as we many time use to say in short), so now find the normal = the perpendicular to this tangent line...

Title: Finding the x coordinate of A


问:
$f$ is integrable iff this weird simple function is integrable.
I want to show that if $f:X\rightarrow\mathbb R$ is measurable and $a>1$, then $f$ is integrable iff
$$\sum_{n\in\mathbb {Z}}a^n\mu(\{a^n\le\lvert f\rvert < a^{n+1}\})<\infty.$$
If we define $A_n=\{a^n\le\lvert f\rvert < a^{n+1}\}$, which are disjoint, measurable sets then of course $s_n:=\sum_{-n}^n a^k\chi_{A_k}$ are nice simple functions for all $n\in\mathbb Z$. However $f$ is not dominated by $s_n$ and $s_n$ don't converge to $f$, so I can't use the go-to convergence theorems.

This also reminds me of Borel-Cantelli from probability theory, but this is a problem from measure/integration theory.

Is there some way to derive the integrability of $f$ from the integrability of the simple functions? Or am I missing a better approach?

答:
We have $\int |f|d\mu=\sum \int_{A_n} |f|d\mu$ and

$$a^{n}\mu (A_n) \leq \int_{A_n} |f|d\mu \leq a^{n+1}\mu (A_n)$$

That is all you need. No theorems like Borel-Cantelli , DCT etc are required.


问:
Existence of periodic solution in an ODE system
Let the ODE system,

\begin{cases}x'(t)=x^3+x^5 \\ y'(t)=y+y^7 \end{cases}

defined in $\mathbb{R}^2$.

I need to say if this system supports periodic solution with period $T>0$.

This is a question of Analysis in $\mathbb{R}^n$ not ODE, that is, I need to demonstrate this using concepts presented in Analysis in $\mathbb{R}^n$, my textbook is Analysis on Manifolds by Munkres. The hint is,

A periodic solution of the system above is a closed curve $\gamma(t) = (x(t), y (t))$ that satisfies the system.

I believe I have to use Stokes, but I am not able to proceed with the solution.

答:
The decoupled dynamic system can be integrated as follows

$$
\cases{
\frac{dx}{x^3+x^5}= dt\\
\frac{dy}{y+y^7}= dt
}\ \ \Rightarrow \cases{\ln \left(x^2+1\right)-2 \ln (x)-\frac{1}{x^2}=2t\\ \ln (y)-\frac{1}{6} \ln \left(y^6+1\right)=t}\ \ \Rightarrow \cases{\psi(x) = 2t\\ \phi(y) = t}
$$

As can be verified $\psi, \phi$ are analytic strict increasing functions in $\mathbb{R}_{+}$ so their inverses $x=\psi^{-1}(t), y=\phi^{-1}(t)$ are also strict increasing functions. The conclusion is that under such circumstances no periodic orbit is possible.


Title: Finding the x coordinate of A

Body:
The curve C has this equation:

$2x^{2}y+2x+4y-\cos(\pi y) = 17$

The point $\mathbf{P}$ with coordinates $(3, \frac{1}{2})$ lies on C.

The normal C at P meets the x-axis at the point A.

a. Find the x coordinate of A, giving your answer in the form $\frac{a\pi + b}{c\pi + d}$

Where do I begin? I thought of replacing the X and Y values with the coordinates, however, that's not the result I'm expecting.

Body:
$$2x^{2}y+2x+4y-\cos(\pi y) = 17 \implies 4xy+2x^2y'+2+4y'+\pi y' \sin(\pi y)=0$$
$$ y'(x,y)=\frac{(-4xy-2)}{2x^2+4+\pi \sin \pi y} \implies y'(3,1/2)=\frac{-8}{22+\pi},m_N=\frac{22+\pi}{8}.$$ $m_N$ is the slope of the required normal whose equation is
$$y-1/2=\frac{22+\pi}{8}(x-3).$$ When $y=0$, the value of $x$ is
$$x=\frac{3\pi+62}{\pi+22}\implies a=3,b=62,c=1,d=22.$$


问:
Determining if ellipse is fully inside another ellipse
I have two ellipses which are both not rotated, but have different sizes. I want to know if the smaller ellipse 1 is fully inside the larger ellipse 0. In my special case both ellipses have the same axis ratio, so $a_0/b_0=a_1/b_1$<s>, but I doubt this makes a difference for the calculation</s>.

I have started to work on a solution, but I am not so sure if this is the right approach and if it will ultimately lead to success. Here is what I have come up with so far:

The radius of ellipse 0 can be calculated for any point on the ellipse as

$$
r_0=\sqrt{(x-x_0)^2+(y-y_0)^2}
$$
The general equation for an ellipse gives a relation between $x$ and $y$ for points on the ellipse.

$$
\frac{(x-x_0)^2}{a^2}+\frac{(y-y_0)^2}{b^2}=1
$$

$$
(y-y_0)^2=b*\sqrt{1-\frac{(x-x_0)^2}{a^2}}
$$

This can be used to calculate radius of both ellipses depending on the x coordinate.

$$
r_0 = \sqrt{(x-x_0) + b_0^2(1-\frac{(x-x_0)^2}{a_0^2})}
$$

$$
r_1 = \sqrt{(x-x_1) + b_1^2(1-\frac{(x-x_1)^2}{a_1^2})}
$$

To calculate the distance $s$ between both ellipses at a certain $x$ coordinate, we simply have to add the distance $d_{01}$ between the center points to radius 1 and subtract this from radius 0.

$$
s=r0 - (d_{01} + r1)
$$
where
$$
d_{01} = \sqrt{(x_1-x_0)^2 + (y1-x_0)^2}
$$

Now I have an equation where $s$ only depends on $x$. My idea is to get the minimum of $s$ through the first derivative. If the minimum is non-negative, ellipse 1 is inside or on ellipse 0. If it is negative, part of ellipse 1 is outside ellipse 0.

Here are my questions:

Am I on the right way so far?

Is calculating the minimum for s the right approach?

Do I have a chance to actually calculate the minimum of $s$?

Note: Ther is a similar question here, but I think my case is much simpler because the ellipses are <s>not rotated</s> similar.

答:
Because they have the same axis ratio and are orientated the same, the easy solution is to multiply all y-coordinates by $\frac{a}{b}$. Then you have two circles.

All points on the large circle are within $a_0$ of its centre whereas all points on the small circle are within $a_l+\sqrt{(x_l-x_0)^2+\frac{a^2}{b^2}(y_l-y_0)^2}$.


问:
Characteristic polynomial, and a coprime polynomial
I'm a bit stuck on this following question in algebra, I hope someone can show me to the right direction.

Let $A\in M_n(F)$ be a matrix and let $f\in F[X]$ be a polyonimal such that $\gcd(f,P_a)=1$, with $P_a$ being the characteristic polynomial of $A$. Show that $f(A)$ is an invertible matrix.

I've tried showing that if $f(A)$ is not invertible, then its determinant is zero and there should be some common root for $f$ and $P_a$, but didn't seem to find a way.

Thanks for the help.

答: Note that $\gcd (f,P_a)=1$ implies there exist polynomials $g$ and $h$ such that $gf+hP_a=1$. Hence $I=g(A)f(A)+h(A)P_a(A)$. Now you have $P_a(A)=0$ and hence $f(A)$ is invertible.</p>


答:
$p(3) = 0$ because as you mentioned, if three people get their passport back then the remaining person cannot get the wrong passport, hence this event never occurs.

Your answer for $p(1)$ is close to the correct answer. You have to multiply $p(1)=\frac{\binom{4}{1}}{24}$ by 2  because $\binom{4}{1}$ is the number of ways to select one person to get the correct passport out of four possible people. This is equivalent to the number of people who get the incorrect passport. For instance, let the three remaining people/passports be $p_1,p_2,p_3$. There are 2*$\binom{4}{1}$ ways they can get the incorrect passport.

For example,

if $p_1$ gets $p_2$'s passport then

$p_2$ gets $p_3$'s passport and

$p_3$ gets $p_1$'s passport.

This can happen in $2$ ways, hence $p(1)=\frac{2*\binom{4}{1}}{24}=\frac{8}{24}$


问:
Independent random variables with zero mean: inequalities
Let $X_1,\ldots,X_n,\ldots$ independent random variables with zero mean, define:

$$S_n=X_1+X_2+\ldots+X_n$$

and

$$M_n=\text{max}\{\vert S_k \vert : k \in \{1,\ldots,n\} \} $$

Prove that:

$$\mathbb{E}(S_n^2 I_{A_k}) > c^2 \mathbb{P}(A_k)$$

where $A_k=\{M_{k-1}\leq c < M_k\}$ and $c>0$. Also prove that:

$$ \mathbb{P}( \text{max}\{\vert S_k \vert ; k \in \{1,\ldots,n\}\} >c) \leq \dfrac{\mathbb{E}(S_n^2)}{c^2}, \quad c>0$$

Honestly I have tried using inequalities and integrals (for the first part) and have not achieved much. Any help would be great, thank you very much.

答:
Both problems are essentially consequences of the Kolmogorov's inequality . First, let's to make the notation a bit simpler, for that you can read the reference easier.

Let $X_{1},X_{2},\ldots,X_{n}$ be independent random variables with mean $\mathbb{E}[X]=0$ and suppose that $\forall k\in \mathbb{N}$ we have that $\mathbb{V}ar[X_{k}]<\infty$. Also, let's to make  $$S_{n}:=X_{1}+X_{2}+\cdots+X_{n},$$
$$M_{n}:=\max_{1\leq k\leq n}|S_{k}|$$

So, in the first part you need to prove that $$\mathbb{E}[S_{n}^{2}\mathbb{I}\{A_{k}\}]>c^{2}\mathbb{P}[A_{k}]$$

Sketch prove: First, note that since that the mean is $0$, so  $ \displaystyle \mathbb{E}[S_{n}^{2}]=\sum_{k=1}^{n}\mathbb{V}ar[X_{k}]$.

Now,
\begin{eqnarray*}
\mathbb{E}[S_{n}^{2}\mathbb{I}\{A_{k}\}]&=&\mathbb{E}[(S_{k}^{2}+2S_{k}(S_{n}-S_{k})+(S_{n}-S_{k})^{2})\mathbb{I}\{A_{k}\}]\\
&\geq &\mathbb{E}[((S_{k}^{2}+2S_{k}(S_{n}-S_{k}))\mathbb{I}\{A_{k}\}]\\
&=&\mathbb{E}[S_{k}^{2}\mathbb{I}\{A_{k}\}], \quad S_{n}-S_{k}\perp S_{k}\mathbb{I}\{A_{k}\},\\
&>&^{2}\mathbb{E}[\mathbb{I}\{A_{k}\}]\\
&=&c^{2}\mathbb{P}[A_{k}]
\end{eqnarray*}

For the second part, you need to prove that $$\mathbb{P}\left[\max_{1\leq k\leq k} |S_{k}|>c \right]\geq \frac{1}{c^{2}}\mathbb{E}\left[\max_{1\leq k \leq n}|S_{k}| \right]^{2}$$
for that you can use the first part and the Chebyshev's inequality.

Remark 1: The Kolmogorov's inequality says that: If $X_{1},X_{2},\ldots,X_{n}$ be independent random variables with mean $0$ and asumming that $\mathbb{V}ar[X_{k}]<\infty$ for all $k\in \mathbb{N}$. Then, we have that for all $c>0$, $$\mathbb{P}\left[ \max_{1\leq k\leq n} |S_{k}|>c \right]\leq \frac{1}{c^{2}}\sum_{k=1}^{n}\mathbb{V}ar[X_{k}].$$

Remark 2: Also, note that $\mathbb{V}ar[X]=\mathbb{E}[X^{2}]-[\mathbb{E}{X}]^{2}$.


问:
The difference between a function and its linear approximations
Suppose that we have a nonlinear $f(x)$ which may be convex/nonconvex. We want to linearize this function in $N$ points over an arbitrary interval $[a,b]$ in such a way that the resultant $N$ linear approximations gives the least deviation from the original function $f(x)$. Then we can say this set of lines provides the best approximation of $f(x)$ over $[a,b]$.
Is this a standard problem which has been already investigated? If no, what is the cheapest way to model this problem?

答:
If you place the points on the curve, and make a polyline by connecting these points, then you are doing approximation by a spline of degree 1. Spline approximations (of all degrees) are well understood. See for example deBoor’s book “A Practical Guide to Splines”. The error depends on the maximum value of the second derivative of the original function.

More generally, approximation by polylines has been studied extensively, and you’ll find lots of references by googling that term. However, I don’t recall ever seeing the tangent line technique that you suggested.


问:
Is there any practical use for a piecewise written in only one function?
I spent around an hour and figured out how to form a piecewise from one function, and it's annoyingly complicated to write out or calculate, and would be much easier to just write the piecewise.

The function is as follows:

f(x)= g(x) + ((h(x)^i(x))-(g(x)^i(x))

where g(x) is the left side function, h(x) is the right side function, and i(x) is a binary logic gate determining when to switch from g(x) to h(x)

i(x)= (ceil(x) summation n=(a+1) (1))^(0^(ceil(x) summation n=(a+1) (1)))

g(x) , x >= a

Here's the graph on desmos since I don't know how to format: https://www.desmos.com/calculator/wgd5v2cpft

As you can see, its bulky and annoying to work with, but it takes a piecewise and makes it one function. I don't think there'd be any practical use for this, but there might be, and it'd be cool to know. I do admit this post is to brag about what I did because I am quite proud I figured this out, but feel free to criticize me.

答:
Well, "never" is a long time, but as far as my experience goes I can agree with the futility: that's why the notation $$f(x)=\begin{cases}u_1(x)&\text{if condition1}\\ u_2(x)&\text{if condition2}\\\vdots\\ u_n(x)&\text{if condition_n}\end{cases}$$ exists.

In programming this is even formalized by a plethora of instructions, like the switch command of c++ and the ternary operator a?b:c, still in c++.


问:
Limit comparison test for complex series
Suppose $\sum_{k=1}^\infty z_k$ is a convergent series with complex valued terms. Suppose there is a sequence of nonzero complex numbers $w_k$ satisfying $\displaystyle\lim_{k\rightarrow \infty}(z_k/w_k)=1.$ Is it then true that $\sum_{k=1}^\infty w_k$ is also convergent?

答:
No, take
$$z_k = \frac{(-1)^k}{\sqrt{k}} \quad \text{and} \quad w_k=\frac{(-1)^k}{\sqrt{k}}+\frac{1}{k}$$


问:
How to assess the complexity of a string
Q How do I quantify complexity of a given string? Consider a sample:

```<code>AAAAAAAAA     //very easy - meta sample [COMPLEXITY = 0]
KEui£$n9&E    //say random - meta sample [COMPLEXITY = ∞]
</code>```

To my limited knowledge Kolmogorov Complexity deals with this problem, but it is non-computable. So what measures I can use to approximate the complexity of the string? Could you point me to the right direction or literature for the following problem.

Many thanks!

答:
Shannon Entropy has a well defined calculation that can be computed that will approximate Kolmogorov Complexity.

I suggest you read up on the two in depth here: http://homepages.cwi.nl/~paulv/papers/info.pdf


问:
Kernel of a morphism between coherent sheaves.
Throughout this book, http://books.google.co.kr/books/about/Algebraic_Geometry_and_Arithmetic_Curves.html?id=uaLKdA0PxS4C&redir_esc=y, kernel of a morphism between coherent sheaves on a locally Noetherian scheme is also coherent.

More precisely, let $X$ be a locally Noetherian scheme and  $u:\mathcal{F}\to\mathcal{G}$ be a morphism of coherent sheaves on $X$. Then $\textrm{Ker }u$ is also coherent.

The author says, this is trivially true. However, I cannot prove it. Moreover, I do not know whether it is really true or not.

Even though I do not have any explicit example, I think this would be false in following sense; when $X$ is locally Noetherian scheme and $\mathcal{F}$ is a coherent sheaf on $X$, it is known that $\mathcal{F}(U)$ is finitely generated $\mathcal{O}_X(U)$-module for any affine open subset $U$ of $X$. If $\textrm{Ker }u$ is coherent, then the sequence $\textrm{Ker }u(U)\to\mathcal{F}(U)\to\mathcal{G}(U)$ of $\mathcal{O}_X(U)$-modules is an exact for any affine open $U$. However, in general, a submodule of a finitely generated module is not finitely generated. So, maybe there would be an example that arises form the sequence $\textrm{ker} f \to L\xrightarrow{f}M$ where $L,M$ are finitely generated modules and $\textrm{ker }f$ cannot be generated by any finite set. Is this reasonable?

Actually, we can find the same statement for $X$ is Noetherian case in Hartshorne's book. If the above statement is true, how can we expand the case?

答:
Since $X$ is locally noetherian, and since submodules of f.g. modules over a noetherian ring are finitely generated, we can see that this is locally true: that is for any affine open spec$R$, there is a cover $U_i=D(f_i)$ of Spec$R$, $f_i\in R$ generating the unit ideal, such that ker$(f)(U_i)$ is finitely generated.

Thus, all we have to prove is the following gluing result: Let $f_1,...,f_k$ generate the ideal $(1)$ in a ring $R$. Let $M$ be a module on $R$. We want to show that if $M_{f_i}$ are all finitely generated $R_{f_i}$-modules, then $M$ is a finitely generated $R$-module. Indeed, let $\frac{m_{ij}}{1}$ generate $M_{f_i}$, where $m_{ij}\in M$.

Let $m\in M$. By our assumption, we can fix a number $N$ and elements $r_{ij}\in R$ such that

$f_i^Nm=\sum_j f_i^Nr_{ij}m_{ij}$ for all $i$.

But now we use the fact that $(f_1,...,f_r)=1$, so we may write $1=\sum_{i=1}^k s_if_i$, $s_i\in R$. Taking this equation to the $kN$th power, we see that, in fact $(f_1^N,...,f_r^N)=(1)$ as well.

Thus we may write $1$ as a linear combination of the $f_i^N$, so we may write $m$ as a linear combination of the elements $f_i^Nm$, which, by our earlier equation, means we can write $m$ as a linear combination of the $m_{ij}$.

So the $m_{ij}$ generate $M$ and we have proven $M$ is finitely generated.


问:
How to find the least number of chips to get right each color?
The problem is as follows:

Claire has as porcelain jar (it is not transparent) with 141 plastic
chips inside. They have the same weight and size. But they have
different colors, some are red, others green and others black. If she
knows that the number of green chips is to the number of black chips
as 5 is to 3 and the number of red tokens is to the number of green as
3 is to 4. How many chips, at least, does she has to take out from the
jar at random to have with certainty among them 11 chips of each
color?

The alternatives given in my book are as follows:

$\begin{array}{ll}
1.&\textrm{136}\\
2.&\textrm{116}\\
3.&\textrm{120}\\
4.&\textrm{166}\\
\end{array}$

I'm not sure exactly how should I solve this problem. Something tells me that the approach to follow is first to find the number of chips which is from each color, so with that then I can expect that to be sure the number of chips will be by considering the most unlikely case scenario.

Since it says that the green tokens it to the number of blacks as $5$ is to $3$. Then is:

$\frac{G}{B}=\frac{5}{3}$

And it also mentions that the red is to the green as $3$ is to $4$. Then this would mean:

$\frac{R}{G}=\frac{3}{4}$

Then we know that:

$R+G+B=141$

Therefore: One could tell the number of the other chips by expressing one in terms of the other as given by the earlier clues.

$R+\frac{4}{3}R+\frac{4}{3}\cdot\frac{3}{5}R=141$

Solving this yields:

$R=45$

$G=15\times 4 =60$

$B=36$

Then these are the number of chips what we have in the jar.

Since it mentions to be certain to get 11 chips of the same color each this would translate as:

$45+60+10+1=116$

Answer number 2.

Thus I believe the answer would be to draw 116 tokens out of the jar at minimum. But is this interpretation the correct one?. Can someone help me here?

答:
The number of chips are correctly counted.
When you have taken up 116 chips as the answer, to verify it, you can try subtracting it from the total number of chips. 141-116= 25.

The worst thing that can happen is that the 25 remaining chips remaining in the bowl are of the same color. The chip with the lowest number is black. So the worst case is that the 25 chips remaining in the bowl are all black.

So if you subtract 25 black chips in the bowl from 36 total black chips, you get 11 black chips. Which proves that there certainly are 11 chips of each color. I hope this helps.


问:
An example for finding an explicit definition of "structure maps"
By googling, I found only What is meant by a “structure map”?. But I could not understand that for my example as follows: Let $L$ be a Lie algebra over $K$, and view $K$ as a trivial $L$-module (that is, define $x \dot a=0$ for all $x \in L$, $a \in K$). In other words, we have a trivial structure map. What does it mean when that $\rho : L \to K$ is a structure map? Does it mean that $\rho$ is just a Lie algebra homomorphism?

答:
Maps from Lie algebras to the ground field usually are forms, e.g., the trace form $\rho\colon L\times L\rightarrow K$, given by
$$
(X,Y)\mapsto \operatorname{tr}(XY),
$$
or the Killing form $\rho\colon L\times L\rightarrow K$, given by
$$
(X,Y)\mapsto \operatorname{tr}({\rm ad}(X){\rm ad}(Y)).
$$ In some translations into English I have seen the word "structure map" here, which is not quite the correct translation. A link to your source text would be helpful, of course.


问:
Evaluate the sum $\binom{2n}{n}+\binom{3n}{n}+\binom{4n}{n}+\cdots+\binom{kn}{n}$
Evaluate the sum $$\binom{2n}{n}+\binom{3n}{n}+\binom{4n}{n} + \cdots +\binom{kn}{n}$$

My Attempt:

Given sum = coefficient of $x^n$ in the expansion $$\{(1+x)^{n}+(1+x)^{2n}+(1+x)^{3n}+\cdots+(1+x)^{kn}\}-1 \\
= \text{coefficient of $x^n$ in}~~ \frac{(1+x)^n\{(1+x)^{nk}-1\}}{(1+x)^n-1}-1$$

But I am not able to go beyond this or there is some method using combinatorial argument

答:
The result I get is the following:

Applying the binomial expansion we have that $$(1+x)^{2n}=\sum\limits_{j=0}^{2n}\binom{2n}{j}x^j.$$ Since we want to keep track of the $n-$th coefficient, all we have to do is to derivate this function $n$ times, evaluate at $x=0$ and divide by $n!$: $$n!\binom{2n}{n}=\dfrac{d^{(n}}{dx}\left( (1+x)^{2n} \right)\big|_{x=0}\Longrightarrow \binom{2n}{n}=\dfrac{1}{n!}\dfrac{d^{(n}}{dx}\left( (1+x)^{2n} \right)\big|_{x=0}$$

Then, the sum we want to compute can be written as a sum of derivatives: $$\sum\limits_{j=2}^k\binom{jn}{n}=\sum\limits_{j=2}^k\dfrac{1}{n!}\dfrac{d^{(n}}{dx}\left( (1+x)^{jn} \right)\big|_{x=0}=\dfrac{1}{n!}\dfrac{d^{(n}}{dx}\left( \sum\limits_{j=2}^k(1+x)^{jn} \right){\huge|}_{x=0}.$$

This is the farthest I could reach when looking for a compact way of writing the initial sum. Anyways, the initial form looks way more compact and friendly. If you are looking for a method to approximate the result, applying the derivatives (numerically) could even be faster than computing the original sum. It may be worth trying.