问:
Paradox: increasing sequence that goes to $0$?
It is $10$ o'clock, and I have a box.

Inside the box is a ball marked $1$.

At $10$:$30$, I will remove the ball marked $1$, and add two balls, labeled $2$ and $3$.

At $10$:$45$, I will remove the balls labeled $2$ and $3$, and add $4$ balls, marked $4$, $5$, $6$, and $7$.

$7.5$ minutes before $11$, I will remove the balls labeled $4$, $5$, and $6$, and add $8$ balls, labeled $8$, $9$, $10$, $11$, $12$, $13$, $14$, and $15$.

This pattern continues.

Each time I reach the halfway point between my previous action and $11$ o'clock, I add some balls, and remove some other balls. Each time I remove one more ball than I removed last time, but add twice as many balls as I added last time.

The result is that as it gets closer and closer to $11$, the number of balls in the box continues to increase. Yet every ball that I put in was eventually removed.

So just how many balls will be in the box when the clock strikes $11$?

$0$, or infinitely many?

What's going on here?

答:
If we want to try and pattern this surreal world to mathematical analysis, then it seem we are discussing limits.

The standard mathematical definition of limit of a sequence is well defined (or so I have been led to believe). Meanwhile, the question posed is ambiguous within this context of such limit definition; however, if we infer some sequences from the question, none of these sequences have limits.

A sequence does not have a limit unless at every step beyond some point we are guaranteed to fall within a bounded nearness to the alleged limit point.

For this question, we have the option to call each step the result of the subtractions and the additions together. In this case, we see that at every step we are increasing the size and never decreasing it. We can't argue in this case that all balls added get removed because the addition and subtraction happened at one step, so they are indivisible.

Alternatively, we can label each subtraction and each addition as a distinct step, but, then, to claim a limit exists as per traditional limit analysis, it must be true that at every step we remain within some small arbitrarily small bound (ie, beyond some step N, at each and every single step, the distance to the limit is always less than some epsilon). If we use this interpretation of the question, then we get a sequence that oscillates and deviates way off the alleged limit of zero. There is no limit point.

Alternatively, we can call one step the subtractions taken together and another the additions taken together. We can instead call the first x subtractions a step and .... No matter what path we take, if the over-riding truth is that there is a step at which we have a very large value (note that the additions came after the subtractions.. despite the ambiguities), then we cannot argue with accepted traditional mathematical analysis limit definition that zero is the limit.

To finish by returning to one point in the question, you can't say that every ball is eventually removed if you simultaneously are adding more balls afterward or at the same exact point in time.. any more than I can say that 10 is not really 10 but is instead -100 + 110 and when it becomes 11 we first remove the 110 we had, then add in 121 (or whatever the pattern is that you like). .. You can say it, but that is not a very useful way to reason about infinity (and as far as I can tell, no such 11 o'clock world exists.. so this is just a model).

If we assume that it's also a true statement that all balls were removed, then perhaps it's also true (though not stated in the question) that every ball removed was added back! Or that every ball removed and added back was then removed!! What kind of reality are we describing here?

A lesson is that mathematicians have adopted certain fairly precise ways of thinking about and reasoning about infinities (such as the limit definition) which they have found to be useful in constructing and analyzing models that are useful in the reality that we (or at least I) live in.

[There are models that lead to crazy results, as this "conversation" is demonstrating.]

Given that I don't have enough points to comment in the proper place, let me add some comments here.

@Niel de Beaudrap, you said, "what matters is the set of balls which are at some point added, and then never removed". Why is this what matters? And also, how did you go from saying that the limit of these sets had infinite elements to just declaring the limit had 0 at the very end? For example, that the intersection of "parents" of those individuals in a particular room is the empty set isn't going to be the reason why when that room is blown up that there will be 0 live humans left. In other words, there are many sets that have empty set intersections and you can simultaneously make many other declarations that are totally unrelated to this intersection. So I don't see why you think that 0 intersection means anything special here.

@Nate Eldredge, "But since every ball has been removed, B(11)=0... indeed it is not [continuous]." Unless "every" ball does not mean the full exhaustion of balls that exist at the very end but instead only means "every" ball as we neared the end.


问:
Proving the product of two real numbers is maximum when the numbers are equal given their sum is constant
Let us consider two real numbers $x$ and $y$. How can we prove value of $xy$ is greatest when $x=y$ given the condition $x+y=$ constant?

I have already found a proof, but I am not entirely happy with it yet.

答:
$(x-y)^2\geqslant0
\Rightarrow (x^2+y^2)/2 \geqslant xy \Rightarrow (x+y)^2/4\geqslant xy$</p>

ContentLicense: CC BY-SA 3.0


问:
Finding a unit in $\mathcal{O}_{\mathbb{Q}(\theta)}$ where $\theta$ is the root of a particular monic polynomial
The notes of a module I'm doing has an example I don't quite understand.

If $\theta$ is the root of $t^3-4t+2$, then $2\theta-1$ is a unit of $\mathcal{O}_{\mathbb{Q}(\theta)}$.
First note that $2\theta-1$ is a root of the monic integer polynomial $\frac{1}{8} \left[(t+1)^3-4(4(t+1))+16\right]=t^3+3t^2-13t+1$.

How did they find the polynomial above? I understand why they did it (the $+1$ in the end is useful later one to determine $2\theta -1$ is indeed a unit).

Could you please explain? thanks in advance.

答:
Short answer: that comes out from trying to get a $\pm 1$ as the constant term.

The general $y=a\theta^2+b\theta+c\in\mathbb{Z}[\theta]\subset\mathbb{Q}(\theta)$ has minimal polynomial
$$
y^3
- (3 c + 8 a) y^2
+ (16 a^2 + 6 a b + 16 a c - 4 b^2 + 3 c^2) y
- (4 a^3 + 8 a^2 b + 16 a^2 c + 6 a b c + 8 a c^2 - 2 b^3 - 4 b^2 c + c^3)
$$
So you want, for a unit,
$$
-4 a^3 - 8 a^2 b - 16 a^2 c - 6 a b c - 8 a c^2 + 2 b^3 + 4 b^2 c - c^3 = \pm 1
$$

For simplicity try $a=0$ and by switching signs we can assume RHS is $1$:
$$
2 b^3 + 4 b^2 c - c^3 = 1
$$
so $(a,b,c)=(0,2,-1)$ is a choice, as are $(0,-1,1)$, $(0,-1,-1)$ or $(0,-3,5)$ (and of course $(a,b,c)=(0,0,-1)$ which is trivial).  I think they are all the solutions with $a=0$ but haven't checked it.

ContentLicense: CC BY-SA 4.0


问:
Upper density, and nested sets
For a given $A \in \mathbb{N}$, we define the upper desnity $\bar d(A)$ by
\begin{equation*}
\bar d(A) = \limsup_{N \to \infty} \frac{A \cap [N]}{N}
\end{equation*}
where $[N]$ denotes the set $\{1,2,\dots, N\}$. My question is, if we have a sequence of sets
\begin{equation*}
A_1 \supseteq A_2 \supseteq \dots \supseteq A_n \supseteq \dots
\end{equation*}
such that
\begin{equation*}
\bigcap_{n \geq 1} A_n = \varnothing
\end{equation*}
then do we we have
\begin{equation*}
\liminf_{n \to \infty} \bar d(A_n) = 0
\end{equation*}
I'm not sure if this is obvious or not. I was thinking that a way to prove this statement is to first define $\frac{1}{2} A_1 \subseteq \mathbb{N}$ to be such that it includes every other element of $A_1$. Then we would have $\bar d(\frac{1}{2} A_1) = \frac{1}{2} \bar d(A_1)$, and there is an $m \in \mathbb{N}$ such that $A_m \subseteq \frac{1}{2} A_1$, so $\bar d(A_m) \leq \frac{1}{2} \bar d(A_1) \leq \frac{1}{2}$. Carrying on like this we get a subsequence which decays as $\frac{1}{2^k}$ which implies the claim. This argument does feel a bit fishy to me though.

答: No.  $A_n=\mathbb{N}-[n]$ is a counterexample.  There is no reason why $A_m$ must be a subset of your $\frac12A_1$.

Title: Upper density, and nested sets


问:
An interesting ODE
I've been thinking about approaches to solve

$$\frac{\textrm{d}^{3}y}{\textrm{d}x^{3}}=\textrm{e}^{-y(x)}.$$

My initial thought was to set $y(x)=\ln(z(x))$ in order to obtain an ODE relating $z$ to $x$. However, this in fact makes things much worse (or at least much messier).

Any insights much appreciated.

Thanks

答:
Your equation is autonomous. The standard method is to let $u(y)=y'(x)$, then carefully writing out the equation we have

