问:
Sorting an array to get the maximum combined sum of the differences between every two adjacent elements
This is related to this question: Stack Overflow

Problem description

We are given a sequence of n positive integers. How to sort the elements to get the maximum combined sum of the differences between every two adjacent elements.

For example, for a sequence {8, 4, 1, 2, 3} the starting difference is (8-4) + (4-1) + (2-1) + (3-2) = 9, but 14 can be reached for {4, 8, 1, 3, 2}.

The best arrangement is {4, 1, 8, 2, 3}, sum 17.

Claim

Optimal solution can always be reached by either starting with the smallest or largest element and then alternately putting currently largest/smallest elements on both sides of the sequence.

That's not all yet: for the starting sequence {1, 2, 3, 4} we would start with 4 $\longrightarrow$ 1 4 2 $\longrightarrow$ 3 1 4 2 or 1 4 2 3. So this approach is not strict enough yet.

However, if we always first put to the left and then to the right (or otherwise), we are guaranteed that the number on the left side will be smaller/bigger than the corresponding number on the right side.

I tested the solution above so I am quite sure it works.
I am interested how would you prove it.

答:
You are correct:

When $n$ is even, the best arrangement has the highest and lowest in the middle, sandwiched between the second lowest and second highest, sandwiched between the third highest and third lowest, etc.

When $n$ is odd, the optimal arrangement either has the highest in the middle, sandwiched between the two lowest, then two remaining highest, etc, or it is the similar sequence where you start with the lowest in the middle.

The proof is easier when $n$ is even, so let's start there. Let the sequence of positive integers, sorted in increasing order, be $x_1\le x_2\le \dots\le x_n$. Then, for $i=1,\dots,n-1$, let $s_i=x_{i+1}-x_i$ be the sequence of gaps between the numbers. Finally, given a permutation $y_1,y_2,\dots,y_n$ of the given sequence, for $i=1,\dots,n-1$, let
$$
m_i=\#\{j:y_{j}\le x_{i}\text{ and } y_{j+1}\ge x_{i+1}\}+\#\{j:y_j\ge x_{i+1}\text{ and } y_{j+1}\le x_i \}
$$
In words, $m_i$ is the number of times the sequence $(y_1,\dots,y_n)$ crosses the "gap" between $x_i$ and $x_{i+1}$. Each time the sequence does this, it adds $s_i$ to the total of the absolute differences of the consecutive elements. Therefore, it follows that
$$
|y_2-y_1|+|y_3-y_2|+\dots+|y_n-y_{n-1}|=\sum_{i=1}^{n-1}m_is_i
$$
If this is unclear, I encourage you to look at some examples. You can then show two things:

For the proposed optimal sequence, we have$$
\begin{cases}
m_i=2i & \text{when $i<n/2$}\\
m_{n/2}=n-1\\
m_{n-i}=2i & \text{when $i<n/2$}\\
\end{cases}
$$

For any permutation, it is true that $$
\begin{cases}
m_i\le 2i & \text{when $i<n/2$}\\
m_{n/2}\le n-1\\
m_{n-i}\le 2i & \text{when $i<n/2$}\\
\end{cases}
$$

These two points imply that the proposed sequence is optimal.

The first bullet can be verified easily. For the second bullet, note that when $i<n/2$, that a crossing between $x_i$ and $x_{i+1}$ can only occur when one of the $i$ smallest values $x_1,\dots,x_i$ is next to one of the largest $n-i$ values. But this can obviously occur at most $2i$ times, to the left and right of each of the $i$ values $x_1,\dots,x_i$.  The same logic applies to $m_{n-i}$. Finally, $m_{n/2}\le n-1$ since there are only $n-1$ adjacent pairs.

I leave the case when $n$ is odd to you. In this case, you will find three things:

When $i<n/2$, $m_i<2i$ and $m_{n-i}<2i$ (same as before).

Furthermore, letting $k=\lfloor n/2\rfloor$, it is impossible to have both $m_k=2k$ and $m_{k+1}=2k$. At least of these must be smaller than their maximal value in any permutation.

The two proposed optimal arrangements achieve the maximal values implied by the two previous bullet points.


问:
Show the collection of sets M is basis for a topology
I am self studying topology using Topology without Tears

Let $C[0,1]$ be set of all real valued continuous functions

Show the collection $M$ given by
$$
M=\{M(f,\epsilon),f\in  C[0,1]\}, \quad
M(f,\epsilon) = \{g:g \in C[0,1] \text{ and } \int_0^1 |f-g| < \epsilon\}
$$

Show this a basis  for $\tau_1$

Ok I saw a bunch of hints
https://math.stackexchange.com/a/1195168/830852

Here goes nothing

Let $\epsilon = 1$. Suppose $f\in M(f,1)$ then
$\int_0^1 |f-f|=0 <1$ so
$C[0,1] =\bigcup M(f,1)$ for $f\in C[0,1]$.

For the rest of it I thought prop. 2.3.2 would
apply somehow

I also thought of using triangle inequality on
the integral.

Any help would be appreciated.

答:
We want to show that $\mathcal M = \{M(f,\epsilon),f\in  C[0,1]\}$ is a basis for $\tau_1$. You don't say what $\tau_1$ is, but from the context it seems that $\tau_1$ is the topology over $C[0,1]$ induced by the metric
$$
d(f,g) = \int_0^1 |f-g|.
$$
Let's review the definition of a basis:

