问:
Why am I getting a 3rd answer for $\sin(x) + \sqrt{3}\cos(x) = 1$?
I'm getting an extra solution to $sin(x) + \sqrt{3}cos(x)$ = 1 (which is $\frac{7\pi}{6}$) that doesn't show up in the graph or is wrong.  Where am I going wrong with my thinking?  I'm also trying to understand this intuitively.

So I start with $sin(x) + \sqrt{3}cos(x) = 1$.

I know that I can define $\sin(x)$ in terms of $\cos(x)$.  So I get $\sin(x) = 1 - \sqrt{3}\cos(x)$.

I also know that I can get a true value for $\cos(x)$ by using the Pythagorean theorem with all terms defined in some form of $\cos(x)$.  So we have $\cos^2(x)+(1-\sqrt{3}\cos(x))^2=1$

which becomes $4\cos^2(x)-2\sqrt{3}\cos(x) = 0$

Now I factor out $2\cos(x)$ and get $2\cos(x)(2\cos(x)-\sqrt{3}) = 0$

We then have two values for $\cos(x)$ which are $\cos(x) = 0$ and $\cos(x) = \frac{\sqrt{3}}{2}$

We plug these values back into our original equation of $\sin(x) + \sqrt{3}\cos(x)$ and get the following:

$\sin(x) + \sqrt{3}(0)=1$ and $\sin(x) + \sqrt{3}(\frac{\sqrt{3}}{2})=1$

This becomes $\sin(x) = 1$ and $\sin(x) = \frac{-1}{2}$.

When $\sin(x) = 1$, $x = \frac{\pi}{2}$ and when $\sin(x) = \frac{-1}{2}$, $x = \frac{7\pi}{6} + 2\pi k$ (which does not show up on the graph) and $x = \frac{11\pi}{6} + 2\pi k$ which does show up on the graph.  Why am I getting this extra answer?

答:
Hint:

By squaring, you are introducing

$$\sin x=-(1-\sqrt3\cos x)$$ as well

See When do we get extraneous roots?

So, avoid squaring whenever  possible

For this case,

we can use Weierstrass substitution

or Double angle formula, $$\sqrt3\left(\cos^2\dfrac x2-\sin^2\dfrac x2\right)=\left(\cos\dfrac x2-\sin\dfrac x2\right)^2$$

use Solving trigonometric equations of the form $a\sin x + b\cos x = c$


问:
Maclaurin's series and its application conditions
Is Maclaurin's series available when x approaches to 10000?
The value I get when I put $x=10000$ into Maclaurin's series will be similar to the right value approximately? And how should I explain this case since Maclaurin's series is a way to get an approximate value near 0.

答:
For values far away from $0$, you need to use Taylor's series rather than Maclaurin. Of course the approximation would work for 'certain' functions but you'd need a lot of terms convergence

See this blog for more information

ContentLicense: CC BY-SA 4.0


答: This will depend on the function you are approximating, the number of terms you include in the Maclaurin series and what exactly you mean by their values being similar. This is a question of convergence and for such a series one can find what is called the radius of convergence, which will correspond to how far from the origin one can go and the series will still converge to the function, i.e. the value of the series approaches the value of the function as the number of terms approach inifinity. There are also formulas for estimating the error when approximation within the radius of convergence. You might want to look into Taylor's formula with remainder.</p>

Title: Maclaurin's series and its application conditions

Body:
Is Maclaurin's series available when x approaches to 10000?
The value I get when I put $x=10000$ into Maclaurin's series will be similar to the right value approximately? And how should I explain this case since Maclaurin's series is a way to get an approximate value near 0.


问:
Showing $\frac{\pi}{4}-\frac{1-x}{1+x^2}<\arctan (x)<\frac{\pi}{4}-\frac{1-x}{2}$ for $0<x<1$
I was trying to solve the following exercise:

Show that for $0<x<1$ the following inequalities hold: $$\frac{\pi}{4}-\frac{1-x}{1+x^2}<\arctan (x)<\frac{\pi}{4}-\frac{1-x}{2}$$

I think the Mean Value Theorem might be useful, but I don't know how to apply it.

答:
You also can use integral to show the inequality. For $x\in(0,1)$, one has
$$ \frac{\pi}{4}-\arctan x=\int_x^1\frac{1}{1+t^2}dt \le\int_x^1\frac{1}{1+x^2}dt=\frac{1-x}{1+x^2} \tag1$$
and
$$ \frac{\pi}{4}-\arctan x=\int_x^1\frac{1}{1+t^2}dt\ge\int_x^1\frac{1}{2}dt=\frac12(1-x). \tag2$$
Putting (1) and (2) together, one will have the desired inequality.


Title: Why am I getting a 3rd answer for $\sin(x) + \sqrt{3}\cos(x) = 1$?

Body:
I'm getting an extra solution to $sin(x) + \sqrt{3}cos(x)$ = 1 (which is $\frac{7\pi}{6}$) that doesn't show up in the graph or is wrong.  Where am I going wrong with my thinking?  I'm also trying to understand this intuitively.

So I start with $sin(x) + \sqrt{3}cos(x) = 1$.

I know that I can define $\sin(x)$ in terms of $\cos(x)$.  So I get $\sin(x) = 1 - \sqrt{3}\cos(x)$.

I also know that I can get a true value for $\cos(x)$ by using the Pythagorean theorem with all terms defined in some form of $\cos(x)$.  So we have $\cos^2(x)+(1-\sqrt{3}\cos(x))^2=1$

which becomes $4\cos^2(x)-2\sqrt{3}\cos(x) = 0$

Now I factor out $2\cos(x)$ and get $2\cos(x)(2\cos(x)-\sqrt{3}) = 0$

We then have two values for $\cos(x)$ which are $\cos(x) = 0$ and $\cos(x) = \frac{\sqrt{3}}{2}$

We plug these values back into our original equation of $\sin(x) + \sqrt{3}\cos(x)$ and get the following:

$\sin(x) + \sqrt{3}(0)=1$ and $\sin(x) + \sqrt{3}(\frac{\sqrt{3}}{2})=1$

This becomes $\sin(x) = 1$ and $\sin(x) = \frac{-1}{2}$.

When $\sin(x) = 1$, $x = \frac{\pi}{2}$ and when $\sin(x) = \frac{-1}{2}$, $x = \frac{7\pi}{6} + 2\pi k$ (which does not show up on the graph) and $x = \frac{11\pi}{6} + 2\pi k$ which does show up on the graph.  Why am I getting this extra answer?

Body:
You have :
$$\sin x+\sqrt{3}\cos x=1\\\frac{1}{2}\sin x+\frac{\sqrt{3}}{2}\cos x=\frac{1}{2}\\
\sin{\frac{\pi}{6}}\sin x+\cos{\frac{\pi}{6}}\cos x=\frac{1}{2} \\
\cos\left(x-\frac{\pi}{6}\right)=\cos{\frac{\pi}{3}} $$

So you get :
$$x-\frac{\pi}{6}= \frac{\pi}{3},\text{or }x-\frac{\pi}{6}=-\frac{\pi}{3}\\
x=\frac{\pi}{2}+2k\pi \text{ or : }x=\frac{11\pi}{6}+2k\pi$$


问:
Stuck solving this PDE problem
I need to solve $$uu_x+yu_y=x, u(x,1)=2x$$ i tried with characteristics method but got stuck solving the ODEs $$\frac{dx}{dt}=u ~,~\frac{dy}{dt}=y~,~\frac{du}{dt}=x$$ with initial values $x(0)=s,y(0)=1,u(0)=2s$. From the second one i get $y=e^t$, but how to solve the first two ODEs? I tried $$\frac{dx}{du}=\frac{u}{x} \implies x^2-u^2=k_1$$ where $k_1=-3s^2$ which gives $u=\sqrt{x^2+3s^2}$. Similarly $$\frac{dy}{y}=\frac{dx}{\sqrt{x^2+3s^2}} \implies y=k_2(x+\sqrt{x^2+3s^2})$$ And $k_2$ can be found out as $k_2=\frac{1}{3s}$, giving me $y=\frac{x+\sqrt{x^2+3s^2}}{3s}$. I'm not sure how to proceed further and solve for $u$?

答:
I think it is easier if we write the ODEs in the parametrisation invariant form of the Lagrange-Charpit equations

$$\frac{dx}{u} = \frac{dy}{y} = \frac{du}{x}$$

You correctly identified the first characteristic curve

$$\frac{dx}{u} = \frac{du}{x} \implies u^{2} - x^{2} = C_{2}$$

Now, we can use componendo dividendo on the first and third fractions to get

\begin{align}
\frac{dx}{u} = \frac{du}{x} &= \frac{du+dx}{u+x} \\
&= \frac{d(u+x)}{u+x} \\
&= \frac{dy}{y} \\
\end{align}

and so solving the last equality and using the functional relationship $C_{2} = f(C_{1})$ yields

\begin{align}
\ln(u+x) &= \ln y + C_{1} \\
\implies \frac{u+x}{y} &= C_{1} \\
\implies u^{2} - x^{2} &= f(C_{1}) \\
&= f \left(\frac{u+x}{y}\right)
\end{align}

which you can check solves the PDE. Now you can apply the data $u(x,1) = 2x$.

Title: Stuck solving this PDE problem


问:
Bounding $X=0$ with Chebyshev Inequality
I'm looking at a variation of Chebyshev and having a hard time convincing myself why the following is correct:

Given a non-negative, integer valued RV $X$

$$\mathbb{P}(X > 0) \geq 1 - \frac{Var(X)}{\mathbb{E}^2(X)}$$

The proof I'm reading goes:

$$\mathbb{P}(X=0)\overset{1}{\leq} \mathbb{P}(|X-\mathbb{E}[X]|\geq \mathbb{E}[X])\overset{2}{\leq} \frac{Var(X)}{\mathbb{E}^2(X)}$$

Step 2 is simply the application of Chebyshev, but could someone elucidate why step 1 is correct? Seems trivial but can't wrap my head around it at the moment...

答:
Hint

I guess $\mu=\mathbb E[X]$. Since $X\geq 0$ a.s., $$X=0\iff X\leq 0\iff X-\mathbb E[X]\leq -\mathbb E[X]\implies |X-E[X]|\geq \mathbb E[X].$$


问:
If 550 represents 0 and 1280 represents 15, a value between 550 and 1280, what value does it represent according to the above?
I am trying to improve my math skills, and I am trying to solve this problem:

I have values that can be in the range between 550 and 1280.

```<code>550 -> 0  (minimum value represents zero)
1280 -> 15 (maximum value represents 15)

780 -> ??
</code>```

What is the mathematical formula to calculate the corresponding value if, for example, the input value for this formula is 780?

excuse my ignorance

答:
See that you are basically "squeezing" the scale from $550$ to $1280$ to $0$ and $15$.

Now note that wherever you squeeze the scale, you can always get to $0$ and $15$ as desired. What I mean to say is, e.g. You mapped the $550$ to $1280$ to $0$ to $730$ scale, by subtracting $550$ from all values in the range. (we just replaced the scale now, not squeezed!)

Now the minimum values are zero, which is our advantage. Now when we squeeze the scale, the minimum does not change. Remap the $0$ to $730$ scale to $0$ and $15$ by multiplying each value in that range by $\frac{15}{730}$.

Hence, $780$ from original scale is remapped to $\frac{(780 - 550)15}{730}$.


问:
How can I found 3rd and 4th central moments of gumbel distribution with characteristic function?
I tried many ways(using digamma function, partial integration etc.) to find moments using by characteristic function but I couldn't. Is there any trick or suggestion? (I couldn't calculate integral of 2nd, 3nd and 4th derivatives of gamma function.)

Thanks in advance..

答:
The characteristic function for the Gumbel distribution with location parameter $\alpha$ and scale parameter $\beta$ is
$$  \varphi_X(t) = \mathrm{e}^{\mathrm{i} t \alpha} \Gamma(1+\mathrm{i}t \beta)  \text{.}  $$
The $n^\text{th}$ (noncentral) moment can be found from the characteristic function using
$$  E[X^n] = \mathrm{i}^{-n} \left. \frac{\mathrm{d}^n}{\mathrm{d}t^n} \varphi_X(t) \right|_{t = 0}  \text{.}  $$

