问:
Solve the recurrence relation $T(n)=3T(n/4)+n$ given that $T(1)=2$
Question:

Assume that a recurrence relation is given as below:

$T(n)=3T(n/4)+n$

and we know that $T(1)=2$.

We want to solve the relation (find an explicit definition of $T(n)$
which does not rely on itself).

My solving:

Equation 1: $T(n)=3T(n/4)+n$

Equation 2: $T(n/4)=3T(n/(4^2))+n/4$

Equation 3: $T(n/(4^2))=3T(n/(4^3))+n/(4^2)$

Substituting the equations (2) and (3) in (1), we get
$T(n) = (3^3)T(n/(4^3)) + ((3^2)n)/4^2 + 3n/4 + n$.

Generalizing it we get $T(n) = (3^k)T(n/(4^k)) + n[1 + 3/4 + (3/4)^2 + … + (3/4)^k-1]$

$k = \log_4(n)$

$T(n) = (3^{(\log_4(n))})*2 + 4n((3/4)^{\log_4(n)}-1)$

How to solve it further?

答:
As

$$
T\left(4^{\log_4 n}\right)=3T\left(4^{\log_4 \frac n4}\right)+n
$$

calling $\mathcal{T}(\cdot) = T\left(4^{(\cdot)}\right)$ and $z = \log_4 n$ we follow with the recurrence

$$
\mathcal{T}(z) = 3\mathcal{T}(z-1)+4^z
$$

with solution

$$
\mathcal{T}(z) = 3^{z-1}c_0 + 4(4^z-3^z)
$$

and now going backwards with $z = \log_4 n$ we arrive at

$$
T(n) = 4(n-3^{\log_4 n})+3^{\log_4 n-1}c_0
$$

and now as $T(1) = 2\Rightarrow c_0 = 6$


问:
Singularities of $f(z)=z/\cos(z)$
Regarding complex functions (in complex variables), I was wondering why the function $g(z)= \cos(z)$ has a singularity at $z = \infty$ but $f(z)= \dfrac{z}{\cos(z)}$ does not.

I am a bit confused about the concept of singularities at $\infty$.

Thank you.

答:
For $\,\frac1z\,$ "close enough to zero" ( say, $\;\frac1{|z|}<\sqrt[3]6\;$ ) , we have

$$f\left(\frac1z\right)=\frac1{z\cos\frac1z}=\frac1z\frac1{\left(1-\frac1{2z^2}+\frac1{24z^4}-\ldots\right)}=$$

$$=\frac1z\left(1+\frac1{2z^2}+\frac1{4z^4}+\ldots\right)=\frac1z+\frac1{2z^3}+\ldots$$

which shows $\,f(z)\;$ has a singularity at $\,z=\infty\;$

ContentLicense: CC BY-SA 3.0

Title: Singularities of $f(z)=z/\cos(z)$


问:
Solution for approximating square roots?
I just saw a post on instagram which said that

$$\sqrt{x}\approx \frac{x+y}{2\sqrt{y}}$$

I tried it out on a few values, and surprisingly, it came within 1 decimal point of the actual answer. Is there a reason for this or is it coincidental?

y is the closest perfect square to x

答:
This is because, for $x\approx y$:

$$\sqrt{xy}\approx \frac{x+y}{2}$$

This is a consequence of the AM-GM Inequality, which states that:

$$\frac{x+y}{2}\geq\sqrt{xy}$$

For all $x, y\geq 0$, with equality occurring if and only if $x=y$.

ContentLicense: CC BY-SA 4.0


问:
What is the minimum number of broken queens required to cover an $n\times n$ board?
Consider an $n\times n$ board.  Assume that the sides of the board are parallel to the north-south and the east-west directions.  If a piece of "broken queen" is placed on this board, it "covers" each cell in the same column, each cell in the same row, each cell in its southeast direction, and each cell in its northwest direction. What is the minimum number of broken queens required to cover the board?

If $m_n$ is this minimum number, I know that $m_n\ge \lceil (2n-1)/3\rceil$.  To show this, let $m=m_n$ and consider a 'covering' of the board by $m$ broken queens.  When $n>1$ it is clear that $m<n$.  Hence there are at least $n-m$ rows and $n-m$ columns that do not have any broken queens in them.  The $(n-m)^2$ cells in the intersections of these rows and columns need at least $2(n-m)-1$ broken queens to cover them.  Therefore $m\ge 2(n-m)-1$ giving $m\ge (2n-1)/3$.

I have a hard time finding an example that requires exactly $m_n$ broken queens for an arbitrary $n$.  But I think that $m_n$ is sharp.  Btw if you know where this problem came from plz let me know.  I believe it is a contest question.  I was asked by a friend, but the friend doesnt know where the question came from.  If the cells are labelled by $(i,j)$ where $i$ increases from $1$ to $n$ as we go east and $j$ increases from $1$ to $n$ as we go north, my guess is that we place $m_n$ broken queens at cells $(i,j)$ with $i+j=2,5,8,..., 3m_n-1$.  I'm not sure if the locations can be random.  If not, I don't see a pattern yet.

答: I just figured out.  Put the $m_n$ broken queens on the cells $(i,j)$ where $i\le j\le i+1$ and $i+j=2, 5,8,...,3m_n-1$.


问:
A problem related to localization
Let $A$ be integrally closed (not necessary be Dedekind), $K=\operatorname{Frac}(A),L/K$ Galois, $B$ is the integral closure of $A$ in $L,p$ is a maximal ideal in $A$. We know that the galois group $G$ acts transitively on maximal ideals in $B$ lying over $p$. If we weaken $p$ maximal to prime, let’s consider localization. Then we know that $G$ acts transitively on prime ideals in $B_{p}$ lying over $A_{p}$’s unique maximal ideal $m_p$. But now does $G$ acts transitively on prime ideal in $B$ lying over $p$?

答:
Atiyah–Macdonald  Exercise 5.13:

In the situation of Exercise 12 [Let $G$ be a finite group of automorphisms of a ring $A$, and let $A^G$ denote the subring of $G$-invariants, that is of all $x \in A$ such that $\sigma(x) = x$ for all $\sigma \in G$.], let $\mathfrak p$ be a prime ideal of $A^G$, and let $P$ be the set of prime ideals of $A$ whose contraction is $\mathfrak p$. Show that $G$ acts transitive on $P$. In particular, $P$ is finite.

So it suffices to show that $B^G = A$. The $\supseteq$ direction is clear. The $\subseteq$ direction follows from $B^G \subseteq B \cap K = A$ since $A$ is integrally closed in $K$.

So the answer is yes.

Title: A problem related to localization


问:
The torus is connected
Let $T^2=S^1 \times S^1$ be a torus, where $S^1 \subset \mathbb{R}^2$ is the unit circle. Is $T^2$ connected? If so, how does one show this?

答:
I found an answer that somewhat follows the results we have seen in my topology course so far. For this we use a couple of definitions:

Definitions.

A topological space $X$ is called connected, if there does not exist any decomposition $X = U \cup V$ into non-empty, disjoint subsets $U,V \subseteq X$.

A topological space $X$ is called path-connected, if $\forall x,y \in X$ there exists a continuous map $\gamma:[a,b] \to X$ with $[a,b] \subseteq \mathbb{R}$ and $\gamma(a)=x,\,\gamma(b)=y$.

Proof.
We make use of some results that can be proven independently. First, we notice that

For $n \geq 1$ we have that the $n$-sphere $S^n = \{x \in \mathbb{R}^{n+1} \mid \|x\|_2 = 1\}$ is path-connected.

Now, because of the fact

Let $X$ and $Y$ be topological spaces. $X$ and $Y$ are path-connected $\iff X \times Y$ is path-connected.

we can conclude that $S^1 \times S^1$ is path-connected. Finally,

Path-connected topological spaces are connected.

Hence, $T^2 = S^1 \times S^1$ is connected. QED.

Title: The torus is connected


答:
Google AM–GM inequality.

If we square any real number $z$, which can be expressed as a difference of two other real numbers $x$ and $y$, the result is always greater or equal $0$, this means $\color{blue}{z^2 \geq 0}$, assume $z = x-y$, it follows $$\color{blue}{z^2} = (x-y)^2 = x^2 \color{red}{-2xy} + y^2 = x^2 \color{red}{+ 2xy} + y^2 \color{red}{- 4xy} =(x+y)^2-4xy\color{blue}{\geq 0} $$

$$\Rightarrow (x+y)^2-4xy\geq 0 \Leftrightarrow(x+y)^2\geq 4xy \Rightarrow x+y \geq \sqrt{4xy} \Leftrightarrow \frac{x+y}{2\sqrt{y}} \geq \sqrt{x}$$

The result is:

$$\sqrt{x} \leq \frac{x+y}{2\sqrt{y}}  $$

If $x = y$, then

$$\sqrt{x} =\frac{x+y}{2\sqrt{y}}  $$

Example: $$\sqrt{4} =\frac{4+4}{2\sqrt{4}} = 2$$

Title: Solution for approximating square roots?

Body:
I just saw a post on instagram which said that

$$\sqrt{x}\approx \frac{x+y}{2\sqrt{y}}$$

I tried it out on a few values, and surprisingly, it came within 1 decimal point of the actual answer. Is there a reason for this or is it coincidental?

y is the closest perfect square to x


答:
Using Taylor series around $y=x$ (assuming them to be positive), we have
$$\sqrt{x\,y}=x+\frac{y-x}{2}-\frac{(y-x)^2}{8 x}+\frac{(y-x)^3}{16 x^2}+O\left((y-x)^4\right)$$ and,sice it is an alternating series, you can build a lot of ineaqualities.


问:
Axiom of choice and function with empty codomain
I'm having a little problem here, namely if the axiom of choice (Wikipedia) is

$$\forall X \left[ \emptyset \notin X \implies \exists f: X \to \bigcup X \quad \forall A \in X \, ( f(A) \in A ) \right]$$

and I choose the nonempty $X=\{\emptyset\}\neq \emptyset$ for which only $\emptyset\in X$ and hence $A=\emptyset$, then I get

$$\exists f:\{\emptyset\}\to\emptyset\ \  \text{such that}\ \  f(\emptyset) \in \emptyset.$$

The last point seems wrong in itself though. Of course, there is no actual value $f(\emptyset)$, so $f(\emptyset) \in \emptyset$ doesn't say much. It might be just taken to be a legal statement. I haven't seen that written down anywhere though.

答:
Note that $X=\{\varnothing\}$ satisfies the statement vacuously, so it's fine. You can change the statement to the following:

$$\forall X\exists f\left[f\colon X\to\bigcup X\cup\{\varnothing\}\land\forall A\in X(f(A)\in A\lor A=\varnothing)\right]$$

It allows $\varnothing\in X$, and therefore $X=\{\varnothing\}$. But it's harder to understand it this way, so it's easier to just require $\varnothing\notin X$.


问:
How to factorize the following expression: $2x^4 + 9x^3+8x^2 +9x+2=0$

How to factorize the following expression: $2x^4 + 9x^3+8x^2 +9x+2=0$

I have tried finding a root through putting values, but I can't find any factor.

Please help.

PS: I'm an elementary student, the question standard might not match with that of the community but any help would be sincerely
appreciated.

答:
Hint:

This is a special polynomial, as the coefficients are symmetric.

Now set

$$t:=x+\frac1x$$ so that $$t^2=x^2+\frac1{x^2}+2.$$

Express the equation in terms of $t$ and $t^2$.

$$2x^2+9x+8+\frac 9x+\frac2{x^2}=2t^2+9t+4=(2t+1)(t+4)=0.$$ $$2x^2+x+2=0,\\x^2+4x+1=0.$$


问:
Why is $\int_{\Omega}X^+\,dP = \int _{0}^{\infty}P(X^+ > t)\,dt$?
$X$ be a random variable and $P$ is a probability measure on $\Omega$. Is it true that $$\displaystyle{\int_{\Omega}}X^+\,\mathrm{d}P = \displaystyle{\int _{0}^{\infty}}P(X^+ > t)\,\mathrm{d}t\,, $$

where $X^+(\omega)=\max\{X(\omega),0\}\,$?

I was thinking along the guidelines of Fubini's theorem as probability is a $\sigma$-finite measure.
The left hand side of the integral is actually area under a curve taking vertical strips and the right hand side is calculating the same area taking horizontal strips. So by Fubini's theorem they must be equal.

But how do I rigorously show this ?

答:
First note that $\displaystyle{\int _{0}^{\infty}}P(X^+ > t)dt =\displaystyle{\int _{0}^{\infty}}\int 1(X^+ > t)\, dP\,dt $, where $1(A)$ is the indicator function of the event $A$. Then use Tonelli's theorem to interchange the integral and get
$$
\displaystyle{\int _{0}^{\infty}}\int 1(X^+ > t)\, dP\,dt =\int \displaystyle{\int _{0}^{\infty}}1(X^+ > t)\, dt\,dP = \int \displaystyle{\int _{0}^{X^+}}\, dt\,dP =\int {X^+}\,dP.
$$


问:
Verifying that $\mathbb Q=\bigcup_{n\ge 1} H_n$
Let $G=(\mathbb Q,+)$ and $r_1=p_1/q_1, r_2=p_2/q_2\in G$. I want to prove that:

$\langle r_1,r_2\rangle\subseteq \langle\frac{1}{q_1q_2}\rangle$

If $r_1,r_2,...,r_n\in G$ then $\langle r_1,r_2,...,r_n\rangle$ is cyclic.

If $H_n=\langle \frac{1}{n!}\rangle$ then every $H_n$ is cyclic, $$H_1\subset H_2\subset H_3\subset...$$ and $\mathbb Q=\bigcup_{n\ge 1} H_n$.

I can see that $r_1\in\langle\frac{1}{q_1q_2}\rangle$ and the same is true for $r_2$. This ends proving $1.$ I guess I should use the first part to see the second part clearly. So, I think I should have $r_i\in \langle\frac{1}{q_1q_2q_3...q_n}\rangle$. Is my guess right because it makes the second proved? For the third part it is obvious that every $H_n$ is cyclic. Assuming that chain of inclusions is correct and that $\bigcup_{n\ge 1} H_n\subseteq\mathbb Q$, just make me an small finial hint. Please verify my way of solution. I will be thankful if you have any other point of views. Thanks

