问:
block matrix multiplication
If $A,B$ are $2 \times 2$ matrices of real or complex numbers, then

$$AB = \left[
\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]\cdot
\left[
\begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array} \right]
=
\left[
\begin{array}{cc} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22} \\ a_{21}b_{11}+a_{22}b_{21} & a_{22}b_{12}+a_{22}b_{22} \end{array} \right]
$$

What if the entries $a_{ij}, b_{ij}$ are themselves $2 \times 2$ matrices?  Does matrix multiplication hold in some sort of "block" form ?

$$AB = \left[
\begin{array}{c|c} A_{11} & A_{12} \\\hline A_{21} & A_{22} \end{array} \right]\cdot
\left[
\begin{array}{c|c} B_{11} & B_{12} \\\hline B_{21} & B_{22} \end{array} \right]
=
\left[
\begin{array}{c|c} A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22} \\\hline A_{21}B_{11}+A_{22}B_{21} & A_{22}B_{12}+A_{22}B_{22} \end{array} \right]
$$
This identity would be very useful in my research.

答:
It is always suspect with a very late answer to a popular question, but I came here looking for what a compatible block partitioning is and did not find it:

For $\mathbf{AB}$ to work by blocks the important part is that the partition along the columns of $\mathbf A$ must match the partition along the rows of $\mathbf{B}$. This is analogous to how, when doing $\mathbf{AB}$ without blocks—which is of course just a partitioning into $1\times 1$ blocks—the number of columns in $\mathbf A$ must match the number of rows in $\mathbf B$.

Example: Let $\mathbf{M}_{mn}$ denote any matrix of $m$ rows and $n$ columns irrespective of contents. We know that $\mathbf{M}_{mn}\mathbf{M}_{nq}$ works and yields a matrix $\mathbf{M}_{mq}$. Split $\mathbf A$ by columns into a block of size $a$ and a block of size $b$, and do the same with $\mathbf B$ by rows. Then split $\mathbf A$ however you wish along its rows, same for $\mathbf B$ along its columns. Now we have
$$
A = \begin{bmatrix}
    \mathbf{M}_{ra} & \mathbf{M}_{rb} \\
    \mathbf{M}_{sa} & \mathbf{M}_{sb}
  \end{bmatrix},
B = \begin{bmatrix}
    \mathbf{M}_{at} & \mathbf{M}_{au} \\
    \mathbf{M}_{bt} & \mathbf{M}_{bu}
  \end{bmatrix},
$$

and
$$
AB = \begin{bmatrix}
    \mathbf{M}_{ra}\mathbf{M}_{at} + \mathbf{M}_{rb}\mathbf{M}_{bt}
& \mathbf{M}_{ra}\mathbf{M}_{au} + \mathbf{M}_{rb}\mathbf{M}_{bu} \\
    \mathbf{M}_{sa}\mathbf{M}_{at} + \mathbf{M}_{sb}\mathbf{M}_{bt}
& \mathbf{M}_{sa}\mathbf{M}_{au} + \mathbf{M}_{sb}\mathbf{M}_{bu}
  \end{bmatrix}
=
\begin{bmatrix}
    \mathbf{M}_{rt} & \mathbf{M}_{ru} \\
    \mathbf{M}_{st} & \mathbf{M}_{su}
  \end{bmatrix}.
$$

All multiplications conform, all sums work out, and the resulting matrix is the size you'd expect. There is nothing special about splitting in two so long as you match any column split of $\mathbf A$ with a row split in $\mathbf B$ (try removing a block row from $\mathbf A$ or further splitting a block column of $\mathbf B$).

The nonworking example from the accepted answer is nonworking because the columns of $\mathbf A$ are split into $(1, 2)$ while the rows of $\mathbf B$ are split into $(2, 1)$.

Title: block matrix multiplication


问:
$F(a,b)$ separable if $F(a)$ and $F(b)$ are separable
Let $F$ be a field and $F(a)$, $F(b)$ simple algebraic separable extensions of $F$.

Is then $F(a,b)$ separable over $F$?

I was trying to use the transitivity of finite separable extensions (since $F(a)$ and $F(b)$ must be finite and so $F(a,b)$ too) but I am a bit stuck there since I don't know if $F(a,b)$ is separable over $F(a)$.

答: Note that $F(a,b) = F(a)(b)$. The polynomial $m(b,F(a))$ divides in particular $m(b,F)$. The latter is separable, so the former is too, and that shows that $F(a,b)/F(a)$ is separable.

ContentLicense: CC BY-SA 4.0


问:
Shortest proof of the Chinese remainder theorem
I was wondering about what is the shortest proof of the Chinese remainder theorem, so I can remember it for a test, and save my time. Can you help me with that?</p>

答:
I think the proof using localization is quite short, i.e. if $I_1,\dots,I_n$ are pairwise comaximal then any maximal ideal contains at most one of these ideals, hence the map $R\to R/I_1\times\dots\times R/I_n$ is surjective at the maximal ideals and therefore surjective itself.

In the case of $R=\Bbb Z$ there is also a short proof using the following argument: If $a,b$ are coprime then the map $\Bbb Z/ab\to \Bbb Z/a\times \Bbb Z/b$ is injective. As the two sets have the same number of elements it is also surjective (it also works for more that two elements).


问:
Laurent series example
I have been trying to understand Laurent series expansion in complex analysis and I need someone's confirmation that what I'm doing is right.

Expand the function $f(z) = \frac{1}{5-2(z+\frac{1}{z})}$ on a disk $\frac{1}{2} < |z| < 2$.

My approach was to break this fraction onto smaller parts using partial fractions and I got the following:
$\frac{-z}{(z-2)(z+2)} = \frac{-1}{2z-4}-\frac{1}{2z+4}$

Next thing I think I should do is find Laurent expansion for first fraction on $\frac{1}{2} < |z|$ and then $|z| <2$. After that I would do same for second fraction and finally I would have two expansions of this function, one on $\frac{1}{2} < |z|$ and second one on $|z| <2$.

Is this the right approach? This has been confusing me a lot lately. Thanks for any tips in advance.

答: The global approach is correct and that's how I would do it. But your computations concerning the given function are wrong. In fact, we have$$\frac1{5-2(z+1/z)}=\frac1{3(2z-1)}-\frac2{3(z-2)}.$$

Title: Laurent series example


问:
Confusion in the solution for this question
Given 4 flags of different colours, how many different signals can be generated. If a signal requires the use of 2 flags one below the other?

Le the colours be R , B , G , O.

My book answers it as  = 4 *3 = 12 which is right answer but not conceptually right .

4 means 4 choices I.e R,B,G,O. Then for 3 choices , we have B,G,O.

Now , if you see . Total combinations it will give  is RB RG RO , BB BG BO , GB GG GO , OB OG OO. Here , OO GG BB are wrong combinations .

So , if I remove them there are total 9 now. But we need 3 more . Those are BR , OR and GR.

Please tell if i am right till here ?

How to consider them then ? Now , all this cutting and then adding made the solution way also long .

Is there a shorter way of doing and how to revive those BR , OR , GR without counting it knowing and also to cut BB , GG ,  OO without counting.

答:
We have one flag each of $4$ colors - $R, B, G, O$. We need to make a signal with two flags and order matters.

So if we pick any of the color as first, we have $3$ choices for the second color. If $R$ is first, we have $3$ choices for second $B, G, O$. If $B$ is first, we again have $3$ choices for second color - $R, G, O$.

Hence total number of different signals that we can make $ = 4 \times 3 = 12$, which is $4$ choices for the first color and $3$ choices for the second for each of the first.


问:
Does pointwise equicontinuous and uniformly equicontinuous implies compactness?
If every sequence of pointwise equicontinuous functions $M \rightarrow \mathbb{R}$ is uniformly equicontinuous, does this imply that $M$ is compact?</p>

答: Consider the subspace $M=\mathbb{Z}$ of the reals, an infinite discrete space, certainly not compact. But every sequence of functions is uniformly equicontinuos in that space.</p>

ContentLicense: CC BY-SA 3.0


问:
Solving algebraic equation (compound interest)
Task: Say you have an initial capital $c_0$ on your bank account and after each year the bank gives you $p \%$ of your hole capital $c$ what you directly put to your bank account. Additionally, you deposit another $t\$$ on your bank account at the end of each year after the bank paid you the interest. After how many years will your capital exceed $b$, i.e. when does $c > b$ hold?

My recurrence formula approach:
$$
f: \mathbb{R} \to \mathbb{R};\space\space f(x) = \begin{cases}(1+\dfrac{p}{100})\cdot c_0 + t, \space \text{if }\space x = 1\\[10pt](1+\dfrac{p}{100})\cdot f(x-1) + t, \space\text{else }\\\phantom{x}\end{cases}
$$

Where $f(x)$ describes $c$ after $x$ years.

Solution: I solved it using telescoping, since it is a rather simple recurrence relation:
$$
f(n) = p\cdot f(n-1) + t = p\cdot(p\cdot f(n-2) + t) + t = \ldots = p^n \cdot c_0 + \sum\limits_{k =0}^{n-1}p^k \cdot t \\= p^n \cdot c_0 + \dfrac{1-p^{n}}{1-p}\cdot t.
$$
Notice that for simplicity we define $p := \dfrac{\text{percentage}}{100} + 1$, in contrast to the $p$ we used above, which was the "raw" percentage.

Now I'm trying to solve for $n$, which doesn't seem that easy to me. Moreover, is there a function that better represents my problem? I just started diving into analysis a few days ago so my knowledge is very little. I'm thankful for any helpful comment!

答:
$p^n \cdot c_0 + \dfrac{1-p^{n}}{1-p}\cdot t  \stackrel{(1)}{=} (k+1)^n \cdot c_0 + \dfrac{1-(k+1)^n}{k} =  (k+1)^n \cdot c_0 + \dfrac{1}{k}-\dfrac{(k+1)^n}{k} = \\[20pt](k+1)^n \cdot(c_0 -\dfrac{1}{k})+\dfrac{1}{k} = b  \Longleftrightarrow (k+1)^n = \dfrac{b}{c_0 -\dfrac{1}{k}} -\dfrac{1}{(c_0 -\dfrac{1}{k}) \cdot k} \Longleftrightarrow \\[30pt]n =\dfrac{\ln  \left(\dfrac{b}{c_0 -\dfrac{1}{k}} -\dfrac{1}{(c_0 -\dfrac{1}{k}) \cdot k} \right)}{\ln(k+1)}\\[20pt]\phantom{x}$

(1) Substitution: $k :=1-p $

Now one can back substitute.


问:
How to prove series expansion for incomplete gamma function?
Wolfram MathWorld (citing Abramowitz and Stegun) gives the following result:

$$E_1(x)\equiv\int_x^\infty \frac{e^{-u}}{u}du=-\gamma-\ln x-\sum_{n=1}^\infty\frac{(-1)^nx^n}{n\cdot n!}$$

I am wondering if anybody could supply some details on the proof of this result? In particular, if we Taylor expand $e^{-u}$, we get:

$$E_1(x)=\int_x^\infty \frac{1-u+u^2/2!-u^3/3!+\ldots}{u}du=\left(\ln u+\sum_{n=1}^\infty\frac{(-1)^nu^n}{n\cdot n!}\right)\Bigg|^\infty_x$$

The last two terms of $E_1(x)$ from above (i.e. $-\ln x-\sum_{n=1}^\infty\frac{(-1)^nx^n}{n\cdot n!}$) follow very easily from the lower bound, but I'm not sure how to argue that the upper bound evaluates to the negative Euler-Mascheroni constant $-\gamma$.

Thank you very much for your help!

答:
$E_1(x)=f(x)-g(x)$ where
$$
f(x)=\int_0^x\frac{1-e^{-t}}{t}\,dt=\int_0^x\sum_{n=1}^\infty\frac{(-t)^{n-1}}{n!}\,dt=-\sum_{n=1}^\infty\frac{(-x)^n}{n\cdot n!},
$$
$$
g(x)=\int_0^x\frac{1-e^{-t}}{t}\,dt-\int_x^\infty\frac{e^{-t}}{t}\,dt=g(1)+\ln x
$$
(indeed, write out $g(x)-g(1)$ and simplify), and finally $g(1)=\gamma$ as shown here.


问:
help me with this regarding hypothesis using chi square distribution
The rope used in a lift produced by a certain manufacturer is known to have a mean tensile breaking strength of 1700 kg and standard deviation 10.5kg. A new component is added to the material which will, it is claimed, decrease the standard deviation without altering the tensile strength. Random samples of 20 pieces of the new rope are tested to destruction and the tensile strength of each piece is noted. The results are used to calculate unbiased estimates of the mean strength and standard deviation of the population of new rope. These were found to be 1724 kg and 8.5kg.

(i) Test, at the 5% level, whether or not the variance has been reduced.

(ii) What recommendation would you make to the manufacturer?

my answer*

i want to simply know when using hypothesis is it possible to use

NULL HYPOTHESIS : population variance(sigma^2) = 10.5^2

ALTERNATE HYPOTHESIS : variance has reduced ==>population variance < 10.5^2

then test statistic =chi square = (n-1)s^2/(sigma)^2 = (20-1)8.5^2/10.5^ = 12.4512

degree of freedom =20-1=19

i have a problem with choosing the critical chi square value

i have chosen chi square critical= chi square for .05 sl and df of 19 =10.1

Since test statistic doesnt fall in region of rejection we don't reject Null hypothesis. hence Variance has not been reduced.
please help me with this problem

答:
No sure what you mean by "sl".  You want a number $c$ such that $\Pr(\chi^2_{19}<c)=0.05$.  If the test statistic is less than that, then you reject $H_0$; otherwise you don't.  (The software I'm using gives $c=10.11701$.)

You're OK, except that as your bottom line, instead of concluding that the variance has not been reduced, you should conclude that you haven't shown that it has been reduced.  That could be because you need a more sensitive test to detect a small reduction, and that more sensitive test could come from just using a larger sample.


问:
Prove that if $|g(x)|\leq a\big( 1+x \big)^{-n-b}$ then $g\in L^1(\mathbb{R^n})$
I am asked to prove that if $g:\mathbb{R}^n \to [-\infty, \infty]$ is a measurable function that satisfies $|g(x)| \le a(1+|x|)^{-n-b}$ for some constants $a, b >0$, then $g \in L^1(\mathbb{R}^n)$.

