问:
complex norm inequality
For $z,w \in \mathbb{C}$ How to show the identity: $$2(|z|^n+|w|^n) \leq (|z+w|^n + |z-w|^n )? $$ for $n \geq 2$.
I tried induction, but can't I finish.

Title: complex norm inequality

Body:
It is similar to parallelogram identity.

\begin{equation}
\begin{aligned}
|z|^n + |w|^n &= <z,z>^{n/2} + <w,w>^{n/2}\\ &\leq (<z,z>+<w,w>)^{n/2}
\\&\leq \frac{1}{2^{n/2}}(<z+w,z+w>+<z-w,z-w>)^{n/2}\\&\leq
\frac{2^{n/2-1}}{2^{n/2}}(<z+w,z+w>^{n/2}+<z-w,z-w>^{n/2}) = \frac{1}{2}|z+w| +\frac{1}{2} |z-w|
\end{aligned}
\end{equation}


问:
Why do the triangular numbers initially form long cycles mod $2^k$?
As discussed at Triangular numbers ($\text{mod } 2^n$) as a permutation of $\{0,1,2,\dots,2^n-1\}$ and What is the set of triangular numbers mod $n$?, mapping the integer $n$  for $0\le n\lt2^k$ to the residue of the corresponding triangular number $\frac12n(n+1)$ modulo $2^k$ yields a permutation. For example, for $k=3$:

$$
01234567\\
01362754
$$

I noticed that up to $k=5$, all elements except for $0$ and $1$ (which are always mapped to themselves) form a single cycle of length $2^k-2$. The probability for a uniformly random permutation of length $n$ to consist of a single cycle is $\frac1n$, so if these permutations (excluding $0$ and $1$) could be considered uniformly random, the probability for this to happen would be only $\frac12\cdot\frac16\cdot\frac1{14}\cdot\frac1{30}=\frac1{5040}$. That was reason enough to check whether the pattern continues for greater $k$.

It turns out that it doesn't, as for $k=6$ there is a $3$-cycle: $(4,10,55)$. Nevertheless, at first unusually large cycle lengths persist: For all $k$ from $2$ to $12$, except for $k=7$, the largest cycle contains more than half the elements, whereas the probability for this to happen in a random permutation is roughly $\ln 2$. In fact, in $9$ of these $11$ cases (all except $k=6$ and $k=7$), the largest cycle contains more than $\frac45$ of the elements; the probability for that is roughly $\ln\frac54\approx0.223$ per case, so the probability for it to happen at least $9$ times out of $11$ is only $\sum_{k=9}^{11}\binom{11}k\left(\ln\frac54\right)^k\left(1-\ln\frac54\right)^{11-k}\approx5\cdot10^{-5}$.

However, this pattern, too, doesn't continue: For $k$ from $2$ to $30$, there are $21$ cases with cycles of more than half the elements, which is about the expected number $29\ln2\approx20.1$; and for $k$ from $13$ to $30$ there are only $4$ cases with cycles of more than $\frac45$ of the elements, which is almost exactly the expected number $18\ln\frac54\approx4.0$.

My question is: Is there an explanation for this initial tendency to form long cycles? Or should we put it down to coincidence?

For your convenience, here's the code I used to find the cycle lengths, and here are the results up to $k=30$:

```<code>4 : 2
8 : 6
16 : 14
32 : 30
64 : 40, 19, 3
128 : 55, 48, 14, 6, 3
256 : 247, 4, 3
512 : 488, 7, 6, 6, 3
1024 : 818, 157, 47
2048 : 1652, 371, 23
4096 : 4060, 25, 9
8192 : 3754, 3609, 412, 321, 79, 12, 3
16384 : 15748, 292, 190, 71, 24, 22, 13, 13, 9
32768 : 20161, 11349, 333, 305, 281, 218, 72, 44, 3
65536 : 20128, 17231, 16759, 8072, 2377, 579, 295, 60, 33
131072 : 85861, 26603, 9389, 3887, 3365, 682, 594, 488, 118, 49, 23, 6, 5
262144 : 159827, 89991, 5749, 5465, 592, 231, 118, 100, 42, 24, 3
524288 : 211265, 176243, 59029, 35639, 28496, 6122, 4245, 1239, 713, 632, 244, 146, 133, 59, 39, 36, 6
1048576 : 620076, 216520, 131454, 68118, 7535, 2111, 1235, 1028, 225, 213, 36, 20, 3
2097152 : 993084, 583840, 394263, 87941, 31835, 3389, 1648, 459, 306, 273, 45, 35, 14, 10, 8
4194304 : 1487646, 1119526, 942359, 429054, 118037, 64446, 28806, 3238, 323, 291, 186, 126, 118, 102, 12, 11, 10, 7, 4
8388608 : 2542051, 2462220, 2040680, 1138236, 93072, 45880, 19664, 16473, 14243, 6319, 2917, 2598, 2160, 1414, 514, 118, 23, 19, 5
16777216 : 12137774, 4004239, 271250, 253890, 43860, 33597, 25495, 4132, 2575, 157, 116, 67, 35, 9, 8, 6, 4
33554432 : 28169497, 2552414, 1401622, 1019221, 356682, 21006, 14735, 10242, 8223, 566, 135, 45, 21, 15, 6
67108864 : 32223531, 29360424, 3530597, 932310, 809707, 99109, 83093, 67418, 1612, 364, 248, 248, 166, 21, 14
134217728 : 87591110, 34361487, 3360928, 3343185, 3291274, 1345478, 353498, 323522, 158252, 47767, 17776, 11159, 5927, 2681, 2343, 530, 235, 208, 162, 84, 59, 31, 30
268435456 : 232647749, 24918738, 5559122, 3742461, 525140, 384941, 278834, 197080, 62977, 48736, 21684, 16632, 13525, 8993, 3073, 2721, 1625, 1262, 153, 5, 3
536870912 : 379598603, 129063661, 26279056, 665648, 483286, 222289, 137686, 106713, 94323, 80276, 59199, 41767, 15498, 10615, 5066, 2816, 2699, 1579, 113, 10, 7
1073741824 : 877039442, 181409872, 7571387, 6549459, 921247, 240525, 3924, 3416, 1602, 894, 54
</code>```

答:
This is a nice question, thank you for anyone who reopened it.

If the calculation of Mr Joriki  is correct, there is a case (say $k=19$ ) where the length of the longest cycle does not exist $\dfrac{2^k}{2}$. So I guess it is not a good lower bound  for all $k$, I cannot say much about the situations in which $k$ is sufficiently large).

Here, by this post, I'll give an elementary explanation for :

Why the length of the longest cycle goes to infinity when $k$ get larges? and in fact, I'll give a lower bound of order $O(k) $

Explosion of the length of the longest cycle

For $k\ge 2$

Let :

$T(n)$ is the respective $n-th$ triangular numbers, that is $T: n \longmapsto \dfrac{n(n+1)}{2}$

$ord(x)$ denote the length of the orbit of $T$ by the mapping $T$, that is: $ord(x)$ is the smallest number $m \ge 1$ such that :$T^m(x)=x \mod 2^k$

$n,m$ be two postive integer such that $k>n$ and $2(n-m+1) \ge k+1$ (1) and $2^{k-n} > m$ (2)

Then, for any integers $x, s $ , we have:
$$\begin{equation} T(x+s2^n)=T(x)+\underbrace{(2x+1)}_{A_1} s2^{n-1}  \mod 2^k \\ T^2(x+s2^n)= T(x)+\underbrace{(2x+1)(2T(x)+1)}_{A_2}s2^{n-2}  \mod 2^k \\ ... \\T^m(x+s2^n)=T(x)+A_ms2^{n-m} \mod 2^k \end{equation} $$
for $A_m= (2x+1)(2T(x)+1)...\left(2T^{m-1}(x)+1\right)$

Remark: The inequality (1) is just here to make sure all the equations above hold. We will not revisit them until the last step.

From the above identities, we see the following lemma which is also the centre of my demonstration.

Lemma

If $s$ is an integer in $[0,2^{k-n})$, one of the following assertions is wrong:

$ord(x)$ and $ ord(x+s2^{n})$  are not bigger than $m$

$ord(x)=ord(x+s2^n)=u$

Proof

If both are true, we can imply that: $$x+s2^{n}= T^u(x+s^{n})=T^u(x)+A_us.2^{n-u}=x+A_us2^{n-u} \mod 2^k$$
$$\longleftrightarrow s2^n= A_us2^{n-u} \mod 2^k$$
which is wrong because $A_u$ is an odd number and $s$ is a nonnegative integer not exceeding $2^{k-n}$.

Now back to our quest of finding the lower bound.

Assume that for all integer $y \in \{0,1,2,...,2^k-1\}=: B$ , $$ord(y) \le m$$
For any nonnegative integer $x$ such that $0 \le x < 2^n$, let us consider the following set:
$$C:=\{ x+s2^n | 0 \le s < 2^{k-n} \}$$
Clearly,

$C \subset B$

$ \#C = 2^{k-n}$

$1 \le ord(y) \le m $ for all $y \in C$

Because $2^{k-n}>m$ (condition (2)), then by Directlet's principle, there are two elements $y_1,y_2 \in C$ such that $ord(y_1)=ord(y_2)\le m$.

Which is wrong thanks to our above lemma

So for all $n,m$ which sastify our condition (1) and (2), there must be an integer $y \in [0,2^{k-1})$ such that:
$ord(y) \ge m+1$

So our longest cycle must have the length of at least $m+1$

Besides, we see that for $k$ big enough, $n=\dfrac{3k}{5}$ and $m=k/10$ sasitify our conditions (1) and (2). So:

Conclusion

For $k$ big enough (say, from $k \ge 10$ on), the length of our longest cycle has a $k/10$ as lower bound.

Discussion

In fact, there are some freedoms in our solution that may promise a better bound.

$T$ is a very interesting function as one may easily think that $T(x+2^k)=T(x) \mod 2^k$ though, in fact, it is wrong.

