答:
Expressing complexity of each part

In big O notation $O(n)$ means that the complexity is a function of $n$ with smaller terms omitted.

Suppose the time complexity for part 1 has a function $f(n_1) = an_1+[\text{smaller terms}]$ such that $\lim_{n_1 \to \infty} \frac{f(n_1)}{n_1} = a$

Likewise suppose the time complexity for part 2 has a function $f(n_2) = bn_2+[\text{smaller terms}]$ such that $\lim_{n_2 \to \infty} \frac{f(n_2)}{n_2} = b$

Expressing complexity of combined parts

The time complexity for part 1 and 2 is the sum of their complexities, i.e. $f(n_1)+f(n_2)$.

With your constraint we know that $n_2=n-n_1$

The complexity is $f(n_1)+f(n-n_1)$.

Proving the complexity of combined parts

Consider the limit $\lim_{n \to \infty} \frac{f(n_1)+f(n-n_1)}{n}$. If this is finite and non-zero then the complexity is $O(n)$.

Expand this out

$\lim_{n \to \infty} \frac{an_1+b(n-n_1)+\text{[smaller terms]}}{n}$

We know that the smaller terms vanish in the limit so this gives

$\lim_{n \to \infty} b+\frac{(a-b)n_1}{n}$

Since ${0\leq n_1 \leq n}$ then $0 \leq \lim_{n\to \infty}\frac{n_1}{n} \leq 1$

Therefore $\lim_{n \to \infty} b+\frac{(a-b)n_1}{n}$ is finite and non zero because $a\neq 0$

Title: overall complexity of additive algorithm

Body:
Assume, for some fixed integer $n$ the computational algorithm consists of two consecutive parts. Part 1 has computational complexity of $O(n_{1})$ and Part 2 has complexity of $O(n_{2})$, and $n_{1} + n_{2} = n$.

What is the overall complexity of the whole algorithm? Is it $O(n)$?


问:
Mean Value Theorem Problems
Consider the graph of the function $f(x)= x^2-x-12$.

a) Write the equation of the secant line in point slope form joining the points at $x=-2$ and $x=4$.

b) Use the Mean value theorem to determine a point c in the interval $(-2,4)$ such that the tangent line at $c$ is parallel to the secant line.

c) Find the equation of the tangent line at $c$ in point slope form.

答:
$f(x)=x^2-x-12\implies f(-2)=-6, f(4)=0$.

(a) Slope of secant joining $(-2,-6),(4,0)$ is $\displaystyle\frac{0-(-6)}{4-(-2)}=1$.Equation of this secant in slope point form is $(y-0)=1\cdot (x-4)\implies y=x-4$.

(b) Now by LMVT, $\exists \ c \in (-2,4)$ such that $f'(c)= 1\implies 2c-1=1\implies c=1$.

(c) $f(1)=1-1-12=-12,f'(1)=1$.Equation of tangent to $f$ at $x=c=1$ is $y-(-12)=1(x-1)\implies y=x-13$.

ContentLicense: CC BY-SA 4.0

Title: Mean Value Theorem Problems


问:
Modulo Ring Homomorphisms
How to I find all the possible values of $f(1)$ when $f$ is the ring homomorphism from $\mathbb{Z}/6\mathbb{Z}$ to $\mathbb{Z}/42\mathbb{Z}$?

My first thought was to see when they are equal like $1$mod6=$1$mod$42$ etc but then this doesn't give me the correct answer and I am not sure why?

答:
The thing for finding a homomorphism of the underlying additive groups is that
$$f(1)+f(1)+f(1)+f(1)+f(1)+f(1)=f(0)=0\, $$
So, $7\,|\,f(1)$ must hold.

To preserve multiplication as well, $f(1)$ must also be an idempotent: $f(1)^2=f(1)$, which further decreases the number possibilities.

If we want a unital ring homomorphism (which is, by the way, the most standard meaning of 'ring homomorphism'), then it means $f(1)=1$ which is impossible in this case because of the first item above.

Title: Modulo Ring Homomorphisms


问:
Study the convergence of $ \sum_{n \ge 1} \frac{\sqrt{n}}{n \sqrt[3]{n} + 2}$
I have to study the convergence of the following series

$$\sum_{n \ge 1} \frac{\sqrt{n}}{n \sqrt[3]{n} + 2}$$

What I tried was to compare the following terms:

$$\frac{\sqrt{n}}{n \sqrt[3]{n} + 2} \le \frac{\sqrt{n}}{n \sqrt[3]{n}}  = \frac{1}{n^{5 / 6}}$$

We know that

$$\frac{1}{n^{5/6}} \rightarrow 0 \text{, as } n \rightarrow \infty$$

so using the First Comparison Test I concluded that the series

$$\sum_{n \ge 1} \frac{\sqrt{n}}{n \sqrt[3]{n} + 2}$$

is convergent. However, I think I got something wrong. The First Comparison Test tells us that if the series is convergent, then the limit of the term that makes the series is $0$, not the other way around. So I think my argument is invalid. How should I approach this?

答:
Your inequality
$$\frac{\sqrt{n}}{n \sqrt[3]{n} + 2} \le \frac{\sqrt{n}}{n \sqrt[3]{n}}  = \frac{1}{n^{5 / 6}}$$

is fine but since $\sum  \frac{1}{n^{5 / 6}}$ diverges it is inconclusive.

As an alternative we can use limit comparison test with $\sum  \frac{1}{n^{5 / 6}}$ to conclude for divergence or by direct comparison we have

$$\frac{\sqrt{n}}{n \sqrt[3]{n} + 2} \ge \frac{\sqrt{n}}{n \sqrt[3]{n}+\sqrt n}  = \frac{1}{n^{5 / 6}+1} \ge \frac{1}{n^{5 / 6}+n^{5 / 6}}=\frac12\frac{1}{n^{5 / 6}}$$


问:
$|\phi^{-1}(\phi(H))| = |\ker \phi||\phi(H)|$ ? where $H \leq G$
Suppose $G$ is a group of finite order, let $\phi: G\to G'$ be a homomorphism and $H$ be a subgroup of $G$ then is it always true that $|\phi^{-1}(\phi(H))| = |\ker \phi||\phi(H)|$ ?

I was reading group homomorphisms and its properties and here's my observation

答:
This is just the statement that fibers of $\phi$ are disjoint and have the same number of elements.

Concretely, if $h \in H$, then $\phi(x)=\phi(h)$ iff $xh^{-1} \in \ker\phi$ and so $$\phi^{-1}(\phi(h))=\{ x \in G : \phi(x) = \phi(h) \} = (\ker\phi) h$$
Apply this to $\phi^{-1}(\phi(H))= \bigcup_{h \in H} \phi^{-1}(\phi(h))$.


问:
prove $f^{-1}(B)=A$
I am given $A_1$, $A_2 \subseteq A$ and $B_1$,$B_2 \subseteq B$. and the function $f: A \rightarrow B$

I want to prove that $f^{-1}(B)=A$.

I just assume that here one is talking about surjectiveness. How do I prove it? I will take any element from $B$ and prove that it has preimage? but rigorously how?

答: If $f:A \rightarrow B$ is a function, then $f^{-1}(B)=A$ is always true, it doesn't depend on any further assumptions.</p>

ContentLicense: CC BY-SA 3.0

Title: prove $f^{-1}(B)=A$


答:
Let $H'\le {\rm im}(\phi)\le G'$ be an arbitrary subgroup.

Then apply the first isomorphism theorem for $\phi|_{\phi^{-1}(H')}:\phi^{-1}(H')\to H'$, and note that $\ker\phi\subseteq\phi^{-1}(H')$.

Title: $|\phi^{-1}(\phi(H))| = |\ker \phi||\phi(H)|$ ? where $H \leq G$

Body:
Suppose $G$ is a group of finite order, let $\phi: G\to G'$ be a homomorphism and $H$ be a subgroup of $G$ then is it always true that $|\phi^{-1}(\phi(H))| = |\ker \phi||\phi(H)|$ ?

I was reading group homomorphisms and its properties and here's my observation


问:
Analysis - Find the Limit
Let $P(x) = ax^3 + bx^2 + cx + d$, $a, b, c, d \in \mathbb{R}$, determine whether the sequence
$$
\left(
\frac{P(n)}
{P(n + 1)}
\right)
$$
it is convergent or not. If so, calculate the limit.

I managed to show that the sequence
$$\frac{an^3 + bn^2 + cn + d}{a(n+1)^3 + b(n+1)^2 + c(n+1) + d}$$
is limited $(0<x_n<1)$, but I can't prove that your limit is 1 by the definition.

答:
HINT

Divide both numerator and denominator by the highest power of $n$ i.e. $n^3$
and note that $n^3$ has the same coefficient in both the numerator and denominator

Title: Analysis - Find the Limit


答:
We can use that, for $a\neq 0$

$$\frac{an^3 + bn^2 + cn + d}{a(n+1)^3 + b(n+1)^2 + c(n+1) + d}=\frac{a + b\frac1{n} + c\frac1{n^2} + d\frac1{n^3}}{a\left(1+\frac1n\right)^3 + \frac b n\left(1+\frac1n\right)^2 + \frac c {n^2}\left(1+\frac1n\right) + \frac d{n^3}} \to 1$$

For $a=0$ we can divide by $n^2$ and so on.

The assuming $a\neq 0$ by the definition we need to show that

$$\left|\frac{an^3 + bn^2 + cn + d}{a(n+1)^3 + b(n+1)^2 + c(n+1) + d}-1\right| \le \epsilon$$

$$\left|\frac{a(3n^2+3n+1) + b(2n+1) + c }{a(n+1)^3 + b(n+1)^2 + c(n+1) + d}\right| \le \epsilon$$

Title: Analysis - Find the Limit

Body:
Let $P(x) = ax^3 + bx^2 + cx + d$, $a, b, c, d \in \mathbb{R}$, determine whether the sequence
$$
\left(
\frac{P(n)}
{P(n + 1)}
\right)
$$
it is convergent or not. If so, calculate the limit.

I managed to show that the sequence
$$\frac{an^3 + bn^2 + cn + d}{a(n+1)^3 + b(n+1)^2 + c(n+1) + d}$$
is limited $(0<x_n<1)$, but I can't prove that your limit is 1 by the definition.


问:
Using an infinite number of Tietze transformations
I have a group presentation $G\cong\langle R|S\rangle$ which I am willing to reduce to $G\cong\langle S'|R'\rangle$ by making use of Tietze transformations. In my case, I am only using the following transformation :

Removing a generator :

If a relation can be formed where one of the generators is a word in the other generators then that generator may be removed. In order to do this it is necessary to replace all occurrences of the removed generator with its equivalent word.

In my case, I can reduce my presentation to having $|S'|=2$. However, to achieve this goal, I am requiring to be able to use an infinite number of such transformations. My setting is that I have $R=\{t\}\coprod\{a_n,\;n\in\mathbb{Z}\}$ and I can express $a_n$ in terms of $t$ and $a_0$ using relations in $R$. Applying a finite number of Tietze transformations, I can reduce the presentation to any set of generators of the form : $$S''=\{t,a_0\}\coprod\{a_n,\;|n|\geqslant N\}$$
with arbitrarily large $N$. My question is therefore :

Is it allowed to make use of an infinite number of Tietze transformations to transform a presentation into another ?

I am expecting this result to be true in fact, since, admitting this is working just fine, the presentation I obtain in the end is exactly the one I am expected to give. Intuition tends to tell me that there's nothing wrong with this, but usually intuition is not working very well when messing with doing something "infinitely many times"...

I couldn't find anything anywhere about the proof of this fact. I even dug deep to try my luck with Tietze's 1908 paper, which was unfortunately never translated.

答:
The definition in wikipedia is incorrect, essentially for situations like you describe. Wikipedia is really defining elementary Tietze transformations, which is fine for finite presentations but not in general.

The following definition is from Section 1.5 of the book Combinatorial group theory by Magnus, Karrass and Solitar. This is a solid textbook, and although I haven't compared it with the original 1908 paper, I see no reason to suspect it is incorrect. Theorem 1.5 of this book proves Tietze's result.

In 1908, H. Tietze showed that given a presentation
\begin{align*}
(7)&&\langle a, b, c, \ldots \mid P, Q, R\rangle
\end{align*}
for a group $G$, any other presentation for $G$ can be obtained by repeated application of the following transformations to (7):

(T1) If the words $S, T, \ldots$ are derivable from $P, Q, R, \ldots$, then add $S, T, \ldots$ to the defining relators in (7).

(T2) If some of the relators, say, $S, T, \ldots$, listed among the defining relators $P, Q, R, \ldots$ are derivable from the others, delete $S, T, \ldots$ from the defining relators in (7).

(T3) If $k, M, \ldots$ are words in $a, b, c, \ldots$, then adjoin the symbols $x, y, \ldots$ to the generating symbols in (7) and adjoin the relations $x=K, y=M, \ldots$ to the defining relators in (7).

(T4) If some of the defining relations in (7) take the form $p=V, q=W, \ldots$ where $p, q, \ldots$ are generators in (7) and $V, W, \ldots$ are words in the generators other than $p, q, \ldots$, then delete $p, q, \ldots$ from the generators, delete $p=V, q=W, \ldots$ from the defining relations, and replace $p, q, \ldots$ by $V, W, \ldots$ respectively, in the remaining defining relators in (7).

... a Tietze transformation is called elementary if it involves the insertion or deletion of one defining relator, or the insertion or deletion of one generator and the corresponding defining relation.

For example, by the above definition the group defined by
$$\langle a, b, c, \ldots\mid, a=1, b=1,c=1, \ldots\rangle$$
is seen to be trivial, as a single application of (T4) gives the empty presentation. However, if we only allow the "elementary" moves, as in Wikipedia, we never obtain the empty presentation.