答:
Your intuition seems correct, but your arguments need to be more rigorous. The crucial step in proving all of these statements is knowing that $a \in \langle b \rangle$ means there is $n \in \Bbb Z$ for which $a = nb$. This follows from the definition of cyclic groups in the additive notation. Another important fact is that $a \in \langle b \rangle$ implies $\langle a \rangle \subset \langle b \rangle$. Try to prove this if you aren't already familiar with it.

To get to specifics, 1 follows from the statements above. For 2, it's not sufficient to prove $r_i \in \left\langle \frac{1}{q_1 \cdots q_n} \right\rangle$. This would imply $\langle r_1, \ldots, r_n \rangle \subset \left\langle \frac{1}{q_1 \cdots q_n} \right\rangle$. You need to show $\langle r_1 \cdots r_n \rangle = \langle s \rangle$ for some $s \in \Bbb Q$.

For 3 and 4, use my initial statements and make sure to show containment in both directions in 4!


问:
Exercise 8.5.13 Terence Tao's Analysis 1

Background

I am trying to prove a lemma in Terence Tao's Analysis 1 which is used to prove the statement below.

Let $X$ be a partially ordered set with ordering relation $\leq$, and let $x_0$ be an element of $X$. Then there is a well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element, and which has no strict upper bound.

My Understanding

The following definitions are relevant:

Let $X$ be a partially ordered set with ordering relation $\leq$, and let $Y$ be a subset of X. If $x \in X$, we say that $x$ is an upper bound for $Y$ iff $y \leq x$ for all $y \in Y$. If in addition $x \notin Y$ then we say $x$ is a strict upper bound of $Y$.

Tao assumes to the contrary that the statement above is false. Then every well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element has at least one strict upper bound. Appealing to the Axiom of Choice we can assign to each such subset $Y$ a strict upper bound $s(Y) \in X$. He then makes the following definition.

A subset $Y$ of $X$ is said to be good set if $Y$ is well-ordered, contains $x_0$ as its minimal element and obeys the property that $x = s(\{y \in Y: y < x\})$ for each $x \in Y$ where $x \neq x_0$.

The lemma set as Exercise 8.5.13 and the one i'm trying to prove is

If $Y$ and $Y'$ are two good subsets of $X$, then every element of $Y'\setminus Y$ is a strict upper bound for $Y$, and every element of $Y \setminus Y'$ is a strict upper bound for $Y'$