So, \begin{align*}
E[X^0] &= 1 \cdot \mathrm{e}^0 \Gamma(1) = 1  \\
E[X^1] &= -\mathrm{i} \cdot \left( \mathrm{e}^{\mathrm{i} \cdot 0 \cdot \alpha} \Gamma'(1 + 0)(\mathrm{i}\beta) + \mathrm{i}\alpha \mathrm{e}^{\mathrm{i}\cdot 0 \cdot \alpha} \Gamma(1+0)\right)  \\
    &= - \gamma \beta + \alpha  \\
E[X^2] &= \cdots  \\
    &= \alpha ^2-2 \gamma  \alpha  \beta +\frac{1}{6} \left(6 \gamma ^2+\pi ^2\right) \beta ^2  \\
E[X^3] &= \cdots  \\
    &= \alpha ^3-3 \gamma  \alpha ^2 \beta +\frac{1}{2} \left(6 \gamma ^2+\pi ^2\right) \alpha  \beta ^2-\frac{1}{2} \beta ^3 \left(2 \gamma ^3+\gamma  \pi ^2-2 \psi^{(2)}(1)\right)  \\
E[X^4] &= \cdots  \\
    &= \alpha ^4-4 \gamma  \alpha ^3 \beta +\left(6 \gamma ^2+\pi ^2\right) \alpha ^2 \beta ^2-2 \alpha  \beta ^3 \left(2 \gamma ^3+\gamma  \pi ^2-2 \psi^{(2)}(1)\right)+\frac{1}{20} \beta ^4 \left(20 \gamma ^4+20 \gamma^2 \pi^2 + 3 \pi^4 - 80 \gamma \psi^{(2)}(1)\right)  \text{,}
\end{align*}
where

$\gamma$ is the Euler-Mascheroni constant and

$\psi^{(2)}$ is the polygamma function of order $2$.

Now we compute the central moments from the noncentral moments.  The $n^\text{th}$ central moment, $\mu_n$ is
$$  \mu_n = \begin{cases}
1 ,& n = 0  \\
E[X^1] ,& n = 1  \\
\sum_{j=0}^n \binom{n}{j} (-1)^{n-j} E[X^j] E[X^1]^{n-j}  ,&  n \geq 2
\end{cases}  \text{.}  $$
So,
\begin{align*}
\mu_1 &= E[X^1]  \\
    &= -\gamma \beta + \alpha  \\
\mu_2 &= \alpha ^2-2 \gamma  \alpha  \beta +(i \alpha -i \gamma  \beta )^2+\frac{\pi^2 \beta ^2}{6}+\gamma ^2 \beta ^2  \\
    &= \frac{\pi^2 \beta^2}{6}  \\
\mu_3 &= 3 i \left(\alpha ^2-2 \gamma  \alpha  \beta +\frac{\pi ^2 \beta ^2}{6}+\gamma ^2 \beta ^2\right) (i \alpha -i \gamma  \beta )+i \left(-i \alpha ^3+3 i \gamma  \alpha ^2 \beta +3 i \alpha  \left(-\frac{1}{6} \pi ^2 \beta ^2-\gamma ^2 \beta ^2\right)+\frac{1}{2} i \gamma  \pi ^2 \beta ^3+i \gamma ^3 \beta ^3-i \beta ^3 \psi ^{(2)}(1)\right)+2 i (i \alpha -i \gamma  \beta )^3  \\
    &= \beta ^3 \psi ^{(2)}(1)
\end{align*}
and you should see how to compute $\mu_4$.


问:
Let $f$ be an entire function. Then choose the correct options from below

I know that $f$ is entire. So 4 is correct option. 3 is false option (Liouville theorem) How to give conclusion in 1,2. Please give some hint.

答: Since $f$ is analytic, then it is a $C^\infty$ function if we see it as a function from $\Bbb R^2$ into $\Bbb R^2$. So, its first component (which is $u$) is also a $C^\infty$ function. Therefore, the first option is true and the second one is false.


问:
Let G be a graph in which every vertex has degree 2.
Is G necessarily a cycle?

I suspect not but I'm having hard time showing this.

Also,

Let be a tree. Prove that the average degree of a vertex in T is less than 2.

I know that the sum of degrees of all vertices is $2|E|=2|V|-2$. Thus the graph must be connected, and the average degrees of a vertex is less than 2, so the vertices must be a degree of one. Is this correct?

答:
If $G$ is finite, then it must contain a cycle.  Start at any vertex, and follow the edges.  Eventually you'll run out of new vertices, and have to visit one you've been to before.  But they all have degree 2, so it must be the starting vertex.

For the second question (and normally one asks only one question at a time here), try counting the number of edges in a tree; surprisingly, it depends only on the number of vertices and not on the shape of the tree.

ContentLicense: CC BY-SA 3.0


问:
Solution space of homogeneous linear differential equation of order n is n-dimensional - alternative proof + construction of a basis
Inspired by one of the answers to this post, I constructed my own proof. In addition, I constructed a basis of the solution space. I'd like to know if the following is correct.

Let $(a_0,\ldots,a_n)\in\mathbf{C}^{n+1}$ ($a_n\neq 0$). If $I\subset\mathbf{R}$ is an open interval and $f\colon I\to\mathbf{C}$ has the property $a_0f^{(0)}+...+a_nf^{(n)}=0$, then $f\in C^{\infty}$$.^1$ This means that "solving" the differential equation is equivalent to determining the set
\begin{equation}
X=\left\{f\in C^{\infty}:a_0f^{(0)}+...+a_nD^nf^{(n)}=0\right\}.
\end{equation}
If we introduce
\begin{align}
D^k\colon C^{\infty}&\to C^{\infty}\\
f&\mapsto f^{(k)}
\end{align}
for all $k\in\mathbf{N}_0$ and
\begin{equation}
O:=a_0D^0+...+a_nD^n,
\end{equation}
then
\begin{equation}
X=\ker O.
\end{equation}
Like for all polynomials, there is a $(c_1,\ldots,c_n)\in\mathbf{C}^n$ with
\begin{equation}
O=a_n\prod_{k=1}^nD^1-c_kD^0=a_n\prod_{k=1}^nD-c_kI
\end{equation}
Thus, if we define $D-a:=D-aI$ ($a\in\mathbf{C}$),
\begin{equation}
X=\ker\prod_{k=1}^nD-a_k.
\end{equation}
$D-a$ and $D-b$ commute for all $a,b\in\mathbf{C}$, thus we can reorder the product however we want. Therefore we can concentrate on finding the kernel of an operator that has the form
\begin{equation}\tag{1}
(D-a_1)^{k_1}\cdots(D-a_m)^{k_m}.
\end{equation}
(This will allow us to construct a basis later on.)

$D-a$ has a $1$-dimensional kernel and is surjective (here is the proof), meaning that $\dim\ker O=n$ according to this post.

We can even construct a basis:
\begin{align}
e_n(a)\colon I&\to\mathbf{C}\\
x&\mapsto\frac{x^n}{n!}e^{ax}
\end{align}
Thanks to the factorial, we have $De_n(a)=e_{n-1}(a)+ae_n(a)$ for $n\in\mathbf{N}$ and $De_0(a)=ae_0(a)$. This means $(D-c)e_n(a)=e_{n-1}(a)+(a-c)e_n(a)$ for $n\in\mathbf{N}$ and $(D-c)e_0(a)=(a-c)e_0(a)$.

Thus,
\begin{equation}
\{e_0(a_1),\ldots,e_{k_1-1}(a_1),\ldots,e_0(a_m),\ldots,e_{k_m-1}(a_m)\}
\end{equation}
is a basis of the operator in equation $(1)$.

$^1$ $a_0f^{(0)}+...+a_nf^{(n)}=0$ is equivalent to
\begin{equation}
f^{(n)}=\frac{-a_0f^{(0)}\ldots-a_{n-1}f^{(n-1)}}{a_n}
\end{equation}
and that is equivalent to
\begin{equation}
f^{(m)}=\frac{-a_0f^{(m-n)}\ldots-a_{n-1}f^{(m-1)}}{a_n}
\end{equation}
for all $n\leq m\in\mathbf{N}$ (you can prove this using induction).

答:
In order to get (2), you need your caracteristic polynom : $\chi(X)=\sum_{i=0}^na_iX^i $ to have simple roots

If you work in $\mathbb{C}$, you have the following result :

$$\ker\left({O=a_n\prod_{i=1}^{k}(D-c_i1)^{m_i}} \right)=\bigoplus_{i=1}^k\ker\left((D-c_i1)^{m_i}\right)$$


问:
existence continuous function $f:X\to [0,1]$ such that $f(x_1)=0 , f(x_2)=\frac{1}{2}, f(x_3)=1$

Let $X$ be a Hausdorff normal topological space and $x_1, x_2, x_3$
  are three distinct points.prove that there exist continuous function
  $f:X\to [0,1]$ such that $f(x_1)=0 , f(x_2)=\frac{1}{2}, f(x_3)=1$

I think Urysohn's Lemma will be helpful here.

By Urysohn's Lemma there exists a continuous function $f:X\to [0,1]$ such that $f(x_1)=0 , f(x_3)=1$ and moreover there exists a continuous function $g:X\to [0,1/2]$ such that $g(x_1)=0 , g(x_2)=1/2$. But how can I add them to get a single function?

答: By Urysonh's lemma and since $X$ is $T_1$ you  can get a continuous $f:X\rightarrow [0,1/2]$ such that $f(x_1)=0,f(x_2)=1/2$ and $f(x_3)=0$; $\{x_1,x_3\}$ is closed, and then $g:X\rightarrow [0,1]$ with $f(x_1)=0,f(x_2)=0$, and $f(x_3)=1$, now you can add these functions.</p>


问:
If $ f $ and $ g $ are similar endomorphism iff $ f $ and $ g $ are represented by the same matrix.
If E is a $ \mathbb {C} $-vector space, we denote by $ \mathcal {L} (E) $ the $ \mathbb {C} $-algebra of endomorphisms of $ E $.
Let $ E $ and $ F $ be two $ \mathbb {C} $-vector spaces of the same finite dimension $ n \geq 1 $ and $ f \in \mathcal {L} (E) $ and $ g \in \mathcal {L} (F) $

Definition: we say that f and g are similar if there exists an isomorphism $ u $ from $ E $ in $ F $ satisfying: $ g = u \circ f \circ u^ {- 1} $. We denote by $ f \mathcal {R} g $.

Thus $ \mathcal {R} $ is an equivalence relation over the set of all endomorphisms of vector spaces of dimension $ n $ over $ \mathbb {C} $.

Problem:

Show that  $ f \mathcal {R} g $ if and only if : there exists  a base $ \mathcal {B} $ of $ E $ and a base $ \mathcal {C} $ of $ F $ such that:
$$
mat_ {\mathcal {B}} (f) = mat_ {\mathcal {C}} (g) \qquad (mat_ {\mathcal {B}} (f) \text { denotes the matrix of  } f \text {  relatively at the base } \mathcal {B})
$$
in other words, $ f $ and $ g $ are represented by the same matrix.

An idea please.

答:
Sketch of Proof: To begin, prove that if $f,g$ are represented by the same matrix, then $f$ and $g$ are similar. To me, this is the "easier" direction.

Let $M$ denote this common matrix, which is the matrix of $f$ relative to $\mathcal B$ and the matrix of $g$ relative to $\mathcal C$. Note that $M$ can be thought of as a linear map $M:\Bbb C^n \to \Bbb C^n$. Corresponding to our choice of basis $\mathcal B$, I claim that there exists an invertible linear map $\beta:\Bbb C^n \to E$ for which
$$
M = \beta^{-1} \circ f \circ \beta.
$$
What exactly is this map? That is, how should this map be defined in terms of the elements of $\mathcal B$? For the same reason, we can write $M = \gamma^{-1} \circ g \circ \gamma$ for an invertible $\gamma:\Bbb C^n \to F$. With that, we find
$$
\beta^{-1} \circ f \circ \beta = \gamma^{-1} \circ g \circ \gamma \implies\\
\gamma \circ \beta^{-1} \circ f \circ \beta \circ \gamma^{-1} = g \implies\\
u \circ f \circ u^{-1} = g,
$$
where $u = \gamma \circ \beta^{-1}$.

For the converse implication, we are given that $g = u \circ f \circ u^{-1}$. I claim that there exist invertible maps $\beta : \Bbb C^n \to E$ and $\gamma : \Bbb C^n \to F$ such that $u = \gamma \circ \beta^{-1}$. With the first half of the proof in mind, use this to conclude that $f$ and $g$ are represented by the same matrix $M$ relative to some choice of basis $\mathcal B$ of $E$ and $\mathcal C$ of $F$.


答:
Since the r.v. is integer valued and non-negative, the event $\{X=0\}$ is equal to the event $\{X\leq 0\}$, which in turn is equivalent to $\{X-E(X)\leq -E(X)\}$.

Notice that $\{|X-E(X)|\geq E(X)\}=\{X-E(X)\geq E(X)\}\cup\{-(X-E(X))\geq E(X)\}$, which in turn equals $\{X-E(X)\geq E(X)\}\cup\underbrace{\{(X-E(X))\leq -E(X)\}}_{\{X=0\}}$.

Notice that if event  $\{X=0\}$ is verified then  $\{|X-E(X)|\geq E(X)\}$ is verified, in terms of set inclusions this means that $\{X=0\}\subset \{|X-E(X)|\geq E(X)\}$. Translated to probabilities this is equivalent to the desired result.

Title: Bounding $X=0$ with Chebyshev Inequality

Body:
I'm looking at a variation of Chebyshev and having a hard time convincing myself why the following is correct:

Given a non-negative, integer valued RV $X$

$$\mathbb{P}(X > 0) \geq 1 - \frac{Var(X)}{\mathbb{E}^2(X)}$$

The proof I'm reading goes:

$$\mathbb{P}(X=0)\overset{1}{\leq} \mathbb{P}(|X-\mathbb{E}[X]|\geq \mathbb{E}[X])\overset{2}{\leq} \frac{Var(X)}{\mathbb{E}^2(X)}$$

Step 2 is simply the application of Chebyshev, but could someone elucidate why step 1 is correct? Seems trivial but can't wrap my head around it at the moment...


答:
You found the solutions

$$\cos x=0,\cos x=\frac{\sqrt 3}2$$ and $$\sin x=1,\sin x=-\frac12,$$ which might make you think that there are in fact five of them ($\frac\pi2,\frac{3\pi}2,\frac\pi6,\frac{7\pi}6,\frac{11\pi}6$). In other cases, you would even find six solutions this way !

But you forget that these hold in pairs, giving only two possible angles.


问:
Automorphisms of the half-plane
I have trouble with proof of:
$\DeclareMathOperator{\Aut}{Aut}$
$$\Aut(H)=T^{-1} \Aut(D) T $$
via Cayley transformations.

I know that I have to show that:
$$\Phi: \Aut(H)\to \Aut(D) $$
$$f \mapsto T^{-1}\circ f\circ T$$
is a well-defined group homomorphism. Further I have to show that:
$$\Psi:\Aut(D) \to \Aut(H)$$
$$f \to ??$$
is the inverse function of $\Phi$.

$\Phi$ is a group isomorphism and $\Aut(H)=T^{-1}\Aut(D)T$ follows.

答:
I understood how to answer this question, we can solve the exercise with the inclusion theorem $$M=N:M⊆NandN⊆M$$
so $$Aut(H)⊆T^{-1}Aut(D)T$$ and the other case.

Title: Automorphisms of the half-plane


答:
1) No. Just take two triangles.

If $G$ is connected and every vertex has degree $2$ then $G$ is a cycle.

2) Combine sum of degrees formula with tree formula...

Title: Let G be a graph in which every vertex has degree 2.

Body:
Is G necessarily a cycle?

I suspect not but I'm having hard time showing this.