问:
What's the probability for k consecutive 1s? I can use Borel-Cantelli
Let ${X_{i}}$ be an infinite sequence of independent random variables with $p = P(X_{i} = 1) = 1−P(X_{i} = −1)$. Let $A_{k}$ be the event that $(X_{2^k},X_{2^k+1},X_{2^k+2},...,X_{2^{k+1}−1})$ contains a sequence of k (or more) consecutive 1s. Prove that
$P(\limsup A_{k}) = \mathcal{1}_{[p ≥ 1/2]}.$ (the indicator function of 1)

be happy for some help... I tried to calculate $A_{k}$ in order to use the Borel-cantelli lemmas but it didn't worked out.

thank you everyone!

答:
If there are at least $k$ consecutive ones, then there are exactly $k$ ones starting from some place $j$ between $2^k$ and $2^{k+1}-k-1$. Each such sequence has probability $p^k$, so by union bound the probability of at least one such sequence is at most $(2^{k}-(k-1))p^k<(2p)^k$. So  $A_k<(2p)^k$, and if $p<1/2$ then $A_k$s  are bounded by geometric progression of ratio below 1, and hence has finite sum.

From the other end, the probability that there is a sequence of at least $k$ ones is at least as big as the probability that first $k$ are ones, or that second $k$ are ones or ... or the $\left \lfloor \frac{2^k}{k} \right \rfloor $th $k$ are ones. Each of those have probability  $p^{k}$ and they are independent, so the probability of all of them not happening is $(1-p^k)^{\left \lfloor \frac{2^k}{k} \right \rfloor }$. (We want this to be small.)

This is decreasing in $p$, so if $p\geq 1/2$ then we can take the value at $p=1/2$ as a bound. Further, the expression is monotone in the power, and the floor is at least the exponent minus 1, so the expression at most $(1-\frac{1}{2^k})^{-1}(1-\frac{1}{2^k})^\frac{2^k}{k}$.

The second term $(1-\frac{1}{2^k})^\frac{2^k}{k}$ is of the form $((1-1/x)^{x})^{1/k}$, and since $((1-1/x)^{x})<1/e$ the term is  $<e^{-1/k}$. This last is in turn $< (1-\frac{1}{2k})$ (because $e^{-x}<1-\frac{1}{2}x$ for $0<x\leq 1$ since the function  $1-\frac{1}{2}x-e^{-x}$ is concave, is zero at zero with positive derivative, and is positive at $x=1$; then take $x=1/k$).

Overall we get an upper bound of $(1-\frac{1}{2k})(1-\frac{1}{2^k})^{-1}$ which us  $<1-\frac{1}{4k}$ as soon as $2^k>4k$ i.e. for $k>4$. So the complementary probability is $>\frac{1}{4k}$. Thus we have a bound from below by divergent series, as wanted.


问:
Variance of square of the mean of Bernoulli variable

Let $X_1,\dots,X_n$ be independent Bernoulli variables, with probability of success $p_i,\ldots,p_n$ and let $Y_n =\dfrac1n\sum\limits^n_{i=1} (X_i - p_i )$. Find $\operatorname{Var}(Y_n^2)$.

What I know is that
$$E(Y_n) = 0, \quad   \operatorname{Var}(Y_n) = \frac1{n^2}\sum^n_{i=1}p_i(1-p_i)$$ and I know I can use the formula $$\operatorname{Var}(Y_n^2) = E(Y_n^4) - (E(Y_n^2))^2$$ but I have no idea how to calculate the $E(Y_n^4)$.

答: Applying the binomial theorem gives \begin{align}n^4\Bbb E[Y^4]&=\Bbb E\left[\left(\sum_{i=1}^n(X_i-p_i)\right)^4\right]\\&=\Bbb E\chi^4-4\rho\Bbb E\chi^3+6\rho^2\Bbb E\chi^2-4\rho^3\Bbb E\chi+\rho^4\end{align} where $\chi^\bullet=\left(\sum\limits_{i=1}^nX_i\right)^\bullet$ and $\rho^\bullet=\left(\sum\limits_{i=1}^np_i\right)^\bullet$. Note that since $\{X_i\}$ are independent Bernoulli random variables, we have $X_i^t=X_i$ for any positive integer $t$ so that \begin{align}\Bbb E\chi&=\rho\\\Bbb E\chi^2&=\Bbb E\left[\sum_{i=1}^nX_i^2+2\sum_{\text{cyc}}X_iX_j\right]=\rho+2\sum_{\text{cyc}}p_ip_j\\\Bbb E\chi^3&=\Bbb E\left[\sum_{i=1}^nX_i^3+3\sum_{\text{cyc}}X_i^2X_j+6\sum_{\text{cyc}}X_iX_jX_k\right]=\rho+3\sum_{\text{cyc}}p_ip_j+6\sum_{\text{cyc}}p_ip_jp_k\\\Bbb E\chi^4&=\Bbb E\left[\sum_{i=1}^nX_i^4+4\sum_{\text{cyc}}X_i^3X_j+6\sum_{\text{cyc}}X_i^2X_j^2+12\sum_{\text{cyc}}X_i^2X_jX_k+24\sum_{\text{cyc}}X_iX_jX_kX_\ell\right]\\&=\rho+10\sum_{\text{cyc}}p_ip_j+12\sum_{\text{cyc}}p_ip_jp_k+24\sum_{\text{cyc}}p_ip_jp_kp_\ell\end{align} which can be substituted back into $\Bbb E[Y^4]$.


问:
Is there an established notation for $A_1A_2\dots A_n$, a product of matrices?
I've taken a course or two in numerical analysis and often several matrices in a family- say $A_i\in \mathbb{C}^{m\times m},1\le i\le n$- need to be multiplied. I haven't encountered an established notation for this, so I often defined and used the usual notation for products with success:
$$
A_1 A_2\dots A_{n-1}A_n = \prod_{k=1}^{n}A_k
$$If instead we are multiplying in the opposite order, one could just 'flip' the product:
$$
A_n A_{n-1}\dots A_2 A_1 = \coprod_{k=1}^{n} A_k \left(=\prod_{k=1}^{n}A_{n+1-k}\right)
$$Is there a more conventional notation for this procedure?

答:
Summarizing the discussion:

In contrast to sigma/product notation, it seems $A_1\dots A_n$ or $A_n\dots A_1$ are generally seen as acceptable and clear.

Using bodil's terminology of left/right products, $\prod_{k=1}^{n} A_k$ is probably an acceptable way to write the left product $ A_n\dots A_1$, even if it doesn't save too many characters. However, if the $A_i$ have a special form, such as $A_i = B_i +\lambda_i I$, the product notation might be better.

Regarding right products, the most common option seems to be either the standard dot-dot-dot notation or $\prod_{k=1}^{n} A_{n-k+1}$. Several people also suggested swapping the limits, viz. $\prod_{k=n}^{1} A_k$. greg had another suggestion: $A_1\cdots A_n = \left(\prod _{k=1}^{n}A_k^T\right)^T$. $\coprod$ was not well-received.


问:
10 to the power of 3.5: $10^{3.5}$
So $10^3 = 10\times 10\times 10 = 1000$, this is really easy to understand.

But what about: $\,10^{3.5}\,?\,$ My logic would suggest this was

$10\times 10 \times 10\times 5 = 5000,\;$ but the calculator says it's 3162.27...

Can someone illustrate how the calculator calculates the power of when the number is with decimals?

Please keep in mind that I'm a newbie to mathematics!

答:
There was a question about irrational numbers. For example, how would
$10^{\pi}$ be calculated?

The trick is to use $ln(x)$ and $e^{x}$ which are inverse functions, that is,
$e^{ln(x)} = x$

If you then use $x = a^{n}$, you'll get

$a^{n} = e^{ln(a^{n})} = e^{n  ln(a)}$

or

$10^{\pi} =  e^{\pi ln(10)}$

Both $ln(x)$ and $e^{x}$ can be easily calculated.

Title: 10 to the power of 3.5: $10^{3.5}$


问:
Complete proof of 1+1=2
I'm searching for the proof that

Started from Peano's axioms

Using modern symbols

Detailed as possible

Could you give me a link to it?
Thanks

答:
There isn't a lot to prove here. Either you define $2$ to be $1+1$, so $2 := 1+1$, or you define it to be the successor of $1$, so $2:=S(1)=S(S(0))$, where $S\colon\mathbb N\to\mathbb N$ is the successor function. But the definition of $+\colon \mathbb N\times\mathbb N\to\mathbb N$ is a recursive one with $a+0 := a$ and $a+S(b):=S(a+b)$, so that
$$
1+1 = 1 + S(0) = S(1+0) = S(1) = 2.
$$

Title: Complete proof of 1+1=2


问:
Variance of two sets of independent bernoulli variables

Suppose $X_1, \ldots, X_n$ are independent Bernoulli variables with probability $p_1, \ldots,p_n$ and $Y_1,\ldots,Y_n$ is another set of independent Bernoulli variables with probability $q_1,\ldots,q_n$. ($X_1, \ldots, X_n$ and $Y_1,\ldots,Y_n$ are also independent)

Now, let $\bar{X} = \frac{\sum_{i = 1}^n X_i}{n}$ and $\bar{Y} = \frac{\sum_{i = 1}^{n}Y_i}{n}$

What I want to know is how to calculate $Var(\bar{X}\cdot\bar{Y})$

答:
Not sure about how much we can simplify, just try to group the terms in a systematic way:

$$ \begin{align} Var[\bar{X}\bar{Y}] &= Cov[\bar{X}\bar{Y},\bar{X}\bar{Y}] \\
&= Cov\left[\left(\frac {1} {n} \sum_{i=1}^n X_i\right)
\left(\frac {1} {n} \sum_{j=1}^n Y_j\right),
\left(\frac {1} {n} \sum_{k=1}^n X_k\right)
\left(\frac {1} {n} \sum_{l=1}^n Y_l\right)
\right] \\
&= \frac {1} {n^4} \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n
Cov[X_iY_j, X_kY_l]
\end{align}$$

For $i \neq k, j \neq l$, by the mutual independence,
$$Cov[X_iY_j, X_kY_l] = 0$$

For $i = k, j \neq l$,
$$ \begin{align}
Cov[X_iY_j, X_kY_l] &= Cov[X_iY_j, X_iY_l] \\
&= E[(X_iY_j)(X_iY_l)] - E[X_iY_j]E[X_iY_l] \\
&= E[X_i^2Y_jY_l] - E[X_i]E[Y_j]E[X_i]E[Y_l] \\
&= E[X_i]E[Y_j]E[Y_l] - p_i^2q_jq_l \\
&= p_i(1 - p_i)q_jq_l
\end{align} $$

Similarly, for $i \neq k, j = l$

$$ Cov[X_iY_j, X_kY_l] = p_ip_kq_j(1 - q_j) $$

and for $i = k, j = l$

$$ Cov[X_iY_j, X_kY_l] = p_iq_j(1 - p_iq_j) $$

So putting all these together,

$$ \begin{align} Var[\bar{X}\bar{Y}] &= \frac {1} {n^4} \Bigg[
2\sum_{i=1}^n \sum_{j=1}^{n-1} \sum_{l=j+1}^n p_i(1 - p_i)q_jq_l  \\
&~~~~~~~~~~~~~ + 2\sum_{i=1}^{n-1} \sum_{k=i+1}^n \sum_{j=1}^n p_ip_kq_j(1 - q_j) \\
&~~~~~~~~~~~~~ + \sum_{i=1}^n \sum_{j=1}^n p_iq_j(1 - p_iq_j) \Bigg]
\end{align}$$


问:
Irreducibility in Polynomial Rings
(a) How many polynomials of degree $2$ are there in $\Bbb Z_2[x]$? (Justify your answer.) Which ones are irreducible?

(b) Let $P \in\mathbb Z_2[x]$ be a polynomial of degree $4$ that is not irreducible. Show that either $P$ admits a root, or $P$ can be written as the product of two irreducible polynomials of degree $2$.

I know there are $4$ polynomials of degree $2$: $x^2$, $x^2+x$, $x^2+1$ and $x^2+x+1$. However I don't know how to justify this?

答:
A polynomial of degree 2 over $\mathbb{Z}_2[x]$ looks like this:

$ax^2+bx+c$ where $a,b,c\in\mathbb{Z}_2$.

So $a,b,c\in\{0,1\}$. Since we have degree 2 we have a=1, and the polynomial takes the form

$x^2+bx+c$. Now there are four possibilities left.

$b=0,1$ and $c=0,1$. (Which you combinate)

After that you only have to figure out which of them are irreducible.

Edit:

When a polynomial of degree 4 is not irreducible, you know that we can write

$ax^4+bx^3+cx^2+dx+e=(a_1x+b_1)(c_1x^3+d_1x^2+e_1x+f_1)$

In this case it has a root. Which one?
Also this does not mean that the polynomial of degree 3 is irreducible as well.

Or (in the case that it has no root) you can compose it as

$ax^4+bx^3+cx^2+dx+e=(a_1x^2+b_1x+c_1)(d_1x^2+e_1x+f_1)$

The polynomials are irreducible, because in this case there is no root, which means there is no linear factor.

Title: Irreducibility in Polynomial Rings


问:
Measure of matrices of nullity $1$, among singular ones.
We know that for a given measure (Lebesgue, or a probability measure) for the whole set of matrices $\mathbb{R}^{n\times n}$, the set of singular ones are of measure zero. However, let $S_n\subset\mathbb{R}^{n\times n}$ be the set of $n\times n$ singular matrices with real entries. If we define a nonzero measure for $S_n$ (a new probability measure for example), what can we say about the measure of the matrices with nullity (dimension of kernel) 1? Is it possible to conclude that the set of singular matrices with nullity 1 have measure 1? (among the singular ones)

I think that this is the case, since the set of matrices of nullity $n$, is just the zero matrix, so this set must be of measure 0. From this point, I don't think it should be different for matrices of nullity e.g. $n-1$: its hard for me to think that the measure distributes nonzero fractions of it between nullity $n-1$, $n-2$, etc... Moreover, if you generate singular random matrices (with normally distributed components, constrained to the $det(M)=0$ condition, for example), you get matrices with nullity 1 most of the times.