A basis for a topology $\tau$ over a space $X$ is a collection of open subsets (elements of $\tau$ such that

The base elements cover $X$

Let $B_1$, $B_2$ be base elements. Then for each $x \in B_1 \cap B_2$, there is a base element $B_3$ containing $x$ such that $B_3 \subset B_1 \cap B_2$.

First, you should verify that the elements of $\mathcal M$  are open. Then, you should show that part 1 of the definition holds (which is what you have done with your argument so far). The tricky part is showing that the second part of the definition applies to 1.

With that in mind: let $B_1 = M(f_1,\epsilon_1)$ and $B_2 = M(f_2,\epsilon_2)$. If $B_1 \cap B_2 = \emptyset$, then there is nothing to show. So, suppose that $B_1 \cap B_2$ is non-empty. Let $g$ be an element of $B_1 \cap B_2$.  By definition, this means that
$$
d(f_1,g) < \epsilon_1, \quad d(f_2,g) < \epsilon_2.
$$
Now, define $\delta = \min\{\epsilon_1 - d(f_1,g),\epsilon_2 - d(f_2,g)\}$. Using the triangle inequality, show that if a function $h \in C[0,1]$ satisfies $d(g,h) < \delta$, then it also satisfies $d(f_1,h) < \epsilon_1$ and $d(f_2,h) < \epsilon_2$. Using this fact, conclude that the basis element $B_3 = M(g,\delta)$ contains $g$ and satisfies $B_3 \subset B_1 \cap B_2$.

ContentLicense: CC BY-SA 4.0


问:
Determining the position of a vertex of a triangle

A triangle has a vertex $A$ at $(0,3)$, vertex $B$ at $(4,0)$, and vertex $C$ at $(x,5)$. If the area of the triangle is $8$, what is the value of $x$?

I did this problem out by using the formula of the given coordinates of the vertices. My answer was 2.66.

答:
Good work, in arriving at one of the correct solutions, Briana..

I would just like to clarify what others mean by there being two solutions: there are two triangles, each sharing vertices at $(0,3)$ and $(4,0)$ (and hence they share a side).  But there are two values for the unknown $x$ in the vertex $(x, 5)$ that yield a triangle with area $8: x = \frac {8}{3} = (2.66$ repeating), and $x = -8.$

In other words, the area of the triangle with third vertex $( \frac {8}{3}, 5)$ and the area of triangle with third vertex $(-8, 5)$ both equal $8$.

ContentLicense: CC BY-SA 3.0


问:
Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?
The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all?

With the discrete logarithm problem I mean the following problem:

Let $G$ be a group and let $g$ and $h$ be elements of $G$ such that $h \in \langle g \rangle$. Find an integer $x$ such that $g^x = h$.

In particular I am interested in the case where $G = \mathbb{Z}_p^*$. If we know an efficient way to factor integers, does this help us in solving the discrete logarithm problem for a given $\mathbb{Z}_p^*$?

Conversely, if we know how to solve  the discrete logarithm problem efficiently for any group $G$ (or just $\mathbb{Z}_p^*$), does this help with factoring integers?

答:
Are these two problems related at all?

The answer is yes, and it is at many levels. The general number field sieve, which is generally thought of as a factoring algorithm, is also very useful for solving discrete logs.

Theoretically:
Solving the discrete log with a composite modulus is exactly as hard as factoring [3]. However, it is not known if solving discrete log with a prime modulus leads to efficient factoring [4].

If we know an efficient way to factor integers, does this help us in solving the discrete logarithm problem for a given $\mathbb{Z}_p^*$?

Conversely, if we know how to solve the discrete logarithm problem efficiently for any group G  (or just $\mathbb{Z}_p^*$), does this help with factoring integers?

For composite modulus, the answer is yes. For prime modulus, we don't know.

A good reference for a lot of this information is John Gregg's thesis page 43.


问:
Manipulating an ODE into a full differential
Find the general solution of:

$$(x-2)\frac{d^2y}{dx^2} + 3\frac{dy}{dx} + \frac{4y}{x^2} = 0$$

If I first multiply through by $x^2$ then I can write the above as

$$x^2(x-2)\frac{d^2y}{dx^2} + 3x^2\frac{dy}{dx} + 4y  $$
$$ =\left[ x^3\frac{d^2y}{dx^2} + 3x^2\frac{dy}{dx}\right]-2x^2 \frac{d^2y}{dx^2} +4y  $$
$$ =\frac{d}{dx}\left( x^3\frac{dy}{dx}\right) -2x^2 \frac{d^2y}{dx^2} +4y = 0$$

and I'm not sure how to express the rest of the equation as the derivative of some function (I tried $\frac{d}{dx} 2x^2y$ to no avail) . Any help would be appreciated.

Body:
Hint:

$$\frac{d}{dx}\left( x^3\frac{dy}{dx}\right) -2x^2 \frac{d^2y}{dx^2} +4y = 0$$
$$\frac{d}{dx}\left( x^3\frac{dy}{dx}\right) -2x^2 \frac{d^2y}{dx^2} \color {red}{-4xy'+4xy'} +4y = 0$$
$$\left( x^3y'\right)' -(2x^2 y')'  +4(xy)' = 0$$


问:
Neat way to calculate intersection of 2 lines using 4 points.
I'm a minecraft speedrunner. We throw pearls to locate a stronghold. It's hard to explain, but here's an explanation:
Image explaining it here
So we know the points (x1,y1), (x2,y2) which are on one line. and we know (x3,y3), (x4,y4), which are on another line. We want to know the intersection of these points, here called (x,y). We are not allowed to use calculators during runs, but we are doing a 10+ people speedrun so we can have some people crunching the numbers with pen and paper. We decided to put them in as vectors, and then take the x and y parts of those vectors, and solve for that. From the x equation we got:
$$a = \frac{x_3-x_1+b \cdot (x_3-x_4)}{x_1-x_2} $$
Filling that in into the y equation gives:
$$b=\frac{(y_1-y_2)\cdot(y_1(x_1-x_2) + x_3-x_1)-y_3(x_1-x_2)}{((x_3-x_4)(y_3-y_4)-(x_3-x_4))}$$
Filling those in in $x=x_3+b(x_3-x_4)$ and $y=y_3+b(y_3-y_4)$ gives:
$$x=x_3+\frac{(y_1-y_2)\cdot(y_1(x_1-x_2) + x_3-x_1)-y_3(x_1-x_2)}{((y_3-y_4)-1)}$$
$$y=y_3+\frac{
(y_1-y_2)\cdot(y_1(x_1-x_2) + x_3-x_1)-y_3(x_1-x_2)}{((x_3-x_4)(y_3-y_4)-(x_3-x_4))}(y_3-y_4)$$
However, this is still pretty complicated. We need to be able to do this during a run, by hand with just pen and paper. Are there any other, less convoluted ways to do this?
Thanks in advance!

EDIT: We can walk to 0,0 to set (x1,y1) = (0,0) which turns the x equation into $$x=x_3+\frac{
-y_2x_3+y_3x_2}{y_3-y_4-1}$$
and the y equation after setting (x3,y3) = (0,0) to $$y=\frac{
(y_1-y_2)\cdot(y_1(x_1-x_2) -x_1)}{(x_4y_4+x_4)}(-y_4)$$
Which is sliiightly nicer already I guess

EDIT 2:
To the person who suggested cramer's rule and deleted their comment: thank you so much! That really helps, we're gonna try to get a formula from that which is probably a LOT easier

答:
This is to document how Cramer's rule may be used to find the intersection point. First, we may express the equation of the first line in point-slope form as $$y-y_1=\frac{x-x_1}{x_2-x_1}(y_2-y_1).$$
After some rearrangement, we obtain
$$(y_2-y_1)x+(x_1-x_2)y=x_1y_2-x_2 y_1.$$
If we repeat this form the second line, we instead obtain
$$(y_4-y_3)x+(x_3-x_4)y=x_3y_4-x_4 y_3.$$
Cramer's rule then gives the solution in terms of determinants as

$$x=\begin{vmatrix} x_1 y_2-x_2 y_1 & x_1-x_2 \\ x_3y_4-x_4 y_3 & x_3-x_4\end{vmatrix}\Bigg/\begin{vmatrix} y_2-y_1 & x_1-x_2 \\ y_4-y_3 & x_3-x_4\end{vmatrix},$$

$$y=\begin{vmatrix} y_2-y_1 & x_1 y_2-x_2 y_1 \\  y_4-y_3 & x_3y_4-x_4 y_3\end{vmatrix}\Bigg/\begin{vmatrix} y_2-y_1 & x_1-x_2 \\ y_4-y_3 & x_3-x_4\end{vmatrix},$$

where $\begin{vmatrix} a & b \\ c & d\end{vmatrix}=ad-bc$. For that matter we may also write $$x_1 y_2 -x_2 y_1=\begin{vmatrix} x_1 & x_2 \\ y_1 & y_2 \end{vmatrix},\quad x_3 y_4 -x_4 y_3=\begin{vmatrix} x_3 & x_4 \\ y_3 & y_4 \end{vmatrix}$$
though this may be more tedious than useful. It should be noted that the above is mostly useful as a way of organizing the computation: Ultimately, the results are the same as would be obtained by the seemingly-uglier equations in the OP.


问:
Then I need to show that the topology induced in $A$ by $X$ coincides with the topology induced in $A$ by $Y$
$X$ a topological space
$Y$ a subspace of $X$
$A$ a subspace of $Y$

That is $A \subset Y \subset X$

Then I need to show that the topology induced in $A$ by $X$ coincides with the topology induced in $A$ by $Y$

Be:

$\tau_1$ the topology induced in $A$ by $Y$

$\tau_2$ the topology induced in $A$ by $X$.

$\tau_Y$ the $Y$ topology

$\tau_X$ the $X$ topology
We need to show that one is contained in the other.

Let $U \subset A$ tq $U \in \tau_1$. So there is an open $V \in \tau_Y$ tq $U = V \cap A$. But we know that if $V \in \tau_Y$ it means that there is $W$ in $\tau_X$ tq $V = W \cap Y$

So I have two equations:

$U = V \cap A$ (equation 1)

$V = W \cap Y$ (equation 2)

I need to show that $U$ is in $\tau_2$, meaning that $U = W \cap Y$.

If I substitute equation 2 for 1, I have:

$U = (W \cap Y) \cap A$.

Could someone help me finish?

答:
Since $A\subseteq Y,W\cap Y\cap A=W\cap A$. Thus $U=W\cap A\in\tau_2$.

For showing that $\tau_2\subseteq\tau_1$, proceed similarly.

Let $U'\in\tau_2$. Then $U'=A\cap V'$ for some $V'\in\tau_X$. But $A\cap V'=A\cap\underbrace{Y\cap V'}_{M\in\tau_Y}\in\tau_1$.


问:
The group $G=\{ \sigma \in Aut(K) : \sigma|_\mathbb{Q} = id_\mathbb{Q} \}$ of $K=\mathbb{Q}(7^\frac{1}{5})$
I'm trying to find the group $G=\{ \sigma \in Aut(K): \sigma|_\mathbb{Q} = id_\mathbb{Q} \}$ for $K=\mathbb{Q}(7^\frac{1}{5})$ and here is my reasoning:

Since $\mathbb{Q}\subseteq K$ is a finite extension and $\textrm{char}(\mathbb{Q})=0$ the extension is separable, hence $|S|=[K:\mathbb{Q}]_s=[K:\mathbb{Q}]=\textrm{deg}(f)=5$ where $f=x^5-7$ is the minimal polynomial of $\alpha=7^\frac{1}{5}$ and $S=\{\sigma:K\rightarrow \overline{\mathbb{Q}} :\sigma \hspace{0.2cm} \textrm{is an homomorphism and} \hspace{0.2cm} \sigma|_\mathbb{Q}=id_\mathbb{Q} \}$. Clearly, $G\subseteq S$.

Note that for each $j=1,...,4$, $\alpha\beta^j$ is a root of $f$, where $\beta=e^\frac{2\pi i}{5}$ and together with $\alpha$ they are all the roots of $f$. Hence $K\simeq \mathbb{Q}[x]/(f) \simeq \mathbb{Q}(\alpha\beta^j)$ for each $j=1,...,4$ by the isomorphism $\sigma_j: K\rightarrow \mathbb{Q}(\alpha\beta^j)$,  $\sigma_j(\alpha)=\alpha\beta^j$, $\sigma_j|_\mathbb{Q}=id_\mathbb{Q}$. Since $\mathbb{Q}(\alpha\beta^j)\subseteq \overline{\mathbb{Q}}$ and there are $4$ distinct $\sigma_j$ we arrive that $S=\{id_K, \sigma_1, \sigma_2, \sigma_3, \sigma_4 \}$. Because $\alpha\beta^j \notin K$ we get that $\sigma_j \notin G$. Therefore: $G=\{id_K\}$

If anyone could verify my reasoning and give me feedback would help me very much. Also any alternative proof is appreciated.

答:
Looks good.  A couple of comments on your proof.  Any field automorphism of $K$ is automatically going to fix $\mathbb Q$ pointwise, so you can just write $G = \operatorname{Aut}K$.

Your proof contains a lot of fluff and can be shorted.  There is no need to mention anything about separability (since we are in characteristic zero as you point out) or about the fields $K(\alpha \beta^j)$ or about embeddings of $K$ into $\overline{\mathbb Q}$.

The main idea is that any automorphism $\sigma$ of $K$ is going to send $\alpha = \sqrt[5]{7}$ to a root of $x^5= 7$.  Since $K$ doesn't contain any such roots except for $\alpha$ itself, this means that $\sigma$ must fix $\alpha$ and hence $\sigma = \operatorname{id}_K$.


问:
Probability that uniform random subsets $S_1\subseteq\dots\subseteq S_m$
Pick (not necessarily distinct) subsets $S_1,\dots,S_m\subseteq\{1,\dots,n\}$ uniformly at random. What is the probability that $S_1\subseteq S_2\subseteq\dots\subseteq S_m$?

I have solved the problem for $m=2$. Conditional on $|S_2|=k$, the probability that $S_1\subseteq S_2$ is $\frac{2^k}{2^n}$. So by law of total probability,
$$\mathbb P(S_1\subseteq S_2)=2^{-n}\sum_{k=0}^n2^k\cdot\mathbb P(|S_2|=k)=2^{-2n}\sum_{k=0}^n\binom{n}{k}2^k=2^{-2n}(1+2)^n=\left(\frac{3}{4}\right)^n.$$
But already for $m=3$ the sums are becoming unmanageable. Perhaps there is another perspective?

答:
In a good configuration, for every $i \in \{1,\ldots,n\}$ there is $k \in \{0,\ldots,m\}$ such that $i \in S_l$ for $l>k$, but $ i\not\in S_l$ for $l \leq k$. (if needed, use $S_0 = \phi$ and $S_{m+1} = \{1,\ldots,n\}$).

Now, these are $m+1$ groups, so in total $(m+1)^n$ "good cases", the total ones are clearly $(2^n)^m = 2^{nm}$.

So, our probability is $$ \Big(\frac{m+1}{2^m} \Big)^n$$


答:
First, for $1\leq i,j\leq m$ and $1\leq k,\ell\leq n$, the events $\{k\in S_i\}$ and $\{\ell\in S_j\}$ are independent (unless of course $k=\ell$ and $i=j$). Now say that some $k\in\{1,\dots,n\}$ is good if one of the following (mutually exclusive) conditions hold:

$k\in S_1, k\in S_2,k\in S_3,\dots,k\in S_m$.

$k\not\in S_1, k\in S_2,k\in S_3,\dots, k\in S_m$.

$k\not\in S_1, k\not\in S_2,k\in S_3,\dots, k\in S_m$.

$\vdots$

$k\not\in S_1, k\not\in S_2,k\not\in S_3,\dots, k\not\in S_m$.

Then $S_1\subseteq\dots\subseteq S_m$ iff every $k$ is good. The probability a given $k\in\{1,\dots,n\}$ is good is $\frac{m+1}{2^m}$, so the probability that all $k$ are good is $\left(\frac{m+1}{2^m}\right)^n$.

Title: Probability that uniform random subsets $S_1\subseteq\dots\subseteq S_m$

Body:
Pick (not necessarily distinct) subsets $S_1,\dots,S_m\subseteq\{1,\dots,n\}$ uniformly at random. What is the probability that $S_1\subseteq S_2\subseteq\dots\subseteq S_m$?

I have solved the problem for $m=2$. Conditional on $|S_2|=k$, the probability that $S_1\subseteq S_2$ is $\frac{2^k}{2^n}$. So by law of total probability,
$$\mathbb P(S_1\subseteq S_2)=2^{-n}\sum_{k=0}^n2^k\cdot\mathbb P(|S_2|=k)=2^{-2n}\sum_{k=0}^n\binom{n}{k}2^k=2^{-2n}(1+2)^n=\left(\frac{3}{4}\right)^n.$$
But already for $m=3$ the sums are becoming unmanageable. Perhaps there is another perspective?


问:
Application of the Identity Theorem to $|x|^3$ for $-1<x<1$
Oxford Exam $2602$ $1997$ $Q3$

We want to show that there is no function $f$ which is holomorphic in $D(0;1)$ and such that $f(x)=|x|^3$ for $-1<x<1$.

Here are my thoughts thus far:

Suppose there is. Then $g(x)=f(x)-|x|^3=0$ for $-1<x<1$. Then by the Identity Theorem we must have that $g^{-1}(\{0\})$ has a limit point in $S:=\{x:-1<x<1\}$.

I'm hoping this leads to a contradiction, but I can't see how. Perhaps the method is incorrect.

Any help appreciated. Thanks.

答:
Hint: If $f(x)=|x|^3$ for $x\in (0,1)$, then $f(x)$ and $x^3$ agree on the interval $(0,1)$. Now use the identity theorem, and derive a contradiction.

Edit: For reference, my version of the identity theorem states:

If $f(z)$ and $g(z)$ are holomorphic functions on a domain $U$ (an open, path connected set), then if $\{ z \in U : f(z)=g(z)\}$ has a non-isolated point $w$, then $\forall z \in U,f(z)=g(z) $.

$\bigg($My definition of $w$ being a limit point for a set $S$ is that $\forall \epsilon > 0 , (B_\epsilon(w)\text{\ }\{w\})\cap S\not=\phi\bigg)$


问:
Understanding change of variables in double integrals
In this libre text chapter, in example 15.7.1B, the author illustrates the change of variables using the following example:

The statement near it is written:

For the vertical length  $A:u=0,0≤v≤1$  transforms to  $x=−v^2,y=0$  so this is the horizontal length $A′ $ that joins  $(−1,0)$  and $ (0,0)$

I find it confusing that regardless of whatever function of $x$ could have been on $v$, it seems that all of them would only have a straight line of $A'$ like suppose it was $x=-v^3$, that'd also denote the same line

If I understood correctly, we derive $A'$ from $A$ by feeding constraints of $A$ into the dependencies of the new variables on the old. Under that idea, does the kind of function $x$ is on the old coordinates not matter in sketching the region(only the bounds does)?

答:
Note the mapping
\begin{align*}
x&=u^2-v^2\tag{1}\\
y&=uv\tag{2}
\end{align*}
from the $u,v$-plane in the $x,y$-plane is also given in (2) by $y=uv$. This means whenever we set $\color{blue}{u=0}$, we have $y=0$ regardless of the setting of $v$.

Nevertheless the mapping to parabolic coordinates given by (1) and (2) is often used since it is a one-to-one mapping with very nice geometrical properties:

The curves $x = \mathrm{constant}$ give rise in the $u,v$-plane to the rectangular hyperbolas $u^2-v^2=\mathrm{constant}$. They have asymptotes which are $u=v$ and $u=-v$. The lines $y = \mathrm{constant}$ also correspond to a family of rectangular hyperbolas. Here the asymptotes are the coordinate axes. The hyperbolas of each family cut those of the other family at right angles.

The lines parallel to the axes in the $u,v$-plane correspond to two families of parabolas in the $x,y$-plane. The parabolas $y^2=c^2(c^2-x)$ correspond to the lines $u=c$ and the parabolas $y^2=k^2(k^2+x)$ correspond to the lines $v=k$. All these parabolas have the origin as focus and the $x$-axis as axis. They form a famliy of confocal  and coaxial parabolas.

This explanation can be found for instance in the classic Introduction to Calculues and Analysis II by R. Courant and F. John.

I also like the following application of this kind of bijective mapping given by the authors. In the following we denote in OP's example the region bounded by the line segments $A,B$ and $C$ with $R$ and the region bounded by the curve segments $A^{\prime}, B^{\prime}$ and $C^{\prime}$ with $R^{\prime}$.

One-one transformations have an important interpretation and application in the representation of deformations or motions of continuously
distributed substances, such as fluids. If we think of such a substance as spread out at a given time over a region $R$ and then deformed by a motion, the substance originally spread over $R$ will in general cover a region $R^{\prime}$ different from $R$. Each particle of the substance can be distinguished at the beginning of the motion by its coordinates $(u,v)$ in $R$ and at the end of the motion by its coordinates $(x,y)$ in $R^{\prime}$. The $1$-$1$ character of the transformation obtained by bringing $(u,v)$ into correspondence with $(x,y)$ is simply the mathematical expression of the physically obvious fact that separate particles remain separate.


问:
For odd $n$ is the polynomial $X^{n-1}-X^{n-2}+...-X+1$ irreducible in $\mathbb{Q}[X]$?
Let $n$ be an odd integer. Is the polynomial $X^{n-1}-X^{n-2}+...-X+1$ irreducible in $\mathbb{Q}[X]$?

I believe that it is, but I don't know how to ptove it. I tried to use Eisenstein's criterion, but it would only work when $n$ is prime. So, how to do it?

答: Let $n=9$. Then your polynomial $P_n$ factors (as mentioned in comments) as $\Phi_3(-x)\Phi_9(-x)$ where the $\Phi$ are cyclotomic polynomials. In general $P_n=\prod_{d\mid n,d>1}\Phi_d(-x)$, so it is irreducible precisely when $n$ is prime.


问:
Are functions in maths "pure"?
In computer science, some functions are said to be "pure", meaning that (amongst other things) they can only use variables defined in their parameters. In a mathematical context, are all functions pure or is something like this allowed?: $$
a = 3 \\
f(x) = x + a
$$
If this is allowed, then does this mean "variables" (e.g. $a$ in this case) is immutable? (also is this true even if math functions are pure?)

答:
You can write
$$
f(x)=x+a
$$
but then it is assumed that $a$ is some constant. If $a$ is a variable, then you should write
$$
f(x,a)=x+a
$$
instead.

Title: Are functions in maths "pure"?


问:
Find the numbers $a,b,c,d$ in a geometric sequence, knowing that $a+1$, $b+6$, $c+6$, $d-4$ are in an arithmetic sequence
The exercise reads as follows:

Find the numbers $a,b,c,d$ in a geometric sequence, knowing that $a+1$, $b+6$, $c+6$, $d-4$ are in an arithmetic sequence.

I am interested in finding out the steps I should use to get to a solution. Or just a starting point, I've been thinking about this for some time and I wouldn't say I am getting close to the result soon.

I was thinking about:

$a+1 = b+6-r \implies a=b+5-r$

$c+6 = b+6+r \implies c=b+r$

And use $b^2=a*c$ from the geometric sequence.

The topic can be closed. Massive thanks to Rafaelle for the solution and also to Oscar Lanzi for explaining the process!

Body:
$$\begin{cases}
\frac{a}{b}=\frac{b}{c}\\
\frac{b}{c}=\frac{c}{d}\\
-(a+1)+b+6=-(b+6)+c+6\\
-(b+6)+c+6=-(c+6)+d-4\\
\end{cases}
$$
$$a= 5,b= 10,c= 20,d= 40$$


问:
Proving $f$ is a power series centered at 0.
By the definition of analytic function, if $f: \mathbb{D}\rightarrow\mathbb{C}$ is analytic, then $f$ can be represented as a power series centered at 0? I think this straightly follows from the definition of the analytic function. I want to check if I am missing something or the statement is actually trivial.

$\mathbb{D}$ is a unit disk.

答: It is true. Indeed, for an analytic function $f : U \rightarrow \mathbb{C}$ defined on an open subset $U \subset \mathbb{C}$, the radius of convergence when you develop $f$ in power series around a point $a \in U$ is at least $d(a, \mathbb{C}\setminus U)$.


答:
It's a (not too difficult) theorem that $d|n$ iff $(x^{d}-1)|(x^n-1)$. Factoring out $x-1$ and letting $n$ be odd should answer your question.

To prove the theorem, you only need the forward direction (which is the easier one). Just suppose $a$ is a root of $x^d -1$ and that $n= dk$. Then  $a^d = a^{dk} = 1$, so $a$ is a root of $x^n - 1$.

Title: For odd $n$ is the polynomial $X^{n-1}-X^{n-2}+...-X+1$ irreducible in $\mathbb{Q}[X]$?

Body:
Let $n$ be an odd integer. Is the polynomial $X^{n-1}-X^{n-2}+...-X+1$ irreducible in $\mathbb{Q}[X]$?

I believe that it is, but I don't know how to ptove it. I tried to use Eisenstein's criterion, but it would only work when $n$ is prime. So, how to do it?


答:
Well, variables in math are not really containers as in programming. You might think of them as rather being constants, in the computer science sense, but they are called variables because their meaning can vary, e.g. $x \in \mathbb{R}$ can be any real number, but it's just one (or rather, it's all of them), it doesn't change overtime.

In a function, the argument varies depending on what is actually "passed" to the function, to use a CS term, but again, it doesn't change at all. Not the function, nor anything else changes what a specific letter refers to after being defined (as in "Let $n \in \mathbb{N}$" or as in "$f : \mathbb{R} \to \mathbb{R}$" which also defines what $x$ in "$f(x) = x+3$" is).

Now, every other variables than the arguments of a function or the unknowns of an equation are called parameters. In your example, $a$ is a parameter.

So, yes, you could say that functions in math are 'pure', but that is a CS term afaik.

Title: Are functions in maths "pure"?

Body:
In computer science, some functions are said to be "pure", meaning that (amongst other things) they can only use variables defined in their parameters. In a mathematical context, are all functions pure or is something like this allowed?: $$
a = 3 \\
f(x) = x + a
$$
If this is allowed, then does this mean "variables" (e.g. $a$ in this case) is immutable? (also is this true even if math functions are pure?)


问:
Right triangles with integer sides
Most of you know these triples:

$3: 4 :5$

$5: 12 :13$

$8: 15 :17$

$7: 24 :25$

$9: 40 :41$

More generally we can construct such triangles such as
$$2x:x^2-1:x^2+1$$

My question is why one of the sides seems to be always prime? (When there is no common divisor)

答:
I'll add a comment on why your claim is probably false, even before you find any counterexamples.  Your formula
$$
2x : x^2 - 1 : x^2 + 1
$$

should be a red flag.  $2x$ is never prime for $x > 1$ because it is divisible by 2, and $x^2 - 1 = (x + 1)(x - 1)$ is never prime for $x > 2$ because it factors.  So your claim seems dubious from the start -- only $x^2 + 1$ even has a chance of being prime.

Title: Right triangles with integer sides


问:
Show that if $a$ and $b$ are real numbers, then $[a+b]\ge [a]+[b]$
How does one go about proving this? I know for instance that for $x\in \mathbb{R}$, then $x-1< [x]\le x$ (where $[x]$ denotes "the greatest integer in x"), so I feel compelled to use this on $a$ and $b$, that is

$a-1< [a]\le a$

$b-1<[b]\le b$

$a+b-1<[a+b]\le a+b$

Body:
$$[a+b]-([a]+[b])=[([a]+\{a\}) + ([b]+\{b\})] - [a]-[b]\\
=[a]+[b]+[\{a\}+\{b\}]-[a]-[b]  = [\{a\}+\{b\}] \ge [0]=0$$
where $\{x\} = x - [x] \in [0,1)$.


问:
Show that $d(x,y)={2|x-y|\over \sqrt{1+|x^2|}\sqrt{1+|y^2|}}$ is a metric on $\mathbb C$
Prove that the function $d:\mathbb{C×C}\rightarrow \mathbb R$ defined by $$d(x,y)={2|x-y|\over \sqrt{1+|x^2|}\sqrt{1+|y^2|}}$$ is a metric on $\mathbb C$.

My professor gave me this problem. The first three properties were easy to prove. But I couldn't prove the Triangle inequality. Just prove that part.

答:
$\mathbf{Hint:}$  $1.\,\,|1+\bar xy|\le \sqrt{1+|x^2|}\sqrt{1+|y^2|} \,\,\forall x,y\in \mathbb C. \text{Start from} (|x|-|y|)^2\ge 0$ $2.$ $(x-z)(1+y\bar y)=(x-y)(1+\bar yz)+(y-z)(1+\bar yx) \,\,\forall  x,y,z \in \mathbb C$. Just simplify the RHS & LHS.

Then take modulus on both sides of (2).


问:
Solving a Complex Diophantine Equation with One Known
I am struggling to find a way to implement Euclid's Algorithm in order to solve this diophantine equation. The $N$ will be known and the set of solutions I wish to find will be a set of decreasing $X$ solutions that satisfy $$x^2 - 4  y^2 = n.$$

When simplifying I have concluded that the solution could be as follows...
$$x^2 - 4 y^2 = (x - 2y)  (x + 2y)$$ when $n = 12$,
$$12 = (x - 2y) (x + 2y)$$
would it be possible to use Euclid's Algorithm to solve for the GCD in decreasing order?
The poposed solutions are a set of $n=12$, $x = 4$ and $y = 1$.

答:
Say $12=(x+2y)(x-2y)=ab$, where $x$ and $y$ are positive integers,

with $x+2y=a, $ and $x-2y=b$.  Then $a>b$, and $2x=a+b$.

That means $a+b$ must be even, so $a$ and $b$ are both odd or both even.

But $a$ and $b$ cannot be both odd, since $ab=12$ is even.

Therefore, $a$ and $b$ are both multiples of $2$.

Since $12=2\times2\times3=ab$, it follows that $a=2\times3$ and $b=2$,

so $x=(a+b)/2=4$ and $y=1$.


问:
Integral of rational functions.
I want to evaluate this integral:

$$\int{\frac{ax+b}{(x^2+2px+q)^n}}dx$$

The book only says to integrate by parts $\int{\dfrac{1}{(x^2+2px+q)^{n-1}}dx}$,
for simplicity if $n = 2$ I get:
$\int{\dfrac{1}{(x^2+2px+q)}dx}=\dfrac{x}{x^2+2px+q}+\int{\dfrac{2x^2+2px}{(x^2+2px+q)^2}}dx$.

Now I don't know what to do.

答:
To answer your specific question, here is a trick that will work. Note that
$$2x^2+2px=(2x^2+4px+2q)-2px-2q=(2x^2+4px +2q)-p(2x+2p)-2q+2p^2.$$
It follows that
$$\int \frac{dx}{x^2+2px+q}=\frac{x}{x^2+2px+q} +2\int \frac{x^2+2px+q}{(x^2+2px+q)^2}\,dx -p\int \frac{2x+2p}{(x^2+2px+q)^2}\,dx+ (2p^2-2q)\int \frac{dx}{(x^2+2px+q)^2}.$$
On the right, the first integral is just the integral on the left. The second integral yields to the substitution $u=x^2+2px+q$. And the third integral is the one we wanted to evaluate. So we can express $\int \frac{dx}{(x^2+2px+q)^2}$ in terms of $\int \frac{dx}{x^2+px+q}$ except in the case $p^2=q$. But in that case $(x^2+2px+q=(x+p)^2$, and the integration is easy without going through the integration by parts.

It would have been easier to make the immediate substitution $x+p=y$, but I wanted to carry on from the point you had reached.

What follows is the beginning of much longer answer I had typed. The reduction formula got unpleasant to work with, so below is only the beginning of that answer.

We have $ax+b=\frac{a}{2}(2x+2p)+ b-ap$. So our integral is
$$\frac{a}{2}\int \frac{2x+2p}{(x^2+2px+q)^n}\,dx+ (b-ap)\int \frac{dx}{(x^2+2px+q)^n}.\tag{$1$}$$
The first integral in $(1)$ is found by making the substitution $u=x^2+2px+q$.  So we are integrating a power of $u$, easy.

The second integral in $(1)$ is not so easy! We use, repeatedly if necessary, a Reduction Formula (they are discussed in great detail in Wikipedia).

For any positive integer $n$, let
$$I_n=\int \frac{dx}{(x^2+2x+q)^n}.$$
We show how to find a general expression for $I_n$ in terms of $I_{n-1}$. Thus if we start with for example $n=3$, we express $I_3$ in terms of $I_2$, then $I_2$ in terms of $I_1$.

Finally, $I_1$ breaks up into cases. Complete the square to get $x^2+2px+q=(x+p)^2+q-p^2$. If $q-p^2=0$, we had an easy integral to begin with, and the Reduction Formula was a waste of time. If $q-p^2\gt 0$, a substitution brings us to $\int \frac{1}{u^2+1}$. If $q-p^2\lt 0$,  use partial fractions.

Now we begin the reduction. As in what you did, we use integration by parts. It is easier for me to go backwards. So we calculate $I_{n-1}$ using integration by parts. Let $n\ge 2$. We have
$$I_{n-1}=\int \frac{dx}{(x^2+2px+q)^{n-1}}.$$
Let $u=\frac{1}{(x^2+2px+q)^{n-1}}$ and let $dv=dx$. Then $du=-\frac{(n-1)(2x+2p)}{(x^2+2px+q)^n}$ and we can take $v=x$. So
$$I_{n-1}= \frac{x}{(x^2+2px+q)^{n-1}}+(n-1)\int \frac{2x^2+2px}{(x^2+2px+q)^{n}}\,dx.$$
To finish, use the same trick as the one at the beginning of the post. However, you will find the calculation far more pleasant with the preliminary change of variable $y=x+p$.

Title: Integral of rational functions.


问:
Prove that $f$ is differentiable at $0$ and what happens when $\alpha = 1$?
Let $I$ be an open interval which contains $0$ and $f : I \rightarrow \mathbb{R}$. If there exists an $\alpha > 1$ such that if $|f(x)| \leq |x|^\alpha$ for all $x \in I$ , prove that $f$ is differentiable at $0$. What happens when $\alpha = 1$?

If $\alpha>1,$

Since $0 \in I$, $|f(0)|\leq 0 \implies f(0)=0$

Now $|f(x)| \leq |x|^\alpha \implies  -\ |x|^\alpha\leq f(x) \leq |x|^\alpha$

this follows $$ \frac{-\ |x|^\alpha-f(0)}{x-0} \leq \frac{f(x)-f(0)}{x-0} \leq \frac{|x|^\alpha-f(0)}{x-0}$$

By Squeeze theorem $$\lim_{x\to 0}\frac{f(x)-f(0)}{x-0}  \space \text{exist and}\space \lim_{x\to 0}\frac{f(x)-f(0)}{x-0}=f^\prime(0)=0$$

When $\alpha =1$, $|f(x)|\leq |x|\implies -1 \leq\dfrac{f(x)}{x}\leq1$

thus $$\lim_{x\to 0}\frac{f(x)-f(0)}{x-0}  \space \text{does not exist}$$

Is that correct? Am I missing something?

答:
The $\alpha=1$ case is not correct. Indeed$$-1 \leq\dfrac{f(x)}{x}\leq1$$

does not imply that

$$\lim_{x\to 0}\frac{f(x)-f(0)}{x-0}  \space \text{does not exist}$$

(consider $f=0$ !)

A correct way is to give a counterexample, and the simplest one is $f(x)=|x|$.


问:
Prove that P(A) ≤ P(B) + P(A|¬B)
I'm supposed to prove that P(A) ≤ P(B) + P(A|¬B). I already figured out that, to get to P(A|¬B) i have to use:

P(A) = P(A and B) or P(A and ¬B)

after that i am replacing P(A and B) with P(A|B)*P(B)
also i am replacing P(A and ¬B) with P(A|¬B)*P(¬B)

after that im stuck with:

P(A) = P(A|B)*P(B) + P(A|¬B)*P(¬B)

I think now i have to get rid of P(A|B) at the beginning of the formula and (¬B) at the end, but can not figure out how to.

答:
To show this use that the probability measure is less or equal to $1$.
$$P(A)=P(A\cap B)+P(A\cap B^\complement)=P(A|B)P(B)+P(A|B^\complement)P(B^\complement)\leq P(B)+P(A|B^\complement).
$$

Title: Prove that P(A) ≤ P(B) + P(A|¬B)


问:
Show that characters are irreducible.
I would like to prove the following:

We have a group $G$ and:
   $$\chi:G\rightarrow \mathbb{C}$$$$ \tilde{\chi}: G/N \rightarrow\mathbb{C}$$
  characters of groups $G$ and $G/N$ respectively, where $\tilde{\chi}$ is given by $\tilde{\chi}(gN)=\chi(g)$ and additionally: $N\leq \ker(\chi)$. Prove that $\chi$ is a irreducible character if and only if $\tilde{\chi}$ is a irreducible character of $G/N$.

My try:

$$\text{(for irreducible characters)}\quad 1=(\chi,\chi)=\frac{1}{|G|}\sum_\limits{g \in G} \chi(g)\overline{\chi(g)}=  $$

$$\text{Here we use the definition } \tilde{\chi}(gN)=\chi(g) $$
$$=\frac{1}{|G|}\sum_\limits{g \in G} \tilde{\chi}(gN)\tilde{\chi}(gN)=\frac{1}{|G/N||N|}\sum_\limits{g \in G} \tilde{\chi}(gN)\tilde{\chi}(gN)=$$
$$\text{Here I'd like to make the substitution: } \sum_\limits{g \in G} \rightarrow \sum_\limits{gN \space \in  \space G/N} $$

$$\text{My asumption:} \sum_\limits{g \in G}=|N|\sum_\limits{gN \space \in \space G/N}$$

$$=\frac{1}{|G/N||N|} |N|\sum_\limits{gN \space \in \space G} \tilde{\chi}(gN)\tilde{\chi}(gN)=\frac{1}{|G/N|} \sum_\limits{gN \space \in \space G} \tilde{\chi}(gN)\tilde{\chi}(gN)=(\tilde{\chi},\overline{\tilde{\chi}})=1$$

My Question:

Is my assumption regarding the substitution above correct? May I substitute a sum $\sum_\limits{g \in G}$ with $|N|\sum_\limits{gN \space \in \space G/N}$? Because intuitively I know that to each element $gN \in G/N$ in the sum $\sum_\limits{gN \space \in \space G/N}$ correspond $|N|$ elements $g \in G$ in >
  the sum $\sum_\limits{g  \in G}$, see for example the table below:

Example borrowed from: https://kconrad.math.uconn.edu/blurbs/grouptheory/coset.pdf .

答:
You need to use that $N \subseteq ker(\chi)$, which implies that $\chi$ is constant on cosets of $N$. For let $\frak{X}$ be a representation that affords $\chi$, then for all $g \in G$, $n \in N$, one has $\frak{X}$$(gn)$=$\frak{X}$$(g)$$\frak{X}$$(n)$=$\frak{X}$$(g)$$\frak{I}$=$\frak{X}$$(g)$, whence $\chi(gn)=\chi(g)=\chi(ng)$. Now choose a transversal set $T$ for $N$ in $G$ (meaning $T$ contains exactly one element of each coset of $N$). Observe that $G=\bigcup_{t \in T,n \in N}tn$ and write $\overline{g}$ for $gN$. Then
$$[\tilde\chi,\tilde\chi]_{G/N}=\frac{1}{|G:N|}\sum_{\overline{g} \in G/N}|\tilde\chi(\overline{g})|^2=\frac{|N|}{|G|}\sum_{\overline{g} \in G/N}|\chi(g)|^2\\=\frac{|N|}{|G|}\sum_{t \in T}|\chi(tn)|^2=\frac{|N|}{|G|}\sum_{t \in T}|\chi(t)|^2=\frac{|N|}{|G|}\frac{1}{|N|}\sum_{n \in N}\sum_{t \in T}|\chi(t)|^2=\\\frac{1}{|G|}\sum_{n \in N}\sum_{t \in T} \chi(tn)=\frac{1}{|G|}\sum_{g \in G}|\chi(g)|^2=[\chi,\chi]_G=1.$$

Title: Show that characters are irreducible.


问:
Prove that if $T:V \rightarrow U$ is an invertible linear transformation then the inverse $T^{-1}: U \rightarrow V$ is also linear
Prove that if $T:V \rightarrow U$ is an invertible linear transformation then the inverse $T^{-1}: U \rightarrow V$ is also linear

So, $T$ is linear and thus $T(v_1+v_2) = T(v_1)+T(v_2)$ for all $v_1,v_2 \in V$. Also, $T$ is invertible and so we can write $T^{-1}T(v)=v$ for all $v \in V$. I'm a bit confused trying to put this all together, help appreciated!!

Body:
$T^{-1}(v+w) \overset{?}{=} T^{-1}(v)+T^{-1}(w)$

Let's apply $T$ on both side we get $w+v = T(T^{-1}(v)+T^{-1}(w)) \overset{T \hspace{0.1cm} \text{linear}}{=} T(T^{-1}(v))+T(T^{-1}(w))$ true.


问:
Finding last coefficient of a multivariate polynomial in $GF(2)$ in polynomial time
This problem was simplified by Alex Ravsky (thanks!). For the original problem see below.

Simplified Problem

With $f(k_1,k_2,\ldots,k_n)$ a polynomial over $GF(2)$, find the value of the coefficient of the term that contains all variables $k_i$ (in other words the coefficient $a\in GF(2)$ of the term $a\prod_{i=1}^n k_i$). There is only one such term in the simplified polynomial because $\forall x\in GF(2),n\in \mathbb{N}: x^n=x$. However, $f$ is too long to be multiplied out completely in practice and can only be represented as a tree of nested sums and products (in which most leaves are present at multiple points throughout the tree). Even though this simpler than the original problem, finding that coefficient algorithmically in polynomial time is still proving challenging and I would appreciate all the help I can get! :D

Original Problem

Essentially I have a nested sum in the form
$$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)$$
where $f(k_1,k_2,\ldots,k_n)$ is a multivariate polynomial over $GF(2)$ which can only be represented as a tree of nested sums and products because multiplying it out would lead to on average $2^{n-1}$ terms (the number of possible terms is $2^n$ because in $GF(2)$ every $k_i=k_i^j$ for $j\in\mathbb{N}$ and the number of possible variable combinations $1;k_1;k_2;k_2k_1;k_3;k_3k_1;k_3k_2;k_3k_2k_1;\ldots$ is $2^n$).

Finding the value of $f$ for a specific set of $k_i$ is trivial, but the exponential time complexity of doing this $2^n$ times (the total number of elements in our nested sum) is a bit of a buzzkill. I'm a patient guy but not enough so to wait longer than the age of the universe, so I'd much prefer to do this in polynomial time :)

So far, I've tried reordering the sum to
$$\sum_{k_1=0}^1 \ldots \sum_{k_{i-1}=0}^1 \sum_{k_{i+1}=0}^1 \ldots \sum_{k_n=0}^1 \sum_{k_i=0}^1 f(k_1,k_2,\ldots,k_n)$$
for some specific $i$ and finding $a,b \in GF(2)$ such that $f(k_1,k_2,\ldots,k_n)=k_ia+b$ (where $a$ and $b$ are each polynomials independent of $k_i$ represented as a tree similar to $f$; this is trivial to do for a single $k_i$) because in $GF(2)$ I can then do
$$\sum_{k_i=0}^1 f(k_1,k_2,\ldots,k_n)=\sum_{k_i=0}^1 (k_ia+b)=0a+b+1a+b=a+b+b=a$$
which means that
$$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)=\sum_{k_1=0}^1 \ldots \sum_{k_{i-1}=0}^1 \sum_{k_{i+1}=0}^1 \ldots \sum_{k_n=0}^1 a$$
which in turn means that I've halved the number of elements of the nested sum. However, the complexity of $a$ is usually higher than the complexity of $f$, because when isolating $k_i$ from $f$, the following happens each time a product is encountered in the tree representing $f$, of which at least two factors are dependent on $k_i$:

Let $k_ia_1+b_1$ and $k_ia_2+b_2$ be two such factors from which $k_i$ is to be isolated such that we obtain an $a_0$ and $b_0$ with $k_ia_0+b_0=(k_ia_1+b_1)(k_ia_2+b_2)$. Finding
$$(k_ia_1+b_1)(k_ia_2+b_2)=k_i^2a_1a_2+k_ia_1b_2+k_ia_2b_1+b_1b_2=k_ia_1a_2+k_ia_1b_2+k_ia_2b_1+b_1b_2=k_i(a_1a_2+a_1b_2+a_2b_1)+b_1b_2$$
is simple, however, even if this were the closest such product to the base of the tree, which would mean that $b_0$ falls away due to the mechanism described above, and even if I rewrite $a_0=a_1a_2+a_1b_2+a_2b_1=(a_1+b_1)(a_2+b_2)+b_1b_2$ to minimize the number of products added to the tree, I've just added at least two products to the tree, each of which will add at least two more products to the tree when I isolate the next $k_j$ because $a_1,a_2,b_1,$ and $b_2$ are almost certain to be dependent on $k_j$. Therefore, we're back to the exponential time complexity. Unfortunately, I have not been able to find a way to get around this problem.

Because we're in $GF(2)$, of course, this problem stays identical if all of the equalities above are replaced with congruences modulo $2$ in $\mathbb{Z}$. I don't actually know if it's easier to think of the problem in such terms, however.

