问:
Checking if the complement of an undirected graph is bipartite
Is there any linear time algorithm that says if the complement of a given undirected graph is bipartite?

I've tried using König's theorem, with no success.

答:
Let us start by formalizing the problem first. In the following we assume that all graphs are simple, finite and undirected.

Def. 1: A graph $G=(V,E)$ is bipartite if $V$ can be partitioned into two subsets $X$ and $Y$  so that every edge has one end in $X$ and one end in $Y$; such a partition $(X,Y)$ is called a bipartition of the graph, and $X$ and $Y$ its parts.

Def. 2: Let $G$ be a graph. The complement $\overline{G}$ of $G$ is the simple graph whose vertex set is $V$ and whose edges are the pairs of nonadjacent vertices of $G$.

Building the complement $\overline{G}$ of a graph $G$ is quite simple and can be done efficiently using the adjacency matrix of $G$.

We denote the matrix of ones, that is a matrix where every element is equal to $1$, by $J$. We denote the identity matrix, that is a matrix where the elements on its main diagonal are ones and all other elements are zero, by $I$.

We denote the complete graph on $n$ vertices by $K_n$. Let $A_{K_n}$ be its adjacency matrix.

Lemma 1: Let $A$ be the adjacency matrix of a graph $G$ on $n$ vertices. Then the adjacency matrix of $\overline{G}$ is given by $\overline{A}=J - I -A$.

Proof: Observe that $(v_i, v_j) \in E(G) \iff (v_i,v_j) \notin E(\overline{G})$, hence $A + \overline{A}=A_{K_n}$. Clearly, $A_{K_n}=J - I$, hence $A + \overline{A}= J -I$, therefore $\overline{A}=J-I-A$.

Doing matrix substraction with $m$ rows and $n$ columns has a runtime complexity of $O(n\cdot m)$.

Now, we have constructed the complement graph. Let us define our main problem instance.

Problem Instance: A graph $G=(V,E)$.

Question: Is $G$ bipartite?

For simplicity, we assume that our graph is connected. We are using breadth-first search for solving our problem instance. It is described here.

Checkout this nice visualisation including pseudocode of the BFS on GitHub.

We also need the following:

Lemma 2: A graph is bipartite if and only if it has no odd cycles.

Proof: Check here.

It follows that a graph containing an odd cycle is not $2$-colourable (which is essentially the same as saying the graph is not bipartite).

Now, consider the following algorithm:

```<code>INPUT: A graph G.
OUTPUT: True, if G is bipartite, False otherwise.

queue := empty queue
v_0 := Pick arbitrary v_0 from V(G)
colour v_0 green
enqueue v_0 in queue
do while queue not empty
   v_x = dequeue from queue
   for each v_y in neighbors of v_x do
     if v_y has no colour assignment:
       if colour of v_x == green:
           colour v_y red
       else
           colour v_y green
       queue.enqueue(v_y)
     else colour of v_y == colour of v_x:
       return False
return True
</code>```

Notice how each neighbour $v_y$ of any vertex $v_x$ is coloured with the same colour. If we encounter a vertex $v_y$ which already has a colour (meaning that we have visited it before) and it has the same colour as $v_x$, we have found an odd-cycle, hence $G$ is not bipartite. In the language of BFS we often speak of "search level" instead of colour.

The algorithm on a graph with $m$ edges and $n$ vertices has a runtime complexity of $O(n+m)$. Notice that this is the runtime complexity when using an adjacency list. Using an adjacency matrix, the runtime complexity is $O(n^2)$. Since we have only used an adjacency matrix in this answer, let us convert it to an adjacency list:

Denote $N(v)$ as the set of neighbours of a vertex $v$ of a graph $G$.

```<code>INPUT: Adjacency matrix A of a graph G.
OUTPUT: Adjacency list of G=(V,E).
    map := empty map
    for each v in V:
        L_v := initialize empty list of size |N(v)|
        put L_v in map with key v
    for each v_i in V:
        for each v_j in V:
            if A[v_i][v_j] == 1:
                add v_i to map.get(v_j)
</code>```

MISC

If the input graph $G$ is not connected, then we need to run our algorithm for each component of $G$. Furthermore, notice that the complement of a bipartite graph does not have to be bipartite. Also, it is well know that the complement of a bipartite graph is a perfect graph, hence its clique number must be equal to its chromatic number.

Body:
Let us start by formalizing the problem first. In the following we assume that all graphs are simple, finite and undirected.

Def. 1: A graph $G=(V,E)$ is bipartite if $V$ can be partitioned into two subsets $X$ and $Y$  so that every edge has one end in $X$ and one end in $Y$; such a partition $(X,Y)$ is called a bipartition of the graph, and $X$ and $Y$ its parts.

Def. 2: Let $G$ be a graph. The complement $\overline{G}$ of $G$ is the simple graph whose vertex set is $V$ and whose edges are the pairs of nonadjacent vertices of $G$.

Building the complement $\overline{G}$ of a graph $G$ is quite simple and can be done efficiently using the adjacency matrix of $G$.

We denote the matrix of ones, that is a matrix where every element is equal to $1$, by $J$. We denote the identity matrix, that is a matrix where the elements on its main diagonal are ones and all other elements are zero, by $I$.

We denote the complete graph on $n$ vertices by $K_n$. Let $A_{K_n}$ be its adjacency matrix.

Lemma 1: Let $A$ be the adjacency matrix of a graph $G$ on $n$ vertices. Then the adjacency matrix of $\overline{G}$ is given by $\overline{A}=J - I -A$.

Proof: Observe that $(v_i, v_j) \in E(G) \iff (v_i,v_j) \notin E(\overline{G})$, hence $A + \overline{A}=A_{K_n}$. Clearly, $A_{K_n}=J - I$, hence $A + \overline{A}= J -I$, therefore $\overline{A}=J-I-A$.

Doing matrix substraction with $m$ rows and $n$ columns has a runtime complexity of $O(n\cdot m)$.

Now, we have constructed the complement graph. Let us define our main problem instance.

Problem Instance: A graph $G=(V,E)$.

Question: Is $G$ bipartite?

For simplicity, we assume that our graph is connected. We are using breadth-first search for solving our problem instance. It is described here.

Checkout this nice visualisation including pseudocode of the BFS on GitHub.

We also need the following:

Lemma 2: A graph is bipartite if and only if it has no odd cycles.

Proof: Check here.

It follows that a graph containing an odd cycle is not $2$-colourable (which is essentially the same as saying the graph is not bipartite).

Now, consider the following algorithm:

INPUT: A graph G.
OUTPUT: True, if G is bipartite, False otherwise.

queue := empty queue
v_0 := Pick arbitrary v_0 from V(G)
colour v_0 green
enqueue v_0 in queue
do while queue not empty
   v_x = dequeue from queue
   for each v_y in neighbors of v_x do
     if v_y has no colour assignment:
       if colour of v_x == green:
           colour v_y red
       else
           colour v_y green
       queue.enqueue(v_y)
     else colour of v_y == colour of v_x:
       return False
return True

Notice how each neighbour $v_y$ of any vertex $v_x$ is coloured with the same colour. If we encounter a vertex $v_y$ which already has a colour (meaning that we have visited it before) and it has the same colour as $v_x$, we have found an odd-cycle, hence $G$ is not bipartite. In the language of BFS we often speak of "search level" instead of colour.

The algorithm on a graph with $m$ edges and $n$ vertices has a runtime complexity of $O(n+m)$. Notice that this is the runtime complexity when using an adjacency list. Using an adjacency matrix, the runtime complexity is $O(n^2)$. Since we have only used an adjacency matrix in this answer, let us convert it to an adjacency list:

Denote $N(v)$ as the set of neighbours of a vertex $v$ of a graph $G$.

INPUT: Adjacency matrix A of a graph G.
OUTPUT: Adjacency list of G=(V,E).
    map := empty map
    for each v in V:
        L_v := initialize empty list of size |N(v)|
        put L_v in map with key v
    for each v_i in V:
        for each v_j in V:
            if A[v_i][v_j] == 1:
                add v_i to map.get(v_j)

MISC

If the input graph $G$ is not connected, then we need to run our algorithm for each component of $G$. Furthermore, notice that the complement of a bipartite graph does not have to be bipartite. Also, it is well know that the complement of a bipartite graph is a perfect graph, hence its clique number must be equal to its chromatic number.


问:
How many 6 character passwords are possible if letters cannot be repeated but digits CAN be?
A computer system uses passwords that have six characters, and each character is
one of the 26 letters (a-z) or 10 integers (0-9). The first character has to be a letter.
The passwords are not case sensitive. How many contain no repeated letters but can contain repeated integers?

I could do this question easily if neither letters nor integers could be repeated but having one allow repetition and the other not has thrown me off.
Any help would be greatly appreciated.
Thanks

答:
Edited to Joffan's input

How I would guess to approach this, I am also pretty new to combinatorics.

For the first space you have 26 options since there is NOT case sensitive.

(26 option)(..)(..)(..)(..)(..)

Now for the remaining five slots you would have six possible cases.