One final (bonus) question: Would the answer change, if we restrict to singular and symmetric matrices?

答:
Yes.

For every $(i,j) \in \lbrace 1, ..., n \rbrace^2$, consider the application $f_{ij} : \mathcal{M}_n(\mathbb{R}) \rightarrow \mathbb{R}$ where for every matrix $M \in \mathcal{M}_n(\mathbb{R})$, $f_{ij}(M)$ is the value of the determinant of the submatrix obtained by deleting the $i-$th row and the $j-$th column of $M$.

Then the set of matrices that have a nullity of dimension $\geq 2$ is exactly
$$\bigcap_{(i,j) \in \lbrace 1, ..., n \rbrace^2} f_{ij}^{-1}(0)$$

The $f_{ij}$ being polynomial, and the vanishing set of any polynomial having Lebesgue measure zero, you get that the set of matrices that have a nullity of dimension $\geq 2$ has measure zero in the set of matrices that have a nullity of dimension $1$.


答:
Well, starting from the Peano axioms define the addition as

$m+0 =m$ and $m+n'=(m+n)'$,

where $n'$ denotes the successor of $n$ according to the axioms.

Define $1=0'$, $2=1'$, and so on.

Then it follows that $1+1 = 1+0' = (1+0)' = 1' =2$. Done.

Title: Complete proof of 1+1=2

Body:
I'm searching for the proof that

Started from Peano's axioms

Using modern symbols

Detailed as possible

Could you give me a link to it?
Thanks


问:
In how many ways can I distribute $100$ identical balls into $6$ different boxes?
In how many ways can I distribute $100$ identical balls into $6$ different boxes so that no box is left empty and every box contains even number of elements?

Firstly, I placed $2$ balls in every box, which covers the condition that no box is left empty and since they all have to contain even number of elements I chose $2$ balls. Now there are $88$ balls left which I have to distribute. I just don't know how to cover the condition that every box should have even number of elements? Can I for example, look at two balls as "one" ball, and distribute the "$44$" balls into $6$ boxes? Then I could use Stirling number of the second kind...

答:
Are you familiar with stars and bars method?

So we have to find the number of 6-tuples $(x_1,...x_6)$ such that each $x_i$ is even number grater than $0$ and their sum is 100. So we can write each $x_i=2y_i$ and we have $$y_1+y_2+...+y_6 = 50$$

If we write $z_i= y_i-1$ we have $$z_1+z_2+...+z_6 = 44$$ and that we can write on $${44+5\choose 5}$$ ways.


问:
Proving $\sqrt[n]{n} < 2-\frac{1}{n}$ inductively

I have already done the first part of the problem. For the second part they give me the following hint: Use (1) with $a =\frac{n-1}{n}$, then take $n$th roots.

I'm actually quite confused. Rewriting the expression I have that $2-\frac{1}{n}=1+\frac{n-1}{n}=1+a$. Thus $\sqrt[n]{n} < 2-\frac{1}{n} = \sqrt[n]{n} < 1+a$, so $n<(1+a)^n$. From now on I don't know how to continue with the exercise. I have made several attempts starting from the last expression but it is not clear to me

Body:
Using I) you get

$$\left(1+\frac{n-1}{n}\right)^n>1+n\frac{n-1}{n}\to \left(\frac{2n-1}{n}\right)^n>n$$
$$\frac{2n-1}{n}>n^{1/n}\to 2-\frac1n>n^{1/n}$$


答:
Your very close. Note that

$$(1+a)^n>1+na=1+n\frac{n-1}{n}=1+n-1=n$$

Can you finish it from here?

Title: Proving $\sqrt[n]{n} < 2-\frac{1}{n}$ inductively

Body:
I have already done the first part of the problem. For the second part they give me the following hint: Use (1) with $a =\frac{n-1}{n}$, then take $n$th roots.

I'm actually quite confused. Rewriting the expression I have that $2-\frac{1}{n}=1+\frac{n-1}{n}=1+a$. Thus $\sqrt[n]{n} < 2-\frac{1}{n} = \sqrt[n]{n} < 1+a$, so $n<(1+a)^n$. From now on I don't know how to continue with the exercise. I have made several attempts starting from the last expression but it is not clear to me


Body:
If $a=\frac{n-1}{n} > 0$ (since $n \ge 2$) using $1$ we have
$$
(1+\frac{n-1}{n})^n > 1+ n \frac{n-1}{n}
$$
thus
$$
(1+\frac{n-1}{n})> \sqrt[n]{n}
$$
so
$$
(2-\frac{1}{n})> \sqrt[n]{n}.
$$


问:
Should every group be a monoid, or should no group be a monoid?
Question: What is more convenient/useful? Writing mathematics as if every group is a monoid, or as if these two classes are disjoint?

Additional discussion. Define a monoid as follows.

Defn 1. A monoid is a triple $(X,*,e)$ such that $*$ is an associative binary operation on $X$, and $e \in X$, and $e$ has the property that for all $x \in X$ it holds that $x * e = e * x = x$.

From here, there's at least two ways of defining a group.

Defn 2. A group is a monoid $(X,*,e)$ such that for all $x \in X$ there exists $y \in X$ such that $x*y=e$.

Defn 2'. A group is a quadruple $(X,*,e,i)$ such that $(X,*,e)$ is a monoid, and $i$ is a function $X \rightarrow X$, and for all $x \in X$ it holds that $x * i(x) = e$.

Now I understand that minimalism favors Defn 2, while practitioners of universal algebra favor Defn 3. However, this is not my question.

My question is not: which is preferable, Defn 2 or Defn 2'?

Rather, my question is: which is preferable, definitions like Defn 2 such that every group is a monoid, or definitions like Defn 2' such that no group is monoid? So just to clarify, I want to know: what is more convenient/useful? Writing mathematics as if every group is a monoid, or as if these two classes are disjoint?

答:
If you define a mathematical structure, you normally also want to define the "valid" homomorphisms. If you use only universal Horn expressions to define your structure, then there is a canonical definition for homomorphisms that automatically does the right thing. It says that a homomorphism $\pi:A\mapsto B$ has to satisfy "if $R^A(x_1,\ldots,x_n)$ then $R^B(\pi(x_1),\ldots,\pi(x_n))$" for all relations $R$ over the mathematical structure that you can define by atomic expressions in the given language (like $R(x)\Leftrightarrow x=c$, $R(x,y)\Leftrightarrow f(x)=y$ or $R(x,y)\Leftrightarrow x\leq y$).

It's not always possible to use only universal Horn expressions as axioms (for example, a total order has $\forall x \forall y(x\leq y \lor y\leq x)$ as an axiom), but it's a good idea to do it for the mathematical structures where it is possible. There might be exceptions from this rule, but I just wanted to explain the basic motivation to avoid "there exists" statements (if possible) in the axioms of a mathematical structure.


问:
Ways of Dealing Playing Cards with Conditions
How many ways are there to deal the playing cards in a 52-card deck to four different players so that each player gets an equal number of cards, one player gets all the spades, and each player gets a king?

My Answer: C(4, 1) * 3! * P(36; 12,12,12)
My Reasoning: C(4, 1) ways of dealing the 13 spades, 3! ways of distributing the kings among the remaining three people, P(36;12,12,12) ways of distributing 36 distinct objects into 3 separate boxes with 12 in each box.

Can someone check my answer, and if its wrong, explain why?

答:
The really irritating thing about these questions is it's not at all clear what is a "way" of dealing cards.  You seem to be assuming that the order in which the the player gets the spades doesn't matter, nor does it matter when another player gets a king which of his thirteen cards is the king.  But then if those don't matter does it matter what player gets the card?  And does it matter if which of the other players get which kings!  Frankly, this is way too ambiguous.  Each interpretation has a specific answer but it's not at all clear which interpretation matters.

====

Your way is correct if we assume it does matter which player is signalled for all spades but it doesn't matter what order the spades come in; the it does matter which player gets which king but not which position the king comes in, and  ....I'm not sure what $P(36:12, 12,12)$ means  but it seems like you are claiming the what the other $12$ cards and order each player gets and order does matter?  Or doesn't?

I figure order either matters for everyone or it doesn't matter for anyone.

So if it matters which player gets all spades, there are $C(4,1) ={4 \choose 1}=4$ ways for that.  But order doesn't matter. If it matters which of the other $3$ get which king there are $3!$ ways to choice which player gets which king.  Of the remaining cards, We arbitrarily pick a player one and there are $C(36,12)={36\choose 12}$ for her cards and arbitrairly pick player two and there are $C(24,12)$ and $C(12,12)$ for the third.

When you write $P(N; a,b,c,...)$ does that mean ${N\choose a}{N-a\choose b}{N-a-b \choose c}....$ which will indeed equal $\frac{N!}{a!b!c!.....}$?  So I suppose you do mean that.


答:
$$2-{1\over n}=1+{n-1\over n}\implies\left(2-{1\over n}\right)^n=\left(1+{n-1\over n}\right)^n\gt1+n\cdot{n-1\over n}=1+n-1=n$$

and

$$\left(2-{1\over n}\right)^n\gt n\implies2-{1\over n}\gt\sqrt[n]n$$


答:
First let's see $\phi^{-1}(\phi(H))$ is a subgroup. Of course $0\in\phi^{-1}(\phi(H))$. Now, if $x,y\in\phi^{-1}(\phi(H))$ then $\phi(x),\phi(y)\in\phi(H)$, which is a subgroup, so $\phi(x*y^{-1})=\phi(x)\phi(y)^{-1}\in\phi(H)$, so $x*y^{-1}\in\phi^{-1}(\phi(H))$ and it is a subgroup indeed.

Then we can consider the homomorphism $\varphi={\phi}_{\mid\phi^{-1}(\phi(H))}$ (the restriction). Then, by the first isomorphism theorem, $\phi^{-1}(\phi(H))/\ker(\varphi)\simeq\varphi(\phi^{-1}(\phi (H)))=\phi(\phi^{-1}(\phi(H)))=\phi(H)$.

Since $\ker(\varphi)$ is a normal subgroup of $\phi^{-1}(\phi(H))$ then $\left|\phi^{-1}(\phi(H))/\ker(\varphi)\right|=\left|\phi^{-1}(\phi(H))\right|/\left|\ker(\varphi)\right|$.

Now, clearly $\ker(\varphi)\subset\ker(\phi)$. But since $0\in\phi(H)$ we have that $\ker(\phi)=\phi^{-1}(0)\subset\phi^{-1}(\phi(H))$, so we can do $\varphi(\ker(\phi))=\phi(\ker(\phi))=0$ and then $\ker(\phi)\subset\ker(\varphi)$. Therefore $\ker(\phi)=\ker(\varphi)$.

We conclude $\left|\phi^{-1}(\phi(H))\right|/\left|\ker(\phi)\right|=\left|\phi^{-1}(\phi(H))/\ker(\phi)\right|=\left|\phi^{-1}(\phi(H))/\ker(\varphi)\right|=$

$=\left|\phi^{-1}(\phi(H))\right|/\left|\ker(\varphi)\right|=\left|\phi(H)\right|$.


问:
Singularity of a sum implies intersection of kernels?
$A,B \in \mathbb{R}^{n \times n}, \beta \in \mathbb{R}$.

I suspect that from

$\forall \beta>0: det(A+i\beta B)=0$

it follows that

Ker(A)$\cap$ Ker(B) $\neq \{0\}$.

Any counterexamples? Ideas for proof?

Body: Consider $A=\pmatrix{1&0\\ 0&0}$ and $B=\pmatrix{0&1\\ 0&0}$.


问:
Function Normalization
I have a question related to function normalization.

I'm dealing with a modulating function, which is a function that has some properties.

Let say that this modulating function is $\phi(t)$ and it is defined in an interval $[0, T]$. To $\phi(t)$ be a modulating function, it needs to satisfy the following properties:

$(P1) \quad \phi_{n}(t) = \begin{cases}sin^{n}\frac{(n\, \pi \, t)}{T}, \quad \text{for $t$} \in [0, T] \text{, $n \in \mathbb{N}$} \\ 0, \quad \text{otherwise}\end{cases}$

$(P2) \quad \phi_{n}^{(p)}(0) = 0 $

$(P2) \quad \phi_{n}^{(p)}(T) = 0$

$p$ in properties $P2$ and $P3$ is the derivative number. Also, the defined modulating function $\phi(t)$ is just a kind of modulating function called Shinbrot's Modulating Function. There are many other types of modulating functions.

Given the context, I would like to know how to normalize this function. When we normalize a vector we perform the following

\begin{equation}
\vec{\hat{u}} = \frac{\vec{u}}{|| \vec{u} ||}
\end{equation}

But when we work with functions, we have to compute the inner product of the function with itself? Like the following

\begin{equation}\label{a}
<\phi(t), \phi(t)> \, = \int_{0}^{T}\phi(t) \bar{\phi}(t) dt
\end{equation}

The $\bar{\phi}(t)$ indicates the conjugate of $\phi(t)$. But in this case, it is a real function, so we have

\begin{equation}
<\phi(t), \phi(t)> \, = \int_{0}^{T}\phi^2 (t) dt
\end{equation}

Then, due to the modulus operator in the denominator, we'll have the following

\begin{equation}
\hat{\phi}(t) = \frac{\phi(t)}{<\phi(t), \phi(t)>} = \frac{\phi(t)}{\sqrt{\int_{0}^{T}\phi^2 (t) dt}}
\end{equation}

So this last equation, with $\hat{\phi}(t)$ will be the normalized function? Are my assumptions correct?

Thanks in advance!

答: Given a non-zero element $v$ of a normed space $(X, \|\cdot\|)$, a normalized vector $\bar v$ is a vector in the same direction but with norm $1$. Namely $\bar v=\tfrac 1{\|v\|}v$. In particular,  if $X$ is a real Hilbert space with an inner product $\langle\cdot,\cdot\rangle$ then $\|v\|=\sqrt{\langle v,v\rangle}$. So if $X$ is a space of a continuous functions on $[0,T]$ with $\langle\phi,\psi\rangle=\int_0^T \phi(t)\psi(t)dt$ for any functions $\phi,\psi\in X$, then a normalized non-zero function $\phi$ is $$\bar{\phi}(x)=\frac 1{\sqrt{\int_0^T (\phi(t))^2 dt}}\phi(x).$$