I am thinking this is not true because for example if $n=1$, $a=1$ and $b=3$, then if we pick $g(x)=a(1+|x|)^{-n-b}$ the integral $ \displaystyle \int_{\mathbb{R}}(1+x)^{-4}$ is divergent so $g \notin  L^1(\mathbb{R})$. But I am probably missing something so help would be appreciated.

答:
$\int_{\mathbb R} \frac 1 {(1+|x|)^{4}}dx =\int_{-1}^{+1} \frac 1 {(1+|x|)^{4}}dx+\int_{|x| >1} \frac 1 {(1+|x|)^{4}}dx \leq 2+\int_{|x| >1} \frac 1 {|x|^{4}}dx=2+\frac 2  3 <\infty $.

For the integrability of $g$ in the general case you can use polar coordinates in $\mathbb R^{n}$


问:
Find the area of $g_0^1(K)$
This is a question from an exam which I don't have a solution to

Given the following system $\begin{pmatrix}\dot{x}\\\dot{y}\end{pmatrix}=\begin{pmatrix}2&-3\\1&-2\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}$ Setting $g_0^1:\mathbb{R}^2\to\mathbb{R}^2$ linear transformation that operate in the following : the point $P=(x_0,y_0)$ moves to $Q=(x_1,y_1)$ if Q is the value of solution at the point $t=1$ with IVP P at $t=0$, Looking at $K=\{(x,y):\|x\|\leq1,\|y\|\leq1\}$

(i) what is $g_0^1(K)$

(ii) what is the area of the set?

I don't know how to approach this and I would like to get some hints and a way of thinking about this

答:
The eigenvalues of the matrix are $\pm 1$, then
$x=pe^t+qe^{-t}$, One ODe is $\dot x=2x-3y$ from here we get $y=\frac{p}{3}e^t+qe^{-t}$ Given that $x(0)=x_0, y(0)=y_0$. You may find $p$ and $q$ in terms of $x_0,y_0$.

Title: Find the area of $g_0^1(K)$


问:
Proving that $s_n= \sum_{j=1}^n \left(\frac{1}{j}\right)^j$ is a Cauchy sequence
I wanted to prove that  the sequence $s_n= \sum_{j=1}^n \left(\frac{1}{j}\right)^j$ is a Cauchy sequence. I started by assuming without loss of generality that $n>m$. Then
\begin{align*}
|s_n-s_m| = \left|\sum_{j=1}^n \left(\frac{1}{j}\right)^j-\sum_{j=1}^m \left(\frac{1}{j}\right)^j\right|= \left|\sum_{j=m+1}^n \left(\frac{1}{j}\right)^j\right| = \dots \ ?
\end{align*}
But I don't know if this makes any sense, because I don't know how to continue... I would be really greatful for tips! Thank you!

答:
You have, for every $j \geq 1$,
$$\frac{1}{j^j} \leq \frac{1}{j^2}$$

Because $\sum \frac{1}{j^2}$ converges, then by comparison,
$$\sum \frac{1}{j^j}$$

also converges, hence the sequence
$$\sum_{j=1}^n \frac{1}{j^j}$$

is a Cauchy sequence.


问:
Set theory task
Let F be a set of sets.
We say a set is n-pretty  (it's writen in my text book, I don't know the exact name)(n is fixed nat. number) if
$$\forall X (X \in F \iff \forall Y (Y \subseteq X \land |Y| <= n \implies Y \in F)$$.
And we say that a set is finite-pretty if:
$$\forall X (X \in F \iff \forall Y (Fin(Y) \land Y \subseteq X \implies Y \in F)$$

So the task is to find if every n-pretty set is finite-pretty

and if every finite-pretty set is n-pretty.

I think that every finite-pretty set is n-pretty. Since it's true for every finite set, it will be true for every set with cardinality n. But I can't seem to  prove it in terms of set theory. And what about the other direction ? Any tips?

答:
(i) It is not true that every finite-pretty set is $n$-pretty.

Consider for example the set $F$ of all $X\subseteq \mathbb{N}$ such that $|X|\le n$. $F$ is closed under taking finite subsets, which shows the $\Rightarrow$ direction of finite-prettiness. On the other hand, let $X$ be any set such that all its finite subsets $Y$ are in $F$. Then $X$ cannot have subsets of size $>n$, and so $X$ itself has size $\le n$, which in turn implies $X\in F$. This shows the $\Leftarrow$-direction of finite-prettiness.

However $F$ is not $n$-pretty, as $Y\in F$ for all sets $Y\subseteq \mathbb{N}$ such that $|Y|\le n$, but $\mathbb{N}\notin F$.

(ii) All $n$-pretty sets are finite-pretty.

Let $F$ be $n$-pretty. Assume first that $X\in F$ and $Y\subseteq X$ is finite; we have to show $Y\in F$. Let $Z\subseteq Y$ have size $\le n$. Since $Z\subseteq X\in F$ and $F$ is $n$-pretty, it follows that $Z\in F$. Since $Z$ was arbitrary, all subsets of $Y$ of size $\le n$ are contained in $F$. Again by $n$-prettiness, this implies that $Y$ itself is in $F$. This is the $\Rightarrow$ direction of finite-prettiness. For the other direction, assume that $X$ is a set such that all finite $Y\subseteq X$ are in $F$. Then in particular $Y\in F$ for all $Y\subseteq X$ of size $\le n$, and so $X\in F$ by $n$-prettiness.

Title: Set theory task


问:
The polynomial subspace
Let $A$ be a set of 6 polynomials in $\mathbb{R}_5[x]$ over $\mathbb{R}$ field,
assume $sp(A) = \mathbb{R}_5[x]$ which of the following is true?

1. It might be that $A$ holds exactly 4 polynomials from second degree.

2. It might be that $A$ holds exactly 4 polynomials from first degree.

I think the two argument are equivalent, and in order to span $\mathbb{R}_5[x]$
a set must have $6$ vectors, and since 4 of the vectors are in 2nd or 3rd degree it means there will always be an unreachable vector and thus the groups described in 1. and 2. cannot span $\mathbb{R}_5[x]$.

答:
Your argument is not exact, you claim that there will be unreachable
vectors but you because of the given assumption - but you don't explain
why.

Hint: What is the dimensions of $\mathbb{R}_{1}[x],\mathbb{R}_{2}[x]$
?

Recall that if $V$ is of dimension $n$ then any $n+1$ vectors
are lineally dependent.

Note: the subset of all polynomials of degree exactly $2$ (or exactly
$1$) is not a vector subspace (since, for example $x^{2}+(-x^{2})=0$
is not in this subset, or $(x^{2}+x)+(-x^{2})$).

Title: The polynomial subspace


问:
Definition of functor in equivalence with skeleton
In "Categories for the Working Mathematician" by Saunders Mac Lane, chapter IV.3, p.93.

In any category $C$ a skeleton of $C$ is any full subcategory $A$ such
that each object of $C$ is isomorphic (in $C$) to exactly one object
of $A$. Then $A$ is equivalent to $C$ and the inclusion $K: A \to C$
is an equivalence of categories. For, select to each $c \in C$ an
isomorphism $\theta_c:c\cong Tc$ with $Tc$ an object of $A$. Then we
can make T a functor $T: C\to A$ in exactly one way so that $\theta$
will become a natural isomorphism $\theta : I \cong KT$.

I suppose there is an abuse of notation, and $\theta_c:c\cong KTc$.

For a morphism $f:c \to b \in C$, how do you define $Tf \in A$ ?

To verify naturality, the relation $KTf \circ \theta_c = \theta_b \circ f$ must be verified. And, since $\theta$ is a natural isomorphism, one can write $KTf = \theta_b \circ f \circ \theta_c^{-1}$. Since the functor $K$ is full, and $\theta_b \circ f \circ \theta_c^{-1}$ is a morphism $KTc \to KTb$, then there is unique preimage to $KTf$ in $A$, and that is how you define $Tf$ in $A$.

Is my argument correct ? If not, how is $Tf$ defined ?

答:
Yes, it is correct.

About the abuse of notation, $A$ was considered to be fully contained by $C$, so $K$ is specifically the identical embedding


问:
Writing a group as a product of its generators in MAGMA
Let $G \subseteq S_8$ be generated by the elements $s=\begin{pmatrix} 1 & 2 \end{pmatrix}\begin{pmatrix} 3 & 5 \end{pmatrix}\begin{pmatrix} 4 & 6 \end{pmatrix}\begin{pmatrix} 7 & 8 \end{pmatrix}$ and $t=\begin{pmatrix} 1 & 3 & 7 & 4 \end{pmatrix}\begin{pmatrix} 2 & 5 & 8 & 6 \end{pmatrix}$.

Now I would like to see how to write the element
$$u = \begin{pmatrix} 1 & 8 \end{pmatrix}\begin{pmatrix} 2 & 7 \end{pmatrix}\begin{pmatrix} 3 & 6 \end{pmatrix}\begin{pmatrix} 4 & 5 \end{pmatrix} \in S_8$$
can be written as a product of $s,s^{-1}$ and $t,t^{-1}$ in MAGMA (assuming that $u \in G$).

I wrote the following code

```<code>G<s,t> := PermutationGroup< 8 | (1, 2)(3, 5)(4, 6)(7, 8) , (1, 3, 7, 4)(2, 5, 8, 6) >;
u := G ! (1, 8)(2, 7)(3, 6)(4, 5);
</code>```

Are there any commands to give me my desired result?

答:
The code below will do what you want - in  fact the answer is rather easy! This method will work provided that the group is not too big - say maximum order about $10^7$ or maybe $10^8$. Although not really necessary for solving this problem, it computes a presentation of the group $G$.

```<code>> G<s,t> := PermutationGroup< 8 |
    (1, 2)(3, 5)(4, 6)(7, 8) , (1, 3, 7, 4)(2, 5, 8, 6) >;
> u := G ! (1, 8)(2, 7)(3, 6)(4, 5);
> F<S,T>, phi := FPGroup(G);
> u @@ phi;
  S * T^2
</code>```

Body:
The code below will do what you want - in  fact the answer is rather easy! This method will work provided that the group is not too big - say maximum order about $10^7$ or maybe $10^8$. Although not really necessary for solving this problem, it computes a presentation of the group $G$.

> G<s,t> := PermutationGroup< 8 |
    (1, 2)(3, 5)(4, 6)(7, 8) , (1, 3, 7, 4)(2, 5, 8, 6) >;
> u := G ! (1, 8)(2, 7)(3, 6)(4, 5);
> F<S,T>, phi := FPGroup(G);
> u @@ phi;
  S * T^2


问:
Is there a more general expression for the probability of any subset of a subset being contained within another subset?
Let:

$\phantom{2}N = \{ 1 .. n \}$

$\phantom{2}J \subset N$, where $\vert J \vert = j$

$\phantom{2}K \subset N$, where $\vert K \vert = k$ and $k \le j$

$\phantom{2}L$ any $\subset\ K$, where $\vert L \vert = l$

For example: $n = 45$, $j = 7$, $k = 6$, $l = 5$

What is the probability that any $L \subset J$?

N.B. the 'any' is important, implying that J K are specific instances, but L is all instances (I'm not sure how to notate this, advice welcome).

So the case $k = j$ is well known:

$\phantom{2}$
$P = \binom{j}{l}.\binom{n-j}{j-l}/\binom{n}{j}$

But I've had no luck finding any results or discussion on the more general case where $k \le j$.

For context this is basically a lottery problem. j is the number of numbers picked by an entrant, $l=k$ is the case of winning the main prize, and $l<k$ are the cases for other lesser prizes. Many lotteries limit the number of picks to the number drawn, but there are those which will allow a greater number of picks.

答:
Doing this as a lottery problem you get a hypergeometric probability that with $n$ possibilities you get an overlap size exactly $l$ between a random set size $j$ and a random set size $k$ $($in fact one of the random sets can be fixed and it does not change the probability, but both cannot as this would make the answer $0$ or $1)$.  This is $$\frac{{k\choose l}{n-k\choose j-l}}{{n\choose j}}$$
and with $n = 45$, $j = 7$, $k = 6$, $l = 5$ you get $\frac{6\times 741}{45379620}$ which is just under $10^{-4}$


问:
Prove that $A_1,B_1,C_1$ is collinear
Let $ABC$ be a triangle inscribled inside circle $(O)$ . M is a point inside the triangle $ABC$ ($M \notin BC,CA,AB$)

$AM,BM,CM$ meets $(O)$ again at $A',B',C'$ respectively. Midperpendicular of $MA', MB', MC'$ meet $BC,CA,AB$ at $A_1,B_1,C_1$ respectively.

1.Prove that $A_1,B_1,C_1$ is collinear

2.$M'$ is symmetric to M through $A_1B_1C_1$. Prove that $M'\in (O)$

Please give me some hint

Thanks

答:
Here's a vector approach.

With a view to invoking Menelaus' Theorem, we write
$$A_1 = a B + (1-a) C \qquad B_1 = b C + (1-b) A \qquad C_1 = c A + (1-c) B$$
and we hope to show
$$\frac{a}{1-a} \cdot \frac{b}{1-b} \cdot \frac{c}{1-c} = -1 \qquad (*)$$

Let $A^{\prime\prime} = M + \frac{1}{2}\frac{|A^\prime M|}{|AM|}(M-A)$ be the midpoint of $MA^\prime$. Since $\overrightarrow{A^{\prime\prime}A_1} \perp \overrightarrow{AM}$, we have
$$( A_1 - A^{\prime\prime} )\cdot( M - A ) = 0$$
so that
$$( \; a B + ( 1 - a ) C \; )\cdot( M - A ) = A^{\prime\prime}\cdot(M-A) = M\cdot(M-A) + \frac{1}{2}|AM||A^\prime M|$$
Thus,
$$a \; ( \; B - C \; )\cdot( M - A ) = ( M - C )\cdot(M-A) + \frac{1}{2}|AM||A^\prime M|$$
and
$$-(1-a) \; (\; B - C \; )\cdot( M - A ) = ( M - B )\cdot( M - A ) + \frac{1}{2}|AM||A^\prime M|$$
whence
$$\frac{a}{1-a} = - \frac{2\;\overrightarrow{CM}\cdot\overrightarrow{AM}+ |AM||A^\prime M|}{2\;\overrightarrow{AM}\cdot\overrightarrow{BM}+|AM||A^\prime M|}$$

Now, recall the Power of a Point theorem, which says that $M$ divides chords through it into sub-segments whose lengths have a constant product, denoted here as $p$:

$$|AM||A^\prime M| = |BM||B^\prime M| = |CM||C^\prime M| = p$$

This guarantees that the left-hand side of $(*)$ expands to a circular product:
$$
\left(- \frac{2\;\overrightarrow{CM}\cdot\overrightarrow{AM}+ p}{2\;\overrightarrow{AM}\cdot\overrightarrow{BM}+p}\right)
\left(- \frac{2\;\overrightarrow{AM}\cdot\overrightarrow{BM}+ p}{2\;\overrightarrow{BM}\cdot\overrightarrow{CM}+p}\right)
\left( - \frac{2\;\overrightarrow{BM}\cdot\overrightarrow{CM}+ p}{2\;\overrightarrow{CM}\cdot\overrightarrow{AM}+p}\right)
$$
which reduces to $-1$; according to Menelaus, $A_1$, $B_1$, $C_1$ are indeed collinear.

For now, I'll leave proof that $M^\prime$ lies on the circle as homework.

Title: Prove that $A_1,B_1,C_1$ is collinear


问:
English translation of Riemann's complete works
Browsing in the library I came across with the mathematical (and some philosophical) papers of Riemann, collected by Weber and Dedekind in the original German (although published by Dover). But apparently there's no English translation reported in internet, even for the most influential papers like the November 1859 report on the Zeta function, and in such a volume some of Riemann's correspondence with mathematicians in other languages are transcribed in the respective original (for example a letter in Italian to Betti). Since the volume is relative thin and certainly highly relevant I wonder if there exists an English translation. (By the way, apparently his complete correspondence has never been fully collected).</p>

答: There is an English translation of the collected papers of Riemann, in $2004$. It says "This is the first English translation of the collected papers of Bernhard Riemann (1826-1866), one of the greatest mathematicians of all time. Riemann surfaces, Riemannian geometry and the Riemann zeta function are fundamental concepts of modern mathematics." And so on.


问:
Probability of getting a full house in five-card poker with 4 cards added?
a)  If I draw 5 cards randomly what are the chances of getting a full house ?

b) Which other card can you remove to maximize your chances of getting full house?

So you have in total 56 cards, the 4 added cards are a new king for each type. I do not really know how to do this.

答:
We have $56$ cards with $8$ kings and rest $48$ cards are of $12$ ranks similar to a standard $52$ cards pack.

a) Possibility $1$ for getting a full house -