Thank you so much for making it this far through my lengthy question! I very much look forward to reading your ideas :)

答:
Given $f$, put $S(f)=\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)$. As I understood, the complexity of an algorithm calculating $S(f)$ depends on the representation of $f$. Indeed, put $\Bbb F=GF(2)$ and $[n]=\{1,\dots,n\}$. Since $x^j=x$ for each $x\in\Bbb F$ and $j\in\mathbb{N}$, there exists a polynomial $\bar f\in\Bbb F[x_1,\dots,x_n]$ such that $\bar f(x_1,\dots,x_n)=f(x_1,\dots,x_n)$ for each $x_1,\dots,x_n\in\Bbb F$ and $\bar f$ has degree at most $1$ with respect to each variable. Then $\bar f(x_1,\dots,x_n)=\sum_{A\subset [n]} a_A\prod_{i\in A} x_i$, where $a_A$’s belong to $\Bbb F$ and, for the convenience,
$\prod_{i\in \varnothing} x_i=1$. Remark that $\prod_{i\in A} k_i$ equals $1$, if $k_i=1$ for each $i\in A$, and equals $0$, otherwise. Then
$$S(f)=\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 f(k_1,k_2,\ldots,k_n)=$$
$$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 \bar f(k_1,k_2,\ldots,k_n)=$$
$$\sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1 \sum_{A\subset [n]} a_A\prod_{i\in A} k_i=$$
$$\sum_{A\subset [n]} \sum_{k_1=0}^1 \sum_{k_2=0}^1 \ldots \sum_{k_n=0}^1  a_A\prod_{i\in A} k_i=$$
$$\sum_{A\subset [n]}2^{n-|A|} a_A=
a_{[n]}.$$

That is if $f$ is represented as a sum of monomials then we can easily calculate $S(f)$.

On the other hand, if $f$ is represented as a tree of nested sums and products then, as I understood, the calculation of $S(f)$ can be hard. Namely, elements of $\Bbb F$ can be considered as Boolean constants. Using equalities $x \wedge y=xy$ and $x\vee y=x+y-xy$, and $\neg x=1-x$ we can consider Boolean formulas depending on $x_1,\dots, x_n$ as as polynomials from $\Bbb F[x_1,\dots,x_n]$ and vise versa. Then $S(f)=1$ iff the Boolean formula corresponding to $f$ has an odd number of variable assignments making it true.

Ryan Williams noted here that “the problem "Parity-SAT" (often written as $\oplus SAT$ in the literature) is the problem of determining whether or not a given Boolean formula has an odd number of assignments. It is well-studied, and is complete for the class $\oplus P$ which contains all languages of the form {$x ~|~ $ there are an odd number of accepting computation paths in $N(x)$}, where $N$ is a nondeterministic polynomial time machine”. See here about the complexity class $\oplus P$. In particular, it contains the graph isomorphism problem, which is not known to be solvable in polynomial time nor to be NP-complete. On the other hard, Parity SAT is NP-hard under randomized reductions, see [VV, p.92].

References

[VV] L.G. Valiant, V.V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science 47 (1986) 85–93.


问:
General Linear Groups with Homomorphisms

Let $G=\mathrm{GL}_n(\mathbb R)$ and $H=\mathbb R^*$. Let $\phi : G=\mathrm{GL}_n(\mathbb R) \rightarrow \mathbb R^*$ be the map defined by $\phi(A)=\det(A)$. Show that $\phi$ is a group homomorphism.

If $\phi : G \rightarrow H$ is a group homomorphism, then the set $\{g \in G : \phi(g)=e_H\}$ where $e_H$ is the identity element of $H$ is called the kernel of $\phi$. Show that the kernel of $\phi$ is a subgroup of $G$.

答:
For the first part, you must show that if $A\in\text{GL}_n(\Bbb R)$, then $\det(A)\in\Bbb R$ and $\det(A)\ne0$, and that for $A,B\in\text{GL}_n(\Bbb R)$, we have $\det(AB)=\det(A)\det(B)$.

You should already know of at least one way to show that a subset $K$ of a group $G$ is a subgroup of $G$. Use such a way to show that the kernel of $\phi$ is a subgroup of $G$ if $\phi:G\to H$ is a group homomorphism.


问:
Find the volume of the set in $\mathbb{R}^3$ defined by the equation $x^2 + y^2 \leq z \leq 1 + x + y$.
Let $D=\left\{\left(x,y,z\right) \in \mathbb{R}^3: x^2 + y^2 \leq z \leq 1 + x + y \right\}$. I tried to integrate with cartesian coordinates, so that

$$\iiint_Ddxdydz = \int_{x=\frac{1-\sqrt{5}}{2}}^{{\frac{1+\sqrt{5}}{2}}} \int_{z=x^2}^{1+x} \left( \int_{y=z-(1+x)}^{\sqrt{z-x^2}}dy\right)dxdz$$

but the calculation seems to be quite laborious. Is there a way to solve it easily, maybe with another coordinate system?

Edit: After your suggestions I finally solved the problem. If someone is interested in the calculation itself I'll report the main steps below:

$$\int_{\theta=0}^{2\pi} \int_{r=0}^{\sqrt{\frac{3}{2}}}\left(\int_{z=r^2+r(\sin\theta+\cos\theta)+\frac{1}{2}}^{r(\sin\theta+\cos\theta)+2}dz\right)rdrd\theta = \int_{\theta=0}^{2\pi} \int_{r=0}^{\sqrt{\frac{3}{2}}} \left( \frac{3}{2}r-r^3\right)drd\theta = \pi\int_{0}^{\frac{3}{2}}\left(\frac{3}{2}-t\right)dt = \frac{\pi}{2} \left[3t-t^2\right]_{0}^{\frac{3}{2}}=\frac{9\pi}{8}$$

答:
$\textbf{Hint}$: Use this modified cylindrical coordinate system:

$$\begin{cases}x = r\cos\left(\theta-\frac{\pi}{4}\right)\\ y = r\sin\left(\theta-\frac{\pi}{4}\right)\\ z = z \\\end{cases}$$

What does the change do? Does it alter the Jacobian (which measures how much the volume is distorted between coordinate systems) ?


