问:
Using $\|V_1 V_1^\star - V_2 V_2^\star\|_\infty$ to bound $\|V_1 - V_2\|_\infty$
The converse question of the result I am asking about is here. Denote the operator norm by $\|\cdot \|_\infty$. That is $\|X\|_\infty = \max\{\|Xv\|:\|v\| = 1\}$ and $\|\cdot\|$ is the Euclidean 2-norm for vectors.

Let $V_1, V_2$ be (possibly rectangular) matrices that satisfy $V_i^\star V_i = I$ (where $\star$ denotes the transpose conjugate) such that

$$\|V_1 XV_1^\star - V_2X V_2^\star\|_\infty\leq \varepsilon$$

for all positive semidefinite $X$ with $\lVert X\rVert_\infty = 1$. Is it possible to then bound

$$\|V_1 - V_2\|_\infty$$

in terms of $\varepsilon$?

答:
I just want to point out another possible positive answer that people may be interested in.

Claim: suppose $V_1, V_2 \in R^{n\times r}$ where $r \leq n$ and $V_1^{\star}V_1 =V_2^{\star}V_2 = I_{r}.$ If $\|V_1V_1^{\star} - V_2V_2^{\star}\| \leq \epsilon$, then there exists a rotation matrix $H \in R^{r\times r}$ where $H^{\star}H = I_{r}$ and
$$
\|V_1 H - V_2\| \leq 2\epsilon.
$$
One possible $H$ can be explicitly constructed: $H = U_Q V_Q^{\star}$ where $V_1^{\star}V_2 = U_Q \Sigma_Q V_Q^{\star}$ is the SVD of $V_1^{\star}V_2.$

Proof:  It is sufficient to show $\|V_1 H - V_2\| \leq 2\epsilon$ for $H = U_QV_Q^{\star}.$

First, notice that $\|AV_2\| \leq \|A\| \|V_2\| \leq \|A\|$ for any $A \in R^{n\times n}$. Let $A = V_1V_1^{\star} - V_2V_2^{\star}$, since $V_2^{\star}V_2 = I_r$, we have
$$
\|V_1V_1^{\star}V_2 - V_2\| \leq \epsilon.
$$
We tend to show that $\|H - V_1^{\star}V_2\| \leq \epsilon$, then by the triangle inequality, we can complete the proof:
$$
\|V_1 H - V_2\| \leq \|V_1V_1^{\star}V_2 - V_2\| + \|V_1 (H - V_1^{\star}V_2)\| \leq \epsilon + \|V_1\| \|H-V_1^{\star}V_2\| \leq 2\epsilon.
$$

Note that in fact,
$$
\|H - V_1^{\star}V_2\| = \|U_Q V_Q^{\star} - U_Q\Sigma_Q V_Q^{\star}\| \leq \|U_Q\|\|I_r - \Sigma_Q\|\|V_Q\| = \|I_r - \Sigma_Q\|.
$$

Next, we want to bound $\|I_r - \Sigma_Q\|.$ Notice that $\|V_2^{\star}A\| \leq \|A\|$. Let $A = V_1V_1^{\star}V_2 - V_2$, we have
$$
\|V_2^{\star}V_1V_1^{\star}V_2 - V_2^{\star}V_2\| \leq \|V_1V_1^{\star}V_2 - V_2\| \leq \epsilon.
$$
Note that $V_2^{\star}V_2 = I_r$ and $V_1^{\star}V_2 = U_Q \Sigma_Q V_Q^{\star}$ again, then
$$
\|V_Q \Sigma_Q^{2} V_Q^{\star} - I_r\| \leq \epsilon.
$$
This implies that $\|\Sigma_Q^2 - I_r\| \leq \epsilon.$ Notice that for any $a \in R^{+}$,
$$
|a-1| \leq |a-1||a+1| = |a^2 - 1|.
$$
Therefore, since $\Sigma_Q$ is diagonal and non-negative (singular values), we have $\|\Sigma_Q - I_r\| \leq \|\Sigma_Q^2 - I_r\| \leq \epsilon.$ This completes the proof.

Remark: Here, $H = U_Q V_Q^{\star}$ is in fact also the optimizer of the following problem:
$$
\min_{F \in R^{r\times r}, F^{\star}F = I_{r}} \|V_1F - V_2\|_{\mathrm{F}}
$$
where $\|\cdot\|_{\mathrm{F}}$ is the Frobenius norm. See Orthogonal Procrustes problem for further reference.


问:
Is UFD an integral domain?
Let $R$ be a ring. Does part of the definition of $R$ being UFD contain that it is an integral domain, or does conditions of $R$ being a UFD forces $R$ being an integral domain?

If latter, why is it true?

答:
Being an integral domain is part of the definition of a UFD; this is what the "domain" part of "unique factorization domain" refers to. Consider for instance $\mathbb{Z}\times\mathbb{Z}$, which satisfies all the "conditions" to be a UFD except that it is not an integral domain. (To see this, note that the irreducible elements of $\mathbb{Z}\times\mathbb{Z}$ are precisely those of the form $(p,1)$ and $(1,q)$ for $p,q\in\mathbb{Z}$ prime.)

I put "conditions" in quotation marks because unique factorization into irreducibles in $\mathbb{Z}\times\mathbb{Z}$ will of course hold only for non-zero divisors, rather than all non-zero elements.

In fact, irreducible elements are themselves often defined only for integral domains, even though the definition carries over to more general cases. (The definition I use here is that an element $x$ in an arbitrary commutative ring $R$ is irreducible when $x=yz$ implies that exactly one of $y,z$ is a unit, for any $y,z\in R$. There are other reasonable definitions, too.)

ContentLicense: CC BY-SA 4.0

Title: Is UFD an integral domain?


答: The domain part of Unique factorization domain refers to the ring being an integral domain. (atleast, this is the way I understood it, however, it is the case that being an integral domain is part of the definition of a UFD)</p>

Title: Is UFD an integral domain?

Body:
Let $R$ be a ring. Does part of the definition of $R$ being UFD contain that it is an integral domain, or does conditions of $R$ being a UFD forces $R$ being an integral domain?

If latter, why is it true?


问:
How to prove fg doesn't equal to gf in permutation?
1.Let f ∈ S3 be a permutation which is not the identity. Prove that there exists g ∈ S3
such that fg ≠ gf.

2.Let n ≥ 3, and let f ∈ Sn be a permutation which is not the identity. Prove that
there exists g ∈ Sn such that fg ≠ gf.

Hey guys I am completely stuck in these two questions I'm really not sure where to start with solving it, can anyone please give me a hint? Any helps would be appreciated!

Update: Thanks everyone for giving me hint and helping me with that question. I have attempted to work on the first question and here is what I've got:
Since f ∈ S3 and it is not identity. This can conclude that there would be 5 permutations in f and 6 permutations for g as g ∈ S3.

We then test the permutations by multiple one f permutation to all g permutations. For example we take f = (321) and we multiple it with all g permutations available.
We would then be able to prove fg ≠ gf in most sets except the one where g is identity and the one that g has the same permutation as f.

Then, we can take this set to conclude that fg ≠ gf in f ∈ S3 and f is not identity and g ∈ S3 except when g is identity and the one that g has the same permutation as f.

Would this be correct at all?

答:
Case $n=3$

This is best treated with disjoint cycle notation.

Consider $(12)$; then $(12)(13)=(132)$ and $(13)(12)=(123)$.

Consider $(123)$; then $(123)(12)=(13)$ and $(12)(123)=(23)$.

Up to a renaming of the elements, these are the only needed cases.

Case $n\ge3$.

Suppose $f$ is not the identity. By a renaming of the elements, we can assume that $f(1)=2$. Take the permutation $g$ that exchanges $2$ and $3$ and leaves everything else fixed. Then
$$
g(f(1))=g(2)=3,\qquad f(g(1))=f(1)=2
$$
Therefore $gf\ne fg$.


问:
How to find joint cdf (cumulative distribution function)?
In all other examples I'd seen, f(x,y) and boundaries are given, but my problem doesn't give that.

I'd solved for pdf f(y), but don't know how t continue from there.

I know i have to do something with $$F_{X,Y}(x,y)=P(X\leq x,Y\leq y)$$ and $$f_{x,y}(x,y)=\frac{\partial ^2F_{X,Y}}{\partial x\partial y}$$, but I never learned how to do it for a problem like this.

Any thoughts on how to go about this problem? Thanks in advance.

Edit: fixed images

答: The joint density $f_{X,Y} (x,y)$ does not exist. The joint distribution funntion $F_{X,Y} (x,y)$ is given by $ F_{X,Y} (x,y)=x$ if $x \leq \frac y {1-y}$ and $ F_{X,Y} (x,y)=\frac y {1-y}$ if $x \geq \frac y {1-y}$ ($0\leq x,y \leq 1$).


问:
What is the connection between expected value (X) of a dice roll and predicting the odds of "X+0.5 or more" at least 50% of the time?
I always knew that with standard dice rolls (1d6,2d8,3d12,etc) we could average the minimum and and maximum value and get the expected value and know that you can roll at least the expected value 50% of the time, or if the value wasn't an integer, just take the next discrete value above it (like 4+ for 1d6 with expected value 3.5).

But I was playing with some custom dice pools in anydice, where you roll a pool of d10 and every 6+ is a hit and every 10 is 2 hits, and noticed something odd: if I take the expected value and add 0.5 to it, I can "predict" the odds of reaching that number rounded down.

For example:

Rolling 1d10 the expected value is 0.6, adding .5 I get 1.1, which means that I get at least 1 hit around 50% of time, since I'm a little bit over 1.

2d10 has EV of 1.2 which gets me 1.7, which means that I get at least 1 hit quite a lot (actually 75%) since I'm a lot over 1.

6d10 has EV of 3.6 which gets me 4.1, which means that I get at least 4 close to 50% of the time.

8d10 has EV of 4.8 which gets me 5.3, which means that i get at least 5 a bit over 50% of the time (actually 55%) since I'm a bit over 5.

I understand the intuition of why that works, and I know it must be related to how close the expected value is from actual discrete numbers, but I would like to know if there is some connection/explanation to that kind of prediction.

The relevant anydice for my custom dice pool: https://anydice.com/program/1efbc

答:
I hope this gets at your question, please let me know if not.

There are two separate problems at play as I understand it. There's this operation of adding 0.5 and rounding down (a.k.a. flooring) and there's an interesting fact about symmetric distributions.

First of all, the sequence of operations of adding 0.5 to a number and then rounding down is equivalent to rounding to the nearest integer for positive numbers (breaking ties by rounding up.).

Second, the distribution you're working with is symmetric. The distribution for any fair die $dN$ is uniform, and thus symmetric, and the sum of symmetrically distributed random variables is also symmetrically distributed. With symmetric distributions, the expected value coincides with the median. This means that with probability $1/2$, the outcome is greater than or equal to the expected value.

