问:
Throw a coin one million times. What is the expected number of sequences of six tails, if we do not allow overlap?
Question itself: Throw a coin one million times. What is the expected number of sequences of six tails, if we do not allow overlap?

I know when overlap is allowed, the answer is (1,000,000-5)/(2^6). Not sure if we can just do (1,000,000-5)/(2^6) divided by 6 if overlap is not allowed?

Some clarifications:

For example, if part of the sequence is "one H, nine T, then one H", we would count 1 sequence of six tails. (When overlap is allowed, we can count three times because each of the first 3 T can start a sequence of six tails; However, this question does not allow overlap, so 9T can only be counted as containing one sequence of six tails)

If part of the sequence is "one H, thirteen T, then one H", we would count 2 sequences of six tails.

答:
Comment. I'm not sure I've got the rules exactly right, but I did some checking
with simulation in R. The rle procedure in R (for Run Length Encoding)
gives run values (0s for Tails, 1s for Heads) and lengths.

For example:

```<code>set.seed(2021)
x = rbinom(10, 1, .5);  x
[1] 0 1 1 0 1 1 1 0 1 1
rle(x)
Run Length Encoding
  lengths: int [1:6] 1 2 1 3 1 2
  values : int [1:6] 0 1 0 1 0 1
rle(x)$len
[1] 1 2 1 3 1 2
</code>```

So it is easy to see how many runs of length 6 or greater we get in a particular session of a million
tosses of a fair coin. Replicating that 1000 times gives a rough idea of the
average number of such runs in a sequence of a million.

```<code>set.seed(202)
run.6 = replicate(1000, sum(rle(rbinom(10^6,1,.5))$len >=6))
mean(run.6)
[1] 15629.12
</code>```