Also,

Let be a tree. Prove that the average degree of a vertex in T is less than 2.

I know that the sum of degrees of all vertices is $2|E|=2|V|-2$. Thus the graph must be connected, and the average degrees of a vertex is less than 2, so the vertices must be a degree of one. Is this correct?


问:
GAP WreathProduct with fixed points
Gap always takes the domain of a permutation group to be the set of points moved by its elements. The documentation of WreathProduct thus includes this comment explaining how form the wreath product between permutation groups whose domains include fixed points:

"If fixed points are desired the wreath product $G \wr T$ has to be formed with a transitive overgroup $T$ of $P$ and then the pre-image of $P$ under the projection $G \wr T \rightarrow T$ has to be taken."

Can someone more well versed in GAP than me demonstrate how to do this in practice? Say e.g.
I want to compute WreathProduct(Group([(1,2)(3)]), Group([(1,2)])), i.e. I want to compute the wreath product as if the first group had domain $\{1,2,3\}$ instead $\{1,2\}$. How do I do that?

答:
You could take the wreath product of a trasitive overgroup (in your example $S_3$) by your second factor, and then take the group generated by the image of your embedded group $G$, together with (the image of) $T$:

```<code>gap> G:=Group((1,2));;
gap> S:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> T:=Group((1,2));;
gap> WS:=WreathProduct(S,T);
Group([ (1,2,3), (1,2), (4,5,6), (4,5), (1,4)(2,5)(3,6) ])
gap> Gemb:=Image(Embedding(WS,1),G);
Group([ (1,2) ])
gap> Temb:=Image(Embedding(WS,3),T);  # 3=1+LargestMovedPoint(T);
Group([ (1,4)(2,5)(3,6) ])
gap> W:=ClosureGroup(Gemb,Temb);
Group([ (1,2), (1,4)(2,5)(3,6) ])
gap> Size(W);
8
</code>```