With dice, the expected value can be a rational (non-integer) number despite all the outcomes being integers. What this means in your situation is that we can round the expected value (using the `add 0.5 and floor' method) and claim that with probability one half the outcome will be at least that big.

This would be the end of my answer if we were just talking about the faces of the dice representing themselves. However, you mentioned a game where the faces get mapped to some hit numbers, $1,2,3,4,5$ are $0$ hits, $6,7,8,9$ are $1$ hit, and $10$ is 2 hits. We can think of this as a discrete random variable $X$ where $P(X=0)=5/10$, $P(X=1)=4/10$ and $P(X=2)=1/10$. This is not a symmetric distribution. The explanation for why it still works in the $kd10$ examples you simulated is that for the single case $1d10$ the expected value (i.e., mean) and the median differ by $0.1<0.5$. You can check to see what the difference between the median and the expected value is for other $k$ in your $kd10$ experiments.


问:
Integral $\int\limits^{\infty}_0\frac{\tan^{-1}t }{(1+t)^{n+1}} dt$
I'm having a good amount of trouble evaluating this: $$\int\limits^{\infty}_0\frac{\tan^{-1}(t)dt}{(1+t)^{n+1}},\ n>0$$
Here are some methods I've tried:
$$\int\limits^{\infty}_0\frac{\tan^{-1}(t)dt}{(1+t)^{n+1}}=\frac1n\int\limits^{\infty}_0\frac{dt}{(1+t^2)(1+t)^{n}}$$
using integration by parts. I then tried more integration by parts, residue theorem, and expanding into a power series but failed. I did however use partial fractions for $n=2$ to get $1/4$.
$$\int\limits^{\infty}_0\frac{\tan^{-1}(t)dt}{(1+t)^{n+1}}=\frac{\pi}{2n}-\int\limits^{\infty}_0\frac1{(1+t)^{n+1}}\int\limits^{\infty}_0\frac{\sin(x)}xe^{-xt}dxdt=\frac{\pi}{2n}-\int\limits^{\infty}_0\frac{\sin(x)}xE_{n+1}(x)e^{-x}dx$$
using the Laplace Transform of $\text{sinc}(x)$ and the $E_n$-function.
$$\int\limits^{\infty}_0\frac{\tan^{-1}(t)dt}{(1+t)^{n+1}}=\int\limits^1_0\frac{\tan^{-1}(t)dt}{(1+t)^{n+1}}+\int\limits^1_0\frac{\cot^{-1}(t)t^{n-1}dt}{(1+t)^{n+1}}=\int\limits^1_0\frac{\tan^{-1}(t)\left(1-t^{n-1}\right)dt}{(1+t)^{n+1}}+\frac{\pi}{2^{n+1}n}$$
This one I felt the best about and its also where I got that at $n=1$ the integral is $\pi/4$, but I was unable to go further.

Update: I had a couple more attempts, one of which I posted as an answer, after Claude Leibovici's idea reminded me you can do partial fractions on $\frac1{(1+x^2)(1+x)^n}$.

Notice that if we write
$$\frac1{(1+x^2)(1+x)^n}=\frac{1+x}{1+x^2}-\frac{a_0+a_1x+\dots+a_{m-1}x^{m-1}}{(1+x)^n}$$
then the coefficients $a_k$ follow the pattern
$$a_0=0,\ a_1=C_1^{n+1},\ a_2=C_2^{n+1}-a_0,\ a_3=C_3^{n+1}-a_1,\ a_4=C_4^{n+1}-a_2\dots$$
The only problem is that this sequence is always infinite and the power series does not converge on all of $[0,\infty)$, so I believe the coefficients of $1$ and $x$ in the numerator of $\frac{1+x}{1+x^2}$ could be changed to avoid this.

答:
Note that $\int\limits^{\infty}_0\frac{\tan^{-1}t}{(1+t)^{n+1}}=\frac1nI_n$, where
$$I_n=\int\limits^{\infty}_0\frac{dt}{(1+t^2)(1+t)^{n}}$$
The integrand can be decomposed iteratively as
$$A_n(t)= \frac{A_{n-1}}{1+t}=\frac{1}{(1+t^2)(1+t)^{n}}
=\frac{a_n-b_n t}{1+t^2}+ \sum_{k=1}^{n}\frac{b_{n-k+1}}{(1+t)^k}\tag1
$$
where the coefficients satisfy the iterative relationships
$$a_n=\frac{a_{n-1}-b_{n-1}}2,\>\>\>\>\> b_n=\frac{a_{n-1}+b_{n-1}}2\tag2$$
Recognize $a_0=1$,  $b_0=0$
and compare
$$\cos \frac{n\pi}4= \frac1{2^{\frac12}}\left(\cos \frac{(n-1)\pi}4-\sin\frac{(n-1)\pi}4\right)
$$
$$\sin \frac{n\pi}4= \frac1{2^{\frac12}}\left(\cos \frac{(n-1)\pi}4+\sin\frac{(n-1)\pi}4\right)
$$
with (2) to get
$$a_n=\frac1{2^{\frac n2} }\cos\frac{n\pi}4,\>\>\>\>\>
 b_n=\frac1{2^{\frac n2} }\sin\frac{n\pi}4\tag3
$$

Then, integrate $A_n(t)$ in (1) to obtain
$$I_n= \int_0^\infty A_n(t)dt =\frac{\pi a_n}2+\sum_{j=1}^{n-1}\frac{b_{j}}{n-j}
$$
Substitute the coefficients (3) to arrive at the result
$$I_n = \frac\pi{2^{\frac{n+1}2}}\cos\frac{n\pi}4
+ \sum_{j=1}^{n-1}\frac{1}{(n-j) 2^{\frac j2}}\sin\frac{j\pi}4
$$
Listed below are the first few integral values
\begin{align}
& I_1 =\frac\pi4 \\ & I_2 =\frac12\\
 & I_3 =\frac34-\frac\pi8\\
 & I_4 =\frac23-\frac\pi8\\
 & I_5 =\frac{5}{12}-\frac\pi{16}\\
\end{align}


问:
Uniform continuity of $\sin^{10}{x}$

let  $f(x) = sin^{10}{x}$, is this function uniformly continuous on $\mathbb{R}$?

I just wanna validate my answer, based on the definition of uniform continuity, for any epsilon: we're looking for a delta independent of the choice of x, such that if the distance between 2 points is less than delta, the distance between their images will be smaller than epsilon, and by the periodicity of sin(x), sin(x) = sin(x +$2\pi$), and hence for any epsilon, picking delta= 2$\pi$ does the job, is this enough for proving uniform continuity?

答: Any continuous periodic function on $\mathbb R$ is uniformly continuous.  For any $\epsilon > 0$, a $\delta$ that works for this function on the interval $[0, 2p]$ (where $p$ is the period) works for the function on $\mathbb R$.

Title: Uniform continuity of $\sin^{10}{x}$


问:
Using complex logarithms to solve equations
Could someone please just explain the formula/method for solving the complex equation $$e^{iω}=k$$ where $k∈C$.

As an example, I know that when $ω=x+iy$, $e^{2iω}=1$ has solutions $ω = n\pi$ for $n∈Z$ but I'm not sure how to show this properly. Thanks in advance.

答:
First try to write $k$ in polar form, i.e., if $k = x+iy$, then $\vert k \vert = \sqrt{x^2+y^2}$ and $\tan(\theta_k) = \dfrac{y}x \implies \theta_k = \arctan\left(\dfrac{y}x\right)$.

Now we want to find $\omega$ such that $e^{i \omega} = \vert k \vert e^{i \theta_k}$. If we let $\omega = \omega_x + i \omega_y$, where $\omega_x, \omega_y \in \mathbb{R}$, we then have
$$e^{-\omega_y} \cdot e^{i \omega_x} = \vert k \vert e^{i \theta_k}$$
Hence, $\omega_y = - \ln(\vert k \vert)$ and $\omega_x = \theta_x + 2 \pi$.

ContentLicense: CC BY-SA 3.0


问:
From Goodfellow book: why can one rescale argmax of conditional probability into an expectation?
I don't understand why the two equations below are equivalent.

\begin{align}
\boldsymbol{\theta}_{\rm ML} &= \mathop{\rm argmax}_\boldsymbol{\theta} \sum_{i=1}^{m} \log p_{\rm model}(\boldsymbol{x}^{(i)}; \boldsymbol{\theta}) \tag{5.58}\label{5.58} \\
\boldsymbol{\theta}_{\rm ML} &= \mathop{\rm argmax}_\boldsymbol{\theta} \mathbb{E}_{\mathbf{x} \sim \hat{p}_{\rm data}} \log p_{\rm model}(\boldsymbol{x}; \boldsymbol{\theta}) \tag{5.59}\label{5.59}
\end{align}

Quoted from chapter 5 of Deep Learning:

Because the $\mathop{\rm argmax}$ does not change when we rescale the cost function, we can divide by $m$ to obtain a version of the criterion that is expressed as an expectation with respect to the empirical distribution $\hat{p}_{\rm data}$ deﬁned by the training data.

答:
It just takes a bit of time to find out where the symbols are defined.  There's no computations involved in this question.
\begin{align}
\boldsymbol{\theta}_{\rm ML} &= \mathop{\rm argmax}_\boldsymbol{\theta} \sum_{i=1}^{m} \log p_{\rm model}(\boldsymbol{x}^{(i)}; \boldsymbol{\theta}) \tag{5.58}\label{558} \\
&= \mathop{\rm argmax}_\boldsymbol{\theta} \underbrace{\frac1m}_\text{const.} \sum_{i=1}^{m} \log p_{\rm model}(\boldsymbol{x}^{(i)}; \boldsymbol{\theta}) \tag{divide by $m$}\label{frac1m}
\end{align}

In \eqref{559}, $\boldsymbol{x}^{(i)}$'s are replaced by $\boldsymbol{x}$, and a new symbol $\hat{p}_{\rm data}$ is introduced, so it's better to scroll up the page to see where they are defined.

Consider a set of $m$ examples $\mathbb{X} = \{\boldsymbol{x}^{(1)}, \dots, \boldsymbol{x}^{(m)}\}$ drawn independently from the true but unknown data-generating distribution $\hat{p}_{\rm data}(\mathbf{x})$.

Observe the difference in boldface styles and their corresponding meaning.

\begin{array}{|c|c|c|}
\hline
\text{$\rm \LaTeX$ code} & \texttt{\boldsymbol{x}} & \texttt{\mathbf{x}} \\ \hline
\text{output} & \boldsymbol{x} & \mathbf{x} \\ \hline
\text{meaning} & \text{realized} & \text{theoretical} \\ \hline
\text{usage} & \boldsymbol{x}^{(i)} & \hat{p}_{\rm data}(\mathbf{x}) \\ \hline
\end{array}

Let's take a closer look at the ${\rm \small{\bf smaller}}$ part of \eqref{559}

\begin{equation}
\boldsymbol{\theta}_{\rm ML} = \mathop{\rm argmax}_\boldsymbol{\theta} \mathbb{E}_{\mathbf{x} \sim \hat{p}_{\rm data}} \log p_{\rm model}(\boldsymbol{x}; \boldsymbol{\theta}). \tag{5.59}\label{559}
\end{equation}

It reads

$${\huge \mathbf{x} \sim \hat{p}_{\rm data}}. \tag{subscript} \label{sub}$$

From the previous quoted text, it's clear that $\boldsymbol{x}^{(i)}$'s are i.i.d. with (unknown) distribution $\hat{p}_{\rm data}$.  In \eqref{558}, we calculate $\log p_{\rm model}(\boldsymbol{x}^{(i)}; \boldsymbol{\theta})$ from these $m$ realisations $\boldsymbol{x}^{(i)}$'s with $i = 1,\dots, m$, then we take the simple average in \eqref{frac1m}.  The symbol $\mathbb{E}$ captures the idea of "average" and the \eqref{sub} indicates the underlying probability distribution.


问:
shortest path not changed if one of formula is used to update all weights
Weighted Directed Graph $G$ is given. there is no negative cycle. vertexes number is $1$ to $n$. weight of edge $a$ to $b$ is $P(a,b)$. $G'$ is graph $G$ with edges will be changed according to following formula. the shortest path (not about weights of shortest path, just shortest path) does not changed !!

A) $P'(a,b)=P(a,b)+a-b$

B) $P'(a,b)=P(a,b)+b-a$

here $a$ and $b$ in sum means number (i.e: $a,b$  are the numbers assigned to those two vertices.)

how we can get the point about this strange claims ?

答:
Pick any path $C$ between two nodes $s$ and $t$ in $G$ and let $w$ be its total weight. After applying the rule:$$P'(a,b) = P(a,b)\ \pm(a-b)$$ the new weight is:
\begin{align*}
w'(s,t) &= \sum_{(u,v)\ \in\ C} P'(u,v)\\
   &= \sum_{(u,v)\ \in\ C} [P(u,v) \pm (u - v)]\\
   &= \sum_{(u,v)\ \in\ C} P(u,v)\ \pm \sum_{(u,v)\ \in\ C}(u - v)\\
   &= w(s,t) \pm [(s - u_1) + (u_1 - u_2) + \cdots + (u_{n-1} - u_n) + (u_n - t)]\\
w'(s,t) &= w(s,t) \pm (s - t)
\end{align*}
This tells us that all s-t paths in $G$ are changed by an equal amount of $s-t$ and therefore their ordering is preserved.

EDIT: As per request, I will add an example.
Assume the are 3 s-t paths in $G$ ordered like:
\begin{align*}
  &w_1(s,t) &\le &\ w_2(s,t) &\le &\ w_3(s,t) &\implies\\
  &w_1(s,t) \pm(s-t) &\le &\ w_2(s,t) \pm(s-t) &\le &\ w_3(s,t) \pm(s-t) &\implies \\
 &w'_1(s,t) &\le &\ w'_2(s,t) &\le &\ w'_3(s,t)
\end{align*}
And we see that the order remains the same.


问:
A functial equations problem over nonzero reals: $ f ( x y ) = f ( x ) f ( y ) $ and $ f \big( f ( x ) \big) = f ( x ) $

How can I find all functions $ f : \mathbb R \setminus \{ 0 \} \to \mathbb R \setminus \{ 0 \} $ such that the following two functional equations are fulfilled:

$$ f ( x y ) = f ( x ) f ( y )  \quad \text {and} \quad  f \big( f ( x ) \big) = f ( x ) $$

There are at least four such functions:

$ f ( x ) = x $

$ f ( x ) = 1 $

$ f ( x ) = | x | $

$ f ( x ) = \operatorname {sgn} ( x ) $

Also, if some $ f ( x ) $ is a solution then $ g ( x ) = \frac x { f ( x ) } $  is a solution as well.

答:
It can be shown that the only regular functions $ f : \mathbb R \setminus \{ 0 \} \to \mathbb R \setminus \{ 0 \} $ satisfying
$$ f ( x y ) = f ( x ) f ( y ) \tag 0 \label 0 $$
for all $ x , y \in \mathbb R \setminus \{ 0 \} $ and
$$ f \big( f ( x ) \big) = f ( x ) \tag 1 \label 1 $$
for all $ x \in \mathbb R \setminus \{ 0 \} $, are exactly those listed by yourself (and there are also wild solutions). To see this, it's easier to first characterize all functions $ f : ( 0 , + \infty ) \to ( 0 , + \infty ) $ satisfying \eqref{0} and \eqref{1}, which I do below.

Solutions when Restricting the Domain and Codomain to $ \mathbb R ^ + $:

The functions $ f : ( 0 , + \infty ) \to ( 0 , + \infty ) $ satisfying \eqref{0} and \eqref{1} for all $ x , y \in ( 0 , + \infty ) $, are exactly those of the form $ f ( x ) = \exp \big( A ( \log x ) \big) $ for some additive and compositionally idempotent $ A $; i.e. those $ A : \mathbb R \to \mathbb R $ that satisfy
$$ A ( x + y ) = A ( x ) + A ( y ) \tag 2 \label 2 $$
for all $ x , y \in \mathbb R $ and
$$ A \big( A ( x ) \big) = A ( x ) \tag 3 \label 3 $$
for all $ x \in \mathbb R $. It's straightforward to check that a function $ f $ of this form will satisfy \eqref{0} and \eqref{1}. To see that these are the only ones, note that for any $ f $ which is a solution, you can define $ A : \mathbb R \to \mathbb R $ with $ A ( x ) = \log \big( f ( \exp x ) \big) $, and then \eqref{0} will imply \eqref{2}, and \eqref{1} will imply \eqref{3}.

It seems that we've only rephrased the problem. But this new formulation has the additional advantage that we can use linear algebra to characterize all the solutions. Here, we look at $ \mathbb R $ as a vector space over the field $ \mathbb Q $.

First, note that assuming some regularity conditions on $ f $, it can be shown that the only solutions are $ f ( x ) = 1 $ and $ f ( x ) = x $. Any of these regularity conditions will work: differentiability at some point, continuity at some point, boundedness from either above or below on some interval, or Lebesgue measurability. These conditions will also hold for $ A $, and as $ A $ satisfies \eqref{2}, there must be a constant $ a \in \mathbb R $ such that $ A ( x ) = a x $ for all $ x \in \mathbb R $. \eqref{3} shows that $ a \in \{ 0 , 1 \} $, and that implies what was desired. See this post for more information about functions satisfying Cauchy's functional equation.

Without regularity conditions, there are other solutions as well. Characterizing all functions $ A $ satisfying \eqref{2} and \eqref{3} can be done using Hamel bases of $ \mathbb R $, which can be shown to exist using the axiom of choice. Choose a Hamel basis $ \mathcal H $ and a nonempty subset $ \mathcal I $ of $ \mathcal H $, map every member of $ \mathcal I $ to itself and every member of $ \mathcal H \setminus \mathcal I $ to an arbitrary member of the linear span of $ \mathcal I $, and finally extend this mapping linearly to a function $ A : \mathbb R \to \mathbb R $. It's then straightforward to check that \eqref{2} and \eqref{3} hold. Conversely, every $ A $ with those properties comes from a Hamel basis following the method we described. To see this, first note that using \eqref{2}, we can see that range of $ A $ is linear subspace of $ \mathbb R $. By \eqref{3}, $ A $ maps every point of this particular subspace to itself. Now, choose a basis $ \mathcal I $ for this subspace, and extend it to a basis $ \mathcal H $ for the whole $ \mathbb R $. Then range of $ A $ is exactly the linear span of $ \mathcal I $, and everything, including members of $ \mathcal H \setminus \mathcal I $, must be mapped into it.

Finding the Solutions of the Original Problem:

Suppose $ f : \mathbb R \setminus \{ 0 \} \to \mathbb R \setminus \{ 0 \} $ satisfies \eqref{0} and \eqref{1}. For any $ x \in ( 0 , + \infty ) $, we can substitute $ \sqrt x $ for both $ x $ and $ y $ in \eqref{0} to see that $ f ( x ) = f \left( \sqrt x \right) ^ 2 > 0 $. Thus if $ g $ is the restriction of $ f $ to $ ( 0 , + \infty ) $, we can see that $ g : ( 0 , + \infty ) \to ( 0 , + \infty ) $, and it satisfies equations similar to \eqref{0} and \eqref{1}, which means that it is one of the functions discussed above. Now, letting $ x = y = - 1 $ in \eqref{0} we get $ f ( - 1 ) ^ 2 = f ( 1 ) = 1 $, or equivalently $ f ( - 1 ) \in \{ - 1 , 1 \} $. Putting $ y = - 1 $ in \eqref{0},  we see that $ f ( - x ) = f ( - 1 ) f ( x ) $, which means that either $ f ( x ) = g ( | x | ) $ for all $ x \in \mathbb R \setminus \{ 0 \} $, or $ f ( x ) = ( \operatorname {sgn} x ) g ( | x | ) $ for all $ x \in \mathbb R \setminus \{ 0 \} $. Finally, it's straightforward to check that in any of these cases, with $ g $ being any of the functions discussed before, $ f $ will satisfy \eqref{0} and \eqref{1}, and therefore we've found all the solutions. Assuming regularity conditions on $ f $, $ g $ will be regular, too, and thus it must either be the constant one function or the identity function, which proves that $ f $ must be one of the functions listed by you.


答:
By basic algebra:$$\begin{align}\mathsf P(X\leqslant x, Y\leqslant y)&=\mathsf P(X\leqslant x, X/(1+X)\leqslant y)\\[1ex]&=\mathsf P(X\leqslant x, X\leqslant y/(1-y))\\[1ex]&=\mathsf P(X\leqslant \min\{x,y/(1-y)\})\\[0ex]&~~\vdots\end{align}$$

You can surely do the rest.

Title: How to find joint cdf (cumulative distribution function)?

Body:
In all other examples I'd seen, f(x,y) and boundaries are given, but my problem doesn't give that.

I'd solved for pdf f(y), but don't know how t continue from there.

I know i have to do something with $$F_{X,Y}(x,y)=P(X\leq x,Y\leq y)$$ and $$f_{x,y}(x,y)=\frac{\partial ^2F_{X,Y}}{\partial x\partial y}$$, but I never learned how to do it for a problem like this.

Any thoughts on how to go about this problem? Thanks in advance.

Edit: fixed images


问:
Prove that any group of order $945$ has at least one subgroup of order $9$
I'm trying to solve this group theory problem from my abstract algebra course. It goes like this:

Prove that any group of order 945 has at least one subgroup of order
9.

First, I noticed that $945=3^3\cdot5\cdot7$, and obviously $9=3^2$. I guess the prove will use Sylow theory, finding Sylow $3,5,7$-subgroups, but I'm not sure where to start. If i'm not wrong, there are either $1$ or $7$ Sylow $3$-subgroups in $G$, but I don't know if this is even useful in this problem. Any help will be appreciated, thanks in advance.

答:
It is sufficient to prove that if $G$ is a group of order $p^{n}$, $p$ a prime and $n\geqslant0$, then $G$ has a subgroup of order $p^{m}$ for all $0\leqslant m\leqslant n$. In fact, we prove by induction in $|G|$ a stronger version of this: If $G$ is a $p$--group of order $p^{n}$, then $G$ has a chain of normal subgroups $1=P_{0}\unlhd P_{1}\unlhd P_{2}\unlhd\cdots\unlhd P_{n}=G$ such that $|P_{i}|=p^{i}$ for all $i=0,\ldots,n$. If $|G|\leqslant p$ we have nothing to prove. If $|G|=p^{n}\geqslant p^{2}$, we assume that the result holds for $p$--groups whose order are less than $|G|=p^{n}$. Since all non-trivial finite $p$--groups have non trivial center, we consider $g\in Z(G)$ whose order is equal $p$. Then $\langle g\rangle\unlhd G$ and we can consider the group $G/\langle g\rangle$, whose order is $p^{n-1}$. By induction we can found a normal chain $$1=\langle g\rangle/\langle g\rangle=P_0/\langle g\rangle\unlhd P_{1}/\langle g\rangle \unlhd\cdots \unlhd P_{n-1}/\langle g\rangle=G/\langle g\rangle$$ such that $|P_{i}/\langle g\rangle|=p^{i}$ for all $i=0,\ldots,n-1$. It follows that for all $i=0,\ldots,n-1$ we have $|P_i|=p^{i+1}$. Writing $H_i=P_{i-1}$ for all $i=1,\ldots, n$ and putting $H_0=1$, we get the chain $1=H_0\unlhd H_{1}=P_{0}=\langle g\rangle\unlhd H_{2}=P_{1}\unlhd\cdots\unlhd H_{n}=P_{n-1}=G$, such that $|H_{0}|=|\{1\}|=1$ and for all $i=1,\ldots,n$ we have $|H_{i}|=|P_{i-1}|=p^{(i-1)+1}=p^{i}$. The claim is now proved.

Finally, since $27=3^{3}$ divides $945$, a group of order 945 has at least one subgroup of order 27 (Sylow theorem), say $H$. By the previous paragraph, $H$ has a subgroup of order 9, say $K$. Then, $K$ is a subgroup of the whole group of order 9.


问:
Cannot see why this formula is wrong
In the book of "Introduction to Algorithm 3rd Edition", p.86, there is subtitled, "Avoiding pitfalls", and it states

When

$T(n) = 2 \cdot T(\lfloor(n/2)\rfloor)+n$

, and if we want to prove $T(n)=O(n)$ by guessing $T(n) \leq cn $ and the argument of this

$T(n) \leq 2(c\lfloor(n/2)\rfloor) +n$

$\leq cn + n$

$=O(n)$     <== Wrong!

since $c$ is a constant.

I don't understand why above is wrong? Could someone explain above, please?

答:
Firstly let me note, that for $n=2^k$ and $T(n) = 2 \cdot T(\lfloor(n/2)\rfloor)+n$ we can obtain $T(n)=nT(1)+n \log_2 n$, so it is not $O(n)$.

About mistake in proof: 86p. clearly says reason as authors see it

"The error is that we have not proved the exact form of the inductive hypothesis, that is, that $T(n) \leqslant cn$. We therefore will explicitly prove that $T(n) \leqslant cn$  when we want to show that $T(n) =O(n)$."

But, as we know, mathematical induction
$$\forall P\Big(P(0) \land \forall k(P(k) \Rightarrow P(k+1)) \Rightarrow \forall n(P(n))\Big)$$

does not require explicit prove of inductive hypothesis $P(k)$, but the implication $\forall k(P(k) \Rightarrow P(k+1))$.

So to prove exact form of induction firstly we need clearly set what is $P$.

If we assume, that $P(n)$ is "$T(n) =O(n)$", then we come to question how to understand initial step of induction, which, in this case, becomes $T(1) =O(1)$. As we know in formal definition of "$T(n) =O(n)$", the "$n$" is the variable in definition under universal quantifier, it is so called bound variable. Exact formulation of sentence $f(x) \in O(g(x))$, $x \to x_0$ means, that we need two functions $f,g$ from variable $x$ and limit point $x_0$. So we can consider, that $P(n)$ is "$T \in O(n)$" and under "$n$" we understand identity function $I(n)=n$. So formally we come to "$T \in O(I)$".

If we assume, that  $P(n)$ is "$T(n) \leqslant cn$", this will fix $c$. So initial step of induction, in this case, is $T(1)\leqslant c $. Now we need to prove $P(k) \Rightarrow P(k+1)$, which is $T(k) \leqslant ck \Rightarrow T(k+1) \leqslant c(k+1)$. But using suggested in book proof we obtain only $T(k+1) \leqslant c(k+1)+(k+1)$, which, sure, is not what we wanted.

Title: Cannot see why this formula is wrong


问:
Proving the inverse of a matrix as a polynomial of matrices
Suppose $A$ is invertible $n\times n$ matrix. Show that $A^{-1}$ can be written as a polynomial of degree at most $n-1$, i.e.

$$A^{-1} = c_{n-1}A^{n-1} + \dots + \ c_{1}A + c_{0}I$$

Are there any tips on how may this proof be approached?

答:
Here is a different take. The set of polynomials in $A$ forms a finite dimensional vector space $K[A]$. Since $A$ is invertible, the map $K[A] \to K[A]$ given by $X \mapsto AX$ is injective and so is surjective. Therefore $I=AP(A)$.

To get a polynomial of degree less than $n$, write $P=QC+R$, where $C$ is the characteristic polynomial of $A$ with $R$ of degree less than $n$. Then $P(A)=R(A)$ because $C(A)=0$.


问:
What does it mean for phase lines to be qualitatively the same?
I have the following phase lines for a differential equation
$$\dfrac{dy}{dt}=y^{2}+a$$

And it was mentioned that the phase lines for $a < 0$ are qualitatively the same, and the phase lines for $a > 0$ are qualitatively the same. However, I feel confused. What does it mean for phase lines to be qualitatively the same? And why isn't $a=0$ considered to be qualitatively the same?

答:
What they mean is that the picture for any negative value of $a$ looks essentially the same as the picture for any other negative value of $a$: two equilibrium values (the solid dots), arrows going up below the lower one and above the upper one, arrow going down between the two dots.
And the picture for any positive value of $a$ looks the same as  the picture for any other positive value of $a$: no equilibrium, the arrow goes up.

As for $a=0$, there isn't any other value for that to be the same as (one equilibrium, arrows up on both sides).


问:
Is this a feasible way to show that a group $G$ is isomorphic to its opposite group $G^{op}$?
Let $G$ be a group with group operation $*$. Let $G^{op}$ be a group that shares the same base set with $G$ but the group operation $*^{'}$ is such that $a*^{'}b = b*a$. We would like to show that $G$ is isomorphic to $G^{op}$.

The standard way is to construct mapping $f: G \to G^{op}$ by $f(x)=x^{-1}$. This constitutes the isomorphism.

But I had an alternative idea which I am not sure whether it works.

Construct mapping $\varphi : G \to G^{op}$. (We assume $G$ is non-trivial of course.)Start with $\varphi(1_G)= 1 _{G^{op}}$. Choose a non-identity $g_1 \in G$, let $\varphi(g_1)=g_1$, and in general $\varphi(g_1 ^ k) = g_1 ^k, \forall k \in \mathbb Z$. Let the cyclic group generated by $g_1$ be named $G_1$.

Now we take an element $g_2 \notin G_1$. Let $\varphi(g_2^k)=g_2^k$. If an element of $G$ can be written as $g_1 ^ {k_1} g_2 ^{k_2}g_1^{k_3}....g_{1 \mbox{ or }2}^{k_\alpha}$, we map it to $ g_{1 \mbox{ or }2}^{k_\alpha}....g_1^{k_3}g_2 ^{k_2}g_1 ^ {k_1}$. This constructs the mapping on the subgroup $G_2$ generated by $g_1$ and $g_2$.

In general, if we have constructed the group $G_\gamma$ generated by a set of generators index by set $\Gamma$ $g_1, ... g_\gamma$, we introduce an element $g_{\gamma +1}$ such that $g_{\gamma+1} \notin G_{\gamma}$, we map the element $g_{i_1}^{k_1}g_{i_2}^{k_2} .... g_{i_\alpha}^{k_\alpha}$ to $g_{i_\alpha}^{k_\alpha} ... g_{i_2}^{k_2}g_{i_1}^{k_1}$ (note that $\alpha$ is finite). We do some sort of transfinite induction (I suppose?) to finish this off, and every element in $G$ can be represented as a word from a finite alphabet drawn from the set of generators. Then I think we should have constructed an anti-automorphism. Does this work?

Thank you.

Wilson

答:
Take an isomorphism of $G$ onto $G^{op}$. Compose it with the isomorphism $x\mapsto x^{-1}$. You get an automorphism of $G$. All isomorphisms of $G$ onto $G^{op}$ are obtained by the reverse process.

Apply this remark to your candidate. You get an automorphism $\sigma$ of $G$ which sends a set of generators to their inverses. In particular, you must have $\sigma^2=1$. Also, $\sigma$ must induce $-1$ on the maximal abelian quotient of $G$, hence act by $(-1)^n$ on the $n$-th term of the graded Lie algebra associated to the lower central series. This obviously puts strong constraints on $G$: for example, if it is nonabelian and you take its quotient by $[G,[G,G]]$, you get a central extension which is split away from $2$.

On the other hand, there are obviously examples beyond abelian groups, e.g. free groups (or quotients of such by any characteristic subgroup).

It's interesting to know whether there are examples within finite simple groups.


问:
Elementary set theory problem: proof of equivalence
Let $A, B, C$ be arbitrary sets. Prove that:
$$(A\backslash B)\backslash C = A\backslash(B\backslash C) \Longleftrightarrow A\cap C = \emptyset$$

The left hand side of the equivalence:

$(A\backslash B)\backslash C = A\backslash(B\backslash C)$

is defined by the following logical expression

$\begin{align}
x\in (A\backslash B)\land x\notin C
&\Leftrightarrow x\in A \land \lnot(x\in B \land x\notin C)\\
&\Leftrightarrow x\in A\land (x\notin B \lor x\in C)\\
&\Leftrightarrow (x\in A \land x\notin B)\lor(x\in A \land x\in  C)\\
&\Leftrightarrow x\in(A\backslash B)\lor x\in (A\cap C)
\end{align}$

So I could rewrite the LHS as the following equivalence:

$x\in (A\backslash B)\land x\notin C \Leftrightarrow x\in(A\backslash B)\lor x\in (A\cap C)$

The right hand side of the equivalence:

$A\cap C = \emptyset$

is analogically defined by the expression:

$x\in A \Rightarrow x\notin C$

The whole problem, rewritten:
So the whole problem narrows down to proving:
$$\Big(x\in (A\backslash B)\land x\notin C \Leftrightarrow x\in(A\backslash B)\lor x\in (A\cap C) \Big)\stackrel{?}{\equiv} \Big(x\in A \Rightarrow x\notin C \Big)$$

Best further approach:
My question is generally: What would be the best and most comprehensive further approach as of this point?

rigorous proof based on boolean algebra with the given result and equivalent transformations;

splitting the proof into two directions: "$\Longrightarrow$" and "$\Longleftarrow$"

proof by contradiction (using terms like "suppose", "for an arbitrary" etc.)

other options?

I know these are all the same, but I'd love to keep going "the rigorous" way with equivalent transformations in the logical expressions. What would your advice be? Thanks in advance!

P.S. I'm also open for corrections of my notation (especially the $\equiv$ symbol, am I using that right?)

答:
Here is my "rigorous" computational way, although I can agree is by far not optimal or that intuitive...

Let's define logical variables $a \equiv x \in A, b\equiv x\in B, c\equiv x\in C$.
Then we start from the LHS and want to arrive at the RHS.

We have
$$\begin{align}
&(a\land \overline{b}\land\overline{c}) \Leftrightarrow a\land(\overline{b}\lor c)\\
\equiv&\lnot\left[(a\land\overline{b}\land\overline{c})\lor\left(a\land(\overline{b}\lor c)\right)\right]\lor\left[(a\land\overline{b}\land\overline{c})\land\left(a\land(\overline{b}\lor c)\right)\right] &L\Leftrightarrow R \equiv \lnot(L\lor R)\lor(L\land R)\\
\equiv&\lnot\left[a\land(\overline{b} \lor c)\right]\lor\left[a\land \overline{b}\land\overline{c}\right] &(a_1\land a_2...\land a_n)\lor a_i \equiv a_i\\
\equiv&\lnot\left[a\land(\overline{b} \lor c)\right]\lor\lnot\left[\overline{a}\lor b\lor c\right] & (a_1\land a_2\land ...\land a_n) \equiv \lnot(a_1\lor a_2\lor ... \lor a_n)\\
\equiv&\lnot\left[a\land(\overline{b}\lor c)\land\left(\overline{a}\lor b\lor c\right)\right] & \text{de Morgan's law, same as above}\\
\equiv&\lnot\left[a\land(\overline{b}\lor c)\land\left(b\lor c\right)\right] &\text{distributive laws}\\
\equiv&\lnot\left[a\land c\right] &(\overline{b}\lor c)\land(b\lor c) \equiv c\\
\equiv&\overline{a}\lor\overline{c}\\
\equiv&a \Rightarrow \overline{c}
\end{align}$$

Thus the equivalence is proven. I don't know, I really find it satisfying working that way! I've maybe just skipped too much between the second and the third row, but all the transformations all really just distributive laws and absorption laws at play.


问:
Solving ANF equations
Can anyone suggest a method of solving a system of boolean equations in ANF form? Boolean equations in ANF form (Algebraic Normal Form ) are equations of the form of xor of products of boolean variables. For example (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)$)=1$</p>

答:
What about one variable at a time?

Let Z be your equation in ANF form, made up of variables A,B,C, etc.

Now convert Z AND A back into ANF form. If you end up with the same equation as Z then A must be true. Otherwise try converting Z AND NOT A into ANF to see if A is false.

Lets try your example:

let Z = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$))

lets try (Z and $x_1$) first

(Z and $x_1$) = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)) and $x_1$

(Z and $x_1$) = ($x_1$ and $x_2$) xor ($x_1$ and $x_2$ and $x_3$) xor ($x_1$ and $x_3$)

(Z and $x_1$) does not equal Z, so $x_1$ could either be false or have more than one solution.

now lets try (Z and not $x_1$)

(Z and not $x_1$) = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)) and (not $x_1$)

(Z and not $x_1$) = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)) and (true xor $x_1$)

(Z and not $x_1$) = ($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$) xor ($x_1$ and $x_2$) xor ($x_1$ and $x_2$ and $x_3$) xor ($x_1$ and $x_3$)

(Z and not $x_1$) = ($x_2$ and $x_3$) xor ($x_1$ and $x_2$ and $x_3$)

(Z and not $x_1$) also does not equal Z. So it is likely there is more than 1 solution if there are any solutions. So to grab just one possible solution, pick any value for $x_1$ and simplify.

lets try $x_1$ = false

Z = ((false and $x_2$) xor ($x_2$ and $x_3$) xor (false and $x_3$))

Z = false xor ($x_2$ and $x_3$) xor false

Z = $x_2$ and $x_3$

leading to $x_2$ = true and $x_3$ = true, if $x_1$ = false

so ($x_1$, $x_2$, $x_3$) = (false, true, true) is one possible solution. And by backtracking and choosing a different substitution for $x_1$ you can get the other solution(s).

Now let $x_1$ = true to grab the other solutions.

Z = ((true and $x_2$) xor ($x_2$ and $x_3$) xor (true and $x_3$))

Z = $x_2$ xor ($x_2$ and $x_3$) xor $x_3$

Z = $x_2$ xor $x_3$ xor ($x_2$ and $x_3$)

Z = $x_2$ or $x_3$

leading to ($x_2$,$x_3$) = (false,true), (true,false) or (true,true), if $x_1$ = true.

So all the solutions to ($x_1$, $x_2$, $x_3$) are (false, true, true), (true, false, true), (true, true, false) and (true, true, true).

Title: Solving ANF equations


问:
Prove there is only 3 non transitive relations on {a,b}
I know the 3 relations that aren't transitive

$${A=\{(a,b) , (b,a)\}\\
B=\{(a,b) , (b,a) , (a,a)\}\\
C=\{(a,b) , (b,a) , (b,b)\}}$$

I can't use brute force as my proof and I'm stuck

答:
The first relation is not transitive.    $(a,b)\in A, (b,a)\in A$ but $(a,a)\notin A$, so we have a counter example for that.

Now find the counter examples for relations $B$ and $C$?

What do you notice about these counter examples?


问:
What's the intuition on normal subgroups/ideals 'factoring' out properties in quotient groups/rings?
I think 'factoring' out here may be a bit of a misnomer; I mean the qualitative 'removal' of certain unwanted properties. For example, consider the Abelian group $G$, and the subgroup $H$ that is all elements of finite order in $G$. Then $G/H$ has no element (other than identity) of finite order. In some sense selecting this particular subgroup $H$, which consisted of elements of finite order, leads to a quotient group of elements having infinite order.

That was the example given in my book, and I followed it fine and it makes sense in this particular example. There were a couple of others which also made sense, in each particular case. However I cannot quite grasp the intuition behind this in general. I don't see why a normal subgroup or ideal having a particular property tends to mean the quotient group/ring will not.

My book implies this is of great practical importance for the construction of homomorphic images with properties we want, so I am trying to figure out why this is the case? I can see in individual cases, when given proof, why the results hold. But I have zero intuition for why any general property can effectively be eliminated by carefully choosing the subgroup or ideal to have said property?

答:
'Removing elements' is not the best intuition for quotients, rather to 'make some of them equal', i.e. informally we can think it as keeping the same elements but modifying the equality rules.

We can quotient out a set by any equivalence relation (reflexivity, symmetry and transitivity are just the main - and characteristic - properties of equality).

A prominent example is the high school definition of vectors on the plane: they are directed segments, but two such are considered equal when they form the opposite sides of a parallel heading towards the same direction.

Another example in every day life is the time. We simply consider 23:00 = 11:00pm. They are equal modulo 12.

If we have some algebraic structure (i.e. group or ring), we want the equality relation to keep the operations as well, so we need an equivalence relation that also preserves the operations, those are called congruence relations.

In a group, a congruence relation is determined by the equivalence class $N$ of the identity element $1$, and this is always a normal subgroup:

In the quotient group, with the above informalism, we will have $1=1$ so $1\in N$;

If $x,y\in N$m i.e. if $x=1$ and $y=1$ then $xy=1$ so $xy\in N$ and for any $g$ if $x=1$ then $gx=g$ and $gxg^{-1}=gg^{-1}=1$ so $gxg^{-1}\in N$.

This can be made precise in many ways, e.g. using $[\cdot]$ brackets or pasting $N$ to denote equivalence classes [=cosets] in $G$ instead of the same elements with a new equality.

Another way is using homomorphisms: if $x\in N$, we don't directly say $x=1$ (or correctly, $[x]=[1]$ or $xN=N$) but that $x$ will be equal to $1$ somewhere, i.e. $f(x)=f(1)=1$ for some homomorphism $f:G\to H$.

Indeed, a subset $N$ of a group $G$ is a normal subgroup if and only if it is the kernel of a homomorphism $f:G\to H$.

[Note that the notion of kernel can be generalized to sets or arbitrary algebraic structures simply by taking the congruence relation $g\sim g'\iff f(g)=f(g')$.]

Rewriting the above, $f(x)=1$ means that $x\in N$,

Clearly we have $f(1)=1$ so $1\in N$; if $f(x)=f(y)=1$ then $f(xy)=1$; and if $f(x)=1$ then $f(gxg^{-1})=f(g)f(x)f(g)^{-1}=f(g)f(g)^{-1}=1$.

The converse of the theorem follows by the quotient construction $G/N$, which defines a group operation on the set of cosets.

The congruence relations of rings are determined by the equivalence class of $0$, and that is always an ideal.

That's why we quotient out by normal subgroups and ideals.


问:
Algorithm for tricoloring a knot
I have just started studying knot theory, and read about tricolorability of knots. Two knots are equivalent iff they are tricolorable. While trying to color a variety of complex knots, I tried a backtracking approach of starting with an arbitrary arc to color, coloring upto a point where there is no possibility of doing a valid coloring and then backtracking to the last point where I made a choice of color to continue with a different choice of color from there.
I wished to know if there is a standard algorithm for coloring knots.

答:
For Fox $n$-colorings in general, one colors the arcs with elements from $\{0,1,\dots,n-1\}$ constrained to a certain linear equation at each crossing.  For $3$-colorings, the equation is

The reduction is using the fact that $1\equiv -2\pmod{3}$. One can check that $a+b+c\equiv 0\pmod{3}$ means that either all three variables have the same value or all have different values.

For example, here is a figure-eight knot along with the associated linear system and its matrix:

I asked Mathematica to compute the nullspace of this matrix modulo $3$ with

```<code>NullSpace[{{1, 0, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {0, 1, 1, 1}}, Modulus -> 3]
</code>```

and it gave back {{1,1,1,1}}, signifying that the only tricolorings are trivial.  Therefore the figure-eight knot is not nontrivially tricolorable.

On the other hand, here is the trefoil knot:

According to Mathematica,

```<code>In[108]:= NullSpace[{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}, Modulus -> 3]

Out[108]= {{2, 0, 1}, {2, 1, 0}}
</code>```

Thus the space of tricolorings is two-dimesional.  One nontrivial one is given by $a=2$, $b=0$, and $c=1$.

(To calculate the nullspace yourself, you do Gaussian elimination modulo $3$.  Then you can read off a basis for the nullspace like you would usually do in linear algebra.  It's just all done modulo $3$.)

Something I didn't mention with the above systems is that, because it turns out tricolorings are linear, you can subtract off the trivial component, letting you assume one of the variables is $0$.  You can cross off any column of the matrix to effect this assumption.  Secondly, there is a linear dependence on the rows, so you can cross off any row.  Hence, given an $n$-crossing knot, you can create an $(n-1)\times(n-1)$ matrix through this process.  The nonzero elements in the nullspace of this matrix is exactly the collection of nontrivial tricolorings.  (In one of my comments on the question, this is the matrix whose determinant is divisible by $3$ iff the knot is tricolorable.)

Title: Algorithm for tricoloring a knot

Body:
For Fox $n$-colorings in general, one colors the arcs with elements from $\{0,1,\dots,n-1\}$ constrained to a certain linear equation at each crossing.  For $3$-colorings, the equation is

The reduction is using the fact that $1\equiv -2\pmod{3}$. One can check that $a+b+c\equiv 0\pmod{3}$ means that either all three variables have the same value or all have different values.

For example, here is a figure-eight knot along with the associated linear system and its matrix:

I asked Mathematica to compute the nullspace of this matrix modulo $3$ with

NullSpace[{{1, 0, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {0, 1, 1, 1}}, Modulus -> 3]

and it gave back {{1,1,1,1}}, signifying that the only tricolorings are trivial.  Therefore the figure-eight knot is not nontrivially tricolorable.

On the other hand, here is the trefoil knot:

According to Mathematica,

In[108]:= NullSpace[{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}, Modulus -> 3]

Out[108]= {{2, 0, 1}, {2, 1, 0}}

Thus the space of tricolorings is two-dimesional.  One nontrivial one is given by $a=2$, $b=0$, and $c=1$.

(To calculate the nullspace yourself, you do Gaussian elimination modulo $3$.  Then you can read off a basis for the nullspace like you would usually do in linear algebra.  It's just all done modulo $3$.)

Something I didn't mention with the above systems is that, because it turns out tricolorings are linear, you can subtract off the trivial component, letting you assume one of the variables is $0$.  You can cross off any column of the matrix to effect this assumption.  Secondly, there is a linear dependence on the rows, so you can cross off any row.  Hence, given an $n$-crossing knot, you can create an $(n-1)\times(n-1)$ matrix through this process.  The nonzero elements in the nullspace of this matrix is exactly the collection of nontrivial tricolorings.  (In one of my comments on the question, this is the matrix whose determinant is divisible by $3$ iff the knot is tricolorable.)


问:
Given A and Find B such that $\frac{\lVert A_n-B\rVert_\infty}{\lVert A_n \rVert_\infty} - \frac{1}{K(A_n)}$ < $\frac{1}{n^2}$
$A_n=\begin{bmatrix}
        1 & 2  \\
        2 & 4+1/n^2\\
        \end{bmatrix}$

How can we find  singular B such

$\frac{\lVert A_n-B\rVert_\infty}{\lVert A_n \rVert_\infty} - \frac{1}{K(A_n)}$ <  $\frac{1}{n^2}$

$A_n^{-1}=\begin{bmatrix}
        4n^2+1 & -2n^2  \\
        -2n^2 & n^2\\
        \end{bmatrix}$

Then, we can find $K(A_n)$. But then I don't know what to do. (K refer condition number.)

Body:
The condition number $\kappa(A) = \| A \| \| A^{-1}\| $ can take any norm. So I'll assume you're also using  $\|\cdot \|_{\infty}$.

First we have $ \frac{\| A_{n} - B \|_{\infty} }{\| A_{n} \|_{\infty} } - \frac{1}{\kappa(A_{n})} = \frac{\| A_{n} - B \|_{\infty} }{\| A_{n} \|_{\infty} } - \frac{1}{\|A_{n}\|_{\infty} \| A_{n}^{-1} \|_{\infty}}$

Let's find $\| A_{n}\|_{\infty} $ and $\| A_{n}^{-1}\|_{\infty} $

$ \|A_{n}\|_{\infty} = \max \{3 , 6 + \frac{1}{n^{2}}  \} = 6 + \frac{1}{n^{2}}$

Now, first $A^{-1} =  \begin{bmatrix} 4n^{2} + 1 & -2n^{2} \\ -2n^{2} & n^{2} \end{bmatrix}$.

Now, we get $ \|A_{n}^{-1}\|_{\infty} = \max \{ 6n^{2}+1, 3n^2 \} = 6n^{2}+1 $.

Now,  we have

$ \frac{\| A_{n} - B \|_{\infty} }{\| A_{n} \|_{\infty} } < \frac{1}{\kappa(A_{n})} + \frac{1}{n^2}  $

Get a common denominator

$ \frac{\| A_{n} - B \|_{\infty} }{\| A_{n} \|_{\infty} } <\frac{n^{2}+\kappa(A_{n})}{n^{2} \kappa(A_{n})} $

Now multiply by $\kappa(A_{n})$

$\| A_{n} - B \|_{\infty}   <\frac{\| A_{n} \|_{\infty} ( n^{2}+\kappa(A_{n})) }{n^{2} \kappa(A_{n})} $

Replace $\kappa(A_{n}) = \|A_{n}\|_{\infty} \| A_{n}^{-1} \|_{\infty}$

$\| A_{n} - B \|_{\infty}   <\frac{\| A_{n} \|_{\infty} ( n^{2}+\kappa(A_{n})) }{n^{2} \|A_{n}\|_{\infty} \| A_{n}^{-1} \|_{\infty} } $

Now cancel $ \|A_{n} \|_{\infty}$

$\| A_{n} - B \|_{\infty}   <\frac{n^{2}+\kappa(A_{n}) }{n^{2} \| A_{n}^{-1} \|_{\infty} } $

Replace $\kappa(A_{n}) = \|A_{n}\|_{\infty} \| A_{n}^{-1} \|_{\infty}$

$\| A_{n} - B \|_{\infty}   <\frac{n^{2}+\|A_{n}\|_{\infty} \| A_{n}^{-1} \|_{\infty} }{n^{2} \| A_{n}^{-1} \|_{\infty} }  = \frac{\| A_{n}\|_{\infty} }{n^{2}} + \frac{1}{\| A_{n}^{-1} \|_{\infty} }$

Now substitute in some things

$ = \frac{ 6  + \frac{1}{n^2} }{n^{2}} + \frac{1}{6n^{2}+1}  =\frac{37n^{4}+12n^{2}+1}{n^{4}(6n^{2}+1)}$

And suppose that $ B = \begin{bmatrix} a & b \\ c &  d\end{bmatrix} $ then we will find that $ \| A_{n} - B\|_{\infty} = \max \{ |1-a| + |2-b| , |2-c| + |4+\frac{1}{n^{2}}  -d| \} $

and

$ \max \{ |1-a| + |2-b| , |2-c| + |4+\frac{1}{n^{2}}  -d| \}  < \frac{37n^{4}+12n^{2}+1}{n^{4}(6n^{2}+1)}$

Now

$ B = \begin{bmatrix}  1 &  2 \\ 2 & 4 \end{bmatrix}$

This matrix is singular

It gives us

$ \max \{ 0 , \frac{1}{n^{2}} \} = \frac{1}{n^{2}}  < \frac{37n^{4}+12n^{2}+1}{n^{4}(6n^{2}+1)}$


问:
$a\in \mathbb{N}$, $p$ prime, $a<p$ prove that $a\mid p+1\iff\exists\, b,c\in\Bbb N:\dfrac{a}{p}=\dfrac{1}{b}+\dfrac{1}{c}$
$a\in \mathbb{N}$, $p$ prime, $a<p$ prove that $a\mid p+1\iff \exists\, b,c\in\Bbb N:\dfrac{a}{p}=\dfrac{1}{b}+\dfrac{1}{c}$

my attempt:

$a\cdot b \cdot c=p\cdot(b+c)$ .

i dont know how to use the given

$a\mid p+1$

答:
We have $ a \mid p+1$ so there is $\lambda$ such that $\lambda a =p+1$. Now divide by $ \lambda p$ & we have
\begin{eqnarray*}
\frac{a}{p} = \frac{1}{\lambda} + \frac{1}{p \lambda}.
\end{eqnarray*}

The other implication: We have $ \dfrac{a}{p}=\dfrac{1}{b}+\dfrac{1}{c}$ or $abc=p(b+c)$.Multiply this by $a$ & rearrange to $(ab-p)(ac-p)=p^2$.

This gives three possiblities $ab-p=1$ or $ac-p=1$ & the result follows.
Or $ab-p=p,ac-p=p$ which gives $ab=ac=2p$ so $a=1$ or $a=2$ and again the result follows.


问:
with which values parameter 'a' series converges and with which diverges
Which values for $a$ will make series convergent or divergent?

$$
\sum_{k=1}^{\infty}\frac{1}{(2k+1)\ln^a(2k+1)}
$$

I have been following this tutorial
http://tutorial.math.lamar.edu/Classes/CalcII/SeriesIntro.aspx
  But now I'm stuck. I haven't seen examples as this one above. There is additional parameter $a$ which values I have to find myself. Could anyone suggest me how should I work this time then?
  Maybe I just choose randomly some values for $a$? Like $a=-2$, $0$ and $2$?

答:
This nature of this series is ruled by the so-called Bertrand criterion, which tells you that $\displaystyle \sum_{n \geqslant 2} \frac{1}{n^{\alpha} \ln^{\beta}(n)}$ converges if and only if $\alpha >1$ or $\alpha=1$ and $\beta >1$.

More precisely, in your case, the general term is positive, and equivalent to $\displaystyle\frac{\rm cte}{n \,  \ln^a(n)}$, so the series converges iff $a>1$.


答:
When $G$ is nonabelian, its elements of finite order are not a subgroup in general (if $g$ and $h$ have finite order, $gh$ could have infinite order).  When $G$ is abelian and $H$ is its subgroup of elements of finite order, the fact that $G/H$ has no nontrivial elements of finite order requires an argument.  To appreciate this, if a group $G$ has a center $Z$, which is always a normal subgroup, the quotient group $G/Z$ might have a nontrivial center.  Passing from $G$ to $G/Z$ does not have to "kill the center" in $G/Z$ because the center of $G/Z$ is represented by elements of $G$ that commute with everything in $G$ "up to multiplication by elements of $Z$", so when $Z$ is killed off, you can be left with nontrivial elements of $G/Z$ that now commute with everything in $G/Z$.

Example: $G = D_4 = \langle r,s\rangle$ where $r^4 = 1$, $s^2 = 1$, and $srs^{-1} = r^{-1}$.  The center of $G$ is $Z = \{1,r^2\}$ and $G/Z$ is a group of order 4, which is abelian (all groups of order 4 are abelian) and therefore $G/Z$ doesn't have a trivial center: the whole quotient group $G/Z$ is its center.  What is going on here is that when you pass from $G$ to $G/Z$, two elements $g$ and $h$ in $G$ that may not commute in $G$ could commute in $G/Z$ because in $G$ they only commute "up to an element in the center": $hg = zgh$ for some nontrivial $z$ in $Z$. Then $g$ and $h$ do not commute in $G$ but their images in $G/Z$ do commute in $G/Z$.

Title: What's the intuition on normal subgroups/ideals 'factoring' out properties in quotient groups/rings?

Body:
I think 'factoring' out here may be a bit of a misnomer; I mean the qualitative 'removal' of certain unwanted properties. For example, consider the Abelian group $G$, and the subgroup $H$ that is all elements of finite order in $G$. Then $G/H$ has no element (other than identity) of finite order. In some sense selecting this particular subgroup $H$, which consisted of elements of finite order, leads to a quotient group of elements having infinite order.

That was the example given in my book, and I followed it fine and it makes sense in this particular example. There were a couple of others which also made sense, in each particular case. However I cannot quite grasp the intuition behind this in general. I don't see why a normal subgroup or ideal having a particular property tends to mean the quotient group/ring will not.

My book implies this is of great practical importance for the construction of homomorphic images with properties we want, so I am trying to figure out why this is the case? I can see in individual cases, when given proof, why the results hold. But I have zero intuition for why any general property can effectively be eliminated by carefully choosing the subgroup or ideal to have said property?


问:
Degree sequence multigraph without loop
I am trying to prove the following

$d_n$ is a degree-sequence of the multigraph  $G$ (without loops) if and only if $\sum_{i=1}^{n}{d_i}$ is even and $d_1 \le\sum_{i=2}^{n}{d_i}$

I have no problems showing the first part.

By the "handshake"-lemma $\sum_{i=1}^{n}{d_i}=2e$ where $e$ is the number of edges in $G$

$$d_1 \le e $$

$$d_1\le \frac{\sum_{i=1}^{n}{d_i}}{2}$$

Hence $d_1 \le \sum_{i=2}^{n}{d_i}$

However, I don't know how to show the other part. Would appreciate some tips or hints

答:
Here's the construction I've found. As far as I know, the result was first proven by Hakimi in 1962 (check the article On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph).

Theorem. Let $d_1\leq...\leq d_n$ be a sequence of natural numbers. This sequence can be realized by some multigraph iff $S=d_1+...+d_n$ is even and $d_n\leq S/2$.

Proof. The necessary part follows from the handshaking lemma. Let's prove that the conditions are also sufficient.

If $n=1$, the only possibility is $d_1=0$. This case is trivially realizable, thus suppose $n\geq2$. Consider $n$ vertices $v_1,...,v_n$. Connect $v_1$ and $v_2$ with $d_1$ edges, $v_2$ and $v_3$ with $d_2-d_1$ edges, $v_3$ and $v_4$ with $d_1-(d_2-d_1)$ edges, etc. You'll get a graph $G$ of the following form (with the degrees subscribed):

$G$ is almost corresponding to our sequence: we have to add $d_n-x$ new edges to $v_n$ to complete the construction. This addition is possible if $G'=G-v_n$ contains enough edges, then you may cut some edge from $G'$ in two parts connecting these parts with $v_n$. The procedure will obviously preserve the degrees of $v_1,...,v_{n-1}$ and will increase $d(v_n)$ by $2$:

Now, we have to prove that $G'$ contains at least $(d_n-x)/2$ edges (it's easy to see that $d_n-x$ is even). If this is not the case, then $|E(G')|=(d_1+...+d_{n-1}-x)/2<(d_n-x)/2$. This implies $d_1+...+d_{n-1}<d_n$ and $S/2<d_n$ giving us a contradiction $\blacksquare$

Let's show how the described method works applied to $2,4,6,8$:

Title: Degree sequence multigraph without loop


答:
Here is an attempt, I am not sure if this would be considered brute force or not though.

First of all, a relation is just an element of the power set of {a,b}$^2$ so there are 16 relations in total to consider. (15 if we dont consider the empty relation to be a valid relation) The equality relation is transitive, and any relation which contains only 1 pair of elements will be trivially transitive. Also the empty relation is trivially transitive, so either way its out. There are 4 relations with only a single element, so we are now down to 10 possible relations.

We can see that any relation which contains both {a,a} and {b,b} will be transitive, since for a relation $R$ to be non transitive, you need some $x,y,z$ such that $(x,y)\in R$, $(y,z)\in R$ and $(x,z)\notin R$. Since we are considering a domain with only 2 elements, $x=z$ or $y=z$ must be true. In the first case, we get $(x,x)\notin R$ and in the second case we get $(y,y)\notin R$. which means $R$ cannot contain both pairs.

There are 4 relations which contain both pairs, but one of them is the identity relation which we already removed, so we can remove 3 more, to get 7 relations left.

there are 4 relations which contain neither $(a,a)$ nor $(b,b)$, but only 1 of them contains at least 2 elements, so that is the only possible one that can be transitive.

There are 6 relations which contain either $(a,a)$ or $(b,b)$ but not both, as well as at least 1 other element. WLOG we can consider the relation which contains $(a,a)$ and not $(b,b)$. However, such a relation will be transitive if it contains only 1 other element. so our remaining relation must contain both other elements. ie they must be {$(a,a),(a,b),(b,a)$} and {$(b,b),(a,b),(b,a)$}.

So we get 3 relations in total.

If you think this is still to brute force, then you can prove there are only 3 possible relations by proving the following things.
1: a non transitive relation must contain more than 1 element.
2: a non transitive relation must contain at least 2 elements of the form $(x,y)$ with $x\neq y$
3: a non transitive relation on a set of 2 variables, cannot contain both pairs $(a,a)$ and $(b,b)$.
these 3 facts should give you only 3 possible relations, without it looking like you checked the other 13 possibilities.

Title: Prove there is only 3 non transitive relations on {a,b}

Body:
I know the 3 relations that aren't transitive

$${A=\{(a,b) , (b,a)\}\\
B=\{(a,b) , (b,a) , (a,a)\}\\
C=\{(a,b) , (b,a) , (b,b)\}}$$

I can't use brute force as my proof and I'm stuck


问:
Proof of relation for open superset
Currently reading a textbook on measure theory. To complete a proof the author uses (without proof) the relation:
$$\bigcup_{n=1}^{\infty}A_n \setminus \bigcup_{n=1}^{\infty}E_n \subset \bigcup_{n=1}^{\infty}(A_n \setminus E_n)$$

where $E_n\subset A_n$ and $A_n$ is open for every $n$. How can I prove this?

答:
Direct element-chasing:

If $x \in \cup_{n=1}^\infty A_n \setminus \cup_{n=1}^\infty E_n$, then $x \in \cup_{n=1}^\infty A_n$ and $x \notin \cup_{n=1}^\infty E_n$. So there is $N$ such that $x \in A_N$ and then of course $x \notin E_N$. Thus $x \in A_N \setminus E_N \subset \cup_{n=1}^\infty \left( A_n \setminus E_n \right)$.

Title: Proof of relation for open superset


问:
Can this be proved using Combinatorics or generating functions?
What is the proof for this identity?

$\displaystyle\sum_{r=0}^{n}\binom{n}{r}\binom{m+r}{n}\ = \displaystyle\sum_{r=0}^{n}\binom{n}{r}\binom{m}{r}2^{r}$

I thought of changing $r$ to $n-r$ on left and right both. Then, I thought of building a set with atleast $n$ elements and atmost $2n$ elements with atmost $n$ elements from $m$ element set, and we can do this on LHS by choosing $n-r$ elements from n and out of remaining $r+m$ elements we can choose n more elements. On RHS, we can again choose $n-r$ elements from $n$ and $r$ elements from $m$, then remaining $r$ elements from n element set have 2 choices each. But I think it has a flaw. Can someone please help? If my proof is not correct, please suggest a combinatorial or a generating function proof.

答:
$$
\eqalign{
  & \sum\limits_{\left( {0\, \le } \right)\,r\,\left( { \le \,n} \right)} {\left( \matrix{
  n \cr
  r \cr}  \right)\left( \matrix{
  m + r \cr
  n \cr}  \right)}  = \sum\limits_{\left( {0\, \le } \right)\,r\,\left( { \le \,n} \right)} {\left( \matrix{
  n \cr
  r \cr}  \right)\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \matrix{
  r \cr
  k \cr}  \right)\left( \matrix{
  m \cr
  n - k \cr}  \right)} }  =   \cr
  &  = \sum\limits_k {\sum\limits_r {\left( \matrix{
  m \cr
  n - k \cr}  \right)\left( \matrix{
  n \cr
  r \cr}  \right)\left( \matrix{
  r \cr
  k \cr}  \right)} }  = \sum\limits_k {\sum\limits_r {\left( \matrix{
  m \cr
  n - k \cr}  \right)\left( \matrix{
  n \cr
  k \cr}  \right)\left( \matrix{
  n - k \cr
  r - k \cr}  \right)} }  =   \cr
  &  = \sum\limits_k {\sum\limits_r {\left( \matrix{
  m \cr
  n - k \cr}  \right)\left( \matrix{
  n \cr
  k \cr}  \right)\left( \matrix{
  n - k \cr
  n - r \cr}  \right)} }  = \sum\limits_k {\left( \matrix{
  m \cr
  n - k \cr}  \right)\left( \matrix{
  n \cr
  k \cr}  \right)2^{n - k} }  =   \cr
  &  = \sum\limits_k {\left( \matrix{
  m \cr
  k \cr}  \right)\left( \matrix{
  n \cr
  k \cr}  \right)2^k }  \cr}
$$

Note that the sum bounds put in parenthesis is to indicate that they can be omitted since they are implicit in the binomial(s), i.e. the binomials are null outside of the bounds.

Then the steps are:

expand 2nd b. as Vandermonde's Convolution;

group and invert the summation indices;

apply the "trinomial revision" identity on last two b.
$$
\eqalign{
  & \left( \matrix{
  n \cr
  r \cr}  \right)\left( \matrix{
  r \cr
  k \cr}  \right) = {{n!} \over {r!\left( {n - r} \right)!}}{{r!} \over {k!\left( {r - k} \right)!}} = {{n!} \over {\left( {n - r} \right)!k!\left( {r - k} \right)!}} =   \cr
  & {{n!} \over {\left( {n - k} \right)!k!}}{{\left( {n - k} \right)!} \over {\left( {n - r} \right)!\left( {r - k} \right)!}} = \left( \matrix{
  n \cr
  k \cr}  \right)\left( \matrix{
  n - k \cr
  r - k \cr}  \right) \cr}
$$

sum on r, and change $n-k$ with $k$


问:
If $\lim_{t\to\infty}\gamma(t)=p$, then $p$ is a singularity of $\gamma$.
I'm trying to solve this question:

Let $X$ be a vectorial field of class $C^1$ in an open set
  $\Delta\subset \mathbb R^n$. Prove if $\gamma(t)$ is a trajectory of
  $X$ defined in a maximal interval $(\omega_-,\omega_+)$ with
  $\lim_{t\to\infty}\gamma(t)=p\in \Delta$, then $\omega_+=\infty$ and
  $p$ is a singularity of $X$.

The first part is easy because $\gamma$ is contained in a compact for a large $t$, my problem is with the second part, I need help.

Thanks in advance

答:
For $n \geq 0$, let $t_n \in (n,n+1)$ such that $\gamma'(t_n)=\gamma(n+1)-\gamma(n)$ (use mean value theorem).

Then $\gamma'(t_n)=X(\gamma(t_n)) \underset{n \to + \infty}{\longrightarrow} X(p)$ and $\gamma'(t_n) \underset{n \to + \infty}{\longrightarrow} p-p=0$. Thus $X(p)=0$.


问:
Do quasi-isometries of Gromov hyperbolic groups coarsely preserve the group operation?
Let $G$ be a finitely generated group and $H$ a hyperbolic group in the sense of Gromov, with a fixed word metric $d$.

Let $\varphi : G\to H$ be a quasi-isometry. Does there exist uniform constant $C> 0$ such that for any $g,h \in G$, $$d(\varphi(g)\varphi(h), \varphi(gh)) \leq C? \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$$

Discussion:

It is not too hard to see that there are quasi-isometries of non-hyperbolic spaces which do not coarsely preserve the group operation. For example, one can take the map $f : \mathbb{R}^2 \to \mathbb{R}^2$, $(r, \theta) \mapsto (r, \log(1+r))$, where $(r,\theta)$ are polar coordinates on $\mathbb{R}^2$ and $(\mathbb{R}^2, +)$ is considered as the additive group.

On the other hand, the Morse Lemma states that any quasi-geodesic in a hyperbolic space is a uniform distance away from a geodesic connecting its endpoints ("uniform" for a given choice of quasi-isometry constants and the hyperbolicity constant). Again, our example above shows that this fails badly in non-hyperbolic spaces.

Questions:

Is Morse Lemma enough to coarsely preserve the group operation under quasi-isometries? Or is there an insightful example of a quasi-isometry of hyperbolic groups where $(*)$ fails miserably?

Is there a natural condition that one can put on groups $G,H$ which would force $(*)$ to hold? (Short of something trivial like requiring one - and thus both - of $G$ and $H$ to be finite.)

答:
Here is a class of examples of infinite hyperbolic groups $G$ such that every self-quasi-isometry $G\to G$ is at finite distance from a left-translation by an element of $G$.

Start with a compact connected $n$-dimensional manifold  $M$ with nonempty boundary which admits a hyperbolic metric such that the boundary is totally-geodesic. Then the universal cover $\tilde{M}$ of $M$ is isometric to a certain convex subset $C\subset {\mathbb H}^n$ in the hyperbolic $n$-space, $n\ge 3$. The fundamental group $\pi(M)$ of $M$ acts on $C$ isometrically as the  group of covering transformations $\Pi$ for $\tilde{M}\to M$. Let $G$ denote the maximal subgroup of isometries of ${\mathbb H}^n$ preserving $C$. Since $C$ has infinitely many boundary components, the subgroup $G$ is discrete; it acts on $C$ cocompactly since $\Pi< G$. Thus, $G$ is a hyperbolic group. As it turns out, every quasi-isometry $C\to C$ is within finite distance from an element of $G$, see

Frígerio, Roberto, Commensurability of hyperbolic manifolds with geodesic boundary, Geom. Dedicata 118, 105-131 (2006). ZBL1096.32014.

Thus, $G$ satisfies the required property.

As for the original question, the answer is negative even when $G=H$, unless $G$ is finite. I'll prove it only for nonelementary hyperbolic groups $G$. Let $x\in G$ be an element of infinite order and $L_x: G\to G$ be the left translation of $G$ by $x$ ($L_x(y)=xy$). Then $L_x$ is an isometry of $G$. However, $L_x$ does not satisfy (*) for any constant $C$. Indeed, apply $(*)$ with $h=g^{-1}$, then you get
$$
d(gxg^{-1}, 1) = d(xgxg^{-1}, x)=d(xgxg^{-1}, xgg^{-1})\le C
$$
for all $g\in G$. But if $x, g$ do not commute and $g$ has infinite order, then
$$
\lim_{n\to\infty} d(g^nxg^{-n}, 1)=\infty.
$$

As for your "secret question", it sounds very difficult. I am sure it has negative answer (in general) but I do not know how to construct an example.


问:
Find ODE which represents a given family of curves
Let the family of curves
$$y=\left(1+\frac{x}{n}\right)^n,$$

with $n\ne 0$. I want to kwnok the ODE from wich this family is the solution to. I have the followin ODE:

$$y'=\left(1+\frac{x}{n}\right)^{n-1}$$

but the problem is to find an expression to $n$ wich depends only on $x$ and $y$. Any hint will be appreciated

答:
Starting from:$$y=\left(1+\frac{x}{n}\right)^n, y'=\left(1+\frac{x}{n}\right)^{n-1}.$$

you get:

$$y' = \left(1+\frac{x}{n}\right)^{n-1} = \left[\left(1+\frac{x}{n}\right)^n\right]^\frac{n-1}{n} = y^{\frac{n-1}{n}}.$$

Now, notice that:

$$\log(y') = \log\left(y^{\frac{n-1}{n}}\right) \Rightarrow \log(y') = \frac{n-1}{n}\log\left(y\right) \Rightarrow \\
\Rightarrow n \log(y')-n\log(y) = -\log(y) \Rightarrow \\
\Rightarrow n = \frac{\log(y)}{\log(y)-\log(y')}.$$

The last equation expressess $n$ as a function of $y$ and $y'$.


问:
Penrose tilings as a cross section of a $5$-dimensional regular tiling
Could somebody explain to me how a penrose tiling , which is not periodic, can be a cross section of a regular tiling in $5$ dimensions, which is periodic? It does not make sense to me how a periodic tiling can produce an aperiodic cross-section.

Also, are there any examples of periodic $3$-dimensional tilings that can produce an aperiodic $2$-dimensional cross section? That would greatly help to visualize the previous question. Thanks!

答:
To give a 3-dimensional example: Let $v$ be the vector $\left(1,\frac{\sqrt{2}}2,\frac{\pi}4\right)$ and $P$ be the plane through the origin orthogonal to $v$. Take the points in $\mathbb{Z}^3$ within distance $0.5$ of $P$, and project them down onto $P$. Then we get the following planar arrangement of points, where the edges are those of $\mathbb{Z}^3$ colored according to their direction:

Here is a GIF of this projection as the thickness of the "slab" of points we project grows from $0$ to $2.5$. (The file was too large to embed within this post, so I have linked to Imgur directly.)


问:
A is a matrix, using Euclidean norm, why $\inf\{C\geq 0:||Ah||\leq C||h||$ for all $h\in\mathbb{R^n}\}=\sup\{||Ah||:h\in\mathbb{R^n}, ||h||=1\}$
I'm reading Duistermaat's Multidimensional Real Analysis, on Page 40, it says:

The Euclidean norm (defined as $(\sum a_{ij}^2)^{1/2}$) of a linear operator $A$ is easy to to compute, but has the disadvantage of not giving the best possible estimate in inequality $||Ah||\leq ||A||_{eucl}||h||$, which would be

$\inf\{C\geq 0:||Ah||\leq C||h|| $ for all $ h\in\mathbb{R^n}\}$. (1)

It is easy to verify that this number is equal to the operator norm $||A||$ of $A$, give by

$\sup\{||Ah||:h\in\mathbb{R^n}, ||h||=1\}$. (2)

I don't understand why (1) is equal to (2)?

答:
Let $$G=\inf \left\{C\geq 0:\frac{\|Ah\|}{\|h\|}\leq C \text{ for all }  h \in \mathbb{R}^n \setminus \{0\} \right\}$$
and $$L=\sup \left\{\frac{\|Ah\|}{\|h\|}: h \neq 0 \right\}.$$

Let $\varepsilon>0$ be given.

We may find $h \in \mathbb{R}^n \setminus \{0\}$  such that
$$ L < \frac{\|Ah\|}{\|h\|}+\varepsilon.$$
Having found $h$, we may then find $C \geq 0$ so that
$$ \frac{\|Ah\|}{\|h\|}- \varepsilon \leq C - \varepsilon<G.$$
Since $\|Ah\|/\|h\| \leq L$ for all $h \in \mathbb{R}^n \setminus \{0\}$, we have $G \leq L$.

We combine to see that we have
$$L-2\varepsilon<\frac{\|Ah\|}{\|h\|}- \varepsilon < G \leq L.$$

Since $\varepsilon>0$ was arbitrary, we are left to conclude that $G=L$.

Note:

If we have $\|Ah\| \leq G\|h\|$ for all $h \in \mathbb{R}^n \setminus \{0\}$, then we have $\|Ah\| \leq G\|h\|$ for all $h \in \mathbb{R}^n$ since $\|A0\| =0 = G\|0\|$.

For $h \neq 0$ we have $h/\|h\|=1$.


问:
Proof of Sum of Trinomial Coeffs = $3^n$
I'm trying to prove that the sum of trinomial coeffs $\sum_{l+k+m=n}^n \binom{n}{l,k,m} = 3^n$.

I tried by induction and got the step as follows:

$$
\begin{split}
\sum_{l+k+m=n+1}^{n+1} \binom{n+1}{l,k,m}
 &= \sum_{l+k+m=n+1}^{n+1}\left[\binom{n}{l-1,k,m}
                               +\binom{n}{l,k-1,m}
                               +\binom{n+1}{l,k,m-1} \right]\\
 &= 3^n+3^n+\sum_{l+k+m=n+1}^{n+1} \binom{n}{l,k,m-1}(n+1) \\
 &= 3^n+3^n+3^n(n+1)
\end{split}
$$
Clearly this doesn't add up. I'm not sure if I'm going in the right direction or if the last step with the trinomial is even correct.

In addition, is it correct to even say $\sum_{l+k+m=n+1}^{n+1}\binom{n}{l-1,k,m}=3^n$, I thought so because it is equivalent to choosing three numbers whose sum is n.
Edit: My problem with the last equation is that $0 \leq k,l,m \leq n+1$, which means that $k-1, l-1, m-1$ may be equal to $-1$, which -I assume- will disturb the sum.

答:
Your $\binom{n+1}{l,k,m-1}$ should instead be $\binom{n}{l,k,m-1}$.  After you correct that, you end up with $3^n+3^n+3^n=3^{n+1}$, as desired.

The induction hypothesis is $$\sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n}} \binom{n}{k,l,m} = 3^n$$
Now
\begin{align}
\sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \binom{n+1}{k,l,m}
&=
\sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \left(
\binom{n}{k-1,l,m}
+\binom{n}{k,l-1,m}
+\binom{n}{k,l,m-1}
\right)
\\
&=
3 \sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \binom{n}{k-1,l,m} \\
&=
3 \sum_{\substack{k \ge 1, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \binom{n}{k-1,l,m} \\
&=
3 \sum_{\substack{k-1 \ge 0, l \ge 0, m \ge 0:\\ k-1+l+m=n}} \binom{n}{k-1,l,m} \\
&=
3 \sum_{\substack{j \ge 0, l \ge 0, m \ge 0:\\ j+l+m=n}} \binom{n}{j,l,m} \\
&=
3 \cdot 3^n \\
&=
3^{n+1}
\end{align}


问:
Generalising the recursion theorem to well-founded posets
The recursion theorem states the following.

Suppose $(A,\preccurlyeq)$ is a chain with order type $\omega$. Let $X$ be any set, let $x\in X$ and let $g\colon X\times A \to X$ be a function. Then there exists a unique function $f\colon A\to X$ such that
$$f(a) = \begin{cases}
         \hfil x\hfil     & \text{if $a=\min A$}\\
         g(f(t),a)   & \text{if $a=\operatorname{succ}(t)$}.
     \end{cases} $$

(E.g., for the factorial function, we put $A=\mathbb N=X$, $x=1$ and $g(m,n)=mn$.)

Now if we instead have a poset $(A,\preccurlyeq)$ which is well-founded, we can partition it so that the classes of the partition form a chain which has order type $\omega$. Indeed, define the idea of a "minimal set" as follows.

Let $(A,\preccurlyeq)$ be a poset. The minimal set of a subset $B\subseteq A$, denoted $M_\preccurlyeq(B)$ or just $M(B)$, is the set defined by
$$M(B):= \{b\in B : \text{there is no $m\in B$ such that $m\preccurlyeq b$}\}.$$

Then the desired partition of $A$ is
\begin{align*}
        A_1 &= M(A)\\
        A_2 &= M(A\smallsetminus A_1) \\
        A_3 &= M(A\smallsetminus (A_1\cup A_2)) \\
        &\kern6pt\vdots\\
        A_{n+1} &= M(A\smallsetminus(A_1\cup \cdots\cup A_n))\\
        &\kern6pt\vdots
    \end{align*}
My question is: can we state a version of the recursion theorem for this set $A$, according to this partial order?

For instance, an example which comes to mind is the binomial coefficients,
$$c(n,k) = \begin{cases}
   \hfil 1 \hfil & \text{if $(n,k)\in A_1$}\\
   \hfil c(n-1,k-1) + c(n-1,k) & \text{otherwise}.
\end{cases}$$
Here we have $A=\{(n,m)\in\mathbb N^2 : m\leqslant n\}$, and we are ordering it in the following way:

for any $n\in\mathbb N$, $(n,0) \preccurlyeq a$ for all $a\in A$

for any $n\in\mathbb N$, $(n,n) \preccurlyeq a$ for all $a\in A$

for any $n,k,\ell\in\mathbb N$, $(n,k) \preccurlyeq (n+1,\ell)$.

This captures the natural order implicit in Pascal's triangle:

Note that $A_1$ contains precisely base cases, and then the rest of the sets are such that we can define $c(n,k)$ at the $A_k$th level using its values at the previous levels.

Another example is remainder upon division:

$$r(n,d) = \begin{cases}
        \hfil n \hfil & \text{if $0\leqslant n\leqslant d$}\\
        r(n-d,d) & \text{if $n > d$}\\
        r(n+d,d) & \text{if $n < 0$}
    \end{cases}$$

Here the set is $A=\mathbb Z\times \mathbb N$, and the order is

$(n,d)\preccurlyeq a$ if $0\leqslant n\leqslant d$ for any $d$

$(n,d)\preccurlyeq (x,y)$ if $|ny|\leqslant|xd|$.

If it is to be formulated similarly, I was thinking the theorem would look something like this:

Suppose $(A,\preccurlyeq)$ is a poset where $\preccurlyeq$ is well-founded, and $\{A_1, A_2,\dots\}$ is the partition of "minimal sets" induced by $\preccurlyeq$. Let $X$ be any set, let $x_a\in X$ for each $a\in A_1$, and let $g\colon A\times X^? \to X$ be a function. Then there exists a unique function $f\colon A\to X$ such that
$$f(a) = \begin{cases}
  \hfil x_a\hfil & \text{if $a\in A_1$}\\
  g(a, f(a_1),f(a_2),\dots) & \text{if $a\in A_k$ and $A_1\cup\cdots\cup A_{k-1} = \{a_1,a_2,\dots\},$}
\end{cases}$$

i.e., the base cases are all for $a\in A_1$, and the inductive case is allowed to use the value of $f$ at any of the $a$ in the previous sets $A_1,\dots,A_{k-1}$. But this formulation doesn't feel as succinct as it could be, and also the arity of $g$ varies depending on which $A_k$ our $a$ lies in. It also doesn't feel like it captures cleanly the examples I had in mind; I can't clearly tell you what $g$ to take.

I appreciate any help with formulating this theorem. I want to have a general theorem which justifies "definition by recursion" for any well-founded poset.

答:
There is no need to get a total order associated to your partial order to make sense of recursion.  Indeed, you don't even need to have a partial order!  Here is a simple way to formulate recursion with respect to any well-founded relation.

Theorem: Let $X$ be a set and let $<$ be a well-founded relation on $X$ (i.e., for any nonempty subset $A\subseteq X$, there exists $a\in A$ such that $b\not< a$ for all $b\in A$).  Let $F:X\times V\to V$ be any (class) function.  Then there exists a unique function $f$ on $X$ such that for each $x\in X$, $f(x)=F(x,f|_{I(x)})$ where $I(x)=\{y\in X:y<x\}$.

In other words, if you have a rule for defining $f(x)$ given $x$ and the values of $f(y)$ for all $y<x$, then this defines a unique function on all of $X$.  For instance, you can use this on Pascal's triangle with $X=\{(a,b)\in\mathbb{N}^2:b\leq a\}$ where you say $(a,b)<(c,d)$ iff $c=a+1$ and $d$ is either $b$ or $b+1$ (i.e., $(a,b)$ is one of the two spots above $(c,d)$ in the triangle).  The rule $F$ would then be to define $f(0,0)=1$, and otherwise define $f(c,d)$ to be the sum of all the values $f(a,b)$ such that $(a,b)<(c,d)$.

Proof of Theorem: Say that a subset $I\subseteq X$ is an initial segment if $x\in I$ and $y<x$ implies $y\in I$.  Note that if $I$ is an initial segment of $X$, then there exists at most one function $f$ on $I$ satisfying $f(x)=F(x,f|_{I(x)})$ for each $x\in I$ (given two such functions, by well-foundedness there is a minimal element on which they disagree, which then gives a contradiction).  Call such a function good.  Now let $S$ be the set of all such good functions defined on initial segments of $X$ (this is a set by Replacement), and let $f=\bigcup S$.  Note that if $g,h\in S$ then $g$ and $h$ agree on $\operatorname{dom}(g)\cap\operatorname{dom}(h)$ since there is at most one good function on that set, and so $f$ is a function.  The domain of $f$ is an initial segment of $X$ (since it is a union of initial segments), and $f$ is good since if $x\in\operatorname{dom}(f)$, there is some $g\in S$ such that $x\in\operatorname{dom}(g)$ and then $f$ and $g$ agree on $I(x)$ and also on $x$.

To complete the proof, it remains to be shown that $f$ is in fact defined on all of $X$.  Suppose it is not; then there is a minimal element $x\in X$ where $f$ is not defined.  This means $f$ is defined on $I(x)$.  But now we can extend $f$ to a good function $f'$ on $\operatorname{dom}(f)\cup\{x\}$ by defining $f'(x)=F(x,f|_{I(x)})$.  This $f'$ is then in $S$, contradicting the definition of $f$.  Thus $f$ must be defined on all of $X$.

That said, your idea of partitioning your set is a natural and useful one, and is called the rank with respect to a well-founded relation.  Here is one way to define it.

Definition: Let $X$ be a set and let $<$ be a well-founded relation on $X$.  We then recursively define a function $\operatorname{rank}:X\to Ord$ as follows: $\operatorname{rank}(x)=\sup\{\operatorname{rank}(y)+1:y<x\}$.  (Note that such a recursive definition makes sense using the Theorem above.)

So, $\operatorname{rank}(x)=0$ if $x$ is minimal, $\operatorname{rank}(x)=1$ if $x$ is not minimal but all its predecessors are minimal, and so on.  Your sets $A_k$ are exactly the elements of rank $k$.  In general, though, the rank of an element may not be finite (in other words, you would need to continue your process transfinitely in order to exhaust your set).  For instance, if $X$ is well-ordered, then the rank function is just the unique isomorphism from $X$ to an ordinal.

Now, how can you use rank to make recursive definitions?  Well, just observe that if you define $x\prec y$ to mean that $\operatorname{rank}(x)<\operatorname{rank}(y)$, then $\prec$ is also a well-founded relation on $X$ (indeed, this uses only the fact that $\operatorname{rank}$ is some function to the ordinals!).  So, using the Theorem, you can recursively define functions on $X$ by defining $f(x)$ in terms of the values of $f(y)$ for all $y$ of lower rank than $x$.


问:
Integrating $\int{\frac{1}{1+e^{x}}}dx$, Partial Fractions(?)
I need help with this integral:

$$H(x) = \int{\frac{1}{1+e^{x}}}dx$$

It should be easy, but I'm stuck. I thought about using a u-substitution but I didn't get any further. Am I meant to use partial fractions? I'm not yet very comfortable with partial fractions. I'd be thankful for someone's explanation!

答:
Alternative way,
$$
\int \frac 1 {1+e^x}dx = \int \left(1-\frac{e^x}{1+e^x}\right)dx
$$
Then use the substitution $t=1+e^x$. </p>


问:
Exponential and Uniform Distribution Problems

Questions

I have the following problems on my probability module:

Qu1

Suppose that X is uniformly distributed over $[−3, 3]$.

(a) Find the probability that the first digit of $X$ after the decimal point is $3$.

(b) Find the distribution function of the random variable $|X|$ and use it to identify the
distribution of $|X|$.

(c) Find the density function of the random variable $1/|X|$.

Qu2

Let $X$ be a standard exponential random variable, meaning that $X ∼ Exp(1)$. Prove
that the random variable $Y = \lceil X \rceil$ is $Geom(\lambda)$ and find $\lambda$.

My answers and ideas

Qu1

(a)
$\mathbb P($First digit after deciaml point of X is 3$)$$=\mathbb P(-2.4\lt X\lt -2.2)+\mathbb P(-1.4\lt X\lt -1.2)+\mathbb P(-0.4\lt X\lt -0.2)+\mathbb P(0.2\lt X\lt 0.4)+\mathbb P(1.2\lt X\lt 1.4)+\mathbb P(2.2 \lt X\lt 2.4)=6\mathbb P(0.2\lt X\lt 0.4)=6\frac{0.2}{3-(-3)}=\frac{1}{5}$

Im not 100% sure this is correct be great if someone could check my workings :)

(b)
$|X| \Rightarrow$ $f(x)=\begin{cases}
\frac{1}{3-0},  & \text{if $0\le x \le 3$} \\
0, & \text{o/w}
\end{cases}$

$\Rightarrow F(x)=\int_{-\infty}^{x}f(t)dt=\int_{-\infty}^{x}\frac{1}{3}dt=\frac{1}{3}(x-0)=\frac{x}{3}$

Even less sure with this one :/

(c)
Not confident tackling as I'm unhappy with (b)

Qu2

I am clueless on how to approach this, tried drawing various distribution graphs. But they havent seemed to help me :(

Be great if anyone could help me by checking solutions and/or helping me with the questions I cannot do :)

答:
For future reference, it is recommended that you post your questions separately, so Question 1 and Question 2 should be different posts.

One way to conceptualize part (a) is to observe that $Y = 10(X+3)$ is uniformly distributed on $[0, 60]$, and if the the tenths digit, which is first digit after the decimal point of $X$, is $3$, that means the units digit of $Y$ is $3$.  This means the set of desired outcomes is $$Y \in [3, 4) \cup [13, 14), \cup \cdots \cup [53, 54).$$  Since this comprises six intervals of unit length, the total length is $6$ out of a total length of $60$, hence the desired probability is $1/10$.

For the second part, you need to rely less on general formulas and reason from first principles.  You cannot blindly integrate the density in the way you have done.

Instead, note that the support of $X$ is on $[-3,3]$, so if $W = |X|$, the support of $W$ is on $[0,3]$.  So we can already establish $\Pr[W < 0] = 0$ and $\Pr[W \le 3] = 1$.  Then for any $w \ge 0$, we must have $$\Pr[W \le w] = \Pr[|X| \le w] = \Pr[-w \le X \le w]  = \Pr[X \le w] - \Pr[X < -w].$$  From here, we can take two approaches.  One is to differentiate with respect to $w$, giving $$f_W(w) = f_X(w) - (-f_X(-w)) = 2f_X(w) = 2 \cdot \frac{1}{6} \mathbb 1 (0 \le w \le 3) = \frac{1}{3} \mathbb 1 (0 \le w \le 3),$$ or we can directly substitute the CDF of $X$, which is $$\Pr[X \le x] = \begin{cases}0, & x < -3 \\ (x+3)/6, & -3 \le x \le 3 \\ 1, & x > 3, \end{cases}$$ to obtain $$\begin{align} \Pr[W \le w] &= \begin{cases} 0, & w < 0 \\ (w+3)/6 - (-w+3)/6, & 0 \le w \le 3 \\ 1, & w > 3 \end{cases} \\ &= \begin{cases} 0, & w < 0 \\ w/3, & 0 \le w \le 3 \\ 1, & w > 3. \end{cases} \end{align}$$

For part (c), the random variable $1/|X|$ is simply $1/W$ from the earlier part.  Note that the support of $1/W$ is on $[1/3, \infty)$.  Thus compute $$\Pr[1/W \le w] = \Pr[W \le 1/w]$$ for some $w \in [1/3, \infty)$.

I addressed Question 2 in a different answer here.


问:
Given an X sided die, and Y throws, what is the probability that the sum of the throws is at least Z
Given an X sided die, and Y throws, what is the probability that the sum of the throws is greater than or equal to Z?

For example, given a 6 sided die and 5 throws, what's the probability that the sum is at least 10?

I tried to do this by trying to figure out the probability of of each individual possible value, but I couldn't get it to work out. What is the approach to this? Is there an easy programmatic way of figuring this out?

答:
Hint

This problem can be attacked via stars and bars analysis analysis.

General procedure.

Focus on the probability that the Y dice sum to exactly Z.

Form a bijection between the constraints of the problem and the # of non-negative integer solutions to

$$x_1 + x_2 + \cdots + x_Y = (Z - Y).$$

Edit

You have the additional constraint that in the bijected equation, each of the $x_i$ must be $\leq (X-1).$  Here, the two ways of handling the additional constraint are either Inclusion-Exclusion or generating functions.

For an illustration of both methods applied to a single mathSE query, see this.

Recognize that each solution represents an event from the sample space of $X^Y$ equally likely events.


问:
Show that $\lim_{n \to \infty} \left(1+\frac{a_n}{n}\right)^n= e^a$ when $a_n \to a$
I have seen a proof that shows
$$\lim_{n\to\infty} \left(1+\frac{x}{n}\right)^n = e^x$$
by looking at the Taylor series expansion of $\ln(1+x)$ at $x=0$.

To prove a theorem, my textbook uses the fact
$$\lim_{n \to \infty} \left(1+\frac{a_n}{n}\right)^n = e^a$$
when $a_n \to a$.

How can I prove this?

答:
Sketch of proof:

Note that $|f_n(a_n) - f(a)| \leqslant |f_n(a_n) - f(a_n)| + |f(a_n) - f(a)|.$

Then use that $f_n(x) = \left(1+\frac{x}{n}\right)^n \to f(x) =e^x $  uniformly on any compact set (proved here) and the exponential function is continuous.


问:
Number of $4$-letter "words'' that can be constructed with the $12$-letter Hawaiian alphabet
The Hawaiian alphabet consists of $12$ letters, the vowels a, e, i, o, u and the consonants h, k, l, m, n, p, w.

Show that $20,736$ different $4$-letter ‘‘words’’ could be constructed using the $12$-letter Hawaiian alphabet.

My answer: Isn't it $12 \cdot 11 \cdot 10 \cdot 9= 11880$?

答:
The other commentator is correct but I feel there can be a better explanation. The fundamental counting principle is as follows: $$\prod_{i=1} ^{n} c_i $$
Where $c_i$ is the number of choices at i. Since in this case we allow any random sequence of characters, $c_i$ will be 12 at all 4 (n) points in the word. Hence the answer, $12^4$ or 20,736.


问:
Factoring $\binom{3(n+1)}{n+1}$
I have been trying to understand how to develop $\binom{3(n+1)}{n+1}$ in this page. I know that $\binom{3n}{n}+\binom{3n}{n+1}=\binom{3n+1}{n+1}$ but I need to get to this form $\binom{3n+3}{n+1}$ and I don't know how to proceed. The result is suppose to be $\binom{3n+3}{n+1}=\binom{3n}{n}(\frac{(3n+1)(3n+2)(3n+3)}{(n+1)(2n+1)(2n+2)})$. I would like some help for this. Thanks!

答:
Using $ \binom{n+1}{r}= \binom{n}{r-1}+ \binom{n}{r} $ several times gives
\begin{eqnarray*}
\binom{3n+3}{n+1} = \binom{3n}{n-2}+3 \binom{3n}{n-1}+3 \binom{3n}{n}+ \binom{3n}{n+1}.
\end{eqnarray*}
So to prove the linked result it suffices to observe that $\binom{3n}{n+1}> \binom{3n}{n}$ so we have
\begin{eqnarray*}
\binom{3n+3}{n+1} > 3 \binom{3n}{n}+ \binom{3n}{n+1} > 4 \binom{3n}{n}
\end{eqnarray*}
and the result follows by induction.

Title: Factoring $\binom{3(n+1)}{n+1}$


答:
You can try the following:

\begin{align*}
\lim_{n\to \infty}\left( 1+\frac{a_n}{n} \right)^n &= \lim_{n\to \infty}\left( 1+\frac{a}{n} + \frac{a_n-a}{n} \right)^n \newline
&= \lim_{n\to \infty}\left( 1+\frac{a}{n} \right)^n + \lim_{n\to \infty}\frac{a_n-a}{n}(\textit{something with finite limit}) \newline
&= e^a + 0 \newline
&= e^a
\end{align*}

To formalize this second line you can use Binomial Expansion.

Title: Show that $\lim_{n \to \infty} \left(1+\frac{a_n}{n}\right)^n= e^a$ when $a_n \to a$

Body:
I have seen a proof that shows
$$\lim_{n\to\infty} \left(1+\frac{x}{n}\right)^n = e^x$$
by looking at the Taylor series expansion of $\ln(1+x)$ at $x=0$.

To prove a theorem, my textbook uses the fact
$$\lim_{n \to \infty} \left(1+\frac{a_n}{n}\right)^n = e^a$$
when $a_n \to a$.

How can I prove this?


答:
We assume the facts

$\lim_{n\rightarrow\infty}(1+\frac{x}{n})^{n}=e^{x}$ for any $x\in\mathbb{R}$.

Exponential function $x\mapsto e^x$ is continuuous.

Suppose that $a_{n}\rightarrow a$. Let $\varepsilon>0$ be given.
Since the exponential function $x \mapsto e^x$ is continuous at $a$,
there exists $\delta>0$ such that $\left|e^{a}-e^{x}\right|<\varepsilon$
whenever $x\in(a-\delta,a+\delta)$. Since $a_{n}\rightarrow a$,
there exists $N_{1}\in\mathbb{N}$ such that $\left|a_{n}-a\right|<\frac{\delta}{2}$
whenever $n\geq N_{1}$. Choose $N_{2}\in\mathbb{N}$ such that $1+\frac{a-\delta/2}{n}>0$
whenever $n\geq N_{2}$. (This is possible because $1+\frac{a-\delta/2}{n}\rightarrow 1$
as $n\rightarrow\infty$.)

Choose $N_{3}\in\mathbb{N}$ such that $\left|\left(1+\frac{a+\delta/2}{n}\right)^{n}-e^{a+\delta/2}\right|<\varepsilon$
whenever $n\geq N_{3}$. Choose $N_{4}\in\mathbb{N}$ such that $\left|\left(1+\frac{a-\delta/2}{n}\right)^{n}-e^{a-\delta/2}\right|<\varepsilon$
whenever $n\geq N_{4}$. Let $N=\max(N_{1},N_{2},N_{3},N_{4})$. Let
$n\geq N$ be arbitrary, then we have

$$
a-\frac{\delta}{2}<a_{n}<a+\frac{\delta}{2},
$$
so
$$
0<1+\frac{a-\frac{\delta}{2}}{n}<1+\frac{a_{n}}{n}<1+\frac{a+\frac{\delta}{2}}{n}.
$$
Raising to the $n$-th power, we further have
$$
(e^{a}-\varepsilon)-\varepsilon<e^{a-\frac{\delta}{2}}-\varepsilon<\left(1+\frac{a-\frac{\delta}{2}}{n}\right)^{n}<\left(1+\frac{a_{n}}{n}\right)^{n}<\left(1+\frac{a+\frac{\delta}{2}}{n}\right)^{n}<e^{a+\delta/2}+\varepsilon<(e^{a}+\varepsilon)+\varepsilon.
$$
Hence, $\left|\left(1+\frac{a_{n}}{n}\right)^{n}-e^{a}\right|<2\varepsilon$.
This shows that $\left(1+\frac{a_{n}}{n}\right)^{n}\rightarrow e^{a}.$


答:
The standard proof for binomial coefficients is to consider $(1 + 1)^n$.

First, see the start of this article.

Then, simply consider $(1 + 1 + 1)^n.$

Title: Proof of Sum of Trinomial Coeffs = $3^n$

Body:
I'm trying to prove that the sum of trinomial coeffs $\sum_{l+k+m=n}^n \binom{n}{l,k,m} = 3^n$.

I tried by induction and got the step as follows:

$$
\begin{split}
\sum_{l+k+m=n+1}^{n+1} \binom{n+1}{l,k,m}
 &= \sum_{l+k+m=n+1}^{n+1}\left[\binom{n}{l-1,k,m}
                               +\binom{n}{l,k-1,m}
                               +\binom{n+1}{l,k,m-1} \right]\\
 &= 3^n+3^n+\sum_{l+k+m=n+1}^{n+1} \binom{n}{l,k,m-1}(n+1) \\
 &= 3^n+3^n+3^n(n+1)
\end{split}
$$
Clearly this doesn't add up. I'm not sure if I'm going in the right direction or if the last step with the trinomial is even correct.

In addition, is it correct to even say $\sum_{l+k+m=n+1}^{n+1}\binom{n}{l-1,k,m}=3^n$, I thought so because it is equivalent to choosing three numbers whose sum is n.
Edit: My problem with the last equation is that $0 \leq k,l,m \leq n+1$, which means that $k-1, l-1, m-1$ may be equal to $-1$, which -I assume- will disturb the sum.


答:
If the question is how to derive the formula in the final line (rather than some other formula in the linked-to page), then note that

$$\begin{align}
{3n+3\choose n+1}
&={(3n+3)!\over(n+1)!(2n+2)!}\\
&={(3n+3)(3n+2)(3n+1)(3n)!\over(n+1)n!(2n+2)(2n+1)(2n)!}\\
&={(3n)!\over n!(2n)!}\cdot{(3n+3)(3n+2)(3n+1)\over(n+1)(2n+2)(2n+1)}\\
&={3n\choose n}{(3n+3)(3n+2)(3n+1)\over(n+1)(2n+2)(2n+1)}
\end{align}$$

Title: Factoring $\binom{3(n+1)}{n+1}$

Body: I have been trying to understand how to develop $\binom{3(n+1)}{n+1}$ in this page. I know that $\binom{3n}{n}+\binom{3n}{n+1}=\binom{3n+1}{n+1}$ but I need to get to this form $\binom{3n+3}{n+1}$ and I don't know how to proceed. The result is suppose to be $\binom{3n+3}{n+1}=\binom{3n}{n}(\frac{(3n+1)(3n+2)(3n+3)}{(n+1)(2n+1)(2n+2)})$. I would like some help for this. Thanks!


问:
$\langle u,v,u^{2} \rangle$ normal vector
When I solve the cross product the result I get is $\langle -2u, 0, 1 \rangle$.

$d\langle u,v,u^{2} \rangle /du = \langle 1,0,2u \rangle$

$d\langle u,v,u^{2} \rangle / dv = \langle 0,1,0 \rangle$

Why is the normal vector pointing up 1 even though it shouldn't? It is the graph of $f(x,y)=x^{2}$.

I mistook this solution as $\langle 0,0,1 \rangle$

答:
Your answer is correct. It helps to be able to visualize the graph $z = x^2$:

(I took a screenshot of this graph generated from https://www.math3d.org/)

If you think about it, this is basically a 1D parabola where the slope would be $\frac{dz}{dx} = 2x$, meaning the normal (perpendicular to tangent slope) would be $-\frac{1}{2x}$. If we parameterize that we could say:

$$
\Delta z = -1, \Delta x = 2x \text{ or } \Delta z = 1, \Delta x = -2x
$$

Either way you get what you found: $\langle -2x, 0, 1\rangle$ or $\langle 2x, 0, -1\rangle$ (and obviously we can multiply those by any constant factor and get infinite more representations).


问:
Strict convexity condition
I have an if and only if, and I am having trouble with one of the arrows! Here it is:

Let $C \subset \mathbb{R}^n$ such that the interior of $C$, $\operatorname{int} C \neq \emptyset$.

$C$ is strictly convex (i.e. $\forall x,y \in C$ then $\lambda x + (1-\lambda)y \in \operatorname{int}C$, $\lambda \in (0,1)$) $\Leftrightarrow \forall x,y \in C$ we have  $\frac{1}{2} x + \frac{1}{2} y \in \operatorname{int} C.$

I have shown the $\Rightarrow$ simply by taking $\lambda=\frac{1}{2}$, but I have no idea on how to prove the other implication.

Thanks a lot in advance.

答:
Given: if $x$ and $y$ are contained in $C$, then $\frac12x+\frac12y$ is in the interior of $C$.

Claim 1: If $\lambda=k/2^n$ where $n$ is an integer and $0<k<2^n$, then $$\frac{k}{2^n}x+\frac{2^n-k}{2^n}y \, \in \mathrm{int}\,C$$

Idea of proof:  induction on $n$. If $k$ is even, then simplifying the fractions brings us back to $n-1$. If $k$ is odd, apply the inductive step to
$$\frac{k-1}{2^n}x+\frac{2^n-(k-1)}{2^n}y, \quad \text{and} \quad \frac{k+1}{2^n}x+\frac{2^n-(k+1)}{2^n}y$$
Then take the average.

Claim 2: If $x \in \mathrm{int}\, C$,  $y\in C$, and $0<\lambda<1$, then $\lambda x+(1-\lambda)y\in \mathrm{int}\,C$.

Idea of proof: We already know the result for dyadic rationals $\lambda$. The dyadic rationals are dense. Also, there is $r>0$ such that the ball of radius $r$ centered at $x$ is contained in $\mathrm{int}\,C$. This allows us to move   $x$ around and cover other numbers $\lambda$ as well.

To be precise, suppose $\lambda x+(1-\lambda)y\notin \mathrm{int}\,C$. Pick $ n$ so that $1/2^n<r\lambda $. Pick $k$ so that $\lambda\le k/2^n\le  \lambda+1/2^n$. Observe that $\mathrm{int}\,C$ contains a ball of radius $rk/2^n$ centered at
$$\frac{k}{2^n}x+\frac{2^n-k}{2^n}y$$
  Try to show that this ball covers $\lambda x+(1-\lambda)y$.

Claim 3: If $x,y \in C$ and $0<\lambda<1$, then $\lambda x+(1-\lambda)y\in \mathrm{int}\,C$.

This is easy now: replace either $x$ or $y$ (as appropriate) with $(x+y)/2$, which is in the interior of $C$. Then Claim 2  applies.

Title: Strict convexity condition