答:
Since the inverse is defined on $U$ I'm assuming $T$ is bijective. So take $u_1, u_2 \in U$. Then $u_1 = T(v_1)$ and $u_2 = T(v_2)$ for some $v_1,v_2\in V$. Now

$$T^{-1}(u_1 + u_2) = T^{-1}\left(T(v_1)+T(v_2)\right) = T^{-1}\left(T(v_1+v_2)\right)= v_1+v_2 = T^{-1}(u_1) + T^{-1}(u_2)$$

as required.

Body:
Prove that if $T:V \rightarrow U$ is an invertible linear transformation then the inverse $T^{-1}: U \rightarrow V$ is also linear

So, $T$ is linear and thus $T(v_1+v_2) = T(v_1)+T(v_2)$ for all $v_1,v_2 \in V$. Also, $T$ is invertible and so we can write $T^{-1}T(v)=v$ for all $v \in V$. I'm a bit confused trying to put this all together, help appreciated!!


问:
How to calculate the area in which a movable point can be over time given a maximum acceleration limit?
My full question is: There is a movable point $P$ in a flat 2D space. The magnitude of its acceleration cannot exceed $a_{max}$. Given its initial position to be at $(0,0)$, and its initial velocity to be $(v_x,0)$ at $t=0$, an area $A$ evolving with time consists of all possible positions $P$ can be at time $t$. Describe $A$ or its boundary with respect to time, using $a_{max}$ and $v_x$.

I guess the first step is to be given another point $(x,y)$, and calculate the fastest way to go there under the acceleration limit, then calculate the minimum time required. I don't know how to do that. Partial or full solutions are both appreciated.

答:
Let's define a new coord system in which the origin is moving to the right with velocity $(v_x, 0)$ in the old coordinate system. In this NEW system, the question is the same as the original, but the initial velocity is zero.

The set of reachable positions, at time $t$ in the new coordinate system, consists of the interior of a disk of radius $\frac{a}{2} t^2$ (by ... well... integrating).

So in the old coordinate system, the set of reachable positions is the disk of radius $r = \frac{a}{2}t^2$, with center at $(tv_x, 0)$.


问:
Universal property of an embedding.
In Tom Dieck’s Algebraic Topology, proposition 1.2.1 it says the following:

Let $i:Y\to X$ be an injective set map between spaces. The following are equivalent:
  (1) $i$ is an embedding.
  (2) A set map $g:Z\to Y$ from any topological space $Z$ is continuous if and only if $ig: Z\to X$ is continuous.

The author calls this proposition the “universal property of an embedding”, while I struggled to find the right categories to formulate it. I think a possible construction for the universal object in this case should be “the set of all embeddings from $X$ to $Y$”, but I cannot find any category to contain this as an object. Could anyone give an idea please?

答: $(Y,i)$ is final in the category of all $(Z,h)$ such that $h$ is continuous from $Z$ to Im $i$ (i.e. continuous to $X$ and Im $h \subset$ Im $i$), where morphisms from $(Z,h)$ to $(Z',h')$ are those $f$ from $Z$ to $Z'$ such that $h=h'\circ f$.

Title: Universal property of an embedding.


问:
Inverse function theorem and tangent space differentials
Having some difficulty with the following proposition,

Consider a $ C^\infty $ map between manifolds $ F:N \rightarrow M $ with $ \text{dim} \, N = \text{dim} \, M $, then $ F $ is locally invertible at some point $ p \in N $ if $ F_{*,p} : T_pN \rightarrow T_{F(p)}M $ is an isomorphism.

Now, I think I understand the general idea of how to show this, but am stuck on a finer point. Of course, the pushforward of a basis vector on $ T_pN $ given charts about $ p  \in N $ and $ F(p) \in M $, $ (U, x^1,...,x^n) $ and $ (V,y^1,...,y^n) $ respectively,
$$ F_{*,p} \bigg( \frac{\partial}{\partial x^i} \bigg|_p\bigg) = \sum_j^n \frac{\partial F^j}{\partial x^i}(p) \frac{\partial}{\partial y^j} \bigg|_{F(p)} \tag{1} $$
with $ F^j := y^j \circ F $. My intuition is to recall that for a linear operator $ T: \mathbb{R}^n \rightarrow \mathbb{R}^n $ such that $ T(v) = A v $ for $ v \in \mathbb{R}^n $ and $ A \in \text{GL}(n,\mathbb{R}) $, then $ T $ is invertible iff $ T $ is an isomorphism, in the hopes that similar logic can be applied to more abstract vector space transformations.

So, naturally, I want to argue that the pushforward of $ \partial / \partial x^i |_p $ is represented by the matrix $ \partial F^j / \partial x^i |_{F(p)} $, and the differential being an isomorphism is equivalent to the inverse matrix existing (which means that $ \text{det}[\partial F^j / \partial x^i |_{F(p)}] \neq 0 $), and thus $ F $ is invertible via the inverse function theorem on manifolds.

But $ F_{*,p} $ is then acting in a form like $ T(v) = A w = z $, with $ v \in T_pN $ and $ w,z \in T_{F(p)}M $. I'm unable to prove an analogue of the variant with $ T $ on $ \mathbb{R}^n $, because I can't just naively toss around $ A^{-1} $ on $ z $ to get an element in $ T_pN $, as $ w $ is in $ T_{F(p)}M $! The linear combination is of basis vectors $ \partial / \partial y^j $, and not $ \partial / \partial x^i $, which exist in different spaces, no? How can I prove that $ F_{*,p} $ is an isomorphism $ \iff \text{det}[\partial F^j / \partial x^i |_{F(p)}] \neq 0 $ to complete the proof?

答:
Remember that $\frac{\partial F^j}{\partial x^k}(p):=\frac{\partial G^j}{\partial r^k}\phi (p)$ for $G:=\psi\circ F\circ \,\phi^{-1}$ where $\phi:=(x^1,\ldots ,x^n),\,\psi :=(y^1,\ldots ,y^n)$ and $r:=(r^1,\ldots ,r^n)$ is the Cartesian coordinate system in $\mathbb{R}^n$. Then as $\phi $ and $\psi $ are local diffeomorphisms of $M$ and $N$ respectively with $\mathbb{R}^n$ then $G:\mathbb{R}^n\to \mathbb{R}^n$ is an smooth map and
$$
\det\left[\frac{\partial F^j}{\partial x^k}(p)\right]=\det\left[\frac{\partial G^j}{\partial r^k}\phi (p)\right]
$$
Therefore if the determinant is not zero the derivative of $G$  at the point $\phi(p)$, that is $G_{*,\phi(p)}$, is an automorphism of $\mathbb{R}^n$ and so it is invertible. Now observe that $\phi_*$ and $\psi_*$ are isomorphisms (because they are assumed to be diffeomorphisms) and by the chain rule we have that $F_{*,p}=\psi _{*,F(p)}^{-1}\circ G_{*,\phi(p)}\circ  \phi _{*,p}$, then as $F_{*,p}$ is composition of invertible linear maps its invertible.

By the other hand, if the determinant is zero then $G_{*,\phi(p)}$ is not invertible and so it kernel is not trivial, so there is some $x\in \mathbb{R}^n\setminus \{0\}$ such that $G_{*,\phi(p)}x=0$, and so $F_{*,p}((\phi_{*,p}) ^{-1}x)=0$, so $F_{*,p}$ is not invertible because, being $\phi_*$ an isomorphism, $(\phi_{*,p}) ^{-1}x\neq 0$ when $x\neq 0$.∎


答:
HINTS

You have $G=\text{GL}(n,\mathbb{R})$ with the operation of matrix multiplication and $H=\mathbb{R}^*$ with the operation of multiplication. You gave $\det : \text{GL}(n,\mathbb{R}) \to \mathbb{R}^*$. You need to show that composing two elements of $G$ and then moving it over to $H$ gives the same as moving two elements of $G$ over to $H$ and composing them there. Can you show that $\det(AB) = \det(A)\det(B)$?

To show that $\ker \phi < G$, just need to check all of the group axioms. If $a,b \in \ker \phi$, then can you show that $ab \in \ker\phi$, i.e. if $\phi(a) = \phi(b) = 1_H$, can you show that $\phi(ab) = 1_H$? Associativity is inherited from $G$. Next you need to show that $1_G \in \ker\phi$, i.e. $\phi(1_G) = 1_H$. Finally, if $a \in \ker\phi$, can you show that $a^{-1} \in \ker\phi$?

Title: General Linear Groups with Homomorphisms

Body:
Let $G=\mathrm{GL}_n(\mathbb R)$ and $H=\mathbb R^*$. Let $\phi : G=\mathrm{GL}_n(\mathbb R) \rightarrow \mathbb R^*$ be the map defined by $\phi(A)=\det(A)$. Show that $\phi$ is a group homomorphism.

If $\phi : G \rightarrow H$ is a group homomorphism, then the set $\{g \in G : \phi(g)=e_H\}$ where $e_H$ is the identity element of $H$ is called the kernel of $\phi$. Show that the kernel of $\phi$ is a subgroup of $G$.


问:
Proving that $f(x) \rightarrow \infty$ as $x \rightarrow \infty$ if $f'(x) \gt K \gt 0 \forall x$...
I would appreciate a review or a different approach:

The question: Prove that if $f$ is derivable for $x \gt a$, and there exists $0 \lt K \in \mathbb{R}$ such that $f'(x) \gt K \forall x \gt a$, then $f(x) \rightarrow \infty$  as $x \rightarrow \infty$.

My proof: Let $f$ be a derivable (thus continuous) function for $x \gt a$, and let $0 \lt K$ be a real number such that $f'(x) \gt K$ for all x's in the mentioned domain.
According to the "Lagrange theorem" we can say that, for every $x$ in the domain and every $c \in (a,x)$ the following is true:
$$\frac{(f(x)-f(a))}{x-a} = f'(c) \gt K \implies f(x) \gt Kx - Ka + f(a).$$
Both $f(a)$ and $-Ka$ are constants. In order to complete our proof, we must show that for every $M\gt0$, there is $m\gt0$, such that for every $x\gt m: f(x)> M$:
Let $M>0$. We'll choose $m = \frac{M+Ka-f(a)}{K}$, and see that for every $x\gt m:$
$$f(x) > Kx - Ka + f(a) > Km - Ka + f(a) = M.$$
Just as required.

答:
Just one observation:

If $x>m=\frac{M+Ka−f(a)}{K}$ is not neccesary true that $x>a$, so the inequality $f(x)>Kx−Ka+f(a)$ is not justified. But if you choose $m=\max\{\frac{M+Ka−f(a)}{K},a\}$, all your inequalities are true.


问:
$f(f(f(x)))=x$, does it necessarily imply $f(x)=x$?

[TIFR GS-2017] Let $f$ be a continuous function on $\mathbb R$ satisfying the relation
$$f(f(f(x))) = x\ \forall x \in \mathbb R$$ Prove or disprove that $f$ is the identity function.

There is a solution to this question in here, but I was trying in this way...

Suppose $f$ is continuous and not identity function. Then we can find some point $c \in \mathbb R$ such that there is a neighbourhood $N_\delta(c)$, where $f(x) \neq x\ \forall x \in \mathbb N_\delta(c)$.

Then two cases arise.

$\underline{Case (i)}:$ $f(f(x))=f(x)$, but that means $f(f(x))=f(x)\neq x$, hence $f(f(f(x))) = f(f(x)) =f(x) \neq x$.

Hence we have a contradiction.

$\underline{Case (ii)}:$ $f(f(x)) \neq f(x)$.

Suppose $p$ be such a point where it holds. Then $f(f(p)) \neq f(p)$. Suppose $m \in \mathbb R$ s.t. it is in between $f(f(p))$ and $f(p)$. Then by IMVP, there is some $q$ between $p$ and $f(p)$ s.t. $f(q) = m$.

After this scene, I am out of ideas to proceed further. We can't say that $f(p) \in N_\delta(c)$. Any help would be appreciated.

答:
Just for others reading this post, the condition of continuity on $f(x)$ is extremely important to this question. If this condition is not included, then $f(x)$ need not be the identity. In fact, going down the rabbit hole of linked questions, the accepted answer at the bottom gives the example

$$f(x)=\frac{x-\sqrt{3}}{x\sqrt{3}+1}$$

which satisfies $f(f(f(x)))=x$. However, this obviously is not continuous on $\mathbb{R}$ and as such is not a counterexample to the question presented in OP's post. To answer this question, consider the function $g(x)=f(x)-x$. Since both $f(x)$ and $x$ are continuous, this function is a continuous function. We will show that it is identically zero. First, note that there must be $x_0$ such that $g(x)=0$. If this were not the case, then either $f(x)>x$ or $f(x)<x$ for all $x\in\mathbb{R}$. In the first case, this would then imply

$$x=f(f(f(x)))$$

$$\Rightarrow f(f(x))<x$$

$$\Rightarrow f(x)<x$$

$$\Rightarrow x<x$$

which is obviously a contradiction. The case where $f(x)<x$ follows in the same manner. Now, the places where $g(x)>0$ form a countable sequence of open intervals. There are four possibilities for the open interval with $x_0$ as an endpoint:

$$(x_0,\infty)$$

$$(x_0,b)$$

$$(-\infty,x_0)$$

$$(a,x_0)$$

(where $a<x_0<b$) and it is possible that multiple of these apply. In addition, there are the possibilities  that $g(x)=0$ for $x\in [a,b]$ where $a<x_0<b$, $g(x)=0$ for $x\in [a,\infty)$ where $a<x_0$, $g(x)=0$ for $x\in (-\infty,b]$ where $x_0<b$, or $g(x)=0$ for $x\in\mathbb{R}$. However, as the argument for these seven cases (as the eight case is what we are trying to prove) are basically identical, we will only prove the first possibility. Thus, consider the interval $(x_0,\infty)$. In this interval, $g(x)>0$ or $g(x)<0$. In the first case, let $\epsilon_n>0$ be any sequence that approaches $0$. Then eventually