We have two ranks without king -

So we first select which two ranks from: $1$ to $10$ and $J, Q, A$ and then any of the chosen two can be $3$ cards and the other $2$. That is,

$2 \cdot {12 \choose 2} {4 \choose 3} {4 \choose 2}$ possibilities

b) Possibility $2$ for getting a full house -

One of the ranks is king and so we choose $1$ rank from remaining $12$ ranks. Then we either have $3$ cards of king and $2$ of the other or $2$ cards of king and $3$ of the other. That is,

${12 \choose 1} \big[{8 \choose 3} {4 \choose 2} + {8 \choose 2} {4 \choose 3})\big]$ possibilities.

Total count of favorable possibilities is sum of $(a)$ and $(b)$ and then to find desired probability, we divide by

c) Total possibilities without restrictions, which is ${56 \choose 5}$.


问:
When would giving an example of these functions be impossible?
I'm trying to understand exactly what would make a request like this impossible

A function defined on $[-1, 1]$ with $\lim_{x\to 0^+}f(x) = \infty$ and $\lim_{x\to 0^-\ }f(x) = \infty$

A continuous function defined on $[-1, 1]$ such that $f(1/n) = n$ for every positive integer $n$

答:
Such a request is not impossible. Indeed, consider $f: [-1, 1] \to \Bbb R$ defined by $$f(x) := \begin{cases} |x|^{-1} & x \neq 0, \\ 0 & x = 0.\end{cases}$$

This also satisfies $f(1/n) = n$ for all positive integers $n$. This is not continuous at $0$, by the way. You didn't demand continuity at the beginning.

However, what you wrote does not suffice. You cannot just say consider a continuous function with that property because you have to show that such a function exists.

In fact, if you do impose continuity, then no such real-valued function exists because continuity would enforce $$f(0) = \lim_{x \to 0^+}f(x) = \infty \notin \Bbb R.$$


问:
Find shortest paths between two groups of a graph
Let $\ G(V,E) $ be a simple directed graph with non-negative edges weights. Given a group of vertices $\ A \subset V $ I need to find an algorithm that for every vertex $\ v \in V \setminus A $ , it will find the shortest path possible from any vertex in $\ A $ to that vertex $\ v $

My attempt:

$\ U := V \setminus A $

I will set a new array of size $\ |U| $ with all of its values set to $\ \infty $ and then for every vertex $\ v_1 \in A $ I will run a modified BFS where BFS iteration will stop if it is needed to go through another vertex in $\ A $ . check the result of the BFS for that $\ v_1 $ and update my initial array with distances if necessary.

答:
Since your edge weights are all positive and you are not stating that these paths must be disjoint, you can just apply Dijsktra‘s algorithm for every vertex in $A$ to every vertex in $V \setminus A$.

The algorithm works for directed graphs, too. This is discussed here. An implementation can be found here.


问:
About completeness of $l^{\infty}$ with respect to sup norm
Let $l^{\infty}$ be the space of all bounded sequences of real numbers $(x_n)_{n =1}^{\infty}$ with the sup norm. I have to show that $l^{\infty}$ is complete with respect to this norm.

Proof: In the proof below I am confused with the sequence $x^n = (x_1^{n},x_2^{n}\ldots )$. I am not able to visualize this sequence. How this sequence can be formed? Is $(x^{n})$ is collection of cauchy sequences?

$x_1^{n}$,$x_2^{n}$ are different cauchy sequences they may be converging to different points so how can we assume that $(x^{n})$ will converge to fixed point $x$?

Please help me to understand this. Any numerical example supporting this will be very much helpful.  Thanks

答:
Elements of $l^\infty$ are sequences. You have to show that a Cauchy sequence in $l^\infty$ converges.

Using a different notation, consider a Cauchy sequence $(x_n)$ in $l^\infty$. Each $x_n$ is itself a sequence; let's denote it by
$$
x_n(0), x_n(1), \dots
$$
So, if $x_n$ is the sequence $1, 1/3, 1/5,\dotsc$ (the reciprocals of the odd integers), you'd have $x_n(0)=1$, $x_n(1)=1/3$ and so on. Thus $x_n(k)$ means "the $k$-th term in the $n$-th element of the sequence we're starting with". The book page you show simply writes this as $x^n_k$.

So every $x_n$ (or $x^n$ in the book's notation) is a bounded sequence, not a Cauchy one, because it's an element of $l^\infty$. It's not at all assumed that $x_n$ converges (most elements of $l^\infty$ don't). It's the sequence (of sequences) $x_0,x_1,\dotsc$ that is a Cauchy sequence under the sup norm.

The fact that $(x_n)$ is a Cauchy sequence means that, for all $\def\eps{\varepsilon}\eps>0$, there is $N$ such that, for $n,m>N$
$$
\|x_n-x_m\|<\eps
$$
that is,
$$\sup_k|x_n(k)-x_m(k)|<\eps,$$
which implies
$$
|x_n(k)-x_m(k)|<\eps, \text{ for all } k.
$$
(it would be equivalent if we used $\le\eps$ throughout).


问:
Confusion in the solution for this question
Given 4 flags of different colours, how many different signals can be generated. If a signal requires the use of 2 flags one below the other?

Le the colours be R , B , G , O.

My book answers it as  = 4 *3 = 12 which is right answer but not conceptually right .

4 means 4 choices I.e R,B,G,O. Then for 3 choices , we have B,G,O.

Now , if you see . Total combinations it will give  is RB RG RO , BB BG BO , GB GG GO , OB OG OO. Here , OO GG BB are wrong combinations .

So , if I remove them there are total 9 now. But we need 3 more . Those are BR , OR and GR.

Please tell if i am right till here ?

How to consider them then ? Now , all this cutting and then adding made the solution way also long .

Is there a shorter way of doing and how to revive those BR , OR , GR without counting it knowing and also to cut BB , GG ,  OO without counting.

答:
The answer that the book provides you is the direct application of the
following formula:
$$
nP_k = {\displaystyle\prod_{i=0}^{k-1} (n - i)}=\dfrac{n!}{(n-k)!}
$$

If we plug $n=4$ (our pool of distinct flags) and $k=2$ (the number of flags to sample in order to build a signal), according to the problem statement, the formula will yield:
$$
4P_2 = \dfrac{4!}{(4-2)!}=\dfrac{4!}{2!} = \dfrac{4\cdot 3\cdot 2\cdot 1}{2\cdot 1}= 4\cdot 3 = 12
$$

As you correctly pointed out that $12$ is the right answer.

Now for the intuition behind the problem and in general when we have to deal with ordered permutations, we can think of the problem as follows:

Let's suppose that we have two placeholders for any of the available flags, denoted as $F_1 \, F_2$ . Furthermore, since the order of the flags matters $F_1 \, F_2 \ne F_2 \, F_1$, this leaves us with $n=4$ possible options for the $F_1$ placeholder and $n-1=3$ for the $F_2$ placeholder. This is because initially the whole set of flags is available for selection e.g. $F=\{R,B,G,O\}$, picking any flag from this set leaves us only three of the rest flags available for selection:

Case 1: First choice is $\color{red}R$ from the whole set of flags $\{R,B,G,O\}$
$$R \, F_2$$
this entails that the second flag must be sampled from the following set $\{B,G,O\}$.
This leads to, the following three permutations:
$$\mathbf{\color{red}R}\color{blue}B, \, \mathbf{\color{red}R}\color{green}G, \, \mathbf{\color{red}R}\color{orange}O$$

Case 2: First choice is $\color{blue}B$, then the possible values for $F_2$ are $\{R,G,O\}$
$$\mathbf{\color{blue}B}\color{red}R, \, \mathbf{\color{blue}B}\color{green}G, \, \mathbf{\color{blue}B}\color{orange}O$$

Case 3: First choice is $\color{green}G$, then the possible values for $F_2$ are $\{R,B,O\}$
$$\mathbf{\color{green}G}\color{red}R, \, \mathbf{\color{green}G}\color{blue}B, \, \mathbf{\color{green}G}\color{orange}O$$

Case 4: First choice is $\color{orange}O$, then the possible values for $F_2$ are $\{R,B,G\}$
$$\mathbf{\color{orange}O}\color{red}R, \, \mathbf{\color{orange}O}\color{blue}B, \, \mathbf{\color{orange}O}\color{green}G$$

Each of the $4$ cases having $3$ possible permutations.
Putting it all together we have $12$ permutations:
$$\mathbf{\color{red}R}\color{blue}B, \, \mathbf{\color{red}R}\color{green}G, \, \mathbf{\color{red}R}\color{orange}O, \, \mathbf{\color{blue}B}\color{red}R, \, \mathbf{\color{blue}B}\color{green}G, \, \mathbf{\color{blue}B}\color{orange}O, \, \mathbf{\color{green}G}\color{red}R, \, \mathbf{\color{green}G}\color{blue}B, \, \mathbf{\color{green}G}\color{orange}O, \, \mathbf{\color{orange}O}\color{red}R, \, \mathbf{\color{orange}O}\color{blue}B, \, \mathbf{\color{orange}O}\color{green}G$$

If we think about the product series from the $nP_{k}$ formula we can see its connection to the physical intuition.
$$
\begin{aligned}
nP_k &= {\displaystyle\prod_{i=0}^{k-1} (n - i)} \\
     &= n \cdot {\displaystyle\prod_{i=1}^{k-1} (n - i)} \\
     &= n\cdot (n-1) \cdot {\displaystyle\prod_{i=2}^{k-1} (n - i)} \\
     &= n \cdot (n-1) \cdot (n-2) \cdot {\displaystyle\prod_{i=3}^{k-1} (n - i)}
\end{aligned}
$$

What one might notice is that each increment of the product series index variable $i$ multiplies the current product by the cardinality of the remaining set of flags e.g. the number of the available flags in the current set. This will carry on until all $k$ placeholders are filled, again considering all remaining flags currently in the set, according to its index number e.g. the current cardinality of the set, denoted as $n-i$ with $i \in [0, k) \subset \mathbb N_0$.

Note :

  This problem is about permutations, your attempt to solve the problem suggests that you calculated the cartesian product of the set with itself and then correctly waived out the invalid combinations namely $RR, GG, BB, OO$.
The latter is a hint that any flag once chosen from the set, is not placed back in it, i.e. there is no replacement of the flags in the set.
The second hint about the problem is that order matters that is $F_1F_2 \ne F_2F_1$ i.e. $RB \ne BR$. This suggests that counting the combinations (unordered edition of the problem) is not the answer. However, had the order been irrelevant, then you could use the $nC_k = \dfrac{n!}{(n-k)!\cdot k!}$ to calculate all possible unordered combinations. It might be apparent to you that $nP_k$ and $nC_k$ relate through $ nP_k = k! \cdot nC_k$.
Since $k=2$ this means that $nP_2 = 2\cdot nC_2$ which could be intuitively derived from the fact that once you have written down the unordered combinations then you must add them again but in flipped order, to account for the other combinations that you have pointed out. Beware that this only works when $k=2$.


问:
Convexity of set bounded positive semidefinite matrix
can anybody help me with this question?
Let $A\in R^{nxn}$ a positive semidefinite matrix and $\alpha \geq 0 $ I want to prove the following:

$ M_{\alpha} = { x \in R^n | x^{T}Ax \leq \alpha}$ is convex?
to prove that I am adviced to use the following tip after proving it
for any $ \lambda,\mu \in R $ the following holds
$\lambda^2x^{T}Ax+2\lambda\mu x^T A y+ \mu^2 y^{T}Ay \geq 0$

Please excuse me for the bad writing

Body:
If you take $x_1,x_2\in M_\alpha$, you have to show that for $t\in[0,1]$, such that , $tx_1+(1-t) x_2 \in M_\alpha$.

