问:
Intuition on the Johnson-Lindenstauss lemma
Johnson-Lindenstrauss Lemma states:

Let $N \gg 1$. For any $0 < \varepsilon < 1$ and $m$ points in $\mathbb{R}^N$ and
$n > \frac{8 \log m}{\varepsilon^2}$ there exists a linear map $f : \mathbb{R}^N \rightarrow R^n$, such that:
$$
(1 - \varepsilon) \Vert u - v \Vert^2 \leqslant \Vert f(u) - f(v) \Vert^2 \leqslant (1 + \varepsilon) \Vert u - v \Vert^2
$$

In other words, there is low-dimensional projection of the data, that almost preserves the distances.

Do I correctly understand, that one can imagine this in a following way : whatever complicated the function from which these points intially came was, whether they lay on some complicated surface, one may choose a hyperplane such that it fits to the data with rather a good precision?

答:
I do not see whether your statement can be derived directly from the Johnson-Lindenstrauss-lemma. However in the article

S. Dasgupta, A. Gupta, An elementary proof of the Johnson-Lindenstrauss-lemma,
International Computer Science Institute, TR 99-006

it is shown, that $f$ can be chosen to be of the form $\sqrt{\frac{n}{m}}p$, where $p$ is an orthogonal projection to an $n$-dimensional subspace of $\mathbb{R}^N$.

Remark: the set of $m$ points needs not be created by any deterministic process at all, the points can be chosen randomly. Of course since the set is finite this is just a "philosophical" distinction, but thinking about applications of the lemma in data mining it might be of some relevance.


问:
finitely generated submodules are flat
Assume that all the finitely generated submodules of $M$ are flat, then why is $M$ also flat?

Thank you so much!

答: That is because $M$ is the direct limit of its finitely generated submodules, and a direct limit of flat modules  is flat.

ContentLicense: CC BY-SA 4.0

Title: finitely generated submodules are flat


问:
For which $n$ is $n\sigma(n)\equiv 2 \pmod {\phi(n)}$?
How to find all of $n \in \Bbb N$ such that: $$n\sigma(n)\equiv 2 \pmod {\phi(n)}$$

$\sigma(n)$ is summation of all distinct divisors of $n$

For $p$ prime we have: $p(p+1)=p^2+p\equiv 2 \pmod {p-1}$
but how to prove for composite number : $4,6,22$ is only solution.

答:
Note that $d \mid \phi(n)$ implies that $n\sigma(n) \equiv 2 \pmod{d}$.

If $p^2 \mid n$ for some odd prime $p$, then $p \mid \phi(n)$. Thus $0 \equiv n\sigma(n) \equiv 2 \pmod{p}$, a contradiction. Thus $p^2 \nmid n$ for any odd prime $p$.

If $8 \mid n$, then $4 \mid \phi(n)$. Thus $0 \equiv n\sigma(n) \equiv 2 \pmod{4}$, a contradiction. Thus $8 \nmid n$.

If $4 \|n$, then write $n=4m$, where $m$ is odd. If $m>1$, then $2 \mid \phi(m)$ so $4 \mid 2\phi(m)=\phi(n)$. Thus $0 \equiv n\sigma(n) \equiv 2 \pmod{4}$, a contradiction. Therefore $m=1$, so $n=4$, which is a solution.

Otherwise $n$ is squarefree.

If $pq \mid n$ for distinct odd primes $p, q$, then write $n=pqm, \gcd(m, pq)=1$. Then $\sigma(n)=\sigma(pq)\sigma(m)=(p+1)(q+1)m$, and $\phi(n)=\phi(n)=\phi(pq)\phi(m)=(p-1)(q-1)\phi(m)$. Thus $4 \mid \sigma(n), \phi(n)$, so $0 \equiv n\sigma(n) \equiv 2 \pmod{4}$, a contradiction.

Therefore we have $n=1, 2, p$ or $2p$, where $p$ is an odd prime. If $n=1, 2$, then $\phi(n)=1$, so we trivially have $n\sigma(n) \equiv 2 \pmod{1}$. If $n=p$, then $\phi(p)=p-1, \sigma(p)=p+1$, so $p\sigma(p)=p(p+1) \equiv 2 \pmod{p-1}$. Therefore $n=1, 2, p$ are solutions.

Suppose that $n=2p$. Then $\phi(n)=p-1$ and $\sigma(n)=1+2+p+2p=3(p+1)$. Then we have $2 \equiv 2p\sigma(p)=6p(p+1) \equiv 12 \pmod{p-1}$, so $(p-1) \mid 10$. Since $p$ is an odd prime, we get $p=3, 11$. This gives $n=6, 22$, which are indeed solutions.

Therefore all solutions are given by $n=1, 4, 6, 22$ and $n=p$, $p$ prime.

ContentLicense: CC BY-SA 3.0


问:
Showing $6x^3 - 3x - 18 $ is irreducible
The techniques I know right now to show a polynomial f(x) in Q[x] is irreducible are to show it is irreducible in some $F_p$ with p a prime f(x) has the same degree in $F_p$ as in Q[x], and the Eisenstein criteria.

I know that $6x^3-3x-18$ is irreducible in Q[x], but I don't see how to show it. The prime divisors of 18 are 2 and 3, both of which divide 6 so a simple Eisenstein doesn't work. And I've tried roots of the polynomial in $F_p$ for many p's, but it always seems to have roots. I'm guessing there is a simple way to solve this problem, does anyone know?

答:
If a cubic polynomial is reducible, it has a linear factor, which corresponds to a  root, which your polynomial does not have in $\mathbb Q$ by the rational root theorem.

Alternatively, you could show that your polynomial has no root in $\Bbb F_{11}$.


问:
Are units in a commutative ring divisors?
Theorem 9.3 from 'Integers, Polynomials, and Rings' by Ronald S. Irving is stated as follows:

Let K be a field and let n be a positive integer. Suppose f(x) is a polynomial in K[x] of degree n. If f(x) is not irreducible, then f(x) has a divisor of degree less than or equal to n/2.

My question is, are units in a ring of polynomials over a field considered as divisors?, and more generally, are units in a commutative ring divisors? the definitions from ProofWiki

https://proofwiki.org/wiki/Definition:Divisor_of_Polynomial

https://proofwiki.org/wiki/Definition:Divisor_(Algebra)

don't discard units as divisors. Consequently, Theorem 9.3 is trivially true since all the units are divisors of all polynomials. For example, let $f(x)\in K[x],f(x)\neq 0_{K[x]}$ & $p(x)=\frac{1}{2}$, then $\exists 2f(x)\in K[x],f(x)=p(x)\cdot 2f(x)$ where $p(x)\cdot 2f(x)=\frac{1}{2}\cdot 2f(x)=f(x)$, consequently $p(x)$ is a divisor of $f(x)$.

答:
Units are divisors, but they are uninteresting: units divide $1$, and $1$ divides everything, so units divide everything: if $uv = 1$ then $a = a \cdot 1 = u(av)$. Every number in a commutative ring is divisible by (i) all  units and (ii) all unit multiples of itself. Therefore these automatic factors, which you can never avoid, are considered trivial. When people speak about trying to factor an integer or a polynomial, they are for the most part interested in factorizations other than than those where one of the factors is a unit.

In particular, when saying a polynomial of (positive) degree $n$ in $K[x]$ for a field $K$ that is not irreducible must have a factor of degree at most $n/2$, the intended meaning here is nontrivial factor. Nonzero constant factors are automatic and therefore of no interest.  It would be more accurate to say a nonconstant polynomial in $K[x]$ that is reducible has a nonconstant factor of degree at most $n/2$.  The reader is expected to realize that is the intended meaning, I guess. Nobody fundamentally cares about trivial factorizations of the form $c((1/c)f(x))$ for $c \in K^\times$. There is no knowledge gained from such a factorization because you can do it for all polynomials.

Do you know what an integral domain is?  If so, then each nonzero element of an integral domain $R$ is exactly one of the following types:

(i) unit (a factor of $1$),

(ii) irreducible (no matter how you write it as a product of two terms, exactly one of them is a unit)

(iii) reducible (everything else: it has some factorization into two numbers that are not both units).

There is a fourth type, called a prime, which is a number that divides a product of two terms only by dividing one of them. Every prime is irreducible, and for many $R$ that don't have unique factorization there will be some irreducibles in $R$ that aren't prime.  Since primes are always irreducible, it's convenient to focus on (i), (ii), and (iii) when talking about factorization numbers as far as possible: "into irreducible parts" more or less.

Some $R$ without unique factorization have no irreducibles at all: the ring $\overline{\mathbf Z}$ of all* algebraic integers has lots of numbers that aren't units (such as integers greater than $1$) but it has no irreducible elements since if $\alpha$ is an algebraic integer that is not a unit then we can write $\alpha = \sqrt{\alpha}\sqrt{\alpha}$.  Every nonzero algebraic integer that is not a unit is reducible in $\overline{\mathbf Z}$.

When $R = K[x]$ for a field $K$, the units are the nonzero elements of $K$ and that is why nonzero constant polynomials are considered trivial for the purpose of factoring (their appearance in a factorization conveys no knowledge).  But when $R = \mathbf Z[x]$, the units are just $\pm 1$ and other nonzero integers are not units in $\mathbf Z[x]$: $2x + 4$ is irreducible in $\mathbf Q[x]$ (all linear polynomials in $K[x]$ are irreducible when $K$ is a field), but $2x+4$ is reducible in $\mathbf Z[x]$ since it is $2(x+2)$ and neither factor is a unit in $\mathbf Z[x]$.  A polynomial in $\mathbf Z[x]$ is called primitive when its coefficients collectively are relatively prime, such as $6x^2 + 10x + 15$: the coefficients are not pairwise relatively prime but they are relatively prime as a triple and this polynomial is primitive.  For primitive polynomials in $\mathbf Z[x]$, irreducibility in $\mathbf Z[x]$ and in $\mathbf Q[x]$ are equivalent conditions, but for non-primitive polynomials the situation is different, as with $2x+4$. By factoring out the gcd $a$ of the coefficients of a nonzero polynomial $f(x) \in \mathbf Z[x]$, you can write $f(x) = aF(x)$ where $a$ is a nonzero integer and $F(x)$ is primitive in $\mathbf Z[x]$.  This breaks up the task of factoring $f(x)$ into two parts: factoring $a$ into prime numbers and factoring $F(x)$ into irreducible polynomials (necessarily primitive) in $\mathbf Z[x]$, with the latter task being essentially the same as factoring $F(x)$ into irreducible factors in $\mathbf Q[x]$ (any such factorization of $F(x)$ can be rescaled in each part to be a factorization into irreducibles in $\mathbf Q[x]$ that are primitive in $\mathbf Z[x]$, all automatically irreducible in $\mathbf Z[x]$).


问:
Proof of the Unique Readability Theorem
So, I'm assuming that I have the language $L_p$ of propositional logic with the symbols $(,),\lnot,\to, A_0,A_1,\ldots$, where the last few symbols is a countable sequence of atomic formulas. I'm also told that these symbols are distinct and that no symbol is a subsequence of another symbol.

Then, I am told that atomic formula is a formula or if $\alpha$ is a formula, then $(\lnot \alpha)$ is a formula or if $\alpha$ and $\beta$ are formulas, then $(\alpha \to \beta)$ is a formula. No other sequence of symbols is a formula.

Now, I want to prove that every formula of $L_p$ satisfies exactly one of the three conditions above.

Proof Attempt:

Let $\phi$ be a formula of $L_p$. If $\phi$ is an atomic formula, then we're done. Now, suppose that $\phi$ is not an atomic formula. Suppose also that $\phi$ satisfies neither of the other two conditions for forming formulas.

Then, $\phi$ is a finite sequence of symbols that differs from $(\lnot \alpha)$ or $(\alpha \to \beta)$ in at least one symbol. But then this is impossible because, then, it cannot be a formula. Hence, it has to satisfy at least one of these.

Now, suppose that it satisfies both of these. So, there exists a formula $\alpha$ such that $\phi$ can be written as $(\lnot \alpha)$ and there exist formulas $\beta$ and $\gamma$ such that $\phi$ can be written as $(\beta \to \gamma)$. However, this is impossible because it would imply that $\lnot \alpha$ and $\beta \to \gamma$ are subsequences of each other. In particular, it would mean that $\lnot$ is a subsequence of $\to$ or vice versa. This is impossible. Hence, $\phi$ can only satisfy one of these conditions. But that just means that $\phi$ satisfies exactly one condition and this proves the desired result. $\Box$

Does the proof work? If it doesn't, then why? How can I fix it?

Also, I had a few separate questions regarding the structure of this whole argument, regardless of whether it's right or wrong. So, I noticed that while I'm doing this argument, I'm sort of making use of an underlying, internal reasoning in order to prove something in logic.