You could do analogously if $T$ is not transitive (though then you would take embeddings of $G$ for every orbit of $T$.

Title: GAP WreathProduct with fixed points

Body:
You could take the wreath product of a trasitive overgroup (in your example $S_3$) by your second factor, and then take the group generated by the image of your embedded group $G$, together with (the image of) $T$:

gap> G:=Group((1,2));;
gap> S:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> T:=Group((1,2));;
gap> WS:=WreathProduct(S,T);
Group([ (1,2,3), (1,2), (4,5,6), (4,5), (1,4)(2,5)(3,6) ])
gap> Gemb:=Image(Embedding(WS,1),G);
Group([ (1,2) ])
gap> Temb:=Image(Embedding(WS,3),T);  # 3=1+LargestMovedPoint(T);
Group([ (1,4)(2,5)(3,6) ])
gap> W:=ClosureGroup(Gemb,Temb);
Group([ (1,2), (1,4)(2,5)(3,6) ])
gap> Size(W);
8

You could do analogously if $T$ is not transitive (though then you would take embeddings of $G$ for every orbit of $T$.


问:
About the additional condition needed to prove the Convergence of Random Variables
We have random variables $X_n\rightarrow X$ almost surely. Now fix a positive real number $M$, define $\bar{Y}=Y \mathbb{I}_{\{Y\leq M\}}$. Then if $P(X=M)=0$, we have $\bar{X_n}\rightarrow \bar{X}$ almost surely.

My question is why we need $P(X=M)=0$ this condition? And would someone please give me a counterexample that this convergence fails without this condition?

Thanks

答:
Let $X_n=M+1/n$ and $X=M$; then $\overline{X_n}=0$ and $\overline{X}=M$ while $X_n\to X$ almost surely.

The reason is that if $P(X=M)=0$, then for almost every $\omega$, we either have $X(\omega)<M$ or $X(\omega)>M$ hence for $n$ large enough, we are sure that $X_n(\omega)<M$ or $X_n(\omega)>M$ and the value of the indicator will not change.


答:
According to your results we have

$$
\cases{
u^2-x^2-3s^2=0\\
y-\frac{x+\sqrt{x^2+3s^2}}{3s}=0
}
$$

or

$$
\cases{
u^2-x^2-3s^2=0\\
(3sy-x)^2-x^2-3s^2=0
}
$$

So solving the first for $s$ and substituting after choosing the feasible one into the second, we have

$$
u = x\frac{3y^2+1}{3y^2-1}
$$

Title: Stuck solving this PDE problem

Body: I need to solve $$uu_x+yu_y=x, u(x,1)=2x$$ i tried with characteristics method but got stuck solving the ODEs $$\frac{dx}{dt}=u ~,~\frac{dy}{dt}=y~,~\frac{du}{dt}=x$$ with initial values $x(0)=s,y(0)=1,u(0)=2s$. From the second one i get $y=e^t$, but how to solve the first two ODEs? I tried $$\frac{dx}{du}=\frac{u}{x} \implies x^2-u^2=k_1$$ where $k_1=-3s^2$ which gives $u=\sqrt{x^2+3s^2}$. Similarly $$\frac{dy}{y}=\frac{dx}{\sqrt{x^2+3s^2}} \implies y=k_2(x+\sqrt{x^2+3s^2})$$ And $k_2$ can be found out as $k_2=\frac{1}{3s}$, giving me $y=\frac{x+\sqrt{x^2+3s^2}}{3s}$. I'm not sure how to proceed further and solve for $u$?


答:
$780\rightarrow4.726$.

Indeed the unique way to solve this problem is to assume that the function is linear, similar to the Fahrenheit $ \leftrightarrow $ Celsius conversion. Otherwise there are infinite possible answers and the problem makes no sense.

Setting $y = mx +n$ we see that, if $550\to 0$ then $0=550m+n$ which means $n=-550m$

if $1280\to 15$ then $15=1280m+n$

Plug the $n$-value and get $15=1280m-550m\to m=\frac{3}{146}$

and finally $n = -\frac{825}{73}$

So we get
$$y = \frac{3}{146}\,x -\frac{825}{73}$$

For $x=780$ we have $y=\frac{345}{73}\approx 4.726$

Hope this helps

Title: If 550 represents 0 and 1280 represents 15, a value between 550 and 1280, what value does it represent according to the above?

Body:
I am trying to improve my math skills, and I am trying to solve this problem:

I have values that can be in the range between 550 and 1280.

```<code>550 -> 0  (minimum value represents zero)
1280 -> 15 (maximum value represents 15)

780 -> ??
</code>```

What is the mathematical formula to calculate the corresponding value if, for example, the input value for this formula is 780?

excuse my ignorance


问:
Affine Plane of Order $5$ Picture?
I am unable to construct an affine plane of order $5$. I currently am able to construct an affine plane for orders $3$ and $4$ but I am not able to figure out the construction of an affine plane of order $5$ using a $5\times 5$ array of dots. Could someone show an example picture of one and how you were able to come to construct the affine plane of order $5$?

答:
There is a field of order $5$, namely $\mathbb{F}_5 = \mathbb{Z}/(5)$, so you can just take the affine plane over $\mathbb{F}_5$.

The points are the elements of $\mathbb{F}_5\times \mathbb{F}_5$, and the lines are the sets of points of the form $\{(x,y)\mid y = ax + b\}$ and $\{(x,y)\mid x = c\}$ for $a,b,c\in \mathbb{F}_5$ (this is just the description of the affine plane over any field). There are $30$ lines, so a picture will inevitably get a bit muddled!

The point is that it's extremely easy to construct an affine plane of prime order $p$ in this way. Constructing an affine plane of prime power order $p^n$ is also straightforward - but a little more complicated to understand explicitly, because you first have to construct a field of order $p^n$ and understand its addition and multiplication tables: see here for example. On the other hand, the existence of affine planes of non-prime-power order is an open problem.

Title: Affine Plane of Order $5$ Picture?


问:
If $\alpha$ is a k-cycle with k odd then there exists a cycle $\beta$ such that $\beta^2$=$\alpha$
If $\alpha$ is a k-cycle with k odd then there exists a cycle $\beta$ such that $\beta^2$=$\alpha$.

I know that $\alpha$ is even since it has odd length but I don´t know how to continue.

答:
By hypothesis, you have $\alpha^k = e$ where $e$ is the identity element of the symmetric group $\mathfrak S_n$.

As $k$ is odd, $\frac{1-k}{2}$ is an integer. Denote $\beta = \alpha^{\frac{1-k}{2}}$. We have

$$\beta^2= \left(\alpha^{\frac{1-k}{2}}\right)^2 = \alpha^{1-k} = \alpha.$$

Because $k + 2 \frac{1-k}{2} = 2$ and $k$ is odd, $k$ and $\frac{1-k}{2}$ are coprimes. It is known that for a cycle of length $l$, $\sigma^r$ is also a cycle of length $l$ when $l,r$ are corpimes.

This conclude our proof: $\beta = \alpha^{\frac{1-k}{2}}$ is a $k$-cycle satisfying $\beta^2=\alpha$.


问:
Geometric solution to classic committee problem
Most people know the classic committe style problems.

I read this solution to one of the basic version of the committe problem and was impressed, but not sure why it works.

I was hoping someone could explain why does it work.

答:
"A person is on exactly two committees" = "An intersection point is in exactly two lines"

"A committee contains exactly three people" = "A line contains exactly three intersection points"

"No two committees have more than one person in common" = "No two lines cross in more than one place"

This sort of solution wouldn't work in the same way if you changed the first or last restriction.


问:
Doubt curious when trying to prove this identity
My friend, Mr. Barreto, did post a problem on Art of Problem Solving (AOPS) about infinite sum and asked me to post the question here in order to have various approaches and answers. I am also curious about this problem as well. Here is his post:

"When trying to prove the following Ramanujan identity:
$$\alpha\sum_{k=1}^\infty\frac{k}{e^{2\alpha k}-1}+\beta\sum_{k=1}^\infty\frac{k}{e^{2\beta k}-1}=\frac{\alpha+\beta}{24}-\frac{1}{4}\quad.............(1)$$
initially the method consists of using $\frac{1}{e^{x}-1}=\frac12\left(\coth\left(\frac x2\right)-1\right)$ and then (1) is :
$$\frac12\sum_{k=1}^\infty k\left\{\alpha \coth(\alpha k)+\beta\coth(\beta k)\right\}-\frac{\alpha+\beta}{2}\sum_{k=1}^\infty k\quad ............(2)$$
We know that these sums are diverging, but one way to escape the obvious in this way is to use a little of the Theory of Divergent Series by the author of the identity (Ramanujan). So, for divergent series, we have:
$$\sum_{n=1}^\infty f(n)=-\frac{f(0)}{2}+i\int_0^\infty\frac{f(it)-f(-it)}{e^{2\pi t}-1}\mathrm dt$$
Here is the point of doubt, I am concluding through the formula above, that (2) is:
$$(\ast)\ \sum_{k=1}^\infty k=-\frac{1}{12},\qquad (\ast\ast)\ \sum_{k=1}^\infty k\left\{\alpha \coth(\alpha k)+\beta\coth(\beta k)\right\}=-1,$$
that way we get: $\frac{\alpha+\beta}{24}-\frac12$ and not $\frac{\alpha+\beta}{24}-\frac14$. I don't know if the theory used is really applicable, I just found it convincing to use the Ramanujan Summation  to prove Ramanujan's Identity (1). I hope that only the algebraic part is wrong, because I found the path simple and elegant."

答:
Let us define the Dedekind Eta function as $$\eta(q) =q^{1/12}\prod_{n\geq 1}(1-q^{2n})\tag{1}$$ It is well known that it satisfies the transformation formula $$\alpha^{1/4}\eta(e^{-\alpha}) =\beta^{1/4} \eta(e^{-\beta})\tag{2}$$ where $\alpha, \beta$ are positive with $\alpha\beta=\pi^2 $.

We can observe that $$\frac{d\beta} {d\alpha} =-\frac{\beta} {\alpha} $$ and logarithmic differentiation of equation $(2)$ gives us $$\alpha\sum_{n\geq 1}\frac{n}{e^{2n\alpha}-1}+\beta\sum_{n\geq 1}\frac {n} {e^{2n\beta}-1}=\frac{\alpha +\beta}{24}-\frac{1}{4}$$ with some amount of algebra.

The transformation formula $(2)$ is almost obvious if one writes the expression of eta function in terms of corresponding elliptic modulus and integrals. But including such details might not be possible here. There are approaches based on complex analysis which I find more complicated.


问:
Find the gradient vector of $f(x,y) = (4+x^2+y^2)^{1/2}$ at the point $(2, 1)$.
In this question there is no mention of a direction to use, how would I go about answering the question regardless?</p>

答:
So the gradient is defined as

$$\nabla f(x,y) = \begin{pmatrix}\frac{df}{dx} \\ \frac{df}{dy}\end{pmatrix}$$

Therefore, after calculations

$$\nabla f(x,y) = \begin{pmatrix}\frac{x}{\sqrt{4+x^2+y^2}} \\ \frac{y}{\sqrt{4+x^2+y^2}}\end{pmatrix}$$

And after specializing the variables

$$\nabla f(2,1) = \begin{pmatrix}\frac{2}{3} \\ \frac{1}{3}\end{pmatrix}$$


问:
Request for Advice on Study Material
I want to learn number theory from the basics, but being in the tenth grade, I am not sure if I would understand everything. Therefore, I need some help regarding what is it that I must read through to get a nice understanding of number theory. A bit of set theory as a topic to learn in the study material alongside the number theory part will also be great (since I am neither a good beginner nor an expert at set theory ).

Currently, I have the lecture notes and exercise questions from Professor Abhinav Kumar's MIT spring lecture series (I got it from OCW), but they are all notes, so I may not be able to grasp the whole picture. It would be great if you suggest me the best book that I can learn from.

答: Thomas Cochy "The elementary introduction to number theory". The best book I have ever seen :D</p>

Title: Request for Advice on Study Material


问:
Finite series manipulation?
Most of the questions I've seen on here about resources ask about good resources for understanding infinite series, but I was wondering if anyone could recommend a good source for manipulating the indices of finite series, such as how to handle double sums, and how to handle derivatives and integrals of finite series. I'm currently studying maximum likelihood estimation and expected value calculations, and the proofs therein perform odd manipulations with series that baffle me.

An example is the following, where the decomposition of the squared term in the first line into a double sum sort of makes sense to me in hindsight, but isn't something I would have come up with on my own. Other examples are converting series to matrix form, which I never quite understand. Can anyone recommend any comprehensive resources about these topics? Thanks in advance!

答:
We do have tricks in manipulating finite series, but those kinds of manipulation are occasional and casewise.

Regarding your reference, "double sums" or anything is not the trick here. It is just the author was so lazy( or with other specific intention) to tell you that what he was doing is the following formula: $$Var(X+Y)=Var(X)+Var(Y)$$ for $X, Y$ independent.

Title: Finite series manipulation?


答:
There are lots of ways of doing this. Given $x_1,x_2, x_3$, there exist functions $f_1,f_2:X \to [0,1]$ such that $f_1(x_1) = 0, f_1(x_2) = 1$, and $f_2(x_3) = 0, f_2(x_2) = 1$. Then $f:X \to [0,1]$ defined by $f(x) = f_1(x)f_2(x)$ satisfies $f(x_1)= f(x_3) = 0$ and $f(x_2) = 1$.

By a similar procedure, we can find a $g:X\to[0,1]$ such that $g(x_1)= g(x_2) = 0$ and $g(x_3) = 1$.

The function $\phi(x) = \frac{1}{2} f(x) + g(x)$ satisfies the requirements.

Title: existence continuous function $f:X\to [0,1]$ such that $f(x_1)=0 , f(x_2)=\frac{1}{2}, f(x_3)=1$

Body:
Let $X$ be a Hausdorff normal topological space and $x_1, x_2, x_3$
  are three distinct points.prove that there exist continuous function
  $f:X\to [0,1]$ such that $f(x_1)=0 , f(x_2)=\frac{1}{2}, f(x_3)=1$

I think Urysohn's Lemma will be helpful here.

By Urysohn's Lemma there exists a continuous function $f:X\to [0,1]$ such that $f(x_1)=0 , f(x_3)=1$ and moreover there exists a continuous function $g:X\to [0,1/2]$ such that $g(x_1)=0 , g(x_2)=1/2$. But how can I add them to get a single function?


问:
Convergence in measurs of any measurable function.
Can i say that any measurable function $f:\Bbb R^n\to \Bbb R$ there exist a sequence of simple measurable functions  $\phi_n, \phi_n:\Bbb R^n\to\Bbb R$ converges to $f$ in measure? This is true in pointwise convergence as well known result. But i don't know about convergence in measurs. There is Lebsuge measure on $\Bbb R^n$.Thanks.

答:
What do you mean by convergence in measure?   So there is already a measure $\mu$ on the space $\mathbb{R}^n$, right?

So if $|\mu|< \infty$, the almost sure convergence clearly gives the convergence in law.

If $|\mu|=\infty$, well, you have to differentiate carefully between different notion of "convergence in measures" ( vague convergence, weak convergence, etc).

Also, you have to be careful if $\mu$ is $\sigma$ finite or not.


问:
Why is there a unique solution to the frog puzzle?
I'm pretty sure this is a trivial question but eh...

The Frog Puzzle is a famous 8th-grade problem (playable here):

$3$ red frogs and $3$ blue frogs are sitting on lily pads, with a spare lily pad in between them.
Frogs can slide onto adjacent lily pads or  jump over a frog; frogs can't jump over more than one frog. Frogs can't move backwards.
Can we swap the red frogs with the blue frogs?

It's fairly easy to solve, even for $n$ red frogs and $m$ blue frogs. But I find it very hard to "mathematize" it : should we see the "pond" as an element of $(\mathbb{Z}_3)^7$ ? Then how can we describe the possible moves ?

Unable to translate this into familiar mathematical terms, I'm thereby very puzzled by this... puzzle. In particular, I can't seem to find why is there always a solution, and only one (up to symetry of course), for any number of frogs. I've tried to make it work in Scylab but I'm very rusty in programmation...

All I've managed to prove is that a frog can't jump over a frog of the same color but I'm not sure this will lead somewhere.

Bonus question : is the number of solution equal to the number of empty lily pads?

答: I have only worked with the 3x3 puzzle.  One interesting thing that I noticed is that the last position is the mirror image of the last (obviously), and the second position is the mirror image of the second to last, and so on.  In the middle, there is a transition from a position to its mirror image.  If you have been keeping track of your moves, once you reach this middle position, you can now solve the rest of the problem</p>


问:
Constructing real numbers and why every real is not computable
Constructive vs computable real numbers asked two questions :

Why isn't every real number computable?

How is it possible to construct an uncountable set?

What is wrong with following answers?

1.Because there is at least one real number that is not computable.

2.
Step 1 : 0.0 , 0.1

Step 2 : 0.00 , 0.01 , 0.10 , 0.11

Step 3 : 0.000 , 0.001 , 0.010 , 0.100 , 0.011 , 0.101 , 0.110  , 0.111

step n : 0.(all combinations 1,0 of length n)

continue above indefinitely in binary to get all values in the interval 0,1.

答: The first does not explain why there are unconstructable numbers.  The second constructs all the terminating binary numbers, so you get all fractions of the form $\frac k{2^m}$ but does not construct any nonterminating number like $\frac 13$.  The set only has countably many members.


问:
Find the basis.
Given,$W=\{(u,v,w,x): u+w+x=0,u+w-2x=0,v=x\}$ subspace of $\mathbb{R}^4$

The problem is this,  $u+w+x=0,u+w-2x=0$

I can get only one member $(-1,0,1,0)$ of basis elements.

I don't understand is there more members or not?

If not then why?

How could one deal with these types equations?

答:
You have $v=x$, $u+w+x=0$ and $u+w-2x=0$. That is $u+w=-x$ and $u+w=2x$, i.e., $-x=2x$ and so $x=0$.

Then $v=0$ and $u+w=0$, i.e., $u=-w$.

Indeed, the basis consists of the vector $(-1, 0, 1, 0)$. All elements of the subspace are scalar multiple of this vector.

Title: Find the basis.


问:
Is $F$ over $\mathbb{F}_2(x)$ separable?
I want to determine whether the extension $F$ over $\mathbb{F}_2(x)$ is separable, where:
$$F=\mathbb{F}_2(x)[t]/ \langle t^2+t+1 \rangle \quad \mbox{and} \quad \mathbb{F}_2 \mbox{ is the finite group with } 2 \mbox{ elements }  \cong \mathbb{Z}_2$$

So far, I've worked out that $E=\mathbb{F}_2[x]/ \langle x^2+x+1 \rangle$ is separable over $\mathbb{F}_2$ by checking that for every $\alpha \in E$, the minimal polynomial of $\alpha$ in $\mathbb{F}_2$ is separable. I was able to do this because $|E| = 2^2=4$, but $|F| = \infty$ and therefore I can't use this method anymore. Can someone help me?

答:
This is not how I would do it, but it seems to be the sort of argument you are asking for.

A general element $\alpha$ of your field $F$ is $f(x)\bar{t}+g(x)$. If $f=0$ this element lies in $\mathbb{F}_2(x)$ and so is separable. If $f\not=0$ then the minimal polynomial $m(Y)$ of $\alpha$ is
$$
Y^2+f(x)Y+f(x)^2+f(x)g(x)+g(x)^2
$$
whose derivative wrt $Y$ is (the invertible) $f(x)$, so that the highest common factor of $m$ and $m'$ is $1$. Hence $m$ does not have repeated roots and so $\alpha$ is separable.


问:
Every finite ring $R$ has a nilpotent ideal $I$ such that the only nilpotent of $R/I$ is the zero ideal
Just like the title.

How to show that every finite ring $R$ has a nilpotent ideal $I$ such that the only nilpotent ideal of $R/I$ is the zero ideal?

I just know that every finite ring has a nilpotent ideal, but how to construct a ideal $I$ satisfiying the additional condition?

I guess that the $I$ need to be large enough, but what's more?

答:
I just know that every finite ring has a nilpotent ideal,

Well... every ring has the trivial ideal as a nilpotent ideal. You could not possibly have meant "nonzero nilpotent ideal" because obviously the finite fields don't have such an ideal, and are quite finite.

but how to construct a ideal  satisfiying the additional condition?

Finiteness plays a very ham-handed role, one which could easily be replaced by a weaker condition.

Consider for a moment any two ideals $I\subseteq J$ of a ring $R$. If the ideal $J/I$ is nilpotent in $R/I$, it means $J^k\subseteq I$ for some $k$.  If $I$ is also a nilpotent ideal of $R$, then so is $J^k$ and also $J$.

What this says is that in order for $R/I$ to lack nonzero nilpotent ideals, you want to find an $I$ that is maximal among nilpotent ideals of $R$.. That is how you will construct/find your answer.

Now... how you get that maximal nilpotent ideal is easily accomplished for a finite ring: there are only finitely many ideals so you just write them all down and pick a maximal nilpotent one.

But really all you needed is the existence of a maximal member of the poset of nilpotent ideals, and that would be given to you merely by the ring being right or left Noetherian.

A final fact worth mentioning is that for a right or left Artinian ring, there is a unique maximal nilpotent ideal: it is the Jacobson radical. The Jacobson radical always contains nilpotent ideals, but for Artinian rings in particular you know that the radical itself is nilpotent, and that makes it the biggest.

All of that last paragraph holds in particular for finite rings, so now you know exactly what ideal to look for.


问:
Probability that all problems are solved
The problem is

A solves a problem with probability 0.6. B solves a problem with
probability 0.5. They are given 7 problems and each chooses 5 out of
the 7 problems randomly and solves them independently. What is the
probability that all the 7 problems are solved by at least one of
them?

It seems like a binomial distribution problem but I am not sure how to do.

I am thinking that probability that a problem is solved

```<code>P(solved)=P(A solved)+P(B solved)-P(A and B both solved)
         =(5/7)(0.6)+(5/7)(0.5)-(5/7)(5/7)(0.6)(0.5)
         =31/49
</code>```

then all problems are solved is

```<code>P(all solved)=(31/49)^7
</code>```

I don't think I am doing right but am not sure where. Can anyone give a thought?

答:
The way I interpret this, if $A$ and $B$ both decided to work on the first five problems... then regardless of their success at solving those first five problems correctly neither of them attempted problems $6$ or $7$ and so neither of those problems are able to be solved.  Taking it a step further, we recognize that for all seven problems to have been solved, we require as a first step that $A$ and $B$ collectively  attempt all seven of the problems... that is, there are $2$ problems attempted only by $A$, $2$ problems attempted only by $B$, and $3$ problems attempted by both.

Your attempted answer incorrectly used this "each chooses 5 problems to work on" aspect of the problem.  Whether or not one question is selected is very much dependent on whether another is selected.  Of those who were selected, the problem being successfully completed will be independent however.

Next, I interpret this as a "problem is solved" iff at least one of the students correctly solved it.

Step 1:  Recognize it is possible to have collectively solved all seven problems only if all seven were attempted.  Find the probability that the problems attempted collectively cover all seven available problems.

 Without loss of generality, suppose $A$ picked what problems to work on first and they happened to be the first five problems.  $B$ now picks the problems they work on and we need two of those problems to have been the last two problems.  There are $\binom{7}{5}$ ways that $B$ could have picked their problems, only $\binom{5}{3}$ of which result in the last two being picked.

Step 2: For each problem, find the probability it was successfully completed by at least one of the students.  Recognize the difference between the questions attempted only by $A$, the questions attempted only by $B$, and the questions attempted by both.

 If a question was attempted only by $A$ there is a $0.6$ chance it was completed correctly.  If a question was attempted only by $B$ there is a $0.5$ chance it was completed correctly.  If a question was attempted by both there is an $0.5 + 0.6 - 0.5\cdot 0.6 = 1.1-0.3=0.8$ chance it was completed correctly by at least one of them.

We get as a final answer then:

 $$\dfrac{\binom{5}{3}}{\binom{7}{5}}(0.6)^2(0.5)^2(0.8)^3$$


问:
permutation of sets
I have a question regarding the permutation of sets and it is:

Problem: let the sample space $X$ be the set of permutations of $\{1,2,3,4,5\}$, the permutation $\{n_1,n_2,n_3,n_4,n_5\}$ represents the object allocation where for $i,j\in \{1,2,3,4,5\}$ we have $n_i=j$ if person $i$ receives the object by person $j$. Furthermore $i\in \{1,2,3,4,5\}$. If we define the events:

$$A_i=\{(n_1,n_2,n_3,n_4,n_5)\in X\space |\space n_i=i\}$$

My confusions: I do not understand how to list these elements under the defined set of element characteristics this set has for instance, in the sample space $X$, can $n_1=1, n_2=2,n_3=3,n_4=4, n_5=5?$

If not then the values $n_1$, $n_2$,... can take are $n_1=2,3,4,5; n_2=1,3,4,5; ...$ etc. So one possible element of the sample space is $(2,3,4,5,1)\in X?$.

But in the set $A_i,$ now there is a new condition which is $n_i=i$, that means the set $A_1=\{(1,1,1,1,1)\}?$. I am alittle confused on the definition of $n_i=i$ in the set $A_i,$ and how many elements  $A_1, A_2,...,A_5$ contains. Can anyone help me explain or find the elements of the set $A_i$, or just an example for$ A_1$ and $A_2?$ I would appreciate it.

答:
No, notice that $i$ is defined outside the characterization of the set. Meaning that $i$ is fixed for each set. So $$A_1=\{\color{red}{1},2,3,4,5),(\color{red}{1},2,3,5,4),(\color{red}{1},2,4,3,5),\cdots\}.$$
Also, notice that the tuple has to be in $X,$ and $(1,1,1,1,1)$ is not a permutation.

It is not clear if by permutation you mean that you have to use every element in $\{1,2,3,4,5\}.$ If so, you will get $(5-1)!$ as the number of elements in $A_1$ because you are fixing the first one and then you have $4$ choices for the second one, and then $3$ choices...

If you allow repetition, then you will have $5$ choices in each of the remaining $4$ positions, so you will end up having $5^4$ elements in $A_1.$

Title: permutation of sets


问:
Calculate the integral $\int_{0}^{1+\log \sqrt 3} |\frac 32 e^{1-x} -\frac 12 e^{x-1}|$
This is small part of a much larger question. My trouble is calculating with the modulus function on. Since I don’t really know which function is greater than the other at, I can’t tell how it will open up. Assuming that there is no graphing calculator (or a calculator of any sort) at my disposal, how should I calculate it?</p>

Body:
hint

$$F(x)=\frac 32e^{1-x}-\frac 12e^{1+x}=$$

$$\frac 12e^{1-x}\Bigl(3-e^{2x}\Bigr)$$

$$e^{2x}<3\iff x<\ln(\sqrt{3})$$

So

$$\int_0^{1+\ln(\sqrt{3})}|F|=\int_0^{\ln(\sqrt{3})}F+\int_{\ln(\sqrt{3})}^{1+\ln(\sqrt{3})}(-F)$$


问:
why derivative of $\sin^{-1}(x)$ is the derivative of the inverse $\sin(x)$?
Why can't we directly apply the chain rule here?

Why $\sin^{-1}x$ is not the same as $1/\sin(x)$?

Is it the general notation as inverse only for trig function?

答:
The arcsine of $x$ is defined as the inverse sine function of $x$ when $-1 \leq x \leq 1$.

When the sine of $y$ is equal to $x$:

$$\sin y = x \quad \tag{*}$$

Then the arcsine of $x$ is equal to the inverse sine function of $x$, which is equal to $y$:

$$\operatorname{arcsin} x = \sin^{-1} x = y$$

You can then use (*) and the chjain rule to investigate the derivative of $\operatorname{arcsin} x$.


问:
Is there a homomorphism $f$ from $(\Bbb Z_4, +_4)$ to $(\Bbb Z, +)$, such that $f(1) =1$?
I think that there is no such homomorphism, at least I couldn't find it. Is it correct?</p>

答:
There is no such homomorphism, since we have the following:

\begin{equation*}
0= f(0) = f(1 + 1 + 1 + 1) = 4f(1) \implies f(1) = 0
\end{equation*}


答:
By the inverse function formula, we have
$$\arcsin'(x)=\frac1{\sin'(y)}, \quad\text{ where } \sin (y)=x.$$