The same procedure can be applied to other polynomials $Q$ in $\mathbb{Q}[X]$ than $T$ and other numbers $a$ than $2$ to achieve the lower bound of order $O(k)$ for the longest cycle. (Just with some good relation between $a$ and $Q'$)

ContentLicense: CC BY-SA 4.0


问:
Axiom Q in Fischer's Intermediate Real Analysis
In Intermediate Real Analysis by Emanuel Fischer page 6, the author states an axiom that says

(Axiom Q) If $x$ and $y$ are real numbers, where $z+y\neq z$ holds for some real $z$, then there exists a real number $q$ such that $yq=x$.

Is there a name for this axiom? I believe "$z+y\neq z$" is a typo; shouldn't it be $z+y\neq x$? Does anyone know if there is a list of typo for this book?

答:
He's postulating the axiom that quotients exist for real numbers, with the necessary restriction that the dividend must be nonzero, i.e. it cannot be the addtive neutral element (usually denoted by $0)$.

Unlike the most common axiomatization of a field, the author does not include axioms for the neutral elements $0$ and $1$ for addition and multiplication. Rather, he defines the additive and multiplicative groups using axioms that differences and quotients exist, i.e. $\,a + x = b\,$ is solvable for all $\,a,b\in \Bbb R,\,$ and $\, a\cdot x = b\,$ is solvable for all $\,a,b\,$ when $\,a\,$ is not additively neutral (i.e. when $\, x + a = x\,$ fails to be true for all $\,x\in \Bbb R,\,$ i.e. when $\,r+a\neq r\,$ for some $\,r\in \Bbb R).$

Later he proves that there exist unique additive and multiplicative neutral elements, denoted by the customary symbols $0$ and $1$.

This axiomatization of groups using division (or subtraction) is less common than that using inverses and neutral elements, but it does occur from time to time (and if memory serves correct it has been discussed here in the past on multiple occasions, e.g. here). In fact there are many known axiomatizations of groups, rings, fields. Typically we choose one that proves convenient for the context at hand.


问:
Show that the function from standard metric to discrete metric is discontinuous.
Show that the function g:(R,d)->(R,d_0) where d_0 is the discrete metric, d is standard metric on R ie d(x,y)=|x-y| and g(x)=x^6 is discontinuous

So I think I'm meant to use epsilon-delta proof but I'm not really sure how to start it? Unless there is a better way to do this?

答: Suppose there exist $\delta >0$ such that $|x-0| <\delta$ implies $d_0(f(x),f(0))<1 $. Take $%x=\frac  1 n$ where $\frac  1 n <\delta$. Then we get $1<1$, a contradiction.


问:
Is every complex Lie algebra a complexification?
I'm wondering if every finite-dimensional complex Lie algebra can be written as a complexification of a real Lie algebra. At the vector space level, clearly every $\mathbb{C}^n$ is a complexification of $\mathbb{R}^n$, but at the level of bracket structure, it's not clear to me if we can consistently "decomplexify" the Lie algebra. Putting it another way, for any given $n$-dimensional complex Lie algebra, can we find a basis $\{e_1,\ldots,e_n\}$ such that the structure constants are all real?  </p>

答:
The answer is no.

A "minimal" example of a complex Lie algebra without a real form is given in example 1.36 of these lecture notes of Karl-Hermann Neeb's. To spell it out, it is the three-dimensional Lie algebra over $\mathbb C$ with basis $x,y,z$ and commutators

$$[x,y]=0, [z,x]=2x, [z,y] = i y.$$

It is minimal in the sense that every $0$- , $1$-, or $2$-dimensional (https://math.stackexchange.com/a/976271/96384, Classsifying 1- and 2- dimensional Algebras, up to Isomorphism) complex Lie algebra does have a real form.

Note that the above Lie algebra is solvable. On the other end of the spectrum, it is a well-known (although maybe not suffciently celebrated) result of the structure theory that all semisimple complex Lie algebras do have real forms -- actually, they can be defined over $\mathbb Q$ or even $\mathbb Z$, a result usually attributed to Chevalley (see "Chevalley basis").

Finally, note that the above example does have a form over the number field $\mathbb Q(i)$. The answers to Are there finite-dimensional Lie algebras which are not defined over the integers? (especially user YCor's comment to Qiaochu Yuan's answer) exhibit examples of complex Lie algebras which do not have forms over any number field, nor $\mathbb R$.

ContentLicense: CC BY-SA 3.0


问:
Can Kruskal's and Prim's algorithm give trees with different weight?
So, I have to find the minimal spanning tree in the graph in the picture. Below are my results. I feel like I shouldn't get 2 different weights, but I can't find a mistake.

答:
You didn’t carry out Prim’s algorithm correctly. I’m assuming that you started with $v_1$, added the edge to $v_2$, and then added the edge from $v_2$ to $v_3$. That much is fine, but then you added the edge from $v_3$ to $v_5$, when you should have added the edge from $v_2$ to $v_5$: of all of the edges between the partial tree that you’d constructed up to that point and the other vertices of the graph, the one between $v_2$ and $v_5$ has the lowest weight. Specifically, the edges available for adding at that point, with their weights, are as follows, with the edge of lowest weight shown in red:

$$\begin{array}{c|cc}
\text{Edge}&\text{Weight}\\\hline
v_1v_4&11\\
v_1v_5&9\\
v_2v_4&9\\
\color{red}{v_2v_5}&\color{red}8\\
v_3v_5&10
\end{array}$$

At each stage you should add the edge of lowest weight between any vertex of the partial tree that you’ve constructed up to that point and any vertex not in that partial tree.


问:
density function of a cumulative distribution function
Let $X$ have a standard normal distribution and $Y$ have an Exponential(1) distribution, with $X$ and $Y$
being independent random variables. Find the density function of Φ(X)+Y , where Φ denotes the standard
normal distribution function.

I am attempting to do this problem through convolution. However, I am not sure about the density of the Φ(X) in the first place, but I know that the density of $X$ is $\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}$, is there a way to use this fact to find density of Φ(X)? Thank you.

答:
The density of $Z=\Phi(X)$ is uniform in$(0;1)$ and it is easy to prove

Proof:

Let $Z=F_X(x)$ with F continuous.

$$F_Z(z)=P[Z \leq z]=P[F_X(x)\leq z]=P[X\leq F_X^{-1}(z)]=F_X[F_X^{-1}(z)]=z$$

Thus

$$f_Z(z)=\mathbb{1}_{(0;1)}(z)$$


问:
maximal tree by Zorn's lemma
In using the Zorn's lemma to show that every connected graph contains a spanning tree, we let $\{T_{\lambda}: \lambda \in \Lambda \}$ be a family of trees contained in $X$ which is totally ordered by inclusion. But how to show that $\bigcup\limits_{\lambda \in \Lambda} T_\lambda$ is a also a tree in $X$?</p>

答:
Actually, $\bigcup\limits_{\lambda \in \Lambda} T_{\lambda}$ may not be a tree.

You have to show that every chain in your family of trees has an upper bound. So, given a chain $\{T_{\alpha}$| $\alpha \in A$}, take the union $T=\bigcup\limits_{\alpha \in A} T_{\alpha}$. It is straightforward to show that this is tree: you just have to show that, given any two vertices $v_1,v_2 \in T$, there is exactly one path between them.

(proof by contradiction: assume two paths - both the paths will be contained in some $T_{\alpha_0}$, but $T_{\alpha_0}$ is a tree, so you get a contradiction )

Now, since you have a poset where every chain has an upper bound, Zorn's lemma can be applied.

Title: maximal tree by Zorn's lemma


问:
Counting Problem - discrete math
I need help with the following problem:

There are three computers A, B, and C. Computer A has 10 tasks, Computer B has 15 tasks, and Computer C has 20 tasks. Each computer must complete its own tasks in order. After, each computer sends its output to a shared fourth computer. How many different orders can the outputs arrive at the fourth computer.

My work so far:
This is a permutation problem since the order matters. 10! * 15! * 20! is what I believe the answer is but I am unsure.

答:
HINT: This is not a permutation problem, because the order of tasks for each of the three computers is fixed; the only thing that varies is how the tasks for the three computers are interleaved. Once we know which $10$ of the $10+15+20=45$ positions in the output are occupied by A’s tasks, we know which of A’s tasks is in each of those $10$ positions: they must have been done in order. Similarly, once we know which $15$ positions have the output of B’s tasks, we know which of B’s tasks is in each of those positions.

How many ways are there to choose the $10$ positions in the output for A’s tasks?

Once that’s been done, how many ways are there to choose $15$ of the remaining positions for B’s tasks?

At that point all $20$ of the positions that still remain must be filled with C’s tasks in their proper order, so there are no more choices to be made. Putting the pieces together, how many different orders are there in which the $45$ outputs can arrive at the fourth computer?

Title: Counting Problem - discrete math


问:
Probability of receiving a job offer on 3rd application
Suppose that when you submit a job application you have a probability of $0.1$ to receive an interview, and a job interview results in a job offer with probability $0.2$. Also assume you only submit one application at a time (i.e. you wait to know if you have been rejected from the job, either at the application stage or the interview stage before applying to another job).

What is the probability of getting your first job offer after submitting at most 3 job applications?

Attempt: Either you get a job offer after your first, second, or third application.

The probability of getting an offer after your 1st application is $(0.1)(0.2)=0.02$.

The probability of getting an offer after your 2nd application is $(1-0.02)(0.1)(0.2)=0.0196$

The probability of getting an offer after your 3rd application is $(1-0.02)(1-0.02)(0.1)(0.2)=0.0192$

Thus, $0.02+0.0196+0.0192=0.0588$

I don't think my approach is correct, it doesn't make sense to me that you have  a higher probability of getting an offer on your first application than you do on your 2nd or 3rd. I'm stumped as to what the mistake is that I am making.

答:
Let $a = 0.1$ the probability to get an interview and $b = 0.2 = 2a$ the probability to be hired after an interview.

The probability to be hired at a given submission is $ab$.

The probability you are looking for is:

$$p = \underbrace{ab}_{\text{1st sub. hired}} + \underbrace{(1-ab)}_{\text{1st sub. fail}}\cdot\left(\underbrace{ab}_{\text{2nd sub. hired}} + \underbrace{(1-ab)}_{\text{2nd sub. fail}}\cdot\underbrace{ab}_{\text{3rd sub. hired}}\right) =\\
= a^3b^3 - 3a^2b^2 + 3ab = \\
= a^3 (2a)^3 - 3a^2 (2a)^2 + 3a(2a) = \\
= 8 a^6 - 12 a^4 + 6 a^2 = \\
= 8 \cdot 10^{-6} - 12 \cdot 10^{-4} + 6 \cdot 10^{2}
= 0.058808.$$


问:
Matrices commuting with an irrep up to automorphism
Let $R$ be an irreducible representation of a finite group $G$.

Schur's lemma tells us that matrices $M$ that commute with $R$
$$MR(g)=R(g)M~, \forall g\in G$$
are proportional to the identity
$$M=\lambda I~.$$

What can be said about matrices $M$ that commute with $R$ up to an automorphism $\sigma$ of $G$?
$$MR(g)=R(\sigma(g))M~, \forall g\in G$$

答:
Following the comment, such a matrix will exists if and only if $R$ and $R\circ \sigma$ are isomorphic as representations of $G$, and all such matrices intertwining these representations will be scalar multiples, by Schurs lemma. So essentially there is one matrix $M$, up to scaling with this property.

This matrix $M$ is incredibly interesting however, if it exists, and the automorphism $\sigma$ is order $n$, then $M^n$ is a scalar matrix, so we may assume (by scaling) that $M^n=I$. This gives you the data you need to extend the representation to an irrep of the semidirect product group of $G$ and $\langle \sigma \rangle$.

To give an impression of the depth of the phenomena at play here, if the order of $\sigma$ is coprime to $|G|$, and this matrix $M$ exists, the trace of $M$ (normalised so $M^n=I$) divides the dimension of $V$, and this theorem was only proven recently, before which it was described as one of the deepest problems in character theory by Navarro. See this paper: https://academic.oup.com/blms/article-abstract/26/6/513/400882?redirectedFrom=PDF.


问:
$X\subsetneqq Y$ but $X^\star=Y^\star$
Are there $X,Y$ real Banach spaces, such that $X\subsetneqq Y$ (strictly contained) and $X^\star=Y^\star$, where $\star$ denotes the topological dual?

This property is not true for Hilbert spaces, nor even for $L^p$ spaces, so I was thinking to try some function space: continuous functions or bounded...

Any help is appreciated.

Thank you

答: Choose a point $p$ in $Y$ outside $X$ and construct a linear functinal $f$ on $X+\mathbb R p$ which vanishes on $X$ whereas $f(p)=1$.  By the Hahn-Banach theorem, $f$ extends to a functional on $Y$.  Clearly therefore the duals of $X$ and $Y$ are never the same.</p>

Title: $X\subsetneqq Y$ but $X^\star=Y^\star$


问:
Show that $X_n := \sum_{i=1}^n Y_i$ is a Markov chain where $Y_n$ is an iid random variable on $\mathbb Z^k$
Given $(Y_n)_{n \in \mathbb N_0}$ is an iid random variable on $\mathbb Z^k$ with law $\mu$ I want to show that $X_n=\sum_i^n Y_i$ is a markov chain. My current solution is

$$\begin{align}
P(X_{n+1}=j \, \vert \, X_n=x_n,...,X_1=x_1)&=P(\sum^{n+1}_i Y_i =j \, \vert \, \sum^{n}_i Y_i = y_n+..+y_1,..., Y_1=y_1)\\ &= P(\sum^{n+1}_i Y_i =j \, \vert \, \sum^{n}_i Y_i = y_n+...+y_1) \\ &= P(X_{n+1}=j \, \vert \, X_n=y_n+...+y_1)\end{align}$$
since all information is contained $\sum^{n}_i Y_i$ already, i.e. $X_{n+1}$ only depends on $X_n$.   Is that correct? What would then the transition matrix initial distribution of $X_n$ be?

答:
You have to show that $(X_n)_n$ is a markov chain and therefore have to prove

$$ P(X_n=j|X_{n-1}=i_{n-1},..., X_1=i_1)=P(X_n=j| X_{n-1}=i_{n-1})\\
 $$

For the transition matrix let us look at $p_{i,j}$, i.e.

$$\begin{align}P(X_n=j | X_{n-1}=i)&=P(X_n=j | \sum_{i=1}^{n-1}Y_i=i) \\
&=P(\sum_{i=1}^{n}Y_i=j|\sum_{i=1}^{n-1}Y_i=i) \\
&=P(\sum_{i=1}^{n-1}Y_i+Y_n=j|\sum_{i=1}^{n-1}Y_i=i)\\
&=P(i+Y_n=j) \\
&=P(Y_n=j-i)\end{align}$$

Now what is given in regards to the $(Y_n)_n$ and what is therefore the last probability?


问:
Prove that there are at least $n$ pairwise disjoint sets in the same class.
Let $S$ be a set containing $n^{2}+n-1$ elements, for some positive integer $n$. Suppose that the $n$-element subsets of $S$ are partitioned into two classes. Prove that there are at least $n$ pairwise disjoint sets in the same class.

I was thinking to use induction on $|S|$, with base $n=1$, and it works for $n=1$. However I am not able to proceed.

答:
This is USAMO 2007 Problem 3.

I will prove the stronger claim: If we have $k \cdot (n + 1) - 1$ elements, then we will have at least $k$ disjoint subsets in a class. Applying this result with $k = n$ gives the desired result. We can proceed by inducting on $k$.

When $k = 1$, this is clearly true since if we have $n$ elements, then we'll have $1$ disjoint subset in a class.

Now we consider two disjoint but exhaustive cases.

First consider the case in which all $(n + 1)$-element subsets have all of their $n$-element subsets in a single class. Take any two $n$-element subsets, say $S_1$ and $S_k$. Clearly, there exists a sequence $S_1, S_2, \ldots, S_k$ such that any two consecutive terms belong to the same subset with $n + 1$ elements. Thus, $S_1$ and $S_k$ are in the same class, which means all subsets are in a single class. Therefore, we can find $k$ disjoint subsets of size $n$.

Next consider the case in which there is a single $(n + 1)$-element subset, say $S$, such that $S$ has two $n$-element subsets in distinct classes. In this case, there are exactly $(k - 1)(n + 1) - 1$ elements that aren't in $S$. However, by assumption, we'd have $k - 1$ disjoint subsets in some class, which pair with some other subset. We can use these $k - 1$ subsets to form $k$ disjoint subsets of size $n$, as desired.


问:
Suppose that $f$ and $g$ are measurable functions on $\mathbb{R}^d$. Prove that $f(x-y)g(y)$ is measurable on $\mathbb{R}^{2d}$.
This is a problem that appears in Stein and Shakarchi's Real Analysis text. Below are some  results relevant to this problem that appear elsewhere in the text, stated exactly as they're written there.

Corollary 3.7 : Suppose $f$ is a measurable function on $\mathbb{R}^d$. Then the function $f$ defined by $\tilde{f}(x,y) = f(x)$ is measurable on $\mathbb{R}^{d_1} \times \mathbb{R}^{d_2}$.

Proposition 3.9 : If $f$ is a measurable function on $\mathbb{R}^d$, then the function $\tilde{f}(x,y) = f(x-y)$ is measurable on $\mathbb{R}^d \times \mathbb{R}^d$.

Property 5 (ii) : If $f$ and $g$ are measurable, then $f + g$ and $fg$ are measurable if both $f$ and $g$ are finite-valued.

Remark on Property 5 (ii) : Property 5 (ii) also holds when $f$ and $g$ are finite-valued almost everywhere.

By Corollary 3.7, both $\tilde{f}(x,y) = f(x)$ and $\tilde{g}(x,y) = g(y)$ are measurable on $\mathbb{R}^d \times \mathbb{R}^d = \mathbb{R}^{2d}$. By Proposition 3.9, the function $\tilde{\tilde{{f}}}(x,y) = f(x-y)$ is measurable on $\mathbb{R}^{2d}$.

We have that $f(x-y)$ and $g(y)$ are each measurable on $\mathbb{R}^{2d}$. It remains to show that their product is measurable on $\mathbb{R}^{2d}$, and this is where my question comes in.

By Property 5 (ii) and the remark that follows, the product of two measurable functions is not, in general, measurable ; we need to know that $f(x-y)$ and $g(y)$ are each either finite-valued or finite-valued almost everywhere. However, in the statement of the problem, the only information that we're given is $f$ and $g$ are measurable on $\mathbb{R}^{2d}$. In general, measurable functions are not finite-valued or finite-valued almost everywhere.

Am I missing something ? Is there an underlying assumption about $f$ and $g$ that I'm not paying attention to ? How can I show that $f$ and $g$ are each either finite-valued or finite-valued almost everywhere to complete the proof ?

Thanks !

答:
To address the comment, we could define $(-\infty)(\infty)=-\infty$, which I'm sure is the usual convention. Also, $0\times \infty = 0\times (-\infty)=0$ and so on. The only issues with arithmetic are things like $\frac{1}{\infty}$, $\frac{1}{0}$ and $\infty-\infty$. As long as we avoid these things, everything else works "nicely".

Property 5(ii) can be generalized as  follows:

Let $f,g:\Bbb{R}^d\to [-\infty,\infty]$ be (Lebesgue) measurable. (Actually the domain can be any measure space, but if I recall correctly, Stein and Shakarchi don't get to this until later on). Then, $fg$ is (Lebesgue) measurable. Furthermore, if the sum $f+g$ is well-defined (i.e for every $x\in \Bbb{R}^d$, we have $(f(x),g(x))\notin \{(\infty, -\infty), (-\infty, \infty)\}$), then $f+g$ is also Lebesgue measurable.

The proof of course will have to be different. For instance we could proceed directly. Recall the following equivalences for measurability of a function $f:\Bbb{R}^d\to [-\infty,\infty]$:

For every Borel (or even open) set $V\subset [-\infty,\infty]$, $f^{-1}(V)$ is measurable.

For every Borel (or even open) set $U\subset \Bbb{R}$, the sets $\{f=\infty\}, \{f=-\infty\}$ and $f^{-1}(U)$ are measurable.

So, for the case of the product, we have:
\begin{align}
\{fg=\infty\} &= \bigg(\{f=\infty\}\cap\{0< g\leq \infty\}\bigg) \cup\bigg(\{f=-\infty\}\cap  \{-\infty \leq g < 0\}\bigg)\\
& \cup \bigg(\{g=\infty\}\cap\{0< f\leq \infty\}\bigg) \cup\bigg(\{g=-\infty\}\cap  \{-\infty \leq f < 0\}\bigg)
\end{align}
Each of the eight sets on the right is measurable because $f$ and $g$ are. These are all basic set operations hence $\{fg=\infty\}$ is also measurable. Similar reasoning holds for $\{fg=-\infty\}$. To finish the proof, we need to show that for every Borel $U\subset \Bbb{R}$, the set $(fg)^{-1}(U)$ is measurable; but this follows from the finite version.

Indeed, let $\phi=f$ whenever $f$ is finite, and $0$ elsewhere. Define $\gamma$ in terms of $g$ similarly. Then, $\phi, \gamma$ are measurable because $f$ and $g$ are. Then, for every Borel set $U\subset \Bbb{R}$, we have
\begin{align}
(fg)^{-1}(U) &= (fg)^{-1}(U\setminus \{0\}) \cup (fg)^{-1}(0)\\
&= (\phi\gamma)^{-1}(U\setminus \{0\})\cup f^{-1}(0)\cup g^{-1}(0)
\end{align}
This is a union of measurable sets hence measurable. This completes the proof that $fg$ is measurable.

Essentially it's just a bit of more case work, but apart from that the result is true. Thus, $(x,y)\mapsto f(x-y)g(y)$ is also measurable.


问:
Notation for Ring Extension
If $K$ is a field extension of a field $F$ (that is, $F\subseteq K$), we write $K/F$. But if $R$ is a ring extension of the ring $S$ (that is, $S\subseteq R$), what is the equivalent notation? Do we write $R/S$ like we would for fields or is something like $R\supseteq S$ more appropriate?

答:
I'm not aware of any generally accepted definition of a "ring extension" with no further qualifiers. When you go beyond the case of fields it's much less clear that "an injection $S \to R$" is the correct notion of "ring extension." On the one hand you may want to discuss an arbitrary map $f : S \to R$, not necessarily injective; equivalently, you may want $R$ to be an arbitrary $S$-algebra. This is the most general thing you could ask for and has nice categorical properties. On the other hand you may want to require various properties of the map $f$: for example, that it's

integral (which generalizes algebraic extensions)

flat (automatic if $S$ is a field)

faithfully flat (various nice properties)

etale (also very nice properties but very restrictive)

and lots and lots of other possibilities. I am also not aware of notation for any of these. People just say "let $f : S \to R$ be (whatever)." (Also, it would be standard to write $f : R \to S$ here.)

Title: Notation for Ring Extension


问:
How to label a cube
I can't come up with a clever way to label a cube's faces, such that if I turned it in one of four directions, "Up", "Down", "Left", "Right", I'd know the resulting face by applying a function to the current face number, e.g., right(f) = f + 1, left(f) = f - 1. Any ideas?

Please excuse my terrible ASCII cube. I needn't label them 1 - 6.

Cube:

```<code>     ____
    / 5 /|   3 (back)
   /___/_|
4  | 1 |2|
   |___|/

     6 (underside)
</code>```

答:
Here's something that works, but it takes a little time to explain why it works. Label the top and bottom faces $\infty$ and $0$, respectively, and label the others $1, i, -1, -i$ in counterclockwise order looking down on the cube (where $i$ is the imaginary unit). If $z$ is the label of the current face at a particular location, then

Right rotation is given by $z \mapsto -iz$,

Left rotation is given by $z \mapsto iz$,

Up rotation is given by $z \mapsto \frac{z + 1}{z - 1}$,

Down rotation is given by $z \mapsto - \frac{z - 1}{z + 1}$.

If you know how to compute with complex numbers you should be able to verify all of this, although to really understand how this works you'll have to learn about the Riemann sphere, stereographic projection, and fractional linear transformations.

You can also explicitly write down the quaternions that represent the rotations you want. But really, none of this seems particularly useful for programming applications (in this special case; the quaternions are very useful for more general rotations).

More generally, you are asking a kind of group-theoretic question, asking whether there are elegant ways to describe the group action of the symmetry group of the cube on the faces (equivalently, on the centers of the faces). There are several ways to do this; one can use permutations, which is the standard way to describe group actions, but since our symmetries act by rotations we can also look at ways to represent the special orthogonal group $\text{SO}(3)$ of rotations. Above I make use of two such representations: one identifies it with the projective unitary group $\text{PU}(2)$, whereas another identifies it with the projective symplectic group $\text{PSp}(1)$ of unit quaternions modulo $-1$.

But again, I don't think any of this is particularly useful for a programming application.

Title: How to label a cube


问:
Question on proof of Sylow's first theorem
Let $G$ be a finite group $p$ a prime.If $p^{k}$ divides $|G|$ then $G$ has at least one subgroup of order $p^{k}$.

Confusing part for me in proof :

consider the class equation of the form $|G|=|Z(G)|+\sum|G:C(a)|$.

where we sum over a representative of each conjugacy class $cl(a)$ where $a \notin Z(G)$.

"Since $p^{k}$ divides $|G|=|G:C(a)||C(a)|$ and $p^{k}$ does not divide $|C(a)|$, where $C(a)$ is the centralizer of $a$.''

My confusion is, why this step holds. Why cannot $p^{k}$ divide the order of the centralizer of $a$? I understand everything except the reason why $p^{k}$ cannot divide the centralizer order.

答:
There should be an observation earlier in the proof (maybe at the very beginning) that, if $p^k$ divides the order of a proper subgroup $H$ of $G$, then we're done by induction on $|G|$, because a $p$-Sylow subgroup of $H$ would also be a $p$-Sylow subgroup of $G$.

After this observation, we can assume that $p^k$ doesn't divide the order of any proper subgroup of $G$. That includes the centralizers $C(a)$ for all $a\notin Z(G)$.


问:
What are the technique to solve this type of exercises with closed form solution?
I have the following statement:

Solve for $y$ in $x^y=y^x$ with $x=\sqrt3$.

When i tried to solve i got $y^y=\sqrt{3}^{\frac{1}{\sqrt3}}$ Clearly I have to transform the exponent in such a way that it remains a variable raised to itself, but is hard to me.

The closed-solution is $y=\sqrt{27}$.

What are the techniques to solve exercises involving $x^x=a^b$ with closed form solution?

答:
No general solution without Lambert W as GEdgar said.

But you can try something like this to help you "guess" the 2nd solution:

let $y=kx$

$x^{kx} = {(kx)}^x$

take xth of both sides

$x^k = kx$

$x^{k-1} = k$

$(\sqrt{3})^{k-1} = k$

This seems a bit more manageable.

We know there are two solutions, because the two curves $y={(\sqrt{3}})^{x-1}$ and $y=x$ intersect in two points.

We already know $k=1$ is a solution. At this point without W lambert, I'd just guess and check for the second solution. With a bit of guessing we see $k=3$ works. That gives $y=\sqrt{3}$ or $y=3\sqrt{3}$. We can only get nice solutions because the problem is set up that way.


问:
Relationship between second order derivatives and cross derivative of smooth surfaces
Probably a silly question, but I wonder if $z=f(x,y)$ is a smooth surface, and the values of its two second order derivatives $\frac{\partial^2f}{\partial x^2}$ and $\frac{\partial^2f}{\partial y^2}$ are known to be both positive throughout a region, say $0<x<1$, $0<y<1$, dose this place a restriction on the possible values of the cross derivative, i. e. $\frac{\partial^2f}{\partial x\partial y}$ ?

The naive geometrical idea behind this is: if I cut a surface horizontally (parallel to the $x$-axis) or vertically (parallel to the $y$-axis) and always find an exponential (or other) curve, does this makes a random cut obliquely more likely to be a exponential-like (or other-like) curve ?

答:
Your original question is not as far-fetched as you think. To elaborate on @Jesse Madnick's response, to understand the behavior (i.e., curvature) of the various cross-sections, you need all the Hessian matrix. That is, if the tangent plane to your surface is horizontal, the second-order Taylor polynomial is
\begin{align*}
f(x,y) &= f(0,0) + Q(x,y)\,, \quad\text{where}\\
Q(x,y) &= \tfrac12\left(f_{xx}(0,0)x^2 + 2f_{xy}(0,0)xy + f_{yy}(0,0)y^2\right)\,.
\end{align*}
That is, the curvature of the slice in direction $\vec v$ is obtained by putting $\vec v$ into the quadratic form given by the Hessian matrix.


问:
Is there a standard mathematical way of joining two functions piecewise without losing differentiability?
I am referring to Huber Loss function. It looks something like this:

$\hspace{3.0cm} L_\delta(a) = \begin{cases} \frac{1}{2} a^2 && |a| \leq \delta \\ c |a|-\frac{1}{2}c^2 && |a| > \delta\end{cases}$

Here the two parts are differentiable separately and the ability to differentiate remains even when they are joined.

So is there a mathematical technique to join any arbitrary function to another function and make sure they are differentiable as a whole ?

To elaborate: In here the function $|a|$ is slightly modified using $c$ to make them smoothly connect. What I am asking is whether there's a more established way of doing this ? Maybe a theory or a rule of thumb for the way we need to modify one of the functions so that they remain differentiable.

Basically I'm asking a way to join two functions without losing their continuity during the process.

答:
Basically I'm asking a way to join two functions without losing their
continuity during the process.

I assume the above is meant to say "without losing continuity of the derivative during the process." Losing (general) continuity is easy. To start with, your $L$ depends also on $c$. So it should be defined rather as: $L_{\delta,c}(a)$. You immediately lose (plain) continuity, if you consider, say, $L_{\delta,c\neq\delta}(a)$, so you necessarily also lose continuity of $L_{\delta,c\neq \delta}'=\frac{dL_{\delta,c\neq \delta}}{da}$ at $a=\delta$.

If you consider $L_{\delta,\delta}(a)$ you neither lose continuity of $L$ nor of $L'$, but you lose continuity of $L''$.

So it really depends on the functions you want to join, and centain assumptions must be satisfied first to even talk about joining them "smoothly". Obviously, you can't "join" them if they are discontinuous at their joint point, since you lose continuity. If they are continuous and agree at a point $a=\delta$, then call them $f_1$ for $a\le \delta$ and $f_2$ for $a\ge \delta$. I am not aware of any "general" methods to make them join smoothly, except some rather ad-hoc ways of smoothing them out around their joint point $a=\delta$:

That is, modify $f_1$ on the interval $(\delta-\epsilon,\delta)$ and $f_2$ on the interval $(\delta,\delta+\epsilon)$ so that they posess arbitrary differentiability to the left ($f_1$) and to the right ($f_2$) of $\delta$. One way of doing this is by using bump functions like $\Psi$ in the wiki page or other $C^{\infty}$ functions as interpolants inside the corresponding intervals, as for example:

$$f_1(a) =
\begin{cases}
f_1,  & \text{if $a\le \delta-\epsilon$} \\
\psi_{f_1}, & \text{if $\delta-\epsilon\le a$ and $a\le \delta$}
\end{cases}$$

where $\psi$ is an appropriate bump function that acts as an interpolant for values between $f_1(\delta-\epsilon)$ and $f_1(\delta)$.

There are other ways, too, if you are not restricted to needing $C^{\infty}$ continuity. For $C^n$ continuity, you can use various interpolants $\psi_f$ (instead of bump functions), such as any method used in Numerical Analysis, like bezier curves, splines or polynomial interpolations. Any of these methods however will kill $f_1^{(n)}=f_1^{\overbrace{''\cdots'}^{n\text{ primes}}}$  continuity at some (finite) level $n_0$ around $\delta$, unless you choose the left and right interpolants to have exactly the same degree of (non-zero) differentiability.

All the above methods slightly modify the originals however, if ever so slightly (in the interval $(\delta-\epsilon,\delta+\epsilon)$), so I am not sure that's what you'd want. For two absolutely non-modifiable functions it's fairly clear that it's impossible, unless the degree of differentiability left and right of $\delta$ for $f_1$ and $f_2$ matches by accident.


问:
Generalization of the Cartesian basis in Hilbert space
Given the Hilbert space of continuous functions $H = \{ u : [0,1] \to \mathbb{R}\}$ with
inner product : $ = \int_0^1 u(x)w(x)dx$,

is there a generalization of a Cartesian basis ?

Intuitively, what I want to have is a basis that "picks up" only the value of $u(x)$ at $x$ each time, like (1,0) and (0,1) in $\mathbb{R}^2$

I was thinking something like $B = \{ \delta(x-l), l \in [0,1] \}$, but this is not continuous.

Thanks a lot,

Kostas

答: The problem is that integrals do not change when you change the integrand at a finite number of points (or, even on a set of measure $0$,) which makes it impossible for the integral inner product to give you a pointwise value for a function. You can retrieve an average value over a small interval with an integral such as $\frac{1}{2\delta}\int_{x-\delta}^{x+\delta}u(x)dx=\int K_{x,\delta}u$, but a point value is not possible; otherwise integral convergence would end up forcing pointwise convergence, which is not the case.


问:
Covering a polygon with an odd number of sides
I have the following elementary problem/question that I do not know how to tackle. It comes with a "math-olympiad-flavor" but I suspect it may be much more difficult than an high-school olympiads problem.

Let $\mathscr{P}$ be a simple polygon (not necessarily convex) in the plane, and such that the number of sides of $\mathscr{P}$ is an odd number $2k+1$.

For each vertex $v$ of $P$ there is an intuitive notion of opposite side (because the number of sides is odd), just label the sides counterclockwise at $v$ from $1$ to $2k+1$, and it would be the one with the label $k+1$.

Now suppose that for each vertex and its corresponding opposite side I consider the triangle the determine in the plane. Let us call $\Delta_v$ this triangle and call it a central triangle.

Is the following:

$$ \mathscr{P} \subseteq \bigcup_{v\in \mathscr{P}} \Delta_v$$

always true? In other words, if one paints all central triangles is it true that the whole polygon is then painted?

答:
For convex polygons, I believe the answer is true. You can use ideas similar to the IMO Windmill problem (2011/2).

First, instead of considering the central triangles, we consider a BEAM that goes through a vertex $P$, splits the remaining vertices into two sets of equal size, rotates clockwise while pivoting around the vertex $P$ until it hits another vertex $Q$. This vertex takes over as the new pivot and continues rotating clockwise. This process continues indefinitely, cycling through all of the vertices.

Number the vertices $1, 2, \ldots 2k+1$ in a clockwise manner.

Claim: When the beams is only going through one vertex, then it splits the remaining vertices evenly.

Proof: The number of vertices that are on one side of the beam is an invariant prior to and after connecting with the next pivot. The result follows.

Claim: If the beam is pivoting about vertex $v$, then the next pivot will be $v-k$.

Proof: Because the polygon is convex, the vertices $v-k$ and $v+k = v-k-1$ uniquely satisfy "split the remaining vertices evenly just prior to and after connecting with the next pivot". Due to the clockwise ordering, the sequence is $v-k-1 \rightarrow v \rightarrow  v-1$.

Claim: The area within the polygon which the beam covers, is indeed the union of the central triangle.

Proof: With the pivot at vertex indexed $v$, the prior vertex is $v-k-1$ and the next vertex is $v-k$, so the beam's intersection with the polygon is the triangle $v-k-1, v , v-k$.

Claim: Every point in the convex polygon is covered by this beam (at least once).

Proof:  Consider a point $p$ in the polygon that doesn't lie on any diagonal.

Draw a line through this point $p$, and let it pivot about $p$.

As this line pivots about $p$, when the line intersects a vertex, count the number of vertices to the "left" of the line and to the "right" of the line.

When the line pivots $180^\circ$, these two numbers flip over.
Consider the expression "left vertices minus right vertices". It

has even parity,

changes by exactly 2 each time the line goes through a vertex

changes signage after a $180^\circ$ rotation.

Hence, by "continuity" (applied to the discrete change), it must be equal to 0 after some rotation. Let this vertex be $K$. Then, from the above, the vertex is covered by the central triangle $K-k-1, K, K-k$.

For points $q$ that are on a diagonal, take a sequence of points not on the diagonal whose limit us $q$. The finite union of closed central triangles is closed, and each of the points $p$ lie in a central triangle, hence so does $q$.

Why does this proof work for convex but not for non-convex? Where did we use convexity?

That the pivot goes from vertices $1, k, 2k+1, k+1, \ldots$

That the pivot going from vertices $1, k, 2k+1$ results in the beam intersection with the polygon giving us the desired central triangle

That the point $p$ and corresponding line through vertex $K$ lies in central triangle $K - k, K , K + k$.

I do not know if the statement is true for non-convex polygons. I suspect it is not.
This is not a counter example. It is just a diagram to stare at.


问:
Finding explicit formula for recursive relation
Here is what I've tried, the question is below. I've been working on this problem for a while now, but I am clueless what to try now so I thought I'd see if anyone else could find an explicit formula.
I did (a) and found the recursive relation to be $$R_n = \frac{2}{3}R_{n-1} + \frac{1}{3}R_{n-2}$$
I then used the vales of $R_0 = 0.5$ and $R_1 = 0.4$
From this I was able to deduce a simplified recursive relation,$$R_0 = 0.5$$ $$R_n = R_{n-1} + \frac{(-1)^n}{3^{n-1}*10}$$ which is still a recursive relation and not a closed formula, however this was as far as I could get, does anyone have any ideas?
$$$$Question A model for the chance of rain on a given day on Motonui Island is given by the weighted
average of the chance of rain yesterday (with weight 2/3), and the day before yesterday
(with weight 1/3).
$$$$(a) Under the assumption for this model, find a recurrence relation (Rn)n2N, where
Rn is the chance of rain on day n. Justify your answer.
$$$$(b) Find a closed formula for Rn, if on day 1 the chance of rain is 50%, and on day 2
the chance of rain is 40%. Justify your answer.

答:
The characteristic equation $x^2-\frac{2}{3}x-\frac{1}{3}=0$ has two roots: 1 and $-\frac{1}{3}$.

$$
R_{n+1} + \frac 13 R_n = R_n + \frac 13 R_{n-1} = \cdots = R_1 + \frac{1}{3} R_0 = \frac{17}{30} \tag 1
$$

$$
R_{n+1} - R_n = -\frac{1}{3} (R_n-R_{n-1})  =\cdots = (-\frac 13)^n (R_1-R_0) = -\frac{(-1)^n}{10 \cdot 3^n}\tag 2
$$

(1)-(2)
$$
R_n=\frac{3}{4}\left(\frac{17}{30}+\frac{(-1)^n}{10\cdot 3^n}\right).
$$

Please check my post Show that for every positive integer $ f_n=\frac{\left ( \frac{1+\sqrt5}{2} \right )^n-\left ( \frac{1-\sqrt5}{2} \right )^n}{\sqrt5}$

The above method does not come from nowhere. For a homogeneous second order linear difference equation $$a_{n+2}-b a_{n+1} + c a_n=0 \tag 3$$
its characteristic equation is $f(x)=x^2-bx+c=0$. (3) can be written in the following form:
$$
f(\mathbb{E})a_n=(\mathbb{E}^2-b\mathbb{E} + c)a_n=0 \tag 4
$$
where $\mathbb{E}$ is the forward shift operator such that $\mathbb{E} a_n=a_{n+1}, \mathbb{E}^2 a_n=a_{n+2}$.

Lemma: The solution to $(\mathbb{E}-\lambda)a_n=0$ is $a_n=\lambda^n a_0.$

This is trivial because $(\mathbb{E}-\lambda)a_n=0 \Rightarrow a_{n+1} = \lambda a_n$ which means $a_n$ is a geometric sequence.

Suppose $f(x)=0$ has two distinct roots $r, s$. Then $b=r+s, c=rs$ via Vieta's formulas. Then (3) and (4) become the following, respectively

$$a_{n+2}-(r+s)a_{n+1}+rs a_n=0,\tag 5$$
$$f(\mathbb{E})a_n=(\mathbb{E}-r)(\mathbb{E} - s)a_n=0. \tag 6$$

In the following table you will see that the "shortcut" method is simply a factorization of the characteristic equation in terms of $\mathbb{E}$.

$$
\begin{array}{lcl}
a_{n+1} - s a_n = r(a_n-sa_{n-1})  & | & (\mathbb{E}-r) (\mathbb{E}-s)a_n=0\\
\Rightarrow \color{red}{a_{n+1} - s a_n = r^n (a_1-s a_0)} & | & \Rightarrow \color{red}{(\mathbb{E}-s)a_n = r^n (\mathbb{E}-s)a_0} \text{ via Lemma} \\
a_{n+1} - r a_n = s(a_n-ra_{n-1})  & | & (\mathbb{E}-s) (\mathbb{E}-r)a_n=0\\
\Rightarrow \color{blue}{a_{n+1} - r a_n = s^n (a_1-ra_0)} & | & \Rightarrow \color{blue}{(\mathbb{E}-r)a_n = s^n (\mathbb{E}-r)a_0} \text{ via Lemma} \\
\end{array}
$$

Subtracting the blue equation from the red, you get
$$
a_n=\frac{a_1-s a_0}{r-s} r^n  - \frac{a_1-r a_0}{r-s} s^n
$$

Solution with duplicate roots

There is also a shortcut. If $f(x)=(x-\lambda)^2$, or
$$a_{n+1} - 2\lambda a_n + \lambda^2 a_{n-1}=0.$$

If $\lambda=0$ it's trivial: $a_n=0$. Otherwise $\lambda \neq 0$, then
$$\frac{a_{n+1}}{\lambda^{n+1}} - 2 \frac{a_n}{\lambda^n} + \frac{a_{n-1}}{\lambda^{n-1}}=0 \Rightarrow \frac{a_{n+1}}{\lambda^{n+1}} - \frac{a_n}{\lambda^n} = \frac{a_n}{\lambda^n} -  \frac{a_{n-1}}{\lambda^{n-1}} = \cdots =\frac{a_1}{\lambda} - a_0$$

So $\frac{a_n}{\lambda^n}$ is an arithmetic sequence,
$$
\frac{a_n}{\lambda^n}=\frac{a_0}{\lambda^0}+n\left( \frac{a_1}{\lambda} - a_0\right) \Rightarrow a_n = \lambda^n(na_1/\lambda-(n-1) a_0).
$$

Other examples

Some non-homogeneous linear difference equations can be converted to homogeneous higher order ones.

Example 1: Recurring Sequence with Exponent

Example 2: $a_n=3a_{n-1}+1$.

For this one, although we can convert to $a_{n+1} - 3a_{n} = a_n-3 a_{n-1}$, it's easier to do the following: $a_n + \frac 12 =3a_{n-1}+\frac{3}{2} = 3 (a_{n-1} + \frac 12) \Rightarrow a_n+\frac 12 = 3^n (a_0+\frac{1}{2}).$

Example 3 (a higher order example illustrating the use of forward shift operator): Is it possible to solve this recurrence equation?


问:
Understanding $\zeta(s, x+y) = \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} (-y)^{k} \zeta(s+k,x) $
Currently, I'm trying to understand how the the equation $$\zeta(s, x+y) = \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} (-y)^{k} \zeta(s+k,x) $$ is derived.

I know that that the following derivative, a shift, is relevant: $$ \frac{\partial}{\partial q} \zeta(s,q) = -s \zeta(s+1,q). $$
Following the approach in the link above, one finds \begin{align}\zeta(s,x+y) &= \sum_{k=0}^{\infty} \frac{y^{k}}{k!} \frac{\partial^{k}}{\partial x^{k}} \zeta(s,x) \\ &= \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} (-y)^{k} \zeta(s+k,x). \qquad \qquad(*) \end{align}

In part, I understand equation $(*)$, but not fully. I see that \begin{align} \frac{1}{k!}\frac{\partial^{k}}{\delta x^{k}} \zeta(s,x) &= (-1)^{k}s(s+1)\dots(s+k-1)\zeta(s+k,x) \\
&= \binom{s+k-1}{s-1} \zeta(s+k,x), \end{align}
but there is some part of the equation I don't understand:

Where does the $x+y$ part come from in $\zeta(s,x+y) $ in $(*)$?

Furthermore, I don't see how the equation $$\zeta(\nu+2) = \sum_{k=0}^{\infty} \binom{k+\nu+1}{k} [ \zeta(k+\nu+2)-1  ] \qquad \qquad (**) $$ results from $(*)$. It is mentioned in the wiki article that $y=-1$ is chosen, but which value of $x$ is then picked?

答:
First, let's remember the definition of the Hurwitz zeta function
\begin{eqnarray*}
\zeta (s,q)= \sum_{n=0}^{\infty} \frac{1}{(n+q)^s}.
\end{eqnarray*}
We will also need the following useful formula
\begin{eqnarray*}
\sum_{k=0}^{\infty} \binom{s+k-1}{k} X^k =\frac{1}{(1-X)^s}.
\end{eqnarray*}
It is actually a total doddle from here ... invert the order of the plums, do the $k$ plum & ... definition of HZ again.

 $$ \sum_{k=0}^{\infty} \binom{s+k-1}{k} (-y)^k \zeta(s+k,x) = \sum_{k=0}^{\infty} \binom{s+k-1}{k} (-y)^k \sum_{n=0}^{\infty} \frac{1}{(n+x)^{s+k}} \\ = \sum_{n=0}^{\infty} \frac{1}{(n+x)^{s}}\sum_{k=0}^{\infty} \binom{s+k-1}{k}  \frac{(-y)^k }{(n+x)^{k}} \\ = \sum_{n=0}^{\infty} \frac{1}{(n+x)^{s}}\frac{1}{\left( 1+ \frac{y }{n+x} \right)^s} = \zeta(s,x+y) $$


问:
Convergence, link with Sierpinski triangle

This image shows the construction of the Sierpinski triangle up to the fourth iteration. My question is simple.

If I construct a sequence of subsets of the triangle in this way :

$\mathcal{E}_{0}=\emptyset$

$\mathcal{E}_{i}$ is the union of the white closed subsets in the triangle at the i-th iteration of the Sierpinski triangle construction.

I know that the k-th element of this sequence is the closed complementary of the approximation of the Sierpinski triangle and that this sequence is increasing and bounded so i suppose that it converges.

So I would like to know if this sequence tends to the triangle or tends to the triangle difference ``something''.

答: Perhaps a definition is needed for "tends to".  Sequence $\mathcal E_n$ tends to the filled-in triangle $\mathcal T$ in the Hausdorff metric.  Every point of $\mathcal T$ is arbitrarily close to some point of $\mathcal E_n$ for large enough $n$.  (And every point of $\mathcal E_n$ is already in $\mathcal T$.)</p>


答:
All possible rational solutions come from rational $u$ with
$$ x = \left( 1 + \frac{1}{u} \right)^u \; , \; \; \;  y = \left( 1 + \frac{1}{u} \right)^{1+u} $$

To get $x,y$ rational there are conditions on $u$ beyond being rational.  On the other hand, failing the extra conditions  still gives a solution to $x^y = y^x,$  now irrational.

The point is that $$  u = \frac{1}{2}   $$ gives what you want.

Title: What are the technique to solve this type of exercises with closed form solution?

Body:
I have the following statement:

Solve for $y$ in $x^y=y^x$ with $x=\sqrt3$.

When i tried to solve i got $y^y=\sqrt{3}^{\frac{1}{\sqrt3}}$ Clearly I have to transform the exponent in such a way that it remains a variable raised to itself, but is hard to me.

The closed-solution is $y=\sqrt{27}$.

What are the techniques to solve exercises involving $x^x=a^b$ with closed form solution?


问:
What is the probability that a random walk on this graphs ends at point A?
Consider the symmetric RW on a graph constructed from two cycles $C_{m}$ and $C_{n}$ in such a way that the two cycles have exactly two consecutive common vertices, like in Figure 2.

Let S denote one of the two common vertices, let S' denote the other common vertex, let A be a vertex of $C_{m}$ not in $C_{n}$, and let B be a vertex of $C_{n}$ not in $C_{m}$. Suppose now that $m=2*10^{6}+1$, where the SS' A-arc is a path of $10^{6}+1$, edges and the other SA-arc(=“lower arc”) is a path of $10^{6}$ edges; and $n = 4*10^{6} +1$, where the SS'B-arc is a path of $2*10^{6} +1$ edges, and the other SB-arc(=“lower arc”) is a path of $2 * 10^{6}$ edges.

I am interested in the probability that the symmetric random walk, starting from S, ends at endpoint A. B is also an end point, however we are interested in solving the probability it ends at A. If the random walk reaches A at any time it immediately ends.

答:
I'm going to assume the random walk also stops when reaching $B$, which the question currently doesn't say; otherwise, the probability is just $1$.

Divide the diagram into a top half (consisting of the $A,B$-path passing through $S'$) and a bottom half (consisting of the $A,B$-path passing through $S$).

By symmetry, the probability of reaching $A$ before $B$ is the same for a vertex in the top half and the corresponding vertex in the bottom half. So we can just solve the same problem for a random walk on a single $A,B$-path of length $3 \cdot 10^6$.

For this random walk, the probability of reaching $A$ before $B$, starting from $S$, is well-known to be $\frac{d(S,A)}{d(S,A) + d(S,B)}$ which gives $\frac13$ in this case.


问:
Compact Hermitian nilpotent operator implies zero operator
Let $A$ be a compact, Hermitian operator. Prove that if $A^n=0$ for some $n$, then $A=0$.

I'm not sure where to start on this question, and I'm having trouble seeing how I can exploit the fact that $A$ is Hermitian. Any help or hints would be appreciated!

答:
Suppose $A$ is a bounded Hermitian operator on a Hilbert space $H$, and further suppose that $A^n=0$ for some $n$. If $n$ is even then $A^{n/2}=0$ because
$$
              0=\langle A^n x,x\rangle=\|A^{n/2}x\|^2,\;\;\; x\in H.
$$
If $n > 1$ is odd, then $A^{n+1}=0$, which gives $A^{(n+1)/2}=0$.

Repeating this argument through finite induction leads to the conclusion that $A=0$


问:
Prove Divide and Combinations.
I have this question: n is a positive integer. s is a largest non negative integer such that $2^{s}|n$. How can I prove $2^{s}|\binom{n}{k}$ for every odd integer k, so that $1 \leq k \leq n$.

Well I know that if $1 \leq k \leq n$, then $\frac{n}{gcd(n,k)}|\binom{n}{k}$. This is from Google Searching. But how is it I can use this to prove the equation. I haven't solved it. But can I make $$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{m}^{\alpha_{m}}$$ and $$k=q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}...p_{m}^{\beta_{m}}$$

Then $\gamma_{i}
=\text{min(}\alpha_{i}, \beta_{i}\text{)}, i=1,2,....m$.Thank you for your time.

答:
No need to use all those primes, you just care about $2.$
If $n$ is odd, then $s=0$ so there is nothing to show because $1$ divides every number.
If $n$ is even and $k$ is odd, then $n/gcd(n,k)=2^s\cdot n_1,$ where $n_1=\frac{n}{2^sgcd(n,k)},$ notice that $gcd(n,k)$ is odd because it has to divide $k,$ so $n_1$ is an integer and we have that $n/gcd(n,k)=2^s\cdot n_1|\binom{n}{k},$ hence $2^s|\binom{n}{k}$ by transitivity.

Title: Prove Divide and Combinations.


问:
An integral involving the Riemann zeta function
Let $c\in \mathbb{R^{+}}$, $0<\delta<1$, and $s\in \mathbb{C}:\;\Re(s)+c>1$.  We have the integral :
$$\frac{1}{2\pi i }\int_{c-i\infty}^{c+i\infty}\frac{\zeta(s+z)}{z(z+1)}\left((1+\delta)^{1+z}-\delta^{1+z}\right)dz$$
I tried shifting the line of integration to the left of zero, picking up the residues at $z=1-s$ and $z=0$, but i have no idea on how to do the integral :
$$\frac{1}{2\pi i }\int_{c^{'}-i\infty}^{c^{'}+i\infty}\frac{\zeta(s+z)}{z(z+1)}\left((1+\delta)^{1+z}-\delta^{1+z}\right)dz\;\;\;\;c<0$$
Any help is appreciated.

答:
We have :
$$\frac{1}{z+1}\left((1+\delta)^{1+z}-\delta^{1+z}\right)=\int_{\delta}^{1+\delta}x^{z}dx$$
and by Perron's formula :
$$\frac{1}{2\pi i }\int_{c-i\infty}^{c+i\infty}\zeta(s+z)\frac{x^{z}}{z}dz=\acute{\sum_{n \leq  x}}\frac{1}{n^{s}}=\zeta(s)-\zeta(s,x+1)$$
where $\zeta(\cdot,\cdot)$ is the Hurwitz zeta function. Thus :
$$\frac{1}{2\pi i }\int_{c-i\infty}^{c+i\infty}\frac{\zeta(s+z)}{z(z+1)}\left((1+\delta)^{1+z}-\delta^{1+z}\right)dz=\int_{\delta}^{1+\delta}\left(\zeta(s)-\zeta(s,x+1\right)dx$$
$$=\zeta(s)-\frac{(\delta+1)^{1-s}}{s-1}$$


问:
Show $A^T U A=0$ iff $A=0$ when $U$ is positive semidefinite matrix
Let $U$ a symmetric,positive definite matrix. It's known that $A^T UA$ is a positive semidefinite matrix. My goal is to show that

$A^T U A =0$ iff $A=0$

The $\Longleftarrow$ implication is trivial.

The $\Longrightarrow$ is tricky to me: I'll try to show it by contradiction: suppose $A \ne 0$. Then, given a non-zero $v$ we have $Av = w \ne 0$

This implies that $v^TA^TUAv =w^TUw >0$ since U is S.P.D. How can I conclude that the whole matrix $A^T U A\ne 0$ ?

Any help is highly appreciated.

答: You don't need to consider the contrapositive. If $A^TUA=0$, then $x^TA^TUAx$ is identically zero. Since $U$ is positive definite, we obtain $Ax=0$. But $x$ is arbitrary. Hence $A$ must be zero.


问:
GgT, (polynomial) division and finite fields...
Exercise: Let $f,g \in \mathbb{Z}_2[x]$ be the polynomials $f = x^6 + x^5 + x^4 + 1$ and $g = x^5 + x^4 + x^3 + 1$. Has the diophantic equation $f u + g u = x^4 + 1$ solutions $u,v \in \mathbb{Z}[x]$? If so, determine them all.

My Solution: First I observed that in $\mathbb{Z}_2$ the relations
\begin{align}
  -x & = x \\
   x + x & = 0 \\
   x^n = x
\end{align}
hold. From this the polynomials $f,g$ reduce to $f = g = x + 1$, so they are the same and so $ggT(f,g) = x + 1$. Now $x^4 + 1 = x + 1$, so $u = 0, v = 1$ is a special solution. To get all solutions, I add solutions of the homogenous part $fu + gv = 0$, i.e. $fu = gv$ with my relations. But because $f = g$, this forces $u = v$, so I could choose for $u$ and $v$ some arbitrary polynomial. So all solutions $(u,v)$ are of the form
\begin{align}
  u & = p \\
  v & = 1 + p
\end{align}
for some polynomial $p \in \mathbb Z_2$.

Reference Solution: First it has to be checked if $x^4 + 1$ is a multiple of
the ggT of $f$ and $g$, then the equation has a solution (criterium for lineare diophantic equations). The euclidean algorithms yields the ggT. It is $f = (x+1)g + x^4 + x^3 + x^2 + x = (x+1)g + r_1$, $g = xr_1 + x^2 + 1$ and $r_1 = (x^2 + x)(x^2 + 1)$. So $ggT(f,g) = x^2 + 1$, and because of $(x^2+1)^2 = x^4 + 1$ the diophantic equation has a solution.

The general solution is given by the sum of a special solution and the general solution of the homogenous part $fu + gv = 0$. The special solution could be obtained by the euclidean algorithm (Lemma of Bezout). With $1 = -1$ we got
$$
  x^2 + 1 = g + xr_1 = g + x(f + (x+1)g)) = xf + (x^2 + x + 1)g.
$$
One special solution for the representation of the ggT is therefore $(x, x^2 + x + 1)$, one special solution of the original equation $(x(x^2+1), (x^2+x+1)(x^2+1)) = (x^3 + x, x^4 + x^3 + x + 1)$.

For the homogenous part $fu = gv$ we divide by the ggT. It is $f = (x^4+1)(x^2+1)$ and $g = (x^3+x^2+1)(x^2+1)$, a solution $(u,v)$ thus has the property $x^2+x^2+1 | u$ and $x^4+1 | v$. Therefore $u = p \cdot (x^3 + x^2 + 1)$. Substitution yields $v = p\cdot (x^4 + 1)$ and furthermore every $u = p\cdot (x^3 + x^2 + 1)$ and $v = p\cdot (x^4 + 1)$ are solutions. Therefore $\{ (p\cdot (x^3+x^2+1), p\cdot (x^4+1)) : p \in \mathbb Z_2[x]\}$ is the solution set of the homogenous part. The solution set is therefore
$$
 \{ (x^3 + x + p\cdot (x^3 + x^2 + 1), x^4 + x^3 + x + 1 + p\cdot (x^4+1)) : p \in \mathbb Z_2[x] \}.
$$

Now I understand the reference solution, it is the standard way of solving the problem. But my solution seems much simpler to mean, so I wonder why they didn't consider it, or maybe my solution is just wrong? But then why should it be wrong?

答:
You are taking polynomials, so it is incorrect to say that $x^n = x$ in $\Bbb{Z}_{2}[x]$. Actually you have that
$$
a_{0} + a_{1} x + \dots + a_{n} x^{n}
=
b_{0} + b_{1} x + \dots + b_{n} x^{n}
$$
for two elements of $\Bbb{Z}_{2}[x]$
if and only if $a_i = b_i$ for all $i$.

Most likely you are mixing up polynomials and polynomial functions.


问:
How to formulate ordinary least squares regression in component formalism?
Matrix formulation is straightforward:

$\mathbf{y} = \mathbf{X} \boldsymbol{\hat{\beta}} +\boldsymbol{\hat{\varepsilon}}$

cost function:
$E = {\boldsymbol{\hat{\varepsilon}}}^T{\boldsymbol{\hat{\varepsilon}}} = {(\mathbf{y} - \mathbf{X}\boldsymbol{\hat{\beta}})}^T(\mathbf{y} - \mathbf{X}\boldsymbol{\hat{\beta}})$

... differentiating wrt $\boldsymbol{\hat{\beta}}$ and searching for extremum:

$\frac{\partial E}{\partial \boldsymbol{\hat{\beta}}} = 2 \mathbf{X}^T\mathbf{X} \boldsymbol{\hat{\beta}} - 2 \mathbf{X}^T \mathbf{y} = 0$

thus the OLS estimate of $\boldsymbol{\hat{\beta}}$ is:
$\boldsymbol{\hat{\beta}} = (\mathbf{X}^T\mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}$

So, there is probably some limitation to the previous relation (e.g. $(\mathbf{X}^T\mathbf{X})^{-1}$ have to exist) ... am I right?

If I try to make the same with component notation, there is a problem in the same formula (I'll come back later to this).

In component formalism (using Einstein's summation convention):

$E = (X_{ij} \beta_j - y_i)^2 = (X_{ij}\beta_j)^2 - 2 X_{ij}\beta_j y_i + y_i^2$

$\frac{\partial E}{\partial \beta_j} = 2X_{ij} \beta_j X_{ij} - 2X_{ij} y_i = 0$

$X_{ij} \beta_j X_{ij} = X_{ij} y_i$

Now, every term is just scalar, so it's tempting to cancel $X_{ij}$ on both sides.
However, this just leads to trivial relation: $y_i = X_{ij} \beta_j$

Can someone help me to enlighten this, please? Isn't it somehow connected to the use of only lower indices? When I have to consider both lower and upper indices (tensors and duals)?

Thank you!

答:
The error in your component derivation: When you differentiate wrt $\beta_j$, the index $j$ now has two roles: one as the generic index in the sum, and one as the index specifying which $\beta$ you are differentiating with respect to. The partial derivative wrt $\beta_j$ should treat the other $\beta$'s as constant, but your notation can no longer distinguish them!

Better to use a new index, say $k$, to perform the differentiation. When you do this, you find that the partial derivative will be
$$\frac{\partial E}{\partial\beta_k}=2X_{ij}\beta_jX_{ik} - 2X_{ik}y_i.\tag1$$
There's still summing going on (involving $i$ and $j$, with $k$ held constant) when you set (1) to zero, so it doesn't make sense to factor out $X_{ij}$. Convert back into matrix notation and you'll get
$$X^TX\beta=X^Ty.\tag2$$
Specifically, $\sum_i\sum_jX_{ij}\beta_jX_{ik}$ is the $k$th member of the vector $X^TX\beta$, while $\sum_iX_{ik}y_i$ is the $k$th member of $X^Ty$.


问:
What are the most broadly applicable or general areas of mathematics?
Background:

I am in the final year of a bachelor's degree program in Data Science with the University of London. I am interested in exploring the possiblity of going to graduate school for pure mathematics, most likely at the master's level in Canada. (I live in Canada.)

All of my studies with the University of London are done remotely and with almost no support from my institution, so I don't really have anyone to ask for any kind of advice. I have recently had some correspondence with the math department chair at a top Canadian university and was told that students must have supervisors in order to be admitted, and that I would significantly improve my chances of admission if I had some idea of my research interests and who my supervisor would be.

To provide some context, I am currently about 130 pages into Analysis I by Amann and Escher, 20 pages into Algebra by Lang, and 20 pages into Topology: A Categorical Approach by Bradley et al. In other words, I am currently working on what I consider to be relatively foundational mathematics, so the idea of mathematical research seems very far off to me.

I do not know precisely what kind of research I would be interested in. As mentioned, I have no one to ask for advice about this at my university, which is why I am asking about this here.

I am not sure exactly what I will end up doing for a career---I think academia is probably quite unlikely for me---so I would like to try to keep my options open as much as possible. To my mind, part of keeping my options open is to try to learn math that is broadly useful as opposed to niche. If you permit the metaphor of mathematics knowledge as being tools in a toolbag, I am more interested in tools that are more commonly used and/or more versatile as opposed to highly specialized tools that are inapplicable outside of a narrow set of circumstances.

End of background

To that end, I am trying to figure out what the most "general" areas of math are, as opposed to niche areas of math. I do not quite know what I am looking for, but I will try to give some examples:

-Without citing any sources, I would say that calculus and linear algebra are probably tremendously versatile, although perhaps not advanced enough to be considered research interests (?)

-If you look at the list of applications of differential geometry on Wikipedia (https://en.wikipedia.org/wiki/Differential_geometry#Applications) you will see it's quite long and varied.

-Wikipedia says that representation theory is "pervasive across fields of mathematics"; also, p. xi of A Tour of Representation Theory by Lorenz says that "representation [theory] enjoys the additional benefit of having applications in myriad contexts other than algebra, ranging from number theory, geometry and combinatorics to probability and statistics [58], general physics [198], quantum field theory [210], the study of molecules in chemistry [49] and, more recently, machine learning [126]."

-At 12:30 in the video https://www.youtube.com/watch?v=vOboYNh_5is, Ravi Vakil seems to suggest that algebraic geometry is in some sense the "unification" of number theory, geometry, algebra and topology.

-Edward Frenkel has said that the Langlands program is "a kind of grand unified theory of mathematics."

Something that, as far as I know, is relatively niche and thus an example of something I'm not looking for would be algebraic number theory. (See for example: https://mathoverflow.net/questions/24971/practical-applications-of-algebraic-number-theory).

I appreciate any help.

TL;DR I am looking into grad school and have been told that I should try to figure out what my research interests are. I don't have any particular interests. I'm trying to figure out which areas of math are the most broadly useful.

答:
Two more suggestions based on the links https://www.reddit.com/r/math/comments/1d9vgy/which_fields_of_higher_mathematics_do_you/ and https://mathoverflow.net/questions/162125/what-areas-of-pure-mathematics-research-are-best-for-a-post-phd-transition-to-in: differential equations and probability theory.

I should also point out that there is a sizable portion of opinions along the lines of "it doesn't matter exactly what you specialize in in graduate school; just make sure to spend some time getting comfortable with statistics, machine learning and computer programming."


问:
Why the set of polynomials is not closed in $C[0,1]$
This question starts from the following theorem: "Every finite dimensional subspace $Y$ of
a normed space $X$ is closed in $X$" (Kreyzig 2.4-3)

So the given counterexample for an infinite dimension subspace, is that if we take $X=C[0,1]$ and $Y = span\{x_0,x_1,x_2...\}$, where $x_j = t^j$, then $Y$ is not closed.

I guess this is the case because for example a sine function can be expressed as the limit point of a sequence of polynomials that converge uniformly (Taylor series). But why is the sine function not considered as a polynomial generated by an infinite basis? After all, we are explicitly saying $Y$ is infinite dimensional. For an infinite dimensional basis case, I would expect to have a mapping between every sequence to a polynomial in $C[0,1]$. If this is not the case, what exacly does it mean for $span\{x_0,x_1,x_2...\}$ to be considered infinite dimensional? If I input an infinite basis, it seems like it is not longer a polynomial.

I am confused.

答:
Even when a vector space is infinite-dimensional, each vector is written as a finite linear combination of basis vectors. Similarly, the definition of $\textrm{span}(S)$ is "the set of all finite linear combinations of elements from $S$".

Thus, even though the sine function can be written as an infinite series, we still define the set of all polynomials to be those functions that can be written as a finite sum of monomials.

The reason for not allowing infinite linear combinations is that this requires some notion of convergence and limits. While in specific cases this is possible, for a general abstract vector space there is no notion of convergence. Even in the case of the polynomials converging to the sine function, this convergence is only uniform on a compact set, not uniform over $\mathbb{R}$, so there is still some choice to be made for how to define convergence.


问:
Examples of a K3 surface in a product of $\mathbb P^1$'s
On the Wikipeida page for K3 surfaces,
there are several examples listed of how to produce a K3 surface
as a subvariety of
projective space
by taking polynomials of specified degrees.
Namely, a K3 surface is cut out by

a degree 4 polynomial in $\mathbb P^3$,

a degree 2 and a degree 3 polynomial in $\mathbb P^4$, and

three degree 2 polynomials in $\mathbb P^5$.

Are there similar examples
of how to get a  K3 surface
as an explicit subvariety of $\mathbb P^1 \times \cdots \times \mathbb P^1$?
Or is there a reason this is not possible?

答:
Huybrechts' book (1.4.1, page 18) gives an example in $\mathbb P^1 \times \mathbb P^1 \times \mathbb P^1$:

Smooth hypersurfaces $X \subset \mathbb P^2 \times \mathbb P^1$ and $X \subset \mathbb P^1 \times \mathbb P^1 \times \mathbb P^1$ of type $(3, 2)$ and $(2, 2, 2)$, respectively, provide K3 surfaces.


问:
Are all elements of an abelian fundamental group path homotopic?
Consider the fundamental group of some topological space $X$. Is it true that if this group is abelian, then all elements are necessarily path homotopic?

答:
I have a slightly silly answer:

Remember the fundamental group relies on a choice of basepoint. So if you take any disconnected space (in particular not path connected) "the" fundamental group will only refer to one of the components. And thus can be abelian when the space is disconnected.

This is one place where the fundamental groupoid begins to look more appealing, as the fundamental groupoid of a disjoint union of spaces is the disjoint union of the groupoids.

For a less silly example, you can run the same argument as outlined in the answer to this question. But take $W$ to be your favorite path connected space with a trivial fundamental group.

Again, this relies on the fact that you need a choice of basepoint. But this isn't really cheating, because the fundamental group can't detect things in other path components (since it's constructed with paths). So any counterexample to claims involving path-disconnected spaces will need to be at least a little bit silly in this way.

I hope this helps ^_^


答:
In fact, you can prove that (thanks to binomial coefficients)

$\sum_{r=0}^{n_{k}}C_{n_k}^{r}M^{N-n_{k}+r}x^{n_{k}-r} = M^{N-n_k} (M+x)^{n_k}$.

Assume $M>0$.

So now we need to prove that $\left(\frac{M}{M+x}\right)^{N-n_k}\le 2^N$, which is obvious.

Title: How prove this equality $\sum\limits_{r=0}^{n_{k}}C_{n}^{r}M^{N-n_{k}+r}x^{n_{k}-r}\le(1+1)^N(M+x)^N$

Body:
prove that
$$\sum_{r=0}^{n_{k}}C_{n}^{r}M^{N-n_{k}+r}x^{n_{k}-r}\le(1+1)^N(M+x)^N$$

and $x\in R,x>0, n_{k},N \in N^{+},N-n_{k}+r>0,n_{k}-r>0$

where
$C_{n}^{m}=\dfrac{n!}{m!(n-m)!}$


问:
Confusion regarding inverse of formal Laurent series
I am trying to understand the discussion in my course notes about algebraic manipulation of generating functions.

Below I've pasted the whole section, though my confusion is greatest regarding the part that starts with "To illustrate this" and continues until the end.

Excerpt:

Discussion:

I don't understand what is being illustrated in the section beginning with "To illustrate this". Are $1 + x, 1 + x - x^2$ and $1 + x - x^2 + x^4$ supposed to be successive approximations to $f^{-1}(x)$?

I tried to figure out what, in general, the inverse of a formal Laurent series would look like, and I came up with the following:

To find the inverse of the Laurent series $f(x) = a_k x^k + a_{k + 1} x^{k + 1} + \dots$, we seek a Laurent series $g(x) = b_l x^l + b_{l + 1} x^{l + 1} + \dots$ such that multiplying the two together in either order produces the Laurent series with 1 in position zero and 0 in all other places. Given our understanding of multiplication, that means we desire a series with coefficients such that $\sum_{j \in \mathbb Z} p_j q_{0 - j} = 1$, and $\sum_{j \in \mathbb Z} p_j q_{n - j} = 0$ for all other $n$.

For the zero position of the product we want 1, so it makes sense to let the first term for $g$ be $a_k^{-1}x^{-k}$. That way, the multiplication produces 1 for the 0th term.

For the one position of the product we want 0, so that means we need $p_k q_{1 - k} + p_{k + 1} q_{1 - (k + 1)} = 0$, or $p_k q_{-k + 1} + p_{k + 1} q_{-k} = 0$, which implies that $q_{-k + 1} = - \frac{p_{k + 1} q_{-k}}{p_k}$, so the second term of $g$ will be $- \frac{p_{k + 1} q_{-k}}{p_k} x^{-k + 1}$.

For the two position of the product we want 0, so following the same pattern, we need $p_k q_{2 - k} + p_{k + 1} q_{2 - (k + 1)} + p_{k + 2} q_{2 - (k + 2)} = 0$, or $p_k q_{-k + 2} + p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k} = 0$, which implies that $q_{-k + 2} = - \frac{p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k}}{p_k}$, so the second term of $g$ will be $- \frac{p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k}}{p_k} x^{-k + 2}$. Thus, we should have

\begin{align*}
g(x) &= a_k^{-1}x^{-k} - \frac{p_{k + 1} q_{-k}}{p_k} x^{-k + 1} - \frac{p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k}}{p_k} x^{-k + 2} - \dots
\end{align*}

although I should really translate it into terms of $a$, which gives me

\begin{align*}
g(x) &= a_k^{-1}x^{-k} - \frac{a_{k + 1} a_k^{-1}}{a_k} x^{-k + 1} - \frac{a_{k + 1} \frac{a_{k + 1} a_k^{-1}}{a_k} + a_{k + 2} a_k^{-1}}{a_k} x^{-k + 2} - \dots.
\end{align*}

Unfortunately, when I let $f(x) = 1 - x + 2x^2 - 3x^3 + 4x^4 - \dots$ as in the notes above, and then try to use the formula I've derived, I end up with $f^{-1}(x) = 1 + x  - 3x^2 \dots$, which doesn't match the approximations given. But I'm not even sure what the approximations are supposed to be approximating, so I don't know if there is a problem or not.

I appreciate any responses regarding my confusion and corrections regarding my derivation of the inverse Laurent series more generally.

答:
Yes, $1+x$, $1+x-x^2$, and $1+x-x^2+x^4$ are successive approximations to $f^{-1}(x)$; this is a bit clearer, I think, if one writes $\frac1{f(x)}$ instead of $f^{-1}(x)$. Notice that the products of these three polynomials with $f(x)$ progressively eliminate the $x$ term, the $x^2$ and $x^3$ terms, and the $x^4$ term. This is an example of the term-by-term algorithm for finding $\frac1{f(x)}$. It is perhaps a little unfortunate that the example is an ordinary power series: an example starting with an $x^{-2}$ term, say, might be more helpful.

What you’re trying to do in the long block quote at the end is fine, and

$$-\frac{p_{k+1}q_{-k+1}+p_{k+2}q_{-k}}{p_k}x^{-k+2}$$

is correct: in the example it evaluates to

$$-\frac{(-1)(1)+(2)(1)}1x^2=-x^2\,,$$

as it should. It appears that when you translated it back to $a_i$ coefficients you inadvertently changed the sign of $q_{-k+1}$.


问:
Let $f∈C^{(n+1)}(a,b)$and suppose $x_o∈(a,b)$ and $f′(x_o) =···=f^{(n)}(x_0) = 0$ but $f^{(n+1)}(x_o) \neq 0$.
Let $f∈C^{(n+1)}(a,b)$and suppose $x_o∈(a,b)$ and $f′(x_o) =···=f^{(n)}(x_0) = 0$ but $f^{(n+1)}(x_o) \neq 0$.  Then in $x_o$ the function f has

(i)  a strict local minimum, if $n$ is odd and $f^{(n+1)}(x_o)>0$,

(ii)  a strict local maximum, if $n$ is odd and $f^{(n+1)}(x_o) < 0$

(iii)  no extremum, if $n$ is even.

My work

Not a lot actually. I definitely do understand why the properties are as such. But where I am having trouble is explicitly writing it down in appropriate mathematical language. As such, what would be a "model answer" for questions like this that prove the statements conclusively?

答:
Here are some big hints.

Since $f^{(n+1)}(x_0)\neq 0$ and $f^{(n+1)}$ is continuous, there exists $\delta$ such that $f^{(n+1)}(x)$ has the same sign as $f^{(n+1)}(x_0)$ for all $x$ with $|x-x_0|<\delta$.

Then apply Taylor's theorem. For all $x$ with $|x-x_0|<\delta$, we may write
$$
f(x)=f(x_0)+f'(x_0)(x-x_0)+\ldots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+\frac{f^{(n+1)}(c)}{(n+1)!}(x-x_0)^{n+1}
$$
for some $c$ between $x$ and $x_0$. It should be obvious how to break it up into cases and determine when $f(x)>f(x_0)$ and when $f(x)<f(x_0)$.


问:
A σ-structure is called rigid if it has no σ -automorphisms other than the identity. Show the structures $(N,0,S,+,·)$ and $(Q,0,1,+,·)$ are rigid.
An σ-isomorphism is a σ-homomorphism that has a 2-sided inverse , which is also a σ-homomorphism. For $(N,0,S,+,·)$ to be rigid, it would mean that it has a 2-sided inverse (other than the identity). For $(Q,0,1,+,·)$ to be rigid, it would mean that it has a 2-sided inverse (other than the identity). That is impossible in both cases. However I'm having a hard time proving it. It's pretty easy to prove the contrary ie. giving an example of an σ-automorphism other than the identity. But, now we need to prove that ALL possible functions will never work. For $(N,0,S,+,·)$ im thinking it might have something to do with S, the successor as maybe the relation will not be respected.

答:
For $\mathbb N$ note that an automorphism $f$ necessarily has $f(0)=0$. Furthermore, $f(S(0))=S(f(0))=1$. Similarly, $f(2)=S(f(1))=2$. You can then use induction to prove that $f(n)=n$ for all $n$.

Now let's consider $\mathbb Q$ and an automorphism $f$. Now, $f(1)=1$ so $f(2)=f(1)+f(1)=2$. Similarly to above, induction tells us that $f$ is the identity on $\mathbb N$. We claim now that $f(-n)=-n$ for any natural $n$. Indeed, $f(0)=0$ so $0=f(n+ (-n))=f(n)+f(-n)=n+f(-n)$. Thus, $f(-n)= -n$ so we have that $f$ is the identity on $\mathbb Z$. Now let's consider some rational number $a/b$. Then $f(a/b)b=f(a)=a$, as $a \in \mathbb Z$. Thus, $f(a/b) = a/b$ and $f$ is the identity.


问:
Find all complex numbers $z$ such that $|z| = 1$ and $\Im((z+1)^{2020}) = 0$
I've stumbled upon an interesting problem. The task is to find all complex numbers $z$ such that $$|z| = 1$$ and $$\Im((z+1)^{2020}) = 0$$
So far I found, that it's possible to follow these steps:
$$u = z+1$$
$$\Im(u^{2020}) = 0$$
$$\sin(2020x) = 0$$
$$x = \dfrac{\pi n}{2020}$$
Which basically gives me all complex numbers $u$ that follow $\Im(u^{2020}) = 0$. However, I don't know how to continue from this point.

答:
From $\Im((z+1)^{2020}) = 0$, it follows that
$$\operatorname{arg}(z+1) = \frac{2k\pi}{2020} $$
$z=-1$ is one solution. If not, from $|z| = 1$, it holds that
$$\operatorname{arg}(z+1) = \frac{1}{2} \operatorname{arg}(z)$$
Combining the two
$$\operatorname{arg}(z) = \frac{k\pi}{505}$$


问:
Drawing an arc between two points
I was writing a java program to draw an arc.
Arc2D.Double(int x,int y,int width,int height,int startAngle,int arcAngle,int type);

Since, I'm not familiar with the mathematics behind drawing arc, I'm facing the problem.
Basically, what I want to is...I want to draw an arc between two points A and B.
I want to draw an arc between the two lines depicting the angle between them.
Some body please help me in calculating the startAngle and arcAngle.

Please help me out.
Thanks in advance.

Well, I found the answer to my scenario here...

Since, I don't have enough reputation to answer I'm writing it here....

Lets say that the center of the circle is (x0, y0) and that the arc contains your two points (x1, y1) and (x2, y2). Then the radius is: r=sqrt((x1-x0)(x1-x0) + (y1-y0)(y1-y0)). So:

```
int r = (int)Math.sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));
int x = x0-r;
int y = y0-r;
int width = 2*r;
int height = 2*r;
int startAngle = (int) (180/Math.PI*atan2(y1-y0, x1-x0));
int endAngle = (int) (180/Math.PI*atan2(y2-y0, x2-x0));
graphics.drawArc(x, y, width, height, startAngle, endAngle);
```

Thanks & Regards

答:
Well, I can answer it now
I found the answer...here

Lets say that the center of the circle is (x0, y0) and that the arc contains your two points (x1, y1) and (x2, y2). Then the radius is: r=sqrt((x1-x0)(x1-x0) + (y1-y0)(y1-y0)). So:

```
int r = (int)Math.sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));
int x = x0-r;
int y = y0-r;
int width = 2*r;
int height = 2*r;
int startAngle = (int) (180/Math.PI*atan2(y1-y0, x1-x0));
int endAngle = (int) (180/Math.PI*atan2(y2-y0, x2-x0));
graphics.drawArc(x, y, width, height, startAngle, endAngle);
```

Title: Drawing an arc between two points

Body:
Well, I can answer it now
I found the answer...here

Lets say that the center of the circle is (x0, y0) and that the arc contains your two points (x1, y1) and (x2, y2). Then the radius is: r=sqrt((x1-x0)(x1-x0) + (y1-y0)(y1-y0)). So:

int r = (int)Math.sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));
int x = x0-r;
int y = y0-r;
int width = 2*r;
int height = 2*r;
int startAngle = (int) (180/Math.PI*atan2(y1-y0, x1-x0));
int endAngle = (int) (180/Math.PI*atan2(y2-y0, x2-x0));
graphics.drawArc(x, y, width, height, startAngle, endAngle);


答:
It's not just sine. The Weierstrass approximation theorem makes clear that every function in $C[0, 1]$ can be uniformly approximated by a sequence of polynomials, even something like $f(x) = |x - 0.5|$, a blancmange curve, Cantor's devil's staircase, or the Minkowski question mark function.

If we want to treat the sine function as a polynomial because it can be written as the uniform limit of a sequence of polynomials, all of those examples would have to be considered "polynomials" also, because they are also uniform limits of some sequence of polynomials. This broadens the definition of polynomial beyond even what I suspect OP would be willing to consider.

Functions like sine, that can be written as an "infinite polynomial" (i.e. are equal to their Taylor series at every point in the interval), are a special subset of $C[0, 1]$ called analytic functions. $A[0, 1]$, the set of analytic functions on $[0, 1]$, is much bigger than the set of polynomial functions $\Bbb{R}[x] \cap C[0, 1]$. For instance, while the set of all polynomials has a countable basis as an $\Bbb{R}$-vector space--the standard one--$A[0, 1]$ does not have such a countable basis, since $f_c(x) = 1/(x + c)$, $c > 0$, is an uncountable linearly independent subset of $A[0, 1]$.

Title: Why the set of polynomials is not closed in $C[0,1]$

Body:
This question starts from the following theorem: "Every finite dimensional subspace $Y$ of
a normed space $X$ is closed in $X$" (Kreyzig 2.4-3)

So the given counterexample for an infinite dimension subspace, is that if we take $X=C[0,1]$ and $Y = span\{x_0,x_1,x_2...\}$, where $x_j = t^j$, then $Y$ is not closed.

I guess this is the case because for example a sine function can be expressed as the limit point of a sequence of polynomials that converge uniformly (Taylor series). But why is the sine function not considered as a polynomial generated by an infinite basis? After all, we are explicitly saying $Y$ is infinite dimensional. For an infinite dimensional basis case, I would expect to have a mapping between every sequence to a polynomial in $C[0,1]$. If this is not the case, what exacly does it mean for $span\{x_0,x_1,x_2...\}$ to be considered infinite dimensional? If I input an infinite basis, it seems like it is not longer a polynomial.

I am confused.


问:
Show that the following is uniformly convergent
Show that if the function $f: R \to R$ is uniformly continuous, then the sequence $f_{n}(x) = f(x + \frac{1}{n})$ converges uniformly.

I know that f(x + 1/n) approaches f(x) as $n \to \infty$. I feel like I could say $Sup |f_n(x) - f(x)| = Sup|x - x| \ as \ n \to \infty$ = 0. Therefore, the function is uniformly convergent.

My instructor told me that using this version of the definition would not be the best idea though. He said using the $\forall \epsilon > 0 \exists N ...$ would be easier. Does anyone agree/disagree and see a way of doing this?

Thank you!

答: Let $\epsilon>0$. By uniform continuity, there exists $\delta>0$ such that $|f(x)-f(y)|<\epsilon$ whenever $|x-y|<\delta$. Pick $N$ such that $1/n<\delta$ for all $n\geq N$. Then...


问:
Average height in calculus
Calculate the average height above the x-axis of a point in the region $0\leq x\leq2$ and $0\leq y\leq x^2$. But I have no idea what average height is. I have googled it and find the formula $\bar H=\frac1{\text{Area}(D)}\int\int\limits_DydA$. Could anyone tell me why we have a $y$ in the given formula? How does it come from?

Title: Average height in calculus

Body: $$\bar{H} = \frac{\int\limits_{x=0}^2 \int\limits_{y=0}^{x^2}\ y\ dy\ dx}{\int\limits_{x=0}^2 x^2\ dx} = \frac{6}{5}$$


问:
Find the required sample size for the investigator.
An investigator interested in estimating a population mean wants to be 95% certain
that the length of the confidence interval does not exceed 4. Find the required
sample size for his study if the population standard deviation is 14.

My work:

Confidence interval: $95$%

Error estimate(E): $4$

$\sigma=14$

$\alpha=0.05$ so $\alpha/2=0.025$

$Z_{0.025}=1.96$

so using $n =(\cfrac{Z_{0.025} \cdot \sigma}{E})^2 = (\cfrac{1.96 \cdot 14}{4})^2 = 47.0596$

The sample size cannot be a decimal so round up to $48$ so $n = 48$

So he needs a sample size of $48$ but the book's answer says it's  $n = 189$

I have no idea how this is right. Please help me.

答: When the length of the confidence interval is 4, the value of E is 2.</p>


答:
For every point in a 2-dimensional figure, $y$ is the height of that point from the x-axis. Thus, when you want to add up heights of every point, you get $\int\int_D ydA$. You also want to divide by $Area(D)$, since you want the average height (and not the sum of heights).

Thus, the answer would be as follows: first, $Area(D) = \int_{0}^{2} \int_{0}^{x^2} dydx = \int_{0}^{2} x^2dx = \frac{8}{3}$. Then, we get that $\int_{0}^{2} \int_{0}^{x^2} ydydx = \int_{0}^{2}\frac{x^4}{2}dx = \frac{16}{5}$. Thus, the average height is $\frac{16*3}{5*8} = \frac{6}{5}$. Cross-check that this makes sense intuitively (i.e, that you would expect it to be more than $1$).

Title: Average height in calculus

Body: Calculate the average height above the x-axis of a point in the region $0\leq x\leq2$ and $0\leq y\leq x^2$. But I have no idea what average height is. I have googled it and find the formula $\bar H=\frac1{\text{Area}(D)}\int\int\limits_DydA$. Could anyone tell me why we have a $y$ in the given formula? How does it come from?


答:
I don't think the proof you wrote really makes sense. $Sup |x-x|$ should just be 0 but this doesn't seem to be what you mean.

Let $\varepsilon > 0$. By definition of uniform continuity, there is some $\delta > 0$ such that for all $x, y$ with $|x-y|<\delta$, $|f(x)-f(y)|<\varepsilon$. Take now some $M \in \mathbb N$ such that $1/N < \delta$. This exists by the Archimedean property. Take now any $n \geq N$. We have that $|f(x)-f_n(x)| = |f(x) - f(x+1/n)|$ for all $x$. As $|x+1/n - x| = 1/n \leq 1/N < \delta$, we conclude that for all $x$ and for all $n \geq N$, $|f(x) - f_n(x)| < \varepsilon$. That's precisely the definition of uniform convergence.

Title: Show that the following is uniformly convergent

Body:
Show that if the function $f: R \to R$ is uniformly continuous, then the sequence $f_{n}(x) = f(x + \frac{1}{n})$ converges uniformly.

I know that f(x + 1/n) approaches f(x) as $n \to \infty$. I feel like I could say $Sup |f_n(x) - f(x)| = Sup|x - x| \ as \ n \to \infty$ = 0. Therefore, the function is uniformly convergent.

My instructor told me that using this version of the definition would not be the best idea though. He said using the $\forall \epsilon > 0 \exists N ...$ would be easier. Does anyone agree/disagree and see a way of doing this?

Thank you!


答:
I immediately spotted one problem that you have. You have confused the notions of a polynomial and that of a polynomial function. Consequently your claim that $x^n=x$ for all positive integers $n$ is simply false.

A (univariate) polynomial over a field $F$ is simply a formal sum $\sum_{i=0}^na_ix^i$ with $i$ ranging over a finite set of non-negative integers, and $a_i$ are elements of $F$ for all $i$. Two polynomials $\sum_ia_ix^i$ and $\sum_ib_ix^i$ are the same polynomial, if (this is the definition!!) $a_i=b_i$ for all $i$. The set of polynomials over the field $F$ forms a ring $F[x]$ known as the ring of polynomials over $F$. This ring has many nice algebraic properties such as greatest common divisors and such.

A polynomial $p(x)\in F[x]$ gives rise to a polynomial function. This is a function $p$ from $F$ to itself gotten by evaluating $p$ at all the elements of $F$. In other words, $p:z\mapsto\sum_i a_i z^i$ for all $z\in F$. We sometimes do not make the distinction between polynomials and polynomial functions, but in the case of finite fields not making the distinction leads to problems.

So you have noticed that all the polynomials $p_n(x)=x^n$, with $n$ any positive integer, give rise to the same polynomial function $p_n$ from $\mathbb{Z}_2$ to itself. Your exercise, however, resides in the universe of polynomials - not in the universe of polynomial functions.

Polynomial functions from a field to itself also form a ring. But this ring is kind of ugly, in particular when $F$ is finite. For example, it has zero divisors and such.

Title: GgT, (polynomial) division and finite fields...

Body:
Exercise: Let $f,g \in \mathbb{Z}_2[x]$ be the polynomials $f = x^6 + x^5 + x^4 + 1$ and $g = x^5 + x^4 + x^3 + 1$. Has the diophantic equation $f u + g u = x^4 + 1$ solutions $u,v \in \mathbb{Z}[x]$? If so, determine them all.

My Solution: First I observed that in $\mathbb{Z}_2$ the relations
\begin{align}
  -x & = x \\
   x + x & = 0 \\
   x^n = x
\end{align}
hold. From this the polynomials $f,g$ reduce to $f = g = x + 1$, so they are the same and so $ggT(f,g) = x + 1$. Now $x^4 + 1 = x + 1$, so $u = 0, v = 1$ is a special solution. To get all solutions, I add solutions of the homogenous part $fu + gv = 0$, i.e. $fu = gv$ with my relations. But because $f = g$, this forces $u = v$, so I could choose for $u$ and $v$ some arbitrary polynomial. So all solutions $(u,v)$ are of the form
\begin{align}
  u & = p \\
  v & = 1 + p
\end{align}
for some polynomial $p \in \mathbb Z_2$.

Reference Solution: First it has to be checked if $x^4 + 1$ is a multiple of
the ggT of $f$ and $g$, then the equation has a solution (criterium for lineare diophantic equations). The euclidean algorithms yields the ggT. It is $f = (x+1)g + x^4 + x^3 + x^2 + x = (x+1)g + r_1$, $g = xr_1 + x^2 + 1$ and $r_1 = (x^2 + x)(x^2 + 1)$. So $ggT(f,g) = x^2 + 1$, and because of $(x^2+1)^2 = x^4 + 1$ the diophantic equation has a solution.

The general solution is given by the sum of a special solution and the general solution of the homogenous part $fu + gv = 0$. The special solution could be obtained by the euclidean algorithm (Lemma of Bezout). With $1 = -1$ we got
$$
  x^2 + 1 = g + xr_1 = g + x(f + (x+1)g)) = xf + (x^2 + x + 1)g.