That is, the deductive reasoning I'm using to get to the conclusion seems to be very different from the what deduction would mean in logic, even though I haven't actually conceptualized the logic that I'm using in the argument. So, my question is if this is valid or not? If it is, then why am I allowed to do this? If it isn't valid, then how do I formalize the logic that I am using in the argument? Or am I getting this wrong entirely and am not looking at things in the best way possible?

答:
Your argument for uniqueness needs a bit of work. First, you really ought to explain why we’re done if $\varphi$ is an atomic formula $A_k$: if $\varphi$ could also be written as $(\neg\alpha)$ or $(\alpha\to\beta)$, then $($ would be a subsequence of $A_k$, which is not the case.

More important, your argument that $\varphi$ cannot be decomposed both as $(\neg\alpha)$ and as $(\beta\to\gamma)$ isn’t correct: $\neg\alpha$ and $\beta\to\gamma$ being the same sequence does not imply that $\neg$ is a subsequence of $\to$ or vice versa. A correct argument could go like this:

Suppose that $\varphi$ is both $(\neg\alpha)$ and $(\beta\to\gamma)$. This does not mean that ‘$\neg$ is a subsequence of $\to$ or vice versa’: it means that $\neg\alpha$ is the same string of symbols as $\beta\to\gamma$, so it means that $\neg$ is the first symbol of $\beta$, where $\beta$ is a formula. It’s easy to prove by induction that every formula that is not atomic begins with a left parenthesis, and $\beta$ is a formula, so either $\beta$ is $A_k$ for some $k$, or $\beta$ is $(\sigma$ for some string $\sigma$ of symbols in the language. And this is impossible, since $\neg$ is not a substring of any $A_k$, and neither of $($ and $\neg$ is a substring of the other.

Proving this, however, is not sufficient: you also need to show that $\varphi$ cannot be written as $(\neg\alpha)$ or as $(\beta\to\gamma)$ in two different ways. The first is easy: it’s clear that if $(\neg\alpha)=(\neg\alpha')$, then $\alpha=\alpha'$. If $\varphi$ contains at least two instances of $\to$, however, it’s conceivable that it can be written as $(\beta\to\gamma)$ and as $(\beta'\to\gamma')$, where $\beta\ne\beta'$ and $\gamma\ne\gamma'$, and in order to have unique readability, we need to rule out that possibility.

Without loss of generality we may assume that $\beta'=\beta\delta$ for some non-empty string $\delta$, so the strings $\beta\to\gamma$ and $\beta\delta\to\gamma'$ are identical. This means that $\beta$ is a formula, and $\delta$ begins with $\to$. Let $\delta$ be $\to\delta'$, so that $\beta'$ is $\beta\to\delta'$. Now $\beta'$ is a formula, and it’s clearly not atomic, so it must begin with a left parenthesis and end with the matching right parenthesis. But $\beta$ is also a formula, and we now know that it begins with a left parenthesis, so it must end with the matching right parenthesis. This is impossible: the left parenthesis at the beginning of $\beta\to\delta'$ cannot have two different matching right parentheses.1 Thus, $\phi$ cannot be written in the form $(\beta\to\gamma)$ in two different ways, and we’re done.

1 This parenthesis matching argument can be made more rigorous, but it does take a bit of work.

Title: Proof of the Unique Readability Theorem


问:
Convergence of a series defined with factorials
This is the series in question.
$$\sum_{n=1}^{\infty} a_n \quad \text{where} \quad a_n = \frac{(2n)!}{4^nn!(n+1)!}$$
Naturally, I tried the Ratio test, but it turned out $L = 1$ so the test was inconclusive. In such series, if the Ratio test doesn't work, what can I try?

答:
Hint:

By the duplication formula for Gamma function you have

$$
\left( {2\,n} \right)! = {{4^{\,n} } \over {\sqrt \pi  }}\left( {n - 1/2} \right)!n!
$$


答:
Use this theorem

Let $\{a_n\} $ and $\{b_n\}$ be two sequences with $a_n>0$ and $b_n>0 $ for all $n \geq N$ and let $c_n = b_n - b_{n+1} \frac{a_{n+1}}{a_n}$ then if there is a positive constant $r$ such that $c_n \geq r > 0$ for all $n \geq N $ then $\sum a_n$ converges

with your series (simplifying you obtain $\frac{a_{n+1}}{a_n} = \frac{2n+1}{2(n+2)} $) and $b_{n+1} = n+2$ so $$c_n = n+1-(n+2)\frac{2n+1}{2(n+2)} = \frac{1}{2}$$

therefore, we can use $r = \frac12$ to show that $\sum a_n $ converges.

Title: Convergence of a series defined with factorials

Body:
This is the series in question.
$$\sum_{n=1}^{\infty} a_n \quad \text{where} \quad a_n = \frac{(2n)!}{4^nn!(n+1)!}$$
Naturally, I tried the Ratio test, but it turned out $L = 1$ so the test was inconclusive. In such series, if the Ratio test doesn't work, what can I try?


问:
General formula for center and radius of the circle $\left|\frac b{z-c}-a\right|=r$
Let us fix $a,b,c\in\Bbb C$ and $r>0$.

The set of complex numbers
$$
A:=\left\{z\in\Bbb C\;:\;\left|\frac b{z-c}-a\right|=r\right\}
$$
is circle if $|a|\neq r$, a line otherwise.

In fact $A=f(C)$ where $C$ is the circle $\{w\in\Bbb C\;:\;|w-a|=r\}$ and $f$ is the Möbius transformations $f(z)=\frac b{z-c}$, and it's well known that circles/lines are preserved under MT.

In the case of $A$ being a circle, does there exist general formulas to express its center and radius?

答:
Note $\left|\frac b{z-c}-a\right|^2=r^2$, or

$$\left( \frac b{z-c}-a\right) \left( \frac{ \bar{b}}{\bar{z}-\bar{c}}-\bar{a}\right)  =r^2$$
Expand to get

$$|z|^2 -\left(c-\frac{\bar{a}b}{|r|^2-|a|^2}\right)\bar{z}
 - \left(\bar{c}-\frac{a\bar{b}}{|r|^2-|a|^2}\right)z
= \frac{|b|^2}{|r|^2-|a|^2} + \frac{a\bar{b}c + \bar{a}b\bar{c}}{|r|^2-|a|^2} - |c|^2$$

Then, express the equation in the standard form of a circle

$$ \bigg| z-\left(c-\frac{\bar{a}b}{|r|^2-|a|^2}\right)\bigg|^2= \frac{|b|^2r^2}{(|r|^2-|a|^2)^2}
$$

Thus, the center and the radius of the circle are respectively
$$c-\frac{\bar{a}b}{|r|^2-|a|^2},\>\>\>\>\>\>\>\frac{|b|r}{||r|^2-|a|^2|}$$


问:
Bisection Method - True error versus Approximate error
From the book "Numerical Methods for Engineers", by Steven C. Chapra, they state the true error is always less than the approximate error, and therefore, it is safe to use the Scarborough Error formula for asserting at least $n$ significant figures:

$$\epsilon_t\leq \epsilon_a \lt (0,5*10^{2-n}) \%$$

I can see that always holds for the absolute true error and the absolute approximate error, since the following also holds:

Let $X_R$ be the real root between the upper limit $x_u$ and lower limit $x_l$

Let $\Delta X$ be the distance between the limits $\Delta X = x_u-x_l$

Let $X_r^{new}$ the new calculated approximate root $(x_u+x_l)/2$

Let $X_r^{old}$ be the old approximate root. In this context, $x_l$ or $x_u$ depending on the last iteration.

Since the real root won't overflow the limits, it is clear to see that:
$$|X_r^{new}-X_r^{old}| = \frac{\Delta X}{2}$$
$$|X_R-X_r^{new}| \leq \frac{\Delta X}{2} = |X_r^{new}-X_r^{old}|$$
$$\therefore |E_t| = |X_R-X_r^{new}| \leq |E_a| = \frac{\Delta X}{2}$$

So the statement is true for the absolute error. What I haven't been able to proof (and I am having my doubts that is always true), is the same statement for the relative errors:

$$\epsilon_a = |\frac{X_r^{new}-X_r^{old}}{X_r^{new}}|\times 100\%$$
$$\epsilon_t = |\frac{X_R - X_r^{new}}{X_R}|\times 100\%$$

Even more, I've been having confusions on what happens when the real root is very close to zero and the estimated root is still far away from it. Wouldn't it make it possible for the real true relative error to be higher than the approximate relative one?

Final questions are, how can I proof that statement is true for the relative errors, and how can I be sure it is safe to use the first inequality given as a stop condition for the algorithm if the statement doesn't always hold?

Thanks in advance.

答:
You are correct that relative error may actually be much higher than expected (infinite even if the actual root is zero). Because of this, it is impossible to assert the claimed inequalities.

If the root is non-zero and bound bounds have the same sign, then an upper bound on the relative error may be found by simply dividing by the estimate closer to zero.

To compensate for both cases (small and large answers), usually a combination of absolute and relative errors are used. This prevents the algorithm from failing to terminate if the root is zero (relative error failure) or very large (absolute error failure). Commonly one uses a stopping criterion in the form of

$$|x_u-x_l|\le\epsilon_\mathrm{abs}+\epsilon_\mathrm{rel}\cdot x_r$$

where $\epsilon_\mathrm{abs}$ and $\epsilon_\mathrm{rel}$ are the desired absolute and relative errors.


问:
Prove that the zeros of an analytic function are finite and isolated
Let us assume that the zeros of $f = \{Z_1,\ldots,Z_n,a\}$ are infinite and converge towards $a$.

The book which I am reading says that any neighborhood of $a$ will contain infinite zeros. Since $f$ is continuous, $f$ must be identically zero in this neighborhood. .....(A)

Then as the neighborhood grows, it will be identically $0$ in that neighborhood too until it engulfs the whole of this region. Hence, the function becomes identically zero in the whole region.

I don't quite understand (A). I am confused over (A) with this analogy. Consider $f(z) = z-1$. This has a zero at $z=1$. Since $f$ is continuous in the $z$ plane, this means that as per (A) points in the neighborhood of $z =1$ should also have mapped value $= 0$.

I am confused; where could I be making a mistake?
Thanks

答:
The statement is wrong the way you quoted it. Take $f \,:\, \mathbb{R} \to \mathbb{R}$, $$
  f(x) = \begin{cases}
    x\sin \frac{1}{x} &\textrm{if } x > 0 \\
    -x &\textrm{if } x \leq 0 \text{.}
  \end{cases}
$$
Since $\lim_{x\to 0^+} f(x) = 0$ (and obviously also $\lim_{x\to 0^-} f(x) = 0$), that function is continuous. It has zeros at $$
  \left\{\frac{1}{n\pi} \,:\, n \in \mathbb{N}\right\} \text{,}
$$
which obviously have $0$ as a cluster point. Yet $f$ isn't identically zero on any neighbourhood of $0$.

For analytic functions, however, you also have that they are $C^\infty$. Your probably have to use that. Note that that only requiring $C^\infty$ isn't enough. Take for example $$
  f(x) = \begin{cases}
    e^{-\frac{1}{x}} \sin \frac{1}{x} &\textrm{if } x > 0 \\
    -x &\textrm{if } x \leq 0 \text{.}
  \end{cases}
$$
That $e^{-\frac{1}{x}}$ should damp things strong enough to ensure the existance of all derivatives of $f$ at zero, i.e. $f$ should be $C^\infty$, yet the theorem still doesn't hold since $f$ still isn't identically zero on a neighbourhood of zero.

So from the above it's clear the we need to use that $f$ is analytic to prove the theorem. We'll wlog assume that $a = 0$ (simply look at $f'(x)=f(x+a)$ if it isn't). Let $(x_n)$ be a sequence of zeros of $f$, with $x_n \to 0$. Since $f$ is analytic at $0$, there's a $r \geq 0$ such that for all $|x| < r$ we have $$
  f(x) = \sum_{k=0}^\infty c_k x^k \text{.}
$$
Let's further wlog assume that $|x_n| < r$ for all $n$ and that $|x_{n+1}| < |x_n|$ (Simply remove those $x_n$ which violate one of the conditions. Since the sequence converges to 0, infinitely many $x_n$ will remain). From the continuity of $f$ it follows that $f(0)=0$, i.e. that $c_0 = 0$. For $f(x_n)$ to be zero, it must hold that \begin{align}
  &\sum_{k=0}^\infty c_k x_n^k = 0
  \implies
  \underbrace{c_0}_{=0} + c_1 x_n = -x_n^2\sum_{k=2}^\infty c_k x_n^{k-2}
  \implies
  c_1 = -x_n\sum_{k=2}^\infty c_k x_n^{k-2} \\
  \implies
  &|c_1| \leq |x_n|\underbrace{\sum_{k=2}^\infty |c_k| |x_n|^{k-2}}_{:=M_n} \text{.}
\end{align}
(The last step uses that the series is absolutely convergent, which you have for series expansions of analytic functions)

Now observe that since $|x_{n+1} < x_n|$ you have $M_{n+1} \leq M_n$, and hence for arbitrary $n$ that $|c_1| \leq |x_n|M_n$. But since $x_n \to 0$, it follows that $c_1=0$.

Knowing that $c_1=0$, you can use the same method to show that, in fact $c_2=0$, and from that $c_3=$, and so on. You thus get that all the $c_n$ are zero, and hence that $f$ is identically zero on the ball with radius $r$ around $0$.


问:
Will this combination of Newton Raphson and bisection method be useful?
I want to write a program to find the roots of an equation of a single variable. Will the following steps be useful?
Iteratively use the Newton Raphson method. At any stage during an iteration:

If we find a root, then report the result and stop. Otherwise, go to step 2.

If we find two points x1 and x2 at which the function values have opposite signs, then find a root between x1 and x2 using the bisection method. Otherwise, go to step 3.

If we find two points x1 and x2 at which the gradients are of opposite signs, then find a point between x1 and x2 at which the gradient is zero. Suppose this point is x3. If f(x3) is of opposite sign compared to f(x1) and f(x2), then there is one root between x1 and x3 and another root between x2 and x3. We find both using the bisection method. If the three are of the same sign, then we report that the root was not found and stop. Otherwise, go to step 4.

If the gradient becomes constant, this means we have found an asymptote. Report that we could not find a root and stop.

In all other cases, continue with the iteration.

Will this be useful? Or, will it find some wrong root in some cases? Any suggestions for improvements?
Thank you.

答:
The outlined method will work mostly, but of course may report no root was found even when there was a root on the given interval.

A particularly notable point is what constitutes a root.

Is it enough that a root is bounded using bisection? What if bisection reports a value where $f(x)$ is not close to $0$ at all e.g. $f(x)=1/x$ giving a value $x\approx0$ with bisection.

What if step 3 finds a point where $f(x)=0$? What if it's very close to $0$? Should this also be considered a root?

It also seems you want to stop at the 4th stop. I'm not entirely sure what is meant for that case, but it may prove a better idea to continue using Newton's method.

Finally I'll also remark that for an algorithm like this, it is usually useful to double (or multiply by some amount greater than 1) the distance that Newton's method covers:

$$x_{n+1}=x_n-2\frac{f(x_n)}{f'(x_n)}$$

This allows for

Jumping over to the other side of a root so that bisection can be used to guarantee convergence.

Potentially faster initial convergence.

Potentially faster convergence for non-simple roots (such as $f(x)=x^3$).

but may also pose other issues, such as missing the root or getting stuck (such as $f(x)=|x|$).


问:
Why is $T(n)=2T\left(\frac{n}{2}\right) + n\log(n)$ time complexity is $Θ\big( n\log^2(n) \big) $?
I was doing some homework and worked out a closed form for $T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)$ and got:

$T(n)=n+n\left(\log(n)+\log\left(\frac{n}{2}\right)+\log\left(\frac{n}{4}\right)+\log\left(\frac{n}{8}\right)+\cdots+ 1\right)$

as closed form.

I was able to prove that $T(n)$ is in big O of $n\log^2(n)$ by:

$T(n) < n + n\log(n)\leq a\log^2(n)$ for some constant $a\geq 1$

But I don't know how $T(n)$ is in big omega of $n\log^2(n)$ since I have to go the other way and cannot see how:

$T(n)\geq a\log^2(n)$

in order to prove that $T(n)$ is in big omega of $n\log^2(n)$ and therefore in big theta of $n\log^2(n)$.

Am I missing something here?

答:
Let $k = \lfloor \frac12 \log n\rfloor$, which is $\Omega(\log n)$. Then if we just take the first $k+1$ terms of the sum, that is
$$
    \log n + \log \frac n2 + \log \frac n4 + \dots + \log \frac n{2^k},
$$
we already get something that's $\Omega(\log^2 n)$.

That's because $\frac{n}{2^k} \ge \sqrt n$, so $\log \frac{n}{2^k} \ge \log \sqrt{n} = \frac12 \log n$, which is $\Omega(\log n)$ - and that's the smallest term. Summing $\Omega(\log n)$ terms, on which we have an $\Omega(\log n)$ lower bound, we get $\Omega(\log^2 n)$.


问:
Find the area of the next polygon
The problem didn't give me any angles.
I was approaching the angle of 640 and 650 as a right angle to calculate the hypotenuse and thus have an edge, but I don't think it is the most correct

答:
Here is a systematic method, taking into account the fact that, fundamentaly, this issue has an infinite range of solutions.

Let $C(M,R)$ denote the circle with center $M$ and radius $R$.

Consider line $OA$ with length $1140$, which will be the $x$ axis with origin $0$.

Take a point $D$ on (green) circle $C(O,132)$ and a point $B$ on (red) circle $C(A,650)$.

If distance $BD \le 958$, these circles $C(D,318)$ and $C(B,640)$ have a common point that we will take for point $C$.

In this way, all the constraints are fulfilled.

Knowing the coordinates of the vertices of the pentagon, its area can be computed by the shoelace formula. In the case displayed on the figure, one obtains:

$$A=404,473 \ \text{m}^2$$

Remark: I have tried to stick to the appearance of the figure given in the question, but as @Achille Hui rightly remarks, this figure isn't faithful.

Taking different positions for $D$ and especially $B$ would lead to  different values of the area: see for example Fig. 2.

Appendix: Points $O,A,B,C,D$ of Fig. 1 have the following (rounded) coordinates:

$$\begin{pmatrix}  0   & 1140  &  \ \ \ 812  &  \ \ \ 199 &  -4 \\
 0& 0 &-561 &-377 &-132\end{pmatrix}$$

Here is another very different "solution", in this case with area $298,151 \ \text{m}^2$:

Title: Find the area of the next polygon


问:
How many positive integers <1,000,000,000 have exactly one digit equal to 9 and have the sum of digits equal to 13?
How many positive integers $<1,000,000,000$ have exactly one digit equal to $9$ and have the sum of digits equal to $13$?

I have:

$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + 9 = 13$

$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 = 4$

Then I use ${{n+k-1}\choose k}$:

${11\choose 4}$ = 330

Then $330*9 = 2970$.

So there are $2970$ integers that satisfy the problem.

My questions:

First, is this correct?

Second, why/when should I use ${{n+k-1}\choose k}$ over ${{n+k-1}\choose k-1}$

Third, when using the stars and bars approach, would this be a correct example for this problem:

.|...|..|..

答:
First of all, when considering which of the numbers in the
set $\{1, 2, \cdots 999999999\}$ have sum of digits equal to 13, you can
pretend that the smaller numbers will be zero filled on the left, since
including left-side zero digits does not affect the sum of the digits.

Second of all, it is impossible to have more than one specific digit
equal to 9, and still have the sum of the digits equal to 13.  Therefore,
you can assume WLOG, that the leftmost digit is 9, obtain a computation,
and then multiply this computation by 9 to get the final answer.
The reason that you are applying the factor of 9 is that the
9-digit can occur in any of the 9 slots.

Using Stars and Bars analysis, as discussed here
you want the number of non-negative solutions
to

$$x_1 + x_2 + \cdots + x_8 = 4.$$

This computation is

$$\binom{4 + [8-1]}{8-1}.$$

Therefore, the final answer is

$$ 9 \times \binom{4 + [8-1]}{8-1} ~=~ 2970.$$


问:
Quantum mechanics for mathematicians
I'm looking for books about quantum mechanics (or related fields) that are written for mathematicians or are more mathematically inclined.

Of course, the field is very big so I'm in particular looking for books that explain how C*-algebras and von Neumann-algebras are used, I want to see "practical" applications of those.

What I know is not much more than Griffiths' book (I don't like that book!) contains. I have in my possession the books by Claude Cohen-Tannoudji but they don't seem to contain this.

答:
I was recently looking for such a book and I found two that look promising:

An Introduction to the Mathematical Structure of Quantum Mechanics by F. Strocchi. This is a small book and assumes that you have prior knowlegde of functional analysis (in particular C* algebras).

Quantum Mechanics in Hilbert Space by Eduard Prugovecki. This book is large as the first three parts are functional analysis and the last two parts deal with quantum mechanics. No C* algebras here though, only Hilbert spaces of operators.

Title: Quantum mechanics for mathematicians


问:
Bisection method to $f(x) = \cos(x) - xe^{x}= 0$ .
I was doing an example of  Bisection method  applied to $f(x) = \cos(x) - xe^{x}= 0$,

I did all correctly upto 4th step , but after that i don't understand how it is considering the interval of $(0.5,0531)$ as i am getting it to be $(0.562,0.625)$
as $f(0.562)>0$ and $f(0.625)<0$ , and i saw other sources the answer is still coming to be $0.517$

Any ideas or help!

答:
As pointed out in the comments, it seems you are using degrees instead of radians for cosine. Letting $\operatorname{cosd}$ be cosine in degrees and $\cos$ be cosine in radians, one has

$$\cos(0.562)\approx0.84619,\quad\operatorname{cosd}(0.562)\approx0.99995$$
$$\cos(0.562)-0.562e^{0.562}\approx-0.13966,\quad\operatorname{cosd}(0.562)-0.562e^{0.562}\approx0.01410$$


问:
$K=\{E|f^{-1}(E)\in \mathcal{S} \}$ is a $\sigma$ algebra
This is a problem I have seen while self studying measure theory:

Let $(X,\mathcal{S})$ be a measure space, and $E\in \mathcal{S} \otimes \mathcal{S}$, with $f(x) = (x,x)$ then $K=\{E|f^{-1}(E)\in \mathcal{S} \}$ is a $\sigma$ algebra.

How do I prove $K$ to a $\sigma$ algebra? I am unsure how it contains $\varnothing$, is closed under complement and countable unions.

答:
Hint: Note that $\emptyset \in \mathcal{S}\otimes \mathcal{S}$ and $\emptyset \in \mathcal{S}$. Also, we have the following union and complement rules for pre-images:
$$f^{-1}(E^{c}) = (f^{-1}(E))^{c} \quad \mbox{and} \quad f^{-1}\bigg{(}\bigcup_{n\in \mathbb{N}}E_{n}\bigg{)} = \bigcup_{n\in \mathbb{N}}f^{-1}(E_{n})$$


问:
Distance between $P$ and a line in $\mathbb{R}^3$
Find the distance between $P=(6,4,-4)$ and a line that crosses points $A=(2,1,2)$ and $B=(3,1,-4)$. Note: Using dot product only. (No cross product).

I've tried doing the proyection of $P$, but since the canonical equation of the line does not exist, the solution was wrong. How could I apply the dot product for this problem?

答: If $\vec{v}$ is the projection of $\vec{PA}$ over $\vec{BA}$, then the distance you require is $||\vec{v}-\vec{PA}||.$


问:
$2^n-3^m=1 , m,n \in \mathbb N =?$
$2^n-3^m=1 , m,n \in \mathbb N =?$ my questions are:

do m,n exist?

are they finitely many $m,n$?

if there are infinitely many is there a way to describe them all?

Same question about $3^n-2^m=1 $, besides $m=n=1$ are there any others?

PS: This is not from number theory or home work, just personal pondering

答:
[Update: Table & text a bit extended]

I like to look at such questions in a, say, "constructive" way. First I change to the more familiar form
$$ 2^n = 3^m + 1$$
Now let m vary, we get, where N is the exponent at primefactor 2 in $3^m+1 (=x \cdot 2^N) $
 $$ \begin{array} {r|llll}
 m & 0&1&2&3&4 & ... \\
 3^m+1 &2& 4 & 10 & 28 &82 & ... \\
 N & 1&2 & 1 & 2 & 1 & ...
 \end{array} $$
which can easily be extended to improve also intuition and finally might be proved by binomial expansion or by Fermat/Euler.
So we find, that N is only 2 or 1 and that's the highest power of 2 occuring in $3^m+1$ - but clearly we can then have at most two solutions, because we have only 2 different N - that first two possibilites found in the table above prove to be true solutions.

Title: $2^n-3^m=1 , m,n \in \mathbb N =?$


问:
Is the statement of this question correct?
Here is the question I want to solve:

Let $f: R \rightarrow S$ be a map of commutative rings. Show that, if $\mathfrak{p}$ is a prime ideal of $S,$ then the inverse image $f^{-1}(\mathfrak{p})$ is a prime ideal of $R$.

My question is:

I need $f$ to be a homomorphism in my proof, does anything in the question givens implies that my function $f$ is a homomorphism?

答:
There is no hope for this to be true if $f$ is not a homomorphism. Typically in algebra, a "map" between some structures is expected to be a homomorphism preserving the expected properties. I don't think anyone is really interested in set maps between rings.

Anyways, here's an argument. Recall that an ideal is prime iff the quotient by that ideal is a domain. Consider then the composition $R \longrightarrow S \longrightarrow S/\frak p$ of $f$ and the quotient map. The kernel of this map is exactly $f^{-1}[\frak p]$, so the first isomorphism theorem implies the existence of an injective ring homomorphism $\overline{f}: R/f^{-1}[\mathfrak{p}] \longrightarrow S/\mathfrak{p}$. $\mathfrak{p} \subseteq S$ is prime by assumption, so $S/\frak p$ is a domain. As $\overline{f}$ is injective, $R/f^{-1}[\frak p]$ is also a domain, so $f^{-1}[\frak p]$ is indeed prime.


问:
Continuity of the function $\frac{1}{log(x)}$
The graph of log(x) is

When you're graphing $\frac{1}{log(x)}$;

Why is it that the reciprocal of log|x| at x=0 is taken to be 0, I.e., why is it continuous there? Isn't it just a limiting value towards infinity? Conversely, on zooming into the second graph (I plotted it online) f(0 never really touches 0).

Why does that happen, too?

答:
The log function $\log_e x \equiv \ln x$ is not defined at $x=0$. More precisely, it is only defined for $x >0$. You are correct when you're saying that this is a "limiting value".

Specifically, it is:

$$\lim_{x \to 0} \ln x = - \infty \implies \lim_{x \to 0} \frac{1}{\ln x} = 0.$$

The thickness of the plotted line does seem misleading, but the value $0$ does not belong to the function plotted - thus it should have a "hole" there.


答:
Why is it that the reciprocal of log|x| at x=0 is taken to be 0?

It isn't taken to be 0.

At $x = 0$, neither $\log|x|$ nor $\frac{1}{\log|x|}$
exist.

However, the $\lim_{x \to 0} \frac{1}{\log|x|}$ does exist and is equal to $0.$

Addendum

Per user request

Shouldn't the second graph have a hole there, then?

Absolutely.  At $x=0$, neither $\log x$ nor $\frac{1}{\log x}$ exist.  I think the thickness of the line in the graph is misleading.

Title: Continuity of the function $\frac{1}{log(x)}$

Body:
The graph of log(x) is

When you're graphing $\frac{1}{log(x)}$;

Why is it that the reciprocal of log|x| at x=0 is taken to be 0, I.e., why is it continuous there? Isn't it just a limiting value towards infinity? Conversely, on zooming into the second graph (I plotted it online) f(0 never really touches 0).

Why does that happen, too?


问:
What's a good way to notate: "$a$ equals all real numbers except $1$ and $-3$"?
I'm wondering if there is a nice way to denote "$a$ equals all real numbers except $1$ and $-3$" without having to just write out the title verbatim.

edit for context for posterity: I was given a 3x3 matrix with a variable $a$ in each of the entries with other numbers (eg. one entry was $a$ + $3$), and I was to find all the value of $a$ for which the matrix was invertible. I used the rule that the det(of a triangular matrix) = the product of the entries on the main diagonal and the fact that a matrix is invertible iff its determinant is not equal to $0$

答: Let $a \in \mathbb R - \{-3, 1\}$. It's also completely fine to write it in prose, like "a is a real number not equal to $1$ or $-3$." This is often preferable to writing it symbolically.


问:
When to use Newtons's, bisection, fixed-point iteration and the secant methods?
I've been introduced more or less to these methods of finding a root of a function (a point where it intersects the $x$ axis), but I'm not sure when they should be used and what are the advantages of one method over the other.

I think that it would be nice to have an answer that puts them in comparison and shows the situations where one method would be more advantageous than the other, etc.

So, my question are:

When should we use one method over the other and why?

And, what are the advantages and disadvantages therefore of one method over the other?

Also, if you want to provide a brief explanation of each of the method, I think that the answer would be more complete and interesting.

答:
I'm of an opinion a bit different from that of Lutz Lehmann's. Here are my thoughts concerning root-finding in 1 dimension:

TL;DR although no method is best and each has their drawbacks, it is often the case that another method can be used to counteract the drawback. The drawbacks to this mindset are either a necessary understanding of the provided function (will Newton's method work well here?) or more complicated code combining multiple methods (which method to be used each iteration?).

You should never use bisection on its own, unless you are absolutely certain the root cannot be linearly approximated nicely, a rather extreme case where no method outperforms bisection. Even if you believe this may be the case, you may want to look at the following points.

You should, whenever possible, use bisection with other methods, even if you believe the root may not be linearly approximated nicely. Such a method is called a hybrid method, and can be used to guarantee convergence in the event that something like Newton's method is not converging fast enough, or worse, diverging. See Newt-safe for example.

For bracketing methods (methods which bound the root like bisection, which should be used whenever possible), it is often better to first try something else before resorting to bisection (which should be a worst case resort). Lutz's answer mentions several of these.

Newton's method should be reserved for cases when computing $f(x)/f'(x)$ is quite easy (such as for a polynomial). Otherwise it is probably simpler to just use the secant method.

Fixed-point iteration should never be used outside of a theoretical situation. There not many advantages here aside from being marginally simpler to use for really simple or specific situations.

It is worth noting that although the second and third points are desirable, they are not always necessary. You may be able to deduce beforehand that Newton's method is perfectly fine on its own without any of the additional considerations above. On top of this, although the concept of a hybrid method sounds enticing, it can lead to significantly more complicated code. In other words, this may be quite overkill for the given problem.


问:
How to locate the points of Continuity & Discontinuity?
I have the given problem:

√(2x+3)

I found the point of discontinuity which is x cannot equal -1.5

However, I'm not sure how to find the point(s) of continuity.

Is there a formula to find the discontinuity and continuity?

答: HINT: Consider the sets where each function is discontinuous, and look at the composition of these functions.</p>


问:
prove this trigonometric expression
If $$\tan \theta +\sin \theta =m $$
and
  $$\tan \theta -\sin \theta =n$$
then prove that $$m^2-n^2=4\sqrt{mn}$$

I've  tried to $(m^2-n^2)$ as $(m-n)(m+n)$ but can't get to RHS.

答:
Hint: note that
$$
mn = (\tan\theta+\sin\theta)(\tan\theta-\sin\theta) = \tan^2\theta-\sin^2\theta
$$
Which can then be written as
$$
\tan^2\theta-\sin^2\theta = \sin^2\theta\left(\sec^2\theta-1\right)
$$
Continue from there, using some trig identities.</p>

Title: prove this trigonometric expression


问:
Equilibria of a Vector ODE
Suppose that $0<\tau<r$. Consider the vector ODE

\begin{align}
\dot{x}=-\tau xy \\
\dot{y}=\tau xy-ry \\
\end{align}

on $\Bbb{R}^{2}$.

Find the equilibria for this ODE and show that the y-axis is an invariant set.

I am having difficulty in solving these ODEs, as I am unsure whether I'm supposed to obtain two separate functions $x(t)$ and $y(t)$, or a single ODE relating both $x$ and $y$. Additionally, I'd appreciate if anyone could give me any pointers regarding the second portion of the question (showing that it's an invariant set) - thanks.

答:
The exercise is asking you to find the equilibria for this given ordinary differential equations problem. This does not require you to solve the problem given. For the equilibria, you simply want to find the points $(x,y)$ which satisfy:
$$\begin{cases}\dot{x} = 0 \\ \dot{y} = 0 \end{cases}.$$
For the second part of the problem, the $y$-axis is the set:
$$Y = \left\{ (x,y) \in \mathbb R^2 : x =0 \right\}.$$
This is the set that you need to show it is invariant.

Title: Equilibria of a Vector ODE


问:
Angle of intersection between
Calculate the angle of intersection between the functions $g(x)$ and $f(x)$ at the point $1.001, 1.9167$ where:

$g(x)=0.4 ln((10(x-1))+3.88623$

and

$f(x)= \sqrt {x-1} + 1.9427$

答:
Hint:

$\tan a = g'(x)$ and $\tan b = f'(x).$

Let $c = a - b.$

Then $\tan c = \tan (a - b) = \frac{\tan a - \tan b}{1 + \tan a \tan b}.$

Title: Angle of intersection between


问:
How to prove using Ferrer's diagrams?
Using Ferrer's diagrams, show that the number of partitions of $n$ into parts of size 1 or 2 is equal to the number of partitions of $n$ into two parts.</p>

答: Hint: Change your direction of viewing the diagram. </p>

Title: How to prove using Ferrer's diagrams?


问:
In a complex fourier series what does the term $\overline{c_n}$ stand for?
Im confused on what the bar in $\overline{c_n}$. Is $\overline{c_n}$ the conjugate of $c_n$? if not, what does the bar indicate? Thank you.

答: Yes, $\bar{c}_n$ is the complex conjugate of the Fourier coefficient of $c_n$


问:
Does changing the order of double integration (both integral limits are constants) alter the final answer?
I have studied that changing the order of double integration will not change the answer if both the limits of integration are constants. But this function is not agreeing with what I have studied:
$$1)\int_0^1\left(\int_0^1{\frac{x-y}{(x+y)^3}dy}\right)dx$$
$$2)\int_0^1\left(\int_0^1{\frac{x-y}{(x+y)^3}dx}\right)dy$$
The answer to the first integral is 0.5 and that of the second integral is -0.5 respectively.

Can anyone please explain why is this so?

答:
We have
\begin{align}
&\int_0^1\left(\int_0^1{\frac{x-y}{(x+y)^3}dx}\right)dy\\
&=\int_0^1\left(\int_0^1{\frac{x+y-2y}{(x+y)^3}dx}\right)dy\\
&=\int_0^1\left[\int_0^1\left(\frac{1}{(x+y)^2}-\frac{2y}{(x+y)^3}\right)dx\right]dy\\
&=\int_0^1\left[\frac{-1}{x+y}+\frac{2y}{2(x+y)^2}\right]_{x=0}^1dy\\
&=\int_0^1\left[\frac{-1}{(1+y)^2}\right]dy\\
&=\left[\frac{1}{1+y}\right]_0^1=-\frac12.
\end{align}
Similarly, you can show that
\begin{align}
\int_0^1\left(\int_0^1{\frac{x-y}{(x+y)^3}dy}\right)dx=\frac12.
\end{align}


答: You can write this as $a\in \{-3,1\}^c$

Title: What's a good way to notate: "$a$ equals all real numbers except $1$ and $-3$"?

Body:
I'm wondering if there is a nice way to denote "$a$ equals all real numbers except $1$ and $-3$" without having to just write out the title verbatim.

edit for context for posterity: I was given a 3x3 matrix with a variable $a$ in each of the entries with other numbers (eg. one entry was $a$ + $3$), and I was to find all the value of $a$ for which the matrix was invertible. I used the rule that the det(of a triangular matrix) = the product of the entries on the main diagonal and the fact that a matrix is invertible iff its determinant is not equal to $0$

Body: You can write this as $a\in \{-3,1\}^c$


问:
Why is $T(n)=2T\left(\frac{n}{2}\right) + n\log(n)$ time complexity is $Θ\big( n\log^2(n) \big) $?
I was doing some homework and worked out a closed form for $T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)$ and got:

$T(n)=n+n\left(\log(n)+\log\left(\frac{n}{2}\right)+\log\left(\frac{n}{4}\right)+\log\left(\frac{n}{8}\right)+\cdots+ 1\right)$

as closed form.

I was able to prove that $T(n)$ is in big O of $n\log^2(n)$ by:

$T(n) < n + n\log(n)\leq a\log^2(n)$ for some constant $a\geq 1$

But I don't know how $T(n)$ is in big omega of $n\log^2(n)$ since I have to go the other way and cannot see how:

$T(n)\geq a\log^2(n)$

in order to prove that $T(n)$ is in big omega of $n\log^2(n)$ and therefore in big theta of $n\log^2(n)$.

Am I missing something here?

答:
$$ \bbox[7px,border:2px solid red] {\text{MASTER THEOREM}}: $$

$$T(n)=aT(n/b)+f(n).$$
$$\bbox[1px,border:1px solid green] {a\ge 1,b>1,f(n)=Θ\big( n^k\cdot \log^p(n)\big)}$$
$$\text{CASE 1}:$$

$$ \text{if } \log_b(a)>k\text{ then: }\quad \bbox[0.2px,border:0.8px solid black] {T(n)=Θ\big( n^{\log_b(a)}\big)}   $$

$$\text{CASE 2}:$$

$$\text{if } \log_b(a)=k:\begin{cases}
\text{if $p>-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log^{p+1}(n)\big)}$} \\
\text{if $p=-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log\big( \log(n)\big)\big)}
$ }\\
\text{if $p<-1:\quad \bbox[1px,border:1.5px solid black] {T(n)=Θ\big( n^k\big)}$ }\\
\end{cases} $$