Then, you can compute :
$$(tx_1+(1-t)x_2)^TA(t x_1+(1-t) x_2)=t^2x_1^TAx_1+(1-t)^2x_2^TAx_2+t(1-t)(x_1^TAx_2+x_2^TAx_1)\\
= t^2x_1^TAx_1+(1-t)^2x_2^TAx_2+t(1-t)\left (x_1^T\left(\frac{x_2x_2^T}{||x_2||^2}\right)Ax_2+x_2^T\left(\frac{x_1x_1^T}{||x_1||^2}\right)Ax_1\right) \\
\leq  t^2x_1^TAx_1+(1-t)^2x_2^TAx_2+t(1-t)\alpha\left(\frac{x_1^Tx_2}{||x_2||^2}+\frac{x_2^Tx_1}{||x_1||^2}\right) \\
\leq \left(t^2+(1-t)^2+t(1-t)<x_1,x_2>^2\left(\frac{||x_1||^2+||x_2||^2}{(||x_1||\cdot||x_2||)^2} \right)\right)\alpha\text{ (using Cauchy-Schwarz)}\\
\leq \left(t^2+(1-t)^2+t(1-t)(||x_1||^2+||x_2||^2)\right)\alpha\\
\leq \left(1-\frac{||x_1||^2+||x_2||^2}{2} \right)\alpha$$

Well, I can't get to the final result, but with this, I can get that $M_\alpha$ is convex on the unitary ball on $\mathbb{R}^n$


问:
Constant Rank Theorem for Manifolds with Boundary
I'm trying to answer problem 4-3 from Lee's Introduction to Smooth Manifolds, 2nd edition.  The problem says:

Formulate and prove a version of the rank theorem for a map of constant rank whose domain is a smooth manifold with boundary.

Lee himself gave a hint in another question. Here is what I have so far:

I'm assuming I have a smooth map of constant rank $F: \mathbb{H}^m\rightarrow\mathbb{R}^n$. Let's say $\mathrm{rank}(F)=k$. Then I extend $F$ to a smooth map $\tilde{F}:\mathbb{R}^m\rightarrow\mathbb{R}^n$.  I can shrink the domain to a small enough neighborhood of $\mathbf{0}$, $U$, such that there is a projection $\pi:\mathbb{R}^n\rightarrow\mathbb{R}^k$ with $\pi\tilde{F}_{|U}$ a submersion. The actual constant-rank theorem then says we have charts $(A,\alpha)$ and $(B,\beta)$ with
$$ \beta\circ\pi\tilde{F}\circ\alpha^{-1}:\alpha(A)\rightarrow\beta(B)$$

If I write the coordinates of $\mathbb{H}^m$ as $(x,y)$ and the coordinates of of $\alpha(A)$ as $(a,t)$, then this map looks like
$$ \beta\circ\pi\tilde{F}\circ\alpha^{-1}(a,t) = a$$

I can switch the order so the projection is the last map applied:
$$ \pi\circ(\beta\times\mathrm{id})\circ\tilde{F}\circ\alpha^{-1}\equiv\beta\circ\pi\tilde{F}\circ\alpha^{-1}$$

Which finally means
$$(\beta\times\mathrm{id})\circ\tilde{F}\circ\alpha^{-1}(a,t)=(a,S(a,t))$$
Where $S:\alpha(A)\rightarrow\mathbb{R}^{(n-k)}$.

This is pretty similar to how the constant-rank theorem is proved, but now I'm stuck.  The map above, restricted to $\alpha(A\cap\mathbb{H}^m)$, has rank $k$. But that does not mean $S$ is independent of $y$. That's because $\alpha$ is not necessarily a boundary chart on $A\cap\mathbb{H}^m$. I also don't see any way to make $\alpha$ a boundary chart (something similar is proved in Lee's book, but crucially uses that $F$ is an immersion).

Can someone give me a hint as to how to finish this? Ideally I'd get to a place where (with possibly different charts)
$$ \tilde{\beta}\circ F\circ\tilde{\alpha}^{-1}(a,t) = (a,0)$$
and $\tilde{\alpha}$ is a boundary chart.

Bonus question: where do I use Lee's assumption (from the hint) that $\ker dF_p\not\subseteq T_p\partial\mathbb{H}^m$?

答:
Lee's Introduction to Smooth Manifolds deals with the case of local immersions for manifolds with boundary in Theorem 4.15. So let us suppose that $F:\mathbb{H}^m \rightarrow \mathbb{R}^n$ has $\mathrm{rank}(F)=k<m$. For $\mathbb{H}^m=\{(x^1,\dots,x^m)\in \mathbb{R}^m, x^m\geq 0\}$, the assumption $\ker dF_p\not\subseteq T_p\partial\mathbb{H}^m$ in Lee's answer to the original question means
that $dF_p(\partial/\partial x^m+a_1\partial/\partial x^1+\dots+a_{m-1}\partial/\partial x^{m-1})=0$ for some numbers $a_i$. The search for $k$ linearly independent tangent vectors in the image can therefore be restricted to $dF_p(\partial/\partial x^i), i<m$. Let's suppose that $k$ is the rank of $(\partial F_i/\partial x^j)_p, 1\leq i, j \leq k$. The coordinate change $(x^1,\dots,x^m) \rightarrow (F_1,\dots,F_k,x^{k+1},\dots,x^m)$ produces another boundary chart $x^m\geq 0$ for which the rest of the proof works as in the case of manifolds without a boundary.


问:
Looking for an approach to proving Inequivalence of norms
X is a infinite dimensional,separable, Banach space with a Hamel Basis $\{e_a\}$. Let $\vert\!\vert x\vert\!\vert=\sum\vert x_a\vert$ ,
where $x=\sum(x_a e_a)$.
Prove that $\vert\!\vert\cdot\vert\!\vert$ is not equivalent to the original norm on X.

I am very confused about where to approach this from. I've tried assuming they are equivalent and proving it wrong to no avail. The other way I have tried to do it is to prove that it will not be complete with the new norm, but i cannot seem to do it that way either. Im not looking for an answer, just a nudge in the right direction.

Thank you <3

答: Suppose that $||x||_1 =\sum |x_a |$ and $||\cdot ||$ are equivalent. Then $(X, ||\cdot ||_1)$  is a Banach space. But the sequence $$z_n =\sum_{k=1}^n \frac{1}{k^2 } e_{a_k}$$ is an Cauchy sequence in $(X, ||\cdot ||_1)$ without a limit. That gives a contradiction.


问:
Calculate $\int_{C(0,1)} z^3\exp(\frac{1}{z^2})dz$
Calculate: $$\int_{C(0,1)} z^3\exp(\frac{1}{z^2})dz$$
I don't have idea what I can do to use Cauchy's theorem.

答:
I think that $C(0,1)$ means $\{z \in \mathbb C: |z|=1\}.$

We have

$$z^3\exp\left(\frac{1}{z^2}\right)= z^3+z+\frac{1}{2} \cdot\frac{1}{z}+\frac{1}{6} \cdot \frac{1}{z^3}+ .....$$

All summands on the RHS have anti-derivatives, with the exception $\frac{1}{2} \cdot\frac{1}{z}$.

Hence

$$\int_{C(0,1)} z^3\exp\left(\frac{1}{z^2}\right)dz= \frac{1}{2} \int_{C(0,1)}\frac{1}{z} dz=i \pi.$$


问:
hypothesis testing result problem
For a normal distribution of $N(30,10)$ and sagnificence of 5% (α=0.05),

the sample mean is 32.5 and the population size is 64.

H0: $μ=30$

H1: $μ>30$

A. What is the probability for a second type error?(β)

What I did was, $=P( accept H_0 |   H_0  false)=P(X ̅<30 | μ=32.5)=Φ((30-32.5)/(10/√64))=1-Φ(2)=0.0227$

B. What is the sample size needed for a $90$% discovery chance of the second type error?

what I did was,

$n≥((Z_(1-α)+Z_(1-β) )^2 σ^2)/(μ_1-μ_0 )^2 =((1.65+1.285)^2 ×10^2)/(32.5-30)^2 =137.83$

My problem is,

In part B, the probability for a second type error is $0.1$, and the sample size I get is 138, BUT in part A the probability for a second type error I get is 0.027 and the sample size is 64.

How is that possible that I get a bigger sample size for a higher probability for an error?

The full excercise,

答:
After reading the original text, it is very different from you initial summary.

First, looking at your calculations, I assume that with $N(30;10)$ you mean a Gaussian with st dev =10 but usually this notation is used as a variance =10. Using a variance =10 the calculations makes no sense thus I correct the solution I wrote before considering $N(30;10^2)$

A:

Verifying the system of hypothesis (one tail) at 5% you get the following critical region

$$\frac{\overline{X}_{64}-30}{10}8 \geq 1.64$$

That is $\overline{X}_{64}\geq 32.06$

Thus we reject the null hypothesis as the sample mean is $\overline{X}_{64}=33>32.06$

The manager's claim is correct.

B: the minimal $\alpha$ is

$$P\left(\overline{X}_{64}>33|H_0\right)=\dots=P(Z>2.4)=0.82\%$$

(this is called p-value of the test)

C: "if really the mean moved to 32.5" means that 32.5 is the new alternative Hypothesis, thus

$$\beta=P(\overline{X}_{64}<32.06|\mu=32.5)=P\left(Z<\frac{32.06-32.5}{10}8\right)=\Phi(-0.355)=0.36$$

Now I think you can proceed by yourself

Title: hypothesis testing result problem


问:
Romberg Integration Midpoint
I've seen multiple sources, claiming that the Richardson Extrapolation for the Romberg Integration (Trapezoidal method) is...
$$R_{i,j}=\frac{4^{j-1}R_{i+1,j-1}-R_{i,j-1}}{4^{j-1}-1}$$

if the intervall step size is $h = (b-a)/t$ with $t = 2^{\mathbb{N}_0}$.

My Professor told me the Richardson Extrapolation for the Romberg Integration (midpoint/rectangle method) is
$$R_{i,j}=\frac{9^{j}R_{i+1,j-1}-R_{i,j-1}}{9^{j}-1}$$

if the intervall step size is $h = (b-a)/t$ with $t = 3^{\mathbb{N}_0}$.

So my questions are:

Is the formula for the Richardson Extrapolation of my prof true? I can't find it anywhere. Especially why it's $9^{j}$ and not $9^{j-1}$

Is $t = 3^{\mathbb{N}_0}$ necessary for the midpoint method or could I do it with $t = 2^{\mathbb{N}_0}$?

Is there any practical difference between using base 2 or base 3?

答:
This is a question of the re-use of previously computed values. If you refine the subdivision by halving, then the old midpoints are no longer used in any of the following refinements. Still, you compute 2 new function values for each subdivided segment.

On the other hand, by reducing the segments to thirds, the old middle point is still the middle point of the middle sub-segment. So you still have to compute 2 new function values per segment, but as this is an overall finer subdivision, the error will thus be smaller accordingly.

Title: Romberg Integration Midpoint


问:
Prove that every component of $E$ is unbounded.
Suppose that $f$ is a nonconstant entire function. Define $E=\{z \in \mathbb{C} : ｜f(z)｜>1\}$. Prove that every component of $E$ is unbounded. My attempt is that if $F$ is a component of $E$, then the continuity of $f$ shows that $|f(z)| \ge 1$ on $\partial F$. Assume $|f(z_0)|>1$ for some $z_0 \in \partial F$. Then I can show that $|f(z)|>1$ for all $z \in D(z_0,\delta)$ for some $\delta>0$. Thus $D(z_0,\delta) \subseteq E$ and it is impossible because $z_0 \in \partial F$. Therefore, we have $|f(z)|=1$ on $\partial F$. However, I stop at this point and I can't do anything. Please help!

答: Assume that there exists a bounded component $F$ of $E=\{z \in \mathbb{C} : |f(z)|> 1\}$. Then $|f(z)|=1$ on $\partial F$, as you already figured out. Because of the maximum modulus principle, $|f|$ attains its maximum on the compact set $\overline F$ only at points on the boundary. It follows that $|f(z)| \le 1$ in $F$, which is a contradiction.


问:
Numbers which are not the sum of distinct squares
We are defining  square factorization as representation a positive natural number as sum of squares of different positive, integer numbers. For example $5 = 1^2 +2^2$ and $5$ has no more representation. But one number can possess more representations, eg. $30$.

$$30 = 1^2 + 2^2 + 5^2 = 1^2 +2^2 + 3^2 + 4^2$$

Sometimes $n$ has no representation, eg. $8$. If square factorization for $n$ is impossible, we call $n$ indecomposable, so $8$ is indecomposable. Because it is a significant part of other proof I began to wonder, how can we know there is finite number of indecomposable numbers. Of course, it is well know fact, but I have still problem with proving that.

How to show that any number greater than $128$ can be written as sum of distinct squares — for all $n > 128$ square factorization exist?

答: I actually did this for fun when I was 17 (and it was mostly fun, though a bit of a grind). The way I did it was to realise that, for numbers 0 mod 4, I only needed to test up to 512, because anything after that could be written as 4 times the solution for the quarter of that number (for example, if 129 = 100 + 25 + 4, then 516 = 400 + 100 + 16). After that, numbers 1 mod 4 need to be tested up to 517 (take any solution that can be quadrupled and add 1), numbers 2 mod 4 need to be tested up to 526 (add 9 and 1), and numbers 3 mod 4 need to be tested up to 551 (add 25, 9 and 1). The grindy part was testing all those numbers.</p>


问:
Finding eigenvalue of a matrix expression
Consider the following matrix
$A=\left[\begin{array}{lll}1 & 0 & 0 \\ 2 & 3 & 0 \\ -3 & 1 & -2\end{array}\right]$

How can I find the eigenvalues of $3 \mathrm{~A}^{3}+5 \mathrm{~A}^{2}-6 \mathrm{~A}+2 \mathrm{I}$?

I know the matrix $A$ has eigenvalues $1,3,-2$ and also that I can use cayley Hamilton theorem and reduce the matrix expression, but that doesn't reduce it enough so that I can avoid multiplication of matricies.

Can anyone please help me how to do this?

Thank you.

答: Hint: If $Av = \lambda v$, then what can we say about $(3A^3 +5A^2 - 6A + 2I)v$?


问:
How to calculate Jacobian in case of this
Now,