Title: Function Normalization


问:
Understanding the regular element of a Lie algebra
Given a Lie algebra $\mathfrak{g}$, we defined
$$
\mathfrak{g}_{0,x}=\{ y\in \mathfrak{g}: \exists N>0\ ad(x)^N(y)=0\},
$$
and $x$ is said to be regular if $\mathfrak{g}_{0,x}$ is of minimal dimension. So I am kind of confused here what the minimal mean. Does it mean $\mathfrak{g}_{0,x}$ has the smallest dimension among such $\mathfrak{g}_{0,x}$ for all $x\in \mathfrak{g}$? Or does it mean $\mathfrak{g}_{0,x}$ has the smallest dimension among all subalgebras of $\mathfrak{g}$?

答: It means the first. It cannot mean the last because the smallest subalgebra of any Lie algebra is $0$, and convince yourself that for every $x\neq 0$, the dimension of $\mathfrak g_{0,x}$ is $\ge 1$ (usually much bigger).


问:
$\lim_{(x,y)\to(0,0)} \frac{x}{y}{\sqrt{x^2+y^2}}, x> 0, y > 0$
How to solve this limit, given that x >0 and y > 0.

It was suggested to me that this can be solved as:

$\lim_{r\to0} r{\cot{\theta}}$

And since x > 0 and y > 0, then $\cot{\theta}$ cannot be infinity and r is zero therefore the limit is zero, but I am not convinced since the same logic can be applied to r.

答:
Yes by polar coordinates we obtain

$$\frac{x}{y}{\sqrt{x^2+y^2}} =r\cot \theta $$

but we can't conclude since $\cot \theta$ is not bounded.

Indeed by $x=y=t\to 0^+$ we obtain

$$\frac{x}{y}{\sqrt{x^2+y^2}} = \sqrt 2 t \to 0$$

but by $x=t\to 0^+$ and $y=t^2\to 0^+$ we obtain

$$\frac{x}{y}{\sqrt{x^2+y^2}} = \frac{t}{t^2}{\sqrt{t^2+t^4}}=\sqrt{1+t^2} \to1$$


问:
'Guessing' local extrema of a polynomial given its roots
To start with let's assume that $p$ is a degree $n>1$ polynomial in $x$ and has $n$ distinct roots $\alpha_1, \ldots, \alpha_n$. Without loss of generality we can also stipulate that $0 = \alpha_1 < \cdots < \alpha_n = 1$. This guarantees there are $n-1$ local extrema, occurring at locations $x_1 \in (\alpha_1, \alpha_2)$, $x_2 \in (\alpha_2, \alpha_3)$, and so on. One might like to guess at the values of $x_i$ based on knowledge of the roots, and I'm curious about any heuristics that could do better than guessing the midpoint of each interval.

Of course, if $n$ is small, then there exists an explicit formula; e.g. when $p(x)=(x-\alpha_1)(x-\alpha_2)$ then $x_1 = (\alpha_1 + \alpha_2)/2$, the midpoint between the roots. But as early as $n=3$ things get murky; if $p(x)=(x-\alpha_1)(x-\alpha_2)(x-\alpha_3)$, then $$x_{1,2}=\frac{\alpha_1+\alpha_2+\alpha_3}{3}\pm\frac{\sqrt{(\alpha_1+\alpha_2+\alpha_3)^2-3(\alpha_1\alpha_2+\alpha_1\alpha_3+\alpha_2\alpha_3)}}{3}$$
From this we see that the two extrema are centered around the mean of the roots. For example when $\alpha_2=1/2$, they are at $1/2 \pm \sqrt{3}/6$, so they're "pushed out" toward $0$ and $1$ (as opposed to being evenly distributed at $1/4$ and $3/4$).

Based on this idea, I can imagine a heuristic that says the extremal values will be nearer some roots and further away from others, where "nearer" and "further" should be taken in a relative sense; in the simple example above they would be nearer $\alpha_1=0$ and $\alpha_3=1$, and further from $\alpha_2 = 1/2$. Once there are more roots, do the roles of the roots alternate? (a "near" root, then a "far root", then a "near" root again?).

A more concrete question to ask is: suppose I just guess that the extrema are at the midpoints between each pair of roots, call them $m_1 = (\alpha_1+\alpha_2)/2$, $m_2=(\alpha_2+\alpha_3)/2$, and so on. Call the error term $E=\frac{1}{n-1}\sum|m_i - x_i|^2$. How does $E$ depend on the roots of $p$? Is it monotonic with $n$ in some sense?

This is an idle curiosity; I'm just trying to dream up interesting Calc I problems and found something that is a little too interesting.

答:
In my opinion, it is wrong to try to look for extreme points through examination of either the polynomial $p(x)$ or any of its roots.  The polynomial is going to be continuous, and have both a first and second derivative everywhere.

Therefore, the extreme points are going to be the (n-1, not necessarily distinct) roots of $p'(x) = 0$ [i.e. $\{r_1, r_2, \cdots, r_{(n-1)}\}$].  For each root, $r_i$, the sign (positive or negative) of $p''(r_i)$ will indicate whether it is a local minimum or maximum.

Edit
In your example, under the assumption that $p(x)$ has $n$ distinct real roots, $p'(x)$ has to have $(n-1)$ distinct real roots, because $p(x)$ must change direction $(n-1)$ times.

As for whether you would expect (for example) that the $p'(x)$ root between $\alpha_k$ and $\alpha_{(k+1)}$ will in general be closer to $\alpha_k$ or $\alpha_{(k+1)}$, I consider that to be an enormously complicated (and perhaps relatively unexplored) question.  I think that you would have to somehow diagnose the interplay between the coefficients of either $p(x)$, $p'(x)$, or both.


问:
Natural description of fibers of blowup of projective space along a subspace
Let $\mathbb{P}^n$ be a projective space, and let $\mathbb{P}^k$ a linear subspace.  There are many descriptions of $Bl_{\mathbb{P}^k}\mathbb{P}^n$, but I haven't seen one that's really intrinsic, they tend to rely on choosing a subspace complementary to the chosen linear one.

So is there any natural description of the fiber of the blowup over a point in the linear subspace? Something like the set of lines through that point satisfying a property, or the like? As mentioned, I'm interested mostly in the case of a linear subspace, but is there a way that generalizes to other subvarieties?

答: When you blow up a single point $p$, the blow-up is the set of pairs $(q,\ell)$ with $q$ a point in $\mathbf P^n$ and $\ell$ a line joining $p$ and $q$ (and the map to the original space is just the projection onto the first coordinate). Can you see how to generalize this?</p>


问:
Is the difference of two recursively enumerable sets, reducible to $K$?
Is the difference of two recursively enumerable sets, reducible to $K$?

$W_x/W_y=\{z|z \in W_x  \&  z \notin W_y\}$

$K=\{x|\Phi_x(x) \downarrow\}$

$W_x= \text{dom}(\Phi_x)$

答:
Which kind of reduction are you looking for?

It is trivially Turing reducible, because if you have a $K$-oracle available you can simply decide $W_x$ and $W_y$.

It's not many-one reducible, however, because it you take $W_x$ to be everything, a many-one reduction would tell you that the complement of a r.e. language is r.e. (which is well known to be false).


问:
Integer Solutions to $x_1+x_2+\ldots+x_n$ = number
The question is how many solutions to the equation $a+b+c+d+e+f+g=20$ are there if all terms are nonnegative integers and $a+b+c=10$?

To answer this, would I just take the number of solutions to $a+b+c=10$ and multiply it by the number of solutions to $d+e+f+g=10$?

答:
This is basically correct.
To figure out the number of solutions to $a+b+c=10$ and $d+e+f+g=10$, you can use the method of 'stars and bars'.


问:
Invertibility of second derivative operator

Let $H$ be the Sobolev space of twice $L^2$-differentiable functions, and define the operator $T:H\to L^2(\mathbb R/2\pi\mathbb Z)$ by
$$
 T=-\frac{d^2}{dx^2}.
 $$

Prove that if $\lambda\in\mathbb C$ is not the square of any integer, then the map $\lambda I-T$ is invertible.

In particular, prove that if also $\lambda<0$ then $\|(\lambda I-T)^{-1}\|\leq1/|\lambda|$.

I'm not sure how to attempt this problem. I began by writing the definitions I know:

$L^2(\mathbb R/2\pi\mathbb Z)$ is the space of square integrable, $2\pi$-periodic functions

$h_2\subset\ell^2(\mathbb Z)$ is the space of sequences $(x_n)_{n\in\mathbb Z}$ such that $\sum_{n\in\mathbb Z}(1+n^2)^2|x_n|^2<\infty$.

$F:L^2(\mathbb R/2\pi\mathbb Z)\to\ell^2(\mathbb Z)$ is the Fourier map defined by

$$
Ff=\left(\langle f(x),(2\pi)^{-1/2}e^{inx}\rangle_{L^2}\right)_{n\in\mathbb Z}=\left(\frac1{\sqrt{2\pi}}\int f(x)e^{-inx}dx\right)_{n\in\mathbb Z}
$$

$H\subset L^2(\mathbb R/2\pi\mathbb Z)$ is the function space defined by $H=\{f\in L^2(\mathbb R/2\pi\mathbb Z):Ff\in h_2\}$.

Help or hints on this question? Thanks!

答:
Suppose that $g=(\lambda I-T)f$. This means that
$$g=\lambda f+f'',\ f(0)=f(2\pi),\ f'(0)=f'(2\pi).$$
Then
$$
f(x)=c_1\,e^{i\,\sqrt{\lambda}\,x}+c_2\,e^{-i\,\sqrt{\lambda}\,x}-\frac1{2\lambda}\,\int_0^{x}g(t)\,e^{i\,\sqrt{\lambda}\,(t-x)}\,dt-\frac1{2\lambda}\,\int_x^{2\pi}g(t)\,e^{-i\,\sqrt{\lambda}\,(t-x)}\,dt.
$$
The boundary conditions give two linear equations in $c_1$ and $c_2$, of the form
\begin{align}
(1-e^{2\pi i\sqrt\lambda})\,c_1+(1-e^{-2\pi i \sqrt\lambda})\,c_2&=\text{stuff}\\
i\sqrt\lambda\,(1-e^{2\pi i\sqrt\lambda})\,c_1-i\sqrt\lambda\,(1-e^{-2\pi i \sqrt\lambda})\,c_2&=\text{other stuff}\\
\end{align}
For this to have unique solution, we need the determinant to be nonzero, that is
$$
-2i\sqrt\lambda\,(1-e^{2\pi i\sqrt\lambda})(1-e^{-2\pi i \sqrt\lambda})\ne0.
$$
This expression is $0$ precisely when $\sqrt\lambda$ is an integer, that is to say when $\lambda$ is the square of an integer. When $\lambda$ is not the square of an integer, we have found that $\lambda I -t$ is invertible and that
\begin{align}
(\lambda I-T)^{-1}g&=\frac{e^{i\sqrt\lambda x}}{4\lambda(1-e^{2\pi i \sqrt\lambda})}\biggl(\int_0^{2\pi}g(t)\,(\cos\sqrt\lambda(t-2\pi)-i\sin\sqrt\lambda t)\,dt\biggr)\\[0.3cm]
&+\frac{e^{-i\sqrt\lambda x}}{4\lambda(1-e^{-2\pi i \sqrt\lambda})}\biggl(\int_0^{2\pi}g(t)\,(\cos\sqrt\lambda(t-2\pi)-i\sin\sqrt\lambda t)\,dt\biggr)\\[0.3cm]
&-\frac1{2\lambda}\,\int_0^{x}g(t)\,e^{i\,\sqrt{\lambda}\,(t-x)}\,dt-\frac1{2\lambda}\,\int_x^{2\pi}g(t)\,e^{-i\,\sqrt{\lambda}\,(t-x)}\,dt.
\end{align}
Unless I've made a mistake (as often happens), an estimate like the one you want seems obvious when $\lambda>0$. In that case,
$$
\|(\lambda I-T)^{-1}g\|^2\leq\frac1{\lambda^2}\,\int_0^{2\pi}\left|\int_0^{2\pi}|g(t)|\,dt\right|^2\,dx\leq\frac{4\pi}\lambda^2\,\|g\|^2,
$$
so
$$
\|(\lambda I-T)^{-1}\|\leq\frac{2\pi}\lambda.
$$
I used fairly crude estimates, so probably something better can be achieved.


问:
A $C^{\infty}$-manifold, which is not a $C$-analytic manifold; and a $C$-analytic manifold, which is not a $C^{\infty}$-manifold.
My Question: I am looking for two counter-examples:

A $C^{\infty}$-manifold, which is not a $C$-analytic manifold.

A $C$-analytic manifold, which is not a $C^{\infty}$-manifold.

I think a lot, but I have no idea.

Why do I ask this question?

Motivating by this question $C^n$-manifold, which is not a $C^{n+1}$-manifold, I think about two natural questions:

Is every $C^{\infty}$-manifold, is a $C$-analytic manifold?

Is every $C$-analytic manifold, is a $C^{\infty}$-manifold?

I think the answer to these two questions should be negative, because otherwise there should be some famous propositions about these very natural questions, but I didn't find anything.

答:
Analytic functions are $C^\infty$, so an analytic atlas is automatically a $C^\infty$ atlas. So analytic manifolds are always $C^\infty$. The reverse is not true, and a counterexample is easy to find: take any non-analytic $C^\infty$-diffeomorphism $\mathbb R\to\mathbb R$, and take a compatible $C^\infty$-atlas of $\mathbb R$ containing the identity map. You get a $C^\infty$-manifold which is not analytic.

This is not a famous proposition because it isn't particularly challenging to prove, and also not a very deep result.