$$\text{CASE 3}:$$

$$\text{if $\log_b(a)<k:\begin{cases}
\text{if $p\ge 0:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot\log^p(n)\big)}
$} \\
\text{if $p<0:\quad \bbox[0.5px,border:0.2px solid black] {T(n)=\mathcal O \big( n^k\big)}
$}
\end{cases}$}$$

$$\text{So, let }a=b=2,f(n)=Θ\big( n^1\cdot \log^1(n)\big) \Rightarrow k=p=1,$$
$$\log_2(2)=1=k\text{ we are in case 2, where $p=1>-1$ hence,}$$
$$T(n)=Θ\big( n^k\cdot \log^{p+1}(n)\big)=\bbox[3px,border:2px solid green] {Θ\big( n\cdot \log^{2}(n)\big)}. $$


问:
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?

答:
With definition 2', every group is still a monoid, for all pratical intents and purposes. Formally one may be a triple and the other a quadruple, but by simply ignoring the last component (i.e. the map of elements to their inverse), you still get a monoid for every group.

If you want to make that relationship more formal, you can say that you have a map $F \::\: (X,*,e,i) \to (X,*,e)$ which takes every group to a monoid, and an associated map $f \::\: X \to X \,:\, x \to x$ which takes elements of the group to elements of the monoid and which is a monoid-isomorphism.