$$x_0+\epsilon_n=f(f(f(x_0+\epsilon_n)))>f(f(x_0+\epsilon_n)>f(x_0+\epsilon_n)>x_0+\epsilon_n$$

As this is a contradiction, we conclude that this open interval cannot actually exist and therefore $g(x)=0$ for $x\in (x_0,\infty)$. This argument can be expanded to the other four cases above, and from there expanded by induction to the entire real number line. We conclude that $f(x)=x$.


问:
For Riemann integral partitions, does it matter whether $f$ is evaluated at a point in $(t_{i-1},t_i)$ or $[t_{i-1},t_i]$?

Definition $:$ Let $F$ be a Banach space. A function $f : [a,b] \longrightarrow F$ is said to be Riemann integrable if there exists $\int_{a}^{b} f \in F$ such that for any $\varepsilon \gt 0$ there exists $\delta \gt 0$ such that for any partition $\mathfrak P = \{a = t_0 \lt t_1 \lt t_2 \lt \cdots \lt t_n = b \}$ with $\left \|\mathfrak P \right \| \lt \delta$ and for any choice of $\xi_i \in (t_{i-1},t_i),$ for $i = 1, 2, \cdots, n$ we have $$\left \|\int_{a}^{b} f - \sum\limits_{i=1}^{n} f(\xi_i) (t_i - t_{i-1}) \right \|_{F} \lt \varepsilon.$$ In this case we say that $\displaystyle {\int_{a}^{b} f}$ is the Riemann integral of $f$ on $[a,b].$

Now my question is as follows $:$

In the above definition of Riemann integral will it make any difference if instead of $\xi_i \in (t_{i-1},t_i)$ we stipulate $\xi_i \in [t_{i-1},t_i]\ $? Any suggestion in this regard will be highly appreciated.

Thanks in advance.

答:
It does not hurt anything to allow for $\xi$ to be in closed subintervals. A kind of manual way to see this is to connect the Riemann sum on a tagged partition with tags at endpoints to a Riemann sum on a tagged partition without tags at endpoints. One way to do that is to split into two cases depending on whether two neighboring $\xi$'s are the same or not.

If they are the same, merge those two subintervals; doing this all over results in a partition with mesh $2\delta$ which still goes to zero, and the Riemann sum on this tagged partition is exactly the same as the Riemann sum you already had.

If they are not the same, enlarge the subinterval which had $\xi$ at the endpoint by a little bit, at the expense of its neighbor. As long as the sum of all the enlargement lengths is less than $\varepsilon/4M$ where $M$ is the bound on $f$, the resulting change in the Riemann sum will be less than $\varepsilon$.


答: Define $$x=r\cos(\theta)+\frac{1}{2}$$ $$y=r\sin(\theta)+\frac{1}{2}$$ $$z=z$$ The volume of your solid is the triple integral $$\int_0^{2\pi} \int_0^{\sqrt{3/2}} \int_{r^2+r\big(\sin(\theta)+\cos(\theta)\big)+\frac{1}{2}}^{r\big(\sin(\theta)+\cos(\theta)\big)+2}rdzdrd\theta$$

Title: Find the volume of the set in $\mathbb{R}^3$ defined by the equation $x^2 + y^2 \leq z \leq 1 + x + y$.

Body:
Let $D=\left\{\left(x,y,z\right) \in \mathbb{R}^3: x^2 + y^2 \leq z \leq 1 + x + y \right\}$. I tried to integrate with cartesian coordinates, so that

$$\iiint_Ddxdydz = \int_{x=\frac{1-\sqrt{5}}{2}}^{{\frac{1+\sqrt{5}}{2}}} \int_{z=x^2}^{1+x} \left( \int_{y=z-(1+x)}^{\sqrt{z-x^2}}dy\right)dxdz$$

but the calculation seems to be quite laborious. Is there a way to solve it easily, maybe with another coordinate system?

Edit: After your suggestions I finally solved the problem. If someone is interested in the calculation itself I'll report the main steps below:

$$\int_{\theta=0}^{2\pi} \int_{r=0}^{\sqrt{\frac{3}{2}}}\left(\int_{z=r^2+r(\sin\theta+\cos\theta)+\frac{1}{2}}^{r(\sin\theta+\cos\theta)+2}dz\right)rdrd\theta = \int_{\theta=0}^{2\pi} \int_{r=0}^{\sqrt{\frac{3}{2}}} \left( \frac{3}{2}r-r^3\right)drd\theta = \pi\int_{0}^{\frac{3}{2}}\left(\frac{3}{2}-t\right)dt = \frac{\pi}{2} \left[3t-t^2\right]_{0}^{\frac{3}{2}}=\frac{9\pi}{8}$$


问:
Finding $f \colon R_+ \to R_+$ such that $sf = f \circ g$, for $g$ strictly increasing
Suppose that $g:R_+\mapsto R_+$ is a strictly increasing and smooth function and let $s$ be a positive real number. I am looking for a function $f:R_+\mapsto R_+$ that satisfies
$$sf(x)=f(g(x))$$
for all $x\geq0$. This problem arises if I want to characterize the extremals of an optimal control problem.

I can find $f$ when $g$ is linear, i.e., $g(x)=ax+b$ with $a>0$. More specifically, I get
$$f(x)=C\left[1-\frac{(1-a)x}b\right]^{\ln s/\ln a}$$
provided that $a\neq1$ and $b\neq0$. Here, $C$ is an arbitrary real number.

If $a=1$ and $b\neq0$, then I get
$$f(x)=Cs^{x/b},$$
and if $a\neq1$ and $b=0$, then I have
$$f(x)=Cx^{\ln s/\ln a}.$$

Of course, I do not know whether these solutions are the only ones, but I would conjecture that they are the only smooth ones.

Do you know of any method which would help me solve the functional equation when $g$ is non-linear? Can you think of other examples (i.e., other functions $g$), for which the functional equation can be solved?

答:
Edit: I didn't quite understand the notation, therefore my old answer is mostly outdated. Still, despite a clarification, the function $f$ that you gave may still be undefined whenever $1-\frac{(1-a)x}{b} < 0$.

Other than that, here is what you could try: use a Taylor expansion to derive certain properties of $f$. Here is an example:
$$f(g(x)) = f(y_0) + [g(x) - y_0]f'(y_0) + ...$$
Plugging this into the functional equation yields, assuming $f$ is smooth enough around $x=0$ for example (you can take any other value for $x$, but that's the easiest one for the next formulas):
$$s[f(0) + xf'(0) + ...] = f(y_0) + [g(x) - y_0]f'(y_0) + ...$$
It now comes down to finding a good choice for $y_0$. For example, taking $y_0 = g(0)$, assuming $g$ is smooth enough around $x=0$ and using yet another Taylor expansion to simplify $g(x) - y_0$ yields
$$s[f(0) + xf'(0) + ...] = f(g(0)) + xg'(0)f'(g(0)) + ...$$
so that after comparing the coefficients you get the conditions
$$sf(0) = f(g(0))$$
and
$$sf'(0) = g'(0)f'(g(0))$$
for example for the first two orders. If you take the case where $g(x) = ax+b$, all these conditions can be summarized as
$$sf^{(n)}(0) = a^nf^{(n)}(b)$$
where $f^{(n)}$ denotes the $n$-th derivative of $f$ for $n \geq 0$, where $f^{(0)} = f$. So, any function that satisfies this condition for every $n\geq 0$ will satisfy your functional equation. For $s = a = 1$, this can be every $b$-periodic function, already showing that a solution is certainly not unique, even among smooth solutions, which makes searching for a specific one that much more complicated.

From there, you can for example assume that $f$ has a Fourier transform $\widehat{f}$ which can be transformed back to $f$. If you assume all of that, then if I'm not mistaken you can rewrite the condition as
$$\int^{\infty}_{-\infty}(s-a^ne^{2\pi i b y})y^n\widehat{f}(y) dy = 0,$$
(using the fact that $\widehat{f^{(n)}}(y) = (2\pi i y)^n \widehat{f}(y)$). This integral formula then has to hold for every $n$. This still gives you a system of infinitely many equations, but at least here you have $f$ (or rather, $\widehat{f}$) appearing only once. Note that this holds when $a = s = 1$ and $f$ is a $b$-periodic function.

For polynomial $g$, using a similar path should lead you to somewhat similar formulas, with more factors however.

Another example that a solution may not be unique or may be trivial, depending on $g$ and $s$: If $g(x) = x$, then for $s=1$ any function satisfies the equation. If $s \neq 1$, only $f(x) \equiv 0$ satisfies it.


问:
Approach ideas for the integral $\int\frac{dx}{(x^4-16)^2}$
Well, the title sums it up pretty well. I'm in search for some smart approach ideas for solving this indefinite integral:
$$\int\frac{dx}{(x^4-16)^2}$$

I know one that would work for sure, namely partial fraction decomposition, but it gets really heavy when regrouping the coefficients for the powers of $x$ and then solving an $8\times8$ system of linear equations. It will eventually work, but I suspect there is something more ingenuine behind this problem.

I also tried all sorts of trigonometric substitutions and formulations, but that added square power really is a bummer to it all.

I'm generally open to any exchange on the topic and would be glad to hear some advice in such situations. Many thanks in advance!

Body:
As $x^4-2^4=(x^2-2^2)(x^2+2^2)$ and $(x^2+2^2)-(x^2-2^2)=8$

$$\dfrac{8^2}{(x^4-16)^2}=\dfrac{(x^2+4-(x^2-4))^2}{(x^2-4)^2(x^2+4)^2}=\dfrac1{(x^2-4)^2}+\dfrac1{(x^2+4)^2}-\dfrac2{(x^2-4)(x^2+4)}$$

For the first, write the numerator as $\dfrac{(x+2-(x-2))^2}{16}$  and expand

For the second either $x=2\tan t$

or integrate by parts $$\int\dfrac1x\cdot\dfrac x{(x^2+4)^2}\ dx$$

Again for the last, $\dfrac{(x^2+4)-(x^2-4)}{(x^2-4)(x^2+4)}$


问:
What is the difference between these two systems?
I have these two models:

Both show Temperature vs Time for 15 different input conditions (i.e. inlet fuel velocity).

My question is: what is the difference between these two systems? Is one of them chaotic/non-chaotic? It is evident that the system on the left is independent of initial conditions as all values converge toward the end of the simulation - is that not the definition of non-chaotic dynamics? If so, since the other system "does care" about every change in the initial conditions - is it more chaotic?

Just trying to correctly formulate the difference in the underlying system dynamics.

答:
I wouldn't describe either as chaotic. The second one does turn small differences into larger differences, but it does so in a very clear and predictable way.

For example, $a_0 \times 1.01^n$ also results in larger changes for small differences in the value of $a_0$, but in a nice and predictable way.

On the other hand, $x_{n+1} = kx_n(1-x_n)$ is very different, a small difference in the value of $k$ can result in wildly different behavior in the sequence of $x_n$.


问:
Conditional Entropy - How to deal with zero-valued probabilities?
I would like to calculate $H(Y|X)$, however, for some values of $X$ and $Y$, I have probabilities which are zero. I understand that for calculating entropy such as $H(X) = \sum p(x)log(p(x))$, if $p(x) = 0$ for some term, that term can then be assumed to be $0$. However, I am unsure how to deal with this in the conditional entropy case. For example, let us say I have a term from calculating $H(Y|X)$:

$$p(x_i,y_i)log(\frac{p(x_i,y_i)}{p(x_i)})$$

Firstly: What if $p(x_i,y_i) = 0$?

Secondly: What if $p(x_i) = 0$?

Thirdly: What if both are $0$?

I've attempted to add some sort of smoothing (such at +1 on denominator), but I don't know of any good justification for doing so. Is there a standard way to deal with this? Thank you.

答: The standard way is to set the corresponding entropy term to $0$ if $p(x_i,y_i) = 0$. The justification for this is that $\lim_{x\to 0} x\log x = 0$. This applies to all the three cases that you mention.


问:
Homotopy (co)limits and model category structure on functor category
Let $C$ be a model category, $I$ a small category and $C^{I}$ the functor category. I was reading about homotopy (co)limits, and they define them the following way. First give a model category structure to $C^{I}$ such that
$$ \text{colim}: C^{I} \to C $$ is a left Quillen functor, and then we can construct its left derived Quillen functor, which gives a functor $$\text{hocolim}: C^{I} \to C$$ which is "well defined up to homotopy".

What is the desired model category structure on $C^{I}$? (which apparently is not unique). A natural definition is that $\alpha: F \Rightarrow G$ is a weak equivalence iff for all $x \in I$ $$\alpha_x : F(x) \to G(x)$$ is a weak equivalence. What about for (co)fibrations?

答:
As you say, you have choices.  Normally for homotopy colimits you want the projective model structure (if that is available).  Sometimes the Reedy model structure works too.  There is also the injective model structure, which is used for homotopy limits.

To give more details, if $\mathsf{C}$ is cofibrantly-generated, the projective model structure on $\mathsf{C}^\mathsf{I}$ has objectwise weak equivalences, objectwise fibrations, and cofibrations whatever they have to be.  Dually for the injective model structure.  The Reedy model structure takes a bit longer to describe.

You may also be interested in techniques to transfer model structures along adjunctions.

FYI, I like Dugger's (unfinished) notes on homotopy colimits as a reference.  See part 3 for model structures on diagram categories.


问:
Can expectation of a random variable be a random variable?
Suppose I have, $$ X = 1$$ with probability $p$ and $$X=0$$ otherwise.
Now, if $p$, in turn, is a random variable (for example, let's say it takes a value from 0 to 1 uniformly at random), what is $\Bbb E[X]$?
Is it just $p$ or $\Bbb E[p]$?

I took some examples (with a dice) and that makes me think that it is $\Bbb E[p]$. Also, as the expectation is constant, I think it cannot be just $p$. But, I am not sure if my logic is correct. I tried looking into this, but the answers I see either involve a lot of measure theory (which I don't know) or are not exactly related to my question.

I apologize if the question is not clear, I can give any extra details that you consider necessary.

Edit: I am not sure if this is the right way to edit and continue a question with a follow-up, but I have an additional question now.

For the example mentioned here, can I instead write $$X=1$$ with probability $E[p]$ and $$X= 0$$ otherwise?

Thanks in advance!

答:
In this case we have $X\sim \text{Bernoulli}(p)$ where $p$ is a random variable. We have \begin{align*}
\mathbb E(X|p)&= p\\
\mathbb E(X) &= \mathbb E(\mathbb E(X|p)) = \mathbb E(p)
\end{align*} which is a constant, not a random variable.


问:
How to generalise $(\wedge^2 \chi)(g) = \frac{1}{2}(\chi(g)^2-\chi(g^2))$?
One can decompose $\bigotimes^2 V = \bigvee^2 V \oplus \bigwedge^2 V$, getting a corresponding decomposition for representations, say when $V$ is a module for some finite group $G$. One then has the relation between the characters $\chi$, $\vee^2 \chi$ and $\wedge^2 \chi$ afforded by the $G$-modules $V$, $\bigvee^2 V$ and $\bigwedge^2 V$, given by $(\wedge^2 \chi)(g) = \frac{1}{2} (\chi(g)^2-\chi(g^2))$ and $(\vee^2 \chi)(g) = \frac{1}{2} (\chi(g)^2 + \chi(g^2))$.

More generally, one can decompose $\bigotimes^r V$ by Schur-Weyl duality in terms of the irreducible representations of the symmetric group $S_r$. Can we use this to give similar formulas for the representations coming up in this decomposition?

答:
From the GAP manual:

The symmetrization $\chi^{[\lambda]}$ of the character $\chi$ with the character $\lambda$ of the symmetric group $S_n$ of degree $n$ is defined by
$$ \chi^{[\lambda]}(g) = \frac{1}{n!}\left( \sum_{{\rho \in S_n}} \lambda(\rho) \prod_{{k=1}}^n \chi(g^k)^{{a_k(\rho)}} \right)$$

where $a_k(\rho)$ is the number of cycles of length $k$ in $\rho$.

You might also be interested in Murnaghan's refinement of these ideas which often can give smaller constituents.  All of these ideas are important as they only rely on the power map of the character table, and so allow one to pretty quickly find a lot of nearly irreducible characters from very little information (which is then followed by LLL to magically make them irreducible).


问:
Rotation of a point in 3d space
I'm trying to rotate a point around a single axis of a 3D system.

Given $P=\begin{pmatrix}
101 \\
102 \\
103
\end{pmatrix}
$,

And the rotation matrix formula for rotation around the X axis only, I get:

$Rx(\psi=90^\circ)=
\begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & -1 \\
0 & 1 & 0
\end{pmatrix}$

The rotation yields
$Rx*P =\begin{pmatrix}101 \\ -103 \\ 102\end{pmatrix}$

...but I expected a 90 degree rotation around $x$ would mirror the $y$ coordinate, yielding $\begin{pmatrix}101 \\ -102 \\ 103\end{pmatrix}$. By now I'm utterly confused by the various rotation conventions, and I'd be grateful for any help in clearing up where I went wrong with this simple operation.

Thanks!

答:
The word "mirror" should be a hint: the transformation
$$\begin{pmatrix}
x\\ y\\ z\end{pmatrix}\mapsto \begin{pmatrix}
x\\ -y\\ z\end{pmatrix}$$is  a reflection, not a rotation.

The result you're getting is correct. To get an intuition for it, try considering a simpler example: rotating the plane $90^\circ$ counterclockwise around the origin turns $(1,0)$ into $(0,1)$, not $(-1,0)$.

Title: Rotation of a point in 3d space


问:
Evaluate $\int_{2}^{7} \frac{x}{1-\sqrt{2+x}} d x$
We have the following integral:

$$
\int_{2}^{7} \frac{x}{1-\sqrt{2+x}}\, dx
$$

And this is my solution, which seems to be wrong, and I am failing to see where exactly I failed at:

We have $u=1-\sqrt{2+x}, x=u^2-2u-1, dx=-2\sqrt{2+x}\, du$, and we know that $x\geq -2$ and thus $u\leq 1$:

\begin{align}
\int_{2}^{7} \frac{x}{1-\sqrt{2+x}}\, dx
&=-2\int_{-1}^{-2} \frac{(u^2+2u-1)(u-1)}{u}\, du\\
&= -2 \left( \int_{-1}^{-2} u^2 d u + \int_{-1}^{-2} u\, du +\int_{-1}^{-2} -3\, du + \int_{-1}^{-2} \frac{1}{u}\, du \right) \\
&= -2\left[\frac{u^3}{3}+\frac{u^2}{2}-3u+\ln{|u|}\right]_{-1}^{-2}\approx -18
\end{align}

Can someone please help me pinpoint the issue?

Body:
I would have calculated it like this:

Let $u=1-\sqrt{2+x} \Leftrightarrow x=(1-u)^2-2$ where $x\ge-2$. We then have
$$ \mathrm dx=2(1-u)(-1)\,\mathrm du$$
so
\begin{align*}
\int_2^7\!\frac{x}{1-\sqrt{2+x}}\,\mathrm dx
&=\int_{-1}^{-2}\!\frac{(1-u)^2-2}{u}\cdot2(1-u)(-1)\,\mathrm du
\\&=2\int_{-2}^{-1}\!\frac{((1-u)^2-2)(1-u)}{u}\,\mathrm du
\\&=2\int_{-2}^{-1}\!\frac{(1-2u+u^2-2)(1-u)}{u}\,\mathrm du
\\&=2\int_{-2}^{-1}\!\frac{(u^2-2u-1)(1-u)}{u}\,\mathrm du
\\&=2\int_{-2}^{-1}\!\frac{-u^3+3 u^2-u-1}{u}\,\mathrm du
\\&=2\int_{-2}^{-1}\!\Bigl(-u^2+3u-1-\frac{1}{u}\Bigr)\,\mathrm du
\\&=2\Bigl[-\frac13u^3+\frac32u^2-u-\ln(|u|)\Bigr]_{-2}^{-1}
\\&=-\frac{47}{3}+2\ln(2).
\end{align*}


答:
The first thing I would like to point out is that since you want to do a substitution, it is really extra (unnecessary) work writing $dx$ in terms of $x$ (where the aim of substitution is to "get rid" of the initial variable and simplify the integral in the process).

With that out of the way, let $u = 1 - \sqrt {2 + x}$, then $x = u^2 - 2u - 1$ and $\mathrm{d}x = 2u - 2$.

Now, observe that, $\forall\ n \in \mathbb {R}$, $\sqrt n \geq 0$, so we note that $u \leq 1$.

\begin{align}
\int_{2}^{7} \frac x {1 - \sqrt {2 + x}}\ \mathrm {d}x & =
2\int_{-1}^{-2} \frac {(u^2 - 2u - 1)(u - 1)} u\ \mathrm {d}u
\\[5 mm] & =
2\int_{-1}^{-2} \frac {u^3 - 3u^2 + u + 1} u\ \mathrm {d}u
\\[5 mm] & =
2\left[\frac {u^3} 3 - \frac {3u^2} 2 + u + \ln|u|\right]^{-2}_{-1}
\\[5 mm] & =
2\ln 2 -\frac {47} 3
\end{align}

Title: Evaluate $\int_{2}^{7} \frac{x}{1-\sqrt{2+x}} d x$

Body:
We have the following integral:

$$
\int_{2}^{7} \frac{x}{1-\sqrt{2+x}}\, dx
$$

And this is my solution, which seems to be wrong, and I am failing to see where exactly I failed at:

We have $u=1-\sqrt{2+x}, x=u^2-2u-1, dx=-2\sqrt{2+x}\, du$, and we know that $x\geq -2$ and thus $u\leq 1$:

\begin{align}
\int_{2}^{7} \frac{x}{1-\sqrt{2+x}}\, dx
&=-2\int_{-1}^{-2} \frac{(u^2+2u-1)(u-1)}{u}\, du\\
&= -2 \left( \int_{-1}^{-2} u^2 d u + \int_{-1}^{-2} u\, du +\int_{-1}^{-2} -3\, du + \int_{-1}^{-2} \frac{1}{u}\, du \right) \\
&= -2\left[\frac{u^3}{3}+\frac{u^2}{2}-3u+\ln{|u|}\right]_{-1}^{-2}\approx -18
\end{align}

Can someone please help me pinpoint the issue?


问:
How to use generating functions to prove that $n^n=\sum\limits^{n-1}_{k=0}\binom{n}{k}k^k(n-k)^{n-k-1}$
Can anyone help? How can we use generating functions to prove the following identity:

$$n^n=\sum^{n-1}_{k=0}\binom{n}{k}k^k(n-k)^{n-k-1}$$

答:
Take $\sum_{n=1}^{\infty}\frac{n^nx^n}{n!}$ as the exponential generating function of the left hand side.

$$\sum_{n=1}^{\infty}\sum_{k=0}^{n-1} \frac{{n \choose k}k^k(n-k)^{n-k-1}x^n}{n!}=\sum_{k=0}^{\infty} \frac{k^k}{k!}\left(\sum_{n=k+1}^{\infty}\frac{(n-k)^{n-k-1}x^n}{(n-k)!}\right)$$

$$\sum_{n=k+1}^{\infty}\frac{(n-k)^{n-k-1}x^n}{(n-k)!}=\sum_{n=1}^{\infty}\frac{n^{n-1}x^{n+k}}{n!}=-x^kW(-x)$$ where $W$ is the Lambert function, defined by $z=W(z)e^{W(z)}$ with the principal branch having the series expansion $W(x)=\sum_{n=1}^{\infty}\frac{(-n)^{n-1}x^n}{n!}$.

$$\sum_{n=0}^{\infty}\sum_{k=0}^{n-1} \frac{{n \choose k}k^k(n-k)^{n-k-1}x^n}{n!}=\sum_{k=0}^{\infty}\frac{k^k(-x^kW(-x))}{k!}=\left(\sum_{k=0}^{\infty}\frac{k^kx^k}{k!}\right)-1=\sum_{k=1}^{\infty}\frac{k^kx^k}{k!}$$


问:
The orbit space $\dfrac{\mathbb{R}^n}{\mathbb{R}^+}$ has an open subset homeomorphic to $S^{n-1}$
Let $X$ be the orbit space $\dfrac{\mathbb{R}^n}{\mathbb{R}^+}$, where the action of $\mathbb{R}^+$ is given by the following lemma. I want to show that $X$ has an open subset homeomorphic to $S^{n-1}$, and a point that belongs to every nonempty closed subset. Could anyone help me show this?
It's problem $2$ of the chapter $21$ of Introduction of smooth manifolds john lee.

here is the lemma :
For any continuous action of a topological group $G$ on a topological
space $M$; the quotient map $\pi : M \to \dfrac{M}{G}$ is an open map.

Recall: Suppose we are given an action of a group $G$ on a topological space $M$; which we
write either as $\theta: G \times G \to M$ or as $(g,p) \to g.p $. (For definiteness, let us assume
that $G$ acts on the left; similar considerations apply to right actions.) Recall that the
orbit of a point $p \in M$ is the set of images of $p$ under all elements of the group:
\begin{align}
G.p=\{g.p : g \in G\}
\end{align}
Define a relation on$M$ by setting $p \sim q$ if there exists $g \in G$ such that $g.p=q$.
This is an equivalence relation, whose equivalence classes are exactly the orbits of
$G$ in $M$. The set of orbits is denoted by $\dfrac{M}{G}$; with the quotient topology it is called
the orbit space of the action

答: Take the unit sphere $S^{(n-1)}$ in $\mathbb{R}^{(n)}$; the quotient map $\pi$ restricted to the unit sphere is a topological embedding since it is injective and continuous. Also, we have $\pi(S^{n-1})=\pi(\mathbb{R}^n\setminus\{0\})$ so $\pi(S^{n-1})$ is open. For the second claim, consider $\pi(0)$. If $V$ is a neighborhood of this point in the quotient space, then $\pi^{-1}(V)$ is a neighborhood of the origin in $\mathbb{R}^n$. Take an open ball $B$ around the origin in this neighborhood. You can see that $\pi(B)=\pi(\mathbb{R}^n)$ because you can make every non-zero vector small enough by multiplying a small positive factor. Hence, the only open set containing $\pi(0)$ is the quotient space itself and every closed non-empty subset must contain this point.


问:
Metalogical motivations for logical inference rules?
For example, does every (introduction/elimination) of natural deduction encode some kind of desideratum about the proof system of natural deduction? This was suggested in this question, asking for motivation for a specific elimination rule.

In the comments of that post, it is suggested that there is a metalogical motivation for defining the inference rules of  natural deduction. "Every (introduction/elimination) encodes some kind of desideratum about the proof system. E.g. ∧ encodes the desideratum that every normal proof of ∧ should consist of two proofs, one for  and one for . We have a ("derived") theorem, the normalization theorem, which ensures that we can normalize every proof, and hence that our system satisfies all the desiderata encoded in the rules." In my understanding this is saying that each rule is accompanied by a derived justification, in the form of a (meta-logical) theorem about the consistency or normalization of the system.

What are the metalogical desiderata for each rule of the natural deduction, and what metalogical proofs establish that each of these desires are indeed satisfied by the  natural deduction.

答:
Gentzen [1] kick-started the field of structural proof theory: the 1934 paper introduces natural deduction. In the paper he already noted that introduction rules essentially represent definitions of the logical symbols. Later on, Gentzen took this perspective much further in his work on the sequent calculus, where he associates to each proof of a given sentence a corresponding canonical (cut-free) proof whose last rule has predictable form, depending only on the principal connective or quantifier of the formula.

Cut-elimination allows us to prove that intuitionistic logic satisfies structural properties (what you'd call metatheoretic properties, many of them tellingly named after the connectives) such as the disjunction property (if there is a proof of $A \vee B$, there ought to be a proof of $A$ or a proof of $B$), the conjunction property (if there is a proof of $A \wedge B$, there ought to be a proof of $A$ and a proof of $B$) and  consistency (there ought to be no proof of $\bot$), and corresponding to the BHK interpretation of the connectives. In Gentzen's sequent calculus, we can prove all of them the same way: by considering the last rule of a canonical proof, which has to be a right rule for the connective. E.g. to prove the conjunction property, we can consider a proof of $\vdash A \wedge B$: by cut-elimination, we can turn this proof into a canonical proof, which must then have the last rule

$$\frac{\vdash A\ \ \ \ \vdash B}{\vdash A \wedge B} \wedge\!R$$

so we indeed have proofs of $\vdash A$ and $\vdash B$ as desired. Similarly, we have consistency: if $\vdash \bot$ had a proof, it would have a cut-free proof, but it obviously has no cut-free proof (what would be its last rule?!). The rules enunciate the BHK-style desiderata: cut-elimination ensures that we indeed get the desiderata. One can play a very similar game in natural deduction, using Prawitz's [2] proof normalization technique (indeed the right rules of the former correspond to introduction rules of the latter, and left rules similarly correspond to elimination rules).

This should give you some idea about the desiderata corresponding to the rules of natural deduction, and the proofs that establish that each of these are indeed met. For a more thorough appraisal and philosophical discussion, check out Francez's book on Proof-theoretic Semantics [3], especially his discussions of inferentialism, and of Prior's tonk connective. If you're more interested in the technical details of normalization, Parwitz [2] or Chapter 4 of Dummett [4] are good starting points as well.

[1] Gerhard Gentzen, "Untersuchungen über das logische Schließen. I". Mathematische Zeitschrift 39 (2), 1934.

[2] Dag Prawitz, "Natural Deduction: A Proof-Theoretical Study", Dover Publications 1965.

[3] Nissim Francez, "Proof-theoretic Semantics", Studies in Logic 57, College Publications UK, 2015.

[4] Michael Dummett, "Elements of intuitionism", Oxford Logic Guides 39, Oxford University Press, 1977.


问:
Finding Tensor Product
Let $\Pi_{n\in \mathbb{N}}\mathbb{Z}:= M$

Is $ M \otimes_{\mathbb{Z}} \mathbb{Q} \cong \Pi_{n\in \mathbb{N}}\mathbb{Q}$ ? I believe this is true but I don't know how to prove this.

Kindly help me with an idea/ hint.

Thanks in advance.

答:
It is false. There's a natural map

$$\left( \prod_{\mathbb{N}} \mathbb{Z} \right) \otimes \mathbb{Q} \to \prod_{\mathbb{N}} \mathbb{Q}$$

which is injective but not surjective. Its image consists of the subspace of $\prod_{\mathbb{N}} \mathbb{Q}$ consisting of sequences whose denominators are bounded, or equivalently which can be put under a common denominator (basically because tensoring by $\mathbb{Q}$ only allows you to divide an entire integer sequence by some common denominator) and so does not contain, for example, the sequence $n \mapsto \frac{1}{n}$.

(On the other hand these groups are abstractly isomorphic because they're both vector spaces over $\mathbb{Q}$ of continuum dimension. See this math.SE answer which says basically the same thing.)

In general, tensor product is only guaranteed to preserve finite products. You can show that tensoring with a module preserves infinite products iff it's finitely presented (which $\mathbb{Q}$ is not); see this math.SE answer.

Title: Finding Tensor Product


问:
Hatcher definition algebraic topology elaboration
In page 108, hatcher says the boundary map $\partial:C_n(X)\rightarrow C_{n-1}(X)$ is defined by

$\partial_n{\sigma}=\sum_i(-1)^i\sigma|_{[v_0,...,\hat{v_i}..,v_n]}$. He then immediately states

"Implicit in this formula is the canonical identification of $[v_0,....\hat{v_i},...,v_n]$ with $\Delta^{n-1}$, preserving ordering of vertices.."

Can someone elaborate on the quoted text, please?

答:
The singular $n$-chain $\sigma \in C_n(X)$ is a formal $\Bbb Z$-linear combination of maps $\Delta^n \to X$, so the boundary map suffices to be defined on generators (i.e., on a single map $\Delta^n \to X$). Thus, let $\sigma: \Delta^n \to X$ be a singular $n$-simplex in $X$.

$\Delta^n$ can be written as an ordered list of vertices $[v_0, ..., v_n]$ (if you specify $n+1$ vertices, you've specified an $n$-simplex, and the converse works too; you can see pictures of this idea on page 103).

$\partial_n (\sigma)$ needs to be a singular $(n-1)$-chain, so it needs to be a formal $\Bbb Z$-linear combination of singular $(n-1)$-simplices. For each $i$ you want to delete, $[v_0, ... \hat{v_i}, ...,v_n]$ is an ordered list of vertices with $n$ entries, so it is an $(n-1)$-simplex, and since it's a list containing (all but one of) the vertices of $\Delta^n$, it is an $(n-1)$-simplex making up one of the faces of $\Delta^n$ . You can see pictures of this idea on page 105.

Thus it makes sense to talk about the restriction of $\sigma$ to this simplex, so $\sigma|_{[v_0,...,\hat{v_i},...,v_n]}$ is a map $\Delta^{n-1} \to X$. We can add these, so the alternating sum of these as $i$ varies is an element of $C_{n-1}(X)$. The note about preserving the ordering of vertices just ensures that when you delete a vertex from your list and look at the remaining list, you do indeed get the exact face of the original simplex that contains all the vertices but the one you deleted.


问:
Prove that $\min_{X \subseteq U} f(x) = \min_{X \subseteq U} g(x)$
Let $U$ be a set. Consider funcions $f$ and $g$ that return positives values and nulls values (equal at zero). If $f(Z) \le g(Z)$ for all $Z \subseteq U$. Moreover, we know that exists $X' \subseteq U$ such that $f(X') = g(X')$. Show that $\min_{X \subseteq U} f(X) = \min_{X \subseteq U} g(X)$.

Proof. Since $f(Z) \le g(Z)$ for each $Z \subseteq U$, then
$$\min_{X \subseteq U} f(X) \le \min_{X \subseteq U} g(X)$$

How to show that $\min_{X \subseteq U} f(X) \ge \min_{X \subseteq U} g(X)$?

答:
Let $U$ be a set. Consider funcions $f$ and $g$ that return positives
values and nulls values (equal at zero). If $f(Z) \le g(Z)$ for all $Z
> \subseteq U$. Moreover, we know that exists $X' \subseteq U$ such that
$f(X') = g(X')$. Show that $\min_{X \subseteq U} f(X) = \min_{X
> \subseteq U} g(X)$.

Not true. Counter-example below.

Choose $U = \{1, 2\}$ and

$f(Z) = 1$ if $Z = \{1\}$ and $f(Z) = 2$ otherwise.

$g(Z) = 2$ for any $Z\subseteq U$.


答:
exactly, when you have $u=1-\sqrt{2+x}\ => x=u^2-2u-1$

Then $du=2(u-1)dx$

Plugging it into your formula we get

$=2\int\ \frac{(u^2-2u-1)(u-1)}{u}$


问:
What is a finitely generated G-operator group?
[I'm self-studying group theory after many, many years away, using Derek Robinson's book.]

Robinson in Ex 2.2.8 says:

Let G be a finitely presented group and let N be a normal subgroup which is finitely generated as a G-operator group.  Prove that G/N is finitely presented.

I think I understand all the words like "G-operator" and "finitely generated," but I don't know what they mean combined (as emphasised in this sentence.)

[Note: I'm not asking for a solution to the problem (yet!) but just to know what it means.]

答:
I don't think Dietrich's guess in the comments is correct (the word "as" is relevant). My guess is that "finitely generated as a $G$-operator group" means that there exists a finite subset $S$ of $N$ such that every element of $N$ can be obtained from this subset by repeated multiplication and the action of $G$ (by conjugation). Equivalently, $N$ is generated (as a group) by $\cup_{g \in G} gSg^{-1}$.

Note that the exercise is much easier if you just assume that $N$ is finitely generated but then there's no need to mention the concept of a $G$-operator group at all.


问:
Probability message is sent correctly

A message of $10^k$ binary digits is sent along a fibre optic cable with high probabilities $p_0$ and $p_1$ that digits 0 and 1, respectively, are recieved correctly. If the probability of a digit in the original message being 1 is $a$, find the probability $Pr$ the entire message is received correctly.

I am stuck between two possibilities for this answer.

Approach 1: There are $a10^k$ 1's and $(1-a)10^k$ 0's. So
$$Pr=P(\text{All 1's send correctly})P(\text{All 0's send correctly})=p_1 ^{a 10^k} * p_0 ^{(1-a) 10^k}$$

Approach 2: For a particular bit
$P(correct) = P(\text{It is a 1})p_1 + P(\text{It is a 0})p_2=ap_1 + (1-a)p_2$
So, $$Pr = (ap_1 + (1-a)p_2)^{10^k}$$

I would be grateful for an explanation why one of these approaches is incorrect (or both, but I'm confident one of them is), as they both sound like they should work.

答:
To stress my earlier comment:  this is a problem of semantics, not math.

The problem, as stated, admits two interpretations.

Interpretation $I$:  The message contains exactly $a\times 10^k\,$  $1's$.
In that case, your first approach is correct.  Well, assuming that the noise hits each digit independently (but I think that's clearly the intent of the question).

Interpretation $II$:  Each digit independently has a probability $a$ of being a $1$.  In that case, the probability of getting a single digit right is $ap_1+(1-a)p_0$, just as you suggest in your method $2$.

I think either interpretation makes sense, so it's just a question of which one was intended. Your first method addresses the first interpretation, and the second method addresses the second.

Title: Probability message is sent correctly


问:
The ratio $a:b:c$ of the sides of a triangle with angles $\alpha=120^\circ$ and $\beta=30^\circ$
We have just studied the law of sines. I am trying to find the ratio $a:b:c$ of the sides of a triangle with angles $\alpha=120^\circ$ and $\beta=30^\circ.$

We can calculate the third angle of the triangle: $\gamma=180^\circ-\alpha-\beta=30^\circ.$ So the triangle is isosceles. The law of sines gives us $$a:b:c=\sin\alpha:\sin\beta:\sin\gamma=$$ $$=\sin120^\circ:\sin30^\circ:\sin30^\circ=\dfrac{\sqrt3}{2}:\dfrac12:\dfrac12=\left(\dfrac{\sqrt3}{2}\cdot2\right):\dfrac{1}{2}=\text{...}=2\sqrt3.$$ That can't be it! Where am I wrong?

答: You are correct; $a:b:c=\sqrt3:1:1$.

Body: You are correct; $a:b:c=\sqrt3:1:1$.


问:
Find the numbers $a,b,c,d$ in a geometric sequence, knowing that $a+1$, $b+6$, $c+6$, $d-4$ are in an arithmetic sequence
The exercise reads as follows:

Find the numbers $a,b,c,d$ in a geometric sequence, knowing that $a+1$, $b+6$, $c+6$, $d-4$ are in an arithmetic sequence.

I am interested in finding out the steps I should use to get to a solution. Or just a starting point, I've been thinking about this for some time and I wouldn't say I am getting close to the result soon.

I was thinking about:

$a+1 = b+6-r \implies a=b+5-r$

$c+6 = b+6+r \implies c=b+r$

And use $b^2=a*c$ from the geometric sequence.

The topic can be closed. Massive thanks to Rafaelle for the solution and also to Oscar Lanzi for explaining the process!

答:
"Then a miracle occurs..."

Let's look inside Raffaele's solution process.

To implement the geometric sequence, render $b=ar,c=ar^2,d=ar^3$.  Then use the fact that the second term in the arithmetic sequence must be the mean of the first and third terms to form tte equation

$2(ar+6)=(a+1)+(ar^2+6)$

which rearranges to

$a(r^2-2r+1)=a(r-1)^2=5$  Eq. 1

Similarly, the third term in the arithmetic sequence is the mean of the second and fourth ones giving

$2(ar^2+6)=(ar+6)+(ar^3-4)$

$a(r^3-2r^2+r)=ar(r-1)^2=10$  Eq. 2

Equations 1 and 2 differ only by a factor of $r$ on the left side, so dividing the latter by the former isolates $r=2$.  Then $a=5$ is obtained by substitution into either equation leading to the geometric progression $(a,b,c,d)=(5,10,20,40)$ and the arithmetic progression $(6,16,26,36)$.


答:
The matrix multiplication you performed is correct... the expectation sentence is wrong.

Rotations and reflections are different, in general. Rotations are generally taken to be orientation preserving rigid motions, and it turns out that any matrix for such a rotation has determinant 1. Reflections, on the other hand, are orientation reversing, and they have to have determinant -1.

If it helps, we can think about plane geometry for a second. If you have a triangle drawn on a sheet of paper and a point marked as the origin, you can rotate this paper in place around the point on the paper. To perform a reflection you have to flip the paper over! This is the difference between a rotation and reflection in the 2-d plane.

Exercises to convince yourself the computation you did is correct:

1) You can confirm that the reflection you were performing was $\begin{bmatrix}1&0&0\\0&-1&0\\0&0&1\end{bmatrix}$, and that the determinants of this matrix and your original matrix are -1 and 1 respectively. This shows the two operations are definitely of different characters.

2) Look at the "shadow" of the point in the $y-z$ plane as the sun shines down the $x$ axis. (I mean $(102,103)$). If you rotate that 90 degrees around the $x$ axis, you can see that it lands in the second $y-z$ quadrant. Of course, this point is the shadow of the original point after rotation. Draw a triangle between the old shadow, the new shadow and the origin, and verify that it's a right triangle.

3) It would also be a good exercise to try a 45 degree rotation instead. Do a 45 degree rotation in the $y-z$ plane, and check to see where the point $(0,100,100)$ goes. It will certainly not be $(0,-100,100)$ :)

Title: Rotation of a point in 3d space

Body:
I'm trying to rotate a point around a single axis of a 3D system.

Given $P=\begin{pmatrix}
101 \\
102 \\
103
\end{pmatrix}
$,

And the rotation matrix formula for rotation around the X axis only, I get:

$Rx(\psi=90^\circ)=
\begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & -1 \\
0 & 1 & 0
\end{pmatrix}$

The rotation yields
$Rx*P =\begin{pmatrix}101 \\ -103 \\ 102\end{pmatrix}$

...but I expected a 90 degree rotation around $x$ would mirror the $y$ coordinate, yielding $\begin{pmatrix}101 \\ -102 \\ 103\end{pmatrix}$. By now I'm utterly confused by the various rotation conventions, and I'd be grateful for any help in clearing up where I went wrong with this simple operation.

Thanks!


问:
Triangle lower bound of a convex function
Suppose the function $f:[0,\infty)\rightarrow [0,\infty)$ is convex on $[T,\infty)$.

Let $\delta=f(t)/|f'(t)|$ then the triangle $T$ determined by the points $(t,f(t)), (t,0)$ and $(t,t+\delta)$ lies below the graph of $f$ for all $t\geq T$.

I cannot confirm that the point $(t,t+\delta)$ does lie below the graph of $f$. I tried to play around the tangent definition of convex function:
$$
f(x)\geq f(y)+f'(y)(x-y)
$$
but unable to get anywhere.

(Edit: I have attached a picture of the source material 06-01-2021)

答: In case $f'(t)=0$, one can check either the integral is infinity, or the integral is $0$, meaning $f=0$ on $[t, \infty)$ and $f(t)=0$, you can interpret $f(t)^2/|f'(t)|=0$.