$$
One special solution for the representation of the ggT is therefore $(x, x^2 + x + 1)$, one special solution of the original equation $(x(x^2+1), (x^2+x+1)(x^2+1)) = (x^3 + x, x^4 + x^3 + x + 1)$.

For the homogenous part $fu = gv$ we divide by the ggT. It is $f = (x^4+1)(x^2+1)$ and $g = (x^3+x^2+1)(x^2+1)$, a solution $(u,v)$ thus has the property $x^2+x^2+1 | u$ and $x^4+1 | v$. Therefore $u = p \cdot (x^3 + x^2 + 1)$. Substitution yields $v = p\cdot (x^4 + 1)$ and furthermore every $u = p\cdot (x^3 + x^2 + 1)$ and $v = p\cdot (x^4 + 1)$ are solutions. Therefore $\{ (p\cdot (x^3+x^2+1), p\cdot (x^4+1)) : p \in \mathbb Z_2[x]\}$ is the solution set of the homogenous part. The solution set is therefore
$$
 \{ (x^3 + x + p\cdot (x^3 + x^2 + 1), x^4 + x^3 + x + 1 + p\cdot (x^4+1)) : p \in \mathbb Z_2[x] \}.
$$

Now I understand the reference solution, it is the standard way of solving the problem. But my solution seems much simpler to mean, so I wonder why they didn't consider it, or maybe my solution is just wrong? But then why should it be wrong?