$x=\frac{sin(a)}{cos(b)}$,

$y=\frac{sin(b)}{cos(a)}$

I want to calculate Jacobian.
Please teach me how to calculate.

答:
I suppose you want to calculate the Jacobian of
$$(x(a,b),y(a,b))=\Bigg(\dfrac{\sin a}{\cos b},\dfrac{\sin b}{\cos a}\Bigg).$$
First we have to compute the partial derivatives of $x(a,b)$ and $y(a,b)$, so
$$x'_a=\dfrac{\cos a}{\cos b}\text{ and }x'_b=\sin a \tan b \sec b$$
$$y'_a=\sin b\tan a \sec a\text{ and }y'_b=\dfrac{\cos b}{\cos a}$$
so the jacobian is given by
$$\mathrm J=\begin{pmatrix}x_a' &x_b'\\y_a'& y_b' \end{pmatrix}=\begin{pmatrix}\dfrac{\cos a}{\cos b}&&\sin a \tan b \sec b\\\sin b\tan a \sec a&&\dfrac{\cos b}{\cos a} \end{pmatrix}.$$


问:
A four-digit number is to be made using 0,1,2,3,4,5. Find probability of following.
I know the concept of the question is repeated. I just want to cross verify my answers as my answers are not matching with textbook.

A four digit number is to be formed from {0,1,2,3,4,5} without repeating any digit. Find the probability that the digit formed is (i) odd (ii) > 4000 (iii) > 3400 (iv) multiple of 5

Question pic

This is my solution:
n(S) = 6P4 = 360

(i) odd :

n(A) = 5P3 * 3P1 = 180

P(A) = 180/360 = 1/2

But textbook says its 12/25

(ii) > 4000

n(B) = 2P1 * 5P3 = 120

P(B) = 120/360 = 1/3

But textbook says its 2/5

(iii) > 3400

n(C) = 2P1 * 5P3 + 1P1 * 2P1 * 4P2 = 144

P(C) = 144/360 = 2/3

But textbook says its 12/25

(iv) multiple of 5

n(D) = 5P3 * 2P1 = 120
P(D) = 120/360 = 1/3

But textbook says its 9/25

What I am doing wrong,If i am?

答:
To find total count of valid $4$ digit numbers, we find how many of $360$ arrangements have leftmost digit as zero and subtract them.

That is simply  $5 \times 4 \times 3 = 60$

So total count of valid $4$ digit numbers $ = 360 - 60 = 300$.

Now we count valid $4$ digit odd numbers which is

$3 \times 5 \times 4 \times 3 - 3 \times 4 \times 3 = 144$

That leads to probability of $\frac{12}{25}$.

You can complete the rest similarly.


答:
If  $a$   is a eigen value of the matrix $A$  then  $a^2$ is the eigen value for $A^2$...similar arguments for $A^m$, where m is a positive  integer.

Similarly, $k*a$ is the eigen value for $kA$.

Now  use the previously mentioned  rules (observations) to calculate the eigen value of any expression  with out calculating the  powers of the matrix.

Title: Finding eigenvalue of a matrix expression

Body:
Consider the following matrix
$A=\left[\begin{array}{lll}1 & 0 & 0 \\ 2 & 3 & 0 \\ -3 & 1 & -2\end{array}\right]$

How can I find the eigenvalues of $3 \mathrm{~A}^{3}+5 \mathrm{~A}^{2}-6 \mathrm{~A}+2 \mathrm{I}$?

I know the matrix $A$ has eigenvalues $1,3,-2$ and also that I can use cayley Hamilton theorem and reduce the matrix expression, but that doesn't reduce it enough so that I can avoid multiplication of matricies.

Can anyone please help me how to do this?

Thank you.


问:
How many $k$-nary relations are there for sets $A_i$ to $A_k$ of sizes $s_i$
I found lots of questions for binary relations. I wonder what the generalization would look like. I somehow can't seem to wrap my hand around this. Any suggestions?

/edit: For my particular case the question is, given a set $A$ with $n$ elemements, how many $k$-nary relations are there, so in this case every $s_i=n$. But I find the generalization a bit more interesting.

/edit: would it  be something like $k^{s_1 \cdot s_2 \cdot  s_3 \cdot \ldots\cdot s_k}$?

答: The relation is a function in the form $A_1 × A_2 × A_3 × \ldots × A_k \to \{\text{true},\text{false}\}$. So there are $s_1\cdot s_2\cdot s_3\cdot\ldots\cdot s_k$ combinations of elements which may or may not be in relation. And you can decide whether or not a combination is in relation or not for each combination independently. So you have $2^{s_1\cdot s_2\cdot s_3\cdot\ldots\cdot s_k}$ relations in total.


问:
when upper limit of integral approaches to lower limit of definite integral, is integral vanish?
I need to compute, $\lim_{n→∞}\int^{a+\frac{1}{n}}_a f(x)dx$. Given that, $F(x)$ antiderivative of continuous function $f$