问:
Find all integer polynomials $f(p)$ that divide $2^p–2$ for every prime $p>2$
Find all polynomials $f(p)$ with integer coefficients that divide $2^p–2$ for every prime $p>2$

From Fermat's little theorem we can find $2p, p, -2p, -p$ (and per comments, some constant polynomials). But are there others, or can we prove higher degrees won't work?

Body:
$(p-1)$ is even, let $p-1=2k$, we can write:

$2^p-2=2(2^{p-1}-1)=2(2^k-1)(2^k+1)=2(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1)$

If $k=\frac{p-1}2=2m+1$ is odd we have:

$m=\frac{p-3}2$

Then:

$2^k-1=(2-1)(2^{2m}+2^{2m-1}+2^{2m-2}+ \cdot\cdot\cdot)=(2^{p-3}+2^{p-4}+2^{p-5}\cdot \cdot \cdot)$

Also:

$2^k+1=(2+1)(2^{2m}-2^{2m-1}+2^{2m-2}-2^{2m-3} \cdot\cdot\cdot)=3(2^{p-3}-2^{p-4}+2^{p-5}-2^{p-7}\cdot \cdot \cdot)$

Hence the factors of $2^p-2$ can at most be  ±2,  ±p,3,$A=(2^{p-3}+2^{p-4}+2^{p-5}\cdot \cdot \cdot)$ and $B=(2^{p-3}-2^{p-4}+2^{p-5}-2^{p-7}\cdot \cdot \cdot)$.
Now we construct an equation it's roots are these factors:

$[x-(2^n-2)](x±2)(x±p)(x-3)(x-A)(x-B)=0$

We can rewrite this equation as:

$f(x,p)=(±2)(3)(±p)(2^n-2)\cdot A\cdot B$

RHS of this equation divides $2^p-2$, therefore polynomial $f(x, p)$, on LHS divides it.


问:
Minimizing the expectation over a set, wrt to the Gaussian measure
I have recently read a proof [1] where, at the last step, the authors use an inequality which basically amounts to a lower bound on
$\int_\mathbb{R} \mathbf{1}_A(x)|x| \phi(x)dx$, where $\phi$ is the Gaussian pdf ($\phi(x)=\frac{e^{-x^2/2}}{\sqrt{2\pi}}$) and $A$ is a Borel set subject to $\int_\mathbb{R} \mathbf{1}_A(x)\phi(x)dx = p$. The bound they use is $p^2/2$; I was wondering if this was tight (up to a constant factor), or if one could improve this to get better than a square dependence on $p$:
$$
\min_{A\in\mathcal{B}_\mathbb{R}} \int_\mathbb{R} \mathbf{1}_A(x)|x| \phi(x)dx\qquad\\
\text{s.t.} \int_\mathbb{R} \mathbf{1}_A(x)\phi(x)dx = p
$$

Does anyone know if a result of this type is known? Any help or suggestion is welcome.

Clement.

[1] Theorem 4 of Testing halfspaces In In Proc. 20th Annual Symposium on Discrete Algorithms (SODA (2009) by Kevin Matulef, Rocco A. Servedio, Ronitt Rubinfeld

答:
This is not a real proof. However it gives some ideas. First of all $x$ is linearly increasing and the density is exponentially decreasing. Due to the absolute value $|x|$ lets assume $\mathbb{R}^+$ for the moment. First we need to show for an interval $[a_1, a_2]$ if $a_1=0$ is a minimizer or not. Since $x$ is increasing and the density is decreasing at a higher rate, if there exists another interval with $a_1\neq 0$ it should either be at higher extremes or lower extremes, namely when $a_1<\epsilon$ where $\epsilon$ is a small number or when $a_1=k$ such that $[k, \infty]$ satisfies the area condition. If in both conditions $a_1=0$ is the minimizer than $a_1=0$ should be at least a part of the solution, namely when finitely or infinitely many number of intervals is assumed. According to some simulations that I did, when a "unique interval" is assumed $a_1=0$ is the minimizer. It is not even difficult to show it algebraically, i think.

Below is the comparision of the lower bound $p^2/2$ (magenda) with the bound obtained by $[-a_1, a_1]$ for $a_1\in\mathbb{R}^+$ (blue).

If the single interval assumption is general enough then, the blue curve is the minimizer function and the lower bound by $p^2/2$ is not tight.


问:
Terminology of "commuting" diagrams.
The question is just about terminology. "Commuting diagrams" generalize both associativity and commutativity laws. They don't seem specifically related to commutativity, so why do we say the diagram "commutes"?

Clarification:

Both "commutativity" and "associativity" are interchange laws. The first says path ab can be interchanged with path ba. The second says that the path (gf)h and the path g(fh) can be interchanged. It seems arbitrary that the name of only one of these interchange laws (i.e. "commutativity") was chosen to describe the general case.

答:
Actually, it is quite related to commutativity.
$\require{AMScd}$
\begin{CD}
A@>{f}>> A\\
@V{g}VV @VV{g}V\\
A @>{f}>> A
\end{CD}
Let $f,g$ be endomorphisms of some algebraic structure $A$. Then $f\circ g=g\circ f$ if and only if the diagram above commutes. So, in some cases commutativity of these operators is equivalent to commutativity of the diagram.

Anyway, this is my interpretation.

Edit: To address the comment, I will only mention that associativity is also a sort of commutativity. For instance, we could define associativity to be the commutativity of the following diagram:
\begin{CD}
A\times A\times A@>{\mu\times \operatorname{Id}}>> A\times A\\
@V{\operatorname{Id}\times \mu}VV @VV{\mu}V\\
A\times A @>{\mu}>> A
\end{CD}
where $\mu:A\times A\to A$ is given by $\mu(x,y)=x\cdot y$, and $\cdot$ is a binary operation on $A$. Then the commutativity of the diagram says that for all $x,y,z\in A$
$$x\cdot(y\cdot z)=(\mu\circ (\operatorname{Id}\times \mu))(x,y,z)=(\mu\circ (\mu\times \operatorname{Id}))(x,y,z)=(x\cdot y)\cdot z.$$
So, it is reasonably to consider associativity as a "special case" of a commutativity condition.

Title: Terminology of "commuting" diagrams.


答: The etymology of the word "commute" comes from "to interchange two things", from Latin. When we talk about, say, a group commuting, we talk about interchanging the orders of the elements ($ab = ba$). When we talk about a graph commuting, we talk about interchanging the paths we travel through the graph ($f = g \circ h$).

Title: Terminology of "commuting" diagrams.

Body:
The question is just about terminology. "Commuting diagrams" generalize both associativity and commutativity laws. They don't seem specifically related to commutativity, so why do we say the diagram "commutes"?

Clarification:

Both "commutativity" and "associativity" are interchange laws. The first says path ab can be interchanged with path ba. The second says that the path (gf)h and the path g(fh) can be interchanged. It seems arbitrary that the name of only one of these interchange laws (i.e. "commutativity") was chosen to describe the general case.


答:
If $\mathcal{M} = (M, \cdot)$ is a monoid, regarded as a category with a single object $\star$ (so the morphisms of the category are the elements of the monoid and the composition is given by the monoid operation), then two elements $a,b \in M$ commute (in the sense that $a \cdot b = b \cdot a$) if and only if the following diagram commutes:

$$
\begin{array}{ccc}
\star & \xrightarrow{a} & \star \\
{\scriptsize b} \downarrow ~ && ~ \downarrow {\scriptsize b} \\
\star & \xrightarrow[a]{} & \star
\end{array}
$$

So in this sense, commutativity for diagrams generalises the usual notion of commutativity.

Title: Terminology of "commuting" diagrams.


问:
Conceptual question about universal generalization and the domain of discourse of our "arbitrary elements"
One of the concepts that I have had some difficulty fully comprehending is the deployment of Universal Generalization in proofs. Here is what I think I understand correctly.

Let's say that I want to prove some generic, universally quantified statement like $\forall x \varphi (x)$ with respect to some domain of discourse $\mathcal D$. I know that if I prove $\varphi(y)$ with respect to $\mathcal D$, where $y$ is a variable that has "no assumptions placed on it", then I can conclude $\forall x \varphi (x)$ with respect to $\mathcal D$.

However, it appears to me that there is, implicitly, an assumption that must be placed on $y$: specifically, that $y$, although arbitrary, must exist within $\mathcal D$.

Therefore, at the outset of any proof strategy that invokes Universal Generalization, it seems like I always need to establish that my arbitrary $y$ resides within the domain of discourse.

Firstly, is this correct?

Secondly, how should one formally assert this?

The axiomatic framework that I have been recently working with is ZFC, and an easy example that I can think of that captures my above outline is the statement:

$\forall x (\emptyset \subseteq x)$ where $\varphi(x):=\emptyset \subseteq x$ ... or more formally: $\forall x \big (\forall z ( z \in \emptyset \rightarrow z \in x) \big )$

I would start this proof off by saying:

Let $x'$ be an arbitrary element in our domain of discourse.

Prove: $\forall z (z\in \emptyset \rightarrow z \in x')$.

Then I would say:

Let $z'$ be an arbitrary element in our domain of discourse.

Prove: $z' \in \emptyset \rightarrow z' \in x'$

etc etc.

My question is thus: What do I need to do to demonstrate that $x'$ and $z'$ are elements in our domain of discourse? What is the FOL justification that $x'$ and $z'$, in fact, reside within our domain of discourse?

Hopefully this question is sufficiently clear.

Cheers~

答:
If you have some flexibility, i.e. you are not committed to a particular form of FOL*, then this problem could be avoided if all domains of quantification were may explicit as is usually the case in mathematical proofs. This would also allow different domains for different quantifiers even within the same statement.

If $D$ is your domain of quantification (a set in this case), then you would write universal generalizations in the form:

(1) $~~~~~~\forall x \in D: P(x)~~~~~~$OR$~~~~~~\forall x:[x\in D \implies P(x)]$

You would write existential generalizations in the form:

(2) $~~~~~~\exists x\in D: P(x)~~~~~~$OR$~~~~~~\exists x:[x\in D \land P(x)]$

To prove a statement of the form (1), you could start with an assumption that $x\in D$. Then it wouldn't matter if $D$ was empty or not. It would matter if you wanted to infer $P(x)$ from (1). Then $D$ would have to be non-empty.

$*$ If you are committed to a form of FOL that does not make the domain explicit on every quantifier, it may help to imagine all of this going on "behind the scenes" with the same unspecified, non-empty domain on every quantifier (as is the convention).


问:
Show that $(U_{7}, \cdot) \cong (Z_6, +)$.

Show that $(U_{7}, \times)  \cong (Z_6, +)$. ($U_{7}$ is the set of units in $Z_7$, and $Z_6$ is the set of integers modulo 6)

I understand this in theory, that we want to define a function $\phi : U_{7} \rightarrow Z_{6}$ that's a homomorphism, and is one-to-one and onto. But there's a lot of things about this I feel like I don't understand or that haven't been explained to me fully.

How do you decide how to define the function?

Is it necessary to prove separately that the function is a homomorphism, and that it's one-to-one, and that it's onto?

How do you prove that a function is a homomorphism? How do you prove a function is onto?

Edit: Following HallaSurvivor's advice I figured out a function that I think should work: $\phi([x]_6)=[3^x]_7$

So now I'm left with my other questions: How do I prove this is a homomorphism and that this is onto, and is it even necessary to do so?

答: $\textbf{Hint}$ : Think of a map $f$ : $\mathbb{Z}_6$ $\rightarrow$ $U_7$ sending a $generator$ to a $generator$ of respective group. Rest is algebraic manipulation.


问:
Abelian subgroup of prime power index
I am having difficulty with the following problem.

Show that, a finite non-abelian simple group cannot have an abelian subgroup of prime power index.

What I was thinking is that I can somehow use a result by Burnside  which says that "For a finite group G having a conjugacy class of order prime power then G cannot be simple"

Kindly suggest how to proceed further.

答:
Take a non-identity element $a$ in $H$, then the centralizer of $a$ contains $H$ since $H$ is abelian.
Then the index of the centralizer of $a$ in $G$ is of prime power,
So by Burnside theorem (you stated), centralizer of $a$ is the whole group, which shows that the centre of $G$ is nontrivial. Simplicity implies $G$ has to be abelian, which is contraction to the given hypothesis.
Hence a non-abelian simple group cannot have an abelian subgroup of prime power index.

Title: Abelian subgroup of prime power index


问:
Irreducibility in Polynomial Rings
(a) How many polynomials of degree $2$ are there in $\Bbb Z_2[x]$? (Justify your answer.) Which ones are irreducible?

(b) Let $P \in\mathbb Z_2[x]$ be a polynomial of degree $4$ that is not irreducible. Show that either $P$ admits a root, or $P$ can be written as the product of two irreducible polynomials of degree $2$.

I know there are $4$ polynomials of degree $2$: $x^2$, $x^2+x$, $x^2+1$ and $x^2+x+1$. However I don't know how to justify this?

答:
The $\Bbb F_2[x]$ polynomials of degree $2$ are precisely those of the form $x^2+bx+c$. Namely, $$p_1(x)=x^2+x+1\;\;\;\;;\;\;\;\;p_2(x)=x^2+x\;\;\;\;;\;\;\;\;\;p_3(x)=x^2+1\;\;\;\;\;;\;\;\;\;\;p_4(x)=x^2$$

but $p_1(x)$ is the only one that is irreducible over $\Bbb F_2$ because it does not have a root in $\Bbb F_2$ ; i.e. $$p_1(\mathbf 1)=p_1(\mathbf 0)=\mathbf 1$$ However, $p_2(x),p_3(x),p_4(x)$ are reducible over $\Bbb F_2$ because each of these polynomials has a root in $\Bbb F_2$ ; i.e. $$p_2(\mathbf 0)=p_3(\mathbf 1)=p_4(\mathbf 0)=\mathbf 0$$
That suffices for (a). Now, assume $f(x)$ is a reducible quartic polynomial in $\Bbb F_2[x]$ with no roots in $\Bbb F_2$ and choose $g(x),h(x)\in\Bbb F_2[x]$ such that $f(x)=g(x)\cdot h(x)$ and $$\deg(g(x)),\deg(h(x))<\deg(f(x))$$ Since $f(x)$ has no $\Bbb F_2$ roots neither of $g(x),h(x)$ are linear or cubic and therefore $\deg(g(x))=\deg(h(x))=2$. Both $g(x),h(x)$ are irreducible over $\Bbb F_2$ or else $f(x)$ has a $\Bbb F_2$ root which is impossible.

Title: Irreducibility in Polynomial Rings


问:
A question regarding properties of upper and Lower riemann sums
This question was part of my analysis quiz and I couldn't solve it.

Let $f:[1/2,2] \to \mathbb{R}$ , a strictly increasing function, put $g(x)=f(x)+f(1/x) $, $x \in [1,2]$. Consider a partition $P$ of $[1,2]$ and then which of following holds:

(a) for a suitable $f$ we can have $U(P,g)=L(P,g)$

(b) For a suitable $f$ we can have $U(P,g) \neq L(P,g)$.

(c) $U(P,g) \geq L(P,g)$ for all choices of $f$.

(d) $U(p,g )<L(P,g)$ for all choices of $f $.

I have question in only (a) and (b) ie how to prove / disprove then .I need help as I was unable to do them despite trying a lot.

Thanks for help!!

答:
Let's break this down.

Firstly, you agree that, by definition, c) is true and d) is false.