In situations such is this, its customary to then not distinguish between an element (a group) in the domain of $F$ and its image under $F$.

If you want to formalize this even further, I'm guessting that category theory allows you to do that nicely. Others will have to comment on the details, though - my knowledge of category theory is quite limited...


问:
In practice, what does it mean for the Newton's method to converge quadratically (when it converges)?
I was studying about the Newton's method (and other root-finding methods) and apparently Newton's method converges quadratically (or more) when it does.

Suppose that the sequence $\{x_k \}$ converges to the number $L$. We say that this sequence converges linearly to $L$, if $\exists$ a number $\mu \in (0, 1)$, such that $$\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_{k} - L|} = \mu$$

and $\mu$ is called the rate of convergence.

Similarly, it would converge quadratically to $L$ if

$$\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_{k} - L|^2} = \mu$$

where $\mu > 0$.

Why is that?

How can I see in practice if a sequence of iterations of the Newton's method is converging or not quadratically?

I guess I need to check for all $x_k$ that the second limit above is $\mu$ for some $\mu$ greater than $zero$...but how would I check this practically for a real concrete example?

答:
Let $\epsilon_n=|x_n-L|$ be the error on the $n$th step. Supposing the claimed limit does indeed hold, this means

$$\frac{\epsilon_{n+1}}{\epsilon_n^2}\sim\mu\implies\epsilon_{n+1}\simeq\mu\epsilon_n^2$$