The answer seems agreeably close to your $10^6/2^6  \approx 15\,625$ runs of length 6 or more.
But if we count runs of length 12 or more as two runs of 6 or more, the
desired number is a little larger, by about an additional 244 runs. There may
not be enough runs of length 18 or more to explore fruitfully by simulation (maybe about 4 more). [See @lulu's Comment.]

S0 roughly, you're going to get something close to $15625 + 244 + 4 = 15873$ runs
of the designated type in a sequence of a million tosses.

```<code>run.12 = replicate(1000, sum(rle(rbinom(10^6,1,.5))$len >=12))
mean(run.12)
[1] 243.97
10^6/2^12
[1] 244.1406
</code>```

Iterations of 10,000 or 100,000 sequences of a million tosses would give slightly more
accuracy, but my purpose here is to give rough estimates for you to
compare with your combinatorial results.

Body:
Comment. I'm not sure I've got the rules exactly right, but I did some checking
with simulation in R. The rle procedure in R (for Run Length Encoding)
gives run values (0s for Tails, 1s for Heads) and lengths.

For example:

set.seed(2021)
x = rbinom(10, 1, .5);  x
[1] 0 1 1 0 1 1 1 0 1 1
rle(x)
Run Length Encoding
  lengths: int [1:6] 1 2 1 3 1 2
  values : int [1:6] 0 1 0 1 0 1
rle(x)$len
[1] 1 2 1 3 1 2

So it is easy to see how many runs of length 6 or greater we get in a particular session of a million
tosses of a fair coin. Replicating that 1000 times gives a rough idea of the
average number of such runs in a sequence of a million.

set.seed(202)
run.6 = replicate(1000, sum(rle(rbinom(10^6,1,.5))$len >=6))
mean(run.6)
[1] 15629.12

The answer seems agreeably close to your $10^6/2^6  \approx 15\,625$ runs of length 6 or more.
But if we count runs of length 12 or more as two runs of 6 or more, the
desired number is a little larger, by about an additional 244 runs. There may
not be enough runs of length 18 or more to explore fruitfully by simulation (maybe about 4 more). [See @lulu's Comment.]

S0 roughly, you're going to get something close to $15625 + 244 + 4 = 15873$ runs
of the designated type in a sequence of a million tosses.

run.12 = replicate(1000, sum(rle(rbinom(10^6,1,.5))$len >=12))
mean(run.12)
[1] 243.97
10^6/2^12
[1] 244.1406

Iterations of 10,000 or 100,000 sequences of a million tosses would give slightly more
accuracy, but my purpose here is to give rough estimates for you to
compare with your combinatorial results.


问:
How to compute $P(Z_2 \le Z_3 \le Z_4| Z_2=Z_1 )$? where we have an i.i.d. sequence of standard normal $Z_1,Z_2,Z_3,Z_4$.
Suppose that we have an i.i.d. sequence of standard normal $Z_1,Z_2,Z_3,Z_4$. How to compute
\begin{align}
P(Z_2 \le Z_3 \le Z_4| Z_2=Z_1 )
\end{align}

My idea

\begin{align}
P(Z_2 \le Z_3 \le Z_4| Z_2=Z_1 ) =P( Z_1 \le Z_3 \le Z_4 ) =\frac{1}{3!}
\end{align}
The last step follow because there are $3!$ ways that arrange $Z_1,Z_3,Z_4$ and normal is symmetric.
However, I am not sure if the second step is fine and we can drop the conditioning?

答:
Partial answer that is too long for a comment:

Consider the joint distribution of $(Z_1-Z_2, Z_2)$. This is a bivariate normal distribution with means $0$ and $0$, variances $2$ and $1$, and correlation $-\frac{1}{\sqrt{2}}$. Thus it has the same distribution as $(2U, -\frac{1}{\sqrt{2}} U +\frac{1}{\sqrt{2}} V)$ where $U$ and $V$ are i.i.d. standard normal. (You can verify this by checking that the means, variances, and correlation are the same.)

So, the conditional distribution of $Z_2$ given $Z_1=Z_2$ is the same as the conditional distribution of $-\frac{1}{\sqrt{2}} U + \frac{1}{\sqrt{2}} V$ given $2U=0$. By plugging in $U=0$, we immediately see that the conditional distribution is $N(0, 1/2)$, as Brian Tung mentioned in the comments.

Thus you can rewrite your original probability as
$$P(\frac{1}{\sqrt{2}}V \le Z_3 \le Z_4)$$
where $V, Z_3, Z_4$ are i.i.d. standard normal. Some sort of volume/symmetry argument might allow you to compute this, but I'm not sure.

ContentLicense: CC BY-SA 4.0


问:
Expectation of derivative
Let $D$ be a random variable and $a_+=max(a,0)$. Can someone give a proof of how second line is derived from the fist line?

答:
The function $g(a) = \max(a,0) =:  [a]_{+}$ is differentiable at $a \neq 0$, with the derivative being given by $$g'(a) = \begin{cases} 1 & \text{if $a > 0$} \\ 0 & \text{if $a < 0$.}\end{cases}$$

Suppose that $z-D\neq0$ and $D-z\neq0$. Then $$\frac{\partial}{\partial z}[z-D]_+ = \begin{cases} 1 & \text{if $z-D>0$}\\ 0 & \text{if $z-D<0$} \end{cases}\quad\text{and}\quad \frac{\partial}{\partial z}[D-z]_+ = \begin{cases} -1 & \text{if $D-z>0$}\\ 0 & \text{if $D-z<0$} \end{cases}$$
using the chain rule. Note that $z-D>0$ iff $D<z$, and $D-z>0$ iff $D>z$. To proceed we have to assume that $\mathbb P(D = z) = 0$ for each $z$ (e.g. the distribution of $D$ is dominated by the Lebesgue measure). Then $$\begin{align*}\mathbb E\left[\frac\partial{\partial z}[z-D]_+\right] &= \int \frac\partial{\partial z}[z-D]_+\,\mathrm d\mathbb P\\ &= \int_{D<z} 1\,\mathrm d\mathbb P + \int_{D>z}0\,\mathrm d\mathbb P + \int_{D=z}1\,\mathrm d\mathbb P \\ &=\int_{D\leq z} 1\,\mathrm d\mathbb P + \int_{D>z}0\,\mathrm d\mathbb P \\ &= 1\cdot\mathbb P(D\leq z) + 0\cdot\mathbb P(D>z) \\ &= \mathbb P(D\leq z),\end{align*}$$
where the first equality is the definition of expectation, the second equality uses the fact that the sets $\{D<z\},\{D>z\}$ and $\{D=z\}$ are disjoint so the integral of the above function can be computed for each set separately.  As mentioned before, the derivative is not defined for $D=z$, so we have to come up with some value in order to compute the integral. However, since, by assumption, the set has probability zero anyway, it doesn't matter what function value we assign to this set - so why not take the value 1 to get to the third last equality. The second last equality is again simply the definition of the integral. Finally, the last equality is obvious.

The other one works analogously.

Title: Expectation of derivative


问:
How can I prove that for any sets A, B, C, D, that $(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$
I tested a few cases and it seems to check out, but I'm not sure how to prove that this statement is true.

$(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$

答:
Solving such a question can be done in a systematic way by decomposing into small steps.

First, let $x \in (A \cap B) \cup (C \cap D)$. Our aim is to prove that $x \in (A \cup C) \cap (B \cup D)$.

Our hypothesis $x \in (A \cap B) \cup (C \cap D)$ means that $x \in A \cap B$ or $x \in C \cap D$.

Case 1: $x \in A \cap B$. This means that $x \in A$ and $x \in B$. As $x \in A$ you get also that $x \in A \cup C$. As $x \in B$ you get also that $x \in B \cup D$. Hence $x \in A \cup C$ and $x \in B \cup D$, which yields $x \in (A \cup C) \cap (B \cup D)$.

Case 2: $x \in C \cap D$. It is the same principle. Try it!


问:
Smallest hexagonal lattice with no more than one point per unit Cartesian cell, as a function of rotation angle?
This answer to How to randomly but evenly distribute nodes on a plane introduces Bridson's Algorithm for Poisson-disc sampling (original paper: Fast Poisson Disk Sampling in Arbitrary Dimensions (also here) by Robert Bridson, University of British Columbia) Also see this and animation and explanation here.

I'm seeding the initial field with some regions with points on periodic lattices which will be both square and hexagonal, and of arbitrary rotation.

Bridson's method is characterized by a minimum distance $r$ that new points can be generated

For the algorithm to go fast, one chooses a square grid of side $r/\sqrt{2}$ which is small enough that there will always be either zero or one point in each cell. This way when a new point is introduced:

it must be introduced in a currently empty cell

only eight adjacent cells must be checked to evaluate the minimum distance to all existing points.

When I seed the space with preexisting array regions, I need to make sure that they never put more than one point in any cell.

Question: What are the constraints on lattice spacing $a$ and rotation angle $\theta$ for a hexagonal lattice with unit vectors:

$$\mathbf{a_1} =  a\cos \left(\theta \right) \ \mathbf{\hat{x}} + a\sin \left(\theta \right) \ \mathbf{\hat{y}}$$

$$\mathbf{a_2} =  a\cos \left(\theta +\frac{\pi}{3} \right) \ \mathbf{\hat{x}} + a\sin \left(\theta +\frac{\pi}{3} \right) \ \mathbf{\hat{y}}$$

such that there will never be more than one point in a unit square cartesian grid with any origin? (In other words, no matter how you translate the origin of the hexagonal lattice with respect to the cartesian grid.)

Rough example of application, for background only. Left: real space, right: reciprocal space (Fourier transform).

答:
I don't think one needs to go to tiling theory to solve this. It's just a question of the lattice constant being longer than the length of the chord of a unit square, with some fancy modulo 12 footwork, 12 being the least common multiple of the 4-fold and 6-fold symmetries.

$$a_{0°} = \frac{2}{\sqrt{3}} = \frac{1}{\cos30°} \approx 1.1547$$

$$a_{15°} = \frac{4}{\sqrt{6}+\sqrt{2}} = \frac{1}{\cos15°} \approx 1.0353$$

In general:

$$a(\theta) = \sec\left(30- |(\theta+15) \bmod 30 -15| \right)$$


问:
a little riddle, prime numbers and modulo
Is there a prime number $k$ , such that $k$  is not $1\bmod3$ , not $2
\bmod4$ , not $3\bmod5$ , not $5
bmod7$ etc..
Meaning, $k$ is not $n\bmod(n+2)$ for any $n=1,....,100000000$ ?

答:
The lower of any pair of twin primes greater than your limit.

Specifically, for a limit of $100000000$, the prime $100000037 $ is two less than the prime $100000039 $ so fulfills your requirement.


问:
If $X$ is a normed vector space and $U\subseteq X$, how do we show $(U^\perp)_\perp=\overline U$?
Let $\mathbb K=\mathbb R$ or $\mathbb K=\mathbb C$, $X$ be a normed $\mathbb K$-vector space. It is easy to see that $$U^\perp:=\{\varphi\in X':\langle x,\varphi\rangle=0\text{ for all }x\in U\}$$ is a closed subspace of $X'$ for all $U\subseteq X$ and $$V_\perp:=\{x\in X:\langle x,\varphi\rangle=0\text{ for all }\varphi\in V\}$$ is a closed subspace of $X$ for all $V\subseteq X'$.

I would like to show

If $U\subseteq X$ and $V:=U^\perp$, then $\overline U=V_\perp$.

If $V\subseteq X'$ and $U:=V_\perp$, then $\overline V=U^\perp$.

In 1. (resp. 2.) it is easy to show that $U\subseteq V_\perp$ (resp. $V\subseteq U^\perp$) and hence $\overline U\subseteq V_\perp$ (resp. $\overline V\subseteq U^\perp$).

Now I know the proof of the analogue result in the Hilbert space case, but this proof relies on the projection theorem and hence doesn't easily generalize to the present situation.

So, how do we show $V_\perp\subseteq\overline U$ (resp. $U^\perp\subseteq\overline V$)?

答:
The proof is greatly facilitated by noting that in general, $M_\perp:=\{x\in X:\langle x,\varphi\rangle=0\text{ for all }\varphi\in M\}$ is norm closed and that $N^\perp:=\{\varphi\in X':\langle x,\varphi\rangle=0\text{ for all }x\in N\}$ is weak$^*$ closed.

For example, Rudin proves the first part like this: by the remark, $\overline V\subseteq (V^{\perp})_{\perp}$. Now, if $x\notin \overline V$ then there is an $x\in V^{\perp}$ such that $\langle x,x^*\rangle \neq 0$ which says that $x\notin (V^{\perp})_{\perp}.$

The second part is similar.


问:
Is Bayes' Theorem really that interesting?
I have trouble understanding the massive importance that is afforded to Bayes' theorem in undergraduate courses in probability and popular science.

From the purely mathematical point of view, I think it would be uncontroversial to say that Bayes' theorem does not amount to a particularly sophisticated result. Indeed, the relation
$$P(A|B)=\frac{P(A\cap B)}{P(B)}=\frac{P(B\cap A)P(A)}{P(B)P(A)}=\frac{P(B|A)P(A)}{P(B)}$$
is a one line proof that follows from expanding both sides directly from the definition of conditional probability. Thus, I expect that what people find interesting about Bayes' theorem has to do with its practical applications or implications. However, even in those cases I find the typical examples being used as a justification of this to be a bit artificial.

To illustrate this, the classical application of Bayes' theorem usually goes something like this: Suppose that

1% of women have breast cancer;

80% of mammograms are positive when breast cancer is present; and

10% of mammograms are positive when breast cancer is not present.

If a woman has a positive mammogram, then what is the probability that she has breast cancer?

I understand that Bayes' theorem allows to compute the desired probability with the given information, and that this probability is counterintuitively low. However, I can't help but feel that the premise of this question is wholly artificial. The only reason why we need to use Bayes' theorem here is that the full information with which the other probabilities (i.e., 1% have cancer, 80% true positive, etc.) have been computed is not provided to us. If we have access to the sample data with which these probabilities were computed, then we can directly find
$$P(\text{cancer}|\text{positive test})=\frac{\text{number of women with cancer and positive test}}{\text{number of women with positive test}}.$$
In mathematical terms, if you know how to compute $P(B|A)$, $P(A)$, and $P(B)$, then this means that you know how to compute $P(A\cap B)$ and $P(B)$, in which case you already have your answer.

From the above arguments, it seems to me that Bayes' theorem is essentially only useful for the following reasons:

In an adversarial context, i.e., someone who has access to the data only tells you about $P(B|A)$ when $P(A|B)$ is actually the quantity that is relevant to your interests, hoping that you will get confused and will not notice.

An opportunity to dispel the confusion between $P(A|B)$ and $P(B|A)$ with concrete examples, and to explain that these are very different when the ratio between $P(A)$ and $P(B)$ deviates significantly from one.

Am I missing something big about the usefulness of Bayes' theorem? In light of point 2., especially, I don't understand why Bayes' theorem stands out so much compared to, say, the Borel-Kolmogorov paradox, or the "paradox" that $P[X=x]=0$ when $X$ is a continuous random variable, etc.

答: Not exactly an answer to the posted question, but Bayesian ideology is important in many practical problems in artificial intel, including character recognition, medical diagnoses, and more, the key structure being a Bayesian inference network.</p>


问:
Prove the sum of two different linear transformations is a linear transformation
How to prove that the sum of two different linear transformation is a linear transformation? I'm not too sure if I should use the properties of linear transformation to prove it?

I know that I have to end up with
(f1+f2)(x + y) = (f1+f2)(x) + (f1+f2)(y)
and
c(f1+f2)(x) = (f1 + f2)(cx)

but Im not too sure how to go between the begin and end statements.

答:
A function $f$ between two vector spaces $V$ and $W$ over the same field $K$ is linear iff $$f(\lambda u+v) = \lambda f(u) + f(v)$$ holds for each $u,v\in V$ and $\lambda\in K$.

So let $g$ and $h$ be two linear functions and let $u,v\in V$ and $\lambda\in K$. Then for the sum $f = g+h$, $$ f(\lambda u + v) = (g+h)(\lambda u + v) = g(\lambda u + v) + h(\lambda u+v)$$
using the definition of a sum of functions. Since $g$ and $h$ are by assumption both linear, $g(\lambda u +v) = \lambda g(u) + g(v)$ and $h(\lambda v + u) = \lambda h(v) + h(u)$. Thus,
$$g(\lambda u + v) + h(\lambda u+v) = \lambda g(u) + g(v) + \lambda h(u) + h(v) = \lambda g(u) + \lambda h(u) + g(v) + h(u)$$
Now apply again the definition of a sum of functions: $$\lambda g(u) + g(v) + \lambda h(u) + h(v) = \lambda g(u) + \lambda h(u) + g(v) + h(u) = \lambda (g + h)(u) + (g + h)(v) = \lambda f(u) + f(v)$$
and we are done.


问:
Quadratic form as sum of squares with fewer terms
Let $\ell_1,\dots,\ell_{m+n}$ be linear functionals over a finite vector space $V$. Suppose that
$$Q(x)=\ell_1(x)^2+\dots+\ell_m(x)^2-\ell_{m+1}(x)^2-\dots-\ell_{m+n}(x)^2$$
is a quadratic form with signature $(a,b,c)$. Show that $a\leq m$ and $b\leq n$.

By Sylvester's law, we know that there are (independent) linear functionals $f_1,\dots,f_{a+b}$ such that $$Q(x)=f_1(x)^2+\dots+f_a(x)^2-f_{a+1}(x)^2-\dots-f_{a+b}(x)^2.$$
So somehow we need to show that this representation is "minimal". I'm not really sure how to proceed from here.

I have tried to represent each functional in the form $\ell_i(v)=u_i\cdot v$ for some vector $u_i$, but this hasn't really helped.

答:
Let $d=\dim V$ and $K=\displaystyle\bigcap_{i=1}^m\ker\ell_i$.

Then $Q(x)\leq0$ for $x\in K$, so $\dim K\leq d-a$. Now let $T:V\to\mathbb R^m$ be the linear map
$$T(x)=(\ell_1(x),\ell_2(x),\dots,\ell_m(x)).$$
As $\dim\operatorname{im}T\leq m$, by rank-nullity $\dim\ker T\geq d-m$. But $K=\ker T$, so it follows that $$d-a\geq d-m\implies a\leq m.$$
Similarly, considering $\displaystyle\bigcap_{i=m+1}^{m+n}\ker\ell_i$ would imply that $b\leq n$.


问:
Definitions of Knot Theory
I am currently doing a course in Knot Theory and after looking at different texts I have found many ways to define knots and knot equivalence. In our course we are given the following definitions:

A knot $K\subseteq\mathbb{R}^{3}$ is a subset of the form $K=f(\mathbb{R})$ where $f:\mathbb{R}\rightarrow\mathbb{R}^{3}$ is a map with the following properties.

$f(x_{1})=f(x_{2})$ if and only $x_{1}-x_{2}\in\mathbb{Z}$

The derivative $\frac{d^{n}}{dx^{n}}f$ exists for all $n\in\mathbb{N}$

The derivative is not zero everywhere, $\frac{df}{dx}\neq 0$

Knots $K$ and $K^{\prime}$ are equivalent if there exists a collection of knots $K_{x}$ for each $x\in\left[ 0,1\right]$. such that $K_{0}=K$ and $K_{1}=K^{\prime}$, and such that there exists a smooth map $F:\left[ 0,1\right]\times \mathbb{R}\rightarrow\mathbb{R}^{3}$ with the property that $F(x,\cdot )$ represents $K_{x}$ in the sense of the previous definition.

I think I understand intuitively what is happening here and that this smooth map ensures that we make no illegal 'jumps'. I am at the same time taking a course in Algebraic Topology and for the sake of my note keeping I would like to give an alternative definition of equivalence more in line of homeomorphisms from Topology, which If im not mistaken is essentially what is going on here.

So I would say that two knots $K$ and $K^{\prime}$ are equivalent if there exists a homeomorphism $f:\mathbb{R}^{3}\rightarrow\mathbb{R}^{3}$ for which $f(K)=K^{\prime}$.

Would this definition be satisfactory, if not how could I change it? Is there any substantial difference from my definition and the one given by my lecturer?

答: As was pointed out in the comments, you need to differntiate mirror images to agree with your first definition. This is fixed by asking for an orientation-preserving homeomorphism $f: \mathbb{R}^3 \to \mathbb{R}^3$. See https://en.wikipedia.org/wiki/Knot_theory#Knot_equivalence, where it is also (briefly) explained why these two notions of equivalence are the same.

Title: Definitions of Knot Theory


问:
How to use substitution to solve a differential equation?
For this question, I'm stuck on how to implement a substitution. Can anyone help me out?

$(\sin(y)-y\sin(x))dx + (x\cos(y)+\cos(x))dy = 0 $

答:
This is an exact differential equation. An exact differential equation is an equation of the form:

$$P(x,y)dx +Q(x,y)dy=0 $$

where $P(x,y),Q(x,y)$ are $C^2$ (twice continuously differentiable) functions and we satisfy:

$$\cfrac{\partial P(x,y)}{\partial y}=\cfrac{\partial Q(x,y)}{\partial x}$$

We check that indeed:

$$\cfrac{\partial (\sin(y)-y\sin(x))}{\partial y}= \cos(y)-\sin(x)=\cfrac{\partial  (x\cos(y)+\cos(x))}{\partial x}$$

It is also clear that $P$ and $Q$ are also $C^2$, as $\sin$ and $\cos$ are actually $C^{\infty}$.

To solve, we can either solve a system of PDEs, given by the above condition, or calculate a line integral (integrating both sides of the equation, of course):

$$\Psi(x,y)=\int P(x,y)dx +Q(x,y)dy= \int (\sin(y)-y\sin(x))dx+(x\cos(y)+\cos(x))dy \implies$$

$$\Psi(x,y)=x\sin(y)+y\cos(x)=C$$

where I "absorb" the multiplier by $2$ into the arbitrary constant $C$.


问:
If $n$ is even, prove $P(x)$ cannot have an inverse function
If $P(x)$ is a polynomial of degree $n$, how can I prove that if $n$ is even, $P(x)$ cannot have an inverse function.

答:
$P(x)$ can be written as $P(x) = a_0 + a_1x + ... + a_nx^n,\ a_n \neq 0,\ $ for some even integer $\ n.$

By writing $P(x) = x^n\left( a_n + \frac{a_{n-1}}{x}+ ... + \frac{a_2}{x^{n-2}}+ \frac{a_1}{x^{n-1}}+ \frac{a_0}{x^n} \right),\ $ we see that $\displaystyle\lim_{x\to+\infty}P(x) = \displaystyle\lim_{x\to-\infty}P(x) = (\pm\infty)^n \times a_n = \infty \times a_n\ $ because $\ n\ $ is even, so both limits equal either $\ +\infty\ $ or $\ -\infty,\ $ depending on the sign of $\ a_n.\ $ Now suppose WLOG that $\ a_n>0,\ $ so that $\displaystyle\lim_{x\to+\infty}P(x) = \displaystyle\lim_{x\to-\infty}P(x)= +\infty\\ $ and let $x_1 \in \mathbb{R}.\ $ Then due to the continuity of $P(x)\ $ and the definition of $\displaystyle\lim_{x\to-\infty}P(x)= +\infty\ $ and $\displaystyle\lim_{x\to+\infty}P(x)= +\infty,\ \exists\ x'< x_1\ $ such that $P(x') = P(x_1) + 1,\ $ and $\ \exists\ x''> x_1\ $ such that $P(x'') = P(x_1) + 1,\ $ i.e. $P(x')=P(x''),\ $ showing that $P$ is not injective. Therefore $P(x)$ doesn't have an inverse function.


问:
Iteratively constructing Borel sets
From this post, given a collection of sets $\mathcal{C}_0$, we can construct $\sigma(\mathcal{C}_0)$ through an iterative process, where for each step we let $\mathcal{C}_\alpha$ be the collection of all countable unions and complements of sets from $\bigcup_{\beta < \alpha}\mathcal{C}_\beta$.

Let $\mathcal{C}_0$ be the collection of all intervals on the unit interval. What would be an example of a set that is in $\mathcal{C}_2$, but not in $\mathcal{C}_1$?

答: The Cantor set has these properties. It is the complement of a countable union of intervals so it is the complement of a set in $\mathcal C_1$. But it is not in $\mathcal C_1$ since it is neither the complemenet of an interval nor a counteble union of intervals. [Recall that $C$ has no interior and it is uncountable].

Title: Iteratively constructing Borel sets


问:
Smoothest zero-centered periodic function $f$ with $f(0) > 0$
I am looking at periodic functions $f$ on $[0,2\pi]$ satisfying these constraints:

$f(0) = 1$.

$f$ is zero-centered, i.e. its integral from 0 to $2\pi$ is 0.

$f$ is even. (More specifically, it's positive definite.)

$f$ has a continuous first derivative.

I suspect that there is some sense in which cosine is the the smoothest function satisfying these constraints, but I'm not sure how to appropriately define "smooth" here nor how to prove that cosine is the smoothest such function. Is there a known result along these lines?

答:
Well, if I use $S\triangleq\int_0^{2\pi}f''(t)^2dt$ as my measure of smoothness (smaller number means smoother function), I've verified that cosine isn't the smoothest function. If $f$ has a continuous first derivative then it is square integrable over $[0,2\pi]$, and hence its Fourier series converges. I then find that

$$S = 8\pi\sum_{k=1}^\infty k^4 a_k^2$$

where $f(t)=2\sum_{k=1}^\infty a_k \cos(k t)$ is the Fourier series for $f$. Subject to the condition that $f(0)=1$, i.e. $\sum_{k=1}^\infty a_k = 1/2$, I find that $S$ is minimized when $a_k\propto 1/k^4$ for all $k$.


问:
Does every Maximal Planar Graph have this Representation?
Can every Maximal Planar Graph be represented by 'inner' and 'outer' triangulations of a regular polygon?  For example for n vertices, draw a regular polygon with n vertices and n edges.  Triangulate the inside with n-3 edges and triangulate again on the outside without repeating connections, another n-3 edges. 3n-6 in total.  A proof seems to be obtained by taking a 'starting triangle' in the Maximal Planar Graph, adding a new vertex which joins two of the existing vertices, but doesn't enclose a vertex and repeating until all vertices are included, none should be 'inside'.  Perhaps this representation would be useful in some situations.  Is the 'proof' valid?</p>

答:
The proof is not valid. In particular, to add a new vertex, it doesn't just need to join two existing vertices, but ones that are adjacent around the polygon built so far; there is no guarantee that such a vertex exists.

The statement is not always true, either. The smallest counterexample is the Goldner–Harary graph shown below:

In this maximal planar graph, there simply is no cycle of length $n$ that visits every vertex once. A quick way to see that is to look at what happens when we delete the $5$ vertices marked with an $X$ below:

The result is $6$ isolated vertices. However, if you have an $11$-gon and delete any $5$ of its vertices, you'll leave the remaining $6$ vertices in $5$ or fewer pieces; there will be some edges between them left. So this graph cannot have an $11$-gon inside it. (In other words, the Goldner-Harary graph is not Hamiltonian because it's not $1$-tough.)


问:
I have a doubt about my text's calculation of $\lim_{x\rightarrow 0} \frac{\sqrt[4]{1-4x^2+x^4} -1+x^2}{x^4}$
I have a doubt about the calculation of a limit in my book.
I have this limit $$\lim_{x\rightarrow 0} \frac{\sqrt[4]{1-4x^2+x^4} -1+x^2}{x^4}$$

In my book it is said that $\sqrt[4]{1-t} \approx 1+ \frac{1}{4}t$ and then $\sqrt[4]{1-4x^2+x^4} \approx 1-x^2+\frac{1}{4}x^4$

I agree with $\sqrt[4]{1-t} \approx 1+ \frac{1}{4}t$ but when I do the derivative of $\sqrt[4]{1-4x^2+x^4} $ it is $\frac{1}{4}(1-4x^2+x^4)^{-\frac{3}{3}} \cdot (-8x+4x^3)$ and its value in $x=0$ is $0$ and not $\frac{1}{4}$,

while in the book the expression $-4x^2+x^4$ is merely put in the formulas without considering the fact that we have to do the derivative.

The calculation is not still good and we have to consider another term of the development to have the right value of the limit. Also in this case the book continues in this way. I've tried with wolfram alpha and actually the book is right, so there is something that I don't understand .
Can someone explain why I'm making mistakes? I'm not very good with this argument of Taylor development

答:
The example from your book is not precise, and draws some accurate conclusions and some inaccurate ones.

If your $\approx$ were actually $=$, then the book's conclusion would be obviously correct. You're just substituting $t=-x^2+\tfrac14 x^4$ into both sides of an equation. The unstated analogy is that while substituting the same thing on both sides preserves equality, it should also preserve approximate equality. To prove whether that's actually true or not requires a bit more about what approximate equality means.

The error in the approximation $\sqrt[4]{1+t} \approx 1+\tfrac14 t$ (which I guess is what you meant) is said to be "of order $t^2$". That means that the error in the approximation is proportional to $t^2$, as long as $t$ is sufficiently close to $0$. It follows that

$$\sqrt[4]{1-4x^2+x^4} \approx 1-x^2+\tfrac14x^4$$
with an error proportional to $(-4x^2 + x^4)^2$, which itself is proportional to $x^4$ when $x$ is small. This means that we can be sure that the terms up to $x^3$ in the expansion above are accurate, but not $x^4$ or higher. In fact, we can use the approximation:

$$\sqrt[4]{1+t} \approx 1+\tfrac14t - \tfrac{3}{32}t^2$$
which has error proprtional to $t^3$, to deduce that the $x^4$ coefficient should actually be $\tfrac14 - 16 \cdot\tfrac{3}{32} = -\tfrac54$, which is the true value of your limit.


答:
Element chase and cases.

Let $x\in (A\cap B) \cup (C\cap D)$.  then either Case 1: $x \in A\cap B$ or Case 2: $x \in C\cap D$ (or both)

Case 1: If $x \in A\cap B$ then $x \in A$.  And since $x \in A$ it will be true that $x$ is either in $A$ or in $C$ (because it IS in $A$) so $x \in A\cup C$.  And $x \in B$. And since $x \in B$ it will be true that $x$ is either in $B$ or in $D$ (because it IS in $B$) so $x \in B\cup D$.  So $x$ is in both $A\cup C$ and in $B\cup B$.  So $x \in (A\cup C)\cap (B\cup D)$.

Case 2: is done the same way will show that if $x \in C\cap D$ then $x \in (A\cup C)\cap (B\cup D)$.

So either way we will always get that if $x \in (A\cap B)\cup (C\cap D)  \implies x \in (A\cup C)\cap (B\cup D)$.  So that means $(A\cap B)\cup (C\cap D) \subset (A\cup C)\cap (B\cup D)$.

Title: How can I prove that for any sets A, B, C, D, that $(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$

Body:
I tested a few cases and it seems to check out, but I'm not sure how to prove that this statement is true.

$(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$


问:
Seminorm - Linear Algebra
let $E=C([0,3])=\{f:[0,3]\rightarrow \mathbb{R}\mid f \text{ is  continuous}\}$. Define $$\|f\| = \max_{x \in [1,2]} |f(x)|.$$

Prove that $\|f\|$ is a seminorm.

My attempt:

The first condition: $\|f\| \geq 0$. Well, it seems kinda obvious.

The second condition: I don't know if I can just assume that $$\|\lambda f\|=\max_{x \in [1,2]} |\lambda f(x)| = |\lambda| \max_{x \in [1,2]} |f(x)|=|\lambda|||f||.$$
We are working with continuous functions in a compact domain, so it seems "natural", but I still feel I'm missing some step.

The third condition: $$\max_{x \in[1,2]}|{f(x)+g(x)}|\leq \max_{x \in [1,2]} |f(x)|+ \max_{x \in [1,2]} |g(x)|.$$

I know that the triangle inequality holds for $\sup |f(x)+g(x)|\leq \sup |f(x)|+\sup |g(x)|$, can I just use the same logic?

Finally, how can I prove that this is not a norm? I'm trying to find a counterexample.

答: Everything is alright. A proof of the triangle inequality is completely the same. The difference is just that continuous functions attain their maximal values on a compact set. For counterexample just construct a continuous function on $[0,3]$ which is $0$ on $[1,2]$.

Title: Seminorm - Linear Algebra


问:
How to determine if this Differential Equation has a singular solution?
I found this Differential Equation $y'^2=16x^2$ and the text says it has a singular solution...

first they make an implicity derivation with respect to $y'$ then they have $2y'=0$. Therefore $y=constant$ and it proves that the D.E. has a singular solution but I can't figure out why it is correct.

答: This is a separable equation of the form $y' = f(y) g(x)$. If $f(y_0) = 0$, then $y = y_0$ is an equilibrium solution to the differential equation. However, if there is no equilibrium solution passing through the point $y = y_0$, then $y = y_0$ is a singular solution. In this case, we have $f(y)$ is a constant, so as you stated, $f'(y) = 0$. Therefore it must be true that if $y = y_0$ is an equilibrium solution, it solves the equation $16x^2 = 0$ for all $x$, which is impossible. Therefore, it is a singular solution for any value of $y_0 \in \mathbb{R}$.


问:
Does function symmetric to y-axis imply local min/max at x=0?
My question is as follows. Suppose $f:\mathbb{R}\rightarrow\mathbb{R}\in C^1$ on a small neighborhood $(-\delta, \delta)$ around $0$, with $\delta>0$. Also there are two converging sequences $\{x_i\}_{i=1}^\infty\rightarrow 0$ and $\{y_i\}_{i=1}^\infty \rightarrow 0$ such that $\ \forall i, x_i < 0, y_i > 0 \text{ and } f(x_i) = f(y_i)$. Then can we prove that $0$ is a local min/max, i.e. $\frac{\partial}{\partial x}f(x)|_{x=0} = 0$?

答:
Having a local min/max at $x=0$ is not equivalent to having zero derivative (also, you should use $\frac{d}{dx}$, not $\frac{\partial}{\partial x}$, because there are derivatives, not partial derivatives).  Also, note that your condition does not imply "symmetric to $y$-axis".

To give an example satisfying your conditions as written in the problem, take
$$f(x) = \left\{\begin{array}{ll}
x^2\sin\left(\frac{1}{x}\right)&\text{if }x\neq 0,\\
0 &\text{if }x=0.
\end{array}\right.$$
It is well-known that $f(x)$ is differentiable at $x=0$, with derivative equal to $0$; it is also clear that $f(x)$ does not have a local maximum or a local minimum at $0$, since $f(0)=0$ but $f$ takes both positive and negative values arbitrarily close to $0$. Finally, you can take $x_n = -\frac{1}{n\pi}$ and $y_n=\frac{1}{n\pi}$  to get the sequences satisfying your conditions.

Replacing the $f(x)$ with
$$g(x) = \left\{\begin{array}{ll}
\frac{x}{|x|}x^2\sin\left(\frac{1}{x}\right) &\text{if }x\neq 0,\\
0 &\text{if }x=0,
\end{array}\right.$$
likewise gives a function that is differentiable everywhere, has value $0$ at $0$,, is even (so it is symmetric about the $y$-axis), but takes both positive and negative values arbitrarily close to $0$ and so does not have a local extreme at $x=0$.

To prove that the derivative at $0$ will be $0$, however, we have:
$$\begin{align*}
f'_+(0) &= \lim_{n\to\infty}\frac{f(y_n)-f(0)}{y_n} = \lim_{n\to\infty} \frac{f(x_n)-f(0)}{y_n},\\
f'_-(0) &= \lim_{n\to\infty}\frac{f(x_n)-f(0)}{x_n}.
\end{align*}$$
Since $f$ is  differentiable at $0$, both limits exist and are equal. If $f'_+(0)\gt 0$, then for $n$ sufficiently large we must have $f(x_n)-f(0)\gt  0$ (since $y_n\gt 0$), but then $f'_-(0)\leq 0$ because for $n$ sufficiently large, $f(x_n)-f(0)\gt 0$ and $x_n\lt 0$.  This is impossible. A symmetric argument shows that we cannot have $f'_-(0)\lt 0$. Thus, $f'_-(0)=f'_+(0)=0=f'(0)$.


问:
completeness and saturation
Let $B$ a complete Boolean algebra. Suppose, for $\kappa$ cardinal, that $B$ is not $\kappa$-saturated. Then there exists a partition $W$ of $B$. Because of completeness, we have $B=\sum W\in B$. So $B$ is in an element of an element of $B$ ?</p>

答:
Yes. A partition is not a collection of subsets of $B$ as we commonly think of a partition. It is an antichain, it's a subset of $B$ with the property: $$u,v\in W\rightarrow u=v\ \text{ or }\ u\cdot v=0_B.$$

Since the Boolean algebra is complete, $\sum W$ is some element in $B$. If $W$ is a maximal antichain then $\sum W=1_B$.

The term partition corresponds to a partition of $A$, or a subset of $A$, when we think about $\mathcal P(A)$ as a Boolean algebra.

ContentLicense: CC BY-SA 3.0

Title: completeness and saturation


问:
The p-value of the test statistic in this problem is approximately equal to:
A survey claims that more than 8 out of 10 doctors recommend aspirin for their patients with
headaches. To test this claim, a random sample of 100 doctors’ results in 86 who indicate that they recommend aspirin.

A. 0.0521

B. 0.0802

C. 0.1231

D. 0.0721

E. 0.0668

So far I got:

Ho: P= 0.8

H1: P> 0.8

Z= (0.86-0.8)/0.4
= 1.50

If z= 1.50, cumulative probability is 0.9332

p-value= 2P(Z>zo)

= 2(1-0.9332)=0.1336

Correct answer seems to be 0.0668, which is half of 0.1336. Not sure where I went wrong

答:
$$\begin{split}
H_0:\pi=.8\\
H_1:\pi>.8
\end{split}
$$

The test statistic is $z^*=\frac{.86-.8}{.4}$

So far so good

You are conducting a one-sided test, so you are only interested in the probability to the right of $z^*$. There is no need to multiply the area by two. The pvalue is is $P(Z>z^*)= 1-0.9332=0.0668$

There is some evidence against the null, that is, it is slightly unlikely that the you would see a sample proportion of .86 if the null hypothesis were true. Therefore it's possible that the true population proportion is greater than .8.


问:
What does it mean when Newton's method encounters a non-invertible matrix?
I'm trying to solve some systems of polynomials. I'm using Newton's method as described here. But my code breaks if my initial guess or any subsequent iteration lands on a point which is a solution for some but not all of the functions.

For example, say I want to find $(x,y,z)$ such that:
$$
f_1(x,y,z)=x^2-z \\
f_2(x,y,z)=y^2-z \\
f_3(x,y,z)=z
$$
are all zero. (The solution is $(0,0,0)$.) I believe the Jacobian and inverse are:
$$
\boldsymbol{J}=
\begin{pmatrix}
2x &  0 & -1 \\
 0 & 2y & -1 \\
 0 &  0 &  1 \\
\end{pmatrix}
,
\boldsymbol{J}^{-1}=
\begin{pmatrix}
\frac{1}{2x} &  0           & \frac{1}{2x} \\
0            & \frac{1}{2y} & \frac{1}{2x} \\
0            &  0           & 1 \\
\end{pmatrix}
$$
If we happen to guess any starting point on $x=0$ or $y=0$, then the corresponding column of $\boldsymbol{J}$ becomes zero, and non-invertible. Or, $\boldsymbol{J}^{-1}$ would contain $\frac{1}{0}$.

Am I Doing It Wrong™? How should the algorithm proceed in this case? Or should I be using a different algorithm?

I found this question which seems to say that $\boldsymbol{J}$ should always be invertible, which I don't understand.

答: One thing you might try is to use the Moore-Penrose pseudoinverse of $J$ rather than the inverse.


答:
It is certainly true that $f'(0)=0$, because $f'$ is continuous at $0$ by hypothesis and any sequence $\xi_i\in(x_i,y_i)$ coming from Rolle's theorem satisfies $f'(\xi_i)=0$ for all $i$ and $\xi_i\to 0$.

Notice however that $$f(x)=\begin{cases}0&\text{if }x=0\\ e^{-x^{-2}}\sin \frac1{x^2}&\text{if }x\ne 0\end{cases}$$

satisfies your hypothesis (whatever they are), but $0$ is neither a local maximum nor a local minimum.

Title: Does function symmetric to y-axis imply local min/max at x=0?

Body: My question is as follows. Suppose $f:\mathbb{R}\rightarrow\mathbb{R}\in C^1$ on a small neighborhood $(-\delta, \delta)$ around $0$, with $\delta>0$. Also there are two converging sequences $\{x_i\}_{i=1}^\infty\rightarrow 0$ and $\{y_i\}_{i=1}^\infty \rightarrow 0$ such that $\ \forall i, x_i < 0, y_i > 0 \text{ and } f(x_i) = f(y_i)$. Then can we prove that $0$ is a local min/max, i.e. $\frac{\partial}{\partial x}f(x)|_{x=0} = 0$?


答:
I would do an expansion of the fourth root via the binomial theorem, up to order $2$:
$$\sqrt[4]{1+u} =1+\tfrac14u -\tfrac 3{32} u^2+o(u^2),$$
and subsituting $u=-4x^2+x^2$ to obtain
\begin{align}
\sqrt[4]{1-4x^2+x^4}&=1+\tfrac14(-4x^2+x^4)-\tfrac 3{32}(-4x^2+x^4)^2+o(x^4)\\
&=1-x^2 -\tfrac 54x^4+o(x^4),
\end{align}
whence
$$\frac{\sqrt[4]{1-4x^2+x^4} -1+x^2}{x^4}=\frac{-\frac54 x^4+o(x^4)}{x^4}=\color{red}{-\frac54}+o(1).$$

Title: I have a doubt about my text's calculation of $\lim_{x\rightarrow 0} \frac{\sqrt[4]{1-4x^2+x^4} -1+x^2}{x^4}$

Body:
I have a doubt about the calculation of a limit in my book.
I have this limit $$\lim_{x\rightarrow 0} \frac{\sqrt[4]{1-4x^2+x^4} -1+x^2}{x^4}$$

In my book it is said that $\sqrt[4]{1-t} \approx 1+ \frac{1}{4}t$ and then $\sqrt[4]{1-4x^2+x^4} \approx 1-x^2+\frac{1}{4}x^4$

I agree with $\sqrt[4]{1-t} \approx 1+ \frac{1}{4}t$ but when I do the derivative of $\sqrt[4]{1-4x^2+x^4} $ it is $\frac{1}{4}(1-4x^2+x^4)^{-\frac{3}{3}} \cdot (-8x+4x^3)$ and its value in $x=0$ is $0$ and not $\frac{1}{4}$,

while in the book the expression $-4x^2+x^4$ is merely put in the formulas without considering the fact that we have to do the derivative.

The calculation is not still good and we have to consider another term of the development to have the right value of the limit. Also in this case the book continues in this way. I've tried with wolfram alpha and actually the book is right, so there is something that I don't understand .
Can someone explain why I'm making mistakes? I'm not very good with this argument of Taylor development


问:
Can An Odd Set of Ordered Elements With this Specified Operation Arrive at any Permutation?
Sorry for the wordy or ambiguous title - I'm not super jargon familiar. Tags/better title suggestions accepted. Here is the set-up (from a game of Magic: the Gathering, no less):

Set L is of size n where n is odd. For simplicity, let set L be the integers from 1 to n:
$$L=(1,2,...,n)$$

If I define two functions such that:
$f(L)= (3,4,...,n,1,2)$ and $g(L) = (3,4,....,n,2,1)$

is it possible, through combinations of $f$ and $g$, to arrive at any desired ordering or permutation of $L$?

Non-mathy, Magic: the Gathering version: I can take the top two cards of my deck and put them on the bottom in any order I want, and I can do this any number of times. Can I sort my deck?

答:
Yes. Let's fix an initial ordering of your library $a_1,...,a_n$ where $a_1$ is the top card and $a_n$ is the bottom card and $n$ is odd. It can shown that any permutation can be written as the product of transpositions which are just permutations in which two elements are swapped and everything else stays the same. We will show that we can make an arbitrary transposition using the given operation.

Fix $i,j \in \{1,...,n\}, i < j$. We can repeatedly put the top two cards on the bottom in the same order until we reach the $a_i$ is in the top card (note that you  have to go through your deck twice to achieve this if $i$ is even). Then put $a_i$ and $a_{i+1}$ on the bottom of your library in the opposite order. So the new order of your deck will be (starting with the top card)
$$
a_{i+2}, a_{i+3},...,a_j,...,a_{i+1},a_i
$$
Each time you do this you effectively move $a_i$ one card closer to $a_j$, while leaving the order of the remaining cards in place. Eventually the top of your deck is $a_i,a_j$, so then you can swap those two and put them on the bottom. Now your ordering looks like $$...a_{j-1},a_i,a_j,a_{j+1},...$$
. Now we repeat the process of putting the top two cards on the bottom in the same order until $a_j$ is second from the top, then we put the top two cards of our library on the bottom swapping the order and essentially moving $a_j$ towards the initial location of $a_i$, while leaving the rest of the order in place. Thus we have been able to generate an arbitrary transposition, and can achieve any permutation (i.e. you can stack your deck).

This is not necessarily the most efficient way of achieving an arbitrary permutation, but it is deterministic, so you should be allowed to just stack your deck.


答:
$$(\sin(y)-y\sin(x))dx + (x\cos(y)+\cos(x))dy = 0$$
$$(\sin(y)-y\sin(x)) + (x\cos(y)+\cos(x))\color {red}{\dfrac {dy}{dx}} = 0$$
Regroup some terms:
$$\sin(y)-y\sin(x) + (x\cos(y)+\cos(x))y' = 0$$
$$ {\sin(y)}-\color {blue} {y\sin(x)} + \color {blue} {(\cos(x)y'}+{x(\sin y)')} = 0$$
$$\color{green}{\sin(y)} +\color {blue} { (\cos(x)y)'}+\color{green}{x(\sin y)' }= 0$$
$$\color {green} {(x\sin(y))'} + (\cos(x)y)' = 0$$
After integration:
$$x\sin(y) + \cos(x)y = C$$

Title: How to use substitution to solve a differential equation?

Body:
For this question, I'm stuck on how to implement a substitution. Can anyone help me out?

$(\sin(y)-y\sin(x))dx + (x\cos(y)+\cos(x))dy = 0 $


问:
Self-adjoint and eigenvalues properties
I wondering about something.

Let $V$ be an inner product space

$T\colon V\to V$ is a linear map

$T$ is self-adjoint and all the eigenvalues of $T$ are not negative

I need to prove that for all $v$ in $V$, $(T(v),v)\ge0$.

So I think that if all the eigenspaces of all the eigenvalues span $V$ I am done (It is very easy).

But who can promise that? I do not know any theorem like that (am I wrong ?).

So which theorem can I use? All I know is that eigenvectors from different eigenspaces are orthogonal and nothing more.

答:
There is a theorem, that says that self-adjoint maps are allways diagonalizable, so there an eigenbasis and you are done.

Let's sketch the proof: Let $\lambda\in \mathbb C$ be an eigenvalue of $T$, $E_\lambda := \ker(\lambda- T)$ the eigenspace. Then $E_\lambda$ is $T$-invariant, and by self-adjointness, its orthogonal complement $E_\lambda^\bot$ is also: For $v \in E_\lambda^\bot$, $w \in E_\lambda$, we have
$$ (Tv, w) = (v,Tw) = (v,\lambda w) = 0$$
so $Tv \in E_\lambda^\bot$. If we restrict $T$ to $T' \colon E_\lambda^\bot \to E_\lambda^\bot$, we can inductively find a $T$-eigenbasis of $E_\lambda^\bot$ and are done.

Title: Self-adjoint and eigenvalues properties


问:
For A,B,C,and D sets. Is it true that $(A - C) \times (B - D) \subset (A \times B) - (C \times D)$ proof verification
I claim that $(A - C)  \times (B - D) \subset  (A \times B) - (C \times D)$.

Let $(x,y) \in (A - C)  \times (B - D)$. It means that $x \in (A - C)$ and $y \in (B - D)$. This implies that $x \in A$ and $y \in B$ such that $x$ and $y$ doesn't exist in C and D respectively. Therefore $(A - C)  \times (B - D) \subset  (A \times B) - (C \times D)$.

I haven't found counter example yet but it should be true that this is strict inclusion.

答:
With $C = \emptyset$, and $A,B,D$ non-empty with $B = D$, you get

$(A \setminus C) \times (B \setminus D) = \emptyset \subsetneq A \times B = (A \times B) \setminus (C \times D)$


问:
Countably generated sigma algebra vs. generated by a real-valued random variable
Dear StackExchange community

Given an arbitrary probability space ($\Omega, \Sigma, P$) (without a topological structure), is it true that for any countably generated sub sigma algebra there exists a real-valued random variable that generates it?

After researching this question, I came up with mixed results.

I know there is this post
Every countably generated sigma algebra is generated by a random variable, but it seems to me that the proof makes implicit use of some topology on $\Omega$

This text https://arxiv.org/pdf/0809.3066.pdf (Prop. 3.2) states that a
sigma algebra is countably generated iff it is generated by a mapping
($\Omega, \Sigma$) $\rightarrow$ ({$0,1$}$^\mathbb{N}$, Borel sigma
algebra on {$0,1$}$^\mathbb{N}$), which is not the same as our usual real-valued random variable
$(\Omega, \Sigma) \rightarrow (\mathbb{R},$ Borel sigma algebra on $\mathbb{R}$)

Why this matters: Several results on the existence of regular conditional probability make use of the condition "$\Sigma$ is countably generated". Life would have been much easier if we could replace this condition with "$\Sigma$ = $\sigma (X)$ for some real-valued random variable $X$" (because $\sigma (X)$ has some nice properties).

答:
$\{0,1\}^{\mathbb N}$ is  a Polish space with the same cardinality as $\mathbb R$. Hence, there is a bijection  $f: \{0,1\}^{\mathbb N}  \to \mathbb  R$  such that $f$ and $f^{-1}$ are measurable (for the Borel sigma algebras on both sides). Composing a $\{0,1\}^{\mathbb N}$  valued measurable function with this $f$ gives the answer.

Reference for existence of $f$: Measure Theory by Cohn.


问:
Convergence of trigonometric sums over the non-trivial Zeta zeros
There is video by B. Conrey where he discusses trigonometric sums of the form:

$\sum_{n=1}^\infty \cos(\gamma_n*\ln(x))$

He indicates that they have support on the prime powers: eg, 33:55 in https://www.youtube.com/watch?v=OS2V6FLFmxU

There is also a book by Mazur and Stein "Prime Numbers and the Riemann Hypothesis" (M&S) where they discuss these sums - referenced as:

$\sum_{i=1}^\infty \cos(\log(x)*\theta_i)$

The numerical evidence in M&S is compelling, but i cant see a reference to a proof that the series converge (even conditionally). They do have some end notes where they say that the phenomena is a result of the "explicit formulation", but i do not believe there is a proof of convergence.

is it known that these series converge?

if they converge in the sense of distributions, how would one prove that?

are there similar expressions which sum over the non-trivial zeros which do converge to something with support at the prime powers (not the sum of prime powers)?

thank you

答:
The series diverges in the usual sense for every $x$,

but it converges in the sense of distributions on $(0,\infty)$, under the RH the limit is $\frac12\sum_n \Lambda(n)n^{-1/2}(\delta(\log x-\log n)+\delta(\log x+\log n))$ plus some 'trivial' terms.


问:
How to derive or logically explain the formula for curl?
Most books state that the formula for curl of a vector field is given by $\nabla \times \vec{V}$ where $\vec{V}$ is a differentiable vector field. Also, they state that: "The curl of a vector field measures the tendency for the vector field to swirl around".

But, none of them state the derivation of the formula. In other words : "How can we derive the formula for the quantity which measures the tendency for the vector field to swirl around" ?

答:
This is an answer for the 2-dimensional curl only.  Hopefully one can turn it into a general argument for 3 dimensions.

Consider a perfect rotation of the plane around the origin, in which, at time $t$,  a point $(x,y)$ is sent to
$$
  R_t(x,y) =
  \left[\matrix {\cos(\omega t) & -\sin(\omega t) \cr \sin(\omega t) & \hfill\cos(\omega t)}\right]
  \left[\matrix {x \cr y }\right] =
  \left[\matrix {x\cos(\omega t)  -y \sin(\omega t) \cr x\sin(\omega t) + y\cos(\omega t)}\right].
  $$

Observe that each point completes a full turn, namely $2\pi $ radians, as $t$ goes from zero to $2\pi /\omega $, so the angular velocity is
$$
  \frac{\Delta \theta }{\Delta t} = \frac{2\pi }{2\pi /\omega } = \omega .
  $$

The linear velocity vector at time zero of each point $(x, y)$ is given by
$$
  \left.\frac d{dt}\right|_{\, t=0}  R_t(x,y) =
  \left[\matrix {-\omega x\sin(\omega t)  -\omega y \cos(\omega t) \cr
  \hfill \omega x\cos(\omega t) - \omega y\sin(\omega t)}\right]_{\, t=0} =
  \left[\matrix {-\omega y \cr \hfill \omega x}\right],
  $$
so the velocity vector field may be represented by
$$
  F(x,y) = (-\omega y,\omega x) = \omega (-y,x).
  $$

Given any point $(x, y)$ in the plane, let $C$ be  the circle about the origin passing thru $(x,y)$, and observe that
the unit vector $\vec t\ $ tangent to $C$ at $(x,y)$ is given by

If we project   $F(x,y)$ onto this vector (notice that these vectors are parallel, although in the more general situation
we are about to consider  they might not be), we get the component of $F(x,y)$ that is causing a rotation around the origin, which is then given by
$$
  \langle F(x,y),\vec t\ \rangle  =
  \left\langle (-\omega y,\omega x), \frac{(-y, x)}{\|(x, y)\|} \right\rangle   =
  \frac{\omega (y^2+x^2)}{\|(x, y)\|} =
  \omega \|(x, y)\|.
  $$
Consequently we may estimate the value of $\omega $ in terms of the vector field at any point $(x,y)$  by the simple formula
$$
  \omega  = \frac{\langle F(x,y),\vec t\ \rangle }{\|(x, y)\|}.
  \tag 1
  $$

If,  instead of the origin, we consider a rotation about another point $(x_0, y_0)$, so that
$$
  R_t(x,y) =
  \left[\matrix {x_0 \cr y_0 }\right] +
  \left[\matrix {\cos(\omega t) & -\sin(\omega t) \cr \sin(\omega t) & \hfill\cos(\omega t)}\right]
  \left[\matrix {x-x_0 \cr y-y_0 }\right] =
  \left[\matrix {x_0 +  (x-x_0)\cos(\omega t)  -(y-y_0) \sin(\omega t) \cr y_0 +(x-x_0)\sin(\omega t) + (y-y_0)\cos(\omega t)}\right],
  $$
the corresponding velocity vector field would be given by
$$
  F(x,y) = \omega (-y+y_0,x-x_0),
  $$
while   estimate (1) would be written as
$$
  \omega  = \frac{\langle F(x,y),\vec t\ \rangle }{\|(x-x_0, y-y_0)\|},
  \tag 2
  $$
where $\vec t$ is now given by
$$
  \vec t = \frac{(-y+y_0, x-x_0)}{\|(x-x_0, y-y_0)\|}.
  $$

Now suppose we are presented with an arbitrary vector field on the plane, say
$$
  F(x,y) =\big (P(x,y),Q(x,y)\big ),
  $$
and we want to estimate how much it rotates about a point $(x_0, y_0)$.

Notice that (2) would no longer  be of much use since the field might perhaps be constant, meaning that  all points are moving along
the same direction, without any rotation taking place, and still the RHS of (2) could yield a meaningless big value of $\omega $.

If you hold a child by the hand when strolling,   you might not know whether they are walking straight or dancing around.  But if the parents each hold one hand, it is much easier to tell!

To account for this,  let us choose many points,  rather than just one, and average the outcomes of (2) for these
points.  A reasonable choice would be four points, to the right, to the left, above and below the point  $(x_0,y_0)$
under consideration.

Fixing  a parameter $h>0$, let us then consider the following four points
$$
  \matrix{
  (x_1, y_1) &=& (x_0+h, y_0) & \quad \text{(right)} \cr
  (x_2, y_2) &=& (x_0-h, y_0) & \quad \text{(left)}  \cr
  (x_3, y_3) &=& (x_0, y_0+h) & \quad \text{(above)} \cr
  (x_4, y_4) &=& (x_0, y_0-h) & \quad \text{(below)}
}
  $$

Regarding   $(x_1, y_1)$, for example, we would have
$$
  \vec t = (0, 1),
  $$
so
$$
  \omega _1 =
  \frac{\langle F(x_0+h,y_0),(0, 1)\rangle }{\|(h, 0)\|} =
  \frac{Q(x_0+h,y_0)}h.
  $$
Averaging the four  angular velocity  estimates $\omega _1$, $\omega _2$, $\omega _3$, and $\omega _4$,  we get
$$
  \frac {\omega _1+ \omega _2 +\omega _3 + \omega _4}4 =
  \frac { Q(x_0+h,y_0) - Q(x_0-h,y_0) - P(x_0,y_0+h) - P(x_0,y_0-h)}{4h}.
  $$
In order to compute  the infinitesimal  angular velocity at $(x_0,y_0)$ we take the limit as $h\to 0$, which we may
compute using L'Hopital rule, leading up to
$$
  \lim_{h\to 0_+}  \frac {\omega _1+ \omega _2 +\omega _3 + \omega _4}4 =
  \frac 1 4 \left(\frac {\partial Q}{\partial x}(x_0,y_0) + \frac {\partial Q}{\partial x}(x_0,y_0)
  - \frac {\partial P}{\partial y}(x_0,y_0) - \frac {\partial P}{\partial y}(x_0,y_0)\right) = $$$$ =
  \frac 1 2 \left(\frac {\partial Q}{\partial x}(x_0,y_0) - \frac {\partial P}{\partial y}(x_0,y_0)\right) =
  \frac 1 2 \text{ curl }F(x_0,y_0).
  $$

Although I was brought up as a mathematician, I was always much irritated when professors introduced new
concepts named after physically significant phenomenon without explaining in depht where   the motivation for the
name came from.  Some of my first
disapointments occured precisely when I was first confronted with the notions of gradient, divergent and curl.

Searching for an explanation does not always bring about any light and this in fact makes me suspect that lots of grown ups
have been force fed these concepts to the point that they eventually seem natural,  after which one no longer feels the  need for any further explanations.

Take the MIT course mentioned in @symplectomorphic's answer,  for example.
There, Green's Theorem is used to explain that the 2-dimensional curl is related to the angular velocity of a small
paddle wheel.  Could Green's Theorem historically have come before the notion of curl?
To me this makes no sense as it  might give  students the impression that Green first obtained his formula out of the blue and then, as an
afterthought, realized that his Theorem could be used to deduce that the  curl represents the rotation of a vector field.


问:
How to compute $P(Z_2 \le Z_3 \le Z_4| Z_2=Z_1 )$? where we have an i.i.d. sequence of standard normal $Z_1,Z_2,Z_3,Z_4$.
Suppose that we have an i.i.d. sequence of standard normal $Z_1,Z_2,Z_3,Z_4$. How to compute
\begin{align}
P(Z_2 \le Z_3 \le Z_4| Z_2=Z_1 )
\end{align}

My idea

\begin{align}
P(Z_2 \le Z_3 \le Z_4| Z_2=Z_1 ) =P( Z_1 \le Z_3 \le Z_4 ) =\frac{1}{3!}
\end{align}
The last step follow because there are $3!$ ways that arrange $Z_1,Z_3,Z_4$ and normal is symmetric.
However, I am not sure if the second step is fine and we can drop the conditioning?

答:
Here's a more direct approach. Let $E=\{Z_1=Z_2\}$ and $h(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Notice $(Z_1,Z_2,Z_3,Z_4)\sim f$ where $$f(x,y,z,w)=h(x)h(y)h(z)h(w)$$ The conditional distribution of $(Z_1,Z_2,Z_3,Z_4)$ given $E$, denoted by $f_{E}$, equals $$f_{E}(z_2,z_3,z_4)=\frac{f(z_2,z_2,z_3,z_4)\sqrt{2}}{\iiint_{\mathbb{R}^3}f(z_2,z_2,z_3,z_4)\sqrt{2}dz_4dz_3dz_2}$$ The probability you're trying to compute is $$P(Z_2 \leq Z_3 \leq Z_4|Z_1=Z_2)=\int_{-\infty}^{\infty} \int_{z_2}^{\infty} \int_{z_3}^{\infty} f_{E}(z_2,z_3,z_4)dz_4dz_3dz_2$$ This is approximately 15.2%

Remark: The $\sqrt{2}$ represents the "surface area component" for the parametric surface $\vec{r}(u,v,w)=(u,u,v,w)$ whose trace is $$\Big\{(z_1,z_2,z_3,z_4)\in \mathbb{R}^4\Big|z_1=z_2\Big\}$$


问:
Ito's Lemma: from $df$ to $df^2$ to get $\operatorname{Var}[df]$
Consider the stochastic process
\begin{align*}
dX_t&=\mu_t dt+\sqrt{Y_t}X_t dB_t \\
dY_t&=m_t dt+s\sqrt{Y_t} dW_t
\end{align*}
where $dB_tdW_t=\rho dt$, $s$ is a constant and $\mu_t$ and $m_t$ are well-behaved drifts.

According to Ito's formula:
\begin{align*}
df(X_t,Y_t) &= \left(\frac{1}{2}Y_tX_t^2f_{xx}(X_t,Y_t)+\rho s Y_tX_t f_{xy}(X_t,Y_t)+\frac{1}{2}s^2Y_tf_{yy}(X_t,Y_t)+\mu_t f_x(X_t,Y_t)+m_t f_y(X_t,Y_t)\right)dt \\
&\;\;\;\;\; +\sqrt{Y_t} X_t f_{x}(X_t,Y_t)dB_t+s\sqrt{Y_t} f_{y}(X_t,Y_t)dW_t.
\end{align*}
My question: Is the following assertion correct?
\begin{align*}
df(X_t,Y_t)^2 &= \bigg( Y_t X_t^2f_{x}(X_t,Y_t)^2+2\rho s X_tY_t f_{x} (X_t,Y_t)f_y(X_t,Y_t)+s^2 Y_t f_y(X_t,Y_t)^2\bigg)\text{d}t
\end{align*}
This expression then gives $\operatorname{Var}[df]=E[df^2]-E[df]^2=E[df^2]=df^2$, because $E[df]$ is of order $dt$ and squaring it makes it negligible whereas $df^2$ is non-random.

答:
Just to mark this question as answered:

@Lutz agrees that the equation in the question is correct
\begin{align*}
df(X_t,Y_t)^2 &= \bigg( Y_t X_t^2f_{x}(X_t,Y_t)^2+2\rho s X_tY_t f_{x} (X_t,Y_t)f_y(X_t,Y_t)+s^2 Y_t f_y(X_t,Y_t)^2\bigg)dt.
\end{align*}


问:
Meaning of Summation Symbol in set theory
This might seem basic or too simple to ask, but I cant find it in my university lectures or exercises. Here is the part I dont understand:

Let $(A_i)_{i\in\{1,2,3\}}$ be a family of sets with $A_1= \{4,5,6\},~A_2 = \{a, b, c, d\}$ and $A_3 = \{a, 4, 40\}$

Construct the two Sets:

(i) //This wasnt a problem

(ii) $\sum_{i\in\{1,2,3\}} A_i$

I dont understand the usage of the summation symbol in this context and couldnt find any sources online with a similar task.

I dont think $\{(4, a), (5, b, 4),\ldots\}$ is correct, since its not a cartesian product. I am a beginner, so excuse the simple question :)

答:
Usually the sum notation for sets means that you take disjoint unions. For example $\{a\} \cup \{a\} = \{a\}$ whereas $\{a\} + \{a\} = \{a_1,a_2\}$ (you make two different copies of $a$). Adding sets amounts to taking their union, but while forcing them to be disjoint.

Formally: $\sum_{i \in I} X_i = \{(i,x) \mid i \in I, x \in X_i \}$


问:
Convergence of a filter defined in a subspace
I am reading about convergence of filters in topological spaces and cluster points. My doubt is the following: let $X$ be a topological space, $A\subset X$ and $\mathcal F$ a filter on $A$. Given $x \in \overline A$, what is the meaning of $\mathcal F \longrightarrow x$?

Bourbaki defines the convergence of a filter (page 68 - topology 1) which is defined in the whole space $X$. Of course that is not the case of $\mathcal F$ if $A\ne X$. But in Proposition 6 of page 70 they use this kind of convergence. I am assuming that this means that  $\mathcal F$ is finer than $\mathcal B(x)_A$, which is the trace of the filter of the neighborhoods of $x$. Is that correct? I found it very strange since Bourbaki's book (as far as I know) does not make this kind of imprecision (to work with a not given definition).

In Dugundji's book only the definition of convergence of a filterbase is given (Def. 2.1 of Chapter 10). So his Theorem 4.1 (that is the cited proposition of Bourbaki's book) is coherent.

答:
$\mathscr F\to x$ means that $\mathcal{N}_x\subset\mathscr F$, where $\mathcal N_x$ is the filter of neighbourhoods of $x$.

The fact that $x\in \overline A$ can be characterized in terms of convergence of filters. Indeed, $x\in \overline{A}$ iff there is some filter $\mathscr{F}\to x$ such that $A\in \mathscr{F}$.

$\Rightarrow$) Let $x\in \overline{A}$. For every $N\in\mathcal N_x$, $N\cap A\neq \emptyset$, so that $\{N\cap A:N\in\mathcal N_x\}$ is a filter base. Let $\mathscr F$ be the filter generated by it. Obviously, $A\in\mathscr F$.

$\Leftarrow$) Let $N\in\mathcal N_x$. Then $N\cap A\in\mathscr F$, so that $N\cap A\neq\emptyset$. This says that $x\in \overline A$.


问:
Fast modular exponentiation with factorial
I have a task 50!+7^133 mod 5.

I know that 7^133(mod5)=2(mod5) because:

7=2(mod5)

7^2=4(mod5)

7^3=3(mod5)

7^4=1(mod5)

7^133= 7^(433+1)=(7^4)^337^1=1*2=2(mod5)

I'm not quite sure how can I calculate 50 in factorial. Any tips?

答:
If $a \le b$ then
$b! \equiv 0 \bmod a$.

In this problem,
$50! \equiv 0 \bmod 5$.


问:
Invertible positive elements
In a $C^*$-algebra ${\cal A}$, I know that $a\in {\cal A}_+$ if and only if $a=x^*x$ for some $x\in {\cal A}$.

Question: If we know that $a$ is also invertible, can we choose $x$ to be invertible? It certainly is true for matrices.

答:
@MikeF's comment is certainly the default answer to your question, but here is an argument which does not need square roots.

If $a$ is invertible and positive, then it also has these properties relative to the commutative C*-algebra generated by $a$ and $1$ (can you prove this?).

Therefore you may find $x$ inside that subalgebra, and hence $x$ and $x^*$  commute.

From the expression $a=x^*x$ you deduce that $x$ is left-invertible, and from $a=xx^*$, that $x$ is right-invertible.  It then follows that $x$ is invertible.

Title: Invertible positive elements


问:
Why does the threshold for most properties in Erdős-Rényi graphs tend to decrease with increasing nodes?
The threshold (edge probability) for certain properties such as diameter two ($\sqrt{2\frac{lnn}{n}}$) are dependent on number of nodes in Erdős-Rényi graphs. Because of which as $n \to \infty$, the threshold edge probability seems to be lower and lower. How does that make any sense? How does small edge probability ensure that the graph is not just connected but also has two hops? What am I missing here?

答: The property you chose, diameter 2, is a good example. There are two competing considerations: For two fixed nodes $x,y$, there are about $n$ (more precisely, $n-2$) potential paths between them; the threshold for one of these paths being available (retained, or open) is $n^{-1/2}$.  Guaranteeing such a path for every pair is what costs the additional logarithmic factor.


问:
What do you do if part of your math equation is undefined?
I have to write trigonometry problems for my math project, and I ended writing one I couldn't solve: $sin(sin^{-1} \ 60 ^\circ + sin^{-1} \frac{3}{5})$.
I'll take you as far as I can.

$sin(sin^{-1} \ 60 ^\circ + sin^{-1} \frac{3}{5}) = sin(sin^{-1} \ 60 ^\circ)*cos(sin^{-1} \frac{3}{5}) +cos(sin^{-1} \ 60 ^\circ) * sin(sin^{-1} \frac{3}{5})$

$undefined * \frac{4}{5} + undefined * \frac{3}{5}$

Is the answer really just undefined? Why is that that? Why can't I take an angle as an input?

Edit: yes, I know I could just have used a valid argument, but I wanted to see what would happen.

答:
"$\sin^{-1}(60^\circ)$" does not make (too much) sense. It is the functions $\sin, \cos, \tan$ etc. that take an angle as an argument: not $\sin^{-1}, \cos^{-1}, \tan^{-1}$. Those latter functions produce angles as their output.

One could formally try to plug the number $60$, or perhaps the number $\pi/3$ (knowing that $60^\circ=\pi/3$) into $\sin^{-1}$ (which is probably what your calculator tried): the result will be defined only if the number you are plugging is between $-1$ and $1$, otherwise the result is undefined. (Note $\pi/3\approx 3.1416\ldots/3>1$ and certainly $60>1$.)


问:
Well definedness of $p:\mathbb{Z}/\gcd(m,n)\mathbb Z\rightarrow P$, universal property of the tensor product.
I am trying to get used to the universal property of the tensor product. I have tried to prove this common fact using the universal property

$\mathbb{Z}/n\mathbb Z\otimes \mathbb{Z}/m\mathbb Z \cong \mathbb{Z}/\gcd(m,n)\mathbb Z$

After checking that there is well-defined bilinear map (which i will call $b$) from $\mathbb{Z}/n\mathbb Z\otimes \mathbb{Z}/m\mathbb Z$ to $\mathbb{Z}/\gcd(m,n)\mathbb Z$ we need to show that we can factor any other bilinear map of $\mathbb Z$-modules $p:\mathbb{Z}/n\mathbb Z\otimes \mathbb{Z}/m\mathbb Z\rightarrow P$ over $b$.

The obvious thing to do is do define $i:\mathbb{Z}/\gcd(m,n)\mathbb Z\rightarrow P$ by $x\mod mn\mapsto p(x,1)$. I am having difficulty checking that this is well defined. We need to show that $p(x,1)=p(x',1)$ where $x'=x+k\cdot \gcd(m,n)$. But the only things we know are that

$p(x,1)=p(1,x)$

$p(x+n,1)=p(x,1)$

$p(1,y)=p(1,y+m)$

I have not been able to use these to prove well definedness.

This exercise has been asked many times on this website but I am asking specifically about why in a certain method a particular map is well defined. I don't want an answer using a different method.

答:
We have for some $a, b \in \mathbb{Z}$
$$
p(x + k \cdot \gcd(m,n),1) = p(x + k(am + bn), 1)
$$
$$
= p(x + kam, 1) =p(1, x + kam) = p(1,x) = p(x,1)
$$
because $\gcd(m,n)$ is an element which generates an ideal $(m,n)$ in PID $\mathbb{Z}$.


问:
Decidability Results for $\mathcal{L}_{\omega_1, \omega}$?
Recently I was giving a talk on decidability results in logic and I wanted to emphasize that there is more to life than than just First Order Logic. In particular, I made sure to include results such as $\mathsf{MSO}[<]$ and quantifiers like $\exists^\infty$,
$\exists^{n\text{ mod } m}$, etc. because I find those results extremely interesting (and you never know -- maybe that extra expressibility will let us solve a problem someday).

In particular, I mentioned infinitary logic as an example of a more expressive language because I think larger conjunctions and disjunctions are pretty easy to understand and act as a good complement to the bonus quantifiers.

Unfortunately I couldn't come up with (or find, on short notice) any decidability results for $\mathcal{L}_{\omega_1, \omega}$. We know that some $\mathsf{MSO}$ theories are decidable, so it doesn't seem too outlandish to think that some $\mathcal{L}_{\omega_1, \omega}$ theories might be too.

Does anybody have any results (ideally with references) in this vein?

Thanks in advance ^_^

答:
There are various things we can say.

Right off the bat though there's a serious type problem. When we talk about decidability without any further elaborations, we're referring to sets of natural numbers, or things which can "naturally" be coded as such (e.g. finite strings of rationals, formulas in the language of set theory, etc.). However, there are continuum-many $\mathcal{L}_{\omega_1,\omega}$-sentences, so right off the bat this is going to break down.

There are two obvious responses to this:

Restrict attention to countable fragments of $\mathcal{L}_{\omega_1,\omega}$.

Use some sort of generalized computability theory to handle the situation.

And in fact we can merge the two approaches:

Study countable fragments of $\mathcal{L}_{\omega_1,\omega}$ using generalized recursion theory.

Each of these three approaches yields interesting results, and in fact it's a bad idea to separate them too much (as indicated by the third). There's too much to put into a single answer, but I'll mention two specific topics which have driven lots of research and are surprisingly accessible. Note that I've backed away from decidability per se; the issues here are so foundational that it's really worth stepping all the way back and seeing how "complexity in $\mathcal{L}_{\omega_1,\omega}$" is developed in the first place.

Overall, I recommend the paper Barwise: infinitary logic and admissible sets as a starting point. While as the title suggests this focuses on the impact of one researcher in particular, it covers a lot of ground - and Barwise really was the most important figure in computability-theoretic infinitary logic, in my opinion. It's also extremely readable.

(The paper Barwise: abstract model theory and generalized quantifiers is also excellent and probably of interest, but less directly related. Ash and Knight's book meanwhile is extremely lovely and relevant, but is really limited to the particular case of $\mathcal{L}_{\omega_1,\omega}\cap L_{\omega_1^{CK}}$, which is not the whole story.)

Scott sentences

Probably the most striking thing about $\mathcal{L}_{\omega_1,\omega}$ right off the bat is Scott's isomorphism theorem, which says that every countable structure (in a countable language) can be "pinned down" by a single $\mathcal{L}_{\omega_1,\omega}$-sentence. Precisely:

Suppose $\mathfrak{A}$ is a countable structure in a countable language $\Sigma$. Then there is a $\mathcal{L}_{\omega_1,\omega}$-sentence $\varphi$ such that for every countable $\Sigma$-structure $\mathfrak{B}$ we have $$\mathfrak{B}\models\varphi\quad\iff\quad\mathfrak{B}\cong\mathfrak{A}.$$ (Note that $\varphi$ could still have models not isomorphic to $\mathfrak{A}$, they'd just have to be uncountable.)

Since countable structures are perfect for computability theory, we run into a bunch of natural questions right off the bat about the difficulty of finding a "Scott sentence" for a given structure. The first big theorem here is that this can force us beyond the computable:

There is a computable structure with no computable Scott sentence.

(Note that "computable $\mathcal{L}_{\omega_1,\omega}$-sentence" does make sense - $\mathcal{L}_{\omega_1,\omega}$-sentences are naturally coded by individual reals, or more clearly labelled well-founded trees, and we can talk about the computability of those codes.) The simplest example of such a thing is the Harrison order - see here.

It turns out that the question of measuring the "Scott complexity" of a computable (or general) structure is surprisingly nuanced - see e.g. here or here. I don't want to go into that here, though.

Fragments and proof systems

Building on work of Lopez-Escobar who looked at the whole $\mathcal{L}_{\omega_1,\omega}$, Barwise introduced the notion of a countable fragment of infinitary logic and showed that countable fragments have extremely nice properties. Specifically, suppose that $\mathbb{A}$ is a countable admissible set, that is, a countable transitive set satisfying $\mathsf{KP}$. Let $\mathcal{L}_{\mathbb{A}}=\mathcal{L}_{\infty,\omega}\cap\mathbb{A}$; that's not a typo, since $\mathbb{A}$ might not realize that each of its elements is countable. Then $\mathcal{L}_{\mathbb{A}}$ satisfies analogues of various properties of first-order logic, like the compactness and completeness theorems - now the Barwise compactness and Barwise completeness theorems. This lets us develop for example an analogue of Godel's incompleteness theorem fro fragments of infinitary logic (see also this old MO question of mine).

I'm glossing over and simplifying a lot here; Barwise's wonderful book is the go-to for all this. But the point is that with a reasonable proof theory in place, "Godel-style" complexity analyses can be carried out smoothly.

Note, however, that the relevant notion of computability is not classical computability; rather, we look at admissible recursion theory (or computability on admissible sets). The idea is that "finite" is replaced with "$\in\mathbb{A}$" and "c.e." is replaced with "$\Sigma_1$ over $\mathbb{A}$" - think about the special case $\mathbb{A}=L_\omega$ to see why this makes sense. This was initially hinted at by Kreisel and Kripke in the context of levels of $L$ specifically, the key breakthrough being that in "one level up" the right analogy is $\Pi^1_1$ = c.e. and $\Delta^1_1$ = finite (these correspond to "$\Sigma_1$-over-$L_{\omega_1^{CK}}$ subset of $\omega$" and "subset of $\omega$ which is an element of $L_{\omega_1^{CK}}$," respectively, and $\omega_1^{CK}$ is the first admissible ordinal $>\omega$).

The standard source on higher recursion theory is Sacks' book, although it really focuses on levels of $L$ (until it gets to $E$-recursion, which is a very different type of thing anyways). Computability on arbitrary admissible sets can actually be quite weird; an admissible set need not have a simply-definable well-ordering of itself, so we can't "index Turing machines" anymore in general.


问:
Question about Conditional Expectation from One Variable
I'm having a bit of trouble understanding how to solve this question in my textbook.

It says to allow X to have the following distribution:

Suppose you are then told that $X \geq 2$. Record a prediction of a future value of X
that uses this information.

I know that I need the expectation, but I was struggling a bit to find $\text{E}(X|X \geq 2)$. $$\text{E}(X|X \geq 2) = \sum_x{x\Pr(X=x|X \geq 2)}$$ and $$\Pr(X=x|X \geq 2) = \frac{\Pr(X=x \cap X\geq2)}{\Pr(X \geq 2)} \\ \Pr(X=x \cap X\geq2) = \frac{1}{2} \\ \Pr(X \geq 2) = \frac{1}{2}$$ so $$\text{E}(X|X \geq 2)= 8$$ which doesn't seem right at all.

edit: I'm really not sure how I got 8 lol!

答:
The summation binds $x$ to a (series of) particular value(s).  In your first line that ends with 1/2, you're using the union of all values $\geq 2$, but that's wrong for the probability expression in the sum.  You have to fill in 2, 3, 4 for $x$, one by one for both $x$'s in the sum.

(I'll let you work out the rest.)

[Not sure how you got 8, but it doesn't matter!]


问:
"Modified" spherical coordinates boundaries
Assume I want to calculate the volume of an ellipsoid $ \frac{x^{2}}{a^{2}}+\frac{y^{2}}{b^{2}}+\frac{z^{2}}{c^{2}}=1 $.

I know that the answer should be $abc$ times the volume of a unit sphere. Now using the following modified spherical coordinates:

$ x=ar\sin\theta\cos\varphi,\thinspace\thinspace\thinspace\thinspace\thinspace y=br\sin\theta\sin\varphi,\thinspace\thinspace\thinspace\thinspace z=cr\cos\theta $

I found the Jacobian would be $abc$. Im having trouble with understanding the new boundries; if it was a regular sphere, I know the bounderies would be $ 0\leq\theta\leq\pi,\thinspace\thinspace\thinspace\thinspace0\leq\varphi\leq2\pi,\thinspace\thinspace\thinspace\thinspace\thinspace0\leq r\leq1 $.

And in order to get the right result from the triple integral, I noticed that the boundaries remain the same, even though this is now exactly the regular spherical coordinates.

So my questions are:

How can I determine for sure the boundaries? is there an explanation for why the boundaries are supposed to remain the same?

2.Is there a way to calculate this integral with the regular spherical coordinates? (I guess that the boundaries would be the problem once again).

Thanks in advance.

答:
Note that the variable changes $u=\frac xa $, $v=\frac yb  $ and $w=\frac zc $ convert the ellipsoid $ \frac{x^{2}}{a^{2}}+\frac{y^{2}}{b^{2}}+\frac{z^{2}}{c^{2}}=1 $ to a unit sphere
$u^2+v^2+w^2=1$ and the volume integration becomes

$$V=\iiint_{ellipsoid}dxdydz=abc\iiint_{unit\>sphere} dudvdw\\
=abc\int_0^\pi\int_0^{2\pi} \int_0^1r^2\sin\theta dr d\theta \phi=\frac{4\pi}3 abc
$$


问:
Folland's Riesz representation theorem for $L^p$

I am reading the Folland's theorem 6.15. I have a hard time understanding the last part, where we assume $\mu$ is arbitrary. My questions are:

(1) How do we know $g_F=g_E$ a.e. on $E$? Could someone give me some more details please?

(2) How do we get $\int|g_F|^q+\int|g_{A-F}|^q=\int|g_A|^q$?

Thank you in advance!

答:
For $ E \subset X$, Folland identifies a function $f \in L^p(E)$ with its extension to $X$ that vanishes identically outside $E$.

For your first query: $g_F 1_E$ satisfies the defining property of $g_E$
(namely $\phi(f)=\int_E f g_F 1_E$ holds for all $f \in L^p(E)$.)
Thus uniqueness of $g_E$ implies that $g_F 1_E=g_E$.

For your second query: Note that $h=|g_A|^{q-1} \cdot{\rm sgn}(g)$ is in $L^p$ because $p(q-1)=q$. Write $B=A \setminus F$. Now
$$\int_F h 1_F g_F+ \int_B h 1_B g_B=\phi(h1_F)+\phi(h1_B)=\phi(h)=\int_A hg_A$$
gives the identity you want.


问:
Find vector set of all orthogonal vectors.
Find the vector set of all orthogonal to vectors $\vec{v}=(1, 2, 3, 4)$, $\vec{w} = (2, -2, 6, -4)$ in $\mathbb{R}^4$. I think orthogonal is means the vectors dot product to be $0$. I maybe can find one of the vectors, but how can I find all of them?

答:
As you said, the set of orthogonal vectors is such that its dot product with v and w are both 0. Choose the vector $(a, b, c, d)^T$ to represent the orthogonal vector. Take the dot product with both v and w to get $$a+2b+3c+4d=0\\2a-2b+6c-4d=0\\ \text{second equation implies } a=b-3c+2d\\\text{plug back in first equation to get }b=-2d\\\text{plug back in second equation to get }a=-3c$$

Thus the set of orthogonal vectors is $$\left(\begin{matrix}-3c\\-2d\\c\\d\end{matrix}\right)=\left(\begin{matrix}-3\\0\\1\\0\end{matrix}\right)c+\left(\begin{matrix}0\\-2\\0\\1\end{matrix}\right)d$$

I believe this can be called a plane in $\mathbb R^4$ as each point in the subspace has 2 degrees of freedom. Since there are 2 unique equations (neither of which is $0=0$ or $0=1)$ and which have no constant term, points in the resulting subspace will have their degree of freedom reduced by 2.


问:
Constructing continuous function using locally finite basis
(Munkres) Let $\mathscr{A}$ be a collection of subsets of $X$ such that $X=$ $\bigcup_{A \in \mathscr{A}} A,$ and let $f: X \rightarrow Y$ be such that $\left.f\right|_{A}$ is continuous, for every $A \in \mathscr{A}$.

We say $\mathscr{A}$ is locally finite if for every $x \in X,$ there is a neighborhood $U \subset X$ of $x$ such that $\{A \in \mathscr{A} \mid U \cap A \neq \emptyset\}$ is finite. Show that if $\mathscr{A}$ is locally finite and if each $A \in \mathscr{A}$ is closed in $X,$ then $f$ is continuous. Give an example to show that the result may fail if $\mathscr{A}$ is not locally finite.

I'm new to topology. My attempt so far:

$\forall\;V\subseteq Y$ such that $V$ is open in $Y$, $f^{-1}(V)\cap A$ is open in $A$ for every $A \in \mathscr{A}$. Another point to note is, if $x \in int\;A$ then $f$ is continuous at $x$, therefore we only need to prove continuity for points on the boundaries of sets in $\mathscr{A}$ (even though I'm confused about the fact that in analysis we talk about continuity at a point but in topology we only talk about continuity of the function as a whole, defined by pre-images of open sets being open). Also, for some finite subcollection $\{A_i\}_i$ of $\mathscr{A}$, $x \in \cap_i A_i$ and $x \notin A$ for all other $A \in \mathscr{A}$. For any sequence $x_n \rightarrow x$, $\exists N$ s.t. for all $n > N$, $x_n \in A_i$ for some $i$ (we would not be able to say this without local finiteness). Therefore by continuity of $f|_A$, $f(x_n) \rightarrow f(x)$.

I did the sequential proof based off my analysis courses where I have dealt with only metric spaces. I'm not sure if the sequential proof is correct in the context of topology.

答:
In metric spaces the topology is completely characterized by the convergent sequences, but in topological spaces in general this is not the case: a point $x$ can be a limit point of a set $A$ even if no sequence in $A$ converges to $x$. Thus, you need to find an approach that doesn’t use sequences. It’s also not enough to know that $x$ belongs to only finitely many of the sets in $\mathscr{A}$, because it might still be a limit point of infinitely many of them. In technical terms, it’s not enough for the collection $\mathscr{A}$ to be point finite, meaning that no point is in infinitely many members of $\mathscr{A}$: we really do need to know that $\mathscr{A}$ is locally finite.

And in fact the result is false as stated: you need to assume further that the members of $\mathscr{A}$ are closed sets. I see that Henno Brandsma has already explained how to prove that in that case $f$ is continuous, so I’ll simply add an example to show that the result is not true in general.

Let $X=[0,2]$ with the usual topology. Let $\mathscr{A}=\{[0,1),[1,2]\}$; $\bigcup\mathscr{A}=X$, and since $\mathscr{A}$ is finite, it is certainly locally finite. Let $Y=\{0,1\}$ with the discrete topology, and let

$$f:X\to\Bbb R:x\mapsto\begin{cases}
0,&\text{if }x\in[0,1]\\
1,&\text{if }x\in(1,2]\,;
\end{cases}$$

clearly $f\upharpoonright[0,1)$ and $f\upharpoonright[1,2]$ are continuous, but $f^{-1}[\{0\}]=[0,1]$ is not open in $X$ even though $\{0\}$ is open in $Y$, so $f$ is not continuous.

In fact we can construct such an example in any space that does not have the discrete topology. Let $X$ be such a space; then there is an $A\subseteq X$ such that $A$ is not clopen. Let $\mathscr{A}=\{A,X\setminus A\}$, let $Y$ be as before, and let

$$f:X\to\Bbb R:x\mapsto\begin{cases}
0,&\text{if }x\in A\\
1,&\text{if }x\in X\setminus A\,;\,;
\end{cases}$$

clearly $\mathscr{A}$ is locally finite and $f\upharpoonright A$ and $f\upharpoonright X\setminus A$ are continuous. $\{0\}$ is clopen in $Y$, but $f^{-1}[\{0\}]$ is not clopen in $X$, so $f$ is not continuous.

Note: In case you’ve not yet encountered the term a clopen set is one that is both closed and open. Since $A$ in that last example is not clopen, either it is not open, or it is not closed (or both).


问:
Analytic expression for $\mathbb E_X[(X^\top u)^p (X^\top v)^p]$, where $u$ and $v$ are fixed vectors in $\mathbb R^d$ and $X$ is uniform on sphere
Let $u$ and $v$ be fixed vectors in $\mathbb R^d$. Let $X$ be a random vector uniformly distributed on the unit-sphere in $\mathbb R^d$, and let $f_p$ be a real polynomial of degree $p \ge 1$ (for simplicity, we might simply consider $f_p(t) \equiv t^p$).

Question. What is an analytic expression for the correlatetion $c(u,v) := \mathbb E_X[f(X^\top u)f(X^\top v)]$ ?

Special case $p=1$

In this case, a simple computation gives

$$
c(u,v) = \mathbb E[X^\top uv^\top X] = \mbox{trace}(\mbox{cov}(X)uv^\top) = \mbox{trace}((1/d) I_d uv^\top) = \frac{u^\top v}{d}
$$

Is it too crazy to conjecture that in general, $c(u,v) = K_{d,p} \cdot (u^\top v)^p$, for some constant $K_{d,p}$ which only depends on $d$ and $p$ ?

答:
Let $Y=(Y_1,\ldots,Y_d)$ be a collection of iid $N(0,1)$'s. Then by using (hyper)spherical coordinates
$$
E[(Y\cdot u)^p(Y\cdot v)^q]=(2\pi)^{-\frac{d}{2}}\int_{0}^{\infty}dr\ {\rm vol}(S^{d-1}) \ r^{d-1+p+q}\ e^{-\frac{r^2}{2}}
\ E[(X\cdot u)^p(X\cdot v)^q]
$$
$$
=\frac{2^{\frac{p+q}{2}}\Gamma\left(\frac{p+q+d}{2}\right)}{\Gamma\left(
\frac{d}{2}\right)}\times
\ E[(X\cdot u)^p(X\cdot v)^q]
$$
We need $p+q$ even for a nonzero result, so we assume that. The Gaussian expectation
$E[(Y\cdot u)^p(Y\cdot v)^q]$ can be computed with the Isserlis-Wick Theorem. It amounts to a sum over complete matchings of a set with $p+q$ elements subdivided into two compartments, one of size $p$ and one of size $q$. Let me organize the count according to $k$, the number of matched pairs joining the two compartments. We then get
$$
E[(Y\cdot u)^p(Y\cdot v)^q]=
$$
$$
\sum_{k}\binom{p}{k}\binom{q}{k}
\times k!\times\frac{(p-k)!}{2^{\frac{p-k}{2}}\left(\frac{p-k}{2}\right)!}
\times\frac{(q-k)!}{2^{\frac{q-k}{2}}\left(\frac{q-k}{2}\right)!}
\times (u\cdot v)^{k}(u\cdot u)^{p-k}(v\cdot v)^{q-k}
$$
where the sum is over $0\le k\le\min(p,q)$ of same parity as $p$ and $q$.

Finally, after some cleanup,
$$
E[(X\cdot u)^p(X\cdot v)^q]=
$$
$$
\frac{p!q!\ \Gamma\left(
\frac{d}{2}\right)}{2^{p+q}\ \Gamma\left(
\frac{p+q+d}{2}\right)}\times \sum_k
\frac{2^k}{k!\left(\frac{p-k}{2}\right)!\left(\frac{q-k}{2}\right)!}\times
(u\cdot v)^{k}(u\cdot u)^{p-k}(v\cdot v)^{q-k}
$$
with the same range of summation for $k$.

(this is a quick computation, didn't yet check for errors typos etc.)


问:
Approximating sums of powers of integers: why does $\sum_{i=1}^n i^r \div \frac{n^{r+1}}{r+1} \to 1$ as $n \to \infty$?
I know there are exact formulas for sums of integer powers of integers ($\sum_{i=1}^n i^r$ with $r \in \mathbb{N}$), but I was interested in approximating them. One way occured to me through a geometrical argument. If you arrange $1,2,3,...,n-1,n$ as a right-angled triangle, they fill up about half of the square $n^2$. Similarly if you arrange $1^2,2^2,3^2,...,(n-1)^2,n^2$ as a 'right-angled' pyramid, they fill up about a third of the cube $n^3$. This suggests the general approximation: $$\sum_{i=1}^n i^r \approx \frac{n^{r+1}}{r+1}$$
and indeed I've found numerically that $$\lim_{n\to\infty}{\frac{\sum_{i=1}^n i^r}{\frac{n^{r+1}}{r+1}}} \to 1.$$How can I prove this?</p>

答: One can show by induction on $r$ that $\sum_{i=1}^n i^r$ is a polynomial funtion in $n$ of degree $d=r+1$. Then noting that $(n+1)^d=n^d+d\cdot n^{d-1}+{d\choose 2}n^{d-2}+\ldots$ you get the asymptotic result.</p>


问:
Ordering of elements
I have 40 elements I need to order (for simplicity just call them "1" - "40"). There are a few rules regarding how I must order some elements:

Elements "2" and "5" must go before element "10",
Element "10" must go before element "7",
Element "7" must go before elements "3" and "28"

How many distinct ways can I make these arrangements?

I think I have to use a partial permutation. I drew it out like this:

"2" (could have elements between) "5"...."10"...."7"...."3" (could have elements between) "28"

I'm lost after this step, however. I know how to use partial permutations with respect to preserving a group of elements that must go together but I am not sure what to make of this problem.

答:
Choose $6$ positions out of $40$, in $40\choose 6$ ways. Arrange the numbers $2,5,10,7,3,28$ into those $6$ positions so that the conditions are satisfied. This is possible in $4$ ways (you can use the order above, or you can swap $2$ with $5$ and/or $3$ with $28$). Arrange the other $34$ elements in any of the $34!$ possible ways. The total number is:

$${40\choose 6}\cdot 34!\cdot 4=\frac{4\cdot 40!}{6!}$$

Title: Ordering of elements


问:
How do I approach this Combinatorics problem?
This is a question put up by Jane Street in their monthly Puzzle Archive.
The Problem

I'll write the problem here as well.

Jane received 78 figurines as gifts this holiday season:  12 drummers drumming, 11 pipers piping, 10 lords a-leaping, etc., down to 1 partridge in a pear tree. They are all mixed together in a big bag.  She agrees with her friend Alex that this seems like too many figurines for one person to have, so she decides to give some of her figurines to Alex. Jane will uniformly randomly pull figurines out of the bag one at a time until she pulls out the partridge in a pear tree, and will give Alex all of the figurines she pulled out of the bag (except the partridge, that’s Jane’s favorite).

If n is the maximum number of any one type of ornament that Alex gets, what is the expected value of n, to seven significant figures?

I approached the problem in this way. Please have a look. My Approach

I'll assume the following (in my approach) -

Let Ci - Selecting 'i' Identical candies before partridge is taken out.
Then I'll compute for each, C2 to C12 - for each type of figurine that fits the criteria.

Example C5 - Selecting 5 identical candies before partridge is taken out. It can be anything from type-5 figurine to type 12 (Drummers).

Is this the right way to solve it. Am i right in the fundamentals ? Is there a better way to go about the problem.

答:
The question is asking for $$\sum_{i=0}^{12}P(\text{max number of same figurine in
sequence is } i | \text{sequence ends with a } 1)*i$$
If we can solve $P(\text{max number of same figurine in
sequence is } i | \text{sequence ends with a } 1)$ for each $i$ then the answer is trivially found.

I'll consider a simpler case ($n=3$) for clarity. Note that these sequences have not been permuted.

max count of same figurine in sequence is $0$ given that sequence ends with a 1

$$1$$

max count of same figurine in sequence is $1$ given that sequence ends with a 1

$$21,31,321$$

max count of same figurine in sequence is $2$ given that sequence ends with a 1

$$221,3221,331,3321, 33221$$

max count of same figurine in sequence is $3$ given that sequence ends with a 1
$$3331, 33321, 333221$$

I'll use $P(i)$ to mean $P(\text{max number of same figurine in
sequence is } i | \text{sequence ends with a } 1)$ from this point on.

$$P(0) = \frac{1}{\frac{n*(n+1)}{2}}\ (\frac{1}{6} \text{in this case})$$

$$P(1) = \frac{1!}{1!} \frac{2}{6}\frac{1}{6} + \frac{1!}{1!} \frac{3}{6}\frac{1}{6} + \frac{2!}{1!} \frac{2}{6}\frac{1}{6}$$

$$P(2) = \frac{2!}{2!} \frac{2}{6}\frac{1}{6}\frac{1}{6} + \frac{3!}{2!} \frac{3}{6}\frac{2}{6}\frac{1}{6}\frac{1}{6} + \frac{2!}{2!} \frac{3}{6}\frac{2}{6}\frac{1}{6}+\frac{3!}{2!} \frac{3}{6}\frac{2}{6}\frac{2}{6}\frac{1}{6}+\frac{4!}{2!2!} \frac{3}{6}\frac{2}{6}\frac{2}{6}\frac{1}{6}\frac{1}{6}$$

$$P(3) = \frac{3!}{3!} \frac{3}{6}\frac{2}{6}\frac{1}{6}\frac{1}{6} + \frac{4!}{3!}\frac{3}{6}\frac{2}{6}\frac{1}{6}\frac{2}{6}\frac{1}{6} + \frac{5!}{3!2!} \frac{3}{6}\frac{2}{6}\frac{1}{6}\frac{2}{6}\frac{1}{6}\frac{1}{6}$$

And so the expected value would just be $P(0)*1+P(1)*1+P(2)*2+P(3)*3=1.65$

This naive computation would not be feasible by hand for $n=12$ because you'd have to compute somewhere around $\frac{77!}{2!3!4!5!6!7!8!9!10!11!12!}$ sequences (and this is an underestimate since we can also have sequences with length less than $77$).

The question we should ask at this point is what can we do to avoid computing more than what we have to?

Let's just take a look at the sequence $333221$. The probability for getting this is $$\frac{5!}{3!2!}\frac{3}{6}\frac{2}{6}\frac{1}{6}\frac{2}{6}\frac{1}{6}\frac{1}{6}$$
Notice that we already know the probability of getting $221$ when we were computing $P(2)$ so the question is how can we refactor the probability of getting $333221$ in such a way that we can reuse the result from probability of getting $221$?

Suppose we were given probability of getting $221$, let's consider the spots we can put $3$ in.

$$\_2\_2\_1$$

Here is where we should consider how we can partition the number 3, because we can have either choose to put $333$ in one spot, $3$ in three spots or $3$ in one spot and $33$ in one spot (for example $3332\_2\_1, 323231, 332\_231$). Luckily, this is a known problem on leetcode.com.

Since $3$ is small, I'll just list out the possible ways of partitioning $3$, $[3] (\frac{1!}{1!}), [1,2](2!), [1,1,1] (\frac{3!}{3!}))$. So probability of getting $333221$ is
$$
\underbrace{\bigg({3\choose 1}\frac{1!}{1!}+{3\choose 2}2!+{3\choose 3}\frac{3!}{3!}\bigg)}_{\text{ways to partition } 3}*\underbrace{\frac{3}{6}\frac{2}{6}\frac{1}{6}}_{\text{probability to get } 3 \text{ 3 times}}*\underbrace{\frac{2!}{2!}\frac{2}{6}\frac{1}{6}\frac{1}{6}}_{\text{probability of getting } 221} $$
$$
\begin{align*}&=\bigg(\frac{3!}{2!}+\frac{3!*2!}{2!}+\frac{3!}{3!}\bigg)*\dots\\
&=10*\underbrace{\frac{3}{6}\frac{2}{6}\frac{1}{6}}_{\text{probability to get } 3 \text{ 3 times}}*\underbrace{\frac{2!}{2!}\frac{2}{6}\frac{1}{6}\frac{1}{6}}_{\text{probability of getting } 221}\\
&= \frac{5!}{3!2!}\frac{3}{6}\frac{2}{6}\frac{1}{6}\frac{2}{6}\frac{1}{6}\frac{1}{6}
\end{align*}$$

This brings us to our optimisation. Let p[i][j] be the array of probability of sequences with max number of any figurine at most i and we consider only all elements to the left of j. For clarity, here's a couple of examples for n=3:

p[3][2] is empty because we don't have $3$ $2$s

p[3][3] represents $3331, 33321, 333221$

p[2][3] represents $3221, 331, 3321, 33221$

p[2][2] represents $221$

p[2][1] is empty because we stop as soon as we draw $1$ and there are no elements left of $1$

p[1][3] represents $31, 321$

p[1][2] represents $21$

p[0][1] represents $1$

p[0][2] is empty since otherwise this would have max number of any figurine = 1.

Then p[i][j] can be formed by adding two parts:

probability of getting $j$ from $1$ to $i-1$ times, how many ways we can partition $i$ and probabilities from p[i][k] where $1\leq k\leq j-1$

probability of getting $j$ $i$ times, how many ways we can partition $i$ and probabilities from p[l][m] where $0\leq l \leq i$ and $1\leq m \leq j-1$

Note that in all cases we have p[0][1] being a length $1$ array (or whatever data structure you prefer) containing $\frac{1}{\frac{n(n+1)}{2}}$ as our base case.

Then $P(1) = \sum_{j=0}^{12}\sum_k p[1][j][k]$, $P(2) = \sum_{j=0}^{12}\sum_k p[2][j][k]$ and so on.


问:
Sieve formula of Eratosthenes
Let $P=\prod_{p\leq\sqrt{x}}p$ Then $\sqrt{x}<n\leq x$ is prime $\iff$ $(n,P)=1$

Then $\pi(x)-\pi(\sqrt{x})+1=\sum_{n\leq x}\delta((n,P))$ Now the book I am reading says
$\sum_{n\leq x}\delta((n,P))=\sum_{d|P}\mu(d)\lfloor\frac{x}{d}\rfloor$ and I am not sure where this comes from.
$$\sum_{n\leq x}\delta((n,P))=\sum_{n\leq x}\sum_{d|(n,P)}\mu(d)$$
Comes from mobius inversion. I do not see how this is equal to $\sum_{d|P}\mu(d)\lfloor\frac{x}{d}\rfloor$

答:
$$\sum_{n\le x}\sum_{d|\gcd(n,P)}\mu(d)=\sum_{n\le x}\sum_{\substack {d|n\\d|P}}\mu(d)$$
and by replacing $n=dm$ we have the above equals to $$\sum_{d|P}\sum_{m\le x/d}\mu(d)=\sum_{d|P}\mu(d)\left[\dfrac{x}{d}\right]$$

Title: Sieve formula of Eratosthenes


问:
One of $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$ for odd $n$

Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$.

I know that pigeonhole principle would be helpful, but how should I apply it? Thanks.

答:
Observe that there are $n$ such number with the possible number of remainders is $n-1$ from $1,2,\cdots,n-2,n-1$ because  if $0$  is a remainder for some $r,$ then $n|(2^r-1)$ and we are done.

Otherwise using Pigeonhole Principle, at least for two distinct values $r$ we shall have same remainder

Let $2^t-1\equiv2^s-1\pmod n$ where $t>s$

$\implies n|\{(2^t-1)-(2^s-1)\}\implies n| 2^s(2^{t-s}-1)\implies n|(2^{t-s}-1)$ as $(2,n)=1$

Clearly, $0<t-s<n$ as $n\ge t>s\ge1$


问:
Throw a coin one million times. What is the expected number of sequences of six tails, if we do not allow overlap?
Question itself: Throw a coin one million times. What is the expected number of sequences of six tails, if we do not allow overlap?

I know when overlap is allowed, the answer is (1,000,000-5)/(2^6). Not sure if we can just do (1,000,000-5)/(2^6) divided by 6 if overlap is not allowed?

Some clarifications:

For example, if part of the sequence is "one H, nine T, then one H", we would count 1 sequence of six tails. (When overlap is allowed, we can count three times because each of the first 3 T can start a sequence of six tails; However, this question does not allow overlap, so 9T can only be counted as containing one sequence of six tails)

If part of the sequence is "one H, thirteen T, then one H", we would count 2 sequences of six tails.

答:
I think I can compute that with an error of plus or minus 1.

This is a sketchy argument that you can make rigorous using Ergodic Theory or Palm measures.

Let us group runs of T from left to right, so a run of 14 T's has a run of 6 starting at position 1, another run starting at position 7, and two single T's at positions 13 and 14 that are not grouped.

Imagine a doubly-infinite sequence of H and T

You can construct it as a doubly infinite sequence of H and an doubly infinite iid sequence of H^k where k+1 is random Geometric(0.5). The average distance between H's is 2 and the average number of non-overlapping runs TTTTTT before the next H equals 1/63.

So a proportion of 1/126 of the integers will be the leftmost point of a non-overlapping group of 6.

The answer would be 1,000,000/126, except that this is not counting the case where a sequence of T's start at some x<0 and ends at 0<x<6 with more T's in x+1,...,6, and it counts the case of an x near the end which is the start of a run that actually ends after the interval. So 1,000,000/126 is the expectation of a random variable that can differ from your random variable by at most 1 unit.

You can probably improve it to an exact number but I'm quite happy with this approximation.


问:
How to show this sequence is unbounded?
$S_n=1+1/2+1/3+....+1/n$,for all n=1,2,3,...,
The question is to show it is divergent. I am thinking if I can prove it is unbounded, i.e., not bounded above, then I prove it. But I don't know how to say it is not bounded above rigorgosly.

Title: How to show this sequence is unbounded?

Body:
$$\begin{align} S_{2n}&=\sum_{k=1}^{2n}\frac1k\\
&=\sum_{k=1}^n\left(\frac1{2k-1}+\frac1{2k}\right)\\
&=\frac32+\sum_{k=2}^n\left(\frac1{2k-1}+\frac1{2k}\right)\\
&\ge\frac32+\sum_{k=2}^n\left(\frac1{2k}+\frac1{2k}\right)\\
&=\frac32+\sum_{k=2}^n\frac1k\\
&=\frac12+S_n\end{align}$$


答:
Hints:

$$(1)\;\;\;2^k-1=2^{k-1}+2^{k-2}+\ldots+2+1\;,\;\;k\in\Bbb N$$

$$(2)\;\;\;\text{Every natural number $\,n\,$ can be uniquely written in base two }$$

$$\text{with maximal power of two less than $\,n\,$ }$$

Title: One of $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$ for odd $n$

Body:
Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$.

I know that pigeonhole principle would be helpful, but how should I apply it? Thanks.


问:
If $a \in \Bbb R$ and $W=\{p \in P_n \mid p(a)=0\}$, show that $W$ is a subspace of $P_n$.
Let $P_n$ be a vector space of all polynomials with real coefficients and of degree $n$ or less. If $a \in \Bbb R$ and $W=\{p \in P_n \mid p(a)=0\}$, show that $W$ is a subspace of $P_n$.

Edit:

Attempt:
Denote $0_p$ be the zero polynomial.

Since $0_p(a)=0 \in W$, then
$0_p \in W$ and thus, $W \ne \emptyset$.

Let $p,q \in W$. Then,
$p(a)=0=q(a)$ for some $a \in \Bbb R$.
Now, $(p+q)(a) = p(a)+q(a)=0+0=0$. Hence, $p+q \in W$.

Let $p \in W$. Let $c$ be an arbitrary scalar. Then, $p(a)=0$ for some $a \in \Bbb R$. Now, $(cp)(a)=cp(a)=c0=0$.
Hence, $cp \in W$.

Thus, $W$ is a subspace of $P_n$.

Am I true?

答:
Spot on.

You can also condense the latter two properties into one: $$\forall \alpha, \beta \in \Bbb R; p, q\in W \implies\alpha p + \beta q \in W $$


答:
Yes, that's fine.

In case you have this tool available, you might also simply observe that $W$ is defined as the kernel of the linear map $P_n\to\Bbb R$, $p\mapsto p(a)$ and therefore a subspace.

Body:
Let $P_n$ be a vector space of all polynomials with real coefficients and of degree $n$ or less. If $a \in \Bbb R$ and $W=\{p \in P_n \mid p(a)=0\}$, show that $W$ is a subspace of $P_n$.

Edit:

Attempt:
Denote $0_p$ be the zero polynomial.

Since $0_p(a)=0 \in W$, then
$0_p \in W$ and thus, $W \ne \emptyset$.

Let $p,q \in W$. Then,
$p(a)=0=q(a)$ for some $a \in \Bbb R$.
Now, $(p+q)(a) = p(a)+q(a)=0+0=0$. Hence, $p+q \in W$.

Let $p \in W$. Let $c$ be an arbitrary scalar. Then, $p(a)=0$ for some $a \in \Bbb R$. Now, $(cp)(a)=cp(a)=c0=0$.
Hence, $cp \in W$.

Thus, $W$ is a subspace of $P_n$.

Am I true?