$$
u(u')^2+u^2 u''=e^{-y}
$$

Now $y$ is the independent variable. A particular solution is $u_p=\left( \frac{9}{2} \right)^{1/3}e^{-y/3}$, letting $u=u_p+v$ just produces another awful nonlinear equation for $v$. At least we have one solution to the original equation: $y_p(x)=3 \ln(x-c_1)+\ln(6)$. In the absence of some clever integrating factor trick, we can look at perturbative solutions

$$
y'''=\varepsilon e^{- y}
$$

When $\varepsilon=0$, we have $y_0(x)=Ax^2+Bx+C$. With the ansatz

$$
y(x)=\sum\limits_{n=0}^\infty y_n(x)\varepsilon^n
$$

Choosing $y(0)=1, \ y'(0)=-1, \ y''(0)=0$, we have $y_0=1-x$, and we can find the next term by matching powers of $\varepsilon^\dagger$

$$
y_1'''=e^{-y_0}=e^{-1+x}
$$

Which is easily integrated

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

Here is a plot of the numerical integration and the two term series $y_0+y_1$:

$\dagger$ To get the higher order terms, you'd want a systematic way of getting down the right coefficients of $\varepsilon$ from $\sum_n y_n \varepsilon^n$ that's in the exponential. For example, at the next order, when equating $\varepsilon^2$ terms, we have on the right

$$
\varepsilon e^{-y_0-\varepsilon y_1 - \dots}=\varepsilon e^{-y_0} e^{-\varepsilon y_1} \dots =\varepsilon e^{-y_0}(1-\varepsilon y_1) \dots
$$

So that the $\varepsilon^2$ coefficient on the right is $-y_1 e^{-y_0}$, and the next term in our perturbation series is given by solving

$$
y_2'''=-y_1 e^{-y_0}
$$

Update: while I do not have a closed form for the coefficients of $\varepsilon^n$, they can be found diagrammatically, as they are in correspondence with the integer partitions of $n$, or equivalently the Young diagrams of $n$ blocks. Consider

$$
e^{-\sum \varepsilon^n y_n}=e^{-y_0} e^{-\varepsilon y_1} e^{-\varepsilon^2 y_2} e^{-\varepsilon^3 y_3}  \dots \\
=e^{-y_0}\left(1-\varepsilon y_1 + \frac{\varepsilon^2 y_1^2}{2} \dots \right) \left(1-\varepsilon^2 y_2 + \frac{\varepsilon^4 y_2^2}{2} \dots \right)\left(1-\varepsilon^3 y_3 + \frac{\varepsilon^6 y_3^2}{2} \dots \right)\dots
$$

The coefficient of $\varepsilon^n$ (from the exponential, excluding the single factor outside the exponential) will be given by all the ways in which expanding the parentheses out can produce $\varepsilon^n$. For example, the coefficients of $\varepsilon^4$ would be represented by the diagrams of four blocks:

Where I'm letting a column of length $n$ = one factor of $y_n$. Thus the fifth order equation reads

$$
y_5'''=e^{-y_0} \left( \frac{(-y_1)^4}{4!} + (-y_2) \frac{(-y_1)^2}{2!} +\frac{(-y_2)^2}{2!} + (-y_3)(-y_1) +(-y_4) \right)
$$

In this way you may generate the solution to any order. The expressions become too cumbersome to type here, but Mathematica has no trouble solving them. Here is a plot:

Since this is a perturbation series, the most we can hope for is that series is asymptotic. If you wished to take this further, note that after you have the $N$th order solution $y_N$, you have a sum of finitely many known terms

$$
y=\sum\limits_{n=0}^N \varepsilon^n y_n
$$

Then you could consider various methods of re-summing this series in $\varepsilon$. You could also investigate slightly different perturbation problems, eg: $y'''=e^{-\varepsilon y}$. I've tried the perturbation ansatz on the differential equation for $u(y)$, but that leads to more intractable differential equations at orders beyond first.

Title: An interesting ODE


答: As a counterexample, how about $A_n=\Bbb N \setminus[n]$?

Title: Upper density, and nested sets

Body:
For a given $A \in \mathbb{N}$, we define the upper desnity $\bar d(A)$ by
\begin{equation*}
\bar d(A) = \limsup_{N \to \infty} \frac{A \cap [N]}{N}
\end{equation*}
where $[N]$ denotes the set $\{1,2,\dots, N\}$. My question is, if we have a sequence of sets
\begin{equation*}
A_1 \supseteq A_2 \supseteq \dots \supseteq A_n \supseteq \dots
\end{equation*}
such that
\begin{equation*}
\bigcap_{n \geq 1} A_n = \varnothing
\end{equation*}
then do we we have
\begin{equation*}
\liminf_{n \to \infty} \bar d(A_n) = 0
\end{equation*}
I'm not sure if this is obvious or not. I was thinking that a way to prove this statement is to first define $\frac{1}{2} A_1 \subseteq \mathbb{N}$ to be such that it includes every other element of $A_1$. Then we would have $\bar d(\frac{1}{2} A_1) = \frac{1}{2} \bar d(A_1)$, and there is an $m \in \mathbb{N}$ such that $A_m \subseteq \frac{1}{2} A_1$, so $\bar d(A_m) \leq \frac{1}{2} \bar d(A_1) \leq \frac{1}{2}$. Carrying on like this we get a subsequence which decays as $\frac{1}{2^k}$ which implies the claim. This argument does feel a bit fishy to me though.


问:
Show that the area vectors for a general $n$-sided closed shape sum to zero
It is possible to show that the sum of the area vectors for a general, closed, $n$-sided figure in $\mathbb{R}^3$ (3-space) is zero.

Hint: it may be easiest to consider orientable and non-orientable surfaces separately.

答: The dot product between an area vector and an arbitrary unit length direction vector $n$ is proportional to the area you obtain by projecting the area onto a plane orthogonal to $n$. So now consider your whole closed shape projected onto that plane. For every point in the plane, you can examine the ray originating from that point an in direction $n$. That ray must intersect the faces of the shape an equal number of times, half of them coming into the shape and half going out of it. So these whill exactly cancel, and the net effect is that there is no contribution of these areas to the point from which your ray originated. Since the same argument holds for all points (with some care for those intersecting edges, vertices and so on), you can tell that there will be no net contribution to any point of the projection. So the sum of the projected area vectors has to be zero. Since this is trie for every possible choice of $n$, you can tell that the sum of area vectors has to be zero, since the sum of dot products equals the dot product with the sum, and the only vector which has zero dot product with every unit-length vector is the zero vector.


问:
What's wrong in this inductive proof?
Let $a$ be any positive integer. If $x$ and $y$ are positive integers such that $max(x, y) = a$, then we know that $x = y$.

I'm pretty sure this is a false claim, and I need to find what is wrong with the induction proof.

For the base case, we let $a = 1$. Here, if $x$ and $y$ are positive integers such that $max(x, y) = 1$, then $x$ and $y$ must both be $1$.

In the inductive case, we let $k$ be some arbitrary positive integer. The induction hypothesis assumes that if $x$ and $y$ are positive integers such that $max(x, y) = k$, then $x = y$ for some positive integer $k$.

Consider the case where $a = k + 1$ and let $x'$ and $y'$ be two positive integers such that $max(x', y') = k + 1$. Now we have $max(x' - 1, y' - 1) = k$, which, by the induction hypothesis, implies that $x' - 1 = y' - 1$, and therefore that $x' = y'$. Thus, we have proven the claim.

I can identify just one counterexample: if $a = 20, x = 10, y = 20$. Then, $max(10, 20) = 20$, but $20 \neq 10$.

答:
" a=k+1 and let x′ and y′ be two positive integers such that max(x′,y′)=k+1. Now we have max(x′−1,y′−1)=k,"-1$

But $x'-1$ or $y'-1$ need not be a positive integer.

Title: What's wrong in this inductive proof?


问:
Validity of a complete residue system statement.
In my number theory book there is a theorem says:

If $C$ is a complete residue system modulo $n$, $a \in \mathbb Z$ and $\gcd(a,n)=1$, So $D=\{ax+b \mid x\in C\}$ is a complete residue system modulo $n$, $\forall b\in \mathbb Z$.

My counterexample:

Let’s work mod $3$
$$C=\{0,1,2\}$$
and let $a=4$ so $\gcd(3,4)=1$ And the theorem says $\forall b\in \mathbb Z$, so we get($x=2\in C$): $$D=\{4\cdot2+0, 4\cdot2+1, 4\cdot 2+4\}=\{8,9,12\}$$
But this clearly not a comple Residue system mod $3$

Either this is a False statement (at least in a part of it) or my counterexample is False.

答:
$D = \{ax+b|x\in C\}$ is set builder notation. It means all elements of the form $ax+b$ where $x$ ranges over the elements in $C$.

This is similar to the set builder notation for the set of squares for example:
$\{x^2|x\in \mathbb{Z}\}$

To give a concrete example, let $C=\{0, 1, 2\}$ and $a=2, b=1$ then this notation becomes:
$D = \{2x+1|x\in\{0, 1, 2\}\} = \{2\cdot0+1, 2\cdot1+1, 2\cdot2+1\} = \{1, 3, 5\}$.

To prove the fact that $D$ is a complete residue system is easy. We know $\gcd(a, n)=1$ so $a$ is a unit modulo $n$. Take an multiplicative inverse $a^{-1}$ of $a$ modulo $n$. For $D$ to be a complete residue system, take any $r\in \mathbb{Z}$, we will find an $x\in C$ such that $ax+b\equiv r \mod n$. The $x$ that works is the element in $C$ congruent to $a^{-1}(r-b)$.


问:
If $p$ prime $>3$ and $a$ primitive root modulo $p$, so $-a$ is that too iff $p\equiv 1\pmod 4$
Let $p>3$ be prime, let $a$ be a primitive root modulo $p$. Show that $-a$ is a primitive root modulo $p$ if and only if $p\equiv 1\pmod 4$.

We have $a^{\phi(p)/2}\equiv -1\pmod p$, so $-a=(-1)a\equiv a^{\phi(p)/2+1}\pmod p$. Then
$$
\operatorname{ord}(-a,p)=\frac{\operatorname{ord}(a,p)}{\gcd\{\phi(p)/2+1,\operatorname{ord}(a,p)\}}=\frac{p-1}{\gcd\{(p+1)/2,p-1\}}.
$$
Want find those $p$ so that $\operatorname{ord}(-a,p)=\phi(p)$. Therefore, we only want to show that
$$
\gcd\{(p+1)/2,p-1\}=1\iff p\equiv 1 \pmod 4.
$$
The direction $\impliedby$ is straightforward. I'm struggling with the other direction.

答:
Let $\langle g\rangle=\Bbb Z_p^\times$. We have $p\equiv_4 1\iff -1\equiv_p g^{2k}$, where $4k=p-1$. Now consider $\langle -g\rangle$.

If $p\equiv_4 1$ then $\langle -g\rangle\cong \langle g^{2k+1}\rangle$, this group is isomorphic to $\Bbb Z_p^\times$. To see this, consider the homomorphism $$\phi:\Bbb Z_p^\times\rightarrow\Bbb Z_p^\times\\g\mapsto g^{2k+1}$$ Then $\phi(g^m)=g^{m(2k+1)}=e$. Using some algebra: $$g^{2mk}g^m=e\\\Rightarrow g^{2m}=e\tag{squaring both sides}$$ This gives that $g^{m(2k+1)}=g^m=e$, so the kernel is trivial and $\phi$ is an isomorphism.

If $p\equiv_4 3$ then $\langle -g\rangle\cong\langle g^{2k}\rangle$. This group generates nothing but the squares in $\Bbb Z_p^\times$, so $\langle -g\rangle\subset\Bbb Z_p^\times$.


问:
How to evaluate the continued fraction $[1,2,3,1,4,1,4,1,4\dots]$

How does one evaluate the continued fraction $[1,2,3,1,4,1,4,1,4...]$?

My attempt

Take

$$y=[1,4,1,4,1,4\dots]={1+\frac{1}{4+\frac{1}{y}}}$$

so that $$4y^2-4y-1=0\quad\text{and}\quad y=\frac{\left(1+\sqrt{2}\right)}{2}$$

which becomes

$$x=1+2+3+\frac{1}{y}=6+\frac{\left(1+\sqrt{2}\right)}{2}=4+2\sqrt{2}$$

Is this right?

Body:
You have correctly found the value of $y = [1;4,1,4,1,4,\cdots]$ (Noting that I have used a semicolon after the first $1$ and not a comma). To finish, you just need to note that

\begin{equation}
\begin{array}{rcl}
[1;2,3,1,4,1,4,1,4\cdots] & = & 1+\frac{1}{2+\frac{1}{3+\frac{1}{[1;4,1,4,1,4,\cdots]}}}\\
& = & 1+\frac{1}{2+\frac{1}{3+\frac{1}{\frac{1+\sqrt{2}}{2}}}}\\
& = & 1+\frac{1}{2+\frac{1}{3+\frac{2}{1+\sqrt{2}}}}\\
& = & 1+\frac{1}{2+\frac{1+\sqrt{2}}{3(1+\sqrt{2})+2}}\\
& = & 1+\frac{1}{2+\frac{1+\sqrt{2}}{5+3\sqrt{2}}}\\
& = & 1+\frac{5+3\sqrt{2}}{2(5+3\sqrt{2})+1+\sqrt{2}}\\
& = & 1+\frac{5+3\sqrt{2}}{11+7\sqrt{2}}\\
& = & \boxed{\frac{16+10\sqrt{2}}{11+7\sqrt{2}}}\\
\end{array}
\end{equation}


答: The problem is that $x'-1$ and $y'-1$ might not both be positive integers (since one of $x',y'$ might be 1), so the induction hypothesis doesn't apply.

Title: What's wrong in this inductive proof?

Body:
Let $a$ be any positive integer. If $x$ and $y$ are positive integers such that $max(x, y) = a$, then we know that $x = y$.

I'm pretty sure this is a false claim, and I need to find what is wrong with the induction proof.

For the base case, we let $a = 1$. Here, if $x$ and $y$ are positive integers such that $max(x, y) = 1$, then $x$ and $y$ must both be $1$.

In the inductive case, we let $k$ be some arbitrary positive integer. The induction hypothesis assumes that if $x$ and $y$ are positive integers such that $max(x, y) = k$, then $x = y$ for some positive integer $k$.

Consider the case where $a = k + 1$ and let $x'$ and $y'$ be two positive integers such that $max(x', y') = k + 1$. Now we have $max(x' - 1, y' - 1) = k$, which, by the induction hypothesis, implies that $x' - 1 = y' - 1$, and therefore that $x' = y'$. Thus, we have proven the claim.

I can identify just one counterexample: if $a = 20, x = 10, y = 20$. Then, $max(10, 20) = 20$, but $20 \neq 10$.


问:
Does $x^T(M+M^T)x \geq 0 \implies x^TMx \geq 0$ hold in only one direction?
I know this is true for the "if" part, but what about the "only if"?

Can you give me one example when the "only if" part does not hold? I am not quite sure about this.

I forgot to tell you that $M$ is real and $x$ arbitrary.

答:
Well

$x^{T}Mx \geq 0 \implies x^{T}M^{T}x \geq 0$ (by taking transpose)

Hence, $x^{T}(M^{T} + M)x \geq 0$.

So, this gives you the one side. However, you wrote the converse in your title.


问:
Constructing a model of non-negative integers $\mathbb{N}$
I am attempting problem 3.43 of MIT's Discrete Mathematics text.

Let $\mathbf{\tilde0}$ be a constant symbol and next and prev be the successor ("+1") and predecessor("-1") total functions. The aim of this problem is to develop a series of predicate formulas using just the symbols $\mathbf{\tilde0}$, next and prev such that every model satisfying these formulas will contain a copy of the nonnegative integers  $\mathbb{N}$.

More precisely, the “copy” of $\mathbb{N}$ in a model will look like an infinite sequence of
distinct points starting with $e_0$ , with a next-arrow going from each point to the next point in the sequence so that next acts like plus one. We also want prev to act like minus one: whenever a next-arrow goes into an element e, then the prev-arrow out of e goes back to the beginning of the next-arrow.

Now prev($\mathbf{\tilde0}$) = $\mathbf{\tilde0}$, reflecting the convention
for nonnegative integers that subtracting from zero has no effect.

The predicate $$(1) \ \ \ \ \ \forall x.\ \mathbf{prev}(\mathbf{next}(x)) = x $$

formula (1) means that the prev-arrow out of any point $e$ goes back to the
beginning of any next-arrow into $e$. Of course this will not be possible if there is
more than one next-arrow into $e$.

There are some standard terms called numerals used to describe the elements
$e_0 , e_1...$ ; namely, the numeral for $e_0$ will be $\mathbf{\tilde0}$, and the numeral for $e_n$ will be the application n times of next to $\mathbf{\tilde0}$. For example, the numeral for three
would be:
$$\mathbf{\tilde3} = \mathbf{next(next(next(\tilde0)))}$$

(a) To make the interpretion $e_0$ of $\mathbf{\tilde0}$ behave like zero and to prevent formation of cycles in the model, write a predicate formula expressing the fact that the value of $\mathbf{\tilde0}$ is not plus-one of anything. Also, by convention, subtracting one from zero has no effect.

(b) Explain why two different numerals must have different values in any model
satisfying (1) and part (a).

It is worth seeing that the formula of part (a) together
with (1) do not ensure that their models consist solely of a copy of $\mathbb{N}$.
For example, a model might consist of two separate copies of $\mathbb{N}$.

(c) Write a formula such that any model has only one copy of $\mathbb{N}$, i.e. that there is only one zero-like element.

But the additional axiom of part (c) still leaves room for models that, besides
having a copy of $\mathbb{N}$, also have “extra stuff” with weird properties.

(d) Describe a model that satisfies the formula of part (c) along with (1), part (a)
and also satisfies

$$(d) \ \ \ \exists x. x = \mathbf{next(}x \mathbf{)} $$

I think the answer to part (a) is the predicate formula $$(a) \ \ \ \ \forall x. \mathbf{\tilde0} \neq \mathbf{next(}x \mathbf{)}$$

For part(b), if two different numerals $m, n$ had the same values in the model then, assuming $m>n$, that would imply that

$$(b) \ \ \ \underbrace{\mathbf{next \circ next\ \circ \ ... \ \circ \ next}}_{m-n\text{ times}}(\mathbf{\tilde0}) = \mathbf{\tilde0}.$$

which is false.

For part(c), to ensure only one zero-like element

$$(c) \ \ \ \mathbf {prev(}x\mathbf{)} = x \implies x = \mathbf{\tilde0}$$

I am having trouble with parts (b) and (d).

For (b) is my argument circular reasoning since I am assuming ordering of numerals? The text also mentions well-ordering property but I can't deduce how that would be applicable here.

Also for (d), if I assume $z$ such that $\mathbf{next(}z \mathbf{)} = z$, then from (1) and (c), $z = \mathbf{\tilde0}.$ which is false since (a). So what is the "weird-stuff" which can satisfy (1), (a), (c) and (d)?

My background is single-variable calculus and the first three chapters of the mentioned text.

答:
Part (a) asks for two things.  You have only provided the first of the two.  You have not addressed "Also, by convention, subtracting one from zero has no effect."

For part (b), you might benefit from introducing some notation.  For instance $\mathbf{next}^3(\mathbf{\tilde{0}}) = \mathbf{\tilde{3}}$.  Notice that the problem does not deny the existence of a $\Bbb{N}$ that you can use for this notation and to count applications of $\mathbf{next}$.  In fact, you are extracting properties from this $\Bbb{N}$ in an attempt to make a model of it, so it must exist and be available for use.  You also know that $\mathbf{next}$ is a well-defined function, so
$$ \mathbf{next}^{m-n} \circ \mathbf{next}^n(\mathbf{\tilde{0}}) = \mathbf{next}^m(0)$$
Additionally, you are given "whenever a next-arrow goes into an element $e$, then the prev-arrow out of $e$ goes back to the beginning of the next-arrow".  This says $\forall e. \mathbf{prev}(\mathbf{next}(e)) = e$.  Applying $\mathbf{prev}$ $n$-times to $\mathbf{next}^m(\mathbf{\tilde{0}}) = \mathbf{next}^n(\mathbf{\tilde{0}})$ yields $\mathbf{next}^{m-n}(\mathbf{\tilde{0}}) = \mathbf{\tilde{0}}$.  Since you have assumed $m > n$, you may write $\mathbf{next}(\mathbf{next}^{m-n-1}(\mathbf{\tilde{0}})) = \mathbf{\tilde{0}}$, using the convention that $\mathbf{next}^0$ is the identity function, to immediately get a contradiction to your statement in part (a) (by setting $x = \mathbf{next}^{m-n-1}(\mathbf{\tilde{0}})$).

In part (c), you need the part you haven't supplied to part (a).  You have a way to characterize $\mathbf{\tilde{0}}$ and you want to ensure that there is only one element in your model that has that property.

Well, a thing that would not violate the list of properties is an element $\mathbf{\tilde{\infty}}$ with the properties

$\mathbf{next}(\mathbf{\tilde{\infty}}) \neq \mathbf{\tilde{\infty}}$.  You say this violates (1) and (c), but those both require an application of $\mathbf{prev}$, which is not present here.

$\mathbf{prev}(\mathbf{\tilde{\infty}}) \neq \mathbf{\tilde{\infty}}$.  Informally, we are allowing ... $\infty + 2$, $\infty + 1$, $\infty$, $\infty - 1$, $\infty -2$, ... to be "extra stuff" in this model.
We've already ensured there is only one starting place for a sequence of points in the $\mathbf{next}$ direction, but we have not ensured there are no extra starting places for sequences of points in both directions.

The descending half of such bidirectional sequences need not be lower bounded.  If one is lower bounded, we have enforced that if its lower bound is $b$, satisfying, for some choice of $k \in \Bbb{N}$, $\mathbf{prev}^k(\mathbf{\tilde{\infty}}) = \mathbf{\tilde{b}}$ and $\mathbf{prev}(\mathbf{\tilde{b}}) = \mathbf{\tilde{b}}$, then it must be the case that $b = \mathbf{\tilde{0}}$.  (We have no requirement of the general shape $\mathbf{next} \circ \mathbf{prev}(x) = x$, so $\mathbf{\tilde{0}}$ is free to be the lower bound of any number of such sequences -- we descend from the chain to $\mathbf{\tilde{0}}$ then ascend to $\mathbf{\tilde{1}}$.)

For this specific type of problem, there is some opportunity for graphical help.  Suppose that we decide that numerals increase to the right, so except for self-loops any $\mathbf{next}$ arrow must point in the right half-space of its source and except for self-loops any $\mathbf{prev}$ arrow must point in the left half-space of its source.  Then, attending first to $\mathbf{next}$, we can have a fan-in of multiple points whose $\mathbf{next}$ is the point $e$ (only two are shown in the "fan", but there can be many more).  Two edges are dashed because either, but not both, can be present at any point.

Likewise, $\mathbf{prev}$ can fan-in and then proceed along the $\mathbf{prev}$ chain from $e$.

Then our various predicates cut down the number of options at each point.

(1) says "if you follow the red arrow from $e$ and the blue arrow from where you now are, you arrive back at $e$.  So either, there is an $f \neq e$ such that $\mathbf{next}(e) = f$ and $\mathbf{prev}(f) = e$, or $\mathbf{next}(e) = \mathbf{prev}(e) = e$.

Then we pick a distinguished point, labelled "$\mathbf{\tilde{0}}$" and notice the $\mathbf{next}$ chain starting from $\mathbf{\tilde{0}}$ could be a model of $\Bbb{N}$.  Then $\mathbf{\tilde{0}}$ is required to have no incoming red arrows.  So the red diagram around $\mathbf{\tilde{0}}$ has one arrow: $\mathbf{next}(\mathbf{\tilde{0}}) = \mathbf{\tilde{0}}$ or $\mathbf{next}(\mathbf{\tilde{0}}) \neq \mathbf{\tilde{0}}$.  Your answer to part (a) eliminates the first case, so there is a $\mathbf{next}$ chain starting at $\mathbf{\tilde{0}}$ (containing at least two distinct points: $\mathbf{\tilde{0}}$ and $\mathbf{next}(\mathbf{\tilde{0}})$).

Notice that we have made no restrictions affecting the blue diagram to reject or allow similar "starting points" for chains in the $\mathbf{prev}$ direction.  We get sort of close with the $\mathbf{prev}(\mathbf{next}(x))$ constraint, but this just says that for the points in the red fan-in of $e$, there is a distinguished one that is the target of hte blue arrow from e -- the real constraint here is that $\mathbf{prev}(e)$ is required to be one of the points having $e$ as its $\mathbf{next}$ (and not some other point that does not have $e$ as its $\mathbf{next}$).

By the time we get to part (d), we have that there are numerals, that the successor of a numeral, $n$, is not $n$, and that every point, whether a numeral or not has a successor.  (This last bit is part (d).)  So, at least the chain of numerals starting at $\mathbf{\tilde{0}}$ gives a model of $\Bbb{N}$, but there could be non-numerals.  A non-numeral point, $e$, ...

... has a $\mathbf{prev}$ and $\mathbf{prev}(e) \neq e$.  The $\mathbf{prev}$ of $e$ can be a numeral, even $\mathbf{\tilde{0}}$.

can be its own $\mathbf{next}$.  Nothing has prevented red self-loops.

could belong to a cyclic chain.  The minimal example of this is: let $f$ be a non-numeral point with $e \neq f$.  Then set \begin{align*}
\mathbf{next}(e) &= f  \text{,}  \\
\mathbf{next}(f) &= e  \text{,}  \\
\mathbf{prev}(e) &= f  \text{, and}  \\
\mathbf{prev}(f) &= e  \text{.}
\end{align*}
That is, there can be more "weird stuff" than just chains descending from upper fixed points.

Notice that this set of arrows cannot be implemented using our convention for arrows going to the right or left.  Go back and re-read the setup for that : we made that choice to follow the model of $\Bbb{N}$ given by the numeral points.  We are talking about non-numeral points, so these arrows need not follow that convention.


问:
Orthogonal complex structures for indefinite inner products
Suppose that $(V,b)$ is a real even-dimensional ($n=2k$) vector space with a nondenegenerate symmetric bilinear form $b$.

Question : Is there (always) a linear map $J:V\to V$  such that

$J^2 = -I$

$J\in O(V,b)$

I know that in the case of a positive-definite form $b$, such a (orthogonal complex) structure always exists, but I was not able to see how to extend that (or prove that we cannot extend that) to the non-positive-definite case, or find references for that question.

答:
The existence of a complex structure depends on the signature $(p,q)$ of $b$. If $p$ and $q$ are even, then there does exist a complex structure. Within $O(p,q)$ you can find a copy of $O(p) \times O(q)$, which reduces to the case you know.

On the other hand, if $p$ is odd (so also $q$ is odd) then there won't be a complex structure.

For example, let $(V,b)$ be $\mathbb{R}^2$ with
$$ b(v,w) = v^T \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} w .$$
If $J \colon V \to V$ satisfies $\det (J)= \pm 1$ and
$$ J^t \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} J = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} $$
then either
$$ J = \begin{pmatrix} a & b \\ b & a \end{pmatrix} \text{ and } \det (J)=1,  \text{ or } \begin{pmatrix} a & b \\ -b & -a \end{pmatrix} \text{ and } \det(J)=-1 .$$
You can check that if you further impose $J^2=-1$ there will be no solutions.


问:
Constructing a singular simplex from other two singular simplexes.
Suppose $\sigma_1:\Delta^k \rightarrow X$ is a singular $k$-simplex and $\sigma_2:\Delta^l \rightarrow X$ is a singular $l$-simplex. Is there a singular $(k+l)$-simplex, $\sigma: \Delta^{k+l} \rightarrow X$, such that $\sigma|_{[v_1,\dots,v_k]} = \sigma_1$ and $\sigma|_{[v_k,\dots,v_{k+l}]}=\sigma_2$?

答: Were there a common extension $\sigma : \Delta^2 \to X$ with $\sigma|_{[v_0, v_1]} = \sigma_1$ and $\sigma|_{[v_1, v_2]} = \sigma_2$ where 1-simplices $\sigma_1$ and $\sigma_2$, then it must be the case that $\sigma_1(v_1) = \sigma_2(v_1)$. This won't always be possible: consider the case when the $\sigma_1$ and $\sigma_2$ have disjoint images.


问:
Graph optimization problem linked with maximal spanning tree.
Let $G$ be a non-oriented connexe graph made of $N$ nodes $B_i$. We suppose that they are not any self-connected node.

For every $(i,j) \in \{1, \dots, N \}$, we note $\nu_{ij} \geq 0$ a positive weigth on the associated edge $ij$.  If $\nu_{ij}=0$, that simply means that the nodes $B_i$ and $B_j$ are not really connected by an edge.

For a collection of real $(b_{ij})_{1 \leq i<j \leq N}$, consider the following problem of optimization :

\begin{equation}
\min_{(u_1,\dots,u_N) \in \mathbb{R}^N} \sum_{i=1}^N \sum_{j=1}^{i-1}
 |b_{ij}+u_i-u_j| \nu_{ij}
\tag{1}
\end{equation}
Solving this problem is equivalent to cut some edges out of the graph $G$, the idea is to chose well the coefficient $u_i$ so as to erase the biggest contributions $\nu_{ij}$. I would like to prove that the edges which are going to be 'erased' (i.e the edges such as $|b_{ij}+u_i-u_j|=0$) are exactly the edges of a maximal spanning tree $T$ of $G$.

I recall here the defitinition of a maximal spanning tree :

A graph $T=((B_i)_{1 \leq N},A_T)$ is said to be a maximal spanning tree of $G$ if for every $(i,j) \in (1, \dots, N)$, the edge $ij$ has a weight of $x_{ij} \nu_{ij}$, with the $(x_{ij})_{1 \leq i < j \leq N}$ be a solution of :

\begin{align}
\max_{x_{ij} \in (0,1)^{\frac{N(N-1)}{2}}}  \sum_{i=1}^N \sum_{j=1}^{i-1} x_{ij} \nu_{ij}
\tag{2}
\end{align}
with the following constraints :

the graphe formed with coefficient $x_{ij} h_{ij}$ has no cycle in it

$$\sum_{j=i+1}^N x_{ij} + \sum_{j=1}^{i-1} x_{ji}  \geq 1, \quad  \forall i \in \{1,\dots,N \}$$

These two conditions insures that the graph obtained with coefficient $x_{ij} \nu_{ij}$ is indeed a tree.

Remark that I'm not sure that the result I want to prove is true. I'have tried this construction on several little graphs but I found no counter-example, but I'm not very used to graph theory. Any remarks or advices are welcomed.

答:
There is always going to be an optimal solution given by a spanning tree, but that spanning tree depends on the $(b_{ij})$ vector and not just the costs, and in general is not going to be the spanning tree with maximum weight. I give an example where it's not at the end of this answer.

You can find the optimal spanning tree with linear programming; your objective function is a linear program, once you replace absolute values by inequalities. I think that, similar to a min-cost flow problem, you can first take the dual (so that you have variables for edges, not vertices, and a spanning tree is a basic solution) and then do a "tree simplex method" where you pivot on a non-tree edge, bringing it into the basis and removing one of the existing edges of the tree.

Fact 1. There is an optimal solution such that edges with $|b_{ij} + u_i - u_j|$ ("erased" edges) form a connected graph.

To see this, suppose you have a solution which is not connected: we can split the vertices of $G$ into two sets $S, \overline{S}$ such that none of the edges between $S$ and $\overline{S}$ are erased. Now consider changing $u_i \to u_i + \delta$ at all vertices in $S$ only. The effect of this is to change $|b_{ij} + u_i - u_j|$ to $|b_{ij}+u_i - u_j + \delta|$ for all edges between $S$ and $\overline{S}$; as a function of $\delta$, the objective function looks like $$\sum_{i \in S} \sum_{j \in \overline{S}} |C_{ij} + \delta|\nu_{ij}$$ for some constants $C_{ij}$. This is piecewise linear in $\delta$, with slopes changing at values $\delta = -C_{ij}$ only; by assumption, $\delta=0$ is not such a corner point, because we don't have any erased edges between $S$ and $\overline{S}$. So starting from $\delta=0$ (our original optimal solution), you can always either increase or decrease $\delta$ to hit one of those points, without making the solution worse (so we retain optimality). This changes the solution to one with an additional erased edge between $S$ and $\overline{S}$.

Fact 2. For every spanning tree $T$, there is a unique solution $(u_i)$ - not necessarily optimal - such that the erased edges are exactly the edges of $T$, up to adding a constant to all $u_i$.

This is because we can "grow" $T$ by starting with a single vertex (whose value of $u_i$ we can choose arbitrarily), and adding a leaf vertex over and over. As we do so, the leaf vertex's value of $u_i$ is uniquely determined by the requirement that its edge to its neighbor in $T$ satisfy $b_{ij}+u_i-u_j=0$.

Generically, for most $(b_{ij})$, it will not be possible to have a cycle of erased edges. A cycle is a path plus another edge; the path of erased edges already fixes the value of $(u_i)$ on all its vertices, up to translation. The last edge can only be erased by coincidence, if its value of $b_{ij}$ happens to be correct. Even a tiny perturbation of $(b_{ij})$ will eliminate all cycles in the optimal solution.

This tells us that it's enough to consider solutions where the graph of erased edges is acyclic and connected: a spanning tree of the graph.

However, in the following problem, taking the max-weight spanning tree is the wrong thing to do:

The max-weight spanning tree is the path along the weight-$2$ edges. Going from left to right, the MST solution sets $u_1=0$, $u_2 = 4$, $u_3 = 11$, $u_4 = 14$, up to translation. The total cost of this solution is $|6+0-11|+|5+4-14|+|8+0-14|$ or $16$.

Another spanning tree is the star using edges from the leftmost vertex to all others. The spanning tree solution from the star sets $u_1=0$, $u_2 = 4$, $u_3 = 6$, $u_4 = 8$. The total cost of this solution is $2|7+4-6| + 2|3+6-8|+|5+4-8|$ or $13$.


问:
possible dynamics on $\mathbb{R}^2$
A linear map is non-hyperbolic if $|\lambda_i|=1$ for a least one eigenvalue $\lambda_i$.

Catalogue the possible dynamics of a non-hyperbolic linear map on $\mathbb{R}^2$

For something like this would you go through all the cases;
i.e $|\lambda_1|=|\lambda_2|=1$ e.t.c?

Any hints on what all the cases are and mean would be great, thanks.

答:
I would suggest the following. What happens if $|\lambda_1|=1$ and

$|\lambda_2|<1$ ?

$|\lambda_2|=1$ ?

$|\lambda_2|>1$ ?

Do you think we need to consider the cases where we swap $1$ and $2$ in the indices above?

Title: possible dynamics on $\mathbb{R}^2$


问:
How to approach Graph Theory Proofs
Show that if $G$ is a simple graph with $n$ vertices (where
$n$ is a positive integer) and each vertex has degree greater than or
equal to $n−1$, then the diameter of $G$ is $2$ or less.

I ended up getting very stuck on this question. Proving by contradiction is usually how I go about getting a better understanding of what is actually being asked for but when I tried this one I ended up doing something with the neighbors of the vertices and I just got off on the wrong track.  How would you have approached this question and in general what are things to look out for with proofs like this?

答:
Hint. (Assume $n \ge 2$.) If every pair of two points is connected by an edge, the diameter is $1$.

Now, suppose two points $v$ and $w$ are not connected by an edge. Let $V_v$ and $V_w$ denote the set of vertices connected to $v$ and $w$, respectively. If $V_v \cap V_w \neq \varnothing$, then you are done. (Why?)

Note that $|V_v|, |V_w| \ge n - 1$. (Why?)

On the other hand, $|V_v \cup V_w| \le n$. Thus, we have $$|V_v \cap V_w| = |V_v| + |V_w| - |V_v \cup V_w| \ge 2(n-1) -n = n - 1 \ge 1.$$
Can you conclude now?

Title: How to approach Graph Theory Proofs


问:
Express the event ${W≤w,M= 1,O≤t}$ in terms of the random variables $X$ and $Y$
$X$ and $Y$ are independent random variables following the exponential distribution such that:
$$X,Y\sim \mathrm{exp}(\lambda)$$
$$W=min(X,Y)$$
$$Z=max(X,Y)$$
$$O=Z-W$$
$$M=\mathbf{1}_{X\le Y}=\begin{Bmatrix}
1 & if X\le Y \\
0 & if X>Y
\end{Bmatrix}$$

So far I know that $W\sim \mathrm{exp}(2\lambda)$ and M follows a bernoulli distribution with parameter $\frac{1}{2}$

In addition to this $P(W>w,M=1)=P(W>w)P(M=1)$ (i.e. the events are independent)

I now need to:

a. express the event $(W\le w,M=1,O\le t)$ in terms of $X$ and $Y$

b. find $P(W\le w,M=1,O\le t)$ and $P(W\le w,M=0,O\le t)$

For a. I rewrote the event as $$(W\le w,M=1,O\le t)=(min(X,Y)\le w,X\le Y,max(X,Y)-min(x,y)\le t)$$ However, I wasn't sure how to condense this into one inequality (e.g. $P(W>w,M=1)=P(Y\ge X>w)$)

For b. I had no clue, I think it is because I have been unable to do part a. properly.

I found $f_{W,Z}(w,z)=2\lambda^2e^{\lambda(z+w)}\mathbf{1}_{0\le w\le z}$

Using this I tried to work out
$$\begin{align}
P(O\le t)&=\int_{0}^{t-w}\int_{w}^{t-w}2\lambda^2e^{-\lambda(z+w)}\mathbf{1}_{0\le w\le z, z-w\le t}dzdw\\
&=1-2\lambda e^{-\lambda t}(t-w)-e^{-2\lambda(t-w)}
\end{align}$$

But I wasn't really sure whether this was actually useful or how to connect the different parts of this probability.

Any hints to get me in the right direction would be much appreciated.

EDIT: I believe it may be something along the lines of proving $W\le w$ and $O\le t$ are independent so then the probability would be $$P(W\le w,M=1,O\le t)=(1-e^{-2\lambda w})\frac{1}{2}(1-e^{-\lambda t})$$

答:
With $w,t\ge 0$ you have

$$\mathbb P(W\le w,M=1,O\le t) \\=\mathbb P(X\le w, X\le Y\le X+t) \\=\int_{x=0}^w\int_{y=x}^{x+t} \lambda^2 e^{-\lambda x}e^{-\lambda y}\, dy\, dx \\=\int_{x=0}^w \lambda(1-e^{-\lambda t}) e^{-2\lambda x}\, dx \\= \frac12 (1-e^{-\lambda t}) (1-e^{-2\lambda w}).$$

The next stage is letting $w \to \infty$ so you get $\mathbb P(M=1,O\le t) =\frac12  (1-e^{-\lambda t})$

and by symmetry $\mathbb P(M=0,O\le t) =\frac12  (1-e^{-\lambda t})$

so adding these together $\mathbb P(O\le t) =(1-e^{-\lambda t})$

meaning $O \sim \exp(\lambda)$

so $O$ is independent of $W$ (and of $M$).


答:
Sometimes rephrasing things in terms of indicator functions can help.

Let $\mathbb{N}$ be the positive integers

First let's define a function $f$ so that

$$ f(x, y, a) = 1 \;\;\text{if}\;\; \text{max}(x, y) \ne a \;\text{or}\; x = y $$
$$ f(x, y, a) = 0 \;\;\text{otherwise} $$

Your original claim is equivalent to saying $f(x,y,a) = 1$ for all $x$, $y$, $a$.

A simple counterexample like $f(1, 2, 2) = 0$ is enough to refute the claim, but I'll show that the induction step fails for each value of $a$ in $\mathbb{N}$, rather than merely failing for some value of $\mathbb{N}$.

The induction hypothesis is equivalent to:

$$ (\forall x \forall y \mathop. f(x, y, a) = 1) \to (\forall x \forall y \mathop. f(x, y, a+1) = 1) $$

Which is equivalent to the following where $c$ and $d$ are constants. $a$, $x$ and $y$ are variables and implicitly universally quantified.

$$ f(c, d, a) = 0 \;\lor\; f(x, y, a+1) = 1 $$

Let's consider the value of the expression $f(a, a+1, a+1)$ .

$a$ and $a+1$ aren't equal, and $\text{max}(a, a+1)$ is $a+1$, so $f(a, a+1, a+1)$ is zero.

This contradicts our induction hypothesis for every value of $a$, so the induction step never holds.

Title: What's wrong in this inductive proof?


问:
$(1-t^2)^2 = 1-2t^2 + t^4$ . Why $+ t^4$?
Understand that involution means to multiply value with the same value so many times as involution number.
So, understand that $1*1=1$

 $t^2 * t^2$ would be 2t^2 (sorry, now understand that this is incorrect. Should be $t^{(2+2)}$ because rule is that for multiplication must sum the exponents).

So far understand.

But why $+ t^4$?

What the rule determines that need $+ t^4$?

If instead t use some number, then yes, all is correct.
Just want to understand why $+ t^4$?

What would need to do if, for example $(1-t^2)^4$ or $(1-t^3)^2$ ?

Here is link to "textbook" https://estudijas.rtu.lv/pluginfile.php/287370/mod_resource/content/0/Uzdevumi/Uzdevumi_1.pdf The first page, the first example (1. piemērs. Aprēķināt / 1.example. Must calculate)

Body: By the binomial formula we have $(1-t^2)^2=1-2 \times t^2+{(t^2)}^2=1-2t^2+t^{2 \times 2}=1-2t^2+t^4$.


问:
Sum of n "integers"?
I was reading a paper on the Gamma Function and came across the problem posed with regard to interpolation theory. I have no idea about interpolation theory, and a simple google search translated interpolation to estimation.

My question is with regard to the equation $a_n=\frac{(n)(n+1)}{2}$

We've all learnt in school how exactly we formed this equation. My question is, is n confined only to integer values? I'm having trouble understanding the following statement from Pg.3 in the above mentioned link:

"The formula extends the scope of the original problem to values of the variable other than those for which it was originally defined and solves the problem of interpolating between the known elementary values"

My reasoning is as follows:

We obviously know that the sum of n integers satisfies the formula. But what does it mean for n to equal a non integral value, let's say $4.5$. It obviously doesn't mean $1+2+3+4+(4.5)$ because 4.5 isn't even an integer. So, does this mean that the formula doesn't return a meaningful value for some n, not an integer?

If not so, on what basis are we saying that we're estimating the sum for the $4.5^{th}$ integer?

答:
It is very common for a concept in mathematics to have a larger scope than expected. Consider, for instance, the sine function. The definition of sine we are taught in elementary geometry as the ratio of the opposite side to the hypotenuse in a right triangle only applies when dealing with acute angles. Later, we discover that sine has many other properties, most of which go far beyond computing the angles and sides of triangles. To do this, however, we shift our perspective. $\sin(100^{\text{o}})$ can no longer mean the ratio of the opposite side to the hypotenuse; instead, it must refer to something different.

In a similar vein, the formula for the sum of first $n$ positive integers is
$$
S_n=\frac{n(n+1)}{2} \, ;
$$
but notice that it is completely meaningful to consider the function $f: n \mapsto n(n+1)/2$ even when $n$ is not a positive integer. So even though $f(4.5)$ does not refer to the sum of the first $4.5$ integers (whatever that would mean), it is still interesting to study the properties of the function $f$. It is almost certainly the case that $f$ will not have all the amazing properties that sine does, but that not does not mean our task in generalising the sum of the first $n$ positive integers was unfruitful.

The gamma function is a better example of such a generalisation, since it is widely documented how useful it was to generalise the factorial beyond integer values. The Riemann zeta function can be analytically continued to the complex plane, and the gamma function provides an explicit form for its value. Given the significance of the Riemann zeta function in number theory, don't you think this is amazing? These developments would not have been possible had it not been for our capacity to broaden our minds and think beyond the initial definition of a function.

Title: Sum of n "integers"?


问:
Flawed strong induction of $2^a = 2$.
I'm trying to prove that for all positive integers $a$, that $2^a = 2$.

Obviously, I know this is false, but I was given an induction proof and I need to find the error.

The base case is that for $a = 1$, it's true that $2^1 = 2$.

For the induction step, we let $x$ be an arbitrary positive integer. The induction hypothesis is that $2^y = 2$ for all integers $y$ such that $1 \leq y \leq x$, with the same restriction on $x$ as mentioned. We need to prove that $2^{x + 1} = 2$.

$2^{x+1} = \frac{2^x \cdot 2^x}{2^{x - 1}}$

$= \frac{2 \cdot 2}{2}$ by the induction hypothesis

$= 2$

This completes strong induction, so $2^a = 2$ for all positive integers $a$.

答: The issue is that in going from $x$ to $x+1$ you assume the hypothesis is true for both $x$ and $x-1$. But if $x=1$ then $x-1$ is out of range, so the step from $1$ to $2$ doesn't work.

Title: Flawed strong induction of $2^a = 2$.


问:
Derivative of conditional expectation of integral of stochastic process
Let $T>0$. Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space and let $\mathbb{F}=(\mathcal{F}_u)_{u\in[0;T]}$ be a filtration such that $\mathcal{F}_T=\mathcal{F}$. Let $(\alpha_u)_{u\geq 0}$ be a strictly positive, $\mathbb{F}$-adapted stochastic process.

I would like to show in a rigorous way that
$$
\frac{d\mathbb{E}_{\mathbb{P}}\left[\int_t^\tau\alpha_u du\biggr|\mathcal{F}_t\right]}{d\tau}\Big|_{\tau=\tau'}=\mathbb{E}_{\mathbb{P}}\left[\alpha_{\tau'}\Big|\mathcal{F}_t\right],
$$
where $t,\tau'\in(0;T)$ and $\tau'>t$.

I could only come up with a intuitive argument where $\alpha_u$ is constant over a small interval $[\tau;\tau+\Delta\tau]$, but I suspect there might be a more rigorous way to prove this statement. What are some theorems that one could use to construct such a rigorous argument? If so, which are those theorems? Is there maybe a general method for proving such statements?

EDIT: Imposing conditions on $(\alpha_u)_{u\geq 0}$ may be required to give a definitive answer to this question.

答:
(I assume $(\alpha_u)_{u\ge 0}$ is progressively measurable and uniformly bounded.)

One can choose the conditional expectations $A_u:=\Bbb E_{\Bbb P}[\alpha_u\mid\mathcal F_t]$, $u\ge t$, so that $(A_u)_{u\ge t}$ is jointly $\mathcal F_t$-measurable in $\omega$ and Borel measurable in $u$. Then, by a version of Fubini's theorem
$$
\Bbb E_{\Bbb P}\left[\int_t^\tau \alpha_u du\mid \mathcal F_t\right] =\int_t^\tau A_u du
$$
in the sense that the integral on the right is a version of the conditional expectation on the left, for each $\tau>t$. The function $\tau\mapsto\int_t^\tau A_u du$ is absolutely continuous on $[t,\infty)$, and so has a pointwise derivative at a.e. $\tau'>t$. The same is therefore true of the left, and so
$$
\lim_{\epsilon\downarrow 0}{\Bbb E_{\Bbb P}\left[\int_t^{\tau'+\epsilon} \alpha_u du\mid \mathcal F_t\right]-\Bbb E_{\Bbb P}\left[\int_t^{\tau'} \alpha_u du\mid \mathcal F_t\right]\over\epsilon} =\lim_{\epsilon\downarrow 0}{\Bbb E_{\Bbb P}\left[\int_{\tau'}^{\tau'+\epsilon}\alpha_u du\mid\mathcal F_t\right]\over \epsilon}=A_{\tau'}
$$
for a.e. $\tau'>t$, almost surely.


问:
Simple probability with marbles
I have completely forgotten my statistics knowledge, and I have now found myself in dire need of this without having access to my books.

While I'm pursuing another context, I would like to ask my questions using marbles. Say I've got $100$ marbles of two colors: $6$ black marbles and $94$ white marbles. Then I pick $4$ marbles at random without putting them back. How do I then calculate the probability that $1$ marble is black, $2$ marbles are black, and $3, 4...$?

I feel there should exist some kind of a formula for calculating this probability. I want to be able to plot these probabilities via this formula.

答:
Hints:

The number of ways of picking 4 marbles out of 100 (order unimportant) is ${100 \choose 4}$.  This accounts for the "without replacement" specification since the $4$ marbles are distinct.

The number of ways of picking, for example, 2 white marbles and 2 black marbles out of the specified 100 marbles is ${6 \choose 2}{94 \choose 2}$.

Title: Simple probability with marbles


问:
Physical meaning of the null space of a matrix
What is an intuitive meaning of the null space of a matrix? Why is it useful?

I'm not looking for textbook definitions. My textbook gives me the definition, but I just don't "get" it.

E.g.: I think of the rank $r$ of a matrix as the minimum number of dimensions that a linear combination of its columns would have; it tells me that, if I combined the vectors in its columns in some order, I'd get a set of coordinates for an $r$-dimensional space, where $r$ is minimum (please correct me if I'm wrong). So that means I can relate rank (and also dimension) to actual coordinate systems, and so it makes sense to me. But I can't think of any physical meaning for a null space... could someone explain what its meaning would be, for example, in a coordinate system?

Thanks!

答:
I find the easiest way to visualise null space is to consider a matrix mapping which represents the mapping of a vector to its shadow on $y=0$ from a fixed light source which is far away.

The null space of this mapping is a vector pointing directly towards the light source, because the vector representing its shadow in $y=0$ will be $0$. Generally, we can see from this example that for some mappings there will exist vectors which will always be mapped to $0$.

We can also see how other vectors undergo a non-invertible mapping. That is, from the shadow the best you could reconstruct the original vector would be up to an ambiguity in the direction of the null space.

(This is also good because you can do it on a table with a pen)


答: You can pretty much always find the error in an induction proof by just stepping through it yourself. An induction proof allows you to deduce $\phi(a)$ from all smaller $\phi(i)$; you know the statement is false when $a=2$; so write out the proof setting $a=2$ throughout, and see what false statement you wrote down.

Title: Flawed strong induction of $2^a = 2$.

Body:
I'm trying to prove that for all positive integers $a$, that $2^a = 2$.

Obviously, I know this is false, but I was given an induction proof and I need to find the error.

The base case is that for $a = 1$, it's true that $2^1 = 2$.

For the induction step, we let $x$ be an arbitrary positive integer. The induction hypothesis is that $2^y = 2$ for all integers $y$ such that $1 \leq y \leq x$, with the same restriction on $x$ as mentioned. We need to prove that $2^{x + 1} = 2$.

$2^{x+1} = \frac{2^x \cdot 2^x}{2^{x - 1}}$

$= \frac{2 \cdot 2}{2}$ by the induction hypothesis

$= 2$

This completes strong induction, so $2^a = 2$ for all positive integers $a$.


问:
Is there only a unique way to decompose a matrix as a series of multiplication of elementary matrix ? (RREF and invertible matrix)
We know that for each given matrix, there exists only one unique matrix in row reduced echelon form.

We also know that the transformations of a matrix to another can be decomposed to a series of elementary matrices:
$$A=E_nE_{n-1}E_{n-2}\dots E_1 (P) \text{ (where P is the original matrix)}$$

As a result, I would like to ask:

Does it exist only one way to transform a matrix to the RREF ?

Is the matrix resulted from $E_nE_{n-1}E_{n-2}\dots E_1$ that transforms a matrix to its RREF unique?

We also know that to find the inverse of an invertible matrix, we can also apply a series of multiplication of elementary matrices.

In that case, is $E_nE_{n-1}E_{n-2}\dots E_1$ unique in finding the inverse matrix?

答:
Try row reducing $\begin{pmatrix} 1 & 0 \\ -1 & 0 \end{pmatrix}$ in two ways: first, by just adding row 1 to row 2, and second, by swapping the rows, adding (the new) row 1 to (the new) row 2, and then scaling row 1 by -1. Pretty sure you get different products of $E$'s.

In more detail, consider the matrix $\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$ (implementing the first RREF) and the matrix product $\begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ (implementing the second). Are they the same?

As a metamathematical note, I came up with this example from a general intuition that the product of $E$s may depend on which rows you choose to use when clearing out entries from a given column.  Often you have some choice in that, and apparently it does make a difference.


问:
An Elegant New Proof of Herons Formula?
A triangle with side lengths $a, b, c$ an altitude($h$), where the height($h_a$) intercepts the hypotenuse($a$) such that it is the sum of two side lengths, $a = u +v$ and height($h_b$) intercepts hypotenuse($b$) such that it is also the sum of two side lengths $b = x + y$, we can find a simple proof of herons formula.

Image here:

(Note that $h =  \sqrt{au}$ and $h = \sqrt{bx}$, giving $au = bx$)

First the equations we have are:

$u + v = a$

$x + y  = b$

$au = bx$

$\sqrt{av} + \sqrt{by} = c$

Substituting $v$ and $y$ with $u$ and $x$ for the $4$th equation:

$\sqrt{a^2 - au} + \sqrt{b^2 - bx} = c$

Then using $au = bx$ we eliminate $x$ to find $u$:

$\sqrt{a^2-au}+\sqrt{b^2-b\left(\frac{au}{b}\right)}=c$

$u =  \frac{1}{4ac^2}(2a^2b^2+2a^2c^2-a^4-b^4+2b^2c^2-c^4)$

Finally, substituting this into $h = \sqrt{au}$:

$h = \sqrt{\frac{1}{4c^2}(2a^2b^2+2a^2c^2-a^4-b^4+2b^2c^2-c^4)}$

Plugging this into the area formula ($A = \frac{1}{2}ch$) gives:

$A = \frac{1}{2}c\sqrt{ \frac{1}{4c^2}(2a^2b^2+2a^2c^2-a^4-b^4+2b^2c^2-c^4)} $

$A = \sqrt{\frac{1}{16}(c^2 - (a - b)^2)(( a + b)^2 - c^2)} $

$A = \sqrt{\frac{1}{16}(a + b - c)( a + b + c)( b + c - a)(a + c - b)} $

$A = \sqrt{s(s - a)(s- b)(s- c)}$

Q.E.D.

Thoughts?

答: It is certainly a correct proof of Heron's formula that I have not seen before. I don't believe that it is any simpler than the other proofs that I have seen, but I am still entertained by it. However, I do not know if this is an appropriate posting since you do not really have a question other than possibly 'is my proof correct?'. I believe that the stack exchange guidelines suggest we only post questions and answers, not discussions.</p>

Title: An Elegant New Proof of Herons Formula?


问:
Is $\mathcal{F}=\{\{2,4,6\},\{3,4,5,6\}, \Omega, \emptyset\}$ a $\sigma$-algebra over $\Omega = \{1,2,3,4,5,6\}$?
Hello so I'm trying to understand when a set can be defined as a $\sigma$-algebra (I'm new to this :)). I stumbled upon this question:

Is $\mathcal{F}=\{\{2,4,6\},\{3,4,5,6\}, \Omega, \emptyset\}$ a $\sigma$-algebra over $\Omega = \{1,2,3,4,5,6\}$?

My thoughts

So I think it's not a sigma algebra because, a part of the definition states:
$$\text{if }A \in \mathcal{F} \rightarrow A^{c}\in \mathcal{F} \text{ with $\mathcal{F}$ a sigma-algebra}$$

So if we take the complement of the subset {2,4,6} you get {1,3,5} which is not in $\mathcal{F}$

The reason why I asked this question is because I'm not sure that this it totally true and mathematical correct.

If someone knows the answer and could share it we me it would be very much appreciated :)

Thanks in advance!

答: Yes, your solution is correct. It is not a σ-algebra.</p>


问:
What's a "rank-two update" to a matrix?
I'm reading a book, and on its numerical optimization chapter, more precisely in the BFGS algorithm section, the authors state that it's a "rank-two update to the matrix". I've searched for the definition, but I only found the definition for the rank-one update here.

So my question is what is a rank-2 update, and why is the BFGS an example of such an update.

Thanks in advance.

答:
It is two independent rank-one updates performed simultaneously, or if you want, the addition of a rank-2 matrix. This happens because you are updating a symmetric matrix in a symmetric way with the dyadic product $ab^T$ and its transpose $ba^T$, which can also be expressed as some difference of the symmetric updates $(a+b)(a+b)^T$ and $(a-b)(a-b)^T$.

For the secant condition one wants to enforce $B_+s=y$. With a rank-1 update that would give $(B+ab^T)s=y$ giving $a=y-Bs$ and with some other geometric constraints $b=\alpha s$. This is not very symmetric in most cases.

So one tries $B_+=B+ab^T+ba^T$ with $y=B_+s=Bs+a(b^Ts)+b(a^Ts)$. Then again for some kind of geometric minimality one gets that $a$ and $b$ have to be linear combinations of $y$ and $Bs$ which again should be sufficient to determine them.

Title: What's a "rank-two update" to a matrix?


问:
Prove that $a_n\to 0$ but $\sum a_n = \infty$.

Let $f:[-1,1]\to\mathbb{R}$ be a $C^2-$function with $f(0)=0$, $f^{\prime}(0)=1$ and $f^{\prime}(x)>1$ for all $x>0$. Let $a_1\in (0,1)$ and define recursively $a_{n+1}$ by equation $f(a_{n+1})=a_n$. Prove that $a_n\to 0$ but $\sum a_n = \infty$.

I was doing this exercise but I am kind of confused by the definition of the sequence, we should have the injection for this and I cannot say anything about the function around $-1$. If I consider $a_n \in (0,1)$ it works well and I can prove that $a_n\to 0$ , with the respective conditions, but I also know that can exist negative points $a_i$ near $0$ for some $i$ so it becomes a problem. And what about $\sum a_n = \infty$? I am out of ideas for this.

答:
As Martin R says, it’s quite necessary to assume $0 < a_n < 1$, and then $a_n$ decreases to zero. Behavior of the series $a_n$ is (of course) trickier.

We know by Taylor that $a_n=f(a_{n+1})=a_{n+1}+\int_0^{a_{n+1}}{tf’’(a_{n+1}(1-t))dt}=a_{n+1}+a_{n+1}^2(c +o(1))$ where $c=f’’(0)/2$. Thus $a_{n+1}^{-1}-a_n^{-1}=a_{n+1}^{-1}(1-(1+(c+o(1))a_{n+1})^{-1})=\frac{(c+o(1))a_{n+1}}{a_{n+1}(1+(c+o(1))a_{n+1})}=c+o(1)$ (so $c \geq 0$). It follows that $0<a_n^{-1}=O(n)$ so $a_n \geq C/n$ for some positive constant $C$.


问:
What is the record for Collatz Conjecture Steps
Does anyone know the record for the number of steps a Collatz Conjecture run has taken to get to 1?

I have written a small program in Python to do the Collatz Conjecture on the Mersenne prime where n=5000 and produced a text file of ~88MB with a total step of 67378.

答:
A small caveat first: what counts as an 'iteration' of the Collatz process varies a bit from source to source. Because what happens at even numbers is 'boring', the most standard convention seems to be looking at the process as it relates to odd numbers specifically, taking $n\mapsto \dfrac{3n+1}{2^i}$, where $2^i$ is the largest power of $2$ that divides $3n+1$.

Now, we can think about how the Mersenne numbers map under this process. Suppose we start with $n_0=2^k-1$. Then we look at $3n_0+1$ and see that this is $3\cdot2^k-2$; dividing by $2$ once gives $n_1=3\cdot 2^{k-1}-1$. Unless $k=1$, this is also odd, so we have no more factors of $2$ to strip out.

And this repeats: $3n_1+1$ is $3^2\cdot2^{k-1}-2$, dividing by $2$ once gives $n_2=3^2\cdot 2^{k-2}-1$, and unless $k=2$ this will also be odd.

It should be clear how this process iterates; after $i$ steps we'll have $n_i=3^i\cdot2^{k-i}-1$, and this continues until $i=k-1$ and we get $n_{k-1}=3^{k-1}\cdot 2-1$. Then $3n_{k-1}+1=3^k\cdot2-2$, and dividing by $2$ gives $3^k-1$ — but note that now we can do at least one more division by $2$, so the expression for $n_k$ isn't quite so neat.

In general the iteration will get much messier from here, and there generally won't be any more 'clean' expressions for the results. But we can explicitly describe the first $k-1$ steps of the process this way, so producing a long chain of iterations is just a question of how much computing power you want to throw at it.


答:
The sequence of transformations is not unique. For example you can insert an operation, then undo it by applying the inverse of the operation.

The matrix $E_nE_{n-1}\cdots E_1$ is not unique unless the original matrix $P$ is of full rank. For example, consider $P:=\begin{pmatrix}1&0\\1&0\end{pmatrix}$, whose RREF is $A:=\begin{pmatrix}1&0\\0&0\end{pmatrix}$. Try writing $A$ as the product $EP$, for $E:= \begin{pmatrix}a&b\\c&d\end{pmatrix}$. After expanding $EP$, you will find that the only constraints are $a+b=1$ and $c+d=0$. This means you have some freedom in selecting $a, b, c, d$.

If $P$ has full rank, then the RREF $A$ is the identity matrix. So if $E$ satisfies the equation $A=EP$, then $E$ must be the inverse of $P$ and is therefore unique.

Title: Is there only a unique way to decompose a matrix as a series of multiplication of elementary matrix ? (RREF and invertible matrix)

Body:
We know that for each given matrix, there exists only one unique matrix in row reduced echelon form.

We also know that the transformations of a matrix to another can be decomposed to a series of elementary matrices:
$$A=E_nE_{n-1}E_{n-2}\dots E_1 (P) \text{ (where P is the original matrix)}$$

As a result, I would like to ask:

Does it exist only one way to transform a matrix to the RREF ?

Is the matrix resulted from $E_nE_{n-1}E_{n-2}\dots E_1$ that transforms a matrix to its RREF unique?

We also know that to find the inverse of an invertible matrix, we can also apply a series of multiplication of elementary matrices.

In that case, is $E_nE_{n-1}E_{n-2}\dots E_1$ unique in finding the inverse matrix?


问:
Practical significance of $\frac{17}{21}$=$\frac{1}{2}$+$\frac{1}{6}$+$\frac{1}{7}$
In an article of ancient maths I found that Babylonians also had a great idea of maths.
For practicle purposes, if I want to divide 17 grain bushels among 21 workers, the equation would be $\frac{17}{21}$≈0.8. It means I have to give 0.8 grain bushels to each worker.
Since $\frac{17}{21}$ can be written as $\frac{1}{2}$+$\frac{1}{6}$+$\frac{1}{7}$, what does this equation implies to the real world?
There is also written that it has practical meaning then I am wondered what's that practical meaning of this equation.

答:
I will give you some simple real world applications which might help you.

Thin lens Equation: If the lenses of focal lengths $f_1, f_2$ are “thin”, the combined focal length $f$ of the lenses is given by $$\dfrac1f=\dfrac1{f_1}+\dfrac1{f_2}$$ while if the lenses are separated in air by some distance $d$ then the combined focal length is given by $$\dfrac{d}{f_1f_2}=\dfrac1{f_1}+\dfrac1{f_2}-\dfrac1f.$$

Electric Circuits: In a parallel circuit the reciprocals in individual resistances/inductances are added to find the total resistance/inductance. A similar equation used to compute the capacitance of capacitors in series.

Harmonic Mean: This is another central tendency measure like arithmetic mean and geometric mean etc. Specially when rates and ratios are involved the harmonic mean gives the most correct value of the mean. This is useful in statistics and financial mathematics.


问:
$p=2^n+1$. Prove that every quadratic nonresidue modulo $p$ is a primitive root modulo $p$
This is another one of the number theory problems I've been struggling with as of late (hopefully I'm not posting too many questions at once!).

Let $n$ be a positive integer and let $p=2^n+1$ be a prime number.
  Prove that every quadratic nonresidue modulo $p$ is a primitive root
  modulo $p$.

Suppose $a$ is a quadratic nonresidue and $r$ a primitive root muodulo $p$. Then there exists no $x$ such that $x^2 \equiv a \mod p$. We must determine the order of $a$. We know that $a$ must be congruent to some power of $r$, say $m$, since $\{r^1,r^2,\ldots,r^{2^n}\}$ is a reduced residue system modulo $p$. Suppose that $\mathrm{ord}_p a=b$. Then $a^b \equiv r^{mb} \equiv 1 \mod p$. We must show that $b=2^n$ since $\phi(p)=2n$. But $r$ is a primitive root and so $mb \equiv 0 \mod{2^n}$ (or $\equiv 2^n \mod{2^n}$). Hence $mb = 2^n k$. How can I finish it?

答:
The number of generators of $\Bbb Z_p^\times$ is $\phi(p-1)=\phi(2^n)=2^{n-1}$. Since half the elements of $\Bbb Z_p^\times$ are residues (and not generators), all the quadratic non-residues are generators.

If $\langle g\rangle\cong\Bbb Z_p^\times$ then $\langle g^i\rangle\cong\Bbb Z_p^\times\iff\gcd(p-1,i)=1$. Moreover, the number of generators of $\Bbb Z_p^\times$ is $\phi(p-1)$.

Proof: Let $g$ be a generator of $\Bbb Z_p^\times$ and consider the homomorphism $$\phi:\Bbb Z_p^\times\rightarrow\Bbb Z_p^\times\\g\mapsto g^i$$ Suppose that $\phi(g^m)=g^{mi}=1$.

If $\gcd(p-1,i)=1$ then $p-1\mid m$ so that $g^m=1$ and $\ker(\phi)=\langle 1\rangle$.

If $\gcd(p-1,i)=d\neq 1$ then $\langle 1\rangle\subset\langle g^{\frac{m}{d}}\rangle\subset\ker(\phi)$.

Let $S=\{x^2\mid x\in\Bbb Z_p\}$, that is, the set of quadratic residues in $\Bbb Z_p^\times$. Then $$|S|=\frac{1}{2}|\Bbb Z_p^\times|$$

Proof: Consider the homomorphism $$\phi:\Bbb Z_p^\times\rightarrow S\\x\mapsto x^2$$
$\ker(\phi)=\langle -1\rangle$, so $\Bbb Z_p^\times/\ker(\phi)\cong S$.


问:
On the definition of the contravariant hom functor
I'm thinking about why we must define the functor $h_A=\mathrm{Hom}(\_,A)$ as a contravariant functor, i.e. if there is a way to choose the morphisms to make it a covariant with same image on objects? I tried as following.

Suppose we have a covariant functor $F$ from category $\mathcal{C}$ to $\mathrm{Sets}$, such that $FX=\mathrm{Hom}(X,A)$ for any object $X$. By Yoneda $[h^A,F]\cong FA=\mathrm{Hom}(A,A)$, where [] is the set of natural transforms and $h^A=\mathrm{Hom}(A,\_)$. Now the $1_A$ in the right corresponds to an isomorphism on the left, hence $h^A\cong F$ , a contradiction.

Is my explanation right? What is the exact way to characterize the functor $h_A$(or $h^A)$, the naturality with respect to A?
And do you have other ideas? Thank you!

答:
Your argument is incomplete. There are two problematic steps, which both contain errors. Firstly, it's not clear that $1_A$ should correspond to an isomorphism on the right hand side (and this is not generally true). Secondly, $h^A\cong F$ doesn't contradict anything.

Indeed, there are categories $\mathcal{C}$ for which $\mathcal{C}(-,A)$ can be made a covariant functor (for all $A$). In particular, any category with a functor $\bar{\cdot}:\mathcal{C}\to \mathcal{C}^{\text{op}}$ which is the identity on objects will do, since then we get a covariant functor from $X\mapsto \mathcal{C}(\bar{X},A)$. A classic example of this is given by groups (regarded as single object categories w/ object $*$), $g\mapsto g^{-1}$ defines a contravariant functor on a group $G$ regarded as a category since $(gh)^{-1}=h^{-1}g^{-1}$.

A nontrivial example of such a category is the category of inner product spaces with all linear maps between them. The adjoint of a linear map defines a contravariant functor which is the identity on objects.

When we define $F$ this way, the natural transformation $h^A\to F$ is going to be defined by
$$f\in h^V(W) = \mathcal{C}(V,W)\mapsto \bar{f} \in F(W) = \mathcal{C}(W,V).$$

To construct an $F$ for which this is not an isomorphism, we need a functor $\mathcal{C}\to\mathcal{C}^{\text{op}}$, which is the identity on objects, but is not fully faithful.

For this, we could take $G$ a group, and define $\bar{g} = 1$ for all $g$. This also defines a contravariant functor, though admittedly a rather boring one. Thus we see that the natural map $h^A\to F$ isn't necessarily an isomorphism.

What is true

You've asked why $\mathcal{C}(-,A)$ must be contravariant. The answer is sort of simple, it's just that it is contravariant. We don't define it to be contravariant, it just naturally has that structure. We can put other structures on the map from objects to sets to make it a covariant functor, as we've just seen, but it would still have the natural contravariant functor structure.

We can also make a more general statement. It is not always possible to put a covariant structure on the sets given by $\mathcal{C}(-,A)$.

Proof.

It suffices to give a counterexample. Consider the category with two objects, $0$, and $1$, and a single nonidentity map, $f$, between them. Call this category $\newcommand\2{\mathbf{2}}\2$.

Then $\2(0,0)=\{1_0\}$, but $\2(1,0)=\varnothing$, so if we had a covariant structure on $\2(-,0)$, we would get a map $f_*: \{1_0\}\to \varnothing$, which is impossible.


问:
Does $x^T(M+M^T)x \geq 0 \implies x^TMx \geq 0$ hold in only one direction?
I know this is true for the "if" part, but what about the "only if"?

Can you give me one example when the "only if" part does not hold? I am not quite sure about this.

I forgot to tell you that $M$ is real and $x$ arbitrary.

答: $M=\frac{M+M^T}2+\frac{M-M^T}2$ and $x^T\left(\frac{M-M^T}2\right)x=0$ for every real vector $x$ (because $x^TMx=(x^TMx)^T=x^TM^Tx$). Therefore $x^TMx\ge0$ if and only if $x^T\left(\frac{M+M^T}2\right)x\ge0$.


问:
Ramsey theory, generalized
Is there a "generalized" Ramsey theory? How large must a graph be such that, with arbitrary connections between vertices, the existence of arbitrarily defined subgraphs is assured?</p>

答:
The paper below rigorously states in the abstract a generalization of Ramsey's Theorem for finding monochromatic subgraphs (not necessarily subcliques/complete graphs) when coloring some arbitrary initial graph.

http://math.mit.edu/~fox/paper-Ramseymultiplecolors.pdf

This seems like a difficult question and a difficult area of research and I don't currently know of any other papers on this topic. I expect that any arbitrary starting graph (a graph with 'arbitrary connections between the vertices') is too wild to study and obtain any reasonable results. I expect that some conditions such as bipartite, postive density of edges, or regularity will be needed in order to make any reasonable progress on the type of question that you are interested in.

Title: Ramsey theory, generalized


问:
Is there a known closed form solution to $\int_0^1\frac{\ln(1+x^{2n})}{1+x^2} \,dx$?
$\require{begingroup} \begingroup$
$\def\e{\mathrm{e}}\def\W{\operatorname{W}}\def\Wp{\operatorname{W_0}}\def\Wm{\operatorname{W_{-1}}}\def\Catalan{\mathsf{Catalan}}$

Related question

Is there a known closed form solution to

\begin{align}
I_n&=
\int_0^1\frac{\ln(1+x^{2n})}{1+x^2} \,dx
=?
\tag{0}\label{0}
\end{align}

It checks out numerically, for $n=1,\dots,7$ that

\begin{align}
I_1=
\int_0^1\frac{\ln(1+x^2)}{1+x^2} \,dx
&=
\tfrac\pi2\,\ln2-\Catalan
\tag{1}\label{1}
,\\
I_2=
\int_0^1\frac{\ln(1+x^{2\cdot2})}{1+x^2} \,dx
&=
\tfrac\pi2\,\ln(2+\sqrt2)-2\Catalan
\tag{2}\label{2}
,\\
I_3=
\int_0^1\frac{\ln(1+x^{2\cdot3})}{1+x^2} \,dx
&=
\tfrac\pi2\,\ln6-3\Catalan
\tag{3}\label{3}
,\\
I_4=
\int_0^1\frac{\ln(1+x^{2\cdot4})}{1+x^2} \,dx
&=
\tfrac\pi2\,\ln(4+\sqrt2+2\sqrt{4+2\sqrt2})-4\Catalan
\tag{4}\label{4}
,\\
I_5=
\int_0^1\frac{\ln(1+x^{2\cdot5})}{1+x^2} \,dx
&=
\tfrac\pi2\,\ln(10+4\sqrt5)-5\Catalan
=
\tfrac\pi2\,\ln(10\cot^2\tfrac\pi5)-5\Catalan
\tag{5}\label{5}
,\\
I_6=
\int_0^1\frac{\ln(1+x^{2\cdot6})}{1+x^2} \,dx
&=
\tfrac\pi2\,\ln((5\sqrt2+2\sqrt{12})(1+\sqrt2))-6\Catalan
\tag{6}\label{6}
,\\
I_7=
\int_0^1\frac{\ln(1+x^{2\cdot7})}{1+x^2} \,dx
&=
\tfrac\pi2\,\ln(14\cot^2\tfrac\pi7)-7\Catalan
\tag{7}\label{7}
,
\end{align}

so \eqref{0} seems to follow the pattern

\begin{align}
I_n&=
\tfrac\pi2\,\ln(f(n))-n\Catalan
\tag{8}\label{8}
\end{align}

for some function $f$.

Items \eqref{5} and \eqref{7} look promising
as they agree to $f(n)=2n\cot^2(\tfrac\pi{n})$,
but the other fail on that.

Edit:

Also, it looks like
\begin{align}
\int_1^\infty\frac{\ln(1+x^{2n})}{1+x^2} \,dx
&=\tfrac\pi2\,\ln(f(n))+n\Catalan
\tag{9}\label{9}
\end{align}

and

\begin{align}
\int_0^\infty\frac{\ln(1+x^{2n})}{1+x^2} \,dx
&=\pi\,\ln(f(n))
\tag{10}\label{10}
\end{align}

with the same $f$.

Edit

Thanks to the great answer by @Quanto,
the function $f$ can be defined as

\begin{align}
f(n)&=
2^n\!\!\!\!\!\!\!\!\!\!
\prod_{k = 1}^{\tfrac{2n-1+(-1)^n}4}
\!\!\!\!\!\!\!\!\!
\cos^2\frac{(n+1-2k)\pi}{4n}
\tag{11}\label{11}
.
\end{align}

$\endgroup$

答:
Not a complete answer, but an elaboration of what I said in the comments.
To evaluate $$\int_1^\infty\frac{\ln(1+x^{2n})}{1+x^2} dx$$

Write it as $$\int_1^\infty\frac{\ln\left(x^{-2n}+1\right)+\ln\left(x^{2n}\right)}{1+x^2} dx = \int_1^\infty\frac{\ln\left(x^{-2n}+1\right)}{1+x^2} dx+2n\int_1^\infty\frac{\ln\left(x\right)}{1+x^2} dx$$

The second integral is a standard integral for Catalan's constant. To solve the first, make the substitution $x \to \frac{1}{x}$ to get $$\int_0^1\frac{\ln(1+x^{2n})}{1+x^2} dx + 2nG$$

So if you know the value of any of the integrals with bounds $(0,\infty)$ or $(1,\infty)$ or $(0,1)$, you could find the other two.

The series for $\ln(1+x)$ converges for $|x|<1$, so expand it to get $$\int_0^1\frac{\sum_{k=1}^{\infty}\frac{\left(-1\right)^{k+1}}{k}x^{2nk}}{1+x^2}dx = \sum_{k=1}^{\infty}\frac{\left(-1\right)^{k+1}}{k}\int_{0}^{1}\frac{x^{2nk}}{1+x^{2}}dx$$

Then you can expand $\frac{1}{1+x^2}$ to get $$\sum_{k=1}^{\infty}\frac{\left(-1\right)^{k+1}}{k}\int_{0}^{1}x^{2nk}\sum_{m=0}^{\infty}\left(-1\right)^{m}x^{2m}dx = \sum_{k=1}^{\infty}\frac{\left(-1\right)^{k+1}}{k}\sum_{m=0}^{\infty}(-1)^m\int_{0}^{1}x^{2nk}x^{2m}dx$$

Finally, evaluate the inner integral to get
$$\sum_{k=1}^{\infty}\frac{\left(-1\right)^{k+1}}{k}\sum_{m=0}^{\infty}(-1)^m\frac{1}{2nk+2m+1}$$


问:
How to take indices and name of a variable in Sage?
I define the following in Sage.

```<code>rank=8
R=PolynomialRing(QQ, 'a' ,rank+1)
a=R.gens()
</code>```

I would like to define a function f which returns the index of a[3]: f(a[3])=3 and define another function g such that g(a[3])=a. How to do this in Sage? Thank you very much!

答:
This answer draws on the one by Alex J Best for defining f,
but also defines g.

Define a multivariate polynomial ring and its generator tuple:

```<code>sage: R = PolynomialRing(QQ, 'a', 4)
sage: R
Multivariate Polynomial Ring in a0, a1, a2, a3 over Rational Field
sage: a = R.gens()
sage: a
(a0, a1, a2, a3)
</code>```

Consider one of the generators (or "indeterminates", or "variables"):

```<code>sage: p = a[2]
sage: p
a2
</code>```

To get its index in the generator tuple:

```<code>sage: a.index(p)
2
</code>```

This can be made into the function f requested in the question:

```<code>sage: f = a.index
sage: f(p)
2
</code>```

The above is tied to the definition of a; more generally:

```<code>def f(p):
    r"""
    Return the index of this generator of a polynomial ring.
    """
    return p.parent().gens().index()
</code>```

What function g the question requests is not entirely clear.

If we want g(a[2]) to return the string 'a':

```<code>def g(p):
    r"""
    Return the generator name stripped of its index.
    """
    return ''.join(c for c in str(p) if not c.isdigit())
</code>```

With that definition:

```<code>sage: p = a[2]
sage: aa, k = g(p), f(p)
sage: aa
'a'
sage: k
2
sage: ak = aa + str(k)
sage: ak
'a2'
sage: ak == str(p)
True
sage: R(ak) == p
True
</code>```

If instead we want g(a[2]) to return the tuple R.gens():

```<code>def g(p):
    r"""
    Return the tuple of generators of the parent polynomial ring.
    """
    return p.parent().gens()
</code>```

With that definition:

```<code>sage: p = a[2]
sage: aa, k = g(p), f(p)
sage: aa
(a0, a1, a2, a3)
sage: k
2
sage: ak = aa[k]
sage: ak
a2
sage: ak == p
True
</code>```

Body:
This answer draws on the one by Alex J Best for defining f,
but also defines g.

Define a multivariate polynomial ring and its generator tuple:

sage: R = PolynomialRing(QQ, 'a', 4)
sage: R
Multivariate Polynomial Ring in a0, a1, a2, a3 over Rational Field
sage: a = R.gens()
sage: a
(a0, a1, a2, a3)

Consider one of the generators (or "indeterminates", or "variables"):

sage: p = a[2]
sage: p
a2

To get its index in the generator tuple:

sage: a.index(p)
2

This can be made into the function f requested in the question:

sage: f = a.index
sage: f(p)
2

The above is tied to the definition of a; more generally:

def f(p):
    r"""
    Return the index of this generator of a polynomial ring.
    """
    return p.parent().gens().index()

What function g the question requests is not entirely clear.

If we want g(a[2]) to return the string 'a':

def g(p):
    r"""
    Return the generator name stripped of its index.
    """
    return ''.join(c for c in str(p) if not c.isdigit())

With that definition:

sage: p = a[2]
sage: aa, k = g(p), f(p)
sage: aa
'a'
sage: k
2
sage: ak = aa + str(k)
sage: ak
'a2'
sage: ak == str(p)
True
sage: R(ak) == p
True

If instead we want g(a[2]) to return the tuple R.gens():

def g(p):
    r"""
    Return the tuple of generators of the parent polynomial ring.
    """
    return p.parent().gens()

With that definition:

sage: p = a[2]
sage: aa, k = g(p), f(p)
sage: aa
(a0, a1, a2, a3)
sage: k
2
sage: ak = aa[k]
sage: ak
a2
sage: ak == p
True


问:
Product of 25 consecutive integers can never be a perfect square
today exam is :   Prove that the product of at most 25 consecutive
integers is not a square.

this problem Also appears in this book： Problems from the Book proposed by Gabriel Dospinescu chapter 3.

I also know the general result which is 1939 Erdoshere but I am no way going to use that in a competition.

Please try to give a high school argument as supposed to be given in a national Olympiad.

Thanks.

答:
This rather elliptic argument (for twenty-five) is really mostly adapting Euler’s proof, which is extremely accessible (there’s no denying a high-schooler studying for the IMO could do that given enough time and perhaps a little encouragement). I admit not being too sure how to consider the case of less integers without redoing some 24 times the calculations.

Consider twenty-five consecutive integers the product of which is a square.

Define, for an integer $n$, the radical of $n$ to be the product of the prime divisors of $n$ who appear an odd number of times in the prime decomposition of $n$. We’ll consider the radicals of our $25$ consecutive integers (so they are square-free, and products of primrs less than $25$).

So, with elementary modular arithmetic, one finds that two appears in seven to ten radicals.
Three appears in five to seven radicals.
Five appears in four to five radicals.
Seven appears in two to four radicals.
Eleven appears in one to three radicals.
Primes above eleven appear in at most two radicals.

Because the product of the consecutive integers is a square, two appears in eight or ten radicals, three in six, five in four, seven in two or four, eleven in two, primes above eleven in zero or two.

It follows that the product of the radicals divides $N=2^{10}3^65^47^4(11\cdot 13 \cdot 17 \cdot 19 \cdot 23)^2$.

But what are the first $25$ square-free numbers? They are $1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38$. Their product is $M=2^93^65^57^411^313^217^219^2 \cdot 23 \cdot (29 \cdot 37)$ so $M > N$.

It follows from this that two of the 25 numbers (let’s call them $a < b$) have the same radical $r$, and thus we can write $a=rx^2,b=ry^2$ and $r(y^2-x^2) \leq 24$. So $r(2y+1) \leq 24$, thus $ry \leq 12$, thus $b \leq (ry)^2 \leq 144$. We can check (counting powers of $19$ and $23$) that this is impossible.


问:
Schur's Theorem proof for Ramsey Theory misunderstanding?
Schur's Theorem in Ramsey Theory asserts that for every positive integer $r$, there is some positive integer $S(r)$ such that for every partition of the set $\{1,\ldots,S\}$ into $r$ parts, one of the parts contains integers $x,y,z$ with $x+y=z$. The standard proof uses Ramsey theory and graph colorings. See https://en.wikibooks.org/wiki/Combinatorics/Schur%27s_Theorem and https://proofwiki.org/wiki/Schur%27s_Theorem_(Ramsey_Theory) for the proofs.

My question is, both of these proofs seem to be saying that this integer $S(r)$ is equal to the Ramsey number $R(3,\ldots,3)$ on $r$ colors. But when $r=2$, it is well known that $R(3,3)=6$ (see https://oeis.org/A003323) but the Schur number $S(2)=5$ (see https://oeis.org/A030126).

What am I missing here?

答: The key observation here is that a coloring f of the interval [1,n] induces a coloring of the  complete graph on n+1 vertices by coloring the edge (i,j) with f(|j-i|), and a monochromatic triangle in the induced coloring of the complete graph corresponds to a monochromatic Schur configuration in the original coloring of [1,n]. HOWEVER, this connection only works one way. If you are given a coloring of the complete graph on n+1 vertices, YOU CANNOT induce a coloring on the interval [1,n] by assigning |i-j| the color of the edge (i,j). To see this, observe that (1,2), (2,3), and (3,4) may all have different colors in the graph coloring, so it would not be well defined to assign 1 = |2-1| = |3-2| = |4-3| the color of any one of the preceding edges.</p>


问:
Does a rectangle's diagonal to its perimeter have a ratio, like Pi?
The ratio of a circle's diameter to circumference merited its very own greek letter, Pi.

I have been wondering if there is such a similar, or important, ratio in a rectangle, i.e. its diagonal to perimeter?

Would I be right in guessing that it's because it's not a single value, but a more complex formula involving trigonometry? Or perhaps not a widely used one?

Many thanks in advance.

答:
Trigonometric solution

$a=d\cos x \qquad b=d\sin x$

perimeter : $2(a+b)=2d\:(\cos x+\sin x)$

$k$ = perimeter/diagonal ratio

$k = \dfrac{2(a+b)}{d}=2(\cos x+\sin x)$

$\cos x = \sin \Big( x + \dfrac{\pi}{2} \Big)$

$\sin u + \sin v = 2\sin\Big( \dfrac{u+v}{2} \Big)\cos\Big( \dfrac{u-v}{2} \Big)$

$u = x+\dfrac{\pi}{2} \; \& \; v = x \quad \Rightarrow \quad k = 2\sqrt{2}\sin\Big(x+\dfrac{\pi}{4}\Big)$

$\color{green}{y_1=2\sin x}\;,\; \color{red}{y_2=2\cos x}\;,\; \color{blue}{y_3=k=2(\sin x+\cos x)}$

$x\in \Big[ 0, \dfrac{\pi}{2} \Big] \quad \Rightarrow \quad k\in \big[ 2, 2\sqrt{2} \big]$

$\pi \approx 3.14 > 2\sqrt{2} \approx 2.83$

Conclusion

The perimeter/diagonal ratio of a rectangle cannot be equal to $\pi$.


问:
Gerrymandering/Optimization of electoral districts for one particular party
I'm asking this on behalf of Zach Weiner (actually it's my own initiative in order to promote this site). Original text is here, and is as follows:

Hey--
This is Zach from SMBC, and I have a math question you may find of interest. I only mention who I am because it relates to the idea.

I had an idea for a comic about gerrymandering. As you may know, gerrymandering is a significant social problem, in that it stifles voters' opinions. So, my idea was this: Why not make a rule that perimeter/area always has to be under a certain value.
I figured this would limit how salamander-like the districts could be made. Then, I tried to figure out the math of this on the assumption that it was a simple calculus min/max problem. It seems not to be...

The biggest problem I'm running into is how to formalize the idea of a shape being weird. My intuition tells me that the lower perimeter/area is, the less weird the shape. I.e. a wacky snakey shape designed to get several populations will have a higher perimeter/area than a more reasonable district shape, which should be vaguely rectangular or circular.
But, I don't know how to mathematize that. If that could be proved, you could probably figure out a reasonable ratio.

Thoughts?

答:
A google scholar search for "optimal gerrymandering" turns up the big results I'm aware of: Katerina Sherstryuk's "How to Gerrymander" http://www.hss.caltech.edu/SSPapers/sswp855.pdf and the American Economic Review's most recent post on the topic: http://web.mit.edu/rholden/www/papers/Friedman-Holden%20(AER,%202008).pdf.

I thought this, like fair division, was one of the areas where mathematicians and economists know the same literature.


问:
Does a limit exist at the end point of a function according to the epsilon delta definition?
According to the epsilon delta definition, the limit L of a function f(x) at a point c in the domain exists if for every $\epsilon > 0$, I can find a $\delta > 0$ such that if $0 < |x - c| < \delta$ then $|f(x) - L| < \epsilon$.

If I have a continuous function defined in $[A, B]$, and I want to calculate $\lim_{x \to A} f(x)$, the I can find the corresponding $\delta$ for for every $\epsilon$. The limit should exist and be equal to $f(A)$.

But the left hand limit of the function doesn't exist, since A is the endpoint, and a limit only exists when the left hand limit is equal to the right hand limit. Therefore the limit should not exist.

Why is it that the limit exists using one definition but not using another? Is there something wrong with how I have interpreted the $\epsilon$ $\delta$ definition?

答:
A limit in an end point is just the one-sided limit. Only when function is defined on both sides of a given point it is required that both one-sided limits exist and are equal.

There are no problems with the epsilon delta definition, the problem is that you want the left-side limit to exist in the end point when it's not required.


问:
Can singleton be an open set?
All singletons are closed sets, but can they be open sets?

By the definition of an isolated point, x in set X is an isolated point of X if {x} is open in X.
I just can't understand how singleton could be open:

$$ \left\{x \right\} \ \mathrm{is \ open \ in} \ X. \ \Leftrightarrow \ \exists r>0: \ \mathcal{B}_r \left(x \right)  \subset \left\{x \right\} $$

Is it possible to have an open ball with radius r in a singleton?

答:
Yes, it is possible. Consider the metric $d(x,y)=\begin{cases}0,&x=y\\1,&x\ne y\end{cases}$. Then $B_r(x)=\{x\}$ for any $r\le1$.

Moreover, consider any finite set  $S=\{x_1,x_2,...,x_n\}$ under any metric $\rho$. Take $d=\frac12\min_{x_i\ne x_j}\{\rho(x_i,x_j)\}>0$. Then $B_d(x_i)$ does not contain any other $x_j$ in $S$. Thus $B_d(x_i)=\{x_i\}$. That is, in a finite metric space every subset is clopen and the topology induced by the metric is the discrete topology.

Title: Can singleton be an open set?


问:
Efron-Stein Inequality proof clarification.
I am currently going through the proof of the Efron-Stein inequality in this set of notes (http://www.econ.upf.edu/~lugosi/mlss_conc.pdf)(P.g. 219-220). However, I have an issue with the final part of the proof where they use the following fact:$$\operatorname{Var}(Y)=\frac{1}{2}E[(Y-Y')^2] \text{, where Y' is an independent copy of Y}$$ to prove that $$E_i[(Z-E_i[Z])^2]=\frac{1}{2}E_i[(Z-Z_i')^2].$$ Can anyone show me how the fact is used in proving the above statement?

答: Note that $\operatorname{Var}_i(Z) =\frac{1}{2} E_i[(Z-E_i[Z])^2] $. Now $E_i$ is the conditional  expectation where all the random variables are given except the $i$-th. Finally note that conditional on $(X_1,\ldots,X_{i-1},X_{i+1},\ldots,X_n)$, $Z$ and $Z_i'$ are independent. Thus the result follows.


问:
Riemann or Lebesgue integrable
Lets consider the following two functions:

$$f(x)=\begin{cases} x &,x\in[0,1]\setminus\Bbb Q \\ 0 &,x\in[0,1]\cap\Bbb Q\end{cases}$$
$$g(x)=\frac{(-1)^{[x]}}{[x]}$$

where $[x]$ is the integer part of $x$. I am trying to determine which of these integrals are Riemann or/and Lebesgue integrable; $f(x)$ over $[0,1]$ and $g(x)$ over $[1,\infty)$.

Lebesgue for $f(x)$:
$\int_{[0,1]} f dx=\int_{[0,1]\setminus\Bbb Q}x\ dx + \underbrace{\int_{[0,1]\cap\Bbb Q}0\ dx}_{=0}=\int_{[0,1]\setminus\Bbb Q}x\ dx=\int_{[0,1]}x\ dx-\underbrace{\int_{\Bbb Q}x\ dx}_{=0}=\frac12$

Riemann for $f(x)$: I assume this function is not Riemann integrable, because every interval in a partition of $[0,1]$ will contain both rationals and irrationals, but I am not sure how to conclude.

Riemann for $g(x)$: The function takes the values $-1$ on $[1,2)$, $\frac12$ on $[2,3)$, $-\frac13$ on $[3,4)$, etc. So the integral is $-1+\frac12-\frac13+\frac14-\ldots=\sum_{k=1}^\infty(-1)^k\frac1k=-\log(2)$.

But I have no idea for the Lebesgue integral of $g(x)$.

答: For $f$: show that for any partition there is a Riemann sum that is zero, and the one which is bigger than, say, $\frac14$. As a result, the Riemann sums do not converge to the same value. For the Lebesgue integrability of $g$ you have to check whether at least one of the integrals $\int g^+$ or $\int g^{-}$ is finite. Otherwise, Lebesgue integral is not defined. Here $g^+ = \max(g,0)$ and $g^{-} = \max(-g,0)$</p>

Title: Riemann or Lebesgue integrable


问:
Variables in Sage with many indices and with negative indices.
I need to define some variables in Sage with 2 indices and the second index is negative. For example, Y[2, -6]. I know how to define variables with one index:

```<code> rank=8
R=PolynomialRing(QQ, 'a' ,rank+1)
a=R.gens()
</code>```

Edit: I tried the following codes to define Y[i,s]:

```<code>m, n = 8, 8
Y = {(i,j): var("Y_{}{}".format(i,j),
latex_name="Y_{{{}{}}}".format(i,j))
for i in [0..m] for j in [(-2*n)..0]}
</code>```

But it is said that "The name "Y_0-16" is not a valid Python identifier".

Is there some way to define Y[i,s] in Sage? Thank you very much.

答:
This may do what you want.

```<code>sage: m, n = 8, 8
sage: Y = {(i, j): var("Y_{}_{}".format(i, str(j).replace('-', 'm')),
....:                  latex_name="Y_{{{},{}}}".format(i, j))
....:      for i in (0 .. m) for j in (-2*n .. 0)}
</code>```

Usage:

```<code>sage: a = Y[0, -16] * Y[2, -3]
sage: a
Y_0_m16*Y_2_m3
sage: latex(a)
{Y_{0,-16}} {Y_{2,-3}}
</code>```

We replaced the "minus sign" - with an m in Python
identifiers but the LaTeX name is as desired.

In a Jupyter sheet, %display latex will ensure LaTeX rendering.

Body:
This may do what you want.

sage: m, n = 8, 8
sage: Y = {(i, j): var("Y_{}_{}".format(i, str(j).replace('-', 'm')),
....:                  latex_name="Y_{{{},{}}}".format(i, j))
....:      for i in (0 .. m) for j in (-2*n .. 0)}

Usage:

sage: a = Y[0, -16] * Y[2, -3]
sage: a
Y_0_m16*Y_2_m3
sage: latex(a)
{Y_{0,-16}} {Y_{2,-3}}

We replaced the "minus sign" - with an m in Python
identifiers but the LaTeX name is as desired.

In a Jupyter sheet, %display latex will ensure LaTeX rendering.


问:
Exponential map in the Lie vs. Riemannian category
Let $G$ be a Lie group with a bi-invariant metric. Then the exponential map at the identity in the Riemannian sense, $\operatorname{exp}(v)$, is the same as the exponential map in the Lie sense, $e^v$. In particular $1$-parameter subgroups $L=e^\ell$ corresponding to lines $\ell\subset T_eG$ are geodesics, but this may fail if only right (or left) invariant.

I would like to have an example of  this fact, to know if the result still holds if I restrict to a central subgroup $N\subset G$, and have a better reference than this (unreferenced) wiki article.

The question regarding the central subgroup is justified by the fact that any invariant metric on an abelian Lie group is automatically bi-invariant.

答:
You can really take your favorite nonabelian Lie group and any metric that isn't bi-invariant. The simplest example is
$$ G  = \left\{ \begin{pmatrix} a & b \\ 0 & a^{-1} \end{pmatrix} \mid a,b \in \mathbb{R} \right\} .$$

This group acts simply transitively by isometries on the hyperbolic plane $\mathbb{H}^2 = \{x+iy \mid y >0 \}$, and admits a (unique) left-invariant Riemannian metric making the orbit map an isometry. For that metric, the geodesics in $G$ correspond to the geodesics in the hyperbolic plane.

The one-parameter subgroups need not correspond to Riemannian geodesics. For example, the curve
$$ c(t) = \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix} \cdot i = t + i $$
is a horocycle.


问:
Are contours allowed to contain branch points / branch cuts on the contour (not inside)
I just wanted to verify something, since I saw some notes online that confused me. They were doing some contour integral and $0$ was the only branch point of the function, and they chose the branch cut connecting $0$ to ${+\infty}$ on the real axis. The contour they chose was a semi-circular contour. The part that confused me, was that at $0$ rather than just "go through" $0$ - they made some small $\epsilon$ semi-circle around $0$, but then allowed themselves to integrate along the branch cut. I thought that as long as the function is analytic at $0$ (which it was) - it's fine to integrate over a contour containing branch points/cuts on the contour? So long as you don't actually "cross" that branch cut or encircle any problematic branch points. Am I correct? Or is there a valid reason they did this? Thank you!

答:
One might say you shouldn't integrate along a branch cut since (depending on exactly how things are defined) the value of the function on the branch cut is ambiguous (it's one thing on one side of the cut, another thing on the other).  So integrate on a path that's very close to the branch cut (and on the side you want), and take the limit as your path approaches the branch cut.  The result should be the same as integrating along the branch cut (using the values that come from the side you want).

As for a path that goes through a branch point, as long as the function has a finite limit as you approach the branch point, there should be no problem.  Again you could avoid the branch point by taking a small detour around it, but in the limit as the size of the detour goes to $0$ you will get the same result.


问:
Meaning of the expression "$\mu$ a.e."
In the monotone convergence theorem:

Let $g_n\geq 0$ be a sequence of measurable functions, such that $g_n \uparrow g\;\; \mu \text{ a.e.},$ i.e. $g_n(\omega) \leq g_{n+1}(\omega)\;\; \mu \text{ a.e.},$ and $\displaystyle \lim_{n\to\infty} g_n(\omega) = g(\omega)\;\; \mu \text{ a.e.},$ then $\int g_n d\mu \uparrow \int g d\mu.$

I wrote the theorem just for context. And I understand that "$\text{a.e.}$" is a way of excluding sets or subsets that are not measurable, and that the measure is $\mu.$

But I don't see the intent or meaning of the expression $$\mu\text{ a.e.}$$

答: It means almost everywhere with respect to the measure $\mu$: for short, $\mu$-almost-everywhere. Id est, that the set of points where the condition fails is contained in a measurable set $S$ such that $\mu(S)=0$.

Title: Meaning of the expression "$\mu$ a.e."