问:
How to interpret the square root of inner product over an arbitrary field?
In an inner product space, the norm $\|x\| = \sqrt{\langle x,x\rangle}$ is induced. I realise I have almost always dealt with either real or complex numbers, so took the square root for granted.

Reading the Inner Product entry on
Wolfram (https://mathworld.wolfram.com/InnerProduct.html), it says "A vector space together with an inner product on it is called an inner product space. This definition also applies to an abstract vector space over any field." This was said after introducing the axioms in the context of a space over $\mathbb{R}$.

I am confused because I do not know how to interpret the square root in an arbitrary field. I assume the obvious way would be to define it to be the element $a \in \mathbb{F}$ such that $a^2 = \langle x,x\rangle$. But the issue I am having is how we even know whether such an element exists in the field? Is this a standard result from ring theory?

My understanding has always been that inner product spaces (and normed spaces) are only defined over either the real or complex numbers. How do you construct them (or something equivalent) over some arbitrary field?

答:
You do not have a norm defined for an arbitrary inner product space. For instance,  $\langle x, y\rangle = x_1 y_1 - x_2 y_2$ is an inner product on $\mathbb{R}^2$.

The norm will be defined on euclidian spaces or hermitian spaces. There are extra conditions ( positivity) required.


问:
Attempting to figure out angle from ray of a cone in $\mathbb{R}^{3}$
I'm working through Shifrin's Multivariable Mathematics and I've stumbled in attempting to figure out a specific statement. I have the following mapping:

Now one of the claims is that "if we fix $v = v_{0}$, the image is a ray making an angle of $\frac{\pi}{4}$." The claim of the image being a ray makes sense to me, but I was attempting to figure out how $\frac{\pi}{4}$ was arrived at. I tried to look at the cone through the point of view of an individual slice and use the trig functions available for right triangles with my $Z$ - axis serving as one of the two axis, but any manipulation in that manner doesn't get me the result.

I guess I'm wondering if it is possible to figure out the angle without having to resort to spherical coordinates?

答:
Here is a diagram.

$r \leq \sqrt{u^2 \cos^2\theta + u^2 \sin^2\theta} = u$

So what you have is a right angled triangle with $\, l^2 = r^2 + z^2 = 2u^2 \implies l = u \sqrt2$.

Hence in this case, the angle between the axis of the cone and its outer edge is

$\displaystyle \tan^{-1} ({\frac{r}{z}}) = \tan^{-1} (1) = \frac{\pi}{4}$.

ContentLicense: CC BY-SA 4.0


问:
angle determined by tangent ratios
I'm new here and not a math student so I apologize if this question is too dumb but I don't know where to begin to solve it.
Given the image below, I'm looking for the red "α" angle such that the ratio between the 2 red segments is equal to the ratio between the 2 blue segments. That's all you need to know. Every other angle is a known variable.

I'd lose my pride if someone told me the full answer but I need at least a starting point because my trigonometry skills are failing me.

答:
Thanks to David K's hint, I could carry on and find the solutions.
Below are my calculations (you have to read David's answer first). I decided to consider a slightly different "$r$" ratio to make it simpler: instead of the ratio between the small and the big segment, I used the small and the sum of the 2 segments. This means I did not have to add the $−tanα$ in the denominator of David's "$r$" fraction.

The quadratic equation brought to my attention the fact that there are actually 2 solutions to this geometrical problem.

This is the second one (I eyeballed the $α$ angle in this drawing, just like in the original one btw) :

So this one is the $\frac{-b+\sqrt{Δ}}{2a}$ root and the original one is $\frac{-b-\sqrt{Δ}}{2a}$

Why this way and not the other way around ? I haven't found proof other than the behavior of the software I use so far. Maybe I'll come back for a detailed answer on that later.

Careful : it may look like the red tangent is parallel to OD but that is pure coincidence.

Title: angle determined by tangent ratios


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

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

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

答:
I also had issues understanding this until I saw quotients in topology. The idea of a quotient in topology is that you "glue" together stuff. For instance, if you start with the square $I^2 = [0,1]^2$, and you glue together the boundary, you get something like a sphere. That's because what you did was glue together the boundary to a single point. Now all the square is reduced to a point.

In algebra, while the visual intuition is not as clear, the same thing happens. Maybe, to get some intuition, start with the obvious quotients. What's $G/G$? Well you're "gluing" all of $G$ into a single point. This is why $G/G = \{e\}$. So in a sense, when you have a normal subgroup that has a certain property, when you quotient out by that subgroup, you effectively reduce all elements that satisfy that property to a single point.

To give you another example from ring theory, the set of nilpotent elements in a ring form an ideal, called the nilradical $N(A)$. In other words, $x\in N(A)$ if and only if $x$ is nilpotent. So what happens when you consider $A/N(A)$? Well, effectively you reduce every nilpotent element to a point, which makes your ring reduced. There's only one nilpotent element now, namely, $0$.

If you think of this geometrically, if the set of elements satisfying a property $P$ forms an ideal $I$, then $A/I$ has only one element that represents $I$. This is why the property "disappears" in the quotient, because you've reduced it to a point. Indeed, if $x$ satisfied $P$ before, then $x\in I$, and the elements of $A/I$ are of the form $a+I$. But $x+I$ is just $I$, the identity in $A/I$.


问:
QQplot to check normal distributed
If I have 10000 data points, how can I check sum(aX+b)/n whether converges to a normal distribution by using qqplot() in R. I am trying to plot the qqplot but not sure how to di it.

For instance, I have mu = 3 and sigma = 5, and my estimated mu, sigma are very closed to 3 and 5. I have 10000 data points in total.

答:
Three samples. Let's look at normal probability plots of three samples of size $n = 1000,$ the first of which is sampled from a normal population.

```<code>set.seed(1124)
x1 = rnorm(1000, 50, 5)
x2 = rgamma(1000, 4, 1/10)
x3 = rbeta(1000, 4, 6)
</code>```

Histograms and population densities. Below are histograms of the three samples. Superimposed on each histogram is a red density curve for the relevant population.

```<code>par(mfrow=c(1,3))
hist(x1, prob=T, br=15, col="skyblue2", main="n=1000, NORM(50,5)")
 curve(dnorm(x,50,5), add=T, col="red", lwd=2)
hist(x2, prob=T, br=15, col="skyblue2", main="n=1000: GAMMA(4,.1)")
 curve(dgamma(x,4,.1), add=T, col="red", lwd=2)
hist(x3, prob=T, br=15, col="skyblue2", main="n=1000: BETA(4,6)")
 curve(dbeta(x,4,6), add=T, col="red", lwd=2)
par(mfrow=c(1,1))
</code>```

Normal quantile plots. In R anyhow, it is not necessary to provides values or estimates of population means or variances in order to make such plots.

(In each plot the green reference line
runs through theoretical normal and sample lower and upper quantiles. Normal samples tend to yield points that lie near such reference lines--except possibly for a very few points near the maximum and minimum.)

```<code>set.seed(1124)
x1 = rnorm(1000, 50, 5)
x2 = rgamma(1000, 4, 1/10)
x3 = rbeta(1000, 4, 6)
par(mfrow=c(1,3))
qqnorm(x1, main="n=1000: NORM(50,5)")
 qqline(x1, col="green", lwd=2)
qqnorm(x2, main="n=1000: GAMMA(4,.1)")
 qqline(x2, col="green", lwd=2)
qqnorm(x3, main="n=1000: BETA(4,6)")
 qqline(x3, col="green", lwd=2)
par(mfrow=c(1,1))
</code>```

Title: QQplot to check normal distributed

Body:
Three samples. Let's look at normal probability plots of three samples of size $n = 1000,$ the first of which is sampled from a normal population.

set.seed(1124)
x1 = rnorm(1000, 50, 5)
x2 = rgamma(1000, 4, 1/10)
x3 = rbeta(1000, 4, 6)

Histograms and population densities. Below are histograms of the three samples. Superimposed on each histogram is a red density curve for the relevant population.

par(mfrow=c(1,3))
hist(x1, prob=T, br=15, col="skyblue2", main="n=1000, NORM(50,5)")
 curve(dnorm(x,50,5), add=T, col="red", lwd=2)
hist(x2, prob=T, br=15, col="skyblue2", main="n=1000: GAMMA(4,.1)")
 curve(dgamma(x,4,.1), add=T, col="red", lwd=2)
hist(x3, prob=T, br=15, col="skyblue2", main="n=1000: BETA(4,6)")
 curve(dbeta(x,4,6), add=T, col="red", lwd=2)
par(mfrow=c(1,1))

Normal quantile plots. In R anyhow, it is not necessary to provides values or estimates of population means or variances in order to make such plots.

(In each plot the green reference line
runs through theoretical normal and sample lower and upper quantiles. Normal samples tend to yield points that lie near such reference lines--except possibly for a very few points near the maximum and minimum.)

set.seed(1124)
x1 = rnorm(1000, 50, 5)
x2 = rgamma(1000, 4, 1/10)
x3 = rbeta(1000, 4, 6)
par(mfrow=c(1,3))
qqnorm(x1, main="n=1000: NORM(50,5)")
 qqline(x1, col="green", lwd=2)
qqnorm(x2, main="n=1000: GAMMA(4,.1)")
 qqline(x2, col="green", lwd=2)
qqnorm(x3, main="n=1000: BETA(4,6)")
 qqline(x3, col="green", lwd=2)
par(mfrow=c(1,1))


问:
Simplifying vector norms in a proof
Consider the optimization problem
$$
\min _{y \in \mathbb{R}^{n}} f(y):=\frac{1}{2}\|A y-b\|_{2}^{2}
$$
Let y be a feasible solution and $y^{*}$ be the optimal solution. The goal is to prove that
$$
f(y)-f\left(y^{*}\right)=\frac{1}{2}\left\|A y-A y^{*}\right\|_{2}^{2}, \forall y \in \mathbb{R}^{n}
$$
I am getting confused when simplifying vector norm terms, which I think is necessary in this proof. My attempt:
$$f(y)=\frac{1}{2}\|A y-b\|_{2}^{2}$$
$$f(y^{*})=\frac{1}{2}\|A y^{*}-b\|_{2}^{2}$$
So,
$$\frac{1}{2}\|A y-b\|_{2}^{2} - \frac{1}{2}\|A y^{*}-b\|_{2}^{2} = \frac{1}{2}\left\|A y-A y^{*}\right\|_{2}^{2}$$
$$\left(\|Ay\|_{2}^{2} - 2\|Ay\|_2\|b\|_2 + \|b\|_2^{2}\right)-\left(\|Ay^{*}\|_{2}^{2} - 2\|Ay^{*}\|_2\|b\|_2 + \|b\|_2^{2}\right) = \|A y-A y^{*}\|_{2}^{2}$$
$$\|A y\|_2^{2} - \|A y^{*}\|_2^{2} = \|A y-A y^{*}\|_{2}^{2}$$
$$\|A y-A y^{*}\|_{2}^{2} = \|A y-A y^{*}\|_{2}^{2}$$
Not very sure about the last two steps. Maybe an application of the Triangle Inequality here?

答:
Because $y^*$ is optimal for the unconstrained optimization problem, we must have $\nabla f(y^*)=0$, i.e. $$A^\top (Ay^*-b)=0.$$

You expanded the norms incorrectly: $\|v-w\|_2^2 = \|v\|_2^2 - 2 v^\top w + \|w\|_2^2$ (the middle term is not $\|v\|_2 \|w\|_2$).

Note that
$$\|Ay-b\|_2^2 - \|Ay^* - b\|_2^2
= \|Ay\|_2^2 - 2 b^\top Ay - \|Ay^*\|_2^2 + 2 b^\top A y^*$$
and
$$\|Ay-Ay^*\|_2^2 = \|Ay\|_2^2 + \|Ay^*\|_2^2 - 2 y^\top A^\top A y^*.$$
It suffices to show the difference is zero. The difference (halved) is
\begin{align}
&\|Ay^*\|_2^2 - y^\top A^\top A y^* + b^\top Ay - b^\top A y^*
\\
&= \|Ay^*\|_2^2 - y^\top \underbrace{A^\top (Ay^*-b)}_{=0} - b^\top A y^*
\\
&= \|Ay^*\|_2^2 - b^\top A y^*
\\
&= (y^*)^\top \underbrace{A^\top (Ay^* - b)}_{=0}\
\\
&= 0.
\end{align}

Title: Simplifying vector norms in a proof


问:
a (bigger than 1) is always bigger than its roots
how can I formally proof that for a > 1: $$ a> \sqrt a > \sqrt[3]a > \sqrt[4]a ...  $$?
Can someone help? ;)

答:
Set $a:=e^b,$ where $b>0;$

Then

$e^b>e^{b/2}>.....e^{b/n}>e^{b/(n+1)}$ since $f(x)=e^x$ is an increasing function.


问:
Why does $7^{2\ln x}\cdot \ln(7) \cdot (2/x)$ equal to $7^{2\ln x}\cdot \ln(49) /x$?
While reviewing, I came upon this problem which has the derivative

$7^{2\ln x}\cdot \ln(7) \cdot (2/x)$

simplified to

$7^{2\ln x}\cdot \ln(49) /x$

How/why is it simplified like that?

答:
The simplification relied on the following fact:

If $a>0$, then $2\log(a) = \log(a^2)$.

In your case, the $2 \log(7)$ got converted to $\log(7^2) = \log(49)$. The rest of the terms remain as such.

ContentLicense: CC BY-SA 3.0


问:
Finding global maximum of a 2-variable function
Let $$f(x,y) = -e^{x^4+y^2}+x^2+y^2+1$$

Find global/local maximum and minimum and upper/lower bound of the function.

I found that the lower bound is ${-\infty} $ and also that, since $$-e^{x^4+y^2}\le -1-x^4-y^2, \forall (x,y)\in \mathbb{R}^2$$we have $$f(x,y)\le -x^4+x^2\le\frac{1}{4},\forall(x,y)\in\mathbb{R}^2$$ so that function is upper bounded.

Then I calculated the critical points, which are $(0,0)$ and $(\pm\alpha,0)$, with $\alpha$ the positive solution of the equation $$e^{x^4}=\frac{1}{2x^2}$$ and by the second-derivative test is apparent that $(0,0)$ is a saddle point while both $(\pm\alpha,0)$ are local maximum.

How do I prove that both $(\pm\alpha,0)$ are global maximum?

答: The function $f$ is even, so $f(\alpha, 0)=f(-\alpha,0)$. The global maximum of $f$ is in particular a local maximum, hence $(\pm \alpha,0)$ must be the points where $f$ attains a global maximum.


问:
How to frame this optimisation problem mathematically so it can be coded up.
I am trying to develop a methodology for solving a constrained optimisation problem I am facing, I would appreciate any help/pointers on how best to frame this problem so that it can be coded up efficiently.

Consider a data set with a unique identifier column along with other variables (you can think of this as a data table/matrix). There are numerous (not necessarily linear) constraints that need to be satisfied on the aggregate level on this data set, and I can remove ids from my data set until these constraints are satisfied on the aggregate level.

I would like to remove ids (or select ids) such that an objective function is maximised (or minimised) - the idea is to have the option to use different objective functions at this stage which is why I have not specified one.

Simplified Example

Below, I have included an example of the scenario I have described above - the context/constraints here are meaningless but should demystify what I am trying to achieve hopefully.

Consider a data set with 5 columns: id, a, b, c and d. Each id has an associated a, b, c and d variable.

Constraints: Overall mean of column a must be <=15, Sum(c)/total_number_ids >= 50%.

Objective Function: Some aggregation of the a,b,c and d (and potentially others) variables - in practice this could be fairly complex.

Task: Remove (or include) ids from the data set such that we maximise (or minimize) the objective function whilst ensuring that on the aggregate the constraints are met.

The end goal to essentially have a list of ids that are to be removed (or included).

Some help on how to frame this problem mathematically and which methods could be used from an optimisation perspective would be greatly appreciated. I have a lot of flexibility in the methods I can use but I would be keen to explore efficient ideas.

答:
Introduce a binary variable $x_i$ to indicate whether row $i$ is included.  Your first constraint becomes
$$\frac{\sum_i a_i x_i}{\sum_i x_i} \le 15,$$
which (assuming $\sum_i x_i \ge 1$) you can linearize as
$$\sum_i a_i x_i \le 15 \sum_i x_i,$$
equivalently,
$$\sum_i (a_i-15) x_i \le 0$$

Not sure exactly what you meant by your second constraint, but maybe you want this:
$$\frac{\sum_i c_i x_i}{\sum_i c_i} \ge 0.5$$


问:
Independence of the statement that a union of $<\mathfrak{c}$ many measure zero sets has measure zero
I read that that the statement that a union of fewer than continuum many measure zero sets has measure zero is independent of $\sf{ZFC}$. Is there a standard reference to this result?

答:
I think the book by Bartoszyński and Judah is one of the standard references for this kind of result (especially, cardinal characteristics of the continuum that are related to null and meager ideals.) Let me sketch how you can construct a proof.

On the one hand, Martin's axiom $\mathsf{MA}$ proves that the union of $<\mathfrak{c}$ null sets is always null. You can see the proof of the consistency of Martin's axiom in some textbooks about forcing (if it covers iterated forcing. Jech and Kunen certainly mention it.)

(Note. I realized that Martin's axiom is overkill. Just assuming the continuum hypothesis suffices. However, Martin's axiom shows that the union of $<\mathfrak{c}$ null sets is still null regardless of what the value of $\mathfrak{c}$ is.)

On the other hand, establishing the consistency of the negation of your statement is usually stated in the following combinatorial form: can we force the following cardinal

$$\mathsf{add}(\mathcal{N}):= \min\{\kappa : \text{the union of some $\kappa$ null sets is not null}\}$$

strictly less than $\mathfrak{c}$? Section 7.3.A of Bartoszyński and Judah discusses how to force $\mathsf{add}(\mathcal{N})<\mathfrak{c}$.


问:
Why is it the case that $\det(T_\alpha)=\det(T_\alpha|_{\mathbb{Q}(\alpha)})^{n/d}$
I'm reading a solution to a problem and in it they use this fact, It seems intuitive that it should be true, but I dont see how you could show it.

$K$ is a number field of degree $n$, and $\alpha\in K$. $T_\alpha:K\to K$ is a linear transformation from $K$ as a $\mathbb{Q}$ vector space corresponding to multiplication by $\alpha$.
Then, if $[\mathbb{Q}(\alpha):\mathbb{Q}]=d$, we get $[K:\mathbb{Q}(\alpha)]=\frac{n}{d}$.

How can we show that $\det(T_\alpha)=\det(T_\alpha|_{\mathbb{Q}(\alpha)})^{n/d}$ and that $N_{K/\mathbb{Q}}(\alpha)=(N_{\mathbb{Q}(\alpha)/\mathbb{Q}}(\alpha))^{n/d}$

答:
Take a basis
$$K = \sum_{j=1}^{n/d} b_j \Bbb{Q}(\alpha)$$

Each subspace $b_j \Bbb{Q}(\alpha)$ is sent to itself by the linear map $T_\alpha:x\to \alpha x$, thus $$\det(T_\alpha) = \prod_{j=1}^{n/d} \det(T_\alpha|_{b_j \Bbb{Q}(\alpha)})$$
Finally $$\det(T_\alpha|_{b_j \Bbb{Q}(\alpha)})=\det(T_\alpha|_{\Bbb{Q}(\alpha)})$$


问:
Find all real values of $x$ which satisfy $\sqrt{x^2 + 1} + x^2 + 1 = 90$.
Find all real values of $x$ which satisfy $\sqrt{x^2 + 1} + x^2 + 1 = 90$.

\begin{align*}
\sqrt{x^2+1} + x^2 &=  89 \\
{(\sqrt{x^2+1} + x^2)}^2 &=  89^2 \\
x^2+2x^2\sqrt{x^2+1}+x^4 &=89^2
\end{align*}

Letting $y = x^2$, so $y^2 = x^4$. This gives us
\begin{equation}
y^2+2y\sqrt{y+1}+y=7920
\end{equation}

I not sure how to proceed to eliminate the radical. I shouldn't square quantities that aren't both positive or else I'll lose the equivalency in the new equation right?

答:
Let me point out couple of substitutions that simplifies this equation:

$T=\sqrt{x^2+1},$ then we have a quadratic equation $$T^2+T-90=0$$ which has two solution s $T=9$ and $T=-10.$ Then you continue from here (with the condition that $T\ge 1$).

$x=\tan\theta,$ then $x^2+1=\sec^2\theta$ and we get a trigonometric equation $$\sec^2\theta+\sec\theta-90=0.$$ Similarly $x=\cot\theta$ is also a possible trigonometric substitution for this equation.

$x=\sinh\theta$ has the property that $x^2+1=\cosh^2\theta$ and hence we get $$\cosh^2\theta+\cosh\theta-90=0.$$

In last two substitutions both $\sec$ and $\cosh$ are even functions, therefore we don't need to consider the negative square root as a separate case.


问:
$\nabla^2f(x)>0$ is a necessary or sufficient condition of the Newton direction $s=-[\nabla^2f(x)]^{-1}\nabla f(x)$ to be a descent direction?
Let $f: \mathbb{R}^N \rightarrow \mathbb{R}$. The Newton direction $s=-[\nabla^2f(x)]^{-1}\nabla f(x)$ a descent direction if:

$\nabla f(x)^Ts<0 \implies -\nabla f(x)^T[\nabla^2f(x)]^{-1}\nabla f(x)<0 $

$\quad\quad\quad\quad\quad\quad\implies \nabla f(x)^T[\nabla^2f(x)]^{-1}\nabla f(x)>0$

$\quad\quad\quad\quad\quad\quad\implies [\nabla^2f(x)]^{-1} $ must be positive definite.

We know that the inverse of a matrix positive definite is also positive definite.

My question is: $\nabla^2f(x)>0$ is a necessary or sufficient condition? and why?

Thanks in advance for any help!

答:
$\nabla^2 f(x) \succ 0$ is equivalent to "$v^\top [\nabla^2 f(x)] v > 0$ for any nonzero vector $v$."

However, you are only asking that the latter condition hold for a specific vector, namely $v = \nabla f(x)$. So positive-definiteness of the Hessian is sufficient for the step to be a descent direction, but not necessary.

(Recall that you run this step many times in Newton's method for different values of $x$ that you do not know in advance. One usually assumes the Hessian is positive-definite everywhere so that we have this assumption that the step is a descent direction. Otherwise it is quite hard to certify whether or not a step will be a descent, and more complex analyses of $f$ would be required to assess how Newton's method will behave.)


问:
Prove if $I$ is an ideal of $R$ ring, then $(I \cup \{x\})/(x) \cong I$.
I am trying to prove the statement above where $(x)$ is the principal ideal generated by the polynom $x$ in $R[x]$, and similarly with $(I \cup \{x\})$. Additionally, I have to prove that $R[x]/(I \cup \{x\}) \cong R/I$ with the help of this statement. For this part, I know that $R[x]/(x) \cong R$ and I should use the 3rd (or maybe 2nd, I don't know which one it is in English) isomorphism theorem, but I'm clueless with the initial statement. I appreciate any sort of help.

答:
The set $(I \cup \{x\})$ is a set of polynomials over $R$, so define a function $\varphi$ from $(I \cup \{x\})$ to $I$ which simply selects the constant term of this polynomial.

This is a homomorphism (this is easy to prove), surjective and its kernel is $(x)$, which proves your proposition through the first isomorphism theorem (sometimes called the homomorphism theorem)


问:
Expected number of trials for event X to happen for the first time vs number of trials after which the expected number of times X happens is 1.
Are these two quantities always the same? Can anyone provide a proof/explanation or counter-example?

As an example, let a trial consist choosing a number from the set {1,2,...,n}, and let event X be that a number is chosen that has been chosen before (a duplicate). Is it true that the expected number of picks for the first duplicate to occur, is the same as the number of picks whereby the expected number of duplicates after this number of picks is 1?

My intuition is that they are the same, and I hope this isn't a daft question.

Many thanks,

t-tough

edit:

Counterexample! Suppose buses always turn up on the hour and suppose exactly half the buses all turn up together at 4pm, and the other half all turn up together at 6pm, but this partition is done at random. Consider the event that bus X turns up. Then the expected number of hours after noon for bus X to turn up for the first time is 5. But at 5pm the expected number of times that bus X has turned up is $\frac{1}{2}$.

答:
If all of the trials are independent and equally likely, the answer is yes.  If the event in question has probability $p$, then the expected number of trials until the first occurrence is $1/p$ (the expectation of a geometric distribution).  On the other hand, the expected number of successes in $m$ trials is $mp$ (the expectation of a binomial distribution), so you need $m = 1/p$ trials to have an expectation of $1$ success.

In the example you give, however, these conditions obviously don't hold, so it's harder to tell.  In particular I'm not sure how to get an expression for $\mathbb{E}$(number of duplicates after $m$ trials) as a function of $m$.

EDIT: Based on computer simulations I suspect the answer is no.  You can calculate directly
$$
\mathbb{E}(\text{# of trials until first duplicate}) = 2 \cdot \frac{1}{10} + 3\cdot \frac{9}{10} \cdot \frac{2}{10} + \dots + 11 \cdot \frac{9}{10} \dots \frac{2}{10} \frac{1}{10} \approx 4.66,
$$
but simulations indicate that the expected number of duplicates after $5$ trials is $\approx 0.9$.


问:
Find the value of summation
If
$$xy = 3 , yz = 6 , xz = 2$$
Find the value of $x+y+z$
My attempt:

Let $$k=x+y+z$$

$$k^2 = x^2 + y^2 + z^2 +2(xy+xz + yz)$$

$$k^2 = x^2 +y^2 + z^2 +22$$

But i stopped here i need a hint

Title: Find the value of summation

Body:
Note
\begin{align}
(x+y+z)^2&= x^2+y^2+z^2+2(xy+yz+zx)\\
&=\frac{(xy)(zx)}{yz}+\frac{(yz)(xy)}{zx}+\frac{(zx)(yz)}{xy}+ 2(xy+yz+zx)\\
&=36
\end{align}
Thus, $x+y+z=\pm6$.


问:
Prove that any group of order $27$ is not simple
I'm stuck on this problem from my abstract algebra course:

Prove that if $G$ is a group with $|G|=27$, then $G$ is not simple.

First I noticed $|G|=27=3^3$. I thought I can use a statement I saw on the text book:

Given $H\leq G$ with $G$ finite and $|G:H|=p$ being $p$ the minimum prime number that divides $|G|$, then $H\unlhd G.$

This would prove that $G$ has a non-trivial normal subgroup, and that would mean $G$ is not simple. But in order to use this I need to prove first that my group $G$ has some subgroup of order $3^2$ (If I'm not wrong, this isn't trivial). So if my reasoning is right, I need to prove that any group of order $27$ has some subgroup of order $3^2$, and my problem will be solved. Am I right? How can I prove this last statement? Any help will be appreciated, thanks in advance.

答:
Every group of prime power order $p^n$ has a non-trivial center. If the group is not abelian, the center thus is a non-trivial proper normal subgroup and hence such a group cannot be simple.

There are many different ways to argue here, see also this post:

Classify groups of order 27

It shows that all subgroups of index $p=3$ are normal.


问:
Conditions for f(x,y) to coincide with some g(x) + h(y)

Given a function of two variables, say f(x,y), how to know/check whether it can be simplified into some g(x) + h(y)?

Some property of some condition that condition that f(x,y) satisfies to know this.

答:
A necessary and sufficient condition is that, for every $(x,y,z,t)$,
$$
f(x,y)+f(z,t)=f(x,t)+f(z,y).
$$</p>


问:
Does being well approximated by a polynomial characterize higher differentiability?
Suppose $f:\mathbb R\to \mathbb R$ admits a polynomial $\sum_{k=0}^n\lambda_k(x-a)^k$ of degree $\leq n$ satisfying $f(x)-\sum_{k=0}^n\lambda_k(x-a)^k\in \mathrm o(|x-a|^n)$ as $x\to a$. Then dividing by powers of $(x-a)$ shows

$$\begin{aligned}\lambda_0 & =\lim_{x\to a}fx, \\ \lambda_1 & =\lim_{x\to a}\tfrac{fx-\lambda_0}{x-a}, \\ \lambda _2 & =\lim_{x\to a}\tfrac{fx-fa-\lambda_1(x-a)}{(x-a)^2}=\lim_{x\to a}\tfrac{\tfrac{fx-fa}{x-a}-\lambda_1}{x-a}, \\  & \vdots \\ \lambda_n & = \lim_{x\to a}\tfrac{fx-\sum_{k=0}^{n-1}\lambda_k(x-a)^k}{(x-a)^n}. \end{aligned}$$

Thus the asymptotic condition determines the polynomial, so it is unique when it exists. If $f$ is furthermore continuous at $x=a$ then $\lambda_0=fa$ whence $\lambda_1=f^\prime(a)$.

If $f$ is $n$-times differentiable at $x=a$ then Peano's form of Taylor's theorem tells us $R^n_af\in \mathrm o(|x-a|^n)$ as $x\to a$. Here $R^n_af(x)=f(x)-j^n_af(x)$ and $$j^n_af(x)=\sum_{k=0}^n\tfrac 1{k!}f^{(k)}(a)(x-a)^k$$ is the $n^\text{th}$ order Taylor series of $f$ about $x=a$.

By uniqueness we therefore have $\lambda_k=\tfrac 1{k!}f^{(k)}(a)$. For instance taking $k=0,1,2$ gives $$\tfrac 12f^{(2)}(a)=\lambda _2  =\lim_{x\to a}\tfrac{fx-fa-f^\prime(a)(x-a)}{(x-a)^2}=\lim_{x\to a}\tfrac{\tfrac{fx-fa}{x-a}-f^\prime(a)}{x-a}.$$

I am interested in the converse: are continuous maps which are well approximated by a polynomial of degree $\leq n$ necessarily $n$-times differentiable?

Question. Suppose $f$ is continuous and admits a polynomial $\sum_{k=0}^n\lambda_k(x-a)^k$ of degree $\leq n$ satisfying $f(x)-\sum_{k=0}^n\lambda_k(x-a)^k\in \mathrm o(|x-a|^n)$ as $x\to a$. Does it follow that $f$ is $n$-times differentiable at $x=a$, with $\lambda_k=\tfrac 1{k!}f^{(k)}(a)$?

Already for $k=2$ this amounts to the assertion$$\tfrac 12f^{(2)}(a)=\lambda _2  =\lim_{x\to a}\tfrac{fx-fa-f^\prime(a)(x-a)}{(x-a)^2}=\lim_{x\to a}\tfrac{\tfrac{fx-fa}{x-a}-f^\prime(a)}{x-a}.$$ This is not obvious at all to me.

答:
The idea is that you cannot reclaim any information about  any neighborhood of $a$. So basically, $f$ may not even be differentiable at any neighborhood of $a$, so definitely it cannot be twice-differentiable. Consider the following example:
$$f(x)=W(x)\cdot e^{-\frac1{x^2}}  $$
Where $W$ is the Weierstrass function. $W$ is known to be non-differentiable at any point. However, $W$ is bounded, and so
$$ f(x)=o(x^n),\quad \forall n\in\mathbb N$$
just as $e^{-\frac{1}{x^2}}$ is. So, $f$ is differentiable at $0$ but
it is non differentiable at any other point. Therefore, we cannot even ask the question whether it is twice differentiable at $0$.


问:
Limit of $\frac{1}{\sqrt[n] n}$
I would like to show that the limit of the sequence $(\frac{1}{\sqrt[n] n})_{n=1}^{\infty}$ is equal to 1 using the definition of the limit of a sequence. (Another way to say this is that it converges to 1).

Definition: A sequence $(a_n)_{n=1}^{\infty}$ converges to a real number A iff for each $\epsilon > 0$ there is a positive integer N such that for all $n \geq N$ we have $|a_n - A| < \epsilon$.

Edit: Here is my work.

Let $\epsilon > 0$. There exists $N$ such that for $n \geq N$,

$$|\frac{1}{\sqrt[n] n}-1| = |\frac{n^{\frac{n-1}{n}}}{n} - 1| = |\frac{n^{\frac{n-1}{n}} - n}{n}| = \frac{n-n^{\frac{n-1}{n}}}{n}$$

Here is where I am stuck.

答:
Pick $\varepsilon>0$. We have

$$\sqrt[n]{n}-1 < \varepsilon \iff \sqrt[n]{n} < 1+\varepsilon \iff n < (1+\varepsilon)^n$$

Now, we have $$(1+\varepsilon)^n = 1+n\varepsilon + {n \choose 2}\varepsilon^2 + \cdots > {n \choose 2}\varepsilon^2 = \frac12(n^2-n)\varepsilon^2$$

so if we pick $$n \ge \sqrt{1+\frac2{\varepsilon^2}} \implies n \le \frac12(n^2-n)\varepsilon^2 < (1+\varepsilon)^n$$

and hence $\lim_{n\to\infty} \sqrt[n]{n} = 1$. Now therefore also
$$\lim_{n\to\infty} \frac1{\sqrt[n]{n}} = 1.$$

Title: Limit of $\frac{1}{\sqrt[n] n}$


问:
Why is connectedness in the majority of graph theoretical results?
Is there any reason why, for example, in the
theorems about embeddings of graphs, at some point
the authors states that all graphs are connected.

To be more concrete, after prop 3.1, and 3.2 in this paper,
the author says "we shall always assume that graphs are connected."

Why? is this just for simplicity? Or what if we consider
disconnected graphs? Can these graphs also be embedded in surfaces?

答: It is probably just for simplicity.  Many results in graph theory apply to each connected component individually, so connectivity is a common simplifying assumption (without loss of generality).  For example, a graph is $k$-colorable if and only if each component is $k$-colorable.


问:
Where do trigonometric functions belong in the order of operations?
I am wondering, where do trigonometric functions ($\sin, \cos$...) belong in the order of operations?

It is obvious when evaluating $\sin(43+47)$, we add 43 and 47 together to get 90, and sine it to get 1. But if we add some more operations, like this: $2+7(\sin(8+37)+2)-2\cos(30)$, what do we do first?

答:
Trigonometric Functions (And Functions In General) Aren't Considered As Operators, But As Functions Instead, So, Technically Speaking, They Can't Belong In The Order Of Operation (A.K.A. BODMAS/PEDMAS/BIDMAS). BUT, If We Would Count Them As Operators, Then They Would Be Computed In The Very Beginning Of A Equation.

That Is, For Example, If We Have A Equation $(7 + 9)^2/sin(\pi/2) - 2 * 8$, Then We Firstly Compute $sin(\pi/2)$, Which Will Be 1. Then We Compute $(7+9)$ (That's 16) And Square The Result (Which Will Be 256). Now We Compute $256/1$, Which Is Going To Be 256. We Now Multiply 2 By 8, Which Gets Us 16. And, Finally, We Subtract 256 By 16, Giving Us 240.

Summary: The Order Of Operations (Including Functions) Is... Functions. Brackets. Orders. Multiplication And Division. Addition And Subtraction. (Or Simply FBODMAS, Though Some Might Say FPEMDAS Or FBIDMAS Depending On Where You Live.)


问:
Prove that if s is the supremum of $X$, then $z + s$ is the supremum of $X + z$
I am having a bit of trouble trying to solve this problem.

Question: For any $X \subseteq \mathbb{R}$ and $z\in\mathbb{R}$ define $X + z$ to be the set of all $x + z$ where $x\in X$. Prove that if $s$ is the supremum of $X$, then $z + s$ is the supremum of $X + z$

My attempt is that you're given that the supremum, $s$, is the supremum of $X$. Then that should mean that $s \geq x, \forall x \in X$, then that should mean that $z + s \geq x + z, \forall x \in X$.

Any help or tips will be useful!

答:
Let be $\varepsilon>0$. Since $s$ is the supremum of $X$, then there exists $x_n\in X$ such that :
$$s-\varepsilon < x_n \le s$$

Now
$$z+s-\varepsilon < z+x_n \le z+s$$

let $z_n = z+x_n$ and $w=z+s$. We have showed that for all $\varepsilon>0$, there exists a $z_n = z+x_n \in z+X$ such that:
$$w-\varepsilon < z_n \le w$$
therefore $w = z+s$ is the supremum of $z+X$


问:
Multiples of one number in base-$10$
How can I prove that all the natural numbers has one multiple in base-$10$ such that this numbers is written just with zeros and ones?

For example, let $n=3$ then, exists al least one number, the $111$, such that is in base-10 and is written just using zeros and ones, in this case just ones or let $n=5$, in this case exists the $10$, that is multiple of $5$ and is written just using zeros and ones.
I must use the Pigeonhole principle to prove this fact.

答:
Given a number $n$, recall that a number divided by $n$ can have $n$ possible remainders.

Now consider the $n$ numbers
$$1; 11; 111; \cdots; \underbrace{11\ldots1}_{n\,\, 1\text{'s}}$$
 If one of the above leaves a remainder $0$, we are done. If none of them leave a remainder $0$, by pigeonhole principle, since we have $n$ numbers and $n-1$ remainders (recall none of them have a remainder zero), two of them leave the same remainder. Subtract the smaller from the larger to get what you want.

As an example, let us see for $n=6$. Consider the numbers,
$$1; 11; 111; 1111; 11111; 111111$$
Note that none of them leave a remainder $0$.

$1$ leaves a remainder $1$.

$11$ leaves a remainder $5$.

$111$ leaves a remainder $3$.

$1111$ leaves a remainder $1$.

$11111$ leaves a remainder $5$.

$111111$ leaves a remainder $3$.

Since $1$ and $1111$ leave the same remainder, subtract $1$ from $1111$ to get $1110$ and clearly $6 \vert 1110$.

Title: Multiples of one number in base-$10$


问:
Proof of semicontinuity
Given Definition:

Function $f$ on metric space $M$ is called lower semicontinuous if, for each real $a$ the set $\{x \in M: f(x) \leq a\}$ is closed in $M$.

Question:

Prove that $f$ is lower semicontinuous if and only if $f(x)\leq \liminf\limits_{n\rightarrow \infty} f(x_n)$ whenever $x_n\to x$ in $M$.

Hint Given:

For the forward implication, suppose that $x_n\to x$ and $m = \liminf\limits_{n\rightarrow \infty} f(x_n) \lt \infty$.
Then, for every $e>0$, the set $\{t \in M: f(t) \leq m + \epsilon \}$ is closed and contains infinitely many $x_n$.

This is from a Real Analysis book I am trying to read.
I would really like to share my work on this, but I do not seem to understand how to even begin with the proof, using only the definition given.

答:
Suppose that $x_n$ converges to $x$. Let $\epsilon>0$, then the set $G_\epsilon=\{y\in M:\, f(y)>f(x)-\epsilon\}$ is open in $M$. Since, $x_n$ converges to $x$ there is an $m$ such that $x_n\in G_\epsilon$ for every $n\geq m$. In other words,
$$f(x_n)>f(x)-\epsilon$$
for every $n\geq m$. This implies that $\liminf_{n}f(x_n)\geq f(x)-\epsilon$. As $\epsilon>0$ was arbitrary we have $\liminf_nf(x_n)\geq f(x)$. For the converse, suppose that whenever $x_n\to x$ we have $\liminf_{n}f(x_n)\geq f(x)$. We wish to show that the set $$F_\alpha=\{x\in M:\, f(x)\leq \alpha\}$$ is closed in $M$. We will show that the complement $$M\setminus F_\alpha=\{x\in M:\, f(x)>\alpha\}$$ is open. Pick $x\in M\setminus F_\alpha$, then $f(x)>\alpha$. If there is no $\rho>0$ such that the ball centered at $x$ with radius $\rho>0$ belongs to $M\setminus F_\alpha$ then we would be able to find a sequence $x_n\in F_\alpha$ such that $x_n\to x$. Then, since $x_n\in F_\alpha$ means that $f(x_n)\leq \alpha $ for all $n$, which implies $\liminf_n f(x_n)\leq \alpha$, contradicting our hypothesis $\liminf_n f(x_n)\geq f(x)>\alpha$. Hence, there is a $\rho>0$ such that the ball centered at $x$ with radius $\rho$ is contained on $M\setminus F_\alpha$. This means, that $M\setminus F_\alpha$ is open, hence $F_\alpha$ is closed as we wanted.

Title: Proof of semicontinuity


问:
$G_2$ as the group of Isometries of a Projective Space
It seems like in the classification of simple complex lie algebras, every lie algebra corresponds to the group of isometries of a projective space. SO(n+1) is the group of isometries on $RP^n$, SU(n+1) is the isometries of $CP^n$, and SP(n+1) is the isometries of $HP^n$.

John Baez explains in his course  on the octonions that the exceptional lie groups are the isometries groups for projective spaces built out of the octonions, as seen in the Magic Square of Lie Algebras1

$G_2$ is the only exceptional lie group left out of this description, and is usually described as the group of automorphisms of the Octonians, which is nice, but following the pattern it seems it should be the group of isometries of some manifold as well. Is it known what this manifold would be?

答:
Too long for a comment, but not a full answer:

There is a famous realization as $G_2$ as the symmetry group of 'a ball rolling over another ball with 3 times its radius'.

I don't really know what that means, but whenever you invent a sensible parametrization of all possible configurations of the two balls it is not hard to convince yourself that his thing has the structure of a manifold. Perhaps this manifold is the thing that has $G_2$ symmetry. On the otherhand, this is just two balls touching. If somehow the notion of rolling plays a more serious role it is less obvious if and how the story can be reformulated as a manifold.

But a good starting point would be to google '$G_2$ rolling ball' or similar and see what that turns up.

EDIT: this quote from Wikipedia (the page on $G_2$) clafifies it quite a lot:

In 1893, Élie Cartan published a note describing an open set in $\mathbb{C}^5$ equipped with a 2-dimensional distribution—that is, a smoothly varying field of 2-dimensional subspaces of the tangent space—for which the Lie algebra $\mathfrak{g}_{2}$ appears as the infinitesimal symmetries.[2] In the same year, in the same journal, Engel noticed the same thing. Later it was discovered that the 2-dimensional distribution is closely related to a ball rolling on another ball. The space of configurations of the rolling ball is 5-dimensional, with a 2-dimensional distribution that describes motions of the ball where it rolls without slipping or twisting.


问:
Rotate a shape 360 degrees on one axis and not be the same as the starting shape?
Are there shapes in nth dimensions (in euclidian geometry), that can be rotated 360 degrees on one axis and have more than one point not in the same place?

Alternatively, in non-euclidian geometry, are there any objects or shapes that can be rotated the full rotation of a closed circle in the relative geometry that fulfil the same properties? (For example, in a non-euclidian plane where 360 degrees is not enough for a full rotation, it would be rotated a full rotation instead.)

答:
Very untechnical answer here. Sorry but its late and I am tired.
I am pretty sure that a 'full' rotation of any shape would be akin to the identity operator. unless the shape undergoes some form of morphing within the rotation then a full rotation would return it to its normal state.
however, if my initial instinct on this is incorrect I would love to know!</p>


问:
Why is $x^4-3x^2+18$ irreducible over the $3$-adics?
Let $f = x^4 - 3x^2 + 18 \in \mathbb{Q}_3[x]$. Since there is an LMFDB page of an extension defined by this polynomial, I assume that $f$ is irreducible. Could you verify if this is true and also why that is (not) the case?

It is not an Eisenstein polynomial (as $3^2$ divides $18$, the constant coefficient of $f$). I also tried the substitution $y = x^2$ and asked myself if $g = y^2 - 3y + 18$ is irreducible. Its reduction mod $3$ is $y^2$ which is not irreducible, so I cannot say whether $g$ is irreducible or not.

答:
As others have explained $f(x)$ has no zeros in $\Bbb{Q}_3$ because $x^2-3x+18$ doesn't have any. Therefore the remaining possibility is that $f(x)=g(x)h(x)$ is the product of two irreducible monic quadratics, $g(x),h(x)\in\Bbb{Q}_3[x]$.

For another way to a contradiction consider the following. The polynomial $f(x)$ is even. Implying that if $g(x)\mid f(x)$ then also $g(-x)\mid f(-x)=f(x)$. In other words, $g(-x)$ is also an irreducible monic factor of $f$. The same applies to $h(-x)$ as well. We have two possibilities:

If $g(-x)=g(x)$ and $h(-x)=h(x)$, then $g(x)$ and $h(x)$ are both even. That is, $g(x)=x^2-a, h(x)= x^2-b, a,b\in\Bbb{Q}_3$. Then $a$ and $b$ would be zeros of $x^2-3x+18$, which is absurd.

If $g(-x)=h(x)$ (when automatically also $h(-x)=g(x)$) then we run into the following problem. If $g(x)=x^2+a_1x+a_2$, then $g(-x)=x^2-a_1x+a_2$, and
$$f(x)=g(x)g(-x)=x^4+\cdots+a_2^2.$$
So $18=a_2^2$. But this is impossible, because $18=2\cdot3^2$, and there is no $\sqrt2$ in $\Bbb{Q}_3$.

No factorization exists, so $f$ is irreducible.


问:
Surjective homomorphism from direct sum $X\oplus Y$ to $X$
Suppose $X$, $Y$ are two abelian groups, and we have a surjective homomorphism $f$ from the direct sum $X\oplus Y$ to $X$, is it always true that $Y\cong \ker(f)$ ?

Thanks!

答:
No. Take $X = \mathbb{Z}_2$ and $Y = \mathbb{Z}_4$. Define $$f:\mathbb{Z}_2\oplus \mathbb{Z}_4 \to \mathbb{Z}_2: (a,b) \mapsto b \mod 2$$
Then $f$ is clearly surjective but
$$\ker(f) = \{(0,0),(0,2),(1,0),(1,2)\} \cong \mathbb{Z}_2 \times \mathbb{Z}_2 \ncong \mathbb{Z}_4.$$


问:
Meaning of this proportionality
I'm having understanding the maths part of a certain chemistry concept. There's a formula that states:

$$\frac{A}{B}\sim v^{-3}.$$

From this I can say that as v gets bigger, the right side gets smaller, and because the two sides are proportional, the left side gets smaller as well. This happens because B gets bigger and A gets smaller.

Is all this correct?

答:
The first concept is correct: as $v$ increases, the RHS decreases and thus the LHS must decrease as well.

However, how that decrease happens is not quite what you describe. Either $A$ must decrease or $B$ must increase. Either of those is sufficient.

Title: Meaning of this proportionality


问:
Is this a correct natural deduction proof?
Prove $ A \rightarrow B \vdash \neg (A \wedge \neg B)$

$A \rightarrow B \quad\quad\quad\quad$ Premise

$(A \wedge \neg B) \rightarrow B \quad \rightarrow $I, subcomputation below

$\quad\quad$ 2.1 $ A \wedge \neg B \quad $ Assumption

$\quad\quad$ 2.2 $ A \quad\quad\quad$ (2.1), $\wedge$E

$\quad\quad$ 2.3 $ B \quad\quad\quad$ (2.2)(1), $\rightarrow$E

$(A \wedge \neg B) \rightarrow \neg B \quad \rightarrow$I, subcomputation below

$\quad\quad$ 3.1 $A \wedge \neg B \quad$ Assumption

$\quad\quad$ 3.2 $\neg B \quad\quad\space\space$ (3.1), $\wedge$E

$\neg (A \wedge \neg B) \quad\quad\space\space$ (2)(3), $\neg$I

答:
For the inference system used in the proof, the answer is correct.

Please see @F. Zer answer for a proof using the Fitch Natural Deduction system.


问:
Random Walks with the equality 1/2
I have recently come across this probability question, but I don't have a clear idea of how to proceed with it. the question is as follows:

Consider a random walk on the integers starting at and with a probability of moving in either direction being $\frac {1}{2}$. What is the approximate probability of the walk being at a point in the interval $[-20,20]$ after 1000 moves?

答:
Let each step of the walk be given as $2 \times X_i - 1$, where $X_i \sim Bernoulli(0.5)$. So your position after $n$ steps is $\sum_{i = 0}^n (2 \times X_i - 1) = 2 \times \sum_{i = 0}^n X_i - n$.

So the probability of being in the range $[a, b]$ is $P(a \leq 2 \sum X_i - n \leq b) = P(\frac{a + n}{2} \leq \sum X_i \leq \frac{b + n}{2})$. That means we just have to do something with the distribution of a sum of Bernoulli variables, which hopefully you know something about?

Title: Random Walks with the equality 1/2


答:
Being inside the interval $[-20,20]$ in $1000$ moves requires you having at most $510$ steps to the right and at least $490$. It is the same question as saying if you toss $1000$ coins what is the probability of $490 \leq H \leq 510 $ This is clearly $\sum\limits_{i=490}^{510} 1000$ choose $i \cdot \frac{1}{2^{1000}} \approx 0.493$

Alternatively you could have modelled the number of heads as a Normal Distributed R.V with mean $500$ and variance  $\sqrt{1000\cdot\frac{1}{2}\cdot\frac{1}{2}}^2 = \sqrt{250}^2 \approx 15.813^2$ And our condition is that we must be within $\frac{10}{15.813} \approx 0.63 $ standard deviations of the mean which a simple integral yields to be approximately 0.473

Title: Random Walks with the equality 1/2

Body:
I have recently come across this probability question, but I don't have a clear idea of how to proceed with it. the question is as follows:

Consider a random walk on the integers starting at and with a probability of moving in either direction being $\frac {1}{2}$. What is the approximate probability of the walk being at a point in the interval $[-20,20]$ after 1000 moves?


答:
The short answer is no, in euclidean space. However, i do not know about non euclidean space.

First of all, what is a rotation in higher dimensions? In 2 dimensions rotation is simple, we just move a point while keeping its distance to some other point fixed. This is simple because we can describe the rotation by a single number (the angle)

In 3 dimensions we have 2 different ways to generalise this. one way is we can hold the position fixed relative to all points on some line. If that line is an axis, then this is equivalent to holding 1 coordinate fixed, while changing the other two coordinates without changing their distance from the origin. This is also simple and can be described by a single number, again the angle.

However, there is a different way, instead we could just move a point while keeping its distance relative to another point fixed. (you may think about this as an object orbiting another object). This type of generalization of rotation cannot be described just by a single number, you need at least 2 numbers to describe it.

Because of this we consider the first way to be the usual way to generalise rotation, in 3 dimensions. However, the thing which gets generalised is not that we fixed a line, instead its that we fixed n-2 dimensions. What I mean is that in 4 dimensions for example, rotation around an axis, would be analogous to rotation around a point in 3 dimensions. To get the usual notion of rotation which can be described by an angle, we need to fix a plane, or a pair of axes. In general, in $\mathbb{R}^n$ rotation occurs around an $n-2$ dimensional shape. If you want this to be rotation about some axes, then this is equivalent to fixing $n-2$ coordinates, and then altering the remaining 2 coordinates while keeping their distance from the origin fixed.

One way to look at it is what happens to a single point of the shape. Since in general a single point of some shape will just be some point in $x\in\mathbb{R}^n,$ we can consider what happens when $x$ is rotated 360 degrees. if $x=(x_1,x_2,...,x_n)$ then we can rotate $x$ by choosing $n-2$ of the values to hold fixed, and then changing the other 2 coordinates. For example, we may choose to hold $x_3,x_4,...,x_n$ fixed, and change $x_1$ and $x_2$.

So we choose $x'=(x_1',x_2',x_3,...,x_n)$ where $x_1'^2+x_2'^2=x_1^2+x_2^2$. What is the angle between $x$ and $x'$?
One way to do this might be to forget the $n-2$ fixed coordinates, and pretend like we are working in the plane. Alternatively there is a way to use cosine law to define angles in $\mathbb{R}^n$. I will leave it to you to confirm that if the angle between $x$ and $x'$ is 360, then $x=x'$.

Title: Rotate a shape 360 degrees on one axis and not be the same as the starting shape?

Body:
Are there shapes in nth dimensions (in euclidian geometry), that can be rotated 360 degrees on one axis and have more than one point not in the same place?

Alternatively, in non-euclidian geometry, are there any objects or shapes that can be rotated the full rotation of a closed circle in the relative geometry that fulfil the same properties? (For example, in a non-euclidian plane where 360 degrees is not enough for a full rotation, it would be rotated a full rotation instead.)


问:
$\mathbb{P}^n_k$ is irreducible as a scheme
How do I show that $\mathbb{P}^n_k$ is irreducible as a scheme? I am still quite confused with the definition by gluing affine schemes. I tried to show that nonempty open sets intersect, but got lost.

答:
Actually, it’s not a scheme question, it really is a topological one.

There are open subsets $U_0,\ldots,U_n$, all homeomorphic and irreducible (they’re the $D(X_i) \cong \mathbb{A}^n_k$) with nonempty global intersection $V$ such that they cover $\mathbb{P}^n_k$.

Let $A,B \subset \mathbb{P}^n_k$ be nonempty open subsets.

Say, $A’=A \cap U_i \neq \emptyset$. Then $A’$ is a nonempty open subset of $U_i$ which is irreducible; moreover, $V \subset U_i$ is a nonempty open subset so $V \cap A’=V \cap A$ is nonempty.

Let $j$ be such that $B’’=B \cap U_j$ is nonempty. Let $A’’ = A \cap U_j \supset A \cap V$. Then $B’’, A’’$ are both nonempty open subsets of $U_j$ so they must meet; as $A \cap B \supset A’’ \cap B’’$, $A$ and $B$ meet and we are done.


问:
Do the Hausdorff quotient and completely regular modification functors converge?
Fix a space $X$. Below we will introduce a sequence of spaces associated to it. I will understand the terms regular and completely regular to not include the $T_1$ axiom, and each subcategory I introduce will be full and replete.

Firstly denote by $hX$ the maximal Hausdorff quotient of $X$. This is a quotient space of $X$ with the property that any map $f:X\rightarrow Y$ from $X$ into a Hausdorff space factors uniquely through a map $f':hX\rightarrow Y$. I'll link those interested in a definition to this post. In any case, the assignment $X\mapsto hX$ is functorial and defines a functor $Top\rightarrow Top_2$ from the category of all topological spaces into the category of Hausdorff spaces.

Secondly we will write $crX$ for the completely regular modification of $X$. To define it notice that the cozero sets in $X$ form a base for a topology on the underlying set which is weaker than $X$'s existing topology. Then $crX$ is the underlying set of $X$ equipped with this new topology. The identity induces a continuous map $X\rightarrow crX$, and any map $f:X\rightarrow Y$ from $X$ into a completely regular space $Y$ factors uniquely through a map $f'':crX\rightarrow Y$. Again this gives a functor $Top\rightarrow Top_{CR}$, $X\mapsto crX$, now into the category $Top_{CR}$ of completely regular spaces.

Notice that $crX$ is Hausdorff if and only if $X$ is completely Hausdorff. In general $crX$ will not be Hausdorff, even if $X$ itself is. Similarly $hX$, although Hausdorff, need not be completely regular. Thus we are led to consider the spaces $h(crX)$ and $cr(hX)$. Now the first of these spaces need not be completely regular, and the second need not be Hausdorff, so we introduce the spaces $cr(h(crX))$ and $h(cr(hX))$. Continuing on we obtain a potentially infinite sequence of spaces, obtained by alternative application of the functors $h$ and $cr$. The sequence will terminate exactly when we apply $h$ to a Hausdorff space, or $cr$ to a completely regular space.

Do these sequences necessarily converge to completely regular Hausdorff spaces?

I'm guessing that they do not. For instance, if we replace $h$ with the k-ification functor, which replaces $X$ with its compactly generated reflection $kX$, then it is know that there is a completely regular space $Y$ and a k-space $Z$ for which $kY=Z$ and $crZ=Y$. On the other hand I have no counterexample to my question above.

Note: $X$ always has its completely regular Hausdorff, aka Tychonoff, modification $tX$, which is the image of the canonical map $X\rightarrow I^{C(X,I)}$. Although $tX$ has a universal property with respect to Tychonoff spaces, this is not the space I am looking for. I am interested in the sequence I construct above.

答:
In fact, $h(crX)$ is always completely regular and is the same as $tX$.  To see this, note that $crX$ is just the coarsest topology on $X$ that makes the canonical map $X\to I^{C(X,I)}$ continuous.  Since the image of this map is $tX$, the induced map $crX\to tX$ is a surjection with the property that the domain has the coarsest topology that makes it continuous.  In other words, this means that points of $X$ which map to the same point of $tX$ are topologically indistinguishable in $crX$, and so $crX\to tX$ is just the $T_0$-ification of $crX$.  Since $tX$ is in fact not just $T_0$ but Hausdorff, $crX\to tX$ is also the Hausdorffification of $crX$.

(To put it another way, what's going on here is that completely regular spaces are very close to being the same as Tychonoff spaces--they are just the spaces whose $T_0$-ification is Tychonoff.)


问:
Which is the correct translation of "Two rivers cannot flow into each other."

$R(x)$ - "x is a river"

$L(x)$ - "x is a lake"

$S(x)$ - "x is a sea"

$F(x, y)$ - "x flows into y"

The domain consists only of waterbodies (rivers, lakes and seas).

"Two rivers cannot flow into each other."

(1) $ \forall x \forall y (R(x) \wedge R(y) \rightarrow \neg F(x, y) \wedge \neg F(y, x))$

(2) $ \forall x \forall y (R(x) \wedge R(y) \rightarrow \neg (F(x, y) \wedge F(y, x)))$

I believe the answer to be number 1, but number 2 is proposed to be the correct answer.

Is the natural language sentence ambiguous and can be translated in either way?

答: To me, "two rivers cannot flow into each other" means that river A could flow into river B, or river B could flow into river A, but not both.  That is what the symbolic expression (2) means.  The symbolic expression (1) means that no river can flow into another (A cannot flow into B, and B cannot flow into A).</p>


问:
Reference for the Construction of Brownian Motion
A common method for constructing Brownian motion is referred to as the
Levy construction, the Levy-Ciesielski construction, the Ciesielski
construction and sometimes seems to be attributed to Wiener (1923). At
least in the book, Diffusions, Markov Processes and Martingales by
Rogers and Williams, I can find a reference for Ciesielski:

```<code>@article{Ciesielski61,
 author = {Z. Ciesielski},
 title = {Holder condition for realization of {G}aussian processes},
 journal = tams,
 volume={99},
 year = 1961,
 pages={403--413}
}
</code>```

Can someone point me at the references for Levy and Wiener? Or perhaps
even better there is an article with a short history of the
construction of Brownian motion?

答:
The reference for Lévy is:

Lévy, M. Paul. “Le Mouvement Brownien Plan.” American Journal of Mathematics, vol. 62, no. 1, 1940, pp. 487–550. JSTOR, www.jstor.org/stable/2371467. Accessed 24 Nov. 2020.


问:
Counterexample to upper continuity
Let $M$ be a $\sigma$-algebra of subsets of a set $X$ and let $\mu:M\rightarrow[0,\infty)$ be a finitely additive set function.  I'm trying to decide if it's automatically true that for all ascending chains $\{A_k\}$ in $M$:

$$\mu\big(\bigcup_{k=1}^{\infty}A_k\big)=\lim_{k\rightarrow\infty}\mu(A_k)$$

I mean we clearly have $\mu\big(\bigcup_{k=1}^{n}A_k\big)=\mu(A_n)$.  These are two identical sequences of real numbers, how can their limits be different? Thus I can see no way for the above not to be true, it doesn't even require finite additivity.  But the above statement along with finite additivity implies that $\mu$ is a measure, which would then force one to conclude that finite additivity implies countable additivity, which I don't think is supposed to be true; although the only counterexample to this I could find was one which involved ultrafilters, and don't be bringin' those ultrafilters round here boy, or we're gonna have strong words.

答:
Certainly $\mu(\cup_{k=1}^n A_k) = \mu(A_n)$  because $\cup_{k=1}^n A_k = A_n$.  This is true for any set function $\mu$.

This question features a countably additive set-function into $[0, \infty]$ which is not upper continuous.  Consider the measure space $(\mathbb{N}, 2^\mathbb{N},\mu)$ where $\mu$ is the counting measure.  Let $A_n = \{k \in \mathbb{N}: k \geq n\}$.  Then $\bigcap_{1}^\infty A_n = \emptyset$ so that $\mu(\bigcap_1^\infty A_n) = 0$ while $\mu(A_n) = \infty$ for any $n$.

Title: Counterexample to upper continuity


问:
Partial order and total order
Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$. Define a relation $L$ on $A×B$ as follows: $L=\{((a,b),(a',b'))\in (A×B)×(A× B) \mid aRa', \text{and if } a=a' \text{ then } bSb'\}$. To show that $L$ is a partial order on $A×B$.

I am okay with proving that $L$ is reflexive and antisymmetric on $A×B$. How do you prove that $L$ is transitive on $A×B$? Also if $R$ and $S$ are total orders, will $L$ be also a total order? If it is, how do you prove it?

答:
This is an old inactive question. But I will answer just to remove it from unanswered category.

In general, say, $A$ and $B$ are two sets equip with two binary operations $R$ and $S.$ If both $R, S$ are reflexive, irreflexive, symmetric, antisymmetric, transitive, or antitransitivity then so does the product binary operation (typically denoted by $R\times S$ ) on $A\times B$ defined as $(a,b)(R\times S)(a',b')$ iff $aRa'$ and $bSb'.$
In other words, Cartesian product preserve both equivalence relations and partial orderings (but not total relations, in general). However here you are given the not the product ordering, but the lexicographical order, which is a total ordering.

For your first question, suppose  $(a,b)L(a',b')$ and $(a',b')L(a'',b''),$ then we have following four cases:

$aRa'$ and $a'Ra''$ which implies $aRa''$ and hence $(a,b)L(a'',b'').$

$a=a', bSb'$ and $a'Ra''$  ...

$aRa'$ and $a'=a'', b'Sb''$ ...

$a=a', bSb'$ and $a'=a'', b'Sb''$ ...

Now carefully apply the transitivity of both $R$ and $S$ to obtain the conclusion in the remaining cases.

For your second question, lets take any $(a,b), (a',b')\in A\times B.$ Assuming the totality of $R$ and $S$ we have either $aRa'$ or $a'Ra$ or $a=a'.$ The result is true in first two cases, and in the last (equality) case use the totality of $S.$ There we have either $bSb'$ or $b'Sb$ or $b=b',$ hence finally we have $(a,b)L(a',b')$ or $(a',b')L(a,b)$ or $(a,b)=(a',b').$

Title: Partial order and total order


问:
Proof that a function is surjective
Prove that the binary function is not surjective in the variable $x_{3}$.

$f(x_{1},x_{2},x_{3})=\overline{x_{1}}$, where $\{x_{1},x_{2},x_{3}\}\in X=\{0,1\}$

Please, answer in detail!

I tried to do this, but I don't really understand what it gives to solve the problem.

答:
I understand 'surjective in one variable' in the following sense:

If you fixate $x_1$ and $x_2$ you'll get a map $$f_{x_1,x_2}:X\to X: x \mapsto f(x_1,x_2,x)$$
Now $f$ is called surjective in $x_3$ if there are $x_1$ and $x_2$ so that the map $f_{x_1,x_2}$ is surjective.

If that's what you mean by 'surjective in one variable' we need to show the opposite. That there are no $x_1$ and $x_2$ such that $f_{x_1,x_2}$ is surjective. This is easy by looking at the given table (the choices of $x_1$ and $x_2$ won't matter since you are only varying $x_3$ but the map $f$ only depends on $x_1$).

Title: Proof that a function is surjective


问:
Obtaining $\mathbb{Z}_2$ from an arbitrary group
Given an arbitrary group $G$ (which may even be trivial), is there any (canonical) way to obtain the two-element group $\mathbb{Z}_2$ from $G$ by performing various operations on $G$, e.g. taking subgroups, (amalgamated) free products, (semi)direct products, quotient groups, etc.?

答: I'm not sure that this what you are looking for,  but every group $G$ can be "extended" to a supergroup $\tilde G$ such that $G\le \tilde G$, $[\tilde G:G]=2$ and $\tilde G\cong G\times \Bbb Z_2$. The construction is given here.


问:
Checking proof that $\sum(-1)^n\frac{1}{\sqrt n}$ converges
I am trying to show (or disprove) that the series $\sum(-1)^n\frac{1}{\sqrt n}$ converges. I tried using the root test, namely, showing that the $$\limsup_{n\rightarrow \infty}(|(-1)^n\frac{1}{\sqrt n}|)^{\frac{1}{n}}=\limsup\limits_{n\rightarrow \infty}(\frac{1}{\sqrt n})^{\frac{1}{n}}=\limsup\limits_{n\rightarrow \infty}(\frac{1}{n^{\frac{1}{2n}}})<1$$ This seems clear, as for all $n>1$, $n^{\frac{1}{2n}}>1$.

Is my proof correct?

答:
No, it isn't correct. The limsup is equal to $1$ here, not less than $1$. Anyway, $\sum_{n=1}^\infty \frac{1}{\sqrt{n}}$ is a well known divergent series, so there is no way the root test would be able to help you prove convergence here. The series is not absolutely convergent.

The convergence of the original series $\sum_{n=1}^\infty (-1)^n\frac{1}{\sqrt{n}}$ follows directly from Leibniz test.


问:
Condition for an element in Ext be zero
Consider an abelian category $\mathcal{A}$ and two objects $A,B$ of $\mathcal{A}$. It is straightforward that an element $\eta \in \text{Ext}^{1}(A,B)$ of the form $0 \to B \xrightarrow{f} X \xrightarrow{g} A \to 0$ is zero in $\text{Ext}^{1}(A,B)$ if and only if $g$ has a right inverse, which is equivalent to say that $f$ has a left inverse.

Question: If we take $n > 1$ and consider an element $\eta \in \text{Ext}^{n}(A,B)$ of the form $0 \to B \xrightarrow{f} X_{n} \to \cdots \to X_{1} \xrightarrow{g} A \to 0$, is it true that $\eta$ is zero $\text{Ext}^{n}(A,B)$ if and only if $g$ has a right inverse (or $f$ has a left inverse)?

答:
No. For example, consider the exact sequence
$$0\to\mathbb{Z}/2\mathbb{Z}\xrightarrow{\times2}\mathbb{Z}/4\mathbb{Z}\xrightarrow{\times2}\mathbb{Z}/4\mathbb{Z}\xrightarrow{\times1}\mathbb{Z}/2\mathbb{Z}\to0$$
of abelian groups.

Title: Condition for an element in Ext be zero


问:
A question related to $S^{\perp}$ and closure of span of $S$
This question was asked in my linear algebra quiz previous year exam and I was unable to solve it.

Let V be an inner ( in question it's written integer , but i think he means inner) product space and S be a subset of V. Let $\bar S$denote the closure of S in V with respect to topology induced by the metric given by inner product. Which of the following statements are  true?

A $ S $=$ (S^{\bot})^{\bot}$

B $ \overline S$= $(S^{\perp})^{\perp}$

C $\overline {\text{span}(S)}$=$(S^{\bot})^{\bot}$

D $ S^{\bot} $=$ ((S^{\bot})^{\bot})^{\bot}$

I was completely blank on how can I approach this problem although I have studied linear algebra carefully. Can you please tell on how I should approach the problem .

Edit : I tried It again . I marked A ,D but answer is C,D. If A is false I don't see why D must be true. So, I think I am missing some concepts.

答:
Recall that $S^\perp$ is defined as the set of all vectors in $V$ which are orthogonal to every vector in $S$.

In case $S$ is a
singleton, say $S=\{s\}$, then we have
$$
  S^\perp = \{x\in  V: \langle x, s\rangle =0\},
  $$
so   $S^\perp$ coincides with the null space of the continuous linear functional
$$
  x\in  V \mapsto  \langle x, s\rangle ,
  $$
and for that reason   $S^\perp$ is obviously a CLS (closed linear subspace).

For a general set $S$, one clearly has that
$$
  S^\perp = \bigcap_{x\in  S} \{s\}^\perp,
  $$
so $S^\perp$ is the intersection of a family of CLS's, and hence itself a CLS.

Notice that the right-hand-side of (A), (B), (C) and (D) all refer to the "perp" of something, so are all CLS's.

Since the left-hand-side of (A) and (B) may or may not represent a CLS, then they can't always be true.

Point (C) is true.  To see why,  first notice that
$$
  S\subseteq (S^\perp)^\perp
  \tag 1
  $$
for a pretty elementary reason (which
nevertheless sounds a bit like a tongue-twister):  every  vector in  $S$ is  orthogonal to anything that is orthogonal to every vector in $S$.

We then see that (1) states that $S$ is contained in a CLS, and since $\overline{\text{span}}(S)$ is the smallest CLS
containing $S$, it follows that
$$
  \overline{\text{span}}(S)\subseteq (S^\perp)^\perp
  $$

To prove the converse inclusion,  pick any vector  $x$ in  $(S^\perp)^\perp$.
A well known result about Hilbert spaces (which requires that $V$ be complete,  and hence  we need to assume it here)
states that $x$ may be written as
$$
  x=u+v,
  $$
where $u$ is perpendicular to $\overline{\text{span}}(S)$, and $v$ velongs to $\overline{\text{span}}(S)$.

Notice that, in particular,  $u$ is perpendicular to every vector of $S$, and hence $u\in  S^\perp$.

On the other hand,
since both $x$ and $v$ lie in $(S^\perp)^\perp$,  we conclude that $u=x-v\in (S^\perp)^\perp$.

This implies that $u\in  (S^\perp)^\perp \cap  S^\perp$,  so $u$ is perpendicular to itself,  whence $u=0$ and then
$$
  x = u+v = v\in  \overline{\text{span}}(S).
  $$
This concludes the proof of (C).

Regarding point (D) it is true even if $V$ is not complete.  It is a consequence of  the following  much more general result:

Lemma.  Let $V$ be any set (e.g. the inner-product space of interest here) and let $\lozenge$ be a symmetric relation on $V$
(e.g. $x\mathrel{\lozenge} y \Leftrightarrow x\perp y$).  For each subset $S\subseteq V$ define
$$
  S^\lozenge = \{x\in V: x\mathrel{\lozenge} s, \text{ for all $s$ in S} \}.
  $$
Then
$$
  S^\lozenge = ((S^\lozenge)^\lozenge)^\lozenge,
  $$
for any $S$.

Proof.  The tongue-twister above immediately implies that
$$
  S\subseteq (S^\lozenge)^\lozenge.
  \tag 2
  $$
Plugging in  $S^\lozenge$ in
place of $S$ in (2), we get $S^\lozenge \subseteq  ((S^\lozenge)^\lozenge)^\lozenge$.

Next observe that
$$
  S_1\subseteq S_2 \Rightarrow   S_2^\lozenge\subseteq S_1^\lozenge,
  $$
and if this is applied to (2), we get
$
  ((S^\lozenge)^\lozenge)^\lozenge\subseteq   S^\lozenge.
  $
QED

An interesting Corollary,  in a totally distinct area of Math is:

Corollary.   Given a ring $R$ and any subset $S\subseteq R$,  define the commutant of $S$, denoted $S'$, to be the set formed by
the elements of $R$
which commute with every element of $S$.    Then $S'''=S'$.


问:
Expected number of trials for event X to happen for the first time vs number of trials after which the expected number of times X happens is 1.
Are these two quantities always the same? Can anyone provide a proof/explanation or counter-example?

As an example, let a trial consist choosing a number from the set {1,2,...,n}, and let event X be that a number is chosen that has been chosen before (a duplicate). Is it true that the expected number of picks for the first duplicate to occur, is the same as the number of picks whereby the expected number of duplicates after this number of picks is 1?

My intuition is that they are the same, and I hope this isn't a daft question.

Many thanks,

t-tough

edit:

Counterexample! Suppose buses always turn up on the hour and suppose exactly half the buses all turn up together at 4pm, and the other half all turn up together at 6pm, but this partition is done at random. Consider the event that bus X turns up. Then the expected number of hours after noon for bus X to turn up for the first time is 5. But at 5pm the expected number of times that bus X has turned up is $\frac{1}{2}$.

答:
What you are asking is a fairly deep question! There is something called the "Markov property" which you should look into if you are really interested. I have taken this question to ask if expected value is "memoryless" as in it the time you must wait for the first time $X$ to happen is the time you must wait for it to happen again after it has happened. I.E if you are waiting for busses and you arrive just after one bus has left is this the same wait you would have had to endure if you arrived just after the second bus leaves?

Anyways the answer is: $\textbf{"It depends on the distribution"}$ I can think of lots of examples where it is yes and lots where it is no. Lets explore some together:

$\textbf{Yes:}$

You toss a fair coin until you get a head.

An ant, who starts at the bottom left corner, walks randomly on the 6 sides of hexagon until it reaches its starting corner.

You play poker until you are dealt pocket aces (a pair of aces when you are given only 2 cards).

You wait on train until someone whose name starts with Z comes onboard.

You generate numbers randomly from $1-100$ until you get a prime.

$\textbf{No:}$

You toss coins until the sequence "HHH" appears

An ant, who starts at the bottom left corner, walks randomly on the 6 sides of hexagon until it reaches the corner diagonally opposite

You deal cards (without replacement from a standard deck) until you get an Ace

You wait on train until you meet a teenager.

You generate numbers randomly from $1-100$ until you get a prime but delete every even number and keep every odd number you have generated.

Now let us examine them: In the yes pile numbers $1,3,4,5$ all are examples such that when we succeed we have not effected our chances of future success. I.E tossing a  head makes another head no more or less likely. Or when we are dealt aces in one hand then the next time the cards are shuffled and re-dealt we are just as likely to get aces. Example 2 is a little different and fun because it effectively is an example of when the game "restarts" i.e once the ant is at the bottom corner the game begins again and it wanders until it has reached the bottom corner.

In the no pile we see that success might impair future sucess. For example in 4) we might note that teenagers tend to come in groups and as such if we see 1 teenager we might be more likely to see another one very quickly, his brother, classmate or friend might be with him and as such seeing a child might make it more likely to see another one quickly and as such reduce the expected waiting time.  In example 1) we can note that once we have tossed "HHH" we need only toss 1 more head for another run of "HHH" and as such tossing 3 heads in a row makes it easier and quicker to toss another "3 Heads", in reality yes this is simply the last two heads and one more but note that the sequence "HHHH" has 2 different runs of 3 heads. I will leave you to think about why in  2) 3) and 5) success either makes future success more or less likely to happen and as such effects the expected value.


问:
Does the following graph have a Hamilton circuit?

A Hamilton circuit (or path) is a path that visits each vertex exactly once (except the start/end point) and ends at the starting point.

I've stared at this for quite a while and cannot find a Hamilton circuit yet my guide says that one exists. Where is the path?


问:
$\nabla^2f(x)>0$ is a necessary or sufficient condition of the Newton direction $s=-[\nabla^2f(x)]^{-1}\nabla f(x)$ to be a descent direction?
Let $f: \mathbb{R}^N \rightarrow \mathbb{R}$. The Newton direction $s=-[\nabla^2f(x)]^{-1}\nabla f(x)$ a descent direction if:

$\nabla f(x)^Ts<0 \implies -\nabla f(x)^T[\nabla^2f(x)]^{-1}\nabla f(x)<0 $

$\quad\quad\quad\quad\quad\quad\implies \nabla f(x)^T[\nabla^2f(x)]^{-1}\nabla f(x)>0$

$\quad\quad\quad\quad\quad\quad\implies [\nabla^2f(x)]^{-1} $ must be positive definite.

We know that the inverse of a matrix positive definite is also positive definite.

My question is: $\nabla^2f(x)>0$ is a necessary or sufficient condition? and why?

Thanks in advance for any help!

答:
Locally, you have:
$$f(x) \approx f(c) + \nabla f(c)^T(x-c) + 0.5(x-c)^T\nabla^2f(c)(x-c)$$
If you move from $c$ to $c-[\nabla^2f(c)]^{-1}\nabla f(c)$, the objective function changes from $f(c)$ to:
$$f\left(c-[\nabla^2f(c)]^{-1}\nabla f(c)\right) \approx f(c) - 0.5 \nabla f(c)^T [\nabla^2f(c)]^{-1}\nabla f(c).$$
The final term is negative, because if $\nabla^2f(c)$ is positive definite, then so is its inverse. So, if the local approximation is valid, there is a reduction in function value.

If the step size is large, the local approximation is not valid, and it is possible that the new iterate has a higher function value. To circumvent that, many algorithms do not take a full Newton step, but a damped step where the new iterate is $c-\alpha[\nabla^2f(c)]^{-1}\nabla f(c)$ for some parameter $0<\alpha\leq 1$. The process of finding $\alpha$ is called line search.


问:
Important results about/requiring multigraphs
Why are multigraphs important?  The wikipedia article on multigraphs mentions several different definitions but does not mention key results about multigraphs. So my question can have several levels of answers:

Are there any interesting/deep results that hold for multigraph?

Are multigraphs required for proving some important results?
E.g. from my internet searches I got the feeling that they featured in the proof of the 4-color theorem, but I am not entirely certain of this fact.

Are multigraphs unavoidable in some contexts? E.g. the dual graph of a planar graph might end up being a multigraph.

Are there any books/papers that focus on multigraphs and might answer the above questions?

答:
I don't know of any book that specifically focuses on multigraphs. However, Diestel writes the following in his book:

Somewhat surprisingly, proving a graph theorem more generally for multigraphs may, on occasion, simplify the proof. Moreover, there are areas in graph theory (such as plane duality; see Chapters 4.6 and 6.5) where multigraphs arise more naturally than graphs, and where any  restriction  to  the latter  would  seem artifcial  and  be  technically complicated.

(I confess I haven't searched the book for examples of proofs simplified by using multigraphs.)

One reason to consider multigraphs has to do with matroid theory. Parallel edges and loops have natural analogues in matroids, and in this setting it is often natural to allow these, primarily because there are various matroid operations (most notably, taking duals and minors) under which the class of simple matroids is not closed. Thus, in "matroidal" areas of graph theory (such as plane duality and the theory of graph minors) multigraphs often appear naturally.

As for interesting results about multigraphs, the first one that comes to my mind is the Nash-Williams theorem, which characterizes multigraphs that contain $k$ disjoint spanning trees. The fact that this result works for multigraphs has fun applications for simple graphs as well. For example, we can decide whether a graph contains three spanning trees such that each edge is used by at most two of the trees simply by doubling each edge and checking if the resulting multigraph contains three edge-disjoint spanning trees.


问:
Without solving explicitly show that for the IVP $x'=x^{3}-x,x(0)=0.5$ the solution converges to $0$ for $t\rightarrow\infty$
I am trying to determine whether the solution to the following IVP converges to $0$ for $t\rightarrow\infty$. The IVP is $x'(t)=x^{3}-x=f(x)$,$x(0)=\frac{1}{2}$.

By looking at the "extended phase portrait" I would infer  that this is indeed the case. However I would like to have solid argument.

I would argue as following: Let $x(t)$ be the solution to the above IVP.

For $x\in(0,1)$ $x^{3}-x<0$. Therefore $x'(t)<0$ and $x(t)$ is decreasing. Since $\tilde{x}(t)=0$ is a (equilibrium) solution $x(t)>0$, which follows from the uniqueness theorem. Hence, $0$ is a lower bound. Because $x(t)$ is bounded below and monotonically decreasing $lim_{t\rightarrow\infty}x(t)$ exists and $lim_{t\rightarrow\infty}x(t)\geq 0$.

Here is the part were I am stuck. I have two approaches. One works and the other doesn't I think. What I want to show is that $\lim_{t\rightarrow\infty}x'(t)=0$. Because then

$0=\lim_{t\rightarrow\infty}x'(t)=lim_{t\rightarrow\infty}f(x(t))=f(lim_{t\rightarrow\infty}x(t))=f(c)=c^{3}-c\iff c=0,c=1,c=-1$.

$c=-1$ is not possible, because the $x(t)$ would intersect $\tilde{x}(t)=0$, hence by the uniqueness it follows that $x(t)=0$ and thus $0>x'{t}=0$.
If $c=1$, then we can find $t_{1}\in\mathbb{R}_{>0}$ such that

$|x(t_{1})-1|<\frac{1}{2}\iff x(0)=\frac{1}{2}<x(t_{1})$.

Hence, by the mean value theorem it follow that there is

$\eta\in(0,t_{1})$ such that $f'(\eta)=\frac{x(t_{1})-x(0)}{t_{0}-0}>0$, but $f'(\eta)<0$. Therefore $c=0$.

Approach 1. Here I am stuck:

From the inequality $x'(t)<0$ it follows that $0\geq lim_{t\rightarrow\infty}x'(t)$.

Since $x(t)$ is a solution and because of the continuity of the r.h.s. of the IVP it follows that

$0\geq lim_{t\rightarrow\infty}x'(t)=lim_{t\rightarrow\infty}f(x(t))=f(lim_{t\rightarrow\infty}x(t))=f(c)=c^{3}-c$. $(*)$

Therefore $c\in[0,1]$ or $c\in(-\infty,-1]$. If the latter is the case then $x(t)$ would intersect with at least one equilibrium solution. Hence, this is not possible. Therefore $c\in[0,1]$. I think I can rule out any $c\in[\frac{1}{2},1]$, since then by the mean value theorem. $f'(\eta)>0$, which is not possible.

Can I somehow show that $f(c)=c^{3}-c\geq 0$. Then it would follow that $\lim_{\rightarrow\infty}x'(t)=0$, wouldn't it?

But isn't it the case that $f(c)\leq 0$, since $c\in[0,1]$ in equation $(*)$? Therefore we would have $0\leq f(c)\leq 0\iff f(c)=0$. Hence, $\lim_{t\rightarrow\infty}x'(t)=f(c)=0$

Is there a shorter way?

Approach 2:

We know that $\lim_{t\rightarrow\infty}x(t)=c$. Then $\lim_{t\rightarrow\infty}x'(t)=\lim_{t\rightarrow\infty}\lim_{h\rightarrow 0}\frac{x(t+h)-x(t)}{h}=\lim_{h\rightarrow 0}\lim_{t\rightarrow\infty}\frac{x(t+h)-x(t)}{h}=\lim_{h\rightarrow 0}\frac{c-c}{h}=0$.
I think all requirements for changing the order of the limits to be legal are met...or at least I hope so.

I would really appreciate any help. Thank you very much in advance!

答:
The IVP
$$
x'=x^3-x, \quad x(0)=\frac{1}{2}, \tag{1}
$$
enjoys uniqueness, since $f(x)=x^3-x$ is continuously differentiable.

Claim. If  $\varphi$ is the solution of $(1)$, then
$$
0<\varphi(t)<1
$$
Proof. If not then $\varphi(t_1)\ge 1$, for some $t_1>0$. Hence, due to Intermediate Value Theorem, there would be a $t_1\in (0,t_1]$ such that
$\varphi(t_2)=1$. In that case, $\varphi$ would satisfy the IVP
$$
x'=x^3-x, \quad x(t_1)=1, \tag{2}
$$
But $(2)$ is satisfied by $\psi(t)\equiv1$, and since $(2)$ enjoys uniqueness, then $\varphi\equiv \psi$. Contradiction. Similarly we can arrive to a contradiction if we assume that $\varphi(t_1)\le 0$, for some $t>0$. $\Box$

So, since $\varphi(t)\in (0,1)$, for all $t$, then (1) possesses a global solution, and
$$
\varphi'(t)=\varphi^3(t)-\varphi(t)<0, \quad \text{for all $t\in\mathbb R$.}
$$
Thus $\varphi$ is strictly decreasing, and therefore the $\lim_{t\to\infty}\varphi(t)$
exists and
$$
\lim_{t\to\infty}\varphi(t)\ge 0.
$$
We shall now show that $\lim_{t\to\infty}\varphi(t)=0$. If not and
$\lim_{t\to\infty}\varphi(t)=a>0,\,$ since $\varphi$ is decreasing, then $a \le 1/2=\varphi(0)$. We would then have that for all $t>0$,
$$
\varphi(t)\ge a\quad\Longrightarrow\quad \varphi'(t)=\varphi^3(t)-\varphi(t)\le a^3-a=-b<0
$$
since $g(t)=t^3-t$ is decreasing in $(0,1/\sqrt{3})$. Thus
$$
\varphi(t)-\varphi(0)=\int_0^t \varphi'(s)\,ds\le -bt\to -\infty
$$
as $t\to\infty$. Contradiction. Thus $\lim_{t\to\infty}\varphi(t)=0$.

Similarly, we can show that $\lim_{t\to-\infty}\varphi(t)=1$.


问:
Directional derivate of a convex proper function
The subgradient at $x\in\mathbb{R}^n$ of a convex function $f:\mathbb{R}^n\to\mathbb{R}$ is any vector $g\in \mathbb{R}^n$ such that $$f(y)\geq f(x) + g^T(y-x) \qquad\forall y \in \mathbb{R}^n.$$I have some problem about showing that
$$\frac{\partial f}{\partial d}:=lim_{t\to0}\frac{f(x+td)-f(x)}{t}=max\{g^Td\,|\,g\, \text{is a subgradient}\}$$

答:
When you refer to a subgradient, you should say at which point otherwise it doesn't make sense. Thus, all "subgradient" instances in your question should be replaced by "subgradient at $x$".

Let me use the standard notation $f'(x; d)$ to denote the directional derivative of $f$ at $x$ in direction $d$:
\begin{equation}
f'(x; d) = \lim_{t\to 0^+} \frac{f(x+td) - f(x)}{t}.
\end{equation}
We need to prove that
\begin{equation}
f'(x; d) = \max_{g\in \partial f(x)} g^T d \quad\forall x,d\in\mathbb{R^n}.
\end{equation}
This is a standard result in convex analysis and proofs can be found in any books on the topic. My proof below may be slightly different than those, in which I explicitly provide the subset of maximum solutions.

First, notice that
\begin{equation}
f(x+td) - f(x) \ge g^T(x+td-x) = tg^Td \quad \forall g\in\partial f(x), \forall x,d,t,
\end{equation}
we obtain
\begin{equation}
\boxed{f'(x; d) \ge g^T d \quad\forall g\in\partial f(x),\forall x,d.}\tag{*}
\end{equation}
We can prove the reverse inequality, or alternatively show that there exists $g\in\partial f(x)$ such that equality holds. To this end, we need some fundamental properties of directional derivatives:

$f(y) \ge f(x) + f'(x;y-x) \quad\forall x,y$.

The function $h(u) = f'(x;u)$ is convex and homogeneous of degree 1.

Both can be proved easily using the definition of $f(x;u)$ and the convexity of $f$.

Since $h(u)$ is convex, we have $h(u)\neq\emptyset$ and thus
$$h(v) - h(u) \ge g^T(v-u)\quad \forall v,\forall g\in\partial h(u).$$
If we choose $v=tu$ for some $t$, then $h(v) = h(tu) = th(u)$ and we obtain
$$(t-1)h(u) \ge (t-1)g^Tu.$$
Because the above holds for any $t$, we must have $h(u) = g^Tu$. Hence, we have proved that
\begin{equation}
\boxed{h(u) = g^Tu \quad\forall g\in\partial h(u), \forall u.}\tag{**}
\end{equation}
Using this equality and the above first property of directional derivatives, we get
$$f(y) \ge f(x) + f'(x;y-x) = f(x) + h(y-x) = f(x) + g^T(y-x) \quad \forall g\in\partial h(y-x), \forall y,$$
which implies $\partial h(y-x) \subset \partial f(x)\ \forall y$, or equivalently $\partial h(u) \subset \partial f(x)\ \forall u$. Therefore, we see that in $(*)$, equality occurs for any $g$ in the nonempty subset $\partial h(d)$ of $\partial f(x)$. QED


问:
Prove $rs=sr^{-1}$ in ${\rm Dih}(2n)$

Let $r$ and $s$ be the rotation and reflection symmetries respectively in ${\rm Dih}(2n)$, the dihedral group of order $2n$. Show that $rs=sr^{-1}$.

I also need to show by induction that $r^js=sr^{-j}$ but I think that will follow easily.

答:
You can see $\text{Dih}(2n)$ as a subgroup of $O(2,\mathbb{R})$. Thus $r= \left( \begin{matrix} \cos(\pi/n) & -\sin(\pi/n) \\ \sin(\pi/n) & \cos(\pi/n) \end{matrix} \right)$ and $s= \left( \begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix} \right)$. Then $srs= \left( \begin{matrix} \cos(\pi/n) & \sin(\pi/n) \\ -\sin(\pi/n) & \cos(\pi/n) \end{matrix} \right)=r^{-1}$.

Another possibility is to notice that $\det(srs)=\det(r)=1$ and $\text{Tr}(srs)=\text{Tr}(r)=2\cos(\pi/n)$. Therefore, $srs$ is a rotation of angle $\pm \pi/n$. If $srs=r$, then $r$ and $s$ commute and you deduce that $\text{Dih}(2n)$ is itself abelian, which is false. So $srs$ is a rotation of angle $-\pi/n$, ie. $srs=r^{-1}$.

Title: Prove $rs=sr^{-1}$ in ${\rm Dih}(2n)$


问:
Uniqueness of solution to least squares gradient descent using normal equations
It is known that any solution to the normal equations will solve the least squares minimization problem.

So finding a $w$ that satisfies $X^TXw=X^Ty$ will show that $w$ is optimal. However, it may be the case $X^TX$ is not invertible, so this would imply that the solution to the least squares may not be unique. However, we can use QR decomposition by setting $X=QR$ where $Q$ has orthogonal columns and $R$ is square and upper triangular with positive entries on the diagonal. This decomposition can always be done and is unique. Given $R$'s properties, it is always invertible. Plugging in this decomposition into the normal equations, after some simplifications we get
$$Rw=Q^Ty$$
Since $R$ is invertible, we have $w=R^{-1}Q^Ty$ which I believe is unique. So would this not imply that the solution to the least squares gradient descent is always unique, regardless of the invertibility of $X^TX$?

答: The entries of $R$ can be chosen to be positive only if $X$ has full column rank. If $X$ does not have independent columns, at least one diagonal entry of $R$ will be zero. Thus $R$ might not be invertible.


问:
Proof of equality for triangle inequality
I am trying to prove the following statement here:

Let $(V,\left<\cdot,\cdot\right>)$ be an inner product space and let $\vec{u},\vec{v}$ be vectors in $V$. Under the assumption that $\vec{u}\neq0$ show that $||\vec{u}+\vec{v}||=||\vec{u}||+||\vec{v}||$ if an only if $\vec{v}=c\vec{u}$ for some non-negative scalar $c$.

Here's my attempt. I use the general proof of the triangle inequality here.

$||\vec{u}+\vec{v}||^2$

$=\left<\vec{u}+\vec{v},\vec{u}+\vec{v}\right>$

$=\left<\vec{u},\vec{u}\right>+2\left<\vec{u},\vec{v}\right>+\left<\vec{v},\vec{v}\right>\leq\left<\vec{u},\vec{u}\right>+2|\left<\vec{u},\vec{v}\right>|+\left<\vec{v},\vec{v}\right>$ (By Cauchy-Scharwz)

So,

$||\vec{u}+\vec{v}||^2\leq\left<\vec{u},\vec{u}\right>+2|\left<\vec{u},\vec{v}\right>|+\left<\vec{v},\vec{v}\right>$

$||\vec{u}+\vec{v}||^2\leq\left<\vec{u},\vec{u}\right>+2||\vec{u}||\hspace{1mm}||\vec{v}||+\left<\vec{v},\vec{v}\right>$

$||\vec{u}+\vec{v}||^2\leq(||\vec{u}||+||\vec{v}||)^2$

$||\vec{u}+\vec{v}||\leq(||\vec{u}||+||\vec{v}||)$

I have a few comments here though. From what I understand, if I can turn the inequality parts into an equality, I am essentially done. I'm not really sure how to do that though. If I let $\vec{v}=c\vec{u}$, then I get:

$=\left<\vec{u},\vec{u}\right>+2\left<\vec{u},c\vec{u}\right>+\left<c\vec{u},c\vec{u}\right>$

but I am stuck at this point.

I know that:

$\left<\vec{u},\vec{u}\right>+2\left<\vec{u},c\vec{u}\right>+\left<c\vec{u},c\vec{u}\right>\leq\left<\vec{u},\vec{u}\right>+2|\left<\vec{u},c\vec{u}\right>|+\left<c\vec{u},c\vec{u}\right>$

becomes:

$\left<\vec{u},\vec{u}\right>+2\left<\vec{u},c\vec{u}\right>+\left<c\vec{u},c\vec{u}\right>=\left<\vec{u},\vec{u}\right>+2|\left<\vec{u},c\vec{u}\right>|+\left<c\vec{u},c\vec{u}\right>$ if and only if $c\vec{u}$ and $\vec{v}$ are non negative real numbers.

So at this point, I've taken care of the Cauchy-Schwarz inequality portion since one vector is a scalar multiple of the other.

How can I show that $\vec{u}$ and $c$ are non-negative though? If $\vec{u}$ and $c$ are non-negative, that immediately implies $\vec{v}$ is non-negative.

Can someone guide me with this part here? Thank you!

答:
Let $x,y \in V$ with $x \neq 0$ and notice that
$$
P(t)=||tx +y ||^2=t^2 || x||^2 + 2t\left<x,y\right>+||y||^2 \ge 0
$$
is a polynomial of degree $2$. By a classic result, $\Delta=4<x,y>^2 -4||x||^2||y||^2 \le 0$ that is $|\left<x,y\right>| \le ||x|| ||y||$. Suppose we have equality, therefore $\Delta=0$ and $P(t)=0=||tx +y ||^2$ with $t=\frac{-\left<x,y\right>}{||x||^2}$, so $y=-tx$.
Now, we have
$$
|| x+y ||=||x|| + ||y|| \iff <x,y>=||x|| ||y||
$$
so we have the result by the above (in case of equality $<x,y>\ge0$ so $-t\ge0$).


问:
Proving the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$ is not Context Free using Pumping Lemma
$\textit{Proof}$. Let $A$ be the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$. We will use the Pumping Lemma to prove that $A$ is not Context Free Language (CFL). The proof is by contradiction.

Suppose that $A$ is CFL. Let $p$ be the Pumping length given by the Pumping Lemma. Let $s$ be the string $1^{p}0^{p}0^{p}1^{p}$. Since $s \in A$ and $|s| \geq p$, the Pumping Lemma guarantees that $s$ can be divided into five pieces, $=uvxyz$, satisfying the following conditions:

for each $i \geq 0$, $uv^{i}xy^{i}z \in A$,

$|vy| > 0$

$|vxy| \leq p$

Then, by condition 3, we have that $vxy$ is a substring of the first half of $s\ (1^{p}0^{p})$, or $vxy$ is a substring of the middle of $s\ (0^{p}0^{p})$, or $vxy$ is a substring of the second half of $s\ (0^{p}1^{p})$. Let's analyze each case:

If $vxy$ is a substring of the first half of $s\ (1^{p}0^{p})$, then, $vxy$ can have only $1's$, or  can have both $1's$ and $0's$, or can have only $0's$. Let's analyze each case:

 If $vxy$ contains only $1's$, then, $uv^{0}xy^{0}z = uxz$ will have less $1's$ than $0's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

If $vxy$ contains $1's$ and $0's$, then $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

If $vxy$ contains only $0's$, then, $uv^{0}xy^{0}z = uxz$ will have less $0's$ than $1's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

If $vxy$ is a substring of the middle of $s\ (0^{p}0^{p})$. In this case $vxy$ will have only a kind of symbol, thus, $ uv^{0}xy^{0}z = uxz$ will have less $0's$ than  $1's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

If $vxy$ is a substring of the second half of $s\ (0^{p}1^{p})$, thus, $vxy$ can have only $0's$, or can have both $0's$ e $1's$, or can have only $1's$. Let's analyze each case:

If $vxy$ have only $0's$, then, $uv^{0}xy^{0}z = uxz$ will have less $0's$ than $1's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

If $vxy$ have $0's$ and $1's$, then, $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

 If $vxy$ have only $1's$, then, $uv^{0}xy^{0}z = uxz$ will have less $1's$ than $0's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

Since we analyzed all possible cases and in all cases a contradiction was inevitable, then we can conclude that $A$ is not CFL. $\square$

I tried to cover all possible cases.  But I am not so sure this is correct or if it can be further simplified.

答:
It’s correct and clear, but it could be simplified. There are really just two cases.

If $vxy$ contains only zeroes or only ones, pumping in either direction will produce a word $w$ such that $|w|_0\ne|w|_1$.

If $vxy$ contains both zeroes and ones, then it intersects only one of the two blocks of ones in $s$, and pumping in either direction will produce a word $w$ such that $w\ne w^R$.


答:
Are there any interesting/deep results that hold for multigraph?

(Bipartite) hypergraphs embedded cellularly on compact surfaces are in a one-to-one correspondence with algebraic curves defined over the algebraic numbers. Furthermore, there is a faithful action of the absolute Galois group over $\mathbb Q$ on the set of hypergraphs (not necessarily bipartite) embedded on compact surfaces. This action restricts to a faithful action on multigraphs.

Many combinatorial properties of multigraphs, such as the degree sequence, are invariant under this action. For more detail, look up dessins d'enfants and Grothendieck's Esquisse d'un Programme.

Title: Important results about/requiring multigraphs

Body:
Why are multigraphs important?  The wikipedia article on multigraphs mentions several different definitions but does not mention key results about multigraphs. So my question can have several levels of answers:

Are there any interesting/deep results that hold for multigraph?

Are multigraphs required for proving some important results?
E.g. from my internet searches I got the feeling that they featured in the proof of the 4-color theorem, but I am not entirely certain of this fact.

Are multigraphs unavoidable in some contexts? E.g. the dual graph of a planar graph might end up being a multigraph.

Are there any books/papers that focus on multigraphs and might answer the above questions?


问:
$h$ homeomorphism, $h(x)$ and $h(y)$ in different components in $h(X)$ implies $x, y$ in different components in $X$?
Homeomorphism $h:X\rightarrow Y$, if $h(x)$ and $h(y)$ lie in different connected components in h(X), is it true that x and y lie in different connected components in X?

I'm thinking for any two connected $U,V$ sets contain $h(x),h(y)$ respectively, they are disjoint. By continuity of $h^{-1}$, we have this is also true for $h^{-1}(U)$ and $h^{-1}(V)$ in $X$. Vice versa.

Thanks!

答: Did you mean $h(X)$ here? Remember that homeomorphisms preserve all the topological information. If $U$ and $V$ are disjoint in $Y$, taking the inverse of the homeomorphism keeps them disjoint. It's exactly the argument you mentioned. If that weren't the case then you could just use $h$ again and you'd get that a connected component splits into two different connected components.


问:
Hint for finding the sum: $\sum_{n=0}^{\infty}\frac{1}{4n^2-1} x^{2n+1}$?
I know that $\sum_{n=0}^{\infty}\frac{1}{4n^2-1}$ is a telescoping sum, but $x^{2n+1}$ in the sum complicates it a bit.

答:
The sum is $-x+\dfrac {x^3}3+\dfrac{x^5}{15}+\dfrac{x^7}{35}+\dfrac{x^9}{63}+\cdots+\dfrac{x^{2n+1}}{4n^2-1}+\cdots$.

Its derivative is $-1+x^2+\dfrac{x^4}3+\dfrac{x^6}5+\dfrac{x^8}{7}+\cdots+\dfrac{x^{2n}}{2n-1}+\cdots.$

$=-1+x\left(x+\dfrac{x^3}3+\dfrac{x^5}5+\dfrac {x^7}7+\cdots+\dfrac{x^{2n-1}}{2n-1}+\cdots\right)$

$=-1+x\tanh^{-1}x$.

Can you take it from here?


问:
Given that $f$ and $\ddot{f}$ are bounded, $\dot{f}(x)<0$ and $\lim_{x \rightarrow \infty} \dot{f}=0$ , Can we conclude that $\ddot{f} \geq 0$?
Given that $f(x)$ is lower bounded, $\dot{f}(x)<0$ , $\lim_{x \rightarrow \infty} \dot{f}=0$ and $\ddot{f}$ is bounded, Can we conclude that $\ddot{f} \geq 0$ , or more specifically $\ddot{f}(x)>0$ and $\lim_{x \rightarrow \infty} \ddot{f}=0$ ?

If the given was $\dot{f}$ is bounded, instead of $\ddot{f}$ being bounded , Can the same be said ?

答: No, we cannot conclude that $f$ is convex. Just draw a graph of a decreasing function which changes from being concave to convex.


问:
What is the relation between graded modules and finitely generated modules
The reason I ask this question is I found two different statements about Hilbert's syzygy theorem from Jacobson's Basic Algebras 2nd and Wikipedia. Please have a look at the following pictures. The first one is from the former and the second one is from the latter.

In this two statements I found the modules required are different. One is called graded and one is called finitely generated. But the results are the same. So I want to ask are these two kinds of modules equivalent? Or there is some connection between them. Someone has told me that there are two editions about this theorem. If this is the case, then which one is more general or widely used?

At the same time, I found Quillen-Suslin theorem from wikipedia, which states that
every finitely generated projective module over a polynomial ring is free. And from Jacobson's book mentioned above there is a corollary

Here I consider the corollary as Any projective graded R-module for $R=F[x_1,x_2,...,x_m]$ is free. I don't know whether I understand it in a correct way or not. Then are these two statements about projective modules to be free the same?

Thank you for your assistance.

答:
The two theorems are not the same. One is about graded modules and the other is about modules.

The two results are related, though. As you say, every projective graded module (that is every projective object of the category of graded modules and homogeneous maps of degree zero) is free as a module, and the conection between the two theorems stems from that.

The second theorem is true even if you remove the hypothesis that the module $M$ be finitely generated.

Finally, that corollary of Quillen-Suslin should be understood in the sense that every projective module is graded free for some grading which is to be found.


答:
Just consider $f(x) = -\arctan(x)+ 100$.

Then:

$f$ is lower bounded;

$\dot f(x) = - \dfrac{1}{x^2+1}< 0$ for every $x \in \mathbb R$;

$\displaystyle\lim_{x \to +\infty} \dot f(x) =0$;

$\ddot  f(x) = \dfrac{2x}{(x^2+1)^2}$ is bounded, but it changes its sign.

EDIT:

In this case $\dot f(x)$ is bounded too.

Title: Given that $f$ and $\ddot{f}$ are bounded, $\dot{f}(x)<0$ and $\lim_{x \rightarrow \infty} \dot{f}=0$ , Can we conclude that $\ddot{f} \geq 0$?

Body:
Given that $f(x)$ is lower bounded, $\dot{f}(x)<0$ , $\lim_{x \rightarrow \infty} \dot{f}=0$ and $\ddot{f}$ is bounded, Can we conclude that $\ddot{f} \geq 0$ , or more specifically $\ddot{f}(x)>0$ and $\lim_{x \rightarrow \infty} \ddot{f}=0$ ?

If the given was $\dot{f}$ is bounded, instead of $\ddot{f}$ being bounded , Can the same be said ?


问:
Showing $\left| \oint \frac{\sin z}{z^{5}}dz \right| \leq 2e\pi$

Show that
$$\left| \oint \frac{\sin z}{z^{5}}dz \right| \leq 2e\pi $$

My attempt:

I solved the integral without the absolute value, but I don't know how to get to the inequality. I also don't know if my calculations are correct.

$$f^{(n)}(z_0)=\frac{n!}{2\pi i}\oint_C \frac{f(z)}{(z-z_0)^{n+1}}\,dz$$

Here, we have $f(z)=\sin z$, $z_0=0$, $n=2$. Therefore, we have
$$
\oint_{|z|=1} \frac{\sin z}{z^{5}}\,dz=\pi i\left.\frac{d^4\sin z}{4!}\right|_{z=0}=0
$$

Thank you

答:
Assuming that the contour in question is the unit circle, we have $|\sin(z)| \le e$ for $|z| = 1$, and $|z|^5 = 1$. Therefore,

$$\left|\oint_C \frac{\sin z}{z^5}\right| \le \text{length}(C) \sup_{|z|=1}|\sin z| = 2\pi e$$

Of course, since $\sin(z)/z^5 = z^{-4} + \tfrac{1}{6}z^{-2} + h(z)$, where $h$ is analytic on the unit disk, the integral is in fact zero. So this is not a very useful bound!

Edit: $\text{length}(C) = 2\pi$ is the length of the unit circle. For the bound, notice that $\sin(z) = \tfrac{1}{2}(e^{iz} - e^{-iz})$, so $|\sin(z)| \le \tfrac12(|e^{iz}| + |e^{-iz}|)$. But also, $|e^{x+iy}| = e^x$, and if $z$ is on the unit circle, then the real and imaginary parts of $z$ are between -1 and 1. Therefore $|e^{iz}| \le e$, and $|\sin(z)| \le e$.