I got stuck for some time so I peeked at the hint in the textbook which was roughly show that $s(Y \cap Y ')$ exists and that $Y \cap Y'$ is good. Then show that $s(Y \cap Y') = \min(Y \setminus Y')$ if $Y \setminus Y'$ is non-empty and simlarly when $Y$ and $Y'$ are interchanged.

I have managed to show $s(Y \cap Y ')$ exists and that $Y \cap Y'$ is good but I am terribly stuck with regards to the last part of the hint. If one can point me in the right direction or give me a hint that would be extremely helpful and appreciated.

Note: I have already looked at the following relevant question Exercise 8.5.13 Tao Analysis 1 but the accepted answer uses Zorn's Lemma which unfortunately is not satisfactory since my lemma is used to prove the statment I mentioned at the start of the question. And this statement is used to prove Zorn's Lemma which is Exercise 8.5.14

答:
I think I have managed to solve my problem:

(*)We first note that using the "generalised strong induction principle" (Proposition 8.5.10) that we can show
$\{y \in Y: y \leq a \} = \{y \in Y': y \leq a \} = \{y \in Y \cap Y': y \leq a \}$ for each $a \in Y \cap Y'$. Also observe that $Y \cap Y'$ is well-ordered since $Y$ is well-ordered and that $\min(Y \cap Y') = x_0$. This implies that $s(Y \cap Y')$ exists.

Now we claim that if $Y\setminus Y'$ is non-empty then $s(Y \cap Y') = \min(Y \setminus Y')$. By assumption $Y$ is good and $\min(Y \setminus Y') \in Y$ which implies that $\min(Y \setminus Y') = s(\{y \in Y: y < \min(Y \setminus Y')\})$. It thus suffices to show that $\{y \in Y: y < \min(Y \setminus Y')\} = Y \cap Y'$. Clearly $\{y \in Y: y < \min(Y \setminus Y') \subseteq Y \cap Y'$ otherwise we would contradict the minimality of $\min(Y \setminus Y')$. Now let $y'\in Y \cap Y$ since $Y$ is totally ordered we must have $\min(Y \setminus Y') < y$ or $y < \min(Y \setminus Y')$. We need only consider the first case. In this situation we have that $\min(Y \setminus Y') \leq y$, where $y \in Y \cap Y'$. But then using (*) we can conclude that $\min(Y \setminus Y') \in Y \cap Y'$ which is a contradiction. Therefore our claim must be true. The same arguement with $Y$ and $Y'$ interchanged shows that when  $Y'\setminus Y$ is non-empty then $s(Y \cap Y') = \min(Y' \setminus Y)$.

Suppose to the contrary that $Y \setminus Y'$ and $Y' \setminus Y$ are non-empty. Then the claim we have just proven yields $\min(Y' \setminus Y) = \min(Y \setminus Y')$ which leads to a contradiction. Therefore at least one of the two sets $Y \setminus Y'$ and $Y' \setminus Y$ is empty.

Without loss of generality suppose that $Y' \setminus Y$ is empty. Then it is vacously true that every element of $Y'\setminus Y$ is a strict upper bound of $Y$. Conversly since $Y' \setminus Y$ is empty it follows that $Y' \subseteq Y$ therefore $Y \cap Y' = Y$. Also we have $s(Y \cap Y') = \min(Y \setminus Y')$ since $Y \setminus Y'$ is not empty. This implies that every element of $Y \setminus Y'$ is a strict upper bound of $Y'$ since otherwise there is an element $y'$
in $Y \setminus Y'$ and an element $y'' \in Y'$ such that $y'' > y$ but $s(Y \cap Y')$ is a strict upper bound of $Y'$. From this we can conclude that $\min(Y \setminus Y') > y'$ a contradiction. Thus it is indeed the case that If $Y$ and $Y'$ are two good subsets of $X$, then every element of $Y'\setminus Y$ is a strict upper bound for $Y$, and every element of $Y \setminus Y'$ is a strict upper bound for $Y'$. As desired.


问:
Least squares solution problem

Let $A = \begin{pmatrix}
2 & 0 & 2 \\
1 & 1 & 2 \\
1 & 1 & 2 \\
2 & 0 & 2
\end{pmatrix}$. Determine the least squares solution for $Ax = e_4.$

The least squares solution can be found from $A^TAx = A^Te_4$. This is problematic since $A^TAx = \begin{pmatrix}10&2&12\\ 2&2&4\\ 12&4&16\end{pmatrix}x = \begin{pmatrix}2\\ 0\\ 2\end{pmatrix}$, but $x$ cannot be solved from here since I cannot multiply the RHS by $A^{T^{-1}}$... What can I do here?

答:
As the matrix

$$B=A^TA=\begin{pmatrix}10&2&12\\ 2&2&4\\ 12&4&16\end{pmatrix}$$ is not invertible, the solution of the least square problem is a linear subspace of dimension greater or equal than $1$. Indeed the kernel of $B$ is a linear line.

You can solve the system
$$Bx = \begin{pmatrix}2\\ 0\\ 2\end{pmatrix}$$ to find this linear line.

Title: Least squares solution problem


问:
On the parity of $\left\lfloor{\frac{3^n}{2^n}}\right\rfloor$
Let $a_n=(-1)^{\left\lfloor{\frac{3^n}{2^n}}\right\rfloor}$ and $$s_n=\sum_{k=1}^na_k.$$

Is it true that $s_n\le 0$ for all $n\geq 1$ ?  (This is true for $n\le 100000$.)

In other words, odd numbers are always more than even numbers on the sequence $\left\lfloor{\frac{3^n}{2^n}}\right\rfloor$.
This is unexpected, I think they should be roughly equal, and even numbers will exceed odd numbers sometimes.

答:
Not a complete answer, but here are some results from computer simulation:

While the sequence $s_n$ starts out being negative for quite some time (as mentioned in the question, for more than the first $100\,000$ terms), it does reach positive values eventually. The first time this happens is for $n=331\,523$; there we have $165\,762$ even and $165\,761$ odd numbers. So the answer to the question would be no.

After that it continues to alternate between positive and negative values.

See this plot of $s_n$ for $n$ up to $1\,000\,000$:

Here is how it continues up to $5\,000\,000$:

Of course it would be nice if this could be verified without computer help... or to see a theoretical description of the asympotic behavior of $s_n$...


问:
Finding $f$ such that $\forall x,y \in \mathbb{R},f(x+y)f(x-y)=(f(x))^2$
Find all the possible continuous functions $f : \mathbb{R} \to \mathbb{C}$ such that $|f|=1$ and $$\forall x,y \in \mathbb{R},f(x+y)f(x-y)=(f(x))^2.$$
By taking suitable values for $x,y$ we have $f(0)=1,f(2x)=(f(x))^2,$ also $x \to e^{icx},c \in \mathbb{R}$ verifies the above functional equation. Tried to find $f(nx)$ in term of $f(x),$ but unfortunately didn't find anything.

Any suggestions?

答:
$a=x+y$

$b=x-y$

Because $f(2x)=(f(x))^2$ it is easily seen $f(a)f(b)=f(a+b)$

$f(a)=e^{ig(a)}$

This implies $g(a)+g(b)+k2\pi=g(a+b)$ where $k$ is an integer

define $h(a)=g(a)+k2\pi$

$h(a)+h(b)=g(a)+g(b)+k4\pi$

$h(a)+h(b)=g(a+b)+k2\pi=h(a+b)$

we have $h(a)+h(b)=h(a+b)$ which is Cauchy functional equation with solution $h(a)=ca$ provided $h(a)$ is measurable ($f(a)$ is measurable)

Therefore $f(x)=e^{icx-ik2\pi}=e^{icx}$


问:
Example where $_ (x), _ (y) \geq 10$ but $_ℎ (x) ≤ 1$

Let $ :  → $ and $ :  → $ be continuous functions between arbitrary vector spaces, and let $ℎ =  ◦ $ . Suppose $ =  (x)$ and $ = (y) = ℎ(x)$. Give a concrete example where $ \kappa_f (x), \kappa_g (y) \geq 10$ but $_ℎ (x) \leq 1$.

I am using the relation $\kappa = \frac { ||J(x)||}{||f(x)||/||x||}$ for each of the three functions. I was able to find the upper bound on $_ℎ(x)$ in terms of $\kappa_ (x)$ and $\kappa_ (y)$ (Came out to be $\kappa_ℎ(x) \leq \kappa_f (x)*\kappa_g (y)$). However, now, I am unable to find an example which satisfies the given condition. How can I go about finding an example? Can I generalise anything from this?

Please note that $\kappa$ here is the relative condition number.

答:
I dont' see how that is possible... If you think of the case $X=Y=Z =\mathbb{R}$, you have that
$$
\kappa_{g \circ f}(x) = \dfrac{x (g\circ f)'(x)}{(g\circ f)(x)}= \dfrac{x f'(x)g'(f(x))}{g(f(x))} = \dfrac{x f'(x)}{f(x)}\cdot \dfrac{f(x) g'(f(x))}{g(f(x))} = \kappa_f(x)\cdot \kappa_g(f(x))
$$

If $|\kappa_f|, |\kappa_g| \ge 10$, you will fatally have that $|\kappa_{g\circ f}| \ge 100$.

There may be a problem in the original statement of the problem... It is possible to choose particular vector spaces and applications $g,f$ to fulfill the requirement but, for arbitrary vector spaces, it is not always possible to find such applications. Maybe the OP could clarify the intent.


问:
How to prove Chebyshev's result: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n $ as $n\to\infty$?
I saw reference to this result of Chebyshev's:
$$\sum_{p\leq n} \frac{\log p}{p} \sim \log n \text{ as }n \to \infty,$$
and its relation to the Prime Number Theorem. I'm looking into an information-theory proof by Kontoyiannis I was wondering if anyone could give me a sense for how difficult or involved the usual proof is.

I don't really need to see the whole thing in detail, more wondering about the general difficulty/complexity of the result. Thanks!

答:
This is an application of the Shapiro -Tauberian theorem.  Please see Tom Apostol's "Introduction to Analytic Number theory'' text.

Theorem: Let $\{a(n)\}$ be a non negative sequence such that

$\displaystyle\sum\limits_{n \leq x }a(n) \biggl[\frac{x}{n}\biggr] = x\log{x} + \mathcal{O}(x)$ for all $x \geq 1$.

Then

For $x \geq 1$ we have $$\sum\limits_{ n \leq x} \frac{a(n)}{n} = \log{x} + \mathcal{O}(1)$$

There is a constant $A >0$ and an $x_{0} > 0$ such that $$\sum\limits_{ n \leq x} a(n) \leq Bx$$ for all $x \geq 1$.

There is a constant $A>0$ and an $x_{0}>0$ such that $$\sum\limits_{ n \leq x} a(n) \geq Ax$$ for all $x \geq x_{0}$.

Lemma 1. We have $$\sum\limits_{n \leq x} \Lambda(n) \biggl[\frac{x}{n}\biggr] = \log[x]!$$ where $\Lambda(n)$ denotes the Von-Mangoldt function which is defined as $$\Lambda(n) = \biggl\{ \begin{array}{cc} \log{p} & \text{if} \ n=p^{m} \ \text{for some prime} \ p \\\ 0 & \text{otherwise}\end{array}$$

Proof. \begin{align*} \sum\limits_{n \leq x}\Lambda(n) \biggl[\frac{x}{n}\biggr] =\sum\limits_{n \leq x}\sum\limits_{d \mid n} \Lambda(d)=\sum\limits_{n \leq x } \log{n} = \log[x]! \quad \biggl[ \because \sum\limits_{d \mid n} \Lambda(d) = \log{n} \ \biggr]
\end{align*}

Lemma 2. $\displaystyle \sum\limits_{n \leq x} \Lambda(n)\biggl[\frac{x}{n}\biggr] = x\log{x}  + \mathcal{O}(\log{x})$.

Proof. Taking $f(t) = \log{t}$ in the Euler's Summation formula, we have
\begin{align*}
\sum\limits_{n \leq x} \log{n} &= \int\limits_{1}^{x} \log{t} \ dt + \int\limits_{1}^{x} \frac{t-[t]}{t}\ dt - ( x -[x])\cdot \log{x} \\\ &= x\log{x} - x + 1 + \int\limits_{1}^{x} \frac{t-[t]}{t} \ dt + \mathcal{O}(\log{x}) \\\ &= x \log{x} + \mathcal{O}(\log{x}) \qquad \Biggl[ \because \int\limits_{1}^{t} \frac{t-[t]}{t} \ dt = \mathcal{O}\biggl(\int\limits_{1}^{t} \frac{1}{t} \ dt\biggr)=\mathcal{O}(\log{x})\Biggr]
\end{align*}

Corollary. Take $a(n)= \Lambda(n)$. By Shapiro-Tauberian theorem, we then have $$\sum\limits_{n \leq x} \frac{\Lambda(n)}{n} = \log{x} + \mathcal{O}(1)$$

Lemma 3. For $x \geq 2$ we have $$\sum\limits_{p \leq x}\biggl[\frac{x}{p}\biggr]\log{p} = x\log{x} + \mathcal{O}(x)$$

Proof. Since $\Lambda(n)=0$ unless $n$ is a prime power, we have $$\sum\limits_{n \leq x} \biggl[\frac{x}{n}\biggr]\Lambda(n)= \mathop{\sum\limits_{p} \sum\limits_{m=1}^{\infty}}_{p^{m} \leq x}\biggl[\frac{x}{p^{m}}\biggr] \Lambda(p^{m})$$

For $p^{m} \leq x$ we have $p \leq x$. Also $\displaystyle \Bigl[\frac{x}{p^{m}}\Bigr]=0$ if $p >x$, so we can write the last sum as $$\sum\limits_{p \leq x}\ \sum\limits_{m=1}^{\infty}\biggl[\frac{x}{p^{m}}\biggr]\log{p}=\sum\limits_{p \leq x} \biggl[\frac{x}{p}\biggr]\log{p} + \sum\limits_{p \leq x} \ \sum\limits_{m=2}^{\infty} \biggl[\frac{x}{p^{m}}\biggr]\log{p}$$

Now we prove that the last sum above is $\mathcal{O}(x)$.  We have
\begin{align*}
\sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \biggl[\frac{x}{p^{m}}\biggr] &\leq \sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \frac{x}{p^{m}} = x \sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \biggl(\frac{1}{p}\biggr)^{m} \\\ &= x \sum\limits_{p \leq x} \log{p} \cdot \frac{1}{p^{2}} \cdot \frac{1}{1-\frac{1}{p}} = x \sum\limits_{p \leq x} \frac{\log{p}}{p(p-1)}\\\ & \leq \sum\limits_{n=2}^{\infty}\frac{\log{n}}{n(n-1)} = \mathcal{O}(x)
\end{align*}

Suppose you set $$\Lambda_{1}(n) = \biggl\{ \begin{array}{cc} \log{p} & \text{if} \ n \ \text{is a prime} \\\ 0 & \text{otherwise}\end{array}$$ then you have from the above Lemma $$\sum\limits_{n \leq x} \Lambda_{1}(n) \biggl[\frac{x}{n}\biggr] = x\log{x} + \mathcal{O}(x)$$ Now applying the Shapiro - Tauberian theorem with $a(n)= \Lambda_{1}(n)$ gives $$\sum\limits_{p \leq x} \frac{\log{p}}{p} = \log{x} + \mathcal{O}(1)$$

Everything Can be found in Apostol's book. I just thought TeXing it here would be nice.


问:
Why does an exponential function eventually get bigger than a quadratic
I have seen the answer to this question and this one.

My $7$th grade son has this question on his homework:

How do you know an exponential expression will eventually be larger than any quadratic expression?

I can explain to him for any particular example such as $3^x$ vs. $10 x^2$ that he can just try different integer values of $x$ until he finds one, e.g. $x=6$. But, how can a $7$th grader understand that it will always be true, even $1.0001^x$ will eventually by greater than $1000 x^2$? They obviously do not know the Binomial Theorem, derivatives, Taylor series, L'Hopital's rule, Limits, etc,

Note: that is the way the problem is stated, it does not say that the base of the exponential expression has to be greater than $1$. Although for base between $0$ and $1$, it is still true that there exists some $x$ where the exponential is larger than the quadratic, the phrase "eventually" makes it sound like there is some $M$ where it is larger for all $x>M$. So, I don't like the way the question is written.

答:
I posted one answer already, in which I provide my understanding of what the teacher is actually asking for.

That said, I also want to provide a weird take on this problem.

The pluses pile up faster.

an integer bigger than zero is made of a pile of 1's and pluses.

$3 = 1 + 1 + 1$

$5 = 1 + 1 + 1 + 1 + 1$

$6 = 1 + 1 + 1 + 1 + 1 + 1$

Adding two numbers together is just bringing all the pluses together.

$6 + 2 = (1 + 1 + 1 + 1 + 1 + 1) + (1 + 1)$

$6 + 3 = (1 + 1 + 1 + 1 + 1 + 1) + (1 + 1 + 1) $

$6 + 4 = (1 + 1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1) $

Multiplication is repeated addition.

$2 \times 3$ means "add together two stacks of three."

$3 \times 3$ means "add together three stacks of three."

$1 \times 3 = (1 + 1 + 1)$

$4 \times 3 = (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1)$

$5 \times 3 = (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1)$

$6 \times 3 = (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1)$

The pluses pile up faster when you multiply than when you add things because you are adding them over and over.

Exponentiation is repeated multiplication.

$3 ^ 4$ means is the same as $3 \times 3 \times 3 \times 3$, which means "add three stacks of three, then add together three stacks of that resulting one, then add together three stacks of THAT resulting one."

$3 ^ 1 = (1 + 1 + 1)$

$3 ^ 2 = (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1)$

$3 ^ 3 = (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1) + (1 + 1 + 1)$

The pluses pile up faster when you exponentiate things than when you multiply things because you are multiplying then over and over.

A quadratic expression is just one multiplication.

$a ^ 2 = a \times a$

$b ^ 2 = b \times b$

$c ^ 2 = c \times c$

The pluses pile up in same speed as multiplication does.

An exponential expression is many multiplications.

$a ^ 2 = a \times a$

$a ^ 3 = a \times a \times a$

$a ^ 4 = a \times a \times a \times a$

The pluses pile up in the same speed as exponentiation does, so an exponential expression piles up pluses faster than a quadratic expression.

The speed in which an expression gets larger is equal to the number of new pluses it is getting at every step.

Multiplication gets more pluses each step than addition, as it is addition done over and over.
Exponentiation gets more pluses each step than multiplication, as it is multiplication done over and over.

The other numbers around don't change the speed, so they don't matter to see how fast things are growing.

Quadratic:

$10 + 2 ^ 2 = (1+1+1+1+1+1+1+1+1+1) + (1+1) + (1+1) $

$10 + 3 ^ 2 = (1+1+1+1+1+1+1+1+1+1) + (1+1+1) + (1+1+1) + (1+1+1) $

$10 + 4 ^ 2 = (1+1+1+1+1+1+1+1+1+1) + (1+1+1+1) + (1+1+1+1) + (1+1+1+1) + (1+1+1+1) $

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

Exponential:

$4 + 2 ^ 2 = (1+1+1+1) + (1+1) + (1+1) $

$4 + 2 ^ 3 = (1+1+1+1) + (1+1) + (1+1) + (1+1) + (1+1) $

$4 + 2 ^ 4 = (1+1+1+1) + (1+1) + (1+1) + (1+1) + (1+1) + (1+1) + (1+1) + (1+1) + (1+1) $

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

It's getting pluses way faster!

The number of pluses those extra numbers add are fixed, so they don't influence the speed of which the numbers grow. It may take some time, but eventually the exponential one will be getting pluses faster than the quadratic one.


问:
KS2 long division problem
Just seeking a little help with one of my daughter's Yr6 math questions,  as the answer I get  on a calculator is different from what she (and I) get by doing it the long division way.

The question is 2912 ÷ 52

Now by calculator it's 56, but by the long division way (admittedly I'm a little rusty on the method nowadays) I come up with 57 r48, which is completely wrong but I can't figure out why,  yet when I simply work out 52 x 56 I get 2912.

I'm assuming I'm missing something,  but not having needed to work out long division in my head since I left school,  I'm (embarrassingly) not proving to be much use so any help would be grateful.

Thanks in advance.

答:
I will explain a possible explanation to the problem, so you can check your work by using many possible methods of division. Here's how I'd solve it:
100 × 4 = 400. So, since 25 × 4 = 100, we can assume that $25\times 4\times 4 = 400$, where $4\times 4 = 16$, from your basic times tables. So, we can say that 25\times 16 = 400. Now that we've gotten 400 into groups of 25, now we can add the extra $400 + 25 = 425$, and $25 × 1 = 25$, so $25 × (16 + 1) = 25 × 17$. So, now, we have the fact family $25 × 17 = 425$, and, since division is backwards multiplication, we can switch around the fact family to then get $425 ÷ 25 = 17$, and this is our final answer.

And now, allow me to answer your question about the problem $2,912 ÷ 57$. Yet again, we only have to find the fact family. You already solved the crucial multiplication part, which is $52\times 56=2912$. Then, we take that, and we reverse it to make $2,912 ÷ 52=56$, the answer you wanted to know in the first place.

Hopefully this was helpful in answering your question, and I hope you can now get a right answer, regardless of disagreement from your calculations and the calculator's calculations.

Title: KS2 long division problem


答:
You probably have information about $4$ degree symmetric polynomials in your textbook.  Since it is in my textbook, I thought of dividing directly each side $x ^ 2.$

Here is an alternative way:

$$2x^4 + 9x^3+8x^2 +9x+2=(x^2+ax+b)(2x^2+cx+d)$$

$$2x^4 + 9x^3+8x^2 +9x+2= 2x^4+x^3(c+2a)+x^2(2b+ac+d)+x(ad+bc)+bd$$

So, you get

$$\begin{cases} c+2a=9 \\ 2b+ac+d=8 \\ad+bc=9 \\ bd=2\end{cases}$$

For the next trick you can take $b=±1, d±2$ or $b±2, d=±1.$

Of course only $1$ pair will work.

Then you will get the quadratic equation respect to $a$ (or $c$).

You don't need to think for 1000 years :)

Body:
How to factorize the following expression: $2x^4 + 9x^3+8x^2 +9x+2=0$

I have tried finding a root through putting values, but I can't find any factor.

Please help.

PS: I'm an elementary student, the question standard might not match with that of the community but any help would be sincerely
appreciated.


问:
Recurrence relation for the volume of a series of truncated cones
I'm struggling to find the recurrence relation to evaluate the volume of a solid formed by a series of truncated cones one on top of the other. The image below illustrates the problem for 2 truncated cones, with the solid being formed by the complete revolution of the area around the $z$ axis. Each $i$ truncated cone is characterized by its height $H_i$ and the aperture angle $\alpha_i$, while the smallest radius is $R$ and $0\le\alpha<\frac{\pi}{2}$.

Since the volume of a truncated cone is given by:
$$V = \frac{\pi H}{3}\left(r_1^2+r_1r_2+r_2^2\right)$$

For 1 truncated cone:
$$V_1 = \frac{\pi H}{3}\left[R^2+R(R+H_1\tan\alpha_1)+(R+H_1\tan\alpha_1)^2\right]$$

For 2 truncated cones:
$$V_2 = \frac{\pi}{3}\left\{H_1\left[R^2+R(R+H_1\tan\alpha_1) + (R+H_1\tan\alpha_1)^2\right] + H_2\left[(R+H_1\tan\alpha_1)^2 + (R+H_1\tan\alpha_1)(R+H_1\tan\alpha_1+H_2\tan\alpha_2)+(R+H_1\tan\alpha_1+H_2\tan\alpha_2)^2 \right]\right\}$$

And so on. Just by analyzing the expressions, my first thought was to propose the following formula for a series of $n$ truncated cones:
$$V_n = \frac{\pi}{3}\sum_{i=1}^{n}{H_i\left[\left(R+H_i\tan\alpha_i+H_{i-1}\tan\alpha_{i-1}+H_{i-2}\tan\alpha_{i-2}+...\right)^2 +\left(R+H_i\tan\alpha_i+H_{i-1}\tan\alpha_{i-1}+H_{i-2}\tan\alpha_{i-2}+...\right)\left(R+H_{i-1}\tan\alpha_{i-1}+H_{i-2}\tan\alpha_{i-2}+...\right) + \left(R+H_{i-1}\tan\alpha_{i-1}+H_{i-2}\tan\alpha_{i-2}+...\right)^2 \right]} $$

But i'm not sure if this is a rigorous solution or the most elegant way to represent this volume. For example, if $i<1$, than both $H_i$ and $\alpha_i$ must be zero. Thanks in advance!

答:
Here is one way to express it using summations as I mentioned in comments.

$v_1 = \frac{\pi}{3} (r_1^2 + r_1 r_2 + r_2^2) h_1$

Now, $r_1 = r_2 - x$, where $x = h_1 \tan \alpha$

Then we have,

$r_1^2 + r_1 r_2 + r_2^2 = (r_2-x)^2 + r_2(r_2-x)+r_2^2 = 3r_2^2 + x^2 - 3r_2x$

So we can express the volume $V$ as -

$\displaystyle \frac{\pi}{3} \bigg[\sum_{i=1}^n 3 h_i \big(R + \sum_{j=1}^i h_j \tan \alpha_j\big)^2 + h^3_i \tan^2 \alpha_i - 3 h^2_i \tan \alpha_i\big(R + \sum_{j=1}^i h_j \tan \alpha_j \big)\bigg]$


问:
Evaluate the following integral $ \int_1^{\infty} \frac{\lbrace x\rbrace-\frac{1}2}{x} dx$
$$\int_1^{\infty} \frac{\lbrace x\rbrace-\frac{1}2}{x} dx$$
Here $\lbrace\cdot\rbrace$ denotes the fractional part.

I found this challenging integral, and I'm curious about the solution, so I decided to do some efforts to solve it, but sadly I didn't, any hints?

Attempts:

\begin{align}
\int_1^{\infty} \frac{\lbrace x\rbrace-\frac{1}2}{x} dx&=\int_1^{\infty} \frac{1\lbrace x\rbrace-1}{2x} dx\\
&=\int_1^{\infty}\frac{\lbrace x\rbrace}{x}-\frac{1}{2x}dx\\
&=\int_1^\infty \frac{x-\lfloor x\rfloor-1}{x}-\frac{1}{2x}dx\\
&=\int_1^\infty \frac{x-\lfloor x\rfloor-1}{x} dx -\int_1^\infty \frac{dx}{2x}
\end{align}
I thought about this property:
$$\int_0^\infty \varphi (x) dx=\lim_{a\to \infty} \int_0^a \varphi(x) dx$$
So I applied it only for the second fraction because its antiderivative was easy enough, and here's what I've got:
\begin{align}
\int_1^\infty \frac{dx}{2x}&=\lim_{a\to \infty} \int_1^a \frac{dx}{2x}\\
&=\lim_{a\to \infty}\frac{\ln (x)}{2}\bigg\vert_0^a\\
&=\lim_{a\to \infty}\frac{\ln (a)}2 -\frac{\ln (0)}{2}
\end{align}
And here I felt that I'm wrong I can't get $\infty -\infty$, So any thoughts or hints, I'll be thankfull!

答:
Euler-Maclaurin formula applied to $\log N!$ gives

$$
\begin{aligned}
\log N!
&=\int_1^N\log x\mathrm dx+{\log N\over2}+\int_1^N{\overline B_1(x)\over x}\mathrm dx \\
&=\left(N+\frac12\right)\log N-N+1+\int_1^N{\overline B_1(x)\over x}\mathrm dx
\end{aligned}
$$

However, according to Stirling's approximation, we have

$$
\log N!=\left(N+\frac12\right)\log N-N+\frac12\log2\pi+\mathcal O\left(\frac1N\right)
$$

Consequently as $N\to\infty$ we get

$$
\int_1^\infty{\overline B_1(x)\over x}\mathrm dx=\int_1^\infty{\{x\}-1/2\over x}\mathrm dx=-1+\frac12\log2\pi
$$


问:
Construction of three types of unions
Let $X$ be a topological space. Let $A$ and $B$ two subsets of $X$ endowed with the subspace topology and
let
$$Y=A\cup_sB$$ where $\cup_s$ designate the union of $A$ and $B$ as sets.
and $$Y'=A'\cup_sB'$$ where  $A'=A\times \{0\}$ and $B'=B\times\{1\}$.
Consider the inclusions $$i_A:A\longrightarrow A \cup_s B$$  $$i_B:B\longrightarrow  A \cup_s B$$

Now according to theses articles : https://en.wikipedia.org/wiki/Disjoint_union_(topology)
[https://en.wikipedia.org/wiki/Coherent_topology

We can give $Y$ the subspace topology from $X$: a set $O$ is open in $Y$ if $O=Y\cap U$ where $U$ is any open subset of $X$. we will denote $Y_s$ the set $Y$ endowed with this subspace topology.

We can give $Y$ the coherent topology: a set $O$ is open in $Y$ if $i_A^{-1}(O)\cap A$ is open in $A$ and $ i_B^{-1}(O)\cap B$ is open in $B$. We will denote $Y_c$ the set $Y$ endowed with this coherent topology.

We can give $Y'$ the disjoint union topology: a set $O'$ is open in $Y'$ if $O'\cap A'$ is open in $A'$ and $ O'\cap B'$ is open in $B'$.

The point is that when $A$ and $B$ are disjoint as sets then $Y_c$ and $Y'$ are different as sets but they  will be homeomorphic as topological spaces, in particular $Y_c$ and $Y'$ will be both disconnected.

But if the sets $A$ and $B$ are not disjoint as sets, then $Y_c$ and $Y'$ are different as sets and are also topologically different, for example $Y'$ is always disconnected as a set union of two disjoint and open subsets $A'$ and $B'$ while $Y_c$ need not be disconnected as $A$ and $B$ are not disjoint.

Is my reasoning correct? thank you for your help!

答:
$Y_s$ also has a nice characterisation as the minimal topology that makes $i_A$ and $i_B$ continuous. We don’t really need these maps to describe the coherent topology $Y_c$: we can just say $$O \subseteq Y_c \text{ is open } \iff O \cap A \text{ is open in } A \text{ and } O \cap B \text{ is open in } B$$ and this makes it the largest topology that makes $i_A$ and $i_B$ continuous. So these topologies are the extremes of the topologies we can put on the set $A \cup B$. To describe the topology on $Y’$ we need to define injections $j_A: A \to A’$ by $j_A(a)=(a,0)$ and $j_B: B \to B’$ by $j_B(b)=(b,1)$ and the topology on $Y’$ is then again the largest one that makes $j_A,j_B$ continuous. This makes the analogy between $Y_s$ and $Y’$ more clear I think.

If $A$ and $B$ are disjoint to start with, it’s clear that $Y_c \simeq Y’$, but the coherent topology is most often applied when the union we take is not disjoint (and often infinite). If $A,B$ are both closed and $A \cup B = X$, the coherent topology on $X$ is just $X$ itself and $X’$ (as a disjoint union) is non-connected so it’s quite easy to create non-homeomorphic examples for $X$ connected when $A,B$ are necessarily overlapping.

So your reasoning is mostly correct but can be slightly refined.

Title: Construction of three types of unions


问:
Locally injective graph homomorphism into a tree
$\DeclareMathOperator{\star}{\mathcal{star}}$

Let $X$ be a connected graph, $T$ be a tree and $\phi: X \rightarrow T$ be a locally injective graph homomorphism. Prove that $\phi$ is injective!

Here, a graph means a pair of sets $X = (X^0,X^1)$ with three maps:

$\alpha: X^1 \rightarrow X^0$

$\omega: X^1 \rightarrow X^0$

$^\bar{}: X^1 \rightarrow X^1$

such that for any $e \in X^1$ the following holds

$\overline{\overline{e}} = e \neq \overline{e}$

$\alpha(e) = \omega(\overline{e})$

A graph homomorphism $\phi:X \rightarrow Y$ is a map from $X^0 \cup X^1$ to $Y^0 \cup Y^1$ such that

$\forall v \in X^0 \ \phi(v) \in Y^0$

$\forall e \in X^1 \ \phi(e) \in Y^1$

$\forall e \in X^1 \ \phi(\alpha(e)) = \alpha(\phi(e))$

$\forall e \in X^1 \ \phi(\omega(e)) = \omega(\phi(e))$

$\forall e \in X^1 \ \phi(\overline{e}) = \overline{\phi(e)}$

A graph homomorphism $\phi: X \rightarrow Y$ is locally injective if $\phi \restriction \star (x)$ is injetive $\forall x \in X^0$, where $\star(x) := \{e \in X^1 \ | \ \alpha(e) = x \}$.

A path between two vertices $v,\tilde{v} \in X^0$ is a sequence of edges $(e_1,e_2, \ldots, e_n) \in (X^1)^n$ such that

$\alpha(e_1) = v$, $\omega(e_n) = \tilde{v}$

$\forall 1 \le i < n \ \omega(e_i) = \alpha(e_{i+1})$

A graph $X$ is connected if for any pair of vertices $(v,\tilde{v}) \in (X^0)^2$ there is a path from $v$ to $\tilde{v}$.

I've tried to prove it via induction,but somehow seem to miss the property leading to my desired contradiction if I assume, $\phi$ was not injective. What goes wrong if I look at a path from $v$ to $\tilde{v}$ with $\phi(v) = \phi(\tilde{v})$ where either $v \neq \tilde{v}$ or the related edges are not equal?

答:
$\DeclareMathOperator{\star}{\mathcal{star}}$
Ok, I got it. Let $v,\tilde{v} \in X^0$ with $\phi(v) = \phi(\tilde{v})$ and $(e_1,e_2, \ldots, e_n)$ be a reduced ($\forall i \ \overline{e_i} \neq e_{i+1}$) path from $v$ to $\tilde{v}$.

If $n = 0$, we have $v = \tilde{v}$ $\checkmark$

If $n = 1$, we have

$\begin{eqnarray}\phi(\alpha (e_1)) &=& \alpha(\phi(e_1)) \\ &=& \alpha ( \phi \restriction_{\star(v)} (e_1)) \\ &=& \phi \restriction_{\star(v)} (\alpha(e_1))\\ &=& \phi(\omega(e_1)) \\ &=& \phi(\alpha(\overline{e_1}) \\ &=& \alpha(\phi(\overline{e_1})) \\ &=& \alpha ( \overline{\phi(e_1)}) \\ &=& \alpha( \overline{ \phi \restriction_{\star(v)}  (e_1)}) \\ &=& \alpha (\phi \restriction _{\star(v)} (\overline{e_1})) \\ &=&\phi \restriction_{\star(v)} (\alpha(\overline{e_1}))  \\ &=& \phi \restriction_{\star(v)} (\omega(e_1))\end{eqnarray}$

  and hence (by the injectivity of $\phi \restriction{\star(v)}$): $v = \alpha(e_1) = \omega(e_1) = \tilde{v}$.

If $n > 1$, we get a path $(\phi(e_1), \phi(e_2), \ldots, \phi(e_n))$ from $\phi(v)$ to $\phi(\tilde{v})$ which (by our assumption $\phi(v) = \phi(\tilde{v})$) is a cycle and hence cannot be reduced. Fix $i \in \{1,\ldots,n-1\}$ with $\overline{\phi(e_i)} = \phi(e_{i+1})$. It is

$\begin{eqnarray} \overline{\phi(e_i)} &=&\ \phi(\overline{e_i}) \\ &=& \phi \restriction_{\star({\alpha(e_{i+1})})}(\overline{e_i}) \\ &=& \phi \restriction_{\star({\alpha(e_{i+1})})}(e_{i+1}) \\ &=& \phi(e_{i+1})\end{eqnarray}$

  and thus (by injectivity of $\phi \restriction _{\star(\alpha(e_{i+1}))}$): $\overline{e_i} = e_{i+1}$, which contradicts our assumption that $(e_1, \ldots, e_n)$ is reduced.

Therefore $\phi$ must be injective on the set of vertices.

Now fix $e,\tilde{e} \in X^1$ with $\phi(e) = \phi(\tilde{e})$. Then $\alpha (\phi(e)) = \phi(\alpha(e)) = \phi(\alpha( \tilde{e})) = \alpha ( \phi(\tilde{e}))$ which witnesses (by injectivity of $\phi$ on the set of vertices): $\alpha(e) = \alpha(\tilde{e})$, which implies $e, \tilde{e} \in \star(\alpha(e))$. Thus $\phi(e) = \phi \restriction _{\star(\alpha(e))} (e) = \phi \restriction _{\star(\alpha(e))} (\tilde{e}) = \phi(\tilde{e})$, which gives $e = \tilde{e}$ by injectivity of $\phi \restriction _{\star(\alpha(e))}$.


问:
Finding example function from nonlinear differential equation
I would like to find a twice continuously differentiable function $f(x_1,x_2): \mathbb{R}^2 \rightarrow \mathbb{R}$. Denote $f_1, f_2, f_{11}, f_{12}, f_{22}$ its first and second order partial derivatives with respect to $x_1, x_2,\dots$. $f$  needs to fulfill the following equation
\begin{equation}
1 - \exp(f) = \frac{f_1}{f_2}a
\end{equation}

where $a$ is a given constant. There are no further constrains on the function. I tried to exploit the fact that $f_{12} = f_{21}$. Differentiating the equation above on both sides separately with respect to $x_1$ and $x_2$ and dividing yields:

\begin{align}
2f_{12} = f_{11}\frac{f_2}{f_1} + f_{22}\frac{f_1}{f_2}
\end{align}

But I do not know how to proceed from here. Thank you for any help and suggestions.

答:
As @A rural reader suggested, substituting $f=\ln(1+g)$ yields the inviscid Burgers' equation:
$$ -g = \frac{g_1}{g_2} a \Leftrightarrow a g_1 + g~ g_2 = 0. $$
Solutions to this equation have to be classified through an initial condition, e.g. $g(0,x) = F(x)$ which has the implicit solution:
$$ g(x_1,x_2) = F\left(x_2-\frac{x_1}{a}\cdot g \right) \Rightarrow g(x_1,x_2) = \cdots \Rightarrow f(x_1,x_2) = \ln(1+g). $$

A typical example for this would be $F(x) = x$, which leads to
$$ g(x_1,x_2) =  \frac{ax_2 }{a+ x_1 } \Rightarrow f(x_1,x_2) = \ln\left( 1 +  \frac{ax_2 }{a+ x_1 } \right). $$


问:
Logarithmic inequation
Good morning, I was studying a function but I got stuck during the study of the signs (by calculating $f(x)\ge0$)

My function is: $f(x)=\log_3 (x^2-9)-\log_{\frac{1}{3}}(x^2-4x+3)$

So it went $\log_3 (x^2-9)-\log_{\frac{1}{3}}(x^2-4x+3)\ge0$

At this point I tried many ways (also to use the same base, and getting $\log_3 (x^2-9)+\log_{3}(x^2-4x+3)\ge0$) but I still can't find any way to resolve it without using the graph.

I thank anyone who is willing to help me.

答:
hint

$ x $ should satisfy

$$x^2-9>0$$
or
$$x\in(-\infty,-3)\cup(3,+\infty)$$
and
$$x^2-4x+3=(x-1)(x-3)>0$$
or
$$x\in(-\infty,1)\cup(3,+\infty)$$

Observe that
$$\log_{\frac 13}(a)=-\log_3(a)$$

So, the inequation becomes
$$\ln\Bigl((x-3)^2(x+3)(x-1)\Bigr)\ge 0$$
where
$$x\in(-\infty,-3)\cup (3,+\infty)$$

Title: Logarithmic inequation


问:
Forgetful functor from Magma to Set
I'm trying to do an exercise on adjoints, where one of the questions asks to prove that the forgetful functor $U: \mathsf{Magma} \rightarrow  \mathsf{Set}$ has a left adjoint.

Is there a way of proving this, assuming that both Magma and Set are categories?

答: Magmas are algebraic structures, and, as such, enjoy the existence of free objects. Do you see why this implies the existence of a particular left adjoint?

Title: Forgetful functor from Magma to Set


答:
Yes. In general, for any algebraic theory $\mathcal A$ (that is magmas, monoids, groups, etc.. ) their is an adjunction
$$U:\mathcal A \to \mathcal Set$$
$$F:\mathcal Set\to\mathcal A$$
with right adjoint given by a forgetful functor $U$ and left adjoint given by the free algebra functor $F$. Formally, a free algebra on a set $X$ is defined by the left adjoint as $F(X)$. But intuitively, a free algebra on a set $X$ is smallest algebra containing $X$ which is "freely" generated by the terms of the algebra.

So to get the left adjoint for the theory of magmas, you need to ask yourself what is a free magma generated by a set.

Hint:

 A free monoid on a set $X$ is the monoid of words with alphabet $X$. If you remove associativity and the identity, you get trees with $X$-labelled leaves. For example, if $X=\{a,b,c\}$, then the underlying set of the free magma on $X$ is given the set of terms $$U_{\text{Magma}}(F_{\text{Magma}}(X))=\{a,b,c,\mu(a,c),\mu(a,\mu(\mu(a,b),c)),\ldots etc.\}$$

Title: Forgetful functor from Magma to Set

Body:
I'm trying to do an exercise on adjoints, where one of the questions asks to prove that the forgetful functor $U: \mathsf{Magma} \rightarrow  \mathsf{Set}$ has a left adjoint.

Is there a way of proving this, assuming that both Magma and Set are categories?


问:
Square Matrices Problem
Let A,B,C,D & E be five real square matrices of the same order such that ABCDE=I where I is the unit matrix . Then,

(a)$B^{-1}A^{-1}=EDC$

(b)$BA$ is a nonsingular matrix

(c)$ABC$ commutes with $DE  $

(d)$ABCD=\frac{1}{det(E)}AdjE$

More than one option may be correct .

Also , taking the special case A=B=C=D=E=I states all these options be true , but answer key states (a) is incorrect, how ?

答:
First, a special case can only show you, that an answer is wrong, but not that is true in general. Regarding the options:

(a) We have
$$ 1 = ABCDE \iff A^{-1} = BCDE \iff B^{-1}A^{-1} = CDE $$
so choosing $C$, $D$, $E$ such that $CDE \ne EDC$ will give you an example for (a) being wrong.

(b) If $BA$ were singular, then
$$ 1 = \det(ABCDE) = \det(AB)\det(CDE) = \det(BA)\det(CDE) = 0. $$

(c) We have
$$ ABCDE = 1 \iff (ABC)^{-1} = DE $$
and every matrix commutes with its inverse.

(d) We have $E^{-1} = ABCD$ and $E^{-1} = \frac 1{\det E} \mathrm{adj}\, E$.

Title: Square Matrices Problem


问:
Let $R$ be a commutative ring, $I$ and ideal of $R$. How can I prove that $(I^e)^c=\{a\in R\mid (\exists s\in S)\,sa\in I\}$?
Let $R$ be a commutative ring, $I$ and ideal of $R$ and $S$ a multiplicative subset of $R$. Consider the natural morphism $\ell:R\to S^{-1}R$. Here the extension $I^e$ of an ideal $I$ of $R$ is defined in two ways:

$I^e:=S^{-1}I$ and

$I^e:=\langle \ell(I)\rangle\in S^{-1}R$.

The contraction $J^c$ of an ideal $J\subseteq S^{-1}R$ is just the preimage by $\ell$.

With all this is mind, how can I prove that $(I^e)^c=\{a\in R\mid (\exists s\in S)\,sa\in I\}$?

I already proved $\supseteq$ (just notice that $\frac{sa}{s}=\frac{a}{1}\in S^{-1}I$) but I can't prove $\subseteq$. This comes form Exercise V.4.9 from Algebra: Chapter 0.

答:
$$x\in (I^e)^c\implies \;\exists\;\frac is\in S^{-1}I\;\;s.t.\;\;\ell^{-1}\left(\frac is\right)=x\iff \ell x:=\frac x{s'}=\frac is\iff sx=is'\in I\implies$$

and we're done. If we assume $\;1\in S\;$ we can take $\;s'=1\;$ in the above and it is slightly simpler.


问:
Verifying that $\mathbb Q=\bigcup_{n\ge 1} H_n$
Let $G=(\mathbb Q,+)$ and $r_1=p_1/q_1, r_2=p_2/q_2\in G$. I want to prove that:

$\langle r_1,r_2\rangle\subseteq \langle\frac{1}{q_1q_2}\rangle$

If $r_1,r_2,...,r_n\in G$ then $\langle r_1,r_2,...,r_n\rangle$ is cyclic.

If $H_n=\langle \frac{1}{n!}\rangle$ then every $H_n$ is cyclic, $$H_1\subset H_2\subset H_3\subset...$$ and $\mathbb Q=\bigcup_{n\ge 1} H_n$.

I can see that $r_1\in\langle\frac{1}{q_1q_2}\rangle$ and the same is true for $r_2$. This ends proving $1.$ I guess I should use the first part to see the second part clearly. So, I think I should have $r_i\in \langle\frac{1}{q_1q_2q_3...q_n}\rangle$. Is my guess right because it makes the second proved? For the third part it is obvious that every $H_n$ is cyclic. Assuming that chain of inclusions is correct and that $\bigcup_{n\ge 1} H_n\subseteq\mathbb Q$, just make me an small finial hint. Please verify my way of solution. I will be thankful if you have any other point of views. Thanks

答:
You need to work a bit harder to prove (2). Suppose that $r_1=\frac6{11}$ and $r_2=\frac{10}{13}$; then $\langle r_1,r_2\rangle$ is $\left\langle\frac2{143}\right\rangle$, not $\left\langle\frac1{143}\right\rangle$, though it’s still cyclic. Note that everything in $\langle r_1,r_2\rangle$ has the form

$$\frac{mp_1+np_2}{q_1q_2}\;;$$

what do you know about $\{mp_1+np_2:m,n\in\Bbb Z\}$ that gives you a generator for this group?

Once you’ve done that, you can use induction to extend from $\langle r_1,r_2\rangle$ to $\langle r_1,\dots,r_k\rangle$; the induction step will just use part (2).

Showing that every rational number $\frac{p}q$ is in some $H_n$ is easy: think about the relative sizes of $n$ and $q$.


问:
if two computers are playing tic-tac-toe, but they are choosing their squares randomly, what is the chance for X to win?
Tic-tac-toe is a children's board game that's notorious for draws. It's easy to write a program for either player (X or O) that always draws the game. I would like to know how the outlook changes if both players play completely randomly. Ie, X places their first move uniformly among the 9 squares, then O does the same, and so on until someone wins. Intuitively, X should be better because they'll usually get more squares and first player advantage, but I'm not sure.

I really have no Idea, but I would really like to know. I am good at math, but not that good.

答:
Well that was an enjoyable time-waster! I wrote a little program to play and, assuming 'X' is the player who goes first, the answer seems to be about 59%:

Draw / Win / Lose = 63384 / 292379 / 144237 out of 500000 equals 13% / 58% / 29%

Draw / Win / Lose = 63221 / 292618 / 144161 out of 500000 equals 13% / 59% / 29%

Draw / Win / Lose = 63383 / 292474 / 144143 out of 500000 equals 13% / 58% / 29%
Draw / Win / Lose = 63224 / 292577 / 144199 out of 500000 equals 13% / 59% / 29%

Like others, I can't see an easy way to do this analytically.


问:
Direct Determinant of Block Matrix
Prove $|C+\overrightarrow{Y}\overrightarrow{Y}'|=(1+\overrightarrow{Y}'C^{-1}\overrightarrow{Y})|C|$ where $Y$ is a $p \times 1$ vector and $C$ is a non-singular $p \times p$ matrix. See Exercise $4.11$ in $JW$.

$\mathbf{Proof}$

Define the block matrix

$$\mathbf{A}=\begin{pmatrix} C & -\overrightarrow{Y} \\ \overrightarrow{Y}^{'} & 1 \end{pmatrix}$$

Problem 4.11 in JW asserts that for any square block matrix $\mathbf{B}$:

$$|\mathbf{B}|=|\mathbf{B}_{11}||\mathbf{B}_{22}-\mathbf{B}_{21}\mathbf{B}_{11}^{-1}\mathbf{B}_{12}|$$

Using the result of $4.11$ we have that:

$$|\mathbf{A}|=|C||1-\overrightarrow{Y}^{'}C^{-1}\overrightarrow{Y}|=|C|(1-\overrightarrow{Y}^{'}C^{-1}\overrightarrow{Y})$$

I understand that for any block matrix $\mathbf{B}=\begin{pmatrix} A & B \\ C & D \end{pmatrix}$ it is not always the case that $|\mathbf{B}|$=AD-BC. Knowing this, I am confused on how I can evaluate the determinant of $\mathbf{A}$ without making use of the result of 4.11 so that $|\mathbf{A}|=|C+\overrightarrow{Y}\overrightarrow{Y}'|$ as desired.

答:
You can factorise the underlying matrix as
$$
\pmatrix{C & 0\\0 &1}
\pmatrix{I & 0\\y^{T}&1}
\pmatrix{I & -C^{-1}y\\0^{T} & y^{T}C^{-1}y+1}
$$
and then all is clear.

Title: Direct Determinant of Block Matrix


问:
An apparent dichotomy in the calculation of a limit with indeterminacy $ 0^0 $
$$L=\lim_{x \to 0}(x+2x^2+3x^3+4x^4+5x^5)^\frac{1}{\log(4x+3x^2+2x^3+x^4)}$$

答:
$$\lim_{x \to 0}(x+2x^2+3x^3+4x^4+5x^5)^\frac{1}{\log(4x+3x^2+2x^3+x^4)}=\lim_{x \to 0}e^{\log{\Big[(x+2x^2+3x^3+4x^4+5x^5)^\frac{1}{\log(4x+3x^2+2x^3+x^4)}}\Big]}=\lim_{x \to 0}e^{\frac{\log{(x+2x^2+3x^3+4x^4+5x^5)}}{\log(4x+3x^2+2x^3+x^4)}}=\lim_{x \to 0}e^{\frac{\log{[x(1+2x+3x^2+4x^3+5x^4)]}}{\log[x(4+3x+2x^2+x^3)]}}=\lim_{x \to 0}e^{\frac{\log{[x]}}{\log[4x]}}=e$$.
The last equality can be obtained thinking about the Hospital rule for which we have $$\lim_{x\to 0}\frac{\log{x}}{\log{4x}}=\frac{\frac{1}{x}}{\frac{1}{x}}=1$$.

$\textbf{For your mistake remember:}$
if you are dealing with the limit of $x$ goes to $0$, consider the "slower" terms (therefore of a lower degree) that you can find in the numerator and denominator and "leave out" the others}, in effect this is exaclty what you obtain selecting $x$ both at numerator and denominator in the last but one passage.


问:
Why does this pattern work: $1 \cdot{1} = 1, 11 \cdot{11} = 121, 111 \cdot{111} = 12321\ldots$
I have recently learned about pattern that goes like this:

$$\begin{align}
1^2 &= 1\\
11^2 &= 121\\
111^2 &= 12,321\\
1,111^2 &= 1,234,321\\
11,111^2 &= 123,454,321.
\end{align}$$

It is a very cool pattern, but after a bit it stops:

$$1,111,111,111^2 = 1,234,567,900,987,654,321$$

My main question:

Why does this pattern work?

A side question that's less important:

Is there an algebraic equation to describe this pattern?

答: well, for 1^2 it isn't very hard to figure out, but here is the basic explanation. there is one of 11, 111, 1111, etc. in each place value until there have been as many place values as there are digits of the original number (1,111; 11,110; 111,100; and 1,111,000 for example). the amount of digits in the product is equal to (nx2)-1, where n is the original number. then, it is like a bell curve, with the numbers determined by how many ones were in that place value. it then breaks because there is no single digit bigger than 9, and thus it moves to the next place, and ruins the symmetry.


问:
Dividing an equilateral triangle into N equal (possibly non-connected) parts
It’s easy to divide an equilateral triangle into $n^2$, $2n^2$, $3n^2$ or $6n^2$ equal triangles.

But can you divide an equilateral triangle into 5 congruent parts? Recently M. Patrakeev found an awesome way to do it — see the picture below (note that the parts are non-connected — but indeed are congruent, not merely having the same area). So an equilateral triangle can also be divided into $5n^2$ and $10n^2$ congruent parts.

Question. Are there any other ways to divide an equilateral triangle into congruent parts? (For example, can it be divided into 7 congruent parts?) Or in the opposite direction: can you prove that an equilateral triangle can’t be divided into $N$ congruent parts for some $N$?

(Naturally, I’ve tried to find something in the spirit of the example above for some time — but to no avail. Maybe someone can find an example using computer search?..)

I’d prefer to use finite unions of polygons as ‘parts’ and different parts are allowed to have common boundary points. But if you have an example with more general ‘parts’ — that also would be interesting.

答:
In this MathOverflow thread, there are dissections with $5n^2$ pieces for all $n\ge 6$ where the pieces are simply connected quadrilaterals. The smallest such is pictured here:

In the thread, it is mentioned that Michael Reid claims to have found a simply-connected dissection using $7n^2$ trapezoids for some $n$, but the result appears not to be published anywhere.

In the case where the tiles are triangles, the 1995 paper Tilings of Triangles by M. Laczkovich has many important results. In particular, it states that there is a dissection of an equilateral triangle into $2469600=2^5\cdot3^2\cdot5^2\cdot 7^3$ triangles with side lengths $7, 8,$ and $13$.

In general, Theorem 3.3 in the paper states

Let $x$ and $y$ be non-zero integers such that $x+2y\neq 0\neq y+2x$. Then there is  a positive integer $k$ such that the equilateral triangle can be dissected into $n=|xy(x+2y)(y+2x)k^2|$ congruent triangles.

This yields dissections with a number of triangles whose squarefree part is any of $ 5, 6, 10, 13, 14, 15, 21, 30, 35, 39, 55, 65, 66, 70, 85, 95, 105, 119, 130,\ldots$


答:
We can find the exact answer by recursion. In all final states of the board, the probability is either $0$ or $1$. In every other state $S$, the probability is the average of the probabilities you get in states obtained by a single move from $S$. There are fewer than $3^9 = 19683$ board states, so a computer has no trouble with this.

Here is some Mathematica code implementing this (the board is a list of length $9$; I represent empty squares by 0, X's by 1, and O's by -1). I represent the final answer by a triple $(\Pr[\text{X wins}], \Pr[\text{O wins}], \Pr[\text{tie}])$.

```<code>(* lines[board] adds up the values along each winning line *)
lines[board_] :=
  Total /@ {board[[{1, 2, 3}]], board[[{4, 5, 6}]], board[[{7, 8, 9}]],
    board[[{1, 4, 7}]], board[[{2, 5, 8}]], board[[{3, 6, 9}]],
    board[[{1, 5, 9}]], board[[{3, 5, 7}]]};

pwin[board_] := pwin[board] =
  Which[Max[lines[board]] == 3, {1,0,0}, (* player 1 has won *)
   Min[lines[board]] == -3, {0,1,0}, (* player -1 has won *)
   FreeQ[board, 0], {0,0,1}, (* no more moves left: draw *)
   Total[board] == 0, (* player 1's turn *)
   Mean[pwin /@ ReplaceList[board, {x___, 0, y___} :> {x, 1, y}]],
   True, (* player -1's turn *)
   Mean[pwin /@ ReplaceList[board, {x___, 0, y___} :> {x, -1, y}]]]

pwin[{0,0,0,0,0,0,0,0,0}] (* outputs {737/1260, 121/420, 8/63} *)
</code>```

It says that from an empty board, the probability of the first player winning is $\frac{737}{1260} \approx 0.5849$. Similar code says that the probability of a tie is $\frac{8}{63} \approx 0.127$ and the probability of the second player winning is $\frac{121}{420} \approx 0.2881$.

Another interesting result we can get in the same way: what if one player plays randomly, but the other player plays to maximize their chances of winning? (And when choosing between a draw and a loss, to avoid losing.) To find this, just replace one of the Means in the code above by a more intelligent choice of move.

If the first player plays to win, they win with probability $\frac{191}{192}$ and tie with probability $\frac1{192}$.

If the second player plays to win, they win with probability $\frac{887}{945}$, tie with probability $\frac{43}{945}$, and lose with probability $\frac1{63}$. (Why do they lose with any probability, when there's a strategy that guarantees a tie? Because if you're playing against a random opponent, sometimes taking a risk of losing gives you a higher chance of winning.)

Title: if two computers are playing tic-tac-toe, but they are choosing their squares randomly, what is the chance for X to win?

Body:
Tic-tac-toe is a children's board game that's notorious for draws. It's easy to write a program for either player (X or O) that always draws the game. I would like to know how the outlook changes if both players play completely randomly. Ie, X places their first move uniformly among the 9 squares, then O does the same, and so on until someone wins. Intuitively, X should be better because they'll usually get more squares and first player advantage, but I'm not sure.

I really have no Idea, but I would really like to know. I am good at math, but not that good.

Body:
We can find the exact answer by recursion. In all final states of the board, the probability is either $0$ or $1$. In every other state $S$, the probability is the average of the probabilities you get in states obtained by a single move from $S$. There are fewer than $3^9 = 19683$ board states, so a computer has no trouble with this.

Here is some Mathematica code implementing this (the board is a list of length $9$; I represent empty squares by 0, X's by 1, and O's by -1). I represent the final answer by a triple $(\Pr[\text{X wins}], \Pr[\text{O wins}], \Pr[\text{tie}])$.

(* lines[board] adds up the values along each winning line *)
lines[board_] :=
  Total /@ {board[[{1, 2, 3}]], board[[{4, 5, 6}]], board[[{7, 8, 9}]],
    board[[{1, 4, 7}]], board[[{2, 5, 8}]], board[[{3, 6, 9}]],
    board[[{1, 5, 9}]], board[[{3, 5, 7}]]};

pwin[board_] := pwin[board] =
  Which[Max[lines[board]] == 3, {1,0,0}, (* player 1 has won *)
   Min[lines[board]] == -3, {0,1,0}, (* player -1 has won *)
   FreeQ[board, 0], {0,0,1}, (* no more moves left: draw *)
   Total[board] == 0, (* player 1's turn *)
   Mean[pwin /@ ReplaceList[board, {x___, 0, y___} :> {x, 1, y}]],
   True, (* player -1's turn *)
   Mean[pwin /@ ReplaceList[board, {x___, 0, y___} :> {x, -1, y}]]]

pwin[{0,0,0,0,0,0,0,0,0}] (* outputs {737/1260, 121/420, 8/63} *)

It says that from an empty board, the probability of the first player winning is $\frac{737}{1260} \approx 0.5849$. Similar code says that the probability of a tie is $\frac{8}{63} \approx 0.127$ and the probability of the second player winning is $\frac{121}{420} \approx 0.2881$.

Another interesting result we can get in the same way: what if one player plays randomly, but the other player plays to maximize their chances of winning? (And when choosing between a draw and a loss, to avoid losing.) To find this, just replace one of the Means in the code above by a more intelligent choice of move.

If the first player plays to win, they win with probability $\frac{191}{192}$ and tie with probability $\frac1{192}$.

If the second player plays to win, they win with probability $\frac{887}{945}$, tie with probability $\frac{43}{945}$, and lose with probability $\frac1{63}$. (Why do they lose with any probability, when there's a strategy that guarantees a tie? Because if you're playing against a random opponent, sometimes taking a risk of losing gives you a higher chance of winning.)


问:
Expected time in half-line for random walk
For a one-dimensional random walk (starting at $0$) for which we move $1$ unit to the right with probability $p$ and $1$ unit to the left with probability $q=1-p>p$, what is the expected time spent in the interval $(0,\infty)$ (equivalently, $[1,\infty)$)?

It is not too hard to come up with an expression for this involving infinite sums and binomial coefficients, but there does not seem to be a straightforward way to put it in closed form. Alternatively, I'm looking for some sort of (asymptotic) estimate if possible.

答:
There are several combinatorial shortcuts which make the calculation not too difficult, and it is worth knowing that $\frac{x}{1-x}=x(1-x)+2x^2(1-x)+3x^3(1-x)+\cdots$ for $|x|<1$

Assuming $0 < p < \frac12$, the probability of moving right initially and then returning to $0$ is $p$.  By symmetry, the probability of moving left initially and then returning to $0$ is also $p$, so the probability of moving left initially but never returning to $0$ is $1-2p$.

So the expected number of returns to $0$ is $$1\times 2p(1-2p) + 2\times (2p)^2(1-2p)+3\times (2p)^3(1-2p)+ \cdots = \frac{2p}{1-2p}$$ and half of these are expected to start by moving right into positive territory, so $\dfrac{p}{1-2p}$.

Suppose the conditional expected time positive on a trip which starts at $0$, moves right, and then returns to $0$ is $T$.  Then the first step takes you to $+1$ and then

with probability $1-p$ you return immediately to $0$ having spent time $1$ positive,

with probability $p(1-p)$ you take a trip to the left of expected time $T+1$ returning to $+1$ and then immediately to $0$ having spent and expected time $T+2$ positive,

with probability $p^2(1-p)$ you take two trips to the left each of expected time $T+1$ returning to $+1$ and then immediately to $0$ having spent and expected time $2T+3$ positive,

and so on.  This means  $$T= 1\times (1-p) + (T+2)\times p(1-p)+(2T+3)\times p^2(1-p)  + \cdots \\= 1+ (T+1)\frac{p}{1-p}$$

which gives $T=\dfrac{1}{1-2p}$.

Multiplying by the overall expected number of trips into positive territory then gives the overall expected time in positive territory of $$\frac{p}{(1-2p)^2}.$$

For $p=0.4$ this would give an expected time in positive territory of $10$, though with a widely dispersed distribution of possible values.  To check, here is a simulation in R:

```<code>above0 <- function(p, top){
  steps <- sample(c(+1,-1), ceiling(top/(1-2*p)), replace=TRUE, prob=c(p,1-p))
  cumsteps <- cumsum(steps)
  sum(cumsteps > 0)
}

set.seed(2021)
simabove0 <- replicate(10^5, above0(0.4, 1000))
max(simabove0)
# 350
mean(simabove0)
# 10.03401
</code>```

Body:
There are several combinatorial shortcuts which make the calculation not too difficult, and it is worth knowing that $\frac{x}{1-x}=x(1-x)+2x^2(1-x)+3x^3(1-x)+\cdots$ for $|x|<1$

Assuming $0 < p < \frac12$, the probability of moving right initially and then returning to $0$ is $p$.  By symmetry, the probability of moving left initially and then returning to $0$ is also $p$, so the probability of moving left initially but never returning to $0$ is $1-2p$.

So the expected number of returns to $0$ is $$1\times 2p(1-2p) + 2\times (2p)^2(1-2p)+3\times (2p)^3(1-2p)+ \cdots = \frac{2p}{1-2p}$$ and half of these are expected to start by moving right into positive territory, so $\dfrac{p}{1-2p}$.

Suppose the conditional expected time positive on a trip which starts at $0$, moves right, and then returns to $0$ is $T$.  Then the first step takes you to $+1$ and then

with probability $1-p$ you return immediately to $0$ having spent time $1$ positive,

with probability $p(1-p)$ you take a trip to the left of expected time $T+1$ returning to $+1$ and then immediately to $0$ having spent and expected time $T+2$ positive,

with probability $p^2(1-p)$ you take two trips to the left each of expected time $T+1$ returning to $+1$ and then immediately to $0$ having spent and expected time $2T+3$ positive,

and so on.  This means  $$T= 1\times (1-p) + (T+2)\times p(1-p)+(2T+3)\times p^2(1-p)  + \cdots \\= 1+ (T+1)\frac{p}{1-p}$$

which gives $T=\dfrac{1}{1-2p}$.

Multiplying by the overall expected number of trips into positive territory then gives the overall expected time in positive territory of $$\frac{p}{(1-2p)^2}.$$

For $p=0.4$ this would give an expected time in positive territory of $10$, though with a widely dispersed distribution of possible values.  To check, here is a simulation in R:

above0 <- function(p, top){
  steps <- sample(c(+1,-1), ceiling(top/(1-2*p)), replace=TRUE, prob=c(p,1-p))
  cumsteps <- cumsum(steps)
  sum(cumsteps > 0)
}

set.seed(2021)
simabove0 <- replicate(10^5, above0(0.4, 1000))
max(simabove0)
# 350
mean(simabove0)
# 10.03401


问:
Integral identity for moment generating function
Consider the following identity for a random variable $X$ with mean $0$:

$\displaystyle \mathbb{E}[e^{tX}] = 1+ \int_0^1 (1-y)\, \mathbb{E}\left[\, (tX)^2 e^{ytX} \right] dy$

I've encountered it in the proof of theorem 3.1 of http://www.stat.cmu.edu/~arinaldo/36788/subgaussians.pdf

Can someone please help me understand why it is true?
Thank you.

答:
Since $(1-y)\, \mathbb{E}\left[\, (tX)^2 e^{ytX}\right]\ge 0$ a.s, you can use Tonelli's theorem to switch the integral with expected value:
$$
\int_0^1 (1-y)\, \mathbb{E}\left[\, (tX)^2 e^{ytX} \right] dy=\mathbb{E}\left[ \int_0^1 (1-y)\, \, (tX)^2 e^{ytX}  dy\right]
$$
Then, treat $X$ like a constant, and evaluate that integral, then the rest is easy.


问:
Get $x,y$ coord of a rectangle when rotation is $0$
I have this square div in the page. I need to get the $x,y$ coords (left/top) of the box based on rotation 0 even when the box is rotated at a different angle.
Is there a formula to calculate the the $x,y$ coords of a square with rotation angle of $0$.

Here is a demo - http://jsfiddle.net/blessenm/XrVTp/

You can see the rectangle is rotated to $22$ degree. And I get the value $'x: 208, y: 234'$.
Where $x$ is bottom left corner and $y$ is top left corner.

If the angle is at a rotation $0$. The value I get is $'x: 208, y: 234'$. This exactly what want irrespective of the rotation.

I know this question has a bit programming but I think strong math people might be able to solve it.

Btw, I get can get the following values as input.

The distance between the left most point in the rotated rect and the left of the container.

The distance between the top most point in the rotated rect and the top of the container.

The distance between the right most point in the rotated rect and the left of the container.

The distance between the bottom most point in the rotated rect and the top of the container.

Angle of rotation

答:
You can use rotation matrix
$$R(\theta) = \begin{bmatrix}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta \\
\end{bmatrix},$$
which rotates vector $\begin{bmatrix}
x \\
y \\
\end{bmatrix}$ (counterclockwise if $\theta>0,$ and clockwise if $\theta<0$) around the center of rotation $(0,\ 0)$ by angle $\theta:$
$$\begin{bmatrix}
x' \\
y' \\
\end{bmatrix} = \begin{bmatrix}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
\end{bmatrix}.$$ This is equivalent to
$$x' = x \cos \theta - y \sin \theta, \\
y' = x \sin \theta + y \cos \theta.
$$
Similarly, rotation around the point with coordinates $(x_0,\ y_0)$ is given by
$$x'-x_0 = (x-x_0) \cos \theta - (y-y_0) \sin \theta, \\
y'-y_0 = (x-x_0)  \sin \theta + (y-y_0) \cos \theta.
$$ </p>


问:
How to denote a function with finitely many functions as arguments?
Suppose one has a function $f : X \times U \to X$. Then the space of all such functions is $X^{X\times U}$.

Suppose one wants to create a function $F$ that takes a finite sequence of such a functions as its arguments and produces a unique function of the same kind. If it is assumed that the sequence of arguments is a 2-tuple, then $F$ would be binary and denoted as
$$
F : \left(X^{X\times U}\right)^2 \to X^{X\times U}.
$$

But, what if the sequence of arguments to $F$ is arbitrarily finite, how is that denoted?

答:
If you mean that $F$ takes an argument which is a finite sequence in $X^{X\times U}$ of any positive length, and $F$ returns values in $X^{X\times U}$, then it seems this would be a map

$$F:\bigcup\limits_{n=1}^{\infty} (X^{X\times U})^n\to X^{X\times U}$$

Or perhaps more clearly,

$$F:\bigcup\limits_{n=1}^{\infty} \mathscr{F}^n\to \mathscr{F}$$
where $\mathscr{F} = X^{X\times U}$.


问:
Find the functions satisfying $ \frac { f ( a b ) } { a b } = \frac { f ( a + b ) } { a + b } \cdot \frac { f ( a - b ) } { a - b } $

Find all the functions $ f : \mathbb R \to\mathbb R $ such that
$$ \frac { f ( a b ) } { a b } = \frac { f ( a + b ) } { a + b } \cdot \frac { f ( a - b ) } { a - b } \text . $$

I think $ f ( x ) = x $, but I don't know how to get it.

答:
First of all, note that you have $ f : \mathbb R \to \mathbb R $, and in particular $ 0 $ is in the domain of $ f $. But the functional equation
$$ \frac { f ( x y ) } { x y } = \frac { f ( x + y ) } { x + y } \cdot \frac { f ( x - y ) } { x - y } \tag 0 \label 0 $$
can only hold when $ x , y \ne 0 $ and $ x \ne \pm y $. That means \eqref{0} doesn't tell you anything about $ f ( 0 ) $, and given any solution $ f $ of \eqref{0}, you can change the value of $ f ( 0 ) $, and still get a solution; i.e. any function $ \tilde f : \mathbb R \to \mathbb R $ with $ \tilde f ( x ) = f ( x ) $ for all $ x \ne 0 $ is a solution. Thus the better question is to ask for all $ f : \mathbb R \setminus \{ 0 \} \to \mathbb R $ satisfying \eqref{0} for all $ x , y \in \mathbb R \setminus \{ 0 \} $ with $ x \ne \pm y $. Then, defining $ g : \mathbb R \setminus \{ 0 \} \to \mathbb R $ with $ g ( x ) = \frac { f ( x ) } x $, \eqref{0} gives
$$ g ( x y ) = g ( x + y ) g ( x - y ) \tag 1 \label 1 $$
for all nonzero $ x $ and $ y $ with $ x \ne \pm y $. Conversely, any $ g : \mathbb R \setminus \{ 0 \} \to \mathbb R $ satisfying \eqref{1} gives rise to an $ f : \mathbb R \setminus \{ 0 \} \to \mathbb R $ defined with $ f ( x ) = x g ( x ) $, which satisfies \eqref{0}. So we will try to solve this equivalent problem. It's straightforward to check that the constant functions $ g ( x ) = 0 $ and $ g ( x ) = 1 $ satisfy \eqref{1} (equivalently, the constant zero function and the identity function both satisfy \eqref{0}). We will show that these are the only solutions.

Setting $ y = 1 $ and then $ y = - 1 $ in \eqref{1} we get
$$ g ( x ) = g ( x + 1 ) g ( x - 1 ) = g ( x - 1 ) g ( x + 1 ) = g ( - x ) $$
for all nonzero $ x $ with $ x \ne \pm 1 $. Similarly, substituting $ \frac x 2 $ for $ x $ in \eqref{1} and once setting $ y = 2 $ and once $ y = - 2 $, we get
$$ g ( x ) = g \left( \frac x 2 + 2 \right) g \left( \frac x 2 - 2 \right) = g \left( \frac x 2 - 2 \right) g \left( \frac x 2 + 2 \right) = g ( - x ) $$
for all nonzero $ x $ with $ x \ne \pm 4 $. Thus we have
$$ g ( - x ) = g ( x ) \tag 2 \label 2 $$
for all nonzero $ x $.

Now, suppose there is a nonzero $ a $ with $ g ( a ) = 0 $. Without loss of generality, we can assume that $ a > 0 $, because if $ a < 0 $, by \eqref{2} we have $ g ( - a ) = 0 $ while at the same time $ - a > 0 $. Letting $ x = y + a $ in \eqref{1} we get $ g \big( y ( y + a ) \big) = 0 $ for all positive $ y $ (note that since $ a > 0 $, thus $ 0 \ne y + a \ne \pm y $). This means that we have $ g ( x ) = 0 $ for all positive $ x $, as when $ x > 0 $ there is a positive $ y $, namely $ y = \frac { - a + \sqrt { a ^ 2 + 4 x } } 2 $, such that $ y ( y + a ) = x $. Using \eqref{2}, this can be generalized for negative $ x $ as well, which means that $ g $ is the constant zero function, one of the mentioned solutions.

Finally, consider the other case where for all nonzero $ x $, $ g ( x ) $ is not equal to $ 0 $. Suppose that $ y $ is negative. Then we have $ 0 \ne \frac y { y - 1 } \ne \pm y $, and we can let $ x = \frac y { y - 1 } $ in \eqref{1}. In that case, we have $ x y = x + y = \frac { y ^ 2 } { y - 1 } $, and by the fact $ g \left( \frac { y ^ 2 } { y - 1 } \right) $ is not equal to $ 0 $, we find out that $ g ( x - y ) = g \left( \frac { y ^ 2 - 2 y } { y - 1 } \right) = 1 $. This means that we have $ g ( x ) = 1 $ for all negative $ x $, since for $ x < 0 $ there is a negative $ y $, namely $ y = \frac { x + 2 - \sqrt { x ^ 2 + 4 } } 2 $, such that $ \frac { y ^ 2 - 2 y } { y - 1 } = x $. By \eqref{2}, that is also true for positive $ x $, and $ g $ is the constant one function, the other mentioned solution.


问:
Understanding a double union of a set
I have an exercise example from Goldrei's Classical Set Theory (For Guided Independent Study) and I am having trouble understanding the axiom of union examples.

Exercise: Given a set F of ordered pairs , give a set in ZF in which all the a's and b's lie.

Solution:
A typical element  of F is a set {{a}, {a,b}}. Thus  $\cup $F   is the set of all {a}'s and {a,b}'s  for   $\in$ F, so that $\cup $($\cup $F) is the set of all a's and b's for which  $\in$ F. As F is a set, $\cup $($\cup $F) is also a set, by the union axiom.

Question:
I am quite confused about the set of $\cup $($\cup $F) and what the elements are. So if I take {{a}, {a,b}} and use the axiom of union I get $\cup $F which results to the set {a,b}. But if I do another union i.e,
$\cup $($\cup $F) wouldn't my result just be {a,b} again? I understand elementary union (that we were taught in High school)  but since I am learning intro into set theory I'm having trouble grasping the axiom of union and understanding the union of the union of a set.

答:
if I take $\{ \{ a \}, \{ a,b \} \}$ and use the axiom of union I get $\cup F$ which results to the set $\{ a,b \}$.

No; if $(a,b)=\{ \{ a \}, \{ a,b \} \} \in F$ we have that:

$\{ a \}, \{ a,b \} \in \cup F$.

The first union is needed in order to retrieve from the set $F$ of pairs the elements.

Then, we need a second "extraction" in order to retrieve $a,b$, from which $a, b \in \cup (\cup F)$.

Thus:

$\cup (\cup F) = \{ z \mid \exists w,a,b \ (w= \{ \{ a \}, \{ a,b \}\} \land w \in F \}$.

Title: Understanding a double union of a set


答:
We have $$ x\in\bigcup  Y\iff \exists y\colon x\in y\in Y$$
and
$$ x\in\bigcup \bigcup  F\iff \exists y\colon x\in y\in \bigcup F\iff \exists y,z\colon x\in y\in z\in F$$
Hence if each element of $F$ is a Kuratowski pair, then we obtain the elements of elements elements of these pairs, so indeed what we want.

Title: Understanding a double union of a set

Body:
I have an exercise example from Goldrei's Classical Set Theory (For Guided Independent Study) and I am having trouble understanding the axiom of union examples.

Exercise: Given a set F of ordered pairs , give a set in ZF in which all the a's and b's lie.

Solution:
A typical element  of F is a set {{a}, {a,b}}. Thus  $\cup $F   is the set of all {a}'s and {a,b}'s  for   $\in$ F, so that $\cup $($\cup $F) is the set of all a's and b's for which  $\in$ F. As F is a set, $\cup $($\cup $F) is also a set, by the union axiom.

Question:
I am quite confused about the set of $\cup $($\cup $F) and what the elements are. So if I take {{a}, {a,b}} and use the axiom of union I get $\cup $F which results to the set {a,b}. But if I do another union i.e,
$\cup $($\cup $F) wouldn't my result just be {a,b} again? I understand elementary union (that we were taught in High school)  but since I am learning intro into set theory I'm having trouble grasping the axiom of union and understanding the union of the union of a set.


问:
Counterexample for the sum formula in Dedekind extension
Let $A\subseteq  B$ be Dedekind domains, and $K\subseteq L$ be their quotient fields respectively, and assume that $B$ is the integral closure of $A$ in $L$. Let $\mathfrak{p}$ be a prime ideal of $A$. If $$
\mathfrak{p}B=\prod_{i=1}^r\mathfrak{P}_i^{e_i}
$$is the prime decomposition of $\mathfrak{p}B$ in $B$, in Serre's Local Fields it is proved the identity $$
\sum_{i=1}^r e_if_i=n
$$where $n=[L:K]$ and $f_i=[B/\mathfrak{P}_i:A/\mathfrak{p}]$, under the hypothesis that $L/K$ is separable. He remarks that the sum of $e_if_i$ may $<n$ without the separable hypothesis. It would be appreciated if anyone can provide an example showing the case that $$
\sum_{i=1}^re_if_i<n
$$can happen.

答:
We need that $L/K$ is a finite extension and $B$ is the integral closure of $A$ in $L$, and that $A_\mathfrak{p} B$ is a finitely generated $A_\mathfrak{p}$-module (satisfied when $L/K$ is separable, by the trace map).

The finitely generated hypothesis is needed to get that $A_\mathfrak{p} B$ is a free $A_\mathfrak{p}$-module of rank $[L:K]$ (as $A_\mathfrak{p}$ is a PID).

A counter-example to the finitely generated hypothesis is given there p.200 and 212: take $f(t)\in \Bbb{F}_p[[t]],\not \in \overline{\Bbb{F}(t)}$, we get an embedding $\Bbb{F}_p[x,y]\to \Bbb{F}_p[t,f(t)]\subset \Bbb{F}_p[[t]]$ and a discrete valuation on the former. The image of $\Bbb{F}_p[x,y^p]$ is $\Bbb{F}_p[t,f(t^p)]$. The discrete valuation $v$ extends to the fraction fields and the obtained DVR $A=\{ a\in \Bbb{F}_p(x,y^p),v(a)\ge 0\},B=\{ b\in \Bbb{F}_p(x,y),v(b)\ge 0\}$ have $t$ as an uniformizer and the same residue field $\Bbb{F}_p$. Finally $B$ is clearly integral over $A$.

If the finitely generated hypothesis is satisfied then $B/\mathfrak{p}\cong A_\mathfrak{p} B/\mathfrak{p}$ is a $[L:K]$-dimensional $A/\mathfrak{p}\cong A_\mathfrak{p}/\mathfrak{p}$ vector space.

On the other hand by comaximality and unique factorization of ideals
$$B/\mathfrak{p}= B/\prod_i\mathfrak{P}_i^{e_i}\cong \prod_i B/\mathfrak{P}_i^{e_i}$$
$B/\mathfrak{P}_i^{e_i}$ is a $e_if_i$-dimensional $A/\mathfrak{p}$ vector space.


问:
Boundedness in $L^{\infty}$ and convergence a.e. implies boundedness of the limit in $L^{\infty}$

Boundedness in $L^{\infty}$ and convergence a.e. implies boundedness of the limit in $L^{\infty}$.

Are there mistakes in my proof, and is the assertion correct? The proof feels too simple and I couldn't find the statement anywhere online.

Let $g_n:\Omega\rightarrow\mathbb{R}$ be a bounded sequence in $L^{\infty}(\Omega)$ such that $g_n\rightarrow g$ a.e. Then $g\in L^{\infty}(\Omega)$.

$\sup_{n}|g_n(x)|\leq \sup_{n}\|g_n\|_\infty\leq C$ a.e.

Since $g_n\rightarrow g$ a.e.  $\sup_{n}|g_n(x)|\geq|g(x)|$ for almost every $x$.

$\|g\|_\infty=\inf\{K>0:|g|\leq K a.e.\}\leq \inf\{K>0:\sup_n|g_n|\leq K a.e.\}\leq C$

Edit: I changed the title to the correct question, thank you for the answer!

答:
The statement in your title is false. For example, $g_n(x) = 1_{[n,n+1)}$ is a sequence of functions which is bounded in $L^\infty(\mathbb{R})$ and converges to $0$ a.e. but does not converge in $L^\infty(\mathbb{R})$ since $\|g_n - 0\|_\infty = 1$ for each $n$.

However, the statement you provide in the question (which does not say that $g_n \to g$ in $L^\infty$ but only that the limit $g$ is in $L^\infty$) is true and your proof of this is indeed correct.


问:
Finding the points in which a smooth surface is regular
I've been given a surface $\sigma(u,v) = (4u,3u,5\sqrt{1-v^2})$ with $u\in\mathbb{R}$, $v \in]-1,1[$ and asked to find the points in which the surface is regular.

I've tried to find these points graphically (critical points) but to no avail. How can I solve this through formulas?

答:
Given $\phi : U \to \mathbb{R}^3$

$\phi (u,v)=(x(u,v),y(u,v),z(u,v))$

The points on the surface which are regular (say P), are those where the matrix $\partial_\phi(P)$ has rank 2.
This is also equivalent to say that the columns must be independent vectors of $\mathbb{R}^3$.

A further explanation can be found here: http://uregina.ca/~mareal/cs3.pdf (second page)


问:
Find values of a parameter p for which the series $\sum_{n=1}^\infty \sqrt{n}\ln^{p} \left(1+ \frac{1}{\sqrt{n}}\right)$
I was requested to find the values of the parameter p for which the following series converges:

$$\sum_{n=1}^\infty \sqrt{n} \ln^{p} \left(1+ \frac{1}{\sqrt{n}}\right)$$

I tried using Cauchy's test and the Term test, but reached a dead-end.
I also tried to use the ratio test with but it didn't seem to be helpful in this situation.

At this point we aren't allowed to use the integral test.

I would appreciate any suggestions on how to approach this problem.

答:
Hint: use the fact that
$$
x-\frac12x^2\le\log(1+x)\le x.
$$

If required it can be proved integrating the inequality
$$
1-x\le\frac1{1+x}\le1,
$$
obviously valid for $x\ge0$.


问:
Proof that the phase of the average of unitary complex numbers is the average phase
I'm quite struggling with the following problem:

-Prove that if
\begin{equation}
re^{i\psi} = \frac{1}{N}\sum_{j=1}^N e^{i\theta_{j}},
\end{equation}

then $\psi = \frac{1}{N}\sum_{j=1}^N \theta_{j}$, i.e the phase of the average of unitary complex numbers is the average phase

I managed to prove it for N=2, but I need a proof for arbitrary N.

答:
After a bit of rumination, I've come up with a possible answer.

If the phases $\theta_j$ are clustered near each other, we could take the paraxial approximations

\begin{equation}
\psi - \theta_i = arctg\left[\frac{\sum_{j=1}^Nsin(\theta_j-\theta_i)}{\sum_{j=1}^Ncos(\theta_j-\theta_i)}\right] \approx arctg\left[\frac{\sum_{j=1}^N(\theta_j-\theta_i)}{N}\right] \approx \frac{\sum_{j=1}^N(\theta_j-\theta_i)}{N},
\end{equation}
so that
\begin{equation}
\psi \approx \frac{1}{N}\sum_{j=1}^N\theta_j,
\end{equation}
which could be the reason why $\psi$ is usually taken as a measure for the average phase. If that is the case, this estimate should be considered only for quasi-coherent states.


问:
A trace norm upper bound proof for a matrix that is a linear combination of rank-1 matrices
I want to prove an upper bound for the trace norm of any matrix $W$ which is a linear combination of matrices $M_i \in \mathbb{M}$, $\mathbb{M} = \{uv^T: u \in \mathbb{R}^d, v \in \mathbb{R}^k, \|u \| = 1, \|v\|=1\}$. $\|.\|_*$ is the trace norm.

$$\|W\|_*= \| \sum \theta_iM_i\|_* \le  \sum \|\theta_iM_i\|_* \le \sum \theta_i \| M_i\|_* =  \sum \theta_i \| uv^T\|_*  $$

My question is what is an upper bound for $\| uv^T\|_*$? is it $1$?

答:
For every pair of unit vectors $u,v,$ $\|uv^T\|_* = 1$. In particular, you can say that
$$
u \cdot 1 \cdot v^T
$$
is a compact SVD.


问:
Variance of Fourier Transform related to the derivative of signal?
Define the frequency variance as:
$$ \sigma^2 = \int^\infty_{-\infty}\omega^2 P(\omega) d\omega$$
Where $P(\omega)$ is the spectral density function, which is the same as normalized power. Therefore,
$$ \sigma^2 = \frac{\int^\infty_{-\infty}\omega^2 X(\omega)\bar{X}(\omega) d\omega}{\int^\infty_{-\infty} X(\omega)\bar{X}(\omega) d\omega}$$

$X(\omega)$ is the Fourier transform of the signal $x(t)$. We can rewrite the numerator ($v$) as:

$$ v = \int^{\infty}_{-\infty}(i \omega X(\omega)e^{i\omega t})(-i \omega \bar{X}(\omega)e^{-i\omega t}) d\omega$$
$$ = \int^{\infty}_{-\infty}|i \omega X(\omega)e^{i\omega t}|^2  d\omega$$

I am trying to relate $v$ to the following expression of the gradient of the signal $x(t)$:
$$ \frac{dx(t)}{dt}=\int^{\infty}_{-\infty} i \omega X(\omega)e^{i\omega t} d\omega$$

However, all I can come up with is the following inequality:

$$v \geq \left(\frac{dx(t)}{dt} \right)^2 $$

which doesn't make sense since $v$ is independent of time (and frequency) but $\left(\frac{dx(t)}{dt} \right)^2$ is dependent on time.

What is the best way to express $v$ in terms of $\frac{dx(t)}{dt}$?

答:
My answer is:
$$ \sigma^2 = \frac{\int^{\infty}_{-\infty} | \frac{dx(t)}{dt} |^2 dt}{\int^{\infty}_{-\infty} | x(t) |^2 dt} $$

I had posted the same question in Mathoverflow and just posted the answer to it.

The relationship turns out to be obvious if you identify that $i \omega X(\omega)$ is a Fourier transform of $\frac{dx(t)}{dt}$, and then we can use Perseval's theorem.


答:
$$\begin{align}
\sqrt{n} \ln^{p} (1+ \frac{1}{\sqrt{n}})
&\overset1= \sqrt n \left( \frac{1}{\sqrt n} + O\left(\frac 1n \right)\right)^p \\
&\overset2= \sqrt n\frac{1}{(\sqrt n)^p}\left(1 + O\left(\frac{1}{\sqrt n}\right)\right) \\
&\overset3= \frac{1}{n^{p/2-1}} + O\left(\frac{1}{n^{(p-1)/2}}\right)
\end{align}$$
Explanation:

Using $\ln(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3}-...$ for $|x|<1$.

Factoring out $\frac{1}{\sqrt n}$ and using $(1+x)^p = 1 + O(x)$.

Expanding the bracket.

Title: Find values of a parameter p for which the series $\sum_{n=1}^\infty \sqrt{n}\ln^{p} \left(1+ \frac{1}{\sqrt{n}}\right)$

Body:
I was requested to find the values of the parameter p for which the following series converges:

$$\sum_{n=1}^\infty \sqrt{n} \ln^{p} \left(1+ \frac{1}{\sqrt{n}}\right)$$

I tried using Cauchy's test and the Term test, but reached a dead-end.
I also tried to use the ratio test with but it didn't seem to be helpful in this situation.

At this point we aren't allowed to use the integral test.

I would appreciate any suggestions on how to approach this problem.


问:
Compact Riemann surfaces with boundary
I am familiar (to an extent) with the theory of compact Riemann surfaces without boundary, but I am interested in the theory of compact Riemann surfaces with boundary.

To what extent do the following ideas/results generalize?

Riemann-Roch theorem

Abel's theorem

The Riemann-Hurwitz formula

The classification of holomorphic line bundles

The literature seems to be a little sparse on this particular subject, so any suggestions would be appreciated.

答: A Riemann surface with boundary is not an algebraic-geometric object, but a real two dimensional manifold, so most of the things you mention do not make sense in that setting. Riemann surfaces with cusps are probably the closest you can come (and there the theory works fine - read Forster's book).</p>

Title: Compact Riemann surfaces with boundary


Title: Understanding a double union of a set

Body:
An example may help. Let
$$
F = \{(1, 2), (2, 3), (3, 1)\} = \{\{\{1\}, \{1, 2\}\}, \{\{2\}, \{2, 3\}\}, \{\{3\}, \{3, 1\}\}\}
$$
Then:
$$
\begin{align*}
\bigcup F &=\{\{1\}, \{1, 2\}, \{2\}, \{2, 3\}, \{3\}, \{3, 1\}\}
\end{align*}
$$
And

$$
\begin{align*}
\bigcup\bigcup F &= \bigcup\{\{1\}, \{1, 2\}, \{2\}, \{2, 3\}, \{3\}, \{3, 1\}\} \\
 &= \{1, 1, 2, 2, 2, 3, 3, 3, 1\} \\
 &= \{1, 2, 3\}
\end{align*}
$$


问:
How to know the shape of the parametric curve $(\frac{6m^2 - 8m}{m^2+1}, \frac{-6m + 8}{m^2 + 1})$?

How to know the shape of the parametric curve $(\frac{6m^2 - 8m}{m^2+1}, \frac{-6m + 8}{m^2 + 1})$, where $m$ goes from -$\infty$ to $\infty$?

I know it should be a circle by plotting it on a graph using a computer, but does there exist a mathematical way for me to deduce the shape of this parametric curve? Obviously, $x = -my$ here but I don't see how it gives useful information.

答:
Consider $$\frac{x}{y}=-m$$
Substitute this expression for $-m$ into the expression for $y$ and you end up with the equation of a circle.

Can you finish?


问:
Role of orthonormal basis for: Linear functional on a finite dimensional inner product space is 'inner product with a fixed vector in the space'
I am working through Theorem 6 in Chapter 8 of Hoffman and Kunze.  (The section is Linear Functionals and Adjoints.)

The statement is
 Let $V$ be a finite-dimensional inner product space, and $f$ a linear functional on $V$.  Then there exists a unique vector $\beta$ in $V$ such that $f(\alpha) = (\alpha | \beta)$ for all $\alpha$ in $V$.

(EDIT:  The following is written in terms of a real vector space.)

I am fine with the fact that this essentially follows from what $f$ does to the elements of a basis for $V$, in other words:

For an arbitrary* $\mathcal{B} = \{e_1, \ldots, e_{n} \}$ (where $n = \dim V\;\;$) we can assign $\xi_{i} = f(e_{i})$ for $i=1,\ldots, n$.  Then any $\alpha \in V$ can be written as $\alpha = x_{1}e_{1} + \cdots + x_{n}e_{n}$ so that
$$\begin{align}
f(\alpha) &= f(x_{1}e_{1} + \cdots + x_{n}e_{n}) \\ \\
          &= x_{1}f(e_{1}) + \cdots + x_{n}f(e_{n}) \\ \\
          &= x_{1} \xi_{1} + \cdots + x_{n}\xi_{n}.\end{align}$$

At this point we can identify the $\xi_{i}$'s as being independent of $\alpha \in V$, and only having been dependent on our choice of a basis.  With this, we can simply assert that $\beta = (\xi_{1}, \ldots, \xi_{n})$ (and is in fact unique).

Now, this is apparently not the whole story!  *According to H. and K., the coordinates of our fixed vector $\beta$ are determined by the action of $f$ on an orthonormal basis for $V$ rather than an arbitrary basis.

Question:  What role does the orthogonality (or even the 'orthonormality') of the basis have in this argument?  It seems to work just fine for an arbitrary basis as far as I can tell.

答: If the basis $\{e_1,\ldots,e_n\}$ is not orthonormal, then the inner product of the vectors $\alpha = x_1e_1 + \cdots + x_n e_n$ and $\beta = \xi_1 e_1 + \cdots + \xi_n e_n$ is not equal to $x_1\xi_1+\cdots+x_n\xi_n$.  Thus, while it is true that $f(\alpha) = x_1\xi_1+\cdots+x_n\xi_n$, it is not true that $f(\alpha)=(\alpha|\beta)$.</p>

ContentLicense: CC BY-SA 2.5


问:
What is the best book to learn probability theory through a linear algebra perspective?
I have heard from my linear algebra professor in undergraduate studies that probability theory can be examined using linear algebra.

As a math student who enjoys linear algebra, does anyone have a good textbook that uses linear algebra to examine probability theory?

答:
One book that explores probability from a linear algebraic point of view is Hilbert Space Methods in Probability and Statistical Inference by Christopher G. Small and Don L. McLeish. From the introduction:

In the traditional approach to probability and statistics, the
starting point is the concept of the sample space and a class of
subsets called events. The Hilbert space approach shifts the starting
point away from the sample space and replaces it with a Hilbert space
whose elements can be variously interpreted as random variables,
estimating functions, or other quantities depending on the data and
the parameter.

But be aware that this book is almost 30 years old (published 1994), and I don't know to what extent practicing probabilists or mathematical statisticians work within this framework today. (Also note that basic linear and matrix algebra is the natural language for multivariate probability and statistics. The Hilbert space view here is more general.)


问:
Radius of circle tangent to six tangent parabolas

Six congruent copies of the parabola $y = x^2$ are arranged in the plane so that each vertex is tangent to a circle, and each parabola is tangent to its two neighbors. Find the radius of the circle.

I'm honestly not sure how to start this problem. The vertices of the parabolas are spaced $60^\circ$ apart on the circumference of the circle, and the points where two parabolas are tangent are also spaced $60^\circ$ apart, $30^\circ$ from a vertex. But I'm not sure how this is useful.

I also know that the focus and directrix of each parabola are the same distance from the vertex, and the directrixes (is that the plural?) intersect $60^\circ$ apart, $30^\circ$ from a vertex. But again, I don't know how useful that is.

Normally on problems like these I'd try to draw a radius and form some right triangles but I really don't see how I can do that here.

TIA!

答:
The idea is to look at a single parabola of the form $y = x^2 + r$, and determine $r$ such that the parabola is tangent to the lines $$y = \pm \sqrt{3} x.$$  This $r$ will be the radius of the inscribed circle.  See the following figure, which only shows the top and bottom parabolas, but adds the lines:

To this end, we compute the derivative $$\frac{dy}{dx} = 2x$$ and equate it to $\pm \sqrt{3}$ to obtain $$x = \pm \frac{\sqrt{3}}{2}.$$  These are the $x$-values at which the parabola is tangent.  So we require $$(\pm \sqrt{3}/2)^2 + r = \pm \sqrt{3}(\pm \sqrt{3}/2) = 3/2,$$ hence $$r = \frac{3}{2} - \frac{3}{4} = \frac{3}{4}.$$


问:
Aren't those Random Variables in a Stochastic Process the same "Functions"? Why do we need to index them?
To my knowledge, a Stochastic Process is a set of Random Variables indexed by time.

Let's take the Bernoulli process as an example, which is a sequence of independent and identically distributed (iid) random variables.

But aren't those random variables in the Bernoulli process the same?
Since every random variable is just a function that maps an outcome from the sample space to a real number, $F: S \to \mathbb{R}$.

If they are just a set of random variables that measure a coin-flip $\{Head, Tail\}$ to $\{T, F\}$, what makes these random variables different so that I need to index them by time ($X_1, X_2, ...$)?

答:
Maybe an example will help.  Let's take the sample space to be the unit interval $[0,1]$, and the probability measure $P$ thereon to be Lebesgue measure. If $\omega\in[0,1]$ let
$$
\sum_{n=1}^\infty {\omega_n\over 2^2}
$$
be the base 2 expansion of $\omega$. Now define $X_n(\omega) :=\omega_n$ to be the $n$th binary digit of $\omega$. [In the ambiguous case of an $\omega$ with a terminating expansion, I choose the one than terminates in all $0$s.] The functions $X_n:[0,1]\to\{0,1\}$ are all different functions,
but they all have the same distribution:
$$
P[X_n=0] = P[X_n=1] = {1\over 2},\qquad n=1,2,\ldots.
$$
In addition, the $X_n$s are mutually independent, so they constitute an instance of a "Bernoulli process".


问:
The students $S_1, S_2,...S_{10}$ are divided into 3 groups A, B and C
It can be seen as distributing n unique objects above m groups

The students $S_1, S_2,...S_{10}$ are divided into 3 groups A, B and C such that each group has at least one students and C has at most 3. Find possibilities of forming groups

$$a+b+c=10$$

The number of positive integral solutions $(\ge 1)$ is
$$\binom {10-1}{3-1}=36$$

I don’t know how to account for the cases where C has at most 3 students

Also I know this method of solving is probably wrong but I don’t know how else to do it.

答:
Hint: the simplest way is to consider the problem by cases. There are only 3 options:
$$
c=1,2,3.
$$

The second issue is that you are asked not about the number of ways to choose the size of groups but to distribute the students between them. For example for $c=1$ the number is
$$
\binom{10}1\sum_{i=1}^8\binom9i=\binom{10}1(2^9-2)
$$

Can you take it from here?