$$ \begin{array}{|c|c|} \hline
\text{# Letters (after first)} & 5 & 4 & 3 & 2 & 1 & 0 \\ \hline
\text{# Numbers} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline
\end{array}$$

There is another layer to think about say in the case of three letter and two numbers, you know have five slots and three slots to place letters so you have ${5 \choose 3}$ ways of picking positions for letters and for each of the positions you would have 25 options for the first slots since one letter is taken for the fist slot, 24 options for the second and 23 options for the third slots, as for the last two number slots you would have $10\cdot 10$ options.

I would then take a guess that the final number would be

$26 \cdot \left({5 \choose 5}
\cdot \frac{25!}{(25-5)!} \cdot 10^0 + {5 \choose 4}
\cdot\frac{25!}{(25-4)!} \cdot 10^1 + {5 \choose 3}
\cdot\frac{25!}{(25-3)!} \cdot 10^2 +{5 \choose 2}
\cdot\frac{25!}{(25-2)!} \cdot 10^3 +{5 \choose 1}
\cdot\frac{25!}{(25-1)!} \cdot 10^4 +{5 \choose 0}
\cdot\frac{25!}{(25)!} \cdot 10^5\right)$

or rather

$26 \cdot \sum_{k=0}^{5}\left({{5 \choose k}
\cdot\frac{25!}{(25-k)!}} \cdot 10^{5-k}\right)$.

And as a final summary since the multiplicative factor of 26 distributes to all summands we end up with

$$\sum_{k=0}^{5}\left({{5 \choose k}
\cdot\frac{26!}{(25-k)!}} \cdot 10^{5-k}\right)$$

This is my first time posting so I know my answer is poorly formatted, I cannot fully verify my answer but this is what I would turn in if I had to give it an attempt. I would love to get some feedback on this as I recently started self learning combinatorics.

ContentLicense: CC BY-SA 4.0


问:
Tensor contraction via universal property of the tensor product
I'm having a little trouble with the definition of the contraction operation for tensors via the universal property of the tensor product. The construction I've found (for instance, suggested here and outlined here) goes as follows: suppose we have a commutative ring $R$ (for example, the smooth real valued functions on a manifold) and an $R$-module $E$ which is finitely generated and projective (for example, the module of smooth sections of the tangent bundle of a smooth manifold), with dual $E^{*}$. Consider the tensor product

$$
\bigotimes_{i=1}^{r}E \otimes \bigotimes_{i=1}^{s}E^{*}
$$

and call $\otimes^r_s$ the corresponding canonical multilinear mapping between the cartesian product to the tensor product. To define the contraction $C^\ell_{k}$ between the $\ell$-th $E$ factor and the $k$-th $E^{*}$ factor, one defines the (suppossedly) multilinear mapping:

$$
f:\prod_{i=1}^{r}E \times \prod_{i=1}^{s}E^{*}\longrightarrow \prod_{i=1}^{r-1}E \times \prod_{i=1}^{s-1}E^{*}
$$

$$
f:(U_1,\ldots,U_r,\omega^1,\ldots,\omega^s)\mapsto \omega^k(U_\ell)(U_1,\ldots,\widehat{U_\ell},\ldots,U_r,\omega_1,\ldots,\widehat{\omega^k},\ldots,\omega_s)
$$

where hats mean ommitted arguments, and where (I presume) the product spaces are understood to be $R$-modules through the usual construction as direct sums/products. Then by the universal property of the tensor product, there exists a unique module homomorphism

$$
h:\bigotimes_{i=1}^{r}E \otimes \bigotimes_{i=1}^{s}E^{*}\longrightarrow \prod_{i=1}^{r-1}E \times \prod_{i=1}^{s-1}E^{*}
$$

such that $f = h\circ\otimes^r_s$; then the contraction would suppossedly be defined as $C^\ell_k:= \otimes^{r-1}_{s-1}\circ h$, and the universal property should yield:

$$
C^\ell_k(U_1\otimes\cdots\otimes U_r\otimes\omega^1\otimes\cdots\otimes\omega^s) = \omega^k(U_\ell)U_1\otimes\cdots,\otimes\widehat{U_\ell}\otimes\cdots\otimes U_r\otimes\omega_1\otimes\cdots\otimes\widehat{\omega^k}\otimes\cdots\otimes\omega_s
$$

I just can't get this to work. My questions/problems are:

How exactly is $f$ suppossed to be multilinear? If addition and multiplication by elements of $R$ on $\prod_{i=1}^{r-1}E \times \prod_{i=1}^{s-1}E^{*}$ are defined component-wise, then it seems that $f$ would only be multilinear in the two arguments that are being contracted.

Even if we admit that $h$ exists and is unique, if we understand that multiplication by elements of $R$ acts componentwise, then we should have:

$$
\otimes^{r-1}_{s-1}\left(\omega^k(U_\ell)(U_1,\ldots,\widehat{U_\ell},\ldots,U_r,\omega_1,\ldots,\widehat{\omega^k},\ldots,\omega_s)\right) = \omega^k(U_\ell)^{(r-1)(s-1)}U_1\otimes\cdots,\otimes\widehat{U_\ell}\otimes\cdots\otimes U_r\otimes\omega_1\otimes\cdots\otimes\widehat{\omega^k}\otimes\cdots\otimes\omega_s
$$

since the factor $\omega^k(U_\ell)$ multiplies all the components and thus appears $(r-1)(s-1)$ times in the tensor product.

What am I missing here?

答:
Your $f$ should go directly to the tensor product space.

How do you multiply an element of the direct product by a scalar (element of $R$)? Well, we can do that: multiply each coordinate - that's how your question 2. possibly arose, but that's not what we want here: the scalar $\omega^k(U_\ell)$ is meant to be a single factor of the single tensor
$$U_1\otimes\cdots\otimes \widehat{U_\ell}\otimes\cdots\otimes U_r\,\otimes\,\omega_1\otimes\cdots \otimes\widehat{\omega_k}\otimes \cdots\otimes \omega_s\,.$$
As you observed, the part $\omega^k(U_\ell)$ is $R$-linear in both variables, and using this tensor, you can prove $R$-linearity of the other variables as well.


问:
Does Hilbert's Nullstellensatz have something to do with the universal property of polynomial rings?
One basic slogan of category theory is that a mathematical concept is uniquely defined by a universal property. For example, polynomial rings are uniquely characterized by their universal property.

Does this mean that every statement about polynomials can be deduced from this universal property? For example, consider the following statement about polynomials, the so-called Hilbert's Nullstellensatz (formulation copied from The Princeton Companion to Mathematics):

Nullstellensatz. The polynomials $f_1,...,f_m$ have no common complex zero if and only if there are polynomials $g_1,...,g_m$ such that $g_1f_1 +···+ g_mf_m = 1$.

Does this statement have something to do with the universal property of polynomial rings? Or should one distinguish between properties of polynomial rings (these should be derivable from the universal property) and concrete statements about polynomials such as Hilbert's Nullstellensatz?

答:
The problem, as KReiser says in the comments, is that the universal property of polynomial rings requires no hypotheses on the base $k$, whereas in the Nullstellensatz $k$ is traditionally an algebraically closed field (in the form you've stated it) and more generally can be a Jacobson ring (in a different form which turns out to be equivalent when specialized to an algebraically closed field). The proof must make use of this extra hypothesis somehow, which is extra "non-categorical input" specific to the situation.

One basic slogan of category theory is that a mathematical concept is uniquely defined by a universal property.

As much as I love category theory, this is much too strong of a slogan. Many interesting mathematical concepts have nothing to do with universal properties.

Generally speaking, at the most basic level, knowing the universal property of an object tells you what either maps into or out of that object look like, depending on the universal property. In principle this completely determines the object but it may not be the best way to prove facts about it, depending on how easily those facts can be stated in terms of maps in or out. Again at the most basic level, if you know a maps-in universal property then that doesn't necessarily help you figure out what maps out look like, and vice versa.

Let me switch to the simpler example of groups so I can be explicit here. The free groups $F_n$ have a maps-out universal property, which is useful for proving various facts involving maps out. For example the maps-out universal property directly implies that $\text{Hom}(F_n, \mathbb{Q}) \cong \mathbb{Q}^n$, which implies that the free groups are not isomorphic for different values of $n$. It also implies that the abelianization is $\mathbb{Z}^n$ and so forth.

Consider, by contrast, statements like "$F_n$ is torsion-free" or "every subgroup of $F_n$ is free." These are statements about maps in, not maps out, and the universal property is less helpful here. In fact a "fully universal" proof is impossible because analogues of these statements are false in other categories of algebraic structures (e.g. subrings of polynomial rings are not polynomial). So at some point one must make use of some "non-categorical input" specific to this situation.

The Nullstellensatz itself is equivalent to the statement that a polynomial ring over a field (or more generally a Jacobson ring) is Jacobson, meaning that every prime ideal is an intersection of maximal ideals. This is in principle a maps-out statement, although a somewhat complicated one, and the polynomial ring has a maps-out universal property, but I'm not aware of a way of proving it in which the universal property really helps at all.


问:
How do I complete the equation?
Can someone help me with this equation.

Solve the following logarithmic equation:
$$\log_5 (2x+4)=2$$

this is all I have got. How can I solve this?

答:
You just need to do the following trick: if $a=b$ then $5^a=5^b$, and conversely, if $5^a=5^b$ then $a=b$.

Doing the same with your equation, we got:

$$
5^{\log_5 (2x+4)}=5^2
$$

and, as was mentioned above, this equation has the same set of roots since the function $y=5^x$ is continuous and monotonic over $\mathbb{R}$. Hope you can take it from here.

HINT: $a^{\log_a b}=b$

Title: How do I complete the equation?


问:
Least residue power modulo
May someone confirm that the least residue of $44^8$ modulo $7$ is $4$ please?

And that $2^2 \equiv  4\, (\!\!\!\mod 7)$?

Thanks in advance.

Title: Least residue power modulo

Body: It is correct: $44\equiv 2\mod 7$, so  $44^8\equiv 2^8\mod 7$. Now $2^3\equiv 1\mod 7$, so $2^8\equiv 2^{8\bmod 3}=2^2\mod 7=4$, since $0\le 4<7$.


问:
Relationship between Dirichlet character and Legrendre symbol
I'm wondering whether you always can express a non trivial Dirichlet character by a Legendre symbol. And in case so, how would one explicitly do that? Or how does one connect the two things?</p>

答:
Only $\pm 1$ valued Dirichlet characters are products of Legendre symbols $(n/p)$  (well almost all of them as there is a problem for the 3 quadratic characters $\bmod 8$)

If $\chi$ is a $\pm 1$ valued character of least period $2N+1$ then it is a product of $\pm 1$ valued characters of period $p^k \| 2N+1$ and each of them is either the trivial character $1_{p\ \nmid\ n}=(n/p)^2$ or the Legendre symbol $(n/p)$.

Then look at $$\chi(5n)=0,\chi(5n+1)=1,\chi(5n+2)=i,\chi(5n+3)=-i,\chi(5n+4)=-1$$


问:
The average weight of $46$ weightlifters is $106$ kg; how many can weigh $125$ kg if none may drop below $82$ kg?
The average weight of $46$ weightlifters is $106$ kg. If none of the lifters weighs less than $82$ kg, at most how many of them can weigh more than $125$ kg?

We are given that $$\overline{X}=\dfrac{x_1+x_2+x_3+\ldots+x_{46}}{46}=106.$$ From here we can conclude $$x_1+x_2+x_3+\ldots+x_{46}=106\times46=4876 \text{ kg }$$ So the total weight of the weightlifters is $4876$ kg. We also know that $x_n\ge82$ kg for every $n$. I don't know what to do next. Thank you in advance!

答:
Let divide the $n=46$ lifters into $h$ "heavy" lifters (weight more than 125) and $t=n-h$ "thin" lifters. Then the respective averages (denoted by $X$, $X_h$, $X_t$) are related by

$$ 106 = X = \frac{h}{n} X_h + \frac{t}{n} X_t =\frac{h}{n}(X_h - X_t) + X_t $$

Obviously $$ X_h > 125, $$
$$ 82 \le X_t \le 106 $$

and

$$ \frac{h}{n} = \frac{106 - X_t}{X_h - X_t} <  \frac{106 - X_t}{125 - X_t} $$

The above is  decreasing in $X_t \in [82,106]$, hence its maximum occurs at $X_t= 82$, so

$$ \frac{h}{46} < \frac{106-82}{125-46} \implies h < 25.674$$

and the maximum number of heavy lifters is $25$.


问:
Limit of $(1-c^n)^{bn}$ when $n\to\infty$, for $c \in (0,1)$ and b is positive constant (arbitrary large).
Limit of $(1-c^n)^{bn}$ when $n\to\infty$. For $c \in (0,1)$ and b is positive constant (arbitrary large).

The inner part grows to 1 exponentially. The outer part, however, decreases the whole value exponentially.

I tried some Matlab simulations, they all converge to 1.
I wonder how to justify the result through mathematical proof.

In addition, is it possible to characterize the convergence speed? Linear (exponential), sublinear, etc.?

答:
I will show that $\lim\limits_{n \to \infty} \log((1-c^n)^{bn})=0$ , the conclusion follows easily.

$$\log((1-c^n)^{bn}) = bn \log(1-c^n) = bn(-c^n) \cdot \frac{\log(1-c^n)}{-c^n} \stackrel{n \to \infty}\to 0\cdot 1 = 0$$


问:
Finding the functions verifying that for all $x$, we get $g \circ \dots \circ g(x)=x$ where the number of composition depends on $x$.
Let $g:[0,1]\to[0,1]$ a continuous function verifying $g(0)=0$ and for every $x$ in $[0,1]$, there exists a non zero positive integer $n=n(x)$ such that $g^n(x)=x$ where $g^n$ is $g \circ \dots \circ g$ ($g$ appears $n$ times, $g^0=Id$).

I'm asked to show that $g$ in injective and surjective, then deduce that $g$ is the identity.

For the surjection, I think it's easy for all $y$ in $[0,1]$, there exists $n$ such that $g^n(y)=y$ so $g(g^{n-1}(y))=y$.

I'm having trouble showing that it's injective. If I take $x,y$ such that $g(x)=g(y)$. There will exist $n,m$ such that $g^n(x)=x$ and $g^m(y)=y$. By symmetry, we can suppose $n>m$ (if $n=m$, we get directly $x=y$), and by Euclidian division, we have $(q,r)$ such that $n=mq+r$ where $0\leq r<m$, and so :  $g^r(y)=x$. This is what I've thought of so far, to finish the proof, I'll have to show that $r=0$, or that $n$ divides $m$. (Maybe I need to use the continuity and that $g(0)=0$ since I haven't used them thus far).

Any help/hints for the injection part or deduction part will be appreciated.

答:
Note that if $g^n(x)=x$ for some positive integer $n$, then $g^{nk}(x)=x$ for all positive integers $k$. Indeed, it is clear for $k=1$, and if $k^{nk}(x)=x$, we have that
$$
g^{n(k+1)}(x)=g^{n}(g^{nk}(x)) = g^n(x) = x.
$$

Now, given that $g^n(x)=x$, $g^{m}(y)=y$ and that $g(x)=g(y)$, then we have that $g^k(x)=g^k(y)$ for every positive integer $k$, in particular, taking $k=nm$, we have by the previous part that $g^{nm}(x)=x$ and $g^{nm}(y)=y$, and
$$
x = g^{nm}(x) = g^{nm}(y) = y,
$$
which proves the injectivity of $g$.

Now, note that $g(1)=1$ because if $g(a)=1$, for some $0<a<1$ then $g(1)<1$ as $g$ is bijective and as $g$ is continuous and $g(0)=0$, there exists $c\in (0,a)$ and $d\in (a,1)$ such that
$$
g(c) = \frac{g(1)+1}{2} \quad \text{and} \quad g(d) = \frac{g(1)+1}{2}
$$
(just apply the intermediate value theorem). This contradicts the injectivity of $g$. Thus $g(1)=1$.

This shows that $g$ must be strictly increasing (Exercise! You will need again the continuity of $g$). Thus, if $g(x)\neq x$ for some $x$, assume, for example, that $g(x)>x$ (the case $g(x)<x$ is analogous), and let $n$ be such that $g^n(x)=x$. Then $g^2(x)=g(g(x))>g(x)>x$, and inductively we see that
$$
g^n(x) > g^{n-1}(x) > \cdots > g(x)>x,
$$
which is absurd as $g^n(x)=x$.

Thus $g(x)=x$ for all $x$, that is, $g$ is the identity map.


问:
All of the dihedral groups are factor groups of the infinite dihedral group.

Show that $\operatorname{Aut}(\Bbb{Z}) \cong \{\pm 1 \}$ and write $\alpha : \mathbb Z_2 \rightarrow \operatorname{Aut}(\Bbb{Z})$ for the nontrivial homomorphism. The semidirect product $\Bbb{Z} \rtimes_{\alpha} \Bbb{Z_2}$ is called the infinite dihedral group. Show that the dihedral groups $D_{2n}$ are all factor groups of the infinite dihedral group.

We know that $\Bbb{Z}$ only has two generators, $1$ and $-1$. So there are only two possibilities: sending $1$ to $1$ and sending $1$ to $-1$. So $\operatorname{Aut}(\Bbb{Z}) \cong \{\pm 1\}$. There is an example in our textbook that shows that $\Bbb{Z}_n \rtimes_{\alpha} \Bbb{Z}_2 \cong D_{2n}$. So I only need to show that $$(\Bbb{Z} \rtimes_{\alpha} \Bbb{Z}_2)/\langle n \rangle \cong \Bbb{Z}_n \rtimes_{\alpha} \Bbb{Z}_2$$ right?

Suppose that $\Bbb{Z} = \langle b \rangle$ and $\Bbb{Z}_2 = \langle a \rangle$. We can see that $(\Bbb{Z} \rtimes_{\alpha} \Bbb{Z_2})/\langle n \rangle = \{b^ia^j \text{mod n} : b^i \in \Bbb{Z}, a^j \in \Bbb{Z}_2\} = \{b^ia^j : b^i \in \Bbb{Z}_n, a^j \in \Bbb{Z}_2\} = \Bbb{Z}_n \rtimes_{\alpha} \Bbb{Z_2}$.

Is my answer correct? I'm just curious because it seems too short.

Thank you in advance

答:
The way to show this, is to note that any of the dihedral groups have a cyclic condition.  When this condition is removed, the elements are infinite.

In essence, the cyclic groups can be written with a $mod(Z)$ condition, while the infinite group is just $z$.  Thus, every cyclic group becomes the infinite group with a cyclic remainder.

ContentLicense: CC BY-SA 3.0


问:
Fundamental Theorem of Linear Algebra proof
I was hoping someone could help me with the following proof question:

"Prove that if $A$ and $B$ are two matrices with $m$ rows, and $N(A^T) \subset N(B^T)$, then $R(B) \subset R(A)$.
Hint: Use the fact that for any matrix $M$ with $m$ rows, we have dim $R(M) +$ dim $N(M^T) = m$

答:
Lemma #1: Suppose $W_1,W_2$ are subspaces of an inner product space $V$ such that $W_1 \subseteq W_2$. Then we have that $W_2^{\perp}\subseteq W_1^{\perp}$.

Proof of Lemma #1: Choose $v\in W_2^{\perp}$ and $w_1\in W_1$ arbitrarily. Since $W_1\subseteq W_2$ we have $w_1\in W_2$ and so $v\cdot w_1=0$. But this means $v\in W_1^{\perp}$ since $w_1\in W_1$ was chosen arbitrarily and containment follows.

Lemma #2: Suppose $U$ is a subspace of an inner product space $V$. Then $\Big(U^{\perp}\Big)^{\perp}=U$

Proof of Lemma #2: Choose $v\in \Big(U^{\perp}\Big)^{\perp}$ arbitrarily and write $v=v_{||}+v_{\perp}$ where $v_{||}=\text{Proj}_{U}(v)\in U$ and $v_{\perp}=v-v_{||}\in U^{\perp}$. Since $v$ is orthogonal to any element of $U^{\perp}$ we have that $$0=v\cdot v_{\perp}=(v_{||}+v_{\perp})\cdot v_{\perp}=v_{||}\cdot v_{\perp}+||v_{\perp}||^2=||v_{\perp}||^2$$ This implies $v_{\perp}=0$ and so $v=v_{||}\in U$ which shows $\Big(U^{\perp}\Big)^{\perp}\subseteq U$. On the other hand, if $u\in U$ is arbitrary, then by definition of $U^{\perp}$ we have that $u \cdot v=0$ for any $v\in U^{\perp}$ meaning $u\in \Big(U^{\perp}\Big)^{\perp}$ and the result follows.

To prove your result let's use the fact that $N(M^T)=R(M)^{\perp}$ for any matrix $M$. We get $$N(A^T)\subseteq N(B^T) \iff R(A)^{\perp} \subseteq R(B)^{\perp} \implies \Big(R(B)^{\perp}\Big)^{\perp} \subseteq \Big(R(A)^{\perp}\Big)^{\perp} \iff R(B)\subseteq R(A)$$


问:
In a general field, is it always true that if x * x = 1 then x = 1 or x = (-1)?
So in an arbitrary field where we call the multiplicative identity "1":

1 * 1 = 1 by definition, and (-1) * (-1) = 1 because you can prove that double negatives cancel, but can any other square roots of 1 exist?

It feels to me like they probably can't, but I'm having a hard time actually proving why that has to be true.  This is equivalent to the question of whether the equation

x = reciprocal (x)

has any solutions besides 1 and (-1), but that also feels like it doesn't without being able to see an obvious proof.

答: Yes. If $x^2 = 1$, then $x^2 - 1 = 0$, so $(x + 1)(x - 1) = 0$. Because fields are integral domains, either $x + 1 = 0$ or $x - 1 = 0$, and the question is solved as you claim. This is a specific instance of lulu's comment that fields can have at most $d$ solutions to a polynomial of degree $d$.


问:
Conditional Expectation for the Exponential Distribution -- solution verification

A device that continuously measures and records seismic activity is placed in a remote region. The time, $T,$ to failure of this device is exponentially distributed with mean $3$ years. Since the device will not be monitored during its first two years of service, the time to discovery of its failure is $X = \max(T, 2)$. Determine $E(X)$.

My attempt:

$$E[X] = E[X\mid T\ge 2] \cdot P(T \ge 2) + E[X\mid T< 2] \cdot P(T< 2)$$
$$= E[T\mid T\ge 2] \cdot P(T \ge 2) + E[2\mid T< 2] \cdot P(T< 2) $$
Using the memoryless property of the Exponential distribution, we have:

$$ = E(T) \cdot P(T\ge 2) + E(2) \cdot P(T<2)$$
$$ = 3[1-P(T<2)] + 2\cdot P(T<2)$$

(Edited based on commments)

Now, $P(T<2)=\int_0^2 \frac{1}{3} e^{-t/3} \; dt = 1- e^{-2/3}$. These calculations do not lead to the correct answer. Can someone please point out what I did incorrectly?

As pointed out in the answer by Michael Hardy, for the benefit of anyone who visits this post in the future, this is how the solution should go:

$$E[T\mid T\ge 2] \cdot P(T \ge 2) + E[2\mid T< 2] \cdot P(T< 2) = \int_2^\infty \frac{t}{3} e^{-t/3}\; \text{d}t + 2 \cdot [1- e^{-2/3}]$$

$$= 5e^{-2/3} + 2 - 2e^{-2/3} = \boxed{3e^{-2/3} +2}$$

答:
You're making a commonplace mistake:
\begin{align}
\require{cancel}
\text{wrong:} & \xcancel{\operatorname E(T\mid T>2) = \operatorname E(T)} \\[10pt]
\text{right: } & \operatorname E( T-2\mid T>2) = \operatorname E(T)
\end{align}


问:
Finding a subspace that is a deformation retract to a given space
$X=T^2\# T^2$,
$Y=$ an open disk removed from $T^2\# T^2$.

I want to find a subspace of $Y$ that is a deformation retract to $Y$ but not deformation retract to $X$.

The fundamental group of $Y$ is wedge of four circles? Can I use this fact to solve the problem? Or what different approach can I take?

答:
From the fundamental polygon for $T^2 \# T^2$, you can see that if you remove an open disk you can deformation retract to the edges of the polygon, which gives you a wedge of $4$ circles. Thus $Y \simeq S^1 \vee S^1 \vee S^1 \vee S^1$.

You can see that this is not a deformation retract of $X$ via fundamental groups: $\pi_1(S^1 \vee S^1 \vee S^1 \vee S^1)$ is the free group on $4$ generators, but $\pi_1(X)$ is not, so $X$ and the wedge of four circles are not homotopy equivalent and hence the wedge of four circles cannot be a deformation retract of $X$.

(Also, this is nitpicky and not very important here, but be careful with your wording: we say that one space is a deformation retract "of" another, or that one space deformation retracts "to" another, but we don't say that one space is a deformation retract to another space. Also, the fundamental group of $Y$ is the free group on 4 generators because it's the fundamental group of a wedge of four circles, but we don't say that "the fundamental group of $Y$ is a wedge of four circles.")


问:
Is the following set non-empty?
I proofed that following set in the image is closed , we know if {Cn} be a bounded sequence in R it should have converged subsequence with all that said can we say that the set in the image is non-empty? HERE

sorry that I posted the set as an image ,I could not paste it correctly , I appreciate if someone tell me how I can type math symbols easily here

答: Yes, as $\{ C_n \}$ has a convergent subsequence, you can take this subsequnce's limit (which exists because of convergence), and it will be an element of the said set.

Title: Is the following set non-empty?


问:
True or False? There is a non-invertible matrix $B$ such that $B^4- I_4 - B^2=0.$
I have no idea how to answer this question, I tried starting with a matrix $B$ containing $16$ different variables but the calculations took hours and I don't think I was getting anywhere anyway.
This is a question from a homework for an introductory module on Matrices and Vectors.

答: Note that $$ B\cdot(B^3-B)=I$$

Body: Note that $$ B\cdot(B^3-B)=I$$


问:
Initial value problem with $t$ and $x'$
Really stuck with this,

\begin{cases}
 2tx'(t)-1=x^2t \\
 x(t=1)=1 \\
 \end{cases}

I don't understand the variables. What does it mean that $x$ differentiated have $t$ as a function value, like this: $x'(t)$? Don't get it :(

答:
One way to see it simply is :

Find all the solutions of functions $x : t \to x(t) $ such that

$$ \forall t \in [1, \infty[, \ 2tx'(t)-1=x^2(t)t\\
x(1)=1$$

The defintion domain is here at minima (it can be bigger than $[1,\infty[$)

Title: Initial value problem with $t$ and $x'$


问:
Existence and the value of $\lim_{x \to 0} \int^{3x}_x \frac{\sin t}{t^2}dt$
I need the show the existence of the following limit and then calculate the limit

$$\lim_{x \to 0} \int^{3x}_x \frac{\sin t}{t^2}dt$$

Since the antiderivative of $\frac{\sin t}{t^2}$ was not nice, I tried to use the approximation $\sin x \approx x$ for $x$ close to $0$. Then, I can integrate and find the limit as $\ln3$.

Is this a valid solution and can I solve this without using such approximation?

答:
Notice that, for any $ x\in\mathbb{R} $; : \begin{aligned} \int_{x}^{3x}{\frac{\sin{y}}{y^{2}}\,\mathrm{d}y}&=\ln{3}-\int_{x}^{3x}{\frac{y-\sin{y}}{y^{2}}\,\mathrm{d}y}\\ &=\ln{3}-\int_{0}^{3x}{\frac{y-\sin{y}}{y^{2}}\,\mathrm{d}y}+\int_{0}^{x}{\frac{y-\sin{y}}{y^{2}}\,\mathrm{d}y}\\ &=\ln{3}-\int_{0}^{x}{\frac{3y-\sin{\left(3y\right)}}{27y^{2}}\,\mathrm{d}y}+\int_{0}^{x}{\frac{y-\sin{y}}{y^{2}}\,\mathrm{d}y}\\&=\ln{3}+\int_{0}^{x}{f\left(x\right)\mathrm{d}x} \end{aligned}

In the second line we were able to split the integral apart because $ x\mapsto\frac{x-\sin{x}}{x^{2}} $ is piecewise continuous on any segment $ \left[a,b\right]\subset\left[0,+\infty\right) $.

In the last line $ f $ is non other than the function $ x\mapsto\frac{x-\sin{x}}{x^{2}}-\frac{3x-\sin{\left(3x\right)}}{27x^{3}} $, which is also piecewise continuous on $ \left[0,a\right] $, for any $ a>0 $.

Being piecewise continuous makes $ f $ bounded on any segment $ \left[a,b\right] \subset\left[0,+\infty\right) $, thus : $$ \int_{0}^{x}{f\left(y\right)\mathrm{d}y}\underset{x\to 0}{\longrightarrow}0 $$

Hence : $$ \int_{x}^{3x}{\frac{\sin{y}}{y^{2}}\,\mathrm{d}y}\underset{x\to 0}{\longrightarrow}\ln{3} $$


问:
From general ramification theory to ramification indexes of morphisms of elliptic curves
The reference for what I'll say here is Silverman's The arithmetic of elliptic curves, ch. 2, § 2.

Let $C_1, C_2$ be two elliptic curves, $\Phi : C_1 \to C_2$ a non trivial morphism of algebraic projective curves and $P\in C_1$ a point. From that, Silverman defines the index of ramification of $\Phi$ at $P$ and denotes $e_\Phi(P)$ to be $$e_\Phi(P) := \mathrm{ord}_P(\Phi^* t_{\Phi(P)}),$$ where $t_{\Phi(P)}\in K(C_2)$ is a uniformiser at $\Phi(P)$.

I have two problems: the first is to connect this definition of the ramification index to the general theory of ramification in Dedekind rings; the second is to derive the following identity from the general theory: for all point $Q\in C_2$, the equality $\star$ $$\sum_{P\in \Phi^{-1}(Q)} e_\Phi(P) = \deg(\Phi)$$ holds. I think I solved the first problem but not the second and I get contradictive results.

First problem

Let $$A = \Phi^* K[C_2]_{\Phi(P)}.$$ Since $K[C_2]_{\Phi(P)}$ is Dedekind, $A$ is Dedekind as well since $\Phi^*$ is an injective ring homomorphism and is therefore a ring isomorphism on its image. Note that since $K[C_2]_{\Phi(P)}$ is a local ring with only one maximal ideal $\mathfrak{m}_{\Phi(P)}$, the ring $A$ is local as well with only maximal ideal $\Phi^* \mathfrak{m}_{\Phi(P)}$. Since $A$ is a Dedekind ring, its maximal ideal is also its only prime ideal.

Now let $$B = K[C_1]_P.$$ This ring is a Dedekind local ring with maximal ideal $\mathfrak{m}_P$. We have an inclusion $$A\subset B.$$ Indeed, if $x\in K[C_2]_{\Phi(P)}$ is well defined at $\Phi(P)$, then $\Phi^* x := x\circ \Phi$ is automatically well defined at $P$.

Therefore $A\subset B$ is a tower of Dedekind rings and the so-called index of ramification of $\Phi$ at $P$ can be seen as the index of ramification (in the sense of the ramification theory in Dedekind rings) of the prime ideal $\mathfrak{m}_P$ over $A$. Indeed, the Dedekind rings $A$ and $B$ both only have one prime ideal, therefore the decomposition of $\Phi^*\mathfrak{m}_{\Phi(P)}$ must be of the form $\mathfrak{m}_P^e$ for some integer $e$.

Second problem

Now let's try to derive the formula $\star$ for a given point $Q\in C_2$. A well-known equality from ramification theory in Dedekind rings is that if $\mathfrak{p}$ is a prime ideal in $A$, then $$\sum_{\mathfrak{P}|\mathfrak{p}} e_{\mathfrak{P}/\mathfrak{p}} f_{\mathfrak{P}/\mathfrak{p}} = [\mathrm{Frac}(B) : \mathrm{Frac}(A)],$$ where $e_{\mathfrak{P}/\mathfrak{p}}$ is the ramification index of $\mathfrak{P}$ over $\mathfrak{p}$ and $f_{\mathfrak{P}/\mathfrak{p}}$ is the residual degree. First, here we have $[\mathrm{Frac}(B) : \mathrm{Frac}(A)] = \mathrm{deg}(\Phi)$. Second, with that being said and what I wrote in the previous section, necessarily $\mathfrak{p} = \mathfrak{m}_{\Phi(P)}$, $\mathfrak{P} = \mathfrak{m}_P$ and the equality yields $$e_\Phi(P)\cdot f_{\mathfrak{m}_{\Phi(P)}/\mathfrak{m}_P} = \mathrm{deg}(\Phi),$$ which contradicts the equality $\star$ given by Silverman.

Could you explain what I did wrong? Thanks a lot.

答: You don't need to go to local rings. You can work just with global fields. See my answer at order of kernel of surjection between curves is equal to separate degree for details.</p>


问:
Evaluating $\lim_{x \to 1} \frac{1 - x^{1/\pi}}{1 - x^{1/e}}$ without de l'Hospital rule
Is it possible to evaluate this limit without de l'Hopital's rule?
$$\lim_{x \to 1} \frac{1 - x^{1/\pi}}{1 - x^{1/e}}$$

答:
Using the fact that $ \lim\limits_{x\to 0}{\frac{\mathrm{e}^{x}-1}{x}}=1 $, we have : \begin{aligned}\Large \frac{1-x^{\frac{1}{\pi}}}{1-x^{\frac{1}{\mathrm{e}}}}=\frac{\exp{\left(\frac{\ln{x}}{\pi}\right)}-1}{\exp{\left(\frac{\ln{x}}{\mathrm{e}}\right)}-1}=\frac{\mathrm{e}}{\pi}\times\frac{\frac{\exp{\left(\frac{\ln{x}}{\pi}\right)}-1}{\frac{\ln{x}}{\pi}}}{\frac{\exp{\left(\frac{\ln{x}}{\mathrm{e}}\right)}-1}{\frac{\ln{x}}{\mathrm{e}}}}\underset{x\to 1}{\longrightarrow}\frac{\mathrm{e}}{\pi} \end{aligned}

Because $ \lim\limits_{x\to 1}{\frac{\exp{\left(\frac{\ln{x}}{\pi}\right)}-1}{\frac{\ln{x}}{\pi}}}=\lim\limits_{y\to 0}{\frac{\mathrm{e}^{y}-1}{y}}=1$, and $ \lim\limits_{x\to 1}{\frac{\exp{\left(\frac{\ln{x}}{\mathrm{e}}\right)}-1}{\frac{\ln{x}}{\mathrm{e}}}}=\lim\limits_{y\to 0}{\frac{\mathrm{e}^{y}-1}{y}}=1 $.


问:
Evaluating $\lim_{n \to \infty} \sum_{k=1}^n \frac{1}{ n + k}$
I'm having some trouble evaluating the following limit:

$$\lim_{n \to \infty} \sum_{k=1}^n \frac{1}{ n + k}$$

I think that I'm supposed to transform this into an integral using Riemann Sums. How should I proceed? Because I can't see anything that resembles a Riemann sum.

答: Using Stadnicki comment, it looks like the limit is$\int_0^1\frac{1}{1+x}dx=ln(2)$.


问:
Eating cake probability problem
Question: We want to divide a cake between Mike and Jack. First, Mike takes a portion of the cake. Then, Jack takes a piece of the remaining cake. Both of the pieces are random variables uniformly distributed over what is currently available. What is the probability that Jack gets more than half of the cake?

Here is my approach:

$X_M \sim Uni(0,1)$

$X_J \sim Uni(0,1)$

$P[ \ X_M(1- X_J) > 0.5 \ | \ X_J] = 1 - P[ \ X_M(1- X_J) \leq 0.5 \ | \ X_J]$

$ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 1 - F_{X_m}(\frac{0.5}{1- X_J} |
 X_J)$

$ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $

At this point I don't know how to proceed and I am not sure if I have modelled the problem correctly. Any help would be appreicated.

答:
Here is another approach, using conditionals.

Notice how $X_M\sim \mathcal{U}(0,1)$ while $X_J|X_M \sim \mathcal{U}(0,1-X_M)$ You're looking to compute $P(X_J>1/2)$. We get $$P(X_J>1/2)=\int_0^{1/2}P(X_j>1/2|X_M=t)f_{X_M}(t)dt=\int_0^{1/2} \int_{1/2}^{1-t}\frac{1}{1-x}dxdt=\frac{1-\ln(2)}{2}$$

Title: Eating cake probability problem


问:
Intuition on non-unique ideal factorization if not integrally closed
I'm aware of the result that integral domains admit unique factorization of ideals iff they are Dedekind domains.

It's clear that $\mathbb{Z}[\sqrt{-3}]$ is not a Dedekind domain, as it is not integrally closed.  I'm having difficulty demonstrating directly that $\mathbb{Z}[\sqrt{-3}]$ does not admit unique factorization of ideals.

Obviously we only need one example of an ideal that doesn't have a unique factorization into prime ideals, but a good answer would provide either a process or some intuition in finding such an example.

答:
Hint $\ $ Given any fraction $\rm\,w\,$ witnessing that the nonmaximal order
$\rm\,D\,$ is not integrally closed, i.e. a proper fraction over $\rm\,D\,$
that's a root of a monic $\rm\,f(x)\in D[x],\,$ the proof below shows,
for the fractional ideal $\rm\ I = (w,1),\ \ I^{\:\!n} =\, I^{\:\!n-1},\,$ but $\rm\ I\ne 1\,$ (by $\rm\,w\not\in D$), $ $ contra unique factorization.
In the OP:  $\rm\, n=2,\  w = (-1\! +\! \sqrt{-3})/2\ $ is integral over
$\rm\,D = \mathbb Z[\sqrt{-3}],\,$ being a root of $\rm\,x^2+x+1\,.$

Alternatively, clearing denominators from the fractional ideals to obtain
integral ideals, we obtain $\rm\ J^2 =\, 2\:\!J,\,$ but $\rm\ J \ne (2),\,$ for $\rm\, J = 2\,(w,1) = (-1+\sqrt{-3},\,2),\, $ also contra unique factorization.
For further remarks, including relations with Dedekind's conductor ideal and
irrationality proofs, see my discussion with Gerry Myerson here and here in a sci.math
thread circa May 20, 2009. Below is an excerpt from the first linked post, followed by an excerpt of the second (first we use fractional ideals, which we then eliminate, for readers knowing only integral ideals).

Theorem $\ $  Dedekind domains $\rm\,D\,$ (so PIDs) are integrally
closed.

Proof   $\ $ Suppose a fraction $\rm\,w\,$ over $\rm\,D\,$ is integral
over $\rm\,D,$ i.e. in terms of $\rm D$-fractional ideals

$$\begin{align}
\rm suppose \,\ \ \color{#c00}{w^n}\,\  &\rm\in\qquad   (w^{n-1},\ldots,w,1)\,.\quad\quad \color{#0a0}{[*]}\\[.4em]
{\rm Since}\   \rm\, (w,1)^n\ &\rm =\ (\color{#c00}{w^n},w^{n-1},\ldots,w,1) \\[.4em]
&\rm =\qquad   (w^{n-1},...,w,1)\ \ \ \rm by\,\ \ \color{#0a0}{[*]}\\[.4em]
{\rm i.e.}\, \ \ \  \rm\ (w,1)^n\, &\rm =\ (w,1)^{n-1}\\[.4em]
\rm thus\ \ \ \,(w,1)\ \  &\rm =\   (1)\ \text{  by cancelling invertible ideal }\ (w,1)^{n-1}\\[.4em]
\rm therefore\,\ \ \ w\ &\rm \in\ \:\!(1) = D,\  thus \ D\ is\ integrally\ closed.
\quad \small \bf QED
\end{align}\qquad\quad $$

Remark $\ $  A common similar proof cancels $\,\rm I\,$ from  $\rm\ I^2 =\, I,\ \  I =
(w^n,...,w,1)\,.$

Note $ $ If fractional ideals are unfamiliar then we can
clear denominators from the prior proof by scaling it by  $\rm\, b^n,\,$
where  $\rm\ w = a/b,\,$ i.e.

$$\begin{align}\rm (w,1)^n\ &\rm =\ (w,1)^{n-1}\ \text{  which, upon scaling
through by }\ b^n\\[.4em]
\rm \Rightarrow\ \ \  (a,b)^n\, &\rm =\ b\ (a,b)^{n-1}\\[.4em]
\rm \Rightarrow\ \ \   (a,b)\ \ \, &=\rm\  (b)\ \ \text{by cancelling the invertible
ideal }\ (a,b)^{n-1}\ \ from\ above\\[.4em]
\Rightarrow \rm \quad  b\mid a\ \ \ &\rm in\ \  D,\ \  i.e.\ \ a/b\in D
\end{align}\quad$$

See here for a more detailed proof in the cubic case.

Gerry Myerson ge...@maths.mq.edi.ai.i2u4email wrote on May 19, 2009, 7:56:35 PM:

Bill Dubuque w...@nestle.csail.mit.edu wrote:

The (monic) Rational Root Test is essentially equivalent to the fact
that the domain of integers is integrally-closed. If you examine the
elementary direct proofs from this more general standpoint they're
essentially all equivalent. This is evident and trivial to anyone
familiar with notion of conductor ideals (dating back to Dedekind).
Alas, apparently not all number-theorists are familiar with this
basic notion, e.g. see Gerry Myerson's post [1] where he rediscovers
the well-known elementary inductive proof that obtains from unwinding
the elegant one-line conductor-based proof. Further, in the same
thread, he seems to lend support to the absurd claim by Estermann
(and Niven?) that this proof is new. Nothing could be further from
the truth. Such methods are merely elementary manifestations of the
raison d'etre for the abstraction incorporated in the conductor ideal.
This fundamental object is introduced very early in any study of
algebraic number theory and the perceptive student should easily
recognize the fundamental role it plays in more concrete instances.

[1] Gerry Myerson, sci.math post on 2006/7/12
Thread: Irrationality and the Fundamental Theorem of Arithmetic

Readers may be interested in my paper, Irrationality via well-ordering,
Australian Math. Soc. Gazette 35 (2008) 121-125, available on the web
at http://www.austms.org.au/Publ/Gazette/2008/May08/Myerson.pdf

A better title would be "Irrationality via the Division Algorithm"
(or "via the Euclidean Algorithm") since your proofs there are simply
well-known proofs of PID results that've been pulled-back to Euclidean
domains by eliminating ideal-theoretic notions. More on this below.

It is misleading to say the the proofs are "via well-ordering".
Rather, the proofs depend crucially on a domain $D$ being Euclidean.
This requires not only a "size" map from $D$ into a well-ordered set,
but also, crucially, a Division Algorithm with respect to the map.
Euclideaness is used implicitly in your proofs when you take the
integer or fractional part of a fraction to help achieve a descent
on possible denominators for $\,w = \sqrt m\,$ (or $w$ an algebraic integer).

In that paper, you'll find,

THEOREM $2$. If $m$ is an integer, and $\sqrt m$ is not an integer, then $\sqrt m$ is irrational.

Proof. Assuming $\,w = \sqrt m\,$ is rational but not an integer, let $k$ be the
integer such that $k < w < k+1,$ and let $n$ be the smallest positive
integer such that nw is an integer; then $n(w-k)$ is a smaller positive
integer whose product with $\sqrt m$ is an integer, contradiction.

That's very well-known and very widely published. It can be presented more  conceptually as a denominator descent via the division algorithm, e.g. see here.

You'll also find the theorem stating that the integers are integrally closed in the rationals;

THEOREM $5$. Let $f$ be a monic polynomial with integer coefficients.
Let $w$ be a solution of $f(w) = 0.$ Then if $w$ is not an integer,
it is irrational.

Proof. Assume the hypotheses, assume $w$ is rational, and let $n$ be
the smallest positive integer whose product with $w^j$ is an integer
for all $j$ less than the degree of $f$. Then $n$ times the fractional part
of $w$ is a smaller positive integer with the same property, contradiction.

Again that's very-well known and I do recall seeing it published at
least a handful of times if not more. Notice that your $\,n\,$ is simply
a least common denominator for the fractions $w^j.\,$ More structurally
consider instead the universal denominator set $\,C\subset \Bbb Z\,$ for the whole ring $\,\Bbb Z[w],\,$
i.e. $\,C\, \Bbb Z[w] \subseteq \Bbb Z,\,$ i.e. $\,C = \{n \in \Bbb Z\ :\ n f(w) \in \Bbb Z,\, \forall\ f(w) \in \Bbb Z[w]\}$. This yields an ideal $\,C\,$ known as the conductor of $\,\Bbb Z[w]\,$ into $\Bbb Z.$

$C\,$ satisfies the crucial property that $\,n \in C \Rightarrow  nw \in C,\,$ simply because $\,w\,$ is integral over $\,\Bbb Z\,$ (i.e. $\,w^k\,$ is a $\,\Bbb Z$-linear combination of $\,w^j,\,$ for $\,j < k = \deg w).\,$ This then implies that $\,C\,$ is not only an ideal of $\,\Bbb Z,\,$ but also of $\,\Bbb Z[w]\,$ (in fact the largest such ideal).
But since $\,\Bbb Z\,$ is a PID, the conductor ideal is principal $\,C = n\Bbb Z\,$
so $\,nw \in C = n\Bbb Z \Rightarrow\, w \in \Bbb Z.\,$ So we've proved any fraction integral over a PID actually lies in it, i.e. PIDs are integrally closed.

Your proofs essentially proceed the same way except you have
eliminated the lemma that $\,\Bbb Z\,$ is a PID by repeating the proof of the Lemma ("inlining" it) in your
descent-based proof on denominators, i.e. $\,n \in C \Rightarrow nw \in C
\Rightarrow n(w-k) \in C,\,$ for $\,k = {\rm integer\_part}(w).\,$ But $\,0 < n(w-k) < n,\,$ via $\,0 < w-k < 1,\,$ so $\,n(w-k)\,$ is a smaller denominator than $\,n.\,$
This is equivalent to descent-based proof that the denominator
ideal $\,C\,$ is principal. It's essentially a special case of the
the standard Euclidean descent proof that Euclidean $\Rightarrow$ PID,
i.e. if $\,n\,$ is the smallest elt of $\,C\,$ then $\,n\,$ must divide every
other elt $\,m\,$ of $\,C,\,$ else Euclidean division yields a smaller
elt $\,m \bmod n \in C,\,$ contra minimality of $\,n.\,$ Above is just the
special case $\,m = nw,\,$ which yields $\,n\mid nw\,$ in $\,\Bbb Z,\,$ i.e. $\,w\in\Bbb Z.$

Here is how I like to present this proof in structural form:

The conductor ideal of a domain extension $\,D \subset E\,$ is $\,C = \{d \in D\ :\ dE \subseteq D\}$.

One easily sees $\,C = CD = CE,\,$ i.e. $\,C\,$ is an ideal of both $\,D\,$ and $\,E$.

$C\neq \{0\}\,$ & $\,D\,$ PID $\Rightarrow C = cD = cE \Rightarrow D = E\,$ via cancel $\,c \neq 0.\ \ $ [*]

Said proof is just the special case $\,C,D,E = n,\,\Bbb Z,\,\Bbb Z[w].\,$ Here
$\,C\neq \{0\}\,$ since $\,w = a/b,\,$ $ \deg f = k \Rightarrow b^{k-1} \in C,\,$ i.e. $\,b^{k-1}\,$ is a denominator for all elts of $\,\Bbb Z[w] = \Bbb Z\langle 1,w,w^2,..,w^{k-1}\rangle$.

Notice how simple the proof has become when expressed in the
appropriate abstractions: it is a trivial one-line proof [*]
based on the conductor ideal, being principal, is cancellable.
More generally, cancellable/invertible ideals (esp. Dedekind
domains) play a fundamental role in algebraic number theory.

I ask in the paper for the earliest publications of these (and other)
proofs in the form in which I relate them. This form may well be
merely an elementary manifestation of the conductor ideal, but I
reckon there's a lot to be said for elementary manifestations. In
particular, students who are still years away from learning about
conductor ideals can still understand, maybe with a little help,
the proofs above.

The same might be argued for analogous "elementary" proofs that've
had their higher-order structure removed, e.g the famous proof (better here)
of unique factorization by Klappauf, Lindemann, Zermelo that I
cited earlier in this thread. It isn't published too frequently
(except as a curiosity) because it obfuscates the underlying
algebraic structure and hence has little pedagogical value.
Someone ignorant of the relevant algebraic theory might stumble
upon such proofs with great effort. But someone familiar with
the theory can mechanically churn out these monstrosities by
simply rewriting the higher-order proofs to use only the most
primitive notions - eliminating structure (rings, ideals, etc.)
Indeed, the process is so mechanical that one could easily
program a computer to perform such proof transformations.

The earliest publication I've seen of the proof given above for
Theorem 2 is the 1975 paper of Estermann. I haven't seen any
print publication of the proof of Theorem 5 given above, but it was
posted to this newsgroup in July 2000, and I've seen it on the web.
There may well have been earlier appearances of these proofs
in the form given here, and I'd like to see them.

There's little point in doing such for the reasons enumerated
above. The conductor-based ideas are over a century old - dating
back to the ground-breaking work of Dedekind. It's highly likely
that the proof is already in Dedekind's work (perhaps implicitly
since there are various ideal-theoretic forms of such proofs).

Alas, no one has yet tackled the enormous task of writing the
definitive history of unique factorization - where many of these
topics would be discussed. I once thought I might do such and
had many files of papers of historical significance to aid in
this endeavor. However I no longer have these available since
they were among items that were stolen while in storage. But
nowadays such a task should be easier since many older papers
are now much more easily accessible in electronic archives.


问:
Riemann integral show $f(x)=g(x)$ for at least 1 $x$ in [a,b]
Let $f$ and $g$ be continuous functions on $[a,b]$ such that $\int_a^b f = \int_a^b g$. Show that there exists $x\in [a,b]$ such that $f(x) = g(x) $.

I want to assume not and then show that the integrals cannot be equal. but perhaps an argument on an upper or lower sums of both fuctions could find the point?

答:
Let $f$ and $g$ be continuous functions on $[a, b]$ such that
$$
\int_a^b f(x)\ dx = \int_a^b g(x)\ dx.
$$
Then
$$
\int_a^b f(x)-g(x)\ dx = 0.
$$
Since $f$ and $g$ are continuous, then $f-g$ is continuous. Hence, if $f-g$ is never zero on $[a, b]$, then it must be strictly positive or negative on $[a, b]$. But then $\int_a^b f(x)-g(x)\ dx \neq 0$, which is a contradiction.</p>


问:
Cardinal numbers and Well ordered Set
(ZF) For every set A we denote with h*(A) the smallest ordinal α for which there is no surjective function from A to α (α is nonzero):

h∗(A) = µα[¬(α ≤∗ A)].
Prove that for every set A it is true that:

h∗(A) ≤ α ⇒ ¬(α ≤∗ A);

h∗(A) is a cardinal number;

h(A) ≤ h∗(A);

If A can be  well ordered set, then it follows that h(A) = h∗(A).

Before I start, I have to say that I am a liitle bit confused of the problem itself. The reason is in the notation of h(A). In previous cases, we have named h as a function of choice for A,but here the meaning is different, so I stick to what is written above,since we are in ZF. However,

My ideas are:
To use the following

Lemma:
.For every set A there exists an ordinal α such that there is no surjective function from A to α:
(∀A)(∃α)[¬(α ≤∗ A).
/1/ Since we have picked up the smallest such ordinal, I will try to use Transfinite recursion to prove the statement. Namely, Let P(h∗(A),α) be a property defined over all ordinals α in A,satisfying the condition we want. Then:(∃ h∗(A))P(h∗(A),α,u)->(∃ h(A))(P(h(A),α,u) and for every β(β<h(A)->¬(P(h(A),β,u)). This directly proves 1).
/2/ Since for every β(β<h*(A)->¬(P(h*(A),β,u)), a.k.a ¬(Limit(β)) and ord(h*(A)) => Nat(h*(A)). But this means card(h*(A)).

To prove (3) I will use the fact that h*(A) is the min cardinal for which there is no surjection. Hence for an arbitrary cardinal number h(A)<h*(A) there is an image with Dom in h(A) and Rng in A.

For (4) I think that the direct application of the Definition for well ordered set which states that : if for every subset A' of A there is a smallest element (<), then A is well ordered. But then since we have assumed that h*(A) is the min cardinal satisfying this and h(A)<h*(A), they should be equal.

I will be extremely thankful if someone help to verify the correctness of my sttempts to solve it. Thank you.

答:
I dislike being so blunt, but so far as I can tell, you are completely lost. Your argument for (1) makes no sense: (1) is not a statement about ordinals in the set $A$. And even if it were, it is not at all clear what $P(h^*(A),\alpha)$ is intended to be. Your argument for (2) is completely incomprehensible. In your argument for (3) you seem to be trying to prove something about ordinals that are known to be less than $h^*(A)$, when in fact you are supposed to be proving that a certain ordinal is less than $h^*(A)$. And your argument for (4) is simply incoherent.

I’m going to do the first three and let you take another crack at the fourth one; spaceisdarkgreen’s comment should at least point you in the right general direction.

(1) Suppose that $h^*(A)\le\alpha$; then the function

$$f:\alpha\to h^*(A):\xi\mapsto\begin{cases}
\xi,&\text{if }\xi<h^*(A)\\
0,&\text{otherwise}
\end{cases}$$

is a surjection. If $g:A\to\alpha$ is a surjection, $f\circ g$ is a surjection from $A$ onto $h^*(A)$, contradicting the definition of $h^*(A)$, so there is no surjection of $A$ onto $\alpha$, and therefore $\alpha\not\le^* A$.

(2) Since $h^*(A)$ is an ordinal, there is a cardinal $\kappa\le h^*(A)$ such that there is a bijection $f:\kappa\to h^*(A)$. If $g:A\to\kappa$ is a surjection, then $f\circ g$ is a surjection of $A$ onto $h^*(A)$, which is impossible. Thus, there is no surjection from $A$ onto $\kappa$. By definition $h^*(A)$ is the smallest ordinal that is not a surjective image of $A$, so $h^*(A)\le\kappa$, and hence $h^*(A)=\kappa$ is a cardinal.

(3) Suppose that $h(A)>h^*(A)$; $h(A)$ is the smallest ordinal $\alpha$ such that there is no injection from $\alpha$ into $A$, so there is an injection $f:h^*(A)\to A$. Let $R=\operatorname{ran}f$, so that $f^{-1}$ is a bijection from $R$ to $h^*(A)$. Then the function

$$g:A\to h^*(A):\xi\mapsto\begin{cases}
f^{-1}(\xi),&\text{if }\xi\in R\\
0,&\text{otherwise}
\end{cases}$$

is a surjection from $A$ onto $h^*(A)$, which is impossible, and therefore $h(A)\le h^*(A)$. (I am assuming here that $h$ is the Hartogs function; it certainly isn’t a choice function.)

Title: Cardinal numbers and Well ordered Set


问:
Why is $\Bbb Z_3$ cyclic?
I want to prove that $\Bbb Z_3$, defined as the only group of order $3$, is cyclic.

The identity element $e$ needs to be there, so $\Bbb Z_3=\{a,b,e\}$. Now, $ab$ can't be nor $a$ or $b$, otherwise one of them would be $e$, so $ab=e \implies b=a^{-1}$. Now, the next step would be proving that $a^2=a^{-1}$, but why is that necessary? Couldn't the multiplication table be like this? $$ab=ba=e, \quad a^2=a, \quad ({a^{-1}})^2=a^{-1}$$

答: From $a^2 = a$  we can multiply both sides with $a^{-1}$ and thus obtaining $a=e$. This is a contradiction(since $a$ and $e$ are two different elements), so you cannot have the multiplication table stated.

Title: Why is $\Bbb Z_3$ cyclic?


答:
$a^2$ could be $1$ or $a$ or $b$.

In the first case $ab\ne aa=1$ and $ab\ne a1=a$ and $ab\ne 1b=b$.

In the second $a=a1\ne aa=a$

Title: Why is $\Bbb Z_3$ cyclic?

Body:
I want to prove that $\Bbb Z_3$, defined as the only group of order $3$, is cyclic.

The identity element $e$ needs to be there, so $\Bbb Z_3=\{a,b,e\}$. Now, $ab$ can't be nor $a$ or $b$, otherwise one of them would be $e$, so $ab=e \implies b=a^{-1}$. Now, the next step would be proving that $a^2=a^{-1}$, but why is that necessary? Couldn't the multiplication table be like this? $$ab=ba=e, \quad a^2=a, \quad ({a^{-1}})^2=a^{-1}$$


问:
$D$ is not open at $Y$, as $D$ is not open at $\mathbb{R}$.
Let    $D=\{x\hspace{0.2cm}|\hspace{0.2cm} \frac{1}{2}\le|x|\le 1\}=\left[-1,-\frac{1}{2}\right]\cup \left[\frac{1}{2},1\right]$, $Y=[-1,1]$

$D$ is not open at $\mathbb{R}$, as there is no $\epsilon>0$ such as $B(-1,\epsilon)\subset D$, $B\left(-\frac{1}{2},\epsilon\right)\subset D$, $B\left(\frac{1}{2},\epsilon\right)\subset D$ and $B(1,\epsilon)\subset D$.

$D$ is not open at $Y$, as $D$ is not open at $\mathbb{R}$.

Is that correct? Obs: Usual topology of the straight and $Y$ induced topology

答:
In this case, $D$ is not open in $Y$ because there is no $\varepsilon > 0$ such that:
$$B\left(\frac 12, \varepsilon\right)\cap Y\subset D$$
However, your reasoning is faulty. For $D\subset Y\subset X$, the implication
$$D\text{ not open in } X\Rightarrow D\text{ not open in } Y$$
is not always true. For example, in your situation, $D$ is not open in $\mathbb R$, but $D$ is open in $D$.


问:
Why is this map an isomorphism?
In Altman-Kleinman "Introduction to Grothendieck Duality Theory", page 105, there is the following Lemma:

I don't understand why by uniqueness, I can conclude $w \circ w'=id$. Any help?

答:
As $d:A \rightarrow \Omega$ is a $K$-derivation there is a unique morphism $w‘: \Omega_{A\mid K}^1 \rightarrow \Omega$ satisfying $w’ \circ d_{A\mid K} = d‘$ by the universal property of the module of Kähler-differentials.

As $d_{A\mid K}$ is a derivation as well, there is a unique morphism $i: \Omega_{A\mid K}^1 \rightarrow \Omega_{A\mid K}^1$ satisfying $i \circ d_{A\mid K} = d_{A\mid K}$. Note that the identity is such a morphism, hence $i = id$.

Finally we are given a morphism $w: \Omega \rightarrow \Omega_{A\mid K}$ satisfying $w \circ d = d_{A\mid K}$. Hence we can calculate
$$w \circ w‘ \circ d_{A\mid K} = w \circ d = d_{A\mid K}$$
which shows that $w \circ w‘$ satisfies the universal property of $\Omega_{A\mid K}$, so again by uniqueness we find
$$w \circ w‘ = i = id.$$

Title: Why is this map an isomorphism?


答: By Lagrange's theorem, the order of $a$ is divisor of $3$. So either it is $1$, which means $a=e$, which is excluded, or it is $3$, i.e. $a^3=e$, which is equivalent to $a^2=a^{-1}$.

Title: Why is $\Bbb Z_3$ cyclic?


问:
Finding inverse modulo
I'm trying to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19.

Here is what I have done before I got stuck:

$x ≡ 9 \mod 19$

$\gcd(9,19) = \gcd(19,9)\\
          19 = 9*2 + 1\\
          9 = 1*9 + 0$

Bezout's Theorm

$\gcd (19,9) = m*19 + n*9\\
      1 = 19 - 9*2\\
        = 1*19 -2*9$

THUS, x = -2 mod 19 = 17 mod 19 = 17

BUT! 17 is not a multiple of 100, so from here, what do I do to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19?

Thanks!

Title: Finding inverse modulo

Body: mod $19\!:\ 100\equiv 5,\,\ 9\equiv -10\ \,$ so $\, \ 100 n\equiv 9 \iff 5n\equiv -10 \iff n\equiv -2\equiv 17.$


问:
Usage of $\epsilon$ in Naive Set Theory by Paul R. Halmos
I am currently learning Set Theory from Paul Halmos' Naive Set Theory. In the section about the axiom of specification, while dealing with Russell's Paradox, the author defined the set $B$ as:

$B=\{x  \epsilon  A: S (x)\}$

with $S(x)$ as

not$(x\epsilon x)$

How is $\epsilon$ used here? If it symbolises the relation 'belongs to' then how can an element belong to itself? It also proceeds, in the proof, to use such statements as:

...if $B \epsilon A$, then either $B \epsilon B$ also or else $B \epsilon' B$...

How can this set $B$ 'belong' to $A?$ $B$ can be is a subset of $A$, and it had been previously made clear that '$\epsilon$' and '$\subset$' are very different relations between elements and sets, or along sets.

Any help is appreciated. Thank You!

答: In most formulations of set theory, all elements of sets are themselves sets. This is called the hereditary property. Without axioms to prevent it, it is totally possible for sets to contain themselves. In ZFC this is prevented by the axiom of well-foundedness. In particular, when unrestricted comprehension is allowed over all sets, it is possible to define a set which is the collection of all sets that do not contain themselves.</p>


问:
Least residue power modulo
May someone confirm that the least residue of $44^8$ modulo $7$ is $4$ please?

And that $2^2 \equiv  4\, (\!\!\!\mod 7)$?

Thanks in advance.

答:
Lemma needed : For $a,b,n,r \in \mathbb{Z^+},$

$$a \equiv b \pmod{n} \implies a^r \equiv b^r \pmod{n}.$$

Proof:

$\displaystyle a\equiv b \pmod{n} \implies n | (a - b) \implies$

$\displaystyle \exists ~k \in \mathbb{Z} ~\text{such that}~ a = (b + nk) \implies$

$\displaystyle (a^r - b^r) = (b + nk)^r - b^r$

[Using binomial expansion]

$\displaystyle =~ \sum_{i=0}^r \left[(b)^i (nk)^{r - i}\right]
~-~ b^r$

$\displaystyle =~ \sum_{i=0}^{(r-1)} \left[(b)^i (nk)^{r - i}\right].$

Since the above summation stops at $(r-1)$,
$n$ divides each term in the summation.

Therefore

$n | (a^r - b^r) \implies a^r \equiv b^r \pmod{n}.$

Title: Least residue power modulo


问:
How to Solve Large Scale Linear Least Squares with Simplex Constraints
I need to solve a rather simple optimization problem, however the structure of the problem makes out-of-the-box commercial solvers fail. The problem is:\begin{aligned}
&\min_{x_i}\|\sum_{i=1}^{10}x_i\mathbf{a}_i - \mathbf{b}\|_2^2 \\
&s.t.: \sum_{i=1}^{10}x_i = 1,\; x_i\geq0
\end{aligned}
The decision variables are $x_i$, which are scalars, and typically the problem will have 10 variables. The complexity comes from the fact that $\mathbf{a}_i, \mathbf{b}$ are VERY LONG constant vectors, varying from 10,000 to 100,000 elements and possibly more. Without going too much into details, black-box solvers fail since they impute the variable over vectors, thus converting a 10-D problem to 100K-vars problem.

Since the problem has a simple structure (only complicated by the constant vectors), I think that interior point algorithms can perform well here. Also, the Hessian is very simple and easy to compute - it's $ij$-th entry is simply $\langle \mathbf{a}_i, \mathbf{a}_j \rangle$, with size $10\times 10$. I'm very familiar with optimization, however my experience is mostly with first-order algorithms. I'm almost clueless when it come to IPMs and not sure how to implement an appropriate algorithm. Does anyhow have a ready script I can use? Or any other tips that might help?

答:
The problem is given by:

\begin{aligned}
&\min_{x_i}\|\sum_{i=1}^{N}x_i\mathbf{a}_i - \mathbf{b}\|_2^2 \\
&s.t.: \sum_{i=1}^{N}x_i = 1,\; x_i\geq0
\end{aligned}

The problem is equivalent to:

$$
\begin{alignat*}{3}
\arg \min_{x} & \quad & \left\| A \boldsymbol{x} - \hat{\boldsymbol{b}} \right\|_{2}^{2} \\
\text{subject to} & \quad & {x}_{i} \geq 0 \\
& \quad & \boldsymbol{x}^{T} \boldsymbol{1} = 1
\end{alignat*}
$$

Where $ A = \left[ \boldsymbol{a}_{1}, \boldsymbol{a}_{2}, \ldots \right] $ and $ \hat{\boldsymbol{b}} = N \boldsymbol{b} $.

This is basically non negative least squares with Linear Equality Constraints.

You could easily solve it with many Least Squares solvers.

You could also utilize Orthogonal Projection onto the Unit Simplex with some acceleration (FISTA like) in the Projected Gradient Descent framework and have low memory and pretty fast solver even for large size problem.

When using the Projected Gradient Descent you should pre calculate $ {A}^{T} A $ and $ {A}^{T} \hat{\boldsymbol{b}} $ then the calculation per loop should be pretty small.


问:
Meager set and disjoint with line $y=ax$
Lemma. Let $X$ and $Y$ be second countable. If $A\subset X$ and $B\subset Y$, then $A\times B$ is meager iff at least of $A,B$ is meager.

Assume $f\colon \mathbb R\to \mathbb R$ and $D$ be a meager set subset of $R.$ Consider the graph of $f$ on $D$, that is. $$W:=\{\langle x, f(x)\rangle\colon \  x\in D\setminus\{0\}\}$$  By lemma above $W$ is meager in $\mathbb R^2$. Now, $\mathbb R^2\setminus W$ is co-meager in $\mathbb R^2$. I want to find a line $\ell_a(x)=ax$ such that $\ell_a\cap W=\{\langle x,ax\rangle\ \colon \  x\in\mathbb R\}\cap W=\emptyset.$  Is it possible in  $\text ZFC$? Do we need a set-theortical assumption, like the union of less than continuum many meager set will not cover $\mathbb R.$ Any help will be apprciacted greatly

答:
It is not necessarily possible. Let $D$ be a meagre subset of $\Bbb R$ of cardinality $2^\omega$, e.g., the middle-thirds Cantor set. Then we can index $D=\{x_a:a\in\Bbb R\}$ by the real numbers. Now let

$$f:D\to\Bbb R:x_a\mapsto ax_a\;;$$

then the graph of $f$ meets every line $\ell_a$ through the origin.


问:
Sum of a series of a number raised to incrementing powers
How would I estimate the sum of a series of numbers like this:  $2^0+2^1+2^2+2^3+\cdots+2^n$.  What math course deals with this sort of calculation?  Thanks much!</p>

答:
A more general answer for the sum of any infinite geometric series would be:

$S(x) = \frac{a(1  −r^X)}{(1  −r)}$

where x is the number of terms (x for the $2^n$ position is n+1), a is the first term ($2^0$) of the series, and r (r ≠ 1) is the common ratio of the terms (2/1 = 4/2 = ... = 2).

So for $2^0 + 2^1 + 2^2 + 2^3 +2^4$ it would be $S(5) = \frac{1*(1 - 2^5)}{(1 - 2)} = \frac{-31}{-1} = 31$


问:
Is $P(1)$ true?
I just recently found out this fake proof by induction that all positive integers are equal from The Mathematical Gazette:

Let $P(n)$ be the propositition:

"If the maximum of two positive integers is $n$ then the integers are equal."

Clearly $P(1)$ is true. Assuming that $P(n)$ is true, assume that $u$ and $v$ are positive integers such that the maximum of $u$ and $v$ is $n + 1$. Then the maximum of $u - 1$ and $v - 1$ is $n$, forcing $u - 1 = v - 1$ by the validity of $P(n)$. Therefore, $u = v$.

I see this, almost a duplicate: Find the fallacy in the following treatment, and I understand it, but I got into an argument with someone. They say that the base case $P(1)$ is in fact, not true, because, either the two integers are already the same, or they are different, and only case where $P(1)$ is true is where they must be already the same, in which case we haven't proved anything.

I say, that the special case $n = 1$ forces the numbers to be the same, which makes $P(1)$ true.

Who is correct?

答: The base case is correct. The fallacy is in the induction step when you assume that $u-1$ and $v-1$ are positive integers.

Title: Is $P(1)$ true?


问:
Prove isomorphism between universal enveloping algebras
I have the following problem I can't solve. I am following a couse in Lie Algebras, and one of the exercises is prove the following isomorphism: Given a semisimple lie algebra $\mathfrak{g}$ over a field $\mathfrak{k}$ of characateristic 0, and let $\mathfrak{h}$ be a toral maximal subalgebra, then by the cartan-chevalley decomposition, $\mathfrak{g}$ splits as $\mathfrak{g}=\mathfrak{n}^- \oplus \mathfrak{h} \oplus \mathfrak{n}$. Let $\mathfrak{b}=\mathfrak{h}\oplus\mathfrak{n}$. Then one has that the map:

$$
f:\mathfrak{U}(\mathfrak{n}^-)\otimes\mathfrak{U}(\mathfrak{b})
\rightarrow
\mathfrak{U}(\mathfrak{g})
$$

$$
x\otimes y\longrightarrow
xy
$$

The exercise is to prove that this map is in fact an isomorphism. Where $\mathfrak{U}(\mathfrak{g})$ is the universal enveloping algebra of the $\mathfrak{g}$ and respectively for the rest.

I am very confused, because if you remove the $\mathfrak{U}$ part this map is no longer injective, since it's easy to find $x\in\mathfrak{n},y\in\mathfrak{b}$ so that $xy=0$,
but I don't understand how that is possible without violating the injectivity of $f$.

Any help is appreciated. Thanks to everyone.

P.D: For clarification, the Cartan-Chevalley decomposition establishes than
$\mathfrak{g}=
\mathfrak{h}
\oplus
\bigoplus_{\alpha\in\Phi}
\mathfrak{g}_\alpha
$
where $\mathfrak{h}$ is a maximal abelian subalgebra of ad-diagonalizable elements. (This just means that the linear map $ad(x)$ is diagonalizable).
Furthermore
$\mathfrak{g}_\alpha=\{
x\in\mathfrak{g} : [h,x]=\alpha(h)x
\}
$. Where $\Phi\subset\mathfrak{h}^*$ and $\Phi$ can
be split into $\Phi=\Phi^+\cup\Phi^-$. Then we define
$n
=
\bigoplus_{\alpha\in\Phi^+}
\mathfrak{g}_\alpha
$
and
$n^-
=
\bigoplus_{\alpha\in\Phi^-}
\mathfrak{g}_\alpha
$.

答:
In fact, if $L$ is any Lie algebra over any field $k$, and $L_1, L_2$ are subalgebras such that $L = L_1 \oplus L_2$ as $k$-vector spaces, then the $k$-linear map $f$ given by

$$U(L_1) \otimes_k U(L_2) \rightarrow U(L)$$
$$x \otimes y \mapsto xy$$

is an isomorphism of $k$-vector spaces (and hence of $(U(L_1),U(L_2))$-bimodules).

As noticed in the first bullet point in this question, this follows from the Poincaré-Birkhoff-Witt theorem, compare e.g. Bourbaki, Lie Groups and Algebras ch. 1 §7. Indeed, it is a corollary of PBW (in Bourbaki, Corollary 3) that if $(e_1, ..., e_n)$ is an ordered $k$-basis of a Lie algebra $\mathfrak g$, then the monomials $e_1^{r_1} \cdot ... \cdot e_n^{r_n}$ are a $k$-basis of $U(\mathfrak g)$. From this the assertion (which is stated in greater generality in Bourbaki's Corollary 6) follows. Namely, if now $(x_1, ..., x_m)$ is an ordered $k$-basis of $L_1$, and $y_1, ..., y_n$ one of $L_2$, then on the one hand PBW and tensor products over fields tell us that the set of all $x_1^{r_1} \cdot ... \cdot x_m^{r_m} \otimes y_1^{l_1} \cdot ... \cdot y_n^{l_n}$ is a $k$-basis of $U(L_1) \otimes U(L_2)$, on the other hand the images of these elements under $f$, namely, all $x_1^{r_1} \cdot ... \cdot x_m^{r_m} \cdot y_1^{l_1} \cdot ... \cdot y_n^{l_n}$, again by PBW are a $k$-basis of $U(L)$, because by assumption $(x_1, ..., x_m, y_1, ..., y_m)$ is an ordered $k$-basis of $L$.

Now apply this to $L=\mathfrak g, L_1 = \mathfrak{n}^-, L_2= \mathfrak b$.

To see where your supposed counterargument goes wrong (copied from comments and discussion):

Your computation of $xy=0$ for certain $x, y \neq 0$ seems to be happening in $M_3(\mathfrak k)$ (or $End_{\mathfrak k} ({\mathfrak k}^3)$). That matrix ring is an enveloping associative algebra of $\mathfrak{sl}_3$, and maybe likewise would be certain associative subalgebras $B:= \pmatrix{*&*&*\\0&*&*\\0&0&*}$, $N^-:=\pmatrix{0&0&0\\*&0&0\\*&*&0}$ corresponding to $\mathfrak b, \mathfrak n^-$. These algebras are quotients of the respective universal enveloping algebras (by the latter's universal property, although surjectivity might be more subtle), but of course a product being zero in a quotient tells us little about the product being zero in the original ring.

What this computation shows, then, is that even though there are canonical surjections of associative algebras
$$U(\mathfrak n^-) \twoheadrightarrow N^-, U(\mathfrak b) \twoheadrightarrow B, U(\mathfrak g) \twoheadrightarrow M_3(k)$$
the map $$N^- \otimes_{\mathfrak k} B \rightarrow M_3(k)$$
induced via those projections from the given map $U(n^-) \otimes U(b) \simeq U(g)$, is no longer an isomorphism. But viewed this way, that is maybe not as surprising.

Full disclosure, I have made the mistake of mixing up standard enveloping matrix algebras with the universal enveloping algebra before, and I still sometimes do calculations in those matrix rings to get a first feeling for the universal enveloping one, but it's important to remember that the matrix algebras (like the above $M_3(\mathfrak k), B, N^-$) are just quotients -- and for that matter, with a lot factored out -- of the "much, much bigger" universal enveloping algebras. In particular, note that the above PBW corollaries also imply that $x^my^n \neq 0$ in $U(\mathfrak g)$ for all $m,n \in \mathbb N$ and any $x \neq 0 \neq y \in \mathfrak g$.


问:
Number Theory - Differences of powers of 2
I'm not really familiar with number theory, or mathy stuff for that matter.
However I recently noticed that if you take the even powers of 2 ( $2^n$ where $n$ is even)
and write the difference of each two consecutive numbers ( $2^4 - 2^2$ which is 12),
and turn those differences into a sequence and repeat, like so:

```<code>1, 4, 16, 64,256
   3, 12, 48,192
       9, 36,144
          27,108
              81 (let's call this 'm')
</code>```

the final numbers is a power of 3.

Why does this happen? Is there any way to prove this? Is it a proven thing?

答:
Let $n=2k$ where $k$ is an integer. Then

$2^n - 2^{n-2} = 2^{2k} - 2^{2k-2} = 2^{2k-2}(4-1) = 3 \cdot 2^{2k-2}$. Thus taking a difference of consecutive even powers of $2$ yields a product of $3$ with the lower power of $2$ that you used.

If you take successive differences, you are introducing more $3$ factors and continuing to reduce the power of $2$ by two. By the time you've reached $0$ as the power on $2$, you've only accumulated powers of $3$.


问:
Why convolution regularize functions?
There is a tool in mathematics that I have used a lot of times and I'm still not confortable with. In fact I can't figure out (by this I mean that I cannot understand it geometrically) why does convolution regularize things. It is know for example that if $u\in L_{loc}^1(\mathbb{R}^N)$ and $f\in C_0^k(\mathbb{R}^N)$, then $f\ast u\in C^k(\mathbb{R}^N)$ and $$D^\alpha (f\ast u)=(D^\alpha f)\ast g$$

Well, I have a lot of questions about convolution that might help me understand it better and I would appreciated one who points me out references to read and some insight about it.

I - For what reason was convolution implemented in mathematics? Was it for regularizing functions? Who used it the first time?

II - Is there any intuitive way to find out why convolution make functions more smooth?

I can understand the analytical proof of II, but in the end it is just algebraic manipulations and I dont get the essence of the thing. Thank you for your help.

答: I can't help with the first question. As for the second, the way I think of it intuitively is that the convolution of two functions mixes their values and integrates. Integrating means averaging out, so whatever properties each function brought in to the convolution are relaxed. For instance, if one function had a sharp corner in its graph but was otherwise quite tame, then the contribution of the sharp point to the convolution will be moderated by the smoothness of the function at other points. This is why local ill-behavior tends to disappear in the convolution. I hope this helps. </p>

Title: Why convolution regularize functions?


问:
Eating cake probability problem
Question: We want to divide a cake between Mike and Jack. First, Mike takes a portion of the cake. Then, Jack takes a piece of the remaining cake. Both of the pieces are random variables uniformly distributed over what is currently available. What is the probability that Jack gets more than half of the cake?

Here is my approach:

$X_M \sim Uni(0,1)$

$X_J \sim Uni(0,1)$

$P[ \ X_M(1- X_J) > 0.5 \ | \ X_J] = 1 - P[ \ X_M(1- X_J) \leq 0.5 \ | \ X_J]$

$ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 1 - F_{X_m}(\frac{0.5}{1- X_J} |
 X_J)$

$ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $

At this point I don't know how to proceed and I am not sure if I have modelled the problem correctly. Any help would be appreicated.

答:
Let the cake be a circle.

Suppose the entire circle is split up into n sectors, each making an angle $d\theta$ with the centre of the circle. Then the probability that Mike eats all of $\theta$ and up until somewhere within the small sector of the cake marked on the diagram as angle $d\theta$ is equal to $$\frac{d\theta}{2\pi}.$$

We need to calculate the probability that Jack eats > half the cake, given that Mike falls into a sector $d\theta$, and then do this for every sector $d\theta$ all the way round the circle.
This probability is

$$\approx \frac{\pi - \theta}{2\pi - \theta}\ \cdot \frac{d\theta}{\pi} \quad \text{ if }\ 0 < \theta < \pi,$$
$$\quad =0 \qquad \qquad \text{ if }\ \pi < \theta < 2\pi.$$

So $P(\ J$ eats $>$ half cake)

\begin{align} =\lim_{n \to \infty} \sum_{i=1}^{n}\frac{\pi - \theta_i}{2\pi - \theta_i} \cdot \frac{d\theta_i}{\pi} + \ 0 \\
\\
= \frac{1}{\pi}\int_0^\pi \frac{\pi - \theta}{2\pi - \theta}\ d\theta \\
\\
= \frac{1}{2\pi}\int_0^\pi 1 + \frac{\pi}{\theta - 2\pi}\ d\theta\\
\\
= \frac{1}{2\pi} \left(\ \pi + \pi \Bigl[ \ln \left|\theta - 2\pi\right| \Bigr]_0^\pi\ \right)\\
\\
= \frac{1 - \ln 2}{2}
\end{align}

Title: Eating cake probability problem


问:
Need an example of $C^*$-algebra where $GL(A_{sa})$ is dense in $A_{sa}$ while $GL(A)$ isn't dense in $A$.
$A_{sa}$ is the set of self-adjoint elements in $A$.

$GL(A)$ is the set of invertible elements in $A$ and $GL(A_{sa})$ is the set of invertible elements in $A_{sa}$.

I need an example where $GL(A_{sa})$ is dense in $A_{sa}$ while $GL(A)$ isn't dense in $A$, but I can't imagine which kind of $C^*$-algebra has such property.

An example where $GL(A)$ isn't dense in $A$ is $C([0,1]\times [0,1])$. And furthermore, when $X$ is a compact metrix space , $GL(C(X))$ is dense in $C(X)$ iff $\text{dim}(X)\leq 1$.

However, $GL(C(X)_{sa})$ is dense in $C(X)_{sa}$ iff $\text{dim}(X)=0$. So such kind of algebra doesn't have the property.

By the way, $GL(A_{sa})$ is dense in $A_{sa}$ iff every unitary $u\in U_0(A)$ can be approximated by unitary with finite spectrum. Don't know whether this would help. $U_0(A)$ is the group generated by elements like $e^{ia}$ with $a\in A_{sa}$.

答:
The Cuntz algebra $\mathcal O_n$ satisfies the desired conditions.

Firstly, $GL(\mathcal O_n)$ cannot be dense in $\mathcal O_n$ because this only happens in stably finite C$^*$-algebras.

Secondly, by [1, Corollary 4.7] one has that the real rank of $\mathcal O_n$ is zero which means that the self-adjoint invertibles are dense in the set of self-adjoint elements.

[1] Jeong, J. A.; Park, G. H.; Shin, D. Y., Stable rank and real rank of graph (C^ *)-algebras., Pac. J. Math. 200, No. 2, 331-343 (2001). ZBL1056.46050.


问:
km to m for probability density
If I have a density of $λ=30$ per $km^2$.

And a rectangular area that is $500$ m by $400$ m.

I need to find the probability distribution for $x$
(by multiplying the 3 numbers together)

But they are not in the same unit, the 'per square km' is really throwing me off.

答:
Well, one square kilometer is $1000000$ square meters. Know your unit conversion formulas.

By the way, since $500 * 400 = 200000$, the area is a fifth of a square kilometer.

Title: km to m for probability density


问:
How is Borel Cantelli Lemma being applied in this case?
I am taking a course in Probability Theory and in a proof, the professor made the following claim:

If for all $\epsilon>0$, the sum $\sum_{n\geq 1}P(|X_n-E[X_n]|> n\epsilon)<\infty$ then by Borel Cantelli Lemma $$\limsup_n \left|\frac{X_n}{n}-\frac{E[X_n]}{n}\right|\leq \epsilon\quad \text{P a.s.}$$

Here $X_n$ is some sequence of random variables assumed that are positive.

I am trying to understand how the inequality can be deduced from the Borel Cantelli Lemma. Here is my attempt.

If the sum is finite then $P(\limsup_n A_n) =0$ where $A_n$ is the event $A_n=\{\omega \in \Omega: |X_n(w)-E[X_n]| > n\epsilon \}.$ This implies that $P(\liminf A_n^c) = 1$ where $A_n^c= \{\omega \in \Omega: |X_n(w)-E[X_n]| \leq  n\epsilon \}.$ If we take $\omega \in \liminf A_n^c = \bigcup_{m\geq 1}\bigcap_{n\geq m}A_n^c$ then there is an $m\geq 1$ such that for all $n\geq m$ the $|\frac{X_n(\omega)}{n}-\frac{E[X_n]}{n}|\leq \epsilon$ and thus we can conclude that,

$$\limsup_n \left|\frac{X_n}{n}-\frac{E[X_n]}{n}\right|\leq \epsilon\quad \text{P a.s.}$$

Is this reasoning correct?

答: Yes your reasoning is correct, though you may be using more words than necessary.  For fixed $\epsilon>0$, Borel-Cantelli tells us that since the sum converges, a.s. only finitely many $n$ have $|X_n-E[X_n]|/n > \epsilon$. On this event, it is clear that the limsup is at most $\epsilon$. Taking a sequence $\epsilon_k \to 0$, on the intersection of all the a.s. events for $\epsilon_k$, it follows that $|X_n-E[X_n]|/n \to 0$, and hence the limit is $0$ a.s.


Title: km to m for probability density

Body:
If I have a density of $λ=30$ per $km^2$.

And a rectangular area that is $500$ m by $400$ m.

I need to find the probability distribution for $x$
(by multiplying the 3 numbers together)

But they are not in the same unit, the 'per square km' is really throwing me off.

Body:
Indeed,
$$30km^{-2} = \frac{30}{1000^2m^2} = \frac{30}{1000000m^2} = \frac{3}{100000m^2} = 0.00003m^{-2} = 3 \times 10^{-5}m^{-2}.$$


问:
How to find $1+\dfrac{1}{a_{1}}+\dfrac{1}{a_{2}}+\cdots+\dfrac{1}{a_{n}}$
Let $a_{i}>0,i=1,2,\cdots,n$,

If
$$1+\dfrac{1}{a_{1}}+\dfrac{1}{a_{2}}+\cdots+\dfrac{1}{a_{n}}\ge k\;\left(\dfrac{1}{\sqrt{1+a^2_{1}}}+\dfrac{1}{\sqrt{1+a^2_{1}+a^2_{2}}}+\cdots+\dfrac{1}{\sqrt{1+a^2_{1}+\cdots+a^2_{n}}}\right)$$

then find the maximum value for $k$

My idea was to use

$$\left(\sum_{i=1}^{n}\dfrac{1}{\sqrt{1+a^2_{1}+a^2_{2}+\cdots+a^2_{i}}}\right)^2\le\left[\sum_{i=1}^{n}\dfrac{a_{i}}{1+a^2_{1}+a^2_{2}+\cdots+a^2_{i}}\right]\left(\sum_{i=1}^{n}\dfrac{1}{a_{i}}\right)$$
and to use the approaches discussed here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=119163&sid=cd139cff36102a55e4f91a7c8dcd4f21#p119163

Alas! I failed to figure out how to do it.

Body:
Let's reduce the statements:

$$(1):\qquad 1+\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_n} \quad=\quad 1+\sum_{i = 1}^{n}\frac{1}{a_i}$$

$$(2):\qquad k\left( \frac{1}{\sqrt{1+{a_1}^2}}+...+\frac{1}{\sqrt{1+{a_1}^2+...+{a_n}^2}} \right) \quad=\quad k\left ( \sum_{i=1}^{n} \frac{1}{\sqrt{(1+\left( \sum_{j = 1}^{i}{{a_j}^2}\right )}}\right )$$

Now, with further reduction, you notice, as $(2)$ implies:

$$(3):\qquad k\left ( \sum_{i=1}^{n} \frac{1}{\sqrt{(1+\left( \sum_{j = 1}^{i}{{a_j}^2}\right )}}\right ) = \frac{k}{1-k}$$

and:

$$(4):\qquad 1+\sum_{i = 1}^{n}\frac{1}{a_i}\ge\frac{k}{1-k} \Rightarrow$$
$$(5):\qquad 1+\sum_{i = 1}^{n}\frac{1}{a_i} + \frac{k}{k-1}\ge0$$

Thus we have:

$$(6):\qquad 1+\sum_{i = 1}^{n}\frac{1}{a_i} \ge k\left ( \sum_{i=1}^{n} \frac{1}{\sqrt{(1+\left( \sum_{j = 1}^{i}{{a_j}^2}\right )}}\right ) \Rightarrow$$
$$1+\sum_{i = 1}^{n}\frac{1}{a_i} + \frac{k}{k-1}\ge0$$


问:
Central Limit Theorem without Measure Theory?
The standard route to proving the Central Limit Theorem is using Levys continuity theorem to show that the limit of characteristic functions $\phi_k(t)$ converging to some function $\phi(t)$ result in the sequence of random variables associated with those characteristic functions $X_k$ converge to $X$ where $X$ is a random variable and $E[e^{Xti}X] = \phi(t)$.

Is this result possible to prove without measure theory? Or at least a more limited result using restrictions on $X$?

In essence you would want to prove for a sequence of pdf $f_k(x)$ where $\int_{-\infty}^{\infty}f_k(x)e^{xti} = \phi_k(t)$ that if $\phi_k(t) \rightarrow \phi(t)$ that $f(x) =\mathcal{F}^{-1}\{\phi(t)\}$ is a valid pdf and $f_k(x)\rightarrow f(x)$.

For example I have seen proofs of the Fourier Transform inversion theorem without requiring DCT or Lebesgue Integral though even a more straightforward proof using DCT would be nice.

答:
If $X_1,...,X_n$ and $Y_1,...,Y_n$ are all independent meanzero, variance 1, then
by replacing only the last in the sum and for some three times differentiable
function $f$, by two Taylor expansions centered at $(X_1+...+X_{n-1})/\sqrt n$ you find
$$
|E[f(\frac{X_1+...+X_{n-1} + Y_n}{\sqrt n})] - E[f(\frac{X_1+...+X_{n-1} + X_n}{\sqrt n})] |
\le  \frac{\sup_{t\in R} |f'''(t)|}{n^{3/2}} E[|X_n|^3 + |Z_n|^3]
$$
because the zeroth, first, second order terms in the Taylor expansions cancel out
by independence.

Now if $X_1.,..,X_n$ are iid with some common meanzero, variance 1 distribution
and $Z_1,...,Z_n$ are iid $N(0,1)$ and we apply the above replacement to
transform $X_1.,..,X_n$ iteratively to $X_1,...,X_{n-1},Z_n$, then to
$X_1,...,X_{n-2},Z_{n-1},Z_n$, then to $X_1,...,X_{n-3},Z_{n-2},Z_{n-1},Z_n$ etc until having replaced all the $X_i$'s with $Z_i$'s, we accumulate $n$ times the error term above so that
$$
|E[f(\frac{X_1+...+X_{n-1} + X_n}{\sqrt n}) - E[f(Z)] |
\le  \frac{\sup_{t\in R} |f'''(t)|}{n^{1/2}} E[|X_1|^3 + |Z_1|^3]
$$
where $Z=(Z_1+...+Z_n)/\sqrt n$ has $N(0,1)$ distribution. At this point you have proved that $|E[f(\frac{X_1+...+X_n}{\sqrt n})] - E[f(Z)]|$ converges to 0 as $n\to+\infty$ when the third moment of $X_1$ is bounded for any function $f$ such that $\sup_{t\in R}|f'''(t)|$ is finite.

This proof does not give you the full generality of the CLT, but is quite approachable early in anyone's probability journey, requriring no measure theory background.

Reference: A User's Guide to Measure Theoretic Probability by David Pollard.


问:
Does such sequence exist?
In analysis course, my professor use a special sequence (in his notes) that I will mention below to prove a theorem.  I can't find any example of such a sequence. I will not bother to mention the full theorem (because I found another proof for it on the internet), but I only want to know does such a sequence $(a_n)$ with below properties exist in real numbers?

it should be bounded

$\limsup (a_n)=\sup_{n}a_n=1$

$\liminf (a_n)=\inf_{n}a_n=-1$

set of its sequential limit have exactly four elements.

I will appreciate if someone gives me an example.

答: Take four non-constant sequences $(x^{(k)}_n), k=0, 1, 2, 3$ that converges to $-1, -\dfrac13, \dfrac13, 1$ respectively. If you want you can impose fuhrer suitable constrains on them. Then take $a_n=x^{(k)}_n$ when $n\equiv k\mod{}4.$

Title: Does such sequence exist?


问:
Showing linear independence of a set
Let $A$ be a $3\times 3$ matrix with characteristic polynomial $p(x)=-x^3$ and suppose $w\in \Bbb R^3$ is a vector such that $A^2w\neq0$. I am supposed to show that $B=\{w,Aw,A^2w\}$ is a basis for $\Bbb R^3$.

To show that this set is linearly independent, $A^3w$ must be equal to $0$ but I cannot see why.

I am so sorry for this very easy question.

I appreciate any help

答:
The Cayley-Hamilton Theorem says that any matrix satisfies its characteristic polynomial; this means that $-A^3 = 0$ which implies $A^3 = 0$. This, of course, means that $A^3w=0$.

If $aw + bAw + cA^2w =0$, then applying $A^2$ to both sides we obtain $aA^2w= 0$. Since $A^2w\neq0$, this means $a=0$. Now replacing $a$ by zero and applying $A$ to both sides of the original equation (which is now $bAw + cA^2w=0$) we get $bA^2w=0$, which again implies $b=0$. Then you're left with $cA^2w=0$ which implies $c=0$. Thus $a=b=c=0$ and the set is linearly independent.

If you're not allowed to use Cayley-Hamilton, by definition of $A$ you know that all eigenvalues of $A$ are zero. This post can show you how to prove that $A^3=0$ from this information, but it requires you to know about Jordan normal form. Otherwise, I know of no other ways to show that $A^3=0$ (besides potentially directly, using the fact that you know both the trace and determinant of $A$ are zero (the cofficient of $x^2$ and the constant term in the characteristic polynomial are both zero!), but this seems like an algebra nightmare), and perhaps someone else has a solution without using Cayley-Hamilton/canonical forms.

Title: Showing linear independence of a set


问:
Why is $\Bbb Z_3$ cyclic?
I want to prove that $\Bbb Z_3$, defined as the only group of order $3$, is cyclic.

The identity element $e$ needs to be there, so $\Bbb Z_3=\{a,b,e\}$. Now, $ab$ can't be nor $a$ or $b$, otherwise one of them would be $e$, so $ab=e \implies b=a^{-1}$. Now, the next step would be proving that $a^2=a^{-1}$, but why is that necessary? Couldn't the multiplication table be like this? $$ab=ba=e, \quad a^2=a, \quad ({a^{-1}})^2=a^{-1}$$

答:
Are you asking why we must prove it?  Or why it must be true.

Why we must prove it:  We need to prove any 3 element group is cyclic.  that means there is an element $a \ne e$ and the three elements are precisely $e,a$ and $a^2$.

So if you have that the elements are $e,a, a^{-1}$ you haven't proven that yet.  You have to prove the third element is $a^2$.  It's not enough to prove it is $a^{-1}$.

that's why you have to prove it.

Why must it be true:  Well, .... that's what you have to prove, isn't it?

You ask if $a^2 = a$ isn't possible.  $a^2 = \color{red}a\color{blue}a \ne \color{red}a$ for the exact  same reason $\color{red}a\color{blue}b \ne \color{red}a$.

.... which come to think of it you didn't give a good reason.

$e$ is the identity element but there is nothing in the definition of a group that says that $e$ is the only identity, nor does it mean if $ab = b$ that $a=e$.  Maybe there are two elements $e$ and $a$ where $ab=b$ and $eb=b$

But note that  if $ab = a$ then $a^{-1}ab= a^{-1}a$.  But $a^{-1}ab = eb =b$ and $a^{-1}a = e$ so that can only happen if $b=e$.

Likewise if $a^2 = a$ then $a^{-1}a^2 = a^{-1}a$.  But $a^{-1}a^2 = a^{-1}aa =ea =a$ and $a^{-1}a = e$ so $a^2 = a\implies a = e$.  (That's true for all groups).

Title: Why is $\Bbb Z_3$ cyclic?


问:
Calculate the probability for the total insurance benefit -- solution verification

A family buys two policies from the same insurance company. Losses under the two policies are independent and have continuous uniform distributions on the interval from $0$ to $10$. One policy has a deductible of $1$ and the other has a deductible of $2$. The family experiences exactly one loss under each policy. Calculate the probability that the total benefit paid to the family does not exceed $5$.

This question has been discussed here and here. I've read them both but couldn't figure out why my solution is incorrect based on those discussions.

My attempt:
Let $P$ denote the loss amount under the first policy and let $Q$ denote that under the second policy. Let $X$ denote the benefits received under the first policy and let $Y$ denote that under the second policy. Then $f(p) = \frac{1}{10}$ when $0\le p\le 10$ and $f(q) = \frac{1}{10}$ when $0\le q\le 10$ and it follows that $f(p, q) = \dfrac{1}{100}$ when $0\le p, q\le 10$. Also,

$$X =
\begin{cases}
0 & 0\le P<1\\
P-1 & 1\le P\le 10
\end{cases}$$

$$Y =
\begin{cases}
0 & 0\le Q<2\\
Q-2 & 2\le Q\le 10
\end{cases}$$

We need to find $\Pr(X+Y\le 5 | X, Y>0)$. I am not sure what distributions $X$ and $Y$ follow (do they necessarily follow the uniform distribution?), so I tried to express the desired probability in terms of the variables whose joint distribution I derived.
$$\Pr(X+Y\le 5| X, Y>0)= \Pr(P+1+Q+2\le 5| P>1, Q>2) =\Pr(P+Q<8 | P>1, Q>2) $$
$$= \int_1^8 \int_2^{8-p} \frac{1}{100} \; \text{d}Q \, \text{d}P$$

This, however, did not lead to the correct response. Where have I gone wrong? Did I compute the conditional probability correctly? Should I divide $\int_1^8 \int_2^{8-p} \frac{1}{100} \; \text{d}Q \, \text{d}P$ by the product of the marginal distributions of $P$ and $Q$?

答:
The deductibles mean that payout distributions are mixtures of a discrete value at $0$ and
a continuous value up to $9$ or $8.$ So you have to be careful finding the
distribution of the sum. The following simulation in R is not a solution, but
it may help you to find the correct solution (or to see mistakes in an incorrect one). With a million iterations of such families, you can expect
two (maybe three) place accuracies for probabilities approximated by simulation.

```<code>set.seed(107)
L1 = runif(10^6, -1, 9);  L2 = runif(10^6, -2, 8)
x = L1;  x[L1 < 0]=0
summary(x)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  0.000   1.500   4.004   4.052   6.506   9.000
mean(x==0)
[1] 0.099936      # aprx P(X = 0) = 0.1

y = L2;  y[L2 < 0]=0  # 0 payout if below deductible
summary(y)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
 0.0000  0.4955  3.0001  3.2007  5.5062  8.0000
mean(y==0)
[1] 0.200588      # aprx P(Y = 0) = 0.2

t = x + y
summary(t)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  0.000   4.417   7.250   7.253   9.932  16.987
mean(t <= 5)
[1] 0.294548      # aprx P(T <= 5)
2*sd(t <=5)/1000
[1] 0.0009116791  # 95% margin of sim error in above
</code>```

Because of the possibility of $0$ payouts for one or both policies,
histograms (below) have to be interpreted with care.

```<code>par(mfrow=c(1,3))
 hist(x, prob=T, br=50, ylim=c(0,1.2), col="wheat", main="First Policy")
 hist(y, prob=T, br=50, ylim=c(0,1.2), col="wheat", main="Second Policy")
 hist(t, prob=T, br=50, col="skyblue2", main="Sum of Two")
  abline(v=5, col="red", lwd=2)
par(mfrow=c(1,1))
</code>```

Body:
The deductibles mean that payout distributions are mixtures of a discrete value at $0$ and
a continuous value up to $9$ or $8.$ So you have to be careful finding the
distribution of the sum. The following simulation in R is not a solution, but
it may help you to find the correct solution (or to see mistakes in an incorrect one). With a million iterations of such families, you can expect
two (maybe three) place accuracies for probabilities approximated by simulation.

set.seed(107)
L1 = runif(10^6, -1, 9);  L2 = runif(10^6, -2, 8)
x = L1;  x[L1 < 0]=0
summary(x)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  0.000   1.500   4.004   4.052   6.506   9.000
mean(x==0)
[1] 0.099936      # aprx P(X = 0) = 0.1

y = L2;  y[L2 < 0]=0  # 0 payout if below deductible
summary(y)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
 0.0000  0.4955  3.0001  3.2007  5.5062  8.0000
mean(y==0)
[1] 0.200588      # aprx P(Y = 0) = 0.2

t = x + y
summary(t)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  0.000   4.417   7.250   7.253   9.932  16.987
mean(t <= 5)
[1] 0.294548      # aprx P(T <= 5)
2*sd(t <=5)/1000
[1] 0.0009116791  # 95% margin of sim error in above

Because of the possibility of $0$ payouts for one or both policies,
histograms (below) have to be interpreted with care.

par(mfrow=c(1,3))
 hist(x, prob=T, br=50, ylim=c(0,1.2), col="wheat", main="First Policy")
 hist(y, prob=T, br=50, ylim=c(0,1.2), col="wheat", main="Second Policy")
 hist(t, prob=T, br=50, col="skyblue2", main="Sum of Two")
  abline(v=5, col="red", lwd=2)
par(mfrow=c(1,1))


问:
Derivation of formula for square of scalar triple product in terms of determinant of dot products
Can anyone provide or link me to a derivation of

$$ (\mathbf{a} \times \mathbf{b} \cdot \mathbf{c})^2 = \begin{vmatrix}
\mathbf{a \cdot a} & \mathbf{a \cdot b} & \mathbf{a\cdot c}\\
\mathbf{b\cdot a} & \mathbf{b\cdot b} & \mathbf{b\cdot c}\\
\mathbf{c \cdot a} & \mathbf{c \cdot b} & \mathbf{c \cdot c}
\end{vmatrix} $$

Preferably without using anything more advanced than the various identities for triple products, determinants and matrices.

答: Let  $E$ be the $3\times 3$ matrix $\left[\begin{matrix}\mathbf{a} \\ \mathbf{b} \\ \mathbf{c}  \end{matrix}\right].$ It is well known that $(\mathbf{a} \times \mathbf{b}) \cdot \mathbf{c} = |E|.$ Therefore, $((\mathbf{a} \times \mathbf{b}) \cdot \mathbf{c})^2=|E|^2=|EE^T|=$ your RHS.


问:
The diophantine equation $5\times 2^{x-4}=3^y-1$
I have this question: can we deduce directly using the Catalan conjecture that the equation
 $$5\times 2^{x-4}-3^y=-1$$
has or no  solutions, or I must look for a method to solve it. Thank you.</p>

答:
Solving for $y$ yields no solutions for $-3000\le x \le 3000$ but solving for $x$ does. WolframAlpha has a solution of $x$ in terms of $y$ here and plugging this into a spreadsheet does yield one solution in this range.
$$5\times 2^{x-4}-3^y+1=0\implies
x = \frac{\log(\frac{16(3^y - 1)}{5})}{\log(2)}\implies x=8\land y=4$$