Secondly, let's examine in which cases would $U(P,g)=L(P,g)$, for a given partition $P$ of $[1,2]$. Both of these quantities are the integrals of step functions $\phi_U\geq\phi_L$ that are equal iff $g$ is a step function in $[1,2]$ that coincides with the partition $P$.

The simplest example for a $g$ that satisfies the above is $g=c$, $c\in\mathbb{R}$. Then, the question becomes can we find an $f$ st $f(x)+f(\frac{1}{x})=c$ and there is a simple example of a usual function that does that.

Finally, about any $f$ you can think of confirms b).


问:
Element of that $\mathbb Q[\sqrt{2}]$ have a square root in $\mathbb Q[\sqrt{2}]$
So I am learning about Quadratic Fields and I have a question:

Consider $\mathbb Q[\sqrt{2}]$. So does every element of that $\mathbb Q[\sqrt{2}]$ have a square root in $\mathbb Q[\sqrt{2}]$. I think that this essentially means that . I don't know if this is right though. Is this true or false. If true why is it true and if falso can someone show me a counterexample.

答:
I think the question is asking that if you have $\alpha^2 = c + d\sqrt{2} $, for ANY $c$ and $d$, then $\alpha$ can be represented as $a + b\sqrt{2}$.

Here's what I came up with:

Let $\alpha = a + b\sqrt{2} \in Q[\sqrt{2}]$.
$$\alpha^2 = (a + b\sqrt{2})^2 = a^2+2ab\sqrt{2}+2b^2=(a^2+2b^2)+(2ab)\sqrt{2} $$
Let $c = a^2+2b^2$ and $d=2ab$, then $\alpha^2= c + d\sqrt{2}$.
From this we can see that in order for $\sqrt{a_1+b_1\sqrt{2}} = a_2+b_2\sqrt{2}$, then $a_1=a_2^2+2b_2^2$ and $b_1=2a_2b_2$.

One example that works is $a_2=\frac{2}{3}$ and $b_2=\frac{4}{7}$, then $a_1 = \frac{484}{441}$ and $b_1 = \frac{16}{21}$. Indeed, if we plug in $\sqrt{\frac{484}{441}+\frac{16}{21}\sqrt{2}}$, we get $\frac{2}{3}+\frac{4}{7}\sqrt{2}$.

However, a counter example would be one that doesn't follow the formulas. For example, if we have $\sqrt{\frac{483}{441}+\frac{16}{21}\sqrt{2}}$ (the numerator of the "a" term was changed), it has no rational square roots of the form $a+b\sqrt{2}$

$\square$


问:
Finding necessary and sufficient conditions on $b$ and $c$ for $x^3-3b^2x+c=0$ to have three distinct real roots

The task is to find necessary and sufficient condition on $b$ and $c$ for the equation  $x^3-3b^2x+c=0$ to have three distinct real roots.

Are there any formulas (such as $x_1x_2=c/a$ and $x_1+x_2=-b/a$ for roots in $ax^2+bx+c=0$), but for equations of 3rd power?

答: Consider this problem geometrically, as a question of where the straight line $y=3b^2x-c$ meets the basic cubic curve $y=x^3$. For three distinct meeting points, first the gradient $3b^2$ of the line must be nonzero, so $b\neq0$, and the line must not be too high (large negative $c$) or too low (large positive $c$). To determine the range of $c$, we must look at the borderline cases where the line touches the curve. this will be when the gradient of the curve, given by $3x^2-3b^2$, matches the gradient of the line: $3x^2-3b^2=3b^2$, namely at $x=\pm b\surd2$. At these points, the $y$ values are respectively $\pm2b^3\surd2$. Substitute these $(x,y)$ values into the equation of the line to get $\pm2b^3\surd2=\pm3b^3\surd2-c.$ Thus $c=\pm b^3\surd2$. For three distinct real roots, therefore, $c$ must be strictly within this range: $-|b|^3\surd2<c<|b|^3\surd2,$ which may be written succinctly as $$c^2<2b^6.$$


问:
Give an open cover of $[0,1]\cap\mathbb{Q}$ that has no finite subcover
I'm stuck on this one.

We know that $[0,1]\cap\mathbb{Q}=\{\frac{a}{b}, a,b \in \mathbb{N}:\frac{a}{b}\in[0,1]\}$

Thus, they look something like $\{0,\frac{a_1}{b_1},\frac{a_2}{b_2},...,1\}$

Pick $x\in[0,1]\cap\mathbb{Q}$

Since the irrationals are dense in $\mathbb{R},$ $x \in[0,1]\cap\mathbb{Q}, \forall \epsilon >0 ,(x-\epsilon,x+\epsilon)$ contains $i$ irrationals

Therefore, $[0,1]\cap\mathbb{Q}$ does not contain all of its accumulation points

Therefore, $[0,1]\cap\mathbb{Q}$ is not closed

This is where I get stuck though because $[0,1]\cap\mathbb{Q}$ has infinitely many holes in it (since the irrationals are dense in $\mathbb{R})$

So naturally I would want to construct an open cover that has no finite subcover, but I can't find it.

答: Take an irrational number $a\in[0,1]$ and consider the set$$\left\{(\Bbb Q\cap[0,1])\setminus\left[a-\frac1n,a+\frac1n\right]\,\middle|\,n\in\Bbb N\right\}.$$It is an open cover of $\Bbb Q\cap[0,1]$ without a finite subcover: if $F$ is a finite subset of $\Bbb N$, if $N=\max F$, and if $q\in\left[a-\frac1N,a+\frac1N\right]\cap\Bbb Q\cap[0,1]$, then$$q\notin\bigcup_{n\in F}(\Bbb Q\cap[0,1])\setminus\left[a-\frac1n,a+\frac1n\right].$$


问:
Newton's method for roots of multiplicity $> 1$
I'm studying numerical analysis and I read in Wikipedia that "If the root being sought has multiplicity greater than one, the convergence rate is merely linear".