If you want to apply the chain rule, you can apply it to
$$\bigl[\sin(\arcsin(x))\bigr]'=(x)'=1=\sin'(\arcsin(x))\cdot \arcsin'(x),$$
which proves  the above formula if $\sin'(y)\ne0$, taken for granted that $\arcsin(x)$ is differentiable.

Title: why derivative of $\sin^{-1}(x)$ is the derivative of the inverse $\sin(x)$?

Body:
Why can't we directly apply the chain rule here?

Why $\sin^{-1}x$ is not the same as $1/\sin(x)$?

Is it the general notation as inverse only for trig function?


答:
Considerations - $A$ and $B$ each choose problems independently and work on them independently. Also assuming the answers are objective and they are either right or wrong, nothing in between. The given probability of solving is probability of getting the right answer and if anyone of them get the answer right, that question gets considered solved.

First number of ways to ensure all $7$ questions are chosen between the two. This can only happen if each of them have $3$ questions that is common and $2$ questions that are different from the other person.

So $C(7) = {7 \choose 5} {5 \choose 3} {2 \choose 2}$

$P(7) = \displaystyle \frac{{7 \choose 5} {5 \choose 3} {2 \choose 2}}{{7 \choose 5} {7 \choose 5}} = \frac{10}{21}$

Now probability of $A$ solving a problem $= \frac{3}{5}$

Probability of $B$ solving a problem $= \frac{1}{2}$

Probability that a common question is not solved by either of them $= \frac{2}{5} \times \frac{1}{2} = \frac{1}{5}$

So they solve a common question with probability $ = \frac{4}{5}$

So probability of all questions getting solved $= \frac{10}{21} \times (\frac{3}{5})^2 \times (\frac{1}{2})^2 \times (\frac{4}{5})^3$

Title: Probability that all problems are solved

Body:
The problem is

A solves a problem with probability 0.6. B solves a problem with
probability 0.5. They are given 7 problems and each chooses 5 out of
the 7 problems randomly and solves them independently. What is the
probability that all the 7 problems are solved by at least one of
them?

It seems like a binomial distribution problem but I am not sure how to do.

I am thinking that probability that a problem is solved

```<code>P(solved)=P(A solved)+P(B solved)-P(A and B both solved)
         =(5/7)(0.6)+(5/7)(0.5)-(5/7)(5/7)(0.6)(0.5)
         =31/49
</code>```

then all problems are solved is

```<code>P(all solved)=(31/49)^7
</code>```

I don't think I am doing right but am not sure where. Can anyone give a thought?


问:
How do you find the smallest of homeomorphic ordinals?
I am trying to get a better feel for the topology of ordinals and just received a great answer to this question where the Cantor-Bendixson rank and degree turn out to be a complete homeomorphism invariant of countable compact spaces. Now I am curious about what is going on within homeomorphism classes of ordinals. In particular, I want to know how to characterize countable ordinals $\alpha$ which are minimal among all ordinals homeomorphic to $\alpha$.

Certainly finite ordinals and $\omega$ are easy. Next, if $\alpha\cong \omega+1$, then it seems like we would have to have $\omega+1\leq \alpha<\omega +\omega$ since there can only be one limit point in $\alpha$. Things become a little fuzzier for me with ordinals that have infinitely many limit points.

For instance, suppose $\alpha$ is an ordinal homeomorphic to $\omega^{\omega}$. Is it necessarily true that $\alpha\geq \omega^{\omega}$? Is there a general rule for knowing when an ordinal is the smallest among all ordinals homeomorphic to it?

答:
[Edit: I apologize for the multiple corrections. The full result is now stated, and there are links to the details not provided here.]

Very nice question. The following is an answer for successor ordinals:

A non-zero ordinal $\alpha$ is (additively) indecomposable iff whenever $\alpha=\beta+\gamma$, then $\gamma=\alpha$ or $\gamma=0$. This is equivalent to saying that $\alpha=\omega^\delta$ for some $\delta$, where the exponentiation is in the ordinal sense.

Let $t(\alpha)$ denote the order type of the limit points of $\alpha$. The following is proved by a straightforward induction:

Fact 1. Let $0<n<\omega$.

$t(\omega n)=n-1$.

If $\alpha$ is a limit ordinal, $t(\alpha+\beta)=t(\alpha)+1+t(\beta)$.

$t(\omega^{m+1} n)=\omega^m n$ for any $0<m<\omega$.

$t(\omega^\delta n)=\omega^\delta n$ for $\delta$ infinite.

Using Fact 1, we can prove:

Claim. If $\alpha$ is infinite and successor, then the following are equivalent:

No $\beta<\alpha$ is homeomorphic to $\alpha$.

$\alpha=(\gamma n)+1$ for some indecomposable $\gamma$, and some finite $n>0$.

Moreover, $\alpha=(\gamma n)+1$ as in item 2 is homeomorphic to $\alpha+\beta+1$ for any $\beta<\gamma$.

Let's prove the claim. First, note that if $\alpha=(\gamma n)+1$ and $\beta<\gamma$ then $\beta+1+\gamma=\gamma$ so $\alpha=\beta+1+\gamma n+1$ and $\alpha+\beta+1=\gamma n+1+\beta+1$ are homeomorphic. This is because $\alpha$ is the disjoint union of two open sets, one of order type $\alpha$, and one of type $\beta+1$.

(This is why we need the $1$s at the end, to ensure both pieces are open.)

This proves that 1. implies 2. To see the converse, use Fact 1 to argue by induction that if $t(\alpha)$ denotes the order type of the set of limit points of $\alpha$, and if $\gamma$ is an infinite indecomposable ordinal, then no ordinal smaller than $\gamma n+1$ has set of limit points homeomorphic to $t(\gamma n+1)$, and this completes the proof of the claim.

The above deals with successor ordinals. Limit ordinals are different, and I do not currently have a complete answer. For one thing, limit ordinals are not compact, while successor ordinals are. Using Fact 1, it follows immediately that

No ordinal other than $\omega n$ itself is homeomorphic to $\omega n$ for $0<n<\omega$.

Recall Cantor's normal form theorem, that any non-zero ordinal can be written uniquely as
$$ \alpha=\omega^{\beta_0}n_0+\dots+\omega^{\beta_k}n_k $$
where $k\in\omega$, the $\beta_i$ are strictly decreasing, and the $n_i$ are non-zero naturals.

The key to continue is a refinement of the idea of examining order-types: The concept of Cantor-Bendixson derivative. The derivative of a space $X$ is the collection of its limit points. The $\alpha$-th derivative of $X$ is the result of iterating this operation $\alpha$ times:

$X^{(0)}=X$.

$X^{(\alpha+1)}=(X^{(\alpha)})'$ is the space of accumulation points of $X^{(\alpha)}$.

$X^{(\lambda)}=\bigcap_{\alpha<\lambda}X^{(\alpha)}$ for $\lambda$ limit.

By an induction that elaborates the proof of the Fact above, we have:

Fact 2. If $\delta>0$, the $\delta$-th derivative of $\omega^\delta$ is empty, and it is its first empty derivative. Moreover, $(\omega^{\delta} n)^{(\delta)}=\{\omega^{\delta}m\mid 0<m<n\}$ for any $0<n<\omega$.

It follows that $n_0$ in the Cantor normal form of $\alpha$ as above can be recovered by iterating the derivative operation. In particular,

$\alpha=\omega^{\beta_0}n_0+\dots+\omega^{\beta_k}n_k$ cannot be homeomorphic to any ordinal whose Cantor form does not begin as $\omega^{\beta_0}n_0$. No two ordinals of the form $\omega^\delta n$ are homeomorphic, and no ordinal other than $\omega^\delta$ is homeomorphic to $\omega^\delta$.

The observations above almost settle the problem completely. I did some online digging, and found that the problem is completely solved in a technical report of the Institute for Language, Logic and Computation of the University of Amsterdam, the short paper "A classification of ordinal topologies" by Vincent Kieftenbeld and Benedikt Löwe, as of this writing available here.

Let $\omega^{\beta_0}n_0+\dots+\omega^{\beta_k}n_k$ be the Cantor normal form of an ordinal $\alpha$. Write $lc(\alpha)=\beta_0$ and $c(\alpha)=n_0$; finally, set $p(\alpha)=0$ if $\alpha=\omega^{\beta_0}n_0\ge\omega$, and $p(\alpha)=\omega^{\beta_k}$ otherwise. ($lc,c,p$ stand for "limit complexity", "coefficient", and "purity", in the notation of the Kieftenbeld-Löwe paper.)

Theorem (Kieftenbeld-Löwe). $\alpha$ and $\beta$ are homeomorphic iff $lc(\alpha)=lc(\beta)$, $c(\alpha)=c(\beta)$, and $p(\alpha)=p(\beta)$.

It may be worth remarking that the argument holds in ZF, i.e., no use of the axiom of choice is required. The details of the argument can be seen in the paper, but (once we have the right statement), it is actually a nice exercise to finish the proof from the argument started above.

Let me note that as a descriptive set theorist, there is a natural follow up question, namely, when is it that the Borel structures of two ordinals $\alpha$ and $\beta$ are Borel isomorphic. This problem turns out to be more delicate. It is solved in a paper by Su Gao, Steve Jackson, and Vincent Kieftenbeld, "A classification of ordinals up to Borel isomorphism", Fundamenta Mathematicae 198 (2008), 61-76. (As of this writing, the paper is available from Fundamenta's page under subscription, or from Kieftenbeld's page.) Their result uses choice in an essential way, and the problem is far from settled in ZF, even under additional assumptions such as the axiom of determinacy. Sketching the proof would take us far from the current question, but let me give the (AC) statement:

Given $\alpha$, let $\kappa(\alpha)=0$ if $|\alpha|$ is a singular cardinal or countable. Otherwise, let $\kappa(\alpha)$ be the largest cardinal such that $|\alpha|\cdot\kappa(\alpha)\le\alpha$.

Theorem (Gao-Jackson-Kieftenbeld). $\alpha$ and $\beta$ are Borel isomorphic iff $|\alpha|=|\beta|$ and $\kappa(\alpha)=\kappa(\beta)$.


问:
Find original permutation based on intersection sets
Consider the permutation graph below:

Let's say I only have the amount of numbers in the permutation. 5, in this case, and all intersections between the first and the second parallel lines, like {2,5},{2,4}, and {2,3}, for example.

With only this information, is it possible to figure out the original one-liner permutation that defines this graph, which is {4,3,5,1,2}, I think?

Thank you very much :)

答:
Yes, it is possible to reconstruct the permutation based on the total number of elements and the list of "intersections" (these correspond to inversions in the original permutation).