i.e. the error on the next step is roughly a quadratic function of the error on the current step (hence the name). Similarly for linear convergence,

$$\epsilon_{n+1}\simeq\mu\epsilon_n$$

is a linear function of the current error.

Visually, however, one cannot easily "see" the value of $\epsilon_n$, but rather $\log(\epsilon_n)$, the number of digits accurate. Taking the logarithm of both sides, one may see that quadratic convergence implies

$$\log(\epsilon_{n+1})\simeq2\log(\epsilon_n)+\log(\mu)\simeq2\log(\epsilon_n)$$

meaning that the amount of digits accurate per iteration will double. You may obtain the order of convergence by observing the limit

$$\frac{\log(\epsilon_{n+1})}{\log(\epsilon_n)}\to2\quad(\text{or 1 for linear convergence})$$

with the additional caveat that the second term, $\log(\mu)$, is bounded (and less than $0$ for linear convergence), though usually if it isn't one doesn't worry too much about it.

For example, let us estimate $\sqrt2$ using Newton's method starting from $x_0=1$.

\begin{array}{c|c}
    n&x_n\\\hline
    0&1.000000000\\
    1&1.500000000\\
    2&1.\underline{41}6666666\\
    3&1.\underline{41421}5686\\
    4&1.\underline{414213562}\\
    5&1.414213562
\end{array}

It is easy to visually see that the number of digits accurate will roughly double per iteration.

If your question concerns why Newton's method (usually) converges quadratically, the proof follows from a quick Taylor expansion:

$$f(L)=f(x)+f'(x)(L-x)+\underbrace{\frac12f''(\xi)(L-x)^2}_{\mathcal O(\epsilon_n^2)}$$

Letting $f(L)=0$ and solving for $L$ from the second term leads to

$$L=\underbrace{x-\frac{f(x)}{f'(x)}}_{x_\mathrm{newton}}-\underbrace{\frac12\frac{f''(\xi)}{f'(x)}(L-x)^2}_{\mathcal O(\epsilon_n^2)}$$

which shows that