问:
Prove that the $\langle x,y\rangle$ is an inner product.
Let's consider the vector space $\mathbb{R}^2$ with $\langle x,y\rangle=2x_1y_1+x_2y_2$. Prove $\langle \cdot,\cdot \rangle$ is an inner dot product.

I know that these 4 properties have to be satisfied to prove it is an inner dot product:

$\langle x+z,y\rangle=\langle x,y\rangle+\langle z,y\rangle$

2.$\langle cx,y\rangle=c\langle x,y\rangle$

$\langle y,x\rangle=\overline{\langle x,y\rangle}$

If $x\neq 0$, then $\langle x,x\rangle$ is a positive real and $\langle 0,0\rangle=0$

I'm just not sure how to apply the definition to the actual problem.

答:
$\langle x+z,y \rangle = 2(x_1+z_1)y_1 + (x_2+z_2)y_2 = 2x_1y_1+x_2y_2 + 2z_1y_1 + z_2y_2 = \langle x,y\rangle + \langle z,y\rangle$

$\langle cx,y\rangle = 2cx_1y_1 + cx_2y_2 = c(2x_1y_1 + x_2y_2) = c\langle x,y\rangle$

This is trivially true because the norm is symmetric, and we are working on reals.

$\langle x,x\rangle = 2x_1^2+x_2^2$, which is $>0$ if and only if $x \neq (0,0)$.