The article in Wikipedia also mentions that "if the multiplicity $m$ of the root is known, one can use the following modified algorithm that preserves the quadratic convergence rate:
$$x_{n+1} = x_n -m \bigl[f(x_n)/f'(x_n)\bigr].$$

I tried proving this and I couldn't do it (I only managed to prove that convergence rate is at least linear).
Any ideas on how can this be proven ?

答:
Suppose that $x$ is a m-multiple root.
then you can have $f(x_k)=(x_k-x)^mf^{(m)}(x)/m!+O((x_k-x)^{m+1})$, derivate it
$f'(x_k)=m(x_k-x)^{m-1}f^{(m)}(x)/m!+O((x_k-x)^m)$

$$x_{k+1}-x=x_k-f(x_k)/f'(x_k)-x$$
$$=x_k-x-(x_k-x)/m+O((x_k-x)^2)$$
you see this is linear convergence.
But if you change here $x_{k+1}=x_k-m[f(x_k)/f'(x_k)]$

then you can get this result $x_k-x-m(x_k-x)/m+O((x_k-x)^2)=O((x_k-x)^2)$


问:
Let $G$ be a set with associative binary operation and a unit.
Let $G$ be a set with associative binary operation and a unit. Assume that for every $ g \in G$ there exists $ x \in G$ with $xg = 1$. Prove that $gx = 1$ is a consequence.

That above is the question, and i think i have the answer however I need clarification on the unit part of the question.

So by saying there is a unit in the set, does this mean that the neutral element is 1, and that the statement is saying that for $ x \in G$ there exists a left inverse $x$ such that $xg = 1$. And conversely we can say that for every $x$ there exists a left inverse say $g'$ such that $g'x=1$. And then by associativity i have proved the consequence.

Is this the right way to go and the simplest?

答:
Denote $x$ by $x_g$. then for each $g$:
$$gx_g=1gx_g=x_{x_g}x_ggx_g=x_{x_g}1x_g=x_{x_g}x_g=1$$</p>


问:
Derivative of inner product of matrix vector and another vector
How do I compute:
\begin{equation}
\frac{\partial}{\partial\mathbf{x}} (A\mathbf{x})^{\top}\mathbf{y},
\end{equation}
where $A$ is a $m\times n$ matrix, $\mathbf{x}$ is $n\times 1$, and $\mathbf{y}$ is $m\times 1$.

答:
In fact,
\begin{eqnarray}
&&\left(\frac{\partial}{\partial\mathbf{x}} (A\mathbf{x})^{\top}\mathbf{y}\right)\mathbf{h}\\
&=&\lim_{t\to0}\frac{(A\mathbf{x}+t\mathbf{h})^{\top}\mathbf{y}-(A\mathbf{x})^{\top}\mathbf{y}}{t}\\
&=&(A\mathbf{h})^{\top}\mathbf{y}\\
&=&\mathbf{y}^{\top}(A\mathbf{h})\\
&=&(\mathbf{y}^{\top}A)\mathbf{h}
\end{eqnarray}
and hence
$$ \frac{\partial}{\partial\mathbf{x}} (A\mathbf{x})^{\top}\mathbf{y} =\mathbf{y}^{\top}A. $$


问:
Smallest positive integer that starts with 2016 and is divisible by 2017
I have the following quiz but I don't really know how to solve it.

Find the smallest positive integer that starts (in decimals) with 2016 and is divisible by 2017.

Why to they specify the decimals in brackets?

First thought was to divide 2016 by 2017. 2016/2017 = 0.999504.
Should the integer start with 2016? I find it confusing. Can someone help?

答:
Your first thought is actually quite spot-on.

Since $2016/2017 \approx 0.999504$, we have $$0.9995 \times 2017 < 2016 < 1\times 2017$$

Multiplying this by various powers of $10$ yields

$$9\times 2017 < 10 \times 2016 < 10 \times 2017$$
$$99\times 2017 < 100 \times 2016 < 100 \times 2017$$
$$999\times 2017 < 1000 \times 2016 < 1000 \times 2017$$

The above shows that there are no $5,6,7$-digit multiple of $2017$ starting with $2016$. Finally:

$$9995\times 2017 < 10000 \times 2016< 9996 \times 2017 = 20161932$$


问:
3 Variable Limit
I cannot seem to solve this 3-variable limit:
$$
{\lim_{(x,y,z) \to (0,0,0)}}\frac{x^2y^2z^2}{x^2+y^2+z^2}
$$
I searched this up on symbolab and it said to convert to polar coordinates. However they immediately set z equal to r which doesn't make sense to me. If there is a 3rd variable I thought I had to convert it to cylindrical coordinates, but I still can't just let z = r or can I? Any help is appreciated.

答:
The function is symmetric with respect to interchange of variables, so you can take your limit as follows:

$$\lim\limits_{q \to 0} \frac{q^6}{3 q^2} = \lim\limits_{q \to 0} \frac{q^4}{3} = 0$$

Title: 3 Variable Limit


问:
How can I calculate Slope and Y-intercept in Multiple Regression?
What is the formula for Slope and Y-intercept in Multiple Linear Regression? We can easily find Slope and Y-intercept of Linear Regression meaning the data having only one Independent Variable?

Is there any general way to calculate it?

答:
Suppose you have the following regression function: $ y_i = \beta_{0} + \beta_{1} x_{i1} + \cdots + \beta_{p} x_{ip} + \varepsilon_i$, where $\varepsilon_i$ is the random part (white noise). Here you have $p+1$ parameters. To estimate the the parameters $b_0,b_1,\ldots, b_p$ we need the following matrix and vectors.

$\mathbf{y} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix},X =  \begin{pmatrix} 1 &  x_{11} & \cdots & x_{1p} \\
 1 & x_{21} & \cdots & x_{2p} \\
 \vdots & \vdots & \ddots & \vdots \\
 1 & x_{n1} & \cdots & x_{np}
 \end{pmatrix}, \textbf β = \begin{pmatrix} \beta_0 \\ \beta_1 \\ \beta_2 \\ \vdots \\ \beta_p \end{pmatrix}, $

Suppose you have the following data

Here is $p=2$ and $n=17$. Then the corresponding vector and matrix is

$\mathbf{y} = \begin{pmatrix} 251.3 \\ 251.3 \\ \vdots \\ 349.0 \end{pmatrix},X =  \begin{pmatrix} 1 &  41.9 & 29.1 \\
 1 & 34.4 & 29.3 \\
 \vdots & \vdots & \vdots \\
 1 & 77.8 & 32.9
 \end{pmatrix}$

The estimated parameters are

$ \begin{pmatrix}  \hat \beta_0 \\  \hat \beta_1 \\  \hat \beta_2 \\ \end{pmatrix}=\hat \beta=(\mathbf{X^{'}X)^{-1}}\cdot \mathbf{X^{'}}\cdot \mathbf{y}$

Here $X^{'}$ denotes the transpose of $X$ and $(X^{'}X)^{-1}$ the inverse of $X^{'}X$

The result is $\begin{pmatrix}  \hat \beta_0 \\  \hat \beta_1 \\  \hat \beta_2 \\ \end{pmatrix}=\begin{pmatrix}  −153.5 \\  1.24 \\  12.08 \\ \end{pmatrix}$


问:
How to understand this strange looking cube root function?
I started messing around in Desmos and I decided to see what it looks like when you put a cubic function inside of a cube root, and I got a truly fascinating curve. It mostly looks like a straight line but it has this fascinating "hump" in the middle. I'm having trouble understanding why the function looks this way though. Here is a screenshot of the Desmos page:

答:
Take for simplicity

$$f(x) = (x^3+1)^{1/3}$$

it has the 'hump' in $[-1,0]$ , and this is true because in that interval $0<x^3+1 < 1$ so when you apply the cube root the value of $f(x)$ increases, while instead in $(-\infty,-1)$ and $(0,+\infty)$ it resembles $f(x) = x$ because more you move away from the interval $[-1,0]$  more the $+1$ in $x^3+1$ becomes less important indeed  $(x^3+1)^{1/3} \sim x $ when $x \to \pm \infty $ .


问:
Calculate average height
The average height of a Russian citizen is 177.2 cm. 80.9% of Russians are ethnic Russians. Is it possible to infer the average height of an ethnic Russian (who is also a Russian citizen), and if it is, what is it?

This question interests me, but I have no formal mathematics education beyond highschool, so I cannot hope to answer it. Any help is much appreciated.

答:
If there isn't any additional data given, there is no way to answer this question. We can't deduce the average height of ethnic Russians, because we don't know if the rest of the Russian citizens are higher or lower on average.

Suppose that the average height of a Russian citizen which isn't ethnic Russian is 200cm. Then we'd find that ethnic Russians aren't very high on average (171.8 cm).
On the contrary if the average height of a Russian citizen which isn't ethnic Russian is 160cm then we'd find that the ethnic Russians' average height is pretty high (181.3 cm).

Title: Calculate average height


问:
A "simple, detailed" reference for Topological groups, which is sufficient for number-theoretic reasons.
For number-theoretical purposes, I want to learn the infinite Galois theory. During this, I faced some other concepts which I am not comfortable with them, for instance, topological groups.

Why $Gl_n(\mathbb{R})$ is a topological group?

I know the group law on it, which is matrix multiplication. But do not feel comfortable with a topology on it. So I am not with the followed concepts, like continuity. I have to read some examples of topological groups with too many details on its topological aspects because I passed the topology course long ago.

Is there any source about examples of topological groups, with too many details on topological aspects?

答:
If your final goal is just studying infinite Galois theory, I believe Milne's book on Galois theory is fine(as fas as I could remember, he treats Krull topology in this book). For other purposes such as studying Lie groups or improving your knowledge in commutative algebra, these following books are highly recommended:

J.Rotman, An Introduction to Algebraic Topology: you could take a glance at some last pages of chapter $3$, The Fundamental Group, where the author defines the notions of topological groups and the so-called $H$-spaces. Roughly, $H$-spaces are topological spaces behaving like topological groups. Next, you may wish to have more insightful treatments about these objects, let turn to chapter $11$, which is also very readable, where Rotman introduces the categorical approach to group objects, $H$-groups, $H'$-groups in a general category. In this point of view, a topological group is simply a group object in $\mathbf{Top}_{*}$ or $\mathbf{hTop}_{*}$.

M.Atiyah, An Introduction to Commutative Algebra, chapter $10$. In this book, Atiyah gives a short introduction about the motivation of considering topological groups. The method of taking completion arises from purely number theoreic aspect ($p$-adic integers,...) and expressed to be extremely useful in commutative algebra.

Loring Tu, An Introduction to Manifolds, chapter $4$ about Lie groups and Lie algebras. I strongly believe Tu presents the whole book in a clearest way along with lots of explicit, detailed examples, including $\mathrm{Gl}_n(\mathbb{R})$.It is true that every mathematician should know at least a little theory of Lie groups, as they naturally occur everywhere in mathematics, even from theoretical physics. With this idea in mind, I strongly believe Tu's book is undoubtedly a good choice.

Topological groups are very well-known objects, especially when you are a algebraic inclined students, you should know them like back of you hand. For instance, consider $\mathrm{GL}_n(\mathbb{R})$, this is an example of the so-called Lie groups, which means that the group operators are all $C^{\infty}$. This is even stronger than asserting it to be just a topological group, which just requires the group operators to be continuous. A Lie group (or a topological group) has the advantage of being a infinesimal group, that is, all other elements are infinitesically close to the identity element, or all your problems with group are transfered to an open neighborhood of the identity element. Back to $\mathrm{GL}_n(\mathbb{R})$, as a set, it is just
$$\mathrm{GL}_n(\mathbb{R}) = \left \{A = [a_{ij}]\in \mathbb{R}^{n^2} \mid \mathrm{det}(A) \neq 0 \right \}$$
Since the $\mathrm{det}$ map is continuous, $\mathrm{GL}_n$ is an open set, therefore, a submanifold of $\mathbb{R}^{n^2}$. The product of two matrices $A=(a_{ij}),B = (b_{jk})$ reads
$$(AB)_{ik} = \sum_{j=1}^n a_{ij}b_{jk}$$
which is obviously $C^{\infty}$ as this is just a polynomial of entrices of $A$ and $B$. Similarly, the entrices of the inverse $A^{-1}$ can be expressed in terms of that of $A$, consequently, the inverse map is also infinitely differentiable.


问:
Prove that 17 divides 1111111111111111 (16 1's) and doesn't divide 11111111
I need to prove that $17$ divides $\underbrace{1111111111111111}_{\text{16 1's}}$ and doesn't divide $\underbrace{11111111}_{\text{8 1's}}$ by using congruence.

I know that $\underbrace{1111111111111111}_{\text{16 1's}}= \frac{10^{16}-1}{9}$ and that $10^{15}\equiv{1}\pmod {17}$. But how do I use these two facts to figure out if $17$ divides $1111111111111111$?

Body:
Let $1111111111111111 \equiv k \pmod {17}$.

Then $9999999999999999 \equiv 9k\pmod {17}$

And $10000000000000000 =10^{16} \equiv 9k + 1\pmod {17}$.

ANd but Fermat's little theorem:

$9k + 1 \equiv 10^{16} \equiv 1 \pmod{17}$

so $9k \equiv 0 \pmod 17$.

Not $2\cdot 9 = 18 \equiv 1 \pmod {19}$ so $9^{-1} \equiv 2 \pmod {17}$ and we may do:

So $2\cdot 9k \equiv 2\cdot 0 \pmod {17}$

$k \equiv 0 \pmod 7$.

So $1111111111111111 \equiv 0 \pmod {17}$ and we are done.  $17$ divides $1111111111111111$

Meanwhile if $11111111\equiv m \pmod{17}$ then

$99999999 \equiv  9m\pmod {17}$

$10^8 \equiv 9m + 1 \pmod {17}$.

And be successive squaring $10^2 \equiv 100=6*17-2\equiv -2 \pmod {17}$.  $10^4\equiv (-2)^2\equiv 4\pmod{17}$ and $10^8 \equiv 4^2 =16\equiv -1 \pmod {17}$.

SO $9m + 1 \equiv -1\pmod{17}$

$9m \equiv -2 \pmod {17}$

$m\equiv 2\cdot 9m \equiv -2\cdot 2 \equiv -4 \equiv 13 \pmod {17}$.

And we are done $17$ does not divide $11111111$ and, indeed, we will have a remainder of $13$ if we attempt to.

$11111098= 653594\times 17$ and $11111111=653594\times 17 + 13$.


答:
First, understand that the space $M_n$ of all $n \times n$ matrices has a natural topology on it:  it is the Euclidean topology of $\mathbb{R}^{n^2}$, where we just associate an $n \times n$ matrix with a tuple of $n^2$ points by writing its rows out side-by-side.  Now  we can give $\operatorname{GL}_n(\mathbb{R})$ the subspace topology inherited from this "matrix-ized" version of $\mathbb{R}^{n^2}$ that I've called $M_n$.  In particular, the topology is given by a metric.  Even better, the topology is particularly simple because $\operatorname{GL}_n(\mathbb{R})$ is an open subset in $M_n$ (it is the preimage of $\mathbb{R}-\{\mathbf{0}\}$ under the determinant map).

Next, we need to show that matrix multiplication and inversion are continuous.  For multiplication it is best to work back in $M_n$.  Multiplication of matrices defines a function $M_n \times M_n \to M_n$ as $(A,B) \mapsto AB$, and this is clearly continuous because it is polynomial in the entries of $A, B \in M_n$.  Since restrictions of continuous functions are continuous, this multiplication restricts down to a continuous operation $\operatorname{GL}_n(\mathbb{R})\times \operatorname{GL}_n(\mathbb{R}) \to \operatorname{GL}_n(\mathbb{R})$.

For inversion, it is much the same trick.  When you write down how inversion acts as a function, $A \mapsto A^{-1}$, you can realize this is given by the inverse of the determinant times the adjugate matrix of $A$.  Since the determinant is polynomial in the entries of $A$ and not zero because $A$ is invertible, you can use this to prove inductively that inversion is a continuous function $\operatorname{GL}_n(\mathbb{R}) \to \operatorname{GL}_n(\mathbb{R})$.

For a reference, although it is old, George McCarty's Topology: An Introduction with Application to Topological Groups is an excellent and fast way to learn the basics.

Title: A "simple, detailed" reference for Topological groups, which is sufficient for number-theoretic reasons.

Body:
For number-theoretical purposes, I want to learn the infinite Galois theory. During this, I faced some other concepts which I am not comfortable with them, for instance, topological groups.

Why $Gl_n(\mathbb{R})$ is a topological group?

I know the group law on it, which is matrix multiplication. But do not feel comfortable with a topology on it. So I am not with the followed concepts, like continuity. I have to read some examples of topological groups with too many details on its topological aspects because I passed the topology course long ago.

Is there any source about examples of topological groups, with too many details on topological aspects?


问:
Does every affine open of a closed subscheme come from an affine open of the ambient scheme?
Let $(\iota,\iota^{\#}):(Y,\mathcal{O}_Y)\to (X,\mathcal{O}_X)$ be a closed immersion of schemes. Is it true that for every affine open $V\subseteq Y$, there exists an affine open $U\subseteq X$ with $\iota^{-1}U=V$? Of course there exists an open set $\tilde{U}\subseteq X$ such that $V=\iota^{-1}\tilde{U}$, and then as $V$ is quasi-compact we may assume that $\tilde{U}$ is a finite union of affines. But can we always reduce it to just being affine?

答:
I don't think so. Every affine open in $\Bbb P^2_k$ is of the form $D(f)$ for some homogeneous $f\in k[x_0,x_1,x_2]$. On the other hand, an elliptic curve $Y\subset \Bbb P^2_k$ with identity $O$ and a point $P$ of infinite order, $Y\setminus\{O,P\}$ is affine but cannot be of the form $D(f)\cap Y$: if so, this would mean that $V(f)\cap Y$ is a divisor supported at $\{0,P\}$ contradicting the fact that $P$ is of infinite order.

It's much better to take an affine open of $X$ and produce an affine open of $Y$ than the other way around.


问:
Calculating the order of the multiplicative group $k^\times$
Let $k$ be a field of cardinality $64$.

1. What is the order of the multiplicative group $k^\times$ of invertible elements of $k$?
What are the possible orders of elements of $k^\times$?

2.
Let $d\geq0$ be an integer. Show that $k^\times$ contains at most $d$ elements of order $d$.

3. Hence prove that $k^\times$ is a cyclic group.

What I have tried so far:

I have determined that the order of the multiplicative group is 63. Hence the possible orders are the factors of 63.

I know that for question 3, a group of order n is cyclic iff it contains an element of order n.

答:
Hints.

$k$ is a field. How many elements does $k^\times$ have?

What equation does an element of order $d$ satisfy?

Add up the number of elements by order.


问:
Why is the Gaussian-Legendre Quadrature so effective?
I understand how it works, how its derived, etc. The proof of it has been shown to me. That is to say, I know how Legendre polynomials are derived, I know they are orthogonal, I know we sample a function at the roots of the polynomial, I know how the weights are calculated, and I see that it is basically a Riemann sum in that we are approximating the area with rectangles.

But the Riemann left sum, midpoint, right sum, simpsons rule, etc., have all been shown to me too. But they are not as impressive. What I dont understand is what makes the G-L Q so effective.  Where does it derive its stellar accuracy? And why should it be so accurate anyway?  The derivation is an interesting proof of concept that a numeric approximation can be done this way and is interesting in its own right... but to see that it is drastically so much more accurate than a Riemann sum is a completely different matter.

I dont see why the orthogonality of the Legendre polynomials is so important and how it plays such a key role in the accuracy.  I dont see why we choose the roots of the polynomials as the sampling points of a function, as opposed to any other set of points with appropriate weights derived.  Is the norm used in deriving the Legendre polynomials unique or can other norms and polynomials prove equally (or more) effective? Does the G-L Q work by approximating an arbitrary function by a polynomial? And if so, wouldnt we get more accuracy making those polynomials generic rather than by restricting them to linear combinations of Legendre?

答:
There is a key estimate which is commonly used in the analysis of quadrature rules for relatively nice functions:

$$|I(f)-Q(f)| \leq |I(f)-I(p)| + |I(p)-Q(p)| + |Q(p)-Q(f)|$$

where $I$ is the exact integral, $Q$ is the quadrature rule, $f$ is your integrand of interest, and $p$ can be any reasonable function, but for this bound to be useful it should be close to $f$ in some suitable sense. Generally we consider the case where $p$ is some polynomial.

Now on a bounded domain with an integrable weight function, Weierstrass's theorem lets you make the first term small as long as you're allowed to choose $p$ to be a polynomial with a large degree. If $Q$ is exact for polynomials of degree all the way up to the degree of $p$, then the second term is just zero. Thus many different rules behave nicely in the first two terms.

If you proceed this way, then the issue is the third term. In general, you can do this computation:

$$|Q(p)-Q(f)|=|Q(p-f)|=\left | \sum_{i=1}^n w_i (p(x_i)-f(x_i)) \right | \leq \left ( \max_i |p(x_i)-f(x_i)| \right ) \sum_{i=1}^n |w_i|.$$

Again Weierstrass's theorem lets you make that maximum as small as you want. But what about the sum? In general there is no reason to expect that sum to be bounded. But it is bounded if the weights have all the same sign, because $I(1)=Q(1)=\sum_{i=1}^n w_i$. For Gauss quadrature these weights are in fact positive, as you can show by noting that

$$0<I \left ( \prod_{j \neq i} (x-x_j)^2 \right ) = Q \left ( \prod_{j \neq i} (x-x_j)^2 \right )=w_i \prod_{j \neq i} (x_i-x_j)^2$$

which is because these polynomials all have degree $2n-2$, are everywhere nonnegative, and vanish at all but one of the nodes.

Note that from this point of view, the theory of orthogonal polynomials doesn't really come into play; the good behavior of Gauss quadrature is driven solely by its exactness behavior. Orthogonal polynomials only really come into play when you ask for the nodes.

There is a subtlety that I glossed over. What if you have some other method and instead of using Weierstrass's theorem to select $p$ so that the first term is small, you select $p$ to just interpolate $f$, so that the third term is zero? In this case the second term can again be made to be zero. But does the first term necessarily go to zero? The answer is no, which is closely related to Runge's phenomenon, which you can read more about on Wikipedia.


问:
positive Markov Matrix
For a positive Markov matrix which satisfy 1) every element is positive 2) each column sums to 1. It's easy to prove that 1 is a eigenvalue and every $ | \lambda | \leq 1  $. However, is there any way to prove that $ \lambda \neq -1  $ ?

答: Suppose $(\lambda,x)$ is a left eigenpair of $A$ for some eigenvalue $\lambda\in\mathbb C$ with unit modulus. By scaling $x$, we may assume that $x_j=\max_i|x_i|=1$. By equating the $j$-th entries on both sides of $|\lambda x^T|=|x^TA|$, we obtain $1=|\lambda x_j|=|\sum_ix_ia_{ij}|\le\sum_i|x_i|a_{ij}\le\sum_ia_{ij}=1$. Therefore $x_i=1$ for all $i$ and $\lambda=1$.

Title: positive Markov Matrix


答:
You can also solve this problem without spherical coordinates: Since $|2xy|\leq x^2+y^2$ also $|2xy|\leq x^2+y^2+z^2$, and hence also $\dfrac{|xy|}{x^2+y^2+z^2} \leq \dfrac{1}{2}$
Therefore
$$0 \leq |f(x,y,z)| \leq \dfrac{|xyz^2|}{2}$$
after which the limits becomes obviously zero.

Title: 3 Variable Limit

Body:
I cannot seem to solve this 3-variable limit:
$$
{\lim_{(x,y,z) \to (0,0,0)}}\frac{x^2y^2z^2}{x^2+y^2+z^2}
$$
I searched this up on symbolab and it said to convert to polar coordinates. However they immediately set z equal to r which doesn't make sense to me. If there is a 3rd variable I thought I had to convert it to cylindrical coordinates, but I still can't just let z = r or can I? Any help is appreciated.


答:
You can also use the definition of a limit. We claim that the limit in question is zero. Indeed, fix $\varepsilon > 0$. It suffices to show that there is $\delta > 0$ such that
$$0<|{\bf r}|<\delta\implies \left\lvert\frac{x^2y^2z^2}{x^2+y^2+z^2}-0\right\rvert<\varepsilon,\text{ where ${\bf r}=(x,y,z)$ }$$
Observe that
$$\frac{x^2y^2z^2}{x^2+y^2+z^2}\leqslant \frac{\left(x^2+y^2+z^2\right)\left(x^2+y^2+z^2\right)\left(x^2+y^2+z^2\right)}{x^2+y^2+z^2}=|{\bf r}|^4$$
Thus, we can take $\delta = \varepsilon^{1/4}$, and the claim is proved.

Title: 3 Variable Limit


问:
What is the n-th sum that has binomial coefficients?
Here's the problem : $\sum_{k=2}^{n}{(k-1)(n-k)!{n \choose k}}$

My approach is to do something with $\frac{n!}{2!}+2\frac{n!}{3!}+3\frac{n!}{4!}+...+(n-1)\frac{n!}{n!}$

Then I'll have a sum $n!(\sum_{k=2}^{n}{\frac{k-1}{k!}})$ and it works as  @player3236 showed, but I was tasked to use properties of binomial coefficients to evaluate this sum.

Such that ${n \choose k} = {n \choose k-1}$ and ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$

答:
The sum $\displaystyle\sum_{k=2}^n \frac {k-1}{k!}$ is not related to the harmonic series.

Observe that $$\frac {k-1}{k!} = \frac k{k!}-\frac 1{k!} = \frac{1}{(k-1)!} - \frac 1{k!}$$

so that sum actually telescopes to $1-\dfrac 1{n!}$.


问:
what is difference between Borel algebra and Borel σ-algebra?
I am a university student, professor gave us definitions of Borel algebra and Borel σ-algebra. In Wikipedia they are the same see here.

but professor defined Borel algebra as:
let $\Omega$ be $[a,b)$ set on real line. Borel algebra on $\Omega$ is finite intersection of such $[c1,c2), [c1,c2], (c1,c2], (c1,c2)$ intervals.(in wikipedia it is not finite it is countable, please help me which one is correct).
are in fact Borel algebra and Borel σ-algebra same? please give me real definitions.

答:
Algebras are closed under finite unions and intersections;
$\sigma$-algebras are closed under countable unions and intersections.

The other requirements are that algebras include $\Omega$ and $\emptyset$, and are closed under complementation.

Borel algebras are a particular example, i.e. with the half open intervals serving as a subbase.


问:
Suppose $E\subseteq\mathbb{R}$ is closed and $K\subseteq\mathbb{R}$ is compact. Show that every open cover of $E\cap K$ has a finite subcover
Since K is compact, any subset of K, for example, $E\cap K\subseteq K$ must also be compact. I want to illustrate this point using open covers only. (Showing that every open cover has a finite subcover)

Let $U$ be an open cover of $E\cap K$

Consider $U\cup (\mathbb{R}\backslash E)$

We can see that $U\cup (\mathbb{R}\backslash E)$ covers all of K (since E and K are complements in $\mathbb{R}$)

Now, I know what I have to do next is to use the open cover of K,  $U\cup (\mathbb{R}\backslash E)$, as well as the fact that $E\cap K$ is compact to construct an arbitrary open cover and its finite subcover.

But I'm not sure of my work. Tell me what you think.

$U$ is an open cover of $E\cap K$

Pick $n \in \mathbb{N}$

$U_n = \cup^{n}_{i=1}Ui$ is a finite subcover of $U$

Thus, every open cover of $E\cap K$ has a finite subcover

This seems too obvious to me to be true, however.

Plus it fails to use the complement that I constructed

答:
Hint:

Write $F=E\cap K$. Let $\{U_{\alpha}\}_{\alpha \in A}$ be an open cover of $F\subset K$. Then $\{U_{\alpha}\}_{\alpha \in A}$, along with $F^c$, provides an open cover of $K$. Since $K$ is compact...


问:
Does the cartesian product have a neutral element?
Let $A$ be any set. Is there a set $E$ such that $A \times E = E \times A = A$?

I thought of the empty set, but Wikipedia says otherwise. This operation changes dimension, so an isomorphism might be needed for such element to exist.

答:
For "equality", no ... if $a \in A$ then it does not have the form $(a,e)$ of an element of $A \times E$, by the Axiom of Foundation.

For "bijection", yes.  I leave that to you.


问:
Is the "ancestor" relationship impossible to define in first-order logic?
Definition: Given a binary relationship $R$, an ancestor relationship $R^*$ exists between $a$ and $b$ iff there is a chain of relationships $R$ connecting $a$ and $b$, for example, $Rax$, $Rxy$ and $Ryb$.

$R^*$ is trivial to define in logic programming (whose logical aspect is often said to be a subset of first-order logic). However, a paper I was reading claimed that $R^*$ cannot be defined in first-order logic. Is this true?

A Prolog definition of ancestor given parent:

$$
\begin{align}
ancestor(X, Y) & \leftarrow parent(X, Y)
\\
ancestor(X, Y) & \leftarrow parent(X, Z) \land ancestor(Z, Y)
\end{align}
$$

答:
Yes, this is a standard application of the compactness theorem.

Here's a rough idea. Consider a theory which says (and adopt a mild abuse of notation):

$aR^*b$,

There is no $c_1$ with $aRc_1Rb$,

There are no $c_1,c_2$ with $aRc_1Rc_2Rb$,

There are no $c_1,c_2,c_3$ with $aRc_1Rc_2Rc_3Rb$,

etc.

This is obviously finitely consistent (just consider a "chain of length $n$" for $n$ large enough), but equally obviously unsatisfiable. So by compactness some clause must not actually be first-order expressible - and the only option is the first one.

EDIT: Re: the prolog definition you describe (caution: I'm not familiar with prolog); at a quick glance "negation-as-failure" is a bit nuanced. I would start by observing that first-order logic does not allow recursive, or least-fixed-point, definitions; in particular, the transitive closure of a definable relation in a structure need not be definable in that same structure.

Wait, but isn't Godel coding all about recursive definitions? Well, sort of - but there's some subtleties there. Godel shows that in certain structures/theories we can handle certain recursive constructions in a "reasonably decent" way. That's a far cry from what's wanted here.

As I said above, at a glance "negation-as-failure" has some subtlety to it (specifically, nonmonotonicity). However I do think that the above is really the heart of the issue, and will wind up being relevant to however one tries to link prolog and first-order logic.


问:
Proving $\binom{2n}{n}<4^{n-1}$ for all positive integers $n\geq 5$
For $n=5$, we get $\binom{10}{5}<4^4$. Asumme inductively that $\binom{2n}{n}<4^{n-1}$ for all positive integers $n\geq 5$. Then I need to prove that $\binom{2(n+1)}{n+1}<4^{n}$ for all positive integers $n\geq 5$. I've been looking around a bit, and I've found that the expression $\binom{2n}{n}$ is precisely a central binomial coefficient. Thus $\sum_{k=0}^{n+1}\binom{n+1}{k}^2=\binom{2(n+1)}{n+1}$. How can I use this to finish my proof?

答:
Hint: Prove directly that
$
\dfrac{\binom{2(n+1)}{n+1}}{\binom{2n}{n}}<4
$
and conclude that
$
\binom{2(n+1)}{n+1} < 4 \binom{2n}{n}
$.


答:
Using inductive argument, you can do something simpler.

$$\binom{2n+2}{n+1}=\frac{2(2n+1)}{n+1}\binom{2n}{n}$$

Now prove that

$$\frac{2(2n+1)}{n+1}<4.$$

Once the inequality is proven, we can multiply both sides by $\binom{2n}{n}$ and get,
$$\frac{2(2n+1)}{n+1}\binom{2n}{n}<4\binom{2n}{n}\to \binom{2n+2}{n+1}<4\binom{2n}{n}$$

and using the inductive hypothesis we get,

$$\binom{2n+2}{n+1}<4\binom{2n}{n}<4\cdot4^{n-1}=4^n.$$

Title: Proving $\binom{2n}{n}<4^{n-1}$ for all positive integers $n\geq 5$

Body: For $n=5$, we get $\binom{10}{5}<4^4$. Asumme inductively that $\binom{2n}{n}<4^{n-1}$ for all positive integers $n\geq 5$. Then I need to prove that $\binom{2(n+1)}{n+1}<4^{n}$ for all positive integers $n\geq 5$. I've been looking around a bit, and I've found that the expression $\binom{2n}{n}$ is precisely a central binomial coefficient. Thus $\sum_{k=0}^{n+1}\binom{n+1}{k}^2=\binom{2(n+1)}{n+1}$. How can I use this to finish my proof?


答:
For instance consider $\Omega = \mathbb{R}$. Let $\mathcal{I}$ be the collection of all half open intervals $]a,b]$ with $a < b$. The $\sigma$-algebra generated by $\mathcal{I}$ is the smallest $\sigma$-algebra containing all sets in $\mathcal{I}$. Such a $\sigma$-algebra always exists. That one is called the Borel $\sigma$-algebra.

It contains at least all other types of intervals because

$$]a,b[ = \displaystyle\bigcup\limits_{m\geq k}\left(\left]a,b-\dfrac{1}{m}\right]\right)$$

as a countable union. Hence it also contains all sets

$$[a,b[ = \displaystyle\bigcap\limits_{m\in\mathbb{N}_0}\left(\left]a-\dfrac{1}{m},b\right[\right)$$

and also all sets

$$[a,b] = \displaystyle\bigcap\limits_{m\in\mathbb{N}_0}\left(\left[a,b+\dfrac{1}{m}\right[\right)$$

as countable intersections.

Hope this helps,

Title: what is difference between Borel algebra and Borel σ-algebra?

Body:
I am a university student, professor gave us definitions of Borel algebra and Borel σ-algebra. In Wikipedia they are the same see here.

but professor defined Borel algebra as:
let $\Omega$ be $[a,b)$ set on real line. Borel algebra on $\Omega$ is finite intersection of such $[c1,c2), [c1,c2], (c1,c2], (c1,c2)$ intervals.(in wikipedia it is not finite it is countable, please help me which one is correct).
are in fact Borel algebra and Borel σ-algebra same? please give me real definitions.