$$\epsilon_{n+1}=|L-x_\mathrm{newton}|=\left|\frac12\frac{f''(\xi)}{f'(x)}(L-x)^2\right|\simeq\mu\epsilon_n^2$$


答:
In my opinion Definition 2' is the correct definition (and Definition 2 is not a definition, but rather a characterization), because it follows the general principles how algebraic structures are defined in universal algebra (by operations satisfying equations), and therefore it also directly generalizes to other categories, for example topological spaces. A topological group is not just a topological monoid such that every object has an inverse. We also need that the inverse map is a continuous map (it is an interesting fact that for Lie groups this is automatic). So it is useful when the inverse map belongs to the data.

There are several other reasons why this is important: The subgroup generated by a subset $X$ of a group has underlying set $\{a_1^{\pm 1} \cdots \dotsc \cdots a_n^{\pm 1} : a_i \in X\}$. When you view groups as special monoids, you may forget the $\pm 1$ here.

Different categories should always be considered as disjoint. This helps to organize mathematics a lot. Unfortunately, forgetful functors between these categories are usually ignored, treated as if they were identities, but of course they are not. For example, we have the forgetful functor $U : \mathsf{Grp} \to \mathsf{Mon}$. It turns out that it is fully faithful (in many texts group homomorphisms are defined that way, of course again this is not conceptually correct). It has a left adjoint (Grothendieck construction) as well as a right adjoint (group of units). In particular it preserves all limits and colimits. These properties of $U$ show that often (but not always!) there is no harm when you identitfy $G$ with $U(G)$.

By the way, Definition 2' is conceptually not complete yet. You have to assume $x \cdot i(x) = i(x) \cdot x = e$. This becomes important when you study group objects in non-cartesian categories, aka Hopf monoids, for example Hopf algebras. The axiom for the antipode then contains two diagrams.

Title: Should every group be a monoid, or should no group be a monoid?

Body:
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?


问:
I am struggling understand how to differentiate the self financial portfolio
The self financing portfolio is given by:

$V_t$ = $a_t$$S_t$ + $b_t$$\beta_t$

where $dS_t$ = 2$S_t$dt + 4$S_t$d$B_t$ and $a_t$ = -t and $b_t$ = $\int_0^tS_u du$ and $\beta_t$ = 1 hence

$V_t$ = -t$S_t$ + $\int_0^tS_u du$

I believe we are suppose to use the chain rule and get the answer:

d$V_t$ = -t d$S_t$ - $S_t$dt + $S_t$dt

But I am not sure how to use the chain rule here and differentiate the integral.

答:
Recall the the product rule and Fundamental Theorem of Calculus.

We have:

$$\frac {dV_t}{dt} = \frac {d}{dt}(-tS_t)+\frac {d}{dt}\int_0^tS_udu=\left(-S_t-t\frac{dS_t}{dt}\right) + S_t$$

Giving:

$$dV_t = -tdS_t-S_tdt+S_tdt$$


问:
Understanding convergence of fixed point iteration
I was reading some slides explaining the convergence of the fixed point iteration, but honestly I'm not seeing or having an intuitive idea of how fixed-point iteration methods converge.

Assuming $p < 1$ as for the fixed point theorem, yields

$$|x_{k+1} - x^*| = |g(x_k) - g(x^*)| \leq p |x_k - x^*|$$

This is a contraction by a factor $p$. So

$$|x_{k+1} - x^*| \leq p|x_k - x^*| \leq p^2|x_{k-1} - x^*| \leq \cdots \leq p^{k+1}|x_{0} - x^*| \rightarrow 0$$

The smaller the $p$, the faster the convergence.

Could someone explain me this?

Also have another problem. There's then a statement saying

For root $x_1^*$ we have the conditions for fixed-point theorem holding $|g'(x)| < 0.4$, and we expect faster convergence than with the bisection methods.

Regarding this last statement, I would have a few questions.

What's the relation between the definition above, and the derivative of $g$ being less than $0.4$?

Why would it be faster than the bisection method? I know that the bisection method converges linearly, but honestly I still didn't have an intuitive idea of these convergence rates.

答:
Other answers cover most of the question. I added this answer because there seems to be a lack of explanation concerning the relation of $p$ and $g'(x)$.

Notice that the ratio of consecutive signed errors is given by

$$\frac{x_{k+1}-x^\star}{x_k-x^\star}=\frac{g(x_k)-g(x^\star)}{x_k-x_\star}\underset{x_k~\to~x^\star}\longrightarrow g'(x^\star)$$

Without the limit, the mean value theorem states this ratio must equal $g'(x)$ for some $x$ between $x_k$ and $x^\star$. These allow you to

bound the ratio of the errors (how fast fixed-point iteration is guaranteed to converge).

find the asymptotic ratio of the errors (how fast fixed-point iteration eventually converges).

It's worth noting that this only works for one-dimensional differentiable functions. More generally you will want to look into Lipschitz continuous functions, where $p$ is the Lipschitz constant.


问:
Using MGF of Normal Variable
I have $X\sim N(0, \sigma^2)$ where $\sigma^2$ is unknown. The HW question asks me to find the expected values of $X^2$ and $X^4$.

Attempt:

My guess is to use MGFs. I know that the MGF of $X$ is $M_X(t)=e^{\frac{1}{2}\sigma^2t^2}$, but don't exactly know how to use this properly. I thought $t$ corresponded to the $t^{th}$ moment but then $M_X(2)=e^{2\sigma^2}$. This is the second moment that I thought was supposed to equal the variance, but clearly it doesn't.

If anyone has any pointers or know of any good resources to point me in the direction of, I would very much appreciate it.

答:
To find the $n^{\rm th}$ moments, take the $n^{\rm th}$ differential of the moment generating function, $\mathsf M_{\small X}(t)$, with respect to $t$ and then evaluate this at $t=0$.

The second moment is thus the second differential evaluated at $t=0$. $$\begin{align}\left.\dfrac{\mathrm d^2~\mathsf M_{\small X}(t)}{\mathrm d t~^2}\right\rvert_{t=0} &= \left.\dfrac{\mathrm d^2~\mathrm e^{\sigma^2 t^2/2}}{\mathrm d t~^2}\right\rvert_{t=0}\\[1ex]&=\left.\dfrac{\mathrm d~\sigma^2t\mathrm e^{\sigma^2t^2/2}}{\mathrm d t}\right\rvert_{t=0}\\[1ex]&=\left[\sigma^2(\sigma^2t^2+1)\mathrm e^{\sigma^2t^2/2}\right]_{t=0}\\&=\sigma^2\end{align}$$

Which tells you that $\mathsf E(X^2)=\sigma^2$

Now do the fourth moment.

Title: Using MGF of Normal Variable


问:
When does $A$ iff $B$, imply $A=B$?
I understand that it goes in the other direction, that is, if $A=B$, then $A$ if and only if $B$ is also true.

(Just do a proof by contradiction, given $A=B$ assume $\lnot(A\leftrightarrow B)$, then $\lnot(A\leftrightarrow A)$, so the assumption was wrong and $A=B$ implies $A\leftrightarrow B$.)

However I want to know under what conditions does the implication go the other way? Is there any general set of requirements I can look for, to know that it will hold in the reverse case? Under what special circumstances can I conclude $A=B$ when I already know $A\leftrightarrow B$?

You are free to interpret $A$ and $B$ as whatever object you wish. If it helps, they can be restricted to a certain type to answer the question.

答:
There are no logic statements $A$ such that for all statements $B$, knowing that $A \leftrightarrow B$ ensures that $B$ is the exact same statement as $A$ (that is, the exact same string of symbols), since any statement $A$ is equivalent to $(True) \rightarrow A$, which is a longer string of symbols.

Of course, you could try putting conditions on both $A$ and $B$, but I'm not sure what you'd accomplish at that point since you get awfully close to having the condition be that $A$ and $B$ are in fact equal.

Title: When does $A$ iff $B$, imply $A=B$?


问:
Computation of a quotient group in the direct sum of three copies of Z
My question is simple: How to compute the quotient group
$$\frac{\langle(1,1,0),(0,0,1)\rangle}{\langle(1,1,-1),(1,1,1)\rangle}$$
of subgroups of $\mathbb Z \oplus \mathbb Z \oplus \mathbb Z$? The answer would be graet if each of the steps are explained.

This is my try: Letting $v=(1,1,0)$ and $w=(0,0,1)$, then the problem is to compute
$$\frac{\langle v,w\rangle}{\langle v+w, v-w \rangle}.$$
I wish this is isomorphic to the quotient
$$\frac{\mathbb Z \oplus \mathbb Z}{\langle (1,1),(1,-1) \rangle} \simeq \mathbb Z_2.$$

How to verify this argument? Or is there any other good argument? I want to know as many ways as possible. The answer may contain any undergraduate level mathematics.

Thank you.

答:
Another way to write this group is as $\langle u,v|uv,uv^{-1}\rangle$.

The Smith normal form can be used.  We start with $\begin{pmatrix} 1&1\\1&-1\end{pmatrix}$, since we have two generators and two relators. This leads to $\begin{pmatrix}1&0\\0&2\end{pmatrix}$, implying that we do indeed have $\Bbb Z_2$.


问:
How to prove that $\int_0^\infty \frac{\ln(x)}{x^2-1}\, dx$ converges
I have been trying really hard to prove that this integral $$\int_0^\infty \frac{\ln(x)}{x^2-1}\, dx$$

converges. However, I did not succeed. For now, I proved that
$$\int_0^\infty \frac{\ln(x)}{x^2-1}\, dx =  2  \int_1^\infty \frac{\ln(x)}{x^2-1}\, dx,$$
and that $f(x) = \frac{\ln(x)}{x^2-1}$ is continuous on $[1,+\infty)$.

If you can give me a hint, that would be nice.

答:
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$\ds{\bbox[5px,#ffd]{}}$
\begin{align}
&\bbox[5px,#ffd]{\int_{0}^{\infty}{\ln\pars{x} \over x^{2} - 1}\,\dd x} \leq
\int_{0}^{\infty}{2\pars{\root{x} - 1} \over x^{2} - 1}\,\dd x
\end{align}
See $\ds{\color{black}{\bf 4.1.37}\,\,}$ in A & S Table.

Then,
\begin{align}
&\bbox[5px,#ffd]{\int_{0}^{\infty}{\ln\pars{x} \over x^{2} - 1}\,\dd x} \leq
2\int_{0}^{\infty}{\dd x \over \pars{\root{x} + 1}
\pars{x + 1}}
\end{align}
The RHS is convergent since its integrand is
$\ds{\sim x^{-3/2}}$ as $\ds{x \to \infty}$.


问:
Linear algebra and multivariable calculus practice exercises for khan-academy videos?
I have completed linear algebra in khan-academy and I am going to watch the multivariable calculus lectures from there .There is no exercise in the linear algebra section. And I heard that linear algebra and multivariable calculus is the different way of looking at the same thing ,

so I am seeking for some practice exercises(possibly worked out so that I can check my soln) so that both my linear algebra skill and intuition behind the relation multivariable calculus become strengthen. Thanks in advance

答:
There is a website named Lemma run by one Pavel Grinfeld that has a course in linear algebra that is similar to Khan Academy's more developed material, in that it has short lecture videos interspersed with exercises that are graded automatically by the website.

I think Dr Grinfeld's linear algebra material is certainly good for its price ($0.00), although my notes from going through the first eight or so chapters note the following small number of issues:

§2.12, “Linear Subspaces of the Plane”, is confusing enough that I think it ought to be redone — for now, read the comment under the video.

Dr Grinfeld habitually abuses notation for null spaces, writing a linear combination with unknown coefficients to represent the set of all linear coefficients of its form. In §7.5, he attempts to address the confusion this caused one student who complained, but I would think it better to bother to use set-builder notation and thus to avoid the problem altogether, as do three of the four freely-available linear algebra textbooks recommended by the American Institute of Mathematics (the one that doesn’t omits null spaces entirely).

Dr Grinfeld, and perhaps his students, likely would make fewer mistakes in Gaussian elimination were he to use augmented matrix notation, as is used in the said three textbooks.


答:
First, a group is a monoid where every element has a two-sided inverse, not just a one-sided inverse.

Second, whether you define a group to be a monoid where every element has a two-sided inverse, or you define a group to be a quadruple $(G,\circ, e, i)$, where $\circ $ is an associative binary operation on $G$, $e$ is a twos-sided identity for the operation, and $i$ is a unary operation assigning to every element a two-sided inverse, is irrelevant to the question whether or not a group is a monoid. The particularities of a definition are of little importance as to what an actual thing is. The reason that every group is a monoid is that there is a fully faithful forgetful functor from $Grp$ to $Mon$ (the category of groups to the category of monoids). That means that there is a way of seeing every group as giving rise to a monoid. Exactly how that is done may depend on the particularities of the given definition of groups and monoids. But, no matter which definitions you'll choose for the concepts of group and monoid, there will result categories $Grp_1$, $Grp_2$, $Mon_1$, and $Mon_2$, with $Grp_1 \cong Grp_2$ and $Mon_1 \cong Mon_2$, and there will be the corresponding forgetful functors.

So, you may choose any particular way to define something. Category theory will then (if that thing you defined gives rise to a category, which most often is the case (but not always)) give you a precise way to saying when two definitions actually define the same thing (strongly the same means the categories will be isomorphic, weakly the same (which is the kind of sameness we care about in maths) means that categories will be equivalent). And then, whether every blool is a gradnal boils down to the existence of a certain nice functor from $Blool$ to $Gradnal$. This is independent of the choice of definition that gave rise to these categories, as long as different categories of blools (resp. gradnals) are equivalent.

In short: a concept lies not in a definition, but rather in the (too large to exist) equivalence class of equivalent categories. In some cases, categories need to be replaced by $\infty$-categories, making things much more difficult and interesting (e.g., this is in a sense modern algebraic topology: spaces are the same as simplicial sets, as long as one considers the relevant $\infty $-categories).


问:
Finite Element Code for Stokes Problem using P2P1 Quad Elements
I am trying to write some MATLAB code to solve fluid flow problems using the finite element method. I am starting with the relatively-simple steady Stokes problem. I am using the quadrilateral P2P1 element, and following Reddy and Gartling 2010. As far as I understand, the viscous matrix (K(1:18,1:18) in my code below) should be symmetric positive definite for the linear Stokes problem, but mine is symmetric but not positive definite! I checked every single line and cannot still figure out why it's not working!

Could anyone please take a look at the code and please tell me if anything is wrong!

I would definitely appreciate any additional advice/resources, thank you.

```<code>clc; clear;

syms r s mu rho x1 x2 x3 x4 x5 x6 x7 x8 x9 y1 y2 y3 y4 y5 y6 y7 y8 y9

% Velocity Shape functions (Reddy and Gartling P65):
% h > ψ, r > ξ, s > η, H > Ψ:
h1 = ( (1-r)*(1-s)*(-r-s-1)+(1-r^2)*(1-s^2) )/4;
h2 = ( (1+r)*(1-s)*(+r-s-1)+(1-r^2)*(1-s^2) )/4;
h3 = ( (1+r)*(1+s)*(+r+s-1)+(1-r^2)*(1-s^2) )/4;
h4 = ( (1-r)*(1+s)*(-r+s-1)+(1-r^2)*(1-s^2) )/4;
h5 = ( 2*(1-r^2)*(1-s^1)-(1-r^2)*(1-s^2) )/4;
h6 = ( 2*(1+r^1)*(1-s^2)-(1-r^2)*(1-s^2) )/4;
h7 = ( 2*(1-r^2)*(1+s^1)-(1-r^2)*(1-s^2) )/4;
h8 = ( 2*(1-r^1)*(1-s^2)-(1-r^2)*(1-s^2) )/4;
h9 = ( 4*(1-r^2)*(1-s^2) )/4;
H =  [h1; h2; h3; h4; h5; h6; h7; h8; h9];

Hr = diff(H,r); Hs = diff(H,s);

% Coordinate Interpolation (Local to Natural Coor.) (Reddy and Gartling P165)
x_n = [x1; x2; x3; x4; x5; x6; x7; x8; x9];
y_n = [y1; y2; y3; y4; y5; y6; y7; y8; y9];

% The Jacobian operator and its determinant (Reddy and Gartling P69)
J = [Hr.'; Hs.']*[x_n y_n];
iJ = J^-1; dJ = det(J);
% Derivatives of H Shape Functions:
Hxy = iJ*[Hr.'; Hs.']; Hx = transpose(Hxy(1,:)); Hy = transpose(Hxy(2,:));

% Pressure Basis Functions (Reddy and Gartling P65):
HP = [(1-r)*(1-s)/(4); (1+r)*(1-s)/(4); (1+r)*(1+s)/(4); (1-r)*(1+s)/(4)];

% Building the FE Equations (Reddy and Gartling P166):
K11 = mu*(Hx*Hx.')*dJ;
K22 = mu*(Hy*Hy.')*dJ;
K12 = mu*Hx*Hy.'*dJ;
K21 = mu*Hy*Hx.'*dJ;
Q1  = Hx*HP.'*dJ;
Q2  = Hy*HP.'*dJ;
Zp  = zeros(max(size(HP)), max(size(HP)));

K = [2*K11+K22,  K12,       -Q1; ...
     K21,        K11+2*K22, -Q2; ...
    -Q1.',      -Q2.',       Zp];
</code>```

答:
I realized the shape functions h5, h6, h7, and h8 in the textbook were wrong. They are missing "2" in the second term. They should be as follows:

```<code>h5 = (2*(1-r^2)*(1-s^1)-2*(1-r^2)*(1-s^2) )/4;
h6 = (2*(1+r^1)*(1-s^2)-2*(1-r^2)*(1-s^2) )/4;
h7 = (2*(1-r^2)*(1+s^1)-2*(1-r^2)*(1-s^2) )/4;
h8 = (2*(1-r^1)*(1-s^2)-2*(1-r^2)*(1-s^2) )/4;
</code>```

It makes me sad that such a highly praised book has such a silly error.

Body:
I realized the shape functions h5, h6, h7, and h8 in the textbook were wrong. They are missing "2" in the second term. They should be as follows:

h5 = (2*(1-r^2)*(1-s^1)-2*(1-r^2)*(1-s^2) )/4;
h6 = (2*(1+r^1)*(1-s^2)-2*(1-r^2)*(1-s^2) )/4;
h7 = (2*(1-r^2)*(1+s^1)-2*(1-r^2)*(1-s^2) )/4;
h8 = (2*(1-r^1)*(1-s^2)-2*(1-r^2)*(1-s^2) )/4;

It makes me sad that such a highly praised book has such a silly error.


问:
Proof that the dimension of a matrix row space is equal to the dimension of its column space
I have the following theorem:

Theorem 3.12. Let A be an m  n matrix. Then the dimension of its row
space is equal to the dimension of its column space.

And the following proof is given:

Proof. Suppose that $\lbrace v_1,v_2,\dots,v_k\rbrace$ is a basis for the column space of $A$.  Then each column of $A$ can be expressed as a linear combination of these vectors; suppose that the $i$-th column $c_i$ is given by $$c_i = \gamma_{1i}v_1+\gamma_{2i}v_2+\dots+\gamma_{ki}v_k$$ Now form two matrices as follows: $B$ is an $m\times k$ matrix whose columns are the basis vectors $v_i$, while $C=(\gamma_{ij})$ is a $k\times n$ matrix whose $i$-th column contains the coefficients $\gamma_{1i},\gamma_{2i,}\dots,\gamma_{ki}$.  It then follows$^7$ that $A=BC$.

However, we can also view the product $A= BC$ as expressing the rows of $A$ as a linear combination of the rows of $C$ with the $i$-th row of $B$ giving the coefficients for the linear combination that determines the $i$-th row of $A$.  Therefore, the rows of $C$ are a spanning set for the row space of $A$, and so the dimension of the row space of $A$ is at most $k$.  We conclude that: $$\dim(\operatorname{rowsp}(A))\leq\dim(\operatorname{colsp}(A))$$
  Applying the same argument to $A^t$, we conclude that:$$\dim(\operatorname{colsp}(A))\leq\dim(\operatorname{rowsp}(A))$$and hence these values are equal

However, I am finding this proof impossible to follow and understand. Can someone please offer an alternative proof or explain what this proof is saying?

Thank you.

答:
Row reduction eliminates the redundant rows in a matrix, i.e. the rows that are linear combinations of other rows. Row operations also do not change the row space because taking nonzero linear combinations of a set of vectors does not change their span.

It is impossible not to eliminate a row that is a linear combination of the others when reducing to reduced echelon form, and so the RREF of the matrix will give you the number of linearly independent rows, i.e. the dimension of the row space. Let p be the number of rows of zeroes at the bottom of the matrix. Then the dimension of the row space is m - p.

Now consider the effect of this reduction on columns. Row operations preserve linear dependence relations among the columns of A so that the same linear dependence relation holds for columns of the RREF of A as for A. If you have an m x n matrix with p rows of zeros at the bottom, then you also have m - p pivots. If this were not the case, then one of the rows above those p rows would be row reducible to a row of all zeros, which is what happens to any row that does not have a pivot.

Since the number of pivots is equal to the number of linearly independent vectors in the RREF, and this is also equal to the number of linearly independent vectors in the original matrix, these columns form a basis for Col(A). The dimension of the column space is the number of basis vectors, and so we have shown that the two are equal.


答:
For something not similar to Khan Academy, a different answer is provided by the free textbooks recommended by the American Institute of Mathematics that I referenced in my other answer. Of the four free linear algebra textbooks that they recommend, three have exercises with solutions:

Linear Algebra by Jim Hefferon — This textbook won the 2020 Daniel Solow Author's Award of the Mathematical Association of America, and the award citation specifically notes (among other worthy qualities) the book's “tremendous variety of exercises”, so this book may be a particularly appropriate choice.

A First Course in Linear Algebra by Rob Beezer

Linear Algebra Done Wrong by Sergei Treil

Title: Linear algebra and multivariable calculus practice exercises for khan-academy videos?

Body:
I have completed linear algebra in khan-academy and I am going to watch the multivariable calculus lectures from there .There is no exercise in the linear algebra section. And I heard that linear algebra and multivariable calculus is the different way of looking at the same thing ,

so I am seeking for some practice exercises(possibly worked out so that I can check my soln) so that both my linear algebra skill and intuition behind the relation multivariable calculus become strengthen. Thanks in advance


问:
How I can find the supremum and infimum of $ \{\frac{m}{2^n}: n,m\in\mathbb{N}\}$?
I claim that supremum doesn't exist and infimum is $0$, but I want to prove this by definition. I can see that $$0<\frac{m}{2^n}<\frac{m}{2}$$ So, I claim that the supremum not exists and $0$ is a lower bound.

答:
Yes, there does not exist an upper bound because otherwise you can take $n = 1$ and if we let $u$ be an upper bound for $m/2$  where $u$ is an integer then take $m = 2u+1$. If $u$ is a non-integer take $m = 2u_{1}+1$ where $u_{1} = \lceil u \rceil$ which denotes the smallest integer $u_{1}$ such that $u_{1} > u$.

Clearly $m/2^n > 0$ since $
m,2^n > 0$ which implies that $0$ is a lower bound. If there exists a lower bound $s > 0$ then take $m = 1$ and we must find an $n$ such that $0 < 1/2^n < s$ to arrive at a contradiction. One can choose $n$ such that $2^n > 1/s$ and more explicity, $n>log_2(1/s)$ and we are done.


问:
5x ≡ 3 (mod 12) how do you find the first three xs without listing them?
5x ≡ 3 (mod 12).

The question asked me to find the smallest positive non zero integers that can be plugged in the place of x.

I only know how to find the answer by making a list.

5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0, 5, 10, 3.

It took 12 for 3 to get back to another 3.
So the answer is 3, 15(=3+12), 27(=3+12+12).

But is there any shortcut or formula to get them more easily?

答: $5\cdot5=25\equiv1\operatorname{mod}12$, so multiplying both sides of the congruence by $5$ gives $x\equiv15\equiv3\operatorname{mod}12$.


问:
bounds for number related to colourings

Let $R(r,s)$ be the minimum $n$ so that for all colourings of the edges of the complete graph $K_n$ on $n$ vertices with $2$ colours green and orange, there is a complete subgraph of $K_n$ with $r$ vertices whose edges are all green or a complete subgraph with $s$ vertices that are all orange. Show that $R(s,s) > (\sqrt{2} + 0.00000001)^{s-1}$ for $s\geq 2$ and $R(s,s) <3.999999999^s$ for all $s\geq 2.$

I know how to show that $R(s,s) > \sqrt{2}^{s-1}$ by showing that for any $s$-element subset of $V(K_n)$, the number of colourings where all the edges of $S$ are the same colour is less than the total number of colourings. But how can I improve this upper bound to the precision specified in the question? What might be useful? Induction? Recurrence relations?

答:
Both of these problems are open. We don't have a lower bound $R(s,s) \ge C^s$ for any constant $C > \sqrt2$, and we don't have an upper bound $R(s,s) \le C^s$ for any constant $C < 4$.

We do have better bounds than $\sqrt 2^{s-1}$ and $4^s$.

The argument for $R(s,s) > \sqrt 2^{s-1}$ you're describing can be strengthened: it shows that $R(s,s) > n$ whenever $\binom ns < 2^{\binom s2 - 1}$, and the best $n$ we can find in this way is asymptotically $(1+o(1))\frac{s}{\sqrt2 e} \sqrt 2^s$.

You can prove by induction that $R(r,s) \le \binom{r+s-2}{s-1}$ and in particular $R(s,s) \le \binom{2s-2}{s-1}$, which is asymptotically $(1+o(1))\frac{1}{\sqrt{\pi s}} 4^s$.

Wikipedia cites results due to Spencer and Conlon that improve on this, giving $$(1+o(1))\frac{\sqrt 2 s}{e}\sqrt2^s \le R(s,s) \le s^{-(c \log s)/(\log \log s)} 4^s.$$

However, a lower bound of $(\sqrt{2} + 0.00000001)^{s-1}$, or an upper bound of $3.999999999^s$, would be stronger than these results for sufficiently large $s$.

Title: bounds for number related to colourings


答:
Use Euclidean algorithm to find the multiplicative inverse,

$$12=2(5)+2$$

$$5=2(2)+1$$

Hence, we have $$1=5-2(2)=5-2(12-2(5))=5(5)-2(12)$$

Hence $$1 \equiv 5(5) \pmod{12}$$

$$5^{-1} \equiv 5 \pmod{12}$$

$$5x \equiv 3 \pmod{12}$$

Multiplying by the $5^{-1}=5$ on both sides,

$$x\equiv 5(3)\equiv 15 \equiv 3 \pmod{12}$$

Title: 5x ≡ 3 (mod 12) how do you find the first three xs without listing them?

Body:
5x ≡ 3 (mod 12).

The question asked me to find the smallest positive non zero integers that can be plugged in the place of x.

I only know how to find the answer by making a list.

5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0, 5, 10, 3.

It took 12 for 3 to get back to another 3.
So the answer is 3, 15(=3+12), 27(=3+12+12).

But is there any shortcut or formula to get them more easily?


问:
linear algebra and variance
Please help me understand the following concept.
Let A be a matrix of constants and Y is a random vector.
Var(AY) = AVar(Y)A', where A' is A transpose.
I understand that AA' = A^2.
What I don't understand is why A' goes in the end, instead of AA'Var(Y).
Is there some kind of property in linear algebra that would help me understand the correct order?
Thank you!</p>

答: By definition, ${\rm Var}(Y) = \mathbb{E}[YY^\top] - \mathbb{E}[Y]\mathbb{E}[Y]^\top$. Recall that $\mathbb{E}$ is a linear map. Let's compute ${\rm Var}(AY)$ directly: $$\begin{align} {\rm Var}(AY) &= \mathbb{E}[AY(AY)^\top] - \mathbb{E}[AY]\mathbb{E}[AY]^\top \\ &=  \mathbb{E}[AYY^\top A^\top]  - (A\mathbb{E}[Y])(A\mathbb{E}[Y])^\top \\ &= A\mathbb{E}[YY^\top]A^\top - A\mathbb{E}[Y] \mathbb{E}[Y]^\top A^\top \\ &= A(\mathbb{E}[YY^\top] - \mathbb{E}[Y]\mathbb{E}[Y]^\top)A^\top \\ &= A{\rm Var}(Y)A^\top,\end{align}$$as required. The key property you seem to have missed is that the transpose of a product of matrices is the product of the transposes, in the reverse order: $(AB)^\top = B^\top A^\top$.

Title: linear algebra and variance


问:
What are the pros and cons of Newton's Method versus the Relaxed version?
Given that Newtons method for solving $f(x)= 0$ is: $x_{k+1} = x_{k} - \frac{f(x_{k})}{f'(x_{k})}$. The relaxtion of this method replaces $\frac{1}{f'(x_{k})}$ with some real valued constant y not equal to zero: $x_{k+1} = x_{k} - yf(x_{k})$

Which method converges faster and why?

How do you derive the error equations in terms of consecutive iterations?

Furthermore, given the error equation of an iterative method how do you derive its order of convergence?

Body:
Use Taylor series in the form
$f(x+h)
=f(x)+hf'(x)+O(h^2)
$.

Then

$\begin{array}\\
\text{Newton}\\
f(x_{k+1})
&=f(x_{k} - \frac{f(x_{k})}{f'(x_{k})})\\
&=f(x_{k}) - \frac{f(x_{k})}{f'(x_{k})}f'(x_k)+O((\frac{f(x_{k})}{f'(x_{k})})^2)
\qquad x = x_k, h = - \frac{f(x_{k})}{f'(x_{k})}\\
&=O((\frac{f(x_{k})}{f'(x_{k})})^2)\\
\\
\text{Relaxed}\\
f(x_{k+1})
&=f(x_{k} - yf(x_k))\\
&=f(x_{k}) - yf(x_{k})f'(x_k))+O(yf(x_{k}))^2
\qquad h = yf(x_k)\\
&=f(x_{k}) - yf(x_{k})f'(x_k))+O(yf(x_{k})^2)\\
&=f(x_{k})(1- yf'(x_k)))+O(yf(x_{k})^2)\\
\end{array}
$

So Newton goes quadratically
and relaxed goes down linearly.


问:
Power series with cubic factorials
I am looking for a starting point to obtain the closed form of
$$ \sum_{k=0}^{\infty} x^k \frac{(2k)!}{(k!)^3}. $$
I have tried transforming the ratio of factorials into combinations, but this lead me nowhere. I also computed several values of the series on Wolfram and I expect the answer to look like $e^{2x} I_0(2x)$ for $I_0$ the $0$-th modified Bessel function.
Does anyone has an idea on how to properly obtain the result ?

答:
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$\ds{\bbox[5px,#ffd]{}}$

\begin{align}
&\bbox[5px,#ffd]{\sum_{k = 0}^{\infty}x^{k}\,
{\pars{2k}! \over \pars{k!}^{3}}} =
\sum_{k = 0}^{\infty}{x^{k} \over k!}{2k \choose k}
\\[5mm] = &\
\sum_{k = 0}^{\infty}{x^{k} \over k!}\bracks{z^{k}}
\pars{1 + z}^{2k}
\\[5mm] = &\
\bracks{z^{0}}\sum_{k = 0}^{\infty}
{\bracks{{\pars{1 + z}^{2}x/z}}^{k} \over k!}
\\[5mm] = &\
\bracks{z^{0}}
\exp\pars{{\pars{1 + z}^{2}\,x \over z}}
\\[5mm] = &\
\bracks{z^{0}}
\exp\pars{x\,\bracks{{1 \over z} + 2 + z}}
\\[5mm] = &\
\expo{2x}\bracks{z^{0}}
\exp\pars{{1 \over 2}\bracks{\color{red}{2x}}\,\bracks{z + z^{-1}}}
\end{align}

The last exponential in the right hand side is the
Beseel $\ds{\on{I}_{\nu}}$ Generating Function. Namely,
\begin{align}
&\bbox[5px,#ffd]{\sum_{k = 0}^{\infty}x^{k}\,
{\pars{2k}! \over \pars{k!}^{3}}} =
\bbx{\expo{2x}\on{I}_{0}\pars{2x}} \\ &
\end{align}

Title: Power series with cubic factorials


问:
a question about calculating eigenvectors
It has to be the silliest question, but it’s not clear to me how to calculate eigenvectors quickly. I am just talking about a very simple 2-by-2 matrix.

When I have already calculated the eigenvalues from a characteristic polynomial, I can start to solve the equations with $A\mathbf{v}_1 = e_1\mathbf{v}_1$ and A\mathbf{v}_2 = e_2\mathbf{v}_2$, but in this case it always requires writing lines of equations and solving them.

On the other hand I figured out that just by looking at the matrix you can come up with the eigenvectors very quickly. But I'm a bit confused in this part.

When you have the matrix with subtracted $e_1$ values like this:
$$\left(\begin{array}{cc}
A&B\\
C&D
\end{array}\right).$$

Then for me, it always worked to use the eigenvector.
$$\left(\begin{array}{r}-B\\A\end{array}\right)$$

But in some guides I find that they are using A C as an eigenvector.
$$\left(\begin{array}{c}A\\C
\end{array}\right).$$

And when I check it, they are indeed multiples of each other. But this other method is not clear to me, how could $A$ and $C$ mean anything about the eigenvector, when both of them are connected to $x$, without having to do anything with $y$. But it’s still working. Was it just a coincidence?

So is the recommended method for calculating them is just to subtract the eigenvalues from the matrix and look at
$$\left(\begin{array}{r}
-B\\A\end{array}\right)\qquad\text{or}\qquad\left(\begin{array}{r}
-D\\A
\end{array}\right).$$

答:
Please goes through this list one by one.

Your method will work as long as either $A$ or $B$ is not zero.

When doesn't it work?  Try calculate the eigenvector of $\left(\begin{smallmatrix} 1 & 0 \\ 1 & 1 \end{smallmatrix} \right )$.

Does the method of taking $\left(\begin{smallmatrix} A\\C  \end{smallmatrix} \right )$ work?  Try calculate the eigenvector of $\left(\begin{smallmatrix} 3 & 3 \\ 4 & 7 \end{smallmatrix} \right )$ and see it for yourself.

What is an obvious solution to the equation $Ax+By=0$? Hint: it has something to do with your method.

Say when either $A$ or $B$ is nonzero, what will happen to the second row when you do row reduction? Why? Remember, the determinant of $\left(\begin{smallmatrix} A & B \\ C & D \end{smallmatrix} \right )$ is zero.

Can you see why your method works by now?


答:
$5$ and $12$ are coprime, so by Bezout some linear combination is $1$.  Indeed, $5\cdot5+(-2)12=1$.  Thus, $5^{-1}\equiv5\bmod{12}$.

So solve the congruence by multiplying by $5^{-1}\equiv5$ on both sides.  Get $x\equiv3\bmod{12}$.


问:
Proving the number of coplanar subgraphs of a hypercube
Given an n-dimensional hypercube, join each vertex to obtain a complete graph. Then the number of subgraphs of four coplanar vertices is given by

$6^n/8−4^{n−1}+2^{n−3}$

Example: a 2D square has just one coplanar rectangular subgraph, a 3D cube has 12 (6 faces and 6 connecting each diagonally opposite pair of edges).

How would I go about proving this result?

I've spent the last few days trying to find a proof for this, I only discovered this formula by computing the first few values with Matlab, and upon Googling this sequence led me to OEIS (sequence A016283), giving me this formula and confirming my suspicions via a brief comment, but I have been unable to find a formal proof for how this formula emerges from the problem.

(I don't have any much experience with graph theory so that's probably why I'm struggling to prove this myself, but this would be a nice result to include in something I'm writing.)

答:
Let's first count the number of planar $K_4$'s with one vertex at the origin (assuming the vertices of the hypercube are at $\{0,1\}^n$).

If three of the vertices are at $\vec 0$, $\vec x$, and $\vec y$, then the entire plane containing them is given by $s \vec x + t \vec y$ with $s, t \in \mathbb R$. What can the fourth point be? There are two cases:

Suppose there are coordinates $i$ with $x_i = 1, y_i = 0$ and $j$ with $x_j=0, y_i = 1$. Then to get $sx_i + t y_i \in \{0,1\}$ we must have $s \in \{0,1\}$;  to get $sx_j + ty_j \in \{0,1\}$ we must have $t \in \{0,1\}$. since $0\vec x + 0\vec y$, $0 \vec x + 1\vec y$, and $1\vec x + 0 \vec y$ are already counted, the fourth point must be $\vec x + \vec y$.

Suppose not there are not such coordinates; then without loss of generality, $\vec x \le \vec y$ in each coordinate. For $\vec x \ne \vec 0$, there needs to be a coordinate $i$ with $x_i = 1$ (and therefore $y_i=1$). For $\vec x \ne \vec y$, there needs to be a coordinate $j$ with $x_j=0$ and $y_j=1$. Now, to get $sx_i + ty_i \in \{0,1\}$ we must have $s=-t$ or $s=1-t$; to get $sx_j + ty_j \in \{0,1\}$ we must have $t \in \{0,1\}$. This is four possibilities, three of which are $\vec 0, \vec x, \vec y$; the fourth point must be $\vec y - \vec x$.

So we must have four vertices $\{0, \vec x, \vec y, \vec x + \vec y\}$ (the second case is just the same as the first with different vertices chosen as $\vec x$ and $\vec y$). To get $\vec x + \vec y \in \{0,1\}^n$, we cannot have $x_i = y_i = 1$ for any coordinate $i$.

This gives $3^n$ ways to choose $\vec x$ and $\vec y$: in each coordinate $i$, we choose either $x_i = y_i = 0$, or $x_i = 1, y_i=0$, or $x_i = 0, y_i = 1$. However, we must choose the second option at least once, and the third option at least once; otherwise, we get a degenerate set with $\vec x = \vec 0$ or $\vec y = \vec 0$. By inclusion-exclusion, the number of options is $3^n - 2^n - 2^n + 1^n$, or $3^n - 2 \cdot 2^n + 1$.

However, we get the same set $\{0, \vec x, \vec y, \vec x + \vec y\}$ if we swap $\vec x$ and $\vec y$, so there are only $\frac{3^n - 2 \cdot 2^n + 1}{2}$ planar $K_4$'s containing $\vec 0$.

There was nothing special about the origin, so there are also $\frac{3^n - 2 \cdot 2^n + 1}{2}$ planar $K_4$'s containing any other vertex. This gives a total of $2^n \cdot \frac{3^n - 2 \cdot 2^n + 1}{2} = \frac{6^n - 2 \cdot 4^n + 2^n}{2}$ planar $K_4$'s, except that each one is counted $4$ times: once for each of its vertices.

So the final answer is $$\frac{6^n - 2 \cdot 4^n + 2^n}{8}.$$


问:
Is $|A| > |B|$?
Let $A=\bigcup_{i\in I_A}A_i$ where $I_A$ is the index set of $A$ and such that $A_i \cap A_j=\emptyset$ for any $i,j\in I_A$. Similarly, let $B=\bigcup_{j\in I_B}B_j$ where $I_B$ is the index set of $B$ and such that $B_i \cap B_j=\emptyset$ for any $i,j\in I_B$. Suppose:

For every $i\in I_A$ and every $j\in I_B$, $|A_i|>|B_j|$.

$|I_A|>|I_B|$.

Can we conclude that $|A|>|B|$? I think we can, but I don't know how to prove it unfortunately. There is definitely an injection from $B$ to $A$. I assumed that there is a bijection from $B$ to $A$ for reductio. But after this, I'm not sure how to proceed.

答:
No.  For instance, suppose $|I_A|=\aleph_1$ and $|A_i|=\aleph_\omega$ for each $i$, while $|I_B|=\aleph_0$ and for each $n\in\mathbb{N}$, there is one $j$ such that $|B_j|=\aleph_n$.  Then $|A|=\aleph_1\cdot\aleph_\omega=\aleph_\omega$ but $|B|=\aleph_\omega$ as well since $|B|\geq\aleph_n$ for each $n$.

In general, we will have $|B|\leq|I_B|\cdot\kappa$ where $\kappa=\sup_j |B_j|$, and $|A|\geq |I_A|\cdot \kappa$ since $|A_i|\geq\kappa$ for each $i$.  However, if $\kappa\geq |I_A|$ and no $|A_i|$ is strictly greater than $\kappa$, then $|A|$ and $|B|$ will both be equal to $\kappa$ as long as $\kappa$ is infinite, as in the example above.

Title: Is $|A| > |B|$?


问:
Hermite's equation of order $\alpha$
Show that the general solution of Hermite's equation of order $\alpha$:

$${y}''-2x{y}'+2\alpha y=0$$

$$is$$

$$y(x)=c_{0}y_{1}(x)+c_{1}y_{2}(x)$$

where $y_{1}(x)$ and $y_{2}(x)$ are power series solutions centered at the ordinary point 0.

Find the two power series.

I am stuck at this question. I don't really know what to do.

答:
Assume that $y(x)=\sum_{n=0}^{\infty}{a_nx^n}$. Substituting this into the equation, we find
$$\sum_{n=0}^{\infty}n(n-1)a_nx^{n-2}-2\sum_{n=0}^{\infty}na_nx^{n}+2\alpha\sum_{n=0}^{\infty}a_nx^{n}=0$$
or, equivalently,
$$\sum_{n=0}^{\infty}(n+2)(n+1)a_{n+2}x^{n}-2\sum_{n=0}^{\infty}na_nx^{n}+2\alpha\sum_{n=0}^{\infty}a_nx^{n}=0.$$
This means that whenever
$$a_{n+2}=\frac{2(n-\alpha)}{(n+2)(n+1)}a_n,\tag{1}$$
the series will solve the differential equation. Obviously, $a_0$ and $a_1$ fix the rest of the series. In particular, we can set $a_1=0$ - then the series will contain only even powers of $x$. Similarly, for $a_0=0$ it will contain only odd powers of $x$. The general solution is an arbitrary linear combination of this odd and even part, so you can interpret $a_0$ and $a_1$ as two arbitrary integration constants.

Added: You can also explicitly solve the recursion (1): for example,
$$a_{2k}=\frac{\Gamma(\frac12)\Gamma(k-\frac{\alpha}{2})}{k!\Gamma(-\frac{\alpha}{2})\Gamma(k+\frac12)}a_0.$$
[Exercise: show this - for example, by induction]. Hence the series
$$\sum_{k=0}^{\infty}\frac{\Gamma(\frac12)\Gamma(k-\frac{\alpha}{2})}{k!\Gamma(-\frac{\alpha}{2})\Gamma(k+\frac12)}x^{2k}$$
gives one solution of your differential equation.
One can similarly determine the coefficients with odd indices and write the second solution.

Title: Hermite's equation of order $\alpha$


问:
$[-1,1]^{\mathbb{N}}$ compact with respect to particular metric
At Showing the "traditional" Hilbert Cube $C$ is homeomorphic to $[-1,1]^{\mathbb{N}}$, the questioner states "$[-1,1]^{\mathbb{N}}$ ... is, by Tychonoff, compact when endowed with the metric $d(x,y)=\sum_{j \in \mathbb{N}}\frac{1}{2^j}\left\lvert x_j-y_j\right\rvert$". How is that proved? Presumably one would need to show that the topology induced by this given metric is equivalent to the product topology in order for Tychonoff's theorem to apply. Beyond that it's rather unclear to me.

答:
You are correct: their point is that the metric and product topologies on $[-1,1]^{\Bbb N}$ are the same. And therefore by Tychonoff, that topology is compact.

Let $x \in U$, an open set in the product topology. $\pi_j(U) = [-1,1]$ except for a finite number of indexes $j$. For each of those, $\pi_j(U)$ is an open neighborhood of $x_j$. You can choose $r_j > 0$ small enough that $(x_j -r_j, x_j+r_j) \subseteq \pi_j(U)$. And since there only finitely many, you can choose $r > 0$ such that $r < 2^{-j}r_j$ for each $j$. It follows that the ball $B(x, r) \subseteq U$. Since this is true of all such $x \in U, U$ is open in the metric topology.

Conversely, let $V$ be open in the metric topology, and let $x \in V$. There is some $r$ such that $B(x,r) \subseteq V$. And there is an $N$ such that $\sum_{j\ge N}\frac 2{2^j} < \frac r2$. If we choose $$U = \left(\prod_{j< N}\left(x_i-\frac r2, x_i+\frac r2\right)\cap[-1,1]\right)\times \prod_{j\ge N} [-1,1]$$
Hence $U \subseteq B(x,r) \subseteq V$. But $U$ is an open neighborhood of $x$ in the product topology. Since this can be accomplished for all $x \in V, V$ is open in the product topology.

Therefore the two topologies are in fact the same.


问:
Calculating the flux of a vector field.
Let $S$ be the unit sphere $x^2+y^2+z^2=1$ with the outward pointing normal vector n. Calculate the flux for the vector field $\mathbf{f}(\mathbf{r})=4\mathbf{r}$ through $S$.

What I have done so far:

I have rearranged the equation to get $z=\sqrt{1-x^2-y^2}$ and thus $N(x,y)=(\frac{x}{\sqrt{1-x^2-y^2}},\frac{y}{\sqrt{1-x^2-y^2}},1)$

Now to calculate the flux the equation is $\iint\limits_{S}\mathbf{f}\cdot\mathbf{n}dS$.

Hence I now have $$4\iint\limits_{S}(x,y, \sqrt{1-x^2-y^2} )\cdot (\frac{x}{\sqrt{1-x^2-y^2}},\frac{y}{\sqrt{1-x^2-y^2}},1)dS$$

$$=4\iint\limits_{S}\frac{1}{\sqrt{-x^2-y^2+1}}dxdy$$

However I don't know how to get the limits for the integral.

答:
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$\ds{\bbox[5px,#ffd]{}}$

\begin{align}
&\bbox[5px,#ffd]{\left.\int 4\vec{r}\cdot\dd\vec{S}
\,\right\vert_{\ r\ =\ 1}} =
4\int r\,\hat{r}\cdot\pars{\hat{r}\verts{\dd\vec{S}} \over r^{2}} =
4\int\overbrace{r}^{\ds{1}}\,\,
\overbrace{\hat{r}\cdot\hat{r}}^{\ds{1}}\
\overbrace{{\verts{\dd\vec{S}} \over r^{2}}}^{\ds{\dd\Omega_{\,\vec{r}}}}
\\[5mm] = &\
4\ \underbrace{\int\dd\Omega_{\,\vec{r}}}_{\ds{4\pi}}\
=\ \bbx{16\,\pi} \\ &
\end{align}

Title: Calculating the flux of a vector field.


问:
How do you write a quadratic formula with $a, b$, and $c$ being integers and its solutions being rational numbers that are not integers?
This question has me stumped and I feel like I must be missing something obvious. How do you write a quadratic equation in the standard form $ax^2+bx+c=0$ such that $a,b$ and $c$ are integers, but the solutions are rational numbers that are not integers?

答: Take two rational numbers, say $p$ and $q$.  These are the roots of the equation $(x-p)(x-q)=0$.  To get integer coefficients, just clear denominators, that is multiply both sides by the product of the denominators of $p$ and $q$.  Then multiply out the left-hand side to get the equation in the desired form.