问:
Simple Random Walk with equal probability of +1 and -1.
You have 1D random Walk, with +1 of probability 0.5, and -1 of probability 0.5.

What is the probability that you will reach +10 but never exceed -5?

Attempt:
The probability of getting +10 is easy, it is just 0.5^10. But I don't know how to factor in the -5 part.

答:
Hint:

Take a look at Gambler's ruin.

Body:
Hint:

Take a look at Gambler's ruin.


问:
Let I be a uncountable set and {$(X_i, \tau_{i} $): i $\in$ I} a family of topological spaces $T_1$ with at least two points
Let I be a uncountable  set and {$(X_i, \tau_{i} $): i $\in$ I} a family of  topological spaces $T_1$ with at least two points.Set f $ \in \prod_{i \in I} X_i $.Show that the subspace  S = { g $\in$ $\prod_{i \in I} X_i$ :( i $\in$ I: g (i) $\neq$ f (i)) is countable} from $ \prod_{i \in I} X_i $ is not separable.

====================================================================

What I thought.

To be separable $ \prod_ {i \in I} X_i $ needs to be countable and dense, we know that it is countable, so it cannot be dense. We also know that I is $ T_1 $ so there is z $ \in $ I and U $ \subset $ I, where z $ \in $ U such that z $ \notin $ S. So $ \prod_ {i \in I} X_i $ is not dense and therefore is not separable.