My attempt:  $\lim_{n→∞}\int^{a+\frac{1}{n}}_a f(x)dx=\lim_{n→∞}(( F(a+\frac{1}{n})-F(a))=F(a)-F(a)=0$

答:
Your considerations are correct.

Another approach: by the mean value theorem for integrals, there is $t_n \in [a,a+1/n]$ with

$$ \int^{a+\frac{1}{n}}_a f(x)dx=\frac{1}{n}f(t_n) \to 0$$

as $ n \to \infty.$


问:
Filtration related to stopping time of Brownian Motion: Paths are measurable?
Given a stopping time $T:\Omega\rightarrow \mathbb{R}$ there is a related $\sigma$-algebra used in Mörters and Peres book, Brownian Motion defined on p. 42 as
$$\mathcal{F}^+(T) = \{A\in \mathcal{A}: A\cap \{T\leq t\}\in \mathcal{F}^+(t)\text{ for all $t\geq 0$}\}$$
where $\mathcal{A}$ is a $\sigma$-algebra and $\mathcal{F}^+(t)$ is a filtration related to Brownian motion via
$$\mathcal{F}^+(t) = \bigcap_{s>t}\sigma(B(\tau):0\leq \tau\leq s).$$
Now on p. 43 they claim that $\{B(t): t\leq T\}$ is $\mathcal{F}^+(T)$ measurable. However I'm confused as to what this means. $\mathcal{F}^+(T)$ is clearly a $\sigma$-algebra on $\Omega$ while $\{B(t):t\leq T\}$ is for each $\omega\in \Omega$ a subset of $\mathbb{R}$? Could someone clarify this for me?

答:
Measurability is defined in terms of preimages. In probability we often use more compact notation for the events that we consider, both because it aligns with our intuition and because it alleviates the notation.

We have for example
\begin{align*} \sigma ( B(\tau) : 0 \leq \tau \leq s) &=  \sigma (\lbrace B(\tau) \in B \rbrace: 0\leq \tau \leq s, B\in\mathcal{B}(\mathbb{R})) \\
&= \sigma (B(\tau)^{-1}(B):0\leq \tau \leq s, B \in \mathcal{B}(\mathbb{R})) \end{align*}
and now it is more clear that the $\sigma$-algebra is actually generated by sets in $\Omega$.

Regarding the set $\lbrace B(t):t\leq T\rbrace$ it seems to me that this is defined on the path space in the same way that the process $\lbrace B(t):t\geq 0\rbrace$ would be. So $B(\cdot,\omega)$ is considered a mapping from $\Omega$ to the space of continuous functions $C([0,\infty),\mathbb{R}) $.


问:
Another pigeonhole principle question
Have another question for you today:

A course has seven elective topics, and students must complete exactly three of them in order to pass the course. If 200 students passed the course, show that at least 6 of them must have completed the same electives as each other.

Now I know this is related to counting and the pigeonhole principle, and there are a couple of other related questions already asked but I couldn't apply them to my quuestion.

I know that the (informal) pigeonhole principle states that if you have $n$ boxes, and you have more than $n$ pigeons to distribute between those boxes, then at least one of the boxes will contain more than one pigeons, but I'm not sure what my boxes and what my pigeons are in this problem

答:
Let us first count the number of topic choices. There are 7 course and a student must choose 3 among them. Therefore there are $$ {7 \choose 3} = 35$$ such choices.

Now there are 200 students. Suppose that there are at most 5 students that have completed the same electives as each other. We have $$5\times 35 =175.$$ But $175<200$ and therefore at least 6 students have completed the same electives.

Title: Another pigeonhole principle question


问:
Why is $ab + bc + c\bar{a} = ab + c\bar{a}$ true in binary?
I was simplifying the equation of a logic gates problem and I realized that ab + bc + cā and ab + cā followed the same truth table which is the following:

```
-----------------
| A | B | C | S |
-----------------
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
-----------------
```

The problem is that I haven't found any way to get to the simplified expression from the main one by applying boolean algebra procedures. Any idea? Thanks.

答: Note that $b \land c$ is the disjoint union of $b \land c \land a$ and $b \land c \land \bar a$. The first of these is contained in $a \land b$, while the second is contained in $c \land \bar a$.</p>


问:
How to abbreviate $a_0=a_1=\cdots=a_n$?
We write $\sum_{j=0}^n a_j =a_0+a_1+\cdots+a_n$ or $\prod_{j=0}^n a_j=a_0\cdot a_1 \cdots a_n$.

How to abbreviate $a_0=a_1=\cdots=a_n$?

Maybe ${\Large =}| _{j=0}^n a_j$? Or $\{\forall j,k| a_j=a_k\}$...

答:
As there is already:

$\displaystyle\sum_i x_i$, $\displaystyle\prod_i x_i$, $\displaystyle\coprod_i x_i$, $\dots$

$\displaystyle\bigcup_i X_i$, $\displaystyle\bigcap_i X_i$, $\dots$

And one can also define things like:

$\underset{i}{+}\; x_i$, $\underset{i}{-}\; x_i$, $\underset{i}{\times}\; x_i$, $\dots$

for pretty much any operator, I suggest doing the same for comparation operators:

$\underset{i}{\Large =} x_i$, $\underset{i} > x_i$, $\underset{i} < x_i$, $\dots$

$\underset{i} \neq x_i$, $\underset{i} \ge x_i$, $\underset{i} \le x_i$, $\dots$

$\underset{i} \approx x_i$, $\underset{i} \equiv x_i$, $\underset{i} \cong x_i$, $\dots$

Therefore, are valid solutions the following:

$\overset{i = n}{\underset{i = 0}{\Large =}} a_i$

$a_0 \overset{i = n}{\underset{i = 1}{\Large =}} a_i$

Title: How to abbreviate $a_0=a_1=\cdots=a_n$?


问:
Prove: $(L_0)^0 = L$
Let $W \subseteq V$ and $L \subseteq V^{*}$.

Let $W^0 = \{ f\in V^{*} \mid f(w)=0 ~~ \forall w \in W \}$ be the annihilator of $W$.

Let $L_0 = \{ v\in V \mid f(v)=0 ~~ \forall f \in L \}$.

How can I show that $(L_0)^0=L$ ?

What is the name of $L_0$ ? (Like $W^0$ is the annihilator of $W$)

Thank you.

答:
Lemma: Suppose $\Lambda_1,...,\Lambda_n$  and $\Lambda$ are linear functionls
on a vector space $X$. Let $N=\bigcap_{i=1}^n \ker
 \Lambda_i$ and $\Lambda(N)=\{0\}$. Then there are scalras
$c_1,...,c_n$ such that $\Lambda=\sum_{i=1}^nc_i\Lambda_i$.

Proof: Let $\Phi$ be our scalar field. Define $\pi: X\to \Phi^n$ by $\pi(x)=(\Lambda_1x,...,\Lambda_nx)$. Note that $\pi(x)=\pi(x')$ implies $\Lambda x=\Lambda x'$, so we have well-defined linear functional $f:\pi(X)\to\Phi$ given by $f\big(\pi(x)\big)=\Lambda x$. Extend the linear functional $f$ to a linear functional $F$ on $\Phi^n$: there are scalars $c_1,..., c_n\in \Phi$  with $F(u_1,...,u_n)= c_1u_1+...c_nu_n.$ Thus, $$\Lambda x= f\big(\pi(x)\big)=F(\Lambda_1 x,...,\Lambda_n x)=\sum_{i=1}^n c_i \Lambda_i x.$$

To prove $(i)$ consider $L_0=\bigcap_{f\in L}f^{-1}(0)=\bigcap_{f\in \text{span}(L)}f^{-1}(0)$. Note that if we assume $V$ is finite-dimensional, then $V^*$ will be finite-dimensional, so $\text{span}(L)$ also.  Now, considering a basis $\{\Lambda_1,...,\Lambda_n\}$ of $\text{span}(L)$ we have  $$g\in (L_0)^0\iff g(L_0)=0$$$$\iff g\bigg(\bigcap_{f\in L}f^{-1}(0)\bigg)=0\iff g\bigg(\bigcap_{f\in \text{span}(L)}f^{-1}(0)\bigg)=0$$$$\iff g\bigg(\bigcap_{i=1}^n\Lambda_i^{-1}(0)\bigg)=0\iff g=\sum_{i=1}^n c_i \Lambda_i\text{ for some scalars }c_i$$$$\iff g\in \text{span}(L).$$ So, if I  assume from the beginning that $L$ is a vector space then $\text{span}(L)=L$, and we are done.

$(ii)$ Note that $L_0$ is the intersections of some hyperspaces of $V$.  In a vector space of dimension $n$, a subspace of dimension $n-1$ is called a hyperspace.

Title: Prove: $(L_0)^0 = L$


问:
Prove that if $|g(x)|\leq a\big( 1+x \big)^{-n-b}$ then $g\in L^1(\mathbb{R^n})$
I am asked to prove that if $g:\mathbb{R}^n \to [-\infty, \infty]$ is a measurable function that satisfies $|g(x)| \le a(1+|x|)^{-n-b}$ for some constants $a, b >0$, then $g \in L^1(\mathbb{R}^n)$.

I am thinking this is not true because for example if $n=1$, $a=1$ and $b=3$, then if we pick $g(x)=a(1+|x|)^{-n-b}$ the integral $ \displaystyle \int_{\mathbb{R}}(1+x)^{-4}$ is divergent so $g \notin  L^1(\mathbb{R})$. But I am probably missing something so help would be appreciated.

答: Hint: consider set $B(0,1) \cup (\cup_{k=1}^\infty B(0,2^k)\setminus B(0,2^{k-1}))$


问:
What a graph should look like with a diameter at least 5 times the average shortest path length?
I need to find what a graph should look like with a diameter at least 5 times the average shortest path length. I understand that it must be a compete graph with a long tail, cause with longer tail diameter will grow faster than the average shortest path length. But I don't know how to find exact number of nodes of that graph. How many nodes there must be in complete graph and how many in tail? Could I define those numbers using formulas of graph diameter and average shortest path length?

By experiments and iterations, I found that complete graph with 100 nodes and tail with 11 nodes has diameter 12 and  average shortest path length 2.097, so it is 5 times larger, but how to find it using math?

答:
If you just want to find one example of such a graph, your idea works : take a huge complete graph (mean path length is $1$), add small tail (it shouldn't change the mean path length because the tail vertex are rare), and it should work.

The exact value of the average path length on such a model can be computed by hand by a case disjunction (both ends are in the complete part, or one end in the complete and the other in the tail, or both in the tail), but I'm not sure I want to do it. But it's interesting to see how this works asymptotically. If you have $n$ nodes in the "complete" part and $k$ in the tail, you'll have approximately (up to corrective terms, the expected path length in a class is just an approximate value) :

$\frac 1 {(n+k)^2} \left [ n^2*1 + 2nk*\frac k 2 + k^2*\frac k 3 \right ]$

To have something close to 1, you need that $nk^2 + k^3 \ll (n+k)^2$ so $k \ll \sqrt n$.

If you want even more "efficiency" (small complete graph compared to the ratio diameter/path length), I'd suggest having two tails instead of one : you should have an average path length about twice as small with the same diameter.
It's the same as placing the complete graph in the middle of the path, so that the central term in the sum becomes $2nk*\frac k 4$.

Anyway, those are not the only graphs that will give you such properties.
An Erdös-Renyi graph with fixed average degree $\ge 3$ will have an average path length in $\log(n)$, and you could use that instead of the complete part of your graph and still have small ratios.


问:
If $I - A$ is invertible, is $\rho(A) < 1$?
I know that if $\rho(A) < 1$ then $I-A$ is invertible but I am stuck with the opposite direction. So far I have only shown the trivial $\rho(A) \neq 1$. Any hints?

答:
So far I have only shown the trivial $\rho(A) \neq 1$.

Well, $I-(-I)$ is invertible and $\rho(-I)=1$...


问:
A different music "shuffle" feature
Suppose every friday night you like going in a lounge bar and drink some soft drinks. Usually you spend $t$ minutes (say, $120$) there and talking to the bartender you know that there are exactly $N$ songs (say, $100$), of $3$ minutes each, in the playlist that keeps the typical atmosphere. The algorithm of the player is made such that once a song is played, it can't be played until other $n$ (say, $20$) different songs are played, then the probability of the choice of that song returns uniform as before.

What is the probability that you'll listen to the same song twice?

Honestly I do not know how to attack this problem, I saw that this kind of problems can have solutions that are "very strange" but still beautiful.

答:
Let's calculate the probability that all the songs played will be different. The probability of hearing at least one repeated song is then $1$ minus that probability.

The first $n+1$ songs will always be different because of the shuffle algorithm.

The next song cannot be any of the previous $n$ songs, but could be any one of the other $N-n$ songs, $1$ of which you have heard before. So the probability that song $n+2$ differs is $\frac{N-n-1}{N-n}$.

The song after that cannot be any of the previous $n$ songs, but could be any one of the other $N-n$ songs, $2$ of which you have heard before. So the probability that song $n+3$ differs is $\frac{N-n-2}{N-n}$.

The song after that cannot be any of the previous $n$ songs, but could be any one of the other $N-n$ songs, $3$ of which you have heard before. So the probability that song $n+4$ differs is $\frac{N-n-3}{N-n}$.

This continues until you have heard $T=\frac{t}{3}$ songs.

I'll leave you to finish this off.

Title: A different music "shuffle" feature


问:
Counting all possible arrangements
I try to solve the following counting problem:

We consider a new type of gamble. In this one there are 7 red balls, 5 blue balls and 3 purple balls. The presenter now rolls a 4-sided die for each red ball, an 8-sided die for each blue ball, and a 12-sided die for each purple ball, and writes the result on the ball. The 15 balls are then placed together in a box. How many possible arrangements of the balls can be created in this way when drawing? Assume that the balls cannot be distinguished by handwriting.

What I did so far:
First, I counted the number of possibilities in which the balls can be numbered. I think there are $12^3\cdot 8^5\cdot 4^7$ possibilities. Now it only remains to count the possible arrangements of the balls.

If any two balls would always be distinguishable, we would have $15!$ possibilities. Thus the answer would be $n:=15!\cdot 12^3\cdot 8^5\cdot 4^7$. But unfortunately it may happen that the balls are indistinguishable (when their color and number coincide). So the answer must be less than $n$, because we effectively counted some events multiple times. But in my head everything becomes so foggy at this point. How to deal with those cases?

答:
The answer to your problem is
$$n=\frac{15!}{3!\cdot5!\cdot7!}\cdot 12^3\cdot 8^5\cdot 4^7.\tag1$$

A simple argument leading to (1) is the following. First arrange the unnumbered balls and then number them choosing the range according to the color.

The same result may be obtained in a much more complicated algebraic way as follows.

After numbering the balls they have two properties: color and number. Two balls which share both color and number are indistinguishable and we will denote the number of such balls as $k_{ij}$, where $i$ and $j$ stay for color and number respectively. $k_{ij}$ can be arbitrary non-negative integer numbers subject to the condition
$$
\sum_{j=1}^{J_i} k_{ij}=K_i\tag2,
$$
where $K_i$ and $J_i$ are the number of balls of the $i$-th color and the range of numbers which can be assigned to these balls, respectively.

With these definitions the total number of possible combinations is ($m$ is the number of colors, $K=\sum_{i=1}^m K_m$ is the number of balls):
$$\begin{align}
n&=\sum_{k_{ij}}^{(2)}\frac{K!}{\prod\limits_{i=1}^m\prod\limits_{j=1}^{J_i} k_{ij}!}\\
&=\sum_{k_{ij}}^{(2)}\frac{K!}{\prod\limits_{i=1}^m K_i!}
\prod\limits_{i=1}^m\frac{K_i!}{\prod\limits_{j=1}^{J_i} k_{ij}!}\\
&=\frac{K!}{\prod\limits_{i=1}^m K_i!}
\prod\limits_{i=1}^m\sum_{k_{ij}}^{(2)}\frac{K_i!}{\prod\limits_{j=1}^{J_i} k_{ij}!}\\
&=\frac{K!}{\prod\limits_{i=1}^m K_i!}\prod\limits_{i=1}^m J_i^{K_i}.\tag3
\end{align}$$

Title: Counting all possible arrangements


问:
$K$-derivation $\delta_\alpha: N^{-1}R[x]\to N^{-1}R[x]$ with $\delta_{\alpha}(x)=\alpha$
I'm reading Kähler Differentials written by Ernst Kunz. There is an exercise in its first chapter: Let $R$ be a $K$-algebra and $\delta:R\to R$ a $K$-derivation. Let $N\subset R[x]$ be multiplicatively closed and $\alpha\in N^{-1}R[x].$ There is precisely one derivation $\delta_\alpha: N^{-1}R[x]\to N^{-1}R[x]$ with $\delta_{\alpha}(x)=\alpha$ such that the below diagram

is commutative. I have extended $\delta$ to $\bar{\delta}$ and $d$, which the first one is determined uniquely, but my problem is with showing that $d$ is unique.

Let $\bar{\delta}:R[x] \to N^{-1}R[x]$ be an extension of $\delta$ that maps $x$ to $\alpha$, and $\bar{\delta}(r)=\dfrac{\delta r}{1}$ (for $r\in R$). Image of an arbitrary member of $R[x]$ can be uniquely determined by the definition of $\bar{\delta}$, using the Leibniz rule. And the below digram is commutative:

Let $d: N^{-1}R[x]\to N^{-1}R[x]$ be an extension of $\bar{\delta}$:
$d(\dfrac{f_1}{f_2}):=(f_2\bar{\delta}(f_1)-f_1\bar{\delta}(f_2))(f_2^2)^{-1}$. Where the inverse is taken in $N^{-1}R[x]$; $d$ satisfies the Leibniz rule and the below diagram is commutative:

Edit: Thanks for the answer

Let $r=\dfrac{f_1}{f_2}\in N^{-1}R[x]$, we have $r\dfrac{f_2}{1}=\dfrac{f_1}{1}$, $\Rightarrow d(r\dfrac{f_2}{1})=d(\dfrac{f_1}{1})$. Since $d(\dfrac{f_i}{1})=\bar{\delta}(f_i)$, using Leibniz rule we have
$\dfrac{f_2}{1}d(r)+r\bar{\delta}(f_2)= \bar{\delta}(f_1)$. $\Rightarrow d(r)=(\bar{\delta}(f_i)-r\bar{\delta}(f_2))(f_2)^{-1}$; Hence for all $r\in N^{-1}R[x]$, $d(r)$ is determined uniquely.

答: Consider a fraction $f=g/h\in N^{-1}R[x]$.  Then $hf=g$, so $d(g)=d(hf)=fd(h)+hd(f)$ for any derivation $d:N^{-1}R[x]\to N^{-1}R[x]$. But now since $h$ acts as a unit on $N^{-1}R[x]$, we can uniquely solve for $d(f)$: we must have $$d(f)=h^{-1}(d(g)-fd(h))=h^{-2}(hd(g)-gd(h)).$$  So, $d$ is uniquely determined by what it does on elements that come from $R[x]$.


问:
Existence theorem for Laplace's equation.
Regarding Laplace's equations, the following two are my questions:
1) If Dirichlet boundary conditions are specified on the surfaces, is it guaranteed that a solution will exist? Or is there some condition that the boundary conditions themselves must satisfy?
2)  If Neumann boundary conditions are specified on the surfaces, is it guaranteed that a solution will exist? Or is there some condition that the boundary conditions themselves must satisfy?</p>

答:
1) For the Dirichlet problem you don't need compatibility condition, but you need that the boundary is not so bad. For instance, smooth surfaces will work.

2) For the Neumann problem, apart from some smoothness of the boundary, you need a compatibility condition that follows immediately from the divergence theorem (also known as integration by parts):
$$
\int_\Omega \Delta u = \int_{\partial\Omega}\partial_\nu u,
$$
where $\partial_\nu u$ is the outward normal derivative of $u$ at the boundary $\partial\Omega$.


问:
Set of vertices of graph $G$ is power set of $\{0,1,2,3,4,5,6,7,8,9\}$. Two vertices $A,B$ are connected iff $|A \Delta B |\le 2$. Then $|E(G)|=?$

Let the set of vertices of graph $G$ be the power set of $\{0,1,2,3,4,5,6,7,8,9\}$ and two (different) vertices $A,B$ are connected iff $|A \Delta B |\le 2$. How many edges does $G$ have?

I just need proof verification:

If $|A\Delta B|=0$ then there is no edges.

If $|A\Delta B|=1$ then there is ${10\choose 1}$ choises for $A\setminus B$ and $2^9$ for $A\cap B$ so we have $10\cdot 2^9$ edges.

If $|A\Delta B|=2$ then we have 2 subcases:

If $|A\setminus B| =2$ then there is ${10\choose 2}$ choises for $A\setminus B$ and $2^8$ for $A\cap B$ so we have $45\cdot 2^8$ edges.

If $|A\setminus B| =1$ and $|B\setminus A| =1$ then there is ${10\choose 2}$ choises for $A\Delta B$ and $2^8$ for $A\cap B$ so we have again $45\cdot 2^8$ edges.

So we have overall $110\cdot 2^8$ edges?

答:
This looks right. I would add the preliminary statement for clarity:

For ensuring edges are only counted once, assume $|A|\geq|B|$

Then the rest follows

If $|A\triangle B|=0$ then $A=B$ and there is no edge.

If $|A\triangle B|=1$ then there are ${10\choose 1}$ choices for $A\setminus B$ and $2^9$ for $A\cap B$ so we have $10\cdot 2^9$ edges.

If $|A\triangle B|=2$ then there are $2^8$ choices for $A\cap B$ and either:

the ${10\choose 2}=45 $ choices for $A\triangle B$ are in $A$, giving $45\cdot 2^8$ edges or

the ${10\choose 2}$ choices for $A\triangle B$ are split between $A$ and $B$ (at each end of an edge)  giving another $45\cdot 2^8$ edges

So a total of $55\cdot 2^9$ edes as you found.


问:
Elementary proof that the limit of $\sum_{i=1}^{\infty} \frac{1}{\operatorname{lcm}(1,2,...,i)}$ is irrational
Show that the infinite sum $S$ defined by -$$S=\sum_{i=1}^\infty \frac{1}{\operatorname{lcm}(1,2,...,i)}$$ is an irrational number.

I found this question while reading 'Mathematical Gems' by Ross Honsberger. After pondering over it for nearly an hour, I was able to prove it by using Bertrand's postulate which states that there is a prime between n and 2n for every natural number n>1.

This question was solved by Lajos Pósa when he was just 12 years old. Is there any elementary proof that does not use Bertrand's postulate or any complicated theorem?

答:
I know this question is 3 years old. But I have a nice proof that does not require Bertrand's postulate. (One can prove the irrationality of e using this method).

Consider n!S=$\frac{n!}{2}$+$\frac{n!}{6}$+$\frac{n!}{12}$+... . Also note that lcm(1,...n) $\leq$ n!, and gcd(a,a+2)=1, for all a in Z. Splitting this sum as

n!S=($\frac{n!}{2}$+$\frac{n!}{6}$+$\frac{n!}{12}$+...+$\frac{n!}{lcm(1,,n)}$)+$\frac{n!}{lcm(1,...,n+1)}$+$\frac{n!}{lcm(1,...,n+2)}$+... , we notice that $\frac{n!}{lcm(1,...,n+1)}$ might be an integer, but $\frac{n!}{lcm(1,...,n+2)}$ never is an integer, since gcd(a,a+2)=1. Thus we have everything after $\frac{n!}{lcm(1,...,n+1)}$ may not be an integer, since it is all <1.