In fact, even less information would be sufficient: we can reconstruct the permutation if, for each number $i$, we know just the count $C(i)$ of numbers smaller than $i$ that intersect with $i$ (we don't need to know which specific numbers it intersects with). In your example, it would be enough to know that $C(1)=C(2)=0$, $C(3)=C(5)=2$ and $C(4)=3$.

The permutation will be built in steps. Starting with an empty list, in $i$-th step we insert number $i$ into the existing list at the right spot, so that the relative ordering of numbers in the list will be the same as in the full permutation. Since by that time we have already placed numbers $1$ to $(i-1)$ in the list and they are already in the correct positions relative to each other, the intersections between the newly-added number and existing ones must be consecutive and on the right-hand side of the list.
Thus, we just need to skip $C(i)$ positions from the right before we insert number $i$ (so if $C(i)=0$, we append number $i$ at the end of the list).

In your example, we would build the list as follows:
$$\begin{array}{lcl}
C(1)=0 & \rightarrow & \mathbf{1} & \\
C(2)=0 & \rightarrow & 1, \mathbf{2} & \\
C(3)=\fbox{2} & \rightarrow & \mathbf{3}, \fbox{1, 2}\\
C(4)=\fbox{3} & \rightarrow & \mathbf{4}, \fbox{3, 1, 2}\\
C(5)=\fbox{2} & \rightarrow & 4, 3, \mathbf{5}, \fbox{1, 2}\\
\end{array}$$


问:
How find all the functions which satisfy the functional equation $f(a+x)-f(a-x)=4ax$?
Determine all functions $f:\mathbb{R}\to \mathbb{R}$ satisfying the equation $f(a+x)-f(a-x)=4ax$, for all $a,x\in \mathbb{R}$, where any real value is available.

I came to the fact that $f(a)=0$, but I still do not know how to get the result to remove $f(x)$. Therefore, it should be confirmed that I can help here the scope of this task.

Thank you very much in advance.

答:
Define $ g : \mathbb R \to \mathbb R $ with $ g ( x ) = f ( a + x ) - ( a + x ) ^ 2 $. Then from
$$ f ( a + x ) - f ( a - x ) = 4 a x \tag 0 \label 0 $$
we get
$$ \left( g ( x ) + ( a + x ) ^ 2 \right) - \left( g ( - x ) + ( a - x ) ^ 2 \right) = 4 a x \text , $$
or equivalently $ g ( - x ) = g ( x ) $; i.e. $ g $ is an even function. Conversely, for any given even function $ g : \mathbb R \to \mathbb R $, if you define $ f : \mathbb R \to \mathbb R $ with $ f ( x ) = g ( x - a ) + x ^ 2 $, then $ f $ will satisfy \eqref{0}, so those form the class of all solutions.


问:
Geometric solution to classic committee problem
Most people know the classic committe style problems.

I read this solution to one of the basic version of the committe problem and was impressed, but not sure why it works.

I was hoping someone could explain why does it work.

答:
Short answer: plane geometry mod $2$.

A longer answer:

There are two different facts in play here.

One is that this type of combinatorial construction is called a block design and is in fact a more special type of design called a finite geometry.  It is similar to, but more general than, the geometry of points and lines, and the terminology is borrowed from geometry. The people in the linked example are what in a design are called "blocks", in a finite geometry are called "lines", and the committees are called "points".

The other fact is that there are finite forms of $n$-dimensional coordinate geometry, and for $n=2$ these are the easiest way to construct very symmetrical and efficient finite geometries (and thus block designs).  For example, take the $49$ points in the plane with integer coordinates modulo $7$, and all $56$ different lines that are solutions sets of $Ax + By + C = 0 \mod 7$ with $(A,B)$ integers that do not both reduce to $0 \mod 7$.

The same construction mod $2$ has $4$ points and $3 \times 2=6$ lines through each point, and a unique line through every two points.  The picture in the link is a drawing of the Cartesian plane mod $2$.

The combinatorics is most perfect when using points and lines from the projective geometry over a finite field, because of the duality between points and lines. In the example mod $7$, the projective plane has $57$ points, $57$ lines, every two distinct lines intersect in one point, every two distinct points have a line that contains them, there are $8$ lines through every point, and $8$ points on every line, which treats points and lines symmetrically. In this problem, the $\mod 2$ design could have been extended to a projective one with $7$ points and lines, $3$ lines through every point and $3$ points on every line, and can be thought of as the projective plane with one line (and its points) removed.


答:
Using the definition of a permutation as a bijective function from a set to itself (rather than related definition of strings of characters each character being used once, etc...) we have that $A_1$ is the set of permutations of $\{1,2,3,4,5\}$ such that $1$ is mapped to $1$.

Equivalently, using the definition of permutations as strings of characters instead, $A_1$ is the set of permutations of $\{1,2,3,4,5\}$ such that $1$ is in the first position.

This includes but is not limited to $12345, 13524, 15243,\dots$ and does not include things like $23451$ or $54321$ since $1$ is not in the first position and further does not include things like $11111$ or $67890$ since these are not permutations of $\{1,2,3,4,5\}$ (the first fails to be a permutation since each character is only allowed to be used exactly once and the second failed because the characters used are not from the correct base set.  equivalently, the first wasn't bijective and the second had the wrong codomain).

It is worth talking about then things like $A_1\cap A_2$ which are those permutations who simultaneously have the first and second terms as fixed points... containing things like $12345, 12543, 12453,\dots$, the first position necessarily being a $1$ and the second position necessarily being a $2$.

It is also worth looking at $A_1^c$, the set of permutations such that $1$ is not a fixed point.

Finally, of considerable importance is the set $A_1^c\cap A_2^c\cap A_3^c\cap A_4^c\cap A_5^c$, the set of permutations on $\{1,2,3,4,5\}$ such that none of the elements are fixed points.  We call a permutation with no fixed points a derangement.

As for counting these, for $|A_1|, |A_1\cap A_2|\dots$ approach directly with rule of product like usual.  For those positions whose values are not forced, pick what element appears in that position and take note of how many options you had given earlier such selections.  You have that $|A_1|=4!$ that $|A_1\cap A_2|=3!$ and so on.

These observations coupled with inclusion-exclusion will then even allow you to calculate the number of derangements, something I leave to you to finish on your own or to read about in the linked article.  I rather strongly suspect that calculating the number of derangements may even be a later part of the current question you are working on or a question to be asked very soon after completing this one since they are so closely related.

Title: permutation of sets

Body:
I have a question regarding the permutation of sets and it is:

Problem: let the sample space $X$ be the set of permutations of $\{1,2,3,4,5\}$, the permutation $\{n_1,n_2,n_3,n_4,n_5\}$ represents the object allocation where for $i,j\in \{1,2,3,4,5\}$ we have $n_i=j$ if person $i$ receives the object by person $j$. Furthermore $i\in \{1,2,3,4,5\}$. If we define the events:

$$A_i=\{(n_1,n_2,n_3,n_4,n_5)\in X\space |\space n_i=i\}$$

My confusions: I do not understand how to list these elements under the defined set of element characteristics this set has for instance, in the sample space $X$, can $n_1=1, n_2=2,n_3=3,n_4=4, n_5=5?$

If not then the values $n_1$, $n_2$,... can take are $n_1=2,3,4,5; n_2=1,3,4,5; ...$ etc. So one possible element of the sample space is $(2,3,4,5,1)\in X?$.

But in the set $A_i,$ now there is a new condition which is $n_i=i$, that means the set $A_1=\{(1,1,1,1,1)\}?$. I am alittle confused on the definition of $n_i=i$ in the set $A_i,$ and how many elements  $A_1, A_2,...,A_5$ contains. Can anyone help me explain or find the elements of the set $A_i$, or just an example for$ A_1$ and $A_2?$ I would appreciate it.


问:
I know this solution but what happens when $ f(x) $ doesn't have derivative
Suppose a continuous function $ f \colon \mathbb{R} \rightarrow \mathbb{R} $ is not identically zero and satisfies the condition $$ f(x + y) = f(x)f(y) \ \ (x , y \in \mathbb{R}) $$
Prove that there exists a number $ a \in \mathbb{R} $ such that $ f(x) = a^x \ \ (x \in \mathbb{R})
$.

I wrote this :
Let's discus the case where $ y = 0 $; In this case the function will look like: $$ f(x + 0) = f(x) \cdotp f(0) $$ We see that: $$ f(x) = f(x) \cdotp f(0) \Rightarrow f(0) = 1 $$
Now let's find the derivative of $ f(x) $

$$ f^{'} (x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}   $$ using the initial formula we can change $ f(x + h) \text{ to } f(x) \cdotp f(h) $ $$  f^{'} (x) = \lim_{h \to 0} \frac{f(x) \cdotp f(h) - f(x)}{h}   $$
$$ f^{'} (x) = f(x) \cdotp \lim_{h \to 0} \frac{f(h) - 1}{h} $$
We can use the fact that: $ f^{'} (0) = \lim_{h \to 0} \frac{f(h) - 1}{h} $. It means that:
$$ f^{'} (x) = f(x) \cdotp f^{'} (0) $$
Let's suppose that $ f^{'} (0) = a $. After denoting $ f^{'} (0) \text{ by } a $, we get the following equation:
$$  f^{'} (x) = f(x) \cdotp a $$
Let's discus the derivative of: $$ f^{'} (x)^{\frac{1}{a}} = \frac{1}{a} \cdotp f (x)^{\frac{1}{a} - 1} \cdotp f^{'} (x) $$
If we plug in $  f^{'} (x) = f(x) \cdotp a $ in the main formula we will get this equation:
$$ f^{'} (x)^{\frac{1}{a}} = \frac{1}{a} \cdotp f (x)^{\frac{1}{a} - 1} \cdotp f(x) \cdotp a  $$
$$ f^{'} (x)^{\frac{1}{a}} = f (x)^{\frac{1}{a}} $$
If the derivative of $ f(x)^{\frac{1}{a}} $ equals to it's value, it means that this function is equal to $ e^x $. thus, we get the following equation: $$ a^{\frac{x}{a}} = e^x $$ $$ a^{\frac{1}{a}} = e $$

答:
It can be proved that $f$ is differentiable using similar methods proving the differentiability of exponential function.

First, because $f$ is continuous, there exists $\delta>0$ such that if $x\in (-\delta,\delta)$, $f(x)>0$ (since $f(0)=1$). Consider the set $S=\mathbb{Q}\cap(0,\delta)$, if there exists $s_1\in S$ and $s_2\in S$ such that $f(s_1)>1$ and $f(s_2)\leq1$. Let $s_1=\frac {m_1}{n_1}$ and $s_2=\frac {m_2}{n_2}$, it is not hard to find $x\in S$ such that $s_1=px$ and $s_2=qx$ for some positive integer $p$ and $q$ (for example, $x=\frac 1{n_1n_2}$). Suppose that $f(x)>1$, then $f(s_1)={f(x)}^p>1$, similarly, $f(s_2)>1$, giving a contradiction. The similarly argument holds when $f(x)=1$ or when $f(x)<1$. Similarly, there does not exist $s_1\in S$ and $s_2\in S$ such that $f(s_1)\ge1$ and $f(s_2)<1$. This shows that the image of $S$ under $f$ either belongs to $(1,\infty)$, $\{1\}$, or $(0,1)$.

Next, consider the set $\mathbb{Q}$. First, notice that if $d\in \mathbb{Q}$, then $d=nx$ for some $x\in \mathbb{Q}\cap (-\delta,\delta)$ and some positive integers $n$. Therefore, $f(d)={f(x)}^n>0$. For any $d_1\in \mathbb{Q}$ and $d_2\in \mathbb{Q}$, WLOG, assuming $d_2>d_1$, it is not hard to find $x\in S$ such that $d_2-d_1=rx$ for some positive integer $r$. Then $f(d_2)=f(d_1)f(rx)=f(d_1){f(x)}^r$. If $f(S)\subset(0,1)$, then $f(d_2)<f(d_1)$ and $f$ strictly monotonically decreases over the set $\mathbb{Q}$, similarly arguments show that $f$ is either strictly monotonic over $\mathbb{Q}$ or equals $1$ for all elements in $\mathbb{Q}$. Note that $\mathbb{Q}$ is dense in $\mathbb{R}$, the continuity of $f$ would then imply $f$ is either strictly monotonic over $\mathbb{R}$ or equals $1$ for all elements in $\mathbb{R}$ and also that $f(x)>0$ for all $x\in \mathbb{R}$.

Finally, the differentiability of $f$ is trivial if $f(x)=1$, so only the case when $f$ is strictly monotonic is considered. Define $g(r)={f(\frac1r)-1\over\frac1r}=rf(\frac1r)-r$ and suppose $f$ increases monotonically. For any $r_1\in\mathbb{Q^+}$ and $r_2\in\mathbb{Q^+}$, let $r_1=\frac {m_1}{n_1}$ and $r_2=\frac {m_2}{n_2}$. WLOG, one may assume $r_2>r_1$. Note that ${f(\frac 1{r_1})}^{m_1n_2}=f(n_1n_2)=f(\frac 1{r_2})^{n_1m_2}$, so let $f(\frac 1{r_1})=1+a$ and $f(\frac 1{r_2})=1+b$ (note also $f(x)>1$ if $x>0$). $r_2>r_1$ means that $n_1m_2>m_1n_2$ and the monotonicity of $f$ means that $a>b$. Now, if $m_1n_2a\leq n_1m_2b$, then $(m_1n_2-i)a\leq (n_1m_2-i)b$ for all positive integer $i$, so $\binom{n}{i}a^i\leq\binom{m}{i}b^i$ for all positive integer $i\leq m_1n_2$, putting all these inequalities into the binomial expansion of ${(1+a)}^{m_1n_2}$ and ${(1+b)}^{n_1m_2}$ would result in ${(1+a)}^{m_1n_2}<{(1+b)}^{n_1m_2}$, which is a contradiction. Hence, $m_1n_2a>n_1m_2b$, $r_1a>r_2b$, and $r_1f(\frac 1{r_1})-r_1>r_2f(\frac 1{r_2})-r_2$, which means $g(r)$ strictly decreases monotonically over $\mathbb{Q^+}$. Notice that $g(r)$ is continuous over $\mathbb{R^+}$ and $\mathbb{Q^+}$ is dense in $\mathbb{R^+}$, this implies that $g(r)$ strictly decreases monotonically over $\mathbb{R^+}$. Notice further that $g(r)>0$ for $r\in\mathbb{R^+}$, the completeness of real number would then imply the limit of $g(r)$ exists as $r\to\infty$. For the final step of the proof, notice that $f(x)f(-x)=f(0)=1$ so $g(-r)=-rf(-\frac 1r)+r={rf(\frac 1r)-r\over f(\frac 1r)}$. Continuity of $f$ would then imply that $\lim_{r\to\infty} f(\frac 1r)=f(0)=1$, giving $\lim_{r\to\infty} g(-r)=\lim_{r\to\infty} g(r)$, this means both $\lim_{h\to0^+} {f(h)-1\over h}$ and $\lim_{h\to0^-} {f(h)-1\over h}$ exist and are equal, showing that $f$ is differentiable at $0$. If $f$ monotonically decreases, define $h(r)=f(-r)$, then $h(x+y)=h(x)h(y)$, $h$ is continuous, and $h$ increases monotonically, and then the differentiability of $h$ would imply the differentiability of $f$.


问:
To estimate a holomorphic function.
Let $f:\mathbb{C}\to \mathbb{C}$ be a holomorphic map such that
$$|f(z)|\leq 1, \forall z\in\mathbb{R},$$
and $$|f(z)|\leq C e^{|z|}, \forall z\in\mathbb{C},$$ for some $C>0.$

Can we conclude that $$|f(z)|\leq C e^{|Im(z)|}, \forall z\in\mathbb{C},$$ for some $C>0?$

答:
Assume $C>1$ wlog. Consider $g(z)=f(z)e^{iz}$. On the real axis $|g(z)| \le 1$ and on the positive imaginary axis $|g(z)|=|f(z)|e^{-|z|} \le C$, while in the upper plane $|g(z)| \le Ce^{|z|}$ since $|e^{iz}| \le 1$ there.

Applying Phragmen Lindelof on the two quadrants in the upper plane with angles $\pi/2$ we get $|g(z)| \le C$ (see proof below) in the upper half-plane hence $|f(z)| \le Ce^{\Im z}, \Im z \ge 0$

(for example if $z$ is in the first qudrant - let $\epsilon >0, h(z)=e^{-\epsilon (ze^{-i\pi /4})^{3/2}}g(z), \rho \le |z| \le R, 0 \le \arg z \le \pi /2$ where the $3/2$ power is defined as usual using the principal value of the logarithms; then if $z=re^{it}, 0 \le t \le \pi/2, \Re (ze^{-i\pi /4})^{3/2}=r^{3/2}\cos (\frac{3(t-\pi/4)}{2}) \ge r^{3/2} \cos \frac{3\pi}{8}$ hence $|h(z)| \le |g(z)|e^{-\epsilon r^{3/2} \cos \frac{3\pi}{8}}$ so on the segment boundaries of the domain $|h(z)| \le C$ while on the arc boundaries $|h(z)| \le e^{-\epsilon R^{3/2} \cos \frac{3\pi}{8}+cR}, |h(z)| \le e^{-\epsilon \rho^{3/2} \cos \frac{3\pi}{8}+c\rho}$ and obviosuly both exponential tend to $1$ as $R \to \infty, \rho \to 0$ so $|h(z)| \le C$ on the domain for large $R$ and small $\rho$ hence on the full quadrant. Letting now $\epsilon \to 0$ we see that the same result holds for $g$ again first on some bounded domain as before and then letting $R \to \infty, \rho \to 0$; same proof with small changes clearly applies if $z$ is in the second quadrant, we just rotate by $-3\pi /4$ in the definition of $h$)

Considering now $g_1(z)=f(z)e^{-iz}$ we get same as above except that we use the negative imaginary axis/lower half-plane, so overall we get $|f(z)| \le Ce^{\Im z}, \Im z \ge 0$ and $|f(z)| \le Ce^{-\Im z}, \Im z \le 0$ which is precisley the required result so done!

Title: To estimate a holomorphic function.


问:
Generating functions and a closed form for the Fibonacci sequence - the big picture
I have spent the last few hours trying to understand one way of deriving a closed form for the Fibonacci sequence. As part of improving my mathematical maturity, I am trying to learn to see the "big picture" of what I'm doing as opposed to myopically following the details of a derivation or proof and then forgetting most of what I've done within a few weeks or months.

Below I will post my derivation so that it can be checked for errors and general clarity, but what I would like also ask what the proper intuition or high-level perspective is on what I've done.

As I look over my work, the key takeaways I see are that we put the Fibonacci sequence into the form of a generating function, and in particular we managed to put the generating function into a compact rational form. Once this was done, the rest of the work essentially involved analyzing the rational form of the generating function and extracting information from it until we were able to write the generating function (in its formal power series form) in two different ways, compare coefficients and thus derive a closed form for the Fibonacci sequence.

If these observations are apt, then perhaps the big takeaway is that generating functions can be useful when they make it possible to package a sequence into a form that allows algebraic and/or analytic techniques to be brought to bear on the sequence, when it is represented as a generating function.

I would appreciate if anyone can tell me whether my perspective is reasonable or not.

My exposition:

The Fibonacci numbers are a sequence $1, 1, 2, 3, 5, 8, 13, \dots$. The first two numbers are 1, and then every subsequent number is the sum of the prior two. Let $(a_n)$ be the sequence of Fibonacci numbers and $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ be the generating function. Consider that

\begin{align*}
x^2 f(x) + x f(x) &= a_0 x^2 + a_1 x^3 + a_2 x^4 + \dots + a_0 x + a_1 x^2 + a_2 x^3 + \dots\\
&= a_0 x + (a_0 + a_1) x^2 + (a_1 + a_2) x^3 + \dots\\
&= a_0 x + a_2 x^2 + a_3 x^3 + \dots\\
&= f(x) - a_0 - a_1 x + a_0 x\\
&= f(x) - 1 - x + x \text{ (using the known values for } a_0 \text{ and } a_1)\\
&= f(x) - 1.
\end{align*}

Thus $f(x) = \frac{1}{1 - x - x^2}$. Now factor $1 - x - x^2$ as $(1 - \alpha x)(1 - \beta x)$, so that $- \alpha - \beta = -1$ (or more naturally, $\alpha + \beta = 1$) and $\alpha \beta = -1$. If you solve this system of equations you will end up with $\alpha = \frac{1 + \sqrt 5}{2}$ and $\beta = \frac{1 - \sqrt 5}{2}$, or the reverse. Now consider the partial fraction decomposition

\begin{align*}
f(x) &= a_0 + a_1 x + a_2 x^2 + \dots\\
&= \frac{1}{1 - x - x^2}\\
&= \frac{1}{(1 - \alpha x)(1 - \beta x)}\\
&= \frac{a}{1 - \alpha x} + \frac{b}{1 - \beta x}\\
\Rightarrow 1 &= a(1 - \beta x) + b(1 - \alpha x).
\end{align*}

This gives us another system of equations such that $a + b = 1$ and $-a \beta - \alpha b = 0$ (or more naturally, $a \beta + \alpha b = 0$.) If you solve \textit{this} system of equations you get $a = \frac{\sqrt 5 + 1}{2 \sqrt 5}$ and $b = \frac{\sqrt 5 - 1}{2 \sqrt 5}$.\

Thus,

\begin{align*}
f(x) &= a_0 + a_1 x + a_2 x^2 + \dots\\
&= \frac{1}{1 - x - x^2}\\
&= \frac{1}{(1 - \alpha x)(1 - \beta x)}\\
&= \frac{a}{1 - \alpha x} + \frac{b}{1 - \beta x}\\
&= a(1 + \alpha x + \alpha^2 x^2 + \dots) + b(1 + \beta x + \beta ^2 x^2 + \dots)\\
&= (a + b) + (a \alpha + b \beta)x + (a \alpha ^2 + b \beta^2)x^2 + \dots
\end{align*}

which explicitly means that $a_k = (\frac{\sqrt 5 + 1}{2 \sqrt 5})(\frac{1 + \sqrt 5}{2})^k + (\frac{\sqrt 5 - 1}{2 \sqrt 5})(\frac{1 - \sqrt 5}{2})^k$, as desired.

答:
It's a good approach. One thing that can be simplified a little bit is:

$$
f(x)=\frac{1}{(1-\alpha x)(1-\beta x)} = \frac{1}{\alpha - \beta} \cdot \frac{\alpha (1-\beta x)  - \beta(1-\alpha x)}{(1-\alpha x)(1-\beta x)} = \frac{\alpha/(\alpha - \beta)}{1-\alpha x} - \frac{\beta/(\alpha - \beta)}{1-\beta x}.
$$

(And this is not hindsight.)


问:
How to calculate smallest pattern size based on set of ratios
So I have x number of items, each one has its own appearance ratio for making a pattern, of which I'm trying to determine the smallest possible pattern. The appearance ratios for all items total up to 1.

This is a bit of a complicated question to get my head around so I'll try and explain with examples…

For example there may be four letters (a, b, c, d) with respective ratios of 0.4, 0.3, 0.2, 0.1, which would require a minimum pattern size of 10 (as 0.1 is the smallest ratio, and 0.1 / 1 = 10). Resulting pattern would be aaaabbbccd.

In another example, of 0.4, 0.4, 0.2 we would get a minimum pattern size of 5 (aabbc).

However an example of 0.3, 0.3, 0.4 would require a pattern size of 10 (aaabbbcccc) because the 0.4 cannot be divided by the 0.3 without resulting in a decimal.

What algorithm could calculate the pattern size based on the input ratios?

答:
As Qiaochu Yuan posted, what you're looking for is the least common denominator of the ratios involved. Many thanks to him - the post I previously had here did not deal with ratios whose decimal expansions are infinite. I have corrected this post accordingly. We can find the LCD of a set of ratios writing the ratios as fractions with integral numerators and any common denominator, and then dividing the denominator by the gcd of these numerators.

For example, with $.3, .3, .4 = \frac{3}{10}, \frac{3}{10}, \frac{4}{10}$, gcd$(3, 3, 4) = 1$, so the pattern size is calculated to be $\frac{10}{1} = 10$.

By contrast, for the example $.2, .4, .4 = \frac{2}{10}, \frac{4}{10}, \frac{4}{10}$, gcd$(2, 4, 4) = 2$, so the pattern size is calculated to be $\frac{10}{2} = 5$.

For an additional example, $.35, .35, .3 = \frac{35}{100}, \frac{35}{100}, \frac{30}{100}$, gcd$(35, 35, 30) = 5$, so the pattern size is calculated to be $\frac{100}{5} = 20$. The pattern is, correspondingly, (${\bf aaaaaaabbbbbbbcccccc}$)


问:
Find the 200th number that is divisible by 3 or 4
My lecturer gave to me this question

$Q)$ Let the set $A = \mathbb N \setminus$ $ (\{3k \mid k \in \mathbb{N} \}$ $\cup$  $\{4k \mid k \in \mathbb{N} \})$

Say the element $a_1(=1) < a_2(=2) < a_3(=5) <...$ for $a_i \in  \mathbb{N}$ (I.e. $a_n < a_{n+1}$)

Find the number of the $a_{200}$

Here is my solution.

As I've known the $[\frac n p]$ is the number of the $p$-multiples which is not larger than $n$ in $\mathbb N$

Since the $\vert \{n(\in \mathbb N) \vert n \leq a_{200} \} \vert =200$, all I have to do just find the $n$ satisfying  $200  = n - [\frac n 3 ] - [\frac n 4] + [\frac n {12}]$ by inclusion–exclusion principle.

But the problem is there isn't only $n$ satisfying $200  = n - [\frac n 3 ] - [\frac n 4] + [\frac n {12}]$ When I check those, $n$ can be there are $398, 400$.

Actually the answer was $398$. Why does the $400$ can't be answer?

Which point did I have in my solution?

Any correct solution and explanation always welcome.

Thanks.

答: 399 is a multiple of 3 and 400 a multiple of 4.  Both 398 and 400 have 200 terms below or equal, but only 398 is a term in the sequence.</p>


问:
Three player combinatorial game - minimizing communication between Alice and Bob
Consider the following game between three parties: Alice, Bob and a Referee. The game starts with $n$ closed boxes. For some fixed $k<n$ known to all parties, the Referee freely chooses $k$ distinct boxes and places a prize inside each of them. Alice sees the Referee do this and thus, she knows which boxes have a prize. Bob now enters the room. He can talk to Alice, then choose one box and if this box has a prize, he can keep it.

What is the smallest number of bits of information that Alice needs to convey to Bob such that Bob is guaranteed to win a prize?

The naive strategy is for Alice to pick a prize-containing box at random and give the ID of this box to Bob. This costs $\log n$ bits of information since she picks one box out of $n$ choices. But given that there are $k$ choices and any of them would do the job, can Alice and Bob win the game with less than $\log n$ bits of communication? If yes, what should their strategy be?

EDIT: I am happy to assume the Referee is not adversarial if that admits a better strategy for Alice and Bob.

答:
An obvious strategy is: Alice picks the lowest box id and sends it. There are $n-k+1$ possible values, hence the information content is at most $\log(n-k+1)$

Actually, if we assume that the $k$ boxes are chosen at random, the distribution of the picked one will not be uniform, hence the information content will be less than that.

The pmf of the smallest member of a $(n,k)$ selection, indexed from $j=0\cdots n-k$ is

$$P(j)= \frac{1}{\binom{n}{k}}\binom{n-j}{k}\frac{k}{n-j}$$

I'm not sure if the entropy of this distribution can be put in a simple form.

Edited: for large $n$ the entropy (in nats) of the above gives me the following not-too-illuminating expression:

$$H\approx \frac{k}{n} \frac{e^{-k/n}}{1-e^{-k/n}} - \log(1- e^{-k/n})$$

For large $n$ and $k$, with $k/n \to 0$, this behaves as $\log(n)-\log(k)+ O(1)$


问:
Show that the following is continuous
Let (X,d) be a metric space with disjoint, nonempty, closed subsets $A,B \subset X$.

Show that the function $V: X \to [0,1]$ defined by

$$V(x) = \frac{\operatorname{dist}(x,A)}{\operatorname{dist}(x,A) + \operatorname{dist}(x,B)}$$

is continuous. Then prove that any connected metric space containing at least two points is uncountable.

I'm kind of in the process of staring and not sure how to start. I'm thinking that I need to use the triangle inequality somehow to put $\delta$ in. Like I know I have $|x - y| < \delta$, so if I only examine the numerator (for example) and I say $d(x,y) \leq d(x,A) + d(y,A)$, then I could plug delta in. I'm not sure how to get to there though as the denominator would become quite complicated. Any tips?

答:
Note that $V=f\circ g$, where $g:X\to [0,\infty)^2\setminus \{(0,0)\}$ is given by $x\mapsto (d(x,A),d(x,B))$ and $f$ is given by $(s,t)\mapsto \frac{s}{s+t}$. Now, $g$ is continuous by the basic properties of metric spaces and $f$ is continuous by basic real analysis. Hence, $V$ is continuous.

Indeed, $g$ maps $X$ into $[0,\infty)^2\setminus \{(0,0)\}$ since $A$ and $B$ are disjoint and closed. To see this, note that $d(x,A)=0$ implies $x\in A$, since $A$ is closed, which then implies that $x\not \in B$, which implies that $d(x,B)>0$, since $B$ is closed.

Title: Show that the following is continuous


问:
How can I see if this integral is convergent or not $\int_0^\infty \ \frac{1}{1 + x^4\sin x} \,dx $
I think the integral is convergent, but I don't know how to prove it.

$\int_0^\infty \ \frac{1}{1 + x^4\sin x} \,dx $

答:
Let $f(x)=1+x^4\sin x$. Its first positive zero $x_0\simeq 3.1517$ is slightly greater than $\pi$. At this point, $f'(x_0)=4x_0^3\sin x_0+x_0^4\cos x_0\simeq -99.9362\neq 0$. So $f(x)\sim f'(x_0)(x-x_0)$ whence
$$
\frac{1}{1+x^4\sin x}=\frac{1}{f(x)}\sim\frac{1}{f'(x_0)(x-x_0)}
$$
when $x$ approaches $x_0$. So the integrand is continuous and positive on $[0,x_0)$, and by comparison
$$
\int_0^{x_0}\frac{1}{1+x^4\sin x}dx=+\infty.
$$
A fortiori, this function is not integrable over $[0,+\infty)$.</p>


问:
Doubly exponential complexity of Presburger arithmetics
I am trying to understand the proof of the aforementioned fact.
For context, here's a rough outline of [what I am understanding to be] the idea behind the proof: in the language we construct a formula $\phi(x)$ asserting "machine $x$, when started on input $x$, halts in less than $f(|x|)$ steps", where $f:x\mapsto 2^{2^{kx}}$ for some $k$.
Next, given any machine $M$ intending to decide $PrA$, we construct a machine $M'$ as follows: when started on input $w$, $M'$ overwrites it with $\neg\phi(w)$, then runs $M$ to decide it. If $M$ decides $\neg\phi(w) \in PrA$, $M'$ halts, otherwise it loops forever. The conclusion is that any machine that decides $PrA$ must take $\geq f(|\sharp M'|)$ steps to decide $\neg\phi(\sharp M')$ - otherwise we get a contradiction when we run $M'$ on $\sharp M'$. So far so good, I guess.

I get lost when it is time to construct $\phi$, though. For example, one of the building blocks [used in the construction] of $\phi$ is a formula $I_{n}(x)$, $|I_{n}(x)| = O(n)$, asserting "$x$ is less than $f(n)^{2}$". Now, the paper doesn't show how to construct this formula, and I have no idea how to, too, given that we can only use addition and we have that bound there.

What am I missing?

EDIT, as suggested: the proof I am talking about is in Rabin and Fischer's paper - .pdf available here.1 And one further thing: I found one post from Lipton's blog where he talks about the "trick" used to construct $I_{n}$ succinctly. It is a sketch only and unfortunately not enough for me. It is mentioned however that the trick was previously discovered by Fischer and Meyer, and Volker Strassen, independently, but I couldn't track down these papers describing it in detail - if anyone knows about them, please tell me!

1Michael J. Fischer, Michael O. Rabin: Super-exponential complexity of Presburger arithmetic. Also: CiteSeerX, MIT, DOI: 10.1007/978-3-7091-9459-1_5, http://hcs64.com/files/cc.pdf#page=35

答:
Fischer and Rabin don't explicitly construct $_()$. Instead they claim its existence is clear in the proof of Theorem 11. This is essentially true, since the multiplication formula $M_n(x,y,z)$ they construct in the proof of Theorem 8 satisfies $M_n(x,y,z) \leftrightarrow x < 2^{2^n} ∧ x·y = z ∧ x ∈ N.$

This fact can be used to define $_()$. Namely, set $_() = M_{n+1}(x,0,0)$ for x ∈ N. Since x·0 = 0 and x ∈ N, $M_{n+1}(x,0,0) \leftrightarrow x < 2^{2^{n+1}} = (2^{2^n})^2$


问:
Prove that the sequence $\{q_n\}_{n \geq 1}$ diverges to $\infty.$

Let $\{x_n \}_{n \geq 1}$ be a sequence of rational numbers converging to $\pi.$ Let for all $n \geq 1,$ $x_n = \frac {p_n} {q_n},$ where $p_n,q_n \in \Bbb Z$ with $\text {gcd}\ (p_n,q_n) = 1.$ Prove that the sequence $\{q_n \}_{n \geq 1}$ diverges to $\infty.$

How do I prove that? Any help will be highly appreciated.

Thanks in advance.

答:
Suppose that $\{q_n\}$ is bounded, and suppose without loss of generality that $q_n > 0$. Since $q_n \in \mathbb{Z}$ is bounded, define $q = \text{lcm}\{q_n$}. Then we know that there exists $z \in \mathbb{Z}$ such that the following holds:

\begin{equation}
\frac{z}{q} < \pi < \frac{z+1}{q}.
\end{equation}

Then any $\frac{p_n}{q_n}$ can be written in the form $\frac{z'}{q}$, so cannot improve on the bounds in the above inequality. So we have that $\frac{p_n}{q_n}$ is bounded away from $\pi$.


问:
Bounded and invertible operator on dense subspace
Who can give me an operator like this or show it doesn't exist: Operator T: X-->Y, is a bijection from normed linear space X to normed linear space Y. X, Y are equipped with the same norm, and X is a proper dense subset of Y. Both T and inverse of T are bounded.</p>

答: Suppose $X = Y$ and $T$ be the Fourier transform on the Schwartz space of functions. If $X = Y$, it is trivially dense in Y and the Fourier transform is bounded on the Schwartz space with the $L^2$ norm (and so is its inverse).</p>


问:
Connected graphs and trees
I have some trouble  prooving 1. to 2. and 2. to 3.

"Let $G$ be a connected graph. Prove that the next statements are equivalent:

$G$ has a single cycle.

$|E(G)| = |V(G)|$.

$\exists \ e \in E(G)\ $ such that $\ G - e\ $ is a tree."

I already have a $\textbf{Lema}$ that says "Let $G$ be a connected graph and $C$ a cycle in $G$. if $e$ is an edge of $G$, then $G - e$ is connected" and it maybe can be used to proove 1. to 3. , but I don't know how to continue with the other proofs.

答:
$\bf1\to3$: If $G$ has a single cycle, we can break it by removing any edge $e$ in the cycle without disturbing the connectedness of $G$. $G−e$ is a connected, acyclic graph i.e. a tree.

$\bf3\to2$: Given for some $e$, $G-e$ is a tree. The number of edges in a tree is one less than the number of vertices. $|E(G-e)|=|E(G)-\{e\}|=|E(G)|-1$. Note that we don't remove any vertex when we remove an edge, so  $|V(G-e)|=|V(G)|$. thus $|V(G)|-1=|E(G)|-1$, giving us $|V(G)|=|E(G)|$.

$\bf2\to1$: If $G$ is acyclic, then $G$ is a tree. So $|E(G)|=|V(G)|−1$, which is a contradiction. So $G$ has at-least one cycle. Let $C_1,C_2$ be cycles in $G$. We can remove an edge $e_1\in E(C_1)$ without disturbing the connectedness of $G$. $G-e_1$ is connected and $|E(G-e_1)|=|E(G)|-1=|V(G-e_1)|-1$ so $G-e_1$ is a tree. Since trees are acyclic, $e_1\in C_2$. Since $e_1$ is arbitrary, we conclude $C_1=C_2$ and $G$ has a single cycle.

Title: Connected graphs and trees


问:
A stick of fixed length is broken into 3 pieces. Construct triangle
A stick of length 1 is broken into 3 pieces in the following way:

We chose random interior point on the stick and break it into two pieces

After that we choose the longest of the two pieces, choose random point on it and break it again, getting 3 pieces total.

The task is to find probability that it would be possible to construct a triangle using that pieces.

I've came up with the following idea:

Let $X_1, X_2$ be random variable, uniformly distributed across all points on the stick ($X_1, X_2\in [0,1]$). It is clear, that Probability space may be illustrated as follows (marked with yellow):

And basing on triangle inequality we may highlight areas on the graph, that would suit us in terms of constructing triangle:

So, we get that $|\Omega|=S_{yellow section}=\cfrac{3}{4}$
And probability we are searching for: $Pr(A)=\cfrac{S_{blue section}}{S_{yellow section}}=\cfrac{1}{3}$. So answer here is $\cfrac{1}{3}$, however my mate got very different result, including $log$. Can you help me with this task/find mistake in my solution?

Any response is welcome and would be appreciated a lot.

答:
Your solution does not fulfill the random protocol described in the problem. The second break is not at a random point in $[0,1]$, but at a random point in the longer piece of the first break.

Choose the first breaking point at $x\in\,\bigl]{1\over2},1\bigr]$ and the second at $xy$ with $y\in\,\bigl]{1\over2},1\bigr]$. The variable $(x,y)$ is then uniformly distributed in the square $Q:=\bigl]{1\over2},1\bigr]^2$ of area ${1\over4}$. In this way we obtain three pieces of length
$$\ell_1=xy,\quad \ell_2=x-xy=x(1-y),\quad \ell_3=1-x\ .$$
The $\ell_i$ can be the sides of a triangle iff all of them are $<{1\over2}$. For $\ell_2$ and $\ell_3$ this is automatically the case, and we are left with the condition $\ell_1=xy<{1\over2}$. Let $S$
be the corresponding part of $Q$. The required probability then is
$$p={{\rm area}(S)\over{\rm area}(Q)}=4\int_{1/2}^1\left({1\over2x}-{1\over2}\right)dx=\ldots=2\log2-1\approx0.3863\ .$$


问:
A normal random variable independent of each component of a multivariate normal random vector.
Suppose that $\mathbf{Y}\sim N_3(0,\,\sigma^2\mathbf{I}_3)$ and that $Y_0$ is $N(0,\,\sigma_0^2)$, independently of the $Y_i$'s.
My question is that does $(\mathbf{Y}, Y_0)$ also have multivariate normal distribution? By using moment generating function, it suffices that $\mathbf Y$ and $Y_0$ are independent. But is this the case?

答:
This is true. To verify this, you can check that any of the equivalent definitions of the multivariate normal distribution hold. (Checking the MGF is one of them.)

Edit: In light of kimchi lover's answer, I should mention that I am assuming $Y_0$ and $\mathbf{Y}$ are independent, which is stronger than assuming that the pair $Y_0$ and $Y_i$ are independent for each $i$.


问:
Show that h is measurable.
Let $X$ be a set, $\mathcal{A}$ and $\sigma$-algebra of subsets of $X$. Let $f,g: X \to \mathbb{R} \cup \{\pm  \infty\}$ be measurable functions and $A \subseteq X$ measurable. Define $h: X \to \mathbb{R} \cup \{ \pm \infty \}$ by

\begin{equation}
  h(x)=\begin{cases}
    f(x) & \text{if $x\in A$},\\
    g(x) & \text{if $x \notin A$}.
  \end{cases}
\end{equation}
Show that h is measurable.

I think that we start by showing that $A \cap h^{-1}(a, \infty] = A \cap f^{-1}(a, \infty] $ and $A^c \cap h^{-1}(a, \infty] = A^c \cap g^{-1}(a, \infty]$. And then show that $h^{-1}(a, \infty]$ is measurable for every $a \in \mathbb{R}$. Is this correct?

答:
I think it is easier to note that
$$h= f\chi_A + g \chi_{A^c}$$
and then invoke that products and sums of measurable functions remain measurable.

Title: Show that h is measurable.


问:
Show that $\sum\limits_{ n \in \mathbb{Z} \setminus \{0\}}\frac{e^{2 \pi i x n}}{n}$ is a convergent series where $x$ is any real
Show that $\displaystyle \sum_{ n \in \mathbb{Z} \setminus \{0\}}^{} \frac{e^{2 \pi i xn}}{n}$ is a convergent series for all real x. I think that this could be done by breaking up the sum into two pieces; the piece that has n going to $\infty$ and the other going to $-\infty$. From there I have applied that fact that $e^{2 \pi x i n}= \cos(2\pi x n)+ i\sin(2 \pi x n)$ and then the fact that  $\displaystyle \frac{\cos(2\pi x n)}{n}+ i\frac{\sin(2 \pi x n)}{n}$ is a sequence such that the series of $\displaystyle \frac{\cos(2\pi x n)}{n}$ and $\displaystyle \frac{\sin(2 \pi x n)}{n}$ both have convergent series. The thing is that I only know these two series are convergent when n goes from 1 to infinity. Is it still true in going from -1 to - infinity? Does the method of this proof even work? Thanks!</p>

答:
Since $$\frac{e^{i2\pi nx}}{n}+\frac{e^{-i2\pi nx}}{-n}=2i\frac{\sin(2\pi nx)}{n}$$ your series is equal to
$$2i\sum_{n=1}^\infty \frac{\sin(2\pi nx)}{n}=4\pi i\sum_{n=1}^\infty \frac{\sin(2\pi nx)}{2n\pi}.$$
But $\sum_{n=1}^\infty \frac{\sin(2\pi nx)}{2n\pi}$ is the Fourier sine series of $$f(x)=\frac{1}{2}\left(\frac{1}{2}-x\right), 0\le x\le 1/2.$$ Let $F(x)$  be the odd period 1 extension of f(x). By convergence of Fourier series, the series $\sum_{n=1}^\infty \frac{\sin(2\pi nx)}{2n\pi}$ converges to $\frac{F(x-)+F(x+)}{2}$ for all $x$.

You can also use Dirichlet Test for convergence.