Thank you in advance for any assistance.

答:
There are several problems with your attempt. First, we’re not interested in whether $\prod_{i\in I}X_i$ is separable: we’re interested in the separability of its subspace $S$. And in any case separability of $\prod_{i\in I}X_i$ would not require $\prod_{i\in I}X_i$ to be countable, and neither $\prod_{i\in I}X_i$ nor $S$ is countable. Here is a correct argument:

Let $D=\{x_n:n\in\Bbb N\}$ be a countable subset of $S$. For each $n\in\Bbb N$ let $I_n=\{i\in I:x_n(i)\ne f(i)\}$; $x_n\in S$, so $I_n$ is countable. Let $J=\bigcup_{n\in\Bbb N}I_n$; $J$ is the union of countably many countable sets, so $J$ is countable, and therefore $I\setminus J$ is uncountable. In particular, $I\setminus J\ne\varnothing$, so we may pick an $i_0\in I\setminus J$. Let $u\in X_{i_0}\setminus\{f(i_0)\}$, and define $y\in S$ as follows:

$$y(i)=\begin{cases}
u,&\text{if }i=i_0\\
f(i),&\text{if }i\ne i_0\,.
\end{cases}$$

For $i\in I\setminus\{i_0\}$ let $U_i=X_i$, and let $U_{i_0}=X_{i_0}\setminus\{f(i_0)\}$; then $S\cap\prod_{i\in I}U_i$ is an open nbhd of $y$ in $S$ that is disjoint from $D$, so $D$ is not dense in $S$. $D$ was an arbitrary countable subset of $S$, so $S$ is not separable.