EDIT: I MADE A MISTAKE! Assume S=$\frac{a}{b}$ and then multiply by b!, not any n!. So replace n with b, and we are done. I also assumed that gcd(a,a+2)=1. This is only true for a is odd. If a is even, gcd(a,a+1)=1. So it depends on the parity of a. So this argument still works.


问:
Distribution of Digit Products
A digit product $P(n)$ of a natural number $n$ is given by the product of its decimal digits. For example:

$$P(1234) = 24,\;\;\; P(24) = 8,\;\;\; P(8) = 8$$
$$1\times2\times3\times4 = 24, \;\;\; 2\times4 = 8$$

Clearly $P(x) \leq x$ as a number with digits "abcd..." gives a product less than $a\times10\times10\times10...$. So

$$P(x) < x\;\;\; \text{or}\;\;\; P(x) < 10$$

Letting $P^n(x)$ represent applying $P$ $n$ times, I have a question about $$P^\infty(x) = \lim_{n\rightarrow\infty}P^n(x)$$

The larger the number the more likely it is that it will contain a zero. So, for a random $x$ we expect that almost always $P^\infty(x)=0$. But we can get rid of all these from the number line:

$$S = \{x\in\mathbb{N}_0|P^\infty(x)\neq0\}$$

What is the distribution of $P^\infty(s)$ for $s\in S$? How likely are the remaining digits? Is one infinitely more likely than the others?

Here's a graph of $10$ to $1,000,000$:

答:
Let $$T=\{n | 0,1~\mathrm{do~not~occur~in~the~decimal~expansion~of~n}\}$$

I'll make this Conjecture: $T\cap S$ is finite.

That is, there are only finitely many $n$ that don't have the digit 1 in their decimal representation and that have $P^\infty(n)>0$.