问:
$f_n \to f$ a.e. and $\lvert f_n(x) \rvert \le \lvert f(x) \rvert $ where $f_n, f \in L^\infty$
If we have $f_n \to f$ a.e. and $\lvert f_n(x) \rvert \le \lvert f(x) \rvert $ a.e. where $f_n, f \in L^\infty$

Does this give enough to ensure $\lvert \vert f_n - f \rvert \rvert_\infty \to 0 $?

This question provides a suitable counterexample if we omit the condition that $\lvert f_n(x) \rvert \le \lvert f(x) \rvert $ a.e.

In the above link $f_n \to 0$ a.e. but always a set of positive measure where the bounding fails. So I am trying to find a potential counterexample.

答: No. Define $f: (0,1] \to \mathbb R$ by $f(x) = \frac 1 x$ for $x \in (0,1]$, and let $f_n(x) = \min(n,f(x))$ for any $x \in (0,1]$. Then $\lvert f_n(x) \rvert \le \lvert f(x)\rvert$ for all $x$ and $f_n(x) \to f(x)$ for all $x \in(0,1]$, but $f_n \not \to f$ in $L^\infty$.


问:
Existence of dominating measure for weak*-compact set of measures
Let $(\Omega,\mathcal F)$ be a measurable space and $\mathcal P$ a weak*-compact set of the set of all probability measures $\mathcal M_1(\Omega)$. Does there always exist a probability measure $\mathbb Q\in\mathcal M_1(\Omega)$ such that every $\mathbb P\in\mathcal P$ is absolutely continuous to $\mathbb Q$, i.e. such that $\mathbb Q$ dominates all measures in $\mathcal P$?</p>

答: The question is now answered at Math Overflow.</p>