The case where all of the digits are the same (and not 1) is covered by a long-standing conjecture of Furstenberg (Conjecture 2' on page 25 of this paper I cited in my answer to this tangentially related question), which says that large enough powers of any number (not a power of 10) contain any finite pattern of digits.

In particular for this problem, for $2\le d \le 9$ there is a $K(d)$ large enough such $d^k$ has a zero in its decimal expansion for $k>K(d)$ and so the decimal numbers $n=ddd\cdots d$ with $k$ repeated $d$s have $P^2(n)=0$.

I think this can be generalized to the case where different digits are allowed, but I only have a very abstract argument. All patterns of digits appear in large powers of $d_1$ because the decimal representation for $d_1^{k_1}$ is "random" in some sense, and multiplying by another $d_2^{k_2}$ gives something else that is still random (unless 10 divides $d_1\times d_2$). So for $k_1+k_2$ large enough $n=d_1^{k_1}d_2^{k_2}$ will contain a zero in its decimal expansion. And continuing the argument, for $k_1+k_2+k_3+k_4$ large enough every $n\in T$ with
$$
P(n)=2^{a_1}3^{a_2}4^{a_2}5^{a_2}6^{a_2}7^{a_2}8^{a_2}9^{a_2} = 2^{k_1}3^{k_2}5^{k_3}7^{k_4}
$$
will contain a zero in its decimal expansion and will have $P^2(n)=0$.

A computer check of exponents up to 200 suggests that the largest value $k_1+k_2+k_3+k_4$ can take is 44, and the largest $n\in T$ with $P^\infty(n)\ne 0$ have $P(n)=2^{39}3^3 7^2$.

Let $L(n)$ be the number of digits in the decimal representation of $n$.

Given $n\in T$ with $L(n)<N$, we can mix the digits of $n$ with $N-L(n)$ additional 1 digits to get $N$-digit numbers $n_1,n_2,\dots$ with $P(n)=P(n_1)=P(n_2)=\cdots$. For example, let $n=2677,N=10$, and
$$
n_2=1111112677, n_2=1111771216, n_3=7172611111, \ldots \\
P(n)=588=P(n_1)=P(n_2)=P(n_3)=\cdots
$$
If the number distinct permutations of the digits of $n$ is $L(n)!/R(n)$, then the number of ways we can generate $N$-digit numbers from $n$ this way is
$$
c(n,N) = \frac{N!}{(N-L(n))!R(n)} = \frac{N^{L(n)}}{R(n)}-O(N^{L(n)-1})
$$
In our example $c(2677,N)=N^4/2-O(N^3)$.

Operating under the conjecture that $L(n)$ is bounded for $n\in T\cap S$, for large $N$ the $N$-digit numbers in $S$ will be mainly composed of $1s$, and their count will be dominated by $N^{L(n)}$ for the longest $n$s.

My computer search turned up the longest $n$ as follows:
$$
\begin{array}{c|c|c|c}
P^\infty(n) & P(n) & L(n) & c(n,N) \\
\hline
2 & 2^{26}3^3 & 29 & N^{29}/(2.4\times 10^{27}) \\
3 & 3 & 1 & N \\
4 & 2^{23}3^7 7 & 31 & N^{31}/(1.3\times 10^{26}) \\
5 & 3^5 5 7^2 & 8 & N^8/240\\
6 & 2^{24} 3^6 7^6 & 36 & N^{36}/(3.2\times 10^{29}) \\
7 & 7 & 1 & N \\
8 & 2^{39} 3^3 7^2 & 44 & N^{44}/(2.4\times 10^{47})\\
9 & 3^2 & 2 & N^2/2
\end{array}
$$
where the right column gives the asymptotic behavior for very large $N$. There is also only one $N$-digit number consisting of all 1s with $P(n)=1$.

So even though up to 50 million the histogram shows a pattern similar to yours:
$$
\begin{array}{c|c|c|c|c|c|c|c|c|c}
P^\infty & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
\mathrm{count} & 8 & 317446 & 36 & 27070 & 16325 & 1336881 & 35 & 697581 & 119
\end{array}
$$
my results suggest that eventually $P^\infty=4$ will dominate $P^\infty=2$, and in the large $N$ limit almost all of $S$ will be made up of numbers with thirty-nine 2s, three 3s, two 7s and a large number of 1s, each with $P^\infty=8$.

Title: Distribution of Digit Products


问:
Estimations of some new recurrence sequences

Problem 1. Given the recursion $a_{n+ 1}= \sqrt{a_{n}^{2}+ a_{n}}$ with $a_{1}= 1.$ Prove that
$$a_{n}\sim\frac{n}{2}+ \frac{1}{2n}\,{\rm as}\,n\rightarrow\infty$$

For problem 1, I only can prove $a_{n}\sim\left ( n+ 1 \right )/2$ by using the Laurent series for the increasing $a_{n} :$
$$a_{n+ 1}= a_{n}+ \dfrac{1}{2}+ \mathcal{O}\left ( \dfrac{1}{a_{n}} \right )$$

Problem 2. Given the recursion $a_{n+ 1}= \sqrt[3]{a_{n}^{3}+ a_{n}}$ with $a_{1}= 1.$ Prove that
$$a_{n+ 1}\sim\sqrt{\dfrac{2n}{3}}\,{\rm as}\,n\rightarrow\infty$$
What if we changed the given one by $a_{n+ 1}= \sqrt[3]{a_{n}^{3}+ 3a_{n}^{2}+ a_{n}}$ ?

For problem 2, similarly, I saw that $a_{n+ 1}\fallingdotseq a_{n}+ \dfrac{1}{3a_{n}}$, then how can we find the relative equations like ${y}'= \dfrac{1}{3y}$ by $n$ times ?

答:
We may use the approach in [1].

For Problem 1:

First, clearly $\lim_{n\to \infty} a_n = \infty$.

Second, we have
\begin{align}
a_{n+1} - a_n &= \sqrt{a_n^2 + a_n} - a_n\\
&= a_n\left(\sqrt{1 + \frac{1}{a_n}} - 1\right)\\
&= a_n\left(1 + \frac{1}{2} \frac{1}{a_n}
+ o\left(\frac{1}{a_n}\right) - 1\right)\\
&\to \frac{1}{2},\quad \mathrm{as}\ n\to \infty.
\end{align}
Thus, $a_n \sim \frac{n}{2}$ as $n\to \infty$.

Third, we have
\begin{align}
a_{n+1} - a_n &= \sqrt{a_n^2 + a_n} - a_n\\
&= a_n\left(\sqrt{1 + \frac{1}{a_n}} - 1\right)\\
&= a_n\left(1 + \frac{1}{2} \frac{1}{a_n} - \frac{1}{8}\frac{1}{a_n^2}
+ o\left(\frac{1}{a_n^2}\right) - 1\right)\\
&\sim \frac{1}{2} - \frac{1}{8}\frac{1}{a_n}, \quad \mathrm{as}\ n\to \infty\\
&\sim \frac{1}{2} - \frac{1}{4n}, \quad \mathrm{as}\ n\to \infty.
\end{align}
Thus, $a_n \sim \frac{n}{2} - \frac{1}{4}\ln n$ as $n\to \infty$.

$\phantom{2}$

For problem 2:

First, clearly $\lim_{n\to \infty} a_n = \infty$.

Second, we have
\begin{align}
a_{n+1}^2 - a_n^2 &= (\sqrt[3]{a_n^3 + a_n})^2 - a_n^2 \\
&= a_n^2 \left(\left(1 + \frac{1}{a_n^2}\right)^{2/3} - 1\right)\\
&= a_n^2 \left(1 + \frac{2}{3} \frac{1}{a_n^2} + o\left(\frac{1}{a_n^2}\right) - 1\right)\\
&\to \frac{2}{3}, \quad \mathrm{as}\ n\to \infty.
\end{align}
Thus, $a_n^2 \sim \frac{2}{3}n$ as $n\to \infty$.
Thus, $a_n \sim \sqrt{\frac{2}{3}n}$ as $n\to \infty$.

Reference

[1] "The second term in asymptotic expansion", by Moubinool OMARJEE, Paris


答: Another method. First, note the number of ordered pairs $(A,B)$, where $A,B\subseteq [0,9]\cap \mathbb Z$ and $|A\Delta B|=k$, is $2^{10}\binom{n}k$. You choose the elements of $|A\cap B|$ in $\binom{n}k$ ways, and independently choose the subset $A$ in $2^{10}$ ways. The choice of $A\Delta B$ and $A$ determines $B$. Adding up $k=1$ and $k=2$, and dividing by two to get unordered pairs, you get $\frac12(2^{10}\binom{10}1+2^{10}\binom{10}2)$, agreeing with your answer.

Title: Set of vertices of graph $G$ is power set of $\{0,1,2,3,4,5,6,7,8,9\}$. Two vertices $A,B$ are connected iff $|A \Delta B |\le 2$. Then $|E(G)|=?$

Body:
Let the set of vertices of graph $G$ be the power set of $\{0,1,2,3,4,5,6,7,8,9\}$ and two (different) vertices $A,B$ are connected iff $|A \Delta B |\le 2$. How many edges does $G$ have?

I just need proof verification:

If $|A\Delta B|=0$ then there is no edges.

If $|A\Delta B|=1$ then there is ${10\choose 1}$ choises for $A\setminus B$ and $2^9$ for $A\cap B$ so we have $10\cdot 2^9$ edges.

If $|A\Delta B|=2$ then we have 2 subcases:

If $|A\setminus B| =2$ then there is ${10\choose 2}$ choises for $A\setminus B$ and $2^8$ for $A\cap B$ so we have $45\cdot 2^8$ edges.

If $|A\setminus B| =1$ and $|B\setminus A| =1$ then there is ${10\choose 2}$ choises for $A\Delta B$ and $2^8$ for $A\cap B$ so we have again $45\cdot 2^8$ edges.

So we have overall $110\cdot 2^8$ edges?


问:
Dixmier's explanation of why $L^1(G)$ is not a $C^*$-algebra
I've recently been learning some basic facts about $C^*$-algebras and their connections to representations of locally compact groups $G$, and I'm currently trying to understand the definition of the $C^*$-algebra of a group, which is obtained from the algebra $L^1(G)$ by completion.

Question: Why do we need to complete $L^1(G)$ to form the $C^*$-algebra of $G$?

It's easy to see that the only axiom of a $C^*$-algebra that could possibly fail is the crucial identity $\|T^*T\| = \|T\|^2$, so in one sense, my question is asking why this axiom fails. By playing around with simple examples it is easy to see that the axiom fails for $G=\mathbb Z$ (Why is $\ell^1(\mathbb{Z})$ not a $C^{*}$-algebra?).

More generally, Dixmier has an argument that appears to work for any abelian $G$, though I don't understand it. He considers the left regular action $\lambda$ of $G$ on $L^2(G)$. It is easy to see that $\|\lambda(f)\|=\|\hat f\|_\infty$, where $\hat f$ is the Fourier transform of $f$. Since $\|f\|_\infty\neq\|f\|_1$ in general, this means that $\lambda$ is not isometric. All this I understand. But then Dixmier concludes that $L^1(G)$ is not a $C^*$-algebra, and this is where he loses me.

Can anyone clarify Dixmier's argument? (Is it true that morphisms of $C^*$-algebras are isometries, even though this is not required as part of the definition of a morphism?) Or more generally, does anyone have a good "moral" explanation as to why $L^1(G)$ is not a $C^*$-algebra and we have to pass to its $C^*$-enveloping algebra?

答:
In [1], one will find the following:

II.2.2.9 Corollary. Let $A$ and $B$ be C*-algebras, $\varphi  : A \to  B$ an injective
*-homomorphism. Then $\varphi $ is isometric, i.e. $\|\varphi (x)\| = \|x\|$ for all $x \in  A$.

[1] Blackadar, Bruce, Operator algebras. Theory of C$^*$-algebras and von Neumann algebras, Encyclopaedia of Mathematical Sciences 122. Operator Algebras and Non-Commutative Geometry 3. Berlin: Springer (ISBN 3-540-28486-9/hbk). xx, 517 p. (2006). ZBL1092.46003.


问:
Are $\exists ! (x,y)$ and $\exists ! x \exists ! y$ equivalent?
Here I have the following definition of $\exists ! (x,y) P(x,y)$:

$$\exists x \exists y[P(x,y) \land \lnot \exists u \exists v (P (u,v) \land (u \neq x \lor v \neq y))]$$

Are that formula equivalent to $\exists ! x \exists ! yP(x,y)$ ?

I'm using that $\exists ! xP(x)$ is equivalent to:

$$\exists x (P(x) \land \lnot \exists u (P(u) \land u \neq x)$$

I could not prove them equivalent, but don't know how to prove that it's not equivalent.

答:
They are different. $\exists!x\exists!y$ allows for the possibility that $P(x,y)$ is true for all $x$ and $y$ except for one particular value of $x$, for which it's $P(x,y)$ is true for one particular value of $y$ but false for all other values.

Added later: As an example, picture a set of keys (on a keyring, say) and a set of doors (along a hallway, say). The proposition $P(x,y)$ says that key $x$ unlocks door $y$. The statement $\exists!(x,y)P(x,y)$ then says that there's one key that unlocks one (and only one) door while the rest of the keys are useless (i.e., don't unlock any of the doors). The statement $\exists!x\exists!yP(x,y)$, on the other hand, says that there's one key that unlocks one (and only one) door while the other keys are either useless or unlock multiple doors.


答:
"There is exactly one pair of people $x$ and $y$ at this party such that $x$ is friends with $y$.

is not the same as

"There is exactly one person $x$ at this party such that there is exactly one person $y$ at this party such that $x$ is friends with $y$.

At the first party, $x$ is the only person with a friend. At the second party, poor $x$ only has one friend, but everybody else is free to have lots of friends (or no friends).

For this "real life" example to  work, the "friends with" relation must not be symmetric. But I think that's not too unrealistic.

Title: Are $\exists ! (x,y)$ and $\exists ! x \exists ! y$ equivalent?

Body:
Here I have the following definition of $\exists ! (x,y) P(x,y)$:

$$\exists x \exists y[P(x,y) \land \lnot \exists u \exists v (P (u,v) \land (u \neq x \lor v \neq y))]$$

Are that formula equivalent to $\exists ! x \exists ! yP(x,y)$ ?

I'm using that $\exists ! xP(x)$ is equivalent to:

$$\exists x (P(x) \land \lnot \exists u (P(u) \land u \neq x)$$

I could not prove them equivalent, but don't know how to prove that it's not equivalent.


答:
Nope, they are not equivalent.

Consider $x,y\in\{0,1\}$ and the condition $xy=0$. Then

$\exists! (x,y):xy=0$ is false (there are three such points),

$\exists! x:\exists! y:xy=0$ is true (for $x=0$, there are two points such that the condition holds, and for $x=1$, only one, so a single $x$ fits).


答:
Let $P(x,y)$ be defined by $y^2 = x$.

Then $\exists!(x,y)P(x,y)$ is false, since there are infinitely many pairs $(x,y)$ that solve the equation.

However, $\exists!x(\exists!yP(x,y))$ is true, since if and only if $x=0$, there is only one $y$ that solves the equation ($y=0$ obviously).


问:
Nash Equilibrium - El Farol Bar Problem
Statement of the problem, from Wikipedia:

Every Thursday night, a fixed population want to go have fun at the El Farol Bar, unless it's too crowded.
If less than 60% of the population go to the bar, they'll all have more fun than if they stayed home.
If more than 60% of the population go to the bar, they'll all have less fun than if they stayed home.
Everyone must decide at the same time whether to go or not, with no knowledge of others' choices.

Is the following solution a Nash Equilibrium?

Each individual rolls a die of 60 faces. If the outcome is 1 they go to the bar, if the outcome is not 1 they stay home.

I am not sure if it can be considered a Nash Equilibrium since I have arguments against it and in favour. This solution does not require cooperation and it is the best way to ensure that they will have fun. On the other hand all the Nash Equilibrium solutions that I have seen so far use utility values to assign probabilities to each action to define the best strategy.

答:
Suppose the number of people in the population is $\ N\ $, and it's not a multiple of $10$ (so you don't have to bother about the payoffs to the participants when exactly $60\%$ of them go to the bar. Let $\ S=\lfloor0.6N\rfloor\ $, so the bar will be too crowded if the number who go to it exceeds $\ S\ $ and won't be too crowded if the number doesn't exceed $\ S\ $.  Let $\ u\ $ be the amount of fun clients will have if they go to an uncrowded bar, $\ c\ $ the amount they will have if they go to a crowded bar, and $\ h\ $ be the amount they will have if they stay home.  I assume $\ u,c,$ and $\ h\ $ have the same value for everyone in the population.  The statement of the problem tells us that $\ u>h>c\ $.

Let
$$
p=\sum_{i=0}^{S-1}{N-1\choose i}\frac{59^{N-1-i}}{60^{N-1}}\ .
$$
This is the probability that $\ S-1\ $ or fewer of a given subset of the population of size $\ N-1\ $ decide to go to the bar when they're all using the strategy described. Any individual in the population has a probability of
$$
\frac{p}{60}
$$
of going to the bar and finding it not too crowded, a probability of
$$
\frac{1-p}{60}
$$
of going to the bar and finding it too crowded, and a probability of
$$
\frac{59}{60}
$$
of staying home. The expected fun of each individual when they all follow the strategy described is therefore
$$
\frac{pu+(1-p)c+59h}{60}\ .
$$
The strategy is a Nash equilibrium if no single individual can increase his expected fun by choosing either definitely to stay home or definitely to go to the bar provided everyone else sticks to the described strategy.

The amount of fun an individual will get by staying home is $\ h\ $, while the expected amount of fun he or she will get by going to the bar when everyone else sticks to the strategy described is $\ pu+(1-p)c\ $. Thus the strategy will be a Nash equilibrium if and only if
\begin{align}
\frac{pu+(1-p)c+59h}{60}&\ge h\hspace{3em}\text{and}\\
\frac{pu+(1-p)c+59h}{60}&\ge pu+(1-p)c\ .
\end{align}
These inequalities are satisfied if and only if $\ pu+(1-p)c=h\ $, or,equivalently $\ p=\frac{h-c}{u-c}\ $.  It's extremely unlikely that this will be the case for any particular given values of $\ N,u,c\ $ and $\ h\ $, and therefore extremely unlikely that the strategy described will be a Nash equilibrium.

However, since $\ 0<\frac{h-c}{u-c}<1\ $, and $\ \mathscr{U}(g)=\sum_\limits{i=0}^{S-1}{N-1\choose i} g^i(1-g)^{N-1-i}\ $ is a strictly decreasing function on $\ [0,1]\ $, with $\ \mathscr{U}(g)=1, \mathscr{U}(1)=0\ $, there is a unique $\ g^*\in(0,1)\ $ such that $\ \mathscr{U}(g*)=\frac{h-c}{u-c}\ $.  If everyone in the population independently chooses a random number $\ \rho\ $ uniformly from the unit interval $\ [0,1]\ $, and goes to the bar if $\ \rho<\mathscr{U}(g*)\ $, then that strategy is a Nash equilibrium.

And you can actually implement this strategy with any die.  If the die has $\ b\ $ sides, labelled $\ 1,2,\dots,b\ $, let $\ t_i\ $ be the result of the $\ i^\text{th}\ $ toss, and keep tossing until either
$$
\mathscr{U}\left(\sum_{i=1}^n\frac{t_i-1}{b^i}\right)<\frac{h-c}{u-c}
$$
or
$$
\mathscr{U}\left(\frac{t_n}{b^n}+\sum_{i=1}^{n-1}\frac{t_i-1}{b^i}\right)>\frac{h-c}{u-c}\ .
$$
One of these events will eventually occur with probability $1$.  If it is one of the latter—which it will be with probability $\ \mathscr{U}(g*)\ $—then you go to the bar, whereas if it is one of the former (probability $\ 1-\mathscr{U}(g*)\ $) you stay home.

Title: Nash Equilibrium - El Farol Bar Problem


问:
Proving $\cosh(\sqrt{1+x^2})$ is not uniformly continuous in $\mathbb{R}$
Given
$f(x) = \cosh(\sqrt{1+x^2})$

I am trying to show that $f(x)$ is not uniformly continuous. Specifically:

$\exists\varepsilon\ \forall\delta\ \exists x,y \in \mathbb{R}: \ |x-y| < \delta \wedge  |f(x) - f(y)| \geq \varepsilon $

So far this is my thought process:

Since $\cosh(\sqrt{1+x^2}) = \frac{\exp(\sqrt{1+x^2})+\exp(-\sqrt{1+x^2})}{2}$, $f(x)$ approaches $\frac{\exp(x)}{2}$ for large enough $x$.

Intuitively I would say that since the derivative of the exponential function is not bounded and increases monotonically, no matter how small we choose $\delta$, for large enough $x$, $f(x+\delta)-f(x)$ is going to surpass any chosen $\varepsilon$.

I am trying to use mean value theorem to calculate the magnitude of $|f(x)-f(y)|$ using $f'$:

$\exists \xi \in ]x,y[:\\f(x) - f(y) = f'(\xi)\cdot(x-y)$

but by doing this, I am introducing an additional variable to the proof.

答: You have\begin{align}\lim_{x\to\infty}f'(x)&=\lim_{x\to\infty}\frac{x\sinh\left(\sqrt{1+x^2}\right)}{\sqrt{1+x^2}}\\&=\infty.\end{align}So, if $\delta>0$, take $x>0$ such that $y\geqslant x\implies f'(x)>\frac1\delta$ and let $y=x+\frac\delta2$. Then $|x-y|=\frac\delta2<\delta$ and\begin{align}\bigl|f(x)-f(y)\bigr|&=\left|\frac{f(x)-f(y)}{x-y}\right||x-y|\\&=\bigl|f'(c)\bigr|\frac\delta2\text{ (for some $c\in(x,y)$)}\\&>\frac12,\end{align}since $f'(c)>\frac1\delta$.


答:
hint

$$\cosh(\sqrt{1+x^2})=\frac 12(e^{\sqrt{1+x^2}}+e^{-\sqrt{1+x^2}})$$

$$=g(x)+h(x)$$

$$\lim_{|x|\to+\infty}h(x)=0\implies $$
$ h$ is uniformly continuous at $\Bbb R$.

So, you just need to prive that $ g $ is Not uniformly continuous .

Title: Proving $\cosh(\sqrt{1+x^2})$ is not uniformly continuous in $\mathbb{R}$

Body:
Given
$f(x) = \cosh(\sqrt{1+x^2})$

I am trying to show that $f(x)$ is not uniformly continuous. Specifically:

$\exists\varepsilon\ \forall\delta\ \exists x,y \in \mathbb{R}: \ |x-y| < \delta \wedge  |f(x) - f(y)| \geq \varepsilon $

So far this is my thought process:

Since $\cosh(\sqrt{1+x^2}) = \frac{\exp(\sqrt{1+x^2})+\exp(-\sqrt{1+x^2})}{2}$, $f(x)$ approaches $\frac{\exp(x)}{2}$ for large enough $x$.

Intuitively I would say that since the derivative of the exponential function is not bounded and increases monotonically, no matter how small we choose $\delta$, for large enough $x$, $f(x+\delta)-f(x)$ is going to surpass any chosen $\varepsilon$.

I am trying to use mean value theorem to calculate the magnitude of $|f(x)-f(y)|$ using $f'$:

$\exists \xi \in ]x,y[:\\f(x) - f(y) = f'(\xi)\cdot(x-y)$

but by doing this, I am introducing an additional variable to the proof.


问:
Understanding Riemannian metrics at points on a manifold that have the 'same' tangent plane
This question came up when I was working through Do Carmo; specifically after the introduction of Riemannian Manifolds and isometries between them.

Take $S^n$ and the antipodal map $A$, for example. To show that $A$ is an isometry, one must show that for all $p$ in $S^n$, the following holds:

$$
<dA_p (u),dA_p(v)>_{-p} = _{p}
$$

It is clear that the left hand side is just $_{-p}$. So the remainder of the proof is showing that the two inner products are the same on antipodal points of the sphere. Visually, this makes sense as if you imagine the tangent planes at antipodal points of $S^2$ as linear subspaces of $\mathbb{R}^3$, they define the same hyperplane. Does it follow that the inner products on these plane given a Riemannian metric must be the same?

The definition of a Riemannian metric I am using here is just a map $<,>_q:T_qS^n\times T_qS^n\rightarrow \mathbb{R}$ such that there is a notion of local differentiability while varying $q$.

Is there a general idea that tangent spaces that lead to the same hyperplanes when considering the manifold as some embedding in Euclidean space lead to the same inner products on these tangent spaces?

答:
If the Riemannian metric you are using here is the restriction of the usual scalar product $\langle\cdot,\cdot\rangle$ of $\mathbb{R}^{n+1}$, that is
$$\langle\cdot,\cdot\rangle_p=\langle\cdot,\cdot\rangle|_{T_pS\times T_pS},$$
then as soon as $T_pS=T_qS$, you will have $\langle\cdot,\cdot\rangle_p=\langle\cdot,\cdot\rangle_q$. This is indeed the case here since $T_pS=p^\perp=(-p)^\perp=T_{-p}S$. If the Riemannian metric depends of the point, then it can no longer be true.


问:
Identity involving a recursive product
Here is yet another problem related to plane partitions. Given the recursive formula

$$
\begin{align*}
F(0)&=1,\\
F(r)&=\prod_{i=1}^r\frac{i+2r-1}{2i+r-2}F(r-1).
\end{align*}
$$

How can we prove

$$F(n)=\prod_{1\leq i\leq j\leq k\leq n}\frac{i+j+k-1}{i+j+k-2}\ ?$$

EDIT: The solution to this problem can be found in the answer section to this question.

答:
First of all, note that, you can write the product as

$$\prod_{i=1}^r\frac{i+2r-1}{2i+r-2}= 2\,{\frac {\Gamma  \left( 3\,r \right) \Gamma \left( \frac{r}{2} \right) }
{{2}^{r+1}\Gamma  \left( \frac{3r}{2} \right) \Gamma  \left( 2\,r \right) }},$$

where $\Gamma(x)$ is the gamma function. Second, you have a first order recurrence relation

$$ F(r) = g(r)F(r-1) $$

which can be solved using the formula.

Notes:

1) $ \prod_{i=1}^r i =r!=\Gamma(r+1). $

2) $ \prod_{i=1}^r \frac{f(i)}{g(i)}=  \frac{\prod_{i=1}^rf(i)}{\prod_{i=1}^rg(i)}.  $

Title: Identity involving a recursive product